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?"

Practice

1.

What does the stack high water mark indicate in FreeRTOS?

easy

A. The total stack size allocated to a task

B. The minimum amount of free stack space a task has had

C. The maximum CPU usage of a task

D. The number of tasks currently running

Solution

1. Step 1: Understand stack high water mark meaning

   The stack high water mark shows the smallest amount of unused stack space a task has had since it started.

2. Step 2: Compare with other options

   Other options describe CPU usage, total stack size, or task count, which are unrelated to stack high water mark.

3. Final Answer:

   The minimum amount of free stack space a task has had -> Option B

4. Quick Check:

   Stack high water mark = minimum free stack space [OK]

Hint: Remember: 'high water mark' means lowest free stack left [OK]

Common Mistakes:

• Confusing stack size with stack usage
• Thinking it measures CPU or task count
• Assuming it shows maximum stack used

2.

Which is the correct way to get the stack high water mark of the current task in FreeRTOS?

?

easy

A. uxTaskGetStackHighWaterMark(NULL);

B. uxTaskGetStackHighWaterMark(currentTask);

C. getStackHighWaterMark(NULL);

D. uxGetStackHighWaterMark();

Solution

1. Step 1: Recall function signature

   The FreeRTOS function to get stack high water mark is uxTaskGetStackHighWaterMark, which takes a task handle or NULL for current task.

2. Step 2: Identify correct usage

   Passing NULL gets the current task's high water mark. Other options use wrong function names or parameters.

3. Final Answer:

   uxTaskGetStackHighWaterMark(NULL); -> Option A

4. Quick Check:

   Use NULL for current task in uxTaskGetStackHighWaterMark [OK]

Hint: Use NULL to refer to current task handle [OK]

Common Mistakes:

• Using wrong function names
• Passing invalid parameters instead of NULL
• Assuming no parameter needed

3.

Given the following code snippet, what will be the output if the task's minimum free stack space was 50 words?

UBaseType_t highWaterMark = uxTaskGetStackHighWaterMark(NULL);
printf("High water mark: %u\n", highWaterMark);

medium

A. High water mark: 50

B. High water mark: 0

C. High water mark: Stack overflow

D. Compilation error

Solution

1. Step 1: Understand uxTaskGetStackHighWaterMark output

   This function returns the minimum free stack space (in words) the task had, which is 50 in this case.

2. Step 2: Analyze printf output

   The printf prints the unsigned integer value returned, so output will be "High water mark: 50".

3. Final Answer:

   High water mark: 50 -> Option A

4. Quick Check:

   Function returns minimum free stack, printed as number [OK]

Hint: Function returns minimum free stack words, print as unsigned int [OK]

Common Mistakes:

• Assuming it returns zero on no overflow
• Thinking it returns error string
• Confusing with stack size or usage

4.

Identify the error in this code snippet intended to get the stack high water mark of a task named myTaskHandle:

UBaseType_t mark = uxTaskGetStackHighWaterMark(myTaskHandle);

Assume myTaskHandle is a valid task handle.

medium

A. Return type should be int, not UBaseType_t

B. Function name is incorrect, should be uxGetStackHighWaterMark

C. Parameter should be NULL to get any task's high water mark

D. No error, code is correct

Solution

1. Step 1: Verify function and parameter usage

   uxTaskGetStackHighWaterMark takes a task handle to get that task's high water mark. Using myTaskHandle is valid.

2. Step 2: Check return type and function name

   Return type UBaseType_t is correct. Function name is correct as per FreeRTOS API.

3. Final Answer:

   No error, code is correct -> Option D

4. Quick Check:

   Correct function and parameter usage means no error [OK]

Hint: Use task handle parameter for specific task, NULL for current task [OK]

Common Mistakes:

• Thinking NULL is required for all tasks
• Using wrong function names
• Confusing return types

5.

You want to monitor stack usage of multiple tasks and log a warning if any task's stack high water mark falls below 20 words. Which approach is best?

hard

A. Only check the current task's stack high water mark using NULL parameter

B. Increase all task stack sizes to 20 words to avoid overflow

C. Periodically call uxTaskGetStackHighWaterMark for each task handle and check if value < 20

D. Use vTaskDelete to remove tasks with low stack

Solution

1. Step 1: Understand monitoring multiple tasks

   To monitor multiple tasks, you must check each task's stack high water mark individually using their task handles.

2. Step 2: Implement threshold check

   Calling uxTaskGetStackHighWaterMark for each task and comparing to 20 words allows detecting low stack and logging warnings.

3. Final Answer:

   Periodically call uxTaskGetStackHighWaterMark for each task handle and check if value < 20 -> Option C

4. Quick Check:

   Check each task's high water mark against threshold [OK]

Hint: Check each task's high water mark, compare to threshold [OK]

Common Mistakes:

• Checking only current task misses others
• Assuming increasing stack size fixes monitoring
• Deleting tasks instead of warning