Computer method and system for conservative-stack and generational heap garbage collection

• US 5,652,883 A
• Filed: 05/23/1995
• Issued: 07/29/1997
• Est. Priority Date: 06/15/1992
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Adcock, James L.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/448,238
• Time in Patent Office: 798 Days
• Field of Search: 395/622, 395/497.01, 395/497.02, 395/486
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 2212/702 Conservative garbage collection

Abstract

A method and system for conservative-stack and generational garbage collection for a computer memory is provided. In a preferred embodiment, the computer memory includes a stack and a heap. The heap comprises a plurality of objects each of which is identified as new or old. During run time, a list of old objects that contain pointers to new objects is maintained. During garbage collection time, each new object that is accessible through an old object in the list is marked as accessible. The stack contains a plurality of stack entry that may be pointers to new objects. During garbage collection time, each stack entry is checked to see if it could point to a new object. Each new object that a stack entry could point to is marked as accessible and each new object that is accessible through the marked objects is also marked as accessible. During memory compaction, the new objects that are not marked as accessible are reclaimed.

Claims

1. A method in a computer system for marking data objects in a computer memory, each object being identified by a pointer, the memory including a stack and a heap, the heap having a plurality of old objects and a plurality of new objects, the memory including a list of pointers to a plurality of old objects that contain a pointer to a new object, the stack having stack entries, each stack entry identifiable as being definitely not a pointer or being possibly a pointer, the method comprising the steps of:

identifying whether each stack entry is definitely not a pointer or possibly a pointer;

for each new object possibly pointed to by a stack entry that is identified as possibly a pointer, marking the new object as accessible and locked, and marking each new object that is accessible through the marked object as accessible; and

for each old object that is pointed to by a pointer in the list of pointers, marking each new object that is pointed to by a pointer contained in the old object as accessible and marking each new object that is accessible through the marked objects as accessible so that during heap compaction, the locked objects are not moved and the accessible objects that are not locked are moved to consolidate free space of the heap.

2. The method of claim 1 wherein the steps of marking each new object that is accessible through a marked object as accessible do not mark those new objects that are accessible from the marked object only through an old object.

3. A method of garbage collection in a computer system, the computer system having a stack and a heap, the heap having a plurality of new objects and a plurality of old objects, the stack having stack entries, each object being identified by a pointer, the method comprising the steps of:

when an old object contains a pointer that is set to point to a new object, remembering the old object; and

during garbage collection,

identifying each stack entry as definitely not a pointer or as possibly a pointer;

marking each new object possibly pointed to by a stack entry identified as possibly a pointer as accessible and locked;

marking each new object pointed to by a remembered object as accessible;

marking each new object that is accessible through a previously marked object as accessible; and

reclaiming the memory used for new objects not marked as accessible by moving new objects that are accessible and not locked and by not moving objects that are accessible and locked.

4. A method of memory compaction in computer system, the computer system having a memory, the memory having a multiplicity of memory locations, the memory for storing a plurality of objects, each object having a size indicating the number of memory locations that comprise the object, each object being accessible or inaccessible, each accessible object being locked or not locked, the objects being ordered from a first object to a last object, each object that is accessible and not locked having a reference pointer that points to the object, the method comprising the steps of:

initializing a memory pointer to point to the first object in the memory; and

for each object in the memory, starting with the first object and proceeding in order to the last object,

selecting the object; and

when the selected object is accessible and not locked,

when the size of the selected object is such that the selected object can be copied to the memory locations starting at the memory location pointed to by the memory pointer without overwriting a locked object, copying the selected object to the memory locations starting with the memory location pointed to by the memory pointer; and

when the size of the selected object is such that the selected object cannot be copied to the memory locations starting at the memory location pointed to by the memory pointer without overwriting a locked object, copying the selected object to the memory locations starting with the memory location after the locked object;

updating the reference pointer to the selected object, so that the reference pointer points to the copied object; and

advancing the memory pointer to point to a memory location after the copied object.

5. The method of claim 4 including the additional steps of:

when the size of the selected object is such that the selected object cannot be copied,

