[SOLVED] CS Carnegie Mellon

Carnegie Mellon
Method 1: Implicit List
For each block we need both size and allocation status
Could store this information in two words: wasteful!
Standard trick
If blocks are aligned, some low-order address bits are always 0
Instead of storing an always-0 bit, use it as a allocated/free flag When reading size word, must mask out this bit
1 word
Size
a
Payload
Optional padding
Format of allocated and free blocks
a = 1: Allocated block a = 0: Free block
Size: block size
Payload: application data (allocated blocks only)
1

Carnegie Mellon
Header Example
Size = 16, allocation status = 1
16 = 00010000
size
0
0
0
1
0
0
0
1
Need to zero out the LSB to get the size -2 = 11111110
Least significant bit is 0
Bitwise AND with -2 sets LSB to 0
allocation
2

Carnegie Mellon
Start of
Detailed Implicit Free List Example
Unused
heap
8/0
16/1
32/0
16/1
Double-word aligned
Allocated blocks: shaded
Free blocks: unshaded
Headers: labeled with size in bytes/allocated bit
3