Time to abandon recursive pulling of dependencies?
Stephen Montgomery-Smith
stephen at math.missouri.edu
Sun May 13 01:12:50 UTC 2007
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;
}
/*
More information about the freebsd-ports
mailing list