Kernel completion 동기화

Completion barrier가 필요한 이유

하나 이상의 thread가 kernel activity가 특정 지점이나 상태에 도달하기를 기다려야 할 때 completion은 race 없는 해결책을 제공한다. 의미상 pthread_barrier()와 어느 정도 비슷하고 사용 사례도 유사하다.

Completion은 lock이나 semaphore의 오용, busy loop보다 선호되는 code synchronization mechanism이다. 다른 작업이 진행되게 하려고 yield() 또는 임의의 msleep(1) loop를 생각하고 있다면 wait_for_completion*()과 complete()를 검토해야 한다.

Completion은 목적이 명확해 code의 의도를 쉽게 알 수 있다. 결과가 실제로 필요할 때까지 모든 thread가 실행을 계속할 수 있고, wait와 signal 모두 scheduler의 저수준 sleep/wakeup facility를 사용하므로 효율적이다.

Completion은 Linux scheduler의 waitqueue와 wakeup infrastructure 위에 구현한다. Waitqueue의 thread가 기다리는 event는 struct completion의 done이라는 단순한 flag로 축약된다. 관련 code는 kernel/sched/completion.c에 있다.

세 구성 요소와 struct completion

• struct completion synchronization object 초기화
• wait_for_completion() variant 중 하나를 호출하는 wait side
• complete() 또는 complete_all()을 호출하는 signal side

Completion 상태를 검사하는 helper도 있다. 초기화는 반드시 먼저 해야 하지만 wait와 signal의 순서는 어느 쪽이 먼저여도 된다. 한 thread가 wait 여부를 검사하기 전에 다른 thread가 completion을 done으로 표시하는 것은 완전히 정상적인 동작이다.

사용하려면 <linux/completion.h>를 include하고 static 또는 dynamic struct completion 변수를 만든다. Structure에는 두 field만 있다.

struct completion {
    unsigned int done;
    struct swait_queue_head wait;
};

wait는 기다릴 task를 넣는 waitqueue이고 done은 완료 여부를 나타내는 flag다. Completion 이름은 동기화 대상 event를 나타내야 한다.

wait_for_completion(&early_console_added);

complete(&early_console_added);

이처럼 직관적인 이름은 가독성을 높인다. 목적이 아주 명백한 경우가 아니라면 completion object를 complete라고 이름 짓는 것은 도움이 되지 않는다.

Dynamic object 초기화와 lifetime

Dynamic allocation한 completion은 가능하면 function 또는 driver의 전체 lifetime 동안 살아 있음이 보장되는 data structure 안에 넣어야 한다. 그래야 asynchronous complete() 호출과 object 해제 사이의 race를 막을 수 있다.

wait_for_completion()의 _timeout(), _killable(), _interruptible() variant는 특히 주의해야 한다. Timeout 또는 signal 때문에 wait가 일찍 return하더라도 관련 complete()와 reinit_completion() activity가 모두 끝날 때까지 memory를 해제해서는 안 된다.

init_completion(&dynamic_object->done);

init_completion()은 waitqueue를 초기화하고 done을 0, 즉 not completed 상태로 만든다. reinit_completion()은 waitqueue를 건드리지 않고 done만 0으로 reset한다. 호출자는 동시에 진행 중인 wait_for_completion()과 race하지 않도록 보장해야 한다.

같은 object에 init_completion()을 두 번 호출하면 queue를 빈 queue로 다시 초기화하여 이미 enqueue된 task를 잃을 수 있으므로 대부분 bug다. 재사용에는 reinit_completion()을 쓰되 다른 race도 고려해야 한다.

Static 및 stack object 초기화

File scope의 static 또는 global declaration에는 DECLARE_COMPLETION()을 사용한다.

static DECLARE_COMPLETION(setup_done);
DECLARE_COMPLETION(setup_done);

이 경우 boot 또는 module load 시 not done 상태로 초기화되므로 init_completion()을 따로 호출하지 않는다.

Function local variable로 선언할 때에는 DECLARE_COMPLETION_ONSTACK()을 명시적으로 사용해야 한다. Lockdep을 만족시키는 것뿐 아니라 제한된 scope를 의도적으로 검토했음을 드러낸다.

DECLARE_COMPLETION_ONSTACK(setup_done)

Stack object는 function stack의 lifetime이 짧다는 점을 엄격히 고려해야 한다. 기다리는 thread를 포함한 모든 activity가 끝나고 object를 아무도 사용하지 않을 때까지 function이 caller로 return해서는 안 된다.

특히 _timeout(), _killable(), _interruptible()은 object를 다른 thread가 여전히 사용하는데 wait만 먼저 끝날 수 있다. Caller가 return하여 stack을 해제한 뒤 다른 thread가 complete()를 호출하면 찾기 어려운 data corruption이 생긴다. 단순한 test에서는 이런 race가 드러나지 않을 수 있다.

