bug#36508: [DRAFT PATCH] Stable allocation of uids, by keeping a historical mapping.

[Maxime Devos <maximedevos@telenet.be>]

[-- Attachment #1.1.1: Type: text/plain, Size: 1564 bytes --]

Hi,

The attached patch maintains a historical mapping from user names to 
UIDs/GIDs (even when those users are removed from the user accounts), to 
solve <https://issues.guix.gnu.org/36508>, as proposed by Mark H Weaver 
in <https://issues.guix.gnu.org/36508#10>.

(The proposed garbage collector is not included, however.)

As I proposed in <https://issues.guix.gnu.org/36508#14>, the information 
of this mapping is kept in a special 'user'.  However, I didn't 
implement the same for groups (raises some questions about atomicity -- 
/etc/passwd and /etc/groups are separate files).

I didn't completely follow that proposal though, since:

 > https://issues.guix.gnu.org/36508#16:
 > Problem is that things like GDM would still propose those old accounts
 > (unless maybe their password is uninitialized, I’m not sure; but it’s
 > still hacky.)

, though that could perhaps be solved by adjusting GDM appropriately.

"make check TESTS=tests/accounts.scm" passes, but otherwise the patch is 
rather untested (hence, 'DRAFT') -- the new functionality will need a 
few additional tests in tests/account.scm, to avoid introducing bugs in 
the handling of /etc/passwd.

On second thought, a separate /etc/previous-uids (as proposed in
<https://issues.guix.gnu.org/36508#16> by Ludovic Courtès)
might be better (there are atomicity issues anyway, due to /etc/passwd 
and /etc/groups being separate files, and losing the historical mapping
is relatively harmless and seems unlikely to happen in practice).

Greetings,
Maxime

[-- Attachment #1.1.2: 0001-DRAFT-Stable-allocation-of-uids.patch --]
[-- Type: text/x-patch, Size: 16012 bytes --]

From 1e0eb78fb7ae1a7b6c40e364d88b0b33945ef7c1 Mon Sep 17 00:00:00 2001
From: Maxime Devos <maximedevos@telenet.be>
Date: Sun, 18 Sep 2022 14:18:10 +0200
Subject: [PATCH] DRAFT: Stable allocation of uids

---
 gnu/build/accounts.scm | 186 +++++++++++++++++++++++++++++++++++------
 tests/accounts.scm     |  14 +++-
 2 files changed, 173 insertions(+), 27 deletions(-)

diff --git a/gnu/build/accounts.scm b/gnu/build/accounts.scm
index 1247fc640c..5e04e9f526 100644
--- a/gnu/build/accounts.scm
+++ b/gnu/build/accounts.scm
@@ -1,5 +1,6 @@
 ;;; GNU Guix --- Functional package management for GNU
 ;;; Copyright © 2019, 2021 Ludovic Courtès <ludo@gnu.org>
+;;; Copyright © 2022 Maxime Devos <maximedevos@telenet.be>
 ;;;
 ;;; This file is part of GNU Guix.
 ;;;
@@ -17,9 +18,11 @@
 ;;; along with GNU Guix.  If not, see <http://www.gnu.org/licenses/>.
 
 (define-module (gnu build accounts)
+  #:use-module (guix base64)
   #:use-module (guix records)
   #:use-module (guix combinators)
   #:use-module (gnu system accounts)
+  #:use-module (rnrs bytevectors)
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-19)
@@ -72,10 +75,16 @@ (define-module (gnu build accounts)
 ;;; <shadow.h>, <pwd.h>, and <grp.h> routines, as well as a subset of the
 ;;; functionality of the Shadow command-line tools.  It can parse and write
 ;;; /etc/passwd, /etc/shadow, and /etc/group.  It can also take care of UID
-;;; and GID allocation in a way similar to what 'useradd' does.
+;;; and GID allocation, in a different way than 'useradd' does.
 ;;;
-;;; The benefit is twofold: less code is involved, and the ID allocation
-;;; strategy and state preservation is made explicit.
+;;; The benefit is threefold: less code is involved, the ID allocation
+;;; strategy and state preservation is made explicit and it avoids
+;;; allocating IDs that were in the past allocated for some user user
+;;; and removed but still present somewhere in the file system.
+;;; Additionally, when such an user is re-added, Guix will use the same
+;;; ID again
+;;;
+;;; TODO: do the same 'keep old IDs' for groups as well.
 ;;;
 ;;; Code:
 
@@ -288,6 +297,85 @@ (define read-shadow
 (define read-group
   (database-reader "/etc/group" string->group-entry))
 
+(define (decode-guix-deleted-users encoded)
+  (alist->vhash (call-with-input-string
+                    (utf8->string (base64-decode encoded))
+                  read)))
+(define (encode-guix-deleted-users deleted-username->id)
+  (define (less this that)
+    (< (cdr this) (cdr that)))
+  (base64-encode
+   (string->utf8
+    (object->string
+     ;; Sort the mappings, to avoid hashing causing non-determinism.
+     (sort
+      (vhash-fold (lambda (username value accumulated)
+                    (unless (string? username)
+                      (error "username should be a string"))
+                    (unless (integer? value)
+                      (error "uid should be a string"))
+                    (cons (cons username value) accumulated))
+                  '()
+                  deleted-username->id)
+      less)))))
+
+(define (passwd-deleted passwd)
+  (define guix-deleted-users
+    ((lookup-procedure passwd password-entry-name)
+     "guix-deleted-users"))
+  (if guix-deleted-users
+      (decode-guix-deleted-users (password-entry-real-name guix-deleted-users))
+      vlist-null))
+
+(define (adjust-deleted-users current-passwd-entries new-passwd-entries
+                              current-deleted)
+  (define lookup-by-name/new
+    (lookup-procedure new-passwd-entries password-entry-name))
+  (define lookup-by-id/new
+    (lookup-procedure new-passwd-entries password-entry-uid))
+  (define lookup-by-id/old
+    (lookup-procedure current-passwd-entries password-entry-uid))
+  ;; Remove all usernames of 'current-deleted' that were allocated
+  ;; (in new-passwd-entries) and similarily, remove all IDs that were
+  ;; allocated.
+  (define current-deleted/filtered
+    (vhash-fold (lambda (username id accumulated)
+                  (if (or (lookup-by-name/new username)
+                          (lookup-by-id/new id))
+                      accumulated
+                      (vhash-cons username id accumulated)))
+                vlist-null
+                current-deleted))
+  (define (id-reused? username id)
+    ;; Was the ID used by a different username than USERNAME in
+    ;; CURRENT-PASSWD-ENTRIES?
+    (let ((old-password-entry (lookup-by-id/old id)))
+      (and old-password-entry (string=? (password-entry-name old-password-entry)
+                                        username))))
+  ;; Add usernames that are present in CURRENT-PASSWD-ENTRIES but
+  ;; not in NEW-PASSWD-ENTRIES, but only if the ID wasn't reused
+  ;; for some other user name.
+  (define new-deleted
+    (fold (lambda (username id accumulated)
+            (if (and (not (lookup-by-name/new username))
+                     (not (id-reused? username id)))
+                (vhash-cons username id accumulated)
+                accumulated))
+          current-deleted/filtered
+          current-passwd-entries))
+
+  (define (adjust password-entry* accumulated)
+    (cons (if (string=? (password-entry-name password-entry*) "guix-deleted-users")
+              (password-entry
+               (inherit password-entry*)
+               (real-name (encode-guix-deleted-users new-deleted)))
+              password-entry*)
+          accumulated))
+  ;; The 'reverse' is to preserve the order -- in theory, this should be
+  ;; unnecessary, but reverting the ordering of the entries in /etc/passwd
+  ;; after each reconfiguration would be surprising.
+  (fold adjust '() (reverse new-passwd-entries)))
+
 \f
 ;;;
 ;;; Building databases.
@@ -321,7 +409,8 @@ (define (user-id? id)
 
 (define* (allocate-id assignment #:key system?)
   "Return two values: a newly allocated ID, and an updated <allocation> record
-based on ASSIGNMENT.  If SYSTEM? is true, return a system ID."
+based on ASSIGNMENT.  If SYSTEM? is true, return a system ID.  This requires
+that no ID is allocated yet."
   (define next
     ;; Return the next available ID, looping if necessary.
     (if system?
@@ -441,20 +530,28 @@ (define previous-entry
           gids
           groups)))
 
-(define* (allocate-passwd users groups #:optional (current-passwd '()))
+(define* (allocate-passwd users groups #:optional (current-passwd '())
+                          (deleted-username->id vlist-null))
   "Return a list of password entries for USERS, a list of <user-account>.
 Take GIDs from GROUPS, a list of group entries.  Reuse UIDs from
-CURRENT-PASSWD, a list of password entries, when possible; otherwise allocate
-new UIDs."
+CURRENT-PASSWD, a list of password entries, or deleted-username->id,
+a vhash of usernames that were deleted in the previous /etc/passwd to IDs,
+when possible; otherwise allocate new UIDs."
   (define uids
-    (reserve-ids (reserve-ids (allocation)
-                              (map password-entry-uid current-passwd))
-                 (filter-map user-account-uid users)
-                 #:skip? #f))
-
-  (define previous-entry
+    (reserve-ids ; <-- TODO: is #:skip? #false needed here as well?
+     (reserve-ids (reserve-ids (allocation)
+                               (map password-entry-uid current-passwd))
+                  (filter-map user-account-uid users)
+                  #:skip? #f)
+     (vhash-fold (lambda (username id accumulated)
+                   (cons id accumulated)) '() deleted-username->id)))
+
+  (define previous-undeleted-entry
     (lookup-procedure current-passwd password-entry-name))
 
+  (define (previous-deleted-entry username)
+    (and=> (vhash-assoc username deleted-username->id) cdr))
+
   (define (group-id name)
     (or (any (lambda (entry)
                (and (string=? (group-entry-name entry) name)
@@ -471,17 +568,28 @@ (define (group-id name)
                   (directory    (user-account-home-directory user))
                   (shell        (user-account-shell user))
                   (system?      (user-account-system? user)))
-              (let*-values (((previous)
-                             (previous-entry name))
+              (let*-values (((previous-undeleted)
+                             (previous-undeleted-entry name))
+                            ((previous-deleted)
+                             (previous-deleted-entry name))
                             ((allocation id)
                              (cond
                               ((number? requested-id)
                                (values (reserve-ids allocation
                                                     (list requested-id))
                                        requested-id))
-                              (previous
+                              (previous-undeleted
                                (values allocation
-                                       (password-entry-uid previous)))
+                                       (password-entry-uid previous-undeleted)))
+                              ((and previous-deleted
+                                    (not (allocated? allocation previous-deleted)))
+                               ;; This deleted user might still have some files
+                               ;; in the file system, reuse the old id such
+                               ;; that it remains correct, unless some other
+                               ;; user has choosen that id.
+                               (values (reserve-ids allocation
+                                                    (list previous-deleted))
+                                       previous-deleted))
                               (else
                                (allocate-id allocation
                                             #:system? system?)))))
@@ -494,9 +602,10 @@ (define (group-id name)
                                ;; Users might change their name to something
                                ;; other than what the sysadmin chose, with
                                ;; 'chfn'.  Thus consider it "stateful".
-                               (real-name (if (and previous (not system?))
-                                              (password-entry-real-name previous)
-                                              real-name))
+                               (real-name
+                                (if (and previous-undeleted (not system?))
+                                    (password-entry-real-name previous-undeleted)
+                                    real-name))
 
                                ;; Do not reuse the shell of PREVIOUS since (1)
                                ;; that could lead to confusion, and (2) the
@@ -556,6 +665,25 @@ (define* (user+group-databases users groups
 entries, and the list of shadow entries corresponding to USERS and GROUPS.
 Preserve stateful bits from CURRENT-PASSWD, CURRENT-GROUPS, and
 CURRENT-SHADOW: UIDs, GIDs, passwords, user shells, etc."
+  (define users*
+    (if ((lookup-procedure users user-account-name)
+         "guix-deleted-users")
+        users
+        (append users
+                (list (user-account
+                       (name "guix-deleted-users")
+                       (group "guix-deleted-users")
+                       (home-directory "/var/empty")
+                       (system? #true))))))
+  (define groups*
+    (if ((lookup-procedure groups user-group-name)
+         "guix-deleted-users")
+        groups
+        (append groups
+                (list (user-group
+                       (name "guix-deleted-users")
+                       (system? #true))))))
+
   (define members
     ;; Map group name to user names.
     (fold (lambda (user members)
@@ -563,16 +691,24 @@ (define members
                   members
                   (user-account-supplementary-groups user)))
           vlist-null
-          users))
+          users*))
+
+  (define current-deleted (passwd-deleted current-passwd))
 
   (define group-entries
-    (allocate-groups groups members current-groups))
+    (allocate-groups groups* members current-groups))
 
   (define passwd-entries
-    (allocate-passwd users group-entries current-passwd))
+    (allocate-passwd users* group-entries current-passwd
+                     (passwd-deleted current-passwd)))
 
   (define shadow-entries
-    (passwd->shadow users passwd-entries current-shadow
+    (passwd->shadow users* passwd-entries current-shadow
                     #:current-time current-time))
 
-  (values group-entries passwd-entries shadow-entries))
+  ;; TODO: adjust new 'deleted'
+  (values group-entries (adjust-deleted-users
+                         current-passwd
+                         passwd-entries
+                         current-deleted)
+          shadow-entries))
diff --git a/tests/accounts.scm b/tests/accounts.scm
index 78136390bb..4e29bfe285 100644
--- a/tests/accounts.scm
+++ b/tests/accounts.scm
@@ -1,5 +1,6 @@
 ;;; GNU Guix --- Functional package management for GNU
 ;;; Copyright © 2019 Ludovic Courtès <ludo@gnu.org>
+;;; Copyright © 2022 Maxime Devos <maximedevos@telenet.be>
 ;;;
 ;;; This file is part of GNU Guix.
 ;;;
@@ -272,7 +273,9 @@ (define allocate-passwd (@@ (gnu build accounts) allocate-passwd))
                            (members '("bob")))
               (group-entry (name "b") (gid (+ 1 %id-min))
                            (members '("alice")))
-              (group-entry (name "s") (gid %system-id-max)))
+              (group-entry (name "s") (gid %system-id-max))
+              (group-entry (name "guix-deleted-users")
+                           (gid (- %system-id-max 1))))
         (list (password-entry (name "alice") (real-name "Alice")
                               (uid %id-min) (gid %id-min)
                               (directory "/a"))
@@ -281,12 +284,19 @@ (define allocate-passwd (@@ (gnu build accounts) allocate-passwd))
                               (directory "/b"))
               (password-entry (name "nobody")
                               (uid 65534) (gid %system-id-max)
+                              (directory "/var/empty"))
+              (password-entry (name "guix-deleted-users")
+                              ;; empty list, start without deleted users
+                              (real-name "KCk=")
+                              (uid %system-id-max)
+                              (gid (- %system-id-max 1)) ; XXX: why not %system-id-max?  Bug or OK?
                               (directory "/var/empty")))
         (list (shadow-entry (name "alice") (last-change 100)
                             (password (crypt "initial pass" "$6$")))
               (shadow-entry (name "bob") (last-change 50)
                             (password (crypt "foo" "$6$")))
-              (shadow-entry (name "nobody") (last-change 100))))
+              (shadow-entry (name "nobody") (last-change 100))
+              (shadow-entry (name "guix-deleted-users") (last-change 100))))
   (call-with-values
       (lambda ()
         (user+group-databases (list (user-account

base-commit: 17f646aeba39f0d297f6c911d83b3bd9e88a227b
prerequisite-patch-id: 1f7c45cf2480f4e6f1e9563660e1b73a8682425e
prerequisite-patch-id: 0caac311875ee39cb48573657ebb960e90da6dfb
prerequisite-patch-id: 418285493d89ebf102175902d9b09a0174e88190
prerequisite-patch-id: 3c39eb839d9d3ff3fca6cd98621a5d5c411b7af4
prerequisite-patch-id: 8d5662e874c469f5ee496ef5181cf2d0a30ad1d8
prerequisite-patch-id: 26513c3b3b86963df718ee41d14a25d1cc6a8f3f
prerequisite-patch-id: 2b2497e2edec0afc48ebadd6f09f0c661c466127
prerequisite-patch-id: 2712efb97bf33985fd0658e4dd8e936dc08be5fe
prerequisite-patch-id: 9d2409b480a8bff0fef029b4b095922d4957e06f
prerequisite-patch-id: 51a32abca3efec1ba67ead59b8694c5ea3129ad3
prerequisite-patch-id: 7d55e3b39eb8803f058857d4412796b3f5dc0856
prerequisite-patch-id: 9092927761a340c07a99f5f3ed314a6add04cdee
prerequisite-patch-id: eafeeba1e6816dee3f8df671631bbeb5c373237a
-- 
2.37.3


[-- Attachment #1.1.3: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 929 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 236 bytes --]