Kernel lock 종류와 중첩 규칙

세 lock category와 owner semantics

Kernel locking primitive는 sleeping lock, CPU local lock, spinning lock의 세 category로 나눌 수 있다. 이 문서는 각 lock을 개념적으로 설명하고 PREEMPT_RT를 포함한 nesting rule을 제시한다.

Sleeping lock 구현이 다른 context에서 try_lock()을 허용하더라도 try_lock뿐 아니라 unlock 안전성과 debugging version까지 검토해야 한다. 다른 선택지가 없다면 모를까 sleeping lock을 비-task context에서 획득하지 않는 것이 원칙이다.

CPU에서 preemption 또는 interrupt를 disable하는 것은 순수한 CPU-local concurrency control이다. 다른 CPU와의 동시 접근을 직렬화하지 못한다.

Semaphore를 제외한 앞의 lock type은 strict owner semantics를 갖는다. Lock을 획득한 context 또는 task가 직접 release해야 한다. rw_semaphore에는 reader를 위해 non-owner release를 허용하는 특별 interface가 있다.

rt_mutex, semaphore와 priority inheritance

RT-mutex는 priority inheritance(PI)를 지원하는 mutex다. Non-PREEMPT_RT kernel에서는 preemption-disabled와 interrupt-disabled section 때문에 PI에 한계가 있다.

PREEMPT_RT에서도 PI가 preemption-disabled 또는 interrupt-disabled code region을 preempt할 수는 없다. 대신 PREEMPT_RT는 interrupt handler와 soft interrupt를 포함한 이런 region 대부분을 preemptible task context에서 실행하도록 변환한다. 이 변환 덕분에 spinlock_t와 rwlock_t를 RT-mutex로 구현할 수 있다.

Semaphore는 counting semaphore 구현이다. Serialization과 waiting 두 목적으로 자주 쓰였지만 새 use case는 mutex와 completion처럼 serialization mechanism과 wait mechanism을 분리해야 한다.

PREEMPT_RT는 semaphore 구현을 바꾸지 않는다. Counting semaphore에는 owner 개념이 없어 priority inheritance를 제공할 수 없기 때문이다. 알 수 없는 owner의 priority는 boost할 수 없다. 따라서 semaphore에서 block하면 priority inversion이 생길 수 있다.

rw_semaphore의 fairness와 PREEMPT_RT

rw_semaphore는 여러 reader 또는 한 writer를 허용하는 lock mechanism이다. Non-PREEMPT_RT 구현은 fair하므로 writer starvation을 막는다. 기본적으로 strict owner semantics를 따르지만 reader용 non-owner release special-purpose interface가 있으며 kernel configuration과 무관하게 동작한다.

PREEMPT_RT는 rw_semaphore를 별도의 rt_mutex 기반 구현으로 mapping하여 fairness를 바꾼다. rw_semaphore writer는 여러 reader에게 자기 priority를 넘겨줄 수 없다. 따라서 preempt된 low-priority reader가 lock을 계속 보유하면 high-priority writer도 starvation될 수 있다.

반대 방향에서는 reader들이 writer에게 priority를 전달할 수 있다. Preempt된 low-priority writer는 lock을 release할 때까지 priority가 boost되므로 그 writer 때문에 reader가 starvation되는 일을 막는다.

local_lock의 named CPU-local scope

local_lock은 preemption 또는 interrupt disable로 보호하는 critical section에 이름 있는 scope를 제공한다. Non-PREEMPT_RT에서 operation은 다음 primitive로 mapping된다.

이름 있는 scope에는 두 장점이 있다. Lock name은 static analysis에 사용할 수 있고 보호 범위를 분명히 문서화한다. 일반 preemption·IRQ primitive는 이름과 scope가 없어 어떤 data를 보호하는지 알기 어렵다.

