Lockdep runtime correctness validator

Lockdep validator와 lock class

Runtime locking correctness validator는 Ingo Molnar가 시작했고 Arjan van de Ven이 내용을 추가했다.

Validator가 다루는 기본 object는 lock의 class다. Lock class는 실제 instance가 여러 개, 많게는 수만 개 존재하더라도 locking rule 관점에서 논리적으로 같은 lock의 집합이다. 예를 들어 inode struct 안의 lock은 하나의 class이고 각 inode는 그 class에 속한 자기 lock instance를 가진다.

Validator는 lock class의 usage state와 서로 다른 lock class 사이 dependency를 추적한다. Lock usage는 IRQ context와 관련해 lock이 어떻게 쓰였는지를 나타낸다. Lock dependency는 lock order로 이해할 수 있다. L1 -> L2는 task가 L1을 보유한 채 L2 획득을 시도했음을 뜻한다.

Lockdep 관점에서 L1과 L2가 원래부터 관련된 lock일 필요는 없다. Dependency는 그 순서가 한 번이라도 실제로 나타났다는 뜻일 뿐이다. Validator는 usage와 dependency가 올바름을 계속 증명하며, 잘못됐다고 판단하면 splat을 출력한다.

Lock class의 behavior는 모든 instance의 사용 이력을 합쳐 구성한다. Boot 뒤 어떤 class의 첫 instance가 사용되면 class를 등록하고, 이후 instance를 그 class에 mapping한다. 따라서 모든 instance의 usage와 dependency가 class의 이력에 기여한다.

Lock instance가 사라져도 lock class는 곧바로 사라지지 않는다. 다만 static 또는 dynamic lock class의 memory space가 회수되면 class를 제거할 수 있다. Module unload나 workqueue destroy가 그 예다.

Usage state와 오류 문자열 읽기

Validator는 lock class의 사용 이력을 (4 usages × n STATEs + 1) category로 나눈다. 각 STATE에 대해 다음 네 종류를 추적한다.

• STATE context에서 한 번이라도 보유됨
• STATE context에서 readlock으로 한 번이라도 보유됨
• STATE가 enabled인 상태에서 한 번이라도 보유됨
• STATE가 enabled인 상태에서 readlock으로 한 번이라도 보유됨

n개의 STATE는 kernel/locking/lockdep_states.h에 정의되며 현재 hardirq와 softirq를 포함한다. 마지막 한 category는 lock이 한 번이라도 사용됐는지를 나타낸다.

Locking rule 위반 때 usage bit는 오류 message의 중괄호 안에 2 × n STATEs개의 문자로 표시된다. 다음 인위적인 예에서는 같은 lock을 이미 보유한 task가 다시 획득하려 한다.

modprobe/2287 is trying to acquire lock:
 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24

