lewis.moe
Nothing to see here, move along
1use crate::block_io::BlockIo;
2use crate::btree::{self, BTreeIter};
3use crate::cache::BlockCache;
4use crate::error::FsError;
5use crate::integrity::xxhash64;
6use crate::pool::NodePool;
7use lancer_core::fs::{BLOCK_SIZE_MIN_LOG2, BlockRef, BlockType, Compression, Inode};
8use zerocopy::IntoBytes;
9
10const MAX_COLLISION_SLOTS: u64 = 8;
11const INLINE_NAME_MAX: usize = 34;
12
13const DIR_INLINE_NAME: u8 = 0x01;
14const DIR_COLLISION: u8 = 0x02;
15
16const NAME_REGIONS: [(usize, usize); 4] = [(24, 16), (40, 4), (49, 1), (51, 13)];
17
18pub fn dir_entry_key(name: &[u8]) -> u64 {
19 xxhash64(name) & !0xF
20}
21
22pub fn new_dir_entry(child_phys_addr: u64, name: &[u8], txn: u64, collision: bool) -> BlockRef {
23 let flags = match (name.len() <= INLINE_NAME_MAX, collision) {
24 (true, true) => DIR_INLINE_NAME | DIR_COLLISION,
25 (true, false) => DIR_INLINE_NAME,
26 (false, true) => DIR_COLLISION,
27 (false, false) => 0,
28 };
29
30 let mut entry = BlockRef::new(
31 child_phys_addr & !0xF,
32 BLOCK_SIZE_MIN_LOG2,
33 0,
34 txn,
35 0u128,
36 0u32,
37 BlockType::Directory,
38 Compression::None,
39 name.len() as u32,
40 flags,
41 );
42
43 if name.len() <= INLINE_NAME_MAX {
44 pack_inline_name(&mut entry, name);
45 }
46
47 entry
48}
49
50pub fn pack_inline_name(entry: &mut BlockRef, name: &[u8]) {
51 let bytes = entry.as_mut_bytes();
52 NAME_REGIONS.iter().fold(0usize, |offset, &(start, len)| {
53 let remaining = name.len().saturating_sub(offset);
54 let n = remaining.min(len);
55 match n {
56 0 => offset,
57 _ => {
58 bytes[start..start + n].copy_from_slice(&name[offset..offset + n]);
59 offset + n
60 }
61 }
62 });
63}
64
65pub fn unpack_inline_name(entry: &BlockRef, buf: &mut [u8]) -> usize {
66 let bytes = entry.as_bytes();
67 let name_len = (entry.logical_size as usize)
68 .min(INLINE_NAME_MAX)
69 .min(buf.len());
70 NAME_REGIONS.iter().fold(0usize, |written, &(start, len)| {
71 let remaining = name_len.saturating_sub(written);
72 let n = remaining.min(len);
73 match n {
74 0 => written,
75 _ => {
76 buf[written..written + n].copy_from_slice(&bytes[start..start + n]);
77 written + n
78 }
79 }
80 })
81}
82
83pub fn dir_entry_matches(
84 entry: &BlockRef,
85 name: &[u8],
86 cache: &mut BlockCache,
87 bio: &mut BlockIo,
88) -> Result<bool, FsError> {
89 let stored_len = entry.logical_size as usize;
90 match stored_len != name.len() {
91 true => Ok(false),
92 false => match entry.flags & DIR_INLINE_NAME != 0 {
93 true => {
94 let mut buf = [0u8; INLINE_NAME_MAX];
95 let unpacked = unpack_inline_name(entry, &mut buf);
96 Ok(&buf[..unpacked] == name)
97 }
98 false => {
99 let block_num = crate::blockref_block_num(entry);
100 let data = cache.cache_read(bio, block_num)?;
101 let inode: Inode =
102 unsafe { core::ptr::read_unaligned(data.as_ptr() as *const Inode) };
103 Ok(&inode.extended_attrs[..stored_len] == name)
104 }
105 },
106 }
107}
108
109enum LookupSignal {
110 Found(BlockRef),
111 Fs(FsError),
112}
113
114pub fn dir_lookup(
115 pool: &mut NodePool,
116 cache: &mut BlockCache,
117 bio: &mut BlockIo,
118 dir_inode: &Inode,
119 name: &[u8],
120 txn_filter: Option<u64>,
121) -> Result<Option<BlockRef>, FsError> {
122 let base = dir_entry_key(name);
123 let root = dir_inode.direct[0];
124
125 scan_collision_slots(pool, cache, bio, &root, name, base, 0, txn_filter)
126}
127
128#[allow(clippy::too_many_arguments)]
129fn scan_collision_slots(
130 pool: &mut NodePool,
131 cache: &mut BlockCache,
132 bio: &mut BlockIo,
133 root: &BlockRef,
134 name: &[u8],
135 base_key: u64,
136 start_slot: u64,
137 txn_filter: Option<u64>,
138) -> Result<Option<BlockRef>, FsError> {
139 let result = (start_slot..MAX_COLLISION_SLOTS).try_fold((), |(), slot| {
140 let entry = btree::btree_lookup(pool, cache, bio, root, base_key | slot, txn_filter)
141 .map_err(LookupSignal::Fs)?;
142 match entry {
143 None => Ok(()),
144 Some(e) => match dir_entry_matches(&e, name, cache, bio).map_err(LookupSignal::Fs)? {
145 true => Err(LookupSignal::Found(e)),
146 false => Ok(()),
147 },
148 }
149 });
150 match result {
151 Ok(()) => Ok(None),
152 Err(LookupSignal::Found(e)) => Ok(Some(e)),
153 Err(LookupSignal::Fs(e)) => Err(e),
154 }
155}
156
157fn find_insert_slot(
158 pool: &mut NodePool,
159 cache: &mut BlockCache,
160 bio: &mut BlockIo,
161 root: &BlockRef,
162 name: &[u8],
163 base_key: u64,
164) -> Result<u64, FsError> {
165 match root.is_null() {
166 true => Ok(0),
167 false => match btree::btree_lookup(pool, cache, bio, root, base_key, None)? {
168 None => Ok(0),
169 Some(entry) => match dir_entry_matches(&entry, name, cache, bio)? {
170 true => Err(FsError::FileExists),
171 false => scan_for_free_slot(pool, cache, bio, root, name, base_key, 1),
172 },
173 },
174 }
175}
176
177fn scan_for_free_slot(
178 pool: &mut NodePool,
179 cache: &mut BlockCache,
180 bio: &mut BlockIo,
181 root: &BlockRef,
182 name: &[u8],
183 base_key: u64,
184 start_slot: u64,
185) -> Result<u64, FsError> {
186 (start_slot..MAX_COLLISION_SLOTS)
187 .try_fold(None::<u64>, |first_free, slot| {
188 match btree::btree_lookup(pool, cache, bio, root, base_key | slot, None)? {
189 None => Ok(first_free.or(Some(slot))),
190 Some(entry) => match dir_entry_matches(&entry, name, cache, bio)? {
191 true => Err(FsError::FileExists),
192 false => Ok(first_free),
193 },
194 }
195 })?
196 .ok_or(FsError::TreeFull)
197}
198
199pub fn dir_insert(
200 pool: &mut NodePool,
201 cache: &mut BlockCache,
202 bio: &mut BlockIo,
203 dir_inode: &Inode,
204 name: &[u8],
205 child_phys_addr: u64,
206 txn: u64,
207) -> Result<Inode, FsError> {
208 let base = dir_entry_key(name);
209 let root = dir_inode.direct[0];
210
211 let slot = find_insert_slot(pool, cache, bio, &root, name, base)?;
212 let entry = new_dir_entry(child_phys_addr, name, txn, slot > 0);
213 let new_root = btree::btree_insert(pool, cache, bio, &root, base | slot, entry, txn)?;
214
215 let mut updated = dir_inode.clone();
216 updated.direct[0] = new_root;
217 updated.transaction_id = txn;
218 Ok(updated)
219}
220
221pub fn dir_remove(
222 pool: &mut NodePool,
223 cache: &mut BlockCache,
224 bio: &mut BlockIo,
225 dir_inode: &Inode,
226 name: &[u8],
227 txn: u64,
228) -> Result<Inode, FsError> {
229 let base = dir_entry_key(name);
230 let root = dir_inode.direct[0];
231
232 let (slot, _entry) = find_matching_slot(pool, cache, bio, &root, name, base)?;
233
234 let new_root =
235 btree::btree_delete(pool, cache, bio, &root, base | slot, txn)?.unwrap_or(BlockRef::ZERO);
236
237 let mut updated = dir_inode.clone();
238 updated.direct[0] = new_root;
239 updated.transaction_id = txn;
240 Ok(updated)
241}
242
243enum MatchSignal {
244 Found(u64, BlockRef),
245 Fs(FsError),
246}
247
248fn find_matching_slot(
249 pool: &mut NodePool,
250 cache: &mut BlockCache,
251 bio: &mut BlockIo,
252 root: &BlockRef,
253 name: &[u8],
254 base_key: u64,
255) -> Result<(u64, BlockRef), FsError> {
256 let result = (0..MAX_COLLISION_SLOTS).try_fold((), |(), slot| {
257 let entry = btree::btree_lookup(pool, cache, bio, root, base_key | slot, None)
258 .map_err(MatchSignal::Fs)?;
259 match entry {
260 None => Ok(()),
261 Some(e) => match dir_entry_matches(&e, name, cache, bio).map_err(MatchSignal::Fs)? {
262 true => Err(MatchSignal::Found(slot, e)),
263 false => Ok(()),
264 },
265 }
266 });
267 match result {
268 Err(MatchSignal::Found(slot, entry)) => Ok((slot, entry)),
269 Err(MatchSignal::Fs(e)) => Err(e),
270 Ok(()) => Err(FsError::NotFound),
271 }
272}
273
274pub fn dir_list(dir_inode: &Inode, txn_filter: Option<u64>) -> BTreeIter {
275 btree::btree_range(&dir_inode.direct[0], 0, u64::MAX, txn_filter)
276}
277
278#[cfg(test)]
279mod tests {
280 use super::*;
281 #[test]
282 fn dir_entry_key_deterministic() {
283 assert_eq!(dir_entry_key(b"hello"), dir_entry_key(b"hello"));
284 }
285
286 #[test]
287 fn dir_entry_key_different_names_differ() {
288 assert_ne!(dir_entry_key(b"file_a"), dir_entry_key(b"file_b"));
289 }
290
291 #[test]
292 fn dir_entry_key_low_nibble_cleared() {
293 let key = dir_entry_key(b"anything");
294 assert_eq!(key & 0xF, 0);
295 }
296
297 #[test]
298 fn pack_unpack_short_name() {
299 let name = b"hi";
300 let entry = new_dir_entry(0x1000, name, 1, false);
301 let mut buf = [0u8; INLINE_NAME_MAX];
302 let len = unpack_inline_name(&entry, &mut buf);
303 assert_eq!(len, 2);
304 assert_eq!(&buf[..len], b"hi");
305 }
306
307 #[test]
308 fn pack_unpack_max_inline_name() {
309 let name: Vec<u8> = (0..INLINE_NAME_MAX)
310 .map(|i| (i as u8 % 26) + b'a')
311 .collect();
312 let entry = new_dir_entry(0x2000, &name, 1, false);
313 let mut buf = [0u8; INLINE_NAME_MAX];
314 let len = unpack_inline_name(&entry, &mut buf);
315 assert_eq!(len, INLINE_NAME_MAX);
316 assert_eq!(&buf[..len], &name[..]);
317 }
318
319 #[test]
320 fn pack_unpack_single_byte_name() {
321 let name = b"x";
322 let entry = new_dir_entry(0x3000, name, 1, false);
323 let mut buf = [0u8; INLINE_NAME_MAX];
324 let len = unpack_inline_name(&entry, &mut buf);
325 assert_eq!(len, 1);
326 assert_eq!(buf[0], b'x');
327 }
328
329 #[test]
330 fn pack_unpack_name_at_each_region_boundary() {
331 [1, 16, 17, 20, 21, 22, 34].iter().for_each(|&name_len| {
332 let name: Vec<u8> = (0..name_len).map(|i| (i as u8 % 26) + b'A').collect();
333 let entry = new_dir_entry(0x4000, &name, 1, false);
334 let mut buf = [0u8; INLINE_NAME_MAX];
335 let len = unpack_inline_name(&entry, &mut buf);
336 assert_eq!(len, name_len, "wrong len for name_len={}", name_len);
337 assert_eq!(&buf[..len], &name[..], "mismatch for name_len={}", name_len);
338 });
339 }
340
341 #[test]
342 fn new_dir_entry_sets_inline_flag() {
343 let short = new_dir_entry(0x1000, b"short", 1, false);
344 assert_ne!(short.flags & DIR_INLINE_NAME, 0);
345 }
346
347 #[test]
348 fn new_dir_entry_collision_flag() {
349 let no_col = new_dir_entry(0x1000, b"test", 1, false);
350 assert_eq!(no_col.flags & DIR_COLLISION, 0);
351
352 let with_col = new_dir_entry(0x1000, b"test", 1, true);
353 assert_ne!(with_col.flags & DIR_COLLISION, 0);
354 }
355
356 #[test]
357 fn new_dir_entry_long_name_no_inline_flag() {
358 let long: Vec<u8> = (0..INLINE_NAME_MAX + 1)
359 .map(|i| (i as u8 % 26) + b'a')
360 .collect();
361 let entry = new_dir_entry(0x5000, &long, 1, false);
362 assert_eq!(entry.flags & DIR_INLINE_NAME, 0);
363 }
364
365 #[test]
366 fn new_dir_entry_stores_logical_size() {
367 let entry = new_dir_entry(0x1000, b"hello", 1, false);
368 assert_eq!(entry.logical_size, 5);
369 }
370
371 #[test]
372 fn dir_entry_matches_inline_match() {
373 let mut bio = crate::test_helpers::make_bio(32);
374 let mut cache = crate::test_helpers::make_cache();
375 let name = b"test.txt";
376 let entry = new_dir_entry(0x1000, name, 1, false);
377 assert!(dir_entry_matches(&entry, name, &mut cache, &mut bio).unwrap());
378 }
379
380 #[test]
381 fn dir_entry_matches_inline_mismatch() {
382 let mut bio = crate::test_helpers::make_bio(32);
383 let mut cache = crate::test_helpers::make_cache();
384 let entry = new_dir_entry(0x1000, b"alpha", 1, false);
385 assert!(!dir_entry_matches(&entry, b"omega", &mut cache, &mut bio).unwrap());
386 }
387
388 #[test]
389 fn dir_entry_matches_length_mismatch() {
390 let mut bio = crate::test_helpers::make_bio(32);
391 let mut cache = crate::test_helpers::make_cache();
392 let entry = new_dir_entry(0x1000, b"ab", 1, false);
393 assert!(!dir_entry_matches(&entry, b"abc", &mut cache, &mut bio).unwrap());
394 }
395}
396
397pub fn dir_is_empty(
398 pool: &mut NodePool,
399 cache: &mut BlockCache,
400 bio: &mut BlockIo,
401 dir_inode: &Inode,
402) -> Result<bool, FsError> {
403 let mut iter = btree::btree_range(&dir_inode.direct[0], 0, u64::MAX, None);
404 match iter.next(pool, cache, bio)? {
405 None => Ok(true),
406 Some(_) => Ok(false),
407 }
408}