RT-mutex와 priority inheritance 구현

문서의 목적과 unbounded priority inversion

이 문서는 rtmutex.c 구현 설계를 설명한다. rtmutex.c가 존재하는 이유 자체는 Documentation/locking/rt-mutex.rst를 참고한다. 다만 code가 실제로 하는 일을 이해하기 위한 개념으로 이 code가 없을 때 생기는 문제도 설명한다.

목표는 사용된 priority inheritance(PI) algorithm과 PI를 현재 방식으로 구현한 설계 결정을 이해하도록 돕는 것이다. 원문 copyright는 2006 Steven Rostedt이며 GNU Free Documentation License 1.2로 제공된다.

Priority inversion은 high-priority process가 실행되기를 원하지만 low-priority process가 실행되는 상황이다. High-priority process가 low-priority process가 보유한 mutex 같은 resource를 필요로 하면 resource release까지 기다려야 하므로 어느 정도의 inversion은 피할 수 없다.

막아야 하는 것은 unbounded priority inversion이다. Low-priority process 때문에 high-priority process가 언제 끝날지 알 수 없는 시간 동안 실행되지 못하는 경우다.

Classic example에서 A가 가장 높은 priority, C가 가장 낮고 B는 중간이다. A가 C 소유 lock L1을 얻으려다 block되어 C가 release하기를 기다린다. 그 사이 B가 runnable이 되면 C보다 priority가 높아 C를 preempt한다. 결과적으로 B는 C를 통해 자신보다 priority가 높은 A까지 간접적으로 막는다. B가 CPU를 계속 사용하면 C가 L1을 release할 기회를 언제 얻을지 알 수 없다.

Priority inheritance와 핵심 용어

PI에서는 다른 process가 current process 소유 lock에서 block하면 current process가 그 process의 priority를 상속한다. 앞의 예에서 A가 C 소유 lock에 block하면 C가 A의 높은 priority를 상속한다. B가 runnable이 되어도 C를 preempt하지 못하고, C가 lock을 release하면 inherited priority를 잃으며 A가 resource를 사용할 수 있다.

Waiter object의 scope는 process가 mutex에서 block되는 code 안이므로 local variable로 task stack에 allocate해도 안전하다. 문맥에 따라 waiter라는 말이 기다리는 task, 즉 waiter->task를 가리키기도 한다. 이 문서는 task와 process를 같은 뜻으로 사용한다.

PI chain의 수렴과 priority 전파

PI chain은 priority inheritance를 만들 수 있는 process와 mutex의 list다. 한 process는 동시에 하나의 mutex에만 block될 수 있으므로 chain은 갈라지지 않지만, 한 process가 여러 mutex를 소유할 수 있어 여러 chain은 합쳐질 수 있다.

A가 L1을 소유하고 B가 L1을 기다리며, B가 L2를 소유하고 C가 기다리는 식으로 E까지 이어지면 chain은 E→L4→D→L3→C→L2→B→L1→A가 된다.

PI가 동작하려면 chain 오른쪽 끝, 또는 top의 process priority가 왼쪽이나 아래쪽 process와 같거나 더 높아야 한다.

Mutex에는 여러 process가 block될 수 있으므로 mutex 지점에서도 chain이 합쳐진다. G가 L2를 기다리면 G→L2→B→L1→A chain이 추가된다.

G가 전체 chain에서 가장 높은 priority라면 chain 위쪽 task인 B와 A의 priority를 G까지 올려야 한다.

Mutex waiters tree와 task PI tree

각 mutex는 자신에게 block된 모든 waiter를 priority 순서 rbtree에 저장한다. Mutex struct 안의 spinlock인 wait_lock이 이 tree를 보호한다.

PI chain을 추적하기 위해 각 process에는 독립 PI rbtree가 있다. 이 tree에는 process가 소유한 각 mutex의 top waiter만 들어가며 모든 waiter를 넣지는 않는다.

