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::PolicyValidationContext;
6use super::parser::{PolicyCursor, PolicyData, PolicyOffset};
7use crate::policy::{Counted, Parse, Validate};
8use hashbrown::hash_table::HashTable;
9use std::fmt::Debug;
10use std::hash::{DefaultHasher, Hash, Hasher};
11use std::marker::PhantomData;
12use std::ops::Deref;
13use zerocopy::FromBytes;
14
15/// A trait for types that have metadata.
16///
17/// Many policy objects have a fixed-sized metadata section that is much faster to parse than the
18/// full object. This trait is used when walking the binary policy to find objects of interest
19/// efficiently.
20pub trait HasMetadata {
21    /// The Rust type that represents the metadata.
22    type Metadata: FromBytes + Sized;
23}
24
25/// A trait for types that can be walked through the policy data.
26///
27/// This trait is used when walking the binary policy to find objects of interest efficiently.
28pub trait Walk {
29    /// Walks the policy data to the next object of the given type.
30    ///
31    /// Returns an error if the cursor cannot be walked to the next object of the given type.
32    fn walk(policy_data: &PolicyData, offset: PolicyOffset) -> PolicyOffset;
33}
34
35/// A view into a policy object.
36///
37/// This struct contains the start and end offsets of the object in the policy data. To read the
38/// object, use [`View::read`].
39#[derive(Debug, Clone, Copy)]
40pub struct View<T> {
41    phantom: PhantomData<T>,
42
43    /// The start offset of the object in the policy data.
44    start: PolicyOffset,
45
46    /// The end offset of the object in the policy data.
47    end: PolicyOffset,
48}
49
50impl<T> View<T> {
51    /// Creates a new view from the start and end offsets.
52    pub fn new(start: PolicyOffset, end: PolicyOffset) -> Self {
53        Self { phantom: PhantomData, start, end }
54    }
55}
56
57impl<T: Sized> View<T> {
58    /// Creates a new view at the given start offset.
59    ///
60    /// The end offset is calculated as the start offset plus the size of the object.
61    pub fn at(start: PolicyOffset) -> Self {
62        let end = start + std::mem::size_of::<T>() as u32;
63        Self::new(start, end)
64    }
65}
66
67impl<T: FromBytes + Sized> View<T> {
68    /// Reads the object from the policy data.
69    ///
70    /// This function requires the object to have a fixed size and simply copies the object from
71    /// the policy data.
72    ///
73    /// For variable-sized objects, use [`View::parse`] instead.
74    pub fn read(&self, policy_data: &PolicyData) -> T {
75        debug_assert_eq!(self.end - self.start, std::mem::size_of::<T>() as u32);
76        let start = self.start as usize;
77        let end = self.end as usize;
78        T::read_from_bytes(&policy_data[start..end]).unwrap()
79    }
80}
81
82impl<T: HasMetadata> View<T> {
83    /// Returns a view into the metadata of the object.
84    ///
85    /// Assumes the metadata is at the start of the object.
86    pub fn metadata(&self) -> View<T::Metadata> {
87        View::<T::Metadata>::at(self.start)
88    }
89
90    /// Reads the metadata from the policy data.
91    pub fn read_metadata(&self, policy_data: &PolicyData) -> T::Metadata {
92        self.metadata().read(policy_data)
93    }
94}
95
96impl<T: Parse> View<T> {
97    /// Parses the object from the policy data.
98    ///
99    /// This function uses the [`Parse`] trait to parse the object from the policy data.
100    ///
101    /// If the object has a fixed size, prefer [`View::read`] instead.
102    pub fn parse(&self, policy_data: &PolicyData) -> T {
103        let cursor = PolicyCursor::new_at(policy_data.clone(), self.start);
104        let (object, _) =
105            T::parse(cursor).map_err(Into::<anyhow::Error>::into).expect("policy should be valid");
106        object
107    }
108}
109
110impl<T: Validate + Parse> Validate for View<T> {
111    type Error = anyhow::Error;
112
113    fn validate(&self, context: &mut PolicyValidationContext) -> Result<(), Self::Error> {
114        let object = self.parse(&context.data);
115        object.validate(context).map_err(Into::<anyhow::Error>::into)
116    }
117}
118
119/// A view into the data of an array of objects.
120///
121/// This struct contains the start offset of the array and the number of objects in the array.
122/// To iterate over the objects, use [`ArrayDataView::iter`].
123#[derive(Debug, Clone, Copy)]
124pub struct ArrayDataView<D> {
125    phantom: PhantomData<D>,
126    start: PolicyOffset,
127    count: u32,
128}
129
130impl<D> ArrayDataView<D> {
131    /// Creates a new array data view from the start offset and count.
132    pub fn new(start: PolicyOffset, count: u32) -> Self {
133        Self { phantom: PhantomData, start, count }
134    }
135
136    /// Iterates over the objects in the array.
137    ///
138    /// The iterator returns views into the objects in the array.
139    ///
140    /// This function requires the policy data to be provided to the iterator because objects in
141    /// the array may have variable size.
142    pub fn iter(self, policy_data: &PolicyData) -> ArrayDataViewIter<D> {
143        ArrayDataViewIter::new(policy_data.clone(), self.start, self.count)
144    }
145}
146
147/// An iterator over the objects in an array.
148///
149/// This struct contains the cursor to the start of the array and the number of objects remaining
150/// to be iterated over.
151pub struct ArrayDataViewIter<D> {
152    phantom: PhantomData<D>,
153    policy_data: PolicyData,
154    offset: PolicyOffset,
155    remaining: u32,
156}
157
158impl<T> ArrayDataViewIter<T> {
159    /// Creates a new array data view iterator from the start cursor and remaining count.
160    pub(crate) fn new(policy_data: PolicyData, offset: PolicyOffset, remaining: u32) -> Self {
161        Self { phantom: PhantomData, policy_data, offset, remaining }
162    }
163}
164
165impl<D: Walk> std::iter::Iterator for ArrayDataViewIter<D> {
166    type Item = View<D>;
167
168    fn next(&mut self) -> Option<Self::Item> {
169        if self.remaining > 0 {
170            let start = self.offset;
171            self.offset = D::walk(&self.policy_data, start);
172            self.remaining -= 1;
173            Some(View::new(start, self.offset))
174        } else {
175            None
176        }
177    }
178}
179
180/// A view into the data of an array of objects.
181///
182/// This struct contains the start offset of the array and the number of objects in the array.
183/// To access the objects in the array, use [`ArrayView::data`].
184#[derive(Debug, Clone, Copy)]
185pub(crate) struct ArrayView<M, D> {
186    phantom: PhantomData<(M, D)>,
187    start: PolicyOffset,
188    count: u32,
189}
190
191impl<M, D> ArrayView<M, D> {
192    /// Creates a new array view from the start offset and count.
193    pub fn new(start: PolicyOffset, count: u32) -> Self {
194        Self { phantom: PhantomData, start, count }
195    }
196}
197
198impl<M: Sized, D> ArrayView<M, D> {
199    /// Returns a view into the metadata of the array.
200    pub fn metadata(&self) -> View<M> {
201        View::<M>::at(self.start)
202    }
203
204    /// Returns a view into the data of the array.
205    pub fn data(&self) -> ArrayDataView<D> {
206        ArrayDataView::new(self.metadata().end, self.count)
207    }
208}
209
210fn parse_array_data<D: Parse>(
211    cursor: PolicyCursor,
212    count: u32,
213) -> Result<PolicyCursor, anyhow::Error> {
214    let mut tail = cursor;
215    for _ in 0..count {
216        let (_, next) = D::parse(tail).map_err(Into::<anyhow::Error>::into)?;
217        tail = next;
218    }
219    Ok(tail)
220}
221
222impl<M: Counted + Parse + Sized, D: Parse> Parse for ArrayView<M, D> {
223    /// [`ArrayView`] abstracts over two types (`M` and `D`) that may have different [`Parse::Error`]
224    /// types. Unify error return type via [`anyhow::Error`].
225    type Error = anyhow::Error;
226
227    fn parse(cursor: PolicyCursor) -> Result<(Self, PolicyCursor), Self::Error> {
228        let start = cursor.offset();
229        let (metadata, cursor) = M::parse(cursor).map_err(Into::<anyhow::Error>::into)?;
230        let count = metadata.count();
231        let cursor = parse_array_data::<D>(cursor, count)?;
232        Ok((Self::new(start, count), cursor))
233    }
234}
235
236/// A view into the data of an array of objects, with efficient lookup based on metadata hash.
237///
238/// This struct contains only a vector of offsets into the policy data, to allow efficient lookup
239/// of vector elements with matching metadata.
240#[derive(Debug, Clone)]
241pub(crate) struct HashedArrayView<M, D: HasMetadata> {
242    array_view: ArrayView<M, D>,
243    index: HashTable<PolicyOffset>,
244}
245
246impl<M, D: HasMetadata> Deref for HashedArrayView<M, D> {
247    type Target = ArrayView<M, D>;
248
249    fn deref(&self) -> &Self::Target {
250        &self.array_view
251    }
252}
253
254impl<D: HasMetadata, M> HashedArrayView<M, D>
255where
256    D::Metadata: Hash,
257{
258    fn metadata_hash(metadata: &D::Metadata) -> u64 {
259        let mut hasher = DefaultHasher::new();
260        metadata.hash(&mut hasher);
261        hasher.finish()
262    }
263}
264
265impl<D: Parse + HasMetadata, M> HashedArrayView<M, D>
266where
267    D::Metadata: Eq + PartialEq + Hash + Debug,
268{
269    /// Looks up the entry with the specified metadata `key`, and parsed & returns the value.
270    pub fn find(&self, key: D::Metadata, policy_data: &PolicyData) -> Option<D> {
271        let key_hash = Self::metadata_hash(&key);
272        let offset = self.index.find(key_hash, |&offset| {
273            let element = View::<D>::at(offset);
274            key == element.read_metadata(policy_data)
275        })?;
276        let element = View::<D>::at(*offset);
277        Some(element.parse(policy_data))
278    }
279}
280
281impl<M: Counted + Parse + Sized, D: Parse + HasMetadata> Parse for HashedArrayView<M, D>
282where
283    D::Metadata: Eq + Debug + PartialEq + Parse + Hash,
284{
285    /// [`HashedArrayView`] abstracts over two types (`M` and `D`) that may have different
286    /// [`Parse::Error`] types. Unify error return type via [`anyhow::Error`].
287    type Error = anyhow::Error;
288
289    fn parse(cursor: PolicyCursor) -> Result<(Self, PolicyCursor), Self::Error> {
290        // Parse the array using `ArrayView<>` rather than replicating that logic, for now.
291        let (array_view, _) =
292            ArrayView::<M, D>::parse(cursor.clone()).map_err(Into::<anyhow::Error>::into)?;
293
294        // Allocate a hash table sized appropriately for the array size.
295        let mut index = HashTable::with_capacity(array_view.count as usize);
296
297        // Iterate over the elements inserting their offsets into hash buckets.
298        let (_, mut cursor) = M::parse(cursor).map_err(Into::<anyhow::Error>::into)?;
299        for _ in 0..array_view.count {
300            let (metadata, _) =
301                D::Metadata::parse(cursor.clone()).map_err(Into::<anyhow::Error>::into)?;
302            let (_, next) = D::parse(cursor.clone()).map_err(Into::<anyhow::Error>::into)?;
303
304            index.insert_unique(Self::metadata_hash(&metadata), cursor.offset(), |&offset| {
305                let element = View::<D>::at(offset);
306                Self::metadata_hash(&element.read_metadata(cursor.data()))
307            });
308
309            cursor = next;
310        }
311
312        Ok((Self { array_view, index }, cursor))
313    }
314}