[SOLVED] CS Carnegie Mellon

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 wont 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