yet another (tiny) implementation of condvars

21 views
Skip to first unread message

Michael Podolsky

unread,
Sep 30, 2010, 1:33:31 PM9/30/10
to
If you are not already bored with this recurring subject,
here is my very compact implementation of condvars based on
semaphores.

Of course, I am interested in feedbacks.

condvar constructor:
{
waiters : int(0)
task : int(0)
turn1 : semaphore(1) // one is open (original sem value = 1)
turn2 : semaphore(0) // another is closed
m: mutex
}

wait(mutex CS)
{
turn1.get();
m.lock();
++waiters;
m.unlock();
turn1.put();

CS.unlock();

turn2.get();
m.lock();
bool last = (--waiters == task);
m.unlock();
if(last)
turn1.put();
else
turn2.put();

CS.lock();
}

signal(bool all)
{
turn1.get();
m.lock();
if(waiters)
{
if(all)
task = 0;
else
task = waiters-1;
m.unlock();
turn2.put();
}
else
{
m.unlock();
turn1.put();
}
}

Thanks, Michael

Chris M. Thomasson

unread,
Sep 30, 2010, 11:26:27 PM9/30/10
to
"Michael Podolsky" <michael.p...@gmail.com> wrote in message
news:53a28afc-cc6f-4ef5...@x42g2000yqx.googlegroups.com...

> If you are not already bored with this recurring subject,
> here is my very compact implementation of condvars based on
> semaphores.
>
> Of course, I am interested in feedbacks.

I need to take a look at it Michael; I will probably implement it in Relacy
Race Detector when I get some time. FWIW, here is a simple and correct
condition variable in Windows, it's broadcast only, but that is definitely
allowed for in the POSIX standard:

<pseudo-code sketch>
___________________________________________________________
struct condvar
{
struct waitset
{
HANDLE m_event; // = manual reset event; set to false
LONG m_refs; // = 0
};


waitset* m_waitset; // = NULL
LONG m_refs; // = 0
CRITICAL_SECTION m_mutex;


bool timed_wait(LPCRITICAL_SECTION umutex, DWORD tout)
{
// grab a reference to the current waitset
EnterCriticalSection(&m_mutex);
waitset* w = m_waitset;
if (! w) w = m_waitset = new waitset();
++m_refs;
LeaveCriticalSection(&m_mutex);

// unlock user mutex and wait on the waitset we obtained
LeaveCriticalSection(umutex);
DWORD status = WaitForSingleObject(w->m_waitset, tout);

// decrement our waitsets refcount
if (! InterlockedDecrement(&w->m_refs))
{
delete w;
}

EnterCriticalSection(umutex);

// that's all folks! ;^)

return status == WAIT_OBJECT_0 ? true : false;
}


void wait(LPCRITICAL_SECTION umutex)
{
timed_wait(umutex, INFINITE);
}


void broadcast()
{
// swap a reference to the current waitset with NULL
EnterCriticalSection(&m_mutex);
waitset* w = m_waitset;
LONG refs = m_refs;
m_waitset = NULL;
m_refs = 0;
LeaveCriticalSection(&m_mutex);

if (w)
{
// signal all waiters
SetEvent(w->m_event);

// transfer the swapped reference count to the
// waitset reference count
if (InterlockedExchangeAdd(&w->m_refs, refs) == -refs)
{
delete w;
}
}
}


void signal()
{
broadcast();
}
};
_____________________________________________________________


Chris M. Thomasson

unread,
Sep 30, 2010, 11:26:27 PM9/30/10
to
"Michael Podolsky" <michael.p...@gmail.com> wrote in message
news:53a28afc-cc6f-4ef5...@x42g2000yqx.googlegroups.com...
> If you are not already bored with this recurring subject,
> here is my very compact implementation of condvars based on
> semaphores.
>
> Of course, I am interested in feedbacks.

I need to take a look at it Michael; I will probably implement it in Relacy

Chris M. Thomasson

