Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Slab slots: reuse fixed-size pages with generation checks

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A slab cache divides each page into a fixed number of equal-shaped object slots. Its free-slot stack stores page and slot coordinates. Allocation pops one coordinate, writes the incident record, marks it live, and returns a handle containing page, slot, and generation. If the stack is empty, the cache adds one page and its slots. Release clears the value, increments that slot's generation, and pushes its coordinate for reuse. A stale handle cannot read a replacement record at the same coordinate because its generation no longer matches. This is a same-shaped in-memory object model; it does not account for byte alignment, page headers, physical page allocation, or object finalizers. Pages stay allocated even when every slot becomes free.

Operational case

With three slots per page, four incident records force a second page. The handle for incident 19 is released, then incident 29 takes the freed coordinate. The replacement's page and slot match the old handle, but its generation differs, so reading through the old handle raises an error. A direct page/slot pointer without a generation field would expose the new record under the old identity. The model also rejects a second release of the old handle. It does not shrink the cache when activity falls; retaining empty pages makes reuse cheap, but can keep memory committed after a brief peak.

Working Python program

python
class IncidentSlabCache:
    def __init__(self, slots_per_page=3):
        if slots_per_page < 1:
            raise ValueError("page must hold at least one slot")
        self.slots_per_page = slots_per_page
        self.pages = []
        self.generations = []
        self.free_slots = []
        self.live = set()

    def _add_page(self):
        page_id = len(self.pages)
        self.pages.append([None] * self.slots_per_page)
        self.generations.append([0] * self.slots_per_page)
        self.free_slots.extend((page_id, slot) for slot in reversed(range(self.slots_per_page)))

    def allocate(self, incident):
        if not self.free_slots:
            self._add_page()
        page, slot = self.free_slots.pop()
        self.pages[page][slot] = incident
        self.live.add((page, slot))
        return page, slot, self.generations[page][slot]

    def _validate(self, handle):
        page, slot, generation = handle
        if ((page, slot) not in self.live or
                self.generations[page][slot] != generation):
            raise KeyError("stale or released incident handle")
        return page, slot

    def get(self, handle):
        page, slot = self._validate(handle)
        return self.pages[page][slot]

    def release(self, handle):
        page, slot = self._validate(handle)
        self.live.remove((page, slot))
        self.pages[page][slot] = None
        self.generations[page][slot] += 1
        self.free_slots.append((page, slot))


cache = IncidentSlabCache(slots_per_page=3)
handles = [cache.allocate(f"incident-{number}") for number in (47, 19, 61, 83)]
cache.release(handles[1])
replacement = cache.allocate("incident-29")
try:
    cache.get(handles[1])
except KeyError:
    stale = True
print("pages=", len(cache.pages), " reused-slot=", replacement[:2] == handles[1][:2],
      " stale=", stale, sep="")

Output

Output
pages=2 reused-slot=True stale=True

Time, space, and tradeoff

Popping or returning one free slot and checking a generation use expected O(1) time under Python set membership. Adding a page initializes S slots and therefore costs O(S) time and O(S) space for S slots per page. For P pages, value slots, generation cells, and free coordinates together use O(P times S) space; live ownership adds O(L) entries for L active records. Lookup is expected O(1). A page is not moved or compacted, and this example has no concurrent access protection. If a generation counter eventually wraps in a fixed-width implementation, old handles could become valid again; Python integers in this model do not wrap automatically.

Common Mistakes

  • Do not identify a record solely by page and slot after that slot is reused.
  • Do not decrement a generation on release; monotone generations reject old handles.
  • Do not claim that empty pages are returned to the system in this model.
  • Do not apply fixed-size slot cost claims to arbitrary-sized objects.

Connected lessons

Compare ownership and reuse with Checkpoint arenas: reclaim a region by lifetime, Free spans: first-fit allocation and adjacent coalescing, Buddy blocks: split powers of two and reunite partners, then run the storage audit and contract quiz.

data structures
range-query-structures
Storage details