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