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

selinux/kernel/avc/
concurrent_access_cache.rs
