Reader-Writer Lock (읽기-쓰기 잠금)

읽기 작업이 쓰기 작업보다 압도적으로 많은 상황에서 동시 읽기를 허용하면서도 쓰기의 배타성을 보장하는 Reader-Writer Lock을 분석합니다. rwlock_t(qrwlock)의 cnts+wait_lock 내부 구조, rw_semaphore의 Optimistic Spinning과 HANDOFF 메커니즘, percpu_rw_semaphore의 Per-CPU 카운터 설계, Writer Starvation 문제와 해결 전략, PREEMPT_RT에서의 rwbase_rt 변환까지 커널 소스 기반으로 분석합니다.

이론적 배경: Readers-Writers 문제

Readers-Writers 문제는 Courtois, Heymans, Parnas(1971)가 정식화한 고전적 동기화 문제입니다. 공유 자원에 대해 읽기 작업(Reader)은 동시에 여럿이 수행할 수 있지만, 쓰기 작업(Writer)은 다른 모든 Reader와 Writer를 배제해야 합니다.

세 가지 변형

Linux 커널은 변형에 따라 다른 정책을 사용합니다. rwlock_t(qrwlock)는 대기 Writer가 있으면 새 Reader를 차단하는 Writer 우선 경향을 보이며, rw_semaphore는 HANDOFF 메커니즘으로 Writer에게 명시적 우선권을 부여합니다.

rwlock_t vs rw_semaphore vs percpu_rw_semaphore

Linux 커널은 세 가지 Reader-Writer 동기화 프리미티브를 제공합니다. 각각 사용 가능한 컨텍스트와 성능 특성이 다릅니다.

rwlock_t 내부 구조 (qrwlock)

Linux 커널 v4.0 이후 rwlock_t는 qrwlock(queued rwlock)으로 구현됩니다. 핵심 자료구조는 include/asm-generic/qrwlock_types.h에 정의되어 있습니다.

/* include/asm-generic/qrwlock_types.h */
typedef struct qrwlock {
    union {
        atomic_t    cnts;       /* 32비트: reader count + writer bits */
        struct {
#ifdef __LITTLE_ENDIAN
            u8      wlocked;    /* Writer locked 바이트 */
            u8      __lstate[3];
#else
            u8      __lstate[3];
            u8      wlocked;
#endif
        };
    };
    arch_spinlock_t wait_lock; /* Writer 대기 직렬화용 qspinlock */
} arch_rwlock_t;

cnts 필드 비트 레이아웃

cnts는 32비트 atomic 변수로, Reader Count와 Writer 상태 비트를 하나의 워드에 인코딩합니다.

/* include/asm-generic/qrwlock.h */
#define _QW_WAITING  0x100   /* 비트 8: Writer 대기 중 */
#define _QW_LOCKED   0x0ff   /* 비트 0-7: Writer locked (0xff) */
#define _QW_WMASK    0x1ff   /* 비트 0-8: Writer 전체 마스크 */
#define _QR_SHIFT    9       /* Reader count 시작 비트 */
#define _QR_BIAS     (1U << _QR_SHIFT)  /* 0x200: Reader 1 증가분 */

wait_lock은 내부적으로 qspinlock(arch_spinlock_t)이며, 여러 Writer가 동시에 진입할 때 직렬화(Serialization)합니다. 실제 Writer 간 경쟁은 이 spinlock에서 발생하며, Reader는 wait_lock 없이 cnts의 atomic 연산만으로 진입합니다.

rwlock_t API 전체 레퍼런스

/* 기본 사용 예시 */
static DEFINE_RWLOCK(my_rwlock);

/* Reader 경로 — 동시 진입 가능 */
void read_data(void)
{
    read_lock(&my_rwlock);
    /* 공유 데이터 읽기... */
    read_unlock(&my_rwlock);
}

/* Writer 경로 — 배타적 진입 */
void write_data(void)
{
    write_lock(&my_rwlock);
    /* 공유 데이터 수정... */
    write_unlock(&my_rwlock);
}

trylock 구현 분석

read_trylock()과 write_trylock()은 락 획득에 실패해도 대기하지 않고 즉시 반환합니다. 인터럽트 핸들러나 데드락 회피 경로에서 필수적입니다.

queued_read_trylock

/* include/asm-generic/qrwlock.h */
static inline int queued_read_trylock(struct qrwlock *lock)
{
    int cnts;

    cnts = atomic_read(&lock->cnts);
    /* Writer가 있으면(locked 또는 waiting) 즉시 실패 */
    if (cnts & _QW_WMASK)
        return 0;

    /* Writer 없음 → Reader count 증가 시도
     * atomic_add_return이 아닌 cmpxchg 사용:
     * → 읽은 시점과 증가 시점 사이에 Writer가 진입하면 실패
     * → 실패 시 재시도하지 않고 즉시 0 반환 */
    cnts = (u32)atomic_add_return_acquire(_QR_BIAS, &lock->cnts);
    if (likely(!(cnts & _QW_WMASK)))
        return 1;  /* 성공 */

    /* atomic_add 이후 Writer가 발견됨 → 복원 */
    atomic_sub(_QR_BIAS, &lock->cnts);
    return 0;   /* 실패 */
}

/*
 * read_trylock vs read_lock 차이:
 *
 * read_lock():
 *   atomic_add → Writer 확인 → 있으면 slowpath (wait_lock에서 spin)
 *   → 반드시 락 획득 후 반환
 *
 * read_trylock():
 *   atomic_read → Writer 확인 → 있으면 즉시 0 반환
 *   → atomic_add → 다시 확인 → Writer 발견 시 복원 후 0 반환
 *   → slowpath 없음, 절대 대기하지 않음
 *
 * 반환값: 1 = 성공 (락 획득), 0 = 실패 (락 미획득)
 */

queued_write_trylock

/* include/asm-generic/qrwlock.h */
static inline int queued_write_trylock(struct qrwlock *lock)
{
    int cnts;

    cnts = atomic_read(&lock->cnts);
    /* cnts가 0이 아니면 (Reader든 Writer든) 즉시 실패 */
    if (cnts)
        return 0;

    /* cnts == 0 (아무도 없음) → cmpxchg로 _QW_LOCKED 설정 시도
     * cmpxchg가 실패하면 (경쟁에서 짐) 재시도 없이 0 반환
     *
     * write_lock()과의 차이:
     *   write_lock(): cmpxchg 실패 → slowpath (wait_lock spin + drain)
     *   write_trylock(): cmpxchg 실패 → 즉시 0 반환
     */
    return atomic_cmpxchg_acquire(&lock->cnts, 0,
        _QW_LOCKED) == 0;
}

/*
 * write_trylock의 조건이 read_trylock보다 엄격한 이유:
 *   read_trylock:  Writer만 없으면 성공 (Reader 여럿 공존 가능)
 *   write_trylock: cnts == 0이어야 성공 (Reader도 Writer도 없어야)
 *
 * 전형적 사용 패턴:
 *   if (write_trylock(&lock)) {
 *       // 배타적 수정...
 *       write_unlock(&lock);
 *   } else {
 *       // 대안 경로: 나중에 재시도 또는 다른 전략
 *   }
 */

unlock 내부 구현

read_unlock()과 write_unlock()은 각각 다른 메커니즘으로 구현됩니다. Reader는 atomic 감소, Writer는 바이트 스토어만으로 해제합니다.

queued_read_unlock 구현

/* include/asm-generic/qrwlock.h */
static inline void queued_read_unlock(struct qrwlock *lock)
{
    /* cnts에서 _QR_BIAS (0x200) 감소 — release 의미론
     *
     * release 의미론:
     *   임계 영역 내의 모든 메모리 접근이 이 연산 이전에 완료
     *   → Reader가 읽은 데이터가 unlock 이후에도 유효
     *
     * 아키텍처별 구현:
     *   x86:    LOCK XADD (암묵적 full barrier)
     *   ARM64:  LDXR + STLXR (STLXR이 release)
     *           또는 LSE: LDADDL (atomic add + release)
     *   RISC-V: amoadd.w.rl (.rl이 release ordering)
     *
     * 마지막 Reader가 나가면 cnts의 상위 23비트가 0이 됨
     * → Writer가 drain 대기 중이면 atomic_cond_read가 감지
     */
    atomic_sub_return_release(_QR_BIAS, &lock->cnts);
}

/*
 * Reader unlock이 Writer를 깨우는 메커니즘:
 *
 * 시나리오: Writer가 queued_write_lock_slowpath에서 drain 대기 중
 *
 * Writer: atomic_cond_read_acquire(&cnts, VAL == _QW_WAITING)
 *         → cnts를 반복 읽으며 reader count가 0이 될 때까지 spin
 *
 * 마지막 Reader: atomic_sub(_QR_BIAS)
 *         → cnts = _QW_WAITING (0x100)
 *         → Writer의 조건 VAL == _QW_WAITING이 참이 됨
 *         → ARM64: STLXR이 exclusive monitor 클리어 → WFE 해제
 *         → x86: LOCK XADD가 캐시라인 변경 → PAUSE 루프 탈출
 *
 * 명시적 wake-up 호출 없음 — atomic 연산의 캐시 일관성이 암묵적 알림
 */

queued_write_unlock 구현

/* include/asm-generic/qrwlock.h */
static inline void queued_write_unlock(struct qrwlock *lock)
{
    /* wlocked 바이트를 0으로 설정 — release 의미론
     *
     * 핵심: 32비트 atomic 연산이 아닌 바이트 스토어 사용!
     *
     * 왜 바이트 스토어로 충분한가:
     *   wlocked는 cnts union의 첫 바이트 (Little-Endian)
     *   Writer는 wlocked = 0xff로 설정하여 락을 보유
     *   wlocked = 0으로 설정하면 _QW_LOCKED 비트 전체 클리어
     *   → Reader count(상위 23비트)는 건드리지 않음
     *   → atomic RMW 불필요 → 더 효율적
     *
     * 아키텍처별 구현:
     *   x86:    MOV BYTE [lock], 0
     *           (TSO가 release 보장 → 배리어 불필요)
     *   ARM64:  STLRB wzr, [lock]
     *           (Store-Release Byte — 명시적 release)
     *   RISC-V: fence rw,w + sb zero, (lock)
     *           (fence가 release, sb가 바이트 스토어)
     */
    smp_store_release(&lock->wlocked, 0);
}

/*
 * Writer unlock 후 대기자 처리:
 *
 * 1. Reader가 slow path에서 대기 중인 경우:
 *    → atomic_cond_read_acquire(&cnts, !(VAL & _QW_LOCKED))
 *    → wlocked = 0이 되면 조건 성립 → Reader 진입
 *
 * 2. 다른 Writer가 wait_lock에서 대기 중인 경우:
 *    → wait_lock은 이미 현재 Writer가 slowpath에서 해제했음
 *    → 다음 Writer가 wait_lock 획득 → cnts 확인 → 진입 시도
 *
 * 3. Reader와 Writer 모두 대기:
 *    → wait_lock을 먼저 잡는 쪽이 진입
 *    → Reader: _QW_LOCKED 해제 확인 후 진입
 *    → Writer: cnts == 0 확인 후 진입 (Reader가 먼저 들어가면 drain 대기)
 */

IRQ 변형 내부 매핑

read_lock_bh(), read_lock_irq(), write_lock_irqsave() 등의 IRQ 변형은 실제로 인터럽트/softirq 제어 + 기본 lock/unlock의 조합입니다. 내부 매핑 관계를 정리합니다.

/* include/linux/rwlock.h — IRQ 변형 매크로 정의 */

/* ■ BH (Bottom Half / softirq) 변형 */
#define read_lock_bh(lock)     \
    do { local_bh_disable(); read_lock(lock); } while (0)
#define read_unlock_bh(lock)   \
    do { read_unlock(lock); local_bh_enable(); } while (0)
#define write_lock_bh(lock)    \
    do { local_bh_disable(); write_lock(lock); } while (0)
#define write_unlock_bh(lock)  \
    do { write_unlock(lock); local_bh_enable(); } while (0)

/* ■ IRQ 변형 (인터럽트 비활성화) */
#define read_lock_irq(lock)    \
    do { local_irq_disable(); read_lock(lock); } while (0)
#define read_unlock_irq(lock)  \
    do { read_unlock(lock); local_irq_enable(); } while (0)
#define write_lock_irq(lock)   \
    do { local_irq_disable(); write_lock(lock); } while (0)
#define write_unlock_irq(lock) \
    do { write_unlock(lock); local_irq_enable(); } while (0)

/* ■ IRQSAVE 변형 (인터럽트 상태 저장/복원) */
#define read_lock_irqsave(lock, flags)   \
    do { local_irq_save(flags); read_lock(lock); } while (0)
#define read_unlock_irqrestore(lock, flags) \
    do { read_unlock(lock); local_irq_restore(flags); } while (0)
#define write_lock_irqsave(lock, flags)  \
    do { local_irq_save(flags); write_lock(lock); } while (0)
#define write_unlock_irqrestore(lock, flags) \
    do { write_unlock(lock); local_irq_restore(flags); } while (0)

IRQ 변형 선택 기준

/*
 * IRQ 변형 선택의 핵심 규칙:
 *
 * 같은 rwlock을 인터럽트 핸들러에서도 사용한다면,
 * 프로세스 컨텍스트에서는 반드시 IRQ를 비활성화해야 합니다.
 *
 * 예시: 네트워크 드라이버에서 통계(Statistics) 보호
 *
 * 프로세스 컨텍스트 (ethtool 통계 읽기):
 *   read_lock_bh(&dev_stats_lock);  // softirq 비활성화
 *   stats->rx_packets = ...;
 *   read_unlock_bh(&dev_stats_lock);
 *
 * NAPI softirq (패킷 수신):
 *   write_lock(&dev_stats_lock);     // 이미 softirq 컨텍스트
 *   stats->rx_packets++;
 *   write_unlock(&dev_stats_lock);
 *
 * local_bh_disable()가 필요한 이유:
 *   프로세스 컨텍스트에서 read_lock() 보유 중
 *   → softirq 발생 → write_lock() 시도
 *   → Reader가 같은 CPU에서 보유 중이므로 drain 불가
 *   → 데드락!
 */

초기화 매크로 내부

/* include/linux/rwlock_types.h */
#define __RW_LOCK_UNLOCKED(lockname)  \
    (rwlock_t) {                      \
        .raw_lock = __ARCH_RW_LOCK_UNLOCKED, \
        RW_DEP_MAP_INIT(lockname)     \
    }

#define DEFINE_RWLOCK(x)  \
    rwlock_t x = __RW_LOCK_UNLOCKED(x)

