Subj : Re: experimental smr-based 100% lock-free eventcount schema for windows...
To   : comp.programming.threads
From : SenderX
Date : Wed Feb 02 2005 07:02 am

> 1) atomically increment the eventcount
> 2) atomically swap the current event object with a new
>    unsignaled event object.
> 3) signal the swapped out (old) event object and
>           drop the reference to it.  Old event object will be
>    GC'd when there are no waiters using it.

I see. The signaler should be responsible for removing the global pointer to
the event object and enqueueing the deferred callback for it. Makes perfect
sense.


> 1) get pointer to current event object.
> 2) atomically compare current eventcount with local copy to
>    see if eventcount has changed

 Ahh, I was doing step 2 before step 1. That would solve the race-condition
I found.


> 3) if eventcount unchanged, wait on event object.

Yes, then after the wait a thread would set its hazard pointer to null and
allow for the garbage collection to occur... Simple, and no dwcas
involved... Well, that would work just fine.




This code follows this logic:


typedef struct ac_waitset_
{
 struct ac_waitset_ *next; /* set to 0 */
 HANDLE gate; /* manual reset event, val = 0  */

} ac_waitset_t;


typedef struct ac_event_count_
{
 volatile ac_waitset_t *active_waitset; /* set to new allocated waitset */
 volatile DWORD ec; /* set to anything */

} ac_event_count_t;


/* gc deferred callback */
VOID ac_waitset_dtor( LPVOID s )
{
    ac_waitset_t *wset = s;
    wset->next = 0;
    ResetEvent( wset->queue );
    ac_waitset_cache_push( wset );
}


DWORD ac_event_count_wait
( ac_event_count_t *_this,
  DWORD ec_cmp,
  DWORD timeout )
{
    DWORD wait_ret = WAIT_OBJECT_0;
    register ac_waitset_t *wset;
    register void **hazard ac_lfgc_get_hazard( 1 );

    /* 1) get pointer to current event object. */
    do
    {
        wset = _this->active_waitset;
        *hazard = wset;

    } while ( wset != _this->active_waitset );

    /* 2) atomically compare current eventcount with local copy to
        see if eventcount has changed */
    if ( InterlockedCompareExchange
            ( &_this->ec,
              ec_cmp,
              ec_cmp ) == ec_cmp )
    {
        /* 3) if eventcount unchanged, wait on event object. */
        wait_ret = WaitForSingleObject( wset->queue );
    }

    *hazard = 0;

    return wait_ret;
}


VOID ac_event_count_signal
( ac_event_count_t *_this )
{
    register ac_waitset_t *wset;

    /* 1) atomically increment the eventcount */
    InterlockedIncrement( &_this->ec );

    /* 2) atomically swap the current event object with a new
        unsignaled event object. */
    wset =  InterlockedExchangePointer
                ( &_this->active_waitset
                  ac_waitset_cache_pop() );

    /* 3) signal the swapped out (old) event object and
        drop the reference to it.  Old event object will be
        GC'd when there are no waiters using it. */
    SetEvent( wset->queue );
    ac_lfgc_collect( wset, ac_waitset_dtor );
}


DWORD ac_event_count_get
( ac_event_count_t *_this )
{
    return InterlockedExchangeAdd
                ( &_this->ec,
                  0 );
}


The signal function could be improved with a waiters bit embedded in the
eventcount...

.