own malloc implementation, metal bare, looking for sources

[legacy]

hi guys
before reinventing the wheel, I wonder if there something well-written around.
I have a metal bare system, 64Kbyte of heap, and I'd like to support malloc.

[legacy]

memory compaction is not allowed, I do not have virtual memory

[dmills]

I don't think it is actually possible to write a standard conforming malloc in standard conforming C (Malloc is guaranteed to meet the alignment requirements of any type), but you can write something that is close enough for a particular platform.

Now with 64K of ram, doing so is a really, really bad idea in general, because memory fragmentation will end up biting you,  and that tends to be an issue after weeks of runtime, not something that happens immediately.

Regards, Dan.

[Jeroen3]

Embedded operating system often have some kind of memory management API that is non-standard. (in it does not use C-runtime libraries)
Such as Chibios http://www.chibios.org/dokuwiki/doku.php

As long as you do not need multiple chained blocks, something like this would be manageable without fragmentation.

[amyk]

You can find the CP/M sources and look at those. 64K address space for the whole system and they did fit in a memory allocator. It's a simple one, probably could be written in less than a day's work.

[legacy]

because memory fragmentation will end up biting you,  and that tends to be an issue after weeks of runtime, not something that happens immediately.

is there a stress test that can help ?
any advice, trick to look ahead during the development ?

[Jeroen3]

Memory fragmentation happens when your memory allocation block size is smaller than the chunk required by the largest consumer. Without memory management unit (virtual address space) you will run into denied mallocs. And only when memory is actually freed, obviously.
Make the block size equal or larger than the chunk of the biggest consumer, and you will not have this drawback.

If the design allows for fragmentation to happen, it will happen sometime. Unless you have some very deterministic system, but then you wouldn't need a memory manager anyways.
There is no stress test, simply because it's not a "if" but a "when". You don't want to develop a system that has to be rebooted once every x hours do you?

https://en.wikipedia.org/wiki/Fragmentation_(computing)

[Mechatrommer]

You don't want to develop a system that has to be rebooted once every x hours do you?

defragmenting process should help... planning during failed memory request should help... better than reboot.

[c4757p]

Defragmenting? As in, moving blocks around that have already been allocated? I'd like to see you try.

[westfw]

The avr-libc implementation is probably a good starting point.
How well a particular malloc() implementation works, in the face of relatively limited memory, is likely to be highly dependent on the particular application.
A version of malloc() that 'works well' when there is nearly unlimited memory to use, is not particularly interesting.

Do you have an OS and some sort of "task" abstraction?  You can certainly save yourself lots of trouble by implementing malloc() but NOT free() (except as part of task destruction.)   :-)

[John_ITIC]

hi guys
before reinventing the wheel, I wonder if there something well-written around.
I have a metal bare system, 64Kbyte of heap, and I'd like to support malloc.

Since you only have 64K heap then you are obviously running a very limited, small microcontroller. In this case, knowing what the allocation pattern is of your application, you could easily roll your own heap management code. This is quite simple; you simply divide up your available heap into a number of fixed chunk that you dole out. If the requested size is smaller then your block size, return one chunk never the less. If your requested size if larger; return multiple blocks. Having fixed size blocks is the only way to avoid fragmentation. The down-size, of course, is that there is an overhead if the application allocates chunks of memory not aligned with the block size. However, this doesn't matter as long as you have enough heap-size for your application.

one trick is to put a header in the first few bytes in the initial block being passed out that tells the heap code how large the chunk is when the application later calls your 'free' function. The application then is passed a pointer that points a few bytes into  block (past the header). You then avoid having to maintain a local table of blocks given out and their sizes (saving some memory).

[Howardlong]

Defragmenting? As in, moving blocks around that have already been allocated? I'd like to see you try.

Handles, aka double dereferencing. Oh, those were the days, my first Mac programming back in the mid 80s.

Downsides are twofold. Firstly, the overhead of double dereferencing, secondly the joys of random heap re-organisation, almost as bad as garbage collection.

And the answer is, if you're doing real time resource limited embedded systems, avoid dynamic memory allocation on the heap.

