Skip to main content

asmkit/core/
jit_allocator.rs

1/* Copyright (c) 2008-2024 The AsmJit Authors
2
3   This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software.
4
5   Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions:
6
7   The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
8   Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
9   This notice may not be removed or altered from any source distribution.
10
11*/
12
13use 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)]
30/// A policy that can be used with `reset()` functions.
31pub enum ResetPolicy {
32    /// Soft reset, does not deeallocate memory (default).
33    Soft = 0,
34
35    /// Hard reset, releases all memory used, if any.
36    Hard = 1,
37}
38#[derive(Clone, Copy, Debug, PartialEq, Eq)]
39pub struct JitAllocatorOptions {
40    /// Enables the use of an anonymous memory-mapped memory that is mapped into two buffers having a different pointer.
41    /// The first buffer has read and execute permissions and the second buffer has read+write permissions.
42    ///
43    /// See the internal `alloc_dual_mapping` implementation for details about this feature.
44    ///
45    /// ## Remarks
46    ///
47    /// Dual mapping would be automatically turned on by [JitAllocator] in case of hardened runtime that
48    /// enforces `W^X` policy, so specifying this flag is essentually forcing to use dual mapped pages even when RWX
49    /// pages can be allocated and dual mapping is not necessary.
50    pub use_dual_mapping: bool,
51    /// Enables the use of multiple pools with increasing granularity instead of a single pool. This flag would enable
52    /// 3 internal pools in total having 64, 128, and 256 bytes granularity.
53    ///
54    /// This feature is only recommended for users that generate a lot of code and would like to minimize the overhead
55    /// of `JitAllocator` itself by having blocks of different allocation granularities. Using this feature only for
56    /// few allocations won't pay off as the allocator may need to create more blocks initially before it can take the
57    /// advantage of variable block granularity.
58    pub use_multiple_pools: bool,
59    /// Always fill reserved memory by a fill-pattern.
60    ///
61    /// Causes a new block to be cleared by the fill pattern and freshly released memory to be cleared before making
62    /// it ready for another use.
63    pub fill_unused_memory: bool,
64    /// When this flag is set the allocator would immediately release unused blocks during `release()` or `reset()`.
65    /// When this flag is not set the allocator would keep one empty block in each pool to prevent excessive virtual
66    /// memory allocations and deallocations in border cases, which involve constantly allocating and deallocating a
67    /// single block caused by repetitive calling `alloc()` and `release()` when the allocator has either no blocks
68    /// or have all blocks fully occupied.
69    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; // int3
92#[cfg(not(any(target_arch = "x86", target_arch = "x86_64")))]
93const DEFAULT_FILL_PATTERN: u32 = 0x0; // int3
94
95/// Number of pools to use when `JitAllocatorOptions::use_multiple_pools` is set.
96///
97/// Each pool increases granularity twice to make memory management more
98/// efficient. Ideal number of pools appears to be 3 to 4 as it distributes
99/// small and large functions properly.
100const MULTI_POOL_COUNT: usize = 3;
101
102/// Minimum granularity (and the default granularity for pool #0).
103const MIN_GRANULARITY: usize = 64;
104
105/// Maximum block size (32MB).
106const 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    /// Link to the pool that owns this block.
212    pool: *mut JitAllocatorPool,
213    /// Virtual memory mapping - either single mapping (both pointers equal) or
214    /// dual mapping, where one pointer is Read+Execute and the second Read+Write.
215    mapping: DualMapping,
216    /// Virtual memory size (block size) [bytes].
217    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        // SAFETY: `JitAllocatorBlock` is only reachable through
289        // `JitAllocator`, which is `!Send`/`!Sync` (it holds raw pointers).
290        // Every caller mutates bitvectors only while holding `&mut
291        // JitAllocator`, and never holds a shared reference to the same vector
292        // at the same time.
293        unsafe { &*self.used_bitvector.get() }
294    }
295
296    fn stop_bitvector(&self) -> &alloc::vec::Vec<u32> {
297        // SAFETY: same invariant as `used_bitvector`: exclusive access
298        // through `&mut JitAllocator`, and no aliasing shared borrow at the
299        // call site.
300        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        // SAFETY: the block is owned by a `JitAllocator` that is only
306        // mutated through `&mut JitAllocator`, and this module never creates
307        // a live `&`/`&mut` pair to the same vector: `mark_*` callers use one
308        // bitvector at a time and drop the borrow before the next.
309        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        // SAFETY: same exclusive-access invariant as `used_bitvector_mut`.
315        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        // SAFETY: `self.pool` is assigned in `new_block` before the block is
337        // published to any list/tree and is never changed afterwards. The pool
338        // is owned by the `JitAllocator` that owns this block, and freed
339        // only after every block is removed in `Drop`, so it is live here.
340        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        // SAFETY: same invariant as `mark_allocated_area`: `self.pool` is live
367        // and owned by the allocator state that owns this block, and all
368        // mutations are serialized through `&mut JitAllocator`.
369        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        // Shrunk area cannot start at zero as it would mean that we have shrunk the first
405        // block to zero bytes, which is not allowed as such block must be released instead.
406        assert!(shrunk_area_start != 0);
407        assert!(shrunk_area_end <= self.area_size());
408
409        // SAFETY: same invariant as `mark_allocated_area`: `self.pool` is live
410        // and owned by the allocator state that owns this block, and all
411        // mutations are serialized through `&mut JitAllocator`.
412        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
567/// A simple implementation of memory manager that uses [virtual_memory].
568/// functions to manage virtual memory for JIT compiled code.
569///
570/// Implementation notes:
571///
572/// - Granularity of allocated blocks is different than granularity for a typical C malloc. In addition, the allocator
573///   can use several memory pools having a different granularity to minimize the maintenance overhead. Multiple pools
574///   feature requires `use_multiple_pools` flag to be set.
575///
576/// - The allocator doesn't store any information in executable memory, instead, the implementation uses two
577///   bit-vectors to manage allocated memory of each allocator-block. The first bit-vector called 'used' is used to
578///   track used memory (where each bit represents memory size defined by granularity) and the second bit vector called
579///   'stop' is used as a sentinel to mark where the allocated area ends.
580///
581/// - Internally, the allocator also uses RB tree to keep track of all blocks across all pools. Each inserted block is
582///   added to the tree so it can be matched fast during `release()` and `shrink()`.
583///
584/// Like asmjit's `JitAllocator`, this is a low-level interface: [`Span`]s are plain handles that do not own
585/// their memory. Allocations live until they are passed to [`JitAllocator::release`], or until the allocator
586/// is reset or dropped, and it is up to the caller not to use a span past that point.
587pub 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    /// Creates a new JIT allocator.
600    pub fn new(mut params: JitAllocatorOptions) -> Box<Self> {
601        let vm_info = virtual_memory::info();
602
603        // Apple platforms refuse executable `MAP_SHARED` mappings, so dual
604        // mapping fails there. Use a single `MAP_JIT` mapping instead and toggle
605        // write access with `pthread_jit_write_protect_np`, as asmjit does.
606        #[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        // SAFETY: callers pass a pointer taken from `self.pools`, which owns the
675        // pool for the lifetime of the state, and call this while holding the
676        // allocator's exclusive borrow.
677        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                // overflow
693                if block_size < allocation_size {
694                    return 0;
695                }
696            }
697
698            block_size
699        }
700    }
701
702    /// Creates a new block owned by `pool` and maps `block_size` bytes for it.
703    ///
704    /// # Safety
705    ///
706    /// `pool` must be a live pool pointer owned by the same `JitAllocator`
707    /// as `self`, and `self` must hold the state's exclusive borrow. The
708    /// returned `Box` owns the only pointer to the block until the caller
709    /// publishes it with [`Self::insert_block`].
710    unsafe fn new_block(
711        &mut self,
712        pool: *mut JitAllocatorPool,
713        block_size: usize,
714    ) -> Result<Box<JitAllocatorBlock>, AsmError> {
715        // SAFETY: `pool` is live per the function contract; the area size is
716        // computed from the block size and the pool's power-of-two granularity
717        // (validated in `JitAllocator::new`), no arithmetic can overflow
718        // because `block_size` is validated to be at most `MAX_BLOCK_SIZE`.
719        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    /// Destroys `block`, unmapping its memory.
766    ///
767    /// # Safety
768    ///
769    /// `block` must be a pointer previously returned by [`Self::new_block`] (or
770    /// `Box::into_raw` of such a block) that has already been removed from the
771    /// RB tree and its pool's list, and must not be used afterwards.
772    unsafe fn delete_block(&mut self, block: *mut JitAllocatorBlock) {
773        // SAFETY: per the contract, `block` is an owned `Box` allocation that is
774        // no longer reachable from any tree/list, so reclaiming it with
775        // `Box::from_raw` is the unique owner. The mapping pointers stored in
776        // the block were produced by `alloc`/`alloc_dual_mapping` and are
777        // released exactly once here, matching the mapping kind recorded in
778        // `FLAG_DUAL_MAPPED`.
779        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    /// Publishes `block` into the RB tree and its pool's block list.
792    ///
793    /// # Safety
794    ///
795    /// `block` must be a live, uniquely owned pointer from [`Self::new_block`]
796    /// that has not yet been inserted, and `self` must hold the state's
797    /// exclusive borrow. Ownership of the pointer is transferred to the tree
798    /// and list (reclaimed by [`Self::remove_block`]).
799    unsafe fn insert_block(&mut self, block: *mut JitAllocatorBlock) {
800        // SAFETY: per the contract `block` is a live uniquely owned allocation;
801        // `b.pool()` was set by `new_block` and points at a live pool, so
802        // `&mut *b.pool()` is a unique borrow. `UnsafeRef::from_raw` hands the
803        // raw pointer to the tree/list, which now own it until removal.
804        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    /// Removes the block under `block` from the RB tree and its pool list and
824    /// returns its raw pointer, transferring ownership back to the caller.
825    ///
826    /// # Safety
827    ///
828    /// `block` must be a non-null cursor positioned on a block that was
829    /// published by [`Self::insert_block`], and `self` must hold the state's
830    /// exclusive borrow. The returned pointer must be reclaimed exactly once,
831    /// normally with [`Self::delete_block`].
832    unsafe fn remove_block(
833        &mut self,
834        block: &mut intrusive_collections::linked_list::CursorMut<'_, BlockListAdapter>,
835    ) -> *mut JitAllocatorBlock {
836        // SAFETY: per the contract the cursor is positioned on a live block
837        // owned by the list; the block's `pool` pointer is still valid because
838        // the pool outlives all of its blocks, and all other accesses happen
839        // under the state's exclusive borrow.
840        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    /// Marks a block as empty, optionally re-filling its memory with the
887    /// allocator fill pattern.
888    ///
889    /// # Safety
890    ///
891    /// `block` must be a non-null cursor positioned on a live block of `self`'s
892    /// tree/list, and `self` must hold the state's exclusive borrow. The block
893    /// must not be in use by any allocation.
894    unsafe fn wipe_out_block(
895        &mut self,
896        block: &mut intrusive_collections::linked_list::CursorMut<'_, BlockListAdapter>,
897    ) {
898        // SAFETY: per the contract the cursor is positioned on a live block; its
899        // `pool` pointer stays valid for the block's lifetime, and this runs
900        // under the state's exclusive borrow so the fill writes cannot race
901        // with an allocation.
902        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                        // SAFETY (inside the outer `unsafe` block): `span_ptr`
935                        // points into the block's RW mapping, `n` stays below
936                        // `span_size` (the span length in bytes), and the span
937                        // is granularity-aligned so each 4-byte write is in
938                        // bounds and `u32`-aligned.
939                        *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    /// Resets current allocator by emptying all pools and blocks.
964    ///
965    /// Frees all memory is `ResetPolicy::Hard` is specified or `immediate_release` in [JitAllocatorOptions] is specific.
966    ///
967    /// # Safety
968    ///
969    /// - The caller must ensure that no code is currently executing from the memory managed by this allocator.
970    /// - The caller must ensure that no references to the memory managed by this allocator are used after calling this function.
971    /// - The caller must ensure that no other thread is currently accessing the memory managed by this allocator.
972    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            // SAFETY: `self.pools` is an owned slice of heap pools that are freed
977            // only in `Drop for JitAllocator` (after a final hard reset);
978            // `pool_id` is in bounds. Taking `&mut` is exclusive because this
979            // method has `&mut self`.
980            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            // SAFETY: every block in `pool.blocks` was published by
993            // `insert_block` and is uniquely owned by this list. `remove_block`
994            // unlinks and returns each one, after which `delete_block` reclaims
995            // it; `block_to_keep` points at a block left in the list, and the
996            // caller's contract guarantees no other code or thread is using it.
997            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                    // SAFETY: `block_to_keep` is still linked in `pool.blocks`
1015                    // (it was skipped above), so a cursor can be constructed
1016                    // from its pointer.
1017                    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    /// Allocates `size` bytes in the executable memory region.
1032    ///
1033    /// The returned [`Span`] holds two pointers. One points to Read-Execute mapping and another to Read-Write
1034    /// mapping. All code writes *must* go to the Read-Write mapping.
1035    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        // SAFETY: `self.pools` owns live pools; `pool_id` is in bounds; every
1049        // block pointer reachable from the pools was produced by previous
1050        // `insert_block` calls under `&mut self`, so it is live.
1051        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            // SAFETY: `offset` is the byte offset of the freshly marked area
1170            // inside the block, so it is within `block_size`; both `rx` and `rw`
1171            // point at the start of a live mapping of at least that size.
1172            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    /// Releases the memory allocated by `alloc`.
1183    ///
1184    /// # Safety
1185    ///
1186    /// - `rx_ptr` must have been returned from `alloc` on this allocator.
1187    /// - `rx_ptr` must not have been passed to `release`/`shrink` before.
1188    /// - `rx_ptr` must point to the read-execute mapping returned by `alloc`,
1189    ///   and no pointer into the released area may be used afterwards.
1190    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        // SAFETY: `block` was located in the RB tree, so it is live and owned by
1205        // this state; `block.pool` was set by `new_block` at the pool that owns
1206        // the block, which outlives it. The tree lookup places `rx_ptr` inside
1207        // this block, so the offset arithmetic stays inside the mapping and
1208        // the bitvector probes are in bounds. The fill writes `area_size`
1209        // bytes of the RW mapping, and the raw pointers are advanced by that
1210        // allocation's exact offset.
1211        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    /// Shrinks the memory allocated by `alloc` and updates `span.size()` to match.
1267    ///
1268    /// A `new_size` of zero releases the allocation.
1269    ///
1270    /// # Safety
1271    ///
1272    /// `span` must describe a live allocation returned by `alloc` on this
1273    /// allocator; no pointer into the released tail may be used afterwards.
1274    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            // SAFETY: forwarding the caller's contract unchanged.
1282            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        // SAFETY: `block` was located in the RB tree, so it is live; `block.pool`
1299        // points at the live owning pool. The bitvector probes are bounded by
1300        // the allocation start/end checks, and the fill range lies inside the
1301        // retained allocation's mapping, so the raw pointer arithmetic is in
1302        // bounds and the flush covers exactly the shrunk tail.
1303        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    /// Takes a pointer to the start of an allocation and returns a [`Span`]
1354    /// describing its RX and RW mappings and size.
1355    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        // SAFETY: `block` was located in the RB tree, so it is live; `block.pool`
1368        // points at its live owning pool. `rx_ptr` lies inside the block because
1369        // `BlockKey` ordered it there, so the offset is in bounds and the
1370        // bitvector probes/pointers stay inside the mapping.
1371        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    /// Writes through a span and synchronizes the instruction cache.
1404    ///
1405    /// Makes JIT memory writable for the duration of `write_func` (MAP_JIT
1406    /// platforms), then flushes the instruction cache for the whole span.
1407    ///
1408    /// # Safety
1409    ///
1410    /// `span` must describe a live allocation of this allocator,
1411    /// `write_func` must only write inside it and leave valid executable code
1412    /// there, and no thread may execute it while the closure is modifying it.
1413    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        // SAFETY: the caller guarantees `span` is a live mapped allocation.
1425        unsafe { flush_instruction_cache(span.rx, span.size)? };
1426        span.icache_clean = true;
1427        Ok(())
1428    }
1429
1430    /// Copies `slice` into `span` at `offset` and synchronizes the written
1431    /// instruction-cache range.
1432    ///
1433    /// # Safety
1434    ///
1435    /// `span` must describe a live allocation of this allocator, and no thread
1436    /// may execute the written range while it is being modified. The range is
1437    /// bounds-checked against `span.size()`.
1438    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        // SAFETY: the caller guarantees `span` is live and `offset..end` was
1456        // bounds-checked against its size, so the copy and the flush stay
1457        // inside its mappings.
1458        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        // SAFETY: this is the unique owner of `self.pools`; reset removes and
1474        // deletes every block from every pool (guaranteed to have `&mut self`,
1475        // so no other user of the mappings can exist), after which each pool
1476        // `Box` is reclaimed exactly once. Any `Span` still held by the caller
1477        // dangles after this, as with asmjit.
1478        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/// Fills `size_in_bytes` of `mem` (rounded down to 4-byte units) with `pattern`.
1488///
1489/// # Safety
1490///
1491/// `mem` must be valid for writes of `size_in_bytes / 4 * 4` bytes and must be
1492/// aligned at least to `u32`.
1493#[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        // SAFETY: `i < n`, so `p.add(i)` is within the first `n * 4` bytes, which
1501        // the caller guarantees are writable and aligned for `u32`.
1502        unsafe {
1503            p.add(i).write(pattern);
1504        }
1505    }
1506}
1507
1508/// A region of executable memory returned by [`JitAllocator::alloc`].
1509///
1510/// This is a plain handle: copying or
1511/// dropping it does nothing to the allocation. Release it explicitly with
1512/// [`JitAllocator::release`], or let the allocator free it on reset or drop.
1513#[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    /// Returns a pointer having Read & Execute permissions (references executable memory).
1524    ///
1525    /// This pointer is never NULL if the allocation succeeded, it points to an executable memory.
1526    pub const fn rx(&self) -> *const u8 {
1527        self.rx
1528    }
1529    /// Returns a pointer having Read & Write permissions (references writable memory).
1530    ///
1531    /// Depending on the type of the allocation strategy this could either be:
1532    ///
1533    ///   - the same address as returned by `rx()` if the allocator uses RWX mapping (pages have all of Read, Write,
1534    ///     and Execute permissions) or MAP_JIT, which requires changing JIT memory protection manually.
1535    ///   - a valid pointer, but not the same as `rx` - this would be valid if dual mapping is used.
1536    ///   - NULL pointer, in case that the allocation strategy doesn't use RWX, MAP_JIT, or dual mapping. In this
1537    ///     case only [JitAllocator] can copy new code into the executable memory referenced by [Span].
1538    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    /// Returns the allocator block this span lives in, as an opaque pointer.
1547    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}