From 1eac97eea4ec0bcef0be061a2cba93a584355283 Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Thu, 30 Nov 2023 02:15:06 -0800 Subject: Add real disk i/o, add mkfs.aya (not yet implemented) --- ayafs/src/disk/allocation.rs | 542 +++++++++++++++++++++++++++++++++++++++++++ ayafs/src/disk/bitmap.rs | 48 ++++ ayafs/src/disk/block.rs | 245 +++++++++++++++++++ ayafs/src/disk/inode.rs | 312 +++++++++++++++++++++++++ ayafs/src/disk/mod.rs | 6 + 5 files changed, 1153 insertions(+) create mode 100644 ayafs/src/disk/allocation.rs create mode 100644 ayafs/src/disk/bitmap.rs create mode 100644 ayafs/src/disk/block.rs create mode 100644 ayafs/src/disk/inode.rs create mode 100644 ayafs/src/disk/mod.rs (limited to 'ayafs/src/disk') diff --git a/ayafs/src/disk/allocation.rs b/ayafs/src/disk/allocation.rs new file mode 100644 index 0000000..a187fad --- /dev/null +++ b/ayafs/src/disk/allocation.rs @@ -0,0 +1,542 @@ +use crate::disk::block::{ + Block, DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock, +}; +use crate::disk::inode::{Inode, DIRECT_NUMBER, ENTRY_PER_BLOCK}; +use crate::memory::cached_block::{convert, CachedBlock}; +use crate::AyaFS; +use libc::c_int; +use log::debug; + +impl AyaFS { + /// 为 Inode 分配新 block, 返回 block 的编号和它在 inode 内的编号 + pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<(u32, usize)> { + // 先看这个 inode 的 direct block 有没有空闲 + for (index_within_direct, index) in inode.direct.iter_mut().enumerate() { + if !self.data_bitmap.query(*index as usize) { + let block_index = self.data_bitmap.allocate().unwrap() as u32; + // println!("allocating {} for direct", block_index); + *index = block_index; + inode.n_blocks += 1; + // 初始化这个 block + self.init_block(block_index as usize); + // 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了 + return Some((block_index, index_within_direct)); + } + } + + // direct block 全部分配完了, 先检查 indirect block 有没有分配, 没有就分配一个 + if !self.data_bitmap.query(inode.single_indirect as usize) { + inode.single_indirect = self + .data_bitmap + .allocate() + .expect("No free space for new block") as u32; + self.init_block(inode.single_indirect as usize); + // println!("allocating {} for indirect", inode.single_indirect); + } + // 在 indirect block 里尝试分配 + if let Some((block_index, index_within_indirect)) = + self.allocate_in_indirect(inode.single_indirect) + { + // println!("allocating {} in indirect", block_index); + inode.n_blocks += 1; + + let index_within_block = DIRECT_NUMBER + index_within_indirect; + return Some((block_index, index_within_block)); + } + + // direct & indirect block 全部分配完了, 先检查 double indirect block 有没有分配, 没有就分配一个 + if !self.data_bitmap.query(inode.double_indirect as usize) { + inode.double_indirect = self + .data_bitmap + .allocate() + .expect("No free space for new block") as u32; + self.init_block(inode.double_indirect as usize); + // println!("allocating {} for double indirect", inode.double_indirect); + } + // 在 double indirect block 里尝试分配 + if let Some((block_index, index_within_double)) = + self.alloc_in_double_indirect(inode.double_indirect) + { + // println!("allocating {} in double indirect", block_index); + inode.n_blocks += 1; + let index_within_block = DIRECT_NUMBER + ENTRY_PER_BLOCK + index_within_double; + return Some((block_index, index_within_block)); + } + + // direct, indirect & double indirect block 全部分配完了, 先检查 triple indirect block 有没有分配, 没有就分配一个 + if !self.data_bitmap.query(inode.triple_indirect as usize) { + inode.triple_indirect = self + .data_bitmap + .allocate() + .expect("No free space for new block") as u32; + self.init_block(inode.triple_indirect as usize); + // println!("allocating {} for triple indirect", inode.triple_indirect); + } + // 在 double indirect block 里尝试分配 + if let Some((block_index, index_within_triple)) = + self.alloc_in_triple_indirect(inode.triple_indirect) + { + // println!("allocating {} in triple indirect", block_index); + inode.n_blocks += 1; + let index_within_block = DIRECT_NUMBER + + ENTRY_PER_BLOCK + + ENTRY_PER_BLOCK * ENTRY_PER_BLOCK + + index_within_triple; + return Some((block_index, index_within_block)); + } + None + } + + fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<(u32, usize)> { + // 取出 single indirect block, 尝试在里面分配 + let indirect_entry = indirect_entry as usize; + // println!("finding indirect block with number {}, bitmap says {}", indirect_entry, self.data_bitmap.query(indirect_entry)); + + if let Some(block) = self + .get_block(indirect_entry) + .map(convert::) + { + // println!("found indirect block with number {}", indirect_entry); + let mut indirect_block = block.clone(); + for (index_within_indirect, entry) in + indirect_block.block.entries.iter_mut().enumerate() + { + if self.data_bitmap.query(*entry as usize) == false { + indirect_block.dirty = true; // 把这个块标记为 dirty + let block_index = self.data_bitmap.allocate().expect("No free space") as u32; + self.init_block(block_index as usize); + *entry = block_index; + self.update_block(indirect_block); + return Some((block_index, index_within_indirect)); + } + } + } + None + } + + fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option<(u32, usize)> { + let double_indirect_entry = double_indirect_entry as usize; + + if let Some(block) = self + .get_block(double_indirect_entry) + .map(convert::) + { + let mut double_indirect_block = block.clone(); + let mut double_indirect_modified = false; + for (index_within_double_indirect, indirect_entry) in + double_indirect_block.block.indirect.iter_mut().enumerate() + { + if self.data_bitmap.query(*indirect_entry as usize) == false { + double_indirect_block.dirty = true; + double_indirect_modified = true; + + let indirect_index = self.data_bitmap.allocate().expect("No free space"); + *indirect_entry = indirect_index as u32; + self.init_block(indirect_index); + } + + if let Some((block_index, index_within_indirect)) = + self.allocate_in_indirect(*indirect_entry) + { + if double_indirect_modified { + self.update_block(double_indirect_block); + } + let index_within_double = + index_within_double_indirect * ENTRY_PER_BLOCK + index_within_indirect; + return Some((block_index, index_within_double)); + } + } + } + None + } + + fn alloc_in_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option<(u32, usize)> { + let triple_indirect_entry = triple_indirect_entry as usize; + + if let Some(block) = self + .get_block(triple_indirect_entry) + .map(convert::) + { + let mut triple_indirect_block = block.clone(); + let mut triple_indirect_modified = false; + for (index_within_triple_indirect, double_indirect_entry) in triple_indirect_block + .block + .double_indirect + .iter_mut() + .enumerate() + { + if self.data_bitmap.query(*double_indirect_entry as usize) == false { + triple_indirect_block.dirty = true; + triple_indirect_modified = true; + + let double_indirect_index = self.data_bitmap.allocate().expect("No free space"); + *double_indirect_entry = double_indirect_index as u32; + self.init_block(double_indirect_index) + } + if let Some((block_index, index_within_double_indirect)) = + self.alloc_in_double_indirect(*double_indirect_entry) + { + if triple_indirect_modified { + self.update_block(triple_indirect_block); + } + let index_within_triple = + index_within_triple_indirect * ENTRY_PER_BLOCK * ENTRY_PER_BLOCK + + index_within_double_indirect; + return Some((block_index, index_within_triple)); + } + } + } + None + } +} + +impl AyaFS { + pub(crate) fn deallocate_all_blocks_for(&mut self, inode: &Inode) -> Result<(), c_int> { + // 遍历 direct block 并删除 + for block_index in inode.direct { + self.data_bitmap.deallocate(block_index as usize); + } + + // 遍历 indirect block 并删除 + if self.data_bitmap.query(inode.single_indirect as usize) { + let indirect = self + .get_block::(inode.single_indirect as usize) + .unwrap(); + for block_index in indirect.block.entries { + self.data_bitmap.deallocate(block_index as usize); + } + self.data_bitmap.deallocate(inode.single_indirect as usize); + } + + // 遍历 double indirect block 并删除 + if self.data_bitmap.query(inode.double_indirect as usize) { + let double_indirect = self + .get_block::(inode.double_indirect as usize) + .unwrap(); + for indirect_block_index in double_indirect.block.indirect { + if let Some(indirect) = + self.get_block::(indirect_block_index as usize) + { + for block_index in indirect.block.entries { + self.data_bitmap.deallocate(block_index as usize); + } + self.data_bitmap.deallocate(indirect_block_index as usize); + } + } + self.data_bitmap.deallocate(inode.double_indirect as usize); + } + + // 遍历 triple indirect block 并删除 + if self.data_bitmap.query(inode.triple_indirect as usize) { + let triple_indirect = self + .get_block::(inode.triple_indirect as usize) + .unwrap(); + for double_indirect_block_index in triple_indirect.block.double_indirect { + if let Some(double_indirect) = + self.get_block::(double_indirect_block_index as usize) + { + for indirect_block_index in double_indirect.block.indirect { + if let Some(indirect) = + self.get_block::(indirect_block_index as usize) + { + for block_index in indirect.block.entries { + self.data_bitmap.deallocate(block_index as usize); + } + self.data_bitmap.deallocate(indirect_block_index as usize); + } + } + self.data_bitmap + .deallocate(double_indirect_block_index as usize); + } + } + self.data_bitmap.deallocate(inode.triple_indirect as usize); + } + + Ok(()) + } + + /// 从 inode 中删去最后一个 block + pub(crate) fn deallocate_block_for(&mut self, inode: &mut Inode) -> Option { + // 如果 triple indirect 块存在, 则尝试从中销毁一个块 + if self.data_bitmap.query(inode.triple_indirect as usize) { + if let Some(block_index) = self.deallocate_from_triple_indirect(inode.triple_indirect) { + inode.n_blocks -= 1; + return Some(block_index); // 销毁成功, 直接返回 + } else { + // 销毁失败, 说明 triple indirect 空了, 把它也销毁. + self.data_bitmap.deallocate(inode.triple_indirect as usize); + inode.triple_indirect = 0; // 这个地方理论上应该不用? + } + } + // 如果 double indirect 块存在, 则从其中销毁 + if self.data_bitmap.query(inode.double_indirect as usize) { + if let Some(block_index) = self.deallocate_from_double_indirect(inode.double_indirect) { + inode.n_blocks -= 1; + return Some(block_index); + } else { + self.data_bitmap.deallocate(inode.double_indirect as usize); + inode.double_indirect = 0; // 这个地方理论上应该不用? + } + } + // 如果 indirect 块存在, 则从其中销毁 + if self.data_bitmap.query(inode.single_indirect as usize) { + if let Some(block_index) = self.deallocate_from_indirect(inode.single_indirect) { + inode.n_blocks -= 1; + return Some(block_index); + } else { + self.data_bitmap.deallocate(inode.single_indirect as usize); + inode.single_indirect = 0; // 这个地方理论上应该不用? + } + } + // 都没有，直接从 direct 块中销毁 + for entry in inode.direct.iter_mut().rev() { + if self.data_bitmap.query(*entry as usize) { + let index = std::mem::replace(entry, 0); // let index = *entry; *entry = 0; + inode.n_blocks -= 1; + self.data_bitmap.deallocate(index as usize); + return Some(index); + } + } + None + } + + fn deallocate_from_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option { + let triple_indirect_entry = triple_indirect_entry as usize; + if let Some(triple_indirect_block) = self + .get_block(triple_indirect_entry) + .map(convert::) + { + let mut triple_indirect_block = triple_indirect_block.clone(); + let mut block_modified = false; + for double_indirect_entry in + triple_indirect_block.block.double_indirect.iter_mut().rev() + { + // 如果这个位置的 double indirect 存在 + if self.data_bitmap.query(*double_indirect_entry as usize) { + // 尝试从中销毁一个块 + if let Some(block_index) = + self.deallocate_from_double_indirect(*double_indirect_entry) + { + if block_modified { + self.update_block(triple_indirect_block); + } + return Some(block_index); // 成功则直接返回 + } else { + // 失败则把这个 double indirect 销毁 + let double_indirect_entry_to_deallocate = + std::mem::replace(double_indirect_entry, 0); + self.data_bitmap + .deallocate(double_indirect_entry_to_deallocate as usize); + triple_indirect_block.dirty = true; + block_modified = true; + } + } + } + if block_modified { + self.update_block(triple_indirect_block); + } + } + None + } + + fn deallocate_from_double_indirect(&mut self, double_indirect_entry: u32) -> Option { + let double_indirect_entry = double_indirect_entry as usize; + if let Some(double_indirect_block) = self + .get_block(double_indirect_entry) + .map(convert::) + { + let mut double_indirect_block = double_indirect_block.clone(); + let mut block_modified = false; + for indirect_entry in double_indirect_block.block.indirect.iter_mut().rev() { + // 如果这个位置的 indirect 存在 + if self.data_bitmap.query(*indirect_entry as usize) { + // 尝试从中销毁一个块 + if let Some(block_index) = self.deallocate_from_indirect(*indirect_entry) { + if block_modified { + self.update_block(double_indirect_block); + } + return Some(block_index); // 成功则直接返回 + } else { + // 失败则把这个 indirect 销毁 + let indirect_entry_to_deallocate = std::mem::replace(indirect_entry, 0); + self.data_bitmap + .deallocate(indirect_entry_to_deallocate as usize); + double_indirect_block.dirty = true; + block_modified = true; + } + } + } + if block_modified { + self.update_block(double_indirect_block); + } + } + None + } + + fn deallocate_from_indirect(&mut self, indirect_entry: u32) -> Option { + let indirect_entry = indirect_entry as usize; + if let Some(indirect_block) = self + .get_block(indirect_entry) + .map(convert::) + { + let mut indirect_block = indirect_block.clone(); + // 遍历 indirect block 里的每个 block + for entry in indirect_block.block.entries.iter_mut().rev() { + // 如果这个 block 存在, 销毁它 + if self.data_bitmap.query(*entry as usize) { + let entry_to_deallocate = std::mem::replace(entry, 0); + + self.data_bitmap.deallocate(entry_to_deallocate as usize); + indirect_block.dirty = true; + self.update_block(indirect_block); + + return Some(entry_to_deallocate); + } + } + } + None + } +} + +impl AyaFS { + pub(crate) fn get_block_index( + &mut self, + inode: &Inode, + mut block_index_within_inode: usize, + ) -> Option { + debug!( + "get_block_index(block_index_within_inode: {})", + block_index_within_inode + ); + // direct block + if block_index_within_inode < DIRECT_NUMBER { + let block_index = inode.direct[block_index_within_inode] as usize; + debug!(" get_block_index -> direct"); + return if self.data_bitmap.query(block_index) { + debug!(" get_block_index -> direct -> ✓"); + Some(block_index) + } else { + debug!(" get_block_index -> direct -> ×"); + None + }; + } else { + block_index_within_inode -= DIRECT_NUMBER; + } + + // indirect block + let indirect_number = ENTRY_PER_BLOCK; + if block_index_within_inode < indirect_number { + return if let Some(indirect_block) = + self.get_block::(inode.single_indirect as usize) + { + debug!(" get_block_index -> indirect"); + let block_index = indirect_block.block.entries[block_index_within_inode] as usize; + if self.data_bitmap.query(block_index) { + debug!(" get_block_index -> indirect -> ✓"); + Some(block_index) + } else { + debug!(" get_block_index -> indirect -> ×"); + None + } + } else { + debug!(" get_block_index -> indirect -> ×"); + None + }; + } else { + block_index_within_inode -= indirect_number; + } + + // double indirect block + let double_indirect_number = ENTRY_PER_BLOCK * ENTRY_PER_BLOCK; + if block_index_within_inode < double_indirect_number { + if let Some(double_indirect_block) = + self.get_block::(inode.double_indirect as usize) + { + debug!(" get_block_index -> double_indirect"); + // 取出 double indirect block + let indirect_block_index = double_indirect_block.block.indirect + [block_index_within_inode / ENTRY_PER_BLOCK] + as usize; + // 要找的 entry 在 double indirect block 中的第几个 indirect block + if let Some(indirect_block) = self.get_block::(indirect_block_index) + { + debug!(" get_block_index -> double_indirect -> indirect"); + let block_index = indirect_block.block.entries + [block_index_within_inode % ENTRY_PER_BLOCK] + as usize; + // 拿到 DirectoryBlock 的 index + return if self.data_bitmap.query(block_index) { + debug!(" get_block_index -> double_indirect -> indirect -> ✓"); + Some(block_index) + } else { + debug!(" get_block_index -> double_indirect -> indirect -> ×"); + None + }; + } + } + return None; + } else { + block_index_within_inode -= double_indirect_number; + } + + // triple indirect block + if let Some(triple_indirect_block) = + self.get_block::(inode.triple_indirect as usize) + { + // 取出 triple indirect block + let double_indirect_block_index = triple_indirect_block.block.double_indirect + [block_index_within_inode / (ENTRY_PER_BLOCK * ENTRY_PER_BLOCK)] + as usize; + // 要找的 entry 在 triple indirect block 中的第几个 double indirect block + if let Some(double_indirect_block) = + self.get_block::(double_indirect_block_index) + { + // 取出 double indirect block + let indirect_block_index = double_indirect_block.block.indirect + [block_index_within_inode % (ENTRY_PER_BLOCK * ENTRY_PER_BLOCK) + / ENTRY_PER_BLOCK] as usize; + // 要找的 entry 在 double indirect block 中的第几个 indirect block + if let Some(indirect_block) = self.get_block::(indirect_block_index) + { + let block_index = indirect_block.block.entries + [block_index_within_inode % ENTRY_PER_BLOCK] + as usize; + // DirectoryBlock 的 index + return if self.data_bitmap.query(block_index) { + Some(block_index) + } else { + None + }; + } + } + } + + None + } + + pub(crate) fn access_block( + &mut self, + inode: &Inode, + block_index_within_inode: usize, + ) -> Option<&CachedBlock> { + self.get_block_index(inode, block_index_within_inode) + .map(|block_index| { + self.get_block::(block_index).unwrap() // 可以 unwrap 吧这里 ?? + }) + } + + pub(crate) fn access_block_mut( + &mut self, + inode: &Inode, + block_index_within_inode: usize, + ) -> Option<&mut CachedBlock> { + self.get_block_index(inode, block_index_within_inode) + .map(|block_index| { + debug!( + "access_block_mut(index: {}) found", + block_index_within_inode + ); + self.get_block_mut::(block_index).unwrap() // 可以 unwrap 吧这里 ?? + }) + } +} diff --git a/ayafs/src/disk/bitmap.rs b/ayafs/src/disk/bitmap.rs new file mode 100644 index 0000000..b68c341 --- /dev/null +++ b/ayafs/src/disk/bitmap.rs @@ -0,0 +1,48 @@ +use crate::block_device::{BlockDevice, BLOCK_SIZE}; +use std::sync::Arc; + +pub struct Bitmap { + pub starting_block: usize, + pub length: usize, + pub device: Arc, + pub data: Vec, +} + +impl Bitmap { + pub(crate) fn new(starting_block: usize, length: usize, device: Arc) -> Self { + Self { + starting_block, + length, + device, + data: vec![0u8; length * BLOCK_SIZE], + } + } + pub(crate) fn allocate(&mut self) -> Option { + for (i, byte) in self.data.iter_mut().enumerate() { + let leading_ones = byte.leading_ones(); + if leading_ones != 8 { + *byte |= (1 << (7 - leading_ones)) as u8; + return Some(i * 8 + leading_ones as usize); + } + } + None + } + + pub(crate) fn query(&self, index: usize) -> bool { + if index == 0 { + false + } else { + self.data[index / 8] & ((1 << (7 - index % 8)) as u8) != 0 + } + } + + pub(crate) fn deallocate(&mut self, index: usize) -> bool { + if self.query(index) { + let mask = !(1u8 << (7 - index % 8)); + self.data[index / 8] &= mask; + true + } else { + false + } + } +} diff --git a/ayafs/src/disk/block.rs b/ayafs/src/disk/block.rs new file mode 100644 index 0000000..73819e2 --- /dev/null +++ b/ayafs/src/disk/block.rs @@ -0,0 +1,245 @@ +use crate::disk::inode::Inode; +use std::ffi::{OsStr, OsString}; +use std::os::unix::ffi::OsStrExt; + +pub trait Block: Default + Clone {} + +#[repr(C)] +#[derive(Clone)] +pub struct DataBlock(pub(crate) [u8; 4096]); + +impl Default for DataBlock { + fn default() -> Self { + Self([0; 4096]) + } +} + +impl Block for DataBlock {} + +#[repr(C)] +#[derive(Clone)] +pub struct InodeBlock { + pub(crate) inodes: [Inode; 32], +} + +impl Default for InodeBlock { + fn default() -> Self { + Self { + inodes: [ + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + ], + } + } +} + +impl Block for InodeBlock {} + +#[repr(C)] +#[derive(Clone)] +pub struct DirectoryEntry { + pub inode: u32, + pub record_len: u16, + pub name_len: u8, + pub file_type: u8, + pub name: [u8; 256], +} + +impl DirectoryEntry { + pub(crate) fn name(&self) -> OsString { + let name = &self.name[0..self.name_len as usize]; + OsStr::from_bytes(name).to_os_string() + } +} + +impl Default for DirectoryEntry { + fn default() -> Self { + Self { + inode: 0, + record_len: 0, + name_len: 0, + file_type: 0x0, + name: [0; 256], + } + } +} + +#[repr(C)] +#[derive(Clone)] +pub struct DirectoryBlock { + pub entries: [DirectoryEntry; 15], + pub occupancy: [u8; 2], + reserved: [u8; 134], +} + +impl Default for DirectoryBlock { + fn default() -> Self { + Self { + entries: [ + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + DirectoryEntry::default(), + ], + occupancy: [0x80, 0x00], // 0b1000_0000 + reserved: [0xFF; 134], + } + } +} + +impl DirectoryBlock { + #[allow(unused)] + pub(crate) fn is_full(&self) -> bool { + self.occupancy[0] == 0xFF && self.occupancy[1] == 0xFF + } + + pub(crate) fn query(&self, mut index: usize) -> bool { + if index < 7 { + // 0-6, first u8 + index = index + 1; + self.occupancy[0] & (1 << (7 - index)) as u8 != 0 + } else if index < 15 { + // 7-14, second u8 + index = index - 7; + self.occupancy[1] & (1 << (7 - index)) as u8 != 0 + } else { + false + } + } + + pub(crate) fn allocate(&mut self, mut index: usize) -> bool { + if index < 7 { + index = index + 1; + let mask = (1 << (7 - index)) as u8; + if self.occupancy[0] & mask != 0 { + false + } else { + self.occupancy[0] |= mask; + true + } + } else { + index = index - 7; + let mask = (1 << (7 - index)) as u8; + if self.occupancy[1] & mask != 0 { + false + } else { + self.occupancy[1] |= mask; + true + } + } + } + + // pub(crate) fn allocate(&mut self) -> Option { + // if self.occupancy[0] != 0xFF { + // let leading_ones = self.occupancy[0].leading_ones(); + // self.occupancy[0] |= (1 << (7 - leading_ones)) as u8; + // Some(leading_ones as usize) + // } else if self.occupancy[1] != 0xFF { + // let leading_ones = self.occupancy[1].leading_ones(); + // self.occupancy[1] |= (1 << (7 - leading_ones)) as u8; + // Some(7 + leading_ones as usize) + // } else { + // None + // } + // } + + pub(crate) fn deallocate(&mut self, mut index: usize) { + if index < 7 { + index = index + 1; + self.occupancy[0] &= !((1 << (7 - index)) as u8); + } else if index < 15 { + // 7-14, second u8 + index = index - 7; + self.occupancy[1] &= !((1 << (7 - index)) as u8); + } + } +} + +impl Block for DirectoryBlock {} + +#[repr(C)] +#[derive(Clone)] +pub struct IndirectBlock { + pub entries: [u32; 1024], +} + +impl Default for IndirectBlock { + fn default() -> Self { + Self { entries: [0; 1024] } + } +} + +impl Block for IndirectBlock {} + +#[repr(C)] +#[derive(Clone)] +pub struct DoubleIndirectBlock { + pub indirect: [u32; 1024], +} + +impl Default for DoubleIndirectBlock { + fn default() -> Self { + Self { + indirect: [0; 1024], + } + } +} + +impl Block for DoubleIndirectBlock {} + +#[repr(C)] +#[derive(Clone)] +pub struct TripleIndirectBlock { + pub double_indirect: [u32; 1024], +} + +impl Default for TripleIndirectBlock { + fn default() -> Self { + Self { + double_indirect: [0; 1024], + } + } +} + +impl Block for TripleIndirectBlock {} diff --git a/ayafs/src/disk/inode.rs b/ayafs/src/disk/inode.rs new file mode 100644 index 0000000..0c801ad --- /dev/null +++ b/ayafs/src/disk/inode.rs @@ -0,0 +1,312 @@ +use crate::utils; +use bitflags::bitflags; +use fuser::FileType; +use crate::block_device::BLOCK_SIZE; + +pub const DIRECT_NUMBER: usize = 15; + +#[derive(Debug, Clone, Copy)] +pub struct InodeMode(pub u16); + +bitflags! { + impl InodeMode: u16 { + const IXOTH = 0x0001; + const IWOTH = 0x0002; + const IROTH = 0x0004; + const IXGRP = 0x0008; + const IWGRP = 0x0010; + const IRGRP = 0x0020; + const IXUSR = 0x0040; + const IWUSR = 0x0080; + const IRUSR = 0x0100; + const ISVTX = 0x0200; + const ISGID = 0x0400; + const ISUID = 0x0800; + // These are mutually-exclusive: + const IFIFO = 0x1000; + const IFCHR = 0x2000; + const IFDIR = 0x4000; + const IFBLK = 0x6000; + const IFREG = 0x8000; + const IFLNK = 0xA000; + const IFSOCK = 0xC000; + } +} + +impl InodeMode { + #[allow(unused)] + pub(crate) fn exec_other(&self) -> bool { + self.0 & Self::IXOTH.0 != 0 + } + #[allow(unused)] + pub(crate) fn write_other(&self) -> bool { + self.0 & Self::IWOTH.0 != 0 + } + #[allow(unused)] + pub(crate) fn read_other(&self) -> bool { + self.0 & Self::IROTH.0 != 0 + } + #[allow(unused)] + pub(crate) fn exec_group(&self) -> bool { + self.0 & Self::IXGRP.0 != 0 + } + #[allow(unused)] + pub(crate) fn write_group(&self) -> bool { + self.0 & Self::IWGRP.0 != 0 + } + #[allow(unused)] + pub(crate) fn read_group(&self) -> bool { + self.0 & Self::IRGRP.0 != 0 + } + #[allow(unused)] + pub(crate) fn exec_user(&self) -> bool { + self.0 & Self::IXUSR.0 != 0 + } + #[allow(unused)] + pub(crate) fn write_user(&self) -> bool { + self.0 & Self::IWUSR.0 != 0 + } + #[allow(unused)] + pub(crate) fn read_user(&self) -> bool { + self.0 & Self::IRUSR.0 != 0 + } + + pub(crate) fn perm(&self) -> u16 { + self.0 & 0x0FFF + } + + pub(crate) fn is_file(&self) -> bool { + (self.0 & 0xF000) == Self::IFREG.0 + } + + pub(crate) fn is_dir(&self) -> bool { + (self.0 & 0xF000) == Self::IFDIR.0 + } + + pub(crate) fn is_symlink(&self) -> bool { + self.0 & 0xF000 == Self::IFLNK.0 + } + + pub(crate) fn validate(mode_value: u16) -> Option { + let valid_flags: [u16; 7] = [0x1000, 0x2000, 0x4000, 0x6000, 0x8000, 0xA000, 0xC000]; + valid_flags + .contains(&(mode_value & 0xF000)) + .then(|| Self(mode_value)) + } +} + +impl From for FileType { + fn from(value: InodeMode) -> Self { + let type_flag = value.0 & 0xF000; + match type_flag { + 0x1000 => FileType::NamedPipe, + 0x2000 => FileType::CharDevice, + 0x4000 => FileType::Directory, + 0x6000 => FileType::BlockDevice, + 0x8000 => FileType::RegularFile, + 0xA000 => FileType::Symlink, + 0xC000 => FileType::Socket, + _ => panic!("Invalid inode mode {:x}", type_flag), + } + } +} + +impl From for u8 { + fn from(value: InodeMode) -> Self { + utils::from_filetype(value.into()) + } +} + +/// Pretty much the same with ext2, with minor changes: +/// - removed OS dependent attributes (osd1 & osd2) +/// - removed i_faddr since fragmentation is not supported +/// - changed uid and gid from u16 to u32 +/// - added more direct blocks for a total size of 128 bytes +/// TODO: do we need to extend time precision? +#[repr(C)] +#[derive(Debug, Clone)] +pub struct Inode { + pub mode: InodeMode, + pub uid: u32, + pub size: u32, + pub atime: u32, // access time, in seconds + pub ctime: u32, // change time, in seconds + pub mtime: u32, // modify time, in seconds + pub crtime: u32, // create time, in seconds + pub gid: u32, + pub n_links: u16, + pub n_blocks: u32, + pub flags: u32, // TODO: do we actually need this? maybe just return 0 + pub direct: [u32; DIRECT_NUMBER], + pub single_indirect: u32, + pub double_indirect: u32, + pub triple_indirect: u32, + pub generation: u32, + pub file_acl: u32, + pub dir_acl: u32, // TODO do we have to implement ACL......? +} + +impl Inode { + fn new( + mode: InodeMode, + uid: u32, + gid: u32, + time: u32, + flags: u32, + generation: u32, + file_acl: u32, + dir_acl: u32, + ) -> Self { + Self { + mode, + uid, + size: 0, + atime: time, + ctime: time, + mtime: time, + crtime: time, + gid, + n_links: 1, + n_blocks: 0, + flags, + direct: [0; DIRECT_NUMBER], + single_indirect: 0, + double_indirect: 0, + triple_indirect: 0, + generation, + file_acl, + dir_acl, + } + } + + #[allow(unused)] + pub fn make_inode( + permissions: u16, + mode: InodeMode, + uid: u32, + gid: u32, + time: u32, + flags: u32, + generation: u32, + file_acl: u32, + dir_acl: u32, + ) -> Self { + Self::new( + InodeMode(permissions) | mode, + uid, + gid, + time, + flags, + generation, + file_acl, + dir_acl, + ) + } + + pub fn directory( + permissions: u16, + uid: u32, + gid: u32, + time: u32, + flags: u32, + generation: u32, + file_acl: u32, + dir_acl: u32, + ) -> Self { + Self::new( + InodeMode(permissions) | InodeMode::IFDIR, + uid, + gid, + time, + flags, + generation, + file_acl, + dir_acl, + ) + } + + pub fn file( + permissions: u16, + uid: u32, + gid: u32, + time: u32, + flags: u32, + generation: u32, + file_acl: u32, + dir_acl: u32, + ) -> Self { + Self::new( + InodeMode(permissions) | InodeMode::IFREG, + uid, + gid, + time, + flags, + generation, + file_acl, + dir_acl, + ) + } + + pub fn symlink( + permissions: u16, + uid: u32, + gid: u32, + time: u32, + flags: u32, + generation: u32, + file_acl: u32, + dir_acl: u32, + ) -> Self { + Self::new( + InodeMode(permissions) | InodeMode::IFLNK, + uid, + gid, + time, + flags, + generation, + file_acl, + dir_acl, + ) + } + + pub(crate) fn is_file(&self) -> bool { + self.mode.is_file() + } + + pub(crate) fn is_dir(&self) -> bool { + self.mode.is_dir() + } + + pub(crate) fn is_symlink(&self) -> bool { + self.mode.is_symlink() + } + + pub(crate) fn file_type(&self) -> FileType { + self.mode.into() + } + + pub fn empty() -> Self { + Self { + mode: InodeMode(0), + uid: 0, + size: 0, + atime: 0, + ctime: 0, + mtime: 0, + crtime: 0, + gid: 0, + n_links: 0, + n_blocks: 0, + flags: 0, + direct: [0; 15], + single_indirect: 0, + double_indirect: 0, + triple_indirect: 0, + generation: 0, + file_acl: 0, + dir_acl: 0, + } + } +} +pub const INODE_SIZE: usize = std::mem::size_of::(); +pub const ENTRY_PER_BLOCK: usize = BLOCK_SIZE / 4; \ No newline at end of file diff --git a/ayafs/src/disk/mod.rs b/ayafs/src/disk/mod.rs new file mode 100644 index 0000000..878e832 --- /dev/null +++ b/ayafs/src/disk/mod.rs @@ -0,0 +1,6 @@ +pub mod allocation; +/// On-disk data structures and logic. +/// Including bitmaps, inodes and blocks. +pub mod bitmap; +pub mod block; +pub mod inode; -- cgit v1.2.3-70-g09d2