Viability of a New Allocator

Viability of a New Allocator

[John Richard Moser]

-----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-----

Re: Viability of a New Allocator

[Glynn Clements]

John Richard Moser wrote:

> 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.

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:

> 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.

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 <glynn.clements@virgin.net>