A Study on Stack
As this subject charmed me, I wanted to be in depth understanding of what is this stack stuff and how it works.
The major part of the collected material was from wikipedia, the Guide to Assembly Programming in Linux, and the #asm channel in Freenode.net.
I hope you enjoy the tour ;)
So what is a Stack?
Conceptually, a stack is a last-in-first-out (LIFO) data structure1. The operation of a stack is analogous to the stack of trays you find in cafeterias. The first tray removed from the stack of trays would be the last tray that had been placed on the stack. There are two operations associated with a stack: insertion and deletion. If we view the stack as a linear array of elements, stack insertion and deletion operation are restricted to one end of the array. Thus, the only elements that is directly accessible is the element at the top-of-stack (TOS). In stack terminology, insert and delete operation are referred to as push and pop operations, respectively.
Lets assume that we are inserting number 10, 11, 12, 13 into a stack in ascending order. The state of the stack can be visualized below. The arrow points to the top-of-stack. When the numbers are deleted from the stack, the numbers will come out in the reverse order of insertion. That is, 13 is removed first, and so on. After the deletion of the last number, the stack is said to be in the empty state.
The deletion of data items from the stack, would be like this:
Implementation of the Stack
The memory space reserved in the stack segment is used to implement the stack. The register SS and ESP are used to implement the stack. The top-of-stack, which points to the last item inserted into the stack, is indicated by SS:ESP.
The key stack implementation characteristics are as follows:
Only words (16-bit data) or doublewords (32-bit data) are saved on the stack, never a single byte.
The stack grows toward lower memory addresses. Since we graphically represent memory with addresses increasing from the bottom of a page to the top, we say that the stack grows downward.
Top-of-stack (TOS) always points to the last data item placed on the stack. The TOS always points to the lower byte of the last word pushed onto the stack. For example, when we push 0xab78 onto the stack, the TOS points to 0x78 byte.
When a word is pushed onto the stack, ESP is first decremented by two, and then the word is stores at SS:ESP. Since the IA-32 processors use the little-endian2 byte order, the higher-order byte is stored in the higher memory address. For instance, when we push 0xab78, the stack expands by two bytes and ESP is decremented by two to point to the last data item.
The stack full condition is indicated by the zero offset value (ESP=0). If we try to insert a data item into a full stack, stack overflow occurs.
Retrieving a 32-bit data item from the stack causes the offset value to increase by four to point to the next data item on the stack.
Stack Operations
Basic Instructions
The stack data structure allows two basic operations: insertion of a data item into the stack (called the push operation) and deletion (called the pop operation). These two operations are allowed on word or doubleword data items. The syntax is:
push source
pop destination
The operand of these two instructions can be a 16- or 32-bit general purpose register, segment register, or a word or doubleword in memory. In addition, source for the push instruction can be an immediate operand of size 8,16 or 32 bits.
On an empty stack , the statements:
push 45b1H
push ab21cc45H
would result in the stack growing down 6 bytes and the ESP pointing to the last byte of the hex number ab21cc45H, that is 45.
Now, if we execute:
pop EBX
on this stack, would result in the EBX register taking the value ab21cc45.
Additional Instructions
Stack Operations on Flags
The push and pop operations cannot be used to save or restore the flags register. For this, two special versions of these instructions are provided:
pushfd (push 32-bit flags)
popfd (pop 32-bit flags)
These instructions do not need any operands. For operating on the 16-bit flags register (FLAGS), we can use pushfw and popfw instructions. If we use pushf the default operand size selects either pushfd or pushfw. In our programs, since our default is 32-bit operands, pushf is used as an alias for pushfd. However, e use pushfd to make the operand size explicit. Similarly, popf can be used as an alias for either popfd or popfw.
Stack Operations on All General-Purpose Registers
The instruction set also has special pusha and popa instructions to save and restore the eight general-purpose registers EAX, ECX, EDX, EBX, ESP, EBP, ESI, and EDI. These registers are pushed in the order specified.
Uses of the Stack
The stack is used for three main purposes: a scratchpad to temporarily store data, for transfer program control, and for passing parameters during a procedure call.
Temporary Storage of Data
The stack can be used to store data on a temporary basis. For example, consider exchanging the contents of two 32-bit variables that are in the memory: value1 and value2.
We cannot use:
xchg value1, value2
because both operands of xchg are in the memory. The code
mov EAX, value1
mov EBC, value2
mov value1, EBX
mov value2, EAX
works, but it uses two 32-bit registers. The code requires four memory operations. However, due to the limited number of general-purpose registers, finding spare registers that can be used for temporary storage is nearly impossible in almost all programs.
What if we need to preserve the contents of the EAX and EBX registers? In this case, we need to save these registers before using them and restore them later as shown below:
;save EAX and EBX registers on the stack
push EAX
push EBX
;EAX and EBX register can now be used
mov EAX, value1
mov EBX, value2
mov value1, EBX
mov value2, EAX
;restore EAX and EBX registers from the stack
pop EBX
pop EAX
This code requires eight memory accesses. Because the stack is a LIFO data structure, the sequence of pop instructions is a mirror image of the push instruction sequence.
An elegant way of exchanging the two values is:
push value1
push value2
pop value1
pop value2
Notice that the above code does not use any general-purpose registers and requires eight memory operations as in the other example. Another point to note is that push and pop instructions allow movement of data from memory to memory (between data and stack segments, for example). This is a special case because mov instructions do not allow memory-to-memory data transfer.
Stack is frequently used as a scratchpad to save and restore registers. The necessity often arises when we need to free up a set of register so they can be used by the current code. This is often the case with procedures.
It should be clear from these examples that the stack grows and shrinks during the course of a program execution. It is important to allocate enough storage space for the stack, as stack overflow and underflow could cause unpredictable results, often causing system errors.
Transfer of Control
The previous discussion concentrated on how we, as programmers, can use the stack to store data temporarily. The stack is also used by some instructions to store data temporarily. In particular, when a procedure is called, the return address of the instruction is stored on the stack so that the control can be transferred back to the calling program.
Parameter Passing
Another important use of the stack is to act as a medium to pass parameters to the called procedure.
Procedure Instructions
To call a procedure, we use the following statement:
call proc-name
The assembler replaces proc-name by the offset value of the first instruction of the called procedure.
How Is Program Control Transferred?
The offset provided in the call instruction is not the absolute value (i.e., offset is not relative to the start of the code segment pointed to by the CS register), but a relative displacement in bytes from the instruction following the call instruction.
The EIP register points to the next instruction to be executed. This instruction should be executed after returning from this procedure. The processor makes a note of this by pushing the contents of the EIP register onto the stack.
The following is a summary of the actions taken during a procedure call:
ESP = ESP – 4 ;push return address onto the stack
SS:ESP = EIP
EIP = EIP + relative displacement ;update EIP to point to the procedure
The ret Instruction
The ret (return) instruction is used to transfer control from the called procedure to the calling procedure. How will the processor know where this instruction is loaded??
Remember that the processor made a note of this when the call instruction was execute. When the ret instruction is executed, the return address from the stack is recovered.
So:
EIP = SS:ESP ;pop return address at TOS into IP
ESP = ESP + 4 ;update TOS by adding 4 to ESP
Parameter Passing
In the assembly language, the calling procedure first places all the parameters needed by the called procedure in a mutually accessible storage area (usually registers or memory). Only then can the procedure be invoked. There are two common methods depending on the type of storage area used to pass parameters: register method or stack method.
Register Method
The advantages are:
The register method is convenient and easier for passing a small number of arguments.
This method is also aster because all the arguments are available in registers.
Disadvantages:
There is a limited number of general-purpose registers in the CPU.
Thus, is necessary to temporarily save the contents of these registers on the stack to free them for use in parameter passing before calling a procedure, and restore them after retuning from the called procedure.
Stack Method
In this method of parameter passing, all arguments required by a procedure are pushed onto the stack before the procedure is called. As an example, let us consider passing the two parameters required by a procedure. This can be done by:
push number1
push number2
call procedure
After executing the call instruction, which automatically pushes the EIP contents onto the stack the stack state is show in the figure below:
Reading the two arguments – number1 and number2 – is tricky. Since the parameter values are buried inside the stack, first we have to pop the EIP value to read the two arguments. This, for example can be done by
pop EAX ;EIP
pop EBX ;number1
pop ECX ;number2
in the called procedure. Since we have removed the return address (EIP) from the stack, we will have to restore it by
push EAX
so that TOS is pointing to the return address.
The main problem with this code is that we need to set aside general-purpose registers to copy parameter values. This means that the calling procedure cannot use these registers for any other purpose. Worse still, what if you want to pass 10 parameters? One way to free up registers is to copy the parameters from the stack to local data variables, but this is impractical and inefficient.
The best way to get parameter values is to leave them on the stack and read them from the stack as needed. Since the stack is a sequence of memory locations, ESP + 4, points to number2, and ESP + 8 to number1. For instance:
mov EBX, [ESP+4]
can be used to access number2, but this causes a problem. The stack pointer is updated by the push and pop instructions. As a result, the relative offset changes with the stack operations performed in the called procedure. This is not a desirable situation.
There is a better alternative: we can use the EBP registers instead of ESP to specify an offset into the stack segment. For example, we can copy the value of number2 into the EAX register by:
mov EBP,ESP
mov EAX,[EBP+4]
This is the usual way of pointing to the parameters on the stack. Since every procedure uses the EBP register to access parameters, the EBP register should be preserved. Therefore, we should save the contents of the EBP register before executing the
mov EBP,ESP
statement. We, of course, use the stack for this. Note that
push EBP
mov EBP,ESP
causes the parameter displacement to increase by four bytes (the size of EBP).
The information stored in the stack – parameters, return address, and the old EBP value – is collectively called the stack frame.
So before returning from the procedure, we should use
pop EBP
to restore the original value of EBP.
Now the problem is that the four bytes of the stack occupied by the two arguments are no longer useful. One way to free these four bytes is to increment ESP by four after the call statement, as shown below:
push number1
push number2
call procedure
add ESP,4
For example, C compilers use this method to clear parameters from the stack. The above assembly language code segment corresponds to the
procedure(number2, number1);
function call in C.
Rather than adjusting the stack by the calling procedure, the called procedure can also clear the stack. Note that we cannot write
procedure:
add ESP,4
ret
because when ret is executed, ESP should point to the return address on the stack. Te solution lies in the optional operand that can be specified in the ret statement. The format is:
ret optional-value
which results in the following sequence of actions:
EIP = SS:ESP
ESP = ESP + 4 + optional-value
The optional-value should be a number. Since the purpose of the optional value is to discard the parameters pushed onto the stack, this operand takes a positive value.
Preserving Calling Procedure State
It is important to preserve the contents of the registers across a procedure call. The necessity for this is illustrated by the following code:
mov ECX, count
repeat:
call compute
… …
… …
loop repeat
The code invokes the compute procedure count times. The ECX register maintains the number of remaining iterations. Recall that, as part of the loop instruction execution, the ECX register is decremented by 1 and, if not 0, starts another iteration.
Suppose, now, that the compute procedure uses the ECX register during its computation.
Then, when compute returns control to the calling program, ECX would have changed, and the program logic would be incorrect.
Since there are a limited number of registers and registers should be used for writing efficient code, registers should be preserved. The stack is used to save registers temporarily.
Which registers should be save?
The answer to this question is simple: Save those registers that are used by the calling procedure but changed by the called procedure. This leads to the following question; Which procedure, the calling or the called should save the registers?
We assume that the called procedure saves the registers that it uses and restores them before returning to the calling procedure. This also conforms to the modular program design principles.
ENTER and LEAVE instructions
The instruction set has two instruction to facilitate stack frame allocation and release on procedure entry and exit. The enter instruction can be used to allocate a stack frame on entering a procedure. The format is:
enter bytes, level
The first operand bytes specifies the number of bytes of local variable storage we want on the new stack frame. The statement:
enter XX,0
is equivalent to:
push EBP
mov EBP, ESP
sub ESP, XX
The leave instruction releases the stack frame allocated by the enter instruction. It does not take any operands. The leave instruction effectively performs the following:
mov ESP, EBP
pop EBP
We use leave instruction before the ret instruction as shown in the following template for procedures:
proc-name:
enter XX,0
. . .
procedure-body
. . .
leave
ret YY
The XX value is nonzero only if our procedure needs some local variable space on the stack frame. The value YY is used to clear the arguments passed on to the procedure.
1http://en.wikipedia.org/wiki/LIFO_%28computing%29
2http://en.wikipedia.org/wiki/Endianness#Little-endian
Labels: assembler, assembly, assembly programming, linux, overflow, programming, security, stack, underflow
posted by Eduardo O Barruzi at 12:01
109 comments
