|Publication number||US8230271 B2|
|Application number||US 12/910,761|
|Publication date||Jul 24, 2012|
|Filing date||Oct 22, 2010|
|Priority date||Mar 23, 2006|
|Also published as||US7844862, US20110041015|
|Publication number||12910761, 910761, US 8230271 B2, US 8230271B2, US-B2-8230271, US8230271 B2, US8230271B2|
|Inventors||Daniel Dwight Grove, Ivan Posva, Jack H. Choquette, Cliff N. Click, Jr., Jeffrey Gee|
|Original Assignee||Azul Systems, Inc.|
|Export Citation||BiBTeX, EndNote, RefMan|
|Patent Citations (17), Classifications (7), Legal Events (3)|
|External Links: USPTO, USPTO Assignment, Espacenet|
This application is a continuation of U.S. patent application Ser. No. 11/716,545, entitled DETECTING SOFTWARE RACE CONDITIONS filed Mar. 8, 2007 which is incorporated herein by reference for all purposes, which is a continuation of U.S. Patent Application No. 60/785,798, entitled DETECTING SOFTWARE RACE CONDITIONS WITHIN A CPU SIMULATOR filed Mar. 23, 2006 which is incorporated herein by reference for all purposes.
In a typical computer architecture, parallel processors can enforce strict memory models of in-order execution of stores and loads. However, memory models are becoming weaker as systems with large numbers of memory-coherent processors are becoming common. To prevent a race condition and guarantee that a desired store to memory by one processor in a system is visible to other processors in the system, memory ordering operations such as barrier instructions must be used by a programmer and/or a compiler and/or some other form of code generator. It is easy for programmers and compilers to accidentally omit these memory ordering operations even though a race condition is not desired. This can lead to unpredictable and incorrect program execution. Therefore, there exists a need for a better way to determine whether a desired memory ordering operation has been omitted.
Various embodiments of the invention are disclosed in the following detailed description and the accompanying drawings.
The invention can be implemented in numerous ways, including as a process, an apparatus, a system, a composition of matter, a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. A component such as a processor or a memory described as being configured to perform a task includes both a general component that is temporarily configured to perform the task at a given time or a specific component that is manufactured to perform the task. In general, the order of the steps of disclosed processes may be altered within the scope of the invention.
A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured.
Detecting a memory race condition in a multi-processor environment is disclosed. In some embodiments, at least a portion of the processors are simulated processors. In some embodiments, memory store operations, memory load operations, and/or ordering operations that order memory operations are monitored to detect potential memory race conditions. For example, if a memory location that has been previously stored by a previous store operation is used in a subsequent store and/or load operation without an associated ordering operation, a race condition is detected. In various embodiments, detecting a potential memory race condition includes performing one or more of the following: running the program in a software multi-processor simulator, trapping store and/or load instructions of the program, and replacing store and/or load instructions of the program with other/additional instructions for memory race condition detection. In some embodiments, when a memory store operation of a program is performed, data associated with the store operation is tracked and a check is performed to determine whether the store operation is associated with a potential memory race condition. In some embodiments, when a memory load operation of a program is performed, a check is performed to determine whether the load operation is associated with a potential memory race condition. In some embodiments, when an ordering operation is performed, a race condition detection processing is performed to update/remove tracked information associated with one or more previous store operations. Examples of the ordering operation includes a fence operation, a barrier operation, and a compare and swap operation.
At 204, a memory address identifier and a processor identifier are stored in a global hash table. Storing the processor identifier is optional. The global hash table is accessible by a plurality of processors for tracking store operations across the plurality of processors. In some embodiments, the memory address identifier and the processor identifier are associated together in the hash table. The memory address identifier is stored in the hash table together with an associated generation number. Other data associated with the store instruction can be stored in the hash table. In some embodiments, storing data in the global hash table is optional. For example, only data structures privately associated with each processor is used to track store operations. In some embodiments, the hash table is an unlocked hash table that allows fast accesses. For example, without a global data tracking structure, searching each race condition detection queue of every processor to determine whether a previous store operation has stored to a desired memory location can be computationally expensive. Since the unlocked hash table allows fast searching and entry addition, the hash table can be used to determine whether to search race condition detection queues and/or which race condition detection queues to search.
If the memory address identifier is found in the global hash table, at 406 it determined whether a processor identifier stored with the memory address identifier in the hash table is associated with a processor that is not the processor performing the memory operation. If the processor identifier is associated with the processor performing the memory operation, at 414 it is concluded that no race condition is detected. Otherwise, at 408 it is determined whether the memory address identifier is found in a race condition detection buffer of a processor identified using the processor identifier. In some embodiments, the race condition detection buffer is the buffer in 204 of
In the example of the
In some embodiments, performing the race detection operation includes modifying (e.g., incrementing) a reference generation identifier that can be used to determine whether a memory operation has been performed after an ordering operation. For example, identifiers of store operation destination memory addresses are stored in a global hash table together with associated generation numbers. When a store and/or load operation is performed, the hash table can be searched to locate entries associated with a desired memory address and a desired generation number to determine whether the memory operation is likely associated with a race condition. By using the generation identifier, the need for a race condition detection queue associated with each processor can be eliminated.
Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.
|Cited Patent||Filing date||Publication date||Applicant||Title|
|US5535365 *||Oct 22, 1993||Jul 9, 1996||Cray Research, Inc.||Method and apparatus for locking shared memory locations in multiprocessing systems|
|US5950228 *||Feb 3, 1997||Sep 7, 1999||Digital Equipment Corporation||Variable-grained memory sharing for clusters of symmetric multi-processors using private and shared state tables|
|US6738737 *||Feb 18, 1999||May 18, 2004||Cirrus Logic, Inc.||Race condition ordering and functional verification system and method|
|US7028119 *||Apr 4, 2001||Apr 11, 2006||Wind River Systems, Inc.||Automated tool for detection of potential race condition|
|US7080213 *||Dec 16, 2002||Jul 18, 2006||Sun Microsystems, Inc.||System and method for reducing shared memory write overhead in multiprocessor systems|
|US7254687 *||Dec 16, 2002||Aug 7, 2007||Cisco Technology, Inc.||Memory controller that tracks queue operations to detect race conditions|
|US7356653 *||Jun 3, 2005||Apr 8, 2008||International Business Machines Corporation||Reader-initiated shared memory synchronization|
|US7366956 *||Jun 16, 2004||Apr 29, 2008||Hewlett-Packard Development Company, L.P.||Detecting data races in multithreaded computer programs|
|US7620852 *||Nov 17, 2009||Microsoft Corporation||Systems and methods of reporting multiple threads involved in a potential data race|
|US7752605 *||Apr 12, 2006||Jul 6, 2010||Microsoft Corporation||Precise data-race detection using locksets|
|US7861118 *||Mar 30, 2007||Dec 28, 2010||Microsoft Corporation||Machine instruction level race condition detection|
|US20030236951 *||Jun 25, 2002||Dec 25, 2003||International Business Machines Corporation||Method and apparatus for efficient and precise datarace detection for multithreaded object-oriented programs|
|US20040068613 *||Oct 3, 2002||Apr 8, 2004||Tierney Gregory E.||Retry-based late race resolution mechanism for a computer system|
|US20040117564 *||Dec 16, 2002||Jun 17, 2004||Oskar Grenholm||System and method for reducing shared memory write overhead in multiprocessor systems|
|US20050038806 *||Aug 12, 2003||Feb 17, 2005||Zhiqiang Ma||Methods and apparatus for detecting data race conditions in message-based multi-threaded programs|
|US20070150665 *||Dec 22, 2005||Jun 28, 2007||International Business Machines Corporation||Propagating data using mirrored lock caches|
|US20080244332 *||Mar 30, 2007||Oct 2, 2008||Microsoft Corporation||Machine instruction level race condition detection|
|U.S. Classification||714/50, 714/38.11, 714/47.1, 711/163|
|Jan 25, 2016||FPAY||Fee payment|
Year of fee payment: 4
|Feb 2, 2016||AS||Assignment|
Owner name: SILICON VALLEY BANK, CALIFORNIA
Free format text: SECURITY INTEREST;ASSIGNOR:AZUL SYSTEMS, INC.;REEL/FRAME:037641/0665
Effective date: 20151203
|Mar 1, 2016||AS||Assignment|
Owner name: PARTNERS FOR GROWTH IV, L.P., CALIFORNIA
Free format text: SECURITY INTEREST;ASSIGNOR:AZUL SYSTEMS, INC.;REEL/FRAME:037959/0694
Effective date: 20160229