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