[LLVMdev] Improving Garbage Collection
Anderson, Todd A
todd.a.anderson at intel.com
Thu Jul 7 10:55:06 PDT 2011
For the past few years, my group in Intel Labs has been working on a project similar to LLVM and C--, and perhaps our experience in handling roots and stack walking could be useful in deciding how LLVM should evolve in the GC area. Our project is called Pillar (you can see our paper "Pillar: A Parallel Implementation Language" in Languages and Compilers for Parallel Computing 2008 for a general overview). Pillar is a generic language and runtime designed to support managed languages and parallel languages although most of our work so far has been on the managed side. We've implemented a JVM and a functional language on top of Pillar so it has evidenced some generality.
In the Pillar language, we have a generalized ref (similar to llvm.gcroot) data type that encompases different kinds of pointers and types into the managed heap. This could be regular pointers, a couple varieties of interior pointers, or user-defined pointer types. The underlying compiler then generates per-callsite stack maps. Those stack maps can indicate when a live ref (local or parameter) is at a known offset from the start of the frame and can also indicate when a live ref is present in a register.
If we want to enumerate the refs of a call stack, we call a runtime function, prtYoungestActivation, and that gives us back a stack iterator for the sequence of activations. The iterator contains the value for esp and pointers to the memory locations where ebp, eip, edi, esi, and ebx were last saved to the stack. (For architectures other than 32-bit x86, the register-specific contents of the activation would of course be defined differently.) In the eip case, this is saved for every activation as part of the call sequence and so provides you with the ability to determine which call site you are at. The other registers may have been saved by the current frame or a subsequent frame. The stack iterator also contains a virtual frame number that basically allows an unwinder to see logical activations instead of physical activations that may combine multiple logical activations via inlining.
You can then call another runtime function, prtEnumerateRootsOfActivation, to ask for the roots associated with the given stack iterator's current activation to be enumerated. To this function, you pass a PrtRseInfo struct that contains a callback that gets invoked once per live ref found and a opaque environment variable passed (unexamined) onto the callback function. To go to the next activation on the call stack, you then call the runtime's prtNextActivation. There are routines to determine when you've got to the bottom of the call stack as well. In addition, there are routines for performing other (non-GC) operations the stack iterator's activation, such as looking up data associated with the SPAN construct (taken from C--) or exception handlers.
We have a couple of associated constructs in this regard. The first is the concept of code regions. We can define regions of code and define different owners for each region. A typical configuration is for most code to be in a region associated with our compiler, another region for code implemented in the Pillar runtime, and another region for code implemented in our GC. You first register a code info manager with the Pillar runtime and then associate regions of code with that manager. When you register, you provide a set of callback functions to enumerate roots, unwind to the next activation, etc. So, the Pillar compiler's code info manager uses a callback that consults the previously generated stack maps in order to enumerate roots. The GC could optimize its barriers and provide its own code info manager to handle enumerating roots in those barriers.
Thoughts?
Todd
Below are the relevant portions from our runtime's include files.
/* This is essentially a pointer-sized integer. */
typedef char *PrtRegister;
/* These are used to document function parameters to indicate whether they are IN, OUT, or INOUT. */
#define PRT_IN
#define PRT_OUT
#define PRT_INOUT
/*
***********************************************************************************************
* Basic constants, definitions, and types.
***********************************************************************************************
*/
/* These are tags that the GC uses to interpret roots that are enumerated.
Some tags require additional parameters that need to be passed in as well.
The interface includes a single argument that can be used directly for a
single parameter, or treated as an array or struct pointer if multiple
parameters are required.
Several tags are predefined for the compiler's benefit, but the high-level
language is free to use them as well.
"Default": The root points to the canonical object address (usually the base).
No additional parameters are used, and the argument is ignored.
"Offset": The root is at a known offset from the canonical object address.
Subtract the int-type parameter from the root to get the canonical
object address. Example: the root points to a specific field of
an object.
"Base": The root is related to an object whose canonical address is found as
the ref-type parameter. Example: the root points to some array element
contained within the object.
Any tag value starting from UserDefined and beyond can be defined and used
by the high-level language and its associated GC implementation.
*/
typedef enum { PrtGcTagDefault = 0, PrtGcTagOffset = 1, PrtGcTagBase = 2, PrtGcTagUserDefined = 3 } PrtGcTag;
/* Points to executable code. It is "unsigned char *" so that arithmetic is valid. */
typedef unsigned char *PrtCodeAddress;
/* Points to a sequence of data bytes. It is "unsigned char *" so that arithmetic is valid. */
typedef unsigned char *PrtDataPointer;
/* Forward declarations of nonexistent structures, to avoid typedef'ing to void*. */
struct PrtCimSpecificDataStruct;
struct PrtCodeInfoManagerStruct;
/*
* The context for stack frames that is used during stack walking. We use pointers in place of
* direct values to support root set enumeration.
*/
struct PrtStackIterator
{
/* Stack pointer, eip, and frame pointer */
PrtRegister esp;
PrtRegister *ebpPtr;
PrtCodeAddress *eipPtr;
/* Callee-save registers */
PrtRegister *ediPtr;
PrtRegister *esiPtr;
PrtRegister *ebxPtr;
/* The Pillar compiler may inline several "virtual" frames into a single "physical" frame.
However, the stack iterator should maintain the illusion that no inlining was done.
This field keeps track of which virtual frame we are at within the physical frame.
The value 0 means the newest, innermost frame, and the value is incremented when
doing a virtual unwind within the same physical frame. */
unsigned virtualFrameNumber;
}; /* struct PrtStackIterator */
/*
* Type of procedures called once for each enumerated root. "rootAddr" is the address of a pointer-sized field
* containing either a reference to a heap object or a managed pointer. "env" is an (opaque to Pillar) value
* that the client passed in a PrtRseInfo structure in the call
*/
typedef void (*PrtRseCallback)(void *env, void **rootAddr, PrtGcTag tag, void *parameter);
struct PrtRseInfo
{
PrtRseCallback callback; /* invoked for each enumerated root */
void *env; /* opaque value to be passed in each call to the callback function */
}; /* struct PrtRseInfo */
/*
**********************************************************************************************************
* Stack iteration functions
**********************************************************************************************************
*/
/*
* Create a stack iterator for the current task. "si" points to client-allocated storage.
*/
void prtYoungestActivation(PRT_OUT struct PrtStackIterator *si);
/* Go to the activation previous to (older than) the current one. */
void prtNextActivation(PRT_INOUT struct PrtStackIterator *si);
/* Return True iff no activations remain on the stack. */
#define prtIsActivationPastEnd(si) (((si)->eipPtr == NULL)? PrtTrue : PrtFalse)
/* Return the ip for the current activation. */
#define prtGetActivationIP(si) ((PrtCodeAddress)((si)->eipPtr ? *(si)->eipPtr : 0))
/* Convenience function for updating all writable fields of a stack iterator at once.
The advantage of using this consistently is that if the PrtStackIterator
ever changes, this function can be changed accordingly, and all calls to
it can be easily found and modified.
*/
void prtSetStackIteratorFields(PRT_OUT struct PrtStackIterator *context,
PRT_IN PrtCodeAddress *eipPtr,
PRT_IN PrtRegister esp,
PRT_IN PrtRegister *ebxPtr,
PRT_IN PrtRegister *ebpPtr,
PRT_IN PrtRegister *esiPtr,
PRT_IN PrtRegister *ediPtr,
PRT_IN unsigned virtualFrameNumber);
/*
* Returns the value associated with the smallest span tagged with "key" and containing the program point
* where "si" is suspended. Returns (PrtDataPointer)NULL if there is no such span.
*/
PrtDataPointer prtGetSpanDescriptor(PRT_IN struct PrtStackIterator *si, PRT_IN unsigned key);
/* Enumerate the roots of a frame given by the specified stack iterator. */
void prtEnumerateRootsOfActivation(PRT_IN struct PrtStackIterator *si, PRT_IN struct PrtRseInfo *rootSetInfo);
/*
***********************************************************************************************
* Code Info Manager functions
***********************************************************************************************
*/
typedef struct PrtCodeInfoManagerStruct *PrtCodeInfoManager;
/* Type of client-specified data that a client can associate with each code range with a prtCodeInfoManager. */
typedef struct PrtCimSpecificDataStruct *PrtCimSpecificDataType;
/*
* A set of callback functions implemented by a producer of managed code (e.g., a JIT or static compiler) that the PRT
* can call as part of its implementation of stack walking, root set enumeration, exception handling, etc. These are
* used to define a CodeInfoManager.
*/
struct PrtCodeInfoManagerFunctions {
/* Returns a string describing the current frame. */
char * ( *cimGetStringForFrame)(PRT_IN struct PrtStackIterator *si,
PRT_OUT char *buffer,
PRT_IN size_t bufferSize,
PRT_IN PrtCimSpecificDataType opaqueData);
/* Modifies si to hold information about the frame previous to the current one. Returns True if this was successful,
and False if not. opaqueData is the same as the opaqueData that was passed to Pillar when the CIM registered
this code region. */
void ( *cimGetPreviousFrame)(PRT_INOUT struct PrtStackIterator *si,
PRT_IN PrtCimSpecificDataType opaqueData);
/* Enumerates the live GC roots of the current stack frame. The activation is guaranteed to be
suspended at a call site. */
void ( *cimEnumerateRoots)(PRT_IN struct PrtStackIterator *si,
PRT_IN struct PrtRseInfo *rootSetInfo,
PRT_IN PrtCimSpecificDataType opaqueData);
/* Returns the value associated with the smallest span tagged with "key" and containing the program point
where "si" is suspended. "opaqueData" is the same data that the CIM passed to Pillar when it registered
the code region containing si's program point. Returns (PrtDataPointer)NULL if there is no such span. */
PrtDataPointer ( *cimGetSpanDescriptor)(PRT_IN struct PrtStackIterator *si,
PRT_IN unsigned key,
PRT_IN PrtCimSpecificDataType opaqueData);
}; /* struct PrtCodeInfoManagerFunctions */
/* Creates a new PrtCodeInfoManager and registers a set of callback functions belonging to it. */
PrtCodeInfoManager prtRegisterCodeInfoManager(PRT_IN const char *theCimName, PRT_IN struct PrtCodeInfoManagerFunctions theCimFns);
/*
* Register the block of code in [start..end] with the given PrtCodeInfoManager.
* Returns True on success and False on failure (e.g., if the code's region overlaps that of already-registered code).
* The opaqueData parameter is associated with this code region and passed back to the Cim during each of the calls
* to the Cim for this code region.
*/
void prtAddCodeRegion(PRT_IN PrtCodeInfoManager theCim,
PRT_IN PrtCodeAddress start,
PRT_IN PrtCodeAddress end,
PRT_IN PrtCimSpecificDataType opaqueData);
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110707/a531975c/attachment.html>
More information about the llvm-dev
mailing list