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