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

selinux/
concurrent_access_cache.rs
