1 /* ---------------------------------------------------------------------------
3 * (c) The GHC Team, 2000-2008
5 * Sparking support for PARALLEL_HASKELL and THREADED_RTS versions of the RTS.
7 -------------------------------------------------------------------------*/
9 #include "PosixSource.h"
20 #include "SMP.h" // for cas
24 #if defined(THREADED_RTS)
27 initSparkPools( void )
29 /* walk over the capabilities, allocating a spark pool for each one */
31 for (i = 0; i < n_capabilities; i++) {
32 capabilities[i].sparks = newWSDeque(RtsFlags.ParFlags.maxLocalSparks);
37 freeSparkPool (SparkPool *pool)
42 /* -----------------------------------------------------------------------------
44 * Turn a spark into a real thread
46 * -------------------------------------------------------------------------- */
49 createSparkThread (Capability *cap)
53 tso = createIOThread (cap, RtsFlags.GcFlags.initialStkSize,
54 &base_GHCziConc_runSparks_closure);
56 postEvent(cap, EVENT_CREATE_SPARK_THREAD, 0, tso->id);
58 appendToRunQueue(cap,tso);
61 /* --------------------------------------------------------------------------
62 * newSpark: create a new spark, as a result of calling "par"
63 * Called directly from STG.
64 * -------------------------------------------------------------------------- */
67 newSpark (StgRegTable *reg, StgClosure *p)
69 Capability *cap = regTableToCapability(reg);
70 SparkPool *pool = cap->sparks;
72 /* I am not sure whether this is the right thing to do.
73 * Maybe it is better to exploit the tag information
74 * instead of throwing it away?
78 if (closure_SHOULD_SPARK(p)) {
82 cap->sparks_created++;
84 postEvent(cap, EVENT_CREATE_SPARK, cap->r.rCurrentTSO->id, 0);
89 /* -----------------------------------------------------------------------------
91 * tryStealSpark: try to steal a spark from a Capability.
93 * Returns a valid spark, or NULL if the pool was empty, and can
94 * occasionally return NULL if there was a race with another thread
95 * stealing from the same pool. In this case, try again later.
97 -------------------------------------------------------------------------- */
100 tryStealSpark (Capability *cap)
102 SparkPool *pool = cap->sparks;
106 stolen = stealWSDeque_(pool);
107 // use the no-loopy version, stealWSDeque_(), since if we get a
108 // spurious NULL here the caller may want to try stealing from
109 // other pools before trying again.
110 } while (stolen != NULL && !closure_SHOULD_SPARK(stolen));
115 /* --------------------------------------------------------------------------
116 * Remove all sparks from the spark queues which should not spark any
117 * more. Called after GC. We assume exclusive access to the structure
118 * and replace all sparks in the queue, see explanation below. At exit,
119 * the spark pool only contains sparkable closures.
120 * -------------------------------------------------------------------------- */
123 pruneSparkQueue (evac_fn evac, void *user, Capability *cap)
126 StgClosurePtr spark, tmp, *elements;
127 nat n, pruned_sparks; // stats only
128 StgWord botInd,oldBotInd,currInd; // indices in array (always < size)
129 const StgInfoTable *info;
131 PAR_TICKY_MARK_SPARK_QUEUE_START();
138 // it is possible that top > bottom, indicating an empty pool. We
139 // fix that here; this is only necessary because the loop below
141 if (pool->top > pool->bottom)
142 pool->top = pool->bottom;
144 // Take this opportunity to reset top/bottom modulo the size of
145 // the array, to avoid overflow. This is only possible because no
146 // stealing is happening during GC.
147 pool->bottom -= pool->top & ~pool->moduloSize;
148 pool->top &= pool->moduloSize;
149 pool->topBound = pool->top;
151 debugTrace(DEBUG_sched,
152 "markSparkQueue: current spark queue len=%ld; (hd=%ld; tl=%ld)",
153 sparkPoolSize(pool), pool->bottom, pool->top);
155 ASSERT_WSDEQUE_INVARIANTS(pool);
157 elements = (StgClosurePtr *)pool->elements;
159 /* We have exclusive access to the structure here, so we can reset
160 bottom and top counters, and prune invalid sparks. Contents are
161 copied in-place if they are valuable, otherwise discarded. The
162 routine uses "real" indices t and b, starts by computing them
163 as the modulus size of top and bottom,
167 At the beginning, the pool structure can look like this:
168 ( bottom % size >= top % size , no wrap-around)
170 ___________***********_________________
172 or like this ( bottom % size < top % size, wrap-around )
174 ***********__________******************
175 As we need to remove useless sparks anyway, we make one pass
176 between t and b, moving valuable content to b and subsequent
177 cells (wrapping around when the size is reached).
180 ***********OOO_______XX_X__X?**********
183 After this movement, botInd becomes the new bottom, and old
184 bottom becomes the new top index, both as indices in the array
188 currInd = (pool->top) & (pool->moduloSize); // mod
190 // copies of evacuated closures go to space from botInd on
191 // we keep oldBotInd to know when to stop
192 oldBotInd = botInd = (pool->bottom) & (pool->moduloSize); // mod
194 // on entry to loop, we are within the bounds
195 ASSERT( currInd < pool->size && botInd < pool->size );
197 while (currInd != oldBotInd ) {
198 /* must use != here, wrap-around at size
199 subtle: loop not entered if queue empty
202 /* check element at currInd. if valuable, evacuate and move to
203 botInd, otherwise move on */
204 spark = elements[currInd];
206 // We have to be careful here: in the parallel GC, another
207 // thread might evacuate this closure while we're looking at it,
208 // so grab the info pointer just once.
209 info = spark->header.info;
210 if (IS_FORWARDING_PTR(info)) {
211 tmp = (StgClosure*)UN_FORWARDING_PTR(info);
212 /* if valuable work: shift inside the pool */
213 if (closure_SHOULD_SPARK(tmp)) {
214 elements[botInd] = tmp; // keep entry (new address)
218 pruned_sparks++; // discard spark
219 cap->sparks_pruned++;
222 if (!(closure_flags[INFO_PTR_TO_STRUCT(info)->type] & _NS)) {
223 elements[botInd] = spark; // keep entry (new address)
224 evac (user, &elements[botInd]);
228 pruned_sparks++; // discard spark
229 cap->sparks_pruned++;
234 // in the loop, we may reach the bounds, and instantly wrap around
235 ASSERT( currInd <= pool->size && botInd <= pool->size );
236 if ( currInd == pool->size ) { currInd = 0; }
237 if ( botInd == pool->size ) { botInd = 0; }
239 } // while-loop over spark pool elements
241 ASSERT(currInd == oldBotInd);
243 pool->top = oldBotInd; // where we started writing
244 pool->topBound = pool->top;
246 pool->bottom = (oldBotInd <= botInd) ? botInd : (botInd + pool->size);
247 // first free place we did not use (corrected by wraparound)
249 PAR_TICKY_MARK_SPARK_QUEUE_END(n);
251 debugTrace(DEBUG_sched, "pruned %d sparks", pruned_sparks);
253 debugTrace(DEBUG_sched,
254 "new spark queue len=%ld; (hd=%ld; tl=%ld)",
255 sparkPoolSize(pool), pool->bottom, pool->top);
257 ASSERT_WSDEQUE_INVARIANTS(pool);
260 /* GC for the spark pool, called inside Capability.c for all
261 capabilities in turn. Blindly "evac"s complete spark pool. */
263 traverseSparkQueue (evac_fn evac, void *user, Capability *cap)
267 StgWord top,bottom, modMask;
271 ASSERT_WSDEQUE_INVARIANTS(pool);
274 bottom = pool->bottom;
275 sparkp = (StgClosurePtr*)pool->elements;
276 modMask = pool->moduloSize;
278 while (top < bottom) {
279 /* call evac for all closures in range (wrap-around via modulo)
280 * In GHC-6.10, evac takes an additional 1st argument to hold a
281 * GC-specific register, see rts/sm/GC.c::mark_root()
283 evac( user , sparkp + (top & modMask) );
287 debugTrace(DEBUG_sched,
288 "traversed spark queue, len=%ld; (hd=%ld; tl=%ld)",
289 sparkPoolSize(pool), pool->bottom, pool->top);
292 /* ----------------------------------------------------------------------------
293 * balanceSparkPoolsCaps: takes an array of capabilities (usually: all
294 * capabilities) and its size. Accesses all spark pools and equally
295 * distributes the sparks among them.
297 * Could be called after GC, before Cap. release, from scheduler.
298 * -------------------------------------------------------------------------- */
299 void balanceSparkPoolsCaps(nat n_caps, Capability caps[]);
301 void balanceSparkPoolsCaps(nat n_caps STG_UNUSED,
302 Capability caps[] STG_UNUSED) {
303 barf("not implemented");
309 newSpark (StgRegTable *reg STG_UNUSED, StgClosure *p STG_UNUSED)
315 #endif /* THREADED_RTS */