Update last note.

1 files changed, 75 insertions, 0 deletions

diff --git a/notes/260727-alloc.md b/notes/260727-alloc.md
index 73af511..0988ee7 100644
--- a/notes/260727-alloc.md
+++ b/notes/260727-alloc.md
@@ -125,3 +125,78 @@ or two specific size classes.  So I guess the main heap will need a
 totally different strategy.  The main heap will also be the main one
 needing a sophisticated garbage collector, so I guess it's OK to not
 use this super simple core allocator for it.
+
+## Addendum A
+
+To prevent false sharing issues, it may be best to have 64 bytes be
+the smallest size class.  Objects smaller than this should generally
+reside on the stack, or be allocated from some kind of pool; remember
+again this isn't for regular language-domain arbitrary heap objects.
+
+Sticking to 16 size classes, this makes the largest 2 MiB, of which
+there can only be 2048, which is fine.  Reducing to 8 size classes
+would make the biggest 8 KiB, which is no good.
+
+The 32-bit index, by the way, should use a scaling factor (say 8, so
+it's zero-cost via the LEA instruction) so it can't overflow, even if
+the 4 GiB slab for a size class is saturated.  This means we could go
+up to e.g. 16 GiB slabs (for a total of 256 GiB of vmem) which fully
+eliminates concerns about ever saturating a size class.
+
+This also enables a remarkably clean strategy for checking for OOM:
+Use a *signed* 32-bit integer for the watermark, and let it overflow
+to negative when the last slot of a size class is used.  Now we only
+need to check if it's negative before an allocation.
+
+The new 16 GiB slab size means we can have 8192 active slots of the
+biggest 2 MiB size class, which is even finer than 2048.
+
+New Summary:
+
+* 256 GiB total vmem divided into 16 slabs of 16 GiB.
+
+* Size classes go from 64 bytes to 2 MiB.
+
+* The watermark of each slab is kept track of via a 32-bit signed int
+  using 8-byte units for "free" shifting in certain CPU instructions
+  on x86-64 and AArch64.
+
+* Atomic fetch-and-add on the watermark for fresh allocations; check
+  the fetched value for a negative to decide if we raise OOM due to
+  slab saturation.  (Fetch-and-add returns *previous* value before
+  addition.)  So, every last slot of a 16 GiB slab is usable, and
+  checking for OOM is a simple less-than-zero check.
+
+* The biggest size class of 2 MiB can have up to 8192 active slots;
+  much more than what we would ever realistically need.  Just make
+  sure not to abuse big size classes based on the logic: "It's just
+  virtual memory anyway; I can reserve lots of 2 MiB slots and only
+  fill each as much as it needs."  No, use a smaller size class; for
+  example, if you're allocating stacks for green threads or such, of
+  which there could be millions, use 8 KiB dynamic stack segments or
+  some strategy like that.
+
+* Thread-local free-list caches hold up to 64 nodes, transferred in
+  chunks of 32 to and from the global free-list for the given size
+  class.  Note this is for native threads, not green threads.  The
+  green threads don't need thread-local caches since each can only
+  execute within one specific native thread.
+
+The previously discussed "low-cost high-yield" optimization of simply
+decrementing the watermark if the last allocation is freed does not
+actually make sense in a multi-threaded context with thread-local
+caches, so scrap that.  However, the following are possible:
+
+* We might eventually implement an expensive cleanup procedure that
+  checks whether the last N slots of a slab are currently free by
+  traversing the global free-list, removing them from the free list,
+  and accordingly decreasing the watermark.  Probably overkill, but
+  possible.
+
+* If we use a GC strategy involving a global STW, we could even do
+  that in a way that involves all thread-local free list caches, just
+  as an extra "side mission" of the GC; these slabs are not otherwise
+  subject to any kind of GC since they are not for the regular heap.
+
+If either or both of these is implemented, we could then also free
+memory back to the OS if a slab watermark drops significantly.