spec_stream_cache/
allocator.rs1use 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
8pub 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#[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 pub(crate) prefix_cache: HashMap<u64, PhysicalBlockId>,
25}
26
27impl BlockAllocator {
28 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 #[inline]
53 pub fn num_free_blocks(&self) -> usize {
54 self.free_list.len()
55 }
56
57 #[inline]
59 pub fn num_allocated_blocks(&self) -> usize {
60 self.total_blocks - self.free_list.len()
61 }
62
63 #[inline]
65 pub fn num_prefix_entries(&self) -> usize {
66 self.prefix_cache.len()
67 }
68
69 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 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; dest.ref_count = 1;
101
102 Ok(new_block_id)
103 }
104
105 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 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 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 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 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 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 pub fn defragment_free_list(&mut self) {
174 self.free_list.sort_unstable_by(|a, b| b.cmp(a));
176 }
177
178 #[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 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}