Virtual memory allocator recommendations?

[David Given]

I have a situation where I need to be able to allocate chunks on
unmapped virtual memory.

Because the memory I'm allocating isn't mapped, I can't use a normal
memory allocator, as most of them want to store their metadata about the
free list in the unused holes in the heap. Instead, I need a memory
allocator that stores its metadata out-of-line (perversely enough, a
simple malloc() heap would be fine for that).

Does anyone know of such a beast?

This sort of thing would be useful for allocating any memory-like
resource, such as space in a file, or blocks of time in a day, or that
sort of thing. So I'm sure they're out there; I just can't find any...

 

[Ian Collins]

I have a situation where I need to be able to allocate chunks on
unmapped virtual memory.

Because the memory I'm allocating isn't mapped, I can't use a normal
memory allocator, as most of them want to store their metadata about the
free list in the unused holes in the heap. Instead, I need a memory
allocator that stores its metadata out-of-line (perversely enough, a
simple malloc() heap would be fine for that).

Does anyone know of such a beast?

It's not hard to do with system specific APIs, but I don't think there's
a what in standard C. So you'd be better off asking in a platform
specific group, this level of access tends to be very platform specific.

 

[Ian Collins]

It's not hard to do with system specific APIs, but I don't think there's
a what in standard C. So you'd be better off asking in a platform
specific group, this level of access tends to be very platform specific.

Oops, make that "way in standard C".

 

[Keith Thompson]

It's not hard to do with system specific APIs, but I don't think there's
a what in standard C. So you'd be better off asking in a platform
specific group, this level of access tends to be very platform specific.

Actually, what he's trying to do doesn't sound very system specific to
me. As he wrote in the original article:

This sort of thing would be useful for allocating any memory-like
resource, such as space in a file, or blocks of time in a day, or
that sort of thing. So I'm sure they're out there; I just can't
find any...

So what he's looking for is a way to allocate chunks out of some range
of <whatever> (memory addresses, file offsets, times of day) without
storing metadata alongside the allocated chunks. He could just as
well be allocating ranges of numbers.

I think the question is more about algorithms and data structures than
about any particular system or even any particular language, so
comp.programming is probably the best place to ask.

 

[David Given]

Richard Harter wrote:
[...]

You might be interested in the getspace allocator that I wrote.
The source code and documentation are at
http://home.tiac.net/~cri_a/source_code/getspace/

Thanks, but being built on top of malloc it doesn't actually allocate
its own chunks, so it doesn't seem to be suitable for what I want, alas.

Any suggestions for other places to look? comp.lang.programming?

 

[Ian Collins]

Richard Harter wrote:
[...]

You might be interested in the getspace allocator that I wrote.
The source code and documentation are at
http://home.tiac.net/~cri_a/source_code/getspace/

Thanks, but being built on top of malloc it doesn't actually allocate
its own chunks, so it doesn't seem to be suitable for what I want, alas.

Any suggestions for other places to look? comp.lang.programming?

You didn't state your platform, but a group for that platform would be a
good place to ask.

 

[Keith Thompson]

Richard Harter wrote:
[...]

You might be interested in the getspace allocator that I wrote.
The source code and documentation are at
http://home.tiac.net/~cri_a/source_code/getspace/

Thanks, but being built on top of malloc it doesn't actually allocate
its own chunks, so it doesn't seem to be suitable for what I want, alas.

Any suggestions for other places to look? comp.lang.programming?

There is no comp.lang.programming. I already suggested
comp.programming.

 

[David Given]

Richard Harter wrote:
[...]

As others have said, you need to look at groups specific to your
platform. There is no way to portably write a storage allocator
in standard C only - to get chunks of memory you have to have
access to the OS memory management facilities.

I think I haven't made myself clear.

I don't want anything platform specific. What I want is an allocator for
an *abstract linear resource*, which could be virtual memory, or time,
or space, or anything like that --- I want to be able to allocate chunks
from a contiguous linear range of numbers. Not only can this be done in
portable C, I *want* it in portable C, because I have to run it on at
least two highly dissimilar platforms.

i.e. an interface something like this:

typedef unsigned int domain_t;

void init_allocator(domain_t start, domain_t length);
domain_t allocrange(domain_t length);
void freerange(domain_t start);
domain_t resizerange(domain_t start, domain_t newlength);

domain_t is utterly abstract and does not need to represent any physical
resource. I only mentioned virtual memory because that's the specific
problem I need to solve, but I'm actually looking for a general solution.

As I said, this is a very similar problem to the one that's solved by
malloc(), but most malloc() implementations make assumptions about what
they're allocating that allows them to take shortcuts, which don't apply
in my case. Which means I can't use them.

 

[David Given]

Richard Harter wrote:
[...]

Your thought about allocators making taking shortcuts is a red
herring - the core code in getspace doesn't do that. (It does
put guard characters surrounding allocated space but that is a
refinement but that has nothing to with the underlying
algorithms.)

Ah, I didn't realise that; as you say, there's quite a lot of stuff in
it, so I read the documentation and skimmed the code rather than looking
how it actually worked, and got the impression it merely wrapped
malloc() and free() rather than allocating from its own areas. I'll take
another look.

[...]

Second side comment: What are your assumptions about resource
usage and desired efficiency.

I'm easy. Currently this is a prototype. I want something that's good
enough for now, and later if it turns out to not be good enough, I'll do
some proper benchmarking and replace it with something else. So any
reasonably straightforward implementation will do.

[...]

The two general strategies that I will mention are buddy system
allocators and best fit, immediate merge allocators with metadata
units for each block.

Yes; my fallback position is to implement a basic best fit allocator
(because I know how they work). However, I was hoping that someone would
be able to point me at an existing *implementation*, which is why I'm
here rather than elsewhere. I can certainly write one myself, it's just
I don't want to. They're fiddly and a pain to debug.

It's very odd; I would have thought that this sort of thing would be a
fairly standard part of any C algorithm library. I just can't *find*
one. (It doesn't help, when searching, the terms are either so vague
that all I get is noise, or else I find about a billion different
malloc() implementations.)

Anyway, thanks for the analysis --- if, as I suspect, I'll have to write
one myself, I'll certainly want it for reference.