Carnegie Mellon

Dynamic Memory Allocation:

Basic Concepts

15-213/18-213/15-513: Introduction to Computer

Systems 13th Lecture, October 12, 2021
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 1
Carnegie Mellon

Announcements
⬛ No lecture on Thursday October 14

⬛ Malloclab out today

▪ Checkpoint due on Tuesday October 26 (+ up to 2 grace days) ▪ Final
submission due on Tuesday November 2 (+ up to 2 grace days)
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 2
Carnegie Mellon

Today
⬛Basic concepts ⬛
Implicit free lists
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 3
Carnegie Mellon Memory

Dynamic Memory
Allocation
Application
Dynamic Memory Allocator
Heap

⬛Programmers use dynamic memory allocators (such as

malloc) to acquire virtual memory (VM) at runtime
▪ For data structures whose size is only known at runtime
⬛Dynamic memory allocators manage an area of process
VM known as the heap

ion for shared libraries

(.init, .text, .rodata) Unused

invisible to user code

%rsp
(stack
pointer)
 brk

Loaded
from
the
executable file

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 4

Carnegie Mellon

Dynamic Memory Allocation

▪ Explicit allocator: application allocates and frees space ▪
e.g., malloc and free in C
⬛ Will discuss simple explicit memory allocation today

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 5

Carnegie Mellon

▪ calloc: Version of malloc that initializes allocated block to zero

▪ realloc: Changes the size of a previously allocated block ▪
sbrk: Used internally by allocators to grow or shrink the heap
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 6
Carnegie Mellon

