Linux rwlock读写锁arch_read_lock与ticket锁对比
Linux rwlock读写锁arch_read_lock与ticket锁对比
Linux内核中的rwlock提供了读写分离的同步语义:读者之间不互斥,写者独占.其实现同样经过多层抽象,rwlock_t -> arch_rwlock_t.底层最关键的对比在于:传统rwlock使用ticket锁来保证公平性,而arch_read_lock/core读者实现则面临写者饥饿问题.
一、rwlock的核心数据结构
```c
typedef struct {
arch_rwlock_t raw_lock;
#ifdef CONFIG_DEBUG_SPINLOCK
unsigned int magic, owner_cpu;
void *owner;
#endif
#ifdef CONFIG_LOCKDEP
struct lockdep_map dep_map;
#endif
} rwlock_t;
```
ARM64平台的arch_rwlock_t基于排队锁(queue rwlock):
```c
typedef struct {
union {
u32 __lock;
struct {
u8 wrpend; /* 写者挂起标志: 0表示无写者等待, 1表示有写者等待 */
u8 waiters; /* 等待者计数 (包括读者和写者) */
u16 readers; /* 活跃读者计数, 0xFFFF表示有写者持有 */
};
};
} arch_rwlock_t;
```
x86平台的传统arch_rwlock_t:
```c
typedef struct {
u32 rwlock; /* 高16位: 读者计数; 低16位: 写者标志 */
} arch_rwlock_t;
```
二、arch_read_lock实现分析
ARM64的读者锁获取:
```c
static inline void arch_read_lock(arch_rwlock_t *lock)
{
unsigned int tmp;
asm volatile(
"1: ldaxr %w0, %1\n"
" tbnz %w0, #24, 2f\n" /* 检查wrpend位,有写者挂起则跳转 */
" add %w0, %w0, #1\n" /* 读者计数+1 */
" stxr %w0, %w0, %1\n"
" cbnz %w0, 1b\n" /* 存储失败则重试 */
" dmb ishld\n" /* 数据内存屏障 */
" ret\n"
"2: /* 写者挂起,等待 */\n"
" ldar %w0, %1\n"
" tbz %w0, #24, 1b\n" /* wrpend清零则重试读获取 */
" wfe\n"
" b 2b\n"
: "=&r" (tmp), "+Q" (lock->__lock)
:
: "memory");
}
```
x86平台的arch_read_lock:
```c
static inline void arch_read_lock(arch_rwlock_t *lock)
{
/* 尝试原子减1 (rwlock初始值0x01000000, 减1后为0x00FFFFFF表示读锁) */
asm volatile(
"1: lock; decl %0\n"
" jns 3f\n"
"2: rep; nop\n"
" cmpl $0, %0\n"
" js 2b\n"
" jmp 1b\n"
"3:"
: "+m" (lock->rwlock)
:
: "memory", "cc");
}
```
三、arch_write_lock实现分析
ARM64的写者锁获取:
```c
static inline void arch_write_lock(arch_rwlock_t *lock)
{
unsigned int tmp;
asm volatile(
"1: mov %w0, #0x00010000\n" /* wrpend=1, waiters递增 */
" ldaxr %w1, %2\n"
" add %w0, %w0, %w1, lsr #16\n" /* waiters域递增 */
" stxr %w0, %w0, %2\n"
" cbnz %w0, 1b\n"
/* 等待所有读者释放 */
"2: dmb ishld\n"
" ldr %w0, %2\n"
" and %w0, %w0, #0xFFFF\n" /* 取readers域 */
" cbnz %w0, 2b\n" /* 仍有读者则等待 */
" ret\n"
: "=&r" (tmp), "=&r" (lock->wrpend), "+Q" (lock->__lock)
:
: "memory");
}
```
四、ticket锁形式的rwlock
某些架构(如旧版x86)使用了ticket锁思想来实现读写锁.每个锁维护两个计数器:当前服务号和服务号上限.
```c
struct ticket_rwlock {
union {
u32 headtail;
struct {
u16 head; /* 当前服务的票号 */
u16 tail; /* 下一个可用的票号 */
};
};
u16 readers; /* 读者计数, 分开存储以避免与写者票号冲突 */
};
```
ticket锁形式的读写锁操作:
```c
static inline void ticket_write_lock(struct ticket_rwlock *lock)
{
u16 my_ticket = xadd(&lock->tail, 2); /* 获取一个偶数的写者票号 */
/* 等待轮到自己的票号 */
while (lock->head != my_ticket)
cpu_relax();
/* 等待所有读者释放 */
while (lock->readers)
cpu_relax();
smp_mb();
}
static inline void ticket_read_lock(struct ticket_rwlock *lock)
{
/* 读者不需要票号队列 */
atomic_inc(&lock->readers);
smp_mb();
}
static inline void ticket_read_unlock(struct ticket_rwlock *lock)
{
smp_mb();
atomic_dec(&lock->readers);
}
```
五、公平性差异分析
传统rwlock(非ticket版)存在严重的写者饥饿问题:如果读者持续到来,写者可能永远无法获取锁.
```c
/* 写者饥饿场景 */
CPU0: read_lock(&rwlock); /* 持有读锁 */
CPU1: read_lock(&rwlock); /* 同时获得读锁 */
CPU2: write_lock(&rwlock); /* 等待所有读者释放 */
CPU3: read_lock(&rwlock); /* CPU0释放后, CPU3进入, 写者依然等待 */
/* 写者CPU2永远等下去... */
```
解决写者饥饿的两个方案:
1. Queue rwlock: 当前ARM64使用的方案,通过wrpend位标记等待的写者,新读者看到wrpend后不再获取锁.
2. ticket rwlock: 写者获取一个票号,所有操作按票号FIFO执行,新读者即使没有写者等待也必须排队.
六、性能对比关键点
- 读者冲突场景: 传统rwlock读者之间通过原子增/减操作,缓存行 bouncing 开销大
- queue rwlock读者路径: 需要检查wrpend位,多一次分支预测
- ticket rwlock读者路径: 完全无需排队,但写者饥饿问题严重
- ARM64 LSE指令集: 支持LDAPR等宽松语义指令,可降低读者路径延迟
七、qrwlock的改进 - 公平读写锁
内核引入了queued_read_lock()来替代旧的arch_read_lock:
```c
static inline void queued_read_lock(struct qrwlock *lock)
{
/* 快速路径: 无写者竞争时直接自增读者计数 */
if (likely(atomic_inc_not_zero(&lock->cnts)))
return;
/* 慢路径: 有写者竞争, 需要排队 */
queued_read_lock_slowpath(lock);
}
static inline void queued_write_lock(struct qrwlock *lock)
{
/* 尝试获取写锁: 从0xFFFFFFFE变为(0xFFFFFFFE | _QW_LOCKED) */
if (likely(atomic_cmpxchg(&lock->cnts, 0, _QW_LOCKED) == 0))
return;
queued_write_lock_slowpath(lock);
}
```
这种设计的核心优势:读者快速路径在无竞争时仅需一条原子操作,慢路径使用MCS锁队列避免缓存行bouncing.
八、使用建议
- 读远多于写的场景(如路由表查找): 使用rwlock,但需注意写者饥饿
- 读写均衡场景: 优先使用带公平性的qrwlock
- 对实时性有要求: 使用RT内核中的rwlock(基于rt_mutex实现),完全避免饥饿
- 读者性能极致要求: 考虑RCU或percpu-rw-semaphore替代rwlock