分类目录归档:IPC

Linux kernel spinlock使用不当的后果

spinlock(自旋锁)是内核中最常见的锁,它的特点是:等待锁的过程中不休眠,而是占着CPU空转,优点是避免了上下文切换的开销,缺点是该CPU空转属于浪费,spinlock适合用来保护快进快出的临界区。

spinlock有很多限制条件,其中最重要的是,持有spinlock的CPU不能被抢占,持有spinlock的代码不能休眠。如果违反,会发生死锁,后果很严重。持有spinlock的代码不能休眠,这一条是开发者编写内核程序使用spinlock的时候要人工保证的。而持有spinlock的CPU不能被抢占是由spinlock的API本身提供保证,出于效率的考虑,spinlock的API提供了多种选择,对抢占的防止程度也不一样,开发者在选用的时候需要谨慎,下文对此详细展开。

Linux内核提供了多种spinlock的API,其中最常用的是:
spin_lock/spin_unlock — 禁止内核抢占
spin_lock_irq/spin_unlock_irq — 禁止内核抢占并屏蔽中断
spin_lock_irqsave/spin_unlock_irqrestore — 禁止内核抢占并屏蔽中断,事先保存中断屏蔽位并事后恢复原状

spin_lock()禁止了内核抢占,但是没有屏蔽中断,意味着持有该spinlock的CPU有可能被中断抢占。如果你的某段内核代码选用了spin_lock(),就必须保证这段代码不会被任何中断处理程序调用,否则就会发生死锁(参见后文的一个实际发生的案例)。如果某段内核代码有可能被中断处理程序调用,那就只能选择spin_lock_irq或spin_lock_irqsave。

下面是一个刚发生的实际案例,SLES11 SP4的系统失去响应,kdump生成了vmcore,分析过程中发现以下backtraces揭示了原因:

我来解释一下,上面的backtraces意思是:CPU 2上正在运行的进程是”kswapd0″(kswapd0是负责swapping的内核线程),它正在压缩dcache以便腾出一些空闲内存,当它执行到__shrink_dcache_sb()的时候被一个中断抢占了CPU,(注意被中断抢占的进程不会离开当前CPU,不会有机会到其它CPU上运行,只能等中断处理结束之后把CPU交还给它),中断处理程序是bnx2x驱动模块(注意看[],表示的是内核模块),它发现内存不够,于是自动清理内存,最终也走到了压缩dcache这一步,也去调用__shrink_dcache_sb(),但是__shrink_dcache_sb()的临界区受到spinlock保护,见下面源代码第0823行,这个名为dcache_lru_lock的spinlock刚才已经被”kswapd0″进程持有了,所以中断处理程序不可能抢到,问题是持有dcache_lru_lock的”kswapd0″进程又被中断抢占了CPU,不可能继续运行,也就没机会释放掉dcache_lru_lock,这就陷入了死锁状态。

根本原因在于,既然__shrink_dcache_sb()选用了spin_lock(),就意味着设计者认为它不会被中断处理程序调用,因为spin_lock()不屏蔽中断,是不能防止中断抢占的,只要中断处理程序不调用__shrink_dcache_sb(),死锁就不会发生;如果要让__shrink_dcache_sb()可以被中断处理程序调用,那就不能选用spin_lock(),而应该用spin_lock_irq或spin_lock_irqsave。这个案例中的问题出在bnx2x驱动程序中,它在bnx2x_alloc_rx_sge() 中调用alloc_pages()时不恰当地使用了GFP_KERNEL标志,实际上应该使用GFP_ATOMIC标志,这样alloc_pages()就不会试图去主动回收内存、也就不会最终调用__shrink_dcache_sb()了。此bug记载在SUSE的bsc#975358中,在kernel 3.0.101-77中得以修复。

RCU CPU STALL DETECTOR

在RHEL 7 和 SELS11 SP2 之后的Linux系统上,有时会看到如下信息:

