Incremental lock-free stack scanning for garbage collection

• US 20100114998A1
• Filed: 10/30/2008
• Published: 05/06/2010
• Est. Priority Date: 10/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kliot, Gabriel, Petrank, Erez, Steensgaard, Bjarne
• Granted Patent: US 8,825,719 B2
• Time in Patent Office: Days
• US Class Current: 707/813
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence

Abstract

Concurrent, incremental, and lock-free stack scanning for garbage collectors is disclosed. This method uses a summary table and return barriers to allow high responsiveness. The method also supports programs that employ fine-synchronization to avoid locks, imposes negligible overhead on program execution, can be used with existing concurrent collectors, and supports the special in-stack references existing in languages such as C#.

Claims

1. A system of incremental lock free stack frame scanning, the system comprising:

a mutator stack comprising a mutator stack frame, the stack frame comprising a pointer value;

a summary data structure comprising a summary of the mutator stack frame;

a mutator reading the mutator stack frame and creating a summary of the pointer value and inserting the summary of the pointer value into the summary data structure when an atomic insertion operation is successful, the mutator being permitted to read, or modify, or both, the mutator stack, and wherein the mutator inserts the summary into the summary data structure before modifying the contents of the mutator stack frame; and

a garbage collector concurrently reading the mutator stack frame and creating a summary of the pointer and inserting the summary of the pointer into the summary data structure when an atomic insertion operation is successful, the garbage collector being permitted to read the mutator stack.

2. The system of claim 1 wherein the insertion operation comprises a compare-and-swap, or a double compare-and-swap, or a load-linked/store-conditional pair of instructions.

3. The system of claim 1 further comprising the mutator installing a return barrier after the atomic insertion operation.

4. The system of claim 1 further comprising the garbage collector utilizing the summary data structure to find a root set.

5. A system comprising;

a memory comprising a computer readable storage medium;

a processor coupled to the memory; and

a garbage collector and a mutator stored in the memory and configured to execute on the processor and concurrently scan a stack comprising stack frames.

6. The system of claim 5 wherein the garbage collector is configured to read from the stack frame and the mutator is configured to read, or modify, or both, to the stack frame.

7. The system of claim 5 wherein the garbage collector and mutator are configured to update a summary data structure using an atomic insertion operation, the update occurring during separate concurrent scans of the stack by the garbage collector and the mutator.

8. The system of claim 7 wherein the summary data structure is used to determine garbage in memory.

9. The system of claim 7 wherein the summary data structure comprises pointer values from the stack.

10. The system of claim 7 wherein the mutator is configured to insert summary data into the summary data structure before modifying the contents of the stack frame.

11. The system of claim 7 wherein the insertion operation comprises a compare-and-swap, or a double compare-and-swap, or a load-linked/store-conditional pair of instructions, or a read-modify-write operation.

12. The system of claim 7 wherein the mutator is configured to install a return barrier after the atomic insertion operation

13. The system of claim 5 wherein the mutator and the garbage collector are configured to execute on the processor as separate threads.

14. A method comprising;

scanning a stack comprising stack fragments concurrently with a garbage collector and a mutator;

updating a summary data structure using an atomic insertion operation initiated by the garbage collector or the mutator, wherein the updating occurs during separate concurrent scans of the stack by the garbage collector and the mutator;

permitting the garbage collector to read from the stack; and

permitting the mutator to read, or write, or both, to the stack.

15. The method of claim 14 further comprising using the information in the summary data structure as the basis for garbage collection.

16. The method of claim 14 wherein the summary data structure comprises a pointer value from the stack.

17. The method of claim 14 wherein the method is stored on a computer-readable storage medium.

18. The method of claim 14 further comprising the mutator inserting summary data into the summary data structure before modifying the contents of the stack fragment.

19. The method of claim 14 further comprising the mutator installing a return barrier.

20. The method of claim 14 wherein the garbage collector waits for the mutator to acknowledge readiness when the mutator is active in a managed language environment.