Lockdep (Lock Dependency Validator)

Linux 커널의 잠금(Lock) 의존성 검증기 lockdep를 분석합니다. 런타임에 잠금 획득 순서를 추적하여 잠재적 교착 상태(deadlock)를 사전에 탐지하는 메커니즘을 lock_class 개념, 의존성 그래프 구축, BFS 순환 탐지, IRQ 안전성 검증, wait_type 검사 등 내부 구현 수준에서 설명합니다. PROVE_LOCKING/LOCK_STAT 설정과 /proc 인터페이스, 실전 경고 메시지 해석과 디버깅(Debugging) 기법까지 포괄합니다.

이론적 배경: 잠금 의존성과 순환 감지

교착 상태(deadlock)는 Coffman 등(1971)이 정의한 4가지 필요 조건 — 상호 배제(Mutual Exclusion), 점유 대기(hold and wait), 비선점(no preemption), 순환 대기(circular wait) — 이 동시에 충족될 때 발생합니다. lockdep는 이 중 순환 대기 조건의 가능성을 런타임에 검증합니다.

ABBA 패턴: 가장 단순한 교착

두 스레드가 두 잠금 A, B를 반대 순서로 획득하면 교착이 발생할 수 있습니다:

/* Thread 1 */           /* Thread 2 */
lock(A);                  lock(B);
lock(B);  /* 대기 */     lock(A);  /* 대기 → deadlock */
unlock(B);                unlock(A);
unlock(A);                unlock(B);

lockdep는 Thread 1이 A→B 순서로 잠금을 획득하는 것을 관찰한 뒤, Thread 2가 B→A를 시도하면 — 실제 교착이 발생하지 않더라도 — 순환 의존성 경고를 발생시킵니다.

그래프 이론 기반 접근

잠금 의존성을 방향 그래프(directed graph)로 모델링합니다. 정점(vertex)은 잠금 클래스, 간선(edge)은 "A를 보유한 상태에서 B를 획득"이라는 관계입니다. 이 그래프에 순환(cycle)이 존재하면 교착 가능성이 있습니다. lockdep는 새로운 간선이 추가될 때마다 순환 검사를 수행합니다.

lockdep 전체 아키텍처

lockdep 서브시스템은 kernel/locking/lockdep.c에 구현되어 있으며, 약 6000줄 이상의 코드로 구성됩니다. 핵심 데이터 구조와 동작 흐름을 정리합니다.

핵심 자료구조 요약

lock_class: 잠금 클래스 개념

lockdep의 핵심 통찰은 개별 잠금 인스턴스가 아닌 잠금 클래스 단위로 의존성을 추적한다는 것입니다. 예를 들어, 시스템에 1000개의 inode가 있고 각 inode에 i_rwsem이 있다면, lockdep는 이 1000개의 잠금을 하나의 lock_class로 취급합니다.

/* include/linux/lockdep_types.h */
struct lock_class {
    struct hlist_node       hash_entry;      /* 해시 테이블 체인 */
    struct list_head        lock_entry;      /* 전역 목록 */
    struct list_head        locks_after;     /* forward 의존성: 이 클래스 후에 획득된 잠금들 */
    struct list_head        locks_before;    /* backward 의존성: 이 클래스 전에 획득된 잠금들 */
    const struct lockdep_subclass_key *key;  /* 클래스 식별 키 */
    unsigned int            subclass;       /* 서브클래스 번호 */
    unsigned int            dep_gen_id;     /* 의존성 생성 ID */
    unsigned long           usage_mask;     /* IRQ 사용 상태 비트마스크 */
    const char             *name;          /* 잠금 이름 (디버그용) */
    short                   name_version;   /* 이름 버전 */
    unsigned long           contention_point[LOCKSTAT_POINTS]; /* 경합 지점 */
    unsigned long           contending_point[LOCKSTAT_POINTS]; /* 피경합 지점 */
};

usage_mask: IRQ 사용 상태 추적

lock_class의 usage_mask 필드는 해당 잠금 클래스가 어떤 컨텍스트에서 사용되었는지를 비트마스크로 기록합니다:

lock_class_key와 정적 키

lock_class_key는 잠금 클래스를 식별하는 핵심 요소입니다. 잠금이 정의된 소스 코드 위치에 정적 변수로 생성되며, 이 변수의 주소가 클래스의 고유 식별자 역할을 합니다.

/* include/linux/lockdep_types.h */
struct lock_class_key {
    union {
        struct hlist_node           hash_entry;
        struct lockdep_subclass_key  subkeys[MAX_LOCKDEP_SUBCLASSES];
    };
};

/* 매크로 전개 예: DEFINE_MUTEX(my_lock) */
static struct lock_class_key __key;  /* 정적 키 — 주소가 클래스 ID */
__mutex_init(&my_lock, "my_lock", &__key);

키 등록 과정

잠금이 처음 lock_acquire()를 거칠 때, lockdep는 키 주소로 해시 테이블(Hash Table)을 검색합니다:

1. 키 주소가 이미 등록된 lock_class에 매핑(Mapping)되어 있으면 해당 클래스를 사용합니다.
2. 처음 보는 키이면 새로운 lock_class를 할당하고 해시 테이블에 등록합니다.
3. lockdep_map 구조체의 class_cache에 캐싱하여 이후 조회를 가속합니다.

/* kernel/locking/lockdep.c — register_lock_class() 핵심 흐름 */
static struct lock_class *
register_lock_class(struct lockdep_map *lock,
                    unsigned int subclass, int force)
{
    struct lockdep_subclass_key *key;
    struct hlist_head *hash_head;
    struct lock_class *class;

    key = lock->key->subkeys + subclass;
    hash_head = classhashentry(key);

    /* 해시 테이블에서 기존 클래스 검색 */
    hlist_for_each_entry_rcu(class, hash_head, hash_entry) {
        if (class->key == key)
            return class;
    }
    /* 새 클래스 할당 — 정적 배열에서 가져옴 */
    class = lock_classes + nr_lock_classes++;
    /* ... 초기화 및 해시 등록 ... */
    return class;
}

잠금 의존성 그래프 구축

lockdep는 스레드가 잠금을 획득할 때마다, 현재 보유 중인 모든 잠금과 새로 획득하는 잠금 사이에 의존성 간선(dependency edge)을 추가합니다. 이 간선은 struct lock_list로 표현됩니다.

/* kernel/locking/lockdep_internals.h */
struct lock_list {
    struct list_head        entry;
    struct lock_class       *class;        /* 대상 클래스 */
    struct lock_class       *links_to;    /* 연결된 클래스 */
    struct lock_trace       *trace;       /* 의존성이 기록된 스택 트레이스 */
    u16                     distance;    /* 재귀 깊이 */
    u8                      dep;         /* 의존성 유형 비트 */
    struct lock_list       *parent;      /* BFS 경로 추적용 */
};

간선 생성 과정

스레드가 잠금 A를 보유한 채 잠금 B를 획득하면:

1. A의 locks_after 리스트에 B를 가리키는 lock_list를 추가합니다 (forward dependency).
2. B의 locks_before 리스트에 A를 가리키는 lock_list를 추가합니다 (backward dependency).
3. 이미 같은 간선이 존재하면 건너뜁니다 (중복 방지).

/* kernel/locking/lockdep.c — check_prev_add() 간선 추가 핵심 */
static int check_prev_add(
    struct task_struct *curr,
    struct held_lock *prev,     /* 기존 보유 잠금 */
    struct held_lock *next,     /* 새로 획득하는 잠금 */
    ...)
{
    /* 1. 순환 검사 (BFS) */
    ret = check_noncircular(next, prev, ...);
    if (!ret)
        return 0;  /* 순환 발견 → 경고 출력 */

    /* 2. IRQ 안전성 검사 */
    ret = check_irq_usage(curr, prev, next);

    /* 3. 간선 추가 */
    add_lock_to_list(prev_class, next_class,
                     &prev_class->locks_after, ...);
    add_lock_to_list(next_class, prev_class,
                     &next_class->locks_before, ...);
}

