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
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.4 0.8
0.6
0.4
0.2

0.2

0
Data Fit
DAllocated ata Peak
 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

Effect 1.4

Internal 1.2
1.0

Memory Used / Peak Data

0.8

Fragmentation
0.6
0.4
0.2
 future requests ▪ Thus, di

Perfect Fit epends on the pattern of

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

32 32 48 16
8

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

Im ti

pl o

e n

m w

e it
h
 sed
F foo
ter
o hea
der
o pay
loa
t d

e 1
w
rs o
r
hea d
der
pay ⬛Locating footer of
loa previous block
d
st
unu at
ic
wo
rd
_t
*f
in
d_
pr
ev
_f Bryant and O’Hallaron, Computer Systems: A Programmer’s
Perspective, Third Edition 42
oo Carnegie Mellon
te
r( lit_block
bl (bloc
oc k_t
k_ *bloc
t k,
*b size_
lo t
ck asize
) ){
{ size_
return t
&(block->header) - block
1; _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 {
z w
e r
- i
a t
s e
i _
z h
e e
) a
> d
= 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
u
e
)
Constant Time
;
write_footer(blo
Coalescing
ck, asize,
true);
block_t
*block_next =
find_next(block) Case 1 Case 2 Case 3
; Case 4
 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)

m1 1 n 1

m1 1
n 1 m2 0
 m2 0
m1 1

m1 1 n+m2 n+m2 0
0

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

Carnegie Mellon

Constant Time Coalescing (Case 3)

m1 0 n 1

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

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)

m1 0 n 1

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

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