Linux内核同步机制之(四):spin lock

作者:linuxer 发布于:2015-4-22 12:22 分类:内核同步机制

一、前言

在linux kernel的实现中,经常会遇到这样的场景:共享数据被中断上下文和进程上下文访问,该如何保护呢?如果只有进程上下文的访问,那么可以考虑使用semaphore或者mutex的锁机制,但是现在中断上下文也参和进来,那些可以导致睡眠的lock就不能使用了,这时候,可以考虑使用spin lock。本文主要介绍了linux kernel中的spin lock的原理以及代码实现。由于spin lock是architecture dependent代码,因此,我们在第四章讨论了ARM32和ARM64上的实现细节。

注:本文需要进程和中断处理的基本知识作为支撑。

 

二、工作原理

1、spin lock的特点

我们可以总结spin lock的特点如下:

(1)spin lock是一种死等的锁机制。当发生访问资源冲突的时候,可以有两个选择:一个是死等,一个是挂起当前进程,调度其他进程执行。spin lock是一种死等的机制,当前的执行thread会不断的重新尝试直到获取锁进入临界区。

(2)只允许一个thread进入。semaphore可以允许多个thread进入,spin lock不行,一次只能有一个thread获取锁并进入临界区,其他的thread都是在门口不断的尝试。

(3)执行时间短。由于spin lock死等这种特性,因此它使用在那些代码不是非常复杂的临界区(当然也不能太简单,否则使用原子操作或者其他适用简单场景的同步机制就OK了),如果临界区执行时间太长,那么不断在临界区门口“死等”的那些thread是多么的浪费CPU啊(当然,现代CPU的设计都会考虑同步原语的实现,例如ARM提供了WFE和SEV这样的类似指令,避免CPU进入busy loop的悲惨境地)

(4)可以在中断上下文执行。由于不睡眠,因此spin lock可以在中断上下文中适用。

2、 场景分析

对于spin lock,其保护的资源可能来自多个CPU CORE上的进程上下文和中断上下文的中的访问,其中,进程上下文包括:用户进程通过系统调用访问,内核线程直接访问,来自workqueue中work function的访问(本质上也是内核线程)。中断上下文包括:HW interrupt context(中断handler)、软中断上下文(soft irq,当然由于各种原因,该softirq被推迟到softirqd的内核线程中执行的时候就不属于这个场景了,属于进程上下文那个分类了)、timer的callback函数(本质上也是softirq)、tasklet(本质上也是softirq)。

先看最简单的单CPU上的进程上下文的访问。如果一个全局的资源被多个进程上下文访问,这时候,内核如何交错执行呢?对于那些没有打开preemptive选项的内核,所有的系统调用都是串行化执行的,因此不存在资源争抢的问题。如果内核线程也访问这个全局资源呢?本质上内核线程也是进程,类似普通进程,只不过普通进程时而在用户态运行、时而通过系统调用陷入内核执行,而内核线程永远都是在内核态运行,但是,结果是一样的,对于non-preemptive的linux kernel,只要在内核态,就不会发生进程调度,因此,这种场景下,共享数据根本不需要保护(没有并发,谈何保护呢)。如果时间停留在这里该多么好,单纯而美好,在继续前进之前,让我们先享受这一刻。

当打开premptive选项后,事情变得复杂了,我们考虑下面的场景:

(1)进程A在某个系统调用过程中访问了共享资源R

(2)进程B在某个系统调用过程中也访问了共享资源R

会不会造成冲突呢?假设在A访问共享资源R的过程中发生了中断,中断唤醒了沉睡中的,优先级更高的B,在中断返回现场的时候,发生进程切换,B启动执行,并通过系统调用访问了R,如果没有锁保护,则会出现两个thread进入临界区,导致程序执行不正确。OK,我们加上spin lock看看如何:A在进入临界区之前获取了spin lock,同样的,在A访问共享资源R的过程中发生了中断,中断唤醒了沉睡中的,优先级更高的B,B在访问临界区之前仍然会试图获取spin lock,这时候由于A进程持有spin lock而导致B进程进入了永久的spin……怎么破?linux的kernel很简单,在A进程获取spin lock的时候,禁止本CPU上的抢占(上面的永久spin的场合仅仅在本CPU的进程抢占本CPU的当前进程这样的场景中发生)。如果A和B运行在不同的CPU上,那么情况会简单一些:A进程虽然持有spin lock而导致B进程进入spin状态,不过由于运行在不同的CPU上,A进程会持续执行并会很快释放spin lock,解除B进程的spin状态。

多CPU core的场景和单核CPU打开preemptive选项的效果是一样的,这里不再赘述。

我们继续向前分析,现在要加入中断上下文这个因素。访问共享资源的thread包括:

(1)运行在CPU0上的进程A在某个系统调用过程中访问了共享资源R

(2)运行在CPU1上的进程B在某个系统调用过程中也访问了共享资源R

(3)外设P的中断handler中也会访问共享资源R

在这样的场景下,使用spin lock可以保护访问共享资源R的临界区吗?我们假设CPU0上的进程A持有spin lock进入临界区,这时候,外设P发生了中断事件,并且调度到了CPU1上执行,看起来没有什么问题,执行在CPU1上的handler会稍微等待一会CPU0上的进程A,等它立刻临界区就会释放spin lock的,但是,如果外设P的中断事件被调度到了CPU0上执行会怎么样?CPU0上的进程A在持有spin lock的状态下被中断上下文抢占,而抢占它的CPU0上的handler在进入临界区之前仍然会试图获取spin lock,悲剧发生了,CPU0上的P外设的中断handler永远的进入spin状态,这时候,CPU1上的进程B也不可避免在试图持有spin lock的时候失败而导致进入spin状态。为了解决这样的问题,linux kernel采用了这样的办法:如果涉及到中断上下文的访问,spin lock需要和禁止本CPU上的中断联合使用。

