diff options
Diffstat (limited to 'src/disk')
| -rw-r--r-- | src/disk/allocation.rs | 159 | ||||
| -rw-r--r-- | src/disk/block.rs | 50 |
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); } } } |