[Bug nptl/4979] New: pthread rwlock writer starvation - bad initializer, bad rdlock code

[Bug nptl/4979] New: pthread rwlock writer starvation - bad initializer, bad rdlock code

[bruce dot gayliard at hp dot com]

Thread model: posix
gcc version 4.1.1 20070105 (Red Hat 4.1.1-52)

[root@mctest1 ~]# uname -a
Linux mctest1.usa.hp.com 2.6.18-8.el5 #1 SMP Fri Jan 26 14:15:14 EST 2007 
x86_64 x86_64 x86_64 GNU/Linux

There are two bugs that cause the same errant behavior, both described below.

This is not a RedHat problem, I am merely using RedHat releases due to the 
systems that I have available and can observe, so though I use RHEL 4 and RHEL 
5 to describe the change in behavior, it is really the underlying delivered 
library versions that are at issue.  If I get a chance later, I will try to 
nail down the exact glibc version where the problems were introduced, but I do 
not have the time to do so now.

A "reader preferred" lock as it seems to be defined in NPTL code is in 
violation of the POSIX specification for most scheduling policies.  Yet some 
bugs, introduced apparently with 64 bit support, have caused this behavior to 
exhibit in a number of cases.  While I don't see a problem with providing the 
capability (reader preferred), I think it is wrong to have it as the default 
behavior.  Besides that, the "recursive" writer is treated as a "reader 
preferred" lock in the latest code.

A change was committed into NPTL that modified the thread initializer from 
(seen in RHEL4):
---------------------------------------------------
#if defined __USE_UNIX98 || defined __USE_XOPEN2K
# define PTHREAD_RWLOCK_INITIALIZER \
  { __LOCK_INITIALIZER, 0, NULL, NULL, NULL,                                  \
    PTHREAD_RWLOCK_DEFAULT_NP, PTHREAD_PROCESS_PRIVATE }
#endif
#ifdef __USE_GNU
# define PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP \
  { __LOCK_INITIALIZER, 0, NULL, NULL, NULL,                                  \
    PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP, PTHREAD_PROCESS_PRIVATE }
#endif
// .....
#if defined __USE_UNIX98 || defined __USE_XOPEN2K
enum
{
  PTHREAD_RWLOCK_PREFER_READER_NP,
  PTHREAD_RWLOCK_PREFER_WRITER_NP,
  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP,
  PTHREAD_RWLOCK_DEFAULT_NP = PTHREAD_RWLOCK_PREFER_WRITER_NP
};
#endif  /* Unix98 */
---------------------------------------------------

to this (seen in RHEL 5), changing default behavior to "reader preferred":
---------------------------------------------------
/* Read-write lock types.  */
#if defined __USE_UNIX98 || defined __USE_XOPEN2K
enum
{
  PTHREAD_RWLOCK_PREFER_READER_NP,
  PTHREAD_RWLOCK_PREFER_WRITER_NP,
  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP,
  PTHREAD_RWLOCK_DEFAULT_NP = PTHREAD_RWLOCK_PREFER_READER_NP
};

/* Read-write lock initializers.  */
# if __WORDSIZE == 64
#  define PTHREAD_RWLOCK_INITIALIZER \
  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } }
# else
#  define PTHREAD_RWLOCK_INITIALIZER \
  { { 0, 0, 0, 0, 0, 0, 0, 0 } }
# endif
# ifdef __USE_GNU
#  if __WORDSIZE == 64
#   define PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP \
  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,                                           \
      PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP } }
#  else
#   define PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP \
  { { 0, 0, 0, 0, 0, 0, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP, 0 } }
#  endif
# endif
#endif  /* Unix98 or XOpen2K */
---------------------------------------------------


As if that weren't bad enough, the code in pthread_rwlock_rdlock.c conspires 
with code in pthread_rwlock_init.c to force "reader preferred" behavior on 
some write locks ("recursive").  The initializer code compares an attribute 
against a particular lock kind and dumps the result in the lock structure:
---------------------------------------------------
int
__pthread_rwlock_init (rwlock, attr)
     pthread_rwlock_t *rwlock;
     const pthread_rwlockattr_t *attr;
{
  const struct pthread_rwlockattr *iattr;

  iattr = ((const struct pthread_rwlockattr *) attr) ?: &default_attr;

  rwlock->__data.__lock = 0;
  rwlock->__data.__flags
    = iattr->lockkind == PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP;
  rwlock->__data.__nr_readers = 0;
  rwlock->__data.__writer = 0;
  rwlock->__data.__readers_wakeup = 0;
  rwlock->__data.__writer_wakeup = 0;
  rwlock->__data.__nr_readers_queued = 0;
  rwlock->__data.__nr_writers_queued = 0;

  return 0;
}
---------------------------------------------------