linux kernel中提供了丰富的bottom half的机制,虽然同属中断上下文,不过还是稍有不同。我们可以把上面的场景简单修改一下:外设P不是中断handler中访问共享资源R,而是在的bottom half中访问。使用spin lock+禁止本地中断当然是可以达到保护共享资源的效果,但是使用牛刀来杀鸡似乎有点小题大做,这时候disable bottom half就OK了。

最后,我们讨论一下中断上下文之间的竞争。同一种中断handler之间在uni core和multi core上都不会并行执行,这是linux kernel的特性。如果不同中断handler需要使用spin lock保护共享资源,对于新的内核(不区分fast handler和slow handler),所有handler都是关闭中断的,因此使用spin lock不需要关闭中断的配合。bottom half又分成softirq和tasklet,同一种softirq会在不同的CPU上并发执行,因此如果某个驱动中的sofirq的handler中会访问某个全局变量,对该全局变量是需要使用spin lock保护的,不用配合disable CPU中断或者bottom half。tasklet更简单,因为同一种tasklet不会多个CPU上并发,具体我就不分析了,大家自行思考吧。

 

三、通用代码实现

1、文件整理

和体系结构无关的代码如下:

(1)include/linux/spinlock_types.h。这个头文件定义了通用spin lock的基本的数据结构(例如spinlock_t)和如何初始化的接口(DEFINE_SPINLOCK)。这里的“通用”是指不论SMP还是UP都通用的那些定义。

(2)include/linux/spinlock_types_up.h。这个头文件不应该直接include,在include/linux/spinlock_types.h文件会根据系统的配置(是否SMP)include相关的头文件,如果UP则会include该头文件。这个头文定义UP系统中和spin lock的基本的数据结构和如何初始化的接口。当然,对于non-debug版本而言,大部分struct都是empty的。

(3)include/linux/spinlock.h。这个头文件定义了通用spin lock的接口函数声明,例如spin_lock、spin_unlock等,使用spin lock模块接口API的驱动模块或者其他内核模块都需要include这个头文件。

(4)include/linux/spinlock_up.h。这个头文件不应该直接include,在include/linux/spinlock.h文件会根据系统的配置(是否SMP)include相关的头文件。这个头文件是debug版本的spin lock需要的。

(5)include/linux/spinlock_api_up.h。同上,只不过这个头文件是non-debug版本的spin lock需要的

(6)linux/spinlock_api_smp.h。SMP上的spin lock模块的接口声明

(7)kernel/locking/spinlock.c。SMP上的spin lock实现。

头文件有些凌乱,我们对UP和SMP上spin lock头文件进行整理:

UP需要的头文件 SMP需要的头文件

linux/spinlock_type_up.h:
linux/spinlock_types.h:
linux/spinlock_up.h:
linux/spinlock_api_up.h:
linux/spinlock.h

asm/spinlock_types.h
linux/spinlock_types.h:
asm/spinlock.h
linux/spinlock_api_smp.h:
linux/spinlock.h

2、数据结构

根据第二章的分析,我们可以基本可以推断出spin lock的实现。首先定义一个spinlock_t的数据类型,其本质上是一个整数值(对该数值的操作需要保证原子性),该数值表示spin lock是否可用。初始化的时候被设定为1。当thread想要持有锁的时候调用spin_lock函数,该函数将spin lock那个整数值减去1,然后进行判断,如果等于0,表示可以获取spin lock,如果是负数,则说明其他thread的持有该锁,本thread需要spin。

内核中的spinlock_t的数据类型定义如下:

typedef struct spinlock {
        struct raw_spinlock rlock; 
} spinlock_t;

typedef struct raw_spinlock {
    arch_spinlock_t raw_lock;
} raw_spinlock_t;

由于各种原因(各种锁的debug、锁的validate机制,多平台支持什么的),spinlock_t的定义没有那么直观,为了让事情简单一些,我们去掉那些繁琐的成员。struct spinlock中定义了一个struct raw_spinlock的成员,为何会如此呢?好吧,我们又需要回到kernel历史课本中去了。在旧的内核中(比如我熟悉的linux 2.6.23内核),spin lock的命令规则是这样:

通用(适用于各种arch)的spin lock使用spinlock_t这样的type name,各种arch定义自己的struct raw_spinlock。听起来不错的主意和命名方式,直到linux realtime tree(PREEMPT_RT)提出对spinlock的挑战。real time linux是一个试图将linux kernel增加硬实时性能的一个分支(你知道的,linux kernel mainline只是支持soft realtime),多年来,很多来自realtime branch的特性被merge到了mainline上,例如:高精度timer、中断线程化等等。realtime tree希望可以对现存的spinlock进行分类:一种是在realtime kernel中可以睡眠的spinlock,另外一种就是在任何情况下都不可以睡眠的spinlock。分类很清楚但是如何起名字?起名字绝对是个技术活,起得好了事半功倍,可维护性好,什么文档啊、注释啊都素那浮云,阅读代码就是享受,如沐春风。起得不好,注定被后人唾弃,或者拖出来吊打(这让我想起给我儿子起名字的那段不堪回首的岁月……)。最终,spin lock的命名规范定义如下:

(1)spinlock,在rt linux(配置了PREEMPT_RT)的时候可能会被抢占(实际底层可能是使用支持PI(优先级翻转)的mutext)。

(2)raw_spinlock,即便是配置了PREEMPT_RT也要顽强的spin

(3)arch_spinlock,spin lock是和architecture相关的,arch_spinlock是architecture相关的实现

对于UP平台,所有的arch_spinlock_t都是一样的,定义如下:

typedef struct { } arch_spinlock_t;

什么都没有,一切都是空啊。当然,这也符合前面的分析,对于UP,即便是打开的preempt选项,所谓的spin lock也不过就是disable preempt而已,不需定义什么spin lock的变量。

对于SMP平台,这和arch相关,我们在下一节描述。

3、spin lock接口API

我们整理spin lock相关的接口API如下:

