selinux/
fifo_cache.rs

Help
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 indexmap::IndexMap;
6use std::hash::Hash;
7use std::ops::Add;
8
9#[cfg(test)]
10use indexmap::map::Iter;
11
12/// Describes the performance statistics of a cache implementation.
13#[derive(Default, Debug, Clone, PartialEq)]
14pub struct CacheStats {
15    /// Cumulative count of lookups performed on the cache.
16    pub lookups: u64,
17    /// Cumulative count of lookups that returned data from an existing cache entry.
18    pub hits: u64,
19    /// Cumulative count of lookups that did not match any existing cache entry.
20    pub misses: u64,
21    /// Cumulative count of insertions into the cache.
22    pub allocs: u64,
23    /// Cumulative count of evictions from the cache, to make space for a new insertion.
24    pub reclaims: u64,
25    /// Cumulative count of evictions from the cache due to no longer being deemed relevant.
26    /// This is not used in our current implementation.
27    pub frees: u64,
28}
29
30impl Add for &CacheStats {
31    type Output = CacheStats;
32
33    fn add(self, other: &CacheStats) -> CacheStats {
34        CacheStats {
35            lookups: self.lookups + other.lookups,
36            hits: self.hits + other.hits,
37            misses: self.misses + other.misses,
38            allocs: self.allocs + other.allocs,
39            reclaims: self.reclaims + other.reclaims,
40            frees: self.frees + other.frees,
41        }
42    }
43}
44
45/// An interface through which statistics may be obtained from each cache.
46pub trait HasCacheStats {
47    /// Returns statistics for the cache implementation.
48    fn cache_stats(&self) -> CacheStats;
49}
50
51/// Associative FIFO cache with capacity defined at creation.
52///
53/// Lookups in the cache are O(1), as are evictions.
54///
55/// This implementation is thread-hostile; it expects all operations to be executed on the same
56/// thread.
57pub(super) struct FifoCache<A: Hash + Eq, R> {
58    cache: IndexMap<A, R>,
59    capacity: usize,
60    oldest_index: usize,
61    stats: CacheStats,
62}
63
64impl<A: Hash + Eq, R> FifoCache<A, R> {
65    pub fn with_capacity(capacity: usize) -> Self {
66        assert!(capacity > 0, "cannot instantiate fixed access vector cache of size 0");
67
68        Self {
69            // Request `capacity` plus one element working-space for insertions that trigger
70            // an eviction.
71            cache: IndexMap::with_capacity(capacity + 1),
72            capacity,
73            oldest_index: 0,
74            stats: CacheStats::default(),
75        }
76    }
77
78    /// Returns true if the cache has reached capacity.
79    #[inline]
80    pub fn is_full(&self) -> bool {
81        self.cache.len() == self.capacity
82    }
83
84    /// Returns the capacity with which this instance was initialized.
85    pub fn capacity(&self) -> usize {
86        self.capacity
87    }
88
89    /// Searches the cache and returns the index of a [`QueryAndResult`] matching
90    /// the given `source_sid`, `target_sid`, and `target_class` (or returns `None`).
91    #[inline]
92    pub fn get(&mut self, query_args: &A) -> Option<&mut R> {
93        self.stats.lookups += 1;
94
95        let result = self.cache.get_mut(query_args);
96
97        if result.is_some() {
98            self.stats.hits += 1;
99        } else {
100            self.stats.misses += 1;
101        }
102
103        result
104    }
105
106    /// Inserts the specified `query` and `result` into the cache, evicting the oldest existing
107    /// entry if capacity has been reached.
108    #[inline]
109    pub fn insert(&mut self, query: A, result: R) -> &mut R {
110        self.stats.allocs += 1;
111
112        // If the cache is already full then it will be necessary to evict an existing entry.
113        // Eviction is performed after inserting the new entry, to allow the eviction operation to
114        // be implemented via swap-into-place.
115        let must_evict = self.is_full();
116
117        // Insert the entry, at the end of the `IndexMap` queue, then evict the oldest element.
118        let (mut index, _) = self.cache.insert_full(query, result);
119        if must_evict {
120            // The final element in the ordered container is the newly-added entry, so we can simply
121            // swap it with the oldest element, and then remove the final element, to achieve FIFO
122            // eviction.
123            assert_eq!(index, self.capacity);
124
125            self.cache.swap_remove_index(self.oldest_index);
126            self.stats.reclaims += 1;
127
128            index = self.oldest_index;
129
130            self.oldest_index += 1;
131            if self.oldest_index == self.capacity {
132                self.oldest_index = 0;
133            }
134        }
135
136        self.cache.get_index_mut(index).map(|(_, v)| v).expect("invalid index after insert!")
137    }
138
139    /// Returns an iterator over the cache elements, for use by tests.
140    #[cfg(test)]
141    #[allow(dead_code)] // Only used by `access_vector_cache.rs` tests when built for Fuchsia.
142    pub fn iter(&self) -> Iter<'_, A, R> {
143        self.cache.iter()
144    }
145}
146
147impl<A: Hash + Eq, R> HasCacheStats for FifoCache<A, R> {
148    fn cache_stats(&self) -> CacheStats {
149        self.stats.clone()
150    }
151}
selinux/fifo_cache.rs

selinux/
fifo_cache.rs
