1 // <memory_resource> implementation -*- C++ -*-
3 // Copyright (C) 2018-2024 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 #include <memory_resource>
26 #include <algorithm> // lower_bound, rotate
28 #include <bit> // has_single_bit, bit_ceil, bit_width
30 #include <bits/move.h> // std::__exchange
31 #if ATOMIC_POINTER_LOCK_FREE != 2
32 # include <bits/std_mutex.h> // std::mutex, std::lock_guard
35 #if __has_cpp_attribute(clang::require_constant_initialization)
36 # define __constinit [[clang::require_constant_initialization]]
39 namespace std
_GLIBCXX_VISIBILITY(default)
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 // This was defined inline in 9.1 and 9.2 so code compiled by those
45 // versions will not use this symbol.
46 memory_resource::~memory_resource() = default;
50 class newdel_res_t final
: public memory_resource
53 do_allocate(size_t __bytes
, size_t __alignment
) override
54 { return ::operator new(__bytes
, std::align_val_t(__alignment
)); }
57 do_deallocate(void* __p
, size_t __bytes
, size_t __alignment
) noexcept
59 { ::operator delete(__p
, __bytes
, std::align_val_t(__alignment
)); }
62 do_is_equal(const memory_resource
& __other
) const noexcept override
63 { return &__other
== this; }
66 class null_res_t final
: public memory_resource
69 do_allocate(size_t, size_t) override
70 { std::__throw_bad_alloc(); }
73 do_deallocate(void*, size_t, size_t) noexcept override
77 do_is_equal(const memory_resource
& __other
) const noexcept override
78 { return &__other
== this; }
87 constexpr constant_init() : obj() { }
90 explicit constexpr constant_init(U arg
) : obj(arg
) { }
92 ~constant_init() { /* do nothing, union member is not destroyed */ }
95 __constinit constant_init
<newdel_res_t
> newdel_res
{};
96 __constinit constant_init
<null_res_t
> null_res
{};
98 #ifndef _GLIBCXX_HAS_GTHREADS
99 # define _GLIBCXX_ATOMIC_MEM_RES_CAN_BE_CONSTANT_INITIALIZED
100 // Single-threaded, no need for synchronization
101 struct atomic_mem_res
104 atomic_mem_res(memory_resource
* r
) : val(r
) { }
106 memory_resource
* val
;
108 memory_resource
* load(std::memory_order
) const
113 memory_resource
* exchange(memory_resource
* r
, std::memory_order
)
115 return std::__exchange(val
, r
);
118 #elif ATOMIC_POINTER_LOCK_FREE == 2
119 using atomic_mem_res
= atomic
<memory_resource
*>;
120 # define _GLIBCXX_ATOMIC_MEM_RES_CAN_BE_CONSTANT_INITIALIZED
122 // Can't use pointer-width atomics, define a type using a mutex instead:
123 struct atomic_mem_res
125 # ifdef __GTHREAD_MUTEX_INIT
126 # define _GLIBCXX_ATOMIC_MEM_RES_CAN_BE_CONSTANT_INITIALIZED
127 // std::mutex has constexpr constructor
130 atomic_mem_res(memory_resource
* r
) : val(r
) { }
133 memory_resource
* val
;
135 memory_resource
* load(std::memory_order
)
137 lock_guard
<mutex
> lock(mx
);
141 memory_resource
* exchange(memory_resource
* r
, std::memory_order
)
143 lock_guard
<mutex
> lock(mx
);
144 return std::__exchange(val
, r
);
149 #ifdef _GLIBCXX_ATOMIC_MEM_RES_CAN_BE_CONSTANT_INITIALIZED
150 __constinit constant_init
<atomic_mem_res
> default_res
{&newdel_res
.obj
};
152 # include "default_resource.h"
157 new_delete_resource() noexcept
158 { return &newdel_res
.obj
; }
161 null_memory_resource() noexcept
162 { return &null_res
.obj
; }
165 set_default_resource(memory_resource
* r
) noexcept
168 r
= new_delete_resource();
169 return default_res
.obj
.exchange(r
, std::memory_order_acq_rel
);
173 get_default_resource() noexcept
174 { return default_res
.obj
.load(std::memory_order_acquire
); }
176 // Member functions for std::pmr::monotonic_buffer_resource
178 // This was defined inline in 9.1 and 9.2 so code compiled by those
179 // versions will not use this symbol.
180 monotonic_buffer_resource::~monotonic_buffer_resource() { release(); }
184 // aligned_size<N> stores the size and alignment of a memory allocation.
185 // The size must be a multiple of N, leaving the low log2(N) bits free
186 // to store the base-2 logarithm of the alignment.
187 // For example, allocate(1024, 32) is stored as 1024 + log2(32) = 1029.
191 // N must be a power of two
192 static_assert( std::__popcount(N
) == 1 );
194 static constexpr size_t _S_align_mask
= N
- 1;
195 static constexpr size_t _S_size_mask
= ~_S_align_mask
;
198 aligned_size(size_t sz
, size_t align
) noexcept
199 : value(sz
| (std::__bit_width(align
) - 1u))
201 __glibcxx_assert(size() == sz
); // sz must be a multiple of N
205 size() const noexcept
206 { return value
& _S_size_mask
; }
209 alignment() const noexcept
210 { return size_t(1) << (value
& _S_align_mask
); }
212 size_t value
; // size | log2(alignment)
215 // Round n up to a multiple of alignment, which must be a power of two.
216 constexpr size_t aligned_ceil(size_t n
, size_t alignment
)
218 return (n
+ alignment
- 1) & ~(alignment
- 1);
223 // Memory allocated by the upstream resource is managed in a linked list
224 // of _Chunk objects. A _Chunk object recording the size and alignment of
225 // the allocated block and a pointer to the previous chunk is placed
226 // at end of the block.
227 class monotonic_buffer_resource::_Chunk
230 // Return the address and size of a block of memory allocated from __r,
231 // of at least __size bytes and aligned to __align.
232 // Add a new _Chunk to the front of the linked list at __head.
233 static pair
<void*, size_t>
234 allocate(memory_resource
* __r
, size_t __size
, size_t __align
,
237 const size_t __orig_size
= __size
;
239 // Add space for the _Chunk object and round up to 64 bytes.
240 __size
= aligned_ceil(__size
+ sizeof(_Chunk
), 64);
242 // Check for unsigned wraparound
243 if (__size
< __orig_size
) [[unlikely
]]
245 // monotonic_buffer_resource::do_allocate is not allowed to throw.
246 // If the required size is too large for size_t then ask the
247 // upstream resource for an impossibly large size and alignment.
249 __align
= ~(size_t(-1) >> 1);
252 void* __p
= __r
->allocate(__size
, __align
);
254 // Add a chunk defined by (__p, __size, __align) to linked list __head.
255 // We know the end of the buffer is suitably-aligned for a _Chunk
256 // because the caller ensured __align is at least alignof(max_align_t).
257 void* const __back
= (char*)__p
+ __size
- sizeof(_Chunk
);
258 __head
= ::new(__back
) _Chunk(__size
, __align
, __head
);
259 return { __p
, __size
- sizeof(_Chunk
) };
262 // Return every chunk in linked list __head to resource __r.
264 release(_Chunk
*& __head
, memory_resource
* __r
) noexcept
266 _Chunk
* __next
= __head
;
270 _Chunk
* __ch
= __next
;
271 __next
= __ch
->_M_next
;
272 size_t __size
= __ch
->_M_size
.size();
273 size_t __align
= __ch
->_M_size
.alignment();
274 void* __start
= (char*)(__ch
+ 1) - __size
;
275 __r
->deallocate(__start
, __size
, __align
);
280 _Chunk(size_t __size
, size_t __align
, _Chunk
* __next
) noexcept
281 : _M_size(__size
, __align
), _M_next(__next
)
284 aligned_size
<64> _M_size
;
289 monotonic_buffer_resource::_M_new_buffer(size_t bytes
, size_t alignment
)
291 const size_t n
= std::max(bytes
, _M_next_bufsiz
);
292 const size_t m
= aligned_ceil(alignment
, alignof(std::max_align_t
));
293 auto [p
, size
] = _Chunk::allocate(_M_upstream
, n
, m
, _M_head
);
296 _M_next_bufsiz
*= _S_growth_factor
;
300 monotonic_buffer_resource::_M_release_buffers() noexcept
302 _Chunk::release(_M_head
, _M_upstream
);
305 // Helper types for synchronized_pool_resource & unsynchronized_pool_resource
309 // Simple bitset with runtime size.
310 // Tracks which blocks in a pool chunk are used/unused.
313 using word
= uint64_t;
314 using size_type
// unsigned integer type with no more than 32 bits
315 = conditional_t
<numeric_limits
<size_t>::digits
<= 32, size_t, uint32_t>;
317 static constexpr unsigned bits_per_word
= numeric_limits
<word
>::digits
;
319 // The bitset does not own p
320 bitset(void* p
, size_type num_blocks
)
321 : _M_words(static_cast<word
*>(p
)), _M_size(num_blocks
),
324 const size_type last_word
= num_blocks
/ bits_per_word
;
325 __builtin_memset(_M_words
, 0, last_word
* sizeof(*_M_words
));
326 // Set bits beyond _M_size, so they are not treated as free blocks:
327 if (const size_type extra_bits
= num_blocks
% bits_per_word
)
328 _M_words
[last_word
] = word(-1) << extra_bits
;
329 __glibcxx_assert( empty() );
330 __glibcxx_assert( free() == num_blocks
);
337 size_type
size() const noexcept
{ return _M_size
; }
339 // Number of free blocks (unset bits)
340 size_type
free() const noexcept
343 for (size_type i
= _M_next_word
; i
< nwords(); ++i
)
344 n
+= (bits_per_word
- std::__popcount(_M_words
[i
]));
348 // True if there are no free blocks (all bits are set)
349 bool full() const noexcept
351 if (_M_next_word
>= nwords())
353 // For a bitset with size() > (max_blocks_per_chunk() - 64) we will
354 // have nwords() == (max_word_index() + 1) and so _M_next_word will
355 // never be equal to nwords().
356 // In that case, check if the last word is full:
357 if (_M_next_word
== max_word_index())
358 return _M_words
[_M_next_word
] == word(-1);
362 // True if size() != 0 and all blocks are free (no bits are set).
363 bool empty() const noexcept
367 if (_M_next_word
!= 0)
369 for (size_type i
= 0; i
< nwords() - 1; ++i
)
370 if (_M_words
[i
] != 0)
372 word last
= _M_words
[nwords() - 1];
373 if (const size_type extra_bits
= size() % bits_per_word
)
374 last
<<= (bits_per_word
- extra_bits
);
378 void reset() noexcept
381 _M_size
= _M_next_word
= 0;
384 bool operator[](size_type n
) const noexcept
386 __glibcxx_assert( n
< _M_size
);
387 const size_type wd
= n
/ bits_per_word
;
388 const word bit
= word(1) << (n
% bits_per_word
);
389 return _M_words
[wd
] & bit
;
392 size_type
get_first_unset() noexcept
394 const size_type wd
= _M_next_word
;
397 const size_type n
= std::__countr_one(_M_words
[wd
]);
398 if (n
< bits_per_word
)
400 const word bit
= word(1) << n
;
403 return (wd
* bits_per_word
) + n
;
406 return size_type(-1);
409 void set(size_type n
) noexcept
411 __glibcxx_assert( n
< _M_size
);
412 const size_type wd
= n
/ bits_per_word
;
413 const word bit
= word(1) << (n
% bits_per_word
);
415 if (wd
== _M_next_word
)
419 void clear(size_type n
) noexcept
421 __glibcxx_assert( n
< _M_size
);
422 const size_type wd
= n
/ bits_per_word
;
423 const word bit
= word(1) << (n
% bits_per_word
);
424 _M_words
[wd
] &= ~bit
;
425 if (wd
< _M_next_word
)
429 // Update _M_next_word to refer to the next word with an unset bit.
430 // The size of the _M_next_word bit-field means it cannot represent
431 // the maximum possible nwords() value. To avoid wraparound to zero
432 // this function saturates _M_next_word at max_word_index().
433 void update_next_word() noexcept
435 size_type next
= _M_next_word
;
436 while (_M_words
[next
] == word(-1) && ++next
< nwords())
438 _M_next_word
= std::min(next
, max_word_index());
441 void swap(bitset
& b
) noexcept
443 std::swap(_M_words
, b
._M_words
);
444 size_type tmp
= _M_size
;
448 _M_next_word
= b
._M_next_word
;
449 b
._M_next_word
= tmp
;
452 size_type
nwords() const noexcept
453 { return (_M_size
+ bits_per_word
- 1) / bits_per_word
; }
455 // Maximum value that can be stored in bitset::_M_size member (approx 500k)
456 static constexpr size_type
max_blocks_per_chunk() noexcept
457 { return (size_type(1) << _S_size_digits
) - 1; }
459 // Maximum value that can be stored in bitset::_M_next_word member (8191).
460 static constexpr size_type
max_word_index() noexcept
461 { return (max_blocks_per_chunk() + bits_per_word
- 1) / bits_per_word
; }
463 word
* data() const noexcept
{ return _M_words
; }
466 static constexpr unsigned _S_size_digits
467 = (numeric_limits
<size_type
>::digits
468 + std::__bit_width(bits_per_word
) - 1) / 2;
470 word
* _M_words
= nullptr;
471 // Number of blocks represented by the bitset:
472 size_type _M_size
: _S_size_digits
;
473 // Index of the first word with unset bits:
474 size_type _M_next_word
: numeric_limits
<size_type
>::digits
- _S_size_digits
;
477 // A "chunk" belonging to a pool.
478 // A chunk contains many blocks of the same size.
479 // Derived from bitset to reuse its tail-padding.
480 struct chunk
: bitset
484 // p points to the start of a chunk of size bytes in length.
485 // The chunk has space for n blocks, followed by a bitset of size n
486 // that begins at address words.
487 // This object does not own p or words, the caller will free it.
488 chunk(void* p
, uint32_t bytes
, void* words
, size_t n
)
491 _M_p(static_cast<std::byte
*>(p
))
492 { __glibcxx_assert(bytes
<= chunk::max_bytes_per_chunk()); }
494 chunk(chunk
&& c
) noexcept
495 : bitset(std::move(c
)), _M_bytes(c
._M_bytes
), _M_p(c
._M_p
)
502 chunk
& operator=(chunk
&& c
) noexcept
508 // Allocated size of chunk:
509 bitset::size_type _M_bytes
= 0;
510 // Start of allocated chunk:
511 std::byte
* _M_p
= nullptr;
513 // True if there are free blocks in this chunk
515 // Number of blocks in this chunk
518 static constexpr uint32_t max_bytes_per_chunk() noexcept
519 { return numeric_limits
<decltype(_M_bytes
)>::max(); }
521 // Determine if block with address p and size block_size
522 // is contained within this chunk.
523 bool owns(void* p
, size_t block_size
)
525 std::less_equal
<uintptr_t> less_equal
;
526 return less_equal(reinterpret_cast<uintptr_t>(_M_p
),
527 reinterpret_cast<uintptr_t>(p
))
528 && less_equal(reinterpret_cast<uintptr_t>(p
) + block_size
,
529 reinterpret_cast<uintptr_t>(bitset::data()));
532 // Allocate next available block of block_size bytes from this chunk.
533 void* reserve(size_t block_size
) noexcept
535 const size_type n
= get_first_unset();
536 if (n
== size_type(-1))
538 return _M_p
+ (n
* block_size
);
541 // Deallocate a single block of block_size bytes
542 void release(void* vp
, size_t block_size
)
544 __glibcxx_assert( owns(vp
, block_size
) );
545 const size_t offset
= static_cast<std::byte
*>(vp
) - _M_p
;
546 // Pointer is correctly aligned for a block in this chunk:
547 __glibcxx_assert( (offset
% block_size
) == 0 );
548 // Block has been allocated:
549 __glibcxx_assert( (*this)[offset
/ block_size
] == true );
550 bitset::clear(offset
/ block_size
);
553 // Deallocate a single block if it belongs to this chunk.
554 bool try_release(void* p
, size_t block_size
)
556 if (!owns(p
, block_size
))
558 release(p
, block_size
);
562 void swap(chunk
& c
) noexcept
564 std::swap(_M_bytes
, c
._M_bytes
);
565 std::swap(_M_p
, c
._M_p
);
569 bool operator<(const chunk
& c
) const noexcept
570 { return std::less
<const void*>{}(_M_p
, c
._M_p
); }
572 friend void swap(chunk
& l
, chunk
& r
) { l
.swap(r
); }
574 friend bool operator<(const void* p
, const chunk
& c
) noexcept
575 { return std::less
<const void*>{}(p
, c
._M_p
); }
578 // For 64-bit pointers this is the size of three pointers i.e. 24 bytes.
579 // For 32-bit and 20-bit pointers it's four pointers (16 bytes).
580 // For 16-bit pointers it's five pointers (10 bytes).
581 // TODO pad 64-bit to 4*sizeof(void*) to avoid splitting across cache lines?
582 static_assert(sizeof(chunk
)
583 == 2 * sizeof(bitset::size_type
) + 2 * sizeof(void*));
585 // An oversized allocation that doesn't fit in a pool.
588 // The minimum size of a big block.
589 // All big_block allocations will be a multiple of this value.
590 // Use bit_ceil to get a power of two even for e.g. 20-bit size_t.
591 static constexpr size_t min
= __bit_ceil(numeric_limits
<size_t>::digits
);
594 big_block(size_t bytes
, size_t alignment
)
595 : _M_size(alloc_size(bytes
), alignment
)
597 // Check for unsigned wraparound
598 if (size() < bytes
) [[unlikely
]]
600 // (sync|unsync)_pool_resource::do_allocate is not allowed to throw.
601 // If the required size is too large for size_t then ask the
602 // upstream resource for an impossibly large size and alignment.
607 void* pointer
= nullptr;
608 aligned_size
<min
> _M_size
;
610 constexpr size_t size() const noexcept
612 if (_M_size
.value
== size_t(-1)) [[unlikely
]]
614 return _M_size
.size();
617 size_t align() const noexcept
618 { return _M_size
.alignment(); }
620 // Calculate size to be allocated instead of requested number of bytes.
621 // The requested value will be rounded up to a multiple of big_block::min,
622 // so the low bits are all zero and can be used to hold the alignment.
623 static constexpr size_t alloc_size(size_t bytes
) noexcept
624 { return aligned_ceil(bytes
, min
); }
626 friend bool operator<(void* p
, const big_block
& b
) noexcept
627 { return less
<void*>{}(p
, b
.pointer
); }
629 friend bool operator<(const big_block
& b
, void* p
) noexcept
630 { return less
<void*>{}(b
.pointer
, p
); }
633 static_assert(sizeof(big_block
) == (2 * sizeof(void*)));
637 // A pool that serves blocks of a particular size.
638 // Each pool manages a number of chunks.
639 // When a pool is full it is replenished by allocating another chunk.
640 struct __pool_resource::_Pool
642 // Smallest supported block size
643 static constexpr unsigned _S_min_block
644 = std::max(sizeof(void*), alignof(bitset::word
));
646 _Pool(size_t __block_size
, size_t __blocks_per_chunk
)
648 _M_block_sz(__block_size
),
649 _M_blocks_per_chunk(__blocks_per_chunk
)
652 // Must call release(r) before destruction!
653 ~_Pool() { __glibcxx_assert(_M_chunks
.empty()); }
655 _Pool(_Pool
&&) noexcept
= default;
656 _Pool
& operator=(_Pool
&&) noexcept
= default;
658 // Size of blocks in this pool
659 size_t block_size() const noexcept
660 { return _M_block_sz
; }
662 // Allocate a block if the pool is not full, otherwise return null.
663 void* try_allocate() noexcept
665 const size_t blocksz
= block_size();
666 if (!_M_chunks
.empty())
668 auto& last
= _M_chunks
.back();
669 if (void* p
= last
.reserve(blocksz
))
671 // TODO last is full, so move another chunk to the back instead?
672 for (auto it
= _M_chunks
.begin(); it
!= &last
; ++it
)
673 if (void* p
= it
->reserve(blocksz
))
679 // Allocate a block from the pool, replenishing from upstream if needed.
680 void* allocate(memory_resource
* r
, const pool_options
& opts
)
682 if (void* p
= try_allocate())
685 return _M_chunks
.back().reserve(block_size());
688 // Return a block to the pool.
689 bool deallocate(memory_resource
*, void* p
)
691 const size_t blocksz
= block_size();
692 if (__builtin_expect(!_M_chunks
.empty(), true))
694 auto& last
= _M_chunks
.back();
695 if (last
.try_release(p
, blocksz
))
697 auto it
= std::upper_bound(_M_chunks
.begin(), &last
, p
);
698 if (it
!= _M_chunks
.begin())
701 if (it
->try_release(p
, blocksz
))
702 // If chunk is empty could return to upstream, but we don't
703 // currently do that. Pools only increase in size.
710 void replenish(memory_resource
* __r
, const pool_options
& __opts
)
712 using word
= chunk::word
;
713 const size_t __blocks
= _M_blocks_per_chunk
;
714 const auto __bits
= chunk::bits_per_word
;
715 const size_t __words
= (__blocks
+ __bits
- 1) / __bits
;
716 const size_t __block_size
= block_size();
717 size_t __bytes
= __blocks
* __block_size
+ __words
* sizeof(word
);
718 size_t __alignment
= std::__bit_ceil(__block_size
);
719 void* __p
= __r
->allocate(__bytes
, __alignment
);
722 size_t __n
= __blocks
* __block_size
;
723 void* __pwords
= static_cast<char*>(__p
) + __n
;
724 _M_chunks
.insert(chunk(__p
, __bytes
, __pwords
, __blocks
), __r
);
728 __r
->deallocate(__p
, __bytes
, __alignment
);
730 if (_M_blocks_per_chunk
< __opts
.max_blocks_per_chunk
)
732 const size_t max_blocks
733 = (chunk::max_bytes_per_chunk() - sizeof(word
))
734 / (__block_size
+ 0.125);
735 _M_blocks_per_chunk
= std::min({
737 __opts
.max_blocks_per_chunk
,
738 size_t(_M_blocks_per_chunk
* 2)
743 void release(memory_resource
* __r
)
745 const size_t __alignment
= std::__bit_ceil(block_size());
746 for (auto& __c
: _M_chunks
)
748 __r
->deallocate(__c
._M_p
, __c
._M_bytes
, __alignment
);
749 _M_chunks
.clear(__r
);
752 // A "resourceless vector" instead of pmr::vector, to save space.
753 // All resize operations need to be passed a memory resource, which
754 // obviously needs to be the same one every time.
755 // Chunks are kept sorted by address of their first block, except for
756 // the most recently-allocated Chunk which is at the end of the vector.
759 using value_type
= chunk
;
760 using size_type
= unsigned;
761 using iterator
= value_type
*;
763 // A vector owns its data pointer but not memory held by its elements.
764 chunk
* data
= nullptr;
766 size_type capacity
= 0;
770 vector(size_type __n
, memory_resource
* __r
)
771 : data(polymorphic_allocator
<value_type
>(__r
).allocate(__n
)),
775 // Must call clear(r) before destruction!
776 ~vector() { __glibcxx_assert(data
== nullptr); }
778 vector(vector
&& __rval
) noexcept
779 : data(__rval
.data
), size(__rval
.size
), capacity(__rval
.capacity
)
781 __rval
.data
= nullptr;
782 __rval
.capacity
= __rval
.size
= 0;
785 vector
& operator=(vector
&& __rval
) noexcept
787 __glibcxx_assert(data
== nullptr);
790 capacity
= __rval
.capacity
;
791 __rval
.data
= nullptr;
792 __rval
.capacity
= __rval
.size
= 0;
796 // void resize(size_type __n, memory_resource* __r);
797 // void reserve(size_type __n, memory_resource* __r);
799 void clear(memory_resource
* __r
)
803 // Chunks must be individually freed before clearing the vector.
804 std::destroy(begin(), end());
805 polymorphic_allocator
<value_type
>(__r
).deallocate(data
, capacity
);
810 // Sort existing elements then insert new one at the end.
811 iterator
insert(chunk
&& c
, memory_resource
* r
)
817 auto mid
= end() - 1;
818 std::rotate(std::lower_bound(begin(), mid
, *mid
), mid
, end());
823 polymorphic_allocator
<value_type
> __alloc(r
);
824 auto __mid
= std::lower_bound(begin(), end() - 1, back());
825 auto __p
= __alloc
.allocate(capacity
* 1.5);
826 // move [begin,__mid) to new storage
827 auto __p2
= std::move(begin(), __mid
, __p
);
828 // move end-1 to new storage
829 *__p2
= std::move(back());
830 // move [__mid,end-1) to new storage
831 std::move(__mid
, end() - 1, ++__p2
);
832 std::destroy(begin(), end());
833 __alloc
.deallocate(data
, capacity
);
839 polymorphic_allocator
<value_type
> __alloc(r
);
840 data
= __alloc
.allocate(capacity
= 8);
842 auto back
= ::new (data
+ size
) chunk(std::move(c
));
843 __glibcxx_assert(std::is_sorted(begin(), back
));
848 iterator
begin() const { return data
; }
849 iterator
end() const { return data
+ size
; }
851 bool empty() const noexcept
{ return size
== 0; }
853 value_type
& back() { return data
[size
- 1]; }
857 unsigned _M_block_sz
; // size of blocks allocated from this pool
858 unsigned _M_blocks_per_chunk
; // number of blocks to allocate next
861 // An oversized allocation that doesn't fit in a pool.
862 struct __pool_resource::_BigBlock
: big_block
864 using big_block::big_block
;
869 constexpr size_t pool_sizes
[] = {
876 #if __SIZE_WIDTH__ > 16
877 // Use bigger pools if size_t has at least 20 bits.
880 #if __INT_WIDTH__ >= 32
881 // Use even bigger pools if int has at least 32 bits.
884 1<<20, 1<<21, 1<<22 // 4MB should be enough for anybody
890 munge_options(pool_options opts
)
892 // The values in the returned struct may differ from those supplied
893 // to the pool resource constructor in that values of zero will be
894 // replaced with implementation-defined defaults, and sizes may be
895 // rounded to unspecified granularity.
897 // max_blocks_per_chunk sets the absolute maximum for the pool resource.
898 // Each pool might have a smaller maximum, because pools for very large
899 // objects might impose smaller limit.
900 if (opts
.max_blocks_per_chunk
== 0)
902 // Pick a default that depends on the number of bits in size_t.
903 opts
.max_blocks_per_chunk
= __SIZE_WIDTH__
<< 8;
907 // Round to preferred granularity.
908 if (opts
.max_blocks_per_chunk
< size_t(-4))
911 opts
.max_blocks_per_chunk
912 = aligned_ceil(opts
.max_blocks_per_chunk
, 4);
917 opts
.max_blocks_per_chunk
&= ~size_t(3);
921 if (opts
.max_blocks_per_chunk
> chunk::max_blocks_per_chunk())
923 opts
.max_blocks_per_chunk
= chunk::max_blocks_per_chunk();
926 // largest_required_pool_block specifies the largest block size that will
927 // be allocated from a pool. Larger allocations will come directly from
928 // the upstream resource and so will not be pooled.
929 if (opts
.largest_required_pool_block
== 0)
931 // Pick a sensible default that depends on the number of bits in size_t
932 // (pools with larger block sizes must be explicitly requested by
933 // using a non-zero value for largest_required_pool_block).
934 opts
.largest_required_pool_block
= __SIZE_WIDTH__
<< 6;
938 // Round to preferred granularity
939 static_assert(std::__has_single_bit(pool_sizes
[0]));
940 opts
.largest_required_pool_block
941 = aligned_ceil(opts
.largest_required_pool_block
, pool_sizes
[0]);
944 if (opts
.largest_required_pool_block
< big_block::min
)
946 opts
.largest_required_pool_block
= big_block::min
;
948 else if (opts
.largest_required_pool_block
> std::end(pool_sizes
)[-1])
950 // Setting _M_opts to the largest pool allows users to query it:
951 opts
.largest_required_pool_block
= std::end(pool_sizes
)[-1];
957 pool_index(size_t block_size
, int npools
)
959 auto p
= std::lower_bound(pool_sizes
, pool_sizes
+ npools
, block_size
);
960 int n
= p
- pool_sizes
;
967 select_num_pools(const pool_options
& opts
)
969 auto p
= std::lower_bound(std::begin(pool_sizes
), std::end(pool_sizes
),
970 opts
.largest_required_pool_block
);
971 const int n
= p
- std::begin(pool_sizes
);
972 if (p
== std::end(pool_sizes
))
977 #ifdef _GLIBCXX_HAS_GTHREADS
978 using shared_lock
= std::shared_lock
<shared_mutex
>;
979 using exclusive_lock
= lock_guard
<shared_mutex
>;
985 __pool_resource(const pool_options
& opts
, memory_resource
* upstream
)
986 : _M_opts(munge_options(opts
)), _M_unpooled(upstream
),
987 _M_npools(select_num_pools(_M_opts
))
990 __pool_resource::~__pool_resource() { release(); }
993 __pool_resource::release() noexcept
995 memory_resource
* res
= resource();
996 // deallocate oversize allocations
997 for (auto& b
: _M_unpooled
)
998 res
->deallocate(b
.pointer
, b
.size(), b
.align());
999 pmr::vector
<_BigBlock
>{res
}.swap(_M_unpooled
);
1003 __pool_resource::allocate(size_t bytes
, size_t alignment
)
1005 auto& b
= _M_unpooled
.emplace_back(bytes
, alignment
);
1007 // N.B. need to allocate b.size(), which might be larger than bytes.
1008 // Also use b.align() instead of alignment parameter, which will be
1009 // an impossibly large value if (bytes+bookkeeping) > SIZE_MAX.
1010 void* p
= resource()->allocate(b
.size(), b
.align());
1012 if (_M_unpooled
.size() > 1)
1014 const auto mid
= _M_unpooled
.end() - 1;
1015 // move to right position in vector
1016 std::rotate(std::lower_bound(_M_unpooled
.begin(), mid
, p
),
1017 mid
, _M_unpooled
.end());
1021 _M_unpooled
.pop_back();
1022 __throw_exception_again
;
1027 __pool_resource::deallocate(void* p
, size_t bytes
[[maybe_unused
]],
1028 size_t alignment
[[maybe_unused
]])
1031 = std::lower_bound(_M_unpooled
.begin(), _M_unpooled
.end(), p
);
1032 __glibcxx_assert(it
!= _M_unpooled
.end() && it
->pointer
== p
);
1033 if (it
!= _M_unpooled
.end() && it
->pointer
== p
) // [[likely]]
1036 __glibcxx_assert(b
.size() == b
.alloc_size(bytes
));
1037 __glibcxx_assert(b
.align() == alignment
);
1038 _M_unpooled
.erase(it
);
1039 // N.B. need to deallocate b.size(), which might be larger than bytes.
1040 resource()->deallocate(p
, b
.size(), b
.align());
1044 // Create array of pools, allocated from upstream resource.
1046 __pool_resource::_M_alloc_pools()
1049 polymorphic_allocator
<_Pool
> alloc
{resource()};
1050 _Pool
* p
= alloc
.allocate(_M_npools
);
1051 for (int i
= 0; i
< _M_npools
; ++i
)
1053 // For last pool use largest_required_pool_block
1054 const size_t block_size
= (i
+1 == _M_npools
)
1055 ? _M_opts
.largest_required_pool_block
1058 // Decide on initial number of blocks per chunk.
1059 // At least 16 blocks per chunk seems reasonable,
1060 // more for smaller blocks:
1061 size_t blocks_per_chunk
= 1024 / block_size
;
1062 blocks_per_chunk
= std::max(size_t(16), blocks_per_chunk
);
1063 // But don't exceed the requested max_blocks_per_chunk:
1065 = std::min(blocks_per_chunk
, _M_opts
.max_blocks_per_chunk
);
1066 // Allow space for bitset to track which blocks are used/unused:
1067 blocks_per_chunk
*= 1 - 1.0 / (__CHAR_BIT__
* block_size
);
1068 // Construct a _Pool for the given block size and initial chunk size:
1069 alloc
.construct(p
+ i
, block_size
, blocks_per_chunk
);
1074 #ifdef _GLIBCXX_HAS_GTHREADS
1075 // synchronized_pool_resource members.
1077 /* Notes on implementation and thread safety:
1079 * Each synchronized_pool_resource manages an linked list of N+1 _TPools
1080 * objects, where N is the number of threads using the pool resource.
1081 * Each _TPools object has its own set of pools, with their own chunks.
1082 * The first element of the list, _M_tpools[0], can be used by any thread.
1083 * The rest of the list contains a _TPools object for each thread,
1084 * accessed via the thread-specific key _M_key (and referred to for
1085 * exposition as _M_tpools[_M_key]).
1086 * The first element, _M_tpools[0], contains "orphaned chunks" which were
1087 * allocated by a thread which has since exited, and so there is no
1088 * _M_tpools[_M_key] for that thread. Orphaned chunks are never reused,
1089 * they're only held in _M_tpools[0] so they can be deallocated.
1090 * A thread can access its own thread-specific set of pools via _M_key
1091 * while holding a shared lock on _M_mx. Accessing _M_impl._M_unpooled
1092 * or _M_tpools[0] or any other thread's _M_tpools[_M_key] requires an
1094 * The upstream_resource() pointer can be obtained without a lock, but
1095 * any dereference of that pointer requires an exclusive lock.
1096 * The _M_impl._M_opts and _M_impl._M_npools members are immutable,
1097 * and can safely be accessed concurrently.
1099 * In a single-threaded program (i.e. __gthread_active_p() == false)
1100 * the pool resource only needs one set of pools and never has orphaned
1101 * chunks, so just uses _M_tpools[0] directly, and _M_tpools->next is null.
1105 static void destroy_TPools(void*);
1108 struct synchronized_pool_resource::_TPools
1110 // Exclusive lock must be held in the thread where this constructor runs.
1112 _TPools(synchronized_pool_resource
& owner
, exclusive_lock
&)
1113 : owner(owner
), pools(owner
._M_impl
._M_alloc_pools())
1115 // __builtin_printf("%p constructing\n", this);
1116 __glibcxx_assert(pools
);
1119 // Exclusive lock must be held in the thread where this destructor runs.
1122 __glibcxx_assert(pools
);
1125 memory_resource
* r
= owner
.upstream_resource();
1126 for (int i
= 0; i
< owner
._M_impl
._M_npools
; ++i
)
1127 pools
[i
].release(r
);
1128 std::destroy_n(pools
, owner
._M_impl
._M_npools
);
1129 polymorphic_allocator
<__pool_resource::_Pool
> a(r
);
1130 a
.deallocate(pools
, owner
._M_impl
._M_npools
);
1138 // Exclusive lock must be held in the thread where this function runs.
1139 void move_nonempty_chunks()
1141 __glibcxx_assert(pools
);
1142 __glibcxx_assert(__gthread_active_p());
1145 memory_resource
* const r
= owner
.upstream_resource();
1146 auto* const shared
= owner
._M_tpools
->pools
;
1147 // move all non-empty chunks to the shared _TPools
1148 for (int i
= 0; i
< owner
._M_impl
._M_npools
; ++i
)
1149 for (auto& c
: pools
[i
]._M_chunks
)
1151 shared
[i
]._M_chunks
.insert(std::move(c
), r
);
1154 synchronized_pool_resource
& owner
;
1155 __pool_resource::_Pool
* pools
= nullptr;
1156 _TPools
* prev
= nullptr;
1157 _TPools
* next
= nullptr;
1159 static void destroy(_TPools
* p
)
1161 exclusive_lock
l(p
->owner
._M_mx
);
1162 // __glibcxx_assert(p != p->owner._M_tpools);
1163 p
->move_nonempty_chunks();
1164 polymorphic_allocator
<_TPools
> a(p
->owner
.upstream_resource());
1170 // Called when a thread exits
1172 static void destroy_TPools(void* p
)
1174 using _TPools
= synchronized_pool_resource::_TPools
;
1175 _TPools::destroy(static_cast<_TPools
*>(p
));
1180 synchronized_pool_resource::
1181 synchronized_pool_resource(const pool_options
& opts
,
1182 memory_resource
* upstream
)
1183 : _M_impl(opts
, upstream
)
1185 if (__gthread_active_p())
1186 if (int err
= __gthread_key_create(&_M_key
, destroy_TPools
))
1187 __throw_system_error(err
);
1188 exclusive_lock
l(_M_mx
);
1189 _M_tpools
= _M_alloc_shared_tpools(l
);
1193 synchronized_pool_resource::~synchronized_pool_resource()
1196 if (__gthread_active_p())
1197 __gthread_key_delete(_M_key
); // does not run destroy_TPools
1201 synchronized_pool_resource::release()
1203 exclusive_lock
l(_M_mx
);
1206 if (__gthread_active_p())
1208 __gthread_key_delete(_M_key
); // does not run destroy_TPools
1209 __gthread_key_create(&_M_key
, destroy_TPools
);
1211 polymorphic_allocator
<_TPools
> a(upstream_resource());
1212 // destroy+deallocate each _TPools
1215 _TPools
* p
= _M_tpools
;
1216 _M_tpools
= _M_tpools
->next
;
1222 // release unpooled memory
1226 // Caller must hold shared or exclusive lock to ensure the pointer
1227 // isn't invalidated before it can be used.
1229 synchronized_pool_resource::_M_thread_specific_pools() noexcept
1231 __pool_resource::_Pool
* pools
= nullptr;
1232 __glibcxx_assert(__gthread_active_p());
1233 if (auto tp
= static_cast<_TPools
*>(__gthread_getspecific(_M_key
)))
1236 // __glibcxx_assert(tp->pools);
1241 // Override for memory_resource::do_allocate
1243 synchronized_pool_resource::
1244 do_allocate(size_t bytes
, size_t alignment
)
1246 const auto block_size
= std::max(bytes
, alignment
);
1247 const pool_options opts
= _M_impl
._M_opts
;
1248 if (block_size
<= opts
.largest_required_pool_block
)
1250 const ptrdiff_t index
= pool_index(block_size
, _M_impl
._M_npools
);
1251 if (__gthread_active_p())
1253 // Try to allocate from the thread-specific pool.
1254 shared_lock
l(_M_mx
);
1255 if (auto pools
= _M_thread_specific_pools()) // [[likely]]
1257 // Need exclusive lock to replenish so use try_allocate:
1258 if (void* p
= pools
[index
].try_allocate())
1260 // Need to take exclusive lock and replenish pool.
1262 // Need to allocate or replenish thread-specific pools using
1263 // upstream resource, so need to hold exclusive lock.
1265 else // single-threaded
1267 if (!_M_tpools
) // [[unlikely]]
1269 exclusive_lock
dummy(_M_mx
);
1270 _M_tpools
= _M_alloc_shared_tpools(dummy
);
1272 return _M_tpools
->pools
[index
].allocate(upstream_resource(), opts
);
1275 // N.B. Another thread could call release() now lock is not held.
1276 exclusive_lock
excl(_M_mx
);
1277 if (!_M_tpools
) // [[unlikely]]
1278 _M_tpools
= _M_alloc_shared_tpools(excl
);
1279 auto pools
= _M_thread_specific_pools();
1281 pools
= _M_alloc_tpools(excl
)->pools
;
1282 return pools
[index
].allocate(upstream_resource(), opts
);
1284 exclusive_lock
l(_M_mx
);
1285 return _M_impl
.allocate(bytes
, alignment
); // unpooled allocation
1288 // Override for memory_resource::do_deallocate
1290 synchronized_pool_resource::
1291 do_deallocate(void* p
, size_t bytes
, size_t alignment
)
1293 size_t block_size
= std::max(bytes
, alignment
);
1294 if (block_size
<= _M_impl
._M_opts
.largest_required_pool_block
)
1296 const ptrdiff_t index
= pool_index(block_size
, _M_impl
._M_npools
);
1297 __glibcxx_assert(index
!= -1);
1298 if (__gthread_active_p())
1300 shared_lock
l(_M_mx
);
1301 if (auto pools
= _M_thread_specific_pools())
1303 // No need to lock here, no other thread is accessing this pool.
1304 if (pools
[index
].deallocate(upstream_resource(), p
))
1307 // Block might have come from a different thread's pool,
1308 // take exclusive lock and check every pool.
1310 else // single-threaded
1312 __glibcxx_assert(_M_tpools
!= nullptr);
1313 if (_M_tpools
) // [[likely]]
1314 _M_tpools
->pools
[index
].deallocate(upstream_resource(), p
);
1318 // TODO store {p, bytes, alignment} somewhere and defer returning
1319 // the block to the correct thread-specific pool until we next
1320 // take the exclusive lock.
1322 exclusive_lock
excl(_M_mx
);
1323 auto my_pools
= _M_thread_specific_pools();
1324 for (_TPools
* t
= _M_tpools
; t
!= nullptr; t
= t
->next
)
1326 if (t
->pools
!= my_pools
)
1327 if (t
->pools
) // [[likely]]
1329 if (t
->pools
[index
].deallocate(upstream_resource(), p
))
1333 // Not necessarily an error to reach here, release() could have been
1334 // called on another thread between releasing the shared lock and
1335 // acquiring the exclusive lock.
1338 exclusive_lock
l(_M_mx
);
1339 _M_impl
.deallocate(p
, bytes
, alignment
);
1342 // Allocate a thread-specific _TPools object and add it to the linked list.
1344 synchronized_pool_resource::_M_alloc_tpools(exclusive_lock
& l
)
1347 __glibcxx_assert(_M_tpools
!= nullptr);
1348 __glibcxx_assert(__gthread_active_p());
1349 // dump_list(_M_tpools);
1350 polymorphic_allocator
<_TPools
> a(upstream_resource());
1351 _TPools
* p
= a
.allocate(1);
1352 bool constructed
= false;
1355 a
.construct(p
, *this, l
);
1357 // __glibcxx_assert(__gthread_getspecific(_M_key) == nullptr);
1358 if (int err
= __gthread_setspecific(_M_key
, p
))
1359 __throw_system_error(err
);
1366 __throw_exception_again
;
1368 p
->prev
= _M_tpools
;
1369 p
->next
= _M_tpools
->next
;
1370 _M_tpools
->next
= p
;
1376 // Allocate the shared _TPools object, _M_tpools[0]
1378 synchronized_pool_resource::_M_alloc_shared_tpools(exclusive_lock
& l
)
1381 __glibcxx_assert(_M_tpools
== nullptr);
1382 polymorphic_allocator
<_TPools
> a(upstream_resource());
1383 _TPools
* p
= a
.allocate(1);
1386 a
.construct(p
, *this, l
);
1391 __throw_exception_again
;
1393 // __glibcxx_assert(p->next == nullptr);
1394 // __glibcxx_assert(p->prev == nullptr);
1397 #endif // _GLIBCXX_HAS_GTHREADS
1399 // unsynchronized_pool_resource member functions
1402 unsynchronized_pool_resource::
1403 unsynchronized_pool_resource(const pool_options
& opts
,
1404 memory_resource
* upstream
)
1405 : _M_impl(opts
, upstream
), _M_pools(_M_impl
._M_alloc_pools())
1409 unsynchronized_pool_resource::~unsynchronized_pool_resource()
1412 // Return all memory to upstream resource.
1414 unsynchronized_pool_resource::release()
1416 // release pooled memory
1419 memory_resource
* res
= upstream_resource();
1420 polymorphic_allocator
<_Pool
> alloc
{res
};
1421 for (int i
= 0; i
< _M_impl
._M_npools
; ++i
)
1423 _M_pools
[i
].release(res
);
1424 alloc
.destroy(_M_pools
+ i
);
1426 alloc
.deallocate(_M_pools
, _M_impl
._M_npools
);
1430 // release unpooled memory
1434 // Find the right pool for a block of size block_size.
1436 unsynchronized_pool_resource::_M_find_pool(size_t block_size
) noexcept
1438 __pool_resource::_Pool
* pool
= nullptr;
1439 if (_M_pools
) // [[likely]]
1441 int index
= pool_index(block_size
, _M_impl
._M_npools
);
1443 pool
= _M_pools
+ index
;
1448 // Override for memory_resource::do_allocate
1450 unsynchronized_pool_resource::do_allocate(size_t bytes
, size_t alignment
)
1452 const auto block_size
= std::max(bytes
, alignment
);
1453 if (block_size
<= _M_impl
._M_opts
.largest_required_pool_block
)
1455 // Recreate pools if release() has been called:
1456 if (__builtin_expect(_M_pools
== nullptr, false))
1457 _M_pools
= _M_impl
._M_alloc_pools();
1458 if (auto pool
= _M_find_pool(block_size
))
1459 return pool
->allocate(upstream_resource(), _M_impl
._M_opts
);
1461 return _M_impl
.allocate(bytes
, alignment
);
1464 // Override for memory_resource::do_deallocate
1466 unsynchronized_pool_resource::
1467 do_deallocate(void* p
, size_t bytes
, size_t alignment
)
1469 size_t block_size
= std::max(bytes
, alignment
);
1470 if (block_size
<= _M_impl
._M_opts
.largest_required_pool_block
)
1472 if (auto pool
= _M_find_pool(block_size
))
1474 pool
->deallocate(upstream_resource(), p
);
1478 _M_impl
.deallocate(p
, bytes
, alignment
);
1482 _GLIBCXX_END_NAMESPACE_VERSION