but task is already holding lock:
 (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24

각 STATE마다 왼쪽부터 lock usage와 readlock usage를 차례로 나타낸다. 각 위치의 문자는 report 시점까지 관측된 정확한 조합을 요약한다.

주어진 STATE에서 IRQ context 획득 이력과 STATE enabled 상태의 획득 이력을 조합하면 네 경우가 나온다.

'-'가 표시되면 IRQ enabled 이력은 없었다고 추론할 수 있다. 있었다면 '?'가 표시됐을 것이기 때문이다. '+'에도 비슷한 추론을 적용할 수 있다. 아직 사용되지 않은 lock, 예를 들어 한 번도 사용되지 않은 mutex는 오류 원인의 일부가 될 수 없다.

Single-lock state rule

Lock이 irq-safe라는 말은 IRQ context에서 한 번이라도 사용됐다는 뜻이다. irq-unsafe는 IRQ enabled 상태에서 한 번이라도 획득됐다는 뜻이다. Softirq-unsafe lock class는 자동으로 hardirq-unsafe이기도 하다.

각 lock class의 usage에서 hardirq-safe와 hardirq-unsafe는 상호 배타적이고, softirq-safe와 softirq-unsafe도 상호 배타적이다. 각 pair에서는 하나만 설정될 수 있다.

<hardirq-safe> or <hardirq-unsafe>
<softirq-safe> or <softirq-unsafe>

IRQ context에서 사용할 수 있는 irq-safe lock은 IRQ enabled 상태에서 획득된 적이 있어서는 안 된다. 그렇게 사용하면 lock을 획득한 뒤 release하기 전에 interrupt가 들어왔을 때 같은 lock을 두 번째로 획득하려 하므로 deadlock이 생길 수 있다. 이를 lock recursion deadlock이라 한다.

Validator는 이 single-lock state rule을 어긴 lock usage를 발견해 report한다.

Multi-lock dependency rule

같은 lock class를 두 번 획득하면 lock recursion deadlock이 생길 수 있으므로 허용되지 않는다.

두 lock을 서로 반대 순서로 획득하는 것도 허용되지 않는다. L1을 보유한 채 L2를 기다리는 context와 L2를 보유한 채 L1을 기다리는 context가 원을 이루어 영원히 서로를 기다릴 수 있다. 이를 lock inversion deadlock이라 한다.

<L1> -> <L2>
<L2> -> <L1>

Validator는 획득 operation 사이에 다른 locking sequence가 얼마든지 들어 있어도 임의 복잡도의 dependency circle을 찾아낸다.

Usage에 기반한 다음 lock dependency도 어떤 두 lock class 사이에서든 허용되지 않는다.

<hardirq-safe> -> <hardirq-unsafe>
<softirq-safe> -> <softirq-unsafe>

Hardirq-safe lock은 hardirq context에서 획득될 수 있고, 그 context가 hardirq-unsafe lock을 보유한 실행을 interrupt할 수 있다. 그러면 lock inversion deadlock이 생길 수 있다. Softirq-safe lock과 softirq-unsafe lock도 같은 원리다.

Kernel에서 어떤 locking sequence가 관측되든 새 lock을 획득할 때 validator는 새 lock과 현재 보유한 모든 lock 사이에 rule 위반이 있는지 검사한다.

Lock class state가 바뀌면 과거 dependency도 다시 검사한다. 새 hardirq-safe lock이 발견되면 과거에 hardirq-unsafe lock을 획득했는지, 새 softirq-safe lock이면 softirq-unsafe lock을 획득했는지 확인한다. 새 hardirq-unsafe lock이 발견되면 과거에 hardirq-safe lock이 이를 획득했는지, 새 softirq-unsafe lock이면 softirq-safe lock이 이를 획득했는지 확인한다.

실제로 그 interrupt timing이 아직 발생하지 않았어도 검사한다. Interrupt context는 어떤 irq-unsafe 또는 hardirq-unsafe lock 보유 구간도 interrupt할 수 있고, 그 가능성만으로 inversion deadlock이 성립할 수 있기 때문이다.

예외: 계층적 data와 nested locking

Linux kernel에는 같은 lock class의 instance를 둘 이상 획득하는 경우가 조금 있다. 같은 type의 object 사이에 hierarchy가 있을 때 주로 나타난다. Hierarchy 속성이 두 object 사이의 자연스러운 순서를 정의하며 kernel은 각 object의 lock을 항상 그 고정 순서로 잡는다.

Whole-disk block device object와 partition block device object가 nested locking의 예다. Partition은 whole device의 일부이므로 whole disk lock을 partition lock보다 항상 상위에서 획득하면 ordering은 올바르다. 다만 이 ordering rule은 static하지 않으므로 validator가 자연스러운 계층을 자동으로 알아내지는 못한다.

이 올바른 usage model을 validator에 알려 주기 위해 여러 locking primitive에 nesting level을 지정하는 _nested() version이 추가됐다. Block device mutex 예시는 다음과 같다.

enum bdev_bd_mutex_lock_class
{
     BD_MUTEX_NORMAL,
     BD_MUTEX_WHOLE,
     BD_MUTEX_PARTITION
};

mutex_lock_nested(&bdev->bd_contains->bd_mutex,
                  BD_MUTEX_PARTITION);

이 호출은 대상 bdev object가 partition임을 알고 lock을 획득한다. Validator는 nested 방식으로 획득한 lock을 validation 목적상 별도 subclass로 취급한다.

Locking requirement annotation

특정 지점에서 어떤 lock을 보유해야 하는지 annotate하고 검사하는 두 construct는 lockdep_assert_held*(&lock)과 lockdep_*pin_lock(&lock)이다.

lockdep_assert_held* macro family는 특정 시점에 지정한 lock을 보유했는지 assert하고, 그렇지 않으면 WARN()을 만든다. Kernel 전반에서 널리 쓰인다. kernel/sched/core.c의 update_rq_clock()은 rq clock을 안전하게 갱신하려면 rq->lock을 보유해야 함을 다음처럼 검사한다.

void update_rq_clock(struct rq *rq)
{
    s64 delta;

    lockdep_assert_held(&rq->lock);
    [...]
}

lockdep_*pin_lock() family는 현재 rq->lock에만 쓰일 정도로 채택 범위가 좁지만 관심 lock이 실수로 unlock되면 WARN()을 만든다. Upper layer는 lock이 계속 잡혀 있다고 가정하지만 callback 아래쪽 layer가 lock을 잠깐 놓았다 다시 잡아도 된다고 생각해 race를 만드는 code를 debug할 때 특히 유용하다.

lockdep_pin_lock()은 struct pin_cookie를 반환하고 lockdep_unpin_lock()은 이 cookie로 중간에 누군가 lock 상태를 건드리지 않았는지 검사한다. kernel/sched/sched.h의 wrapper는 다음과 같다.

static inline void rq_pin_lock(struct rq *rq,
                               struct rq_flags *rf)
{
    rf->cookie = lockdep_pin_lock(&rq->lock);
    [...]
}

static inline void rq_unpin_lock(struct rq *rq,
                                 struct rq_flags *rf)
{
    [...]
    lockdep_unpin_lock(&rq->lock, rf->cookie);
}

Locking requirement를 comment로 남기는 것도 정보가 되지만 annotation의 runtime check는 locking problem debug에 매우 값지고 code를 읽을 때도 같은 수준의 detail을 전달한다. 어느 쪽을 쓸지 망설여진다면 annotation을 우선한다.

Locking correctness의 수학적 closure와 성능

Validator는 kernel lifetime 동안 한 번이라도 발생한 단순하고 독립적인 single-task locking sequence 각각에 대해 수학적 closure를 만든다. 이 component sequence들을 어떤 조합과 timing으로 실행해도 어떤 종류의 lock-related deadlock도 만들 수 없음을 100% 확실하게 증명한다.

복잡한 multi-CPU, multi-task locking scenario가 실제로 발생할 필요는 없다. 단순 component locking chain이 어느 task나 context에서든 한 번씩만 나타나면 validator가 correctness를 증명할 수 있다. 원래라면 CPU 세 개 이상과 task, IRQ context, timing의 매우 희귀한 조합이 필요한 deadlock도 부하가 적은 single-CPU system에서 검출할 수 있다.

따라서 locking QA의 복잡성이 크게 낮아진다. 현실적으로 불가능한 모든 CPU interaction과 모든 hardirq·softirq nesting 조합을 일으키는 대신, kernel의 단순 single-task dependency를 가능한 한 많이 한 번씩 실행하면 된다.

O(N²) 검사를 줄이는 chain cache

위 rule을 lock 획득과 IRQ-enable event마다 모두 검사하면 runtime overhead가 너무 커져 system을 사실상 쓸 수 없을 정도로 느리게 만든다. 검사 complexity는 O(N²)이므로 lock class가 수백 개만 있어도 event마다 수만 번 검사해야 한다.

Lockdep은 주어진 locking scenario, 즉 lock을 차례로 획득한 unique sequence를 한 번만 검사해 해결한다. Held lock의 단순 stack을 유지하고 lock chain마다 unique한 가벼운 64-bit hash를 계산한다.

Chain을 처음 validate하면 hash를 lock-free 방식으로 조회할 수 있는 hash table에 넣는다. 나중에 같은 chain이 다시 발생하면 hash table을 보고 다시 validate하지 않는다.

MAX_LOCKDEP_KEYS 고갈 진단

Validator가 추적할 수 있는 lock class는 최대 MAX_LOCKDEP_KEYS개다. 이 수를 넘으면 다음 warning이 발생한다.

DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS)

