//! ext2, the "second extended file system" (Rémy Card, 1993): Linux's main //! file system through the 1990s, and the base that ext3 and ext4 grew from. //! Written by hand here, no crate. It's the classic file system to learn //! from: everything on disk is an array of fixed-size records. //! //! # On-disk layout //! //! The disk is cut into **blocks** of 1, 2 or 4 KiB (`1024 << s_log_block_size`). //! Blocks are numbered from 0 and grouped into **block groups** of //! `s_blocks_per_group` blocks (8192 with 1 KiB blocks). Our 32 MiB disk has //! 1 KiB blocks, so it has 4 groups: //! //! ```text //! byte 0 1024 block 2 (with 1 KiB blocks) //! | boot | superblock | group descriptor table | reserved GDT blocks | //! | block bitmap | inode bitmap | inode table ... | data blocks ... | <- group 0 //! | (superblock + GDT backup) | block bitmap | inode bitmap | inode table | data... | <- group 1 //! ... //! ``` //! //! * **Superblock** (always at byte 1024, 1024 bytes): the totals. //! It records the block size, blocks and inodes per group, free //! counts, the magic number 0xEF53, the revision and feature flags. //! "sparse_super" keeps backup copies only in groups 0, 1 and powers of //! 3, 5 and 7. We read and update only the primary copy, like Linux. //! * **Group descriptor table** (the block after the superblock): 32 bytes per //! group, saying where that group's block bitmap, inode bitmap and inode //! table are, and its free block and inode counts. //! * **Bitmaps**: one block each, one bit per block or inode in the group; //! 1 = in use. Allocating means finding a 0 bit. //! * **Inode table**: `s_inodes_per_group` inodes of `s_inode_size` bytes //! (128 in revision 0; usually 256 in revision 1, where only the first 128 //! are classic ext2 fields). Inode numbers start at 1; inode N lives in //! group (N-1) / inodes_per_group. Inode 2 is the root directory, 1-10 are //! reserved, and 11 is usually lost+found. //! * **An inode** describes one file. It holds the mode (type + permissions), //! size, link count and times, plus 15 block pointers: //! //! ```text //! i_block[0..12] -> data blocks 0..11 directly //! i_block[12] -> a block of block numbers (single indirect) //! i_block[13] -> a block of single-indirect blocks (double indirect) //! i_block[14] -> a block of double-indirect blocks (triple indirect) //! ``` //! //! With 1 KiB blocks an indirect block holds 256 numbers. Direct blocks //! cover 12 KiB, single indirect up to 268 KiB, double up to ~64 MiB, and //! triple up to ~16 GiB. A 0 pointer is a *hole*, which reads as zeros //! (sparse files). //! * **A directory** is a file of variable-length entries: //! `inode u32, rec_len u16, name_len u8, file_type u8, name`. The entries //! are padded to 4 bytes and never cross a block. `rec_len` jumps to the //! next entry, so deleting just adds the entry's length to the previous //! one, and the last entry stretches to the end of the block. Revision 0 //! has no file_type byte (name_len is 16 bits). Every directory starts //! with "." and "..". //! * **Symlinks**: a target shorter than 60 bytes is stored right inside //! `i_block` (a "fast" symlink). Longer ones get a data block ("slow"). //! //! # What we do //! //! * **Reading:** all of the above, including holes and both symlink kinds. //! Large "dir_index" (htree) directories also work: their hash index //! hides inside entries that plain ext2 code skips. //! * **Writing:** //! - We create files and directories, write and append, truncate to 0, //! and unlink and rmdir. //! - Blocks and inodes come from the bitmaps. The free counts are kept //! right in the group descriptors and the superblock, so `e2fsck` finds //! a clean file system. //! - When we change an htree directory, we clear its index flag, like //! Linux's ext2 driver does. //! * **Not supported:** //! - Creating symlinks or hard links, and rename. //! - Extended attribute blocks: deleting a file that has one gives //! EOPNOTSUPP. //! - Files bigger than 2 GiB on write. //! * **Unknown features:** //! - A file system with an "incompat" feature we don't know refuses to //! mount (ext4's extents, for example). //! - An unknown "ro_compat" feature mounts read-only. //! //! Every operation reads what it needs straight from the disk: there's no //! cache, and writes go straight through. One Mutex serializes the volume. //! There's no journal (that's ext3), so a crash in the middle of an //! operation can leave work for e2fsck, just like real ext2. use super::{DirEntry, FileSystem, Inode, InodeKind}; use crate::block::{BlockDevice, SECTOR_SIZE}; use crate::errno::Errno; use alloc::{format, string::String, sync::Arc, vec, vec::Vec}; use spin::Mutex; const MAGIC: u16 = 0xEF53; const ROOT_INO: u32 = 2; // Superblock fields (byte offsets inside the 1024-byte superblock). const SB_INODES_COUNT: usize = 0; const SB_BLOCKS_COUNT: usize = 4; const SB_FREE_BLOCKS: usize = 12; const SB_FREE_INODES: usize = 16; const SB_FIRST_DATA_BLOCK: usize = 20; // block holding the superblock: 1 with 1 KiB blocks, else 0 const SB_LOG_BLOCK_SIZE: usize = 24; const SB_BLOCKS_PER_GROUP: usize = 32; const SB_INODES_PER_GROUP: usize = 40; const SB_WTIME: usize = 48; const SB_MAGIC: usize = 56; const SB_REV_LEVEL: usize = 76; const SB_FIRST_INO: usize = 84; // revision 1+ const SB_INODE_SIZE: usize = 88; // revision 1+ (u16) const SB_FEATURE_INCOMPAT: usize = 96; const SB_FEATURE_RO_COMPAT: usize = 100; const SB_VOLUME_NAME: usize = 120; // 16 bytes // Feature flags we understand. const INCOMPAT_FILETYPE: u32 = 0x0002; // directory entries have a file type byte const RO_COMPAT_SPARSE_SUPER: u32 = 0x0001; // fewer superblock backups const RO_COMPAT_LARGE_FILE: u32 = 0x0002; // files > 2 GiB (we only read them) const RO_COMPAT_BTREE_DIR: u32 = 0x0004; // never used by anyone // Group descriptor fields (32 bytes per group). const GD_SIZE: usize = 32; const GD_BLOCK_BITMAP: usize = 0; const GD_INODE_BITMAP: usize = 4; const GD_INODE_TABLE: usize = 8; const GD_FREE_BLOCKS: usize = 12; // u16 const GD_FREE_INODES: usize = 14; // u16 const GD_USED_DIRS: usize = 16; // u16 // Inode fields (the classic first 128 bytes). const I_MODE: usize = 0; // u16 const I_SIZE: usize = 4; const I_ATIME: usize = 8; const I_CTIME: usize = 12; const I_MTIME: usize = 16; const I_DTIME: usize = 20; // deletion time (0 = in use) const I_LINKS: usize = 26; // u16 const I_SECTORS: usize = 28; // "i_blocks": counted in 512-byte sectors! const I_FLAGS: usize = 32; const I_BLOCK: usize = 40; // 15 block pointers (60 bytes) const I_FILE_ACL: usize = 104; // extended attribute block const I_SIZE_HIGH: usize = 108; // upper 32 bits of the size (regular files) // i_mode: the top 4 bits are the type, the low 12 the permissions. const S_IFMT: u16 = 0o170000; const S_IFREG: u16 = 0o100000; const S_IFDIR: u16 = 0o040000; const S_IFLNK: u16 = 0o120000; // Directory entry file types (with INCOMPAT_FILETYPE). const FT_REG: u8 = 1; const FT_DIR: u8 = 2; const INDEX_FL: u32 = 0x1000; // directory has an htree index /// Biggest file we write (bigger needs the large_file feature handling). const MAX_WRITE_SIZE: u64 = (1 << 31) - 1; fn get16(b: &[u8], at: usize) -> u16 { u16::from_le_bytes([b[at], b[at + 1]]) } fn get32(b: &[u8], at: usize) -> u32 { u32::from_le_bytes([b[at], b[at + 1], b[at + 2], b[at + 3]]) } fn put16(b: &mut [u8], at: usize, v: u16) { b[at..at + 2].copy_from_slice(&v.to_le_bytes()); } fn put32(b: &mut [u8], at: usize, v: u32) { b[at..at + 4].copy_from_slice(&v.to_le_bytes()); } /// Does `dev` hold an ext2 (or ext3/ext4) file system? Checks the magic /// number in the superblock at byte 1024 (= sectors 2 and 3). pub fn probe(dev: &dyn BlockDevice) -> bool { let mut sb = [0u8; 1024]; dev.read_sectors(2, &mut sb).is_ok() && get16(&sb, SB_MAGIC) == MAGIC } // --------------------------------------------------------------------------- // One inode, as on disk // --------------------------------------------------------------------------- /// An inode's bytes (all `s_inode_size` of them, so writing it back keeps /// the fields we don't interpret), with accessors for the ones we use. #[derive(Clone)] struct DiskInode { ino: u32, raw: Vec, } impl DiskInode { fn mode(&self) -> u16 { get16(&self.raw, I_MODE) } fn kind(&self) -> InodeKind { match self.mode() & S_IFMT { S_IFDIR => InodeKind::Directory, S_IFLNK => InodeKind::Symlink, _ => InodeKind::File, // regular files (devices, fifos: treated as files) } } fn is_regular(&self) -> bool { self.mode() & S_IFMT == S_IFREG } fn size(&self) -> u64 { let high = if self.is_regular() { get32(&self.raw, I_SIZE_HIGH) as u64 } else { 0 }; (high << 32) | get32(&self.raw, I_SIZE) as u64 } fn set_size(&mut self, size: u64) { put32(&mut self.raw, I_SIZE, size as u32); if self.is_regular() { put32(&mut self.raw, I_SIZE_HIGH, (size >> 32) as u32); } } fn links(&self) -> u16 { get16(&self.raw, I_LINKS) } fn set_links(&mut self, n: u16) { put16(&mut self.raw, I_LINKS, n); } fn sectors(&self) -> u32 { get32(&self.raw, I_SECTORS) } fn add_sectors(&mut self, n: i64) { let sectors = (self.sectors() as i64 + n) as u32; put32(&mut self.raw, I_SECTORS, sectors); } fn block(&self, slot: usize) -> u32 { get32(&self.raw, I_BLOCK + 4 * slot) } fn set_block(&mut self, slot: usize, b: u32) { put32(&mut self.raw, I_BLOCK + 4 * slot, b); } fn file_acl(&self) -> u32 { get32(&self.raw, I_FILE_ACL) } fn set_times(&mut self, which: &[usize], t: u32) { which.iter().for_each(|&at| put32(&mut self.raw, at, t)); } } /// One directory entry, as read from disk. struct RawDirEntry { ino: u32, name: String, file_type: u8, // 0 = unknown (revision 0 file systems) } /// Size a directory entry with this name needs: 8-byte header + name, /// rounded up to 4 bytes. fn entry_size(name_len: usize) -> usize { (8 + name_len + 3) & !3 } // --------------------------------------------------------------------------- // The volume: superblock, group descriptors and all the disk work // --------------------------------------------------------------------------- struct Volume { dev: Arc, sb: Vec, // the 1024-byte superblock, as on disk gdt: Vec, // the group descriptor table, as on disk (whole blocks) block_size: usize, groups: u32, gdt_block: u32, // where the descriptor table starts inode_size: usize, first_ino: u32, // first inode for ordinary files (11) revision: u32, filetype: bool, // directory entries carry a file type writable: bool, } impl Volume { fn open(dev: Arc) -> Result { let mut sb = vec![0u8; 1024]; dev.read_sectors(2, &mut sb)?; if get16(&sb, SB_MAGIC) != MAGIC { return Err(Errno::EINVAL); } let log = get32(&sb, SB_LOG_BLOCK_SIZE); if log > 6 { return Err(Errno::EINVAL); // > 64 KiB: corrupted } let block_size = 1024usize << log; let revision = get32(&sb, SB_REV_LEVEL); let (inode_size, first_ino, incompat, ro_compat) = if revision == 0 { (128, 11, 0, 0) // revision 0: fixed sizes, no feature flags } else { ( get16(&sb, SB_INODE_SIZE) as usize, get32(&sb, SB_FIRST_INO), get32(&sb, SB_FEATURE_INCOMPAT), get32(&sb, SB_FEATURE_RO_COMPAT), ) }; if inode_size < 128 || !inode_size.is_power_of_two() || inode_size > block_size { return Err(Errno::EINVAL); } // "incompat" features change the format: if we don't know one, we // can't even read safely (ext4 extents, a journal needing recovery...). if incompat & !INCOMPAT_FILETYPE != 0 { return Err(Errno::EOPNOTSUPP); } // "ro_compat" features: reading is fine, writing could break them. let writable = ro_compat & !(RO_COMPAT_SPARSE_SUPER | RO_COMPAT_LARGE_FILE | RO_COMPAT_BTREE_DIR) == 0; let blocks_count = get32(&sb, SB_BLOCKS_COUNT); let first_data = get32(&sb, SB_FIRST_DATA_BLOCK); let per_group = get32(&sb, SB_BLOCKS_PER_GROUP); if per_group == 0 || get32(&sb, SB_INODES_PER_GROUP) == 0 || blocks_count <= first_data { return Err(Errno::EINVAL); } let groups = (blocks_count - first_data).div_ceil(per_group); let gdt_block = first_data + 1; let gdt_blocks = (groups as usize * GD_SIZE).div_ceil(block_size); let mut gdt = vec![0u8; gdt_blocks * block_size]; dev.read_sectors(gdt_block as u64 * (block_size / SECTOR_SIZE) as u64, &mut gdt)?; Ok(Volume { dev, sb, gdt, block_size, groups, gdt_block, inode_size, first_ino, revision, filetype: incompat & INCOMPAT_FILETYPE != 0, writable, }) } fn sb32(&self, at: usize) -> u32 { get32(&self.sb, at) } /// Timestamp for new and changed inodes. We have no clock driver yet, /// so we reuse the superblock's "last written" time (set by mke2fs). fn now(&self) -> u32 { self.sb32(SB_WTIME).max(1) } // ---- blocks ---------------------------------------------------------- fn read_block(&self, block: u32) -> Result, Errno> { if block == 0 || block >= self.sb32(SB_BLOCKS_COUNT) { return Err(Errno::EIO); // a bad pointer: corrupted file system } let mut data = vec![0u8; self.block_size]; self.dev.read_sectors(block as u64 * (self.block_size / SECTOR_SIZE) as u64, &mut data)?; Ok(data) } fn write_block(&self, block: u32, data: &[u8]) -> Result<(), Errno> { if block == 0 || block >= self.sb32(SB_BLOCKS_COUNT) { return Err(Errno::EIO); } self.dev.write_sectors(block as u64 * (self.block_size / SECTOR_SIZE) as u64, data) } // ---- group descriptors and counters ---------------------------------- fn gd32(&self, group: u32, field: usize) -> u32 { get32(&self.gdt, group as usize * GD_SIZE + field) } fn gd16(&self, group: u32, field: usize) -> u16 { get16(&self.gdt, group as usize * GD_SIZE + field) } /// Change a group's free-block / free-inode / directory counts (and the /// superblock totals), and write both back to disk. fn adjust_counts(&mut self, group: u32, blocks: i32, inodes: i32, dirs: i32) -> Result<(), Errno> { let at = group as usize * GD_SIZE; for (field, delta) in [(GD_FREE_BLOCKS, blocks), (GD_FREE_INODES, inodes), (GD_USED_DIRS, dirs)] { let v = get16(&self.gdt, at + field) as i32 + delta; put16(&mut self.gdt, at + field, v as u16); } for (field, delta) in [(SB_FREE_BLOCKS, blocks), (SB_FREE_INODES, inodes)] { let v = get32(&self.sb, field) as i64 + delta as i64; put32(&mut self.sb, field, v as u32); } // Write the descriptor table block holding this group, then the // superblock (sectors 2-3, wherever block 0/1 boundaries are). let index = at / self.block_size; let bs = self.block_size; self.write_block(self.gdt_block + index as u32, &self.gdt[index * bs..(index + 1) * bs])?; self.dev.write_sectors(2, &self.sb) } // ---- bitmaps: allocating and freeing --------------------------------- /// Find a 0 bit among the first `bits` of group `group`'s bitmap (block /// or inode bitmap, by `field`), set it, and return its index. fn take_bit(&self, group: u32, field: usize, bits: u32) -> Result, Errno> { let block = self.gd32(group, field); let mut map = self.read_block(block)?; for i in 0..bits.min(self.block_size as u32 * 8) { let (byte, mask) = ((i / 8) as usize, 1u8 << (i % 8)); if map[byte] & mask == 0 { map[byte] |= mask; self.write_block(block, &map)?; return Ok(Some(i)); } } Ok(None) // the counts said there was room: they were wrong } fn clear_bit(&self, group: u32, field: usize, i: u32) -> Result<(), Errno> { let block = self.gd32(group, field); let mut map = self.read_block(block)?; let (byte, mask) = ((i / 8) as usize, 1u8 << (i % 8)); if map[byte] & mask == 0 { return Err(Errno::EIO); // freeing something free: corrupted } map[byte] &= !mask; self.write_block(block, &map) } /// Allocate a block, preferably in `goal` (the group of its inode, so a /// file's blocks stay near each other). The new block is zeroed. fn alloc_block(&mut self, goal: u32) -> Result { let per_group = self.sb32(SB_BLOCKS_PER_GROUP); let first_data = self.sb32(SB_FIRST_DATA_BLOCK); for k in 0..self.groups { let group = (goal + k) % self.groups; if self.gd16(group, GD_FREE_BLOCKS) == 0 { continue; } // The last group can be shorter than the others. let start = first_data + group * per_group; let bits = per_group.min(self.sb32(SB_BLOCKS_COUNT) - start); if let Some(i) = self.take_bit(group, GD_BLOCK_BITMAP, bits)? { self.adjust_counts(group, -1, 0, 0)?; let block = start + i; self.write_block(block, &vec![0u8; self.block_size])?; return Ok(block); } } Err(Errno::ENOSPC) } fn free_block(&mut self, block: u32) -> Result<(), Errno> { let first_data = self.sb32(SB_FIRST_DATA_BLOCK); if block < first_data || block >= self.sb32(SB_BLOCKS_COUNT) { return Err(Errno::EIO); } let per_group = self.sb32(SB_BLOCKS_PER_GROUP); let group = (block - first_data) / per_group; self.clear_bit(group, GD_BLOCK_BITMAP, (block - first_data) % per_group)?; self.adjust_counts(group, 1, 0, 0) } /// Allocate an inode number, preferably in group `goal`, and zero it. fn alloc_inode(&mut self, goal: u32, dir: bool) -> Result { let per_group = self.sb32(SB_INODES_PER_GROUP); for k in 0..self.groups { let group = (goal + k) % self.groups; if self.gd16(group, GD_FREE_INODES) == 0 { continue; } if let Some(i) = self.take_bit(group, GD_INODE_BITMAP, per_group)? { let ino = group * per_group + i + 1; // inode numbers start at 1 if ino < self.first_ino { return Err(Errno::EIO); // reserved inodes must be marked used } self.adjust_counts(group, 0, -1, dir as i32)?; let inode = DiskInode { ino, raw: vec![0u8; self.inode_size] }; self.write_inode(&inode)?; return Ok(inode); } } Err(Errno::ENOSPC) } fn free_inode(&mut self, ino: u32, dir: bool) -> Result<(), Errno> { let per_group = self.sb32(SB_INODES_PER_GROUP); let group = (ino - 1) / per_group; self.clear_bit(group, GD_INODE_BITMAP, (ino - 1) % per_group)?; self.adjust_counts(group, 0, 1, -(dir as i32)) } // ---- inodes ---------------------------------------------------------- /// Which block of the inode table holds inode `ino`, and where in it. fn inode_location(&self, ino: u32) -> Result<(u32, usize), Errno> { if ino == 0 || ino > self.sb32(SB_INODES_COUNT) { return Err(Errno::EIO); } let per_group = self.sb32(SB_INODES_PER_GROUP); let (group, index) = ((ino - 1) / per_group, (ino - 1) % per_group); let byte = index as usize * self.inode_size; let block = self.gd32(group, GD_INODE_TABLE) + (byte / self.block_size) as u32; Ok((block, byte % self.block_size)) } fn read_inode(&self, ino: u32) -> Result { let (block, at) = self.inode_location(ino)?; let data = self.read_block(block)?; Ok(DiskInode { ino, raw: data[at..at + self.inode_size].to_vec() }) } fn write_inode(&self, inode: &DiskInode) -> Result<(), Errno> { let (block, at) = self.inode_location(inode.ino)?; let mut data = self.read_block(block)?; data[at..at + self.inode_size].copy_from_slice(&inode.raw); self.write_block(block, &data) } fn group_of(&self, ino: u32) -> u32 { (ino - 1) / self.sb32(SB_INODES_PER_GROUP) } // ---- file block mapping: direct and indirect blocks ------------------ /// Which disk block holds block number `index` of the file? 0 = a hole. /// With `alloc`, holes are filled with new zeroed blocks (and any /// missing indirect blocks on the way); the caller then writes `inode` /// back, since its block pointers and sector count changed. fn bmap(&mut self, inode: &mut DiskInode, index: u64, alloc: bool) -> Result { let p = (self.block_size / 4) as u64; // pointers per indirect block // Which of the 15 pointers, how many indirect levels below it, and // the index inside that tree. let (slot, levels, mut rest) = if index < 12 { (index as usize, 0, 0) } else if index - 12 < p { (12, 1, index - 12) } else if index - 12 - p < p * p { (13, 2, index - 12 - p) } else if index - 12 - p - p * p < p * p * p { (14, 3, index - 12 - p - p * p) } else { return Err(Errno::EFBIG); }; let goal = self.group_of(inode.ino); let sectors_per_block = (self.block_size / SECTOR_SIZE) as i64; let mut block = inode.block(slot); if block == 0 { if !alloc { return Ok(0); } block = self.alloc_block(goal)?; inode.set_block(slot, block); inode.add_sectors(sectors_per_block); } // Walk down the indirect blocks: at each level, pick the pointer for // our part of the tree (like digits of `rest` in base p). for level in (0..levels).rev() { let span = p.pow(level); let i = (rest / span) as usize; rest %= span; let mut table = self.read_block(block)?; let mut next = get32(&table, 4 * i); if next == 0 { if !alloc { return Ok(0); } next = self.alloc_block(goal)?; put32(&mut table, 4 * i, next); self.write_block(block, &table)?; inode.add_sectors(sectors_per_block); } block = next; } Ok(block) } /// Free a block and, for indirect blocks (`levels` > 0), everything it /// points to. fn free_tree(&mut self, block: u32, levels: u32) -> Result<(), Errno> { if levels > 0 { let table = self.read_block(block)?; for i in 0..self.block_size / 4 { let next = get32(&table, 4 * i); if next != 0 { self.free_tree(next, levels - 1)?; } } } self.free_block(block) } /// Free all of a file's data blocks: size 0, no blocks (truncate). fn free_data(&mut self, inode: &mut DiskInode) -> Result<(), Errno> { if !self.is_fast_symlink(inode) { for slot in 0..15 { let block = inode.block(slot); if block != 0 { let levels = slot.saturating_sub(11) as u32; // 12 -> 1, 13 -> 2, 14 -> 3 self.free_tree(block, levels)?; inode.set_block(slot, 0); } } // What's left in i_blocks is the extended attribute block, if any. let ea = if inode.file_acl() != 0 { self.block_size / SECTOR_SIZE } else { 0 }; put32(&mut inode.raw, I_SECTORS, ea as u32); } inode.set_size(0); Ok(()) } /// A symlink whose target is stored inside i_block (no data blocks). fn is_fast_symlink(&self, inode: &DiskInode) -> bool { let ea = if inode.file_acl() != 0 { (self.block_size / SECTOR_SIZE) as u32 } else { 0 }; inode.kind() == InodeKind::Symlink && inode.sectors() == ea } // ---- file contents --------------------------------------------------- fn read_file(&mut self, inode: &DiskInode, offset: u64, buf: &mut [u8]) -> Result { let size = inode.size(); if offset >= size { return Ok(0); } let len = buf.len().min((size - offset) as usize); let bs = self.block_size as u64; let mut inode = inode.clone(); // bmap wants &mut (it won't change it without alloc) let mut done = 0; while done < len { let pos = offset + done as u64; let within = (pos % bs) as usize; let n = (self.block_size - within).min(len - done); match self.bmap(&mut inode, pos / bs, false)? { 0 => buf[done..done + n].fill(0), // a hole block => buf[done..done + n].copy_from_slice(&self.read_block(block)?[within..within + n]), } done += n; } Ok(done) } fn write_file(&mut self, inode: &mut DiskInode, offset: u64, buf: &[u8]) -> Result { let end = offset.checked_add(buf.len() as u64).ok_or(Errno::EFBIG)?; if end > MAX_WRITE_SIZE { return Err(Errno::EFBIG); } let bs = self.block_size as u64; let mut done = 0; let mut result = Ok(()); while done < buf.len() { let pos = offset + done as u64; let within = (pos % bs) as usize; let n = (self.block_size - within).min(buf.len() - done); let step = (|| { let block = self.bmap(inode, pos / bs, true)?; // A whole block is simply overwritten; part of one is // read-modify-write. let mut data = if n == self.block_size { vec![0u8; n] } else { self.read_block(block)? }; data[within..within + n].copy_from_slice(&buf[done..done + n]); self.write_block(block, &data) })(); if let Err(e) = step { result = Err(e); // e.g. ENOSPC: keep what was written so far break; } done += n; } // Always save the inode: bmap may have allocated blocks even if a // later step failed. let new_end = offset + done as u64; if new_end > inode.size() { inode.set_size(new_end); } let now = self.now(); inode.set_times(&[I_MTIME, I_CTIME], now); self.write_inode(inode)?; match result { Err(e) if done == 0 => Err(e), _ => Ok(done), } } // ---- directories ----------------------------------------------------- /// Parse the entry at `at` in a directory block: (inode, rec_len, name_len, type). fn parse_entry(&self, data: &[u8], at: usize) -> Result<(u32, usize, usize, u8), Errno> { let rec_len = get16(data, at + 4) as usize; let (name_len, file_type) = if self.filetype { (data[at + 6] as usize, data[at + 7]) } else { (get16(data, at + 6) as usize, 0) }; if rec_len < 8 || rec_len % 4 != 0 || at + rec_len > data.len() || 8 + name_len > rec_len { return Err(Errno::EIO); // corrupted directory } Ok((get32(data, at), rec_len, name_len, file_type)) } fn write_entry(&self, data: &mut [u8], at: usize, ino: u32, rec_len: usize, name: &str, file_type: u8) { put32(data, at, ino); put16(data, at + 4, rec_len as u16); if self.filetype { data[at + 6] = name.len() as u8; data[at + 7] = file_type; } else { put16(data, at + 6, name.len() as u16); } data[at + 8..at + 8 + name.len()].copy_from_slice(name.as_bytes()); } fn dir_blocks(&self, dir: &DiskInode) -> u64 { dir.size().div_ceil(self.block_size as u64) } /// All entries of a directory, "." and ".." included. fn read_dir(&mut self, dir: &DiskInode) -> Result, Errno> { let mut out = Vec::new(); let mut dir = dir.clone(); for index in 0..self.dir_blocks(&dir) { let block = self.bmap(&mut dir, index, false)?; if block == 0 { continue; } let data = self.read_block(block)?; let mut at = 0; while at < data.len() { let (ino, rec_len, name_len, file_type) = self.parse_entry(&data, at)?; if ino != 0 { let name = String::from_utf8_lossy(&data[at + 8..at + 8 + name_len]).into_owned(); out.push(RawDirEntry { ino, name, file_type }); } at += rec_len; } } Ok(out) } fn find_entry(&mut self, dir: &DiskInode, name: &str) -> Result, Errno> { Ok(self.read_dir(dir)?.into_iter().find(|e| e.name == name).map(|e| e.ino)) } /// We don't keep the htree hash index of big directories up to date, /// so mark it gone when changing a directory (like Linux's ext2 does). fn drop_index(dir: &mut DiskInode) { let flags = get32(&dir.raw, I_FLAGS); put32(&mut dir.raw, I_FLAGS, flags & !INDEX_FL); } /// Add `name -> ino` to a directory: in the slack space after an /// existing entry if there is room, else in a new block at the end. fn add_entry(&mut self, dir: &mut DiskInode, name: &str, ino: u32, file_type: u8) -> Result<(), Errno> { let need = entry_size(name.len()); Self::drop_index(dir); for index in 0..self.dir_blocks(dir) { let block = self.bmap(dir, index, false)?; if block == 0 { continue; } let mut data = self.read_block(block)?; let mut at = 0; while at < data.len() { let (e_ino, rec_len, name_len, _) = self.parse_entry(&data, at)?; let used = if e_ino == 0 { 0 } else { entry_size(name_len) }; if rec_len - used >= need { if e_ino == 0 { // An unused entry (start of a block): take it over. self.write_entry(&mut data, at, ino, rec_len, name, file_type); } else { // Shrink this entry to its real size; we get the rest. put16(&mut data, at + 4, used as u16); self.write_entry(&mut data, at + used, ino, rec_len - used, name, file_type); } self.write_block(block, &data)?; return self.write_inode(dir); } at += rec_len; } } // No room anywhere: grow the directory by one block. let index = self.dir_blocks(dir); let block = self.bmap(dir, index, true)?; let mut data = vec![0u8; self.block_size]; self.write_entry(&mut data, 0, ino, self.block_size, name, file_type); self.write_block(block, &data)?; dir.set_size((index + 1) * self.block_size as u64); self.write_inode(dir) } /// Remove `name` from a directory; returns its inode number. The entry /// is merged into the previous one (or, first in its block, marked /// unused with inode 0). fn remove_entry(&mut self, dir: &mut DiskInode, name: &str) -> Result { Self::drop_index(dir); for index in 0..self.dir_blocks(dir) { let block = self.bmap(dir, index, false)?; if block == 0 { continue; } let mut data = self.read_block(block)?; let (mut at, mut prev) = (0, None); while at < data.len() { let (e_ino, rec_len, name_len, _) = self.parse_entry(&data, at)?; if e_ino != 0 && &data[at + 8..at + 8 + name_len] == name.as_bytes() { match prev { Some(p) => { let merged = get16(&data, p + 4) as usize + rec_len; put16(&mut data, p + 4, merged as u16); } None => put32(&mut data, at, 0), } self.write_block(block, &data)?; self.write_inode(dir)?; return Ok(e_ino); } prev = Some(at); at += rec_len; } } Err(Errno::ENOENT) } // ---- the operations the VFS uses ------------------------------------- fn create(&mut self, parent_ino: u32, name: &str, kind: InodeKind) -> Result { if !self.writable { return Err(Errno::EROFS); } if name.is_empty() || name == "." || name == ".." || name.contains('/') { return Err(Errno::EINVAL); } if name.len() > 255 { return Err(Errno::ENAMETOOLONG); } let mut parent = self.read_inode(parent_ino)?; if parent.kind() != InodeKind::Directory { return Err(Errno::ENOTDIR); } if self.find_entry(&parent, name)?.is_some() { return Err(Errno::EEXIST); } let dir = match kind { InodeKind::File => false, InodeKind::Directory => true, InodeKind::Symlink => return Err(Errno::EOPNOTSUPP), // no symlink syscall yet }; let mut inode = self.alloc_inode(self.group_of(parent_ino), dir)?; let now = self.now(); inode.set_times(&[I_ATIME, I_CTIME, I_MTIME], now); if dir { put16(&mut inode.raw, I_MODE, S_IFDIR | 0o755); inode.set_links(2); // the parent's entry + its own "." } else { put16(&mut inode.raw, I_MODE, S_IFREG | 0o644); inode.set_links(1); } let result = (|| { if dir { // A new directory holds "." and ".." (which takes the rest of the block). let block = self.bmap(&mut inode, 0, true)?; let mut data = vec![0u8; self.block_size]; self.write_entry(&mut data, 0, inode.ino, 12, ".", FT_DIR); self.write_entry(&mut data, 12, parent_ino, self.block_size - 12, "..", FT_DIR); self.write_block(block, &data)?; inode.set_size(self.block_size as u64); } self.write_inode(&inode)?; self.add_entry(&mut parent, name, inode.ino, if dir { FT_DIR } else { FT_REG })?; if dir { parent.set_links(parent.links() + 1); // the new ".." points at it self.write_inode(&parent)?; } Ok(()) })(); if let Err(e) = result { // Undo (e.g. the parent directory couldn't grow: ENOSPC). let _ = self.free_data(&mut inode); let _ = self.free_inode(inode.ino, dir); return Err(e); } Ok(inode.ino) } fn remove(&mut self, parent_ino: u32, name: &str) -> Result<(), Errno> { if !self.writable { return Err(Errno::EROFS); } let mut parent = self.read_inode(parent_ino)?; let ino = self.find_entry(&parent, name)?.ok_or(Errno::ENOENT)?; let mut child = self.read_inode(ino)?; let is_dir = child.kind() == InodeKind::Directory; if is_dir && self.read_dir(&child)?.iter().any(|e| e.name != "." && e.name != "..") { return Err(Errno::ENOTEMPTY); } let last_link = is_dir || child.links() <= 1; if last_link && child.file_acl() != 0 { return Err(Errno::EOPNOTSUPP); // we don't do extended attribute blocks } self.remove_entry(&mut parent, name)?; if is_dir { parent.set_links(parent.links() - 1); // its ".." is gone self.write_inode(&parent)?; } if !last_link { child.set_links(child.links() - 1); // another hard link remains return self.write_inode(&child); } // Last link gone: free the data, mark the inode deleted, free it. self.free_data(&mut child)?; child.set_links(0); let now = self.now(); child.set_times(&[I_DTIME, I_CTIME], now); self.write_inode(&child)?; self.free_inode(ino, is_dir) } fn truncate(&mut self, ino: u32) -> Result<(), Errno> { if !self.writable { return Err(Errno::EROFS); } let mut inode = self.read_inode(ino)?; self.free_data(&mut inode)?; let now = self.now(); inode.set_times(&[I_MTIME, I_CTIME], now); self.write_inode(&inode) } fn readlink(&mut self, inode: &DiskInode) -> Result { let size = inode.size() as usize; let bytes = if self.is_fast_symlink(inode) { inode.raw[I_BLOCK..I_BLOCK + size.min(60)].to_vec() // stored in i_block itself } else { let mut buf = vec![0u8; size]; let n = self.read_file(inode, 0, &mut buf)?; buf.truncate(n); buf }; String::from_utf8(bytes).map_err(|_| Errno::EINVAL) } fn label(&self) -> String { let raw = &self.sb[SB_VOLUME_NAME..SB_VOLUME_NAME + 16]; let len = raw.iter().position(|&b| b == 0).unwrap_or(16); String::from_utf8_lossy(&raw[..len]).into_owned() } } // --------------------------------------------------------------------------- // The VFS side // --------------------------------------------------------------------------- /// A mounted ext2 volume. pub struct Ext2Fs { vol: Arc>, } impl Ext2Fs { pub fn mount(dev: Arc) -> Result, Errno> { let vol = Volume::open(dev)?; let root = vol.read_inode(ROOT_INO)?; if root.kind() != InodeKind::Directory { return Err(Errno::EIO); } Ok(Arc::new(Ext2Fs { vol: Arc::new(Mutex::new(vol)) })) } /// For the boot log, e.g. `ext2 volume "RUSTBELT" (rev 1, 1 KiB blocks, 4 groups)`. pub fn describe(&self) -> String { let v = self.vol.lock(); format!( "ext2 volume \"{}\" (rev {}, {} KiB blocks, {} groups{})", v.label(), v.revision, v.block_size / 1024, v.groups, if v.writable { "" } else { ", read-only" } ) } /// (free blocks, total blocks, free inodes, total inodes), from the superblock. pub fn counts(&self) -> (u32, u32, u32, u32) { let v = self.vol.lock(); (v.sb32(SB_FREE_BLOCKS), v.sb32(SB_BLOCKS_COUNT), v.sb32(SB_FREE_INODES), v.sb32(SB_INODES_COUNT)) } } impl FileSystem for Ext2Fs { fn name(&self) -> &'static str { "ext2" } fn root(&self) -> Arc { Arc::new(Ext2Inode { vol: self.vol.clone(), ino: ROOT_INO, kind: InodeKind::Directory }) } } /// A file, directory or symlink on an ext2 volume: just its inode number. /// Every operation reads the on-disk inode fresh. pub struct Ext2Inode { vol: Arc>, ino: u32, kind: InodeKind, } impl Ext2Inode { fn child(&self, ino: u32, kind: InodeKind) -> Arc { Arc::new(Ext2Inode { vol: self.vol.clone(), ino, kind }) } fn dir_only(&self) -> Result<(), Errno> { if self.kind == InodeKind::Directory { Ok(()) } else { Err(Errno::ENOTDIR) } } } impl Inode for Ext2Inode { fn kind(&self) -> InodeKind { self.kind } fn size(&self) -> usize { if self.kind == InodeKind::Directory { return self.list().map(|l| l.len()).unwrap_or(0); } let vol = self.vol.lock(); vol.read_inode(self.ino).map(|i| i.size() as usize).unwrap_or(0) } fn mode(&self) -> u32 { let vol = self.vol.lock(); vol.read_inode(self.ino).map(|i| (i.mode() & 0o7777) as u32).unwrap_or(0) } fn readlink(&self) -> Result { if self.kind != InodeKind::Symlink { return Err(Errno::EINVAL); } let mut vol = self.vol.lock(); let inode = vol.read_inode(self.ino)?; vol.readlink(&inode) } fn read_at(&self, offset: usize, buf: &mut [u8]) -> Result { if self.kind == InodeKind::Directory { return Err(Errno::EISDIR); } let mut vol = self.vol.lock(); let inode = vol.read_inode(self.ino)?; vol.read_file(&inode, offset as u64, buf) } fn write_at(&self, offset: usize, buf: &[u8]) -> Result { if self.kind == InodeKind::Directory { return Err(Errno::EISDIR); } let mut vol = self.vol.lock(); if !vol.writable { return Err(Errno::EROFS); } let mut inode = vol.read_inode(self.ino)?; vol.write_file(&mut inode, offset as u64, buf) } fn truncate(&self) -> Result<(), Errno> { if self.kind == InodeKind::Directory { return Err(Errno::EISDIR); } self.vol.lock().truncate(self.ino) } fn lookup(&self, name: &str) -> Result, Errno> { self.dir_only()?; let mut vol = self.vol.lock(); let dir = vol.read_inode(self.ino)?; let ino = vol.find_entry(&dir, name)?.ok_or(Errno::ENOENT)?; let kind = vol.read_inode(ino)?.kind(); Ok(self.child(ino, kind)) } fn create(&self, name: &str, kind: InodeKind) -> Result, Errno> { self.dir_only()?; let ino = self.vol.lock().create(self.ino, name, kind)?; Ok(self.child(ino, kind)) } fn list(&self) -> Result, Errno> { self.dir_only()?; let mut vol = self.vol.lock(); let dir = vol.read_inode(self.ino)?; let mut out = Vec::new(); for e in vol.read_dir(&dir)? { if e.name == "." || e.name == ".." { continue; } let kind = match e.file_type { 1 => InodeKind::File, 2 => InodeKind::Directory, 7 => InodeKind::Symlink, _ => vol.read_inode(e.ino)?.kind(), // revision 0: no type in the entry }; out.push(DirEntry { name: e.name, kind }); } Ok(out) } fn remove(&self, name: &str) -> Result<(), Errno> { self.dir_only()?; self.vol.lock().remove(self.ino, name) } }