Portable eventcount (try 2)

I take into account feedback from Anthony Williams and Chris Thomasson
after my first try:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/9461b41709e4063a

Here is claimed properties:
1. No memory allocation/deallocation
2. No kernel object creation/destruction
3. Broadcasting with single syscall
4. No mutex acquisition after wait on semaphore
5. Portable because based on semaphore
6. No spurious wakeups by design
7. You can easily transform this algorithm into condition variable

Brief comments on algorithm:
1. Every thread has associated node which it uses in eventcount
operations
2. Threads exchange of their nodes
3. Mutex acquisition, which must be after wait on semaphore, executed
before next wait (it's just deferred).

Here is the code:

struct thread_node
{
thread_node* next;
size_t count;
size_t unconsumed;
HANDLE sema;
CRITICAL_SECTION mtx;
};

__declspec(thread) thread_node* t_thread_node;

void on_thread_exit()
{
thread_node* head = t_thread_node;
thread_node* my = 0;
if (head)
{
EnterCriticalSection(&head->mtx);
if (head->next)
{
my = head->next;
head->next = my->next;
}
else
{
my = head;
}
LeaveCriticalSection(&head->mtx);
DeleteCriticalSection(&my->mtx);
CloseHandle(my->sema);
delete my;
}
}

struct eventcount
{
eventcount()
{
root = 0;
InitializeCriticalSection(&mtx);
}

~eventcount()
{
DeleteCriticalSection(&mtx);
}

void prepare_wait()
{
thread_node* my = 0;
thread_node* head = t_thread_node;
if (head)
{
EnterCriticalSection(&head->mtx);
if (head->next)
{
my = head->next;
head->next = my->next;
my->next = 0;
}
else
{
my = head;
}
LeaveCriticalSection(&head->mtx);
}
else
{
my = new thread_node;
my->next = 0;
my->count = 0;
my->unconsumed = 0;
my->sema = CreateSemaphoreW(0, 0, LONG_MAX, 0);
InitializeCriticalSection(&my->mtx);
}

while (my->unconsumed)
{
WaitForSingleObject(my->sema, 0);
my->unconsumed -= 1;
}

EnterCriticalSection(&mtx);
if (root)
{
my->next = root->next;
root->next = my;
my = root;
}
else
{
root = my;
}
root->count += 1;
LeaveCriticalSection(&mtx);
t_thread_node = my;
}

void wait()
{
thread_node* head = t_thread_node;
if (head == root)
{
WaitForSingleObject(head->sema, INFINITE);
}
else
{
EnterCriticalSection(&head->mtx);
head->unconsumed += 1;
LeaveCriticalSection(&head->mtx);
}
}

void retire_wait()
{
thread_node* head = t_thread_node;
if (head == root)
{
EnterCriticalSection(&mtx);
if (head == root)
{
thread_node* my = 0;
head->count -= 1;
if (head->next)
{
my = head->next;
head->next = my->next;
my->next = 0;
}
else
{
my = head;
}
LeaveCriticalSection(&mtx);
t_thread_node = my;
return;
}
LeaveCriticalSection(&mtx);
}
EnterCriticalSection(&head->mtx);
head->unconsumed += 1;
LeaveCriticalSection(&head->mtx);
}

void signal_all()
{
_mm_mfence();
thread_node* head = root;
if (0 == head)
return;
EnterCriticalSection(&mtx);
if (head != root)
{
LeaveCriticalSection(&mtx);
return;
}
root = 0;
LeaveCriticalSection(&mtx);
size_t count = head->count;
head->count = 0;
ReleaseSemaphore(head->sema, count, 0);
}

void signal_one()
{
_mm_mfence();
thread_node* head = root;
if (0 == head)
return;
EnterCriticalSection(&mtx);
if (head != root)
{
LeaveCriticalSection(&mtx);
return;
}
head->count -= 1;
if (0 == head->count)
root = 0;
LeaveCriticalSection(&mtx);
ReleaseSemaphore(head->sema, 1, 0);
}

thread_node* volatile root;
CRITICAL_SECTION mtx;
};


Dmitriy V'jukov
--
Relacy Race Detector: Make your synchronization correct!
http://groups.google.ru/group/relacy/web
.

Relevant Pages

  • Re: Portable eventcount (try 2)
    ... I guess you can put a pointer to the eventcount in the ... void on_thread_exit; ... if (root) ... if (head == root) ...
    (comp.programming.threads)
  • Re: Portable eventcount (try 2)
    ... I guess you can put a pointer to the eventcount in the `thread_node' ... void on_thread_exit; ... if (root) ... if (head == root) ...
    (comp.programming.threads)
  • Re: Portable eventcount (try 2)
    ... When thread pops node from stack, ... checks whether stack's head is still equal to eventcount's root. ... void on_thread_exit ...
    (comp.programming.threads)
  • Re: Benson DVD is entirely weird
    ... extra step of actually "hearing" the root even on rootless chords. ... I cannot transcribe it in my head. ... That's a great musical skill to have but not a pre-requisite to playing ...
    (rec.music.makers.guitar.jazz)
  • Re: Prevent root to remove files/directories
    ... head" concerning _real_ solutions, I would only add that the only ... use suto issue root commands as needed. ... but because I let a "friend" of a friend once utilize my ... Shoot root in the head. ...
    (comp.unix.shell)