Looking for free memory pool software

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.

On Sun, 26 Aug 2007 20:29:27 -0700, Baron Samedi wrote:

> 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

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

-- 
Martijn van Buul - pino@dohd.org 

"Baron Samedi" <Papa.Legba.666@gmail.com> wrote in message 
news:1188185367.982646.138140@r23g2000prd.googlegroups.com...
>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.

-- 
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Baron Samedi wrote:
> 
> 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.

-- 
 Chuck F (cbfalconer at maineline dot net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>



-- 
Posted via a free Usenet account from http://www.teranews.com

On Aug 27, 6:29 am, Baron Samedi <Papa.Legba....@gmail.com> wrote:
> 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

------------------------------------------------------
Dimiter Popoff               Transgalactic Instruments

http://www.tgi-sci.com
------------------------------------------------------

Baron Samedi wrote:
> 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.

A simple 'malloc' replacement with a fixed memory pool doesn't take more
than a day to implement, hence I didn't bother looking for one (and a
Unix malloc using mmap etc. doesn't help you on a controller without MMU
or operating system) but instead made my own.

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

You probably do not want garbage collection (=automatic reclaim of
unused memory), but compaction. Last time I needed that, I implemented
that on the application side; much easier than in a general way inside
the allocator. Essentially, I used this very crude routine (retyped from
memory)
     void* try_to_move(void* orig, size_t size) {
         void* new = malloc(size);
         if (new != 0) {
             if ((intptr_t) new < (intptr_t) orig) {
                 memcpy(new, orig, size);
                 free(orig);
                 return new;
             }
             free(new);
         }
         return orig;
     }
and, if malloc returned 0, used it to compact the central data
structures ("thingy = try_to_move(thingy, sizeof(*thingy))"). If you
want to use knowledge about the allocator, you can also do that to
improve performance; that wasn't an option in my case.

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

Although it's probably not a good idea, implementing your own malloc
will allow you to do that :-)


  Stefan