Looking for free memory pool software

[Baron Samedi]

I don't want to reinvent the wheel, so I am looking for some freely
reusable memory pool software. Something tried, tested and efficient.

- It should dynamically allocate memory from a statically allocated
structure or structures, for use in an embedded system.

- it should be coded in C++ (or C).

- it should allow user defined handling of the "out of memory"
situation.

- garbage collection would be very welcome, otherwise defragmentation
may occur after some time and lead to a premature "out of memory".

- since dynamic memory is not expected to have a long lifetime, it
might be useful to timestamp allocated memory so that a low priority
process can flag as suspicious any memory which has been allocated for
more than X seconds or minutes (probably just during the development
process).

Thanks in advance for any help.

 

[Tim Wescott]

I don't want to reinvent the wheel, so I am looking for some freely
reusable memory pool software. Something tried, tested and efficient.

- It should dynamically allocate memory from a statically allocated
structure or structures, for use in an embedded system.

- it should be coded in C++ (or C).

- it should allow user defined handling of the "out of memory"
situation.

- garbage collection would be very welcome, otherwise defragmentation
may occur after some time and lead to a premature "out of memory".

- since dynamic memory is not expected to have a long lifetime, it
might be useful to timestamp allocated memory so that a low priority
process can flag as suspicious any memory which has been allocated for
more than X seconds or minutes (probably just during the development
process).

Thanks in advance for any help.

To have garbage collection you'll need to use a processor with an MMU, or
always access memory through handles, with some defined way to make
accesses reentrant. The mind boggles at how rapidly your code will
balloon.

It is quite common to allocate memory in fixed-size chunks from a pool --
I've done this off and on for comm software that must store packets.
Because the pool is in fixed size chunks it does not fragment (or rather,
it is always fragmented in a way that is well known to the application).
The only real drawback is that you must either make a chunk as big as your
largest possible packet or you must make a mechanism for daisy-chaining
memory chunks and mapping packets onto them.

--
Tim Wescott
Control systems and communications consulting
http://www.wescottdesign.com

Need to learn how to apply control theory in your embedded system?
"Applied Control Theory for Embedded Systems" by Tim Wescott
Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html

 

[Martijn van Buul]

* Baron Samedi:

- garbage collection would be very welcome, otherwise defragmentation
may occur after some time and lead to a premature "out of memory".

Garbage collection in the sense of "getting rid of memory left behind due to
sloppy programmer" won't help you with the fragmentation. If you want to
actually *relocate* memory, you're might be biting off more than you can chew.
Assuming that memory has to be stale just because the allocation is old can
be very dangerous in the general case, but might still be valid in your
specific case. You might want to use a MMU-approach, but in that case you're
trading fragmentation of physical memory with fragmentation of virtual memory.
Depending on your platform, that might be just as bad.

Choosing your memory allocation policy wisely, and choosing your pools wisely
so you don't mix objects with widely varying lifetimes, greatly helps
reducing memory fragmentation.

I found http://www.cs.utexas.edu/users/oops/papers.html to be a valuable
source of information, especially no 8 and 12, when I recently implemented a
pooled memory allocater.

 

[Malcolm McLean]

I don't want to reinvent the wheel, so I am looking for some freely
reusable memory pool software. Something tried, tested and efficient.

- It should dynamically allocate memory from a statically allocated
structure or structures, for use in an embedded system.

- it should be coded in C++ (or C).

- it should allow user defined handling of the "out of memory"
situation.

- garbage collection would be very welcome, otherwise defragmentation
may occur after some time and lead to a premature "out of memory".

- since dynamic memory is not expected to have a long lifetime, it
might be useful to timestamp allocated memory so that a low priority
process can flag as suspicious any memory which has been allocated for
more than X seconds or minutes (probably just during the development
process).

If you are writing a system from scratch, you can do it like this.

1) For quite a lot of objects you know their memory requirements on
creation, and you can arrange them in a stack so that the first created is
also the last destroyed. Thus you can use a stack for allocating these
objects, it the most efficient answer. You could in theory put them on the
main C stack, given a C99 variable-length array extension.
2) Some of the rest of the objects will have a fixed and fairly small size,
like nodes in a tree. These can be allocated very efficiently with a
fixed-size allocator, as long as you know the maximum number you need, and
the maximum isn't too high in relation to total memory.
3) If neither of these apply you need a full allocate any size, any time,
free any time malloc() replacement. You can also use it as a back-up to a
fixed memory allocator - say you know that 99% of the time your tree has
less than 1024 nodes.

