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:
Source package |
VCS: build |
VCS: control |
Bug: build |
Bug: control |
Depends on |
autogen |
Git (B-D-I) |
- |
751470 (B-D-I) |
- |
texlive |
avahi |
|
|
734669 (wookey) |
|
libqt4-dev, libgtk2.0-dev, libgtk-3-dev, python-gtk2 |
bluez |
|
|
|
|
libgstreamer-plugins-base0.10-dev |
boost-defaults |
|
|
|
|
libboost1.55-dev |
boost1.55 |
|
|
|
|
mpi-default-dev |
colord |
|
|
|
|
docbook-utils, libsane-dev |
cups |
|
|
|
|
ghostscript, libcupsfilters-dev, poppler-utils, cups-filters |
cups-filters |
|
|
|
|
ghostscript, libcupsimage2-dev |
cyrus-sasl2 |
libldap2-dev, libmysqlclient-dev, libpq-dev, heimdal-multidev |
||||
doxygen |
|
|
738263 (dschepler) |
738263 (dschepler) |
libqt4-dev |
ecj |
|
|
|
|
gcj-4.9-jdk |
flex |
texlive-fonts-recommended, texlive-latex-base |
||||
freetype |
libx11-dev, x11proto-core-dev |
||||
gconf |
|
|
|
|
libgtk-3-dev |
gnome-pkg-tools |
|
|
|
|
|
gpm |
- |
- |
texlive-base (dropped unconditionally, not used at all) |
||
graphite2 |
|
|
|
|
cmake |
gtk+3.0 |
|
|
|
|
gnome-icon-theme-symbolic |
highlight |
swig |
||||
ijs |
- |
752159 (B-D-I) |
- |
ghostscript, docbook-utils |
|
jack-audio-connection-kit |
|
|
|
|
libffado-dev |
jackd2 |
|
|
|
|
libffado-dev |
java-atk-wrapper |
|
|
|
|
default-jdk |
krb5 |
libldap2-dev |
||||
libav |
|
|
|
|
libopencv-dev, frei0r-plugins-dev |
libdrm |
|
|
|
|
valgrind |
libfontenc (rather, xfonts-utils) |
Make xfonts-utils only build font-util in stage1 |
||||
libidn |
|
|
738147 (dschepler) |
|
gcj-jdk |
libproxy |
libwebkitgtk-3.0-dev, libjavascriptcoregtk-3.0-dev, kdelibs5-dev |
||||
libraw1394 |
docbook-utils, docbook-xml (only used with docbook-utils) |
||||
libtasn1-6 |
texlive-latex-base |
||||
libtheora |
Git (drop) |
- |
751702 (drop) |
- |
graphviz |
libvpx |
- |
726485 (B-D-I) |
- |
php5-cli |
|
llvm-toolchain-3.4 |
|
|
|
|
python-sphinx |
lynx-cur |
|
|
|
|
openssh-client |
matplotlib |
|
|
basemap |
||
mpdecimal |
Git (B-D-I) |
- |
751861 (B-D-I) |
- |
python3-sphinx, python-sphinx |
network-manager |
|
|
|
|
libsoup2.4-dev |
openjdk-7 |
|
|
|
|
metacity |
openldap |
|
|
724518 (dschepler) |
|
heimdal-dev |
opensp |
|
|
|
|
openjade1.3, docbook-dsssl, poppler-utils, jadetex |
phonon-backend-gstreamer |
|
|
|
|
libphonon-dev |
pkg-config |
libglib2.0-dev |
||||
poppler |
Git (not submitted yet) |
Git (not submitted yet) |
738338 (dschepler) |
|
qtbase5-dev |
ppl |
|
|
|
|
swi-prolog |
pygobject |
|
|
|
|
gir1.2-gtk-3.0 |
python-defaults |
Git (B-D-I) |
- |
751706 (B-D-I) |
- |
lsb-release, python-docutils |
python-numpy |
|
|
|
|
cython |
python2.7 |
|
|
738520 (partially) |
|
python, tk-dev, lsb-release, libbluetooth-dev, xauth, xvfb, blt-dev |
python3-defaults |
|
|
|
|
python3-minimal, python3-docutils |
python3.3 |
|
|
|
|
libbluetooth-dev, python3 |
python3.4 |
|
|
|
|
libbluetooth-dev, python3 |
qt4-x11 |
|
|
|
|
libmariadbclient-dev, libgstreamer-plugins-base0.10-dev |
qtchooser |
|
|
|
|
libqt4-dev |
shared-mime-info |
- |
758421 (B-D-I) |
- |
docbook-utils, docbook-utils-xml |
|
swig2.0 |
|
|
|
|
dh-autoreconf, php5-cgi, default-jdk, php5-dev |
tiff |
|
|
|
|
freeglut3-dev |
vala-0.14 |
|
|
|
|
valac |
w3m |
|
|
738208 (dschepler) |
|
libimlib2-dev |
x264 |
735742 (sent a patch) |
libffms2-dev, libgpac-dev, libavformat-dev |
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 ============= ...