[Bug libgomp/51249] New: semaphore implemetation for linux leaves threads blocked

[Bug libgomp/51249] New: semaphore implemetation for linux leaves threads blocked

[amodra at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51249

             Bug #: 51249
           Summary: semaphore implemetation for linux leaves threads
                    blocked
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libgomp
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: amodra@gmail.com


Refer libgomp/config/linux/sem.[ch]

Threads A, B, C.  Initial sem value = 1.

A calls gomp_sem_wait, successfully decrements sem to 0.
B calls gomp_set_wait, drops into gomp_sem_wait_slow, sets sem to -1
and blocks.
C calls gomp_set_wait, and similarly blocks.  sem is -1.
A calls gomp_sem_post, drops into gomp_sem_post_slow, sets sem to 1
and wakes one thread, lets say B.
B grabs sem, sets it to 0.
B calls gomp_sem_post, setting sem to 1 but does not wake up C.
With no more semaphore activity, C stays blocked forever.

You might think that adding one to wake count would fix this,
ie. waking one more thread than can successfully get the semaphore,
with the idea that the failing thread will then set sem to -1 to flag
that some threads are waiting.  That doesn't work though.  Add one
more thread to the example above, D, that like C is blocked.  When A
wakes two threads, B and C say, B might get the sem then release it
before C runs.  Then C won't wake up D.

[Bug libgomp/51249] semaphore implemetation for linux leaves threads blocked

[amodra at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51249

Alan Modra <amodra at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2011-11-21
         AssignedTo|unassigned at gcc dot       |amodra at gmail dot com
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #1 from Alan Modra <amodra at gmail dot com> 2011-11-21 03:07:04 UTC ---
What's more, the mutex implementation has a similar problem. 
libgomp/config/linux/mutex.c gomp_mutex_lock_slow uses a value of 2 in the
mutex to flag that threads are waiting on the mutex, similar to sem.c use of -1
in sem.  When two or more threads are waiting it is possible to clear the flag,
wake one thread but leave the other blocked forever.

[Bug libgomp/51249] semaphore implemetation for linux leaves threads blocked

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51249

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |rth at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-11-21 14:52:58 UTC ---
Can you please clarify why do you think mutex is problematic too?
When you do futex_wake in gomp_mutex_unlock_slow, you wake up one of the
threads that are already blocked (i.e. have called futex_wait in
gomp_mutex_lock_slow).
But once it calls futex_wait, it breaks the first loop and keeps setting the
mutex value to 2 rather than just 1.

As for gomp_sem_{wait,post}, I guess libgomp's sem.[ch] has been written based
on glibc before
http://sources.redhat.com/git/?p=glibc.git;a=patch;h=3d2dd6ca71fa9933e3413625d606f4b486661409
changes (we always want private in libgomp, so those parts are non-issue, but
the nwaiters maybe is).  I'll need to think about this more when I'm not so
sleepy.

[Bug libgomp/51249] semaphore implemetation for linux leaves threads blocked

[amodra at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51249

--- Comment #3 from Alan Modra <amodra at gmail dot com> 2011-11-21 22:21:13 UTC ---
Sorry, I misread the code.  Indeed, the mutex will be left at 2.

I'm chasing a frustratingly elusive locking bug.  Symptoms are that one or two
libgomp tests fail each gcc testsuite run, not always the same test.  log shows
a timeout, but I'm fairly certain it isn't a real timeout but one of the
threads blocking.  This used to happen before rth's recent locking changes. 
The difficulty is that I can't seem to reproduce the failure when running tests
by hand.

I have a rewrite of sem.c,h which adds a "wait" field to the struct and uses
atomics, and have rewritten a number of other files to use atomics rather than
the old __sync functions.  I just haven't been game to post my changes until I
track down the problem.

[Bug libgomp/51249] semaphore implemetation for linux leaves threads blocked

[amodra at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51249

--- Comment #4 from Alan Modra <amodra at gcc dot gnu.org> 2011-11-30 03:44:02 UTC ---
Author: amodra
Date: Wed Nov 30 03:43:57 2011
New Revision: 181831

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=181831
Log:
    PR libgomp/51249
    * config/linux/sem.h: Rewrite.
    * config/linux/sem.c: Rewrite.


Modified:
    trunk/libgomp/ChangeLog
    trunk/libgomp/config/linux/sem.c
    trunk/libgomp/config/linux/sem.h

[Bug libgomp/51249] semaphore implemetation for linux leaves threads blocked

[amodra at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51249

Alan Modra <amodra at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.7.0

--- Comment #5 from Alan Modra <amodra at gmail dot com> 2011-11-30 04:47:40 UTC ---
fixed