Wound/Wait ww_mutex 설계

여러 GPU buffer lock과 deadlock 문제

GPU operation은 흔히 여러 buffer를 함께 사용한다. Buffer는 context와 process 사이에서 공유되고 VRAM과 system memory처럼 서로 다른 memory domain에 있을 수 있으며 PRIME/dmabuf를 통해 device 사이에서도 공유된다. Driver가 buffer 준비를 기다려야 하는 상황이 생긴다.

Buffer mutex가 풀리기를 기다린다고 생각하면 문제가 보인다. 모든 context에서 execbuf/batch의 buffer 순서가 같다고 보장할 수 없다. 순서는 userspace와 application의 GL call sequence가 결정하므로 deadlock 가능성이 있다.

Kernel이 GPU operation 전에 buffer를 VRAM으로 migration해야 하고 이를 위해 다른 buffer를 evict해야 하는 상황까지 고려하면 더 복잡하다. 이미 GPU에 queue된 buffer를 evict해서도 안 된다. 다만 기본 문제를 이해할 때에는 이 세부 사항을 생략할 수 있다.

Wait-Die와 Wound-Wait

TTM graphics subsystem이 사용한 기본 algorithm은 단순하다. Lock해야 할 각 buffer group, 즉 execbuf에 global counter에서 고유 reservation id 또는 ticket을 부여한다. 모든 buffer를 lock하다 deadlock이 생기면 ticket이 가장 낮은 오래된 task가 이긴다. Reservation id가 높은 젊은 task는 이미 lock한 모든 buffer를 unlock하고 다시 시도한다.

RDBMS 문헌에서는 reservation ticket을 transaction과 연결하며 이 deadlock 처리 방식을 Wait-Die라고 한다. Lock을 잡은 transaction이 더 젊으면 lock을 요청한 오래된 transaction은 기다린다. Holder가 더 오래되었으면 젊은 requester가 물러나 죽는다.

Wound-Wait에서는 lock holder가 더 젊으면 오래된 requester가 holder를 wound하여 죽도록 요청한다. Holder가 더 오래되었으면 requester가 기다린다.

두 algorithm 모두 transaction이 결국 성공한다는 점에서 fair하다. Wound-Wait는 일반적으로 Wait-Die보다 backoff가 적지만 backoff recovery 작업은 더 많다. 다른 transaction이 wound하는 preemptive algorithm이므로 wounded 상태를 확실히 감지해 실행 transaction을 중단할 방법이 필요하다. 이는 process preemption과 다르다. Wound 뒤 -EDEADLK를 return하며 transaction이 죽을 때 Wound-Wait transaction이 preempt된 것으로 본다.

Acquire context, ww class, lock API

일반 mutex와 비교하면 ww mutex interface에는 두 개념이 추가된다.

Acquire context는 transaction을 나타낸다. Forward progress를 보장하려면 task가 lock acquisition을 다시 시도할 때 새 reservation id를 받지 않고 처음 시작할 때 받은 ticket을 유지해야 한다. Context는 ticket과 ww mutex interface 오용을 찾기 위한 debug state를 보관한다.

WW class는 lock class와 사용할 algorithm을 명시한다. 일반 mutex와 달리 acquire context 초기화에 class가 필요하며 Wound-Wait 또는 Wait-Die 중 하나를 선택한다.

_slow function은 의미상 꼭 필요하지는 않다. 다른 ww mutex를 모두 놓은 뒤 normal ww_mutex_lock()을 contended lock에 다시 호출해도 deadlock 가능성이 없어 block하고 -EDEADLK를 조기 return하지 않는다. 하지만 _slow는 interface safety를 높인다.

• ww_mutex_lock은 __must_check int를 return하지만 ww_mutex_lock_slow는 void다. Retry loop가 필요하므로 첫 lock이 실패하지 않아도 __must_check가 불필요한 warning을 만들지는 않는다.
• Full debugging에서 ww_mutex_lock_slow는 획득했던 모든 ww mutex를 놓았는지 검사하여 deadlock을 막고 contended lock에서 실제로 block하는지 확인하여 -EDEADLK slowpath를 spin하는 일을 막는다.
• WW mutex 하나만 필요하면 acquire context와 deadlock avoidance ticket을 만들 필요가 없으므로 NULL context를 쓴다.
• Signal wakeup을 처리하는 일반 variant도 모두 제공한다.

Class 선택과 method 1: 순서를 바꿀 수 없는 list

DEFINE_WW_CLASS()는 Wound-Wait, DEFINE_WD_CLASS()는 Wait-Die를 선택한다. 동시에 경쟁하는 transaction 수가 보통 적고 rollback 수를 줄이고 싶다면 대략적인 기준으로 Wound-Wait를 사용한다.

Method 1과 2에서 공통으로 쓰는 type은 다음과 같다.

static DEFINE_WW_CLASS(ww_class);

