threadSafeDeque.h
Engine/source/platform/threads/threadSafeDeque.h
Classes:
class
Fast, lock-free double-ended queue for concurrent access.
class
List node.
Detailed Description
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 _THREADSAFEDEQUE_H_ 25#define _THREADSAFEDEQUE_H_ 26 27#ifndef _THREADSAFEFREELIST_H_ 28# include "platform/threads/threadSafeFreeList.h" 29#endif 30 31#include "platform/tmm_off.h" 32 33 34/// Fast, lock-free double-ended queue for concurrent access. 35/// 36/// @param T Type of list elements; must have default contructor. 37template< typename T > 38class ThreadSafeDeque 39{ 40 // Lock-free deques using just single-word atomic writes are 41 // very tricky as each pointer update must immediately result 42 // in a fully valid list state. The idea here is to maintain the 43 // deque's head and tail pointers unreliably but otherwise keep a 44 // regular double-linked list (since we never insert nodes in the 45 // middle, single-word writes are all we need). 46 // 47 // Deletions are a bit less straightforward and require the threads 48 // to work cooperatively. Since failure of a pointer update depends 49 // on the deletion state, the deletion flag has to be encoded into 50 // the link fields. However, as there are two link fields this creates 51 // two independent deletion flags for each single node, one on the 52 // next link and one on the prev link. 53 // 54 // This will not lead to a problem, though, as it only becomes relevant 55 // when there is only a single value in the list which, even if the 56 // respective node gets both deleted and appended/prepended a new node, 57 // will result in a valid list state. 58 59 60 public: 61 62 typedef T ValueType; 63 64 protected: 65 66 class Node; 67 class DeleteNode; 68 typedef ThreadSafeRef< Node> NodeRef; 69 70 /// List node. 71 class Node : public ThreadSafeFreeListNode< Node, DeleteNode > 72 { 73 public: 74 75 friend class DeleteNode; // mFreeList; 76 typedef typename ThreadSafeDeque< T >::ValueType ValueType; 77 78 /// Thread claim flag. This is to prevent two threads who concurrently 79 /// do a tryPopFront() and tryPopBack() respectively on a deque with just 80 /// a single node to both claim and return the same value (which would happen 81 /// without the flag as otherwise both threads would use two different 82 /// deletion bits for claiming the node). 83 U32 mIsClaimed; 84 85 /// Link to the freelist that the node has been 86 /// allocated from. 87 ThreadSafeFreeList< Node>& mFreeList; 88 89 /// Value contained in the node. 90 ValueType mValue; 91 92 /// Reference to next node and deletion bit. 93 NodeRef mNext; 94 95 /// Reference to previous node and deletion bit. 96 NodeRef mPrev; 97 98 /// Construct an unlinked node allocated from "freeList". 99 Node( ThreadSafeFreeList< Node>& freeList, const ValueType& value ) 100 : mIsClaimed( 0 ), mFreeList( freeList ), mValue( value ) {} 101 }; 102 103 class DeleteNode 104 { 105 public: 106 template< typename N > 107 static void destroy( N* ptr ) 108 { 109 AssertFatal( ptr->mIsClaimed, 110 "ThreadSafeDeque::DeleteNode::destroy() - deleting unclaimed node" ); 111 destructInPlace( ptr ); 112 ptr->mFreeList.free( ptr ); 113 } 114 }; 115 116 #ifdef TORQUE_DEBUG 117 S32 mNumValues; 118 #endif 119 120 /// Reference to the head node. 121 NodeRef mHead; 122 123 /// 124 NodeRef mTail; 125 126 /// Free list for list nodes. 127 ThreadSafeFreeList< Node> mFreeList; 128 129 /// @return the leftmost node in the list. 130 /// @note Updates the list state and may purge deleted nodes. 131 NodeRef getHead(); 132 133 /// @return the rightmost node in the list. 134 /// @note Updates the list state and may purge deleted nodes. 135 NodeRef getTail(); 136 137 public: 138 139 /// Construct an empty deque. 140 ThreadSafeDeque() 141 { 142 #ifdef TORQUE_DEBUG 143 mNumValues = 0; 144 #endif 145 } 146 147 ~ThreadSafeDeque() 148 { 149 ValueType value; 150 while( tryPopFront( value ) ); 151 AssertFatal( isEmpty(), "ThreadSafeDeque::~ThreadSafeDeque() - not empty" ); 152 } 153 154 /// @return true if the queue is empty. 155 bool isEmpty() 156 { 157 return ( !getHead() && !getTail() ); 158 } 159 160 /// Prepend the given value to the list. 161 void pushFront( const ValueType& value ); 162 163 /// Append the given value to the list. 164 void pushBack( const ValueType& value ); 165 166 /// Try to take the leftmost value from the deque. 167 /// Fails if the deque is empty at the time the method tries to 168 /// take a node from the list. 169 bool tryPopFront( ValueType& outValue ); 170 171 /// Try to take the rightmost value from the deque. 172 /// Fails if the deque is empty at the time the method tries to 173 /// take a node from the list. 174 bool tryPopBack( ValueType& outValue ); 175 176 void dumpDebug() 177 { 178 #ifdef TORQUE_DEBUG 179 Platform::outputDebugString( "[ThreadSafeDeque] numValues=%i", mNumValues ); 180 mFreeList.dumpDebug(); 181 #endif 182 } 183}; 184 185// The getHead() and getTail() code here is pretty much brute-force in order 186// to keep the complexities of synchronizing it bounded. We just let each 187// thread work as if it is the only thread but require each one to start from 188// scratch on each iteration. 189 190template< typename T > 191typename ThreadSafeDeque< T >::NodeRef ThreadSafeDeque< T >::getHead() 192{ 193 // Find leftmost node. 194 195 NodeRef result; 196 while( 1 ) 197 { 198 // Iterate through to leftmost node. 199 200 { 201 NodeRef head = mHead; 202 while( head != NULL ) 203 { 204 NodeRef prev = head->mPrev; 205 if( prev != NULL ) 206 mHead.trySetFromTo( head, prev, NodeRef::TAG_Unset ); 207 else 208 break; 209 210 head = mHead; 211 } 212 } 213 214 // Clear out dead nodes at front of list. 215 216 { 217 NodeRef head = mHead; 218 if( head && head->mPrev.isTagged() ) 219 { 220 NodeRef next = head->mNext; 221 222 mHead.trySetFromTo( head, next, NodeRef::TAG_Unset ); 223 mTail.trySetFromTo( head, next, NodeRef::TAG_Unset ); 224 225 if( next != NULL ) 226 next->mPrev.trySetFromTo( head, NULL ); 227 228 head->mNext.trySetFromTo( next, NULL, NodeRef::TAG_Set ); 229 230 continue; // Restart. 231 } 232 } 233 234 // Try head. 235 236 NodeRef head = mHead; 237 if( head != NULL && !head->mPrev.isTagged() ) 238 { 239 result = head; 240 break; 241 } 242 243 // Try tail. 244 245 if( !head ) 246 { 247 head = mTail; 248 if( !head ) 249 break; 250 } 251 252 // Update head. 253 254 NodeRef prev = head->mPrev; 255 if( head->mPrev != NULL ) 256 { 257 if( !mHead.trySetFromTo( head, prev, NodeRef::TAG_Unset ) ) 258 mHead.trySetFromTo( NULL, prev ); 259 } 260 else 261 mHead.trySetFromTo( NULL, head ); 262 } 263 264 AssertFatal( !result.isTagged(), "ThreadSafeDeque::getHead() - head got tagged" ); 265 return result; 266} 267 268template< typename T > 269typename ThreadSafeDeque< T >::NodeRef ThreadSafeDeque< T >::getTail() 270{ 271 // Find rightmost node. 272 273 NodeRef result; 274 while( 1 ) 275 { 276 // Iterate through to rightmost node. 277 278 { 279 NodeRef tail = mTail; 280 while( tail != NULL ) 281 { 282 NodeRef next = tail->mNext; 283 if( next != NULL ) 284 mTail.trySetFromTo( tail, next, NodeRef::TAG_Unset ); 285 else 286 break; 287 288 tail = mTail; 289 } 290 } 291 292 // Clear out dead nodes at tail of list. 293 294 { 295 NodeRef tail = mTail; 296 if( tail != NULL && tail->mNext.isTagged() ) 297 { 298 NodeRef prev = tail->mPrev; 299 300 mHead.trySetFromTo( tail, prev, NodeRef::TAG_Unset ); 301 mTail.trySetFromTo( tail, prev, NodeRef::TAG_Unset ); 302 303 if( prev != NULL ) 304 prev->mNext.trySetFromTo( tail, NULL ); 305 306 tail->mPrev.trySetFromTo( prev, NULL, NodeRef::TAG_Set ); 307 308 continue; // Restart. 309 } 310 } 311 312 // Try tail. 313 314 NodeRef tail = mTail; 315 if( tail != NULL && !tail->mNext.isTagged() ) 316 { 317 result = tail; 318 break; 319 } 320 321 // Try head. 322 323 if( !tail ) 324 { 325 tail = mHead; 326 if( !tail ) 327 break; 328 } 329 330 // Update tail. 331 332 NodeRef next = tail->mNext; 333 if( next != NULL ) 334 { 335 if( !mTail.trySetFromTo( tail, next, NodeRef::TAG_Unset ) ) 336 mTail.trySetFromTo( NULL, next ); 337 } 338 else 339 mTail.trySetFromTo( NULL, tail ); 340 } 341 342 AssertFatal( !result.isTagged(), "ThreadSafeDeque::getTail() - tail got tagged" ); 343 return result; 344} 345 346template< typename T > 347void ThreadSafeDeque< T >::pushFront( const ValueType& value ) 348{ 349 NodeRef nextNode; 350 NodeRef newNode; 351 352 NodeRef::unsafeWrite( newNode, new ( mFreeList ) Node( mFreeList, value ) ); 353 354 while( 1 ) 355 { 356 nextNode = getHead(); 357 if( !nextNode ) 358 { 359 newNode->mNext = NULL; 360 if( mHead.trySetFromTo( NULL, newNode ) ) 361 break; 362 } 363 else 364 { 365 newNode->mNext = nextNode; 366 if( nextNode->mPrev.trySetFromTo( NULL, newNode, NodeRef::TAG_FailIfSet ) ) 367 break; 368 } 369 } 370 371#ifdef TORQUE_DEBUG 372 dFetchAndAdd( mNumValues, 1 ); 373#endif 374} 375 376template< typename T > 377void ThreadSafeDeque< T >::pushBack( const ValueType& value ) 378{ 379 NodeRef prevNode; 380 NodeRef newNode; 381 382 NodeRef::unsafeWrite( newNode, new ( mFreeList ) Node( mFreeList, value ) ); 383 384 while( 1 ) 385 { 386 prevNode = getTail(); 387 if( !prevNode ) 388 { 389 newNode->mPrev = NULL; 390 if( mHead.trySetFromTo( NULL, newNode ) ) // use head so we synchronize with pushFront 391 break; 392 } 393 else 394 { 395 newNode->mPrev = prevNode; 396 if( prevNode->mNext.trySetFromTo( NULL, newNode, NodeRef::TAG_FailIfSet ) ) 397 break; 398 } 399 } 400 401#ifdef TORQUE_DEBUG 402 dFetchAndAdd( mNumValues, 1 ); 403#endif 404} 405 406template< typename T > 407bool ThreadSafeDeque< T >::tryPopFront( ValueType& outValue ) 408{ 409 NodeRef oldHead; 410 411 while( 1 ) 412 { 413 oldHead = getHead(); 414 if( !oldHead ) 415 return false; 416 417 // Try to claim the node. 418 419 if( oldHead->mPrev.trySetFromTo( NULL, NULL, NodeRef::TAG_SetOrFail ) ) 420 { 421 if( dCompareAndSwap( oldHead->mIsClaimed, 0, 1 ) ) 422 break; 423 else 424 continue; 425 } 426 } 427 428 outValue = oldHead->mValue; 429 oldHead = NULL; 430 431 // Cleanup. 432 getHead(); 433 434#ifdef TORQUE_DEBUG 435 dFetchAndAdd( mNumValues, -1 ); 436#endif 437 return true; 438} 439 440template< typename T > 441bool ThreadSafeDeque< T >::tryPopBack( ValueType& outValue ) 442{ 443 NodeRef oldTail; 444 445 while( 1 ) 446 { 447 oldTail = getTail(); 448 if( !oldTail ) 449 return false; 450 451 // Try to claim the node. 452 453 if( oldTail->mNext.trySetFromTo( NULL, NULL, NodeRef::TAG_SetOrFail ) ) 454 { 455 if( dCompareAndSwap( oldTail->mIsClaimed, 0, 1 ) ) 456 break; 457 } 458 } 459 460 outValue = oldTail->mValue; 461 oldTail = NULL; 462 463 // Cleanup. 464 getTail(); 465 466#ifdef TORQUE_DEBUG 467 dFetchAndAdd( mNumValues, -1 ); 468#endif 469 return true; 470} 471 472 473#include "platform/tmm_on.h" 474 475#endif // _THREADSAFEDEQUE_H_ 476