Incremental lock-free stack scanning for garbage collection

摘要

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#.

主权项

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; anda 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.