2

What does the ascending and descending mean on the ARM stack ? What does full and empty mean ? If the stack is full, wouldn't the push instruction result in stack overflow ?

ARM System Developers Guide

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Circuit_Breaker0.7
  • 125
  • 1
  • 5
  • Thanks for reminding, I have added the test from where I am reading about the ARM stack – Circuit_Breaker0.7 Nov 17 '21 at 17:29
  • @Circuit_Breaker0.7 Please do not add pictures of text. Instead, post the text as text. That said, the text seems to answer the questions you have in a very clear manner. What part do you not understand? – fuz Nov 17 '21 at 17:30
  • 1
    SO has helpfully linked [Can i configure a ARM processor for Ascending Stack growth direction?](https://stackoverflow.com/questions/906443/can-i-configure-a-arm-processor-for-ascending-stack-growth-direction) to which the answer is "sort of, but not really". –  Nov 17 '21 at 17:33
  • @fuz Why do we need two separate instructions of Full and Empty stack when we can just use one instead ? Also why use ascending and descending and not just one ? Wouldn't it make the design and implementations easier ? – Circuit_Breaker0.7 Nov 17 '21 at 17:50
  • 1
    ARM does not really have dedicated push and pop instructions. It has load/store multiple instructions that [can also be used to implement a stack](https://developer.arm.com/documentation/dui0068/b/Writing-ARM-and-Thumb-Assembly-Language/Load-and-store-multiple-register-instructions/Implementing-stacks-with-LDM-and-STM). The designer of the operating system can choose full/empty ascending/descending and which register will be used as the stack pointer according to their taste. Although if you want to use Thumb instructions, those decide the convention for you as full descending r13. –  Nov 17 '21 at 18:06
  • So the details of the stack on ARM are just a convention set by the OS designer. But once it is decided, all the processes on that OS have to follow it or there will be a mess. –  Nov 17 '21 at 18:12
  • 2
    @Circuit_Breaker0.7 The instructions do different things. They differ in whether the stack pointer is changed before or after the memory access and whether the stack pointer is incremented or decremented. The combination of these two options yields the four possible stack models. – fuz Nov 17 '21 at 18:13
  • 1
    This is a different usage of "full" and "empty" (and kind of an annoying one, here). "Full" doesn't mean "unable to accept more entries" or "would overflow". It is just a name for the style of stack management where the stack pointer points to the location used previously, instead of the one to be used next. – Nate Eldredge Nov 17 '21 at 18:16
  • Don't understand it? then keep reading the documents until you do. – Jake 'Alquimista' LEE Nov 18 '21 at 12:35
  • that is a very well written section of a manual, no confusion whatsoever. – old_timer Nov 18 '21 at 15:50
  • arm has dedicated push and pop in thumb mode, and pseudo code otherwise that becomes ldm/stm – old_timer Nov 18 '21 at 15:50
  • why does arm have these options? so the programmer has some flexibility and choice, and is not forced into one solution. gcc and others basically use a decending with the sp pointing at a used item on the stack (full). (or most folks writing code in asm that I have seen). – old_timer Nov 18 '21 at 15:53
  • what part do you not understand, that is one of the best descriptions I have seen thus far, well written. It answers your questions, decending,meaning addresses decreas as you push, aschending meaning addresses increase as you push. – old_timer Nov 18 '21 at 15:54
  • full means sp points at a location that has an item, next push requires an address increment/decrement. empty means sp points at an empty location, next push write then increment/decrement – old_timer Nov 18 '21 at 15:55

1 Answers1

2

A hardware stack is common to most CPUs and there are several different ways it is implemented in hardware. Most CPUs use a descending stack, which means that when you PUSH a new value, the stack pointer's value decreases by the amount of data pushed (on ARM this is 4 bytes) and the new value is pushed onto the stack. Here's an example using Z80 Assembly, which uses a full descending stack. (Even though the question is about ARM, I feel it best to use a simpler CPU which behaves similarly to make the explanation a little more clear.)

ld sp,0xFFFF
ld bc,0x1234
ld de,0x5678
push bc
push de

At this point in execution if you were to read a hexdump of the stack you'd see this:

0xFF00: 00 00 00 00 00 00 00 00 00 00 00 |78 56| |34 12| 00
                                          E   D    C  B

The vertical bars and the registers below were added by me to show where those values came from, they're not going to appear in a typical hexdump program. This is just to illustrate how the stack works in general. The ARM is very similar, however it can be configured to be big-endian (which means that the bytes are pushed in the order you would expect rather than sequentially reversed as you see here, which is actually the norm for most CPUs)

The fact that the Z80 uses a full stack convention is reflected in that the current value of the stack pointer is 0xFFFB - which points directly to the last byte we pushed. A CPU that uses the empty stack convention would have its stack pointer pointing to 0xFFF9 right now.

A stack overflow is when the stack has reached its "limit" and is starting to overwrite the hardware's normal RAM area (a.k.a "the heap"). I'll use the Game Boy Advance to show this example, which actually uses an ARM CPU. The heap starts at 0x02000000, and we'll say our stack pointer is initialized to 0x03000000. For this example, let's say that our "heap" ends at 0x027FFFFF.

; program begins here
mov sp,#0x03000000
stmfd sp!,{r0-r12,lr}   ;push 56 bytes onto the stack.
stmfd sp!,{r0-r12,lr}   ;push 56 bytes onto the stack.
stmfd sp!,{r0-r12,lr}   ;push 56 bytes onto the stack.
...

Eventually if you keep doing this you'll start overwriting the memory in the heap with the pushed values, and this is what a stack overflow is. Given how huge the stack is on most modern hardware this is usually a result of assembly code where the author mismanaged the stack or a recursive function is called too many times. It's not likely you'll ever encounter this if your program consists entirely of non-recursive functions and you've made sure to "balance" the stack correctly.

puppydrum64
  • 1,598
  • 2
  • 15