Then, the pthread_rwlock_rdlock makes the following assertion:
---------------------------------------------------
  while (1)
    {
      /* Get the rwlock if there is no writer...  */
      if (rwlock->__data.__writer == 0
          /* ...and if either no writer is waiting or we prefer readers.  */
          && (!rwlock->__data.__nr_writers_queued
              || rwlock->__data.__flags == 0))
        {
---------------------------------------------------

Unfortunately, PTHREAD_RWLOCK_PREFER_WRITER_NP then behaves as "reader 
preferred" ... this is no good.


Both of the above bugs need to be repaired.  Here is a test program to display 
the behavior - output comes fast, so it may be easiest to pipe throug a grep 
for "write".  If "BUG" is defined, the writer starvation is shown.  If not, 
the PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP is explicitly initialized and 
the behavior is as it should be.  If you define BUG2 (leaving BUG undefined), 
you will reproduce "reader preferred" behavior with 
PTHREAD_RWLOCK_PREFER_WRITER_NP.

Yes - these are contrived examples, but you want to reproduce the bugs, 
right :-) .

--------------------------------------------------
#include <stdio.h>
#include <pthread.h>

#define BUG 1
// #define BUG2
// #define FILLTEST 1
// #define LOCKDUMP 1

long workercount = 4;
long writers = 1;
long workerid;

long writersleep = 0;
long readersleep = 0;
long spincount = 100000;
long spinout = 0;
long procsleep = 100000;

#ifdef BUG
pthread_rwlock_t mylock = PTHREAD_RWLOCK_INITIALIZER;
#else
pthread_rwlock_t mylock;
pthread_rwlockattr_t mylock_attr;
#endif


void *
lockdump (pthread_rwlock_t *thelock) {
    int *mptr = (int *) thelock;
    int i;
    for (i=0; i < (sizeof(pthread_rwlock_t) / 4); i++) {
        printf ("lock %x + %d = %x\n", (void *)thelock, i*4, *(mptr+i));
    }
}

void *
attrdump (pthread_rwlockattr_t *theattr) {
    int *mptr = (int *) theattr;
    int i;
    for (i=0; i < (sizeof(pthread_rwlockattr_t) / 4); i++) {
        printf ("attr %x + %d = %x\n", (void *)theattr, i*4, *(mptr+i));
    }
}

void *
lockclear (pthread_rwlock_t *thelock) {
    int *mptr = (int *) thelock;
    int i;
    for (i=0; i < (sizeof(pthread_rwlock_t) / 4); i++) {
        *(mptr+i) = 0;
    }
}

void *
attrclear (pthread_rwlockattr_t *theattr) {
    int *mptr = (int *) theattr;
    int i;
    for (i=0; i < (sizeof(pthread_rwlockattr_t) / 4); i++) {
        *(mptr+i) = 0;
    }
}

void *
lockfill (pthread_rwlock_t *thelock) {
    int *mptr = (int *) thelock;
    int i;
    for (i=0; i < (sizeof(pthread_rwlock_t) / 4); i++) {
        *(mptr+i) = 0xffffffff;
    }
}

void *
attrfill (pthread_rwlockattr_t *theattr) {
    int *mptr = (int *) theattr;
    int i;
    for (i=0; i < (sizeof(pthread_rwlockattr_t) / 4); i++) {
        *(mptr+i) = 0xffffffff;
    }
}

void *
reader (long workid, long rwtype) {
    while (1) {
        int spn = spincount, spc = spincount;
        // printf ("reader %d going for lock\n", workid);
        pthread_rwlock_rdlock(&mylock);
        while (spn != 0) { spn = spc--; }
        printf ("reader %d obtained the lock\n", workid);
#ifdef LOCKDUMP
    lockdump (&mylock);
#endif
        pthread_rwlock_unlock(&mylock);
        // printf ("reader %d released the lock at %d\n", workid, spc);
        spn = spinout, spc = spinout;
        while (spn != 0) { spn = spc--; }
#ifdef LOCKDUMP
    lockdump (&mylock);
#endif
        // printf ("reader %d going yield at %d\n", workid, spc);
        // pthread_yield();
        // usleep(readersleep);
    }
}

void *
writer (long workid, long rwtype) {
    while (1) {
        int spn = spincount, spc = spincount;
        printf ("writer %d going for lock\n", workid);
        pthread_rwlock_wrlock(&mylock);
#ifdef LOCKDUMP
    lockdump (&mylock);
#endif
        printf ("writer %d obtained the lock\n", workid);
        while (spn != 0) { spn = spc--; }
        pthread_rwlock_unlock(&mylock);
        printf ("writer %d released the lock at %d\n", workid, spc);
        spn = spinout, spc = spinout;
        while (spn != 0) { spn = spc--; }
#ifdef LOCKDUMP
    lockdump (&mylock);
#endif
        // printf ("writer %d going yield at %d\n", workid, spc);
        // pthread_yield();
        // usleep(writersleep);
    }
}

int
main () {

#ifdef FILLTEST
    printf ("size of lock struct is %d\n", sizeof(pthread_rwlock_t));
    printf ("address of lock struct is %x\n", &mylock);
    lockdump (&mylock);
    attrdump (&mylock_attr);
    lockfill (&mylock);
    attrfill (&mylock_attr);
    lockdump (&mylock);
    attrdump (&mylock_attr);
#endif

#ifndef BUG
    pthread_rwlockattr_init (&mylock_attr);
    pthread_rwlockattr_setkind_np (&mylock_attr,
#ifdef BUG2
                       PTHREAD_RWLOCK_PREFER_WRITER_NP);
#else                                  
                       PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
#endif
    pthread_rwlock_init(&mylock, &mylock_attr);
#endif
#ifdef LOCKDUMP
    printf ("lock has been initialized\n");
    lockdump (&mylock);
#endif

    pthread_t thrd[workercount];

    pthread_attr_t simple_attr;
    pthread_attr_init(&simple_attr);
    pthread_attr_setinheritsched(&simple_attr, PTHREAD_INHERIT_SCHED);

    long res;

    for (workerid = 0; workerid < writers; workerid++) {
        if (res = pthread_create(&thrd[workerid], &simple_attr,
                                 (void *)writer, (void *)workerid)) {
            printf ("failed to start worker %d, ret %d\n", workerid, res);
        }
    }
    for (workerid = 0; workerid < (workercount - writers); workerid++) {
        if (res = pthread_create(&thrd[workerid], &simple_attr,
                                 (void *)reader, (void *)workerid)) {
            printf ("failed to start worker %d, ret %d\n", workerid, res);
        }
    }
    sleep(procsleep);
}

-- 
           Summary: pthread rwlock writer starvation - bad initializer, bad
                    rdlock code
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P1
         Component: nptl
        AssignedTo: drepper at redhat dot com
        ReportedBy: bruce dot gayliard at hp dot com
                CC: glibc-bugs at sources dot redhat dot com


http://sourceware.org/bugzilla/show_bug.cgi?id=4979

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug nptl/4979] pthread rwlock writer starvation - bad initializer, bad rdlock code

