How to Use Dynamic Memory in IEC61508 Systems

by Michael Hillmann (comments: 0)

The IEC61508 states, that static memory management is highly recommended. We all are following this recommendation - unless there is a good reason to be more dynamic, right?

The time will come when we need features like:

  • Run time configuration
  • Remove all compile time configurations
  • Flexibility to external behavior or hardware
  • Platform for a complete generation of products

...then it is time to discuss dynamic solutions, because it’s not efficient (or even possible) to eliminate dynamic memory management completely out of the system while designing such features.

We must avoid and detect programming errors

Let’s go back to the IEC61508. The reason for the recommendation is the potential risk of multiple well known and hard to detect programming errors in relation to dynamic memory management:

  1. Memory Fragmentation
  2. No Memory Available
  3. Missing Memory Free
  4. Free Memory to Wrong Pool
  5. Free Memory multiple Times
  6. Using Memory after Free
  7. Free Memory while Using

Some solutions allow only the allocation of memory (I call them ’pseudo-dynamic’). These type of solutions are addressing the problems 1.) and 2.) in the list. Good descriptions can be found in other posts1.

For a more generic approach, we need mechanisms to avoid or detect all of the listed situations systematically.

1. Memory Fragmentation

The memory fragmentation is an effect, which may result when we perform multiple allocation and free cycles with different memory sizes.

In real time systems, we need determinism and constant execution times. With improved allocation algorithms like first fit algorithm2, the execution timing depends heavily on previous memory activities. This is bad for many of our system designs.

The established way to avoid memory fragmentation is working with one (or more) fixed size memory block pools.

Good news: professional real time kernels provide a memory management with fixed size memory blocks3. Even some real time kernel for non-safety usage provide this kind of service4. I think we should use the provided service of our preferred real time kernel.

For this article we consider the principal function interface of the real time kernel. For reference, a simple usage cycle is:

ptr = MemAlloc(pool);
/* use memory via ptr */
MemFree(pool, ptr);

and somewhere during start up:

pool = Create(mem, size, num);

2. No Memory Available

All memory allocation functions are giving us feedback (e.g. a NULL pointer), if not enough memory is available for the current allocation request. I think it is straight forward to check this and take an appropriate action.

ptr = MemAlloc(pool);
if (ptr == NULL) {
    MemErrOutOfMemory(pool);
}
/* use memory via ptr */
MemFree(pool, ptr);

When using a real time kernel we can furthermore avoid the risk of a missing check and failure handling: we extend our memory allocation function with a blocking wait for free memory:

ptr = MemAllocWait(pool);
/* use memory via ptr */
MemFree(pool, ptr);

Now we guarantee, that the returned pointer is always a valid allocated memory block. The mandatory safety task monitor will detect, if a task will not get enough memory within the defined deadline.

3. Free Memory to Wrong Pool

If we are responsible to free the memory to the correct pool (e.g. the pool is an argument to free the memory), we could do this wrong.

This is not a big issue, because we can completely avoid this error by adding the required argument to an info area. For simple (and fast) access of this data, the info area is a part of the allocated memory.

This part is not usable for the application and located in front of the application memory block reference:

Memory Block Layout

The usage sequence with this improvement is now:

ptr = MemAllocWait(pool);
/* use memory via ptr */
MemFree(ptr);

4. Missing Memory Free

A so-called 'memory leak' occurs when we allocate memory and after usage we miss to free the memory block. This error is not easy to detect, especially when allocation and free actions will take place in different functions (or tasks).

One method I found for detecting a memory leak, without knowing the application details, is a memory watchdog. This watchdog is working analogous to a typically used execution watchdog.

Let us assume, we define a watchdog time during the memory allocation. This forces us to trigger the watchdog within this period of time to keep the memory block valid.

We store the memory timing data in the already introduced info area.

For checking the watchdog time period of all allocated memory blocks we introduce a checking function. The pseudo code should give you an idea how we check the blocks.

void MemCheck(pool)
{
    for each 'block' in 'pool' do:
        if ( 'block::timeout' is greater than 0 ) then:
            decrement 'block::timeout' by 1
            if ( 'block::timeout' is equal to 0 ) then:
                call MemErrTimeout (block)
}

We call this function periodically as part of the system safety self tests. Our using sequence looks like the following lines.

ptr = MemAllocWait(timeout, pool);
MemUseTrigger(ptr);
/* use memory via ptr */
MemFree(ptr);

Note: between the lines, we allow a maximum time period of the given timeout. This may occur, when an interrupt leads to a task switch between these lines.

In case we miss the watchdog time period with our use-trigger, we can define an appropriate action on this detection in a callback function:

void MemErrTimeout(ptr)
{
    /* action on timeout:  */
    /* log diagnostic data */
    /* initiate safe state */
}

5. Free Memory multiple Times

