Method and apparatus for performing generational garbage collection using remembered set counter

Abstract

A method and apparatus are provided for the efficient management of remembered sets in a generational garbage collection scheme. In order to manage the remembered set, the present invention provides a first mechanism for detecting when an old object has a pointer to a young object, and needs to be added to the remembered set, and a second mechanism for detecting when an object already in the remembered set no longer contains a pointer to a young object, so that the object can be removed from the remembered set. Entries in the remembered set have an associated counter, C, identifying the garbage collection cycle during which the object was placed in the remembered set. Objects inserted into the remembered set are assumed to point to the youngest possible object. Entries automatically expire from the remembered set when the garbage collection counter reaches C+N, since the objects pointed to by the object in the remembered set must now themselves be old objects. If an old object (one that has survived at least N garbage collections) is identified during a minor garbage collection, the old object is scanned normally, and is placed into the remembered set, with a counter C identifying the garbage collection cycle during which the old object was placed in the remembered set. The counter identifies the age of the youngest possible object pointed to by this object. When the garbage collection count reaches C+N, this entry can be discarded from the remembered set, since the associated object cannot point to any objects that are not old unless another more recent entry in the remembered set or write buffer exists for that object.