순환 탐지 알고리즘

lockdep는 새로운 의존성 간선 A→B를 추가하기 전에, B에서 A로 도달 가능한 경로가 있는지 BFS(너비 우선 탐색)로 검사합니다. 경로가 존재하면 A→B 간선을 추가했을 때 순환이 생기므로, 잠재적 교착으로 보고합니다.

/* kernel/locking/lockdep.c — check_noncircular() */
static enum bfs_result
check_noncircular(struct held_lock *src,
                  struct held_lock *target, ...)
{
    /*
     * src의 forward 의존성을 BFS로 탐색하여
     * target에 도달 가능한지 확인
     * → 도달 가능하면 순환 존재
     */
    result = __bfs_forwards(&this, target,
                            class_equal, ...);
    if (result == BFS_RMATCH)
        print_circular_bug(...);  /* 순환 보고 */
    return result;
}

BFS 구현 세부사항

lock_acquire() 후킹 메커니즘

모든 잠금 API(spin_lock(), mutex_lock(), down_read() 등)는 실제 잠금 획득 전에 lock_acquire()를 호출하여 lockdep에 잠금 획득 의도를 알립니다. 이 함수가 lockdep의 핵심 진입점(Entry Point)입니다.

/* kernel/locking/lockdep.c */
void lock_acquire(
    struct lockdep_map *lock,  /* 잠금 인스턴스 */
    unsigned int subclass,    /* 서브클래스 번호 */
    int trylock,               /* trylock 여부 */
    int read,                  /* 읽기 잠금 여부 */
    int check,                 /* 검사 수준 */
    struct lockdep_map *nest_lock, /* 중첩 잠금 */
    unsigned long ip)        /* 호출 위치 IP */
{
    struct task_struct *curr = current;

    /* 1. lockdep 비활성화 상태이면 리턴 */
    if (unlikely(!debug_locks))
        return;

    /* 2. 재진입 방지 */
    if (unlikely(curr->lockdep_recursion))
        return;

    raw_local_irq_save(flags);
    curr->lockdep_recursion++;

    /* 3. 핵심 검증 로직 */
    __lock_acquire(lock, subclass, trylock,
                   read, check, irqs_disabled_flags(flags),
                   nest_lock, ip, 0, 0);

    curr->lockdep_recursion--;
    raw_local_irq_restore(flags);
}

__lock_acquire() 처리 단계

held_lock 구조체는 현재 태스크가 보유 중인 잠금의 정보를 담습니다. task_struct의 held_locks 배열은 최대 MAX_LOCK_DEPTH(기본 48)개까지 중첩을 추적합니다:

/* include/linux/lockdep_types.h */
struct held_lock {
    u64                     prev_chain_key; /* 이전 체인 해시 */
    unsigned long           acquire_ip;    /* 획득 위치 IP */
    struct lockdep_map      *instance;      /* 잠금 인스턴스 */
    struct lockdep_map      *nest_lock;     /* 중첩 잠금 */
    unsigned int            class_idx:13;  /* lock_class 인덱스 */
    unsigned int            irq_context:2; /* IRQ 컨텍스트 */
    unsigned int            trylock:1;     /* trylock 호출 */
    unsigned int            read:2;        /* 읽기 잠금 */
    unsigned int            check:1;       /* 검사 활성화 */
    unsigned int            hardirqs_off:1; /* 하드 IRQ 비활성 */
    unsigned int            waittime_stamp; /* LOCK_STAT 대기 시작 */
    unsigned int            holdtime_stamp; /* LOCK_STAT 보유 시작 */
};

lock_release() 후킹 메커니즘

잠금 해제 시 lock_release()가 호출됩니다. lock_acquire()에 비해 단순하지만, 중요한 일관성 검사를 수행합니다.

/* kernel/locking/lockdep.c */
void lock_release(
    struct lockdep_map *lock,
    unsigned long ip)
{
    /* 1. held_lock 스택에서 해당 잠금 찾기 */
    /* 2. 스택에서 제거 (LIFO 아닌 경우 경고) */
    /* 3. 잠금 깊이(depth) 감소 */
    /* 4. LOCK_STAT: 보유 시간 기록 */
    __lock_release(lock, ip);
}

해제 시 검사 항목

IRQ 안전성 검증

lockdep는 잠금의 IRQ 안전성을 추적하여, 인터럽트 컨텍스트에서 발생할 수 있는 교착을 감지합니다. 핵심 규칙은 단순합니다:

IRQ 상태 추적 메커니즘

lockdep는 각 잠금 클래스에 대해 4가지 IRQ 사용 상태를 추적합니다:

/* /proc/lockdep 출력 예시 */
 all lock classes:
 ---- ----  rcu_read_lock
 ..+. ..+.  &rq->__lock
 ..-- ..--  &sb->s_type->i_lock_key

wait_type 검사: sleep-in-atomic 감지

lockdep의 wait_type 검사는 잘못된 컨텍스트에서 슬립(Sleep) 가능 잠금을 사용하는 것을 방지합니다. 각 잠금은 생성 시 wait_type이 지정됩니다:

/* kernel/locking/lockdep.c — check_wait_context() */
static int check_wait_context(
    struct task_struct *curr,
    struct held_lock *next)
{
    /*
     * 현재 컨텍스트의 wait_type(innermost lock 기준)과
     * 새로 획득하려는 잠금의 wait_type을 비교
     *
     * 규칙: inner wait_type <= outer wait_type
     * 위반 시: "possible sleeping function called from"
     */
    short curr_inner = current_wait_type(curr);
    short next_outer = next->class->wait_type_outer;

    if (curr_inner < next_outer)
        return 0;  /* 위반: spin 컨텍스트에서 sleep lock 시도 */
}

lockdep 어노테이션 (nest_lock, subclass)

커널의 일부 코드는 의도적으로 같은 클래스의 잠금을 여러 개 동시에 보유합니다 (예: inode 잠금 중첩). lockdep는 이를 "possible recursive locking"으로 오경보할 수 있으므로, 개발자는 어노테이션으로 합법적인 중첩임을 표시합니다.

서브클래스 어노테이션

/* 같은 종류의 잠금을 중첩 획득 — 서브클래스로 구분 */
mutex_lock_nested(&parent->i_mutex, I_MUTEX_PARENT);
mutex_lock_nested(&child->i_mutex, I_MUTEX_CHILD);
/*
 * I_MUTEX_PARENT = 0, I_MUTEX_CHILD = 1
 * lockdep는 subclass 0과 subclass 1을 다른 클래스로 취급
 * → recursive locking 경고 회피
 */

/* spin_lock_nested 예시 */
spin_lock_nested(&lock, SINGLE_DEPTH_NESTING);

lockdep_set_class / lockdep_set_subclass

/* 잠금에 다른 클래스 키 지정 */
static struct lock_class_key my_special_key;
lockdep_set_class(&lock->dep_map, &my_special_key);

/* 서브클래스만 변경 */
lockdep_set_subclass(&lock->dep_map, 2);

nest_lock 어노테이션

/* nest_lock: 상위 잠금을 중첩 기준으로 지정 */
mutex_lock_nest_lock(&child->i_mutex, &parent->i_mutex);
/*
 * child의 i_mutex는 parent의 i_mutex를 보유한 상태에서만
 * 획득된다고 lockdep에 알림
 */

