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