selinux/policy/
view.rs

1// Copyright 2025 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::arrays::SimpleArrayView;
6use super::parser::{PolicyCursor, PolicyData, PolicyOffset};
7use super::{Counted, Parse, PolicyValidationContext, Validate};
8
9use hashbrown::hash_table::HashTable;
10use rapidhash::RapidHasher;
11use static_assertions::const_assert;
12use std::fmt::Debug;
13use std::hash::{Hash, Hasher};
14use std::marker::PhantomData;
15use zerocopy::{FromBytes, Immutable, KnownLayout, Unaligned, little_endian as le};
16
17/// A trait for types that have metadata.
18///
19/// Many policy objects have a fixed-sized metadata section that is much faster to parse than the
20/// full object. This trait is used when walking the binary policy to find objects of interest
21/// efficiently.
22pub trait HasMetadata {
23    /// The Rust type that represents the metadata.
24    type Metadata: FromBytes + Sized;
25}
26
27/// A trait for types that can be walked through the policy data.
28///
29/// This trait is used when walking the binary policy to find objects of interest efficiently.
30pub trait Walk {
31    /// Walks the policy data to the next object of the given type.
32    ///
33    /// Returns an error if the cursor cannot be walked to the next object of the given type.
34    fn walk(policy_data: &PolicyData, offset: PolicyOffset) -> PolicyOffset;
35}
36
37/// A view into a policy object.
38///
39/// This struct contains the start and end offsets of the object in the policy data. To read the
40/// object, use [`View::read`].
41#[derive(Debug, Clone, Copy)]
42pub struct View<T> {
43    phantom: PhantomData<T>,
44
45    /// The start offset of the object in the policy data.
46    start: PolicyOffset,
47
48    /// The end offset of the object in the policy data.
49    end: PolicyOffset,
50}
51
52impl<T> View<T> {
53    /// Creates a new view from the start and end offsets.
54    pub fn new(start: PolicyOffset, end: PolicyOffset) -> Self {
55        Self { phantom: PhantomData, start, end }
56    }
57
58    /// The start offset of the object in the policy data.
59    fn start(&self) -> PolicyOffset {
60        self.start
61    }
62}
63
64impl<T: Sized> View<T> {
65    /// Creates a new view at the given start offset.
66    ///
67    /// The end offset is calculated as the start offset plus the size of the object.
68    pub fn at(start: PolicyOffset) -> Self {
69        let end = start + std::mem::size_of::<T>() as u32;
70        Self::new(start, end)
71    }
72}
73
74impl<T: FromBytes + Sized> View<T> {
75    /// Reads the object from the policy data.
76    ///
77    /// This function requires the object to have a fixed size and simply copies the object from
78    /// the policy data.
79    ///
80    /// For variable-sized objects, use [`View::parse`] instead.
81    pub fn read(&self, policy_data: &PolicyData) -> T {
82        debug_assert_eq!(self.end - self.start, std::mem::size_of::<T>() as u32);
83        let start = self.start as usize;
84        let end = self.end as usize;
85        T::read_from_bytes(&policy_data[start..end]).unwrap()
86    }
87}
88
89impl<T: HasMetadata> View<T> {
90    /// Returns a view into the metadata of the object.
91    ///
92    /// Assumes the metadata is at the start of the object.
93    pub fn metadata(&self) -> View<T::Metadata> {
94        View::<T::Metadata>::at(self.start)
95    }
96
97    /// Reads the metadata from the policy data.
98    pub fn read_metadata(&self, policy_data: &PolicyData) -> T::Metadata {
99        self.metadata().read(policy_data)
100    }
101}
102
103impl<T: Parse> View<T> {
104    /// Parses the object from the policy data.
105    ///
106    /// This function uses the [`Parse`] trait to parse the object from the policy data.
107    ///
108    /// If the object has a fixed size, prefer [`View::read`] instead.
109    pub fn parse(&self, policy_data: &PolicyData) -> T {
110        let cursor = PolicyCursor::new_at(policy_data, self.start);
111        let (object, _) =
112            T::parse(cursor).map_err(Into::<anyhow::Error>::into).expect("policy should be valid");
113        object
114    }
115}
116
117impl<T: Validate + Parse> Validate for View<T> {
118    type Error = anyhow::Error;
119
120    fn validate(&self, context: &PolicyValidationContext) -> Result<(), Self::Error> {
121        let object = self.parse(&context.data);
122        object.validate(context).map_err(Into::<anyhow::Error>::into)
123    }
124}
125
126/// A view into the data of an array of objects.
127///
128/// This struct contains the start offset of the array and the number of objects in the array.
129/// To iterate over the objects, use [`ArrayDataView::iter`].
130#[derive(Debug, Clone, Copy)]
131pub struct ArrayDataView<D> {
132    phantom: PhantomData<D>,
133    start: PolicyOffset,
134    count: u32,
135}
136
137impl<D> ArrayDataView<D> {
138    /// Creates a new array data view from the start offset and count.
139    pub fn new(start: PolicyOffset, count: u32) -> Self {
140        Self { phantom: PhantomData, start, count }
141    }
142
143    /// Iterates over the objects in the array.
144    ///
145    /// The iterator returns views into the objects in the array.
146    ///
147    /// This function requires the policy data to be provided to the iterator because objects in
148    /// the array may have variable size.
149    pub fn iter(self, policy_data: &PolicyData) -> ArrayDataViewIter<D> {
150        ArrayDataViewIter::new(policy_data.clone(), self.start, self.count)
151    }
152}
153
154/// An iterator over the objects in an array.
155///
156/// This struct contains the cursor to the start of the array and the number of objects remaining
157/// to be iterated over.
158pub struct ArrayDataViewIter<D> {
159    phantom: PhantomData<D>,
160    policy_data: PolicyData,
161    offset: PolicyOffset,
162    remaining: u32,
163}
164
165impl<T> ArrayDataViewIter<T> {
166    /// Creates a new array data view iterator from the start cursor and remaining count.
167    fn new(policy_data: PolicyData, offset: PolicyOffset, remaining: u32) -> Self {
168        Self { phantom: PhantomData, policy_data, offset, remaining }
169    }
170}
171
172impl<D: Walk> std::iter::Iterator for ArrayDataViewIter<D> {
173    type Item = View<D>;
174
175    fn next(&mut self) -> Option<Self::Item> {
176        if self.remaining > 0 {
177            let start = self.offset;
178            self.offset = D::walk(&self.policy_data, start);
179            self.remaining -= 1;
180            Some(View::new(start, self.offset))
181        } else {
182            None
183        }
184    }
185}
186
187/// A view into the data of an array of objects.
188///
189/// This struct contains the start offset of the array and the number of objects in the array.
190/// To access the objects in the array, use [`ArrayView::data`].
191#[derive(Debug, Clone, Copy)]
192pub(super) struct ArrayView<M, D> {
193    phantom: PhantomData<(M, D)>,
194    start: PolicyOffset,
195    count: u32,
196}
197
198impl<M, D> ArrayView<M, D> {
199    /// Creates a new array view from the start offset and count.
200    pub fn new(start: PolicyOffset, count: u32) -> Self {
201        Self { phantom: PhantomData, start, count }
202    }
203}
204
205impl<M: Sized, D> ArrayView<M, D> {
206    /// Returns a view into the metadata of the array.
207    pub fn metadata(&self) -> View<M> {
208        View::<M>::at(self.start)
209    }
210
211    /// Returns a view into the data of the array.
212    pub fn data(&self) -> ArrayDataView<D> {
213        ArrayDataView::new(self.metadata().end, self.count)
214    }
215}
216
217fn parse_array_data<'a, D: Parse>(
218    cursor: PolicyCursor<'a>,
219    count: u32,
220) -> Result<PolicyCursor<'a>, anyhow::Error> {
221    let mut tail = cursor;
222    for _ in 0..count {
223        let (_, next) = D::parse(tail).map_err(Into::<anyhow::Error>::into)?;
224        tail = next;
225    }
226    Ok(tail)
227}
228
229impl<M: Counted + Parse + Sized, D: Parse> Parse for ArrayView<M, D> {
230    /// [`ArrayView`] abstracts over two types (`M` and `D`) that may have different [`Parse::Error`]
231    /// types. Unify error return type via [`anyhow::Error`].
232    type Error = anyhow::Error;
233
234    fn parse<'a>(cursor: PolicyCursor<'a>) -> Result<(Self, PolicyCursor<'a>), Self::Error> {
235        let start = cursor.offset();
236        let (metadata, cursor) = M::parse(cursor).map_err(Into::<anyhow::Error>::into)?;
237        let count = metadata.count();
238        let cursor = parse_array_data::<D>(cursor, count)?;
239        Ok((Self::new(start, count), cursor))
240    }
241}
242
243/// A trait for types that can be used as keys in a hash table.
244///
245/// This trait is used by [`HashedBlocksView`] to store and retrieve values.
246pub(super) trait Hashable {
247    type Key: Parse + Hash + Eq;
248    type Value: Parse + Walk;
249
250    /// Returns a reference to the key.
251    fn key(&self) -> &Self::Key;
252
253    /// Returns a [`SimpleArrayView`] into the values.
254    fn values(&self) -> &SimpleArrayView<Self::Value>;
255}
256
257/// Stores an mapping from a [`D::Key`] to a set of [`D::Value`]s
258#[derive(Debug, Clone)]
259pub(super) struct CustomKeyHashedView<D: Hashable> {
260    /// Stores the offset to D::Key.
261    index: HashTable<PolicyOffset>,
262    _phantom: PhantomData<D>,
263}
264
265impl<D: Hashable + Parse> CustomKeyHashedView<D> {
266    /// Returns an iterator over the entries with the specified `key` and parses and
267    /// emits those values.
268    pub(super) fn find_all(
269        &self,
270        query_key: D::Key,
271        policy_data: &PolicyData,
272    ) -> impl Iterator<Item = D::Value> {
273        let key_offset = self.index.find(compute_hash(&query_key), |&key_offset| {
274            let cursor = PolicyCursor::new_at(policy_data, key_offset);
275            let (key, _) = D::Key::parse(cursor)
276                .map_err(Into::<anyhow::Error>::into)
277                .expect("policy should be valid");
278
279            key == query_key
280        });
281
282        key_offset.into_iter().flat_map(move |&key_offset| {
283            let cursor = PolicyCursor::new_at(policy_data, key_offset);
284            let (entry, _) = D::parse(cursor)
285                .map_err(Into::<anyhow::Error>::into)
286                .expect("policy should be valid");
287
288            entry.values().data().iter(policy_data).map(move |v| v.parse(policy_data))
289        })
290    }
291
292    pub(super) fn iter<'a>(
293        &'a self,
294        policy_data: &'a PolicyData,
295    ) -> impl Iterator<Item = Result<D, anyhow::Error>> + 'a {
296        self.index.iter().map(move |&offset| {
297            let cursor = PolicyCursor::new_at(policy_data, offset);
298            let (entry, _) = D::parse(cursor).map_err(Into::<anyhow::Error>::into)?;
299            Ok(entry)
300        })
301    }
302}
303
304fn compute_hash<V: Hash>(val: &V) -> u64 {
305    let mut hasher = RapidHasher::default();
306    val.hash(&mut hasher);
307    hasher.finish()
308}
309
310impl<D: Hashable + Parse> Parse for CustomKeyHashedView<D> {
311    type Error = anyhow::Error;
312
313    /// Parses (D::Key, SimpleArrayView<D::Value>) entries and stores the keys into a CustomKeyHashedView.
314    fn parse<'a>(cursor: PolicyCursor<'a>) -> Result<(Self, PolicyCursor<'a>), Self::Error> {
315        // Parse the count of entries.
316        let (metadata, cursor) = le::U32::parse(cursor).map_err(Into::<anyhow::Error>::into)?;
317        let count = metadata.count();
318
319        // The index will store [`count`] entries. Reserve the necessary capacity ahead to avoid resizing later on.
320        let mut index = HashTable::with_capacity(count as usize);
321
322        let mut key_offset = cursor.offset();
323        let mut tail = cursor;
324        for _ in 0..count {
325            let (entry, next) = D::parse(tail).map_err(Into::<anyhow::Error>::into)?;
326            tail = next;
327
328            let key: &D::Key = entry.key();
329            index.insert_unique(compute_hash(&key), key_offset, |&key_offset| {
330                let policy_cursor = PolicyCursor::new_at(tail.data(), key_offset);
331                let (key, _) = D::Key::parse(policy_cursor)
332                    .map_err(Into::<anyhow::Error>::into)
333                    .expect("policy should be valid");
334                compute_hash::<D::Key>(&key)
335            });
336            key_offset = tail.offset();
337        }
338
339        Ok((Self { _phantom: PhantomData, index }, tail))
340    }
341}
342
343impl<D: Hashable + Parse> Validate for CustomKeyHashedView<D>
344where
345    SimpleArrayView<D::Value>: Validate<Error = anyhow::Error>,
346{
347    type Error = anyhow::Error;
348
349    fn validate(&self, context: &PolicyValidationContext) -> Result<(), Self::Error> {
350        for key_offset in self.index.iter() {
351            let cursor = PolicyCursor::new_at(&context.data, *key_offset);
352            let (entry, _) = D::parse(cursor).map_err(Into::<anyhow::Error>::into)?;
353
354            entry.values().validate(context)?;
355        }
356        Ok(())
357    }
358}
359
360/// An iterator giving views of the objects in the underlying [`policy_data`] found from
361/// a single entry of a `HashedArrayView`.
362struct HashedArrayViewEntryIter<'a, D: HasMetadata> {
363    policy_data: &'a PolicyData,
364    limit: PolicyOffset,
365    metadata: D::Metadata,
366    offset: Option<PolicyOffset>,
367}
368
369/// An unsigned integer in the range [0, 0x1000000) stored in three unaligned bytes.
370//
371// TODO: https://fxbug.dev/479180246 - it would be better to get this type from a library
372// somewhere. Probably not https://docs.rs/u24 (because of "The type has the same size,
373// alignment, and memory layout as a little-endian encoded u32" in that implementation's
374// specification). But maybe from somewhere else?
375#[derive(Clone, Copy, Debug, KnownLayout, FromBytes, Immutable, PartialEq, Unaligned)]
376#[repr(C, packed)]
377pub(super) struct U24 {
378    low: u8,
379    middle: u8,
380    high: u8,
381}
382
383// U24's space-efficiency is its reason for existence.
384const_assert!(std::mem::size_of::<U24>() == 3);
385const_assert!(std::mem::align_of::<U24>() == 1);
386
387impl U24 {
388    /// The zero value.
389    pub const ZERO: Self = Self { low: 0, middle: 0, high: 0 };
390}
391
392impl TryFrom<u32> for U24 {
393    type Error = ();
394
395    fn try_from(value: u32) -> Result<Self, Self::Error> {
396        if 0x1000000 <= value {
397            Err(())
398        } else {
399            Ok(Self {
400                low: (value & 0xff) as u8,
401                middle: ((value >> 8) & 0xff) as u8,
402                high: ((value >> 16) & 0xff) as u8,
403            })
404        }
405    }
406}
407
408impl From<U24> for u32 {
409    fn from(value: U24) -> u32 {
410        ((value.high as u32) << 16) + ((value.middle as u32) << 8) + (value.low as u32)
411    }
412}
413
414impl<'a, D: HasMetadata + Walk> Iterator for HashedArrayViewEntryIter<'a, D>
415where
416    D::Metadata: Eq,
417{
418    type Item = View<D>;
419
420    fn next(&mut self) -> Option<Self::Item> {
421        if let Some(offset) = self.offset
422            && offset < self.limit
423        {
424            let element = View::<D>::at(offset);
425            let metadata = element.read_metadata(&self.policy_data);
426            if metadata == self.metadata {
427                self.offset = Some(D::walk(&self.policy_data, offset));
428                Some(element)
429            } else {
430                self.offset = None;
431                None
432            }
433        } else {
434            None
435        }
436    }
437}
438
439/// A view into the data of an array of objects, with efficient lookup based on metadata hash.
440///
441/// This struct contains only a vector of offsets into the policy data, to allow efficient lookup
442/// of vector elements with matching metadata.
443#[derive(Debug, Clone)]
444pub(super) struct HashedArrayView<D: HasMetadata> {
445    phantom: PhantomData<D>,
446    index: HashTable<U24>,
447    /// The offset in the policy data at which the elements indexed by this [`HashedArrayView`]
448    /// end. Iteration of elements by this [`HashedArrayView`] must not look for an element at
449    /// or beyond this offset.
450    limit: PolicyOffset,
451}
452
453impl<D: HasMetadata> HashedArrayView<D>
454where
455    D::Metadata: Hash,
456{
457    fn metadata_hash(metadata: &D::Metadata) -> u64 {
458        let mut hasher = RapidHasher::default();
459        metadata.hash(&mut hasher);
460        hasher.finish()
461    }
462}
463
464impl<D: Parse + HasMetadata + Walk> HashedArrayView<D>
465where
466    D::Metadata: Eq + PartialEq + Hash + Debug,
467{
468    /// Looks up the entry with the specified metadata `key`, and parses and returns the value.
469    /// This method is only appropriate to call when expecting to find at most one entry for
470    /// `key`; if there is a possibility of more than one element in the underlying
471    /// `policy_data` being associated with `key`, call `find_all` instead.
472    pub fn find(&self, key: D::Metadata, policy_data: &PolicyData) -> Option<D> {
473        let key_hash = Self::metadata_hash(&key);
474        let offset = self.index.find(key_hash, |&offset| {
475            let element = View::<D>::at(u32::from(offset));
476            key == element.read_metadata(policy_data)
477        })?;
478        let element = View::<D>::at(u32::from(*offset));
479        Some(element.parse(policy_data))
480    }
481
482    /// Returns an iterator over the entries with the specified metadata `key` and parses and
483    /// emits those values.
484    pub(super) fn find_all(
485        &self,
486        key: D::Metadata,
487        policy_data: &PolicyData,
488    ) -> impl Iterator<Item = D> {
489        let key_hash = Self::metadata_hash(&key);
490        let offset = self.index.find(key_hash, |&offset| {
491            let element = View::<D>::at(u32::from(offset));
492            key == element.read_metadata(policy_data)
493        });
494        (HashedArrayViewEntryIter {
495            policy_data: policy_data,
496            limit: self.limit,
497            metadata: key,
498            offset: offset.map(|offset| u32::from(*offset)),
499        })
500        .map(|element| element.parse(policy_data))
501    }
502
503    /// Returns an iterator that emits a view for each reachable element.
504    pub(super) fn iter(&self, policy_data: &PolicyData) -> impl Iterator<Item = View<D>> {
505        self.index
506            .iter()
507            .map(|offset| {
508                let element = View::<D>::at(u32::from(*offset));
509                HashedArrayViewEntryIter {
510                    policy_data: policy_data,
511                    limit: self.limit,
512                    metadata: element.read_metadata(policy_data),
513                    offset: Some(u32::from(*offset)),
514                }
515            })
516            .flatten()
517    }
518}
519
520impl<D: Parse + HasMetadata + Walk> Parse for HashedArrayView<D>
521where
522    D::Metadata: Eq + Debug + PartialEq + Parse + Hash,
523{
524    type Error = anyhow::Error;
525
526    fn parse<'a>(cursor: PolicyCursor<'a>) -> Result<(Self, PolicyCursor<'a>), Self::Error> {
527        let (array_view, cursor) = SimpleArrayView::<D>::parse(cursor)?;
528
529        // Allocate a hash table sized appropriately for the array size.
530        let mut index = HashTable::with_capacity(array_view.count as usize);
531
532        // Record the offset at which the last array element ends.
533        let limit = cursor.offset();
534
535        // Iterate over the elements inserting the first offset at which each is
536        // seen into a hash bucket.
537        for view in array_view.data().iter(cursor.data()) {
538            let metadata = view.read_metadata(cursor.data());
539
540            index
541                .entry(
542                    Self::metadata_hash(&metadata),
543                    |&offset| {
544                        let element = View::<D>::at(u32::from(offset));
545                        metadata == element.read_metadata(cursor.data())
546                    },
547                    |&offset| {
548                        let element = View::<D>::at(u32::from(offset));
549                        Self::metadata_hash(&element.read_metadata(cursor.data()))
550                    },
551                )
552                .or_insert(U24::try_from(view.start()).expect("Policy offsets ought fit in U24!"));
553        }
554
555        Ok((Self { phantom: PhantomData, index, limit }, cursor))
556    }
557}
558
559impl<D: Validate + Parse + HasMetadata + Walk> Validate for HashedArrayView<D>
560where
561    D::Metadata: Eq,
562{
563    type Error = anyhow::Error;
564
565    fn validate(&self, context: &PolicyValidationContext) -> Result<(), Self::Error> {
566        let policy_data = context.data.clone();
567        for element in self
568            .index
569            .iter()
570            .map(|offset| {
571                let element = View::<D>::at(u32::from(*offset));
572                HashedArrayViewEntryIter::<D> {
573                    policy_data: &policy_data,
574                    limit: self.limit,
575                    metadata: element.read_metadata(&policy_data),
576                    offset: Some(u32::from(*offset)),
577                }
578            })
579            .flatten()
580        {
581            element.validate(context)?;
582        }
583
584        Ok(())
585    }
586}
587
588#[cfg(test)]
589mod tests {
590    use super::U24;
591
592    #[test]
593    fn to_and_from_u24() {
594        for i in 0u32..0x10000 {
595            let u24_result = U24::try_from(i);
596            assert!(u24_result.is_ok());
597            let u24 = u24_result.unwrap();
598            assert_eq!(i >> 16, u24.high as u32);
599            assert_eq!((i >> 8) & 0xff, u24.middle as u32);
600            assert_eq!(i & 0xff, u24.low as u32);
601            let j = u32::from(u24);
602            assert_eq!(i, j);
603        }
604
605        assert!(U24::try_from(0x1000000).is_err());
606    }
607}
selinux/policy/view.rs

selinux/policy/
view.rs
