Systems and methods for multiprocessor scalable write barrier

• US 6,973,554 B2
• Filed: 04/23/2003
• Issued: 12/06/2005
• Est. Priority Date: 04/23/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dussud, Patrick H.
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US10/422,116
• Publication Number:
  US 20040215914A1
• Time in Patent Office: 958 Days
• Field of Search: 711/159, 711/160, 711/165, 711/170, 707/206, 707/205, 709/104
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Systems and methods providing a multiprocessor scalable write barrier to a main memory card table are described. The main memory is divided into multiple cards bit-mapped by the card table. In one aspect, an application store operation (reference) associated with one of the cards is detected. Responsive to detecting the reference, card table bit(s) that are mapped to the card are evaluated. Responsive to determining that the bit(s) have already been marked as dirty, the card table bit(s) are not again marked. This technique effectively reduces the probability of more than a single overlapping write operation to a card table cache line by two or more processors in the system.

Claims

1. A computing device providing multiprocessor scalable write barrier to a card table in a main memory coupled to the computing device, the main memory having been divided into multiple cards that are bit-mapped by the card table, the computing device comprising:

means for detecting, by a garbage collector, an application reference to a card of the multiple cards;

means, responsive to detecting, for determining whether the main memory is being utilized by two or more processors in a symmetrical multiprocessing system (SMP);

if the main memory is not part of an SMP system;

means for card marking the one or more bits in response to the application reference;

if the main memory is part of an SMP system;

means for determining, by the garbage collector, that one or more bits of the card table have not been card marked, the one or more bits having been bit-mapped to the card; and

responsive the determining, means for eliminating, by the garbage collector, more than a single probability of an overlapping write operation to a cache line comprising the one or more bits by two or more processors of the computing system prior to a subsequent collection of an object(s) associated with the card.

2. A computing device as recited in claim 1, wherein the means for detecting, determining, and eliminating are part of a Common Language Runtime service.

3. A computing device as recited in claim 1, wherein the means for eliminating further comprise means for not card marking the one or more bits.

4. A computing device as recited in claim 1, wherein the means for bypassing reading operation further comprises means for skipping a card table check operation during code compilation.

5. A method providing multiprocessor scalable write barrier to a main memory, the main memory having been divided into multiple cards that are mapped by a card table, the method comprising operations of:

detecting an application store operation to a location in a card of the multiple cards;

responsive to detecting, determining whether the main memory is being utilized by two or more processors in a symmetrical multiprocessing system (SMP);

if the main memory is not part of an SMP system;

card marking the one or more bits in response to the application store operation;

if the main memory is part of an SMP system;

reading one or more bits of the card table, the one or more bits having been mapped to the card;

responsive to reading, if the one or more bits have already been marked;

not card marking the one or more bits;

wherein not card marking substantially reduces probability of an overlapping write operation to a card table cache line comprising the one or more bits by two or more processors.

6. A method as recited in claim 5, wherein bypassing reading operation is performed by a compiler and further comprises skipping a card table check operation when compiling at least a portion of code that is directed to performing the operations of detecting, reading, and not card marking.

7. A method as recited in claim 5, wherein the operations of detecting, reading, and not card marking are performed by a garbage collector (GC).

8. A method as recited in claim 5, wherein the operations of detecting, reading, and not card marking are part of a service provided by a Common Language Runtime.

9. A method as recited in claim 5, wherein the operations of detecting, reading, and not marking eliminates probability of more than a single overlapping write operation to the card table cache line before a subsequent garbage collection operation associated with the cache line.

10. A method as recited in claim 5, and wherein the method further comprises responsive to reading, if the one or more bits are not marked, card marking the one or more bits.

11. A computer-readable medium providing multiprocessor scalable write barrier to a main memory, the main memory having been divided into multiple cards that are mapped by a card table, the computer-readable medium comprising computer-program executable instructions executable by a processor for:

detecting, by a garbage collector, an application reference to a location in a card of the multiple cards;

responsive to detecting, determining whether the main memory is being utilized by two or more processors in a symmetrical multiprocessing system (SMP); and

if the main memory is not pan of an SMP system;

card marking, by the garbage collector, the one or more bits in response to the application reference;

if the main memory is part of an SMP system;

reading, by the garbage collector, one or more bits of the card table, the one or more bits having been mapped to the card;

responsive to reading;

if the one or more bits are not marked, card marking, by the garbage collector, the one or more bits, the card marking being an atomic write operation; and

if the one or more bits have already been marked, not card marking, by the garbage collector, the one or more bits to substantially guarantee a probability of at most only one processor-to-processor contention to a cache line comprising the one or more bits during a card marking operation.

12. A computer-readable medium as recited in claim 11, wherein the garbage collector is a service of a Common Language Runtime.

13. A computer-readable medium as recited in claim 11, wherein the computer-program instructions for bypassing the instructions for reading further comprise instructions for skipping a card table check operation when compiling at least a portion of the garbage collector.

14. A computing device providing multiprocessor scalable write barrier to a card table in main memory, the main memory having been divided into multiple cards that are bit-mapped by the card table, the computing device comprising a computer-readable medium, the computer-readable medium comprising computer-program executable instructions executable by a processor for:

detecting, by a Common Language Runtime Garbage Collector (CLR GC), an application reference directed to a card of the multiple cards;

determining whether the main memory is utilized by two or more processors in a symmetrical multiprocessing system (SMP);

if the main memory is not utilized by a SMP system;

card marking, by the garbage collector, the one or more bits in response to the application reference; and

wherein the instructions for bypassing scale the multiprocessor write barrier to a single processor system of the computing device;

if the main memory is utilized by a SMP system;

reading, by the CLR GC, of one or mare bits of the card table, the one or more bits having been bit-mapped to the card;

responsive to reading, if the one or more bits have already been marked, substantially guaranteeing a probability of at most only one processor-to-processor contention to a cache line comprising the one or more bits.

15. A computing device as recited in claim 14, wherein the probability corresponds to any access to the card prior to a CLR GC collection of an object(s) associated with the card subsequent to the computer-program instructions for substantially guaranteeing.

16. A computing device as recited in claim 14, wherein the computer-program instructions responsive to reading further comprise instructions for, if the one or more bits are not marked, card marking, by the CLR GC, the one or more bits.

17. A computing device as recited in claim 14, wherein the computer-program instructions for substantially guaranteeing further comprise instructions for not card marking, by the CLR GC, the one or more bits.

18. A computing device as recited in claim 14, wherein the computer-program instructions for bypassing further comprises instructions for skipping a card table check operation when compiling at least a portion of the CLR GC.