malloc Example
#include <stdio.h>
#include <stdlib.h>
void foo(long n) {
long i, *p;

ed
Free block

(2 words)
Free word Allocated word

Allocated block (4 words)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9

Carnegie Mellon

#define SIZ sizeof(size_t)

 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10
Carnegie Mellon

ocated blocks in free memory ▪ Must align blocks so they

 satisfy all alignment requirements ▪ 16-byte (x86-64)
▪ Bias toward allocate at beginning &
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14
Carnegie Mellon

Benchmark Visualization
11 a 7 33856 33856 90036 90036

12 f 1 -50084 39952 90036

Step Command Delta Allocated Peak 13 a 8 136 136 40088 90036

1 a 0 9904 9904 9904 9904 14 f 7 -33856 6232 90036
2 a 1 50084 50084 59988 59988 15 f 6 -2012 4220 90036
3 a 2 20 20 60008 60008 16 a 9 20 20 4240 90036
4 a 3 16784 16784 76792 76792 17 f 4 -840 3400 90036
5 f 3 -16784 60008 76792 18 f 8 -136 3264 90036
6 a 4 840 840 60848 76792 19 f 5 -3244 20 90036
7 a 5 3244 3244 64092 76792 20 f 9 -20 0 90036
8 f 0 -9904 54188 76792

9 a 6 2012 2012 56200 76792 1

10 f 2 -20 56180 76792

Normalized Aggregate Memory

0.8

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Step

0.6 Allocated Peak1.2

1.0

Memory Used / Peak Data

0.8
0.6
0.4
0.2
0.4

0.2

Data Fit
DAllocated ata Peak
0

0.0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Operation / Operation Count

⬛ Longer sequence of mallocs & frees (40,000 blocks)

▪ Starts with all mallocs, and shifts toward all frees
⬛ Allocator must manage space efficiently the whole time
 ⬛ Production allocators can shrink the heap
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 16
Carnegie Mellon

ayload Internal fragmentation

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 18
Carnegie Mellon

Internal
Fragmentation
Perfect Fit
Data Fit
DAllocated ata

Effect 1.4
Peak + Internal FragPeak

1.2
1.0 free(p2)
Memory Used / Peak Data
0.8
0.6
0.4
0.2 p4 = malloc(7*SIZ)
Yikes! (what would
happen now?)
 t
⬛
e
D
r
e
n
p
o
e
f
n
f
d
u
s
t
o
u
n
r
t
e
h
r
e
e
p
q
a
u
t
e
 s u
t s
,
s d
▪ i
T
h

Size
a

Format of

16/0 32/1 64/0 32/1

 Block 8/1

End

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 30

Carnegie Mellon

Implicit List: Finding a Free Block

⬛ First fit:
▪ Search list from beginning, choose first free block that fits:
▪ Finding space for asize bytes (including header):
static block_t *find_fit(size_t asize)
{
block_t *block;
for (block = heap_start; block != heap_end;
block = find_next(block)) {
{
if (!(get_alloc(block))
&& (asize <= get_size(block)))
return block;
}
return NULL; // No fit found
}

heap_start heap_end16/0 32/1 64/0 32/1 8/1

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 31

Carnegie Mellon

Implicit List: Finding a Free

 ▪ Still a greedy algorithm. No guarantee of optimality

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 32

Carnegie Mellon

▪ First Fit: 11.9%

▪ Next Fit: 21.6%
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 33
Carnegie Mellon

Implicit List: Allocating in Free Block

⬛ Allocating in a free block: splitting
▪ Since allocated space might be smaller than free space, we might want
to split the block

32 32 48 16
8
 p

split_block(p, 32)

32 16
32 32 16
8

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 34

Carnegie Mellon

Implicit List: Splitting Free

 Block split_block(p, 32)
64 p 16 32 32 16

// Warning: This code is incomplete

static void split_block(block_t *block, size_t asize){

size_t block_size = get_size(block);

if ((block_size - asize) >= min_block_size) {

write_header(block, asize, true);
block_t *block_next = find_next(block);
write_header(block_next, block_size - asize, false);
} Carnegie Mellon

Implicit List: Coalescing

⬛ Join (coalesce) with next/previous blocks, if they are free
▪ Coalescing with next block
 32 32 16 16 8

32 logically
free(p) p

Bryant and O’Hallaron, Computer Systems: A Programmer’s

Perspective, Third Edition 40
Carnegie Mellon

Im
[Link]
/courses/24383/quizzes pl
/67237
e
m it
e h
n F
t o
a o
ti t
o e
n rs
hea
w der
 pay
loa ⬛Locating footer of
d current block
unu const size_t dsize =
2*sizeof(word_t);
sed
foo st
at
ter ic
hea wo
rd
der _t
pay *h
ea
loa de
d r_
to
asize _f
asize oo
d te
s r(
bl
i
oc
z k_
e t
*b
 lo
ck pl
)
{
size_t asize = e
get_size(block);
return
(word_t *) m
(block->pa
yload +
asize -
dsize); }
e
n
t
Bryant and O’Hallaron, Computer Systems: A Programmer’s
Perspective, Third Edition 41
Carnegie Mellon
a

Im ti
o
n rs
hea
w der
pay
it loa
d
h unu
sed
F foo
ter
o hea
der
o pay
loa
t d

e 1
 k_
t
*b
lo
ck
)
{
⬛Locating footer of return
previous block &(block->header) -
1;
st }
at
ic
wo
rd
_t
*f
in
d_
pr
Bryant and O’Hallaron, Computer Systems: A Programmer’s
ev Perspective, Third Edition 42
_f Carnegie Mellon
oo
te lit_block
r( (bloc
bl k_t
oc *bloc
k, z
size_ e
t -
asize a
){ s
size_ i
t z
block e
_size )
= >
get_s =
ize(b m
lock) i
; n
_
i b
f l
( o
( c
b k
l _
o s
c i
k z
_ e
s )
i {
w u
r e
i )
t ;
e write_footer(blo
_ ck, asize,
h true);
e block_t
a *block_next =
d find_next(block)
e ;
r write_h
( eader(block_nex
b t, block_size -
l asize, false);
o write_footer(bl
c ock_next,
k block_size -
, asize, false);
a }
s
i
z
e
Bryant and O’Hallaron, Computer Systems: A Programmer’s
, Perspective, Third Edition 43
t Carnegie Mellon
r
 Case 4

Constant Time
Coalescing

Case 1 Case 2 Case 3

Allocated Allocated Free Free Free

Block being Allocated

Allocated Free
freed
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 44
Carnegie Mellon er’s Perspective, Third Edition 45
Carnegie Mellon

Constant Time Coalescing (Case 2)

m2 0
m1 1
m1 1
m1 1 n+m2
m1 1 n 1 0

n 1 m2 0
 n+m2 0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 46

Carnegie Mellon

Constant Time Coalescing (Case 3)

n 1 m2 1

m1 0
m2 1
n+m1 0
m1 0 n 1
 m2 1

n+m1 0 m2 1

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 47

Carnegie Mellon

Constant Time Coalescing (Case 4)

n 1 m2 0

m1 0
m2 0

m1 0 n 1
 n+m1+m2 0 n+m1+m2 0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 48

Carnegie Mellon

Heap Structure Dummy

Dummy
Footer 8/1 16/0 32/1 64/0 32/1 Header 8/1
Start of
heap

heap_start heap_end

⬛nt and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 49

Carnegie Mellon
 size_t block_size =
Top-Level Malloc get_size(block);
write_header(block, block_size,
Code true); write_footer(block,
block_size, true);

const size_t dsize = split_block(block, asize);

2*sizeof(word_t);
return header_to_payload(block);
void *mm_malloc(size_t size) }
{
size_t asize = round_up(size +

dsize, dsize); block_t *block =

find_fit(asize);
round_up(n, m) =
if (block == NULL) m *((n+m-1)/m)
return NULL;
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50
Carnegie Mellon

Top-Level Free Code

void mm_free(void *bp)
{
block_t *block = payload_to_header(bp);
size_t size = get_size(block);

write_header(block, size, false);

 write_footer(block, size, false);

coalesce_block(block);
}

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 51

Carnegie Mellon

Size a
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 52
Carnegie Mellon

No Boundary Tag for Allocated Blocks

⬛ Boundary tag needed only for free blocks ⬛ When
sizes are multiples of 16, have 4 spare bits
Optional block
Payload b = 1: Previous
1 word Size block is
a = 1: Allocated allocated b = 0:
b1
block Previous block
a = 0: Free is free
 application b0
Size: block size data
1 word Size
Payload: Unallocated
d Block
Size b0

Free
Block

padding

Allocate
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 53
Carnegie Mellon

No Boundary Tag for Allocated Blocks

(Case 1)
block next
previous block being block
freed
 m1 ?1 n 11 m2 11
n 10 m2 01
n 10
m1 ?1

Header: Use 2 bits (address bits always zero due to alignment):

(previous block allocated)<<1 | (current block
allocated)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 54

Carnegie Mellon

No Boundary Tag for Allocated Blocks

(Case 2)
block next
previous block being block
freed
 m1 ?1 n 11
m2 10 m2 10

m1 ?1 n+m2 10 n+m2 10

Header: Use 2 bits (address bits always zero due to alignment):

(previous block allocated)<<1 | (current block
allocated)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 55

Carnegie Mellon

No Boundary Tag for Allocated Blocks

(Case 3)
block next
previous block being block
freed m1 ?0
 m1 ?0 n 01

m2 11 n+m1 ?0 m2 01
n+m1 ?0

Header: Use 2 bits (address bits always zero due to alignment):

(previous block allocated)<<1 | (current block
allocated)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 56

Carnegie Mellon

No Boundary Tag for Allocated Blocks

(Case 4)
 n+m1+m2 ?0 ?0

previous m2 10 m2 10
block
n+m1+m2
block
being
freed

next
block
m1 ?0

m1 ?0 n 01
Header: Use 2 bits (address bits always zero due to alignment):
(previous block allocated)<<1 | (current block
allocated)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 57

Carnegie Mellon

Summary of Key Allocator Policies

⬛ Placement policy:
▪ First-fit, next-fit, best-fit, etc.
▪ Trades off lower throughput for less fragmentation
▪ Interesting observation: segregated free lists (next lecture)
approximate a best fit placement policy without having to search
entire free list

⬛ Splitting policy:
▪ When do we go ahead and split free blocks?
▪ How much internal fragmentation are we willing to tolerate?
⬛ Coalescing policy:
▪ Immediate coalescing: coalesce each time free is called ▪ Deferred
coalescing: try to improve performance of free by deferring coalescing
until needed.

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 58

Carnegie Mellon
Implicit Lists: Summary
⬛ Implementation: very simple
⬛ Allocate cost:
▪ linear time worst case
⬛ Free cost:
▪ constant time worst case
▪ even with coalescing
⬛ Memory Overhead
▪ will depend on placement policy
▪ First-fit, next-fit or best-fit
⬛ Not used in practice for malloc/free because of linear
time allocation
▪ used in many special purpose applications
⬛ However, the concepts of splitting and boundary tag
coalescing are general to all allocators
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 59