Time to abandon recursive pulling of dependencies?

[Stephen Montgomery-Smith]

OK chaps, this is what I came up with.  So for example, if I do "make 
install" on /usr/ports/x11/xorg (having made all the dependencies), on 
my computer it turns the pkg_create from taking about 4 minutes to the 
blink of an eye.  Now people need to figure out how to speed up the 
"make package-depends" in bsd.ports.mk, but that is beyond my abilities.

I really hope this works.  The prospect of modifying a piece of code 
that is used by practically the whole FreeBSD community kind of scares 
me, so I would appreciate some good testing.

Apply the patch http://www.math.missouri.edu/~stephen/deps/ddd to 
/usr/src/usr.sbin/pkg_install/lib.  I have also put the patch as an 
attachment, but I don't know if the mail filters will take it out.

Stephen
-------------- next part --------------
--- deps.c-orig	Sat May 12 19:02:21 2007
+++ deps.c	Sat May 12 19:56:17 2007
@@ -26,98 +26,105 @@
 #include <err.h>
 #include <stdio.h>
 
+void list_deps(const char *pkgname, char **pkgs, char *listed, 
+               char *check_loop, char **newpkgs, int *nrnewpkgs, int *errcount);
+
 /*
  * Sort given NULL-terminated list of installed packages (pkgs) in
  * such a way that if package A depends on package B then after
  * sorting A will be listed before B no matter how they were
  * originally positioned in the list.
+ *
+ * Works by performing a recursive depth-first search on the required-by lists.
  */
+
 int
 sortdeps(char **pkgs)
 {
-    char *tmp;
-    int i, j, loop_cnt;
-    int err_cnt = 0;
+    int i, errcount=0;
+    int nrpkgs, nrnewpkgs;
+    char *listed, *check_loop, **newpkgs;
+    char *cp;
 
     if (pkgs[0] == NULL || pkgs[1] == NULL)
 	return (0);
 
-    for (i = 0; pkgs[i + 1]; i++) {
-	/*
-	 * Check to see if any other package in pkgs[i+1:] depends
-	 * on pkgs[i] and swap those two packages if so.
-	 */
-	loop_cnt = 0;
-	for (j = i + 1; pkgs[j]; j++) {
-	    if (chkifdepends(pkgs[j], pkgs[i]) == 1) {
-		/*
-		 * Try to avoid deadlock if package A depends on B which in
-		 * turn depends on C and C due to an error depends on A.
-		 * Use ugly but simple method, becase it Should Never
-		 * Happen[tm] in the real life anyway.
-		 */
-		if (loop_cnt > 4096) {
-		    warnx("dependency loop detected for package %s", pkgs[j]);
-		    err_cnt++;
-		    break;
-		}
-		loop_cnt++;
-		tmp = pkgs[i];
-		pkgs[i] = pkgs[j];
-		pkgs[j] = tmp;
-		/*
-		 * Another iteration requred to check if new pkgs[i]
-		 * itself has any packages that depend on it
-		 */
-		j = i + 1;
-	    }
-	}
+    nrpkgs = 0;
+    while (pkgs[nrpkgs]) nrpkgs++;
+    listed = malloc(nrpkgs);
+    bzero(listed,nrpkgs);
+    check_loop = malloc(nrpkgs);
+    bzero(check_loop,nrpkgs);
+    newpkgs = malloc(nrpkgs*sizeof(char*));
+    nrnewpkgs = 0;
+
+    for (i = 0; pkgs[i]; i++) if (!listed[i]) {
+	check_loop[i] = 1;
+	cp = strchr(pkgs[i], ':');
+	if (cp != NULL)
+	    *cp = '\0';
+	list_deps(pkgs[i],pkgs,listed,check_loop,newpkgs,&nrnewpkgs,&errcount);
+	if (cp != NULL)
+	    *cp = ':';
+	listed[i] = 1;
+	newpkgs[nrnewpkgs] = pkgs[i];
+	nrnewpkgs++;
     }
-    return err_cnt;
+
+    if (nrnewpkgs != nrpkgs) {
+	fprintf(stderr,"Huge error in code\n");
+	exit(1);
+    }
+    for (i = 0; i < nrnewpkgs; i++) pkgs[i] = newpkgs[i];
+
+    return errcount;
 }
 
 /*
- * Check to see if pkgname1 depends on pkgname2.
- * Returns 1 if depends, 0 if not, and -1 if error occured.
- */ 
-int
-chkifdepends(const char *pkgname1, const char *pkgname2)
-{
-    char *cp1, *cp2;
-    int errcode;
+ * This recursive function lists the dependencies (that is, the "required-by"s)
+ * for pkgname, putting them into newpkgs.
+ */
+
+void list_deps(const char *pkgname, char **pkgs, char *listed, 
+               char *check_loop, char **newpkgs, int *nrnewpkgs, int *errcount) {
+    char *cp;
+    int errcode, j;
     struct reqr_by_entry *rb_entry;
     struct reqr_by_head *rb_list;
 
-    cp2 = strchr(pkgname2, ':');
-    if (cp2 != NULL)
-	*cp2 = '\0';
-    cp1 = strchr(pkgname1, ':');
-    if (cp1 != NULL)
-	*cp1 = '\0';
-
-    errcode = 0;
-    /* Check that pkgname2 is actually installed */
-    if (isinstalledpkg(pkgname2) <= 0)
-	goto exit;
+    if (isinstalledpkg(pkgname) <= 0)
+	return;
 
-    errcode = requiredby(pkgname2, &rb_list, FALSE, TRUE);
+    errcode = requiredby(pkgname, &rb_list, FALSE, TRUE);
     if (errcode < 0)
-	goto exit;
+	return;
 
-    errcode = 0;
-    STAILQ_FOREACH(rb_entry, rb_list, link) {
-	if (strcmp(rb_entry->pkgname, pkgname1) == 0) {	/* match */
-	    errcode = 1;
-	    break;
+    STAILQ_FOREACH(rb_entry, rb_list, link)
+	for (j = 0; pkgs[j]; j++) if (!listed[j]) {
+	    cp = strchr(pkgs[j], ':');
+	    if (cp != NULL)
+		*cp = '\0';
+	    if (strcmp(rb_entry->pkgname, pkgs[j]) == 0) { /*match */
+		/*
+		 * Try to avoid deadlock if package A depends on B which in
+		 * turn depends on C and C due to an error depends on A.
+		 * It Should Never Happen[tm] in the real life.
+		 */
+		if (check_loop[j]) {
+		    warnx("dependency loop detected for package %s", pkgs[j]);
+		    (*errcount)++;
+		}
+		else {
+		    check_loop[j] = 1;
+		    list_deps(pkgs[j],pkgs,listed,check_loop,newpkgs,nrnewpkgs,errcount);
+		    listed[j] = 1;
+		    newpkgs[*nrnewpkgs] = pkgs[j];
+		    (*nrnewpkgs)++;
+		}
+	    }
+	    if (cp != NULL)
+		*cp = ':';
 	}
-    }
-
-exit:
-    if (cp1 != NULL)
-	*cp1 = ':';
-    if (cp2 != NULL)
-	*cp2 = ':';
-    return errcode;
 }
 
 /*