Having trouble avoiding malloc on embedded ARM, suggestions?

[jnz]

Have an ARM chip with 128K RAM, I almost certainly have enough for anything I’ll want to do but not entirely certain and I don’t really have a say to solve my problem that I like.


Scenario is I have a stream of data coming in. It could be 20 bytes to 2,048 bytes. I need the entire stream received, block decrypt it, then store it for another function to use. There are 10 types of data that can come in and while i can only handle one “7” type at a time, I could handle a “3” and a “7” concurrently. If a “7” comes in while I’m working on a “7” I ignore it. Further complicated that “6” “7” and “8” types can not run concurrently, so they “could” share memory.

Problem is, I either statically allocate 20K or RAM in 2K chunks which seems very wasteful as most data blocks will be far less than that 2,048 worst case, I use malloc() and free() carefully, or I try and manage the memory myself by declaring a block and allocating and freeing from inside that manually.

Am I missing an obvious option?

I read a lot of malloc() hate for embedded but it would make things seem clearer.

[ataradov]

malloc-style allocation work if you have  predictable and limited processing time. This will eliminate problems with memory fragmentation. In that case, even if holes are formed, they are naturally eliminated and don't hang around for a long time. It will work for quick processing of frames.

Just never allocate long-living structures, that's a path to disaster.

I would not use malloc directly, but a custom implementation that may benefit from specific knowledge of the data size limits and allocation patterns. This approach also eliminates casual use for other things

[Kalvin]

Here is a nice article on memory pools in embedded systems:
https://barrgroup.com/Embedded-Systems/How-To/Malloc-Free-Dynamic-Memory-Allocation

[Mechatrommer]

Problem is, I either statically allocate 20K or RAM in 2K chunks which seems very wasteful as most data blocks will be far less than that 2,048 worst case

what is datatype sized 2048? is there possibility 10 consecutive of this datatype occured? if yes, allocating 20K is not a wastefull strategy. but not enough information given, such as how fast can you process data when they keep coming, you need to decide worst case scenario about how many data left in the buffer before you can process them, how much data to ignore etc etc. the keyword to this type of problem is "circular buffer", you set how many you want and then you decide how much faster to process them, this afaik is done in any hardware communication channels such as SPI, UART I2C etc, some mcu may provide only 1 or 2 bytes, some maybe many, you process slower than datarate coming in, you lose data, simple as that. knowing your worst case scenario and case specification will tell you how much memory to be allocated permanently.

I read a lot of malloc() hate for embedded but it would make things seem clearer.

malloc is just a tool, if you dont know how to use it, it will bite you in the butt...

[MosherIV]

Hi

As Mecatrommer says, circular buffers as definitely a good idea.

Use the concept of a 'communications protocol stack'. What that means in practise is that your code to handle each stage is seperated into different parts/layers.
Start with the receive layer. Keep this small,fast and short. No need to assemble whole message packet. Just get data and pass onto next layer.
Next layer assembles the whole message/packet. Pass it onto next layer.
Next layer decodes type of message and passes on to correct decoder. Etc

Keep the buffers for each layer the appropriate size.

Not using malloc/free is only essential in safety critical application.

[poorchava]

I'd consider using an RTOS of some type as they generally have heap allocation implemented as well as mechanisms for detecting overflows and such. If you don't want / don't need / can't use multitasking, then just run everything in one thread and that's it.

[DeanCording]

Have an ARM chip with 128K RAM, I almost certainly have enough for anything I’ll want to do

Problem is, I either statically allocate 20K or RAM in 2K chunks which seems very wasteful as most data blocks will be far less than that 2,048 worst case, I use malloc() and free() carefully, or I try and manage the memory myself by declaring a block and allocating and freeing from inside that manually.

Why is statically allocating memory a waste?  It's not like you can't save it up for another project!  The only wasted memory in an embedded single process system is the memory you never put to use.

If, at any point, you are going to need to malloc 20K, then it makes no difference whether it is statically allocated at startup or dynamically allocated during runtime. It is going to need to be allocated sometime and you might as well find out that you are short of space during development instead in production.  Besides, by the time you add in the extra code to do the malloc, keep track of the allocations, and clean up after yourself, you will probably end up using nearly as much in code space.

