Futex (Fast Userspace Mutex)

Futex(Fast Userspace Mutex)는 리눅스 커널이 제공하는 사용자 공간(User Space) 동기화 프리미티브의 핵심 빌딩 블록입니다. 경합(Contention)이 없는 경우(uncontended path) 커널 진입 없이 원자적 연산(Atomic Operation)만으로 잠금(Lock)을 획득/해제하고, 경합이 발생하면(contended path) futex(2) 시스템 콜(System Call)을 통해 커널의 대기 큐(Wait Queue)에서 효율적으로 슬립(Sleep)/웨이크업합니다. 이 문서에서는 kernel/futex/ 디렉터리의 내부 구현, 해시 테이블(Hash Table)과 futex_q 대기 큐, PI(Priority Inheritance) Futex, Robust Futex, FUTEX_WAIT_BITSET, FUTEX_CMP_REQUEUE, NUMA 최적화, futex2/futex_waitv(Linux 5.16+), glibc pthread 매핑(Mapping), Lock Elision, 성능 특성, 디버깅(Debugging), 보안 고려사항, 아키텍처별 차이, PREEMPT_RT 상호작용까지 종합적으로 다룹니다.

/* include/uapi/linux/futex.h — 사용자 공간 인터페이스 정의 */
#define FUTEX_WAIT              0
#define FUTEX_WAKE              1
#define FUTEX_FD                2
#define FUTEX_REQUEUE           3
#define FUTEX_CMP_REQUEUE       4
#define FUTEX_WAKE_OP           5
#define FUTEX_LOCK_PI           6
#define FUTEX_UNLOCK_PI         7
#define FUTEX_TRYLOCK_PI        8
#define FUTEX_WAIT_BITSET       9
#define FUTEX_WAKE_BITSET       10
#define FUTEX_WAIT_REQUEUE_PI   11
#define FUTEX_CMP_REQUEUE_PI    12
#define FUTEX_LOCK_PI2          13

#define FUTEX_PRIVATE_FLAG      128
#define FUTEX_CLOCK_REALTIME    256
#define FUTEX_CMD_MASK          ~(FUTEX_PRIVATE_FLAG | FUTEX_CLOCK_REALTIME)

/* 편의 매크로 */
#define FUTEX_WAIT_PRIVATE      (FUTEX_WAIT | FUTEX_PRIVATE_FLAG)
#define FUTEX_WAKE_PRIVATE      (FUTEX_WAKE | FUTEX_PRIVATE_FLAG)

# futex 시스템 콜 추적
$ strace -e futex -p $(pidof my_threaded_app)
futex(0x7f1234567890, FUTEX_WAIT_PRIVATE, 0, NULL) = 0
futex(0x7f1234567890, FUTEX_WAKE_PRIVATE, 1) = 1

# glibc pthread_mutex_lock이 futex를 호출하는지 확인
$ strace -e futex ./mutex_contention_test
futex(0x55a8b234c040, FUTEX_WAIT_BITSET_PRIVATE|FUTEX_CLOCK_REALTIME, 2, NULL, FUTEX_BITSET_MATCH_ANY) = 0
futex(0x55a8b234c040, FUTEX_WAKE_PRIVATE, 1) = 1

단계별 이해: Futex 잠금/해제 흐름

단계 1: 잠금 획득 시도 (Fast Path — 사용자 공간)

스레드 A가 잠금을 획득하려 합니다. futex word의 현재 값이 0(잠금 해제 상태)이면, cmpxchg(&futex_word, 0, tid)를 실행하여 원자적으로 자신의 TID를 기록합니다. 이 과정은 사용자 공간에서 단일 원자적 명령어로 완료되며, 시스템 콜이 필요 없습니다.

/* glibc nptl/lowlevellock.h — 간소화 */
static inline void
__lll_lock(int *futex, int private)
{
    /* Fast path: 0 → 1 (잠금 획득) */
    if (atomic_compare_exchange_weak_acquire(futex, 0, 1))
        return;  /* 성공! 커널 진입 없이 완료 */

    /* Slow path: 이미 잠겨 있으므로 커널에 도움 요청 */
    __lll_lock_wait(futex, private);
}

단계 2: 경합 발생 (Slow Path — 커널 진입)

스레드 B가 같은 잠금을 획득하려 하지만, futex word가 이미 0이 아닙니다. cmpxchg가 실패하면 futex word를 2(대기자 있음)로 설정하고 futex(FUTEX_WAIT, &futex_word, 2, ...) 시스템 콜을 호출합니다.

단계 3: 커널 해시 조회 및 대기 큐 삽입

커널은 futex word의 가상 주소(프라이빗) 또는 물리 페이지(Page)+오프셋(공유)으로 futex_key를 생성합니다. 이 키를 해시하여 futex_hash_bucket을 찾고, futex_q 노드를 생성하여 버킷의 plist에 삽입합니다. 그런 다음 태스크를 TASK_INTERRUPTIBLE로 설정하고 schedule()을 호출합니다.

단계 4: 잠금 해제 (Fast Path — 사용자 공간)

스레드 A가 잠금을 해제합니다. futex word를 atomic_exchange(&futex_word, 0)으로 0으로 설정합니다. 이전 값이 1이었다면(대기자 없음) 커널 진입 없이 완료됩니다. 이전 값이 2이었다면(대기자 있음) futex(FUTEX_WAKE, &futex_word, 1)을 호출합니다.

단계 5: 웨이크업

커널은 해시 버킷에서 해당 futex_key와 일치하는 futex_q를 찾아 대기 중인 태스크를 wake_up_state()으로 깨웁니다. 깨어난 스레드 B는 다시 잠금 획득을 시도합니다.

단계 6: 깨어난 태스크의 잠금 재시도

스레드 B가 깨어나 다시 cmpxchg(&futex_word, 0, 2)를 시도합니다. 성공하면 잠금을 획득하고, 실패하면(다른 스레드가 먼저 획득) 다시 FUTEX_WAIT로 슬립합니다.

Futex 개요와 역사

Futex는 2002년 Hubertus Franke, Matthew Kirkwood, Ingo Molnar, Rusty Russell에 의해 Linux 2.5.7에 도입되었습니다. 그 이전의 리눅스에서 사용자 공간 동기화는 System V 세마포어(semget/semop)나 파일 잠금(flock)에 의존했으며, 이들은 경합 여부와 무관하게 항상 시스템 콜을 요구했습니다.

Futex 이전의 동기화

커널 소스 구조 변천

초기에는 kernel/futex.c 단일 파일(약 4,000줄)에 모든 구현이 있었지만, Linux 5.17에서 Peter Zijlstra에 의해 kernel/futex/ 디렉터리로 분리되었습니다.

주요 마일스톤

Linux 2.5.7 ~ 6.x Futex 변경 상세 타임라인

Futex는 2002년 도입 이후 20년 넘게 지속적으로 진화해왔습니다. 각 커널 버전에서 추가된 기능, 수정된 버그, 성능 개선 사항을 상세히 살펴봅니다.

설계 철학: Fast Path vs Slow Path 분리 원칙

Futex의 설계 철학은 "일반적인 경우(common case)를 극한으로 최적화"하는 것입니다. 이 원칙은 세 가지 핵심 관찰에 기반합니다:

/* Futex 설계의 핵심: 3-level 잠금 전략 */

/* Level 1: Fast Path (사용자 공간, ~10ns) */
/* 조건: futex_word == 0 (잠금 해제 상태) */
if (cmpxchg(&futex_word, 0, 1) == 0)
    return; /* 성공! syscall 불필요 */

/* Level 2: Medium Path (사용자 공간, ~20-50ns) */
/* 조건: 잠금 보유자가 곧 해제할 것으로 예상 (adaptive spin) */
for (int i = 0; i < SPIN_COUNT; i++) {
    if (futex_word == 0 && cmpxchg(&futex_word, 0, 2) == 0)
        return;
    cpu_relax(); /* PAUSE 명령 */
}

/* Level 3: Slow Path (커널 진입, ~1000-5000ns) */
/* 조건: 경합이 지속됨 — 스케줄러에 양보 */
futex_word = 2; /* 대기자 있음 표시 */
syscall(SYS_futex, &futex_word, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);

Futex와 System V 세마포어 내부 비교

Futex가 System V 세마포어를 어떻게 대체했는지 내부 구현 수준에서 비교합니다.

/* System V 세마포어: 항상 커널 진입 */
/* ipc/sem.c — semop() 호출 경로 */
/* 1. sys_semop() → sys_semtimedop()
 * 2. sem_lock() — 전역 세마포어 배열 잠금
 * 3. perform_atomic_semop() — 세마포어 값 변경
 * 4. 실패 시 sem_queue에 삽입 → schedule()
 * 5. 성공해도 최소 1 syscall 오버헤드 (항상)
 *
 * 비용: 비경합 시에도 ~500-2000ns (syscall + 커널 잠금)
 */

/* Futex: 비경합 시 커널 미진입 */
/* kernel/futex/waitwake.c — futex_wait() 호출 경로
 * 비경합: cmpxchg 1회 (~10ns) → 끝
 * 경합: sys_futex() → get_futex_key() → futex_q_lock()
 *       → get_futex_value_locked() → schedule()
 *
 * 비용: 비경합 ~10ns, 경합 ~1000-5000ns
 */

시스템 콜 인터페이스

Futex 시스템 콜의 원형은 다음과 같습니다. 단일 futex(2) 시스템 콜이 op 매개변수에 따라 다양한 연산을 다중화(multiplexing)합니다.

/* man 2 futex — 시스템 콜 원형 */
#include <linux/futex.h>
#include <sys/syscall.h>

long syscall(SYS_futex,
    uint32_t *uaddr,          /* futex word 주소 */
    int       futex_op,       /* 연산 | 플래그 */
    uint32_t  val,            /* 의미는 op에 따라 다름 */
    const struct timespec *timeout,  /* 또는 val2 (requeue 시) */
    uint32_t *uaddr2,        /* requeue/wake_op 시 두 번째 futex */
    uint32_t  val3            /* bitset 또는 비교 값 */
);

FUTEX_WAIT 상세

FUTEX_WAIT는 futex의 가장 기본 대기 연산입니다. *uaddr == val이면 슬립하고, 아니면 즉시 -EAGAIN을 반환합니다. 이 “비교 후 슬립”은 커널 내부에서 원자적으로 수행되어 wakeup lost 문제를 방지합니다.

/* kernel/futex/waitwake.c — FUTEX_WAIT 핵심 로직 (간소화) */
static int futex_wait(u32 __user *uaddr, unsigned int flags,
                      u32 val, ktime_t *abs_time, u32 bitset)
{
    struct futex_hash_bucket *hb;
    struct futex_q q = futex_q_init;
    int ret;

    /* 1. futex_key 생성 (주소 → 키) */
    ret = get_futex_key(uaddr, flags, &q.key, FUTEX_READ);
    if (ret)
        return ret;

retry:
    /* 2. 해시 버킷 조회 및 잠금 */
    hb = futex_q_lock(&q);

    /* 3. 사용자 공간 값 읽기 (원자적으로 비교) */
    ret = get_futex_value_locked(&uval, uaddr);
    if (uval != val) {
        futex_q_unlock(hb);
        return -EAGAIN;  /* 값이 변경됨: spurious wakeup 방지 */
    }

    /* 4. 대기 큐에 삽입 */
    futex_wait_queue(hb, &q);

    /* 5. 슬립 (schedule) */
    if (!signal_pending(current)) {
        /* 타임아웃 설정 후 스케줄러로 전환 */
        freezable_schedule();
    }

    /* 6. 깨어남 — 결과 반환 */
    return ret;
}

FUTEX_WAKE 상세

/* kernel/futex/waitwake.c — FUTEX_WAKE 핵심 로직 (간소화) */
static int futex_wake(u32 __user *uaddr, unsigned int flags,
                      int nr_wake, u32 bitset)
{
    struct futex_hash_bucket *hb;
    struct futex_q *this, *next;
    union futex_key key;
    int ret;

    /* 1. futex_key 생성 */
    ret = get_futex_key(uaddr, flags, &key, FUTEX_READ);

    /* 2. 해시 버킷 조회 및 잠금 */
    hb = futex_hash(&key);
    spin_lock(&hb->lock);

    /* 3. 대기자 순회하며 깨움 */
    plist_for_each_entry_safe(this, next, &hb->chain, list) {
        if (futex_match(&this->key, &key)) {
            if (!(this->bitset & bitset))
                continue;

            futex_wake_mark(&wake_q, this);

            if (++ret >= nr_wake)
                break;
        }
    }

    spin_unlock(&hb->lock);
    wake_up_q(&wake_q);
    return ret;  /* 깨운 태스크 수 반환 */
}

FUTEX_WAKE_OP: 원자적 연산과 조건부 깨움

FUTEX_WAKE_OP는 glibc의 pthread_cond_signal() 구현에서 사용됩니다. 두 개의 futex(조건 변수의 대기 큐와 뮤텍스(Mutex))를 하나의 시스템 콜로 처리하여 성능을 최적화합니다.

/* FUTEX_WAKE_OP의 동작:
 * 1. *uaddr2에 원자적 연산 수행 (op 인코딩에 따라)
 * 2. uaddr에서 nr_wake개 깨움
 * 3. 연산 결과가 조건을 만족하면 uaddr2에서 nr_wake2개 추가 깨움
 *
 * 인코딩: val3 = (op << 28) | (cmp << 24) | (oparg << 12) | cmparg
 */
#define FUTEX_OP_SET   0  /* *uaddr2 = oparg */
#define FUTEX_OP_ADD   1  /* *uaddr2 += oparg */
#define FUTEX_OP_OR    2  /* *uaddr2 |= oparg */
#define FUTEX_OP_ANDN  3  /* *uaddr2 &= ~oparg */
#define FUTEX_OP_XOR   4  /* *uaddr2 ^= oparg */

#define FUTEX_OP_CMP_EQ  0  /* oldval == cmparg */
#define FUTEX_OP_CMP_NE  1  /* oldval != cmparg */
#define FUTEX_OP_CMP_LT  2  /* oldval < cmparg */
#define FUTEX_OP_CMP_LE  3  /* oldval <= cmparg */
#define FUTEX_OP_CMP_GT  4  /* oldval > cmparg */
#define FUTEX_OP_CMP_GE  5  /* oldval >= cmparg */

FUTEX_WAIT 상세 흐름 (커널 코드 레벨)

FUTEX_WAIT는 단순해 보이지만 내부적으로 여러 복잡한 경로를 처리합니다. 페이지 폴트(Page Fault) 재시도, 시그널(Signal) 처리, 타임아웃, spurious wakeup 등을 모두 고려해야 합니다.

/* kernel/futex/waitwake.c — FUTEX_WAIT 전체 경로 (상세) */
static int futex_wait(u32 __user *uaddr, unsigned int flags,
                      u32 val, ktime_t *abs_time, u32 bitset)
{
    struct hrtimer_sleeper timeout, *to;
    struct futex_hash_bucket *hb;
    struct futex_q q = futex_q_init;
    int ret;

    if (!bitset)
        return -EINVAL;  /* bitset=0은 유효하지 않음 */

    q.bitset = bitset;

    /* 타임아웃 설정 */
    to = futex_setup_timer(abs_time, &timeout, flags, 0);

retry:
    /* 1. futex_key 생성 (프라이빗/공유 분기) */
    ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key,
                        FUTEX_READ);
    if (unlikely(ret != 0))
        goto out;

retry_private:
    /* 2. 해시 버킷 조회 + spinlock 획득 */
    hb = futex_q_lock(&q);

    /* 3. 사용자 공간 값 읽기 (spinlock 보유 상태) */
    ret = get_futex_value_locked(&uval, uaddr);
    if (ret) {
        /* 페이지 폴트! spinlock 해제 후 fault-in */
        futex_q_unlock(hb);
        ret = get_user(uval, uaddr);  /* 페이지 fault-in */
        if (ret)
            goto out;  /* EFAULT: 잘못된 주소 */

        /* 공유 futex: 페이지가 바뀌었을 수 있으므로 키 재생성 */
        if (!(flags & FLAGS_SHARED))
            goto retry_private;
        goto retry;
    }

    /* 4. 값 비교: 변경되었으면 즉시 반환 */
    if (uval != val) {
        futex_q_unlock(hb);
        ret = -EAGAIN;  /* 값이 이미 변경됨 */
        goto out;
    }

    /* 5. 대기 큐에 삽입 + schedule() */
    futex_wait_queue(hb, &q, to);

    /* 6. 깨어남 — 이유 분석 */
    ret = 0;
    if (!unqueue_me(&q))
        goto out;  /* 정상 wakeup */
    ret = -ETIMEDOUT;
    if (to && !to->task)
        goto out;  /* 타임아웃 */
    if (signal_pending(current)) {
        ret = -ERESTARTSYS;  /* 시그널 수신 */
        if (abs_time)
            ret = -ERESTARTNOHAND;
    }

