Page 1

Monday, February 28, 2022
Computer Systems
Winter 2022
Stanford University
Computer Science Department
Lecturer: Chris Gregg
CS 107
Lecture 15: Managing
the Heap Part II
malloc()
calloc()
realloc()
free()

Page 2

Today's Topics
•

Programs from class: /afs/ir/class/cs107/samples/lect15
•

Review of implicit heap allocator
•

Explicit heap allocator
•

More examples!
•

Extra slides: Casting and structs

Page 3

Implicit Free List (review from Friday)
•
On Monday, we discussed the implicit free list, which is one common (though slow...)
way to create a heap allocator. It uses what is called a
block header
to hold the
information.
•
The block header is actually stored in the same memory area as the payload, and it
generally precedes the payload.
88
F
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

Page 4

Implicit Free List (review from Monday)
a = malloc(16);
16
U
aaaaaaaa
64
F
•
This is where things start to get a bit tricky. The heap allocator has 96 bytes, and
it needs to keep the free block information
in those 96 bytes
(I N C E P T I O N)
•
In other words, the heap allocator is using part of the 96 bytes as housekeeping.
•
Note here that there are now 16 bytes of overhead, because there are two header
blocks
.
•
Here, the first 8-byte header block denotes 16 Used bytes, then there is a 16 byte
payload, and then there is another 8
-
byte header to denote the 64 free bytes
after.
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
b
0xffffe808
a
0xffffe800
0x108

Page 5

Implicit Free List (review from Monday)
a = malloc(16);
b = malloc(8);
16
U
aaaaaaaa
8
U
bbbb
48
F
•
We changed the header to reflect the fact that 8 bytes are going to to
b, and we
added a header for the remaining 48 bytes.
•
Also, note that the pointer returned for
a is 0x108, and the pointer returned for b
is 0x120.
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
b
0xffffe808
0x120
a
0xffffe800
0x108

Page 6

Implicit Free List (review from Monday)
a = malloc(16);
b = malloc(8);
c = malloc(24);
16
U
aaaaaaaa
8
U
bbbb
24
U
cccccccccccc
16
F
•
Now we only have 16 bytes left for payloads…let's free some memory.
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
0x130
b
0xffffe808
0x120
a
0xffffe800
0x108

Page 7

Implicit Free List (review from Monday)
a = malloc(16);
b = malloc(8);
c = malloc(24);
free(a);
16
U
aaaaaaaa
8
U
bbbb
24
U
cccccccccccc
16
F
•
Notice that 0x108 will be passed to free. How do we know how much to free?
•
We have to do some pointer arithmetic, so we can grab the 16 from address
0x100 (this diagram does not reflect the
free
yet).
•
As you'll find out when writing your heap allocator: the arithmetic is super
important.
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
0x130
b
0xffffe808
0x120
a
0xffffe800
0x108

Page 8

Implicit Free List (review from Monday)
a = malloc(16);
b = malloc(8);
c = malloc(24);
free(a);
16
F
8
U
bbbb
24
U
cccccccccccc
16
F
•
The diagram now reflects the free.
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
0x130
b
0xffffe808
0x120
a
0xffffe800
0x108

Page 9

Implicit Free List (review from Monday)
a = malloc(16);
b = malloc(8);
c = malloc(24);
free(a);
free(c);
16
F
8
U
bbbb
24
U
cccccccccccc
16
F
•
Again, 0x130 is passed in to this free, so we need to figure out that we need to
look at address 0x128 for the amount of bytes to free.
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
0x130
b
0xffffe808
0x120
a
0xffffe800
0x108

Page 10

Implicit Free List (review from Monday)
a = malloc(16);
b = malloc(8);
c = malloc(24);
free(a);
free(c);
16
F
8
U
bbbb
24
F
16
F
•
One choice for the free is this diagram. Note that we have actually fragmented
our free space! It looks like we only have a block of 24 bytes and then a block of
16 bytes to allocate, yet we should have a block of 48 bytes (we can save a
header, too!)
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
0x130
b
0xffffe808
0x120
a
0xffffe800
0x108