/* 동적 초기화 — lockdep 키 자동 생성 */
#define rwlock_init(lock)  \
    do {                   \
        static struct lock_class_key __key;  \
        __rwlock_init((lock), #lock, &__key); \
    } while (0)

/* kernel/locking/spinlock_debug.c */
void __rwlock_init(rwlock_t *lock, const char *name,
                    struct lock_class_key *key)
{
    /*
     * qrwlock 초기화:
     *   cnts = 0 (FREE 상태)
     *   wait_lock = UNLOCKED (qspinlock 초기)
     *   lockdep dep_map 초기화
     *
     * __ARCH_RW_LOCK_UNLOCKED:
     *   x86:    { .cnts = ATOMIC_INIT(0), .wait_lock = ... }
     *   ARM64:  동일
     *   RISC-V: 동일
     *
     * lockdep 키:
     *   DEFINE_RWLOCK은 정적 → 변수 이름으로 키 생성
     *   rwlock_init은 동적 → __key가 static으로 고유성 보장
     *   같은 코드 위치에서 생성된 모든 rwlock은 같은 클래스
     */
    lock->raw_lock = (arch_rwlock_t)__ARCH_RW_LOCK_UNLOCKED;
    lockdep_init_map(&lock->dep_map, name, key, 0);
}

qrwlock 내부: cnts + wait_lock

qrwlock의 핵심 설계는 Reader는 cnts atomic 연산만으로 fast path를 처리하고, Writer는 wait_lock(qspinlock)으로 직렬화한 후 cnts를 조작하는 이중 구조입니다.

/* include/asm-generic/qrwlock.h — queued_read_lock() */
static inline void queued_read_lock(struct qrwlock *lock)
{
    int cnts;

    cnts = atomic_add_return_acquire(_QR_BIAS, &lock->cnts);
    if (likely(!(cnts & _QW_WMASK)))
        return;  /* Fast path: Writer 없음, 즉시 진입 */

    /* Slow path: Writer가 있으면 cnts 복원 후 대기 */
    queued_read_lock_slowpath(lock);
}

/* queued_write_lock() */
static inline void queued_write_lock(struct qrwlock *lock)
{
    if (atomic_cmpxchg_acquire(&lock->cnts, 0, _QW_LOCKED) == 0)
        return;  /* Fast path: 아무도 없으면 즉시 획득 */

    queued_write_lock_slowpath(lock);
}

Reader Fast Path: atomic_add

Reader의 fast path는 단 하나의 atomic 연산으로 구현됩니다. atomic_add_return_acquire(_QR_BIAS, &cnts)를 수행한 후, 결과의 하위 9비트(Writer 영역)가 0이면 즉시 진입합니다.

/* Reader fast path의 핵심 */
cnts = atomic_add_return_acquire(_QR_BIAS, &lock->cnts);
if (likely(!(cnts & _QW_WMASK)))
    return;  /* Writer 없음 → 진입 (acquire 의미론 보장) */

/*
 * _QW_WMASK = 0x1ff (비트 8:0)
 * Writer가 locked(0xff) 또는 waiting(0x100)이면 이 조건 실패
 * → slow path로 진입
 *
 * 아키텍처별 구현:
 *   x86:   LOCK XADD → XADD 결과 확인
 *   ARM64: LDAXR/STXR + DMB ISH (acquire)
 *   RISC-V: amoadd.w.aq
 */

이 설계의 핵심 장점은 Writer가 없는 일반적인 경우 Reader 간 경합(Contention)이 캐시(Cache)라인 하나에서만 발생한다는 것입니다. 다만 이 캐시라인이 모든 CPU에서 공유되므로, CPU 수가 많아질수록 atomic_add의 캐시 일관성(Cache Coherency) 트래픽이 성능 병목(Bottleneck)이 됩니다. 이것이 percpu_rw_semaphore가 필요한 이유입니다.

Reader Slow Path

/* kernel/locking/qrwlock.c — queued_read_lock_slowpath() 단순화 */
void queued_read_lock_slowpath(struct qrwlock *lock)
{
    /* 1. 먼저 추가한 reader count를 되돌림 */
    atomic_sub(_QR_BIAS, &lock->cnts);

    /* 2. wait_lock 획득하여 Reader도 직렬화 */
    arch_spin_lock(&lock->wait_lock);

    /* 3. Writer의 locked 비트가 해제될 때까지 spin */
    atomic_cond_read_acquire(&lock->cnts, !(VAL & _QW_LOCKED));

    /* 4. Reader count 다시 증가 + wait_lock 해제 */
    atomic_add(_QR_BIAS, &lock->cnts);
    arch_spin_unlock(&lock->wait_lock);
}

Writer 경로: wait_lock + reader drain

Writer는 Reader보다 복잡한 3단계 과정을 거칩니다.

/* kernel/locking/qrwlock.c — queued_write_lock_slowpath() 단순화 */
void queued_write_lock_slowpath(struct qrwlock *lock)
{
    /* ① wait_lock 획득 — Writer 간 직렬화 */
    arch_spin_lock(&lock->wait_lock);

    /* ② Reader가 없으면 즉시 locked 설정 시도 */
    if (!atomic_read(&lock->cnts) &&
        (atomic_cmpxchg_acquire(&lock->cnts, 0, _QW_LOCKED) == 0))
        goto unlock;

    /* ③ _QW_WAITING 비트 설정 → 새 Reader의 fast path 차단 */
    atomic_or(_QW_WAITING, &lock->cnts);

    /* ④ 기존 Reader들이 모두 나갈 때까지 spin */
    do {
        atomic_cond_read_acquire(&lock->cnts,
            VAL == _QW_WAITING);
    } while (0);

    /* ⑤ _QW_WAITING → _QW_LOCKED로 전환 */
    atomic_sub(_QW_WAITING, &lock->cnts);
    smp_store_release(&lock->wlocked, 1);

unlock:
    arch_spin_unlock(&lock->wait_lock);
}

rw_semaphore 구조체(Struct) 분석

rw_semaphore는 sleeping lock으로, mutex와 유사한 대기 큐 기반 구조를 가집니다. include/linux/rwsem.h에 정의되어 있습니다.

/* include/linux/rwsem.h */
struct rw_semaphore {
    atomic_long_t       count;      /* 64비트: reader count + flags */
    atomic_long_t       owner;      /* Writer owner + flags */
    struct optimistic_spin_queue osq; /* Optimistic Spinning MCS 큐 */
    raw_spinlock_t      wait_lock;  /* 대기 큐 보호 */
    struct list_head    wait_list;  /* rwsem_waiter 리스트 */
};

count 필드 인코딩

/* kernel/locking/rwsem.c */
#define RWSEM_WRITER_LOCKED   (1UL << 0)  /* 비트 0: Writer 보유 */
#define RWSEM_FLAG_WAITERS    (1UL << 1)  /* 비트 1: 대기자 존재 */
#define RWSEM_FLAG_HANDOFF    (1UL << 2)  /* 비트 2: HANDOFF 활성 */
#define RWSEM_READER_BIAS     (1UL << 8)  /* Reader 1 증가분 */
#define RWSEM_READER_MASK     (~(RWSEM_READER_BIAS - 1))

/*
 * count 값 해석:
 *   0x000          → FREE
 *   0x001          → Writer LOCKED
 *   0x100          → 1 Reader
 *   0x300          → 3 Readers
 *   0x003          → Writer LOCKED + WAITERS 존재
 *   0x007          → Writer LOCKED + WAITERS + HANDOFF
 */

rw_semaphore API 레퍼런스

/* rw_semaphore 사용 예시: VFS mmap_lock 패턴 */
struct mm_struct *mm = current->mm;

/* 페이지 폴트 핸들러 — Reader 경로 */
mmap_read_lock(mm);           /* down_read(&mm->mmap_lock) */
vma = find_vma(mm, address);
/* ... VMA 탐색 ... */
mmap_read_unlock(mm);         /* up_read(&mm->mmap_lock) */

/* mmap/munmap 시스템 콜 — Writer 경로 */
mmap_write_lock(mm);          /* down_write(&mm->mmap_lock) */
/* ... VMA 생성/삭제/분할 ... */
mmap_write_unlock(mm);        /* up_write(&mm->mmap_lock) */

rwsem Fast Path 인라인 구현

down_read(), up_read(), down_write(), up_write()의 fast path는 인라인 함수로 구현되어 대부분의 경우 단일 atomic 연산으로 완료됩니다. 경합이 없을 때의 오버헤드를 최소화하는 핵심 코드입니다.

down_read Fast Path

/* kernel/locking/rwsem.c */
static inline void __down_read(struct rw_semaphore *sem)
{
    long tmp;

    /* count에 RWSEM_READER_BIAS (0x100) 추가 — acquire 의미론
     *
     * 결과 분석:
     *   하위 3비트(WRITER_LOCKED | WAITERS | HANDOFF)가 0이면
     *   → Writer 없고 대기자 없음 → 즉시 Reader 진입!
     *
     * 하위 3비트가 0이 아닌 경우:
     *   bit 0 (WRITER_LOCKED): Writer 보유 중 → slowpath
     *   bit 1 (WAITERS): 대기자 존재 → slowpath (공정성)
     *   bit 2 (HANDOFF): HANDOFF 활성 → slowpath
     */
    tmp = atomic_long_fetch_add_acquire(
        RWSEM_READER_BIAS, &sem->count);

    if (unlikely(tmp & RWSEM_READ_FAILED_MASK))
        rwsem_down_read_slowpath(sem, TASK_UNINTERRUPTIBLE);
}

/*
 * RWSEM_READ_FAILED_MASK:
 *   RWSEM_WRITER_LOCKED | RWSEM_FLAG_WAITERS | RWSEM_FLAG_HANDOFF
 *   = 0x7 (하위 3비트)
 *
 * 왜 WAITERS 비트도 확인하는가?
 *   대기 중인 Writer가 있는데 새 Reader가 계속 진입하면
 *   Writer starvation 발생 → 대기자가 있으면 slowpath로 보내
 *   대기 큐에서 공정하게 순서 대기
 *
 * down_read_interruptible / down_read_killable:
 *   동일한 fast path, slowpath에서 TASK_INTERRUPTIBLE /
 *   TASK_KILLABLE로 슬립하여 시그널 수신 시 -EINTR 반환
 */

/* down_read_trylock — 비차단 시도 */
static inline int __down_read_trylock(struct rw_semaphore *sem)
{
    long tmp;

    tmp = atomic_long_read(&sem->count);
    while (!(tmp & RWSEM_READ_FAILED_MASK)) {
        /* Writer/대기자 없음 → READER_BIAS 추가 시도 */
        if (atomic_long_try_cmpxchg_acquire(
                &sem->count, &tmp,
                tmp + RWSEM_READER_BIAS)) {
            rwsem_set_reader_owned(sem);
            return 1;
        }
    }
    return 0;
}

/*
 * down_read_trylock vs down_read 차이:
 *   down_read: fetch_add로 낙관적 추가 → 실패 시 slowpath (슬립)
 *   down_read_trylock: cmpxchg 루프 → 실패 시 즉시 0 반환
 *
 * cmpxchg 루프를 사용하는 이유:
 *   fetch_add는 무조건 count를 증가시키므로,
 *   실패 시 다시 빼야 함 (비효율적)
 *   cmpxchg는 조건 확인 후 원자적으로 추가하므로
 *   실패 시 복원 불필요
 */

up_read Fast Path

/* kernel/locking/rwsem.c */
static inline void __up_read(struct rw_semaphore *sem)
{
    long tmp;

    /* count에서 RWSEM_READER_BIAS 감소 — release 의미론
     *
     * 반환값 분석:
     *   결과가 음수가 아니고 하위 비트가 0이면
     *   → 다른 Reader가 있거나 아무도 없음 → 즉시 완료
     *
     *   WAITERS 비트가 설정되어 있으면
     *   → 대기 중인 Writer/Reader가 있음
     *   → 마지막 Reader라면 깨워야 함 → slowpath
     */
    tmp = atomic_long_add_return_release(
        -RWSEM_READER_BIAS, &sem->count);

    if (unlikely((tmp & (RWSEM_LOCK_MASK | RWSEM_FLAG_WAITERS))
                 == RWSEM_FLAG_WAITERS))
        rwsem_wake(sem);
}

/*
 * up_read slowpath (rwsem_wake) 진입 조건:
 *
 *   (tmp & RWSEM_LOCK_MASK) == 0  → Writer 없고 Reader count 0
 *   (tmp & RWSEM_FLAG_WAITERS) != 0  → 대기자 존재
 *
 * 즉: "마지막 Reader가 나갔고, 대기자가 있을 때"만 rwsem_wake 호출
 *
 * rwsem_wake가 하는 일:
 *   1. wait_lock 획득
 *   2. 대기 큐 첫 번째 waiter 확인
 *   3. Writer이면 → 해당 Writer 깨움 (HANDOFF일 수 있음)
 *   4. Reader이면 → 연속된 Reader들을 모두 깨움
 *   5. wait_lock 해제
 */

down_write Fast Path

/* kernel/locking/rwsem.c */
static inline int __down_write_common(struct rw_semaphore *sem,
                                      int state)
{
    /* count가 0이면 (아무도 없음) WRITER_LOCKED로 cmpxchg
     *
     * 성공: count = RWSEM_WRITER_LOCKED (0x1) → 즉시 획득
     * 실패: Reader가 있거나 다른 Writer가 있음 → slowpath
     */
    if (unlikely(!atomic_long_try_cmpxchg_acquire(
            &sem->count, 0, RWSEM_WRITER_LOCKED)))
        return rwsem_down_write_slowpath(sem, state);

    /* fast path 성공: owner 설정 */
    rwsem_set_owner(sem);
    return 0;
}

/*
 * down_write 변형들의 fast path는 모두 동일:
 *   down_write(sem)          → state = TASK_UNINTERRUPTIBLE
 *   down_write_killable(sem) → state = TASK_KILLABLE
 *   down_write_trylock(sem)  → slowpath 없이 즉시 0 반환
 *
 * rwsem_set_owner(sem):
 *   atomic_long_set(&sem->owner, (long)current)
 *   → optimistic spinning에서 owner->on_cpu 확인에 사용
 *   → PREEMPT_RT에서 PI(Priority Inheritance) chain에 사용
 */

up_write Fast Path

/* kernel/locking/rwsem.c */
static inline void __up_write(struct rw_semaphore *sem)
{
    long tmp;

    /* owner 클리어 */
    rwsem_clear_owner(sem);

    /* count에서 WRITER_LOCKED 제거 — release 의미론
     *
     * 반환값 분석:
     *   결과가 정확히 0이면
     *   → 대기자 없음 → 즉시 완료
     *
     *   WAITERS 비트가 남아 있으면
     *   → 대기자 깨우기 필요 → rwsem_wake
     */
    tmp = atomic_long_fetch_add_release(
        -RWSEM_WRITER_LOCKED, &sem->count);

    if (unlikely(tmp & RWSEM_FLAG_WAITERS))
        rwsem_wake(sem);
}

/*
 * up_write에서 rwsem_wake 호출 시:
 *
 * 대기 큐 첫 번째가 Writer이면:
 *   → 해당 Writer 하나만 깨움
 *   → HANDOFF가 설정되어 있으면 해당 Writer에게 직접 전달
 *
 * 대기 큐 첫 번째가 Reader이면:
 *   → 연속된 모든 Reader를 한꺼번에 깨움 (batch wakeup)
 *   → 중간에 Writer가 있으면 거기서 멈춤
 *   → 예: [R, R, R, W, R] → R 3개만 깨움, W는 대기 유지
 */

struct rwsem_waiter와 대기 큐 관리

rwsem_waiter 구조체는 대기 큐의 각 항목을 표현하며, HANDOFF와 타임아웃(Timeout) 관리의 핵심입니다.

/* kernel/locking/rwsem.c */
struct rwsem_waiter {
    struct list_head    list;      /* wait_list 연결 */
    struct task_struct  *task;     /* 대기 중인 태스크 */
    enum rwsem_waiter_type type;   /* READER 또는 WRITER */
    unsigned long       timeout;   /* HANDOFF 타임아웃 시각 */
    bool                handoff_set; /* HANDOFF 플래그 설정 여부 */
};

enum rwsem_waiter_type {
    RWSEM_WAITING_FOR_WRITE,
    RWSEM_WAITING_FOR_READ,
};

/*
 * 대기 큐의 구조 예시:
 *
 * wait_list → [W1 (first, handoff_set=true)]
 *           → [R2]
 *           → [R3]
 *           → [W4]
 *           → [R5]
 *
 * W1이 깨어나면:
 *   HANDOFF가 설정되어 있으므로 W1만 락 획득 가능
 *   다른 optimistic spinner는 try_write_lock에서 실패
 *
 * 현재 Writer가 해제하면:
 *   rwsem_wake → W1을 깨움 → W1이 락 획득
 *   W1이 해제하면 → R2, R3를 한꺼번에 깨움 (W4에서 멈춤)
 *   R2, R3 모두 해제하면 → W4를 깨움
 *   W4가 해제하면 → R5를 깨움
 */

/* RWSEM_WAIT_TIMEOUT — HANDOFF 활성화 시점 */
#define RWSEM_WAIT_TIMEOUT  (4 * HZ / 1000)  /* ~4ms (4 jiffies @ HZ=1000) */
/*
 * 4ms는 대략적 가이드라인:
 *   HZ=1000 → 4 jiffies = 4ms
 *   HZ=250  → 1 jiffy = 4ms
 *   HZ=100  → 0 jiffies → 최소 1 jiffy = 10ms
 *
 * 이 시간이 지나도 락을 얻지 못하면 HANDOFF 설정
 * → optimistic spinner 차단
 * → 첫 번째 대기자에게 우선 전달
 */

rwsem_mark_wake: 대기자 깨우기 로직

/* kernel/locking/rwsem.c — 단순화 */
static void rwsem_mark_wake(struct rw_semaphore *sem,
    enum rwsem_wake_type wake_type,
    struct wake_q_head *wake_q)
{
    struct rwsem_waiter *waiter, *tmp;
    long oldcount, woken = 0, adjustment = 0;

    lockdep_assert_held(&sem->wait_lock);
    waiter = rwsem_first_waiter(sem);

    /* ■ 첫 번째 대기자가 Writer인 경우 */
    if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
        if (wake_type == RWSEM_WAKE_ANY) {
            /* Writer를 직접 깨움
             * → Writer가 rwsem_try_write_lock()으로 획득 시도
             * → HANDOFF 설정 시 이 Writer만 성공 가능 */
            wake_q_add(wake_q, waiter->task);
        }
        return;
    }

    /* ■ 첫 번째 대기자가 Reader인 경우
     *    → 연속된 Reader를 모두 깨움 (batch wakeup) */
    list_for_each_entry_safe(waiter, tmp,
        &sem->wait_list, list) {

        /* Writer를 만나면 멈춤 */
        if (waiter->type == RWSEM_WAITING_FOR_WRITE)
            break;

        woken++;
        list_del(&waiter->list);

        /*
         * waiter->task = NULL로 설정하여 깨움 알림
         * → smp_store_release: 임계 영역 데이터가 가시적
         * → 깨어난 Reader가 schedule()에서 복귀 시
         *   smp_load_acquire(&waiter.task)로 NULL 관찰
         */
        smp_store_release(&waiter->task, NULL);
        wake_q_add(wake_q, waiter->task);
    }

    /* Reader 수만큼 count 조정
     * (이미 slowpath에서 READER_BIAS를 추가했으므로 추가 조정) */
    adjustment = woken * RWSEM_READER_BIAS;
    if (list_empty(&sem->wait_list))
        adjustment -= RWSEM_FLAG_WAITERS;  /* 대기자 없으면 플래그 제거 */

    if (adjustment)
        atomic_long_add(adjustment, &sem->count);

    /* owner를 READER_OWNED로 설정 */
    rwsem_set_reader_owned(sem);
}