out:
    if (to)
        hrtimer_cancel(&to->timer);
    return ret;
}

FUTEX_WAKE 상세 흐름

FUTEX_WAKE의 핵심은 해시 버킷에서 일치하는 대기자를 찾아 깨우는 것입니다. wake_q 메커니즘을 사용하여 spinlock 해제 후에 실제 wakeup을 수행합니다.

/* wake_q: spinlock 밖에서 wakeup 수행하는 메커니즘 */
/* 왜 필요한가?
 * - wake_up_state()는 스케줄러 잠금을 획득할 수 있음
 * - 해시 버킷 spinlock을 보유한 상태에서 스케줄러 잠금을 획득하면
 *   잠금 순서 위반(lock ordering violation) → 교착 가능
 * - 해결: wake_q에 태스크를 등록 후, spinlock 해제 후에 깨움 */

struct wake_q_head {
    struct wake_q_node *first;
    struct wake_q_node **lastp;
};

/* futex_wake 전체 흐름:
 * 1. spin_lock(&hb->lock)
 * 2. plist 순회 → 매칭 대기자 찾기
 * 3. wake_q_add(&wake_q, task)  // 등록만
 * 4. spin_unlock(&hb->lock)
 * 5. wake_up_q(&wake_q)         // 실제 wakeup
 */

FUTEX_FD (deprecated) 역사와 제거 이유

FUTEX_FD(op=2)는 futex word에 파일 디스크립터를 연결하여 poll()/select()/epoll로 futex 이벤트를 대기할 수 있게 했습니다. 그러나 심각한 설계 결함과 보안 문제로 Linux 2.6.26에서 제거되었습니다.

/* FUTEX_FD가 제거된 후의 대안 패턴 */
/* 1. futex + eventfd 조합: */
int efd = eventfd(0, EFD_NONBLOCK);
/* 스레드 A: futex 조건 충족 시 eventfd에 알림 */
uint64_t val = 1;
write(efd, &val, sizeof(val));
/* 스레드 B: epoll로 eventfd 대기 */
epoll_wait(epollfd, events, 1, -1);

/* 2. futex_waitv (Linux 5.16+): 다중 futex 동시 대기의 현대적 해법 */
struct futex_waitv waiters[4];
/* ... 설정 ... */
syscall(SYS_futex_waitv, waiters, 4, 0, timeout, CLOCK_MONOTONIC);

FUTEX_LOCK_PI / FUTEX_UNLOCK_PI 상세

PI futex의 시스템 콜 인터페이스는 일반 futex와 다른 의미론을 가집니다. futex word 자체에 소유자의 TID가 기록되며, 커널이 소유권을 추적합니다.

/* FUTEX_LOCK_PI 사용법 */
/* futex_word 초기값: 0 (잠금 해제)
 * 잠금 후: current_tid (소유자 TID)
 * 대기자 있을 때: current_tid | FUTEX_WAITERS
 *
 * 사용자 공간에서의 전형적 패턴: */
uint32_t futex_word = 0;
uint32_t tid = gettid();

/* 잠금 획득 */
uint32_t expected = 0;
if (cmpxchg(&futex_word, expected, tid) != 0) {
    /* Fast path 실패: 커널에 PI 잠금 요청 */
    syscall(SYS_futex, &futex_word,
            FUTEX_LOCK_PI | FUTEX_PRIVATE_FLAG,
            0, NULL, NULL, 0);
    /* 커널이 futex_word에 우리 TID를 기록해줌 */
}

/* 잠금 해제 */
uint32_t prev = cmpxchg(&futex_word, tid, 0);
if (prev != tid) {
    /* FUTEX_WAITERS 비트가 설정되어 있음: 커널에 해제 요청 */
    syscall(SYS_futex, &futex_word,
            FUTEX_UNLOCK_PI | FUTEX_PRIVATE_FLAG,
            0, NULL, NULL, 0);
    /* 커널이 다음 대기자에게 소유권 전달 */
}

/* FUTEX_LOCK_PI2 (Linux 5.14+): CLOCK_MONOTONIC 타임아웃 지원 */
struct timespec timeout = { .tv_sec = 5, .tv_nsec = 0 };
syscall(SYS_futex, &futex_word,
        FUTEX_LOCK_PI2 | FUTEX_PRIVATE_FLAG,
        0, &timeout, NULL, 0);
/* FUTEX_LOCK_PI는 CLOCK_REALTIME만 사용하므로
 * 시스템 시간 변경에 영향을 받음.
 * FUTEX_LOCK_PI2는 CLOCK_MONOTONIC으로 안정적 타임아웃 */

내부 구현: 해시 테이블과 대기 큐

futex_key: 주소 식별

futex_key는 futex word를 고유하게 식별하는 3-워드 구조체입니다. 동일한 물리 메모리(Physical Memory)를 가리키는 서로 다른 가상 주소가 같은 키로 매핑되어야 프로세스 간 공유 futex가 올바르게 동작합니다.

/* kernel/futex/futex.h */
union futex_key {
    struct {
        u64 i_seq;        /* inode sequence number */
        unsigned long pgoff;  /* 페이지 오프셋 */
        unsigned int offset;  /* 페이지 내 바이트 오프셋 */
    } shared;               /* 공유 futex: mmap, shm, 파일 매핑 */

    struct {
        union {
            struct mm_struct *mm;
            u64 __tmp;
        };
        unsigned long address;  /* 가상 주소 */
        unsigned int offset;    /* 항상 0 */
    } private;                /* 프라이빗 futex: 프로세스/스레드 내부 */

    struct {
        u64 ptr;
        unsigned long word;
        unsigned int offset;
    } both;                   /* 해시 계산용 통합 뷰 */
};

get_futex_key(): 프라이빗 vs 공유

/* kernel/futex/core.c — get_futex_key() 핵심 로직 (간소화) */
int get_futex_key(u32 __user *uaddr, unsigned int flags,
                  union futex_key *key, enum futex_access rw)
{
    unsigned long address = (unsigned long)uaddr;
    struct mm_struct *mm = current->mm;

    key->both.offset = address % PAGE_SIZE;

    if (flags & FLAGS_SHARED) {
        /* 공유 futex: 물리 페이지 기반 식별 필요 */
        struct page *page;
        struct vm_area_struct *vma;

        /* GUP: 페이지 조회 (비용 높음) */
        ret = get_user_pages_fast(address, 1, 0, &page);

        if (PageAnon(page)) {
            /* 익명 매핑: mm + address */
            key->private.mm = mm;
            key->private.address = address;
        } else {
            /* 파일 매핑: inode + page offset */
            struct inode *inode = vma->vm_file->f_mapping->host;
            key->shared.i_seq = get_inode_sequence_number(inode);
            key->shared.pgoff = page_to_pgoff(page);
        }
    } else {
        /* 프라이빗 futex: 가상 주소만으로 충분 (빠름!) */
        key->private.mm = mm;
        key->private.address = address;
    }
    return 0;
}

해시 테이블 크기 결정

futex 해시 테이블은 부팅 시 할당되며, CPU 수에 비례하여 크기가 결정됩니다. 해시 충돌은 futex 성능의 주요 병목(Bottleneck)이 될 수 있으므로, 적절한 크기가 중요합니다.

/* kernel/futex/core.c — 해시 테이블 초기화 */
static int __init futex_init(void)
{
    unsigned long hashsize;

    /* CPU 수에 비례하여 해시 크기 결정 */
    hashsize = 256 * num_possible_cpus();
    hashsize = roundup_pow_of_two(hashsize);

    /* 최소 16, 최대 2^21 */
    if (hashsize < 16)
        hashsize = 16;

    futex_queues = alloc_large_system_hash("futex",
        sizeof(struct futex_hash_bucket),
        hashsize, 0, 0, &futex_shift, NULL,
        hashsize, hashsize);

    for (i = 0; i < hashsize; i++) {
        atomic_set(&futex_queues[i].waiters, 0);
        plist_head_init(&futex_queues[i].chain);
        spin_lock_init(&futex_queues[i].lock);
    }
    return 0;
}

futex_q 구조체

/* kernel/futex/futex.h */
struct futex_q {
    struct plist_node list;      /* 해시 버킷 체인의 노드 */
    struct task_struct *task;    /* 대기 중인 태스크 */
    spinlock_t *lock_ptr;        /* 해시 버킷의 spinlock 포인터 */
    union futex_key key;         /* futex 식별 키 */
    struct futex_pi_state *pi_state;  /* PI futex 상태 */
    struct rt_mutex_waiter *rt_waiter; /* PI: rt_mutex 대기자 */
    union futex_key *requeue_pi_key;  /* PI requeue 키 */
    u32 bitset;                  /* WAIT_BITSET/WAKE_BITSET 마스크 */
    atomic_t requeue_state;      /* requeue 상태 추적 */
};

해시 버킷 내부 구조 상세

futex_hash_bucket은 futex 시스템의 핵심 자료 구조입니다. 각 버킷은 spinlock으로 보호되며, 우선순위 정렬 리스트(plist)로 대기자를 관리합니다.

/* kernel/futex/futex.h — futex_hash_bucket 상세 */
struct futex_hash_bucket {
    atomic_t waiters;       /* 이 버킷의 대기자 수 (최적화용) */
    spinlock_t lock;        /* 버킷 보호 spinlock */
    struct plist_head chain; /* 우선순위 정렬 대기 큐 */
} ____cacheline_aligned_in_smp;

/* ____cacheline_aligned_in_smp:
 * 각 버킷이 별도의 캐시라인에 위치하도록 정렬.
 * SMP 시스템에서 서로 다른 버킷의 spinlock이
 * 같은 캐시라인을 공유하면 false sharing으로 성능 저하.
 * sizeof(futex_hash_bucket) ≈ 32~48 bytes
 * 패딩으로 64 bytes (L1 캐시라인) 정렬 */

/* plist (Priority List):
 * - 일반 list_head와 달리 우선순위로 정렬된 이중 연결 리스트
 * - PI futex에서 가장 높은 우선순위 대기자를 O(1)에 찾기 위함
 * - SCHED_FIFO/SCHED_RR 태스크가 먼저 깨어남
 * - 같은 우선순위 내에서는 FIFO 순서 */

futex_key 구조 상세: 프라이빗 vs 공유 식별

futex_key의 핵심 과제는 "동일한 futex word를 가리키는 서로 다른 가상 주소가 같은 키로 매핑되어야 한다"는 것입니다. 이를 위해 공유 futex는 물리 페이지 기반으로 식별합니다.

/* futex_key 비교: futex_match() */
static inline int futex_match(union futex_key *key1,
                               union futex_key *key2)
{
    return (key1->both.ptr == key2->both.ptr &&
            key1->both.word == key2->both.word &&
            key1->both.offset == key2->both.offset);
}
/* 3개 필드 모두 일치해야 같은 futex
 * → 해시 충돌이 있어도 정확한 매칭 보장 */

/* 공유 futex 시나리오:
 * Process A: mmap(NULL, 4096, PROT_READ|PROT_WRITE,
 *                  MAP_SHARED, shm_fd, 0) → addr_A = 0x7f0000
 * Process B: mmap(NULL, 4096, PROT_READ|PROT_WRITE,
 *                  MAP_SHARED, shm_fd, 0) → addr_B = 0x7f8000
 *
 * addr_A != addr_B (다른 가상 주소)
 * 하지만 같은 물리 페이지를 가리킴
 * → futex_key.shared = {inode_seq, pgoff, offset}
 * → 같은 key → 같은 해시 버킷 → 올바른 wakeup */

대기 큐 연산: enqueue / dequeue / unqueue

futex 대기 큐의 삽입/제거 연산은 해시 버킷의 spinlock으로 보호됩니다. 각 연산의 정확한 시점과 잠금 범위를 이해하는 것이 futex 코드 분석의 핵심입니다.

/* kernel/futex/core.c — 대기 큐 삽입 */
static inline void
futex_q_lock_and_enqueue(struct futex_q *q,
                          struct futex_hash_bucket *hb)
{
    /* spinlock 획득 */
    spin_lock(&hb->lock);

    /* 대기자 카운터 증가 (최적화: 빈 버킷 체크) */
    atomic_inc(&hb->waiters);

    /* plist에 삽입 (우선순위 순) */
    plist_node_init(&q->list, current->normal_prio);
    plist_add(&q->list, &hb->chain);

    q->lock_ptr = &hb->lock;

    /* spinlock 유지한 채 반환 → 값 비교 후 schedule() */
}

/* 대기 큐 제거 (wakeup 측) */
static inline void
futex_wake_mark(struct wake_q_head *wake_q,
                struct futex_q *q)
{
    /* plist에서 제거 */
    plist_del(&q->list, &hb->chain);

    /* 대기자 카운터 감소 */
    atomic_dec(&hb->waiters);

    /* wake_q에 등록 (spinlock 해제 후 깨움) */
    wake_q_add(wake_q, q->task);

    q->lock_ptr = NULL; /* unqueue_me() 방지 */
}

/* 자발적 제거 (타임아웃, 시그널) */
static int unqueue_me(struct futex_q *q)
{
    spinlock_t *lock_ptr;
    int ret = 0;

    lock_ptr = READ_ONCE(q->lock_ptr);
    if (!lock_ptr)
        return 1; /* 이미 wakeup 측에서 제거됨 */

    spin_lock(lock_ptr);
    if (q->lock_ptr != lock_ptr) {
        spin_unlock(lock_ptr);
        return 1; /* 동시에 wakeup됨 */
    }

    /* plist에서 자신을 제거 */
    plist_del(&q->list, &q->list.plist);
    atomic_dec(&hb->waiters);
    q->lock_ptr = NULL;

    spin_unlock(lock_ptr);
    return 0; /* 성공적으로 제거 */
}

get_futex_value_locked(): 페이지 폴트 처리

해시 버킷 spinlock을 보유한 상태에서 사용자 공간 메모리에 접근하는 것은 잠재적으로 위험합니다. 페이지가 스왑(Swap) 아웃되었으면 페이지 폴트가 발생하고, 페이지 폴트 핸들러(Handler)가 I/O 대기를 시도하면 sleep-in-atomic-context 버그가 됩니다.

/* futex의 "fault, retry" 패턴 상세 */
/* kernel/futex/waitwake.c */

retry:
    hb = futex_q_lock(&q); /* spinlock 획득 */

    /* pagefault_disable: 페이지 폴트 시 -EFAULT 반환 (sleep 불가) */
    ret = get_futex_value_locked(&uval, uaddr);

    if (ret) {
        /* 페이지 폴트 발생! */
        futex_q_unlock(hb); /* spinlock 해제 (중요!) */

        /* 이제 sleep 가능: 페이지를 fault-in */
        ret = get_user(uval, uaddr);
        /* get_user()는 필요시 I/O 대기 → 페이지 로드 */

        if (ret)
            return -EFAULT; /* 진짜 잘못된 주소 */

        /* 페이지가 로드됨: 처음부터 재시도 */
        /* 주의: 공유 futex는 키도 재생성해야 함
         * (페이지가 CoW되었을 수 있으므로) */
        if (shared)
            goto retry;     /* 키 재생성 포함 */
        else
            goto retry_private; /* 키 유지, spinlock만 재획득 */
    }

/* 이 패턴의 핵심:
 * 1. spinlock 보유 → 사용자 메모리 접근 시도
 * 2. 실패하면 spinlock 해제 → 안전하게 fault-in
 * 3. 전체 재시도 (값이 변경되었을 수 있으므로)
 *
 * 최악의 경우 2번 재시도 (스왑 페이지) 하지만
 * 대부분은 페이지가 메모리에 있으므로 0번 재시도 */

PI Futex (우선순위 상속(Priority Inheritance))

PI(Priority Inheritance) Futex는 우선순위 역전(Priority Inversion) 문제를 해결합니다. 저우선순위 태스크가 잠금을 보유하고, 고우선순위 태스크가 대기하며, 중간 우선순위 태스크가 저우선순위 태스크를 선점(Preemption)하는 상황을 방지합니다.

우선순위 역전 시나리오

우선순위 역전의 전형적인 3-task 시나리오(High/Mid/Low)와 PI 프로토콜의 해결 과정은 PREEMPT_RT: PI chain 문서에서 단계별로 상세히 설명합니다.

PI 프로토콜의 해결

