own malloc implementation, metal bare, looking for sources

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