Stack overflow detection in Embedded C

Introduction

Stack overflow detection helps catch when a program uses more memory than the stack can hold. This prevents crashes and unexpected behavior.

When writing embedded programs with limited memory.

When debugging unexpected program crashes.

When you want to ensure your program does not overwrite important data.

When working with recursive functions that might use too much stack.

When developing safety-critical systems that must avoid memory errors.

Syntax

Embedded C

/* Example of stack overflow detection in embedded C */
#define STACK_SIZE 256

unsigned char stack[STACK_SIZE];
unsigned char *stack_pointer = stack;

// Initialize stack pointer to start of stack
void init_stack() {
    stack_pointer = stack;
}

// Push data onto stack
int push(unsigned char value) {
    if (stack_pointer - stack >= STACK_SIZE) {
        // Stack overflow detected
        return -1;
    }
    *stack_pointer = value;
    stack_pointer++;
    return 0;
}

// Pop data from stack
int pop(unsigned char *value) {
    if (stack_pointer == stack) {
        // Stack underflow
        return -1;
    }
    stack_pointer--;
    *value = *stack_pointer;
    return 0;
}

The stack is represented as an array with a fixed size.

The stack pointer points to the next free position in the stack.

Examples

When the stack is empty, the stack pointer points to the start of the stack array.

Embedded C

/* Example: Stack is empty */
init_stack();
// stack_pointer == stack, no overflow

After pushing one value, the stack pointer moves forward by one.

Embedded C

/* Example: Stack has one element */
init_stack();
push(42);
// stack_pointer points one byte past start

When trying to push more than the stack size, overflow is detected and push returns -1.

Embedded C

/* Example: Stack overflow detection */
init_stack();
for (int i = 0; i < STACK_SIZE + 1; i++) {
    if (push(i) == -1) {
        // Overflow detected when i == STACK_SIZE
        break;
    }
}

Trying to pop from an empty stack returns an error.

Embedded C

/* Example: Stack underflow detection */
init_stack();
unsigned char value;
if (pop(&value) == -1) {
    // Underflow detected because stack is empty
}

Sample Program

This program creates a small stack of size 5. It pushes five values, then tries to push one more to cause overflow. It prints the stack contents before and after. Then it pops all values and tries to pop once more to show underflow detection.

Embedded C

#include <stdio.h>

#define STACK_SIZE 5

unsigned char stack[STACK_SIZE];
unsigned char *stack_pointer = stack;

void init_stack() {
    stack_pointer = stack;
}

int push(unsigned char value) {
    if (stack_pointer - stack >= STACK_SIZE) {
        // Stack overflow detected
        return -1;
    }
    *stack_pointer = value;
    stack_pointer++;
    return 0;
}

int pop(unsigned char *value) {
    if (stack_pointer == stack) {
        // Stack underflow
        return -1;
    }
    stack_pointer--;
    *value = *stack_pointer;
    return 0;
}

void print_stack() {
    printf("Stack contents: ");
    for (unsigned char *ptr = stack; ptr < stack_pointer; ptr++) {
        printf("%d ", *ptr);
    }
    printf("\n");
}

int main() {
    init_stack();
    printf("Initial stack state:\n");
    print_stack();

    printf("Pushing values 10, 20, 30, 40, 50:\n");
    for (unsigned char value = 10; value <= 50; value += 10) {
        if (push(value) == -1) {
            printf("Stack overflow detected when pushing %d\n", value);
            break;
        }
    }
    print_stack();

    printf("Attempting to push 60 to cause overflow:\n");
    if (push(60) == -1) {
        printf("Stack overflow detected when pushing 60\n");
    }
    print_stack();

    printf("Popping all values:\n");
    unsigned char popped_value;
    while (pop(&popped_value) == 0) {
        printf("Popped: %d\n", popped_value);
    }
    printf("Stack is now empty.\n");

    printf("Attempting to pop from empty stack:\n");
    if (pop(&popped_value) == -1) {
        printf("Stack underflow detected.\n");
    }

    return 0;
}

Important Notes

Time complexity of push and pop operations is O(1) because they only move the pointer and read/write one value.

Space complexity is O(n) where n is the stack size, as the stack uses a fixed array.

A common mistake is not checking for overflow before pushing, which can overwrite memory and cause bugs.

Use stack overflow detection when you want to avoid memory corruption in embedded systems with limited stack size.

Summary

Stack overflow detection prevents writing beyond the stack's fixed size.

It is done by checking the stack pointer before pushing data.

Detecting overflow helps avoid crashes and data corruption in embedded programs.

Practice

1.

What is the main purpose of stack overflow detection in embedded C?

easy

A. To increase the stack size dynamically

B. To prevent writing data beyond the stack's fixed size

C. To optimize CPU speed

D. To clear the stack memory automatically

Solution

