1-- A caller-backed reclaiming allocator. Unlike core/mem's arena, every
2-- successful allocation owns one uniform slot. Free indices form a min heap
3-- in caller-supplied metadata for lowest-index reuse. No operation imports
4-- or falls back to a backing allocator.
5
6import core/mem
7
8--- Caller-owned bookkeeping record for one pool slot. Supply an initialized
9--- slice to `over`; the provider maintains its fields after construction.
10public slot: type = struct
11 size: usize
12 free_index: usize
13end slot
14
15fixed_pool: type = struct
16 base: ptr mut u8
17 extent: usize
18 slot_size: usize
19 slot_count: usize
20 bookkeeping: []mut slot
21 slot_alignment: usize
22 first_offset: usize
23 stride: usize
24 free_count: usize
25 allocations: usize
26 frees: usize
27 live_count: usize
28 rejected_frees: usize
29end fixed_pool
30
31--- Reclaiming allocator over uniform slots in caller storage. Reuses the
32--- lowest free index, never grows in place, and uses no fallback allocator.
33--- Even a zero-byte allocation occupies a slot.
34public provider: type = fixed_pool
35
36-- This is D193's absolute-address algorithm kept local because core/mem's
37-- helper is private and the pool must remain an independent module. Every
38-- potentially overflowing operation is preceded by its own bound.
39allocation_offset: (base: ptr mut u8, used: usize, extent: usize,
40 size: usize, alignment: usize)
41 -> (offset: usize) ! mem.out_of_memory =
42 maximum: usize = 0 -% 1
43 fail mem.out_of_memory when used > extent
44
45 base_address: usize = usize(base)
46 fail mem.out_of_memory when used > maximum - base_address
47 current_address: usize = base_address + used
48
49 mut padding: usize = 0
50 if alignment > 1 then
51 remainder: usize = current_address % alignment
52 if not (remainder == 0) then
53 padding = alignment - remainder
54 end if
55 end if
56
57 fail mem.out_of_memory when padding > extent - used
58 fail mem.out_of_memory when padding > maximum - current_address
59 offset = used + padding
60 aligned_address: usize = current_address + padding
61 fail mem.out_of_memory when size > extent - offset
62 fail mem.out_of_memory when size > maximum - aligned_address
63end allocation_offset
64
65slot_stride: (size: usize, alignment: usize)
66 -> (stride: usize) ! mem.out_of_memory =
67 fail mem.out_of_memory when size == 0
68 maximum: usize = 0 -% 1
69 mut padding: usize = 0
70 if alignment > 1 then
71 remainder: usize = size % alignment
72 if not (remainder == 0) then
73 padding = alignment - remainder
74 end if
75 end if
76 fail mem.out_of_memory when padding > maximum - size
77 stride = size + padding
78end slot_stride
79
80--- Construct a pool over caller backing and bookkeeping. Validates positive
81--- slot size, alignment, extent and record capacity before publishing the
82--- provider. Keep both backing ranges alive until all allocations end.
83---
84--- slot_size is positive. The initialized bookkeeping slice is supplied by
85--- the caller, its length is the finite bookkeeping capacity, and slot_count
86--- may be zero but may not exceed it. The maximum usize marks a free slot,
87--- so a positive pool cannot use that slot size. A positive pool aligns its
88--- first slot from the absolute backing address, includes that padding in extent
89--- accounting, and proves every later slot and its complete payload fit both
90--- the backing extent and target address space before publishing the provider.
91public over: (base: ptr mut u8, extent: usize, slot_size: usize,
92 slot_count: usize, slot_alignment: usize,
93 bookkeeping: []mut slot)
94 -> (state: provider from base, bookkeeping)
95 ! mem.out_of_memory =
96 fail mem.out_of_memory when slot_count > lenof bookkeeping
97 empty: usize = 0 -% 1
98 fail mem.out_of_memory when slot_count > 0 and slot_size == empty
99
100 mut normalized_alignment: usize = slot_alignment
101 if normalized_alignment <= 1 then
102 normalized_alignment = 1
103 end if
104 step: usize = try slot_stride(slot_size, normalized_alignment)
105
106 mut offset: usize = 0
107 if slot_count > 0 then
108 offset = try allocation_offset(base, 0, extent, slot_size,
109 normalized_alignment)
110 remaining_slots: usize = slot_count - 1
111 after_first: usize = extent - offset - slot_size
112 fail mem.out_of_memory when remaining_slots > after_first / step
113
114 maximum: usize = 0 -% 1
115 first_address: usize = usize(base) + offset
116 address_room: usize = maximum - first_address - slot_size
117 fail mem.out_of_memory when remaining_slots > address_room / step
118 end if
119
120 mut index: usize = 0
121 while index < slot_count do
122 bookkeeping[index] = (size: empty,
123 free_index: index)
124 inc index
125 end while
126
127 state = (base: base, extent: extent, slot_size: slot_size,
128 slot_count: slot_count,
129 bookkeeping: bookkeeping,
130 slot_alignment: normalized_alignment,
131 first_offset: offset, stride: step, free_count: slot_count,
132 allocations: 0, frees: 0, live_count: 0,
133 rejected_frees: 0)
134end over
135
136-- Keep indexed heap access in shared routines. Each access still checks its
137-- slice bound, while freestanding callers do not duplicate the aggregate
138-- address calculation at every step of both heap operations.
139free_index_at: (state: ptr fixed_pool, index: usize) -> (value: usize) =
140 value = state.val.bookkeeping[index].free_index
141end free_index_at
142
143store_free_index: (state: ptr mut fixed_pool, index: usize,
144 value: usize) -> none =
145 state.val.bookkeeping[index].free_index = value
146end store_free_index
147
148take_free_index: (inout state: fixed_pool) -> (index: usize) =
149 index = free_index_at(addr state, 0)
150 dec state.free_count
151 if state.free_count > 0 then
152 last: usize = free_index_at(addr state, state.free_count)
153 mut position: usize = 0
154 while position < state.free_count / 2 do
155 child: usize = position * 2 + 1
156 mut smallest: usize = child
157 if child + 1 < state.free_count
158 and free_index_at(addr state, child + 1)
159 < free_index_at(addr state, child)
160 then
161 smallest = child + 1
162 end if
163 if last <= free_index_at(addr state, smallest) then
164 break
165 end if
166 store_free_index(addr state, position,
167 free_index_at(addr state, smallest))
168 position = smallest
169 end while
170 store_free_index(addr state, position, last)
171 end if
172end take_free_index
173
174return_free_index: (inout state: fixed_pool, index: usize) -> none =
175 mut position: usize = state.free_count
176 while position > 0 do
177 parent: usize = (position - 1) / 2
178 if free_index_at(addr state, parent) <= index then
179 break
180 end if
181 store_free_index(addr state, position,
182 free_index_at(addr state, parent))
183 position = parent
184 end while
185 store_free_index(addr state, position, index)
186 inc state.free_count
187end return_free_index
188
189pool_alloc: (inout state: fixed_pool,
190 size: usize, alignment: usize)
191 -> (block: ptr mut u8) ! mem.out_of_memory =
192 fail mem.out_of_memory when size > state.slot_size
193 if alignment > 1 then
194 -- A power-of-two request divides the slot alignment iff its low
195 -- bits are clear; other requests retain numeric divisibility.
196 mask: usize = alignment - 1
197 if (alignment & mask) == 0 then
198 fail mem.out_of_memory when (state.slot_alignment & mask) <> 0
199 else
200 fail mem.out_of_memory when state.slot_alignment % alignment <> 0
201 end if
202 end if
203
204 fail mem.out_of_memory when state.free_count == 0
205 index: usize = take_free_index(state)
206 distance: usize = index * state.stride
207 address: usize = usize(state.base) + state.first_offset + distance
208 block = ptr(address)
209 selected: ptr mut slot = addr state.bookkeeping[index]
210 selected.val.size = size
211 inc state.allocations
212 inc state.live_count
213end pool_alloc
214
215pool_free: (inout state: fixed_pool,
216 block: ptr mut u8, size: usize) -> none =
217 if state.slot_count == 0 then
218 inc state.rejected_frees
219 return
220 end if
221 first_address: usize = usize(state.base) + state.first_offset
222 address: usize = usize(block)
223 if address < first_address then
224 inc state.rejected_frees
225 return
226 end if
227 distance: usize = address - first_address
228 if distance % state.stride <> 0 then
229 inc state.rejected_frees
230 return
231 end if
232 index: usize = distance / state.stride
233 if index >= state.slot_count then
234 inc state.rejected_frees
235 return
236 end if
237 selected: ptr mut slot = addr state.bookkeeping[index]
238 if selected.val.size == 0 -% 1 or selected.val.size <> size then
239 inc state.rejected_frees
240 return
241 end if
242
243 selected.val.size = 0 -% 1
244 return_free_index(state, index)
245 inc state.frees
246 dec state.live_count
247end pool_free
248
249pool_grow: (inout state: fixed_pool, block: ptr mut u8,
250 old_size: usize, new_size: usize, alignment: usize)
251 -> (grown: bool) =
252 _ = state.live_count
253 _ = block
254 _ = old_size
255 _ = new_size
256 _ = alignment
257 grown = false
258end pool_grow
259
260fixed_pool is mem.allocator (alloc: pool_alloc, grow: pool_grow,
261 free: pool_free)
262
263--- Return the configured number of allocatable slots.
264public capacity: (state: provider) -> (count: usize) =
265 count = state.slot_count
266end capacity
267
268--- Return the length of the supplied metadata slice, which may exceed the
269--- configured slot count.
270public bookkeeping_capacity: (state: provider) -> (count: usize) =
271 bookkeeping: []mut slot = state.bookkeeping
272 count = lenof bookkeeping
273end bookkeeping_capacity
274
275--- Return the number of currently allocated slots.
276public live: (state: provider) -> (count: usize) =
277 count = state.live_count
278end live
279
280--- Return the number of successful allocations, including zero-byte
281--- allocations.
282public allocation_count: (state: provider) -> (count: usize) =
283 count = state.allocations
284end allocation_count
285
286--- Return the number of successful slot reclamations.
287public free_count: (state: provider) -> (count: usize) =
288 count = state.frees
289end free_count
290
291--- Return frees rejected for an invalid address, extent or already-free slot.
292--- A rejected free does not reclaim a slot.
293public rejected_free_count: (state: provider) -> (count: usize) =
294 count = state.rejected_frees
295end rejected_free_count