Wiki

• FrontPage
• RecentChanges
• FindPage
• HelpContents
• CircularBuildDependencies

Details of Build-dependency loops and how to analyse them

Finding build-dependency loops in packages is about looking for the strongly-connected set in a set of build-dependencies. If it is not empty then there are loops.

This analysis was done by adding functionality to xdeb to output dot syxtax graph output instead of it's normal textual human-debug info. The code has been in xdeb since end-2010. Check for the --generate-graph option.

Having done a run, you need to post-process the results to get nice graphs. The scripts and info to do that is in xdeb as examples. See /usr/share/doc/xdeb/examples/README.txt for info

To use these tools you need xdeb and graphviz installed.

Use them like this:

mkdir cyclicdeps
cd cyclicdeps
cp /usr/share/doc/xdeb/examples/graphutils/* .
./findcycles <package>

You should get a results directory containing both <packagename>.cycle and <packagename>.ps files for any package that contains a build-loop.

There are some limitations due to the way xdeb interprets Build-dependencies, but it's pretty good.

Analysing a distro

To run the above analysis on a distro you need to make a file listing all the packages of interest then fun findcycles over them. This can be done with:

To get list of essential packages: grep-aptavail -Fessential yes -s Source:Package | awk '{ print $2 }' | uniq

to get all available source packages: grep-aptavail -S  -r .\* -s Source:Package | awk '{ print $2 }' | uniq

then use a noddy script (listofcycles):

if [ ! -n "$1" ]; then
echo "Specify a file listing packages"
  exit 1
fi

if [ -e "$1" ]; then
  for package in `cat $1`
  do
    ./findcycles $package
  done
fi

So

grep-aptavail -Fessential yes -s Source:Package | awk '{ print $2 }' | uniq > essentialpkgs
listofcycles essentialpkgs

would analyse all the essential packages. You could do something clever with xargs if you don;t want to keep the package list for reference.

Examples of build-dep loops

Examples of output from this process (slightly older version of script)

Kerberos/ldap loop: krb5.ps

Cups+everything loop: cups.ps

This is a build-loop graph for openldap, which shows a loop that affects many packages (such as apache2, mozilla, and of course the involved packages).

Circles are source packages. Boxes are binary packages listed as build-deps and the diamond is the package that was given to xdeb to generate the initial dependency graph. The weights shown are the number of build-dependencies on other packages. The brightest green are the packages with the smallest number of such dependencies, indicating the likely easiest places to break the loops (because work is only needed in the one package and dependency).

An expanded version shows the binary-packages involved in each build dependency.

Size of the problem

There are about 20 loops which come up over and over again in Debian Squeeze and Ubuntu Natty. More recent analysis has not been run, but these things only change slowly (generally for the worse).

Whilst there are a lot of loops, they tend to involve the same packages over and over again, so our initial estimate is that less than 50 packages will need significant work for dependency-cycle breaking. Many more than that need cross-building work.

The Feedback Arc Set

As part of Google Summer of Code 2014, the Bootstrappable Debian project aims to eliminate as many of the loops in the Feedback Arc Set as possible.

There are two main goals in this project:

• Modify some packages so that they may be built in some limited way ("nocheck", binary-only, or build profiles like "stage1") without some of their usual build dependencies - not generating documentation, not running tests, not building some of the binary packages.

• In the process of modifications, make any changes (some files not regenerated, others not built at all) with binary package level granularity. This means that if a binary package is built at all during a limited build, then it must have the same contents as the same binary package resulting from a full build; explained better at the Profile-built binary packages page.

There are two types of changes made to the packages:

• modifying the debian/rules file to drop support for some features when building in the "stage1" build profile (i.e. if the word "stage1" is in the DEB_BUILD_PROFILES variable); these changes may be added to the packages right now without any impact on the buildd infrastructure

• modifying the debian/control file to drop some of the build dependencies in the "stage1" build profile (i.e. add a <!profile.stage1> condition to the build dependency); these changes will be filed as separate bugs blocked by 744246, since currently the Debian archive infrastructure does not support <!profile.*> restrictions

The status of the ongoing work is tracked here:

Raw notes on observed loops in Debian and Ubuntu

Updated March 2011.

Fixing krb5 loop.

Involved packages:
gamin
glib2.0

This is old. Should remove itself. Gone in natty.

consolekit
policykit-1

This is gone in natty. May be a false positive anyway? Checking...

stylebook
libxerces2-java

Not sure if this is real. divide by zero error in natty.

----------------

jakarta-log4j
libmx4j-java

-----------------
network-manager
gnome-panel

-------------------
libdb-mysql-perl
mysql-5.1

------------------
lapack
atlas

-----------------

gettext
libcroco
glib2.0

------------------
krb5
openldap
cyrus-sasl2
postgresql-8.4
(and heimdal)

build krb5 (and heimdal) without ldap support? (so libldap2-dev not
needed)

---------------------
gmp
gcc-4.5 or gcc-4.4
cloog-ppl

gmp builds lib32gmpxx4 which depends on lib32stdc++6
skip lib32gmpxx4 (i.e the multilib builds) and that should fix the
whole loop. probably fixes the autogen loop below too.
xdeb thinks this loops counts because it is thinking about
cross-compiling - it's not a loop in native arm builds?

autogen
guile
<gmp>

--------------

webkit
libsoup2.4
libproxy

---------------------
poppler
qt4-x11
qt-assistant-compat
qtwebkit-source
gtk+2.0
cups
phonon
xine-lib
imagemagick
ffmpeg
pulseaudio
gnome-vfs
samba
avahi
bluez
gconf
alsa-plugins
libsdl1.2
libtheora
gst-plugins-base0
libwmf
libgsf
libsvg
djvulibre
qt-x11-free
libodbc2

build poppler without glade and without qt4

------------------------
ant
<stylebook>
<ecj>
<jakarta-log4j>
tomcat6
axis
11 java library packages

use native ant - does that fix it all?


lvm loop

lvm2 can be build without redhat cluster support

--------------------------
[tk8.4]
libxt
libsm
util-linux
libselinux
ruby1.8

build without ruby stuff?

--------------------

stuff that has to be native supplied:
dpkg, flex, ant
stuff that has to be cross-built:


Ubuntu maverick
===============

gamin <-> glib2.0
gmp -> gcc-4.5 -> mpfr4 -> gmp (inc mpclib, ppl, cloog-ppl)
op
krb5 -> openldap -> krb5 (inc cyrus-sasl2, postgresql-8.4)
poppler -> qt4-x11 -> gtk+2.0 -> cups -> poppler (inc phonon,
xine-lib, imagemagick, ffmpeg, pulseaudio, gnomevfs, samba, avahi + 10
more) normally 26 packages.


ant -> <stuff> (20 packages)
autogen -> guile -> gmp -> autogen (inc gmploop)
webkit -> libsoup2.4 -> libproxy ->webkit [brasero]
lvm2 -> redhat-cluster -> libvirt -> parted ->lvm2  [cryptsetup]
consolekit <-> policykit-1
ecj <-> gcj-4.4 [bsh]
jakarta-log4j -> libmx4j-java -> jakarta-log4j [c3p0, excalibur]
cdebconf -> gtk2loop/ krb5loop [cdebconf]
stylebook -> libxerces2-java -> stylebook [dom4j]
[doxygen] has a _huge_ loop.
libffi
network-manager <-> gnome-panel [empathy]
ghostscript is biggest yet!
libdb-mysql-perl <-> mysql-5.1
lapack <-> atlas
libxt -> libsm -> util-linux -> libselinux -> ruby1.8 -> tk8.4 -> libxt
libcroco -> glib2.0 -> gettext [gettext]


Ubuntu natty
============

krb5 and poppler loops now tied into one mess


Debian squeeze
==============

lapack <-> atlas
krb5...
poppler...
gamin<->glib2.0
webkit...

Debian Wheezy
=============
...