Fast reader/writer locks

The Linux kernel contains a number of primitives for controlling mutual exclusion. Semaphores and spinlocks (in several varieties) have been around for a while, and the read-copy-update mechanism was added in the 2.5 series. Yet another mechanism, called "fast reader/writer locks," has found its way into Andrew Morton's -mm patch set, and appears likely to be forwarded on to Linus soon for inclusion. So this seems like as good a time as any to look at how "frlocks" work.

Frlocks, as implemented by Stephen Hemminger, are aimed at solving a couple of problems with the gettimeofday() system call. One is simple performance; gettimeofday() is not particularly slow, but some applications (including anything using the X Window System) call it frequently. It also turns out that the current implementation, which uses reader/writer spinlocks, is susceptible to a denial of service problem. Frequent calls to gettimeofday() can delay or lock out timer tick updates.

The frlock patch works by not blocking readers or writers at all. Code wishing write access to the protected data structure is given that access immediately (at least, in the absence of other writers), so there is no way that time updates can be blocked or delayed. Readers, too, get immediate access to the data structure. The catch is that readers must be prepared to retry the access if collides with a writer for access to the data.

The lock works by maintaining "pre" and "post" sequence numbers. A writer process does the following:

• Take out a spinlock associated with the frlock
• Increment the "pre" sequence
• Mess around with the data structure
• Increment the "post" sequence
• Release the spinlock

Readers do something like the following:

• Remember the lock's "post" sequence number
• Grab the data of interest
• Ensure that the lock's "pre" sequence matches the remembered "post" sequence. If not, go back to the beginning.

In other words, as long as the sequence numbers match, the reader knows that no writer changed the data while the reader was doing its thing. In practice, the reader side tends to be expressed in code like:

	do {
		seq = fr_read_begin(&some_lock);
		/* Copy the data */
	} while (seq != fr_read_end(&some_lock));

Frlocks, clearly, will not be suitable for lengthy calculations, or those which have immediate side effects. In cases where a small data structure is changed infrequently but read often, however, frlocks may be the key to improved performance. In the introduction to the latest set of frlock patches, Stephen claims an 18% improvement in the speed of gettimeofday() - and the elimination of the timer tick lockout problem.

---

(Log in to post comments)

do {
   while((seq = fr_read_seq(&some_lock)) & 1);
   /* copy data */
} while (seq != fr_read_seq(&some_lock));