주요 어노테이션 API 정리

Cross-release 의존성

일반적인 잠금은 같은 컨텍스트(함수/스레드)에서 획득과 해제가 이루어집니다. 하지만 일부 동기화 패턴은 한 컨텍스트에서 획득하고 다른 컨텍스트에서 해제합니다 — completion, 페이지(Page) 잠금 등이 그 예입니다.

cross-release의 도전

lockdep의 기본 모델은 held_lock 스택이 LIFO(또는 유사 LIFO)로 동작한다고 가정합니다. Cross-release 패턴은 이 가정을 깨뜨리므로, 일반 lockdep로는 추적이 어렵습니다.

/* Cross-release 패턴 예시: completion */
/* Thread A */
wait_for_completion(&done);  /* "잠금 획득" — 여기서 대기 */

/* Thread B */
complete(&done);             /* "잠금 해제" — 다른 스레드에서 해제 */

/proc/lockdep, /proc/lockdep_stats, /proc/lockdep_chains

lockdep는 /proc 파일시스템(Filesystem)을 통해 현재 상태를 노출합니다. 디버깅과 시스템 분석에 핵심적인 인터페이스입니다.

/proc/lockdep

등록된 모든 잠금 클래스와 그 의존성을 출력합니다:

# 등록된 잠금 클래스 목록 조회
$ cat /proc/lockdep | head -20
all lock classes:
 ---- ----  rcu_read_lock
 ---- ----  rcu_callback
 ..+. ..+.  &rq->__lock
 ...+ ...+  &p->pi_lock
 ..-- ..--  &sb->s_type->i_mutex_key#2

/proc/lockdep_stats

$ cat /proc/lockdep_stats
 lock-classes:                         1423
 direct dependencies:                  8752
 indirect dependencies:                45123
 all direct dependencies:              17504
 dependency chains:                    12847
 dependency chain hlocks used:         48231
 dependency chain hlocks lost:         0
 in-hardirq chains:                    234
 in-softirq chains:                    456
 in-process chains:                    12157
 stack-trace entries:                  89432
 max locking depth:                    15
 max bfs queue depth:                  312
 debug_locks:                          1

/proc/lockdep_chains

관찰된 잠금 획득 체인(순서)을 모두 나열합니다:

$ cat /proc/lockdep_chains | head -10
all lock chains:
irq_context: 0
[ffffffc000123456] &rq->__lock
[ffffffc000789abc] &p->pi_lock

irq_context: 0
[ffffffc000234567] &sb->s_type->i_mutex_key
[ffffffc000345678] &sb->s_type->i_mutex_key#2

lockdep 경고 메시지 해석

lockdep 경고는 dmesg에 상세한 정보를 포함합니다. 경고 메시지의 구조를 이해하면 문제를 빠르게 진단할 수 있습니다.

경고 메시지 구조

======================================================
WARNING: possible circular locking dependency detected
6.8.0-rc1 #1 Not tainted
------------------------------------------------------
kworker/0:1/123 is trying to acquire lock:
ffff888012345678 (&sb->s_type->i_mutex_key), at: ext4_file_write_iter+0x123/0x456

but task is already holding lock:
ffff888087654321 (jbd2_handle), at: start_this_handle+0x78/0x9ab

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #1 (&sb->s_type->i_mutex_key):
       lock_acquire+0xd1/0x2e0
       down_write+0x44/0xc0
       ext4_map_blocks+0x234/0x567
       ...

-> #0 (jbd2_handle):
       lock_acquire+0xd1/0x2e0
       start_this_handle+0x78/0x9ab
       ...

other info that might help us debug this:
 Possible unsafe locking scenario:
       CPU0                    CPU1
       ----                    ----
  lock(jbd2_handle);
                               lock(&sb->s_type->i_mutex_key);
                               lock(jbd2_handle);
  lock(&sb->s_type->i_mutex_key);

                *** DEADLOCK ***

경고 읽는 법

1. 제목: 경고 유형 (circular, inconsistent, recursive 등)
2. 현재 시도: 어떤 태스크가 어떤 잠금을 획득하려 하는지
3. 기존 보유: 이미 보유 중인 잠금
4. 의존성 체인: 역순으로 보여주는 의존성 경로
5. 교착 시나리오: 구체적인 CPU별 교착 재현 순서
6. 스택 트레이스: 각 의존성이 기록된 코드 경로

주요 경고 유형과 해결법

1. possible circular locking dependency

가장 흔한 경고로, 잠금 획득 순서가 다른 곳에서 역전된 것을 감지합니다.

2. inconsistent {SOFTIRQ-ON-W} -> {IN-SOFTIRQ-W} usage

IRQ 안전성 불일치입니다. 한 곳에서는 IRQ 활성 상태로 잠금을 잡고, 다른 곳에서는 IRQ 핸들러 안에서 같은 잠금을 잡습니다.

/* 문제 코드 */
spin_lock(&my_lock);    /* softirq 활성 상태 */
...
/* softirq 핸들러 */
spin_lock(&my_lock);    /* softirq에서 같은 잠금! */

/* 수정: softirq에서도 사용되면 _bh 변형 사용 */
spin_lock_bh(&my_lock); /* softirq 비활성화 */

3. possible recursive locking detected

같은 잠금 클래스를 중첩 획득합니다. 의도된 경우 서브클래스 어노테이션으로 해결합니다.

/* 문제: 디렉터리 inode와 파일 inode의 i_rwsem 중첩 */
inode_lock(dir);
inode_lock(inode);  /* 같은 클래스 → recursive 경고 */

/* 수정: 서브클래스로 구분 */
inode_lock(dir);                                    /* subclass 0 */
inode_lock_nested(inode, I_MUTEX_CHILD);             /* subclass 1 */

4. BUG: sleeping function called from invalid context

원자적(Atomic) 컨텍스트(spinlock 보유, IRQ 비활성 등)에서 슬립 가능 함수를 호출합니다.

PROVE_LOCKING 동작 원리

CONFIG_PROVE_LOCKING은 lockdep의 핵심 기능을 활성화하는 커널 설정입니다. 이 옵션이 켜지면 모든 잠금 API에 계측 코드가 삽입됩니다.

PROVE_LOCKING이 활성화하는 기능

/* include/linux/lockdep.h — PROVE_LOCKING 비활성 시 */
#ifndef CONFIG_PROVE_LOCKING
#define lock_acquire(l, s, t, r, c, n, i)   do { } while (0)
#define lock_release(l, i)                  do { } while (0)
/* → 모든 lockdep 계측이 no-op이 됨 */
#endif

LOCK_STAT: 잠금 경합(Lock Contention) 통계

CONFIG_LOCK_STAT는 lockdep 인프라를 활용하여 잠금 경합(contention) 통계를 수집합니다. 성능 분석에 매우 유용합니다.

/proc/lock_stat 데이터

$ cat /proc/lock_stat | head -20
lock_stat version 0.4
-------------------------------------------------------------------
                              class name    con-bounces    contentions
                              ---------    -----------    -----------
                         &rq->__lock:        51234          12045
                         &p->pi_lock:         8234           2134
              &sb->s_type->i_mutex_key:       3456            891

                              class name    waittime-min    waittime-max
                              ---------    ------------    ------------
                         &rq->__lock:           0.12         145.67
                         &p->pi_lock:           0.05          23.45

통계 컬럼 설명

# LOCK_STAT 초기화 (통계 리셋)
$ echo 0 > /proc/lock_stat

lockdep 자체 디버깅

lockdep 자체가 비활성화되거나 오동작할 때의 진단 방법입니다.

debug_locks가 꺼지는 경우

