Method and apparatus for facilitating mark-sweep garbage collection with reference counting

1. A method for facilitating garbage collection (GC) in a memory-management system that supports both mark-sweep (MS) objects and reference-counted (RC) objects, wherein both MS objects and RC objects can be marked and have a reference count, the method comprising:

during a marking phase of a GC operation in a memory-management system,

identifying roots for the GC operation,

marking referents of the roots, and

recursively traversing referents of the roots which are MS objects and while doing so, marking referents of the traversed MS objects, wherein while recursively traversing referents of the roots which are MS objects, when a referent is identified as an RC object, the referent is marked but is not recursively traversed; and

during a subsequent sweeping phase of the GC operation, reclaiming objects that are unmarked and have a zero reference count, wherein marked RC objects are not reclaimed,

wherein objects which are frequently modified are classified as MS objects; and

wherein objects which are infrequently modified are classified as RC objects.

2. The method of claim 1 , wherein both MS objects and RC objects contain:

an indicator bit indicating whether the object is an MS object or an RC object;

a mark bit indicating whether the object is marked or unmarked; and

a reference counter, which maintains a reference count for the object.

3. The method of claim 1 , wherein identifying roots for the GC operation involves identifying MS objects with non-zero reference counts.

4. The method of claim 1 , wherein while recursively traversing referents of the roots, if a referent is identified as an RC object, the referent is marked but is not recursively traversed.

5. The method of claim 2 :

wherein an RC object, which contains a reference to a referent, which is either an MS object or and RC object, contributes one to the referent's reference count; and

wherein an MS object which contains a reference to a referent, which is either an MS object or an RC object, does not contribute to the referent's reference count.

6. The method of claim 1 , further comprising:

receiving a command to modify a reference within an object to point to a new referent; and

if the object is an RC object, decrementing the reference count in a previous referent for the reference and incrementing the reference count in the new referent for the reference.

7. The method of claim 2 , wherein an object can be converted from an MS object to an RC object by:

changing the indicator bit of the object to indicate that the object is an RC object; and

incrementing reference counts for all referents of the object.

8. The method of claim 2 , wherein an object can be converted from an RC object to an MS object by:

changing the indicator bit of the object to indicate that the object is an MS object; and

decrementing reference counts for all referents of the object.

9. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for facilitating garbage collection (GC) in a memory-management system that supports both mark-sweep (MS) objects and reference-counted (RC) objects, wherein both MS objects and RC objects can be marked and have a reference count, the method comprising:

during a marking phase of a GC operation,

identifying roots for the GC operation,

marking referents of the roots, and

recursively traversing referents of the roots which are MS objects and while doing so, marking referents of the traversed MS objects, wherein while recursively traversing referents of the roots which are MS objects, when a referent is identified as an RC object, the referent is marked but is not recursively traversed; and

during a subsequent sweeping phase of the GC operation, reclaiming objects that are unmarked and have a zero reference count, wherein marked RC objects are not reclaimed,

wherein objects which are frequently modified are classified as MS objects; and

wherein objects which are infrequently modified are classified as RC objects.

10. The computer-readable storage medium of claim 9 , wherein both MS objects and RC objects contain:

an indicator bit indicating whether the object is an MS object or an RC object;

a mark bit indicating whether the object is marked or unmarked; and

a reference counter, which maintains a reference count for the object.

11. The computer-readable storage medium of claim 9 , wherein identifying roots for the GC operation involves identifying MS objects with non-zero reference counts.

12. The computer-readable storage medium of claim 9 , wherein while recursively traversing referents of the roots, if a referent is identified as an RC object, the referent is marked but is not recursively traversed.

13. The computer-readable storage medium of claim 10 ,

wherein an RC object, which contains a reference to a referent, which is either an MS object or and RC object, contributes one to the referent's reference count; and

wherein an MS object which contains a reference to a referent, which is either an MS object or an RC object, does not contribute to the referent's reference count.

14. The computer-readable storage medium of claim 9 , further comprising:

receiving a command to modify a reference within an object to point to a new referent; and

if the object is an RC object, decrementing the reference count in a previous referent for the reference and incrementing the reference count in the new referent for the reference.

15. The computer-readable storage medium of claim 10 , wherein an object can be converted from an MS object to an RC object by:

changing the indicator bit of the object to indicate that the object is an RC object; and

incrementing reference counts for all referents of the object.

16. The computer-readable storage medium of claim 10 , wherein an object can be converted from an RC object to an MS object by:

changing the indicator bit of the object to indicate that the object is an MS object; and

decrementing reference counts for all referents of the object.

17. A computer system that facilitates garbage collection (GC) in a memory-management system that supports both mark-sweep (MS) objects and reference-counted (RC) objects, wherein both MS objects and RC objects can be marked and have a reference count, the apparatus comprising:

a processor;

a memory;

an identification mechanism implemented in the computer system and configured to identify roots for a GC operation during a marking phase of the GC operation;

a marking mechanism implemented in the computer system and configured to mark referents of the roots during the marking phase of the GC operation;

a traversing mechanism implemented in the computer system and configured to recursively traverse referents of the roots which are MS objects during the marking phase of the GC operation and while doing so, marking referents of the traversed MS objects, wherein while recursively traversing referents of the roots which are MS objects, when a referent is identified as an RC object, the referent is marked but is not recursively traversed; and

a reclamation mechanism implemented in the computer system and configured to reclaim objects that are unmarked and have a zero reference count during a subsequent sweeping phase of the GC operation, wherein marked RC objects are not reclaimed,

wherein objects which are frequently modified are classified as MS objects; and

wherein objects which are infrequently modified are classified as RC objects.

18. The computer system of claim 17 , wherein both MS objects and RC objects contain:

an indicator bit indicating whether the object is an MS object or an RC object;

a mark bit indicating whether the object is marked or unmarked; and

a reference counter, which maintains a reference count for the object.