对LINUX内核各种锁的理解

自旋锁

自旋锁是内核中最基础的锁机制。
自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元持有，调用者就一直循环在那里看是否该自旋锁的持有者已经释放了锁，"自旋"一词就是因此而得名。
自旋锁适用于锁使用者保持锁时间比较短的情况。

使用自旋锁需要注意有可能造成的死锁情况:

1.     static DEFINE_SPINLOCK(xxx_lock);
   
2. 
   
3.     unsigned long flags;
   
4.     spin_lock_irqsave(&xxx_lock, flags);
   
5.     ... critical section here ..
   
6.     spin_unlock_irqrestore(&xxx_lock, flags);

代码中spin_lock_irqsave会禁止本地cpu中断的抢占。以上代码在任何情况下都是安全的。但问题是关中断的代价太大。
如果把spin_lock_irqsave/spin_unlock_irqrestore换成spin_lock/spin_unlock会有什么问题吗？
答案是，如果中断中调用了spin_lock，可能会引起死锁！
例如：

1. spin_lock(&lock);
   
2. ...
   
3.     <- interrupt comes in:
   
4.         spin_lock(&lock);

值得注意的是，如果产生中断的cpu和进程中调用spin_lock的cpu不是同一个，则不会有问题。这也是irq版本的spin_lock函数实现时只需要禁止本地cpu中断的原因。

结论：要想在进程中用spin_lock代替spin_lock_irqsave，条件是中断中不会使用相应的spin_lock

何时使用自旋锁？
不允许睡眠的上下文且临界区操作较短时使用自旋锁。

读写自旋锁

如果读写锁当前没有读者，也没有写者，那么写者可以立刻获得读写锁，否则它必须自旋在那里，直到没有任何写者或读者。如果读写锁没有写者，那么读者可以立即获得该读写锁，否则读者必须自旋在那里，直到写者释放该读写锁。
读写锁适合于对数据结构的读次数比写次数多得多的情况。

注意：读写锁需要比spinlocks更多的访问原子内存操作，如果读临界区不是很大，最好别使用读写锁。

读写锁代码：

点击(此处)折叠或打开

1. rwlock_t xxx_lock = __RW_LOCK_UNLOCKED(xxx_lock);
   
2. 
   
3.     unsigned long flags;
   
4. 
   
5.     read_lock_irqsave(&xxx_lock, flags);
   
6.     .. critical section that only reads the info ...
   
7.     read_unlock_irqrestore(&xxx_lock, flags);
   
8. 
   
9.     write_lock_irqsave(&xxx_lock, flags);
   
10.     .. read and write exclusive access to the info ...
    
11.     write_unlock_irqrestore(&xxx_lock, flags);

读写锁比较适合链表等数据结构，特别是查找远多于修改的情况。

另外，可以灵活的使用read-write和irq版本的自旋锁。例如，如果中断中只是用了读锁，进程中就可以使用non-irq版本的读锁和irq版本的写锁。

注意：RCU比读写锁更适合遍历list，但需要更关注细节。目前kernel社区正在努力用RCU代替读写锁。

信号量

semaphore和spin lock的区别是semaphore会引起睡眠。
查看semaphore的数据结构可以发现，semaphore除了拥有spinlock，还有一个计数器和一个等待队列。当某个进程获取信号量的count值小于等于0时，被添加到wait_list中。

1. struct semaphore {
   
2.         raw_spinlock_t lock;
   
3.         unsigned int count;
   
4.         struct list_head wait_list;
   
5. };

何时使用semaphore？
允许睡眠的上下文、临界区操作较长、计数值大于1时使用semaphore

信号量也有读写信号量，在此略过。

mutex

mutex可以理解成计数值只有0和1的semaphore

既然有了semaphore，内核为何还需要mutex？
因为内核中对二值信号量的需求很大，单独提供一个mutex更利于代码编写和清晰度。

mutex缺点：
为了实现某些性能上的优化，mutex数据结构比semaphore更大（这已经违背了mutex刚设计时的意愿），这也会消耗更多的CPU cache和memory footprint.

何时使用mutex？
允许睡眠的上下文、临界区操作较长、计数值只为0或1时使用mutex
kernel文档建议，在任何需要加锁且mutex可以满足需求的情况都应该使用mutex而不是其他锁。

RCU

RCU(Read-Copy Update)即读-拷贝，更新。对于用RCU保护的资源，读者不需要任何等待，而写者访问它时，需要先拷贝一个副本，然后对副本修改，最后在适当的时机把指向原来数据的指针指向新的数据。这个“适当的时机”指的是没有任何读者操作该资源时。

