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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
use crate::allocators::{
buddy::{
bitvec::BitVec,
stripe::{FreeListNode, Stripe},
MAX_ORDER,
},
PAGE_SIZE_BITS,
};
use contracts::requires;
use core::ptr::NonNull;
/// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for
/// more information.
pub struct Tree<'buddy> {
/// The base address of the tree.
pub base: *const (),
/// The log2 of the number of pages in the region represented by the tree.
pub log2_page_count: usize,
/// The array of sentinel nodes of the free-list for this node. As an invariant of the type,
/// there are no live references to any node in any list in this array, and there are
/// MAX_ORDER + 1 nodes.
pub free_lists: NonNull<FreeListNode>,
/// The bitset used to track whether subregion are allocated or not in this tree.
pub bitset: &'buddy mut BitVec,
}
impl<'buddy> Tree<'buddy> {
/// Tries to allocate a subregion with the given order, possibly splitting a larger subregion
/// in order to so so.
#[requires(order <= MAX_ORDER)]
pub fn alloc(&mut self, order: usize) -> Option<NonNull<FreeListNode>> {
if let Some(ptr) = self.stripe(order).pop() {
Some(ptr)
} else if order == MAX_ORDER {
None
} else {
// Get a larger region.
let ptr = self.alloc(order + 1)?;
// Get a pointer to the higher half.
//
// SAFETY: This has to be in-bounds, it's part of the same allocation!
let higher_half = unsafe { ptr.byte_add(1 << (PAGE_SIZE_BITS + order)) };
// Put the higher half in the current buddy's stripe.
//
// SAFETY: The higher half is from this region, not in the higher stripe, and of the
// right size.
unsafe {
self.stripe(order).push(higher_half);
}
// Return the pointer.
Some(ptr)
}
}
/// Returns the stripe with the given order.
#[requires(order <= MAX_ORDER)]
fn stripe<'stripe>(&'stripe mut self, order: usize) -> Stripe<'stripe> {
// TODO: There should be some smart bitwise-math version of this...
let mut bitset_offset = 0;
for i in 0..order {
bitset_offset += (1 << self.log2_page_count) >> i;
}
Stripe {
base: self.base,
order,
// SAFETY: order is constrained to be in-bounds.
free_list: unsafe { self.free_lists.add(order) },
bitset: self.bitset,
bitset_offset,
}
}
}
/// Evil bitwise version of the reasonable loop to compute the `bitset_offset` of a stripe.
#[requires(log2_page_count < usize::BITS as usize)]
#[requires(order < usize::BITS as usize)]
fn compute_bitset_offset(log2_page_count: usize, order: usize) -> usize {
let ones = |i: usize| !(usize::MAX << i);
if order > log2_page_count + 1 {
ones(log2_page_count + 1)
} else {
ones(order).wrapping_shl((log2_page_count + 1 - order) as u32)
}
}
#[test]
fn compute_bitset_offset_test() {
fn compute_bitset_offset_loop(log2_page_count: usize, order: usize) -> usize {
let mut bitset_offset = 0;
for i in 0..order {
bitset_offset += (1 << log2_page_count) >> i;
}
bitset_offset
}
for log2_page_count in 0..64 {
for order in 0..64 {
assert_eq!(
compute_bitset_offset(log2_page_count, order),
compute_bitset_offset_loop(log2_page_count, order),
);
}
}
}
|
