[pacman-dev] [PATCH] deps.c: check for indirect deps when ordering
On upgrades, indirect dependencies were not being detected if there was a dependency in between them that was not part of the transaction. For example, with the dependency chain: pkg1 -> pkg2 -> pkg3, if pkg1 and pkg3 are being upgraded but not pkg2 pacman would not order pkg1 and pkg3 properly. This was particularly problematic when replacements were involved because the replaced package(s) would be removed at the start of the transaction. If an install script required the replacer and lacked a direct dependency, it could fail. Fixes FS#32764. Partially fixes FS#23011. Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- The need to keep state in order to avoid getting stuck in cyclic dependencies makes this a little ugly (hence the wrapper function). If anybody has a better idea for avoiding those loops, I'd love to clean it up. lib/libalpm/deps.c | 101 +++++++++++++++++++++++++++++++++------- test/pacman/tests/replace100.py | 2 - test/pacman/tests/upgrade100.py | 44 +++++++++++++++++ 3 files changed, 127 insertions(+), 20 deletions(-) create mode 100644 test/pacman/tests/upgrade100.py diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 96c49a9..adcdd3a 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -65,8 +65,8 @@ void _alpm_depmiss_free(alpm_depmissing_t *miss) FREE(miss); } -/* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */ -static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) +/** Check if pkg2 satisfies a dependency of pkg1 */ +static int _alpm_pkg_depends_on(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) { alpm_list_t *i; for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { @@ -77,6 +77,84 @@ static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) return 0; } +static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep) +{ + alpm_list_t *i; + + for(i = pkgs; i; i = i->next) { + alpm_pkg_t *pkg = i->data; + if(_alpm_depcmp(pkg, dep)) { + return pkg; + } + } + return NULL; +} + +/** Check if pkg2 is anywhere in pkg1's dependency tree. + * @param pkg1 + * @param pkg2 + * @param targets if a package in this list is an intermediate dependency + * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be + * reported + * @param ignore packages which should not be recursively checked for + * intermediate dependencies. Used internally for state to avoid + * getting stuck on cyclic dependencies. + * @return 1 if pkg2 is found in pkg1's dependency tree + */ +static int _alpm_pkg_in_dep_tree(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2, + alpm_list_t *targets, alpm_list_t **ignore) +{ + alpm_list_t *i, *pkgs = alpm_db_get_pkgcache(pkg1->handle->db_local); + + if(_alpm_pkg_depends_on(pkg1, pkg2)) { + return 1; + } + + *ignore = alpm_list_add(*ignore, pkg1); + + /* pkg1 does not directly depend on pkg2, but if this is an upgrade + * operation there may be an indirect dependency through an installed + * dependency not part of the current transaction */ + for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { + alpm_depend_t *dep = i->data; + alpm_pkg_t *lpkg = find_dep_satisfier(pkgs, dep); + + if(!lpkg) { + continue; + } else if(alpm_list_find(targets, lpkg, _alpm_pkg_cmp)) { + /* lpkg's upgrade is part of the transaction, any dependency will be + * detected separately as pkg1 -> lpkg and lpkg -> pkg2 */ + continue; + } else if(alpm_list_find(*ignore, lpkg, _alpm_pkg_cmp)) { + /* we've already checked lpkg, move on */ + continue; + } else if(_alpm_pkg_in_dep_tree(lpkg, pkg2, targets, ignore)) { + /* we have an indirect dependency: pkg1 -> lpkg -> ... -> pkg2 */ + return 1; + } + } + + return 0; +} + +/** Check if pkg2 is anywhere in pkg1's dependency tree. + * Wrapper for _alpm_pkg_in_dep_tree to handle creating and destroying state. + * @param pkg1 + * @param pkg2 + * @param targets if a package in this list is an intermediate dependency + * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be + * reported + * @return 1 if pkg2 is found in pkg1's dependency tree + */ +static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2, + alpm_list_t *targets) +{ + alpm_list_t *ignore = NULL; + int ret = _alpm_pkg_in_dep_tree(pkg1, pkg2, targets, &ignore); + alpm_list_free(ignore); + return ret; +} + /* Convert a list of alpm_pkg_t * to a graph structure, * with a edge for each dependency. * Returns a list of vertices (one vertex = one package) @@ -101,7 +179,7 @@ static alpm_list_t *dep_graph_init(alpm_list_t *targets) for(j = vertices; j; j = j->next) { alpm_graph_t *vertex_j = j->data; alpm_pkg_t *p_j = vertex_j->data; - if(_alpm_dep_edge(p_i, p_j)) { + if(_alpm_dep_edge(p_i, p_j, targets)) { vertex_i->children = alpm_list_add(vertex_i->children, vertex_j); } @@ -229,19 +307,6 @@ static void release_filtered_depend(alpm_depend_t *dep, int nodepversion) } } -static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep) -{ - alpm_list_t *i; - - for(i = pkgs; i; i = i->next) { - alpm_pkg_t *pkg = i->data; - if(_alpm_depcmp(pkg, dep)) { - return pkg; - } - } - return NULL; -} - /** Find a package satisfying a specified dependency. * The dependency can include versions with depmod operators. * @param pkgs an alpm_list_t* of alpm_pkg_t where the satisfier will be searched @@ -517,7 +582,7 @@ static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg, /* see if other packages need it */ for(i = _alpm_db_get_pkgcache(db); i; i = i->next) { alpm_pkg_t *lpkg = i->data; - if(_alpm_dep_edge(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) { + if(_alpm_pkg_depends_on(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) { return 0; } } @@ -549,7 +614,7 @@ int _alpm_recursedeps(alpm_db_t *db, alpm_list_t *targs, int include_explicit) alpm_pkg_t *pkg = i->data; for(j = _alpm_db_get_pkgcache(db); j; j = j->next) { alpm_pkg_t *deppkg = j->data; - if(_alpm_dep_edge(pkg, deppkg) + if(_alpm_pkg_depends_on(pkg, deppkg) && can_remove_package(db, deppkg, targs, include_explicit)) { alpm_pkg_t *copy; _alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n", diff --git a/test/pacman/tests/replace100.py b/test/pacman/tests/replace100.py index f94ca0f..dcb7111 100644 --- a/test/pacman/tests/replace100.py +++ b/test/pacman/tests/replace100.py @@ -41,5 +41,3 @@ self.addrule("PKG_VERSION=kernel26|2.6.37.1-1") self.addrule("FILE_EXIST=sbin/blkid") self.addrule("FILE_EXIST=foundit") - -self.expectfailure = True diff --git a/test/pacman/tests/upgrade100.py b/test/pacman/tests/upgrade100.py new file mode 100644 index 0000000..3f7a021 --- /dev/null +++ b/test/pacman/tests/upgrade100.py @@ -0,0 +1,44 @@ +self.description = "Indirect dependency ordering (FS#32764)" + +lp1 = pmpkg("fcitx-gtk2", "1.0-1"); +lp1.depends = ["gtk2"] +self.addpkg2db("local", lp1) + +lp2 = pmpkg("gtk2", "1.0-1"); +lp2.depends = ["pango"] +self.addpkg2db("local", lp2) + +lp3 = pmpkg("pango", "1.0-1"); +lp3.depends = ["harfbuzz"] +self.addpkg2db("local", lp3) + +lp4 = pmpkg("harfbuzz", "1.0-1"); +lp4.depends = ["icu"] +self.addpkg2db("local", lp4) + +lp5 = pmpkg("icu", "1.0-1"); +self.addpkg2db("local", lp5) + +sp1 = pmpkg("fcitx-gtk2", "1.0-2"); +sp1.depends = ["gtk2"] +sp1.install['post_upgrade'] = "[ -f bin/harfbuzz ] && echo > found_harfbuzz" +self.addpkg2db("sync", sp1) + +sp4 = pmpkg("harfbuzz", "1.0-2"); +sp4.depends = ["icu"] +sp4.files = ["bin/harfbuzz"] +sp4.install['post_upgrade'] = "[ -f bin/icu ] && echo > found_icu" +self.addpkg2db("sync", sp4) + +sp5 = pmpkg("icu", "1.0-2"); +sp5.files = ["bin/icu"] +self.addpkg2db("sync", sp5) + +self.args = "-Su" + +self.addrule("PACMAN_RETCODE=0") +self.addrule("PKG_VERSION=fcitx-gtk2|1.0-2") +self.addrule("PKG_VERSION=harfbuzz|1.0-2") +self.addrule("PKG_VERSION=icu|1.0-2") +self.addrule("FILE_EXIST=found_harfbuzz") +self.addrule("FILE_EXIST=found_icu") -- 1.8.2.3
On 19/05/13 05:53, Andrew Gregory wrote:
On upgrades, indirect dependencies were not being detected if there was a dependency in between them that was not part of the transaction. For example, with the dependency chain: pkg1 -> pkg2 -> pkg3, if pkg1 and pkg3 are being upgraded but not pkg2 pacman would not order pkg1 and pkg3 properly.
This was particularly problematic when replacements were involved because the replaced package(s) would be removed at the start of the transaction. If an install script required the replacer and lacked a direct dependency, it could fail.
Fixes FS#32764.
Partially fixes FS#23011.
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> ---
The need to keep state in order to avoid getting stuck in cyclic dependencies makes this a little ugly (hence the wrapper function). If anybody has a better idea for avoiding those loops, I'd love to clean it up.
Finally got to reviewing this... I can not immediately see a way to avoid those loops. Signed-off-by: Allan
lib/libalpm/deps.c | 101 +++++++++++++++++++++++++++++++++------- test/pacman/tests/replace100.py | 2 - test/pacman/tests/upgrade100.py | 44 +++++++++++++++++ 3 files changed, 127 insertions(+), 20 deletions(-) create mode 100644 test/pacman/tests/upgrade100.py
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 96c49a9..adcdd3a 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -65,8 +65,8 @@ void _alpm_depmiss_free(alpm_depmissing_t *miss) FREE(miss); }
-/* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */ -static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) +/** Check if pkg2 satisfies a dependency of pkg1 */ +static int _alpm_pkg_depends_on(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) { alpm_list_t *i; for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { @@ -77,6 +77,84 @@ static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2) return 0; }
+static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep) +{ + alpm_list_t *i; + + for(i = pkgs; i; i = i->next) { + alpm_pkg_t *pkg = i->data; + if(_alpm_depcmp(pkg, dep)) { + return pkg; + } + } + return NULL; +} + +/** Check if pkg2 is anywhere in pkg1's dependency tree. + * @param pkg1 + * @param pkg2 + * @param targets if a package in this list is an intermediate dependency + * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be + * reported + * @param ignore packages which should not be recursively checked for + * intermediate dependencies. Used internally for state to avoid + * getting stuck on cyclic dependencies. + * @return 1 if pkg2 is found in pkg1's dependency tree + */ +static int _alpm_pkg_in_dep_tree(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2, + alpm_list_t *targets, alpm_list_t **ignore) +{ + alpm_list_t *i, *pkgs = alpm_db_get_pkgcache(pkg1->handle->db_local); + + if(_alpm_pkg_depends_on(pkg1, pkg2)) { + return 1; + } + + *ignore = alpm_list_add(*ignore, pkg1); + + /* pkg1 does not directly depend on pkg2, but if this is an upgrade + * operation there may be an indirect dependency through an installed + * dependency not part of the current transaction */ + for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { + alpm_depend_t *dep = i->data; + alpm_pkg_t *lpkg = find_dep_satisfier(pkgs, dep); + + if(!lpkg) { + continue; + } else if(alpm_list_find(targets, lpkg, _alpm_pkg_cmp)) { + /* lpkg's upgrade is part of the transaction, any dependency will be + * detected separately as pkg1 -> lpkg and lpkg -> pkg2 */ + continue; + } else if(alpm_list_find(*ignore, lpkg, _alpm_pkg_cmp)) { + /* we've already checked lpkg, move on */ + continue; + } else if(_alpm_pkg_in_dep_tree(lpkg, pkg2, targets, ignore)) { + /* we have an indirect dependency: pkg1 -> lpkg -> ... -> pkg2 */ + return 1; + } + } + + return 0; +} + +/** Check if pkg2 is anywhere in pkg1's dependency tree. + * Wrapper for _alpm_pkg_in_dep_tree to handle creating and destroying state. + * @param pkg1 + * @param pkg2 + * @param targets if a package in this list is an intermediate dependency + * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be + * reported + * @return 1 if pkg2 is found in pkg1's dependency tree + */ +static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2, + alpm_list_t *targets) +{ + alpm_list_t *ignore = NULL; + int ret = _alpm_pkg_in_dep_tree(pkg1, pkg2, targets, &ignore); + alpm_list_free(ignore); + return ret; +} + /* Convert a list of alpm_pkg_t * to a graph structure, * with a edge for each dependency. * Returns a list of vertices (one vertex = one package) @@ -101,7 +179,7 @@ static alpm_list_t *dep_graph_init(alpm_list_t *targets) for(j = vertices; j; j = j->next) { alpm_graph_t *vertex_j = j->data; alpm_pkg_t *p_j = vertex_j->data; - if(_alpm_dep_edge(p_i, p_j)) { + if(_alpm_dep_edge(p_i, p_j, targets)) { vertex_i->children = alpm_list_add(vertex_i->children, vertex_j); } @@ -229,19 +307,6 @@ static void release_filtered_depend(alpm_depend_t *dep, int nodepversion) } }
-static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep) -{ - alpm_list_t *i; - - for(i = pkgs; i; i = i->next) { - alpm_pkg_t *pkg = i->data; - if(_alpm_depcmp(pkg, dep)) { - return pkg; - } - } - return NULL; -} - /** Find a package satisfying a specified dependency. * The dependency can include versions with depmod operators. * @param pkgs an alpm_list_t* of alpm_pkg_t where the satisfier will be searched @@ -517,7 +582,7 @@ static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg, /* see if other packages need it */ for(i = _alpm_db_get_pkgcache(db); i; i = i->next) { alpm_pkg_t *lpkg = i->data; - if(_alpm_dep_edge(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) { + if(_alpm_pkg_depends_on(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) { return 0; } } @@ -549,7 +614,7 @@ int _alpm_recursedeps(alpm_db_t *db, alpm_list_t *targs, int include_explicit) alpm_pkg_t *pkg = i->data; for(j = _alpm_db_get_pkgcache(db); j; j = j->next) { alpm_pkg_t *deppkg = j->data; - if(_alpm_dep_edge(pkg, deppkg) + if(_alpm_pkg_depends_on(pkg, deppkg) && can_remove_package(db, deppkg, targs, include_explicit)) { alpm_pkg_t *copy; _alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n", diff --git a/test/pacman/tests/replace100.py b/test/pacman/tests/replace100.py index f94ca0f..dcb7111 100644 --- a/test/pacman/tests/replace100.py +++ b/test/pacman/tests/replace100.py @@ -41,5 +41,3 @@ self.addrule("PKG_VERSION=kernel26|2.6.37.1-1") self.addrule("FILE_EXIST=sbin/blkid") self.addrule("FILE_EXIST=foundit") - -self.expectfailure = True diff --git a/test/pacman/tests/upgrade100.py b/test/pacman/tests/upgrade100.py new file mode 100644 index 0000000..3f7a021 --- /dev/null +++ b/test/pacman/tests/upgrade100.py @@ -0,0 +1,44 @@ +self.description = "Indirect dependency ordering (FS#32764)" + +lp1 = pmpkg("fcitx-gtk2", "1.0-1"); +lp1.depends = ["gtk2"] +self.addpkg2db("local", lp1) + +lp2 = pmpkg("gtk2", "1.0-1"); +lp2.depends = ["pango"] +self.addpkg2db("local", lp2) + +lp3 = pmpkg("pango", "1.0-1"); +lp3.depends = ["harfbuzz"] +self.addpkg2db("local", lp3) + +lp4 = pmpkg("harfbuzz", "1.0-1"); +lp4.depends = ["icu"] +self.addpkg2db("local", lp4) + +lp5 = pmpkg("icu", "1.0-1"); +self.addpkg2db("local", lp5) + +sp1 = pmpkg("fcitx-gtk2", "1.0-2"); +sp1.depends = ["gtk2"] +sp1.install['post_upgrade'] = "[ -f bin/harfbuzz ] && echo > found_harfbuzz" +self.addpkg2db("sync", sp1) + +sp4 = pmpkg("harfbuzz", "1.0-2"); +sp4.depends = ["icu"] +sp4.files = ["bin/harfbuzz"] +sp4.install['post_upgrade'] = "[ -f bin/icu ] && echo > found_icu" +self.addpkg2db("sync", sp4) + +sp5 = pmpkg("icu", "1.0-2"); +sp5.files = ["bin/icu"] +self.addpkg2db("sync", sp5) + +self.args = "-Su" + +self.addrule("PACMAN_RETCODE=0") +self.addrule("PKG_VERSION=fcitx-gtk2|1.0-2") +self.addrule("PKG_VERSION=harfbuzz|1.0-2") +self.addrule("PKG_VERSION=icu|1.0-2") +self.addrule("FILE_EXIST=found_harfbuzz") +self.addrule("FILE_EXIST=found_icu")
On 18.06.2013 08:04, Allan McRae wrote:
On 19/05/13 05:53, Andrew Gregory wrote:
On upgrades, indirect dependencies were not being detected if there was a dependency in between them that was not part of the transaction. For example, with the dependency chain: pkg1 -> pkg2 -> pkg3, if pkg1 and pkg3 are being upgraded but not pkg2 pacman would not order pkg1 and pkg3 properly.
This was particularly problematic when replacements were involved because the replaced package(s) would be removed at the start of the transaction. If an install script required the replacer and lacked a direct dependency, it could fail.
Fixes FS#32764.
Partially fixes FS#23011.
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> ---
The need to keep state in order to avoid getting stuck in cyclic dependencies makes this a little ugly (hence the wrapper function). If anybody has a better idea for avoiding those loops, I'd love to clean it up.
Finally got to reviewing this... I can not immediately see a way to avoid those loops.
Signed-off-by: Allan
This patch causes a slowdown from subsecond sort time to ~60sec on my machine (i7-920) when sorting 183 packages for -Su.
On 17/10/13 21:57, Florian Pritz wrote:
On 18.06.2013 08:04, Allan McRae wrote:
On 19/05/13 05:53, Andrew Gregory wrote:
On upgrades, indirect dependencies were not being detected if there was a dependency in between them that was not part of the transaction. For example, with the dependency chain: pkg1 -> pkg2 -> pkg3, if pkg1 and pkg3 are being upgraded but not pkg2 pacman would not order pkg1 and pkg3 properly.
This was particularly problematic when replacements were involved because the replaced package(s) would be removed at the start of the transaction. If an install script required the replacer and lacked a direct dependency, it could fail.
Fixes FS#32764.
Partially fixes FS#23011.
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> ---
The need to keep state in order to avoid getting stuck in cyclic dependencies makes this a little ugly (hence the wrapper function). If anybody has a better idea for avoiding those loops, I'd love to clean it up.
Finally got to reviewing this... I can not immediately see a way to avoid those loops.
Signed-off-by: Allan
This patch causes a slowdown from subsecond sort time to ~60sec on my machine (i7-920) when sorting 183 packages for -Su.
I filed a bug report to keep track of this: https://bugs.archlinux.org/task/37380 A
Detecting indirect dependencies by traversing a package's entire dependency tree is prohibitively slow for larger transactions. Instead add local packages to the dependency graph. This additionally requires delaying dependency ordering for sync operations so that removed packages may be excluded from dependency detection. tests/sync012.py was also updated to ensure that the dependency cycle was actually detected. Fixes FS#37380 Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> --- $ ./pacman -Sg | (time ./pacman -Sp -) | wc -l ./pacman -Sp - 1.38s user 0.04s system 82% cpu 1.718 total 1293 lib/libalpm/deps.c | 155 ++++++++++++++++++++----------------------- lib/libalpm/deps.h | 3 +- lib/libalpm/remove.c | 2 +- lib/libalpm/sync.c | 9 ++- test/pacman/tests/sync012.py | 2 + 5 files changed, 82 insertions(+), 89 deletions(-) diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 745eac1..7cf2d36 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -90,69 +90,9 @@ static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep) return NULL; } -/** Check if pkg2 is anywhere in pkg1's dependency tree. - * @param pkg1 - * @param pkg2 - * @param targets if a package in this list is an intermediate dependency - * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be - * reported - * @param ignore packages which should not be recursively checked for - * intermediate dependencies. Used internally for state to avoid - * getting stuck on cyclic dependencies. - * @return 1 if pkg2 is found in pkg1's dependency tree - */ -static int _alpm_pkg_in_dep_tree(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2, - alpm_list_t *targets, alpm_list_t **ignore) -{ - alpm_list_t *i, *pkgs = alpm_db_get_pkgcache(pkg1->handle->db_local); - - if(_alpm_pkg_depends_on(pkg1, pkg2)) { - return 1; - } - - *ignore = alpm_list_add(*ignore, pkg1); - - /* pkg1 does not directly depend on pkg2, but if this is an upgrade - * operation there may be an indirect dependency through an installed - * dependency not part of the current transaction */ - for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) { - alpm_depend_t *dep = i->data; - alpm_pkg_t *lpkg = find_dep_satisfier(pkgs, dep); - - if(!lpkg) { - continue; - } else if(alpm_list_find(targets, lpkg, _alpm_pkg_cmp)) { - /* lpkg's upgrade is part of the transaction, any dependency will be - * detected separately as pkg1 -> lpkg and lpkg -> pkg2 */ - continue; - } else if(alpm_list_find(*ignore, lpkg, _alpm_pkg_cmp)) { - /* we've already checked lpkg, move on */ - continue; - } else if(_alpm_pkg_in_dep_tree(lpkg, pkg2, targets, ignore)) { - /* we have an indirect dependency: pkg1 -> lpkg -> ... -> pkg2 */ - return 1; - } - } - - return 0; -} - -/** Check if pkg2 is anywhere in pkg1's dependency tree. - * Wrapper for _alpm_pkg_in_dep_tree to handle creating and destroying state. - * @param pkg1 - * @param pkg2 - * @param targets if a package in this list is an intermediate dependency - * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be - * reported - * @return 1 if pkg2 is found in pkg1's dependency tree - */ -static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2, - alpm_list_t *targets) +static int ptr_cmp(const void *p, const void *q) { - alpm_list_t *ignore = NULL; - int ret = _alpm_pkg_in_dep_tree(pkg1, pkg2, targets, &ignore); - alpm_list_free(ignore); - return ret; + return (p != q); } /* Convert a list of alpm_pkg_t * to a graph structure, @@ -160,10 +100,14 @@ static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2, * Returns a list of vertices (one vertex = one package) * (used by alpm_sortbydeps) */ -static alpm_list_t *dep_graph_init(alpm_list_t *targets) +static alpm_list_t *dep_graph_init(alpm_handle_t *handle, + alpm_list_t *targets, alpm_list_t *ignore) { alpm_list_t *i, *j; alpm_list_t *vertices = NULL; + alpm_list_t *localpkgs = alpm_list_diff( + alpm_db_get_pkgcache(handle->db_local), ignore, ptr_cmp); + /* We create the vertices */ for(i = targets; i; i = i->next) { alpm_graph_t *vertex = _alpm_graph_new(); @@ -179,13 +123,32 @@ static alpm_list_t *dep_graph_init(alpm_list_t *targets) for(j = vertices; j; j = j->next) { alpm_graph_t *vertex_j = j->data; alpm_pkg_t *p_j = vertex_j->data; - if(_alpm_dep_edge(p_i, p_j, targets)) { + if(_alpm_pkg_depends_on(p_i, p_j)) { + vertex_i->children = + alpm_list_add(vertex_i->children, vertex_j); + } + } + + /* lazily add local packages to the dep graph so they don't + * get resolved unnecessarily */ + j = localpkgs; + while(j) { + alpm_list_t *next = j->next; + if(_alpm_pkg_depends_on(p_i, j->data)) { + alpm_graph_t *vertex_j = _alpm_graph_new(); + vertex_j->data = (void *)j->data; + vertices = alpm_list_add(vertices, vertex_j); vertex_i->children = alpm_list_add(vertex_i->children, vertex_j); + localpkgs = alpm_list_remove_item(localpkgs, j); + free(j); } + j = next; } + vertex_i->childptr = vertex_i->children; } + alpm_list_free(localpkgs); return vertices; } @@ -198,13 +161,15 @@ static alpm_list_t *dep_graph_init(alpm_list_t *targets) * * Should be re-ordered to C,A,B,D * + * packages listed in ignore will not be used to detect indirect dependencies + * * if reverse is > 0, the dependency order will be reversed. * * This function returns the new alpm_list_t* target list. * */ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, - alpm_list_t *targets, int reverse) + alpm_list_t *targets, alpm_list_t *ignore, int reverse) { alpm_list_t *newtargs = NULL; alpm_list_t *vertices = NULL; @@ -217,7 +182,7 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, _alpm_log(handle, ALPM_LOG_DEBUG, "started sorting dependencies\n"); - vertices = dep_graph_init(targets); + vertices = dep_graph_init(handle, targets, ignore); vptr = vertices; vertex = vertices->data; @@ -232,34 +197,56 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, found = 1; nextchild->parent = vertex; vertex = nextchild; - } - else if(nextchild->state == -1) { - alpm_pkg_t *vertexpkg = vertex->data; - alpm_pkg_t *childpkg = nextchild->data; - - _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); - if(reverse) { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be removed after its %s dependency\n"), - vertexpkg->name, childpkg->name); + } else if(nextchild->state == -1) { + /* child is an ancestor of vertex */ + alpm_graph_t *transvertex = vertex; + + if(!alpm_list_find(targets, nextchild->data, ptr_cmp)) { + /* child is not part of the transaction, not a problem */ + continue; + } + + /* find the nearest parent that's part of the transaction */ + while(transvertex) { + if(alpm_list_find(targets, transvertex->data, ptr_cmp)) { + break; + } + transvertex = transvertex->parent; + } + + if(!transvertex || transvertex == nextchild) { + /* no transaction package in our ancestry or the package has + * a circular dependency with itself, not a problem */ } else { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be installed before its %s dependency\n"), - vertexpkg->name, childpkg->name); + alpm_pkg_t *transpkg = transvertex->data; + alpm_pkg_t *childpkg = nextchild->data; + _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); + if(reverse) { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be removed after its %s dependency\n"), + transpkg->name, childpkg->name); + } else { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be installed before its %s dependency\n"), + transpkg->name, childpkg->name); + } } } } if(!found) { - newtargs = alpm_list_add(newtargs, vertex->data); + if(alpm_list_find(targets, vertex->data, ptr_cmp)) { + newtargs = alpm_list_add(newtargs, vertex->data); + } /* mark that we've left this vertex */ vertex->state = 1; vertex = vertex->parent; if(!vertex) { - vptr = vptr->next; - while(vptr) { + /* top level vertex reached, move to the next unprocessed vertex */ + for( vptr = vptr->next; vptr; vptr = vptr->next) { vertex = vptr->data; - if(vertex->state == 0) break; - vptr = vptr->next; + if(vertex->state == 0) { + break; + } } } } diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h index 1fbeff9..8cf5ad2 100644 --- a/lib/libalpm/deps.h +++ b/lib/libalpm/deps.h @@ -30,7 +30,8 @@ void _alpm_dep_free(alpm_depend_t *dep); alpm_depend_t *_alpm_dep_dup(const alpm_depend_t *dep); void _alpm_depmiss_free(alpm_depmissing_t *miss); -alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, alpm_list_t *targets, int reverse); +alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, + alpm_list_t *targets, alpm_list_t *ignore, int reverse); int _alpm_recursedeps(alpm_db_t *db, alpm_list_t *targs, int include_explicit); int _alpm_resolvedeps(alpm_handle_t *handle, alpm_list_t *localpkgs, alpm_pkg_t *pkg, alpm_list_t *preferred, alpm_list_t **packages, alpm_list_t *remove, diff --git a/lib/libalpm/remove.c b/lib/libalpm/remove.c index 7cb86ff..2e72852 100644 --- a/lib/libalpm/remove.c +++ b/lib/libalpm/remove.c @@ -242,7 +242,7 @@ int _alpm_remove_prepare(alpm_handle_t *handle, alpm_list_t **data) /* re-order w.r.t. dependencies */ _alpm_log(handle, ALPM_LOG_DEBUG, "sorting by dependencies\n"); - lp = _alpm_sortbydeps(handle, trans->remove, 1); + lp = _alpm_sortbydeps(handle, trans->remove, NULL, 1); /* free the old alltargs */ alpm_list_free(trans->remove); trans->remove = lp; diff --git a/lib/libalpm/sync.c b/lib/libalpm/sync.c index 9081c73..6b1e054 100644 --- a/lib/libalpm/sync.c +++ b/lib/libalpm/sync.c @@ -471,10 +471,8 @@ int _alpm_sync_prepare(alpm_handle_t *handle, alpm_list_t **data) * holds to package objects. */ trans->unresolvable = unresolvable; - /* re-order w.r.t. dependencies */ alpm_list_free(trans->add); - trans->add = _alpm_sortbydeps(handle, resolved, 0); - alpm_list_free(resolved); + trans->add = resolved; EVENT(handle, ALPM_EVENT_RESOLVEDEPS_DONE, NULL, NULL); } @@ -628,6 +626,11 @@ int _alpm_sync_prepare(alpm_handle_t *handle, alpm_list_t **data) } goto cleanup; } + + /* re-order w.r.t. dependencies */ + alpm_list_t *add_orig = trans->add; + trans->add = _alpm_sortbydeps(handle, add_orig, trans->remove, 0); + alpm_list_free(add_orig); } for(i = trans->add; i; i = i->next) { /* update download size field */ diff --git a/test/pacman/tests/sync012.py b/test/pacman/tests/sync012.py index 3aaba37..441e5d5 100644 --- a/test/pacman/tests/sync012.py +++ b/test/pacman/tests/sync012.py @@ -18,3 +18,5 @@ self.addrule("PKG_EXIST=pkg1") self.addrule("PKG_EXIST=pkg2") self.addrule("PKG_EXIST=pkg3") +self.addrule("PACMAN_OUTPUT=dependency cycle detected") +self.addrule("PACMAN_OUTPUT=pkg3 will be installed before its pkg1 dependency") -- 1.8.4.1
On 18/10/13 13:38, Andrew Gregory wrote:
Detecting indirect dependencies by traversing a package's entire dependency tree is prohibitively slow for larger transactions. Instead add local packages to the dependency graph. This additionally requires delaying dependency ordering for sync operations so that removed packages may be excluded from dependency detection.
tests/sync012.py was also updated to ensure that the dependency cycle was actually detected.
Fixes FS#37380
Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> ---
Have not reviewed the patch itself yet, but the diff between the output of "pacman -Sg | pacman -Sp -" with and without the patch is:
diff -Naur old.txt new.txt --- old.txt 2013-10-18 14:39:08.001081130 +1000 +++ new.txt 2013-10-18 14:24:34.621969663 +1000 @@ -9,12 +9,12 @@ http://topsecretserver.org/testing/os/x86_64/logrotate-3.8.7-1-x86_64.pkg.ta... http://topsecretserver.org/core/os/x86_64/bzip2-1.0.6-4-x86_64.pkg.tar.xz http://topsecretserver.org/core/os/x86_64/coreutils-8.21-2-x86_64.pkg.tar.xz +http://topsecretserver.org/core/os/x86_64/perl-5.18.1-1-x86_64.pkg.tar.xz +http://topsecretserver.org/core/os/x86_64/gawk-4.1.0-1-x86_64.pkg.tar.xz http://topsecretserver.org/core/os/x86_64/shadow-4.1.5.1-6-x86_64.pkg.tar.xz http://topsecretserver.org/core/os/x86_64/util-linux-2.23.2-1-x86_64.pkg.tar... http://topsecretserver.org/core/os/x86_64/e2fsprogs-1.42.8-1-x86_64.pkg.tar.... http://topsecretserver.org/core/os/x86_64/findutils-4.4.2-5-x86_64.pkg.tar.x... -http://topsecretserver.org/core/os/x86_64/gawk-4.1.0-1-x86_64.pkg.tar.xz -http://topsecretserver.org/core/os/x86_64/perl-5.18.1-1-x86_64.pkg.tar.xz http://topsecretserver.org/core/os/x86_64/sed-4.2.2-3-x86_64.pkg.tar.xz http://topsecretserver.org/testing/os/x86_64/pacman-4.1.2-2-x86_64.pkg.tar.x... http://topsecretserver.org/core/os/x86_64/cronie-1.4.9-5-x86_64.pkg.tar.xz
which obviously is cosmetic. And a bit over 15 minutes or runtime... A
participants (3)
-
Allan McRae
-
Andrew Gregory
-
Florian Pritz