lockdep는 내부 일관성 오류를 감지하면 스스로를 비활성화합니다(debug_locks = 0). 이 상태가 되면 이후 모든 검증이 중단됩니다.

# debug_locks 상태 확인
$ cat /proc/lockdep_stats | grep debug_locks
 debug_locks:                          1    # 1 = 정상, 0 = 비활성

# lockdep가 꺼진 원인은 dmesg에서 확인
$ dmesg | grep -i "lockdep\|DEBUG_LOCKS_WARN"

비활성화 주요 원인

lockdep 오버헤드

lockdep는 디버깅 도구이므로 런타임 오버헤드가 존재합니다. 프로덕션 커널에서는 일반적으로 비활성화됩니다.

오버헤드 분석

오버헤드 경감 기법

• 체인 캐시 — lock_chain 해시로 이전 검증 결과를 재사용합니다. 대부분의 잠금 획득은 캐시 히트로 처리됩니다.
• class_cache — lockdep_map 내의 캐시로 해시 테이블 조회를 회피합니다.
• trylock 최적화 — trylock은 의존성 간선을 추가하지 않습니다 (교착 불가).
• debug_locks 비활성화 — 심각한 오류 시 lockdep를 완전히 끄고 no-op으로 전환합니다.

관련 커널 설정

권장 디버그 설정

# 개발/테스트 커널 권장 설정
CONFIG_PROVE_LOCKING=y       # 의존성 추적 + 순환 탐지
CONFIG_LOCK_STAT=y           # 경합 통계
CONFIG_DEBUG_LOCKDEP=y       # lockdep 내부 디버깅
CONFIG_DEBUG_ATOMIC_SLEEP=y  # might_sleep() 검사 강화
CONFIG_LOCKDEP_CHAINS_BITS=16 # 체인 해시 크기 (기본 16)

# 프로덕션 커널 — lockdep 비활성
# CONFIG_PROVE_LOCKING is not set
# CONFIG_LOCK_STAT is not set

__lock_acquire()/validate_chain() 소스 분석

__lock_acquire()는 lockdep의 가장 핵심적인 내부 함수로, 약 200줄의 복잡한 제어 흐름을 가집니다. 이 함수가 호출되면 잠금 클래스 등록부터 의존성 그래프 검증까지 전 과정이 수행됩니다.

__lock_acquire() 전체 경로

/* kernel/locking/lockdep.c — __lock_acquire() 핵심 흐름 */
static int __lock_acquire(
    struct lockdep_map *lock,
    unsigned int subclass,
    int trylock, int read,
    int check, int hardirqs_off,
    struct lockdep_map *nest_lock,
    unsigned long ip,
    int references, int pin_count)
{
    struct task_struct *curr = current;
    struct lock_class *class;
    struct held_lock *hlock;
    int depth, chain_head;

    /* ① lock_class 조회 또는 신규 등록 */
    class = register_lock_class(lock, subclass, 0);
    if (!class)
        return 0;

    /* ② depth 한계 검사: MAX_LOCK_DEPTH(48) 초과 여부 */
    depth = curr->lockdep_depth;
    if (depth >= MAX_LOCK_DEPTH) {
        debug_locks_off();
        return 0;
    }

    /* ③ held_lock 초기화 및 스택에 push */
    hlock = curr->held_locks + depth;
    hlock->class_idx = class_idx(class);
    hlock->acquire_ip = ip;
    hlock->trylock = trylock;
    hlock->read = read;
    hlock->irq_context = task_irq_context(curr);

    /* ④ wait_type 검사 (sleep-in-atomic 감지) */
    if (!check_wait_context(curr, hlock))
        return 0;

    /* ⑤ 이전 체인 키로 체인 해시 계산 */
    hlock->prev_chain_key = chain_key;
    chain_key = iterate_chain_key(chain_key,
                    hlock_id(hlock));

    /* ⑥ 체인 캐시 조회 → 히트이면 BFS 건너뜀 */
    if (lookup_chain_cache(curr, hlock, chain_key))
        return 1; /* 이전 검증 통과 */

    /* ⑦ 새로운 체인 → validate_chain() 호출 */
    if (!validate_chain(curr, hlock, chain_head, chain_key))
        return 0;

    curr->lockdep_depth++;
    return 1;
}

validate_chain() 내부

validate_chain()은 새로운 의존성 체인이 관찰될 때 호출됩니다. 현재 보유 중인 잠금들과 새 잠금 사이의 관계를 검증합니다.

/* kernel/locking/lockdep.c — validate_chain() */
static int validate_chain(
    struct task_struct *curr,
    struct held_lock *hlock,
    int chain_head, u64 chain_key)
{
    /*
     * held_locks 스택의 각 이전 잠금에 대해
     * check_prev_add()로 의존성 간선 검증
     */
    for (i = curr->lockdep_depth - 1; i >= 0; i--) {
        struct held_lock *prev = curr->held_locks + i;

        /* prev→hlock 의존성 검증 */
        if (!check_prev_add(curr, prev, hlock, ...))
            return 0;

        /* 같은 IRQ 컨텍스트에서만 의존성 추적 */
        if (prev->irq_context != hlock->irq_context)
            break;
    }

    /* 새 체인 해시 등록 */
    add_chain_cache(curr, hlock, chain_key);
    return 1;
}

check_prev_add() 상세

check_prev_add()는 prev→next 의존성 간선을 추가하기 전에 3가지 핵심 검증을 수행합니다.

/* kernel/locking/lockdep.c — check_prev_add() 핵심 */
static int check_prev_add(
    struct task_struct *curr,
    struct held_lock *prev,
    struct held_lock *next, ...)
{
    struct lock_class *prev_class = hlock_class(prev);
    struct lock_class *next_class = hlock_class(next);

    /* trylock은 의존성 간선을 생성하지 않음 */
    if (next->trylock)
        return 1;

    /* 동일 클래스 → 재귀 잠금 검사 */
    if (prev_class == next_class)
        return check_deadlock(curr, next);

    /* ① 순환 검사: next의 forward deps에서 prev에 도달? */
    ret = check_noncircular(next, prev, ...);
    if (ret == BFS_RMATCH)
        return 0;  /* 순환 감지! */

    /* ② IRQ 안전성 검사 */
    if (!check_irq_usage(curr, prev, next))
        return 0;

    /* ③ 중복 간선(redundant) 검사 → 이미 prev→next 경로 있으면 스킵 */
    ret = check_redundant(prev, next);
    if (ret == BFS_RMATCH)
        return 1;  /* 이미 간선 존재, 추가 불필요 */

    /* 간선 추가: prev_class→next_class */
    add_lock_to_list(prev_class, next_class,
                     &prev_class->locks_after, ...);
    add_lock_to_list(next_class, prev_class,
                     &next_class->locks_before, ...);
    return 1;
}

BFS 순환 탐지 구현 분석

lockdep의 순환 탐지는 __bfs() 함수를 기반으로 합니다. 이 함수는 의존성 그래프에서 너비 우선 탐색을 수행하며, forward(locks_after) 방향과 backward(locks_before) 방향 모두 지원합니다.

__bfs() 핵심 구현

/* kernel/locking/lockdep.c — __bfs() */
static enum bfs_result __bfs(
    struct lock_list *source_entry,
    void *data,
    bool (*match)(struct lock_list *, void *),
    bool forward,
    struct lock_list **target_entry)
{
    struct lock_list *entry;
    struct lock_list *lock;
    struct list_head *head;
    struct circular_queue *cq = &__bfs_queue;
    unsigned int bfs_visited = 0;

    /* 큐 초기화 */
    __cq_init(cq);
    __cq_enqueue(cq, source_entry);

