fxfs/object_store/
tree_cache.rs

1// Copyright 2023 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use super::object_record::{ObjectKey, ObjectKeyData, ObjectValue};
6use crate::lsm_tree::cache::{ObjectCache, ObjectCachePlaceholder, ObjectCacheResult};
7use fuchsia_sync::Mutex;
8use linked_hash_map::{Entry, LinkedHashMap};
9use std::hash::BuildHasherDefault;
10use std::sync::atomic::{AtomicU64, Ordering};
11
12fn filter(key: &ObjectKey) -> bool {
13    match key.data {
14        // Attribute and keys could also be added here to some immediate benefit, but would be
15        // somewhat redundant with a node cache planned to be added after.
16        ObjectKeyData::Object => true,
17        ObjectKeyData::ExtendedAttribute { .. } => true,
18        ObjectKeyData::Keys => true,
19        _ => false,
20    }
21}
22
23// Limiting to ~100KiB of space usage. 56 bytes of linear overhead per item plus the overhead of
24// the structure. This is just used directly for now, we can parameterize it in the type if this is
25// ever desired to vary.
26const ITEM_LIMIT: usize = 1535;
27
28struct Placeholder<'a> {
29    cache: &'a TreeCache,
30    key: ObjectKey,
31    placeholder_id: u64,
32}
33
34impl Placeholder<'_> {
35    fn replace_entry(&mut self, value: Option<CacheValue>) {
36        let key = std::mem::replace(&mut self.key, ObjectKey::object(0));
37        let mut inner = self.cache.inner.lock();
38        // The value is present...
39        if let Entry::Occupied(mut entry) = inner.entry(key) {
40            // And the same placeholder as the token has...
41            let is_current = match entry.get() {
42                CacheValue::Placeholder(placeholder_id) => &self.placeholder_id == placeholder_id,
43                _ => false,
44            };
45            if is_current {
46                match value {
47                    Some(v) => *(entry.get_mut()) = v,
48                    None => {
49                        entry.remove();
50                    }
51                }
52            }
53        }
54    }
55}
56
57impl Drop for Placeholder<'_> {
58    fn drop(&mut self) {
59        self.replace_entry(None);
60    }
61}
62
63impl<'a> ObjectCachePlaceholder<ObjectValue> for Placeholder<'a> {
64    fn complete(mut self: Box<Self>, value: Option<&ObjectValue>) {
65        let entry_value = match value {
66            value @ Some(ObjectValue::Object { .. }) => value.cloned(),
67            value @ Some(ObjectValue::ExtendedAttribute(_)) => value.cloned(),
68            value @ Some(ObjectValue::Keys(_)) => value.cloned(),
69            _ => None,
70        }
71        .map(|v| CacheValue::Value(v));
72        self.replace_entry(entry_value);
73    }
74}
75
76enum CacheValue {
77    Placeholder(u64),
78    Value(ObjectValue),
79}
80
81/// Supports caching for Objects directly for now. Speeds up stat calls.
82pub struct TreeCache {
83    inner: Mutex<LinkedHashMap<ObjectKey, CacheValue, BuildHasherDefault<rustc_hash::FxHasher>>>,
84    placeholder_counter: AtomicU64,
85}
86
87impl TreeCache {
88    pub fn new() -> Self {
89        Self {
90            inner: Mutex::new(LinkedHashMap::with_capacity_and_hasher(
91                ITEM_LIMIT + 1,
92                BuildHasherDefault::<rustc_hash::FxHasher>::default(),
93            )),
94            placeholder_counter: AtomicU64::new(0),
95        }
96    }
97}
98
99impl ObjectCache<ObjectKey, ObjectValue> for TreeCache {
100    fn lookup_or_reserve(&self, key: &ObjectKey) -> ObjectCacheResult<'_, ObjectValue> {
101        if !filter(key) {
102            return ObjectCacheResult::NoCache;
103        }
104        let mut inner = self.inner.lock();
105        match inner.get_refresh(key) {
106            Some(CacheValue::Value(entry)) => ObjectCacheResult::Value(entry.clone()),
107            Some(CacheValue::Placeholder(_)) => ObjectCacheResult::NoCache,
108            _ => {
109                let placeholder_id = self.placeholder_counter.fetch_add(1, Ordering::Relaxed);
110                inner.insert(key.clone(), CacheValue::Placeholder(placeholder_id));
111                if inner.len() > ITEM_LIMIT {
112                    let _ = inner.pop_front();
113                }
114                ObjectCacheResult::Placeholder(Box::new(Placeholder {
115                    cache: self,
116                    key: key.clone(),
117                    placeholder_id,
118                }))
119            }
120        }
121    }
122
123    fn invalidate(&self, key: ObjectKey, value: Option<ObjectValue>) {
124        if !filter(&key) {
125            return;
126        }
127        let mut inner = self.inner.lock();
128        if let Entry::Occupied(mut entry) = inner.entry(key) {
129            if let Some(replacement) = value {
130                *(entry.get_mut()) = CacheValue::Value(replacement);
131            } else {
132                entry.remove();
133            }
134        }
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use super::super::object_record::{ObjectKey, ObjectValue, Timestamp};
141    use super::{ITEM_LIMIT, TreeCache};
142    use crate::lsm_tree::cache::{ObjectCache, ObjectCacheResult};
143    use crate::object_store::EncryptionKey;
144    use assert_matches::assert_matches;
145
146    #[fuchsia::test]
147    async fn test_basic_operations() {
148        let cache = TreeCache::new();
149        let key = ObjectKey::object(1);
150        let now = Timestamp::now();
151        let value = ObjectValue::file(1, 0, now, now, now, now, 0, None);
152
153        let placeholder = match cache.lookup_or_reserve(&key) {
154            ObjectCacheResult::Placeholder(placeholder) => placeholder,
155            _ => panic!("Expected cache miss with placeholder returned."),
156        };
157        placeholder.complete(Some(&value));
158
159        let result = match cache.lookup_or_reserve(&key) {
160            ObjectCacheResult::Value(value) => value,
161            _ => panic!("Expected to find item."),
162        };
163        assert_eq!(&result, &value);
164
165        cache.invalidate(key.clone(), None);
166
167        match cache.lookup_or_reserve(&key) {
168            ObjectCacheResult::Placeholder(placeholder) => placeholder.complete(None),
169            _ => panic!("Expected cache miss with placeholder returned."),
170        };
171    }
172
173    #[fuchsia::test]
174    async fn test_enforce_limits() {
175        let cache = TreeCache::new();
176        let now = Timestamp::now();
177
178        for i in 1..(ITEM_LIMIT as u64 + 2) {
179            let key = ObjectKey::object(i);
180            let value = ObjectValue::file(1, 0, now, now, now, now, 0, None);
181            let placeholder = match cache.lookup_or_reserve(&key) {
182                ObjectCacheResult::Placeholder(placeholder) => placeholder,
183                _ => panic!("Expected cache miss with placeholder returned."),
184            };
185            placeholder.complete(Some(&value));
186        }
187
188        // Item 1 should be evicted.
189        assert_matches!(
190            cache.lookup_or_reserve(&ObjectKey::object(1)),
191            ObjectCacheResult::Placeholder(_)
192        );
193
194        // And item 2 has been evicted by the lookup of item 1.
195        for i in 3..(ITEM_LIMIT as u64 + 2) {
196            let key = ObjectKey::object(i);
197            assert_matches!(cache.lookup_or_reserve(&key), ObjectCacheResult::Value(_));
198        }
199    }
200
201    #[fuchsia::test]
202    async fn test_invalidate_inserts() {
203        let cache = TreeCache::new();
204        let key = ObjectKey::object(1);
205        let now = Timestamp::now();
206        let value1 = ObjectValue::file(1, 0, now, now, now, now, 0, None);
207        let value2 = ObjectValue::file(2, 0, now, now, now, now, 0, None);
208
209        let placeholder = match cache.lookup_or_reserve(&key) {
210            ObjectCacheResult::Placeholder(placeholder) => placeholder,
211            _ => panic!("Expected cache miss with placeholder returned."),
212        };
213        placeholder.complete(Some(&value1));
214
215        let result = match cache.lookup_or_reserve(&key) {
216            ObjectCacheResult::Value(value) => value,
217            _ => panic!("Expected to find item."),
218        };
219        assert_eq!(&result, &value1);
220
221        cache.invalidate(key.clone(), Some(value2.clone()));
222
223        let result = match cache.lookup_or_reserve(&key) {
224            ObjectCacheResult::Value(value) => value,
225            _ => panic!("Expected to find item."),
226        };
227        assert_eq!(&result, &value2);
228    }
229
230    #[fuchsia::test]
231    async fn test_no_caching_for_filtered_item() {
232        let cache = TreeCache::new();
233        let key = ObjectKey::extent(1, 1, 1..2);
234
235        assert!(matches!(cache.lookup_or_reserve(&key), ObjectCacheResult::NoCache));
236    }
237
238    // Two clients looking for the same key don't interfere with each other. Prevents priority
239    // inversion.
240    #[fuchsia::test]
241    async fn test_two_parallel_clients() {
242        let cache = TreeCache::new();
243        let key = ObjectKey::object(1);
244        let now = Timestamp::now();
245        let value1 = ObjectValue::file(1, 0, now, now, now, now, 0, None);
246        let value2 = ObjectValue::file(2, 0, now, now, now, now, 0, None);
247
248        let placeholder1 = match cache.lookup_or_reserve(&key) {
249            ObjectCacheResult::Placeholder(placeholder) => placeholder,
250            _ => panic!("Expected cache miss with placeholder returned."),
251        };
252
253        // Another search should not get a placeholder, as one is already held.
254        assert!(matches!(cache.lookup_or_reserve(&key), ObjectCacheResult::NoCache));
255
256        // Invalidate the current placeholder.
257        cache.invalidate(key.clone(), None);
258
259        // Get a new placeholder
260        let placeholder2 = match cache.lookup_or_reserve(&key) {
261            ObjectCacheResult::Placeholder(placeholder) => placeholder,
262            _ => panic!("Expected cache miss with placeholder returned."),
263        };
264
265        // Complete them out of order.
266        placeholder2.complete(Some(&value2));
267        placeholder1.complete(Some(&value1));
268
269        // Result should be from the second placeholder, as the first was invalidated.
270        let result = match cache.lookup_or_reserve(&key) {
271            ObjectCacheResult::Value(value) => value,
272            _ => panic!("Expected to find item."),
273        };
274        assert_eq!(&result, &value2);
275    }
276
277    #[fuchsia::test]
278    async fn test_keys_are_cached() {
279        let cache = TreeCache::new();
280        let key = ObjectKey::keys(1);
281        let value = ObjectValue::keys(
282            vec![(2, EncryptionKey::FscryptInoLblk32File { key_identifier: [3u8; 16] })].into(),
283        );
284
285        let placeholder = match cache.lookup_or_reserve(&key) {
286            ObjectCacheResult::Placeholder(placeholder) => placeholder,
287            _ => panic!("Expected cache miss with placeholder returned."),
288        };
289        placeholder.complete(Some(&value));
290
291        let result = match cache.lookup_or_reserve(&key) {
292            ObjectCacheResult::Value(value) => value,
293            _ => panic!("Expected to find item."),
294        };
295        assert_eq!(&result, &value);
296
297        cache.invalidate(key.clone(), None);
298
299        match cache.lookup_or_reserve(&key) {
300            ObjectCacheResult::Placeholder(placeholder) => placeholder.complete(None),
301            _ => panic!("Expected cache miss with placeholder returned."),
302        };
303    }
304}
fxfs/object_store/tree_cache.rs

fxfs/object_store/
tree_cache.rs