[djacobow]

Andrei Alexandrescu gave a nice talk on allocators at CppCon 2015:

It's somewhat c++ specific, but he's advocating thinking of allocation and object creation quite separately, so the former can easily be applied to malloc as well as it could to new.

His basic point is that it's hard, but probably the right strategy is to, once you understand how your app uses memory to create multiple allocators for different sizes and alignments and then have a master allocator that dispatches to one of the others based on the type/size being requested.

I've spent enough time in small-memory embedded systems that I have to say I don't personally recommend trying to solve the fragmentation problem by making a smarter allocator. If you can, don't use dynamic memory. Otherwise, if you program just does a lot of allocations at startup and doesn't free anything, then don't worry about it, it'll be fine with just a simple buffer-pointer-increment-and-round allocator. If it does malloc/free a lot, then change your program! It's an embedded disaster in the making. Make that stop happening by changing your code. Allocate buffers in advance and reuse them, perhaps in a ring if necessary.

[Mechatrommer]

Handles, aka double dereferencing. Oh, those were the days, my first Mac programming back in the mid 80s.

i think most modern flat memory model OSes still using this method esp on their own managed objects.. for real pointers, it doesnt matter if one has 64K or 8K of RAM compared to 100GB of RAM, if you dont use them wisely, the machine is going to either reboot or converge to a temporal halt, regardless... so it will go down to programmers to behave their App.

Firstly, the overhead of double dereferencing.

anything "managed" as in dynamic alloc fragmented multiple chain block, virtual table etc will have onetime and runtime overhead back of the screen. the only thing that doesnt have overhead is bare metal..

actually i'm confused with the OP why he need ready made malloc on his specific machine? whats wrong with GCC? gcc's malloc works on 8K RAM avr, so why not just code away? i guess in any system's API memory manager, inevitably you'll need to study the nitty gritty of it, everything has pro and con, nothing is free meal... and i think an attempt to support fragmentation without virtual or temporary memory swap is a joke... just go bare metal and BOM your own memory manually.

[legacy]

For what I know most major platforms have glibc or whatever types of libc from compiler packages, even on bare metal, so why writing your own?

cause it's a must, customer requirement!
(do not believe you can use glib in avionics)

[legacy]

Do you have an OS and some sort of "task" abstraction?

unfortunately no

You can certainly save yourself lots of trouble by implementing malloc() but NOT free() (except as part of task destruction.)

good trick

[djacobow]

(do not believe you can use glib in avionics)

Someone once told me that it was common practice (if not standard) in avionics not call malloc() after the wheels have departed the pavement, and not call free(), well, ever. Any truth to that?

[legacy]

Since you only have 64K heap then you are obviously running a very limited, small microcontroller. In this case, knowing what the allocation pattern is of your application, you could easily roll your own heap management code. This is quite simple; you simply divide up your available heap into a number of fixed chunk that you dole out. If the requested size is smaller then your block size, return one chunk never the less. If your requested size if larger; return multiple blocks. Having fixed size blocks is the only way to avoid fragmentation. The down-size, of course, is that there is an overhead if the application allocates chunks of memory not aligned with the block size. However, this doesn't matter as long as you have enough heap-size for your application.

one trick is to put a header in the first few bytes in the initial block being passed out that tells the heap code how large the chunk is when the application later calls your 'free' function. The application then is passed a pointer that points a few bytes into  block (past the header). You then avoid having to maintain a local table of blocks given out and their sizes (saving some memory).

thank you, it sounds like a good trick 

in the ideal world, you get in advance the documentation from your partner, while in the real world … it happens it's not documented yet, I got no documentation from the team, and I am allocated to a different task. I am supporting the Board Support Package (BSP&C), so the whole activity will be handled like "code integration", their work + my work merged into the final commit, but as I have sources, I can analyze the application that I have to support, so I can have an idea about its dynamic memory requirement 

[legacy]

Someone once told me that it was common practice (if not standard) in avionics not call malloc() after the wheels have departed the pavement, and not call free(), well, ever. Any truth to that?

