Read Write Spin Locks

Read/write spin locks have been introduced to increase the amount of concurrency inside the kernel. They allow several kernel control paths to simultaneously read the same data structure, as long as no kernel control path modifies it. If a kernel control path wishes to write to the structure, it must acquire the write version of the read/write lock, which grants exclusive access to the resource. Of course, allowing concurrent reads on data structures improves system performance.

Figure 5-2 illustrates two critical regions (C1 and C2) protected by read/write locks. Kernel control paths R0 and R1 are reading the data structures in C1 at the same time, while W0 is waiting to acquire the lock for writing. Kernel control path W1 is writing the data structures in C2, while both R2 and W2 are waiting to acquire the lock for reading and writing, respectively.

Figure 5-2. Read/write spin locks

Figure 5-2. Read/write spin locks

Spin Read Write

Each read/write spin lock is a rwlock_t structure; its lock field is a 32-bit field that encodes two distinct pieces of information:

• A 24-bit counter denoting the number of kernel control paths currently reading the protected data structure. The two's complement value of this counter is stored in bits

0-23 of the field.

• An unlock flag that is set when no kernel control path is reading or writing, and clear otherwise. This unlock flag is stored in bit 24 of the field.

Notice that the lock field stores the number 0x01000000 if the spin lock is idle (unlock flag set and no readers), the number 0x00000000 if it has been acquired for writing (unlock flag clear and no readers), and any number in the sequence 0x00ffffff, 0x00fffffe, and so on, if it has been acquired for reading by one, two, and more processes (unlock flag clear and the two's complement on 24 bits of the number of readers).

The rwlock_init macro initializes the lock field of a read/write spin lock to 0x01000000 (unlocked).

5.3.4.1 Getting and releasing a lock for reading

The read_lock macro, applied to the address rwlp of a read/write spin lock, essentially yields the following code:

movl $rwlp,%eax lock; subl $1,(%eax) jns 1f call _ _read_lock_failed

where _ _read_lock_failed( ) is the following assembly language function:

read lock failed: lock; incl (%eax) 1: cmpl $1,(%eax) js 1b lock; decl (%eax)

js read lock failed ret

The read_lock macro atomically decreases the spin lock value by 1, thus incrementing the number of readers. The spin lock is acquired if the decrement operation yields a nonnegative value; otherwise, the _ _read_lock_failed( ) function is invoked. The function atomically increments the lock field to undo the decrement operation performed by the read_lock macro, and then loops until the field becomes positive (greater than or equal to 1). Next, _ _read_lock_failed( ) tries to get the spin lock again (another kernel control path could acquire the spin lock for writing right after the cmpl instruction).

Releasing the read lock is quite simple because the read_unlock macro must simply increment the counter in the lock field to decrease the number of readers; thus, the macro yields the following assembly language instruction:

lock; incl rwlp

5.3.4.2 Getting and releasing a lock for writing

The write_lock function applied to the address rwlp of a read/write spin lock yields the following instructions:

movl $rwlp,%eax lock; subl $0x01000000,(%eax)

jz 1f call _ _write_lock_failed

where _ _write_lock_failed( ) is the following assembly language function:

write lock failed: lock; addl $0x01000000,(%eax) 1: cmpl $0x01000000,(%eax) jne 1b lock; subl $0x01000000,(%eax) jnz write lock failed ret

The write_lock macro atomically subtracts 0x01000000 from the spin lock value, thus clearing the unlock flag. The spin lock is acquired if the subtraction operation yields zero (no readers); otherwise, the _ _write_lock_failed( ) function is invoked. This function atomically adds 0x01000000 to the lock field to undo the subtraction operation performed by the write_lock macro, and then loops until the spin lock becomes idle (lock field equal to 0x01000000). Next, _ _write_lock_failed( ) tries to get the spin lock again (another kernel control path could acquire the spin lock right after the cmpl instruction).

Once again, releasing the write lock is much simpler because the write_unlock macro must simply set the unlock flag in the lock field. Thus, the macro yields the following assembly language instruction:

lock; addl $0x01000000,rwlp

Was this article helpful?

0 0

Post a comment