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

0 Members and 1 Guest are viewing this topic.

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
own malloc implementation, metal bare, looking for sources
« on: October 25, 2015, 08:39:41 am »
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.
 

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #1 on: October 25, 2015, 08:46:52 am »
memory compaction is not allowed, I do not have virtual memory
 

Offline dmills

  • Super Contributor
  • ***
  • Posts: 2093
  • Country: gb
Re: own malloc implementation, metal bare, looking for sources
« Reply #2 on: October 25, 2015, 11:31:10 am »
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.
 

Offline Jeroen3

  • Super Contributor
  • ***
  • Posts: 4067
  • Country: nl
  • Embedded Engineer
    • jeroen3.nl
Re: own malloc implementation, metal bare, looking for sources
« Reply #3 on: October 25, 2015, 12:11:15 pm »
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.
 

Offline amyk

  • Super Contributor
  • ***
  • Posts: 8240
Re: own malloc implementation, metal bare, looking for sources
« Reply #4 on: October 25, 2015, 12:14:14 pm »
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.
 

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #5 on: October 25, 2015, 06:58:40 pm »
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 ?
 

Offline Jeroen3

  • Super Contributor
  • ***
  • Posts: 4067
  • Country: nl
  • Embedded Engineer
    • jeroen3.nl
Re: own malloc implementation, metal bare, looking for sources
« Reply #6 on: October 25, 2015, 07:30:45 pm »
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)

 

Online Mechatrommer

  • Super Contributor
  • ***
  • Posts: 11537
  • Country: my
  • reassessing directives...
Re: own malloc implementation, metal bare, looking for sources
« Reply #7 on: October 26, 2015, 01:15:35 am »
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.
Nature: Evolution and the Illusion of Randomness (Stephen L. Talbott): Its now indisputable that... organisms “expertise” contextualizes its genome, and its nonsense to say that these powers are under the control of the genome being contextualized - Barbara McClintock
 

Offline c4757p

  • Super Contributor
  • ***
  • Posts: 7799
  • Country: us
  • adieu
Re: own malloc implementation, metal bare, looking for sources
« Reply #8 on: October 26, 2015, 01:17:46 am »
Defragmenting? As in, moving blocks around that have already been allocated? I'd like to see you try. :popcorn:
No longer active here - try the IRC channel if you just can't be without me :)
 

Offline westfw

  • Super Contributor
  • ***
  • Posts: 4196
  • Country: us
Re: own malloc implementation, metal bare, looking for sources
« Reply #9 on: October 26, 2015, 01:53:30 am »
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.)   :-)
 

Offline John_ITIC

  • Frequent Contributor
  • **
  • Posts: 507
  • Country: us
  • ITIC Protocol Analyzers
    • International Test Instruments Corporation
Re: own malloc implementation, metal bare, looking for sources
« Reply #10 on: October 26, 2015, 02:00:51 am »
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).
Pocket-Sized USB 2.0 LS/FS/HS Protocol Analyzer Model 1480A with OTG decoding.
Pocket-sized PCI Express 1.1 Protocol Analyzer Model 2500A. 2.5 Gbps with x1, x2 and x4 lane widths.
https://www.internationaltestinstruments.com
 

Online Howardlong

  • Super Contributor
  • ***
  • Posts: 5315
  • Country: gb
Re: own malloc implementation, metal bare, looking for sources
« Reply #11 on: October 26, 2015, 02:40:54 am »
Defragmenting? As in, moving blocks around that have already been allocated? I'd like to see you try. :popcorn:

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.
 

Offline djacobow

  • Super Contributor
  • ***
  • Posts: 1151
  • Country: us
  • takin' it apart since the 70's
Re: own malloc implementation, metal bare, looking for sources
« Reply #12 on: October 26, 2015, 03:22:52 am »
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.
« Last Edit: October 26, 2015, 03:25:33 am by djacobow »
 

Online Mechatrommer

  • Super Contributor
  • ***
  • Posts: 11537
  • Country: my
  • reassessing directives...
Re: own malloc implementation, metal bare, looking for sources
« Reply #13 on: October 26, 2015, 05:07:18 am »
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.
« Last Edit: October 26, 2015, 05:12:04 am by Mechatrommer »
Nature: Evolution and the Illusion of Randomness (Stephen L. Talbott): Its now indisputable that... organisms “expertise” contextualizes its genome, and its nonsense to say that these powers are under the control of the genome being contextualized - Barbara McClintock
 

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #14 on: October 26, 2015, 03:09:36 pm »
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)
 

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #15 on: October 26, 2015, 03:24:11 pm »
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 :D
 

Offline djacobow

  • Super Contributor
  • ***
  • Posts: 1151
  • Country: us
  • takin' it apart since the 70's
Re: own malloc implementation, metal bare, looking for sources
« Reply #16 on: October 26, 2015, 03:31:22 pm »
(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?
 

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #17 on: October 26, 2015, 03:36:16 pm »
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  :D

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

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #18 on: October 26, 2015, 03:44:59 pm »
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 :palm: )

 

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #19 on: October 26, 2015, 03:54:34 pm »
p.s.
If i will have success, I might access the level D, call it "career progress:D
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  :-DD
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 26755
  • Country: nl
    • NCT Developments
Re: own malloc implementation, metal bare, looking for sources
« Reply #20 on: October 26, 2015, 04:02:22 pm »
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.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: own malloc implementation, metal bare, looking for sources
« Reply #21 on: October 26, 2015, 04:02:43 pm »
I have found this topic on the avrfreaks (avr8) forum, arguing "why using malloc:-+
 

Offline AlfBaz

  • Super Contributor
  • ***
  • Posts: 2183
  • Country: au
Re: own malloc implementation, metal bare, looking for sources
« Reply #22 on: October 26, 2015, 05:53:50 pm »
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
 

Offline Jeroen3

  • Super Contributor
  • ***
  • Posts: 4067
  • Country: nl
  • Embedded Engineer
    • jeroen3.nl
Re: own malloc implementation, metal bare, looking for sources
« Reply #23 on: October 26, 2015, 06:13:55 pm »
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.

 

Offline westfw

  • Super Contributor
  • ***
  • Posts: 4196
  • Country: us
Re: own malloc implementation, metal bare, looking for sources
« Reply #24 on: October 27, 2015, 01:23:18 am »
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...
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf