Bug#614249: britney2: insufficient removal checks
Package: release.debian.org
User: release.debian.org@packages.debian.org
Usertag: britney
Tag: patch
[Executive summary: britney2's attempt to avoid continually
installability checking the entire package set means it can increase
installability when removing packages]
Hi,
britney1 and britney2 have different methods of determining whether a
package can be removed from testing, which recently led to britney2
removing a package when it shouldn't have. A patch which appears to fix
this is attached, the remainder of this mail is discussion of what
happened and why I believe the patch is correct.
To set the scene... a package P depends on functionality which used to
be provided by packages O1 and O2 and is now provided by package N. P
depends on "N | O1, N | O2"; N conflicts with both O1 and O2 (and
provides O2, but that's not relevant here as P's dependency on O2 is
versioned). Another package, Q, depends on P and O1. O2 has been
removed from unstable, so britney is trying to remove it from testing.
britney1's approach here is very simple:
a) store uninstallable package count
b) try removing package
c) recalculate uninstallable count; compare to the earlier count
d) if no new uninstallability has occurred, the package may be removed
britney2 tries to avoid the relatively expensive step of recalculating
installability regularly by being cleverer:
a) store a list of the r-depends of the to-be-removed package
b) for each package in that list, note whether its installabile status
has changed
c) for each package in the list where the status has changed
- iterate its r-depends checking their installability, repeating
step c until no status changes are found
d) if no new uninstallability has occurred, the package may be removed
In our example scenario, britney2 removes O2 and checks the status of
its r-dependency, P; P can use N to satisfy the alternative dependencies
which involve O1 and O2, so it is still installable and the removal is
declared possible despite it rendering Q uninstallable.
My patch augments step a by storing a recursive list of r-depends for
later consideration; in this case this would mean that Q is checked in
step b and discovered to be uninstallable.
The patch does add some overhead to each migration operation as more
packages need to be checked but if this is a problem then it could be
mitigated by making the recursive check conditional on the operation in
question being a removal rather than upgrade or addition of a package.
Comments / questions / cluesticks welcome.
Regards,
Adam
diff -adNru /srv/release.debian.org/britney/code/b2/britney.py ../b2/britney.py
--- /srv/release.debian.org/britney/code/b2/britney.py 2011-02-11 08:06:24.000000000 +0000
+++ ../b2/britney.py 2011-02-20 16:40:28.000000000 +0000
@@ -2034,9 +2034,19 @@
# save the old binary for undo
undo['binaries'][p] = binaries[parch][0][binary]
# all the reverse dependencies are affected by the change
- for j in binaries[parch][0][binary][RDEPENDS]:
- key = (j, parch)
- if key not in affected: affected.append(key)
+ seen = [ binary ]
+ rev_deps = [ binaries[parch][0][binary][RDEPENDS] ]
+ while len(rev_deps) > 0:
+ rev_deps = rev_deps[0]
+ for j in rev_deps:
+ key = (j, parch)
+ if key not in affected: affected.append(key)
+ # Store a temporary copy of rev_deps so we can use it after
+ # calculating the next iteration
+ _rev_deps = rev_deps
+ rev_deps = [ binaries[parch][0][x][RDEPENDS] for x in rev_deps \
+ if x in binaries[parch][0] and x not in seen ]
+ seen.extend(_rev_deps)
# remove the provided virtual packages
for j in binaries[parch][0][binary][PROVIDES]:
key = j + "/" + parch
Reply to: