Atomicity violation detection using access interleaving invariants
Inventors
Zhou, Yuanyuan • Lu, Shan • Tucek, Joseph Andrew
Assignees
Publication Number
US-8533681-B2
Publication Date
2013-09-10
Expiration Date
2027-09-19
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
During execution of a program, the situation where the atomicity of a pair of instructions that are to be executed atomically is violated is identified, and a bug is detected as occurring in the program at the pair of instructions. The pairs of instructions that are to be executed atomically can be identified in different manners, such as by executing a program multiple times and using the results of those executions to automatically identify the pairs of instructions.
Core Innovation
The invention relates to detecting atomicity violations in computer programs by identifying pairs of instructions intended to be executed atomically. During multiple executions of the program, pairs of instructions that the programmer intended to execute without interference are automatically identified. During subsequent program execution, situations where the atomicity of these pairs is violated are detected to identify bugs at those instruction pairs.
Atomicity violations occur when the intended serial execution of two instructions accessing the same memory locations is interrupted by other instructions, especially in multithreaded environments. The invention addresses the difficulty programmers face in detecting such violations when interleaved accesses from multiple threads occur, by using access interleaving invariants (AI invariants) that represent atomic instruction pairs. These AI invariants are extracted automatically from multiple program executions and used during runtime to detect atomicity violations based on the interleaving of local and remote memory accesses.
Claims Coverage
The patent includes fifteen independent claims covering methods, computer-readable media, and computing devices for detecting atomicity violations using access interleaving invariants and cache line metadata.
Method for identifying atomic pairs and detecting atomicity violations using cache line bits
The method automatically identifies pairs of instructions intended to be executed atomically by analyzing multiple correct executions. It detects atomicity violations during program execution by accessing cache line metadata including an invalidate bit, a downgrade bit, and a preceding access instruction bit, and determines violation based on these bits.
Detection of atomicity violations by instruction type and interleaving remote accesses
The detection method checks if one instruction in the pair is a read or write access. For reads, violations occur if interleaving remote write accesses happen between the instruction and its preceding one. For writes, violations depend on the preceding instruction being a read or write access and the presence of interleaving remote accesses.
Automatic extraction of access interleaving invariants from multiple executions
The method identifies AI invariants by observing multiple executions and selecting instruction pairs that are never violated in any correct execution, thereby forming an automatically extracted set of access interleaving invariants.
Use of global access-owner and local access tables to detect atomicity violations
The method maintains a global table identifying the thread that last wrote to each global memory location and per-thread local access tables recording whether the last access was a read or write. These tables are used to determine atomicity violations by tracking interleaving remote accesses.
Use of cache line bits to determine atomicity violations based on instruction types
Using the invalidate, downgrade, and preceding access instruction bits, the method determines violation states for a read access instruction and write access instruction based on combinations of these bits being set or cleared.
Computer-readable media implementing detection based on instruction type and tables
Instructions stored on media perform checks for read or write types in a pair of instructions drawn from extracted AI invariants, maintain global and local access tables, and detect violations based on interleaving remote writes between instructions or types of preceding instructions.
Computer-readable media implementing automatic extraction of AI invariants
Instructions stored on media execute programs multiple times, detect violated access interleaving invariants by occurrence threshold, remove violated invariants, and select the remaining invariants not violated across executions as the extracted AI invariants.
Computing device with cache memory extended with downgrade and preceding access instruction bits and thread identifiers
A computing device includes a processor and cache memory where each cache line stores data plus bits indicating downgrade state, preceding access instruction type, and thread identifiers representing which thread most recently accessed the cache line; the device uses these to detect atomicity violations.
Use of downgrade and preceding access instruction bits for atomicity violation detection in hardware
The device uses the combination of invalidate, downgrade, and preceding access instruction bits within cache lines and the instruction type (read or write) to determine atomicity violations at pairs of instructions.
Encoding of I-instructions to mark instructions for atomicity violation checks
Instructions in the program are encoded to identify I-instructions, signaling the detection logic to perform atomicity violation checks at these instructions using the cache line bits and coherence states.
Cache line granularity optimization with multiple bits per cache line for words
Cache lines can maintain multiple downgrade and preceding access instruction bits corresponding to individual words within the cache line, allowing finer granularity for atomicity violation detection.
The independent claims collectively describe methods and apparatus for automatically extracting pairs of atomic instructions from multiple executions, monitoring cache line state bits enhanced with downgrade and preceding access instruction information, and detecting atomicity violations through analysis of interleaving remote accesses and instruction types in software and hardware implementations.
Stated Advantages
Automatic identification of atomic instruction pairs without programmer annotations.
Improved detection of atomicity violations in multithreaded programs by focusing on unserializable interleavings.
Capability to detect atomicity violations dynamically during program execution including testing and normal operation.
Support for various implementation forms including software, firmware, and hardware with enhanced cache line metadata.
Flexibility to use multiple program executions to reduce false positives by filtering permitted unserializable interleavings.
Documented Applications
Automatic detection of atomicity violations (bugs) in multithreaded computer programs by identifying pairs of instructions intended to execute atomically.
Enhancement of software testing and debugging processes to find subtle concurrency bugs that arise from instruction interleaving.
Real-time detection of atomicity violations during normal program operation on end-user systems.
Implementation in computing devices using extended cache coherence protocols to detect atomicity violations at the hardware level.
Interested in licensing this patent?