What's the best linux kernel locking mechanism for a specific scenario

Question

I need to solve a locking problem for this scenario:

1. A multi CPU system.
2. All of the CPU's use a common (software) resource.
3. Read only access to the resource is very common. (Processing of incoming network packets)
4. Write access is a lot less frequent. (Pretty much configuration changes only).

Currently I use the read_lock_bh, write_lock_bh (spinlocks) mechanism. The problem is that the more CPU's, the more I get soft lockups in a writer context.

I read the concurrency chapter in this book, But couldn't quite understand whether the reader or the writer will get priority when using spin locks.

So the questions are:

1. Does the Linux spinlock mechanism give priority the reader/writer/none of them?
2. Is there a better mechanism I can use in order to avoid those soft lockups in my scenario, or maybe a way for me to give priority to the writer whenever it tries to obtain the lock, while using my current solution?

Thanks, Nir

Answer 1

Isn't this the sort of usage case RCU is designed to handle? See http://lwn.net/Articles/262464/ for a good write up on it's use.

Answer 2

Here's a direct quote from Essential Linux Device Drivers which might be what you're looking for. It seems the part dealing with RCU at the end may be what you're interested in.

Reader-Writer Locks

Another specialized concurrency regulation mechanism is a reader-writer variant of spinlocks. If the usage of a critical section is such that separate threads either read from or write to a shared data structure, but don't do both, these locks are a natural fit. Multiple reader threads are allowed inside a critical region simultaneously. Reader spinlocks are defined as follows:

rwlock_t myrwlock = RW_LOCK_UNLOCKED;

read_lock(&myrwlock);             /* Acquire reader lock */
/* ... Critical Region ... */
read_unlock(&myrwlock);           /* Release lock */

However, if a writer thread enters a critical section, other reader or writer threads are not allowed inside. To use writer spinlocks, you would write this:

rwlock_t myrwlock = RW_LOCK_UNLOCKED;

write_lock(&myrwlock);            /* Acquire writer lock */
/* ... Critical Region ... */
write_unlock(&myrwlock); /* Release lock */

Look at the IPX routing code present in net/ipx/ipx_route.c for a real-life example of a reader-writer spinlock. A reader-writer lock called ipx_routes_lock protects the IPX routing table from simultaneous access. Threads that need to look up the routing table to forward packets request reader locks. Threads that need to add or delete entries from the routing table acquire writer locks. This improves performance because there are usually far more instances of routing table lookups than routing table updates.

Like regular spinlocks, reader-writer locks also have corresponding irq variants—namely, read_lock_irqsave(), read_lock_irqrestore(), write_lock_irqsave(), and write_lock_irqrestore(). The semantics of these functions are similar to those of regular spinlocks.

Sequence locks or seqlocks, introduced in the 2.6 kernel, are reader-writer locks where writers are favored over readers. This is useful if write operations on a variable far outnumber read accesses. An example is the jiffies_64 variable discussed earlier in this chapter. Writer threads do not wait for readers who may be inside a critical section. Because of this, reader threads may discover that their entry inside a critical section has failed and may need to retry:

u64 get_jiffies_64(void) /* Defined in kernel/time.c */
{
   unsigned long seq;
   u64 ret;
   do {
      seq = read_seqbegin(&xtime_lock);
      ret = jiffies_64;
   } while (read_seqretry(&xtime_lock, seq));
   return ret;
}

Writers protect critical regions using write_seqlock() and write_sequnlock().

The 2.6 kernel introduced another mechanism called Read-Copy Update (RCU), which yields improved performance when readers far outnumber writers. The basic idea is that reader threads can execute without locking. Writer threads are more complex. They perform update operations on a copy of the data structure and replace the pointer that readers see. The original copy is maintained until the next context switch on all CPUs to ensure completion of all ongoing read operations. Be aware that using RCU is more involved than using the primitives discussed thus far and should be used only if you are sure that it's the right tool for the job. RCU data structures and interface functions are defined in include/linux/rcupdate.h. There is ample documentation in Documentation/RCU/*.

For an RCU usage example, look at fs/dcache.c. On Linux, each file is associated with directory entry information (stored in a structure called dentry), metadata information (stored in an inode), and actual data (stored in data blocks). Each time you operate on a file, the components in the file path are parsed, and the corresponding dentries are obtained. The dentries are kept cached in a data structure called the dcache, to speed up future operations. At any time, the number of dcache lookups is much more than dcache updates, so references to the dcache are protected using RCU primitives.