Looking for free memory pool software

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

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

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

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

------------------------------------------------------

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.

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.

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

Stefan