Lockdep를 enable하면 local_lock에 lockmap이 생겨 보호가 올바른지 검증할 수 있다. 예를 들어 preempt_disable()로 보호하는 function이 interrupt 또는 soft-interrupt context에서 불리는 오류를 찾는다. lockdep_assert_held(&llock)도 다른 locking primitive와 같은 방식으로 사용할 수 있다.

PREEMPT_RT는 local_lock을 per-CPU spinlock_t로 mapping하므로 spinlock_t의 모든 의미 변화가 local_lock에도 적용된다. Local_lock은 non-RT에서 per-CPU data structure를 보호하기 위해 preemption 또는 interrupt disable이 적절한 경우에 사용한다. RT에서는 spinlock_t semantics 때문에 preemption이나 interrupt 자체를 막는 용도로 사용할 수 없다.

CPU-local softirq scope를 명시하는 nested_bh

Softirq context에서만 접근하는 per-CPU variable이라도 그 context가 non-preemptible이라 자동 보호된다고 가정해서는 안 된다. PREEMPT_RT에서는 softirq context가 preemptible이며, bottom-half-disabled section 전체를 암묵적으로 동기화하면 per-CPU big kernel lock과 같은 결과가 된다.

local_lock_t와 local_lock_nested_bh()·local_unlock_nested_bh()를 사용하면 실제 locking scope를 식별할 수 있다. Lockdep가 켜져 있으면 data structure access가 softirq context 안에서 이루어지는지 검증한다.

local_unlock_nested_bh()는 local_lock()과 달리 preemption을 disable하지 않으며 lockdep가 없을 때 overhead를 추가하지 않는다. PREEMPT_RT에서는 local_lock_t가 real lock으로 동작하고 local_unlock_nested_bh()가 data access를 직렬화하므로 local_bh_disable()에 의한 serialization을 제거할 수 있다.

raw_spinlock_t와 spinlock_t의 기본 차이

raw_spinlock_t는 PREEMPT_RT를 포함한 모든 kernel에서 strict spinning lock이다. Real critical core code, low-level interrupt handling, hardware state에 안전하게 접근하기 위해 preemption 또는 interrupt disable이 반드시 필요한 곳에서만 사용한다. Critical section이 극히 작아 RT-mutex overhead를 피하려는 경우에도 제한적으로 쓸 수 있다.

spinlock_t 의미는 PREEMPT_RT 여부에 따라 달라진다. Non-PREEMPT_RT에서는 raw_spinlock_t에 mapping되어 완전히 같은 semantics를 갖는다.

PREEMPT_RT에서는 spinlock_t가 rt_mutex 기반 별도 구현으로 mapping된다. Preemption을 disable하지 않으며 spin_lock/spin_unlock의 _irq, _irqsave/_irqrestore suffix도 CPU interrupt-disabled state를 바꾸지 않는다.

_bh suffix는 여전히 softirq handler를 disable한다. Non-RT는 preemption을 disable해 이 효과를 얻지만 PREEMPT_RT는 preemption을 유지하면서 per-CPU lock으로 serialization한다. 이 lock은 softirq handler를 disable하고 task preemption에 의한 reentrancy도 막는다.

그 밖의 spinlock_t semantics는 유지된다. Lock을 가진 task는 migrate하지 않는다. Non-RT는 preemption disable로 migration을 막고 PREEMPT_RT는 migration만 disable하여 task가 preempt되더라도 per-CPU variable pointer가 유효하도록 보장한다.

PREEMPT_RT spinlock 대기와 task state 보존

Spinlock 획득 전후의 task state도 모든 kernel configuration에서 보존해야 한다. Non-PREEMPT_RT는 task state를 건드리지 않는다. 하지만 PREEMPT_RT에서는 rt_mutex 기반 spinlock 획득 중 task가 block할 수 있어 state를 바꿔야 한다. Block 전에 current state를 saved_state에 저장하고 lock wakeup이 이를 복원한다.

