123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422 |
- use alloc::{boxed::Box, vec::Vec};
- use hashbrown::HashMap;
- use crate::{driver::base::block::block_device::BlockId, libs::rwlock::RwLock};
- use super::{
- cache_block::{CacheBlock, CacheBlockAddr},
- cache_iter::{BlockIter, FailData},
- BlockCacheError, BLOCK_SIZE, BLOCK_SIZE_LOG, CACHE_THRESHOLD,
- };
- static mut CSPACE: Option<LockedCacheSpace> = None;
- static mut CMAPPER: Option<LockedCacheMapper> = None;
- /// # 结构功能
- /// 该结构体向外提供BlockCache服务
- pub struct BlockCache;
- unsafe fn mapper() -> Result<&'static mut LockedCacheMapper, BlockCacheError> {
- unsafe {
- match &mut CMAPPER {
- Some(x) => return Ok(x),
- None => return Err(BlockCacheError::StaticParameterError),
- }
- };
- }
- unsafe fn space() -> Result<&'static mut LockedCacheSpace, BlockCacheError> {
- unsafe {
- match &mut CSPACE {
- Some(x) => return Ok(x),
- None => return Err(BlockCacheError::StaticParameterError),
- }
- };
- }
- impl BlockCache {
- /// # 函数的功能
- /// 初始化BlockCache需要的结构体
- pub fn init() {
- unsafe {
- CSPACE = Some(LockedCacheSpace::new(CacheSpace::new()));
- CMAPPER = Some(LockedCacheMapper::new(CacheMapper::new()));
- }
- kdebug!("BlockCache Initialized!");
- }
- /// # 函数的功能
- /// 使用blockcache进行对块设备进行连续块的读操作
- ///
- /// ## 参数:
- /// - 'lba_id_start' :连续块的起始块的lba_id
- /// - 'count' :从连续块算起需要读多少块
- /// - 'buf' :读取出来的数据存放在buf中
- ///
- /// ## 返回值:
- /// - Ok(usize) :表示读取块的个数
- /// - Err(BlockCacheError::BlockFaultError) :缺块的情况下,返回读取失败的块的数据,利用该返回值可以帮助blockcache插入读取失败的块值(见insert函数)
- /// - Err(BlockCacheError::____) :不缺块的情况往往是初始化或者其他问题,这种异常会在block_device中得到处理
- pub fn read(
- lba_id_start: BlockId,
- count: usize,
- buf: &mut [u8],
- ) -> Result<usize, BlockCacheError> {
- // 生成一个块迭代器(BlockIter),它可以迭代地给出所有需要块的数据,其中就包括lba_id
- let block_iter = BlockIter::new(lba_id_start, count, BLOCK_SIZE);
- // 调用检查函数,检查有无缺块,如果没有就可以获得所有块的Cache地址。如果失败了就直接返回FailData向量
- let cache_block_addr = Self::check_able_to_read(block_iter)?;
- // 块地址vec的长度应当等于块迭代器的大小
- assert!(cache_block_addr.len() == block_iter.count());
- // 迭代地读取cache并写入到buf中
- for (index, _) in block_iter.enumerate() {
- Self::read_one_block(cache_block_addr[index], index, buf)?;
- }
- return Ok(count);
- }
- /// # 函数的功能
- /// 检查cache中是否有缺块的函数
- ///
- /// ## 参数:
- /// - 'block_iter' :需要检查的块迭代器(因为块迭代器包含了需要读块的信息,所以传入块迭代器)
- ///
- /// ## 返回值:
- /// - Ok(Vec<CacheBlockAddr>) :如果成功了,那么函数会返回每个块的Cache地址,利用Cache地址就可以访问Cache了
- /// - Err(BlockCacheError::BlockFaultError) :如果发现了缺块,那么我们会返回所有缺块的信息(即FailData)
- /// - Err(BlockCacheError::____) :不缺块的情况往往是初始化或者其他问题
- fn check_able_to_read(block_iter: BlockIter) -> Result<Vec<CacheBlockAddr>, BlockCacheError> {
- // 存放缺块信息的向量
- let mut fail_ans = vec![];
- // 存放命中块地址的向量
- let mut success_ans = vec![];
- // 获取mapper
- let mapper = unsafe { mapper()? };
- for (index, i) in block_iter.enumerate() {
- // 在mapper中寻找块的lba_id,判断是否命中
- match mapper.find(i.lba_id()) {
- Some(x) => {
- success_ans.push(x);
- continue;
- }
- // 缺块就放入fail_ans
- None => fail_ans.push(FailData::new(i.lba_id(), index)),
- // 缺块不break的原因是,我们需要把所有缺块都找出来,这样才能补上缺块
- }
- }
- // 只要有缺块就认为cache失败,因为需要补块就需要进行io操作
- if !fail_ans.is_empty() {
- return Err(BlockCacheError::BlockFaultError(fail_ans));
- } else {
- return Ok(success_ans);
- }
- }
- /// # 函数的功能
- /// 在cache中读取一个块的数据并放置于缓存的指定位置
- ///
- /// ## 参数:
- /// - 'cache_block_addr' :表示需要读取的cache块的地址
- /// - 'position' :表示该块的数据需要放置在buf的哪个位置,比如position为2,那么读出的数据将放置在buf\[1024..1536\](这里假设块大小是512)
- /// - 'buf' :块数据的缓存
- ///
- /// ## 返回值:
- /// - Ok(usize) :表示读取了多少个字节
- /// - Err(BlockCacheError) :如果输入的cache_block_addr超过了cache的容量,那么将返回Err(由于目前的cache不支持动态变化上限,所以可能出现这种错误;而实际上,由于Cache的地址是由frame_selector给出的,所以正确实现的frame_selector理论上不会出现这种错误)
- fn read_one_block(
- cache_block_addr: CacheBlockAddr,
- position: usize,
- buf: &mut [u8],
- ) -> Result<usize, BlockCacheError> {
- let space = unsafe { space()? };
- space.read(cache_block_addr, position, buf)
- }
- /// # 函数的功能
- /// 根据缺块的数据和io获得的数据,向cache中补充块数据
- ///
- /// ## 参数:
- /// - 'f_data_vec' :这里输入的一般是从read函数中返回的缺块数据
- /// - 'data' :经过一次io后获得的数据
- ///
- /// ## 返回值:
- /// Ok(usize) :表示补上缺页的个数
- /// Err(BlockCacheError) :一般来说不会产生错误,这里产生错误的原因只有插入时还没有初始化(一般也很难发生)
- pub fn insert(f_data_vec: Vec<FailData>, data: &[u8]) -> Result<usize, BlockCacheError> {
- let count = f_data_vec.len();
- for i in f_data_vec {
- let index = i.index();
- Self::insert_one_block(
- i.lba_id(),
- data[index * BLOCK_SIZE..(index + 1) * BLOCK_SIZE].to_vec(),
- )?;
- }
- Ok(count)
- }
- /// # 函数的功能
- /// 将一个块数据插入到cache中
- ///
- /// ## 参数:
- /// - 'lba_id' :表明该块对应的lba_id,用于建立映射
- /// - 'data' :传入的数据
- ///
- /// ## 返回值:
- /// Ok(()):表示插入成功
- /// Err(BlockCacheError) :一般来说不会产生错误,这里产生错误的原因只有插入时还没有初始化(一般也很难发生)
- fn insert_one_block(lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError> {
- let space = unsafe { space()? };
- space.insert(lba_id, data)
- }
- /// # 函数的功能
- /// 立即回写,这里仅仅作为取消映射的方法,并没有真正写入到cache的功能
- ///
- /// ## 参数:
- /// - 'lba_id_start' :需要读取的连续块的起始块
- /// - 'count' :需要读取块的个数
- /// - '_data' :目前没有写入功能,该参数暂时无用
- ///
- /// ## 返回值:
- /// Ok(usize) :表示写入了多少个块
- /// Err(BlockCacheError) :这里产生错误的原因只有插入时还没有初始化
- pub fn immediate_write(
- lba_id_start: BlockId,
- count: usize,
- _data: &[u8],
- ) -> Result<usize, BlockCacheError> {
- let mapper = unsafe { mapper()? };
- let block_iter = BlockIter::new(lba_id_start, count, BLOCK_SIZE);
- for i in block_iter {
- mapper.remove(i.lba_id());
- }
- Ok(count)
- }
- }
- struct LockedCacheSpace(RwLock<CacheSpace>);
- impl LockedCacheSpace {
- pub fn new(space: CacheSpace) -> Self {
- LockedCacheSpace(RwLock::new(space))
- }
- pub fn read(
- &self,
- addr: CacheBlockAddr,
- position: usize,
- buf: &mut [u8],
- ) -> Result<usize, BlockCacheError> {
- self.0.read().read(addr, position, buf)
- }
- pub fn _write(&mut self, _addr: CacheBlockAddr, _data: CacheBlock) -> Option<()> {
- todo!()
- }
- pub fn insert(&mut self, lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError> {
- unsafe { self.0.get_mut().insert(lba_id, data) }
- }
- }
- /// # 结构功能
- /// 管理Cache空间的结构体
- struct CacheSpace {
- /// 用于存放CacheBlock,是Cache数据的实际存储空间的向量
- root: Vec<CacheBlock>,
- /// 在块换出换入时,用于选择替换块的结构体
- frame_selector: Box<dyn FrameSelector>,
- }
- impl CacheSpace {
- pub fn new() -> Self {
- Self {
- root: Vec::new(),
- // 如果要修改替换算法,可以设计一个结构体实现FrameSelector trait,再在这里替换掉SimpleFrameSelector
- frame_selector: Box::new(SimpleFrameSelector::new()),
- }
- }
- /// # 函数的功能
- /// 将一个块的数据写入到buf的指定位置
- ///
- /// ## 参数:
- /// - 'addr' :请求块在Cache中的地址
- /// - 'position' :表示需要将Cache放入buf中的位置,例如:若position为1,则块的数据放入buf\[512..1024\]
- /// - 'buf' :存放数据的buf
- ///
- /// ## 返回值:
- /// Some(usize):表示读取的字节数(这里默认固定为BLOCK_SIZE)
- /// Err(BlockCacheError):如果你输入地址大于cache的最大上限,那么就返回InsufficientCacheSpace
- pub fn read(
- &self,
- addr: CacheBlockAddr,
- position: usize,
- buf: &mut [u8],
- ) -> Result<usize, BlockCacheError> {
- if addr > self.frame_selector.size() {
- return Err(BlockCacheError::InsufficientCacheSpace);
- } else {
- // CacheBlockAddr就是用于给root寻址的
- return self.root[addr]
- .data(&mut buf[position * BLOCK_SIZE..(position + 1) * BLOCK_SIZE]);
- }
- }
- /// # 函数的功能
- /// 向cache空间中写入的函数,目前尚未实现
- pub fn _write(&mut self, _addr: CacheBlockAddr, _data: CacheBlock) -> Option<()> {
- todo!()
- }
- /// # 函数的功能
- /// 向cache中插入一个块并建立lba_id到块之间的映射
- ///
- /// ## 参数:
- /// - 'lba_id' :表明你插入的块的lba_id,用于建立映射
- /// - 'data' :要插入块的数据
- ///
- /// ## 返回值:
- /// Ok(())
- pub fn insert(&mut self, lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError> {
- // CacheBlock是cached block的基本单位,这里使用data生成一个CacheBlock用于向Cache空间中插入块
- let data_block = CacheBlock::from_data(lba_id, data);
- let mapper = unsafe { mapper()? };
- // 这里我设计了cache的一个threshold,如果不超过阈值就可以append,否则只能替换
- if self.frame_selector.can_append() {
- // 这是append的操作逻辑:
- // 从frame_selector获得一个CacheBlockAddr
- let index = self.frame_selector.index_append();
- // 直接将块push进去就可以,因为现在是append操作
- self.root.push(data_block);
- assert!(index == self.root.len() - 1);
- // 建立mapper的映射
- mapper.insert(lba_id, index);
- Ok(())
- } else {
- // 这是replace的操作逻辑
- // 从frame_selector获得一个CacheBlockAddr,这次是它替换出来的
- let index = self.frame_selector.index_replace();
- // 获取被替换的块的lba_id,待会用于取消映射
- let removed_id = self.root[index].lba_id();
- // 直接替换原本的块,由于被替换的块没有引用了,所以会被drop
- self.root[index] = data_block;
- // 建立映射插入块的映射
- mapper.insert(lba_id, index);
- // 取消被替换块的映射
- mapper.remove(removed_id);
- Ok(())
- }
- }
- }
- struct LockedCacheMapper {
- lock: RwLock<CacheMapper>,
- }
- impl LockedCacheMapper {
- pub fn new(inner: CacheMapper) -> Self {
- Self {
- lock: RwLock::new(inner),
- }
- }
- pub fn insert(&mut self, lba_id: BlockId, caddr: CacheBlockAddr) -> Option<()> {
- unsafe { self.lock.get_mut().insert(lba_id, caddr) }
- }
- pub fn find(&self, lba_id: BlockId) -> Option<CacheBlockAddr> {
- self.lock.read().find(lba_id)
- }
- pub fn remove(&mut self, lba_id: BlockId) {
- unsafe { self.lock.get_mut().remove(lba_id) }
- }
- }
- /// # 结构功能
- /// 该结构体用于建立lba_id到cached块的映射
- struct CacheMapper {
- // 执行键值对操作的map
- map: HashMap<BlockId, CacheBlockAddr>,
- }
- impl CacheMapper {
- pub fn new() -> Self {
- Self {
- map: HashMap::new(),
- }
- }
- /// # 函数的功能
- /// 插入操作
- pub fn insert(&mut self, lba_id: BlockId, caddr: CacheBlockAddr) -> Option<()> {
- self.map.insert(lba_id, caddr)?;
- Some(())
- }
- /// # 函数的功能
- /// 查找操作
- #[inline]
- pub fn find(&self, lba_id: BlockId) -> Option<CacheBlockAddr> {
- Some(*self.map.get(&lba_id)?)
- }
- /// # 函数的功能
- /// 去除操作
- pub fn remove(&mut self, lba_id: BlockId) {
- self.map.remove(&lba_id);
- }
- }
- /// # 结构功能
- /// 该trait用于实现块的换入换出算法,需要设计替换算法只需要实现该trait即可
- trait FrameSelector {
- /// # 函数的功能
- /// 给出append操作的index(理论上,如果cache没满,就不需要换出块,就可以使用append操作)
- fn index_append(&mut self) -> CacheBlockAddr;
- /// # 函数的功能
- /// 给出replace操作后的index
- fn index_replace(&mut self) -> CacheBlockAddr;
- /// # 函数的功能
- /// 判断是否可以append
- fn can_append(&self) -> bool;
- /// # 函数的功能
- /// 获取size
- fn size(&self) -> usize;
- }
- /// # 结构功能
- /// 该结构体用于管理块的换入换出过程中,CacheBlockAddr的选择,替换算法在这里实现
- struct SimpleFrameSelector {
- // 表示BlockCache的阈值,即最大可以存放多少块,这里目前还不支持动态变化
- threshold: usize,
- // 表示使用过的块帧的数量
- size: usize,
- // 这里使用从头至尾的替换算法,其替换策略为0,1,2,...,threshold,0,1...以此类推(该算法比FIFO还要简陋,后面可以再实现别的:)
- current: usize,
- }
- impl SimpleFrameSelector {
- pub fn new() -> Self {
- Self {
- threshold: CACHE_THRESHOLD * (1 << (20 - BLOCK_SIZE_LOG)),
- size: 0,
- current: 0,
- }
- }
- }
- impl FrameSelector for SimpleFrameSelector {
- fn index_append(&mut self) -> CacheBlockAddr {
- let ans = self.current;
- self.size += 1;
- self.current += 1;
- self.current %= self.threshold;
- return ans;
- }
- fn index_replace(&mut self) -> CacheBlockAddr {
- let ans = self.current;
- self.current += 1;
- self.current %= self.threshold;
- return ans;
- }
- fn can_append(&self) -> bool {
- self.size < self.threshold
- }
- fn size(&self) -> usize {
- self.size
- }
- }
|