malloc in embedded system?
Stein Erik Andresen
Has anybody got any information on how to use the C library
functions malloc and free on an embedded system? I assume
that on a PC, malloc asks DOS for memory chunks, but how
does this work on an OS-less embedded system. How is the
"heap-manager" initialized/configured? Any C source that
I could look at? I intend to use this on an i486 target, and I
use PharLap/MetaWare tools.
Stein Erik Andresen
s...@null.net
Alec Cawley
In article <3479d64...@news.online.no>, Stein Erik Andresen
<s...@null.net> writes
I don't know how it works in an x86 systems. On the systems I work on
(68k, transputer) the system performs a ram self-size, either at powerup
or at the first call of morecore(). There is no point in doing it more
than once, because all available memory not full of code or static
variable is given to the heap manager.
--
Alec Cawley
Newbury
Berks, UK
George C. Lindauer
Stein Erik Andresen (s...@null.net) wrote:
> Has anybody got any information on how to use the C library
> functions malloc and free on an embedded system? I assume
> that on a PC, malloc asks DOS for memory chunks, but how
> does this work on an OS-less embedded system. How is the
> "heap-manager" initialized/configured? Any C source that
> I could look at? I intend to use this on an i486 target, and I
> use PharLap/MetaWare tools.
> Stein Erik Andresen
> s...@null.net
there has been discussion about related issues in the past. Without an OS
you are probably going to have to write a suitable malloc/free type
thing. BUT... if your system is going to run for a long time you need to
analyze the types of allocation you are going to do and make sure you
use a heep algorithm that will NOT eventually end up fragmenting the
heap so badly that you end up with lots of heap space but all in
small fragments. As an example, one of my applications with some
commercial DOS compiler (borland) left me with 88K of heap space free,
but it was all in 16-byte chunks because their algorithm was very
inefficient for lots of different sized heap allocation and frees.
Another thing you need to consider is thrashing, that is if you somehow
mangage a general-purpose solution to the above you want to make sure
that your heap reconstitution routines don't spend so much time
that whatever your device is it gets out of control.
The absolute best thing in an embedded system is, if you can characterize
the allocation sizes and the maximum allocation for each size you
just statically allocate all that space and write a heap routine which
just tags the entries 'used' or 'unused. In the case where you CAN
characterize it this is much preferable from a design standpoint,
as you never have that nagging question... is my heap going to get
too fragmented?
When this is not possible a fair alternative is to have the heap manager
select from several heaps, pick one heap for small allocations and other
heaps for successively larger allocations. Even with only two heaps
you get a marked improvement in terms of fragmentation because small
allocations can never fragment the larger heap. Of course your application
code doesn't know there are multiple heaps, you have your malloc
routine as a wrapper around the multiple heaps.
I have also written a more general-purpose heap routine that I use for
my 32-bit C compiler, it is the same one I came up with to get around
the problems with the borland heap routines. But it is optimized for
keeping the heap defragmented rather than for speed... still I could
NOT guarantee that any program in general will not fail after a long
run period due to fragmentation. But you are welcome to look at it for
ideas if you want... it basically works by combining blocks whenever
possible, and prefering to reuse a small block rather than go
fragmenting the heap any further than it is already fragmented...
another thing I have seen done when you have some sort of scoping going
on is to grab a fixed-size chunk from the main heap, then manage that
seperately for the lifetime of the variables on that heap. Then you can
just free that one block at the end of its lifetime and the heap stays
relatively defragmented...
david
Harold Rabbie
Stein Erik Andresen <s...@null.net> wrote in article
<3479d64...@news.online.no>...
> Has anybody got any information on how to use the C library
> functions malloc and free on an embedded system? I assume
> that on a PC, malloc asks DOS for memory chunks, but how
> does this work on an OS-less embedded system.
malloc() and free() are the types of services that are provided by the
real-time kernel. Products like VRTX, pSOS
and Wind River have implementations that are suitably protected against
interrupts, re-entrancy and the like.
Since these functions operate on a shared data structure (the heap) you
have to write them VERY carefully.
--
Harold Rabbie
Saratoga, CA
Remove .NOSPAM from my address before replying
Travis Marlatte
It depends mostly on the processor. But, in general, dynamic memory
routines are easy and commonplace.
The most common method that I have been exposed to is based on the Intel
architecture. Global memory is filled in from the bottom of RAM. What's
left is allocated for a dynamic memory heap. A small structure is
defined and tacked onto the beginning of every allocated block of
memory. The structure contains at least the size of the allocated block,
if not other administrative stuff.
In simple systems, the allocated memory is given away without tracking
it. This makes it impossible to garbage collect, or to track problems.
When the block is freed, some effort is made to at least combine
adjacent free blocks.
Depending on the system, you may have to worry about fragmentation. If
your system needs to allocate a lot of small pieces, consider allocating
larger blocks and sub-dividing.
I've built embedded systems that successfully used one heap for NEAR
space (remember this is Intel), another heap for FAR space, and another
for battery backed up space (more FAR).
Travis
Robert McConnell
Check the C-Snippets library. It has malloc and free functions
available that I have used. You have to set up the block headers in
your startup functions, and it has no garbage collection. I simply
modified the malloc to concatenate any contiguous free blocks while
looking for a new block to allocate.
Last I knew the Snippets files were in the SimTel collection.
Bob McConnell
N2SPP
On Mon, 24 Nov 1997 19:39:25 GMT, s...@null.net (Stein Erik Andresen)
wrote:
>Has anybody got any information on how to use the C library
>functions malloc and free on an embedded system? I assume
>that on a PC, malloc asks DOS for memory chunks, but how
John Saunders
Peter wrote:
> Without knowing more about your app, it is not possible to be more
> specific, except to say that if you look carefully at the job you
> should be able to work out a static allocation scheme which works, and
> this will be much safer.
I haven't seen mention of buffer pools (or whatever name you might
call it). Essentually your heap is divided up into a pools that
contains a number of fixed sized buffers. At startup the buffers
are linked together into a free list. You can have several pools
offering different sized buffers, and malloc selects a buffer
from the best sized pool. Then free has to figure out which pool
to place the buffer back into. In the comms area we tend to
allocate and free a lot of buffers to hold things like IP packets
as they pass through the box. Buffer pools are very common as
they offer fast allocate and release times, and don't get fragmented.
The one problem is resource waste, an app may allocate a 5 byte
block and the smallest buffer you can give it is 1024 bytes.
Cheers.
-- +------------------------------------------------------------+
. | John Saunders mailto:John.S...@scitec.com.au (Work) |
,--_|\ | mailto:jo...@nlc.net.au (Home) |
/ Oz \ | http://www.nlc.net.au/~john/ |
\_,--\_/ | SCITEC LIMITED Phone +61 2 9428 9563 Fax +61 2 9428 9933 |
v | "By the time you make ends meet, they move the ends." |
+------------------------------------------------------------+
Frank W. Miller
In article <347B93D1...@scitec.com.au>,
John Saunders <John.S...@scitec.com.au> wrote:
>Peter wrote:
>
>call it). Essentually your heap is divided up into a pools that
>contains a number of fixed sized buffers. At startup the buffers
>
The classic alternative is something like a boundary tag algorithm
where you essentially keep a double linked list of blocks that match
size requests perfectly. The drawback is the potential for fragmentation
but the bonus is excellent memory utilization. Fragmentation can be
mitigated by using malloc/free to allocate chunks which are then managed
as groups of higher level structures like pools of thread control blocks
or I/O buffers. In embedded systems, the potential utilization might
make this approach more attractive.
Later,
FM
--
Frank W. Miller Department of Computer Science
fwmi...@cs.umd.edu University of Maryland
http://www.cs.umd.edu/~fwmiller College Park, Maryland 20742
Mark Jordan
On Mon, 24 Nov 1997 19:39:25, s...@null.net (Stein Erik Andresen) wrote:
> Has anybody got any information on how to use the C library
> functions malloc and free on an embedded system? I assume
> that on a PC, malloc asks DOS for memory chunks, but how
> does this work on an OS-less embedded system. How is the
> "heap-manager" initialized/configured? Any C source that
> I could look at? I intend to use this on an i486 target, and I
> use PharLap/MetaWare tools.
Well basically unless the C library for your system has
support for garbage collection, then the malloc() free()
pair will be unsuitable for embedded work due to memory
fragmentation.
One thing you can do is to use malloc() to allocate variable
sized blocks, structures etc, but never use free(). This
way all memory is allocated up front.
Most C library implementations call an initialisation function
to setup the heap before you reach main(). You need to tell
it the start address and size of the block used for the heap.
Then when malloc() is called a function called sbrk() is
called to allocate a block from this area. To get some ideas
I suggest you obtain the source for a C library and examine
the malloc() free() implementations.
If your using a multi-tasking OS which dosn't have malloc()
or free() then you will also need to add mutexes to ensure
only one task allocates memory at a time.
Best Regards,
Mark Jordan.
Rich Walker
In message <347b8ab5...@news2.lightlink.com>
rmcc...@lightlink.com (Robert McConnell) wrote:
> Check the C-Snippets library. It has malloc and free functions
> available that I have used. You have to set up the block headers in
> your startup functions, and it has no garbage collection. I simply
> modified the malloc to concatenate any contiguous free blocks while
> looking for a new block to allocate.
>
> Last I knew the Snippets files were in the SimTel collection.
just grabbed a copy, and it's got some fine stuff in it.
Cheers,
Rich.
--
Rich Walker: r...@shadow.org.uk (Shadow Robot Project)
http://www.shadow.org.uk 251 Liverpool Road
+44(0)171 700 2487 London N1 1PX
Knut Roll-Lund
In article <3479d64...@news.online.no> Stein Erik Andresen of Telenor Online Public Access writes:
> Has anybody got any information on how to use the C library
> functions malloc and free on an embedded system? I assume
> that on a PC, malloc asks DOS for memory chunks, but how
> does this work on an OS-less embedded system. How is the
> "heap-manager" initialized/configured? Any C source that
> I could look at? I intend to use this on an i486 target, and I
> use PharLap/MetaWare tools.
>
> s...@null.net
If you use PharLap as what it is - a dos extender (not just as an
assembler and linker) you will have dos running underneath,
providing memory management, so you use Metaware HighC's
malloc and free as usual.
Well, I can't help giving this advise, it's one of my crusades :-)
Out of memory error on an embedded system??? It must
never happen!!! When you design your system don't use
free, allocate all necessary memory at startup and
reuse it "manually" if necessary. Using malloc and free,
especially in a realtime system, might hide from you what
the real maximum memory burst can be, and your system
could crash violently, every once in a very long while, giving
no indication just because you malloced one byte too much.
Knut
Gabriel Rusaneanu
About calloc() malloc() realloc() and free() functions in 8051 systems :
If they are interesting for you please enclose them.
The next sources code are given with C51 Compiler package from
KEIL ELEKTRONIK GmbH 1993 .This routune are for 8051 family and
for XDATA space memory is necesary an External RAM chip .
/***********************************************************************/
/* This file is part of the C51 Compiler package */
/* Copyright KEIL ELEKTRONIK GmbH 1993 */
/***********************************************************************/
/* */
/* file: STRING.H: string functions */
#ifndef _SIZE_T
#define _SIZE_T
typedef unsigned int size_t;
#endif
#ifndef NULL
#define NULL ((void *) 0L)
#endif
#pragma SAVE
#pragma REGPARMS
extern char *strcat (char *s1, char *s2);
extern char *strncat (char *s1, char *s2, int n);
extern char strcmp (char *s1, char *s2);
extern char strncmp (char *s1, char *s2, int n);
extern char *strcpy (char *s1, char *s2);
extern char *strncpy (char *s1, char *s2, int n);
extern int strlen (char *);
extern char *strchr (const char *s, char c);
extern int strpos (const char *s, char c);
extern char *strrchr (const char *s, char c);
extern int strrpos (const char *s, char c);
extern int strspn (char *s, char *set);
extern int strcspn (char *s, char *set);
extern char *strpbrk (char *s, char *set);
extern char *strrpbrk (char *s, char *set);
extern char memcmp (void *s1, void *s2, int n);
extern void *memcpy (void *s1, void *s2, int n);
extern void *memchr (void *s, char val, int n);
extern void *memccpy (void *s1, void *s2, char val, int n);
extern void *memmove (void *s1, void *s2, int n);
extern void *memset (void *s, char val, int n);
#pragma RESTORE
/***********************************************************************/
/* This file is part of the C51 Compiler package */
/* Copyright KEIL ELEKTRONIK GmbH 1993 */
/***********************************************************************/
/* */
/* file: CALLOC.C:
*/
#include <string.h>
extern void *malloc (int);
struct mem {
struct mem xdata *next;
struct mem xdata *prev;
unsigned int len;
unsigned char mem[1];
};
void * calloc (unsigned int size, unsigned int len) {
void xdata *p;
size *= len;
p = malloc (size);
if (!p) return ((void *) 0);
memset (p, 0, size);
return (p);
}
/***********************************************************************/
/* This file is part of the C51 Compiler package */
/* Copyright KEIL ELEKTRONIK GmbH 1993 */
/***********************************************************************/
/* */
/* file: MALLOC.C:
*/
struct mem {
struct mem xdata *next;
struct mem xdata *prev;
unsigned int len;
unsigned char mem[1];
};
extern struct mem xdata *__mp__;
void *malloc (unsigned int size) {
struct mem xdata *p;
struct mem xdata *np;
if (size > 0xfffb) return ((void *) 0);
size += (sizeof (struct mem) - 1);
p = __mp__;
while (1) {
if ((((unsigned int) p->next)-((unsigned int) p) - p->len) >= size)
break;
p = p->next;
if (!p->next) return ((void *) 0);
}
if (!p->len) { p->len = size; return (p->mem); }
np = (void xdata *) p + p->len;
np->next = p->next;
np->prev = p;
p->next = np;
if (np->next) np->next->prev = np;
np->len = size;
return (np->mem);
}
/***********************************************************************/
/* This file is part of the C51 Compiler package */
/* Copyright KEIL ELEKTRONIK GmbH 1993 */
/***********************************************************************/
/* */
/* file: REALLOC.C:
*/
#include <string.h>
extern free (void *);
extern void *malloc (int);
struct mem {
struct mem xdata *next;
struct mem xdata *prev;
unsigned int len;
unsigned char mem[1];
};
void *realloc (struct mem xdata *p, unsigned int size) {
void xdata *p1;
if (!p) return ((void *) 0);
p = (void xdata *) p - (sizeof (struct mem) - 1);
if ((((unsigned int) p->next) - ((unsigned int) p)) >=
((sizeof (struct mem) - 1) + size)) {
p->len = size + sizeof (struct mem) - 1;
return (p->mem);
}
p1 = malloc (size);
if (!p1) return ((void *) 0);
memcpy (p1, p->mem, p->len);
free (p->mem);
return (p1);
}
/***********************************************************************/
/* This file is part of the C51 Compiler package */
/* Copyright KEIL ELEKTRONIK GmbH 1993 */
/***********************************************************************/
/* */
/* file: FREE.C:
*/
struct mem {
struct mem xdata *next;
struct mem xdata *prev;
unsigned int len;
unsigned char mem[1];
};
void free (struct mem xdata *p) {
struct mem xdata *op;
if (!p) return;
p = (void xdata *) p - (sizeof (struct mem) - 1);
if (op = p->prev) {
op->next = p->next;
if (p->next) p->next->prev = op;
}
else p->len = 0;
}
-from: Gabriel Rusaneanu E-Mail: rusa...@mail.dnttm.ro