일반 wakeup은 보통 task state를 무조건 RUNNING으로 바꾼다. 그러나 spinlock을 기다리며 block된 task에 그렇게 하면 lock이 가능하기 전에 실행될 수 있어 안 된다. 따라서 non-lock wakeup은 실제 state가 아니라 saved_state를 RUNNING으로 바꾼다. Lock 획득이 끝나면 lock wakeup이 saved_state를 current state에 복원한다.

이 two-stage state update 덕분에 실제 wakeup event가 lock wait에 가려져 유실되지 않는다.

rwlock_t와 PREEMPT_RT fairness

rwlock_t는 여러 reader 또는 한 writer를 허용한다. Non-PREEMPT_RT에서는 spinning lock으로 구현되어 spinlock_t suffix rule이 적용되고 fair implementation이 writer starvation을 막는다.

PREEMPT_RT는 rwlock_t를 별도 rt_mutex 기반 구현으로 mapping한다. Spinlock_t의 모든 변화가 rwlock_t에도 적용된다.

Writer는 여러 reader에게 priority를 전달할 수 없으므로 preempt된 low-priority reader가 lock을 계속 보유해 high-priority writer를 starvation시킬 수 있다. 반대로 reader는 writer에게 priority를 전달할 수 있어 preempt된 low-priority writer는 release할 때까지 boost되고 reader starvation을 막는다.

PREEMPT_RT에서 local_lock 변환 시 주의점

Non-PREEMPT_RT에서 다음 sequence는 local_lock_irq()가 interrupt를 disable하므로 기대대로 동작하며 raw_spin_lock_irq(&lock)와 같다.

local_lock_irq(&local_lock);
raw_spin_lock(&lock);

/* non-RT에서 동등 */
raw_spin_lock_irq(&lock);

PREEMPT_RT에서는 local_lock_irq()가 interrupt나 preemption을 disable하지 않는 per-CPU spinlock_t로 mapping되어 이 sequence가 깨진다. 다음처럼 일반 spin_lock을 nesting하면 RT와 non-RT 모두 올바르다.

local_lock_irq(&local_lock);
spin_lock(&lock);

또 다른 함정은 local_lock마다 고유한 protection scope가 있다는 점이다. 두 caller가 같은 func3()의 protected data에 접근하면서 서로 다른 local_lock_1과 local_lock_2를 사용하면 RT에서 두 caller를 직렬화하지 못한다. local_lock_irqsave()가 interrupt를 실제로 disable하지 않으므로 lockdep_assert_irqs_disabled()도 fail한다.

/* 잘못된 변환: 서로 다른 scope */
func1()
{
  local_lock_irqsave(&local_lock_1, flags);
  func3();
  local_unlock_irqrestore(&local_lock_1, flags);
}

func2()
{
  local_lock_irqsave(&local_lock_2, flags);
  func3();
  local_unlock_irqrestore(&local_lock_2, flags);
}

func3()
{
  lockdep_assert_irqs_disabled();
  access_protected_data();
}

올바른 변환은 두 caller가 같은 local_lock을 사용하고 callee가 lockdep_assert_held()로 그 lock을 확인하는 것이다.

func1()
{
  local_lock_irqsave(&local_lock, flags);
  func3();
  local_unlock_irqrestore(&local_lock, flags);
}

func2()
{
  local_lock_irqsave(&local_lock, flags);
  func3();
  local_unlock_irqrestore(&local_lock, flags);
}

func3()
{
  lockdep_assert_held(&local_lock);
  access_protected_data();
}

IRQ disable, per-CPU pointer와 RT spinlock nesting

Non-PREEMPT_RT에서 local_irq_disable() 뒤 spin_lock()을 호출하는 sequence는 spin_lock_irq()와 같다. rwlock_t와 _irqsave suffix도 마찬가지다.

local_irq_disable();
spin_lock(&lock);

/* non-RT에서 동등 */
spin_lock_irq(&lock);

PREEMPT_RT에서는 RT-mutex가 fully preemptible context를 요구하므로 첫 sequence가 깨진다. 대신 spin_lock_irq() 또는 spin_lock_irqsave()와 대응 unlock을 사용한다. IRQ disable과 locking을 분리해야 한다면 local_lock으로 task를 CPU에 pin한 뒤 per-CPU interrupt-disabled lock 등을 획득할 수 있지만 반드시 필요한 경우에만 사용한다.

