framehop/
rule_cache.rs

1use alloc::boxed::Box;
2
3use crate::unwind_rule::UnwindRule;
4
5const CACHE_ENTRY_COUNT: usize = 509;
6
7pub struct RuleCache<R: UnwindRule> {
8    entries: Box<[Option<CacheEntry<R>>; CACHE_ENTRY_COUNT]>,
9    stats: CacheStats,
10}
11
12impl<R: UnwindRule> RuleCache<R> {
13    pub fn new() -> Self {
14        Self {
15            entries: Box::new([None; CACHE_ENTRY_COUNT]),
16            stats: CacheStats::new(),
17        }
18    }
19
20    pub fn lookup(&mut self, address: u64, modules_generation: u16) -> CacheResult<R> {
21        let slot = (address % (CACHE_ENTRY_COUNT as u64)) as u16;
22        match &self.entries[slot as usize] {
23            None => {
24                self.stats.miss_empty_slot_count += 1;
25            }
26            Some(entry) => {
27                if entry.modules_generation == modules_generation {
28                    if entry.address == address {
29                        self.stats.hit_count += 1;
30                        return CacheResult::Hit(entry.unwind_rule);
31                    } else {
32                        self.stats.miss_wrong_address_count += 1;
33                    }
34                } else {
35                    self.stats.miss_wrong_modules_count += 1;
36                }
37            }
38        }
39        CacheResult::Miss(CacheHandle {
40            slot,
41            address,
42            modules_generation,
43        })
44    }
45
46    pub fn insert(&mut self, handle: CacheHandle, unwind_rule: R) {
47        let CacheHandle {
48            slot,
49            address,
50            modules_generation,
51        } = handle;
52        self.entries[slot as usize] = Some(CacheEntry {
53            address,
54            modules_generation,
55            unwind_rule,
56        });
57    }
58
59    /// Returns a snapshot of the cache usage statistics.
60    pub fn stats(&self) -> CacheStats {
61        self.stats
62    }
63}
64
65pub enum CacheResult<R: UnwindRule> {
66    Miss(CacheHandle),
67    Hit(R),
68}
69
70pub struct CacheHandle {
71    slot: u16,
72    address: u64,
73    modules_generation: u16,
74}
75
76const _: () = assert!(
77    CACHE_ENTRY_COUNT as u64 <= u16::MAX as u64,
78    "u16 should be sufficient to store the cache slot index"
79);
80
81#[derive(Clone, Copy, Debug)]
82struct CacheEntry<R: UnwindRule> {
83    address: u64,
84    modules_generation: u16,
85    unwind_rule: R,
86}
87
88/// Statistics about the effectiveness of the rule cache.
89#[derive(Default, Debug, Clone, Copy)]
90pub struct CacheStats {
91    /// The number of successful cache hits.
92    pub hit_count: u64,
93    /// The number of cache misses that were due to an empty slot.
94    pub miss_empty_slot_count: u64,
95    /// The number of cache misses that were due to a filled slot whose module
96    /// generation didn't match the unwinder's current module generation.
97    /// (This means that either the unwinder's modules have changed since the
98    /// rule in this slot was stored, or the same cache is used with multiple
99    /// unwinders and the unwinders are stomping on each other's cache slots.)
100    pub miss_wrong_modules_count: u64,
101    /// The number of cache misses that were due to cache slot collisions of
102    /// different addresses.
103    pub miss_wrong_address_count: u64,
104}
105
106impl CacheStats {
107    /// Create a new instance.
108    pub fn new() -> Self {
109        Default::default()
110    }
111
112    /// The number of total lookups.
113    pub fn total(&self) -> u64 {
114        self.hits() + self.misses()
115    }
116
117    /// The number of total hits.
118    pub fn hits(&self) -> u64 {
119        self.hit_count
120    }
121
122    /// The number of total misses.
123    pub fn misses(&self) -> u64 {
124        self.miss_empty_slot_count + self.miss_wrong_modules_count + self.miss_wrong_address_count
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use crate::{aarch64::UnwindRuleAarch64, x86_64::UnwindRuleX86_64};
131
132    use super::*;
133
134    // Ensure that the size of Option<CacheEntry<UnwindRuleX86_64>> doesn't change by accident.
135    #[test]
136    fn test_cache_entry_size() {
137        assert_eq!(
138            core::mem::size_of::<Option<CacheEntry<UnwindRuleX86_64>>>(),
139            16
140        );
141        assert_eq!(
142            core::mem::size_of::<Option<CacheEntry<UnwindRuleAarch64>>>(),
143            24 // <-- larger than we'd like
144        );
145    }
146}
framehop/rule_cache.rs

framehop/
rule_cache.rs