Task PI tree의 top은 그 task가 소유한 mutex 중 하나를 기다리는 가장 높은 priority task다. Owner task가 priority를 상속했다면 항상 이 top task의 priority를 상속한다.

이 tree는 task structure의 pi_waiters rbtree에 저장되고 같은 task structure의 pi_lock spinlock이 보호한다. pi_lock은 interrupt context에서도 획득될 수 있으므로 lock을 잡을 때 interrupt를 disable해야 한다.

PI chain depth는 함수 nesting만 보고 알 수 없다

Maximum PI chain depth는 dynamic하지 않아 이론상 정의할 수 있지만 모든 mutex nesting에 의존해 계산이 매우 복잡하다. L1, L2, L3와 네 function의 예를 보자.

void func1(void)
{
	mutex_lock(L1);
	/* do anything */
	mutex_unlock(L1);
}

void func2(void)
{
	mutex_lock(L1);
	mutex_lock(L2);
	/* do something */
	mutex_unlock(L2);
	mutex_unlock(L1);
}

void func3(void)
{
	mutex_lock(L2);
	mutex_lock(L3);
	/* do something else */
	mutex_unlock(L3);
	mutex_unlock(L2);
}

void func4(void)
{
	mutex_lock(L3);
	/* do something again */
	mutex_unlock(L3);
}

Process A·B·C·D가 각각 func1·func2·func3·func4를 실행하고 D가 먼저, A가 마지막에 실행된다고 하자. D가 func4 critical section에서 preempt되면 D owns L3, C blocked on L3 and owns L2, B blocked on L2 and owns L1, A blocked on L1 관계가 생긴다.

A -> L1 -> B -> L2 -> C -> L3 -> D

각 function의 lock nesting depth는 최대 2처럼 보이지만 process 네 개의 PI depth는 4가 된다. Compile-time locking depth가 정해져 있어도 가능한 chain depth를 찾기 어려운 이유다.

User-space application도 mutex를 정의할 수 있으므로 매우 많은 mutex를 nesting해 거대한 PI chain을 만들고 kernel이 spinlock을 가진 채 대량 data를 순회하게 하는 DOS를 막아야 한다. 구현은 maximum lock depth를 제한할 뿐 아니라 PI chain을 걷는 동안 동시에 최대 두 lock만 보유한다.

Owner pointer flag와 cmpxchg fast path

Mutex struct는 owner task pointer를 갖고 소유자가 없으면 NULL이다. 모든 architecture에서 task structure가 최소 2-byte aligned이므로 least significant bit를 flag로 쓸 수 있다. Bit 0은 Has Waiters flag이며 mutex에 waiter가 있으면 설정한다. 자세한 내용은 Documentation/locking/rt-mutex.rst에 있다.

일부 architecture는 atomic cmpxchg(Compare and Exchange)를 구현한다. 가능한 경우 mutex 획득·release fast path를 짧게 만드는 데 사용한다. 개념적으로 다음 operation을 atomic하게 수행한다.

unsigned long _cmpxchg(unsigned long *A, unsigned long *B,
                       unsigned long *C)
{
	unsigned long T = *A;
	if (*A == *B) {
		*A = *C;
	}
	return T;
}
#define cmpxchg(a,b,c) _cmpxchg(&a,&b,&c)

Variable이 expected value일 때만 update하며 return한 old A가 B와 같으면 성공한 것이다. rt_mutex_cmpxchg macro가 mutex lock·unlock을 시도한다. Architecture가 CMPXCHG를 지원하지 않으면 항상 fail하도록 정의되어 slow path로 가고, 지원하면 owner field flag와 함께 fast path를 크게 최적화한다.

pi_waiters top으로 priority를 boost·deboost

rtmutex.c PI code에는 process priority를 조정해야 하는 곳이 여러 군데 있다. Task의 pi_waiters 덕분에 필요한 조정을 쉽게 알 수 있다.

