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

fuchsia_inspect/writer/
heap.rs
