/* walk.c: OBJECT WALKER
*
* $Id: //info.ravenbrook.com/project/mps/master/code/walk.c#33 $
* Copyright (c) 2001-2020 Ravenbrook Limited. See end of file for license.
*/
#include "mpm.h"
#include "mps.h"
SRCID(walk, "$Id: //info.ravenbrook.com/project/mps/master/code/walk.c#33 $");
/* Heap Walking
*/
#define FormattedObjectsStepClosureSig ((Sig)0x519F05C1) /* SIGnature Formatted Objects Step CLosure */
typedef struct FormattedObjectsStepClosureStruct *FormattedObjectsStepClosure;
typedef struct FormattedObjectsStepClosureStruct {
Sig sig; /* design.mps.sig.field */
mps_formatted_objects_stepper_t f;
void *p;
size_t s;
} FormattedObjectsStepClosureStruct;
ATTRIBUTE_UNUSED
static Bool FormattedObjectsStepClosureCheck(FormattedObjectsStepClosure c)
{
CHECKS(FormattedObjectsStepClosure, c);
CHECKL(FUNCHECK(c->f));
/* p and s fields are arbitrary closures which cannot be checked */
return TRUE;
}
static void ArenaFormattedObjectsStep(Addr object, Format format, Pool pool,
void *p, size_t s)
{
FormattedObjectsStepClosure c;
/* Can't check object */
AVERT(Format, format);
AVERT(Pool, pool);
c = p;
AVERT(FormattedObjectsStepClosure, c);
AVER(s == UNUSED_SIZE);
(*c->f)((mps_addr_t)object, (mps_fmt_t)format, (mps_pool_t)pool,
c->p, c->s);
}
/* ArenaFormattedObjectsWalk -- iterate over all objects
*
* So called because it walks all formatted objects in an arena. */
static void ArenaFormattedObjectsWalk(Arena arena, FormattedObjectsVisitor f,
void *p, size_t s)
{
Seg seg;
FormattedObjectsStepClosure c;
Format format;
AVERT(Arena, arena);
AVER(FUNCHECK(f));
AVER(f == ArenaFormattedObjectsStep);
/* Know that p is a FormattedObjectsStepClosure */
c = p;
AVERT(FormattedObjectsStepClosure, c);
/* Know that s is UNUSED_SIZE */
AVER(s == UNUSED_SIZE);
if (SegFirst(&seg, arena)) {
do {
if (PoolFormat(&format, SegPool(seg))) {
ShieldExpose(arena, seg);
SegWalk(seg, format, f, p, s);
ShieldCover(arena, seg);
}
} while(SegNext(&seg, arena, seg));
}
}
/* mps_arena_formatted_objects_walk -- iterate over all objects
*
* Client interface to ArenaFormattedObjectsWalk. */
void mps_arena_formatted_objects_walk(mps_arena_t mps_arena,
mps_formatted_objects_stepper_t f,
void *p, size_t s)
{
Arena arena = (Arena)mps_arena;
FormattedObjectsStepClosureStruct c;
ArenaEnter(arena);
AVERT(Arena, arena);
AVER(FUNCHECK(f));
/* p and s are arbitrary closures, hence can't be checked */
c.sig = FormattedObjectsStepClosureSig;
c.f = f;
c.p = p;
c.s = s;
ArenaFormattedObjectsWalk(arena, ArenaFormattedObjectsStep, &c, UNUSED_SIZE);
ArenaLeave(arena);
}
/* Root Walking
*
* This involves more code than it should. The roots are walked by
* scanning them. But there's no direct support for invoking the scanner
* without there being a trace, and there's no direct support for
* creating a trace without also condemning part of the heap. (@@@@ This
* looks like a useful candidate for inclusion in the future). For now,
* the root walker contains its own code for creating a minimal trace
* and scan state.
*
* ASSUMPTIONS
*
* .assume.parked: The root walker must be invoked with a parked
* arena. It's only strictly necessary for there to be no current trace,
* but the client has no way to ensure this apart from parking the
* arena.
*
* .assume.rootaddr: The client closure is called with a parameter which
* is the address of a reference to an object referenced from a
* root. The client may desire this address to be the address of the
* actual reference in the root (so that the debugger can be used to
* determine details about the root). This is not always possible, since
* the root might actually be a register, or the format scan method
* might not pass this address directly to the fix method. If the format
* code does pass on the address, the client can be sure to be passed
* the address of any root other than a register or stack. */
/* rootsStepClosure -- closure environment for root walker
*
* Defined as a subclass of ScanState. */
#define rootsStepClosureSig ((Sig)0x51965C10) /* SIGnature Roots Step CLOsure */
typedef struct rootsStepClosureStruct *rootsStepClosure;
typedef struct rootsStepClosureStruct {
ScanStateStruct ssStruct; /* generic scan state object */
mps_roots_stepper_t f; /* client closure function */
void *p; /* client closure data */
size_t s; /* client closure data */
Root root; /* current root, or NULL */
Sig sig; /* design.mps.sig.field.end.outer */
} rootsStepClosureStruct;
#define rootsStepClosure2ScanState(rsc) (&(rsc)->ssStruct)
#define ScanState2rootsStepClosure(ss) \
PARENT(rootsStepClosureStruct, ssStruct, ss)
/* rootsStepClosureCheck -- check a rootsStepClosure */
ATTRIBUTE_UNUSED
static Bool rootsStepClosureCheck(rootsStepClosure rsc)
{
CHECKS(rootsStepClosure, rsc);
CHECKD(ScanState, &rsc->ssStruct);
CHECKL(FUNCHECK(rsc->f));
/* p and s fields are arbitrary closures which cannot be checked */
if (rsc->root != NULL) {
CHECKD_NOSIG(Root, rsc->root); /* <design/check/#.hidden-type> */
}
return TRUE;
}
/* rootsStepClosureInit -- Initialize a rootsStepClosure
*
* Initialize the parent ScanState too. */
static void rootsStepClosureInit(rootsStepClosure rsc,
Globals arena, Trace trace,
SegFixMethod rootFix,
mps_roots_stepper_t f, void *p, size_t s)
{
ScanState ss;
/* First initialize the ScanState superclass */
ss = &rsc->ssStruct;
ScanStateInit(ss, TraceSetSingle(trace), GlobalsArena(arena), RankMIN,
trace->white);
/* Initialize the fix method in the ScanState */
ss->fix = rootFix;
/* Initialize subclass specific data */
rsc->f = f;
rsc->p = p;
rsc->s = s;
rsc->root = NULL;
rsc->sig = rootsStepClosureSig;
AVERT(rootsStepClosure, rsc);
}
/* rootsStepClosureFinish -- Finish a rootsStepClosure
*
* Finish the parent ScanState too. */
static void rootsStepClosureFinish(rootsStepClosure rsc)
{
ScanState ss;
ss = rootsStepClosure2ScanState(rsc);
rsc->sig = SigInvalid;
ScanStateFinish(ss);
}
/* RootsWalkFix -- the fix method used during root walking
*
* This doesn't cause further scanning of transitive references, it just
* calls the client closure. */
static Res RootsWalkFix(Seg seg, ScanState ss, Ref *refIO)
{
rootsStepClosure rsc;
Ref ref;
AVERT(Seg, seg);
AVERT(ScanState, ss);
AVER(refIO != NULL);
rsc = ScanState2rootsStepClosure(ss);
AVERT(rootsStepClosure, rsc);
ref = *refIO;
/* Call the client closure - .assume.rootaddr */
rsc->f((mps_addr_t*)refIO, (mps_root_t)rsc->root, rsc->p, rsc->s);
AVER(ref == *refIO); /* can walk object graph - but not modify it */
return ResOK;
}
/* rootWalk -- the step function for ArenaRootsWalk */
static Res rootWalk(Root root, void *p)
{
ScanState ss = (ScanState)p;
AVERT(ScanState, ss);
if (RootRank(root) == ss->rank) {
/* set the root for the benefit of the fix method */
ScanState2rootsStepClosure(ss)->root = root;
/* Scan it */
ScanStateSetSummary(ss, RefSetEMPTY);
return RootScan(ss, root);
} else
return ResOK;
}
/* rootWalkGrey -- make the root grey for the trace passed as p */
static Res rootWalkGrey(Root root, void *p)
{
Trace trace = p;
AVERT(Root, root);
AVERT(Trace, trace);
RootGrey(root, trace);
return ResOK;
}
/* ArenaRootsWalk -- walks all the root in the arena */
static Res ArenaRootsWalk(Globals arenaGlobals, mps_roots_stepper_t f,
void *p, size_t s)
{
Arena arena;
rootsStepClosureStruct rscStruct;
rootsStepClosure rsc = &rscStruct;
Trace trace;
ScanState ss;
Rank rank;
Res res;
Seg seg;
AVERT(Globals, arenaGlobals);
AVER(FUNCHECK(f));
/* p and s are arbitrary client-provided closure data. */
arena = GlobalsArena(arenaGlobals);
/* Scan all the roots with a minimal trace. Invoke the scanner with a */
/* rootsStepClosure, which is a subclass of ScanState and contains the */
/* client-provided closure. Supply a special fix method in order to */
/* call the client closure. This fix method must perform no tracing */
/* operations of its own. */
res = TraceCreate(&trace, arena, TraceStartWhyWALK);
/* Have to fail if no trace available. Unlikely due to .assume.parked. */
if (res != ResOK)
return res;
/* .roots-walk.first-stage: In order to fool MPS_FIX12 into calling
_mps_fix2 for a reference in a root, the reference must pass the
first-stage test (against the summary of the trace's white
set), so make the summary universal. */
trace->white = ZoneSetUNIV;
/* .roots-walk.second-stage: In order to fool _mps_fix2 into calling
our fix function (RootsWalkFix), the reference must be to a
segment that is white for the trace, so make all segments white
for the trace. */
if (SegFirst(&seg, arena)) {
do {
SegSetWhite(seg, TraceSetAdd(SegWhite(seg), trace));
} while (SegNext(&seg, arena, seg));
}
/* Make the roots grey so that they are scanned */
res = RootsIterate(arenaGlobals, rootWalkGrey, trace);
/* Make this trace look like any other trace. */
arena->flippedTraces = TraceSetAdd(arena->flippedTraces, trace);
rootsStepClosureInit(rsc, arenaGlobals, trace, RootsWalkFix, f, p, s);
ss = rootsStepClosure2ScanState(rsc);
for(rank = RankMIN; rank < RankLIMIT; ++rank) {
ss->rank = rank;
AVERT(ScanState, ss);
res = RootsIterate(arenaGlobals, rootWalk, (void *)ss);
if (res != ResOK)
break;
}
/* Turn segments black again. */
if (SegFirst(&seg, arena)) {
do {
SegSetWhite(seg, TraceSetDel(SegWhite(seg), trace));
} while (SegNext(&seg, arena, seg));
}
rootsStepClosureFinish(rsc);
/* Make this trace look like any other finished trace. */
trace->state = TraceFINISHED;
TraceDestroyFinished(trace);
AVER(!ArenaEmergency(arena)); /* There was no allocation. */
return res;
}
/* mps_arena_roots_walk -- Client interface for walking */
void mps_arena_roots_walk(mps_arena_t mps_arena, mps_roots_stepper_t f,
void *p, size_t s)
{
Arena arena = (Arena)mps_arena;
Res res;
ArenaEnter(arena);
STACK_CONTEXT_BEGIN(arena) {
AVER(FUNCHECK(f));
/* p and s are arbitrary closures, hence can't be checked */
AVER(ArenaGlobals(arena)->clamped); /* .assume.parked */
AVER(arena->busyTraces == TraceSetEMPTY); /* .assume.parked */
res = ArenaRootsWalk(ArenaGlobals(arena), f, p, s);
AVER(res == ResOK);
} STACK_CONTEXT_END(arena);
ArenaLeave(arena);
}
/* walkNoFix -- third-stage fix function for poolWalk.
*
* The second-stage fix is not called via poolWalk; so this is not
* called either. The NOTREACHED checks that this is the case.
*/
static Res walkNoFix(Seg seg, ScanState ss, Addr *refIO)
{
AVERT(Seg, seg);
AVERT(ScanState, ss);
AVER(refIO != NULL);
NOTREACHED;
return ResUNIMPL;
}
/* poolWalkScan -- format scanner for poolWalk */
static mps_res_t poolWalkScan(mps_ss_t mps_ss, void *base, void *limit)
{
ScanState ss = PARENT(ScanStateStruct, ss_s, mps_ss);
AVERT(ScanState, ss);
AVER(base != NULL);
AVER(limit != NULL);
AVER(base < limit);
return ss->areaScan(mps_ss, base, limit, ss->areaScanClosure);
}
/* poolWalk -- walk formatted areas in a pool
*
* See <design/walk>.
*/
static Res poolWalk(Arena arena, Pool pool, mps_area_scan_t area_scan, void *closure)
{
Trace trace;
TraceSet ts;
ScanStateStruct ss;
Ring node, nextNode;
Res res = ResOK;
AVERT(Arena, arena);
AVERT(Pool, pool);
AVER(FUNCHECK(area_scan));
/* closure is arbitrary and can't be checked */
AVER(ArenaGlobals(arena)->clamped); /* .assume.parked */
AVER(arena->busyTraces == TraceSetEMPTY); /* .assume.parked */
/* Synthesize a flipped trace with an empty white set. The empty
* white set means that the MPS_FIX1 test will always fail and
* _mps_fix2 will never be called. */
res = TraceCreate(&trace, arena, TraceStartWhyWALK);
/* Fail if no trace available. Unlikely due to .assume.parked. */
if (res != ResOK)
return res;
trace->white = ZoneSetEMPTY;
trace->state = TraceFLIPPED;
arena->flippedTraces = TraceSetAdd(arena->flippedTraces, trace);
ts = TraceSetSingle(trace);
ScanStateInit(&ss, ts, arena, RankEXACT, trace->white);
ss.formatScan = poolWalkScan;
ss.areaScan = area_scan;
ss.areaScanClosure = closure;
ss.fix = walkNoFix;
RING_FOR(node, &pool->segRing, nextNode) {
Bool wasTotal;
Seg seg = SegOfPoolRing(node);
Bool needSummary = SegRankSet(seg) != RankSetEMPTY;
if (needSummary)
ScanStateSetSummary(&ss, RefSetEMPTY);
/* Expose the segment to make sure we can scan it. */
ShieldExpose(arena, seg);
res = SegScan(&wasTotal, seg, &ss);
ShieldCover(arena, seg);
if (needSummary)
ScanStateUpdateSummary(&ss, seg, res == ResOK && wasTotal);
if (res != ResOK)
break;
}
ScanStateFinish(&ss);
trace->state = TraceFINISHED;
TraceDestroyFinished(trace);
AVER(!ArenaEmergency(arena)); /* There was no allocation. */
return res;
}
mps_res_t mps_pool_walk(mps_pool_t pool, mps_area_scan_t area_scan, void *closure)
{
Arena arena;
Res res;
AVER(TESTT(Pool, pool));
arena = PoolArena(pool);
ArenaEnter(arena);
AVER(FUNCHECK(area_scan));
/* closure is arbitrary and can't be checked */
res = poolWalk(arena, pool, area_scan, closure);
ArenaLeave(arena);
return res;
}
/* C. COPYRIGHT AND LICENSE
*
* Copyright (C) 2001-2020 Ravenbrook Limited <https://www.ravenbrook.com/>.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/