From 23e3c5880901f5d744f88d1c5cd5397b5640868d Mon Sep 17 00:00:00 2001
From: Lennart Poettering <lennart@poettering.net>
Date: Thu, 3 Jun 2010 03:00:47 +0200
Subject: manager: when we sweep the tree when looking for ordering cycles,
 remember and reuse if we already decided a tree was loop free, to improve
 speed drastically

---
 src/manager.c | 34 ++++++++++++++++++++++------------
 1 file changed, 22 insertions(+), 12 deletions(-)

(limited to 'src')

diff --git a/src/manager.c b/src/manager.c
index 933dd5064f..a71150d0a9 100644
--- a/src/manager.c
+++ b/src/manager.c
@@ -964,20 +964,25 @@ static int transaction_verify_order_one(Manager *m, Job *j, Job *from, unsigned
         /* Does a recursive sweep through the ordering graph, looking
          * for a cycle. If we find cycle we try to break it. */
 
-        /* Did we find a cycle? */
-        if (j->marker && j->generation == generation) {
+        /* Have we seen this before? */
+        if (j->generation == generation) {
                 Job *k;
 
-                /* So, we already have been here. We have a
-                 * cycle. Let's try to break it. We go backwards in
-                 * our path and try to find a suitable job to
-                 * remove. We use the marker to find our way back,
-                 * since smart how we are we stored our way back in
-                 * there. */
+                /* If the marker is NULL we have been here already and
+                 * decided the job was loop-free from here. Hence
+                 * shortcut things and return right-away. */
+                if (!j->marker)
+                        return 0;
 
+                /* So, the marker is not NULL and we already have been
+                 * here. We have a cycle. Let's try to break it. We go
+                 * backwards in our path and try to find a suitable
+                 * job to remove. We use the marker to find our way
+                 * back, since smart how we are we stored our way back
+                 * in there. */
                 log_debug("Found ordering cycle on %s/%s", j->unit->meta.id, job_type_to_string(j->type));
 
-                for (k = from; k; k = (k->generation == generation ? k->marker : NULL)) {
+                for (k = from; k; k = ((k->generation == generation && k->marker != k) ? k->marker : NULL)) {
 
                         log_debug("Walked on cycle path to %s/%s", k->unit->meta.id, job_type_to_string(k->type));
 
@@ -1002,8 +1007,10 @@ static int transaction_verify_order_one(Manager *m, Job *j, Job *from, unsigned
         }
 
         /* Make the marker point to where we come from, so that we can
-         * find our way backwards if we want to break a cycle */
-        j->marker = from;
+         * find our way backwards if we want to break a cycle. We use
+         * a special marker for the beginning: we point to
+         * ourselves. */
+        j->marker = from ? from : j;
         j->generation = generation;
 
         /* We assume that the the dependencies are bidirectional, and
@@ -1035,6 +1042,7 @@ static int transaction_verify_order(Manager *m, unsigned *generation) {
         Job *j;
         int r;
         Iterator i;
+        unsigned g;
 
         assert(m);
         assert(generation);
@@ -1042,8 +1050,10 @@ static int transaction_verify_order(Manager *m, unsigned *generation) {
         /* Check if the ordering graph is cyclic. If it is, try to fix
          * that up by dropping one of the jobs. */
 
+        g = (*generation)++;
+
         HASHMAP_FOREACH(j, m->transaction_jobs, i)
-                if ((r = transaction_verify_order_one(m, j, NULL, (*generation)++)) < 0)
+                if ((r = transaction_verify_order_one(m, j, NULL, g)) < 0)
                         return r;
 
         return 0;
-- 
cgit v1.2.3-54-g00ecf