The Big Reader Lock

Read/write spin locks are useful for data structures that are accessed by many readers and a few writers. They are more convenient than normal spin locks because they allow several readers to concurrently access the protected data structure. However, any time a CPU acquires a read/write spin lock, the counter in rwlock_t must be updated. A further access to the rwlock_t data structure performed by another CPU incurs in a significant performance penalty because the hardware caches of the two processors must be synchronized. Even worse, the new CPU changes the rwlock_t data structure, so the cache of the former CPU becomes invalid and there is another performance penalty when the former CPU releases the lock. In short, reader CPUs are playing ping-pong with the cache line containing the read/write spin lock data structure.

A special type of read/write spin locks, named big reader read/write spin locks, was designed to address this problem. The idea is to split the "reader" portion of the lock across all CPUs, so that each per-CPU data structure lies in its own line of the hardware caches. Readers do not need to stomp one another, so no reader CPU "snoops" the reader lock of another CPU. Conversely, the "writer" portion of the lock is common to all CPUs because

The__brlock_array array stores the "reader" portions of the big reader read/write spin locks; for every such lock, and for every CPU in the system, the array includes a lock flag, which is set to 1 when the lock is closed for reading by the corresponding CPU. Conversely, the _ _br_write_locks array stores the "writer" portions of the big reader spin locks — that is, a normal spin lock that is set when the big reader spin lock has been acquired for writing.

The br_read_lock( ) function acquires the spin lock for reading. It just sets the lock flag in _ _brlock_array corresponding to the executing CPU and the big reader spin lock to 1, and then waits until the spin lock in _ _br_write_locks is open. Conversely, the br_read_unlock( ) function simply clears the lock flag in _brlock_array.

The br_write_lock( ) function acquires the spin lock for writing. It invokes spin_lock to get the spin lock in _ _br_write_locks corresponding to the big reader spin lock, and then checks that all lock flags in _ _brlock_array corresponding to the big reader lock are cleared; if not, it releases the spin lock in _ _br_write_locks and starts again. The br_write_unlock( ) function simply invokes spin_unlock to release the spin lock in _ br write locks.

As you may notice, acquiring an open big reader spin lock for reading is really fast, but acquiring it for writing is very slow because the CPU must acquire a spin lock and check several lock flags. Thus, big reader spin locks are rarely used. On the Intel architecture, there is just one big reader spin lock, used in the networking code.

Continue reading here: Semaphores

Was this article helpful?

+1 0