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.