2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
19 #include <type_traits>
23 #include <boost/noncopyable.hpp>
24 #include <folly/AtomicStruct.h>
25 #include <folly/detail/CacheLocality.h>
26 #include <folly/portability/SysMman.h>
27 #include <folly/portability/Unistd.h>
29 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
30 #pragma GCC diagnostic push
31 #pragma GCC diagnostic ignored "-Wshadow"
36 template <typename Pool>
37 struct IndexedMemPoolRecycler;
40 /// Instances of IndexedMemPool dynamically allocate and then pool their
41 /// element type (T), returning 4-byte integer indices that can be passed
42 /// to the pool's operator[] method to access or obtain pointers to the
43 /// actual elements. The memory backing items returned from the pool
44 /// will always be readable, even if items have been returned to the pool.
45 /// These two features are useful for lock-free algorithms. The indexing
46 /// behavior makes it easy to build tagged pointer-like-things, since
47 /// a large number of elements can be managed using fewer bits than a
48 /// full pointer. The access-after-free behavior makes it safe to read
49 /// from T-s even after they have been recycled, since it is guaranteed
50 /// that the memory won't have been returned to the OS and unmapped
51 /// (the algorithm must still use a mechanism to validate that the read
52 /// was correct, but it doesn't have to worry about page faults), and if
53 /// the elements use internal sequence numbers it can be guaranteed that
54 /// there won't be an ABA match due to the element being overwritten with
55 /// a different type that has the same bit pattern.
57 /// IndexedMemPool has two object lifecycle strategies. The first
58 /// is to construct objects when they are allocated from the pool and
59 /// destroy them when they are recycled. In this mode allocIndex and
60 /// allocElem have emplace-like semantics. In the second mode, objects
61 /// are default-constructed the first time they are removed from the pool,
62 /// and deleted when the pool itself is deleted. By default the first
63 /// mode is used for non-trivial T, and the second is used for trivial T.
65 /// IMPORTANT: Space for extra elements is allocated to account for those
66 /// that are inaccessible because they are in other local lists, so the
67 /// actual number of items that can be allocated ranges from capacity to
68 /// capacity + (NumLocalLists_-1)*LocalListLimit_. This is important if
69 /// you are trying to maximize the capacity of the pool while constraining
70 /// the bit size of the resulting pointers, because the pointers will
71 /// actually range up to the boosted capacity. See maxIndexForCapacity
72 /// and capacityForMaxIndex.
74 /// To avoid contention, NumLocalLists_ free lists of limited (less than
75 /// or equal to LocalListLimit_) size are maintained, and each thread
76 /// retrieves and returns entries from its associated local list. If the
77 /// local list becomes too large then elements are placed in bulk in a
78 /// global free list. This allows items to be efficiently recirculated
79 /// from consumers to producers. AccessSpreader is used to access the
80 /// local lists, so there is no performance advantage to having more
81 /// local lists than L1 caches.
83 /// The pool mmap-s the entire necessary address space when the pool is
84 /// constructed, but delays element construction. This means that only
85 /// elements that are actually returned to the caller get paged into the
86 /// process's resident set (RSS).
88 int NumLocalLists_ = 32,
89 int LocalListLimit_ = 200,
90 template<typename> class Atom = std::atomic,
91 bool EagerRecycleWhenTrivial = false,
92 bool EagerRecycleWhenNotTrivial = true>
93 struct IndexedMemPool : boost::noncopyable {
96 typedef std::unique_ptr<T, detail::IndexedMemPoolRecycler<IndexedMemPool>>
99 static_assert(LocalListLimit_ <= 255, "LocalListLimit must fit in 8 bits");
101 NumLocalLists = NumLocalLists_,
102 LocalListLimit = LocalListLimit_
106 static constexpr bool eagerRecycle() {
107 return std::is_trivial<T>::value
108 ? EagerRecycleWhenTrivial : EagerRecycleWhenNotTrivial;
111 // these are public because clients may need to reason about the number
112 // of bits required to hold indices from a pool, given its capacity
114 static constexpr uint32_t maxIndexForCapacity(uint32_t capacity) {
115 // index of uint32_t(-1) == UINT32_MAX is reserved for isAllocated tracking
116 return uint32_t(std::min(
117 uint64_t(capacity) + (NumLocalLists - 1) * LocalListLimit,
118 uint64_t(uint32_t(-1) - 1)));
121 static constexpr uint32_t capacityForMaxIndex(uint32_t maxIndex) {
122 return maxIndex - (NumLocalLists - 1) * LocalListLimit;
126 /// Constructs a pool that can allocate at least _capacity_ elements,
127 /// even if all the local lists are full
128 explicit IndexedMemPool(uint32_t capacity)
129 : actualCapacity_(maxIndexForCapacity(capacity))
131 , globalHead_(TaggedPtr{})
133 const size_t needed = sizeof(Slot) * (actualCapacity_ + 1);
134 size_t pagesize = sysconf(_SC_PAGESIZE);
135 mmapLength_ = ((needed - 1) & ~(pagesize - 1)) + pagesize;
136 assert(needed <= mmapLength_ && mmapLength_ < needed + pagesize);
137 assert((mmapLength_ % pagesize) == 0);
139 slots_ = static_cast<Slot*>(mmap(nullptr, mmapLength_,
140 PROT_READ | PROT_WRITE,
141 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0));
142 if (slots_ == MAP_FAILED) {
143 assert(errno == ENOMEM);
144 throw std::bad_alloc();
148 /// Destroys all of the contained elements
150 if (!eagerRecycle()) {
151 for (size_t i = size_; i > 0; --i) {
155 munmap(slots_, mmapLength_);
158 /// Returns a lower bound on the number of elements that may be
159 /// simultaneously allocated and not yet recycled. Because of the
160 /// local lists it is possible that more elements than this are returned
163 return capacityForMaxIndex(actualCapacity_);
166 /// Finds a slot with a non-zero index, emplaces a T there if we're
167 /// using the eager recycle lifecycle mode, and returns the index,
168 /// or returns 0 if no elements are available.
169 template <typename ...Args>
170 uint32_t allocIndex(Args&&... args) {
171 static_assert(sizeof...(Args) == 0 || eagerRecycle(),
172 "emplace-style allocation requires eager recycle, "
173 "which is defaulted only for non-trivial types");
174 auto idx = localPop(localHead());
175 if (idx != 0 && eagerRecycle()) {
176 T* ptr = &slot(idx).elem;
177 new (ptr) T(std::forward<Args>(args)...);
182 /// If an element is available, returns a std::unique_ptr to it that will
183 /// recycle the element to the pool when it is reclaimed, otherwise returns
184 /// a null (falsy) std::unique_ptr
185 template <typename ...Args>
186 UniquePtr allocElem(Args&&... args) {
187 auto idx = allocIndex(std::forward<Args>(args)...);
188 T* ptr = idx == 0 ? nullptr : &slot(idx).elem;
189 return UniquePtr(ptr, typename UniquePtr::deleter_type(this));
192 /// Gives up ownership previously granted by alloc()
193 void recycleIndex(uint32_t idx) {
194 assert(isAllocated(idx));
195 if (eagerRecycle()) {
198 localPush(localHead(), idx);
201 /// Provides access to the pooled element referenced by idx
202 T& operator[](uint32_t idx) {
203 return slot(idx).elem;
206 /// Provides access to the pooled element referenced by idx
207 const T& operator[](uint32_t idx) const {
208 return slot(idx).elem;
211 /// If elem == &pool[idx], then pool.locateElem(elem) == idx. Also,
212 /// pool.locateElem(nullptr) == 0
213 uint32_t locateElem(const T* elem) const {
218 static_assert(std::is_standard_layout<Slot>::value, "offsetof needs POD");
220 auto slot = reinterpret_cast<const Slot*>(
221 reinterpret_cast<const char*>(elem) - offsetof(Slot, elem));
222 auto rv = uint32_t(slot - slots_);
224 // this assert also tests that rv is in range
225 assert(elem == &(*this)[rv]);
229 /// Returns true iff idx has been alloc()ed and not recycleIndex()ed
230 bool isAllocated(uint32_t idx) const {
231 return slot(idx).localNext == uint32_t(-1);
243 Slot() : localNext{}, globalNext{} {}
249 // size is bottom 8 bits, tag in top 24. g++'s code generation for
250 // bitfields seems to depend on the phase of the moon, plus we can
251 // do better because we can rely on other checks to avoid masking
256 SizeMask = (1U << SizeBits) - 1,
257 TagIncr = 1U << SizeBits,
260 uint32_t size() const {
261 return tagAndSize & SizeMask;
264 TaggedPtr withSize(uint32_t repl) const {
265 assert(repl <= LocalListLimit);
266 return TaggedPtr{ idx, (tagAndSize & ~SizeMask) | repl };
269 TaggedPtr withSizeIncr() const {
270 assert(size() < LocalListLimit);
271 return TaggedPtr{ idx, tagAndSize + 1 };
274 TaggedPtr withSizeDecr() const {
276 return TaggedPtr{ idx, tagAndSize - 1 };
279 TaggedPtr withIdx(uint32_t repl) const {
280 return TaggedPtr{ repl, tagAndSize + TagIncr };
283 TaggedPtr withEmpty() const {
284 return withIdx(0).withSize(0);
288 struct FOLLY_ALIGN_TO_AVOID_FALSE_SHARING LocalList {
289 AtomicStruct<TaggedPtr,Atom> head;
291 LocalList() : head(TaggedPtr{}) {}
296 /// the actual number of slots that we will allocate, to guarantee
297 /// that we will satisfy the capacity requested at construction time.
298 /// They will be numbered 1..actualCapacity_ (note the 1-based counting),
299 /// and occupy slots_[1..actualCapacity_].
300 size_t actualCapacity_;
302 /// the number of bytes allocated from mmap, which is a multiple of
303 /// the page size of the machine
306 /// this records the number of slots that have actually been constructed.
307 /// To allow use of atomic ++ instead of CAS, we let this overflow.
308 /// The actual number of constructed elements is min(actualCapacity_,
310 Atom<uint32_t> size_;
312 /// raw storage, only 1..min(size_,actualCapacity_) (inclusive) are
313 /// actually constructed. Note that slots_[0] is not constructed or used
314 FOLLY_ALIGN_TO_AVOID_FALSE_SHARING Slot* slots_;
316 /// use AccessSpreader to find your list. We use stripes instead of
317 /// thread-local to avoid the need to grow or shrink on thread start
318 /// or join. These are heads of lists chained with localNext
319 LocalList local_[NumLocalLists];
321 /// this is the head of a list of node chained by globalNext, that are
322 /// themselves each the head of a list chained by localNext
323 FOLLY_ALIGN_TO_AVOID_FALSE_SHARING AtomicStruct<TaggedPtr,Atom> globalHead_;
325 ///////////// private methods
327 size_t slotIndex(uint32_t idx) const {
329 idx <= actualCapacity_ &&
330 idx <= size_.load(std::memory_order_acquire));
334 Slot& slot(uint32_t idx) {
335 return slots_[slotIndex(idx)];
338 const Slot& slot(uint32_t idx) const {
339 return slots_[slotIndex(idx)];
342 // localHead references a full list chained by localNext. s should
343 // reference slot(localHead), it is passed as a micro-optimization
344 void globalPush(Slot& s, uint32_t localHead) {
346 TaggedPtr gh = globalHead_.load(std::memory_order_acquire);
347 s.globalNext = gh.idx;
348 if (globalHead_.compare_exchange_strong(gh, gh.withIdx(localHead))) {
355 // idx references a single node
356 void localPush(AtomicStruct<TaggedPtr,Atom>& head, uint32_t idx) {
358 TaggedPtr h = head.load(std::memory_order_acquire);
362 if (h.size() == LocalListLimit) {
363 // push will overflow local list, steal it instead
364 if (head.compare_exchange_strong(h, h.withEmpty())) {
365 // steal was successful, put everything in the global list
370 // local list has space
371 if (head.compare_exchange_strong(h, h.withIdx(idx).withSizeIncr())) {
376 // h was updated by failing CAS
380 // returns 0 if empty
381 uint32_t globalPop() {
383 TaggedPtr gh = globalHead_.load(std::memory_order_acquire);
384 if (gh.idx == 0 || globalHead_.compare_exchange_strong(
385 gh, gh.withIdx(slot(gh.idx).globalNext))) {
386 // global list is empty, or pop was successful
392 // returns 0 if allocation failed
393 uint32_t localPop(AtomicStruct<TaggedPtr,Atom>& head) {
395 TaggedPtr h = head.load(std::memory_order_acquire);
397 // local list is non-empty, try to pop
398 Slot& s = slot(h.idx);
399 if (head.compare_exchange_strong(
400 h, h.withIdx(s.localNext).withSizeDecr())) {
402 s.localNext = uint32_t(-1);
408 uint32_t idx = globalPop();
410 // global list is empty, allocate and construct new slot
411 if (size_.load(std::memory_order_relaxed) >= actualCapacity_ ||
412 (idx = ++size_) > actualCapacity_) {
416 // default-construct it now if we aren't going to construct and
417 // destroy on each allocation
418 if (!eagerRecycle()) {
419 T* ptr = &slot(idx).elem;
422 slot(idx).localNext = uint32_t(-1);
427 if (head.compare_exchange_strong(
428 h, h.withIdx(s.localNext).withSize(LocalListLimit))) {
429 // global list moved to local list, keep head for us
430 s.localNext = uint32_t(-1);
433 // local bulk push failed, return idx to the global list and try again
438 AtomicStruct<TaggedPtr,Atom>& localHead() {
439 auto stripe = detail::AccessSpreader<Atom>::current(NumLocalLists);
440 return local_[stripe].head;
446 /// This is a stateful Deleter functor, which allows std::unique_ptr
447 /// to track elements allocated from an IndexedMemPool by tracking the
448 /// associated pool. See IndexedMemPool::allocElem.
449 template <typename Pool>
450 struct IndexedMemPoolRecycler {
453 explicit IndexedMemPoolRecycler(Pool* pool) : pool(pool) {}
455 IndexedMemPoolRecycler(const IndexedMemPoolRecycler<Pool>& rhs)
457 IndexedMemPoolRecycler& operator= (const IndexedMemPoolRecycler<Pool>& rhs)
460 void operator()(typename Pool::value_type* elem) const {
461 pool->recycleIndex(pool->locateElem(elem));
469 # pragma GCC diagnostic pop