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