GC API

From MozillaWiki
Revision as of 14:26, 1 April 2008 by Jorend (talk | contribs) (prefer bsmedberg's names)
Jump to navigation Jump to search

This page contains notes regarding a generic conservative-GC API that we want to insert between application code (SpiderMonkey/Tamarin/XPCOM/whatever) and GC implementations (MMgc/jegc/spam/whatever).

Very preliminary.

—jorendorff 11:11, 28 March 2008 (PDT)

If you want to listen in on some design discussions, lurk in the #memory channel on irc.mozilla.org. Next meeting: Wednesday, April 2, 2008, 12:00 noon Pacific time.

Decisions

We will require the GC implementation to scan the C/C++ stack conservatively.

The API will support mostly-exact GC, meaning each object is exactly scanned to find other objects directly reachable from it, and only the stack and certain objects are scanned conservatively. (However, it seems to me like you could still implement this kind of API as a thin wrapper around a conservative-only GC like Boehm GC. It would just be more conservative than the API requires, that's all.)

We will support C++ objects somehow, as well as something like spam's "onion" layout.

We won't bend over backwards to make the API support MMgc in the fastest or most natural way. For example, the fastest possible MMgc write barrier requires the caller to know the beginning-of-allocation pointers for both the object containing the field being written and the pointer being stored there. This is a pain for the user, and a card-marking GC doesn't need those pointers anyway. So our API will not provide this information; the MMgc wrapper will have to calculate it each time the write barrier hits. This will make MMgc look slow, but we can live with that.

The purpose of this API is to support switching to a different GC implementation at compile time, not at run time. (Each implementation will have its own header file, with its own inline functions or function-like macros. Maybe we'll produce a GC API header file that has no inline anything, just showing the signatures the implementation must provide, for reference.)

Open issue: API style. (C or C++? Use templates? What naming conventions? I think it's too early to ask these questions. So please consider all the function signatures below to be pseudocode.)

Open issue: We should detect dumb implementation mismatches at link time and bomb out. I don't know the trick, but I bet bsmedberg does.

API areas

Heap setup/teardown

Requirement: Support multiple heaps. Each heap is a disjoint universe of objects. We don't need to trace pointers across heaps.

Allocation

(BTW we haven't established naming conventions; this is just a sketch)

The idea here is to support allocations of different types: no_pointers allocations are leaf objects and never contain pointers at all; with_layout and array_with_layout allocations have a known layout that governs which fields are pointers; and conservative allocations might contain pointers at any pointer-aligned offset and must be conservatively scanned.

(Where the layout information isn't a speed win, the implementation can of course just discard it. A hacky implementation can just delegate gc_alloc_with_layout and gc_alloc_array_with_layout to gc_alloc_conservative. Sloppy, but fine by me.)


All these functions return a pointer to a newly allocated region of memory that is subject to GC (that is, the GC may collect it when it becomes unreachable), or NULL on failure.

All allocations are malloc-aligned (that is, alignment is such that the pointer can be cast to any reasonable C/C++ type and used). 

void * gc_alloc_no_pointers(GCHeap heap, size_t size);

Allocate size bytes of memory, not necessarily zeroed. The GC will assume the memory never contains pointers to other GC allocations. 

void * gc_alloc_conservative(GCHeap heap, size_t size);

Allocate and zero out size bytes of memory. The GC will conservatively scan the memory for pointers. 

void * gc_alloc_onion(GCHeap, size_t rawSize, size_t ptrsSize);

Allocate rawSize + ptrsSize bytes of memory. Both sizes must be pointer-size-aligned. The first rawSize bytes are not necessarily zeroed. They GC will assume that they never contain pointers. The next ptrsSize bytes are treated as an array of "possible pointers" (jsval, really; see below). 

void * gc_alloc_with_layout(GCHeap heap, GCLayout layout);

Allocate and zero out memory for an object. The layout specifies the size of the allocation and which words of it may contain pointers. Layout is described in more detail below. 

void * gc_alloc_array_with_layout(
    GCHeap heap,
    GCLayout headerLayout,
    GCLayout elementLayout,
    size_t count);

Allocate and zero out memory for an array. The layout of the array consists of an optional header described by headerLayout, followed by count array elements, each described by elementLayout. Returns a pointer to the beginning of the allocation (the header).

Open issue: API for onions.

Open issue: Reference counting (or DRC) and/or other nasty tricks to keep memory usage down.

Open issue: Finalizers.

Open issue: Weak references.

Layout

TODO

Write barrier

template <class T, class U>
void gc_update(T **pField, U *newPtr);

(It's not decided whether we want C++ inline function templates, C macros, or what. This is just a sketch.)

Haven't discussed possibly having a different flavor of write barrier for jsval fields, etc.  :-P

(I'm calling it gc_update after what Jones and Lins call it in their book. Two very minor reasons to prefer this over gc_write_barrier: gc_update is less obscure for non-GC-experts; and it makes it clear that it actually performs the assignment, not just GC bookkeeping.)

Open issue: The Tamarin JIT might want some APIs that can help it generate fast inline machine code for pointer assignments (by inlining parts of the write barrier). At a minimum the JIT probably requires a wb function whose address can be taken. Not worrying about this yet.


GC

gc / maybe_gc / do_incremental_gc

Open issue: Hooks into the GC cycle.

Rooting

add root / remove root

Synchronization/concurrency

The request model, or something.

Open issue: This whole area.

(jorendorff note: SpiderMonkey has some pretty awesome hacks in the gc synchronization code, requiring equally awesome hacking in ActionMonkey's branch of MMgc. Maybe we could better divide the responsibilities. Discuss.)

Tracing

Some SpiderMonkey 1.8 JSAPI features, yet to be documented, need this. See mdc:JSAPI Reference#Memory_management.

bsmedberg says: most of the spidermonkey tracing APIs were designed for the cycle collector. I would dearly love to flush them down the drain once XPCOMGC lands.

The Memory API

This is a description of the API that the allocator needs to provide to the GC engine which runs atop it: 

/* GC Heap API */
typedef struct gcheap gcheap;
gcheap * gc_create_heap();
void gc_destroy_heap(gcheap *heap);

/* Layout API */
typedef struct gclayout gclayout;

/* Create a layout object which represents the layout of pointers within
   an object type.
   @param bitmap An array of bytes. Each byte represents one word of the
                 target object (there must be size / 4 entries)
          0 - the word is not a pointer
          1 - the word is a pointer, perhaps an interior pointer, and
              perhaps a pointer to an rcobject
          2 - the word is a jsval
          3 - the word is a ttbox
*/
gclayout * gc_create_layout(gcheap *heap, size_t size,
                            char *bitmap);

/* Allocation API */

typedef enum gcallocflags {
  GC_HAS_FINALIZER
};

/* allocate memory which has no pointers */
void * gc_alloc_no_pointers(gcheap *heap, size_t size,
                            int gcallocflags);

/* allocate memory in which every word is a pointer */
void * gc_alloc_all_pointers(gcheap *heap, size_t size,
                             int gcallocflags);

/* allocate memory in which every word must be conservatively scanned
   for pointers */
void * gc_alloc_conservative(gcheap *heap, size_t size,
                             int gcallocflags);

/* allocate memory using a layout object */
void * gc_alloc_with_layout(gcheap *heap, gclayout *layout,
                            int gcallocflags);

/* allocate an array of objects */
void * gc_alloc_array_with_layout(gcheap *heap, gclayout *header_layout,
                                  gclayout *entry_layout, size_t entrycount,
                                  gcallocflags);

void gc_free(gcheap *heap);

/* APIs for marking */

/* Begin the process of mark/sweep: after this call, gc_is_marked should
   return GC_UNMARKED for all allocations */
void gc_begin_mark(gcheap *heap);

/* @param object must be the outermost pointer to the allocation */
void gc_mark_object(gcheap *heap, void *object);

/* Get the "next" object which has been marked but not yet processed.
   The GC engine needs to know about the object layout, but I don't know
   the best way to expose this (or whether the allocator ought to do that?) */
void * gc_get_next_unprocessed(gcheap *heap, some_kind_of_layout_object);

typedef enum gcmarkstate {
  GC_NOT_GCOBJECT, /* this pointer is not a gc allocation */
  GC_UNMARKED,
  GC_MARKED,     /* gc_mark_object, but not yet gc_get_next_unprocessed */
  GC_PROCESSED   /* processed by gc_get_next_unprocessed */
} gcmarkstate;

/* @param object must be an exterior pointer to an object in this heap */
gcmarkstate gc_get_markstate(gcheap *heap, void *object);

/* @param object inout - in is a conservative pointer
                 if the function returns something other than GC_NOT_GCOBJECT,
                 it will be set to the "outer" pointer */
gcmarkstate gc_conservative_beginning(gcheap *heap, void **object);

void gc_mark_stack(gcheap *heap);

/* Inform the allocator that we're done marking. The allocator will sweep
   all unmarked objects, firing finalizers where appropriate. */
gc_end_mark(gcheap *heap);

Things to be specified:

  • Synchronization
  • RCObjects - other than write barriers and a flag bit, I don't think the allocator itself needs to know anything about RCObjects
Retrieved from "https://wiki.mozilla.org/index.php?title=GC_API&oldid=88641"