Difference between revisions of "Stack"

From SEGGER Wiki
Jump to: navigation, search
m
m
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
  +
  +
  +
[[Category:Knowledge Base]]
 
A stack is a memory area used to store and retrieve information in LIFO (last in, first out) order.
 
A stack is a memory area used to store and retrieve information in LIFO (last in, first out) order.
It is very commonly used in basically any computer system and any program.
+
It is very commonly used; basically in almost every computer system and almost every program.
 
==Basic operations==
 
==Basic operations==
There are basically only 2 operation which can be performed on a stack:
+
There are basically only two operations performed on a stack:
 
* Push - Adding information to the stack
 
* Push - Adding information to the stack
 
* Pop - Removing information from stack
 
* Pop - Removing information from stack
  +
On many systems, a function call comes with an implicit push of the return address, and likewise a return from subroutine pops (retrieves) the return address from the stack.
  +
Many newer CPUs have a register which allows the CPU to remember the return address on a call. This is the case for example in modern ARM CPUs, which use R14 (for the 32-bit architectures) as link register (LR).
  +
This way, in a leaf function (which does not call other functions), the return address does not need to be saved on the stack,
  +
making the program slightly smaller but mostly more efficient.
  +
A call in these architectures is a
  +
BL SubRoutine // Call subroutine, saving the return address (next PC) to LR (R14)
  +
  +
SubRoutine:
  +
BX LR // Simply jump back to the former PC which has been saved in the LR.
  +
// Note that "BX" is historic and stands for "branch with potential mode switch
  +
// between ARM and Thumb modes
  +
   
 
A stack needs a stack pointer (SP), which typically points to the last item pushed onto the stack.
 
A stack needs a stack pointer (SP), which typically points to the last item pushed onto the stack.
Hardware stacks used for program execution (that contain return addresses and activation frames) typically grow
+
Hardware stacks, used for program execution (that contain return addresses and activation frames), typically grow
downward from high memory to low memory; pushing a 32-bit value onto a stack will decrement the stack pointer
+
downward from high memory to low memory. Pushing a 32-bit value onto a stack will decrement the stack pointer
by 4, where pop a 32-bit value does the opposite and increments the stack pointer by 4.
+
by 4, whereas popping a 32-bit value does the opposite and increments the stack pointer by 4.
   
 
==Stack overflow==
 
==Stack overflow==
One problem that is hard to control and avoid is stack overflow. It happens when the application has pushed more data onto the stack than actually fit,
+
One problem that is hard to control and avoid is stack overflow. It happens when the application has pushed more data onto the stack than it can store,
thereby overwriting other data areas or writing into areas that are not data. In any case, the effects will usually create problem when program execution continues,
+
thereby overwriting other data areas or writing onto areas that are not data. In any case, the effects will usually create problems when program execution continues,
 
very likely a crash of the program.
 
very likely a crash of the program.
This is a problem especially in smaller [[Embedded System]]s, which do not have a memory management unit (MMU) or
+
This is a especially problematic in smaller [[Embedded System]]s, which do not have a memory management unit (MMU) or
 
memory protection unit (MPU) to control the access to the stack.
 
memory protection unit (MPU) to control the access to the stack.

Latest revision as of 14:53, 20 May 2023

A stack is a memory area used to store and retrieve information in LIFO (last in, first out) order. It is very commonly used; basically in almost every computer system and almost every program.

Basic operations

There are basically only two operations performed on a stack:

  • Push - Adding information to the stack
  • Pop - Removing information from stack

On many systems, a function call comes with an implicit push of the return address, and likewise a return from subroutine pops (retrieves) the return address from the stack. Many newer CPUs have a register which allows the CPU to remember the return address on a call. This is the case for example in modern ARM CPUs, which use R14 (for the 32-bit architectures) as link register (LR). This way, in a leaf function (which does not call other functions), the return address does not need to be saved on the stack, making the program slightly smaller but mostly more efficient. A call in these architectures is a

BL SubRoutine     // Call subroutine, saving the return address (next PC) to LR (R14)
SubRoutine:
  BX  LR          // Simply jump back to the former PC which has been saved in the LR.
                  // Note that "BX" is historic and stands for "branch with potential mode switch
                  // between ARM and Thumb modes


A stack needs a stack pointer (SP), which typically points to the last item pushed onto the stack. Hardware stacks, used for program execution (that contain return addresses and activation frames), typically grow downward from high memory to low memory. Pushing a 32-bit value onto a stack will decrement the stack pointer by 4, whereas popping a 32-bit value does the opposite and increments the stack pointer by 4.

Stack overflow

One problem that is hard to control and avoid is stack overflow. It happens when the application has pushed more data onto the stack than it can store, thereby overwriting other data areas or writing onto areas that are not data. In any case, the effects will usually create problems when program execution continues, very likely a crash of the program. This is a especially problematic in smaller Embedded Systems, which do not have a memory management unit (MMU) or memory protection unit (MPU) to control the access to the stack.