w6d5: Header fragmentation

Continuously growing header list

Growing the header list is O(1) but will cause holes when headers are in state FREE_BLOCK (for later compacting) or UNUSED. Since handle is mapped 1:1 with header, they cannot be compacted.  Scanning the list to find a free header to use in malloc() would take O(n) time

By wasting an extra integer value in the header structure, a monotonically increasing number can be assigned to each new handle and copied into the header.  When compacting, the handles will be sorted by that key.  Looking up a handle in lock/unlock() will be O(log n). Is that acceptable?

According to http://jfdube.wordpress.com/2012/01/13/memory-management-part-4-allocators-overhead-waste-and-fragmentation/, the overhead is 8-24 bytes per chunk. I'm up to 20 bytes right now.

Could the address of the header be cached in the handle for as long as compact hasn't happened yet? Then, when the compact happens, all handles are updated according to the new value.  Caching the address with the integer requires actual storage somewhere, and we're back to square one with actual lookup having to be done. Rats.

A hash function mapping <handle-integer> to <header> in O(1) that is rewritten on each compact? See http://burtleburtle.net/bob/hash/doobs.html for more on hashes -- has a thorough discussion. Also Paul Hsieh's quick hash used in WebKit: http://www.azillionmonkeys.com/qed/hash.html

To consider: to get rid of the extra integer, is it possible to combine the handle and memory block addresses and use that to adress, and update the handle according to an invariant, e.g. that only one will ever be moved at a time, or similar?

Don't grow the header list, don't scan

Since we don't care about any particular order of the headers, only the entire table remains compact, getting any header is fine.

Therefore, use the fact that UNUSED headers don't use their pointer field to keep track of memory blocks, to instead maintain a header free list by using the pointer as the next pointer!  Requires two pointers: one to keep track of the start and the end of the free list. New headers are grabbed from the start and appended to the end.  If no free list, then grow list as before.

At the compact() step, all FREE_BLOCK headers turn into UNUSED and inserted to the free list.