diff options
| -rw-r--r-- | rts/WSDeque.c | 88 |
1 files changed, 44 insertions, 44 deletions
diff --git a/rts/WSDeque.c b/rts/WSDeque.c index 8efd1bbe48..19f2866c08 100644 --- a/rts/WSDeque.c +++ b/rts/WSDeque.c @@ -3,7 +3,7 @@ * (c) The GHC Team, 2009 * * Work-stealing Deque data structure - * + * * The implementation uses Double-Ended Queues with lock-free access * (thereby often called "deque") as described in * @@ -18,24 +18,24 @@ * array is accessed with indices modulo array-size. While this bears * the risk of overflow, we assume that (with 64 bit indices), a * program must run very long to reach that point. - * + * * The write end of the queue (position bottom) can only be used with * mutual exclusion, i.e. by exactly one caller at a time. At this * end, new items can be enqueued using pushBottom()/newSpark(), and * removed using popBottom()/reclaimSpark() (the latter implying a cas * synchronisation with potential concurrent readers for the case of * just one element). - * + * * Multiple readers can steal from the read end (position top), and * are synchronised without a lock, based on a cas of the top * position. One reader wins, the others return NULL for a failure. - * + * * Both popWSDeque and stealWSDeque also return NULL when the queue is empty. * * Testing: see testsuite/tests/rts/testwsdeque.c. If * there's anything wrong with the deque implementation, this test * will probably catch it. - * + * * ---------------------------------------------------------------------------*/ #include "PosixSource.h" @@ -56,7 +56,7 @@ static StgWord roundUp2(StgWord val) { StgWord rounded = 1; - + /* StgWord is unsigned anyway, only catch 0 */ if (val == 0) { barf("DeQue,roundUp2: invalid size 0 requested"); @@ -71,11 +71,11 @@ roundUp2(StgWord val) WSDeque * newWSDeque (nat size) { - StgWord realsize; + StgWord realsize; WSDeque *q; - + realsize = roundUp2(size); /* to compute modulo as a bitwise & */ - + q = (WSDeque*) stgMallocBytes(sizeof(WSDeque), /* admin fields */ "newWSDeque"); q->elements = stgMallocBytes(realsize * sizeof(StgClosurePtr), /* dataspace */ @@ -83,11 +83,11 @@ newWSDeque (nat size) q->top=0; q->bottom=0; q->topBound=0; /* read by writer, updated each time top is read */ - + q->size = realsize; /* power of 2 */ q->moduloSize = realsize - 1; /* n % size == n & moduloSize */ - - ASSERT_WSDEQUE_INVARIANTS(q); + + ASSERT_WSDEQUE_INVARIANTS(q); return q; } @@ -103,7 +103,7 @@ freeWSDeque (WSDeque *q) } /* ----------------------------------------------------------------------------- - * + * * popWSDeque: remove an element from the write end of the queue. * Returns the removed spark, and NULL if a race is lost or the pool * empty. @@ -123,9 +123,9 @@ popWSDeque (WSDeque *q) StgWord t, b; long currSize; void * removed; - - ASSERT_WSDEQUE_INVARIANTS(q); - + + ASSERT_WSDEQUE_INVARIANTS(q); + b = q->bottom; // "decrement b as a test, see what happens" @@ -153,7 +153,7 @@ popWSDeque (WSDeque *q) if (currSize > 0) { /* no danger, still elements in buffer after b-- */ // debugBelch("popWSDeque: t=%ld b=%ld = %ld\n", t, b, removed); return removed; - } + } /* otherwise, has someone meanwhile stolen the same (last) element? Check and increment top value to know */ if ( !(CASTOP(&(q->top),t,t+1)) ) { @@ -161,10 +161,10 @@ popWSDeque (WSDeque *q) } q->bottom = t+1; /* anyway, empty now. Adjust bottom consistently. */ q->topBound = t+1; /* ...and cached top value as well */ - - ASSERT_WSDEQUE_INVARIANTS(q); + + ASSERT_WSDEQUE_INVARIANTS(q); ASSERT(q->bottom >= q->top); - + // debugBelch("popWSDeque: t=%ld b=%ld = %ld\n", t, b, removed); return removed; @@ -178,27 +178,27 @@ void * stealWSDeque_ (WSDeque *q) { void * stolen; - StgWord b,t; - + StgWord b,t; + // Can't do this on someone else's spark pool: -// ASSERT_WSDEQUE_INVARIANTS(q); - +// ASSERT_WSDEQUE_INVARIANTS(q); + // NB. these loads must be ordered, otherwise there is a race // between steal and pop. t = q->top; load_load_barrier(); b = q->bottom; - + // NB. b and t are unsigned; we need a signed value for the test // below, because it is possible that t > b during a // concurrent popWSQueue() operation. - if ((long)b - (long)t <= 0 ) { + if ((long)b - (long)t <= 0 ) { return NULL; /* already looks empty, abort */ } - + /* now access array, see pushBottom() */ stolen = q->elements[t & q->moduloSize]; - + /* now decide whether we have won */ if ( !(CASTOP(&(q->top),t,t+1)) ) { /* lost the race, someon else has changed top in the meantime */ @@ -208,8 +208,8 @@ stealWSDeque_ (WSDeque *q) // debugBelch("stealWSDeque_: t=%d b=%d\n", t, b); // Can't do this on someone else's spark pool: -// ASSERT_WSDEQUE_INVARIANTS(q); - +// ASSERT_WSDEQUE_INVARIANTS(q); + return stolen; } @@ -217,11 +217,11 @@ void * stealWSDeque (WSDeque *q) { void *stolen; - - do { + + do { stolen = stealWSDeque_(q); } while (stolen == NULL && !looksEmptyWSDeque(q)); - + return stolen; } @@ -238,17 +238,17 @@ pushWSDeque (WSDeque* q, void * elem) { StgWord t; StgWord b; - StgWord sz = q->moduloSize; - - ASSERT_WSDEQUE_INVARIANTS(q); - + StgWord sz = q->moduloSize; + + ASSERT_WSDEQUE_INVARIANTS(q); + /* we try to avoid reading q->top (accessed by all) and use - q->topBound (accessed only by writer) instead. + q->topBound (accessed only by writer) instead. This is why we do not just call empty(q) here. */ b = q->bottom; t = q->topBound; - if ( (StgInt)b - (StgInt)t >= (StgInt)sz ) { + if ( (StgInt)b - (StgInt)t >= (StgInt)sz ) { /* NB. 1. sz == q->size - 1, thus ">=" 2. signed comparison, it is possible that t > b */ @@ -260,20 +260,20 @@ pushWSDeque (WSDeque* q, void * elem) will in the meantime use the old one and modify only top. This means: we cannot safely free the old space! Can keep it on a free list internally here... - + Potential bug in combination with steal(): if array is replaced, it is unclear which one concurrent steal operations use. Must read the array base address in advance in steal(). */ #if defined(DISCARD_NEW) - ASSERT_WSDEQUE_INVARIANTS(q); + ASSERT_WSDEQUE_INVARIANTS(q); return rtsFalse; // we didn't push anything #else /* could make room by incrementing the top position here. In * this case, should use CASTOP. If this fails, someone else has * removed something, and new room will be available. */ - ASSERT_WSDEQUE_INVARIANTS(q); + ASSERT_WSDEQUE_INVARIANTS(q); #endif } } @@ -289,7 +289,7 @@ pushWSDeque (WSDeque* q, void * elem) */ write_barrier(); q->bottom = b + 1; - - ASSERT_WSDEQUE_INVARIANTS(q); + + ASSERT_WSDEQUE_INVARIANTS(q); return rtsTrue; } |