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 自旋锁

评论:

坚持到底
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
descent
2015-11-10 13:45
請問一下禁止中斷的話, 有沒有可能漏掉中斷, 若漏了中斷, 是不是有可能會發生什麼問題呢?ex: 資料接收不完整之類的。
wowo
2015-11-10 16:48
@descent:中斷被禁止的過程中,如果來一次可以觸發中斷的事件,是不會丟的,下一次打開中斷之後,會接著觸發中斷。如果來多次,要看相應的硬體行為了。
另外,一般中斷被禁止的時間不會很長,那些硬件模塊的buffer足以應付了。
cinmun
2015-07-29 11:40
spin lock相关的接口API如下: 这里 unlock的好多函数名都是错误的
linuxer
2015-07-29 12:06
@cinmun:多谢指正,晚上回家就修改之
cinmun
2015-07-29 11:35
我想问楼主 如果我在操作gpio口的时候 用spinlock 在多核cpu里是 锁 当前核  还是所有核。  为什么 打开spinlcok的时候 后台播放音乐会卡顿暂停呢
linuxer
2015-07-29 12:11
@cinmun:spinlock 当然是 lock all cpu core

你确定 后台播放音乐会卡顿和spinlock相关吗?你的spinlock是否配合其他的内核同步机制?例如关中断什么的,能否进一步描述如何使用spinlock的?
维尼
2015-07-29 12:34
@linuxer:我用的终极spinlock-》spin_lock_irqsave 我锁定大约200ms 如果程序一直跑 那就一直锁定  后台放音乐卡顿 是不是就是内核不能去解码音乐了
linuxer
2015-07-29 19:36
@维尼:用spin_lock_irqsave锁定200ms实在是太残暴了,你的临界区真正的那么长吗?如果那么长,完全考虑其他的内核同步机制了,例如semaphore或者mutex

如果后台放音乐的进程要竞争这个残暴的临界区,那么卡是一定的了
维尼
2015-07-30 08:49
@linuxer:我是在操作gpio口的时候用spin_lock_irqsave 用其他同步semaphore或者mutex  io都有延迟 或者错误
dadanio
2015-11-11 09:56
@linuxer:spinlock我的理解是锁住当前cpu。 spinlock其实就是CPU一直循环查询lock状态,如果是锁住所有的cpu,那么就有可能导致其他cpu没有机会释放spinlock从而导致当前cpu一直忙。不知道理解对不对
linuxer
2015-11-11 12:16
@dadanio:spinlock只是锁住临界区,允许一个thread进入而已。
tigger
2015-06-15 13:39
如果我只知道,arch_spinlock_t里面的owner跟next,我有方法知道是那个进程拿到了锁么??或者说哪个core。我想到有一种情况
比如我现在有8个core,core 1到core7 都在等同一把锁。owner 跟 next相差7,说明有7个thread在等,根据spinlock的原理,那么肯定是那个不再等的core上面拿了锁。
但是我又如何证明锁是被哪个core拿了呢?
再仅有owner跟next的情况下,是不是没法确定,必须打开debug的宏才知道呢?
bear20081015
2015-06-15 21:02
@tigger:我理解应该没办法知道。除非恰好这个spinlock是全局变量,然后可以通过system.map知道lock的名字。再看看code看能不能知道是哪段code拿到的。局部变量只能打开debug宏了。
linuxer
2015-06-15 22:46
@tigger:仅有owner跟next的情况下应该是无法知道持有锁的是哪一个core。不过你为何要知道哪一个core持有锁呢?具体的应用场景是什么?
tigger
2015-06-16 18:16
@linuxer:因为会出现一种情况,几个core都在等同一把锁。这个时候就要知道哪个core拿锁。是不是core出现了问题,没有释放
wowo
2015-06-02 13:10
@bear20081015: cluster的power down以及醒来,是要经过arm trust firmware哦。
bear20081015
2015-06-02 13:17
@wowo:是的,但是arm trust firmware是在ARMV8之后才有的。我的意思是说在之前的armv7架构上,cluster的power down以及醒来的初始代码还是要有类似于bakery lock的锁吧,只不过不像ATF里面那样是标准的,可能是各个vendor自己实现了吧。
wowo
2015-06-02 13:53
@bear20081015:嗯,这就清楚了。
另外关于RPM的我要先看看,另外你看到的kernel版本是哪个?电源管理是kernel比较活跃的模块,一直在进化,有问题也是可能的。
bear20081015
2015-06-03 13:51
@wowo:我的版本的3.14的。但我看到最新的3.18里面我提的这个问题牵涉到的相关代码似乎没有什么变化,所以3.18里我相信也会有这个问题的。
bear20081015
2015-05-29 14:18
楼主,请问ARM里面spinlock的实现究竟是否依赖于L1和L2 cache呢?我看了下ldr和str(即ldrex和strexeq)的文档,感觉不是很明白。或者这样说,在cache被disable的情况下,能直接调用spin lock/unlock么?还是需要自己去实现spinlock锁?谢谢!
linuxer
2015-05-29 18:30
@bear20081015:当然不会,spinlock依赖的是对内存中的一个u32数据,怎么会和cache是否enable or disable相关呢?能说明你对ldrex和strex哪些不明白?我好象还没有搞清楚你要问什么问题
bear20081015
2015-05-30 00:48
@linuxer:不好意思,我可能没有描述清楚。这是从ARM网站上看到的描述(http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dht0008a/CJAGCFAF.html):
Each processor that supports exclusive accesses has a local monitor. Exclusive accesses to memory locations marked as Non-shareable are checked only against this local monitor. Exclusive accesses to memory locations marked as Shareable are checked against both the local monitor and the global monitor.
我个人理解,ldrex和strex指令的实现是依赖于local monitor和global monitor组成的状态机的,而这两者需要在L1和L2 cache中实现。那么当cache被disable的话这两个monitor也就不能工作了吧?这时候是不是就不能使用strex和ldrex指令了?
linuxer
2015-06-01 09:12
@bear20081015:你摘录的英文都是在描述Shareability,但是你的问题却在说cache,你是不是把Shareability和Cacheability搞混了?
bear20081015
2015-06-01 10:43
@linuxer:linux,我摘录的那一段都是在描述arm中如何支持exclusive access的。我的理解是:spinlock从本质上来说确实就是内存中的一个u32数据,但如何支持ldx和stx这两条指令的原子性呢?硬件上肯定要有东西来支撑它,我理解就是local monitor和global monitor。正如这句话“Each processor that supports exclusive accesses has a local monitor.”。进一步从arm的文档中看,local和global monitor是实现在L1和L2 cache中的。所以我才怀疑当L1,L2 cache被disable掉的时候,ldx和stx指令都无效了,也就不能使用spinlock了。我这两天看了下ARM的trust firmware里的bakery lock,我不确定自己理解的对不对,但是看起来就是一个软件上的锁似乎就是为了代替在cpu刚上电时cache关掉时各个CPU的race condition,如果能够直接用spinlock的话似乎就没这个必要了吧。
linuxer
2015-06-01 12:34
@bear20081015:local和global monitor是实现在L1和L2 cache中的
---------------------------------------------------
我看原文上是说local和global monitor是实现在L1和L2 memory system中,我是觉得local timer以及global timer应该是和L1和L2 cache是否enable或者disable无关,即便是L1和L2 cache disable了,local monitor和global monitor也应该是可以工作的

当然,这也是我的猜测而已,仅供参考
bear20081015
2015-06-01 15:34
@linuxer:我个人还是感觉是有点关系的,否则不可能arm trustfirm要多此一举去实现一个软件的spinlock锁,而且这个锁就是在cache没有enable的情况下使用的。但还是感谢你耐心的回答!另外多问一句,我看到你们的pm runtime的系列文章似乎只开了个头,我最近在这一块有点疑问,不知道你们后续文章有时间表么?或者就在评论区里面大家讨论一下?
wowo
2015-06-01 20:18
@bear20081015:我来插一句:
ARM架构提供了non-blocking的同步机制(也称作synchronization primitives),确实比较高效、实用。但该机制需要一些额外机制的支撑,也就是您所提到的local monitor和global monitor。monitor特别是global monitor的实现, 和cache、MMU等没有直接关系。但是,对那些特殊位置的memory,如non-cacheable、cache-disable等,需要在PE之外实现monitor功能,而并不是所有厂商都会做这些事情。
对arm trusted firmware来说,它无法假设厂商的具体行为,因此为了确保同步的有效,就不得不使用软件的互斥机制(bakery lock)。
而对Linux kernel而言,kernel是在单核、preemptive disable的情况下启动的,等到真正使用spin lock的时候,一切都准备就绪了,因此也就没什么问题了。