iit's banned by DO178A + MIL-STD from level C to level A, while my task is level E, so they are tolerant about malloc, and they are tolerant because the other team has to port a software that uses a lot of dynamic memory. I do no have the power and the authority to say what has to be allowed or rejected, I got a task (BSP), and I have to provide a solution, and in this solution I can't simply "reuse" glibc because they said NO (already asked about )

[legacy]

p.s.
If i will have success, I might access the level D, call it "career progress" 
you get more responsabilities, more money, even if you lose a few freedom of degree, e.g. you can no more use malloc

if I will not have success, I will stay on level E, but if they really want to punish me, they will make me segregated to the "cave-office", with tasks like .. documentation, which might also imply the documentation of the documentation ,which is worst than cleaning the dust in Hell for a (wanna be real avionic) developer 

[nctnico]

I once made a malloc based on a linked-list (chained blocks) memory manager. It had 2 APIs: one to use the memory manager as a buffer using dynamic memory blocks in a random order chain and one API which supported malloc, free and even realloc. In case of malloc it looked for consequtive chain of blocks so a pointer could be used to point to the first block. It wasn't fast but it worked quite well. Whatever you create make sure to unit test it on a PC! I also added some functions which could dump an overview of blocks and I think I also (in a debug mode) kept track of from where the allocation was called (that info is in the stack frame so it takes some inline asm to figure that out). In case a piece of memory is never freed you can see from where it was created.

[legacy]

I have found this topic on the avrfreaks (avr8) forum, arguing "why using malloc" 

[AlfBaz]

Hi Legacy
Have you looked at Doug Lee's malloc implementation?

I came across it years ago when looking into Microchip's version for a very old version of their C32 compiler (pre V1.12)
It seems to do the business and is well commented and documented
You can find a description of it here
and according to google the source can be found here ftp://g.oswego.edu/pub/misc/malloc.c or simply search for doug lee malloc

[Jeroen3]

This is really easy and found in almost every rtos.
http://chibios.sourceforge.net/docs3/rt/chheap_8c.html
https://github.com/contiki-os/contiki/wiki/Memory-allocation
Basic rule is to never require more than one base block of sequential memory. You can use two or more, but never assume they are concatenated.

[westfw]

Quote

I do no have the power and the authority to say what has to be allowed or rejected, I got a task (BSP), and I have to provide a solution, and in this solution I can't simply "reuse" glibc because they said NO (already asked about

)This is the sort of crap I always end up seeing that makes it really difficult to take "code quality assurance standards" seriously.   "I need to use X"  "You may not use the <industry standard> X code/technique.  You must write your own version of X, from scratch."  Like that will somehow be higher in quality.

So, if you were using a commercial compiler (greenhills, Keil, IAR), would you be allowed to use their malloc() implementation?   How about one of the hybrids with a "supported" library?   This *is* one reason that companies pay big bucks for marginally better compilers...

[legacy]

So, if you were using a commercial compiler (greenhills, Keil, IAR)

AdaMulti-packet {C, ADA}, by GreenHills

would you be allowed to use their malloc() implementation? 

no, they haven't bought the "verified version" for metal bare, they got a kernel from GreenHills which comes with its verified stuff (I am not authorized to browse sources, they are level A-C, I physically do not have the password to the repository), while I am on my own way with meal bare (BSP, iBSP, etc) and I had to rewrite the full crt0 

target:PowerPC460, don't ask me WHY I had to rewrite the crt0 (in assembly) providing them a piece of paper which assures them that there is a "cache invalidation" before invoking "main": it's a requirement, and I had to show them I have satisfied it 

the job-activity consists of the following parts

• you get requirements
• you have to fight to get the documentation (which is never ready and detailed)
• you get a passfree to access the hardware (which is available only for 4 hour a day, sometimes 5 minutes a day (their coffee break)  )
• you can't ever argue with your executive manager, ever
• you have to satisfy all the requirements
• you have to prove you have satisfied all of them through test activity plus documentation (called ATP, ATR, etc, TP=test plan, TR=test report)
• your work has to pass all the QA checks (other dudes will verify your documentation and sources)
• if everything is OK (which usually implies 3-4 iterations between you and QA dudes), your "engineering draft version" will be committed as "production version"

