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