4

I am working on a set that is frequently read but rarely written.

class A {
  boost::shared_ptr<std::set<int> > _mySet;
public:
  void add(int v) {
    boost::shared_ptr<std::set<int> > tmpSet(new std::set<int>(*_mySet));
    tmpSet->insert(v);  // insert to tmpSet
    _mySet = tmpSet;    // swap _mySet
  }
  void check(int v) {
    boost::shared_ptr<std::set<int> > theSet = _mySet;
    if (theSet->find(v) != theSet->end()) {
      // do something irrelevant
    }
  }
};

In the class, add() is only called by one thread and check() is called by many threads. check() does not care whether _mySet is the latest or not. Is the class thread-safe? Is it possible that the thread executing check() would observe swap _mySet happening before insert to tmpSet?

paper
  • 165
  • 1
  • 6
  • I think this would be threadsafe if the swap of shared_ptr is atomic. Otherwise you could have a partial swap at the end of add, and a partial copy at the start of check. You could probably replace shared_ptr with an real atomic pointer type class and then this algorithm would be correct. –  Feb 07 '12 at 06:46

3 Answers3

2

You do need synchronization, it is not thread safe. Generally it doesn't matter, even something as simple as shared += value; is not thread safe.

look here for example with regards to thread safety of shared_ptr: Is boost shared_ptr <XXX> thread safe?

I would also question your allocation/swapping in add() and use of shared_ptr in check()

update:

I went back and re-rad dox for shared_ptr ... It is most likely thread-safe in your particular since the reference counting for shared_ptr is thread-safe. However you are doing (IMHO) unnecessary complexity by not using read/write lock.

Community
  • 1
  • 1
Anycorn
  • 50,217
  • 42
  • 167
  • 261
  • I understand why `shared += value` is not thread-safe as it is a read-modify-write operation. But is a copy-and-swap for pointer non-thread-safe because the object referred by the pointer could be in an inconsistent state or something else? The shared_ptr in check() ensure the find() and end() applies to the same object. Is there something wrong? – paper Feb 07 '12 at 07:21
  • 1
    @Anycorn: Reference counting itself is thread safe, but copying, moving or assignment of shared_ptr are not synchronized with the reference counting, these operations therefore are NOT atomic on "volatile" shared pointers. It seems your initial answer is right, but the update is wrong :) – user396672 Feb 07 '12 at 15:18
2

This is an interesting use of shared_ptr to implement thread safety. Whether it is OK depends on the thread-safety guarantees of boost::shared_ptr. In particular, does it establish some sort of fence or membar, so that you are guaranteed that all of the writes in the constructor and insert functions of set occur before any modification of the pointer value becomes visible.

I can find no thread safety guarantees whatsoever in the Boost documentation of smart pointers. This surprizes me, as I was sure that there was some. But a quick look at the sources for 1.47.0 show none, and that any use of boost::shared_ptr in a threaded environment will fail. (Could someone please point me to what I'm missing. I can't believe that boost::shared_ptr has ignored threading.)

Anyway, there are three possibilities: you can't use the shared pointer in a threaded environment (which seems to be the case), the shared pointer ensures its own internal consistency in a threaded environment, but doesn't establish ordering with regards to other objects, or the shared pointer establishes full ordering. Only in the last case will your code be safe as is. In the first case, you'll need some form of lock around everything, and in the second, you'll need some sort of fences or membar to ensure that the necessary writes are actually done before publishing the new version, and that they will be seen before trying to read it.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • Apparently recent boost libraries support atomic_load/atomic_store operations on shared_ptr but seems their implementation use spinlocks, it is a controversal choice from the performance viwepoint (see also my answer) – user396672 Feb 07 '12 at 12:45
  • .. hmm I don't see volatile variant for atomic_load/store in http://www.boost.org/doc/libs/1_48_0/boost/smart_ptr/shared_ptr.hpp I don't understand why.. they apparently use spinlock but do not provide volatile variant.. – user396672 Feb 07 '12 at 12:50
  • @user396672 To get the locking, you'd have to use `atomic_store` and `atomic_load` for all of the accesses to the `shared_ptr`. Otherwise, there's absolutely no protection: `operator=` is based on `swap`, and `swap` swaps the two pointers independently. (This is, in fact, the classical guarantee: in the original code, a thread modifies the smart pointer, and other threads access it, so some sort of external synchronization is required.) – James Kanze Feb 07 '12 at 13:59
  • you are right, all access operations should be atomic (in my answer I forgot u*_mySet paramiter used in the set ctor, the parameter shoud be *atomic_load(_mySet) – user396672 Feb 07 '12 at 15:02
0

Eventually this code should be thread safe:

atomic_store(&_my_set,tmpSet);

and

theSet = atomic_load(&_mySet);

(instead of simple assignments)

But I don't know the current status of atomicity support for shared_ptr.

Note, that adding atomicity to shared_ptr in lock-free manner is really dificult thing; so even atomicity is implemented it may relay on mutexes or usermode spinlocks and, therefore, may sometimes suffer from performance issues

Edit: Perhaps, volatile qualifier for _my_set member variable should also be added.. but I'm not sure that it is strictly required by semantics of atomic operations

user396672
  • 3,106
  • 1
  • 21
  • 31
  • I wouldn't expect `atomic_store` and `atomic_load` to be defined on a smart pointer. The standard requires implementations for the integral types and (raw) pointers, and nothing else. Unless I've overlooked something (quite possible), no class type (nor even the floating point types) support atomic operations. And as you say, about the only way an implementation of `shared_ptr` can be "atomic" is to use a lock of some sort, in which case, you might as well make it explicit. – James Kanze Feb 07 '12 at 14:06
  • 1
    @James Kanze: the Standard has a special paragraph (20.7.2.5 shared_ptr atomic access) that lists the atomic functions specializations for shared_ptr and their meaning (it is not clear for me are these specializations required or optional), cppreference also lists atomics as a part of shared_ptr description (http://en.cppreference.com/w/cpp/memory/shared_ptr), boost currently implements atomic load/store (although undocumented) I'm pretty sure that atomic support for shared_ptr will be generally available (although I'm doubt it is widely available right now). – user396672 Feb 07 '12 at 14:51
  • It was my understanding, back when I was an active participant in the standardization effort, that the purpose of the atomic functions was to provide portable support for lock-free algorithms, and the intent was only to provide them for types which could potentially be updated and read without a lock (but with fences or membars). This may have changed, however. But I don't really see any interest in having them for other types; if you need a lock, it's better that the client code provide it. – James Kanze Feb 07 '12 at 16:15
  • @James: I generally agree, but shared_ptr is not an ordinary "other type", and some interest, of course, presents (meanwhile OP's question indirectly confirms this interest). Unfortunatelly, it seems there are no widely (and freely) available lock-free implementation, the problem is hard enough and patent-mined. I agree that lock- or spinlock-based palliatives are rather unusable but their appearance expresses a trend, so some hope remains :) – user396672 Feb 07 '12 at 16:54