/*
 * rwsem_wake_type:
 *   RWSEM_WAKE_ANY      — Reader 또는 Writer 깨움 (up_read/up_write)
 *   RWSEM_WAKE_READERS  — Reader만 깨움 (downgrade_write 시)
 *   RWSEM_WAKE_READ_OWNED — Reader 이미 소유, 추가 Reader 깨움
 *
 * wake_q:
 *   실제 wake_up_process() 호출을 지연시키는 큐
 *   → wait_lock 보유 중에 wake_up 하면 데드락 위험
 *   → wake_q에 모아놓고 wait_lock 해제 후 한꺼번에 깨움
 *   → wake_up_q(wake_q)로 일괄 처리
 */

downgrade_write 구현 상세

/* kernel/locking/rwsem.c */
void downgrade_write(struct rw_semaphore *sem)
{
    long tmp;

    /*
     * count 원자적 변환:
     *   -RWSEM_WRITER_LOCKED + RWSEM_READER_BIAS
     *   = -1 + 0x100 = 0xFF (64비트에서)
     *
     * 이 단일 atomic 연산으로:
     *   1. Writer 비트 제거
     *   2. Reader 카운트 1 추가
     *   → Writer에서 Reader로 원자적 전환
     */
    tmp = atomic_long_fetch_add_release(
        -RWSEM_WRITER_LOCKED + RWSEM_READER_BIAS,
        &sem->count);

    /* owner를 READER_OWNED로 변경 */
    rwsem_set_reader_owned(sem);

    /* 대기 중인 Reader가 있으면 깨움 */
    if (tmp & RWSEM_FLAG_WAITERS)
        rwsem_downgrade_wake(sem);
}

/*
 * rwsem_downgrade_wake:
 *   RWSEM_WAKE_READ_OWNED 타입으로 rwsem_mark_wake 호출
 *   → 대기 큐의 연속 Reader만 깨움 (Writer는 건너뜀)
 *   → downgrade 후 현재 태스크가 Reader로 계속 보유하므로
 *     Writer는 깨워도 lock을 얻지 못함
 *
 * 전형적 사용 사례 — VFS rename:
 *   down_write(parent_dir->i_rwsem);  // 배타적 디렉터리 수정
 *   // ... rename 수행 ...
 *   downgrade_write(parent_dir->i_rwsem);  // Reader로 전환
 *   // ... 수정된 디렉터리 내용 기반으로 추가 조회 ...
 *   up_read(parent_dir->i_rwsem);
 */

rwsem Optimistic Spinning

rw_semaphore는 mutex와 마찬가지로 Optimistic Spinning(적극적 스피닝)을 지원합니다. Writer가 lock을 보유하고 있지만 해당 task가 CPU에서 실행 중(owner->on_cpu)이면, 슬립하지 않고 스피닝하며 기다립니다.

/* kernel/locking/rwsem.c — rwsem_optimistic_spin() 핵심 로직 */
static bool rwsem_optimistic_spin(struct rw_semaphore *sem,
                                    struct rwsem_waiter *waiter)
{
    /* 1. osq_lock으로 스피너 큐 진입 (MCS 기반) */
    if (!osq_lock(&sem->osq))
        goto done;

    for (;;) {
        enum owner_state owner_state;

        /* 2. owner가 CPU에서 실행 중인지 확인 */
        owner_state = rwsem_spin_on_owner(sem);
        if (owner_state != OWNER_READER &&
            owner_state != OWNER_WRITER)
            break;  /* owner가 슬립했으면 스피닝 중단 */

        /* 3. 락 시도 */
        taken = rwsem_try_write_lock_unqueued(sem);
        if (taken)
            break;

        /* 4. 선점 필요하면 스피닝 중단 */
        if (need_resched())
            break;

        cpu_relax();
    }

    osq_unlock(&sem->osq);
done:
    return taken;
}

rwsem HANDOFF와 Writer 우선 정책

rwsem에는 HANDOFF 메커니즘이 있어 대기 시간(Latency)이 긴 첫 번째 Writer에게 우선권을 부여합니다. Optimistic Spinner가 대기 큐의 첫 번째 대기자를 건너뛰고 락을 가로채는 것을 방지합니다.

/* HANDOFF 플래그 설정 조건 */
/*
 * 1. 대기 큐의 첫 번째 waiter가 일정 횟수 이상 락 획득에 실패
 * 2. → RWSEM_FLAG_HANDOFF (bit 2) 설정
 * 3. Optimistic Spinner는 HANDOFF가 설정되면 스피닝 중단
 * 4. 락 해제 시 → 첫 번째 waiter에게 직접 HANDOFF
 */

/* kernel/locking/rwsem.c — HANDOFF 확인 */
static inline bool rwsem_try_write_lock(struct rw_semaphore *sem,
                                          struct rwsem_waiter *waiter)
{
    long count, new;

    count = atomic_long_read(&sem->count);
    do {
        bool has_handoff = !!(count & RWSEM_FLAG_HANDOFF);

        if (has_handoff) {
            /* HANDOFF가 설정되어 있으면 첫 번째 waiter만 획득 가능 */
            if (waiter != rwsem_first_waiter(sem))
                return false;
        }

        new = count | RWSEM_WRITER_LOCKED;
        new &= ~RWSEM_FLAG_HANDOFF;

        if (count & RWSEM_READER_MASK)
            return false;  /* Reader가 아직 있음 */

    } while (!atomic_long_try_cmpxchg_acquire(&sem->count,
                                                &count, new));
    return true;
}

Writer Starvation 문제와 해결

Writer Starvation은 Reader-Writer Lock의 근본적 문제입니다. Reader가 계속 진입하면 Writer는 영원히 락을 획득할 수 없습니다.

Starvation 시나리오

시간 →

CPU 0 (Writer):  [대기 .......................................]  ← Writer Starvation!
CPU 1 (Reader):  [R1 보유][해제][R3 보유][해제][R5 보유] ...
CPU 2 (Reader):  [R2 보유   ][해제][R4 보유   ][해제] ...

문제: Reader R1이 보유 중일 때 Writer가 도착하지만,
R1이 해제되기 전에 R2가 진입하고, R2가 해제되기 전에 R3가 진입...
Reader의 연속 진입으로 reader count가 0이 되는 순간이 없음

커널의 해결 메커니즘

percpu_rw_semaphore 분석

percpu_rw_semaphore는 읽기 경로의 오버헤드를 거의 0으로 만들기 위해 Per-CPU 카운터를 사용합니다. 대신 쓰기 경로는 모든 CPU의 카운터를 합산해야 하므로 매우 비쌉니다.

/* include/linux/percpu-rwsem.h */
struct percpu_rw_semaphore {
    struct rcu_sync     rss;       /* RCU synchronization state */
    unsigned int __percpu *read_count; /* Per-CPU reader 카운터 */
    struct rcuwait      writer;    /* Writer 대기 */
    wait_queue_head_t   waiters;   /* 슬로우 패스 대기 큐 */
    atomic_t            block;     /* Reader 차단 플래그 */
};

/* Reader fast path — preempt_disable + per-cpu 증가만! */
void percpu_down_read(struct percpu_rw_semaphore *sem)
{
    might_sleep();
    rwsem_acquire_read(&sem->dep_map, 0, 0, _RET_IP_);

    preempt_disable();
    /*
     * rcu_sync_is_idle()가 true이면 (Writer가 없으면)
     * Per-CPU 카운터만 증가 — 전역 atomic 연산 없음!
     */
    if (likely(rcu_sync_is_idle(&sem->rss)))
        this_cpu_inc(*sem->read_count);
    else
        __percpu_down_read(sem, false);  /* slow path */
    preempt_enable();
}

/* Writer 경로 — 매우 비쌈 */
void percpu_down_write(struct percpu_rw_semaphore *sem)
{
    /* 1. RCU sync 시작 — 이후 Reader는 slow path */
    rcu_sync_enter(&sem->rss);

    /* 2. 새 Reader 차단 */
    atomic_set(&sem->block, 1);

    /* 3. RCU grace period 대기 — 진행 중인 Reader의
     *    preempt_disable 섹션이 모두 완료될 때까지 */
    synchronize_rcu();

    /* 4. 모든 Per-CPU 카운터 합산하여 0이 될 때까지 대기 */
    rcuwait_wait_event(&sem->writer,
        readers_active_check(sem));
}

커널 내 대표적 사용처

percpu_rw_semaphore 추가 API

percpu_rw_semaphore는 기본 lock/unlock 외에도 trylock, 상태 확인, 초기화/해제 등 다양한 API를 제공합니다.

percpu_down_read_trylock 구현

/* include/linux/percpu-rwsem.h */
static inline bool percpu_down_read_trylock(
    struct percpu_rw_semaphore *sem)
{
    bool ret = true;

    preempt_disable();
    /*
     * fast path: Writer 없으면 per-cpu 카운터만 증가
     * 동일한 rcu_sync_is_idle 확인
     */
    if (likely(rcu_sync_is_idle(&sem->rss)))
        this_cpu_inc(*sem->read_count);
    else
        ret = __percpu_down_read(sem, true);  /* try=true */
    preempt_enable();

    /*
     * try=true일 때 __percpu_down_read 동작:
     *   1. this_cpu_inc → smp_mb → block 확인
     *   2. block == 0 → 성공 (true 반환)
     *   3. block == 1 → this_cpu_dec → 실패 (false 반환)
     *   → wait_event 없이 즉시 반환 (비차단)
     *
     * percpu_down_read와의 차이:
     *   percpu_down_read: try=false → block 시 wait_event 슬립
     *   percpu_down_read_trylock: try=true → block 시 즉시 false
     */
    return ret;
}

percpu_is_read_locked / percpu_is_write_locked

/* include/linux/percpu-rwsem.h */
static inline bool percpu_is_read_locked(
    struct percpu_rw_semaphore *sem)
{
    /*
     * 모든 CPU의 per-cpu read_count를 합산하여 > 0인지 확인
     *
     * 주의: 이 함수는 정확한 스냅샷을 보장하지 않음!
     *   → 합산 도중 Reader가 진입/해제될 수 있음
     *   → lockdep 어서션이나 디버깅 목적으로만 사용
     *   → 동기화 결정의 기반으로 사용하면 안 됨
     */
    return per_cpu_sum(*sem->read_count) != 0 &&
           rcu_sync_is_idle(&sem->rss);
}

static inline bool percpu_is_write_locked(
    struct percpu_rw_semaphore *sem)
{
    /*
     * 내부 rwsem의 Writer 보유 여부 확인
     * → 단일 atomic 읽기로 충분 (per-cpu 합산 불필요)
     * → lockdep 어서션 목적
     */
    return atomic_read(&sem->block);
}

/* lockdep 어서션 예시 */
void cgroup_migrate(struct task_struct *tsk)
{
    /* cgroup_threadgroup_rwsem Writer 보유 확인 */
    percpu_rwsem_assert_held(&cgroup_threadgroup_rwsem);
    /* ... 마이그레이션 수행 ... */
}

/* percpu_init_rwsem / percpu_free_rwsem */
int percpu_init_rwsem(struct percpu_rw_semaphore *sem,
                       const char *name,
                       struct lock_class_key *key)
{
    /*
     * 1. per-cpu unsigned int 할당 (alloc_percpu)
     *    → 각 CPU마다 자체 read_count 캐시라인
     *    → 할당 실패 시 -ENOMEM 반환
     *
     * 2. rcu_sync 초기화 (rcu_sync_init)
     * 3. rcuwait 초기화 (Writer 대기용)
     * 4. wait_queue 초기화 (Reader slow path 대기용)
     * 5. block = 0 (초기: Reader 차단 없음)
     * 6. 내부 rwsem 초기화 (Writer 직렬화용)
     * 7. lockdep 키 등록
     */
    sem->read_count = alloc_percpu(unsigned int);
    if (!sem->read_count)
        return -ENOMEM;

    rcu_sync_init(&sem->rss);
    rcuwait_init(&sem->writer);
    init_waitqueue_head(&sem->waiters);
    atomic_set(&sem->block, 0);
    __init_rwsem(&sem->rw_sem, name, key);
    return 0;
}

void percpu_free_rwsem(struct percpu_rw_semaphore *sem)
{
    /* rcu_sync 정리 → 진행 중인 RCU 콜백 대기 */
    rcu_sync_dtor(&sem->rss);
    /* per-cpu 메모리 해제 */
    free_percpu(sem->read_count);
    sem->read_count = NULL;
}

down_write → downgrade_write 패턴