Page 11

Implicit Free List (review from Monday)
a = malloc(16);
b = malloc(8);
c = malloc(24);
free(a);
free(c);
16
F
8
U
bbbb
48
F
•
When we combine free blocks, this is called coalescing, and it is an important tool
that the heap allocator uses to keep memory as unfragmented as possible.
•
We can't coalesce any more because
b is in the middle, and we absolutely cannot
move that block until the program we gave it to frees it.
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Address
Value
e
0xffffe820
d
0xffffe818
c
0xffffe810
0x130
b
0xffffe808
0x120
a
0xffffe800
0x108

Page 12

Implicit Free List
16
F
8
U
bbbb
48
F
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
•
Let's answer the questions we posed before:
•
How do we track the information in a block?
•
The header block that holds the bytes in the block and the state (free or used)
•
How do we organize/find free blocks?
•
Linear search, starting from the first block.
•
How do we pick which free block from available options?
•
If the block is free and has enough space we can choose it, though there are other options
(covered in the next few slides).
•
What do we do with excess space when allocating a block?
•
If we can fit another header and still have at least a block's worth of space, we can do that. If
we can't, it should just become part of the block we are allocating.
•
How do we recycle a freed block?
•
Mark it free, and coalesce if we can.

Page 13

Placement: first
-fit, next-fit, best-fit
The method we have described simply finds the first available block that is free and fits the
request, and then starts from the beginning again on a future allocation. This is called a
first
-
fit

placement policy. One drawback is that you always have to start from the beginning
of the heap, and it can be slow. Another drawback is that it can leave "splinters" (small free
blocks) towards the beginning of the list. One advantage is that it leaves large blocks
towards the end of the list, which allows for larger allocations if necessary.
A second method is called
next-fit
, and was first proposed by Donald Knuth. With next-fit,
you start looking for follow-on blocks after the location of the last allocation. If you found a
suitable block before, you have a good chance to find another one in the same location. It is
still not clear whether next
-fit leads to better (or comparable) memory utilization.
The final method is called
best-fit, and relies on searching the entire heap to find a block
that matches the requested allocation the best. The obvious drawback of best-
fit is that it
requires an exhaustive search of the list.

Page 14

Splitting and Coalescing
We have already described both splitting and coalescing as used in the implicit free list
implementation.
Splitting the memory block is necessary when you have one large block to work with
(which is what you will have for the heap allocator assignment). However, the heap
allocator can request an increase in the size of the block of memory (using the
sbrk
system call
), meaning that you could have a policy to use the entire block and just
request more. But, we aren't going to cover that low level in this course.
Coalescing does not have to happen when you
free
— you can postpone coalescing
until future
malloc
s or reallocs, and while it makes malloc a bit slower, frees are
lighting fast.

Page 15

More on Coalescing: coalescing backwards
Coalescing forwards is straightforward:
16
F
8
U
bbbb
24
F
8
F
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
If we just freed the 24
-byte block, we know exactly where the next block is in order to
see if it (and subsequent blocks) are free.
However, what if we had just freed the 8 byte block? How could we coalesce the two
blocks?
One way would be to look through the whole list from the beginning, keeping track of
where the just
-freed block is. But…this is slow.

Page 16

More on Coalescing: coalescing backwards
Coalescing forwards is straightforward:
16
F
8
U
bbbb
24
F
8
F
96 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158
Another method (described by Knuth) is to keep a footer on each block, as well. The footer is identical
to the header. The above list would look like this with headers and footers (assume we were using them
the whole time, and we have to add more space because of the extra overhead):
16
F
16
F
8
U
bbbb
8
U
24
F
24
F
8
F
8
F
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
Now, let's say we just freed the 8 byte block at 0x168. We can look eight bytes back (to
0x160) at the footer for the 24
-byte block, and we can see that it is also free, and we
can coalesce.

Page 17

More on Coalescing: coalescing backwards
16
F
16
F
8
U
bbbb
8
U
24
F
24
F
8
F
8
F
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
Freed block