struct obj {
    struct ww_mutex lock;
    /* obj data */
};

struct obj_entry {
    struct list_head head;
    struct obj *obj;
};

Method 1은 execbuf->buffers list 순서를 바꿀 수 없을 때 사용한다. 필요한 object list를 이미 다른 곳에서 추적하는 경우에 유용하다. Duplicate entry가 있으면 lock helper가 -EALREADY를 caller에 전달할 수 있어 userspace input으로 만든 list에서 중복을 금지하는 ABI, 예를 들어 GPU command buffer submission ioctl에 적합하다.

int lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
    struct obj *res_obj = NULL;
    struct obj_entry *contended_entry = NULL;
    struct obj_entry *entry;

    ww_acquire_init(ctx, &ww_class);

retry:
    list_for_each_entry(entry, list, head) {
        if (entry->obj == res_obj) {
            res_obj = NULL;
            continue;
        }
        ret = ww_mutex_lock(&entry->obj->lock, ctx);
        if (ret < 0) {
            contended_entry = entry;
            goto err;
        }
    }

    ww_acquire_done(ctx);
    return 0;

err:
    list_for_each_entry_continue_reverse(entry, list, head)
        ww_mutex_unlock(&entry->obj->lock);

    if (res_obj)
        ww_mutex_unlock(&res_obj->lock);

    if (ret == -EDEADLK) {
        /* seqno race에서 패배: contended lock을 잡고 다시 시도 */
        ww_mutex_lock_slow(&contended_entry->obj->lock, ctx);
        res_obj = contended_entry->obj;
        goto retry;
    }
    ww_acquire_fini(ctx);

    return ret;
}

실패하면 지금까지 획득한 lock을 역순으로 놓는다. -EDEADLK이면 contended object만 slowpath로 먼저 lock하고 같은 acquire context와 ticket으로 list 전체를 다시 순회한다. Retry 중 res_obj를 만나면 이미 획득했으므로 건너뛴다.

Method 2: 재정렬할 수 있는 list

Method 2는 execbuf->buffers list를 재정렬할 수 있을 때 사용한다. Method 1과 같이 -EALREADY로 duplicate를 감지하지만 contended entry를 list head로 옮겨 더 자연스러운 retry loop를 만든다.

int lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
    struct obj_entry *entry, *entry2;

    ww_acquire_init(ctx, &ww_class);

    list_for_each_entry(entry, list, head) {
        ret = ww_mutex_lock(&entry->obj->lock, ctx);
        if (ret < 0) {
            entry2 = entry;

            list_for_each_entry_continue_reverse(entry2, list, head)
                ww_mutex_unlock(&entry2->obj->lock);

            if (ret != -EDEADLK) {
                ww_acquire_fini(ctx);
                return ret;
            }

            /* seqno race에서 패배: contended lock을 잡고 다시 시도 */
            ww_mutex_lock_slow(&entry->obj->lock, ctx);

            /* contended entry를 head로 옮겨 다음 unlocked entry부터 재시작 */
            list_del(&entry->head);
            list_add(&entry->head, list);
        }
    }

    ww_acquire_done(ctx);
    return 0;
}

Method 1과 2의 unlock 방식은 같다. 모든 object lock을 놓은 뒤 acquire context를 fini한다.

void unlock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
    struct obj_entry *entry;

    list_for_each_entry(entry, list, head)
        ww_mutex_unlock(&entry->obj->lock);

    ww_acquire_fini(ctx);
}

Method 3: graph를 걸으며 동적으로 object 발견

Method 3은 object list를 미리 만들지 않고 임시로 구성할 때 유용하다. 각 node가 ww_mutex를 가진 graph에서 관련 node의 lock을 모두 잡아야 edge를 바꿀 수 있는 경우가 예다.

• WW mutex는 임의 순서 acquisition을 처리하므로 시작 node에서 graph를 순회하면서 새 edge와 연결 node를 발견할 때마다 lock할 수 있다.
• -EALREADY가 이미 보유한 object를 알려 주므로 graph cycle을 끊거나 이미 잡은 lock을 따로 기록할 필요가 없다. 여러 starting node를 써도 같다.

Method 1·2와는 두 차이가 있다. 동적 object list는 -EDEADLK retry 때 달라질 수 있으므로 lock하지 않은 object를 persistent list에 둘 필요가 없고 list_head를 object 자체에 넣을 수 있다. 반면 dynamic construction에서는 -EALREADY를 caller에 전달할 수 없다.

Method 1 또는 2로 userspace가 전달한 시작 node list를 먼저 lock한 뒤 method 3으로 추가 affected object를 lock하는 결합도 가능하다. Dynamic 단계에서 -EDEADLK가 나면 fixed list에서 얻은 lock도 모두 놓아야 하므로 backoff/retry가 복잡해진다. WW mutex debug check는 이런 결합의 interface 오용도 찾는다.