PI Futex는 커널 내부의 rt_mutex와 연동하여 우선순위 상속 체인을 관리합니다. 고우선순위 태스크 H가 잠금을 요청하면, 잠금 보유자 L의 우선순위를 H 수준으로 일시적으로 상승시킵니다. 이로써 L이 중간 우선순위 태스크 M에 의해 선점되지 않습니다.

FUTEX_LOCK_PI / FUTEX_UNLOCK_PI 흐름

/* kernel/futex/pi.c — FUTEX_LOCK_PI 핵심 로직 (간소화) */
static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
                         ktime_t *time, int trylock)
{
    struct futex_hash_bucket *hb;
    struct futex_q q = futex_q_init;
    struct futex_pi_state *pi_state;
    u32 uval, curval;

    /* 1. Fast path: cmpxchg(uaddr, 0, current->pid) */
    if (cmpxchg_futex_value_locked(&curval, uaddr, 0,
                                    current->pid) == 0)
        return 0;  /* 경합 없이 획득! */

    /* 2. 해시 버킷 잠금 */
    hb = futex_q_lock(&q);

    /* 3. futex_pi_state 생성 또는 기존 것 참조 */
    ret = futex_lock_pi_atomic(uaddr, hb, &q.key, &ps,
                               current, &exiting, 0);

    /* 4. rt_mutex에서 대기 (우선순위 상속 발동) */
    ret = rt_mutex_futex_trylock(&q.pi_state->pi_mutex);
    if (!ret) {
        /* rt_mutex_slowlock → 우선순위 부스트 + 슬립 */
        ret = __rt_mutex_futex_lock(&q.pi_state->pi_mutex,
                                     &rt_waiter, timeout);
    }

    /* 5. 깨어남: futex word에 자신의 TID 기록 */
    if (!ret)
        futex_lock_pi_complete(uaddr, q.pi_state);

    return ret;
}

/* FUTEX_UNLOCK_PI */
static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
{
    u32 curval;

    /* 1. Fast path: 대기자 없으면 cmpxchg(uaddr, pid, 0) */
    if (cmpxchg_futex_value_locked(&curval, uaddr,
                                    current->pid, 0) == 0)
        return 0;

    /* 2. 대기자가 있으면 rt_mutex_unlock → 우선순위 복원 */
    /* 다음 대기자에게 소유권 전달 */
    rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
    wake_up_q(&wake_q);

    return 0;
}

futex_pi_state 구조체

/* kernel/futex/futex.h */
struct futex_pi_state {
    struct list_head list;        /* task->pi_state_list에 연결 */
    struct rt_mutex_base pi_mutex;  /* 실제 PI 잠금 */
    struct task_struct *owner;    /* 현재 소유자 */
    refcount_t refcount;          /* 참조 카운트 */
    union futex_key key;          /* futex 식별 키 */
};

PI 프로토콜 동작 상세: rt_mutex_waiter 연결

PI futex는 커널의 rt_mutex 인프라를 활용합니다. 사용자 공간의 PI futex 잠금 요청이 커널로 들어오면, futex_pi_state에 연결된 rt_mutex에서 대기합니다.

PI 프로토콜의 핵심 자료구조인 rt_mutex_waiter는 대기자의 우선순위, 대기 중인 잠금, 트리 노드 등을 관리합니다. 구조체 상세 필드는 PREEMPT_RT: RT Mutex 내부 구현을 참고하세요.

PI 체인 워킹 알고리즘 코드

rt_mutex_adjust_prio_chain()은 PI 체인을 따라 우선순위를 전파하는 핵심 함수입니다. 잠금 소유자를 찾아 우선순위를 부스트하고, 해당 소유자가 다른 잠금을 대기 중이면 체인을 따라 재귀적으로 전파합니다.

PI 데드락 감지

PI 체인 워킹 도중 순환이 감지되면 교착 상태입니다. 커널은 순환 감지(A→B→C→A)와 깊이 제한(max_lock_depth=1024) 두 가지 방법으로 데드락을 감지하며, 감지 시 -EDEADLK를 반환합니다.

Robust Futex (비정상 종료 대응)

일반 futex에서 잠금 보유자가 SIGKILL이나 비정상 종료로 잠금을 해제하지 못하면, 대기 중인 모든 스레드가 영원히 차단됩니다. Robust Futex는 이 문제를 해결합니다.

robust_list_head 메커니즘

각 스레드는 set_robust_list() 시스템 콜로 자신의 robust futex 리스트를 커널에 등록합니다. 스레드가 종료할 때 커널은 이 리스트를 순회하면서 보유 중인 futex를 정리합니다.

/* include/uapi/linux/futex.h */
struct robust_list {
    struct robust_list __user *next;  /* 다음 노드 */
};

struct robust_list_head {
    struct robust_list list;           /* 리스트 헤드 */
    long futex_offset;                 /* robust_list → futex word 오프셋 */
    struct robust_list __user *list_op_pending;  /* 진행 중인 잠금 연산 */
};

/* glibc nptl/pthread_mutex_lock.c — robust mutex 획득 (간소화) */
int __pthread_mutex_lock(pthread_mutex_t *mutex)
{
    /* 1. robust 리스트에 등록 */
    THREAD_SETMEM(THREAD_SELF, robust_head.list_op_pending,
                  &mutex->__data.__list.__next);

    /* 2. futex word에 TID 기록 */
    int newval = THREAD_GETMEM(THREAD_SELF, tid);
    oldval = atomic_compare_and_exchange_val_acq(
        &mutex->__data.__lock, newval, 0);

    if (oldval != 0) {
        /* 경합: FUTEX_LOCK_PI 또는 FUTEX_WAIT */
    }

    /* 3. robust 리스트에 연결 완료 */
    ENQUEUE_MUTEX(mutex);
    THREAD_SETMEM(THREAD_SELF, robust_head.list_op_pending, NULL);
    return 0;
}

커널의 종료 시 정리

/* kernel/futex/core.c — exit_robust_list() */
void exit_robust_list(struct task_struct *curr)
{
    struct robust_list_head __user *head;
    struct robust_list __user *entry, *next_entry;
    unsigned int limit = ROBUST_LIST_LIMIT; /* 2048개 제한 */

    if (get_user(entry, &head->list.next))
        return;

    /* robust 리스트 순회 */
    while (entry != (struct robust_list __user *)&head->list) {
        u32 __user *futex_addr;

        /* futex word 주소 계산: entry + futex_offset */
        futex_addr = (u32 __user *)((char *)entry + futex_offset);

        /* FUTEX_OWNER_DIED 비트 설정 + FUTEX_WAKE */
        handle_futex_death(futex_addr, curr);

        if (get_user(next_entry, &entry->next))
            break;
        entry = next_entry;

        if (!--limit)
            break;  /* 무한 루프 방지 */
    }

    /* list_op_pending 처리 (진행 중이던 잠금) */
    if (head->list_op_pending)
        handle_futex_death(pending_futex_addr, curr);
}

static int handle_futex_death(u32 __user *uaddr,
                               struct task_struct *curr)
{
    u32 uval, nval;

    /* futex word에 FUTEX_OWNER_DIED (bit 30) 설정 */
    do {
        get_user(uval, uaddr);
        if ((uval & FUTEX_TID_MASK) != task_pid_vnr(curr))
            return 0;  /* 소유자가 아님 */

        nval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
    } while (cmpxchg_futex_value_locked(&nval, uaddr, uval, nval));

    /* 대기자 깨움 */
    if (uval & FUTEX_WAITERS)
        futex_wake(uaddr, FLAGS_SIZE_32, 1, FUTEX_BITSET_MATCH_ANY);

    return 0;
}

robust_list 순회 알고리즘 상세

커널이 프로세스 종료 시 robust list를 순회하는 과정은 여러 edge case를 처리해야 합니다. 사용자 공간 메모리를 읽어야 하므로 페이지 폴트, 잘못된 포인터, 무한 루프 등에 대비합니다.

exit_robust_list() 보안 고려사항

exit_robust_list()는 사용자 공간의 리스트 포인터를 따라가므로, 악의적으로 조작된 robust list가 커널을 공격하는 벡터가 될 수 있습니다.

32비트 호환 Robust List

64비트 커널에서 32비트 프로세스가 실행될 때, robust list의 포인터 크기가 다릅니다. 커널은 compat_exit_robust_list()로 이를 처리합니다.

/* kernel/futex/core.c — 32비트 호환 처리 */
#ifdef CONFIG_COMPAT
void compat_exit_robust_list(struct task_struct *curr)
{
    struct compat_robust_list_head __user *head;
    /* compat_robust_list: 32비트 포인터 사용 */
    /* 로직은 exit_robust_list()와 동일하지만
     * compat_ptr()로 32비트→64비트 포인터 변환 */
}

/* set_robust_list / get_robust_list도 compat 버전 존재:
 * - COMPAT_SYSCALL_DEFINE2(set_robust_list, ...)
 * - COMPAT_SYSCALL_DEFINE3(get_robust_list, ...)
 * 32비트 프로세스에서 sizeof(robust_list_head)가 다르므로
 * len 매개변수로 크기 검증 */
#endif

FUTEX_WAIT_BITSET / FUTEX_WAKE_BITSET

FUTEX_WAIT_BITSET과 FUTEX_WAKE_BITSET은 32비트 비트 마스크를 사용하여 대기자를 선택적으로 분류하고 깨우는 기능을 제공합니다. glibc의 pthread_cond_wait()와 pthread_cond_signal()/pthread_cond_broadcast() 구현에서 핵심적으로 사용됩니다.

동작 원리

/* FUTEX_WAIT_BITSET: val3에 비트 마스크 전달 */
syscall(SYS_futex, uaddr, FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG,
        expected_val, timeout, NULL, bitset_mask);

/* FUTEX_WAKE_BITSET: val3에 비트 마스크 전달 */
syscall(SYS_futex, uaddr, FUTEX_WAKE_BITSET | FUTEX_PRIVATE_FLAG,
        nr_wake, NULL, NULL, bitset_mask);

/* 웨이크업 조건: waiter.bitset & wake_bitset != 0
 * 즉, 비트가 하나라도 겹치면 깨움 */

/* FUTEX_BITSET_MATCH_ANY = 0xFFFFFFFF
 * → 모든 대기자를 깨움 (FUTEX_WAKE와 동일 효과) */

condvar에서의 활용 (glibc 2.34+)

glibc의 새로운 condvar 구현에서는 비트셋을 사용하여 pthread_cond_signal()(단일 깨움)과 pthread_cond_broadcast()(전체 깨움)을 효율적으로 구분합니다. 각 대기 그룹(generation)에 서로 다른 비트셋을 할당하여 정확한 타겟팅이 가능합니다.

BITSET을 활용한 condvar 그룹 관리

glibc 2.25+의 새로운 condvar 구현은 비트셋을 활용하여 대기자를 세대(generation)별로 분류합니다. 이를 통해 pthread_cond_signal()이 정확히 원하는 세대의 대기자만 깨울 수 있습니다.

/* glibc condvar의 비트셋 활용 상세 */
/* condvar 내부에 2개의 그룹(g1, g2)이 교대로 사용됨 */

/* 세대 0의 대기자: bitset = (1u << 0) = 0x00000001 */
/* 세대 1의 대기자: bitset = (1u << 16) = 0x00010000 */

/* pthread_cond_signal()에서:
 * 현재 활성 세대의 비트셋만 사용하여 FUTEX_WAKE_BITSET
 * → 다른 세대의 대기자는 영향 없음 */

/* 예시: 세대 0이 활성인 경우 */
futex_wake_bitset(&cond->g_signals[0],
                  1,           /* nr_wake = 1 */
                  0x00000001); /* 세대 0 비트셋 */

/* pthread_cond_broadcast()에서:
 * 세대 전환 + 해당 세대 전체 깨움 (FUTEX_CMP_REQUEUE 사용) */

/* 이 구현의 장점:
 * - signal/broadcast가 올바른 대기자에게만 도달
 * - 세대 전환으로 spurious wakeup 최소화
 * - WAIT_BITSET의 절대 타임아웃으로 시그널 재시도 불필요 */

BITSET의 다른 활용 사례

/* 비트셋을 활용한 다중 이벤트 타입 시스템 예시 */
#define EVENT_DATA_READY   (1u << 0)  /* 데이터 준비됨 */
#define EVENT_ERROR        (1u << 1)  /* 에러 발생 */
#define EVENT_SHUTDOWN     (1u << 2)  /* 종료 요청 */
#define EVENT_ALL          0xFFFFFFFF

/* 특정 이벤트만 대기 */
syscall(SYS_futex, &event_word, FUTEX_WAIT_BITSET_PRIVATE,
        0, &timeout, NULL, EVENT_DATA_READY | EVENT_ERROR);

/* 에러 이벤트 대기자만 깨움 */
event_word = 1;
syscall(SYS_futex, &event_word, FUTEX_WAKE_BITSET_PRIVATE,
        INT_MAX, NULL, NULL, EVENT_ERROR);

FUTEX_REQUEUE / FUTEX_CMP_REQUEUE

Requeue 연산은 thundering herd 문제를 해결하는 핵심 메커니즘입니다. 조건 변수에서 broadcast 시 모든 대기자를 깨우면, 깨어난 스레드들이 뮤텍스를 동시에 획득하려 하여 극심한 경합이 발생합니다. Requeue는 대기자를 깨우지 않고 다른 futex의 대기 큐로 직접 이동시켜 이 문제를 회피합니다.

Thundering Herd 시나리오

/* pthread_cond_broadcast() without requeue (비효율) */
/* 1. condvar에서 100개 스레드를 전부 FUTEX_WAKE
 * 2. 100개 스레드가 동시에 깨어남
 * 3. 100개 스레드가 동시에 mutex 획득 시도
 * 4. 1개만 성공, 99개는 다시 FUTEX_WAIT → 극심한 경합 */

/* pthread_cond_broadcast() with CMP_REQUEUE (효율적) */
/* 1. condvar에서 1개 WAKE + 99개를 mutex 대기 큐로 REQUEUE
 * 2. 1개 스레드만 깨어나 mutex 획득
 * 3. 해제 시 mutex 대기 큐에서 다음 1개 WAKE
 * 4. 순차적으로 처리: 99회의 불필요한 wake-sleep 사이클 제거 */

FUTEX_REQUEUE vs FUTEX_CMP_REQUEUE

FUTEX_REQUEUE는 값 비교 없이 requeue를 수행하므로 race condition이 존재합니다. FUTEX_CMP_REQUEUE는 *uaddr == val3을 먼저 확인하여 안전합니다. 현재 glibc는 FUTEX_CMP_REQUEUE만 사용합니다.

CMP_REQUEUE 커널 구현 상세

/* kernel/futex/requeue.c — futex_requeue() 핵심 (간소화) */
static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
    u32 __user *uaddr2, int nr_wake, int nr_requeue,
    u32 *cmpval, int requeue_pi)
{
    struct futex_hash_bucket *hb1, *hb2;
    union futex_key key1, key2;
    struct futex_q *this, *next;
    DEFINE_WAKE_Q(wake_q);
    int task_count = 0, ret;

    /* 1. 두 futex의 키 생성 */
    ret = get_futex_key(uaddr1, flags, &key1, FUTEX_READ);
    ret = get_futex_key(uaddr2, flags, &key2,
                        requeue_pi ? FUTEX_WRITE : FUTEX_READ);

    /* 2. 두 해시 버킷 잠금 (주소 순서로 교착 방지) */
    hb1 = futex_hash(&key1);
    hb2 = futex_hash(&key2);
    double_lock_hb(hb1, hb2);

    /* 3. 비교값 확인 (CMP_REQUEUE만) */
    if (cmpval) {
        u32 curval;
        ret = get_futex_value_locked(&curval, uaddr1);
        if (curval != *cmpval) {
            ret = -EAGAIN; /* 값이 변경됨: requeue 취소 */
            goto out;
        }
    }

    /* 4. uaddr1 대기 큐에서 처리 */
    plist_for_each_entry_safe(this, next, &hb1->chain, list) {
        if (!futex_match(&this->key, &key1))
            continue;

        if (task_count < nr_wake) {
            /* nr_wake개는 실제로 깨움 */
            futex_wake_mark(&wake_q, this);
            task_count++;
        } else if (task_count < nr_wake + nr_requeue) {
            /* 나머지는 uaddr2 대기 큐로 이동 */
            requeue_futex(this, hb1, hb2, &key2);
            task_count++;
        } else {
            break;
        }
    }

out:
    double_unlock_hb(hb1, hb2);
    wake_up_q(&wake_q);
    return ret;
}

