HowTo : get malloc to work

dereksoftstuff wrote:
c) what's sbrk

So, just out of idle curiosity, where does the name "sbrk" come from...?

This is really a good post. Awhile back I was getting "_sbrk" errors and had no clue what this was. I searched for hours online with no resolution in sight. I finally figured out it was used by malloc, but I still didn't know what this function was supposed to do until someone in another forum provided a generic example. This one is just drop-in-and-go.

As a matter of fact, I think I'm going to use it. Mine doesn't check if I'm running off the RAM memory map.....

Hello JM

I just don't know how we can get by without dynamic memory ...

I've seen some of your posts on your project, are you going to share some of the good bits of code with us?

I'm putting together some building blocks that I'll post soon. There doesn't seem to be much about regarding simple generic code utilities etc.

The driverlib doesn't go far enough, and noone seems to be posting what they have done - is everyone building the same wheel? Or is everyone too shy ...

I'd like to see more development within the forum, so that newcomers can start off with some good stuff.
And we can create some solid flexible utilities.

Anyone else out there? or shall I continue making my own square wheel ...

I have a routine that sets up PWM and SPI to generate signals for an audio DAC for 9 common sample frequencies, and code that processes Shoutcast audio streams....that one is still kinda beta. Useful to the right person, maybe.

I thought DriverLib is fairly decent at what it is intended to do, but sometimes, like with other things, something isn't obvious. Like how to set/clear a digital output. It took a few days to figure out why the outputs I was trying to control didn't work.

dereksoftstuff wrote:
I just don't know how we can get by without dynamic memory ...
For embedded stuff - especially small embedded stuff - avoiding dynamic allocation is more the norm than the exception!

The thing is: by the time you've done all the work to determine how big your heap needs to be, and what to do if an out-of-memory happens, you might just as well have spent that time working out a suitable static allocation scheme...

Hello AN

Yes I used to use PIC's as well (PIC18) - great stuff, but those days are gone now. It had 3 or 4k RAM and not much point in using dynamic memory.
The current range of LMI M3 chips have 64k RAM - lets just say that again "64k RAM" for small embedded systems - new world ...

You probably will not be interested in my upcoming posts regading utilities and dynamic memory, but if you get the chance give it a try, you might be surprised.

I've been meaning to post this for awhile, but I am having an odd problem with the _sbrk function. It is a problem with the part of the code that checks if I'm exceeding available RAM.

With this code in place, I was having a problem where malloc was not allocating RAM, even though I knew I had enough. When I removed this code, everything worked fine. So I did some debugging....Turns out, even though I was requesting 20-some KB from malloc, the number passed to the _sbrk function was over 23 or 24K!

For now I just removed the check and make sure I have enough before asking for memory. But any ideas what is going on with this?

Nice spot, the last chunk of RAM isn't allocated.

The RAM check is OK - infact only needed if your stack starts at top of heap.

The problem is that the end of heap is at 2000fff8 and malloc wants to go to 20010000.

Therefore 2 mods :-
a) linker (remove -8)

Code:

PROVIDE ( _HEAP_END = ALIGN(ORIGIN(SRAM) + LENGTH(SRAM) ,8) );

b) sbrk
>= to >

Code:

