Futex requeue PI

Requeue PI가 필요한 불변 조건

Task를 non-PI futex에서 PI futex로 requeue할 때는 특별한 처리가 필요하다. 기반 rt_mutex에 waiter가 있는데 owner가 없는 상태를 절대로 만들면 안 되기 때문이다. 그런 상태는 rt-mutex-design.rst에서 설명하는 PI priority boosting logic을 깨뜨린다.

이 문서에서는 이 동작을 줄여서 requeue_pi라고 부르고 priority inheritance는 PI로 표기한다.

pthread_cond_broadcast()와 thundering herd

requeue_pi가 없으면 glibc의 pthread_cond_broadcast() 구현은 pthread condition variable에서 기다리는 모든 task를 깨워야 한다. 깨어난 task들은 누가 먼저 실행할지를 두고 고전적인 thundering herd 형태로 경쟁한다.

이상적인 구현은 가장 높은 priority의 waiter 하나만 깨우고, 나머지는 condition variable과 연결된 mutex가 unlock될 때 자연스럽게 이어지는 wakeup에 맡기는 방식이다.

일반 condvar requeue의 문제

/* caller must lock mutex */
pthread_cond_wait(cond, mutex)
{
    lock(cond->__data.__lock);
    unlock(mutex);
    do {
        unlock(cond->__data.__lock);
        futex_wait(cond->__data.__futex);
        lock(cond->__data.__lock);
    } while (...)
    unlock(cond->__data.__lock);
    lock(mutex);
}

pthread_cond_broadcast(cond)
{
    lock(cond->__data.__lock);
    unlock(cond->__data.__lock);
    futex_requeue(cond->data.__futex, cond->mutex);
}

pthread_cond_broadcast()가 task를 requeue하면 cond->mutex에 waiter가 생긴다. 하지만 pthread_cond_wait()는 userspace로 돌아온 뒤에야 mutex lock을 시도한다. 이 사이에는 기반 rt_mutex에 waiter는 있지만 owner는 없는 상태가 되어 PI boosting algorithm의 전제를 깨뜨린다.

PI-aware condvar의 호출 형태

PI를 인식하는 pthread condition variable을 지원하려면 kernel이 task를 PI futex로 requeue할 수 있어야 한다. 이 방식에서는 futex_wait system call이 성공하면 caller가 PI futex를 이미 보유한 채 userspace로 돌아온다.

/* caller must lock mutex */
pthread_cond_wait_pi(cond, mutex)
{
    lock(cond->__data.__lock);
    unlock(mutex);
    do {
        unlock(cond->__data.__lock);
        futex_wait_requeue_pi(cond->__data.__futex);
        lock(cond->__data.__lock);
    } while (...)
    unlock(cond->__data.__lock);
    /* the kernel acquired the mutex for us */
}

pthread_cond_broadcast_pi(cond)
{
    lock(cond->__data.__lock);
    unlock(cond->__data.__lock);
    futex_requeue_pi(cond->data.__futex, cond->mutex);
}

실제 glibc는 PI 전용 API를 새로 만들기보다 기존 호출 안에서 PI 여부를 검사하고 필요한 동작을 선택할 가능성이 높다. pthread_cond_timedwait()와 pthread_cond_signal()에도 같은 변경이 필요하다.

Owner 없는 rt_mutex를 막는 proxy lock

rt_mutex에 waiter가 있다면 반드시 owner도 있도록 보장하려면 requeue code와 wait code 모두 userspace로 돌아가기 전에 rt_mutex를 획득할 수 있어야 한다. Requeue code가 waiter를 깨운 뒤 waiter 스스로 rt_mutex를 획득하게 두면 requeue system call이 userspace로 돌아간 시점과 waiter가 실제로 깨어 실행되는 시점 사이에 race window가 생긴다. 경쟁이 없는 경우에도 이 문제는 중요하다.

해결책은 rt_mutex_start_proxy_lock()과 rt_mutex_finish_proxy_lock()이라는 두 helper다. Requeue code는 waiter를 대신해 경쟁 없는 rt_mutex를 획득하거나, 경쟁 중인 rt_mutex의 wait queue에 waiter를 넣을 수 있다.

Kernel과 userspace 사이의 requeue_pi interface는 FUTEX_WAIT_REQUEUE_PI와 FUTEX_CMP_REQUEUE_PI라는 두 futex operation이 제공한다.

FUTEX_WAIT_REQUEUE_PI

Waiter 측의 pthread_cond_wait()와 pthread_cond_timedwait()는 FUTEX_WAIT_REQUEUE_PI를 호출해 최초 futex에서 block되고 PI-aware futex로 requeue되기를 기다린다. 구현은 futex_wait()와 futex_lock_pi()를 결합한 형태이며 추가 wakeup 상황을 검사하는 logic이 더해져 있다.

FUTEX_CMP_REQUEUE_PI

Waker 측의 pthread_cond_broadcast()와 pthread_cond_signal()은 FUTEX_CMP_REQUEUE_PI를 호출해 기다리는 task를 requeue하고 가능하면 깨운다. Kernel 내부에서는 requeue_pi=1을 넘긴 futex_requeue()가 이 operation을 처리한다.

Requeue 전에 futex_requeue()는 가장 높은 priority의 waiter를 대신해 target PI futex 획득을 시도한다. 획득할 수 있으면 해당 waiter를 깨운다. 이어서 남은 nr_wake+nr_requeue개 task를 PI futex로 옮기며, 각 requeue 전에 rt_mutex_start_proxy_lock()을 호출해 task를 기반 rt_mutex의 waiter로 준비한다. 이 단계에서 lock을 획득할 수 있다면 다음 waiter를 깨워 lock 획득을 마무리하게 한다.

FUTEX_CMP_REQUEUE_PI는 nr_wake와 nr_requeue를 받지만 실질적으로 중요한 값은 둘의 합이다. futex_requeue()는 최대 nr_wake+nr_requeue개 task를 깨우거나 requeue한다. 실제로 깨우는 수는 lock을 대신 획득할 수 있는 task 수뿐이다.

올바른 사용에서는 pthread_cond_broadcast()나 pthread_cond_signal() caller가 먼저 mutex를 보유하므로 대개의 경우 즉시 깨울 수 있는 task 수는 0이다. FUTEX_CMP_REQUEUE_PI는 nr_wake=1을 요구한다. Broadcast에서는 nr_requeue=INT_MAX, signal에서는 nr_requeue=0을 사용한다.