419427 - use exact incremental GC in tamarin

Status: VERIFIED WONTFIX

(Tamarin Graveyard :: Garbage Collection (mmGC), enhancement, P3)

Description

[Sergey Yanovich]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9b3) Gecko/2008021418 Firefox/3.0b3
Build Identifier: n/a

An exact incremental garbage collection framework implemented in C may be a faster, more reliable and easier to use alternative to MMgc, or may not.

Reproducible: Always




It is an exact incremental GC framework with potential thread-safety. It is implemented in C and can be used to create a single pool of objects from different programming languages like JavaScript, Java and Python within one OS process.

MMgc is currently using colored states of managed object to determine , whether they are ready for collection. The states are only valid within one cycle, and all objects need to be accessed again to clear the state, before the next cycle can start. The idea is to replace ever changing colored states with an minimum distance to a root, which is permanently kept in sync with dependency list.

The framework uses a relational table to store links between objects. The table has two unique indexes: (source, target) and (target, source), and implemented as a digital search tree (DST) for each index. The first index allows to traverse the object graph at O (ln N) speed, the second one enables O (ln N) cost of determining minimum distance to a root of any given object.

XLgc uses a linked list for input queue. Linked list operations are a single point, where synchronization is required, if multiple threads are to generate GC events.

Its exact nature and decent performance also make XLgc a candidate for the single place to store frames/DOM/boxes hierarchies of objects.

The framework is currently implemented at a proof-of-concept level. It correctly handles reference graphs with cycles. The patch follows immediately.

I spent some time trying to wire it up to XPCOM and SpiderMonkey, but with little success. Instead, I used a test with mozilla-like classes and smart pointers. Switch to the proposed system looks to be of the similar size to XPCOMGC, which is batch of manual and automatic rewriting.

Comment 1

[Sergey Yanovich]

Attachment: proof-of-concept implementation

There is a convenience makefile snippet, which can be invoked:
make -C modules/xlgc -f check.mk

from the top of mozilla tree. It is all tested only on linux. If there is an installed libxul, the makefile will pick it up. Otherwise, it can be supplied with LIBXULPATH=/path/to/libxul-sdk parameter.

The objdir will be created in modules/xlgc/objdir

Thanks for comments and attention.