ext2/
blockgroup.rs

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
7use std::collections::BTreeMap;
8
9use anyhow::Result;
10use zerocopy::FromBytes;
11use zerocopy::Immutable;
12use zerocopy::IntoBytes;
13use zerocopy::KnownLayout;
14
15use crate::arena::Arena;
16use crate::arena::BlockId;
17use crate::bitmap::BitMap;
18use crate::inode::Inode;
19use crate::inode::InodeNum;
20use crate::superblock::SuperBlock;
21
22/// The size of a block in bytes.
23/// We only support 4K-byte blocks.
24pub 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)]
31pub(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
48pub(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
59impl<'a> GroupMetaData<'a> {
60    // Write GroupMetaData to the first block group.
61    // This data need to be copied to other block gropups' descriptor tables.
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)]
131mod 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]
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]
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}
ext2/blockgroup.rs

ext2/
blockgroup.rs
