As an exercise I've implemented malloc and free in Python as a first fit free list as described here. This tracks which blocks are free in a doubly linked list that is sorted by the address of the first byte of the block. It also keeps track of the size of each allocated block in a dictionary. The time complexity is \$O(N)\$ for both malloc and free, where \$N\$ is the number of free blocks.
from typing import Optional
class Block():
def __init__(self, size: int, address: int):
self.address: int = address
self.size = size
self.prev: Optional[Block] = None
self.next: Optional[Block] = None
def __str__(self):
return f"(start {self.address}, size {self.size})"
def __repr__(self):
return f"(start {self.address}, size {self.size})"
class Heap():
def __init__(self, size: int):
self.size = size
self.head: Optional[Block] = Block(size, 0)
self.allocation_headers: dict[int, int] = {}
def num_free_blocks(self) -> int:
block = self.head
total = 0
while block:
total += 1
block = block.next
return total
def free_size(self) -> int:
block = self.head
total = 0
while block:
total += block.size
block = block.next
return total
def total_size(self) -> int:
free = self.free_size()
allocated = sum(self.allocation_headers.values())
return allocated + free
def malloc(self, size: int) -> int:
if size <= 0:
raise Exception
# Sort the linked list by address
block = self.head
while block:
if block.size >= size:
self.allocation_headers[block.address] = size
return_address = block.address
if block.size == size: # remove the block
if block.prev:
block.prev.next = block.next
if block.next:
block.next.prev = block.prev
if self.head == block:
self.head = block.next
else: # make the block smaller
block.address += size
block.size -= size
return return_address
block = block.next
raise Exception
def free(self, ptr: int):
"""
Take an address pointer ptr and free it.
All we need to do to free is to add an element to the free list.
"""
free_size = self.allocation_headers[ptr]
del self.allocation_headers[ptr]
prev = None
block = self.head
while block and block.address < ptr:
prev = block
block = block.next
new_block = Block(free_size, ptr)
if not self.head:
self.head = new_block
if prev:
prev.next = new_block
new_block.prev = prev
if block:
block.prev = new_block
new_block.next = block
if self.head == block:
self.head = new_block
# coalesce next
if new_block.next and new_block.next.address == (new_block.address +
new_block.size):
new_block.size += new_block.next.size
new_block.next = new_block.next.next
if new_block.next:
new_block.next.prev = new_block
# coalesce prev
if new_block.prev and new_block.address == (new_block.prev.address +
new_block.prev.size):
new_block.prev.size += new_block.size
new_block.prev.next = new_block.next
if new_block.prev.next:
new_block.prev.next.prev = new_block.prev
Example usage:
def test_case_1():
heap = Heap(1000)
assert (heap.total_size() == 1000)
assert (heap.num_free_blocks() == 1)
assert (heap.free_size() == 1000)
a = heap.malloc(100)
assert (heap.num_free_blocks() == 1)
assert (heap.free_size() == 900)
assert (a == 0)
b = heap.malloc(500)
assert (heap.num_free_blocks() == 1)
assert (heap.free_size() == 400)
assert (b == 100)
try:
heap.malloc(950)
except:
pass
heap.free(b)
assert (heap.num_free_blocks() == 1)
assert (heap.free_size() == 900)
heap.free(a)
try:
heap.free(a)
except:
pass
heap.malloc(950)
print("Test case 1 succeeded!")
I believe this implementation is correct as I've fuzzed it with hundreds of millions of random inputs and all of these conditions were maintained:
def perform_checks(self):
forward_blocks: list[Block] = []
forward_addresses: list[int] = []
reverse_blocks: list[Block] = []
reverse_addresses: list[int] = []
tail = None
block = self.head
forward_length = 0
forward_free = 0
last_address = -1
while block: # zoom to the end
assert (block.address > last_address)
forward_addresses.append(block.address)
forward_blocks.append(block)
forward_length += 1
forward_free += block.size
if not block.next:
tail = block
last_address = block.address
block = block.next
reverse_length = 0
reverse_free = 0
last_address = 1000000000
if self.head is not None:
assert (tail is not None)
while tail:
assert (tail.address < last_address)
reverse_blocks.append(tail)
reverse_addresses.append(tail.address)
reverse_length += 1
reverse_free += tail.size
last_address = tail.address
tail = tail.prev
assert (
forward_length == reverse_length
), f"Forward length of {forward_length}, Reverse length of {reverse_length}"
reverse_blocks.reverse()
assert (forward_blocks == reverse_blocks)
assert (forward_free == reverse_free)
assert (self.total_size() == self.size
), f"Total size {self.total_size()}, size {self.size}"
assert (forward_length == len(forward_addresses))
However, I would like suggestions on improving the simplicity of the code.
The time complexity and block fragmentation could be improved by switching to a best-fit red/black tree, but let's ignore that. Assuming a flat left-to-right heap, how can we improve this and maintain the \$O(N)\$ time complexity? Could the code be dramatically cleaned up by using a Python built-in data structure?