Thread context에서 per-CPU variable을 보호하는 다음 code는 non-RT에서는 맞지만 RT에서는 get_cpu_ptr()가 암묵적으로 preemption을 disable하기 때문에 p->lock을 획득할 수 없다.

struct foo *p = get_cpu_ptr(&var1);

spin_lock(&p->lock);
p->count += this_cpu_read(var2);

두 kernel에서 모두 동작하려면 migration만 disable하고 task는 preemptible하게 유지한다. migrate_disable()은 task를 current CPU에 pin하여 var1과 var2의 per-CPU access가 같은 CPU에 남게 한다.

struct foo *p;

migrate_disable();
p = this_cpu_ptr(&var1);
spin_lock(&p->lock);
p->count += this_cpu_read(var2);

그러나 migrate_disable()은 preempting task의 reentrancy를 막지 못한다. Function이 per-CPU data를 읽은 뒤 preempt될 수 있고 다른 task가 같은 data에 다시 들어올 수 있는 경우에는 local_lock을 사용해야 한다.

func()
{
  struct foo *p;

  local_lock(&foo_lock);
  p = this_cpu_ptr(&var1);
  p->val = func2();
}

Non-RT에서는 local_lock이 preemption을 disable해 reentrancy를 막고 PREEMPT_RT에서는 underlying per-CPU spinlock을 획득해 같은 보호를 제공한다.

RT에서 raw_spinlock과 bit spinlock의 atomic 제약

raw_spinlock_t를 획득하면 preemption과 경우에 따라 interrupt도 disable된다. 따라서 critical section은 일반 spinlock_t 또는 rwlock_t를 추가로 획득해서는 안 되고 memory allocation 같은 operation도 피해야 한다.

다음 code는 non-PREEMPT_RT에서는 동작하지만 fully preemptible memory allocator를 truly atomic context에서 호출할 수 없는 PREEMPT_RT에서는 실패한다.

raw_spin_lock(&lock);
p = kmalloc(sizeof(*p), GFP_ATOMIC);

PREEMPT_RT에서 일반 non-raw spinlock은 preemption을 disable하지 않으므로 해당 lock을 가진 상태에서 allocator를 호출하는 것은 허용된다.

spin_lock(&lock);
p = kmalloc(sizeof(*p), GFP_ATOMIC);

Bit 하나에는 RT-mutex를 담을 수 없어 PREEMPT_RT가 bit spinlock을 대체할 수 없다. 따라서 bit spinlock semantics는 그대로이며 raw_spinlock_t의 주의점이 모두 적용된다.

일부 bit spinlock은 사용 위치의 #ifdef code로 PREEMPT_RT에서 일반 spinlock_t로 바꾼다. 반면 spinlock_t 자체의 대체는 사용 위치를 고칠 필요가 없다. Header와 core locking implementation의 conditional이 compiler가 투명하게 substitution하도록 만든다.

Lock category nesting 순서

• 같은 category의 lock끼리는 일반 lock ordering rule을 지켜 deadlock을 막는 한 자유롭게 nesting할 수 있다.
• Sleeping lock은 CPU-local lock 또는 spinning lock 안에 nesting할 수 없다.
• CPU-local lock과 spinning lock은 sleeping lock 안에 nesting할 수 있다.
• Spinning lock은 모든 lock type 안에 nesting할 수 있다.

이 제약은 PREEMPT_RT와 non-RT 모두에 적용된다. PREEMPT_RT에서는 spinlock_t와 rwlock_t category가 spinning에서 sleeping으로 바뀌고 local_lock이 per-CPU spinlock_t가 되므로 raw spinlock을 가진 상태에서 이들을 획득할 수 없다.

PREEMPT_RT 여부와 관계없이 이 제약을 위반하면 lockdep가 경고한다.