/* requeue_futex: 대기자를 다른 해시 버킷으로 이동 */
static void requeue_futex(struct futex_q *q,
    struct futex_hash_bucket *hb1,
    struct futex_hash_bucket *hb2,
    union futex_key *key2)
{
    /* hb1에서 제거 */
    plist_del(&q->list, &hb1->chain);
    atomic_dec(&hb1->waiters);

    /* 키 변경 */
    q->key = *key2;

    /* hb2에 삽입 */
    plist_add(&q->list, &hb2->chain);
    atomic_inc(&hb2->waiters);
    q->lock_ptr = &hb2->lock;
}

FUTEX_CMP_REQUEUE_PI: PI futex로의 requeue

FUTEX_CMP_REQUEUE_PI는 condvar에서 PI mutex로 대기자를 이동할 때 사용됩니다. 일반 requeue와 달리 대상 futex가 PI futex이므로 futex_pi_state를 설정하고 rt_mutex에 대기자를 등록해야 합니다. 이것이 CVE-2014-3153의 원인이 된 복잡한 경로입니다.

NUMA-aware Futex 최적화

NUMA(Non-Uniform Memory Access) 시스템에서 futex 해시 테이블의 배치는 성능에 큰 영향을 미칩니다. futex word가 위치한 메모리 노드와 해시 버킷이 위치한 메모리 노드가 다르면 원격 메모리 접근 지연(Latency)이 발생합니다.

해시 테이블 NUMA 배치

Linux 커널의 alloc_large_system_hash()는 해시 테이블을 부팅 시 할당하며, 기본적으로 노드 0에 집중됩니다. 대형 NUMA 시스템에서는 이것이 병목이 될 수 있습니다.

최적화 전략

# NUMA 노드별 futex 관련 캐시 미스 측정
$ perf stat -e cache-misses,cache-references \
    -C 0-15  taskset -c 0-15 ./futex_bench

# numactl로 메모리 바인딩하여 futex word를 로컬 노드에 배치
$ numactl --membind=0 --cpunodebind=0 ./my_app

# NUMA 토폴로지 확인
$ numactl --hardware
available: 2 nodes (0-1)
node 0 cpus: 0 1 2 3 4 5 6 7
node 0 size: 32768 MB
node 1 cpus: 8 9 10 11 12 13 14 15
node 1 size: 32768 MB
node distances:
node   0   1
  0:  10  21
  1:  21  10

NUMA-aware 해시 분산 메커니즘

현재 Linux의 futex 해시 테이블은 단일 전역 배열입니다. NUMA 시스템에서 원격 노드의 해시 버킷에 접근하면 메모리 지연이 2~3배 증가합니다. 향후 노드별 해시 테이블 분리가 논의되고 있습니다.

# NUMA 시스템에서 futex 관련 원격 메모리 접근 측정
$ perf stat -e 'node-loads,node-load-misses' \
    taskset -c 0-7 ./futex_bench --threads=8
#  Performance counter stats:
#       1,234,567  node-loads
#         345,678  node-load-misses  (28% 원격 접근!)

# 개선: 스레드를 동일 NUMA 노드에 배치
$ numactl --cpunodebind=0 --membind=0 ./futex_bench --threads=8
#       1,234,567  node-loads
#          12,345  node-load-misses  (1% 미만!)

# futex 해시 테이블의 물리 메모리 위치 확인
$ cat /proc/pagetypeinfo | grep futex
# (직접 확인은 어렵지만, dmesg에서 할당 로그 확인 가능)
$ dmesg | grep "futex hash"
# futex hash table entries: 65536 (order: 10, 4194304 bytes, linear)

futex2 / futex_waitv (벡터 대기)

futex_waitv()는 Linux 5.16(2021년, Andre Almeida)에 도입된 새 시스템 콜로, 여러 futex word를 동시에 대기할 수 있습니다. select()/poll()의 futex 버전입니다. Wine/Proton의 Windows WaitForMultipleObjects() 에뮬레이션과 게임 엔진의 다중 이벤트 대기에서 핵심적으로 사용됩니다.

시스템 콜 인터페이스

/* include/uapi/linux/futex.h */
struct futex_waitv {
    __u64 val;       /* 기대 값 */
    __u64 uaddr;     /* futex word 주소 */
    __u32 flags;     /* FUTEX_32, FUTEX_PRIVATE_FLAG 등 */
    __u32 __reserved;
};

/* syscall 원형 */
long sys_futex_waitv(
    struct futex_waitv __user *waiters,  /* 대기 벡터 배열 */
    unsigned int nr_futexes,             /* 배열 크기 (최대 128) */
    unsigned int flags,                  /* 현재 0 */
    struct __kernel_timespec __user *timeout,
    clockid_t clockid                    /* CLOCK_MONOTONIC 등 */
);

/* 반환값: 깨어난 futex의 인덱스 (0-based), 에러 시 음수 */

사용 예: WaitForMultipleObjects 에뮬레이션

/* Wine/Proton — Windows WaitForMultipleObjects 에뮬레이션 */
#include <linux/futex.h>
#include <sys/syscall.h>

int wait_for_multiple_events(uint32_t *events[], int count,
                              struct timespec *timeout)
{
    struct futex_waitv waiters[128];
    int i;

    for (i = 0; i < count && i < 128; i++) {
        waiters[i].uaddr = (uintptr_t)events[i];
        waiters[i].val = 0;  /* 아직 시그널되지 않은 상태 */
        waiters[i].flags = FUTEX_32 | FUTEX_PRIVATE_FLAG;
        waiters[i].__reserved = 0;
    }

    /* 여러 futex 중 하나라도 변경되면 깨어남 */
    long ret = syscall(SYS_futex_waitv, waiters, count,
                       0, timeout, CLOCK_MONOTONIC);

    if (ret >= 0)
        return ret;  /* 깨어난 이벤트의 인덱스 */

    return -errno;
}

futex_waitv 내부 구현: 벡터 대기 상태 머신

futex_waitv()는 여러 futex를 동시에 대기하는 복잡한 상태 머신을 관리합니다. 모든 futex에 대해 원자적으로 대기 큐에 삽입하고, 하나라도 깨어나면 나머지를 정리합니다.

futex2 크기 변형: u8/u16/u32/u64

futex_waitv의 flags 필드는 futex word의 크기를 지정할 수 있도록 설계되었습니다. 현재 Linux에서는 FUTEX_32만 지원되지만, 향후 다른 크기가 추가될 수 있습니다.

/* include/uapi/linux/futex.h — futex2 크기 플래그 */
#define FUTEX_SIZE_MASK   0x03
#define FUTEX_8           0x00  /* 8비트 futex (미구현) */
#define FUTEX_16          0x01  /* 16비트 futex (미구현) */
#define FUTEX_32          0x02  /* 32비트 futex (현재 유일하게 지원) */
#define FUTEX_64          0x03  /* 64비트 futex (미구현) */

/* futex_waitv에서 사용:
 * waiters[i].flags = FUTEX_32 | FUTEX_PRIVATE_FLAG;
 *
 * 왜 다른 크기가 필요한가?
 * - u8/u16: 메모리 절약 (임베디드, 대량 futex)
 * - u64: 64비트 원자적 연산이 필요한 경우 (시퀀스 번호 등)
 * - Windows 호환: WaitOnAddress()는 1/2/4/8 바이트 지원
 *
 * 현재 상태: 커널에 검증 코드만 있고 실제 u8/u16/u64 경로는 미구현
 * → FUTEX_32 이외를 전달하면 -EINVAL */

futex2 NUMA 확장 (제안)

futex2 설계에는 NUMA-aware 해시 분산이 고려되어 있습니다. 현재 구현에서는 아직 활성화되지 않았지만, 향후 대규모 NUMA 시스템에서 해시 버킷을 NUMA 노드별로 분리하여 원격 메모리 접근을 줄이는 방안이 논의 중입니다.

Wine/Proton의 futex_waitv 활용 상세

Wine/Proton에서 futex_waitv가 없던 시절의 비효율성과 도입 후의 개선을 비교합니다.

/* Wine/Proton: futex_waitv 도입 전 (비효율적) */
/* WaitForMultipleObjects(3, handles, FALSE, INFINITE) 에뮬레이션:
 *
 * 방법 1: 스레드 풀 사용
 * → 각 핸들마다 대기 스레드 1개 생성 (3개 스레드 추가!)
 * → 어떤 스레드가 깨어나면 나머지에 signal
 * → 문제: 스레드 생성/해제 오버헤드, 메모리 사용
 *
 * 방법 2: busy polling
 * → 모든 핸들을 번갈아 FUTEX_WAIT(timeout=짧음) 시도
 * → 문제: CPU 낭비, 지연 시간 증가
 */

/* Wine/Proton: futex_waitv 도입 후 (효율적) */
NTSTATUS wait_for_multiple_objects(DWORD count, HANDLE *handles,
                                    BOOLEAN wait_all, LARGE_INTEGER *timeout)
{
    struct futex_waitv waiters[MAXIMUM_WAIT_OBJECTS]; /* 최대 64 */
    int i;

    for (i = 0; i < count; i++) {
        struct wine_object *obj = handle_to_object(handles[i]);
        waiters[i].uaddr = (uint64_t)&obj->signaled;
        waiters[i].val = 0; /* 아직 시그널되지 않은 값 */
        waiters[i].flags = FUTEX_32 | FUTEX_PRIVATE_FLAG;
        waiters[i].__reserved = 0;
    }

    long idx = syscall(SYS_futex_waitv, waiters, count,
                       0, timeout_ptr, CLOCK_MONOTONIC);

    if (idx >= 0)
        return WAIT_OBJECT_0 + idx;

    if (errno == ETIMEDOUT)
        return WAIT_TIMEOUT;

    return STATUS_UNSUCCESSFUL;
}
/* → 추가 스레드 없음, 단일 syscall, CPU 낭비 없음
 * → 게임 호환성 대폭 개선 (특히 DirectX 동기화 관련) */

glibc pthread → futex 매핑

glibc의 NPTL(Native POSIX Threads Library)은 POSIX 동기화 API를 내부적으로 futex 시스템 콜로 변환합니다. 이 매핑을 이해하면 pthread를 사용하는 애플리케이션의 커널 수준 동작을 정확히 추적할 수 있습니다.

glibc mutex 내부 상태 (lowlevellock)

/* glibc nptl/lowlevellock.h — 일반 mutex의 futex word 상태 */
/* 0: 잠금 해제 (unlocked)
 * 1: 잠겼으나 대기자 없음 (locked, no waiters)
 * 2: 잠기고 대기자 있음 (locked, with waiters)
 *
 * unlock 시:
 *   atomic_exchange(&futex, 0)의 이전값이 2이면 → FUTEX_WAKE 호출
 *   이전값이 1이면 → 커널 호출 불필요 */

static inline void
__lll_lock(int *futex, int private)
{
    /* Fast path: 0 → 1 */
    if (__glibc_likely(atomic_compare_exchange_weak_acquire(
            futex, 0, 1)))
        return;

    /* Medium path: 이미 잠겼지만 대기자 없음 → 1 → 2 */
    if (*futex != 2)
        *futex = atomic_exchange_acquire(futex, 2);

    /* Slow path: 커널 대기 */
    while (*futex == 2 || atomic_exchange_acquire(futex, 2) != 0) {
        futex_wait((unsigned int *)futex, 2, private);
    }
}

static inline void
__lll_unlock(int *futex, int private)
{
    /* 이전값이 2가 아니면 (대기자 없음) → 커널 호출 불필요 */
    if (atomic_exchange_release(futex, 0) != 1)
        futex_wake((unsigned int *)futex, 1, private);
}

glibc condvar 내부 (새 구현, glibc 2.25+)

/* glibc nptl/pthread_cond_wait.c — 간소화 */
int __pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)
{
    /* 1. 현재 세대(generation)의 시퀀스 번호 읽기 */
    uint64_t seq = atomic_load_relaxed(&cond->__data.__wseq);
    unsigned int g = seq & 1;  /* 현재 그룹 번호 */

    /* 2. 대기자 수 증가 */
    atomic_fetch_add_relaxed(&cond->__data.__g_refs[g], 2);

    /* 3. mutex 해제 */
    pthread_mutex_unlock(mutex);

    /* 4. futex 대기 (비트셋으로 그룹 구분) */
    unsigned int bitset = 1u << (g * 16);
    futex_wait_bitset(&cond->__data.__g_signals[g],
                      signals_val, private, NULL, bitset);

    /* 5. 깨어남 → mutex 재획득 */
    pthread_mutex_lock(mutex);
    return 0;
}

pthread_mutex 내부 구현 상세 (lowlevellock.h)

glibc의 pthread_mutex_t는 내부적으로 여러 타입을 지원하며, 각 타입에 따라 futex 호출 패턴이 다릅니다.

pthread_cond 내부: condvar와 futex의 관계

glibc 2.25+의 새로운 condvar 구현(Torvald Riegel 설계)은 이전 구현의 여러 문제점(steal wakeup, ABA)을 해결합니다. 2개의 대기 그룹과 비트셋을 사용합니다.

/* glibc pthread_cond_t 내부 구조 (간소화) */
struct pthread_cond_t.__data {
    unsigned long long __wseq;       /* 대기 시퀀스 번호 */
    unsigned long long __g1_start;   /* 그룹 1 시작 위치 */
    unsigned int __g_refs[2];        /* 그룹별 참조 카운트 */
    unsigned int __g_size[2];        /* 그룹별 대기자 수 */
    unsigned int __g1_orig_size;     /* 그룹 1 원래 크기 */
    unsigned int __wrefs;            /* 총 참조 카운트 */
    unsigned int __g_signals[2];     /* 그룹별 시그널 (futex word!) */
    /* __g_signals[g]가 각 그룹의 futex word 역할 */
};

/* pthread_cond_wait() 핵심 흐름:
 * 1. wseq에서 현재 그룹 g 결정 (bit 0)
 * 2. g_refs[g]++ (그룹 참조)
 * 3. mutex 해제
 * 4. FUTEX_WAIT_BITSET(&g_signals[g], expected, bitset=1<<(g*16))
 * 5. 깨어남 → mutex 재획득
 * 6. g_refs[g]-- (그룹 참조 해제)
 */

/* pthread_cond_signal() 핵심 흐름:
 * 1. 현재 활성 그룹 g 확인
 * 2. g_signals[g] 업데이트
 * 3. FUTEX_WAKE_BITSET(&g_signals[g], 1, bitset=1<<(g*16))
 */

/* pthread_cond_broadcast() 핵심 흐름:
 * 1. 세대 전환: wseq++ (g 값 반전)
 * 2. g_signals[g] 업데이트
 * 3. FUTEX_CMP_REQUEUE(&g_signals[g], 1, INT_MAX, &mutex.__lock, ...)
 *    → 1개만 깨우고 나머지는 mutex 대기 큐로 이동
 */

pthread_rwlock 내부: 읽기/쓰기 잠금의 futex 매핑

/* glibc pthread_rwlock_t 내부 (간소화) */
/* __readers: 현재 reader 수 + writer flag + 대기 플래그
 * 비트 레이아웃:
 *   bits 0-30: reader count
 *   bit 31: writer flag (WRPHASE)
 *
 * __writers_futex: writer 대기용 futex word
 * __wrhandover_futex: writer → reader 전환용
 *
 * 읽기 잠금:
 *   1. __readers++ (원자적)
 *   2. WRPHASE 비트 확인: writer 있으면 FUTEX_WAIT_BITSET(__readers, ...)
 *
 * 쓰기 잠금:
 *   1. __readers에 WRPHASE 설정 시도
 *   2. reader count > 0이면 FUTEX_WAIT_BITSET(__writers_futex, ...)
 *
 * 읽기 해제:
 *   1. __readers-- (원자적)
 *   2. 마지막 reader이고 writer 대기 시 FUTEX_WAKE(__writers_futex, 1)
 *
 * 쓰기 해제:
 *   1. WRPHASE 클리어
 *   2. reader 대기 시 FUTEX_WAKE(__readers, INT_MAX) 또는
 *      writer 대기 시 FUTEX_WAKE(__writers_futex, 1)
 */

pthread_barrier 내부: 장벽 동기화

/* glibc pthread_barrier_t 내부 (간소화) */
/* 동작 원리:
 * N개 스레드가 모두 도착할 때까지 대기,
 * 마지막 스레드가 도착하면 모두 깨움
 *
 * __count: 남은 대기 스레드 수
 * __current_round: 현재 라운드 번호 (세대)
 * __futex: 대기/깨움용 futex word
 */

