LINUX KERNEL LOCKING

Some of them are:

  • seq_lock
  • RCU (Read-Copy-Update)

SEQ_LOCK:
==========
Seqlocks work in situations where the resource to be protected is small, simple, and frequently accessed, and where write access is rare but must be fast. Essentially, they work by allowing readers free access to the resource but requiring those readers to check for collisions with writers and, when such a collision happens, retry their access. Seqlocks generally cannot be used to protect data structures involving pointers, because the reader may be following a pointer that is invalid while the writer is changing the data structure.

How it works:
——————

  • Reader obtains sequence value before reading
  • Reader reads value
  • Readers compares obtained sequence value with current value
  • If there is mismatch, read access is retried
unsigned int seq;
do {
seq = read_seqbegin(&seq_lock);
/* Do what you need to do */
} while read_seqretry(&seq_lock, seq);

– Writers need to get seqlock before writing data. Writers can use below callbacks (as well as other variants based on requirements) to lock and unlock seqlock.

void write_seqlock(seqlock_t *lock);
void write_sequnlock(seqlock_t *lock);

If it is required to use seqlock from IRQ, IRQ-safe versions can be used.

unsigned int read_seqbegin_irqsave(seqlock_t *lock, unsigned long flags);
int read_seqretry_irqrestore(seqlock_t *lock, unsigned int seq, unsigned long flags);

References:
http://www.makelinux.net/ldd3/chp-5-sect-7

Read-Copy-Update:
================

Provides high performance when used at proper place:

  • There are many constrains on data structures which RCU can protect.
  • Optimized for situations where reads are common and writes are rare
  • The resources being protected should be accessed via pointer
  • All references to those resources must be held only by atomic code

When data structure need to be changed, writing thread makes a copy of current
data, changes data in copy and change the read pointer.

  • On the reader side,
    – rcu_read_lock();
    – data = dereference_data_using_rcu_callback(…);
    – do_something_with_data(data);
    – rcu_read_unlock();
  • On Write side,- allocate memory for new data
    – copy old data to new memory
    – update data in new memory
    – update rcu data pointer using rcu callback
    – register a RCU call for to free old data memory (Alternate is
    synchronize_rcu() but this will block thread until all readers are done)

How to make sure that all readers are done before freeling old memory:
————————————————————————————————

  1. This can be done using synchronize_rcu() callback which will block thread
    until all readers are done.
  2. call_rcu() through which a callback can be registered will be invoked after
    the completion of all RCU read-side critical sections that might be
    referencing that data item.

References:

http://www.rdrop.com/users/paulmck/rclock/intro/rclock_intro.html
http://www.rdrop.com/~paulmck/RCU/whatisRCU.html

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s