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

selinux/kernel/avc/
local_cache.rs
