3 ms·

Lock free algorithms have to be careful to avoid dataraces by using the appropriate atomic instructions on the CPU. Using non-atomic instructions is a data race

by dbaupp 12y ago

Lock free algorithms have to be careful to avoid dataraces by using the appropriate atomic instructions on the CPU. Using non-atomic instructions is a data race and may mean you incorrectly detect that you won the race (seeing stale data in a CPU cache or somesuch). A data race is essentially defined as a race condition between reads and writes where at least one of those is non-atomic. Rust's type system allows one to enforce atomicity by default (e.g. using atomic instructions, or wrapping data in a mutex).

asveikau 12y ago
Are you assuming that I haven't written these things in real life or something? I said "safely" detect, so yes, the final observation that you have won or lost the race must come from an atomic op. However, a "data race" susceptible read can totally be part of the process. The most common idiom I have seen for a lock free atomic read-modify-write has been to do an "unsafe" read, then act like it was OK, then issue compare-and-swap to determine if it really was OK and do the write if successful. (A failed compare and swap means you need to re-fetch and try again.) Yes you need to make sure fences are OK and the compiler is not caching/reordering the read and you need to account for the famous "ABA problem", blah blah blah, but it's what people do and I am not making it up for the purposes of an HN discussion. The typical RISC approach to atomics, load-link/store-conditional, also encourages what I will call "my kind of thinking" on this issue, though it does so with specialized instructions. You do a special read, then you use ordinary non-atomic register operations, then you do the special store which fails when you lose the race. I will give you that these are specialized instructions and not ordinary C assignments but I would suggest looking into them if you have not already, the semantics are very educational. (And they may just convince you that disallowing data races is an overly restrictive thing to do in some scenarios.)
- dbaupp 12y ago
  I was assuming you were talking about the race & detection as e.g. // let the "race" happen: old = compare_and_swap(some_shared_memory, 1); if old == 0 { // we won! } This is perfectly valid data-race-free code if the CAS is atomic, but is invalid if the CAS is not (assuming no other memory fences). But sure, if you're manually fencing then you can have data races that are benign; however, just because something has some relatively rare uses doesn't mean it's wildly unsafe for the general case, and so disallowing by default it helps the correctness of the vast majority of concurrent code. In any case, Rust allows one to opt-in to that sort of behaviour using `unsafe` locally, e.g. one would use `unsafe` deep in the internals of the implementation of the lock-free data structure and with careful vetting to ensure it's correct, and then all users can benefit with the compiler ensuring concurrency-safety by default. Rust tries not to completely disallow behaviour, just make memory safety the default. The programmer can override the compiler via `unsafe` if they truly know better.
  - asveikau 12y ago
    Other than the address compare and swap takes two operands: expected value and new value. It does an equality check and (if equal) the swap atomically. Therefore the equality check is handy to atomically check if a previous potentially unsafe read is still valid, and if so, set a new value.
    - asveikau 12y ago
      Too late to edit the post but maybe some code sample will help illustrate the pattern. I am typing code into a web form so I make no guarantees that it is perfect. // Performs some modification on the input. extern int f(int); volatile int global_var = /* ... */; int expected; int new; // assuming C and not C++, where "new" is reserved do { // Do a speculative read expected = global_var; // Make some (non-atomic) modification new = f(expected); // loop until the speculative read was OK. (won the race) } while (compare_and_swap(&global_var, expected, new) != expected);
      - dbaupp 12y ago
        Whoops, I got the signature of CAS slightly wrong. In any case, I already understood the pattern and understand why it is OK. However, as I said, it is the exception that a data race is OK, which is why Rust disallows them by default (it does not disallow them completely).

by dbaupp 12y ago

asveikau 12y ago

Are you assuming that I haven't written these things in real life or something? I said "safely" detect, so yes, the final observation that you have won or lost the race must come from an atomic op. However, a "data race" susceptible read can totally be part of the process. The most common idiom I have seen for a lock free atomic read-modify-write has been to do an "unsafe" read, then act like it was OK, then issue compare-and-swap to determine if it really was OK and do the write if successful. (A failed compare and swap means you need to re-fetch and try again.) Yes you need to make sure fences are OK and the compiler is not caching/reordering the read and you need to account for the famous "ABA problem", blah blah blah, but it's what people do and I am not making it up for the purposes of an HN discussion. The typical RISC approach to atomics, load-link/store-conditional, also encourages what I will call "my kind of thinking" on this issue, though it does so with specialized instructions. You do a special read, then you use ordinary non-atomic register operations, then you do the special store which fails when you lose the race. I will give you that these are specialized instructions and not ordinary C assignments but I would suggest looking into them if you have not already, the semantics are very educational. (And they may just convince you that disallowing data races is an overly restrictive thing to do in some scenarios.)

dbaupp 12y ago
I was assuming you were talking about the race & detection as e.g. // let the "race" happen: old = compare_and_swap(some_shared_memory, 1); if old == 0 { // we won! } This is perfectly valid data-race-free code if the CAS is atomic, but is invalid if the CAS is not (assuming no other memory fences). But sure, if you're manually fencing then you can have data races that are benign; however, just because something has some relatively rare uses doesn't mean it's wildly unsafe for the general case, and so disallowing by default it helps the correctness of the vast majority of concurrent code. In any case, Rust allows one to opt-in to that sort of behaviour using `unsafe` locally, e.g. one would use `unsafe` deep in the internals of the implementation of the lock-free data structure and with careful vetting to ensure it's correct, and then all users can benefit with the compiler ensuring concurrency-safety by default. Rust tries not to completely disallow behaviour, just make memory safety the default. The programmer can override the compiler via `unsafe` if they truly know better.
- asveikau 12y ago
  Other than the address compare and swap takes two operands: expected value and new value. It does an equality check and (if equal) the swap atomically. Therefore the equality check is handy to atomically check if a previous potentially unsafe read is still valid, and if so, set a new value.
  - asveikau 12y ago
    Too late to edit the post but maybe some code sample will help illustrate the pattern. I am typing code into a web form so I make no guarantees that it is perfect. // Performs some modification on the input. extern int f(int); volatile int global_var = /* ... */; int expected; int new; // assuming C and not C++, where "new" is reserved do { // Do a speculative read expected = global_var; // Make some (non-atomic) modification new = f(expected); // loop until the speculative read was OK. (won the race) } while (compare_and_swap(&global_var, expected, new) != expected);
    - dbaupp 12y ago
      Whoops, I got the signature of CAS slightly wrong. In any case, I already understood the pattern and understand why it is OK. However, as I said, it is the exception that a data race is OK, which is why Rust disallows them by default (it does not disallow them completely).