Memory Organisation and Procedure Call Protocol

12th February 2010

These are lecture notes from my Computer Science course, not a general reference for "Memory Organisation and Procedure Call Protocol"

Generally RAM is split up into (in order):

Code
Static Data
Stack
Free Space
Heap

And code memory is usually split up into code for procedures, with entry points at the bottom (lowest address) for each procedure.

Storage can be allocated statically for global variables, static variables of functions, and constants and literals that are not stored directly in the code (e.g. “Hello World” in a printf statement). Fixed address = efficient access.

When we refer to ‘Procedures’ we’re talking about methods, functions, subroutines, whatever. It’s fairly obvious (from previous modules) how running procedures pushes the PC onto the stack, and returning from them pops the last item off that stack.

However, procedures also have arguments and local variables, so we push more than just the PC; push a stack frame also known as an activation record onto the stack.

A typical stack frame contains:

Frame pointer which points to the middle (?) of the current frame on the stack.
All frame components (variables for example) accessed by a fixed offset from the FP.
Sometimes you may have a global stack pointer (ST) which points to the top of the stack.
A dynamic link points to the preceding frame on the stack (the old value of FP), often used because the frame size is only known late in compiler phases.

Passing arguments

Pretty obvious, there are 2 ways of passing arguments:

Pass by value (this is how C works): argument is evaluated by caller and value passed to callee.
Pass by reference: Imagine Ada, basically.

Accessing enclosing procedure’s variables

Two possible methods:

Use a static link which is a pointer to frame of inner procedure
Use a global display; an array of frame pointers.

There’s also a couple of issues with these involving passing procedures around, see the slides for detail as it’s a bit confusing.

Registers

Registers are fast.
You have global registers, caller-save and callee-save registers.
Procedure results are returned in a register.
Procedure arguments are stored in registers (the first 4-6 generally).
Callers store return addresses in registers.
Registers may be ‘spilled’ into a frame, but many procedures do not call other procedures and register values may only be needed before the first procedure call.

Heap

The heap is for data where you don’t know how much, or how big it will be. It’s also useful for data where the lifetime will be shorter than the whole run-time.

It is allocated explicitly via an allocator (e.g. malloc) or implicitly. It is deallocated explicitly via a deallocator (e.g. free) or implicitly through garbage collection.

At run time the heap expands and (occasionally) contracts. Deallocation usually leaves a gap which can cause fragmentation, a run-time module called a heap manager maintains a list of these gaps so that when something wants to allocate in the heap, the heap manager can pick a good spot for it to minimise fragmentation. However over time as a result you will get very small gaps that are useless; garbage collection will help with this.