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
The frlock patch works by not blocking readers or writers at all. Code
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:
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.
to post comments)