class VmSlotPageStorage

Slot-page storage is an allocator optimized around the expectations, and distributions of,

compressed pages. At the high level it breaks a page into 64 equal slots that can be used to

store data.

The overall operation is closest to a buddy allocator where a page is broken into 64 slots, and

kept in a list indexed by the largest contiguous run of free slots. This largest contiguous run

represents the largest allocation supported by the page.

As free space in the page is measured only in slots, any allocation is rounded up to the next

slot size multiple, causing wastage due to internal fragmentation. Performing an allocation is

done by finding a page that has at least as many contiguous free slots as the size of the

allocation, allocating the run of slots, and then re-calculating the potentially changed

contiguous run and placing in the correct list.

There are three relevant data structures for this system:

1. vm_page_t free_block_mask: This is a bitmap, stored directly in the vm_page_t, that tracks

exactly which slots are free and which slots are allocated.

2. Contiguous free slot list: For every possible slot length [0, 64) there is a linked list of

pages for which that is their largest run of contiguous free slots. This is just a cache of

what can always be calculated from the free_block_mask, but this serves to provide a way to

find a valid page to allocate from in O(1) time, instead of scanning all pages.

3. `Data` allocation: This is the metadata about the specific allocation being tracked and

points to the vm_page_t that contains the allocation, the slot range being used, and the

true (unrounded) length of the data. This metadata is separately allocated using a slab

allocator, instead of the heap, that so that a reference to it that fits in a CompressedRef

can be returned to the user.

Compressed pages, by number, tend to have a reasonably even distribution over the different size

buckets. However, when weighted by cumulative size, there is therefore more data to store at

larger compressed sizes. The use of slots allows for a balance of being able to store these

large items, and then packing in multiple smaller items around it, as well as being able to

store large amount of small items in a single page if need be.

The use of 64 slots, and the resulting 64-byte slot size for 4k pages, is a trade-off in the

resulting fragmentation due to rounding, and the efficiency of being able to track slots in a

bitmap that fits in a single machine word.