X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FIndexedMemPool.h;h=437685a23e657349cee5dd9c8e2ce51376242299;hb=30e9f34e93579b255767fc1680c81fcd9c023ba9;hp=0c959a3c803e39a5963e0d3762c9cd1ac33ed179;hpb=054af315ec7cbd725a9ae6d0c271710998fc56ea;p=folly.git diff --git a/folly/IndexedMemPool.h b/folly/IndexedMemPool.h index 0c959a3c..437685a2 100644 --- a/folly/IndexedMemPool.h +++ b/folly/IndexedMemPool.h @@ -1,5 +1,5 @@ /* - * Copyright 2014 Facebook, Inc. + * Copyright 2015 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -17,6 +17,7 @@ #ifndef FOLLY_INDEXEDMEMPOOL_H #define FOLLY_INDEXEDMEMPOOL_H +#include #include #include #include @@ -25,6 +26,10 @@ #include #include +// Ignore shadowing warnings within this file, so includers can use -Wshadow. +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wshadow" + namespace folly { namespace detail { @@ -32,21 +37,30 @@ template struct IndexedMemPoolRecycler; } -/// 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. Once they are constructed, elements are -/// never destroyed. 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 pooling 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. +/// 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. +/// +/// IndexedMemPool has two object lifecycle strategies. The first +/// 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 the second mode, 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. /// /// IMPORTANT: Space for extra elements is allocated to account for those /// that are inaccessible because they are in other local lists, so the @@ -73,7 +87,9 @@ struct IndexedMemPoolRecycler; template class Atom = std::atomic> + template class Atom = std::atomic, + bool EagerRecycleWhenTrivial = false, + bool EagerRecycleWhenNotTrivial = true> struct IndexedMemPool : boost::noncopyable { typedef T value_type; @@ -87,6 +103,11 @@ struct IndexedMemPool : boost::noncopyable { }; + static constexpr bool eagerRecycle() { + return std::is_trivial::value + ? EagerRecycleWhenTrivial : EagerRecycleWhenNotTrivial; + } + // these are public because clients may need to reason about the number // of bits required to hold indices from a pool, given its capacity @@ -117,7 +138,7 @@ struct IndexedMemPool : boost::noncopyable { slots_ = static_cast(mmap(nullptr, mmapLength_, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)); - if (slots_ == nullptr) { + if (slots_ == MAP_FAILED) { assert(errno == ENOMEM); throw std::bad_alloc(); } @@ -125,8 +146,10 @@ struct IndexedMemPool : boost::noncopyable { /// Destroys all of the contained elements ~IndexedMemPool() { - for (size_t i = size_; i > 0; --i) { - slots_[i].~Slot(); + if (!eagerRecycle()) { + for (size_t i = size_; i > 0; --i) { + slots_[i].~Slot(); + } } munmap(slots_, mmapLength_); } @@ -139,24 +162,38 @@ struct IndexedMemPool : boost::noncopyable { return capacityForMaxIndex(actualCapacity_); } - /// Grants ownership of (*this)[retval], or returns 0 if no elements - /// are available - uint32_t allocIndex() { - return localPop(localHead()); + /// 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. + template + uint32_t allocIndex(Args&&... args) { + static_assert(sizeof...(Args) == 0 || eagerRecycle(), + "emplace-style allocation requires eager recycle, " + "which is defaulted only for non-trivial types"); + auto idx = localPop(localHead()); + if (idx != 0 && eagerRecycle()) { + T* ptr = &slot(idx).elem; + new (ptr) T(std::forward(args)...); + } + return idx; } /// 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 - UniquePtr allocElem() { - auto idx = allocIndex(); - auto ptr = idx == 0 ? nullptr : &slot(idx).elem; + template + UniquePtr allocElem(Args&&... args) { + auto idx = allocIndex(std::forward(args)...); + T* ptr = idx == 0 ? nullptr : &slot(idx).elem; return UniquePtr(ptr, typename UniquePtr::deleter_type(this)); } /// Gives up ownership previously granted by alloc() void recycleIndex(uint32_t idx) { assert(isAllocated(idx)); + if (eagerRecycle()) { + slot(idx).elem.~T(); + } localPush(localHead(), idx); } @@ -269,7 +306,7 @@ struct IndexedMemPool : boost::noncopyable { /// To allow use of atomic ++ instead of CAS, we let this overflow. /// The actual number of constructed elements is min(actualCapacity_, /// size_) - std::atomic size_; + Atom size_; /// raw storage, only 1..min(size_,actualCapacity_) (inclusive) are /// actually constructed. Note that slots_[0] is not constructed or used @@ -375,8 +412,12 @@ struct IndexedMemPool : boost::noncopyable { // allocation failed return 0; } - // construct it - new (&slot(idx)) T(); + // default-construct it now if we aren't going to construct and + // destroy on each allocation + if (!eagerRecycle()) { + T* ptr = &slot(idx).elem; + new (ptr) T(); + } slot(idx).localNext = uint32_t(-1); return idx; } @@ -424,4 +465,5 @@ struct IndexedMemPoolRecycler { } // namespace folly +# pragma GCC diagnostic pop #endif