Task adjustment function은 rt_mutex_adjust_prio와 rt_mutex_setprio다. rt_mutex_setprio는 rt_mutex_adjust_prio에서만 사용되며 실제 priority 변경은 kernel/sched/core.c에 정의된 rt_mutex_setprio가 수행한다.

rt_mutex_adjust_prio는 task own priority와 task 소유 mutex 전체를 기다리는 process 중 가장 높은 priority를 비교한다. pi_waiters는 각 mutex top waiter를 priority 순으로 보유하므로 top pi waiter와 task의 normal/deadline priority 중 높은 쪽을 고르면 된다.

Higher-priority process가 task 소유 mutex에 block되면 rt_mutex_adjust_prio가 task를 boost한다. 반대로 그 waiter가 timeout 또는 signal로 떠나면 같은 함수가 task를 deboost한다. pi_waiters top과 normal priority만 비교하면 두 방향을 모두 처리할 수 있다.

rt_mutex_adjust_prio_chain의 고수준 동작

PI chain walk는 rt_mutex_adjust_prio_chain이 구현한다. 여러 iteration을 거쳐 동시에 최대 두 lock만 잡고 chain을 걷는 효율적인 형태가 되었다. Process priority를 boost하거나 낮추는 양쪽에 사용한다.

Input에는 PI boost/deboost를 검사할 task, deadlock 검사 flag, task가 소유한 mutex, 그 mutex에 block된 process의 waiter pointer(deboost 때 NULL일 수 있음), task가 block된 mutex pointer, mutex의 top waiter인 top_task가 들어간다.

이 설명은 deadlock detection을 제외하고 high level에 집중한다. Function 진입 시 보유한 lock이 없으므로 진입하는 동안 owner와 lock state가 바뀔 수 있다.

호출 전에 task에는 이미 rt_mutex_adjust_prio가 실행되어 필요한 priority로 설정되어 있다. 하지만 task waiter의 rbtree node priority와 pi_waiters·waiters tree 위치는 아직 갱신되지 않았을 수 있다. rt_mutex_adjust_prio_chain이 이를 바로잡는다. 더 자세한 요약은 rtmutex.c의 Chain walk basics and protection scope comment에 있다.

Mutex 획득 fast path와 slow path

Mutex 획득은 먼저 fast path를 시도한다. CMPXCHG가 enable되어 있고 owner field가 NULL일 때만 atomic exchange로 lock을 얻으며 추가 작업은 필요 없다. CMPXCHG가 없으면 fast attempt는 자동으로 실패한다.

Contention이 있으면 rt_mutex_slowlock slow path로 간다. 이 function에서 waiter struct를 stack에 만든다. Waiter는 이 function scope에서만 필요하며 mutex waiters tree와 필요 시 owner pi_waiters tree에 task를 넣을 node를 보유한다.

Mutex slow unlock path도 사용하는 wait_lock을 획득해 locking과 unlocking을 동기화한다. 그 뒤 try_to_take_rt_mutex를 호출한다. CMPXCHG가 없는 architecture에서는 contention이 없을 때 이 경로에서 lock을 얻게 된다.

Slow path에서 매 획득 시도마다 try_to_take_rt_mutex를 사용한다. 먼저 owner field의 Has Waiters flag를 atomically 설정한다. 그러면 current owner는 slow unlock path로 들어가 현재 code가 가진 wait_lock을 잡아야 하므로 이 경로와 반드시 synchronize한다.

Lock owner가 없고 current task가 모든 waiter 중 highest priority일 때만 lock을 획득한다. 성공하면 current task를 owner로 설정하고 waiter가 더 있으면 top_waiter를 새 owner task의 pi_waiters tree에 추가한다.

try_to_take_rt_mutex()가 실패하면 task_blocks_on_rt_mutex()를 호출한다. Task를 mutex waiters tree에 추가하고 owner pi_waiters tree와 lock PI chain에 priority를 전파한다.

