Safe Lock-free Primitives with iceoryx2's ByteAtomic • Hacker News Board

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#21

Post by danbruc » Tue, Aug 04, 2026, 3:28 PM UTC

adrian_b wrote: post #20

eqvinox wrote: post #15

Earlier quoted context omitted.

I think you missed the point; seqlock based approaches will lock dead if you suspend/abort a thread in the wrong place. Other lock-free approaches don't have this issue. This isn't about a thread writing garbage, it's about guarantees applicable within the constraints.

No, you missed my point. I agree that there is the risk for a writer to be halted in the middle of its critical section, which would stop all the other writers and readers. My point is that there exists no solution that is risk free, because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm, regardless if it is claimed to be wait-free. There exists no me…

[...] because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm [...]

Even if you have

  while (true) { sharedData.writeWaitFree(randomData) }

all other threads will be able to continue. Whether the result will be of any value will depend on the use case.

If, on the other hand, you mean that some threads will enter an infinite loop inside of a read or write operation, then you have a bug in your wait-free algorithm and all bets are off. But we would generally assume that the implementation is good and the erroneous behavior is external.

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#22

Post by adrian_b » Tue, Aug 04, 2026, 3:28 PM UTC

jimaway123 wrote: post #6

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 undefi…

The problem is that a reader should not do anything with the data that is read, which depends on its value, before validating the copy, by counter comparison.

As another poster has said, the high-level languages leave undefined what happens when you copy non-atomically data that is written concurrently, but in fact the computer cannot catch fire when you do that, and the only thing that can happen is that the data may have values that are invalid for its type, e.g. an integer that is defined to belong in a range may have a value outside that range.

A much more serious problem that is not mentioned in TFA is that on computers that do not use Intel/AMD CPUs, this algorithm needs write barriers and read barriers. The writer must use 2 write barriers, after incrementing the counter before accessing the shared data, and before incrementing the counter after finishing with the shared data. Similarly the reader needs read barriers after the first reading of the counter and before the final reading of the counter.

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#23

Post by adrian_b » Tue, Aug 04, 2026, 3:35 PM UTC

danbruc wrote: post #19

adrian_b wrote: post #17

Earlier quoted context omitted.

Only the read of data small enough to be read atomically will complete in a bounded amount of time (i.e. not larger than 16 bytes on the current x86 or Arm CPUs). If you have a bigger shared data structure, in which some other thread writes continuously, there exists absolutely no way to stop it and no way for any other thread to progress.

No, such algorithms exist and they use various mechanisms to achieve this. For larger data structures a common trick is to make a copy, update the copy, and then replace the original or parts of it with the copy. This provide readers with a stable view of the data structure that does not depend on small atomic reads. Another mechanism is that the different threads help each other to complete their interrupted work in…

Not true.

If a writer writes continuously the shared data, it is impossible for the other thread to make the copy that must be edited.

If the copy succeeds, then you are right that an updated version could be substituted to the original using an atomic operation on pointers.

But there is no way to guarantee that the first copy succeeds.

Of course, in practice RCU is used very frequently, because all the other threads are well behaved and access the shared data for a minimum time, so the copy will succeed in most cases.

But absolute guarantees are impossible inside an algorithm expressible in an abstract programming language. Only using functions of the operating system to detect and stop a misbehaving thread can solve all cases.

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#24

Post by jimaway123 » Tue, Aug 04, 2026, 3:35 PM UTC

charleslmunger wrote: post #8

jimaway123 wrote: post #6

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 undefi…

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.

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?

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#25

Post by adrian_b » Tue, Aug 04, 2026, 3:39 PM UTC

danbruc wrote: post #21

adrian_b wrote: post #20

Earlier quoted context omitted.

No, you missed my point. I agree that there is the risk for a writer to be halted in the middle of its critical section, which would stop all the other writers and readers. My point is that there exists no solution that is risk free, because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm, regardless if it is claimed to be wait-free. There exists no me…

[...] because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm [...] Even if you have while (true) { sharedData.writeWaitFree(randomData) } all other threads will be able to continue. Whether the result will be of any value will depend on the use case. If, on the other hand, you mean that some threads will enter an infinite loop inside of a read or writ…

Whatever is your writeWaitFree, nothing can stop another thread to do plain writes.

In that case no other thread can make progress.

I agree that this is a very unlikely case, but the case when a thread is halted inside the critical region can also appear only as a consequence of some bug, and such unlikely occurrences cannot justify wasting time at every access of shared data by using a too complicated wait-free algorithm.

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#26

Post by jimaway123 » Tue, Aug 04, 2026, 3:39 PM UTC

adrian_b wrote: post #22

jimaway123 wrote: post #6

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 undefi…

