fuchsia_inspect/writer/
heap.rs

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

fuchsia_inspect/writer/
heap.rs