Task block accounting과 wakeup loop

Mutex와 process의 관계는 process waiter struct로 기록한다. task field는 process, lock field는 mutex를 가리키며 waiter rbtree node를 current process priority로 초기화한다.

Slow lock 진입 때 wait_lock을 획득했으므로 waiter를 mutex waiter tree에 안전하게 넣을 수 있다. Current process가 mutex의 새 highest-priority waiter라면 기존 top waiter를 owner pi_waiters에서 제거하고 current process를 추가한다. Owner pi_waiter가 바뀌었으므로 rt_mutex_adjust_prio로 owner priority 조정 여부를 확인한다.

Owner도 다른 lock에 block되어 있고 pi_waiters가 바뀌었거나 deadlock check가 켜져 있으면 mutex wait_lock을 풀고 owner에 대해 rt_mutex_adjust_prio_chain을 실행한다.

모든 lock을 release한 뒤 current process가 여전히 mutex에 block되어 있다면, 즉 waiter task field가 NULL이 아니면 schedule()로 sleep한다.

Task가 깨는 이유는 이전 owner가 release하여 task가 top_waiter가 되었거나 signal·timeout을 받은 경우다. 두 경우 모두 lock 획득을 다시 시도한다. 성공하면 waiters tree에서 자신을 제거하고 TASK_RUNNING으로 돌아간다.

첫 경우 다른 task가 먼저 lock을 얻었다면 다시 sleep하여 다음 wakeup을 기다린다. 두 번째는 rt_mutex_timed_futex_lock()처럼 signal 또는 timeout으로 lock 전에 깰 수 있는 mutex에만 해당한다. 재시도 성공 시 lock을 보유한 채 return하고 실패하면 signal은 -EINTR, timeout은 -ETIMEDOUT을 반환한다.

Unlock fast path, slow path와 pending owner wakeup

CMPXCHG architecture에서는 unlock도 fast path가 있다. Contended acquisition이 항상 owner field의 Has Waiters flag를 설정하므로 unlock 시 slow path 필요 여부를 알 수 있다. Waiter가 없으면 owner field가 current process와 같고 이를 NULL로 바꾸기만 하면 된다.

Owner field에 Has Waiters bit가 있거나 CMPXCHG가 없으면 slow unlock으로 간다. 먼저 mutex wait_lock을 잡아 lock·unlock path를 동기화한다.

그 뒤 waiter 존재 여부를 다시 검사한다. CMPXCHG가 없는 architecture는 여기서 깨울 waiter를 결정한다. CMPXCHG가 있어도 slow path에는 재검사가 필요하다. Owner가 fast CMPXCHG check에 실패한 뒤 wait_lock을 잡기 전 사이에 waiter가 signal 또는 timeout으로 떠났을 수 있기 때문이다. Waiter가 없으면 owner=NULL로 만들고 wait_lock을 release한 뒤 끝낸다.

Waiter가 있으면 하나를 깨운다. Wakeup code는 current owner의 pi_lock을 잡고 mutex top waiter를 찾아 mutex waiters tree와 current owner pi_waiters tree에서 제거한다. Lower-priority task가 lock을 steal하지 못하도록 Has Waiters bit를 표시한다. 마지막으로 pending owner의 pi_lock을 풀고 그 task를 wake up한다.

문서 연락처와 이력

문서 update 연락처는 Steven Rostedt <rostedt@goodmis.org>다. Author는 Steven Rostedt이고 Alex Shi가 2017년 7월 6일 update했다.

Original reviewer는 Ingo Molnar, Thomas Gleixner, Thomas Duetsch, Randy Dunlap이며 2017년 update reviewer는 Steven Rostedt와 Sebastian Siewior다.

이 문서는 원래 2.6.17-rc3-mm1을 위해 작성되었고 4.12에서 update되었다.