/* pthread_barrier_wait() 흐름:
 * 1. round = __current_round 기록
 * 2. __count-- (원자적)
 * 3. __count > 0이면:
 *      FUTEX_WAIT(&__futex, round) → 슬립
 * 4. __count == 0이면 (마지막 도착자):
 *      __count = barrier_count (리셋)
 *      __current_round++ (다음 세대)
 *      __futex++ (값 변경으로 대기자 깨움)
 *      FUTEX_WAKE(&__futex, INT_MAX)
 * 5. return PTHREAD_BARRIER_SERIAL_THREAD (마지막 도착자만)
 *    또는 return 0 (나머지)
 */

사용자 공간 동기화 라이브러리 패턴

Futex를 직접 사용하는 것은 오류 가능성이 높으므로 일반적으로 glibc pthread를 권장하지만, 특수한 성능 요구사항이 있는 경우 futex 위에 맞춤 동기화 프리미티브를 구축합니다.

간단한 Futex 기반 Mutex 구현

/* 최소한의 사용자 공간 futex mutex */
#include <linux/futex.h>
#include <sys/syscall.h>
#include <stdatomic.h>

typedef struct { atomic_int val; } futex_mutex_t;

#define FUTEX_MUTEX_INIT {0}

static inline long futex_syscall(int *addr, int op, int val,
    const struct timespec *to, int *addr2, int val3) {
    return syscall(SYS_futex, addr, op, val, to, addr2, val3);
}

void futex_mutex_lock(futex_mutex_t *m) {
    int c;

    /* Fast path: 0 → 1 */
    c = 0;
    if (atomic_compare_exchange_strong_explicit(&m->val, &c, 1,
            memory_order_acquire, memory_order_relaxed))
        return;

    /* 이미 잠겨 있음: 대기자 있음(2)으로 표시 */
    if (c != 2)
        c = atomic_exchange_explicit(&m->val, 2,
                memory_order_acquire);

    /* Slow path: 커널 대기 */
    while (c != 0) {
        futex_syscall((int *)&m->val,
            FUTEX_WAIT | FUTEX_PRIVATE_FLAG, 2, NULL, NULL, 0);
        c = atomic_exchange_explicit(&m->val, 2,
                memory_order_acquire);
    }
}

void futex_mutex_unlock(futex_mutex_t *m) {
    /* 2 → 0: 대기자가 있을 수 있으므로 깨움 */
    if (atomic_exchange_explicit(&m->val, 0,
            memory_order_release) != 1) {
        futex_syscall((int *)&m->val,
            FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1, NULL, NULL, 0);
    }
}

Futex 기반 이벤트 (One-shot Signal)

/* 간단한 이벤트: 하나의 생산자가 여러 소비자에게 시그널 */
typedef struct { atomic_int signaled; } futex_event_t;

void futex_event_wait(futex_event_t *ev) {
    while (atomic_load_explicit(&ev->signaled,
            memory_order_acquire) == 0) {
        futex_syscall((int *)&ev->signaled,
            FUTEX_WAIT | FUTEX_PRIVATE_FLAG, 0, NULL, NULL, 0);
    }
}

void futex_event_signal(futex_event_t *ev) {
    atomic_store_explicit(&ev->signaled, 1, memory_order_release);
    /* INT_MAX: 모든 대기자 깨움 */
    futex_syscall((int *)&ev->signaled,
        FUTEX_WAKE | FUTEX_PRIVATE_FLAG, INT_MAX, NULL, NULL, 0);
}

Futex 기반 Read-Write Lock

/* 간소화된 read-write lock
 * state: 0 = free, >0 = reader count, -1 = writer locked
 */
typedef struct {
    atomic_int state;
    atomic_int writer_wait;  /* 대기 중인 writer 수 */
} futex_rwlock_t;

void futex_rwlock_rdlock(futex_rwlock_t *rw) {
    for (;;) {
        int s = atomic_load_acquire(&rw->state);
        if (s >= 0 &&
            atomic_load_acquire(&rw->writer_wait) == 0) {
            if (atomic_compare_exchange_weak_acquire(
                    &rw->state, &s, s + 1))
                return;
        } else {
            futex_syscall((int *)&rw->state,
                FUTEX_WAIT | FUTEX_PRIVATE_FLAG, s,
                NULL, NULL, 0);
        }
    }
}

void futex_rwlock_wrlock(futex_rwlock_t *rw) {
    atomic_fetch_add(&rw->writer_wait, 1);
    int expected = 0;
    while (!atomic_compare_exchange_weak_acquire(
            &rw->state, &expected, -1)) {
        futex_syscall((int *)&rw->state,
            FUTEX_WAIT | FUTEX_PRIVATE_FLAG, expected,
            NULL, NULL, 0);
        expected = 0;
    }
    atomic_fetch_sub(&rw->writer_wait, 1);
}

Futex 기반 카운팅 세마포어

/* Futex 기반 카운팅 세마포어 구현 */
typedef struct {
    atomic_int count;  /* 세마포어 카운트 */
} futex_sem_t;

void futex_sem_init(futex_sem_t *sem, int initial) {
    atomic_store(&sem->count, initial);
}

void futex_sem_wait(futex_sem_t *sem) {
    for (;;) {
        int c = atomic_load_acquire(&sem->count);
        if (c > 0) {
            /* 카운트 > 0: 즉시 획득 시도 */
            if (atomic_compare_exchange_weak(&sem->count, &c, c - 1))
                return;  /* Fast path 성공 */
        } else {
            /* 카운트 == 0: 커널 대기 */
            futex_syscall((int *)&sem->count,
                FUTEX_WAIT | FUTEX_PRIVATE_FLAG, 0,
                NULL, NULL, 0);
        }
    }
}

void futex_sem_post(futex_sem_t *sem) {
    int old = atomic_fetch_add_release(&sem->count, 1);
    if (old == 0) {
        /* 이전 카운트가 0이었으면 대기자가 있을 수 있음 */
        futex_syscall((int *)&sem->count,
            FUTEX_WAKE | FUTEX_PRIVATE_FLAG, 1,
            NULL, NULL, 0);
    }
}
/* glibc sem_wait/sem_post도 내부적으로 유사한 패턴 사용 */

스핀록-Futex 하이브리드 패턴

짧은 임계 구역에서는 순수 스핀록이, 긴 임계 구역에서는 futex가 효율적입니다. 하이브리드 접근법은 짧은 스핀 후 futex로 전환합니다.

/* 스핀-futex 하이브리드: 튜닝 가능한 스핀 횟수 */
typedef struct {
    atomic_int val;
    int max_spin;  /* 스핀 횟수 상한 */
} hybrid_mutex_t;

void hybrid_lock(hybrid_mutex_t *m) {
    int c = 0;

    /* Fast path: 즉시 획득 */
    if (atomic_compare_exchange_strong(&m->val, &c, 1))
        return;

    /* Spin phase: CPU에서 짧은 대기 */
    for (int i = 0; i < m->max_spin; i++) {
        c = 0;
        if (atomic_compare_exchange_weak(&m->val, &c, 1))
            return;
        __asm__ volatile("pause" ::: "memory"); /* x86 */
    }

    /* Futex phase: 커널 대기로 전환 */
    if (c != 2)
        c = atomic_exchange(&m->val, 2);
    while (c != 0) {
        futex_syscall((int *)&m->val,
            FUTEX_WAIT | FUTEX_PRIVATE_FLAG, 2, NULL, NULL, 0);
        c = atomic_exchange(&m->val, 2);
    }
}

/* max_spin 튜닝:
 * - CS < 100ns: max_spin = 100~200
 * - CS 100ns~1us: max_spin = 50~100
 * - CS > 1us: max_spin = 0 (즉시 futex)
 * glibc ADAPTIVE_NP는 max_spin=100 기본값 사용 */

Lock Elision (TSX/HLE와 Futex)

Lock Elision은 Intel TSX(Transactional Synchronization Extensions)의 HLE(Hardware Lock Elision) 또는 RTM(Restricted Transactional Memory)을 사용하여 실제 잠금 없이 트랜잭션(Transaction)으로 임계 구역을 실행하는 기법입니다. glibc는 이를 futex 기반 mutex의 최적화 경로로 지원했습니다.

TSX Lock Elision 동작 원리

/* glibc의 TSX Lock Elision (간소화) */
void mutex_lock_with_elision(mutex_t *m) {
    int ret;

retry_elision:
    /* 1. 트랜잭션 시작 (XBEGIN) */
    ret = _xbegin();

    if (ret == _XBEGIN_STARTED) {
        /* 2. 트랜잭션 내에서 잠금 상태 확인 */
        if (m->lock == 0) {
            /* 잠금을 실제로 획득하지 않고 임계 구역 실행
             * 트랜잭션이 성공하면 잠금 없이 완료 */
            return;
        }
        /* 잠금이 이미 획득됨: 트랜잭션 중단 */
        _xabort(0xFF);
    }

    /* 3. 트랜잭션 실패 시 일반 futex 경로로 폴백 */
    if (--elision_retries > 0)
        goto retry_elision;

    futex_mutex_lock(m);  /* 일반 잠금 */
}

TSX 이후의 대안: RTM 대체 기법

TSX가 사실상 폐기된 후, 비슷한 효과를 얻기 위한 소프트웨어 기법들이 연구되고 있습니다.

# glibc elision 설정 확인 및 제어
$ /lib64/ld-linux-x86-64.so.2 --help 2>&1 | grep elision
# glibc.elision.enable: 0 (기본값: 비활성화)

# TSX 지원 여부 확인
$ grep -o 'rtm\|hle' /proc/cpuinfo | sort -u
# (출력 없으면 TSX 미지원 또는 비활성화)

# TSX 강제 비활성화 (보안 권장)
# /etc/default/grub: GRUB_CMDLINE_LINUX="tsx=off"

Futex 성능 특성과 벤치마킹

Fast Path vs Slow Path 지연 비교

벤치마킹 도구와 방법

# perf bench futex — 커널 내장 futex 벤치마크
$ perf bench futex hash
# Run summary [PID 12345]: 4 threads, each operating on 1024 futexes for 10 secs.
# [thread  0] futexes: 0x55a8b0001000 ... 0x55a8b0001ffc
# Averaged 12345678 operations/sec (+- 0.12%), total secs = 10

$ perf bench futex wake
# Wokeup 1 of 1024 threads in 0.0023 ms

$ perf bench futex wake-parallel
# 4 threads waking up 1024 others

$ perf bench futex requeue
# Requeued 1023 of 1024 threads in 0.0089 ms

# 특정 프로세스의 futex syscall 빈도 측정
$ perf stat -e 'syscalls:sys_enter_futex' -p $(pidof myapp) -- sleep 10
 Performance counter stats for process id '12345':
         1,234,567      syscalls:sys_enter_futex

# strace로 futex 호출 분석
$ strace -e futex -c -p $(pidof myapp)
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- --------
 52.34    0.123456           1     98765           futex(WAIT)
 47.66    0.112345           1     89012           futex(WAKE)

성능 최적화 가이드라인

/* Adaptive mutex: 소유자가 다른 CPU에서 실행 중이면 스핀 */
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ADAPTIVE_NP);
pthread_mutex_init(&mutex, &attr);
/* glibc의 ADAPTIVE mutex는 소유자가 CPU에서 실행 중이면
 * 짧은 스핀(기본 100회)을 시도한 후 futex_wait로 전환합니다.
 * 짧은 임계 구역에서 syscall 오버헤드를 크게 줄입니다. */

벤치마크 방법론

Futex 벤치마크는 워크로드 특성에 따라 결과가 크게 달라집니다. 경합률, 임계 구역 길이, 스레드 수, NUMA 토폴로지(Topology)를 모두 고려해야 합니다.

/* 올바른 futex 벤치마크 작성법 */
#include <pthread.h>
#include <time.h>

#define ITERATIONS 10000000
#define NUM_THREADS 4
#define CRITICAL_SECTION_NS 50  /* 임계 구역 시뮬레이션 */

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
volatile long shared_counter = 0;

void *worker(void *arg) {
    struct timespec ts = {0, CRITICAL_SECTION_NS};

    for (int i = 0; i < ITERATIONS / NUM_THREADS; i++) {
        pthread_mutex_lock(&mutex);

        /* 임계 구역: 실제 작업 시뮬레이션 */
        shared_counter++;
        if (CRITICAL_SECTION_NS > 0)
            nanosleep(&ts, NULL);

        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

/* 주요 벤치마크 매개변수:
 * 1. CRITICAL_SECTION_NS: 0=uncontended 위주, 1000+=고경합
 * 2. NUM_THREADS: 1=단일 스레드, CPU수 이상=과경합
 * 3. ITERATIONS: 충분히 크게 (통계적 유의미성)
 * 4. CPU affinity: taskset으로 고정 (재현성)
 * 5. 주파수 고정: cpupower frequency-set -g performance
 */

경합 시 확장성 분석

Futex의 경합 시 확장성은 해시 테이블 크기, spinlock 보유 시간, 캐시라인 경합에 의해 결정됩니다. 스레드 수가 증가할수록 성능 저하가 발생하는 원인을 분석합니다.

해시 충돌의 성능 영향

# 해시 충돌 분석: bpftrace로 버킷 분포 확인
$ bpftrace -e '
kprobe:futex_hash {
    /* arg0은 futex_key의 해시값 */
    @buckets[arg0 % 4096] = count();
}
interval:s:5 {
    print(@buckets);
    clear(@buckets);
}
'

# 이상적: 균등 분포 (각 버킷 ~동일한 count)
# 문제: 특정 버킷에 집중 → spinlock 경합

# 해시 테이블 크기 확인
$ dmesg | grep futex
[    0.123456] futex hash table entries: 65536 (order: 10, 4194304 bytes, linear)

# 크기 부족 시 커널 파라미터로 조정 (6.7+)
# 또는 애플리케이션에서 futex word 주소를 캐시라인 단위로 분산

/proc 파라미터와 sysctl

Futex 자체에는 직접적인 sysctl 파라미터가 거의 없지만, 관련 커널 서브시스템의 설정이 futex 동작에 영향을 미칩니다.

futex 관련 /proc 디버그 인터페이스

futex 자체에는 전용 /proc 파일이 없지만, 관련 정보를 여러 /proc 파일에서 수집할 수 있습니다.

futex 통계 확인

# 시스템 전체 futex syscall 횟수 (ftrace)
$ echo 1 > /sys/kernel/debug/tracing/events/syscalls/sys_enter_futex/enable
$ cat /sys/kernel/debug/tracing/trace_pipe | head -20

# perf로 futex 이벤트 집계
$ perf stat -e 'syscalls:sys_enter_futex' -a -- sleep 5

# /proc/<pid>/syscall로 현재 대기 중인 syscall 확인
$ cat /proc/12345/syscall
202 0x7f1234567890 0x80 0x2 0x0 0x0 0x0 0x7ffd12345678 0x7f1234001234

# /proc/<pid>/status에서 robust_list 확인 (gdb)
$ cat /proc/12345/status | grep -i robust
# (직접 노출되지 않지만, gdb로 확인 가능)

# /proc/<pid>/maps에서 futex word 주소의 매핑 확인
$ grep '7f1234567' /proc/12345/maps
7f1234560000-7f1234570000 rw-p 00000000 00:00 0     [stack:12346]

Futex 디버깅 (ftrace, perf, strace)

Futex 관련 문제(교착 상태, 성능 저하, 잘못된 wakeup)를 디버깅하는 실전 기법을 다룹니다.

strace를 이용한 futex 추적

# futex 시스템 콜만 추적
$ strace -e futex -f -tt -T ./my_threaded_app
[pid 12345] 14:30:05.123456 futex(0x55a8b234c040, FUTEX_WAIT_BITSET_PRIVATE|FUTEX_CLOCK_REALTIME, 2, NULL, FUTEX_BITSET_MATCH_ANY) = 0 <0.001234>
[pid 12346] 14:30:05.124690 futex(0x55a8b234c040, FUTEX_WAKE_PRIVATE, 1) = 1 <0.000012>

# -c로 통계 요약
$ strace -e futex -c -f ./my_app
% time     seconds  usecs/call     calls    errors syscall
 60.00    0.600000          60     10000           futex(WAIT)
 30.00    0.300000          30     10000           futex(WAKE)
 10.00    0.100000         100      1000      500  futex(WAIT)  EAGAIN

ftrace를 이용한 커널 내부 추적

# futex 관련 커널 함수 추적
$ echo 'futex_wait*' > /sys/kernel/debug/tracing/set_ftrace_filter
$ echo 'futex_wake*' >> /sys/kernel/debug/tracing/set_ftrace_filter
$ echo function > /sys/kernel/debug/tracing/current_tracer
$ echo 1 > /sys/kernel/debug/tracing/tracing_on

# 특정 프로세스만 추적
$ echo $PID > /sys/kernel/debug/tracing/set_ftrace_pid

# 결과 확인
$ cat /sys/kernel/debug/tracing/trace
# tracer: function
#   TASK-PID   CPU#  TIMESTAMP  FUNCTION
#   -------    ----  ---------  --------
  myapp-12345 [002] 12345.678: futex_wait_setup <-futex_wait
  myapp-12345 [002] 12345.678: get_futex_key <-futex_wait_setup
  myapp-12346 [003] 12345.679: futex_wake <-do_futex
  myapp-12346 [003] 12345.679: futex_wake_mark <-futex_wake

# futex tracepoint 사용 (더 구조화된 데이터)
$ echo 1 > /sys/kernel/debug/tracing/events/lock/futex_wait/enable
$ echo 1 > /sys/kernel/debug/tracing/events/lock/futex_wake/enable

perf를 이용한 futex 프로파일링(Profiling)

# futex contention 프로파일링
$ perf lock record -- ./my_app
$ perf lock report
# Name              acquired   contended  avg wait   total wait
# mutex@0x55a8b234  10000      500        1.2us      600.0us

# futex syscall에서 CPU 소비 시간 분석
$ perf record -g -e 'syscalls:sys_enter_futex' ./my_app
$ perf report --sort=dso,symbol
# Overhead  Shared Object  Symbol
#   35.00%  libc.so.6      __lll_lock_wait
#   25.00%  libc.so.6      pthread_cond_wait@@GLIBC_2.3.2
#   15.00%  libc.so.6      __lll_unlock_wake

# futex 해시 버킷 충돌 분석 (bpftrace)
$ bpftrace -e '
kprobe:futex_wait_setup {
    @hash_bucket[arg0 % 256] = count();
}
END { print(@hash_bucket); }
'

GDB를 이용한 Futex 교착 상태 분석

# 교착 상태 발생 시 GDB로 분석
$ gdb -p $(pidof deadlocked_app)
(gdb) info threads
  Id   Target Id         Frame
  1    Thread 0x7f123  __lll_lock_wait (futex=0x55a8b234)
  2    Thread 0x7f456  __lll_lock_wait (futex=0x55a8b238)

# 각 스레드가 어떤 뮤텍스를 대기하는지 확인
(gdb) thread 1
(gdb) bt
#0  __lll_lock_wait (futex=0x55a8b234c040, private=0)
#1  pthread_mutex_lock (mutex=0x55a8b234c040)
#2  worker_function (arg=0x0)
...

# mutex 소유자 확인 (futex word의 TID)
(gdb) x/1wx 0x55a8b234c040
0x55a8b234c040: 0x00003042     # TID=12354 (스레드 2의 TID)

(gdb) x/1wx 0x55a8b238c040
0x55a8b238c040: 0x00003041     # TID=12353 (스레드 1의 TID)

# → 스레드 1(TID=12353)이 mutex A를 대기, mutex B를 보유
# → 스레드 2(TID=12354)가 mutex B를 대기, mutex A를 보유
# → 교착 상태!

ftrace로 futex 이벤트 추적

ftrace는 futex 내부의 커널 함수 호출 체인을 추적하는 가장 강력한 도구입니다. function_graph tracer를 사용하면 각 함수의 실행 시간까지 확인할 수 있습니다.

# function_graph로 futex 호출 체인과 실행 시간 추적
$ echo function_graph > /sys/kernel/debug/tracing/current_tracer
$ echo 'futex_*' > /sys/kernel/debug/tracing/set_graph_function
$ echo $PID > /sys/kernel/debug/tracing/set_ftrace_pid
$ echo 1 > /sys/kernel/debug/tracing/tracing_on

# 잠시 후 확인
$ cat /sys/kernel/debug/tracing/trace
# CPU  DURATION                  FUNCTION CALLS
#  |     |   |                     |   |   |   |
 2)               |  futex_wait() {
 2)   0.234 us    |    get_futex_key();
 2)               |    futex_q_lock() {
 2)   0.089 us    |      futex_hash();
 2)   0.456 us    |    }
 2)   0.123 us    |    get_futex_value_locked();
 2)               |    futex_wait_queue() {
 2)   0.067 us    |      plist_add();
 2) ! 1234.5 us   |      schedule();  /* ← 여기서 슬립! */
 2)   0.098 us    |    }
 2)   0.078 us    |    unqueue_me();
 2) ! 1235.8 us   |  }

