Method and system for concurrent garbage collection

• US 6,502,111 B1
• Filed: 07/31/2000
• Issued: 12/31/2002
• Est. Priority Date: 07/31/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dussud, Patrick H.
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/629,031
• Time in Patent Office: 883 Days
• Field of Search: 707/206, 709/1, 709/107, 709/315, 714/9, 717/162
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and system for concurrent garbage collection wherein live memory objects, i.e., not garbage, can be marked while an application executes. Root information is gleaned by taking a snapshot program roots or by arranging the stack to be scanned during execution of the program. Next, a first marking act is performed using the root information while the program executes. Modifications in the memory structure that occur during the concurrent marking act are logged or accumulated by a write watch module. The application is then paused or stopped to perform a second marking act using information from the write watch module. Following the second marking act, the garbage collection may be completed using various techniques.

Claims

1. A method of marking memory objects for collecting garbage in a computer system, said method comprising:

getting root information, the root information having object references to memory objects;

accumulating modification information, the modification information related to memory objects modified following the getting of root information;

marking reachable memory objects using the root information; and

following the marking operation, revisiting modified memory objects identified by the accumulated modification information, wherein the revisiting act marks the revisited memory object.

2. A method as defined in claim 1 wherein an application thread modifies the memory objects and the accumulating act is performed independently of the application thread.

3. A method as defined in claim 1 wherein the computer system further comprises a write watch module and the act of accumulating modification information is performed by the write watch module.

4. A method as defined in claim 3 wherein the computer system further comprises at least one executing application and a stack of memory information, wherein the method further comprises:

following the act of revisiting the modified memory objects, pausing an executing application; and

marking at least one unvisited memory object from the stack.

5. A method as defined in claim 1 wherein prior to pausing the executing application, the revisiting and marking act is repeated until the modification information is below a predetermined threshold.

6. A method as defined in claim 1 wherein prior to the revisiting and marking act, unvisited memory objects are indicated using a first color, visited objects are indicated using a second color, and modified visited objects are indicated using a third color, wherein the modified visited objects are objects that have been modified after being visited.

7. A method of collecting garbage for an executing application in a computer system having memory and a root stack of object references, the computer system further having a plurality of allocated memory objects, the memory objects being unmarked, said method comprising the following:

pausing the executing application;

taking a snapshot of the root stack in memory;

initiating a write watch module to keep track of modifications in the memory;

restarting the application;

while the application is running, performing a first marking act of marking all reachable memory objects using snapshot information;

pausing the application;

performing a second marking act of marking all reachable memory objects identified by the write watch module;

collecting all objects left unmarked; and

restarting the application.

8. A method as defined in claim 7 further comprising:

following the first act of marking reachable objects, analyzing information from the write watch module related to the changes in the memory to determine whether an intermediate marking phase should be done before pausing the application a second time;

if the analysis step determines that an intermediate marking act should be performed, performing an intermediate marking act based on information from the write watch module.

9. A method as defined in claim 8 further comprising:

if an intermediate marking act is performed, repeating the analysis act and intermediate marking act until the analysis step determines that an intermediate marking act is not necessary.

10. A method as defined in claim 8 wherein the analysis of the information from the write watch module comprises:

comparing the number of modified memory objects to a predetermined threshold value;

if the number of modified memory objects is greater than the predetermined threshold value, determining that an intermediate marking act should be performed.

11. A method as defined in claim 10 wherein the predetermined threshold value relates to a percentage of the number of allocated memory objects.

12. A method as defined in claim 7 wherein the second marking act of marking modified memory objects is repeated a predetermined number of times.

13. A method as defined in claim 7 wherein the act of collection unmarked memory objects further comprises sweeping the memory and adding references to the unmarked memory to a free list.

14. A method as defined in claim 7 wherein the memory is divided into at least two memory portions and wherein all marked and unmarked objects are located in one of the memory portions, and wherein the act of collecting unmarked memory objects further comprises copying all marked objects to another memory portion.

15. A method as defined in claim 7 wherein the act of collecting unmarked memory objects further comprises:

planning the relocation of the marked memory objects;

updating object references located within other memory objects, wherein the updated object reference related to the new locations in memory as determined by the act of planning the relocation;

compacting the memory objects to relocate the memory objects; and

