1use crate::AsmError;
14use crate::util::virtual_memory::{
15 self, DualMapping, MemoryFlags, alloc, alloc_dual_mapping, flush_instruction_cache, release,
16 release_dual_mapping,
17};
18use crate::util::{
19 align_down, align_up, bit_vector_clear, bit_vector_fill, bit_vector_get_bit,
20 bit_vector_index_of, bit_vector_set_bit,
21};
22use alloc::vec::Vec;
23use core::cell::{Cell, UnsafeCell};
24use core::mem::size_of;
25use core::ops::Range;
26use core::ptr::null_mut;
27
28#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
29#[repr(u32)]
30pub enum ResetPolicy {
32 Soft = 0,
34
35 Hard = 1,
37}
38#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub struct JitAllocatorOptions {
40 pub use_dual_mapping: bool,
51 pub use_multiple_pools: bool,
59 pub fill_unused_memory: bool,
64 pub immediate_release: bool,
70 pub custom_fill_pattern: Option<u32>,
71
72 pub block_size: u32,
73 pub granularity: u32,
74}
75
76impl Default for JitAllocatorOptions {
77 fn default() -> Self {
78 Self {
79 use_dual_mapping: true,
80 use_multiple_pools: true,
81 fill_unused_memory: true,
82 immediate_release: false,
83 custom_fill_pattern: None,
84 block_size: 0,
85 granularity: 0,
86 }
87 }
88}
89
90#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
91const DEFAULT_FILL_PATTERN: u32 = 0xCCCCCCCC; #[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
93const DEFAULT_FILL_PATTERN: u32 = 0x0; const MULTI_POOL_COUNT: usize = 3;
101
102const MIN_GRANULARITY: usize = 64;
104
105const MAX_BLOCK_SIZE: usize = 32 * 1024 * 1024;
107
108struct BitVectorRangeIterator<'a, const B: u32> {
109 slice: &'a [u32],
110 idx: usize,
111 end: usize,
112 bit_word: u32,
113}
114
115const BIT_WORD_SIZE: usize = core::mem::size_of::<u32>() * 8;
116
117impl<'a, const B: u32> BitVectorRangeIterator<'a, B> {
118 const XOR_MASK: u32 = if B == 0 { u32::MAX } else { 0 };
119
120 fn from_slice_and_nbitwords(data: &'a [u32], num_bit_words: usize) -> Self {
121 Self::new(data, num_bit_words, 0, num_bit_words * BIT_WORD_SIZE)
122 }
123
124 fn new(data: &'a [u32], _num_bit_words: usize, start: usize, end: usize) -> Self {
125 let idx = align_down(start, BIT_WORD_SIZE);
126 let slice = &data[idx / BIT_WORD_SIZE..];
127
128 let mut bit_word = 0;
129
130 if idx < end {
131 bit_word =
132 (slice[0] ^ Self::XOR_MASK) & (u32::MAX << (start as u32 % BIT_WORD_SIZE as u32));
133 }
134
135 Self {
136 slice,
137 idx,
138 end,
139 bit_word,
140 }
141 }
142
143 fn next_range(&mut self, range_hint: u32) -> Option<Range<u32>> {
144 while self.bit_word == 0 {
145 self.idx += BIT_WORD_SIZE;
146
147 if self.idx >= self.end {
148 return None;
149 }
150
151 self.slice = &self.slice[1..];
152 self.bit_word = self.slice[0] ^ Self::XOR_MASK;
153 }
154
155 let i = self.bit_word.trailing_zeros();
156 let start = self.idx as u32 + i;
157 self.bit_word = !(self.bit_word ^ !(u32::MAX << i));
158 let mut end;
159 if self.bit_word == 0 {
160 end = (self.idx as u32 + BIT_WORD_SIZE as u32).min(self.end as _);
161
162 while end.wrapping_sub(start) < range_hint {
163 self.idx += BIT_WORD_SIZE;
164
165 if self.idx >= self.end {
166 break;
167 }
168
169 self.slice = &self.slice[1..];
170 self.bit_word = self.slice[0] ^ Self::XOR_MASK;
171
172 if self.bit_word != u32::MAX {
173 let j = (!self.bit_word).trailing_zeros();
174 end = (self.idx as u32 + j).min(self.end as _);
175 self.bit_word &= u32::MAX << j;
176 break;
177 }
178
179 end = (self.idx as u32 + BIT_WORD_SIZE as u32).min(self.end as _);
180 self.bit_word = 0;
181 continue;
182 }
183
184 Some(start..end)
185 } else {
186 let j = self.bit_word.trailing_zeros();
187 end = (self.idx as u32 + j).min(self.end as _);
188
189 self.bit_word = !(self.bit_word ^ !(u32::MAX << j));
190
191 Some(start..end)
192 }
193 }
194}
195
196impl<'a> Iterator for BitVectorRangeIterator<'a, 0> {
197 type Item = Range<u32>;
198
199 fn next(&mut self) -> Option<Self::Item> {
200 self.next_range(u32::MAX)
201 }
202}
203
204use intrusive_collections::{KeyAdapter, UnsafeRef};
205use intrusive_collections::{intrusive_adapter, rbtree::*};
206
207struct JitAllocatorBlock {
208 node: Link,
209 list_node: intrusive_collections::LinkedListLink,
210
211 pool: *mut JitAllocatorPool,
213 mapping: DualMapping,
216 block_size: usize,
218
219 flags: Cell<u32>,
220 area_size: Cell<u32>,
221 area_used: Cell<u32>,
222 largest_unused_area: Cell<u32>,
223 search_start: Cell<u32>,
224 search_end: Cell<u32>,
225
226 used_bitvector: UnsafeCell<alloc::vec::Vec<u32>>,
227 stop_bitvector: UnsafeCell<alloc::vec::Vec<u32>>,
228}
229
230impl JitAllocatorBlock {
231 const FLAG_EMPTY: u32 = 0x00000001;
232 const FLAG_DIRTY: u32 = 0x00000002;
233 const FLAG_DUAL_MAPPED: u32 = 0x00000004;
234
235 fn pool(&self) -> *mut JitAllocatorPool {
236 self.pool
237 }
238
239 fn rx_ptr(&self) -> *const u8 {
240 self.mapping.rx
241 }
242
243 fn rw_ptr(&self) -> *mut u8 {
244 self.mapping.rw
245 }
246
247 fn flags(&self) -> u32 {
248 self.flags.get()
249 }
250
251 fn add_flags(&self, flags: u32) {
252 self.flags.set(self.flags() | flags);
253 }
254
255 fn clear_flags(&self, flags: u32) {
256 self.flags.set(self.flags() & !flags);
257 }
258
259 fn is_dirty(&self) -> bool {
260 (self.flags() & Self::FLAG_DIRTY) != 0
261 }
262
263 fn block_size(&self) -> usize {
264 self.block_size
265 }
266
267 fn area_used(&self) -> u32 {
268 self.area_used.get()
269 }
270
271 fn area_size(&self) -> u32 {
272 self.area_size.get()
273 }
274
275 fn largest_unused_area(&self) -> u32 {
276 self.largest_unused_area.get()
277 }
278
279 fn search_start(&self) -> u32 {
280 self.search_start.get()
281 }
282
283 fn search_end(&self) -> u32 {
284 self.search_end.get()
285 }
286
287 fn used_bitvector(&self) -> &alloc::vec::Vec<u32> {
288 unsafe { &*self.used_bitvector.get() }
294 }
295
296 fn stop_bitvector(&self) -> &alloc::vec::Vec<u32> {
297 unsafe { &*self.stop_bitvector.get() }
301 }
302
303 #[allow(clippy::mut_from_ref)]
304 fn used_bitvector_mut(&self) -> &mut alloc::vec::Vec<u32> {
305 unsafe { &mut *self.used_bitvector.get() }
310 }
311
312 #[allow(clippy::mut_from_ref)]
313 fn stop_bitvector_mut(&self) -> &mut alloc::vec::Vec<u32> {
314 unsafe { &mut *self.stop_bitvector.get() }
316 }
317
318 fn area_available(&self) -> u32 {
319 self.area_size() - self.area_used()
320 }
321
322 fn mark_allocated_area(&self, allocated_area_start: u32, allocated_area_end: u32) {
323 let allocated_area_size = allocated_area_end - allocated_area_start;
324
325 bit_vector_fill(
326 self.used_bitvector_mut(),
327 allocated_area_start as _,
328 allocated_area_size as _,
329 );
330 bit_vector_set_bit(
331 self.stop_bitvector_mut(),
332 allocated_area_end as usize - 1,
333 true,
334 );
335
336 unsafe {
341 (*self.pool).total_area_used += allocated_area_size as usize;
342 }
343
344 self.area_used.set(self.area_used() + allocated_area_size);
345
346 if self.area_available() == 0 {
347 self.search_start.set(self.area_size());
348 self.search_end.set(0);
349 self.largest_unused_area.set(0);
350 self.clear_flags(Self::FLAG_DIRTY);
351 } else {
352 if self.search_start.get() == allocated_area_start {
353 self.search_start.set(allocated_area_end as _);
354 }
355
356 if self.search_end.get() == allocated_area_end {
357 self.search_end.set(allocated_area_start as _);
358 }
359
360 self.add_flags(Self::FLAG_DIRTY);
361 }
362 }
363 fn mark_released_area(&self, released_area_start: u32, released_area_end: u32) {
364 let released_area_size = released_area_end - released_area_start;
365
366 unsafe {
370 (*self.pool).total_area_used -= released_area_size as usize;
371 }
372
373 self.area_used.set(self.area_used() - released_area_size);
374 self.search_start
375 .set(self.search_start.get().min(released_area_start));
376 self.search_end
377 .set(self.search_end.get().max(released_area_end));
378
379 bit_vector_clear(
380 self.used_bitvector_mut(),
381 released_area_start as _,
382 released_area_size as _,
383 );
384 bit_vector_set_bit(
385 self.stop_bitvector_mut(),
386 released_area_end as usize - 1,
387 false,
388 );
389
390 if self.area_used() == 0 {
391 self.search_start.set(0);
392 self.search_end.set(self.area_size());
393 self.largest_unused_area.set(self.area_size());
394 self.add_flags(Self::FLAG_EMPTY);
395 self.clear_flags(Self::FLAG_DIRTY);
396 } else {
397 self.add_flags(Self::FLAG_DIRTY);
398 }
399 }
400
401 fn mark_shrunk_area(&self, shrunk_area_start: u32, shrunk_area_end: u32) {
402 let shrunk_area_size = shrunk_area_end - shrunk_area_start;
403
404 assert!(shrunk_area_start != 0);
407 assert!(shrunk_area_end <= self.area_size());
408
409 unsafe {
413 (*self.pool).total_area_used -= shrunk_area_size as usize;
414 }
415
416 self.area_used.set(self.area_used() - shrunk_area_size);
417 self.search_start
418 .set(self.search_start.get().min(shrunk_area_start));
419 self.search_end
420 .set(self.search_end.get().max(shrunk_area_end));
421
422 bit_vector_clear(
423 self.used_bitvector_mut(),
424 shrunk_area_start as _,
425 shrunk_area_size as _,
426 );
427 bit_vector_set_bit(
428 self.stop_bitvector_mut(),
429 shrunk_area_end as usize - 1,
430 false,
431 );
432 bit_vector_set_bit(
433 self.stop_bitvector_mut(),
434 shrunk_area_start as usize - 1,
435 true,
436 );
437
438 self.add_flags(Self::FLAG_DIRTY);
439 }
440}
441
442impl PartialOrd for JitAllocatorBlock {
443 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
444 Some(self.cmp(other))
445 }
446}
447
448impl Ord for JitAllocatorBlock {
449 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
450 self.rx_ptr().cmp(&other.rx_ptr())
451 }
452}
453
454impl PartialEq for JitAllocatorBlock {
455 fn eq(&self, other: &Self) -> bool {
456 self.rx_ptr() == other.rx_ptr()
457 }
458}
459
460impl Eq for JitAllocatorBlock {}
461use intrusive_collections::linked_list::LinkedList;
462intrusive_adapter!(JitAllocatorBlockAdapter = UnsafeRef<JitAllocatorBlock> : JitAllocatorBlock { node: Link });
463intrusive_adapter!(BlockListAdapter = UnsafeRef<JitAllocatorBlock> : JitAllocatorBlock { list_node: intrusive_collections::LinkedListLink });
464
465struct BlockKey {
466 rxptr: *const u8,
467 block_size: u32,
468}
469
470impl PartialEq for BlockKey {
471 fn eq(&self, other: &Self) -> bool {
472 self.rxptr == other.rxptr
473 }
474}
475
476impl Eq for BlockKey {}
477
478impl PartialOrd for BlockKey {
479 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
480 Some(self.cmp(other))
481 }
482}
483
484impl Ord for BlockKey {
485 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
486 let addr_off = other.rxptr as usize + other.block_size as usize;
487
488 if addr_off <= self.rxptr as usize {
489 core::cmp::Ordering::Less
490 } else if other.rxptr > self.rxptr {
491 core::cmp::Ordering::Greater
492 } else {
493 core::cmp::Ordering::Equal
494 }
495 }
496}
497
498impl<'a> KeyAdapter<'a> for JitAllocatorBlockAdapter {
499 type Key = BlockKey;
500
501 fn get_key(
502 &self,
503 value: &'a <Self::PointerOps as intrusive_collections::PointerOps>::Value,
504 ) -> Self::Key {
505 BlockKey {
506 rxptr: value.rx_ptr(),
507 block_size: value.block_size as _,
508 }
509 }
510}
511
512struct JitAllocatorPool {
513 blocks: LinkedList<BlockListAdapter>,
514 cursor: *mut JitAllocatorBlock,
515
516 block_count: u32,
517 granularity: u16,
518 granularity_log2: u8,
519 empty_block_count: u8,
520 total_area_size: usize,
521 total_area_used: usize,
522 total_overhead_bytes: usize,
523}
524
525impl JitAllocatorPool {
526 fn new(granularity: u32) -> Self {
527 let granularity_log2 = granularity.trailing_zeros() as u8;
528 let granularity = granularity as u16;
529
530 Self {
531 blocks: LinkedList::new(BlockListAdapter::new()),
532 cursor: core::ptr::null_mut(),
533 block_count: 0,
534 granularity,
535 granularity_log2,
536 empty_block_count: 0,
537 total_area_size: 0,
538 total_area_used: 0,
539 total_overhead_bytes: 0,
540 }
541 }
542
543 fn reset(&mut self) {
544 self.blocks.clear();
545 self.cursor = core::ptr::null_mut();
546 self.block_count = 0;
547 self.empty_block_count = 0;
548 self.total_area_size = 0;
549 self.total_area_used = 0;
550 self.total_overhead_bytes = 0;
551 }
552
553 fn byte_size_from_area_size(&self, area_size: u32) -> usize {
554 area_size as usize * self.granularity as usize
555 }
556
557 fn area_size_from_byte_size(&self, byte_size: usize) -> u32 {
558 ((byte_size + self.granularity as usize - 1) >> self.granularity_log2) as u32
559 }
560
561 fn bit_word_count_from_area_size(&self, area_size: u32) -> usize {
562 align_up(area_size as _, 32) / 32
563 }
564}
565use alloc::boxed::Box;
566
567pub struct JitAllocator {
588 options: JitAllocatorOptions,
589 block_size: usize,
590 granulariy: usize,
591 fill_pattern: u32,
592
593 allocation_count: usize,
594 tree: RBTree<JitAllocatorBlockAdapter>,
595 pools: Box<[*mut JitAllocatorPool]>,
596}
597
598impl JitAllocator {
599 pub fn new(mut params: JitAllocatorOptions) -> Box<Self> {
601 let vm_info = virtual_memory::info();
602
603 #[cfg(not(windows))]
607 if virtual_memory::has_map_jit_support() {
608 params.use_dual_mapping = false;
609 }
610
611 let mut block_size = params.block_size;
612 let mut granularity = params.granularity;
613
614 let mut pool_count = 1;
615
616 if params.use_multiple_pools {
617 pool_count = MULTI_POOL_COUNT;
618 }
619
620 if !(64 * 1024..=MAX_BLOCK_SIZE as u32).contains(&block_size)
621 || !block_size.is_power_of_two()
622 {
623 block_size = vm_info.page_granularity as _;
624 }
625
626 if !(64..=256).contains(&granularity) || !granularity.is_power_of_two() {
627 granularity = MIN_GRANULARITY as _;
628 }
629
630 let fill_pattern = params.custom_fill_pattern.unwrap_or(DEFAULT_FILL_PATTERN);
631
632 let mut pools = Vec::with_capacity(pool_count);
633
634 for _ in 0..pool_count {
635 pools.push(Box::into_raw(Box::new(JitAllocatorPool::new(granularity))));
636 }
637
638 Box::new(Self {
639 options: params,
640 block_size: block_size as _,
641 granulariy: granularity as _,
642 fill_pattern,
643 allocation_count: 0,
644 tree: RBTree::new(JitAllocatorBlockAdapter::new()),
645 pools: pools.into_boxed_slice(),
646 })
647 }
648
649 fn size_to_pool_id(&self, size: usize) -> usize {
650 let mut pool_id = self.pools.len() - 1;
651 let mut granularity = self.granulariy << pool_id;
652
653 while pool_id != 0 {
654 if align_up(size, granularity) == size {
655 break;
656 }
657
658 pool_id -= 1;
659 granularity >>= 1;
660 }
661
662 pool_id
663 }
664
665 fn bitvector_size_to_byte_size(area_size: u32) -> usize {
666 (area_size as usize).div_ceil(32) * size_of::<u32>()
667 }
668
669 fn calculate_ideal_block_size(
670 &self,
671 pool: *mut JitAllocatorPool,
672 allocation_size: usize,
673 ) -> usize {
674 unsafe {
678 let last = (*pool).blocks.back();
679
680 let mut block_size = match last.get() {
681 Some(block) => block.block_size(),
682 None => self.block_size,
683 };
684
685 if block_size < MAX_BLOCK_SIZE {
686 block_size *= 2;
687 }
688
689 if allocation_size > block_size {
690 block_size = align_up(allocation_size, block_size);
691
692 if block_size < allocation_size {
694 return 0;
695 }
696 }
697
698 block_size
699 }
700 }
701
702 unsafe fn new_block(
711 &mut self,
712 pool: *mut JitAllocatorPool,
713 block_size: usize,
714 ) -> Result<Box<JitAllocatorBlock>, AsmError> {
715 unsafe {
720 let area_size =
721 (block_size + (*pool).granularity as usize - 1) >> (*pool).granularity_log2;
722 let num_bit_words = area_size.div_ceil(32);
723
724 let mut block = Box::new(JitAllocatorBlock {
725 node: Link::new(),
726 list_node: intrusive_collections::LinkedListLink::new(),
727 pool,
728 mapping: DualMapping {
729 rx: null_mut(),
730 rw: null_mut(),
731 },
732 block_size: block_size as _,
733 flags: Cell::new(0),
734 area_size: Cell::new(0),
735 area_used: Cell::new(0),
736 largest_unused_area: Cell::new(area_size as _),
737 search_end: Cell::new(area_size as _),
738 search_start: Cell::new(0),
739 used_bitvector: UnsafeCell::new(alloc::vec![0; num_bit_words]),
740 stop_bitvector: UnsafeCell::new(alloc::vec![0; num_bit_words]),
741 });
742 let mut block_flags = 0;
743 let virt_mem = if self.options.use_dual_mapping {
744 block_flags |= JitAllocatorBlock::FLAG_DUAL_MAPPED;
745 alloc_dual_mapping(block_size, MemoryFlags::ACCESS_RWX.into())?
746 } else {
747 let rx = alloc(block_size, MemoryFlags::ACCESS_RWX.into())?;
748 DualMapping { rx, rw: rx }
749 };
750
751 if self.options.fill_unused_memory {
752 virtual_memory::with_jit_write_access(|| {
753 fill_pattern(virt_mem.rw, self.fill_pattern, block_size);
754 });
755 let _ = flush_instruction_cache(virt_mem.rx, block_size);
756 }
757
758 block.area_size.set(area_size as _);
759 block.mapping = virt_mem;
760 block.flags.set(block_flags);
761 Ok(block)
762 }
763 }
764
765 unsafe fn delete_block(&mut self, block: *mut JitAllocatorBlock) {
773 unsafe {
780 let mut block = Box::from_raw(block);
781 if (block.flags() & JitAllocatorBlock::FLAG_DUAL_MAPPED) != 0 {
782 let _ = release_dual_mapping(&mut block.mapping, block.block_size);
783 } else {
784 let _ = release(block.mapping.rx as _, block.block_size);
785 }
786
787 drop(block);
788 }
789 }
790
791 unsafe fn insert_block(&mut self, block: *mut JitAllocatorBlock) {
800 unsafe {
805 let b = &mut *block;
806 let pool = &mut *b.pool();
807
808 if pool.cursor.is_null() {
809 pool.cursor = block;
810 }
811
812 self.tree.insert(UnsafeRef::from_raw(block));
813 pool.blocks.push_front(UnsafeRef::from_raw(block));
814
815 pool.block_count += 1;
816 pool.total_area_size += b.area_size() as usize;
817
818 pool.total_overhead_bytes += size_of::<JitAllocatorBlock>()
819 + Self::bitvector_size_to_byte_size(b.area_size()) * 2;
820 }
821 }
822
823 unsafe fn remove_block(
833 &mut self,
834 block: &mut intrusive_collections::linked_list::CursorMut<'_, BlockListAdapter>,
835 ) -> *mut JitAllocatorBlock {
836 unsafe {
841 let b = match block.get() {
842 Some(b) => b,
843 None => unreachable!("remove_block is only called on a positioned cursor"),
844 };
845 let pool = &mut *b.pool();
846
847 if core::ptr::eq(pool.cursor, b) {
848 pool.cursor = if let Some(block) = block.peek_prev().get() {
849 block as *const _ as *mut _
850 } else if let Some(block) = block.peek_next().get() {
851 block as *const _ as *mut _
852 } else {
853 null_mut()
854 };
855 }
856
857 if let Entry::Occupied(mut c) = self.tree.entry(&BlockKey {
858 rxptr: b.rx_ptr(),
859 block_size: b.block_size as _,
860 }) {
861 let removed = match c.remove() {
862 Some(removed) => removed,
863 None => unreachable!("an occupied tree entry always yields its block"),
864 };
865 assert_eq!(
866 UnsafeRef::into_raw(removed),
867 b as *const _ as *mut JitAllocatorBlock,
868 "blocks are not the same"
869 );
870 }
871 let area_size = b.area_size();
872
873 pool.block_count -= 1;
874 pool.total_area_size -= area_size as usize;
875
876 pool.total_overhead_bytes -=
877 size_of::<JitAllocatorBlock>() + Self::bitvector_size_to_byte_size(area_size) * 2;
878
879 match block.remove() {
880 Some(removed) => UnsafeRef::into_raw(removed),
881 None => unreachable!("a positioned cursor always removes its block"),
882 }
883 }
884 }
885
886 unsafe fn wipe_out_block(
895 &mut self,
896 block: &mut intrusive_collections::linked_list::CursorMut<'_, BlockListAdapter>,
897 ) {
898 unsafe {
903 let b = match block.get() {
904 Some(b) => b,
905 None => unreachable!("wipe_out_block is only called on a positioned cursor"),
906 };
907 if (b.flags() & JitAllocatorBlock::FLAG_EMPTY) != 0 {
908 return;
909 }
910
911 let pool = &mut *b.pool();
912
913 let area_size = b.area_size();
914 let granularity = pool.granularity;
915
916 virtual_memory::with_jit_write_access(|| {
917 if !self.options.fill_unused_memory {
918 return;
919 }
920 let rw_ptr = b.rw_ptr();
921
922 let it = BitVectorRangeIterator::from_slice_and_nbitwords(
923 b.stop_bitvector(),
924 pool.bit_word_count_from_area_size(b.area_size()),
925 );
926
927 for range in it {
928 let span_ptr = rw_ptr.add(range.start as usize * granularity as usize);
929 let span_size =
930 (range.end as usize - range.start as usize) * granularity as usize;
931
932 let mut n = 0;
933 while n < span_size {
934 *span_ptr.add(n).cast::<u32>() = self.fill_pattern;
940 n += size_of::<u32>();
941 }
942
943 let _ = virtual_memory::flush_instruction_cache(span_ptr, span_size);
944 }
945 });
946
947 let b = match block.get() {
948 Some(b) => b,
949 None => unreachable!("the cursor still points at the wiped block"),
950 };
951 b.used_bitvector_mut().fill(0);
952 b.stop_bitvector_mut().fill(0);
953
954 b.area_used.set(0);
955 b.largest_unused_area.set(area_size);
956 b.search_start.set(0);
957 b.search_end.set(area_size);
958 b.add_flags(JitAllocatorBlock::FLAG_EMPTY);
959 b.clear_flags(JitAllocatorBlock::FLAG_DIRTY);
960 }
961 }
962
963 pub unsafe fn reset(&mut self, reset_policy: ResetPolicy) {
973 let pool_count = self.pools.len();
974
975 for pool_id in 0..pool_count {
976 let pool = unsafe { &mut *self.pools[pool_id] };
981 let block_to_keep =
982 if reset_policy != ResetPolicy::Hard && !self.options.immediate_release {
983 let mut cursor = pool.blocks.cursor();
984 cursor.move_next();
985 cursor
986 .get()
987 .map(|block| block as *const JitAllocatorBlock as *mut JitAllocatorBlock)
988 } else {
989 None
990 };
991
992 unsafe {
998 let mut cursor = pool.blocks.cursor_mut();
999 cursor.move_next();
1000 while !cursor.is_null() {
1001 let block = match cursor.get() {
1002 Some(block) => block as *const JitAllocatorBlock as *mut JitAllocatorBlock,
1003 None => unreachable!("a non-null cursor always has a current block"),
1004 };
1005 if Some(block) != block_to_keep {
1006 let block = self.remove_block(&mut cursor);
1007 self.delete_block(block);
1008 } else {
1009 cursor.move_next();
1010 }
1011 }
1012
1013 if let Some(block) = block_to_keep {
1014 let mut cursor = pool.blocks.cursor_mut_from_ptr(&*block);
1018 self.wipe_out_block(&mut cursor);
1019 pool.cursor = block;
1020 pool.empty_block_count = 1;
1021 pool.total_area_used = 0;
1022 } else {
1023 pool.reset();
1024 }
1025 }
1026 }
1027
1028 self.allocation_count = 0;
1029 }
1030
1031 pub fn alloc(&mut self, size: usize) -> Result<Span, AsmError> {
1036 const NO_INDEX: u32 = u32::MAX;
1037
1038 let size = align_up(size, self.granulariy);
1039
1040 if size == 0 {
1041 return Err(AsmError::InvalidArgument);
1042 }
1043
1044 if size > u32::MAX as usize / 2 {
1045 return Err(AsmError::TooLarge);
1046 }
1047
1048 unsafe {
1052 let pool_id = self.size_to_pool_id(size);
1053 let pool = &mut *self.pools[pool_id];
1054
1055 let mut area_index = NO_INDEX;
1056 let area_size = pool.area_size_from_byte_size(size);
1057
1058 let mut block = pool.blocks.cursor();
1059 block.move_next();
1060 if let Some(initial) = block.get().map(|x| x as *const JitAllocatorBlock) {
1061 loop {
1062 let b = match block.get() {
1063 Some(b) => b,
1064 None => unreachable!("the cursor was positioned on a block"),
1065 };
1066
1067 if b.area_available() >= area_size
1068 && (b.is_dirty() || b.largest_unused_area() >= area_size)
1069 {
1070 let mut it = BitVectorRangeIterator::<0>::new(
1071 b.used_bitvector(),
1072 pool.bit_word_count_from_area_size(b.area_size()),
1073 b.search_start() as _,
1074 b.search_end() as _,
1075 );
1076
1077 let mut range_start;
1078 let mut range_end = b.area_size() as usize;
1079
1080 let mut search_start = usize::MAX;
1081 let mut largest_area = 0;
1082
1083 while let Some(range) = it.next_range(area_size as _) {
1084 range_start = range.start as _;
1085 range_end = range.end as _;
1086
1087 let range_size = range_end - range_start;
1088
1089 if range_size >= area_size as usize {
1090 area_index = range_start as _;
1091 break;
1092 }
1093
1094 search_start = search_start.min(range_start);
1095 largest_area = largest_area.max(range_size);
1096 }
1097
1098 if area_index != NO_INDEX {
1099 break;
1100 }
1101
1102 if search_start != usize::MAX {
1103 let search_end = range_end;
1104
1105 b.search_start.set(search_start as _);
1106
1107 b.search_end.set(search_end as _);
1108 b.largest_unused_area.set(largest_area as _);
1109 b.clear_flags(JitAllocatorBlock::FLAG_DIRTY);
1110 }
1111 }
1112
1113 block.move_next();
1114
1115 if block.get().map(|x| x as *const _) == Some(initial) {
1116 break;
1117 }
1118
1119 if block.is_null() {
1120 break;
1121 }
1122 }
1123 }
1124
1125 let mut block = block.get();
1126
1127 if area_index == NO_INDEX {
1128 let block_size = self.calculate_ideal_block_size(pool, size);
1129
1130 {
1131 let nblock = self.new_block(pool, block_size)?;
1132
1133 area_index = 0;
1134
1135 nblock.search_start.set(area_size as _);
1136
1137 nblock
1138 .largest_unused_area
1139 .set(nblock.area_size() - area_size);
1140
1141 let nblock = Box::into_raw(nblock);
1142
1143 self.insert_block(nblock);
1144
1145 block = Some(&*nblock);
1146 }
1147 } else {
1148 let b = match block {
1149 Some(b) => b,
1150 None => unreachable!("area_index was found in an existing block"),
1151 };
1152 if (b.flags() & JitAllocatorBlock::FLAG_EMPTY) != 0 {
1153 pool.empty_block_count -= 1;
1154 b.clear_flags(JitAllocatorBlock::FLAG_EMPTY);
1155 }
1156 }
1157
1158 self.allocation_count += 1;
1159
1160 let block = match block {
1161 Some(block) => block,
1162 None => unreachable!("a block is selected when area_index is valid"),
1163 };
1164
1165 block.mark_allocated_area(area_index, area_index + area_size);
1166
1167 let offset = pool.byte_size_from_area_size(area_index);
1168
1169 Ok(Span {
1173 rx: block.rx_ptr().add(offset),
1174 rw: block.rw_ptr().add(offset),
1175 size,
1176 block: block as *const JitAllocatorBlock as *mut u8,
1177 icache_clean: true,
1178 })
1179 }
1180 }
1181
1182 pub unsafe fn release(&mut self, rx_ptr: *const u8) -> Result<(), AsmError> {
1191 if rx_ptr.is_null() {
1192 return Err(AsmError::InvalidArgument);
1193 }
1194
1195 let block = self.tree.find(&BlockKey {
1196 rxptr: rx_ptr,
1197 block_size: 0,
1198 });
1199
1200 let Some(block) = block.get() else {
1201 return Err(AsmError::InvalidState);
1202 };
1203
1204 unsafe {
1212 let pool = &mut *block.pool;
1213
1214 let offset = rx_ptr as usize - block.rx_ptr() as usize;
1215 if offset % pool.granularity as usize != 0 {
1216 return Err(AsmError::InvalidArgument);
1217 }
1218
1219 let area_index = (offset >> pool.granularity_log2 as usize) as u32;
1220 let is_allocation_start = bit_vector_get_bit(block.used_bitvector(), area_index as _)
1221 && (area_index == 0
1222 || !bit_vector_get_bit(block.used_bitvector(), area_index as usize - 1)
1223 || bit_vector_get_bit(block.stop_bitvector(), area_index as usize - 1));
1224 if !is_allocation_start {
1225 return Err(AsmError::InvalidArgument);
1226 }
1227 let area_end =
1228 bit_vector_index_of(block.stop_bitvector(), area_index as _, true) as u32 + 1;
1229 let area_size = area_end - area_index;
1230
1231 self.allocation_count -= 1;
1232
1233 block.mark_released_area(area_index, area_end);
1234
1235 if self.options.fill_unused_memory {
1236 let span_ptr = block
1237 .rw_ptr()
1238 .add(area_index as usize * pool.granularity as usize);
1239 let span_size = area_size as usize * pool.granularity as usize;
1240
1241 virtual_memory::with_jit_write_access(|| {
1242 fill_pattern(span_ptr, self.fill_pattern, span_size);
1243 });
1244 let _ = flush_instruction_cache(
1245 block
1246 .rx_ptr()
1247 .add(area_index as usize * pool.granularity as usize),
1248 span_size,
1249 );
1250 }
1251
1252 if block.area_used() == 0 {
1253 if pool.empty_block_count != 0 || self.options.immediate_release {
1254 let mut cursor = pool.blocks.cursor_mut_from_ptr(block);
1255 let block = self.remove_block(&mut cursor);
1256
1257 self.delete_block(block);
1258 } else {
1259 pool.empty_block_count += 1;
1260 }
1261 }
1262 }
1263
1264 Ok(())
1265 }
1266 pub unsafe fn shrink(&mut self, span: &mut Span, new_size: usize) -> Result<(), AsmError> {
1275 let rx_ptr = span.rx;
1276 if rx_ptr.is_null() {
1277 return Err(AsmError::InvalidArgument);
1278 }
1279
1280 if new_size == 0 {
1281 unsafe { self.release(rx_ptr)? };
1283 span.size = 0;
1284 return Ok(());
1285 }
1286
1287 let Some(block) = self
1288 .tree
1289 .find(&BlockKey {
1290 rxptr: rx_ptr,
1291 block_size: 0,
1292 })
1293 .get()
1294 else {
1295 return Err(AsmError::InvalidArgument);
1296 };
1297
1298 unsafe {
1304 let pool = &mut *block.pool;
1305 let offset = rx_ptr as usize - block.rx_ptr() as usize;
1306 if offset % pool.granularity as usize != 0 {
1307 return Err(AsmError::InvalidArgument);
1308 }
1309 let area_start = (offset >> pool.granularity_log2 as usize) as u32;
1310
1311 let is_allocation_start = bit_vector_get_bit(block.used_bitvector(), area_start as _)
1312 && (area_start == 0
1313 || !bit_vector_get_bit(block.used_bitvector(), area_start as usize - 1)
1314 || bit_vector_get_bit(block.stop_bitvector(), area_start as usize - 1));
1315 if !is_allocation_start {
1316 return Err(AsmError::InvalidArgument);
1317 }
1318
1319 let area_end =
1320 bit_vector_index_of(block.stop_bitvector(), area_start as _, true) as u32 + 1;
1321
1322 let area_prev_size = area_end - area_start;
1323 let area_shrunk_size = pool.area_size_from_byte_size(new_size);
1324
1325 if area_shrunk_size > area_prev_size {
1326 return Err(AsmError::InvalidState);
1327 }
1328
1329 let area_diff = area_prev_size - area_shrunk_size;
1330
1331 if area_diff != 0 {
1332 block.mark_shrunk_area(area_start + area_shrunk_size, area_end);
1333
1334 if self.options.fill_unused_memory {
1335 let area_offset =
1336 (area_start + area_shrunk_size) as usize * pool.granularity as usize;
1337 let span_ptr = block.rw_ptr().add(area_offset);
1338 let span_size = area_diff as usize * pool.granularity as usize;
1339
1340 virtual_memory::with_jit_write_access(|| {
1341 fill_pattern(span_ptr, self.fill_pattern, span_size);
1342 });
1343 let _ = flush_instruction_cache(block.rx_ptr().add(area_offset), span_size);
1344 }
1345 }
1346
1347 span.size = pool.byte_size_from_area_size(area_shrunk_size);
1348 }
1349
1350 Ok(())
1351 }
1352
1353 pub fn query(&self, rx_ptr: *const u8) -> Result<Span, AsmError> {
1356 let Some(block) = self
1357 .tree
1358 .find(&BlockKey {
1359 rxptr: rx_ptr,
1360 block_size: 0,
1361 })
1362 .get()
1363 else {
1364 return Err(AsmError::InvalidArgument);
1365 };
1366
1367 unsafe {
1372 let pool = &mut *block.pool;
1373 let offset = rx_ptr as usize - block.rx_ptr() as usize;
1374 if offset % pool.granularity as usize != 0 {
1375 return Err(AsmError::InvalidArgument);
1376 }
1377
1378 let area_start = (offset >> pool.granularity_log2 as usize) as u32;
1379
1380 let is_allocation_start = bit_vector_get_bit(block.used_bitvector(), area_start as _)
1381 && (area_start == 0
1382 || !bit_vector_get_bit(block.used_bitvector(), area_start as usize - 1)
1383 || bit_vector_get_bit(block.stop_bitvector(), area_start as usize - 1));
1384 if !is_allocation_start {
1385 return Err(AsmError::InvalidArgument);
1386 }
1387
1388 let area_end =
1389 bit_vector_index_of(block.stop_bitvector(), area_start as _, true) as u32 + 1;
1390 let byte_offset = pool.byte_size_from_area_size(area_start);
1391 let byte_size = pool.byte_size_from_area_size(area_end - area_start);
1392
1393 Ok(Span {
1394 rx: block.rx_ptr().add(byte_offset),
1395 rw: block.rw_ptr().add(byte_offset),
1396 size: byte_size,
1397 block: block as *const JitAllocatorBlock as *mut u8,
1398 icache_clean: true,
1399 })
1400 }
1401 }
1402
1403 pub unsafe fn write(
1414 &mut self,
1415 span: &mut Span,
1416 write_func: impl FnOnce(&mut Span),
1417 ) -> Result<(), AsmError> {
1418 if span.size == 0 {
1419 return Ok(());
1420 }
1421
1422 span.icache_clean = false;
1423 virtual_memory::with_jit_write_access(|| write_func(span));
1424 unsafe { flush_instruction_cache(span.rx, span.size)? };
1426 span.icache_clean = true;
1427 Ok(())
1428 }
1429
1430 pub unsafe fn copy_from_slice(
1439 &mut self,
1440 span: &mut Span,
1441 offset: usize,
1442 slice: &[u8],
1443 ) -> Result<(), AsmError> {
1444 let end = offset
1445 .checked_add(slice.len())
1446 .ok_or(AsmError::InvalidArgument)?;
1447 if end > span.size {
1448 return Err(AsmError::InvalidArgument);
1449 }
1450 if slice.is_empty() {
1451 return Ok(());
1452 }
1453
1454 span.icache_clean = false;
1455 unsafe {
1459 virtual_memory::with_jit_write_access(|| {
1460 span.rw
1461 .add(offset)
1462 .copy_from_nonoverlapping(slice.as_ptr(), slice.len());
1463 });
1464 flush_instruction_cache(span.rx.add(offset), slice.len())?;
1465 }
1466 span.icache_clean = true;
1467 Ok(())
1468 }
1469}
1470
1471impl Drop for JitAllocator {
1472 fn drop(&mut self) {
1473 unsafe {
1479 self.reset(ResetPolicy::Hard);
1480 for pool in &mut self.pools {
1481 drop(Box::from_raw(*pool));
1482 }
1483 }
1484 }
1485}
1486
1487#[inline]
1494unsafe fn fill_pattern(mem: *mut u8, pattern: u32, size_in_bytes: usize) {
1495 let n = size_in_bytes / 4;
1496
1497 let p = mem as *mut u32;
1498
1499 for i in 0..n {
1500 unsafe {
1503 p.add(i).write(pattern);
1504 }
1505 }
1506}
1507
1508#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1514pub struct Span {
1515 rx: *const u8,
1516 rw: *mut u8,
1517 size: usize,
1518 block: *mut u8,
1519 icache_clean: bool,
1520}
1521
1522impl Span {
1523 pub const fn rx(&self) -> *const u8 {
1527 self.rx
1528 }
1529 pub const fn rw(&self) -> *mut u8 {
1539 self.rw
1540 }
1541
1542 pub const fn size(&self) -> usize {
1543 self.size
1544 }
1545
1546 pub const fn block(&self) -> *mut u8 {
1548 self.block
1549 }
1550
1551 pub const fn is_icache_clean(&self) -> bool {
1552 self.icache_clean
1553 }
1554
1555 pub const fn is_directly_writeable(&self) -> bool {
1556 !self.rw.is_null()
1557 }
1558}