Re: How to make reference counting thread-safe

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2000-09-11 17:45:16

Kaz Kylheku wrote:

> On Sun, 10 Sep 2000 23:19:38 -0500, Larry Evans <jcampbell3_at_[hidden]> wrote:
> >
> >Kaz Kylheku wrote:
> >
> >> On Mon, 28 Aug 2000 20:49:24 +0200, Frederic Chauvin
> >> <frederic.chauvin_at_[hidden]> wrote:
> >> >Hi,
> >> >
> >> >I'm developing a C++ application and which uses extensively smart
> >> >pointers and reference counting in a fashion similar to Microsoft's
> >> >IUnkown::AddRef/Release.
> >> >My question is: how to make this mecanisn thread-safe?
> >>
> >> You must ensure that the reference count increments and decrements are atomic
> >> operations. This means that you need a lock around these operations.
> >
> >Even with atomic increment and decrement, wouldn't there be the race condition
> >described in figs 4&5 of  the article at www-sor.inria.fr/publi/SDGC_iwmm95.html ?
>
> No. This paper is talking about distributed reference counting. The particular
> race condition example involves message passing communications.
>
> I was only talking about straightforward reference counting within the address
> space of a threaded process (i.e. squarely within the topic for
> comp.programming.threads).
>
> No such race occurs in this situation because the handoff of a reference
> between one subsystem and another is typically done synchronously.  E.g.
> subsystem A holds a reference to an object managed by subsystem B, and wants
> to pass it to C. It calls a function within C which increments the reference.
> Upon returning, A releases its reference. There is no race because everything
> is done in order by the calling thread.

I've attached a file which I hope illustrates why I still don't agree.

Each  access to RefCountAny::m_nrefs is made atomic by use of `Sentry s(m_lock)`
in each method which changes m_nrefs.

An example of a thread schedule which causes premature deletion is indicated
by comments of the form:

  //step_<i>:<op><thread_id>

where:
   <i> is an integer indicating execution order
   <thread_id> is either main_t or sub_t which are thread id's
   <op> is either:
       +  indicating <thread_id> is resuming execution
       -  indicating <thread_id> is yielding to the other thread

Between step_5 and step_6,  pointee1 is deleted; however, step_7 and step_8 shows
sub_t still accessing pointee.

Does this convince you, or is there something I'm missing?

Thanks for you patience.


#include <pthread.h>
#include <stdio.h>
//========================================
  class 
Lock
  {
  public:
    Lock(void)
      { pthread_mutex_init(&m_mutex,NULL)
      ;}
    ~Lock(void)
      { pthread_mutex_destroy(&m_mutex)
      ;}
      void
    lock(void)
      { pthread_mutex_lock(&m_mutex)
      ;}
      void
    unlock(void)
      { pthread_mutex_unlock(&m_mutex)
      ;}
  private:
      pthread_mutex_t 
    m_mutex
      ;
  };
//========================================
  class 
Sentry
  {
  public:
    Sentry(Lock&a_lock)
      : m_lock(a_lock)
      { 
      ; m_lock.lock()
      ;}
    ~Sentry(void)
      { 
      ; m_lock.unlock()
      ;}
  private:
      Lock& 
    m_lock
      ;
  };
//========================================
  class 
SmartPtr
  ;
  class
RefCountAny
  {
  friend SmartPtr;
  public:
        typedef
      RefCountAny
    ThisType
      ;
        typedef
      unsigned
    NrefsType
      ;
        virtual
    ~RefCountAny(void)
      {
      ;}
    RefCountAny(void)
      : m_nrefs(0)
      {
      ;}
    RefCountAny(RefCountAny const&)
      : m_nrefs(0)
      {
      ;}
      RefCountAny const&
    operator=(RefCountAny const&)
      { return *this
      ;}
  private:
      NrefsType
    inc_nrefs(void)
      { 
      ; NrefsType res=0
      //step_4:-sub_t
      //step_7:+sub_t
      ; {
        ; Sentry s(m_lock)
        ; res=++m_nrefs
        ;}
      ; return res
      //step_8:-sub_t
      ;}
      NrefsType
    dec_nrefs(void)
      { 
      ; NrefsType res=0
      ; {
        ; Sentry s(m_lock)
        ; res=--m_nrefs
        ; if(res==0) delete this
        ;}
      ; return res
      ;}
      NrefsType
    m_nrefs
      //The number of references to this instance
      ;
        mutable
      Lock
    m_lock
      //To make accesses and changes to m_nrefs atomic
      ;
  };
//========================================
  class 
SmartPtr 
  {
  public:
        typedef
      SmartPtr
    ThisType
      ;
    SmartPtr(RefCountAny*p=0)
      : pointee_(p)
      { inc_nrefs()
      ;}
    SmartPtr(SmartPtr const&p)
      : pointee_(p.pointee_)
      { 
      ; inc_nrefs()
      ;}
    ~SmartPtr()
      { dec_nrefs()
      ;}
      ThisType const&
    operator=(RefCountAny*p)
      {
      ; if(p!=pointee_)
        { dec_nrefs()
        ; pointee_=p
        ; inc_nrefs()
        ;}
      ; return *this
      ;}
      ThisType const&
    operator=(SmartPtr const&sp)
      { return operator=(sp.pointee_)
      ;}
      bool
    valid(void)const
      { 
      ; return !(pointee_==0)
      ;}  
  private:
      RefCountAny*
    pointee_
      ;
      RefCountAny::NrefsType
    dec_nrefs(void)
      { RefCountAny::NrefsType res=0
      ; if(valid() && (res=pointee_->dec_nrefs()) == 0)
        {
        ; pointee_=0
        ;}
      ; return res
      ;}
      RefCountAny::NrefsType
    inc_nrefs(void)
      { RefCountAny::NrefsType res=0
      ; if(valid())
        { 
        ; res=pointee_->inc_nrefs()
        ;}
      ; return res
      ;}
  };
//========================================
  void*
thread_sub(void*v_arg)
  ;
//========================================
  pthread_t
main_t
  //main thread
  ;
  pthread_t
sub_t
  //thread_sub thread
  ;
  int
main(void)
  { 
//step_1:+main_t
  ; int ret=0
  ; main_t=pthread_self()
  ; RefCountAny*pointee1=new RefCountAny
  ; SmartPtr sp1(pointee1)
  ; ret=pthread_create(&sub_t,0,thread_sub,&sp1)
  ; if(ret)return ret
//step_2:-main_t
//step_5:+main_t 
  ; RefCountAny*pointee2=new RefCountAny
  ; sp1=pointee2
//step_6:-main_t
//step_9:+main_t
  ; ret=pthread_join(sub_t,0)
  ; if(ret)return ret
  ; return 0
  ;}  
//========================================
  void*
thread_sub(void*v_arg)
  { 
//step_3:+sub_t
  ; SmartPtr*sp1=static_cast<SmartPtr*>(v_arg)
  ; SmartPtr sp2(*sp1)
  ; return ((void*)0)
  ;}