[jakub at redhat dot com]

------- Additional Comments From jakub at redhat dot com  2007-09-19 13:58 -------
AFAIK POSIX just sais that implementations may favor writers over readers,
it doesn't say they must, so the choice of the default (or even the existance
of different rwlock policies) is implementation choice.
This default has never changed in NPTL, you are probably confused by using
LinuxThreads headers in earlier glibc versions.  LinuxThreads used to
default to PREFER_WRITER, but never so in NPTL.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=4979

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug nptl/4979] pthread rwlock writer starvation - bad initializer, bad rdlock code

[bruce dot gayliard at hp dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 4579 bytes --]


------- Additional Comments From bruce dot gayliard at hp dot com  2007-09-20 18:18 -------
Hmmm - this is the spec I am looking at:
--------------------------------------------
IEEE Std 1003.1™, 2004 Edition
The Open Group Technical Standard
Base Specifications, Issue 6
Includes IEEE Std 1003.1™-2001, IEEE Std 1003.1™-2001/Cor 1-2002
and IEEE Std 1003.1™-2001/Cor 2-2004
...
pthread_rwlock_rdlock( ) System Interfaces
35616 NAME
35617 pthread_rwlock_rdlock, pthread_rwlock_tryrdlock—lock a read-write lock 
object for reading
35618 SYNOPSIS
35619 THR #include <pthread.h>
35620 int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
35621 int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
35622
35623 DESCRIPTION
35624 The pthread_rwlock_rdlock( ) function shall apply a read lock to the 
read-write lock referenced by
35625 rwlock. The calling thread acquires the read lock if a writer does not 
hold the lock and there are
35626 no writers blocked on the lock.
35627 TPS If the Thread Execution Scheduling option is supported, and the 
threads involved in the lock are
35628 executing with the scheduling policies SCHED_FIFO or SCHED_RR, the 
calling thread shall not
35629 acquire the lock if a writer holds the lock or if writers of higher or 
equal priority are blocked on
35630 the lock; otherwise, the calling thread shall acquire the lock.
35631 TPS TSP If the Threads Execution Scheduling option is supported, and the 
threads involved in the lock
35632 are executing with the SCHED_SPORADIC scheduling policy, the calling 
thread shall not
35633 acquire the lock if a writer holds the lock or if writers of higher or 
equal priority are blocked on
35634 the lock; otherwise, the calling thread shall acquire the lock.
35635 If the Thread Execution Scheduling option is not supported, it is 
implementation-defined
35636 whether the calling thread acquires the lock when a writer does not hold 
the lock and there are
35637 writers blocked on the lock. If a writer holds the lock, the calling 
thread shall not acquire the
35638 read lock. If the read lock is not acquired, the calling thread shall 
block until it can acquire the
35639 lock. The calling thread may deadlock if at the time the call is made it 
holds a write lock.

