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

["bruce dot gayliard at hp dot com" <sourceware-bugzilla at sourceware dot org>]

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.