1 use alloc::{boxed::Box, vec::Vec}; 2 use hashbrown::HashMap; 3 4 use crate::{driver::base::block::block_device::BlockId, libs::rwlock::RwLock}; 5 6 use super::{ 7 cache_block::{CacheBlock, CacheBlockAddr}, 8 cache_iter::{BlockIter, FailData}, 9 BlockCacheError, BLOCK_SIZE, BLOCK_SIZE_LOG, CACHE_THRESHOLD, 10 }; 11 12 static mut CSPACE: Option<LockedCacheSpace> = None; 13 static mut CMAPPER: Option<LockedCacheMapper> = None; 14 /// # 结构功能 15 /// 该结构体向外提供BlockCache服务 16 pub struct BlockCache; 17 18 unsafe fn mapper() -> Result<&'static mut LockedCacheMapper, BlockCacheError> { 19 unsafe { 20 match &mut CMAPPER { 21 Some(x) => return Ok(x), 22 None => return Err(BlockCacheError::StaticParameterError), 23 } 24 }; 25 } 26 27 unsafe fn space() -> Result<&'static mut LockedCacheSpace, BlockCacheError> { 28 unsafe { 29 match &mut CSPACE { 30 Some(x) => return Ok(x), 31 None => return Err(BlockCacheError::StaticParameterError), 32 } 33 }; 34 } 35 36 impl BlockCache { 37 /// # 函数的功能 38 /// 初始化BlockCache需要的结构体 39 pub fn init() { 40 unsafe { 41 CSPACE = Some(LockedCacheSpace::new(CacheSpace::new())); 42 CMAPPER = Some(LockedCacheMapper::new(CacheMapper::new())); 43 } 44 kdebug!("BlockCache Initialized!"); 45 } 46 /// # 函数的功能 47 /// 使用blockcache进行对块设备进行连续块的读操作 48 /// 49 /// ## 参数： 50 /// - 'lba_id_start' :连续块的起始块的lba_id 51 /// - 'count' :从连续块算起需要读多少块 52 /// - 'buf' :读取出来的数据存放在buf中 53 /// 54 /// ## 返回值： 55 /// - Ok(usize) :表示读取块的个数 56 /// - Err(BlockCacheError::BlockFaultError) :缺块的情况下，返回读取失败的块的数据，利用该返回值可以帮助blockcache插入读取失败的块值（见insert函数） 57 /// - Err(BlockCacheError::____) :不缺块的情况往往是初始化或者其他问题，这种异常会在block_device中得到处理 58 pub fn read( 59 lba_id_start: BlockId, 60 count: usize, 61 buf: &mut [u8], 62 ) -> Result<usize, BlockCacheError> { 63 // 生成一个块迭代器（BlockIter），它可以迭代地给出所有需要块的数据，其中就包括lba_id 64 let block_iter = BlockIter::new(lba_id_start, count, BLOCK_SIZE); 65 // 调用检查函数，检查有无缺块，如果没有就可以获得所有块的Cache地址。如果失败了就直接返回FailData向量 66 let cache_block_addr = Self::check_able_to_read(block_iter)?; 67 // 块地址vec的长度应当等于块迭代器的大小 68 assert!(cache_block_addr.len() == block_iter.count()); 69 // 迭代地读取cache并写入到buf中 70 for (index, _) in block_iter.enumerate() { 71 Self::read_one_block(cache_block_addr[index], index, buf)?; 72 } 73 return Ok(count); 74 } 75 76 /// # 函数的功能 77 /// 检查cache中是否有缺块的函数 78 /// 79 /// ## 参数： 80 /// - 'block_iter' :需要检查的块迭代器（因为块迭代器包含了需要读块的信息，所以传入块迭代器） 81 /// 82 /// ## 返回值： 83 /// - Ok(Vec<CacheBlockAddr>) :如果成功了，那么函数会返回每个块的Cache地址，利用Cache地址就可以访问Cache了 84 /// - Err(BlockCacheError::BlockFaultError) :如果发现了缺块，那么我们会返回所有缺块的信息（即FailData） 85 /// - Err(BlockCacheError::____) :不缺块的情况往往是初始化或者其他问题 86 fn check_able_to_read(block_iter: BlockIter) -> Result<Vec<CacheBlockAddr>, BlockCacheError> { 87 // 存放缺块信息的向量 88 let mut fail_ans = vec![]; 89 // 存放命中块地址的向量 90 let mut success_ans = vec![]; 91 // 获取mapper 92 let mapper = unsafe { mapper()? }; 93 for (index, i) in block_iter.enumerate() { 94 // 在mapper中寻找块的lba_id，判断是否命中 95 match mapper.find(i.lba_id()) { 96 Some(x) => { 97 success_ans.push(x); 98 continue; 99 } 100 // 缺块就放入fail_ans 101 None => fail_ans.push(FailData::new(i.lba_id(), index)), 102 // 缺块不break的原因是，我们需要把所有缺块都找出来，这样才能补上缺块 103 } 104 } 105 // 只要有缺块就认为cache失败，因为需要补块就需要进行io操作 106 if !fail_ans.is_empty() { 107 return Err(BlockCacheError::BlockFaultError(fail_ans)); 108 } else { 109 return Ok(success_ans); 110 } 111 } 112 /// # 函数的功能 113 /// 在cache中读取一个块的数据并放置于缓存的指定位置 114 /// 115 /// ## 参数： 116 /// - 'cache_block_addr' :表示需要读取的cache块的地址 117 /// - 'position' :表示该块的数据需要放置在buf的哪个位置，比如position为2，那么读出的数据将放置在buf\[1024..1536\](这里假设块大小是512) 118 /// - 'buf' :块数据的缓存 119 /// 120 /// ## 返回值： 121 /// - Ok(usize) :表示读取了多少个字节 122 /// - Err(BlockCacheError) :如果输入的cache_block_addr超过了cache的容量，那么将返回Err（由于目前的cache不支持动态变化上限，所以可能出现这种错误;而实际上，由于Cache的地址是由frame_selector给出的,所以正确实现的frame_selector理论上不会出现这种错误） 123 fn read_one_block( 124 cache_block_addr: CacheBlockAddr, 125 position: usize, 126 buf: &mut [u8], 127 ) -> Result<usize, BlockCacheError> { 128 let space = unsafe { space()? }; 129 space.read(cache_block_addr, position, buf) 130 } 131 /// # 函数的功能 132 /// 根据缺块的数据和io获得的数据，向cache中补充块数据 133 /// 134 /// ## 参数： 135 /// - 'f_data_vec' :这里输入的一般是从read函数中返回的缺块数据 136 /// - 'data' :经过一次io后获得的数据 137 /// 138 /// ## 返回值： 139 /// Ok(usize) :表示补上缺页的个数 140 /// Err(BlockCacheError) :一般来说不会产生错误，这里产生错误的原因只有插入时还没有初始化（一般也很难发生） 141 pub fn insert(f_data_vec: Vec<FailData>, data: &[u8]) -> Result<usize, BlockCacheError> { 142 let count = f_data_vec.len(); 143 for i in f_data_vec { 144 let index = i.index(); 145 Self::insert_one_block( 146 i.lba_id(), 147 data[index * BLOCK_SIZE..(index + 1) * BLOCK_SIZE].to_vec(), 148 )?; 149 } 150 Ok(count) 151 } 152 153 /// # 函数的功能 154 /// 将一个块数据插入到cache中 155 /// 156 /// ## 参数： 157 /// - 'lba_id' :表明该块对应的lba_id，用于建立映射 158 /// - 'data' :传入的数据 159 /// 160 /// ## 返回值： 161 /// Ok(()):表示插入成功 162 /// Err(BlockCacheError) :一般来说不会产生错误，这里产生错误的原因只有插入时还没有初始化（一般也很难发生） 163 fn insert_one_block(lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError> { 164 let space = unsafe { space()? }; 165 space.insert(lba_id, data) 166 } 167 /// # 函数的功能 168 /// 立即回写，这里仅仅作为取消映射的方法，并没有真正写入到cache的功能 169 /// 170 /// ## 参数： 171 /// - 'lba_id_start' :需要读取的连续块的起始块 172 /// - 'count' :需要读取块的个数 173 /// - '_data' :目前没有写入功能，该参数暂时无用 174 /// 175 /// ## 返回值： 176 /// Ok(usize) :表示写入了多少个块 177 /// Err(BlockCacheError) :这里产生错误的原因只有插入时还没有初始化 178 pub fn immediate_write( 179 lba_id_start: BlockId, 180 count: usize, 181 _data: &[u8], 182 ) -> Result<usize, BlockCacheError> { 183 let mapper = unsafe { mapper()? }; 184 let block_iter = BlockIter::new(lba_id_start, count, BLOCK_SIZE); 185 for i in block_iter { 186 mapper.remove(i.lba_id()); 187 } 188 Ok(count) 189 } 190 } 191 192 struct LockedCacheSpace(RwLock<CacheSpace>); 193 194 impl LockedCacheSpace { 195 pub fn new(space: CacheSpace) -> Self { 196 LockedCacheSpace(RwLock::new(space)) 197 } 198 199 pub fn read( 200 &self, 201 addr: CacheBlockAddr, 202 position: usize, 203 buf: &mut [u8], 204 ) -> Result<usize, BlockCacheError> { 205 self.0.read().read(addr, position, buf) 206 } 207 208 pub fn _write(&mut self, _addr: CacheBlockAddr, _data: CacheBlock) -> Option<()> { 209 todo!() 210 } 211 212 pub fn insert(&mut self, lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError> { 213 unsafe { self.0.get_mut().insert(lba_id, data) } 214 } 215 } 216 217 /// # 结构功能 218 /// 管理Cache空间的结构体 219 struct CacheSpace { 220 /// 用于存放CacheBlock，是Cache数据的实际存储空间的向量 221 root: Vec<CacheBlock>, 222 /// 在块换出换入时，用于选择替换块的结构体 223 frame_selector: Box<dyn FrameSelector>, 224 } 225 226 impl CacheSpace { 227 pub fn new() -> Self { 228 Self { 229 root: Vec::new(), 230 // 如果要修改替换算法，可以设计一个结构体实现FrameSelector trait，再在这里替换掉SimpleFrameSelector 231 frame_selector: Box::new(SimpleFrameSelector::new()), 232 } 233 } 234 /// # 函数的功能 235 /// 将一个块的数据写入到buf的指定位置 236 /// 237 /// ## 参数： 238 /// - 'addr' :请求块在Cache中的地址 239 /// - 'position' :表示需要将Cache放入buf中的位置，例如:若position为1，则块的数据放入buf\[512..1024\] 240 /// - 'buf' :存放数据的buf 241 /// 242 /// ## 返回值： 243 /// Some(usize):表示读取的字节数（这里默认固定为BLOCK_SIZE） 244 /// Err(BlockCacheError):如果你输入地址大于cache的最大上限，那么就返回InsufficientCacheSpace 245 pub fn read( 246 &self, 247 addr: CacheBlockAddr, 248 position: usize, 249 buf: &mut [u8], 250 ) -> Result<usize, BlockCacheError> { 251 if addr > self.frame_selector.size() { 252 return Err(BlockCacheError::InsufficientCacheSpace); 253 } else { 254 // CacheBlockAddr就是用于给root寻址的 255 return self.root[addr] 256 .data(&mut buf[position * BLOCK_SIZE..(position + 1) * BLOCK_SIZE]); 257 } 258 } 259 /// # 函数的功能 260 /// 向cache空间中写入的函数，目前尚未实现 261 pub fn _write(&mut self, _addr: CacheBlockAddr, _data: CacheBlock) -> Option<()> { 262 todo!() 263 } 264 /// # 函数的功能 265 /// 向cache中插入一个块并建立lba_id到块之间的映射 266 /// 267 /// ## 参数： 268 /// - 'lba_id' :表明你插入的块的lba_id，用于建立映射 269 /// - 'data' :要插入块的数据 270 /// 271 /// ## 返回值： 272 /// Ok(()) 273 pub fn insert(&mut self, lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError> { 274 // CacheBlock是cached block的基本单位，这里使用data生成一个CacheBlock用于向Cache空间中插入块 275 let data_block = CacheBlock::from_data(lba_id, data); 276 let mapper = unsafe { mapper()? }; 277 // 这里我设计了cache的一个threshold，如果不超过阈值就可以append，否则只能替换 278 if self.frame_selector.can_append() { 279 // 这是append的操作逻辑： 280 // 从frame_selector获得一个CacheBlockAddr 281 let index = self.frame_selector.index_append(); 282 // 直接将块push进去就可以，因为现在是append操作 283 self.root.push(data_block); 284 assert!(index == self.root.len() - 1); 285 // 建立mapper的映射 286 mapper.insert(lba_id, index); 287 Ok(()) 288 } else { 289 // 这是replace的操作逻辑 290 // 从frame_selector获得一个CacheBlockAddr，这次是它替换出来的 291 let index = self.frame_selector.index_replace(); 292 // 获取被替换的块的lba_id，待会用于取消映射 293 let removed_id = self.root[index].lba_id(); 294 // 直接替换原本的块，由于被替换的块没有引用了，所以会被drop 295 self.root[index] = data_block; 296 // 建立映射插入块的映射 297 mapper.insert(lba_id, index); 298 // 取消被替换块的映射 299 mapper.remove(removed_id); 300 Ok(()) 301 } 302 } 303 } 304 305 struct LockedCacheMapper { 306 lock: RwLock<CacheMapper>, 307 } 308 309 impl LockedCacheMapper { 310 pub fn new(inner: CacheMapper) -> Self { 311 Self { 312 lock: RwLock::new(inner), 313 } 314 } 315 316 pub fn insert(&mut self, lba_id: BlockId, caddr: CacheBlockAddr) -> Option<()> { 317 unsafe { self.lock.get_mut().insert(lba_id, caddr) } 318 } 319 320 pub fn find(&self, lba_id: BlockId) -> Option<CacheBlockAddr> { 321 self.lock.read().find(lba_id) 322 } 323 324 pub fn remove(&mut self, lba_id: BlockId) { 325 unsafe { self.lock.get_mut().remove(lba_id) } 326 } 327 } 328 329 /// # 结构功能 330 /// 该结构体用于建立lba_id到cached块的映射 331 struct CacheMapper { 332 // 执行键值对操作的map 333 map: HashMap<BlockId, CacheBlockAddr>, 334 } 335 336 impl CacheMapper { 337 pub fn new() -> Self { 338 Self { 339 map: HashMap::new(), 340 } 341 } 342 /// # 函数的功能 343 /// 插入操作 344 pub fn insert(&mut self, lba_id: BlockId, caddr: CacheBlockAddr) -> Option<()> { 345 self.map.insert(lba_id, caddr)?; 346 Some(()) 347 } 348 /// # 函数的功能 349 /// 查找操作 350 #[inline] 351 pub fn find(&self, lba_id: BlockId) -> Option<CacheBlockAddr> { 352 Some(*self.map.get(&lba_id)?) 353 } 354 /// # 函数的功能 355 /// 去除操作 356 pub fn remove(&mut self, lba_id: BlockId) { 357 self.map.remove(&lba_id); 358 } 359 } 360 361 /// # 结构功能 362 /// 该trait用于实现块的换入换出算法，需要设计替换算法只需要实现该trait即可 363 trait FrameSelector { 364 /// # 函数的功能 365 /// 给出append操作的index（理论上，如果cache没满，就不需要换出块，就可以使用append操作） 366 fn index_append(&mut self) -> CacheBlockAddr; 367 /// # 函数的功能 368 /// 给出replace操作后的index 369 fn index_replace(&mut self) -> CacheBlockAddr; 370 /// # 函数的功能 371 /// 判断是否可以append 372 fn can_append(&self) -> bool; 373 /// # 函数的功能 374 /// 获取size 375 fn size(&self) -> usize; 376 } 377 378 /// # 结构功能 379 /// 该结构体用于管理块的换入换出过程中，CacheBlockAddr的选择，替换算法在这里实现 380 struct SimpleFrameSelector { 381 // 表示BlockCache的阈值，即最大可以存放多少块，这里目前还不支持动态变化 382 threshold: usize, 383 // 表示使用过的块帧的数量 384 size: usize, 385 // 这里使用从头至尾的替换算法，其替换策略为0，1，2，...，threshold，0，1...以此类推（该算法比FIFO还要简陋，后面可以再实现别的：） 386 current: usize, 387 } 388 389 impl SimpleFrameSelector { 390 pub fn new() -> Self { 391 Self { 392 threshold: CACHE_THRESHOLD * (1 << (20 - BLOCK_SIZE_LOG)), 393 size: 0, 394 current: 0, 395 } 396 } 397 } 398 399 impl FrameSelector for SimpleFrameSelector { 400 fn index_append(&mut self) -> CacheBlockAddr { 401 let ans = self.current; 402 self.size += 1; 403 self.current += 1; 404 self.current %= self.threshold; 405 return ans; 406 } 407 408 fn index_replace(&mut self) -> CacheBlockAddr { 409 let ans = self.current; 410 self.current += 1; 411 self.current %= self.threshold; 412 return ans; 413 } 414 415 fn can_append(&self) -> bool { 416 self.size < self.threshold 417 } 418 419 fn size(&self) -> usize { 420 self.size 421 } 422 } 423