summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/block_device/memory_disk.rs4
-rw-r--r--src/block_device/mod.rs1
-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
-rw-r--r--src/filesystem/trait_impl.rs13
-rw-r--r--src/main.rs25
-rw-r--r--src/memory/cached_block.rs201
-rw-r--r--src/memory/cached_inode.rs48
-rw-r--r--src/memory/mod.rs1
-rw-r--r--src/tests/bitmap.rs23
-rw-r--r--src/tests/block_cache.rs79
-rw-r--r--src/tests/common/mod.rs8
-rw-r--r--src/tests/mod.rs6
15 files changed, 492 insertions, 83 deletions
diff --git a/src/block_device/memory_disk.rs b/src/block_device/memory_disk.rs
index 3876736..0639d3e 100644
--- a/src/block_device/memory_disk.rs
+++ b/src/block_device/memory_disk.rs
@@ -9,9 +9,9 @@ pub struct MemoryDisk {
}
impl MemoryDisk {
- pub fn new() -> Self {
+ pub fn new(block_number: usize) -> Self {
Self {
- arena: RefCell::new(vec![0u8; BLOCK_SIZE * 16384]),
+ arena: RefCell::new(vec![0u8; BLOCK_SIZE * block_number]),
}
}
}
diff --git a/src/block_device/mod.rs b/src/block_device/mod.rs
index c7e1362..a8fd8b7 100644
--- a/src/block_device/mod.rs
+++ b/src/block_device/mod.rs
@@ -1,6 +1,5 @@
/// Abstracts for block devices.
/// Currently only a mock memory disk.
-
pub mod memory_disk;
pub const BLOCK_SIZE: usize = 4096;
pub trait BlockDevice {
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;
diff --git a/src/filesystem/trait_impl.rs b/src/filesystem/trait_impl.rs
index 9f157a5..3a60578 100644
--- a/src/filesystem/trait_impl.rs
+++ b/src/filesystem/trait_impl.rs
@@ -1,9 +1,12 @@
-use std::ffi::OsStr;
-use std::time::SystemTime;
-use fuser::{Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry, ReplyLseek, ReplyWrite, Request, TimeOrNow};
+use crate::AyaFS;
+use fuser::{
+ Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry,
+ ReplyLseek, ReplyWrite, Request, TimeOrNow,
+};
use libc::{c_int, ENOENT, ENOSPC, ENOSYS};
use log::debug;
-use crate::AyaFS;
+use std::ffi::OsStr;
+use std::time::SystemTime;
impl Filesystem for AyaFS {
fn init(&mut self, _req: &Request<'_>, _config: &mut KernelConfig) -> Result<(), c_int> {
@@ -186,4 +189,4 @@ impl Filesystem for AyaFS {
);
reply.error(ENOSYS);
}
-} \ No newline at end of file
+}
diff --git a/src/main.rs b/src/main.rs
index e01d352..a5ec616 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,7 +1,8 @@
mod block_device;
mod disk;
-mod memory;
mod filesystem;
+mod memory;
+mod tests;
mod utils;
use clap::Parser;
@@ -12,12 +13,14 @@ use std::num::NonZeroUsize;
use std::sync::Arc;
use std::time::Duration;
-use memory::cached_block::CachedBlock;
-use disk::data_block::DataBlock;
+use crate::disk::block::InodeBlock;
use crate::disk::inode::InodeMode;
-use block_device::{BLOCK_SIZE, BlockDevice, memory_disk::MemoryDisk};
+use crate::memory::cached_block::BlockCache;
+use block_device::{memory_disk::MemoryDisk, BlockDevice, BLOCK_SIZE};
use disk::bitmap::Bitmap;
+use disk::block::DataBlock;
use disk::inode::INODE_SIZE;
+use memory::cached_block::CachedBlock;
use users::{get_current_gid, get_current_uid};
#[derive(Parser, Debug)]
@@ -61,8 +64,10 @@ struct AyaFS {
inode_start_block: usize,
data_start_block: usize,
- // cached_inodes: LruCache<usize, CachedInode>,
- cached_blocks: LruCache<usize, CachedBlock<DataBlock>>,
+ cached_inodes: BlockCache<InodeBlock>,
+ cached_blocks: BlockCache<DataBlock>,
+ // cached_inodes: LruCache<usize, CachedBlock<InodeBlock>>,
+ // cached_blocks: LruCache<usize, CachedBlock<DataBlock>>,
}
impl AyaFS {
@@ -103,7 +108,7 @@ impl AyaFS {
let _ = inode_bitmap.allocate().unwrap(); // inode block 0 is not usable
let mut fs = Self {
- device,
+ device: device.clone(),
data_bitmap,
inode_bitmap,
inode_start_block: data_bitmap_block_number + inode_bitmap_block_number + 1,
@@ -111,8 +116,10 @@ impl AyaFS {
+ inode_bitmap_block_number
+ inode_block_number
+ 1,
+ cached_inodes: BlockCache::new(device.clone(), 256),
+ cached_blocks: BlockCache::new(device.clone(), 256),
// cached_inodes: LruCache::new(NonZeroUsize::new(256).unwrap()),
- cached_blocks: LruCache::new(NonZeroUsize::new(256).unwrap()),
+ // cached_blocks: LruCache::new(NonZeroUsize::new(256).unwrap()),
};
fs.create_inode(
@@ -137,7 +144,7 @@ fn main() {
MountOption::AutoUnmount,
MountOption::AllowRoot,
];
- let mem_disk = Arc::new(MemoryDisk::new());
+ let mem_disk = Arc::new(MemoryDisk::new(16384));
let filesystem = AyaFS::new(mem_disk, 16384);
fuser::mount2(filesystem, mount_point, &options).unwrap();
diff --git a/src/memory/cached_block.rs b/src/memory/cached_block.rs
index 0c401ff..9e266ef 100644
--- a/src/memory/cached_block.rs
+++ b/src/memory/cached_block.rs
@@ -1,7 +1,10 @@
-use and_then_some::BoolExt;
+use crate::block_device::{BlockDevice, BLOCK_SIZE};
+use crate::disk::block::Block;
use crate::AyaFS;
-use crate::block_device::BLOCK_SIZE;
-use crate::disk::data_block::{Block, DataBlock};
+use and_then_some::BoolExt;
+use lru::LruCache;
+use std::num::NonZeroUsize;
+use std::sync::Arc;
#[derive(Clone)]
pub struct CachedBlock<T: Block> {
@@ -28,39 +31,24 @@ pub fn convert<U: Block, T: Block>(input_block: &CachedBlock<U>) -> &CachedBlock
unsafe { &*block }
}
-impl AyaFS {
- pub(crate) fn update_block<T: Block>(&mut self, block: CachedBlock<T>) -> bool {
- if self.cached_blocks.contains(&block.index) {
- let data_block = convert::<T, DataBlock>(&block).clone();
- self.cached_blocks.push(block.index, data_block);
- true
- } else {
- false
- }
- }
- pub(crate) fn get_block<T: Block>(&mut self, index: usize) -> Option<&CachedBlock<T>> {
- self.load_block(index)
- .and_then(|| self.cached_blocks.get(&index).map(convert::<DataBlock, T>))
- }
+pub(crate) struct BlockCache<T: Block> {
+ device: Arc<dyn BlockDevice>,
+ cache: LruCache<usize, CachedBlock<T>>,
+}
- pub(crate) fn get_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
- self.load_block(index).and_then(|| {
- self.cached_blocks
- .get_mut(&index)
- .map(convert_mut::<DataBlock, T>)
- })
+impl<T: Block> BlockCache<T> {
+ pub(crate) fn new(device: Arc<dyn BlockDevice>, cache_size: usize) -> Self {
+ Self {
+ device,
+ cache: LruCache::new(NonZeroUsize::new(cache_size).unwrap()),
+ }
}
pub(crate) fn load_block(&mut self, index: usize) -> bool {
- // 反正我自己保证所有实现了 Block trait 的数据结构都是 4K bytes 长, 来回 cast 没问题
- // 如果 block cache 里没有这个 block
- if self.cached_blocks.contains(&index) == false {
- if self.data_bitmap.query(index) == false {
- return false;
- } // 先看这个 block 是不是 valid, 不 valid 直接返回 None
- let block = DataBlock::default();
+ if self.cache.contains(&index) == false {
+ let block = T::default();
let buffer = unsafe {
- std::slice::from_raw_parts_mut(&block as *const DataBlock as *mut u8, BLOCK_SIZE)
+ std::slice::from_raw_parts_mut(&block as *const T as *mut u8, BLOCK_SIZE)
};
self.device.read(index, buffer);
let cached_block = CachedBlock {
@@ -68,17 +56,160 @@ impl AyaFS {
index,
dirty: false,
};
- if let Some((old_index, old_block)) = self.cached_blocks.push(index, cached_block) {
+ if let Some((old_index, old_block)) = self.cache.push(index, cached_block) {
assert_ne!(old_index, index); // 只有 block 不在 cache 里的时候才会插入
if old_block.dirty {
- let old_block_ptr = &old_block.block as *const DataBlock as *mut u8;
+ let old_block_ptr = &old_block.block as *const T as *mut u8;
let old_block_buffer =
unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) };
self.device.write(old_index, old_block_buffer);
}
- } // 如果 valid 就放到 block cache 里, 同时将（可能）被驱逐的 block 依据其是否为脏块进行写回
+ }
}
-
true
}
+
+ /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载.
+ pub(crate) fn get_block<U: Block>(&mut self, index: usize) -> Option<&CachedBlock<U>> {
+ self.load_block(index)
+ .and_then(|| self.cache.get(&index).map(convert::<T, U>))
+ }
+
+ /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载.
+ pub(crate) fn get_block_mut<U: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<U>> {
+ self.load_block(index)
+ .and_then(|| self.cache.get_mut(&index).map(convert_mut::<T, U>))
+ }
+
+ /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+ pub(crate) fn peek_block<U: Block>(&self, index: usize) -> Option<&CachedBlock<U>> {
+ self.cache.peek(&index).map(convert::<T, U>)
+ }
+
+ /// 从 LRU cache 中读取一个 block 的可变引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+ pub(crate) fn peek_block_mut<U: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<U>> {
+ self.cache.peek_mut(&index).map(convert_mut::<T, U>)
+ }
+
+ pub(crate) fn update_block<U: Block>(&mut self, block: CachedBlock<U>) -> bool {
+ if self.cache.contains(&block.index) {
+ let data_block = convert::<U, T>(&block).clone();
+ self.cache.push(block.index, data_block);
+ true
+ } else {
+ false
+ }
+ }
+
+ fn pop(&mut self, entry: &usize) -> Option<CachedBlock<T>> {
+ self.cache.pop(entry)
+ }
+}
+
+impl AyaFS {
+ pub(crate) fn load_block(&mut self, index: usize) -> bool {
+ if !self.data_bitmap.query(index) {
+ self.cached_blocks.pop(&index);
+ // deallocate 时只更新 bitmap 没有动 cache, lazy 地驱逐 cache 中的无效 entry.
+ return false;
+ }
+ self.cached_blocks.load_block(index)
+ }
+
+ pub(crate) fn get_block<T: Block>(&mut self, index: usize) -> Option<&CachedBlock<T>> {
+ self.data_bitmap
+ .query(index)
+ .and_then(|| self.cached_blocks.get_block::<T>(index))
+ }
+
+ pub(crate) fn get_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+ self.data_bitmap
+ .query(index)
+ .and_then(|| self.cached_blocks.get_block_mut::<T>(index))
+ }
+
+ pub(crate) fn peek_block<T: Block>(&self, index: usize) -> Option<&CachedBlock<T>> {
+ self.data_bitmap
+ .query(index)
+ .and_then(|| self.cached_blocks.peek_block::<T>(index))
+ }
+
+ pub(crate) fn peek_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+ self.data_bitmap
+ .query(index)
+ .and_then(|| self.cached_blocks.peek_block_mut::<T>(index))
+ }
+
+ pub(crate) fn update_block<T: Block>(&mut self, block: CachedBlock<T>) -> bool {
+ self.cached_blocks.update_block(block)
+ }
+
+ // pub(crate) fn update_block<T: Block>(&mut self, block: CachedBlock<T>) -> bool {
+ // if self.cached_blocks.contains(&block.index) {
+ // let data_block = convert::<T, DataBlock>(&block).clone();
+ // self.cached_blocks.push(block.index, data_block);
+ // true
+ // } else {
+ // false
+ // }
+ // }
+ //
+ // /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载.
+ // pub(crate) fn get_block<T: Block>(&mut self, index: usize) -> Option<&CachedBlock<T>> {
+ // self.load_block(index)
+ // .and_then(|| self.cached_blocks.get(&index).map(convert::<DataBlock, T>))
+ // }
+ //
+ // /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载.
+ // pub(crate) fn get_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+ // self.load_block(index).and_then(|| {
+ // self.cached_blocks
+ // .get_mut(&index)
+ // .map(convert_mut::<DataBlock, T>)
+ // })
+ // }
+ //
+ // /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+ // pub(crate) fn peek_block<T: Block>(&self, index: usize) -> Option<&CachedBlock<T>> {
+ // self.cached_blocks.peek(&index).map(convert::<DataBlock, T>)
+ // }
+ //
+ // /// 从 LRU cache 中读取一个 block 的可变引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+ // pub(crate) fn peek_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+ // self.cached_blocks.peek_mut(&index).map(convert_mut::<DataBlock, T>)
+ // }
+ //
+ // pub(crate) fn load_block(&mut self, index: usize) -> bool {
+ // // 先看这个 block 是不是 valid, 不 valid 直接返回 false.
+ // if !self.data_bitmap.query(index) {
+ // self.cached_blocks.pop(&index);
+ // // deallocate 时只更新 bitmap 没有动 cache, lazy 地驱逐 cache 中的无效 entry.
+ // return false;
+ // }
+ //
+ // // 接下来这个 block 一定 valid. 如果 cache 里没有这个 block 就把它 load 到 cache 里
+ // if self.cached_blocks.contains(&index) == false {
+ // let block = DataBlock::default();
+ // let buffer = unsafe {
+ // std::slice::from_raw_parts_mut(&block as *const DataBlock as *mut u8, BLOCK_SIZE)
+ // };
+ // self.device.read(index, buffer);
+ // let cached_block = CachedBlock {
+ // block,
+ // index,
+ // dirty: false,
+ // };
+ // if let Some((old_index, old_block)) = self.cached_blocks.push(index, cached_block) {
+ // assert_ne!(old_index, index); // 只有 block 不在 cache 里的时候才会插入
+ // if old_block.dirty {
+ // let old_block_ptr = &old_block.block as *const DataBlock as *mut u8;
+ // let old_block_buffer =
+ // unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) };
+ // self.device.write(old_index, old_block_buffer);
+ // }
+ // }
+ // }
+ //
+ // true
+ // }
}
diff --git a/src/memory/cached_inode.rs b/src/memory/cached_inode.rs
index b51d279..b81bd2e 100644
--- a/src/memory/cached_inode.rs
+++ b/src/memory/cached_inode.rs
@@ -1,7 +1,7 @@
-use and_then_some::BoolExt;
+use crate::disk::block::{Block, InodeBlock};
+use crate::disk::inode::{Inode, InodeMode, INODE_SIZE};
use crate::AyaFS;
-use crate::disk::data_block::InodeBlock;
-use crate::disk::inode::{Inode, INODE_SIZE, InodeMode};
+use and_then_some::BoolExt;
impl AyaFS {
pub(crate) fn create_inode(
@@ -30,10 +30,24 @@ impl AyaFS {
})
}
+ pub(crate) fn update_inode(&mut self, inode_index: usize, inode: Inode) -> bool {
+ if self.inode_bitmap.query(inode_index) {
+ let (block_index, offset) = self.locate_inode(inode_index);
+ if let Some(cached_block) = self.cached_inodes.get_block_mut::<InodeBlock>(block_index)
+ {
+ cached_block.block.inodes[offset / INODE_SIZE] = inode;
+ }
+ true
+ } else {
+ false
+ }
+ }
+
pub(crate) fn get_inode(&mut self, inode_index: usize) -> Option<&Inode> {
self.inode_bitmap.query(inode_index).and_then(|| {
let (block_index, offset) = self.locate_inode(inode_index);
- self.get_block::<InodeBlock>(block_index)
+ self.cached_inodes
+ .get_block::<InodeBlock>(block_index)
.map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE])
})
}
@@ -41,11 +55,33 @@ impl AyaFS {
pub(crate) fn get_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> {
self.inode_bitmap.query(inode_index).and_then(|| {
let (block_index, offset) = self.locate_inode(inode_index);
- self.get_block_mut::<InodeBlock>(block_index)
+ self.cached_inodes
+ .get_block_mut::<InodeBlock>(block_index)
+ .map(|cached_block| {
+ cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏
+ &mut cached_block.block.inodes[offset / INODE_SIZE]
+ })
+ })
+ }
+
+ pub(crate) fn peek_inode(&self, inode_index: usize) -> Option<&Inode> {
+ self.inode_bitmap.query(inode_index).and_then(|| {
+ let (block_index, offset) = self.locate_inode(inode_index);
+ self.cached_inodes
+ .peek_block::<InodeBlock>(block_index)
+ .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE])
+ })
+ }
+
+ pub(crate) fn peek_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> {
+ self.inode_bitmap.query(inode_index).and_then(|| {
+ let (block_index, offset) = self.locate_inode(inode_index);
+ self.cached_inodes
+ .peek_block_mut::<InodeBlock>(block_index)
.map(|cached_block| {
cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏
&mut cached_block.block.inodes[offset / INODE_SIZE]
})
})
}
-} \ No newline at end of file
+}
diff --git a/src/memory/mod.rs b/src/memory/mod.rs
index ffdf04c..3380d0f 100644
--- a/src/memory/mod.rs
+++ b/src/memory/mod.rs
@@ -1,5 +1,4 @@
/// In-memory data structures and logic.
/// This is where the crucial block and inode methods presented to upper calls implemented.
-
pub mod cached_block;
pub mod cached_inode;
diff --git a/src/tests/bitmap.rs b/src/tests/bitmap.rs
new file mode 100644
index 0000000..9b21b6f
--- /dev/null
+++ b/src/tests/bitmap.rs
@@ -0,0 +1,23 @@
+use crate::tests::common;
+
+#[test]
+fn test_allocate() {
+ let mut fs = common::setup();
+ for _ in 0..10 {
+ fs.data_bitmap.allocate().unwrap();
+ }
+ assert!(fs.data_bitmap.deallocate(5));
+ assert_eq!(fs.data_bitmap.allocate().unwrap(), 5);
+ assert_eq!(fs.data_bitmap.allocate().unwrap(), 11);
+}
+
+#[test]
+fn test_query() {
+ let mut fs = common::setup();
+ for _ in 0..10 {
+ fs.data_bitmap.allocate().unwrap();
+ }
+ assert_eq!(fs.data_bitmap.query(0), false);
+ assert_eq!(fs.data_bitmap.query(5), true);
+ assert_eq!(fs.data_bitmap.query(11), false);
+}
diff --git a/src/tests/block_cache.rs b/src/tests/block_cache.rs
new file mode 100644
index 0000000..f1c18cc
--- /dev/null
+++ b/src/tests/block_cache.rs
@@ -0,0 +1,79 @@
+use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock};
+use crate::disk::inode::InodeMode;
+use crate::tests::common;
+
+#[test]
+fn test_basic_lru() {
+ let mut fs = common::setup();
+
+ let v: Vec<usize> = (1..=256)
+ .map(|_| {
+ let index = fs.data_bitmap.allocate().unwrap();
+ fs.get_block::<DataBlock>(index).unwrap();
+ index
+ })
+ .collect();
+ assert!(fs.peek_block::<DataBlock>(v[0]).is_some());
+
+ for i in 0..256 {
+ let index = fs.data_bitmap.allocate().unwrap();
+ fs.get_block::<DataBlock>(index).unwrap();
+ assert!(fs.peek_block::<DataBlock>(v[i]).is_none());
+ }
+}
+
+#[test]
+fn test_inode() {
+ let mut fs = common::setup();
+
+ let inode_index = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap();
+ let mut inode = fs.get_inode(inode_index).unwrap().clone();
+
+ const DIRECT_NUMBER: u32 = 15;
+ const INDIRECT_NUMBER: u32 = 1024;
+ const DOUBLE_INDIRECT_NUMBER: u32 = 1024 * 1024;
+
+ for i in 0..DIRECT_NUMBER {
+ fs.allocate_block_for(&mut inode).unwrap();
+ assert!(fs.data_bitmap.query(inode.direct[i as usize] as usize))
+ }
+
+ for i in 0..INDIRECT_NUMBER {
+ fs.allocate_block_for(&mut inode).unwrap();
+ }
+
+ for i in 0..DOUBLE_INDIRECT_NUMBER {
+ fs.allocate_block_for(&mut inode).unwrap();
+ }
+
+ let single_indirect = inode.single_indirect;
+ let double_indirect = inode.double_indirect;
+ let triple_indirect = inode.triple_indirect;
+
+ fs.update_inode(inode_index, inode);
+
+ let indirect_block = fs
+ .peek_block::<IndirectBlock>(single_indirect as usize)
+ .unwrap();
+ for entry in indirect_block.block.entries {
+ assert_ne!(entry, 0);
+ assert!(fs.data_bitmap.query(entry as usize));
+ }
+
+ // let double_indirect_block = fs
+ // .peek_block::<DoubleIndirectBlock>(double_indirect as usize)
+ // .unwrap();
+ // for indirect_entry in double_indirect_block.block.indirect {
+ // let indirect_block = fs
+ // .peek_block::<IndirectBlock>(indirect_entry as usize)
+ // .unwrap();
+ // for entry in indirect_block.block.entries {
+ // assert_ne!(entry, 0);
+ // assert!(fs.data_bitmap.query(entry as usize));
+ // }
+ // }
+
+ assert_eq!(fs.data_bitmap.query(double_indirect as usize), false);
+
+ assert_eq!(fs.data_bitmap.query(triple_indirect as usize), false);
+}
diff --git a/src/tests/common/mod.rs b/src/tests/common/mod.rs
new file mode 100644
index 0000000..9314fd9
--- /dev/null
+++ b/src/tests/common/mod.rs
@@ -0,0 +1,8 @@
+use crate::block_device::memory_disk::MemoryDisk;
+use crate::AyaFS;
+use std::sync::Arc;
+
+pub(crate) fn setup() -> AyaFS {
+ let mem_disk = Arc::new(MemoryDisk::new(1059715));
+ AyaFS::new(mem_disk, 1059715)
+}
diff --git a/src/tests/mod.rs b/src/tests/mod.rs
new file mode 100644
index 0000000..df442c1
--- /dev/null
+++ b/src/tests/mod.rs
@@ -0,0 +1,6 @@
+#[cfg(test)]
+mod bitmap;
+mod common;
+
+#[cfg(test)]
+mod block_cache;
generated by cgit v1.2.3-70-g09d2 (git 2.46.2) at 2024-10-16 16:27:30 +0000