Adding C-Like Atomic Operation Support to Rust
When: Monday,
October 28, 2024
3:30 PM
-
4:30 PM
Where: > See description for location
Description: College of Engineering
Computer & Information Science
CIS Master's Thesis Defense by Dante Broggi
Date & Time: Monday October 28, 2024 at 3:30 pm
Thesis Advisor: Dr. Adnan El-Nasan
Committee Members: Dr. Firas Khatib and Professor Clinton Rogers
Join Zoom Meeting
https://umassd.zoom.us/j/5039281530?pwd=Qnp6dGNlQVFPam5saHJWb3YyQ3dBQT09
Meeting ID: 503 928 1530
Passcode: 582509
Abstract: Many common programming languages (C, C++, Rust, Swift) provide an API to enable programmers to access atomic operations for use by multithreaded algorithms such as parallelized searches and to provide access to data structures such as concurrent linked lists. We investigated atomic operations in Rust and added wide pointer atomic support to mitigate the ABA problem in a way that is based on the solution supported in the Pony runtime. The ABA problem is a general problem scenario in which a function falsely assumes that atomically loading bitwise equivalent values means nothing relevant has changed between the loads. This can occur due to an algorithm failure, or due to object allocation reuse for logically distinct objects. We added experimental support for wide pointers with a 64-bit counter alongside the 64-bit pointer. This circumvents the ambiguity of having 2 or more pointers that point to the same address but are semantically different. Such pointers can occur, for example, when one is created in such a way that permits reading a whole array while the other is intended to read or write only the first element, or one was recently deallocated (these additional semantic differences are called the pointer’s “provenance†data). Rust extensively uses pointer provenance data to optimize its reference types by implementing their documented exclusivity and immutability guarantees. We implemented the standard atomic operations of load, store, and compare and swap (CAS) on Rust-wide pointers, both in the Rust intermediate representation interpreter Miri and in the LLVM backend, in a way that preserves provenance without hindering later optimization by exposing it unnecessarily. This implementation was assessed using several individual-operation correctness tests and an analysis of how our solution changes the result of a case of the ABA problem in a stack. We also tested the API design against that desired by our preceding attempt at translating the Pony runtime into Rust [1], where this or similar API is one of the blockers to further progress. We found that the proposed API is satisfactory, and the implementation passes the correctness tests and avoids internal ABA problems in all test cases.
For further information please contact Dr. Adnan El-Nasan at aelnasan@umassd.edu.
Computer & Information Science
CIS Master's Thesis Defense by Dante Broggi
Date & Time: Monday October 28, 2024 at 3:30 pm
Thesis Advisor: Dr. Adnan El-Nasan
Committee Members: Dr. Firas Khatib and Professor Clinton Rogers
Join Zoom Meeting
https://umassd.zoom.us/j/5039281530?pwd=Qnp6dGNlQVFPam5saHJWb3YyQ3dBQT09
Meeting ID: 503 928 1530
Passcode: 582509
Abstract: Many common programming languages (C, C++, Rust, Swift) provide an API to enable programmers to access atomic operations for use by multithreaded algorithms such as parallelized searches and to provide access to data structures such as concurrent linked lists. We investigated atomic operations in Rust and added wide pointer atomic support to mitigate the ABA problem in a way that is based on the solution supported in the Pony runtime. The ABA problem is a general problem scenario in which a function falsely assumes that atomically loading bitwise equivalent values means nothing relevant has changed between the loads. This can occur due to an algorithm failure, or due to object allocation reuse for logically distinct objects. We added experimental support for wide pointers with a 64-bit counter alongside the 64-bit pointer. This circumvents the ambiguity of having 2 or more pointers that point to the same address but are semantically different. Such pointers can occur, for example, when one is created in such a way that permits reading a whole array while the other is intended to read or write only the first element, or one was recently deallocated (these additional semantic differences are called the pointer’s “provenance†data). Rust extensively uses pointer provenance data to optimize its reference types by implementing their documented exclusivity and immutability guarantees. We implemented the standard atomic operations of load, store, and compare and swap (CAS) on Rust-wide pointers, both in the Rust intermediate representation interpreter Miri and in the LLVM backend, in a way that preserves provenance without hindering later optimization by exposing it unnecessarily. This implementation was assessed using several individual-operation correctness tests and an analysis of how our solution changes the result of a case of the ABA problem in a stack. We also tested the API design against that desired by our preceding attempt at translating the Pony runtime into Rust [1], where this or similar API is one of the blockers to further progress. We found that the proposed API is satisfactory, and the implementation passes the correctness tests and avoids internal ABA problems in all test cases.
For further information please contact Dr. Adnan El-Nasan at aelnasan@umassd.edu.
Contact:
Computer and Information Science Department 508.999.6692 http://www.umassd.edu/engineering/cis/
Topical Areas: Faculty, Students, Computer and Information Science, Graduate Studies