downgrade_write()는 Writer 락을 Reader 락으로 원자적으로 전환합니다. 이 패턴은 먼저 배타적으로 데이터를 수정한 후, 수정된 데이터를 읽기만 하는 후속 작업 동안 다른 Reader의 동시 접근을 허용할 때 유용합니다.

/* downgrade_write 사용 패턴 */
down_write(&sem);

/* 배타적으로 데이터 수정 */
data->value = new_value;
list_add(&new_entry->list, &data->list);

/* Writer → Reader 전환 (대기 중인 Reader들 깨움) */
downgrade_write(&sem);

/* 이제 Reader로서 수정된 데이터를 기반으로 추가 작업 */
result = compute_with(data);

up_read(&sem);

/*
 * 내부 구현:
 *   1. count에서 WRITER_LOCKED 클리어 + READER_BIAS 추가
 *   2. 대기 큐의 Reader들을 깨움
 *   3. owner를 READER_OWNED로 변경
 *
 * 주의: down_read → upgrade_write 함수는 존재하지 않음!
 *       이를 수동 구현하면 두 Reader가 동시에 upgrade하여 데드락 발생
 */

PREEMPT_RT에서의 rwlock/rwsem

CONFIG_PREEMPT_RT 커널에서 rwlock_t는 busy-wait 대신 sleeping lock(rwbase_rt)으로 변환됩니다. 이는 인터럽트 핸들러(Handler)도 스레드화되어 슬립이 가능하기 때문입니다.

/* include/linux/rwlock_rt.h — PREEMPT_RT 정의 */
typedef struct {
    struct rwbase_rt rwbase;
    unsigned int magic;
} rwlock_t;

/* rwbase_rt 구조 */
struct rwbase_rt {
    struct rt_mutex_base rtmutex;  /* PI(Priority Inheritance) 지원 */
    atomic_t             readers;  /* Reader count */
};

/*
 * RT에서의 핵심 변화:
 *   - rwlock_t는 더 이상 busy-wait하지 않음
 *   - rt_mutex 기반이므로 PI(Priority Inheritance) 지원
 *   - read_lock()도 슬립 가능 → softirq에서 사용 시 주의
 *   - raw_rwlock은 존재하지 않음!
 *     (인터럽트에서 진짜 busy-wait이 필요하면 raw_spinlock 사용)
 */

rwbase_rt 내부 구현 상세

PREEMPT_RT 커널에서 rwlock_t는 rwbase_rt로 변환됩니다. 이 구조는 rt_mutex_base를 기반으로 하여 PI(Priority Inheritance)를 지원하는 sleeping RW lock입니다.

rwbase_rt 구조체 상세

/* kernel/locking/rwbase_rt.c */
struct rwbase_rt {
    struct rt_mutex_base rtmutex;
    /*
     * rt_mutex_base:
     *   .owner    — Writer owner (PI chain용)
     *   .wait_lock — 대기 큐 보호 spinlock
     *   .waiters  — PI-sorted 대기자 rbtree
     *
     * PI(Priority Inheritance) 동작:
     *   Writer가 락을 보유하고 있을 때,
     *   높은 우선순위 태스크가 대기하면
     *   Writer의 우선순위가 일시적으로 승격
     *   → 우선순위 역전(Priority Inversion) 방지
     */

    atomic_t readers;
    /*
     * readers 카운터:
     *   > 0  — 현재 활성 Reader 수
     *   == 0 — Reader/Writer 없음 (FREE) 또는 Writer 보유
     *
     * Non-RT qrwlock의 cnts와 유사하지만:
     *   - Writer 비트가 없음 (rtmutex.owner로 관리)
     *   - Reader는 슬립 가능 (busy-wait 아님)
     *   - atomic_add로 Reader 등록 후, rtmutex를 잠깐 잡아
     *     Writer 부재를 확인
     */
};

/*
 * PREEMPT_RT rwlock_t typedef:
 *   typedef struct {
 *       struct rwbase_rt rwbase;
 *       unsigned int     magic;   // DEBUG용 매직 넘버
 *   } rwlock_t;
 *
 * magic 필드:
 *   RWLOCK_MAGIC = 0xdeaf1eed
 *   디버그 빌드에서 초기화 안 된 rwlock 감지
 */

RT read_lock 구현

/* kernel/locking/rwbase_rt.c — 단순화 */
static int __rwbase_read_lock(struct rwbase_rt *rwb,
                               unsigned int state)
{
    struct rt_mutex_base *rtm = &rwb->rtmutex;
    int ret;

    raw_spin_lock_irq(&rtm->wait_lock);

    /*
     * ① Reader count 증가 시도
     *    Writer가 없으면 (rtm->owner == NULL) 즉시 성공
     */
    if (!rt_mutex_base_is_locked(rtm)) {
        atomic_inc(&rwb->readers);
        raw_spin_unlock_irq(&rtm->wait_lock);
        return 0;
    }

    /*
     * ② Writer 보유 중 → 대기 큐에 삽입 후 슬립
     *    PI-sorted rbtree에 삽입:
     *    → 우선순위 높은 Reader가 앞에 위치
     *    → Writer의 PI chain에 연결
     *    → Writer 우선순위가 필요 시 승격됨
     */
    ret = rt_mutex_slowlock_block(rtm, NULL, state,
                                    NULL, &waiter);

    /* ③ 깨어나면 Reader count 증가 */
    if (!ret)
        atomic_inc(&rwb->readers);

    raw_spin_unlock_irq(&rtm->wait_lock);
    return ret;
}

/*
 * Non-RT vs RT read_lock 비교:
 *
 * Non-RT (qrwlock):
 *   atomic_add_return_acquire(_QR_BIAS, &cnts)  → busy-wait
 *   → 선점 비활성화 상태에서 spin
 *   → 짧은 임계영역에 최적화
 *
 * RT (rwbase_rt):
 *   raw_spin_lock → readers++ → raw_spin_unlock  → sleeping
 *   → 선점 가능! 임계영역 중 높은 우선순위 태스크가 실행 가능
 *   → PI 지원으로 우선순위 역전 방지
 *   → 결정적 지연 시간(Deterministic Latency) 보장
 */

RT write_lock 구현

/* kernel/locking/rwbase_rt.c — 단순화 */
static int __rwbase_write_lock(struct rwbase_rt *rwb,
                                unsigned int state)
{
    struct rt_mutex_base *rtm = &rwb->rtmutex;

    /* ① rtmutex 획득 — Writer 간 직렬화 + PI 지원
     *    rt_mutex_lock은 PI chain을 통해
     *    현재 holder의 우선순위를 승격시킴
     */
    rt_mutex_slowlock(rtm, NULL, state);

    /* ② Reader drain 대기
     *    atomic_read(&rwb->readers) == 0이 될 때까지 슬립
     *
     *    Non-RT와의 핵심 차이:
     *    → Non-RT: atomic_cond_read로 busy-wait
     *    → RT: rcuwait_wait_event로 sleeping wait
     *    → 대기 중 선점 가능, CPU를 다른 태스크에 양보
     */
    rwbase_write_wait(rwb);

    return 0;
}

static void rwbase_write_wait(struct rwbase_rt *rwb)
{
    /* readers가 0이 될 때까지 sleeping wait
     * → 마지막 Reader가 read_unlock 시 깨움
     *
     * Non-RT drain과 비교:
     *   Non-RT: atomic_cond_read_acquire → PAUSE/WFE 루프
     *   RT: schedule 기반 → CPU 양보, 결정적 지연 보장
     */
    while (atomic_read(&rwb->readers))
        rcuwait_wait_event(..., !atomic_read(&rwb->readers));
}

/*
 * RT write_unlock:
 *   1. rtmutex 해제 → PI chain에서 제거
 *   2. 대기 중인 Reader/Writer 중 가장 높은 우선순위 태스크 깨움
 *   → PI-sorted이므로 가장 중요한 태스크가 먼저 실행
 *
 * RT read_unlock:
 *   1. atomic_dec(&rwb->readers)
 *   2. readers == 0이면 Writer 대기자 깨움
 *   → 마지막 Reader가 나가면 Writer에게 알림
 */

RT에서 IRQ 변형의 변환

/*
 * PREEMPT_RT에서 IRQ 변형 매핑 변화:
 *
 * ■ Non-RT:
 *   read_lock_irq(lock)  → local_irq_disable + qrwlock
 *   read_lock_bh(lock)   → local_bh_disable + qrwlock
 *
 * ■ PREEMPT_RT:
 *   read_lock_irq(lock)  → migrate_disable + rwbase_rt
 *   read_lock_bh(lock)   → migrate_disable + rwbase_rt
 *
 * 핵심 변화:
 *   - local_irq_disable → 더 이상 IRQ를 비활성화하지 않음!
 *     (IRQ는 스레드화되어 sleeping lock으로 충분)
 *   - local_bh_disable → softirq도 스레드화
 *   - migrate_disable → CPU 마이그레이션만 방지
 *     (슬립은 가능하지만 다른 CPU로 이동 불가)
 *
 * 주의: raw_spin_lock_irq/raw_spin_lock_irqsave는
 *   RT에서도 진짜 IRQ를 비활성화합니다.
 *   → rwbase_rt의 내부 wait_lock이 raw_spinlock인 이유
 *
 * 결과적으로:
 *   read_lock_irqsave(&lock, flags) — RT에서:
 *     flags는 dummy (IRQ 상태 저장 안 함)
 *     migrate_disable만 수행
 *     rwbase_rt를 통해 sleeping lock 획득
 */

실전 사용 패턴

tasklist_lock: 프로세스 목록 보호

/* kernel/fork.c — 프로세스 생성 시 Writer */
write_lock_irq(&tasklist_lock);
list_add_tail_rcu(&p->sibling, &p->real_parent->children);
list_add_tail_rcu(&p->tasks, &init_task.tasks);
write_unlock_irq(&tasklist_lock);

/* fs/proc/array.c — 프로세스 정보 읽기 시 Reader */
read_lock(&tasklist_lock);
task = pid_task(find_vpid(pid), PIDTYPE_PID);
if (task)
    get_task_struct(task);
read_unlock(&tasklist_lock);

mmap_lock: VMA 보호

/* mm/memory.c — 페이지 폴트 (Reader 경로, 매우 빈번) */
if (!mmap_read_trylock(mm)) {
    if (!(flags & FAULT_FLAG_RETRY_NOWAIT))
        mmap_read_lock(mm);
}
vma = find_vma(mm, address);
/* ... 페이지 폴트 처리 ... */
mmap_read_unlock(mm);

/* mm/mmap.c — mmap() 시스템 콜 (Writer 경로) */
mmap_write_lock(mm);
/* ... VMA 생성/병합/분할 ... */
mmap_write_unlock(mm);

superblock s_writers: 파일시스템 freeze

/* fs/super.c — 일반 I/O (Reader, 매우 빈번) */
sb_start_write(inode->i_sb);
/* ... 파일 쓰기 ... */
sb_end_write(inode->i_sb);

/* fs/super.c — 파일시스템 freeze (Writer, 매우 드묾) */
percpu_down_write(sb->s_writers.rw_sem + SB_FREEZE_WRITE - 1);
/* ... 파일시스템 freeze 처리 ... */

안티패턴과 흔한 실수

1. Writer 대기 중 Reader 재진입 데드락

/* 데드락 시나리오 */
read_lock(&lock);      /* CPU 0: Reader 획득 */
                         /* CPU 1: write_lock() 호출 → _QW_WAITING 설정 */
read_lock(&lock);      /* CPU 0: 재진입 시도 → _QW_WAITING 때문에 slow path */
                         /* → wait_lock에서 대기, CPU 1은 Reader drain 대기 */
                         /* → 데드락! */

/* 해결: lockdep이 이 패턴을 감지함 */
/* 또는 단일 read_lock 섹션으로 합치기 */

2. rwlock_t 보유 중 슬립

/* 잘못된 코드 */
read_lock(&lock);
kmalloc(size, GFP_KERNEL);  /* 슬립 가능! BUG! */
read_unlock(&lock);

/* 올바른 코드 옵션 1: GFP_ATOMIC 사용 */
read_lock(&lock);
kmalloc(size, GFP_ATOMIC);  /* 슬립 안 함 */
read_unlock(&lock);

/* 올바른 코드 옵션 2: rw_semaphore로 전환 */
down_read(&sem);
kmalloc(size, GFP_KERNEL);  /* OK — rwsem은 sleeping lock */
up_read(&sem);

3. Reader → Writer 업그레이드 시도

/* 데드락 시나리오 */
down_read(&sem);
/* ... 조건 확인 ... */
up_read(&sem);
down_write(&sem);      /* TOCTTOU: 이 사이에 다른 Writer가 진입 가능! */
/* ... 조건이 변경되었을 수 있음 ... */

/* 올바른 패턴: 처음부터 Writer로 진입 */
down_write(&sem);
if (!need_modify) {
    downgrade_write(&sem);  /* Writer → Reader 전환 (안전) */
    /* ... 읽기 작업 ... */
    up_read(&sem);
} else {
    /* ... 수정 작업 ... */
    up_write(&sem);
}

4. IRQ 변형 불일치

/* 잘못된 코드: 인터럽트 핸들러에서 같은 rwlock 사용 */

/* 프로세스 컨텍스트 */
read_lock(&lock);        /* IRQ 비활성화 안 함 */
/* ← 여기서 IRQ 발생! */

/* IRQ 핸들러 */
write_lock(&lock);       /* 데드락! Reader가 같은 CPU에서 보유 중 */

/* 올바른 코드 */
read_lock_irqsave(&lock, flags);  /* IRQ 비활성화 */
/* ... */
read_unlock_irqrestore(&lock, flags);

디버깅(Debugging)과 lockdep

lockdep은 rwlock/rwsem의 잘못된 사용을 컴파일 타임이 아닌 런타임에 동적으로 감지합니다.

관련 설정

CONFIG_PROVE_LOCKING=y     # lockdep 교착 감지 활성화
CONFIG_LOCK_STAT=y         # /proc/lock_stat 경합 통계
CONFIG_DEBUG_LOCK_ALLOC=y  # 잠금 할당 추적
CONFIG_DEBUG_RWSEMS=y      # rwsem 전용 디버깅

lockdep 어서션

/* rwsem 보유 상태 검증 */
lockdep_assert_held(&sem);           /* Reader 또는 Writer 보유 */
lockdep_assert_held_write(&sem);     /* Writer만 보유 */
lockdep_assert_held_read(&sem);      /* Reader만 보유 */
lockdep_assert_not_held(&sem);       /* 보유하지 않아야 함 */

/* rwlock_t 보유 상태 검증 */
lockdep_assert_held(&lock);          /* read 또는 write 보유 */
lockdep_assert_held_write(&lock);    /* write_lock 보유 */

lockdep 경고 메시지 해석

