Merge pull request #12461 from Werkov/fix-job-ordering

Refactor job ordering implementation (and fix cycle detection)

3 files changed, 106 insertions, 104 deletions

diff --git a/src/core/job.c b/src/core/job.c
index c69ccc221d..90c829d08d 100644
--- a/src/core/job.c
+++ b/src/core/job.c
@@ -477,36 +477,14 @@ static bool job_is_runnable(Job *j) {
         if (j->type == JOB_NOP)
                 return true;
 
-        if (IN_SET(j->type, JOB_START, JOB_VERIFY_ACTIVE, JOB_RELOAD)) {
-                /* Immediate result is that the job is or might be
-                 * started. In this case let's wait for the
-                 * dependencies, regardless whether they are
-                 * starting or stopping something. */
-
-                HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i)
-                        if (other->job)
-                                return false;
-        }
-
-        /* Also, if something else is being stopped and we should
-         * change state after it, then let's wait. */
+        HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i)
+                if (other->job && job_compare(j, other->job, UNIT_AFTER) > 0)
+                        return false;
 
         HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_BEFORE], i)
-                if (other->job &&
-                    IN_SET(other->job->type, JOB_STOP, JOB_RESTART))
+                if (other->job && job_compare(j, other->job, UNIT_BEFORE) > 0)
                         return false;
 
-        /* This means that for a service a and a service b where b
-         * shall be started after a:
-         *
-         *  start a + start b → 1st step start a, 2nd step start b
-         *  start a + stop b  → 1st step stop b,  2nd step start a
-         *  stop a  + start b → 1st step stop a,  2nd step start b
-         *  stop a  + stop b  → 1st step stop b,  2nd step stop a
-         *
-         *  This has the side effect that restarts are properly
-         *  synchronized too. */
-
         return true;
 }
 
@@ -1455,46 +1433,14 @@ bool job_may_gc(Job *j) {
         if (j->type == JOB_NOP)
                 return false;
 
-        /* If a job is ordered after ours, and is to be started, then it needs to wait for us, regardless if we stop or
-         * start, hence let's not GC in that case. */
-        HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_BEFORE], i) {
-                if (!other->job)
-                        continue;
-
-                if (other->job->ignore_order)
-                        continue;
-
-                if (IN_SET(other->job->type, JOB_START, JOB_VERIFY_ACTIVE, JOB_RELOAD))
+        /* The logic is inverse to job_is_runnable, we cannot GC as long as we block any job. */
+        HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_BEFORE], i)
+                if (other->job && job_compare(j, other->job, UNIT_BEFORE) < 0)
                         return false;
-        }
-
-        /* If we are going down, but something else is ordered After= us, then it needs to wait for us */
-        if (IN_SET(j->type, JOB_STOP, JOB_RESTART))
-                HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i) {
-                        if (!other->job)
-                                continue;
-
-                        if (other->job->ignore_order)
-                                continue;
 
+        HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i)
+                if (other->job && job_compare(j, other->job, UNIT_AFTER) < 0)
                         return false;
-                }
-
-        /* The logic above is kinda the inverse of the job_is_runnable() logic. Specifically, if the job "we" is
-         * ordered before the job "other":
-         *
-         *  we start + other start → stay
-         *  we start + other stop  → gc
-         *  we stop  + other start → stay
-         *  we stop  + other stop  → gc
-         *
-         * "we" are ordered after "other":
-         *
-         *  we start + other start → gc
-         *  we start + other stop  → gc
-         *  we stop  + other start → stay
-         *  we stop  + other stop  → stay
-         */
 
         return true;
 }
@@ -1512,7 +1458,7 @@ void job_add_to_gc_queue(Job *j) {
         j->in_gc_queue = true;
 }
 
