linux驱动之并发与竞态

2020-06-19  本文已影响0人  wipping的技术小栈

一、前言

在应用程序下经常会遇到 多线程并发访问同一资源 的问题，Linux 提供了多种机制来解决这一问题。在 Linux设备驱动 中也同样有类似问题，即 多个进程多共享资源的访问。并发访问会导致 竞态。一个好的驱动程序可以良好地解决这一问题，本文将整理并记录当前内核中的多种 并发访问机制 。

二、并发

并发(Concurrency) 是指 多个 执行单元 并行执行，且对某一 共享资源 进行访问，这种操作容易导致 竞态。
竞态 一般存在下面多种情况：

解决 竞态问题 的途径：保证对 共享资源 的 互斥访问，即一个 执行单元 访问 共享资源 时，其他 执行单元 被 禁止访问。共享资源 也被称为 临界区(Critical Sections)。

设备驱动程序 一般可以采样下面的方法来进行 互斥访问：

2.1 编译乱序和执行乱序

2.1.1 编译乱序

现代的 高性能编译器 在 目标代码优化 上具备对指令进行 乱序优化 的能力。编译器 对 访问内存的指令进行乱序，可以实现以下效果：

解决 编译乱序 问题，可以使用 编译屏障。设置 编码屏障 可以保障 屏障之前的语句不会在屏障之后运行。

编译屏障代码如下：

#define barrier() __asm__ __volatile__("": : :"memcory")

看看下面的代码例子：

#include <stdio.h>
int main(int argc, char* argv[])
{
    int a = 0, b, c, d[4096], e;

    e = d[4095];
    b = a;
    c = a;
    printf("a:%d, b:%d, c:%d, e:%d\n", a, b, c, e);
    return 0;
}

我们使用 O2优化 并查看其 反汇编：

arm-linux-gnueabihf-gcc -O2 compile_optmz.c -o compile_optmz
arm-linux-gnueabihf-objdump -D compile_optmz > compile_optmz.S