接口API的类型 spinlock中的定义 raw_spinlock的定义
定义spin lock并初始化 DEFINE_SPINLOCK DEFINE_RAW_SPINLOCK
动态初始化spin lock spin_lock_init raw_spin_lock_init
获取指定的spin lock spin_lock raw_spin_lock
获取指定的spin lock同时disable本CPU中断 spin_lock_irq raw_spin_lock_irq
保存本CPU当前的irq状态,disable本CPU中断并获取指定的spin lock spin_lock_irqsave raw_spin_lock_irqsave
获取指定的spin lock同时disable本CPU的bottom half spin_lock_bh raw_spin_lock_bh
释放指定的spin lock spin_unlock raw_spin_unlock
释放指定的spin lock同时enable本CPU中断 spin_unlock_irq raw_spin_unock_irq
释放指定的spin lock同时恢复本CPU的中断状态 spin_unlock_irqstore raw_spin_unlock_irqstore
获取指定的spin lock同时enable本CPU的bottom half spin_unlock_bh raw_spin_unlock_bh
尝试去获取spin lock,如果失败,不会spin,而是返回非零值 spin_trylock raw_spin_trylock
判断spin lock是否是locked,如果其他的thread已经获取了该lock,那么返回非零值,否则返回0 spin_is_locked raw_spin_is_locked
     

在具体的实现面,我们不可能把每一个接口函数的代码都呈现出来,我们选择最基础的spin_lock为例子,其他的读者可以自己阅读代码来理解。

spin_lock的代码如下:

static inline void spin_lock(spinlock_t *lock)
{
    raw_spin_lock(&lock->rlock);
}

当然,在linux mainline代码中,spin_lock和raw_spin_lock是一样的,在realtime linux patch中,spin_lock应该被换成可以sleep的版本,当然具体如何实现我没有去看(也许直接使用了Mutex,毕竟它提供了优先级继承特性来解决了优先级翻转的问题),有兴趣的读者可以自行阅读,我们这里重点看看(本文也主要focus这个主题)真正的,不睡眠的spin lock,也就是是raw_spin_lock,代码如下:

#define raw_spin_lock(lock)    _raw_spin_lock(lock)

UP中的实现:

#define _raw_spin_lock(lock)            __LOCK(lock)

#define __LOCK(lock) \
  do { preempt_disable(); ___LOCK(lock); } while (0)

SMP的实现:

void __lockfunc _raw_spin_lock(raw_spinlock_t *lock)
{
    __raw_spin_lock(lock);
}

static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
    preempt_disable();
    spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
    LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

UP中很简单,本质上就是一个preempt_disable而已,和我们在第二章中分析的一致。SMP中稍显复杂,preempt_disable当然也是必须的,spin_acquire可以略过,这是和运行时检查锁的有效性有关的,如果没有定义CONFIG_LOCKDEP其实就是空函数。如果没有定义CONFIG_LOCK_STAT(和锁的统计信息相关),LOCK_CONTENDED就是调用do_raw_spin_lock而已,如果没有定义CONFIG_DEBUG_SPINLOCK,它的代码如下:

static inline void do_raw_spin_lock(raw_spinlock_t *lock) __acquires(lock)
{
    __acquire(lock);
    arch_spin_lock(&lock->raw_lock);
}

__acquire和静态代码检查相关,忽略之,最终实际的获取spin lock还是要靠arch相关的代码实现。

 

四、ARM平台的细节

代码位于arch/arm/include/asm/spinlock.h和spinlock_type.h,和通用代码类似,spinlock_type.h定义ARM相关的spin lock定义以及初始化相关的宏;spinlock.h中包括了各种具体的实现。

1、回忆过去

在分析新的spin lock代码之前,让我们先回到2.6.23版本的内核中,看看ARM平台如何实现spin lock的。和arm平台相关spin lock数据结构的定义如下(那时候还是使用raw_spinlock_t而不是arch_spinlock_t):

typedef struct {
    volatile unsigned int lock;
} raw_spinlock_t;

一个整数就OK了,0表示unlocked,1表示locked。配套的API包括__raw_spin_lock和__raw_spin_unlock。__raw_spin_lock会持续判断lock的值是否等于0,如果不等于0(locked)那么其他thread已经持有该锁,本thread就不断的spin,判断lock的数值,一直等到该值等于0为止,一旦探测到lock等于0,那么就设定该值为1,表示本thread持有该锁了,当然,这些操作要保证原子性,细节和exclusive版本的ldr和str(即ldrex和strexeq)相关,这里略过。立刻临界区后,持锁thread会调用__raw_spin_unlock函数是否spin lock,其实就是把0这个数值赋给lock。

这个版本的spin lock的实现当然可以实现功能,而且在没有冲突的时候表现出不错的性能,不过存在一个问题:不公平。也就是所有的thread都是在无序的争抢spin lock,谁先抢到谁先得,不管thread等了很久还是刚刚开始spin。在冲突比较少的情况下,不公平不会体现的特别明显,然而,随着硬件的发展,多核处理器的数目越来越多,多核之间的冲突越来越剧烈,无序竞争的spinlock带来的performance issue终于浮现出来,根据Nick Piggin的描述:

On an 8 core (2 socket) Opteron, spinlock unfairness is extremely noticable, with a userspace test having a difference of up to 2x runtime per thread, and some threads are starved or "unfairly" granted the lock up to 1 000 000 (!) times.

多么的不公平,有些可怜的thread需要饥饿的等待1000000次。本质上无序竞争从概率论的角度看应该是均匀分布的,不过由于硬件特性导致这么严重的不公平,我们来看一看硬件block:

lock

lock本质上是保存在main memory中的,由于cache的存在,当然不需要每次都有访问main memory。在多核架构下,每个CPU都有自己的L1 cache,保存了lock的数据。假设CPU0获取了spin lock,那么执行完临界区,在释放锁的时候会调用smp_mb invalide其他忙等待的CPU的L1 cache,这样后果就是释放spin lock的那个cpu可以更快的访问L1cache,操作lock数据,从而大大增加的下一次获取该spin lock的机会。

2、回到现在:arch_spinlock_t

ARM平台中的arch_spinlock_t定义如下(little endian):

