1 // Copyright 2024 The ChromiumOS Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 //! Defines structs for metadata of block groups. 6 7 use std::collections::BTreeMap; 8 9 use anyhow::Result; 10 use zerocopy::AsBytes; 11 use zerocopy_derive::FromBytes; 12 use zerocopy_derive::FromZeroes; 13 14 use crate::arena::Arena; 15 use crate::arena::BlockId; 16 use crate::bitmap::BitMap; 17 use crate::inode::Inode; 18 use crate::inode::InodeNum; 19 use crate::superblock::SuperBlock; 20 21 /// The size of a block in bytes. 22 /// We only support 4K-byte blocks. 23 pub const BLOCK_SIZE: usize = 4096; 24 25 /// A block group descriptor. 26 /// 27 /// See [the specification](https://www.nongnu.org/ext2-doc/ext2.html#block-group-descriptor-table) for the details. 28 #[repr(C)] 29 #[derive(Default, Debug, Copy, Clone, FromZeroes, FromBytes, AsBytes)] 30 pub(crate) struct BlockGroupDescriptor { 31 /// Index of the first block of the block bitmap. 32 pub block_bitmap: u32, 33 /// Index of the first block of the inode bitmap. 34 pub inode_bitmap: u32, 35 /// Index of the first block of the inode table. 36 pub inode_table: u32, 37 /// Number of free blocks. 38 pub free_blocks_count: u16, 39 /// Number of free inodes. 40 pub free_inodes_count: u16, 41 /// Number of directories. 42 pub used_dirs_count: u16, 43 pad: u16, 44 reserved: [u8; 12], 45 } 46 47 pub(crate) struct GroupMetaData<'a> { 48 pub group_desc: &'a mut BlockGroupDescriptor, 49 pub block_bitmap: BitMap<'a>, 50 pub inode_bitmap: BitMap<'a>, 51 52 pub inode_table: BTreeMap<InodeNum, &'a mut Inode>, 53 54 pub first_free_block: u32, 55 pub first_free_inode: u32, 56 } 57 58 impl<'a> GroupMetaData<'a> { 59 // Write GroupMetaData to the first block group. 60 // This data need to be copied to other block gropups' descriptor tables. new(arena: &'a Arena<'a>, sb: &mut SuperBlock, group_id: u16) -> Result<Self>61 pub fn new(arena: &'a Arena<'a>, sb: &mut SuperBlock, group_id: u16) -> Result<Self> { 62 let gd_size = std::mem::size_of::<BlockGroupDescriptor>() as u32; 63 let num_blocks_for_gds = (gd_size * sb.num_groups() as u32).div_ceil(BLOCK_SIZE as u32); 64 65 let inodes_per_block = BLOCK_SIZE as u64 / sb.inode_size as u64; 66 let num_blocks_for_inode_table = 67 (sb.inodes_per_group as usize).div_ceil(inodes_per_block as usize); 68 69 // Allocate a block group descriptor at Block 1. 70 let group_desc = arena.allocate::<BlockGroupDescriptor>( 71 BlockId::from(1), 72 std::mem::size_of::<BlockGroupDescriptor>() * group_id as usize, 73 )?; 74 75 // First blocks for block_bitmap, inode_bitmap, and inode_table. 76 let super_block_id = group_id as u32 * sb.blocks_per_group; 77 let group_desc_id = super_block_id + 1; 78 group_desc.block_bitmap = group_desc_id + num_blocks_for_gds; 79 group_desc.inode_bitmap = group_desc.block_bitmap + 1; 80 group_desc.inode_table = group_desc.inode_bitmap + 1; 81 82 // First free block is the one after inode table. 83 let first_free_block = group_desc.inode_table + num_blocks_for_inode_table as u32; 84 // Free blocks are from `first_free_block` to `blocks_per_group`, inclusive. 85 group_desc.free_blocks_count = 86 (sb.blocks_per_group * (group_id as u32 + 1) - first_free_block) as u16; 87 sb.free_blocks_count += group_desc.free_blocks_count as u32; 88 89 // 10 inodes should be reserved in ext2. 90 let reserved_inode = if group_id == 0 { 10 } else { 0 }; 91 let first_free_inode = group_id as u32 * sb.inodes_per_group + reserved_inode + 1; 92 group_desc.free_inodes_count = sb.inodes_per_group as u16 - reserved_inode as u16; 93 sb.free_inodes_count -= reserved_inode; 94 95 // Initialize block bitmap block. 96 let bmap = arena.allocate::<[u8; BLOCK_SIZE]>(BlockId::from(group_desc.block_bitmap), 0)?; 97 let valid_bmap_bytes = (sb.blocks_per_group / 8) as usize; 98 // Unused parts in the block is marked as 1. 99 bmap[valid_bmap_bytes..].iter_mut().for_each(|x| *x = 0xff); 100 // Interpret the region as BitMap and mask bits for blocks used for metadata. 101 let mut block_bitmap = BitMap::from_slice_mut(&mut bmap[..valid_bmap_bytes]); 102 block_bitmap.mark_first_elems( 103 (first_free_block - group_id as u32 * sb.blocks_per_group) as usize, 104 true, 105 ); 106 107 let imap = arena.allocate::<[u8; BLOCK_SIZE]>(BlockId::from(group_desc.inode_bitmap), 0)?; 108 let valid_imap_bytes = (sb.inodes_per_group / 8) as usize; 109 // Unused parts in the block is marked as 1. 110 imap[valid_imap_bytes..].iter_mut().for_each(|x| *x = 0xff); 111 // Interpret the region as BitMap and mask bits for reserved inodes. 112 let mut inode_bitmap = 113 BitMap::from_slice_mut(&mut imap[..(sb.inodes_per_group / 8) as usize]); 114 inode_bitmap.mark_first_elems(reserved_inode as usize, true); 115 116 Ok(GroupMetaData { 117 group_desc, 118 block_bitmap, 119 inode_bitmap, 120 121 inode_table: BTreeMap::new(), 122 123 first_free_block, 124 first_free_inode, 125 }) 126 } 127 } 128 129 #[cfg(test)] 130 mod test { 131 use base::MemoryMappingBuilder; 132 133 use super::*; 134 use crate::Builder; 135 136 // Check if `GroupMetaData` is correctly initialized from `SuperBlock` with one block group. 137 #[test] test_group_metadata_with_one_block_group()138 fn test_group_metadata_with_one_block_group() { 139 let blocks_per_group = 1024; 140 let num_groups = 1; 141 let size = BLOCK_SIZE as u32 * blocks_per_group * num_groups; 142 let mut mem = MemoryMappingBuilder::new(size as usize).build().unwrap(); 143 let arena = Arena::new(BLOCK_SIZE, &mut mem).unwrap(); 144 let sb = SuperBlock::new( 145 &arena, 146 &Builder { 147 inodes_per_group: 1024, 148 blocks_per_group, 149 size, 150 root_dir: None, 151 }, 152 ) 153 .unwrap(); 154 let group = GroupMetaData::new(&arena, sb, 0).unwrap(); 155 156 assert_eq!(sb.block_group_nr, 1); 157 158 // First a few blocks are used for specific purposes. 159 // Their indexes are arbitrary but we can assume the following values unless we use much 160 // larger parameters: 161 // 0: 1024-byte offset + superblock 162 // 1: group descriptor(s) 163 // 2: block bitmap 164 // 3: inode bitmap 165 // 4+ : inode table 166 assert_eq!(group.group_desc.block_bitmap, 2); 167 assert_eq!(group.group_desc.inode_bitmap, 3); 168 assert_eq!(group.group_desc.inode_table, 4); 169 170 assert_eq!( 171 group.group_desc.free_blocks_count as u32, 172 sb.free_blocks_count 173 ); 174 assert_eq!( 175 group.group_desc.free_inodes_count as u32, 176 sb.free_inodes_count 177 ); 178 assert_eq!(group.block_bitmap.len(), sb.blocks_per_group as usize); 179 assert_eq!( 180 group.block_bitmap.count_zeros(), 181 group.group_desc.free_blocks_count as usize, 182 ); 183 assert_eq!( 184 group.inode_bitmap.count_zeros(), 185 group.group_desc.free_inodes_count as usize, 186 ); 187 } 188 189 #[test] test_group_metadata_with_multiple_block_groups()190 fn test_group_metadata_with_multiple_block_groups() { 191 let blocks_per_group = 1024u32; 192 let num_groups = 10u32; 193 let mem_size = BLOCK_SIZE as u32 * blocks_per_group * num_groups; 194 let mut mem = MemoryMappingBuilder::new(mem_size as usize) 195 .build() 196 .unwrap(); 197 let arena = Arena::new(BLOCK_SIZE, &mut mem).unwrap(); 198 let sb = SuperBlock::new( 199 &arena, 200 &Builder { 201 inodes_per_group: 512, 202 blocks_per_group, 203 size: mem_size, 204 root_dir: None, 205 }, 206 ) 207 .unwrap(); 208 209 let groups = (0..num_groups) 210 .map(|group_id| GroupMetaData::new(&arena, sb, group_id as u16).unwrap()) 211 .collect::<Vec<_>>(); 212 assert_eq!( 213 groups 214 .iter() 215 .map(|gd| gd.group_desc.free_blocks_count as u32) 216 .sum::<u32>(), 217 sb.free_blocks_count 218 ); 219 assert_eq!( 220 groups 221 .iter() 222 .map(|gd| gd.group_desc.free_inodes_count as u32) 223 .sum::<u32>(), 224 sb.free_inodes_count 225 ); 226 } 227 } 228