# trace-cmd로 더 편리하게:
$ trace-cmd record -p function_graph -g 'futex_wait' \
    -P $PID -- sleep 5
$ trace-cmd report

perf로 futex 병목 분석

# perf lock: 뮤텍스 경합 핫스팟 분석
$ perf lock record -a -- sleep 10
$ perf lock report --sort acquired --key contended
# Name               acquired  contended  avg wait  total wait
# 0x55a8b234c040       123456       5432    2.3us     12.5ms
# → 이 주소의 mutex가 가장 심한 경합

# perf lock contention: 경합 소스 찾기
$ perf lock contention --output perf.data -- sleep 10
$ perf lock contention -i perf.data
# contended   total wait     max wait     avg wait   type      caller
#      5432       12.5ms       45us        2.3us      mutex     worker_func+0x34

# perf로 futex 호출 스택 분석
$ perf record -e 'syscalls:sys_enter_futex' -g -p $PID -- sleep 5
$ perf report --sort comm,dso,symbol --call-graph folded
# 어떤 코드 경로에서 futex syscall이 가장 많이 호출되는지 확인

# flamegraph 생성
$ perf script | stackcollapse-perf.pl | flamegraph.pl > futex_flame.svg

strace futex 분석 실전

# futex 연산 종류별 통계
$ strace -e futex -f -c -p $PID 2>&1 | head -20
# % time     seconds  usecs/call     calls    errors syscall
# ------ ----------- ----------- --------- --------- --------
#  45.12    0.451200           4    112800           futex(WAIT)
#  35.67    0.356700           3    118900           futex(WAKE)
#  10.23    0.102300           5     20460           futex(WAIT_BITSET)
#   5.34    0.053400           2     26700           futex(CMP_REQUEUE)
#   3.64    0.036400          18      2022      1011 futex(WAIT) EAGAIN

# EAGAIN이 많으면? → spurious wakeup 또는 잠금 경합이 매우 높음
# CMP_REQUEUE가 많으면? → condvar broadcast 빈번

# 특정 futex 주소의 wait/wake 패턴 분석
$ strace -e futex -f -tt -T -p $PID 2>&1 | \
    grep '0x55a8b234' | head -10
# 14:30:05.123 futex(0x55a8b234, WAIT, 2, NULL) = 0 <0.001234>
# 14:30:05.124 futex(0x55a8b234, WAKE, 1) = 1 <0.000012>
# → WAIT 시간 1.234ms: 경합 대기 시간
# → WAKE 시간 0.012ms: 깨우는 데 걸리는 시간

bpftrace 기반 futex 모니터링 도구

# 1. futex 연산별 호출 빈도 (실시간)
$ bpftrace -e '
tracepoint:syscalls:sys_enter_futex {
    $op = args->op & 0x7F;  /* PRIVATE_FLAG 마스크 */
    if ($op == 0)       { @ops["WAIT"] = count(); }
    else if ($op == 1)  { @ops["WAKE"] = count(); }
    else if ($op == 4)  { @ops["CMP_REQUEUE"] = count(); }
    else if ($op == 6)  { @ops["LOCK_PI"] = count(); }
    else if ($op == 7)  { @ops["UNLOCK_PI"] = count(); }
    else if ($op == 9)  { @ops["WAIT_BITSET"] = count(); }
    else if ($op == 10) { @ops["WAKE_BITSET"] = count(); }
    else                { @ops["OTHER"] = count(); }
}
interval:s:3 { print(@ops); clear(@ops); }
'

# 2. 프로세스별 futex 대기 시간 TOP 5
$ bpftrace -e '
tracepoint:syscalls:sys_enter_futex {
    @start[tid] = nsecs;
}
tracepoint:syscalls:sys_exit_futex /@start[tid]/ {
    @wait_us[comm, pid] = stats((nsecs - @start[tid]) / 1000);
    delete(@start[tid]);
}
interval:s:10 { print(@wait_us); exit(); }
'

# 3. futex 주소별 경합 핫스팟
$ bpftrace -e '
tracepoint:syscalls:sys_enter_futex /args->op == 0 || args->op == 128/ {
    @hotspot[args->uaddr] = count();
}
interval:s:5 { print(@hotspot, 10); clear(@hotspot); }
'

실전 패턴: eventfd vs futex vs io_uring

사용자 공간 동기화에는 futex 외에도 eventfd, io_uring 등 다양한 메커니즘이 있습니다. 각 메커니즘의 특성과 적합한 사용 사례를 비교합니다.

선택 가이드

• 스레드 간 뮤텍스/조건 변수 → pthread_mutex_t / pthread_cond_t (내부적으로 futex)
• 이벤트 루프(Event Loop)에서 대기/알림 → eventfd (epoll 통합 가능)
• 다중 futex 동시 대기 → futex_waitv() (게임, Wine)
• 비동기 I/O 완료 대기 → io_uring
• 경합이 극히 드문 경우 → futex (fast path 최적화 극대)
• 경합이 빈번한 경우 → 잠금 분할 또는 lock-free 알고리즘 고려

futex vs eventfd 내부 구조 비교

/* eventfd 내부 구조 */
struct eventfd_ctx {
    struct kref kref;           /* 참조 카운트 */
    wait_queue_head_t wqh;      /* 커널 대기 큐 */
    __u64 count;                /* 카운터 (항상 커널에서 관리) */
    unsigned int flags;
    int id;
};
/* → 항상 커널 객체 접근 필요 (fd 기반)
 * → 비경합 시에도 write()/read() syscall 필수
 * → epoll_wait()로 다중 이벤트 대기 가능 (장점) */

/* futex 내부 구조 */
/* → futex word는 사용자 공간 변수 (커널 객체 없음)
 * → 비경합 시 syscall 불필요 (핵심 장점)
 * → epoll 통합 불가 (FUTEX_FD 제거됨)
 * → futex_waitv()로 다중 대기 가능 (5.16+) */

/* 결론: 동기화 프리미티브(mutex/condvar)에는 futex가 최적.
 * 이벤트 기반 비동기 프로그래밍에는 eventfd가 최적.
 * 두 패턴이 모두 필요하면 eventfd + futex 조합 사용. */

io_uring의 futex 통합 (Linux 6.7+)

Linux 6.7부터 io_uring에 IORING_OP_FUTEX_WAIT와 IORING_OP_FUTEX_WAKE 연산이 추가되었습니다. 이를 통해 io_uring의 SQ/CQ 링에서 futex 대기/깨움을 비동기적으로 처리할 수 있습니다.

/* io_uring futex 연산 (Linux 6.7+) */
#include <linux/io_uring.h>

/* FUTEX_WAIT를 io_uring SQE로 제출 */
struct io_uring_sqe *sqe = io_uring_get_sqe(&ring);
io_uring_prep_futex_wait(sqe,
    &futex_word,      /* futex 주소 */
    expected_val,     /* 기대값 */
    FUTEX_BITSET_MATCH_ANY,
    FUTEX_32 | FUTEX_PRIVATE_FLAG,
    0);
sqe->user_data = MY_FUTEX_ID;

/* io_uring_submit() → 커널에 제출 */
io_uring_submit(&ring);

/* CQE로 결과 수신 (다른 I/O와 함께) */
struct io_uring_cqe *cqe;
io_uring_wait_cqe(&ring, &cqe);
if (cqe->user_data == MY_FUTEX_ID) {
    /* futex가 시그널됨! */
}

/* 장점:
 * - futex 대기와 I/O 대기를 단일 io_uring에서 통합
 * - epoll 없이 futex + 파일 I/O + 네트워크 I/O 동시 대기
 * - SQ polling 모드에서 syscall 오버헤드 제거 */

보안 고려사항 (CVE 사례)

Futex 코드는 사용자 공간의 입력을 직접 처리하는 시스템 콜이므로 보안에 매우 민감합니다. 복잡한 상태 기계와 다중 잠금으로 인해 역사적으로 여러 심각한 취약점이 발견되었습니다.

CVE-2014-3153 상세 분석

이 취약점은 FUTEX_REQUEUE와 PI futex의 상호작용에서 발생했습니다. 일반 futex에서 PI futex로 requeue하면서 futex_pi_state의 소유권 관리가 잘못되어 use-after-free가 발생했습니다. 이를 통해 커널 메모리를 조작하여 로컬 권한 상승이 가능했습니다.

/* CVE-2014-3153 공격 원리 (개념적) */
/* 1. 일반 futex(uaddr)에 스레드를 대기시킴 */
futex(uaddr, FUTEX_WAIT, val, NULL, NULL, 0);

/* 2. FUTEX_CMP_REQUEUE_PI로 PI futex(uaddr2)로 requeue */
futex(uaddr, FUTEX_CMP_REQUEUE_PI, 1, INT_MAX, uaddr2, val);

/* 3. 조작된 순서로 해제/재사용하여 dangling pointer 생성 */
/* → futex_pi_state가 해제된 후에도 참조되어 use-after-free */

/* 수정: requeue 시 PI 상태 참조 카운트를 정확히 관리하고,
 *       일반 futex에서 PI futex로의 requeue 경로를 엄격히 검증 */

CVE-2014-3153 상세 분석 (Towelroot)

CVE-2014-3153은 futex 역사상 가장 유명한 취약점입니다. FUTEX_REQUEUE와 FUTEX_CMP_REQUEUE_PI의 상호작용에서 use-after-free가 발생하여, Android 기기의 루트 권한을 획득하는 Towelroot 익스플로잇으로 악용되었습니다.

/* CVE-2014-3153 취약점 메커니즘 (개념적 설명) */
/*
 * 문제: 일반 futex 대기자를 PI futex로 requeue할 때
 * futex_pi_state의 소유권이 올바르게 관리되지 않음
 *
 * 공격 순서:
 * 1. Thread A: FUTEX_WAIT(uaddr1, val) → 일반 futex에서 대기
 * 2. Thread B: FUTEX_CMP_REQUEUE_PI(uaddr1, 1, INT_MAX, uaddr2, val)
 *    → Thread A를 PI futex(uaddr2)로 requeue
 * 3. requeue 과정에서 futex_pi_state 생성
 * 4. Thread A: FUTEX_LOCK_PI(uaddr2) → PI state 사용
 * 5. 특정 조건에서 futex_pi_state가 해제된 후에도 참조됨
 *    → use-after-free!
 * 6. 해제된 메모리를 공격자가 제어하는 데이터로 재할당
 *    → 커널 메모리 임의 쓰기 → 권한 상승
 */

/* 수정 패치 (Thomas Gleixner, 2014):
 * - requeue 시 PI state 참조 카운트 정확히 관리
 * - 일반 futex에서 PI futex로의 requeue 경로에 추가 검증
 * - requeue_state 원자 변수로 상태 전이 추적
 * - FUTEX_WAIT_REQUEUE_PI로 대기 중인 태스크만 requeue 허용
 */

CVE-2021-3347 PI futex 취약점

CVE-2021-3347은 PI futex의 futex_pi_state 해제 후 재사용 취약점입니다. 이 취약점은 FUTEX_LOCK_PI의 에러 경로에서 PI 상태 정리가 불완전하여 발생했습니다.

취약점 대응 패치와 방어 강화 히스토리

• KASAN (Kernel Address Sanitizer) — use-after-free를 런타임에 탐지
• KCSAN (Kernel Concurrency Sanitizer) — data race 탐지
• lockdep — 잠금 순서 위반 탐지 (PI 체인 포함)
• syzkaller — 커널 퍼저로 futex 코드의 엣지 케이스 자동 탐색
• seccomp — 불필요한 futex 연산 제한 (컨테이너(Container) 환경)

# syzkaller로 futex 퍼징 시 발견된 버그 예시
# syzkaller는 다양한 futex 연산을 무작위 조합하여 커널 크래시를 탐지
# 대표적 패턴:
# - FUTEX_WAIT + FUTEX_CMP_REQUEUE_PI 동시 호출
# - 잘못된 정렬 주소에 futex 연산
# - PI futex의 TID 조작
# - robust list의 포인터 조작
# - futex_waitv에 128개 futex + 타임아웃 동시 사용

