Techniques and systems for data race detection

• US 9,135,082 B1
• Filed: 05/20/2011
• Issued: 09/15/2015
• Est. Priority Date: 05/20/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hundt, Robert, Sheng, Tianwei, Vachharajani, Neil A., Eranian, Stephane
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): APONTE, FRANCISCO JAVIER
• Application Number:
  US13/112,945
• Time in Patent Office: 1,579 Days
• Field of Search: 717101-178, 712/220, 712/225, 712/227, 714100-824
• US Class Current: 1/1
• CPC Class Codes: G06F 11/28 by checking the correct order of processing G06F11/08 - G06F11/26 take precedence; monitoring patterns of pulse trains H03K5/19
• CPC Class Codes: G06F 11/36 Preventing errors by testing or debugging software
• CPC Class Codes: G06F 11/3632 of specific synchronisation aspects
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 8/458 Synchronisation, e.g. post-wait, barriers, locks synchronisation among tasks G06F9/52
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A race detection mechanism can include running threads of a multithreaded program on a processor, the program being configured to produce locksets each of which indicate a set of one or more locks that a thread holds at a point in time. The mechanism can cause a performance monitoring unit included in the processor to monitor memory accesses caused by the threads and to produce samples based on the memory accesses, the samples being indicative of an accessed memory location. The mechanism can detect an existence of a data race condition based on the samples and the locksets. Detecting can include identifying a protected access to a memory location by a first thread of the threads and identifying an unprotected access to the memory location by a second thread of the threads. The process selectively outputs an indication of the data race condition.

Claims

1. A method performed by data processing apparatus, comprising:

running two or more threads of a multithreaded program on a processor, the program being configured to;

produce locksets, each of which indicate a set of one or more locks that a thread holds at a point in time; and

cause a hardware implemented performance monitoring unit included in the processor to i) monitor memory accesses caused by the threads, ii) produce samples based on the memory accesses, each sample indicating an accessed memory location, wherein a sampling rate of the samples is controlled based on an overhead parameter, and iii) produce a separate processor interrupt for each sample;

aligning, using each separate processor interrupt produced for each sample by the performance monitoring unit, the samples produced by the performance monitoring unit with locksets produced by the program; and

determining an existence of a data race condition based on the samples and the locksets, the determining comprising;

(i) identifying, from a first lockset of the locksets and a first sample of the samples produced for a first thread of the two or more threads, a protected access, by the first thread, to a memory location indicated by the first sample;

(ii) identifying, from the first lockset and a second sample of the samples produced for a second thread of the two or more threads, an unprotected access, by the second thread, to the memory location indicated by the second sample; and

(iii) determining the data race condition exists based on the identified protected access and the identified unprotected access; and

selectively outputting an indication of the data race condition.

2. The method of claim 1, further comprising:

selecting a sample of the samples;

determining one or more additional memory accesses based on (i) register file information included in the selected sample and (ii) one or more associated basic blocks of the program, the selected sample corresponding to a memory reference instruction within the one or more associated basic blocks, wherein detecting the existence of the data race condition comprises using the one or more additional memory accesses.

3. The method of claim 1, further comprising:

obtaining memory allocation events associated with the program, wherein detecting the existence of the data race condition comprises using at least a portion of the memory allocation events.

4. The method of claim 1, further comprising:

configuring a size of a buffer of the performance monitoring unit to store a single sample such that each processor interrupt occurs based on the performance monitoring unit writing a single sample to the buffer.

5. The method of claim 1, wherein running the threads comprises running multiple instances of the application on one or more servers, and wherein detecting the existence of the data race condition comprises aggregating performance monitoring unit data generated by running the multiple instances of the application.

6. A system, comprising:

a computer storage device having instructions stored thereon; and

a processor coupled to the computer storage device, the processor comprising a performance monitoring unit,

wherein the instructions, when executed by the processor, cause the processor to perform operations comprising;

running two or more threads of a multithreaded program on a processor, the program being configured to;

produce locksets, each of which indicate a set of one or more locks that a thread holds at a point in time; and