If you have the source you can add your own out of memory handling routines.
Timestamps and garbage collection are much more difficult to do efficiently,
though Jacob Navia has garbage collection in his C-like compiler, lcc-win.

 

[CBFalconer]

I don't want to reinvent the wheel, so I am looking for some freely
reusable memory pool software. Something tried, tested and efficient.

- It should dynamically allocate memory from a statically allocated
structure or structures, for use in an embedded system.

- it should be coded in C++ (or C).

- it should allow user defined handling of the "out of memory"
situation.

- garbage collection would be very welcome, otherwise defragmentation
may occur after some time and lead to a premature "out of memory".

- since dynamic memory is not expected to have a long lifetime, it
might be useful to timestamp allocated memory so that a low priority
process can flag as suspicious any memory which has been allocated for
more than X seconds or minutes (probably just during the development
process).

Consider adapting a general purpose malloc package, that comes
complete with debuggery facilities. nmalloc is written for the
DJGPP system, but requires very little non-standard code. Most of
the code is avoiding memory moves on realloc. It compiles under
gcc and is available at:

<http://cbfalconer.home.att.net/download/>

Look at the debugging system for end user help, and the package
debugging system for means of supplying memory from other sources.

 

[Didi]

I don't want to reinvent the wheel, so I am looking for some freely
reusable memory pool software. Something tried, tested and efficient.

- It should dynamically allocate memory from a statically allocated
structure or structures, for use in an embedded system.

- it should be coded in C++ (or C).

- it should allow user defined handling of the "out of memory"
situation.

- garbage collection would be very welcome, otherwise defragmentation
may occur after some time and lead to a premature "out of memory".

- since dynamic memory is not expected to have a long lifetime, it
might be useful to timestamp allocated memory so that a low priority
process can flag as suspicious any memory which has been allocated for
more than X seconds or minutes (probably just during the development
process).

Thanks in advance for any help.

This comes typically with an OS; unless you can get the Linux memory
management thing for free (which I am not familiar with and I don't
know
if it does all you describe), I suspect you will have to do it
yourself.

My memory allocation/deallocation etc. writing experience is mostly
from writing DPS; in fact, this is the first thing one does when
beginning
a new OS (which I did in ... well, the end of 1994).
I do use (to this day) bit per cluster for allocation; which cluster
belongs to whom is recorded (or not) elsewhere.
The allocate/find space etc. pieces are highly critical, you want to
save every CPU cycle while doing this.
Garbage collection/reallocate carries more implications that it may
seem
first - like preserving address/data coherency etc.
In the days when DPS was running only on a small CPU32, I implemented
a pseudo VM-mechanism, which is very efficient: the user task requests
memory for allocation as usual, gets it, and at some point allows the
OS
to "swap" that memory. Knowing that is has allowed that, next time it
needs
that piece of memory it asks the OS to return it and gets it [having
been
swapped or not], perhaps at
another address, for which the user code is prepared. Or, if no memory
is
available at this time, the task gets the registration of the file
which
holds the swapped piece to bang its its head with (I have used that
also
in user code, I remember I used to swap window off-screen buffers like
this and having to restore the window on-screen even if there were no
system memory for the entire window at the moment...).

This mechanism survives in DPS to this day also on the PPC (older
code
uses it), where one gets MMU, VM and all, I have not had to resort to
it recently. Since a few years I also have a "memory_pool" DPS
object, which is a "piece_of_memory" etc., which gives another level
of flexibility & accessibility without sacrificing speed, but I guess
talking about them would make this too DPS specific.

If you really need only the memory allocate/deallocate stuff, you may
want to consider writing it yourself. It is critical, but by far not
bulky;
gets called all the time but is written just once .

Dimiter

 

[Kelsey Bjarnason]

[snips]

1) For quite a lot of objects you know their memory requirements on
creation, and you can arrange them in a stack so that the first created is
also the last destroyed. Thus you can use a stack for allocating these
objects, it the most efficient answer. You could in theory put them on the
main C stack

