cds/intrusive/free_list_cached.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
  32 #define CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H
  33
  34 #include <cds/algo/atomic.h>
  35 #include <cds/opt/options.h>
  36 #include <cds/user_setup/cache_line.h>
  37 #include <cds/details/type_padding.h>
  38
  39 #include <thread>
  40 #include <functional>
  41
  42 namespace cds { namespace intrusive {
  43
  44     /// Cached free list
  45     /** @ingroup cds_intrusive_freelist
  46
  47         The class that is a wrapper over other \p FreeList contains a small cache of free elements.
  48         Before placing a new item into underlying \p FreeList the cached free-list tryes
  49         to put that item into the cache if its corresponding slot is empty. The slot is calculated by
  50         current thread id:
  51         \code
  52         int slot = std::hash<std::thread::id>()( std::this_thread::get_id()) & (CacheSize - 1);
  53         \endcode
  54
  55         When getting the free-list checks the corresponding cache slot. If it is not empty, its
  56         contents is returned.
  57
  58         In some cases such simple algorithm significantly reduces \p FreeList contention.
  59
  60         Template parameters:
  61         - \p FreeList - a free-list implementation: \p FreeList, \p TaggedFreeList
  62         - \p CacheSize - size of cache, a small power-of-two number, default is 16
  63         - \p Padding - padding of cache elements for solving false sharing, default is \p cds::c_nCacheLineSize
  64     */
  65     template <typename FreeList, size_t CacheSize = 16, unsigned Padding = cds::c_nCacheLineSize >
  66     class CachedFreeList
  67     {
  68     public:
  69         typedef FreeList free_list_type;    ///< Undelying free-list type
  70         typedef typename free_list_type::node node; ///< Free-list node
  71
  72         static size_t const c_cache_size = CacheSize;   ///< Cache size
  73         static unsigned const c_padding = Padding;      ///< Cache element padding
  74
  75         static_assert( c_cache_size >= 4, "Cache size is too small" );
  76         static_assert( (c_cache_size & (c_cache_size - 1)) == 0, "CacheSize must be power of two" );
  77         static_assert( (c_padding & (c_padding - 1)) == 0, "Padding must be power-of-two");
  78
  79     public:
  80         /// Creates empty free list
  81         CachedFreeList()
  82         {
  83             for ( auto& i: m_cache )
  84                 i.store( nullptr, atomics::memory_order_relaxed );
  85         }
  86
  87         /// Destroys the free list. Free-list must be empty.
  88         /**
  89             @warning dtor does not free elements of the list.
  90             To free elements you should manually call \p clear() with an appropriate disposer.
  91         */
  92         ~CachedFreeList()
  93         {
  94             assert( empty());
  95         }
  96
  97         /// Puts \p pNode to the free list
  98         void put( node* pNode )
  99         {
 100             // try to put into free cell of cache
 101             node* expect = nullptr;
 102             if ( m_cache[ get_hash() ].compare_exchange_weak( expect, pNode, atomics::memory_order_release, atomics::memory_order_relaxed ))
 103                 return;
 104
 105             // cache cell is not empty - use free-list
 106             m_freeList.put( pNode );
 107         }
 108
 109         /// Gets a node from the free list. If the list is empty, returns \p nullptr
 110         node * get()
 111         {
 112             // try get from cache
 113             atomics::atomic<node*>& cell = m_cache[ get_hash() ];
 114             node* p = cell.load( atomics::memory_order_relaxed );
 115             if ( p && cell.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
 116                 return p;
 117
 118             // try read from free-list
 119             p = m_freeList.get();
 120             if ( p )
 121                 return p;
 122
 123             // iterate the cache
 124             for ( auto& cell : m_cache ) {
 125                 p = cell.load( atomics::memory_order_relaxed );
 126                 if ( p && cell.compare_exchange_weak( p, nullptr, atomics::memory_order_acquire, atomics::memory_order_relaxed ))
 127                     return p;
 128             }
 129
 130             return m_freeList.get();
 131         }
 132
 133         /// Checks whether the free list is empty
 134         bool empty() const
 135         {
 136             if ( !m_freeList.empty())
 137                 return false;
 138
 139             for ( auto& cell : m_cache ) {
 140                 node* p = cell.load( atomics::memory_order_relaxed );
 141                 if ( p )
 142                     return false;
 143             }
 144
 145             return true;
 146         }
 147
 148         /// Clears the free list (not atomic)
 149         /**
 150             For each element \p disp disposer is called to free memory.
 151             The \p Disposer interface:
 152             \code
 153             struct disposer
 154             {
 155                 void operator()( FreeList::node * node );
 156             };
 157             \endcode
 158
 159             This method must be explicitly called before the free list destructor.
 160         */
 161         template <typename Disposer>
 162         void clear( Disposer disp )
 163         {
 164             m_freeList.clear( disp );
 165             for ( auto& cell : m_cache ) {
 166                 node* p = cell.load( atomics::memory_order_relaxed );
 167                 if ( p ) {
 168                     disp( p );
 169                     cell.store( nullptr, atomics::memory_order_relaxed );
 170                 }
 171             }
 172         }
 173
 174     private:
 175         //@cond
 176         size_t get_hash()
 177         {
 178             return std::hash<std::thread::id>()( std::this_thread::get_id()) & (c_cache_size - 1);
 179         }
 180         //@endcond
 181     private:
 182         //@cond
 183         typedef typename cds::details::type_padding< atomics::atomic<node*>, c_padding >::type array_item;
 184         array_item m_cache[ c_cache_size ];
 185         free_list_type  m_freeList;
 186         //@endcond
 187     };
 188
 189 }} // namespace cds::intrusive
 190 //@endcond
 191
 192 #endif // CDSLIB_INTRUSIVE_FREE_LIST_CACHED_H