How about one of the hybrids with a "supported" library?   This *is* one reason that companies pay big bucks for marginally better compilers...

the executive manager has asked me to develop, and that's all I know, but from my point of view it's good: task assigned, money paid, good occasion to make career points, what they want to do/the reason why, it's all up to their choices 

you are right: they (avionics dudes) are crazy, no doubt about that

[opty]

If you haven't already please have a look at malloc() implementation in avr-gcc

You can start here (nicely explained implementation idea): http://www.nongnu.org/avr-libc/user-manual/malloc.html

ps. when I first read this doc I was GREATLY surprised how simple it actually is.

Opty,

[0xdeadbeef]

(do not believe you can use glib in avionics)

Honestly, with a 64k heap and a safety relevant environment (avionics), I wonder if dynamic RAM allocation is a good idea anyway.
E.g. what happens if there is no heap left? On a desktop system you throw a warning and everything is good. In an embedded system working in a car or plane, every possible kind of error reaction is undesired.
-> In safety relevant systems with limited heap, usually either static or pseudo-dynamic allocation strategies are used.
Where "pseudo-dynamic" means that functions can allocate RAM once after a reset, but RAM can only be "freed"/reallocated by a reset.
Like you have different memory setups you can chose from after a reset (e.g. to handle different hardware variants or operation modes) with different memory layouts, but each of them is static during runtime.

[Mechatrommer]

Honestly, with a 64k heap and a safety relevant environment (avionics), I wonder if dynamic RAM allocation is a good idea anyway.

dynamic allocations and deallocations utility + carefull allocations deallocations strategy is possible if its "custom" to the target environment. but asking for a generalized ready made household usage example is quite nonsensical imho, esp in classified environment as in military (edit: except for learning purpose ymmv)...

[legacy]

In an embedded system working in a car or plane, every possible kind of error reaction is undesired

• Level-A, Failure condition is Catastrophic, Failure may cause a crash. Error or loss of critical function required to safely fly and land aircraft
• Level-B, Failure condition is Hazardous, Failure has a large negative impact on safety or performance, or reduces the ability of the crew to operate the aircraft due to physical distress or a higher workload, or causes serious or fatal injuries among the passengers. (Safety-significant)
• Level-C, Failure condition is Major, Failure is significant, but has a lesser impact than a Hazardous failure (for example, leads to passenger discomfort rather than injuries) or significantly increases crew workload (safety related)
• Level-D, Failure condition is Minor, Failure is noticeable, but has a lesser impact than a Major failure (for example, causing passenger inconvenience or a routine flight plan change)
• Level-E, Failure condition is No Effect, Failure has no impact on safety, aircraft operation, or crew workload.

I am assigned with Level-E 

[legacy]

interesting DO-178B Process Visual Summary about the project life cycle 

[legacy]

dynamic allocations and deallocations utility + carefull allocations deallocations strategy is possible if its "custom" to the target environment. but asking for a generalized ready made household usage example is quite nonsensical imho, esp in classified environment as in military

it's of course custom to their target environment usage, but I do not have documentation because it's not ready yet, so I am the preliminary phase, looking around, acquire know/how, prepare a draft, roll your stones … once I get the access the hardware I also get the documentation, and I can finalize the custom-malloc

(they are crazy about that)

[legacy]

You can start here (nicely explained implementation idea): http://www.nongnu.org/avr-libc/user-manual/malloc.html

excellent, thank you 

[Kalvin]

If you have control of the software design process, you should consider dumping malloc and use resource pools instead in order to prevent the heap defragmentation and/or heap starvation. However, typically malloc can be used safely at the system startup phase allocating the resources needed, but the allocated memory is never released by free(). In that case the malloc implementattion will be really simple.

[Mechatrommer]

dynamic allocations and deallocations utility + carefull allocations deallocations strategy is possible if its "custom" to the target environment. but asking for a generalized ready made household usage example is quite nonsensical imho, esp in classified environment as in military