# Docker 컨테이너에서 futex 보안 강화
$ docker run --security-opt seccomp=custom-profile.json ...
# custom-profile.json에서 FUTEX_REQUEUE(op=3) 차단 권장
# (안전한 FUTEX_CMP_REQUEUE만 허용)

# seccomp으로 futex 연산 제한 (컨테이너 프로필)
# Docker 기본 seccomp 프로필은 futex를 허용합니다.
# 커스텀 프로필에서 특정 futex_op만 허용:
{
    "names": ["futex", "futex_waitv"],
    "action": "SCMP_ACT_ALLOW"
}

# KASAN 활성화 빌드로 futex 버그 탐지
$ make defconfig
$ scripts/config -e KASAN
$ scripts/config -e KASAN_INLINE
$ make -j$(nproc)

아키텍처별 구현 차이 (x86, ARM64, RISC-V)

Futex의 커널 코드는 대부분 아키텍처 독립적이지만, 원자적 연산, 메모리 배리어, 사용자 공간 접근 방식에서 아키텍처별 차이가 있습니다.

/* arch/arm64/include/asm/futex.h — ARM64 원자적 연산 */
static inline int
arch_futex_atomic_op_inuser(int op, int oparg, int *oval,
                            u32 __user *uaddr)
{
    int oldval = 0, ret, tmp;

    uaccess_enable_privileged();

    switch (op) {
    case FUTEX_OP_SET:
        asm volatile(
        "   prfm    pstl1strm, %2\n"
        "1: ldxr    %w1, %2\n"
        "   stlxr   %w0, %w3, %2\n"
        "   cbnz    %w0, 1b\n"
        "   dmb     ish\n"
        : "=&r" (ret), "=&r" (oldval), "+Q" (*uaddr)
        : "r" (oparg)
        : "memory");
        break;
    /* ... FUTEX_OP_ADD, OR, ANDN, XOR ... */
    }

    uaccess_disable_privileged();
    *oval = oldval;
    return ret;
}

x86 구현 상세: LOCK CMPXCHG와 예외 처리

x86에서 futex의 사용자 공간 cmpxchg는 LOCK CMPXCHG 명령어를 사용합니다. 이 명령어는 TSO(Total Store Ordering) 메모리 모델과 결합하여 추가 메모리 배리어 없이도 올바른 동기화를 보장합니다.

/* arch/x86/include/asm/futex.h — x86 futex 원자적 연산 */
static inline int
futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
                               u32 oldval, u32 newval)
{
    int ret = 0;

    asm volatile(
        "1:\t" LOCK_PREFIX "cmpxchgl %4, %2\n"
        "2:\n"
        "\t.section .fixup, \"ax\"\n"
        "3:\tmov     %3, %0\n"    /* -EFAULT */
        "\tjmp     2b\n"
        "\t.previous\n"
        _ASM_EXTABLE_UA(1b, 3b)
        : "+r" (ret), "=a" (oldval), "+m" (*uaddr)
        : "i" (-EFAULT), "r" (newval), "1" (oldval)
        : "memory");

    *uval = oldval;
    return ret;
}

/* 핵심 포인트:
 * 1. LOCK_PREFIX: 캐시라인 잠금으로 원자성 보장
 * 2. LOCK CMPXCHG: compare-and-swap (EAX vs *uaddr)
 * 3. .fixup 섹션: 페이지 폴트 시 -EFAULT 반환
 * 4. _ASM_EXTABLE_UA: 사용자 주소 접근 예외 테이블 등록
 *
 * x86 TSO 모델에서:
 * - 모든 store는 프로그램 순서대로 관측됨
 * - LOCK 접두사는 전체 메모리 배리어 역할
 * - 따라서 추가 mfence/lfence 불필요 */

ARM64 구현: UAO, PAN과 futex의 관계

ARM64에서는 사용자 공간 메모리에 커널이 접근할 때 UAO(User Access Override)와 PAN(Privileged Access Never) 기능이 보안 경계를 강화합니다. futex 코드에서 사용자 메모리 접근 시 이러한 보호 기능을 올바르게 관리해야 합니다.

/* ARM64 futex에서의 사용자 공간 접근 제어 */
/* PAN (Privileged Access Never):
 * - 커널이 사용자 공간 주소에 직접 접근하면 폴트 발생
 * - 보안: 커널이 실수로 사용자 데이터를 읽는 것 방지
 *
 * futex 코드에서:
 * uaccess_enable_privileged()  → PAN 비활성화 (접근 허용)
 * ... LDXR/STXR 사용자 메모리 연산 ...
 * uaccess_disable_privileged() → PAN 재활성화
 *
 * UAO (User Access Override, ARMv8.2):
 * - LDTR/STTR 대신 일반 LDR/STR로 사용자 접근 가능
 * - unprivileged load/store가 자동으로 적용됨
 */

/* ARM64 LSE (Large System Extensions) 사용 여부:
 * alternatives 메커니즘으로 런타임에 결정 */
asm volatile(
ALTERNATIVE(
    /* LL/SC fallback (모든 ARM64) */
    "   prfm    pstl1strm, %2\n"
    "1: ldxr    %w1, %2\n"
    "   sub     %w0, %w1, %w3\n"
    "   cbnz    %w0, 2f\n"
    "   stlxr   %w0, %w4, %2\n"
    "   cbnz    %w0, 1b\n"
    "   dmb     ish\n"
    "2:",
    /* LSE CAS (ARMv8.1+ 지원 시) */
    "   mov     %w0, %w3\n"
    "   casal   %w0, %w4, %2\n"
    "   sub     %w0, %w0, %w3\n",
    ARM64_HAS_LSE_ATOMICS)
);

RISC-V 구현: LR/SC와 Zacas 확장

RISC-V의 futex 구현은 현재 A(Atomic) 확장의 LR/SC(Load-Reserved/Store-Conditional)를 주로 사용합니다. 향후 Zacas 확장이 보급되면 CAS 명령어로 대체될 예정입니다.

/* RISC-V 메모리 모델과 futex:
 *
 * RVWMO (RISC-V Weak Memory Ordering):
 * - 기본 약한 순서 모델
 * - 원자적 연산에 .aq (acquire), .rl (release) 수식어 필요
 *
 * futex cmpxchg에서:
 * LR.W       → load-reserved (다른 코어의 수정 감지 가능)
 * SC.W.RL    → store-conditional + release 순서
 * FENCE RW,RW → 전체 배리어 (acquire 보장)
 *
 * Ztso (Total Store Ordering) 확장이 있으면:
 * - fence 대부분 제거 가능
 * - x86과 동일한 메모리 모델
 * - futex 성능 약간 향상 (fence 오버헤드 감소)
 */

Futex와 PREEMPT_RT 상호작용

PREEMPT_RT 패치(Linux 6.12에서 메인라인 통합)는 커널 내부의 거의 모든 spinlock을 rt_mutex 기반의 sleeping lock으로 변환합니다. 이는 futex의 내부 구현에도 영향을 미칩니다.

PREEMPT_RT에서의 futex 변경점

PREEMPT_RT에서 PI Futex의 중요성

PREEMPT_RT 환경에서는 거의 모든 커널 잠금이 PI를 지원하므로, 사용자 공간의 PI futex가 커널 내부 잠금까지 연쇄적으로 우선순위 상속을 전파할 수 있습니다. 이는 실시간 애플리케이션에서 결정론적 지연 시간을 보장하는 데 필수적입니다.

/* PREEMPT_RT에서의 futex 해시 버킷 잠금 */
/* 일반 커널에서: */
spin_lock(&hb->lock);  /* 선점 불가, 실제 스핀 */
/* ... 해시 버킷 작업 ... */
spin_unlock(&hb->lock);

/* PREEMPT_RT 커널에서: */
spin_lock(&hb->lock);  /* rt_mutex 기반: 선점 가능, 슬립 가능 */
/* ... 해시 버킷 작업 ... */
spin_unlock(&hb->lock);
/* 문법은 동일하지만 내부 동작이 완전히 다름!
 * - 다른 RT 태스크가 선점할 수 있음
 * - PI가 적용되어 잠금 보유자의 우선순위가 부스트됨 */

# PREEMPT_RT 커널에서 futex 지연 측정
$ cyclictest -m -S -p 98 -i 1000 -l 100000
# T: 0 ( 1234) P:98 I:1000 C: 100000 Min:   1 Act:   3 Avg:   4 Max:  15

PREEMPT_RT에서의 futex 지연 시간 분석

PREEMPT_RT 커널에서 futex의 최악 지연 시간(worst-case latency)을 측정하고 일반 커널과 비교합니다.

PREEMPT_RT 환경 futex 모범 사례

FUTEX_WAKE_OP 상세 인코딩

FUTEX_WAKE_OP는 glibc의 pthread_cond_signal() 구현에서 조건 변수의 시퀀스 카운터를 원자적으로 업데이트하면서 동시에 대기자를 깨우는 데 사용됩니다. 하나의 시스템 콜로 두 개의 futex에 대한 연산을 수행하여 syscall 오버헤드를 절반으로 줄입니다.

/* kernel/futex/waitwake.c — futex_wake_op() 핵심 로직 */
static int futex_wake_op(u32 __user *uaddr1, unsigned int flags,
    u32 __user *uaddr2, int nr_wake, int nr_wake2, int op)
{
    struct futex_hash_bucket *hb1, *hb2;
    union futex_key key1, key2;
    int ret, oldval;

    /* 1. 두 futex의 키 생성 */
    ret = get_futex_key(uaddr1, flags, &key1, FUTEX_READ);
    ret = get_futex_key(uaddr2, flags, &key2, FUTEX_WRITE);

    /* 2. 두 해시 버킷 모두 잠금 (deadlock 방지를 위해 주소 순) */
    double_lock_hb(hb1, hb2);

    /* 3. uaddr2에 원자적 연산 수행 */
    ret = futex_atomic_op_inuser(op, uaddr2);
    /* op 인코딩:
     *   (op_type << 28) | (cmp_type << 24) | (oparg << 12) | cmparg
     * op_type: SET, ADD, OR, ANDN, XOR
     * cmp_type: EQ, NE, LT, LE, GT, GE */

    /* 4. uaddr1에서 nr_wake개 깨움 */
    ret = futex_wake_mark_all(hb1, &key1, nr_wake);

    /* 5. 연산 결과가 비교 조건을 만족하면 uaddr2에서도 깨움 */
    if (futex_op_cmp(oldval, op, cmparg))
        ret += futex_wake_mark_all(hb2, &key2, nr_wake2);

    double_unlock_hb(hb1, hb2);
    return ret;
}

해시 버킷 이중 잠금과 교착 방지

FUTEX_WAKE_OP와 FUTEX_CMP_REQUEUE는 두 개의 해시 버킷을 동시에 잠가야 합니다. 교착 상태를 방지하기 위해 항상 주소가 작은 버킷을 먼저 잠급니다.

/* kernel/futex/core.c — double_lock_hb() */
static inline void
double_lock_hb(struct futex_hash_bucket *hb1,
               struct futex_hash_bucket *hb2)
{
    if (hb1 <= hb2) {
        spin_lock(&hb1->lock);
        if (hb1 < hb2)
            spin_lock_nested(&hb2->lock, SINGLE_DEPTH_NESTING);
    } else {
        spin_lock(&hb2->lock);
        spin_lock_nested(&hb1->lock, SINGLE_DEPTH_NESTING);
    }
    /* lockdep: SINGLE_DEPTH_NESTING으로 중첩 잠금 허용 표시 */
}

사용자 공간 주소 유효성 검증

커널은 사용자 공간의 futex word에 접근할 때 여러 단계의 유효성 검증을 수행합니다. 잘못된 주소, 정렬되지 않은 주소, 매핑되지 않은 페이지 등을 처리해야 합니다.

/* kernel/futex/core.c — 주소 검증 */
static int futex_check_address(u32 __user *uaddr)
{
    /* 1. 자연 정렬 확인 (4바이트 경계) */
    if ((unsigned long)uaddr % sizeof(u32))
        return -EINVAL;

    /* 2. 사용자 공간 주소 범위 확인 */
    if (!access_ok(uaddr, sizeof(u32)))
        return -EFAULT;

    return 0;
}

/* get_futex_value_locked — 해시 버킷 잠금 하에서 값 읽기 */
static int get_futex_value_locked(u32 *dest, u32 __user *from)
{
    int ret;

    /* pagefault_disable: 잠금 보유 중 페이지 폴트 금지 */
    pagefault_disable();
    ret = __get_user(*dest, from);
    pagefault_enable();

    /* 페이지 폴트 시 잠금 해제 후 재시도 */
    return ret ? -EFAULT : 0;
}

PI Futex: Futex Word 인코딩 상세

PI futex에서 futex word는 단순한 잠금 상태가 아니라 소유자의 TID와 상태 비트를 인코딩합니다.

/* PI Futex word 비트 레이아웃 (32비트) */
/*
 * Bits 0-29:  TID (Thread ID) of the lock owner
 *             0이면 잠금 해제 상태
 *
 * Bit 30:     FUTEX_OWNER_DIED
 *             소유자가 robust futex를 보유한 채 사망
 *             다음 소유자는 EOWNERDEAD를 받음
 *
 * Bit 31:     FUTEX_WAITERS
 *             커널에 대기자가 있음을 표시
 *             이 비트가 설정되면 unlock 시 반드시 커널 호출 필요
 */

#define FUTEX_TID_MASK    0x3FFFFFFFU  /* bits 0-29 */
#define FUTEX_OWNER_DIED  0x40000000U  /* bit 30 */
#define FUTEX_WAITERS     0x80000000U  /* bit 31 */

/* 예시:
 * futex_word = 0x00001234  → TID 0x1234가 소유, 대기자 없음
 * futex_word = 0x80001234  → TID 0x1234가 소유, 대기자 있음
 * futex_word = 0x40001234  → TID 0x1234가 소유했으나 사망
 * futex_word = 0xC0001234  → 사망 + 대기자 있음
 * futex_word = 0x00000000  → 잠금 해제 상태
 */

Robust Futex: glibc의 등록 흐름

/* glibc nptl/nptl_setxid.c — robust list 등록 (간소화) */
/* 각 스레드 생성 시 자동으로 호출됨 */
void __nptl_set_robust_list_internal(void)
{
    struct robust_list_head *head;

    head = &THREAD_SELF->robust_head;

    /* 커널에 robust list 위치 등록 */
    INTERNAL_SYSCALL(set_robust_list, 2, head, sizeof(*head));
}

/* 스레드 종료 시 커널이 자동으로 exit_robust_list() 호출
 * → 보유 중인 모든 robust mutex 정리 */

pthread_cond_broadcast와 CMP_REQUEUE의 조합

glibc의 pthread_cond_broadcast()는 FUTEX_CMP_REQUEUE를 사용하여 thundering herd를 방지합니다. 구체적인 동작은 다음과 같습니다:

/* glibc nptl/pthread_cond_broadcast.c — 간소화 */
int __pthread_cond_broadcast(pthread_cond_t *cond)
{
    /* 1. 시퀀스 번호 증가 (다음 세대로 전환) */
    unsigned int g = cond->__data.__wseq & 1;
    cond->__data.__wseq += 1;  /* 세대 전환 */

    /* 2. 대기자에게 시그널 */
    atomic_store_release(&cond->__data.__g_signals[g],
                         cond->__data.__g_size[g] << 1);

    /* 3. FUTEX_CMP_REQUEUE: 1개 깨우고 나머지는 mutex 큐로 이동 */
    futex_cmp_requeue(&cond->__data.__g_signals[g],
                      1,  /* nr_wake: 1개만 깨움 */
                      INT_MAX,  /* nr_requeue: 나머지 전부 이동 */
                      &mutex->__data.__lock,
                      signals_val);  /* 비교 값 */

    return 0;
}

futex_waitv 커널 구현 상세