具体可参考DDI0487A_d_armv8_arm.pdf:
For Shareable memory locations, in some implementations and for some memory types, the properties of the global
monitor require functionality outside the PE. Some system implementations might not implement this functionality
for all locations of memory. In particular, this can apply to:
• Any type of memory in the system implementation that does not support hardware cache coherency.
• Non-cacheable memory, or memory treated as Non-cacheable, in an implementation that does support
hardware cache coherency.
In such a system, it is defined by the system:
• Whether the global monitor is implemented.
• If the global monitor is implemented, which address ranges or memory types it monitors  

...

Therefore, architecturally-compliant software that requires mutual
exclusion must not rely on using the Load-Exclusive/Store-Exclusive mechanism, and must instead use a software
algorithm such as Lamport’s Bakery algorithm to achieve mutual exclusion.
wowo
2015-06-01 20:23
@bear20081015:至于runtime PM,确实只是开了一个头。因为RPM的使用比较简单,但内部实现涉及到的知识点就多了,因此还没有时间去写。可以直接评论交流,非常欢迎~~~~
bear20081015
2015-06-02 10:53
@wowo:wowo,我最近在梳理pm runtime和suspend之间的关系。碰到有一种case有点不太理解,请帮我看看:
1.一个设备在系统suspend之前处于RPM_SUSPENDED状态;此时dev->power.usage_count=0,dev->power.runtime_state = RPM_SUSPENDED;
2.在dev->prepare函数, system suspend框架会调用pm_runtime_get_noresume,此时dev->power.usage_count=1, runtime_state仍然是RPM_SUSPENEDED;
3.接着,system suspend会调用device_suspend_late,这个函数中调用了__pm_runtime_disable()。如果恰好在此之前,有人希望通过pm_runtime_get来resume这个设备,那么就会把一个pending的resume request放到pm runtime work queue上;此时usage_count=2, runtime_state = RPM_SUSPENDED;
4. 在__pm_runtime_disable中,函数会调用__pm_runtime_barrier,这会取消step3中的pending resume请求。 但不会将usage_count减1。此时usage_count=2, runtime_state = RPM_SUSPENDED。
5. 当系统resume回来的时候,它会调用pm_runtime_put来将usage_count减1。 此时usage_count=1, runtime_state = RPM_SUSPENDED。

可以看到,经过这几个步骤后,device的runtime_state和usage_count出现了不匹配的情况,runtime_state=RPM_SUSPENDED的时候usage_count应该是0,但现在变成了1。我做的实验也是这样。不知道这算不算runtime的bug呢?还是我上面哪一步有问题?请指教,谢谢!
bear20081015
2015-06-02 10:58
@wowo:谢谢!看起来非常合理啊。唯一有点疑问的:“而对Linux kernel而言,kernel是在单核、preemptive disable的情况下启动的,等到真正使用spin lock的时候,一切都准备就绪了,因此也就没什么问题了”。我的理解是确实在启动情况下没什么问题,但是对于SMP来说,当cluster进入到power down的状态,如果有多个cpu同时醒来的话,那么还是有竞争关系,仍然需要类似于spinlock的锁来保护吧,如果这时候local/global monitor还不能用的话。
linuxer
2016-07-18 12:12
@linuxer:之前对于Exclusive access instructions理解有误,重新整理如下:
1、Exclusive access instructions不适合用在device memory中,基本上在控制多个thread访问某个外设的时候,可以使用基于normal memory的资源控制方法(例如spin lock或者mutex),而不是依赖Exclusive access instructions。在有些系统上,对device memory使用Exclusive access instructions会产生bus error。
2、对于normal memory,可以分成Shareable memory regions和Non-Shareable memory regions。对于前者,需要local monitor和global monitor,对于后者,仅仅需要local monitor
3、低于local monitor和global monitor而言,不同的系统实现也不同。对于特定的系统,如A9双核SOC,local monitor在L1 cache中,global monitor在SCU中。
4、在MMU on(告知Shareable属性)和cache on(让monitors on)的情况下,一切工作应该是正常的,local monitor和global monitor都是正常工作的,否则,应该Exclusive access instructions不能正常工作
新手上路
2015-05-21 14:02
我刚开始拜读大牛文章。很有些茅塞顿开的感觉。下面一段没看懂,能麻烦解释一下为什么要disable么?
“使用spin lock+禁止本地中断当然是可以达到保护共享资源的效果,但是使用牛刀来杀鸡似乎有点小题大做,这时候disable bottom half就OK了。”
我感觉spin lock是在isr handle里面做的,因为很快,不需要放到bottom half里面。我的理解是否有误?
linuxer
2015-05-21 23:22
@新手上路:到底用哪一种方式的锁机制是由访问共享资源的上下文决定的,当然,我们希望访问spin lock的共享资源执行比较快,例如某一个counter变量的操作。但是,你不能保证对这个counter变量的访问总是在中断handler中执行,因为对该counter的操作可能依赖于一系列比较耗时的操作,需要推到bottom half中执行,因此,驱动代码中的逻辑就是在bottom half中执行:
1、首先进行一系列比较耗时的操作
2、counter++

