selinux/kernel/avc/
local_cache.rs

1// Copyright 2026 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 crate::kernel::{ClassPermission, KernelAccessDecision, KernelClass, KernelPermission};
6use crate::permission_check::PermissionCheckResult;
7use crate::policy::{AccessVector, XpermsKind};
8use crate::{PolicySeqNo, SecurityId};
9use std::cell::Cell;
10
11/// Simple allow decision (allowed, not audited, not permissive, no TODO bug).
12const SIMPLE_ALLOW: PermissionCheckResult =
13    PermissionCheckResult { granted: true, audit: false, permissive: false, todo_bug: None };
14
15/// Sizes for the different caches. These have been experimentally determined.
16///
17/// These must be powers of two so that modulo indexing (`% *_CACHE_SIZE`) compiles to a single
18/// bitwise mask while allowing the compiler to elide array bounds checks.
19const FD_USE_CACHE_SIZE: usize = 1 << 2;
20const ACCESS_CACHE_SIZE: usize = 1 << 3;
21const XPERM_CACHE_SIZE: usize = 1 << 1;
22
23/// Each nibble in LruState stores the index of the entry in that cache position, from most recent
24/// (least significant nibble) to least recent (most significant nibble).
25#[derive(Clone, Copy, Debug)]
26struct LruState<const ENTRIES: usize>(u32);
27
28impl<const ENTRIES: usize> LruState<ENTRIES> {
29    fn new() -> Self {
30        const {
31            assert!(ENTRIES > 0 && ENTRIES <= 8);
32        }
33        let mask = if ENTRIES >= 8 { u32::MAX } else { (1_u32 << (ENTRIES * 4)) - 1 };
34        Self(0x76543210 & mask)
35    }
36
37    /// Finds an entry to evict and put it back as most recently used.
38    fn evict(&mut self) -> usize {
39        // We evict the least recently used entry, which is the one at the highest index.
40        let shift = (ENTRIES - 1) * 4;
41        let evicted = (self.0 >> shift) & 0xF;
42        // The evicted entry is now first, all other entries are shifted down by one position.
43        self.0 = (self.0 << 4) | evicted;
44        evicted as usize
45    }
46
47    /// Moves the entry from position `hit_idx` to most recently used (index 0).
48    fn touch_mru_idx(&mut self, hit_idx: usize) {
49        if hit_idx >= ENTRIES || hit_idx == 0 {
50            return;
51        }
52        let pos = hit_idx * 4;
53        let val = (self.0 >> pos) & 0xF; // The nibble to move to index 0.
54
55        // 1. Get the bits below the nibble at `pos`. These represent indices 0 to hit_idx - 1.
56        //    These bits need to be shifted left by 4.
57        let lower_mask = (1_u32 << pos) - 1;
58        let lower_part = self.0 & lower_mask;
59        let shifted_lower = lower_part << 4;
60
61        // 2. Get the bits above the nibble at `pos`. These represent indices hit_idx + 1 to entries - 1.
62        //    These bits remain in place relative to each other.
63        //    Pre-apply the shift of 4 to avoid an illegal shift of 32 when pos == 28 (hit_idx == 7).
64        let upper_mask = (!0_u32 << 4) << pos;
65        let upper_part = self.0 & upper_mask;
66
67        // 3. Combine the parts: [upper_part] | [shifted_lower] | [val]
68        self.0 = upper_part | shifted_lower | val;
69    }
70}
71
72/// Packs two SecurityIds into a u64 for efficient aligned comparison.
73#[derive(Clone, Copy, Debug, PartialEq, Eq)]
74struct SidPair(u64);
75
76impl SidPair {
77    fn new(source: SecurityId, target: SecurityId) -> Self {
78        Self((source.0.get() as u64) << 32 | (target.0.get() as u64))
79    }
80    const NONE: Self = Self(0);
81}
82
83impl Default for SidPair {
84    fn default() -> Self {
85        Self::NONE
86    }
87}
88
89#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
90struct XpermCacheKey {
91    sids: SidPair,
92    // Packs (kind as u8, permission.class() as u8, permission.id() as u8, xperm as u16)
93    details: u64,
94}
95
96impl XpermCacheKey {
97    fn new(
98        source_sid: SecurityId,
99        target_sid: SecurityId,
100        kind: XpermsKind,
101        permission: &KernelPermission,
102        xperm: u16,
103    ) -> Self {
104        let kind_num = match kind {
105            XpermsKind::Ioctl => 0u64,
106            XpermsKind::Nlmsg => 1u64,
107        };
108        let class_num = permission.class() as u64;
109        let id_num = permission.id() as u64;
110        let xperm_num = xperm as u64;
111        let details = (kind_num << 40) | (class_num << 32) | (id_num << 16) | xperm_num;
112        Self { sids: SidPair::new(source_sid, target_sid), details }
113    }
114}
115
116/// Per-thread cache for SELinux policy decisions.
117#[derive(Debug)]
118pub struct PerThreadCache {
119    /// Policy version for which this cache is valid.
120    policy_seqno: Cell<PolicySeqNo>,
121    /// fd_use cache. Stores "simple allow" decisions (allowed, not audited, not permissive, no TODO bug).
122    fd_use_cache: [Cell<SidPair>; FD_USE_CACHE_SIZE],
123    fd_use_lru: Cell<LruState<FD_USE_CACHE_SIZE>>,
124    /// Access query cache. This only stores "simple" (non-permissive, non-TODO) access decisions.
125    /// Decomposed as a structure-of-array for efficient packing.
126    access_cache_sid_idx: [Cell<SidPair>; ACCESS_CACHE_SIZE],
127    access_cache_class_idx: [Cell<KernelClass>; ACCESS_CACHE_SIZE],
128    access_cache_result: [Cell<(AccessVector, AccessVector)>; ACCESS_CACHE_SIZE],
129    access_lru: Cell<LruState<ACCESS_CACHE_SIZE>>,
130    /// Xperm query cache. This cache is indexed by the exact extended permission required.
131    xperm_cache: [Cell<XpermCacheKey>; XPERM_CACHE_SIZE],
132    xperm_lru: Cell<LruState<XPERM_CACHE_SIZE>>,
133}
134
135impl Default for PerThreadCache {
136    fn default() -> Self {
137        Self {
138            policy_seqno: Cell::new(PolicySeqNo::INITIAL),
139            fd_use_cache: std::array::from_fn(|_| Cell::new(SidPair::NONE)),
140            fd_use_lru: Cell::new(LruState::new()),
141            access_cache_sid_idx: std::array::from_fn(|_| Cell::new(SidPair::NONE)),
142            access_cache_class_idx: std::array::from_fn(|_| Cell::new(KernelClass::File)),
143            access_cache_result: std::array::from_fn(|_| {
144                Cell::new((AccessVector::NONE, AccessVector::NONE))
145            }),
146            access_lru: Cell::new(LruState::new()),
147            xperm_cache: std::array::from_fn(|_| Cell::new(XpermCacheKey::default())),
148            xperm_lru: Cell::new(LruState::new()),
149        }
150    }
151}
152
153impl PerThreadCache {
154    #[cold]
155    fn reset(&self) {
156        self.fd_use_cache.iter().for_each(|c| c.set(SidPair::NONE));
157        self.fd_use_lru.set(LruState::new());
158        self.access_cache_sid_idx.iter().for_each(|c| c.set(SidPair::NONE));
159        self.access_lru.set(LruState::new());
160        self.xperm_cache.iter().for_each(|c| c.set(XpermCacheKey::default()));
161        self.xperm_lru.set(LruState::new());
162    }
163
164    /// Checks whether the policy version has changed since the last time the cache was accessed, and
165    /// resets the cache in this case.
166    fn check_policy_version(&self, policy_seqno: PolicySeqNo) {
167        if self.policy_seqno.get() != policy_seqno {
168            self.reset();
169            self.policy_seqno.set(policy_seqno);
170        }
171    }
172
173    /// Looks up a fd use decision in cache, or falls back to using `compute`.
174    #[inline]
175    pub(crate) fn lookup_fd_use<F>(
176        &self,
177        policy_seqno: PolicySeqNo,
178        source_sid: SecurityId,
179        target_sid: SecurityId,
180        compute: F,
181    ) -> PermissionCheckResult
182    where
183        F: FnOnce() -> PermissionCheckResult,
184    {
185        self.check_policy_version(policy_seqno);
186
187        let key = SidPair::new(source_sid, target_sid);
188        let mut lru = self.fd_use_lru.get();
189        let mut sequence = lru.0;
190        for hit_idx in 0..FD_USE_CACHE_SIZE {
191            let i = (sequence & 0xF) as usize % FD_USE_CACHE_SIZE;
192            if self.fd_use_cache[i].get() == key {
193                if hit_idx != 0 {
194                    lru.touch_mru_idx(hit_idx);
195                    self.fd_use_lru.set(lru);
196                }
197                return SIMPLE_ALLOW;
198            }
199            sequence >>= 4;
200        }
201        self.lookup_fd_use_miss(key, lru, compute)
202    }
203
204    // Outlined to avoid creating a stack frame on the hot cache hit path.
205    #[inline(never)]
206    fn lookup_fd_use_miss<F>(
207        &self,
208        key: SidPair,
209        mut lru: LruState<FD_USE_CACHE_SIZE>,
210        compute: F,
211    ) -> PermissionCheckResult
212    where
213        F: FnOnce() -> PermissionCheckResult,
214    {
215        let result = compute();
216        // Only cache simple "allow" decisions. This keeps the cache smaller and focuses on the
217        // most common case.
218        if result == SIMPLE_ALLOW {
219            let evicted = lru.evict();
220            self.fd_use_lru.set(lru);
221            self.fd_use_cache[evicted % FD_USE_CACHE_SIZE].set(key);
222        }
223        result
224    }
225
226    /// Looks up an xperms access decision in cache, or falls back to calling `compute`.
227    #[inline]
228    pub(crate) fn check_xperm<F>(
229        &self,
230        policy_seqno: PolicySeqNo,
231        kind: XpermsKind,
232        source_sid: SecurityId,
233        target_sid: SecurityId,
234        permission: KernelPermission,
235        xperm: u16,
236        compute: F,
237    ) -> PermissionCheckResult
238    where
239        F: FnOnce() -> PermissionCheckResult,
240    {
241        self.check_policy_version(policy_seqno);
242        let key = XpermCacheKey::new(source_sid, target_sid, kind, &permission, xperm);
243        let mut lru = self.xperm_lru.get();
244        let mut sequence = lru.0;
245        for hit_idx in 0..XPERM_CACHE_SIZE {
246            let i = (sequence & 0xF) as usize % XPERM_CACHE_SIZE;
247            if self.xperm_cache[i].get() == key {
248                if hit_idx != 0 {
249                    lru.touch_mru_idx(hit_idx);
250                    self.xperm_lru.set(lru);
251                }
252                return SIMPLE_ALLOW;
253            }
254            sequence >>= 4;
255        }
256        self.check_xperm_miss(key, lru, compute)
257    }
258
259    // Outlined to avoid creating a stack frame on the hot cache hit path.
260    #[inline(never)]
261    fn check_xperm_miss<F>(
262        &self,
263        key: XpermCacheKey,
264        mut lru: LruState<XPERM_CACHE_SIZE>,
265        compute: F,
266    ) -> PermissionCheckResult
267    where
268        F: FnOnce() -> PermissionCheckResult,
269    {
270        let result = compute();
271        // Only cache simple "allow" decisions. This keeps the cache smaller and focuses on the
272        // most common case.
273        if result == SIMPLE_ALLOW {
274            let evicted = lru.evict();
275            self.xperm_lru.set(lru);
276            self.xperm_cache[evicted % XPERM_CACHE_SIZE].set(key);
277        }
278        result
279    }
280
281    /// Looks up an access decision in cache, or falls back to calling `compute`. This caches the
282    /// whole access vector instead of individual permissions so that multiple checks for different
283    /// permissions on the same (source, target, class) triple can make use of the cache.
284    #[inline]
285    pub(crate) fn lookup_access_decision<F>(
286        &self,
287        policy_seqno: PolicySeqNo,
288        source_sid: SecurityId,
289        target_sid: SecurityId,
290        class: KernelClass,
291        compute: F,
292    ) -> KernelAccessDecision
293    where
294        F: FnOnce() -> KernelAccessDecision,
295    {
296        self.check_policy_version(policy_seqno);
297        let key = SidPair::new(source_sid, target_sid);
298        let mut lru = self.access_lru.get();
299        let mut sequence = lru.0;
300        for hit_idx in 0..ACCESS_CACHE_SIZE {
301            let i = (sequence & 0xF) as usize % ACCESS_CACHE_SIZE;
302            if key == self.access_cache_sid_idx[i].get()
303                && class == self.access_cache_class_idx[i].get()
304            {
305                if hit_idx != 0 {
306                    lru.touch_mru_idx(hit_idx);
307                    self.access_lru.set(lru);
308                }
309                let (allow, audit) = self.access_cache_result[i].get();
310                return KernelAccessDecision { allow, audit, flags: 0, todo_bug: None };
311            }
312            sequence >>= 4;
313        }
314        self.lookup_access_decision_miss(key, class, lru, compute)
315    }
316
317    // Outlined to avoid creating a stack frame on the hot cache hit path.
318    #[inline(never)]
319    fn lookup_access_decision_miss<F>(
320        &self,
321        key: SidPair,
322        class: KernelClass,
323        mut lru: LruState<ACCESS_CACHE_SIZE>,
324        compute: F,
325    ) -> KernelAccessDecision
326    where
327        F: FnOnce() -> KernelAccessDecision,
328    {
329        let result = compute();
330
331        // Only cache decisions that do not have an associated todo bug or flags. This keeps the
332        // cache smaller and focused on the common case.
333        if result.todo_bug.is_none() && result.flags == 0 {
334            let evicted = lru.evict();
335            self.access_lru.set(lru);
336            let idx = evicted % ACCESS_CACHE_SIZE;
337            self.access_cache_sid_idx[idx].set(key);
338            self.access_cache_class_idx[idx].set(class);
339            self.access_cache_result[idx].set((result.allow, result.audit));
340        }
341
342        result
343    }
344}
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349    use crate::FilePermission;
350
351    #[test]
352    fn test_lru_state() {
353        let mut lru = LruState::<4>::new();
354        assert_eq!(lru.0, 0x3210);
355
356        // Touch 2 at index 2 - it moves to front.
357        lru.touch_mru_idx(2);
358        assert_eq!(lru.0, 0x3102);
359
360        // Evict LRU.
361        assert_eq!(lru.evict(), 3);
362        assert_eq!(lru.0 & 0xFFFF, 0x1023);
363
364        // Touch 0 at index 2.
365        lru.touch_mru_idx(2);
366        assert_eq!(lru.0 & 0xFFFF, 0x1230);
367
368        // Evict LRU.
369        assert_eq!(lru.evict(), 1);
370        assert_eq!(lru.0 & 0xFFFF, 0x2301);
371    }
372
373    #[test]
374    fn test_touch_mru_idx_max_entries() {
375        let mut lru = LruState::<8>::new();
376        // Touch index 7 (last entry).
377        lru.touch_mru_idx(7);
378        // Verify no panic and state is updated.
379        // Initial state for 8 entries is 0x76543210.
380        // Touching 7 (at pos 28) means moving nibble 7 to front.
381        assert_eq!(lru.0, 0x65432107);
382    }
383
384    #[test]
385    fn test_cache_lookup_hit() {
386        let cache = PerThreadCache::default();
387        let sid1 = SecurityId(1.try_into().unwrap());
388        let sid2 = SecurityId(2.try_into().unwrap());
389
390        // First lookup: miss, calls compute.
391        let mut compute_called = false;
392        let result = cache.lookup_fd_use(PolicySeqNo::INITIAL, sid1, sid2, || {
393            compute_called = true;
394            PermissionCheckResult { granted: true, audit: false, permissive: false, todo_bug: None }
395        });
396        assert!(compute_called);
397        assert!(result.granted);
398
399        // Second lookup: hit, does not call compute.
400        compute_called = false;
401        let result2 = cache.lookup_fd_use(PolicySeqNo::INITIAL, sid1, sid2, || {
402            compute_called = true;
403            PermissionCheckResult {
404                granted: false,
405                audit: false,
406                permissive: false,
407                todo_bug: None,
408            }
409        });
410        assert!(!compute_called);
411        assert!(result2.granted);
412    }
413
414    #[test]
415    fn test_fd_use_cache_invalidation_on_policy_change() {
416        let cache = PerThreadCache::default();
417        let sid1 = SecurityId(1.try_into().unwrap());
418        let sid2 = SecurityId(2.try_into().unwrap());
419
420        // Cache a result with policy change count 0.
421        cache.lookup_fd_use(PolicySeqNo::INITIAL, sid1, sid2, || PermissionCheckResult {
422            granted: true,
423            audit: false,
424            permissive: false,
425            todo_bug: None,
426        });
427
428        // Lookup with policy change count 1: should miss because policy changed.
429        let mut compute_called = false;
430        let result = cache.lookup_fd_use(PolicySeqNo::OTHER, sid1, sid2, || {
431            compute_called = true;
432            PermissionCheckResult {
433                granted: false,
434                audit: false,
435                permissive: false,
436                todo_bug: None,
437            }
438        });
439        assert!(compute_called);
440        assert!(!result.granted);
441    }
442
443    #[test]
444    fn test_access_cache_lookup() {
445        let cache = PerThreadCache::default();
446        let sid1 = SecurityId(1.try_into().unwrap());
447        let sid2 = SecurityId(2.try_into().unwrap());
448        let class = KernelClass::File;
449
450        let mut compute_called = false;
451        let result = cache.lookup_access_decision(PolicySeqNo::INITIAL, sid1, sid2, class, || {
452            compute_called = true;
453            KernelAccessDecision {
454                allow: AccessVector::from(1),
455                audit: AccessVector::NONE,
456                flags: 0,
457                todo_bug: None,
458            }
459        });
460        assert!(compute_called);
461        assert_eq!(result.allow, AccessVector::from(1));
462
463        compute_called = false;
464        let result2 = cache.lookup_access_decision(PolicySeqNo::INITIAL, sid1, sid2, class, || {
465            compute_called = true;
466            KernelAccessDecision {
467                allow: AccessVector::NONE,
468                audit: AccessVector::NONE,
469                flags: 0,
470                todo_bug: None,
471            }
472        });
473        assert!(!compute_called);
474        assert_eq!(result2.allow, AccessVector::from(1));
475    }
476
477    #[test]
478    fn test_access_cache_todo_uncached() {
479        let cache = PerThreadCache::default();
480        let sid1 = SecurityId(1.try_into().unwrap());
481        let sid2 = SecurityId(2.try_into().unwrap());
482        let class = KernelClass::File;
483
484        cache.lookup_access_decision(PolicySeqNo::INITIAL, sid1, sid2, class, || {
485            KernelAccessDecision {
486                allow: AccessVector::from(1),
487                audit: AccessVector::NONE,
488                flags: 0,
489                todo_bug: Some(123.try_into().unwrap()),
490            }
491        });
492
493        let mut compute_called = false;
494        cache.lookup_access_decision(PolicySeqNo::INITIAL, sid1, sid2, class, || {
495            compute_called = true;
496            KernelAccessDecision {
497                allow: AccessVector::NONE,
498                audit: AccessVector::NONE,
499                flags: 0,
500                todo_bug: None,
501            }
502        });
503        assert!(compute_called);
504    }
505
506    #[test]
507    fn test_access_cache_permissive_uncached() {
508        let cache = PerThreadCache::default();
509        let sid1 = SecurityId(1.try_into().unwrap());
510        let sid2 = SecurityId(2.try_into().unwrap());
511        let class = KernelClass::File;
512
513        cache.lookup_access_decision(PolicySeqNo::INITIAL, sid1, sid2, class, || {
514            KernelAccessDecision {
515                allow: AccessVector::from(1),
516                audit: AccessVector::NONE,
517                flags: 1,
518                todo_bug: None,
519            }
520        });
521
522        let mut compute_called = false;
523        cache.lookup_access_decision(PolicySeqNo::INITIAL, sid1, sid2, class, || {
524            compute_called = true;
525            KernelAccessDecision {
526                allow: AccessVector::NONE,
527                audit: AccessVector::NONE,
528                flags: 0,
529                todo_bug: None,
530            }
531        });
532        assert!(compute_called);
533    }
534
535    #[test]
536    fn test_xperm_cache_lookup() {
537        let cache = PerThreadCache::default();
538        let sid1 = SecurityId(1.try_into().unwrap());
539        let sid2 = SecurityId(2.try_into().unwrap());
540        let permission = KernelPermission::File(FilePermission::Ioctl);
541
542        let mut compute_called = false;
543        let result = cache.check_xperm(
544            PolicySeqNo::INITIAL,
545            XpermsKind::Ioctl,
546            sid1,
547            sid2,
548            permission.clone(),
549            1,
550            || {
551                compute_called = true;
552                PermissionCheckResult {
553                    granted: true,
554                    audit: false,
555                    permissive: false,
556                    todo_bug: None,
557                }
558            },
559        );
560        assert!(compute_called);
561        assert!(result.granted);
562
563        compute_called = false;
564        let result2 = cache.check_xperm(
565            PolicySeqNo::INITIAL,
566            XpermsKind::Ioctl,
567            sid1,
568            sid2,
569            permission,
570            1,
571            || {
572                compute_called = true;
573                PermissionCheckResult {
574                    granted: false,
575                    audit: false,
576                    permissive: false,
577                    todo_bug: None,
578                }
579            },
580        );
581        assert!(!compute_called);
582        assert!(result2.granted);
583    }
584
585    #[test]
586    fn test_access_cache_invalidation_on_policy_change() {
587        let cache = PerThreadCache::default();
588        let sid1 = SecurityId(1.try_into().unwrap());
589        let sid2 = SecurityId(2.try_into().unwrap());
590        let class = KernelClass::File;
591
592        cache.lookup_access_decision(PolicySeqNo::INITIAL, sid1, sid2, class, || {
593            KernelAccessDecision {
594                allow: AccessVector::from(1),
595                audit: AccessVector::NONE,
596                flags: 0,
597                todo_bug: None,
598            }
599        });
600
601        let mut compute_called = false;
602        let result = cache.lookup_access_decision(PolicySeqNo::OTHER, sid1, sid2, class, || {
603            compute_called = true;
604            KernelAccessDecision {
605                allow: AccessVector::NONE,
606                audit: AccessVector::NONE,
607                flags: 0,
608                todo_bug: None,
609            }
610        });
611        assert!(compute_called);
612        assert_eq!(result.allow, AccessVector::NONE);
613    }
614
615    #[test]
616    fn test_xperm_cache_invalidation_on_policy_change() {
617        let cache = PerThreadCache::default();
618        let sid1 = SecurityId(1.try_into().unwrap());
619        let sid2 = SecurityId(2.try_into().unwrap());
620        let permission = KernelPermission::File(FilePermission::Ioctl);
621
622        cache.check_xperm(
623            PolicySeqNo::INITIAL,
624            XpermsKind::Ioctl,
625            sid1,
626            sid2,
627            permission.clone(),
628            1,
629            || PermissionCheckResult {
630                granted: true,
631                audit: false,
632                permissive: false,
633                todo_bug: None,
634            },
635        );
636
637        let mut compute_called = false;
638        let result = cache.check_xperm(
639            PolicySeqNo::OTHER,
640            XpermsKind::Ioctl,
641            sid1,
642            sid2,
643            permission,
644            1,
645            || {
646                compute_called = true;
647                PermissionCheckResult {
648                    granted: false,
649                    audit: false,
650                    permissive: false,
651                    todo_bug: None,
652                }
653            },
654        );
655        assert!(compute_called);
656        assert!(!result.granted);
657    }
658}
selinux/kernel/avc/local_cache.rs

selinux/kernel/avc/
local_cache.rs
