Improved allocated object classification

[avikivity]

Currently, free(v) uses the offset of an objectwithin a page (o = v & 0xfff) to determine which allocator is responsible for the page:

• if o == 0, it is a large object (> page size)
• if o == 8, it is a an early allocator object
• otherwise, it is a mempool object, with the pool page header residing at the beginning of the page (v - o)

this scheme has a number of issues:

• allocating objects that are exactly page sized waste two pages
• it is hard to align objects that are between half a page and a page
• the header for a large object is sized an entire page (the expected waste is half a page on average)

We can improve this by using information other than the offset within the page to determine the allocator. If we map physical memory multiple times (all aliases of each other), we can use virtual address bits 44:46 to determine the allocator.

The value of v[44:46] can be used as follows:

0 - mempool allocator
1 - page allocator (for objects between half a page and a page)
2 - half-page allocator (for objects exactly half a page, useful for network buffers)
3 - large objects
4-5 reserved
6 - early allocator objects
7 - debug allocator (using a non identity virtual:physical mapping)

The virtual memory map will now be

0000_0000_0000_0000 - 0000_7fff_ffff_ffff kernel code and application virtual memory
ffff_8000_0000_0000 - ffff_8fff_ffff_ffff mempool (sub-page) objects
ffff_9000_0000_0000 - ffff_9fff_ffff_ffff page objects
ffff_a000_0000_0000 - ffff_afff_ffff_ffff halfpage objects
ffff_b000_0000_0000 - ffff_bfff_ffff_ffff large objects (> 1 page)
ffff_e000_0000_0000 - ffff_efff_ffff_ffff early allocator objects
ffff_f000_0000_0000 - ffff_ffff_ffff_ffff debug allocator objects

[nyh]

In the mailing list Avi pointed out that as part of this fix, we should also get a more complete implementation of posix_memalign() than what we have now:

On Tue, Nov 19, 2013 at 11:38 AM, Avi Kivity [email protected] wrote:

I should implement posix_memalign (POSIX) and/or aligned_alloc() (new to C11), and use that.
Shoud be done as part of #87.
Note it's pretty easy if you change the header to include a pointer to the start of the block.