lewis.moe
Nothing to see here, move along
1use crate::block_io::BlockIo;
2use crate::cache::BlockCache;
3use crate::error::FsError;
4use lancer_core::fs::{BTREE_NODE_SIZE, BTreeNode};
5use zerocopy::{FromBytes, IntoBytes};
6
7const POOL_SIZE: usize = 256;
8const BITMAP_WORDS: usize = POOL_SIZE / 64;
9
10pub type NodeIdx = u16;
11
12const POOL_SENTINEL: u64 = 1u64 << 63;
13
14pub const fn is_pool_ref(physical_addr: u64) -> bool {
15 physical_addr & POOL_SENTINEL != 0
16}
17
18pub const fn pool_idx_to_addr(idx: NodeIdx) -> u64 {
19 POOL_SENTINEL | ((idx as u64) << 4)
20}
21
22pub const fn addr_to_pool_idx(addr: u64) -> NodeIdx {
23 (((addr & lancer_core::fs::ADDR_MASK) & !POOL_SENTINEL) >> 4) as NodeIdx
24}
25
26#[derive(Clone, Copy, PartialEq, Eq)]
27pub enum NodeSlot {
28 Free,
29 Clean(u64),
30 Dirty,
31}
32
33pub struct NodePool {
34 nodes: [BTreeNode; POOL_SIZE],
35 status: [NodeSlot; POOL_SIZE],
36 free_bitmap: [u64; BITMAP_WORDS],
37 free_count: u16,
38}
39
40impl NodePool {
41 pub const fn new() -> Self {
42 Self {
43 nodes: [BTreeNode::ZEROED; POOL_SIZE],
44 status: [NodeSlot::Free; POOL_SIZE],
45 free_bitmap: [u64::MAX; BITMAP_WORDS],
46 free_count: POOL_SIZE as u16,
47 }
48 }
49}
50
51impl Default for NodePool {
52 fn default() -> Self {
53 Self::new()
54 }
55}
56
57impl NodePool {
58 pub fn pool_alloc(&mut self) -> Result<NodeIdx, FsError> {
59 let (word_idx, bit) = self
60 .free_bitmap
61 .iter()
62 .enumerate()
63 .find_map(|(i, &w)| match w {
64 0 => None,
65 _ => Some((i, w.trailing_zeros() as usize)),
66 })
67 .ok_or(FsError::PoolExhausted)?;
68
69 let idx = (word_idx * 64 + bit) as NodeIdx;
70 self.free_bitmap[word_idx] &= !(1u64 << bit);
71 self.free_count -= 1;
72 self.status[idx as usize] = NodeSlot::Dirty;
73 self.nodes[idx as usize] = BTreeNode::EMPTY_LEAF;
74 Ok(idx)
75 }
76
77 pub fn pool_free(&mut self, idx: NodeIdx) {
78 let i = idx as usize;
79 match self.status[i] {
80 NodeSlot::Free => {}
81 _ => {
82 let word_idx = i / 64;
83 let bit = i % 64;
84 self.free_bitmap[word_idx] |= 1u64 << bit;
85 self.free_count += 1;
86 self.status[i] = NodeSlot::Free;
87 }
88 }
89 }
90
91 pub fn pool_load(
92 &mut self,
93 cache: &mut BlockCache,
94 bio: &mut BlockIo,
95 block_num: u64,
96 ) -> Result<NodeIdx, FsError> {
97 let idx = self.pool_alloc()?;
98 let data = cache.cache_read(bio, block_num)?;
99 let node = BTreeNode::read_from_bytes(data.as_slice()).map_err(|_| FsError::CorruptNode)?;
100 self.nodes[idx as usize] = node;
101 self.status[idx as usize] = NodeSlot::Clean(block_num);
102 Ok(idx)
103 }
104
105 pub fn get(&self, idx: NodeIdx) -> &BTreeNode {
106 &self.nodes[idx as usize]
107 }
108
109 pub fn get_mut(&mut self, idx: NodeIdx) -> &mut BTreeNode {
110 self.status[idx as usize] = NodeSlot::Dirty;
111 &mut self.nodes[idx as usize]
112 }
113
114 pub fn is_dirty(&self, idx: NodeIdx) -> bool {
115 self.status[idx as usize] == NodeSlot::Dirty
116 }
117
118 pub fn status(&self, idx: NodeIdx) -> NodeSlot {
119 self.status[idx as usize]
120 }
121
122 pub fn clear_all(&mut self) {
123 self.free_bitmap = [u64::MAX; BITMAP_WORDS];
124 self.free_count = POOL_SIZE as u16;
125 self.status = [NodeSlot::Free; POOL_SIZE];
126 }
127
128 pub fn node_bytes(&self, idx: NodeIdx) -> &[u8; BTREE_NODE_SIZE] {
129 self.nodes[idx as usize].as_bytes().try_into().unwrap()
130 }
131
132 pub fn dirty_indices_by_level(&self) -> ([NodeIdx; POOL_SIZE], usize) {
133 let mut indices = [0u16; POOL_SIZE];
134 let mut count = 0usize;
135
136 (0..POOL_SIZE as NodeIdx).for_each(|idx| {
137 if self.status[idx as usize] == NodeSlot::Dirty {
138 indices[count] = idx;
139 count += 1;
140 }
141 });
142
143 let used = &mut indices[..count];
144 used.sort_unstable_by_key(|&idx| self.nodes[idx as usize].header.level);
145
146 (indices, count)
147 }
148}