它们来自RCU CPU Stall Detector,要了解RCU CPU Stall Detector是什么,首先要知道RCU是什么。RCU(Read-Copy Update) 是Linux 2.6 内核开始引入的一种新的锁机制,与spinlock、rwlock不同,RCU有其独到之处,它只适用于读多写少的情况。

RCU是基于其原理命名的,Read-Copy Update,[Read]指的是对于被RCU保护的共享数据,reader可以直接访问,不需要获得任何锁;[Copy Update]指的是writer修改数据前首先拷贝一个副本,然后在副本上进行修改,修改完毕后向reclaimer(垃圾回收器)注册一个回调函数(callback),在适当的时机完成真正的修改操作–把原数据的指针重新指向新的被修改的数据,–这里所说的适当的时机就是当既有的reader全都退出临界区的时候,而等待恰当时机的过程被称为 grace period。在RCU机制中,writer不需要和reader竞争任何锁,只在有多个writer的情况下它们之间需要某种锁进行同步作,如果写操作频繁的话RCU的性能会严重下降,所以RCU只适用于读多写少的情况。

RCU API 最核心的函数是:
rcu_read_lock()
rcu_read_unlock()
synchronize_rcu()
call_rcu()

  • rcu_read_lock()和rcu_read_unlock()配对使用,由reader调用,用以标记reader进入/退出临界区。夹在这两个函数之间的代码区称为”读端临界区”(read-side critical section),注:读端临界区可以嵌套。reader在临界区内是不能被阻塞的。
  • synchronize_rcu()由writer调用,它会阻塞writer(即writer会进入睡眠等待),直到经过grace period后,即所有的reader都退出读端临界区,writer才可以继续下一步操作。如果有多个writer调用该函数,它们将在grace period之后全部被唤醒。
  • call_rcu()是synchronize_rcu()的非阻塞版本,它也由 writer调用,但不会阻塞writer(即writer不会进入睡眠,而是继续运行),因而可以在中断上下文或 softirq 中使用,而 synchronize_rcu()只能在进程上下文使用。call_rcu()把参数中指定的callback函数挂接到 RCU回调函数链上,然后立即返回。一旦所有的 CPU 都已经完成端临界区操作(即grace period之后),该callback函数将被调用,用writer修改过的数据副本替换原数据并释放原数据空间。需要指出的是,函数 synchronize_rcu 的实现实际上也使用了函数call_rcu()。

RCU API 有一些特殊用途的分支,比如 RCU BH (防DDoS攻击的API)、RCU Sched(适用于 scheduler 和 interrupt/NMI-handler 的 API),等。参见 http://lwn.net/Articles/264090/

RCU在Linux 2.6内核中(RHEL6和SLES11 SP1)就已经存在了,那时处理grace period利用了软中断(softirq),而到了新的3.x内核之后有所改变,处理grace period利用的是内核线程,因为内核线程可以被抢占,减少了实时任务的响应延迟。所以在3.x内核的系统上,会看到类似如下的内核线程:
[rcu_sched]
[rcu_bh]
[rcuob/0]
[rcuob/1]
[rcuos/0]
[rcuos/1]
还有可能会见到rcu_preempt线程。
注:其中 rcuob/N, rcuos/N 是负责处理 RCU callbacks 的内核线程,参见https://www.kernel.org/doc/Documentation/kernel-per-CPU-kthreads.txt

