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 types of changes made to the packages:

The status of the ongoing work is tracked here:

Source package

VCS: build

VCS: control

Bug: build

Bug: control

Depends on

autogen

texlive

avahi

734669 (wookey)

libqt4-dev, libgtk2.0-dev, libgtk-3-dev, python-dbus, libdaemon-dev, python-gtk2

bluez

libgstreamer-plugins-base0.10-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

Git

Git

749344

749470

dh-autoreconf, texlive-fonts-recommended, texlive-latex-base

gconf

libgtk-3-dev

gdb

texlive-base

gobject-introspection

python-mako

gpm

texlive-base

graphite2

cmake

gst-plugins-base0.10

libgtk-3-dev, libtheora-dev

gtk+3.0

gnome-icon-theme-symbolic

highlight

libboost-dev

ijs

ghostscript, docbook-utils

java-atk-wrapper

default-jdk

krb5

Git

Git

libldap2-dev

libav

libopencv-dev, frei0r-plugins-dev

libcanberra

libpulse-dev

libdrm

valgrind

libfontenc

xfonts-utils

libidn

738147 (dschepler)

gcj-jdk

libproxy

libwebkitgtk-3.0-dev, libjavascriptcoregtk-3.0-dev, network-manager-dev, kdelibs5-dev

libtasn1-6

texlive-latex-base

libxcb

python, python-xcbgen

libxslt

python-all-dev, python-all-dbg

libxt

libglib2.0-dev

llvm-toolchain-3.4

python-sphinx

mariadb-5.5

cmake

mpdecimal

python-sphinx

openjpeg

default-jdk

openldap

724518 (dschepler)

heimdal-dev

opensp

openjade1.3, docbook-dsssl, poppler-utils, jadetex

phonon-backend-gstreamer

libphonon-dev

php5

libgd-dev

pkg-config

libglib2.0-dev

pulseaudio

libjack-jackd2-dev

python-defaults

lsb-release, python-docutils

python-numpy

cython

python-qt4

libphonon-dev

python2.7

738520 (partially)

python, lsb-release, libbluetooth-dev, xvfb

python3-defaults

python3-minimal, python3.4-minimal, python3-docutils

python3.3

libbluetooth-dev, python3

python3.4

libbluetooth-dev

qdbm

default-jdk

qtchooser

libqt4-dev

shared-mime-info

docbook-utils

swig2.0

dh-autoreconf, php5-cgi, default-jdk, php5-dev

vala-0.14

valac

w3m

738208 (dschepler)

libimlib2-dev

x264

735742 (report only)

libffms2-dev, libgpac-dev, libavformat-dev

xutils-dev

cpp-4.7

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
=============
...