Viability of a New Allocator

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've been trying to circulate a new idea for a new allocator for some time now, to replace the current glibc allocator. It would leave behind the heap in favor of complex mmap()ing to create what is best described as a virtual virtual heap-- a completely noncontiguous virtual heap that acts as a contiguous virtual heap that acts as a real heap. For our purposes, we will call a real heap a "real heap," and a virtual virtual heap "the heap" or just "heap."

The advantages of this are many, mainly that unused pages can be returned to the system and that memory fragmentation would be reduced in severity. The disadvantages are that the code would be more complex.

Any unused, allocated area of memory that touches or crosses a page boundary is infinite in size under this scheme, and so can be expanded and utilized, reducing the impact of heap fragmentation.

I believe that this would not only give less memory usage; but also increase the speed of allocations. Allocations could be done by checking the largest finite size unused segment of existing allocations, and if it's smaller than what you need, using an infinite size fragment.
~ Seaching out an unused, allocated segment to fit an allocation call
would be a shorter operation, because all page-aligned and page-crossing unused fragments are of inifinite size; and so if a finite size fragment exists that fits what is needed, it will be found in a smaller, possibly much smaller list.

The idea was first developed on a bug posted to the Red Hat Sources Bugzilla; and later refined in a blog, and posted in a Red Hat Linux Bugzilla bug, and also to libc-alpha. Those links are as follows:

http://sources.redhat.com/bugzilla/show_bug.cgi?id=167
http://bluefoxicy.blogspot.com/2004_05_01_bluefoxicy_archive.html#108507154064758877
https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=123965
http://sources.redhat.com/ml/libc-alpha/2004-05/msg00216.html

I have no idea how to implement this, although from what I gather it is feasible. I believe but can not guarantee that it will give the returns I expect. Is anyone interested in this at all? I don't have the skill to code it, but if someone could find someone to code it or at least confirm that it should behave as expected, I'd be grateful. -----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA2nXahDd4aOud5P8RAuFpAJ9wldF6eEe12w0QUS9jHmmTK6DoaQCdEjDl aT3XERefzLEHZ57jtgPU2FA=
=gZ2e
-----END PGP SIGNATURE-----

glibc's malloc() already uses anonymous mmap() for blocks above a certain threshold (default is 128Kb, configurable via environment variables and mallopt()).

However, there is a (kernel-imposed) limit on the number of such blocks, so you can't just mmap() a separate region for each block.

The last time I checked, glibc won't attempt to map a large region then allocate multiple smaller blocks from it. In typical usage, there probably wouldn't be much point. It can't unmap the region so long as any portion of it is in use.

It could resize the region, moving the top downwards. OTOH, moving the bottom upwards would require moving the base of region and copying all used blocks, and that would be problematic in a multi-threaded process. The same issue applies to splitting a block which is used at both ends but empty in the middle.

The main thing in your proposal which doesn't make sense is:

While you could extend such regions using mremap(), they certainly aren't "infinite size". They can't be extended any further than the next memory location which is currently in use.

Ultimately, on a 32-bit system, the problem tends to degenerate into one of allocating address space rather than memory. And that limits how much you can do with a malloc()-style interface, i.e. where the block has to remain at a fixed address throughout its lifespan.

You would have a lot more flexibility using either x86 segmentation (which is x86-specific, and would require 48-bit pointers), or a mechansism similar to the Win16 API (LocalAlloc, LocalLock, LocalUnlock) where blocks can be moved around.

Glynn Clements <[email protected]>