Before executing a program, the
OS allocates enough memory, copies the
code and
initialized data
to memory and creates a
stack. Memory available to a program can be roughly divided in four
layers : the
code, the
heap,
the
stack and the
available memory.
- The code part contains the instructions to be executed.
- The heap lies at the bottom of the available memory and is managed by software routines.
When a program wants to dynamically allocate memory, it calls complex functions (typically malloc() and free())
that find a free block of memory in the heap and return a pointer to it.
-
The stack lies at the top of the memory and occupies memory from SP (stack pointer) to the end of the segment.
When an entry is added to the stack
(this operation is called PUSH),
it is copied at location SP and SP is decremented. When an entry is removed
(this operation is called POP),
SP is incremented and the value is read at location SP.
Throughout the program's execution, the stack limit and the heap limit vary. If they overlap,
data is overwritten and results in an unexpected
behaviour called
stack overflow. This can be illustrated by the following diagram :
+--------+ +--------+ +--------+
| STACK | | STACK | | |
+--------+ EXECUTION | | STACK OVERFLOW | STACK |
| | +--------+ | |
| | stack and heap | | crash : they +XXXXXXXX+
| | grow due to +--------+ overlap | |
| | memory needs | | | HEAP |
+--------+ | HEAP | | |
| HEAP | ------------> | | ------------> | |
+--------+ +--------+ +--------+
| CODE | | CODE | | CODE |
+--------+ +--------+ +--------+
Memory addresses increase upwards
On modern OSes, the stack generally lies at the end of the virtual address space
and the heap is located at the other end. The virtual address space
is typically over 2Gb therefore stack/heap collisions are not likely to happen.
But will still cause an error because the computer runs out of memory.
See malloc bomb.
Allocation methods
There are three different allocation methods : static allocation, heap allocation (also called dynamic allocation) and stack allocation.
Static allocation
Static allocation is the memory allocation method
used when you declare
global or
static variables in your program.
A global variable in C language is defined outside a function body and is available to all functions of the file. It can be exported to other files. A static variable is a variable declared with the static type modifier that keeps its value between function calls. Its scope is limited to the function body.
When a static/global variable is declared, the compiler and the linker
reserve a fixed place at the beginning of the data segment.
For example, when the C language compiler encounters
int a=4;
outside a
function body, it typically generates the following
assembler op code
DD _a 0x0004
which instructs the linker to reserve 4
bytes of memory, initialize it
with the integer value 4 and call it _a.
Static variables are directly referred to by their constant
offset in the data segment.
When creating the
executable, the linker replaces every reference to _a by the
corresponding constant
memory location. For example, if the linker has reserved
the bytes 0x24 to 0x27 for the variable _a, then
MOV AX, _a
becomes
MOV AX, [0x24]
The drawback of this method is that it can't be used at run time to allocate memory.
But it is faster than using pointers because the memory location is known directly.
Heap allocation
Heap allocation is also called
dynamic allocation and is the
memory allocation method
used when you call
malloc() related
functions at
run time.
Roughly speaking, the heap
is only a big memory block allocated by the operating system's kernel. It is up to the application
to deal with it. Fortunately compilers come with a Run Time Library RTL that include memory management
functions. In C language, the main ones are called malloc() and free().
Implementation details is left to the Run Time Library developers. But usually the heap is divided in
little blocks. A little malloc descriptor is prefixed
to the block indicating if it is used or not and what length it has. Two consecutive free blocks are merged.
Generally blocks are aligned on paragraphs (16 or 32 bytes). If the alignment is 16 bytes, whether you ask for a 1 byte, 2 byte... 15 byte
or 16 block, a 16 byte block is allocated.
Malloc bugs appear when a program writes outside of an allocated block and overwrites a malloc descriptor.
On subsequent calls the memory functions read wrong values and the program has an unexpected behaviour that
can result in a system crash. Malloc bugs are VERY difficult to debug as the system crashes everywhere except
where data is being overwritten. Malloc bugs are also called fandango on core.
Stack allocation
Stack allocation is the memory allocation method
used when you
declare a
variable in a
function body.
When a function is called,
it pushes the return address on the stack and saves the stack pointer in a register (usually in register BP).
Then it moves the stack pointer to reserve enough memory for the variables. These variables are referred to
with the SS:BP-n indirection, where n is constant.
The following diagram illustrates this :
| | | |
| | |==============| <- new stack
| | n=2 | local | pointer
| | n=1 | variables |
| | +--------------+ <- BP
| | | return addr. |
+==============+ <- stack function +--------------+
| XXXXXXXXXXXX | pointer call | XXXXXXXXXXXX |
| XXXXXXXXXXXX | -----> | XXXXXXXXXXXX |
Addresses decrease upwards
When the function has to return, it gives back its previous value to the stack pointer
(SP=BP) and issues a RET instruction which pops the return address
from the stack and jumps back to this location. In fact function calls are more complex.
The memory marked with X's is usually filled up with
the function's arguments. But these arguments are pushed and popped from the stack by the caller
function.
The memory used by a function on the stack is called
the stack space. Each function call has its own stack space. This permits recursive programming.
But keep in mind that each recursive call will expand the stack size. It is a good programing habit
to keep the stack space as small as possible. Some golden rules
are : do not allocate big objects (such as tables and large
structures) on the stack, do not pass large objects (such as structures) as arguments
since they are copied on the stack (try
as much as possible to pass pointers), and try to use inline functions (they do not
generate a function call).
Overflows do not always result in an 'unexpected behaviour'. Overflows of buffers stored on the stack is the basis of most exploits. With this method, people can sometimes execute
given code on remote machines to get administrative privileges.
Conclusion
Here is a brief summary of the three different allocation methods :
Static allocation
The memory has a fixed size defined at compile time. It is globally available to all functions.
It can be initialized with a given value. It is placed at the beginning of the heap. Static allocation is handled by the compiler.
Heap allocation
Memory allocated/freed at run time with malloc() and free() functions. The size of the requested memory
block is arbitrary. Memory allocated will contain random values.
Stack allocation
The memory is allocated each time the function is called and freed when the function exits.
It can be initialized with a given value. It permits recursive programming.