Nothing to see here, move along meow
1use crate::block_io::BlockIo;
2use crate::cache::BlockCache;
3use crate::error::FsError;
4use crate::freemap::FreemapAllocator;
5use lancer_core::fs::{BTreeNode, BlockRef, FREEMAP_BITS_PER_LEAF};
6
7const SCRATCH_WORDS: usize = 16384;
8const SCRATCH_BITS: u64 = SCRATCH_WORDS as u64 * 64;
9const WALK_STACK_DEPTH: usize = 8;
10const MAX_ROOTS: usize = 20;
11
12pub const fn scratch_coverage() -> u64 {
13 SCRATCH_BITS
14}
15
16struct ScratchBitmap {
17 bits: [u64; SCRATCH_WORDS],
18 base_block: u64,
19 coverage: u64,
20}
21
22impl ScratchBitmap {
23 const fn new() -> Self {
24 Self {
25 bits: [0u64; SCRATCH_WORDS],
26 base_block: 0,
27 coverage: SCRATCH_BITS,
28 }
29 }
30
31 fn clear(&mut self) {
32 self.bits.iter_mut().for_each(|w| *w = 0);
33 }
34
35 fn mark(&mut self, block: u64) {
36 let relative = block.saturating_sub(self.base_block);
37 if relative < self.coverage {
38 let word = relative as usize / 64;
39 let bit = relative as usize % 64;
40 self.bits[word] |= 1u64 << bit;
41 }
42 }
43
44 fn is_marked(&self, block: u64) -> bool {
45 let relative = block.saturating_sub(self.base_block);
46 match relative < self.coverage {
47 true => {
48 let word = relative as usize / 64;
49 let bit = relative as usize % 64;
50 (self.bits[word] >> bit) & 1 != 0
51 }
52 false => false,
53 }
54 }
55
56 fn covers(&self, block: u64) -> bool {
57 let relative = block.saturating_sub(self.base_block);
58 relative < self.coverage
59 }
60}
61
62#[derive(Clone, Copy, PartialEq, Eq)]
63pub enum BulkfreePhase {
64 Idle,
65 Marking,
66 Sweeping,
67 Done,
68}
69
70pub struct BulkfreeState {
71 phase: BulkfreePhase,
72 scratch: ScratchBitmap,
73 stack: [(u64, u8); WALK_STACK_DEPTH],
74 stack_depth: u8,
75 resume_key: u64,
76 alloc_fence: u64,
77 pending_roots: [BlockRef; MAX_ROOTS],
78 pending_root_count: u8,
79 current_root_idx: u8,
80}
81
82impl BulkfreeState {
83 pub const fn new() -> Self {
84 Self {
85 phase: BulkfreePhase::Idle,
86 scratch: ScratchBitmap::new(),
87 stack: [(0, 0); WALK_STACK_DEPTH],
88 stack_depth: 0,
89 resume_key: 0,
90 alloc_fence: 0,
91 pending_roots: [BlockRef::ZERO; MAX_ROOTS],
92 pending_root_count: 0,
93 current_root_idx: 0,
94 }
95 }
96}
97
98impl Default for BulkfreeState {
99 fn default() -> Self {
100 Self::new()
101 }
102}
103
104impl BulkfreeState {
105 pub fn start(&mut self, roots: &[BlockRef], current_txn: u64, base_block: u64) {
106 self.scratch.clear();
107 self.scratch.base_block = base_block;
108 self.phase = BulkfreePhase::Marking;
109 self.stack_depth = 0;
110 self.resume_key = 0;
111 self.alloc_fence = current_txn;
112 self.current_root_idx = 0;
113
114 let count = roots.len().min(MAX_ROOTS);
115 self.pending_root_count = count as u8;
116 roots.iter().enumerate().take(count).for_each(|(i, r)| {
117 self.pending_roots[i] = *r;
118 });
119
120 self.begin_next_root();
121 }
122
123 fn begin_next_root(&mut self) {
124 let found = (self.current_root_idx..self.pending_root_count)
125 .find(|&i| !self.pending_roots[i as usize].is_null());
126
127 match found {
128 Some(idx) => {
129 self.current_root_idx = idx + 1;
130 let root_block = crate::blockref_block_num(&self.pending_roots[idx as usize]);
131 self.scratch.mark(root_block);
132 self.stack[0] = (root_block, 0);
133 self.stack_depth = 1;
134 }
135 None => {
136 self.phase = BulkfreePhase::Sweeping;
137 }
138 }
139 }
140
141 pub fn mark_step(
142 &mut self,
143 cache: &mut BlockCache,
144 bio: &mut BlockIo,
145 ) -> Result<bool, FsError> {
146 match self.phase {
147 BulkfreePhase::Marking => {}
148 _ => return Ok(true),
149 }
150
151 if self.stack_depth == 0 {
152 self.begin_next_root();
153 match self.phase {
154 BulkfreePhase::Sweeping => {
155 self.resume_key = 0;
156 return Ok(true);
157 }
158 _ => return Ok(false),
159 }
160 }
161
162 let depth = (self.stack_depth - 1) as usize;
163 let (node_block, child_idx) = self.stack[depth];
164
165 let node_data = cache.cache_read(bio, node_block)?;
166 let node = unsafe { &*(node_data.as_ptr() as *const BTreeNode) };
167
168 match node.is_valid() {
169 true => {}
170 false => return Err(FsError::CorruptNode),
171 }
172
173 match node.is_leaf() {
174 true => {
175 node.active_entries().iter().for_each(|entry| {
176 let block = crate::blockref_block_num(entry);
177 match block {
178 0 => {}
179 _ => self.scratch.mark(block),
180 }
181 });
182 self.stack_depth -= 1;
183 Ok(false)
184 }
185 false => {
186 let count = node.entry_count();
187 match (child_idx as usize) < count {
188 true => {
189 let entry = &node.entries[child_idx as usize];
190 self.stack[depth].1 = child_idx + 1;
191
192 let child_block = crate::blockref_block_num(entry);
193 match child_block {
194 0 => Ok(false),
195 _ => {
196 self.scratch.mark(child_block);
197 match (self.stack_depth as usize) < WALK_STACK_DEPTH {
198 true => {
199 self.stack[self.stack_depth as usize] = (child_block, 0);
200 self.stack_depth += 1;
201 Ok(false)
202 }
203 false => Err(FsError::CorruptNode),
204 }
205 }
206 }
207 }
208 false => {
209 self.stack_depth -= 1;
210 Ok(false)
211 }
212 }
213 }
214 }
215 }
216
217 pub fn sweep_step(
218 &mut self,
219 cache: &mut BlockCache,
220 bio: &mut BlockIo,
221 freemap: &mut FreemapAllocator,
222 ) -> Result<bool, FsError> {
223 match self.phase {
224 BulkfreePhase::Sweeping => {}
225 _ => return Ok(true),
226 }
227
228 let total_data = freemap.total_data_blocks();
229 let data_start = freemap.data_region_start();
230
231 if self.resume_key >= total_data {
232 self.phase = BulkfreePhase::Done;
233 return Ok(true);
234 }
235
236 let leaf_key = self.resume_key / FREEMAP_BITS_PER_LEAF as u64;
237 let leaf_base = leaf_key * FREEMAP_BITS_PER_LEAF as u64;
238 let bits_in_leaf = (total_data.saturating_sub(leaf_base)).min(FREEMAP_BITS_PER_LEAF as u64);
239
240 (0..bits_in_leaf).try_for_each(|bit| {
241 let absolute_block = data_start + leaf_base + bit;
242 match self.scratch.covers(absolute_block) && !self.scratch.is_marked(absolute_block) {
243 true => match freemap.free_blocks(cache, bio, absolute_block, 1) {
244 Ok(()) | Err(FsError::DoubleFree) => Ok(()),
245 Err(e) => Err(e),
246 },
247 false => Ok(()),
248 }
249 })?;
250
251 self.resume_key = leaf_base + FREEMAP_BITS_PER_LEAF as u64;
252 Ok(false)
253 }
254
255 pub fn fence_allocation(&mut self, block: u64) {
256 match self.phase {
257 BulkfreePhase::Marking | BulkfreePhase::Sweeping => self.scratch.mark(block),
258 _ => {}
259 }
260 }
261
262 pub fn is_active(&self) -> bool {
263 matches!(self.phase, BulkfreePhase::Marking | BulkfreePhase::Sweeping)
264 }
265
266 pub fn is_done(&self) -> bool {
267 self.phase == BulkfreePhase::Done
268 }
269
270 pub fn phase(&self) -> BulkfreePhase {
271 self.phase
272 }
273}