Page 18

Page 19

More on Coalescing: coalescing backwards
16
F
16
F
8
U
bbbb
8
U
24
F
24
F
8
F
8
F
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
Footer for
previous
block (also
free)

Page 20

More on Coalescing: coalescing backwards
16
F
16
F
8
U
bbbb
8
U
24
F
24
F
8
F
8
F
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
Entire free
area
16
F
16
F
8
U
bbbb
8
U
56
F
56
F
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
After coalescing
backwards

Page 21

Explicit Free List
One critical issue with the implicit list is the problem with the linear search to find free
blocks (by the way: the implicit list just keeps a pointer to the first block for first-
fit).
The
explicit
free list solves this problem by keeping a linked list of free blocks embedded
in the memory. This is best shown with an example. As before, let's start with an empty
block of memory. With an explicit list, we keep a pointer to the first
free
block.
152
F
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
We use two blocks
in the payload
of the free block to point to the
next
and previous
free blocks.

Page 22

Page 23

Explicit Free List
One critical issue with the implicit list is the problem with the linear search to find free
blocks (by the way: the implicit list just keeps a pointer to the first block for first-
fit).
The
explicit
free list solves this problem by keeping a linked list of free blocks embedded
in the memory. This is best shown with an example. As before, let's start with an empty
block of memory. With an explicit list, we keep a pointer to the first
free
block.
152
F
P:
0x0
N:
0x0
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
We use two blocks
in the payload
of the free block to point to the
next
and previous
free blocks. In this case, there aren't any more free blocks, so they are
NULL
pointers.
0x100
First Free Block

Page 24

Explicit Free List
16
U
aaaaaaaa
96
F
P:
0x0
N:
0x0
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
a = malloc(16);
If we malloc 16, then we allocate as we would in the impl

icit list, but now we have a
pointer to the next free block, and that block still has no previous or next free block.
Notice something important: the two pointers we had just got eaten up by the payload!
0x118
First Free Block

Page 25

Explicit Free List
16
U
aaaaaaaa
16
U
bbbbbbbb
24
U
cccccccccccc
48
F
P:
0x0
N:
0x0
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
a = malloc(16);
b = malloc(8);
c = malloc(24);
We continue the process. Note that we must leave at least 16 bytes in a block to save
room for pointers if we eventually free (e.g.,
b
has more space than it requested).
0x150
First Free Block

Page 26

Explicit Free List
a = malloc(16);
b = malloc(8);
c = malloc(24);
free(b);
Now when we free
b
, we point to the newly freed memory, and update the pointers
16
U
aaaaaaaa
16
U
bbbbbbbb
24
U
cccccccccccc
48
F
P:
0x0
N:
0x0
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
0x150
First Free Block

Page 27

Explicit Free List
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
a = malloc(16);
b = malloc(8);
c = malloc(24);
free(b);
Now when we free
b
, we point to the newly freed memory, and update the pointers
16
U
aaaaaaaa
16
F
P:
0x0
N:
0x150
24
U
cccccccccccc
48
F
P:
0x118
N:
0x0
0x118
First Free Block
The newly freed block becomes the first free block (it is
added to the beginning of the list)

Page 28

Page 29

Explicit Free List
160 bytes
0x100

0x108

0x110

0x118

0x120

0x128

0x130

0x138

0x140

0x148

0x150

0x158

0x160

0x168

0x170

0x178
Why is this better than the implicit free list?
16
U
aaaaaaaa
16
F
P:
0x0
N:
0x150
24
U
cccccccccccc
48
F
P:
0x118
N:
0x0
0x118
•
We can now traverse only the free blocks!
•
This is much faster than traversing the whole list.
•
For instance, if we now tried to malloc 24 bytes, we would only need to look
through two blocks (0x118 and then 0x150) to find enough space.
First Free Block

Page 30

More on Implicit and Explicit Heap Allocation
•

For Assignment 7, you will be writing two heap allocators: implicit and explicit.
•