此外,还有进程上下文操作这个counter变量,这时候,就是需要用spin_lock_bh和spin_unlock_bh这样的保护机制
新手上路
2015-05-22 05:36
@linuxer:谢谢大牛指点。没想到回复这么快。

我理解这句话,“使用spin lock+禁止本地中断当然是可以达到保护共享资源的效果,但是使用牛刀来杀鸡似乎有点小题大做,这时候disable bottom half就OK了。”  就是用spin lock的时候,如果case 很简单, 就可以抛弃bottom half了对么?
linuxer
2015-05-22 12:21
@新手上路:不是这个意思。如何使用锁的机制来保护临界区始终是和场景相关,我们假设访问共享资源的thread包括:

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

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

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

这时候,使用spin lock+禁止本地中断当然是可以达到保护共享资源的效果,但是disable中断会影响系统的中断延迟。在这种场景下,最适合的策略是:使用spin lock+禁止bottom half的方法。
新手上路
2015-05-24 13:40
@linuxer:受教了! 我的基本概念还有待加强。
tigger
2015-04-24 13:32
等这样一篇有干货的文章,足足从3月26号等到4月22号
不过值啦,哈哈。每一篇都能学到好多东西
linuxer
2015-04-26 12:07
@tigger:呵呵~~~也是没有办法的事情,毕竟是业余时间搞,更重要的是家庭原因,还需要照顾家庭,和孩子玩...
不过,在陪孩子上早教的时候,看到教室中的一句荀子的话还是很有道理的:不闻不若闻之,闻之不若见之,见之不若知之,知之不若行之。我把自己的理解的知识整理出来也勉强算是到了“见之”这个阶段,真正掌握还需要“行之”
同样的道理,如果读者有缘看到这份文档也就是到了“闻之”阶段,离“知之”和“行之”还是有一段距离。
拽一段古文,与tigger同学共勉,哈哈!
tigger
2015-04-27 13:41
@linuxer:我在想,会不会增加这样的操作比较好。
比如你看到比较好的文章,推荐出来,
这样就不限于你自己写了,
当然我希望你推荐英文的文档,国内的文档作者太不负责任了。
与其看到错误的文档,不如不看~~~~
ps:我这样说的原因是,我有很深的体会,英文的文档,我总是找不到我想要看的,总找不到有很多干货的,要不就是我的渠道有问题。
linuxer
2015-04-30 00:48
@tigger:我基本上都是看git的log,有时候也会看lwn上的一些文档,还有就是stackoverflow上的一些问题解答。推荐英文文档当然没有问题,不过我上面的话主要是委婉催促你写点什么,哈哈,真的,相信我,越写越聪明
tigger
2015-04-30 08:37
@linuxer:哈哈 ok
tigger
2015-04-24 11:22
semaphore可以允许多个thread进入
这个怎么理解?

另外64位的spinlock 好像窝窝写过一次 在wfe wfi文档里面
linuxer
2015-04-24 12:12
@tigger:mutex和spin lock都是允许一个thread进入临界区的lock机制。
semaphore可以允许多个thread进入。就好像九毛九有10张桌子,当然允许10个人(thread)进入,当第11人到来的时候,只能等待了(thread将无法获取锁从而挂入等待队列,进入睡眠)。

不停的spin是对电源管理是一个硬伤,因此ARM处理器提供了WFE指令,从而让准备获取spin lock的那个thread不需不停的spin,只需要调用WFE指令,进入低功耗状态,其他处理器会在unlock的时候会触发唤醒动作的。我文档中引用了那份专门描述WFI WFE的文档,呵呵~~~
tigger
2015-04-24 13:13
@linuxer:我把semaphore 看成了mutex
还在纳闷呢

发表评论:

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