... (nextHeap > (caddr_t)&_HEAP_END)){         return NULL; // error - no more memory

I think that there is not necessarily a 1:1 relationship between malloc calls and sbrk calls, that depends on the malloc algorithm. It might get a bit more than you requested and try and service your next request with what's left ...

Also the malloc algorithm itself will use some of the RAM to link the chunks etc.


I use the following simple utility :-
systemRAM.h & .c

Code:

#ifndef SYSTEM_RAM_H_ #define SYSTEM_RAM_H_ #include  #ifdef __cplusplus extern "C" { #endif typedef struct dynamicRAMInfoType {     UINT size;     UINT startAddr;     UINT endAddr; }; typedef void* RAM_ADDRESS; struct dynamicRAMInfoType sizeofDynamicRAM(void); boolean validHeapAddress(RAM_ADDRESS addr); RAM_ADDRESS freeMemory(RAM_ADDRESS addr); #ifdef __cplusplus } #endif #endif // SYSTEM_RAM_H_

Code:

#include  #include  #include  // linker (standalone.ld) sets heap start and end extern unsigned int  _HEAP_START; extern unsigned int  _HEAP_END; #ifdef __cplusplus extern "C" { #endif struct dynamicRAMInfoType sizeofDynamicRAM(void) {     struct dynamicRAMInfoType info;          info.startAddr = (UINT)&_HEAP_START;     info.endAddr = (UINT)&_HEAP_END;     info.size = info.endAddr - info.startAddr;          return info; } boolean validHeapAddress(RAM_ADDRESS addr) {     if (((UINT)addr >= (UINT)&_HEAP_START) &&          ((UINT)addr <>UINT)&_HEAP_END)) {         return TRUE;     } else {         return FALSE;     } } RAM_ADDRESS freeMemory(RAM_ADDRESS addr) {     free(addr);     return NULL; } #ifdef __cplusplus } #endif

Hi!

New to this forum so let me introduce myself briefly:
20 odd years of C, 15 odd years of C++, 7 years of Atmel AVR 8-bit microcontrollers in the luggage.

I recently got hold of the EKT-LM3S6965 Evaluation Kit, and am using the Code Red IDE. It rests on GCC and Eclipse just as the CodeSourcery does. (Difference is that the free version of Code Red has no size limitations, but is tied to the Ev Kit.) I am using it to evaluate programming in C++ for CortexM3's.

I've been struggling with the new-operator for more than a week now, having dug to the point where I understood that it had to do with sbrk(). I tried several sbrk() suggestions found on the net. I also tried to nick the sbrk() that is suggested in the newlib documentation. All to no avail. Upon entering sbrk() the increment was always ridicolously high (think megabytes) and have struggled on under the assumption that there was some kind of type mismatch in the call chain down to sbrk(). Not until today did I realize that LM had this forum set up, and found this thread. It took me much less than an hour to start afresh and test the suggestion here by "dereksoftstuff" and it seems to work like a charm!

Details on my implementation for Code Red:
I am setting up a C++ project thus like so:
1) File, New, C++ Project
2) In the C++ Project wizard, select Executable and then LMI C++ Project
You now have a C++ project, and can implement sbrk(). I chose to simply add it to min_cpp.c. In its default state this file implements dummy versions of malloc() and free(), where malloc() returns 0 to indicate that it failed to allocate dynamic memory. The file contains two "blocks" mutually exclusive by a #ifdef preprocessor directive.

3) Comment out the definition of CPP_NO_HEAP. This will eliminate the dummy definitions of malloc() and free() so that the linker instead will get the "real" ones out of newlib/libc.

4) In the #else block of the file, implement sbrk() as adviced by Derek. Dont forget extern [...] HEAP_START, extern [...] _HEAP_END and static [...] heap.

5) Change the linker script as adviced by Derek. For the project set up as abobe the linker script is named LM3S6965.ld .

You should now be able to test the functionality of malloc() and ultimately of the new-operator.

Great post, Derek! Thank you!

Aside: I have also wondered about the meaning of "sbrk" and have found a small tidbit on this. "brk", short for "break", was the name of the end of the heap in Unix. The "s" is not clear to me, but I'm speculation that "Set Break" (ie. change the size of the memory region holding the heap) was shortened to "sbrk".

@johanekdahl-

Great post - welcome aboard - believe that you will love these LMI devices.

Agree - derek is terrific - we owe him - thanks derek...

Hi All

Since there are obviously knowledgeable people involved in this thread I would like to try to fill in a couple of gaps.

Can someone explain the following?
1) __HEAPSIZE__ = 1024; // just 1k defined for heap use in the linker script file
2) When malloc(1) is called, _sbrk() is called with a value of 0x20. On first call the heap location is returned (in the test case 0x200007c4)
3) _srbrk() is then called again (still from initial malloc()) with the value 0x81c which seems to be setting the top of heap to the next 4k boundary(?) 0x20001000, which is however above the allocated heap range (__heap_end__ is 0x20000bc4 in the test case). This causes a NULL to be returned.
4) following mallocs() then cause _sbrk() to be called with 0x1000 and always returns a NULL
5) repeating with 4k HEAP size defined, the second _sbrk() call is successful and then the test sequence of a few malloc() and free() works normally. _sbrk() is not called any more.

Does this mean that at least 4k of heap space is required for the malloc() to guaranty that it can be used at all?

Background:
a) the system this is used in has two memory management systems at the same time. A dynamic system with no overhead (this not supporting free()) which is used for main work. This avoids management overhead for most efficient storage (1 byte can be allocated without taking more that 1 byte from heap. It also has controllable alignment which is useful for drivers which need special hardware alignment.
b) optionally malloc() can be used from the library for code which needs malloc()/free() type operation.
c) The memory layout is seen here memory layout and the HEAP size allocated to malloc() needs fixed boundaries and can not grow up to the stack space.

The following is the _sbrk() implementation:

Code:

extern int  __heap_start__; extern int  __heap_end__; extern void *_sbrk(int incr) {     static unsigned char *heap = NULL;     unsigned char *prev_heap;     if (heap == NULL) {         heap = (unsigned char *)&__heap_start__;     }     prev_heap = heap;     if ((heap + incr) >= (unsigned char *)&__heap_end__) {         return 0;     }     heap += incr;     return (void *)prev_heap; }

