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    fn new_mut(
106        util: &mut CacheStoreUtilT, index: CacheIndexT,
107    ) -> CacheAlgoDataSetter<'_, CacheStoreUtilT, CacheIndexT> {
108        // `algo_data` is a write-only placeholder: every caller overwrites it
109        // via `placement_new_*` before the `Drop` flush, so its initial value
110        // never affects the result. `Default` avoids `mem::uninitialized()` UB.
111        CacheAlgoDataSetter {
112            cache_store_util: util,
113            element_index: index,
114            algo_data: Default::default(),
115        }
116    }
117
118    fn new_mut_most_recently_accessed(
119        util: &mut CacheStoreUtilT, index: CacheIndexT,
120    ) -> CacheAlgoDataSetterMostRecentlyAccessed<'_, CacheStoreUtilT, CacheIndexT>
121    {
122        // See `new_mut`: write-only placeholder, overwritten before flush.
123        CacheAlgoDataSetterMostRecentlyAccessed {
124            cache_store_util: util,
125            element_index: index,
126            algo_data: Default::default(),
127        }
128    }
129}
130
131#[derive(Debug, PartialEq)]
132pub enum CacheAccessResult<CacheIndexT> {
133    Hit,
134    MissInsert,
135    MissReplaced {
136        evicted: Vec<CacheIndexT>,
137        evicted_keep_cache_algo_data: Vec<CacheIndexT>,
138    },
139}
140
141pub trait CacheAlgorithm: Send {
142    type CacheIndex: CacheIndexTrait;
143    type CacheAlgoData: CacheAlgoDataTrait;
144
145    /// The cache index is the identifier for content being cached. If user want
146    /// to reuse the cache storage of evicted cache element, it should be
147    /// done in the cache storage.
148    fn access<
149        CacheStoreUtilT: CacheStoreUtil<
150            ElementIndex = Self::CacheIndex,
151            CacheAlgoData = Self::CacheAlgoData,
152        >,
153    >(
154        &mut self, cache_index: Self::CacheIndex,
155        cache_store_util: &mut CacheStoreUtilT,
156    ) -> CacheAccessResult<Self::CacheIndex>;
157
158    /// When an element is removed because of external logic, update the cache
159    /// algorithm.
160    ///
161    /// Note 1: do not use cache_store_util which implements special
162    /// logic for most recently accessed cache index, because the case
163    /// doesn't apply in deletion.
164    ///
165    /// Note 2: Since the cache deletion updates cache_algo_data for the element
166    /// to delete, caller must delete the item after the call to this delete
167    /// method has finished.
168    fn delete<
169        CacheStoreUtilT: CacheStoreUtil<
170            ElementIndex = Self::CacheIndex,
171            CacheAlgoData = Self::CacheAlgoData,
172        >,
173    >(
174        &mut self, cache_index: Self::CacheIndex,
175        cache_store_util: &mut CacheStoreUtilT,
176    );
177
178    fn log_usage(&self, prefix: &str);
179}
180
181// TODO(yz): maybe replace it with a library.
182pub trait PrimitiveNum:
183    Copy
184    + Debug
185    + Display
186    + Add<Output = Self>
187    + AddAssign
188    + Sub<Output = Self>
189    + SubAssign
190    + Div<Output = Self>
191    + DivAssign
192    + Mul<Output = Self>
193    + PartialOrd
194    + PartialEq
195    + MyInto<usize>
196    + MyInto<isize>
197    + MyFrom<i32>
198    + MyFrom<usize>
199    + Send
200    + MallocSizeOf
201{
202}
203
204pub trait MyFrom<X> {
205    fn from(x: X) -> Self;
206}
207
208pub trait MyInto<X> {
209    fn into(self) -> X;
210}
211
212impl MyFrom<usize> for u32 {
213    fn from(x: usize) -> Self { x as Self }
214}
215
216impl MyFrom<i32> for u32 {
217    fn from(x: i32) -> Self { x as Self }
218}
219
220impl MyInto<isize> for u32 {
221    fn into(self) -> isize { self as isize }
222}
223
224impl MyInto<usize> for u32 {
225    fn into(self) -> usize { self as usize }
226}
227
228impl PrimitiveNum for u32 {}
229
230struct CacheAlgoDataSetter<
231    'a,
232    CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
233    CacheIndexT: CacheIndexTrait,
234> where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
235{
236    algo_data: CacheStoreUtilT::CacheAlgoData,
237    element_index: CacheIndexT,
238    cache_store_util: &'a mut CacheStoreUtilT,
239}
240
241impl<
242        'a,
243        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
244        CacheIndexT: CacheIndexTrait,
245    > Drop for CacheAlgoDataSetter<'a, CacheStoreUtilT, CacheIndexT>
246where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
247{
248    fn drop(&mut self) {
249        let (util, index, data) = (
250            &mut self.cache_store_util,
251            &self.element_index,
252            &self.algo_data,
253        );
254        util.set(*index, data);
255    }
256}
257
258impl<
259        'a,
260        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
261        CacheIndexT: CacheIndexTrait,
262    > Deref for CacheAlgoDataSetter<'a, CacheStoreUtilT, CacheIndexT>
263where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
264{
265    type Target = CacheStoreUtilT::CacheAlgoData;
266
267    fn deref(&self) -> &Self::Target { &self.algo_data }
268}
269
270impl<
271        'a,
272        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
273        CacheIndexT: CacheIndexTrait,
274    > DerefMut for CacheAlgoDataSetter<'a, CacheStoreUtilT, CacheIndexT>
275where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
276{
277    fn deref_mut(&mut self) -> &mut Self::Target { &mut self.algo_data }
278}
279
280struct CacheAlgoDataSetterMostRecentlyAccessed<
281    'a,
282    CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
283    CacheIndexT: CacheIndexTrait,
284> where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
285{
286    algo_data: CacheStoreUtilT::CacheAlgoData,
287    element_index: CacheIndexT,
288    cache_store_util: &'a mut CacheStoreUtilT,
289}
290
291impl<
292        'a,
293        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
294        CacheIndexT: CacheIndexTrait,
295    > Drop
296    for CacheAlgoDataSetterMostRecentlyAccessed<
297        'a,
298        CacheStoreUtilT,
299        CacheIndexT,
300    >
301where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
302{
303    fn drop(&mut self) {
304        let (util, index, data) = (
305            &mut self.cache_store_util,
306            &self.element_index,
307            &self.algo_data,
308        );
309        util.set_most_recently_accessed(*index, data);
310    }
311}
312
313impl<
314        'a,
315        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
316        CacheIndexT: CacheIndexTrait,
317    > Deref
318    for CacheAlgoDataSetterMostRecentlyAccessed<
319        'a,
320        CacheStoreUtilT,
321        CacheIndexT,
322    >
323where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
324{
325    type Target = CacheStoreUtilT::CacheAlgoData;
326
327    fn deref(&self) -> &Self::Target { &self.algo_data }
328}
329
330impl<
331        'a,
332        CacheStoreUtilT: 'a + CacheStoreUtil<ElementIndex = CacheIndexT>,
333        CacheIndexT: CacheIndexTrait,
334    > DerefMut
335    for CacheAlgoDataSetterMostRecentlyAccessed<
336        'a,
337        CacheStoreUtilT,
338        CacheIndexT,
339    >
340where CacheStoreUtilT::CacheAlgoData: CacheAlgoDataTrait
341{
342    fn deref_mut(&mut self) -> &mut Self::Target { &mut self.algo_data }
343}
344
345use malloc_size_of::MallocSizeOf;
346use std::{
347    fmt::{Debug, Display},
348    marker::PhantomData,
349    ops::{
350        Add, AddAssign, Deref, DerefMut, Div, DivAssign, Mul, Sub, SubAssign,
351    },
352};
cfx_storage/impls/delta_mpt/cache/algorithm/mod.rs

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