Carnegie Mellon

Dynamic Memory Allocation:

Basic Concepts
15-213/15-513/14-513: Introduction to Computer Systems
13th Lecture, October 8, 2024

Instructors:
Brian Railing
David Varodayan

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

 Carnegie Mellon

Deadlines and Fall Break

 Labs
 Cachelab is due this Thursday October 10
 Malloc checkpoint is due on Tuesday October 29
 Malloc final is due on Tuesday November 5

 Written Assignments
 Written 5 and Peer Review 4 is due October 9
 Written 5 is double credit
 Treat it like an exam

 Fall Break (October 12 to 20)

 No lectures or deadlines
 No office hours, but there may be some piazza coverage

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

Dynamic Memory Allocation

Memory
invisible to
Application Kernel virtual memory
user code
User stack
Dynamic Memory Allocator (created at runtime)
%rsp
Heap (stack
pointer)
 Programmers use dynamic Memory-mapped region for
memory allocators (such as shared libraries

malloc) to acquire virtual

memory (VM) at runtime “The break”
 For data structures whose size Run-time heap
(created by malloc)
is only known at runtime
Read/write segment Loaded
 Dynamic memory allocators (.data, .bss) from
manage an area of process the
Read-only segment executable
VM known as the heap (.init, .text, .rodata) file
0x400000
Unused
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 0 4
 Carnegie Mellon

Dynamic Memory Allocation

 Allocator maintains heap as collection of variable sized

blocks, which are either allocated or free
 Types of allocators
 Explicit allocator: application allocates and frees space

e.g., malloc and free in C
 Implicit allocator: application allocates, but does not free space
 e.g., new and garbage collection in Java

 Will discuss simple explicit memory allocation today

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

 Carnegie Mellon

The malloc Package

#include <stdlib.h>
void *malloc(size_t size)
 Successful:
 Returns a pointer to a memory block of at least size bytes
aligned to a 16-byte boundary (on x86-64)
 If size == 0, returns NULL
 Unsuccessful: returns NULL (0) 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, calloc, or realloc
Other functions
 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;

/* Allocate a block of n longs */

p = (long *) malloc(n * sizeof(long));
if (p == NULL) {
perror("malloc");
exit(0);
}

/* Initialize allocated block */

for (i=0; i<n; i++)
p[i] = i;
/* Do something with p */
. . .
/* Return allocated block to the heap */
free(p);
}

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

 Carnegie Mellon

Heap Visualization Convention

 1 square = 1 “word” = 8 bytes

Highest address
within heap
Lowest address (“the break”, adjustable
within heap by sbrk system call)

Allocated block Free block

(4 words) (2 words) Free word
Allocated word

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

 Carnegie Mellon

Allocation Example
(Conceptual)
p1 = malloc(32)

p2 = malloc(40)

Gap for alignment

p3 = malloc(48)

free(p2)

p4 = malloc(16)

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

 Carnegie Mellon

Constraints
 Applications
 Can issue arbitrary sequence of malloc and free requests
 free request must be to a malloc’d block

 Explicit Allocators
 Can’t control number 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
 Can manipulate and modify only free memory
 Can’t move the allocated blocks once they are malloc’d
 i.e., compaction is not allowed. Why not?

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

 Carnegie Mellon

Performance Goal: Throughput

 Given some sequence of malloc and free requests:


 Goals: maximize throughput and peak memory utilization

 These goals are often conflicting

 Throughput:
 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 11

 Carnegie Mellon

Performance Goal: Minimize Overhead

 Given some sequence of malloc and free requests:

 After requests we have:

 Def: Aggregate payload
 malloc(p) results in a block with a payload of p bytes
 The aggregate payload is the sum of currently allocated payloads
 The peak aggregate payload is the maximum aggregate payload at any
point in the sequence up to request
 Def: Current heap size
 Assume heap only grows when allocator uses sbrk, never shrinks
 Def: Overhead,
 Fraction of heap space NOT used for program data

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

 Carnegie Mellon

Benchmark Example
Step Command Delta Allocated Peak
1 a 0 9904 9904 9904 9904
 Benchmark 2 a 1 50084 50084 59988 59988
syn-array-short 3 a 2 20 20 60008 60008
4 a 3 16784 16784 76792 76792
 Trace provided with 5 f 3 -16784 60008 76792
