Date: Sat, 12 May 2007 20:11:49 -0500 From: Stephen Montgomery-Smith <stephen@math.missouri.edu> To: "[LoN]Kamikaze" <LoN_Kamikaze@gmx.de> Cc: freebsd-ports@freebsd.org, Kris Kennaway <kris@obsecurity.org> Subject: Re: Time to abandon recursive pulling of dependencies? Message-ID: <464665D5.1090509@math.missouri.edu> In-Reply-To: <4646193E.5040503@gmx.de> References: <464597C6.3030406@gmx.de> <20070512174011.GA22526@xor.obsecurity.org> <4645FF71.60100@gmx.de> <20070512175824.GA23103@xor.obsecurity.org> <20070512133054.B5588@math.missouri.edu> <4646193E.5040503@gmx.de>
index | next in thread | previous in thread | raw e-mail
[-- Attachment #1 --] 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 [-- Attachment #2 --] --- 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; } /*help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?464665D5.1090509>