Let's perform the following allocation and free on both allocators, to practice more.
Note:
the method outlined here doesn't have to be exactly how you implement the
allocators (and in fact, they can be improved conceptually to be faster, etc.), but this
should give you an overview of the differences and some details.
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
allocation 0 for 24 bytes
allocation 1 for 20 bytes
allocation 2 for 16 bytes
free 1
allocation 3 for 32 bytes
allocation 4 for 12 bytes
free 3
reallocate 2 to 60 bytes

Page 31

Implict Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
•

We will start with the following free heap
•

Headers will take up 8 bytes.
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Addresses are in hex

Page 32

Implict Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
248
F
•

After initialization, header holds the value of the whole free area, and designates it as (F)ree
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
•

Addresses are in hex
•

Byte allocations are in decimal

Page 33

Implict Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
248
F
•

Allocation of 24 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
yes
yes
use this block
2.

Is there enough space for the request?

Page 34

Implict Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
216
F
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
yes
yes
use this block
•

Allocation of 24 bytes
1.

Is the block free?
2.

Is there enough space for the request?
0000000

Page 35

Implict Heap Allocation
•

Allocation of 20 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
no
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
216
F
0000000
2.

Go to next block (use pointer arithmetic to get there)

Page 36

Page 37

Implict Heap Allocation
•

Allocation of 20 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
2.

Is there enough space for the request?
yes
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
184
F
yes
use this block
Why 24 bytes?

8-byte alignment
0000000
1111111
Is this strictly necessary here? No
— the header
blocks don't have to be aligned to 8-
byte
boundaries. But it may make it easier! Remember,
all
allocations
must be on an 8-byte alignment.

Page 38

Implict Heap Allocation
•

Allocation of 16 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
2.

Go to next block (use pointer arithmetic to get there)
no
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
184
F
0000000
1111111

Page 39

Page 40

Implict Heap Allocation
•

Allocation of 16 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
2.

Is there enough space for the request?
yes
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
184
F
yes
use this block
0000000
1111111

Page 41

Page 42

Implict Heap Allocation
•

Free 1
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Mark as free
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
160
F
0000000
1111111
2222

Page 43

Page 44

Implict Heap Allocation
•

Allocation of 32 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
no
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
16
U
160
F
2.

Go to next block (use pointer arithmetic to get there)
2222

Page 45

Implict Heap Allocation
•

Allocation of 32 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
2.

Is there enough space for the request?
yes
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
16
U
160
F
no
3.

Go to next block (use pointer arithmetic to get there)
2222

Page 46

Page 47

Page 48

Page 49

Implict Heap Allocation
•

Allocation of 12 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
no
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
16
U
32
U
120
F
2222

3333333333
2.

Go to next block (use pointer arithmetic to get there)

Page 50

Implict Heap Allocation
•

Allocation of 12 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
yes
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
16
U
32
U
120
F
2222

3333333333
2.

Is there enough space for request?
yes
use this block

Page 51

Implict Heap Allocation
•

Allocation of 12 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
yes
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
U
120
F
2222

3333333333
2.

Is there enough space for request?
yes
use this block
4444444
Why not 12 or 16?
alignment and not enough space after

Page 52

Implict Heap Allocation
•

Free 3
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Set to free
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
U
120
F
2222

3333333333
4444444

Page 53

Page 54

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Enough space after?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
F
120
F
2222
4444444
yes
(take as much space to the right as
possible, but only for realloc, not
malloc)
If no, we would have had to move
the block by searching through he
whole list for a spot with enough
space (see the next slide)

Page 55

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
F
16
U
96
F
2222
4444444
no
Check next block
5555
Assume, for a moment, that there had not been
space. We would have started searching

Page 56

Page 57

Page 58

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
F
16
U
96
F
2222
4444444
yes
Check next block
5555
Assume, for a moment, that there had not been
space. We would have started searching
2.

Is there enough space?
no

Page 59

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
F
16
U
96
F
2222
4444444
no
5555
Assume, for a moment, that there had not been
space. We would have started searching
Check next block

