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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
/// 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,
// /// The bitset used to track whether subregion are allocated or not in this tree.
// pub bitset: &'buddy mut BitVec,
phantom: core::marker::PhantomData<&'buddy mut [u8; PAGE_SIZE]>,
}
/*
use crate::{
bitvec::BitVec,
stripe::{FreeListNode, Stripe},
MAX_ORDER, PAGE_SIZE_BITS,
};
use contracts::requires;
/// 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),
);
}
}
}
*/
|
