Method and apparatus for performing generational garbage collection using barrier bits

Abstract

A method and apparatus are disclosed for efficiently creating and maintaining a remembered set in a generational garbage collection scheme using a write buffer and a barrier bit associated with each object. A barrier bit associated with each object differentiates generations in a generational garbage collection scheme. When an object is first created, the barrier bit of the object is set to zero. The barrier bit is set when the object becomes old, for example, after surviving a first garbage collection. The barrier bit is used to determine whether to make an entry into a write buffer when a reference to another object is stored into an object. An entry is made in the write buffer only if the barrier bit of the object that is written into is set. At the end of each garbage collection, entries in the write buffer are added to the remembered set for the next garbage collection if the objects satisfy the criterion for membership, i.e., they are live and may contain pointers to objects in a younger generation. Thus, the remembered set consists of objects that were in the write buffer at the time of a garbage collection, that must be remembered for the next garbage collection. The write buffer is kept small by eliminating duplicate entries. The present invention turns off the barrier bit after the first store during each reclamation period (which causes the object to be identified in the write buffer). The barrier bit is turned on again by the garbage collector after the write buffer has been processed.