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