Robust futex ABI

Task exit에서 보유 lock을 정리하는 ABI

Paul Jackson이 시작한 이 문서는 robust futex ABI를 설명한다. Robust futex는 일반 futex에 더해 task가 exit할 때 보유 중인 lock을 kernel이 정리하도록 돕는다.

Thread가 보유한 futex 정보는 userspace linked list에 둔다. Lock을 획득하고 해제할 때 system call 없이 효율적으로 갱신할 수 있다. 일반 futex에 비해 필요한 추가 kernel 개입은 thread마다 한 번 robust futex list의 시작 주소를 알려 주는 일과 thread exit 때 list의 held lock을 처리하는 일뿐이다.

일반 futex도 경쟁 없는 lock은 system call 없이 처리하고 경쟁이 있으면 kernel에 waiter list를 두는 fast userspace locking을 제공한다. sys_futex(2) option은 특정 futex에서 기다리고 다음 waiter를 깨우는 동작을 제공한다.

Robust futex가 동작하려면 glibc 같은 userspace library가 kernel이 기대하는 정확한 layout과 순서로 list element를 관리해야 한다. 잘못 등록된 lock은 exit 때 정리되지 않아 같은 lock을 기다리는 thread의 deadlock이나 다른 failure를 일으킬 수 있다.

sys_set_robust_list()와 32/64-bit list

asmlinkage long
sys_set_robust_list(struct robust_list_head __user *head, size_t len);

Robust futex를 사용할 가능성이 있는 thread는 먼저 이 system call을 호출한다. head는 thread address space 안의 세 word 구조체를 가리킨다. Word는 32-bit architecture에서 32 bit, 64-bit architecture에서 64 bit이고 native byte order를 사용한다. Thread마다 private head가 있어야 한다.

64-bit native kernel에서 32-bit compatibility mode로 실행되는 thread는 32-bit compat list와 64-bit native list를 각각 가질 수 있다. 64-bit kernel이 compat mode를 지원하고 각 list에 대해 sys_set_robust_list()가 호출되었다면 task exit 때 두 list를 모두 처리한다.

robust_list_head의 세 word

Lock entry와 lock word

Head에서 시작하는 single linked list의 각 lock entry는 다음 lock entry 또는 끝에서 head를 가리키는 한 word로 이루어진다. 각 entry의 offset 위치에는 하나의 lock word가 있다.

Lock word는 항상 32 bit이며 일반 futex mechanism에서 쓰는 lock variable과 같은 word다. Exit 때 kernel이 다음 waiter를 깨우려면 그 waiter가 futex mechanism을 사용해 lock word 주소를 kernel에 등록해 두었어야 한다.

Thread가 현재 보유한 futex lock 중 exit cleanup을 원하는 lock마다 list에 lock entry 하나를 둔다. Thread가 lock을 보유한 채 죽으면 kernel이 list를 순회해 owner가 죽었다는 bit를 lock word에 표시하고 futex mechanism으로 다음 waiter를 깨운다.

등록한 head 조회와 embedded lock

asmlinkage long
sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
                    size_t __user *len_ptr);

Kernel은 sys_set_robust_list()로 받은 head pointer를 task에 저장하고 sys_get_robust_list()로 다시 조회할 수 있게 한다.

일반적으로 robust futex는 lock마다 하나인 더 큰 userspace locking structure 안에 embedded된다. 같은 thread가 사용하는 모든 robust futex에서 lock word의 offset만 같다면 kernel은 structure의 나머지 field에 관여하지 않는다. Kernel이 쓰는 single linked list 외에 userspace가 reverse link 같은 별도 link를 추가해도 무방하다.

Kernel이 아는 head에서 현재 held lock을 연결해 두면 예상하지 못한 exit가 일어날 때 kernel이 lock 정리를 도울 수 있다.

정상 동작 중 kernel의 최소 개입

정상적인 lock과 unlock은 경쟁 thread의 userspace code와 기존 futex wait/wakeup mechanism이 전부 처리한다. Robust futex에서 kernel의 필수 역할은 list head를 기억하고 thread exit 때 list를 순회해 아직 보유 중인 lock을 처리하는 것이다.

Thread가 공유 memory에 수천 개의 futex lock structure를 볼 수 있어도 특정 시점에 그 thread가 실제로 보유한 lock만 robust list에 있어야 한다. 공유 영역의 같은 lock은 시간에 따라 다른 thread가 보유할 수 있고 현재 owner TID는 lock word 하위 30 bit에 기록된다.

List insert와 remove protocol

Signal 9처럼 list 조작 중 예기치 않게 task가 exit하더라도 kernel이 정리할 수 있도록 userspace는 다음 순서를 지켜야 한다.

Exit scan과 lock word flag

Exit 때 kernel은 list_op_pending에 저장된 주소와 head list를 순회해 찾은 각 lock word 주소를 조사한다. 각 주소에서 offset만큼 떨어진 lock word의 하위 30 bit가 exiting thread의 TID와 같으면 두 작업을 수행한다.

• Bit 31, 즉 0x80000000이 설정되어 있으면 해당 주소에 futex wakeup을 시도해 futex wait 중인 다음 thread를 깨운다.
• Lock word의 bit 30, 즉 0x40000000을 atomic하게 설정한다.

Bit 31은 waiter가 자신이 기다리고 있음을 표시하는 bit이고, bit 30은 kernel이 lock owner가 lock을 보유한 채 죽었다고 표시하는 bit다.

Kernel이 list scan을 중단하는 조건

• head pointer 또는 뒤따르는 linked-list pointer가 유효한 userspace word 주소가 아니다.
• entry 주소에 offset을 적용해 계산한 lock word 위치가 유효한 32-bit userspace word 주소가 아니다.
• List element가 100만 개를 넘는다. 이 제한은 향후 kernel configuration에 따라 바뀔 수 있다.

List entry의 lock word 하위 30 bit가 current exiting thread의 TID와 다르면 kernel은 그 entry를 변경하지 않고 다음 entry로 진행한다.