1-- A monotonic allocator over a caller-supplied byte extent, a provider of
2-- its own beside core/pool, core/region and core/fault. Individual frees
3-- deliberately do nothing; ending the extent ends all of its allocations
4-- together. The caller holds the counters; the handle holds the backing
5-- and a pointer to them.
6
7import core/mem
8
9arena_state: type = struct
10 size: usize
11 used: usize
12end arena_state
13
14--- Caller-owned state of an arena: its extent and the bytes it has handed
15--- out. Declare it `zeroed` beside the backing and give it to `over`,
16--- which fills it; it must outlive the arena handle.
17public space: type = arena_state
18
19arena_value: type = struct
20 state: ptr mut arena_state
21 base: ptr mut u8
22end arena_value
23
24--- Monotonic allocator over caller-owned bytes, as a handle: copies share one
25--- arena. Individual frees do not reclaim space; only the most recent
26--- allocation can grow in place, or give back its tail when it is resized
27--- smaller, and a resize that cannot grow in place moves the block to a new
28--- allocation, leaving the old bytes spent. Zero-byte requests may consume
29--- alignment padding. `reset` gives every allocation back at once,
30--- the arena's one free that reclaims anything.
31public arena: type = arena_value
32
33--- Fill `state` for an arena over retainable backing and return its handle,
34--- without allocating. The range must stay valid for the arena and all
35--- allocations made through it.
36---
37--- The independent allocator result may be retained after this call. Only
38--- backing which the caller may itself retain can enter the checked arena.
39public over: (inout state: space, escaping base: ptr mut u8, size: usize)
40 -> (handle: arena from state, base) =
41 state = (size: size, used: 0)
42 handle = (state: addr state, base: base)
43end over
44
45--- Fill `state` for an arena over local backing with an explicit lifetime
46--- opt-out and return its handle. The caller must end every allocated view
47--- before that backing ends.
48---
49--- Explicit lifetime opt-out for a local extent. The handle still keeps its
50--- tracked origins, but allocations do not; users must end every allocation
51--- before the backing ends, including allocations retained by helpers.
52public over_unchecked: (inout state: space, base: ptr mut u8, size: usize)
53 -> (handle: arena from state, base) =
54 state = (size: size, used: 0)
55 handle = (state: addr state, base: base)
56end over_unchecked
57
58--- Return consumed arena bytes, including alignment padding.
59public used: (memory: arena) -> (count: usize) =
60 count = memory.state.val.used
61end used
62
63--- Give every allocation of the arena back at once: the next allocation
64--- starts at its base again. Every block it gave is then free, and a
65--- program that still uses one has the same obligation as after `free`.
66public reset: (memory: arena) -> none =
67 memory.state.val.used = 0
68end reset
69
70arena_alloc: (self: arena, size: usize, alignment: usize)
71 -> (block: ptr mut u8) ! mem.out_of_memory =
72 state: ptr mut arena_state = self.state
73 offset: usize = try mem.aligned_offset(self.base, state.val.used,
74 state.val.size, size, alignment)
75 -- [0810]: the block borrows nothing, so that a container may keep it
76 -- in its own storage; its lifetime is the backing's, which the caller
77 -- keeps.
78 address: usize = usize(self.base) + offset
79 block = ptr(address)
80 state.val.used = offset + size
81end arena_alloc
82
83arena_free: (self: arena, block: ptr mut u8, size: usize) -> none =
84 _ = self.state
85 _ = block
86 _ = size
87end arena_free
88
89arena_grow: (self: arena, block: ptr mut u8,
90 old_size: usize, new_size: usize, alignment: usize)
91 -> (grown: bool) =
92 grown = false
93 state: ptr mut arena_state = self.state
94 return when new_size <= old_size or state.val.used > state.val.size
95 base_address: usize = usize(self.base)
96 block_address: usize = usize(block)
97 return when block_address < base_address
98 offset: usize = block_address - base_address
99 return when offset > state.val.used or old_size <> state.val.used - offset
100 return when alignment > 1 and block_address % alignment <> 0
101 return when new_size > state.val.size - offset
102 maximum: usize = 0 -% 1
103 return when new_size > maximum - block_address
104 state.val.used = offset + new_size
105 grown = true
106end arena_grow
107
108-- A smaller extent keeps the block where it is, and the latest allocation
109-- gives its tail back; a larger one grows in place when `arena_grow` can,
110-- and otherwise moves the block to the top.
111arena_resize: (self: arena, block: ptr mut u8,
112 old_size: usize, new_size: usize, alignment: usize)
113 -> (moved: ptr mut u8) ! mem.out_of_memory =
114 -- [0810]: the block borrows nothing, as an allocation does.
115 moved = ptr(usize(block))
116 if new_size <= old_size then
117 state: ptr mut arena_state = self.state
118 base_address: usize = usize(self.base)
119 block_address: usize = usize(block)
120 return when block_address < base_address
121 offset: usize = block_address - base_address
122 if offset <= state.val.used and old_size == state.val.used - offset
123 then
124 state.val.used = offset + new_size
125 end if
126 return
127 end if
128 return when arena_grow(self, block, old_size, new_size, alignment)
129 moved = try mem.relocate(self, block, old_size, new_size, alignment)
130end arena_resize
131
132arena is mem.allocator (alloc: arena_alloc, grow: arena_grow,
133 resize: arena_resize, free: arena_free)