/* ----------------------------------------------------------------------------- * * (c) The GHC Team, 1998-2019 * * Non-moving garbage collector and allocator: * Indirection short-cutting and the selector optimisation * * ---------------------------------------------------------------------------*/ #include "Rts.h" #include "GC.h" #include "SMPClosureOps.h" #include "NonMovingMark.h" #include "NonMovingShortcut.h" #include "Printer.h" #define MAX_THUNK_SELECTOR_DEPTH 16 //#define SELECTOR_OPT_DEBUG #if defined(SELECTOR_OPT_DEBUG) static void print_selector_chain(StgClosure *p) { debugBelch("Selector chain: %p", (void*)p); StgClosure *next = p->payload[0]; while (next != NULL) { debugBelch(", %p", next); next = next->payload[0]; } debugBelch("\n"); } #endif static void update_selector_chain( StgClosure *chain, StgClosure **origin, StgSelector * const p0, StgClosure * const val ) { ASSERT(val != NULL); // Make sure we don't introduce non-moving-to-moving pointers here. ASSERT(isNonmovingClosure(val)); // This case we can't handle because we don't know info ptr of the closure // before we locked it. ASSERT(chain != val); #if defined(SELECTOR_OPT_DEBUG) if (chain != NULL) { print_selector_chain(chain); debugBelch("Value: "); printClosure(val); } #endif while (chain) { // debugBelch("chain: %p\n", (void*)chain); StgClosure *next = chain->payload[0]; // We only update closures in the non-moving heap ASSERT(isNonmovingClosure(chain)); ((StgInd*)chain)->indirectee = val; unlockClosure((StgClosure*)chain, &stg_IND_info); chain = next; } if (origin != NULL && (StgClosure*)p0 != val) { cas((StgVolatilePtr)origin, (StgWord)p0, (StgWord)val); } } // Returns value of the selector thunk. The value is a non-moving closure. If // it's not possible to evaluate the selector thunk the return value will be the // selector itself. static StgClosure* nonmoving_eval_thunk_selector_( MarkQueue *queue, StgSelector * const p0, StgClosure ** const origin, int depth ) { // This function should only be called on non-moving objects. ASSERT(HEAP_ALLOCED_GC((P_)p0) && isNonmovingClosure((StgClosure*)p0)); markQueuePushClosure(queue, (StgClosure*)p0, NULL); // INVARIANT: A non-moving object. Locked (below). StgClosure *p = (StgClosure*)p0; // Chain of non-moving selectors to update. These will be INDs to `p` when // we reach to a value. INVARIANT: All objects in the chain are locked, and // in the non-moving heap. StgClosure *chain = NULL; // Variables to update: p. selector_changed: ; // debugBelch("Selector changed: %p\n", (void*)p); // Lock the selector to avoid concurrent modification in mutators const StgInfoTable *selector_info_ptr = lockClosure((StgClosure*)p); StgInfoTable *selector_info_tbl = INFO_PTR_TO_STRUCT(selector_info_ptr); if (selector_info_tbl->type != THUNK_SELECTOR) { // Selector updated in the meantime, or we reached to a value. Update // the chain. unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return p; } // The closure is locked and it's a selector thunk. If the selectee is a // CONSTR we do the selection here and the In the selected value will be the // value of this selector thunk. // // Two cases: // // - If the selected value is also a selector thunk, then we loop and // evaluate it. The final value will be the value of both the current // selector and the selected value (which is also a selector thunk). // // - If the selectee is a selector thunk, we recursively evaluate it (up to // a certain depth, specified with MAX_THUNK_SELECTOR_DEPTH), then do the // selection on the value of it. // // Do the selection // uint32_t field = selector_info_tbl->layout.selector_offset; StgClosure *selectee = UNTAG_CLOSURE(((StgSelector*)p)->selectee); // Variables to update: selectee selectee_changed: // debugBelch("Selectee changed: %p\n", (void*)selectee); if (!isNonmovingClosure(selectee)) { // The selectee is a moving object, and it may be moved by a concurrent // minor GC while we read the info table and fields, so don't try to // read the fields, just update the chain. unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return p; } // Selectee is a non-moving object, mark it. markQueuePushClosure(queue, selectee, NULL); const StgInfoTable *selectee_info_tbl = get_itbl(selectee); switch (selectee_info_tbl->type) { case WHITEHOLE: { // Probably a loop. Abort. unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return p; } case CONSTR: case CONSTR_1_0: case CONSTR_0_1: case CONSTR_2_0: case CONSTR_1_1: case CONSTR_0_2: case CONSTR_NOCAF: { // Selectee is a constructor in the non-moving heap. // Select the field. // Check that the size is in range. ASSERT(field < (StgWord32)(selectee_info_tbl->layout.payload.ptrs + selectee_info_tbl->layout.payload.nptrs)); StgClosure *val = UNTAG_CLOSURE(selectee->payload[field]); // `val` is the value of this selector thunk. We need to check a // few cases: // // - If `val` is in the moving heap, we stop here and update the // chain. All updated objects should be added to the mut_list. // (TODO (osa): What happens if the value is evacuated as we do // this?) // // - If `val` is in the non-moving heap, we check if it's also a // selector. If it is we add it to the chain and loop. // Follow indirections. Variables to update: `val`. val_changed: if (!isNonmovingClosure(val)) { // The selected value is a moving object, so we won't be // updating the chain to this object. unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return p; } switch (get_itbl(val)->type) { case IND: case IND_STATIC: ; // Follow the indirection StgClosure *indirectee = UNTAG_CLOSURE(((StgInd*)val)->indirectee); if (isNonmovingClosure(indirectee)) { val = UNTAG_CLOSURE(((StgInd*)val)->indirectee); goto val_changed; } else { unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return p; } case THUNK_SELECTOR: // Value of the selector thunk is again a selector thunk in the // non-moving heap. Add the current selector to the chain and // loop. p->payload[0] = chain; chain = p; p = val; goto selector_changed; default: // Found a value, add the current selector to the chain and // update it. p->payload[0] = chain; chain = p; update_selector_chain(chain, origin, p0, val); return val; } } case IND: case IND_STATIC: { StgClosure *indirectee = UNTAG_CLOSURE(((StgInd *)selectee)->indirectee); if (isNonmovingClosure(indirectee)) { selectee = indirectee; goto selectee_changed; } else { unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return p; } } case BLACKHOLE: { StgClosure *indirectee = ((StgInd*)selectee)->indirectee; if (!isNonmovingClosure(UNTAG_CLOSURE(indirectee))) { unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return p; } // Establish whether this BH has been updated, and is now an // indirection, as in evacuate(). if (GET_CLOSURE_TAG(indirectee) == 0) { const StgInfoTable *i = indirectee->header.info; if (i == &stg_TSO_info || i == &stg_WHITEHOLE_info || i == &stg_BLOCKING_QUEUE_CLEAN_info || i == &stg_BLOCKING_QUEUE_DIRTY_info) { unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return (StgClosure*)p; } ASSERT(i != &stg_IND_info); // TODO not sure about this part } // It's an indirection, follow it. selectee = UNTAG_CLOSURE(indirectee); goto selectee_changed; } case AP: case AP_STACK: case THUNK: case THUNK_1_0: case THUNK_0_1: case THUNK_2_0: case THUNK_1_1: case THUNK_0_2: case THUNK_STATIC: { // Not evaluated yet unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return (StgClosure*)p; } case THUNK_SELECTOR: { // Selectee is a selector thunk. Evaluate it if we haven't reached // the recursion limit yet. if (depth < MAX_THUNK_SELECTOR_DEPTH) { StgClosure *new_selectee = UNTAG_CLOSURE(nonmoving_eval_thunk_selector_( queue, (StgSelector*)selectee, NULL, depth+1)); ASSERT(isNonmovingClosure(new_selectee)); if (selectee == new_selectee) { unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return (StgClosure*)p; } else { selectee = new_selectee; goto selectee_changed; } } else { // Recursion limit reached unlockClosure(p, selector_info_ptr); update_selector_chain(chain, origin, p0, p); return (StgClosure*)p; } } default: { barf("nonmoving_eval_thunk_selector: strange selectee %d", (int)(selectee_info_tbl->type)); } } } void nonmoving_eval_thunk_selector(MarkQueue *queue, StgSelector *p, StgClosure **origin) { nonmoving_eval_thunk_selector_(queue, p, origin, 0); }