[Mageia-dev] Fwd: [Cooker] WANTED: the cyclic dependency Hell (aka Automated Bootstrapping)
Maarten Vanraes
alien at rmail.be
Mon Oct 17 11:57:56 CEST 2011
Did anyone see this? this sounds very interesting imho...
---------- Doorgestuurd bericht ----------
Onderwerp: [Cooker] WANTED: the cyclic dependency Hell (aka Automated
Bootstrapping)
Datum: maandag 17 oktober 2011, 11:32:08
Van: Franck Bui <franck.bui at mandriva.com>
Aan: maintainers at mandriva.com, cooker at mandrivalinux.org
CC: Jeff Johnson <n3npq at mac.com>
Hi Folks,
,----[ Preface ]
| This is boring material simply because its main purpose is overall
| quality improvement. But please keep on reading and contribute ! :)
`----
,----[ Disclaimer ]
| I'm far from being an expert packager, actually it's quite the
| opposite, so I'm probably saying a lot of obvious things, sorry again
| for being boring.
`----
Table of Contents
=================
1 Bootstrapping
2 Cyclic dependencies
2.1 Reasons
3 "Digraph" tool
3.1 Goals
3.2 Examples
4 "Digraph" application to Cooker main/release media
4.1 First inconsistencies
4.1.1 Example 1
4.1.2 Example 2
4.1.3 Example 3
4.2 Get all of them
4.3 Results
5 Conclusion
1 Bootstrapping
~~~~~~~~~~~~~~~~
Bootstrapping cooker into a new architecture (or even into the same arch
but with a new but incompatible ABI) is currently a pain and takes an
insane amount of time (ask to pcpa for gory details :).
First, what's a bootstrap ? It's the different steps/stages taken to
rebuild all packages into a new ABI using a) some packages built for
the old ABI (mostly the toolchain for cross compiling a very small set
of programs to create a basic native rootfs) b) the package sources
which are going to be build natively.
Having an automated bootstrapping not only means less pain to switch to
a new ABI but it also means that the distro is in a good shape since the
bootstrap requires a consistent repository, no more cyclic dependence
between packages, etc...
Eventually having an automated bootstrapping means that the process is a
repeatable and deterministic one. Since this process is pretty sensible
to the coherency state of the distro, it could be run regularly to catch
any new regressions.
How are packages being built during the bootstrapping ?
Let say that we want to build 'A' package. 'A' has a build-require on
'B' which in its turn has a build-require on 'C': A -> B -> C
To build/install 'A.rpm', we should:
- see if 'C.rpm' is already installed. If so then go to the next item
otherwise we have to build/install 'C.rpm' first (from C.src.rpm).
- Same as previous item but with 'B.rpm'.
- Finally build and install 'A.rpm'.
Note: that both the build and the install steps have their own deps.
You may think it's not that different from what's happening when you
submit a package to the build-system. But it is simply because we start
with an _empty_ rpm database. This means that when a build requirement
is missing, rpm likely won't find the BR's binary package installed.
Therefore the build-require will be considered for a build in its turn
and so on.
2 Cyclic dependencies
~~~~~~~~~~~~~~~~~~~~~~
At this point you probably guess why the automated bootstrapping is
currently not possible: the reason is: "cyclic dependencies".
How are they created ?
2.1 Reasons
============
Here are the main reasons I could see:
1/ Each package has build requirements specific to the generation of
the documentation that the package ships amongst the binaries.
Unfortunately tools used to generate documentation such as doxygen,
tex... are pretty 'high-level' tools and they require themself a
lot of other packages (having their own docs) to be built first.
2/ Some packages provides a main functionality with light
requirements but also some additional/minor functionalities
(sometimes not use at all) with some strong requirements. Such
packages may be considered for being splitted. You can take a look
to libidn package for an example.
3/ Some packages 'pull' a huge build dependency just for building a
useless module/example-code. For example, 'libalsa2' has a
buildrequires on python-devel simply in order to build a (useless)
python module example which won't be used at all.
By far, the more problematic item is 1/. The reason is that it's
currently not possible to disable easily the doc generation hence
removing the associated requirements. Most of the packages are
affected.
Item 2/ and 3/ are less important IMO because they depend on
packager's taste only. Moreover there should be many less packages
following into these 2 categories.
Therefore I think we should first focus on 1/. I'll try to come up
with a simple/naive proposition in a next post mostly in order to
initiate a reflexion on this subject.
3 "Digraph" tool
~~~~~~~~~~~~~~~~~
Back to the cycle dependencies.
As you know, all package relations can be represented by a directed
graph. I wrote a basic tool which can be used to operate on directed
graph: [https://github.com/fbuihuu/digraph].
3.1 Goals
==========
The tool is in a very early stage and probably will stay as it is. But
it can be used to:
- find all cycles in a graph.
- group each cycle into a single node making the resulting graph
(called condensation graph) acyclic.
- do a topological sort on an acyclic graph. This means that the tool
is able to tell you the order of the packages to be built.
- visualize graph with the help of graphviz.
You simply need to describe the graph first in a text file. For an
example, have a look to graph.txt, the syntax used is obvious.
3.2 Examples
=============
This file gives an example of a graph description that can be visualized
here:
[http://mes5devel.mandriva.com/~fbui/graph/graph1.pdf]
Once your graph description is ready you can feed the tool with it:
$ ./digraph.py graph.txt
Connected components:
--------------------
* Group(c - 2): c, d
* Group(g - 2): g, f
* Group(y - 2): y, x
* Group(a - 3): a, b, e
The tool by default shows you the cyclic groups (aka "strongly connected
components").
If you want other information then you'll need to hack the current
script but it's quite trivial to do so. See main() for a couple of
examples.
For example, you can create the condensation of the previous graph and
ask it to plot it. Here's the result:
[http://mes5devel.mandriva.com/~fbui/graph/graph2.pdf]
Or you can get a compact view to represent each group by a single
node:
[http://mes5devel.mandriva.com/~fbui/graph/graph3.pdf]
Eventually you can ask to the tool to do a topological sort of the
nodes. Here's the result:
Topological order:
-----------------
h -> j -> Group(g - 2) -> Group(c - 2) -> Group(a - 3) -> i -> Group(y - 2)
4 "Digraph" application to Cooker main/release media
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As you probably guess, the purpose of this script is mainly for its
application to the distro.
The fist step is to generate a description of the packages relationship
in cooker. The following script exactly do that:
[http://mes5devel.mandriva.com/~fbui/graph/dump-rpmdeps.py]
How ? It simply parses a set of .rpm files, extracts some info such as
the "requires:" and "provides:" tags and retrieve the src.rpm used to
generate the .rpm. From the source package it extracts the
"buildrequires:" tags. With those information, it dumps the dependencies
into a description format used by "digraph" tool.
BTW, if someone can figure out a faster method for achieving this, I'm
listening :). It's currently slow mainly because it uses "urpmq
--sourcerpm <rpm>" to extract the source package filename. If someone
can figure out another mean with rpm(8) to do that...
4.1 First inconsistencies
==========================
Running "dump-rpmdeps.py" script shows the first repository's
inconsistencies. Following are some examples:
4.1.1 Example 1
----------------
Warning: source not found:
/mnt/BIG/devel/cooker/SRPMS/main/release/ant-1.8.2-4.src.rpm (referenced by
ant-commons-logging)
In this case, the name of the source rpm is not exact since the file in
the SRPMS directory that can be found is "ant-1.8.2-4.1.src.rpm".
4.1.2 Example 2
----------------
Warning: unknown alias 'sepol-static-devel' used by 'libselinux'
In this case 'libselinux' refers to 'sepol-static-devel' package which
doesn't seem to exist, at least in the main/release media.
4.1.3 Example 3
----------------
Warning: unknown alias 'geronimo-jta-1.0.1B-api' used by 'jakarta-commons-
transaction'
'jakarta-commons-transaction' (in main/release) has a buildrquires on
'geronimo-jta-1.0.1B-api', which is in contrib media.
4.2 Get all of them
====================
For a full list of such inconsistencies, please see:
[http://mes5devel.mandriva.com/~fbui/graph/cooker-inconsistencies.log]
4.3 Results
============
This description can now be used it with "digraph" to see if there're
some cycles and if so what they look like:
$ ./digraph.py cooker-i586-dependencies.txt
Connected components:
--------------------
* Group(asm2 - 2): asm2, objectweb-anttask
* Group(python-sphinx - 2): python-sphinx, python-nose
* Group(nant - 2): log4net, nant
* Group(gnome-js-common - 2): gnome-js-common, seed
* Group(vcdimager - 3): vcdimager, libcdio, libcddb
* Group(perl-Moose - 5): perl-Moose, perl-Test-Warn, perl-Array-Compare,
perl-Package-DeprecationManager, perl-Package-Stash
* Group(ant - 461): flac, drakx-kbd-mouse-x11, xcb-util, gd, recode, gdbm,
poppler, strigi, libxp, libsndfile, ...
So "only" 7 cycles, BUT the last one involves 461 packages ! And the
reason is mainly "documentation generation".
You can visualize those cycles, except the last one, by looking at the
cyclic-*.pdf files at:
[http://mes5devel.mandriva.com/~fbui/graph/]
5 Conclusion
~~~~~~~~~~~~~
Please help to nuke this crazy dependency hell !
The most important task IMHO is the need to find out how the
documentation generation can be separated/disabled properly.
Note that disabling generation of documentation is not only
interesting for automated bootstrapping but also for architectures
(such as ARM) which targets embedded devices with limited disk
spaces.
Also if the first inconsistencies found by the dumb tool are revelant,
we want develop more sanity checkers and run them regularly to trap
any new regressions introduced later.
-------------------------------------------------------
More information about the Mageia-dev
mailing list