typedef struct {
    union {
        u32 slock;
        struct __raw_tickets {
            u16 owner;
            u16 next;
        } tickets;
    };
} arch_spinlock_t;

本来以为一个简单的整数类型的变量就搞定的spin lock看起来没有那么简单,要理解这个数据结构,需要了解一些ticket-based spin lock的概念。如果你有机会去九毛九去排队吃饭(声明:不是九毛九的饭托,仅仅是喜欢面食而常去吃而已)就会理解ticket-based spin lock。大概是因为便宜,每次去九毛九总是无法长驱直入,门口的笑容可掬的靓女会给一个ticket,上面写着15号,同时会告诉你,当前状态是10号已经入席,11号在等待。

回到arch_spinlock_t,这里的owner就是当前已经入席的那个号码,next记录的是下一个要分发的号码。下面的描述使用普通的计算机语言和在九毛九就餐(假设九毛九只有一张餐桌)的例子来进行描述,估计可以让吃货更有兴趣阅读下去。最开始的时候,slock被赋值为0,也就是说owner和next都是0,owner和next相等,表示unlocked。当第一个个thread调用spin_lock来申请lock(第一个人就餐)的时候,owner和next相等,表示unlocked,这时候该thread持有该spin lock(可以拥有九毛九的唯一的那个餐桌),并且执行next++,也就是将next设定为1(再来人就分配1这个号码让他等待就餐)。也许该thread执行很快(吃饭吃的快),没有其他thread来竞争就调用spin_unlock了(无人等待就餐,生意惨淡啊),这时候执行owner++,也就是将owner设定为1(表示当前持有1这个号码牌的人可以就餐)。姗姗来迟的1号获得了直接就餐的机会,next++之后等于2。1号这个家伙吃饭巨慢,这是不文明现象(thread不能持有spin lock太久),但是存在。又来一个人就餐,分配当前next值的号码2,当然也会执行next++,以便下一个人或者3的号码牌。持续来人就会分配3、4、5、6这些号码牌,next值不断的增加,但是owner岿然不动,直到欠扁的1号吃饭完毕(调用spin_unlock),释放饭桌这个唯一资源,owner++之后等于2,表示持有2那个号码牌的人可以进入就餐了。 

3、接口实现

同样的,这里也只是选择一个典型的API来分析,其他的大家可以自行学习。我们选择的是arch_spin_lock,其ARM32的代码如下:

static inline void arch_spin_lock(arch_spinlock_t *lock)
{
    unsigned long tmp;
    u32 newval;
    arch_spinlock_t lockval;

    prefetchw(&lock->slock);------------------------(1)
    __asm__ __volatile__(
"1:    ldrex    %0, [%3]\n"-------------------------(2)
"    add    %1, %0, %4\n"
"    strex    %2, %1, [%3]\n"------------------------(3)
"    teq    %2, #0\n"----------------------------(4)
"    bne    1b"
    : "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
    : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
    : "cc");

    while (lockval.tickets.next != lockval.tickets.owner) {------------(5)
        wfe();-------------------------------(6)
        lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);------(7)
    }

    smp_mb();------------------------------(8)
}

(1)和preloading cache相关的操作,主要是为了性能考虑

(2)将slock的值保存在lockval这个临时变量中

(3)将spin lock中的next加一

(4)判断是否有其他的thread插入。更具体的细节参考Linux内核同步机制之(一):原子操作中的描述

(5)判断当前spin lock的状态,如果是unlocked,那么直接获取到该锁

(6)如果当前spin lock的状态是locked,那么调用wfe进入等待状态。更具体的细节请参考ARM WFI和WFE指令中的描述。

(7)其他的CPU唤醒了本cpu的执行,说明owner发生了变化,该新的own赋给lockval,然后继续判断spin lock的状态,也就是回到step 5。

(8)memory barrier的操作,具体可以参考memory barrier中的描述。

  arch_spin_lock函数ARM64的代码(来自4.1.10内核)如下:

static inline void arch_spin_lock(arch_spinlock_t *lock)
{
    unsigned int tmp;
    arch_spinlock_t lockval, newval;

    asm volatile(
    /* Atomically increment the next ticket. */
"    prfm    pstl1strm, %3\n"
"1:    ldaxr    %w0, %3\n"-----(A)-----------lockval = lock
"    add    %w1, %w0, %w5\n"-------------newval = lockval + (1 << 16),相当于next++
"    stxr    %w2, %w1, %3\n"--------------lock = newval
"    cbnz    %w2, 1b\n"--------------是否有其他PE的执行流插入?有的话,重来。
    /* Did we get the lock? */
"    eor    %w1, %w0, %w0, ror #16\n"--lockval中的next域就是自己的号码牌,判断是否等于owner
"    cbz    %w1, 3f\n"----------------如果等于,持锁进入临界区
    /*
     * No: spin on the owner. Send a local event to avoid missing an
     * unlock before the exclusive load.
     */
"    sevl\n"
"2:    wfe\n"--------------------否则进入spin
"    ldaxrh    %w2, %4\n"----(A)---------其他cpu唤醒本cpu,获取当前owner值
"    eor    %w1, %w2, %w0, lsr #16\n"---------自己的号码牌是否等于owner?
"    cbnz    %w1, 2b\n"----------如果等于,持锁进入临界区,否者回到2,即继续spin
    /* We got the lock. Critical section starts here. */
"3:"
    : "=&r" (lockval), "=&r" (newval), "=&r" (tmp), "+Q" (*lock)
    : "Q" (lock->owner), "I" (1 << TICKET_SHIFT)
    : "memory");
}


基本的代码逻辑的描述都已经嵌入代码中,这里需要特别说明的有两个知识点:

