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.

Human Memory Layers

Oddly enough, humans have layers of memory as well. The layers do not correspond directly to the layers in computer memory but there are 3 of them.

1. Sensory Store

The sensory store is the first layer of human memory and is a nearly perfect record of any and all sensory stimuli for about the last 30 seconds. Most notable in the research of sensory memory was Sperling, who used a T-Scope device to flash sets of images up for 1/2 second intervals, then test his subjects on their memory of them. It was through this procedure that it was found that while the sensory store does store items almost perfectly, recalling those stored stimuli is difficult for humans and on average we can only recall 3 1/2 images or objects from a set. If, however, the images are subdivided into sets and those sets given key phrases or sounds, a human can recall any of the sets, provided each set is under or around 4 objects.

2. Short Term Store

The short term store lasts for about 20 seconds and is an auditory store, meaning we store information their as sound, or talking to ourselves. Keeping an object in short term can be achieved by constant internal repetition, or rote rehearsal. Most notable in this work was a man named Miller, who found we can store 7 objects or concepts in short term store. Miller was a phone company employee and it is thus that up until recently phone numbers contained only 7 digits, the number we could remember long enough to jot down or dial.

A note before continuing: both sensory and short term store have time limits on them, and without processing the information and giving it some kind of meaning, after the memory is faded from sensory and short term stores it is gone forever.

3. Long Term Store

If we have taken in information we can transfer memory from either sensory or short term store to the long term store. Some interesting aspects of long term store are that all information there is stored semantically, or by meaning. Long term store has no known time limit and no known quantity, ergo we could store a limitless amount of information indefinitely if we could process all information into meaning. You may wonder why, if long term store is permanent, can we forget things we knew for a long time. The answer is that the memory persists, but the cues to recall it are gone. Much like finding a specific passage in a book, unless the place is marked, or has cues associated, finding the place in the book could be very difficult in even a small book, and next to impossible in an encyclopedic tome like the brain.

Summary

1. Sensory Store: 30 seconds of physical memory, recalling on average 3 1/2 items from a set.

2. Short Term Store: 20 seconds of auditory memory, recalling on average 7 items.

3. Long Term Store: Limitless time and quantity, but dependent on meaning and the ability to find the memory.

You might also look into the Method of Loci as a means of improving memory. Might be my next node, I dunno.