34 ms·

Safe Lock-free Primitives with iceoryx2's ByteAtomic

14 points by elfenpiff 2mo ago

elfenpiff 2mo ago
iceoryx2 provides zero-copy inter-process communication mechanisms based on shared memory and data structures that are modified concurrently by multiple processes. One of the key operations in these algorithms is a memory copy using core::ptr::copy. However, this results in undefined behavior if one process reads the data while another process writes to it concurrently. Even if our lock-free algorithm reliably detects such a race, iceoryx2 cannot depend on undefined behavior in a safety-critical system. This blog post introduces our solution: a byte-wise atomic wrapper that enables well-defined concurrent copy operations. It also shows how it can be used to implement a simple sequence lock.
- eqvinox 2mo ago
  You're fixing a theoretical problem (mismatch between CPU and compiler memory models, the CPU is perfectly fine doing these reads and writes, it's only the compiler declaring them "UB") by throwing away a shitton of performance, forcing everything into bytewise accesses. Considering this is Rust, I would at minimum expect this be written to be generic over access size to allow using 64-bit reads/writes. I'm also missing any acquire/release barrier annotations in your code snippets. If you're using sequentially consistent accesses you might as well just single thread your code, performance wise. Lastly, in almost all cases it's way more efficient and appropriate to shuffle things on the whole-object level, posting and retrieving pointers, and not poke around inside objects (especially on the byte level). Check how rare the use of seqlocks in the Linux kernel is, compared to other RCU primitives. (and regarding "appropriate", cf. top-level comment by danbruc https://news.ycombinator.com/item?id=49168283 https://news.ycombinator.com/item?id=49168283 )
  - wbl 2mo ago
    The compiler declares them UB because very useful transformations would change the semantics of races. Races are ok with specially marked variables!
    - eqvinox 2mo ago
      That's not the point of my argument. The compiler declaring things UB needs to be addressed by telling the compiler to not be silly, not by forcing every single access to be on the byte level. And especially not if those are SeqCst atomics.
danbruc 2mo ago
A common approach to mitigating the described data race without using blocking locks is to utilize a sequence lock. A sequence lock is a blocking lock. If the writer dies between the two increment operations, then the readers will spin forever waiting for the counter to become even again.
- jnwatson 2mo ago
  Also, there's no guarantee of progress. The writer can starve the reader forever.
  - adrian_b 2mo ago
    That is always possible, even in any algorithm that claims to be wait-free, if some writer just keeps writing the shared data. All the claims about something being lock-free and/or wait-free depend on a rational behavior of the writers. If any writer acts crazy, progress becomes impossible regardless of what all others do, unless someone kills the rogue thread or process. In practice, the algorithm from TFA is much more likely to guarantee progress than any of the algorithms that are theoretically proven to guarantee progress, because it has an extremely small overhead, while the alternatives are much more complex and they waste a lot of time. Moreover, most wait-free algorithms guarantee progress only for the whole system, in the sense that one random thread will progress, but they do not guarantee anything for a given thread, which may be blocked forever or stuck in an infinite loop, if unlucky.
    - deleted 2mo ago
      [deleted]
    - danbruc 2mo ago
      Not true, a wait-free algorithm guarantees that a read will complete in a bounded amount of time. And it guarantees that all threads make progress, it is lock-free that only guarantees progress for one thread. If the value changes frequently, it will get outdated quickly, but that has nothing to do with the synchronization mechanism used. And even if writes happen rarely, there is always a chance that the value you read will be outdated a nanosecond later.
jimaway123 2mo ago
From the article: >>>The Problem: Even if the reader detects that the data was modified and discards the copy before use, the act of copying the non-atomic data itself still triggers undefined behavior. While a sequence lock can detect that a data race occurred, it does not prevent it. Why is this a problem? Isn't the correct way to deal with a sequence lock failure to just retry? A torn read yes means you get undefined behavior as far as the result of your read, but you throw it all away and start again anyway so what is this solving?
- charleslmunger 2mo ago
  From a hardware perspective this is correct. From a language perspective it's UB, and unless your compiler has defined that UB, it doesn't matter what the hardware's behavior is unless you're writing assembly.
  - jimaway123 2mo ago
    So you're saying the problem that this article is solving is just preventing the language from generating code that can possibly load some incorrect bytes from main memory, even though these incorrect bytes will in every case be ignored? Why is this considered a problem at all?
    - charleslmunger 2mo ago
      It's a problem for language specifiers, basically. The behavior is undefined in the standard; to rely on it you either need your implementation of the standard to define it themselves, or you need to bet that there is no possible sequence of machine instructions the compiler could emit that would implement the defined behavior in a way where a data race would do something harmful. As far as I know there is no reasonable compiler that wasn't specifically trying to add some kind of sanitizer that would emit anything other than plain memory reads, but it would be nice to not have to worry. But sanitizers are handy! I can imagine some sanitizer implementation forgoing extra internal synchronization that would only be needed in the case of program UB anyway.
- 2mo ago

14 points by elfenpiff 2mo ago

iceoryx2 provides zero-copy inter-process communication mechanisms based on shared memory and data structures that are modified concurrently by multiple processes. One of the key operations in these algorithms is a memory copy using core::ptr::copy. However, this results in undefined behavior if one process reads the data while another process writes to it concurrently. Even if our lock-free algorithm reliably detects such a race, iceoryx2 cannot depend on undefined behavior in a safety-critical system. This blog post introduces our solution: a byte-wise atomic wrapper that enables well-defined concurrent copy operations. It also shows how it can be used to implement a simple sequence lock.

eqvinox 2mo ago
You're fixing a theoretical problem (mismatch between CPU and compiler memory models, the CPU is perfectly fine doing these reads and writes, it's only the compiler declaring them "UB") by throwing away a shitton of performance, forcing everything into bytewise accesses. Considering this is Rust, I would at minimum expect this be written to be generic over access size to allow using 64-bit reads/writes. I'm also missing any acquire/release barrier annotations in your code snippets. If you're using sequentially consistent accesses you might as well just single thread your code, performance wise. Lastly, in almost all cases it's way more efficient and appropriate to shuffle things on the whole-object level, posting and retrieving pointers, and not poke around inside objects (especially on the byte level). Check how rare the use of seqlocks in the Linux kernel is, compared to other RCU primitives. (and regarding "appropriate", cf. top-level comment by danbruc https://news.ycombinator.com/item?id=49168283 https://news.ycombinator.com/item?id=49168283 )
- wbl 2mo ago
  The compiler declares them UB because very useful transformations would change the semantics of races. Races are ok with specially marked variables!
  - eqvinox 2mo ago
    That's not the point of my argument. The compiler declaring things UB needs to be addressed by telling the compiler to not be silly, not by forcing every single access to be on the byte level. And especially not if those are SeqCst atomics.

danbruc 2mo ago

A common approach to mitigating the described data race without using blocking locks is to utilize a sequence lock. A sequence lock is a blocking lock. If the writer dies between the two increment operations, then the readers will spin forever waiting for the counter to become even again.

jnwatson 2mo ago
Also, there's no guarantee of progress. The writer can starve the reader forever.
- adrian_b 2mo ago
  That is always possible, even in any algorithm that claims to be wait-free, if some writer just keeps writing the shared data. All the claims about something being lock-free and/or wait-free depend on a rational behavior of the writers. If any writer acts crazy, progress becomes impossible regardless of what all others do, unless someone kills the rogue thread or process. In practice, the algorithm from TFA is much more likely to guarantee progress than any of the algorithms that are theoretically proven to guarantee progress, because it has an extremely small overhead, while the alternatives are much more complex and they waste a lot of time. Moreover, most wait-free algorithms guarantee progress only for the whole system, in the sense that one random thread will progress, but they do not guarantee anything for a given thread, which may be blocked forever or stuck in an infinite loop, if unlucky.
  - deleted 2mo ago
    [deleted]
  - danbruc 2mo ago
    Not true, a wait-free algorithm guarantees that a read will complete in a bounded amount of time. And it guarantees that all threads make progress, it is lock-free that only guarantees progress for one thread. If the value changes frequently, it will get outdated quickly, but that has nothing to do with the synchronization mechanism used. And even if writes happen rarely, there is always a chance that the value you read will be outdated a nanosecond later.

jimaway123 2mo ago

From the article: >>>The Problem: Even if the reader detects that the data was modified and discards the copy before use, the act of copying the non-atomic data itself still triggers undefined behavior. While a sequence lock can detect that a data race occurred, it does not prevent it. Why is this a problem? Isn't the correct way to deal with a sequence lock failure to just retry? A torn read yes means you get undefined behavior as far as the result of your read, but you throw it all away and start again anyway so what is this solving?

charleslmunger 2mo ago
From a hardware perspective this is correct. From a language perspective it's UB, and unless your compiler has defined that UB, it doesn't matter what the hardware's behavior is unless you're writing assembly.
- jimaway123 2mo ago
  So you're saying the problem that this article is solving is just preventing the language from generating code that can possibly load some incorrect bytes from main memory, even though these incorrect bytes will in every case be ignored? Why is this considered a problem at all?
  - charleslmunger 2mo ago
    It's a problem for language specifiers, basically. The behavior is undefined in the standard; to rely on it you either need your implementation of the standard to define it themselves, or you need to bet that there is no possible sequence of machine instructions the compiler could emit that would implement the defined behavior in a way where a data race would do something harmful. As far as I know there is no reasonable compiler that wasn't specifically trying to add some kind of sanitizer that would emit anything other than plain memory reads, but it would be nice to not have to worry. But sanitizers are handy! I can imagine some sanitizer implementation forgoing extra internal synchronization that would only be needed in the case of program UB anyway.
2mo ago