=====================================================
WARNING: possible recursive locking detected
-----------------------------------------------------
kworker/0:1/28 is trying to acquire lock:
ffff888100a5c0d0 (&sb->s_type->i_mutex_key#5){++++}-{3:3}

but task is already holding lock:
ffff888100a5c148 (&sb->s_type->i_mutex_key#5){++++}-{3:3}

{++++} → Reader(+) 4개 모드 모두 허용
{----} → 모든 컨텍스트에서 사용됨 (hardirq, softirq, reclaim, ...)
{3:3}  → wait_type (read:write)

lockdep에 대한 자세한 내용은 동시성 디버깅 문서를 참고하세요.

성능 특성과 비교

캐시라인 경합 분석

/* rwlock_t의 캐시라인 경합 패턴 */
/*
 * 모든 Reader가 동일한 cnts 캐시라인에 atomic_add 수행
 * → CPU 수가 증가할수록 캐시 일관성 트래픽 증가
 *
 * 32-CPU 시스템에서의 대략적 Reader 오버헤드:
 *   rwlock_t:          ~200ns (전역 atomic 경합)
 *   percpu_rw_semaphore: ~5ns  (로컬 캐시만)
 *
 * perf로 측정:
 *   perf stat -e cache-misses,cache-references \
 *     -p $(pgrep -f "rwlock_test") -- sleep 5
 *
 *   perf c2c record -p $PID -- sleep 5
 *   perf c2c report  # false sharing/true sharing 분석
 */

대안 선택: seqlock, RCU, percpu

Reader-Writer Lock은 항상 최선의 선택이 아닙니다. 많은 경우 seqlock이나 RCU가 더 나은 성능을 제공합니다.

관련 커널 설정 옵션

# /proc/lock_stat 출력 예시 (rwsem 관련)
# lock_stat 활성화:
echo 1 > /proc/lock_stat

# 출력 확인:
cat /proc/lock_stat | grep -A2 "mmap_lock"

#                 contentions   waittime-min  waittime-max  waittime-total
# mmap_lock-W:           2345       0.52         125.40          8234.50
# mmap_lock-R:            123       0.10          12.30           456.78
# -W: Writer 경합, -R: Reader 경합

qrwlock 소스 코드 심층 분석

qrwlock의 내부 구현은 kernel/locking/qrwlock.c와 include/asm-generic/qrwlock.h에 걸쳐 있으며, cnts 필드의 비트 인코딩과 atomic_cond_read_acquire를 중심으로 동작합니다. 이 섹션에서는 실제 커널 소스의 세밀한 경로를 한 줄씩 추적합니다.

cnts 필드 인코딩 심층

/* include/asm-generic/qrwlock.h */
/*
 * cnts 32비트 필드의 전체 상태 전이:
 *
 * 상태                cnts 값        의미
 * ─────────────────────────────────────────
 * FREE                0x00000000     아무도 보유하지 않음
 * 1 Reader            0x00000200     _QR_BIAS (1 << 9)
 * N Readers           N << 9         최대 ~8M readers
 * Writer LOCKED       0x000000ff     _QW_LOCKED
 * Writer WAITING      0x00000100     _QW_WAITING
 * W_WAIT + 3 Readers  0x00000700     _QW_WAITING | (3 << 9)
 * W_LOCK + 0 Readers  0x000000ff     Writer 보유 중 (Reader drain 완료)
 *
 * 핵심 불변량(invariant):
 *   - Writer LOCKED (0xff)와 Reader count > 0은 동시에 성립 불가
 *   - Writer WAITING 중에도 기존 Reader는 계속 보유 가능
 *   - Writer WAITING이 설정되면 새 Reader의 fast path 실패
 */

/* cnts 조작 헬퍼 매크로 */
#define _QW_WAITING   0x100      /* bit 8 */
#define _QW_LOCKED    0x0ff      /* bits 7:0 전부 1 → 0xff */
#define _QW_WMASK     0x1ff      /* bits 8:0 → WAITING | LOCKED */
#define _QR_SHIFT     9
#define _QR_BIAS      (1U << _QR_SHIFT)  /* 0x200 */

/* wlocked 바이트 직접 접근 — union 활용 */
/*
 * Little-endian에서 wlocked는 cnts의 바이트 0에 위치
 * → smp_store_release(&lock->wlocked, 1)로 Writer locked 설정 가능
 * → 전체 32비트 cmpxchg 없이 바이트 스토어로 충분
 * → ARM64/RISC-V에서 성능 이점 (작은 단위 스토어)
 */

queued_read_lock 상세 경로

/* include/asm-generic/qrwlock.h */
static inline void queued_read_lock(struct qrwlock *lock)
{
    int cnts;

    /* ① atomic_add_return_acquire: cnts += _QR_BIAS (0x200)
     *    acquire 의미론: 이 연산 이후의 메모리 접근이
     *    이 연산 이전으로 재배치되지 않음을 보장
     *    → 임계 영역의 읽기가 락 획득 이전으로 이동 불가 */
    cnts = atomic_add_return_acquire(_QR_BIAS, &lock->cnts);

    /* ② Writer 비트 확인: _QW_WMASK = 0x1ff
     *    하위 9비트가 0이면 Writer 없음 → fast path 성공
     *    likely() 힌트: 대부분의 경우 Writer 없음 */
    if (likely(!(cnts & _QW_WMASK)))
        return;

    /* ③ Writer 존재 → slow path
     *    먼저 추가한 reader count를 되돌려야 함 */
    queued_read_lock_slowpath(lock);
}

queued_read_lock_slowpath 전체 분석

/* kernel/locking/qrwlock.c */
void queued_read_lock_slowpath(struct qrwlock *lock)
{
    /* Step 1: 낙관적으로 추가한 reader bias를 되돌림
     *         Writer가 drain 중이므로, reader count가 높으면
     *         Writer가 더 오래 기다려야 함 → 빠르게 빼줘야 */
    atomic_sub(_QR_BIAS, &lock->cnts);

    /* Step 2: wait_lock(qspinlock) 획득
     *         → Reader끼리의 thundering herd 방지
     *         → Writer 해제 직후 모든 Reader가 동시에
     *           atomic_add를 하면 캐시라인 폭풍 발생
     *         → wait_lock이 하나씩 진입하게 직렬화 */
    arch_spin_lock(&lock->wait_lock);

    /* Step 3: atomic_cond_read_acquire — Writer locked 해제 대기
     *
     * atomic_cond_read_acquire(ptr, cond):
     *   - ptr을 반복 읽으며 cond가 참이 될 때까지 대기
     *   - x86: PAUSE 루프로 구현
     *   - ARM64: WFE(Wait For Event) + LDAXR로 구현
     *     → WFE는 CPU를 저전력 대기 상태로 전환
     *     → exclusive monitor가 해제되면 SEV로 깨움
     *   - RISC-V: fence + spin 루프
     *
     * _QW_LOCKED (0xff)가 클리어될 때까지 대기
     * _QW_WAITING(0x100)은 상관없음 — Reader는 WAITING 상태에서도
     * Writer가 실제 LOCKED가 아니면 진입 가능 */
    atomic_cond_read_acquire(&lock->cnts,
        !(VAL & _QW_LOCKED));

    /* Step 4: Writer locked 해제됨 → Reader count 다시 추가
     *         + wait_lock 해제하여 다음 대기 Reader 허용 */
    atomic_add(_QR_BIAS, &lock->cnts);
    arch_spin_unlock(&lock->wait_lock);
}

queued_write_lock_slowpath 전체 분석

/* kernel/locking/qrwlock.c */
void queued_write_lock_slowpath(struct qrwlock *lock)
{
    /* ① Writer 간 직렬화 — wait_lock(qspinlock) 획득
     *    여러 Writer가 동시에 진입하면 이 spinlock에서 대기
     *    → 한 번에 하나의 Writer만 cnts를 조작 가능 */
    arch_spin_lock(&lock->wait_lock);

    /* ② 빠른 재시도: 아무도 없으면 즉시 획득
     *    atomic_read로 먼저 확인 → cmpxchg 호출 최소화 */
    if (!atomic_read(&lock->cnts) &&
        (atomic_cmpxchg_acquire(&lock->cnts, 0,
            _QW_LOCKED) == 0))
        goto unlock;

    /* ③ _QW_WAITING 비트 설정 (bit 8)
     *    핵심 메커니즘: 이 비트가 설정되면
     *    queued_read_lock()의 fast path 조건
     *    !(cnts & _QW_WMASK)가 실패함
     *    → 새 Reader는 slow path로 강제 이동
     *    → Writer starvation 방지의 핵심 */
    atomic_or(_QW_WAITING, &lock->cnts);

    /* ④ 기존 Reader drain 대기
     *    cnts == _QW_WAITING (0x100)이 될 때까지 spin
     *    → Reader count가 0이고 Writer waiting만 남은 상태
     *
     *    atomic_cond_read_acquire 사용:
     *    - 아키텍처 최적화된 busy-wait
     *    - ARM64: WFE 사용으로 전력 절약
     *    - x86: PAUSE로 파이프라인 비움 */
    atomic_cond_read_acquire(&lock->cnts,
        VAL == _QW_WAITING);

    /* ⑤ WAITING → LOCKED 전환
     *    atomic_sub로 _QW_WAITING 제거 → cnts = 0
     *    smp_store_release로 wlocked = 1 설정
     *    → 바이트 스토어이므로 전체 cmpxchg보다 효율적
     *    → release 의미론: 이전 메모리 접근이 완료된 후 저장 */
    atomic_sub(_QW_WAITING, &lock->cnts);
    smp_store_release(&lock->wlocked, 1);

unlock:
    arch_spin_unlock(&lock->wait_lock);
}

/* queued_write_unlock — Writer 해제 */
static inline void queued_write_unlock(struct qrwlock *lock)
{
    /* wlocked 바이트를 0으로 설정 (release 의미론)
     *   → 임계 영역의 모든 스토어가 이 해제 이전에 완료
     *   → Reader의 atomic_cond_read_acquire가 이를 관찰 */
    smp_store_release(&lock->wlocked, 0);
}

atomic_cond_read_acquire 내부

/* include/linux/atomic/atomic-instrumented.h */
/*
 * atomic_cond_read_acquire(v, cond)
 *
 * v를 반복적으로 읽으며 cond가 참이 될 때까지 대기
 * VAL은 매크로 내부에서 현재 읽은 값을 참조하는 특수 변수
 *
 * 아키텍처별 구현 차이:
 *
 * ■ x86 (arch/x86/include/asm/barrier.h):
 *   do {
 *       VAL = smp_cond_load_acquire(v, cond);
 *       // → 내부적으로 READ_ONCE + cpu_relax() 루프
 *       // → cpu_relax()는 PAUSE 명령어 (rep; nop)
 *       // → 파이프라인 비우고 ~140 사이클 대기
 *   } while (0);
 *
 * ■ ARM64 (arch/arm64/include/asm/barrier.h):
 *   do {
 *       VAL = __atomic_load_n(v, __ATOMIC_RELAXED);
 *       if (cond) break;
 *       __wfe();  // Wait For Event — CPU 저전력 대기
 *       // exclusive monitor가 해당 캐시라인 변경 감지 시
 *       // SEV(Send Event)로 WFE 해제
 *   } while (1);
 *   __dmb(ishld);  // acquire 배리어
 *
 * ■ RISC-V:
 *   → fence + spin 루프 (WFE 미지원 ISA에서)
 *   → Svvptc 확장이 있으면 WRS.STO 사용 가능
 */

rwsem 소스 코드 심층 분석

rw_semaphore의 핵심 슬로우패스 구현은 kernel/locking/rwsem.c에 있으며, 약 1,500줄에 달하는 복잡한 상태 머신으로 구성됩니다. count 필드의 비트 인코딩, optimistic spinning 조건, 대기 큐 관리를 깊이 분석합니다.

count 비트 필드 상세

/* kernel/locking/rwsem.c */
#define RWSEM_WRITER_LOCKED   (1UL << 0)   /* bit 0 */
#define RWSEM_FLAG_WAITERS    (1UL << 1)   /* bit 1 */
#define RWSEM_FLAG_HANDOFF    (1UL << 2)   /* bit 2 */
#define RWSEM_READER_BIAS     (1UL << 8)   /* Reader 1 증가분 */

/*
 * count 값 인코딩 상세:
 *
 *  bits 63:8  — Reader Count (양수: 활성 reader 수)
 *  bit  2     — HANDOFF: 첫 대기자에게 직접 전달
 *  bit  1     — WAITERS: 대기 큐에 waiter 존재
 *  bit  0     — WRITER_LOCKED: Writer가 보유 중
 *
 *  특수 조합:
 *  count = RWSEM_READER_BIAS → 1 reader, 대기자 없음
 *  count = RWSEM_WRITER_LOCKED | RWSEM_FLAG_WAITERS
 *        → Writer 보유 중 + 대기자 존재
 *  count = RWSEM_WRITER_LOCKED | RWSEM_FLAG_WAITERS | RWSEM_FLAG_HANDOFF
 *        → Writer 보유 중 + 대기자 존재 + HANDOFF 활성
 *  count < 0 → Reader count 오버플로 (이론상, 실제 발생 불가)
 */

/* owner 필드 인코딩 */
#define RWSEM_READER_OWNED    (1UL << 0)
#define RWSEM_NONSPINNABLE    (1UL << 1)
/*
 * owner 포인터의 하위 2비트를 플래그로 활용 (task_struct 정렬 보장):
 *   bit 0 = READER_OWNED: Reader가 보유 중 (writer spinning 차단)
 *   bit 1 = NONSPINNABLE: optimistic spinning 하지 말 것
 *
 * Writer 보유 시: owner = current task_struct *
 * Reader 보유 시: owner = RWSEM_READER_OWNED (또는 첫 reader의 주소 | READER_OWNED)
 */

rwsem_down_read_slowpath 분석

/* kernel/locking/rwsem.c — 단순화된 down_read slowpath */
static struct rw_semaphore *
rwsem_down_read_slowpath(struct rw_semaphore *sem,
                          long count, unsigned int state)
{
    struct rwsem_waiter waiter;
    long adjustment;
    bool wake = false;

    /* ① Optimistic Spinning 시도 (Writer가 CPU에서 실행 중이면)
     *    Reader도 optimistic spin 가능 (v5.0+)
     *    조건: 대기 큐가 비어있고, owner가 CPU에서 실행 중 */
    if (rwsem_can_spin_on_owner(sem)) {
        if (rwsem_optimistic_spin(sem, NULL)) {
            /* spinning 중 lock 획득 성공! */
            return sem;
        }
    }

    /* ② waiter 구조체 초기화 */
    waiter.task = current;
    waiter.type = RWSEM_WAITING_FOR_READ;
    waiter.timeout = jiffies + RWSEM_WAIT_TIMEOUT;
    waiter.handoff_set = false;

    /* ③ wait_lock 획득 후 대기 큐에 삽입 */
    raw_spin_lock_irq(&sem->wait_lock);

    /* 대기 큐 맨 앞이 Reader이고 Writer 없으면 즉시 획득 시도 */
    if (list_empty(&sem->wait_list)) {
        /* 첫 번째 대기자 → WAITERS 플래그 설정 */
        adjustment = RWSEM_FLAG_WAITERS | RWSEM_READER_BIAS;
        count = atomic_long_add_return(adjustment, &sem->count);

        if (!(count & RWSEM_LOCK_MASK)) {
            /* Writer 없음 → 즉시 깨움 */
            raw_spin_unlock_irq(&sem->wait_lock);
            return sem;
        }
    } else {
        adjustment = RWSEM_READER_BIAS;
        atomic_long_add(adjustment, &sem->count);
    }

    /* ④ 대기 큐 삽입 (FIFO 순서) */
    list_add_tail(&waiter.list, &sem->wait_list);

    /* ⑤ 슬립 루프 */
    for (;;) {
        set_current_state(state);
        if (!smp_load_acquire(&waiter.task))
            break;  /* 깨움 받음 */
        raw_spin_unlock_irq(&sem->wait_lock);
        schedule();     /* 슬립 → 컨텍스트 스위치 */
        raw_spin_lock_irq(&sem->wait_lock);
    }

    __set_current_state(TASK_RUNNING);
    raw_spin_unlock_irq(&sem->wait_lock);
    return sem;
}

rwsem_down_write_slowpath 분석

/* kernel/locking/rwsem.c — 단순화된 down_write slowpath */
static struct rw_semaphore *
rwsem_down_write_slowpath(struct rw_semaphore *sem,
                           unsigned int state)
{
    struct rwsem_waiter waiter;

    /* ① Optimistic Spinning 시도
     *    osq_lock으로 MCS 큐에 진입하여 스피닝
     *    owner가 CPU에서 실행 중이면 스피닝 계속
     *    owner가 슬립하면 스피닝 중단 → 대기 큐로 */
    if (rwsem_can_spin_on_owner(sem) &&
        rwsem_optimistic_spin(sem, NULL))
        return sem;  /* spinning 중 획득 성공 */

    /* ② waiter 준비 */
    waiter.task = current;
    waiter.type = RWSEM_WAITING_FOR_WRITE;
    waiter.timeout = jiffies + RWSEM_WAIT_TIMEOUT;
    waiter.handoff_set = false;

    raw_spin_lock_irq(&sem->wait_lock);
    list_add_tail(&waiter.list, &sem->wait_list);

    /* WAITERS 플래그 설정 */
    rwsem_set_waiters(sem);

    /* ③ 슬립 루프 */
    for (;;) {
        if (rwsem_try_write_lock(sem, &waiter))
            break;  /* 락 획득 성공 */

        raw_spin_unlock_irq(&sem->wait_lock);

        /* ④ HANDOFF 설정 조건 확인
         *    대기 시간이 RWSEM_WAIT_TIMEOUT을 초과하면
         *    HANDOFF 플래그 설정 → optimistic spinner 차단
         *    → 첫 번째 대기자에게 직접 전달 */
        if (time_after(jiffies, waiter.timeout)) {
            if (!waiter.handoff_set) {
                atomic_long_or(RWSEM_FLAG_HANDOFF,
                    &sem->count);
                waiter.handoff_set = true;
            }
        }

        set_current_state(state);
        schedule();

        raw_spin_lock_irq(&sem->wait_lock);
    }

    __set_current_state(TASK_RUNNING);
    list_del(&waiter.list);
    raw_spin_unlock_irq(&sem->wait_lock);
    return sem;
}

Optimistic Spinning 조건 판단

/* kernel/locking/rwsem.c */
static bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)
{
    struct task_struct *owner;
    unsigned long flags;
    bool ret = true;

    /* need_resched() → 스피닝하면 안 됨 */
    if (need_resched())
        return false;

    owner = rwsem_owner_flags(sem, &flags);

    /* NONSPINNABLE 플래그 설정됨 → 스피닝 금지 */
    if (flags & RWSEM_NONSPINNABLE)
        return false;

    /* READER_OWNED → Reader가 보유 중
     *   Reader는 스케줄 아웃될 수 있으므로
     *   스피닝이 비효율적 → false */
    if (flags & RWSEM_READER_OWNED)
        return false;

    /* owner가 있고 CPU에서 실행 중 → 스피닝 가치 있음 */
    if (owner && !owner_on_cpu(owner))
        ret = false;

    return ret;
}

x86 아키텍처 구현

x86에서 qrwlock과 rwsem의 atomic 연산은 LOCK 접두사 명령어로 구현됩니다. LOCK은 버스(Bus) 잠금이 아니라 캐시 일관성 프로토콜(MESI/MESIF)을 통해 해당 캐시라인의 배타적 소유권을 보장합니다.

LOCK 접두사와 캐시 프로토콜

/* x86에서 qrwlock 핵심 연산의 어셈블리 */

/* atomic_add_return_acquire(_QR_BIAS, &cnts) →
 *
 *   LOCK XADD [cnts], $0x200
 *
 *   LOCK 접두사:
 *   1. 캐시라인을 Exclusive 상태로 전환 (MESI)
 *   2. read-modify-write를 원자적으로 수행
 *   3. 다른 코어의 읽기/쓰기를 차단하지 않음
 *      (버스 잠금이 아닌 캐시 락)
 *   4. Full memory barrier 효과 (x86 TSO에서)
 *
 *   XADD: Exchange and Add
 *   → 기존 값을 반환하면서 새 값을 저장
 *   → cmpxchg보다 효율적 (단일 명령어)
 */

/* atomic_cmpxchg_acquire(cnts, 0, _QW_LOCKED) →
 *
 *   mov eax, 0          ; expected = 0
 *   mov ecx, 0xff       ; desired = _QW_LOCKED
 *   LOCK CMPXCHG [cnts], ecx
 *   ; ZF=1이면 성공 (cnts에 0xff 저장)
 *   ; ZF=0이면 실패 (eax에 현재 cnts 값)
 */

/* smp_store_release(&lock->wlocked, 1) →
 *
 *   x86 TSO(Total Store Ordering)에서:
 *   → Store-Store 재배치가 원래 불가
 *   → 따라서 일반 MOV로 충분! (배리어 불필요)
 *   → MOV BYTE [lock+0], 1
 *
 *   cf. ARM64에서는 STLR (Store-Release) 필요
 */

PAUSE 명령어와 스핀 루프

/*
 * x86 cpu_relax() = PAUSE (rep; nop)
 *
 * PAUSE의 효과:
 * 1. 파이프라인 비움 (~140 사이클 지연)
 *    → 스핀 루프에서 명령어 낭비 감소
 * 2. 메모리 순서 위반(Memory Order Violation) 방지
 *    → speculative execution이 lock 변수를 과도하게 읽는 것 방지
 *    → MOB(Memory Order Buffer) flush 비용 감소
 * 3. Hyper-Threading에서 다른 논리 코어에 자원 양보
 *    → 스핀 중인 스레드가 파이프라인 자원을 독점하지 않음
 * 4. 전력 소비 감소 (P-state 전환 힌트)
 *
 * TPAUSE/UMWAIT (신규 프로세서):
 * → 지정된 시간까지 CPU를 C0.1/C0.2 대기 상태로 전환
 * → PAUSE보다 적극적인 전력 절약
 * → 커널은 아직 qrwlock에서 미사용 (2024 기준)
 */

/* x86 atomic_cond_read_acquire 구현 */
#define smp_cond_load_acquire(ptr, cond_expr) ({
    typeof(*ptr) VAL;
    for (;;) {
        VAL = READ_ONCE(*ptr);
        if (cond_expr)
            break;
        cpu_relax();    /* PAUSE */
    }
    VAL;
})

