rts/parallel/WSDeque.h

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team, 2009
   4  *
   5  * Work-stealing Deque data structure
   6  *
   7  * ---------------------------------------------------------------------------*/
   8
   9 #ifndef WSDEQUE_H
  10 #define WSDEQUE_H
  11
  12 #if defined(THREADED_RTS)
  13
  14 typedef struct WSDeque_ {
  15     // Size of elements array. Used for modulo calculation: we round up
  16     // to powers of 2 and use the dyadic log (modulo == bitwise &)
  17     StgWord size;
  18     StgWord moduloSize; /* bitmask for modulo */
  19
  20     // top, index where multiple readers steal() (protected by a cas)
  21     volatile StgWord top;
  22
  23     // bottom, index of next free place where one writer can push
  24     // elements. This happens unsynchronised.
  25     volatile StgWord bottom;
  26
  27     // both top and bottom are continuously incremented, and used as
  28     // an index modulo the current array size.
  29
  30     // lower bound on the current top value. This is an internal
  31     // optimisation to avoid unnecessarily accessing the top field
  32     // inside pushBottom
  33     volatile StgWord topBound;
  34
  35     // The elements array
  36     void ** elements;
  37
  38     //  Please note: the dataspace cannot follow the admin fields
  39     //  immediately, as it should be possible to enlarge it without
  40     //  disposing the old one automatically (as realloc would)!
  41
  42 } WSDeque;
  43
  44 /* INVARIANTS, in this order: reasonable size,
  45    topBound consistent, space pointer, space accessible to us.
  46
  47    NB. This is safe to use only (a) on a spark pool owned by the
  48    current thread, or (b) when there's only one thread running, or no
  49    stealing going on (e.g. during GC).
  50 */
  51 #define ASSERT_WSDEQUE_INVARIANTS(p)         \
  52   ASSERT((p)->size > 0);                        \
  53   ASSERT((p)->topBound <= (p)->top);            \
  54   ASSERT((p)->elements != NULL);                \
  55   ASSERT(*((p)->elements) || 1);                \
  56   ASSERT(*((p)->elements - 1  + ((p)->size)) || 1);
  57
  58 // No: it is possible that top > bottom when using pop()
  59 //  ASSERT((p)->bottom >= (p)->top);
  60 //  ASSERT((p)->size > (p)->bottom - (p)->top);
  61
  62 /* -----------------------------------------------------------------------------
  63  * Operations
  64  *
  65  * A WSDeque has an *owner* thread.  The owner can perform any operation;
  66  * other threads are only allowed to call stealWSDeque_(),
  67  * stealWSDeque(), looksEmptyWSDeque(), and dequeElements().
  68  *
  69  * -------------------------------------------------------------------------- */
  70
  71 // Allocation, deallocation
  72 WSDeque * newWSDeque  (nat size);
  73 void      freeWSDeque (WSDeque *q);
  74
  75 // Take an element from the "write" end of the pool.  Can be called
  76 // by the pool owner only.
  77 void* popWSDeque (WSDeque *q);
  78
  79 // Push onto the "write" end of the pool.  Return true if the push
  80 // succeeded, or false if the deque is full.
  81 rtsBool pushWSDeque (WSDeque *q, void *elem);
  82
  83 // Removes all elements from the deque
  84 INLINE_HEADER void discardElements (WSDeque *q);
  85
  86 // Removes an element of the deque from the "read" end, or returns
  87 // NULL if the pool is empty, or if there was a collision with another
  88 // thief.
  89 void * stealWSDeque_ (WSDeque *q);
  90
  91 // Removes an element of the deque from the "read" end, or returns
  92 // NULL if the pool is empty.
  93 void * stealWSDeque (WSDeque *q);
  94
  95 // "guesses" whether a deque is empty. Can return false negatives in
  96 //  presence of concurrent steal() calls, and false positives in
  97 //  presence of a concurrent pushBottom().
  98 INLINE_HEADER rtsBool looksEmptyWSDeque (WSDeque* q);
  99
 100 INLINE_HEADER long dequeElements   (WSDeque *q);
 101
 102 /* -----------------------------------------------------------------------------
 103  * PRIVATE below here
 104  * -------------------------------------------------------------------------- */
 105
 106 INLINE_HEADER long
 107 dequeElements (WSDeque *q)
 108 {
 109     StgWord t = q->top;
 110     StgWord b = q->bottom;
 111     // try to prefer false negatives by reading top first
 112     return ((long)b - (long)t);
 113 }
 114
 115 INLINE_HEADER rtsBool
 116 looksEmptyWSDeque (WSDeque *q)
 117 {
 118     return (dequeElements(q) <= 0);
 119 }
 120
 121 INLINE_HEADER void
 122 discardElements (WSDeque *q)
 123 {
 124     q->top = q->bottom;
 125 //    pool->topBound = pool->top;
 126 }
 127
 128 #endif // THREADED_RTS
 129
 130 #endif // WSDEQUE_H