현재 기본 MAX_LOCKDEP_KEYS는 8191이고 일반 desktop system의 lock class는 1,000개보다 적다. 따라서 이 warning은 보통 lock class leak이나 lock initialization 누락을 뜻한다.

반복되는 module load와 unload

Validator를 실행한 채 module을 반복 load·unload하면 lock class leak이 생긴다. Load할 때마다 module lock의 새 class set을 만들지만 unload는 과거 class를 제거하지 않는다. Lock class 재사용이 어려운 이유는 아래 설명과 같다. 반복하면 class 수가 결국 maximum에 도달한다.

대규모 lock array의 초기화 누락

명시적으로 초기화하지 않은 lock을 많이 포함한 array 같은 structure도 원인이 된다. Bucket마다 spinlock_t가 있는 8192-bucket hash table에서 각 spinlock을 runtime에 명시적으로 초기화하지 않으면 lock class 8192개를 소비한다.

Compile-time initializer인 __SPIN_LOCK_UNLOCKED()만 쓰지 말고 loop에서 각 lock에 spin_lock_init()을 호출하면 8192개 lock이 모두 하나의 lock class에 들어간다. 교훈은 lock을 항상 명시적으로 초기화하라는 것이다.

Lock class를 재사용하도록 validator를 고치자는 주장이 나올 수 있다. 그러나 제거할 class가 lock-dependency graph에 연결돼 있을 가능성을 고려해 필요한 변경을 검토하면 말보다 구현이 훨씬 어렵다는 점을 알 수 있다.

