Let a held snapshot keep the states of its time, not all that came after

An app's snapshots formed a chain, each holding the next, and what the
app's lists let go while a snapshot was the newest went with it. So one
snapshot held for long held every later one and every node and text let
go since: a surface holding the snapshot of 20,000 items while their
notes were set again grew the node from 6.5 MB to 696 MB in 30 s, 3.4 KB
an update, without end.

A snapshot reads only what was made before it. Snapshots are now
numbered (their epoch, given to the lists' copies and so to each node
and text made after), and the ones held are linked under a register
they share. What the app lets go while a snapshot is its newest goes
with it, as before; when that one goes, what the newest older one still
held may read (made before its epoch) goes to it, and the rest back to
the system at once. The links move under a spin the register keeps; what
is freed is freed outside it. The same held snapshot now costs its
states once: 6.6 MB to 10.6 MB, flat after the notes diverge.

test-module's snapshot_held holds a snapshot through 40,000 events and
snapshots: none of the second 20,000's allocations stays (0 B; with the
chain's keeping, it fails). The kept-snapshots tests read eight held in
random order, and the module tests pass under AddressSanitizer too.

1 files changed, 37 insertions, 3 deletions

diff --git a/core/module-list.c b/core/module-list.c
index f32fd05..861798e 100644
--- a/core/module-list.c
+++ b/core/module-list.c
@@ -67,7 +67,7 @@ struct PureList {
     unsigned char *journal;
     size_t journal_size, journal_capacity;
     uint64_t id, version; /* which list, and a number every change moves on */
-    uint64_t shares;      /* copies made so far: a node or text made before the last one is shared */
+    uint64_t shares;      /* the last copy's epoch: a node or text made before it is shared */
     PureRetired *retired; /* where shared nodes and texts go when the list lets them go */
     Node *spare[2];       /* inner nodes and leaves let go that no copy read, kept for the next ones (linked by first) */
     unsigned spares[2];
@@ -195,6 +195,36 @@ void pure_retired_free(PureRetired *retired) {
     *retired = (PureRetired){0};
 }
 
+static uint64_t made_at(const Retired *r) {
+    return r->text ? ((const uint64_t *)r->pointer)[-1] : ((const Node *)r->pointer)->made;
+}
+
+/* Room for more entries in retired; false when memory runs out. */
+static bool retired_room(PureRetired *retired, size_t more) {
+    if (retired->count + more <= retired->capacity) return true;
+    size_t capacity = 2 * retired->capacity > retired->count + more ? 2 * retired->capacity : retired->count + more;
+    Retired *grown = realloc(retired->entries, capacity * sizeof(*grown));
+    if (!grown) return false;
+    retired->entries = grown;
+    retired->capacity = capacity;
+    return true;
+}
+
+void pure_retired_pass(PureRetired *from, uint64_t epoch, PureRetired *kept, PureRetired *gone) {
+    Retired *entries = from->entries;
+    size_t keeping = 0;
+    for (size_t i = 0; kept && i < from->count; ++i) keeping += made_at(&entries[i]) < epoch;
+    bool room = (!keeping || retired_room(kept, keeping)) &&
+                (!gone || keeping == from->count || retired_room(gone, from->count - keeping));
+    for (size_t i = 0; i < from->count; ++i) {
+        PureRetired *to = kept && made_at(&entries[i]) < epoch ? kept : gone;
+        if (room && to) ((Retired *)to->entries)[to->count++] = entries[i];
+        /* else kept for good rather than freed while read (memory ran out) */
+    }
+    free(entries);
+    *from = (PureRetired){0};
+}
+
 static Node *new_node(PureList *list, bool leaf) {
     Node *node = list->spare[leaf];
     if (node) {
@@ -570,16 +600,20 @@ void pure_list_clear(PureList *list) {
 
 size_t pure_list_count(const PureList *list) { return list->count; }
 
-PureList *pure_list_share(PureList *list, PureRetired *retired) {
+PureList *pure_list_share(PureList *list, PureRetired *retired, uint64_t epoch) {
     PureList *copy = malloc(sizeof(*copy));
     if (!copy) return NULL;
     *copy = (PureList){.layout = list->layout, .root = list->root, .count = list->count, .bytes = list->bytes,
                        .id = list->id, .version = list->version, .refs = 1, .copy = true};
     list->retired = retired;
-    ++list->shares;
+    list->shares = epoch > list->shares ? epoch : list->shares + 1;
     return copy;
 }
 
+void pure_list_mark(PureList *list, uint64_t epoch) {
+    if (list->retired && epoch > list->shares) list->shares = epoch;
+}
+
 void pure_list_hold(PureList *copy) { __atomic_add_fetch(&copy->refs, 1, __ATOMIC_RELAXED); }
 
 bool pure_list_current(const PureList *copy, const PureList *list) {