summaryrefslogtreecommitdiff
path: root/src/disk
diff options
context:
space:
mode:
authorChuyan Zhang <me@zcy.moe>2023-11-25 19:36:31 -0800
committerChuyan Zhang <me@zcy.moe>2023-11-25 19:36:31 -0800
commit777d5e01a34b8ebe6f1a5751b593266f93e88499 (patch)
tree3857444fd8aa3663cb210358ce71cb5d9ea3018e /src/disk
parent76ac602c3d79bb39c133c81a38425a77bc0b8b1f (diff)
downloadmyfs-777d5e01a34b8ebe6f1a5751b593266f93e88499.tar.gz
myfs-777d5e01a34b8ebe6f1a5751b593266f93e88499.zip
Add dir entry operations
Diffstat (limited to 'src/disk')
-rw-r--r--src/disk/allocation.rs159
-rw-r--r--src/disk/block.rs50
2 files changed, 179 insertions, 30 deletions
diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs
index bde2014..57cca0e 100644
--- a/src/disk/allocation.rs
+++ b/src/disk/allocation.rs
@@ -1,20 +1,20 @@
-use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
-use crate::disk::inode::Inode;
-use crate::memory::cached_block::convert;
-use crate::AyaFS;
+use crate::disk::block::{Block, DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
+use crate::disk::inode::{DIRECT_NUMBER, Inode};
+use crate::memory::cached_block::{CachedBlock, convert};
+use crate::{AyaFS, INODE_PER_BLOCK};
impl AyaFS {
- /// 为 Inode 分配新 block, 返回 block 的编号
- pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<u32> {
+ /// 为 Inode 分配新 block, 返回 block 的编号和它在 inode 内的编号
+ pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<(u32, usize)> {
// 先看这个 inode 的 direct block 有没有空闲
- for index in inode.direct.iter_mut() {
+ 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;
// 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了
- return Some(block_index);
+ return Some((block_index, index_within_direct));
}
}
@@ -27,10 +27,11 @@ impl AyaFS {
// println!("allocating {} for indirect", inode.single_indirect);
}
// 在 indirect block 里尝试分配
- if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) {
+ 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;
- return Some(block_index);
+ let index_within_block = DIRECT_NUMBER + index_within_indirect;
+ return Some((block_index, index_within_block));
}
// direct & indirect block 全部分配完了, 先检查 double indirect block 有没有分配, 没有就分配一个
@@ -42,10 +43,11 @@ impl AyaFS {
// println!("allocating {} for double indirect", inode.double_indirect);
}
// 在 double indirect block 里尝试分配
- if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) {
+ 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;
- return Some(block_index);
+ let index_within_block = DIRECT_NUMBER + INODE_PER_BLOCK + index_within_double;
+ return Some((block_index, index_within_block));
}
// direct, indirect & double indirect block 全部分配完了, 先检查 triple indirect block 有没有分配, 没有就分配一个
@@ -57,15 +59,16 @@ impl AyaFS {
// println!("allocating {} for triple indirect", inode.triple_indirect);
}
// 在 double indirect block 里尝试分配
- if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) {
+ 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;
- return Some(block_index);
+ let index_within_block = DIRECT_NUMBER + INODE_PER_BLOCK + INODE_PER_BLOCK * INODE_PER_BLOCK + index_within_triple;
+ return Some((block_index, index_within_block));
}
None
}
- fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<u32> {
+ 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));
@@ -76,20 +79,20 @@ impl AyaFS {
{
// println!("found indirect block with number {}", indirect_entry);
let mut indirect_block = block.clone();
- for entry in indirect_block.block.entries.iter_mut() {
+ 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;
*entry = block_index;
self.update_block(indirect_block);
- return Some(block_index);
+ return Some((block_index, index_within_indirect));
}
}
}
None
}
- fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option<u32> {
+ 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
@@ -97,24 +100,27 @@ impl AyaFS {
.map(convert::<DataBlock, DoubleIndirectBlock>)
{
let mut double_indirect_block = block.clone();
- for indirect_entry in double_indirect_block.block.indirect.iter_mut() {
+ 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;
*indirect_entry = self.data_bitmap.allocate().expect("No free space") as u32;
}
- if let Some(block_index) = self.allocate_in_indirect(*indirect_entry) {
- if double_indirect_block.dirty {
+ if let Some((block_index, index_within_indirect)) = self.allocate_in_indirect(*indirect_entry) {
+ if double_indirect_modified {
self.update_block(double_indirect_block);
}
- return Some(block_index);
+ let index_within_double = index_within_double_indirect * INODE_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> {
+ 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
@@ -122,17 +128,20 @@ impl AyaFS {
.map(convert::<DataBlock, TripleIndirectBlock>)
{
let mut triple_indirect_block = block.clone();
- for double_indirect_entry in triple_indirect_block.block.double_indirect.iter_mut() {
+ 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;
*double_indirect_entry =
self.data_bitmap.allocate().expect("No free space") as u32;
}
- if let Some(block_index) = self.alloc_in_double_indirect(*double_indirect_entry) {
- if triple_indirect_block.dirty {
+ 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);
}
- return Some(block_index);
+ let index_within_triple = index_within_triple_indirect * INODE_PER_BLOCK * INODE_PER_BLOCK + index_within_double_indirect;
+ return Some((block_index, index_within_triple));
}
}
}
@@ -283,3 +292,99 @@ impl AyaFS {
None
}
}
+
+impl AyaFS {
+ fn get_block_index(&mut self, inode: &Inode, mut block_index_within_inode: usize) -> Option<usize> {
+ // direct block
+ if block_index_within_inode < DIRECT_NUMBER {
+ let block_index = inode.direct[block_index_within_inode] as usize;
+ return Some(block_index);
+ } else {
+ block_index_within_inode -= DIRECT_NUMBER;
+ }
+
+ // indirect block
+ let indirect_number = INODE_PER_BLOCK;
+ if block_index_within_inode < indirect_number {
+ return if let Some(indirect_block) =
+ self.get_block::<IndirectBlock>(inode.single_indirect as usize)
+ {
+ let block_index = indirect_block.block.entries[block_index_within_inode] as usize;
+ Some(block_index)
+ } else {
+ None
+ };
+ } else {
+ block_index_within_inode -= indirect_number;
+ }
+
+ // double indirect block
+ let double_indirect_number = INODE_PER_BLOCK * INODE_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)
+ {
+ // 取出 double indirect block
+ let indirect_block_index = double_indirect_block.block.indirect
+ [block_index_within_inode / INODE_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 % INODE_PER_BLOCK]
+ as usize;
+ // 拿到 DirectoryBlock 的 index
+ return Some(block_index)
+ }
+ }
+ 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 / (INODE_PER_BLOCK * INODE_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 % (INODE_PER_BLOCK * INODE_PER_BLOCK)
+ / INODE_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 % INODE_PER_BLOCK]
+ as usize;
+ // DirectoryBlock 的 index
+ return Some(block_index)
+ }
+ }
+ }
+
+ 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| {
+ self.get_block_mut::<T>(block_index).unwrap() // 可以 unwrap 吧这里 ??
+ })
+ }
+} \ No newline at end of file
diff --git a/src/disk/block.rs b/src/disk/block.rs
index 0058b3e..be3d85a 100644
--- a/src/disk/block.rs
+++ b/src/disk/block.rs
@@ -49,7 +49,7 @@ impl Default for InodeBlock {
impl Block for InodeBlock {}
-const FULL_MAP: u32 = 0b111_111_111_111_111;
+const FULL_MAP: u16 = 0b111_111_111_111_111;
#[repr(C)]
#[derive(Clone)]
@@ -84,7 +84,8 @@ impl Default for DirectoryEntry {
#[derive(Clone)]
pub struct DirectoryBlock {
pub entries: [DirectoryEntry; 15],
- reserved: [u8; 136],
+ pub occupancy: [u8; 2],
+ reserved: [u8; 134],
}
impl Default for DirectoryBlock {
@@ -107,7 +108,50 @@ impl Default for DirectoryBlock {
DirectoryEntry::default(),
DirectoryEntry::default(),
],
- reserved: [0xFF; 136],
+ occupancy: [0x80, 0x00], // 0b1000_0000
+ reserved: [0xFF; 134],
+ }
+ }
+}
+
+impl DirectoryBlock {
+ 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) -> 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);
}
}
}