Sequence locks can be used in situations where a writer should get immediate access to a critical section even in the presence of multiple readers. Readers should realize that they have got inconsistent results because of a writer interfering, and they should be prepared to try reading again and again till they get consistent results. A writer should never interfere while another writer is active in the critical section. The code which implements this locking scheme is fairly simple and has been introduced as part of the 2.6 kernel.

Lets first look at a `toy' program which demonstrates the use sequence locks. We have a writer process which keeps incrementing a 32 bit counter implemented as two independent 16 bit counters. The idea is to increment the higher 16 bits if the lower 16 bits overflows from 0xffff to 0x0. A reader process keeps reading the two 16 bits counters and generates a 32 bit count value. At no point of time should the reader process get a count which was lower than the previous count. The maximum count in the two 16 bit counters taken together at any point of time will always be less than 0xffffffff.

Two problems can give inconsistent results. Say the current value of the count is 0x6FFFF (stored as 0xFFFF and 0x6 in the two independent counters). The writer changes 0xFFFF to 0x0, which the reader reads and records as the lower 16 bits of the count. Next, if the reader reads the higher 16 bits before the writer increments it, reader would get 0x6. So the combined value will be 0x60000 which is less than the previous count 0x6FFFF. The problems here is that the reader is interrupting the writer.

Another scenario. Say current total is 0x2FFFF. The reader reads the higher 16 bits and gets 0x2. Before the reader can sum this up with the lower 16 bits, the writer starts running and changes 0x2FFFF to 0x30000, 0x30001 etc. It is possible that the reader will run again only when the count becomes say 0x30006. At this point, the reader will get the lower 16 bits, 0x0006. Reader combines both parts and gets 0x20006 which is less than 0x2FFFF.

[Listing 12, kernel module demonstrating reader/writer problem]

Here is a user space test program:

[Listing 13]

In situations where there are only a few writers and many readers running concurrently, where a writer is so impatient that he is not prepared to wait for any of the readers, sequence locks can be employed effectively. Examples of usage can be found in kernel/timer.c.

We will modify our program to use seq locks - we shall then look at how these locks are implemented.

[Listing 14, Using sequence locks to solver reader-writer problem]

Now let's look at the kernel implementation of the sequence lock.

[Listing 15]


typedef struct {
        unsigned sequence;
        spinlock_t lock;

} seqlock_t;

#define SEQLOCK_UNLOCKED { 0, SPIN_LOCK_UNLOCKED }

static inline void 
write_seqlock(seqlock_t *sl)
{

        spin_lock(&sl->lock);
        ++sl->sequence;
        smp_wmb();                      
}       

static inline void 
write_sequnlock(seqlock_t *sl) 
{
        smp_wmb();
        sl->sequence++;
        spin_unlock(&sl->lock);
}

static inline unsigned 
read_seqbegin(const seqlock_t *sl)
{
        unsigned ret = sl->sequence;
        smp_rmb();
        return ret;
}

static inline int 
read_seqretry(const seqlock_t *sl, unsigned iv)
{
        smp_rmb();
        return (iv & 1) | (sl->sequence ^ iv);
}

We note that seqlock_t is a structure which contains a sequence number and a spin lock - the initial sequence number will be 0 and the spin lock will be in the unlocked state. A writer will always have to acquire this spinlock to enter the critical section - this guards against other writers. Once the writer enters the critical section, it increments the sequence number. Once the writer leaves the critical section, the sequence number gets incremented again and the lock is unlocked. The important point here is that while the writer is operating, the sequence number would be odd. No writer in the critical section means sequence number will be even. A reader enters the critical section without grabbing any lock. If it is lucky, it wont be interrupting any writer and no writer would interrupt it. How does the reader know that it has been lucky enough? Simple, before doing its critical section, the reader will save away the sequence number of the associated lock. Now, after the critical section is over, the reader will check for two things:

    Whether the saved sequence number was odd. If so, it means that the reader was running while a writer also was there in the critical section.
    Whether the saved sequence number and the current sequence number are the same. If not, it means that a writer had interrupted the reading process. 

If there has been no interruptions, the reader is happy with the value it has got - it's surely going to be a consistent value. Otherwise, the reader will redo the reading process till it gets a consistent result. The read_seqretry function is the heart of this technique. Its body looks like this:


return (iv & 1) | (sl->sequence ^ iv);

The first part checks whether iv, the old sequence number is even or odd. The second part checks whether the old and the new sequence numbers are identical. The smp_rmb, smp_wmb functions which you see in the code are to handle out of order loads and stores which I don't think Intel CPUs do - so those functions need not hinder your understanding of the code.