linux自旋琐源码分析

本文对linux内核中自旋锁的实现进行分析，描述了其背后原理和相关数据结构的含义。本文所有代码来源于linux-5.13.10。

自旋锁被定义为 spinlock_t ,其具体的实现方式与CPU体系结构相关。自旋锁相关的文件列表如下（仅通用部分可供使用者在源文件中使用#include指令包含）。

类别	路径
通用	include/linux/spinlock.h
通用	include/linux/spinlock_types.h
UP	include/linux/spinlock_up.h
UP	include/linux/spinlock_types_up.h
SMP	include/linux/spinlock_api_smp.h
SMP	arch/<arch>/include/asm/spinlock_types.h

为了便于对自旋锁进行分析，本文认为linux中相关宏的定义情况如下，并在展示的示例代码中移除掉了与未定义的宏相关的代码。

是否定义	值	含义
否	CONFIG_DEBUG_SPINLOCK	用于调试自旋锁
否	CONFIG_DEBUG_LOCK_ALLOC	用于调试自旋锁
否	CONFIG_LOCK_STAT	用于分析调试自旋锁
是	CONFIG_INLINE_SPIN_LOCK	用于控制内联
是	CONFIG_INLINE_SPIN_UNLOCK	用于控制内联

1 通用

自旋锁（spinlock）：是指当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环。这意味着自旋锁要求临界区代码尽可能短小且不能睡眠。

1.1 数据结构

//文件 include/linux/spinlock_types.h
typedef struct spinlock {
    union {
        struct raw_spinlock rlock; 
    };
} spinlock_t;
//文件 include/linux/spinlock_types.h
typedef struct raw_spinlock {
    arch_spinlock_t raw_lock;
} raw_spinlock_t;

1.2 操作方法

仅列举和分析主要的操作方法。

spin_lock_init
spin_lock
spin_unlock

spin_lock_init：用于初始化一个自旋锁，其定义如下，读者可自行分析这部分代码。其最终是通过体系结构相关的代码 __ARCH_SPIN_LOCK_UNLOCKED 对锁进行初始化。

// 文件 include/linux/spinlock.h
# define spin_lock_init(_lock)                  \
    do {                                        \
        spinlock_check(_lock);                  \
        *(_lock) = __SPIN_LOCK_UNLOCKED(_lock); \
    } while (0)

// 文件 include/linux/spinlock.h
/* 由自旋锁获取原始自旋锁 */
static __always_inline raw_spinlock_t *spinlock_check(spinlock_t *lock)
{
    return &lock->rlock;
}
// 文件 include/linux/spinlock_types.h
#define __SPIN_LOCK_UNLOCKED(lockname) (spinlock_t) __SPIN_LOCK_INITIALIZER(lockname)
// 文件 include/linux/spinlock_types.h
#define __SPIN_LOCK_INITIALIZER(lockname) { { .rlock = ___SPIN_LOCK_INITIALIZER(lockname) } }
// 文件 include/linux/spinlock_types.h
#define ___SPIN_LOCK_INITIALIZER(lockname) { .raw_lock = __ARCH_SPIN_LOCK_UNLOCKED}

spin_lock：用于锁定。其最终是调用于体系结构相关的代码 _raw_spin_lock 来锁定的。

// 文件 include/linux/spinlock.h
static __always_inline void spin_lock(spinlock_t *lock)
{
    raw_spin_lock(&lock->rlock);
}
// 文件 include/linux/spinlock.h
#define raw_spin_lock(lock) _raw_spin_lock(lock)

spin_unlock：用于解锁。其最终是调用于体系结构相关的代码 _raw_spin_unlock 来解锁的。

// 文件 include/linux/spinlock.h
static __always_inline void spin_unlock(spinlock_t *lock)
{
    raw_spin_unlock(&lock->rlock);
}
// 文件 include/linux/spinlock.h
#define raw_spin_unlock(lock) _raw_spin_unlock(lock)

2 体系结构相关

由前文可知，自旋锁的初始化、锁定、解锁最终调用到体系结构实现的 __ARCH_SPIN_LOCK_UNLOCKED 、 _raw_spin_lock 、 _raw_spin_unlock 。本章将描述其在各体系结构下的实现。

2.1 UP

