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

--
┌─── ｄｇ＠ｃｏｗｌａ ｒｋ．ｃｏ ｍ ───── http://www.cowlark.com ─────
│ "...it's not that well-designed GUI's are rare, it's just that the
│ three-armed users GUI's are designed for are rare." --- Mike Uhl on
│ a.f.c

[Ian Collins]

Re: Virtual memory allocator recommendations ?

David Given wrote:

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.

[Ian Collins]

Re: Virtual memory allocator recommendations ?

Ian Collins wrote:

David Given wrote:

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

Oops, make that "way in standard C".

--
Ian Collins.

[Keith Thompson]

Re: Virtual memory allocator recommendations ?

Ian Collins <ian-news@hotmail.co mwrites:

David Given wrote:

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

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(memor y 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.programmin g is probably the best place to ask.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Richard Harter]

Re: Virtual memory allocator recommendations ?

On Tue, 07 Oct 2008 23:51:42 +0100, David Given <dg@cowlark.com >
wrote:

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

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/

The main reason I thought you might be interested is that all
metadata is stored separately from from the allocated space.
However is built on top of malloc/free and is portable. If this
works for you, you are welcome to go ahead and use it.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[David Given]

Re: Virtual memory allocator recommendations ?

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.progr amming?

--
┌─── ｄｇ＠ｃｏｗｌａ ｒｋ．ｃｏ ｍ ───── http://www.cowlark.com ─────
│ "...it's not that well-designed GUI's are rare, it's just that the
│ three-armed users GUI's are designed for are rare." --- Mike Uhl on
│ a.f.c

[Ian Collins]

Re: Virtual memory allocator recommendations ?

David Given wrote:

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.progr amming?
>

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

--
Ian Collins

[Keith Thompson]

Re: Virtual memory allocator recommendations ?

David Given <dg@cowlark.com writes:

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.progr amming?

There is no comp.lang.progr amming. I already suggested
comp.programmin g.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Richard Harter]

Re: Virtual memory allocator recommendations ?

On Fri, 10 Oct 2008 00:35:17 +0100, David Given <dg@cowlark.com >
wrote:

>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.progr amming?

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.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[David Given]

Re: Virtual memory allocator recommendations ?

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(doma in_t length);
void freerange(domai n_t start);
domain_t resizerange(dom ain_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
dg@cowlark.com

[Eric Sosman]

Re: Virtual memory allocator recommendations ?

David Given wrote:

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

This sounds like a general data-structure question, not
a C question. Here's the test: Would your question change in
any important way if you planned to write the code in Fortran?
C questions may arise when you get to the implementation stage
or when you're studying or modifying a piece of existing code,
but at the moment your question seems language-independent. The
advice to seek help in a forum about algorithms or techniques
rather than in a forum about C/Ada/Java/COBOL/Unameit seems good.
Or one of the "sources.wanted " groups, if you're looking for a
pre-written implementation you can play with.

<ot meaning_of_o="o ff">

Bit maps, Judy trees, skip lists, splay trees, ... These
all seem plausible, at first blush, with different advantages
and disadvantages. The size of the "arena" you want to manage,
the "churn rate" you need to support, and the responsiveness
you require will probably influence your choice.

</ot>

--
Eric Sosman
esosman@ieee-dot-org.invalid

[Richard Harter]

Re: Virtual memory allocator recommendations ?

On Fri, 10 Oct 2008 12:20:42 +0100, David Given <dg@cowlark.com >
wrote:

>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(doma in_t length);
>void freerange(domai n_t start);
>domain_t resizerange(dom ain_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.

As Eric remarks, this really is a general programming question;
however we are here and now and I see no point in not answering
your question.

If I undestand your question correctly, getspace and many other
allocators actually actually have what you want; unfortunately
they also necessarily have a lot of stuff that you don't need.
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.) What it is managing is an abstract resource
(interger range) that is correlated with physical memory. Robust
allocators do this so that metadata and resource are not
comingled.

Side comment: Your initializer allocates a fixed domain size -
what if you need a larger domain?

Second side comment: What are your assumptions about resource
usage and desired efficiency. This will affect what kind of
allocation strategy you use. N.b. You probably should read up on
storage allocation strategies. Knuth has some material (not
enough) on the issues.

Third side comment: Will your usage let you change "start" under
the hood? If it does, you can effectively use compaction
techniques.

An abstract allocator has two basic problems to solve; finding a
block of the requisite size when allocrange is called and finding
the metadata for "start" when freerange is called. Resizing is
trivial if you've solved those problems.

The two general strategies that I will mention are buddy system
allocators and best fit, immediate merge allocators with metadata
units for each block. I don't propose to describe how to
implement buddy allocators here. They are good and they are
simple to implement. IIRC the overhead is two bitmaps of the
domain range. The one drawback is that they are relatively
inefficient in their allocation - about 1/3 of the available
resource will be unused. Best fit allocators are (in some
environments) more efficient in their domain usage; however they
have significant overhead per block.

Getspace uses the latter; however there is a lot of complexity
that has been added for performance reasons. Let's look at the
core functionality. Our resource is broken up into a list of
contiguous blocks (ranges in your notation) that are either free
(available for allocation) or in use (allocated). We have a
block representation node that looks like this:

struct allocation_node {
struct allocation_node * domain_left;
struct allocation_node * domain_right;
int index;
int usage_flag;
/* more stuff */
};

Left and right are smaller and larger indices respectively.
Domain_left and domain_right are the links in a doubly linked
list. Index is the start of the represented block. And, of
course, usage_flag says whether the block is allocated or not.

Now we need two data structures. One holds all of the nodes with
their size as a key - the size is available by subtracting the
domain_right index from the current index. The other holds all
of the allocated nodes with their index as a key.

When we allocate we search the first data structure for the
smallest block that is larger than the desired size. If it is
the right size we mark it as in use and return the index. If it
is too large we create a new node that is linked between the node
and its domain right neighbour, and use it to hold the remnant.
The resized node is moved to its new location in the data
structure and the remnant node is added. The resized node is
added to the second data structure.

When we free a block we search the second data structure to find
its node. We remove the node from the second data structure.
Now we do the merges. If left and right neighbours are in use we
mark the node free and add it to the first data structure. If it
has free neighbours they are removed from the first data
structure and are delinked. The neighbour blocks are
incorporated in the node and the resized block is marked free and
is added to the first data structure.

Getspace uses some "interestin g" data structures to gain
performance but that is the core of the package.












Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[David Given]

Re: Virtual memory allocator recommendations ?

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.

--
┌─── ｄｇ＠ｃｏｗｌａ ｒｋ．ｃｏ ｍ ───── http://www.cowlark.com ─────
│ "...it's not that well-designed GUI's are rare, it's just that the
│ three-armed users GUI's are designed for are rare." --- Mike Uhl on
│ a.f.c