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