1use crate::block::{BlockError, Block};
2use crate::allocator::AllocError;
3use crate::constants;
4
5use std::ptr::write;
6
7impl From<BlockError> for AllocError {
8 fn from(error: BlockError) -> AllocError {
9 match error {
10 BlockError::BadRequest => AllocError::BadRequest,
11 BlockError::OOM => AllocError::OOM,
12 }
13 }
14}
15
16pub struct BumpBlock {
17 block: Block,
18 cursor: *const u8,
19 limit: *const u8
20}
21
22impl BumpBlock {
23 pub fn new() -> Result<BumpBlock, AllocError> {
24 let block = Block::new(constants::BLOCK_SIZE)?;
25 let limit = block.as_ptr();
26 let cursor = unsafe { limit.add(constants::BLOCK_CAPACITY) };
27 let mut bump_block = BumpBlock { block, cursor, limit};
28
29 bump_block.reset();
30
31 Ok(bump_block)
32 }
33
34 pub fn inner_alloc(&mut self, alloc_size: usize) -> Option<*const u8> {
35 let ptr = self.cursor as usize;
36 let limit = self.limit as usize;
37 let next_ptr = ptr.checked_sub(alloc_size)? & constants::ALLOC_ALIGN_MASK;
38
39 if next_ptr < limit {
40 let block_relative_limit =
41 unsafe { self.limit.sub(self.block.as_ptr() as usize) } as usize;
42
43 if block_relative_limit > 0 {
44 if let Some((cursor, limit)) = self
45 .find_next_available_hole(block_relative_limit, alloc_size)
46 {
47 self.cursor = unsafe { self.block.as_ptr().add(cursor) };
48 self.limit = unsafe { self.block.as_ptr().add(limit) };
49 return self.inner_alloc(alloc_size);
50 }
51 }
52
53 None
54 } else {
55 self.cursor = next_ptr as *const u8;
56 Some(self.cursor)
57 }
58 }
59
60 fn find_next_available_hole(
61 &self,
62 starting_at: usize,
63 alloc_size: usize,
64 ) -> Option<(usize, usize)> {
65 let mut count = 0;
66 let starting_line = starting_at / constants::LINE_SIZE;
67 let lines_required = (alloc_size + constants::LINE_SIZE - 1) / constants::LINE_SIZE;
68 let mut end = starting_line;
69
70 for index in (0..starting_line).rev() {
71 let marked = unsafe { *self.block.as_ptr().add(constants::META_OFFSET + index) };
72
73 if marked == 0 {
74 count += 1;
75
76 if index == 0 && count >= lines_required {
77 let limit = 0;
78 let cursor = end * constants::LINE_SIZE;
79 return Some((cursor, limit));
80 }
81 } else {
82 if count > lines_required {
83 let limit = (index + 2) * constants::LINE_SIZE;
84 let cursor = end * constants::LINE_SIZE;
85 return Some((cursor, limit));
86 }
87
88 count = 0;
89 end = index;
90 }
91 }
92
93 None
94 }
95
96 pub fn mark_line(&mut self, line_num: usize) {
97 if constants::LINE_COUNT <= line_num {
98 panic!("ALLOC ERROR: tried marking non existent line");
99 }
100
101 let line_marker = unsafe { self.block.as_ptr().add(constants::META_OFFSET + line_num) as *mut u8 };
102
103 unsafe { *line_marker = constants::MARKED; };
104 }
105
106 pub fn mark_block(&mut self) {
107 let block_marker = unsafe { self.block.as_ptr().add(constants::BLOCK_SIZE - 1) as *mut u8 };
108
109 unsafe { *block_marker = constants::MARKED; };
110
111 }
112
113 pub fn reset(&mut self) {
114 self.limit = self.block.as_ptr();
115 self.cursor = unsafe { self.limit.add(constants::BLOCK_CAPACITY) };
116
117 unsafe {
118 for i in 0..128 {
119 *(self.block.as_ptr().add(constants::META_OFFSET + i) as *mut u8)
120 = constants::FREE;
121 }
122 }
123 }
124
125 unsafe fn write<T>(&mut self, object: T, offset: usize) -> *const T {
126 let p = self.block.as_ptr().add(offset) as *mut T;
127 write(p, object);
128 p
129 }
130
131 pub fn current_hole_size(&self) -> usize {
132 self.cursor as usize - self.limit as usize
133 }
134}
135
136#[cfg(test)]
137mod tests {
138 use super::*;
139 use std::mem::size_of;
140
141 #[test]
142 fn test_begins_with_full_capacity() {
143 let b = BumpBlock::new().unwrap();
144
145 assert!(b.current_hole_size() == constants::BLOCK_CAPACITY);
146 }
147
148 #[test]
149 fn test_writes_obj() {
150 let mut b = BumpBlock::new().unwrap();
151 let important_number = 69;
152 let ptr = unsafe { b.write(important_number, 420) };
153 let val = unsafe { *ptr };
154
155 assert!(val == important_number);
156 }
157
158 #[test]
159 fn test_find_next_hole() {
160 let mut block = BumpBlock::new().unwrap();
161
162 block.mark_line(0);
163 block.mark_line(1);
164 block.mark_line(2);
165 block.mark_line(4);
166 block.mark_line(10);
167
168 let expect = Some((10 * constants::LINE_SIZE, 6 * constants::LINE_SIZE));
169
170 let got = block.find_next_available_hole(10 * constants::LINE_SIZE, constants::LINE_SIZE);
171
172 println!("test_find_next_hole got {:?} expected {:?}", got, expect);
173
174 assert!(got == expect);
175 }
176
177 #[test]
178 fn test_find_next_hole_at_line_zero() {
179 let mut block = BumpBlock::new().unwrap();
180
181 block.mark_line(3);
182 block.mark_line(4);
183 block.mark_line(5);
184
185 let expect = Some((3 * constants::LINE_SIZE, 0));
186
187 let got = block.find_next_available_hole(3 * constants::LINE_SIZE, constants::LINE_SIZE);
188
189 println!(
190 "test_find_next_hole_at_line_zero got {:?} expected {:?}",
191 got, expect
192 );
193
194 assert!(got == expect);
195 }
196
197 #[test]
198 fn test_find_next_hole_at_block_end() {
199 let mut block = BumpBlock::new().unwrap();
200
201 let halfway = constants::LINE_COUNT / 2;
202
203 for i in halfway..constants::LINE_COUNT {
204 block.mark_line(i);
205 }
206
207 let expect = Some((halfway * constants::LINE_SIZE, 0));
208
209 let got = block.find_next_available_hole(constants::BLOCK_CAPACITY, constants::LINE_SIZE);
210
211 println!(
212 "test_find_next_hole_at_block_end got {:?} expected {:?}",
213 got, expect
214 );
215
216 assert!(got == expect);
217 }
218
219
220 #[test]
221 fn test_find_hole_all_conservatively_marked() {
222 let mut block = BumpBlock::new().unwrap();
223
224 for i in 0..constants::LINE_COUNT {
225 if i % 2 == 0 {
226 block.mark_line(i);
227 }
228 }
229
230 let got = block.find_next_available_hole(constants::BLOCK_CAPACITY, constants::LINE_SIZE);
231
232 println!(
233 "test_find_hole_all_conservatively_marked got {:?} expected None",
234 got
235 );
236
237 assert!(got == None);
238 }
239
240
241 #[test]
242 fn test_find_entire_block() {
243 let block = BumpBlock::new().unwrap();
244
245 let expect = Some((constants::BLOCK_CAPACITY, 0));
246 let got = block.find_next_available_hole(constants::BLOCK_CAPACITY, constants::LINE_SIZE);
247
248 println!("test_find_entire_block got {:?} expected {:?}", got, expect);
249
250 assert!(got == expect);
251 }
252
253 #[test]
254 fn test_mark_line_overflow_panics() {
255 let mut block = BumpBlock::new().unwrap();
256
257 block.mark_line(126); let result = std::panic::catch_unwind(move || block.mark_line(127));
260
261 assert!(result.is_err());
262 }
263
264 #[test]
265 fn test_alloc_empty_block() {
266 let mut block = BumpBlock::new().unwrap();
267 let alloc_size = 8;
268 let ptr = block.inner_alloc(alloc_size).unwrap();
269
270 assert!(block.current_hole_size() == (constants::BLOCK_CAPACITY - 8));
271 assert!(ptr == unsafe { block.block.as_ptr().add(constants::BLOCK_CAPACITY - 8) });
272 }
273
274 #[test]
275 fn test_block_write() {
276 let mut block = BumpBlock::new().unwrap();
277 let my_bytes: [u8; 4] = [1, 2, 3, 4];
278 let ptr = block.inner_alloc(4).unwrap();
279 let ptr_offset = (ptr as usize) - (block.block.as_ptr() as usize);
280 let my_written_bytes = unsafe { *block.write::<[u8; 4]>(my_bytes, ptr_offset) };
281
282 assert!(my_written_bytes == my_bytes);
283 }
284
285 #[test]
286 fn test_block_alloc_aligns_to_usize() {
287 let mut block = BumpBlock::new().unwrap();
288 let alloc_size = 1;
289 let mut ptr = block.inner_alloc(alloc_size).unwrap();
290
291 assert!(block.current_hole_size() == (constants::BLOCK_CAPACITY - size_of::<usize>()));
292 assert!(ptr == unsafe { block.block.as_ptr().add(constants::BLOCK_CAPACITY - size_of::<usize>()) });
293
294 ptr = block.inner_alloc(alloc_size).unwrap();
295
296 assert!(block.current_hole_size() == (constants::BLOCK_CAPACITY - (size_of::<usize>() * 2)));
297 assert!(ptr == unsafe { block.block.as_ptr().add(constants::BLOCK_CAPACITY - (size_of::<usize>() * 2)) });
298 }
299
300 #[test]
301 fn test_alloc_on_full_block() {
302 let mut block = BumpBlock::new().unwrap();
303 let alloc_size = 128;
304
305 for i in 1..=constants::LINE_COUNT {
306 let ptr = block.inner_alloc(alloc_size).unwrap();
307 let cursor = i * 128;
308
309 assert!(block.current_hole_size() == (constants::BLOCK_CAPACITY - cursor));
310 assert!(ptr == unsafe { block.block.as_ptr().add(constants::BLOCK_CAPACITY - cursor) });
311 }
312
313 let ptr = block.inner_alloc(1);
314 assert!(ptr.is_none());
315 }
316
317 #[test]
318 fn test_reset() {
319 let mut block = BumpBlock::new().unwrap();
320
321 block.cursor = block.limit;
322
323 for i in 0..constants::LINE_COUNT {
324 block.mark_line(i);
325 }
326
327 let ptr = block.inner_alloc(1);
328 println!("{:?}", ptr);
329 assert!(ptr.is_none());
330block.reset();
331
332 let ptr = block.inner_alloc(1).unwrap();
333 assert!(block.current_hole_size() == (constants::BLOCK_CAPACITY - 8));
334 assert!(ptr == unsafe { block.block.as_ptr().add(constants::BLOCK_CAPACITY - 8) });
335 }
336}