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