The problem is that a reader should not do anything with the data that is read, which depends on its value, before validating the copy, by counter comparison. As another poster has said, the high-level languages leave undefined what happens when you copy non-atomically data that is written concurrently, but in fact the computer cannot catch fire when you do that, and the only thing that can happen is that the data ma…

>>>The problem is that a reader should not do anything with the data that is read, which depends on its value, before validating the copy, by counter comparison.

The description of the problem explicitly says that this is not happening. The data is being thrown away if the counter comparison fails. So the only undefined behavior that I can think they might be referring to is the act of loading the data itself, even though it is thrown away if it is wrong. Is that what they mean?

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#27

Post by danbruc » Tue, Aug 04, 2026, 3:42 PM UTC

adrian_b wrote: post #23

danbruc wrote: post #19

Earlier quoted context omitted.

No, such algorithms exist and they use various mechanisms to achieve this. For larger data structures a common trick is to make a copy, update the copy, and then replace the original or parts of it with the copy. This provide readers with a stable view of the data structure that does not depend on small atomic reads. Another mechanism is that the different threads help each other to complete their interrupted work in…

Not true. If a writer writes continuously the shared data, it is impossible for the other thread to make the copy that must be edited. If the copy succeeds, then you are right that an updated version could be substituted to the original using an atomic operation on pointers. But there is no way to guarantee that the first copy succeeds. Of course, in practice RCU is used very frequently, because all the other threads…

About what scenario are you actually talking? Are all threads using the read() and write() functions of the shared data structure? In that case it is absolutely possible for readers and writers to make progress even if a rogue writer is calling write() in a tight loop.

Or are you talking about a scenario where a rogue writer essentially randomly modifies the shared data structure instead of using the designated write() function? Well, in that case all bets are obviously off.

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#28

Post by eqvinox » Tue, Aug 04, 2026, 3:58 PM UTC

adrian_b wrote: post #20

eqvinox wrote: post #15

Earlier quoted context omitted.

I think you missed the point; seqlock based approaches will lock dead if you suspend/abort a thread in the wrong place. Other lock-free approaches don't have this issue. This isn't about a thread writing garbage, it's about guarantees applicable within the constraints.

No, you missed my point. I agree that there is the risk for a writer to be halted in the middle of its critical section, which would stop all the other writers and readers. My point is that there exists no solution that is risk free, because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm, regardless if it is claimed to be wait-free. There exists no me…

> if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm

No, it won't, not in a wait-free algorithm. For lock-free algorithms, yes, it's a matter of scheduling and stochastics.

But this is not the case for seqlocks. You don't need an infinite loop, you don't need to keep writing. Just stop the thread after it set the seqlock value to odd ("being modified"). Because it's not lock-free.

(I do agree that a lot of this is overblown and ill-applied; "lock-free" just sounds good and it's sufficiently available that people reach for it and end up overusing it. However, there are cases where it matters and is absolutely appropriate, and it also matters that we are able to have a conversation about these situations and conditions and use the terminology in a consistent manner.)

> using a lock for writers and using the method from TFA for readers

Case in point, I'm confused what you mean there, what do you mean with "method from TFA"? I don't see how anything in the article combines with a lock for writers.

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#29

Post by danbruc » Tue, Aug 04, 2026, 4:02 PM UTC

eqvinox wrote: post #28

adrian_b wrote: post #20

Earlier quoted context omitted.

No, you missed my point. I agree that there is the risk for a writer to be halted in the middle of its critical section, which would stop all the other writers and readers. My point is that there exists no solution that is risk free, because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm, regardless if it is claimed to be wait-free. There exists no me…

> if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm No, it won't, not in a wait-free algorithm. For lock-free algorithms, yes, it's a matter of scheduling and stochastics. But this is not the case for seqlocks. You don't need an infinite loop, you don't need to keep writing. Just stop the thread after it set the seqlock value to odd ("being modified"). B…

I suspect adrian_b is talking about a scenario where a rouge thread essentially writes random garbage to random addresses in the address space.

Re: Safe Lock-free Primitives with iceoryx2's ByteAtomic

#30

Post by eqvinox » Tue, Aug 04, 2026, 4:07 PM UTC

danbruc wrote: post #29

eqvinox wrote: post #28

Earlier quoted context omitted.

> if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm No, it won't, not in a wait-free algorithm. For lock-free algorithms, yes, it's a matter of scheduling and stochastics. But this is not the case for seqlocks. You don't need an infinite loop, you don't need to keep writing. Just stop the thread after it set the seqlock value to odd ("being modified"). B…

I suspect adrian_b is talking about a scenario where a rouge thread essentially writes random garbage to random addresses in the address space.

ACK. I hadn't read the other arc of this thread yet, I think we're having a failure of communication... along the lines of looking at things from the perspective of a different layer, or something like that.