1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
use crate::bitvec::{Bitset, SubregionStatus};
use contracts::requires;
/// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for
/// more information.
///
/// This type is valid when zero-initialized.
#[derive(Debug)]
pub struct Tree<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> {
/// The base address of the tree.
pub base_ptr: *const [u8; PAGE_SIZE],
/// The log2 of the number of pages in the region represented by the tree.
pub size_class: usize,
/// The offset in the bitset to the bits responsible for this tree's pages.
pub bitset_offset: usize,
phantom: core::marker::PhantomData<&'buddy mut [u8; PAGE_SIZE]>,
}
impl<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize>
Tree<'buddy, PAGE_SIZE, PAGE_SIZE_BITS>
{
/// Reads a bit from the bitset.
#[requires(size_class <= self.size_class)]
#[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
#[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
pub fn bitset_get(
&self,
bitset: &mut Bitset,
size_class: usize,
offset_bytes: usize,
) -> SubregionStatus {
bitset.get(self.bitset_index(size_class, offset_bytes))
}
/// Returns the index of a bit in the bitset that corresponds to the given size class and
/// offset.
#[requires(size_class <= self.size_class)]
#[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
#[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
fn bitset_index(&self, size_class: usize, offset_bytes: usize) -> usize {
// We store the largest size classes first in the bitset. Count how many we are away from
// the largest.
let skipped_size_classes = self.size_class - size_class;
let bits_skipped_for_size_class = (1 << skipped_size_classes) - 1;
// Next, find our index in the size class.
let bits_skipped_for_index = offset_bytes >> (PAGE_SIZE_BITS + size_class);
// The sum of those two is simply our index.
bits_skipped_for_size_class + bits_skipped_for_index
}
/// Changes a bit in the bitset from `InFreeList` to `NotInFreeList`.
#[requires(size_class <= self.size_class)]
#[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
#[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
pub fn bitset_mark_as_absent(
&self,
bitset: &mut Bitset,
size_class: usize,
offset_bytes: usize,
) {
let index = self.bitset_index(size_class, offset_bytes);
assert_eq!(bitset.get(index), SubregionStatus::InFreeList);
bitset.set(index, SubregionStatus::NotInFreeList)
}
/// Changes a bit in the bitset from `NotInFreeList` to `InFreeList`.
#[requires(size_class <= self.size_class)]
#[requires(offset_bytes <= (PAGE_SIZE << self.size_class))]
#[requires(offset_bytes.trailing_zeros() as usize >= PAGE_SIZE_BITS + size_class)]
pub fn bitset_mark_as_present(
&self,
bitset: &mut Bitset,
size_class: usize,
offset_bytes: usize,
) {
let index = self.bitset_index(size_class, offset_bytes);
assert_eq!(bitset.get(index), SubregionStatus::NotInFreeList);
bitset.set(index, SubregionStatus::InFreeList)
}
/// Returns whether the tree contains an address.
pub fn contains(&self, addr: usize) -> bool {
let tree_addr_lo = self.base_ptr as usize;
let tree_addr_hi = tree_addr_lo + (PAGE_SIZE << self.size_class);
(tree_addr_lo..tree_addr_hi).contains(&addr)
}
}
|
