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
Constraints
or size of allocated blocks
▪ Must respond immediately to malloc requests
▪ i.e., can’t reorder or buffer requests
▪ Must allocate blocks from free memory
▪ i.e., can only place allocated blocks in free memory ▪
Must
align blocks so they satisfy all alignment requirements ▪
16-byte (x86-64) alignment on 64-bit systems
Carnegie Mellon

Performance Goal: Throughput

⬛ Given some sequence of malloc and free
▪ Number of completed requests per unit time
▪ Example:
▪ 5,000 malloc calls and 5,000 free calls in 10 seconds
 ▪ Throughput is 1,000 operations/second

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

Carnegie Mellon

Performance Goal: Minimize Overhead

⬛ Given some sequence of malloc and free
requests: ▪ ��0, ��1, … , ����, … , ����−1
⬛ After �� requests we have:

▪ Assume heap only grows when allocator uses sbrk, never shrinks

⬛ Def: Overhead, ����

▪ Fraction of heap space NOT used for program data
▪ ���� = (����Τmax��≤�� ����) − 1.0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13
Carnegie Mellon
 Benchmark Example
⬛Benchmark
syn-array-short
▪ Trace provided with
malloc lab
▪ Allocate & free 10 blocks ▪ a = allocate
▪ f = free
▪ Bias toward allocate at beginning &

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

Carnegie Mellon
 Benchmark Visualization
16 a 9 20 20 4240 90036

17 f 4 -840 3400 90036

Step Command Delta Allocated Peak 18 f 8 -136 3264 90036
1 a 0 9904 9904 9904 9904 19 f 5 -3244 20 90036
2 a 1 50084 50084 59988 59988 20 f 9 -20 0 90036
3 a 2 20 20 60008 60008

4 a 3 16784 16784 76792 76792 1

5 f 3 -16784 60008 76792

6 a 4 840 840 60848 76792 Normalized Aggregate Memory

7 a 5 3244 3244 64092 76792 0.8

8 f 0 -9904 54188 76792

9 a 6 2012 2012 56200 76792

0.6
10 f 2 -20 56180 76792

11 a 7 33856 33856 90036 90036

12 f 1 -50084 39952 90036 0.4

13 a 8 136 136 40088 90036

14 f 7 -33856 6232 90036

0.2
15 f 6 -2012 4220 90036
 1.0

Memory Used / Peak Data

0.8
0.6
0.4
0.2
0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Step
Data Fit
DAllocated ata Peak
Allocated Peak1.2

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
 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17
Carnegie Mellon

Internal Fragmentation
⬛ For a given block, internal fragmentation occurs if payload is
smaller than block size
 Block

Payload Internal fragmentation

Internal
fragmentation⬛ Caused by

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
t
⬛
D e
r
e
p n
e o
n f
f
d
u
s
o t
n u
t r
h e
e r
p e
a q
u
 e h
s u
s
t ,
s d
▪ i
T
Payload
free blocks
Size
a Optional
padding
Format of
allocated and
a = 1: Allocated block a = 0: Free Payload: application data (allocated
block blocks only)

Size: total block size

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

Carnegie Mellon
 Detailed Implicit Free List Example End

Start of Unused Block 8/1

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

heap_start heap_end
Headers: labeled with “size in
words/allocated bit” Headers are at
Double-word aligned
non-aligned positions
Allocated blocks: shaded
➔ Payloads are aligned
Free blocks: unshaded

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

Carnegie Mellon

Implicit List: Data Structures

block pointer return (void *) (block->payload);

⬛Getting header from payload

// Zerond O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 29
Carnegie Mellon

Implicit List:
Traversing list
header payload unused header payload

block size

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

End
Block 8/1

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

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

[Link]
/courses/24383/quizzes
/67237
 e
n
t
Bryant and O’Hallaron, Computer Systems: A Programmer’s
a
Perspective, Third Edition 40
Carnegie Mellon
ti
Im
o
pl
n
e
w
m
it
 d
h unu
sed
F foo
ter
o hea
der
o pay
loa
t d
asize
e asize
d
rs s
i
hea z
e
der
pay ⬛Locating footer of
loa 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
r_
to
_f Bryant and O’Hallaron, Computer Systems: A Programmer’s
Perspective, Third Edition 41
oo Carnegie Mellon
te
r(
bl
oc
Im
k_
t
*b
pl
lo
ck
)
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 previous block
unu
sed st
at
foo ic
ter wo
rd
hea _t
der *f
in
pay d_
loa pr
ev
d _f
oo
te
r(
bl
oc
k_
t
*b
lo
 ck ){
) size_
{ t
return block
&(block->header) - _size
1; =
} get_s
ize(b
lock)
;

i
f
(
(
b
Bryant and O’Hallaron, Computer Systems: A Programmer’s l
Perspective, Third Edition 42
Carnegie Mellon o
c
lit_block k
(bloc _
k_t s
*bloc i
k, z
size_ e
t -
asize a
s e
i _
z h
e e
) a
> d
= e
m r
i (
n b
_ l
b o
l c
o k
c ,
k a
_ s
s i
i z
z e
e ,
) t
{ r
w u
r e
i )
t ;
 Perspective, Third Edition 43
write_footer(blo Carnegie Mellon
ck, asize,
true);
block_t
*block_next = Constant Time
find_next(block)
; Coalescing
write_h
eader(block_nex
t, block_size -
asize, false);
write_footer(bl Case 1 Case 2 Case 3
ock_next,
Case 4
block_size -
asize, false);
}

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

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