What, exactly, is "the main C stack" and where in the standard is it
defined?

 

[Malcolm McLean]

[snips]

1) For quite a lot of objects you know their memory requirements on
creation, and you can arrange them in a stack so that the first created
is
also the last destroyed. Thus you can use a stack for allocating these
objects, it the most efficient answer. You could in theory put them on
the
main C stack

What, exactly, is "the main C stack" and where in the standard is it
defined?

A stack the only way of implementing a conforming C compiler. Those that do
not use stacks do not support recursion.
Read my book "Basic Algorithms" if confused about stacks and how they are
useful.

 

[Charlton Wilbur]

M> A stack the only way of implementing a conforming C
M> compiler. Those that do not use stacks do not support
M> recursion.

There's a difference between having a data structure that a programmer
would recognize as isomorphic to a stack and having an area of storage
defined as "the stack." C does not require the presence of an
explicit stack; it does require support for recursion, but imposes no
requirements on how this is to be accomplished.

M> Read my book "Basic Algorithms" if confused about
M> stacks and how they are useful.

Yes, and then he'd be *more* confused, especially if he had a working
knowledge of C and attempted to read your code. Perhaps something
analogous -- "read the C standard if confused about C" -- is advice
you should follow?

Charlton

 

[Malcolm McLean]

M> A stack the only way of implementing a conforming C
M> compiler. Those that do not use stacks do not support
M> recursion.

There's a difference between having a data structure that a programmer
would recognize as isomorphic to a stack and having an area of storage
defined as "the stack." C does not require the presence of an
explicit stack; it does require support for recursion, but imposes no
requirements on how this is to be accomplished.

I said "you could in theory put them on the main C stack". No suggestion
about how the main C stack is implemented, though there must be such an
object.

There is a difference between useful and pointless pedantry.

 

[Keith Thompson]

[snips]

1) For quite a lot of objects you know their memory requirements on
creation, and you can arrange them in a stack so that the first
created is
also the last destroyed. Thus you can use a stack for allocating these
objects, it the most efficient answer. You could in theory put them
on the
main C stack

What, exactly, is "the main C stack" and where in the standard is it
defined?

A stack the only way of implementing a conforming C compiler. Those
that do not use stacks do not support recursion.

The term "stack" is used in (at least) two different ways. As a
fundamental data structure, a stack supports last-in first-out access;
C requires a "stack" in this sense to support recursion, though it
doesn't use the term. But if a compiler can prove that a given
function is never called recursively, it can choose to store its local
automatic variables in static storage. This just turns out not to be
advantageous on most modern architectures.

But another very common use of the term is a contiguous region of
memory, accessed via a "stack pointer" (often a dedicated CPU
register). C does not require a "stack" in this sense, and there are
implementations that do not use one.

Read my book "Basic Algorithms" if confused about stacks and how they
are useful.

Must ... resist ... sarcastic ... response.

 

[Charlton Wilbur]

(quoting me)

M> I said "you could in theory put them on the main C stack". No
M> suggestion about how the main C stack is implemented, though
M> there must be such an object.

No, there doesn't need to be such an object. That's why I was careful
to say "a data structure that a programmer would recognize as
isomorphic to a stack."

M> There is a difference between useful and pointless pedantry.

From where I sit, it looks like the difference is more accurately
described as between being correct and being incorrect.

Charlton

 

[Kelsey Bjarnason]

[snips]

1) For quite a lot of objects you know their memory requirements on
creation, and you can arrange them in a stack so that the first created
is
also the last destroyed. Thus you can use a stack for allocating these
objects, it the most efficient answer. You could in theory put them on
the
main C stack

What, exactly, is "the main C stack" and where in the standard is it
defined?

A stack the only way of implementing a conforming C compiler.

Oh? I'm sure you'll support this.

Those that
do not use stacks do not support recursion.

And this. Perhaps you'd be best off defining what "the main C stack" is,
as the standard uses the term, so we're all clear on what, exactly, you're
talking about, as I can't seem to find the term anywhere in my copy.

Read my book "Basic
Algorithms" if confused about stacks and how they are useful.

I'm well aware of what the stack as a data structure is. You appeared to
be discussing the concept of stack as pertains to the language - a
language which neither defines nor requires any such thing.

 

