Nothing to see here, move along meow
1use crate::block_io::BlockIo;
2use crate::cache::BlockCache;
3use crate::ditto::DittoRegion;
4use crate::error::FsError;
5use crate::freemap::FreemapAllocator;
6use crate::integrity;
7use lancer_core::fs::{BTreeNode, BlockRef, FREEMAP_BITS_PER_LEAF, FreemapLeaf};
8
9const SCRUB_BATCH_SIZE: u64 = 1024;
10const CORRUPTION_LOG_SIZE: usize = 64;
11
12#[derive(Clone, Copy)]
13pub struct CorruptionEvent {
14 pub block_num: u64,
15 pub outcome: ScrubOutcome,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum ScrubOutcome {
20 PrimaryDittoDivergence,
21 DittoReadFailed,
22}
23
24pub struct ScrubState {
25 cursor: u64,
26 active: bool,
27 events: [CorruptionEvent; CORRUPTION_LOG_SIZE],
28 event_head: usize,
29 event_count: usize,
30 total_events_logged: usize,
31}
32
33impl ScrubState {
34 pub const fn new() -> Self {
35 Self {
36 cursor: 0,
37 active: false,
38 events: [CorruptionEvent {
39 block_num: 0,
40 outcome: ScrubOutcome::PrimaryDittoDivergence,
41 }; CORRUPTION_LOG_SIZE],
42 event_head: 0,
43 event_count: 0,
44 total_events_logged: 0,
45 }
46 }
47}
48
49impl Default for ScrubState {
50 fn default() -> Self {
51 Self::new()
52 }
53}
54
55impl ScrubState {
56 pub fn start(&mut self, saved_cursor: u64) {
57 self.cursor = saved_cursor;
58 self.active = true;
59 }
60
61 pub fn cursor(&self) -> u64 {
62 self.cursor
63 }
64
65 pub fn is_active(&self) -> bool {
66 self.active
67 }
68
69 pub fn event_count(&self) -> usize {
70 self.event_count
71 }
72
73 fn log_event(&mut self, block_num: u64, outcome: ScrubOutcome) {
74 self.events[self.event_head] = CorruptionEvent { block_num, outcome };
75 self.event_head = (self.event_head + 1) % CORRUPTION_LOG_SIZE;
76 self.total_events_logged += 1;
77 self.event_count = self.total_events_logged.min(CORRUPTION_LOG_SIZE);
78 }
79
80 pub fn recent_events(&self, buf: &mut [CorruptionEvent]) -> usize {
81 let count = self.event_count.min(buf.len());
82 match count == 0 {
83 true => 0,
84 false => {
85 let start = match self.total_events_logged > CORRUPTION_LOG_SIZE {
86 true => self.event_head,
87 false => 0,
88 };
89 (0..count).for_each(|i| {
90 buf[i] = self.events[(start + i) % CORRUPTION_LOG_SIZE];
91 });
92 count
93 }
94 }
95 }
96
97 pub fn scrub_step(
98 &mut self,
99 cache: &mut BlockCache,
100 bio: &mut BlockIo,
101 ditto: &DittoRegion,
102 freemap: &FreemapAllocator,
103 ) -> Result<bool, FsError> {
104 match self.active {
105 false => Ok(true),
106 true => {
107 let total = freemap.total_data_blocks();
108 let data_start = freemap.data_region_start();
109 let end_block = self.cursor + SCRUB_BATCH_SIZE;
110
111 let batch_end = match end_block >= total {
112 true => total,
113 false => end_block,
114 };
115
116 (self.cursor..batch_end).try_for_each(|rel_offset| {
117 let absolute_block = data_start + rel_offset;
118 match is_block_allocated(cache, bio, freemap, rel_offset)? {
119 true => self.verify_single_block(cache, bio, ditto, absolute_block),
120 false => Ok(()),
121 }
122 })?;
123
124 match batch_end >= total {
125 true => {
126 self.cursor = 0;
127 Ok(true)
128 }
129 false => {
130 self.cursor = batch_end;
131 Ok(false)
132 }
133 }
134 }
135 }
136 }
137
138 fn verify_single_block(
139 &mut self,
140 cache: &mut BlockCache,
141 bio: &mut BlockIo,
142 ditto: &DittoRegion,
143 block_num: u64,
144 ) -> Result<(), FsError> {
145 let ditto_block = match ditto.ditto_addr(block_num) {
146 Some(addr) => addr,
147 None => return Ok(()),
148 };
149
150 let data = match cache.cache_read(bio, block_num) {
151 Ok(d) => d,
152 Err(_) => return Ok(()),
153 };
154
155 let primary_crc = integrity::crc32c(data);
156
157 let mut ditto_buf = [0u8; 4096];
158 match bio.read_blocks(ditto_block, 1, &mut ditto_buf) {
159 Ok(()) => {
160 let ditto_crc = integrity::crc32c(&ditto_buf);
161 match ditto_crc == primary_crc {
162 true => Ok(()),
163 false => {
164 self.log_event(block_num, ScrubOutcome::PrimaryDittoDivergence);
165 Ok(())
166 }
167 }
168 }
169 Err(_) => {
170 self.log_event(block_num, ScrubOutcome::DittoReadFailed);
171 Ok(())
172 }
173 }
174 }
175}
176
177#[cfg(test)]
178mod tests {
179 use super::*;
180
181 #[test]
182 fn new_state_defaults() {
183 let s = ScrubState::new();
184 assert_eq!(s.cursor(), 0);
185 assert!(!s.is_active());
186 assert_eq!(s.event_count(), 0);
187 }
188
189 #[test]
190 fn start_sets_cursor_and_active() {
191 let mut s = ScrubState::new();
192 s.start(42);
193 assert_eq!(s.cursor(), 42);
194 assert!(s.is_active());
195 }
196
197 #[test]
198 fn log_event_increments_count() {
199 let mut s = ScrubState::new();
200 s.log_event(100, ScrubOutcome::PrimaryDittoDivergence);
201 assert_eq!(s.event_count(), 1);
202 s.log_event(200, ScrubOutcome::DittoReadFailed);
203 assert_eq!(s.event_count(), 2);
204 }
205
206 #[test]
207 fn recent_events_returns_chronological_order() {
208 let mut s = ScrubState::new();
209 s.log_event(10, ScrubOutcome::PrimaryDittoDivergence);
210 s.log_event(20, ScrubOutcome::DittoReadFailed);
211 s.log_event(30, ScrubOutcome::PrimaryDittoDivergence);
212
213 let mut buf = [CorruptionEvent {
214 block_num: 0,
215 outcome: ScrubOutcome::PrimaryDittoDivergence,
216 }; 8];
217 let count = s.recent_events(&mut buf);
218 assert_eq!(count, 3);
219 assert_eq!(buf[0].block_num, 10);
220 assert_eq!(buf[1].block_num, 20);
221 assert_eq!(buf[2].block_num, 30);
222 }
223
224 #[test]
225 fn recent_events_ring_buffer_wraps() {
226 let mut s = ScrubState::new();
227 (0..CORRUPTION_LOG_SIZE + 10).for_each(|i| {
228 s.log_event(i as u64, ScrubOutcome::PrimaryDittoDivergence);
229 });
230
231 assert_eq!(s.event_count(), CORRUPTION_LOG_SIZE);
232
233 let mut buf = [CorruptionEvent {
234 block_num: 0,
235 outcome: ScrubOutcome::PrimaryDittoDivergence,
236 }; CORRUPTION_LOG_SIZE];
237 let count = s.recent_events(&mut buf);
238 assert_eq!(count, CORRUPTION_LOG_SIZE);
239
240 assert_eq!(buf[0].block_num, 10);
241 assert_eq!(
242 buf[CORRUPTION_LOG_SIZE - 1].block_num,
243 (CORRUPTION_LOG_SIZE + 9) as u64
244 );
245
246 (0..count - 1).for_each(|i| {
247 assert!(
248 buf[i].block_num < buf[i + 1].block_num,
249 "events not chronological at index {}: {} >= {}",
250 i,
251 buf[i].block_num,
252 buf[i + 1].block_num
253 );
254 });
255 }
256
257 #[test]
258 fn recent_events_partial_buffer() {
259 let mut s = ScrubState::new();
260 (0..20).for_each(|i| {
261 s.log_event(i, ScrubOutcome::DittoReadFailed);
262 });
263
264 let mut buf = [CorruptionEvent {
265 block_num: 0,
266 outcome: ScrubOutcome::PrimaryDittoDivergence,
267 }; 5];
268 let count = s.recent_events(&mut buf);
269 assert_eq!(count, 5);
270 assert_eq!(buf[0].block_num, 0);
271 }
272
273 #[test]
274 fn recent_events_empty() {
275 let s = ScrubState::new();
276 let mut buf = [CorruptionEvent {
277 block_num: 0,
278 outcome: ScrubOutcome::PrimaryDittoDivergence,
279 }; 4];
280 assert_eq!(s.recent_events(&mut buf), 0);
281 }
282
283 #[test]
284 fn recent_events_exactly_fills_ring() {
285 let mut s = ScrubState::new();
286 (0..CORRUPTION_LOG_SIZE).for_each(|i| {
287 s.log_event(i as u64 * 10, ScrubOutcome::PrimaryDittoDivergence);
288 });
289
290 assert_eq!(s.event_count(), CORRUPTION_LOG_SIZE);
291
292 let mut buf = [CorruptionEvent {
293 block_num: 0,
294 outcome: ScrubOutcome::PrimaryDittoDivergence,
295 }; CORRUPTION_LOG_SIZE];
296 let count = s.recent_events(&mut buf);
297 assert_eq!(count, CORRUPTION_LOG_SIZE);
298 assert_eq!(buf[0].block_num, 0);
299 assert_eq!(
300 buf[CORRUPTION_LOG_SIZE - 1].block_num,
301 (CORRUPTION_LOG_SIZE - 1) as u64 * 10
302 );
303 }
304
305 #[test]
306 fn event_outcome_preserved() {
307 let mut s = ScrubState::new();
308 s.log_event(1, ScrubOutcome::PrimaryDittoDivergence);
309 s.log_event(2, ScrubOutcome::DittoReadFailed);
310
311 let mut buf = [CorruptionEvent {
312 block_num: 0,
313 outcome: ScrubOutcome::PrimaryDittoDivergence,
314 }; 4];
315 s.recent_events(&mut buf);
316 assert_eq!(buf[0].outcome, ScrubOutcome::PrimaryDittoDivergence);
317 assert_eq!(buf[1].outcome, ScrubOutcome::DittoReadFailed);
318 }
319}
320
321fn is_block_allocated(
322 cache: &mut BlockCache,
323 bio: &mut BlockIo,
324 freemap: &FreemapAllocator,
325 relative_offset: u64,
326) -> Result<bool, FsError> {
327 let leaf_key = relative_offset / FREEMAP_BITS_PER_LEAF as u64;
328 let bit_offset = (relative_offset % FREEMAP_BITS_PER_LEAF as u64) as usize;
329
330 let leaf_block = find_freemap_leaf_for_scrub(cache, bio, &freemap.root(), leaf_key)?;
331 match leaf_block {
332 Some(block) => {
333 let data = cache.cache_read(bio, block)?;
334 let leaf = unsafe { &*(data.as_ptr() as *const FreemapLeaf) };
335 Ok(leaf.is_allocated(bit_offset))
336 }
337 None => Ok(false),
338 }
339}
340
341fn find_freemap_leaf_for_scrub(
342 cache: &mut BlockCache,
343 bio: &mut BlockIo,
344 root: &BlockRef,
345 leaf_key: u64,
346) -> Result<Option<u64>, FsError> {
347 match root.is_null() {
348 true => Ok(None),
349 false => {
350 let start = crate::blockref_block_num(root);
351
352 let result = (0..6).try_fold(start, |current_block, _| {
353 let node_data = cache.cache_read(bio, current_block)?;
354 let node = unsafe { &*(node_data.as_ptr() as *const BTreeNode) };
355
356 match node.is_valid() {
357 false => Err(FsError::CorruptNode),
358 true => match node.is_leaf() {
359 true => Ok(current_block | (1u64 << 62)),
360 false => {
361 let child_idx = node.find_child_index(leaf_key);
362 match child_idx < node.entry_count() {
363 true => Ok(crate::blockref_block_num(&node.entries[child_idx])),
364 false => Err(FsError::NotFound),
365 }
366 }
367 },
368 }
369 });
370
371 match result {
372 Ok(block) => match block & (1u64 << 62) != 0 {
373 true => Ok(Some(block & !(1u64 << 62))),
374 false => Err(FsError::CorruptNode),
375 },
376 Err(FsError::NotFound) => Ok(None),
377 Err(e) => Err(e),
378 }
379 }
380 }
381}