Memory reclamation method and apparatus

Abstract

A method and apparatus for reclaiming memory space allocated to data structures comprising data objects linked by identifying pointers. The memory allocated to data objects is reclaimed using two systems. In the first system ( 240 ), the data structures are traversed to identify those objects to which no references are made by the pointers of other objects, and the memory allocated to those objects to which no references are made is reclaimed. In the second system ( 210 ), objects which are not descendants of root objects are determined and the memory allocated to those objects is reclaimed. Cycles of the first system are interleaved with cycles of the second system.

What is claimed is:  
     
       1. A method of reclaiming memory space allocated to data structures comprising data objects linked by identifying pointers, in which the memory allocated to data objects is reclaimed using two systems: 
       a first system, by which the data structures are traversed to identify those objects to which no references are made by the pointers of other objects, and reclaiming the memory allocated to those objects to which no references are made; and  
       a second system, which determines which objects are not descendants of root objects and reclaiming the memory allocated to those objects, wherein cycles of the first system are interleaved with cycles of the second system, and wherein the memory space is traversed in a first direction during even numbered cycles and is traversed in a second, alternate, direction during odd numbered cycles.  
     
     
       2. A method as claimed in  claim 1 , wherein the second system determines which objects are descendants of root objects from a mark associated with each object, which mark has been set by the first system if the object is a descendant of a root object. 
     
     
       3. A method as claimed in  claim 1 , wherein the cycles of the first system reclaim the memory allocated to a group of data objects the pointers of which reference each other but none of which are referred to by the pointer of a root object. 
     
     
       4. A method as claimed in  claim 1 , wherein the interleaving of first and second systems is performed according to predetermined criteria. 
     
     
       5. A method as claimed in  claim 4 , wherein the predetermined criteria perform cycles of the first system until no unreferenced objects are found, followed by a cycle of the second system. 
     
     
       6. A method as claimed in  claim 4 , wherein a cycle of the first system is interleaved between cycles of the second system. 
     
     
       7. A method as claimed in  claim 4 , wherein a first number of cycles of the first system are interleaved between a second number of cycles of the second system. 
     
     
       8. A method as claimed in  claim 7 , wherein a first mark is associated with objects referenced by pointers of other objects found during the traversal in the first direction. 
     
     
       9. A method as claimed in  claim 8 , wherein a second mark is associated with objects referenced by pointers of other objects found during the traversal in the second direction. 
     
     
       10. A method as claimed in  claim 9 , wherein an object found to be unreferenced by pointers of other objects traversed in one direction and not having the mark from a prior traversal in the alternate direction is deleted. 
     
     
       11. A data processing apparatus comprising a data processor coupled with a random access memory containing data structures comprising data objects linked by identifying pointers, the processor being configured to provide the following for operating on the stored plurality of data objects: 
       first means for traversing the data structures to identify those objects to which no references are made by the pointers of other objects, and for reclaiming the memory allocated to those objects to which no references are made; and  
       second means for determining which objects are not descendants of root objects and for reclaiming the memory allocated to those objects, wherein cycles of the first means are interleaved with cycles of the second means, and wherein the memory space is traversed in a first direction during even numbered cycles and is traversed in a second, alternate, direction during odd numbered cycles.  
     
     
       12. A data processing apparatus as claimed in  claim 11 , wherein the second means determines which objects are descendants of root objects from a mark associated with each object, which mark has been set by the first system if the object is a descendant of a root object. 
     
     
       13. A data processing apparatus as claimed in  claim 11 , comprising means for associating a first mark with objects referenced by pointers of other objects found during the traversal in the first direction. 
     
     
       14. A data processing apparatus as claimed in  claim 13 , comprising means for associating a second mark with objects referenced by pointers of other objects found during the traversal in the second direction. 
     
     
       15. A data processing apparatus as claimed in  claim 14 , further comprising means for deleting an object found to be unreferenced by pointers of other objects traversed in one direction and not having the mark from a prior traversal in the alternate direction. 
     
     
       16. A data processing apparatus as claimed in  claim 11 , comprising means for monitoring changes to pointers referencing objects, wherein the first means only traverses a data structure to identify those objects to which no references are made by the pointers of other objects when a change to a pointer referencing a constituent object of the data structure occurs. 
     
     
       17. A data processing apparatus as claimed in  claim 16 , comprising means for deleting a uniquely referenced object if a change to a pointer which