Linux内核中的rwlock以及IGMP中读锁的重入。

Cyberman.Wu

Linux内核中的rwlock有没有具体的设计原则？一般读写锁基本原则是读可以共享，而写互斥，但读写之间互斥具体是什么样好像并没有很明确的规定吧？简单的就是：
1. 如果当前没有锁定，read lock和write lock均能成功。
2. 如果当前是read lock，那么新来的read lock就可以成功，而write lock就等待。
3. 如果当前是write lock，所有新来的锁都等待。

而这种简单设计会导致一个问题，就是如果频繁地发起read lock，则write lock有可能会被“饿死”。所以在许多大量写很少量写的场景，例如数据库中，往往会优先读锁，一旦有写锁等待读锁，则后面再发起的读锁会被“阻塞”。

目前在Linux内核中多数rwlock都是前面一种设计，但TILEPro平台上则采用了优先写锁的设计（这个平台已经合入到最新的2.6.36中，具体参见arch/tile/lib/spinlock_32.c文件）。这两种设计有一个差异，是前面的一种设计可以支持读锁的“重入”，而后者是有风险的：如果在两次获取read lock之间，另一个核试图获取write lock，则就会发生死锁。
在内核中，IGMP的timer中发送IGMP message时有可能会在已经获取read lock的情况下再次获取read lock，不知道这个是IGMP设计上没有考虑周全的一个地方，还是Linux中的锁本来就是按前面一种要求的？

另外IGMP中的timer会在每一个调用join/leave的核上启动，但它们都处理同一个共享数据，感觉这个地方是不是对于SMP考虑并不全，应该是一个可以优化的地方？


对于spinlock，在核比较多例如超过100个的时候，一直测试一个内存值会导致比较多的访问冲突，是不是还不如获取冲突的时候简单地“等待”一个随机值再试，就好像以前半双工网络中的冲突检测一样？

smalloc

回复 1# Cyberman.Wu


    >>IGMP的timer中发送IGMP message时有可能会在已经获取read lock的情况下再次获取read lock.

好象中断中几乎没有读写锁这种要求,如果有那也是相当罕见
大部分用在进程和软中断中.
发生递归的情况下确实死锁,在你说的2种设计中前一种对于"自旋"锁也是本处理器不可重入.
仔细看下这帖子会发现一个是软中断一个是进程时递归在设计上应该是被避免的,2个软中断情况也一样,和中间是否插入写没关系.
http://linux.chinaunix.net/bbs/thread-1169235-1-1.html

剩下的就是2个进程情况.但是读写锁是一种自旋锁,在获得锁的时候是"应该"禁止内核抢占的,所以死锁也不会发生----这个待验证

如果IGMP中真如你说的那样.2次获得读锁出现在同一个软中断中.那么应该就是设计上的BUG
LZ可不可以具体说明下在哪里发生?
如果真是如此,按第2种设计仅仅需要保证读锁本处理器不重入就可以了

另 >>例如数据库中，往往会优先读锁，一旦有写锁等待读锁，则后面再发起的读锁会被“阻塞”。
这句话感觉有点说不通.如果按后面的说法读优先好象说不过去...只能说这是一种层次锁...是否是优先写锁的笔误?

smalloc

>>是不是还不如获取冲突的时候简单地“等待”一个随机值再试
这个好象没什么意义.这要看你如何等待了.如果只是在一边自己while 1啥事情也不做,和自旋一样玩.还没自旋利用率高呢。 如果想做其他事情,可以考虑类似 spintrylock的形式
如果共享数据访问不是占用太多时间.多个等待同时发生也概率比较小的情况下 还是不用变动设计

Cyberman.Wu

>>是不是还不如获取冲突的时候简单地“等待”一个随机值再试
这个好象没什么意义.这要看你如何等待了.如果 ...
smalloc 发表于 2010-11-11 23:37

核少的时候一样，而核多的时候未必就相同，因为锁测试的必须是一个cache coherent的内存值，而且必然产生修改，如果集中在一个时间内大规模访问，可能会导致冲突比较严重。后面随着核的增加，以后分布式cache有可能会成为主流，此时cache的读写一致性会是比较有挑战的一件事。

Cyberman.Wu

回复 2# smalloc


