snazzy-d / sdc

The Snazzy D Compiler
MIT License
249 stars 55 forks source link

Appendability for slab allocs. #287

Closed dsm9000 closed 1 year ago

dsm9000 commented 1 year ago

Full appendability support for slab allocs, and tests for same. Requires https://github.com/snazzy-d/sdc/pull/286 . realloc() preserves metadata during transitions between size classes, both large and small, that support appendability. (All large size classes support appendability, and all but four small size classes -- likewise.) allocAppendable() allocates one size class up from the default, for small allocs (two if the immediately next size class does not support appendability.) getCapacity() returns a logically-correct result for slices of all size classes of alloc. extend() likewise works on all appendable size classes where the slice being extended follows the required rules, i.e. has sufficient adjacent free space for the requested extension.

Description of the implemented scheme, from earlier chat: instead of "appendability" bits in slabData space: have "has free space?" bits indicating slots that are not fully used; when set for an occupied slab slot, triggers the use of the length data at the end of the alloc. the latter can then fill up 100%, rather than having the length data always waste the final 1 or 2 bytes (dep. on size class). This way we can also later aggregate slab slots... ...in this scheme, all size classes where <512 slots can be treated as appendable and at the same time safely fillable to the max (the "has space" bit corresponding to a slot will simply unset). the last 1 or 2 bytes (dep. on size class) will store free space length rather than used capacity (which can be found simply by subtracting the free length from the respective size class's size.) i.e. if the "has free space" bit corresponding to a slab slot is set, then bit 0 of the last byte in the alloc is set if there is a second freespace-length byte below it; the top 7 bits of the last byte in the alloc correspond to the lower 7 bits of the freespace length, and the penultimate byte, if its presence is indicated as above, has the upper 8 (well, 7, we need only 14) bits of the freespace length. this way a slab alloc can extend, let's say it starts out needing both of the freespace-length bytes; when extends to the point it needs only 1, bit0 of the 1st (end of alloc) length byte unsets; and if extends to the point that it fills the avail. size entirely, incl. the final byte, the "has free space" meta bit corresponding to the slot is cleared. slab size classes where 512 slots, we can simply treat as "appendable but full".

Currently labels are structured like this. "Byte Low" is found at the end of the allocation body (if and only if the alloc is not full, from an appendability POV, i.e. the size class supports labels, and the label slabData bit is set for the respective slot.) And under it, optionally, "Byte High" :

Byte Low (bits in descending order of significance) :
|F6|F5|F4|F3|F2|F1|F0|HB|

Byte High:
|U|F13|F12|F11|F10|F9|F8|F7|

... where HB is a flag indicating the presence of Byte High, and F0 ... F13 represent free capacity length (which is up to 14 bits wide.) Bit U is currently unused.

Elsewhere: the size field in pInfo allows for a later use of slab allocs which are to be considered shorter (for appendability purposes) than the size of the size class they belong to. This will make it easy to put in optional finalizer data.

deadalnix commented 1 year ago

This needs to be rebased.

dsm9000 commented 1 year ago

Thought I'd finish cutting it up first, then rebase

dsm9000 commented 1 year ago

Superceded by https://github.com/snazzy-d/sdc/pull/301 .