Finish yesterday's note.

1 files changed, 130 insertions, 15 deletions

diff --git a/notes/260822-release3.md b/notes/260822-release3.md
index d4f0741..03ee8dc 100644
--- a/notes/260822-release3.md
+++ b/notes/260822-release3.md
@@ -9,18 +9,26 @@ It's especially difficult if you don't want to allocate auxiliary
 memory, which is crucial if you're trying to free memory to the OS
 because it's signaling memory pressure or declining an allocation.
 
-Here's a method that sacrifices CPU time, in exchange for locating
-unused spans of memory from a free-list without extra allocation.
+Below are two ways to achieve this.  The first is almost trivial in
+both complexity and CPU cost.  The second is highly complex and may
+incur significant CPU cost, but should still be quite reasonable to
+employ if there is a need for aggressively releasing memory back to
+the kernel due to pressure or because the application just finished
+some extremely memory-intensive subroutine and wishes to release it
+back to the rest of the system.
 
 
 ## Locking
 
+Before going into the actual algorithms that will achieve our goal,
+let's consider their thread safety.
+
 Meta Alloc uses a lock-free Treiber stack for the free-list, which
 only works when threads contend for the top node of the linked list,
 trying to push and pop in parallel.
 
 Any subroutine that wants to walk through the whole list will need
-some other strategy for synchronization.  Here are some choices:
+some other safety strategy.  Here are some choices:
 
 1. Some way to communicate to the relevant portions of `alloc()` and
    `free()` that the free-list is locked.  Not sure how to best do
@@ -34,10 +42,10 @@ some other strategy for synchronization.  Here are some choices:
 
 3. Atomically swap out the entire free-list, but also use some global
    flag that says "fresh allocations banned."  The benefit of this is
-   that you don't *have* to set that flag; you can decide that based
-   on whether memory pressure is really that severe.  This way, the
-   free-list pruning can be done without stalling allocations when
-   there's no such dire pressure.
+   that you don't *have* to set that flag; you can decide it based on
+   whether memory pressure is severe.  This way, our free-list sweep
+   algorithms can run without stalling allocations, when there's no
+   such dire pressure.
 
 I think I like the third.  It means that, when fresh alloc is banned,
 threads will stall after they've found the free-list to be empty, but
@@ -46,8 +54,11 @@ can just check it again once they continue.  Pseudo-code:
     if (check_free_list()) |ptr|
       return ptr;
 
-    if (fresh_alloc_banned()) // Reads atomic flag
-      sleep_until_unbanned(); // Could just be a 10 ms sleep loop.
+    if (fresh_alloc_banned()) {
+      sleep_until_unbanned();
+      if (check_free_list()) |ptr|
+        return ptr;
+    }
 
     if (check_vacancy_list()) |ptr|
       return ptr;
@@ -78,7 +89,7 @@ never reach 4 KiB.)  So, we can also safely release every non-first
 page of every chunk head slot.  Taking the 64 KiB size class as an
 example again, where each slot is 16 pages (assuming 4 KiB), we can
 release `4*16+15` out of `5*16` pages.  That's 79/80, or 98.75% of
-memory held by the free-list, that we can release.
+memory held by the free-list, that we can release.  Very good!
 
 I think the worst-case is the 4 KiB size class, and even there, the
 free-list chunks store 8 other slots, so we release 8 out of every 9
@@ -111,13 +122,117 @@ The consolidation in question could happen in two ways:
   entries instead.
 
 The second option is simpler and simply better.  I don't know why I
-even bothered to write out the other option.
+even bothered to write out the first option.
 
 The only question, then, is how to identify such contiguous slots in
 the free-list, which carries indexes in arbitrary order.
 
-At this point I have to admit that the following is probably way too
-much complication for a small benefit, and this is partly just a fun
-mental exercise.
 
