lewis.moe
Nothing to see here, move along
1use crate::block_io::BlockIo;
2use crate::btree;
3use crate::cache::BlockCache;
4use crate::error::FsError;
5use crate::pool::NodePool;
6use lancer_core::fs::BlockRef;
7
8pub enum DedupResult {
9 Reused(BlockRef),
10 Unique,
11}
12
13pub fn dedup_check(
14 pool: &mut NodePool,
15 cache: &mut BlockCache,
16 bio: &mut BlockIo,
17 dedup_root: &BlockRef,
18 content_hash: u128,
19) -> Result<DedupResult, FsError> {
20 let key = dedup_key(content_hash);
21
22 let existing = btree::btree_lookup(pool, cache, bio, dedup_root, key, None)?;
23
24 match existing {
25 None => Ok(DedupResult::Unique),
26 Some(ref entry) => match entry.content_hash_u128() == content_hash {
27 true => Ok(DedupResult::Reused(*entry)),
28 false => Ok(DedupResult::Unique),
29 },
30 }
31}
32
33pub fn dedup_insert(
34 pool: &mut NodePool,
35 cache: &mut BlockCache,
36 bio: &mut BlockIo,
37 dedup_root: &BlockRef,
38 content_hash: u128,
39 block_ref: &BlockRef,
40 txn: u64,
41) -> Result<BlockRef, FsError> {
42 let key = dedup_key(content_hash);
43
44 let mut entry = *block_ref;
45 entry.content_hash = content_hash.to_le_bytes();
46
47 match btree::btree_insert(pool, cache, bio, dedup_root, key, entry, txn) {
48 Err(FsError::DuplicateKey) => Ok(*dedup_root),
49 other => other,
50 }
51}
52
53pub fn dedup_shard(content_hash: u128) -> usize {
54 (content_hash >> 124) as usize & 0xF
55}
56
57fn dedup_key(hash: u128) -> u64 {
58 (hash >> 64) as u64
59}
60
61#[cfg(test)]
62mod tests {
63 use super::*;
64
65 #[test]
66 fn dedup_key_extracts_upper_64() {
67 let hash: u128 = 0xDEAD_BEEF_CAFE_BABE_1234_5678_9ABC_DEF0;
68 assert_eq!(dedup_key(hash), 0xDEAD_BEEF_CAFE_BABE);
69 }
70
71 #[test]
72 fn dedup_key_zero_hash() {
73 assert_eq!(dedup_key(0), 0);
74 }
75
76 #[test]
77 fn dedup_key_max_hash() {
78 assert_eq!(dedup_key(u128::MAX), u64::MAX);
79 }
80
81 #[test]
82 fn dedup_key_lower_half_ignored() {
83 let a: u128 = 0xAAAA_BBBB_CCCC_DDDD_0000_0000_0000_0001;
84 let b: u128 = 0xAAAA_BBBB_CCCC_DDDD_FFFF_FFFF_FFFF_FFFF;
85 assert_eq!(dedup_key(a), dedup_key(b));
86 }
87
88 #[test]
89 fn dedup_shard_extracts_top_4_bits() {
90 let hash: u128 = 0xA000_0000_0000_0000_0000_0000_0000_0000;
91 assert_eq!(dedup_shard(hash), 0xA);
92 }
93
94 #[test]
95 fn dedup_shard_zero() {
96 assert_eq!(dedup_shard(0), 0);
97 }
98
99 #[test]
100 fn dedup_shard_max() {
101 assert_eq!(dedup_shard(u128::MAX), 0xF);
102 }
103
104 #[test]
105 fn dedup_shard_all_values() {
106 (0u8..16).for_each(|s| {
107 let hash = (s as u128) << 124;
108 assert_eq!(dedup_shard(hash), s as usize);
109 });
110 }
111
112 #[test]
113 fn dedup_check_empty_tree_returns_unique() {
114 let mut pool = crate::test_helpers::make_pool();
115 let mut cache = crate::test_helpers::make_cache();
116 let mut bio = crate::test_helpers::make_bio(256);
117
118 let result = dedup_check(
119 &mut pool,
120 &mut cache,
121 &mut bio,
122 &BlockRef::ZERO,
123 0x1234_5678_9ABC_DEF0,
124 )
125 .unwrap();
126 match result {
127 DedupResult::Unique => {}
128 DedupResult::Reused(_) => panic!("expected Unique on empty tree"),
129 }
130 }
131}