summaryrefslogtreecommitdiff
path: root/src/disk
diff options
context:
space:
mode:
Diffstat (limited to 'src/disk')
-rw-r--r--src/disk/allocation.rs131
-rw-r--r--src/disk/bitmap.rs30
-rw-r--r--src/disk/block.rs (renamed from src/disk/data_block.rs)0
-rw-r--r--src/disk/mod.rs5
4 files changed, 142 insertions, 24 deletions
diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs
index 291a136..3622e4f 100644
--- a/src/disk/allocation.rs
+++ b/src/disk/allocation.rs
@@ -1,15 +1,16 @@
-use crate::memory::cached_block::convert;
-use crate::disk::data_block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
+use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
use crate::disk::inode::Inode;
+use crate::memory::cached_block::convert;
use crate::AyaFS;
impl AyaFS {
/// 为 Inode 分配新 block, 返回 block 的编号
- pub(crate) fn allocate_block(&mut self, inode: &mut Inode) -> Option<u32> {
+ pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<u32> {
// 先看这个 inode 的 direct block 有没有空闲
for index in inode.direct.iter_mut() {
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;
// 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了
@@ -23,9 +24,11 @@ impl AyaFS {
.data_bitmap
.allocate()
.expect("No free space for new block") as u32;
+ println!("allocating {} for indirect", inode.single_indirect);
}
// 在 indirect block 里尝试分配
if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) {
+ println!("allocating {} in indirect", block_index);
inode.n_blocks += 1;
return Some(block_index);
}
@@ -36,9 +39,11 @@ impl AyaFS {
.data_bitmap
.allocate()
.expect("No free space for new block") as u32;
+ println!("allocating {} for double indirect", inode.double_indirect);
}
// 在 double indirect block 里尝试分配
if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) {
+ println!("allocating {} in double indirect", block_index);
inode.n_blocks += 1;
return Some(block_index);
}
@@ -49,9 +54,11 @@ impl AyaFS {
.data_bitmap
.allocate()
.expect("No free space for new block") as u32;
+ println!("allocating {} for triple indirect", inode.triple_indirect);
}
// 在 double indirect block 里尝试分配
if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) {
+ println!("allocating {} in triple indirect", block_index);
inode.n_blocks += 1;
return Some(block_index);
}
@@ -61,11 +68,13 @@ impl AyaFS {
fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<u32> {
// 取出 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 entry in indirect_block.block.entries.iter_mut() {
if self.data_bitmap.query(*entry as usize) == false {
@@ -130,3 +139,119 @@ impl AyaFS {
None
}
}
+
+impl AyaFS {
+ /// 从 inode 中删去最后一个 block
+ pub(crate) fn deallocate_block(&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
+ .peek_block(triple_indirect_entry)
+ .map(convert::<DataBlock, TripleIndirectBlock>)
+ {
+ for double_indirect_entry in triple_indirect_block
+ .block
+ .double_indirect
+ .into_iter()
+ .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)
+ {
+ return Some(block_index); // 成功则直接返回
+ } else {
+ // 失败则把这个 double indirect 销毁
+ self.data_bitmap.deallocate(double_indirect_entry as usize);
+ }
+ }
+ }
+ }
+ 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
+ .peek_block(double_indirect_entry)
+ .map(convert::<DataBlock, DoubleIndirectBlock>)
+ {
+ for indirect_entry in double_indirect_block.block.indirect.into_iter().rev() {
+ // 如果这个位置的 indirect 存在
+ if self.data_bitmap.query(indirect_entry as usize) {
+ // 尝试从中销毁一个块
+ if let Some(block_index) = self.deallocate_from_indirect(indirect_entry) {
+ return Some(block_index); // 成功则直接返回
+ } else {
+ // 失败则把这个 indirect 销毁
+ self.data_bitmap.deallocate(indirect_entry as usize);
+ }
+ }
+ }
+ }
+ 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
+ .peek_block(indirect_entry)
+ .map(convert::<DataBlock, IndirectBlock>)
+ {
+ // 遍历 indirect block 里的每个 block
+ for entry in indirect_block.block.entries.into_iter().rev() {
+ // 如果这个 block 存在, 销毁它
+ if self.data_bitmap.query(entry as usize) {
+ self.data_bitmap.deallocate(entry as usize);
+ return Some(entry);
+ }
+ }
+ }
+ None
+ }
+}
diff --git a/src/disk/bitmap.rs b/src/disk/bitmap.rs
index 64389c2..b68c341 100644
--- a/src/disk/bitmap.rs
+++ b/src/disk/bitmap.rs
@@ -1,5 +1,4 @@
use crate::block_device::{BlockDevice, BLOCK_SIZE};
-use std::cell::RefCell;
use std::sync::Arc;
pub struct Bitmap {
@@ -10,7 +9,7 @@ pub struct Bitmap {
}
impl Bitmap {
- pub fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> Self {
+ pub(crate) fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> Self {
Self {
starting_block,
length,
@@ -18,8 +17,7 @@ impl Bitmap {
data: vec![0u8; length * BLOCK_SIZE],
}
}
- pub fn allocate(&mut self) -> Option<usize> {
- // let mut data = self.data.borrow_mut();
+ 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 {
@@ -28,11 +26,9 @@ impl Bitmap {
}
}
None
- // panic!("No more space for allocation!")
}
- pub fn query(&self, index: usize) -> bool {
- // let data = self.data.borrow();
+ pub(crate) fn query(&self, index: usize) -> bool {
if index == 0 {
false
} else {
@@ -40,15 +36,13 @@ impl Bitmap {
}
}
- // fn write_back(&mut self) {
- // for block_index_offset in self.dirty_blocks.iter() {
- // let buffer_front_index = BLOCK_SIZE * block_index_offset;
- // let buffer_back_index = BLOCK_SIZE * (block_index_offset + 1);
- // self.device.write(
- // self.starting_block + block_index_offset,
- // &self.data[buffer_front_index..buffer_back_index],
- // );
- // }
- // self.dirty_blocks = Vec::new();
- // }
+ 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/src/disk/data_block.rs b/src/disk/block.rs
index d287ee6..d287ee6 100644
--- a/src/disk/data_block.rs
+++ b/src/disk/block.rs
diff --git a/src/disk/mod.rs b/src/disk/mod.rs
index 65f313c..878e832 100644
--- a/src/disk/mod.rs
+++ b/src/disk/mod.rs
@@ -1,7 +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;
-pub mod data_block;
-pub mod allocation;
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-24 10:31:29 +0000