use crate::allocator::{compute_block_prefix_hash, BlockAllocator};
use crate::block::PhysicalBlockId;
use crate::error::CacheError;
use spec_stream_core::TokenId;
#[derive(Debug, Clone)]
pub struct BlockTable {
pub physical_blocks: Vec<PhysicalBlockId>,
pub prefix_hashes: Vec<u64>,
pub seq_len: usize,
pub block_size: usize,
}
impl BlockTable {
pub fn new(block_size: usize) -> Self {
Self {
physical_blocks: Vec::new(),
prefix_hashes: Vec::new(),
seq_len: 0,
block_size,
}
}
pub fn append_token(
&mut self,
token_id: TokenId,
allocator: &mut BlockAllocator,
) -> Result<(), CacheError> {
if self.seq_len % self.block_size == 0 {
let block_id = allocator.allocate()?;
self.physical_blocks.push(block_id);
}
let last_idx = self.physical_blocks.len() - 1;
let current_block_id = self.physical_blocks[last_idx];
let block_id_to_use = if allocator.get_block(current_block_id)?.ref_count > 1 {
let new_block_id = allocator.clone_block(current_block_id)?;
allocator.free(current_block_id)?;
self.physical_blocks[last_idx] = new_block_id;
new_block_id
} else {
current_block_id
};
let block = allocator.get_block_mut(block_id_to_use)?;
block.tokens.push(token_id);
block.num_tokens += 1;
self.seq_len += 1;
if block.is_full() {
let parent_hash = self.prefix_hashes.last().copied();
let hash = compute_block_prefix_hash(parent_hash, &block.tokens);
self.prefix_hashes.push(hash);
allocator.register_prefix(hash, block_id_to_use);
}
Ok(())
}
pub fn append_tokens(
&mut self,
mut tokens: &[TokenId],
allocator: &mut BlockAllocator,
) -> Result<(), CacheError> {
while !tokens.is_empty() && self.seq_len % self.block_size != 0 {
self.append_token(tokens[0], allocator)?;
tokens = &tokens[1..];
}
while tokens.len() >= self.block_size {
let chunk = &tokens[..self.block_size];
let parent_hash = self.prefix_hashes.last().copied();
let hash = compute_block_prefix_hash(parent_hash, chunk);
if let Some(shared_block_id) = allocator.find_prefix(hash) {
self.physical_blocks.push(shared_block_id);
self.prefix_hashes.push(hash);
self.seq_len += self.block_size;
} else {
let block_id = allocator.allocate()?;
{
let block = allocator.get_block_mut(block_id)?;
block.tokens.extend_from_slice(chunk);
block.num_tokens = self.block_size;
}
allocator.register_prefix(hash, block_id);
self.physical_blocks.push(block_id);
self.prefix_hashes.push(hash);
self.seq_len += self.block_size;
}
tokens = &tokens[self.block_size..];
}
for &t in tokens {
self.append_token(t, allocator)?;
}
Ok(())
}
pub fn rollback(
&mut self,
valid_token_count: usize,
allocator: &mut BlockAllocator,
) -> Result<usize, CacheError> {
if valid_token_count > self.seq_len {
return Err(CacheError::InvalidRollback {
target_len: valid_token_count,
current_len: self.seq_len,
});
}
let tokens_discarded = self.seq_len - valid_token_count;
if tokens_discarded == 0 {
return Ok(0);
}
let required_blocks = valid_token_count.div_ceil(self.block_size);
while self.physical_blocks.len() > required_blocks {
let block_id = self.physical_blocks.pop().unwrap();
allocator.free(block_id)?;
if self.prefix_hashes.len() > self.physical_blocks.len() {
self.prefix_hashes.pop();
}
}
if let Some(&last_block_id) = self.physical_blocks.last() {
let tokens_in_last =
if valid_token_count % self.block_size == 0 && valid_token_count > 0 {
self.block_size
} else {
valid_token_count % self.block_size
};
if tokens_in_last < self.block_size
&& self.prefix_hashes.len() == self.physical_blocks.len()
{
self.prefix_hashes.pop();
}
let last_idx = self.physical_blocks.len() - 1;
let block_to_truncate = if allocator.get_block(last_block_id)?.ref_count > 1 {
let new_block_id = allocator.clone_block(last_block_id)?;
allocator.free(last_block_id)?;
self.physical_blocks[last_idx] = new_block_id;
new_block_id
} else {
last_block_id
};
let last_block = allocator.get_block_mut(block_to_truncate)?;
last_block.num_tokens = tokens_in_last;
last_block.tokens.truncate(tokens_in_last);
last_block.prefix_hash = None;
}
self.seq_len = valid_token_count;
Ok(tokens_discarded)
}
pub fn translate_logical_offset(
&self,
logical_index: usize,
) -> Result<(PhysicalBlockId, usize), CacheError> {
if logical_index >= self.seq_len {
return Err(CacheError::IndexOutOfBounds {
index: logical_index,
length: self.seq_len,
});
}
let block_idx = logical_index / self.block_size;
let offset = logical_index % self.block_size;
Ok((self.physical_blocks[block_idx], offset))
}
pub fn free_all(&mut self, allocator: &mut BlockAllocator) -> Result<(), CacheError> {
for &block_id in &self.physical_blocks {
allocator.free(block_id)?;
}
self.physical_blocks.clear();
self.prefix_hashes.clear();
self.seq_len = 0;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_prefix_caching_sharing() {
let block_size = 4;
let mut allocator = BlockAllocator::new(10, block_size);
let mut table1 = BlockTable::new(block_size);
let mut table2 = BlockTable::new(block_size);
let system_prompt = vec![101, 102, 103, 104];
table1
.append_tokens(&system_prompt, &mut allocator)
.unwrap();
assert_eq!(allocator.num_free_blocks(), 9);
assert_eq!(allocator.num_prefix_entries(), 1);
table2
.append_tokens(&system_prompt, &mut allocator)
.unwrap();
assert_eq!(allocator.num_free_blocks(), 9); assert_eq!(table1.physical_blocks[0], table2.physical_blocks[0]); assert_eq!(
allocator
.get_block(table1.physical_blocks[0])
.unwrap()
.ref_count,
2
);
table1.free_all(&mut allocator).unwrap();
assert_eq!(allocator.num_free_blocks(), 9);
assert_eq!(
allocator
.get_block(table2.physical_blocks[0])
.unwrap()
.ref_count,
1
);
table2.free_all(&mut allocator).unwrap();
assert_eq!(allocator.num_free_blocks(), 10);
}
#[test]
fn test_copy_on_write() {
let block_size = 4;
let mut allocator = BlockAllocator::new(10, block_size);
let mut table1 = BlockTable::new(block_size);
let mut table2 = BlockTable::new(block_size);
let prompt = vec![1, 2, 3, 4];
table1.append_tokens(&prompt, &mut allocator).unwrap();
table2.append_tokens(&prompt, &mut allocator).unwrap();
let shared_id = table1.physical_blocks[0];
assert_eq!(table2.physical_blocks[0], shared_id);
table2.append_token(99, &mut allocator).unwrap();
assert_eq!(table2.seq_len, 5);
assert_eq!(table1.seq_len, 4);
table2.rollback(3, &mut allocator).unwrap();
assert_ne!(table1.physical_blocks[0], table2.physical_blocks[0]);
let block1 = allocator.get_block(table1.physical_blocks[0]).unwrap();
assert_eq!(block1.num_tokens, 4);
assert_eq!(block1.tokens, vec![1, 2, 3, 4]);
let block2 = allocator.get_block(table2.physical_blocks[0]).unwrap();
assert_eq!(block2.num_tokens, 3);
assert_eq!(block2.tokens, vec![1, 2, 3]);
}
}