Data race detection with per-thread memory protection
Data race detection in multi-threaded programs can be achieved by leveraging per-thread memory protection technology in conjunction with a custom dynamic memory allocator to protect shared memory objects with unique memory protection keys, allowing data races to be turned into inter-thread memory access violations. Threads may acquire or release the keys used for accessing protected memory objects at the entry and exit points of critical sections within the program. An attempt by a thread to access a protected memory object within a critical section without the associated key triggers a protection fault, which may be indicative of a data race.
1. A method for data race detection during execution of a multi-threaded program comprising one or more critical sections, the method using a set of access keys available to protect memory objects in the one or more critical sections, wherein each memory object is protected by only one of the access keys at a time, the method comprising:
maintaining, in one or more machine-readable media, a first subset of the set of access keys, the first subset consisting of access keys currently not held by any of multiple threads and thus available for acquisition;
maintaining, in the one or more machine-readable media, multiple second subsets of the set of access keys, each of the second subsets associated with one of the multiple threads and consisting of access keys held by that thread, the first subset and the multiple second subsets collectively containing all keys of the set of access keys available to protect the memory objects in the one or more critical sections of the program, wherein an access key is removed from the first subset upon acquisition from the first subset by any of the multiple threads and added back to the first subset upon release by that thread;
maintaining, in the one or more machine-readable media, one or more third subsets of the set of access keys, each of the one or more third subsets associated with one of the one or more critical sections of the program, each access key within one of the one or more third subsets of access keys being one of the keys of the set of access keys and being associated with a memory object to be accessed within the respective critical section, at least one of the third subsets comprising at least two access keys; and
detecting, by a computer processor, an attempt of one of the multiple threads to access a memory object whose associated access key is held by another one of the multiple threads, and registering a data race in response thereto.
2. The method of claim 1 , wherein maintaining the multiple second subsets comprises, at a time of entry of one of the multiple threads into one of the one or more critical sections, acquiring, by the thread, any one or more keys of the third subset associated with the critical section that are within the first subset at the time of entry.
3. The method of claim 1 , wherein maintaining the one or more third subsets comprises, for each of the one or more critical sections, upon an attempt by one of the multiple threads to access a memory object within the critical section that is not protected by any key of the set of access keys, assigning one of the keys of the set of access keys to the memory object.
4. The method of claim 3 , wherein maintaining the one or more second subsets comprises, upon assigning one of the keys to the memory object, adding the assigned key to the second subset associated with the respective thread.
5. The method of claim 3 , wherein maintaining the one or more third subsets further comprises, upon exit of the respective thread from the critical section, adding the assigned key to the third subset associated with the critical section.
6. The method of claim 3 , wherein assigning one of the keys of the set of access keys comprises assigning an access key from the second subset associated with the respective thread that is not also within a third subset associated with another one of the one or more critical sections.
7. The method of claim 3 , wherein assigning one of the keys of the set of access keys comprises assigning an access key from the first subset of access keys, and wherein maintaining the one or more third subsets further comprises retracting the assigned access key from a third subset associated with another one of the one or more critical sections.
8. The method of claim 1 , wherein maintaining the multiple second subsets comprises, upon an attempt by one of the multiple threads to access, within one of the one or more critical sections, a memory object whose associated access key is within the first subset, acquiring the access key by the thread.
9. The method of claim 1 , further comprising:
maintaining one or more temporary fourth subsets of the set of access keys, each of the temporary fourth subsets being associated with one of the multiple threads and with a section among the one or more critical sections that is being executed by the thread, each of the temporary fourth subsets of access keys including all access keys acquired by the respective thread during entering or executing the respective critical section, and
wherein maintaining the one or more second subsets comprises, upon exit of one of the multiple threads from one of the one or more critical sections, retracting all access keys within the associated temporary fourth subset from the second subset associated with the thread.
10. The method of claim 9 , wherein maintaining the one or more third subsets comprises, upon exit of one of the multiple threads from one of the one or more critical sections, merging the associated temporary fourth subset with the third subset associated with the respective critical section.
11. The method of claim 1 , wherein maintaining the multiple second subsets comprises, upon acquisition of an access key by or retraction of the access key from one of the multiple threads, updating, within a thread-local processor register associated with the respective thread, an access permission for the associated key.
12. The method of claim 1 , wherein maintaining the multiple third subsets comprises tracking protected memory objects in the one or more critical sections in a section-object map and tracking access keys associated with the protected memory objects in a page table that maps virtual memory pages storing memory objects to physical memory addresses.
13. A system comprising:
a computer processor supporting per-thread memory protection using a set of access keys available to protect memory objects in one or more critical sections of a multi-threaded program, wherein each memory object is protected by only one of the access keys at a time; and
computer memory storing processor-executable instructions for data race detection during execution of the multi-threaded program on the computer processor, the instructions, when executed by the computer processor, causing the computer processor to perform operations comprising:
maintaining, in the computer memory, a first subset of the set of access keys, the first subset consisting of access keys currently not held by any of multiple threads and thus available for acquisition;
maintaining, in the computer memory, multiple second subsets of the set of access keys, each of the second subsets associated with one of the multiple threads and consisting of access keys held by that thread, the first subset and the multiple second subsets collectively containing all keys of the set of access keys available to protect the memory objects in the one or more critical sections of the program, wherein an access key is removed from the first subset upon acquisition from the first subset by any of the multiple threads and added back to the first subset upon release by that thread;
maintaining, in the computer memory, one or more third subsets of the set of access keys, each of the one or more third subsets associated with one of the one or more critical sections of the program, each access key within one of the one or more third subsets being one of the keys of the set of access keys and being associated with a memory object to be accessed within the respective critical section, at least one of the third subsets comprising at least two access keys; and
detecting, by the computer processor an attempt of one of the multiple threads to access a memory object whose associated access key is held by another one of the multiple threads, and registering a data race in response thereto.
14. The system of claim 13 , wherein maintaining the multiple second subsets comprises at least one of:
at a time of entry of one of the multiple threads into one of the one or more critical sections, acquiring, by the thread, any key of the third subset associated with the critical section that is within the first subset at the time of entry, or
upon an attempt by one of the multiple threads to access, within one of the one or more critical sections, a memory object whose associated access key is within the first subset, acquiring the access key by the thread.
15. The system of claim 13 , wherein maintaining the one or more second subsets and the one or more third subsets comprises, for each of the one or more critical sections, upon an attempt by one of the multiple threads to access a memory object within the critical section that is not protected by any key of the set of access keys:
assigning one of the keys of the set of access keys to the memory object,
adding the assigned key to the second subset associated with the respective thread, and upon exit of the respective thread from the critical section, adding the assigned key to the third subset associated with the critical section.
16. The system of claim 15 , wherein assigning one of the keys of the set of access keys comprises:
assigning an access key from the second subset associated with the respective thread that is not also within a third subset associated with another one of the one or more critical sections, if available, and
otherwise assigning an access key from the first subset, if available, and retracting the assigned access key from any third subset associated with another one of the one or more critical sections that holds the access key.
17. The system of claim 13 , the operations further comprising:
maintaining one or more temporary fourth subsets of the set of access keys, each of the temporary fourth subsets being associated with one of the multiple threads and with a section among the one or more critical sections that is being executed by the thread, each of the temporary fourth subsets including all access keys acquired by the respective thread during entering or executing the respective critical section,
wherein maintaining the one or more second subsets and the one or more third subsets comprises, upon exit of one of the multiple threads from one of the one or more critical sections: retracting all access keys within the associated temporary fourth subset from the second subset of access keys associated with the thread, and merging the associated temporary fourth subset with the third subset associated with the respective critical section.
18. The system of claim 13 , wherein maintaining the multiple second subsets comprises, upon acquisition of an access key by or retraction of the access key from one of the multiple threads, updating, within a thread-local processor register associated with the respective thread, an access permission for the associated key.
19. The system of claim 13 , wherein maintaining the multiple third subsets comprises tracking protected memory objects in the one or more critical sections in a section-object map and tracking access keys associated with the protected memory objects in a page table that maps virtual memory pages storing memory objects to physical memory addresses.
20. One or more non-transitory machine-readable media storing processor-executable instruction for data race detection during execution of a multi-threaded program comprising one or more critical sections, using a set of access keys available to protect memory objects in the one or more critical sections, wherein each memory object is protected by only one of the access keys at a time, the instructions, when executed by a computer processor, causing the computer processor to perform operations comprising:
maintaining, in the one or more machine-readable media, a first subset of the set of access keys, the first subset consisting of access keys currently not held by any of multiple threads and thus available for acquisition;
maintaining, in the one or more machine-readable media, multiple second subsets of the set of access keys, each of the second subsets associated with one of the multiple threads and consisting of access keys held by that thread, the first subset and the multiple second subsets collectively containing all keys of the set of access keys available to protect the memory objects in the one or more critical sections of the program, wherein an access key is removed from the first subset upon acquisition from the first subset by any of the multiple threads and added back to the first subset upon release by that thread;
maintaining, in the one or more machine-readable media, one or more third subsets of the set of access keys, each of the one or more third subsets associated with one of the one or more critical sections of the program, each access key within one of the one or more third subsets being one of the keys of the set of access keys and being associated with a memory object to be accessed within the respective critical section, at least one of the third subsets comprising at least two access keys; and
detecting, by the computer processor, an attempt of one of the multiple threads to access a memory object whose associated access key is held by another one of the multiple threads, and registering a data race in response thereto.