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

selinux/policy/
extensible_bitmap.rs