<main>:
    push    {r4, lr}
    sub.w   sp, sp, #16384  ; 0x4000
    sub     sp, #8
    movw    r0, #1104       ; 0x450
    add.w   r3, sp, #16384  ; 0x4000
    movt    r0, #1
    adds    r3, #4
    ldr     r4, [r3, #0]
    movs    r3, #0//语句 a = 0
    mov     r2, r3//语句b = a
    mov     r1, r3//语句c = a
    str     r4, [sp, #0]//语句e = d[4095]
    blx     102e4 <printf@plt>
    movs    r0, #0
    add.w   sp, sp, #16384  ; 0x4000
    add     sp, #8
    pop     {r4, pc}
    nop

可以看到代码中出现了乱序，我们再试试 加上 编译屏障

#include <stdio.h>

#define barrier() __asm__ __volatile__("": : :"memory")

int main(int argc, char* argv[])
{
    int a = 0, b, c, d[4096], e;

    e = d[4095];
    barrier();
    b = a;
    c = a;
    printf("a:%d, b:%d, c:%d, e:%d\n", a, b, c, e);
    return 0;
}

同理使用 O2优化 并查看其 反汇编：

arm-linux-gnueabihf-gcc -O2 compile_optmz.c -o compile_optmz
arm-linux-gnueabihf-objdump -D compile_optmz > compile_optmz.S

<main>:
    push    {lr}
    sub.w   sp, sp, #16384  ; 0x4000
    sub     sp, #12
    add.w   r3, sp, #16384  ; 0x4000
    adds    r3, #4
    ldr     r2, [r3, #0]
    movs    r3, #0 //语句a = 0
    movw    r0, #1104       ; 0x450
    str     r2, [sp, #0] //语句e = d[4095]
    mov     r1, r3//语句b = a
    mov     r2, r3//语句c = a
    movt    r0, #1
    blx     102e4 <printf@plt>
    movs    r0, #0
    add.w   sp, sp, #16384  ; 0x4000
    add     sp, #12
    ldr.w   pc, [sp], #4

可以明显看到，之前被乱序的语句恢复正常。

2.1.2 执行乱序

乱序执行(Out-of-Order-Execution) 是 CPU处理器 运行时的一种 策略，高级的CPU根据自身缓存的特性，将访问内存的指令 重新排序执行。一般有以下策略：

由于以上原因，CPU 未必会按照 汇编指令 进行执行。

单核CPU 和 多核CPU 对 乱序执行 的结果是不同的。在说明影响之前需要先知道一个概念 依赖点，即 后面的指令依赖于前面指令的执行结果。

单核CPU 遇到 依赖点 是会进行等待，所以 乱序过程 并不会表现出来了，而 多核CPU(SMP) 的 单一个核 在遇到 依赖点 也会进行等待，只是每个核之间的等待对其他核来说 不可见。由此就会造成数据上的错乱。代码例程如下：

/* CPU0执行 */
while(0 == f)
  printf("%d\n", x);

/* CPU1执行 */
x = 42;
f = 1

以上的代码打印出来的 x 未必会是 42。因为 乱序执行 的原因，f = 1 语句可能会先执行，此时 x 的值为 0。

为了解决 内存行为 在多核之间不可见的问题，需要引入一些内存屏障的指令来保证 内存访问 的顺序进行。如下所以：

DMB 和 DSB 的区别：
DMB 作用的范围仅仅是 内存访问行为，而 DSB 的作用范围是 所有指令，所以 DSB 的范围比 DMB 要大得多。

对于一些 外设 来说，需要保证 读写寄存器的顺序，但因为 乱序执行 的原因，又不能保证这一点。所以在该场景下，Linux 定义了一些 读写宏 和 屏障宏 来保证这一点，如下：

在内核中 readl_relaxed() 和 readl()、writel_relaxed() 和 writel() 的区别在于 有读写屏障，如下所示：

/* arch/arm/include/asm/io.h */
#define readb(c)        ({ u8  __v = readb_relaxed(c); __iormb(); __v; })
#define readw(c)        ({ u16 __v = readw_relaxed(c); __iormb(); __v; })
#define readl(c)        ({ u32 __v = readl_relaxed(c); __iormb(); __v; })

#define writeb(v,c)     ({ __iowmb(); writeb_relaxed(v,c); })
#define writew(v,c)     ({ __iowmb(); writew_relaxed(v,c); })
#define writel(v,c)     ({ __iowmb(); writel_relaxed(v,c); })

2.2 原子操作

原子操作 可以保证对某一个 整型数据 的修改是 排他性的。Linux 提供了 2种原子操作，分别为：

ARM 使用 独占指令ldrex和strex 来实现 原子操作。

下面的例子展示了 Linux内核 如何使用 独占指令 实现 原子加法：

static inline void atomic_add(int i, atomic_t *v)           
{                                   
    unsigned long tmp;                      
    int result;                         
                                    
    prefetchw(&v->counter);                     
    __asm__ __volatile__(
    "1: \n"
    "ldrex %0, [%3]\n" //读取v->counter的只，并设置对应的独占访问标志
    "add   %0, %0, %4\n"
    "strex %1, %0, [%3]\n"//将进行加法后的值存在内存中。如果失败 tmp 为 1，成功 tmp 为 0
    "teq   %1, #0\n"//判断 tmp 的值是否为0
    "bne   1b"//如果 tmp 为 1，则跳转到开头重新执行。如果为 0 则完成操作退出
    : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)
    : "r" (&v->counter), "Ir" (i)
    : "cc");
}

Linux 定义了以下接口用于 原子操作：

2.3 自旋锁

在 内核 中有 信号量 、互斥量 等同步原语，但是这些 同步机制 会造成 进程切换，如果多个 CPU 的多个进程 频繁访问 同个 共享资源，会造成进程频繁的 换入换出，从而降低新能。
自旋锁 的目的就在于 短时间内进行轻量级锁定，不会导致进程切换。这样就可以解决 进程因频繁访问共享资源而导致切换造成的性能问题。

这里需要注意到，自旋锁 用于 多核多进程，因为 单核 情况下，始终只有一个 进程 占用 CPU，此时访问 共享资源 一定需要进行 进程切换，所以 自旋锁 的意义并不大。而且在 单核 下使用 自旋锁 会带来一定的风险。

所以需要将 自旋锁 分为 单核 和 多核 进行讨论：

综上所述，自旋锁在内核中主要用来防止多CPU并发访问临界区并造成抢占竞争

上面提到 自旋锁在不能休眠的代码中使用(比如中断处理或者无法休眠的进程)。因为如果此时调用 任何会引起调度的函数，比如 kmalloc、copy_to/from_user 等。因为 自旋锁 会对处理器进行 禁止抢占 处理，如果此时 休眠引发调度 会导致 处理器即无法调度其余进程，又无法继续往下执行释放锁，最终导致内核死锁

自旋锁 的 粒度 越小越好，大粒度 的 自旋锁 会影响性能。

自旋锁 在内核中有以下接口：

当 驱动程序 拥有 自旋锁 时，如果此时发生 中断 并且在 中断服务函数 中去获取该锁，那么就会造成 CPU 永远都在 中断服务函数 中自旋，不会跳出。导致 CPU 无法继续运行任何程序。所以在一般情况下，在持有 自旋锁 时，需要 禁止本地的CPU中断。接口如下所示：

一般在 驱动程序 中使用 spin_lock_irq/spin_lock_irqsave，而在 中断服务函数 中使用 spin_lock。

在 并发访问共享资源 时，多个 执行单元 同时进行 读取 是允许的。由此 自旋锁 也引发出了 自旋读写锁。读写锁 允许 多个进程同时读，单个进程进行写，且读写操作互斥，即读操作会被写操作阻塞，写操作也会被写操作阻塞。有兴趣的读者可以自行了解。

2.4 顺序锁

前面提到的 读写锁，其 读操作 和 写操作 没有 优先级 之分，即 读操作与写操作之间、写操作和写操作之间会进行阻塞。为了提高 写操作 的优先级，引入了 顺序锁。当然了，顺序锁 的 写操作 还是 互斥的。

顺序锁 允许 读操作 进行的时候直接进行 写操作，即 写操作不会被读操作阻塞。
其原理为当 读操作 正在进行时，写操作 可以直接修改共享资源。读操作 完成后需要判断 当前是否有进行过写操作，如果进行过 写操作 则需要再重新进行 读操作。

其接口如下：

下面的代码片段展示 顺序锁 的基本用法：

/* 写操作 */
write_seqlock(seqlock)
......//写操作代码
write_sequnlock(seqlock)

/* 读操作 */
do{
  seqnum = read_raedbegin(seqlock);
  ......//读操作代码块
}while(read_seqretry(seqlock, seqnum))

2.5 读-复制-更新(RCU)

RUC 即 读-复制-更新(Read-Copy-Update) ，这并不是一种 锁，但能够起到同步 共享资源访问 的作用。

RCU 的原理是 写执行单元 在访问 共享资源 前会 复制一个副本，然后对 副本 进行修改，最后等到合适的时机使用 回调机制 把 副本 更新到 共享资源。通常这个等待合适时机的时期称为 宽限期(Grace Period)

宽限期的意义在于： 线程执行 修改操作 后，它必须等待所有 在宽限期开始前已经开始访问共享资源 的 读线程 结束访问才可以进行 销毁操作。

宽限期 可能比较抽象，在网上流传的这幅图可以帮助理解：

宽限期

PS：图中的 删除 和 销毁 属于 写线程
步骤如下：

  1. 写线程 执行 删除操作，将 节点 移出 链表，从此刻起 进入宽限期。
  2. 线程1 和 线程2 在 宽限期 之前已经开始访问，但还未完成 访问操作。所以需要等待它们完成访问后才能执行 销毁操作。
  3. 线程3、线程4 和 线程6 都分别完成了 访问操作，不需要进行同步。
  4. 线程5 必须等待 宽限期结束 和 写线程 完成修改后才能继续访问。

下面通过 《Linux设备驱动开发详解》 中的一段代码进行描述：

struct foo{
  struct list_head list;
  int a;
  int b;
  int c;
};

/* 访问链表节点p */
p = get_node(head, N);

/* 创建副本 */
q = kmalloc(sizeof(*p), GFP_KERNEL);

/* 拷贝节点p */
*q = *p;

/* 修改节点q */
q->b = 2;
q->a = 3;

/* q节点替换掉p节点 */
list_replace_rcu(&p->list, &q->list);

/* 等待宽限期结束 */
synchronize_rcu();

/* 释放节点p */
kfree(p);

从上面的代码可以看出 RCU 的流程：

  1. 进程A 获取 节点p
  2. 创建新的 节点q，并完成拷贝
  3. 修改 节点q，并完成 替换
  4. 等待 宽限期 结束，即 所有读操作完成
  5. 释放 节点p

RCU 的优点在于 允许多个读执行单元同时访问共享资源，也允许多个读写执行单元同时访问共享资源。
但 RCU 在 多个写执行单元之间的同步开销比较大，因为它需要 复制副本、延迟释放数据结构 还需要 使用锁机制同步其他写操作。
因此 RCU 并不能代替 读写锁，因为 写操作 多的时候损耗的性能更加多。
按照笔者的总结：RCU 可以提高 读写性能，但 写写同步开销比较大。

RCU 的接口如下：

2.6.1 订阅-发布机制

1、发布

前面提到过 编译乱序 和 执行乱序 会提高性能，但在某些场景下 RCU 并不希望发生这样的事情以免造成错误。如下代码所示：

struct foo{
  struct list_head list;
  int a;
  int b;
  int c;
};
strct foo* gp;

/* 步骤1. 对gp进行操作 */
......

strct foo* old_gp = gp;

/* 步骤2. 创建副本 */
p = kmalloc(sizeof(*p), GFP_KERNEL);
p->b = 2;
p->a = 3;

/* 步骤3. 为gp赋新值p */
gp = p;

/* 步骤4. 释放节点p */
kfree(old_gp );

一般情况下我们希望 步骤2 比 步骤3 先执行，但由于 编译乱序 和 执行乱序 的存在，有可能导致 步骤3 比 步骤四 先执行，这样就会导致程序错误甚至崩溃。所以我们需要使用屏障来阻止 乱序行为。

由此引出接口 rcu_assign_pointer，代码如下所示：

#define rcu_assign_pointer(p, v) \   
         __rcu_assign_pointer((p), (v), __rcu)  
  
#define __rcu_assign_pointer(p, v, space) \   
         do { \  
                 smp_wmb(); \  
                 (p) = (typeof(*v) __force space *)(v); \  
         } while (0)

可以看到 rcu_assign_pointer 使用了屏障 smp_wmb 来保证了代码的执行顺序。这样就可以保证 读执行单元 看到的是 rcu_assign_pointer 之前的内存，而 写端 使用 rcu_assign_pointer 则是可以看成是 发布 了新的 gp。

2、订阅

与 发布 同理，我们希望在 读取 时不会发生 乱序执行 的情况，以避免读到的是错误的数据。此时可以使用接口 rcu_dereference 来保证读到的数据不发生错误。

使用 rcu_dereference 接口的 读端 可以看成是 订阅 了 RCU保护的数据。

PS：由于笔者查到到的源码与 参考资料 的有些不同，鉴于 科学且严谨 的精神，笔者不对该接口的源码进行阐述，有兴趣的笔者请自行查阅。

2.6.2 RCU链表

Linux内核 中有专门的 RCU链表 接口，使用这种接口可以在 RCU机制 的保护下对 链表 进行访问。接口如下：

其应用代码一般如下：

/* 写端 */
list_add_rcu(list, head)

/* 读端 */
rcu_read_lock()
list_for_each_entry_rcu(p, head, list){
  /* do something */
}
rcu_read_unlock()

2.7 信号量

信号量(Semaphore) 是操作系统中最典型的 同步机制，在 应用层 和 内核驱动 都存在这种机制。
信号量的值可以是 大于0 的数值，其数值的增减与 PV操作 对应：

其接口如下：

对于 生产者-消费者模型，使用 信号量 可以达到比较好的同步效果。

2.8 互斥体

信号量 已经能够达到 同步互斥 机制了，为什么还需要 互斥体 呢？
正确来讲，信号量 是允许 多个执行单元 同时访问 共享资源。而 互斥体 仅允许 1个线程 访问 临界区域，具有 唯一性 和 排他性。

同理 互斥体 在应用层中也被广泛使用，而 Linux内核 也提供下面的接口用于 互斥机制：

互斥体 和 自旋锁 都是解决 互斥问题 的基本手段，它们之间的选择原则一般如下：

  1. 当 临界区 比较时，应使用 互斥锁，反之使用 自旋锁
  2. 互斥体 保护的 临界区 可以包含 引起阻塞 的代码，而 自旋锁 则不能含有 阻塞代码。
  3. 互斥体 运行在 进程上下文，如果 临界区 在 中断 中运行，则只能使用 自旋锁

2.9 实时互斥体

在有些场景，单纯使用 互斥体 会引起 进程优先级反转 的问题。通俗来说就是 低优先级进程 抢占高优先级进程。

下面举个例子帮助理解：

  1. 假设系统中有三个具有不同优先级的进程， 分别为 进程1、进程2 和 进程3。其中优先级排序为 进程1 > 进程2 > 进程3。
  2. 进程1 和 进程3 共享资源，此时 进程3 先获取到 资源使用权，进程1 随后也想要访问资源。
  3. 此时 进程3 已经在访问资源了，所以 进程1 被 阻塞。
  4. 在无处理 优先级反转 机制的情况下，如果此时 进程2 由于某些原因发生调度，抢占了 进程3，那么 进程1 等待的时间就延长了。
    这种

这种 低优先级 抢占 高优先级 的情况就叫 优先级反转。解决此类问题通常有以下几种：

上述两者的区别在于：

Linux内核 引入了 实时互斥体(rt_mutex) 来解决 优先级反转 问题，实时互斥体 使用的是 优先级继承，其接口如下：

2.10 完成量

在设备驱动中，经常出现一个线程需要等待另一个线程完成工作后才能继续执行。信号量 可以完成这种工作，但如果出现的是 多个线程 等待 另一个线程 完成呢？这种情况下如果 信号量 不够用则会导致 大部分线程 继续休眠。
为了解决上面的问题，Linux内核 引入 完成量(completion) 。完成量 是一种 轻量级通知机制，可以有效实现 线程通知 的功能。其接口如下：

三、参考链接

《Linux设备驱动开发详解》
ARM屏蔽指令介绍
ARM平台下独占访问指令LDREX和STREX的原理与使用详解
自旋锁spin_lock、spin_lock_irq 和 spin_lock_irqsave 分析
Linux kernel rt_mutex的背景和简介
linux内核的优先级继承协议(pip)和μC/OSII 2.52内核的优先级置顶协议(pcp)

。

上一篇 下一篇

猜你喜欢

热点阅读