summaryrefslogtreecommitdiff
path: root/ayafs/src/disk/allocation.rs
diff options
context:
space:
mode:
Diffstat (limited to 'ayafs/src/disk/allocation.rs')
-rw-r--r--ayafs/src/disk/allocation.rs542
1 files changed, 0 insertions, 542 deletions
diff --git a/ayafs/src/disk/allocation.rs b/ayafs/src/disk/allocation.rs
deleted file mode 100644
index a187fad..0000000
--- a/ayafs/src/disk/allocation.rs
+++ /dev/null
@@ -1,542 +0,0 @@
-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 吧这里 ??
- })
- }
-}
generated by cgit v1.2.3-70-g09d2 (git 2.46.2) at 2024-10-16 21:34:33 +0000