updated pseudo-code for my eventcount algorithm...

[Chris Thomasson]

Here is the original algorithm:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/aa8c62ad06dbb380

please note that the posted pseudo-code only has support for broadcasts;
adding signaling is trivial. Here is some slightly tweaked pseudo-code that
has timed waits, try waits, broadcasts and signals:

class eventcount
{
enum flags_e { WAITER_FLAG = 0x80000000, WAITER_MASK = 0x7FFFFFFF };

public:
typedef int count_t;

private:
pthread_mutex_t m_mutex;
pthread_cond_t m_cond;
mutable count_t volatile m_count;

public:
eventcount() : m_count( 0 ) {
// init mutex and cond
}

private:
bool inc(count_t local) {
if (local & WAITER_FLAG) {
pthread_mutex_lock(&m_mutex);

while (! ATOMIC_CAS(&m_ec, local, (local + 1) & WAITER_MASK)) {
local = ATOMIC_LOAD(&m_count);
}

pthread_mutex_unlock(&m_mutex);
return true;
}
return false;
}

public:
count_t get() const throw() {
count_t local = ATOMIC_LOAD(&m_count);
membar #StoreLoad | #LoadLoad;
ATOMIC_OR(&m_count, WAITER_FLAG);
return local & WAITER_MASK;
}

void signal() {
membar #StoreLoad | #StoreStore;
if (inc(ATOMIC_LOAD(&m_count))) {
pthread_cond_signal(&m_cond);
}
}

void broadcast() {
membar #StoreLoad | #StoreStore;
if (inc(ATOMIC_LOAD(&m_count))) {
pthread_cond_broadcast(&m_cond);
}
}

bool trywait(count_t cmp) {
int local = ATOMIC_LOAD(&m_count) & WAITER_MASK;
membar #LoadStore | #LoadLoad;
if ( local == cmp ) {
int ret = pthread_mutex_trylock( &m_mutex );
if (ret == EBUSY || ret == EAGAIN) {
return false;
} else if(ret) { assert(! ret); throw; }

ret = ((ATOMIC_LOAD(&m_count) & WAITER_MASK) == cmp);

pthread_mutex_unlock(&m_mutex);
if (! ret) { return false; }
}
return true;
}

bool timedwait(count_t cmp, const struct timespec *tout) {
int local = ATOMIC_LOAD(&m_count) & WAITER_MASK;
membar #LoadLoad;
if (local == cmp) {
pthread_mutex_lock( &m_mutex );

int ret = 0;
while(! ret && (ATOMIC_LOAD(&m_count) & WAITER_MASK) == cmp ) {
int ret = (tout) ? pthread_cond_timedwait(&m_cond, &m_mutex, tout) :
pthread_cond_wait(&m_cond, &m_mutex);
}

pthread_mutex_unlock(&m_mutex);
if (ret == ETIMEDOUT) {
if (tout) { return false; }
assert(tout); throw;
} else if(ret) { assert(! ret); throw; }
}

return true;
}

void wait(count_t cmp) { (void)timedwait(cmp, 0); }
};

I have been meaning to do this for some time.... I am going to update
AppCore's eventcount with this one fairly soon...

Any thoughts?

[Chris Thomasson]

DOH!:

> while (! ATOMIC_CAS(&m_ec, local, (local + 1) & WAITER_MASK)) {

^^^^^^^^^^^

Is suppose to be:

while (! ATOMIC_CAS(&m_count, local, (local + 1) & WAITER_MASK)) {

of course!

[Chris Thomasson]

[...]

OOPS!

> bool timedwait(count_t cmp, const struct timespec *tout) {
> int local = ATOMIC_LOAD(&m_count) & WAITER_MASK;
> membar #LoadLoad;

^^^^^^^^^^^^^^^^^^^

I think I need membar #LoadStore | #LoadLoad here.

> if (local == cmp) {
> pthread_mutex_lock( &m_mutex );
>
> int ret = 0;
> while(! ret && (ATOMIC_LOAD(&m_count) & WAITER_MASK) == cmp ) {
> int ret = (tout) ? pthread_cond_timedwait(&m_cond, &m_mutex, tout)
> :
> pthread_cond_wait(&m_cond, &m_mutex);
> }
>
> pthread_mutex_unlock(&m_mutex);
> if (ret == ETIMEDOUT) {
> if (tout) { return false; }
> assert(tout); throw;
> } else if(ret) { assert(! ret); throw; }
> }
>
> return true;
> }

[...]

Sorry for any confusion!

;^)

[Chris Thomasson]

Son of a bitch! One more typo:

[...]

> bool trywait(count_t cmp) {
> int local = ATOMIC_LOAD(&m_count) & WAITER_MASK;
> membar #LoadStore | #LoadLoad;
> if ( local == cmp ) {
> int ret = pthread_mutex_trylock( &m_mutex );
> if (ret == EBUSY || ret == EAGAIN) {
> return false;
> } else if(ret) { assert(! ret); throw; }
>
> ret = ((ATOMIC_LOAD(&m_count) & WAITER_MASK) == cmp);
>
> pthread_mutex_unlock(&m_mutex);

> if (! ret) { return false; }

^^^^^^^^^^^^^^^^^^^^^^^^

I was returning true when the counter and the comprand were equal! That
obviously has to be:

if (ret) { return false; }

> }
> return true;
> }

[Philippe Amarenco]

"Chris Thomasson" <cri...@comcast.net> writes:

> membar #LoadStore | #LoadLoad here.

Hi,

I can't find a resource on the web that precisely explains this
notation. Could you point one to me or explain it?

I mean, I see what is a load barrier, a store barrier but a
"LoadStore", a "LoadLoad" and "LoadStore | LoadLoad" is confusing
to me.

many thanks,

--
Philippe Amarenco, aka Phix
epita 2007 - GISTR - ACU - EpX

[Joe Seigh]

Philippe Amarenco wrote:
> "Chris Thomasson" <cri...@comcast.net> writes:
>
>
>>membar #LoadStore | #LoadLoad here.
>
>
> Hi,
>
> I can't find a resource on the web that precisely explains this
> notation. Could you point one to me or explain it?
>
> I mean, I see what is a load barrier, a store barrier but a
> "LoadStore", a "LoadLoad" and "LoadStore | LoadLoad" is confusing
> to me.
>
> many thanks,
>

You need to look at the sparc programmers guide / architecture manual
in the memory model section to see what they mean. They're used in
discussions since they offer more precise specification of what memory
ordering you need.

Good luck trying to find an online copy on Sun's web site if you don't
already know where it is.

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

[Philippe Amarenco]

Joe Seigh <jsei...@xemaps.com> writes:

> look at the sparc programmers guide / architecture manual

> Good luck trying to find an online copy on Sun's web site if you don't

> already know where it is.

"google: sparc architecture manual pdf", 10 seconds :)

[Joe Seigh]

Philippe Amarenco wrote:
> Joe Seigh <jsei...@xemaps.com> writes:
>
>
>>look at the sparc programmers guide / architecture manual
>
>
>>Good luck trying to find an online copy on Sun's web site if you don't
>>already know where it is.
>
>
> "google: sparc architecture manual pdf", 10 seconds :)
>

My bad. I tried docs.sun.com. :)