1 /* ---------------------------------------------------------------------------
2 *
3 * (c) The GHC Team, 2000-2008
4 *
5 * Sparking support for THREADED_RTS version of the RTS.
6 *
7 -------------------------------------------------------------------------*/
8
9 #include "PosixSource.h"
10 #include "Rts.h"
11
12 #include "Schedule.h"
13 #include "RtsUtils.h"
14 #include "Trace.h"
15 #include "Prelude.h"
16 #include "Sparks.h"
17 #include "ThreadLabels.h"
18 #include "sm/NonMovingMark.h"
19 #include "sm/HeapAlloc.h"
20
21 #if defined(THREADED_RTS)
22
23 SparkPool *
allocSparkPool(void)24 allocSparkPool( void )
25 {
26 return newWSDeque(RtsFlags.ParFlags.maxLocalSparks);
27 }
28
29 void
freeSparkPool(SparkPool * pool)30 freeSparkPool (SparkPool *pool)
31 {
32 freeWSDeque(pool);
33 }
34
35 /* -----------------------------------------------------------------------------
36 *
37 * Turn a spark into a real thread
38 *
39 * -------------------------------------------------------------------------- */
40
41 void
createSparkThread(Capability * cap)42 createSparkThread (Capability *cap)
43 {
44 StgTSO *tso;
45
46 tso = createIOThread (cap, RtsFlags.GcFlags.initialStkSize,
47 (StgClosure *)runSparks_closure);
48 labelThread(cap, tso, "spark evaluator");
49 traceEventCreateSparkThread(cap, tso->id);
50
51 appendToRunQueue(cap,tso);
52 }
53
54 /* --------------------------------------------------------------------------
55 * newSpark: create a new spark, as a result of calling "par"
56 * Called directly from STG.
57 * -------------------------------------------------------------------------- */
58
59 StgInt
newSpark(StgRegTable * reg,StgClosure * p)60 newSpark (StgRegTable *reg, StgClosure *p)
61 {
62 Capability *cap = regTableToCapability(reg);
63 SparkPool *pool = cap->sparks;
64
65 if (!fizzledSpark(p)) {
66 if (pushWSDeque(pool,p)) {
67 cap->spark_stats.created++;
68 traceEventSparkCreate(cap);
69 } else {
70 /* overflowing the spark pool */
71 cap->spark_stats.overflowed++;
72 traceEventSparkOverflow(cap);
73 }
74 } else {
75 cap->spark_stats.dud++;
76 traceEventSparkDud(cap);
77 }
78
79 return 1;
80 }
81
82 /* --------------------------------------------------------------------------
83 * Remove all sparks from the spark queues which should not spark any
84 * more. Called after GC. We assume exclusive access to the structure
85 * and replace all sparks in the queue, see explanation below. At exit,
86 * the spark pool only contains sparkable closures.
87 * -------------------------------------------------------------------------- */
88
89 void
pruneSparkQueue(bool nonmovingMarkFinished,Capability * cap)90 pruneSparkQueue (bool nonmovingMarkFinished, Capability *cap)
91 {
92 SparkPool *pool;
93 StgClosurePtr spark, tmp, *elements;
94 uint32_t n, pruned_sparks; // stats only
95 StgInt botInd,oldBotInd,currInd; // indices in array (always < size)
96 const StgInfoTable *info;
97
98 n = 0;
99 pruned_sparks = 0;
100
101 pool = cap->sparks;
102
103 // it is possible that top > bottom, indicating an empty pool. We
104 // fix that here; this is only necessary because the loop below
105 // assumes it.
106 if (pool->top > pool->bottom)
107 pool->top = pool->bottom;
108
109 // Take this opportunity to reset top/bottom modulo the size of
110 // the array, to avoid overflow. This is only possible because no
111 // stealing is happening during GC.
112 pool->bottom -= pool->top & ~pool->moduloSize;
113 pool->top &= pool->moduloSize;
114
115 debugTrace(DEBUG_sparks,
116 "markSparkQueue: current spark queue len=%ld; (hd=%ld; tl=%ld)",
117 sparkPoolSize(pool), pool->bottom, pool->top);
118
119 ASSERT_WSDEQUE_INVARIANTS(pool);
120
121 elements = (StgClosurePtr *)pool->elements;
122
123 /* We have exclusive access to the structure here, so we can reset
124 bottom and top counters, and prune invalid sparks. Contents are
125 copied in-place if they are valuable, otherwise discarded. The
126 routine uses "real" indices t and b, starts by computing them
127 as the modulus size of top and bottom,
128
129 Copying:
130
131 At the beginning, the pool structure can look like this:
132 ( bottom % size >= top % size , no wrap-around)
133 t b
134 ___________***********_________________
135
136 or like this ( bottom % size < top % size, wrap-around )
137 b t
138 ***********__________******************
139 As we need to remove useless sparks anyway, we make one pass
140 between t and b, moving valuable content to b and subsequent
141 cells (wrapping around when the size is reached).
142
143 b t
144 ***********OOO_______XX_X__X?**********
145 ^____move?____/
146
147 After this movement, botInd becomes the new bottom, and old
148 bottom becomes the new top index, both as indices in the array
149 size range.
150 */
151 // starting here
152 currInd = (pool->top) & (pool->moduloSize); // mod
153
154 // copies of evacuated closures go to space from botInd on
155 // we keep oldBotInd to know when to stop
156 oldBotInd = botInd = (pool->bottom) & (pool->moduloSize); // mod
157
158 // on entry to loop, we are within the bounds
159 ASSERT( currInd < pool->size && botInd < pool->size );
160
161 while (currInd != oldBotInd ) {
162 /* must use != here, wrap-around at size
163 subtle: loop not entered if queue empty
164 */
165
166 /* check element at currInd. if valuable, evacuate and move to
167 botInd, otherwise move on */
168 spark = elements[currInd];
169
170 // We have to be careful here: in the parallel GC, another
171 // thread might evacuate this closure while we're looking at it,
172 // so grab the info pointer just once.
173 if (GET_CLOSURE_TAG(spark) != 0) {
174 // Tagged pointer is a value, so the spark has fizzled. It
175 // probably never happens that we get a tagged pointer in
176 // the spark pool, because we would have pruned the spark
177 // during the previous GC cycle if it turned out to be
178 // evaluated, but it doesn't hurt to have this check for
179 // robustness.
180 pruned_sparks++;
181 cap->spark_stats.fizzled++;
182 traceEventSparkFizzle(cap);
183 } else {
184 info = spark->header.info;
185 load_load_barrier();
186 if (IS_FORWARDING_PTR(info)) {
187 tmp = (StgClosure*)UN_FORWARDING_PTR(info);
188 /* if valuable work: shift inside the pool */
189 if (closure_SHOULD_SPARK(tmp)) {
190 elements[botInd] = tmp; // keep entry (new address)
191 botInd++;
192 n++;
193 } else {
194 pruned_sparks++; // discard spark
195 cap->spark_stats.fizzled++;
196 traceEventSparkFizzle(cap);
197 }
198 } else if (HEAP_ALLOCED(spark)) {
199 bdescr *spark_bd = Bdescr((P_) spark);
200 bool is_alive = false;
201 if (nonmovingMarkFinished) {
202 // See Note [Spark management under the nonmoving collector]
203 // in NonMoving.c.
204 // If we just concluded concurrent marking then we can rely
205 // on the mark bitmap to reflect whether sparks living in the
206 // non-moving heap have died.
207 if (spark_bd->flags & BF_NONMOVING) {
208 is_alive = nonmovingIsAlive(spark);
209 } else {
210 // The nonmoving collector doesn't collect anything
211 // outside of the non-moving heap.
212 is_alive = true;
213 }
214 } else if (spark_bd->flags & (BF_EVACUATED | BF_NONMOVING)) {
215 is_alive = true;
216 }
217
218 if (is_alive) {
219 if (closure_SHOULD_SPARK(spark)) {
220 elements[botInd] = spark; // keep entry (new address)
221 botInd++;
222 n++;
223 } else {
224 pruned_sparks++; // discard spark
225 cap->spark_stats.fizzled++;
226 traceEventSparkFizzle(cap);
227 }
228 } else {
229 pruned_sparks++; // discard spark
230 cap->spark_stats.gcd++;
231 traceEventSparkGC(cap);
232 }
233 } else {
234 if (INFO_PTR_TO_STRUCT(info)->type == THUNK_STATIC) {
235 // We can't tell whether a THUNK_STATIC is garbage or not.
236 // See also Note [STATIC_LINK fields]
237 // isAlive() also ignores static closures (see GCAux.c)
238 elements[botInd] = spark; // keep entry (new address)
239 botInd++;
240 n++;
241 } else {
242 pruned_sparks++; // discard spark
243 cap->spark_stats.fizzled++;
244 traceEventSparkFizzle(cap);
245 }
246 }
247 }
248
249 currInd++;
250
251 // in the loop, we may reach the bounds, and instantly wrap around
252 ASSERT( currInd <= pool->size && botInd <= pool->size );
253 if ( currInd == pool->size ) { currInd = 0; }
254 if ( botInd == pool->size ) { botInd = 0; }
255
256 } // while-loop over spark pool elements
257
258 ASSERT(currInd == oldBotInd);
259
260 pool->top = oldBotInd; // where we started writing
261
262 pool->bottom = (oldBotInd <= botInd) ? botInd : (botInd + pool->size);
263 // first free place we did not use (corrected by wraparound)
264
265 debugTrace(DEBUG_sparks, "pruned %d sparks", pruned_sparks);
266
267 debugTrace(DEBUG_sparks,
268 "new spark queue len=%ld; (hd=%ld; tl=%ld)",
269 sparkPoolSize(pool), pool->bottom, pool->top);
270
271 ASSERT_WSDEQUE_INVARIANTS(pool);
272 }
273
274 /* GC for the spark pool, called inside Capability.c for all
275 capabilities in turn. Blindly "evac"s complete spark pool. */
276 void
traverseSparkQueue(evac_fn evac,void * user,Capability * cap)277 traverseSparkQueue (evac_fn evac, void *user, Capability *cap)
278 {
279 StgClosure **sparkp;
280 SparkPool *pool;
281 StgWord top,bottom, modMask;
282
283 pool = cap->sparks;
284
285 ASSERT_WSDEQUE_INVARIANTS(pool);
286
287 top = pool->top;
288 bottom = pool->bottom;
289 sparkp = (StgClosurePtr*)pool->elements;
290 modMask = pool->moduloSize;
291
292 while (top < bottom) {
293 /* call evac for all closures in range (wrap-around via modulo)
294 * In GHC-6.10, evac takes an additional 1st argument to hold a
295 * GC-specific register, see rts/sm/GC.c::mark_root()
296 */
297 evac( user , sparkp + (top & modMask) );
298 top++;
299 }
300
301 debugTrace(DEBUG_sparks,
302 "traversed spark queue, len=%ld; (hd=%ld; tl=%ld)",
303 sparkPoolSize(pool), pool->bottom, pool->top);
304 }
305
306 #else
307
308 StgInt
newSpark(StgRegTable * reg STG_UNUSED,StgClosure * p STG_UNUSED)309 newSpark (StgRegTable *reg STG_UNUSED, StgClosure *p STG_UNUSED)
310 {
311 /* nothing */
312 return 1;
313 }
314
315 #endif /* THREADED_RTS */
316