One would expect that it is quite easy to find GCC malloc() source code to study but this has turned out to be rather a challenge. Moreover it seems that there are various malloc() implementations and it then depends on the package being used as to which one is actually integrated. For example, previous versions of Codesourcery G++ work differently and don't need the user to supply the _sbrk() stub at all...

All in all rather confusing. Can anyone explain the exact operation as detailed from experimental results above and confirm the 4k limitation?

Regards

Mark

Hi

I would like to add some more experimental results which may be relevant.

a) as noted before, the first call of sbrk() with parameter zero is used to find out the start location of heap.
b) the second, as also noted before, requests the heap size to be increased to the next 4k boundary (why 4k boundary?). This means that the initial heap size varies somewhere between a small value and almost 4k
c) If I now try to allocate memory that doesn't fit into the available heap space, _sbrk() is called again to increase the space. It is always called with an increment value of 4k. If there is 3.9k of physical memory from the present top of heap to the end of the available space (however calculated) it will thus fail.
d) the consequence that I see is that the point at which it fails depends also on the heap start location (due to the strange first increment value). If a _sbrk() call is just successful (just enough remaining to allocate the next 4k block) all is well and in fact there may be then well over 3k of free heap left (if the last malloc() call only uses a small value). If variables in the system are added/removed it will reposition the starting location of heap and possibly change this so that the final 4k block request will suddenly fail (eg. when there is only 3.99k free), even if the malloc() caller only wants 1 byte form heap.

My present conclusion is that the malloc(), _sbrk() technique used by this GCC implementation requires a certain amount of margin (certainly over 4k and preferably at least 8k) to ensure that it can tolerate changes in memory use without sudden failure. A minimum heap size of 4k is required to guaranty that the first heap size increment will work. A minimum heap size of 8k is required to guaranty that the second heap size increment will always work. The second heap size increment will, in the worst case, allocate only around 4k of actual heap for use so a 4k overhead should be available. Due to some management overhead (which is also on heap) the values should be increased also by at least 20 bytes plus around 16 per actual malloc() chunk on heap.

Have I understood this correctly???

Regards

Mark

www.uTasker.com

If you are linking with newlib then the source for malloc ought to be at the RedHat site (http://sourceware.org/newlib/).

If you download a snapshot then the path, including tarballs and stuff, is:

newlib-1.17.0.tar.gz/newlib-1.17.0.tar/newlib-1.17.0/newlib/libc/stdlib/malloc.c

Post edited by: johanekdahl, at: 2009/01/26 03:53
Forum software seems to dislike backslashes - replaced by forward slashes.

Post edited by: johanekdahl, at: 2009/01/26 03:55

Hello Mark

a) It's important to understand the interface relationship :-

User -> malloc -> sbrk

Analogy

Customer -> shop -> Warehouse

sbrk is a BULK memory allocator, so it allocates BIG chunks of the heap to malloc (not the User).

It seems that the default pagesize is 4k bytes, so this is a chunk.

b) The only important thing to the User is the HEAP SIZE (= HEAP END - HEAP START)

The utility posted here will give you all 3 of these values.
The HEAP START is set by the linker, and so will vary from build to build.


c) malloc, realloc ... need to know where to start their memory allocation from.
So at initialisation, at least 2 calls to sbrk are needed - first to find the HEAP START, and next to find the first chunk (This will be on a 4k boundary).
If the HEAP SIZE is < 4k="" (or="" last="" chunk="" to="" be="" allocated)="" then="" the="" sbrk="" will="" return="" nextheap="HEAP" end="" (0x20010000="" here).="">
Future calls to sbrk will return NULL to malloc. No more Heap!

malloc allocates memory to the user, so when we call malloc(n) n = num bytes, malloc will try to service our request from its own resources.
If it can not it will call sbrk for more BULK memory.

Therefore, just because sbrk says to malloc that there is no more BULK memory, does not mean that malloc can not fulfill our next call to it.
That will depend on 'n' and the resources malloc already has.

Obviously, if the system has 10k HEAP SIZE, and we malloc with n = 11k, no joy, and malloc will return NULL to User.
We will not be able to use every byte of the Heap, beacuse malloc will have an overhead.
From initial testing this seems to be ~ 1 -> 1.5k bytes.
If the system has 3k HEAP SIZE, and we malloc with n = 1800 ok, n = 1850 fails.

malloc does all the memory management including updating it's map for User Free()'s etc, so the memory available at any given time will vary.

d) a simple test program

Put a print in sbrk for nextHeap returned, and match to succesive malloc calls in test app - separate with a few seconds delay so that you can see the behaviour between malloc and sbrk.

e) details of malloc & mallocr (reentrant) are in the libc (newlib) sources from codesourcery g++.
I don't think you can configure anything externally, so a new build of libc would have to be done.

Hope this helps ...