FreeToken brings datacenter-scale model serving to your desktop. Run massive models locally, fast and efficiently.
"""Shared pieces of the sliding-window paged pools (DSV4, DSV41).
* ``FreeListAllocator`` -- LIFO page allocator for the window tier (unit = one P-slot page).
* ``CompressStateRing`` -- per-window-page fp32 ``kv | score`` carry ring with a scratch row.
* ``reserved_window_pages`` -- the window working set every such pool keeps for its running requests.
* ``window_state_loc`` -- the derived (never stored) ring slot of a window slot.
* ``WindowTierPagedPool`` -- the pool base: the full-loc -> window-slot mapping over the shared page
table, the page-atomic window allocator behind the CacheManager's ``swa_pool`` duck-type, the
in-place rebuild, and the ABC glue every such pool shares. Subclasses allocate their own tiers
(``_alloc_buffers`` / ``_drop_buffers``), size themselves (the ``kv_cost`` family) and write rows.
``DSV4PagedKVCache`` (the origin of this code) and ``DSV41PagedKVCache`` both build on these, so a
fix to allocation, freeing or the mapping lands in one place.
"""
from __future__ import annotations
import gc
from abc import abstractmethod
import torch
from ..base import BaseKVCachePool
class FreeListAllocator:
"""LIFO free list over ``capacity // page_unit`` units; a unit's base slot is a multiple of
``page_unit`` (the window tier's ``G*P`` page-base invariant)."""
def __init__(self, capacity: int, device: torch.device, page_unit: int = 1) -> None:
assert capacity % page_unit == 0, f"capacity {capacity} must be a multiple of page_unit {page_unit}"
self._capacity = int(capacity)
self._page_unit = int(page_unit)
self._device = device
self._free = self._fresh_free()
def _fresh_free(self) -> torch.Tensor:
n_units = self._capacity // self._page_unit
return torch.arange(n_units, dtype=torch.int64, device=self._device) * self._page_unit
def alloc(self, n_units: int) -> torch.Tensor:
"""Return ``n_units`` unit base slots (each a multiple of ``page_unit``)."""
if n_units < 0:
raise ValueError(f"n_units must be non-negative, got {n_units}")
if n_units > self._free.numel():
raise RuntimeError(
f"FreeListAllocator out of slots: requested {n_units} units, "
f"have {self._free.numel()} (capacity {self._capacity}, unit {self._page_unit})"
)
if n_units == 0:
return self._free[:0].clone()
taken = self._free[-n_units:].clone()
self._free = self._free[:-n_units]
return taken
def free(self, units: torch.Tensor) -> None:
"""Return previously-allocated unit base slots to the pool (LIFO recycle)."""
if units.numel() == 0:
return
units = units.to(device=self._device, dtype=torch.int64).reshape(-1)
self._free = torch.cat([self._free, units])
def available(self) -> int:
"""Free capacity in slots (units * page_unit)."""
return int(self._free.numel()) * self._page_unit
@property
def capacity(self) -> int:
return self._capacity
def reset(self) -> None:
self._free = self._fresh_free()
class CompressStateRing:
"""Per-layer fp32 compress-state ring: ``[n_slots + 1, 2*(1+overlap)*head_dim]``.
Last row (index ``-1``) is a permanent scratch slot, re-cleared on every write. Last dim is
split ``kv | score``; ``set`` writes both halves.
"""
def __init__(
self,
n_slots: int,
ring_size: int,
overlap: bool,
head_dim: int,
device: torch.device,
dtype: torch.dtype = torch.float32,
) -> None:
self.ring_size = ring_size
self.head_dim = head_dim
self._item_size = (1 + int(overlap)) * head_dim # width of kv (== width of score)
last_dim = 2 * self._item_size
self.buffer = torch.zeros((n_slots + 1, last_dim), dtype=dtype, device=device)
self.n_slots = n_slots
self._clear_scratch()
def _clear_scratch(self) -> None:
self.buffer[-1, : self._item_size].zero_()
self.buffer[-1, self._item_size :].fill_(float("-inf"))
@property
def item_size(self) -> int:
return self._item_size
def get(self, state_loc: torch.Tensor) -> torch.Tensor:
"""Gather ``kv_score`` rows at ``state_loc`` (``-1`` -> scratch row)."""
return self.buffer[state_loc]
def set(self, state_loc: torch.Tensor, kv_score: torch.Tensor) -> None:
"""Scatter ``kv_score`` rows to ``state_loc`` then re-clear the scratch row."""
self.buffer[state_loc] = kv_score
self._clear_scratch()
def get_blocks(self, page_base: torch.Tensor) -> torch.Tensor:
"""Batched per-row carry-block read: ``page_base`` ``[B]`` (``(window_slot // P) * ring_size``)
-> ``[B, ring_size, 2*item]``. Distinct pages -> disjoint blocks."""
rows = page_base[:, None] + torch.arange(self.ring_size, device=page_base.device)
return self.buffer[rows]
def set_blocks(self, page_base: torch.Tensor, blocks: torch.Tensor) -> None:
"""Batched per-row carry-block write of ``[B, ring_size, 2*item]``; re-clears scratch."""
rows = page_base[:, None] + torch.arange(self.ring_size, device=page_base.device)
self.buffer[rows] = blocks
self._clear_scratch()
def reserved_window_pages(max_running_req: int, radix: bool) -> int:
"""Window pages the sliding pool must always keep for the concurrent working set: each
running request's decode transients (2 per req + dummy) plus, in radix mode, PER concurrent
request one locked live-tail page AND a retained (soft-pinned) prompt-end window -- the
window is 2 pages here because the retention gap page-aligns to a whole extra page at
P == window."""
return 2 * (max_running_req + 1) + (3 * max_running_req if radix else 0) + 1
def window_state_loc(window_slot: torch.Tensor, ring_size: int, P: int) -> torch.Tensor:
"""Ring slot of a window slot: ``(ws // P) * ring_size + ws % ring_size``; ``-1`` stays ``-1``
(the scratch row). ``ring_size | P`` keeps distinct pages on disjoint blocks."""
pages = torch.div(window_slot, P, rounding_mode="floor")
loc = pages * ring_size + (window_slot % ring_size)
return torch.where(window_slot < 0, torch.full_like(loc, -1), loc)
class WindowTierPagedPool(BaseKVCachePool):
"""A paged KV pool whose window tier is page-bound to the shared full-token page table.
Subclasses set ``P`` (the window page), ``_device``, ``_dtype`` and ``sizes`` (with
``full_token`` and ``n_win_slots``) before calling ``_alloc_buffers``, which must create
``self.full_to_window`` (``[full_token + 1]`` int64, ``-1`` = unmapped, the trailing row a
permanent ``-1`` sentinel so a gather at ``-1`` is safe) and ``self.window_pool`` (one tensor
per layer, indexed by window slot). Scatter paths must never see a negative slot.
ShadowRadix layering: the shared page table is the virtual full-token coordinate; the pool
projects it into physical tiers. The window tier is the managed "second currency" -- token-face
signatures (what the generic CacheManager speaks), PAGE-ATOMIC internals (window pages are 1:1
page-bound to full pages; the per-page state ring requires it). ``alloc_swa`` receives whole
ascending pages and free paths are page-complete by construction -- asserted here, not assumed.
"""
swa_paged = True
# the tier buffers are bound into per-forward model scratch, invalid after a realloc
needs_rebind_on_rebuild = True
P: int
_device: torch.device
_dtype: torch.dtype
sizes: object
full_to_window: torch.Tensor
window_pool: list
# ----- tiers (subclass) -----
@abstractmethod
def _alloc_buffers(self) -> None: ...
@abstractmethod
def _drop_buffers(self) -> None:
"""Release every tier buffer before a rebuild reallocates them."""
# ----- full-loc translation (gather-only -1 safety; see the class docstring) -----
def translate_full_to_window(self, full_locs: torch.Tensor) -> torch.Tensor:
# int64 gather indices: the shared page_table stores full locs as int32
return self.full_to_window[full_locs.to(dtype=torch.int64)]
@staticmethod
def cmp_rows(full_locs: torch.Tensor, ratio: int) -> torch.Tensor:
"""The compressed row of a full loc: ``full_loc // ratio`` (negative stays negative)."""
return torch.div(full_locs.to(dtype=torch.int64), ratio, rounding_mode="floor")
def bind_window_pages(self, full_page_base: int, window_page_base: int) -> None:
assert full_page_base % self.P == 0 and window_page_base % self.P == 0
self.full_to_window[full_page_base : full_page_base + self.P] = torch.arange(
window_page_base, window_page_base + self.P, dtype=torch.int64, device=self._device
)
def unbind_window_pages(self, full_locs: torch.Tensor) -> None:
self.full_to_window[full_locs[full_locs >= 0]] = -1
@staticmethod
def state_loc(window_slot: torch.Tensor, ring_size: int, P: int) -> torch.Tensor:
return window_state_loc(window_slot, ring_size, P)
# ----- generic swa_pool duck-type (the CacheManager plug-in surface) -----
@property
def sliding_window_size(self) -> int:
return self.P
@property
def prefill_chunk_budget(self) -> int:
return self._chunk_budget
def _init_paged_state(self, max_running_req: int, radix: bool) -> None:
"""Build the pool-owned window free list + the tail dummy binding. The LAST full page and
LAST window page are the reserved dummy region: page_table's dummy row points at
``full_token - P`` (the generic ``fill_(num_tokens)`` convention), permanently bound so
graph-padded rows scatter to a real slot."""
P = self.P
self._paged_params = (int(max_running_req), bool(radix))
self.full_to_window.fill_(-1)
self._win_alloc = FreeListAllocator(self.sizes.n_win_slots - P, self._device, page_unit=P)
self.bind_window_pages(self.sizes.full_token - P, self.sizes.n_win_slots - P)
# Chunk cap: a batched prefill holds the whole chunk's window live at once (sliding frees
# only between chunks; peak ~2x the chunk), so reserve the concurrent working set and
# halve the rest.
n_win_pages = (self.sizes.n_win_slots // P) - 1
reserved = reserved_window_pages(max_running_req, radix)
self._chunk_budget = max(P, (n_win_pages - reserved) // 2 * P)
@property
def window_pages(self) -> int:
return self.sizes.n_win_pages - 1
@property
def swa_num_tokens(self) -> int:
# Allocatable window slots + 1: the generic capacity convention reserves slot 0 as a
# sentinel (cap == swa_num_tokens - 1); here the reserved unit is the tail dummy page,
# already excluded from the free list, so +1 re-encodes the same cap.
return (self.sizes.n_win_slots - self.P) + 1
def swa_available_size(self) -> int:
return int(self._win_alloc.available())
def alloc_swa(self, full_indices: torch.Tensor) -> None:
"""Bind one window page per incoming FULL page. ``full_indices`` must be whole ascending
pages (the ``_page_to_token`` expansion); the in-page offsets are preserved
(``window_slot = wbase + pos % P``), which the state ring's page-block layout requires."""
n = int(full_indices.numel())
if n == 0:
return
P = self.P
assert n % P == 0, f"alloc_swa needs whole pages, got {n} slots"
fi = full_indices.to(device=self._device, dtype=torch.int64).view(-1, P)
fbases = fi[:, 0]
assert torch.equal(fi, fbases[:, None] + torch.arange(P, device=self._device)), "alloc_swa pages must be contiguous ascending"
wbases = self._win_alloc.alloc(fbases.numel()) # raises when exhausted (caller gated)
offsets = torch.arange(P, dtype=torch.int64, device=self._device)
self.full_to_window[(fbases[:, None] + offsets).flatten()] = (wbases[:, None] + offsets).flatten()
def free_swa(self, full_indices: torch.Tensor) -> None:
"""Return the window pages backing these FULL locs and unbind the mapping. Page-atomic: the
incoming locs must cover each touched page completely (guaranteed by the padded finish
tails / aligned frontiers / page-aligned tree values). Idempotent over already unbound
(slid / tombstoned) pages."""
if full_indices.numel() == 0:
return
P = self.P
fi = full_indices.to(device=self._device, dtype=torch.int64)
fi = fi[fi >= 0]
if fi.numel() == 0:
return
fbases, counts = torch.unique(torch.div(fi, P, rounding_mode="floor") * P, return_counts=True)
assert bool((counts == P).all()), f"free_swa got partial pages (counts {counts[counts != P].tolist()[:4]})"
ws = self.full_to_window[fbases]
live = ws[ws >= 0]
offsets = torch.arange(P, dtype=torch.int64, device=self._device)
self.full_to_window[(fbases[:, None] + offsets).flatten()] = -1
if live.numel():
self._win_alloc.free(torch.div(live, P, rounding_mode="floor") * P)
def translate_loc_from_full_to_swa(self, kv_indices: torch.Tensor) -> torch.Tensor:
return self.full_to_window[kv_indices.to(dtype=torch.int64)]
# ----- rebuild / page table -----
def rebuild(self, sizes) -> None:
"""In-place resize to ``sizes`` (identity-preserving; free-before-alloc). The manager's
tree / page bookkeeping reset is the scheduler's generic cache_manager.rebuild; the engine
re-attaches the page table via attach_page_table afterwards."""
assert self._paged_params is not None, "rebuild before _init_paged_state"
self.sizes = sizes
self._drop_buffers()
self.full_to_window = None # type: ignore[assignment]
gc.collect()
if torch.cuda.is_available():
torch.cuda.empty_cache()
self._alloc_buffers()
self._init_paged_state(*self._paged_params)
def attach_page_table(self, page_table: torch.Tensor) -> None:
# the model reads full locs through full_loc_map; under the shared route that IS the page table
self.full_loc_map = page_table
# ----- BaseKVCachePool glue: the window tier is the K == V latent cache -----
def k_cache(self, index: int) -> torch.Tensor:
return self.window_pool[index]
def v_cache(self, index: int) -> torch.Tensor:
return self.window_pool[index]
def store_kv(self, k, v, out_loc, layer_id) -> None:
self.store_window(k, layer_id, out_loc)
@abstractmethod
def store_window(self, kv: torch.Tensor, layer_id: int, window_slot: torch.Tensor) -> None: ...
@property
def device(self) -> torch.device:
return self._device
@property
def dtype(self) -> torch.dtype:
return self._dtype
__all__ = [
"FreeListAllocator",
"CompressStateRing",
"WindowTierPagedPool",
"reserved_window_pages",
"window_state_loc",
]