[Malcolm McLean]

M> I said "you could in theory put them on the main C stack". No
M> suggestion about how the main C stack is implemented, though
M> there must be such an object.

No, there doesn't need to be such an object. That's why I was careful
to say "a data structure that a programmer would recognize as
isomorphic to a stack."

So now you are quibbling about "object".

M> There is a difference between useful and pointless pedantry.

From where I sit, it looks like the difference is more accurately
described as between being correct and being incorrect.

No, there is a clear difference.
Some pedants illuminate, other just insist on precise definitions of terms,
when in fact the English language isn't structured like that. "object" is
here being used as synonym for "structure", as is English idiom, not to
repeat the major semantic word in consecutive sentences, because that makes
the language easier to understand. However there are no exact synonyms. This
is not a grammar group, just understand that some of us has been trained in
linguistics and know these things, whilst most computer programmers have
not.

You and KB are pedants in the bad sense of the term. In this case I was
explaining how most data objects can be structured in a stack, allowing a
very simple and efficient memory management paradigm. The question then
arises, why not make the objects automatic? However there is not much point
using the standard's term "automatic storage duration", because it may not
be familiar, as anyone with any common sense would realise.

 

[Keith Thompson]

I said "you could in theory put them on the main C stack". No
suggestion about how the main C stack is implemented, though there
must be such an object.

There is a difference between useful and pointless pedantry.

There's a big difference between a "stack" as a fundamental data
structure and a "stack" as a feature of a CPU architecture. You used
the term "stack", without qualification, in the former meaning (I
presume), but in a context in which a reasonable reader could easily
think you're referring to the latter. Pointing this out is useful
pedantry.

C implicitly requires something that behaves in a stack-like manner
(in the fundamental data structure sense), but the standard doesn't
use the word "stack" to refer to this. By introducing the word
"stack", you have not clarified anything.

 

[Charlton Wilbur]

M> So now you are quibbling about "object".

No, I'm quibbling about your erroneous belief that every C
implementation will necessarily have something obviously idenfiable as
a stack in it.

Because of the nature of function calls and the lack of coroutines in
C, there will necessarily be something in memory that is isomorphic
with a stack. This does not mean that there will be a stack.

M> Some pedants illuminate, other just insist on precise
M> definitions of terms, when in fact the English language isn't
M> structured like that. "object" is here being used as synonym
M> for "structure", as is English idiom, not to repeat the major
M> semantic word in consecutive sentences, because that makes the
M> language easier to understand. However there are no exact
M> synonyms. This is not a grammar group, just understand that
M> some of us has been trained in linguistics and know these
M> things, whilst most computer programmers have not.

I'm not quibbling over the word "object." One would think that
someone claiming to be "trained in linguistics" would have better
reading comprehension.

Further, if you're going to use "some of us has [sic] been trained in
linguistics" as an attempt to shut down those who disagree with you,
you should be prepared for the use of "some of us have been trained in
computer science" as an attempt to shut down your next bit of
wingnuttery -- or the next iteration of one of your previous bits of
wingnuttery. Or for someone to say, "you know, Malcolm, I've been
trained in linguistics and I speak, read, and write four languages,
and you're full of it." Whoops, I just did.

M> You and KB are pedants in the bad sense of the term.

In other words, "you're people who correct me when I'm talking out of
my ass." If you don't like being corrected, don't say things that are
flat-out wrong, and when you're corrected, learn from it.

M> In this case I was explaining how most data objects can be
M> structured in a stack, allowing a very simple and efficient
M> memory management paradigm.

Yes, and you referred to "the main C stack," and you were challenged
to provide a citation from the standard -- any C standard you like --
that indicates that C requires such a beast.

M> The question then arises, why not make the objects automatic?
M> However there is not much point using the standard's term
M> "automatic storage duration", because it may not be familiar,
M> as anyone with any common sense would realise.

Ah, but there is a point: it's correct, and it's precise. And using
it gives people who are unfamiliar with it an opportunity to learn it,
and to discover something of which you seem doggedly determined to
remain ignorant: that the common convention of "stack" and "heap" is
merely a convenient implementation detail.