中断中很少会有写锁，但是有可能会有读锁。内核代码我看得也不多，至少在IGMP中是有的。进程之间的话实现上最终调用到内核态也不算是一种抢占，因为可以是运行在不同的核上面的。目前的内核并不是一个大锁了吧，至少我这个死锁问题出现的时候，许多其它核是阻塞在ip_mc_join_group或ip_mc_leave_group中rtnl_lock()的调用上，已经在内核核了。

IGMP协议实现中join/leave的系统调用并不会直接产生IGMP消息，而是处理一个共享的数据结构并启动一个timer，发送消息是在时钟中断的下半部分中通过如下调用完成的：
igmp_ifc_timer_expire() -> igmpv3_send_cr() -> igmpv3_sendpack()

igmpv3_send_cr() 中会先read_lock()，然后申请一个sk_buff调用add_grec()生成sk_buff中的数据，然后read_unlock()并调用igmpv3_sendpack()发送消息。但如果有大量的join/leave产生的时候，在add_grec()中可以会把已经填写满的消息发送然后重新申请一个继续填写，而发送过程中：
__mkroute_output() -> ip_check_mc()
调用中会再次read_lock()/read_unlock()相关的锁（mc_list_lock），从而在一个调用链上两次调用read_lock()。在正常情况下因为读锁是共享锁，所以这里执行是成功的。
但如果在第一次获取读锁成功之后、第二次获取读锁之前，另一个核上面调用了join/leave的操作，并且运行到获取写锁的地方，情况就有变化了：
1. 对于x86/PowerPC/ARM等平台，因为有读锁定之后写锁是简单的等待，所以第二次获取读锁仍然成功，然后一直到第一次的读锁也释放掉，写锁获取成功并完成join/leave的操作。
2. 对于TILEPro平台上，因为“优先”了写锁，当写锁等待的时候，它同时会“阻塞”后续发起的读锁，那么在timer中ip_check_mc()就会和进程中的join/leave产生死锁。

这里究竟是协议栈设计时考虑得不周全，还是rwlock设计上的缺陷不是很容易说清楚。内核中对于rwlock的行为并没有严格的规定，我看了不同平台上实现也略有差异（x86有一个读锁的上限，只是很大而已）。在内核的邮件列表中有一个人说Linux内核的读锁是需要支持nested的，并且在iptable中也这样用了（我还没看到代码具体在哪），但单纯一个nested也很难说清楚，这种锁必须不同于信号量，还有owner的存在，很难区分是nested调用还是不同的核上面发起的新的read_lock。

后面我是写错了，是指“优先写锁”：） 以前有些资料中讲过这种设计，主要是为了防止大量而频繁的读把写锁“饿死”。

Cyberman.Wu

回复 6# smalloc


    和进程/CPU关联可以会导致另一个问题，就是多访问内存数据，这种锁本身就要求时间非常短。在邮件列表中有人提到用一个基于CPU的锁，我还没来得及细看。

smalloc

多核片上网络!!

eexplorer

回复 1# Cyberman.Wu

> 对于spinlock，在核比较多例如超过100个的时候，一直测试一个内存值会导致比较多的访问冲突，是不是还不如获取冲突的时候
> 简单地“等待”一个随机值再试，就好像以前半双工网络中的冲突检测一样？

这个已经有人在linux kernel里提过相应的patch了，但是好像没什么跟进：
http://lwn.net/Articles/531254/， http://lwn.net/Articles/530458/
make ticket spinlock proportional backoff w/ auto tuning

Google还有人提出过fast queue spinlock http://lwn.net/Articles/533636/ (基于MCS queue lock), 但是好像也没有什么跟进。

   

eexplorer

Cyberman.Wu 发表于 2010-11-12 11:07
回复 2# smalloc

mc_list_lock好像在最新的kernel里已经没有了，而且IGMP相关的code好像都用RCU了。

Cyberman.Wu

回复 9# eexplorer


Linux内核一直改来改去的，隔几个版本许多东西就得重新确认。

这个问题后来在内核的mail list中讨论过，已经确认是Tilera自己实现的读写锁不符合Linux
内核对于读写锁的要求。
另外这个平台上的TNS指令做锁其实还有另一个死锁的风险，不能仅使用TNS。