-[TBC]
+### Self-Reflecting Pointer Trie
+
+I don't know if this is a new invention, or if I'm reinventing some
+idea others came up with before:
+
+The Self-Reflecting Pointer Trie is a trie of pointers in which the
+pointers making up the structure of the trie also happen to be the
+pointers stored as data in the trie.
+
+The pointers must be cut up into units we will call "words" for the
+sake of simplicity.  Let's demonstrate this with 16-bit pointers cut
+into 4-bit words, so it fits in a small graphic.
+
+Given that each word (4 bits) can have 16 different values, nodes of
+the trie must be able to hold arrays of 16 pointers.  In other words,
+every pointer leads to a memory location large enough to store at
+least 16 other pointers.
+
+We will use hexadecimal to represent pointers and array indexes; one
+hexadecimal digit 0 to F represents a 4-bit word / array position.
+
+The following graphic shows a Self-Reflecting Pointer Trie that has
+the pointers 1234, 1256, 7800, and 7855 stored in it:
+
+    Root -> [  // Level 1: Sorts by first word.
+
+      [0]   [1]   [2]   ...  [6]   [7]   [8]   ...
+      null  1234  null  ...  null  7800  null  ...
+
+    ]
+
+    1234 -> [  // Level 2: Sorts by second word.
+
+      ...   [1]   [2]   [3]   ...
+      ...   null  1256  null  ...
+
+    ]
+
+    7800 -> [  // Level 2: Sorts by second word.
+
+      ...   [7]   [8]   [9]   ...
+      ...   null  7855  null  ...
+
+    ]
+
+    1256 -> [ <empty> ]  // Level 3
+
+    7855 -> [ <empty> ]  // Level 3
+
+As you can see, the pointer 1234 is both stored in the root node as
+data, and happens to point to a node which can hold further pointers
+sharing the same first word with it.
+
+The pointer 1256 is stored as data at the second level, and points to
+a node that would store further pointers sharing the first and second
+word with it.
+
+The maximum level (height) would be 4, corresponding to the number of
+words a pointer is made of.
+
+In this example, the trie is already "sorted" in the sense that the
+pointer 1234, stored in the root, is less than 1256, stored in the
+node 1234.  What if we insert 1200?  Keeping it sorted is easy:
+
+If a pointer to be stored has a value less than the parent into which
+it would be stored, then move the contents of the parent into it, put
+it in place of the parent, and continue the insertion procedure with
+the parent pointer's value.  I believe this is similar to rotation of
+an AVL tree.
+
+By the way, pointers most commonly have more variance in their least
+significant bits.  That is, you are more likely to encounter pointer
+groups like 0001, 0003, 0012, etc. that have equal higher bits, than
+pointer groups like 1000, 3000, 1200, etc. which vary in their high
+bits while having equal low bits.  For this reason, after splitting
+pointers into words, it's best to order them low to high when using
+them to navigate.  Otherwise, the trie will quickly become tall and
+narrow; pessimal for efficiency.
+
+Of course, 16-bit pointers are easy.  Let's see how we can actually
+implement this strategy in Meta Alloc.
+
+
+### Actual implementation
+
+Based on the current implementation details of Meta Alloc, we can use
+the following schema in practice:
+
+* Our "pointers" (indexes) are 32 bits including the highest bit that
+  signals NULL.  But given that the smallest size class is 128 bytes,
+  which is 16 "units" in terms of index values, the lowest four bits
+  are always zero, so there are only up to 28 meaningful bits.
+
+* Our smallest size class being 128 means that every slot (trie node)
+  can store up to 32 indexes, which allows splitting our indexes into
+  5-bit words.
+
+* That means we have a maximum trie height of 6, with 2 spare bits.
+
+The need to move entire node contents to keep the trie sorted worries
+me a little, but I think it should be fine.  Just make sure to sort
+the indexes within each free-list chunk in-place before iterating
+through them to insert them into the trie.
+
+I'm not going to implement this yet.  It's way too much complexity,
+only to offer a feature that may hardly ever be needed.
+
+But it was fun to come up with, and good to know that it's possible.