cfx_storage/impls/delta_mpt/cache/algorithm/
mod.rs

1// Copyright 2019 Conflux Foundation. All rights reserved.
2// Conflux is free software and distributed under GNU General Public License.
3// See http://www.gnu.org/licenses/
4
5pub mod lru;
6pub mod recent_lfu;
7pub mod removable_heap;
8
9#[cfg(test)]
10mod tests;
11
12/// The cache algorithm should store a reference to the cached element in order
13/// to link between cache store and internal data structure of cache algorithm.
14/// Normally this should be simple type like pointer, or map key for the
15/// element.
16///
17/// User may use a 32bit data type to reduce memory usage.
18pub trait CacheIndexTrait: Copy + Send + MallocSizeOf {}
19
20pub trait CacheAlgoDataTrait: Copy + Default + Send + MallocSizeOf {}
21
22/// The cache storage interface that user should implement for cache algorithm
23/// to update reference from cached object to its internal data structure.
24///
25/// The cache algorithm should normally call the interface sequentially.
26pub trait CacheStoreUtil {
27    type CacheAlgoData: CacheAlgoDataTrait;
28    type ElementIndex: CacheIndexTrait;
29
30    fn get(&self, element_index: Self::ElementIndex) -> Self::CacheAlgoData;
31
32    fn get_most_recently_accessed(
33        &self, element_index: Self::ElementIndex,
34    ) -> Self::CacheAlgoData {
35        self.get(element_index)
36    }
37
38    fn set(
39        &mut self, element_index: Self::ElementIndex,
40        algo_data: &Self::CacheAlgoData,
41    );
42
43    /// In some cases only temporary space in cache store is available for most
44    /// recently accessed (new) element. This method offers possibility for this
45    /// special case. Cache algorithm should always call this method to set
46    /// for the most recently accessed element.
47    ///
48    /// Without an overriding implementation, calls to this method is forwarded
49    /// to the normal set method.
50    fn set_most_recently_accessed(
51        &mut self, element_index: Self::ElementIndex,
52        algo_data: &Self::CacheAlgoData,
53    ) {
54        self.set(element_index, algo_data);
55    }
56}
57
58struct CacheAlgoDataAdapter<
59    CacheStoreUtilT: CacheStoreUtil,
60    CacheIndexT: CacheIndexTrait,
61> where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
62{
63    _marker_s: PhantomData<CacheStoreUtilT>,
64    _marker_i: PhantomData<CacheIndexT>,
65}
66
67impl<
68        CacheStoreUtilT: CacheStoreUtil<ElementIndex = CacheIndexT>,
69        CacheIndexT: CacheIndexTrait,
70    > CacheAlgoDataAdapter<CacheStoreUtilT, CacheIndexT>
71where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
72{
73    fn get(
74        util: &CacheStoreUtilT, index: CacheIndexT,
75    ) -> CacheStoreUtilT::CacheAlgoData {
76        util.get(index)
77    }
78
79    /// It's impossible to abstract get_mut directly in CacheStoreUtil,
80    /// therefore we have CacheAlgoDataAdapter.
81    fn get_mut(
82        util: &mut CacheStoreUtilT, index: CacheIndexT,
83    ) -> CacheAlgoDataSetter<'_, CacheStoreUtilT, CacheIndexT> {
84        let data = Self::get(util, index).clone();
85        CacheAlgoDataSetter {
86            cache_store_util: util,
87            element_index: index,
88            algo_data: data,
89        }
90    }
91
92    #[allow(unused)]
93    fn get_mut_most_recently_accessed(
94        util: &mut CacheStoreUtilT, index: CacheIndexT,
95    ) -> CacheAlgoDataSetterMostRecentlyAccessed<'_, CacheStoreUtilT, CacheIndexT>
96    {
97        let data = util.get_most_recently_accessed(index).clone();
98        CacheAlgoDataSetterMostRecentlyAccessed {
99            cache_store_util: util,
100            element_index: index,
101            algo_data: data,
102        }
103    }
104
105    unsafe fn new_mut(
106        util: &mut CacheStoreUtilT, index: CacheIndexT,
107    ) -> CacheAlgoDataSetter<'_, CacheStoreUtilT, CacheIndexT> {
108        CacheAlgoDataSetter {
109            cache_store_util: util,
110            element_index: index,
111            algo_data: mem::uninitialized(),
112        }
113    }
114
115    unsafe fn new_mut_most_recently_accessed(
116        util: &mut CacheStoreUtilT, index: CacheIndexT,
117    ) -> CacheAlgoDataSetterMostRecentlyAccessed<'_, CacheStoreUtilT, CacheIndexT>
118    {
119        CacheAlgoDataSetterMostRecentlyAccessed {
120            cache_store_util: util,
121            element_index: index,
122            algo_data: mem::uninitialized(),
123        }
124    }
125}
126
127#[derive(Debug, PartialEq)]
128pub enum CacheAccessResult<CacheIndexT> {
129    Hit,
130    MissInsert,
131    MissReplaced {
132        evicted: Vec<CacheIndexT>,
133        evicted_keep_cache_algo_data: Vec<CacheIndexT>,
134    },
135}
136
137pub trait CacheAlgorithm: Send {
138    type CacheIndex: CacheIndexTrait;
139    type CacheAlgoData: CacheAlgoDataTrait;
140
141    /// The cache index is the identifier for content being cached. If user want
142    /// to reuse the cache storage of evicted cache element, it should be
143    /// done in the cache storage.
144    fn access<
145        CacheStoreUtilT: CacheStoreUtil<
146            ElementIndex = Self::CacheIndex,
147            CacheAlgoData = Self::CacheAlgoData,
148        >,
149    >(
150        &mut self, cache_index: Self::CacheIndex,
151        cache_store_util: &mut CacheStoreUtilT,
152    ) -> CacheAccessResult<Self::CacheIndex>;
153
154    /// When an element is removed because of external logic, update the cache
155    /// algorithm.
156    ///
157    /// Note 1: do not use cache_store_util which implements special
158    /// logic for most recently accessed cache index, because the case
159    /// doesn't apply in deletion.
160    ///
161    /// Note 2: Since the cache deletion updates cache_algo_data for the element
162    /// to delete, caller must delete the item after the call to this delete
163    /// method has finished.
164    fn delete<
165        CacheStoreUtilT: CacheStoreUtil<
166            ElementIndex = Self::CacheIndex,
167            CacheAlgoData = Self::CacheAlgoData,
168        >,
169    >(
170        &mut self, cache_index: Self::CacheIndex,
171        cache_store_util: &mut CacheStoreUtilT,
172    );
173
174    fn log_usage(&self, prefix: &str);
175}
176
177// TODO(yz): maybe replace it with a library.
178pub trait PrimitiveNum:
179    Copy
180    + Debug
181    + Display
182    + Add<Output = Self>
183    + AddAssign
184    + Sub<Output = Self>
185    + SubAssign
186    + Div<Output = Self>
187    + DivAssign
188    + Mul<Output = Self>
189    + PartialOrd
190    + PartialEq
191    + MyInto<usize>
192    + MyInto<isize>
193    + MyFrom<i32>
194    + MyFrom<usize>
195    + Send
196    + MallocSizeOf
197{
198}
199
200pub trait MyFrom<X> {
201    fn from(x: X) -> Self;
202}
203
204pub trait MyInto<X> {
205    fn into(self) -> X;
206}
207
208impl MyFrom<usize> for u32 {
209    fn from(x: usize) -> Self { x as Self }
210}
211
212impl MyFrom<i32> for u32 {
213    fn from(x: i32) -> Self { x as Self }
214}
215
216impl MyInto<isize> for u32 {
217    fn into(self) -> isize { self as isize }
218}
219
220impl MyInto<usize> for u32 {
221    fn into(self) -> usize { self as usize }
222}
223
224impl PrimitiveNum for u32 {}
225
226struct CacheAlgoDataSetter<
227    'a,
228    CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
229    CacheIndexT: CacheIndexTrait,
230> where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
231{
232    algo_data: CacheStoreUtilT::CacheAlgoData,
233    element_index: CacheIndexT,
234    cache_store_util: &'a mut CacheStoreUtilT,
235}
236
237impl<
238        'a,
239        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
240        CacheIndexT: CacheIndexTrait,
241    > Drop for CacheAlgoDataSetter<'a, CacheStoreUtilT, CacheIndexT>
242where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
243{
244    fn drop(&mut self) {
245        let (util, index, data) = (
246            &mut self.cache_store_util,
247            &self.element_index,
248            &self.algo_data,
249        );
250        util.set(*index, data);
251    }
252}
253
254impl<
255        'a,
256        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
257        CacheIndexT: CacheIndexTrait,
258    > Deref for CacheAlgoDataSetter<'a, CacheStoreUtilT, CacheIndexT>
259where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
260{
261    type Target = CacheStoreUtilT::CacheAlgoData;
262
263    fn deref(&self) -> &Self::Target { &self.algo_data }
264}
265
266impl<
267        'a,
268        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
269        CacheIndexT: CacheIndexTrait,
270    > DerefMut for CacheAlgoDataSetter<'a, CacheStoreUtilT, CacheIndexT>
271where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
272{
273    fn deref_mut(&mut self) -> &mut Self::Target { &mut self.algo_data }
274}
275
276struct CacheAlgoDataSetterMostRecentlyAccessed<
277    'a,
278    CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
279    CacheIndexT: CacheIndexTrait,
280> where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
281{
282    algo_data: CacheStoreUtilT::CacheAlgoData,
283    element_index: CacheIndexT,
284    cache_store_util: &'a mut CacheStoreUtilT,
285}
286
287impl<
288        'a,
289        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
290        CacheIndexT: CacheIndexTrait,
291    > Drop
292    for CacheAlgoDataSetterMostRecentlyAccessed<
293        'a,
294        CacheStoreUtilT,
295        CacheIndexT,
296    >
297where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
298{
299    fn drop(&mut self) {
300        let (util, index, data) = (
301            &mut self.cache_store_util,
302            &self.element_index,
303            &self.algo_data,
304        );
305        util.set_most_recently_accessed(*index, data);
306    }
307}
308
309impl<
310        'a,
311        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
312        CacheIndexT: CacheIndexTrait,
313    > Deref
314    for CacheAlgoDataSetterMostRecentlyAccessed<
315        'a,
316        CacheStoreUtilT,
317        CacheIndexT,
318    >
319where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
320{
321    type Target = CacheStoreUtilT::CacheAlgoData;
322
323    fn deref(&self) -> &Self::Target { &self.algo_data }
324}
325
326impl<
327        'a,
328        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
329        CacheIndexT: CacheIndexTrait,
330    > DerefMut
331    for CacheAlgoDataSetterMostRecentlyAccessed<
332        'a,
333        CacheStoreUtilT,
334        CacheIndexT,
335    >
336where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
337{
338    fn deref_mut(&mut self) -> &mut Self::Target { &mut self.algo_data }
339}
340
341use malloc_size_of::MallocSizeOf;
342use std::{
343    fmt::{Debug, Display},
344    marker::PhantomData,
345    mem,
346    ops::{
347        Add, AddAssign, Deref, DerefMut, Div, DivAssign, Mul, Sub, SubAssign,
348    },
349};
cfx_storage/impls/delta_mpt/cache/algorithm/mod.rs

cfx_storage/impls/delta_mpt/cache/algorithm/
mod.rs
