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