Threading From Scratch (#7) - RW Locks

RW Locks

A read-write lock protects a critical section by allowing multiple readers when there are no writers. We won't bother implementing lock attributes handling because we don't support process-shared locks (irrelevant in our case) and we don't let the user prefer readers (a non-POSIX extension). The implementation remembers the ID of the current writer if any. It also counts readers as well as the queued writers. We use two futexes, one to block the readers and one to block the writers.

A writer first bumps the number of queued writers. If there is no other writer and no readers, it marks itself as the owner of the lock and decrements the number of queued writers. It goes to sleep on the writer futex otherwise.

 1int tbthread_rwlock_wrlock(tbthread_rwlock_t *rwlock)
 2{
 3  int queued = 0;
 4  while(1) {
 5    tb_futex_lock(&rwlock->lock);
 6
 7    if(!queued) {
 8      queued = 1;
 9      ++rwlock->writers_queued;
10    }
11
12    if(!rwlock->writer && !rwlock->readers) {
13      rwlock->writer = tbthread_self();
14      --rwlock->writers_queued;
15      tb_futex_unlock(&rwlock->lock);
16      return 0;
17    }
18    int sleep_status = rwlock->wr_futex;
19
20    tb_futex_unlock(&rwlock->lock);
21
22    SYSCALL3(__NR_futex, &rwlock->wr_futex, FUTEX_WAIT, sleep_status);
23  }
24}

A reader acquires the lock if there are no writers at all. It goes to sleep on the reader futex otherwise.

 1int tbthread_rwlock_rdlock(tbthread_rwlock_t *rwlock)
 2{
 3  while(1) {
 4    tb_futex_lock(&rwlock->lock);
 5
 6    if(!rwlock->writer && !rwlock->writers_queued) {
 7      ++rwlock->readers;
 8      tb_futex_unlock(&rwlock->lock);
 9      return 0;
10    }
11    int sleep_status = rwlock->rd_futex;
12
13    tb_futex_unlock(&rwlock->lock);
14
15    SYSCALL3(__NR_futex, &rwlock->rd_futex, FUTEX_WAIT, sleep_status);
16  }
17}

When unlocking, we use the writer field to determine whether we were a reader or a writer. If we were a writer, we've had an exclusive ownership of the lock. Therefore, we need to either wake another writer or all of the readers, depending on the state of the counters. If we were a reader, we've had a non-exclusive lock. Therefore, we only need to wake a writer when we're the last reader and there is a writer queued. We bump the value of the futex because we want to handle the cases when FUTEX_WAKE was called before the other thread manged to call FUTEX_WAIT.

 1int tbthread_rwlock_unlock(tbthread_rwlock_t *rwlock)
 2{
 3  tb_futex_lock(&rwlock->lock);
 4  if(rwlock->writer) {
 5    rwlock->writer = 0;
 6    if(rwlock->writers_queued) {
 7      __sync_fetch_and_add(&rwlock->wr_futex, 1);
 8      SYSCALL3(__NR_futex, &rwlock->wr_futex, FUTEX_WAKE, 1);
 9    } else {
10      __sync_fetch_and_add(&rwlock->rd_futex, 1);
11      SYSCALL3(__NR_futex, &rwlock->rd_futex, FUTEX_WAKE, INT_MAX);
12    }
13    goto exit;
14  }
15
16  --rwlock->readers;
17  if(!rwlock->readers && rwlock->writers_queued) {
18    __sync_fetch_and_add(&rwlock->wr_futex, 1);
19    SYSCALL3(__NR_futex, &rwlock->wr_futex, FUTEX_WAKE, 1);
20  }
21
22exit:
23  tb_futex_unlock(&rwlock->lock);
24  return 0;
25}

See the full patch at GitHub.

If you like this kind of content, you can subscribe to my newsletter, follow me on Twitter, or subscribe to my RSS channel.

2016-03-09

Table of Contents

RW Locks