memory management

the stack & the heap

hic 1
 memory management
So far:
data representations:
how are individual data elements represented in memory?

pointers and pointer arithmetic

to find out where data is allocated

Now:
memory management:
how is the memory as a whole organised and managed?

hic 2
 memory segments
high command line args
The OS allocates memory for each address
process - ie. a running program – stack
for data and code (grows downwards)

This memory consists of different segments

• stack - for local variables unused
– incl. command line arguments
and environment variables
heap
• heap - for dynamic memory
(grows upwards)
• data segment for
– global uninitialised variables (.bss) .bss
– global initialised variables (.data) .data
• code segment
code
typically read-only
low (read only)
address
hic 3
 memory segments
On Linux
> cat /proc/<pid>/maps
shows memory regions of process <pid>

With
> ps
you get a listing of all processes,
like the Taskbar in windows

(This is not exam material)

hic 4
 (Aside: real vs virtual memory)

Memory management depends on

high address command line args
capabilities of 0xFFFF
1. the hardware and stack
2. the operating system (OS) (grows downwards)

On primitive computers, which can only unused

run a single process and have no real
OS, the memory of the process may heap
simply be all the physical memory (grows upwards)
.bss
.data
Eg, for an old 64K computer
code
low address (read only)
0x0000
hic 5
 (Aside: primitive computers)

These may only run

a single process which
then gets to use all
of the memory

hic 6
 global variables (in .bss and .data)

These are the easy ones for the compiler to deal with.

#include <stdio.h>
long n = 12345;
char *string = "hello world\n";
int a[256];
...

Here
• the global variables n, string and the string literal ”hello world\n”,
will be allocated in data
• The uninitialised global array a will be allocated in .bss
The segment .bss is initialised to all zeroes. NB this is a rare case where C
will do a default initialisation for the programmer!

hic 7
 the stack

hic 8
 stack, pop, push
A stack (in Dutch: stapel) organises a set of elements
in a Last In, First Out (LIFO) manner

The three basic operations on a stack are

• pushing a new element on the stack
• popping an element from the stack
• checking if the stack is empty

hic 9
 the stack
The stack consists of stack frames aka
stack frame
activation records, one for each function call,
for main()
• allocated when a function is called,
• de-allocated when it returns.

main(int i){
char *msg =”hello”;
f(msg); stack frame
for f()
}

int f(char *p){

int j;
..;
return 5; unused
} memory

hic 10
 the stack
On most machines, the stack grows downward
stack frame
for main()
The stack pointer (SP) points to the last element
on the stack

On x86 architectures, the stack pointer is stored

in the ESP (Extended Stack Pointer) register stack frame
for f()

stack pointer
(ESP)
unused
memory

hic 11
 the stack
Each stack frame provides memory for
previous stack
• arguments frame
• the return value
• local variables return value
of a function, plus some admin stuff .
arguments

frame pointer admin stuff

The frame pointer provides a
(EBP)
starting point to locate the local local variables
variables, using offsets. stack pointer
On x86 architectures, it is stored in the (ESP)
EBP (Extended Base Pointer) register unused
memory

hic 12
 the stack
The admin stuff stored on the stack :
previous stack
• return address frame
ie where to resume execution after return
• previous frame pointer return value
to locate previous frame
arguments

return address
frame pointer saved frame pointer
(EBP)
local variables
stack pointer
(ESP)
unused
memory

hic 13
 the stack
stack
Stack during call to f int i frame
for
main(int i){ main
char *msg =”hello”; char *msg
f(msg);
} int return value
char *p stack
return address frame
int f(char *p){ for
saved frame pointer
int j; frame pointer f(msg)
int j
..; stack pointer
return 5;
} unused
memory

hic 14
 function calls
• When a function is called, a new stack frame is created
– arguments are stored on the stack
– current frame pointer and return address are recorded
– memory for local variables is allocated
– stack pointer is adjusted

• When a function returns, the top stack frame is removed

– old frame pointer and return address are restored
– stack pointer is adjusted
– the caller can find the return value, if there is one, on top of the stack

• Because of recursion, there may be multiple frames for the same

function on the stack
• Note that the variables that are stored in the current stack frame are
precisely the variables that are in scope

hic 15
 security worries
• There is no default initialisation for stack variables
– by reading unitialised local variables,
you can read memory content used in earlier function calls

• There is only finite stack space

– a function call may fail because there is no more memory
In highly safety- or security-critical code, you may want to ensure that
this cannot happen, or handle it in a safe way when it does.

• The stack mixes program data and control data

– by overrunning buffers on the stack we can corrupt the return
addresses!
More on that the next weeks!

hic 16
 (Aside: hardware-specific details)

• The precise organisation of the stack depends on the machine

architecture of the CPU

• Instead of storing data on the stack (in RAM)

some data may be stored in a register (in the CPU)

Eg, for efficiency, the top values of the stack may be stored in CPU
registers, or in the CPU cache, or the return value could be stored in a
register instead of on the stack.

hic 17
 Example security problem
caused by bad memory management

hic 18
http://embeddedgurus.com/state-space/2014/02/are-we-shooting-ourselves-in-the-foot-with-stack-overflow/
sws1 19
sws1 20
sws1 21