    while (__cq_dequeue(cq, &lock)) {
        /* 방문 카운트 제한: MAX_CIRCULAR_QUEUE_SIZE */
        if (++bfs_visited >= MAX_CIRCULAR_QUEUE_SIZE)
            return BFS_EQUEUEFULL;

        /* forward: locks_after, backward: locks_before */
        head = forward ?
            &hlock_class(lock)->locks_after :
            &hlock_class(lock)->locks_before;

        /* 인접 노드 순회 */
        list_for_each_entry(entry, head, entry) {
            /* 세대 번호로 방문 체크 (비트맵 불필요) */
            if (!lock_accessed(entry))
                continue;

            /* 매칭 콜백으로 타겟 확인 */
            if (match(entry, data)) {
                *target_entry = entry;
                return BFS_RMATCH;
            }

            /* parent 포인터 설정 (경로 역추적용) */
            entry->parent = lock;
            __cq_enqueue(cq, entry);
        }
    }

    return BFS_RNOMATCH;
}

circular_queue 자료구조

BFS에 사용되는 큐는 정적으로 할당된 원형 큐입니다. 동적 메모리 할당이 잠금 컨텍스트에서 불가능하므로, 고정 크기 배열을 사용합니다.

/* kernel/locking/lockdep.c */
#define MAX_CIRCULAR_QUEUE_SIZE  4096

struct circular_queue {
    struct lock_list *element[MAX_CIRCULAR_QUEUE_SIZE];
    unsigned int front;
    unsigned int rear;
};

/* Per-CPU BFS 큐 (재진입 방지) */
static DEFINE_PER_CPU(struct circular_queue, bfs_queue);

Forward vs Backward 탐색

경로 복원과 순환 보고

순환이 탐지되면 print_circular_bug()가 호출됩니다. 각 lock_list 노드의 parent 포인터를 역추적하여 전체 순환 경로를 복원합니다.

/* 순환 경로 출력 예시 */
/*
 * Chain exists of:
 *   &A → &B → &C → &A
 *
 * Possible unsafe locking scenario:
 *       CPU0                    CPU1
 *       ----                    ----
 *  lock(&A);
 *                               lock(&C);
 *                               lock(&A);  ← deadlock
 *  lock(&B);
 */

IRQ 안전성 검증 소스 분석

lockdep의 IRQ 안전성 검증은 check_irq_usage()를 통해 수행됩니다. 잠금이 인터럽트 컨텍스트에서 사용되는지(IRQ-safe) 아닌지(IRQ-unsafe)를 추적하고, 두 타입 간의 의존성 역전을 감지합니다.

IRQ 사용 플래그

각 lock_class는 IRQ 컨텍스트에서의 사용 여부를 비트 마스크로 추적합니다.

/* include/linux/lockdep_types.h — usage bits */
enum lock_usage_bit {
    LOCK_USED_IN_HARDIRQ,          /* hardirq에서 사용됨 */
    LOCK_USED_IN_SOFTIRQ,          /* softirq에서 사용됨 */
    LOCK_USED_IN_HARDIRQ_READ,     /* hardirq에서 읽기 잠금 */
    LOCK_USED_IN_SOFTIRQ_READ,     /* softirq에서 읽기 잠금 */
    LOCK_ENABLED_HARDIRQ,          /* hardirq 활성 상태에서 사용 */
    LOCK_ENABLED_SOFTIRQ,          /* softirq 활성 상태에서 사용 */
    LOCK_ENABLED_HARDIRQ_READ,     /* hardirq 활성 + 읽기 잠금 */
    LOCK_ENABLED_SOFTIRQ_READ,     /* softirq 활성 + 읽기 잠금 */
    LOCK_USED,                     /* 한 번이라도 사용됨 */
    LOCK_USAGE_STATES,             /* 총 상태 수 */
};

check_irq_usage() 검증 로직

/* kernel/locking/lockdep.c — check_irq_usage() 핵심 */
static int check_irq_usage(
    struct task_struct *curr,
    struct held_lock *prev,
    struct held_lock *next)
{
    /*
     * prev를 hardirq-unsafe로, next를 hardirq-safe로
     * 사용한 기록이 있으면 → 위험한 잠금 순서
     *
     * 시나리오: 프로세스 컨텍스트에서 L1→L2 순서로 잠금
     *   - L2가 hardirq에서도 사용되면 (USED_IN_HARDIRQ)
     *   - L1이 hardirq 활성 상태에서 사용되면 (ENABLED_HARDIRQ)
     *   → hardirq 발생 시: L2를 먼저 잡으려 하지만
     *     프로세스 컨텍스트가 L1을 잡고 L2를 기다릴 수 있음
     */

    /* Hardirq 검사 */
    if (!check_usage(curr, prev, next,
                     LOCK_USED_IN_HARDIRQ,
                     LOCK_ENABLED_HARDIRQ,
                     "hard"))
        return 0;

    /* Softirq 검사 */
    if (!check_usage(curr, prev, next,
                     LOCK_USED_IN_SOFTIRQ,
                     LOCK_ENABLED_SOFTIRQ,
                     "soft"))
        return 0;

    return 1;
}

static int check_usage(
    struct task_struct *curr,
    struct held_lock *prev,
    struct held_lock *next,
    enum lock_usage_bit bit_backwards,
    enum lock_usage_bit bit_forwards,
    const char *irqclass)
{
    /* backward 탐색: prev의 선행자 중 IRQ-safe 잠금이 있는가? */
    ret = find_usage_backwards(prev, bit_backwards, ...);

    /* forward 탐색: next의 후행자 중 IRQ-unsafe 잠금이 있는가? */
    ret = find_usage_forwards(next, bit_forwards, ...);

    /* 둘 다 발견되면 → IRQ 역전 보고 */
    if (backwards_match && forwards_match)
        return print_irq_inversion_bug(...);

    return 1;
}

mark_lock_irq(): 사용 비트 설정

잠금이 처음 특정 IRQ 컨텍스트에서 사용될 때 mark_lock_irq()가 호출되어 usage 비트를 설정합니다.

/* kernel/locking/lockdep.c */
static int mark_lock_irq(
    struct task_struct *curr,
    struct held_lock *this,
    enum lock_usage_bit new_bit)
{
    /* 이미 설정된 비트이면 빠른 리턴 */
    if (hlock_class(this)->usage_mask & (1 << new_bit))
        return 1;

    /* 새 비트 설정 */
    hlock_class(this)->usage_mask |= (1 << new_bit);

    /* 사용 위치 스택 트레이스 저장 */
    save_trace(hlock_class(this)->usage_traces + new_bit);

    /* 역방향 의존성 검사: 새 비트와 충돌하는 사용이 있는지 */
    return check_irq_usage_aggregate(curr, this);
}

IRQ 역전 시나리오

잠금 체인 해싱과 캐싱

lockdep의 성능은 체인 캐시에 크게 의존합니다. 매 lock_acquire()마다 BFS를 수행하면 오버헤드가 심각해지므로, 이전에 검증된 잠금 획득 순서(체인)를 해시하여 캐시합니다. 동일한 체인이 다시 관찰되면 검증을 건너뜁니다.

체인 키 계산: iterate_chain_key()

/* kernel/locking/lockdep.c — 체인 키 계산 */
static inline u64 iterate_chain_key(
    u64 key, u64 id)
{
    /*
     * 해시 함수: Jenkins의 mix 함수 변형
     * key = 이전 체인 키
     * id  = hlock_id(hlock) — 잠금 클래스+읽기/쓰기+IRQ 컨텍스트 인코딩
     */
    key = key * ITERATOR_HASH_MULT;
    key += id;
    key = (key >> 16) ^ key;
    return key;
}