캐시라인 경합 패턴

/*
 * qrwlock의 x86 캐시라인 경합 분석:
 *
 * struct qrwlock은 8바이트 (cnts 4B + wait_lock 4B)
 * → 하나의 캐시라인(64B)에 완전히 수용
 *
 * Reader fast path (atomic XADD):
 *   CPU0: LOCK XADD → 캐시라인 Exclusive 획득
 *   CPU1: LOCK XADD → CPU0으로부터 캐시라인 전송 (RFO: Read For Ownership)
 *   CPU2: LOCK XADD → CPU1으로부터 캐시라인 전송
 *   ...
 *   → N개 CPU에서 O(N) RFO 트래픽
 *   → 각 RFO는 ~50-100ns (NUMA 교차 시 ~200ns+)
 *
 * 이것이 percpu_rw_semaphore가 필요한 근본적 이유:
 *   percpu: this_cpu_inc → 로컬 캐시라인만 수정 → O(1)
 *
 * perf c2c로 확인:
 *   perf c2c record -e mem-loads,mem-stores -p $PID -- sleep 5
 *   perf c2c report --stdio
 *   → HITM(Hit Modified) 카운트가 높으면 true sharing 경합
 */

ARM64 아키텍처 구현

ARM64는 약한 메모리 순서(Weakly Ordered) 아키텍처이므로, rwlock 구현에서 명시적 배리어와 exclusive 모니터 기반의 원자 연산이 필수적입니다. x86과 달리 모든 acquire/release 의미론을 명시적으로 인코딩해야 합니다.

Exclusive Monitor와 LDAXR/STLXR

/*
 * ARM64 atomic_add_return_acquire(_QR_BIAS, &cnts):
 *
 *   prfm  pstl1strm, [x0]     ; prefetch for store (선택적)
 * 1:
 *   ldaxr w1, [x0]            ; Load-Acquire Exclusive Register
 *                              ; → exclusive monitor 설정
 *                              ; → acquire 의미론 포함
 *   add   w2, w1, #0x200      ; w2 = w1 + _QR_BIAS
 *   stxr  w3, w2, [x0]        ; Store Exclusive Register
 *                              ; → exclusive monitor 확인
 *                              ; → 성공: w3=0, 실패: w3=1
 *   cbnz  w3, 1b              ; 실패 시 재시도
 *   ; w1에 원래 cnts 값 (반환값)
 *
 * Exclusive Monitor 동작:
 *   - LDAXR: 해당 캐시라인에 exclusive 표시 설정
 *   - 다른 코어가 같은 캐시라인을 수정하면
 *     exclusive 표시 클리어 → STXR 실패
 *   - Local monitor (CPU별) + Global monitor (버스 레벨)
 *
 * LDAXR vs LDXR:
 *   LDAXR = Load + Acquire + Exclusive
 *   LDXR  = Load + Exclusive (acquire 없음)
 *   → rwlock은 acquire 의미론이 필요하므로 LDAXR 사용
 */

/*
 * smp_store_release(&lock->wlocked, 1):
 *
 *   STLRB w1, [x0]            ; Store-Release Byte
 *   ; STLRB: Store + Release 의미론
 *   ; → 이전의 모든 메모리 접근이 이 스토어 이전에 완료
 *   ; → 임계 영역의 데이터가 lock 해제 이전에 가시적
 *
 *   cf. x86에서는 단순 MOV로 충분 (TSO 보장)
 */

WFE/SEV 메커니즘

/*
 * ARM64에서 atomic_cond_read_acquire의 구현:
 *
 * WFE (Wait For Event):
 *   1. Event Register가 설정되어 있으면 즉시 반환 (플래그 클리어)
 *   2. 설정되어 있지 않으면 CPU를 저전력 대기 상태로 전환
 *   3. 다음 조건에서 깨어남:
 *      a. SEV/SEVL 명령어 (Send Event)
 *      b. 인터럽트 (IRQ/FIQ/SError)
 *      c. exclusive monitor 클리어 (다른 코어가 캐시라인 수정)
 *      d. 디버그 이벤트
 *
 * → x86 PAUSE보다 전력 효율적: CPU가 실제로 대기 상태
 * → 깨어나는 지연은 PAUSE(~140 사이클)보다 길 수 있음
 *    (마이크로아키텍처에 따라 ~1us 수준)
 *
 * SEV (Send Event):
 *   - 모든 코어의 Event Register를 설정
 *   - Writer unlock 시 호출 → 대기 중인 Reader WFE 해제
 *   - 커널에서 직접 호출하지 않음; STLR이 암묵적으로
 *     exclusive monitor 클리어 → WFE 자동 해제
 */

/* ARM64 qrwlock spin 루프 의사 코드 */
static inline void arm64_cond_read(atomic_t *v, int cond_mask)
{
    int val;
    for (;;) {
        val = __atomic_load_n(&v->counter, __ATOMIC_RELAXED);
        if (!(val & cond_mask))
            break;
        __wfe();   /* Wait For Event — CPU 저전력 대기 */
    }
    __dmb(ishld);  /* acquire 배리어: Inner Shareable, Load */
}

DMB 배리어 종류

/*
 * ARM64 메모리 배리어 명령어 (rwlock 관련):
 *
 * DMB (Data Memory Barrier):
 *   DMB ISH    — Inner Shareable, Full barrier
 *   DMB ISHLD  — Inner Shareable, Load-Load + Load-Store
 *   DMB ISHST  — Inner Shareable, Store-Store
 *
 * DSB (Data Synchronization Barrier):
 *   → DMB보다 강력: 명령어 실행 자체를 차단
 *   → rwlock에서는 일반적으로 불필요
 *
 * rwlock에서의 배리어 배치:
 *
 * read_lock:  LDAXR → STXR → (acquire 내장)
 *             ┌─ 여기서부터 임계 영역 ─┐
 * read_unlock: atomic_sub(_QR_BIAS)  (release)
 *             └─ 여기까지 임계 영역 ─┘
 *
 * write_lock: LDAXR/STLXR 반복 (acquire)
 *             ┌─ 임계 영역 ─┐
 * write_unlock: STLRB wzr   (release)
 *             └─ 임계 영역 ─┘
 *
 * LDAXR: Load-Acquire Exclusive → acquire + exclusive
 * STLXR: Store-Release Exclusive → release + exclusive
 * STLRB: Store-Release Byte → release (바이트 단위)
 */

RISC-V 아키텍처 구현

RISC-V는 원자 연산을 위해 LR/SC(Load-Reserved/Store-Conditional)와 AMO(Atomic Memory Operation) 두 가지 메커니즘을 제공합니다. qrwlock 구현에서 두 메커니즘이 어떻게 사용되는지 분석합니다.

LR/SC 기반 원자 연산

/*
 * RISC-V atomic_add_return_acquire(_QR_BIAS, &cnts):
 *
 * 방법 1: AMO 명령어 사용
 *   amoadd.w.aq a0, a1, (a2)   ; atomic add with acquire
 *   ; a0 = 원래 값 (반환), [a2] += a1
 *   ; .aq = acquire ordering (이후 메모리 접근 재배치 금지)
 *   ; .rl = release ordering (.aqrl이면 둘 다)
 *
 * 방법 2: LR/SC 사용
 * 1: lr.w.aq a0, (a2)          ; Load-Reserved, acquire
 *    add     a1, a0, a3        ; a1 = a0 + _QR_BIAS
 *    sc.w    a4, a1, (a2)      ; Store-Conditional
 *    bnez    a4, 1b            ; 실패 시 재시도
 *    ; a0에 원래 cnts 값
 *
 * LR/SC vs AMO:
 *   - AMO: 단일 명령어, 간단한 연산(add/and/or/xor/swap)
 *   - LR/SC: 복잡한 연산 가능 (cmpxchg 등), ABA 문제 없음
 *   - qrwlock fast path: amoadd.w.aq 사용 (더 효율적)
 *   - qrwlock slow path: LR/SC 사용 (cmpxchg 필요)
 */

/*
 * LR/SC 예약 세트(Reservation Set):
 *   - LR이 예약하는 메모리 범위: 구현 정의 (최소 1 워드)
 *   - 다른 코어가 예약 범위 내 메모리를 수정하면 SC 실패
 *   - ARM64 exclusive monitor와 유사하지만:
 *     → RISC-V는 "forward progress" 보장이 더 약함
 *     → LR/SC 사이에 다른 메모리 접근을 넣지 말아야 함
 *     → 스펙: LR과 SC 사이 최대 16개 명령어 권장
 */

fence 명령어와 메모리 순서

/*
 * RISC-V 메모리 순서 명령어:
 *
 * fence rw, rw     ; Full barrier (iorw 포함 시 fence iorw, iorw)
 * fence r, r       ; Load-Load barrier
 * fence w, w       ; Store-Store barrier
 * fence r, rw      ; acquire barrier 역할
 * fence rw, w      ; release barrier 역할
 *
 * RISC-V는 ARM64보다 더 약한 기본 메모리 모델 (RVWMO):
 *   - Load-Load 재배치 가능
 *   - Load-Store 재배치 가능
 *   - Store-Store 재배치 가능
 *   - Store-Load 재배치 가능 (x86도 이것만 허용)
 *   → 모든 종류의 재배치가 가능하므로 배리어 필수
 *
 * qrwlock에서의 배리어 사용:
 *
 * read_lock:
 *   amoadd.w.aq → .aq가 acquire fence 포함
 *
 * read_unlock:
 *   amoadd.w.rl → .rl이 release fence 포함
 *   또는 fence rw, w + amoadd.w
 *
 * write_lock:
 *   lr.w.aq / sc.w → acquire
 *   또는 amocas.w.aq (Zacas 확장)
 *
 * write_unlock:
 *   fence rw, w     ; release 배리어
 *   sb zero, (wlocked) ; wlocked = 0
 */

