1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
use std::collections::{HashMap, VecDeque};
use super::dvaddr::DVAddr;
use super::zio;
use super::djb2::Djb2;
use std::hash::BuildHasherDefault;
/// MRU - Most Recently Used cache
struct Mru {
map: HashMap<DVAddr, Vec<u8>, BuildHasherDefault<Djb2>>,
/// Oldest DVAddrs are at the end
queue: VecDeque<DVAddr>,
/// Max mru cache size in blocks
size: usize,
/// Number of used blocks in mru cache
used: usize,
}
impl Mru {
pub fn new() -> Self {
Mru {
map: HashMap::with_hasher(Default::default()),
queue: VecDeque::new(),
size: 1000,
used: 0,
}
}
pub fn cache_block(&mut self, dva: &DVAddr, block: Vec<u8>) -> Result<Vec<u8>, &str> {
// If necessary, make room for the block in the cache
while self.used + (dva.asize() as usize) > self.size {
let last_dva = match self.queue.pop_back() {
Some(dva) => dva,
None => return Err("No more ARC MRU items to free"),
};
self.map.remove(&last_dva);
self.used -= last_dva.asize() as usize;
}
// Add the block to the cache
self.used += dva.asize() as usize;
self.map.insert(*dva, block);
self.queue.push_front(*dva);
Ok(self.map.get(dva).unwrap().clone())
}
}
/// MFU - Most Frequently Used cache
struct Mfu {
// TODO: Keep track of use counts. So mfu_map becomes (use_count: u64, Vec<u8>). Reset the use
// count every once in a while. For instance, every 1000 reads. This will probably end up being
// a knob for the user.
// TODO: Keep track of minimum frequency and corresponding DVA
map: HashMap<DVAddr, (u64, Vec<u8>), BuildHasherDefault<Djb2>>,
size: usize, // Max mfu cache size in blocks
used: usize, // Number of used bytes in mfu cache
}
impl Mfu {
pub fn new() -> Self {
Mfu {
map: HashMap::with_hasher(Default::default()),
size: 1000,
used: 0,
}
}
pub fn cache_block(&mut self, dva: &DVAddr, block: Vec<u8>) -> Result<&[u8], &str> {
{
let mut lowest_freq = !0;
let mut lowest_dva = Err("No valid DVA found.");
for (&dva_key, &(freq, _)) in self.map.iter() {
if freq < lowest_freq {
lowest_freq = freq;
lowest_dva = Ok(dva_key);
}
}
self.map.remove(&try!(lowest_dva));
}
// Add the block to the cache
self.used += dva.asize() as usize;
self.map.insert(*dva, (2, block));
Ok(&self.map.get(dva).unwrap().1)
}
}
/// Our implementation of the Adaptive Replacement Cache (ARC) is set up to allocate
/// its buffer on the heap rather than in a private pool thing. This makes it much
/// simpler to implement, but defers the fragmentation problem to the heap allocator.
/// We named the type `ArCache` to avoid confusion with Rust's `Arc` reference type.
pub struct ArCache {
mru: Mru,
mfu: Mfu,
}
impl ArCache {
pub fn new() -> Self {
ArCache {
mru: Mru::new(),
mfu: Mfu::new(),
}
}
pub fn read(&mut self, reader: &mut zio::Reader, dva: &DVAddr) -> Result<Vec<u8>, &str> {
if let Some(block) = self.mru.map.remove(dva) {
self.mfu.map.insert(*dva, (0, block.clone()));
// Block is cached
return Ok(block);
}
if let Some(block) = self.mfu.map.get_mut(dva) {
// Block is cached
if block.0 > 1000 {
block.0 = 0;
} else {
block.0 += 1;
}
return Ok(block.1.clone());
}
// Block isn't cached, have to read it from disk
let block = reader.read(dva.sector() as usize, dva.asize() as usize);
// Blocks start in MRU cache
self.mru.cache_block(dva, block)
}
}