<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Package ordering in rpm-4.0.1 and later</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.2.17 -->
<center>
<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="modules.html">Modules</a> <a class="qindex" href="annotated.html">Data Structures</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Data Fields</a> <a class="qindex" href="globals.html">Globals</a> <a class="qindex" href="pages.html">Related Pages</a> </center>
<hr><h2><a name="tsort">Package ordering in rpm-4.0.1 and later</a>
</h2> The package ordering algorithm in rpm-4.0.1 has changed.
<p>
<h3><a name="tsort_problem">The Problem</a>
</h3>
<p>
Here's a simple test to illustrate the need for the change (from bugzilla #12327):
<p>
Assume the minimal 7.0 package manifest in /tmp/list <div class="fragment"><pre>
/mnt/redhat/comps/dist/7.0/sparc/bash-2.04-11.sparc.rpm
/mnt/redhat/comps/dist/7.0.2/sparc/glibc-2.1.94-1.sparc.rpm
/mnt/redhat/comps/dist/7.0/sparc/mktemp-1.5-5.sparc.rpm
/mnt/redhat/comps/dist/7.0/noarch/basesystem-7.0-2.noarch.rpm
/mnt/redhat/comps/dist/7.0/noarch/setup-2.3.4-1.noarch.rpm
/mnt/redhat/comps/dist/7.0/noarch/filesystem-2.0.7-1.noarch.rpm
/mnt/redhat/comps/dist/7.0/sparc/libtermcap-2.0.8-25.sparc.rpm
/mnt/redhat/comps/dist/7.0/noarch/termcap-11.0.1-3.noarch.rpm
</pre></div>
<p>
with database initialization as <div class="fragment"><pre>
mkdir -p /tmp/ROOT/var/lib/rpm
rpm --initdb /tmp/ROOT/var/lib/rpm
</pre></div>
<p>
This command "works" <div class="fragment"><pre>
rpm -Uvh -r /tmp/ROOT `cat /tmp/list`
</pre></div> while this command <div class="fragment"><pre>
rpm -Uvh -r /tmp/ROOT `tac /tmp/list`
</pre></div> fails with <div class="fragment"><pre>
loop in prerequisite chain: libtermcap bash libtermcap
</pre></div>
<p>
<dl compact><dt><b>Note: </b></dt><dd>
The 2nd upgrade reverse orders the packages in the manifest.</dl>The problem is that the previous ordering algorithm, basically a very clever implementation of tsort, was sensitive to initial conditions, and the first command "happens" to snip a loop, while the second does not.
<p>
<h3><a name="tsort_solution">The Solution</a>
</h3>
<p>
The current ordering algorithm is exactly tsort from Knuth V1, with one further twist. Since the only way out of a dependency loop is to snip the loop somewhere, rpm uses hints from Requires: dependencies to distinguish co-requisite (these are not needed to install, only to use, a package) from pre-requisite (these are guaranteed to be installed before the package that includes the dependency) relations.
<p>
There is now syntax in spec files to explicitly specify the source of a Requires: dependency. If, for example, you use grep in post, then you as a packager would normally add <div class="fragment"><pre>
PreReq: grep
</pre></div> in order to insure that grep was installed before attempted use by the postun scriptlet.
<p>
Now the same dependency can be expressed more precisely as <div class="fragment"><pre>
Requires(post): grep
</pre></div>
<p>
For completeness, here's the complete set of tokens that may be added to Requires: as in the example above: <div class="fragment"><pre>
"interp", RPMSENSE_INTERP
"prereq", RPMSENSE_PREREQ
"preun", RPMSENSE_SCRIPT_PREUN
"pre", RPMSENSE_SCRIPT_PRE
"postun", RPMSENSE_SCRIPT_POSTUN
"post", RPMSENSE_SCRIPT_POST
"rpmlib", RPMSENSE_RPMLIB
"verify", RPMSENSE_SCRIPT_VERIFY
</pre></div>
<p>
Ditto BuildRequires: <div class="fragment"><pre>
"prep", RPMSENSE_SCRIPT_PREP
"build", RPMSENSE_SCRIPT_BUILD
"install", RPMSENSE_SCRIPT_INSTALL
"clean", RPMSENSE_SCRIPT_CLEAN
</pre></div> but let's not go there (yet).
<p>
For giggles, you can also do stuff like <div class="fragment"><pre>
Requires(pre,post): /bin/sh
</pre></div>
<p>
By marking dependencies more precisely, rpm can distinguish between an upgrade context (like the use of grep in post above) and an installed context (like the autogenerated Requires: in a package that includes a script with #!/bin/sh), and that permits rpm to differentiate pre-requisites from co-requisites while doing package ordering.
<p>
Here's what cures the libtermcap <-> bash loop: <div class="fragment"><pre>
Requires(postun): /bin/sh
</pre></div> which, since the dependency is clearly not useful or necessary in determining install ordering, is safely ignored.
<p>
<h3><a name="tsort_sideeffects">Side Effects</a>
</h3>
<p>
One of the side effects of changing the package install ordering, is that there are a handful of new loops that are detected. Here's what I found looking at supported Red Hat releases:
<p>
<div class="fragment"><pre>
ghostscript-fonts ghostscript
/* 7.0 only */
pango-gtkbeta-devel pango-gtkbeta
XFree86 Mesa
compat-glibc db2
compat-glibc db1
pam initscripts
kernel initscripts
initscripts sysklogd
/* 6.2 */
egcs-c++ libstdc++
/* 6.1 */
pilot-link-devel pilot-link
/* 5.2 */
pam pamconfig
</pre></div>
<p>
Why are there new loops? Because tsort is trying to use all of the dependency relations for ordering, while the previous tsort ignored all Requires: from added packages.
<p>
Except for the "well known" libtermcap <-> bash loop (which is just wrong), all of the other dependencies are simply not needed in an upgrade context to perform package ordering. Please note that all of the known to cause loop dependencies listed above are, for now, explicitly ignored when determining package install ordering.
<p>
<h3><a name="tsort_summary">Summary</a>
</h3>
<p>
So what does this all mean? Basically not much, unless you find yourself trying to specify dependencies amongst a set of packages correctly and happen to create a dependency loop.
<p>
And, before you start adding the new-fangled syntax to packages, please remember that rpm will almost certainly be auto-generating fine-grained dependencies for post et al scriptlets pretty soon. Truly, rpm needs to make packaging easier, not provide Yet More Complicated Syntax in spec files.
<p>
With thanks to Ken Estes for doing the implementation in bash2 that makes it possible to auto-generate scriptlet dependencies, blame me for the long, slow deployment.
<p>
<hr><address style="align: right;"><small>Generated on Thu Sep 12 22:15:12 2002 for rpm by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0
width=110 height=53></a>1.2.17 </small></address>
</body>
</html>
