nptl/DESIGN-rwlock.txt

   1 Reader Writer Locks pseudocode
   2 ==============================
   3
   4         pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
   5         pthread_rwlock_unlock(pthread_rwlock_t *rwlock);
   6         pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
   7
   8 struct pthread_rwlock_t {
   9
  10    unsigned int lock:
  11          - internal mutex
  12
  13    unsigned int writers_preferred;
  14          - locking mode: 0 recursive, readers preferred
  15                          1 nonrecursive, writers preferred
  16
  17    unsigned int readers;
  18          - number of read-only references various threads have
  19
  20    pthread_t writer;
  21          - descriptor of the writer or 0
  22
  23    unsigned int readers_wakeup;
  24          - 'all readers should wake up' futex.
  25
  26    unsigned int writer_wakeup;
  27          - 'one writer should wake up' futex.
  28
  29    unsigned int nr_readers_queued;
  30          - number of readers queued up.
  31
  32    unsigned int nr_writers_queued;
  33          - number of writers queued up.
  34 }
  35
  36 pthread_rwlock_rdlock(pthread_rwlock_t *rwlock)
  37 {
  38   lll_lock(rwlock->lock);
  39   for (;;) {
  40     if (!rwlock->writer && (!rwlock->nr_writers_queued ||
  41                                         !rwlock->writers_preferred))
  42         break;
  43
  44     rwlock->nr_readers_queued++;
  45     val = rwlock->readers_wakeup;
  46     lll_unlock(rwlock->lock);
  47
  48     futex_wait(&rwlock->readers_wakeup, val)
  49
  50     lll_lock(rwlock->lock);
  51     rwlock->nr_readers_queued--;
  52   }
  53   rwlock->readers++;
  54   lll_unlock(rwlock->lock);
  55 }
  56
  57 pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock)
  58 {
  59   int result = EBUSY;
  60   lll_lock(rwlock->lock);
  61   if (!rwlock->writer && (!rwlock->nr_writers_queued ||
  62                                         !rwlock->writers_preferred))
  63     rwlock->readers++;
  64   lll_unlock(rwlock->lock);
  65   return result;
  66 }
  67
  68 pthread_rwlock_wrlock(pthread_rwlock_t *rwlock)
  69 {
  70   lll_lock(rwlock->lock);
  71   for (;;) {
  72     if (!rwlock->writer && !rwlock->readers)
  73        break;
  74
  75     rwlock->nr_writers_queued++;
  76     val = rwlock->writer_wakeup;
  77     lll_unlock(rwlock->lock);
  78
  79     futex_wait(&rwlock->writer_wakeup, val);
  80
  81     lll_lock(rwlock->lock);
  82     rwlock->nr_writers_queued--;
  83   }
  84   rwlock->writer = pthread_self();
  85   lll_unlock(rwlock->lock);
  86 }
  87
  88 pthread_rwlock_unlock(pthread_rwlock_t *rwlock)
  89 {
  90   lll_lock(rwlock->lock);
  91
  92   if (rwlock->writer)
  93     rwlock->writer = 0;
  94   else
  95     rwlock->readers--;
  96
  97   if (!rwlock->readers) {
  98     if (rwlock->nr_writers_queued) {
  99       ++rwlock->writer_wakeup;
 100       lll_unlock(rwlock->lock);
 101       futex_wake(&rwlock->writer_wakeup, 1);
 102       return;
 103     } else
 104       if (rwlock->nr_readers_queued) {
 105         ++rwlock->readers_wakeup;
 106         lll_unlock(rwlock->lock);
 107         futex_wake(&rwlock->readers_wakeup, MAX_INT);
 108         return;
 109       }
 110   }
 111
 112   lll_unlock(rwlock->lock);
 113 }