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, 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 mut allow_u64s = [0u64; 4];
233        let mut audit_u64s = [0u64; 4];
234
235        for i in 0..4 {
236            allow_u64s[i] = out_of_line_u64s[i].load(Ordering::Relaxed);
237            audit_u64s[i] = out_of_line_u64s[i + 4].load(Ordering::Relaxed);
238        }
239
240        let allow = allow_u64s.into();
241        let audit = audit_u64s.into();
242
243        KernelXpermsAccessDecision { allow, audit, permissive, has_todo }
244    }
245
246    #[inline(always)]
247    fn write_key_value(
248        &self,
249        key: &Self::Key,
250        value: &Self::Value,
251        inline_u64s: &[AtomicU64; 1],
252        _inline_u32s: &[AtomicU32; 0],
253        inline_u16s: &[AtomicU16; 1],
254        inline_u8s: &[AtomicU8; 1],
255        out_of_line_u64s: &[AtomicU64; 8],
256    ) {
257        let source_sid = key.source_sid.0.get() as u64;
258        let target_sid = key.target_sid.0.get() as u64;
259        let class = key.permission.class() as u16;
260        let xperms_prefix = key.xperms_prefix as u16;
261        let permission_id = key.permission.id() as u8;
262        let xperms_kind_bit = match key.xperms_kind {
263            XpermsKind::Ioctl => 0,
264            XpermsKind::Nlmsg => 1,
265        };
266
267        let u64_0 = source_sid | (target_sid << 32);
268        let u16_0 = class | (xperms_prefix << 8);
269        let u8_0 = permission_id
270            | (xperms_kind_bit << Self::XPERMS_KIND_BIT_INDEX)
271            | ((value.permissive as u8) << Self::PERMISSIVE_BIT_INDEX)
272            | ((value.has_todo as u8) << Self::HAS_TODO_BIT_INDEX);
273
274        inline_u64s[0].store(u64_0, Ordering::Relaxed);
275        inline_u16s[0].store(u16_0, Ordering::Relaxed);
276        inline_u8s[0].store(u8_0, Ordering::Relaxed);
277
278        let allow_u64s: [u64; 4] = value.allow.into();
279        let audit_u64s: [u64; 4] = value.audit.into();
280
281        for i in 0..4 {
282            out_of_line_u64s[i].store(allow_u64s[i], Ordering::Relaxed);
283            out_of_line_u64s[i + 4].store(audit_u64s[i], Ordering::Relaxed);
284        }
285    }
286}
287
288#[derive(Default)]
289pub(super) struct SidCacheStorage;
290
291/// Storage for a SID cache entry. We store the two sids (4 bytes each) in a u64, the class in a
292/// u8, and the resulting SID in an u32.
293impl
294    StorageStrategy<
295        /*u64*/ 1,
296        /*u32*/ 1,
297        /*u16*/ 0,
298        /*u8*/ 1,
299        /*out_of_line_u64s*/ 0,
300    > for SidCacheStorage
301{
302    type Key = AccessQueryArgs;
303    type Value = SecurityId;
304
305    #[inline(always)]
306    fn hash_key(&self, key: &Self::Key) -> u64 {
307        rapidhash::rapidhash(key.as_bytes())
308    }
309
310    #[inline(always)]
311    fn check_key(
312        &self,
313        key: &Self::Key,
314        inline_u64s: &[AtomicU64; 1],
315        _inline_u32s: &[AtomicU32; 1],
316        _inline_u16s: &[AtomicU16; 0],
317        inline_u8s: &[AtomicU8; 1],
318        _out_of_line_u64s: &[AtomicU64; 0],
319    ) -> bool {
320        inline_u8s[0].load(Ordering::Relaxed) == key.target_class as u8
321            && inline_u64s[0].load(Ordering::Relaxed)
322                == (key.source_sid.0.get() as u64 | (key.target_sid.0.get() as u64) << 32)
323    }
324
325    #[inline(always)]
326    fn read_value(
327        &self,
328        _inline_u64s: &[AtomicU64; 1],
329        inline_u32s: &[AtomicU32; 1],
330        _inline_u16s: &[AtomicU16; 0],
331        _inline_u8s: &[AtomicU8; 1],
332        _out_of_line_u64s: &[AtomicU64; 0],
333    ) -> Self::Value {
334        let u32_val = inline_u32s[0].load(Ordering::Relaxed);
335        SecurityId(std::num::NonZeroU32::new(u32_val).unwrap())
336    }
337
338    #[inline(always)]
339    fn write_key_value(
340        &self,
341        key: &Self::Key,
342        value: &Self::Value,
343        inline_u64s: &[AtomicU64; 1],
344        inline_u32s: &[AtomicU32; 1],
345        _inline_u16s: &[AtomicU16; 0],
346        inline_u8s: &[AtomicU8; 1],
347        _out_of_line_u64s: &[AtomicU64; 0],
348    ) {
349        let source_sid = key.source_sid.0.get() as u64;
350        let target_sid = key.target_sid.0.get() as u64;
351        let target_class = key.target_class.clone() as u8;
352        let value_sid = value.0.get() as u32;
353
354        let u64_0 = source_sid | (target_sid << 32);
355
356        inline_u64s[0].store(u64_0, Ordering::Relaxed);
357        inline_u32s[0].store(value_sid, Ordering::Relaxed);
358        inline_u8s[0].store(target_class, Ordering::Relaxed);
359    }
360}
361
362#[cfg(test)]
363mod tests {
364    use super::*;
365    use crate::kernel_permissions::{DirPermission, KernelClass, KernelPermission};
366    use crate::policy::{AccessVector, XpermsBitmap};
367
368    #[test]
369    fn test_access_cache_storage_roundtrip() {
370        let key = AccessQueryArgs {
371            source_sid: SecurityId(1.try_into().unwrap()),
372            target_sid: SecurityId(2.try_into().unwrap()),
373            target_class: KernelClass::File,
374        };
375        let value = KernelAccessDecision {
376            allow: AccessVector::from(4),
377            audit: AccessVector::from(5),
378            flags: 42,
379            todo_bug: Some(12345.try_into().unwrap()),
380        };
381
382        let inline_u64s = std::array::from_fn(|_| AtomicU64::new(0));
383        let inline_u32s = std::array::from_fn(|_| AtomicU32::new(0));
384        let inline_u16s = std::array::from_fn(|_| AtomicU16::new(0));
385        let inline_u8s = std::array::from_fn(|_| AtomicU8::new(0));
386        let out_of_line_u64s = std::array::from_fn(|_| AtomicU64::new(0));
387
388        AccessCacheStorage::default().write_key_value(
389            &key,
390            &value,
391            &inline_u64s,
392            &inline_u32s,
393            &inline_u16s,
394            &inline_u8s,
395            &out_of_line_u64s,
396        );
397
398        assert!(AccessCacheStorage::default().check_key(
399            &key,
400            &inline_u64s,
401            &inline_u32s,
402            &inline_u16s,
403            &inline_u8s,
404            &out_of_line_u64s,
405        ));
406
407        let read_val = AccessCacheStorage::default().read_value(
408            &inline_u64s,
409            &inline_u32s,
410            &inline_u16s,
411            &inline_u8s,
412            &out_of_line_u64s,
413        );
414
415        assert_eq!(read_val, value);
416    }
417
418    #[test]
419    fn test_xperms_access_cache_storage_roundtrip() {
420        let key = XpermsAccessQueryArgs {
421            xperms_kind: XpermsKind::Ioctl,
422            source_sid: SecurityId(1.try_into().unwrap()),
423            target_sid: SecurityId(2.try_into().unwrap()),
424            permission: KernelPermission::Dir(DirPermission::AddName),
425            xperms_prefix: 0,
426        };
427        let value = KernelXpermsAccessDecision {
428            allow: XpermsBitmap::NONE,
429            audit: XpermsBitmap::NONE,
430            permissive: false,
431            has_todo: true,
432        };
433
434        let inline_u64s = std::array::from_fn(|_| AtomicU64::new(0));
435        let inline_u32s = std::array::from_fn(|_| AtomicU32::new(0));
436        let inline_u16s = std::array::from_fn(|_| AtomicU16::new(0));
437        let inline_u8s = std::array::from_fn(|_| AtomicU8::new(0));
438        let out_of_line_u64s = std::array::from_fn(|_| AtomicU64::new(0));
439
440        XpermsAccessCacheStorage::default().write_key_value(
441            &key,
442            &value,
443            &inline_u64s,
444            &inline_u32s,
445            &inline_u16s,
446            &inline_u8s,
447            &out_of_line_u64s,
448        );
449
450        assert!(XpermsAccessCacheStorage::default().check_key(
451            &key,
452            &inline_u64s,
453            &inline_u32s,
454            &inline_u16s,
455            &inline_u8s,
456            &out_of_line_u64s,
457        ));
458
459        let read_val = XpermsAccessCacheStorage::default().read_value(
460            &inline_u64s,
461            &[],
462            &inline_u16s,
463            &inline_u8s,
464            &out_of_line_u64s,
465        );
466
467        assert_eq!(read_val, value);
468    }
469
470    #[test]
471    fn test_sid_cache_storage_roundtrip() {
472        let key = AccessQueryArgs {
473            source_sid: SecurityId(1.try_into().unwrap()),
474            target_sid: SecurityId(2.try_into().unwrap()),
475            target_class: KernelClass::Process,
476        };
477        let value = SecurityId(3.try_into().unwrap());
478
479        let inline_u64s = std::array::from_fn(|_| AtomicU64::new(0));
480        let inline_u32s = std::array::from_fn(|_| AtomicU32::new(0));
481        let inline_u16s = std::array::from_fn(|_| AtomicU16::new(0));
482        let inline_u8s = std::array::from_fn(|_| AtomicU8::new(0));
483        let out_of_line_u64s = std::array::from_fn(|_| AtomicU64::new(0));
484
485        SidCacheStorage::default().write_key_value(
486            &key,
487            &value,
488            &inline_u64s,
489            &inline_u32s,
490            &inline_u16s,
491            &inline_u8s,
492            &out_of_line_u64s,
493        );
494
495        assert!(SidCacheStorage::default().check_key(
496            &key,
497            &inline_u64s,
498            &inline_u32s,
499            &inline_u16s,
500            &inline_u8s,
501            &out_of_line_u64s,
502        ));
503
504        let read_val = SidCacheStorage::default().read_value(
505            &inline_u64s,
506            &inline_u32s,
507            &inline_u16s,
508            &inline_u8s,
509            &out_of_line_u64s,
510        );
511
512        assert_eq!(read_val, value);
513    }
514
515    #[test]
516    fn test_access_cache_bucket_size() {
517        // The access cache packs 4 entries in 128 bytes.
518        assert_eq!(ConcurrentAccessCache::bucket_size(), 128);
519    }
520
521    #[test]
522    fn test_xperms_cache_bucket_size() {
523        // The xperms cache packs 4 entries in 64 bytes (and stores the rest out-of-line).
524        assert_eq!(ConcurrentXpermsCache::bucket_size(), 64);
525    }
526
527    #[test]
528    fn test_sid_cache_bucket_size() {
529        // The SID cache packs 8 entries in 128 bytes.
530        assert_eq!(ConcurrentSidCache::bucket_size(), 128);
531    }
532}
selinux/concurrent_access_cache.rs

selinux/
concurrent_access_cache.rs