RCU相关API：

1. rcu_read_lock()
   
2. 读者进入临界区
   
3. rcu_read_unlock()
   
4. 读者退出临界区
   
5. synchronize_rcu()
   
6. 由写者调用，当读者都退出老更新前的临界区后，写者才可以返回该函数。
   
7. call_rcu()
   
8. 由写者调用，但不阻塞。该函数的参数中有一个回调函数，当读者都退出更新前的临界区后，调用该回调函数。
   
9. rcu_assign_pointer()
   
10. 给临界区资源赋新值
    
11. rcu_dereference()
    
12. 使用临界区资源

RCU 写者的典型流程：
1. 拷贝一份临界区资源，此时有两份临界区资源，这里称为老资源和新资源
2. 用新资源代替老资源，使得之后的读者访问的是新资源
3. 等待读取老临界区的读者全部退出
4. 此时，老资源已没有读者操作，释放该资源

内核提供了对list,hlist等常用数据结构的RCU版本。对于RCU，对共享数据的操作必须保证能够被没有使用同步机制的读者看到，所以内存栅是非常必要的。内存栅只在alpha架构上才使用。

RCU代替读写锁：

点击(此处)折叠或打开

1.     @@ -13,15 +14,15 @@
   
2.         struct list_head *lp;
   
3.         struct el *p;
   
4. 
   
5.     -    read_lock();
   
6.     -    list_for_each_entry(p, head, lp) {
   
7.     +    rcu_read_lock();
   
8.     +    list_for_each_entry_rcu(p, head, lp) {
   
9.             if (p->key == key) {
   
10.                 *result = p->data;
    
11.     -            read_unlock();
    
12.     +            rcu_read_unlock();
    
13.                 return 1;
    
14.             }
    
15.         }
    
16.     -    read_unlock();
    
17.     +    rcu_read_unlock();
    
18.         return 0;
    
19.      }
    
20. 
    
21.     @@ -29,15 +30,16 @@
    
22.      {
    
23.         struct el *p;
    
24. 
    
25.     -    write_lock(&listmutex);
    
26.     +    spin_lock(&listmutex);
    
27.         list_for_each_entry(p, head, lp) {
    
28.             if (p->key == key) {
    
29.     -            list_del(&p->list);
    
30.     -            write_unlock(&listmutex);
    
31.     +            list_del_rcu(&p->list);
    
32.     +            spin_unlock(&listmutex);
    
33.     +            synchronize_rcu();
    
34.                 kfree(p);
    
35.                 return 1;
    
36.             }
    
37.         }
    
38.     -    write_unlock(&listmutex);
    
39.     +    spin_unlock(&listmutex);
    
40.         return 0;
    
41.      }

用RCU保护数据结构:

点击(此处)折叠或打开

1.     struct foo {
   
2.         int a;
   
3.         char b;
   
4.         long c;
   
5.     };
   
6.     DEFINE_SPINLOCK(foo_mutex);
   
7. 
   
8.     struct foo *gbl_foo;
   
9. 
   
10.     /*
    
11.      * Create a new struct foo that is the same as the one currently
    
12.      * pointed to by gbl_foo, except that field "a" is replaced
    
13.      * with "new_a". Points gbl_foo to the new structure, and
    
14.      * frees up the old structure after a grace period.
    
15.      *
    
16.      * Uses rcu_assign_pointer() to ensure that concurrent readers
    
17.      * see the initialized version of the new structure.
    
18.      *
    
19.      * Uses synchronize_rcu() to ensure that any readers that might
    
20.      * have references to the old structure complete before freeing
    
21.      * the old structure.
    
22.      */
    
23.     void foo_update_a(int new_a)
    
24.     {
    
25.         struct foo *new_fp;
    
26.         struct foo *old_fp;
    
27. 
    
28.         new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
    
29.         spin_lock(&foo_mutex);
    
30.         old_fp = gbl_foo;
    
31.         *new_fp = *old_fp;
    
32.         new_fp->a = new_a;
    
33.         rcu_assign_pointer(gbl_foo, new_fp);
    
34.         spin_unlock(&foo_mutex);
    
35.         synchronize_rcu();
    
36.         kfree(old_fp);
    
37.     }
    
38. 
    
39.     /*
    
40.      * Return the value of field "a" of the current gbl_foo
    
41.      * structure. Use rcu_read_lock() and rcu_read_unlock()
    
42.      * to ensure that the structure does not get deleted out
    
43.      * from under us, and use rcu_dereference() to ensure that
    
44.      * we see the initialized version of the structure (important
    
45.      * for DEC Alpha and for people reading the code).
    
46.      */
    
