Boost logo

Boost :

From: Talbot, George (Gtalbot_at_[hidden])
Date: 2008-07-23 10:29:13


Thanks for responding.

> -----Original Message-----
> From: boost-bounces_at_[hidden]
> On Behalf Of Dean Michael Berris
> Sent: Tuesday, July 22, 2008 9:24 PM
> To: boost_at_[hidden]
> Subject: Re: [boost] Would anybody like a wrapper atomic_shared<T>
> aroundshared_ptr<T>?
> Hi George,
> On Wed, Jul 23, 2008 at 6:04 AM, Talbot, George
> wrote:
> >
> > A while back (~2006 I think) I was asking around on this list about
> > using boost::shared_ptr<T> to build a composite data structure that
> > be accessed and modified by multiple threads.
> >
> > Peter Dimov's suggestion at the time was to write a wrapper class
> > boost::shared_ptr<T> that would protect access to the
> > boost::shared_ptr<T> with a spinlock. I've done this, and this
> > pretty good in my application. I'm interested in contributing this
> > to BOOST, as it's been quite useful.
> >
> > I have a few questions:
> >
> > 1) Is there interest in such a donation. It's just one header
> > and it's wafer-thin...
> I am interested, although I do have some reservations with it not
> using the locks already available in Boost.Thread.

I would likely convert it to do so. Haven't got around to that yet.

> > 2) If so, how does one go about making such a donation?
> (I think it's a little funny that you use 'donation' instead of
> contribution... but nonetheless... ;-) )

Sorry....contribution. I'm a bit of a space cadet. ;^)

> >From what I gather, this is something that may have to go through a
> mini-review. The veterans can answer this question better though.

I'm sure, and that would be great, actually.

> > 3) My implementation below uses a spinlock to protect things and
> > as one might expect, under load my application does spend some
> > time in ::pthread_spin_lock(). Is there a way to rewrite this
> > class (possibly with friendship of boost::shared_ptr<T>) in a
> > lock-free manner? I've attached the code below...
> >
> I'm not sure about lock-free approaches, but doesn't shared_ptr<T>
> already use atomic operations when built in multi-threaded mode?

Yes, but read the Thread Safety page. The guarantee you get from
shared_ptr<T> is that two or more separate instances in separate threads
that point to the same object and refcount will be handled lock-free and
work properly. However it explicitly does not guarantee multiple
threads looking at the _same_ instance of shared_ptr<T> can perform
operations upon that same instance without some sort of additional
guarantees. The purpose of this class is to provide that guarantee.

> Another issue I see is the dependence to ::pthread_spin_lock() -- can
> you use a shared recursive_mutex instead?

How expensive is that in memory and time? I was using
::pthread_spin_lock() because on my x86_64 Linux box, pthread_spinlock_t
is a single machine word.

Also, it's just a proof-of-concept. I think the "right thing" is to be
able to implement the unary bool operators, get() and compare_and_set()
via a lock-free algorithm. My problem is that I don't have enough depth
of knowledge of the lock-free shared_ptr<T> class in BOOST to be able to
work out such an algorithm. I was hoping for a little bit of "pointing
in the right direction" from the author(s) of BOOST's lock-free
shared_ptr<T> implementation.

That said I'd have no problem "falling-back" to using a shared
recursive_mutex instead if a lock-free algorithm isn't available on a
particular platform. As such, attached below is a rewrite using
recursive_try_mutex...This appears similar in execution efficiency to my
previous implementation with the spinlock in my stress test. It appears
from examining the pthread libraries that the mutex is using about 8
machine words instead of one for the spinlock.

Of course, as above, I'd prefer no lock at all; I'll see what I can come
up with.

Thanks for looking at this.

