-
Notifications
You must be signed in to change notification settings - Fork 1
/
arc.cpp
105 lines (93 loc) · 2.47 KB
/
arc.cpp
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
#include "arc.h"
#define min(a,b) ((a < b)? a : b)
#define max(a,b) ((a > b)? a : b)
int ARCCache::get(int target) {
if (_c <= 0) {
return -1;
}
++_get_count;
auto it = _table.find(target);
if (it != _table.end()) {
// case1
if (it->second->lru_type == T1 || it->second->lru_type == T2) {
move_to_lru(it->second, T2);
assert_c();
++_hit_count;
return it->second->addr;
}
// case2
if (it->second->lru_type == B1) {
auto t = _b1.size() >= _b2.size() ? 1: _b2.size() / (double)_b1.size();
_p = min(_p + t, _c);
replace(false);
move_to_lru(it->second, T2);
it->second->addr = target;
assert_c();
return it->second->addr;
}
// case3
if (it->second->lru_type == B2) {
auto t = _b2.size() >= _b1.size() ? 1: _b1.size() / (double)_b2.size();
_p = max(_p - t, 0);
replace(true);
move_to_lru(it->second, T2);
it->second->addr = target;
assert_c();
return it->second->addr;
}
}
// case4
assert(_t1.size() + _b1.size() <= _c);
if (_t1.size() + _b1.size() == _c) {
// case4.1
if (_t1.size() < _c) {
_table.erase(_b1.back()->target);
_b1.pop_back();
replace(false);
} else {
_table.erase(_t1.back()->target);
_t1.pop_back();
}
} else {
// case 4.2
assert(_t1.size() + _b1.size() < _c);
auto size = _t1.size() + _t2.size() + _b1.size() + _b2.size();
if (size >= _c) {
if (size == _c * 2) {
_table.erase(_b2.back()->target);
_b2.pop_back();
}
replace(false);
}
}
std::shared_ptr<ArcEntry> entry = std::make_shared<ArcEntry>();
entry->target = target;
entry->addr = target;
entry->lru_type = T1;
_t1.push_front(entry);
_t1.front()->iter = _t1.begin();
_table[target] = entry;
assert_c();
return _t1.front()->addr;
}
void ARCCache::replace(bool in_b2) {
if (_t1.size() != 0 &&
((_t1.size() > _p) || (in_b2 && _t1.size() == _p))) {
_t1.back()->addr = -1;
assert(_t1.back()->lru_type == T1);
move_to_lru(_t1.back(), B1);
} else {
_t2.back()->addr = -1;
assert(_t2.back()->lru_type == T2);
move_to_lru(_t2.back(), B2);
}
}
std::string ARCCache::statics() {
std::stringstream s;
s << "trace:" << _file_name << " arc_cache:"
<< " cache_size:" << _c
<< " request:" << _get_count
<< " hit:" << _hit_count
<< " hit_rate:" << 1.0 * _hit_count / _get_count << std::endl;
return s.str();
}