Dynamic Memory in IEC61508 Systems

The time will come when we need features like:

• Run time configuration

• Removing compile time configurations of components

• 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 allocation of memory. These type of solutions are addressing the problems 3.) to 7.) in the list by avoiding the reuse of memory for multiple purpose. This is a working solution and often used for flexible memory usage in product variants during startup, while keeping the resulting memory layout static during operation.

When even this approach is not enougth, we need a more generic approach with an approach 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 algorithm, the execution timing depends heavily on previous memory activities. This is bad for of our system designs.

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

Good news: professional real time kernels provide you memory management with fixed size memory blocks. I think we should use these 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);
ptr = MemAllocWait(pool);

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:

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 within each allocated memory block

• deterministic amount of CPU run time

Nevertheless, I recommend using dynamic memory with caution for safety-critical systems. With the measures provided, however, the use is acceptable in my opinion.