(1)Load-Acquire/Store-Release指令的应用。Load-Acquire/Store-Release指令是ARMv8的特性,在执行load和store操作的时候顺便执行了memory barrier相关的操作,在spinlock这个场景,使用Load-Acquire/Store-Release指令代替dmb指令可以节省一条指令。上面代码中的(A)就标识了使用Load-Acquire指令的位置。Store-Release指令在哪里呢?在arch_spin_unlock中,这里就不贴代码了。Load-Acquire/Store-Release指令的作用如下:

       -Load-Acquire可以确保系统中所有的observer看到的都是该指令先执行,然后是该指令之后的指令(program order)再执行

       -Store-Release指令可以确保系统中所有的observer看到的都是该指令之前的指令(program order)先执行,Store-Release指令随后执行

(2)第二个知识点是关于在arch_spin_unlock代码中为何没有SEV指令?关于这个问题可以参考ARM ARM文档中的Figure B2-5,这个图是PE(n)的global monitor的状态迁移图。当PE(n)对x地址发起了exclusive操作的时候,PE(n)的global monitor从open access迁移到exclusive access状态,来自其他PE上针对x(该地址已经被mark for PE(n))的store操作会导致PE(n)的global monitor从exclusive access迁移到open access状态,这时候,PE(n)的Event register会被写入event,就好象生成一个event,将该PE唤醒,从而可以省略一个SEV的指令。


注: 

(1)+表示在嵌入的汇编指令中,该操作数会被指令读取(也就是说是输入参数)也会被汇编指令写入(也就是说是输出参数)。
(2)=表示在嵌入的汇编指令中,该操作数会是write only的,也就是说只做输出参数。
(3)I表示操作数是立即数

 

原创文章,转发请注明出处。蜗窝科技

Change log:

1、2015/11/5,加入ARM64的代码实现部分的分析

2、2015/11/17,增加ARM64代码中的两个知识点的描述

标签: spin lock 自旋锁

评论:

fy
2017-11-02 19:58
hi 说到spin lock
说一个老生常谈的问题吧。
如果一个临界区X是有进程上下文和中断上下文都会访问的。那按理 spin lock应该做到
1.禁止本地中断 2.禁止抢占 3.自旋

那又由于内核抢占真正能运行的前提是 从一个中断返回时(A) 并且当前允许抢占(B)并且当前中断开启(C)。。。
因为上面1.中已经禁止本地中断了,即使2.禁止抢占不做也没关系了。
我个人觉得确实是不需要2.禁止抢占的。只要1禁止本地中断和3.自旋 一起就可以达到保护临界区X
如果真的不加上 2.禁止抢占,会不会有问题,我想了一些case,暂时没想到。
当然,我是默认临界区X内不会主动放弃CPU为前提的。(临界区也确实不应该睡眠才是)

不知道linuxer对此什么看法。
wowo
2017-11-06 17:07
@fy:我有点看不太明白这个问题,不过可以试着说一下我的理解:
spin lock有两大类:
一类是spin_lock,做的事情就是禁止抢占+自旋,这样可以保护那些没有中断参与的临界区,代价也小一些。
一类是spin_lock_irqsave,做的事情是禁止中断+(禁止抢占+自旋),这样在第一类的基础上也可以保护有中断参与的临界区。
你好像在质疑第二类中禁止抢占的必要性,确实,没什么必要。可spin_lock_irqsave要调用spin_lock啊,再封出来一个接口?岂不是有点画蛇添足了?
fy
2017-11-11 16:08
@wowo:是的。我只是就这里的“禁止抢占”非必要,问问wowo的个人理解。
确实是非必要的。
非常感谢。
LOONG
2017-11-29 13:10
@fy:前来膜拜郭大侠:)
那天看文嘉转了郭大侠在另一个群里讨论这个问题(关抢占有没有必要),觉得受益匪浅,学习了。
当时就想:或者作者当初也并不是一气呵成呢?这样定然有commit log可以查询。试着搜了一下,发现目前的git库已经没有相关记录了。于是上网搜到了这个问题:
https://stackoverflow.com/questions/13263538/linux-kernel-spinlock-smp-why-there-is-a-preempt-disable-in-spin-lock-irq-sm
基本跟郭大侠分析的一样:)
不知@fy有何理解?或许可以直接问Dave Miller,说不定他跟郭大侠一样nice:)
linuxer
2017-11-30 08:38
@LOONG:多谢支持!问题是一样的问题,但是在stackoverflow上也没有得到回答,不过在前几天的微信群里,这里问题已经讨论的比较清楚了。
linuxer
2017-11-30 08:50
@fy:非常好的问题,非常精彩的思考点。

禁止了中断的确等于了禁止抢占,但是并不意味着它们两个完全等同,因为在preempt disable---preempt enable这个的调用过程中,在打开抢占的时候有一个抢占点,内核控制路径会在这里检查抢占,如果满足抢占条件,那么会立刻调度schedule函数进行进程切换,但是local irq disable---local irq enable的调用中,并没有显示的抢占检查点,当然,中断有点特殊,因为一旦打开中断,那么pending的中断会进来,并且在返回中断点的时候会检查抢占,但是也许下面的这个场景就无能为力了。进程上下文中调用如下序列:
(1)local irq disable
(2)wake up high level priority task
(3)local irq enable
当唤醒的高优先级进程被调度到本CPU执行的时候,按理说这个高优先级进程应该立刻抢占当前进程,但是这个场景无法做到。在调用try_to_wake_up的时候会设定need resched flag并检查抢占,但是由于中断disable,因此不会立刻调用schedule,但是在step (3)的时候,由于没有检查抢占,这时候本应立刻抢占的高优先级进程会发生严重的调度延迟.....直到下一个抢占点到来。
wowo
2017-11-30 10:06
@linuxer:这个场景还是挺有意思的,不过话说回来了,spin_lock_xxx的目的是保护临界区,关preempt的抢占点什么事呢?爱抢占不抢占啊~
本质上还是spin_lock需要通过开关抢占进行临界区保护,到spin_lock_irqxxx的时候,顺便做一下,再顺便帮preempt一个忙而已。
所以这个场景并不能构成“spin_lock_irqsave关抢占是否有必要的理由”,最后的答案还是没必要(因为“保护”的目的已经达到),至于是不是可以增加一个抢占点,在local_irq_restore的时候,调用一下preempt_check_resched岂不是更直接?
zoro
2017-10-31 17:18
如果CPU0上有个线程A获得了锁后在执行临界代码,这个时候CPU0上发生了中断,中断中也申请同一个锁,这样的话这个CPU0岂不是就进入低功耗等待模式了?不能再去做其他事情了。