Or would you advocate that we call symphonies and rhapsodies and
toccatas and arias and murder ballads all "songs," as imprecise as
that is, because the correct terms might be unfamiliar to some
potential listener, somewhere?

Charlton

 

[Malcolm McLean]

Further, if you're going to use "some of us has [sic] been trained in
linguistics" as an attempt to shut down those who disagree with you,
you should be prepared for the use of "some of us have been trained in
computer science" as an attempt to shut down your next bit of
wingnuttery -- or the next iteration of one of your previous bits of
wingnuttery. Or for someone to say, "you know, Malcolm, I've been
trained in linguistics and I speak, read, and write four languages,
and you're full of it." Whoops, I just did.

A "linguist" is not someone who knows lots of foreign languages, at least in
sense in which I am using the term. You can't have had any exposure at all
to lingustics if you don't know something as elementary as that.

 

[Charlton Wilbur]

>> Further, if you're going to use "some of us has [sic] been
>> trained in linguistics" as an attempt to shut down those who
>> disagree with you, you should be prepared for the use of "some
>> of us have been trained in computer science" as an attempt to
>> shut down your next bit of wingnuttery -- or the next iteration
>> of one of your previous bits of wingnuttery. Or for someone to
>> say, "you know, Malcolm, I've been trained in linguistics and I
>> speak, read, and write four languages, and you're full of it."
>> Whoops, I just did.

M> A "linguist" is not someone who knows lots of foreign
M> languages, at least in sense in which I am using the term. You
M> can't have had any exposure at all to lingustics if you don't
M> know something as elementary as that.

Notice, please, the coordinating conjunction 'and.' Had I really
meant to imply that I was trained as a linguist *because* I spoke,
read, and wrote four languages, I would have no doubt used that
subordinating conjunction instead.

You may be casually sloppy in your use of language; it is a
significant error to assume that others are as well.

Charlton

 

[Flash Gordon]

Malcolm McLean wrote, On 29/08/07 21:54:

Further, if you're going to use "some of us has [sic] been trained in
linguistics" as an attempt to shut down those who disagree with you,
you should be prepared for the use of "some of us have been trained in
computer science" as an attempt to shut down your next bit of
wingnuttery -- or the next iteration of one of your previous bits of
wingnuttery. Or for someone to say, "you know, Malcolm, I've been
trained in linguistics and I speak, read, and write four languages,
and you're full of it." Whoops, I just did.

A "linguist" is not someone who knows lots of foreign languages, at
least in sense in which I am using the term. You can't have had any
exposure at all to lingustics if you don't know something as elementary
as that.

For someone trained in linguistics your reading comprehension is
sometimes very low. Charlton said that he is trained in linguistics. He
went on to say that in addition to this he can speak, read and write
four languages. The relevance of the second part, the part after the
word "and" in what he typed, is that English has linguistic routes in a
number of languages, and this is something I would expect someone
trained in linguistics to know.

Now, I've not remembered enough posted by Charlton to have formed an
opinion about him, so for all I know he could be bulshitting. Although I
tend to assume people are honest until given reason to disbelieve it.
However his main point that if you will try to use linguistics to shut
people down then others are equally entitled to use computer science to
shut you down is certainly valid. Especially as the definition of the C
language provides specific *narrow* definitions for a number of terms
and specific terms for a number of concepts.

 

[Ben Bacarisse]

In this case I
was explaining how most data objects can be structured in a stack,
allowing a very simple and efficient memory management paradigm.

Assuming that by "most data objects" you mean something like "function
arguments and local variables" the statement is uncontentious and
might have been helpful. In the earlier post you did say that.

It is odd, then, that rather than leaving it at that you made the much
stronger statement:

| A stack the only way of implementing a conforming C compiler.

I suspect you were hoping to poke a few pedants with such a remark,
knowing that the position, whilst not exactly correct, is at least
defensible in a comp.lang.c bare knuckle fight.

question then arises, why not make the objects automatic? However
there is not much point using the standard's term "automatic storage
duration", because it may not be familiar, as anyone with any common
sense would realise.

I think it would have been more helpful to point out the relationship
between the term "automatic storage" and the common arrangement of
putting such objects on a stack. You'd have explained a term the OP
will have to come to terms with eventually and you would look less like
someone who wants to a start a row.