/* kernel/futex/syscalls.c — sys_futex_waitv() */
SYSCALL_DEFINE5(futex_waitv,
    struct futex_waitv __user *, waiters,
    unsigned int, nr_futexes,
    unsigned int, flags,
    struct __kernel_timespec __user *, timeout,
    clockid_t, clockid)
{
    struct futex_vector *futexv;
    struct hrtimer_sleeper to;
    int ret;

    /* 유효성 검사 */
    if (nr_futexes < 2 || nr_futexes > FUTEX_WAITV_MAX) /* 128 */
        return -EINVAL;

    /* futex_vector 배열 할당 (스택 또는 kmalloc) */
    futexv = kcalloc(nr_futexes, sizeof(*futexv), GFP_KERNEL);

    /* 사용자 공간에서 대기 벡터 복사 */
    if (copy_from_user(futexv, waiters,
                       nr_futexes * sizeof(*waiters)))
        goto err;

    /* 각 futex에 대해 키 생성 및 대기 큐 삽입 */
    for (i = 0; i < nr_futexes; i++) {
        ret = get_futex_key(futexv[i].uaddr, futexv[i].flags,
                           &futexv[i].q.key, FUTEX_READ);

        /* 값 비교: 이미 변경되었으면 즉시 반환 */
        if (*futexv[i].uaddr != futexv[i].val) {
            ret = i;  /* 변경된 futex의 인덱스 */
            goto unqueue_all;
        }

        futex_q_lock_and_enqueue(&futexv[i].q);
    }

    /* 모든 futex가 아직 유효하면 슬립 */
    set_current_state(TASK_INTERRUPTIBLE);
    if (timeout)
        hrtimer_sleeper_start_expires(&to, HRTIMER_MODE_ABS);

    /* schedule: 어느 하나라도 WAKE되면 깨어남 */
    freezable_schedule();

    /* 깨어남: 어떤 futex가 시그널되었는지 확인 */
    for (i = 0; i < nr_futexes; i++) {
        if (futexv[i].q.woken) {
            ret = i;
            break;
        }
    }

unqueue_all:
    /* 나머지 모든 futex_q를 해시 버킷에서 제거 */
    for (j = 0; j < nr_futexes; j++)
        futex_unqueue(&futexv[j].q);

    kfree(futexv);
    return ret;  /* 깨어난 futex의 인덱스 */
}

NUMA-aware 잠금 설계 패턴

대규모 NUMA 시스템에서 최적의 futex 성능을 위한 설계 패턴을 소개합니다.

/* NUMA-aware 잠금 분할 예시 */
#include <numa.h>

#define MAX_NUMA_NODES 8
#define CACHE_LINE_SIZE 64

/* 각 NUMA 노드별 독립적인 잠금 */
struct numa_lock_set {
    struct {
        pthread_mutex_t lock;
        char padding[CACHE_LINE_SIZE - sizeof(pthread_mutex_t)];
    } __attribute__((aligned(CACHE_LINE_SIZE))) per_node[MAX_NUMA_NODES];
};

/* 현재 NUMA 노드에 해당하는 잠금 사용 */
void numa_aware_lock(struct numa_lock_set *ls) {
    int node = numa_node_of_cpu(sched_getcpu());
    pthread_mutex_lock(&ls->per_node[node].lock);
}

void numa_aware_unlock(struct numa_lock_set *ls) {
    int node = numa_node_of_cpu(sched_getcpu());
    pthread_mutex_unlock(&ls->per_node[node].lock);
}

/* 이 패턴은 노드 간 캐시라인 바운싱을 제거하여
 * 경합 시 성능을 수 배 개선합니다.
 * 단, 모든 노드의 잠금을 동시에 획득해야 하는
 * 전역 연산이 있다면 추가 조정이 필요합니다. */

Futex 경합 프로파일링 실전 예제

# 1. perf bench futex 전체 실행
$ perf bench futex all

# hash: Operations/second for 4 threads hashing on 1024 futexes:
#   15234567 ops/sec

# wake: Wokeup 1 of 1024 threads in 0.0021 ms
# wake-parallel: 4 threads waking 1024 in 0.0045 ms
# requeue: Requeued 1023 of 1024 in 0.0078 ms
# lock-pi: 4 threads locking on PI futex for 10 secs: 567890 ops/sec

# 2. bpftrace로 futex 대기 시간 히스토그램
$ bpftrace -e '
tracepoint:syscalls:sys_enter_futex /args->op == 0 || args->op == 128/ {
    @start[tid] = nsecs;
}
tracepoint:syscalls:sys_exit_futex /@start[tid]/ {
    @wait_us = hist((nsecs - @start[tid]) / 1000);
    delete(@start[tid]);
}
interval:s:10 { exit(); }
' 2>/dev/null

# 3. Lock contention 핫스팟 찾기
$ perf lock record -a -- sleep 10
$ perf lock report --sort acquired --key contended
#              acquired   contended  avg wait   total wait
# 0x55a8...       98765       5432    2.3us     12.5ms
# 0x55a8...       87654       1234    1.1us      1.4ms

# 4. futex 시스템 콜 빈도 by PID
$ bpftrace -e '
tracepoint:syscalls:sys_enter_futex {
    @count[comm, pid] = count();
}
interval:s:5 { print(@count); clear(@count); }
'

교착 상태 자동 탐지 스크립트

#!/bin/bash
# futex_deadlock_detector.sh — 교착 상태 의심 프로세스 분석

PID=${1:?Usage: $0 <pid>}

echo "=== Futex Deadlock Analysis for PID $PID ==="

# 1. 모든 스레드의 현재 syscall 확인
echo -e "\n--- Threads in futex wait ---"
for tid in /proc/$PID/task/*/; do
    tid_num=$(basename $tid)
    syscall=$(cat $tid/syscall 2>/dev/null | awk '{print $1}')
    if [ "$syscall" = "202" ] || [ "$syscall" = "98" ]; then
        futex_addr=$(cat $tid/syscall 2>/dev/null | awk '{print $2}')
        echo "  TID $tid_num: FUTEX_WAIT on $futex_addr"
    fi
done

# 2. 스택 트레이스 수집
echo -e "\n--- Thread stack traces ---"
for tid in /proc/$PID/task/*/; do
    tid_num=$(basename $tid)
    if grep -q 'futex_wait\|__lll_lock_wait' $tid/wchan 2>/dev/null; then
        echo "  TID $tid_num ($(cat $tid/wchan)):"
        cat $tid/stack 2>/dev/null | head -10 | sed 's/^/    /'
    fi
done

# 3. Mutex 소유자 추적 (gdb 필요)
echo -e "\n--- Use GDB for mutex owner analysis: ---"
echo "  gdb -batch -ex 'thread apply all bt' -p $PID"

Futex 관련 보안 강화 설정

# 1. seccomp BPF로 futex 연산 제한
# 위험한 FUTEX_REQUEUE (op=3) 차단, 안전한 CMP_REQUEUE (op=4)만 허용
# (libseccomp 사용)

# 2. KASAN으로 futex use-after-free 탐지 (커널 빌드 옵션)
CONFIG_KASAN=y
CONFIG_KASAN_GENERIC=y  # 또는 CONFIG_KASAN_SW_TAGS (ARM64)
CONFIG_KASAN_INLINE=y

# 3. lockdep으로 PI 체인 교착 탐지
CONFIG_PROVE_LOCKING=y
CONFIG_DEBUG_LOCK_ALLOC=y
CONFIG_LOCKDEP=y

# 4. futex 관련 커널 디버그 옵션
CONFIG_DEBUG_PI_LIST=y
CONFIG_DEBUG_RT_MUTEXES=y

# 5. syzkaller 퍼저로 futex 엣지 케이스 테스트
$ cat syzkaller_futex.cfg
{
    "enable_syscalls": [
        "futex", "futex_waitv",
        "set_robust_list", "get_robust_list"
    ]
}

PREEMPT_RT 환경에서의 실시간 뮤텍스 설정

/* 실시간 애플리케이션을 위한 PI mutex 설정 */
#include <pthread.h>
#include <sched.h>

int setup_rt_mutex(pthread_mutex_t *mutex, int ceiling_prio)
{
    pthread_mutexattr_t attr;
    int ret;

    ret = pthread_mutexattr_init(&attr);

    /* PI (우선순위 상속) 활성화 — PREEMPT_RT에서 필수 */
    ret = pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);

    /* Robust 활성화 — 비정상 종료 대응 */
    ret = pthread_mutexattr_setrobust(&attr, PTHREAD_MUTEX_ROBUST);

    /* 에러 체킹 타입 — 디버깅 시 유용 */
    ret = pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ERRORCHECK);

    ret = pthread_mutex_init(mutex, &attr);
    pthread_mutexattr_destroy(&attr);

    return ret;
}

/* RT 스레드 생성 */
void create_rt_thread(pthread_t *thread, void *(*func)(void *),
                       int priority)
{
    pthread_attr_t attr;
    struct sched_param param;

    pthread_attr_init(&attr);
    pthread_attr_setinheritsched(&attr, PTHREAD_EXPLICIT_SCHED);
    pthread_attr_setschedpolicy(&attr, SCHED_FIFO);
    param.sched_priority = priority;
    pthread_attr_setschedparam(&attr, &param);

    pthread_create(thread, &attr, func, NULL);
    pthread_attr_destroy(&attr);
}

/* EOWNERDEAD 처리 예시 */
int safe_mutex_lock(pthread_mutex_t *mutex)
{
    int ret = pthread_mutex_lock(mutex);

    if (ret == EOWNERDEAD) {
        /* 이전 소유자가 비정상 종료함 */
        /* 공유 자원 일관성 복구 수행 */
        recover_shared_state();

        /* mutex를 일관된 상태로 표시 */
        pthread_mutex_consistent(mutex);
        return 0;
    }

    return ret;
}

/* 복구 불가능한 경우 */
int unrecoverable_mutex_lock(pthread_mutex_t *mutex)
{
    int ret = pthread_mutex_lock(mutex);

    if (ret == EOWNERDEAD) {
        /* 복구 불가능: mutex를 ENOTRECOVERABLE 상태로 전환 */
        /* 이후 모든 lock 시도는 ENOTRECOVERABLE 반환 */
        pthread_mutex_unlock(mutex);  /* → ENOTRECOVERABLE 전파 */
        return -1;
    }

    if (ret == ENOTRECOVERABLE) {
        /* mutex가 영구적으로 손상됨 — 재초기화 필요 */
        return -1;
    }

    return ret;
}

ARM64 LSE 원자적 연산과 Futex 성능

ARMv8.1-A의 LSE(Large System Extensions)는 LL/SC(Load-Linked/Store-Conditional) 루프를 단일 원자적 명령어로 대체합니다. 이는 futex의 cmpxchg 성능에 직접적인 영향을 미칩니다.

LSE 명령어는 특히 높은 경합 상황에서 LL/SC 대비 3~4배 빠릅니다. 이는 LL/SC 루프가 경합 시 재시도를 반복하는 반면, LSE CAS는 하드웨어 수준에서 원자성을 보장하기 때문입니다.

/* arch/arm64/include/asm/atomic_lse.h — LSE CAS 사용 */
static inline u32 __lse_cmpxchg_case_32(volatile void *ptr,
                                         u32 old, u32 new)
{
    u32 tmp;
    asm volatile(
        "   cas     %w[old], %w[new], %[v]\n"
        : [v] "+Q" (*(u32 *)ptr), [old] "+r" (old)
        : [new] "r" (new)
        : "memory");
    return old;
}

/* vs LL/SC 방식 */
static inline u32 __ll_sc_cmpxchg_case_32(volatile void *ptr,
                                            u32 old, u32 new)
{
    u32 tmp, oldval;
    asm volatile(
        "1: ldxr    %w[oldval], %[v]\n"
        "   eor     %w[tmp], %w[oldval], %w[old]\n"
        "   cbnz    %w[tmp], 2f\n"
        "   stxr    %w[tmp], %w[new], %[v]\n"
        "   cbnz    %w[tmp], 1b\n"  /* 실패 시 재시도 루프 */
        "2:"
        : [v] "+Q" (*(u32 *)ptr), [oldval] "=&r" (oldval),
          [tmp] "=&r" (tmp)
        : [old] "r" (old), [new] "r" (new)
        : "memory");
    return oldval;
}

RISC-V에서의 Futex 고려사항

RISC-V의 원자적 확장(A 확장)은 LR/SC(Load-Reserved/Store-Conditional)와 AMO(Atomic Memory Operations)를 제공합니다. 현재 대부분의 RISC-V futex 구현은 LR/SC를 사용하며, Zacas 확장의 AMOCAS는 아직 초기 단계입니다.

/* arch/riscv/include/asm/futex.h — RISC-V futex 원자적 연산 */
static inline int
futex_atomic_cmpxchg_inatomic(u32 *uval, u32 __user *uaddr,
                               u32 oldval, u32 newval)
{
    int ret = 0;
    u32 val;

    __enable_user_access();

    asm volatile(
        "1: lr.w    %[val], %[addr]\n"
        "   bne     %[val], %[old], 2f\n"
        "   sc.w.rl %[ret], %[new], %[addr]\n"
        "   bnez    %[ret], 1b\n"
        "   fence   rw, rw\n"
        "2:\n"
        _ASM_EXTABLE_UACCESS_ERR(1b, 2b, %[ret])
        : [val] "=&r" (val), [ret] "+r" (ret),
          [addr] "+A" (*uaddr)
        : [old] "r" (oldval), [new] "r" (newval)
        : "memory");

    __disable_user_access();

    *uval = val;
    return ret;
}

futex vs eventfd vs io_uring: 벤치마크 결과

# 스레드 간 알림(ping-pong) 지연 비교 테스트
# 테스트 환경: x86_64, Intel Xeon Gold 6342, Linux 6.6

# 1. futex (FUTEX_WAIT/WAKE)
$ ./ipc_bench --method=futex --iterations=1000000
  Avg latency: 1.23 us
  P99 latency: 2.45 us
  P99.9 latency: 5.67 us

# 2. eventfd (read/write)
$ ./ipc_bench --method=eventfd --iterations=1000000
  Avg latency: 1.56 us
  P99 latency: 3.12 us
  P99.9 latency: 7.89 us

# 3. io_uring (IORING_OP_MSG_RING, Linux 6.0+)
$ ./ipc_bench --method=io_uring --iterations=1000000
  Avg latency: 0.89 us  (SQ polling mode)
  P99 latency: 1.67 us
  P99.9 latency: 3.45 us

# 4. pipe (write/read)
$ ./ipc_bench --method=pipe --iterations=1000000
  Avg latency: 2.34 us
  P99 latency: 4.56 us
  P99.9 latency: 12.34 us

glibc Adaptive Mutex의 스핀 전략

TSX Lock Elision이 사실상 무력화된 현재, glibc의 PTHREAD_MUTEX_ADAPTIVE_NP가 짧은 경합에 대한 실질적인 최적화입니다.

/* glibc nptl/pthread_mutex_lock.c — adaptive 스핀 (간소화) */
static int
adaptive_spin(pthread_mutex_t *mutex)
{
    int max_spin = 100;  /* 기본 스핀 횟수 */
    int cnt = 0;

    /* 소유자가 다른 CPU에서 실행 중인지 확인 */
    int owner_tid = mutex->__data.__owner;
    if (owner_tid == 0)
        return 0;  /* 이미 해제됨 */

    /* /proc/[tid]/status를 통해 확인하는 것이 아니라,
     * 커널이 FUTEX_WAIT에서 반환할 때의 조건으로 판단 */
    while (cnt++ < max_spin) {
        if (atomic_load_relaxed(&mutex->__data.__lock) == 0)
            return 0;  /* 잠금 해제됨: cmpxchg 시도 */

        /* CPU 힌트: x86에서 PAUSE 명령 */
        __asm__ volatile("pause" ::: "memory");
    }

    return 1;  /* 스핀 실패: futex_wait로 전환 */
}

참고 자료

커널 공식 문서 및 man 페이지

• futex(2) — futex 시스템 콜 man 페이지
• futex(7) — futex 개요 및 사용자 공간 동기화 개념
• RT-mutex implementation design — PI Futex의 기반이 되는 rt_mutex 설계
• Lock types and their rules — futex 내부 잠금의 커널 규칙

LWN.net 심층 기사

• A futex overview and update (2009) — futex 전체 아키텍처와 발전 역사
• Futex2 and futex_waitv (2021) — futex2 시스템 콜과 futex_waitv() 소개
• A realtime preemption overview (2006) — PI futex와 실시간 커널
• Lockless patterns: an introduction to compare-and-swap (2014) — futex fast path의 CAS 기반 동작

학술 자료 및 외부 참고

• Hubertus Franke & Rusty Russell — "Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux" (OLS 2002) — futex 원본 논문
• Ulrich Drepper — "Futexes Are Tricky" (2011) — futex 사용의 함정과 올바른 패턴
• Paul McKenney — "Is Parallel Programming Hard?" — 사용자 공간 동기화 패턴
• 커널 소스: kernel/futex/core.c, kernel/futex/waitwake.c, kernel/futex/pi.c, kernel/futex/requeue.c
• glibc NPTL: nptl/lowlevellock.h, nptl/pthread_mutex_lock.c, nptl/pthread_cond_wait.c
• 벤치마크: perf bench futex hash|wake|wake-parallel|requeue|lock-pi

관련 문서

Futex 커널 디버그 빌드 옵션