Page 60

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
F
16
U
96
F
2222
4444444
yes
2.

Is there enough room?
yes
Move 2, free, and update
5555
Assume, for a moment, that there had not been
space. We would have started searching

Page 61

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
F
32
F
16
U
64
F
24
F
22222222222222222222
4444444
yes
2.

Is there enough room?
yes
Move 2, free, and update
5555
Assume, for a moment, that there had not been
space. We would have started searching

Page 62

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
F
120
F
2222
4444444
yes
2.

Is there enough room?
yes (take as much as
possible to the right)
Back to the version where we
do
have space, if we
count all the possible free space to the right

Page 63

Implict Heap Allocation
•

Realloc 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to heap
1.

Is the block free?
0000000
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
64
U
112
F
22222222222222222222
4444444
yes
2.

Is there enough room?
yes (take as much as
possible to the right)
3.

Expand block
Back to the version where we
do
have space, if we
count all the possible free space to the right

Page 64

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
248
F
\0

\0
•

After initialization, header holds the value of the whole free area, and designates it as (F)ree
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to free block
•

Addresses are in hex
•

Byte allocations are in decimal
•

The pointer to the heap is always to a free block!
•

For explicit, we will have two pointers that live in the
potential payload area
(in yellow).
•

The pointers are the previous and next pointers for
our linked list, although in this case they will both be
NULL because there aren't any other nodes.
next prev

Page 65

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
248
F
\0

\0
•

Allocate 24 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Is there enough space?
pointer to free block
yes
use this block
next prev

Page 66

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
216
F
\0

\0
•

Allocate 24 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Is there enough space?
pointer to free block
yes
use this block
•

The pointers become part of the allocated space,
because we don't need them now!
•

We update the heap pointer to point to a free
block.
0000000
next prev

Page 67

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
216
F
\0

\0
•

Allocate 20 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Is there enough space?
pointer to free block
yes
use this block
•

The pointers become part of the allocated space,
because we don't need them now!
•

We update the heap pointer to point to a free
block.
0000000
next prev

Page 68

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
184
F
\0

\0
•

Allocate 20 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Is there enough space?
pointer to free block
yes
use this block
•

The pointers become part of the allocated space,
because we don't need them now!
•

We update the heap pointer to point to a free
block.
0000000
1111111
next prev

Page 69

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
184
F
\0

\0
•

Allocate 16 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Is there enough space?
pointer to free block
yes
use this block
•

The pointers become part of the allocated space,
because we don't need them now!
•

We update the heap pointer to point to a free
block.
0000000

1111111
next prev

Page 70

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
160
F
\0

\0
•

Allocate 16 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Is there enough space?
pointer to free block
yes
use this block
•

The pointers become part of the allocated space,
because we don't need them now!
•

We update the heap pointer to point to a free
block.
0000000
1111111
2222
next prev

Page 71

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
160
F
\0

\0
•

Free 1
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Free, and add to linked list
pointer to free block
0000000
1111111
2222
next prev

Page 72

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
58

\0
16
U
160
F
\0

20
•

Free 1
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Free, and add to linked list
•

(remember to update all necessary
doubly
-linked list pointers!)
pointer to free block
0000000
2222
next prev
next prev

Page 73

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
58

\0
16
U
160
F
\0

20
•

Allocate 32 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Check head of list (green) — is there enough
room?
pointer to free block
0000000
2222
no
Follow next pointer
next prev
next prev

Page 74

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
58

\0
16
U
160
F
\0

20
•

Allocate 32 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
pointer to free block
0000000
2222
next prev
next prev

Page 75

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
58

\0
16
U
160
F
\0

20
•

Allocate 32 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Check node (green) in list — is there enough
room?
pointer to free block
0000000
2222
yes
add here and update list
next prev
next prev

Page 76

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
88

\0
16
U
32
U
120
F
\0

20
•

Allocate 32 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Check node in list — is there enough
room?
pointer to free block
0000000
2222
yes
add here and update list
3333333333
next prev
next prev