对于单核处理器，自旋锁得到极大的简化，分析如下代码会发现结构体类型 arch_spinlock_t 内无成员且锁定和解锁只是禁能抢占和使能抢占（资料：非抢占式内核与抢占式内核）。

// 代码中的 __acquire(lock) 和 __release(lock) 仅与调试相关，分析过程可忽略它们
// 代码中的 preempt_disable() 用于禁能抢占，preempt_enable() 用于使能抢占。

// 文件 include/linux/spinlock_types_up.h
typedef struct { } arch_spinlock_t;
#define __ARCH_SPIN_LOCK_UNLOCKED { } 

// 文件 include/linux/spinlock_api_up.h 
#define _raw_spin_lock(lock) __LOCK(lock)
// 文件 include/linux/spinlock_api_up.h 
#define __LOCK(lock)  do { preempt_disable(); ___LOCK(lock); } while (0)
// 文件 include/linux/spinlock_api_up.h 
#define ___LOCK(lock) do { __acquire(lock); (void)(lock); } while (0)

// 文件 include/linux/spinlock_api_up.h
#define _raw_spin_unlock(lock) __UNLOCK(lock)
// 文件 include/linux/spinlock_api_up.h
#define __UNLOCK(lock)  do { preempt_enable(); ___UNLOCK(lock); } while (0)
// 文件 include/linux/spinlock_api_up.h
#define ___UNLOCK(lock) do { __release(lock); (void)(lock); } while (0)

锁定时，禁能抢占是必须的。因为若不禁能抢占则当一个线程处于自旋锁临界区时存在被被另一个高优先级线程抢占CPU的可能性，在这种情况下当高优先级线程也要对同一自旋锁进行锁定时，系统将发生死锁。另外在单核处理器中禁能抢占意味着当前线程独占CPU，自然不可能在同一时刻存在其他线程与当前线程竞争自旋锁。

综上，对于单核处理器而言，自旋锁的锁定与解锁只需要禁能抢占和使能抢占。

2.2 SMP

对于多核处理器，自旋锁的实现较复杂。我们以ARM架构的处理器为例进行介绍。

在ARM处理器中，使用一套名为“FIFO ticket-based”的算法来实现自旋锁，使线程按照申请锁的顺序排队，先申请的线程先获得锁。本文对采用此算法的自旋锁称呼为排队自旋锁。

2.2.1 数据结构

// 文件 arch/arm/include/asm/spinlock_types.h
typedef struct {
    union {
        u32 slock;
        struct __raw_tickets {
            u16 owner;
            u16 next;
        } tickets;
    };
} arch_spinlock_t;

2.2.2 操作方法

初始化时只需要对结构体 arch_spinlock_t 赋值为0即可。

// 文件 arch/arm/include/asm/spinlock_types.h
#define __ARCH_SPIN_LOCK_UNLOCKED   { { 0 } }

锁定时，各级函数调用流程如下，其主要逻辑在方法 arch_spin_lock中。

// 代码中的 preempt_disable() 用于禁能抢占 
// 代码中的 debug_spin_lock_before(lock) 、 debug_spin_lock_after(lock) 仅与调试相关，分析过程可忽略它们
// 代码中的 spin_acquire(lock)仅与调试相关，分析过程可忽略它们
// 代码中的 mmiowb_spin_lock与屏障相关，分析过程可忽略它们