-static int job_compare(Job * const *a, Job * const *b) {
+static int job_compare_id(Job * const *a, Job * const *b) {
         return CMP((*a)->id, (*b)->id);
 }
 
@@ -1521,7 +1467,7 @@ static size_t sort_job_list(Job **list, size_t n) {
         size_t a, b;
 
         /* Order by numeric IDs */
-        typesafe_qsort(list, n, job_compare);
+        typesafe_qsort(list, n, job_compare_id);
 
         /* Filter out duplicates */
         for (a = 0, b = 0; a < n; a++) {
@@ -1552,23 +1498,21 @@ int job_get_before(Job *j, Job*** ret) {
                 return 0;
         }
 
-        if (IN_SET(j->type, JOB_START, JOB_VERIFY_ACTIVE, JOB_RELOAD)) {
-
-                HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i) {
-                        if (!other->job)
-                                continue;
+        HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i) {
+                if (!other->job)
+                        continue;
+                if (job_compare(j, other->job, UNIT_AFTER) <= 0)
+                        continue;
 
-                        if (!GREEDY_REALLOC(list, n_allocated, n+1))
-                                return -ENOMEM;
-                        list[n++] = other->job;
-                }
+                if (!GREEDY_REALLOC(list, n_allocated, n+1))
+                        return -ENOMEM;
+                list[n++] = other->job;
         }
 
         HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_BEFORE], i) {
                 if (!other->job)
                         continue;
-
-                if (!IN_SET(other->job->type, JOB_STOP, JOB_RESTART))
+                if (job_compare(j, other->job, UNIT_BEFORE) <= 0)
                         continue;
 
                 if (!GREEDY_REALLOC(list, n_allocated, n+1))
@@ -1602,7 +1546,7 @@ int job_get_after(Job *j, Job*** ret) {
                 if (other->job->ignore_order)
                         continue;
 
-                if (!IN_SET(other->job->type, JOB_START, JOB_VERIFY_ACTIVE, JOB_RELOAD))
+                if (job_compare(j, other->job, UNIT_BEFORE) >= 0)
                         continue;
 
                 if (!GREEDY_REALLOC(list, n_allocated, n+1))
@@ -1610,19 +1554,20 @@ int job_get_after(Job *j, Job*** ret) {
                 list[n++] = other->job;
         }
 
-        if (IN_SET(j->type, JOB_STOP, JOB_RESTART)) {
 
-                HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i) {
-                        if (!other->job)
-                                continue;
+        HASHMAP_FOREACH_KEY(v, other, j->unit->dependencies[UNIT_AFTER], i) {
+                if (!other->job)
+                        continue;
+
+                if (other->job->ignore_order)
+                        continue;
 
-                        if (other->job->ignore_order)
-                                continue;
+                if (job_compare(j, other->job, UNIT_AFTER) >= 0)
+                        continue;
 
-                        if (!GREEDY_REALLOC(list, n_allocated, n+1))
-                                return -ENOMEM;
-                        list[n++] = other->job;
-                }
+                if (!GREEDY_REALLOC(list, n_allocated, n+1))
+                        return -ENOMEM;
+                list[n++] = other->job;
         }
 
         n = sort_job_list(list, n);
@@ -1692,3 +1637,45 @@ const char* job_type_to_access_method(JobType t) {
         else
                 return "reload";
 }
+
+/*
+ * assume_dep   assumed dependency between units (a is before/after b)
+ *
+ * Returns
+ *    0         jobs are independent,
+ *   >0         a should run after b,
+ *   <0         a should run before b,
+ *
+ * The logic means that for a service a and a service b where b.After=a:
+ *
+ *  start a + start b → 1st step start a, 2nd step start b
+ *  start a + stop b  → 1st step stop b,  2nd step start a
+ *  stop a  + start b → 1st step stop a,  2nd step start b
+ *  stop a  + stop b  → 1st step stop b,  2nd step stop a
+ *
+ *  This has the side effect that restarts are properly
+ *  synchronized too.
+ */
+int job_compare(Job *a, Job *b, UnitDependency assume_dep) {
+        assert(a->type < _JOB_TYPE_MAX_IN_TRANSACTION);
+        assert(b->type < _JOB_TYPE_MAX_IN_TRANSACTION);
+        assert(IN_SET(assume_dep, UNIT_AFTER, UNIT_BEFORE));
+
+        /* Trivial cases first */
+        if (a->type == JOB_NOP || b->type == JOB_NOP)
+                return 0;
+
+        if (a->ignore_order || b->ignore_order)
+                return 0;
+
+        if (assume_dep == UNIT_AFTER)
+                return -job_compare(b, a, UNIT_BEFORE);
+
+        /* Let's make it simple, JOB_STOP goes always first (in case both ua and ub stop,
+         * then ub's stop goes first anyway).
+         * JOB_RESTART is JOB_STOP in disguise (before it is patched to JOB_START). */
+        if (IN_SET(b->type, JOB_STOP, JOB_RESTART))
+                return 1;
+        else
+                return -1;
+}
diff --git a/src/core/job.h b/src/core/job.h
index 0f15cbf821..9c79c873d1 100644
--- a/src/core/job.h
+++ b/src/core/job.h
@@ -237,3 +237,5 @@ const char* job_result_to_string(JobResult t) _const_;
 JobResult job_result_from_string(const char *s) _pure_;
 
 const char* job_type_to_access_method(JobType t);
+
+int job_compare(Job *a, Job *b, UnitDependency assume_dep);
diff --git a/src/core/transaction.c b/src/core/transaction.c
index 3b6b240d36..d1bf2e64c9 100644
--- a/src/core/transaction.c
+++ b/src/core/transaction.c
@@ -353,6 +353,11 @@ static int transaction_verify_order_one(Transaction *tr, Job *j, Job *from, unsi
         Unit *u;
         void *v;
         int r;
+        static const UnitDependency directions[] = {
+                UNIT_BEFORE,
+                UNIT_AFTER,
+        };
+        size_t d;
 
         assert(tr);
         assert(j);
@@ -441,25 +446,33 @@ static int transaction_verify_order_one(Transaction *tr, Job *j, Job *from, unsi
         j->marker = from ? from : j;
         j->generation = generation;
 
-        /* We assume that the dependencies are bidirectional, and
-         * hence can ignore UNIT_AFTER */
-        HASHMAP_FOREACH_KEY(v, u, j->unit->dependencies[UNIT_BEFORE], i) {
-                Job *o;
-
-                /* Is there a job for this unit? */
-                o = hashmap_get(tr->jobs, u);
-                if (!o) {
-                        /* Ok, there is no job for this in the
-                         * transaction, but maybe there is already one
-                         * running? */
-                        o = u->job;
-                        if (!o)
+        /* Actual ordering of jobs depends on the unit ordering dependency and job types. We need to traverse
+         * the graph over 'before' edges in the actual job execution order. We traverse over both unit
+         * ordering dependencies and we test with job_compare() whether it is the 'before' edge in the job
+         * execution ordering. */
+        for (d = 0; d < ELEMENTSOF(directions); d++) {
+                HASHMAP_FOREACH_KEY(v, u, j->unit->dependencies[directions[d]], i) {
+                        Job *o;
+
+                        /* Is there a job for this unit? */
+                        o = hashmap_get(tr->jobs, u);
+                        if (!o) {
+                                /* Ok, there is no job for this in the
+                                 * transaction, but maybe there is already one
+                                 * running? */
+                                o = u->job;
+                                if (!o)
+                                        continue;
+                        }
+
+                        /* Cut traversing if the job j is not really *before* o. */
+                        if (job_compare(j, o, directions[d]) >= 0)
                                 continue;
-                }
 
-                r = transaction_verify_order_one(tr, o, j, generation, e);
-                if (r < 0)
-                        return r;
+                        r = transaction_verify_order_one(tr, o, j, generation, e);
+                        if (r < 0)
+                                return r;
+                }
         }
 
         /* Ok, let's backtrack, and remember that this entry is not on