-------------------------------------------------------------------

You could take the position that if a "reader preferred" lock was specified, 
that reader locks have priority.  However, as I stated in my original writeup, 
that should not be the default.  By the way, I did not see "may" in the above.

Please let me know if I am looking at the wrong specification.

I assume you are echoing my opinion that it is not an issue to provide 
the "reader preferred" capability, and I agree that the spec does not disallow 
that.  I will say that in 30 years of working with parallel / shared memory 
applications, I have never run across a situation where a "reader preferred" 
lock (as the behavior is referred to in the library code) would be desired.  
That opinion seems to be reflected in the language of the specification.

The code I am looking at comes from the following tree:
glibc-2.5-25.src.rpm
/usr/src/redhat/SOURCES/nptl/sysdeps/pthread/pthread.h
/usr/src/redhat/SOURCES/nptl/sysdeps/pthread/pthread_rwlock_rdlock.c
/usr/src/redhat/SOURCES/nptl/pthread_rwlock_init.c

It is in the pthread.h file supplied at the path above where the modification 
that I pointed out in the PTHREAD_RWLOCK_DEFAULT_NP had occurred - clearly a 
modification from writer preferred to reader preferred for the default.
Whether or not the prior RHEL4 version used nptl is actually moot - the fact 
of the matter is that there are bugs (as I reported) in the version of glibc 
that I mention above, and probably in a number of other versions as well.  The 
bugs can be readily reproduced with the supplied test program, which should be 
allowing writes to occur regardless of whether BUG1 or BUG2 is defined.

So, I assumed nptl was the correct place to report, based on the directory 
tree in which the code was found.  If this is in error, apologies - please let 
me know where I should enter this bug report.

Finally, I will re-iterate that I found this due to a failure of an 
application that was previously working (i.e. in RHEL4).  Some behavior, 
clearly, has changed in the transition to RHEL5.  The application code had not 
been changed.



-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=4979

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug nptl/4979] pthread rwlock writer starvation - bad initializer, bad rdlock code

[drepper at redhat dot com]

------- Additional Comments From drepper at redhat dot com  2007-09-20 18:31 -------
There is nothing wrong in the implementation and nothing will change.  If you
want reliable behavior then by all means, specify it.  This is what the
attributes are for.  If you don't use them stop complaining.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WORKSFORME


http://sourceware.org/bugzilla/show_bug.cgi?id=4979

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug nptl/4979] pthread rwlock writer starvation - bad initializer, bad rdlock code

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=4979

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com
              Flags|                            |security-

-- 
You are receiving this mail because:
You are on the CC list for the bug.