확신할 수 없다면 helper thread보다 lifetime이 충분히 긴 object 안에 dynamic completion을 넣거나, 해제된 object에 complete()가 호출되지 않도록 lock 또는 다른 synchronization mechanism을 둔다. Stack에서 단순 DECLARE_COMPLETION()을 사용하면 lockdep warning이 발생한다.

wait_for_completion() 동작과 context 제약

void wait_for_completion(struct completion *done)

동시에 수행되는 activity가 끝나기를 기다리는 thread는 초기화된 completion에 wait_for_completion()을 호출한다. 원문의 두 CPU ASCII 예시는 다음 단계로 정리할 수 있다.

이 도식은 두 호출의 순서를 강제하지 않는다. complete()가 먼저 실행되었다면 dependency가 이미 충족되었으므로 wait side는 즉시 계속한다. 그렇지 않으면 complete()가 signal할 때까지 block된다.

wait_for_completion()은 spin_lock_irq()와 spin_unlock_irq()를 호출하므로 interrupt가 enable되어 있음을 아는 상황에서만 안전하다. IRQ-off atomic context에서 호출하면 찾기 어려운 방식으로 interrupt를 잘못 enable할 수 있다.

기본 동작은 timeout 없이 task를 TASK_UNINTERRUPTIBLE로 두고 기다리는 것이다. Sleep할 수 있으므로 wait_for_completion()과 variant는 process context에서만 안전하다. Atomic context, interrupt context, IRQ disabled 상태, preemption disabled 상태에서는 사용할 수 없다. Atomic 또는 interrupt context에서는 아래의 try_wait_for_completion()을 검토한다.

모든 wait_for_completion() variant는 대상 activity에 따라 오래 block될 수 있으므로 대부분의 경우 mutex를 잡은 채 호출해서는 안 된다.

wait_for_completion*() variant와 return value

아래 variant는 status를 return하므로 대부분 또는 모든 경우 이를 검사해야 한다. 의도적으로 무시한다면 이유를 comment로 남기는 편이 좋다. Return value는 정확한 type의 변수에 받아야 한다.

Return value 의미를 부정확하게 검사하는 흔한 오류가 있다.

if (!wait_for_completion_interruptible_timeout(...))

이 형태는 성공적 completion과 signal로 interrupt된 경우를 같은 code path로 처리할 수 있어 의도와 다를 가능성이 높다.

Timeout은 code가 CONFIG_HZ에 거의 독립적이도록 msecs_to_jiffies() 또는 usecs_to_jiffies()로 계산하는 편이 좋다. Return된 timeout 값을 의도적으로 무시한다면 그 이유를 comment로 설명해야 한다. _io variant의 waiting on IO accounting은 scheduling 및 I/O 통계에서 task를 계산하는 방식에 영향을 준다.

complete()와 complete_all()

계속 실행할 조건이 충족되었음을 알리는 thread는 complete()로 waiter 하나만 깨우거나 complete_all()로 현재와 미래의 모든 waiter를 깨운다.

void complete(struct completion *done)
void complete_all(struct completion *done)

Thread가 wait를 시작하기 전에 signal해도 정상 동작한다. Waiter가 struct completion의 done을 감소시키며 게시된 completion 하나를 소비하기 때문이다. Waiting thread는 enqueue된 FIFO 순서로 깨어난다.

complete()를 여러 번 호출하면 호출할 때마다 done이 증가하여 그 횟수만큼 waiter가 계속 실행할 수 있다. 반면 complete_all()을 여러 번 호출하는 것은 bug다. complete()와 complete_all()은 IRQ 또는 atomic context에서 안전하게 호출할 수 있다.

특정 struct completion에 대해 한 순간에는 thread 하나만 complete() 또는 complete_all()을 호출해야 하며 waitqueue spinlock으로 serialize된다. Concurrent signal 호출이 필요해 보인다면 설계 bug일 가능성이 높다.

IRQ context에서 completion을 signal하는 것은 안전하다. spin_lock_irqsave()와 spin_unlock_irqrestore()로 적절히 lock하며 절대 sleep하지 않는다.

try_wait_for_completion()과 completion_done()

bool try_wait_for_completion(struct completion *done)
bool completion_done(struct completion *done)

try_wait_for_completion()은 thread를 waitqueue에 넣지 않는다. Enqueue하여 block해야 하는 상태면 false를 return한다. 게시되어 아직 소비되지 않은 completion이 있으면 하나를 소비하고 true를 return한다.

completion_done()은 completion 상태를 바꾸지 않고 검사한다. Waiter가 아직 소비하지 않은 게시된 completion이 하나도 없으면 false를, 있으면 true를 return한다. 두 function 모두 IRQ 또는 atomic context에서 호출해도 안전하다.