summaryrefslogtreecommitdiff
path: root/ayafs-core/src/disk
diff options
context:
space:
mode:
authorChuyan Zhang <me@zcy.moe>2023-11-30 12:01:11 -0800
committerChuyan Zhang <me@zcy.moe>2023-11-30 12:01:11 -0800
commitfd125947c9db0b33761414e65e919f73d9bf1815 (patch)
treec4c66d95ba85601427928aa7f23659590055d464 /ayafs-core/src/disk
parent1eac97eea4ec0bcef0be061a2cba93a584355283 (diff)
downloadmyfs-fd125947c9db0b33761414e65e919f73d9bf1815.tar.gz
myfs-fd125947c9db0b33761414e65e919f73d9bf1815.zip
Refactor workspace
Diffstat (limited to 'ayafs-core/src/disk')
-rw-r--r--ayafs-core/src/disk/allocation.rs542
-rw-r--r--ayafs-core/src/disk/bitmap.rs48
-rw-r--r--ayafs-core/src/disk/block.rs271
-rw-r--r--ayafs-core/src/disk/inode.rs312
-rw-r--r--ayafs-core/src/disk/mod.rs6
5 files changed, 1179 insertions, 0 deletions
diff --git a/ayafs-core/src/disk/allocation.rs b/ayafs-core/src/disk/allocation.rs
new file mode 100644
index 0000000..a187fad
--- /dev/null
+++ b/ayafs-core/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::<DataBlock, IndirectBlock>)
+ {
+ // 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::<DataBlock, DoubleIndirectBlock>)
+ {
+ 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::<DataBlock, TripleIndirectBlock>)
+ {
+ 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::<IndirectBlock>(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::<DoubleIndirectBlock>(inode.double_indirect as usize)
+ .unwrap();
+ for indirect_block_index in double_indirect.block.indirect {
+ if let Some(indirect) =
+ self.get_block::<IndirectBlock>(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::<TripleIndirectBlock>(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::<DoubleIndirectBlock>(double_indirect_block_index as usize)
+ {
+ for indirect_block_index in double_indirect.block.indirect {
+ if let Some(indirect) =
+ self.get_block::<IndirectBlock>(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<u32> {
+ // 如果 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<u32> {
+ let triple_indirect_entry = triple_indirect_entry as usize;
+ if let Some(triple_indirect_block) = self
+ .get_block(triple_indirect_entry)
+ .map(convert::<DataBlock, TripleIndirectBlock>)
+ {
+ 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<u32> {
+ let double_indirect_entry = double_indirect_entry as usize;
+ if let Some(double_indirect_block) = self
+ .get_block(double_indirect_entry)
+ .map(convert::<DataBlock, DoubleIndirectBlock>)
+ {
+ 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<u32> {
+ let indirect_entry = indirect_entry as usize;
+ if let Some(indirect_block) = self
+ .get_block(indirect_entry)
+ .map(convert::<DataBlock, IndirectBlock>)
+ {
+ 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<usize> {
+ 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::<IndirectBlock>(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::<DoubleIndirectBlock>(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::<IndirectBlock>(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::<TripleIndirectBlock>(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::<DoubleIndirectBlock>(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::<IndirectBlock>(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<T: Block>(
+ &mut self,
+ inode: &Inode,
+ block_index_within_inode: usize,
+ ) -> Option<&CachedBlock<T>> {
+ self.get_block_index(inode, block_index_within_inode)
+ .map(|block_index| {
+ self.get_block::<T>(block_index).unwrap() // 可以 unwrap 吧这里 ??
+ })
+ }
+
+ pub(crate) fn access_block_mut<T: Block>(
+ &mut self,
+ inode: &Inode,
+ block_index_within_inode: usize,
+ ) -> Option<&mut CachedBlock<T>> {
+ 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::<T>(block_index).unwrap() // 可以 unwrap 吧这里 ??
+ })
+ }
+}
diff --git a/ayafs-core/src/disk/bitmap.rs b/ayafs-core/src/disk/bitmap.rs
new file mode 100644
index 0000000..b68c341
--- /dev/null
+++ b/ayafs-core/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<dyn BlockDevice>,
+ pub data: Vec<u8>,
+}
+
+impl Bitmap {
+ pub(crate) fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> Self {
+ Self {
+ starting_block,
+ length,
+ device,
+ data: vec![0u8; length * BLOCK_SIZE],
+ }
+ }
+ pub(crate) fn allocate(&mut self) -> Option<usize> {
+ 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-core/src/disk/block.rs b/ayafs-core/src/disk/block.rs
new file mode 100644
index 0000000..76769b9
--- /dev/null
+++ b/ayafs-core/src/disk/block.rs
@@ -0,0 +1,271 @@
+use crate::disk::inode::Inode;
+use std::ffi::{OsStr, OsString};
+use std::os::unix::ffi::OsStrExt;
+
+pub trait Block: Default + Clone {}
+
+#[repr(C)]
+pub struct SuperBlock {
+ pub(crate) data_bitmap_block_number: u64,
+ pub(crate) inode_bitmap_block_number: u64,
+ pub(crate) inode_block_number: u64,
+ pub(crate) data_block_number: u64,
+ padding: [u8; 4064],
+}
+
+impl SuperBlock {
+ pub(crate) fn new(
+ data_bitmap_block_number: usize,
+ inode_bitmap_block_number: usize,
+ inode_block_number: usize,
+ data_block_number: usize,
+ ) -> Self {
+ Self {
+ data_bitmap_block_number: data_bitmap_block_number as u64,
+ inode_bitmap_block_number: inode_bitmap_block_number as u64,
+ inode_block_number: inode_block_number as u64,
+ data_block_number: data_block_number as u64,
+ padding: [0; 4064],
+ }
+ }
+}
+
+#[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<usize> {
+ // 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-core/src/disk/inode.rs b/ayafs-core/src/disk/inode.rs
new file mode 100644
index 0000000..d94b795
--- /dev/null
+++ b/ayafs-core/src/disk/inode.rs
@@ -0,0 +1,312 @@
+use crate::block_device::BLOCK_SIZE;
+use crate::utils;
+use bitflags::bitflags;
+use fuser::FileType;
+
+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<Self> {
+ let valid_flags: [u16; 7] = [0x1000, 0x2000, 0x4000, 0x6000, 0x8000, 0xA000, 0xC000];
+ valid_flags
+ .contains(&(mode_value & 0xF000))
+ .then(|| Self(mode_value))
+ }
+}
+
+impl From<InodeMode> 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<InodeMode> 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::<Inode>();
+pub const ENTRY_PER_BLOCK: usize = BLOCK_SIZE / 4;
diff --git a/ayafs-core/src/disk/mod.rs b/ayafs-core/src/disk/mod.rs
new file mode 100644
index 0000000..878e832
--- /dev/null
+++ b/ayafs-core/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;