Skip to question
ASIC.FYI

Q212FreeSystemVerilog

Build a first-fit range allocator

Difficulty
Medium
Topic
Memory Systems
Language
SV
Interview prompt

Question

Maintain inclusive free address ranges. Allocate the first range large enough for a request, and return freed ranges while merging every overlap or adjacency.

Starting point

Question code

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);
endclass
Reviewed example

Trace one case

Input
free=[[0x1000,0x10FF]]; alloc(0x20, addr); dealloc(addr=0x1000,size=0x20)
Expected output
allocation base=0x1000; final free list=[[0x1000,0x10FF]]

Allocation preserves suffix [0x1020,0x10FF], and the exact deallocation coalesces the returned prefix back into one maximal range.

What to cover

Requirements

  1. Reject zero-sized construction, allocation, and deallocation.
  2. Return the first sufficient range and its lowest address.
  3. Remove exact fits and preserve the remainder of partial fits.
  4. Keep the free list sorted, disjoint, and maximally coalesced after deallocation.
Continue practicing
Q263 · Memory SystemsMake the allocator thread-safeQ276 · Memory SystemsRandomize free-range allocationQ262 · Memory SystemsAllocate on a power-of-two boundary