Carnegie Mellon
Implicit List: Freeing a Block Simplest implementation:
Need only clear the “allocated” flag
void free_block(ptr p) { *p = *p & -2 }
But can lead to “false fragmentation”
4
4
4
2
2
free(p)
malloc(5)
p
4
4
4
2
2
Oops!
There is enough free space, but the allocator won’t be able to find it
1
Carnegie Mellon
Implicit List: Coalescing
Join (coalesce) with next/previous blocks, if they are free
Coalescing with next block
4
4
4
2
2
free(p)
p
logically gone
4
4
6
2
2
void free_block(ptr p) {
*p = *p & -2;
// clear allocated flag
// find next block
// add to this block if
// not allocated
}
*p = *p + *next;
next = p + *p;
if ((*next & 1) == 0)
But how do we coalesce with previous block?
2
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!
4
4
4
4
6
6
4
4
Size
a
Payload and padding
Size
a
Header
Format of allocated and free blocks
Boundary tag (footer)
a = 1: Allocated block a = 0: Free block
Size: Total block size
Payload: Application data (allocated blocks only)
3
Carnegie Mellon
Constant Time Coalescing
Case 1 Case 2 Case 3 Case 4
Allocated
Allocated
Allocated
Free
Free
Allocated
Free
Free
Block being freed
4
Carnegie Mellon
Constant Time Coalescing (Case 1)
m1
1
m1
1
n
1
n
1
m2
1
m2
1
m1
1
m1
1
n
0
n
0
m2
1
m2
1
5
Carnegie Mellon
Constant Time Coalescing (Case 2)
m1
1
m1
1
n
1
n
1
m2
0
m2
0
m1
1
m1
1
n+m2
0
n+m2
0
6
Carnegie Mellon
Constant Time Coalescing (Case 3)
m1
0
m1
0
n
1
n
1
m2
1
m2
1
n+m1
0
n+m1
0
m2
1
m2
1
7
Carnegie Mellon
Constant Time Coalescing (Case 4)
m1
0
m1
0
n
1
n
1
m2
0
m2
0
n+m1+m2
0
n+m1+m2
0
8