size = p - q;
if (free + size > free_bd->start + BLOCK_SIZE_W) {
- // unset the next bit in the bitmap to indicate that
+ // set the next bit in the bitmap to indicate that
// this object needs to be pushed into the next
// block. This saves us having to run down the
// threaded info pointer list twice during the next pass.
- unmark(q+1,bd);
+ mark(q+1,bd);
free_bd = free_bd->link;
free = free_bd->start;
} else {
- ASSERT(is_marked(q+1,bd));
+ ASSERT(!is_marked(q+1,bd));
}
unthread(q,(StgWord)free + GET_CLOSURE_TAG((StgClosure *)iptr));
}
#endif
- if (!is_marked(p+1,bd)) {
+ if (is_marked(p+1,bd)) {
// don't forget to update the free ptr in the block desc.
free_bd->free = free;
free_bd = free_bd->link;
BEGIN_RTS_PRIVATE
-INLINE_HEADER rtsBool
-mark_stack_empty(void)
-{
- return mark_sp == mark_stack;
-}
-
-INLINE_HEADER rtsBool
-mark_stack_full(void)
-{
- return mark_sp >= mark_splim;
-}
-
-INLINE_HEADER void
-reset_mark_stack(void)
-{
- mark_sp = mark_stack;
-}
-
-INLINE_HEADER void
-push_mark_stack(StgPtr p)
-{
- *mark_sp++ = p;
-}
-
-INLINE_HEADER StgPtr
-pop_mark_stack(void)
-{
- return *--mark_sp;
-}
-
INLINE_HEADER void
mark(StgPtr p, bdescr *bd)
{
#include "GCThread.h"
#include "GCUtils.h"
#include "Compact.h"
+#include "MarkStack.h"
#include "Prelude.h"
#include "Trace.h"
#include "LdvProfile.h"
*/
if (!is_marked((P_)q,bd)) {
mark((P_)q,bd);
- if (mark_stack_full()) {
- debugTrace(DEBUG_gc,"mark stack overflowed");
- mark_stack_overflowed = rtsTrue;
- reset_mark_stack();
- }
push_mark_stack((P_)q);
}
return;
#include "Evac.h"
#include "Scav.h"
#include "GCUtils.h"
+#include "MarkStack.h"
#include "MarkWeak.h"
#include "Sparks.h"
#include "Sweep.h"
#endif
/* -----------------------------------------------------------------------------
- The mark bitmap & stack.
+ The mark stack.
-------------------------------------------------------------------------- */
-#define MARK_STACK_BLOCKS 4
-
-bdescr *mark_stack_bdescr;
-StgPtr *mark_stack;
-StgPtr *mark_sp;
-StgPtr *mark_splim;
-
-// Flag and pointers used for falling back to a linear scan when the
-// mark stack overflows.
-rtsBool mark_stack_overflowed;
-bdescr *oldgen_scan_bd;
-StgPtr oldgen_scan;
+bdescr *mark_stack_top_bd; // topmost block in the mark stack
+bdescr *mark_stack_bd; // current block in the mark stack
+StgPtr mark_sp; // pointer to the next unallocated mark stack entry
/* -----------------------------------------------------------------------------
GarbageCollect: the main entry point to the garbage collector.
/* Allocate a mark stack if we're doing a major collection.
*/
if (major_gc && oldest_gen->steps[0].mark) {
- nat mark_stack_blocks;
- mark_stack_blocks = stg_max(MARK_STACK_BLOCKS,
- oldest_gen->steps[0].n_old_blocks / 100);
- mark_stack_bdescr = allocGroup(mark_stack_blocks);
- mark_stack = (StgPtr *)mark_stack_bdescr->start;
- mark_sp = mark_stack;
- mark_splim = mark_stack + (mark_stack_blocks * BLOCK_SIZE_W);
+ mark_stack_bd = allocBlock();
+ mark_stack_top_bd = mark_stack_bd;
+ mark_stack_bd->link = NULL;
+ mark_stack_bd->u.back = NULL;
+ mark_sp = mark_stack_bd->start;
} else {
- mark_stack_bdescr = NULL;
+ mark_stack_bd = NULL;
+ mark_stack_top_bd = NULL;
+ mark_sp = NULL;
}
// this is the main thread
pinned_object_block = NULL;
// Free the mark stack.
- if (mark_stack_bdescr != NULL) {
- freeGroup(mark_stack_bdescr);
+ if (mark_stack_top_bd != NULL) {
+ debugTrace(DEBUG_gc, "mark stack: %d blocks",
+ countBlocks(mark_stack_top_bd));
+ freeChain(mark_stack_top_bd);
}
// Free any bitmaps.
write_barrier();
// scavenge objects in compacted generation
- if (mark_stack_overflowed || oldgen_scan_bd != NULL ||
- (mark_stack_bdescr != NULL && !mark_stack_empty())) {
+ if (mark_stack_bd != NULL && !mark_stack_empty()) {
return rtsTrue;
}
prodCapability(&capabilities[i], cap->running_task);
}
}
- for (j=0; j < 10000000; j++) {
+ for (j=0; j < 10; j++) {
retry = rtsFalse;
for (i=0; i < n_threads; i++) {
if (i == me) continue;
}
}
if (!retry) break;
+ yieldThread();
}
}
}
extern nat N;
extern rtsBool major_gc;
-extern bdescr *mark_stack_bdescr;
-extern StgPtr *mark_stack;
-extern StgPtr *mark_sp;
-extern StgPtr *mark_splim;
-
-extern rtsBool mark_stack_overflowed;
-extern bdescr *oldgen_scan_bd;
-extern StgPtr oldgen_scan;
+extern bdescr *mark_stack_bd;
+extern bdescr *mark_stack_top_bd;
+extern StgPtr mark_sp;
+extern StgPtr mark_splim;
extern long copied;
--- /dev/null
+/* -----------------------------------------------------------------------------
+ *
+ * (c) The GHC Team 1998-2009
+ *
+ * Operations on the mark stack
+ *
+ * Documentation on the architecture of the Garbage Collector can be
+ * found in the online commentary:
+ *
+ * http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
+ *
+ * ---------------------------------------------------------------------------*/
+
+#ifndef SM_MARKSTACK_H
+#define SM_MARKSTACk_H
+
+BEGIN_RTS_PRIVATE
+
+INLINE_HEADER void
+push_mark_stack(StgPtr p)
+{
+ bdescr *bd;
+
+ *mark_sp++ = (StgWord)p;
+
+ if (((W_)mark_sp & BLOCK_MASK) == 0)
+ {
+ if (mark_stack_bd->u.back != NULL)
+ {
+ mark_stack_bd = mark_stack_bd->u.back;
+ }
+ else
+ {
+ bd = allocBlock_sync();
+ bd->link = mark_stack_bd;
+ bd->u.back = NULL;
+ mark_stack_bd->u.back = bd; // double-link the new block on
+ mark_stack_top_bd = bd;
+ mark_stack_bd = bd;
+ }
+ mark_sp = mark_stack_bd->start;
+ }
+}
+
+INLINE_HEADER StgPtr
+pop_mark_stack(void)
+{
+ if (((W_)mark_sp & BLOCK_MASK) == 0)
+ {
+ if (mark_stack_bd->link == NULL)
+ {
+ return NULL;
+ }
+ else
+ {
+ mark_stack_bd = mark_stack_bd->link;
+ mark_sp = mark_stack_bd->start + BLOCK_SIZE_W;
+ }
+ }
+ return (StgPtr)*--mark_sp;
+}
+
+INLINE_HEADER rtsBool
+mark_stack_empty(void)
+{
+ return (((W_)mark_sp & BLOCK_MASK) == 0 && mark_stack_bd->link == NULL);
+}
+
+END_RTS_PRIVATE
+
+#endif /* SM_MARKSTACK_H */
#include "GCThread.h"
#include "GCUtils.h"
#include "Compact.h"
+#include "MarkStack.h"
#include "Evac.h"
#include "Scav.h"
#include "Apply.h"
gct->evac_step = &oldest_gen->steps[0];
saved_evac_step = gct->evac_step;
-linear_scan:
- while (!mark_stack_empty()) {
- p = pop_mark_stack();
+ while ((p = pop_mark_stack())) {
ASSERT(LOOKS_LIKE_CLOSURE_PTR(p));
info = get_itbl((StgClosure *)p);
recordMutableGen_GC((StgClosure *)q, gct->evac_step->gen_no);
}
}
-
- // mark the next bit to indicate "scavenged"
- mark(q+1, Bdescr(q));
-
- } // while (!mark_stack_empty())
-
- // start a new linear scan if the mark stack overflowed at some point
- if (mark_stack_overflowed && oldgen_scan_bd == NULL) {
- debugTrace(DEBUG_gc, "scavenge_mark_stack: starting linear scan");
- mark_stack_overflowed = rtsFalse;
- oldgen_scan_bd = oldest_gen->steps[0].old_blocks;
- oldgen_scan = oldgen_scan_bd->start;
- }
-
- if (oldgen_scan_bd) {
- // push a new thing on the mark stack
- loop:
- // find a closure that is marked but not scavenged, and start
- // from there.
- while (oldgen_scan < oldgen_scan_bd->free
- && !is_marked(oldgen_scan,oldgen_scan_bd)) {
- oldgen_scan++;
- }
-
- if (oldgen_scan < oldgen_scan_bd->free) {
-
- // already scavenged?
- if (is_marked(oldgen_scan+1,oldgen_scan_bd)) {
- oldgen_scan += sizeofW(StgHeader) + MIN_PAYLOAD_SIZE;
- goto loop;
- }
- push_mark_stack(oldgen_scan);
- // ToDo: bump the linear scan by the actual size of the object
- oldgen_scan += sizeofW(StgHeader) + MIN_PAYLOAD_SIZE;
- goto linear_scan;
- }
-
- oldgen_scan_bd = oldgen_scan_bd->link;
- if (oldgen_scan_bd != NULL) {
- oldgen_scan = oldgen_scan_bd->start;
- goto loop;
- }
- }
+ } // while (p = pop_mark_stack())
}
/* -----------------------------------------------------------------------------
}
// scavenge objects in compacted generation
- if (mark_stack_overflowed || oldgen_scan_bd != NULL ||
- (mark_stack_bdescr != NULL && !mark_stack_empty())) {
+ if (mark_stack_bd != NULL && !mark_stack_empty()) {
scavenge_mark_stack();
work_to_do = rtsTrue;
}