Realloc wasting lots of space in my MCU?

Question

I am writing a simple task scheduler and using dynamic memory allocation on my cc430F5137. I agree that it is not a good practice but for the time being lets assume it is my application requirement to use dynamic memory allocation.

In my OS.c file

I have two structures,

typedef struct
{
    task_t task;
    uint8_t next;
    uint8_t prev;
    uint8_t priority;

} info_t;


typedef struct
{
    task_t task;
    uint8_t index;
} index_t;

size of info_t is 8 bytes and size of index_t is 6 bytes.

Also I do

index_t* m_index;
info_t* m_info;

Then I have initialize function in which I do

m_info = NULL;
m_index = NULL;

Now I have a function registerTask(& task) which takes address of the function to schedule. In this function I do

m_info = realloc(m_info,(num_registered_tasks + 1) * sizeof(*m_info));

and then set the values of .priority, next,task and prev.

Then I do

m_index = realloc(m_index,(num_registered_tasks + 1) * sizeof(*m_index));

and set the values of task and index. and do num_registered_tasks++;

My Question is that how is realloc() behaving in this regard.

Suppose my memory space, First Task is registered, so It will have first 8 bytes for m_info[0] and next 6 bytes for m_index[0]. Now when my second task calls this function, what will happen? What I am guessing is that for m_info it will first look for 16 bytes of continuous data and will only find it after the first 14 bytes, it will change the address of m_info[0] and copy the contents and then add m_info[1]. And when m_index is called, it will only find 12 bytes after this (14 + 16) bytes and place m_index[0] and m_index[1] here.

If this is true then all my previous space is being wasted?

If I am wrong then how will this function work?

How can I utilize the previous space also?

I need index_t struct for implementing some sort of search algorithm so it is necessary also

Answer 1

Using dynamic memory allocation on a 16 bit MCU with 4kb RAM is very poor engineering.

Not so much because of the usual problems with memory leaks. Not so much because of heap memory fragmentation. Not even because of the rather steep execution time overhead needed for the allocation routines. But because it is completely pointless and makes no sense.

You have some real world requirements stating what your program should do, and based on these your program will need to use exactly x bytes of RAM to handle the worst-case scenario. You will not need less, you will not need more, you will need that exact amount of RAM, which can be determined at compile time.

It doesn't make sense to save part of the 4kb, leaving them unused. Who is going to use them? Similarly, it doesn't make sense to allocate more memory than needed for the worst-case scenario. Simply statically allocate as much memory as is needed, period.

In addition you have a worst-case scenario with maximum stack usage, where you are deep into a call stack and all interrupts that are enabled have fired. This worst case scenario can be calculated at compile-time or measured in runtime. Good practice is to allocate more RAM than what is needed for the worst-case, to prevent stack overflows (the stack is actually a dynamic memory area as well). Or rather: use every single byte of RAM not used by your program for the stack.

If your application needs exactly 3kb of RAM, then you should use the remaining 1kb for the stack.

Dynamic allocation/the computer heap is intended to be used on hosted applications such as Windows or Linux, where every process has a fixed amount of RAM, and in addition can use heap memory to use as much RAM as there is in the hardware. It only makes sense to use dynamic allocation in such complex, multi-process systems, with vast amounts of RAM available.

In a MCU program, either bare metal or RTOS-based, you have to realize that heap implementations work like this: reserve a fixed amount, x kb of RAM for the heap. Whenever using dynamic allocation, you get handed a chunk of this fixed amount of memory. So why not simply take those x kb you would use for allocating the heap and instead use them to store your variables instead?

---

I've expanded on this with a more detailed explanation and more possible problems, here:
Why should I not use dynamic memory allocation in embedded systems?

Answer 2

This is called memory fragmentation.

There are all kinds of fancy algorithms to deal with it, but the bookkeeping overhead makes them unsuitable for a small MCU.

Instead, you can write you own memory allocation routines based on your expected usage pattern. You might have a separate routine for each thread of execution, for example. If you can guarantee that free() happens in opposite order of alloc() then you can use a simple pointer to the end of memory.

Or you could use a level of indirection: Access the memory only through a pointer to a pointer. Then you can freely garbage-collect the memory and adjust the pointer table to point to memory wherever it ends up.

The best answer for embedded systems is usually to avoid dynamic memory allocation altogether.

Answer 3

After lots and lots of comments and answers of not using dynamic memory, I still found a way which at the time being solved my problem.

I changed this in my code

typedef struct
{
    task_t task;
    uint8_t next;
    uint8_t prev;
    uint8_t priority;

} info_t;


typedef struct
{
    task_t task;
    uint8_t index;
} index_t;

typedef struct
{
    info_t m_info;
    info_t m_index;
} combined_t;

combined_t* m_combined;

By this, nw my realloc() allocates contiguous memory to m_combined and my fragmentation issue is resolved. (Well I guess because after analyzing the memory step by step).