Atomically setting an Option in lock-free code

help
1

I have a large array of Option<T>. I know T will have a niche in all its uses.

this array can be accessed in multiple threads, in particular, any thread may iterate over all the array's contents. I want to be able to set one of the array's elements to Some. I have external synchronization methods in place that will ensure only one thread at a time will try setting an element to Some.

I could easily do this with an (AtomicBool, MaybeUninit<T>), but I don't want to increase the size of the array, as it will be very large in practice.

it should be possible to write all of T into the cell besides the Option, then atomically write the value into the niche part.

in practice, T will only be one of a few different types, so if i have to use a trait and a custom type to re-implement the niche optimization in a way that is guaranteed, that is acceptable.

1 Like
2

There is no "then" in atomics. It all has to be written at once.

This should work. You'd have an associated type that specifies which of the Atomic* types is the same size as your Option<T>. The array would store something like union Value<Atomic, T> { Atomic, Option<T> }.

Then you don't need atomics, you can just unsafely write it.

3

I disagree with @drewtato on some points. You are right that in principle it should be possible. But Option doesn't support this.

In general Rust does not have a strong story for data structures that can have both many readers and one writer at the same time, doing lock-free monotonic changes. if you know of a crate for this, let me know. I've had to design it from scratch for work.

I guess we could open source ours, but it is not the most fun to use. It's arena based and fairly conceptually heavy.

4

I'm saying you will first use a number of non-atomic writes (which is sound in exactly the same way you can use non-atomic writes to shared data protected by a mutex), then use a final atomic write to synchronize.

well, sounds like i'm reinventing what you already did, because what i'm building is also arena based (currently built on top of AppendOnlyVec, but that might change, since that isn't lock-free).

basically, what i want is a lock-free single-producer multi-consumer oneshot channel, except it can be read from multiple times to get the same value.

5

What about SeqLock — Rust concurrency library // Lib.rs?

6

This is not necessarily possible. Counterexample: Option<NonZeroU64>, compiled on a a target that does not have cfg(target_has_atomic = "64") — or Option<NonZeroU128> anywhere. In this case, the niche is a value too wide to be written atomically, so there is no pattern of writes and reads which avoids the reader racing with the writer when trying to check the Option's discriminant.

1 Like
7

Since you said you already have synchronization to protect the writes, you don't any other "final atomic write to synchronize". That's why they said "you can just unsafely write it".

Note that such abstractions with unsafe code should have strictly limited APIs so the unsafe aspects can be thoroughly tested and audited. Ideally it would be general purpose and published as a separate crate, but this isn't always practical.

1 Like
8

yes, i know, in that case it would be acceptable to fall back to just adding another field

9

So you want OnceCell?

Edit: I meant OnceLock but with a Once that uses the niche.

2 Likes
10

I have synchronization to protect against concurrent writes, but not concurrent reads, which must be allowed to happen. these reads will always check the niche/discriminant first, so the payload can be written non-atomically, but the discriminant must be written atomically.

1 Like
11

I think the way to go is to write an unsafe trait AtomicNiche and implement your own tagged union.

12

believe it or not, OnceLock is not lock-free.

13

that's what i've been doing :p

14

It would help to show the type, and say why it doesn't work. You haven't actually asked an explicit question, which may be why there is some confusion.

15

I suppose my question is "is there an easy way to do this, and is it even a coherent thing to do"

so far it seems like the answers are no, yes.

16

I thought OnceLock should be lock-free if there’s only a single writer, isn’t it?

1 Like
17

Readers can be concurrent with that single writer.

18

Which should not result in any locking, still, should it?

1 Like
19

Right. I may be miscommunicating or misunderstand. But I think the issue is that readers have no synchronization, they just do two atomic loads that read different parts of the value. The first atomic load checks the discriminator, and if it is "none" the read doesn't go further. If "not none", the read then does an atomic load of the rest of the value.

It would really help me to see the actual types. Or at least an attempt at doing them. I think the idea is to design a type with an explicit niche that can be an atomic type, and also has an atomic type for the rest of the value. Maybe designing this type is the actual problem at hand? But we don't know what the values are.

Edit: Sorry, this whole time I've been reading OnceCell when you wrote OnceLock, because OnceCell was the first thing mentioned further above.

20

OnceLock seems to be backed by a futex, meaning trying to access it results in a system call. this is completely unacceptable for my usecase.

I don't need any "thread parking", just the ability to check its emptyness atomically.