[IanB]

Problem is, I either statically allocate 20K or RAM in 2K chunks which seems very wasteful as most data blocks will be far less than that 2,048 worst case, I use malloc() and free() carefully, or I try and manage the memory myself by declaring a block and allocating and freeing from inside that manually.

Am I missing an obvious option?

Why is statically allocating memory a waste?

Precisely. What is the "waste" you are concerned about? You either have 20 K available on the system or you don't. If you "may" have 20 K available but you are not sure then you have an unreliable design and a bug waiting to happen. Your question betrays faulty logic in your thinking.

You should create a memory table, laying out what memory is to be used for what purpose, and then allocate the appropriate memory buffers statically at startup.

[ebastler]

Why is statically allocating memory a waste?  It's not like you can['t] save it up for another project!  The only wasted memory in an embedded single process system is the memory you never put to use.

   My thoughts exactly. Allocate the memory you need for your application, organize it in a suitable structure (a ring buffer of blocks may make sense), and be done with it.

[Berni]

To me 20K does not sound that bad if you have 128K of RAM

For C programing it works quite well to have a big typedef struct sitting statically allocated in memory. Its harder to garble it by doing something silly with memory access and in debugging you can easily place a watch on it. This means you can stop your program at any time in its execution and be able to see all the most recent packets.

Its nice to see programmers still being worried about using 20KB rather than just amusing RAM is infinite as most non MCU programmers do. But if this means a lot more complex code just to turn the 20KB into perhaps 10KB while you don't really need those extra 10KB to get your program to fit in then its mostly a waste of time. Heck in your example if you get a big burst of data and processing is slow dynamic allocation might use more than 20KB when the packets pile up. Heck perhaps in a rare oddball case it might use up all the available dynamic RAM and cause your program to crash in some very strange ways that are difficult to reproduce. This is also how a lot of security vulnerabilities appear in software where barfing an unexpected stream of data into it causes something to run out of memory or overflow, leading to a 'soft crash' in just the right way to trample over some memory and cause the software to do something it shouldn't later on.

[Brutte]

There are 10 types of data that can come in and while i can only handle one “7” type at a time, I could handle a “3” and a “7” concurrently. If a “7” comes in while I’m working on a “7” I ignore it. Further complicated that “6” “7” and “8” types can not run concurrently, so they “could” share memory.

Here is my proposition. It is statically allocated and occupies only the necessary amount.

Code: [Select]

typedef enum{
    notUsed = 0x000,
    type001 = 0x001,
    type002 = 0x002,
    type003 = 0x003,
    type031 = 0x031,
    type013 = 0x013,
    //... all possible scenarios
  }Scenario_t;

  //This layout is only for debugging and memory allocation
  struct{
  Scenario_t currentScenario;
    union{
      struct{int data1[99];}type001;
      struct{int data2[10];}type002;
      struct{int data3[17];}type003;
      struct{int data1[99]; int data3[17];}type031;
      struct{int data3[17]; int data1[99];}type013;
      //.....
    };
  }staticAllocation;
And whenever a new packet arrives, you can calculate what is already in the allocated buffer and push in a new data. Mind the staticAllocaiton layout is for debugging mostly as the runtime calculations can be based on masking currentScenario. Below I show a naive implelementation that you should not use as this would require tons of switch()-es.

Code: [Select]

  //...
  //if a type3 arrives when type1 is already at place:
  if(staticAllocation.currentScenario == type001){
    staticAllocation.currentScenario = type031;
    staticAllocation.type031.data3[14]=0x01234567;
  }

[andyturk]

Consider a non-malloc heap allocator. The advantage there is that you know that no other code will be using it and you're free to wipe it out and start fresh as your program runs. You'll have to statically allocate the space for the heap itself, but then you can be dynamic within its boundaries.

Here's one you might want to look at: https://github.com/rhempel/umm_malloc

[SiliconWizard]