Page 77

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
F
88

\0
16
U
32
U
120
F
\0

20
•

Allocate 12 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Check node (green) in list — is there
enough room?
pointer to free block
0000000
2222
yes
add here and update list
3333333333
next prev
next prev

Page 78

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
U
120
F
\0

\0
•

Allocate 12 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Check node (green) in list — is there
enough room?
pointer to free block
0000000
2222
yes
add here and update list
3333333333
next prev
4444444

Page 79

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
32
U
120
F
\0

\0
•

Free 3
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Free 3, and coalesce
pointer to free block
0000000
2222
3333333333
next prev
4444444

Page 80

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
160
F
\0

\0
•

Free 3
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Free 3, and coalesce
•

Make sure to update linked list
pointer to free block
0000000
2222
next prev
4444444

Page 81

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
16
U
160
F
\0

\0
•

Reallocate 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Enough space after?
pointer to free block
0000000
2222
next prev
4444444
yes
•

No move necessary, but we do have
to do our updates.

Page 82

Explicit Heap Allocation
Heap size: 256 bytes
0

8

10 18 20 28 30 38 40 48 50 58 60 68 70 78 80 88 90 98 a0 a8 b0 b8 c0 c8 d0 d8 e0 e8 f0 f8
24
U
24
U
64
U
112
F
\0

\0
•

Reallocate 2 to 60 bytes
a 0 24
a 1 20
a 2 16
f 1
a 3 32
a 4 12
f 3
r 2 60
•

Enough space after?
pointer to free block
0000000
22222222222222222222
next prev
4444444
yes
•

No move necessary, but we do have
to do our updates.

Page 83

References and Advanced Reading
References:
•
The textbook is the best reference for this material.
•
Here are more slides from a similar course:
https://courses.engr.illinois.edu/cs241/sp2014/lecture/06-HeapMemory_sol.pdf
Advanced Reading:
•

Implementation tactics for a heap allocator:
https://stackoverflow.com/questions/2946604/c-implementation-
tactics
-
for
-
heap
-allocators

Page 84

Extra Slides
Extra Slides

Page 85

Struct Casting
For your heap allocator assignment, you might want to consider casting all of your
void *

pointers to
structs
, as this will make it easier to debug. It will also
make the code a lot cleaner. Let's see an example of casting structs that helps
see how it is done.
First, here is a struct for some student information (
struct_ex.c
in
samples/lect15
):
typedef struct student_info {
char email[32];
int labs_attended;
double assignment_avg;
double midterm;
double final;
} student_info;
We can typedef the struct to
make it easier to work with. Now
we can refer to it as, simply,
student_info
.

Page 86

Struct Casting
Next, let's write an update_info function but without the benefit of any type
information for the struct:
void update_info(void *student, char *email, int labs_attended,
double assignment_avg, double midterm, double final)
{
// we have a void *, but we can simply cast it
student_info *si = (student_info *)student;
strcpy(si
-
>email, email);
si
-
>labs_attended = labs_attended;
si
-
>assignment_avg = assignment_avg;
si
-
>midterm = midterm;
si
-
>final = final;
}
We simply cast the
void *
pointer to our data type, and the
struct
just
works.

Page 87

