5
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ This can be very implementation-specific. Yes, in general you can expect that the first realloc has to find a contiguous block "somewhere" and that will likely be past the second block. The space occupied by original first block will technically become free but what happens to it depends on implementation a lot. Maybe it is reused on its own (if it happens to be large enough) later, maybe it is merged with the second block when the latter gets freed and they together are reused. \$\endgroup\$ – sharptooth May 19 '15 at 14:54
  • 2
    \$\begingroup\$ Why do you need all of your info_t structs to be located together in a contiguous block of memory? You have next & prev pointers so there's nothing preventing you from allocating individual blocks for individual info_t structs and using those next & prev pointers to maintain your linked-list. \$\endgroup\$ – brhans May 19 '15 at 16:47
  • 1
    \$\begingroup\$ Given that the number of each is always the same, is there a reason they are two separate structures? With a cacheless MCU, locality of reference is generally less important (it may help simplify addressing). This would eliminate fragmentation from these structures and a custom memory allocator could limit fragmentation from other allocations (e.g., placing other objects at the top of the heap/region). \$\endgroup\$ – Paul A. Clayton May 19 '15 at 20:49
25
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ I get the point Thanks. I needed dynamic memory allocation for some benchmarking of the program. Not that I am making some commercial application. I found a good workaround for this and I will mention what I did in an answer. \$\endgroup\$ – Hassan May 21 '15 at 11:59
  • \$\begingroup\$ The worst case memory use does not necessarily mean that a static allocation will only use that much memory. Furthermore, in some designs functionality can be dropped under high memory use, allowing some live variables to be killed and their memory freed (the same applies to other resources like processing time); with variable memory demand by features, dynamic allocation may allow the device to retain a nice but unnecessary feature under a larger range of conditions. Even repurposing a chunk of memory (e.g., from I/O buffer to collection of structures) is a limited from of dynamic memory. \$\endgroup\$ – Paul A. Clayton May 21 '15 at 12:22
  • 3
    \$\begingroup\$ @Hassan Using dynamic allocation for benchmarking makes even less sense, since introducing dynamic allocation will likely affect performance drastically. Benchmarking of embedded systems is done with an oscilloscope and a general-purpose I/O pin. You will get extremely accurate benchmarking figures that way. \$\endgroup\$ – Lundin May 21 '15 at 12:49
  • 3
    \$\begingroup\$ @PaulA.Clayton "functionality can be dropped under high memory use, allowing some live variables to be killed and their memory freed" For what purpose? What are you going to use that memory for? Either your program allocates enough memory to handle the worst case, or it does not. When not executing the worst case, there is nothing meaningful you could do with the so-called "saved" memory. Are you planning to have the program use that memory to do something completely unrelated to its designated task, when not executing the worst case scenario, or what? \$\endgroup\$ – Lundin May 21 '15 at 12:59
  • 1
    \$\begingroup\$ As a completely made-up example, suppose one had an event log that could hold five events without optimistic memory use, but with optimistic memory use 90% of the time could hold 15 events, 9% of the time could hold 9 events, and 1% of the time could hold only four events. Expanding log capacity in the typical case might be worth the development effort and sacrificing one event entry 1% of the time. (Not a great example because event log depth would probably be most important under high stress, but prohibition of dynamic memory removes the choice altogether.) \$\endgroup\$ – Paul A. Clayton May 22 '15 at 0:45
10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Making use of usage patters is one solution. Another is using a fixed size array and not accepting more "task" objects that can possibly fit there. No reallocation - no worries. \$\endgroup\$ – sharptooth May 19 '15 at 15:03
  • \$\begingroup\$ Hi Thanks, I get this. My tasks can get free in any random fashion so I cant have this method. I was just curious that is it possible that I can address the available memory space and allocate m_info from the beginning and m_index from somewhere near the end? m_info and m_index will always be same in number of elements \$\endgroup\$ – Hassan May 19 '15 at 15:08
  • \$\begingroup\$ @sharptooth. I agree but I cannot use this. I need dynamic memory allocation for some bench markings also. \$\endgroup\$ – Hassan May 19 '15 at 15:13
  • 2
    \$\begingroup\$ @brhans - Isn't an array just another way of describing main memory ... ? :) \$\endgroup\$ – OrangeDog May 19 '15 at 16:22
  • 3
    \$\begingroup\$ It doesn't make any sense to use dynamic memory allocation, so why recommend it? I don't mean to be rude, but if you find yourself using dynamic memory for a 16 bit MCU with 4kb of RAM, you are not using common sense and are not quite sure about what you are doing, simple as that. \$\endgroup\$ – Lundin May 21 '15 at 7:54
0
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.