/* hlock_id: 잠금 클래스 인덱스 + 컨텍스트 정보를 결합 */
static inline u64 hlock_id(
    struct held_lock *hlock)
{
    return (u64)hlock->class_idx |
           ((u64)hlock->read << 13);
}

chainhash_table 구조

/* kernel/locking/lockdep.c */
#define CHAINHASH_BITS       (CONFIG_LOCKDEP_CHAINS_BITS) /* 기본 16 */
#define CHAINHASH_SIZE       (1UL << CHAINHASH_BITS)
#define CHAINHASH_MASK       (CHAINHASH_SIZE - 1)

static struct hlist_head chainhash_table[CHAINHASH_SIZE];

/* lock_chain: 캐시된 의존성 체인 */
struct lock_chain {
    struct hlist_node   entry;     /* 해시 체인 */
    u64                 chain_key; /* 체인 해시 값 */
    int                 depth;     /* 체인 깊이 */
    int                 base;      /* chain_hlocks 인덱스 */
};

체인 캐시 조회

/* kernel/locking/lockdep.c — lookup_chain_cache() */
static int lookup_chain_cache(
    struct task_struct *curr,
    struct held_lock *hlock,
    u64 chain_key)
{
    struct hlist_head *hash_head;
    struct lock_chain *chain;

    hash_head = chainhash_table +
                (chain_key & CHAINHASH_MASK);

    hlist_for_each_entry(chain, hash_head, entry) {
        if (chain->chain_key == chain_key) {
            /* 캐시 히트: 이전 검증 결과 재사용 */
            return 1;
        }
    }

    /* 캐시 미스: validate_chain() 필요 */
    return 0;
}

해시 충돌 처리

체인 키는 64비트이므로 충돌 확률이 극히 낮지만, CHAINHASH_SIZE(65536)개의 버킷에 분산됩니다. 충돌 시 연결 리스트(hlist)로 체인링됩니다.

Cross-release 의존성 심층

일반적인 잠금은 같은 컨텍스트에서 획득하고 해제합니다. 그러나 completion, wait_for_completion(), 일부 비동기 패턴에서는 한 컨텍스트에서 잠금(또는 동기화 대기)을 시작하고, 다른 컨텍스트에서 해제(완료 신호)하는 cross-release 패턴이 발생합니다.

Cross-release 추적의 역사

Cross-release가 감지 못하는 교착

/* Cross-release 교착 패턴: lockdep가 감지하지 못함 */

/* Thread A */
mutex_lock(&lock_X);
wait_for_completion(&comp);  /* Thread B의 complete() 대기 */
mutex_unlock(&lock_X);

/* Thread B */
mutex_lock(&lock_X);        /* Thread A가 잡고 있음 → 대기 */
complete(&comp);            /* 여기 도달 못함 → deadlock */
mutex_unlock(&lock_X);

수동 어노테이션 기법

cross-release 의존성을 lockdep에 알리기 위해 lockdep_map을 수동으로 사용할 수 있습니다.

/* Cross-release 의존성을 lockdep에 수동 표현 */
static DEFINE_LOCKDEP_MAP(comp_map,
    "comp_dep", &comp_key, 0);

/* 대기 측 (Thread A) */
lock_acquire(&comp_map, 0, 0, 0, 1,
             NULL, _THIS_IP_);
wait_for_completion(&comp);
lock_release(&comp_map, _THIS_IP_);

/* 완료 측 (Thread B) — lock_release로 모델링 */
/* 주의: cross-context이므로 lockdep_map의
 * lock/unlock 쌍이 다른 태스크에서 수행되어
 * lock_release에서 "not held" 경고 발생 가능 */

Cross-release 대안 전략

lockdep 오버헤드 정량 분석

lockdep는 강력한 디버깅 도구이지만 상당한 런타임 비용을 수반합니다. 이 절에서는 메모리 사용량, CPU 오버헤드, 한계 값들을 정량적으로 분석합니다.

메모리 소비 분석

CPU 오버헤드 분석

lockdep 한계 값과 모니터링

/* /proc/lockdep_stats 주요 지표 */
$ cat /proc/lockdep_stats
 lock-classes:                         1234
 direct dependencies:                  5678
 indirect dependencies:               12345
 all direct dependencies:              9012
 dependency chains:                   23456
 dependency chain hlocks:             45678
 in-hardirq chains:                      89
 in-softirq chains:                     123
 in-process chains:                   23244
 stack-trace entries:                 98765
 max locking depth:                      15
 max bfs queue depth:                   234
 chain lookup hits:                 9876543
 chain lookup misses:                 23456
 cyclic checks:                       23456
 redundant checks:                    12345
 redundant links found:                6789
 find-hierarchical-usage:              5678
 find-usage-forwards checks:           3456
 find-usage-backwards checks:          2345

벤치마크 결과 (일반적 수치)

서브시스템: 네트워크 스택 lockdep

네트워크 스택은 커널에서 가장 복잡한 잠금 계층 구조를 가진 서브시스템 중 하나입니다. 소켓(Socket) 잠금, 해시 테이블 잠금, NAPI 잠금 등이 다양한 컨텍스트에서 중첩됩니다.

소켓 잠금 중첩

/* include/net/sock.h — 소켓 잠금 계층 */

/*
 * 소켓 잠금 순서 (lockdep 어노테이션 기반):
 *
 * 1. sk->sk_lock.slock        (BH-disabled spinlock)
 * 2. sk->sk_lock (owner)      (소프트웨어 mutex)
 * 3. sk->sk_receive_queue.lock
 * 4. sk->sk_write_queue.lock
 */

/* 소켓 잠금 nesting 레벨 정의 */
enum sock_lock_nesting {
    SINGLE_DEPTH_NESTING = 1,
    SOCK_LOCK_NESTING    = 2,  /* 소켓 내부 중첩 */
};

주소 패밀리별 잠금 키

네트워크 스택은 주소 패밀리(AF_INET, AF_INET6, AF_UNIX 등)별로 별도의 lock_class_key를 사용합니다. 이렇게 하지 않으면 서로 다른 프로토콜의 소켓 잠금이 동일한 클래스로 분류되어 거짓 양성(false positive)이 발생합니다.

/* net/core/sock.c — 주소 패밀리별 잠금 키 */
static struct lock_class_key
    af_family_keys[AF_MAX];
static struct lock_class_key
    af_family_slock_keys[AF_MAX];
static struct lock_class_key
    af_family_kern_keys[AF_MAX];

/* sock_init_data()에서 AF별 키 할당 */
void sock_init_data(struct socket *sock,
                    struct sock *sk)
{
    int family = sk->sk_family;

    lockdep_set_class_and_name(
        &sk->sk_lock.slock,
        af_family_slock_keys + family,
        af_family_slock_key_strings[family]);

    lockdep_init_map(
        &sk->sk_lock.dep_map,
        af_family_key_strings[family],
        af_family_keys + family, 0);
}

네트워크 lockdep 과제

주요 네트워크 lockdep 어노테이션

/* TCP 연결 수락 시 소켓 잠금 중첩 */
struct sock *inet_csk_accept(
    struct sock *sk, ...)
{
    /* 리스닝 소켓 잠금 (level 0) */
    lock_sock(sk);

    /* 새 연결 소켓 잠금 (level 1) */
    lock_sock_nested(newsk,
                     SINGLE_DEPTH_NESTING);
    ...
}

/* splice/tee 시 파이프+소켓 잠금 */
/* AF_UNIX: 두 소켓 간 교차 잠금 필요 */
static void unix_state_double_lock(
    struct sock *sk1,
    struct sock *sk2)
{
    /* 주소 순서로 잠금 획득 → ABBA 방지 */
    if (sk1 < sk2) {
        unix_state_lock(sk1);
        unix_state_lock_nested(sk2,
                    SINGLE_DEPTH_NESTING);
    } else {
        unix_state_lock(sk2);
        unix_state_lock_nested(sk1,
                    SINGLE_DEPTH_NESTING);
    }
}