// 文件 include/linux/spinlock_api_smp.h
#define _raw_spin_lock(lock) __raw_spin_lock(lock)
// 文件 include/linux/spinlock_api_smp.h
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);
}
// 文件 include/linux/lockdep.h
#define LOCK_CONTENDED(_lock, try, lock) lock(_lock)
// 文件 kernel/locking/spinlock_debug.c
void do_raw_spin_lock(raw_spinlock_t *lock)
{
    debug_spin_lock_before(lock);     
    arch_spin_lock(&lock->raw_lock);
    mmiowb_spin_lock();
    debug_spin_lock_after(lock);     
}
// 文件 arch/arm/include/asm/spinlock.h
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
    unsigned long tmp;
    u32 newval;
    arch_spinlock_t lockval;

    /*
     * 令当前线程获取号牌（即lockval.tickets.next）并更新锁内下一次分配的号牌（lock->tickets.next）  
     * 
     */
    prefetchw(&lock->slock);
    __asm__ __volatile__(
"1:    ldrex   %0, [%3]\n"
"  add %1, %0, %4\n"
"  strex   %2, %1, [%3]\n"
"  teq %2, #0\n"
"  bne 1b"
    : "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
    : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
    : "cc");

    /*
     * 使用号牌（即lockval.tickets.next）不断的与锁内的owner值比较（即lock->tickets.owner）
     * 当二者相等时，意味着当前线程获得此锁。
     *
     * 在执行本函数的线程的视角下，变量lock->tickets.owner从未修改，编译器可能自作聪明的认为
     * lock->tickets.owner是一个定值而执行优化手段。此处的READ_ONCE用于告诫编译器勿做相关的
     * 优化操作，每次均由内存中读取此变量。
     */
    while (lockval.tickets.next != lockval.tickets.owner) {
        wfe();
        lockval.tickets.owner = READ_ONCE(lock->tickets.owner);
    }

    smp_mb();
}

解锁时，各级函数调用流程如下，其主要逻辑在方法 arch_spin_unlock中。

// 代码中的 preempt_enable() 用于禁能抢占 
// 代码中的 debug_spin_unlock(lock) 仅与调试相关，分析过程可忽略它们
// 代码中的 spin_release(lock)仅与调试相关，分析过程可忽略它们
// 代码中的 mmiowb_spin_unlock与屏障相关，分析过程可忽略它们

// 文件 include/linux/spinlock_api_smp.h
#define _raw_spin_unlock(lock) __raw_spin_unlock(lock)
// 文件 include/linux/spinlock_api_smp.h
static inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
    spin_release(&lock->dep_map, _RET_IP_);
    do_raw_spin_unlock(lock);
    preempt_enable();
} 
// 文件 kernel/locking/spinlock_debug.c
void do_raw_spin_unlock(raw_spinlock_t *lock)
{
    mmiowb_spin_unlock();
    debug_spin_unlock(lock);
    arch_spin_unlock(&lock->raw_lock);
}
// 文件 arch/arm/include/asm/spinlock.h
static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
    smp_mb();
    /*
     * 释放锁 
     */
    lock->tickets.owner++;
    dsb_sev();
}

2.2.3 细节分析

本小节分析 arch_spin_lock 和 arch_spin_unlock 为何可正常工作。

2.2.3.1 关于线程安全的分析

通过阅读函数 arch_spin_lock 和 arch_spin_unlock 的实现，会发现同一时刻不同线程对 arch_spinlock_t 类型变量的访问可能正在执行如下三个阶段之一：

阶段A：arch_spin_lock 中获取号牌阶段
阶段B：arch_spin_lock 中等待获得锁阶段
阶段C：arch_spin_unlock 中释放锁阶段

当一个线程正在执行阶段A时，可能有任意多个线程正在执行阶段A、可能有任意多个线程正在执行阶段B、可能有1个（或0）线程正在执行阶段C（最多有一个线程在执行阶段C，表示其正在解锁）。

当前线程和其他正在执行阶段A的线程安全是由原子变量来保证的：原子变量保证了执行的 LDREX 和 STREX 之间是原子操作（原子变量原理描述：为了保证“读-修改-写回”流程的原子性，线程会在写回时检查在读之后和写回之前是否有其他线程对此变量执行了写操作，如无，则将值写回入变量，否则重新执行“读-修改-写回”流程）。因此多个执行阶段A的线程对自旋锁的操作是串行化的。
当前线程和其他正在执行阶段B的线程不存在线程安全问题。阶段A未修改阶段B所关注的变量。
当前线程和其他正在执行阶段C的线程安全是由原子变量来保证的。若阶段C在阶段A的LDREX 和 STREX 之间发起STR 指令执行写操作，则阶段A会重新执行“读-修改-写回”流程。因此多个执行阶段A的线程和一个执行阶段C的线程对自旋锁的操作是串行化的。

当一个线程正在执行阶段B时，可能有任意多个线程正在执行阶段A、可能有任意多个线程正在执行阶段B、可能有1个（或0）线程正在执行阶段C（最多有一个线程在执行阶段C，表示其正在解锁）。