DescriptionQ212
Q212ArchASIC interview problem
Build a first-fit range allocator
TechniquesAllocatorIntervalsCoalescing
DifficultyMedium
TopicMemory Systems
LanguageSystemVerilog
Requirements4 checkpoints
01
Problem
Maintain inclusive free address ranges. Allocate the first range large enough for a request, and return freed ranges while merging every overlap or adjacency.
Class declarationSystemVerilog
class RangeAllocator;
function new(int unsigned base, int unsigned size);
function bit alloc(int unsigned size, output int unsigned addr);
function void dealloc(int unsigned addr, int unsigned size);
endclassExample input and output
Use this case to check your interpretationInput
free=[[0x1000,0x10FF]]; alloc(0x20, addr); dealloc(addr=0x1000,size=0x20)Output
allocation base=0x1000; final free list=[[0x1000,0x10FF]]Explanation
Allocation preserves suffix [0x1020,0x10FF], and the exact deallocation coalesces the returned prefix back into one maximal range.
02
Requirements (4)
- Reject zero-sized construction, allocation, and deallocation.
- Return the first sufficient range and its lowest address.
- Remove exact fits and preserve the remainder of partial fits.
- Keep the free list sorted, disjoint, and maximally coalesced after deallocation.