fuchsia_inspect/writer/
heap.rs

1// Copyright 2019 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
5//! Implements the buddy allocation algorithm for the [Inspect VMO][inspect-vmo]
6//!
7//! [inspect-vmo]: https://fuchsia.dev/fuchsia-src/reference/diagnostics/inspect/vmo-format
8
9use crate::writer::Error;
10use inspect_format::{
11    Block, BlockAccessorExt, BlockAccessorMutExt, BlockIndex, BlockType, Free, ReadBytes, Reserved,
12    WriteBytes, constants, utils,
13};
14use std::cmp::min;
15
16/// The inspect heap.
17#[derive(Debug)]
18pub struct Heap<T> {
19    pub(crate) container: T,
20    current_size_bytes: usize,
21    free_head_per_order: [BlockIndex; constants::NUM_ORDERS as usize],
22    allocated_blocks: usize,
23    deallocated_blocks: usize,
24    failed_allocations: usize,
25    has_header: bool,
26}
27
28impl<T: ReadBytes + WriteBytes> Heap<T> {
29    /// Creates a new heap on the underlying mapped VMO and initializes the header block in it.
30    pub fn new(container: T) -> Result<Self, Error> {
31        let mut heap = Self::empty(container)?;
32        heap.init_header()?;
33        Ok(heap)
34    }
35
36    /// Creates a new heap on the underlying mapped VMO without initializing the header block.
37    pub fn empty(container: T) -> Result<Self, Error> {
38        let mut heap = Heap {
39            container,
40            current_size_bytes: 0,
41            free_head_per_order: [BlockIndex::EMPTY; constants::NUM_ORDERS as usize],
42            allocated_blocks: 0,
43            deallocated_blocks: 0,
44            failed_allocations: 0,
45            has_header: false,
46        };
47        heap.grow_heap(constants::PAGE_SIZE_BYTES)?;
48        Ok(heap)
49    }
50
51    #[inline]
52    fn init_header(&mut self) -> Result<(), Error> {
53        let header_index =
54            self.allocate_block(inspect_format::utils::order_to_size(constants::HEADER_ORDER))?;
55        let heap_current_size = self.current_size_bytes;
56        self.container
57            .block_at_unchecked_mut::<Reserved>(header_index)
58            .become_header(heap_current_size)?;
59        self.has_header = true;
60        Ok(())
61    }
62
63    /// Returns the current size of this heap in bytes.
64    pub fn current_size(&self) -> usize {
65        self.current_size_bytes
66    }
67
68    /// Returns the maximum size of this heap in bytes.
69    pub fn maximum_size(&self) -> usize {
70        self.container.len()
71    }
72
73    /// Returns the number of blocks allocated since the creation of this heap.
74    pub fn total_allocated_blocks(&self) -> usize {
75        self.allocated_blocks
76    }
77
78    /// Returns the number blocks deallocated since the creation of this heap.
79    pub fn total_deallocated_blocks(&self) -> usize {
80        self.deallocated_blocks
81    }
82
83    /// Returns the number of failed allocations since the creation of this heap.
84    pub fn failed_allocations(&self) -> usize {
85        self.failed_allocations
86    }
87
88    /// Allocates a new block of the given `min_size`.
89    pub fn allocate_block(&mut self, min_size: usize) -> Result<BlockIndex, Error> {
90        let min_fit_order = utils::fit_order(min_size);
91        if min_fit_order >= constants::NUM_ORDERS as usize {
92            return Err(Error::InvalidBlockOrder(min_fit_order));
93        }
94        let min_fit_order = min_fit_order as u8;
95        // Find free block with order >= min_fit_order
96        let order_found = (min_fit_order..constants::NUM_ORDERS)
97            .find(|&i| self.is_free_block(self.free_head_per_order[i as usize], i).is_some());
98        let next_order = match order_found {
99            Some(order) => order,
100            None => {
101                self.grow_heap(self.current_size_bytes + constants::PAGE_SIZE_BYTES)?;
102                constants::NUM_ORDERS - 1
103            }
104        };
105        let block_index = self.free_head_per_order[next_order as usize];
106        while self.container.block_at(block_index).order() > min_fit_order {
107            self.split_block(block_index)?;
108        }
109        self.remove_free(block_index);
110        let _ = self.container.block_at_unchecked_mut::<Free>(block_index).become_reserved();
111        self.allocated_blocks += 1;
112        Ok(block_index)
113    }
114
115    /// Marks the memory region pointed by the given `block` as free.
116    pub fn free_block(&mut self, mut block_index: BlockIndex) -> Result<(), Error> {
117        let block = self.container.block_at(block_index);
118        if block.block_type() == Some(BlockType::Free) {
119            return Err(Error::BlockAlreadyFree(block_index));
120        }
121        let mut buddy_index = buddy(block_index, block.order());
122
123        while self.possible_to_merge(buddy_index, block_index) {
124            self.remove_free(buddy_index);
125            if buddy_index < block_index {
126                std::mem::swap(&mut buddy_index, &mut block_index);
127            }
128            let mut block = self.container.block_at_mut(block_index);
129            let order = block.order();
130            block.set_order(order + 1)?;
131            buddy_index = buddy(block_index, order + 1);
132        }
133        let block = self.container.block_at_unchecked_mut::<Reserved>(block_index);
134        let order = block.order();
135        let _ = block.become_free(self.free_head_per_order[order as usize]);
136        self.free_head_per_order[order as usize] = block_index;
137        self.deallocated_blocks += 1;
138        Ok(())
139    }
140
141    #[inline]
142    fn possible_to_merge(&self, buddy_index: BlockIndex, block_index: BlockIndex) -> bool {
143        let max_block_index = self.current_size_bytes / constants::MIN_ORDER_SIZE;
144        if *buddy_index as usize >= max_block_index {
145            return false;
146        }
147        self.container
148            .maybe_block_at::<Free>(buddy_index)
149            .map(|buddy_block| {
150                let block = self.container.block_at(block_index);
151                block.order() < constants::NUM_ORDERS - 1 && block.order() == buddy_block.order()
152            })
153            .unwrap_or(false)
154    }
155
156    /// Returns a copy of the bytes stored in this Heap.
157    pub(crate) fn bytes(&self) -> Vec<u8> {
158        self.container.get_slice(self.current_size_bytes).unwrap().to_vec()
159    }
160
161    #[inline]
162    fn grow_heap(&mut self, requested_size: usize) -> Result<(), Error> {
163        let container_size = self.container.len();
164        if requested_size > container_size || requested_size > constants::MAX_VMO_SIZE {
165            self.failed_allocations += 1;
166            return Err(Error::HeapMaxSizeReached);
167        }
168        let new_size = min(container_size, requested_size);
169        let min_index = BlockIndex::from_offset(self.current_size_bytes);
170        let mut last_index = self.free_head_per_order[(constants::NUM_ORDERS - 1) as usize];
171        let mut curr_index =
172            BlockIndex::from_offset(new_size - new_size % constants::PAGE_SIZE_BYTES);
173        loop {
174            curr_index -= BlockIndex::from_offset(constants::MAX_ORDER_SIZE);
175            Block::free(&mut self.container, curr_index, constants::NUM_ORDERS - 1, last_index)
176                .expect("Failed to create free block");
177            last_index = curr_index;
178            if curr_index <= min_index {
179                break;
180            }
181        }
182        self.free_head_per_order[(constants::NUM_ORDERS - 1) as usize] = last_index;
183        self.current_size_bytes = new_size;
184        if self.has_header {
185            self.container
186                .block_at_unchecked_mut(BlockIndex::HEADER)
187                // Safety: the current size can't be larger than a max u32 value
188                .set_vmo_size(self.current_size_bytes as u32)?;
189        }
190        Ok(())
191    }
192
193    #[inline]
194    fn is_free_block(
195        &mut self,
196        index: BlockIndex,
197        expected_order: u8,
198    ) -> Option<Block<&mut T, Free>> {
199        // Safety: promoting from u32 to usize
200        if (*index as usize) >= self.current_size_bytes / constants::MIN_ORDER_SIZE {
201            return None;
202        }
203        self.container
204            .maybe_block_at_mut::<Free>(index)
205            .filter(|block| block.order() == expected_order)
206    }
207
208    #[inline]
209    fn remove_free(&mut self, block_index: BlockIndex) {
210        let block = self.container.block_at_unchecked::<Free>(block_index);
211        let free_next_index = block.free_next_index();
212        let order = block.order();
213        if order >= constants::NUM_ORDERS {
214            return;
215        }
216        let mut next_index = self.free_head_per_order[order as usize];
217        if next_index == block_index {
218            self.free_head_per_order[order as usize] = free_next_index;
219            return;
220        }
221        while let Some(mut curr_block) = self.is_free_block(next_index, order) {
222            next_index = curr_block.free_next_index();
223            if next_index == block_index {
224                curr_block.set_free_next_index(free_next_index);
225                return;
226            }
227        }
228    }
229
230    #[inline]
231    fn split_block(&mut self, block_index: BlockIndex) -> Result<(), Error> {
232        let block_order = self.container.block_at(block_index).order();
233        if block_order >= constants::NUM_ORDERS {
234            return Err(Error::InvalidBlockOrderAtIndex(block_order, block_index));
235        }
236        self.remove_free(block_index);
237        let buddy_index = buddy(block_index, block_order - 1);
238        let mut block = self.container.block_at_mut(block_index);
239        block.set_order(block_order - 1)?;
240        block.become_free(buddy_index);
241
242        let mut buddy = self.container.block_at_mut(buddy_index);
243        let buddy_order = block_order - 1;
244        buddy.set_order(buddy_order)?;
245        buddy.become_free(self.free_head_per_order[buddy_order as usize]);
246        self.free_head_per_order[buddy_order as usize] = block_index;
247        Ok(())
248    }
249}
250
251fn buddy(index: BlockIndex, order: u8) -> BlockIndex {
252    index ^ BlockIndex::from_offset(utils::order_to_size(order))
253}
254
255#[cfg(test)]
256mod tests {
257    use super::*;
258    use crate::reader::snapshot::{BackingBuffer, BlockIterator};
259    use inspect_format::{BlockType, Container, Header, block_testing};
260
261    #[derive(Debug)]
262    struct BlockDebug {
263        index: BlockIndex,
264        order: u8,
265        block_type: BlockType,
266    }
267
268    fn validate<T: WriteBytes + ReadBytes>(expected: &[BlockDebug], heap: &Heap<T>) {
269        let buffer = BackingBuffer::Bytes(heap.bytes());
270        let actual: Vec<BlockDebug> = BlockIterator::from(&buffer)
271            .map(|block| BlockDebug {
272                order: block.order(),
273                index: block.index(),
274                block_type: block.block_type().unwrap(),
275            })
276            .collect();
277        assert_eq!(expected.len(), actual.len());
278        for (i, result) in actual.iter().enumerate() {
279            assert_eq!(result.block_type, expected[i].block_type);
280            assert_eq!(result.index, expected[i].index);
281            assert_eq!(result.order, expected[i].order);
282        }
283    }
284
285    #[fuchsia::test]
286    fn test_possible_to_merge_out_of_bounds() {
287        let (container, _storage) = Container::read_and_write(4096).unwrap();
288        let heap = Heap::empty(container).unwrap();
289        let oob_buddy = BlockIndex::from_offset(8192);
290        let block_idx = BlockIndex::from(0);
291        assert!(!heap.possible_to_merge(oob_buddy, block_idx));
292    }
293
294    #[fuchsia::test]
295    fn empty_heap() {
296        let (container, _storage) = Container::read_and_write(4096).unwrap();
297        let heap = Heap::empty(container).unwrap();
298        assert_eq!(heap.current_size_bytes, 4096);
299        assert_eq!(heap.free_head_per_order, [BlockIndex::EMPTY; 8]);
300
301        let expected = [
302            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Free },
303            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
304        ];
305        validate(&expected, &heap);
306        assert_eq!(*heap.free_head_per_order[7], 0);
307        assert_eq!(*heap.container.block_at_unchecked::<Free>(0.into()).free_next_index(), 128);
308        assert_eq!(*heap.container.block_at_unchecked::<Free>(128.into()).free_next_index(), 0);
309        assert_eq!(heap.failed_allocations, 0);
310    }
311
312    #[fuchsia::test]
313    fn new_heap() {
314        let (container, _storage) = Container::read_and_write(4096).unwrap();
315        let heap = Heap::new(container).unwrap();
316        assert_eq!(heap.current_size_bytes, 4096);
317        assert_eq!(
318            heap.free_head_per_order,
319            [
320                BlockIndex::from(0),
321                BlockIndex::from(2),
322                BlockIndex::from(4),
323                BlockIndex::from(8),
324                BlockIndex::from(16),
325                BlockIndex::from(32),
326                BlockIndex::from(64),
327                BlockIndex::from(128)
328            ]
329        );
330
331        let expected = [
332            BlockDebug { index: 0.into(), order: 1, block_type: BlockType::Header },
333            BlockDebug { index: 2.into(), order: 1, block_type: BlockType::Free },
334            BlockDebug { index: 4.into(), order: 2, block_type: BlockType::Free },
335            BlockDebug { index: 8.into(), order: 3, block_type: BlockType::Free },
336            BlockDebug { index: 16.into(), order: 4, block_type: BlockType::Free },
337            BlockDebug { index: 32.into(), order: 5, block_type: BlockType::Free },
338            BlockDebug { index: 64.into(), order: 6, block_type: BlockType::Free },
339            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
340        ];
341        validate(&expected, &heap);
342        assert_eq!(*heap.container.block_at_unchecked::<Free>(128.into()).free_next_index(), 0);
343        assert_eq!(heap.failed_allocations, 0);
344    }
345
346    #[fuchsia::test]
347    fn allocate_and_free() {
348        let (container, _storage) = Container::read_and_write(4096).unwrap();
349        let mut heap = Heap::empty(container).unwrap();
350
351        // Allocate some small blocks and ensure they are all in order.
352        for i in 0..=5 {
353            let block = heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap();
354            assert_eq!(*block, i);
355        }
356
357        // Free some blocks. Leaving some in the middle.
358        assert!(heap.free_block(BlockIndex::from(2)).is_ok());
359        assert!(heap.free_block(BlockIndex::from(4)).is_ok());
360        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
361
362        // Allocate more small blocks and ensure we get the same ones in reverse
363        // order.
364        let b = heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap();
365        assert_eq!(*b, 0);
366        let b = heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap();
367        assert_eq!(*b, 4);
368        let b = heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap();
369        assert_eq!(*b, 2);
370
371        // Free everything except the first two.
372        assert!(heap.free_block(BlockIndex::from(4)).is_ok());
373        assert!(heap.free_block(BlockIndex::from(2)).is_ok());
374        assert!(heap.free_block(BlockIndex::from(3)).is_ok());
375        assert!(heap.free_block(BlockIndex::from(5)).is_ok());
376
377        let expected = [
378            BlockDebug { index: 0.into(), order: 0, block_type: BlockType::Reserved },
379            BlockDebug { index: 1.into(), order: 0, block_type: BlockType::Reserved },
380            BlockDebug { index: 2.into(), order: 1, block_type: BlockType::Free },
381            BlockDebug { index: 4.into(), order: 2, block_type: BlockType::Free },
382            BlockDebug { index: 8.into(), order: 3, block_type: BlockType::Free },
383            BlockDebug { index: 16.into(), order: 4, block_type: BlockType::Free },
384            BlockDebug { index: 32.into(), order: 5, block_type: BlockType::Free },
385            BlockDebug { index: 64.into(), order: 6, block_type: BlockType::Free },
386            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
387        ];
388        validate(&expected, &heap);
389        assert!(heap.free_head_per_order.iter().enumerate().skip(2).all(|(i, &j)| (1 << i) == *j));
390        let buffer = BackingBuffer::from(heap.bytes());
391        assert!(
392            BlockIterator::from(&buffer).skip(2).all(|b| *b
393                .cast::<Free>()
394                .unwrap()
395                .free_next_index()
396                == 0)
397        );
398
399        // Ensure a large block takes the first free large one.
400        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
401        let b = heap.allocate_block(2048).unwrap();
402        assert_eq!(*b, 128);
403
404        // Free last small allocation, next large takes first half of the
405        // buffer.
406        assert!(heap.free_block(BlockIndex::from(1)).is_ok());
407        let b = heap.allocate_block(2048).unwrap();
408        assert_eq!(*b, 0);
409
410        let expected = [
411            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Reserved },
412            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Reserved },
413        ];
414        validate(&expected, &heap);
415
416        // Allocate twice in the first half, free in reverse order to ensure
417        // freeing works left to right and right to left.
418        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
419        let b = heap.allocate_block(1024).unwrap();
420        assert_eq!(*b, 0);
421        let b = heap.allocate_block(1024).unwrap();
422        assert_eq!(*b, 64);
423        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
424        assert!(heap.free_block(BlockIndex::from(64)).is_ok());
425
426        // Ensure freed blocks are merged int a big one and that we can use all
427        // space at 0.
428        let b = heap.allocate_block(2048).unwrap();
429        assert_eq!(*b, 0);
430        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
431
432        let expected = [
433            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Free },
434            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Reserved },
435        ];
436        validate(&expected, &heap);
437        assert_eq!(*heap.free_head_per_order[7], 0);
438        assert_eq!(*heap.container.block_at_unchecked::<Free>(0.into()).free_next_index(), 0);
439
440        assert!(heap.free_block(BlockIndex::from(128)).is_ok());
441        let expected = [
442            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Free },
443            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
444        ];
445        validate(&expected, &heap);
446        assert_eq!(*heap.free_head_per_order[7], 128);
447        assert_eq!(*heap.container.block_at_unchecked::<Free>(0.into()).free_next_index(), 0);
448        assert_eq!(*heap.container.block_at_unchecked::<Free>(128.into()).free_next_index(), 0);
449        assert_eq!(heap.failed_allocations, 0);
450    }
451
452    #[fuchsia::test]
453    fn allocation_counters_work() {
454        let (container, _storage) = Container::read_and_write(4096).unwrap();
455        let mut heap = Heap::empty(container).unwrap();
456
457        let block_count_to_allocate: usize = 50;
458        for _ in 0..block_count_to_allocate {
459            heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap();
460        }
461
462        assert_eq!(heap.total_allocated_blocks(), block_count_to_allocate);
463
464        let block_count_to_free: usize = 5;
465        for i in 0..block_count_to_free {
466            heap.free_block(BlockIndex::from(i as u32)).unwrap();
467        }
468
469        assert_eq!(heap.total_allocated_blocks(), block_count_to_allocate);
470        assert_eq!(heap.total_deallocated_blocks(), block_count_to_free);
471
472        for i in block_count_to_free..block_count_to_allocate {
473            heap.free_block(BlockIndex::from(i as u32)).unwrap();
474        }
475
476        assert_eq!(heap.total_allocated_blocks(), block_count_to_allocate);
477        assert_eq!(heap.total_deallocated_blocks(), block_count_to_allocate);
478    }
479
480    #[fuchsia::test]
481    fn allocate_merge() {
482        let (container, _storage) = Container::read_and_write(4096).unwrap();
483        let mut heap = Heap::empty(container).unwrap();
484        for i in 0..=3 {
485            let block = heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap();
486            assert_eq!(*block, i);
487        }
488
489        assert!(heap.free_block(BlockIndex::from(2)).is_ok());
490        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
491        assert!(heap.free_block(BlockIndex::from(1)).is_ok());
492
493        let expected = [
494            BlockDebug { index: 0.into(), order: 1, block_type: BlockType::Free },
495            BlockDebug { index: 2.into(), order: 0, block_type: BlockType::Free },
496            BlockDebug { index: 3.into(), order: 0, block_type: BlockType::Reserved },
497            BlockDebug { index: 4.into(), order: 2, block_type: BlockType::Free },
498            BlockDebug { index: 8.into(), order: 3, block_type: BlockType::Free },
499            BlockDebug { index: 16.into(), order: 4, block_type: BlockType::Free },
500            BlockDebug { index: 32.into(), order: 5, block_type: BlockType::Free },
501            BlockDebug { index: 64.into(), order: 6, block_type: BlockType::Free },
502            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
503        ];
504        validate(&expected, &heap);
505        assert!(heap.free_head_per_order.iter().enumerate().skip(3).all(|(i, &j)| (1 << i) == *j));
506        let buffer = BackingBuffer::from(heap.bytes());
507        assert!(
508            BlockIterator::from(&buffer).skip(3).all(|b| *b
509                .cast::<Free>()
510                .unwrap()
511                .free_next_index()
512                == 0)
513        );
514        assert_eq!(*heap.free_head_per_order[1], 0);
515        assert_eq!(*heap.free_head_per_order[0], 2);
516        assert_eq!(*heap.container.block_at_unchecked::<Free>(0.into()).free_next_index(), 0);
517        assert_eq!(*heap.container.block_at_unchecked::<Free>(2.into()).free_next_index(), 0);
518
519        assert!(heap.free_block(BlockIndex::from(3)).is_ok());
520        let expected = [
521            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Free },
522            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
523        ];
524        validate(&expected, &heap);
525        assert_eq!(*heap.free_head_per_order[1], 0);
526        assert_eq!(*heap.container.block_at_unchecked::<Free>(0.into()).free_next_index(), 128);
527        assert_eq!(*heap.container.block_at_unchecked::<Free>(128.into()).free_next_index(), 0);
528    }
529
530    #[fuchsia::test]
531    fn extend() {
532        let (container, _storage) = Container::read_and_write(8 * 2048).unwrap();
533        let mut heap = Heap::empty(container).unwrap();
534
535        let b = heap.allocate_block(2048).unwrap();
536        assert_eq!(*b, 0);
537        let b = heap.allocate_block(2048).unwrap();
538        assert_eq!(*b, 128);
539        let b = heap.allocate_block(2048).unwrap();
540        assert_eq!(*b, 256);
541
542        let expected = [
543            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Reserved },
544            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Reserved },
545            BlockDebug { index: 256.into(), order: 7, block_type: BlockType::Reserved },
546            BlockDebug { index: 384.into(), order: 7, block_type: BlockType::Free },
547        ];
548        validate(&expected, &heap);
549        assert_eq!(*heap.free_head_per_order[7], 384);
550        assert_eq!(*heap.container.block_at_unchecked::<Free>(384.into()).free_next_index(), 0);
551
552        let b = heap.allocate_block(2048).unwrap();
553        assert_eq!(*b, 384);
554        let b = heap.allocate_block(2048).unwrap();
555        assert_eq!(*b, 512);
556
557        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
558        assert!(heap.free_block(BlockIndex::from(128)).is_ok());
559        assert!(heap.free_block(BlockIndex::from(256)).is_ok());
560        assert!(heap.free_block(BlockIndex::from(384)).is_ok());
561        assert!(heap.free_block(BlockIndex::from(512)).is_ok());
562
563        let expected = [
564            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Free },
565            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
566            BlockDebug { index: 256.into(), order: 7, block_type: BlockType::Free },
567            BlockDebug { index: 384.into(), order: 7, block_type: BlockType::Free },
568            BlockDebug { index: 512.into(), order: 7, block_type: BlockType::Free },
569            BlockDebug { index: 640.into(), order: 7, block_type: BlockType::Free },
570        ];
571        validate(&expected, &heap);
572        assert_eq!(heap.current_size_bytes, 2048 * 4 + 4096);
573        assert_eq!(*heap.free_head_per_order[7], 512);
574        assert_eq!(*heap.container.block_at_unchecked::<Free>(512.into()).free_next_index(), 384);
575        assert_eq!(*heap.container.block_at_unchecked::<Free>(384.into()).free_next_index(), 256);
576        assert_eq!(*heap.container.block_at_unchecked::<Free>(256.into()).free_next_index(), 128);
577        assert_eq!(*heap.container.block_at_unchecked::<Free>(128.into()).free_next_index(), 0);
578        assert_eq!(*heap.container.block_at_unchecked::<Free>(0.into()).free_next_index(), 640);
579        assert_eq!(*heap.container.block_at_unchecked::<Free>(640.into()).free_next_index(), 0);
580        assert_eq!(heap.failed_allocations, 0);
581    }
582
583    #[fuchsia::test]
584    fn extend_error() {
585        let (container, _storage) = Container::read_and_write(4 * 2048).unwrap();
586        let mut heap = Heap::empty(container).unwrap();
587
588        let b = heap.allocate_block(2048).unwrap();
589        assert_eq!(*b, 0);
590        let b = heap.allocate_block(2048).unwrap();
591        assert_eq!(*b, 128);
592        let b = heap.allocate_block(2048).unwrap();
593        assert_eq!(*b, 256);
594
595        let expected = [
596            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Reserved },
597            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Reserved },
598            BlockDebug { index: 256.into(), order: 7, block_type: BlockType::Reserved },
599            BlockDebug { index: 384.into(), order: 7, block_type: BlockType::Free },
600        ];
601        validate(&expected, &heap);
602
603        let b = heap.allocate_block(2048).unwrap();
604        assert_eq!(*b, 384);
605        assert_eq!(heap.failed_allocations, 0);
606        assert!(heap.allocate_block(2048).is_err());
607        assert_eq!(heap.failed_allocations, 1);
608        assert!(heap.allocate_block(2048).is_err());
609        assert_eq!(heap.failed_allocations, 2);
610
611        assert!(heap.free_block(BlockIndex::from(0)).is_ok());
612        assert!(heap.free_block(BlockIndex::from(128)).is_ok());
613        assert!(heap.free_block(BlockIndex::from(256)).is_ok());
614        assert!(heap.free_block(BlockIndex::from(384)).is_ok());
615
616        let expected = [
617            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Free },
618            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
619            BlockDebug { index: 256.into(), order: 7, block_type: BlockType::Free },
620            BlockDebug { index: 384.into(), order: 7, block_type: BlockType::Free },
621        ];
622        validate(&expected, &heap);
623    }
624
625    #[fuchsia::test]
626    fn extend_vmo_greater_max_size() {
627        let (container, _storage) =
628            Container::read_and_write(constants::MAX_VMO_SIZE + 2048).unwrap();
629        let mut heap = Heap::empty(container).unwrap();
630
631        for n in 0_u32..(constants::MAX_VMO_SIZE / constants::MAX_ORDER_SIZE).try_into().unwrap() {
632            let b = heap.allocate_block(2048).unwrap();
633            assert_eq!(*b, n * 128);
634        }
635        assert_eq!(heap.failed_allocations, 0);
636        assert!(heap.allocate_block(2048).is_err());
637        assert_eq!(heap.failed_allocations, 1);
638
639        for n in 0_u32..(constants::MAX_VMO_SIZE / constants::MAX_ORDER_SIZE).try_into().unwrap() {
640            assert!(heap.free_block(BlockIndex::from(n * 128)).is_ok());
641        }
642    }
643
644    #[fuchsia::test]
645    fn dont_reinterpret_upper_block_contents() {
646        let (container, _storage) = Container::read_and_write(4096).unwrap();
647        let mut heap = Heap::empty(container).unwrap();
648
649        // Allocate 3 blocks.
650        assert_eq!(*heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap(), 0);
651        let b1 = heap.allocate_block(utils::order_to_size(1)).unwrap();
652        assert_eq!(*b1, 2);
653        assert_eq!(*heap.allocate_block(utils::order_to_size(1)).unwrap(), 4);
654
655        // Write garbage to the second half of the order 1 block in index 2.
656        {
657            let mut block = heap.container.block_at_mut(3.into());
658            block_testing::override_header(&mut block, 0xffffffff);
659            block_testing::override_payload(&mut block, 0xffffffff);
660        }
661
662        // Free order 1 block in index 2.
663        assert!(heap.free_block(b1).is_ok());
664
665        // Allocate small blocks in free order 0 blocks.
666        assert_eq!(*heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap(), 1);
667        assert_eq!(*heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap(), 2);
668
669        // This should succeed even if the bytes in this region were garbage.
670        assert_eq!(*heap.allocate_block(constants::MIN_ORDER_SIZE).unwrap(), 3);
671
672        let expected = [
673            BlockDebug { index: 0.into(), order: 0, block_type: BlockType::Reserved },
674            BlockDebug { index: 1.into(), order: 0, block_type: BlockType::Reserved },
675            BlockDebug { index: 2.into(), order: 0, block_type: BlockType::Reserved },
676            BlockDebug { index: 3.into(), order: 0, block_type: BlockType::Reserved },
677            BlockDebug { index: 4.into(), order: 1, block_type: BlockType::Reserved },
678            BlockDebug { index: 6.into(), order: 1, block_type: BlockType::Free },
679            BlockDebug { index: 8.into(), order: 3, block_type: BlockType::Free },
680            BlockDebug { index: 16.into(), order: 4, block_type: BlockType::Free },
681            BlockDebug { index: 32.into(), order: 5, block_type: BlockType::Free },
682            BlockDebug { index: 64.into(), order: 6, block_type: BlockType::Free },
683            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
684        ];
685        validate(&expected, &heap);
686    }
687
688    #[fuchsia::test]
689    fn update_header_vmo_size() {
690        let (container, _storage) = Container::read_and_write(3 * 4096).unwrap();
691        let mut heap = Heap::new(container).unwrap();
692        assert_eq!(
693            heap.container
694                .block_at_unchecked::<Header>(BlockIndex::HEADER)
695                .vmo_size()
696                .unwrap()
697                .unwrap() as usize,
698            heap.current_size()
699        );
700        let b = heap.allocate_block(2048).unwrap();
701        assert_eq!(*b, 128);
702        assert_eq!(
703            heap.container
704                .block_at_unchecked::<Header>(BlockIndex::HEADER)
705                .vmo_size()
706                .unwrap()
707                .unwrap() as usize,
708            heap.current_size()
709        );
710        let b = heap.allocate_block(2048).unwrap();
711        assert_eq!(*b, 256);
712        assert_eq!(
713            heap.container
714                .block_at_unchecked::<Header>(BlockIndex::HEADER)
715                .vmo_size()
716                .unwrap()
717                .unwrap() as usize,
718            heap.current_size()
719        );
720        let b = heap.allocate_block(2048).unwrap();
721        assert_eq!(*b, 384);
722        assert_eq!(
723            heap.container
724                .block_at_unchecked::<Header>(BlockIndex::HEADER)
725                .vmo_size()
726                .unwrap()
727                .unwrap() as usize,
728            heap.current_size()
729        );
730
731        let expected = [
732            BlockDebug { index: 0.into(), order: 1, block_type: BlockType::Header },
733            BlockDebug { index: 2.into(), order: 1, block_type: BlockType::Free },
734            BlockDebug { index: 4.into(), order: 2, block_type: BlockType::Free },
735            BlockDebug { index: 8.into(), order: 3, block_type: BlockType::Free },
736            BlockDebug { index: 16.into(), order: 4, block_type: BlockType::Free },
737            BlockDebug { index: 32.into(), order: 5, block_type: BlockType::Free },
738            BlockDebug { index: 64.into(), order: 6, block_type: BlockType::Free },
739            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Reserved },
740            BlockDebug { index: 256.into(), order: 7, block_type: BlockType::Reserved },
741            BlockDebug { index: 384.into(), order: 7, block_type: BlockType::Reserved },
742        ];
743        validate(&expected, &heap);
744
745        let b = heap.allocate_block(2048).unwrap();
746        assert_eq!(*b, 512);
747        assert_eq!(
748            heap.container
749                .block_at_unchecked::<Header>(BlockIndex::HEADER)
750                .vmo_size()
751                .unwrap()
752                .unwrap() as usize,
753            heap.current_size()
754        );
755        let b = heap.allocate_block(2048).unwrap();
756        assert_eq!(*b, 640);
757        assert_eq!(
758            heap.container
759                .block_at_unchecked::<Header>(BlockIndex::HEADER)
760                .vmo_size()
761                .unwrap()
762                .unwrap() as usize,
763            heap.current_size()
764        );
765        assert_eq!(heap.failed_allocations, 0);
766        assert!(heap.allocate_block(2048).is_err());
767        assert_eq!(
768            heap.container
769                .block_at_unchecked::<Header>(BlockIndex::HEADER)
770                .vmo_size()
771                .unwrap()
772                .unwrap() as usize,
773            heap.current_size()
774        );
775        assert_eq!(heap.failed_allocations, 1);
776
777        assert!(heap.free_block(BlockIndex::from(128)).is_ok());
778        assert!(heap.free_block(BlockIndex::from(256)).is_ok());
779        assert!(heap.free_block(BlockIndex::from(384)).is_ok());
780        assert!(heap.free_block(BlockIndex::from(512)).is_ok());
781        assert!(heap.free_block(BlockIndex::from(640)).is_ok());
782        assert_eq!(
783            heap.container
784                .block_at_unchecked::<Header>(BlockIndex::HEADER)
785                .vmo_size()
786                .unwrap()
787                .unwrap() as usize,
788            heap.current_size()
789        );
790
791        assert!(heap.free_block(BlockIndex::HEADER).is_ok());
792
793        let expected = [
794            BlockDebug { index: 0.into(), order: 7, block_type: BlockType::Free },
795            BlockDebug { index: 128.into(), order: 7, block_type: BlockType::Free },
796            BlockDebug { index: 256.into(), order: 7, block_type: BlockType::Free },
797            BlockDebug { index: 384.into(), order: 7, block_type: BlockType::Free },
798            BlockDebug { index: 512.into(), order: 7, block_type: BlockType::Free },
799            BlockDebug { index: 640.into(), order: 7, block_type: BlockType::Free },
800        ];
801        validate(&expected, &heap);
802    }
803}
fuchsia_inspect/writer/heap.rs

fuchsia_inspect/writer/
heap.rs
