Overview

When implementing parallel programs, it is very common to have data structures which have a severe imbalance in how they are concurrently accessed (read from vs. written to).

Most of the time your shared data structures can be efficiently protected with a simple mutual-exclusion lock, "mutex" for short. Pthreads provides this primitive with the pthread_mutex_*() portion of the API.

When your design results in shared data that is often concurrently read, and occasionally written to, simple mutexes will be serializing your potentially parallel readers. This is especially true if the critical section is expected to have a long duration. Keep in mind the scheduler can preempt and stop running your thread with the lock held no matter how 'fast' your critical section appears in code, this depends on the scheduler / operating system being used.

A good example of a proper reader-writer lock use would be a large shared hash that occasionally has entries added or removed. But often has multiple threads reading from it to search for entries of interest.

Before searching the hash the code would acquire a "read lock" on a server_rwlock_t instance protecting the hash, this is done with the function server_rwlock_rlock(). For the duration of the search the rwlock will have an internal reader count set positive. Once the search has been completed the reader must release the "read lock" using server_rwlock_unlock().

Since the search code is only acquiring a "read lock" it has the potential to execute in parallel. The critical section is reduced to only the serialization needed to protect the internal server_rwlock_t counters. The only time this search code cannot potentially run is when the "write lock" is held. This will cause the acquisition of the "read lock" to block until the "write lock" has been released.

Before modifying the hash, the code would acquire a "write lock" on the same server_rwlock_t instance protecting the shared hash. This is done using the server_rwlock_wlock() function. For the duration of the modification (writing) the rwlock will have an intenal writer count set positive. Once the modification is completed the writer must release the "write lock" using server_rwlock_unlock(), same as a reader releases the "read lock".

When either the "read lock" or the "write lock" is released, the library decrements the respective internal reader or writer counter. When the counter has been decremented down to zero, a "free lock" condition variable is signaled internally. This will awake blocked acquisitions on the "read lock" or the "write lock", if any exist that is.

A new addition to ServerKit has been the ability to convert a held lock to either a "read lock" or a "write lock". In the example given above, where a "read lock" was acquired to search a hash, lets say after searching the hash you failed to locate the entry. Your routine is required to insert the entry after confirming it doesnt already exist in the hash.

This poses a problem, you acquired a "read lock" so that others could search the hash while you searched it in parallel. But now you are in an interesting position of having to modify the hash which you are not immediately permitted to do.

Previously, you would be required to unlock the reader-writer lock, and acquire a "write lock" using server_rwlock_wlock(). This would work just fine, except between your unlock and wlock, there is a window where another thread could acquire the "write lock" and modify the hash. A classic race condition. As a result of this possibility, you would have to do something to ensure your insert is still the result of a true condition (the searched for entry not being present).

There are a few ways you could achieve this, one which is to simply redo the search after acquiring the "write lock". Another would be to simply acquire a "write lock" on all searches that need to insert an entry when it doesnt exist.

Instead of forcing you to deal with this complex situation, the reader-writer locks have been made more flexible. Two functions, server_rwlock_r2wlock() and server_rwlock_w2rlock(), have been added which atomically convert a held "read lock" to a "write lock" and vice versa.

In the above example, instead of unlocking the "read lock" and then acquiring a "write lock" with a race, you simply call server_rwlock_r2wlock() on the reader-writer lock you already hold a "read lock" on. If the function returns 1, you will hold a "write lock" as if you called server_rwlock_wlock(). Whatever data condition was true before, requiring the "write lock" _will_ still be true. No "write lock" could possibly have been acquired since your search by anyone else. If the function returns 2 however, you will still hold the "write lock" but the different return value indicates that you were unable to atomically move from "read lock" to "write lock", and will have to assume conditions changed.

Making this possible does add some overhead to the reader-writer locks in general, but properly used the increased flexibility is welcome.

You must match all server_rwlock_[rw]lock() calls with a single call to server_rwlock_unlock(), protecting your critical section just like you would using Pthreads mutexes.

Note that GNU libc implements reader-writer locks as part of the Pthreads library. It is conditionally available based on the __USE_UNIX98 define, and you are free to use this instead of the ServerKit reader-writer locks. Note the ServerKit implementation features held-lock conversions which UNIX98 rwlocks don't have.