Author Topic: own malloc implementation, metal bare, looking for sources  (Read 10948 times)

0 Members and 1 Guest are viewing this topic.

Offline westfw

  • Super Contributor
  • ***
  • Posts: 2529
  • Country: us
Re: own malloc implementation, metal bare, looking for sources
« Reply #25 on: October 27, 2015, 12:23:18 pm »
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
:palm: )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...
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 2797
  • Country: 00
Re: own malloc implementation, metal bare, looking for sources
« Reply #26 on: October 27, 2015, 10:11:18 pm »
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  |O

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  :palm: :palm: :palm: :palm:

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)  :palm: :palm: :palm: )
  • 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
the Bunker is open!
 

Offline opty

  • Regular Contributor
  • *
  • Posts: 55
  • Country: ie
Re: own malloc implementation, metal bare, looking for sources
« Reply #27 on: October 27, 2015, 10:11:42 pm »
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,
 

Offline 0xdeadbeef

  • Frequent Contributor
  • **
  • Posts: 997
  • Country: de
Re: own malloc implementation, metal bare, looking for sources
« Reply #28 on: October 27, 2015, 10:29:24 pm »
(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.
Trying is the first step towards failure - Homer J. Simpson
 

Offline Mechatrommer

  • Super Contributor
  • ***
  • Posts: 7946
  • Country: my
  • reassessing directives...
Re: own malloc implementation, metal bare, looking for sources
« Reply #29 on: October 27, 2015, 10:53:15 pm »
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)...
if something can select, how cant it be intelligent? if something is intelligent, how cant it exist?
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 2797
  • Country: 00
Re: own malloc implementation, metal bare, looking for sources
« Reply #30 on: October 27, 2015, 11:28:02 pm »
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  :)
the Bunker is open!
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 2797
  • Country: 00
Re: own malloc implementation, metal bare, looking for sources
« Reply #31 on: October 27, 2015, 11:32:13 pm »
interesting DO-178B Process Visual Summary about the project life cycle  :D
the Bunker is open!
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 2797
  • Country: 00
Re: own malloc implementation, metal bare, looking for sources
« Reply #32 on: October 27, 2015, 11:42:25 pm »
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)
the Bunker is open!
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 2797
  • Country: 00
Re: own malloc implementation, metal bare, looking for sources
« Reply #33 on: October 27, 2015, 11:43:36 pm »
You can start here (nicely explained implementation idea): http://www.nongnu.org/avr-libc/user-manual/malloc.html

excellent, thank you  :-+
the Bunker is open!
 

Online Kalvin

  • Super Contributor
  • ***
  • Posts: 1651
  • Country: fi
  • Embedded SW/HW.
Re: own malloc implementation, metal bare, looking for sources
« Reply #34 on: October 28, 2015, 12:46:06 am »
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.
 

Offline Mechatrommer

  • Super Contributor
  • ***
  • Posts: 7946
  • Country: my
  • reassessing directives...
Re: own malloc implementation, metal bare, looking for sources
« Reply #35 on: October 28, 2015, 01:13:54 am »
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...
if something can select, how cant it be intelligent? if something is intelligent, how cant it exist?
 

Offline BloodyCactus

  • Frequent Contributor
  • **
  • Posts: 459
  • Country: us
Re: own malloc implementation, metal bare, looking for sources
« Reply #36 on: October 28, 2015, 01:39:28 am »
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
 

Offline JacquesBBB

  • Frequent Contributor
  • **
  • Posts: 784
  • Country: fr
Re: own malloc implementation, metal bare, looking for sources
« Reply #37 on: October 28, 2015, 01:56:10 pm »
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.

 

Offline amyk

  • Super Contributor
  • ***
  • Posts: 5568
Re: own malloc implementation, metal bare, looking for sources
« Reply #38 on: October 28, 2015, 06:30:40 pm »
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.
 

Offline Mechatrommer

  • Super Contributor
  • ***
  • Posts: 7946
  • Country: my
  • reassessing directives...
Re: own malloc implementation, metal bare, looking for sources
« Reply #39 on: October 28, 2015, 09:32:50 pm »
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 :scared:
if something can select, how cant it be intelligent? if something is intelligent, how cant it exist?
 

Offline Mechatrommer

  • Super Contributor
  • ***
  • Posts: 7946
  • Country: my
  • reassessing directives...
Re: own malloc implementation, metal bare, looking for sources
« Reply #40 on: October 28, 2015, 10:18:03 pm »
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.
if something can select, how cant it be intelligent? if something is intelligent, how cant it exist?
 

Offline JacquesBBB

  • Frequent Contributor
  • **
  • Posts: 784
  • Country: fr
Re: own malloc implementation, metal bare, looking for sources
« Reply #41 on: October 28, 2015, 11:29:24 pm »
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.
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 2797
  • Country: 00
Re: own malloc implementation, metal bare, looking for sources
« Reply #42 on: October 29, 2015, 12:29:13 am »
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  :D
the Bunker is open!
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 2797
  • Country: 00
Re: own malloc implementation, metal bare, looking for sources
« Reply #43 on: October 29, 2015, 05:36:50 pm »
interesting article, Justifiably taboo: Avoiding malloc()/free() APIs in military/aerospace embedded code  :)
the Bunker is open!
 

Offline bson

  • Supporter
  • ****
  • Posts: 1050
  • Country: us
Re: own malloc implementation, metal bare, looking for sources
« Reply #44 on: October 29, 2015, 05:58:51 pm »
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.
« Last Edit: October 29, 2015, 06:02:20 pm by bson »
<This space intentionally left blank>
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf