Dynamic memory allocation in small microcontrollers.

[misterT]

Hey, does anybody know a good example when using malloc (dynamic memory) is a good idea? I mean, I know many reasons why using malloc is a bad idea.. just want to find an example when it is safe and "elegant" to use malloc. (when programming small microcontrollers, of course).

 

[NorthGuy]

Heap helps when you have to allocate pieces of memory of various and often unpredictable size, such as when you create objects in C++. However, with small memory it will cause fragmentation very soon. Also MCU doesn't have a good way to recover from "not enough memoory" condition. So, it's pretty much useless, and it's easier to live with fixed memory.

If you have to, you shouldn't use malloc() but rather create your own memory allocator, which would work as in old ages - handles instead of pointers, periodic garbage collection. Since there's no language support for handles, they would be a hassle for an average MCU programmer.

 

[misterT]

Yes.. that is something I knew already. And I do not believe in "dumbing it down for the average people". When you say that something is "a hassle" or difficult for an average mcu programmer, you are practically saying "you are too stupid to get any better". It is better to say things as they are and leave it to the reader to consider if the topic is too advanced or not.

So anyway, do you think there is no situation where dynamic memory allocation is "safe and elegant" solution? That is my challenge.. to find an example where using dynamic memory allocation is a very good solution.

 

[misterT]

Wow...

Your comments would be ok if this was a chat, but this is not a chat. This is a forum. When I post I usually read my text through couple of times before posting to be sure that it delivers some kind of input to the thread. And sometimes.. many times.. I read my own posts after posting and edit them if I notice an error etc.

I started this thread just for the sake of discussion. A little bit of friendly debate keeps our minds entertained.

 

[NorthGuy]

Yes.. that is something I knew already. And I do not believe in "dumbing it down for the average people". When you say that something is "a hassle" or difficult for an average mcu programmer, you are practically saying "you are too stupid to get any better". It is better to say things as they are and leave it to the reader to consider if the topic is too advanced or not.

I'm not saying that anyone is stupid.

What I'm saying is this: Let's suppose you've got a library that does dynamic memory allocation, garbage collection etc., so that you can have a non-fragmentable heap in 2K (or may be even 1K) memory space. Then you give it to a typical MCU programmer, but he tells you: "no, that's too much hassle, I'd be better off with fixed memory".

Of course there could be some people who might find it useful, but I suspect these will be rare and far between.

So anyway, do you think there is no situation where dynamic memory allocation is "safe and elegant" solution? That is my challenge.. to find an example where using dynamic memory allocation is a very good solution.

You can think of something. For example, if you have a network (such as CAN) and you don't know how many nodes and of what kind you might encounter. You need to dynamically allocate memory to hold information for each new node you discover and then free this memory when the node disconnects.

There are two dangers here - defragmentation and running out of memory. You can combat defragmentation by allocating the same size (which is a max for node kinds), but this will require more memory. Or you can combat defragmentation by using handles. Or you can keep the memory allocated in case the node comes back.

Or you just get a bigger processor, which is what most people would do (wanted to say "waht average programmer would do", but I'm getting better at this )

Are you writing a book or something?

 

[nsaspook]

So anyway, do you think there is no situation where dynamic memory allocation is "safe and elegant" solution? That is my challenge.. to find an example where using dynamic memory allocation is a very good solution.

C type "dynamic memory allocation" is not free, it requires valuable system resources to make it efficient even on a platform with proper VM and paging. To me "safe and elegant" programming means working correctly within the given hardware resources , not designing software to some theoretical abstract ideal on hardware with no support for memory isolation or protection. There are problems like dynamic resource management in a uC RTOS environment (that uses valuable memory) where a system level user malloc type function is implemented to assign memory resources to processes but most fake it with fixed block allocation anyway on small processors.

There is usually a trade-off in methods (time/cpu resources vs memory). For example a Fibonacci series can be programmed with or without recursion. On a small micro with limited memory the loop method might be a safer method.
https://www.programmingsimplified.com/c-program-generate-fibonacci-series

 

[misterT]

C type "dynamic memory allocation" is not free, it requires valuable system resources to make it efficient even on a platform with proper VM and paging.

Dynamic memory allocation is very efficient. A simple linked list will do fine on small uC. The problems are fragmentation and indeterministic memory use... not efficiency.

For example a Fibonacci series can be programmed with or without recursion. On a small micro with limited memory the loop method might be a safer method.
https://www.programmingsimplified.com/c-program-generate-fibonacci-series

Who has ever needed a good way to calculate fibonacci series? And what does that to do with dynamic memory allocation..

... Or you can combat defragmentation by using handles.

Could you explain that a little bit more.. what do you mean by "handles". How are those related to memory management?

Are you writing a book or something?

Haha.. no. The forum has been so boring lately so I wanted to have something to talk about..

 

[misterT]

In my current usart library I use a ring buffer and the interface to initialize whole thing is:
void init_usart(uint8_t *buffer, uint8_t length);

Of course I am already sacrificing some efficiency for abstraction and flexibility.. so why shouldn't I take it a step further and just say:
void init_usart(uint8_t bufferSize);
.. and let the module figure out what to do. Something like that only allocates a piece of memory that would be needed anyway.. Only drawback is that the compiler can't tell you how much memory you are actually using. But at the end the memory usage is the same.. no matter what the method is.

 

[nsaspook]

Dynamic memory allocation is very efficient. A simple linked list will do fine on small uC. The problems are fragmentation and indeterministic memory use... not efficiency.

To handle fragmentation and indeterministic memory use you need to program around it nor ignore it. If the problem is so simple that those factors don't matter then static allocation is the logical choice, Why would you use dynamic memory allocation in a single threaded program when simple recursion that uses stack to allocate space for variables works on almost every problem? Memory leaks from nested functions that have error return paths that miss or unlink the wrong memory are the cause of many a grey hair on systems without hardware assisted memory management.

If you have to design software that might cause harm to humans then the Misra C rules might be a good read.

**broken link removed**

20.4 (req): Dynamic heap memory allocation shall not be used.

**broken link removed**

 

[misterT]

If you have to design software that might cause harm to humans then the Misra C rules might be good read.

**broken link removed**

Yes.. I need to program according to misra in my job (it is not required.. misra is not "the rule", but it does make life easier when you can refer to it.).

I'm just trying to find out if there is any good reason in any case to use dynamic memory allocation..

Also.. when does using memory come "dynamic" or "static"... Calling malloc once to get a piece of available memory? Is that dynamic? According to "misra" I can write to any memory location, but I can't call malloc.. which is actually just a datastructure with a well defined amount of memory allocated to it. Nothing dynamic there.

 

[misterT]

20.4 (req): Dynamic heap memory allocation shall not be used.

So, stack is against the misra rules? I can't see why dynamic memory is banned, but you can have multiple stacks possibly collide with each other.

 

[NorthGuy]

Could you explain that a little bit more.. what do you mean by "handles". How are those related to memory management?

When your memory is fragmented, there are little pieces of free memory, but you cannot use them, because you need a contiguous piece. So, you need to do a process called "garbage collection" - you move all the allocated pieces together and all the free space together. Now, your memory is not fragmented any more and you can allocate more.

The problem is that old pointers are no good any more because the memory has moved. Therefore, during the garbage collection, pointers have to be updated too. To do so, you need to know where the pointers are. This can be achieved by keeping all the pointers in a single table.

You need to somehow access the pointers in the table. This is done with handles, which are pointers to the pointers stored in the table. To access your allocated memory, instead of *p (where p is a pointer) you use **h (where h is a handle). The difference is that h is still valid even though the allocated memory might have been moved. You can get a pointer from it (p = *h), but this defeats the purpose. This is how it's been done long time ago before hardware memory mapping came along.

 

[misterT]

To access your allocated memory, instead of *p (where p is a pointer) you use **h (where h is a handle).

I would have called it "pointer to pointer".. haha. Is 'handle' something that comes from windows-world, or is there more history to that naming convention? Nice post anyway.. thanks.

 

[nsaspook]

I'm just trying to find out if there is any good reason in any case to use dynamic memory allocation..
...
but I can't call malloc..

Sure there are lots of reasons to use it for general programming if you have a full OS system like the Linux kernel or a good RTOS but is it necessary the best answer where there is not a dynamic pool of possible resources that can be allocated to processes that have (real or OS supplied) separate threads of execution?
...
Those are the rules partner but there are ways around anything.

 

[NorthGuy]

I would have called it "pointer to pointer".. haha. Is 'handle' something that comes from windows-world, or is there more history to that naming convention? Nice post anyway.. thanks.

I remember handles on MacOS somewhere around 20 years ago. I think it was before Windows.

 

[misterT]

I am doing a memory test like this:
- Allocate some memory
- Test allocated memory
- Copy contents of the memory section under test
- Test that memory
- Copy contents back
- Repeat until all memory is tested
- Release allocated memory

So.. is that against misra? GCC compiler does save information about how much memory is used.. so I could start using memory from &(__data_load_end[0]); and skip using malloc. But what is the difference..

 

[nsaspook]

I guess the question is can you at build time trace every memory access location and value from the logic of your provably correct program (no undefined behavior in runtime ) without knowing the guts of the C runtime (Implementation-defined) memory allocation library? How long does a call to malloc take for a random sized hunk of memory instead of using automatic and static variables and what are the results from every request?

 

[NorthGuy]

If you don't free the memory that has been allocated, I would call this static.

 

[large_ghostman]

I have just read that MISRA link!!!! Good job they were not around when moses was! can you imagine his face when he saw the Tablet of stone!!!

 

[large_ghostman]

Any idea why this is considered a no no 20.10 (req): The library functions 'atof', 'atoi' and 'atol' from library <stdlib.h> shall not be used.


It almost cries out for : OR THOU SHALL BE CAST FROM THE GARDEN AND BE ETERNAL IN HELL!