Slab Alloc

slaballoc_design

Design:

Note: The smallest block that can be allocated is 8 bytes due to the following structure.

Byte Layout:
 0             3             7
  ----------------------------
 |   size of   |  offset to  |
 |   data      |  next free  |
  ----------------------------

Offset:
 The externally facing offset (uint32_t)(what is returned from Alloc) is composed of 2 parts:
     
     slab index: the slab number, ie what slab to look in
         = offset >> SlabShiftConst
     
     block offset: the offset into the selected slab
         = offset & ((1 << SlabShiftConst) - 1)
     
     ** SlabShiftConst = 24 was selected to allow for slabs of 16MB and a maximum of 256 slabs to be allocated 

Grain Size: 
A block offset shift.  This allows external offsets to be smaller, thus increasing the 
amount of memory we can address.
     
     Slab Size Formula:  For n, grain size > 0, 2^(24 + n) = slab size, in bytes
     Addressible Memory Formula: For n, grain size, (2^32 * 2^n) = addressible memory, in bytes.
     Example:
         Grain Size      Slab Size   Addressible Memory
         0               16MB            4GB
         1               32MB            8GB
         2               64MB            16GB
         3               128MB           32GB
         4               256MB           64GB
         5               512MB           128GB
         6               1GB             256GB
         7               2GB             512GB
         8               4GB             1TB

Note: largest block size is 2^32 

I approve.