1. Step 1: Understand stack overflow concept

   Stack overflow occurs when data is pushed beyond the stack's allocated size.

2. Step 2: Identify purpose of detection

   Detection helps prevent writing beyond stack limits, avoiding crashes and corruption.

3. Final Answer:

   To prevent writing data beyond the stack's fixed size -> Option B

4. Quick Check:

   Stack overflow detection = prevent overflow [OK]

Hint: Stack overflow detection stops writes beyond stack size [OK]

Common Mistakes:

• Thinking stack size can grow automatically
• Confusing overflow detection with CPU optimization
• Assuming stack clears itself on overflow

2.

Which of the following code snippets correctly checks for stack overflow before pushing a value?

int stack[10];
int sp = 0; // stack pointer
int value = 5;

// Check before push
if (____) {
    stack[sp++] = value;
}

easy

A. sp < 10

B. sp > 10

C. sp == 10

D. sp >= 10

Solution

1. Step 1: Understand stack pointer and size

   Stack size is 10, valid indices are 0 to 9, so sp must be less than 10 to push.

2. Step 2: Choose correct condition

   Condition 'sp < 10' ensures we don't write beyond array bounds.

3. Final Answer:

   sp < 10 -> Option A

4. Quick Check:

   Push only if sp less than stack size [OK]

Hint: Check sp < stack size before push [OK]

Common Mistakes:

• Using sp >= 10 allows overflow
• Using sp == 10 pushes out of bounds
• Using sp > 10 misses last valid index

3.

What will be the output of the following code snippet?

int stack[3];
int sp = 0;

void push(int val) {
    if (sp < 3) {
        stack[sp++] = val;
        printf("Pushed %d\n", val);
    } else {
        printf("Stack Overflow!\n");
    }
}

int main() {
    push(1);
    push(2);
    push(3);
    push(4);
    return 0;
}

medium

A. Pushed 1
Pushed 2
Pushed 3
Stack Overflow!

B. Pushed 1
Pushed 2
Pushed 3
Pushed 4

C. Stack Overflow!
Stack Overflow!
Stack Overflow!
Stack Overflow!

D. Pushed 1
Pushed 2
Stack Overflow!
Stack Overflow!

Solution

1. Step 1: Trace push calls and stack pointer

   First three pushes succeed because sp < 3; fourth push fails as sp == 3.

2. Step 2: Check output for each push

   Outputs "Pushed 1", "Pushed 2", "Pushed 3", then "Stack Overflow!" on last push.

3. Final Answer:

   Pushed 1 Pushed 2 Pushed 3 Stack Overflow! -> Option A

4. Quick Check:

   Pushes succeed until sp == 3, then overflow [OK]

Hint: Pushes stop when sp reaches stack size [OK]

Common Mistakes:

• Assuming push always succeeds
• Ignoring else branch output
• Confusing sp increment timing

4.

Identify the bug in the following stack push function that causes stack overflow detection to fail:

void push(int val) {
    if (sp <= 3) {
        stack[sp++] = val;
    } else {
        printf("Overflow detected\n");
    }
}

medium

A. sp is not incremented after push

B. Stack size is not checked at all

C. Condition should be sp < 3, not sp <= 3

D. printf statement is inside if block

Solution

1. Step 1: Analyze condition sp <= 3 with stack size 3

   sp can be 3, but valid indices are 0,1,2; sp=3 causes out-of-bounds write.

2. Step 2: Correct condition to prevent overflow

   Use sp < 3 to allow only valid indices 0 to 2.

3. Final Answer:

   Condition should be sp < 3, not sp <= 3 -> Option C

4. Quick Check:

   Use strict less than to avoid overflow [OK]

Hint: Use sp < stack size, not <=, to avoid overflow [OK]

Common Mistakes:

• Allowing sp == stack size causes overflow
• Not incrementing sp after push
• Misplacing overflow message

5.

You have a stack of size 5 and want to implement a safe push function that returns 0 on success and -1 on overflow. Which code snippet correctly implements this?

int stack[5];
int sp = 0;

int push(int val) {
    // Fill in condition
    if (__________) {
        stack[sp++] = val;
        return 0;
    } else {
        return -1;
    }
}

hard

A. sp > 5

B. sp <= 5

C. sp == 5

D. sp < 5

Solution

1. Step 1: Understand stack size and valid indices

   Stack size is 5, so valid indices are 0 to 4; sp must be less than 5 to push safely.

2. Step 2: Choose condition that prevents overflow

   Condition 'sp < 5' ensures no out-of-bounds write and returns 0 on success.

3. Final Answer:

   sp < 5 -> Option D

4. Quick Check:

   Push only if sp less than stack size [OK]

Hint: Return error if sp not less than stack size [OK]

Common Mistakes:

• Using sp <= 5 allows overflow
• Returning success on overflow
• Checking sp == 5 instead of less than