cause a hardware implemented performance monitoring unit included in the processor to i) monitor memory accesses caused by the threads, ii) produce samples based on the memory accesses, each sample indicating an accessed memory location, wherein a sampling rate of the samples is controlled based on an overhead parameter, and iii) produce a separate processor interrupt for each sample;

aligning, using each separate processor interrupt produced for each sample by the performance monitoring unit, the samples produced by the performance monitoring unit with locksets produced by the program; and

determining an existence of a data race condition based on the samples and the locksets, the determining comprising;

(i) identifying, from a first lockset of the locksets and a first sample of the samples produced for a first thread of the two or more threads, a protected access, by the first thread, to a memory location indicated by the first sample;

(ii) identifying, from the first lockset and a second sample of the samples produced for a second thread of the two or more threads, an unprotected access, by the second thread, to the memory location indicated by the second sample; and

(iii) determining the data race condition exists based on the identified protected access and the identified unprotected access; and

selectively outputting an indication of the data race condition.

7. The system of claim 6, the operations further comprising:

selecting a sample of the samples;

determining one or more additional memory accesses based on (i) register file information included in the selected sample and (ii) one or more associated basic blocks of the program, the selected sample corresponding to a memory reference instruction within the one or more associated basic blocks, wherein detecting the existence of the data race condition comprises using the one or more additional memory accesses.

8. The system of claim 6, the operations further comprising:

obtaining memory allocation events associated with the program, wherein detecting the existence of the data race condition comprises using at least a portion of the memory allocation events.

9. The system of claim 6, the operations further comprising:

configuring a size of a buffer of the performance monitoring unit to store a single sample such that each processor interrupt occurs based on the performance monitoring unit writing a single sample to the buffer.

10. The system of claim 6, wherein running the threads comprises running multiple instances of the application on one or more servers, and wherein detecting the existence of the data race condition comprises aggregating performance monitoring unit data generated by running the multiple instances of the application.

11. A non-transitory computer readable medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

running two or more threads of a multithreaded program on a processor, the program being configured to;

produce locksets, each of which indicate a set of one or more locks that a thread holds at a point in time; and

cause a hardware implemented performance monitoring unit included in the processor to i) monitor memory accesses caused by the threads, ii) produce samples based on the memory accesses, each sample indicating an accessed memory location, wherein a sampling rate of the samples is controlled based on an overhead parameter, and iii) produce a separate processor interrupt for each sample;

aligning, using each separate processor interrupt produced for each sample by the performance monitoring unit, the samples produced by the performance monitoring unit with locksets produced by the program; and

determining an existence of a data race condition based on the samples and the locksets, the determining comprising;

(i) identifying, from a first lockset of the locksets and a first sample of the samples produced for a first thread of the two or more threads, a protected access, by the first thread, to a memory location indicated by the first sample;

(ii) identifying, from the first lockset and a second sample of the samples produced for a second thread of the two or more threads, an unprotected access, by the second thread, to the memory location indicated by the second sample; and

(iii) determining the data race condition exists based on the identified protected access and the identified unprotected access; and

selectively outputting an indication of the data race condition.

12. The computer readable medium of claim 11, the operations further comprising:

selecting a sample of the samples;

determining one or more additional memory accesses based on (i) register file information included in the selected sample and (ii) one or more associated basic blocks of the program, the selected sample corresponding to a memory reference instruction within the one or more associated basic blocks, wherein detecting the existence of the data race condition comprises using the one or more additional memory accesses.

13. The computer readable medium of claim 11, the operations further comprising:

obtaining memory allocation events associated with the program, wherein detecting the existence of the data race condition comprises using at least a portion of the memory allocation events.

14. The computer readable medium of claim 11, the operations further comprising:

configuring a size of a buffer of the performance monitoring unit to store a single sample such that each processor interrupt occurs based on the performance monitoring unit writing a single sample to the buffer.

15. The computer readable medium of claim 11, wherein running the threads comprises running multiple instances of the application on one or more servers, and wherein detecting the existence of the data race condition comprises aggregating performance monitoring unit data generated by running the multiple instances of the application.