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 <[email protected]> Aan: [email protected], [email protected] CC: Jeff Johnson <[email protected]> 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. -------------------------------------------------------
