Stack overflow detection (method 1 and 2) in FreeRTOS - Time & Space Complexity

Time Complexity: Stack overflow detection (method 1 and 2)

O(1) for Method 1, O(n) for Method 2

Understanding Time Complexity

We want to understand how checking for stack overflow costs time as tasks run in FreeRTOS.

How does the time to detect overflow grow when the stack size or number of tasks changes?

Scenario Under Consideration

Analyze the time complexity of these two stack overflow detection methods.

// Method 1: Check stack watermark
if (uxTaskGetStackHighWaterMark(NULL) == 0) {
    // Stack overflow detected
}

// Method 2: Check stack fill pattern
for (int i = 0; i < stackSize; i++) {
    if (stack[i] != STACK_FILL_PATTERN) {
        break; // Stack used up to i
    }
}

Method 1 uses a built-in function to get minimum free stack. Method 2 scans the stack memory to find usage.

Identify Repeating Operations

Look at what repeats in each method.

• Primary operation in Method 1: A single function call that returns a stored value.
• Primary operation in Method 2: A loop scanning each stack element until a pattern changes.
• How many times: Method 1 runs once per check; Method 2 may scan up to the entire stack size.

How Execution Grows With Input

Method 1's time stays about the same no matter the stack size.

Method 2's time grows as the stack size grows, because it may check each stack element.

Input Size (stackSize)	Method 1 Ops	Method 2 Ops
10	1	up to 10
100	1	up to 100
1000	1	up to 1000

Pattern observation: Method 1 is constant time; Method 2 grows linearly with stack size.

Final Time Complexity

Time Complexity: O(1) for Method 1, O(n) for Method 2

Method 1 takes the same time regardless of stack size; Method 2 takes longer as stack size grows.

Common Mistake

[X] Wrong: "Both methods take the same time because they both detect overflow."

[OK] Correct: Method 1 uses a stored value and is quick; Method 2 scans memory and takes longer as stack grows.

Interview Connect

Understanding how different detection methods scale helps you explain trade-offs clearly in real projects.

Self-Check

What if Method 2 used a binary search on the stack pattern instead of a linear scan? How would the time complexity change?

Practice

1. What is the main purpose of stack overflow detection in FreeRTOS?

easy

A. To reduce RAM usage by tasks

B. To prevent tasks from using more stack memory than allocated

C. To increase CPU clock speed

D. To speed up task switching

Solution

1. Step 1: Understand stack overflow concept

   Stack overflow happens when a task uses more stack memory than allocated, causing memory corruption.

2. Step 2: Identify purpose of detection

   Stack overflow detection helps catch this problem early to prevent crashes or unpredictable behavior.

3. Final Answer:

   To prevent tasks from using more stack memory than allocated -> Option B

4. Quick Check:

   Stack overflow detection = prevent excess stack use [OK]

Hint: Stack overflow detection stops tasks using too much stack [OK]

Common Mistakes:

• Confusing stack overflow with CPU speed
• Thinking it reduces RAM usage
• Assuming it speeds up task switching

2. Which FreeRTOS configuration enables Method 1 stack overflow detection?

easy

A. configMAX_PRIORITIES set to 5

B. configUSE_PREEMPTION set to 0

C. configUSE_IDLE_HOOK set to 1

D. configCHECK_FOR_STACK_OVERFLOW set to 1 or 2

Solution

1. Step 1: Identify config for stack overflow detection

   FreeRTOS uses configCHECK_FOR_STACK_OVERFLOW to enable Method 1 detection.

2. Step 2: Understand valid values

   Setting configCHECK_FOR_STACK_OVERFLOW to 1 or 2 activates automatic detection on context switches.

3. Final Answer:

   configCHECK_FOR_STACK_OVERFLOW set to 1 or 2 -> Option D

4. Quick Check:

   configCHECK_FOR_STACK_OVERFLOW = 1 or 2 [OK]

Hint: Method 1 uses configCHECK_FOR_STACK_OVERFLOW = 1 or 2 [OK]

Common Mistakes:

• Confusing unrelated config options
• Using configUSE_PREEMPTION for stack checks
• Setting configMAX_PRIORITIES thinking it affects stack

3. Given this FreeRTOS hook function for Method 1:

void vApplicationStackOverflowHook(TaskHandle_t xTask, char *pcTaskName) {
    printf("Stack overflow detected in task: %s\n", pcTaskName);
    while(1); // Halt
}

What will happen if a stack overflow is detected?

medium

A. Prints task name and halts the system

B. Resets the task automatically

C. Ignores the overflow and continues

D. Logs overflow but continues running

Solution

1. Step 1: Analyze the hook function code

   The function prints the task name where overflow occurred and then enters an infinite loop.

2. Step 2: Understand effect of infinite loop

   The infinite loop halts the system to prevent further damage after overflow detection.

3. Final Answer:

   Prints task name and halts the system -> Option A

4. Quick Check:

   Stack overflow hook prints and halts [OK]

Hint: Stack overflow hook prints and stops system [OK]

Common Mistakes:

• Thinking system resets automatically
• Assuming overflow is ignored
• Believing task restarts without halt

4. In Method 2 stack overflow detection, which mistake will cause incorrect detection?

medium

A. Using vApplicationStackOverflowHook function

B. Enabling configCHECK_FOR_STACK_OVERFLOW to 2

C. Not initializing the stack pointer check value properly

D. Setting configUSE_PREEMPTION to 1

Solution

1. Step 1: Understand Method 2 detection

   Method 2 manually checks stack pointer against a known value to detect overflow.

2. Step 2: Identify common error

   If the initial stack pointer check value is not set correctly, the comparison will be invalid, causing false negatives or positives.

3. Final Answer:

   Not initializing the stack pointer check value properly -> Option C

4. Quick Check:

   Method 2 needs correct stack pointer init [OK]

Hint: Method 2 needs proper stack pointer initialization [OK]

Common Mistakes:

• Confusing Method 1 config with Method 2
• Ignoring stack pointer initialization
• Assuming hook function is used in Method 2

5. You want to implement stack overflow detection in your FreeRTOS project using Method 1. Which steps should you follow to ensure it works correctly?

hard

A. Set configCHECK_FOR_STACK_OVERFLOW to 1 or 2 and implement vApplicationStackOverflowHook

B. Manually compare stack pointers in each task without config changes

C. Disable preemption and use configUSE_IDLE_HOOK for detection

D. Increase task stack size to avoid overflow without detection

Solution

1. Step 1: Enable Method 1 detection in config

   Set configCHECK_FOR_STACK_OVERFLOW to 1 or 2 to activate automatic detection during context switches.

2. Step 2: Implement the hook function

   Define vApplicationStackOverflowHook to handle overflow events, e.g., log and halt.

3. Final Answer:

   Set configCHECK_FOR_STACK_OVERFLOW to 1 or 2 and implement vApplicationStackOverflowHook -> Option A

4. Quick Check:

   Method 1 = config + hook function [OK]

Hint: Method 1 needs config and hook function implemented [OK]

Common Mistakes:

• Trying manual pointer checks for Method 1
• Disabling preemption thinking it helps detection
• Ignoring hook function implementation