unread,
Oct 3, 2010, 11:33:45 PM10/3/10
to
"Michael Podolsky" <michael.p...@gmail.com> wrote in message
news:53a28afc-cc6f-4ef5...@x42g2000yqx.googlegroups.com...
> If you are not already bored with this recurring subject,
> here is my very compact implementation of condvars based on
> semaphores.
>
> Of course, I am interested in feedbacks.
>
> condvar constructor:
[...]

> signal(bool all)
> {
> turn1.get();
> m.lock();
> if(waiters)
> {
> if(all)
> task = 0;
> else
> task = waiters-1;
> m.unlock();
> turn2.put();
> }
[...]

I must be missing something important here, but does the logic above
actually broadcast? I mean, you only seem to be incrementing the semaphore
one single time... How does that wake multiple waiters? I am confused here!

;^(...


Chris M. Thomasson

unread,
Oct 3, 2010, 11:37:36 PM10/3/10
to
"Chris M. Thomasson" <cri...@charter.net> wrote in message
news:eWbqo.1140$HW3...@newsfe11.iad...

> "Michael Podolsky" <michael.p...@gmail.com> wrote in message
> news:53a28afc-cc6f-4ef5...@x42g2000yqx.googlegroups.com...
>> If you are not already bored with this recurring subject,
>> here is my very compact implementation of condvars based on
>> semaphores.
>>
>> Of course, I am interested in feedbacks.
[...]
> I must be missing something important here, but does the logic above
> actually broadcast? I mean, you only seem to be incrementing the semaphore
> one single time... How does that wake multiple waiters? I am confused
> here!
>
> ;^(...

Ahh. It seems like you "continue" to increment the semaphore in the
following waiting logic:
___________________________________


turn2.get();
m.lock();
bool last = (--waiters == task);
m.unlock();
if(last)
turn1.put();
else
turn2.put();

___________________________________


Okay. I still need to impl this in Relacy, but I think I see what you are
getting at here Michael.


Michael Podolsky

unread,
Oct 4, 2010, 6:45:59 PM10/4/10
to
On Sep 30, 11:26 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:

>     void broadcast()
>     {
>         // swap a reference to the current waitset with NULL
>         EnterCriticalSection(&m_mutex);
>         waitset* w = m_waitset;
>         LONG refs = m_refs;
>         m_waitset = NULL;
>         m_refs = 0;
>         LeaveCriticalSection(&m_mutex);
>
>         if (w)
>         {
>             // signal all waiters
>             SetEvent(w->m_event);
>
>             // transfer the swapped reference count to the
>             // waitset reference count
>             if (InterlockedExchangeAdd(&w->m_refs, refs) == -refs)
>             {
>                 delete w;
>             }
>         }
>     }

BTW, as for your implementation, I could not figure out why you
collect the waiters number in condvar::m_refs and not directly in
waitset::m_refs. Then there comes a trick of transferring
condvar::m_refs to waitset::m_refs. Well, it should work, but I could
not understand why you needed to maintain two separate counters at all
and not worked directly on waitset::m_refs. Could you please clarify?

Thanks, Michael

Chris M. Thomasson

unread,
Oct 6, 2010, 4:33:51 PM10/6/10
to
> "Michael Podolsky" <michael.p...@gmail.com> wrote in message
> news:58035933-7006-479e...@d25g2000yqc.googlegroups.com...

> > On Sep 30, 11:26 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:

> > void broadcast()
> > {
[...]
> > }

> BTW, as for your implementation, I could not figure out why you
> collect the waiters number in condvar::m_refs and not directly in
> waitset::m_refs. Then there comes a trick of transferring
> condvar::m_refs to waitset::m_refs. Well, it should work, but I could
> not understand why you needed to maintain two separate counters at all
> and not worked directly on waitset::m_refs. Could you please clarify?

I did it to avoid locking the `condvar::m_mutex' after a waiter wakes.
Although, I think I might be able to use a single reference count and still
avoid locking the `condvar::m_mutex'. Humm... Perhaps something like:


<pseudo-code sketch>
___________________________________________________________
struct condvar
{
struct waitset
{
HANDLE m_event; // = manual reset event; set to false

LONG m_refs; // = 1
};


waitset* m_waitset; // = NULL

CRITICAL_SECTION m_mutex;


bool timed_wait(LPCRITICAL_SECTION umutex, DWORD tout)
{

// grab a reference to the current waitset


EnterCriticalSection(&m_mutex);
waitset* w = m_waitset;

if (! w) w = m_waitset = new waitset();

InterlockedIncrement(&w->m_refs);
LeaveCriticalSection(&m_mutex);

// unlock user mutex and wait on the waitset we obtained
LeaveCriticalSection(umutex);
DWORD status = WaitForSingleObject(w->m_waitset, tout);

// decrement our waitsets refcount
if (! InterlockedDecrement(&w->m_refs))
{
delete w;
}

EnterCriticalSection(umutex);

// that's all folks! ;^)

return status == WAIT_OBJECT_0 ? true : false;
}


void wait(LPCRITICAL_SECTION umutex)
{
timed_wait(umutex, INFINITE);
}

void broadcast()
{
// swap a reference to the current waitset with NULL
EnterCriticalSection(&m_mutex);
waitset* w = m_waitset;

m_waitset = NULL;
LeaveCriticalSection(&m_mutex);

if (w)
{
// signal all waiters
SetEvent(w->m_event);

// decrement our waitsets refcount


if (! InterlockedDecrement(&w->m_refs))
{
delete w;
}
}
}


void signal()
{
broadcast();
}
};
_____________________________________________________________


What do you think?


Chris M. Thomasson

unread,
Oct 6, 2010, 11:05:11 PM10/6/10
to
"Michael Podolsky" <michael.p...@gmail.com> wrote in message
news:53a28afc-cc6f-4ef5...@x42g2000yqx.googlegroups.com...

> If you are not already bored with this recurring subject,
> here is my very compact implementation of condvars based on
> semaphores.
>
> Of course, I am interested in feedbacks.
[...]

I went ahead and implemented your algorithm in Relacy Race Detector 2.3:

http://cpt.pastebin.com/uhcAg5Km

http://groups.google.com/group/relacy

It's working great.

:^)


Michael Podolsky

unread,
Oct 8, 2010, 3:10:44 PM10/8/10
to
On Oct 6, 4:33 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> > "Michael Podolsky" <michael.podolsky...@gmail.com> wrote in message

> > BTW, as for your implementation, I could not figure out why you
> > collect the waiters number in condvar::m_refs and not directly in
> > waitset::m_refs. Then there comes a trick of transferring
> > condvar::m_refs to waitset::m_refs. Well, it should work, but I could
> > not understand why you needed to maintain two separate counters at all
> > and not worked directly on waitset::m_refs. Could you please clarify?
>
> I did it to avoid locking the `condvar::m_mutex' after a waiter wakes.
> Although, I think I might be able to use a single reference count and still
> avoid locking the `condvar::m_mutex'. Humm... Perhaps something like:
>
> <pseudo-code sketch>
> What do you think?

Looks good for me. Apart from decrementing refcount and deleting a
waitset in broadcast.
I would just wipe out the following part of your code:

> void broadcast()
> {
...


>
> // decrement our waitsets refcount
> if (! InterlockedDecrement(&w->m_refs))
> {
> delete w;
> }

...
> }

Thanks, Michael

Michael Podolsky

unread,
Oct 8, 2010, 3:16:48 PM10/8/10
to
> "Michael Podolsky" <michael.podolsky...@gmail.com> wrote in message

Oh, it is just an 'academic' exercise, I do not mean to use it in a
real application. It has too many problems. I am working now on a,
hopefully, much better implementation (still with only a couple of
semaphores for it's still an 'academic' task for me).

BTW, what do you mean by "implemented it in Relacy"? You did not make
it a part of Relacy, did you? What then?

Thanks, Michael

Chris M. Thomasson

unread,
Oct 9, 2010, 8:32:53 PM10/9/10
to
"Michael Podolsky" <michael.p...@gmail.com> wrote in message
news:8dade1f9-f288-4722...@h7g2000yqn.googlegroups.com...

> On Oct 6, 4:33 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>> > "Michael Podolsky" <michael.podolsky...@gmail.com> wrote in message
>> > BTW, as for your implementation, I could not figure out why you
>> > collect the waiters number in condvar::m_refs and not directly in
>> > waitset::m_refs.
[...]

>> I did it to avoid locking the `condvar::m_mutex' after a waiter wakes.
>> Although, I think I might be able to use a single reference count and
>> still
>> avoid locking the `condvar::m_mutex'. Humm... Perhaps something like:
>>
>> <pseudo-code sketch>
>> What do you think?
>
> Looks good for me. Apart from decrementing refcount and deleting a
> waitset in broadcast.
> I would just wipe out the following part of your code:
>
>> void broadcast()
>> {
> ...
>>
>> // decrement our waitsets refcount
>> if (! InterlockedDecrement(&w->m_refs))
>> {
>> delete w;
>> }
> ...
>> }

What did you have in mind? I need to decrement the reference count here in
order to determine when a waitset can be safely destroyed/reused.


Chris M. Thomasson

unread,
Oct 11, 2010, 2:39:10 AM10/11/10
to
"Michael Podolsky" <michael.p...@gmail.com> wrote in message
news:e90172c7-7183-486d...@d17g2000yqm.googlegroups.com...
[...]

> BTW, what do you mean by "implemented it in Relacy"? You did not make
> it a part of Relacy, did you? What then?

I probably should have written:

I implemented your condvar algorithm using the API's provided by Relacy.


Sorry for any confusion!

;^(


Michael Podolsky

unread,
Oct 18, 2010, 1:21:03 PM10/18/10
to

I meant in your last version of the code, you should decrement and
delete inside 'timed_wait' function only.
Otherwise you have N+1 InterlockedDecrements (N inside 'timed_wait and
one inside 'broadcast')
and may delete your waitset too soon, then access it again with last
decrement which leads to GPF or memory corruption.
Ain't I right?

Regards, Michael
(Late answer, sorry)

Chris M. Thomasson

unread,
Oct 18, 2010, 7:01:40 PM10/18/10
to
"Michael Podolsky" <michael.p...@gmail.com> wrote in message
news:5e809343-83ee-4d12...@e14g2000yqe.googlegroups.com...

On Oct 9, 8:32 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
[...]

> > What did you have in mind? I need to decrement the reference count here
> > in
> > order to determine when a waitset can be safely destroyed/reused.

> I meant in your last version of the code, you should decrement and
> delete inside 'timed_wait' function only.
> Otherwise you have N+1 InterlockedDecrements (N inside 'timed_wait and
> one inside 'broadcast')

Take note of the following snippet:
_____________________________________________________


struct waitset
{
HANDLE m_event; // = manual reset event; set to false
LONG m_refs; // = 1
};


waitset* m_waitset; // = NULL
CRITICAL_SECTION m_mutex;


bool timed_wait(LPCRITICAL_SECTION umutex, DWORD tout)
{
// grab a reference to the current waitset
EnterCriticalSection(&m_mutex);
waitset* w = m_waitset;
if (! w) w = m_waitset = new waitset();
InterlockedIncrement(&w->m_refs);
LeaveCriticalSection(&m_mutex);

[...]
}
_____________________________________________________


Okay, a new waitset has always has a reference count of 1. When a waiter
_creates_ a new waitset, or references a current waitset, it always does an
atomic increment _within_ the critical section. Therefore if there are N
waiters, the reference count will always be 1 greater than N before a
broadcast occurs. Therefore, I think that the scenario you describe cannot
happen.

Let's say there are 3 waiters; the refcount will be 4. Now, 1 waiter times
out, thus rendering the refcount to 3. A broadcast occurs, thus rendering
the refcount to 2. Finally the last two waiters wake and perform decrements,
thus rendering the refcount to zero. This seems safe to me...

> and may delete your waitset too soon, then access it again with last
> decrement which leads to GPF or memory corruption.
> Ain't I right?

I am having trouble coming up with a scenario in which a waitset can be
destroyed too soon...


Michael Podolsky

unread,
Oct 19, 2010, 10:19:36 AM10/19/10
to
Oh, sorry, I did not notice you create your waiter object with
starting ref count = 1.
i thought it was zero.

You are right.

Thanks, Michael

Reply all
Reply to author
Forward
0 new messages