squads_multisig_program/
allocator.rs

1/*
2Optimizing Bump Heap Allocation
3
4Objective: Increase available heap memory while maintaining flexibility in program invocation.
5
61. Initial State: Default 32 KiB Heap
7
8Memory Layout:
90x300000000           0x300008000
10      |                    |
11      v                    v
12      [--------------------]
13      ^                    ^
14      |                    |
15 VM Lower              VM Upper
16 Boundary              Boundary
17
18Default Allocator (Allocates Backwards / Top Down) (Default 32 KiB):
190x300000000           0x300008000
20      |                    |
21      [--------------------]
22                           ^
23                           |
24                  Allocation starts here (SAFE)
25
262. Naive Approach: Increase HEAP_LENGTH to 8 * 32 KiB + Default Allocator
27
28Memory Layout with Increased HEAP_LENGTH:
290x300000000           0x300008000                          0x300040000
30      |                    |                                     |
31      v                    v                                     v
32      [--------------------|------------------------------------|]
33      ^                    ^                                     ^
34      |                    |                                     |
35 VM Lower              VM Upper                         Allocation starts here
36 Boundary              Boundary                         (ACCESS VIOLATION!)
37
38Issue: Access violation occurs without requestHeapFrame, requiring it for every transaction.
39
403. Optimized Solution: Forward Allocation with Flexible Heap Usage
41
42Memory Layout (Same as Naive Approach):
430x300000000           0x300008000                          0x300040000
44      |                    |                                     |
45      v                    v                                     v
46      [--------------------|------------------------------------|]
47      ^                    ^                                     ^
48      |                    |                                     |
49 VM Lower              VM Upper                             Allocator & VM
50 Boundary              Boundary                             Heap Limit
51
52Forward Allocator Behavior:
53
54a) Without requestHeapFrame:
550x300000000           0x300008000
56      |                    |
57      [--------------------]
58      ^                    ^
59      |                    |
60 VM Lower               VM Upper
61 Boundary               Boundary
62 Allocation
63 starts here (SAFE)
64
65b) With requestHeapFrame:
660x300000000           0x300008000                          0x300040000
67      |                    |                                     |
68      [--------------------|------------------------------------|]
69      ^                    ^                                     ^
70      |                    |                                     |
71 VM Lower                  |                                VM Upper
72 Boundary                                                   Boundary
73 Allocation        Allocation continues              Maximum allocation
74 starts here       with requestHeapFrame             with requestHeapFrame
75(SAFE)
76
77Key Advantages:
781. Compatibility: Functions without requestHeapFrame for allocations ≤32 KiB.
792. Extensibility: Supports larger allocations when requestHeapFrame is invoked.
803. Efficiency: Eliminates mandatory requestHeapFrame calls for all transactions.
81
82Conclusion:
83The forward allocation strategy offers a robust solution, providing both backward
84compatibility for smaller heap requirements and the flexibility to utilize extended
85heap space when necessary.
86
87The following allocator is a copy of the bump allocator found in
88solana_program::entrypoint and
89https://github.com/solana-labs/solana-program-library/blob/master/examples/rust/custom-heap/src/entrypoint.rs
90
91but with changes to its HEAP_LENGTH and its
92starting allocation address.
93*/
94
95use solana_program::entrypoint::HEAP_START_ADDRESS;
96use std::{alloc::Layout, mem::size_of, ptr::null_mut};
97
98/// Length of the memory region used for program heap.
99pub const HEAP_LENGTH: usize = 8 * 32 * 1024;
100
101struct BumpAllocator;
102
103unsafe impl std::alloc::GlobalAlloc for BumpAllocator {
104    #[inline]
105    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
106        const POS_PTR: *mut usize = HEAP_START_ADDRESS as *mut usize;
107        const TOP_ADDRESS: usize = HEAP_START_ADDRESS as usize + HEAP_LENGTH;
108        const BOTTOM_ADDRESS: usize = HEAP_START_ADDRESS as usize + size_of::<*mut u8>();
109        let mut pos = *POS_PTR;
110        if pos == 0 {
111            // First time, set starting position to bottom address
112            pos = BOTTOM_ADDRESS;
113        }
114        // Align the position upwards
115        pos = (pos + layout.align() - 1) & !(layout.align() - 1);
116        let next_pos = pos.saturating_add(layout.size());
117        if next_pos > TOP_ADDRESS {
118            return null_mut();
119        }
120        *POS_PTR = next_pos;
121        pos as *mut u8
122    }
123
124    #[inline]
125    unsafe fn dealloc(&self, _: *mut u8, _: Layout) {
126        // I'm a bump allocator, I don't free
127    }
128}
129
130// Only use the allocator if we're not in a no-entrypoint context
131#[cfg(not(feature = "no-entrypoint"))]
132#[global_allocator]
133static A: BumpAllocator = BumpAllocator;
squads_multisig_program/allocator.rs

squads_multisig_program/
allocator.rs
