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)]
mapper() -> Result<&'static mut LockedCacheMapper, BlockCacheError>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)]
space() -> Result<&'static mut LockedCacheSpace, BlockCacheError>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需要的结构体
init()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中得到处理
read( lba_id_start: BlockId, count: usize, buf: &mut [u8], ) -> Result<usize, BlockCacheError>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::____) :不缺块的情况往往是初始化或者其他问题
check_able_to_read(block_iter: BlockIter) -> Result<Vec<CacheBlockAddr>, 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理论上不会出现这种错误）
read_one_block( cache_block_addr: CacheBlockAddr, position: usize, buf: &mut [u8], ) -> Result<usize, BlockCacheError>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) :一般来说不会产生错误，这里产生错误的原因只有插入时还没有初始化（一般也很难发生）
insert(f_data_vec: Vec<FailData>, data: &[u8]) -> Result<usize, 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) :一般来说不会产生错误，这里产生错误的原因只有插入时还没有初始化（一般也很难发生）
insert_one_block(lba_id: BlockId, data: Vec<u8>) -> Result<(), 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) :这里产生错误的原因只有插入时还没有初始化
immediate_write( lba_id_start: BlockId, count: usize, _data: &[u8], ) -> Result<usize, 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 {
new(space: CacheSpace) -> Self198 pub fn new(space: CacheSpace) -> Self {
199 LockedCacheSpace(RwLock::new(space))
200 }
201
read( &self, addr: CacheBlockAddr, position: usize, buf: &mut [u8], ) -> Result<usize, BlockCacheError>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
_write(&mut self, _addr: CacheBlockAddr, _data: CacheBlock) -> Option<()>211 pub fn _write(&mut self, _addr: CacheBlockAddr, _data: CacheBlock) -> Option<()> {
212 todo!()
213 }
214
insert(&mut self, lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError>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 {
new() -> Self230 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
read( &self, addr: CacheBlockAddr, position: usize, buf: &mut [u8], ) -> Result<usize, BlockCacheError>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空间中写入的函数，目前尚未实现
_write(&mut self, _addr: CacheBlockAddr, _data: CacheBlock) -> Option<()>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(())
insert(&mut self, lba_id: BlockId, data: Vec<u8>) -> Result<(), BlockCacheError>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 {
new(inner: CacheMapper) -> Self313 pub fn new(inner: CacheMapper) -> Self {
314 Self {
315 lock: RwLock::new(inner),
316 }
317 }
318
insert(&mut self, lba_id: BlockId, caddr: CacheBlockAddr) -> Option<()>319 pub fn insert(&mut self, lba_id: BlockId, caddr: CacheBlockAddr) -> Option<()> {
320 unsafe { self.lock.get_mut().insert(lba_id, caddr) }
321 }
322
find(&self, lba_id: BlockId) -> Option<CacheBlockAddr>323 pub fn find(&self, lba_id: BlockId) -> Option<CacheBlockAddr> {
324 self.lock.read().find(lba_id)
325 }
326
remove(&mut self, lba_id: BlockId)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 {
new() -> Self340 pub fn new() -> Self {
341 Self {
342 map: HashMap::new(),
343 }
344 }
345 /// # 函数的功能
346 /// 插入操作
insert(&mut self, lba_id: BlockId, caddr: CacheBlockAddr) -> Option<()>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]
find(&self, lba_id: BlockId) -> Option<CacheBlockAddr>354 pub fn find(&self, lba_id: BlockId) -> Option<CacheBlockAddr> {
355 Some(*self.map.get(&lba_id)?)
356 }
357 /// # 函数的功能
358 /// 去除操作
remove(&mut self, lba_id: BlockId)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操作）
index_append(&mut self) -> CacheBlockAddr369 fn index_append(&mut self) -> CacheBlockAddr;
370 /// # 函数的功能
371 /// 给出replace操作后的index
index_replace(&mut self) -> CacheBlockAddr372 fn index_replace(&mut self) -> CacheBlockAddr;
373 /// # 函数的功能
374 /// 判断是否可以append
can_append(&self) -> bool375 fn can_append(&self) -> bool;
376 /// # 函数的功能
377 /// 获取size
size(&self) -> usize378 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 {
new() -> Self393 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 {
index_append(&mut self) -> CacheBlockAddr403 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
index_replace(&mut self) -> CacheBlockAddr411 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
can_append(&self) -> bool418 fn can_append(&self) -> bool {
419 self.size < self.threshold
420 }
421
size(&self) -> usize422 fn size(&self) -> usize {
423 self.size
424 }
425 }
426