47.     int foo_get_a(void)
    
48.     {
    
49.         int retval;
    
50. 
    
51.         rcu_read_lock();
    
52.         retval = rcu_dereference(gbl_foo)->a;
    
53.         rcu_read_unlock();
    
54.         return retval;
    
55.     }

以下是写者不阻塞的代码：

点击(此处)折叠或打开

1.     struct foo {
   
2.         int a;
   
3.         char b;
   
4.         long c;
   
5.         struct rcu_head rcu;
   
6.     };
   
7. 
   
8.     /*
   
9.      * Create a new struct foo that is the same as the one currently
   
10.      * pointed to by gbl_foo, except that field "a" is replaced
    
11.      * with "new_a". Points gbl_foo to the new structure, and
    
12.      * frees up the old structure after a grace period.
    
13.      *
    
14.      * Uses rcu_assign_pointer() to ensure that concurrent readers
    
15.      * see the initialized version of the new structure.
    
16.      *
    
17.      * Uses call_rcu() to ensure that any readers that might have
    
18.      * references to the old structure complete before freeing the
    
19.      * old structure.
    
20.      */
    
21.     void foo_update_a(int new_a)
    
22.     {
    
23.         struct foo *new_fp;
    
24.         struct foo *old_fp;
    
25. 
    
26.         new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
    
27.         spin_lock(&foo_mutex);
    
28.         old_fp = gbl_foo;
    
29.         *new_fp = *old_fp;
    
30.         new_fp->a = new_a;
    
31.         rcu_assign_pointer(gbl_foo, new_fp);
    
32.         spin_unlock(&foo_mutex);
    
33.         call_rcu(&old_fp->rcu, foo_reclaim);
    
34.     }
    
35. 
    
36.     void foo_reclaim(struct rcu_head *rp)
    
37.     {
    
38.         struct foo *fp = container_of(rp, struct foo, rcu);
    
39. 
    
40.         foo_cleanup(fp->a);
    
41. 
    
42.         kfree(fp);
    
43.     }

何时使用RCU？
读操作远多于写操作、且写操作不是特别紧急时使用RCU

顺序锁

顺序锁为写者赋予更高的优先级，写者永远不会等待读者。缺点是读者有时不得不读多次数据以获取正确的结果。
顺序锁的数据结构中除了有spinlock外，还有一个顺序号。如果成功获得锁，顺序锁的顺序号会加1，以便读者能够检查出是否在读期间有写者访问过。读者在读取数据前后两次读顺序值，如果两次值不相同，则说明读取期间有新的写者操作过数据了，那么本次读取就是无效的。

典型使用：
读端：

1. do {
   
2.     seqnum = read_seqbegin(&seqlock_a);
   
3.     //读操作代码块
   
4.     ...
   
5. } while (read_seqretry(&seqlock_a, seqnum));

写端：

1.     spin_lock(&lock);
   
2.     write_seqlock(&seqlock_a)
   
3.     ...
4.    write_sequnlock(&seqlock_a)
   
5.     spin_unlock(&lock);

写者通过调用write_seqlock()和write_sequnlock()获取和释放顺序锁。write_seqlock()函数获取seqlock_t数据结构中的自旋锁，然后使顺序计数器sequence加1；write_sequnlock()函数再次增加顺序计数器sequence，然后释放自旋锁。这样可以保证写者在整个写的过程中，计数器sequence的值是奇数，并且当没有写者在改变数据的时候，计数器的值是偶数。
read_seqbegin()返回顺序锁的当前顺序号；如果局部变量seq的值是奇数（写者在read_seqbegin()函数被调用后，正更新数据结构），或seq的值与顺序锁的顺序计数器的当前值不匹配（当读者正执行临界区代码时，写者开始工作），read_seqretry()就返回1，说明本次读取失败，需要重新读取 。

并不是每一种资源都可以使用顺序锁来保护。一般来说，必须在满足下述条件时才能使用顺序锁：
1. 读者的临界区资源不包括被写者修改和被读者取值的指针，否则，写者有可能使指针失效，读者读取时会产生OPPs。
2. 读者的临界区代码没有副作用。

何时使用顺序锁？
读操作远多于写操作、且写操作很紧急时使用顺序锁。

小结

本文对Linux内核的多种锁的同步机制进行了分析对比，如有疏漏或错误，请各位不吝指正。