selinux/kernel/avc/
concurrent_access_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 super::concurrent_cache::{LockFreeQueryCache, StorageStrategy};
6use super::{AccessQueryArgs, XpermsAccessQueryArgs};
7use crate::SecurityId;
8use crate::kernel::{ClassPermission, KernelAccessDecision, KernelXpermsAccessDecision};
9use crate::policy::{XpermsBitmap, XpermsKind};
10use std::sync::atomic::{AtomicU8, AtomicU16, AtomicU32, AtomicU64, Ordering};
11use zerocopy::IntoBytes;
12
13/// Cache for access decisions.
14/// This cache has 4 slots per bucket, with 25 bytes of inline storage. A bucket is 128 bytes.
15pub type ConcurrentAccessCache = LockFreeQueryCache<
16    AccessCacheStorage,
17    /* ways4 = */ 1,
18    /* u64 = */ 3,
19    /* u32 = */ 0,
20    /* u16 = */ 0,
21    /* u8 = */ 1,
22    /* out_of_line_u64s = */ 0,
23>;
24
25/// Cache for extended access decisions.
26/// This cache has 4 slots per bucket, with 11 bytes of inline storage and 256 bytes of out-of-line
27/// storage. A bucket is 64 bytes.
28pub(super) type ConcurrentXpermsCache = LockFreeQueryCache<
29    XpermsAccessCacheStorage,
30    /* ways4 = */ 1,
31    /* u64 = */ 1,
32    /* u32 = */ 0,
33    /* u16 = */ 1,
34    /* u8 = */ 1,
35    /* out_of_line_u64s = */ 8,
36>;
37
38/// Cache for computed SIDs.
39/// This cache has 8 slots per bucket, with 13 bytes of inline storage. A bucket is 128 bytes.
40pub(super) type ConcurrentSidCache = LockFreeQueryCache<
41    SidCacheStorage,
42    /* ways4 = */ 2,
43    /* u64 = */ 1,
44    /* u32 = */ 1,
45    /* u16 = */ 0,
46    /* u8 = */ 1,
47    /* out_of_line_u64s = */ 0,
48>;
49
50#[derive(Default)]
51pub struct AccessCacheStorage;
52
53/// Storage for an access vector cache entry. We store the two sids (4 bytes each) in a u64, the
54/// allow and audit AccessVectors in another u64, and the class in a u8.
55impl
56    StorageStrategy<
57        /* u64 = */ 3,
58        /* u32 = */ 0,
59        /* u16 = */ 0,
60        /* u8 = */ 1,
61        /* out_of_line_u64s = */ 0,
62    > for AccessCacheStorage
63{
64    type Key = AccessQueryArgs;
65    type Value = KernelAccessDecision;
66
67    #[inline(always)]
68    fn hash_key(&self, key: &Self::Key) -> u64 {
69        rapidhash::rapidhash(key.as_bytes())
70    }
71
72    #[inline(always)]
73    fn check_key(
74        &self,
75        key: &Self::Key,
76        inline_u64s: &[AtomicU64; 3],
77        _inline_u32s: &[AtomicU32; 0],
78        _inline_u16s: &[AtomicU16; 0],
79        inline_u8s: &[AtomicU8; 1],
80        _out_of_line_u64s: &[AtomicU64; 0],
81    ) -> bool {
82        inline_u8s[0].load(Ordering::Relaxed) == key.target_class as u8
83            && inline_u64s[0].load(Ordering::Relaxed)
84                == (key.source_sid.0.get() as u64 | (key.target_sid.0.get() as u64) << 32)
85    }
86
87    #[inline(always)]
88    fn read_value(
89        &self,
90        inline_u64s: &[AtomicU64; 3],
91        _inline_u32s: &[AtomicU32; 0],
92        _inline_u16s: &[AtomicU16; 0],
93        _inline_u8s: &[AtomicU8; 1],
94        _out_of_line_u64s: &[AtomicU64; 0],
95    ) -> Self::Value {
96        let u64_1 = inline_u64s[1].load(Ordering::Relaxed);
97        let u64_2 = inline_u64s[2].load(Ordering::Relaxed);
98
99        let allow_u32 = (u64_1 >> 32) as u32;
100        let audit_u32 = (u64_1 & 0xFFFFFFFF) as u32;
101        let flags = (u64_2 >> 32) as u32;
102        let todo_u64 = u64_2 & 0xFFFFFFFF;
103
104        KernelAccessDecision {
105            allow: allow_u32.into(),
106            audit: audit_u32.into(),
107            flags,
108            todo_bug: if todo_u64 == 0 {
109                None
110            } else {
111                Some(std::num::NonZeroU32::new(todo_u64 as u32).unwrap())
112            },
113        }
114    }
115
116    #[inline(always)]
117    fn write_key_value(
118        &self,
119        key: &Self::Key,
120        value: &Self::Value,
121        inline_u64s: &[AtomicU64; 3],
122        _inline_u32s: &[AtomicU32; 0],
123        _inline_u16s: &[AtomicU16; 0],
124        inline_u8s: &[AtomicU8; 1],
125        _out_of_line_u64s: &[AtomicU64; 0],
126    ) {
127        let source_sid = key.source_sid.0.get() as u64;
128        let target_sid = key.target_sid.0.get() as u64;
129        let target_class = key.target_class.clone() as u8;
130
131        let allow_u32: u32 = value.allow.into();
132        let allow = allow_u32 as u64;
133        let audit_u32: u32 = value.audit.into();
134        let audit = audit_u32 as u64;
135        let flags = value.flags as u64;
136        let todo_bug = match value.todo_bug {
137            Some(n) => n.get() as u64,
138            None => 0,
139        };
140
141        let u64_0 = source_sid | (target_sid << 32);
142        let u64_1 = audit | (allow << 32);
143        let u64_2 = todo_bug | (flags << 32);
144
145        inline_u64s[0].store(u64_0, Ordering::Relaxed);
146        inline_u64s[1].store(u64_1, Ordering::Relaxed);
147        inline_u64s[2].store(u64_2, Ordering::Relaxed);
148        inline_u8s[0].store(target_class, Ordering::Relaxed);
149    }
150}
151
152#[derive(Default)]
153pub(super) struct XpermsAccessCacheStorage;
154
155impl XpermsAccessCacheStorage {
156    const PERMISSION_ID_MASK: u8 = 0b0001_1111;
157    const XPERMS_KIND_BIT_INDEX: usize = 5;
158    const PERMISSIVE_BIT_INDEX: usize = 6;
159    const HAS_TODO_BIT_INDEX: usize = 7;
160
161    #[inline(always)]
162    fn pack_key(key: &XpermsAccessQueryArgs) -> (u64, u16, u8) {
163        let source_sid = key.source_sid.0.get() as u64;
164        let target_sid = key.target_sid.0.get() as u64;
165        let class = key.permission.class() as u16;
166        let xperms_prefix = key.xperms_prefix as u16;
167        let permission_id = key.permission.id() as u8;
168        let xperms_kind_bit = match key.xperms_kind {
169            XpermsKind::Ioctl => 0,
170            XpermsKind::Nlmsg => 1,
171        };
172        (
173            source_sid | (target_sid << 32),
174            class | (xperms_prefix << 8),
175            permission_id | (xperms_kind_bit << Self::XPERMS_KIND_BIT_INDEX),
176        )
177    }
178}
179
180/// Xperms storage: we store the two sids (4 bytes each) in a u64, the class and xperms_prefix in a
181/// u16, and we pack the permission, xperms_kind and 2 bits of flags in an u8. The xperm bitmaps
182/// (64 bytes in total) are stored out of line.
183impl
184    StorageStrategy<
185        /* u64 = */ 1,
186        /* u32 = */ 0,
187        /* u16 = */ 1,
188        /* u8 = */ 1,
189        /* out_of_line_u64s = */ 8,
190    > for XpermsAccessCacheStorage
191{
192    type Key = XpermsAccessQueryArgs;
193    type Value = KernelXpermsAccessDecision;
194
195    #[inline(always)]
196    fn hash_key(&self, key: &Self::Key) -> u64 {
197        let (sids, class_and_prefix, perm_and_kind) = Self::pack_key(key);
198        let details = (class_and_prefix as u64) | ((perm_and_kind as u64) << 16);
199        let bytes = ((sids as u128) | ((details as u128) << 64)).to_ne_bytes();
200        rapidhash::rapidhash(&bytes)
201    }
202
203    #[inline(always)]
204    fn check_key(
205        &self,
206        key: &Self::Key,
207        inline_u64s: &[AtomicU64; 1],
208        _inline_u32s: &[AtomicU32; 0],
209        inline_u16s: &[AtomicU16; 1],
210        inline_u8s: &[AtomicU8; 1],
211        _out_of_line_u64s: &[AtomicU64; 8],
212    ) -> bool {
213        let (u64_0, u16_0, u8_0_key) = Self::pack_key(key);
214
215        let u64_0_matches = inline_u64s[0].load(Ordering::Relaxed) == u64_0;
216        let u16_0_matches = inline_u16s[0].load(Ordering::Relaxed) == u16_0;
217        let u8_0_val = inline_u8s[0].load(Ordering::Relaxed);
218        let u8_0_matches = (u8_0_val
219            & (Self::PERMISSION_ID_MASK | (1u8 << Self::XPERMS_KIND_BIT_INDEX)))
220            == u8_0_key;
221
222        u64_0_matches && u16_0_matches && u8_0_matches
223    }
224
225    #[inline(always)]
226    fn read_value(
227        &self,
228        _inline_u64s: &[AtomicU64; 1],
229        _inline_u32s: &[AtomicU32; 0],
230        _inline_u16s: &[AtomicU16; 1],
231        inline_u8s: &[AtomicU8; 1],
232        out_of_line_u64s: &[AtomicU64; 8],
233    ) -> Self::Value {
234        let u8_0 = inline_u8s[0].load(Ordering::Relaxed);
235        let permissive = (u8_0 & (1u8 << Self::PERMISSIVE_BIT_INDEX)) != 0;
236        let has_todo = (u8_0 & (1u8 << Self::HAS_TODO_BIT_INDEX)) != 0;
237
238        let (chunks, _) = out_of_line_u64s.as_chunks::<{ XpermsBitmap::BITMAP_BLOCKS }>();
239        let allow = XpermsBitmap::from_atomics(&chunks[0]);
240        let audit = XpermsBitmap::from_atomics(&chunks[1]);
241
242        KernelXpermsAccessDecision { allow, audit, permissive, has_todo }
243    }
244
245    #[inline(always)]
246    fn write_key_value(
247        &self,
248        key: &Self::Key,
249        value: &Self::Value,
250        inline_u64s: &[AtomicU64; 1],
251        _inline_u32s: &[AtomicU32; 0],
252        inline_u16s: &[AtomicU16; 1],
253        inline_u8s: &[AtomicU8; 1],
254        out_of_line_u64s: &[AtomicU64; 8],
255    ) {
256        let (u64_0, u16_0, u8_0_key) = Self::pack_key(key);
257        let u8_0 = u8_0_key
258            | ((value.permissive as u8) << Self::PERMISSIVE_BIT_INDEX)
259            | ((value.has_todo as u8) << Self::HAS_TODO_BIT_INDEX);
260
261        inline_u64s[0].store(u64_0, Ordering::Relaxed);
262        inline_u16s[0].store(u16_0, Ordering::Relaxed);
263        inline_u8s[0].store(u8_0, Ordering::Relaxed);
264
265        let (chunks, _) = out_of_line_u64s.as_chunks::<{ XpermsBitmap::BITMAP_BLOCKS }>();
266        value.allow.to_atomics(&chunks[0]);
267        value.audit.to_atomics(&chunks[1]);
268    }
269}
270
271#[derive(Default)]
272pub(super) struct SidCacheStorage;
273
274/// Storage for a SID cache entry. We store the two sids (4 bytes each) in a u64, the class in a
275/// u8, and the resulting SID in an u32.
276impl
277    StorageStrategy<
278        /* u64 = */ 1,
279        /* u32 = */ 1,
280        /* u16 = */ 0,
281        /* u8 = */ 1,
282        /* out_of_line_u64s = */ 0,
283    > for SidCacheStorage
284{
285    type Key = AccessQueryArgs;
286    type Value = SecurityId;
287
288    #[inline(always)]
289    fn hash_key(&self, key: &Self::Key) -> u64 {
290        rapidhash::rapidhash(key.as_bytes())
291    }
292
293    #[inline(always)]
294    fn check_key(
295        &self,
296        key: &Self::Key,
297        inline_u64s: &[AtomicU64; 1],
298        _inline_u32s: &[AtomicU32; 1],
299        _inline_u16s: &[AtomicU16; 0],
300        inline_u8s: &[AtomicU8; 1],
301        _out_of_line_u64s: &[AtomicU64; 0],
302    ) -> bool {
303        inline_u8s[0].load(Ordering::Relaxed) == key.target_class as u8
304            && inline_u64s[0].load(Ordering::Relaxed)
305                == (key.source_sid.0.get() as u64 | (key.target_sid.0.get() as u64) << 32)
306    }
307
308    #[inline(always)]
309    fn read_value(
310        &self,
311        _inline_u64s: &[AtomicU64; 1],
312        inline_u32s: &[AtomicU32; 1],
313        _inline_u16s: &[AtomicU16; 0],
314        _inline_u8s: &[AtomicU8; 1],
315        _out_of_line_u64s: &[AtomicU64; 0],
316    ) -> Self::Value {
317        let u32_val = inline_u32s[0].load(Ordering::Relaxed);
318        SecurityId(std::num::NonZeroU32::new(u32_val).unwrap_or(std::num::NonZeroU32::MIN))
319    }
320
321    #[inline(always)]
322    fn write_key_value(
323        &self,
324        key: &Self::Key,
325        value: &Self::Value,
326        inline_u64s: &[AtomicU64; 1],
327        inline_u32s: &[AtomicU32; 1],
328        _inline_u16s: &[AtomicU16; 0],
329        inline_u8s: &[AtomicU8; 1],
330        _out_of_line_u64s: &[AtomicU64; 0],
331    ) {
332        let source_sid = key.source_sid.0.get() as u64;
333        let target_sid = key.target_sid.0.get() as u64;
334        let target_class = key.target_class.clone() as u8;
335        let value_sid = value.0.get() as u32;
336
337        let u64_0 = source_sid | (target_sid << 32);
338
339        inline_u64s[0].store(u64_0, Ordering::Relaxed);
340        inline_u32s[0].store(value_sid, Ordering::Relaxed);
341        inline_u8s[0].store(target_class, Ordering::Relaxed);
342    }
343}
344
345#[cfg(test)]
346mod tests {
347    use super::*;
348    use crate::kernel::{DirPermission, KernelClass, KernelPermission};
349    use crate::policy::{AccessVector, XpermsBitmap};
350
351    #[test]
352    fn test_access_cache_storage_roundtrip() {
353        let key = AccessQueryArgs {
354            source_sid: SecurityId(1.try_into().unwrap()),
355            target_sid: SecurityId(2.try_into().unwrap()),
356            target_class: KernelClass::File,
357        };
358        let value = KernelAccessDecision {
359            allow: AccessVector::from(4),
360            audit: AccessVector::from(5),
361            flags: 42,
362            todo_bug: Some(12345.try_into().unwrap()),
363        };
364
365        let inline_u64s = std::array::from_fn(|_| AtomicU64::new(0));
366        let inline_u32s = std::array::from_fn(|_| AtomicU32::new(0));
367        let inline_u16s = std::array::from_fn(|_| AtomicU16::new(0));
368        let inline_u8s = std::array::from_fn(|_| AtomicU8::new(0));
369        let out_of_line_u64s = std::array::from_fn(|_| AtomicU64::new(0));
370
371        AccessCacheStorage::default().write_key_value(
372            &key,
373            &value,
374            &inline_u64s,
375            &inline_u32s,
376            &inline_u16s,
377            &inline_u8s,
378            &out_of_line_u64s,
379        );
380
381        assert!(AccessCacheStorage::default().check_key(
382            &key,
383            &inline_u64s,
384            &inline_u32s,
385            &inline_u16s,
386            &inline_u8s,
387            &out_of_line_u64s,
388        ));
389
390        let read_val = AccessCacheStorage::default().read_value(
391            &inline_u64s,
392            &inline_u32s,
393            &inline_u16s,
394            &inline_u8s,
395            &out_of_line_u64s,
396        );
397
398        assert_eq!(read_val, value);
399    }
400
401    #[test]
402    fn test_xperms_access_cache_storage_roundtrip() {
403        let key = XpermsAccessQueryArgs {
404            xperms_kind: XpermsKind::Ioctl,
405            source_sid: SecurityId(1.try_into().unwrap()),
406            target_sid: SecurityId(2.try_into().unwrap()),
407            permission: KernelPermission::Dir(DirPermission::AddName),
408            xperms_prefix: 0,
409        };
410        let value = KernelXpermsAccessDecision {
411            allow: XpermsBitmap::NONE,
412            audit: XpermsBitmap::NONE,
413            permissive: false,
414            has_todo: true,
415        };
416
417        let inline_u64s = std::array::from_fn(|_| AtomicU64::new(0));
418        let inline_u32s = std::array::from_fn(|_| AtomicU32::new(0));
419        let inline_u16s = std::array::from_fn(|_| AtomicU16::new(0));
420        let inline_u8s = std::array::from_fn(|_| AtomicU8::new(0));
421        let out_of_line_u64s = std::array::from_fn(|_| AtomicU64::new(0));
422
423        XpermsAccessCacheStorage::default().write_key_value(
424            &key,
425            &value,
426            &inline_u64s,
427            &inline_u32s,
428            &inline_u16s,
429            &inline_u8s,
430            &out_of_line_u64s,
431        );
432
433        assert!(XpermsAccessCacheStorage::default().check_key(
434            &key,
435            &inline_u64s,
436            &inline_u32s,
437            &inline_u16s,
438            &inline_u8s,
439            &out_of_line_u64s,
440        ));
441
442        let read_val = XpermsAccessCacheStorage::default().read_value(
443            &inline_u64s,
444            &[],
445            &inline_u16s,
446            &inline_u8s,
447            &out_of_line_u64s,
448        );
449
450        assert_eq!(read_val, value);
451    }
452
453    #[test]
454    fn test_sid_cache_storage_roundtrip() {
455        let key = AccessQueryArgs {
456            source_sid: SecurityId(1.try_into().unwrap()),
457            target_sid: SecurityId(2.try_into().unwrap()),
458            target_class: KernelClass::Process,
459        };
460        let value = SecurityId(3.try_into().unwrap());
461
462        let inline_u64s = std::array::from_fn(|_| AtomicU64::new(0));
463        let inline_u32s = std::array::from_fn(|_| AtomicU32::new(0));
464        let inline_u16s = std::array::from_fn(|_| AtomicU16::new(0));
465        let inline_u8s = std::array::from_fn(|_| AtomicU8::new(0));
466        let out_of_line_u64s = std::array::from_fn(|_| AtomicU64::new(0));
467
468        SidCacheStorage::default().write_key_value(
469            &key,
470            &value,
471            &inline_u64s,
472            &inline_u32s,
473            &inline_u16s,
474            &inline_u8s,
475            &out_of_line_u64s,
476        );
477
478        assert!(SidCacheStorage::default().check_key(
479            &key,
480            &inline_u64s,
481            &inline_u32s,
482            &inline_u16s,
483            &inline_u8s,
484            &out_of_line_u64s,
485        ));
486
487        let read_val = SidCacheStorage::default().read_value(
488            &inline_u64s,
489            &inline_u32s,
490            &inline_u16s,
491            &inline_u8s,
492            &out_of_line_u64s,
493        );
494
495        assert_eq!(read_val, value);
496    }
497
498    #[test]
499    fn test_access_cache_bucket_size() {
500        // The access cache packs 4 entries in 128 bytes.
501        assert_eq!(ConcurrentAccessCache::bucket_size(), 128);
502    }
503
504    #[test]
505    fn test_xperms_cache_bucket_size() {
506        // The xperms cache packs 4 entries in 64 bytes (and stores the rest out-of-line).
507        assert_eq!(ConcurrentXpermsCache::bucket_size(), 64);
508    }
509
510    #[test]
511    fn test_sid_cache_bucket_size() {
512        // The SID cache packs 8 entries in 128 bytes.
513        assert_eq!(ConcurrentSidCache::bucket_size(), 128);
514    }
515}
selinux/kernel/avc/concurrent_access_cache.rs

selinux/kernel/avc/
concurrent_access_cache.rs
