Concurrent Collection of Cyclic Garbage in Reference Counting Systems

Abstract

The present invention provides techniques that allow concurrent collection of cyclic garbage on reference counting systems. In general, candidate objects are found that may be part of cyclic garbage. Each candidate object has a reference count. Two tests are performed to determine if concurrent operations have affected the reference counts of the candidate objects. If concurrent operations have not affected the reference counts, the candidate objects are collected as garbage. Additionally, during garbage collection, the decrements to reference counts are delayed so that increments occur before decrements and so that decrements are held a predetermined time before being applied. This prevents decrementing a reference and collecting a cycle as garbage right before a reference is added to an object in the cycle.

1 . A method useful for concurrent collection of cyclic garbage in a reference counting system, the method comprising the steps of: 
 identifying candidate objects having associated reference counts for garbage collection, wherein each candidate object is potentially garbage; and    determining if the candidate objects are garbage, the step of determining performed without preventing mutators in the system from changing object references and the step of determining further comprising the steps of:    determining, after a time period, if the candidate objects are still potentially garbage; and    for those candidate objects that are still potentially garbage, determining if the reference count associated with the candidate object has changed.    
   
   
       2 . The method of  claim 1 , wherein: 
 wherein each candidate object is potentially garbage;    the step of determining if the candidate objects are garbage further comprises the steps of:    determining, after a time period, if the candidate objects are still potentially garbage; and    for those candidate objects that are still potentially garbage, determining if the reference count associated with the candidate object has changed.    
   
   
       3 . The method of  claim 1 , wherein the step of determining if the reference count associated with the candidate object has changed further comprises the step of determining, after a time period, if the reference count associated with the candidate object has changed.  
   
   
       4 . The method of  claim 3 , wherein: 
 the step of determining, after a time period, if the candidate objects are still potentially garbage further comprises the step of for each candidate object, copying a reference count associated with the object into a cyclic reference count; and    the step of determining, after a second time period, if the reference count associated with the candidate object has changed further comprises the step of determining, for each candidate object if the cyclic reference count is zero.    
   
   
       5 . The method of  claim 4 , wherein: 
 the step of finding candidate objects for garbage collection comprises the steps of:    determining root objects by determining objects whose reference count has been decremented to a non-zero value;    for each root object, determining objects in a cycle defined by the root object;    storing references to each object in a cycle, thereby storing each cycle; and    the step of determining, after a second time period, if the reference count associated with the candidate object has changed further comprises the step of processing the cycles in reverse order of an order in which they were stored.    
   
   
       6 . The method of  claim 3 , wherein the time period is an epoch.  
   
   
       7 . The method of  claim 1 , wherein each candidate object is part of a cycle and wherein the step of determining, after a time period, if the candidate objects are still potentially garbage comprises the steps of: 
 for each candidate object, copying a reference count associated with the object into a cyclic reference count;    for each candidate object, decrementing the cyclic reference count each time a reference from a referencing object refers to the candidate object, wherein the referencing object resides in the cycle in which the candidate object resides;    waiting the time period; and    for each candidate object, determining if the cyclic reference count associated with the candidate object is zero.    
   
   
       8 . The method of  claim 1 , wherein: 
 the step of identifying candidate objects for garbage collection further comprises the steps of:    identifying a plurality of roots for garbage collection, wherein each root comprises a reference count and wherein each root describes a set comprising objects that are interconnected through references;    selecting one of the sets;    performing the following steps for the set:    for each object in the set, creating a copy of the reference count; and    for each object in the set, decrementing the copy of the reference count associated with the object for as many times as the object is referenced by itself or another object contained in the set;    the step of determining further comprises:    determining, after a time period, if the copies of the reference counts for each object in the set are zero;    determining if one or more increments have made at least one reference count for objects in the set outdated; and    collecting the set as garbage when the copies for each object in the set are zero and when there are no outdated reference counts.    
   
   
       9 . The method of  claim 8 , wherein the time period is an epoch.  
   
   
       10 . A method for processing changes to reference counts in a reference counting system, each reference count associated with a particular object and containing a number of references that reference the particular object, the method comprising the steps of: 
 determining increments and decrements of reference counts for a current time period;    processing the increments of reference counts for the current time period;    storing the decrements of reference counts for the current time period; and    processing decrements of reference counts for a previous time period.    
   
   
       11 . The method of  claim 10 , wherein each of the current and previous time periods are an epoch.  
   
   
       12 . The method of  claim 11 , wherein each epoch is separated by a period where increments and decrements to reference counts are applied for all processors in a plurality of processors.  
   
   
       13 . A computer system comprising: 
 a memory that stores computer-readable code; and    a processor operatively coupled to the memory, the processor configured to implement the computer-readable code, the computer-readable code configured to:    identify candidate objects having associated reference counts for garbage collection, wherein each candidate object is potentially garbage; and    determine if the candidate objects are garbage, the step of determining performed without preventing mutators in the system from changing object references and the step of determining further comprising the steps of:    determining, after a time period, if the candidate objects are still potentially garbage; and    for those candidate objects that are still potentially garbage, determining if the reference count associated with the candidate object has changed.    
   
   
       14 . An article of manufacture comprising: 
 a computer-readable medium having computer-readable program code means embodied thereon, the computer-readable program code means comprising:    a step to identify candidate objects having associated reference counts for garbage collection, wherein each candidate object is potentially garbage; and    a step to determine if the candidate objects are garbage, the step of determining performed without preventing mutators in the system from changing object references and the step of determining further comprising the steps of:    determining, after a time period, if the candidate objects are still potentially garbage; and    for those candidate objects that are still potentially garbage, determining if the reference count associated with the candidate object has changed.