Why is statically allocating memory a waste?  It's not like you can['t] save it up for another project!  The only wasted memory in an embedded single process system is the memory you never put to use.

   My thoughts exactly. Allocate the memory you need for your application, organize it in a suitable structure (a ring buffer of blocks may make sense), and be done with it.

That's usually the preferred way, especially for small systems.

Besides, dynamic memory allocation can be dangerous and usually has unpredictable execution time.
Some safety-critical related guidelines (such as MISRA-C) and standards (such as IEC 61508) either explicitely prohibit all forms of dynamic allocation, or at least strongly recommend against using it.

[nctnico]

I'm wondering how long the data needs to be stored. Can't the data be processed as soon as it arrives? That way you'd need to hold a maximum of 2 blocks of data (one which is being received and one which is being processed). If you can't process the data as fast as it comes in then there is always the chance data will be lost.

A circular buffer is one way of doing it. Another way is chopping the memory up in small chunks and use a linked list to create buffers which have a variable size. The advantage is that fragmentation isn't a problem but you'd have to iterate through each chunk of a buffer (you can't have a pointer to a buffer!). I have implemented this in a really space constrained device and it worked well.

[Mechatrommer]

I'm wondering how long the data needs to be stored. Can't the data be processed as soon as it arrives? That way you'd need to hold a maximum of 2 blocks of data (one which is being received and one which is being processed). If you can't process the data as fast as it comes in then there is always the chance data will be lost.

yes this is another good solution. double buffering and page flipping. when each packet/data block/type arrived, buffer is flipped, earlier buffer is processed ASAP. but this requires processing must be completed before the buffer is flipped again to receive 3rd packet. so you can just allocate 2 max size packet ie 2 x 2048 = 4KB memory. or you can just use circular buffer of size 4KB without the above requirement needed by page flipping technique. you only need get_next_byte() or something from processing layer and send it to appropriate data type processor, if you can process fast, you dont have to ignore anything, otherwise you can just use move_to_next_byte() or something to skip the data and move/rotate the start pointer of your circular buffer faster to give more room for incoming data. ymmv.

Why is statically allocating memory a waste?  It's not like you can't save it up for another project!  The only wasted memory in an embedded single process system is the memory you never put to use.

i believe whats he wants is so he can maximize memory allocation for other parameters, maybe he has another elastic (size keep changing) memory. so if his 20K buffer is only 50% utilized all the time, his another elastic memory cannot be freed and expanded 10KB bigger, but this will end up a messy housekeeping job imho, in the end, the get bigger memory size applied, if you want stable operation.

otoh with malloc, if me. i will allocate critical, fixed sized and static parameters first, once and untill to the end, and elastic (expandable) memories at the end of the row. so less housekeeping/shuffling memory job either by manually tracking them or by using malloc.h facility. ymmv.

[jnz]

There is some great data here but some questions about time.

The shortest answer is IDK.

Datatype “7” sized 1k comes in. I need somewhere to put it. I need to decrypt or other “process” it. I need to use it which ideally would just be passing a pointer to it to another function. When that function is done I can remove it.

This could be 1mS or 30S until I’m don’t with it.

In that time no other “7” type of data will be expected/allowed.

At any time I can expect an average use max of 5K data, so it seems bad to allow 20k of storage that basically can’t happen.


I don’t mind the cyclic buffer, but I want to store and use this data “in place” so at the wrap around that’s a bad idea. I’d have to store here and copy somewhere else - and in that case I have 10x 2K buffers just somewhere else sitting around. Using cyclic buffer without copying the data out means if I pass a pointer and the object is on the roll over I need all sorts of logic supporting that.

I don’t mind malloc-ing a region and try and divide that up.

I still need to check the links posted. Just wanted to update the time requirements and explain that where-ever I store these, I also need to work with them from until they are of no use anymore.

[ebastler]

The shortest answer is IDK.

Datatype “7” sized 1k comes in. I need somewhere to put it. I need to decrypt or other “process” it. I need to use it which ideally would just be passing a pointer to it to another function. When that function is done I can remove it.

Enlighten me, please -- so what does IDK stand for?  "Incoming, Decrypt, Kremove"? 

[IanB]

Enlighten me, please -- so what does IDK stand for?  "Incoming, Decrypt, Kremove"? 

"I Don't Know"

[IanB]

At any time I can expect an average use max of 5K data, so it seems bad to allow 20k of storage that basically can’t happen.

If your system has 128 K of memory and your application when it's running leaves 50 K unused, then you are wasting that 50 K of memory.

On an embedded system there is no concept of "waste" in the way you are thinking. You own the whole system; you are not sharing it and you are not competing with anyone or anything else for resources (?).

Therefore, the only problem with allocating a 20 K buffer at startup and keeping it available is if it prevents you successfully executing other parts of your application. If you have enough memory to allocate that buffer permanently, then allocate it permanently. Your application will execute faster, have fewer bugs, be more reliable.

[ebastler]

"I Don't Know"

Ah, thanks -- that's one I had not come across yet. 

[jnz]

At any time I can expect an average use max of 5K data, so it seems bad to allow 20k of storage that basically can’t happen.

If your system has 128 K of memory and your application when it's running leaves 50 K unused, then you are wasting that 50 K of memory.

On an embedded system there is no concept of "waste" in the way you are thinking. You own the whole system; you are not sharing it and you are not competing with anyone or anything else for resources (?).

Therefore, the only problem with allocating a 20 K buffer at startup and keeping it available is if it prevents you successfully executing other parts of your application. If you have enough memory to allocate that buffer permanently, then allocate it permanently. Your application will execute faster, have fewer bugs, be more reliable.

IT'S NOT FINISHED. I can't tell you how much of the RAM is left, what I know right now is that I don't want to be wasteful just because I didn't think ahead of how this would work. I don't want to devote 20k to 10 buffers of 2k when realistically most objects cases with be 32 bytes or so.

I have whole swaths of future features that will need surely RAM. Just pretend that I can't budget every byte. This isn't a toy with a fixed life and no update schedule.

[nctnico]

But how about optimising when really needed instead of banging your head against the wall to solve a problem which may never arrive?
Still given your problem I think a circular receive buffer is the easiest way to solve it. Read a packet from the receive buffer and then process it in a seperate buffer. Sure you'll need an extra buffer but that is only 2k extra. However you could put that 2k buffer onto the stack (declare it inside a function and do processing from there) so it gets freed when it is no longer needed without needing to worry about memory fragmentation. I often declare temporary buffers on the stack to share memory.

[Howardlong]

IT'S NOT FINISHED. I can't tell you how much of the RAM is left, what I know right now is that I don't want to be wasteful just because I didn't think ahead of how this would work. I don't want to devote 20k to 10 buffers of 2k when realistically most objects cases with be 32 bytes or so.

I have whole swaths of future features that will need surely RAM. Just pretend that I can't budget every byte. This isn't a toy with a fixed life and no update schedule.

It sounds very much like you’re coming up with a solution before you know what the requirements are.

Edit:

I’ll add to that, you need to scribble down all of your requirements, and prioritise them.

Accept that compromises will be made: compromises are a fundamental part of engineering, driven by priorities.

I’ll bet that getting a product out of the door is far more important than possible future updates.

[NorthGuy]

This may sound paradoxical, but ... You achieve better resource utilization when you use substantially all of the available resources because you have already paid for all your memory. To contrary, if you have 128K of memory and only use 8K - that's a waste of memory.

Therefore, if using more memory helps you create better code (as with static allocation case), there's absolutely no doubts that this is the way to go.

[MosherIV]

I don't want to devote 20k to 10 buffers of 2k when realistically most objects cases with be 32 bytes or so.

Nctnico pretty much said this suggestion in a different way.

Layer your functions.
Layer 0 with fixed 2K buffer receives data, when full msg received, copy and post it to next layer.
Layer 1 decides what packet is and what need to be done, 2k fixed buffer. Copies data to buffers in next layer.
Layer 2, 1 fixed size buffer per object. Holds data until done, buffers can then be reused.

Ok it still uses 6K but better than 10K and no dynamic allocation.
You could collaspe layer1 and 2 if you can process fast enough.