updating a reference pointer related to an end of the compacted memory.

16. A system for collecting garbage memory objects using a concurrent marking scheme, the system comprising:

a write watch module for accumulating information related to modified objects, wherein the write watch module maintains a bit map having at least one bit per memory object;

a root module for getting root information allowing the tracing memory objects that are live memory objects at the time of cloning the memory information;

a marking module for marking the memory objects traceable using the root information;

a revisiting module for revisiting modified memory objects using information accumulated by the write watch module; and

a finishing module for collecting all unmarked memory objects, where the unmarked memory objects are garbage objects.

17. A system as defined in claim 16 further comprising a testing module for determining whether another revisiting process should be completed prior to finishing the collection of unmarked objects.

18. A computer program product readable by a computer and encoding instructions for executing a computer process for marking memory objects as part of a garbage collection session, the process comprising:

getting root information, the memory information having object references to memory objects;

accumulating modification information, the modification information related to memory objects modified following the getting of root information;

marking reachable memory objects using the root information; and

following the marking operation, revisiting modified memory objects identified by the accumulated modification information, wherein the revisiting act marks the revisited memory object.

19. A computer program product as defined in claim 18 wherein the computer further comprises a write watch module and the act of accumulating modification information is performed by the write watch module.

20. A computer program product as defined in claim 19 wherein the computer further comprises at least one executing application and a stack of memory information, wherein the method further comprises:

following the act of revisiting the modified memory objects, pausing an executing application; and

marking at least one unvisited memory object from the stack.

21. A computer program product as defined in claim 18 wherein prior to pausing the executing application, the revisiting and marking act is repeated until the modification information is below a predetermined threshold.

22. A computer program product as defined in claim 18 wherein prior to the revisiting and marking act, unvisited memory objects are indicated using a first color, visited objects are indicated using a second color, and modified visited objects are indicated using a third color, wherein the modified visited objects are objects that have been modified after being visited.

23. A computer program product readable by a computer system and encoding instructions for executing a computer process for marking memory objects as part of a garbage collection session, the computer system memory and a root stack of object references, the computer system further comprising a plurality of allocated memory objects, the memory objects being unmarked, said process comprising:

pausing the executing application;

taking a snapshot of the root stack in memory;

initiating a write watch module to keep track of modifications in the memory;

restarting the application;

while the application is running, performing a first marking act of marking all reachable memory objects using snapshot information;

pausing the application;

performing a second marking act of marking all reachable memory objects identified by the write watch module;

collecting all objects left unmarked; and

restarting the application.

24. A computer program product as defined in claim 23 wherein the process further comprises:

following the first act of marking reachable objects, analyzing information from the write watch module related to the changes in the memory to determine whether an intermediate marking phase should be done before pausing the application a second time;

if the analysis step determines that an intermediate marking act should be performed, performing an intermediate marking act based on information from the write watch module.

25. A computer program product as defined in claim 24 wherein the process further comprises:

if an intermediate marking act is performed, repeating the analysis act and intermediate marking act until the analysis step determines that an intermediate marking act is not necessary.

26. A computer program product as defined in claim 25 wherein the process further comprises:

comparing the number of modified memory objects to a predetermined threshold value;

if the number of modified memory objects is greater than the predetermined threshold value, determining that an intermediate marking act should be performed.

27. A computer program product as defined in claim 26 wherein the predetermined threshold value relates to a percentage of the number of allocated memory objects.

28. A computer program product as defined in claim 23 wherein the second marking act of marking modified memory objects is repeated a predetermined number of times.

29. A computer program product as defined in claim 23 wherein the act of collection unmarked memory objects further comprises sweeping the memory and adding references to the unmarked memory to a free list.

30. A computer program product as defined in claim 23 wherein the memory is divided into at least two memory portions and wherein all marked and unmarked objects are located in one of the memory portions, and wherein the act of collecting unmarked memory objects further comprises copying all marked objects to another memory portion.

31. A computer program product as defined in claim 23 wherein the act of collecting unmarked memory objects further comprises:

planning the relocation of the marked memory objects;

updating object references located within other memory objects, wherein the updated object reference related to the new locations in memory as determined by the act of planning the relocation;

compacting the memory objects to relocate the memory objects; and

updating a reference pointer related to an end of the compacted memory.