如果CPU0进入了低功耗等待模式,那么其他的CPU能不能去释放这个锁,同时把CPU0从低功耗等待模式退出呢?
linuxer
2017-11-02 12:02
@zoro:你说的场景属于错误的使用了锁的机制,如果一个临界区会被中断和线程并非访问,那么你需要的内核同步机制是spin lock+disable local irq
benjoying
2017-07-18 18:08
(1)运行在CPU0上的进程A在某个系统调用过程中访问了共享资源R

(2)运行在CPU1上的进程B在某个系统调用过程中也访问了共享资源R

(3)外设P的bottom half中也会访问共享资源R

这时候,使用spin lock+禁止本地中断当然是可以达到保护共享资源的效果,但是disable中断会影响系统的中断延迟。在这种场景下,最适合的策略是:使用spin lock+禁止bottom half的方法。
@linuxer, 在这里有点不太明白,bottom half一般是用来做一些比较费时的事情,那如果把这个disable掉,那这部分如何处理呢,感谢!
linuxer
2017-07-19 14:34
@benjoying:一般而言,这种临界区不会太长,一旦离开临界区,打开了bottom half的话,delay的bottom half会立刻执行。
benjoying
2017-07-19 20:37
@linuxer:@linuxer 感谢感谢,之前把这个意思曲解了谢谢!
michael
2017-04-13 22:02
@linuxer

您的文章中这样写到:
最后,我们讨论一下中断上下文之间的竞争。同一种中断handler之间在uni core和multi core上都不会并行执行,这是linux kernel的特性。如果不同中断handler需要使用spin lock保护共享资源,对于新的内核(不区分fast handler和slow handler),所有handler都是关闭中断的,因此使用spin lock不需要关闭中断的配合。bottom half又分成softirq和tasklet,同一种softirq会在不同的CPU上并发执行,因此如果某个驱动中的sofirq的handler中会访问某个全局变量,对该全局变量是需要使用spin lock保护的,不用配合disable CPU中断或者bottom half。tasklet更简单,因为同一种tasklet不会多个CPU上并发,具体我就不分析了,大家自行思考吧

下面是我对这段话的分析,帮忙分析是否正确:
(1)中断handler+spinlock
1.同一种中断不能并发运行在多个CPU上,因此同一种中断访问时不需要spinlock保护.
2.如果两个中断handler运行同一个CPU上,由于新的内核disable local irq,因此这种情况不需要spinlock保护.
3.如果两个中断handler运行在不同的CPU上,这种情况需要spinlock保护,且调用函数spin_lock_irqsave进行保护?
(2)softirq+spinlock
4.同一种softirq可以运行在多个CPU上,因此需要spinlock保护,调用哪个API进行保护?
5.不同的softirq可以运行在多个CPU上,因此需要spinlock保护,调用哪个API进行保护?
(3)tasklet+spinlock
6.同一种tasklet只能运行在同一个CPU上串行执行,因此不需要spinlock保护.
7.不同的tasklet可以运行在不同的CPU上执行,因此需要进行spinlock保护,调用哪个API进行保护?
(4)workqueue+spinlock
workqueue属于线程化,但优先级仍高于普通进程。
8.同一个work在某一时间点上只能在同一CPU上运行,是不是就不需要spinlock保护?
9.不同的work访问共享资源时,由于可以运行在不同的CPU上,就需要spinlock保护,调用哪个API进行保护?
michael
2017-04-13 22:07
@michael:追加两个问题:
1.我的理解,中断也是一种抢占,它是一种异步抢占,是不是调用了preempt_disable禁止了本CPU的抢占,是不是也disable中断了?
2.所谓的抢占,是不是指同一CPU上进程、中断间争夺CPU的控制权,而两个CPU之间,不存在抢占?也就是说,运行在不同CPU上的两个线程间,不存在抢占了
John
2017-08-15 19:28
@michael:同样追加两个回答:
1.我的理解,中断也是一种抢占,它是一种异步抢占,是不是调用了preempt_disable禁止了本CPU的抢占,是不是也disable中断了?
    A:preempt_disable只是一种软件方法,达到同步的目的。而disable中断是一个涉及硬件的行为。所以diable中断是一个更底层的行为,它的结果可以影响软件,比如使scheduler没有办法执行,更不能执行preempt。
2.所谓的抢占,是不是指同一CPU上进程、中断间争夺CPU的控制权,而两个CPU之间,不存在抢占?也就是说,运行在不同CPU上的两个线程间,不存在抢占了
    A:我的理解是这里的抢占指的是进入临界区。获得CPU的控制权是手段,目的还是要进入临界区完成一些操作。
John
2017-08-15 19:20
@michael:我的理解是linuxer表达的意思是所有的临界区都是在相同的handler中共享的。比如同种softirq的handler之间或者不同softirq handler之间,他们会访问全局的变量。并不考虑softirq handler与硬中断handler(top handler)之间的临界区这种情况。
以下是我的一些理解,回答如下:
(1)中断handler+spinlock
1.同一种中断不能并发运行在多个CPU上,因此同一种中断访问时不需要spinlock保护.
    A:我的理解是你的观点是正确的。spin lock主要是防止其他的CPU进入临界区,如果这个临界区只在这个中断handler中访问的话,那么由于只有一个handler(同一种中断不能并发运行在多个CPU上),所以不需要spin lock保护。
2.如果两个中断handler运行同一个CPU上,由于新的内核disable local irq,因此这种情况不需要spinlock保护.
    A:由于中断handler执行时是关中断的,所以不存在两个中断handler运行同一个CPU上的情况。
