Hi,
I'm attaching a patch against startpar, specifically makeboot.{h,c}. It
should be able to drop into the debian/startpar/patches folder (but
needs offset adjusting) and is intended to obsolete
04_makeboot_loop_upper_bound.patch.
The check of the variable 'loop' in the original code is quite strange.
The dependency graph has no loops by construction, so I can only assume
that it was intended to catch an error on the part of the programmer,
rather a loop in the makefile dependencies itself. Anyway, the patch
still guarantees that check_loop will terminate since it cannot
recursively call itself more than the number of nodes in the dependency
graph.
The other problem with the original code is the efficiency of
check_loop. It treats the dependency graph as a tree instead of a DAG,
and therefore repeatedly checks the same parts of the graph multiple
times (hence the massive values for loop). I've avoided this by using a
flag variable that is set when a node is visited. Instead of having to
clear these flags, which is difficult to do in a depth-first
implementation anyway, that flag variable is an integer which changes
value on each call to check_loop.
Summing across /etc/init.d/.depend.{boot,start,stop} on my system, this
patch reduces the number of calls to check_loop from 3331320 to 8233
(0.25% of original).
Please let me know if you have any questions,
Francis
diff -Nur startpar/makeboot.c startpar.new//makeboot.c
--- startpar/makeboot.c 2011-03-21 22:33:39.649682525 +0000
+++ startpar.new//makeboot.c 2011-03-21 22:35:59.439157460 +0000
@@ -20,6 +20,8 @@
static int o_flags = O_RDONLY;
#endif
+static int check_loop(struct makenode *dep, struct makenode *src);
+static int check_loop_helper(struct makenode *dep, struct makenode *src);
int tree_entries = 0;
struct makenode *tree_list = NULL;
@@ -58,6 +60,7 @@
}
memset(node, 0, alignof(struct makenode)+strsize(name));
node->name = ((char*)node)+alignof(struct makenode);
+ node->cycle_check_value = -1;
strcpy(node->name, name);
/* append to the list in alphabetical order */
@@ -102,18 +105,29 @@
/*
* check whether the given target would create an infinte loop
*/
-static int loop;
+
+static int cycle_check_value;
static int check_loop(struct makenode *dep, struct makenode *src)
{
+ ++cycle_check_value;
+ return check_loop_helper(dep, src);
+}
+
+static int check_loop_helper(struct makenode *dep, struct makenode *src)
+{
+ if (dep->cycle_check_value == cycle_check_value)
+ return 0;
+ else
+ dep->cycle_check_value = cycle_check_value;
+
struct makelist *s;
for (s = dep->depend; s; s = s->next) {
if (s->node == src) {
fprintf(stderr, "loop exists %s in %s!\n", dep->name, src->name);
return 1;
}
- if (loop++ > 999)
- return 1;
- if (check_loop(s->node, src))
+
+ if (check_loop_helper(s->node, src))
return 1;
}
return 0;
@@ -127,7 +141,6 @@
struct makenode *dep;
dep = add_target(dst);
- loop = 0;
if (check_loop(dep, node))
return;
dep->select = new_list(node, dep->select);
diff -Nur startpar/makeboot.h startpar.new//makeboot.h
--- startpar/makeboot.h 2011-03-21 22:33:39.649682525 +0000
+++ startpar.new//makeboot.h 2011-03-21 22:34:47.071017702 +0000
@@ -17,6 +17,7 @@
struct makenode *next;
int interactive;
int importance;
+ int cycle_check_value;
};
/* dependency and selection list nodes */
