1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<TITLE> [Mageia-dev] Fwd: [Cooker] WANTED: the cyclic dependency Hell (aka Automated Bootstrapping)
</TITLE>
<LINK REL="Index" HREF="index.html" >
<LINK REL="made" HREF="mailto:mageia-dev%40mageia.org?Subject=Re%3A%20%5BMageia-dev%5D%20Fwd%3A%20%5BCooker%5D%20WANTED%3A%20the%20cyclic%20dependency%20Hell%20%28aka%0A%09Automated%20Bootstrapping%29&In-Reply-To=%3C201110171157.56827.alien%40rmail.be%3E">
<META NAME="robots" CONTENT="index,nofollow">
<META http-equiv="Content-Type" content="text/html; charset=us-ascii">
<LINK REL="Previous" HREF="008919.html">
<LINK REL="Next" HREF="008938.html">
</HEAD>
<BODY BGCOLOR="#ffffff">
<H1>[Mageia-dev] Fwd: [Cooker] WANTED: the cyclic dependency Hell (aka Automated Bootstrapping)</H1>
<B>Maarten Vanraes</B>
<A HREF="mailto:mageia-dev%40mageia.org?Subject=Re%3A%20%5BMageia-dev%5D%20Fwd%3A%20%5BCooker%5D%20WANTED%3A%20the%20cyclic%20dependency%20Hell%20%28aka%0A%09Automated%20Bootstrapping%29&In-Reply-To=%3C201110171157.56827.alien%40rmail.be%3E"
TITLE="[Mageia-dev] Fwd: [Cooker] WANTED: the cyclic dependency Hell (aka Automated Bootstrapping)">alien at rmail.be
</A><BR>
<I>Mon Oct 17 11:57:56 CEST 2011</I>
<P><UL>
<LI>Previous message: <A HREF="008919.html">[Mageia-dev] Latest Evolution update on Cauldron - error with Google Calendar
</A></li>
<LI>Next message: <A HREF="008938.html">[Mageia-dev] [packages-commits] [155802] Update to fix crash #1816
</A></li>
<LI> <B>Messages sorted by:</B>
<a href="date.html#8931">[ date ]</a>
<a href="thread.html#8931">[ thread ]</a>
<a href="subject.html#8931">[ subject ]</a>
<a href="author.html#8931">[ author ]</a>
</LI>
</UL>
<HR>
<!--beginarticle-->
<PRE>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 <<A HREF="https://www.mageia.org/mailman/listinfo/mageia-dev">franck.bui at mandriva.com</A>>
Aan: <A HREF="https://www.mageia.org/mailman/listinfo/mageia-dev">maintainers at mandriva.com</A>, <A HREF="https://www.mageia.org/mailman/listinfo/mageia-dev">cooker at mandrivalinux.org</A>
CC: Jeff Johnson <<A HREF="https://www.mageia.org/mailman/listinfo/mageia-dev">n3npq at mac.com</A>>
Hi Folks,
,----[ Preface ]
|<i> This is boring material simply because its main purpose is overall
</I>|<i> quality improvement. But please keep on reading and contribute ! :)
</I>`----
,----[ Disclaimer ]
|<i> I'm far from being an expert packager, actually it's quite the
</I>|<i> opposite, so I'm probably saying a lot of obvious things, sorry again
</I>|<i> for being boring.
</I>`----
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: [<A HREF="https://github.com/fbuihuu/digraph">https://github.com/fbuihuu/digraph</A>].
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:
[<A HREF="http://mes5devel.mandriva.com/~fbui/graph/graph1.pdf">http://mes5devel.mandriva.com/~fbui/graph/graph1.pdf</A>]
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:
[<A HREF="http://mes5devel.mandriva.com/~fbui/graph/graph2.pdf">http://mes5devel.mandriva.com/~fbui/graph/graph2.pdf</A>]
Or you can get a compact view to represent each group by a single
node:
[<A HREF="http://mes5devel.mandriva.com/~fbui/graph/graph3.pdf">http://mes5devel.mandriva.com/~fbui/graph/graph3.pdf</A>]
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:
[<A HREF="http://mes5devel.mandriva.com/~fbui/graph/dump-rpmdeps.py">http://mes5devel.mandriva.com/~fbui/graph/dump-rpmdeps.py</A>]
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:
[<A HREF="http://mes5devel.mandriva.com/~fbui/graph/cooker-inconsistencies.log">http://mes5devel.mandriva.com/~fbui/graph/cooker-inconsistencies.log</A>]
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:
[<A HREF="http://mes5devel.mandriva.com/~fbui/graph/">http://mes5devel.mandriva.com/~fbui/graph/</A>]
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.
-------------------------------------------------------
</PRE>
<!--endarticle-->
<HR>
<P><UL>
<!--threads-->
<LI>Previous message: <A HREF="008919.html">[Mageia-dev] Latest Evolution update on Cauldron - error with Google Calendar
</A></li>
<LI>Next message: <A HREF="008938.html">[Mageia-dev] [packages-commits] [155802] Update to fix crash #1816
</A></li>
<LI> <B>Messages sorted by:</B>
<a href="date.html#8931">[ date ]</a>
<a href="thread.html#8931">[ thread ]</a>
<a href="subject.html#8931">[ subject ]</a>
<a href="author.html#8931">[ author ]</a>
</LI>
</UL>
<hr>
<a href="https://www.mageia.org/mailman/listinfo/mageia-dev">More information about the Mageia-dev
mailing list</a><br>
</body></html>
|
