[PATCH 1/3] s6-rc-update.c: add #define constants for bitflags

[PATCH 1/3] s6-rc-update.c: add #define constants for bitflags

[Adam Joseph]

The documentation for s6-rc-update says "Live upgrading a service
database is not easy, and no fully automated system can get it right
in all cases."  This is certainly true!  I reviewed the source code
in order to be sure I fully understood the algorithm.

I found it much easier to do this after replacing all of the
"Conversions and transitions" bitflags with descriptive #define
identifiers.  For example this routine, which had no comment, was
quite difficult to understand:

  if (oldstate[i] & 1 && (oldstate[i] & 4 || !(oldstate[i] & 8)))
    oldstate[i] |= 34 ;
  else oldstate[i] &= 221 ;

Here's what these two lines of code do: if a service was up in the
old state and either shall be restarted or else converts to a
non-singleton bundle, set the two flags 'included in the down
transition' and 'wanted down or restarted'; otherwise clear those
two flags.

When the integers above are replaced by symbolic identifiers, the
code now conveys exactly what it does:

  if (oldstate[i] & OLDSTATE_WAS_UP &&
      (oldstate[i] & OLDSTATE_RESTART ||
       !(oldstate[i] & OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE)
       ))
    oldstate[i] |=
      OLDSTATE_WANT_DOWN_OR_RESTART |
      OLDSTATE_INCLUDE_IN_DOWN_TRANSITION;
  else
    oldstate[i] &=
      ~(OLDSTATE_WANT_DOWN_OR_RESTART |
        OLDSTATE_INCLUDE_IN_DOWN_TRANSITION);

This commit has been written to do nothing other than add the
descriptive identifiers and replace integers with their
corresponding identifier-combinations.  Therefore it should be
straightforward to locally verify the correctness of each change in
this commit.

Signed-off-by: Adam Joseph <adam@westernsemico.com>
---
 src/s6-rc/s6-rc-update.c | 167 +++++++++++++++++++++++----------------
 1 file changed, 100 insertions(+), 67 deletions(-)

diff --git a/src/s6-rc/s6-rc-update.c b/src/s6-rc/s6-rc-update.c
index 617cdfb..c1074de 100644
--- a/src/s6-rc/s6-rc-update.c
+++ b/src/s6-rc/s6-rc-update.c
@@ -48,26 +48,24 @@ static unsigned int verbosity = 1 ;
 
  /* Conversions and transitions */
 
