System and method for garbage collection with ambiguous roots

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.