Incremental, multi-area, generational, copying garbage collector for use in a virtual address space

• US 4,797,810 A
• Filed: 06/26/1986
• Issued: 01/10/1989
• Est. Priority Date: 06/26/1986
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: McEntee, Timothy J., Bloemer, Robert W., Oxley, Donald W., Thatte, Satish M.
• Primary Examiner(s): Williams, Jr., Archie E.
• Assistant Examiner(s): Mohamed, Ayni
• Application Number:
  US06/878,551
• Time in Patent Office: 929 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

An incremental garbage collector for use in conjunction with a virtual memory, operates on selected generations of an area upon objects which are contained in a semispace, oldspace or newspace, and during the garbage collection process, all accessible objects are copied from the oldspace to the newspace. The garbage collection process occurs in four phases. In the "flip" phase oldspace and newspace of each generation are exchanged. In the "trace" phase, the pointers which are part of a root set of the generation being collected are traced and all oldspace objects referenced by the pointers are copied to newspace, and the pointers in the root set are updated. All copied objects are then "scavenged" to update any pointers in the cells of the copied objects, and to copy to newspace all oldspace objects referenced by those pointers. Finally a "cleaning oldspace" phase is performed as a low-priority background process to purge the entries for the virtual pages on which "obsolete" pointers reside.

Claims

1. A method for managing a virtual memory of a computer system, such virtual memory having a main memory and a backing store, and a plurality of virtual pages in each of the main memory and the backing store, comprising the steps of:

(a) dividing the virtual memory into at least two areas, each area containing a plurality of pages, and capable of storing a plurality of objects;

(b) dividing each area into at least two generations, each generation containing a plurality of pages, and capable of storing a plurality of objects, wherein the generations in each area are ordered from youngest to oldest, with an older generation containing objects which have survived more garbage collection processes than those contained in a younger generation;

(c) for each generation within each area, providing a first trouble pointers data structure which identifies the locations of trouble pointers for that generation, wherein a trouble pointer is considered to be (1) a pointer from within the same area but originating from an older generation, or (2) a pointer originating from another area;

(d) providing a second trouble pointers data structure which indicates, for each page currently located in the main memory, whether that page has contained, since such page was last loaded into the main memory, any pointers which are trouble pointers for another generation or area;

(e) whenever a page is copied into the main memory from the backing store, scanning such page for pointers to other areas or younger generations within the same area, whereby any pointers so found are trouble pointers;

(f) for each page in which trouble pointers are found in step (e), providing a trouble pointers page-in list containing all trouble pointers which were found in step (e);

(g) whenever a page is copied from the main memory to the backing store, scanning such page for trouble pointers as in step (e), and comparing any trouble pointers so found with the trouble pointers page-in list provided in step (f);

(h) whenever step (g) indicates that a page being written to the backing store has different trouble pointers that when that page was copied into the main memory, updating the first trouble pointers data structures of the generations, which are referenced by those trouble pointers which have been changed; and

(i) periodically performing garbage collection on generations within areas, wherein each such generation has a root set which includes all trouble pointers into that generation as defined by the corresponding first trouble pointers data structure, and wherein all pages which are indicated by the second trouble pointers data structure as having contained trouble pointers are scanned for trouble pointers which point to the generation being collected, with any such pointers being included in the root set thereof.

2. The method of claim 1, wherein the first trouble pointers data structure is a B-tree.

3. The method of claim 1, wherein the second trouble pointers data structure is a bit map.

4. The method of claim 1, wherein the second trouble pointers data structure contains a plurality of bit maps, with a bit map assigned to at least one selected generation, wherein the bit map assigned to such selected generation indicates which pages currently located in memory have contained trouble pointers which point into such selected generation, and wherein garbage collection performed on such selected generation in step (i) includes scanning the bit map assigned to such selected generation for pointers to be included in the root set thereof.

5. The method of claim 4, further including providing an active generations table which indicates which generations within areas are selected generations and therefore have an assigned bit map.

6. The method of claim 4, wherein the second trouble pointers data structure further includes a default bit map which indicates which pages currently located in memory have contained trouble pointers which point only into non-selected generations which do not have an assigned bit map, and wherein garbage collection performed on such non-selected generations in step (i) includes scanning the default bit map for pointers to be included in the root set thereof.

7. The method of claim 1, wherein step (k) utilizes a copying garbage collector.

8. The method of claim 1, wherein step (h) comprises:

(h.1) for trouble pointers which are contained in the page being written out to the backing store and which are not contacted in the trouble pointers page-in list for that page, identifying such trouble pointers in the first trouble pointers data structures for the generations within areas to which such trouble pointers point;

(h.2) for trouble pointers which are contained in the trouble pointers page-in list for a page and which are not contained in that page when it is written out to the backing store, deleting references thereto from the first trouble pointers data structures for the generations within areas to which such trouble pointers contained only in the trouble pointers page-in list point; and

(h.3) for trouble pointers which are contained in the trouble pointers page-in list for a page and which are also contained in that page when it is written out to the backing store, making no changes to any first trouble pointers data structures.

9. A garbage collectible memory for a computer system, comprising:

a virtual memory having a plurality of pages, such virtual memory implemented as a main memory backed by a backing store wherein pages are copied from the backing store to main memory and from the main memory to the backing store;

at least two areas, each area containing a plurality of virtual memory pages;

at least two generations within each area, each generation containing a plurality of virtual memory pages, wherein the generations within each area are ordered from youngest to oldest, with an older generation within an area containing memory objects which have survived more garbage collection processes than those contained in a younger generation;

a first trouble pointers data structure within each generation which identifies trouble pointers into that generation, wherein a trouble pointer is considered to be (1) a pointer from within the same area but originating from an older generation, or (2) a pointer originating from another area;

a second trouble pointers data structure which indicates, for each page currently located in the main memory, whether such page has contained, since such page was last copied into the main memory, any pointers which are trouble pointers for another generation or area;

a trouble pointers page-in list containing all trouble pointers which were located in each page in the main memory at the time such pages were copied into main memory from the backing store;

a trouble pointers page-out list containing all trouble pointers located in a page currently being copied from the main memory to the backing store;

means connected to said trouble pointers page-in list and to said trouble pointers page-out list for updating the first trouble pointers data structures of those generations in which trouble pointers have changed between the page-in list and the page-out list for the page currently being copied from main memory to the backing store; and

a copying garbage collector which collects each generation of each area independently, wherein a root set of any generation being collected includes any pointers contained in the first trouble pointer data structure of such generation, and any pointers contained in pages in main memory which are indicated by said second trouble pointers list as containing trouble pointers and which point into such generation being collected.

10. The method of claim 9, wherein the first trouble pointers data structure is a B-tree.

11. The method of claim 9, wherein the second trouble pointers data structure is a bit map.