好了,现在终于可以讲 RCU CPU Stall Detector 了,它其实是RCU代码中的一个debugging feature(参见https://lwn.net/Articles/301910/ ),在2.6内核中缺省是关闭的,而到3.x内核中缺省是打开的,它有助于检测导致 grace period 过度延迟的因素,因为grace period的长短是RCU性能的重要因素。发生RCU grace period延迟会在系统日志中记录告警信息,称为RCU CPU Stall Warnings

INFO: rcu_sched_state detected stalls on CPUs/tasks: { 15} (detected by 17, t=15002 jiffies)

INFO: rcu_bh_state detected stalls on CPUs/tasks: { 3 5 } (detected by 2, 2502 jiffies)
等等。

在上述告警信息之后通常还会看到相关CPU的stack dump,检查stack trace有助于了解当时运行的代码和可能导致延迟的原因。

如果你不想看到以上告警信息,可以通过以下参数关掉它:
/sys/module/rcupdate/parameters/rcu_cpu_stall_suppress
注:缺省值为0,表示显示延迟告警;置为1表示禁止显示延迟告警。
RCU grace period延迟多长时间会触发告警呢?这是以下参数决定的(以秒为单位):
/sys/module/rcupdate/parameters/rcu_cpu_stall_timeout
RCU的其它内核参数,如rcupdate.rcu_task_stall_timeout等参见:
https://www.kernel.org/doc/Documentation/kernel-parameters.txt

有哪些原因会导致 RCU grace period延迟(RCU CPU Stall Warnings)呢?参见 https://www.kernel.org/doc/Documentation/RCU/stallwarn.txt 这里仅列举几例:

  • CPU 在 RCU read-side 临界区内死循环
  • CPU 在屏蔽中断的情况下死循环
  • Linux引导过程中输出信息很多,但是所用的 console太慢,跟不上信息输出的速度。
  • 任何可能导致 RCU grace-period 内核线程无法运行的因素
  • 优先级很高的实时任务占着 CPU 不放,抢占了恰好处于RCU read-side临界区的低优先级任务。
  • RCU代码bug。
  • 硬件故障。.
  • 等等。

具体分析还需从告警信息中输出的stack trace入手。

参考资料:
源代码:kernel/rcupdate.c, kernel/rcutree.c …
https://www.ibm.com/developerworks/cn/linux/l-rcu/
https://www.kernel.org/doc/Documentation/RCU/stallwarn.txt
https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt
http://lwn.net/Articles/262464/
https://lwn.net/Articles/518953/

futex

futex (fast userspace mutex) 是Linux的一个基础构件,可以用来构建各种更高级别的同步机制,比如锁或者信号量等等,POSIX信号量就是基于futex构建的。大多数时候编写应用程序并不需要直接使用futex,一般用基于它所实现的系统库就够了。

futex的性能非常优异,它是怎样做到的呢?这要从它的设计思想谈起。传统的SystemV IPC(inter process communication)进程间同步机制都是通过内核对象来实现的,以 semaphore 为例,当进程间要同步的时候,必须通过系统调用semop(2)进入内核进行PV操作。系统调用的缺点是开销很大,需要从user mode切换到kernel mode、保存寄存器状态、从user stack切换到kernel stack、等等,通常要消耗上百条指令。事实上,有一部分系统调用是可以避免的,因为现实中很多同步操作进行的时候根本不存在竞争,即某个进程从持有semaphore直至释放semaphore的这段时间内,常常没有其它进程对同一semaphore有需求,在这种情况下,内核的参与本来是不必要的,可是在传统机制下,持有semaphore必须先调用semop(2)进入内核去看看有没有人和它竞争,释放semaphore也必须调用semop(2)进入内核去看看有没有人在等待同一semaphore,这些不必要的系统调用造成了大量的性能损耗。futex就为了解决这个问题而生的,它的办法是:在无竞争的情况下,futex的操作完全在user space进行,不需要系统调用,仅在发生竞争的时候进入内核去完成相应的处理(wait 或者 wake up)。所以说,futex是一种user mode和kernel mode混合的同步机制,需要两种模式合作才能完成,futex变量必须位于user space,而不是内核对象,futex的代码也分为user mode和kernel mode两部分,无竞争的情况下在user mode,发生竞争时则通过sys_futex系统调用进入kernel mode进行处理,具体来说:

futex变量是位于user space的一个整数,支持原子操作。futex同步操作都是从user space开始的:

  • 当要求持有futex的时候,对futex变量执行”down”操作,即原子递减,如果变量变为0,则意味着没有竞争发生,进程成功持有futex并继续在user mode运行;如果变量变为负数,则意味着有竞争发生,需要通过sys_futex系统调用进入内核执行futex_wait操作,让进程进入休眠等待。
  • 当释放futex的时候,对futex变量进行”up”操作,即原子递增,如果变量变成1,则意味着没有竞争发生,进程成功释放futex并继续在user mode执行;否则意味着有竞争,需要通过sys_futex系统调用进入内核执行futex_wake操作,唤醒正在等待的进程。

如果需要在多个进程之间共享futex,那就必须把futex变量放在共享内存中,并确保这些进程都有访问共享内存的权限;如果仅需在线程之间使用futex的话,那么futex变量可以位于进程的私有内存中,比如普通的全局变量即可。

更详细的信息请参阅futex作者的论文:
Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux

POSIX信号量

提起信号量,大多数人首先想到SystemV 信号量,熟悉POSIX信号量的人则相对少一点,下面就对POSIX信号量做一个简单介绍,但在此之前,我们先简单回顾一下SystemV 信号量,以便比较它们的异同。SystemV 信号量是内核对象,由内核统一管理,用户程序通过semget(2)向内核提出申请,内核根据需要创建新的信号量或者关联已存在的信号量,每组信号量都有唯一的ID标识,可以被多个进程共享。PV操作通过调用semop(2)或者semtimedop(2)来进行。因为SystemV 信号量是内核对象,所以它的存续不依赖于进程,而是由内核管理,即使进程退出也仍然存在,要删除信号量必须显式地调用semctl(2)。有两条命令用来管理System V 信号量:ipcs(1)ipcrm(1)ipcs -s 用于查看,ipcrm -s 用于删除。

POSIX信号量与SystemV 不太一样,它分为两类:无名信号量(unnamed semaphore) 和 有名信号量(named semaphore)

有名信号量与System V 信号量类似,它也是由内核统一管理的,但不是用ID作标识,而是用名字作标识,有名信号量的名字有点像文件名,必须是以”/”开头的字符串,但不能包含字符”.”。用户程序通过调用sem_open(3)创建或打开有名信号量。有名信号量的存续也是内核决定的,与进程是否退出没有关系,必须显式调用sem_unlink(3)才能删除。在Linux系统上,有名信号量跟共享内存一样,会在/dev/shm 目录下产生文件,管理有名信号量通过这些文件进行,查看的命令如下:

删除的命令如下:
$ rm /dev/shm/sem.mysem

无名信号量是基于user memory的,通过sem_init(3)创建,调用参数中需要指定放置信号量的内存地址,这个地址可以是私有内存,也可以是共享内存。如果要在多个进程之间共享无名信号量的话,就必须使用共享内存。在实践中,无名信号量一般用于线程之间、或者父子进程之间,否则编程有点麻烦:因为要事先约定好无名信号量的地址才行。由于无名信号量建立在user memory上,它的存续与内存的存续直接相关,如果无名信号量位于进程的私有内存(比如进程的全局变量),那么当该进程终止时无名信号量也会消失;如果无名信号量是在共享内存区中,那么只要该共享内存区还存在,该信号量就存在,而与进程是否中止没有关系。
注:好像没有命令用来查看或管理无名信号量。

POSIX信号量的PV操作通过调用sem_wait(3)和sem_post(3)进行,对无名信号量和有名信号量都一样。

POSIX信号量的API是库函数,而SystemV信号量的API是系统调用(system calls)。如果你用strace(1)跟踪一下,会看到SystemV信号量使用的系统调用是semget(2)/semctl(2)/semop(2)等,而POSIX信号量使用的系统调用是futex(2)。使用POSIX信号量的程序需要链接librt.xxx库,编译时使用-lrt参数。