Hardware Stack
A common use of stacks at the
architecture level is as a means of allocating and accessing memory.
Basic architecture of a stack
A typical
stack, storing local data and call information for nested procedure calls (not
necessarily nested procedures!). This stack grows downward
from its origin. The stack pointer points to the current topmost datum on the stack. A
push operation decrements the pointer and copies the data to the stack; a pop
operation copies data from the stack and then increments the pointer. Each
procedure called in the program stores procedure return information (in yellow)
and local data (in other colors) by pushing them onto the stack. This type of
stack implementation is extremely common, but it is vulnerable to buffer
overflow attacks (see the text).
A typical stack is an area of computer
memory with a fixed origin and a variable size. Initially the size of the stack
is zero. A stack pointer, usually in the form of a hardware
register, points to the most recently referenced location on the stack; when
the stack has a size of zero, the stack pointer points to the origin of the
stack.
The two operations applicable to all
stacks are:
§
a push operation, in which a data item
is placed at the location pointed to by the stack pointer, and the address in
the stack pointer is adjusted by the size of the data item;
§
a pop or pull operation:
a data item at the current location pointed to by the stack pointer is removed,
and the stack pointer is adjusted by the size of the data item.
There are many variations on the basic
principle of stack operations. Every stack has a fixed location in memory at
which it begins. As data items are added to the stack, the stack pointer is
displaced to indicate the current extent of the stack, which expands away from
the origin.
Stack pointers may point to the origin
of a stack or to a limited range of addresses either above or below the origin
(depending on the direction in which the stack grows); however, the stack
pointer cannot cross the origin of the stack. In other words, if the origin of
the stack is at address 1000 and the stack grows downwards (towards addresses
999, 998, and so on), the stack pointer must never be incremented beyond 1000
(to 1001, 1002, etc.). If a pop operation on the stack causes the stack pointer
to move past the origin of the stack, a stack underflow occurs.
If a push operation causes the stack pointer to increment or decrement beyond
the maximum extent of the stack, a stack overflow occurs.
Some environments that rely heavily on
stacks may provide additional operations, for example:
§
Duplicate: the top item is popped, and then pushed again (twice),
so that an additional copy of the former top item is now on top, with the
original below it.
§
Peek: the topmost item is inspected (or returned), but the
stack pointer is not changed, and the stack size does not change (meaning that
the item remains on the stack). This is also called top operation
in many articles.
§
Swap or exchange: the two topmost items on
the stack exchange places.
§
Rotate (or Roll): the n topmost items
are moved on the stack in a rotating fashion. For example, if n=3,
items 1, 2, and 3 on the stack are moved to positions 2, 3, and 1 on the stack,
respectively. Many variants of this operation are possible, with the most
common being called left rotate and right rotate.
Stacks are either visualized growing
from the bottom up (like real-world stacks), or, with the top of the stack in a
fixed position (see image [note in the image, the top (28) is the stack
'bottom', since the stack 'top' is where items are pushed or popped from]), a
coin holder, a Pez dispenser,
or growing from left to right, so that "topmost" becomes
"rightmost". This visualization may be independent of the actual
structure of the stack in memory. This means that a right rotates will
move the first element to the third position, the second to the first and the
third to the second. Here are two equivalent visualizations of this process:
apple banana
banana ===right
rotate==> cucumber
cucumber apple
cucumber apple
banana ===left
rotate==> cucumber
apple banana
A stack is usually represented in
computers by a block of memory cells, with the "bottom" at a fixed location,
and the stack pointer holding the address of the current "top" cell
in the stack. The top and bottom terminology are used irrespective of whether
the stack actually grows towards lower memory addresses or towards higher
memory addresses.
Pushing an item on to the stack adjusts
the stack pointer by the size of the item (either decrementing or incrementing,
depending on the direction in which the stack grows in memory), pointing it to
the next cell, and copies the new top item to the stack area. Depending again
on the exact implementation, at the end of a push operation, the stack pointer
may point to the next unused location in the stack, or it may point to the
topmost item in the stack. If the stack points to the current topmost item, the
stack pointer will be updated before a new item is pushed onto the stack; if it
points to the next available location in the stack, it will be updated after the
new item is pushed onto the stack.
Popping the stack is simply the inverse
of pushing. The topmost item in the stack is removed and the stack pointer is
updated, in the opposite order of that used in the push operation.
Hardware support
Stack in main memory
Most CPUs have registers that can be used
as stack pointers. Processor families like the x86, Z80, 6502, and many others have
special instructions that implicitly use a dedicated (hardware) stack pointer
to conserve opcode space. Some processors, like thePDP-11 and
the 68000,
also have special addressing modes for implementation of stacks, typically with
a semi-dedicated stack pointer as well (such as A7 in the 68000). However, in
most processors, several different registers may be used as additional stack
pointers as needed (whether updated via addressing modes or via add/sub
instructions).
Stack in registers or dedicated memory
The x87 floating
point architecture is an example of a set of registers
organised as a stack where direct access to individual registers (relative the
current top) is also possible. As with stack-based machines in general, having
the top-of-stack as an implicit argument allows for a small machine code footprint
with a good usage of bus bandwidth and code caches,
but it also prevents some types of optimizations possible on processors permitting random access to
the register file for all (two or three)
operands. A stack structure also makes superscalar implementations
with register renaming (for speculative execution) somewhat more
complex to implement, although it is still feasible, as exemplified by modern x87 implementations.
Sun SPARC, AMD Am29000,
and Intel i960 are
all examples of architectures using register
windows within a register-stack as another strategy to avoid
the use of slow main memory for function arguments and return values.
There are also a number of small
microprocessors that implements a stack directly in hardware and some microcontrollers have
a fixed-depth stack that is not directly accessible. Examples are the PIC microcontrollers, the Computer Cowboys MuP21, the Harris RTX line, and
the Novix NC4016. Many stack-based microprocessors
were used to implement the programming language Forth at the microcode level.
Stacks were also used as a basis of a number of mainframes and mini computers.
Such machines were called stack machines, the most famous being the Burroughs B5000.
Notes
continue into the next blog:
Applications (Abstract Data Type (ADT))
J.W. PRODUCTION