rpm  5.4.10
tsort
Go to the documentation of this file.
1 /*! \page tsort Package ordering in rpm-4.0.1 and later
2 
3 The package ordering algorithm in rpm-4.0.1 has changed.
4 
5 \subsection tsort_problem The Problem
6 
7 Here's a simple test to illustrate the need for the change (from
8 bugzilla #12327):
9 
10 Assume the minimal 7.0 package manifest in /tmp/list
11 \verbatim
12  /mnt/rpm/comps/dist/7.0/sparc/bash-2.04-11.sparc.rpm
13  /mnt/rpm/comps/dist/7.0.2/sparc/glibc-2.1.94-1.sparc.rpm
14  /mnt/rpm/comps/dist/7.0/sparc/mktemp-1.5-5.sparc.rpm
15  /mnt/rpm/comps/dist/7.0/noarch/basesystem-7.0-2.noarch.rpm
16  /mnt/rpm/comps/dist/7.0/noarch/setup-2.3.4-1.noarch.rpm
17  /mnt/rpm/comps/dist/7.0/noarch/filesystem-2.0.7-1.noarch.rpm
18  /mnt/rpm/comps/dist/7.0/sparc/libtermcap-2.0.8-25.sparc.rpm
19  /mnt/rpm/comps/dist/7.0/noarch/termcap-11.0.1-3.noarch.rpm
20 \endverbatim
21 
22 with database initialization as
23 \verbatim
24  mkdir -p /tmp/ROOT/var/lib/rpm
25  rpm --initdb /tmp/ROOT/var/lib/rpm
26 \endverbatim
27 
28 This command "works"
29 \verbatim
30  rpm -Uvh -r /tmp/ROOT `cat /tmp/list`
31 \endverbatim
32 while this command
33 \verbatim
34  rpm -Uvh -r /tmp/ROOT `tac /tmp/list`
35 \endverbatim
36 fails with
37 \verbatim
38  loop in prerequisite chain: libtermcap bash libtermcap
39 \endverbatim
40 
41 \note The 2nd upgrade reverse orders the packages in the manifest.
42 
43 The problem is that the previous ordering algorithm, basically a very clever
44 implementation of tsort, was sensitive to initial conditions, and the first
45 command "happens" to snip a loop, while the second does not.
46 
47 \subsection tsort_solution The Solution
48 
49 The current ordering algorithm is exactly tsort from Knuth V1, with one further
50 twist. Since the only way out of a dependency loop is to snip the loop
51 somewhere, rpm uses hints from Requires: dependencies to distinguish
52 co-requisite (these are not needed to install, only to use, a package) from
53 pre-requisite (these are guaranteed to be installed before the package that
54 includes the dependency) relations.
55 
56 There is now syntax in spec files to explicitly specify the source of a
57 Requires: dependency. If, for example, you use grep in %post, then you
58 as a packager would normally add
59 \verbatim
60  PreReq: grep
61 \endverbatim
62 in order to insure that grep was installed before attempted use by the
63 %postun scriptlet.
64 
65 Now the same dependency can be expressed more precisely as
66 \verbatim
67  Requires(post): grep
68 \endverbatim
69 
70 For completeness, here's the complete set of tokens that may be
71 added to Requires: as in the example above:
72 \verbatim
73  "interp", RPMSENSE_INTERP
74  "prereq", RPMSENSE_PREREQ
75  "preun", RPMSENSE_SCRIPT_PREUN
76  "pre", RPMSENSE_SCRIPT_PRE
77  "postun", RPMSENSE_SCRIPT_POSTUN
78  "post", RPMSENSE_SCRIPT_POST
79  "rpmlib", RPMSENSE_RPMLIB
80  "verify", RPMSENSE_SCRIPT_VERIFY
81 \endverbatim
82 
83 Ditto BuildRequires:
84 \verbatim
85  "prep", RPMSENSE_SCRIPT_PREP
86  "build", RPMSENSE_SCRIPT_BUILD
87  "install", RPMSENSE_SCRIPT_INSTALL
88  "clean", RPMSENSE_SCRIPT_CLEAN
89 \endverbatim
90 but let's not go there (yet).
91 
92 For giggles, you can also do stuff like
93 \verbatim
94  Requires(pre,post): /bin/sh
95 \endverbatim
96 
97 By marking dependencies more precisely, rpm can distinguish between
98 an upgrade context (like the use of grep in %post above) and an installed
99 context (like the autogenerated Requires: in a package that includes a
100 script with #!/bin/sh), and that permits rpm to differentiate pre-requisites
101 from co-requisites while doing package ordering.
102 
103 Here's what cures the libtermcap <-> bash loop:
104 \verbatim
105  Requires(postun): /bin/sh
106 \endverbatim
107 which, since the dependency is clearly not useful or necessary in determining
108 install ordering, is safely ignored.
109 
110 \subsection tsort_sideeffects Side Effects
111 
112 One of the side effects of changing the package install ordering, is that
113 there are a handful of new loops that are detected. Here's what I found
114 looking at supported Red Hat releases:
115 
116 \verbatim
117  ghostscript-fonts ghostscript
118  /* 7.0 only */
119  pango-gtkbeta-devel pango-gtkbeta
120  XFree86 Mesa
121  compat-glibc db2
122  compat-glibc db1
123  pam initscripts
124  kernel initscripts
125  initscripts sysklogd
126  /* 6.2 */
127  egcs-c++ libstdc++
128  /* 6.1 */
129  pilot-link-devel pilot-link
130  /* 5.2 */
131  pam pamconfig
132 \endverbatim
133 
134 Why are there new loops? Because tsort is trying to use all of the
135 dependency relations for ordering, while the previous tsort ignored all
136 Requires: from added packages.
137 
138 Except for the "well known" libtermcap <-> bash loop (which is just wrong),
139 all of the other dependencies are simply not needed in an upgrade context
140 to perform package ordering. Please note that all of the known to cause
141 loop dependencies listed above are, for now, explicitly ignored when
142 determining package install ordering.
143 
144 \subsection tsort_summary Summary
145 
146 So what does this all mean? Basically not much, unless you find yourself
147 trying to specify dependencies amongst a set of packages correctly and
148 happen to create a dependency loop.
149 
150 And, before you start adding the new-fangled syntax to packages, please
151 remember that rpm will almost certainly be auto-generating fine-grained
152 dependencies for %post et al scriptlets pretty soon. Truly, rpm needs to
153 make packaging easier, not provide Yet More Complicated Syntax in spec files.
154 
155 With thanks to Ken Estes for doing the implementation in bash2 that makes
156 it possible to auto-generate scriptlet dependencies, blame me for the long,
157 slow deployment.
158 
159 */