501 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include <cstddef>10#include <memory>11#include <memory_resource>12 13#if _LIBCPP_HAS_ATOMIC_HEADER14# include <atomic>15#elif _LIBCPP_HAS_THREADS16# include <mutex>17# if defined(__ELF__) && defined(_LIBCPP_LINK_PTHREAD_LIB)18# pragma comment(lib, "pthread")19# endif20#endif21 22_LIBCPP_BEGIN_NAMESPACE_STD23 24namespace pmr {25 26// memory_resource27 28memory_resource::~memory_resource() = default;29 30// new_delete_resource()31 32#if !_LIBCPP_HAS_ALIGNED_ALLOCATION33static 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#endif40 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_ALLOCATION44 return std::__libcpp_allocate<std::byte>(__element_count(bytes), align);45#else46 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#endif55 }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_priority85// attribute with a value that's reserved for the implementation (we're the implementation).86#include "memory_resource_init_helper.h"87 88} // namespace89 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_HEADER98 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_THREADS107 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#else120 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#endif130}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.pool139 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 else308 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 else317 __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 for348 // 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 request350 // 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 in402 // 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.buffer417 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 pmr499 500_LIBCPP_END_NAMESPACE_STD501