Enhancement #2904
Wrong signal-event order under certain circumstance
Status: | CLOSED | Start date: | ||
---|---|---|---|---|
Priority: | Normal | Due date: | ||
Assignee: | - | % Done: | 100% | |
Category: | nethserver-yum | |||
Target version: | v6.5 | |||
Resolution: | NEEDINFO: | No |
Description
nethserver_events.py yum plugin (nethserver-yum package) launch package-name-update signal-event when packages are installed.
If multiple packages are installed, the order of the events matter, because some events may rely on services to be configured. For example, if a package needs to create a mysql database, nethserver-mysql-update signal-event has to be launched before the installation event of this package.
The nethserver_events.py algorithm take the list of packages (that have an -update event) and build the ordered list of signal-event to launch putting required packages signal-event before the package itself
def read_package_list(): """ Query RPM db for any nethserver* package and return the list of package names, preserving the dependency order. RPM 'Require' tags are parsed. """ packages = [] ts = rpm.TransactionSet() mi = ts.dbMatch() for h in mi: if not has_update_event(h['name']): continue for dep in h[rpm.RPMTAG_REQUIRENAME]: if not has_update_event(dep): continue try: # insert deps before the package name packages.insert(packages.index(h['name']), dep) except ValueError: packages.append(dep) if not h['name'] in packages: packages.append(h['name']) # Reduce the package list preserving the element order: return list_unique(packages)
The algorithm fails under certain cirmstances:
if we have the following list of package-> dep1, dep2, dep3...:
A B -> E C D -> C,A E -> D,C,A
At each iteration, dependencies are putted in the final list before the first occurrence of the package
At 1st iteration, resulting list will be the following because A doesn't have dependencies
A B C D E
At 2nd iteration, E will be putted before B (and also D,C and A that are dependencies of E):
A E D C A B C D E
At 3rd nothing changes because C has no deps, but at 4th C and A are putted before D:
A E C A D C A B C D E
At 5th D,C,A are putted before E but they are putted before the 1st occurrence of E:
A D C A E C A D C A B C D E
And here is the problem, order of D dependencies is defined in 4th iteration, but now they are putted in the top of the list (before E) in an order that isn't defined anywhere.
After list_uniq, the new list will be
A D C E B
D dependencies aren't satisfied Proposed solution:
- in rpm, dependencies order is defined with a tsort function https://en.wikipedia.org/wiki/Tsort
here https://github.com/tengu/py-tsort a python tsort impelentation (look at description: "Useful for dependency resolution")
Associated revisions
Use tsort algorithm for sorting -update events after packages installation. Refs #2904
Ensure only a tree of deps exists. Refs #2904
Add a fake "$root" package, then remove it.
History
#1 Updated by Stefano Fancello almost 7 years ago
- Status changed from NEW to TRIAGED
- % Done changed from 0 to 20
#2 Updated by Stefano Fancello almost 7 years ago
- Status changed from TRIAGED to ON_DEV
- Assignee set to Stefano Fancello
- % Done changed from 20 to 30
#3 Updated by Stefano Fancello almost 7 years ago
here the patch for proposed solution with some extra DEBUG lines
diff --git a/usr/lib/yum-plugins/nethserver_events.py b/usr/lib/yum-plugins/nethserver_events.py index 947900b..36e8fa8 100644 --- a/usr/lib/yum-plugins/nethserver_events.py +++ b/usr/lib/yum-plugins/nethserver_events.py @@ -64,9 +64,11 @@ def read_package_list(): are parsed. """ - packages = [] ts = rpm.TransactionSet() mi = ts.dbMatch() + packages = [] + touples = [] + for h in mi: if not has_update_event(h['name']): continue @@ -74,18 +76,70 @@ def read_package_list(): for dep in h[rpm.RPMTAG_REQUIRENAME]: if not has_update_event(dep): continue - - try: - # insert deps before the package name - packages.insert(packages.index(h['name']), dep) - except ValueError: - packages.append(dep) - - if not h['name'] in packages: - packages.append(h['name']) - - # Reduce the package list preserving the element order: - return list_unique(packages) + print "DEBUG:\t" + dep + " is a dependency of " + h['name'] + touples.append([dep,h['name']]) + + packages = topological_sort(touples) + + print "DEBUG: events: " + for p in packages: + print "DEBUG: \t" + p + return packages + +class GraphError(Exception): + pass + +def topological_sort(edges): + """topologically sort vertices in edges. + edges: list of pairs of vertices. Edges must form a DAG. + If the graph has a cycle, then GraphError is raised. + returns: topologically sorted list of vertices. + see http://en.wikipedia.org/wiki/Topological_sorting + + thanks to https://github.com/tengu/py-tsort + """ + # resulting list + L=[] + + # maintain forward and backward edge maps in parallel. + st,ts={},{} + + def prune(s,t): + del st[s][t] + del ts[t][s] + + def add(s,t): + try: + st.setdefault(s,{})[t]=1 + except Exception, e: + raise RuntimeError(e, (s,t)) + ts.setdefault(t,{})[s]=1 + + for s,t in edges: + add(s,t) + + # frontier + S=set(st.keys()).difference(ts.keys()) + + while S: + s=S.pop() + L.append(s) + for t in st.get(s,{}).keys(): + prune(s,t) + if not ts[t]: # new frontier + S.add(t) + + if filter(None, st.values()): # we have a cycle. report the cycle. + def traverse(vs, seen): + for s in vs: + if s in seen: + raise GraphError('contains cycle: ', seen) + seen.append(s) # xx use ordered set.. + traverse(st[s].keys(), seen) + traverse(st.keys(), list()) + assert False, 'should not reach..' + + return L def list_unique(l): s = set()
patching your /usr/lib/yum-plugins/nethserver_events.py before installing any nethserver package/group, event order will be computed using tsort and will be also printed to stdout
#4 Updated by Stefano Fancello almost 7 years ago
- Status changed from ON_DEV to MODIFIED
- Assignee deleted (
Stefano Fancello) - % Done changed from 30 to 60
commit fd516c3e12236e1888e47996b180778f2e073051
Test case:- Update nethserver-yum
- install packages with a lot of dependencies (try "yum groupinstall GROUPS", where GROUPS are one or more groups from yum grouplist)
- check /var/log/messages for FAIL(s) or ERROR(s). An event that needs another before should fail if the order is wrong. Also make sure that every expected event is executed.
#5 Updated by Stefano Fancello almost 7 years ago
- Status changed from MODIFIED to ON_QA
- % Done changed from 60 to 70
In nethserver-testing:nethserver-yum-1.3.3-1.0gitfd516c3e.ns6.noarch.rpm
nethserver-yum-1.3.3-2.0git31bda416.ns6.noarch.rpm
#6 Updated by Davide Principi almost 7 years ago
- Assignee set to Davide Principi
#7 Updated by Davide Principi almost 7 years ago
- Assignee deleted (
Davide Principi)
Tested an everything-install: no errors occurred.
But the nethserver-release-update
event was missing. Added a patch that transform a forest of deps in a single tree. Verify again.
#8 Updated by Giacomo Sanchietti over 6 years ago
- Assignee set to Giacomo Sanchietti
#9 Updated by Giacomo Sanchietti over 6 years ago
- Status changed from ON_QA to VERIFIED
- Assignee deleted (
Giacomo Sanchietti) - % Done changed from 70 to 90
Tested on multiple installations and no problems reported.
Marking as VERIFIED:
#10 Updated by Davide Principi over 6 years ago
- Status changed from VERIFIED to CLOSED
- % Done changed from 90 to 100
In nethserver-updates:
nethserver-yum-1.3.4-1.ns6.noarch.rpm