When we free a memory block multiple times (by mistake) without a detection mechanism, we are running in strange behavior of the system. This kind of error is very hard to debug - and must be avoided.

With an additional redundancy value within the info area, we can handle this very efficiently. I prefer the complement value of the pool argument. We must set both values to a matching pair within the memory allocation function.

The memory free function can check this redundant information, put back the memory block into the addressed pool and has to corrupt the redundant information. A pseudo code could look like:

void MemFree(ptr)
{
    if ( 'ptr::pool' is equal to complement of 'ptr::inv_pool' ) then:
        release memory block 'ptr' to ’ptr::pool'
        set 'ptr::inv_pool' to 'ptr::pool'
    else:
        call MemErrDoubleFree (ptr)
}

At the end, we can define an appropriate action for this erroneous case in a callback function: MemErrDoubleFree(ptr).

6. Using Memory after Free

This programming error sounds crazy, but in multi tasking environments this error may exist, in worst case undetected for a long time.

For detecting this situation, we can reuse our data redundancy in the info area. In this case we check, that the redundancy is not corrupted before using the memory block. To get the usage sequence as simple as possible, we can integrate the memory watchdog triggering:

void MemStartAccess(ptr)
{
    if ( 'ptr::pool' is not equal to complement of 'ptr::inv_pool' ) then:
        call MemErrUsedFree (ptr)
    else
        set 'ptr::timeout' to 'ptr::watchdog_time'
}

At the end, we can define an appropriate action for this erroneous case in a callback function: MemErrUsedFree(ptr).

The usage sequence for that detection mechanism will need an additional function call before using the memory block.

ptr = MemAllocWait(timeout, pool);
MemStartAccess(ptr);
/* use memory block via ptr */
MemFree(ptr);

7. Free Memory while Using

This programming error is in the same class of errors like the previous one. In multi tasking environment it is possible to free a memory block, which was used by the interrupted task. Coming back to the using task, we use memory that is already released.

When thinking about this problem, I found a solution with symmetric functions. We already have a MemStartAccess() function - so why not introduce a function at the end, too? (I like to have symmetric functions for this kind of use cases...)

This new function can inform us, that the memory block is not used anymore:

void MemEndAccess(ptr);

With a corresponding blocking function for releasing the memory, we can avoid this programming error.

void MemFreeWait(ptr);

This leads us to the final dynamic memory usage sequence in this article:

ptr = MemAllocWait(timeout, pool);
MemStartAccess(ptr);
/* use memory block via ptr */
MemEndAccess(ptr);
MemFreeWait(ptr);

Conclusion

In this article we discovered a dynamic memory management approach for use in IEC61508 systems.

We systematically avoid the programming errors:

  • memory fragmentation
  • free memory to wrong pool
  • no memory is available
  • free memory while using

and we are able to detect and perform individual reactions on the situations:

  • missing free memory
  • free memory multiple times
  • usage of memory after free

The price we pay for these safety features is:

  • additional memory space (e.g. 16 byte) within each allocated memory block
  • deterministic amount of CPU run time

Nevertheless, for safety critical systems I still recommend to use dynamic memory with care. With the provided measures, I think it is acceptable.

Do you know other solutions with less overhead? I'm pleased to see a comment from you.

Go back

Add a comment

Update Notification

For an automatic notification on new blog articles, just register your EMail address.

Subscription

We are the Blogger:

Andrea Dorn

After my study of industrial engineering I worked at an engineering service provider. As team leader and sales representative, I was responsible for customers from aviation and mechanical engineering. I am part of the Embedded Office team since 2010. Here I am responsible for the Sales and Marketing activities. I love being outside for hiking, riding or walking no matter the weather.

Fridolin Kolb

I have more than 20 years experience in developing safety critical software as developer and project manager in medical, aerospace and automotive industries. I am always keen on finding a solution for any problem. The statement “This won’t never work”, will never work for me. In my spare time You can find me playing the traverse flute in our local music association, spending time with my family, or in a session as member of our local council and member of the local church council. So obviously I am lacking the ability to say “No” to any challenge ;-).

Michael Hillmann

I have been working for 20 years in safety critical software development. Discussing and solving challenges with customers and colleagues excites me again and again. In my spare time I can be found while hiking, spending time with my family, having a sauna with friends - or simply reading a good book.

Wolfgang Engelhard

I’m a functional safety engineer with over 10 years of experience in software development. I’m most concerned with creating accurate documentation for safety critical software, but lately found joy in destruction of software (meaning I’m testing). Spare time activities range from biking to mentoring a local robotics group of young kids.

Matthias Riegel

Since finishing my master in computer science (focus on Embedded Systems and IT-Security), I’ve been working at Embedded Office. Before that, I worked with databases, and learned many unusual languages (like lisp, clojure, smalltalk, io, prolog, …). In my spare time I’m often on my bike, at the lathe or watching my bees.