selinux/policy/
extensible_bitmap.rs

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

selinux/policy/
extensible_bitmap.rs
