Subj : sketch for a simple smr based reference count api...
To   : comp.programming.threads
From : Chris Thomasson
Date : Fri Mar 25 2005 03:24 am

Anybody notice any major problems? In particular, I was wondering about 
calling the user state dtor when the reference count goes to zero. I think 
it might be safe because the ref_node_load function does not touch the 
actual user state, and it does not try to inc a reference count that isn't 
greater than zero. The only object that is garbage collected is ref_node_t 
since it could drop to zero and be destroyed during an addref. SMR is used 
to protect against this race-condition. As you can see, the ref_node_load 
function is extremely expensive because of the darn hazard pointer loop. 
Humm...

:O




This should provide the all the basic pointer operations required for a 
generic smart pointer implementation. I guess they could call it 
boost::shared_smr_ptr< T >...

;)

<just a very rough sketch>


smr reference counted node api
-------------------------------

ref_node_alloc - inits node
ref_node_get - gets user state
ref_node_smr_dtor - SMR dtor
ref_node_release - release a node
ref_node_load - loads a node
ref_node_store - stores to a node
ref_node_copy_local - copies a local node
ref_node_copy_shared - copies a shared node
ref_node_cas - CAS a node




basic pointer ops
------------------

local = *shared;
ref_node_load( &local, shared );


*shared = local;
ref_node_store( shared, &local );


*shared1 = *shared2;
ref_node_copy_shared( shared1, shared2 );


local1 = local2;
ref_node_copy_local( &local1, local2 );




source
-------

typedef struct ref_node_
{
  int refs;
  void ( *fp_dtor ) ( void* );
  void *state;

} ref_node_t;




/* init */
ref_node_t* ref_node_alloc
( void ( *fp_dtor ) ( void* ),
  void *state )
{
  ref_node_t *_this = malloc( sizeof( *_this ) );

  if ( _this )
  { _this->refs = 1;
    _this->fp_dtor = fp_dtor;
    _this->state = state;
  }

  return _this;
}




/* gets the users state */
void* ref_node_get
( ref_node_t *_this )
{
  return ( _this ) ? _this->state : 0;
}




/* smr would call this from its "scan" function */
void ref_node_smr_dtor
( void *state )
{
  ref_node_t *_this = state;
  assert( ! _this->refs && ! _this->s );
  free( _this );
}




/* releases the reference count */
void ref_node_release
( ref_node_t *_this )
{
  if ( _this &&
       atomic_dec_release( &_this->refs ) == 1 )
  { _this->fp_dtor( _this->s );

    /* defer the free via. SMR */
    smr_collect( ref_node_smr_dtor, _this );
  }
}




/* loads a reference */
void ref_node_load
( ref_node_t **pdest,
  ref_node_t **psrc )
{
  int refs;
  ref_node_t *src, *old = *pdest;

  for ( ;; )
  { /* expensive smr loop */
    src = atomic_load_naked( psrc );
    do
    { if ( ! src ) { break; }
      hptr_store_fence( 0, src );
      src = atomic_load_acquire( psrc );
    } while ( src != hptr_load_naked( 0 ) );

    /* addref */
    refs = src->refs;
    while ( refs > 0 )
    { if ( atomic_cas_acquire
            ( &src->refs,
              refs,
              refs + 1 ) == refs )
      { hptr_store_release( 0, 0 );
        goto ref_node_load_ok;
      }
      refs = src->refs;
    }
  }

ref_node_load_ok:
  atomic_store_release( pdest, src );
  ref_node_release( old );
}




/* stores a reference */
void ref_node_store
( ref_node_t **pdest,
  ref_node_t *src )
{
  if ( src ) { atomic_inc_acquire( src, 1 ); }
  ref_node_release
    ( atomic_xchg_release
        ( pdest,
          src ) );
}




/* copys a local reference */
void ref_node_copy_local
( ref_node_t **pdest,
  ref_node_t *src )
{
  ref_node_t *old = *pdest;
  if ( src ) { atomic_inc_acquire( src, 1 ); }
  atomic_store_release( pdest, src );
  ref_node_release( old );
}




/* copys a shared reference */
void ref_node_copy_shared
( ref_node_t **pdest,
  ref_node_t **psrc )
{
  ref_node_t *temp;
  ref_node_load( &temp, psrc );
  ref_node_store( pdest, &temp );
  ref_node_release( &temp );
}




/* cas a reference */
int ref_node_cas
( ref_node_t **pdest,
  ref_node_t *cmp,
  ref_node_t *xchg )
{
  if ( xchg ) { atomic_inc_acquire( xchg, 1 ); }

  if ( atomic_cas_release
        ( pdest,
          cmp,
          xchg ) == cmp )
  {
    ref_node_release( cmp );
    return 0;
  }

  ref_node_release( xchg );
  return 1;
}




-- 
http://appcore.home.comcast.net/
(portable lock-free data-structures)

.