malloc in embedded systems

I have an embedded system using an RTOS.  The one weakness of this
RTOS is that it has a weak memory manager.  You can pre-define the
block size that will be created in the memory pool, but this block
size is always fixed.  That means that it won't be able to allocate
the exact amount of memory that you need - it will turn out to always
be too much.  The only exception to this is if I pre-define the block
size to be the same as the size of my most often used data object. 
But I have two different types of data objects (ie. different sizes),
and they are both used often. Soo, I have avoided using this memory
manager, and have been using static arrays instead.

I have a list of data objects that I will need to create during run
time.  The number of objects on this list at any given time during
runtime is unknown, although there can a be worst case maximum limit
to the size of this list.
So, my question is this:  Which is preferable for my situation,
malloc() or pre-defining a static array that is equal to the worst
case size ?


Thx.
Cheers,
Albert

phileo wrote:
> I have an embedded system using an RTOS.  The one weakness of this
> RTOS is that it has a weak memory manager.  You can pre-define the
> block size that will be created in the memory pool, but this block
> size is always fixed.  That means that it won't be able to allocate
> the exact amount of memory that you need - it will turn out to always
> be too much.  The only exception to this is if I pre-define the block
> size to be the same as the size of my most often used data object. 
> But I have two different types of data objects (ie. different sizes),
> and they are both used often. Soo, I have avoided using this memory
> manager, and have been using static arrays instead.
> 
> I have a list of data objects that I will need to create during run
> time.  The number of objects on this list at any given time during
> runtime is unknown, although there can a be worst case maximum limit
> to the size of this list.
> So, my question is this:  Which is preferable for my situation,
> malloc() or pre-defining a static array that is equal to the worst
> case size ?


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

> But I have two different types of data objects (ie. different sizes),
> and they are both used often. Soo, I have avoided using this memory
> manager, and have been using static arrays instead.

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.

http://www.FreeRTOS.org

On 3 Feb 2004 20:01:06 -0800, phileo98@yahoo.com (phileo) wrote:

>I have an embedded system using an RTOS.  The one weakness of this
>RTOS is that it has a weak memory manager.  You can pre-define the
>block size that will be created in the memory pool, but this block
>size is always fixed.  That means that it won't be able to allocate
>the exact amount of memory that you need - it will turn out to always
>be too much.  The only exception to this is if I pre-define the block
>size to be the same as the size of my most often used data object. 
>But I have two different types of data objects (ie. different sizes),
>and they are both used often. Soo, I have avoided using this memory
>manager, and have been using static arrays instead.
>
>I have a list of data objects that I will need to create during run
>time.  The number of objects on this list at any given time during
>runtime is unknown, although there can a be worst case maximum limit
>to the size of this list.
>So, my question is this:  Which is preferable for my situation,
>malloc() or pre-defining a static array that is equal to the worst
>case size ?

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 <same-name>@epost.de instead !

phileo98@yahoo.com (phileo) wrote in message news:<c64a9677.0402032001.7b00e199@posting.google.com>...
> I have an embedded system using an RTOS.  The one weakness of this
> RTOS is that it has a weak memory manager.  You can pre-define the
> block size that will be created in the memory pool, but this block
> size is always fixed.

> Soo, I have avoided using this memory
> manager, and have been using static arrays 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.

> 
> I have a list of data objects that I will need to create during run
> time.  The number of objects on this list at any given time during
> runtime is unknown, although there can a be worst case maximum limit
> to the size of this list.

> So, my question is this:  Which is preferable for my situation,
> malloc() or pre-defining a static array that is equal to the worst
> case size ?

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

http://www.connotech.com
e-mail: thierry.moreau@connotech.com

> I have a list of data objects that I will need to create during run
> time.  The number of objects on this list at any given time during
> runtime is unknown, although there can a be worst case maximum limit
> to the size of this list.
> So, my question is this:  Which is preferable for my situation,
> malloc() or pre-defining a static array that is equal to the worst
> case size ?
 
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
--
http://www.EventHelix.com/EventStudio
EventStudio 2.0 - Real-time and Embedded System Design CASE Tool

eventhelix@hotmail.com (EventHelix.com) wrote in message news:<566e2bfb.0402041908.18661bf8@posting.google.com>...
> > I have a list of data objects that I will need to create during run
> > time.  The number of objects on this list at any given time during
> > runtime is unknown, although there can a be worst case maximum limit
> > to the size of this list.
> > So, my question is this:  Which is preferable for my situation,
> > malloc() or pre-defining a static array that is equal to the worst
> > case size ?
>  
> 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

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:

> I have an embedded system using an RTOS.  The one weakness of this
> RTOS is that it has a weak memory manager.
...
> I have a list of data objects that I will need to create during run time.
...
> Which is preferable for my situation, malloc() or pre-defining a static array

On 4 Feb 2004 23:51:48 -0800, phileo98@yahoo.com (phileo) wrote:

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

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
 

Emmanuel HERBRETEAU wrote:
> 
> 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).

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:

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

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