selinux/policy/
extensible_bitmap.rs

1// Copyright 2023 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::parser::PolicyCursor;
6use super::{
7    Counted, PolicyValidationContext, Validate, ValidateArray, array_type,
8    array_type_validate_deref_both,
9};
10use crate::policy::error::ValidateError;
11
12use crate::policy::Array;
13use std::cmp::Ordering;
14use zerocopy::{FromBytes, Immutable, KnownLayout, Unaligned, little_endian as le};
15
16/// Maximum number of [`MapItem`] objects in a single [`ExtensibleBitmap`].
17pub(super) const MAX_BITMAP_ITEMS: u32 = 0x40;
18
19/// Fixed expectation for number of bits per [`MapItem`] in every [`ExtensibleBitmap`].
20pub(super) const MAP_NODE_BITS: u32 = 8 * std::mem::size_of::<u64>() as u32;
21
22array_type!(ExtensibleBitmap, Metadata, Vec<MapItem>);
23
24array_type_validate_deref_both!(ExtensibleBitmap);
25
26impl ExtensibleBitmap {
27    /// Returns the number of bits described by this [`ExtensibleBitmap`].
28    pub fn num_elements(&self) -> u32 {
29        self.high_bit()
30    }
31
32    /// Returns whether the `index`'th bit in this bitmap is a 1-bit.
33    pub fn is_set(&self, index: u32) -> bool {
34        if index > self.high_bit() {
35            return false;
36        }
37
38        let map_items = &self.data;
39        if let Ok(i) = map_items.binary_search_by(|map_item| self.item_ordering(map_item, index)) {
40            let map_item = &map_items[i];
41            let item_index = index - map_item.start_bit.get();
42            return map_item.map.get() & (1 << item_index) != 0;
43        }
44
45        false
46    }
47
48    /// Returns an iterator that yields the indices of this [`ExtensibleBitmap`]'s set bits.
49    pub fn indices_of_set_bits<'a>(&'a self) -> impl Iterator<Item = u32> {
50        ExtensibleBitmapSpansIterator::<'a> { bitmap: self, map_item: 0, next_bit: 0 }
51            .flat_map(|span| span.low..=span.high)
52    }
53
54    /// Returns an iterator that returns a set of spans of continuous set bits.
55    /// Each span consists of inclusive low and high bit indexes (i.e. zero-based).
56    pub fn spans<'a>(&'a self) -> ExtensibleBitmapSpansIterator<'a> {
57        ExtensibleBitmapSpansIterator::<'a> { bitmap: self, map_item: 0, next_bit: 0 }
58    }
59
60    /// Returns the next bit after the bits in this [`ExtensibleBitmap`]. That is, the bits in this
61    /// [`ExtensibleBitmap`] may be indexed by the range `[0, Self::high_bit())`.
62    fn high_bit(&self) -> u32 {
63        self.metadata.high_bit.get()
64    }
65
66    fn item_ordering(&self, map_item: &MapItem, index: u32) -> Ordering {
67        let map_item_start_bit = map_item.start_bit.get();
68        if map_item_start_bit > index {
69            Ordering::Greater
70        } else if map_item_start_bit + self.metadata.map_item_size_bits.get() <= index {
71            Ordering::Less
72        } else {
73            Ordering::Equal
74        }
75    }
76}
77
78/// Describes the indexes of a span of "true" bits in an `ExtensibleBitmap`.
79/// Low and high values are inclusive, such that when `low==high`, the span consists
80/// of a single bit.
81#[derive(Debug, Clone, PartialEq)]
82pub(super) struct ExtensibleBitmapSpan {
83    pub low: u32,
84    pub high: u32,
85}
86
87/// Iterator returned by `ExtensibleBitmap::spans()`.
88pub(super) struct ExtensibleBitmapSpansIterator<'a> {
89    bitmap: &'a ExtensibleBitmap,
90    map_item: usize, // Zero-based `Vec<MapItem>` index.
91    next_bit: u32,   // Zero-based bit index within the bitmap.
92}
93
94impl ExtensibleBitmapSpansIterator<'_> {
95    /// Returns the zero-based index of the next bit with the specified value, if any.
96    fn next_bit_with_value(&mut self, is_set: bool) -> Option<u32> {
97        let map_item_size_bits = self.bitmap.metadata.map_item_size_bits.get();
98        let num_elements = self.bitmap.num_elements();
99
100        while self.next_bit < num_elements {
101            let (start_bit, map) = self
102                .bitmap
103                .data
104                .get(self.map_item)
105                .map_or((num_elements, 0), |item| (item.start_bit.get(), item.map.get()));
106
107            if start_bit > self.next_bit {
108                if is_set {
109                    // Skip the implicit "false" bits, to the next `MapItem`.
110                    self.next_bit = start_bit
111                } else {
112                    return Some(self.next_bit);
113                }
114            } else {
115                // Scan the `MapItem` for the next matching bit.
116                let next_map_item_bit = self.next_bit - start_bit;
117                for map_bit in next_map_item_bit..map_item_size_bits {
118                    if ((map & (1 << map_bit)) != 0) == is_set {
119                        self.next_bit = start_bit + map_bit;
120                        return Some(self.next_bit);
121                    }
122                }
123
124                // Move on to the next `MapItem`, which may not be contiguous with
125                // this one.
126                self.next_bit = start_bit + map_item_size_bits;
127                self.map_item += 1;
128            }
129        }
130
131        None
132    }
133}
134
135impl Iterator for ExtensibleBitmapSpansIterator<'_> {
136    type Item = ExtensibleBitmapSpan;
137
138    /// Returns the next span of at least one bit set in the bitmap.
139    fn next(&mut self) -> Option<Self::Item> {
140        let low = self.next_bit_with_value(true)?;
141        // End the span at the bit preceding either the next false bit, or the end of the bitmap.
142        let high =
143            self.next_bit_with_value(false).unwrap_or_else(|| self.bitmap.num_elements()) - 1;
144        Some(Self::Item { low, high })
145    }
146}
147
148impl Validate for Vec<ExtensibleBitmap> {
149    type Error = <ExtensibleBitmap as Validate>::Error;
150
151    fn validate(&self, context: &mut PolicyValidationContext) -> Result<(), Self::Error> {
152        for extensible_bitmap in self.iter() {
153            extensible_bitmap.validate(context)?;
154        }
155
156        Ok(())
157    }
158}
159
160impl Validate for Metadata {
161    type Error = ValidateError;
162
163    /// Validates that [`ExtensibleBitmap`] metadata is internally consistent with data
164    /// representation assumptions.
165    fn validate(&self, _context: &mut PolicyValidationContext) -> Result<(), Self::Error> {
166        // Only one size for `MapItem` instances is supported.
167        let found_size = self.map_item_size_bits.get();
168        if found_size != MAP_NODE_BITS {
169            return Err(ValidateError::InvalidExtensibleBitmapItemSize { found_size });
170        }
171
172        // High bit must be `MapItem` size-aligned.
173        let found_high_bit = self.high_bit.get();
174        if found_high_bit % found_size != 0 {
175            return Err(ValidateError::MisalignedExtensibleBitmapHighBit {
176                found_size,
177                found_high_bit,
178            });
179        }
180
181        // Count and high bit must be consistent.
182        let found_count = self.count.get();
183        if found_count * found_size > found_high_bit {
184            return Err(ValidateError::InvalidExtensibleBitmapHighBit {
185                found_size,
186                found_high_bit,
187                found_count,
188            });
189        }
190        if found_count > MAX_BITMAP_ITEMS {
191            return Err(ValidateError::InvalidExtensibleBitmapCount { found_count });
192        }
193        if found_high_bit != 0 && found_count == 0 {
194            return Err(ValidateError::ExtensibleBitmapNonZeroHighBitAndZeroCount);
195        }
196
197        Ok(())
198    }
199}
200
201#[derive(Clone, Debug, KnownLayout, FromBytes, Immutable, PartialEq, Unaligned)]
202#[repr(C, packed)]
203pub(super) struct Metadata {
204    /// How many bits on each `MapItem`.
205    map_item_size_bits: le::U32,
206    /// Highest bit, non-inclusive.
207    high_bit: le::U32,
208    /// The number of map items.
209    count: le::U32,
210}
211
212impl Counted for Metadata {
213    /// The number of [`MapItem`] objects that follow a [`Metadata`] is the value stored in the
214    /// `metadata.count` field.
215    fn count(&self) -> u32 {
216        self.count.get()
217    }
218}
219
220#[derive(Clone, Debug, KnownLayout, FromBytes, Immutable, PartialEq, Unaligned)]
221#[repr(C, packed)]
222pub(super) struct MapItem {
223    /// The first bit that this [`MapItem`] stores, relative to its [`ExtensibleBitmap`] range:
224    /// `[0, extensible_bitmap.high_bit())`.
225    start_bit: le::U32,
226    /// The bitmap data for this [`MapItem`].
227    map: le::U64,
228}
229
230impl Validate for [MapItem] {
231    type Error = anyhow::Error;
232
233    /// All [`MapItem`] validation requires access to [`Metadata`]; validation performed in
234    /// `ExtensibleBitmap<PS>::validate()`.
235    fn validate(&self, _context: &mut PolicyValidationContext) -> Result<(), Self::Error> {
236        Ok(())
237    }
238}
239
240impl ValidateArray<Metadata, MapItem> for ExtensibleBitmap {
241    type Error = anyhow::Error;
242
243    /// Validates that `metadata` and `data` are internally consistent. [`MapItem`] objects are
244    /// expected to be stored in ascending order (by `start_bit`), and their bit ranges must fall
245    /// within the range `[0, metadata.high_bit())`.
246    fn validate_array(
247        _context: &mut PolicyValidationContext,
248        metadata: &Metadata,
249        items: &[MapItem],
250    ) -> Result<(), Self::Error> {
251        let found_size = metadata.map_item_size_bits.get();
252        let found_high_bit = metadata.high_bit.get();
253
254        // `MapItem` objects must be in sorted order, each with a `MapItem` size-aligned starting bit.
255        //
256        // Note: If sorted order assumption is violated `ExtensibleBitmap::binary_search_items()` will
257        // misbehave and `ExtensibleBitmap` will need to be refactored accordingly.
258        let mut min_start: u32 = 0;
259        for map_item in items.iter() {
260            let found_start_bit = map_item.start_bit.get();
261            if found_start_bit % found_size != 0 {
262                return Err(ValidateError::MisalignedExtensibleBitmapItemStartBit {
263                    found_start_bit,
264                    found_size,
265                }
266                .into());
267            }
268            if found_start_bit < min_start {
269                return Err(ValidateError::OutOfOrderExtensibleBitmapItems {
270                    found_start_bit,
271                    min_start,
272                }
273                .into());
274            }
275            min_start = found_start_bit + found_size;
276        }
277
278        // Last `MapItem` object may not include bits beyond (and including) high bit value.
279        if min_start > found_high_bit {
280            return Err(ValidateError::ExtensibleBitmapItemOverflow {
281                found_items_end: min_start,
282                found_high_bit,
283            }
284            .into());
285        }
286
287        Ok(())
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    use super::*;
294    use crate::policy::Parse;
295    use crate::policy::error::ParseError;
296    use crate::policy::parser::{PolicyCursor, PolicyData};
297    use crate::policy::testing::{as_parse_error, as_validate_error};
298    use std::borrow::Borrow;
299    use std::sync::Arc;
300
301    macro_rules! parse_test {
302        ($parse_output:ident, $data:expr, $result:tt, $policy_data:tt, $check_impl:block) => {{
303            let data = Arc::new($data);
304            fn check_by_value(
305                $result: Result<
306                    ($parse_output, PolicyCursor),
307                    <$parse_output as crate::policy::Parse>::Error,
308                >,
309                $policy_data: &PolicyData,
310            ) -> Option<($parse_output, PolicyCursor)> {
311                $check_impl
312            }
313
314            let by_value_result = $parse_output::parse(PolicyCursor::new(data.clone()));
315            let _ = check_by_value(by_value_result, &data);
316        }};
317    }
318
319    struct ExtensibleBitmapIterator<B: Borrow<ExtensibleBitmap>> {
320        extensible_bitmap: B,
321        i: u32,
322    }
323
324    impl<B: Borrow<ExtensibleBitmap>> Iterator for ExtensibleBitmapIterator<B> {
325        type Item = bool;
326
327        fn next(&mut self) -> Option<Self::Item> {
328            if self.i >= self.extensible_bitmap.borrow().high_bit() {
329                return None;
330            }
331            let value = self.extensible_bitmap.borrow().is_set(self.i);
332            self.i = self.i + 1;
333            Some(value)
334        }
335    }
336
337    impl ExtensibleBitmap {
338        fn iter(&self) -> ExtensibleBitmapIterator<&ExtensibleBitmap> {
339            ExtensibleBitmapIterator { extensible_bitmap: self, i: 0 }
340        }
341    }
342
343    #[test]
344    fn extensible_bitmap_simple() {
345        parse_test!(
346            ExtensibleBitmap,
347            [
348                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
349                MAP_NODE_BITS.to_le_bytes().as_slice(), // high bit for 1-item bitmap
350                (1 as u32).to_le_bytes().as_slice(), // count of `MapItem` entries in 1-item bitmap
351                (0 as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
352                (1 as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
353            ]
354            .concat(),
355            result,
356            _policy_data,
357            {
358                let (extensible_bitmap, tail) = result.expect("parse");
359                assert_eq!(0, tail.len());
360                let mut count: u32 = 0;
361                for (i, bit) in extensible_bitmap.iter().enumerate() {
362                    assert!((i == 0 && bit) || (i > 0 && !bit));
363                    count = count + 1;
364                }
365                assert_eq!(MAP_NODE_BITS, count);
366                Some((extensible_bitmap, tail))
367            }
368        );
369    }
370
371    #[test]
372    fn extensible_bitmap_sparse_two_item() {
373        parse_test!(
374            ExtensibleBitmap,
375            [
376                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
377                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for 2-item bitmap
378                (2 as u32).to_le_bytes().as_slice(), // count of `MapItem` entries  in 2-item bitmap
379                ((MAP_NODE_BITS * 2) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
380                ((1 << 2) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
381                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
382                ((1 << 7) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
383            ]
384            .concat(),
385            result,
386            _policy_data,
387            {
388                let (extensible_bitmap, tail) = result.expect("parse");
389                assert_eq!(0, tail.len());
390                for i in 0..(MAP_NODE_BITS * 10) {
391                    let expected = i == ((MAP_NODE_BITS * 2) + 2) || i == ((MAP_NODE_BITS * 7) + 7);
392                    assert_eq!(expected, extensible_bitmap.is_set(i));
393                }
394
395                let mut count: u32 = 0;
396                for (i, bit) in extensible_bitmap.iter().enumerate() {
397                    let expected = i == (((MAP_NODE_BITS * 2) + 2) as usize)
398                        || i == (((MAP_NODE_BITS * 7) + 7) as usize);
399                    assert_eq!(expected, bit);
400                    count = count + 1;
401                }
402                assert_eq!(MAP_NODE_BITS * 10, count);
403                Some((extensible_bitmap, tail))
404            }
405        );
406    }
407
408    #[test]
409    fn extensible_bitmap_sparse_malformed() {
410        parse_test!(
411            ExtensibleBitmap,
412            [
413                (MAP_NODE_BITS - 1).to_le_bytes().as_slice(), // invalid bits per node
414                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for 2-item bitmap
415                (2 as u32).to_le_bytes().as_slice(), // count of `MapItem` entries in 2-item bitmap
416                ((MAP_NODE_BITS * 2) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
417                ((1 << 2) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
418                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
419                ((1 << 7) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
420            ]
421            .concat(),
422            result,
423            policy_data,
424            {
425                let (parsed, tail) = result.expect("parsed");
426                assert_eq!(0, tail.len());
427                let mut context =
428                    crate::policy::PolicyValidationContext { data: policy_data.clone() };
429                assert_eq!(
430                    Err(ValidateError::InvalidExtensibleBitmapItemSize {
431                        found_size: MAP_NODE_BITS - 1
432                    }),
433                    parsed.validate(&mut context).map_err(as_validate_error)
434                );
435                Some((parsed, tail))
436            }
437        );
438
439        parse_test!(
440            ExtensibleBitmap,
441            [
442                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
443                (((MAP_NODE_BITS * 10) + 1) as u32).to_le_bytes().as_slice(), // invalid high bit for 2-item bitmap
444                (2 as u32).to_le_bytes().as_slice(), // count of `MapItem` entries in 2-item bitmap
445                ((MAP_NODE_BITS * 2) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
446                ((1 << 2) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
447                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
448                ((1 << 7) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
449            ]
450            .concat(),
451            result,
452            policy_data,
453            {
454                let (parsed, tail) = result.expect("parsed");
455                assert_eq!(0, tail.len());
456                let mut context =
457                    crate::policy::PolicyValidationContext { data: policy_data.clone() };
458                assert_eq!(
459                    Err(ValidateError::MisalignedExtensibleBitmapHighBit {
460                        found_size: MAP_NODE_BITS,
461                        found_high_bit: (MAP_NODE_BITS * 10) + 1
462                    }),
463                    parsed.validate(&mut context).map_err(as_validate_error),
464                );
465                Some((parsed, tail))
466            }
467        );
468
469        parse_test!(
470            ExtensibleBitmap,
471            [
472                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
473                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for 2-item bitmap
474                (11 as u32).to_le_bytes().as_slice(), // invalid count of `MapItem` entries in 2-item bitmap
475                ((MAP_NODE_BITS * 2) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
476                ((1 << 2) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
477                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
478                ((1 << 7) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
479            ]
480            .concat(),
481            result,
482            _policy_data,
483            {
484                match result.err().map(Into::<anyhow::Error>::into).map(as_parse_error) {
485                    // `PolicyCursor` attempts to read `Vec` one item at a time.
486                    Some(ParseError::MissingData { type_name, type_size, num_bytes: 0 }) => {
487                        assert_eq!(std::any::type_name::<MapItem>(), type_name);
488                        assert_eq!(std::mem::size_of::<MapItem>(), type_size);
489                    }
490                    v => {
491                        panic!(
492                            "Expected Some({:?}), but got {:?}",
493                            ParseError::MissingData {
494                                type_name: std::any::type_name::<MapItem>(),
495                                type_size: std::mem::size_of::<MapItem>(),
496                                num_bytes: 0,
497                            },
498                            v
499                        );
500                    }
501                };
502                None::<(ExtensibleBitmap, PolicyCursor)>
503            }
504        );
505
506        parse_test!(
507            ExtensibleBitmap,
508            [
509                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
510                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for 2-item bitmap
511                (2 as u32).to_le_bytes().as_slice(), // count of `MapItem` entries in 2-item bitmap
512                (((MAP_NODE_BITS * 2) + 1) as u32).to_le_bytes().as_slice(), // invalid start bit for `MapItem` 0
513                ((1 << 2) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
514                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
515                ((1 << 7) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
516            ]
517            .concat(),
518            result,
519            policy_data,
520            {
521                let (parsed, tail) = result.expect("parsed");
522                assert_eq!(0, tail.len());
523                let mut context =
524                    crate::policy::PolicyValidationContext { data: policy_data.clone() };
525                match parsed.validate(&mut context).map_err(as_validate_error) {
526                    Err(ValidateError::MisalignedExtensibleBitmapItemStartBit {
527                        found_start_bit,
528                        ..
529                    }) => {
530                        assert_eq!((MAP_NODE_BITS * 2) + 1, found_start_bit);
531                    }
532                    parse_err => {
533                        assert!(
534                            false,
535                            "Expected Err(MisalignedExtensibleBitmapItemStartBit...), but got {:?}",
536                            parse_err
537                        );
538                    }
539                }
540                Some((parsed, tail))
541            }
542        );
543
544        parse_test!(
545            ExtensibleBitmap,
546            [
547                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
548                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for 2-item bitmap
549                (2 as u32).to_le_bytes().as_slice(), // count of `MapItem` entries in 2-item bitmap
550                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // out-of-order start bit for `MapItem` 0
551                ((1 << 7) as u64).to_le_bytes().as_slice(),            // bit values for `MapItem` 0
552                ((MAP_NODE_BITS * 2) as u32).to_le_bytes().as_slice(), // out-of-order start bit for `MapItem` 1
553                ((1 << 2) as u64).to_le_bytes().as_slice(),            // bit values for `MapItem` 1
554            ]
555            .concat(),
556            result,
557            policy_data,
558            {
559                let (parsed, tail) = result.expect("parsed");
560                assert_eq!(0, tail.len());
561                let mut context =
562                    crate::policy::PolicyValidationContext { data: policy_data.clone() };
563                assert_eq!(
564                    parsed.validate(&mut context).map_err(as_validate_error),
565                    Err(ValidateError::OutOfOrderExtensibleBitmapItems {
566                        found_start_bit: MAP_NODE_BITS * 2,
567                        min_start: (MAP_NODE_BITS * 7) + MAP_NODE_BITS,
568                    })
569                );
570                Some((parsed, tail))
571            }
572        );
573
574        parse_test!(
575            ExtensibleBitmap,
576            [
577                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
578                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for 2-item bitmap
579                (3 as u32).to_le_bytes().as_slice(), // invalid count of `MapItem` entries in 2-item bitmap
580                ((MAP_NODE_BITS * 2) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
581                ((1 << 2) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
582                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
583                ((1 << 7) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
584            ]
585            .concat(),
586            result,
587            _policy_data,
588            {
589                match result.err().map(Into::<anyhow::Error>::into).map(as_parse_error) {
590                    // `PolicyCursor` attempts to read `Vec` one item at a time.
591                    Some(ParseError::MissingData { type_name, type_size, num_bytes: 0 }) => {
592                        assert_eq!(std::any::type_name::<MapItem>(), type_name);
593                        assert_eq!(std::mem::size_of::<MapItem>(), type_size);
594                    }
595                    parse_err => {
596                        assert!(
597                            false,
598                            "Expected Some({:?}), but got {:?}",
599                            ParseError::MissingData {
600                                type_name: std::any::type_name::<MapItem>(),
601                                type_size: std::mem::size_of::<MapItem>(),
602                                num_bytes: 0
603                            },
604                            parse_err
605                        );
606                    }
607                };
608                None::<(ExtensibleBitmap, PolicyCursor)>
609            }
610        );
611    }
612
613    #[test]
614    fn extensible_bitmap_spans_iterator() {
615        type Span = ExtensibleBitmapSpan;
616
617        // Single- and multi-bit spans.
618        parse_test!(
619            ExtensibleBitmap,
620            [
621                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
622                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for bitmap
623                (2 as u32).to_le_bytes().as_slice(),    // count of `MapItem` entries in bitmap
624                ((MAP_NODE_BITS * 2) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
625                ((1 << 2) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 0
626                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
627                ((1 << 7) | (1 << 8) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
628            ]
629            .concat(),
630            result,
631            _policy_data,
632            {
633                let (extensible_bitmap, tail) = result.expect("parse");
634                assert_eq!(0, tail.len());
635
636                let mut iterator = extensible_bitmap.spans();
637                assert_eq!(
638                    iterator.next(),
639                    Some(Span { low: (MAP_NODE_BITS * 2) + 2, high: (MAP_NODE_BITS * 2) + 2 })
640                );
641                assert_eq!(
642                    iterator.next(),
643                    Some(Span { low: (MAP_NODE_BITS * 7) + 7, high: (MAP_NODE_BITS * 7) + 8 })
644                );
645                assert_eq!(iterator.next(), None);
646
647                Some((extensible_bitmap, tail))
648            }
649        );
650
651        // Multi-bit span that straddles two `MapItem`s.
652        parse_test!(
653            ExtensibleBitmap,
654            [
655                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
656                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for bitmap
657                (2 as u32).to_le_bytes().as_slice(),    // count of `MapItem` entries in bitmap
658                ((MAP_NODE_BITS * 6) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
659                ((1 as u64) << 63).to_le_bytes().as_slice(), // bit values for `MapItem` 0
660                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
661                ((1 << 0) | (1 << 1) as u64).to_le_bytes().as_slice(), // bit values for `MapItem` 1
662            ]
663            .concat(),
664            result,
665            _policy_data,
666            {
667                let (extensible_bitmap, tail) = result.expect("parse");
668                assert_eq!(0, tail.len());
669
670                let mut iterator = extensible_bitmap.spans();
671                assert_eq!(
672                    iterator.next(),
673                    Some(Span { low: (MAP_NODE_BITS * 6) + 63, high: (MAP_NODE_BITS * 7) + 1 })
674                );
675                assert_eq!(iterator.next(), None);
676
677                Some((extensible_bitmap, tail))
678            }
679        );
680
681        // Multi-bit spans of full `MapItem`s, separated by an implicit span of false bits,
682        // and with further implicit spans of false bits at the end.
683        parse_test!(
684            ExtensibleBitmap,
685            [
686                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
687                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for bitmap
688                (2 as u32).to_le_bytes().as_slice(),    // count of `MapItem` entries in bitmap
689                ((MAP_NODE_BITS * 5) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
690                (u64::MAX).to_le_bytes().as_slice(),    // bit values for `MapItem` 0
691                ((MAP_NODE_BITS * 7) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 1
692                (u64::MAX).to_le_bytes().as_slice(),    // bit values for `MapItem` 1
693            ]
694            .concat(),
695            result,
696            _policy_data,
697            {
698                let (extensible_bitmap, tail) = result.expect("parse");
699                assert_eq!(0, tail.len());
700
701                let mut iterator = extensible_bitmap.spans();
702                assert_eq!(
703                    iterator.next(),
704                    Some(Span { low: (MAP_NODE_BITS * 5), high: (MAP_NODE_BITS * 6) - 1 })
705                );
706                assert_eq!(
707                    iterator.next(),
708                    Some(Span { low: (MAP_NODE_BITS * 7), high: (MAP_NODE_BITS * 8) - 1 })
709                );
710                assert_eq!(iterator.next(), None);
711
712                Some((extensible_bitmap, tail))
713            }
714        );
715
716        // Span reaching the end of the bitmap is handled correctly.
717        parse_test!(
718            ExtensibleBitmap,
719            [
720                MAP_NODE_BITS.to_le_bytes().as_slice(), // bits per node
721                ((MAP_NODE_BITS * 10) as u32).to_le_bytes().as_slice(), // high bit for bitmap
722                (1 as u32).to_le_bytes().as_slice(),    // count of `MapItem` entries  in bitmap
723                ((MAP_NODE_BITS * 9) as u32).to_le_bytes().as_slice(), // start bit for `MapItem` 0
724                (u64::MAX).to_le_bytes().as_slice(),    // bit values for `MapItem` 0
725            ]
726            .concat(),
727            result,
728            _policy_data,
729            {
730                let (extensible_bitmap, tail) = result.expect("parse");
731                assert_eq!(0, tail.len());
732
733                let mut iterator = extensible_bitmap.spans();
734                assert_eq!(
735                    iterator.next(),
736                    Some(Span { low: (MAP_NODE_BITS * 9), high: (MAP_NODE_BITS * 10) - 1 })
737                );
738                assert_eq!(iterator.next(), None);
739
740                Some((extensible_bitmap, tail))
741            }
742        );
743    }
744}
selinux/policy/extensible_bitmap.rs

selinux/policy/
extensible_bitmap.rs
