Stack high water mark monitoring in FreeRTOS - Time & Space Complexity

Time Complexity: Stack high water mark monitoring

O(n)

Understanding Time Complexity

We want to understand how checking the stack high water mark scales as the stack size changes.

This helps us know how long it takes to find the minimum free stack space.

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS code snippet.

UBaseType_t uxTaskGetStackHighWaterMark( TaskHandle_t xTask ) {
    uint8_t *pucStack = ( uint8_t * ) xTask->pxStack;
    UBaseType_t uxCount = 0;

    while( *pucStack == ( uint8_t ) tskSTACK_FILL_BYTE ) {
        pucStack++;
        uxCount++;
    }

    return uxCount;
}
    

This code counts how many bytes at the start of the stack are still unused (filled with a known pattern).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that checks each byte of the stack until it finds a byte not equal to the fill pattern.
• How many times: Up to the total stack size in bytes, depending on how much stack is unused.

How Execution Grows With Input

The number of operations grows linearly with the amount of unused stack space.

Input Size (stack bytes unused)	Approx. Operations (checks)
10	10
100	100
1000	1000

Pattern observation: If the unused stack doubles, the number of checks doubles too.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows directly with the size of the unused stack space.

Common Mistake

[X] Wrong: "Checking the stack high water mark is always a fixed, quick operation regardless of stack size."

[OK] Correct: The check loops through unused stack bytes, so larger unused stacks take more time to check.

Interview Connect

Understanding how stack monitoring scales helps you reason about system performance and reliability in embedded systems.

Self-Check

"What if the stack fill pattern was checked in blocks of 4 bytes instead of 1 byte? How would the time complexity change?"