malloc lab 6 a 4 840 840 60848 76792
 7 a 5 3244 3244 64092 76792
Allocate & free 10 blocks 8 f 0 -9904 54188 76792
 a = allocate 9 a 6 2012 2012 56200 76792
 10 f 2 -20 56180 76792
f = free 11 a 7 33856 33856 90036 90036
 Bias toward allocate at 12 f 1 -50084 39952 90036
beginning & free at end 13 a 8 136 136 40088 90036
14 f 7 -33856 6232 90036
 Blocks number 1–10 15 f 6 -2012 4220 90036
 Allocated: Sum of all 16 a 9 20 20 4240 90036
17 f 4 -840 3400 90036
allocated amounts 18 f 8 -136 3264 90036
 Peak: Max so far of 19 f 5 -3244 20 90036
Allocated 20 f 9 -20 0 90036

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

 Carnegie Mellon

Benchmark Visualization
Step Command Delta Allocated Peak 1
1 a 0 9904 9904 9904 9904
2 a 1 50084 50084 59988 59988

Normalized Aggregate Memory

3 a 2 20 20 60008 60008 0.8
4 a 3 16784 16784 76792 76792
5 f 3 -16784 60008 76792
0.6
6 a 4 840 840 60848 76792
7 a 5 3244 3244 64092 76792
8 f 0 -9904 54188 76792 0.4
9 a 6 2012 2012 56200 76792
10 f 2 -20 56180 76792
11 a 7 33856 33856 90036 90036 0.2
12 f 1 -50084 39952 90036
13 a 8 136 136 40088 90036
0
14 f 7 -33856 6232 90036 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
15 f 6 -2012 4220 90036
Step
16 a 9 20 20 4240 90036
17 f 4 -840 3400 90036
18 f 8 -136 3264 90036 Allocated Peak
19 f 5 -3244 20 90036
20 f 9 -20 0 90036  Plot (allocated) and (peak)
as a function of (step)
 Y-axis normalized — fraction of maximum

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

 Carnegie Mellon

Typical Benchmark Behavior

Peak
Allocated

 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 15
 Carnegie Mellon

Fragmentation
 Poor memory utilization caused by fragmentation
 Internal fragmentation
 External fragmentation

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

 Carnegie Mellon

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

Block

Internal Internal
Payload
fragmentation fragmentation

 Caused by
 Overhead of maintaining heap data structures
 Padding for alignment purposes
 Explicit policy decisions
(e.g., to return a big block to satisfy a small request)
 Depends only on the pattern of previous requests
 Thus, easy to measure
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17
 Carnegie Mellon

Internal Fragmentation Effect

Peak + Internal Frag

Peak
Allocated

 Purple line: additional heap size due to

allocator’s data + padding for alignment
 For this benchmark, 1.5% overhead
 Cannot achieve in practice
 Especially since cannot move allocated blocks
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 18
 Carnegie Mellon

External Fragmentation
 Occurs when there is enough aggregate heap memory,
but no single free block is large enough
p1 = malloc(32)

p2 = malloc(40)

p3 = malloc(48)

free(p2)

p4 = malloc(64) Yikes! (what would happen now?)

 Depends on the pattern of future requests
 Thus, difficult to measure

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

 Carnegie Mellon

External Fragmentation Effect

Peak + All Frag (Best Fit)

Peak + Internal Frag
Peak
Allocated

 Green line: additional heap size due to external fragmentation

 Best Fit: One allocation strategy
 (To be discussed later)
 Total overhead = 8.3% on this benchmark

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

 Carnegie Mellon

Implementation Issues
 How do we know how much memory to free given just a
pointer?

 How do we keep track of the free blocks?

 What do we do with the extra space when allocating a

structure that is smaller than the free block it is placed in?

 How do we pick a block to use for allocation -- many

might fit?

 How do we reuse a block that has been freed?

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

Knowing How Much to Free

 Standard method
 Keep the length (in bytes) of a block in the word preceding the
block.
 Including the header
 This word is often called the header field or header
 Requires an extra word for every allocated block

p0
p0 = malloc(32)
48

block size Payload Padding

(aligned) (for alignment)
free(p0)

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

 Carnegie Mellon

Keeping Track of Free Blocks

 Method 1: Implicit list using length—links all blocks