3.如果两个中断handler运行在不同的CPU上,这种情况需要spinlock保护,且调用函数spin_lock_irqsave进行保护?
    A:两个中断handler运行在不同的CPU上,这种情况需要spinlock保护,但是并不需要关闭中断。因为中断handler执行时local cpu是关中断的。所以只需使用spin_lock就行了。
(2)softirq+spinlock
4.同一种softirq可以运行在多个CPU上,因此需要spinlock保护,调用哪个API进行保护?
    A:同1,基于linuxer原文的意思,不考虑softirq handler和硬中断handler临界区情况,所以只需要spin_lock就可以了。
5.不同的softirq可以运行在多个CPU上,因此需要spinlock保护,调用哪个API进行保护?
    A:同4。
(3)tasklet+spinlock
6.同一种tasklet只能运行在同一个CPU上串行执行,因此不需要spinlock保护.
    A:我的理解是你的观点是正确的。
7.不同的tasklet可以运行在不同的CPU上执行,因此需要进行spinlock保护,调用哪个API进行保护?
    A:只需要spin_lock就可以了
(4)workqueue+spinlock
workqueue属于线程化,但优先级仍高于普通进程。
8.同一个work在某一时间点上只能在同一CPU上运行,是不是就不需要spinlock保护?
    A:我不确定同一个work是否可以同时运行在多个CPU上。如果是的话,必须使用spin lock防止其他CPU干扰。
9.不同的work访问共享资源时,由于可以运行在不同的CPU上,就需要spinlock保护,调用哪个API进行保护?
    A:基于linuxer原文的意思,不考虑work与其他人(softirq handler,thread,top handler)共享临界区的情况,spin_lock就可以了。
ron
2017-02-27 18:27
@linuxner: 在arm32中,next和owner初始化都为0, 当第一个thread获取spin_lock的时候 汇编中 next++, 但是owner仍然为0, 做完汇编之后就会判断 这两个值是否相等。
    while (lockval.tickets.next != lockval.tickets.owner) {------------(5)
        wfe();-------------------------------(6)
        lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);------(7)
    }
由于owner从未改变所以此时岂不是一直在循环里出不来吗? 多谢!
linuxer
2017-02-27 19:23
@ron:lock->tickets.owner的值怎么会不变呢?其他thread终究会unlock从而修改owner的。
ron
2017-02-28 14:57
@linuxer:谢谢@linuxer,我的意思是 第一次获取锁的时候, next和owner初始化都为0, 当进入arch_spin_lock()的时候,next和owner都没有改变, 但是在汇编里 "add    %1, %0, %4\n" 此时next++, 后面接着就while 判断,理论上这时候是unlock的,而且锁应该是谁申请 谁释放。
spin_lock --------> 第一次进入的时候 next++, 而owner未改变,应该会while循环
do_citical()
spin_unlock
如果上述情况成立,那其他thread应该先spin_lock申请锁,此时上面的锁还在while循环。。。。
linuxer
2017-03-01 00:21
@ron:也许汇编代码影响了你的逻辑判断,我用c代码重新写过spinlock的过程(当然,这里无法保证原子操作了,不过我们主要是理解逻辑):
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
    unsigned long tmp;
    u32 newval;
    arch_spinlock_t lockval;

    lockval = lock->slock;----获得了next和owner值,
    lock->tickets.next++;----lock中的next++,lockval不变
    
如果这时候当前的号码牌(lockval.tickets.next)和owner相等,说明可以持有锁长驱直入。
    while (lockval.tickets.next != lockval.tickets.owner) {
    wfe();
    lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);---用当前spinlock中的owner值更新lockval中的owner值
    }

    smp_mb();
}
你把lock和lockval这两个变量搞混了。
ron
2017-03-01 09:34
@linuxer:@linuxer 明白了, 是我把两个变量的值混淆了, 一语惊醒梦中人啊... 非常感谢。
Jeffle
2016-11-17 17:27
你好,我用的内核版本是3.6.10,其中看到 spin_unlock对owner进行修改时并没有使用strex,而是直接令owner++,我觉得会有一个问题,那就是如果一个进程并不调用spin_lock,而是一上来直接调用spin_unlock,这里就存在一个bug,
作者的意思是“only one CPU can be performing an unlock() operation for a given lock, this doesn't need to be exclusive”,是不是说作者认为这种bug应该由编程者自己来解决,而不是自旋锁的机制本身来解决呢?

static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
-    unsigned long tmp;
-    u32 slock;
-
    smp_mb();
-
-    __asm__ __volatile__(
-"    mov    %1, #1\n"
-"1:    ldrex    %0, [%2]\n"
-"    uadd16    %0, %0, %1\n"
-"    strex    %1, %0, [%2]\n"
-"    teq    %1, #0\n"
-"    bne    1b"
-    : "=&r" (slock), "=&r" (tmp)
-    : "r" (&lock->slock)
-    : "cc");
-
+    lock->tickets.owner++;
    dsb_sev();
}
hony
2017-04-30 11:00
@Jeffle:应该是由使用者保证的,就像使用互斥锁时使用不当就会产生死锁一样道理。
randy
2016-09-08 16:24
请问下,spinlock的使用限制,除了不能阻塞性操作、耗时太久,critical section中是不是也不能开中断?对于spinlock_irq而言,内部实现为关local irq,如果critical section中开了中断是不是就会有问题?如果是的话,为啥很多资料里面没有提到这点呢?
linuxer
2016-09-09 09:00
@randy:spinlock的接口有多个,例如spin_lock、spin_lock_bh、spin_lock_irq,不同的场景,使用不同的接口。对于spin_lock而言,其实是没有关闭本地中断的需求的,因此,在进入临界区的时候,中断是打开的,如果在临界区有对中断的操作也是OK的。对于spin_lock_irq,其临界区是关中断的,因此,在临界区内当然不能打开中断,这是常识,因此没有必要提出。
randy
2016-09-09 09:30
@linuxer:了解, linuxer,thanks
simonzhang
2016-04-27 19:54
新的内核这里改变比较大,确实改善了公平性,保证了先来先得。
但是next和owner都是16 bits,最大也就是65536,如果next overflow,但是owner不变的话,可能有两个thread可以同时获得lock。不过就目前的CPU硬件规模,(如最大cores数目100?)应该不会有问题了,就是说没有65536个cpu thread去竞争这个spin lock了。
当然如果next和owner同时overflow的话也自然也不会有问题,只要不相差65536以上。
hony
2017-04-30 11:04
@simonzhang:#if (CONFIG_NR_CPUS < 256)
typedef u8  __ticket_t;
typedef u16 __ticketpair_t;
#else
typedef u16 __ticket_t;
typedef u32 __ticketpair_t;
#endif
从作者的定义看cpu数不会超过16位。
zhr2130
2016-03-02 17:59
@linuxer:问一个比较low但一直困扰我的问题。

