System and method for garbage collection with ambiguous roots

• US 4,907,151 A
• Filed: 09/30/1988
• Issued: 03/06/1990
• Est. Priority Date: 09/30/1988
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Bartlett, Joel F.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US07/251,554
• Time in Patent Office: 522 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300 MS File
• US Class Current: 711/166
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/702 Conservative garbage collection

Abstract

In a computer system, a dynamic memory allocation and recovery system and method, sometimes referred to as a garbage collection system and method, provides a heap of storage space for storing program objects generated by a task. The heap is divided into pages whose size is independent of physical page sizes used by the computer system. Pages are denoted an unallocated or allocated for storing program objects. A root stroage area stores information called hints regarding program objects stored in the heap. The hints can include ambiguous pointers which may or may not point to program objects stored in the heap. Garbage collection is performed by promoting and retaining all pages in the heap which are referenced by hints, and by copying into previously unallocated pages all other accessible program objects in the heap. All pointers to the copied program objects are replaced with pointers to the new copies of those program objects. As a result, all program objects located in pages pointed to by ambiguous pointers are left in their original position, and only the pointers to the copied program objects are replaced with pointers to the new copies of the program objects. After garbage collection, the set of allocated pages for the task includes all promoted and retained pages pointed to by ambiguous pointers as well as all pages containing the new copies of the copied program objects. All other pages in the heap become the unallocated pages available for storing new program objects generated by the task.

Claims

1. A garbage collection method for recovering unused memory in a heap of dynamically allocated storage, the steps of the method comprising:

dividing a heap of storage into a multiplicity of pages;

labelling as allocated pages each page in said heap allocated for storing program objects, and labelling as unallocated pages all other pages of the heap;

identifying a root set of hints which point directly and indirectly to all of the accessible program objects stored in said heap, said program objects storing additional hints pointing to other ones of said program objects;

said hints including unambiguous pointers to program objects stored in said heap and ambiguous pointers which may or may not point to program objects stored in said heap;

labelling as promoted pages, pages labelled as allocated and pointed to by ambiguous pointers in said root set and in said accessible program objects; and

copying all said accessible program objects, excepting those in promoted pages, to newly allocated pages in said heap;

said steps of labelling promoted pages and copying including the steps of labelling said promoted pages and newly allocated pages as allocated pages, and labelling all other pages in said heap as unallocated pages.

2. The garbage collection method as set forth in claim 1, said copying step including the step of replacing unambiguous pointers to the program objects copied by said copying step with pointers to the copies of said program objects created by said copying step.

3. A garbage collection system for recovering unused memory in a heap of dynamically allocated storage, comprising:

heap organizing means for dividing a heap of storage into a multiplicity of pages, and for labelling as allocated pages each page in said heap allocated for storing program objects, and labelling as unallocated pages all other pages of the heap;

root means for identifying a root set of hints which point directly and indirectly to all of the accessible program objects stored in said heap, said program objects storing additional hints pointing to other ones of said program objects;

said hints including unambiguous pointers to program objects stored in said heap and ambiguous pointers which may or may not point to program objects stored in said heap;

relabelling means for labelling as promoted pages, pages labelled as allocated and pointed to by ambiguous pointers in said root set and in said accessible program objects; and

copying means for copying all said accessible program objects, excepting those in promoted pages, to newly allocated pages in said heap;

said relabelling and copying means including means for labelling said promoted pages and newly allocated pages as allocated pages, and for labelling all other pages in said heap as unallocated pages.

4. The garbage collection system set forth in claim 3, said copying means including means for replacing unambiguous pointers to the program objects copied by said copying means with pointers to the copies of said program objects created by said copying means.

5. A dynamic memory allocation and recovery method, comprising the steps of:

providing a heap of storage space for storing program objects, said heap being divided into a multiplicity of pages, and labelling means for denoting each said page as unallocated, allocated and newly allocated for storing program objects;

providing a root set of hints directly and indirectly pointing to all accessible program objects stored in said heap, said hints including unambiguous pointers to program objects stored in said heap and ambiguous pointers which may or may not point to program objects stored in said heap;

said program objects containing additional pointers to other ones of said program objects;

labelling as retained pages the allocated pages in said heap pointed to by said ambiguous pointers;

copying into newly allocated pages of said heap said accessible program objects, excluding program objects stored in said retained pages;

replacing pointers to the program objects copied by said copying step with pointers to the copies of said program objects created by said copying step; and

identifying as allocated pages said retained pages and said newly allocated pages containing program objects which were copied by said copying step, and identifying all other pages as unallocated.

6. A dynamic memory allocation and recovery method as set forth in claim 5, said garbage collection step including the step of identifying ambiguous pointers in said program objects and retaining the allocated pages in said heap pointed to by said ambiguous pointers.

7. A computer memory managment system, comprising:

means for providing a heap of storage space for storing program objects generated by a task, said heap being divided into a multiplicity of pages;

means for denoting said pages in said heap as unallocated, allocated and newly allocated to said task;

dynamic storage means for dynamically allocating pages of said heap to said task and for storing program objects in said allocated pages;

a root storage area for storing unambiguous pointers and ambiguous pointers to said program objects stored in said heap;

said dynamic storage means including means for storing pointers to said stored program objects in said root storage are and in other ones of said program objects stored in said heap;

said pointers in said root set thereby providing access to the set of accessible program objects in said heap; and

garbage collection means for reducing the number of pages in said heap occupied by said set of accessible program objects in said heap, said garbage collection means including;

means for denoting as retained pages the allocated pages in said heap pointed to by said ambiguous pointers;

means for copying into newly allocated pages of said heap program objects pointed to by said unambiguous pointers in said root storage area and in said set of accessible program objects in said heap;

means for replacing unambiguous pointers to the program objects copied by said copying means with pointers to the copies of said program objects created by said copying means, excepting pointers, if any, to program objects located in said retained pages; and

means for denoting as allocated pages said retained pages and said newly allocated pages containing the copies of program objects made by said copying means, and for denoting all other pages in said heap as unallocated.

8. A computer memory managment system as set forth in claim 7, including means for storing ambiguous pointers in selected ones of said accessible program objects;

said means for denoting retained pages including means for denoting as retained the allocated pages in said heap, if any, pointed by said ambiguous pointers stored in said accessible program objects.

9. A computer memory managment system as set forth in claim 8,

said copying means including means for leaving a forwarding pointer in each said copied program object to the copy of said program object made by said copying means;

said replacing means including means for replacing each pointer in said copies of said program objects with said forwarding pointer in the program object pointed to by said pointer.

10. A computer memory managment system as set forth in claim 8, including means for replacing each pointer in those of said program objects in said retained pages which have been copied by said copying means with the corresonding pointer in the copy of said program object.