linux RT-Preempt spin lock实现
一、spin_lock概述
Spinlock是linux内核中常用的一种互斥锁机制，和mutex不同，当无法持锁进入临界区的时候，当前执行线索不会阻塞，而是不断的自旋等待该锁释放。正因为如此，自旋锁也是可以用在中断上下文的。也正是因为自旋，临界区的代码要求尽量的精简，否则在高竞争场景下会浪费宝贵的CPU资源。
1. spin lock 的发展
(1) TAS和CAS
硬件对同步的支持-TAS和CAS指令 - 元思 - 博客园
锁只有一个原子变量，通过原子指令来修改自旋锁的状态（locked、unlocked）。问题是没有公平可言，无法让等待最长的那个任务优先拿到锁，为了解决这个问题引入了ticket spinlock。
如果thread4当前持锁，同一个cluster中的cpu7上的thread7和另外一个cluster中的thread0都在自旋等待锁的释放。当thread4释放锁的时候，由于cpu7和cpu4的拓扑距离更近，thread7会有更高概率可以抢到自旋锁，从而产生了不公平现象。
(2) ticket spinlock
类似排队叫号，只有任务手中事先领取的号和被叫到的号相等时才能持锁进入临界区。这解决了不公平的问题。但是出现叫号时，所有等待的任务所在的cpu都要读取内存，刷新对应的cache line，而只有获取锁的那个任务所在的cpu对cache line 的刷新才是有意义的，锁争抢的越激烈，无谓的开销也就越大。
但是这种自旋锁在持锁失败的时候会对自旋锁状态数据next成员进行++操作，当CPU数据巨大并且竞争激烈的时候，自旋锁状态数据对应的cacheline会在不同cpu上跳来跳去，从而对性能产生影响，
(3) MCS Lock
在ticket spinlock的基础上做一定的修改，让多个CPU不再等待同一个spinlock变量，而是基于各自的per-CPU的变量进行等待，那么每个CPU平时只需要查询自己对应的这个变量所在的本地cache line，仅在这个变量发生变化的时候，才需要读取内存和刷新这条cache line，这样就可以解决上述问题。要实现类似这样的spinlock的分身，其中的一种方法就是使用MCS lock。试图获取一个spinlock的每个CPU，都有一份自己的MCS lock。
(4) qspinlock
相比起Linux中只占4个字节的ticket spinlock，MCS lock多了一个指针，要多占4（或者8）个字节，消耗的存储空间是原来的2-3倍。qspinlock的首要目标就是改进原生的MCS lock结构体，尽量将原生MCS lock要包含的内容塞进4字节的空间里。
如果只有1个或2个CPU试图获取锁，那么只需要一个4字节的qspinlock就可以了，其所占内存的大小和ticket spinlock一样。当有3个以上的CPU试图获取锁，需要一个qspinlock加上(N-2)个MCS node。
qspinlock中加入”pending”位域，如果是两个CPU试图获取锁，那么第二个CPU只需要简单地设置”pending”为1，而不用另起炉灶创建一个MCS node。
试图加锁的CPU数目超过3个是小概率事件，但一旦发生，使用ticket spinlock机制就会造成多个CPU的cache line无谓刷新的问题，而qspinlock可以利用MCS node队列来解决这个问题。
可见，使用qspinlock机制来实现spinlock，具有很好的可扩展性，也就是无论当前锁的争抢程度如何，性能都可以得到保证。
2. spin lock 的命令规范
（1）spinlock，对于没有打上Linux-RT（实时Linux）的patch的系统，spin_lock只是简单地调用raw_spin_lock，实际上他们是完全一样的；如果打上这个patch之后，spin_lock会使用信号量完成临界区的保护工作，带来的好处是同一个CPU可以有多个临界区同时工作，而原有的体系因为禁止抢占的原因，一旦进入临界区，其他临界区就无法运行，新的体系在允许使用同一个临界区的其他进程进行休眠等待，而不是强占着CPU进行自旋操作。
（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相关，我们在下一节描述。
二、代码结构
最上层是通用自旋锁代码（体系结构无关，平台无关），这一层的代码提供了两种接口：spinlock接口和raw spinlock接口。在没有配置PREEMPT_RT情况下，spinlock接口和raw spinlock接口是一毛一样的。如果配置了PREEMPT_RT，spinlock接口走rt spinlock，底层是基于rtmutex的。也就是说这时候的spinlock不再禁止抢占，不再自旋等待，而是使用了支持PI的睡眠锁来实现，因此有了更好的实时性。而raw spinlock接口即便在配置了PREEMPT_RT下仍然保持传统自旋锁特性。
中间一层是区分SMP和UP的，在SMP和UP上，自旋锁的实现是不一样的。对于UP，自旋没有意义，因此spinlock的上锁和放锁操作退化为preempt disable和enable。SMP平台上，除了抢占操作之外还有正常自旋锁的逻辑，具体如何实现自旋锁逻辑是和底层的CPU architecture相关的，后面我们会详细描述。
最底层的代码是体系结构相关的代码，ARM64上，目前采用是qspinlock。和体系结构无关的Qspinlock代码抽象在qspinlock.c文件中，也就是本文重点要描述的内容。
在2024年9月的欧洲开源峰会上，Linux创始人Linus Torvalds宣布，“PREEMPT_RT”（实时Linux）补丁已被正式合并进Linux主线内核。 从Linux 6.12版本起，所有发行版将内置实时Linux代码，进一步拓宽Linux在任务关键型设备和工业硬件上的应用。
入口：
先看看linux rt spin lock的结构体：spinlock_types.h - include/linux/spinlock_types.h - Linux source code v6.13-rc3 - Bootlin Elixir Cross Referencer
#include <linux/rtmutex.h>typedef struct spinlock {struct rt_mutex_base lock;
} spinlock_t;// include/linux/rtmutex.h
struct rt_mutex_base {raw_spinlock_t wait_lock;struct rb_root_cached waiters;struct task_struct *owner;
};从上述实现可以看出，rt spin lock的底层实现是支持优先级继承的rt mutex
// include/linux/spinlock_rt.hstatic __always_inline void spin_lock(spinlock_t *lock)
{rt_spin_lock(lock);
}// kernel/locking/spinlock_rt.c
void __sched rt_spin_lock(spinlock_t *lock) __acquires(RCU)
{spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);__rt_spin_lock(lock);
}static __always_inline void __rt_spin_lock(spinlock_t *lock)
{rtlock_might_resched();rtlock_lock(&lock->lock);rcu_read_lock();migrate_disable();
}static __always_inline void rtlock_lock(struct rt_mutex_base *rtm)
{lockdep_assert(!current->pi_blocked_on);if (unlikely(!rt_mutex_cmpxchg_acquire(rtm, NULL, current)))rtlock_slowlock(rtm);
}https://elixir.bootlin.com/linux/v6.13-rc3/source/kernel/locking/rtmutex.c#L1875
static __always_inline void __sched rtlock_slowlock(struct rt_mutex_base *lock)
{unsigned long flags;DEFINE_WAKE_Q(wake_q);raw_spin_lock_irqsave(&lock->wait_lock, flags);rtlock_slowlock_locked(lock, &wake_q);preempt_disable();raw_spin_unlock_irqrestore(&lock->wait_lock, flags);wake_up_q(&wake_q);preempt_enable();
}自旋锁spin_lock和raw_spin_lock_raw spin log-CSDN博客
linux 之 mutex、rt_mutex、spinlock_t 的实时性补丁分析_linux rt补丁中断能达到多少-CSDN博客
Linux并发与同步专题 (2)spinlock - ArnoldLu - 博客园
Linux内核同步 - spin_lock - AlanTu - 博客园
Linux内核机制—spin_lock - Hello-World3 - 博客园
自旋锁spin_lock、spin_lock_irq 和 spin_lock_irqsave 分析 - 裸睡的猪 - 博客园
自旋锁探秘-CSDN博客
spinlock.h - include/linux/spinlock.h - Linux source code v5.4.90 - Bootlin Elixir Cross Referencer