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:

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

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

Git

Git

758461

758462

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

texlive-fonts-recommended, texlive-latex-base

freetype

Git

Git

752270

752271

libx11-dev, x11proto-core-dev

gconf

libgtk-3-dev

gpm

Git

-

749616

-

texlive-base (dropped unconditionally, not used at all)

graphite2

cmake

gtk+3.0

gnome-icon-theme-symbolic

highlight

Git

Git

758418

758420

swig

ijs

Git

-

752159 (B-D-I)

-

ghostscript, docbook-utils

jack-audio-connection-kit

libffado-dev

jackd2

libffado-dev

java-atk-wrapper

default-jdk

krb5

Git

Git

752407

752409

libldap2-dev

libav

libopencv-dev, frei0r-plugins-dev

libdrm

valgrind

libfontenc (rather, xfonts-utils)

Git

Git

717843

752235

Make xfonts-utils only build font-util in stage1

libidn

738147 (dschepler)

gcj-jdk

libproxy

Git

Git

758466

758467

libwebkitgtk-3.0-dev, libjavascriptcoregtk-3.0-dev, kdelibs5-dev

libraw1394

Git

Git

749989

749990

docbook-utils, docbook-xml (only used with docbook-utils)

libtasn1-6

Git

Git

749854

749855

texlive-latex-base

libtheora

Git (drop)

-

751702 (drop)

-

graphviz

libvpx

Git

-

726485 (B-D-I)

-

php5-cli

llvm-toolchain-3.4

python-sphinx

lynx-cur

openssh-client

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

Git

Git

751899

751922

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

Git

-

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

Git

Git

735742 (sent a patch)

752103

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