updated pseudo-code for my eventcount algorithm...

14 views
Skip to first unread message

Chris Thomasson

unread,
Oct 29, 2006, 6:34:34 PM10/29/06
to
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

unread,
Oct 29, 2006, 9:41:30 PM10/29/06
to
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

unread,
Oct 30, 2006, 5:00:08 AM10/30/06
to
[...]


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

unread,
Oct 30, 2006, 5:04:09 AM10/30/06
to
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

unread,
Oct 31, 2006, 6:24:46 PM10/31/06
to
"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

unread,
Nov 1, 2006, 9:14:49 AM11/1/06
to
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

unread,
Nov 1, 2006, 9:50:53 AM11/1/06
to
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

unread,
Nov 1, 2006, 10:53:25 AM11/1/06
to
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. :)
Reply all
Reply to author
Forward
0 new messages