Need to tag
Unused
each block as
32 48 32 16
allocated/free

 Method 2: Explicit list among the free blocks using pointers

Need space
32 48 32 16
for pointers
 Method 3: Segregated free list
 Different free lists for different size classes

 Method 4: Blocks sorted by size

 Can use a balanced tree (e.g., Red-Black tree) with pointers within each
free block, and the length used as a key
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23
 Carnegie Mellon

Today
 Basic concepts
 Implicit free lists

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

 Carnegie Mellon

Method 1: Implicit Free List

 For each block we need both size and allocation status
 Could store this information in two words: wasteful!
 Standard trick
 When blocks are aligned, some low-order address bits are always 0
 Instead of storing an always-0 bit, use it as an allocated/free flag
 When reading the Size word, must mask out this bit
1 word

Size a a = 1: Allocated block

a = 0: Free block
Format of
allocated and Payload
Size: total block size
free blocks
Payload: application data
(allocated blocks only)
Optional
padding
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25
 Carnegie Mellon

Detailed Implicit Free List Example

End
Unused Block
Start
of 16/0 32/1 64/0 32/1 8/1
heap

heap_start heap_end

Double-word Allocated blocks: shaded

aligned Free blocks: unshaded
Headers: labeled with “size in words/allocated bit”
Headers are at non-aligned positions
 Payloads are aligned

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

 Carnegie Mellon

Implicit List: Data Structures

header payload
 Block declaration
typedef uint64_t word_t;
typedef struct block
{
word_t header;
unsigned char payload[0]; // Zero length array
} block_t;

 Getting payload from block pointer // block_t *block

return (void *) (block->payload);
 Getting header from payload // bp points to a payload
return (block_t *) ((unsigned char *) bp
- offsetof(block_t, payload));

C function offsetof(struct, member) returns offset of member within struct

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

 Carnegie Mellon

Implicit List: Header access

Size a
 Getting allocated bit from header
return header & 0x1;
 Getting size from header
return header & ~0xfL;
 Initializing header // block_t *block
block->header = size | alloc;

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

 Carnegie Mellon

Implicit List: Traversing list

header payload unused header payload

block size

 Find next block

static block_t *find_next(block_t *block)
{
return (block_t *) ((unsigned char *) block
+ get_size(block));
}

End
Unused Block

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

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

 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_end

16/0 32/1 64/0 32/1 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:
 Can take linear time in total number of blocks (allocated and free)
 In practice it can cause “splinters” at beginning of list
 Next fit:
 Like first fit, but search list starting where previous search finished
 Should often be faster than first fit: avoids re-scanning unhelpful blocks
 Some research suggests that fragmentation is worse
 Best fit:
 Search the list, choose the best free block: fits, with fewest bytes left over
 Keeps fragments small—usually improves memory utilization
 Will typically run slower than first fit
 Still a greedy algorithm. No guarantee of optimality

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

 Carnegie Mellon

Comparing Strategies

 Total Overheads (for this benchmark)

 Perfect Fit: 1.6%
 Best Fit: 8.3%
 First Fit: 11.9%
 Next Fit: 21.6%

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

 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 32 32 16 16 8

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

 Carnegie Mellon

Implicit List: Splitting Free Block

split_block(p, 32)

64 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);
}

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

 Carnegie Mellon

Implicit List: Freeing a Block

 Simplest implementation:
 Need only clear the “allocated” flag
 But can lead to “false fragmentation”

32 32 32 16 16 8

free(p) p

32 32 32 16 16 8

malloc(5*SIZ) Yikes!
There is enough contiguous
free space, but the allocator
won’t be able to find it

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

 Carnegie Mellon

Implicit List: Coalescing

 Join (coalesce) with next/previous blocks, if they are free
 Coalescing with next block

32 32 32 16 16 8
logically
p
free(p) gone
32 32 48 16 16 1

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

 Carnegie Mellon

Implicit List: Coalescing

 Join (coalesce) with next block, if it is free
 Coalescing with next block

64 32 16 16 8
logically
p
free(p) gone
64 48 16 16 8

 How do we coalesce with previous block?

 How do we know where it starts?
 How can we determine whether its allocated?

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

 Carnegie Mellon