/*
 * RISC-V의 WFE 부재:
 *   RISC-V에는 ARM64의 WFE에 해당하는 표준 명령어가 없음
 *   → cpu_relax()가 순수 spin 루프 (NOP 또는 PAUSE 힌트)
 *   → Zawrs 확장이 있으면 WRS.STO/WRS.NTO 사용 가능:
 *     wrs.sto rs1  ; Wait on Reservation Set, Short Timeout
 *     → 예약 세트가 변경될 때까지 대기 (WFE와 유사)
 *   → 2024 기준 대부분의 구현에서 Zawrs 미지원
 */

RISC-V qrwlock 전체 시퀀스

/* RISC-V queued_read_lock 어셈블리 의사 코드 */
queued_read_lock:
    /* ① atomic_add_return_acquire(_QR_BIAS, &cnts) */
    li      a1, 0x200           /* a1 = _QR_BIAS */
    amoadd.w.aq a0, a1, (lock)   /* a0 = old cnts, [lock] += 0x200 */
    add     a0, a0, a1           /* a0 = new cnts */

    /* ② Writer 확인 */
    andi    a2, a0, 0x1ff       /* a2 = cnts & _QW_WMASK */
    bnez    a2, .Lslow           /* Writer 존재 → slow path */
    ret                          /* fast path 성공 */

.Lslow:
    /* slow path: queued_read_lock_slowpath */
    li      a1, -0x200          /* a1 = -_QR_BIAS */
    amoadd.w a0, a1, (lock)      /* reader count 복원 */
    /* ... wait_lock 획득 후 spin ... */

/* queued_read_unlock */
queued_read_unlock:
    li      a1, -0x200
    amoadd.w.rl a0, a1, (lock)   /* release: reader count 감소 */
    ret

percpu_rw_semaphore 내부 심층

percpu_rw_semaphore는 Reader fast path에서 전역 atomic 연산을 완전히 제거하여 확장성을 극대화합니다. 이 섹션에서는 fast path의 정확한 구현, RCU 동기화, slow path의 복잡한 상호작용을 소스 레벨에서 분석합니다.

Reader Fast Path: __percpu_down_read 내부

/* include/linux/percpu-rwsem.h */
static inline void percpu_down_read(struct percpu_rw_semaphore *sem)
{
    might_sleep();

    preempt_disable();
    /*
     * rcu_sync_is_idle() 확인:
     *   true  → Writer가 없음 (정상 상태)
     *          → this_cpu_inc()만으로 Reader 등록!
     *          → 전역 atomic 없음, 캐시 경합 없음
     *          → ~2-5ns (로컬 캐시 라인만 접근)
     *
     *   false → Writer가 활동 중 (rcu_sync_enter 호출됨)
     *          → __percpu_down_read() slow path 진입
     */
    if (likely(rcu_sync_is_idle(&sem->rss)))
        this_cpu_inc(*sem->read_count);
    else
        __percpu_down_read(sem, false);
    preempt_enable();
}

/* kernel/locking/percpu-rwsem.c — slow path */
bool __percpu_down_read(struct percpu_rw_semaphore *sem,
                         bool try)
{
    /*
     * Writer가 활동 중일 때의 Reader 경로:
     * ① per-cpu 카운터 먼저 증가
     * ② atomic_read(&sem->block) 확인
     *    → 0이면 Writer가 아직 Reader 차단 안 함 → 성공
     *    → 1이면 Reader 차단 중 → 카운터 복원 후 대기
     */
    this_cpu_inc(*sem->read_count);
    smp_mb();  /* read_count inc과 block 읽기 순서 보장 */

    if (likely(!atomic_read(&sem->block)))
        return true;

    /* Writer가 차단 중 → 카운터 복원 */
    this_cpu_dec(*sem->read_count);

    /* try 모드면 실패 반환 */
    if (try)
        return false;

    /* ③ Writer 완료까지 대기 큐에서 슬립
     *    Writer가 percpu_up_write() 호출하면 깨움 */
    wait_event(sem->waiters,
        !atomic_read(&sem->block));

    /* ④ Writer 완료 → 다시 per-cpu 카운터 증가 */
    this_cpu_inc(*sem->read_count);
    return true;
}

Writer 경로 상세: synchronize_rcu의 역할

/* kernel/locking/percpu-rwsem.c */
void percpu_down_write(struct percpu_rw_semaphore *sem)
{
    might_sleep();

    /* ① rcu_sync_enter: RCU sync 상태 전환
     *    rcu_sync_is_idle()가 false를 반환하게 만듦
     *    → 이후 Reader의 fast path에서 slow path로 전환
     *    → rcu_sync는 내부적으로 call_rcu/synchronize_rcu 사용
     *    → 첫 번째 Writer가 이미 enter 했으면 빠르게 반환 */
    rcu_sync_enter(&sem->rss);

    /* ② 내부 rwsem Writer 획득
     *    여러 Writer 간 직렬화 */
    down_write(&sem->rw_sem);

    /* ③ block = 1 → 새 Reader의 slow path에서도 차단
     *    smp_mb() 이후 block 설정 → 순서 보장 */
    atomic_set(&sem->block, 1);
    smp_mb();  /* block 설정이 per-cpu 합산 이전에 가시적 */

    /* ④ synchronize_rcu()
     *    핵심: 현재 preempt_disable() 섹션에 있는 Reader들이
     *    모두 preempt_enable()을 호출할 때까지 대기
     *
     *    왜 필요한가?
     *    Reader fast path: preempt_disable → this_cpu_inc → preempt_enable
     *    synchronize_rcu()는 모든 CPU가 quiescent state를 지남을 보장
     *    → preempt_disable 구간에 있던 Reader는 반드시 완료됨
     *    → 이후 per-cpu 합산 결과가 정확함을 보장 */
    synchronize_rcu();

    /* ⑤ 모든 per-cpu 카운터 합산하여 0이 될 때까지 대기
     *    readers_active_check: sum of all per-cpu read_count == 0
     *    → 슬로우 패스에서 진입한 Reader도 모두 나갈 때까지 */
    rcuwait_wait_event(&sem->writer,
        readers_active_check(sem));
}

/* percpu_up_write — Writer 해제 */
void percpu_up_write(struct percpu_rw_semaphore *sem)
{
    /* ① block = 0 → 새 Reader 허용 */
    atomic_set(&sem->block, 0);

    /* ② 대기 중인 Reader 깨움 */
    wake_up_all(&sem->waiters);

    /* ③ 내부 rwsem 해제 */
    up_write(&sem->rw_sem);

    /* ④ rcu_sync_exit: 충분한 grace period 후
     *    rcu_sync_is_idle()가 다시 true 반환
     *    → Reader fast path 복구 */
    rcu_sync_exit(&sem->rss);
}

readers_active_check 구현

/* kernel/locking/percpu-rwsem.c */
static bool readers_active_check(struct percpu_rw_semaphore *sem)
{
    /*
     * 모든 CPU의 per-cpu read_count를 합산
     * → 0이면 모든 Reader가 나간 것
     *
     * 주의: 이 합산은 반드시 synchronize_rcu() 이후에 수행해야 함
     * 그래야 preempt_disable 구간에 있던 Reader가
     * this_cpu_inc를 완료한 상태를 보장
     *
     * percpu_counter_sum()은 smp_call_function보다 저렴하지만
     * 여전히 NR_CPUS 개의 캐시라인을 읽어야 함
     * → 128-CPU 시스템에서 ~10us 수준
     */
    if (per_cpu_sum(*sem->read_count) != 0)
        return false;
    return true;
}

/* per_cpu_sum 의사 구현 */
static inline long per_cpu_sum(unsigned int __percpu var)
{
    long sum = 0;
    int cpu;

    for_each_possible_cpu(cpu)
        sum += per_cpu(var, cpu);

    return sum;
}

벤치마크: reader/writer 비율별 성능

Reader-Writer Lock의 성능은 읽기/쓰기 비율에 극도로 민감합니다. 이 섹션에서는 다양한 프리미티브를 Reader/Writer 비율, CPU 수, 임계 영역 크기에 따라 비교합니다.

벤치마크 방법론

/* 커널 모듈 기반 벤치마크 (locktorture 변형) */
/*
 * 테스트 환경:
 *   - CPU: Intel Xeon Platinum 8380 (2S, 80C/160T)
 *   - 메모리: DDR4-3200 512GB (NUMA 2 노드)
 *   - 커널: v6.8 defconfig + CONFIG_LOCK_STAT=y
 *   - 각 테스트: 10초간 반복, ops/sec 측정
 *
 * 임계 영역: 공유 카운터 1회 읽기/증가 (~10ns)
 */

/* locktorture 파라미터 */
/*
 * modprobe locktorture torture_type=rwsem_lock \
 *     nreaders_stress=79 nwriters_stress=1 \
 *     stat_interval=1 verbose=1
 *
 * torture_type:
 *   rwsem_lock      — rw_semaphore
 *   rw_lock_lock    — rwlock_t
 *   percpu_rwsem    — percpu_rw_semaphore
 *   mutex_lock      — mutex (비교 기준)
 */

Reader/Writer 비율별 처리량

CPU 수별 확장성

임계 영역 크기의 영향

/*
 * 임계 영역 크기별 성능 영향 (64 CPU, R:W = 99:1):
 *
 * 임계 영역    rwlock_t    rwsem      percpu_rwsem
 * ─────────────────────────────────────────────────
 * ~10ns        120M ops    180M ops   380M ops
 * ~100ns        95M ops    150M ops   370M ops
 * ~1us          40M ops     80M ops   350M ops
 * ~10us         12M ops     25M ops   300M ops
 * ~100us         1.5M ops    3M ops    50M ops
 *
 * 관찰:
 * 1. 임계 영역이 짧을수록 lock 오버헤드 비중이 높음
 *    → percpu_rwsem의 이점이 극대화됨
 * 2. 임계 영역이 길면(~100us) 모든 프리미티브 성능 하락
 *    → lock 오버헤드보다 임계 영역 자체가 병목
 * 3. rwsem이 rwlock_t보다 나은 이유:
 *    → optimistic spinning이 Writer 전환 비용 감소
 *    → 경합 시 슬립으로 CPU 낭비 방지
 */

메모리 순서와 배리어 배치

Reader-Writer Lock의 정확성은 메모리 순서 보장(Ordering)에 의존합니다. 이 섹션에서는 각 연산의 acquire/release 의미론과 아키텍처별 배리어 배치를 분석합니다.

Acquire/Release 의미론

/*
 * rwlock의 메모리 순서 계약:
 *
 * ┌─────────────────────────────────────────────────┐
 * │ read_lock()/write_lock()  →  ACQUIRE            │
 * │   이후의 메모리 접근이 이전으로 재배치 불가       │
 * │                                                   │
 * │ read_unlock()/write_unlock() →  RELEASE           │
 * │   이전의 메모리 접근이 이후로 재배치 불가          │
 * │                                                   │
 * │ 결합 효과:                                        │
 * │   CPU A: write_lock → [store X] → write_unlock   │
 * │   CPU B: read_lock  → [load X]  → read_unlock    │
 * │   → CPU B는 반드시 CPU A의 X 갱신을 관찰         │
 * └─────────────────────────────────────────────────┘
 *
 * 이것이 보장하는 것:
 * 1. 임계 영역 내의 접근이 임계 영역 밖으로 유출되지 않음
 * 2. Writer의 수정이 이후 Reader에게 가시적
 * 3. 여러 Reader의 읽기 결과가 일관적 (동일 시점의 데이터)
 */

qrwlock의 배리어 배치

/*
 * qrwlock 각 연산의 정확한 배리어:
 *
 * ■ queued_read_lock:
 *   atomic_add_return_acquire(_QR_BIAS, &cnts)
 *   → ACQUIRE 의미론
 *   → x86: LOCK XADD (암묵적 full barrier)
 *   → ARM64: LDAXR + STXR (LDAXR이 acquire)
 *   → RISC-V: amoadd.w.aq (.aq가 acquire)
 *
 * ■ queued_read_unlock:
 *   atomic_sub_return_release(_QR_BIAS, &cnts)
 *   → RELEASE 의미론
 *   → x86: LOCK XADD (암묵적 full barrier)
 *   → ARM64: LDXR + STLXR (STLXR이 release)
 *   → RISC-V: amoadd.w.rl (.rl이 release)
 *
 * ■ queued_write_lock:
 *   atomic_cmpxchg_acquire(&cnts, 0, _QW_LOCKED)
 *   → ACQUIRE 의미론
 *
 * ■ queued_write_unlock:
 *   smp_store_release(&lock->wlocked, 0)
 *   → RELEASE 의미론
 *   → x86: MOV (TSO가 release 보장)
 *   → ARM64: STLRB (Store-Release Byte)
 *   → RISC-V: fence rw,w + sb
 */

rwsem의 배리어 배치

/*
 * rwsem의 메모리 순서 — qrwlock보다 복잡:
 *
 * ■ down_read (fast path):
 *   atomic_long_fetch_add_acquire(RWSEM_READER_BIAS, &count)
 *   → ACQUIRE
 *
 * ■ up_read (fast path):
 *   count이 0이 아니면 (대기자 없음):
 *     atomic_long_add_return_release(-RWSEM_READER_BIAS, &count)
 *     → RELEASE
 *   대기자 있으면:
 *     rwsem_wake() 호출 → wake_up_process()
 *     → 깨우는 쪽에서 smp_store_release 수행
 *
 * ■ down_write (fast path):
 *   atomic_long_cmpxchg_acquire(&count, 0, RWSEM_WRITER_LOCKED)
 *   → ACQUIRE
 *
 * ■ up_write:
 *   atomic_long_add_return_release(-RWSEM_WRITER_LOCKED, &count)
 *   → RELEASE
 *   대기자가 있으면 rwsem_wake() 호출
 *
 * ■ downgrade_write:
 *   count에서 WRITER_LOCKED 제거 + READER_BIAS 추가
 *   → 내부적으로 atomic_long_add(-RWSEM_WRITER_LOCKED+RWSEM_READER_BIAS)
 *   → 대기 중인 Reader 깨움 (RELEASE 의미론 포함)
 */

/*
 * 중요한 배리어 주의점:
 *
 * 1. Owner 확인 시 smp_load_acquire:
 *    owner를 읽어 optimistic spinning 결정 시
 *    → smp_load_acquire로 읽어야 owner->on_cpu의
 *      최신 값을 보장
 *
 * 2. Waiter 깨움 시 smp_store_release:
 *    waiter->task = NULL로 설정하여 깨움 알림
 *    → release로 임계 영역의 변경 사항이 가시적
 *
 * 3. HANDOFF 플래그:
 *    atomic_long_or(RWSEM_FLAG_HANDOFF, &count)
 *    → 별도 배리어 불필요 (atomic OR이 충분)
 */

서브시스템 사례: VFS inode->i_rwsem

inode->i_rwsem은 리눅스 커널에서 가장 빈번하게 경합하는 rwsem 중 하나입니다. 파일 읽기/쓰기, 디렉터리 조회, 메타데이터 업데이트 등 거의 모든 VFS 연산이 이 락을 거칩니다.

i_rwsem의 역할

/* include/linux/fs.h */
struct inode {
    /* ... */
    struct rw_semaphore     i_rwsem;
    /* ... */
};

