University
of
Washington
Roadmap
Memory
&
data
Integers
&
floats
Machine
code
&
C
C:
Java:
x86
assembly
car *c = malloc(sizeof(car)); Car c = new Car(); Procedures
&
stacks
c->miles = 100; [Link](100); Arrays
&
structs
c->gals = 17; [Link](17);
float mpg = get_mpg(c); float mpg =
Memory
&
caches
free(c); [Link](); Processes
Virtual
memory
Assembly
get_mpg: Memory
alloca@on
language:
pushq %rbp Java
vs.
C
movq %rsp, %rbp
...
popq %rbp
ret
OS:
Machine
0111010000011000
100011010000010000000010
code:
1000100111000010
110000011111101000011111
Computer
system:
Memory
Alloca@on
University
of
Washington
Sec@on
10:
Memory
Alloca@on
Topics
¢ Dynamic
memory
alloca@on
§ Size/number
of
data
structures
may
only
be
known
at
run
7me
§ Need
to
allocate
space
on
the
heap
§ Need
to
de-‐allocate
(free)
unused
memory
so
it
can
be
re-‐allocated
¢ Implementa@on
§ Implicit
free
lists
§ Explicit
free
lists
–
subject
of
next
programming
assignment
§ Segregated
free
lists
¢ Garbage
collec@on
¢ Common
memory-‐related
bugs
in
C
programs
Memory
Alloca@on
University
of
Washington
Dynamic
Memory
Alloca@on
¢ Programmers
use
Applica@on
dynamic
memory
Dynamic
Memory
Allocator
allocators
(such
as
Heap
malloc)
to
acquire
memory
at
run
@me.
§ For
data
structures
whose
User
stack
size
is
only
known
at
run7me.
Top
of
heap
¢ Dynamic
memory
(brk ptr)
Heap
(via
malloc)
allocators
manage
an
area
of
process
virtual
Unini@alized
data
(.bss)
memory
known
as
the
Ini@alized
data
(.data)
heap.
Program
text
(.text)
0
Memory
Alloca@on
University
of
Washington
Dynamic
Memory
Alloca@on
¢ Allocator
maintains
heap
as
collec@on
of
variable
sized
blocks,
which
are
either
allocated
or
free
§ Allocator
requests
space
in
heap
region;
VM
hardware
and
kernel
allocate
these
pages
to
the
process
§ Applica7on
objects
are
typically
smaller
than
pages,
so
the
allocator
manages
blocks
within
pages
¢ Types
of
allocators
§ Explicit
allocator:
applica7on
allocates
and
frees
space
§E.g.
malloc
and
free
in
C
§ Implicit
allocator:
applica7on
allocates,
but
does
not
free
space
§ E.g.
garbage
collec7on
in
Java,
ML,
and
Lisp
Memory
Alloca@on
University
of
Washington
The
malloc
Package
#include <stdlib.h>
void *malloc(size_t size)
§ Successful:
§ Returns
a
pointer
to
a
memory
block
of
at
least
size
bytes
(typically)
aligned
to
8-‐byte
boundary
§ If
size == 0,
returns
NULL
§ Unsuccessful:
returns
NULL
and
sets
errno
void free(void *p)
§ Returns
the
block
pointed
at
by
p
to
pool
of
available
memory
§ p
must
come
from
a
previous
call
to
malloc or
realloc
Other
func@ons
§ calloc:
Version
of
malloc
that
ini7alizes
allocated
block
to
zero.
§ realloc:
Changes
the
size
of
a
previously
allocated
block.
§ sbrk:
Used
internally
by
allocators
to
grow
or
shrink
the
heap.
Memory
Alloca@on
University
of
Washington
Malloc
Example
void foo(int n, int m) {
int i, *p;
/* allocate a block of n ints */
p = (int *)malloc(n * sizeof(int));
if (p == NULL) {
perror("malloc");
exit(0);
}
for (i=0; i<n; i++) p[i] = i;
/* add space for m ints to end of p block */
if ((p = (int *)realloc(p, (n+m) * sizeof(int))) == NULL) {
perror("realloc");
exit(0);
}
for (i=n; i < n+m; i++) p[i] = i;
/* print new array */
for (i=0; i<n+m; i++)
printf("%d\n", p[i]);
free(p); /* return p to available memory pool */
}
Memory
Alloca@on
