Meta Alloc cleanup and doc update.

1 files changed, 62 insertions, 17 deletions

diff --git a/doc/0/A-meta_alloc.md b/doc/0/A-meta_alloc.md
index 51f3ff7..3ac005a 100644
--- a/doc/0/A-meta_alloc.md
+++ b/doc/0/A-meta_alloc.md
@@ -29,6 +29,7 @@ This is not directly related to garbage collection, though a GC may
 use Meta Alloc to manage auxiliary metadata, or even for the actual
 heap memory returned to application code; it's up to the GC.
 
+
 ## Overview
 
 The entire architecture is built on three pillars:
@@ -48,6 +49,7 @@ in advance and letting the operating system automatically handle the
 actual mapping to physical memory provides an immense simplification
 of the allocator implementation.
 
+
 ## Slabs and Size Classes
 
 A single global pointer in static memory is initialized to point to
@@ -121,6 +123,7 @@ If a size greater than the largest size class is requested, then Meta
 Alloc simply forwards this to an `mmap()` call, acting as a mere thin
 wrapper around mmap, calling `munmap()` on `free()`.
 
+
 ## Global metadata
 
 The static array `slab_infos` holds `N_SLABS` many structures which
@@ -130,11 +133,14 @@ record just two pieces of information associated with each Slab:
 
 * The head of the global, shared *Free-List* for this Slab.
 
+* The head of the global, shared *Vacancy-List* for this Slab.
+
 Expressed in pseudo-code:
 
     struct SlabInfo {
       watermark: Integer,
       free_list: ListHead,
+      vacancy_list: ListHead,
     }
 
     var slab_infos: [N_SLABS]SlabInfo;
@@ -152,7 +158,8 @@ In other words, it may be implemented as a Treiber stack:
 The initial value of the `free_list` head is of course some sort of
 null indicator so we can know it's empty.
 
-Detailed explanations of the Watermark and Free-List follow.
+Detailed explanations of the Watermark, Free-List, and Vacancy-List
+follow.
 
 ### Slab Watermark
 
@@ -223,6 +230,38 @@ using up to 512-bit SIMD instructions on modern processors.
 Why we would need to bulk-transfer 16 Index values will be explained
 later, as we look into thread-local cache metadata.
 
+### Vacancy-List
+
+For reasons we will go into later, there may be memory regions below
+the Watermark of a Slab that are completely vacant, span across pages
+of memory, and need not be backed by physical memory.
+
+Vacant, in this case, means no *meaningful* data is held; either the
+memory has never been touched and is all zeros, or application code
+has given it back for freeing and we decided not even to store any
+meta-data in it, so we don't care if it's zeroed out.
+
+Such memory regions are recorded in the Vacancy-List, which has the
+following simple node structure:
+
+    {
+      next_vacancy_idx: Index,
+      vacancy_end_idx: Index,
+    }
+
+These nodes themselves occupy the beginning of each such vacancy,
+which means that the real vacancy only begins after two Indexes.
+Starting from the next page boundary after that, writing any data
+could lead to a page fault.
+
+Slots in the Free-List, in contrast, are likely to have physical
+memory backing them, which is why they're given out first.
+
+The Vacancy-List is the penultimate choice to satisfy an allocation
+request, before increasing the Watermark and giving out completely
+fresh memory.
+
+
 ## Per-thread metadata
 
 We don't want to burden code using Meta Alloc with concerns about
@@ -261,6 +300,10 @@ we need to check the global Watermark again (it may have been bumped
 by another thread) to set our new Low, and bump the global, to which
 we set our new High.
 
+When Meta Alloc decides to reach for Vacancy-List entries, it does
+that by setting the calling thread's Low and High to the start and
+ending point of the vacancy.
+
 ### Free Slot Cache
 
 When `free()` is called in a thread, it checks whether there's still
@@ -290,14 +333,13 @@ Slots as a reserve.  For this reason, although the Free Slot Cache
 array has a static maximum size, larger size classes have a lower
 maximum element count that they enforce.
 
-Note: While the bumping of the global Watermark happens in fairly
-massive chunks for the smaller size classes, the Free Slot Cache
-instead has fairly small upper limits throughout all size classes.
-This is because reserving a big "hole" in a Slab is totally benign,
-since the operating system won't map any physical memory to it until
-it's actually used; whereas freed Slots already have physical memory
-backing them, making it important not to let too many of them linger
-around in some thread's local cache without being reused.
+Note: While the bumping of the global Watermark happens in massive
+chunks for the smaller size classes, the Free Slot Cache has small
+upper limits throughout all size classes.  This is because, while
+reserving a big "hole" in a Slab is benign (since physical memory
+won't be mapped until pages are touched), freed Slots have physical
+memory backing them already, making it important not to keep around
+too many of them in some thread's local cache without being reused.
 
 ### Thread destruction
 
@@ -310,16 +352,19 @@ without any other subsequent calls to `alloc()` or `free()` before
 exiting.
 
 This immediately transfers the thread's Free Slot Cache entries into
-the global Free-List, in multiple chunks if necessary, then creates
-Free-List entries (also in chunks) for any leftover memory that was
-reserved from bumping the global Watermark by a chunk.
+the global Free-List, in multiple chunks if necessary; and creates a
+Vacancy-List entry for leftover reserved memory (from the bumping of
+the global Watermark) if the amount of reserved memory spans across
+multiple pages.  Otherwise, it's simply split into Slots and also
+pushed onto the Free-List.
 
 ## Releasing vmem
 
 Though not currently implemented, Meta Alloc may be able to release
-virtual memory back to the operating system via strategies explained
-in the following Zisp Note:
-
-* [Releasing virtual memory](../../notes/260817-release.html)
+virtual memory back to the operating system by detecting that there
+are Free-List entries corresponding to contiguous memory regions
+spanning across pages of memory.
 
-End.
+In this case, these Free-List entries may be removed, a Vacancy-List
+entry created instead, and one or more pages of memory given back to
+the operating system.