diff options
| -rw-r--r-- | ANNOUNCE | 6 | ||||
| -rw-r--r-- | CONTRIBUTORS | 6 | ||||
| -rw-r--r-- | ChangeLog | 30 | ||||
| -rw-r--r-- | README.CV | 1732 | ||||
| -rw-r--r-- | condvar.c | 436 | ||||
| -rw-r--r-- | implement.h | 49 | ||||
| -rw-r--r-- | misc.c | 29 | ||||
| -rw-r--r-- | mutex.c | 565 | ||||
| -rw-r--r-- | nonportable.c | 26 | ||||
| -rw-r--r-- | pthread.def | 13 | ||||
| -rw-r--r-- | pthread.h | 205 | ||||
| -rw-r--r-- | rwlock.c | 8 | ||||
| -rw-r--r-- | sched.c | 67 | ||||
| -rw-r--r-- | tsd.c | 8 |
14 files changed, 2613 insertions, 567 deletions
@@ -219,6 +219,10 @@ The following functions are implemented: pthread_attr_setschedparam
pthread_getschedparam
pthread_setschedparam
+ pthread_getconcurrency
+ pthread_getconcurrency
+ pthread_attr_getscope
+ pthread_attr_setscope
sched_get_priority_max (POSIX 1b)
sched_get_priority_min (POSIX 1b)
sched_yield (POSIX 1b)
@@ -265,10 +269,8 @@ The following functions are not implemented: ---------------------------
pthread_attr_getinheritsched
pthread_attr_getschedpolicy
- pthread_attr_getscope
pthread_attr_setinheritsched
pthread_attr_setschedpolicy
- pthread_attr_setscope
pthread_mutex_getprioceiling
pthread_mutex_setprioceiling
pthread_mutex_attr_getprioceiling
diff --git a/CONTRIBUTORS b/CONTRIBUTORS index aa4dd3e..ce30926 100644 --- a/CONTRIBUTORS +++ b/CONTRIBUTORS @@ -1,5 +1,8 @@ Contributors (in approximate order of appearance)
+[See also the ChangeLog file where individuals are
+attributed in log entries. Likewise in the FAQ file.]
+
Ben Elliston bje@cygnus.com
Ross Johnson rpj@ise.canberra.edu.au
Robert Colquhoun rjc@trump.net.au
@@ -26,4 +29,5 @@ David Baggett dmb.itasoftware.com Paul Redondo paul.matchvision.com
Scott McCaskill scott.3dfx.om
Thomas Pfaff tpfaff@gmx.net
-Franco Bez ???
+Franco Bez franco.bez@gmx.de
+Alexander Terekhov TEREKHOV@de.ibm.com
@@ -1,3 +1,33 @@ +2001-02-06 Ross Johnson <rpj@setup1.ise.canberra.edu.au> + + * condvar.c (pthread_cond_init): Completely revamped. + (pthread_cond_destroy): Likewise. + (ptw32_cond_wait_cleanup): Likewise. + (ptw32_cond_timedwait): Likewise. + (ptw32_cond_unblock): New general signaling routine. + (pthread_cond_signal): Now calls ptw32_cond_unblock. + (pthread_cond_broadcast): Likewise. + implement.h (pthread_cond_t_): Revamped. + README.CV: New; explanation of the above changes. + - Alexander Terekhov <TEREKHOV@de.ibm.com> + +2001-02-05 Ross Johnson <rpj@setup1.ise.canberra.edu.au> + + * sched.c (pthread_getconcurrency): New no-op function. + * sched.c (pthread_setconcurrency): New no-op function. + * sched.c (pthread_attr_getscope): New no-op function. + * sched.c (pthread_attr_setscope): New no-op function. + * sched.c (ENOSUP): Removed define and changed references + to use ENOTSUP. + * pthread.h (PTHREAD_SCOPE_SYSTEM): Defined. + * pthread.h (PTHREAD_SCOPE_PROCESS): Defined. + * pthread.h (ENOTSUP): Defined - not defined by Win32. + +2001-01-10 Ross Johnson <rpj@setup1.ise.canberra.edu.au> + + * rwlock.c (ptw32_rwlock_cancelwrwait): Renamed. + (ptw32_rwlock_cancelrdwait): Renamed. + 2000-12-29 Ross Johnson <rpj@special.ise.canberra.edu.au> * Makefile: Back-out "for" loops which don't work. diff --git a/README.CV b/README.CV new file mode 100644 index 0000000..1ce222a --- /dev/null +++ b/README.CV @@ -0,0 +1,1732 @@ +README.CV -- Condition Variables +-------------------------------- + +The original implementation of condition variables in +pthreads-win32 was based on a discussion paper: + +"Strategies for Implementing POSIX Condition Variables +on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html + +The changes suggested below were made on Feb 6 2001. This +file is included in the package for the benefit of anyone +interested in understanding the pthreads-win32 implementation +of condition variables and the (sometimes subtle) issues that +it attempts to resolve. + +Thanks go to the individuals whose names appear throughout +the following text. + +Ross Johnson + +-------------------------------------------------------------------- + +fyi.. (more detailed problem description/demos + possible fix/patch) + +regards, +alexander. + + +Alexander Terekhov +31.01.2001 17:43 + +To: ace-bugs@cs.wustl.edu +cc: +From: Alexander Terekhov/Germany/IBM@IBMDE +Subject: Implementation of POSIX CVs: spur.wakeups/lost + signals/deadlocks/unfairness + + + + ACE VERSION: + + 5.1.12 (pthread-win32 snapshot 2000-12-29) + + HOST MACHINE and OPERATING SYSTEM: + + IBM IntelliStation Z Pro, 2 x XEON 1GHz, Win2K + + TARGET MACHINE and OPERATING SYSTEM, if different from HOST: + COMPILER NAME AND VERSION (AND PATCHLEVEL): + + Microsoft Visual C++ 6.0 + + AREA/CLASS/EXAMPLE AFFECTED: + + Implementation of POSIX condition variables - OS.cpp/.h + + DOES THE PROBLEM AFFECT: + + EXECUTION? YES! + + SYNOPSIS: + + a) spurious wakeups (minor problem) + b) lost signals + c) broadcast deadlock + d) unfairness (minor problem) + + DESCRIPTION: + + Please see attached copy of discussion thread + from comp.programming.threads for more details on + some reported problems. (i've also posted a "fyi" + message to ace-users a week or two ago but + unfortunately did not get any response so far). + + It seems that current implementation suffers from + two essential problems: + + 1) cond.waiters_count does not accurately reflect + number of waiters blocked on semaphore - w/o + proper synchronisation that could result (in the + time window when counter is not accurate) + in spurious wakeups organised by subsequent + _signals and _broadcasts. + + 2) Always having (with no e.g. copy_and_clear/..) + the same queue in use (semaphore+counter) + neither signal nor broadcast provide 'atomic' + behaviour with respect to other threads/subsequent + calls to signal/broadcast/wait. + + Each problem and combination of both could produce + various nasty things: + + a) spurious wakeups (minor problem) + + it is possible that waiter(s) which was already + unblocked even so is still counted as blocked + waiter. signal and broadcast will release + semaphore which will produce a spurious wakeup + for a 'real' waiter coming later. + + b) lost signals + + signalling thread ends up consuming its own + signal. please see demo/discussion below. + + c) broadcast deadlock + + last_waiter processing code does not correctly + handle the case with multiple threads + waiting for the end of broadcast. + please see demo/discussion below. + + d) unfairness (minor problem) + + without SignalObjectAndWait some waiter(s) + may end up consuming broadcasted signals + multiple times (spurious wakeups) because waiter + thread(s) can be preempted before they call + semaphore wait (but after count++ and mtx.unlock). + + REPEAT BY: + + See below... run problem demos programs (tennis.cpp and + tennisb.cpp) number of times concurrently (on multiprocessor) + and in multiple sessions or just add a couple of "Sleep"s + as described in the attached copy of discussion thread + from comp.programming.threads + + SAMPLE FIX/WORKAROUND: + + See attached patch to pthread-win32.. well, I can not + claim that it is completely bug free but at least my + test and tests provided by pthreads-win32 seem to work. + Perhaps that will help. + + regards, + alexander. + + +>> Forum: comp.programming.threads +>> Thread: pthread_cond_* implementation questions +. +. +. +David Schwartz <davids@webmaster.com> wrote: + +> terekhov@my-deja.com wrote: +> +>> BTW, could you please also share your view on other perceived +>> "problems" such as nested broadcast deadlock, spurious wakeups +>> and (the latest one) lost signals?? +> +>I'm not sure what you mean. The standard allows an implementation +>to do almost whatever it likes. In fact, you could implement +>pthread_cond_wait by releasing the mutex, sleeping a random +>amount of time, and then reacquiring the mutex. Of course, +>this would be a pretty poor implementation, but any code that +>didn't work under that implementation wouldn't be strictly +>compliant. + +The implementation you suggested is indeed correct +one (yes, now I see it :). However it requires from +signal/broadcast nothing more than to "{ return 0; }" +That is not the case for pthread-win32 and ACE +implementations. I do think that these implementations +(basically the same implementation) have some serious +problems with wait/signal/broadcast calls. I am looking +for help to clarify whether these problems are real +or not. I think that I can demonstrate what I mean +using one or two small sample programs. +. +. +. +========== +tennis.cpp +========== + +#include "ace/Synch.h" +#include "ace/Thread.h" + +enum GAME_STATE { + + START_GAME, + PLAYER_A, // Player A playes the ball + PLAYER_B, // Player B playes the ball + GAME_OVER, + ONE_PLAYER_GONE, + BOTH_PLAYERS_GONE + +}; + +enum GAME_STATE eGameState; +ACE_Mutex* pmtxGameStateLock; +ACE_Condition< ACE_Mutex >* pcndGameStateChange; + +void* + playerA( + void* pParm + ) +{ + + // For access to game state variable + pmtxGameStateLock->acquire(); + + // Play loop + while ( eGameState < GAME_OVER ) { + + // Play the ball + cout << endl << "PLAYER-A" << endl; + + // Now its PLAYER-B's turn + eGameState = PLAYER_B; + + // Signal to PLAYER-B that now it is his turn + pcndGameStateChange->signal(); + + // Wait until PLAYER-B finishes playing the ball + do { + + pcndGameStateChange->wait(); + + if ( PLAYER_B == eGameState ) + cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl; + + } while ( PLAYER_B == eGameState ); + + } + + // PLAYER-A gone + eGameState = (GAME_STATE)(eGameState+1); + cout << endl << "PLAYER-A GONE" << endl; + + // No more access to state variable needed + pmtxGameStateLock->release(); + + // Signal PLAYER-A gone event + pcndGameStateChange->broadcast(); + + return 0; + +} + +void* + playerB( + void* pParm + ) +{ + + // For access to game state variable + pmtxGameStateLock->acquire(); + + // Play loop + while ( eGameState < GAME_OVER ) { + + // Play the ball + cout << endl << "PLAYER-B" << endl; + + // Now its PLAYER-A's turn + eGameState = PLAYER_A; + + // Signal to PLAYER-A that now it is his turn + pcndGameStateChange->signal(); + + // Wait until PLAYER-A finishes playing the ball + do { + + pcndGameStateChange->wait(); + + if ( PLAYER_A == eGameState ) + cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl; + + } while ( PLAYER_A == eGameState ); + + } + + // PLAYER-B gone + eGameState = (GAME_STATE)(eGameState+1); + cout << endl << "PLAYER-B GONE" << endl; + + // No more access to state variable needed + pmtxGameStateLock->release(); + + // Signal PLAYER-B gone event + pcndGameStateChange->broadcast(); + + return 0; + +} + + +int +main (int, ACE_TCHAR *[]) +{ + + pmtxGameStateLock = new ACE_Mutex(); + pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock +); + + // Set initial state + eGameState = START_GAME; + + // Create players + ACE_Thread::spawn( playerA ); + ACE_Thread::spawn( playerB ); + + // Give them 5 sec. to play + Sleep( 5000 );//sleep( 5 ); + + // Set game over state + pmtxGameStateLock->acquire(); + eGameState = GAME_OVER; + + // Let them know + pcndGameStateChange->broadcast(); + + // Wait for players to stop + do { + + pcndGameStateChange->wait(); + + } while ( eGameState < BOTH_PLAYERS_GONE ); + + // Cleanup + cout << endl << "GAME OVER" << endl; + pmtxGameStateLock->release(); + delete pcndGameStateChange; + delete pmtxGameStateLock; + + return 0; + +} + +=========== +tennisb.cpp +=========== +#include "ace/Synch.h" +#include "ace/Thread.h" + +enum GAME_STATE { + + START_GAME, + PLAYER_A, // Player A playes the ball + PLAYER_B, // Player B playes the ball + GAME_OVER, + ONE_PLAYER_GONE, + BOTH_PLAYERS_GONE + +}; + +enum GAME_STATE eGameState; +ACE_Mutex* pmtxGameStateLock; +ACE_Condition< ACE_Mutex >* pcndGameStateChange; + +void* + playerA( + void* pParm + ) +{ + + // For access to game state variable + pmtxGameStateLock->acquire(); + + // Play loop + while ( eGameState < GAME_OVER ) { + + // Play the ball + cout << endl << "PLAYER-A" << endl; + + // Now its PLAYER-B's turn + eGameState = PLAYER_B; + + // Signal to PLAYER-B that now it is his turn + pcndGameStateChange->broadcast(); + + // Wait until PLAYER-B finishes playing the ball + do { + + pcndGameStateChange->wait(); + + if ( PLAYER_B == eGameState ) + cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl; + + } while ( PLAYER_B == eGameState ); + + } + + // PLAYER-A gone + eGameState = (GAME_STATE)(eGameState+1); + cout << endl << "PLAYER-A GONE" << endl; + + // No more access to state variable needed + pmtxGameStateLock->release(); + + // Signal PLAYER-A gone event + pcndGameStateChange->broadcast(); + + return 0; + +} + +void* + playerB( + void* pParm + ) +{ + + // For access to game state variable + pmtxGameStateLock->acquire(); + + // Play loop + while ( eGameState < GAME_OVER ) { + + // Play the ball + cout << endl << "PLAYER-B" << endl; + + // Now its PLAYER-A's turn + eGameState = PLAYER_A; + + // Signal to PLAYER-A that now it is his turn + pcndGameStateChange->broadcast(); + + // Wait until PLAYER-A finishes playing the ball + do { + + pcndGameStateChange->wait(); + + if ( PLAYER_A == eGameState ) + cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl; + + } while ( PLAYER_A == eGameState ); + + } + + // PLAYER-B gone + eGameState = (GAME_STATE)(eGameState+1); + cout << endl << "PLAYER-B GONE" << endl; + + // No more access to state variable needed + pmtxGameStateLock->release(); + + // Signal PLAYER-B gone event + pcndGameStateChange->broadcast(); + + return 0; + +} + + +int +main (int, ACE_TCHAR *[]) +{ + + pmtxGameStateLock = new ACE_Mutex(); + pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock +); + + // Set initial state + eGameState = START_GAME; + + // Create players + ACE_Thread::spawn( playerA ); + ACE_Thread::spawn( playerB ); + + // Give them 5 sec. to play + Sleep( 5000 );//sleep( 5 ); + + // Make some noise + pmtxGameStateLock->acquire(); + cout << endl << "---Noise ON..." << endl; + pmtxGameStateLock->release(); + for ( int i = 0; i < 100000; i++ ) + pcndGameStateChange->broadcast(); + cout << endl << "---Noise OFF" << endl; + + // Set game over state + pmtxGameStateLock->acquire(); + eGameState = GAME_OVER; + cout << endl << "---Stopping the game..." << endl; + + // Let them know + pcndGameStateChange->broadcast(); + + // Wait for players to stop + do { + + pcndGameStateChange->wait(); + + } while ( eGameState < BOTH_PLAYERS_GONE ); + + // Cleanup + cout << endl << "GAME OVER" << endl; + pmtxGameStateLock->release(); + delete pcndGameStateChange; + delete pmtxGameStateLock; + + return 0; + +} +. +. +. +David Schwartz <davids@webmaster.com> wrote: +>> > It's compliant +>> +>> That is really good. +> +>> Tomorrow (I have to go urgently now) I will try to +>> demonstrate the lost-signal "problem" of current +>> pthread-win32 and ACE-(variant w/o SingleObjectAndWait) +>> implementations: players start suddenly drop their balls :-) +>> (with no change in source code). +> +>Signals aren't lost, they're going to the main thread, +>which isn't coded correctly to handle them. Try this: +> +> // Wait for players to stop +> do { +> +> pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock ); +>printf("Main thread stole a signal\n"); +> +> } while ( eGameState < BOTH_PLAYERS_GONE ); +> +>I bet everytime you thing a signal is lost, you'll see that printf. +>The signal isn't lost, it was stolen by another thread. + +well, you can probably loose your bet.. it was indeed stolen +by "another" thread but not the one you seem to think of. + +I think that what actually happens is the following: + +H:\SA\UXX\pt\PTHREADS\TESTS>tennis3.exe + +PLAYER-A + +PLAYER-B + +----PLAYER-B: SPURIOUS WAKEUP!!! + +PLAYER-A GONE + +PLAYER-B GONE + +GAME OVER + +H:\SA\UXX\pt\PTHREADS\TESTS> + +here you can see that PLAYER-B after playing his first +ball (which came via signal from PLAYER-A) just dropped +it down. What happened is that his signal to player A +was consumed as spurious wakeup by himself (player B). + +The implementation has a problem: + +================ +waiting threads: +================ + +{ /** Critical Section + + inc cond.waiters_count + +} + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.mtx.release + + /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX, + /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE + /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL! + + cond.sem.wait + +Player-A after playing game's initial ball went into +wait (called _wait) but was pre-empted before reaching +wait semaphore. He was counted as waiter but was not +actually waiting/blocked yet. + +=============== +signal threads: +=============== + +{ /** Critical Section + + waiters_count = cond.waiters_count + +} + + if ( waiters_count != 0 ) + + sem.post 1 + + endif + +Player-B after he received signal/ball from Player A +called _signal. The _signal did see that there was +one waiter blocked on the condition (Player-A) and +released the semaphore.. (but it did not unblock +Player-A because he was not actually blocked). +Player-B thread continued its execution, called _wait, +was counted as second waiter BUT was allowed to slip +through opened semaphore gate (which was opened for +Player-B) and received his own signal. Player B remained +blocked followed by Player A. Deadlock happened which +lasted until main thread came in and said game over. + +It seems to me that the implementation fails to +correctly implement the following statement +from specification: + +http://www.opengroup.org/ +onlinepubs/007908799/xsh/pthread_cond_wait.html + +"These functions atomically release mutex and cause +the calling thread to block on the condition variable +cond; atomically here means "atomically with respect +to access by another thread to the mutex and then the +condition variable". That is, if another thread is +able to acquire the mutex after the about-to-block +thread has released it, then a subsequent call to +pthread_cond_signal() or pthread_cond_broadcast() +in that thread behaves as if it were issued after +the about-to-block thread has blocked." + +Question: Am I right? + +(I produced the program output above by simply +adding ?Sleep( 1 )?: + +================ +waiting threads: +================ + +{ /** Critical Section + + inc cond.waiters_count + +} + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.mtx.release + +Sleep( 1 ); // Win32 + + /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX, + /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE + /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL! + + cond.sem.wait + +to the source code of pthread-win32 implementation: + +http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/ +condvar.c?rev=1.36&content-type=text/ +x-cvsweb-markup&cvsroot=pthreads-win32 + + + /* + * We keep the lock held just long enough to increment the count of + * waiters by one (above). + * Note that we can't keep it held across the + * call to sem_wait since that will deadlock other calls + * to pthread_cond_signal + */ + cleanup_args.mutexPtr = mutex; + cleanup_args.cv = cv; + cleanup_args.resultPtr = &result; + + pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) +&cleanup_args); + + if ((result = pthread_mutex_unlock (mutex)) == 0) + {((result +Sleep( 1 ); // @AT + + /* + * Wait to be awakened by + * pthread_cond_signal, or + * pthread_cond_broadcast, or + * a timeout + * + * Note: + * ptw32_sem_timedwait is a cancelation point, + * hence providing the + * mechanism for making pthread_cond_wait a cancelation + * point. We use the cleanup mechanism to ensure we + * re-lock the mutex and decrement the waiters count + * if we are canceled. + */ + if (ptw32_sem_timedwait (&(cv->sema), abstime) == -1) { + result = errno; + } + } + + pthread_cleanup_pop (1); /* Always cleanup */ + + +BTW, on my system (2 CPUs) I can manage to get +signals lost even without any source code modification +if I run the tennis program many times in different +shell sessions. +. +. +. +David Schwartz <davids@webmaster.com> wrote: +>terekhov@my-deja.com wrote: +> +>> well, it might be that the program is in fact buggy. +>> but you did not show me any bug. +> +>You're right. I was close but not dead on. I was correct, however, +>that the code is buggy because it uses 'pthread_cond_signal' even +>though not any thread waiting on the condition variable can do the +>job. I was wrong in which thread could be waiting on the cv but +>unable to do the job. + +Okay, lets change 'pthread_cond_signal' to 'pthread_cond_broadcast' +but also add some noise from main() right before declaring the game +to be over (I need it in order to demonstrate another problem of +pthread-win32/ACE implementations - broadcast deadlock)... +. +. +. +It is my understanding of POSIX conditions, +that on correct implementation added noise +in form of unnecessary broadcasts from main, +should not break the tennis program. The +only 'side effect' of added noise on correct +implementation would be 'spurious wakeups' of +players (in fact they are not spurious, +players just see them as spurious) unblocked, +not by another player but by main before +another player had a chance to acquire the +mutex and change the game state variable: +. +. +. + +PLAYER-B + +PLAYER-A + +---Noise ON... + +PLAYER-B + +PLAYER-A + +. +. +. + +PLAYER-B + +PLAYER-A + +----PLAYER-A: SPURIOUS WAKEUP!!! + +PLAYER-B + +PLAYER-A + +---Noise OFF + +PLAYER-B + +---Stopping the game... + +PLAYER-A GONE + +PLAYER-B GONE + +GAME OVER + +H:\SA\UXX\pt\PTHREADS\TESTS> + +On pthread-win32/ACE implementations the +program could stall: + +. +. +. + +PLAYER-A + +PLAYER-B + +PLAYER-A + +PLAYER-B + +PLAYER-A + +PLAYER-B + +PLAYER-A + +PLAYER-B + +---Noise ON... + +PLAYER-A + +---Noise OFF +^C +H:\SA\UXX\pt\PTHREADS\TESTS> + + +The implementation has problems: + +================ +waiting threads: +================ + +{ /** Critical Section + + inc cond.waiters_count + +} + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.mtx.release + cond.sem.wait + + /*** ^^-- WAITER CAN BE PREEMPTED AFTER BEING UNBLOCKED... + +{ /** Critical Section + + dec cond.waiters_count + + /*** ^^- ...AND BEFORE DECREMENTING THE COUNT (1) + + last_waiter = ( cond.was_broadcast && + cond.waiters_count == 0 ) + + if ( last_waiter ) + + cond.was_broadcast = FALSE + + endif + +} + + if ( last_waiter ) + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.auto_reset_event_or_sem.post /* Event for Win32 + cond.mtx.acquire + + /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (2) + + /*** ^^-- NESTED BROADCASTS RESULT IN A DEADLOCK + + + else + + cond.mtx.acquire + + /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (3) + + endif + + +================== +broadcast threads: +================== + +{ /** Critical Section + + waiters_count = cond.waiters_count + + if ( waiters_count != 0 ) + + cond.was_broadcast = TRUE + + endif + +} + +if ( waiters_count != 0 ) + + cond.sem.post waiters_count + + /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1) + + cond.auto_reset_event_or_sem.wait /* Event for Win32 + + /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY + HAPPEN TO GO INTO WAIT WHILE PREVIOUS + BROADCAST IS STILL IN PROGRESS/WAITING + +endif + +a) cond.waiters_count does not accurately reflect +number of waiters blocked on semaphore - that could +result (in the time window when counter is not accurate) +in spurios wakeups organised by subsequent _signals +and _broadcasts. From standard compliance point of view +that is OK but that could be a real problem from +performance/efficiency point of view. + +b) If subsequent broadcast happen to go into wait on +cond.auto_reset_event_or_sem before previous +broadcast was unblocked from cond.auto_reset_event_or_sem +by its last waiter, one of two blocked threads will +remain blocked because last_waiter processing code +fails to unblock both threads. + +In the situation with tennisb.c the Player-B was put +in a deadlock by noise (broadcast) coming from main +thread. And since Player-B holds the game state +mutex when it calls broadcast, the whole program +stalled: Player-A was deadlocked on mutex and +main thread after finishing with producing the noise +was deadlocked on mutex too (needed to declare the +game over) + +(I produced the program output above by simply +adding ?Sleep( 1 )?: + +================== +broadcast threads: +================== + +{ /** Critical Section + + waiters_count = cond.waiters_count + + if ( waiters_count != 0 ) + + cond.was_broadcast = TRUE + + endif + +} + +if ( waiters_count != 0 ) + +Sleep( 1 ); //Win32 + + cond.sem.post waiters_count + + /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1) + + cond.auto_reset_event_or_sem.wait /* Event for Win32 + + /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY + HAPPEN TO GO INTO WAIT WHILE PREVIOUS + BROADCAST IS STILL IN PROGRESS/WAITING + +endif + +to the source code of pthread-win32 implementation: + +http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/ +condvar.c?rev=1.36&content-type=text/ +x-cvsweb-markup&cvsroot=pthreads-win32 + + if (wereWaiters) + {(wereWaiters)sroot=pthreads-win32eb.cgi/pthreads/Yem...m + /* + * Wake up all waiters + */ + +Sleep( 1 ); //@AT + +#ifdef NEED_SEM + + result = (ptw32_increase_semaphore( &cv->sema, cv->waiters ) + ? 0 + : EINVAL); + +#else /* NEED_SEM */ + + result = (ReleaseSemaphore( cv->sema, cv->waiters, NULL ) + ? 0 + : EINVAL); + +#endif /* NEED_SEM */ + + } + + (void) pthread_mutex_unlock(&(cv->waitersLock)); + + if (wereWaiters && result == 0) + {(wereWaiters + /* + * Wait for all the awakened threads to acquire their part of + * the counting semaphore + */ + + if (WaitForSingleObject (cv->waitersDone, INFINITE) + == WAIT_OBJECT_0) + { + result = 0; + } + else + { + result = EINVAL; + } + + } + + return (result); + +} + +BTW, on my system (2 CPUs) I can manage to get +the program stalled even without any source code +modification if I run the tennisb program many +times in different shell sessions. + +=================== +pthread-win32 patch +=================== +struct pthread_cond_t_ { + long nWaitersBlocked; /* Number of threads blocked +*/ + long nWaitersUnblocked; /* Number of threads unblocked +*/ + long nWaitersToUnblock; /* Number of threads to unblock +*/ + sem_t semBlockQueue; /* Queue up threads waiting for the +*/ + /* condition to become signalled +*/ + sem_t semBlockLock; /* Semaphore that guards access to +*/ + /* | waiters blocked count/block queue +*/ + /* +-> Mandatory Sync.LEVEL-1 +*/ + pthread_mutex_t mtxUnblockLock; /* Mutex that guards access to +*/ + /* | waiters (to)unblock(ed) counts +*/ + /* +-> Optional* Sync.LEVEL-2 +*/ +}; /* Opt*) for _timedwait and +cancellation*/ + +int +pthread_cond_init (pthread_cond_t * cond, const pthread_condattr_t * attr) + int result = EAGAIN; + pthread_cond_t cv = NULL; + + if (cond == NULL) + {(cond + return EINVAL; + } + + if ((attr != NULL && *attr != NULL) && + ((*attr)->pshared == PTHREAD_PROCESS_SHARED)) + { + /* + * Creating condition variable that can be shared between + * processes. + */ + result = ENOSYS; + + goto FAIL0; + } + + cv = (pthread_cond_t) calloc (1, sizeof (*cv)); + + if (cv == NULL) + {(cv + result = ENOMEM; + goto FAIL0; + } + + cv->nWaitersBlocked = 0; + cv->nWaitersUnblocked = 0; + cv->nWaitersToUnblock = 0; + + if (sem_init (&(cv->semBlockLock), 0, 1) != 0) + {(sem_init + goto FAIL0; + } + + if (sem_init (&(cv->semBlockQueue), 0, 0) != 0) + {(sem_init + goto FAIL1; + } + + if (pthread_mutex_init (&(cv->mtxUnblockLock), 0) != 0) + {(pthread_mutex_init + goto FAIL2; + } + + + result = 0; + + goto DONE; + + /* + * ------------- + * Failed... + * ------------- + */ +FAIL2: + (void) sem_destroy (&(cv->semBlockQueue)); + +FAIL1: + (void) sem_destroy (&(cv->semBlockLock)); + +FAIL0: +DONE: + *cond = cv; + + return (result); + +} /* pthread_cond_init */ + +int +pthread_cond_destroy (pthread_cond_t * cond) +{ + int result = 0; + pthread_cond_t cv; + + /* + * Assuming any race condition here is harmless. + */ + if (cond == NULL + || *cond == NULL) + { + return EINVAL; + } + + if (*cond != (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(*cond + cv = *cond; + + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + {(sem_wait(&(cv->semBlockLock)) + return errno; + } + + /* + * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + {((result + (void) sem_post(&(cv->semBlockLock)); + return result; + } + + /* + * Check whether cv is still busy (still has waiters blocked) + */ + if (cv->nWaitersBlocked - cv->nWaitersUnblocked > 0) + {(cv->nWaitersBlocked + (void) sem_post(&(cv->semBlockLock)); + (void) pthread_mutex_unlock(&(cv->mtxUnblockLock)); + return EBUSY; + } + + /* + * Now it is safe to destroy + */ + (void) sem_destroy (&(cv->semBlockLock)); + (void) sem_destroy (&(cv->semBlockQueue)); + (void) pthread_mutex_unlock (&(cv->mtxUnblockLock)); + (void) pthread_mutex_destroy (&(cv->mtxUnblockLock)); + + free(cv); + *cond = NULL; + } + else + { + /* + * See notes in ptw32_cond_check_need_init() above also. + */ + EnterCriticalSection(&ptw32_cond_test_init_lock); + + /* + * Check again. + */ + if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(*cond + /* + * This is all we need to do to destroy a statically + * initialised cond that has not yet been used (initialised). + * If we get to here, another thread + * waiting to initialise this cond will get an EINVAL. + */ + *cond = NULL; + } + else + { + /* + * The cv has been initialised while we were waiting + * so assume it's in use. + */ + result = EBUSY; + } + + LeaveCriticalSection(&ptw32_cond_test_init_lock); + } + + return (result); +} + +/* + * Arguments for cond_wait_cleanup, since we can only pass a + * single void * to it. + */ +typedef struct { + pthread_mutex_t * mutexPtr; + pthread_cond_t cv; + int * resultPtr; +} ptw32_cond_wait_cleanup_args_t; + +static void +ptw32_cond_wait_cleanup(void * args) +{ + ptw32_cond_wait_cleanup_args_t * cleanup_args = +(ptw32_cond_wait_cleanup_args_t *) args; + pthread_cond_t cv = cleanup_args->cv; + int * resultPtr = cleanup_args->resultPtr; + int eLastSignal; /* enum: 1=yes 0=no -1=cancelled/timedout w/o signal(s) +*/ + int result; + + /* + * Whether we got here as a result of signal/broadcast or because of + * timeout on wait or thread cancellation we indicate that we are no + * longer waiting. The waiter is responsible for adjusting waiters + * (to)unblock(ed) counts (protected by unblock lock). + * Unblock lock/Sync.LEVEL-2 supports _timedwait and cancellation. + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + {((result + *resultPtr = result; + return; + } + + cv->nWaitersUnblocked++; + + eLastSignal = (cv->nWaitersToUnblock == 0) ? + -1 : (--cv->nWaitersToUnblock == 0); + + /* + * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed + */ + if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) + {((result + *resultPtr = result; + return; + } + + /* + * If last signal... + */ + if (eLastSignal == 1) + {(eLastSignal + /* + * ...it means that we have end of 'atomic' signal/broadcast + */ + if (sem_post(&(cv->semBlockLock)) != 0) + {(sem_post(&(cv->semBlockLock)) + *resultPtr = errno; + return; + } + } + /* + * If not last signal and not timed out/cancelled wait w/o signal... + */ + else if (eLastSignal == 0) + { + /* + * ...it means that next waiter can go through semaphore + */ + if (sem_post(&(cv->semBlockQueue)) != 0) + {(sem_post(&(cv->semBlockQueue)) + *resultPtr = errno; + return; + } + } + + /* + * XSH: Upon successful return, the mutex has been locked and is owned + * by the calling thread + */ + if ((result = pthread_mutex_lock(cleanup_args->mutexPtr)) != 0) + {((result + *resultPtr = result; + } + +} /* ptw32_cond_wait_cleanup */ + +static int +ptw32_cond_timedwait (pthread_cond_t * cond, + pthread_mutex_t * mutex, + const struct timespec *abstime) +{ + int result = 0; + pthread_cond_t cv; + ptw32_cond_wait_cleanup_args_t cleanup_args; + + if (cond == NULL || *cond == NULL) + {(cond + return EINVAL; + } + + /* + * We do a quick check to see if we need to do more work + * to initialise a static condition variable. We check + * again inside the guarded section of ptw32_cond_check_need_init() + * to avoid race conditions. + */ + if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(*cond + result = ptw32_cond_check_need_init(cond); + } + + if (result != 0 && result != EBUSY) + {(result + return result; + } + + cv = *cond; + + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + {(sem_wait(&(cv->semBlockLock)) + return errno; + } + + cv->nWaitersBlocked++; + + /* + * Thats it. Counted means waiting, no more access needed + */ + if (sem_post(&(cv->semBlockLock)) != 0) + {(sem_post(&(cv->semBlockLock)) + return errno; + } + + /* + * Setup this waiter cleanup handler + */ + cleanup_args.mutexPtr = mutex; + cleanup_args.cv = cv; + cleanup_args.resultPtr = &result; + + pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) &cleanup_args); + + /* + * Now we can release 'mutex' and... + */ + if ((result = pthread_mutex_unlock (mutex)) == 0) + {((result + + /* + * ...wait to be awakened by + * pthread_cond_signal, or + * pthread_cond_broadcast, or + * timeout, or + * thread cancellation + * + * Note: + * + * ptw32_sem_timedwait is a cancellation point, + * hence providing the mechanism for making + * pthread_cond_wait a cancellation point. + * We use the cleanup mechanism to ensure we + * re-lock the mutex and adjust (to)unblock(ed) waiters + * counts if we are cancelled, timed out or signalled. + */ + if (ptw32_sem_timedwait (&(cv->semBlockQueue), abstime) != 0) + {(ptw32_sem_timedwait + result = errno; + } + } + + /* + * Always cleanup + */ + pthread_cleanup_pop (1); + + + /* + * "result" can be modified by the cleanup handler. + */ + return (result); + +} /* ptw32_cond_timedwait */ + + +static int +ptw32_cond_unblock (pthread_cond_t * cond, + int unblockAll) +{ + int result; + pthread_cond_t cv; + + if (cond == NULL || *cond == NULL) + {(cond + return EINVAL; + } + + cv = *cond; + + /* + * No-op if the CV is static and hasn't been initialised yet. + * Assuming that any race condition is harmless. + */ + if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(cv + return 0; + } + + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + {(sem_wait(&(cv->semBlockLock)) + return errno; + } + + /* + * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) + * This sync.level supports _timedwait and cancellation + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + {((result + return result; + } + + /* + * Adjust waiters blocked and unblocked counts (collect garbage) + */ + if (cv->nWaitersUnblocked != 0) + {(cv->nWaitersUnblocked + cv->nWaitersBlocked -= cv->nWaitersUnblocked; + cv->nWaitersUnblocked = 0; + } + + /* + * If (after adjustment) there are still some waiters blocked counted... + */ + if ( cv->nWaitersBlocked > 0) + {( + /* + * We will unblock first waiter and leave semBlockLock/LEVEL-1 locked + * LEVEL-1 access is left disabled until last signal/unblock +completes + */ + cv->nWaitersToUnblock = (unblockAll) ? cv->nWaitersBlocked : 1; + + /* + * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed + * This sync.level supports _timedwait and cancellation + */ + if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) + {((result + return result; + } + + + /* + * Now, with LEVEL-2 lock released let first waiter go through +semaphore + */ + if (sem_post(&(cv->semBlockQueue)) != 0) + {(sem_post(&(cv->semBlockQueue)) + return errno; + } + } + /* + * No waiter blocked - no more LEVEL-1 access to blocked count needed... + */ + else if (sem_post(&(cv->semBlockLock)) != 0) + { + return errno; + } + /* + * ...and no more LEVEL-2 access to waiters (to)unblock(ed) counts needed +too + * This sync.level supports _timedwait and cancellation + */ + else + { + result = pthread_mutex_unlock(&(cv->mtxUnblockLock)); + } + + return(result); + +} /* ptw32_cond_unblock */ + +int +pthread_cond_wait (pthread_cond_t * cond, + pthread_mutex_t * mutex) +{ + /* The NULL abstime arg means INFINITE waiting. */ + return(ptw32_cond_timedwait(cond, mutex, NULL)); +} /* pthread_cond_wait */ + + +int +pthread_cond_timedwait (pthread_cond_t * cond, + pthread_mutex_t * mutex, + const struct timespec *abstime) +{ + if (abstime == NULL) + {(abstime + return EINVAL; + } + + return(ptw32_cond_timedwait(cond, mutex, abstime)); +} /* pthread_cond_timedwait */ + + +int +pthread_cond_signal (pthread_cond_t * cond) +{ + /* The '0'(FALSE) unblockAll arg means unblock ONE waiter. */ + return(ptw32_cond_unblock(cond, 0)); +} /* pthread_cond_signal */ + +int +pthread_cond_broadcast (pthread_cond_t * cond) +{ + /* The '1'(TRUE) unblockAll arg means unblock ALL waiters. */ + return(ptw32_cond_unblock(cond, 1)); +} /* pthread_cond_broadcast */ + + + + +TEREKHOV@de.ibm.com on 17.01.2001 01:00:57 + +Please respond to TEREKHOV@de.ibm.com + +To: pthreads-win32@sourceware.cygnus.com +cc: schmidt@uci.edu +Subject: win32 conditions: sem+counter+event = broadcast_deadlock + + spur.wakeup/unfairness/incorrectness ?? + + + + + + + +Hi, + +Problem 1: broadcast_deadlock + +It seems that current implementation does not provide "atomic" +broadcasts. That may lead to "nested" broadcasts... and it seems +that nested case is not handled correctly -> producing a broadcast +DEADLOCK as a result. + +Scenario: + +N (>1) waiting threads W1..N are blocked (in _wait) on condition's +semaphore. + +Thread B1 calls pthread_cond_broadcast, which results in "releasing" N +W threads via incrementing semaphore counter by N (stored in +cv->waiters) BUT cv->waiters counter does not change!! The caller +thread B1 remains blocked on cv->waitersDone event (auto-reset!!) BUT +condition is not protected from starting another broadcast (when called +on another thread) while still waiting for the "old" broadcast to +complete on thread B1. + +M (>=0, <N) W threads are fast enough to go thru their _wait call and +decrement cv->waiters counter. + +L (N-M) "late" waiter W threads are a) still blocked/not returned from +their semaphore wait call or b) were preempted after sem_wait but before +lock( &cv->waitersLock ) or c) are blocked on cv->waitersLock. + +cv->waiters is still > 0 (= L). + +Another thread B2 (or some W thread from M group) calls +pthread_cond_broadcast and gains access to counter... neither a) nor b) +prevent thread B2 in pthread_cond_broadcast from gaining access to +counter and starting another broadcast ( for c) - it depends on +cv->waitersLock scheduling rules: FIFO=OK, PRTY=PROBLEM,... ) + +That call to pthread_cond_broadcast (on thread B2) will result in +incrementing semaphore by cv->waiters (=L) which is INCORRECT (all +W1..N were in fact already released by thread B1) and waiting on +_auto-reset_ event cv->waitersDone which is DEADLY WRONG (produces a +deadlock)... + +All late W1..L threads now have a chance to complete their _wait call. +Last W_L thread sets an auto-reselt event cv->waitersDone which will +release either B1 or B2 leaving one of B threads in a deadlock. + +Problem 2: spur.wakeup/unfairness/incorrectness + +It seems that: + +a) because of the same problem with counter which does not reflect the +actual number of NOT RELEASED waiters, the signal call may increment +a semaphore counter w/o having a waiter blocked on it. That will result +in (best case) spurious wake ups - performance degradation due to +unnecessary context switches and predicate re-checks and (in worth case) +unfairness/incorrectness problem - see b) + +b) neither signal nor broadcast prevent other threads - "new waiters" +(and in the case of signal, the caller thread as well) from going into +_wait and overtaking "old" waiters (already released but still not returned +from sem_wait on condition's semaphore). Win semaphore just [API DOC]: +"Maintains a count between zero and some maximum value, limiting the number +of threads that are simultaneously accessing a shared resource." Calling +ReleaseSemaphore does not imply (at least not documented) that on return +from ReleaseSemaphore all waiters will in fact become released (returned +from their Wait... call) and/or that new waiters calling Wait... afterwards +will become less importance. It is NOT documented to be an atomic release +of +waiters... And even if it would be there is still a problem with a thread +being preempted after Wait on semaphore and before Wait on cv->waitersLock +and scheduling rules for cv->waitersLock itself +(??WaitForMultipleObjects??) +That may result in unfairness/incorrectness problem as described +for SetEvent impl. in "Strategies for Implementing POSIX Condition +Variables +on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html + +Unfairness -- The semantics of the POSIX pthread_cond_broadcast function is +to wake up all threads currently blocked in wait calls on the condition +variable. The awakened threads then compete for the external_mutex. To +ensure +fairness, all of these threads should be released from their +pthread_cond_wait calls and allowed to recheck their condition expressions +before other threads can successfully complete a wait on the condition +variable. + +Unfortunately, the SetEvent implementation above does not guarantee that +all +threads sleeping on the condition variable when cond_broadcast is called +will +acquire the external_mutex and check their condition expressions. Although +the Pthreads specification does not mandate this degree of fairness, the +lack of fairness can cause starvation. + +To illustrate the unfairness problem, imagine there are 2 threads, C1 and +C2, +that are blocked in pthread_cond_wait on condition variable not_empty_ that +is guarding a thread-safe message queue. Another thread, P1 then places two +messages onto the queue and calls pthread_cond_broadcast. If C1 returns +from +pthread_cond_wait, dequeues and processes the message, and immediately +waits +again then it and only it may end up acquiring both messages. Thus, C2 will +never get a chance to dequeue a message and run. + +The following illustrates the sequence of events: + +1. Thread C1 attempts to dequeue and waits on CV non_empty_ +2. Thread C2 attempts to dequeue and waits on CV non_empty_ +3. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_ +4. Thread P1 exits +5. Thread C1 wakes up from CV not_empty_, dequeues a message and runs +6. Thread C1 waits again on CV not_empty_, immediately dequeues the 2nd + message and runs +7. Thread C1 exits +8. Thread C2 is the only thread left and blocks forever since + not_empty_ will never be signaled + +Depending on the algorithm being implemented, this lack of fairness may +yield +concurrent programs that have subtle bugs. Of course, application +developers +should not rely on the fairness semantics of pthread_cond_broadcast. +However, +there are many cases where fair implementations of condition variables can +simplify application code. + +Incorrectness -- A variation on the unfairness problem described above +occurs +when a third consumer thread, C3, is allowed to slip through even though it +was not waiting on condition variable not_empty_ when a broadcast occurred. + +To illustrate this, we will use the same scenario as above: 2 threads, C1 +and +C2, are blocked dequeuing messages from the message queue. Another thread, +P1 +then places two messages onto the queue and calls pthread_cond_broadcast. +C1 +returns from pthread_cond_wait, dequeues and processes the message. At this +time, C3 acquires the external_mutex, calls pthread_cond_wait and waits on +the events in WaitForMultipleObjects. Since C2 has not had a chance to run +yet, the BROADCAST event is still signaled. C3 then returns from +WaitForMultipleObjects, and dequeues and processes the message in the +queue. +Thus, C2 will never get a chance to dequeue a message and run. + +The following illustrates the sequence of events: + +1. Thread C1 attempts to dequeue and waits on CV non_empty_ +2. Thread C2 attempts to dequeue and waits on CV non_empty_ +3. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_ +4. Thread P1 exits +5. Thread C1 wakes up from CV not_empty_, dequeues a message and runs +6. Thread C1 exits +7. Thread C3 waits on CV not_empty_, immediately dequeues the 2nd + message and runs +8. Thread C3 exits +9. Thread C2 is the only thread left and blocks forever since + not_empty_ will never be signaled + +In the above case, a thread that was not waiting on the condition variable +when a broadcast occurred was allowed to proceed. This leads to incorrect +semantics for a condition variable. + + +COMMENTS??? + +regards, +alexander. + @@ -319,7 +319,6 @@ pthread_condattr_setpshared (pthread_condattr_t * attr, int pshared) } /* pthread_condattr_setpshared */ - int pthread_cond_init (pthread_cond_t * cond, const pthread_condattr_t * attr) /* @@ -377,43 +376,40 @@ pthread_cond_init (pthread_cond_t * cond, const pthread_condattr_t * attr) goto FAIL0; } - cv->waiters = 0; - cv->wasBroadcast = FALSE; + cv->nWaitersBlocked = 0; + cv->nWaitersUnblocked = 0; + cv->nWaitersToUnblock = 0; - if (sem_init (&(cv->sema), 0, 0) != 0) + if (sem_init(&(cv->semBlockLock), 0, 1) != 0) { goto FAIL0; } - if (pthread_mutex_init (&(cv->waitersLock), NULL) != 0) + + if (sem_init(&(cv->semBlockQueue), 0, 0) != 0) { goto FAIL1; } - cv->waitersDone = CreateEvent ( - 0, - (int) FALSE, /* manualReset */ - (int) FALSE, /* setSignaled */ - NULL); - - if (cv->waitersDone == NULL) + if (pthread_mutex_init(&(cv->mtxUnblockLock), 0) != 0) { goto FAIL2; } + result = 0; goto DONE; /* * ------------- - * Failure Code + * Failed... * ------------- */ FAIL2: - (void) pthread_mutex_destroy (&(cv->waitersLock)); + (void) sem_destroy(&(cv->semBlockQueue)); FAIL1: - (void) sem_destroy (&(cv->sema)); + (void) sem_destroy(&(cv->semBlockLock)); FAIL0: DONE: @@ -423,7 +419,6 @@ DONE: } /* pthread_cond_init */ - int pthread_cond_destroy (pthread_cond_t * cond) /* @@ -458,7 +453,7 @@ pthread_cond_destroy (pthread_cond_t * cond) /* * Assuming any race condition here is harmless. */ - if (cond == NULL + if (cond == NULL || *cond == NULL) { return EINVAL; @@ -468,24 +463,42 @@ pthread_cond_destroy (pthread_cond_t * cond) { cv = *cond; - if (pthread_mutex_lock(&(cv->waitersLock)) != 0) - { - return EINVAL; - } + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + { + return errno; + } - if (cv->waiters > 0) - { - (void) pthread_mutex_unlock(&(cv->waitersLock)); - return EBUSY; - } + /* + * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + { + (void) sem_post(&(cv->semBlockLock)); + return result; + } - (void) sem_destroy (&(cv->sema)); - (void) CloseHandle (cv->waitersDone); - (void) pthread_mutex_unlock(&(cv->waitersLock)); - (void) pthread_mutex_destroy (&(cv->waitersLock)); + /* + * Check whether cv is still busy (still has waiters blocked) + */ + if (cv->nWaitersBlocked - cv->nWaitersUnblocked > 0) + { + (void) sem_post(&(cv->semBlockLock)); + (void) pthread_mutex_unlock(&(cv->mtxUnblockLock)); + return EBUSY; + } + /* + * Now it is safe to destroy + */ + *cond = NULL; /* Invalidate it before anything else */ + (void) sem_destroy(&(cv->semBlockLock)); + (void) sem_destroy(&(cv->semBlockQueue)); + (void) pthread_mutex_unlock(&(cv->mtxUnblockLock)); + (void) pthread_mutex_destroy(&(cv->mtxUnblockLock)); free(cv); - *cond = NULL; } else { @@ -535,59 +548,76 @@ typedef struct { static void ptw32_cond_wait_cleanup(void * args) { - ptw32_cond_wait_cleanup_args_t * cleanup_args = (ptw32_cond_wait_cleanup_args_t *) args; - pthread_mutex_t * mutexPtr = cleanup_args->mutexPtr; + ptw32_cond_wait_cleanup_args_t * cleanup_args = + (ptw32_cond_wait_cleanup_args_t *) args; pthread_cond_t cv = cleanup_args->cv; int * resultPtr = cleanup_args->resultPtr; - int lastWaiter = FALSE; + int eLastSignal; /* enum: 1=yes 0=no -1=cancelled/timedout w/o signal(s) */ + int result; /* - * Whether we got here legitimately or because of an error we - * indicate that we are no longer waiting. The alternative - * will result in never signaling the broadcasting thread. + * Whether we got here as a result of signal/broadcast or because of + * timeout on wait or thread cancellation we indicate that we are no + * longer waiting. The waiter is responsible for adjusting waiters + * (to)unblock(ed) counts (protected by unblock lock). + * Unblock lock/Sync.LEVEL-2 supports _timedwait and cancellation. */ - if (pthread_mutex_lock (&(cv->waitersLock)) == 0) + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) { - /* - * The waiter is responsible for decrementing - * its count, protected by an internal mutex. - */ + *resultPtr = result; + return; + } + + cv->nWaitersUnblocked++; - cv->waiters--; + eLastSignal = (cv->nWaitersToUnblock == 0) ? -1 : (--cv->nWaitersToUnblock == 0); - lastWaiter = cv->wasBroadcast && (cv->waiters == 0); + /* + * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed + */ + if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) + { + *resultPtr = result; + return; + } - if (lastWaiter) + /* + * If last signal... + */ + if (eLastSignal == 1) + { + /* + * ...it means that we have end of 'atomic' signal/broadcast + */ + if (sem_post(&(cv->semBlockLock)) != 0) { - cv->wasBroadcast = FALSE; + *resultPtr = errno; + return; } - - (void) pthread_mutex_unlock (&(cv->waitersLock)); } - /* - * If we are the last waiter on this broadcast - * let the thread doing the broadcast proceed + * If not last signal and not timed out/cancelled wait w/o signal... */ - if (lastWaiter && !SetEvent (cv->waitersDone)) + else if (eLastSignal == 0) { - *resultPtr = EINVAL; + /* + * ...it means that next waiter can go through semaphore + */ + if (sem_post(&(cv->semBlockQueue)) != 0) + { + *resultPtr = errno; + return; + } } /* - * We must always regain the external mutex, even when - * errors occur, because that's the guarantee that we give - * to our callers. - * - * Note that the broadcasting thread may already own the lock. - * The standard actually requires that the signaling thread hold - * the lock at the time that it signals if the developer wants - * predictable scheduling behaviour. It's up to the developer. - * In that case all waiting threads will block here until - * the broadcasting thread releases the lock, having been - * notified by the last waiting thread (SetEvent call above). + * XSH: Upon successful return, the mutex has been locked and is owned + * by the calling thread */ - (void) pthread_mutex_lock (mutexPtr); + if ((result = pthread_mutex_lock(cleanup_args->mutexPtr)) != 0) + { + *resultPtr = result; + } } static int @@ -623,63 +653,68 @@ ptw32_cond_timedwait (pthread_cond_t * cond, cv = *cond; /* - * It's not OK to increment cond->waiters while the caller locked 'mutex', - * there may be other threads just waking up (with 'mutex' unlocked) - * and cv->... data is not protected. + * Synchronize access to waiters blocked count (LEVEL-1) */ - if (pthread_mutex_lock(&(cv->waitersLock)) != 0) + if (sem_wait(&(cv->semBlockLock)) != 0) { - return EINVAL; + return errno; } - cv->waiters++; + cv->nWaitersBlocked++; - if (pthread_mutex_unlock(&(cv->waitersLock)) != 0) + /* + * Thats it. Counted means waiting, no more access needed + */ + if (sem_post(&(cv->semBlockLock)) != 0) { - return EINVAL; + return errno; } /* - * We keep the lock held just long enough to increment the count of - * waiters by one (above). - * Note that we can't keep it held across the - * call to sem_wait since that will deadlock other calls - * to pthread_cond_signal + * Setup this waiter cleanup handler */ cleanup_args.mutexPtr = mutex; cleanup_args.cv = cv; cleanup_args.resultPtr = &result; - pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) &cleanup_args); + pthread_cleanup_push(ptw32_cond_wait_cleanup, (void *) &cleanup_args); - if ((result = pthread_mutex_unlock (mutex)) == 0) + /* + * Now we can release 'mutex' and... + */ + if ((result = pthread_mutex_unlock(mutex)) == 0) { + /* - * Wait to be awakened by + * ...wait to be awakened by * pthread_cond_signal, or * pthread_cond_broadcast, or - * a timeout + * timeout, or + * thread cancellation + * + * Note: * - * Note: - * ptw32_sem_timedwait is a cancelation point, - * hence providing the - * mechanism for making pthread_cond_wait a cancelation - * point. We use the cleanup mechanism to ensure we - * re-lock the mutex and decrement the waiters count - * if we are canceled. + * ptw32_sem_timedwait is a cancellation point, + * hence providing the mechanism for making + * pthread_cond_wait a cancellation point. + * We use the cleanup mechanism to ensure we + * re-lock the mutex and adjust (to)unblock(ed) waiters + * counts if we are cancelled, timed out or signalled. */ - if (ptw32_sem_timedwait (&(cv->sema), abstime) == -1) - { - result = errno; - } + if (ptw32_sem_timedwait(&(cv->semBlockQueue), abstime) != 0) + { + result = errno; + } } - pthread_cleanup_pop (1); /* Always cleanup */ + /* + * Always cleanup + */ + pthread_cleanup_pop(1); + /* * "result" can be modified by the cleanup handler. - * Specifically, if we are the last waiting thread and failed - * to notify the broadcast thread to proceed. */ return (result); @@ -736,8 +771,11 @@ pthread_cond_wait (pthread_cond_t * cond, * ------------------------------------------------------ */ { - /* The NULL abstime arg means INFINITE waiting. */ + /* + * The NULL abstime arg means INFINITE waiting. + */ return(ptw32_cond_timedwait(cond, mutex, NULL)); + } /* pthread_cond_wait */ @@ -805,6 +843,105 @@ pthread_cond_timedwait (pthread_cond_t * cond, } /* pthread_cond_timedwait */ +static int +ptw32_cond_unblock (pthread_cond_t * cond, + int unblockAll) +{ + int result; + pthread_cond_t cv; + + if (cond == NULL || *cond == NULL) + { + return EINVAL; + } + + cv = *cond; + + /* + * No-op if the CV is static and hasn't been initialised yet. + * Assuming that any race condition is harmless. + */ + if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + { + return 0; + } + + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + { + return errno; + } + + /* + * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) + * This sync.level supports _timedwait and cancellation + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + { + return result; + } + + /* + * Adjust waiters blocked and unblocked counts (collect garbage) + */ + if (cv->nWaitersUnblocked != 0) + { + cv->nWaitersBlocked -= cv->nWaitersUnblocked; + cv->nWaitersUnblocked = 0; + } + + /* + * If (after adjustment) there are still some waiters blocked counted... + */ + if ( cv->nWaitersBlocked > 0) + { + /* + * We will unblock first waiter and leave semBlockLock/LEVEL-1 locked + * LEVEL-1 access is left disabled until last signal/unblock completes + */ + cv->nWaitersToUnblock = (unblockAll) ? cv->nWaitersBlocked : 1; + + /* + * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed + * This sync.level supports _timedwait and cancellation + */ + if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) + { + return result; + } + + + /* + * Now, with LEVEL-2 lock released let first waiter go through semaphore + */ + if (sem_post(&(cv->semBlockQueue)) != 0) + { + return errno; + } + } + /* + * No waiter blocked - no more LEVEL-1 access to blocked count needed... + */ + else if (sem_post(&(cv->semBlockLock)) != 0) + { + return errno; + } + /* + * ...and no more LEVEL-2 access to waiters (to)unblock(ed) counts needed too + * This sync.level supports _timedwait and cancellation + */ + else + { + result = pthread_mutex_unlock(&(cv->mtxUnblockLock)); + } + + return(result); + +} /* ptw32_cond_unblock */ + + int pthread_cond_signal (pthread_cond_t * cond) /* @@ -847,35 +984,10 @@ pthread_cond_signal (pthread_cond_t * cond) * ------------------------------------------------------ */ { - int result = 0; - pthread_cond_t cv; - - if (cond == NULL || *cond == NULL) - { - return EINVAL; - } - - cv = *cond; - - /* - * No-op if the CV is static and hasn't been initialised yet. - * Assuming that race conditions are harmless. - */ - if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) - { - return 0; - } - - /* - * If there aren't any waiters, then this is a no-op. - * Assuming that race conditions are harmless. + /* + * The '0'(FALSE) unblockAll arg means unblock ONE waiter. */ - if (cv->waiters > 0) - { - result = sem_post (&(cv->sema)); - } - - return (result); + return(ptw32_cond_unblock(cond, 0)); } /* pthread_cond_signal */ @@ -917,76 +1029,10 @@ pthread_cond_broadcast (pthread_cond_t * cond) * ------------------------------------------------------ */ { - int result = 0; - int wereWaiters = FALSE; - pthread_cond_t cv; - - if (cond == NULL || *cond == NULL) - { - return EINVAL; - } - - cv = *cond; - - /* - * No-op if the CV is static and hasn't been initialised yet. - * Assuming that any race condition is harmless. + /* + * The '1'(TRUE) unblockAll arg means unblock ALL waiters. */ - if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) - { - return 0; - } - - if (pthread_mutex_lock(&(cv->waitersLock)) == EINVAL) - { - return EINVAL; - } - - cv->wasBroadcast = TRUE; - wereWaiters = (cv->waiters > 0); - - if (wereWaiters) - { - /* - * Wake up all waiters - */ - -#ifdef NEED_SEM - - result = (ptw32_increase_semaphore( &cv->sema, cv->waiters ) - ? 0 - : EINVAL); - -#else /* NEED_SEM */ - - result = (ReleaseSemaphore( cv->sema, cv->waiters, NULL ) - ? 0 - : EINVAL); - -#endif /* NEED_SEM */ - - } - - (void) pthread_mutex_unlock(&(cv->waitersLock)); - - if (wereWaiters && result == 0) - { - /* - * Wait for all the awakened threads to acquire their part of - * the counting semaphore - */ - if (WaitForSingleObject (cv->waitersDone, INFINITE) - == WAIT_OBJECT_0) - { - result = 0; - } - else - { - result = EINVAL; - } - - } - - return (result); + return(ptw32_cond_unblock(cond, 1)); } + diff --git a/implement.h b/implement.h index c6f535e..ec889e3 100644 --- a/implement.h +++ b/implement.h @@ -72,6 +72,32 @@ typedef enum { } PThreadDemise; + +/* + * ==================== + * ==================== + * Internal implementation of a critical section + * ==================== + * ==================== + */ + +typedef struct ptw32_cs_t_ { + CRITICAL_SECTION cs; + LONG lock_idx; + int entered_count; + int valid; + pthread_t owner; +} ptw32_cs_t; + + +/* + * ==================== + * ==================== + * POSIX thread and attributes + * ==================== + * ==================== + */ + struct pthread_t_ { DWORD thread; HANDLE threadH; @@ -122,8 +148,7 @@ struct pthread_attr_t_ { #define PTW32_OBJECT_INVALID NULL struct pthread_mutex_t_ { - HANDLE mutex; - CRITICAL_SECTION cs; + ptw32_cs_t cs; int lockCount; pthread_t ownerThread; }; @@ -131,7 +156,7 @@ struct pthread_mutex_t_ { struct pthread_mutexattr_t_ { int pshared; - int forcecs; + int type; }; @@ -152,7 +177,7 @@ struct ThreadParms { void *arg; }; - +#if 0 struct pthread_cond_t_ { long waiters; /* # waiting threads */ pthread_mutex_t waitersLock; /* Mutex that guards access to @@ -168,6 +193,22 @@ struct pthread_cond_t_ { or broadcasting */ }; +#else + +struct pthread_cond_t_ { + long nWaitersBlocked; /* Number of threads blocked */ + long nWaitersUnblocked; /* Number of threads unblocked */ + long nWaitersToUnblock; /* Number of threads to unblock */ + sem_t semBlockQueue; /* Queue up threads waiting for the */ + /* condition to become signalled */ + sem_t semBlockLock; /* Semaphore that guards access to */ + /* waiters blocked count/block queue */ + /* +-> Mandatory Sync.LEVEL-1 */ + pthread_mutex_t mtxUnblockLock; /* Mutex that guards access to */ + /* waiters (to)unblock(ed) counts */ + /* +-> Optional* Sync.LEVEL-2 */ +}; /* Opt*) for _timedwait and cancellation */ +#endif struct pthread_condattr_t_ { int pshared; @@ -142,36 +142,9 @@ pthread_self (void) * ------------------------------------------------------ */ { - pthread_t self = NULL; - DWORD lastErr; + pthread_t self; - /* - * Need to ensure there always is a self. - * - * The following call to pthread_getspecific uses TlsGetValue. - * Win32 functions that return indications of failure call SetLastError when - * they fail. They generally do not call SetLastError when they succeed. The - * TlsGetValue function is an exception to this general rule. The TlsGetValue - * function calls SetLastError to clear a thread's last error when it - * succeeds. - * - * We restore the last error if TlsGetValue succeeds. - */ - lastErr = GetLastError(); self = (pthread_t) pthread_getspecific (ptw32_selfThreadKey); - if (GetLastError() == NO_ERROR) - { - SetLastError(lastErr); - } - else - { - /* - * What else can we do? GetLastError will tell the - * the caller more but this is not supposed to - * happen. - */ - return(NULL); - } if (self == NULL) { @@ -85,6 +85,222 @@ ptw32_mutex_check_need_init(pthread_mutex_t *mutex) return(result); } + +/* + * The following internal versions of *CriticalSection() + * include an implementation of TryEnterCriticalSection + * for platforms on which that function has not been + * provided by Microsoft (eg. W95/98). This allows us + * to use critical sections exclusively as the basis + * of our implementation of POSIX mutex locks. + * + * Where TryEnterCriticalSection() is provided by the + * platform, these routines act as wrappers with + * minimal additional overhead. Otherwise, these + * routines manage additional state in order to + * properly emulate TryEnterCriticalSection(). + * + * In any case, using of critical sections exclusively + * should still be much faster than using Win32 mutex + * locks as our POSIX mutex locks. + */ + +static void +ptw32_InitializeCriticalSection (ptw32_cs_t * csect) + /* + * ------------------------------------------------------ + * + * PARAMETERS + * csect + * pointer to an instance of ptw32_cs_t + * + * DESCRIPTION + * Internal implementation of InitializeCriticalSection. + * + * ------------------------------------------------------ + */ +{ + ptw32_cs_t cs = *csect; + + cs->owner = NULL; + cs->lock_idx = -1; + cs->entered_count = 0; + InitializeCriticalSection(&cs->cs); + cs->valid = 1; +} + +static void +ptw32_DeleteCriticalSection (ptw32_cs_t * csect) + /* + * ------------------------------------------------------ + * + * PARAMETERS + * csect + * pointer to an instance of ptw32_cs_t + * + * DESCRIPTION + * Internal implementation of DeleteCriticalSection. + * + * ------------------------------------------------------ + */ +{ + ptw32_cs_t cs = *csect; + + cs->valid = 0; + DeleteCriticalSection(&cs->cs); +} + +static void +ptw32_EnterCriticalSection(ptw32_cs_t * csect) + /* + * ------------------------------------------------------ + * + * PARAMETERS + * csect + * pointer to an instance of ptw32_cs_t + * + * DESCRIPTION + * Internal implementation of EnterCriticalSection. + * + * ------------------------------------------------------ + */ +{ + ptw32_cs_t cs = *csect; + + if (!cs->valid) + { + return; + } + + if (NULL != ptw32_try_enter_critical_section) + { + EnterCriticalSection(&cs->cs); + } + else + { + while (InterlockedIncrement(&cs->lock_idx) > 0) + { + InterlockedDecrement(&cs->lock_idx); + Sleep(0); + } + EnterCriticalSection(&cs->cs); + cs->entered_count++; + cs->owner = pthread_self(); + InterlockedDecrement(&cs->lock_idx); + } +} + +static void +ptw32_LeaveCriticalSection (ptw32_cs_t * csect) + /* + * ------------------------------------------------------ + * + * PARAMETERS + * csect + * pointer to an instance of ptw32_cs_t + * + * DESCRIPTION + * Internal implementation of LeaveCriticalSection. + * + * ------------------------------------------------------ + */ +{ + ptw32_cs_t cs = *csect; + + if (!cs->valid) + { + return; + } + + if (NULL != ptw32_try_enter_critical_section) + { + LeaveCriticalSection(&cs->cs); + } + else + { + while (InterlockedIncrement(&cs->lock_idx) > 0) + { + InterlockedDecrement(&cs->lock_idx); + Sleep(0); + } + + LeaveCriticalSection(&cs->cs); + + cs->entered_count--; + + if (cs->entered_count == 0) + { + cs->owner = NULL; + } + + InterlockedDecrement(&cs->lock_idx); + } +} + +static BOOL +ptw32_TryEnterCriticalSection (ptw32_cs_t * csect) + /* + * ------------------------------------------------------ + * + * PARAMETERS + * csect + * pointer to an instance of ptw32_cs_t + * + * DESCRIPTION + * Internal implementation of TryEnterCriticalSection. + * + * RETURNS + * FALSE Current thread doesn't own the + * lock, + * TRUE Current thread owns the lock + * (if the current thread already + * held the lock then we recursively + * enter). + * ------------------------------------------------------ + */ +{ + ptw32_cs_t cs = *csect; + BOOL result = FALSE; + + if (!cs->valid) + { + return (FALSE); + } + + if (NULL != ptw32_try_enter_critical_section) + { + result = (*ptw32_try_enter_critical_section)(&cs->cs); + } + else + { + pthread_t self = pthread_self(); + + while (InterlockedIncrement(&cs->lock_idx) > 0) + { + InterlockedDecrement(&cs->lock_idx); + Sleep(0); + } + + if (cs->owner == NULL || pthread_equal(cs->owner, self)) + { + /* The semantics of TryEnterCriticalSection + * (according to the documentation at MS) + * are that the CS is entered recursively + * if the thread is the current owner. + */ + EnterCriticalSection(&cs->cs); + cs->entered_count++; + cs->owner = self; + result = TRUE; + } + + InterlockedDecrement(&cs->lock_idx); + } + + return (result); +} + + int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr) { @@ -104,82 +320,35 @@ pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr) goto FAIL0; } - mx->mutex = 0; + ptw32_InitializeCriticalSection(&mx->cs); mx->lockCount = 0; mx->ownerThread = NULL; - if (attr != NULL - && *attr != NULL - && (*attr)->pshared == PTHREAD_PROCESS_SHARED - ) + if (attr != NULL && *attr != NULL) { - /* - * Creating mutex that can be shared between - * processes. - */ -#if _POSIX_THREAD_PROCESS_SHARED - /* - * Not implemented yet. - */ + mx->type = (*attr)->type; -#error ERROR [__FILE__, line __LINE__]: Process shared mutexes are not supported yet. + if ((*attr)->pshared == PTHREAD_PROCESS_SHARED) + { + /* + * Creating mutex that can be shared between + * processes. + */ +#if _POSIX_THREAD_PROCESS_SHARED - mx->mutex = CreateMutex(NULL, FALSE, "FIXME FIXME FIXME"); + /* + * Not implemented yet. + */ - if (mx->mutex == 0) - { - result = EAGAIN; - } +#error ERROR [__FILE__, line __LINE__]: Process shared mutexes are not supported yet. #else - result = ENOSYS; + result = ENOSYS; #endif /* _POSIX_THREAD_PROCESS_SHARED */ - } - else - { - if (ptw32_try_enter_critical_section != NULL - || (attr != NULL - && *attr != NULL - && (*attr)->forcecs == 1) - ) - { - /* - * Create a critical section. - */ - InitializeCriticalSection(&mx->cs); - - /* - * Check that it works ok - since InitializeCriticalSection doesn't - * return success or failure. - */ - if ((*ptw32_try_enter_critical_section)(&mx->cs)) - { - LeaveCriticalSection(&mx->cs); - } - else - { - DeleteCriticalSection(&mx->cs); - result = EAGAIN; - } - } - else - { - /* - * Create a mutex that can only be used within the - * current process - */ - mx->mutex = CreateMutex (NULL, - FALSE, - NULL); - - if (mx->mutex == 0) - { - result = EAGAIN; - } - } + } } if (result != 0 && mx != NULL) @@ -200,8 +369,7 @@ pthread_mutex_destroy(pthread_mutex_t *mutex) int result = 0; pthread_mutex_t mx; - if (mutex == NULL - || *mutex == NULL) + if (mutex == NULL || *mutex == NULL) { return EINVAL; } @@ -213,7 +381,9 @@ pthread_mutex_destroy(pthread_mutex_t *mutex) { mx = *mutex; - if ((result = pthread_mutex_trylock(&mx)) == 0) + result = pthread_mutex_trylock(&mx); + + if (result == 0 || result == EDEADLK) { /* * FIXME!!! @@ -224,20 +394,11 @@ pthread_mutex_destroy(pthread_mutex_t *mutex) */ *mutex = NULL; - pthread_mutex_unlock(&mx); - - if (mx->mutex == 0) - { - DeleteCriticalSection(&mx->cs); - } - else - { - result = (CloseHandle (mx->mutex) ? 0 : EINVAL); - } + result = pthread_mutex_unlock(&mx); if (result == 0) { - mx->mutex = 0; + ptw32_DeleteCriticalSection(&mx->cs); free(mx); } else @@ -321,6 +482,9 @@ pthread_mutexattr_init (pthread_mutexattr_t * attr) result = ENOMEM; } + ma->pshared = PTHREAD_PROCESS_PRIVATE; + ma->type = PTHREAD_MUTEX_DEFAULT; + *attr = ma; return (result); @@ -519,10 +683,130 @@ pthread_mutexattr_setpshared (pthread_mutexattr_t * attr, int +pthread_mutexattr_settype (pthread_mutexattr_t * attr, + int type) + /* + * ------------------------------------------------------ + * + * PARAMETERS + * attr + * pointer to an instance of pthread_mutexattr_t + * + * type + * must be one of: + * + * PTHREAD_MUTEX_DEFAULT + * + * PTHREAD_MUTEX_NORMAL + * + * PTHREAD_MUTEX_ERRORCHECK + * + * PTHREAD_MUTEX_RECURSIVE + * + * DESCRIPTION + * The pthread_mutexattr_gettype() and + * pthread_mutexattr_settype() functions respectively get and + * set the mutex type attribute. This attribute is set in the + * type parameter to these functions. The default value of the + * type attribute is PTHREAD_MUTEX_DEFAULT. + * + * The type of mutex is contained in the type attribute of the + * mutex attributes. Valid mutex types include: + * + * PTHREAD_MUTEX_NORMAL + * This type of mutex does not detect deadlock. A + * thread attempting to relock this mutex without + * first unlocking it will deadlock. Attempting to + * unlock a mutex locked by a different thread + * results in undefined behavior. Attempting to + * unlock an unlocked mutex results in undefined + * behavior. + * + * PTHREAD_MUTEX_ERRORCHECK + * This type of mutex provides error checking. A + * thread attempting to relock this mutex without + * first unlocking it will return with an error. A + * thread attempting to unlock a mutex which another + * thread has locked will return with an error. A + * thread attempting to unlock an unlocked mutex will + * return with an error. + * + * PTHREAD_MUTEX_RECURSIVE + * A thread attempting to relock this mutex without + * first unlocking it will succeed in locking the + * mutex. The relocking deadlock which can occur with + * mutexes of type PTHREAD_MUTEX_NORMAL cannot occur + * with this type of mutex. Multiple locks of this + * mutex require the same number of unlocks to + * release the mutex before another thread can + * acquire the mutex. A thread attempting to unlock a + * mutex which another thread has locked will return + * with an error. A thread attempting to unlock an + * unlocked mutex will return with an error. This + * type of mutex is only supported for mutexes whose + * process shared attribute is + * PTHREAD_PROCESS_PRIVATE. + * + * RESULTS + * 0 successfully set attribute, + * EINVAL 'attr' or 'type' is invalid, + * + * ------------------------------------------------------ + */ +{ + int result = 0; + + if ((attr != NULL && *attr != NULL)) + { + switch (type) + { + case PTHREAD_MUTEX_DEFAULT: + case PTHREAD_MUTEX_NORMAL: + case PTHREAD_MUTEX_ERRORCHECK: + case PTHREAD_MUTEX_RECURSIVE: + (*attr)->type = type; + break; + default: + result = EINVAL; + break; + } + } + else + { + result = EINVAL; + } + + return (result); + +} /* pthread_mutexattr_settype */ + + +int +pthread_mutexattr_gettype (pthread_mutexattr_t * attr, + int type) +{ + int result = 0; + + if ((attr != NULL && *attr != NULL)) + { + result = (*attr)->type; + } + else + { + result = EINVAL; + } + + return (result); +} + + +int pthread_mutex_lock(pthread_mutex_t *mutex) { int result = 0; pthread_mutex_t mx; + pthread_t self; + if (mutex == NULL || *mutex == NULL) { @@ -541,25 +825,49 @@ pthread_mutex_lock(pthread_mutex_t *mutex) } mx = *mutex; + self = pthread_self(); - if (result == 0) + ptw32_EnterCriticalSection(&mx->cs); + + switch (mx->type) { - if (mx->mutex == 0) - { - EnterCriticalSection(&mx->cs); - } - else - { - result = (WaitForSingleObject(mx->mutex, INFINITE) - == WAIT_OBJECT_0) - ? 0 - : EINVAL; - } + case PTHREAD_MUTEX_NORMAL: + if (pthread_equal(mx->ownerThread, self)) + { + ptw32_LeaveCriticalSection(&mx->cs); + /* + * Pretend to be deadlocked but release the + * mutex if we are canceled. + */ + pthread_cleanup_push(pthread_mutex_unlock, (void *) mutex); + while (TRUE) + { + Sleep(0); + } + pthread_cleanup_pop(1); + } + break; + case PTHREAD_MUTEX_DEFAULT: + case PTHREAD_MUTEX_ERRORCHECK: + if (pthread_equal(mx->ownerThread, self)) + { + ptw32_LeaveCriticalSection(&mx->cs); + result = EDEADLK; + } + break; + case PTHREAD_MUTEX_RECURSIVE: + /* + * Nothing more to do. + */ + break; + default: + result = EINVAL; + break; } if (result == 0) { - mx->ownerThread = pthread_self(); + mx->ownerThread = self; mx->lockCount++; } @@ -586,39 +894,16 @@ pthread_mutex_unlock(pthread_mutex_t *mutex) */ if (mx != (pthread_mutex_t) PTW32_OBJECT_AUTO_INIT) { - pthread_t self = pthread_self(); - - if (pthread_equal(mx->ownerThread, self)) + if (pthread_equal(mx->ownerThread, pthread_self())) { - int oldCount = mx->lockCount; - pthread_t oldOwner = mx->ownerThread; - - if (mx->lockCount > 0) - { - mx->lockCount--; - } + mx->lockCount--; if (mx->lockCount == 0) { mx->ownerThread = NULL; } - if (mx->mutex == 0) - { - LeaveCriticalSection(&mx->cs); - } - else - { - if (!ReleaseMutex(mx->mutex)) - { - result = EINVAL; - /* - * Put things back the way they were. - */ - mx->lockCount = oldCount; - mx->ownerThread = oldOwner; - } - } + ptw32_LeaveCriticalSection(&mx->cs); } else { @@ -638,6 +923,7 @@ pthread_mutex_trylock(pthread_mutex_t *mutex) { int result = 0; pthread_mutex_t mx; + pthread_t self; if (mutex == NULL || *mutex == NULL) { @@ -656,36 +942,41 @@ pthread_mutex_trylock(pthread_mutex_t *mutex) } mx = *mutex; + self = pthread_self(); if (result == 0) { - if (mx->mutex == 0) - { - if ((*ptw32_try_enter_critical_section)(&mx->cs) != TRUE) - { - result = EBUSY; - } - } + /* + * TryEnterCriticalSection is a little different to + * the POSIX trylock semantics. Trylock returns + * EBUSY even if the calling thread already owns + * the mutex - it doesn't lock it recursively, even + * if the mutex type is PTHREAD_MUTEX_RECURSIVE. + */ + if (ptw32_TryEnterCriticalSection(&mx->cs)) + { + /* + * We now own the lock, but check that we don't + * already own the mutex. + */ + if (pthread_equal(mx->ownerThread, self)) + { + ptw32_LeaveCriticalSection(&mx->cs); + result = EBUSY; + } + } else - { - DWORD status; - - status = WaitForSingleObject (mx->mutex, 0); - - if (status != WAIT_OBJECT_0) - { - result = ((status == WAIT_TIMEOUT) - ? EBUSY - : EINVAL); - } - } + { + result = EBUSY; + } } if (result == 0) { - mx->ownerThread = pthread_self(); + mx->ownerThread = self; mx->lockCount++; } - return(result); + return (result); } + diff --git a/nonportable.c b/nonportable.c index 49548dd..17cbc60 100644 --- a/nonportable.c +++ b/nonportable.c @@ -27,30 +27,6 @@ #include "implement.h" /* - * pthread_mutexattr_setforcecs_np() - * - * Allows an application to force the library to use - * critical sections rather than win32 mutexes as - * the basis for any mutexes that use "attr". - * - * Values for "forcecs" are defined in pthread.h - */ -int -pthread_mutexattr_setforcecs_np(pthread_mutexattr_t *attr, - int forcecs) -{ - if (attr == NULL || *attr == NULL) - { - /* This is disallowed. */ - return EINVAL; - } - - (*attr)->forcecs = forcecs; - - return 0; -} - -/* * pthread_getw32threadhandle_np() * * Returns the win32 thread handle that the POSIX @@ -271,4 +247,4 @@ pthread_win32_thread_detach_np () } return TRUE; -}
\ No newline at end of file +} diff --git a/pthread.def b/pthread.def index 9371ce9..580caf5 100644 --- a/pthread.def +++ b/pthread.def @@ -1,5 +1,5 @@ ; pthread.def
-; Last updated: $Date: 2000/12/28 05:32:07 $
+; Last updated: $Date: 2001/02/06 05:44:38 $
; Currently unimplemented functions are commented out.
@@ -13,7 +13,7 @@ pthread_attr_getdetachstate ;pthread_attr_getinheritsched
pthread_attr_getschedparam
;pthread_attr_getschedpolicy
-;pthread_attr_getscope
+pthread_attr_getscope
pthread_attr_getstackaddr
pthread_attr_getstacksize
pthread_attr_init
@@ -21,12 +21,12 @@ pthread_attr_setdetachstate ;pthread_attr_setinheritsched
pthread_attr_setschedparam
;pthread_attr_setschedpolicy
-;pthread_attr_setscope
+pthread_attr_setscope
pthread_attr_setstackaddr
pthread_attr_setstacksize
pthread_cancel
;
-; These are implemented as macros
+; These two are implemented as macros
;
;pthread_cleanup_pop
;pthread_cleanup_push
@@ -45,6 +45,7 @@ pthread_create pthread_detach
pthread_equal
pthread_exit
+pthread_getconcurrency
pthread_getschedparam
pthread_getspecific
pthread_join
@@ -55,10 +56,12 @@ pthread_mutexattr_destroy ;pthread_mutexattr_getprioceiling
;pthread_mutexattr_getprotocol
pthread_mutexattr_getpshared
+pthread_mutexattr_gettype
pthread_mutexattr_init
;pthread_mutexattr_setprioceiling
;pthread_mutexattr_setprotocol
pthread_mutexattr_setpshared
+pthread_mutexattr_settype
pthread_mutexattr_destroy
pthread_mutex_init
pthread_mutex_destroy
@@ -69,6 +72,7 @@ pthread_once pthread_self
pthread_setcancelstate
pthread_setcanceltype
+pthread_setconcurrency
pthread_setschedparam
pthread_setspecific
;pthread_sigmask
@@ -101,7 +105,6 @@ pthread_rwlock_unlock ;
; Non-portable but useful
;
-pthread_mutexattr_setforcecs_np
pthread_getw32threadhandle_np
pthread_delay_np
pthreadCancelableWait
@@ -35,157 +35,7 @@ * POSIX 1003.1c-1995 (POSIX.1c) * * Authors: - * Contributors are listed in the file "MAINTAINERS". - * - * The following functions are implemented: - * --------------------------- - * PThreads - * --------------------------- - * pthread_attr_init - * pthread_attr_destroy - * pthread_attr_getdetachstate - * pthread_attr_getstackaddr - * pthread_attr_getstacksize - * pthread_attr_setdetachstate - * pthread_attr_setstackaddr - * pthread_attr_setstacksize - * - * pthread_create - * pthread_detach - * pthread_equal - * pthread_exit - * pthread_join - * pthread_self - * sched_yield - * - * pthread_cancel - * pthread_cleanup_pop - * pthread_cleanup_push - * pthread_setcancelstate - * pthread_setcanceltype - * pthread_testcancel - * - * --------------------------- - * Thread Specific Data - * --------------------------- - * pthread_key_create - * pthread_key_delete - * pthread_setspecific - * pthread_getspecific - * - * --------------------------- - * Mutexes - * --------------------------- - * pthread_mutexattr_init - * pthread_mutexattr_destroy - * pthread_mutexattr_getpshared - * pthread_mutexattr_setpshared - * - * pthread_mutex_init - * pthread_mutex_destroy - * pthread_mutex_lock - * pthread_mutex_trylock - * pthread_mutex_unlock - * - * --------------------------- - * Condition Variables - * --------------------------- - * pthread_condattr_init - * pthread_condattr_destroy - * pthread_condattr_getpshared - * pthread_condattr_setpshared - * - * pthread_cond_init - * pthread_cond_destroy - * pthread_cond_wait - * pthread_cond_timedwait - * pthread_cond_signal - * pthread_cond_broadcast - * - * --------------------------- - * Protected Methods - * --------------------------- - * pthreadCancelableWait - * - * --------------------------- - * RealTime Scheduling: - * --------------------------- - * pthread_attr_getschedparam - * pthread_attr_setschedparam - * pthread_getschedparam - * pthread_setschedparam - * sched_get_priority_max - * sched_get_priority_min - * - * --------------------------- - * Signals: - * --------------------------- - * pthread_sigmask - * - * --------------------------- - * Read/Write Locks: - * --------------------------- - * pthread_rwlock_init - * pthread_rwlock_destroy - * pthread_rwlock_tryrdlock - * pthread_rwlock_trywrlock - * pthread_rwlock_rdlock - * pthread_rwlock_rwlock - * pthread_rwlock_unlock - * - * Limitations - * =========== - * The following functions are not implemented: - * - * --------------------------- - * RealTime Scheduling: - * --------------------------- - * pthread_attr_getinheritsched - * pthread_attr_getschedpolicy - * pthread_attr_getscope - * pthread_attr_setinheritsched - * pthread_attr_setschedpolicy - * pthread_attr_setscope - * pthread_mutex_getprioceiling - * pthread_mutex_setprioceiling - * pthread_mutex_attr_getprioceiling - * pthread_mutex_attr_getprotocol - * pthread_mutex_attr_setprioceiling - * pthread_mutex_attr_setprotocol - * - * --------------------------- - * Fork Handlers: - * --------------------------- - * pthread_atfork - * - * --------------------------- - * Stdio: - * --------------------------- - * flockfile - * ftrylockfile - * funlockfile - * getc_unlocked - * getchar_unlocked - * putc_unlocked - * putchar_unlocked - * - * --------------------------- - * Thread-Safe C Runtime Library: - * --------------------------- - * readdir_r - * getgrgid_r - * getgrnam_r - * getpwuid_r - * getpwnam_r - * - * --------------------------- - * Signals: - * --------------------------- - * pthread_kill - * sigtimedwait - * sigwait - * sigwaitinfo - * + * Contributors are listed in the file "CONTRIBUTORS". * * ------------------------------------------------------------- */ @@ -267,6 +117,14 @@ struct timespec { #define ETIMEDOUT 10060 /* This is the value in winsock.h. */ #endif +/* + * If ENOTSUP is not defined, define it to a value that will never occur. + * This is the value used in the Win32 TCL port. + */ +#ifndef ENOTSUP +#define ENOTSUP -1030507 +#endif + #ifdef __MINGW32__ #define PT_STDCALL #else @@ -495,10 +353,20 @@ typedef struct pthread_rwlockattr_t_ *pthread_rwlockattr_t; #define PTHREAD_PROCESS_SHARED 1 /* - * pthread_mutexattr_setforcecs_np + * pthread_mutexattr_(get,set}type + */ +#define PTHREAD_MUTEX_DEFAULT 0 +#define PTHREAD_MUTEX_NORMAL 1 +#define PTHREAD_MUTEX_ERRORCHECK 2 +#define PTHREAD_MUTEX_RECURSIVE 3 + +/* + * pthread_attr_(get,set}scope + * + * PTHREAD_SCOPE_PROCESS is the only scope supported. */ -#define PTHREAD_MUTEX_AUTO_CS_NP 0 -#define PTHREAD_MUTEX_FORCE_CS_NP 1 +#define PTHREAD_SCOPE_SYSTEM 0 +#define PTHREAD_SCOPE_PROCESS 1 /* * ==================== @@ -556,6 +424,14 @@ struct sched_param { }; +/* + * ==================== + * ==================== + * Cancelation cleanup + * ==================== + * ==================== + */ + /* There are three implementations of cancel cleanup. * Note that pthread.h is included in both application * compilation units and also internally for the library. @@ -878,6 +754,19 @@ int pthread_attr_getschedparam (const pthread_attr_t *attr, int pthread_attr_setschedparam (pthread_attr_t *attr, const struct sched_param *param); +int +pthread_setconcurrency (int); + +int +pthread_getconcurrency (void); + +int +pthread_attr_setscope (const pthread_attr_t *, int); + +int +pthread_attr_getscope (const pthread_attr_t *, + int *); + /* * Read-Write Lock Functions */ @@ -904,10 +793,10 @@ int pthread_rwlock_unlock(pthread_rwlock_t *lock); /* Possibly supported by other POSIX threads implimentations */ int pthread_delay_np (struct timespec * interval); -/* Pthread Win32 specific */ -int pthread_mutexattr_setforcecs_np(pthread_mutexattr_t *attr, - int forcecs); - +/* + * Returns the Win32 thread HANDLE associated + * with the given POSIX thread. + */ HANDLE pthread_getw32threadhandle_np(pthread_t thread); /* @@ -231,7 +231,7 @@ pthread_rwlock_destroy(pthread_rwlock_t *rwlock) } static void -_rwlock_cancelrdwait(void * arg) +ptw32_rwlock_cancelrdwait(void * arg) { pthread_rwlock_t rw; @@ -286,7 +286,7 @@ pthread_rwlock_rdlock(pthread_rwlock_t *rwlock) while (rw->rw_refcount < 0 || rw->rw_nwaitwriters > 0) { rw->rw_nwaitreaders++; - pthread_cleanup_push(_rwlock_cancelrdwait, rw); + pthread_cleanup_push(ptw32_rwlock_cancelrdwait, rw); result = pthread_cond_wait(&(rw->rw_condreaders), &(rw->rw_lock)); pthread_cleanup_pop(0); rw->rw_nwaitreaders--; @@ -309,7 +309,7 @@ FAIL1: } static void -_rwlock_cancelwrwait(void * arg) +ptw32_rwlock_cancelwrwait(void * arg) { pthread_rwlock_t rw; @@ -360,7 +360,7 @@ pthread_rwlock_wrlock(pthread_rwlock_t * rwlock) while (rw->rw_refcount != 0) { rw->rw_nwaitwriters++; - pthread_cleanup_push(_rwlock_cancelwrwait, rw); + pthread_cleanup_push(ptw32_rwlock_cancelwrwait, rw); result = pthread_cond_wait(&(rw->rw_condwriters), &(rw->rw_lock)); pthread_cleanup_pop(0); rw->rw_nwaitwriters--; @@ -23,7 +23,10 @@ * MA 02111-1307, USA */ -#define ENOSUP 0 +/* + * If ENOTSUP is not defined, define it to a value that will never occur. + * This is the value used in the Win32 TCL port. + */ #include "pthread.h" #include "implement.h" @@ -63,7 +66,8 @@ pthread_attr_getschedparam(const pthread_attr_t *attr, return 0; } -int pthread_setschedparam(pthread_t thread, int policy, +int +pthread_setschedparam(pthread_t thread, int policy, const struct sched_param *param) { /* Validate the thread id. */ @@ -81,7 +85,7 @@ int pthread_setschedparam(pthread_t thread, int policy, /* Ensure the policy is SCHED_OTHER. */ if (policy != SCHED_OTHER) { - return ENOSUP; + return ENOTSUP; } /* Validate priority level. */ @@ -97,7 +101,8 @@ int pthread_setschedparam(pthread_t thread, int policy, return 0; } -int pthread_getschedparam(pthread_t thread, int *policy, +int +pthread_getschedparam(pthread_t thread, int *policy, struct sched_param *param) { int prio; @@ -129,6 +134,51 @@ int pthread_getschedparam(pthread_t thread, int *policy, } +int +pthread_setconcurrency(int level) +{ + if (level < 0) + { + return EINVAL; + } + else + { + return 0; + } +} + +int +pthread_getconcurrency(void) +{ + return 0; +} + +int +pthread_attr_setscope(pthread_attr_t *attr, int contentionscope) +{ +#ifdef _POSIX_THREAD_PRIORITY_SCHEDULING + if (contentionscope != PTHREAD_SCOPE_SYSTEM) + { + return ENOTSUP; + } + + return 0; +#else + return ENOSYS; +#endif +} + +int +pthread_attr_getscope(const pthread_attr_t *attr, int *contentionscope) +{ +#ifdef _POSIX_THREAD_PRIORITY_SCHEDULING + *contentionscope = PTHREAD_SCOPE_SYSTEM; + return 0; +#else + return ENOSYS; +#endif +} + /* * On Windows98, THREAD_PRIORITY_LOWEST is (-2) and * THREAD_PRIORITY_HIGHEST is 2, and everything works just fine. @@ -144,7 +194,8 @@ int pthread_getschedparam(pthread_t thread, int *policy, #define sched_Max(a,b) ((a)<(b)?(b):(a)) #define sched_Min(a,b) ((a)>(b)?(b):(a)) -int sched_get_priority_max(int policy) +int +sched_get_priority_max(int policy) { if (policy < SCHED_MIN || policy > SCHED_MAX) { @@ -160,7 +211,8 @@ int sched_get_priority_max(int policy) #endif } -int sched_get_priority_min(int policy) +int +sched_get_priority_min(int policy) { if (policy < SCHED_MIN || policy > SCHED_MAX) { @@ -176,7 +228,8 @@ int sched_get_priority_min(int policy) #endif } -int sched_yield(void) +int +sched_yield(void) /* * ------------------------------------------------------ * DOCPUBLIC @@ -322,6 +322,12 @@ pthread_getspecific (pthread_key_t key) * ------------------------------------------------------ */ { - return (TlsGetValue (key->key)); + int lasterror = GetLastError(); + + void *ptr = TlsGetValue(key->key); + + SetLastError(lasterror); + + return (ptr); } |