Incremental lock-free stack scanning for garbage collection

• US 8,825,719 B2
• Filed: 10/30/2008
• Issued: 09/02/2014
• Est. Priority Date: 10/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Steensgaard, Bjarne, Petrank, Erez, Kliot, Gabriel
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US12/261,920
• Publication Number:
  US 20100114998A1
• Time in Patent Office: 2,133 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 processor;

a memory coupled to the processor and comprising computer readable storage medium storing instructions that, when executed by the processor, configure the processor to implement computer components comprising;

a mutator stack comprising a mutator stack frame, the mutator 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 of the pointer value into the summary data structure before modifying the contents of the mutator stack frame and the mutator installs a return barrier after the atomic insertion operation; 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 garbage collector utilizing the summary data structure to find a root set.

4. A system comprising:

a memory comprising a computer readable storage medium;

a processor coupled to the memory;

a garbage collector stored in the memory and configured to execute on the processor, concurrently scan a stack comprising stack frames, and read from the stack frame; and

a mutator stored in the memory and configured to;

execute on the processor,

update a summary data structure comprising pointer values from the stack using an atomic insertion operation, during separate concurrent scans of the stack by the garbage collector and the mutator,

read, or modify, or both, the stack frame, and

install a return barrier after the atomic insertion operation.

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

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

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

8. The system of claim 5 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.

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

10. A method comprising:

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

updating a summary data structure in the computer system using an atomic insertion operation initiated by the garbage collector and updating the summary data structure in the computer system using an atomic insertion operation initiated by the mutator,

wherein each of the updatings occurs during separate concurrent scans of the stack by the garbage collector and the mutator, wherein the summary data structure comprises a pointer value from the stack;

permitting the garbage collector to read from the stack;

permitting the mutator to read, or write, or both, to the stack; and

installing, by the mutator, a return barrier after the atomic insertion operation.

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

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

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