Nothing to see here, move along meow
1use lancer_core::fs::*;
2use proptest::prelude::*;
3
4fn btree_with_keys(keys: &[u64]) -> BTreeNode {
5 let mut node = BTreeNode::new(0);
6 keys.iter().enumerate().for_each(|(i, &key)| {
7 node.entries[i] = BlockRef::new(
8 (i as u64 + 1) * 16,
9 12,
10 key,
11 1,
12 0,
13 0,
14 BlockType::Data,
15 Compression::None,
16 4096,
17 0,
18 );
19 });
20 node.header.entry_count = keys.len() as u16;
21 node
22}
23
24fn make_blockref(addr: u64, size_log2: u8, key: u64) -> BlockRef {
25 BlockRef::new(
26 addr,
27 size_log2,
28 key,
29 1,
30 0,
31 0,
32 BlockType::Data,
33 Compression::None,
34 4096,
35 0,
36 )
37}
38
39fn naive_find_free(leaf: &FreemapLeaf, start: usize, count: usize) -> Option<usize> {
40 if count == 0 {
41 return None;
42 }
43 let total = FREEMAP_BITS_PER_LEAF;
44 let mut run_start = start;
45 let mut run_len = 0usize;
46 (start..total).find_map(|bit| match leaf.is_allocated(bit) {
47 true => {
48 run_len = 0;
49 run_start = bit + 1;
50 None
51 }
52 false => {
53 if run_len == 0 {
54 run_start = bit;
55 }
56 run_len += 1;
57 match run_len >= count && run_start + count <= total {
58 true => Some(run_start),
59 false => None,
60 }
61 }
62 })
63}
64
65#[test]
66fn freemap_empty_finds_any_run() {
67 let leaf = FreemapLeaf::ZERO;
68 assert_eq!(leaf.find_contiguous_free(1), Some(0));
69 assert_eq!(leaf.find_contiguous_free(64), Some(0));
70 assert_eq!(leaf.find_contiguous_free(FREEMAP_BITS_PER_LEAF), Some(0));
71}
72
73#[test]
74fn freemap_full_returns_none() {
75 assert_eq!(FreemapLeaf::FULL.find_contiguous_free(1), None);
76}
77
78#[test]
79fn freemap_count_zero_returns_none() {
80 assert_eq!(FreemapLeaf::ZERO.find_contiguous_free(0), None);
81}
82
83#[test]
84fn freemap_exceeds_leaf_returns_none() {
85 assert_eq!(
86 FreemapLeaf::ZERO.find_contiguous_free(FREEMAP_BITS_PER_LEAF + 1),
87 None
88 );
89}
90
91#[test]
92fn freemap_single_bit_at_word_boundaries() {
93 [0usize, 63, 64, 127, 128].iter().for_each(|&bit| {
94 let leaf = FreemapLeaf::FULL.with_bit_cleared(bit);
95 assert_eq!(
96 leaf.find_contiguous_free_from(bit, 1),
97 Some(bit),
98 "failed at bit {}",
99 bit
100 );
101 });
102}
103
104#[test]
105fn freemap_run_spans_word_boundary() {
106 let mut leaf = FreemapLeaf::FULL;
107 leaf.clear_range(60, 9);
108 assert_eq!(leaf.find_contiguous_free(9), Some(60));
109 assert_eq!(leaf.find_contiguous_free(10), None);
110}
111
112#[test]
113fn freemap_run_at_exact_word_boundary() {
114 let mut leaf = FreemapLeaf::FULL;
115 leaf.clear_range(64, 64);
116 assert_eq!(leaf.find_contiguous_free(64), Some(64));
117 assert_eq!(leaf.find_contiguous_free(65), None);
118}
119
120#[test]
121fn freemap_run_at_end_of_leaf() {
122 let mut leaf = FreemapLeaf::FULL;
123 let start = FREEMAP_BITS_PER_LEAF - 10;
124 leaf.clear_range(start, 10);
125 assert_eq!(leaf.find_contiguous_free(10), Some(start));
126 assert_eq!(leaf.find_contiguous_free(11), None);
127}
128
129#[test]
130fn freemap_alternating_no_run_of_two() {
131 let mut leaf = FreemapLeaf::ZERO;
132 (0..FREEMAP_BITS_PER_LEAF)
133 .step_by(2)
134 .for_each(|i| leaf.set_bit(i));
135 assert_eq!(leaf.find_contiguous_free(2), None);
136 assert_eq!(leaf.find_contiguous_free(1), Some(1));
137}
138
139#[test]
140fn freemap_set_clear_range_roundtrip() {
141 let mut leaf = FreemapLeaf::ZERO;
142 leaf.set_range(100, 50);
143 (100..150).for_each(|i| assert!(leaf.is_allocated(i)));
144 (0..100).for_each(|i| assert!(!leaf.is_allocated(i)));
145 leaf.clear_range(100, 50);
146 assert_eq!(leaf, FreemapLeaf::ZERO);
147}
148
149#[test]
150fn freemap_set_range_crosses_byte_boundaries() {
151 let mut leaf = FreemapLeaf::ZERO;
152 leaf.set_range(5, 16);
153 (5..21).for_each(|i| assert!(leaf.is_allocated(i), "bit {} should be set", i));
154 (0..5).for_each(|i| assert!(!leaf.is_allocated(i)));
155 assert!(!leaf.is_allocated(21));
156}
157
158#[test]
159fn freemap_start_bit_skips_earlier_free_region() {
160 let mut leaf = FreemapLeaf::FULL;
161 leaf.clear_range(10, 5);
162 leaf.clear_range(200, 5);
163 assert_eq!(leaf.find_contiguous_free_from(100, 5), Some(200));
164 assert_eq!(leaf.find_contiguous_free_from(0, 5), Some(10));
165}
166
167#[test]
168fn freemap_with_bit_set_cleared_functional() {
169 let set = FreemapLeaf::ZERO.with_bit_set(42);
170 assert!(set.is_allocated(42));
171 assert!(!FreemapLeaf::ZERO.is_allocated(42));
172 let cleared = set.with_bit_cleared(42);
173 assert!(!cleared.is_allocated(42));
174 assert_eq!(cleared, FreemapLeaf::ZERO);
175}
176
177#[test]
178fn freemap_run_bit63_into_next_word() {
179 let mut leaf = FreemapLeaf::FULL;
180 leaf.clear_range(63, 2);
181 assert_eq!(leaf.find_contiguous_free(2), Some(63));
182 assert_eq!(leaf.find_contiguous_free(3), None);
183
184 let mut leaf2 = FreemapLeaf::FULL;
185 leaf2.clear_range(63, 65);
186 assert_eq!(leaf2.find_contiguous_free(65), Some(63));
187 assert_eq!(leaf2.find_contiguous_free(66), None);
188}
189
190#[test]
191fn freemap_run_partial_to_zero_words_to_partial() {
192 let mut leaf = FreemapLeaf::FULL;
193 leaf.clear_range(60, 4 + 64 + 64 + 10);
194 assert_eq!(leaf.find_contiguous_free(142), Some(60));
195 assert_eq!(leaf.find_contiguous_free(143), None);
196
197 let expected = naive_find_free(&leaf, 0, 142);
198 assert_eq!(leaf.find_contiguous_free(142), expected);
199}
200
201#[test]
202fn freemap_start_bit_mid_run() {
203 let mut leaf = FreemapLeaf::FULL;
204 leaf.clear_range(50, 20);
205 assert_eq!(leaf.find_contiguous_free_from(55, 10), Some(55));
206 assert_eq!(leaf.find_contiguous_free_from(55, 15), Some(55));
207 assert_eq!(leaf.find_contiguous_free_from(55, 16), None);
208 assert_eq!(leaf.find_contiguous_free_from(60, 10), Some(60));
209 assert_eq!(leaf.find_contiguous_free_from(60, 11), None);
210}
211
212#[test]
213fn freemap_near_full_sparse_holes() {
214 let mut leaf = FreemapLeaf::FULL;
215 leaf.clear_bit(100);
216 leaf.clear_bit(5000);
217 leaf.clear_bit(32000);
218
219 assert_eq!(leaf.find_contiguous_free(1), Some(100));
220 assert_eq!(leaf.find_contiguous_free(2), None);
221 assert_eq!(leaf.find_contiguous_free_from(101, 1), Some(5000));
222 assert_eq!(leaf.find_contiguous_free_from(5001, 1), Some(32000));
223 assert_eq!(leaf.find_contiguous_free_from(32001, 1), None);
224}
225
226#[test]
227fn freemap_two_candidate_runs_first_too_short() {
228 let mut leaf = FreemapLeaf::FULL;
229 leaf.clear_range(100, 9);
230 leaf.clear_range(300, 10);
231 assert_eq!(leaf.find_contiguous_free(10), Some(300));
232 assert_eq!(leaf.find_contiguous_free(9), Some(100));
233}
234
235#[test]
236fn freemap_run_across_three_word_types() {
237 let mut leaf = FreemapLeaf::FULL;
238 leaf.clear_range(62, 130);
239 assert_eq!(leaf.find_contiguous_free(130), Some(62));
240 let expected = naive_find_free(&leaf, 0, 130);
241 assert_eq!(leaf.find_contiguous_free(130), expected);
242}
243
244#[test]
245fn freemap_start_bit_not_word_aligned_all_free_after() {
246 let mut leaf = FreemapLeaf::ZERO;
247 assert_eq!(leaf.find_contiguous_free_from(37, 200), Some(37));
248
249 leaf.set_range(0, 37);
250 assert_eq!(leaf.find_contiguous_free(200), Some(37));
251 assert_eq!(
252 leaf.find_contiguous_free(FREEMAP_BITS_PER_LEAF - 37),
253 Some(37)
254 );
255 assert_eq!(leaf.find_contiguous_free(FREEMAP_BITS_PER_LEAF - 36), None);
256}
257
258#[test]
259fn freemap_start_bit_past_end() {
260 let leaf = FreemapLeaf::ZERO;
261 assert_eq!(
262 leaf.find_contiguous_free_from(FREEMAP_BITS_PER_LEAF, 1),
263 None
264 );
265 assert_eq!(
266 leaf.find_contiguous_free_from(FREEMAP_BITS_PER_LEAF + 1000, 1),
267 None
268 );
269}
270
271#[test]
272fn freemap_oracle_deterministic_patterns() {
273 let patterns: Vec<(Vec<(usize, usize)>, usize)> = vec![
274 (vec![(0, 64)], 1),
275 (vec![(0, 64)], 65),
276 (vec![(63, 1)], 1),
277 (vec![(0, 128)], 129),
278 (vec![(60, 9)], 5),
279 (vec![(0, 32768)], 1),
280 (vec![(0, 100), (200, 100)], 50),
281 (vec![(0, 100), (200, 100)], 101),
282 ];
283
284 patterns.iter().for_each(|(ranges, count)| {
285 let mut leaf = FreemapLeaf::FULL;
286 ranges
287 .iter()
288 .for_each(|&(start, len)| leaf.clear_range(start, len));
289
290 let optimized = leaf.find_contiguous_free(*count);
291 let naive = naive_find_free(&leaf, 0, *count);
292 assert_eq!(
293 optimized, naive,
294 "mismatch for ranges {:?}, count {}",
295 ranges, count
296 );
297 });
298}
299
300proptest! {
301 #[test]
302 fn freemap_oracle_random_bitmap(
303 data in proptest::collection::vec(any::<u8>(), 4096),
304 count in 1usize..256,
305 start in 0usize..32768,
306 ) {
307 let mut leaf = FreemapLeaf::ZERO;
308 leaf.bits.copy_from_slice(&data);
309
310 let optimized = leaf.find_contiguous_free_from(start, count);
311 let naive = naive_find_free(&leaf, start, count);
312
313 prop_assert_eq!(
314 optimized, naive,
315 "oracle mismatch: start={}, count={}", start, count
316 );
317 }
318
319 #[test]
320 fn freemap_oracle_sparse_bitmap(
321 set_positions in proptest::collection::vec(0usize..32768, 0..200),
322 count in 1usize..512,
323 ) {
324 let mut leaf = FreemapLeaf::ZERO;
325 set_positions.iter().for_each(|&pos| leaf.set_bit(pos));
326
327 let optimized = leaf.find_contiguous_free(count);
328 let naive = naive_find_free(&leaf, 0, count);
329 prop_assert_eq!(optimized, naive, "sparse oracle mismatch, count={}", count);
330 }
331
332 #[test]
333 fn freemap_oracle_dense_bitmap(
334 clear_positions in proptest::collection::vec(0usize..32768, 0..200),
335 count in 1usize..64,
336 ) {
337 let mut leaf = FreemapLeaf::FULL;
338 clear_positions.iter().for_each(|&pos| leaf.clear_bit(pos));
339
340 let optimized = leaf.find_contiguous_free(count);
341 let naive = naive_find_free(&leaf, 0, count);
342 prop_assert_eq!(optimized, naive, "dense oracle mismatch, count={}", count);
343 }
344
345 #[test]
346 fn freemap_set_clear_roundtrip_prop(
347 start in 0..32000usize,
348 count in 1..200usize,
349 ) {
350 prop_assume!(start + count <= FREEMAP_BITS_PER_LEAF);
351 let mut leaf = FreemapLeaf::ZERO;
352 leaf.set_range(start, count);
353 (start..start + count).for_each(|i| {
354 assert!(leaf.is_allocated(i), "bit {} should be allocated", i);
355 });
356 leaf.clear_range(start, count);
357 (start..start + count).for_each(|i| {
358 assert!(!leaf.is_allocated(i), "bit {} should be free", i);
359 });
360 }
361
362 #[test]
363 fn freemap_find_result_is_genuinely_free(
364 data in proptest::collection::vec(any::<u8>(), 4096),
365 count in 1usize..128,
366 ) {
367 let mut leaf = FreemapLeaf::ZERO;
368 leaf.bits.copy_from_slice(&data);
369 if let Some(start) = leaf.find_contiguous_free(count) {
370 prop_assert!(start + count <= FREEMAP_BITS_PER_LEAF);
371 (start..start + count).for_each(|bit| {
372 assert!(!leaf.is_allocated(bit), "bit {} in returned run is allocated", bit);
373 });
374 }
375 }
376}
377
378#[test]
379fn btree_empty_search_returns_err_zero() {
380 assert_eq!(BTreeNode::EMPTY_LEAF.search_by_key(42), Err(0));
381}
382
383#[test]
384fn btree_single_entry_search() {
385 let node = btree_with_keys(&[100]);
386 assert_eq!(node.search_by_key(100), Ok(0));
387 assert_eq!(node.search_by_key(50), Err(0));
388 assert_eq!(node.search_by_key(150), Err(1));
389}
390
391#[test]
392fn btree_full_node_search() {
393 let keys: Vec<u64> = (0..BTREE_MAX_ENTRIES as u64)
394 .map(|i| (i + 1) * 10)
395 .collect();
396 let node = btree_with_keys(&keys);
397 assert!(node.is_full());
398
399 assert_eq!(node.search_by_key(10), Ok(0));
400 assert_eq!(node.search_by_key(320), Ok(31));
401 assert_eq!(node.search_by_key(630), Ok(62));
402
403 assert_eq!(node.search_by_key(5), Err(0));
404 assert_eq!(node.search_by_key(15), Err(1));
405 assert_eq!(node.search_by_key(635), Err(63));
406}
407
408#[test]
409fn btree_full_node_miss_between_every_pair() {
410 let keys: Vec<u64> = (0..BTREE_MAX_ENTRIES as u64)
411 .map(|i| (i + 1) * 10)
412 .collect();
413 let node = btree_with_keys(&keys);
414 (0..BTREE_MAX_ENTRIES).for_each(|i| {
415 let key = (i as u64 + 1) * 10 + 5;
416 assert_eq!(node.search_by_key(key), Err(i + 1));
417 });
418}
419
420#[test]
421fn btree_find_child_index_routes_correctly() {
422 let node = btree_with_keys(&[10, 20, 30]);
423 assert_eq!(node.find_child_index(5), 0);
424 assert_eq!(node.find_child_index(10), 0);
425 assert_eq!(node.find_child_index(15), 1);
426 assert_eq!(node.find_child_index(20), 1);
427 assert_eq!(node.find_child_index(25), 2);
428 assert_eq!(node.find_child_index(30), 2);
429 assert_eq!(node.find_child_index(35), 2);
430}
431
432#[test]
433fn btree_is_valid_checks_magic() {
434 assert!(BTreeNode::EMPTY_LEAF.is_valid());
435 assert!(BTreeNode::new(0).is_valid());
436 assert!(BTreeNode::new(5).is_valid());
437 assert!(!BTreeNode::ZEROED.is_valid());
438}
439
440#[test]
441fn btree_is_leaf_checks_level() {
442 assert!(BTreeNode::new(0).is_leaf());
443 assert!(!BTreeNode::new(1).is_leaf());
444 assert!(!BTreeNode::new(255).is_leaf());
445}
446
447#[test]
448fn btree_entry_count_reflects_header() {
449 let mut node = BTreeNode::new(0);
450 assert_eq!(node.entry_count(), 0);
451 node.header.entry_count = 5;
452 assert_eq!(node.entry_count(), 5);
453 node.header.entry_count = BTREE_MAX_ENTRIES as u16;
454 assert_eq!(node.entry_count(), BTREE_MAX_ENTRIES);
455}
456
457#[test]
458fn btree_active_entries_correct_slice() {
459 let node = btree_with_keys(&[10, 20, 30]);
460 let entries = node.active_entries();
461 assert_eq!(entries.len(), 3);
462 assert_eq!(entries[0].key, 10);
463 assert_eq!(entries[1].key, 20);
464 assert_eq!(entries[2].key, 30);
465}
466
467#[test]
468fn btree_underflow_and_full() {
469 let mut node = BTreeNode::new(0);
470 assert!(node.is_underflow());
471 assert!(!node.is_full());
472
473 node.header.entry_count = BTREE_MIN_ENTRIES as u16;
474 assert!(!node.is_underflow());
475
476 node.header.entry_count = BTREE_MAX_ENTRIES as u16;
477 assert!(node.is_full());
478}
479
480#[test]
481fn btree_duplicate_keys_search() {
482 let node = btree_with_keys(&[10, 10, 10, 20, 20]);
483 let result = node.search_by_key(10);
484 assert!(result.is_ok());
485 assert!(result.unwrap() <= 2);
486
487 let result2 = node.search_by_key(20);
488 assert!(result2.is_ok());
489 let idx = result2.unwrap();
490 assert!(idx >= 3 && idx <= 4);
491}
492
493#[test]
494fn btree_search_key_zero_against_unpopulated_entries() {
495 let mut node = BTreeNode::new(0);
496 node.entries[0] = make_blockref(16, 12, 100);
497 node.entries[1] = make_blockref(32, 12, 200);
498 node.header.entry_count = 2;
499
500 assert_eq!(node.search_by_key(0), Err(0));
501 assert_eq!(node.search_by_key(100), Ok(0));
502 assert_eq!(node.search_by_key(150), Err(1));
503 assert_eq!(node.search_by_key(200), Ok(1));
504 assert_eq!(node.search_by_key(300), Err(2));
505}
506
507#[test]
508#[should_panic]
509fn btree_entry_count_exceeds_array_panics() {
510 let mut node = BTreeNode::new(0);
511 node.header.entry_count = BTREE_MAX_ENTRIES as u16 + 1;
512 let _ = node.active_entries();
513}
514
515proptest! {
516 #[test]
517 fn btree_sorted_keys_all_findable(count in 1..=63usize) {
518 let keys: Vec<u64> = (0..count as u64).map(|i| i * 7 + 1).collect();
519 let node = btree_with_keys(&keys);
520 keys.iter().enumerate().for_each(|(i, &key)| {
521 assert_eq!(node.search_by_key(key), Ok(i));
522 });
523 }
524
525 #[test]
526 fn btree_miss_always_returns_valid_insertion_point(count in 1..=63usize) {
527 let keys: Vec<u64> = (0..count as u64).map(|i| (i + 1) * 100).collect();
528 let node = btree_with_keys(&keys);
529
530 let miss_key = count as u64 * 100 + 50;
531 let result = node.search_by_key(miss_key);
532 prop_assert!(result.is_err());
533 let idx = result.unwrap_err();
534 prop_assert!(idx <= count);
535
536 if idx > 0 {
537 prop_assert!(node.entries[idx - 1].key < miss_key);
538 }
539 if idx < count {
540 prop_assert!(node.entries[idx].key > miss_key);
541 }
542 }
543}
544
545#[test]
546fn blockref_physical_addr_masks_bottom_bits() {
547 let br = make_blockref(0x1000, 12, 0);
548 assert_eq!(br.physical_block_addr(), 0x1000);
549 assert_eq!(br.size_shift(), 0);
550}
551
552#[test]
553fn blockref_size_shift_extracts_correctly() {
554 (0u8..=MAX_SIZE_SHIFT).for_each(|shift| {
555 let log2 = shift + BLOCK_SIZE_MIN_LOG2;
556 let br = make_blockref(0x1000, log2, 0);
557 assert_eq!(br.size_shift(), shift);
558 assert_eq!(br.physical_block_addr(), 0x1000);
559 });
560}
561
562#[test]
563fn blockref_block_size_log2_valid_range() {
564 (BLOCK_SIZE_MIN_LOG2..=BLOCK_SIZE_MAX_LOG2).for_each(|log2| {
565 let br = make_blockref(0x1000, log2, 0);
566 assert_eq!(br.block_size_log2(), Some(log2));
567 assert_eq!(br.block_size(), Some(1u32 << log2));
568 });
569}
570
571#[test]
572fn blockref_invalid_size_shift_returns_none() {
573 let mut br = BlockRef::ZERO;
574 br.physical_addr = MAX_SIZE_SHIFT as u64 + 1;
575 assert_eq!(br.block_size_log2(), None);
576 assert_eq!(br.block_size(), None);
577}
578
579#[test]
580fn blockref_is_null_semantics() {
581 assert!(BlockRef::ZERO.is_null());
582
583 let mut addr_only = BlockRef::ZERO;
584 addr_only.physical_addr = 0x10;
585 assert!(!addr_only.is_null());
586
587 let mut key_only = BlockRef::ZERO;
588 key_only.key = 1;
589 assert!(!key_only.is_null());
590
591 let mut both_nonzero = BlockRef::ZERO;
592 both_nonzero.physical_addr = 0x10;
593 both_nonzero.key = 1;
594 assert!(!both_nonzero.is_null());
595}
596
597#[test]
598fn blockref_null_requires_both_zero() {
599 let mut br = BlockRef::ZERO;
600 br.transaction_id = 999;
601 br.integrity_crc = 0xDEAD;
602 assert!(br.is_null());
603}
604
605#[test]
606fn blockref_content_hash_roundtrip() {
607 let hash: u128 = 0xDEAD_BEEF_CAFE_BABE_1234_5678_9ABC_DEF0;
608 let br = BlockRef::new(
609 0x2000,
610 12,
611 42,
612 1,
613 hash,
614 0,
615 BlockType::Data,
616 Compression::None,
617 100,
618 0,
619 );
620 assert_eq!(br.content_hash_u128(), hash);
621}
622
623#[test]
624fn blockref_content_hash_zero() {
625 assert_eq!(BlockRef::ZERO.content_hash_u128(), 0);
626}
627
628#[test]
629fn blockref_content_hash_max() {
630 let br = BlockRef::new(
631 0x1000,
632 12,
633 0,
634 0,
635 u128::MAX,
636 0,
637 BlockType::Data,
638 Compression::None,
639 0,
640 0,
641 );
642 assert_eq!(br.content_hash_u128(), u128::MAX);
643}
644
645#[test]
646fn blockref_new_all_block_types() {
647 [
648 BlockType::Data,
649 BlockType::Inode,
650 BlockType::Indirect,
651 BlockType::Freemap,
652 BlockType::Directory,
653 ]
654 .iter()
655 .for_each(|&bt| {
656 let br = BlockRef::new(0x1000, 12, 1, 1, 0, 0, bt, Compression::None, 4096, 0);
657 assert_eq!(br.block_type_enum(), Some(bt));
658 });
659}
660
661#[test]
662fn blockref_new_all_compressions() {
663 [Compression::None, Compression::Lz4].iter().for_each(|&c| {
664 let br = BlockRef::new(0x1000, 12, 1, 1, 0, 0, BlockType::Data, c, 4096, 0);
665 assert_eq!(br.compression_enum(), Some(c));
666 });
667}
668
669#[test]
670fn blockref_zero_const() {
671 let z = BlockRef::ZERO;
672 assert!(z.is_null());
673 assert_eq!(z.physical_block_addr(), 0);
674 assert_eq!(z.key, 0);
675 assert_eq!(z.transaction_id, 0);
676 assert_eq!(z.content_hash_u128(), 0);
677 assert_eq!(z.block_type_enum(), Some(BlockType::Data));
678 assert_eq!(z.compression_enum(), Some(Compression::None));
679}
680
681#[test]
682fn blockref_raw_misaligned_addr_leaks_into_shift() {
683 let mut br = BlockRef::ZERO;
684 br.physical_addr = 0x1003;
685 assert_eq!(br.physical_block_addr(), 0x1000);
686 assert_eq!(br.size_shift(), 3);
687 assert_eq!(br.block_size_log2(), Some(15));
688
689 br.physical_addr = 0x100F;
690 assert_eq!(br.size_shift(), 0xF);
691 assert!(!br.is_valid_size_shift());
692 assert_eq!(br.block_size_log2(), None);
693}
694
695#[test]
696fn blockref_raw_invalid_block_type() {
697 let mut br = BlockRef::ZERO;
698 br.block_type = 99;
699 assert_eq!(br.block_type_enum(), None);
700 br.compression = 77;
701 assert_eq!(br.compression_enum(), None);
702}
703
704proptest! {
705 #[test]
706 fn blockref_addr_roundtrip(
707 addr_high in 0u64..=0x0FFF_FFFF_FFFFu64,
708 size_idx in 0u8..=4u8,
709 ) {
710 let addr = addr_high << 4;
711 let size_log2 = size_idx + BLOCK_SIZE_MIN_LOG2;
712 let br = make_blockref(addr, size_log2, 0);
713 prop_assert_eq!(br.physical_block_addr(), addr);
714 prop_assert_eq!(br.block_size_log2(), Some(size_log2));
715 }
716}
717
718#[test]
719fn superblock_both_valid_a_higher_seq() {
720 let mut a = Superblock::new(1000, 4096);
721 let mut b = Superblock::new(1000, 4096);
722 a.sequence = 5;
723 b.sequence = 3;
724 assert_eq!(select_superblock(&a, &b).sequence, 5);
725 assert_eq!(commit_target(&a, &b), SuperblockSlot::B);
726}
727
728#[test]
729fn superblock_both_valid_b_higher_seq() {
730 let mut a = Superblock::new(1000, 4096);
731 let mut b = Superblock::new(1000, 4096);
732 a.sequence = 3;
733 b.sequence = 5;
734 assert_eq!(select_superblock(&a, &b).sequence, 5);
735 assert_eq!(commit_target(&a, &b), SuperblockSlot::A);
736}
737
738#[test]
739fn superblock_both_valid_equal_seq_selects_a() {
740 let mut a = Superblock::new(1000, 4096);
741 let mut b = Superblock::new(1000, 4096);
742 a.sequence = 5;
743 b.sequence = 5;
744 let selected = select_superblock(&a, &b);
745 assert!(core::ptr::eq(selected, &a));
746 assert_eq!(commit_target(&a, &b), SuperblockSlot::B);
747}
748
749#[test]
750fn superblock_a_valid_b_invalid() {
751 let a = Superblock::new(1000, 4096);
752 let mut b = Superblock::new(1000, 4096);
753 b.magic = 0;
754 let selected = select_superblock(&a, &b);
755 assert!(core::ptr::eq(selected, &a));
756 assert_eq!(commit_target(&a, &b), SuperblockSlot::B);
757}
758
759#[test]
760fn superblock_b_valid_a_invalid() {
761 let mut a = Superblock::new(1000, 4096);
762 let b = Superblock::new(1000, 4096);
763 a.magic = 0;
764 let selected = select_superblock(&a, &b);
765 assert!(core::ptr::eq(selected, &b));
766 assert_eq!(commit_target(&a, &b), SuperblockSlot::A);
767}
768
769#[test]
770fn superblock_both_invalid_falls_back_to_a() {
771 let mut a = Superblock::new(1000, 4096);
772 let mut b = Superblock::new(1000, 4096);
773 a.magic = 0;
774 b.magic = 0;
775 let selected = select_superblock(&a, &b);
776 assert!(core::ptr::eq(selected, &a));
777 assert_eq!(commit_target(&a, &b), SuperblockSlot::A);
778}
779
780#[test]
781fn superblock_commit_target_always_opposite_of_select() {
782 let scenarios: Vec<(u64, u64, bool, bool)> = vec![
783 (5, 3, true, true),
784 (3, 5, true, true),
785 (5, 5, true, true),
786 (0, 0, true, true),
787 (0, 0, true, false),
788 (0, 0, false, true),
789 (0, 0, false, false),
790 (u64::MAX, 0, true, true),
791 (0, u64::MAX, true, true),
792 ];
793
794 scenarios
795 .iter()
796 .for_each(|&(seq_a, seq_b, a_valid, b_valid)| {
797 let mut a = Superblock::new(1000, 4096);
798 let mut b = Superblock::new(1000, 4096);
799 a.sequence = seq_a;
800 b.sequence = seq_b;
801 if !a_valid {
802 a.magic = 0;
803 }
804 if !b_valid {
805 b.magic = 0;
806 }
807
808 let selected = select_superblock(&a, &b);
809 let target = commit_target(&a, &b);
810
811 let selected_is_a = core::ptr::eq(selected, &a);
812 match (a_valid || b_valid, selected_is_a) {
813 (true, true) => assert_eq!(target, SuperblockSlot::B),
814 (true, false) => assert_eq!(target, SuperblockSlot::A),
815 (false, _) => assert_eq!(target, SuperblockSlot::A),
816 }
817 });
818}
819
820#[test]
821fn superblock_next_sequence_overflow() {
822 let mut sb = Superblock::new(1000, 4096);
823 sb.sequence = u64::MAX;
824 assert_eq!(sb.next_sequence(), None);
825 sb.sequence = 0;
826 assert_eq!(sb.next_sequence(), Some(1));
827 sb.sequence = u64::MAX - 1;
828 assert_eq!(sb.next_sequence(), Some(u64::MAX));
829}
830
831#[test]
832fn superblock_next_transaction_overflow() {
833 let mut sb = Superblock::new(1000, 4096);
834 sb.transaction_id = u64::MAX;
835 assert_eq!(sb.next_transaction(), None);
836 sb.transaction_id = 0;
837 assert_eq!(sb.next_transaction(), Some(1));
838}
839
840#[test]
841fn superblock_is_valid_magic_checks() {
842 let valid = Superblock::new(1000, 4096);
843 assert!(valid.is_valid_magic());
844
845 let mut wrong_magic = Superblock::new(1000, 4096);
846 wrong_magic.magic = 0xDEAD;
847 assert!(!wrong_magic.is_valid_magic());
848
849 let mut wrong_version = Superblock::new(1000, 4096);
850 wrong_version.version = 999;
851 assert!(!wrong_version.is_valid_magic());
852
853 let mut both_wrong = Superblock::new(1000, 4096);
854 both_wrong.magic = 0;
855 both_wrong.version = 0;
856 assert!(!both_wrong.is_valid_magic());
857}
858
859#[test]
860fn superblock_slot_block_numbers() {
861 assert_eq!(SuperblockSlot::A.block_number(), 0);
862 assert_eq!(SuperblockSlot::B.block_number(), 1);
863}
864
865#[test]
866fn inode_is_inline_flag() {
867 let file = Inode::new_file(1, 1, 1, 0, 0);
868 assert!(!file.is_inline());
869
870 let symlink = Inode::new_symlink(1, 1, 1, 0, 0, b"target");
871 assert!(symlink.is_inline());
872}
873
874#[test]
875fn inode_inline_data_returns_correct_bytes() {
876 let target = b"/usr/local/bin/foo";
877 let inode = Inode::new_symlink(1, 1, 1, 0, 0, target);
878 assert_eq!(inode.inline_data(), Some(target.as_slice()));
879}
880
881#[test]
882fn inode_inline_data_none_for_non_inline() {
883 assert_eq!(Inode::new_file(1, 1, 1, 0, 0).inline_data(), None);
884 assert_eq!(Inode::new_directory(1, 1, 1, 0, 0).inline_data(), None);
885}
886
887#[test]
888fn inode_new_file_sets_correct_type() {
889 let inode = Inode::new_file(42, 7, 3, 0o644, 1000);
890 assert_eq!(inode.inode_type_enum(), Some(InodeType::File));
891 assert_eq!(inode.object_id, 42);
892 assert_eq!(inode.generation, 7);
893 assert_eq!(inode.transaction_id, 3);
894 assert_eq!(inode.rights_template, 0o644);
895 assert_eq!(inode.create_time, 1000);
896 assert_eq!(inode.modify_time, 1000);
897 assert_eq!(inode.link_count, 1);
898 assert_eq!(
899 inode.compression_policy_enum(),
900 Some(CompressionPolicy::Inherit)
901 );
902}
903
904#[test]
905fn inode_new_directory_sets_correct_type() {
906 let inode = Inode::new_directory(10, 1, 1, 0o755, 500);
907 assert_eq!(inode.inode_type_enum(), Some(InodeType::Directory));
908 assert_eq!(inode.link_count, 1);
909 assert_eq!(
910 inode.compression_policy_enum(),
911 Some(CompressionPolicy::Inherit)
912 );
913}
914
915#[test]
916fn inode_new_symlink_sets_correct_type() {
917 let inode = Inode::new_symlink(5, 1, 1, 0o777, 100, b"target");
918 assert_eq!(inode.inode_type_enum(), Some(InodeType::Symlink));
919 assert_eq!(inode.link_count, 1);
920 assert_eq!(
921 inode.compression_policy_enum(),
922 Some(CompressionPolicy::Disabled)
923 );
924 assert!(inode.is_inline());
925 assert_eq!(inode.size, 6);
926}
927
928#[test]
929fn inode_symlink_max_inline() {
930 let target = [0xABu8; INODE_INLINE_MAX];
931 let inode = Inode::new_symlink(1, 1, 1, 0, 0, &target);
932 let data = inode.inline_data().expect("should be inline");
933 assert_eq!(data.len(), INODE_INLINE_MAX);
934 assert_eq!(data, &target[..]);
935}
936
937#[test]
938fn inode_symlink_empty_target() {
939 let inode = Inode::new_symlink(1, 1, 1, 0, 0, b"");
940 assert!(inode.is_inline());
941 assert_eq!(inode.size, 0);
942 assert_eq!(inode.inline_data(), Some([].as_slice()));
943}
944
945#[test]
946fn inode_inline_size_exceeds_max_clamps() {
947 let mut inode = Inode::new_symlink(1, 1, 1, 0, 0, b"hello");
948 inode.size = u64::MAX;
949 let data = inode.inline_data().expect("should still return Some");
950 assert_eq!(data.len(), INODE_INLINE_MAX);
951}
952
953#[test]
954fn inode_inline_data_byte_accuracy() {
955 let target: Vec<u8> = (0..INODE_INLINE_MAX).map(|i| (i & 0xFF) as u8).collect();
956 let inode = Inode::new_symlink(1, 1, 1, 0, 0, &target);
957 let data = inode.inline_data().expect("should be inline");
958 data.iter()
959 .enumerate()
960 .for_each(|(i, &byte)| assert_eq!(byte, (i & 0xFF) as u8, "mismatch at byte {}", i));
961}
962
963#[test]
964fn inode_invalid_type_returns_none() {
965 let mut inode = Inode::ZERO;
966 inode.inode_type = 255;
967 assert_eq!(inode.inode_type_enum(), None);
968 inode.inode_type = 3;
969 assert_eq!(inode.inode_type_enum(), None);
970}
971
972#[test]
973fn inode_invalid_compression_policy_returns_none() {
974 let mut inode = Inode::ZERO;
975 inode.compression_policy = 255;
976 assert_eq!(inode.compression_policy_enum(), None);
977 inode.compression_policy = 3;
978 assert_eq!(inode.compression_policy_enum(), None);
979}
980
981#[test]
982fn inode_zero_all_fields_default() {
983 let z = Inode::ZERO;
984 assert_eq!(z.inode_type_enum(), Some(InodeType::File));
985 assert_eq!(
986 z.compression_policy_enum(),
987 Some(CompressionPolicy::Inherit)
988 );
989 assert!(!z.is_inline());
990 assert_eq!(z.inline_data(), None);
991 assert_eq!(z.link_count, 0);
992 assert_eq!(z.size, 0);
993}
994
995#[test]
996fn blocktype_from_u8_roundtrip() {
997 assert_eq!(BlockType::from_u8(0), Some(BlockType::Data));
998 assert_eq!(BlockType::from_u8(1), Some(BlockType::Inode));
999 assert_eq!(BlockType::from_u8(2), Some(BlockType::Indirect));
1000 assert_eq!(BlockType::from_u8(3), Some(BlockType::Freemap));
1001 assert_eq!(BlockType::from_u8(4), Some(BlockType::Directory));
1002 assert_eq!(BlockType::from_u8(5), None);
1003 assert_eq!(BlockType::from_u8(u8::MAX), None);
1004}
1005
1006#[test]
1007fn compression_from_u8_roundtrip() {
1008 assert_eq!(Compression::from_u8(0), Some(Compression::None));
1009 assert_eq!(Compression::from_u8(1), Some(Compression::Lz4));
1010 assert_eq!(Compression::from_u8(2), None);
1011 assert_eq!(Compression::from_u8(u8::MAX), None);
1012}
1013
1014#[test]
1015fn inodetype_from_u8_roundtrip() {
1016 assert_eq!(InodeType::from_u8(0), Some(InodeType::File));
1017 assert_eq!(InodeType::from_u8(1), Some(InodeType::Directory));
1018 assert_eq!(InodeType::from_u8(2), Some(InodeType::Symlink));
1019 assert_eq!(InodeType::from_u8(3), None);
1020 assert_eq!(InodeType::from_u8(u8::MAX), None);
1021}
1022
1023#[test]
1024fn compression_policy_from_u8_roundtrip() {
1025 assert_eq!(
1026 CompressionPolicy::from_u8(0),
1027 Some(CompressionPolicy::Inherit)
1028 );
1029 assert_eq!(CompressionPolicy::from_u8(1), Some(CompressionPolicy::Lz4));
1030 assert_eq!(
1031 CompressionPolicy::from_u8(2),
1032 Some(CompressionPolicy::Disabled)
1033 );
1034 assert_eq!(CompressionPolicy::from_u8(3), None);
1035 assert_eq!(CompressionPolicy::from_u8(u8::MAX), None);
1036}