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

selinux/
local_cache.rs