서브시스템: MM lockdep 어노테이션

메모리 관리(MM) 서브시스템은 lockdep와 밀접하게 연동됩니다. mmap_lock, 페이지 테이블(Page Table) 잠금, 메모리 할당기 내부 잠금이 다양한 컨텍스트에서 중첩되며, 특히 fs_reclaim 어노테이션은 메모리 부족 시 잠재적 교착을 감지합니다.

mmap_lock과 lockdep

/* include/linux/mm_types.h */
struct mm_struct {
    struct rw_semaphore mmap_lock;
    /*
     * mmap_lock은 VMA 트리를 보호하는 핵심 잠금
     *
     * 잠금 순서 규칙:
     *   mmap_lock(write) → page table lock
     *   mmap_lock(read)  → page fault 처리
     *   mmap_lock        → i_rwsem (일부 경로)
     */
};

/* mm/mmap.c — mmap_lock lockdep 어노테이션 */
static inline void mmap_write_lock(
    struct mm_struct *mm)
{
    down_write(&mm->mmap_lock);
}

/* 중첩 mmap_lock (ptrace, fork 등) */
static inline void mmap_write_lock_nested(
    struct mm_struct *mm, int subclass)
{
    down_write_nested(&mm->mmap_lock,
                      subclass);
}

fs_reclaim 어노테이션

fs_reclaim은 메모리 회수(Memory Reclaim) 경로에서의 잠금 의존성을 추적하는 lockdep 어노테이션입니다. __GFP_FS 플래그가 있는 메모리 할당은 파일시스템 잠금을 획득할 수 있으며, 이미 파일시스템 잠금을 보유한 상태에서 메모리를 할당하면 교착이 발생할 수 있습니다.

/* mm/page_alloc.c — fs_reclaim lockdep */
static inline bool __need_fs_reclaim(
    gfp_t gfp_mask)
{
    /* GFP_NOFS/GFP_NOIO → fs_reclaim 불필요 */
    if (!(gfp_mask & __GFP_FS))
        return false;
    if (current->flags & PF_MEMALLOC)
        return false;
    return true;
}

/* mm/vmscan.c — fs_reclaim 어노테이션 */
static unsigned long
__perform_reclaim(gfp_t gfp_mask, ...)
{
    /* fs_reclaim 의존성 추적 시작 */
    fs_reclaim_acquire(gfp_mask);
    /*
     * lockdep에 가상 잠금 "fs_reclaim" 획득을 알림
     * 이 시점에 이미 잡고 있는 잠금과
     * fs_reclaim 사이의 의존성이 기록됨
     */

    ret = try_to_free_pages(...);

    fs_reclaim_release(gfp_mask);
    return ret;
}

fs_reclaim 교착 시나리오

/* fs_reclaim 교착 시나리오 */

/* Thread 1: 파일시스템 작업 */
mutex_lock(&inode->i_rwsem);
/* 메모리 할당 (GFP_KERNEL → __GFP_FS 포함) */
page = alloc_page(GFP_KERNEL);
/*
 * 메모리 부족 시 kswapd가 reclaim 수행
 * → try_to_free_pages()
 * → shrink_slab()
 * → super_operations->free_inode()
 * → mutex_lock(&other_inode->i_rwsem)  ← 같은 클래스!
 * → 잠재적 교착
 */
mutex_unlock(&inode->i_rwsem);

/* lockdep 경고: i_rwsem → fs_reclaim → i_rwsem (순환) */
/* 해결: GFP_NOFS 사용 */
page = alloc_page(GFP_NOFS);

GFP 플래그와 lockdep

페이지 테이블 잠금

/* include/linux/mm.h — 페이지 테이블 잠금 계층 */

/* PGD/P4D/PUD/PMD — mmap_lock 아래에서 보호 */
/* PTE — pte_lockptr()로 개별 잠금 */

/* 잠금 순서:
 * mmap_lock(write)
 *   → pmd_lock(pmd)
 *     → pte_lock(ptl)          ← page table lock
 *       → page lock (PG_locked)
 */

/* split page table lock: 각 PTE 페이지별 별도 잠금 */
#ifdef CONFIG_SPLIT_PTLOCK_CPUS
static inline spinlock_t *pte_lockptr(
    struct mm_struct *mm,
    pmd_t *pmd)
{
    return ptlock_ptr(pmd_page(*pmd));
}
#endif

커널 버전별 진화

lockdep는 2006년 v2.6.18에서 Ingo Molnar에 의해 도입된 이후 지속적으로 개선되어 왔습니다. 각 주요 버전에서의 변경 사항을 추적합니다.

진화 타임라인

wait_type 도입 (v5.0)

wait_type은 lockdep v5.0에서 도입된 중요한 기능으로, 잠금 컨텍스트의 "대기 가능 여부"를 분류합니다.

/* include/linux/lockdep_types.h — wait_type (v5.0+) */
enum lockdep_wait_type {
    LD_WAIT_INV   = 0,  /* 무효 (미설정) */
    LD_WAIT_FREE  = 1,  /* lock-free: rcu_read_lock, preempt_disable */
    LD_WAIT_SPIN  = 2,  /* spin-wait: raw_spinlock, spinlock */
    LD_WAIT_CONFIG= 2,  /* PREEMPT_RT에서 SLEEP으로 변경 가능 */
    LD_WAIT_SLEEP = 3,  /* sleep-wait: mutex, rwsem */
    LD_WAIT_MAX   = 4,
};

/*
 * 검사 규칙:
 *   LD_WAIT_FREE 컨텍스트 → LD_WAIT_SPIN/SLEEP 잠금 불가
 *   LD_WAIT_SPIN 컨텍스트 → LD_WAIT_SLEEP 잠금 불가
 *
 * 예: spin_lock() 내부에서 mutex_lock() → lockdep 경고
 */

lockdep_assert 매크로 진화

/* include/linux/lockdep.h — assertion 매크로 */

/* v2.6.18: 기본 assertion */
lockdep_assert_held(&lock);

/* v5.10+: 확장 assertion */
lockdep_assert_held_write(&lock);
lockdep_assert_held_read(&lock);
lockdep_assert_not_held(&lock);
lockdep_assert_held_once(&lock);

/* v5.15+: PREEMPT_RT 관련 */
lockdep_assert_preemption_disabled();
lockdep_assert_preemption_enabled();
lockdep_assert_in_softirq();

/* 구현: CONFIG_PROVE_LOCKING 비활성 시 no-op */
#ifdef CONFIG_PROVE_LOCKING
#define lockdep_assert_held(l) \
    WARN_ON(debug_locks && \
            !lockdep_is_held(l))
#else
#define lockdep_assert_held(l)  do { (void)(l); } while (0)
#endif

실전: 실제 커널 버그 lockdep 보고서 분석

lockdep 경고 메시지(splat)를 읽고 해석하는 능력은 커널 개발에서 필수적입니다. 이 절에서는 실제 패턴별 lockdep 보고서를 분석하고 수정 방법을 제시합니다.

lockdep splat 구조 해석

lockdep 경고 메시지는 일정한 구조를 따릅니다. 각 구성 요소를 이해하면 빠르게 원인을 파악할 수 있습니다.

/* lockdep splat 구조 분석 */

/* ① 헤더: 경고 유형 */
======================================================
WARNING: possible circular locking dependency detected
6.1.0-rc1 #1 Not tainted
------------------------------------------------------