Leak 찾기

현재 사용 중인 lock class 수와 maximum은 다음 명령으로 확인한다.

grep "lock-classes" /proc/lockdep_stats

lock-classes:                          748 [max: 8191]

할당 수가 시간에 따라 계속 늘어나면 leak일 가능성이 높다. Leaking lock class는 다음 명령으로 찾을 수 있다.

grep "BD" /proc/lockdep

명령 결과를 저장하고 나중 결과와 비교해 새로 늘어난 class를 찾는다. 같은 output은 runtime lock initialization을 빠뜨린 위치를 찾는 데도 도움이 된다.

Recursive read lock의 의미와 blocking matrix

이후 문서는 특정 종류의 dependency cycle과 deadlock 가능성이 동치임을 증명한다. Locker는 writer, non-recursive reader, recursive reader 세 종류다.

따라서 N은 r 또는 W이고 S는 r 또는 R이다. Recursive reader는 같은 lock instance의 다른 reader critical section 안에서도 획득할 수 있어 한 lock의 read-side critical section을 중첩할 수 있다. Non-recursive reader는 같은 상황에서 획득을 시도하면 self-deadlock을 일으킨다.

차이는 recursive reader가 현재 write lock holder에게만 block되지만 non-recursive reader는 write lock waiter에게도 block될 수 있다는 점에서 생긴다.

같은 lock instance의 reader와 writer 사이에는 네 가지 blocking condition이 있다. Writer는 다른 writer를 block하고, reader는 writer를 block한다. Writer는 recursive와 non-recursive reader를 모두 block한다. Reader는 다른 recursive reader를 block하지 않지만 함께 존재할 수 있는 writer waiter 때문에 non-recursive reader는 block할 수 있다.

표에서 Y는 row의 locker가 column의 locker를 block함을 뜻하고 N은 block하지 않음을 뜻한다.

Recursive read lock은 current write lock holder에게는 block되지만 write lock waiter만으로는 block되지 않는다. Task A가 read_lock(X)을 가진 상태에서 Task B가 write_lock(X)을 기다려도 Task A의 두 번째 recursive read_lock(X)은 기다릴 필요가 없다. 같은 operation이 non-recursive라면 B가 실제 lock을 얻지 못했더라도 waiter가 두 번째 read를 block해 deadlock이 된다.

하나의 lock instance도 어떤 acquisition function을 사용했는지, 더 정확히는 lock_acquire()의 read parameter 값에 따라 exclusive write lock, non-recursive read lock, recursive read lock 세 형태로 획득될 수 있다.

이후 설명에서는 write lock과 non-recursive read lock을 합쳐 non-recursive lock, recursive read lock을 recursive lock이라 부른다. Recursive lock끼리는 서로 block하지 않는다. Non-recursive lock끼리는 두 non-recursive read lock인 경우까지 서로 block한다. Non-recursive lock과 대응 recursive lock은 서로를 block할 수 있다.

Recursive lock이 포함된 실제 deadlock 형태

Task A는 Task B가 Y를 read_unlock()하기를 기다리고 Task B는 Task A가 X를 read_unlock()하기를 기다리므로 둘 다 진행할 수 없다.

Dependency edge 네 종류와 strong path

Lock dependency는 두 lock의 획득 순서를 기록한다. Locker가 세 종류이므로 이론상 dependency는 아홉 종류지만 deadlock detection에는 네 종류면 충분함을 보일 수 있다.

L1 -> L2는 같은 runtime context에서 L1을 보유한 뒤 L2를 획득한 이력을 lockdep이 봤다는 뜻이다. Deadlock detection에서 필요한 것은 L1을 보유한 상태로 L2에서 block될 수 있는지다. 즉 L1이 무엇을 block하는지와 무엇이 L2를 block하는지만 중요하다.

따라서 L1 쪽에서는 recursive reader와 non-recursive reader가 같은 type을 block하므로 합칠 수 있다. L2 쪽에서는 writer와 non-recursive reader가 같은 type에게 block되므로 합칠 수 있다.

두 lock 사이에는 dependency가 여러 개 있을 수 있다. Task A가 read_lock(X) 뒤 write_lock(Y)을 획득하고 Task B가 write_lock(X) 뒤 write_lock(Y)을 획득했다면 graph에는 X -(SN)-> Y와 X -(EN)-> Y가 모두 존재한다.