storing a dummy object starting at the memory pointed to by the memory pointer, such that the size of the dummy object does not overwrite a locked object; and

advancing the memory pointer to point to a location after the locked object.

6. A method of memory compaction in computer system, the computer system having a memory with a multiplicity of memory locations and a plurality of objects, each object comprising one or more memory locations, the objects being ordered from a first object to a last object, each object being accessible or inaccessible, each accessible object being locked or not locked, each object that is accessible and not locked having a reference pointer that points to the object, the method comprising the steps of:

moving a plurality of accessible objects, wherein accessible objects that are not locked are moved, and wherein accessible objects that are locked are not moved and wherein the ordering of the accessible and not locked objects is maintained after moving; and

adjusting the reference pointer of each moved object to point to the moved to location.

7. The method of claim 6 wherein the step of moving moves the accessible and not locked objects to memory locations previously occupied by an accessible and not locked object already moved or by an inaccessible object.

8. A garbage collector in a computer system comprising:

a stack located in computer memory having a plurality of stack entries;

a heap located in the computer memory having a plurality of new and old objects;

a remember list identifying old objects that contains pointers to new objects;

a process stack pointer routine wherein each stack entry is identified as being either possibly a pointer or not a pointer to a new object;

a process possibly a pointer routine wherein each new object pointed to by a stack entry that is identified as possibly a pointer is marked as accessible and locked;

a process remember list routine wherein new objects pointed to by an old object identified in the remember list are marked as accessible;

a check embedded pointers routine wherein new objects that are accessible through a new object that is marked as accessible are marked as accessible; and

a reclamation routine wherein each object that is not marked as accessible is reclaimed by moving accessible objects, wherein accessible objects that are not locked are moved and accessible objects that are locked are not moved.

9. A method for garbage collecting in a computer system having a stack with stack entries and having a heap with new and old objects, the method comprising the steps of:

conservatively determining whether each stack entry is a pointer to an object;

remembering which old objects contain pointers to new objects;

reclaiming new objects that are not accessible through a stack entry conservatively determined to be a pointer and that are not accessible through a remembered old object;

and coalescing the heap by moving new objects that are accessible but not pointed to through a stack entry conservatively determined to be a pointer, wherein the objects of the heap have a relative position to one another and wherein the moving of new objects maintains the relative position of the moved objects.

10. The method of claim 9 wherein an object contains a data member and including the step of definitely determining whether the data member contains a pointer to a new object.

11. A garbage collector for a computer system having a stack and a heap, the stack having stack entries, the heap having new and old objects, comprising:

means for conservatively determining whether each stack entry points to a new object;

means for tracking old objects that contain pointers to new objects;

means for reclaiming new objects that are not accessible through a stack entry conservatively determined to be a pointer and that are not accessible through an old object that contains a pointer to a new object; and

means for coalescing the heap by moving new objects that are accessible but not pointed to through a stack entry conservatively determined to be a pointer, wherein the objects of the heap have a relative position to one another and wherein the means for reclaiming new objects maintains the relative position of the moved objects.

12. The garbage collector of claim 11 wherein an object contains a data member and including means for definitely determining whether the data member contains a pointer to a new object.

13. A method of garbage collection in a computer system, the computer system having a heap, the heap having a plurality of objects, the computer system having a plurality of data values that are definitely references to objects and plurality of data values that are possibly references to objects, the method comprising the steps of:

marking each object possibly referred to by a data value as accessible and locked;

marking each object definitely referred to by a data value as accessible;

marking each object that is accessible through a previously marked object as accessible; and

compacting the heap wherein objects that are locked are not moved and objects that are accessible and not locked are moved so as to coalesce portions of the heap that are not accessible.

14. The method of claim 13 wherein the computer system includes a stack and the data values that are possibly references to objects are contained within the stack.

15. The method of claim 13 wherein the step of compacting includes the step of moving objects that are accessible and not locked wherein the relative position of the moved objects is maintained.

16. The method of claim 13, including the step of designating each object as either old or new, and wherein the step of marking each object definitely referred to by a data value as accessible includes the step of marking only those new objects that are accessible from an old object and wherein the step of compacting includes the step of moving only new objects.