Method 3은 -EALREADY를 error로 전달하지 않으므로 non-interruptible 예제의 lock acquisition step은 실패하지 않는다. _interruptible variant는 이 예제 범위 밖이다.

Method 3 code

struct obj {
    struct ww_mutex ww_mutex;
    struct list_head locked_list;
};

static DEFINE_WW_CLASS(ww_class);

void __unlock_objs(struct list_head *list)
{
    struct obj *entry, *temp;

    list_for_each_entry_safe(entry, temp, list, locked_list) {
        /* 현재 lock holder만 object를 쓸 수 있으므로 unlock 전에 제거 */
        list_del(&entry->locked_list);
        ww_mutex_unlock(entry->ww_mutex);
    }
}

void lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
    struct obj *obj;

    ww_acquire_init(ctx, &ww_class);

retry:
    /* loop 시작 상태를 다시 초기화 */
    loop {
        /* graph를 순회하며 lock할 object를 고르는 code */

        ret = ww_mutex_lock(obj->ww_mutex, ctx);
        if (ret == -EALREADY) {
            /* 이미 보유했으므로 다음 object로 진행 */
            continue;
        }
        if (ret == -EDEADLK) {
            __unlock_objs(list);

            ww_mutex_lock_slow(obj, ctx);
            list_add(&entry->locked_list, list);
            goto retry;
        }

        /* 새 object를 lock했으므로 list에 추가 */
        list_add_tail(&entry->locked_list, list);
    }

    ww_acquire_done(ctx);
    return 0;
}

void unlock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
    __unlock_objs(list);
    ww_acquire_fini(ctx);
}

원문 예제는 algorithm 구조를 보여 주는 pseudo-code 성격이며 entry와 obj 사용 등 실제 code에 맞게 보완해야 할 부분이 있다. 핵심은 acquired object를 object 내부 locked_list로 추적하고 -EDEADLK 때 전부 unlock한 뒤 contended object를 slowpath로 선점해 graph walk를 다시 시작하는 것이다.

Method 4: object 하나만 lock

Object 하나만 lock하면 같은 class 안에서 deadlock을 만들 수 없으므로 deadlock detection과 prevention은 불필요하다. 이 경우 NULL acquire context로 ww mutex API를 사용한다.

ww_mutex_lock(&obj->lock, NULL);

구현 invariant와 lazy wound preemption

현재 ww_mutex는 struct mutex를 감싼다. 훨씬 흔한 normal mutex lock에는 추가 overhead가 없고 wait/wound mutex를 사용하지 않으면 code size만 조금 증가한다.

Wait list에는 다음 invariant를 유지한다.

• Acquire context가 있는 waiter는 stamp 순서로 정렬한다. Context가 없는 waiter는 FIFO 순서로 사이에 배치한다.
• Wait-Die에서는 context가 있는 waiter 중 첫 번째만 다른 lock을 이미 획득한 상태(ctx->acquired > 0)일 수 있다. 이 waiter 앞에 context 없는 waiter가 있을 수 있다.

Wound-Wait preemption은 lazy-preemption scheme으로 구현한다. 새 lock에 contention이 생겨 실제 deadlock 가능성이 있을 때만 transaction의 wounded 상태를 검사한다. Wounded transaction은 backoff하고 상태를 clear한 뒤 retry한다.

이 방식의 큰 장점은 transaction을 다시 시작하기 전에 기다릴 contended lock을 식별할 수 있다는 점이다. 아무 lock도 우선 확보하지 않고 무작정 다시 시작하면 같은 상황에서 또 backoff할 가능성이 크다.

일반적으로 contention은 많지 않을 것으로 예상한다. Lock은 주로 device resource access를 serialize하므로 optimization은 uncontended case에 집중해야 한다.

Lockdep이 찾는 API 오용

가능한 많은 API 오용을 warning하도록 특별히 신경 썼다. 일부 흔한 오류는 CONFIG_DEBUG_MUTEXES로 찾지만 CONFIG_PROVE_LOCKING을 권장한다.

• ww_acquire_fini() 또는 ww_acquire_init() 호출 누락
• ww_acquire_done() 뒤 추가 mutex lock 시도
• -EDEADLK 뒤 모든 mutex를 놓고 잘못된 mutex lock 시도
• -EDEADLK 뒤 모든 mutex를 놓기 전에 올바른 contended mutex를 lock하려는 시도
• -EDEADLK를 받기 전에 ww_mutex_lock_slow() 호출
• 잘못된 unlock function으로 mutex unlock
• 같은 context에 동일한 ww_acquire_* function을 두 번 호출
• Mutex와 ww_acquire_ctx에 서로 다른 ww_class 사용
• Deadlock을 일으킬 수 있는 일반 lockdep error
• 첫 ww_acquire_ctx에 ww_acquire_fini()를 호출하기 전에 두 번째 context를 ww_acquire_init()으로 초기화
• 일반적인 deadlock