proxygen: folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits

#include <IndexedMemPool.h>

Inheritance diagram for folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >:

Classes
struct	LocalList

struct	Slot

struct	TaggedPtr

Public Types
enum	{ NumLocalLists = NumLocalLists_, LocalListLimit = LocalListLimit_ }

typedef T	value_type

typedef std::unique_ptr< T, detail::IndexedMemPoolRecycler< IndexedMemPool > >	UniquePtr

Public Member Functions
	IndexedMemPool (uint32_t capacity)

	~IndexedMemPool ()
	Destroys all of the contained elements. More...

uint32_t	capacity ()

uint32_t	maxAllocatedIndex () const

template<typename... Args>
uint32_t	allocIndex (Args &&...args)

template<typename... Args>
UniquePtr	allocElem (Args &&...args)

void	recycleIndex (uint32_t idx)
	Gives up ownership previously granted by alloc() More...

T &	operator[] (uint32_t idx)
	Provides access to the pooled element referenced by idx. More...

const T &	operator[] (uint32_t idx) const
	Provides access to the pooled element referenced by idx. More...

uint32_t	locateElem (const T *elem) const

bool	isAllocated (uint32_t idx) const
	Returns true iff idx has been alloc()ed and not recycleIndex()ed. More...

Static Public Member Functions
static constexpr uint32_t	maxIndexForCapacity (uint32_t capacity)

static constexpr uint32_t	capacityForMaxIndex (uint32_t maxIndex)

Static Public Attributes
static constexpr std::size_t	kSlotSize = sizeof(Slot)

Private Member Functions
uint32_t	slotIndex (uint32_t idx) const

Slot &	slot (uint32_t idx)

const Slot &	slot (uint32_t idx) const

void	globalPush (Slot &s, uint32_t localHead)

void	localPush (AtomicStruct< TaggedPtr, Atom > &head, uint32_t idx)

uint32_t	globalPop ()

uint32_t	localPop (AtomicStruct< TaggedPtr, Atom > &head)

AtomicStruct< TaggedPtr, Atom > &	localHead ()

void	markAllocated (Slot &slot)

Private Attributes
size_t	mmapLength_

uint32_t	actualCapacity_

Atom< uint32_t >	size_

Slot *	slots_

LocalList	local_ [NumLocalLists]

AtomicStruct< TaggedPtr, Atom >	globalHead_

Detailed Description

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>
struct folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >

Instances of IndexedMemPool dynamically allocate and then pool their element type (T), returning 4-byte integer indices that can be passed to the pool's operator[] method to access or obtain pointers to the actual elements. The memory backing items returned from the pool will always be readable, even if items have been returned to the pool. These two features are useful for lock-free algorithms. The indexing behavior makes it easy to build tagged pointer-like-things, since a large number of elements can be managed using fewer bits than a full pointer. The access-after-free behavior makes it safe to read from T-s even after they have been recycled, since it is guaranteed that the memory won't have been returned to the OS and unmapped (the algorithm must still use a mechanism to validate that the read was correct, but it doesn't have to worry about page faults), and if the elements use internal sequence numbers it can be guaranteed that there won't be an ABA match due to the element being overwritten with a different type that has the same bit pattern.

The object lifecycle strategy is controlled by the Traits parameter. One strategy, implemented by IndexedMemPoolTraitsEagerRecycle, is to construct objects when they are allocated from the pool and destroy them when they are recycled. In this mode allocIndex and allocElem have emplace-like semantics. In another strategy, implemented by IndexedMemPoolTraitsLazyRecycle, objects are default-constructed the first time they are removed from the pool, and deleted when the pool itself is deleted. By default the first mode is used for non-trivial T, and the second is used for trivial T. Clients can customize the object lifecycle by providing their own Traits implementation. See IndexedMemPoolTraits for a Traits example.

IMPORTANT: Space for extra elements is allocated to account for those that are inaccessible because they are in other local lists, so the actual number of items that can be allocated ranges from capacity to capacity + (NumLocalLists_-1)*LocalListLimit_. This is important if you are trying to maximize the capacity of the pool while constraining the bit size of the resulting pointers, because the pointers will actually range up to the boosted capacity. See maxIndexForCapacity and capacityForMaxIndex.

To avoid contention, NumLocalLists_ free lists of limited (less than or equal to LocalListLimit_) size are maintained, and each thread retrieves and returns entries from its associated local list. If the local list becomes too large then elements are placed in bulk in a global free list. This allows items to be efficiently recirculated from consumers to producers. AccessSpreader is used to access the local lists, so there is no performance advantage to having more local lists than L1 caches.

The pool mmap-s the entire necessary address space when the pool is constructed, but delays element construction. This means that only elements that are actually returned to the caller get paged into the process's resident set (RSS).

Definition at line 159 of file IndexedMemPool.h.

Member Typedef Documentation

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

typedef std::unique_ptr<T, detail::IndexedMemPoolRecycler<IndexedMemPool> > folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::UniquePtr

Definition at line 163 of file IndexedMemPool.h.

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

typedef T folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::value_type

Definition at line 160 of file IndexedMemPool.h.

Member Enumeration Documentation

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

anonymous enum

Enumerator
NumLocalLists
LocalListLimit

Definition at line 166 of file IndexedMemPool.h.

        {
     NumLocalLists = NumLocalLists_,
     LocalListLimit = LocalListLimit_,
   };

Constructor & Destructor Documentation

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::IndexedMemPool ( uint32_t capacity )

inlineexplicit

Constructs a pool that can allocate at least capacity elements, even if all the local lists are full

Definition at line 192 of file IndexedMemPool.h.

References i, and value.

       : actualCapacity_(maxIndexForCapacity(capacity)),
         size_(0),
         globalHead_(TaggedPtr{}) {
     const size_t needed = sizeof(Slot) * (actualCapacity_ + 1);
     size_t pagesize = size_t(sysconf(_SC_PAGESIZE));
     mmapLength_ = ((needed - 1) & ~(pagesize - 1)) + pagesize;
     assert(needed <= mmapLength_ && mmapLength_ < needed + pagesize);
     assert((mmapLength_ % pagesize) == 0);
 
     slots_ = static_cast<Slot*>(mmap(
         nullptr,
         mmapLength_,
         PROT_READ | PROT_WRITE,
         MAP_PRIVATE | MAP_ANONYMOUS,
         -1,
         0));
     if (slots_ == MAP_FAILED) {
       assert(errno == ENOMEM);
       throw std::bad_alloc();
     }
     // Atom is expected to be std::atomic, which is trivially
     // constructible, so we can avoid explicitly initializing the
     // slots which would cause the whole mapped area to be paged in.
     //
     // TODO: Switch to is_trivially_constructible once support
     // for GCC 4.9 is dropped for this file.
     if /* constexpr */ (!std::is_trivial<Atom<uint32_t>>::value) {
       for (size_t i = 1; i < actualCapacity_ + 1; i++) {
         // Atom is enforced above to be nothrow-default-constructible
         new (&slots_[i].localNext) Atom<uint32_t>;
         new (&slots_[i].globalNext) Atom<uint32_t>;
       }
     }
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::~IndexedMemPool ( )

inline

Destroys all of the contained elements.

Definition at line 229 of file IndexedMemPool.h.

References folly::ssl::cleanup(), i, and uint32_t.

                     {
     using A = Atom<uint32_t>;
     for (uint32_t i = maxAllocatedIndex(); i > 0; --i) {
       Traits::cleanup(&slots_[i].elem);
     }
     for (size_t i = 1; i < actualCapacity_ + 1; i++) {
       slots_[i].localNext.~A();
       slots_[i].globalNext.~A();
     }
     munmap(slots_, mmapLength_);
   }

Member Function Documentation

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

template<typename... Args>

UniquePtr folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::allocElem ( Args &&... args )

inline

If an element is available, returns a std::unique_ptr to it that will recycle the element to the pool when it is reclaimed, otherwise returns a null (falsy) std::unique_ptr. Passes a pointer to the element to Traits::onAllocate before the slot is marked as allocated.

Definition at line 279 of file IndexedMemPool.h.

References ptr, and T.

Referenced by TEST(), and testTraits().

                                       {
     auto idx = allocIndex(std::forward<Args>(args)...);
     T* ptr = idx == 0 ? nullptr : &slot(idx).elem;
     return UniquePtr(ptr, typename UniquePtr::deleter_type(this));
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

template<typename... Args>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::allocIndex ( Args &&... args )

inline

Finds a slot with a non-zero index, emplaces a T there if we're using the eager recycle lifecycle mode, and returns the index, or returns 0 if no elements are available. Passes a pointer to the element to Traits::onAllocate before the slot is marked as allocated.

Definition at line 264 of file IndexedMemPool.h.

References testing::Args(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::Slot::elem, and s.

Referenced by folly::detail::LifoSemBase< BatonType, Atom >::allocateNode(), folly::FlatCombining< FcSimpleExample< Mutex, Atom >, Mutex, Atom >::allocRec(), and TEST().

                                       {
     auto idx = localPop(localHead());
     if (idx != 0) {
       Slot& s = slot(idx);
       Traits::onAllocate(&s.elem, std::forward<Args>(args)...);
       markAllocated(s);
     }
     return idx;
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::capacity ( )

inline

Returns a lower bound on the number of elements that may be simultaneously allocated and not yet recycled. Because of the local lists it is possible that more elements than this are returned successfully

Definition at line 245 of file IndexedMemPool.h.

                       {
     return capacityForMaxIndex(actualCapacity_);
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

static constexpr uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::capacityForMaxIndex ( uint32_t maxIndex )

inlinestatic

Definition at line 186 of file IndexedMemPool.h.

                                                                    {
     return maxIndex - (NumLocalLists - 1) * LocalListLimit;
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::globalPop ( )

inlineprivate

Definition at line 472 of file IndexedMemPool.h.

References folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::idx, and folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withIdx().

                        {
     while (true) {
       TaggedPtr gh = globalHead_.load(std::memory_order_acquire);
       if (gh.idx == 0 ||
           globalHead_.compare_exchange_strong(
               gh,
               gh.withIdx(
                   slot(gh.idx).globalNext.load(std::memory_order_relaxed)))) {
         // global list is empty, or pop was successful
         return gh.idx;
       }
     }
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

void folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::globalPush	(	Slot &	s,
		uint32_t	localHead
	)

inlineprivate

Definition at line 434 of file IndexedMemPool.h.

References folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::Slot::globalNext, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::idx, and folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withIdx().

                                                {
     while (true) {
       TaggedPtr gh = globalHead_.load(std::memory_order_acquire);
       s.globalNext.store(gh.idx, std::memory_order_relaxed);
       if (globalHead_.compare_exchange_strong(gh, gh.withIdx(localHead))) {
         // success
         return;
       }
     }
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

bool folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::isAllocated ( uint32_t idx ) const

inline

Returns true iff idx has been alloc()ed and not recycleIndex()ed.

Definition at line 320 of file IndexedMemPool.h.

References uint32_t.

Referenced by testTraits().

                                        {
     return slot(idx).localNext.load(std::memory_order_acquire) == uint32_t(-1);
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

AtomicStruct<TaggedPtr, Atom>& folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::localHead ( )

inlineprivate

Definition at line 525 of file IndexedMemPool.h.

References current, and folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::LocalList::head.

                                              {
     auto stripe = AccessSpreader<Atom>::current(NumLocalLists);
     return local_[stripe].head;
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::localPop ( AtomicStruct< TaggedPtr, Atom > & head )

inlineprivate

Definition at line 487 of file IndexedMemPool.h.

References folly::AtomicStruct< T, Atom >::compare_exchange_strong(), h, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::idx, folly::AtomicStruct< T, Atom >::load(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::Slot::localNext, cpp.ast::next(), s, uint32_t, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withIdx(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withSize(), and folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withSizeDecr().

                                                          {
     while (true) {
       TaggedPtr h = head.load(std::memory_order_acquire);
       if (h.idx != 0) {
         // local list is non-empty, try to pop
         Slot& s = slot(h.idx);
         auto next = s.localNext.load(std::memory_order_relaxed);
         if (head.compare_exchange_strong(h, h.withIdx(next).withSizeDecr())) {
           // success
           return h.idx;
         }
         continue;
       }
 
       uint32_t idx = globalPop();
       if (idx == 0) {
         // global list is empty, allocate and construct new slot
         if (size_.load(std::memory_order_relaxed) >= actualCapacity_ ||
             (idx = ++size_) > actualCapacity_) {
           // allocation failed
           return 0;
         }
         Traits::initialize(&slot(idx).elem);
         return idx;
       }
 
       Slot& s = slot(idx);
       auto next = s.localNext.load(std::memory_order_relaxed);
       if (head.compare_exchange_strong(
               h, h.withIdx(next).withSize(LocalListLimit))) {
         // global list moved to local list, keep head for us
         return idx;
       }
       // local bulk push failed, return idx to the global list and try again
       globalPush(s, idx);
     }
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

void folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::localPush	(	AtomicStruct< TaggedPtr, Atom > &	head,
		uint32_t	idx
	)

inlineprivate

Definition at line 446 of file IndexedMemPool.h.

References folly::AtomicStruct< T, Atom >::compare_exchange_strong(), h, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::idx, folly::AtomicStruct< T, Atom >::load(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::Slot::localNext, s, folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::size(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withEmpty(), folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withIdx(), and folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::TaggedPtr::withSizeIncr().

                                                                     {
     Slot& s = slot(idx);
     TaggedPtr h = head.load(std::memory_order_acquire);
     while (true) {
       s.localNext.store(h.idx, std::memory_order_release);
       Traits::onRecycle(&slot(idx).elem);
 
       if (h.size() == LocalListLimit) {
         // push will overflow local list, steal it instead
         if (head.compare_exchange_strong(h, h.withEmpty())) {
           // steal was successful, put everything in the global list
           globalPush(s, idx);
           return;
         }
       } else {
         // local list has space
         if (head.compare_exchange_strong(h, h.withIdx(idx).withSizeIncr())) {
           // success
           return;
         }
       }
       // h was updated by failing CAS
     }
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::locateElem ( const T * elem ) const

inline

If elem == &pool[idx], then pool.locateElem(elem) == idx. Also, pool.locateElem(nullptr) == 0

Definition at line 303 of file IndexedMemPool.h.

References uint32_t, and value.

Referenced by folly::detail::LifoSemBase< BatonType, Atom >::nodeToIdx(), folly::detail::LifoSemNodeRecycler< Handoff, Atom >::operator()(), TEST(), and testTraits().

                                            {
     if (!elem) {
       return 0;
     }
 
     static_assert(std::is_standard_layout<Slot>::value, "offsetof needs POD");
 
     auto slot = reinterpret_cast<const Slot*>(
         reinterpret_cast<const char*>(elem) - offsetof(Slot, elem));
     auto rv = uint32_t(slot - slots_);
 
     // this assert also tests that rv is in range
     assert(elem == &(*this)[rv]);
     return rv;
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

void folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::markAllocated ( Slot & slot )

inlineprivate

Definition at line 530 of file IndexedMemPool.h.

References folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::Slot::localNext, and uint32_t.

                                  {
     slot.localNext.store(uint32_t(-1), std::memory_order_release);
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::maxAllocatedIndex ( ) const

inline

Returns the maximum index of elements ever allocated in this pool including elements that have been recycled.

Definition at line 251 of file IndexedMemPool.h.

References testing::Args(), min, and uint32_t.

                                      {
     // Take the minimum since it is possible that size_ > actualCapacity_.
     // This can happen if there are multiple concurrent requests
     // when size_ == actualCapacity_ - 1.
     return std::min(uint32_t(size_), uint32_t(actualCapacity_));
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

static constexpr uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::maxIndexForCapacity ( uint32_t capacity )

inlinestatic

Definition at line 178 of file IndexedMemPool.h.

References max, min, uint32_t, and uint64_t.

                                                                    {
     // index of std::numeric_limits<uint32_t>::max() is reserved for isAllocated
     // tracking
     return uint32_t(std::min(
         uint64_t(capacity) + (NumLocalLists - 1) * LocalListLimit,
         uint64_t(std::numeric_limits<uint32_t>::max() - 1)));
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

T& folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::operator[] ( uint32_t idx )

inline

Provides access to the pooled element referenced by idx.

Definition at line 292 of file IndexedMemPool.h.

                               {
     return slot(idx).elem;
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

const T& folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::operator[] ( uint32_t idx ) const

inline

Provides access to the pooled element referenced by idx.

Definition at line 297 of file IndexedMemPool.h.

                                           {
     return slot(idx).elem;
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

void folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::recycleIndex ( uint32_t idx )

inline

Gives up ownership previously granted by alloc()

Definition at line 286 of file IndexedMemPool.h.

Referenced by folly::detail::LifoSemBase< BatonType, Atom >::allocateNode(), folly::FlatCombining< FcSimpleExample< Mutex, Atom >, Mutex, Atom >::freeRec(), folly::detail::LifoSemNodeRecycler< Handoff, Atom >::operator()(), and testTraits().

                                   {
     assert(isAllocated(idx));
     localPush(localHead(), idx);
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

Slot& folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::slot ( uint32_t idx )

inlineprivate

Definition at line 424 of file IndexedMemPool.h.

                            {
     return slots_[slotIndex(idx)];
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

const Slot& folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::slot ( uint32_t idx ) const

inlineprivate

Definition at line 428 of file IndexedMemPool.h.

                                        {
     return slots_[slotIndex(idx)];
   }

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::slotIndex ( uint32_t idx ) const

inlineprivate

Definition at line 417 of file IndexedMemPool.h.

                                          {
     assert(
         0 < idx && idx <= actualCapacity_ &&
         idx <= size_.load(std::memory_order_acquire));
     return idx;
   }

Member Data Documentation

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

uint32_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::actualCapacity_

private

the actual number of slots that we will allocate, to guarantee that we will satisfy the capacity requested at construction time. They will be numbered 1..actualCapacity_ (note the 1-based counting), and occupy slots_[1..actualCapacity_].

Definition at line 393 of file IndexedMemPool.h.

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

AtomicStruct<TaggedPtr, Atom> folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::globalHead_

private

this is the head of a list of node chained by globalNext, that are themselves each the head of a list chained by localNext

Definition at line 413 of file IndexedMemPool.h.

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

constexpr std::size_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::kSlotSize = sizeof(Slot)

static

Definition at line 535 of file IndexedMemPool.h.

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

LocalList folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::local_[NumLocalLists]

private

use AccessSpreader to find your list. We use stripes instead of thread-local to avoid the need to grow or shrink on thread start or join. These are heads of lists chained with localNext

Definition at line 408 of file IndexedMemPool.h.

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

size_t folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::mmapLength_

private

the number of bytes allocated from mmap, which is a multiple of the page size of the machine

Definition at line 387 of file IndexedMemPool.h.

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

Atom<uint32_t> folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::size_

private

this records the number of slots that have actually been constructed. To allow use of atomic ++ instead of CAS, we let this overflow. The actual number of constructed elements is min(actualCapacity_, size_)

Definition at line 399 of file IndexedMemPool.h.

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>

Slot* folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >::slots_

private

raw storage, only 1..min(size_,actualCapacity_) (inclusive) are actually constructed. Note that slots_[0] is not constructed or used

Definition at line 403 of file IndexedMemPool.h.

The documentation for this struct was generated from the following file:

proxygen/folly/folly/IndexedMemPool.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>> struct folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T, uint32_t NumLocalLists_ = 32, uint32_t LocalListLimit_ = 200, template< typename > class Atom = std::atomic, typename Traits = IndexedMemPoolTraits<T>>
struct folly::IndexedMemPool< T, NumLocalLists_, LocalListLimit_, Atom, Traits >