/*
 * i_rwsem 보호 대상:
 *
 * ■ 일반 파일:
 *   Reader (down_read):
 *     - read() 시스템 콜 (버퍼드 I/O)
 *     - 파일 크기 조회 (stat)
 *     - mmap 읽기 경로
 *
 *   Writer (down_write):
 *     - write() 시스템 콜 (파일 확장 시)
 *     - truncate/ftruncate
 *     - fallocate
 *     - 권한/타임스탬프 변경 (setattr)
 *
 * ■ 디렉터리:
 *   Reader (down_read):
 *     - 이름 해석 (lookup) — 경로 탐색
 *     - readdir/getdents
 *     - 디렉터리 내 stat
 *
 *   Writer (down_write):
 *     - 파일/디렉터리 생성 (create, mkdir)
 *     - 삭제 (unlink, rmdir)
 *     - 이름 변경 (rename)
 *     - 하드 링크 생성 (link)
 */

VFS 잠금 순서 규칙

/*
 * VFS i_rwsem 잠금 순서 (lockdep으로 검증):
 *
 * 1. 디렉터리 i_rwsem → 자식 inode i_rwsem
 *    예: rename(src_dir, dst_dir):
 *      down_write(src_dir->i_rwsem)
 *      down_write(dst_dir->i_rwsem)  // src < dst 순서
 *      down_write(victim->i_rwsem)   // 삭제될 파일
 *
 * 2. mmap_lock → i_rwsem
 *    페이지 폴트 → 파일 읽기:
 *      down_read(mm->mmap_lock)  // 이미 보유
 *      down_read(inode->i_rwsem)
 *
 * 3. i_rwsem → 페이지 락
 *    write() → 페이지 캐시:
 *      down_write(inode->i_rwsem)
 *      lock_page(page)
 *
 * lockdep 어노테이션:
 *   inode_lock(inode)       → down_write(&inode->i_rwsem)
 *   inode_unlock(inode)     → up_write(&inode->i_rwsem)
 *   inode_lock_shared(inode) → down_read(&inode->i_rwsem)
 *   inode_unlock_shared(inode) → up_read(&inode->i_rwsem)
 *
 * 중첩 잠금 (lockdep class):
 *   I_MUTEX_PARENT  — 부모 디렉터리
 *   I_MUTEX_CHILD   — 자식 inode
 *   I_MUTEX_NORMAL  — 일반 파일
 *   I_MUTEX_XATTR   — 확장 속성
 */

i_rwsem 경합 분석

/*
 * i_rwsem 경합이 높은 시나리오:
 *
 * 1. 다중 스레드 동시 읽기 + 간헐적 쓰기
 *    예: 웹 서버가 정적 파일을 서빙하면서
 *        로그 로테이션이 발생하는 경우
 *    → read()는 down_read, 로그 로테이션의 truncate는 down_write
 *    → Writer가 기다리는 동안 HANDOFF 발동 가능
 *
 * 2. 디렉터리 집중 워크로드
 *    예: /tmp에서 수천 개 파일 생성/삭제
 *    → 모든 create/unlink가 동일 디렉터리의 i_rwsem Writer 획득
 *    → lookup(Reader)과 create(Writer)의 경합
 *
 * 3. 메일디르 패턴 (Maildir++)
 *    예: 수천 프로세스가 동일 디렉터리에 파일 생성
 *    → 모든 프로세스가 디렉터리 i_rwsem Writer 대기
 *    → 해결: 디렉터리 해싱 또는 tmpfile+linkat 패턴
 *
 * 성능 측정:
 *   echo 1 > /proc/lock_stat
 *   # 워크로드 실행
 *   cat /proc/lock_stat | grep -A3 "i_rwsem"
 *   # contentions, waittime-total, holdtime-avg 확인
 *
 * perf lock:
 *   perf lock record -p $PID -- sleep 10
 *   perf lock report --sort acquired,contended,avg_wait
 */

VFS 레벨 최적화

/*
 * i_rwsem 경합 감소 전략:
 *
 * 1. 파일별 읽기 시 i_rwsem 불필요한 경우:
 *    → Direct I/O 읽기: v5.19부터 i_rwsem 없이 수행 가능
 *      (inode_dio_begin/end로 충분)
 *    → io_uring의 IORING_OP_READ_FIXED:
 *      고정 버퍼 사용 시 i_rwsem 회피
 *
 * 2. 디렉터리 연산 최적화:
 *    → 경로 해석 시 RCU-walk 모드:
 *      i_rwsem 없이 d_seq seqcount 사용
 *      실패 시만 REF-walk(down_read) 폴백
 *    → 이것이 VFS의 가장 중요한 확장성 최적화
 *
 * 3. parallel_rename (실험적):
 *    → 디렉터리 내 rename을 파일 이름 해시로 분할
 *    → 다른 해시 버킷의 rename은 동시 수행
 *    → 아직 mainline 미포함 (2024 기준)
 */

/* RCU-walk vs REF-walk */
/*
 * 경로 해석 예: /home/user/file.txt
 *
 * RCU-walk (fast path):
 *   rcu_read_lock()
 *   / → d_seq 확인 → home → d_seq 확인 → user → d_seq 확인 → file.txt
 *   rcu_read_unlock()
 *   → i_rwsem 사용 안 함! seqcount만 확인
 *   → 대부분의 lookup이 이 경로로 성공
 *
 * REF-walk (fallback):
 *   inode_lock_shared(dir)  // down_read(&dir->i_rwsem)
 *   dir->lookup()
 *   inode_unlock_shared(dir)
 *   → rename/unlink 등으로 d_seq가 변경되면 RCU-walk 실패
 *   → REF-walk로 전환하여 i_rwsem 사용
 */

서브시스템 사례: 네트워크 스택

네트워크 스택은 rwlock_t와 rw_semaphore를 광범위하게 사용합니다. 네트워크 디바이스(Device) 목록, 소켓(Socket) 콜백, 라우팅(Routing) 테이블 등에서 읽기 경로의 성능이 핵심입니다.

dev_base_lock: 네트워크 디바이스 목록

/* net/core/dev.c */
DEFINE_RWLOCK(dev_base_lock);

/*
 * dev_base_lock 보호 대상:
 *   - 네트워크 네임스페이스의 디바이스 리스트 (dev_base_head)
 *   - dev->name, dev->ifindex 등 디바이스 속성
 *
 * Reader 사용처 (매우 빈번):
 *   - dev_get_by_name() — 이름으로 디바이스 찾기
 *   - dev_get_by_index() — 인덱스로 디바이스 찾기
 *   - /proc/net/dev 읽기
 *   - netlink 덤프 (ip link show)
 *
 * Writer 사용처 (드묾):
 *   - register_netdevice() — 디바이스 등록
 *   - unregister_netdevice() — 디바이스 해제
 *   - dev_change_name() — 인터페이스 이름 변경
 *
 * 주의: 최신 커널에서는 RCU로 대부분 대체되었지만,
 * dev_base_lock은 Writer 직렬화와 하위 호환성을 위해 유지됨
 */

/* 디바이스 등록 — Writer 경로 */
int register_netdevice(struct net_device *dev)
{
    /* ... 검증 ... */
    write_lock(&dev_base_lock);
    list_netdevice(dev);        /* 리스트에 추가 */
    write_unlock(&dev_base_lock);
    /* ... 후처리 ... */
}

/* 디바이스 조회 — Reader 경로 (RCU 대안 존재) */
struct net_device *__dev_get_by_name(
    struct net *net, const char *name)
{
    /* ASSERT_RTNL() 또는 dev_base_lock Reader 보유 확인 */
    /* 해시 테이블에서 이름으로 검색 */
    hlist_for_each_entry(dev, head, name_hlist) {
        if (!strncmp(dev->name, name, IFNAMSIZ))
            return dev;
    }
    return NULL;
}

sk_callback_lock: 소켓 콜백 보호

/* include/net/sock.h */
struct sock {
    /* ... */
    rwlock_t  sk_callback_lock;
    /* ... */
};

/*
 * sk_callback_lock은 소켓의 콜백 함수 포인터를 보호합니다:
 *   - sk->sk_data_ready    — 데이터 수신 알림
 *   - sk->sk_write_space   — 쓰기 공간 확보 알림
 *   - sk->sk_state_change  — 상태 변경 알림
 *   - sk->sk_error_report  — 에러 보고
 *
 * Reader (매우 빈번 — 패킷 수신 경로):
 *   read_lock_bh(&sk->sk_callback_lock);
 *   sk->sk_data_ready(sk);    // 콜백 호출
 *   read_unlock_bh(&sk->sk_callback_lock);
 *
 * Writer (드묾 — 콜백 변경):
 *   write_lock_bh(&sk->sk_callback_lock);
 *   sk->sk_data_ready = new_callback;
 *   write_unlock_bh(&sk->sk_callback_lock);
 *
 * BH 변형 사용 이유:
 *   패킷 수신은 softirq(NAPI/NET_RX)에서 발생
 *   프로세스 컨텍스트에서 콜백 변경 시 softirq와 경합 방지
 *
 * 사용 사례:
 *   - TLS(kTLS): 암호화 콜백으로 교체
 *   - epoll: poll 콜백 등록
 *   - splice/sendfile: 데이터 파이프 콜백
 */

/* TCP 수신 경로 — softirq에서 Reader */
void tcp_data_ready(struct sock *sk)
{
    /* softirq 컨텍스트 → _bh 불필요 (이미 softirq) */
    read_lock(&sk->sk_callback_lock);
    sk->sk_data_ready(sk);
    read_unlock(&sk->sk_callback_lock);
}

/* kTLS 콜백 교체 — 프로세스 컨텍스트에서 Writer */
int tls_set_device_offload(struct sock *sk, ...)
{
    write_lock_bh(&sk->sk_callback_lock);
    sk->sk_data_ready = tls_data_ready;
    write_unlock_bh(&sk->sk_callback_lock);
}

dev_addr_list_lock: MAC 주소 목록

/* net/core/dev_addr_lists.c */
/*
 * 네트워크 디바이스의 유니캐스트/멀티캐스트 주소 목록 보호
 *
 * struct netdev_hw_addr_list {
 *     struct list_head list;
 *     int count;
 *     // ... 이 리스트를 rwlock으로 보호
 * };
 *
 * Reader (패킷 수신 시 주소 매칭):
 *   netif_addr_lock(dev);   // read_lock_bh(&dev->addr_list_lock)
 *   // 유니캐스트/멀티캐스트 주소 리스트 탐색
 *   netif_addr_unlock(dev);
 *
 * Writer (주소 추가/삭제 — ip link set 등):
 *   netif_addr_lock_bh(dev); // write_lock_bh(&dev->addr_list_lock)
 *   dev_mc_add(dev, addr);
 *   netif_addr_unlock_bh(dev);
 *
 * 이 패턴은 네트워크 드라이버 작성 시 자주 등장합니다.
 * 프로미스큐어스(Promiscuous) 모드 전환, VLAN 주소 추가 등에서
 * 항상 이 rwlock을 통해 주소 목록에 접근해야 합니다.
 */

fib 테이블: rwsem 사용

/* net/ipv4/fib_trie.c */
/*
 * 라우팅 테이블(FIB)은 rcu_read_lock으로 보호되지만,
 * 테이블 수정 시에는 RTNL lock(mutex) + fib_info rwsem을 사용합니다.
 *
 * 읽기 경로 (패킷 포워딩 — 초당 수백만 회):
 *   rcu_read_lock();
 *   fib_lookup(net, flp, &res);  // RCU로 보호
 *   rcu_read_unlock();
 *
 * 쓰기 경로 (라우트 추가/삭제):
 *   rtnl_lock();   // mutex
 *   fib_table_insert(tb, cfg, ...);
 *   rtnl_unlock();
 *
 * 이는 rwlock → RCU 전환의 모범 사례입니다:
 *   초기: rwlock_t로 FIB 보호
 *   현재: RCU로 읽기, mutex로 쓰기 직렬화
 *   → 읽기 경로에서 lock 오버헤드 완전 제거
 *   → 패킷 포워딩 성능 극대화
 */

커널 버전별 진화

Reader-Writer Lock은 20년 이상에 걸쳐 지속적으로 발전해왔습니다. 초기의 단순한 rwlock_t에서 현재의 qrwlock + rwsem HANDOFF + percpu_rw_semaphore까지, 각 버전의 핵심 변화를 추적합니다.

핵심 커밋 레퍼런스

설계 철학의 변화

/*
 * Reader-Writer Lock 설계 철학의 진화:
 *
 * ■ 1세대 (v2.6): 하드웨어 최적화
 *   "아키텍처별 최적 어셈블리로 개별 연산을 빠르게"
 *   → 결과: x86/ARM/MIPS 각각 다른 구현, 유지보수 악몽
 *
 * ■ 2세대 (v3.x): 알고리즘 혁신
 *   "Optimistic Spinning으로 슬립 비용을 줄이자"
 *   → 결과: mutex에서 검증된 기법을 rwsem에 적용
 *   → 부작용: spinning이 대기 큐 waiter를 기아시킬 수 있음
 *
 * ■ 3세대 (v4.x-v5.x): 공정성 + 확장성
 *   "qrwlock으로 Writer starvation 방지,
 *    HANDOFF로 공정성, percpu로 확장성"
 *   → 결과: 균형 잡힌 설계, 대부분의 시나리오에서 우수
 *
 * ■ 4세대 (v6.x+): 사용 범위 축소
 *   "RW lock 자체를 최적화하기보다,
 *    RW lock이 필요 없도록 자료구조를 변경"
 *   → mmap_lock → per-VMA lock
 *   → i_rwsem → RCU-walk, lockless DIO
 *   → 철학: "가장 빠른 lock은 잡지 않는 lock"
 */

참고 자료

커널 공식 문서

• Lock types and their rules — rwlock, rwsem, percpu_rw_semaphore 비교 및 PREEMPT_RT 규칙
• Locking lessons — rwlock과 spinlock의 선택 기준
• Runtime locking correctness validator — rwsem lockdep 서브클래스 및 재귀 검증
• Lock Statistics — rwlock/rwsem contention 프로파일링

LWN.net 심층 기사

• Reader/writer problems (2009) — rwsem의 writer starvation 문제와 해결 방안
• MCS locks and qspinlocks (2015) — qrwlock의 MCS 기반 구현 배경
• MCS lock and qspinlock (2014) — qrwlock이 활용하는 qspinlock 인프라
• What is RCU, Fundamentally? (2007) — 읽기 위주 workload에서 rwlock 대신 RCU 선택 기준
• The percpu_rw_semaphore (2012) — percpu_rw_semaphore 설계와 scalability
• Concurrency bugs should fear the big bad data-race detector (2019) — KCSAN으로 rwlock 데이터 레이스 탐지

학술 자료 및 외부 참고

• Paul McKenney — "Is Parallel Programming Hard?" — Chapter 9.4: Reader-Writer Locking
• 커널 소스: kernel/locking/rwsem.c, kernel/locking/qrwlock.c, include/linux/percpu-rwsem.h

관련 문서

Reader-Writer Lock과 관련된 다른 동기화 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• 동기화 기법 — 전체 동기화 프리미티브 비교 및 선택 가이드
• Spinlock — qspinlock, MCS lock, PREEMPT_RT raw_spinlock
• Mutex — Optimistic Spinning, osq_lock, HANDOFF, PI chain
• RCU — 잠금 없는 읽기 경로 동기화, grace period
• Atomic 연산 — CAS/cmpxchg, 메모리 순서 의미론
• 메모리 배리어 — acquire/release, 아키텍처별 메모리 모델
• Per-CPU 변수 — percpu_rw_semaphore의 기반
• Futex — 유저 공간 rwlock (pthread_rwlock)
• 동시성 디버깅 — lockdep, KCSAN, perf lock 통합 가이드
• preempt_count — 선점 모델과 컨텍스트 판별