cached_block_device.rs 15 KB

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