-
- /*
-  oldstate flags:
-     1 -> is up
-     2 -> wanted down
-     4 -> restart
-     8 -> converts to atomic or singleton
-    16 -> has a new name
-    32 -> wanted down after closure
-    64 -> appears in convfile
-
-  newstate flags:
-     1 -> is up (converted from old up)
-     2 -> wanted up
-     4 -> is a bijective conversion target
-     8 -> is a conversion target
-    16 -> changed names
-    32 -> is up after closure (i.e. includes new deps)
-   128 -> depends on a new service, has to be restarted
- */
+#define OLDSTATE_WAS_UP 1
+#define OLDSTATE_INCLUDE_IN_DOWN_TRANSITION 2
+#define OLDSTATE_RESTART 4
+#define OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE 8
+#define OLDSTATE_HAS_NEW_NAME 16
+#define OLDSTATE_WANT_DOWN_OR_RESTART 32
+#define OLDSTATE_WANT_DOWN_OR_RESTART_BITNO 5
+#define OLDSTATE_APPEARS_IN_CONVFILE 64
+
+#define NEWSTATE_WAS_UP 1
+#define NEWSTATE_INCLUDE_IN_UP_TRANSITION 2
+#define NEWSTATE_IS_BIJECTIVE_CONVERSION_TARGET 4
+#define NEWSTATE_IS_CONVERSION_TARGET 8
+#define NEWSTATE_CHANGED_NAMES 16
+#define NEWSTATE_WANT_UP_AFTER_CLOSURE_BITNO 5
+#define NEWSTATE_WANT_UP_AFTER_CLOSURE 32
+#define NEWSTATE_DEPENDS_ON_A_NEW_SERVICE_BITNO 7
+#define NEWSTATE_DEPENDS_ON_A_NEW_SERVICE 128U
 
 static inline void parse_line (stralloc *sa, char const *s, size_t slen, unsigned int *newnames, unsigned char *oldstate, cdb const *oldc, s6rc_db_t const *olddb)
 {
@@ -96,22 +94,22 @@ static inline void parse_line (stralloc *sa, char const *s, size_t slen, unsigne
     if (data.len != 4) strerr_dief5x(5, "identifier ", sa->s + base + slen, " does not represent an atomic service in ", live, "/compiled") ;
     uint32_unpack_big(data.s, &x) ;
     if (x >= oldn) strerr_dief3x(4, "invalid database in ", live, "/compiled") ;
-    if (oldstate[x] & 64)
+    if (oldstate[x] & OLDSTATE_APPEARS_IN_CONVFILE)
       strerr_dief3x(6, "service ", olddb->string + olddb->services[x].name, " appears more than once in conversion file") ;
-    oldstate[x] |= 64 ;
+    oldstate[x] |= OLDSTATE_APPEARS_IN_CONVFILE ;
     cur = base + slen + strlen(sa->s + base + slen) + 1 ;
     if (n >= 2 && !strcmp(sa->s + cur, "->"))
     {
       size_t newnamelen = strlen(sa->s + cur + 3) ;
       memcpy(sa->s + sa->len, sa->s + cur + 3, newnamelen + 1) ;
-      newnames[x] = sa->len ; oldstate[x] |= 16 ;
+      newnames[x] = sa->len ; oldstate[x] |= OLDSTATE_HAS_NEW_NAME ;
       sa->len += newnamelen + 1 ;
       cur += newnamelen + 4 ;
       n -= 2 ;
     }
     while (n--)
     {
-      if (!strcmp(sa->s + cur, "restart")) oldstate[x] |= 4 ;
+      if (!strcmp(sa->s + cur, "restart")) oldstate[x] |= OLDSTATE_RESTART ;
       else
         strerr_dief2x(100, "unknown keyword in conversion file: ", sa->s + cur) ;
       cur += strlen(sa->s + cur) + 1 ;
@@ -161,37 +159,39 @@ static inline void fill_convtable_and_flags (unsigned char *conversion_table, un
 
   while (i--)
   {
-    char const *newname = oldstate[i] & 16 ? namedata + oldindex[i] : olddb->string + olddb->services[i].name ;
+    char const *newname = oldstate[i] & OLDSTATE_HAS_NEW_NAME ? namedata + oldindex[i] : olddb->string + olddb->services[i].name ;
     cdb_data data ;
     int r = cdb_find(newc, &data, newname, strlen(newname)) ;
     if (r < 0) strerr_dief3x(111, "invalid cdb in ", newfn, "/resolve.cdb") ;
     if (!r)
     {
-      if (oldstate[i] & 16)
+      if (oldstate[i] & OLDSTATE_HAS_NEW_NAME)
         strerr_dief4x(4, "bad conversion file: new service ", newname, " is undefined in database ", newfn) ;
-      oldstate[i] |= 34 ; /* disappeared */
+      oldstate[i] |= OLDSTATE_WANT_DOWN_OR_RESTART | OLDSTATE_INCLUDE_IN_DOWN_TRANSITION ; /* disappeared */
       continue ;
     }
     if (data.len & 3) strerr_dief3x(4, "invalid resolve database in ", newfn, "/resolve.cdb") ;
     if (data.len >> 2 > newn)
       strerr_dief3x(4, "invalid resolve database in ", newfn, "/resolve.cdb") ;
-    if (data.len == 4) oldstate[i] |= 8 ;
+    if (data.len == 4) oldstate[i] |= OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE ;
     while (data.len)
     {
       uint32_t x ;
       uint32_unpack_big(data.s, &x) ; data.s += 4 ; data.len -= 4 ;
       if (x >= newn)
         strerr_dief3x(4, "invalid resolve database in ", newfn, "/resolve.cdb") ;
-      if (newstate[x] & 8)
+      if (newstate[x] & NEWSTATE_IS_CONVERSION_TARGET)
         strerr_diefu4x(6, "convert database: new service ", newdb->string + newdb->services[x].name, " is a target for more than one conversion, including old service ", olddb->string + olddb->services[i].name) ;
-      newstate[x] |= 8 ;
+
+      newstate[x] |= NEWSTATE_IS_CONVERSION_TARGET ;
       invimage[x] = i ;
-      if (oldstate[i] & 16) newstate[x] |= 16 ;
+      if (oldstate[i] & OLDSTATE_HAS_NEW_NAME) newstate[x] |= NEWSTATE_CHANGED_NAMES ;
       bitarray_set(conversion_table + i * bitarray_div8(newn), x) ;
-      if (oldstate[i] & 8)
+      if (oldstate[i] & OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE)
       {
-        newstate[x] |= 4 ;
-        if ((i < olddb->nlong) != (x < newdb->nlong)) oldstate[i] |= 4 ;
+        newstate[x] |= NEWSTATE_IS_BIJECTIVE_CONVERSION_TARGET ;
+
+        if ((i < olddb->nlong) != (x < newdb->nlong)) oldstate[i] |= OLDSTATE_RESTART ;
       }
     }
   }
@@ -222,7 +222,11 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
   {
     int done = 1 ;
     unsigned int i = newn ;
-    while (i--) newstate[i] &= 28 ;
+    while (i--)
+      newstate[i] &=
+        ( NEWSTATE_IS_BIJECTIVE_CONVERSION_TARGET |
+          NEWSTATE_IS_CONVERSION_TARGET |
+          NEWSTATE_CHANGED_NAMES);
 
    /*
      If an old service needs to restart, mark it wanted down, as well
@@ -232,11 +236,22 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
     i = oldn ;
     while (i--)
     {
-      if (oldstate[i] & 1 && (oldstate[i] & 4 || !(oldstate[i] & 8)))
-        oldstate[i] |= 34 ;
-      else oldstate[i] &= 221 ;
+      if (oldstate[i] & OLDSTATE_WAS_UP &&
+          (oldstate[i] & OLDSTATE_RESTART ||
+           !(oldstate[i] & OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE)
+           ))
+        oldstate[i] |=
+          OLDSTATE_WANT_DOWN_OR_RESTART |
+          OLDSTATE_INCLUDE_IN_DOWN_TRANSITION;
+      else
+        oldstate[i] &=
+          ~(OLDSTATE_WANT_DOWN_OR_RESTART |
+            OLDSTATE_INCLUDE_IN_DOWN_TRANSITION);
     }
-    s6rc_graph_closure(olddb, oldstate, 5, 0) ;
+    s6rc_graph_closure(olddb,
+                       oldstate,
+                       OLDSTATE_WANT_DOWN_OR_RESTART_BITNO,
+                       0) ;
 
 
    /*
@@ -247,12 +262,16 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
    */
 
     i = oldn ;
-    while (i--) if (oldstate[i] & 1)
-    {
-      unsigned int j = newn ;
-      while (j--) if (bitarray_peek(conversion_table + i * newm, j))
-        newstate[j] |= (oldstate[i] & 32) ? 2 : 33 ;
-    }
+    while (i--)
+      if (oldstate[i] & OLDSTATE_WAS_UP) {
+        unsigned int j = newn ;
+        while (j--)
+          if (bitarray_peek(conversion_table + i * newm, j))
+            newstate[j] |=
+              (oldstate[i] & OLDSTATE_WANT_DOWN_OR_RESTART)
+              ? NEWSTATE_INCLUDE_IN_UP_TRANSITION
+              : (NEWSTATE_WAS_UP | NEWSTATE_WANT_UP_AFTER_CLOSURE) ;
+      }
 
 
    /*
@@ -261,17 +280,23 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
      restart and loop until there are no new dependencies.
    */
 
-    s6rc_graph_closure(newdb, newstate, 5, 1) ;
+    s6rc_graph_closure(newdb, newstate, NEWSTATE_WANT_UP_AFTER_CLOSURE_BITNO, 1) ;
     i = newn ;
-    while (i--) if ((newstate[i] & 33) == 32)
-    {
-      done = 0 ;
-      newstate[i] |= 128U ;
-    }
+    while (i--)
+      if ( (newstate[i] & NEWSTATE_WANT_UP_AFTER_CLOSURE) &&
+          !(newstate[i] & NEWSTATE_WAS_UP)) {
+        done = 0 ;
+        newstate[i] |= NEWSTATE_DEPENDS_ON_A_NEW_SERVICE ;
+      }
     if (done) break ;
-    s6rc_graph_closure(newdb, newstate, 7, 0) ;
+
+    s6rc_graph_closure(newdb, newstate, NEWSTATE_DEPENDS_ON_A_NEW_SERVICE_BITNO, 0) ;
+
     i = newn ;
-    while (i--) if ((newstate[i] & 129U) == 129U) oldstate[invimage[i]] |= 4 ;
+    while (i--)
+      if ((newstate[i] & NEWSTATE_WAS_UP) &&
+          (newstate[i] & NEWSTATE_DEPENDS_ON_A_NEW_SERVICE))
+        oldstate[invimage[i]] |= OLDSTATE_RESTART ;
   }
 }
 
@@ -291,9 +316,9 @@ static inline void rollback_servicedirs (char const *newlive, unsigned char cons
     memcpy(newfn, newlive, newllen) ;
     memcpy(newfn + newllen, "/servicedirs/", 13) ;
     memcpy(newfn + newllen + 13, newdb->string + newdb->services[i].name, newnamelen + 1) ;
-    if (newstate[i] & 1)
+    if (newstate[i] & NEWSTATE_WAS_UP)
     {
-      char const *oldname = newstate[i] & 8 ? olddb->string + olddb->services[invimage[i]].name : newdb->string + newdb->services[i].name ;
+      char const *oldname = newstate[i] & NEWSTATE_IS_CONVERSION_TARGET ? olddb->string + olddb->services[invimage[i]].name : newdb->string + newdb->services[i].name ;
       size_t oldnamelen = strlen(oldname) ;
       char oldfn[livelen + 23 + oldnamelen] ;
       memcpy(oldfn, live, livelen) ;
@@ -327,7 +352,7 @@ static inline void make_new_livedir (unsigned char const *oldstate, s6rc_db_t co
     if (r < 0) strerr_diefu2sys(111, "readlink ", sdlink) ;
     if (r >= SKALIBS_PATH_MAX - 1) strerr_dief3x(100, "target for ", sdlink, " is too long") ;
     sdtarget[r] = 0 ;
-    while (i--) tmpstate[i] = newstate[i] & 1 ;
+    while (i--) tmpstate[i] = newstate[i] & NEWSTATE_WAS_UP ;
     if (!s6rc_livedir_create(sa, live, PROG, sdtarget, prefix, newcompiled, tmpstate, newdb->nlong + newdb->nshort, &dirlen))
       strerr_diefu1sys(111, "create new livedir") ;
   }
@@ -345,9 +370,9 @@ static inline void make_new_livedir (unsigned char const *oldstate, s6rc_db_t co
     memcpy(newfn + newclen + 13, newdb->string + newdb->services[i].name, newnamelen + 1) ;
     sa->len = sdlen ;
     if (!stralloc_cats(sa, newdb->string + newdb->services[i].name) || !stralloc_0(sa)) goto rollback ;
-    if (newstate[i] & 1)
+    if (newstate[i] & NEWSTATE_WAS_UP)
     {
-      char const *oldname = newstate[i] & 8 ? olddb->string + olddb->services[invimage[i]].name : newdb->string + newdb->services[i].name ;
+      char const *oldname = newstate[i] & NEWSTATE_IS_CONVERSION_TARGET ? olddb->string + olddb->services[invimage[i]].name : newdb->string + newdb->services[i].name ;
       size_t oldnamelen = strlen(oldname) ;
       char oldfn[livelen + 14 + oldnamelen] ;
       memcpy(oldfn, live, livelen) ;
@@ -381,7 +406,11 @@ static inline void make_new_livedir (unsigned char const *oldstate, s6rc_db_t co
  /* scandir cleanup, then old livedir cleanup */
   i = olddb->nlong ;
   while (i--)
-    s6rc_servicedir_unsupervise(sa->s, prefix, olddb->string + olddb->services[i].name, (oldstate[i] & 33) == 1) ;
+    s6rc_servicedir_unsupervise(sa->s,
+                                prefix,
+                                olddb->string + olddb->services[i].name,
+                                (oldstate[i] & OLDSTATE_WAS_UP) &&
+                                !(oldstate[i] & OLDSTATE_WANT_DOWN_OR_RESTART)) ;
   rm_rf_in_tmp(sa, 0) ;
   sa->len = 0 ;
   return ;
@@ -405,7 +434,7 @@ static inline int delete_unused_pipes (s6_fdholder_t *a, s6rc_db_t const *olddb,
 {
   unsigned int i = olddb->nlong ;
   while (i--)
-    if (!(oldstate[i] & 8) && olddb->services[i].x.longrun.nproducers)
+    if (!(oldstate[i] & OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE) && olddb->services[i].x.longrun.nproducers)
     {
       size_t len = strlen(olddb->string + olddb->services[i].name) ;
       char pipename[len + 13] ;
@@ -426,7 +455,9 @@ static inline int rename_pipes (s6_fdholder_t *a, s6rc_db_t const *olddb, s6rc_d
   unsigned int i = newdb->nlong ;
   while (i--)
   {
-    if ((newstate[i] & 20) == 20 && newdb->services[i].x.longrun.nproducers)
+    if ((newstate[i] & NEWSTATE_CHANGED_NAMES) &&
+        (newstate[i] & NEWSTATE_IS_BIJECTIVE_CONVERSION_TARGET) &&
+        newdb->services[i].x.longrun.nproducers)
     {
       int fd ;
       size_t oldlen = strlen(olddb->string + olddb->services[invimage[i]].name) ;
@@ -472,7 +503,8 @@ static inline int create_new_pipes (s6_fdholder_t *a, s6rc_db_t const *newdb, un
   nano1.nano = 1 ;
   while (i--)
   {
-    if (!(newstate[i] & 4) && newdb->services[i].x.longrun.nproducers)
+    if (!(newstate[i] & NEWSTATE_IS_BIJECTIVE_CONVERSION_TARGET) &&
+        newdb->services[i].x.longrun.nproducers)
     {
       int p[2] ;
       size_t len = strlen(newdb->string + newdb->services[i].name) ;
@@ -516,7 +548,7 @@ static inline void update_fdholder (s6rc_db_t const *olddb, unsigned char const
 {
   s6_fdholder_t a = S6_FDHOLDER_ZERO ;
   char fnsocket[livelen + sizeof("/servicedirs/" S6RC_FDHOLDER "/s")] ;
-  if (!(newstate[1] & 1)) return ;
+  if (!(newstate[1] & NEWSTATE_WAS_UP)) return ;
   memcpy(fnsocket, live, livelen) ;
   memcpy(fnsocket + livelen, "/servicedirs/" S6RC_FDHOLDER "/s", sizeof("/servicedirs/" S6RC_FDHOLDER "/s")) ;
   if (!s6_fdholder_start_g(&a, fnsocket, deadline)) goto hammer ;
@@ -692,7 +724,7 @@ int main (int argc, char const *const *argv, char const *const *envp)
         if (rr < oldn) strerr_diefu2x(4, "read valid db in ", dbfn) ;
       }
       r = oldn ;
-      while (r--) oldstate[r] &= 1 ;
+      while (r--) oldstate[r] &= OLDSTATE_WAS_UP ;
       memset(newstate, 0, newn) ;
       r = newn ;
       while (r--) invimage[r] = olddb.nlong + olddb.nshort ;
@@ -735,8 +767,9 @@ int main (int argc, char const *const *argv, char const *const *envp)
         newargv[m++] = "-d" ;
         newargv[m++] = "--" ;
         newargv[m++] = "change" ;
-        while (i--) if (oldstate[i] & 2)
-          newargv[m++] = olddb.string + olddb.services[i].name ;
+        while (i--)
+          if (oldstate[i] & OLDSTATE_INCLUDE_IN_DOWN_TRANSITION)
+            newargv[m++] = olddb.string + olddb.services[i].name ;
         newargv[m++] = 0 ;
         if (verbosity >= 2)
           strerr_warni1x("stopping services in the old database") ;
@@ -819,7 +852,7 @@ int main (int argc, char const *const *argv, char const *const *envp)
         newargv[m++] = "-u" ;
         newargv[m++] = "--" ;
         newargv[m++] = "change" ;
-        while (i--) if (newstate[i] & 2)
+        while (i--) if (newstate[i] & NEWSTATE_INCLUDE_IN_UP_TRANSITION)
           newargv[m++] = newdb.string + newdb.services[i].name ;
         newargv[m++] = 0 ;
         if (verbosity >= 2)
-- 
2.41.0

[PATCH 2/3] s6-rc-update.c: rewrite O(n^2) loop as O(n) complexity

[Adam Joseph]

Prior to this commit, s6-rc-update had a loop with the following
comment:

  This part runs in O(oldn*newn). There are no syscalls in the loop,
  so it should still be negligible unless you have 10k services.

The loop does the following:

   for each old service which was already up
     for each new service
       if the old service converts to the new service,
         set some new service flags based on old service flags

The loop is O(n^2) due to the nested iteration.  We can rewrite this
with a single iteration by making use of the invimage[] array, which
maps from new services to old services:

   for each new service
     if *ANY* old service converts to the new service,
       set some new service flags based on that old service's flags

This takes advantage of the fact that invimage is an injective
(partial) function.

Signed-off-by: Adam Joseph <adam@westernsemico.com>
---
 src/s6-rc/s6-rc-update.c | 15 ++++++---------
 1 file changed, 6 insertions(+), 9 deletions(-)

diff --git a/src/s6-rc/s6-rc-update.c b/src/s6-rc/s6-rc-update.c
index c1074de..e0726a2 100644
--- a/src/s6-rc/s6-rc-update.c
+++ b/src/s6-rc/s6-rc-update.c
@@ -257,20 +257,17 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
    /*
       Convert the old state to the new state: if an old service is up,
       the new service will be either up or wanted up.
-      This part runs in O(oldn*newn). There are no syscalls in the loop,
-      so it should still be negligible unless you have 10k services.
    */
 
-    i = oldn ;
+    i = newn;
     while (i--)
-      if (oldstate[i] & OLDSTATE_WAS_UP) {
-        unsigned int j = newn ;
-        while (j--)
-          if (bitarray_peek(conversion_table + i * newm, j))
-            newstate[j] |=
-              (oldstate[i] & OLDSTATE_WANT_DOWN_OR_RESTART)
+      if (newstate[i] & NEWSTATE_IS_CONVERSION_TARGET) {
+        if (oldstate[invimage[i]] & OLDSTATE_WAS_UP) {
+            newstate[i] |=
+              (oldstate[invimage[i]] & OLDSTATE_WANT_DOWN_OR_RESTART)
               ? NEWSTATE_INCLUDE_IN_UP_TRANSITION
               : (NEWSTATE_WAS_UP | NEWSTATE_WANT_UP_AFTER_CLOSURE) ;
+        }
       }
 
 
-- 
2.41.0

[PATCH 3/3] [WIP] s6-rc-update.c: add additional comments

[Adam Joseph]

This commit adds additional explanatory comments for parts of
s6-rc-update.c that did not seem immediately obvious to me.

It is probably not appropriate to apply this commit verbatim in its current
form.  Feel free to pick changes from it selectively.

Signed-off-by: Adam Joseph <adam@westernsemico.com>
---
 src/s6-rc/s6-rc-update.c | 43 ++++++++++++++++++++++++++++++++++------
 1 file changed, 37 insertions(+), 6 deletions(-)

diff --git a/src/s6-rc/s6-rc-update.c b/src/s6-rc/s6-rc-update.c
index e0726a2..240a256 100644
--- a/src/s6-rc/s6-rc-update.c
+++ b/src/s6-rc/s6-rc-update.c
@@ -51,6 +51,7 @@ static unsigned int verbosity = 1 ;
 #define OLDSTATE_WAS_UP 1
 #define OLDSTATE_INCLUDE_IN_DOWN_TRANSITION 2
 #define OLDSTATE_RESTART 4
+/* or, equivalently, "converts to a multi-element bundle" */
 #define OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE 8
 #define OLDSTATE_HAS_NEW_NAME 16
 #define OLDSTATE_WANT_DOWN_OR_RESTART 32
@@ -60,6 +61,11 @@ static unsigned int verbosity = 1 ;
 #define NEWSTATE_WAS_UP 1
 #define NEWSTATE_INCLUDE_IN_UP_TRANSITION 2
 #define NEWSTATE_IS_BIJECTIVE_CONVERSION_TARGET 4
+/*
+  this flag is set for:
+  - anything which is the target of a rename in the convfile
+  - the contents of bundles which are the targets of renames
+*/
 #define NEWSTATE_IS_CONVERSION_TARGET 8
 #define NEWSTATE_CHANGED_NAMES 16
 #define NEWSTATE_WANT_UP_AFTER_CLOSURE_BITNO 5
@@ -183,6 +189,12 @@ static inline void fill_convtable_and_flags (unsigned char *conversion_table, un
       if (newstate[x] & NEWSTATE_IS_CONVERSION_TARGET)
         strerr_diefu4x(6, "convert database: new service ", newdb->string + newdb->services[x].name, " is a target for more than one conversion, including old service ", olddb->string + olddb->services[i].name) ;
 
+      /*
+        Note: the following will fail if you have a singleton bundle
+        and try to rename both the bundle and the thing it contains
+        in the same s6-rc-update invocation.  Parts of this loop
+        should probably be skipped for singleton bundles.
+      */
       newstate[x] |= NEWSTATE_IS_CONVERSION_TARGET ;
       invimage[x] = i ;
       if (oldstate[i] & OLDSTATE_HAS_NEW_NAME) newstate[x] |= NEWSTATE_CHANGED_NAMES ;
@@ -191,6 +203,8 @@ static inline void fill_convtable_and_flags (unsigned char *conversion_table, un
       {
         newstate[x] |= NEWSTATE_IS_BIJECTIVE_CONVERSION_TARGET ;
 
+        /* The following line forces a restart when a oneshot
+           converts to a longrun or vice versa. */
         if ((i < olddb->nlong) != (x < newdb->nlong)) oldstate[i] |= OLDSTATE_RESTART ;
       }
     }
@@ -229,8 +243,9 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
           NEWSTATE_CHANGED_NAMES);
 
    /*
-     If an old service needs to restart, mark it wanted down, as well
-     as everything that depends on it.
+     If an old service was up and either needs to restart or
+     converts to an atomic or converts to a singleton, then: mark it
+     wanted down, as well as everything that depends on it.
    */
 
     i = oldn ;
@@ -238,6 +253,11 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
     {
       if (oldstate[i] & OLDSTATE_WAS_UP &&
           (oldstate[i] & OLDSTATE_RESTART ||
+           /*
+             The following clause deals with the situation where
+             you convert an atomic or singleton bundle into a
+             multi-element bundle
+           */
            !(oldstate[i] & OLDSTATE_CONVERTS_TO_ATOMIC_OR_SINGLETON_BUNDLE)
            ))
         oldstate[i] |=
@@ -255,7 +275,7 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
 
 
    /*
-      Convert the old state to the new state: if an old service is up,
+      Convert the old state to the new state: if an old service was up,
       the new service will be either up or wanted up.
    */
 
@@ -277,6 +297,7 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
      restart and loop until there are no new dependencies.
    */
 
+    /* For every service wanted up, propagate that marking to its dependencies. */
     s6rc_graph_closure(newdb, newstate, NEWSTATE_WANT_UP_AFTER_CLOSURE_BITNO, 1) ;
     i = newn ;
     while (i--)
@@ -287,8 +308,12 @@ static void compute_transitions (char const *convfile, unsigned char *oldstate,
       }
     if (done) break ;
 
+    /* For every service marked "depends on a new service", mark
+       services which depend upon the same way */
     s6rc_graph_closure(newdb, newstate, NEWSTATE_DEPENDS_ON_A_NEW_SERVICE_BITNO, 0) ;
 
+    /* For every service which acquires a new dependency (one which
+       did not previously exist), force it to restart. */
     i = newn ;
     while (i--)
       if ((newstate[i] & NEWSTATE_WAS_UP) &&
@@ -401,13 +426,19 @@ static inline void make_new_livedir (unsigned char const *oldstate, s6rc_db_t co
   if (verbosity >= 2) strerr_warni1x("successfully switched to new database") ;
 
  /* scandir cleanup, then old livedir cleanup */
+
   i = olddb->nlong ;
-  while (i--)
+  while (i--) {
+    /* If an old service survived without needing a restart, do not
+       kill its supervisor */
+    unsigned int keepsupervisor =
+      (oldstate[i] & OLDSTATE_WAS_UP) &&
+      !(oldstate[i] & OLDSTATE_WANT_DOWN_OR_RESTART);
     s6rc_servicedir_unsupervise(sa->s,
                                 prefix,
                                 olddb->string + olddb->services[i].name,
-                                (oldstate[i] & OLDSTATE_WAS_UP) &&
-                                !(oldstate[i] & OLDSTATE_WANT_DOWN_OR_RESTART)) ;
+                                keepsupervisor);
+  }
   rm_rf_in_tmp(sa, 0) ;
   sa->len = 0 ;
   return ;
-- 
2.41.0

Re: [PATCH 2/3] s6-rc-update.c: rewrite O(n^2) loop as O(n) complexity

[Adam Joseph]

Quoting Adam Joseph (2023-09-25 17:44:17)
> The loop is O(n^2) due to the nested iteration.  We can rewrite this
> with a single iteration by making use of the invimage[] array, which
> maps from new services to old services:
> 
>    for each new service
>      if *ANY* old service converts to the new service,
>        set some new service flags based on that old service's flags
> 
> This takes advantage of the fact that invimage is an injective
> (partial) function.

As discussed on IRC, this commit touches the dependency computation routines,
which are quite delicate and (at this point) battle-tested; tampering with them
probably isn't worth the mostly-theoretical performance benefit.

I wrote this commit mainly because it seemed like there was an easy way to do
this in O(n) time, and the fact that it hadn't been done that way must mean that
I had overlooked something important.  If anybody sees an obvious mistake in
this commit, please do let me know -- it's a sign that I misunderstood
something.  Otherwise there's no need to apply this patch.

  - a

Re: [PATCH 3/3] [WIP] s6-rc-update.c: add additional comments

[Adam Joseph]

Quoting Adam Joseph (2023-09-25 17:44:18)
> +      /*
> +        Note: the following will fail if you have a singleton bundle
> +        and try to rename both the bundle and the thing it contains
> +        in the same s6-rc-update invocation.  Parts of this loop
> +        should probably be skipped for singleton bundles.
> +      */

I'm working on a minimal example of this issue and a fix, but it might be a few
days before I have something worth submitting.