circular dependencies.. possible fix
Hello,
I'm not sure this is the right place to send something like this
but I'll try it anyway.
I experienced a very ugly dpkg behaviour when trying to install
cmucl and cmucl-small. There seems to be an apropriate bug filed
already so I did not do anything in that direction. As there was
no fix available anyware I decided to look into it on my own and
it seems to have worked out quite well.
When dpkg tries to configure cmucl it notices a missing dependency
to cmucl-small (well actually it's lisp-core) and gets delayed.
Next dpkg attempts to install cmucl-small but notices the dependency
to cmucl. Normally this would either result in an endless loop or
a fatal, non-descriptive error through assert().
In my approach I utilize a simple table with information on the
dependency between packages. The table would look like the following
at run-time for the above example:
cmucl -> cmucl-small
cmucl-small -> cmucl
At installation time dpkg now checks every delayed, newly installed
package wether it fits together to an endless dependency loop.
That's what checkfor_dependency_loop() does. The code talks by it's
self, I hope.
The de-installation part seems a bit more unclear to me and I can
not guarantee that it actually works under all circumstances as I
am not sure where to place the apropriate checkfor_dependency_loop()
call. It seems to work for me at the moment, but maybe I broke
something at the same time. Could someone with more insight to the
dpkg functionality please take a look?
At the moment, the loop detection function will make the active
queue package pretend to have all dependencies fullfilled as soon
as a loop is deteced. This can easily replaced with something else
if it seems too risky, but I do not see a real alternative. All
dependencies can not be satisfied in such a case so a bit unsafe
behaviour is always necessary. Well.. of course we could always
turn it into a fatal error but that woul not gain us much
compaired to the situation at the moment.
Ok, that's all for now. I hope it's useful in one way or the other.
I would be happy to comment on the code in more detail if needed.
btw.: the patch should be applied to dpkg-1.4.1.3/main/packages.c
(No other files were changed).
Greetings,
--
Fabian Knittel | fknittel@gmx.de
--- packages_orig.c Sun Jun 13 03:27:43 1999
+++ packages.c Sun Jun 13 05:55:13 1999
@@ -45,10 +45,25 @@
struct pkginfo *pkg;
};
+struct loop_table {
+ struct loop_table *next;
+ struct pkginfo *pkg;
+ struct pkginfo *depends;
+};
+
+static struct loop_table *deps_loop_table = 0;
static struct pkginqueue *queuehead= 0, **queuetail= &queuehead;
int queuelen=0, sincenothing=0, dependtry=0;
+
+static int match_dependency(struct dependency *dep, struct pkginfo *pkg, int *matched, int *interestingwarnings, struct varbuf *oemsgs, struct pkginfo *removing);
+static void add_loop_entry(struct pkginfo *pkg, struct pkginfo *depends);
+static void del_loop_entry(struct pkginfo *pkg, struct pkginfo *depends);
+static int is_dep_loop(struct pkginfo *possdependee, struct pkginfo *requiredby);
+static int checkfor_dependency_loop(struct pkginfo *possdependee, struct pkginfo *requiredby);
+
+
void add_to_queue(struct pkginfo *pkg) {
struct pkginqueue *newent;
@@ -104,10 +119,10 @@
iterpkgend(it);
} else {
-
+
if (!*argv)
badusage(_("--%s needs at least one package name argument"), cipaction->olong);
-
+
while ((thisarg= *argv++) != 0) {
pkg= findpackage(thisarg);
if (pkg->status == stat_notinstalled) {
@@ -159,7 +174,7 @@
internerr("unknown action in duplicate");
}
rundown->pkg= 0;
- } else {
+ } else {
rundown->pkg->clientdata->istobe= istobe;
}
}
@@ -206,7 +221,7 @@
set_error_display(0,0);
error_unwind(ehflag_normaltidy);
}
-}
+}
/*** dependency processing - common to --configure and --remove ***/
@@ -245,6 +260,93 @@
* and breaking.
*/
+
+static void add_loop_entry(struct pkginfo *pkg, struct pkginfo *depends)
+{
+ struct loop_table *t = deps_loop_table, *newt, *ot = 0;
+
+ /* Search for duplicate entry and the end of the list */
+ while (t) {
+ if ((t->pkg == pkg) && (t->depends == depends))
+ return; /* found duplicate */
+ ot = t;
+ t = t->next;
+ }
+
+ newt = m_malloc(sizeof(struct loop_table));
+ newt->pkg = pkg;
+ newt->depends = depends;
+ newt->next = 0;
+ if (ot)
+ ot->next = newt;
+ else
+ deps_loop_table = newt;
+}
+
+static void del_loop_entry(struct pkginfo *pkg, struct pkginfo *depends)
+{
+ struct loop_table *t = deps_loop_table, *ot = 0;
+
+ while (t) {
+ if ((t->pkg == pkg) && (t->depends == depends)) {
+ if (ot)
+ ot->next = t->next;
+ else
+ deps_loop_table = t->next;
+ free(t);
+
+ return;
+ }
+
+ ot = t;
+ t = t->next;
+ }
+}
+
+
+
+/* find loops in the dependency list */
+static int is_dep_loop(struct pkginfo *possdependee, struct pkginfo *requiredby)
+{
+ struct loop_table *t = deps_loop_table;
+
+ while (t) {
+ if (t->pkg == possdependee) {
+ /* Either we find the dependency loop */
+ if ((t->depends == requiredby)
+ /* or we keep on searching */
+ || is_dep_loop(t->depends, requiredby))
+ return 1;
+ }
+ /* try it in every element */
+ t = t->next;
+ }
+
+ return 0;
+}
+
+
+/*
+ * Tries to detect dependency loops by going through the dependencies
+ * and looking for recurrent dependency patterns.
+ *
+ * If a loop is detected we will return 3 to break out of the loop
+ * and continue the processing although not all dependencies can be
+ * maintained, i.e. we just *hope* that no package will break in the
+ * dependency ring.
+ */
+static int checkfor_dependency_loop(struct pkginfo *possdependee,
+ struct pkginfo *requiredby)
+{
+ if (is_dep_loop(possdependee, requiredby)) {
+ fprintf(stderr, "dpkg: warning: detected dependancy loop - attemping to break through\n");
+ return 3;
+ }
+
+ add_loop_entry(possdependee, requiredby);
+ return 1;
+}
+
static int deppossi_ok_found(struct pkginfo *possdependee,
struct pkginfo *requiredby,
struct pkginfo *removing,
@@ -257,6 +359,7 @@
if (ignore_depends(possdependee)) {
debug(dbg_depcondetail," ignoring depended package so ok and found");
+ del_loop_entry(requiredby, possdependee);
return 3;
}
thisf= 0;
@@ -271,6 +374,11 @@
*matched= 1;
if (fc_depends) thisf= (dependtry >= 4) ? 2 : 1;
debug(dbg_depcondetail," removing possdependee, returning %d",thisf);
+ if (!thisf) {
+ /* returns 3 if a loop is detected, otherwise 1 */
+ if (checkfor_dependency_loop(possdependee, requiredby) == 3)
+ thisf = 3;
+ }
return thisf;
}
switch (possdependee->status) {
@@ -293,12 +401,14 @@
}
if (possdependee->status == stat_installed) {
debug(dbg_depcondetail," is installed, ok and found");
+ del_loop_entry(requiredby, possdependee);
return 3;
}
if (possdependee->clientdata &&
possdependee->clientdata->istobe == itb_installnew) {
debug(dbg_depcondetail," unpacked/halfconfigured, defer");
- return 1;
+ /* returns 3 if a loop is detected, otherwise 1 */
+ return checkfor_dependency_loop(possdependee, requiredby);
} else if (!removing && fc_configureany && !skip_due_to_hold(possdependee)) {
fprintf(stderr,
_("dpkg: also configuring `%s' (required by `%s')\n"),
@@ -332,12 +442,54 @@
}
}
+/* 0=none, 1=defer, 2=withwarning, 3=ok */
+static int match_dependency(struct dependency *dep, struct pkginfo *pkg, int *matched,
+ int *interestingwarnings, struct varbuf *oemsgs,
+ struct pkginfo *removing) {
+ struct deppossi *possi, *provider;
+ int thisf = 0, found = 0;
+
+ for (possi= dep->list; found != 3 && possi; possi= possi->next) {
+ debug(dbg_depcondetail," checking possibility -> %s",possi->ed->name);
+ if (possi->cyclebreak) {
+ debug(dbg_depcondetail," break cycle so ok and found");
+ found= 3;
+ break;
+ }
+ thisf= deppossi_ok_found(possi->ed,pkg,removing,0,matched,possi,
+ interestingwarnings,oemsgs);
+ if (thisf > found)
+ found= thisf;
+ if (found != 3 && possi->verrel == dvr_none) {
+ if (possi->ed->installed.valid) {
+ for (provider= possi->ed->installed.depended;
+ found != 3 && provider;
+ provider= provider->nextrev) {
+ if (provider->up->type != dep_provides)
+ continue;
+ debug(dbg_depcondetail," checking provider %s",provider->up->up->name);
+ thisf = deppossi_ok_found(provider->up->up,pkg,removing,possi->ed,
+ matched,0,interestingwarnings,oemsgs);
+ if (thisf > found)
+ found= thisf;
+ }
+ }
+ }
+ debug(dbg_depcondetail," found %d",found);
+ if (thisf > found)
+ found= thisf;
+ }
+
+ /* 0=none, 1=defer, 2=withwarning, 3=ok */
+ return found;
+}
+
+/* returns 2=ok, 1=defer, 0=halt */
int dependencies_ok(struct pkginfo *pkg, struct pkginfo *removing,
struct varbuf *aemsgs) {
- int ok, matched, found, thisf, interestingwarnings;
+ int ok, matched, found, interestingwarnings;
struct varbuf oemsgs;
struct dependency *dep;
- struct deppossi *possi, *provider;
varbufinit(&oemsgs);
interestingwarnings= 0;
@@ -348,33 +500,12 @@
for (dep= pkg->installed.depends; dep; dep= dep->next) {
if (dep->type != dep_depends && dep->type != dep_predepends) continue;
debug(dbg_depcondetail," checking group ...");
- matched= 0; varbufreset(&oemsgs);
- found= 0; /* 0=none, 1=defer, 2=withwarning, 3=ok */
- for (possi= dep->list; found != 3 && possi; possi= possi->next) {
- debug(dbg_depcondetail," checking possibility -> %s",possi->ed->name);
- if (possi->cyclebreak) {
- debug(dbg_depcondetail," break cycle so ok and found");
- found= 3; break;
- }
- thisf= deppossi_ok_found(possi->ed,pkg,removing,0,
- &matched,possi,&interestingwarnings,&oemsgs);
- if (thisf > found) found= thisf;
- if (found != 3 && possi->verrel == dvr_none) {
- if (possi->ed->installed.valid) {
- for (provider= possi->ed->installed.depended;
- found != 3 && provider;
- provider= provider->nextrev) {
- if (provider->up->type != dep_provides) continue;
- debug(dbg_depcondetail," checking provider %s",provider->up->up->name);
- thisf= deppossi_ok_found(provider->up->up,pkg,removing,possi->ed,
- &matched,0,&interestingwarnings,&oemsgs);
- if (thisf > found) found= thisf;
- }
- }
- }
- debug(dbg_depcondetail," found %d",found);
- if (thisf > found) found= thisf;
- }
+ matched= 0;
+ varbufreset(&oemsgs);
+
+ found= match_dependency(dep, pkg, &matched,
+ &interestingwarnings, &oemsgs,
+ removing);
debug(dbg_depcondetail," found %d matched %d",found,matched);
if (removing && !matched) continue;
switch (found) {
Reply to: