1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include <atomic>
10#include <cstddef>
11#include <memory>
12#include <memory_resource>
13
14_LIBCPP_BEGIN_NAMESPACE_STD
15_LIBCPP_BEGIN_EXPLICIT_ABI_ANNOTATIONS
16
17namespace pmr {
18
19// memory_resource
20
21memory_resource::~memory_resource() = default;
22
23// new_delete_resource()
24
25#if !_LIBCPP_HAS_ALIGNED_ALLOCATION
26static bool is_aligned_to(void* ptr, size_t align) {
27 void* p2 = ptr;
28 size_t space = 1;
29 void* result = std::align(align, 1, p2, space);
30 return (result == ptr);
31}
32#endif
33
34class _LIBCPP_HIDDEN __new_delete_memory_resource_imp : public memory_resource {
35 void* do_allocate(size_t bytes, size_t align) override {
36#if _LIBCPP_HAS_ALIGNED_ALLOCATION
37 return ::operator new(sz: bytes, std::align_val_t(align));
38#else
39 if (bytes < align)
40 bytes = align;
41 std::byte* result = ::operator new(bytes);
42 if (!is_aligned_to(result, align)) {
43 std::__libcpp_deallocate<std::byte>(result, __element_count(bytes), align);
44 std::__throw_bad_alloc();
45 }
46 return result;
47#endif
48 }
49
50 void do_deallocate(void* p, size_t bytes, size_t align) override {
51#if _LIBCPP_HAS_ALIGNED_ALLOCATION
52 ::operator delete(p: p, sz: bytes, align_val_t(align));
53#else
54 ::operator delete(p, bytes);
55#endif
56 }
57
58 bool do_is_equal(const memory_resource& other) const noexcept override { return &other == this; }
59};
60
61// null_memory_resource()
62
63class _LIBCPP_HIDDEN __null_memory_resource_imp : public memory_resource {
64 void* do_allocate(size_t, size_t) override { std::__throw_bad_alloc(); }
65 void do_deallocate(void*, size_t, size_t) override {}
66 bool do_is_equal(const memory_resource& other) const noexcept override { return &other == this; }
67};
68
69namespace {
70
71union ResourceInitHelper {
72 struct {
73 __new_delete_memory_resource_imp new_delete_res;
74 __null_memory_resource_imp null_res;
75 } resources;
76 char dummy;
77 constexpr ResourceInitHelper() : resources() {}
78 ~ResourceInitHelper() {}
79};
80
81// Pretend we're inside a system header so the compiler doesn't flag the use of the init_priority
82// attribute with a value that's reserved for the implementation (we're the implementation).
83#include "memory_resource_init_helper.h"
84
85} // namespace
86
87memory_resource* new_delete_resource() noexcept { return &res_init.resources.new_delete_res; }
88
89memory_resource* null_memory_resource() noexcept { return &res_init.resources.null_res; }
90
91// default_memory_resource()
92
93static memory_resource* __default_memory_resource(bool set = false, memory_resource* new_res = nullptr) noexcept {
94 static constinit atomic<memory_resource*> __res{&res_init.resources.new_delete_res};
95 if (set) {
96 new_res = new_res ? new_res : new_delete_resource();
97 // TODO: Can a weaker ordering be used?
98 return std::atomic_exchange_explicit(o: &__res, d: new_res, m: memory_order_acq_rel);
99 } else {
100 return std::atomic_load_explicit(o: &__res, m: memory_order_acquire);
101 }
102}
103
104memory_resource* get_default_resource() noexcept { return __default_memory_resource(); }
105
106memory_resource* set_default_resource(memory_resource* __new_res) noexcept {
107 return __default_memory_resource(set: true, new_res: __new_res);
108}
109
110// 23.12.5, mem.res.pool
111
112static size_t roundup(size_t count, size_t alignment) {
113 size_t mask = alignment - 1;
114 return (count + mask) & ~mask;
115}
116
117struct unsynchronized_pool_resource::__adhoc_pool::__chunk_footer {
118 __chunk_footer* __next_;
119 char* __start_;
120 size_t __align_;
121 size_t __allocation_size() { return (reinterpret_cast<char*>(this) - __start_) + sizeof(*this); }
122};
123
124void unsynchronized_pool_resource::__adhoc_pool::__release_ptr(memory_resource* upstream) {
125 while (__first_ != nullptr) {
126 __chunk_footer* next = __first_->__next_;
127 upstream->deallocate(p: __first_->__start_, bytes: __first_->__allocation_size(), align: __first_->__align_);
128 __first_ = next;
129 }
130}
131
132void* unsynchronized_pool_resource::__adhoc_pool::__do_allocate(memory_resource* upstream, size_t bytes, size_t align) {
133 const size_t footer_size = sizeof(__chunk_footer);
134 const size_t footer_align = alignof(__chunk_footer);
135
136 if (align < footer_align)
137 align = footer_align;
138
139 size_t aligned_capacity = roundup(count: bytes, alignment: footer_align) + footer_size;
140
141 void* result = upstream->allocate(bytes: aligned_capacity, align: align);
142
143 __chunk_footer* h = (__chunk_footer*)((char*)result + aligned_capacity - footer_size);
144 h->__next_ = __first_;
145 h->__start_ = (char*)result;
146 h->__align_ = align;
147 __first_ = h;
148 return result;
149}
150
151void unsynchronized_pool_resource::__adhoc_pool::__do_deallocate(
152 memory_resource* upstream, void* p, size_t bytes, size_t align) {
153 _LIBCPP_ASSERT_NON_NULL(__first_ != nullptr, "deallocating a block that was not allocated with this allocator");
154 if (__first_->__start_ == p) {
155 __chunk_footer* next = __first_->__next_;
156 upstream->deallocate(p: p, bytes: __first_->__allocation_size(), align: __first_->__align_);
157 __first_ = next;
158 } else {
159 for (__chunk_footer* h = __first_; h->__next_ != nullptr; h = h->__next_) {
160 if (h->__next_->__start_ == p) {
161 __chunk_footer* next = h->__next_->__next_;
162 upstream->deallocate(p: p, bytes: h->__next_->__allocation_size(), align: h->__next_->__align_);
163 h->__next_ = next;
164 return;
165 }
166 }
167 // The request to deallocate memory ends up being a no-op, likely resulting in a memory leak.
168 _LIBCPP_ASSERT_VALID_DEALLOCATION(false, "deallocating a block that was not allocated with this allocator");
169 }
170}
171
172class unsynchronized_pool_resource::__fixed_pool {
173 struct __chunk_footer {
174 __chunk_footer* __next_;
175 char* __start_;
176 size_t __align_;
177 size_t __allocation_size() { return (reinterpret_cast<char*>(this) - __start_) + sizeof(*this); }
178 };
179
180 struct __vacancy_header {
181 __vacancy_header* __next_vacancy_;
182 };
183
184 __chunk_footer* __first_chunk_ = nullptr;
185 __vacancy_header* __first_vacancy_ = nullptr;
186
187public:
188 explicit __fixed_pool() = default;
189
190 void __release_ptr(memory_resource* upstream) {
191 __first_vacancy_ = nullptr;
192 while (__first_chunk_ != nullptr) {
193 __chunk_footer* next = __first_chunk_->__next_;
194 upstream->deallocate(p: __first_chunk_->__start_, bytes: __first_chunk_->__allocation_size(), align: __first_chunk_->__align_);
195 __first_chunk_ = next;
196 }
197 }
198
199 void* __try_allocate_from_vacancies() {
200 if (__first_vacancy_ != nullptr) {
201 void* result = __first_vacancy_;
202 __first_vacancy_ = __first_vacancy_->__next_vacancy_;
203 return result;
204 }
205 return nullptr;
206 }
207
208 void* __allocate_in_new_chunk(memory_resource* upstream, size_t block_size, size_t chunk_size) {
209 _LIBCPP_ASSERT_INTERNAL(chunk_size % block_size == 0, "");
210 static_assert(__default_alignment >= alignof(std::max_align_t), "");
211 static_assert(__default_alignment >= alignof(__chunk_footer), "");
212 static_assert(__default_alignment >= alignof(__vacancy_header), "");
213
214 const size_t footer_size = sizeof(__chunk_footer);
215 const size_t footer_align = alignof(__chunk_footer);
216
217 size_t aligned_capacity = roundup(count: chunk_size, alignment: footer_align) + footer_size;
218
219 void* result = upstream->allocate(bytes: aligned_capacity, align: __default_alignment);
220
221 __chunk_footer* h = (__chunk_footer*)((char*)result + aligned_capacity - footer_size);
222 h->__next_ = __first_chunk_;
223 h->__start_ = (char*)result;
224 h->__align_ = __default_alignment;
225 __first_chunk_ = h;
226
227 if (chunk_size > block_size) {
228 __vacancy_header* last_vh = this->__first_vacancy_;
229 for (size_t i = block_size; i != chunk_size; i += block_size) {
230 __vacancy_header* vh = (__vacancy_header*)((char*)result + i);
231 vh->__next_vacancy_ = last_vh;
232 last_vh = vh;
233 }
234 this->__first_vacancy_ = last_vh;
235 }
236 return result;
237 }
238
239 void __evacuate(void* p) {
240 __vacancy_header* vh = (__vacancy_header*)(p);
241 vh->__next_vacancy_ = __first_vacancy_;
242 __first_vacancy_ = vh;
243 }
244
245 size_t __previous_chunk_size_in_bytes() const { return __first_chunk_ ? __first_chunk_->__allocation_size() : 0; }
246
247 static const size_t __default_alignment = alignof(max_align_t);
248};
249
250size_t unsynchronized_pool_resource::__pool_block_size(int i) const { return size_t(1) << __log2_pool_block_size(i: i); }
251
252int unsynchronized_pool_resource::__log2_pool_block_size(int i) const { return (i + __log2_smallest_block_size); }
253
254int unsynchronized_pool_resource::__pool_index(size_t bytes, size_t align) const {
255 if (align > alignof(std::max_align_t) || bytes > (size_t(1) << __num_fixed_pools_))
256 return __num_fixed_pools_;
257 else {
258 int i = 0;
259 bytes = (bytes > align) ? bytes : align;
260 bytes -= 1;
261 bytes >>= __log2_smallest_block_size;
262 while (bytes != 0) {
263 bytes >>= 1;
264 i += 1;
265 }
266 return i;
267 }
268}
269
270unsynchronized_pool_resource::unsynchronized_pool_resource(const pool_options& opts, memory_resource* upstream)
271 : __res_(upstream), __fixed_pools_(nullptr) {
272 size_t largest_block_size;
273 if (opts.largest_required_pool_block == 0)
274 largest_block_size = __default_largest_block_size;
275 else if (opts.largest_required_pool_block < __smallest_block_size)
276 largest_block_size = __smallest_block_size;
277 else if (opts.largest_required_pool_block > __max_largest_block_size)
278 largest_block_size = __max_largest_block_size;
279 else
280 largest_block_size = opts.largest_required_pool_block;
281
282 if (opts.max_blocks_per_chunk == 0)
283 __options_max_blocks_per_chunk_ = __max_blocks_per_chunk;
284 else if (opts.max_blocks_per_chunk < __min_blocks_per_chunk)
285 __options_max_blocks_per_chunk_ = __min_blocks_per_chunk;
286 else if (opts.max_blocks_per_chunk > __max_blocks_per_chunk)
287 __options_max_blocks_per_chunk_ = __max_blocks_per_chunk;
288 else
289 __options_max_blocks_per_chunk_ = opts.max_blocks_per_chunk;
290
291 __num_fixed_pools_ = 1;
292 size_t capacity = __smallest_block_size;
293 while (capacity < largest_block_size) {
294 capacity <<= 1;
295 __num_fixed_pools_ += 1;
296 }
297}
298
299pool_options unsynchronized_pool_resource::options() const {
300 pool_options p;
301 p.max_blocks_per_chunk = __options_max_blocks_per_chunk_;
302 p.largest_required_pool_block = __pool_block_size(i: __num_fixed_pools_ - 1);
303 return p;
304}
305
306void unsynchronized_pool_resource::release() {
307 __adhoc_pool_.__release_ptr(upstream: __res_);
308 if (__fixed_pools_ != nullptr) {
309 const int n = __num_fixed_pools_;
310 for (int i = 0; i < n; ++i)
311 __fixed_pools_[i].__release_ptr(upstream: __res_);
312 __res_->deallocate(p: __fixed_pools_, bytes: __num_fixed_pools_ * sizeof(__fixed_pool), align: alignof(__fixed_pool));
313 __fixed_pools_ = nullptr;
314 }
315}
316
317void* unsynchronized_pool_resource::do_allocate(size_t bytes, size_t align) {
318 // A pointer to allocated storage (6.6.4.4.1) with a size of at least bytes.
319 // The size and alignment of the allocated memory shall meet the requirements for
320 // a class derived from memory_resource (23.12).
321 // If the pool selected for a block of size bytes is unable to satisfy the memory request
322 // from its own internal data structures, it will call upstream_resource()->allocate()
323 // to obtain more memory. If bytes is larger than that which the largest pool can handle,
324 // then memory will be allocated using upstream_resource()->allocate().
325
326 int i = __pool_index(bytes, align);
327 if (i == __num_fixed_pools_)
328 return __adhoc_pool_.__do_allocate(upstream: __res_, bytes, align);
329 else {
330 if (__fixed_pools_ == nullptr) {
331 __fixed_pools_ =
332 (__fixed_pool*)__res_->allocate(bytes: __num_fixed_pools_ * sizeof(__fixed_pool), align: alignof(__fixed_pool));
333 __fixed_pool* first = __fixed_pools_;
334 __fixed_pool* last = __fixed_pools_ + __num_fixed_pools_;
335 for (__fixed_pool* pool = first; pool != last; ++pool)
336 ::new ((void*)pool) __fixed_pool;
337 }
338 void* result = __fixed_pools_[i].__try_allocate_from_vacancies();
339 if (result == nullptr) {
340 auto min = [](size_t a, size_t b) { return a < b ? a : b; };
341 auto max = [](size_t a, size_t b) { return a < b ? b : a; };
342
343 size_t prev_chunk_size_in_bytes = __fixed_pools_[i].__previous_chunk_size_in_bytes();
344 size_t prev_chunk_size_in_blocks = prev_chunk_size_in_bytes >> __log2_pool_block_size(i);
345
346 size_t chunk_size_in_blocks;
347
348 if (prev_chunk_size_in_blocks == 0) {
349 size_t min_blocks_per_chunk = max(__min_bytes_per_chunk >> __log2_pool_block_size(i), __min_blocks_per_chunk);
350 chunk_size_in_blocks = min_blocks_per_chunk;
351 } else {
352 static_assert(__max_bytes_per_chunk <= SIZE_MAX - (__max_bytes_per_chunk / 4), "unsigned overflow is possible");
353 chunk_size_in_blocks = prev_chunk_size_in_blocks + (prev_chunk_size_in_blocks / 4);
354 }
355
356 size_t max_blocks_per_chunk =
357 min((__max_bytes_per_chunk >> __log2_pool_block_size(i)),
358 min(__max_blocks_per_chunk, __options_max_blocks_per_chunk_));
359 if (chunk_size_in_blocks > max_blocks_per_chunk)
360 chunk_size_in_blocks = max_blocks_per_chunk;
361
362 size_t block_size = __pool_block_size(i);
363
364 size_t chunk_size_in_bytes = (chunk_size_in_blocks << __log2_pool_block_size(i));
365 result = __fixed_pools_[i].__allocate_in_new_chunk(upstream: __res_, block_size, chunk_size: chunk_size_in_bytes);
366 }
367 return result;
368 }
369}
370
371void unsynchronized_pool_resource::do_deallocate(void* p, size_t bytes, size_t align) {
372 // Returns the memory at p to the pool. It is unspecified if,
373 // or under what circumstances, this operation will result in
374 // a call to upstream_resource()->deallocate().
375
376 int i = __pool_index(bytes, align);
377 if (i == __num_fixed_pools_)
378 return __adhoc_pool_.__do_deallocate(upstream: __res_, p, bytes, align);
379 else {
380 _LIBCPP_ASSERT_NON_NULL(
381 __fixed_pools_ != nullptr, "deallocating a block that was not allocated with this allocator");
382 __fixed_pools_[i].__evacuate(p);
383 }
384}
385
386bool synchronized_pool_resource::do_is_equal(const memory_resource& other) const noexcept { return &other == this; }
387
388// 23.12.6, mem.res.monotonic.buffer
389
390constexpr size_t __default_growth_factor = 2;
391
392static void* align_down(size_t align, size_t size, void*& ptr, size_t& space) {
393 if (size > space)
394 return nullptr;
395
396 char* p1 = static_cast<char*>(ptr);
397 char* new_ptr = reinterpret_cast<char*>(reinterpret_cast<uintptr_t>(p1 - size) & ~(align - 1));
398
399 if (new_ptr < (p1 - space))
400 return nullptr;
401
402 ptr = new_ptr;
403 space -= p1 - new_ptr;
404
405 return ptr;
406}
407
408template <bool is_initial, typename Chunk>
409void* __try_allocate_from_chunk(Chunk& self, size_t bytes, size_t align) {
410 if constexpr (is_initial) {
411 // only for __initial_descriptor.
412 // if __initial_descriptor.__cur_ equals nullptr, means no available buffer given when ctor.
413 // here we just return nullptr, let the caller do the next handling.
414 if (!self.__cur_)
415 return nullptr;
416 }
417 void* new_ptr = static_cast<void*>(self.__cur_);
418 size_t new_capacity = (self.__cur_ - self.__start_);
419 void* aligned_ptr = align_down(align, size: bytes, ptr&: new_ptr, space&: new_capacity);
420 if (aligned_ptr != nullptr)
421 self.__cur_ = static_cast<char*>(new_ptr);
422 return aligned_ptr;
423}
424
425void* monotonic_buffer_resource::do_allocate(size_t bytes, size_t align) {
426 const size_t footer_size = sizeof(__chunk_footer);
427 const size_t footer_align = alignof(__chunk_footer);
428
429 auto previous_allocation_size = [&]() {
430 if (__chunks_ != nullptr)
431 return __chunks_->__allocation_size();
432
433 size_t newsize = (__initial_.__start_ != nullptr) ? (__initial_.__end_ - __initial_.__start_) : __initial_.__size_;
434
435 return roundup(count: newsize, alignment: footer_align) + footer_size;
436 };
437
438 if (void* result = __try_allocate_from_chunk<true, __initial_descriptor>(self&: __initial_, bytes, align))
439 return result;
440 if (__chunks_ != nullptr) {
441 if (void* result = __try_allocate_from_chunk<false, __chunk_footer>(self&: *__chunks_, bytes, align))
442 return result;
443 }
444
445 // Allocate a brand-new chunk.
446
447 if (align < footer_align)
448 align = footer_align;
449
450 size_t aligned_capacity = roundup(count: bytes, alignment: footer_align) + footer_size;
451 size_t previous_capacity = previous_allocation_size();
452
453 if (aligned_capacity <= previous_capacity) {
454 size_t newsize = __default_growth_factor * (previous_capacity - footer_size);
455 aligned_capacity = roundup(count: newsize, alignment: footer_align) + footer_size;
456 }
457
458 char* start = (char*)__res_->allocate(bytes: aligned_capacity, align: align);
459 auto end = start + aligned_capacity - footer_size;
460 __chunk_footer* footer = (__chunk_footer*)(end);
461 footer->__next_ = __chunks_;
462 footer->__start_ = start;
463 footer->__cur_ = end;
464 footer->__align_ = align;
465 __chunks_ = footer;
466
467 return __try_allocate_from_chunk<false, __chunk_footer>(self&: *__chunks_, bytes, align);
468}
469
470} // namespace pmr
471
472_LIBCPP_END_EXPLICIT_ABI_ANNOTATIONS
473_LIBCPP_END_NAMESPACE_STD
474