but I do not have documentation because it's not ready yet

well now i see it, this is maximus trouble. expected for the worst. you are in literature study stage, not trying to pick one particular method yet. this means reading all malloc implementation from big pc to very tiny mcu library, from the basic to the advanced, get the feel of many optimization and data structuring strategies and all relevant to the known environment. you are expected to be a fully equipped soldier when the doc is at hand. right now pick one best malloc is not the way, right now is read all malloc all notes way, not much time for foruming in this situation...

[BloodyCactus]

when I had to do a simple malloc in the past, I did msdos style MCB / memory control block scheme. allocate one huge chunk, ie: yor single pool. and mark a header. then when you allocate a chunk, just subtrct from the pool  + header size, when you free, compact the above + below block markers, then you reduce fragmentation. code for this type of simple block walking allocator is all over the net these days. the mcb method is very easy to understand

[JacquesBBB]

Long ago (25 yrs) i needed a malloc for a computer algebra system. I simply used the one in kernighan  & ritchie. It was very short, simple and very effective.
Search google for it.

[amyk]

This is the sort of crap I always end up seeing that makes it really difficult to take "code quality assurance standards" seriously.   "I need to use X"  "You may not use the <industry standard> X code/technique.  You must write your own version of X, from scratch."  Like that will somehow be higher in quality.

As avionics was mentioned, I think the reason has to do with liability - they want someone they can point at and blame when something goes wrong.

[Mechatrommer]

they want someone they can point at and blame when something goes wrong.

and that someone better be ready with an answer or debug solution overnight, they at the top are expecting a good "library maker", the 2nd highest ranking in programmers community according to the_my_own scale. so the OP must become one

[Mechatrommer]

well assuming... the rules are only.... dont use anyone elses' code and Level-E failure....
then KISS make the simplest malloc... record the allocated memory and empty spaces, and its location etc in housekeeping table wherever it is i'm guessing the heap itself. merge adjacent empty spaces during free(), and in any case malloc size request > largest empty chunk, return null. let the other programmers at the top deal with it... fragmentation is not allowed in memory manager, period. if they ask why tell them fragmentations cost spaces in housekeeping and we have only 64K of ram for flying a plane with human lifes on board or an multimillions dollar UAV whatever it is, period.

[JacquesBBB]

This is a link to a commented version of the k&r  malloc code
With the code

http://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book

I must say i used the original k&r. Maybe with some corrections.

[legacy]

well assuming... the rules are only.... dont use anyone elses' code and Level-E failure....
then KISS make the simplest malloc... record the allocated memory and empty spaces, and its location etc in housekeeping table wherever it is i'm guessing the heap itself. merge adjacent empty spaces during free(), and in any case malloc size request > largest empty chunk, return null. let the other programmers at the top deal with it... fragmentation is not allowed in memory manager, period. if they ask why tell them fragmentations cost spaces in housekeeping and we have only 64K of ram for flying a plane with human lifes on board or an multimillions dollar UAV whatever it is, period.

thank you for your tricks 

[legacy]

interesting article, Justifiably taboo: Avoiding malloc()/free() APIs in military/aerospace embedded code 

[bson]

I've used dlmalloc for many projects.  It merely requires an sbrk() like function to obtain more heap and the actual functions used are found in a bunch of #defines.  So you set a pointer to the start of your heap, and as dlmalloc asks for more you advance the pointer and return the pre-advance value.  If it gets to the end of the heap you're out of memory.  It never returns anything but integrates it into the heap and keeps reusing it, so manages any fragmentation for you.  It's a good allocator for simple uses, but not so great for highly threaded software, and has no well-defined complexity; I wouldn't trust it for anything that requires hard real time response times.  For those kinds of uses, preallocation is usually a perfectly fine strategy anyway.  And of course, you should never ever allocate or free heap data in an interrupt handler; those kinds of uses are better served with pre-provisioning buffers and maintaining a free list.  But it works well for all sort of non-critical application code (parsing, rendering, etc).

It can do more, but all you need in a simple uC type system is an sbrk and no shrinkage.