diff options
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/ChangeLog | 32 | ||||
| -rw-r--r-- | libstdc++-v3/config/abi/pre/gnu.ver | 9 | ||||
| -rw-r--r-- | libstdc++-v3/include/std/memory_resource | 105 | ||||
| -rw-r--r-- | libstdc++-v3/src/c++17/Makefile.am | 5 | ||||
| -rw-r--r-- | libstdc++-v3/src/c++17/Makefile.in | 5 | ||||
| -rw-r--r-- | libstdc++-v3/src/c++17/memory_resource.cc | 786 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc | 155 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/is_equal.cc | 38 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/options.cc | 42 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/release.cc | 113 |
10 files changed, 1285 insertions, 5 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index fe28f52..0231623 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,35 @@ +2018-11-06 Jonathan Wakely <jwakely@redhat.com> + + Implement std::pmr::unsynchronized_pool_resource + * config/abi/pre/gnu.ver: Add new symbols. + * include/std/memory_resource (std::pmr::__pool_resource): New class. + (std::pmr::unsynchronized_pool_resource): New class. + * src/c++17/Makefile.am: Add -fimplicit-templates to flags for + memory_resource.cc + * src/c++17/Makefile.in: Regenerate. + * src/c++17/memory_resource.cc (bitset, chunk, big_block): New + internal classes. + (__pool_resource::_Pool): Define new class. + (munge_options, pool_index, select_num_pools): New internal functions. + (__pool_resource::__pool_resource, __pool_resource::~__pool_resource) + (__pool_resource::allocate, __pool_resource::deallocate) + (__pool_resource::_M_alloc_pools): Define member functions. + (unsynchronized_pool_resource::unsynchronized_pool_resource) + (unsynchronized_pool_resource::~unsynchronized_pool_resource) + (unsynchronized_pool_resource::release) + (unsynchronized_pool_resource::_M_find_pool) + (unsynchronized_pool_resource::do_allocate) + (unsynchronized_pool_resource::do_deallocate): Define member + functions. + * testsuite/20_util/unsynchronized_pool_resource/allocate.cc: New + test. + * testsuite/20_util/unsynchronized_pool_resource/is_equal.cc: New + test. + * testsuite/20_util/unsynchronized_pool_resource/options.cc: New + test. + * testsuite/20_util/unsynchronized_pool_resource/release.cc: New + test. + 2018-11-06 John Bytheway <jbytheway@gmail.com> PR libstdc++/87872 diff --git a/libstdc++-v3/config/abi/pre/gnu.ver b/libstdc++-v3/config/abi/pre/gnu.ver index e8cd286..b55038b 100644 --- a/libstdc++-v3/config/abi/pre/gnu.ver +++ b/libstdc++-v3/config/abi/pre/gnu.ver @@ -2055,6 +2055,15 @@ GLIBCXX_3.4.26 { _ZNSt13basic_filebufI[cw]St11char_traitsI[cw]EE4openEPKwSt13_Ios_Openmode; _ZN11__gnu_debug25_Safe_local_iterator_base16_M_attach_singleEPNS_19_Safe_sequence_baseEb; + + # <memory_resource> members + _ZTINSt3pmr28unsynchronized_pool_resourceE; + _ZNSt3pmr28unsynchronized_pool_resourceC[12]ERKNS_12pool_optionsEPNS_15memory_resourceE; + _ZNSt3pmr28unsynchronized_pool_resourceD[12]Ev; + _ZNSt3pmr28unsynchronized_pool_resource7releaseEv; + _ZNSt3pmr28unsynchronized_pool_resource11do_allocateEmm; + _ZNSt3pmr28unsynchronized_pool_resource13do_deallocateEPvmm; + } GLIBCXX_3.4.25; # Symbols in the support library (libsupc++) have their own tag. diff --git a/libstdc++-v3/include/std/memory_resource b/libstdc++-v3/include/std/memory_resource index 7dc35ae..40486af 100644 --- a/libstdc++-v3/include/std/memory_resource +++ b/libstdc++-v3/include/std/memory_resource @@ -33,9 +33,9 @@ #if __cplusplus >= 201703L -#include <bit> // __ceil2, __log2p1 #include <memory> // align, allocator_arg_t, __uses_alloc #include <utility> // pair, index_sequence +#include <vector> // vector #include <cstddef> // size_t, max_align_t #include <debug/assertions.h> @@ -296,8 +296,107 @@ namespace pmr size_t largest_required_pool_block = 0; }; - // TODO class synchronized_pool_resource; - // TODO class unsynchronized_pool_resource; + // Common implementation details for unsynchronized/synchronized pool resources. + class __pool_resource + { + friend class synchronized_pool_resource; + friend class unsynchronized_pool_resource; + + __pool_resource(const pool_options& __opts, memory_resource* __upstream); + + ~__pool_resource(); + + __pool_resource(const __pool_resource&) = delete; + __pool_resource& operator=(const __pool_resource&) = delete; + + // Allocate a large unpooled block. + void* + allocate(size_t __bytes, size_t __alignment); + + // Deallocate a large unpooled block. + void + deallocate(void* __p, size_t __bytes, size_t __alignment); + + + // Deallocate unpooled memory. + void release() noexcept; + + memory_resource* resource() const noexcept + { return _M_unpooled.get_allocator().resource(); } + + struct _Pool; + + _Pool* _M_alloc_pools(); + + const pool_options _M_opts; + + struct _BigBlock; + // Collection of blocks too big for any pool, sorted by address. + // This also stores the only copy of the upstream memory resource pointer. + pmr::vector<_BigBlock> _M_unpooled; + + const int _M_npools; + }; + + // TODO class synchronized_pool_resource + + /// A non-thread-safe memory resource that manages pools of fixed-size blocks. + class unsynchronized_pool_resource : public memory_resource + { + public: + [[__gnu__::__nonnull__]] + unsynchronized_pool_resource(const pool_options& __opts, + memory_resource* __upstream); + + unsynchronized_pool_resource() + : unsynchronized_pool_resource(pool_options(), get_default_resource()) + { } + + [[__gnu__::__nonnull__]] + explicit + unsynchronized_pool_resource(memory_resource* __upstream) + : unsynchronized_pool_resource(pool_options(), __upstream) + { } + + explicit + unsynchronized_pool_resource(const pool_options& __opts) + : unsynchronized_pool_resource(__opts, get_default_resource()) { } + + unsynchronized_pool_resource(const unsynchronized_pool_resource&) = delete; + + virtual ~unsynchronized_pool_resource(); + + unsynchronized_pool_resource& + operator=(const unsynchronized_pool_resource&) = delete; + + void release(); + + [[__gnu__::__returns_nonnull__]] + memory_resource* + upstream_resource() const noexcept + { return _M_impl.resource(); } + + pool_options options() const noexcept { return _M_impl._M_opts; } + + protected: + void* + do_allocate(size_t __bytes, size_t __alignment) override; + + void + do_deallocate(void* __p, size_t __bytes, size_t __alignment) override; + + bool + do_is_equal(const memory_resource& __other) const noexcept override + { return this == &__other; } + + private: + using _Pool = __pool_resource::_Pool; + + auto _M_find_pool(size_t) noexcept; + + __pool_resource _M_impl; + _Pool* _M_pools = nullptr; + }; class monotonic_buffer_resource : public memory_resource { diff --git a/libstdc++-v3/src/c++17/Makefile.am b/libstdc++-v3/src/c++17/Makefile.am index 21b64b5..c748f50 100644 --- a/libstdc++-v3/src/c++17/Makefile.am +++ b/libstdc++-v3/src/c++17/Makefile.am @@ -63,6 +63,11 @@ AM_CXXFLAGS = \ AM_MAKEFLAGS = \ "gxx_include_dir=$(gxx_include_dir)" +memory_resource.lo: memory_resource.cc + $(LTCXXCOMPILE) -fimplicit-templates -c $< -o $@ +memory_resource.o: memory_resource.cc + $(CXXCOMPILE) -fimplicit-templates -c $< -o $@ + # Libtool notes # 1) In general, libtool expects an argument such as `--tag=CXX' when diff --git a/libstdc++-v3/src/c++17/Makefile.in b/libstdc++-v3/src/c++17/Makefile.in index efa4fd9..287b4b8 100644 --- a/libstdc++-v3/src/c++17/Makefile.in +++ b/libstdc++-v3/src/c++17/Makefile.in @@ -731,6 +731,11 @@ uninstall-am: vpath % $(top_srcdir)/src/c++17 +memory_resource.lo: memory_resource.cc + $(LTCXXCOMPILE) -fimplicit-templates -c $< -o $@ +memory_resource.o: memory_resource.cc + $(CXXCOMPILE) -fimplicit-templates -c $< -o $@ + # Tell versions [3.59,3.63) of GNU make to not export all variables. # Otherwise a system limit (for SysV at least) may be exceeded. .NOEXPORT: diff --git a/libstdc++-v3/src/c++17/memory_resource.cc b/libstdc++-v3/src/c++17/memory_resource.cc index aa82813..781bdad 100644 --- a/libstdc++-v3/src/c++17/memory_resource.cc +++ b/libstdc++-v3/src/c++17/memory_resource.cc @@ -23,7 +23,9 @@ // <http://www.gnu.org/licenses/>. #include <memory_resource> +#include <algorithm> // lower_bound, rotate #include <atomic> +#include <bit> // __ceil2, __log2p1 #include <new> #if ATOMIC_POINTER_LOCK_FREE != 2 # include <bits/std_mutex.h> // std::mutex, std::lock_guard @@ -246,8 +248,788 @@ namespace pmr _Chunk::release(_M_head, _M_upstream); } + // Helper types for synchronized_pool_resource & unsynchronized_pool_resource + + namespace { + + // Simple bitset with runtime size. Tracks used blocks in a pooled chunk. + struct bitset + { + using word = uint64_t; + using size_type = uint32_t; + + static constexpr unsigned bits_per_word = numeric_limits<word>::digits; + + // The bitset does not own p + bitset(void* p, size_type num_blocks) + : _M_words(static_cast<word*>(p)), _M_size(num_blocks), + _M_next_word(0) + { + const size_type last_word = num_blocks / bits_per_word; + __builtin_memset(_M_words, 0, last_word * sizeof(*_M_words)); + // Set bits beyond _M_size, so they are not treated as free blocks: + if (const size_type extra_bits = num_blocks % bits_per_word) + _M_words[last_word] = (word)-1 << extra_bits; + __glibcxx_assert( empty() ); + __glibcxx_assert( free() == num_blocks ); + } + + bitset() = default; + ~bitset() = default; + + // Number of blocks + size_t size() const noexcept { return _M_size; } + + // Number of unset bits + size_t free() const noexcept + { + size_t n = 0; + for (size_type i = _M_next_word; i < nwords(); ++i) + n += (bits_per_word - std::__popcount(_M_words[i])); + return n; + } + + // True if all bits are set + bool full() const noexcept { return _M_next_word >= nwords(); } + + // True if size() != 0 and no bits are set. + bool empty() const noexcept + { + if (nwords() == 0) + return false; + if (_M_next_word != 0) + return false; + for (size_type i = 0; i < nwords() - 1; ++i) + if (_M_words[i] != 0) + return false; + word last = _M_words[nwords() - 1]; + if (const size_type extra_bits = size() % bits_per_word) + last <<= (bits_per_word - extra_bits); + return last == 0; + } + + void reset() noexcept + { + _M_words = nullptr; + _M_size = _M_next_word = 0; + } + + bool operator[](size_type n) const noexcept + { + __glibcxx_assert( n < _M_size ); + const size_type wd = n / bits_per_word; + const word bit = word(1) << (n % bits_per_word); + return _M_words[wd] & bit; + } + + size_type find_first_unset() const noexcept + { + for (size_type i = _M_next_word; i < nwords(); ++i) + { + const size_type n = std::__countr_one(_M_words[i]); + if (n < bits_per_word) + return (i * bits_per_word) + n; + } + return size_type(-1); + } + + size_type get_first_unset() noexcept + { + for (size_type i = _M_next_word; i < nwords(); ++i) + { + const size_type n = std::__countr_one(_M_words[i]); + if (n < bits_per_word) + { + const word bit = word(1) << n; + _M_words[i] |= bit; + if (i == _M_next_word) + { + while (_M_words[_M_next_word] == word(-1) + && ++_M_next_word != nwords()) + { } + } + return (i * bits_per_word) + n; + } + } + return size_type(-1); + } + + void set(size_type n) noexcept + { + __glibcxx_assert( n < _M_size ); + const size_type wd = n / bits_per_word; + const word bit = word(1) << (n % bits_per_word); + _M_words[wd] |= bit; + if (wd == _M_next_word) + { + while (_M_words[_M_next_word] == word(-1) + && ++_M_next_word != nwords()) + { } + } + } + + void clear(size_type n) noexcept + { + __glibcxx_assert( n < _M_size ); + const size_type wd = n / bits_per_word; + const word bit = word(1) << (n % bits_per_word); + _M_words[wd] &= ~bit; + if (wd < _M_next_word) + _M_next_word = wd; + } + + void swap(bitset& b) noexcept + { + std::swap(_M_words, b._M_words); + size_type tmp = _M_size; + _M_size = b._M_size; + b._M_size = tmp; + tmp = _M_next_word; + _M_next_word = b._M_next_word; + b._M_next_word = tmp; + } + + size_type nwords() const noexcept + { return (_M_size + bits_per_word - 1) / bits_per_word; } + + // Maximum value that can be stored in bitset::_M_size member (approx 500k) + static constexpr size_t max_blocks_per_chunk() noexcept + { return (1ull << _S_size_digits) - 1; } + + word* data() const noexcept { return _M_words; } + + private: + static constexpr unsigned _S_size_digits + = (numeric_limits<size_type>::digits + + std::__log2p1(bits_per_word) - 1) / 2; + + word* _M_words = nullptr; + // Number of blocks represented by the bitset: + size_type _M_size : _S_size_digits; + // Index of the first word with unset bits: + size_type _M_next_word : numeric_limits<size_type>::digits - _S_size_digits; + }; + + // A "chunk" belonging to a pool. + // A chunk contains many blocks of the same size. + // Derived from bitset to reuse its tail-padding. + struct chunk : bitset + { + chunk() = default; + + // p points to the start of a chunk of size bytes in length. + // The chunk has space for n blocks, followed by a bitset of size n + // that begins at address words. + // This object does not own p or words, the caller will free it. + chunk(void* p, size_t bytes, void* words, size_t n) + : bitset(words, n), + _M_bytes(bytes), + _M_p(static_cast<std::byte*>(p)) + { } + + chunk(chunk&& c) noexcept + : bitset(std::move(c)), _M_bytes(c._M_bytes), _M_p(c._M_p) + { + c._M_bytes = 0; + c._M_p = nullptr; + c.reset(); + } + + chunk& operator=(chunk&& c) noexcept + { + swap(c); + return *this; + } + + // Allocated size of chunk: + unsigned _M_bytes = 0; + // Start of allocated chunk: + std::byte* _M_p = nullptr; + + // True if there are free blocks in this chunk + using bitset::full; + // Number of blocks in this chunk + using bitset::size; + + // Determine if block with address p and size block_size + // is contained within this chunk. + bool owns(void* p, size_t block_size) + { + std::less_equal<uintptr_t> less_equal; + return less_equal(reinterpret_cast<uintptr_t>(_M_p), + reinterpret_cast<uintptr_t>(p)) + && less_equal(reinterpret_cast<uintptr_t>(p) + block_size, + reinterpret_cast<uintptr_t>(bitset::data())); + } + + // Allocate next available block of block_size bytes from this chunk. + void* reserve(size_t block_size) noexcept + { + const size_type n = get_first_unset(); + if (n == size_type(-1)) + return nullptr; + return _M_p + (n * block_size); + } + + // Deallocate a single block of block_size bytes + void release(void* vp, size_t block_size) + { + __glibcxx_assert( owns(vp, block_size) ); + const size_t offset = static_cast<std::byte*>(vp) - _M_p; + // Pointer is correctly aligned for a block in this chunk: + __glibcxx_assert( (offset % block_size) == 0 ); + // Block has been allocated: + __glibcxx_assert( (*this)[offset / block_size] == true ); + bitset::clear(offset / block_size); + } + + // Deallocate a single block if it belongs to this chunk. + bool try_release(void* p, size_t block_size) + { + if (!owns(p, block_size)) + return false; + release(p, block_size); + return true; + } + + void swap(chunk& c) noexcept + { + std::swap(_M_bytes, c._M_bytes); + std::swap(_M_p, c._M_p); + bitset::swap(c); + } + + bool operator<(const chunk& c) const noexcept + { return std::less<const void*>{}(_M_p, c._M_p); } + + friend void swap(chunk& l, chunk& r) { l.swap(r); } + + friend bool operator<(const void* p, const chunk& c) noexcept + { return std::less<const void*>{}(p, c._M_p); } + }; + +#ifdef __LP64__ + // TODO pad up to 4*sizeof(void*) to avoid splitting across cache lines? + static_assert(sizeof(chunk) == (3 * sizeof(void*)), ""); +#else + static_assert(sizeof(chunk) == (4 * sizeof(void*)), ""); +#endif + + // An oversized allocation that doesn't fit in a pool. + struct big_block + { + static constexpr unsigned _S_alignbits + = std::__log2p1((unsigned)numeric_limits<size_t>::digits) - 1; + static constexpr unsigned _S_sizebits + = numeric_limits<size_t>::digits - _S_alignbits; + // The maximum value that can be stored in _S_size + static constexpr size_t all_ones = (1ul << _S_sizebits) - 1u; + // The minimum size of a big block + static constexpr size_t min = 1u << _S_alignbits; + + big_block(size_t bytes, size_t alignment) + : _M_size((bytes + min - 1u) >> _S_alignbits), + _M_align_exp(std::__log2p1(alignment) - 1u) + { + if (__builtin_expect(std::__countl_one(bytes) == _S_sizebits, false)) + _M_size = all_ones; + } + + void* pointer = nullptr; + size_t _M_size : numeric_limits<size_t>::digits - _S_alignbits; + size_t _M_align_exp : _S_alignbits; + + size_t size() const noexcept + { + if (__builtin_expect(_M_size == all_ones, false)) + return (size_t)-1; + else + return _M_size << _S_alignbits; + } + + size_t align() const noexcept { return 1ul << _M_align_exp; } + + friend bool operator<(void* p, const big_block& b) noexcept + { return less<void*>{}(p, b.pointer); } + + friend bool operator<(const big_block& b, void* p) noexcept + { return less<void*>{}(b.pointer, p); } + }; + + static_assert(sizeof(big_block) == (2 * sizeof(void*))); + + } // namespace + + // A pool that serves blocks of a particular size. + // Each pool manages a number of chunks. + // When a pool is full it is replenished by allocating another chunk. + struct __pool_resource::_Pool + { + // Smallest supported block size + static constexpr unsigned _S_min_block + = std::max(sizeof(void*), alignof(bitset::word)); + + _Pool(size_t __block_size, size_t __blocks_per_chunk) + : _M_chunks(), + _M_block_sz(__block_size), + _M_blocks_per_chunk(__blocks_per_chunk) + { + __glibcxx_assert(block_size() == __block_size); + } + + // Must call release(r) before destruction! + ~_Pool() { __glibcxx_assert(_M_chunks.empty()); } + + _Pool(_Pool&&) noexcept = default; + _Pool& operator=(_Pool&&) noexcept = default; + + // Size of blocks in this pool + size_t block_size() const noexcept +#if POW2_BLKSZ + { return _S_min_block << _M_blksize_mul; } +#else + { return _M_block_sz; } +#endif + + // Allocate a block if the pool is not full, otherwise return null. + void* try_allocate() noexcept + { + const size_t blocksz = block_size(); + if (!_M_chunks.empty()) + { + auto& last = _M_chunks.back(); + if (void* p = last.reserve(blocksz)) + return p; + // TODO last is full, so move another chunk to the back instead? + for (auto it = _M_chunks.begin(); it != &last; ++it) + if (void* p = it->reserve(blocksz)) + return p; + } + return nullptr; + } + + // Allocate a block from the pool, replenishing from upstream if needed. + void* allocate(memory_resource* r, const pool_options& opts) + { + if (void* p = try_allocate()) + return p; + replenish(r, opts); + return _M_chunks.back().reserve(block_size()); + } + + // Return a block to the pool. + bool deallocate(memory_resource*, void* p) + { + const size_t blocksz = block_size(); + if (__builtin_expect(!_M_chunks.empty(), true)) + { + auto& last = _M_chunks.back(); + if (last.try_release(p, blocksz)) + return true; + auto it = std::upper_bound(_M_chunks.begin(), &last, p); + if (it != _M_chunks.begin()) + { + it--; + if (it->try_release(p, blocksz)) + // If chunk is empty could return to upstream, but we don't + // currently do that. Pools only increase in size. + return true; + } + } + return false; + } + + void replenish(memory_resource* __r, const pool_options& __opts) + { + using word = chunk::word; + const size_t __blocks + = std::min<size_t>(__opts.max_blocks_per_chunk, _M_blocks_per_chunk); + const auto __bits = chunk::bits_per_word; + const size_t __words = (__blocks + __bits - 1) / __bits; + const size_t __block_size = block_size(); + size_t __bytes = __blocks * __block_size + __words * sizeof(word); + size_t __alignment = std::__ceil2(__block_size); + void* __p = __r->allocate(__bytes, __alignment); + __try + { + size_t __n = __blocks * __block_size; + void* __pwords = static_cast<char*>(__p) + __n; + _M_chunks.insert(chunk(__p, __bytes, __pwords, __blocks), __r); + } + __catch (...) + { + __r->deallocate(__p, __bytes, __alignment); + } + if (_M_blocks_per_chunk < __opts.max_blocks_per_chunk) + _M_blocks_per_chunk *= 2; + } + + void release(memory_resource* __r) + { + const size_t __alignment = std::__ceil2(block_size()); + for (auto& __c : _M_chunks) + if (__c._M_p) + __r->deallocate(__c._M_p, __c._M_bytes, __alignment); + _M_chunks.clear(__r); + } + + // A "resourceless vector" instead of pmr::vector, to save space. + // All resize operations need to be passed a memory resource, which + // obviously needs to be the same one every time. + // Chunks are kept sorted by address of their first block, except for + // the most recently-allocated Chunk which is at the end of the vector. + struct vector + { + using value_type = chunk; + using size_type = unsigned; + using iterator = value_type*; + + // A vector owns its data pointer but not memory held by its elements. + chunk* data = nullptr; + size_type size = 0; + size_type capacity = 0; + + vector() = default; + + vector(size_type __n, memory_resource* __r) + : data(polymorphic_allocator<value_type>(__r).allocate(__n)), + capacity(__n) + { } + + // Must call clear(r) before destruction! + ~vector() { __glibcxx_assert(data == nullptr); } + + vector(vector&& __rval) noexcept + : data(__rval.data), size(__rval.size), capacity(__rval.capacity) + { + __rval.data = nullptr; + __rval.capacity = __rval.size = 0; + } + + vector& operator=(vector&& __rval) noexcept + { + __glibcxx_assert(data == nullptr); + data = __rval.data; + size = __rval.size; + capacity = __rval.capacity; + __rval.data = nullptr; + __rval.capacity = __rval.size = 0; + return *this; + } + + // void resize(size_type __n, memory_resource* __r); + // void reserve(size_type __n, memory_resource* __r); + + void clear(memory_resource* __r) + { + if (!data) + return; + // Chunks must be individually freed before clearing the vector. + std::destroy(begin(), end()); + polymorphic_allocator<value_type>(__r).deallocate(data, capacity); + data = nullptr; + capacity = size = 0; + } + + // Sort existing elements then insert new one at the end. + iterator insert(chunk&& c, memory_resource* r) + { + if (size < capacity) + { + if (size > 1) + { + auto mid = end() - 1; + std::rotate(std::lower_bound(begin(), mid, *mid), mid, end()); + } + } + else if (size > 0) + { + polymorphic_allocator<value_type> __alloc(r); + auto __mid = std::lower_bound(begin(), end() - 1, back()); + auto __p = __alloc.allocate(capacity * 1.5); + // move [begin,__mid) to new storage + auto __p2 = std::move(begin(), __mid, __p); + // move end-1 to new storage + *__p2 = std::move(back()); + // move [__mid,end-1) to new storage + std::move(__mid, end() - 1, ++__p2); + std::destroy(begin(), end()); + __alloc.deallocate(data, capacity); + data = __p; + capacity *= 1.5; + } + else + { + polymorphic_allocator<value_type> __alloc(r); + data = __alloc.allocate(capacity = 8); + } + auto back = ::new (data + size) chunk(std::move(c)); + __glibcxx_assert(std::is_sorted(begin(), back)); + ++size; + return back; + } + + iterator begin() const { return data; } + iterator end() const { return data + size; } + + bool empty() const noexcept { return size == 0; } + + value_type& back() { return data[size - 1]; } + }; + + vector _M_chunks; + unsigned _M_block_sz; // size of blocks allocated from this pool + unsigned _M_blocks_per_chunk; // number of blocks to allocate next + }; + + // An oversized allocation that doesn't fit in a pool. + struct __pool_resource::_BigBlock : big_block + { + using big_block::big_block; + }; + + namespace { + + pool_options + munge_options(pool_options opts) + { + // The values in the returned struct may differ from those supplied + // to the pool resource constructor in that values of zero will be + // replaced with implementation-defined defaults, and sizes may be + // rounded to unspecified granularity. + + // Absolute maximum. Each pool might have a smaller maximum. + if (opts.max_blocks_per_chunk == 0) + { + opts.max_blocks_per_chunk = 1024 * 10; // TODO a good default? + } + else + { + // TODO round to preferred granularity ? + } + + if (opts.max_blocks_per_chunk > chunk::max_blocks_per_chunk()) + { + opts.max_blocks_per_chunk = chunk::max_blocks_per_chunk(); + } + + // Absolute minimum. Likely to be much larger in practice. + if (opts.largest_required_pool_block == 0) + { + opts.largest_required_pool_block = 4096; // TODO a good default? + } + else + { + // TODO round to preferred granularity ? + } + + if (opts.largest_required_pool_block < big_block::min) + { + opts.largest_required_pool_block = big_block::min; + } + return opts; + } + + const size_t pool_sizes[] = { + 8, 16, 24, + 32, 48, + 64, 80, 96, 112, + 128, 192, + 256, 320, 384, 448, + 512, 768, + 1024, 1536, + 2048, 3072, + 1<<12, 1<<13, 1<<14, 1<<15, 1<<16, 1<<17, + 1<<20, 1<<21, 1<<22 // 4MB should be enough for anybody + }; + + inline int + pool_index(size_t block_size, int npools) + { + auto p = std::lower_bound(pool_sizes, pool_sizes + npools, block_size); + int n = p - pool_sizes; + if (n != npools) + return n; + return -1; + } + + inline int + select_num_pools(const pool_options& opts) + { + auto p = std::lower_bound(std::begin(pool_sizes), std::end(pool_sizes), + opts.largest_required_pool_block); + if (int npools = p - std::begin(pool_sizes)) + return npools; + return 1; + } + + } // namespace + + __pool_resource:: + __pool_resource(const pool_options& opts, memory_resource* upstream) + : _M_opts(munge_options(opts)), _M_unpooled(upstream), + _M_npools(select_num_pools(_M_opts)) + { } + + __pool_resource::~__pool_resource() { release(); } + + void + __pool_resource::release() noexcept + { + memory_resource* res = resource(); + // deallocate oversize allocations + for (auto& b : _M_unpooled) + res->deallocate(b.pointer, b.size(), b.align()); + pmr::vector<_BigBlock>{res}.swap(_M_unpooled); + } + + void* + __pool_resource::allocate(size_t bytes, size_t alignment) + { + auto& b = _M_unpooled.emplace_back(bytes, alignment); + __try { + void* p = resource()->allocate(b.size(), alignment); + b.pointer = p; + if (_M_unpooled.size() > 1) + { + const auto mid = _M_unpooled.end() - 1; + // move to right position in vector + std::rotate(std::lower_bound(_M_unpooled.begin(), mid, p), + mid, _M_unpooled.end()); + } + return p; + } __catch(...) { + _M_unpooled.pop_back(); + __throw_exception_again; + } + } + + void + __pool_resource::deallocate(void* p, size_t bytes [[maybe_unused]], + size_t alignment [[maybe_unused]]) + { + const auto it + = std::lower_bound(_M_unpooled.begin(), _M_unpooled.end(), p); + __glibcxx_assert(it != _M_unpooled.end() && it->pointer == p); + if (it != _M_unpooled.end() && it->pointer == p) // [[likely]] + { + const auto b = *it; + __glibcxx_assert(b.size() == bytes); + __glibcxx_assert(b.align() == alignment); + _M_unpooled.erase(it); + resource()->deallocate(p, b.size(), b.align()); + } + } + + // Create array of pools, allocated from upstream resource. + auto + __pool_resource::_M_alloc_pools() + -> _Pool* + { + polymorphic_allocator<_Pool> alloc{resource()}; + _Pool* p = alloc.allocate(_M_npools); + for (int i = 0; i < _M_npools; ++i) + { + const size_t block_size = pool_sizes[i]; + // Decide on initial number of blocks per chunk. + // Always have at least 16 blocks per chunk: + const size_t min_blocks_per_chunk = 16; + // But for smaller blocks, use a larger initial size: + size_t blocks_per_chunk + = std::max(1024 / block_size, min_blocks_per_chunk); + // But don't exceed the requested max_blocks_per_chunk: + blocks_per_chunk + = std::min(blocks_per_chunk, _M_opts.max_blocks_per_chunk); + // Allow space for bitset to track which blocks are used/unused: + blocks_per_chunk *= 1 - 1.0 / (__CHAR_BIT__ * block_size); + // Construct a _Pool for the given block size and initial chunk size: + alloc.construct(p + i, block_size, blocks_per_chunk); + } + return p; + } + + // unsynchronized_pool_resource member functions + + // Constructor + unsynchronized_pool_resource:: + unsynchronized_pool_resource(const pool_options& opts, + memory_resource* upstream) + : _M_impl(opts, upstream), _M_pools(_M_impl._M_alloc_pools()) + { } + + // Destructor + unsynchronized_pool_resource::~unsynchronized_pool_resource() + { release(); } + + // Return all memory to upstream resource. + void + unsynchronized_pool_resource::release() + { + // release pooled memory + if (_M_pools) + { + memory_resource* res = upstream_resource(); + polymorphic_allocator<_Pool> alloc{res}; + for (int i = 0; i < _M_impl._M_npools; ++i) + { + _M_pools[i].release(res); + alloc.destroy(_M_pools + i); + } + alloc.deallocate(_M_pools, _M_impl._M_npools); + _M_pools = nullptr; + } + + // release unpooled memory + _M_impl.release(); + } + + // Find the right pool for a block of size block_size. + auto + unsynchronized_pool_resource::_M_find_pool(size_t block_size) noexcept + { + __pool_resource::_Pool* pool = nullptr; + if (_M_pools) // [[likely]] + { + int index = pool_index(block_size, _M_impl._M_npools); + if (index != -1) + pool = _M_pools + index; + } + return pool; + } + + // Override for memory_resource::do_allocate + void* + unsynchronized_pool_resource::do_allocate(size_t bytes, size_t alignment) + { + const auto block_size = std::max(bytes, alignment); + if (block_size <= _M_impl._M_opts.largest_required_pool_block) + { + // Recreate pools if release() has been called: + if (__builtin_expect(_M_pools == nullptr, false)) + _M_pools = _M_impl._M_alloc_pools(); + if (auto pool = _M_find_pool(block_size)) + return pool->allocate(upstream_resource(), _M_impl._M_opts); + } + return _M_impl.allocate(bytes, alignment); + } + + // Override for memory_resource::do_deallocate + void + unsynchronized_pool_resource:: + do_deallocate(void* p, size_t bytes, size_t alignment) + { + size_t block_size = std::max(bytes, alignment); + if (block_size <= _M_impl._M_opts.largest_required_pool_block) + { + if (auto pool = _M_find_pool(block_size)) + { + pool->deallocate(upstream_resource(), p); + return; + } + } + _M_impl.deallocate(p, bytes, alignment); + } + } // namespace pmr _GLIBCXX_END_NAMESPACE_VERSION } // namespace std - - diff --git a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc new file mode 100644 index 0000000..ce9be2f --- /dev/null +++ b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/allocate.cc @@ -0,0 +1,155 @@ +// Copyright (C) 2018 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +#include <memory_resource> +#include <cstring> +#include <testsuite_allocator.h> +#include <testsuite_hooks.h> + +void +test01() +{ + __gnu_test::memory_resource test_mr; + { + std::pmr::unsynchronized_pool_resource r(&test_mr); + void* p1 = r.allocate(1, 1); + VERIFY( p1 != nullptr ); + auto n = test_mr.number_of_active_allocations(); + VERIFY( n > 0 ); + // Ensure memory region can be written to (without corrupting heap!) + std::memset(p1, 0xff, 1); + void* p2 = r.allocate(1, 1); + VERIFY( p2 != nullptr ); + VERIFY( p2 != p1 ); + VERIFY( test_mr.number_of_active_allocations() == n ); + std::memset(p1, 0xff, 1); + r.deallocate(p1, 1, 1); + // Returning single blocks to the pool doesn't return them upstream: + VERIFY( test_mr.number_of_active_allocations() == n ); + r.deallocate(p2, 1, 1); + VERIFY( test_mr.number_of_active_allocations() == n ); + } + VERIFY( test_mr.number_of_active_allocations() == 0 ); +} + +void +test02() +{ + struct nullable_memory_resource : public std::pmr::memory_resource + { + void* + do_allocate(std::size_t bytes, std::size_t alignment) override + { return upstream->allocate(bytes, alignment); } + + void + do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override + { upstream->deallocate(p, bytes, alignment); } + + bool + do_is_equal(const memory_resource& r) const noexcept override + { return &r == this; } + + std::pmr::memory_resource* upstream = std::pmr::get_default_resource(); + }; + + nullable_memory_resource test_mr; + std::pmr::unsynchronized_pool_resource r(&test_mr); + void* p1 = r.allocate(8, 1); + VERIFY( p1 != nullptr ); + std::memset(p1, 0xff, 8); + test_mr.upstream = nullptr; + void* p2 = r.allocate(8, 1); //should not need to replenish + VERIFY( p2 != nullptr ); + VERIFY( p2 != p1 ); + std::memset(p1, 0xff, 8); + r.deallocate(p1, 8, 1); // should not use upstream + r.deallocate(p2, 8, 1); // should not use upstream + + // Destructor will return memory upstream, so restore the upstream resource: + test_mr.upstream = std::pmr::get_default_resource(); +} + +void +test03() +{ + __gnu_test::memory_resource test_mr; + { + std::pmr::unsynchronized_pool_resource r({10, 16}, &test_mr); + std::size_t largest_pool = r.options().largest_required_pool_block; + void* p1 = r.allocate(2 * largest_pool); + VERIFY( p1 != nullptr ); + const std::size_t n = test_mr.number_of_active_allocations(); + // Allocation of pools + allocation of pmr::vector + oversize allocation: + VERIFY( n >= 1 ); + std::memset(p1, 0xff, 2 * largest_pool); + void* p2 = r.allocate(3 * largest_pool); + VERIFY( p2 != nullptr ); + VERIFY( p2 != p1 ); + VERIFY( test_mr.number_of_active_allocations() == n + 1 ); + std::memset(p2, 0xff, 3 * largest_pool); + r.deallocate(p1, 2 * largest_pool); + VERIFY( test_mr.number_of_active_allocations() == n ); + r.deallocate(p2, 3 * largest_pool); + VERIFY( test_mr.number_of_active_allocations() == n - 1 ); + } + VERIFY( test_mr.number_of_active_allocations() == 0 ); + { + std::pmr::unsynchronized_pool_resource r({16, 16}, &test_mr); + (void) r.allocate(2); + (void) r.allocate(8); + (void) r.allocate(16); + (void) r.allocate(2); + (void) r.allocate(8); + (void) r.allocate(16); + (void) r.allocate(2 * r.options().largest_required_pool_block); + VERIFY( test_mr.number_of_active_allocations() != 0 ); + // Destructor calls release() + } + VERIFY( test_mr.number_of_active_allocations() == 0 ); +} + +void +test04() +{ + std::pmr::unsynchronized_pool_resource r({256, 256}); + // Check alignment + void* p1 = r.allocate(2, 64); + VERIFY( (std::uintptr_t)p1 % 64 == 0 ); + void* p2 = r.allocate(2, 128); + VERIFY( (std::uintptr_t)p2 % 128 == 0 ); + void* p3 = r.allocate(2, 256); + VERIFY( (std::uintptr_t)p3 % 256 == 0 ); + const std::size_t largest_pool = r.options().largest_required_pool_block; + void* p4 = r.allocate(2 * largest_pool, 1024); + VERIFY( (std::uintptr_t)p4 % 1024 == 0 ); + r.deallocate(p1, 2, 64); + r.deallocate(p2, 2, 128); + r.deallocate(p3, 2, 256); + r.deallocate(p4, 2 * largest_pool, 1024); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/is_equal.cc b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/is_equal.cc new file mode 100644 index 0000000..789e7bb --- /dev/null +++ b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/is_equal.cc @@ -0,0 +1,38 @@ +// Copyright (C) 2018 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +#include <memory_resource> +#include <testsuite_hooks.h> + +void +test01() +{ + std::pmr::unsynchronized_pool_resource r1; + VERIFY( r1 == r1 ); + std::pmr::unsynchronized_pool_resource r2; + VERIFY( r1 != r2 ); + VERIFY( r2 != r1 ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/options.cc b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/options.cc new file mode 100644 index 0000000..bfa8a8c --- /dev/null +++ b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/options.cc @@ -0,0 +1,42 @@ +// Copyright (C) 2018 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +#include <memory_resource> +#include <testsuite_hooks.h> + +void +test01() +{ + std::pmr::unsynchronized_pool_resource r0; + const std::pmr::pool_options opts = r0.options(); + VERIFY( opts.max_blocks_per_chunk != 0 ); + VERIFY( opts.largest_required_pool_block != 0 ); + + std::pmr::unsynchronized_pool_resource r1(opts); + auto [max_blocks_per_chunk, largest_required_pool_block ] = r1.options(); + VERIFY( max_blocks_per_chunk == opts.max_blocks_per_chunk ); + VERIFY( largest_required_pool_block == opts.largest_required_pool_block ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/release.cc b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/release.cc new file mode 100644 index 0000000..e28ec47 --- /dev/null +++ b/libstdc++-v3/testsuite/20_util/unsynchronized_pool_resource/release.cc @@ -0,0 +1,113 @@ +// Copyright (C) 2018 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +#include <memory_resource> +#include <testsuite_allocator.h> +#include <testsuite_hooks.h> + +void +test01() +{ + __gnu_test::memory_resource test_mr; + std::pmr::unsynchronized_pool_resource r(&test_mr); + r.release(); + VERIFY( test_mr.number_of_active_allocations() == 0 ); + r.release(); + VERIFY( test_mr.number_of_active_allocations() == 0 ); + (void) r.allocate(1); + VERIFY( test_mr.number_of_active_allocations() != 0 ); + r.release(); + VERIFY( test_mr.number_of_active_allocations() == 0 ); + r.release(); + VERIFY( test_mr.number_of_active_allocations() == 0 ); +} + +void +test02() +{ + struct nullable_memory_resource : public std::pmr::memory_resource + { + void* + do_allocate(std::size_t bytes, std::size_t alignment) override + { return upstream->allocate(bytes, alignment); } + + void + do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override + { upstream->deallocate(p, bytes, alignment); } + + bool + do_is_equal(const memory_resource& r) const noexcept override + { return &r == this; } + + std::pmr::memory_resource* upstream = std::pmr::get_default_resource(); + }; + + nullable_memory_resource test_mr; + std::pmr::unsynchronized_pool_resource r(&test_mr); + r.release(); + test_mr.upstream = nullptr; + r.release(); // should not need to call anything through upstream pointer +} + +void +test03() +{ + __gnu_test::memory_resource test_mr; + { + std::pmr::unsynchronized_pool_resource r(&test_mr); + // Destructor calls release() + } + VERIFY( test_mr.number_of_active_allocations() == 0 ); + { + std::pmr::unsynchronized_pool_resource r(&test_mr); + (void) r.allocate(1); + VERIFY( test_mr.number_of_active_allocations() != 0 ); + // Destructor calls release() + } + VERIFY( test_mr.number_of_active_allocations() == 0 ); + { + std::pmr::unsynchronized_pool_resource r({10, 16}, &test_mr); + (void) r.allocate(2 * r.options().largest_required_pool_block); + VERIFY( test_mr.number_of_active_allocations() != 0 ); + // Destructor calls release() + } + VERIFY( test_mr.number_of_active_allocations() == 0 ); + { + std::pmr::unsynchronized_pool_resource r({16, 16}, &test_mr); + (void) r.allocate(2); + (void) r.allocate(8); + (void) r.allocate(16); + (void) r.allocate(2); + (void) r.allocate(8); + (void) r.allocate(16); + (void) r.allocate(2 * r.options().largest_required_pool_block); + VERIFY( test_mr.number_of_active_allocations() != 0 ); + // Destructor calls release() + } + VERIFY( test_mr.number_of_active_allocations() == 0 ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} |