Implicit List: Bidirectional Coalescing

 Boundary tags [Knuth73]
 Replicate size/allocated word at “bottom” (end) of free blocks
 Allows us to traverse the “list” backwards, but requires extra space
 Important and general technique!

8 32 32 32 32 48 48 32 32 8

Header Size a a = 1: Allocated block

a = 0: Free block
Format of
Size: Total block size
allocated and Payload and
free blocks padding
Payload: Application data
(allocated blocks only)
Boundary tag Size a
(footer)

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

 Carnegie Mellon

Quiz

[Link]

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

 Carnegie Mellon

Implementation with Footers

header payload unused footer header payload

asize
asize
dsize

 Locating footer of current block

const size_t dsize = 2*sizeof(word_t);

static word_t *header_to_footer(block_t *block)

{
size_t asize = get_size(block);
return (word_t *) (block->payload + asize - dsize);
}

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

 Carnegie Mellon

Implementation with Footers

header payload unused footer header payload

1 word

 Locating footer of previous block

static word_t *find_prev_footer(block_t *block)
{
return &(block->header) - 1;
}

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

 Carnegie Mellon

Splitting Free Block: Full Version

split_block(p, 32)

64 64 16 32 32 32 32 16

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);
write_footer(block, asize, true);
block_t *block_next = find_next(block);
write_header(block_next, block_size - asize, false);
write_footer(block_next, block_size - asize, false);
}

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

 Carnegie Mellon

Constant Time Coalescing

Case 1 Case 2 Case 3 Case 4

Allocated Allocated Free Free

Block being
freed
Allocated Free Allocated Free

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

 Carnegie Mellon

Constant Time Coalescing (Case 1)

m1 1 m1 1

m1 1 m1 1
n 1 n 0

n 1 n 0
m2 1 m2 1

m2 1 m2 1

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

 Carnegie Mellon

Constant Time Coalescing (Case 2)

m1 1 m1 1

m1 1 m1 1
n 1 n+m2 0

n 1
m2 0

m2 0 n+m2 0

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

 Carnegie Mellon

Constant Time Coalescing (Case 3)

m1 0 n+m1 0

m1 0
n 1

n 1 n+m1 0
m2 1 m2 1

m2 1 m2 1

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

 Carnegie Mellon

Constant Time Coalescing (Case 4)

m1 0 n+m1+m2 0

m1 0
n 1

n 1
m2 0

m2 0 n+m1+m2 0

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

 Carnegie Mellon

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

heap_start heap_end

 Dummy footer before first header

 Marked as allocated
 Prevents accidental coalescing when freeing first block
 Dummy header after last footer
 Prevents accidental coalescing when freeing final block

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

 Carnegie Mellon

Top-Level Malloc Code

const size_t dsize = 2*sizeof(word_t);

void *mm_malloc(size_t size)

{ round_up(n, m)
size_t asize = round_up(size + dsize, dsize); =
m *((n+m-1)/m)
block_t *block = find_fit(asize);

if (block == NULL)
return NULL;

size_t block_size = get_size(block);

write_header(block, block_size, true);
write_footer(block, block_size, true);

split_block(block, asize);

return header_to_payload(block);
}

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

 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 50

 Carnegie Mellon

Disadvantages of Boundary Tags

 Internal fragmentation
Size a
 Can it be optimized?
 Which blocks need the footer tag? Payload and
 What does that mean? padding

Size a

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

 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

1 word 1 word

Size b1 a = 1: Allocated block Size b0

a = 0: Free block
b = 1: Previous block is allocated
b = 0: Previous block is free
Payload
Unallocated
Size: block size

Optional Payload: application data

padding Size b0

Allocated Free
Block Block
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 52
 Carnegie Mellon

No Boundary Tag for Allocated Blocks

(Case 1)
m1 ?1 m1 ?1
previous
block

block n 11 n 10
being
freed n 10
m2 11 m2 01
next
block

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 53

 Carnegie Mellon

No Boundary Tag for Allocated Blocks

(Case 2)
m1 ?1 m1 ?1
previous
block

block n 11 n+m2 10
being
freed
m2 10
next
block 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 54

 Carnegie Mellon

No Boundary Tag for Allocated Blocks

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

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 4)
m1 ?0 n+m1+m2 ?0
previous
block
m1 ?0
block n 01
being
freed
m2 10
next
block m2 10 n+m1+m2 ?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

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 57

 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 58