/* ② 트리거: 어떤 프로세스가 어떤 잠금에서 */
kworker/0:1/123 is trying to acquire lock:
ffff888012345678 (&fs_info->tree_log_mutex){+.+.}-{3:3}
                   ^                         ^^^^   ^^^
                   잠금 이름              IRQ flags  wait_type

/* ③ IRQ 사용 플래그 해석:
 *   {+.+.} = {HARDIRQ, SOFTIRQ, HARDIRQ_READ, SOFTIRQ_READ}
 *   +: USED_IN_xxx 설정
 *   -: ENABLED_xxx 설정
 *   .: 미사용
 *   ?: 알 수 없음
 */

/* ④ 현재 보유 잠금 */
but task is already holding lock:
ffff888098765432 (&fs_info->reloc_mutex){+.+.}-{3:3}

/* ⑤ 의존성 체인 */
which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

/* ⑥ 체인 내 각 간선 */
-> #2 (&fs_info->tree_log_mutex){+.+.}-{3:3}:
       lock_acquire+0xd8/0x300
       mutex_lock_nested+0x1c/0x30
       btrfs_tree_log_wq_func+0x50/0x180
       ...

-> #1 (&fs_info->ordered_extent_mutex){+.+.}-{3:3}:
       ...

-> #0 (&fs_info->reloc_mutex){+.+.}-{3:3}:
       ...

/* ⑦ 순환 경로 요약 */
Chain exists of:
  tree_log_mutex --> ordered_extent_mutex --> reloc_mutex

/* ⑧ 교착 시나리오 */
Possible unsafe locking scenario:
      CPU0                    CPU1
      ----                    ----
 lock(reloc_mutex);
                              lock(tree_log_mutex);
                              lock(ordered_extent_mutex);
 lock(tree_log_mutex);   <-- deadlock!

IRQ 사용 플래그 참조표

{3:3}은 wait_type을 나타냅니다. {outer:inner} 형식으로, 3은 LD_WAIT_SLEEP입니다.

패턴 1: ABBA 순환 — 잠금 순서 통일

/* 문제: 두 경로에서 잠금 순서가 다름 */

/* 경로 A: commit_transaction() */
mutex_lock(&fs_info->reloc_mutex);
mutex_lock(&fs_info->tree_log_mutex);

/* 경로 B: btrfs_tree_log_wq_func() */
mutex_lock(&fs_info->tree_log_mutex);
mutex_lock(&fs_info->reloc_mutex);  /* 순환! */

/* 수정: 잠금 순서 통일 */
/* 규칙: reloc_mutex는 항상 tree_log_mutex보다 먼저 */
/* 경로 B 수정: */
mutex_lock(&fs_info->reloc_mutex);
mutex_lock(&fs_info->tree_log_mutex);

패턴 2: IRQ 역전 — irqsave 사용

/* 문제: 프로세스 컨텍스트에서 IRQ 비활성 없이 잠금 */

/* lockdep 경고:
 * WARNING: inconsistent lock state
 * inconsistent {IN-HARDIRQ-W} -> {HARDIRQ-ON-W} usage
 */

/* 프로세스 컨텍스트 (IRQ 활성) */
spin_lock(&dev->lock);  /* ENABLED_HARDIRQ 설정 */
...
spin_unlock(&dev->lock);

/* 인터럽트 핸들러 */
spin_lock(&dev->lock);  /* USED_IN_HARDIRQ 설정 → 충돌! */
...
spin_unlock(&dev->lock);

/* 수정: 프로세스 컨텍스트에서 IRQ 비활성 */
spin_lock_irqsave(&dev->lock, flags);
...
spin_unlock_irqrestore(&dev->lock, flags);

패턴 3: sleep-in-atomic — wait_type 경고

/* 문제: spinlock 내에서 sleep 가능 잠금 획득 */

/* lockdep 경고:
 * BUG: sleeping function called from invalid context
 * in_atomic(): 1, irqs_disabled(): 0
 * ... lock type mismatch, lock(&mtx) wait type: 3
 * held lock: &slock wait type: 2
 */

spin_lock(&slock);       /* LD_WAIT_SPIN (2) */
mutex_lock(&mtx);       /* LD_WAIT_SLEEP (3) → 위반! */
mutex_unlock(&mtx);
spin_unlock(&slock);

/* 수정 방법 1: spinlock 밖에서 mutex 획득 */
mutex_lock(&mtx);
spin_lock(&slock);
...
spin_unlock(&slock);
mutex_unlock(&mtx);

/* 수정 방법 2: spinlock을 mutex로 변경 (sleep 허용 경로인 경우) */

패턴 4: 재귀 잠금 — nest_lock/subclass

/* 문제: 같은 lock_class의 잠금을 중첩 획득 */

/* lockdep 경고:
 * WARNING: possible recursive locking detected
 * kworker/123 is trying to acquire lock:
 *   (&inode->i_rwsem){+.+.}-{3:3}
 * but task is already holding lock:
 *   (&inode->i_rwsem){+.+.}-{3:3}
 */

/* 디렉토리 → 파일 i_rwsem 중첩 (rename 등) */
inode_lock(dir);
inode_lock(child);  /* 같은 lock_class → 경고 */

/* 수정: 서브클래스 사용 */
inode_lock(dir);
inode_lock_nested(child, I_MUTEX_CHILD);

/* 또는 nest_lock 사용 */
mutex_lock_nest_lock(&child->i_rwsem,
                     &dir->i_rwsem);

lockdep splat 디버깅 체크리스트

흔한 거짓 양성(false positive) 사례

참고 자료

커널 공식 문서

• Runtime locking correctness validator — lockdep 설계 문서: lock_class, 의존성 그래프, 순환 탐지
• Lock Statistics — /proc/lock_stat 인터페이스와 contention 분석
• Lock types and their rules — lockdep이 검증하는 잠금 유형별 규칙
• The Kernel Concurrency Sanitizer (KCSAN) — lockdep과 보완적인 데이터 레이스 탐지기

LWN.net 심층 기사

• Lockdep: how to read its cryptic output (2013) — lockdep 출력 해석 완전 튜토리얼
• The kernel lock validator (2006) — Ingo Molnár의 lockdep 최초 소개
• Concurrency bugs should fear the big bad data-race detector (2019) — KCSAN과 lockdep의 상보적 역할
• Lockdep and crossrelease (2009) — cross-release 의존성 추적 확장

학술 자료 및 외부 참고

• Paul McKenney — "Is Parallel Programming Hard?" — 동기화 검증 방법론
• 커널 소스: kernel/locking/lockdep.c, include/linux/lockdep.h, kernel/locking/lockdep_internals.h
• /proc 인터페이스: /proc/lockdep, /proc/lockdep_chains, /proc/lockdep_stats, /proc/lock_stat
• syzkaller: syzbot dashboard — lockdep이 탐지한 커널 버그 현황

관련 문서

lockdep와 관련된 다른 동기화 및 디버깅 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• 동기화 기법 — 전체 동기화 프리미티브 비교 및 lockdep 개요
• 동기화 기법 — lockdep 섹션 — lockdep 아키텍처 요약
• Spinlock — qspinlock, lock contention, lockdep 연동
• Mutex — mutex_lock_nested, lockdep 디버깅
• Reader-Writer Lock — rwsem, lockdep 서브클래스
• RT Mutex — Priority Inheritance, 데드락 감지
• 동시성 디버깅 — KCSAN, lockdep, perf lock 통합 가이드
• preempt_count — 선점 모델과 컨텍스트 판별
• Atomic 연산 — CAS/cmpxchg, 메모리 순서 의미론
• 메모리 배리어(Memory Barrier) — acquire/release, 아키텍처별 메모리 모델