Struct Casting
We can do the same thing for a print function:
void print_student(void *student)
{
// again, we have a void *, but we can just cast
student_info *si = (student_info *)student;
printf("Email: %s
\
n",si
-
>email);
printf("Labs attended: %d out of %d
\
n",si
-
>labs_attended,NUM_LABS);
printf("Assignment Average: %g
\
n",si
-
>assignment_avg);
printf("Midterm: %g
\
n",si
-
>midterm);
printf("Final: %g
\
n",si
-
>final);
double overall_avg = (si
-
>labs_attended / (double)NUM_LABS * 10 +
si
-
>assignment_avg * 0.4 +
(si
-
>midterm * 0.33 + si
-
>final * 0.67) * 0.5);
printf("Overall average: %g
\n\
n",overall_avg);
}

Page 88

Struct Casting
Here is where it gets interesting. In
main
, we're just going to grab a typeless block
of data:
#define BIG_BLOCK 10000
int main(int argc, char **argv)
{
// big block of data with no type information :(
void *student_data = malloc(BIG_BLOCK);
// let's add some students
// let's add one at the beginning of the block of data
update_info(student_data, "cgregg@stanford.edu", 7, 92.0, 83.4, 94.0);
...
We can add a student to
anywhere we want
in that block of data (though this
might not be ideal for alignment purposes)

Page 89

Struct Casting
Again, we can add a student anywhere in the data!
// it's a big block of data, so we can add a student anywhere :O
// let's add one 6543 bytes down the line. Remember, we do have to
// cast if we want pointer arithmetic
void *random_location = (char *)student_data + 6543;
update_info(random_location, "super_student@stanford.edu", 8, 100.0, 100.0, 100.0);
// let's print the two students
print_student(student_data);
print_student(random_location);
free(student_data);
return 0;
}
We just added a student at location 6543 in our block of data -- we didn't have
to put the data on what would be a struct boundary in an array of structs.

Page 90

Struct Casting
Let's look at a gdb trace of the program:
$ gdb struct_ex
(gdb) break main
Breakpoint 1 at 0x400756: file struct_ex.c, line 45.
(gdb) run
Starting program:
/afs/.ir.stanford.edu/users/c/g/cgregg/tmp/lect15/struct
_ex
Breakpoint 1, main (argc=1, argv=0x7fffffffea78) at
struct_ex.c:45
(gdb) n
47

void *student_data = malloc(BIG_BLOCK);
(gdb)
52

update_info(student_data, "cgregg@stanford.edu",
7, 92.0, 83.4, 94.0);
(gdb) x/10gx student_data
0x602010: 0x0000000000000000

0x0000000000000000
0x602020: 0x0000000000000000

0x0000000000000000
0x602030: 0x0000000000000000

0x0000000000000000
0x602040: 0x0000000000000000

0x0000000000000000
0x602050: 0x0000000000000000

0x0000000000000000
(gdb) n
We can look at the bytes in the
student_data

block. One
compact way to do this is with
the "
x/gx" command.
Before we update the student,
the data happens to be all 0s.

Page 91

Page 92

Struct Casting
Let's look at a gdb trace of the program:
(gdb) n
(gdb) x/10gx student_data
0x602010: 0x7340676765726763

0x2e64726f666e6174
0x602020: 0x0000000000756465

0x0000000000000000
0x602030: 0x0000000000000007

0x4057000000000000
0x602040: 0x4054d9999999999a

0x4057800000000000
0x602050: 0x0000000000000000

0x0000000000000000
(gdb) n
We put in the following information: email: cgregg@stanford.edu, number of
labs: 7.
The long values are read in reverese:
0x60210
is the
0x63
in the first block,
which is a "c".
After we update the student, the
info is located in
student_data
, but we have to
be careful reading it -- it
presumes little-endian format,
but prints in normal format...

Page 93

Page 94

Page 95

Page 96

Page 97

Struct Casting
Let's look at a gdb trace of the program:
(gdb) n
(gdb) x/10gx student_data
0x602010: 0x7340676765726763

0x2e64726f666e6174
0x602020: 0x0000000000756465

0x0000000000000000
0x602030: 0x0000000000000007

0x4057000000000000
0x602040: 0x4054d9999999999a

0x4057800000000000
0x602050: 0x0000000000000000

0x0000000000000000
(gdb) n
Our next data is the
int
for the number of labs. It turns out that the alignment
for other fields is going to be on an 8-byte boundary, so the struct actually takes
8 bytes for the int. Again, the addresses are backwards, because the number
itself is in little-endian format. So,
0x602030
is the
0x07
byte,
0x0602031
is
the
0x00 byte to the left of the 0x07
, etc.
After we update the student, the
info is located in
student_data
, but we have to
be careful reading it -- it
presumes little-endian format,
but prints in normal format...