threadSafeRefCount.h

  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 _THREADSAFEREFCOUNT_H_
 25#define _THREADSAFEREFCOUNT_H_
 26
 27#ifndef _PLATFORMINTRINSICS_H_
 28#  include "platform/platformIntrinsics.h"
 29#endif
 30#ifndef _TYPETRAITS_H_
 31#  include "platform/typetraits.h"
 32#endif
 33
 34
 35/// @file
 36/// Templated code for concurrent reference-counting.
 37///
 38/// Part of this code is based on work by J.D. Valois, Michael M. Maged,
 39/// and Scott L. Michael.
 40
 41
 42//--------------------------------------------------------------------------
 43//    ThreadSafeRefCount.
 44//--------------------------------------------------------------------------
 45
 46/// Baseclass for concurrently reference-counted objects.
 47///
 48/// @note NOTE that freshly instantiated objects start out with a reference
 49///    count of ZERO!  Depending on how this class is used, this may not
 50///    be desirable, so override this behavior in constructors if necessary.
 51///
 52/// @param T the class being reference counted; this is passed to this class,
 53///    so it can call the correct destructor without having to force users
 54///    to have virtual methods
 55
 56template< class T, class DeletePolicy = DeleteSingle >
 57class ThreadSafeRefCount
 58{
 59   public:
 60
 61      typedef void Parent;
 62
 63      ThreadSafeRefCount()
 64         : mRefCount( 0 ) {}
 65      ThreadSafeRefCount( bool noSet ) {}
 66
 67      bool           isShared() const;
 68      U32            getRefCount() const;
 69      void           addRef();
 70      void           release();
 71      void           clearLowestBit();
 72      static T*      safeRead( T* const volatile& refPtr );
 73
 74   protected:
 75
 76      U32            mRefCount;  ///< Reference count and claim bit.  Note that this increments in steps of two.
 77
 78      static U32     decrementAndTestAndSet( U32& refCount );
 79};
 80
 81/// @return true if the object is referenced by more than a single
 82///   reference.
 83
 84template< class T, class DeletePolicy >
 85inline bool ThreadSafeRefCount< T, DeletePolicy >::isShared() const
 86{
 87   return ( mRefCount > 3 );
 88}
 89
 90/// Get the current reference count.  This method is mostly meant for
 91/// debugging and should not normally be used.
 92
 93template< class T, class DeletePolicy >
 94inline U32 ThreadSafeRefCount< T, DeletePolicy >::getRefCount() const
 95{
 96   return mRefCount;
 97}
 98
 99/// Increase the reference count on the object.
100
101template< class T, class DeletePolicy >
102inline void ThreadSafeRefCount< T, DeletePolicy >::addRef()
103{
104   dFetchAndAdd( mRefCount, 2 );
105}
106
107/// Decrease the object's reference count and delete the object, if the count
108/// drops to zero and claiming the object by the current thread succeeds.
109
110template< class T, class DeletePolicy >
111inline void ThreadSafeRefCount< T, DeletePolicy >::release()
112{
113   AssertFatal( mRefCount != 0, "ThreadSafeRefCount::release() - refcount of zero" );
114   if( decrementAndTestAndSet( mRefCount ) != 0 )
115      DeletePolicy::destroy( ( T* ) this );
116}
117
118/// Dereference a reference-counted pointer in a multi-thread safe way.
119
120template< class T, class DeletePolicy >
121T* ThreadSafeRefCount< T, DeletePolicy >::safeRead( T* const volatile& refPtr )
122{
123   while( 1 )
124   {
125      // Support tagged pointers here.
126
127      T* ptr = TypeTraits< T* >::getUntaggedPtr( refPtr );
128      if( !ptr )
129         return 0;
130
131      ptr->addRef();
132      if( ptr == TypeTraits< T* >::getUntaggedPtr( refPtr ) )
133         return ptr;
134      else
135         ptr->release();
136   }
137}
138
139/// Decrement the given reference count.  Return 1 if the count dropped to zero
140/// and the claim bit has been successfully set; return 0 otherwise.
141
142template< class T, class DeletePolicy >
143U32 ThreadSafeRefCount< T, DeletePolicy >::decrementAndTestAndSet( U32& refCount )
144{
145   U32 oldVal;
146   U32 newVal;
147
148   do
149   {
150      oldVal = refCount;
151      newVal = oldVal - 2;
152
153      AssertFatal( oldVal >= 2,
154         "ThreadSafeRefCount::decrementAndTestAndSet() - invalid refcount" );
155
156      if( newVal == 0 )
157         newVal = 1;
158   }
159   while( !dCompareAndSwap( refCount, oldVal, newVal ) );
160
161   return ( ( oldVal - newVal ) & 1 );
162}
163
164///
165
166template< class T, class DeletePolicy >
167inline void ThreadSafeRefCount< T, DeletePolicy >::clearLowestBit()
168{
169   AssertFatal( mRefCount % 2 != 0, "ThreadSafeRefCount::clearLowestBit() - invalid refcount" );
170
171   U32 oldVal;
172   U32 newVal;
173
174   do
175   {
176      oldVal = mRefCount;
177      newVal = oldVal - 1;
178   }
179   while( !dCompareAndSwap( mRefCount, oldVal, newVal ) );
180}
181
182//--------------------------------------------------------------------------
183//    ThreadSafeRef.
184//--------------------------------------------------------------------------
185
186/// Reference to a concurrently reference-counted object.
187///
188/// This class takes care of the reference-counting as well as protecting
189/// the reference itself from concurrent operations.
190///
191/// Tagging allows the pointer contained in the reference to be flagged.
192/// Tag state is preserved through updates to the reference.
193///
194/// @note If you directly assign a freshly created object with a reference
195///   count of zero to a ThreadSafeRef, make absolutely sure the ThreadSafeRef
196///   is accessed only by a single thread.  Otherwise there's a risk of the
197///   object being released and freed in midst of trying to set the reference.
198template< class T >
199class ThreadSafeRef
200{
201   public:
202
203      enum ETag
204      {
205         TAG_PreserveOld,  ///< Preserve existing tagging state when changing pointer.
206         TAG_PreserveNew,  ///< Preserve tagging state of new pointer when changing pointer.
207         TAG_Set,          ///< Set tag when changing pointer; okay if already set.
208         TAG_Unset,        ///< Unset tag when changing pointer; okay if already unset.
209         TAG_SetOrFail,    ///< Set tag when changing pointer; fail if already set.
210         TAG_UnsetOrFail,  ///< Unset tag when changing pointer; fail if already unset.
211         TAG_FailIfSet,    ///< Fail changing pointer when currently tagged.
212         TAG_FailIfUnset   ///< Fail changing pointer when currently untagged.
213      };
214
215      typedef ThreadSafeRef< T> ThisType;
216
217      ThreadSafeRef()                        : mPtr( 0 ) {}
218      ThreadSafeRef( T* ptr )                : mPtr( ThreadSafeRefCount< T >::safeRead( ptr ) ) {}
219      ThreadSafeRef( const ThisType& ref )   : mPtr( ThreadSafeRefCount< T >::safeRead( ref.mPtr ) ) {}
220      ~ThreadSafeRef()
221      {
222         T* ptr = NULL;
223         while( !trySetFromTo( mPtr, ptr ) );
224      }
225
226      T*             ptr() const { return getUntaggedPtr( mPtr ) ; }
227      void           setTag() { while( !trySetFromTo( mPtr, mPtr, TAG_Set ) ); }
228      bool           isTagged() const { return isTaggedPtr( mPtr ); }
229      bool           trySetFromTo( T* oldVal, T* const volatile& newVal, ETag tag = TAG_PreserveOld );
230      bool           trySetFromTo( T* oldVal, const ThisType& newVal, ETag tag = TAG_PreserveOld );
231      bool           trySetFromTo( const ThisType& oldVal, const ThisType& newVal, ETag tag = TAG_PreserveOld );
232      static void    unsafeWrite( ThisType& ref, T* ptr );
233      static T*      safeRead( T* const volatile& refPtr ) { return ThreadSafeRefCount< T >::safeRead( refPtr ); }
234
235      bool           operator==( T* ptr ) const;
236      bool           operator==( const ThisType& ref ) const;
237      bool           operator!=( T* ptr ) const { return !( *this == ptr ); }
238      bool           operator!=( const ThisType& ref ) const { return !( *this == ref ); }
239      ThisType&      operator=( T* ptr );
240      ThisType&      operator=( const ThisType& ref );
241
242      bool           operator!() const   { return ( ptr() == 0 ); }
243      T&             operator*() const   { return *ptr(); }
244      T*             operator->() const  { return ptr(); }
245                     operator T*() const  { return ptr(); }
246
247   protected:
248
249      T* volatile    mPtr;
250
251      static bool isTaggedPtr( T* ptr ) { return TypeTraits< T* >::isTaggedPtr( ptr ); }
252      static T* getTaggedPtr( T* ptr ) { return TypeTraits< T* >::getTaggedPtr( ptr ); }
253      static T* getUntaggedPtr( T* ptr ) { return TypeTraits< T* >::getUntaggedPtr( ptr ); }
254};
255
256/// Update the reference from pointing to oldVal to point to newVal.
257/// Do so in a thread-safe way.
258///
259/// This operation will only succeed, if, when doing the pointer-swapping,
260/// the reference still points to oldVal.  If, however, the reference
261/// has been changed in the meantime by another thread, the operation will
262/// fail.
263///
264/// @param oldVal The pointer assumed to currently be contained in this ThreadSafeRef.
265/// @param newVal The pointer to store in this ThreadSafeRef.
266/// @param tag Operation to perform on the reference's tag field.
267///
268/// @return true, if the reference now points to newVal.
269
270template< class T >
271bool ThreadSafeRef< T >::trySetFromTo( T* oldVal, T* const volatile& newVal, ETag tag )
272{
273   bool setTag = false;
274   bool getTag = false;
275   bool isTagged = isTaggedPtr( oldVal );
276
277   switch( tag )
278   {
279   case TAG_PreserveOld:   setTag = isTaggedPtr( oldVal ); break;
280   case TAG_PreserveNew:   setTag = isTaggedPtr( newVal ); break;
281   case TAG_Set:           setTag = true; break;
282   case TAG_Unset:         setTag = false; break;
283   case TAG_SetOrFail:     setTag = true; getTag = true; break;
284   case TAG_UnsetOrFail:   setTag = false; getTag = true; break;
285   case TAG_FailIfSet:     if( isTagged ) return false; break;
286   case TAG_FailIfUnset:   if( !isTagged ) return false; break;
287   }
288
289   T* newValPtr = ( setTag
290                    ? getTaggedPtr( ThreadSafeRefCount< T >::safeRead( newVal ) )
291                    : getUntaggedPtr( ThreadSafeRefCount< T >::safeRead( newVal ) ) );
292
293   if( dCompareAndSwap( mPtr,
294                        ( getTag
295                          ? ( setTag
296                              ? getUntaggedPtr( oldVal )
297                              : getTaggedPtr( oldVal ) )
298                          : oldVal ),
299                        newValPtr ) )
300   {
301      if( getUntaggedPtr( oldVal ) )
302         getUntaggedPtr( oldVal )->release();
303      return true;
304   }
305   else
306   {
307      if( getUntaggedPtr( newValPtr ) )
308         getUntaggedPtr( newValPtr )->release();
309      return false;
310   }
311}
312
313template< class T >
314inline bool ThreadSafeRef< T >::trySetFromTo( T* oldVal, const ThisType& newVal, ETag tag )
315{
316   return trySetFromTo( oldVal, newVal.mPtr, tag );
317}
318
319template< class T >
320inline bool ThreadSafeRef< T >::trySetFromTo( const ThisType& oldVal, const ThisType& newVal, ETag tag )
321{
322   return trySetFromTo( oldVal.mPtr, newVal.mPtr, tag );
323}
324
325/// Update ref to point to ptr but <em>do not</em> release an existing
326/// reference held by ref nor do the operation in a thread-safe way.
327///
328/// This method is <em>only</em> for when you absolutely know that your
329/// thread is the only thread operating on a reference <em>and</em> you
330/// are keeping track of reference counts yourself.
331///
332/// @param ref The reference to update.
333/// @param ptr The new pointer to store in ref.
334
335template< class T >
336inline void ThreadSafeRef< T >::unsafeWrite( ThisType& ref, T* ptr )
337{
338   ref.mPtr = ptr;
339}
340
341template< class T >
342inline bool ThreadSafeRef< T >::operator==( T* p ) const
343{
344   return ( ptr() == p );
345}
346
347template< class T >
348inline bool ThreadSafeRef< T >::operator==( const ThisType& ref ) const
349{
350   return ( ptr() == ref.ptr() );
351}
352
353template< class T >
354inline ThreadSafeRef< T>& ThreadSafeRef< T >::operator=( T* ptr )
355{
356   while( !trySetFromTo( mPtr, ptr, TAG_PreserveNew ) );
357   return *this;
358}
359
360template< class T >
361inline ThreadSafeRef< T>& ThreadSafeRef< T >::operator=( const ThisType& ref )
362{
363   while( !trySetFromTo( mPtr, ref, TAG_PreserveNew ) );
364   return *this;
365}
366
367
368template< typename T >
369struct TypeTraits< ThreadSafeRef< T > > : public TypeTraits< T* > {};
370template< typename T >
371inline T& Deref( ThreadSafeRef< T>& ref )
372{
373   return *ref;
374}
375template< typename T >
376inline T& Deref( const ThreadSafeRef< T>& ref )
377{
378   return *ref;
379}
380
381#endif // _THREADSAFEREFCOUNT_H_
382