TASK A:
read_lock(X);
write_lock(Y);

TASK B:
write_lock(X);
write_lock(Y);

-(xN)->은 -(EN)-> 또는 -(SN)-> edge를 뜻한다. 같은 방식으로 -(Ex)->, -(xR)->, -(Sx)-> 표기를 사용한다.

Path는 graph에서 연속으로 이어진 dependency edge의 series다. Strong path는 path의 어떤 인접한 두 edge도 -(xR)-> 다음 -(Sx)-> 조합이 아닌 path로 정의한다.

다르게 말하면 X -> Y -> Z가 path에 있고 X에서 Y로 이동한 edge가 -(SR)-> 또는 -(ER)->라면 Y에서 Z로 이동하는 edge는 -(SN)-> 또는 -(SR)->일 수 없다. 다음 절에서 이 조건이 왜 strong이라 불리는지 증명한다.

Strong circle과 deadlock 가능성의 동치

두 lemma를 증명한다. Lemma 1은 closed strong path, 즉 strong circle이 있으면 deadlock을 만드는 locking sequence 조합이 존재한다는 명제다. Strong circle은 deadlock detection의 충분조건이다.

Lemma 2는 closed strong path가 없으면 deadlock을 만들 수 있는 locking sequence 조합도 없다는 명제다. Strong circle은 deadlock detection의 필요조건이다.

두 lemma를 합치면 closed strong path는 deadlock의 필요충분조건이고 deadlock 가능성과 동치다. Deadlock을 만들지 않는 dependency circle도 있으므로, deadlock 가능한 chain을 구별해 strong이라 부른다.

충분조건 증명: strong circle이면 deadlock을 구성할 수 있다

L1 -> L2 -> ... -> Ln -> L1인 strong circle이 있다고 하자. 이는 L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln, Ln -> L1 dependency가 있다는 뜻이다.

먼저 한 CPU 또는 task가 L1 -> L2에서 L1을 획득하게 하고, 다른 CPU 또는 task가 L2 -> L3에서 L2를 획득하게 하는 식으로 배치한다. 그러면 Lx -> Lx+1의 모든 Lx를 서로 다른 CPU 또는 task가 보유한다.

L1 holder가 L2 획득을 시도할 때 L2는 이미 다른 CPU 또는 task가 보유한다. Strong 정의 때문에 L1 -> L2와 L2 -> L3는 -(xR)-> 뒤 -(Sx)-> 조합이 아니다. 즉 앞 dependency의 L2가 누구에게나 block되는 non-recursive locker이거나 뒤 dependency의 L2가 누구든 block하는 writer다. 따라서 L1 holder는 L2를 얻지 못하고 L2 holder의 release를 기다린다.

같은 결론을 이어가면 L2 holder는 L3 holder를 기다리고 모든 Lx holder는 Lx+1 holder를 기다린다. Ln+1은 L1이므로 circular waiting이 완성되고 누구도 진행하지 못해 deadlock이 된다.

필요조건 증명: deadlock이면 strong circle이 존재한다

Lemma 2는 deadlock scenario가 있다면 dependency graph에 반드시 strong circle이 있다는 명제와 동치다.

Deadlock에는 circular waiting이 존재한다. N개의 CPU 또는 task P1...Pn이 있고 P1은 P2가 보유한 lock을, P2는 P3가 보유한 lock을 기다리며, 마지막 Pn은 P1이 보유한 lock을 기다린다.

Px가 기다리는 lock을 Lx라 하자. P1은 Ln을 보유하면서 L1을 기다리므로 dependency graph에 Ln -> L1이 있다. 같은 방식으로 L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln이 있어 Ln -> L1 -> L2 -> ... -> Ln circle이 만들어진다.

각 Lx에서 Px는 Lx-1 -> Lx dependency를 만들고 Px+1은 Lx -> Lx+1 dependency를 만든다. Px가 Px+1의 Lx release를 실제로 기다리므로 Px+1 쪽 Lx가 reader이고 Px 쪽 Lx가 recursive reader인 조합은 불가능하다. Recursive 여부와 상관없이 reader는 recursive reader를 block하지 않기 때문이다.

따라서 Lx-1 -> Lx와 Lx -> Lx+1은 -(xR)-> 뒤 -(Sx)-> pair일 수 없다. Circle의 모든 lock에 같은 사실이 성립하므로 이 circle은 strong이다.

참고 자료

• Deadlockhttps://en.wikipedia.org/wiki/Deadlock

Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill.