Line data Source code
1 : //
2 : // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // Official repository: https://github.com/boostorg/capy
8 : //
9 :
10 : #include "work_allocator.hpp"
11 : #include <cstdlib>
12 : #include <functional>
13 : #include <new>
14 :
15 : namespace boost {
16 : namespace capy {
17 :
18 : //------------------------------------------------------------------------------
19 : //
20 : // work_allocator::arena
21 : //
22 : //------------------------------------------------------------------------------
23 :
24 8 : work_allocator::arena::
25 : ~arena()
26 : {
27 8 : std::free(base_);
28 8 : }
29 :
30 8 : work_allocator::arena::
31 8 : arena(std::size_t capacity)
32 8 : : prev_(nullptr)
33 8 : , next_(nullptr)
34 8 : , base_(std::malloc(capacity))
35 8 : , capacity_(capacity)
36 8 : , offset_(capacity)
37 8 : , count_(0)
38 : {
39 8 : if(!base_)
40 0 : throw std::bad_alloc();
41 8 : }
42 :
43 : bool
44 38 : work_allocator::arena::
45 : owns(void* p) const noexcept
46 : {
47 : std::less<char const*> cmp;
48 38 : auto* cp = static_cast<char const*>(p);
49 38 : auto* base = static_cast<char const*>(base_);
50 : // cp >= base && cp < base + capacity_
51 38 : return !cmp(cp, base) && cmp(cp, base + capacity_);
52 : }
53 :
54 : void*
55 38 : work_allocator::arena::
56 : allocate(std::size_t size, std::size_t align) noexcept
57 : {
58 38 : if(offset_ < size)
59 0 : return nullptr;
60 :
61 38 : std::size_t aligned = (offset_ - size) & ~(align - 1);
62 :
63 38 : if(aligned > offset_)
64 0 : return nullptr;
65 :
66 38 : offset_ = aligned;
67 38 : ++count_;
68 38 : return static_cast<char*>(base_) + offset_;
69 : }
70 :
71 : void
72 38 : work_allocator::arena::
73 : deallocate(void* /*p*/, std::size_t /*size*/, std::size_t /*align*/) noexcept
74 : {
75 38 : --count_;
76 38 : }
77 :
78 : void
79 0 : work_allocator::arena::
80 : reset() noexcept
81 : {
82 0 : offset_ = capacity_;
83 0 : count_ = 0;
84 0 : }
85 :
86 : //------------------------------------------------------------------------------
87 : //
88 : // work_allocator
89 : //
90 : //------------------------------------------------------------------------------
91 :
92 12 : work_allocator::
93 : ~work_allocator()
94 : {
95 12 : arena* a = head_;
96 20 : while(a)
97 : {
98 8 : arena* next = a->next_;
99 8 : delete a;
100 8 : a = next;
101 : }
102 12 : }
103 :
104 12 : work_allocator::
105 : work_allocator(
106 : std::size_t min_size,
107 : std::size_t max_size,
108 12 : std::size_t keep_empty)
109 12 : : head_(nullptr)
110 12 : , tail_(nullptr)
111 12 : , arena_count_(0)
112 12 : , next_size_(min_size)
113 12 : , min_size_(min_size)
114 12 : , max_size_(max_size)
115 12 : , keep_empty_(keep_empty)
116 : {
117 12 : }
118 :
119 : void*
120 38 : work_allocator::
121 : allocate(std::size_t size, std::size_t align)
122 : {
123 : // Always allocate from tail (active arena)
124 38 : if(tail_)
125 : {
126 30 : if(void* p = tail_->allocate(size, align))
127 30 : return p;
128 : }
129 :
130 : // Active arena full or none exists.
131 : // Try recycling a parked arena to preserve allocation order.
132 8 : arena* fresh = find_parked();
133 8 : if(fresh)
134 : {
135 0 : unlink(fresh);
136 0 : fresh->reset();
137 0 : link_at_tail(fresh);
138 : }
139 : else
140 : {
141 8 : std::size_t arena_size = next_size_;
142 8 : if(arena_size < size + align)
143 0 : arena_size = size + align;
144 :
145 8 : fresh = new arena(arena_size);
146 8 : link_at_tail(fresh);
147 :
148 8 : if(next_size_ < max_size_)
149 : {
150 8 : next_size_ *= 2;
151 8 : if(next_size_ > max_size_)
152 0 : next_size_ = max_size_;
153 : }
154 : }
155 :
156 8 : void* p = tail_->allocate(size, align);
157 8 : if(!p)
158 0 : throw std::bad_alloc();
159 8 : return p;
160 : }
161 :
162 : void
163 38 : work_allocator::
164 : deallocate(void* p, std::size_t size, std::size_t align) noexcept
165 : {
166 38 : arena* a = find_arena(p);
167 38 : if(!a)
168 0 : return;
169 :
170 38 : a->deallocate(p, size, align);
171 :
172 : // Prune when a non-active arena empties
173 38 : if(a->empty() && a != tail_)
174 0 : prune();
175 : }
176 :
177 : void
178 8 : work_allocator::
179 : link_at_tail(arena* a) noexcept
180 : {
181 8 : a->prev_ = tail_;
182 8 : a->next_ = nullptr;
183 8 : if(tail_)
184 0 : tail_->next_ = a;
185 : else
186 8 : head_ = a;
187 8 : tail_ = a;
188 8 : ++arena_count_;
189 8 : }
190 :
191 : void
192 0 : work_allocator::
193 : unlink(arena* a) noexcept
194 : {
195 0 : if(a->prev_)
196 0 : a->prev_->next_ = a->next_;
197 : else
198 0 : head_ = a->next_;
199 :
200 0 : if(a->next_)
201 0 : a->next_->prev_ = a->prev_;
202 : else
203 0 : tail_ = a->prev_;
204 :
205 0 : a->prev_ = nullptr;
206 0 : a->next_ = nullptr;
207 0 : --arena_count_;
208 0 : }
209 :
210 : work_allocator::arena*
211 38 : work_allocator::
212 : find_arena(void* p) noexcept
213 : {
214 38 : for(arena* a = head_; a; a = a->next_)
215 : {
216 38 : if(a->owns(p))
217 38 : return a;
218 : }
219 0 : return nullptr;
220 : }
221 :
222 : work_allocator::arena*
223 8 : work_allocator::
224 : find_parked() noexcept
225 : {
226 : // Search from oldest, skip the active arena (tail)
227 8 : for(arena* a = head_; a && a != tail_; a = a->next_)
228 : {
229 0 : if(a->empty())
230 0 : return a;
231 : }
232 8 : return nullptr;
233 : }
234 :
235 : void
236 0 : work_allocator::
237 : prune() noexcept
238 : {
239 : // Count parked (empty non-active) arenas
240 0 : std::size_t parked_count = 0;
241 0 : for(arena* a = head_; a && a != tail_; a = a->next_)
242 : {
243 0 : if(a->empty())
244 0 : ++parked_count;
245 : }
246 :
247 : // Delete excess parked arenas from the front
248 0 : arena* a = head_;
249 0 : while(a && a != tail_ && parked_count > keep_empty_)
250 : {
251 0 : arena* next = a->next_;
252 0 : if(a->empty())
253 : {
254 0 : unlink(a);
255 0 : delete a;
256 0 : --parked_count;
257 : }
258 0 : a = next;
259 : }
260 :
261 : // Shrink next_size if we're back to minimal state
262 0 : if(arena_count_ <= 1)
263 0 : next_size_ = min_size_;
264 0 : }
265 :
266 : } // capy
267 : } // boost
268 :
|