George T. Talbot
/** \file           atomic_shared.h
 *  \author         George T. Talbot
 *  \author         Peter Dimov
 *  \brief          This file defines a template class that can wrap
 *                  boost::shared_ptr and provide thread-safe atomic
 *                  get/set operations on them.
 *  (C) Copyright Locus Pharmaceuticals, Inc., Peter Dimov 2006.
 *  Distributed under the Boost Software License, Version 1.0. (See
 *  accompanying file LICENSE_1_0.txt or copy at
#include <boost/shared_ptr.hpp>
#include <boost/pointer_cast.hpp>
#include <boost/thread/recursive_mutex.hpp>
/** atomic_shared<T> wraps boost::shared_ptr<T> with a mutex and a very
 *  restricted set of operations so that a large composite data
 *  may be accessed by multiple threads with a minimum of locking
 *  Threads working on a large composite data structure create their own
 *  private boost::shared_ptr<T> around their own new nodes and then use
 *  compare_and_set() to place their new nodes in the composite data
 *  structure.
 *  Threads that are viewing the composite data structure may call get()
 *  get a private copy of the pointer so they can do some work with it.
 *  intended idiom for modifications to nodes is like so:
 *  \code
 *      atomic_shared<const Blah>   global_blah;
 *      void    modify_the_global_blah_in_many_threads_with_no_locking()
 *      {
 *          bool    done = false;
 *          do
 *          {
 *              boost::shared_ptr<const Blah>
 *              boost::shared_ptr<Blah>         new_blah(*my_blah);
 *              new_blah->some_modification();
 *              done    = global_blah.compare_and_set(my_blah,
 *          }
 *          while (!done);
 *      }
 *  \endcode
 *  Threads that just need to do some work looking at the node:
 *  \code
 *      void    print_the_global_blah_in_many_threads_with_no_locking()
 *      {
 *          boost::shared_ptr<const Blah>   my_blah(global_blah.get());
 *          my_blah->print();
 *      }
 *  \endcode
 *  Using atomic_shared<T> this way satisfies the Thread Safety portion
 *  the boost::shared_ptr<T> documentation.
template<class T>
class atomic_shared
    atomic_shared&  operator=(const atomic_shared&);
    typedef boost::shared_ptr<T>            base_ptr;
    /** construct an empty pointer. */
        : ptr(),
    /** copy constructor.  Since we like to put atomic_shared<> in
     *  via std::map<atomic_shared<T> >::insert(std::make_pair(key,
     *  this needs to be here.
    atomic_shared(const atomic_shared& p)
        : ptr(p.get()),
    /** construct a protected pointer from a bare one. */
    template<class Y>
    explicit atomic_shared(Y* p)
        : ptr(p),
    /** construct a protected pointer from a shared_ptr. */
    template<class U>
    explicit atomic_shared(const boost::shared_ptr<U>& p)
        : ptr(p),
    /** Is it not null? */
    operator bool() const
        bool    rv;
            boost::recursive_try_mutex::scoped_lock  l(mutex);
            rv  = ptr;
        return rv;
    /** Is it null? */
    bool    operator!() const
        bool    rv;
            boost::recursive_try_mutex::scoped_lock  l(mutex);
            rv  = !ptr;
        return rv;
    /** Right here is the only way to _use_ the pointer.  To use what
     *  pointer is pointing to, you must make a private copy in your
     *  thread.
    inline base_ptr get() const
        base_ptr    p;
            boost::recursive_try_mutex::scoped_lock  l(mutex);
            p = ptr;
        return p;
    /** Attempt to set the value of the pointer with another pointer,
     *  only if the pointer is the same as a previously sampled value of
     *  the pointer.
     *  @param  cmp     Value of pointer previously retrieved with
     *  @param  x       New value of pointer.
     *  @return true if the pointer could be set to x (i.e. its value
     *               still cmp with the mutex locked.)
    template<class Y, class X>
    bool    compare_and_set(const boost::shared_ptr<Y>& cmp,
                            boost::shared_ptr<X>&       x)
        bool    r = false;
        boost::recursive_try_mutex::scoped_try_lock  l(mutex, false);
        if (l.try_lock())
            r = ptr == cmp;
            if (r) ptr = x;
        return r;
    base_ptr                            ptr;
    mutable boost::recursive_try_mutex  mutex;
};  // atomic_shared

Boost list run by bdawes at, gregod at, cpdaniel at, john at