Skip to main content

spec_stream_cache/
allocator.rs

1use crate::block::{PhysicalBlock, PhysicalBlockId, DEFAULT_BLOCK_SIZE};
2use crate::error::CacheError;
3use spec_stream_core::TokenId;
4use std::collections::hash_map::DefaultHasher;
5use std::collections::HashMap;
6use std::hash::{Hash, Hasher};
7
8/// Computes an incremental hash over a slice of tokens given an optional parent block hash.
9pub fn compute_block_prefix_hash(parent_hash: Option<u64>, tokens: &[TokenId]) -> u64 {
10    let mut hasher = DefaultHasher::new();
11    parent_hash.hash(&mut hasher);
12    tokens.hash(&mut hasher);
13    hasher.finish()
14}
15
16/// Central allocator managing the physical pool of KV-cache blocks.
17#[derive(Debug)]
18pub struct BlockAllocator {
19    pub block_size: usize,
20    pub total_blocks: usize,
21    pub(crate) blocks: Vec<PhysicalBlock>,
22    pub(crate) free_list: Vec<PhysicalBlockId>,
23    /// Prefix cache: maps a 64-bit sequence hash to an existing shared physical block.
24    pub(crate) prefix_cache: HashMap<u64, PhysicalBlockId>,
25}
26
27impl BlockAllocator {
28    /// Initializes a pool with `total_blocks` of capacity `block_size` tokens each.
29    pub fn new(total_blocks: usize, block_size: usize) -> Self {
30        let mut blocks = Vec::with_capacity(total_blocks);
31        let mut free_list = Vec::with_capacity(total_blocks);
32
33        for id in 0..total_blocks {
34            blocks.push(PhysicalBlock::new(id, block_size));
35            free_list.push(id);
36        }
37
38        Self {
39            block_size,
40            total_blocks,
41            blocks,
42            free_list,
43            prefix_cache: HashMap::new(),
44        }
45    }
46
47    pub fn with_default_block_size(total_blocks: usize) -> Self {
48        Self::new(total_blocks, DEFAULT_BLOCK_SIZE)
49    }
50
51    /// Number of physical blocks currently available for allocation.
52    #[inline]
53    pub fn num_free_blocks(&self) -> usize {
54        self.free_list.len()
55    }
56
57    /// Number of physical blocks currently in use.
58    #[inline]
59    pub fn num_allocated_blocks(&self) -> usize {
60        self.total_blocks - self.free_list.len()
61    }
62
63    /// Number of distinct prefix entries cached.
64    #[inline]
65    pub fn num_prefix_entries(&self) -> usize {
66        self.prefix_cache.len()
67    }
68
69    /// Allocates an empty physical block from the free list.
70    pub fn allocate(&mut self) -> Result<PhysicalBlockId, CacheError> {
71        let block_id = self.free_list.pop().ok_or(CacheError::OutOfMemory {
72            total_blocks: self.total_blocks,
73        })?;
74
75        let block = &mut self.blocks[block_id];
76        block.ref_count = 1;
77        block.num_tokens = 0;
78        block.tokens.clear();
79        block.prefix_hash = None;
80
81        Ok(block_id)
82    }
83
84    /// Duplicates an existing physical block into a new block with ref_count = 1 (Copy-on-Write).
85    pub fn clone_block(
86        &mut self,
87        src_block_id: PhysicalBlockId,
88    ) -> Result<PhysicalBlockId, CacheError> {
89        let src_block = self
90            .blocks
91            .get(src_block_id)
92            .ok_or(CacheError::BlockNotFound(src_block_id))?
93            .clone();
94
95        let new_block_id = self.allocate()?;
96        let dest = &mut self.blocks[new_block_id];
97        dest.num_tokens = src_block.num_tokens;
98        dest.tokens = src_block.tokens.clone();
99        dest.prefix_hash = None; // Reset hash on new uncommitted CoW copy
100        dest.ref_count = 1;
101
102        Ok(new_block_id)
103    }
104
105    /// Increments ref_count for sharing an existing block (e.g. prompt prefix).
106    pub fn inc_ref(&mut self, block_id: PhysicalBlockId) -> Result<(), CacheError> {
107        let block = self
108            .blocks
109            .get_mut(block_id)
110            .ok_or(CacheError::BlockNotFound(block_id))?;
111        block.ref_count += 1;
112        Ok(())
113    }
114
115    /// Decrements ref_count and frees the block if ref_count hits zero.
116    pub fn free(&mut self, block_id: PhysicalBlockId) -> Result<(), CacheError> {
117        let block = self
118            .blocks
119            .get_mut(block_id)
120            .ok_or(CacheError::BlockNotFound(block_id))?;
121
122        if block.ref_count > 0 {
123            block.ref_count -= 1;
124            if block.ref_count == 0 {
125                if let Some(hash) = block.prefix_hash {
126                    self.prefix_cache.remove(&hash);
127                }
128                block.reset();
129                self.free_list.push(block_id);
130            }
131        }
132
133        Ok(())
134    }
135
136    /// Registers a full block into the prefix cache for reuse.
137    pub fn register_prefix(&mut self, hash: u64, block_id: PhysicalBlockId) {
138        if let Some(block) = self.blocks.get_mut(block_id) {
139            block.prefix_hash = Some(hash);
140            self.prefix_cache.insert(hash, block_id);
141        }
142    }
143
144    /// Searches for an existing shared block by prefix hash.
145    pub fn find_prefix(&mut self, hash: u64) -> Option<PhysicalBlockId> {
146        if let Some(&block_id) = self.prefix_cache.get(&hash) {
147            if let Some(block) = self.blocks.get_mut(block_id) {
148                block.ref_count += 1;
149                return Some(block_id);
150            }
151        }
152        None
153    }
154
155    /// Returns a reference to a physical block.
156    pub fn get_block(&self, block_id: PhysicalBlockId) -> Result<&PhysicalBlock, CacheError> {
157        self.blocks
158            .get(block_id)
159            .ok_or(CacheError::BlockNotFound(block_id))
160    }
161
162    /// Returns a mutable reference to a physical block.
163    pub fn get_block_mut(
164        &mut self,
165        block_id: PhysicalBlockId,
166    ) -> Result<&mut PhysicalBlock, CacheError> {
167        self.blocks
168            .get_mut(block_id)
169            .ok_or(CacheError::BlockNotFound(block_id))
170    }
171
172    /// Defragments the free list by sorting block IDs so future allocations favor lowest contiguous physical pages.
173    pub fn defragment_free_list(&mut self) {
174        // Sort descending so pop() returns lowest block index first (0, 1, 2...)
175        self.free_list.sort_unstable_by(|a, b| b.cmp(a));
176    }
177
178    /// Computes pool utilization ratio between 0.0 (empty) and 1.0 (fully saturated).
179    #[inline]
180    pub fn utilization_ratio(&self) -> f32 {
181        self.num_allocated_blocks() as f32 / self.total_blocks.max(1) as f32
182    }
183
184    /// Computes memory fragmentation ratio of the free block list.
185    /// Returns 0.0 when free blocks form a single contiguous block range, higher when scattered.
186    pub fn fragmentation_ratio(&self) -> f32 {
187        if self.free_list.len() <= 1 {
188            return 0.0;
189        }
190
191        let mut sorted = self.free_list.clone();
192        sorted.sort_unstable();
193
194        let mut gaps = 0;
195        for window in sorted.windows(2) {
196            if window[1] != window[0] + 1 {
197                gaps += 1;
198            }
199        }
200
201        gaps as f32 / (self.free_list.len() - 1) as f32
202    }
203}