Patent ID: 8533681

Claim:
A method of detecting atomicity violations in a program, the method comprising: identifying, based on multiple executions of the program, multiple pairs of instructions that were intended to be executed atomically, the identifying multiple pairs of the instructions including a particular pair of instructions as one of the multiple pairs of instructions that were intended to be executed atomically only if atomicity of the particular pair of instructions is not violated during one of the multiple correct executions of the program; identifying, during subsequent execution of the program, when a pair of instructions of the multiple pairs of instructions are to be executed and the atomicity of the pair of instructions violated, wherein identifying the atomicity of the pair of instructions is violated comprises: accessing a cache line in a cache memory of a computing device that stores data for a memory location accessed by the pair of instructions, the cache line including: an invalidate bit that is set when an interleaving remote write to the memory location occurs, a downgrade bit that is set when the value in the memory location is a result of a previous write access by a local thread and the memory location has been read by a remote thread, and is cleared when the local thread accesses the memory location, and a preceding access instruction bit that is set when the local thread performs a read access to the memory location, and is cleared when the local thread performs a write access to the memory location, and using one or more of the invalidate bit, the downgrade bit, and the preceding access instruction bit to determine whether the atomicity of the pair of instructions is violated; and detecting a bug as occurring in the program at the pair of instructions.