lewis.moe
Nothing to see here, move along
1use crate::block_io::BlockIo;
2use crate::cache::BlockCache;
3use crate::ditto::{DittoRegion, HealResult};
4use crate::error::IntegrityError;
5use lancer_core::fs::{BTREE_NODE_SIZE, BTreeNode, BlockRef};
6
7pub struct BlockHashes {
8 pub content_hash: u128,
9 pub integrity_crc: u32,
10}
11
12pub fn xxhash128(data: &[u8]) -> u128 {
13 xxhash_rust::xxh3::xxh3_128(data)
14}
15
16pub fn xxhash64(data: &[u8]) -> u64 {
17 xxhash_rust::xxh3::xxh3_64(data)
18}
19
20pub fn compute_block_hashes(data: &[u8]) -> BlockHashes {
21 BlockHashes {
22 content_hash: xxhash128(data),
23 integrity_crc: crc32c(data),
24 }
25}
26
27pub fn verify_block_crc(data: &[u8], expected_crc: u32) -> bool {
28 crc32c(data) == expected_crc
29}
30
31pub fn verify_block_hash(data: &[u8], expected_hash: u128) -> bool {
32 xxhash128(data) == expected_hash
33}
34
35const CRC32C_TABLE: [u32; 256] = generate_crc32c_table();
36
37const fn generate_crc32c_table() -> [u32; 256] {
38 let mut table = [0u32; 256];
39 let mut i = 0u32;
40 while i < 256 {
41 let mut crc = i;
42 let mut j = 0;
43 while j < 8 {
44 crc = match crc & 1 {
45 1 => (crc >> 1) ^ 0x82F6_3B78,
46 _ => crc >> 1,
47 };
48 j += 1;
49 }
50 table[i as usize] = crc;
51 i += 1;
52 }
53 table
54}
55
56pub fn crc32c_sw(data: &[u8]) -> u32 {
57 !data.iter().fold(!0u32, |crc, &byte| {
58 (crc >> 8) ^ CRC32C_TABLE[((crc ^ byte as u32) & 0xFF) as usize]
59 })
60}
61
62#[cfg(target_arch = "x86_64")]
63#[target_feature(enable = "sse4.2")]
64unsafe fn crc32c_sse42(data: &[u8]) -> u32 {
65 use core::arch::x86_64::{_mm_crc32_u8, _mm_crc32_u64};
66
67 let chunk_count = data.len() / 8;
68 let tail_start = chunk_count * 8;
69
70 let crc_after_chunks = (0..chunk_count).fold(!0u64, |crc, i| {
71 debug_assert!(i * 8 + 8 <= data.len());
72 let chunk = unsafe { core::ptr::read_unaligned(data.as_ptr().add(i * 8) as *const u64) };
73 _mm_crc32_u64(crc, chunk)
74 });
75
76 let crc_final = data[tail_start..]
77 .iter()
78 .fold(crc_after_chunks as u32, |crc, &byte| {
79 _mm_crc32_u8(crc, byte)
80 });
81
82 !crc_final
83}
84
85#[cfg(target_arch = "x86_64")]
86#[allow(unused_unsafe)]
87fn sse42_available() -> bool {
88 use core::sync::atomic::{AtomicU8, Ordering};
89 static STATUS: AtomicU8 = AtomicU8::new(0);
90 match STATUS.load(Ordering::Acquire) {
91 0 => {
92 let cpuid = unsafe { core::arch::x86_64::__cpuid(1) };
93 let available = (cpuid.ecx & (1 << 20)) != 0;
94 STATUS.store(
95 match available {
96 true => 2,
97 false => 1,
98 },
99 Ordering::Release,
100 );
101 available
102 }
103 2 => true,
104 _ => false,
105 }
106}
107
108#[cfg(target_arch = "x86_64")]
109pub fn crc32c(data: &[u8]) -> u32 {
110 match sse42_available() {
111 true => unsafe { crc32c_sse42(data) },
112 false => crc32c_sw(data),
113 }
114}
115
116#[cfg(not(target_arch = "x86_64"))]
117pub fn crc32c(data: &[u8]) -> u32 {
118 crc32c_sw(data)
119}
120
121const VERIFY_MAX_DEPTH: usize = 5;
122
123enum VerifyWalk {
124 Verified,
125 Error(IntegrityError),
126}
127
128pub fn verify_path(
129 cache: &mut BlockCache,
130 bio: &mut BlockIo,
131 tree_root: &BlockRef,
132 target_key: u64,
133) -> Result<(), IntegrityError> {
134 if tree_root.is_null() {
135 return Err(IntegrityError::TreeCorrupt);
136 }
137
138 let result = (0..VERIFY_MAX_DEPTH + 1).try_fold(*tree_root, |current_ref, _| {
139 let block_num = crate::blockref_block_num(¤t_ref);
140 let data = cache
141 .cache_read(bio, block_num)
142 .map_err(|e| VerifyWalk::Error(IntegrityError::Io(e)))?;
143
144 let actual_crc = crc32c(data);
145 match actual_crc == current_ref.integrity_crc {
146 true => {}
147 false => {
148 return Err(VerifyWalk::Error(IntegrityError::CrcMismatch { block_num }));
149 }
150 }
151
152 let actual_hash = xxhash128(data);
153 match actual_hash == current_ref.content_hash_u128() {
154 true => {}
155 false => {
156 return Err(VerifyWalk::Error(IntegrityError::HashMismatch {
157 block_num,
158 }));
159 }
160 }
161
162 let node = read_btree_node(data);
163 match node.is_valid() {
164 true => {}
165 false => return Err(VerifyWalk::Error(IntegrityError::TreeCorrupt)),
166 }
167
168 match node.is_leaf() {
169 true => Err(VerifyWalk::Verified),
170 false => {
171 let child_idx = node.find_child_index(target_key);
172 match child_idx < node.entry_count() {
173 true => Ok(node.entries[child_idx]),
174 false => Err(VerifyWalk::Error(IntegrityError::KeyNotInTree)),
175 }
176 }
177 }
178 });
179
180 match result {
181 Err(VerifyWalk::Verified) => Ok(()),
182 Err(VerifyWalk::Error(e)) => Err(e),
183 Ok(_) => Err(IntegrityError::TreeCorrupt),
184 }
185}
186
187fn read_btree_node(data: &[u8; BTREE_NODE_SIZE]) -> BTreeNode {
188 unsafe { core::ptr::read_unaligned(data.as_ptr() as *const BTreeNode) }
189}
190
191pub fn metadata_read_healing(
192 cache: &mut BlockCache,
193 bio: &mut BlockIo,
194 ditto: &DittoRegion,
195 block_num: u64,
196 expected_crc: u32,
197) -> Result<ReadHealOutcome, IntegrityError> {
198 let data = cache
199 .cache_read(bio, block_num)
200 .map_err(IntegrityError::Io)?;
201
202 let actual_crc = crc32c(data);
203 match actual_crc == expected_crc {
204 true => Ok(ReadHealOutcome::Clean),
205 false => match ditto.try_heal(bio, block_num, expected_crc) {
206 Ok(HealResult::Repaired(repaired_data)) => {
207 cache
208 .cache_write(bio, block_num, &repaired_data)
209 .map_err(IntegrityError::Io)?;
210 Ok(ReadHealOutcome::Repaired)
211 }
212 Ok(HealResult::BothCorrupt) => Err(IntegrityError::CrcMismatch { block_num }),
213 Err(e) => Err(IntegrityError::Io(e)),
214 },
215 }
216}
217
218#[derive(Debug)]
219pub enum ReadHealOutcome {
220 Clean,
221 Repaired,
222}
223
224pub fn verify_and_heal_block(
225 bio: &mut BlockIo,
226 ditto: &DittoRegion,
227 block_num: u64,
228 data: &[u8],
229 expected_crc: u32,
230 is_metadata: bool,
231) -> Result<VerifyHealResult, IntegrityError> {
232 let actual_crc = crc32c(data);
233 match actual_crc == expected_crc {
234 true => Ok(VerifyHealResult::Ok),
235 false => match is_metadata {
236 true => match ditto.try_heal(bio, block_num, expected_crc) {
237 Ok(HealResult::Repaired(_)) => Ok(VerifyHealResult::HealedFromDitto),
238 Ok(HealResult::BothCorrupt) => Err(IntegrityError::CrcMismatch { block_num }),
239 Err(e) => Err(IntegrityError::Io(e)),
240 },
241 false => Err(IntegrityError::CrcMismatch { block_num }),
242 },
243 }
244}
245
246pub enum VerifyHealResult {
247 Ok,
248 HealedFromDitto,
249}
250
251#[cfg(test)]
252mod tests {
253 use super::*;
254
255 #[test]
256 fn crc32c_empty_input() {
257 assert_eq!(crc32c_sw(&[]), 0x0000_0000);
258 assert_eq!(crc32c(&[]), 0x0000_0000);
259 }
260
261 #[test]
262 fn crc32c_known_vector_iscsi() {
263 let data = b"123456789";
264 assert_eq!(crc32c_sw(data), 0xE306_9283);
265 }
266
267 #[test]
268 fn crc32c_sw_matches_dispatch() {
269 let patterns: &[&[u8]] = &[
270 b"",
271 b"\x00",
272 b"hello world",
273 b"123456789",
274 &[0xFF; 4096],
275 &(0..=255).collect::<Vec<u8>>(),
276 ];
277 patterns.iter().for_each(|data| {
278 assert_eq!(
279 crc32c(data),
280 crc32c_sw(data),
281 "mismatch for data len {}",
282 data.len()
283 );
284 });
285 }
286
287 #[test]
288 fn crc32c_single_byte_variations() {
289 let results: Vec<u32> = (0u8..=255).map(|b| crc32c_sw(&[b])).collect();
290 let unique_count = {
291 let mut sorted = results.clone();
292 sorted.sort();
293 sorted.dedup();
294 sorted.len()
295 };
296 assert_eq!(unique_count, 256);
297 }
298
299 #[test]
300 fn crc32c_different_data_different_crcs() {
301 let a = crc32c(b"block A content");
302 let b = crc32c(b"block B content");
303 assert_ne!(a, b);
304 }
305
306 #[test]
307 fn crc32c_full_block_sw_matches_dispatch() {
308 let block = [0xAB_u8; 4096];
309 assert_eq!(crc32c(&block), crc32c_sw(&block));
310 }
311
312 #[test]
313 fn crc32c_alignment_sizes() {
314 [1, 7, 8, 9, 15, 16, 17, 63, 64, 65, 256, 4096]
315 .iter()
316 .for_each(|&size| {
317 let data: Vec<u8> = (0..size).map(|i| (i & 0xFF) as u8).collect();
318 assert_eq!(crc32c(&data), crc32c_sw(&data), "mismatch at size {}", size);
319 });
320 }
321
322 #[test]
323 fn xxhash128_deterministic() {
324 let data = b"some block data";
325 assert_eq!(xxhash128(data), xxhash128(data));
326 }
327
328 #[test]
329 fn xxhash128_different_data_different_hashes() {
330 assert_ne!(xxhash128(b"aaa"), xxhash128(b"bbb"));
331 }
332
333 #[test]
334 fn xxhash64_deterministic() {
335 let data = b"snapshot name";
336 assert_eq!(xxhash64(data), xxhash64(data));
337 }
338
339 #[test]
340 fn xxhash64_different_data_different_hashes() {
341 assert_ne!(xxhash64(b"snap1"), xxhash64(b"snap2"));
342 }
343
344 #[test]
345 fn compute_block_hashes_consistent() {
346 let data = [0x42u8; 4096];
347 let h = compute_block_hashes(&data);
348 assert_eq!(h.integrity_crc, crc32c(&data));
349 assert_eq!(h.content_hash, xxhash128(&data));
350 }
351
352 #[test]
353 fn verify_block_crc_pass() {
354 let data = [0xDE_u8; 4096];
355 let crc = crc32c(&data);
356 assert!(verify_block_crc(&data, crc));
357 }
358
359 #[test]
360 fn verify_block_crc_fail() {
361 let data = [0xDE_u8; 4096];
362 assert!(!verify_block_crc(&data, 0xDEAD_BEEF));
363 }
364
365 #[test]
366 fn verify_block_hash_pass() {
367 let data = [0x11_u8; 4096];
368 let hash = xxhash128(&data);
369 assert!(verify_block_hash(&data, hash));
370 }
371
372 #[test]
373 fn verify_block_hash_fail() {
374 let data = [0x11_u8; 4096];
375 assert!(!verify_block_hash(&data, 0xBAD));
376 }
377
378 #[test]
379 fn metadata_read_healing_clean_block() {
380 let mut bio = crate::test_helpers::make_bio(256);
381 let mut cache = crate::test_helpers::make_cache();
382 let ditto = DittoRegion::init(10, 200);
383
384 let block_data = [0xAA_u8; 4096];
385 let crc = crc32c(&block_data);
386 bio.write_blocks(50, 1, &block_data).unwrap();
387
388 match metadata_read_healing(&mut cache, &mut bio, &ditto, 50, crc) {
389 Ok(ReadHealOutcome::Clean) => {}
390 other => panic!("expected Clean, got {:?}", other),
391 }
392 }
393
394 #[test]
395 fn metadata_read_healing_repairs_from_ditto() {
396 let mut bio = crate::test_helpers::make_bio(256);
397 let mut cache = crate::test_helpers::make_cache();
398 let ditto = DittoRegion::init(10, 200);
399
400 let good_data = [0xBB_u8; 4096];
401 let good_crc = crc32c(&good_data);
402
403 let corrupt_data = [0xCC_u8; 4096];
404 bio.write_blocks(50, 1, &corrupt_data).unwrap();
405
406 let ditto_block = ditto.ditto_addr(50).unwrap();
407 bio.write_blocks(ditto_block, 1, &good_data).unwrap();
408
409 match metadata_read_healing(&mut cache, &mut bio, &ditto, 50, good_crc) {
410 Ok(ReadHealOutcome::Repaired) => {}
411 other => panic!("expected Repaired, got {:?}", other),
412 }
413 }
414
415 #[test]
416 fn metadata_read_healing_both_corrupt() {
417 let mut bio = crate::test_helpers::make_bio(256);
418 let mut cache = crate::test_helpers::make_cache();
419 let ditto = DittoRegion::init(10, 200);
420
421 let corrupt = [0xDD_u8; 4096];
422 bio.write_blocks(50, 1, &corrupt).unwrap();
423
424 let ditto_block = ditto.ditto_addr(50).unwrap();
425 let also_corrupt = [0xEE_u8; 4096];
426 bio.write_blocks(ditto_block, 1, &also_corrupt).unwrap();
427
428 let expected_crc = crc32c(&[0xFF_u8; 4096]);
429 match metadata_read_healing(&mut cache, &mut bio, &ditto, 50, expected_crc) {
430 Err(IntegrityError::CrcMismatch { block_num: 50 }) => {}
431 other => panic!("expected CrcMismatch, got {:?}", other),
432 }
433 }
434}