Stack and Stack Overflow

Hello Guys, In this section we will discuss about -
1. What is Stack ?
2. What is Stack overflow ?
3. How to avoid Stack overflow ?
Basically, this will be related to Embedded Systems.       

What is stack?

Stack is a special region of our process's memory, where processes are tracked. The types of data stored in the stack include -

1. local variables

2. return addresses

3. function arguments

4. compiler temporaries

5. interrupt contexts

So basically, we can say that the stack is an area of RAM where a program stores temporary data during the execution of code blocks.

Whenever a new local variable is declared it is pushed onto the stack.

The life span of variables on the stack is limited to the duration of the function. As soon as the function returns, the used stack memory will be free for use by subsequent function calls.

Stack follows Last-In-First-Out data structure.

A “stack pointer” register tracks the top of the stack; it is adjusted each time a value is “pushed” onto the stack. The set of values pushed for one function call is termed a “stack frame”; A stack frame consists at minimum of a return address.

Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables. This is how recursive functions in C can work. Each time a recursive function calls itself, a new stack frame is used, so one set of variables doesn’t interfere with the variables from another instance of the function.

We need to recognize that many, and indeed most, embedded systems contain multiple stacks.

Some common combinations are Single stack, Two stacks, One stack per task. 

Single stack - This is the classic approach where function return addresses, parameters, automatic variables and registers are all saved on to a single stack, microchips 32-bit compiler when used without an RTOS has this architecture.

Two stacks, one for return addresses and one for everything else. This approach is used by IAR. IAR refers to these two stacks as the RSTACK and the CSTACK. You also effectively get this approach with microprocessors that have a hardware return stack. For example, on 8-bit PIC processors.

Two stacks, one for exception handling and one for everything else. This is often done with hardware that has a dedicated exception stack.

One stack per task. This is a common approach when using an RSTACK.

How stack grows?

On the standard PC x86 computer architecture it grows toward address zero, on some other architectures it grows the opposite direction.

What is stack overflow?

Stack overflow is when a function or program uses more memory than is in the stack. As it grows beyond its allocated space, the dynamic stack contents begin to overwrite other things, such as critical application code and data. The stack is a fixed amount of memory that is set statically by the programmer before execution.

In embedded systems you might only have 256 bytes for the stack, and if each function takes up 32 bytes then you can only have function calls 8 deep - function 1 calls function 2 who calls function 3 who calls function 4 .... who calls function 8 who calls function 9, but function 9 overwrites memory outside the stack. This might overwrite memory, code, etc.

Many programmers make this mistake by calling function A that then calls function B, that then calls function C, that then calls function A. It might work most of the time, but just once the wrong input will cause it to go in that circle forever until the computer recognizes that the stack is overblown.

Recursive functions are also a cause for this, but if you're writing recursively (i.e. your function calls itself) then you need to be aware of this and use static/global variables to prevent infinite recursion.

So basically following There are two cases in which stack overflow can occur-

1. If we declare large number of local variables or declare an array or matrix or any higher dimensional array of large size can result in overflow of stack.

2. If function recursively call itself infinite times then the stack is unable to store large number of local variables used by every function call and will result in overflow of stack.

The above fig. describes how stack overwrites adjacent memory.

How to avoid stack overflow?

Embedded Systems

In the embedded world, especially in high reliability code (automotive, aircraft, space) you do extensive code reviews and checking, but you also do the following-

• Disallow recursion and cycles - enforced by policy and testing.
• Keep code and stack far apart (code in flash, stack in RAM, and never the twain shall meet).
• Place guard bands around the stack - empty area of memory that you fill with a magic number (usually a software interrupt instruction, but there are many options here), and hundreds or thousands of times a second you look at the guard bands to make sure they haven't been overwritten.
• Use memory protection (I.e. no execute on the stack, no read or write just outside the stack).
• Interrupts don't call secondary functions - they set flags, copy data, and let the application take care of processing it (otherwise you might get 8 deep in your function call tree, have an interrupt, and then go out another few functions inside the interrupt, causing the blowout). You have several call trees - one for the main processes, and one for each interrupt. If your interrupts can interrupt each other... well, there be dragons…

High-level languages and systems

But in high level languages run on operating systems-

• Reduce your local variable storage (local variables are stored on the stack - although compilers are pretty smart about this and will sometimes put big locals on the heap if your call tree is shallow)
• Avoid or strictly limit recursion.
• Don't break your programs up too far into smaller and smaller functions - even without counting local variables each function call consumes as much as 64 bytes on the stack (32 bit processor, saving half the CPU registers, flags, etc)

Keep your call tree shallow (similar to the above statement)

 To prevent - always make sure there's an exit path that will be hit.

Stack sentinels and avoidance of recursion are an entrenched part of embedded systems.

MISRA Software Guidelines discourage recursion, saying that it can cause unpredictable behavior (MISRA Guidelines, pg. 20).

NASA recommends using stack guards (essentially the same as the technique that I call “stack sentinels”) to check for stack overflow or corruption (NASA 2004, p. 93).

Some best practices for preventing stack overflow

• Avoid stack-hogging functions like printf( ) and related functions. Try to pass by reference instead of by copy. When passing by copy, it tends to go on the stack, particularly if it’s an array. With an array, it’s easier to run out of the stack and overflow the stack rapidly.
• Another best practice is to limit the number of arguments to a function; for example, the first four arguments go into registers, and all subsequent arguments go onto the stack.  The Application Binary Interface (ABI) of an MCU tells a compiler how many arguments can be passed in the registers; all others must be passed on the stack.
• Last, avoid recursive functions (a function that calls itself) as they use a significant portion of the stack as they go deeper. If you must use recursion, set variables to stop infinite recursion from happening. However, it’s a good practice to avoid recursion altogether.

Some solutions mentioned above are not portable, but quite fine.

It is typically part of compiler’s job to adhere to an ABI. An embedded ABI operates at the machine code level and determines how function calls are made, file formatting, use of the register, and the framework of the stack. ABIs vary between architectures in the embedded world.