malloc in embedded systems

I prefer static fixed-size allocations (just arrays / structs in code) to dynamic allocation due to:

- there is no risk of fragmentation,

- if there is over-allocation, it's known at build time,

- there is no allocator overhead.

Are you going to free() the blocks?

If you have a complete heap with allocation and freeing of very varying-size objects, you have a strong risk of memory fragmentation: there is plenty of space, but no free areas large enough to satisfy an allocation request. This is a very difficult situation in an embedded system, as there is usually no user interface suited for an error message of not enough memory.

Admitted, there are allocation schemes which minimise the risk of fragmentation (e.g. the buddy system), but it comes for a price: the allocation block size is usually limited to some pre-defined sizes.

Your RTOS probably tries to get rid of the fragmentation problem by fixing the allocation block size.

There is a way to recover from fragmentation: compressing the allocated blocks together to combine all free blocks into one large block. This is defragmetation or garbage collection. There is a requirement, though: the pointers to the allocated blocks have to be chaqnged to follow the movement of the allocated blocks. This is often done by using indirect addressing to the allocated blocks via an address vector in the memory allocator. An example of thid kind of solution is the memory allocation handle method in the early Windowses.

In general, you cannot get a dynamic allocation scheme with freely selectable block size, no risk of fragmentation, no memory space overhead and no garbage collector.

For more information, get Don Knuth's The Art of Computer Programming.

HTH

Tauno Voipio tauno voipio @ iki fi

Perhaps a very basic compromise solution would be to include an allocater that maintains two or more pools - each pool having different but fixed size blocks. When you require a block you check the pool of smallest blocks first, then if they are too small or there are none left move on to check the pool the next size up ... etc. until you find a free block. This type of scheme can then be tuned as you learn how your system is using memory (assuming it cannot be determined up front).

In your RTOS you can have the idle process looking at how the pools are used - how often a pool runs out of blocks, etc. Information that can be used to make adjustments on your next build.

Regards, Richard.

malloc() is not really a good choice.

I do earn my money designing RTOS (and with this memory managers). And I found that a fixed-buffer size allocator is best when it comes to memory-usage and determinism.

But other than the RTOS (which ?) you are refering to, we give you the choice of a) multiple pools and b) either 4,8 or 16 buffersizes per pool.

With a little tuning of the buffersizes, it results in no fragmentation (external and internal) and still very fast !

--
42Bastian
Do not email to bastian42@yahoo.com, it's a spam-only account :-)
Use @epost.de instead !

Perhaps this is good enough, it gives predictable performance and you can more easily specify how the system will fail in case of an overload.

The "buddy system memory allocator" might be a reasonable compromise. A buddy system allows block sizes of e.g. 100, 200, 400, ..., 3200 bytes. There is an implementation in the ABCD Proto-Kernel(tm) source code available on the web site below. Integration into the kernel requires the use of mutual exclusion semaphores.

Anyway, the selection of a good allocator is a debatable issue on any system.

- Thierry Moreau

CONNOTECH Experts-conseils inc.

9130 Place de Montgolfier Montreal, Qc H2M 2A1

Tel.: (514)385-5691 Fax: (514)385-5900

e-mail: snipped-for-privacy@connotech.com

I would recommend using the worstcase limit and creating a static array of the objects. If you have to support the worstcase size, you are not wasting any memory by dimensioning to the worst case.

Sandeep

--

EventStudio 2.0 - Real-time and Embedded System Design CASE Tool

So is the "create on demand" philosophy invalid in this case ? The worst case scenario would only occur if a certain combination of event scenarios occur. The probability of this specific combination of event scenarios occuring is very low - something in the order of 1 in 10000. Also, does that mean the embedded system philosophy is "prefer static objects of malloc'd objects, unless you cannot avoid using malloc'd objects." ??

Thx. Cheers, Albert

Hi Phileo,

Most of the time, static memory allocation is better for realtime application. But some application needs a good dynamic memory allocator to optimize the memory available. ie: data recorder, C++ GUI task running over RTOS, etc...

I had to do this with VxWorks. But the memory allocator was really weak, generating too much fragmentation. I replaced it by a port of Doug Lea's memory allocator : now, it's much faster and reliable.

check this link : ftp://gee.cs.oswego.edu/pub/misc/malloc.c

If you needs a port to vxWorks 5.x, I had the source (made by Bill Pringlemeir).

Regards Emmanuel.

phileo wrote:

...

...

And what do you do when that unlikely situation occurs ? Hide your head in the sand (e.g. display Blue Screen of Death) ?

In many systems, hiding your head in the sand is simply not an option, so you really have to allocate the resources required by the worst case situation or manipulate the environment, so that this kind of combinations of events can not occur (e.g. by high level flow control of incoming requests).

Paul

Please do not toppost.

For a malloc system dependant only on flat byte addressing and the availability of sbrk(), check out my nmalloc.zip. It compiles under gcc, and that limitation is largely due to the use of macros with varargs for fundamental initial debugging. On the x86 the result is about 3k bytes. The associated malldbg package (part of the zip file) takes about 2.5k bytes, and allows extensive user level debugging and analysis.

I would be interested to know how easily it ports to other systems. Everything has been deliberately kept as close to standard C as possible. It is under the DJGPP licence, so there are no barriers to usage in other systems.

The original reason for creation was the O(n) action of free, which is now O(1). This also applies to realloc. It is not a buddy system allocator, but it avoids fragmentation as far as possible. The memalign portion is not done, but not needed for anything known except porting gcc. The hooks for user level debugging are very flexible and do not require any recompilation, although they do require standards mandated zeroing of static storage initialization.

It, with documentation info style, can be found at:

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
     USE worldnet address!

I believe you will find that Murphy's Law covers this situation. You should see what we have to do to ensure that sort of thing does not happen with our avionics software (people do not have a sense of humor when the airplane falls out of the sky ..). If it can happen, it will -- and if you are not the one who has to fix it, the next poor guy trying to figure out why it crashes every third week when it is sunny out or whatever.

mikey