Enhancement #2904

Wrong signal-event order under certain circumstance

Added by Stefano Fancello almost 7 years ago. Updated over 6 years ago.

Status:CLOSEDStart date:
Priority:NormalDue 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:

Associated revisions

Revision fd516c3e
Added by Stefano Fancello almost 7 years ago

Use tsort algorithm for sorting -update events after packages installation. Refs #2904

Revision 31bda416
Added by Davide Principi almost 7 years ago

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

Also available in: Atom PDF