Playing with FreeRTOS, part I

The spooky month is upon us, ideal time to start messing with something that is horroresque. What is more scary than a stack overflow on a real time operating system? perhaps StackOverflow,. sometimes,..

The idea of a real time system is to provide maximum response times (deadlines) to tasks. The speed itself is not critical, determinism is. When there is a crash of the operating system running our predictability reliant tasks, it can get deadly. Imagine if the computer in a self driven car, or heck, an airplane, crashed. Then no tasks, even safety critical ones, can get done within their deadlines. Hence why it is a good idea to look into one of the more common reasons a system might crash, which is stack exhaustion.

Let's give ourselves an exercise then. We'll try finding the stack size for a system running two tasks. First we'll use an experimental approach and then analytical. (Both of the tasks do not depend on external factors, which means the experimental approach will be accurate, but such isolation is almost unheard of when it comes to embedded. The analytical approach is better, if it can be done.)

The following file contains our tasks, this file will be the same for both approaches of measurement:

#include <stdlib.h>
#include <stdio.h>

#include "FreeRTOS.h"
#include "task.h"
#include "stack.h"

short prvFoo(long lA)
{
    short sI;
    unsigned char ucArr[20];
    for (sI = 0; sI < 20; sI++)
        ucArr[sI] = 42;
    return 42;
}

unsigned char prvBar(short sB)
{
    short *psP;
    short sA;
    sA = sB;
    psP = &sA;
    return *psP;
}

void vStackTask1(void *pvParameters)
{
    unsigned short usI;
    srand('a');
    while (1)
    {
        for (usI = 0; usI < 10; usI++)
        {
            if (rand() % 2)
            //if (usI % 2)
                prvFoo(1);
            else
                prvBar(2);
        }
    }
    vTaskDelete(NULL);
}

unsigned short prvBinomial(unsigned short usN,
                           unsigned short usK)
{
    if (usK == 0 || usK == usN)
        return 1;
    return prvBinomial(usN - 1, usK - 1) +
           prvBinomial(usN - 1, usK);
}

void vStackTask2(void *pvParameters)
{
    while (1)
    {
        prvBinomial(10, 3);
    }
    vTaskDelete(NULL);
}

You can read what the tasks do, but importantly they do not rely on external factors. Next follows a testing file. Since we are first testing via the experimental approach, we will use uxTaskGetStackHighWaterMark. We will first fill the memory allocated for stack with a predefined value. Then try to go through as many different cases of behavior as possible. When we then look at the stack, we will see where the values were overwritten, how much has the stack risen. We add a bit to this value and we got the size of the stack. The benefit of this approach is that it is very simple, it can be used in a project of any size and it is relatively accurate if we test correctly. The main disadvantage is we're probably not able to test the worst case if the project size is massive.

#include <stdio.h>

#include "FreeRTOS.h"
#include "task.h"
#include "stack.h"

TaskHandle_t xHandle1 = NULL;
TaskHandle_t xHandle2 = NULL;

volatile UBaseType_t uxHighWaterMark1 = 0;
volatile UBaseType_t uxHighWaterMark2 = 0;

volatile int isOverflow = 0;

void vApplicationStackOverflowHook(TaskHandle_t xTask,
                                   char *pcTaskName) {
    isOverflow = 1;
    taskDISABLE_INTERRUPTS();
    for (;;) {
    }
}

void monitorTask(void *params) {
    for (;;) {
        vTaskDelay(1000);
        uxHighWaterMark1 =
            uxTaskGetStackHighWaterMark(xHandle1);
        uxHighWaterMark2 =
            uxTaskGetStackHighWaterMark(xHandle2);
    }
}

int main(void)
{
    xTaskCreate(vStackTask1, (const char*)"ST 1", 400,
                NULL, tskIDLE_PRIORITY + 1, &xHandle1);
    xTaskCreate(vStackTask2, (const char*)"ST 2", 400,
                NULL, tskIDLE_PRIORITY + 1, &xHandle2);
    xTaskCreate(monitorTask, (const char*)"MON", 300,
                NULL, tskIDLE_PRIORITY + 2, NULL);

    vTaskStartScheduler();

    return 0;
}

Now, since we are using FreeRTOS, the stack memory fill can be done for us if we set #define INCLUDE_uxTaskGetStackHighWaterMark 1 in FreeRTOSConfig.h, so that we do not have to worry about these mechanisms ourselves. When we check the memory values between pxStack and pxEndOfStack, we'll be able to see how much of the stack is used and how much of it was left untouched. (stays on the default value of A5A5). However, FreeRTOS simplifies this further with uxHighWaterMark, which returns the minimum amount of free stack the task has ever had, so we can simply watch the values in a debugger and substract it from the stack size (in this case 400+1), as the stack counting starts on the lower byte of the last word and never checks the higher one. What we get is available size in words (in my scenario a word is 2B)

I have a PIC24F board at hand, and after measuring stack size via the experimental approach, I got 122B and 208B for both of the tasks respectfully with the experimental approach. Let's now try the analytical approach to see, how big the stack is in reality. If we look at the first task, we can count just from the C code that vStackTask1 is three words, (frame pointer (1) + pvParameters (1) + usI (1) = 3), by same logic prvFoo is 16, prvBar is 6 and prvBinomial is 5. Meaning Task one is 19 words. Adding 42 words as interrupts makes it 61 words, meaning 122B, which is how much we got with our experimental approach. However, if we tried counting the second task using the same approach, we'd end up at a lower number than with experimental approach. That is because there is more going behind the scenes than the C code shows. return prvBinomial(usN - 1, usK - 1) + prvBinomial(usN - 1, usK); the processor does not call both functions at once, so it needs to create a temporary variable into which it stores the intermediate result. Meaning we get 6 words in total. Even though it is recursion, on stack there can only be 10 calls of it, meaning 6x10=60 words. Adding 2 words of the second tasks to it, we get 62+42=104 words, or 208B.

We now see what our stack size must be, which allows us to not waste memory and at the same time prove we will not run out of it.