Amend last note.

1 files changed, 61 insertions, 1 deletions

diff --git a/notes/260923-green-tea.md b/notes/260923-green-tea.md
index 1299224..5b0649a 100644
--- a/notes/260923-green-tea.md
+++ b/notes/260923-green-tea.md
@@ -50,7 +50,7 @@ the Level 3 index.
 
 (Note: 262,144 bits is 32 KiB which is OK to allocate statically.)
 
-Level 3: A 64 x 64 x 64 = 262144-element array of Work Table Header
+Level 3: A 64 x 64 x 64 = 262,144-element array of Work Table Header
 structs, which consist of a 64-bit pointer to a buffer of memory, and
 a 64-bit summary bitmap indicating which portions of it contain valid
 entries right now.
@@ -138,10 +138,70 @@ size classes they support.
 |    2 |       24, 32 |        24 |      16 |     128 KiB |
 |    3 |      40 - 64 |        40 |      32 |      64 KiB |
 |    4 |     80 - 128 |        80 |      64 |      32 KiB |
+|    5 |    160 - 256 |       160 |     128 |      16 KiB |
+|    6 |    320 - 512 |       320 |     256 |       8 KiB |
+|    7 |   640 - 1024 |       640 |     512 |       4 KiB |
 |  ... |          ... |       ... |     ... |         ... |
 
 (Assuming 2-byte Work Table entries.)
 
+### Occupancy Bitmap
+
+*This entire sub-section is a correction to the design after I was
+done writing all the above; too lazy to edit original.*
+
+Above I said it would be extremely fast to scan 4 KiB of memory, to
+look for 16-bit values in it.  That was a bit naive, and we should
+improve on that.
+
+The Work Table Header, instead of being a 64-bit buffer pointer and
+64-bit summary bitmap, could instead be:
+
+    u32: buffer_ptr
+    u32: bitmap_ptr
+    u64: summary_map
+
+The 32-bit "pointers" would be indexes into specific Meta Alloc slabs
+as implied by the buffer size.  For example, for the first 1/16 part
+of the Work Table Header array, we know the entries are for 8-byte
+objects, meaning the Work Table needs to be 256 KiB, meaning it's in
+the Meta Alloc slab for 256 KiB slots.  (Actually, we may also get it
+from Block Alloc; doesn't matter much I think.)
+
+The `bitmap_ptr` would point to a buffer that's 1/16 the size of the
+Work Table buffer, indicating which 16-bit entries have a value.  For
+example, for the 8-byte size class, the Work Table buffer is 256 KiB
+so the bitmap buffer would be 16 KiB.  The 64-bit summary tells us
+which 1/64 portion to check for occupancy, so we only scan 256 bytes
+worth of bits, and thus we get indices into the Work Table itself.
+
+If the Work Table buffer is so small that the 64-bit summary already
+provides enough granularity, then the `bitmap_ptr` can be the Meta
+Alloc index equivalent of NULL.
+
+| Slab | Buffer Size | Bitmap Buffer | Scan Size |
+|------|-------------|---------------|-----------|
+|    0 |     256 KiB |        16 KiB |       256 |
+|    1 |     128 KiB |         8 KiB |       128 |
+|    2 |     128 KiB |         8 KiB |       128 |
+|    3 |      64 KiB |         4 KiB |        64 |
+|    4 |      32 KiB |         2 KiB |        32 |
+|    5 |      16 KiB |         1 KiB |        16 |
+|    6 |       8 KiB |         512 B |         8 |
+|    7 |       4 KiB |         256 B |         4 |
+|    8 |       2 KiB |         128 B |         2 |
+|    9 |       1 KiB |          64 B |         1 |
+|   10 |       512 B |             - |         8 |
+|   11 |       256 B |             - |         4 |
+|   12 |       128 B |             - |         2 |
+|   13 |        64 B |             - |         1 |
+|   14 |        32 B |             - |         1 |
+|   15 |        16 B |             - |         1 |
+
+As we can see, by the time we reach Slab 9, we only need to scan a
+single byte of the occupancy bitmap.  After that, we stop using an
+additional bitmap buffer, using only the 64-bit summary bitmap.
+
 
 ## Slab Exhaustion?