关于spin lock(或其他同步机制如信号量,互斥锁),是如何和它要保护的共享资源(或临界区)关联起来的。是根据spin lock定义的位置么。比如要用spin lock保护一个共享的struct,那么在这个struct中添加一个spin lock的element应该是可行的。放在struct外面可以么。另外对于其它类型的共享资源,如何和spin lock关联呢?

看了很多参考资料,都只是介绍在进入临界区时要获得spin lock,却没有说这个spin lock应该放在哪。难道这个spin lock 可以随便定义在任何位置么??

非常感谢
wowo
2016-03-02 18:48
@zhr2130:其实您问这个问题的时候应该已经有答案啦,即iushi随便放了,这完全是软件结构的事情了,和spin lock无关的。或者换个思路,如果要保护的仅仅是一个变量,没有结构体,spin lock放哪里呢?
zhr2130
2016-03-03 23:15
@wowo:@wowo,那意思就是在进临界区时,只要获取一个kernel中任意一个spinlock就行,只要这个spinlock可以获取到.添加新code时增加的新spinlock,完全是因为我们不清楚旧的spinlock有谁在用,如果用旧有的spinlock可能会造成死锁.是这样么.
wowo
2016-03-04 11:32
@zhr2130:是的。
zhr2130
2016-03-07 11:16
@wowo:@wowo,终于明白了,非常感谢
郭健
2016-03-04 12:52
@zhr2130:其实这和数据结构的设计有关,如果你的数据是全局范围的,那么多半定义如下:
1、struct xxxx foo。foo就是多个thread并发访问的资源
2、DEFINE_SPINLOCK(foo_lock)。foo_lock就是控制并发访问foo这个全局资源的spin lock,不在struct xxxx,应该和foo这个需要控制并发的资源定义在一起。

如果你的数据是局部的,比如struct xxxx是动态分配的,有A B C D.......等等若干个实例,而并发控制如下:
1、对A资源的并发是需要控制在线程t1、t2、t3.....之间
2、对B资源的并发是需要控制在线程t1、t2、t3.....之间
....
这时候,定义全局的spinlock显然不合适,最好的设计是相关的数据放在一起,因此,spin lock应该放在struct xxxx中,成为其成员。
zhr2130
2016-03-07 11:18
@郭健:非常感谢,这下就清楚了
zhr2130
2016-03-08 08:54
@郭健:@郭健:不好意思还有个问题,如你描述的第一种情况,“foo_lock就是控制并发访问foo这个全局资源的spin lock,不在struct xxxx,应该和foo这个需要控制并发的资源定义在一起。”虽然它们定义在一起,可它们并没有相关性。那么其它进程要访问该全局数据时,并不一定要获取foo_lock,才能访问。可这样就没有定义锁的意义了吧。还是说因为它们做为全局变量定义在一起,所以spin lock把它们所在的存储区整个保护起来了。非常感谢
郭健
2016-03-08 18:52
@zhr2130:其实我不太清楚你的问题,不过我强调2点:
1、foo_lock和foo的定义相关性非常,非常....的大,对于一个代码洁癖的工程师而言,他们必须在源代码中定义在一起。
2、访问foo必须获取foo_lock
zhr2130
2016-03-08 21:20
@郭健:@郭健
不好意思,我对这块的概念比较模糊.其实我的问题就是foo_lock和foo是怎么关联到一起的.特别是foo_lock并未定义在foo结构里的时候.
1、foo_lock和foo的定义相关性非常,非常....的大,
它们的相关性是如何产生的,我没有找到它们能关联在一起的方法.spinlock_init的过程也没有把锁和相关资源关联起来啊.

非常感谢你的耐心回答
郭健
2016-03-08 22:37
@zhr2130:我还是换一个实际的例子好了,比如在clocksource.c文件中,有如下代码:

static LIST_HEAD(clocksource_list);
static DEFINE_MUTEX(clocksource_mutex);

clocksource_list就是共享的资源,而clocksource_mutex就是保护这个资源的锁。任何对clocksource_list这个资源的访问都必须获取clocksource_mutex,以便确定在任何时候,系统只有一个thread在临界区,从而不会产生竞态条件:

    mutex_lock(&clocksource_mutex);
    访问临界区的代码
    mutex_unlock(&clocksource_mutex);

这里的mutex并不会定义在struct clocksource中,因为mutex控制的资源是全局性的,是系统所有clocksource的实例构成的链表。
zhr2130
2016-03-08 23:40
@郭健:@郭健:

又仔细看了看文章终于搞明白了,非常感谢你的解答
坚持到底
2015-11-20 17:12
hi,

我有个疑问:

ticket spinlock 的实现上,只在初始化的时候把 owner, next 置为 0, 就一直 ++, ++,什么时候会被清空?理论上 16bit 的数据 65535 次后就溢出了。
linuxer
2015-11-20 18:46
@坚持到底:即便是溢出了,整个逻辑还是对的,你可以自己再分析一下
坚持到底
2015-11-23 10:16
@linuxer:是的。请问 wowotech 有群不?方便大家交流一下。
wowo
2015-11-24 08:47
@坚持到底:这里有一些联系方式:http://wowotech.net/contact_us.html

发表评论:

Copyright @ 2013-2015 蜗窝科技 All rights reserved. Powered by emlog