summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLennart Poettering <lennart@poettering.net>2010-06-03 03:00:47 +0200
committerLennart Poettering <lennart@poettering.net>2010-06-03 03:00:47 +0200
commit23e3c5880901f5d744f88d1c5cd5397b5640868d (patch)
treea8b727660f99d25ef15cd818517e6ec57d341dc4
parent2279955bb56859e76702bd9c40a0b875bd6c6bb8 (diff)
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
-rw-r--r--src/manager.c34
1 files changed, 22 insertions, 12 deletions
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;