// Copyright 2024 The ChromiumOS Authors // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. //! Defines structs for metadata of block groups. use std::collections::BTreeMap; use anyhow::Result; use zerocopy::FromBytes; use zerocopy::Immutable; use zerocopy::IntoBytes; use zerocopy::KnownLayout; use crate::arena::Arena; use crate::arena::BlockId; use crate::bitmap::BitMap; use crate::inode::Inode; use crate::inode::InodeNum; use crate::superblock::SuperBlock; /// The size of a block in bytes. /// We only support 4K-byte blocks. pub const BLOCK_SIZE: usize = 4096; /// A block group descriptor. /// /// See [the specification](https://www.nongnu.org/ext2-doc/ext2.html#block-group-descriptor-table) for the details. #[repr(C)] #[derive(Default, Debug, Copy, Clone, FromBytes, Immutable, IntoBytes, KnownLayout)] pub(crate) struct BlockGroupDescriptor { /// Index of the first block of the block bitmap. pub block_bitmap: u32, /// Index of the first block of the inode bitmap. pub inode_bitmap: u32, /// Index of the first block of the inode table. pub inode_table: u32, /// Number of free blocks. pub free_blocks_count: u16, /// Number of free inodes. pub free_inodes_count: u16, /// Number of directories. pub used_dirs_count: u16, pad: u16, reserved: [u8; 12], } pub(crate) struct GroupMetaData<'a> { pub group_desc: &'a mut BlockGroupDescriptor, pub block_bitmap: BitMap<'a>, pub inode_bitmap: BitMap<'a>, pub inode_table: BTreeMap, pub first_free_block: u32, pub first_free_inode: u32, } impl<'a> GroupMetaData<'a> { // Write GroupMetaData to the first block group. // This data need to be copied to other block gropups' descriptor tables. pub fn new(arena: &'a Arena<'a>, sb: &mut SuperBlock, group_id: u16) -> Result { let gd_size = std::mem::size_of::() as u32; let num_blocks_for_gds = (gd_size * sb.num_groups() as u32).div_ceil(BLOCK_SIZE as u32); let inodes_per_block = BLOCK_SIZE as u64 / sb.inode_size as u64; let num_blocks_for_inode_table = (sb.inodes_per_group as usize).div_ceil(inodes_per_block as usize); // Allocate a block group descriptor at Block 1. let group_desc = arena.allocate::( BlockId::from(1), std::mem::size_of::() * group_id as usize, )?; // First blocks for block_bitmap, inode_bitmap, and inode_table. let super_block_id = group_id as u32 * sb.blocks_per_group; let group_desc_id = super_block_id + 1; group_desc.block_bitmap = group_desc_id + num_blocks_for_gds; group_desc.inode_bitmap = group_desc.block_bitmap + 1; group_desc.inode_table = group_desc.inode_bitmap + 1; // First free block is the one after inode table. let first_free_block = group_desc.inode_table + num_blocks_for_inode_table as u32; // Free blocks are from `first_free_block` to `blocks_per_group`, inclusive. group_desc.free_blocks_count = (sb.blocks_per_group * (group_id as u32 + 1) - first_free_block) as u16; sb.free_blocks_count += group_desc.free_blocks_count as u32; // 10 inodes should be reserved in ext2. let reserved_inode = if group_id == 0 { 10 } else { 0 }; let first_free_inode = group_id as u32 * sb.inodes_per_group + reserved_inode + 1; group_desc.free_inodes_count = sb.inodes_per_group as u16 - reserved_inode as u16; sb.free_inodes_count -= reserved_inode; // Initialize block bitmap block. let bmap = arena.allocate::<[u8; BLOCK_SIZE]>(BlockId::from(group_desc.block_bitmap), 0)?; let valid_bmap_bytes = (sb.blocks_per_group / 8) as usize; // Unused parts in the block is marked as 1. bmap[valid_bmap_bytes..].iter_mut().for_each(|x| *x = 0xff); // Interpret the region as BitMap and mask bits for blocks used for metadata. let mut block_bitmap = BitMap::from_slice_mut(&mut bmap[..valid_bmap_bytes]); block_bitmap.mark_first_elems( (first_free_block - group_id as u32 * sb.blocks_per_group) as usize, true, ); let imap = arena.allocate::<[u8; BLOCK_SIZE]>(BlockId::from(group_desc.inode_bitmap), 0)?; let valid_imap_bytes = (sb.inodes_per_group / 8) as usize; // Unused parts in the block is marked as 1. imap[valid_imap_bytes..].iter_mut().for_each(|x| *x = 0xff); // Interpret the region as BitMap and mask bits for reserved inodes. let mut inode_bitmap = BitMap::from_slice_mut(&mut imap[..(sb.inodes_per_group / 8) as usize]); inode_bitmap.mark_first_elems(reserved_inode as usize, true); Ok(GroupMetaData { group_desc, block_bitmap, inode_bitmap, inode_table: BTreeMap::new(), first_free_block, first_free_inode, }) } } #[cfg(test)] mod test { use base::MemoryMappingBuilder; use super::*; use crate::Builder; // Check if `GroupMetaData` is correctly initialized from `SuperBlock` with one block group. #[test] fn test_group_metadata_with_one_block_group() { let blocks_per_group = 1024; let num_groups = 1; let size = BLOCK_SIZE as u32 * blocks_per_group * num_groups; let mut mem = MemoryMappingBuilder::new(size as usize).build().unwrap(); let arena = Arena::new(BLOCK_SIZE, &mut mem).unwrap(); let sb = SuperBlock::new( &arena, &Builder { inodes_per_group: 1024, blocks_per_group, size, root_dir: None, }, ) .unwrap(); let group = GroupMetaData::new(&arena, sb, 0).unwrap(); assert_eq!(sb.block_group_nr, 1); // First a few blocks are used for specific purposes. // Their indexes are arbitrary but we can assume the following values unless we use much // larger parameters: // 0: 1024-byte offset + superblock // 1: group descriptor(s) // 2: block bitmap // 3: inode bitmap // 4+ : inode table assert_eq!(group.group_desc.block_bitmap, 2); assert_eq!(group.group_desc.inode_bitmap, 3); assert_eq!(group.group_desc.inode_table, 4); assert_eq!( group.group_desc.free_blocks_count as u32, sb.free_blocks_count ); assert_eq!( group.group_desc.free_inodes_count as u32, sb.free_inodes_count ); assert_eq!(group.block_bitmap.len(), sb.blocks_per_group as usize); assert_eq!( group.block_bitmap.count_zeros(), group.group_desc.free_blocks_count as usize, ); assert_eq!( group.inode_bitmap.count_zeros(), group.group_desc.free_inodes_count as usize, ); } #[test] fn test_group_metadata_with_multiple_block_groups() { let blocks_per_group = 1024u32; let num_groups = 10u32; let mem_size = BLOCK_SIZE as u32 * blocks_per_group * num_groups; let mut mem = MemoryMappingBuilder::new(mem_size as usize) .build() .unwrap(); let arena = Arena::new(BLOCK_SIZE, &mut mem).unwrap(); let sb = SuperBlock::new( &arena, &Builder { inodes_per_group: 512, blocks_per_group, size: mem_size, root_dir: None, }, ) .unwrap(); let groups = (0..num_groups) .map(|group_id| GroupMetaData::new(&arena, sb, group_id as u16).unwrap()) .collect::>(); assert_eq!( groups .iter() .map(|gd| gd.group_desc.free_blocks_count as u32) .sum::(), sb.free_blocks_count ); assert_eq!( groups .iter() .map(|gd| gd.group_desc.free_inodes_count as u32) .sum::(), sb.free_inodes_count ); } }