Nothing to see here, move along meow
1use crate::block_io::BlockIo;
2use crate::error::FsError;
3use crate::freemap::compute_reserved_count;
4use crate::integrity;
5use lancer_core::fs::{
6 BLOCK_SIZE_MIN, BLOCK_SIZE_MIN_LOG2, BTREE_MAX_ENTRIES, BTREE_NODE_SIZE, BTreeNode, BlockRef,
7 BlockType, Compression, FREEMAP_BITS_PER_LEAF, FreemapLeaf, INODE_SIZE, Inode, SUPERBLOCK_SIZE,
8 Superblock,
9};
10use zerocopy::IntoBytes;
11
12const BLOCK_SIZE: usize = BLOCK_SIZE_MIN as usize;
13const ROOT_INODE_OBJECT_ID: u64 = 1;
14const ROOT_INODE_GENERATION: u64 = 1;
15const INITIAL_NEXT_OBJECT_ID: u64 = 2;
16
17pub struct MkfsResult {
18 pub root_inode_block: u64,
19 pub root_object_id: u64,
20 pub root_generation: u64,
21}
22
23pub fn mkfs(bio: &mut BlockIo, total_blocks: u64) -> Result<MkfsResult, FsError> {
24 let reserved_count = compute_reserved_count(total_blocks);
25 let data_region_start = 2 + reserved_count;
26 let total_data_blocks = total_blocks.saturating_sub(data_region_start);
27 let freemap_leaves_needed = total_data_blocks.div_ceil(FREEMAP_BITS_PER_LEAF as u64);
28
29 let root_inode_block = data_region_start;
30 let metadata_leaf_block = root_inode_block + 1;
31
32 let root_inode = Inode::new_directory(ROOT_INODE_OBJECT_ID, ROOT_INODE_GENERATION, 0, 0, 0);
33 let mut inode_block_data = [0u8; BLOCK_SIZE];
34 inode_block_data[..INODE_SIZE].copy_from_slice(root_inode.as_bytes());
35 write_block(bio, root_inode_block, &inode_block_data)?;
36
37 let inode_hashes = integrity::compute_block_hashes(&inode_block_data);
38 let tree_root_ref = BlockRef::new(
39 crate::block_num_to_phys(root_inode_block),
40 BLOCK_SIZE_MIN_LOG2,
41 ROOT_INODE_OBJECT_ID,
42 0,
43 inode_hashes.content_hash,
44 inode_hashes.integrity_crc,
45 BlockType::Inode,
46 Compression::None,
47 0,
48 0,
49 );
50
51 let metadata_root = {
52 let mut leaf = BTreeNode::new(0);
53 leaf.entries[0] = tree_root_ref;
54 leaf.header.entry_count = 1;
55 let leaf_bytes: &[u8; BTREE_NODE_SIZE] = leaf.as_bytes().try_into().unwrap();
56 write_block(bio, metadata_leaf_block, leaf_bytes)?;
57
58 let leaf_hashes = integrity::compute_block_hashes(leaf_bytes);
59 BlockRef::new(
60 crate::block_num_to_phys(metadata_leaf_block),
61 BLOCK_SIZE_MIN_LOG2,
62 0,
63 0,
64 leaf_hashes.content_hash,
65 leaf_hashes.integrity_crc,
66 BlockType::Indirect,
67 Compression::None,
68 0,
69 0,
70 )
71 };
72
73 let mut freemap_leaf = FreemapLeaf::ZERO;
74 freemap_leaf.set_bit(0);
75 freemap_leaf.set_bit(1);
76
77 let freemap_leaf_bytes: &[u8; BTREE_NODE_SIZE] = freemap_leaf.as_bytes().try_into().unwrap();
78 let freemap_leaf_block = reserved_count_to_freemap_leaf_block(reserved_count);
79 write_block(bio, freemap_leaf_block, freemap_leaf_bytes)?;
80
81 let freemap_leaf_hashes = integrity::compute_block_hashes(freemap_leaf_bytes);
82 let freemap_leaf_ref = BlockRef::new(
83 crate::block_num_to_phys(freemap_leaf_block),
84 BLOCK_SIZE_MIN_LOG2,
85 0,
86 0,
87 freemap_leaf_hashes.content_hash,
88 freemap_leaf_hashes.integrity_crc,
89 BlockType::Freemap,
90 Compression::None,
91 0,
92 0,
93 );
94
95 let freemap_root_ref = match freemap_leaves_needed <= 1 {
96 true => {
97 let mut root_node = BTreeNode::new(0);
98 root_node.entries[0] = freemap_leaf_ref;
99 root_node.header.entry_count = 1;
100 let root_bytes: &[u8; BTREE_NODE_SIZE] = root_node.as_bytes().try_into().unwrap();
101 let root_block = freemap_leaf_block + 1;
102 write_block(bio, root_block, root_bytes)?;
103
104 let root_hashes = integrity::compute_block_hashes(root_bytes);
105 BlockRef::new(
106 crate::block_num_to_phys(root_block),
107 BLOCK_SIZE_MIN_LOG2,
108 0,
109 0,
110 root_hashes.content_hash,
111 root_hashes.integrity_crc,
112 BlockType::Freemap,
113 Compression::None,
114 0,
115 0,
116 )
117 }
118 false => build_freemap_tree(
119 bio,
120 freemap_leaf_block,
121 freemap_leaves_needed,
122 &freemap_leaf_ref,
123 )?,
124 };
125
126 let mut sb = Superblock::new(total_blocks, BLOCK_SIZE_MIN);
127 sb.sequence = 0;
128 sb.transaction_id = 0;
129 sb.tree_root = metadata_root;
130 sb.freemap_root = freemap_root_ref;
131 sb.dedup_roots = [BlockRef::ZERO; lancer_core::fs::DEDUP_SHARDS];
132 sb.snapshot_root = BlockRef::ZERO;
133 sb.scrub_cursor = 0;
134 sb.next_object_id = INITIAL_NEXT_OBJECT_ID;
135 sb.checksum = 0;
136
137 let mut sb_bytes = [0u8; SUPERBLOCK_SIZE];
138 sb_bytes[..SUPERBLOCK_SIZE].copy_from_slice(sb.as_bytes());
139 let checksum = integrity::crc32c(&sb_bytes[..SUPERBLOCK_SIZE - 4]);
140 sb_bytes[SUPERBLOCK_SIZE - 4..].copy_from_slice(&checksum.to_le_bytes());
141
142 write_block_raw(bio, 0, &sb_bytes)?;
143 write_block_raw(bio, 1, &sb_bytes)?;
144
145 bio.flush()?;
146
147 Ok(MkfsResult {
148 root_inode_block,
149 root_object_id: ROOT_INODE_OBJECT_ID,
150 root_generation: ROOT_INODE_GENERATION,
151 })
152}
153
154fn reserved_count_to_freemap_leaf_block(_reserved_count: u64) -> u64 {
155 2
156}
157
158fn build_freemap_tree(
159 bio: &mut BlockIo,
160 first_leaf_block: u64,
161 leaf_count: u64,
162 first_leaf_ref: &BlockRef,
163) -> Result<BlockRef, FsError> {
164 let empty_leaf_bytes = FreemapLeaf::ZERO.as_bytes();
165 let empty_leaf_arr: &[u8; BTREE_NODE_SIZE] = empty_leaf_bytes.try_into().unwrap();
166 let empty_hashes = integrity::compute_block_hashes(empty_leaf_arr);
167
168 (1..leaf_count).try_for_each(|i| write_block(bio, first_leaf_block + i, empty_leaf_arr))?;
169
170 let mut item_start = first_leaf_block;
171 let mut item_count = leaf_count;
172 let mut next_free = first_leaf_block + leaf_count;
173 let mut btree_level: u8 = 0;
174 let mut grouping_leaves = true;
175
176 loop {
177 let node_count = item_count.div_ceil(BTREE_MAX_ENTRIES as u64);
178 let node_start = next_free;
179
180 (0..node_count).try_for_each(|n| {
181 let child_offset = n * BTREE_MAX_ENTRIES as u64;
182 let children = (item_count - child_offset).min(BTREE_MAX_ENTRIES as u64) as usize;
183
184 let mut node = BTreeNode::new(btree_level);
185 (0..children).try_for_each(|c| {
186 let child_global = child_offset + c as u64;
187 let child_block = item_start + child_global;
188
189 let (content_hash, integrity_crc) = match grouping_leaves {
190 true => match child_global {
191 0 => (
192 first_leaf_ref.content_hash_u128(),
193 first_leaf_ref.integrity_crc,
194 ),
195 _ => (empty_hashes.content_hash, empty_hashes.integrity_crc),
196 },
197 false => {
198 let mut buf = [0u8; BLOCK_SIZE];
199 bio.read_blocks(child_block, 1, &mut buf)?;
200 let h = integrity::compute_block_hashes(&buf);
201 (h.content_hash, h.integrity_crc)
202 }
203 };
204
205 let subtree_span = (0..btree_level as u32)
206 .fold(1u64, |acc, _| acc.saturating_mul(BTREE_MAX_ENTRIES as u64));
207 let key = child_global * subtree_span;
208
209 node.entries[c] = BlockRef::new(
210 crate::block_num_to_phys(child_block),
211 BLOCK_SIZE_MIN_LOG2,
212 key,
213 0,
214 content_hash,
215 integrity_crc,
216 BlockType::Freemap,
217 Compression::None,
218 0,
219 0,
220 );
221 Ok::<(), FsError>(())
222 })?;
223
224 node.header.entry_count = children as u16;
225 let node_bytes: &[u8; BTREE_NODE_SIZE] = node.as_bytes().try_into().unwrap();
226 write_block(bio, node_start + n, node_bytes)
227 })?;
228
229 match node_count {
230 1 => {
231 let mut buf = [0u8; BLOCK_SIZE];
232 bio.read_blocks(node_start, 1, &mut buf)?;
233 let hashes = integrity::compute_block_hashes(&buf);
234 return Ok(BlockRef::new(
235 crate::block_num_to_phys(node_start),
236 BLOCK_SIZE_MIN_LOG2,
237 0,
238 0,
239 hashes.content_hash,
240 hashes.integrity_crc,
241 BlockType::Freemap,
242 Compression::None,
243 0,
244 0,
245 ));
246 }
247 _ => {
248 item_start = node_start;
249 item_count = node_count;
250 next_free = node_start + node_count;
251 grouping_leaves = false;
252 btree_level += 1;
253 }
254 }
255 }
256}
257
258fn write_block(bio: &mut BlockIo, block_num: u64, data: &[u8; BLOCK_SIZE]) -> Result<(), FsError> {
259 bio.write_blocks(block_num, 1, data)
260}
261
262fn write_block_raw(bio: &mut BlockIo, block_num: u64, data: &[u8]) -> Result<(), FsError> {
263 bio.write_blocks(block_num, 1, data)
264}
265
266#[cfg(test)]
267mod tests {
268 use super::*;
269 use crate::commit;
270 use crate::test_helpers;
271
272 #[test]
273 fn mkfs_creates_valid_superblocks() {
274 let mut bio = test_helpers::make_bio(1024);
275 let result = mkfs(&mut bio, 1024).unwrap();
276
277 let mut buf = [0u8; SUPERBLOCK_SIZE];
278 bio.read_blocks(0, 1, &mut buf).unwrap();
279 let sb_a: Superblock =
280 unsafe { core::ptr::read_unaligned(buf.as_ptr() as *const Superblock) };
281 assert!(sb_a.is_valid_magic());
282 assert!(commit::verify_superblock_crc(&sb_a));
283 assert_eq!(sb_a.total_blocks, 1024);
284 assert_eq!(sb_a.sequence, 0);
285 assert_eq!(sb_a.transaction_id, 0);
286 assert_eq!(sb_a.next_object_id, INITIAL_NEXT_OBJECT_ID);
287
288 bio.read_blocks(1, 1, &mut buf).unwrap();
289 let sb_b: Superblock =
290 unsafe { core::ptr::read_unaligned(buf.as_ptr() as *const Superblock) };
291 assert!(sb_b.is_valid_magic());
292 assert!(commit::verify_superblock_crc(&sb_b));
293
294 assert!(!sb_a.tree_root.is_null());
295 assert!(!sb_a.freemap_root.is_null());
296 assert!(sb_a.dedup_roots.iter().all(|r| r.is_null()));
297 assert!(sb_a.snapshot_root.is_null());
298
299 assert_eq!(result.root_object_id, 1);
300 assert_eq!(result.root_generation, 1);
301 }
302
303 #[test]
304 fn mkfs_root_inode_is_directory() {
305 let mut bio = test_helpers::make_bio(1024);
306 let result = mkfs(&mut bio, 1024).unwrap();
307
308 let mut buf = [0u8; BLOCK_SIZE];
309 bio.read_blocks(result.root_inode_block, 1, &mut buf)
310 .unwrap();
311 let inode: Inode = unsafe { core::ptr::read_unaligned(buf.as_ptr() as *const Inode) };
312 assert_eq!(inode.object_id, 1);
313 assert_eq!(inode.generation, 1);
314 assert_eq!(
315 inode.inode_type_enum(),
316 Some(lancer_core::fs::InodeType::Directory)
317 );
318 }
319
320 #[test]
321 fn mkfs_can_mount() {
322 let mut bio = test_helpers::make_bio(1024);
323 mkfs(&mut bio, 1024).unwrap();
324
325 let mut buf = [0u8; SUPERBLOCK_SIZE];
326 bio.read_blocks(0, 1, &mut buf).unwrap();
327 let sb: Superblock =
328 unsafe { core::ptr::read_unaligned(buf.as_ptr() as *const Superblock) };
329
330 let freemap = crate::freemap::FreemapAllocator::init(&sb);
331 assert!(freemap.total_data_blocks() > 0);
332 }
333
334 #[test]
335 fn mkfs_freemap_integrity_matches() {
336 let mut bio = test_helpers::make_bio(1024);
337 mkfs(&mut bio, 1024).unwrap();
338
339 let mut sb_buf = [0u8; SUPERBLOCK_SIZE];
340 bio.read_blocks(0, 1, &mut sb_buf).unwrap();
341 let sb: Superblock =
342 unsafe { core::ptr::read_unaligned(sb_buf.as_ptr() as *const Superblock) };
343
344 let freemap_root_block = crate::blockref_block_num(&sb.freemap_root);
345 let mut node_buf = [0u8; BLOCK_SIZE];
346 bio.read_blocks(freemap_root_block, 1, &mut node_buf)
347 .unwrap();
348
349 let root_crc = integrity::crc32c(&node_buf);
350 assert_eq!(root_crc, sb.freemap_root.integrity_crc);
351
352 let node: BTreeNode =
353 unsafe { core::ptr::read_unaligned(node_buf.as_ptr() as *const BTreeNode) };
354 let leaf_ref = node.entries[0];
355 let leaf_block = crate::blockref_block_num(&leaf_ref);
356
357 let mut leaf_buf = [0u8; BLOCK_SIZE];
358 bio.read_blocks(leaf_block, 1, &mut leaf_buf).unwrap();
359 let leaf_crc = integrity::crc32c(&leaf_buf);
360 assert_eq!(leaf_crc, leaf_ref.integrity_crc);
361 }
362}