threadSafeFreeList.h

Engine/source/platform/threads/threadSafeFreeList.h

Lock-free freelists for concurrent access.

More...

Classes:

Detailed Description

Lock-free freelists for concurrent access.

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _THREADSAFEFREELIST_H_
 25#define _THREADSAFEFREELIST_H_
 26
 27#ifndef _THREADSAFEREFCOUNT_H_
 28#  include "platform/threads/threadSafeRefCount.h"
 29#endif
 30#ifndef _PLATFORMINTRINSICS_H_
 31#  include "platform/platformIntrinsics.h"
 32#endif
 33
 34#include "platform/tmm_off.h"
 35
 36
 37/// @file
 38/// Lock-free freelists for concurrent access.
 39
 40
 41/// Freelist for re-using allocations in a concurrent setting.
 42///
 43/// @note Make sure that there are no more allocations in use
 44///   when the free list is destructed.
 45/// @note Allocated instances come with a reference already counted
 46///   on the instance.
 47///
 48/// @param T Type of elements to allocate; must be derived from
 49///   ThreadSafeRefCount and have at least define one additional
 50///   pointer-sized field.
 51template< class T >
 52class ThreadSafeFreeList
 53{
 54   protected:
 55
 56      T* mFreeList;
 57
 58      #ifdef TORQUE_DEBUG
 59      S32 mNumNodesTotal;
 60      S32 mNumNodesFree;
 61      #endif
 62
 63      T*& getNext( T* ptr )
 64      {
 65         return *( ( T** ) &( ( U8* ) ptr )[ sizeof( T ) - sizeof( T* ) ] );
 66      }
 67
 68   public:
 69
 70      /// Create the freelist.
 71      ///
 72      /// @param numPreAlloc Number of instances to pre-allocate.
 73      ThreadSafeFreeList( U32 numPreAlloc = 0 )
 74         : mFreeList( 0 )
 75      {
 76         #ifdef TORQUE_DEBUG
 77         mNumNodesTotal = 0;
 78         mNumNodesFree = 0;
 79         #endif
 80
 81         for( U32 i = 0; i < numPreAlloc; ++ i )
 82            free( alloc() );
 83      }
 84
 85      ~ThreadSafeFreeList()
 86      {
 87         #ifdef TORQUE_DEBUG
 88         AssertWarn( mNumNodesTotal == mNumNodesFree,
 89            "ThreadSafeFreeList::~ThreadSafeFreeList() - still got live instances" );
 90         #endif
 91
 92         // Destroy remaining nodes.  Not synchronized.  We assume all
 93         // concurrent processing to have finished.
 94
 95         while( mFreeList )
 96         {
 97            T* next = getNext( mFreeList );
 98            dFree( mFreeList );
 99            mFreeList = next;
100         }
101      }
102
103      /// Return memory for a new instance.
104      void* alloc()
105      {
106         T* ptr;
107         while( 1 )
108         {
109            ptr = ThreadSafeRef< T >::safeRead( mFreeList );
110            if( !ptr )
111            {
112               ptr = ( T* ) dMalloc( sizeof( T ) );
113               dMemset( ptr, 0, sizeof( T ) );
114
115               #ifdef TORQUE_DEBUG
116               dFetchAndAdd( mNumNodesTotal, 1 );
117               #endif
118
119               ptr->addRef();
120               break;
121            }
122            else if( dCompareAndSwap( mFreeList, ptr, getNext( ptr ) ) )
123            {
124               #ifdef TORQUE_DEBUG
125               dFetchAndAdd( mNumNodesFree, -1 );
126               #endif
127
128               ptr->clearLowestBit();
129               break;
130            }
131            else
132               ptr->release();
133         }
134
135         return ptr;
136      }
137
138      /// Return the memory allocated to the given instance to the freelist.
139      void free( void* ptr )
140      {
141         AssertFatal( ptr, "ThreadSafeFreeList::free() - got a NULL pointer" );
142         T* node = ( T* ) ptr;
143
144         while( 1 )
145         {
146            T* list = mFreeList;
147            getNext( node ) = list;
148            if( dCompareAndSwap( mFreeList, list, node ) )
149               break;
150         }
151
152         #ifdef TORQUE_DEBUG
153         dFetchAndAdd( mNumNodesFree, 1 );
154         #endif
155      }
156
157      void dumpDebug()
158      {
159         #ifdef TORQUE_DEBUG
160         Platform::outputDebugString( "[ThreadSafeFreeList] total=%i, free=%i",
161            mNumNodesTotal, mNumNodesFree );
162         #endif
163      }
164};
165
166/// Baseclass for objects allocated from ThreadSafeFreeLists.
167template< class T, class DeletePolicy = DeleteSingle >
168class ThreadSafeFreeListNode : public ThreadSafeRefCount< T, DeletePolicy >
169{
170   public:
171
172      typedef ThreadSafeRefCount< T, DeletePolicy> Parent;
173
174      ThreadSafeFreeListNode()
175         : Parent( false ) {}
176
177      static void* operator new( size_t size, ThreadSafeFreeList< T>& freeList )
178      {
179         AssertFatal( size <= sizeof( T ),
180            "ThreadSafeFreeListNode::new() - size exceeds limit of freelist" );
181         TORQUE_UNUSED( size );
182         return freeList.alloc();
183      }
184      static void operator delete( void* ptr, ThreadSafeFreeList< T>& freeList )
185      {
186         freeList.free( ptr );
187      }
188};
189
190
191#include "platform/tmm_on.h"
192
193#endif // _THREADSAFEFREELIST_H_
194