search

bossmc / pinboard

A threadsafe way to publish data, just stick it on the pinboard
MIT License
28 stars 4 forks source link

Requires `AcqRel` for `set()` and `clear()`? #8

Closed jeehoonkang closed 6 years ago

jeehoonkang commented 6 years ago

I think, in set() and clear(), it's necessary to swap self.0 with the AcqRel ordering (instead of Release). Because otherwise, guard.unlinked(t) is not necessarily happening after the initialization of the data contained in t.

For example, suppose that an invocation "A" of set() writes a value t and another invocation "B" of set() is replacing t. Then B's invocation of guard.unlinked(t) should happen after A's invocation of Owned::new(t). However, with only Release ordering we cannot guarantee that.

By the way, thank you for building this wonderful library. I needed pinboard in building a new version of Crossbeam, so I reimplemented it with the name AtomicBox: https://github.com/jeehoonkang/crossbeam-epoch/blob/hazard-pointer/src/sync/atomic_box.rs (warning: no documentation at all yet!) I'll properly acknowledge the pinboard crate before submitting it as a PR to crossbeam-epoch.

bossmc commented 6 years ago

Hi @jeehoonkang, thanks for your kind words, I'm glad you find my project useful 😀!

When I first wrote pinboard I had the same worry as you (though less clearly formed) and asked on the #rust IRC channel. One of the crossbeam developers had a look and thought it looked okay, but he commented that the unlinked() call contains a AcqRel which meant that it would be fine. Possibly that's not true any more in the new crossbeam-epoch crate?

On the other hand, I intend my code outside crossbeam should be correct in and of itself, so if AcqRel is the right thing to do, I'd like to make the change. I'm not too familiar with the memory orderings so bear with me here (actually, I've convinced myself you're right, but I'll leave my notes here for posterity).

Release

When coupled with a store, all previous writes become visible to the other threads that perform a load with Acquire ordering on the same value.

Acquire

When coupled with a load, all subsequent loads will see data written before a store with Release ordering on the same value in other threads.

AcqRel

When coupled with a load, uses Acquire ordering, and with a store Release ordering.

In the set() function, we're swapping the value in the store for one in our hands. Hence we're performing both a read and a write. In your case there are two threads doing a set() simultaneously, they both use Release ordering, which means that neither of their reads are subject to the terms of the Release ordering (as neither uses Acquire) so previous writes in the first thread may not be visible to the second thread (including, as you point out, the constructor of the first thread's value) hence the second thread may read an incomplete value as a Shared<T>, attempt to call unlinked() on it and potentially invoke unsafe behaviour. I'm suspicious that unlinked() doesn't do anything dangerous (at least not until GC time), but I guess there's no guarantee in my code that the constructor of t becomes visible to the second thread ever :anguished:.

With AcqRel semantics, the second thread will see all writes in the first thread when it reads the pinboard, so it's certain to see a consistent view.

bossmc commented 6 years ago

Fix released in version 1.4.1. Thanks!