Hash Table

Linux 커널의 해시 테이블(Hash Table) 구현 전반을 다룹니다. hlist 자료구조, <linux/hashtable.h> API, 리사이즈 가능한 rhashtable, 커널 해시(Hash) 함수(hash_long, jhash), RCU 보호 해시 테이블, 그리고 conntrack·inode·pid 등 실제 커널 활용 사례까지 종합적으로 설명합니다.

개요 (Overview)

해시 테이블(Hash Table)은 키(key)를 해시 함수로 변환하여 버킷(bucket)에 매핑(Mapping)하는 자료구조입니다. 평균 O(1) 시간에 검색·삽입·삭제가 가능하여, 대량의 객체를 빠르게 룩업해야 하는 커널 서브시스템 전반에서 핵심적으로 사용됩니다.

리눅스 커널에서 해시 테이블이 사용되는 대표적인 영역:

• inode 캐시 — 파일시스템(Filesystem) inode를 빠르게 검색하는 inode_hashtable
• dentry 캐시 — 경로명 룩업을 가속하는 dentry_hashtable
• PID 해시 — find_task_by_vpid() 등에서 PID → task_struct 변환
• conntrack — Netfilter 연결 추적(Connection Tracking) 테이블 (nf_conntrack)
• 네트워크 소켓 — TCP/UDP 소켓 룩업 해시 (inet_ehash, udp_table)
• 모듈 심볼 — 커널 심볼 테이블(Symbol Table) 룩업
• 페이지 캐시(Page Cache) — 현재는 XArray, 과거는 radix tree 기반 인덱싱 구조(해시 테이블이 아닌 별도 계열, 역사적)

커널은 두 가지 주요 해시 테이블 구현을 제공합니다:

• <linux/hashtable.h> — 고정 크기, 단순하고 가벼운 구현
• <linux/rhashtable.h> — 자동 리사이즈, 대규모 동적 데이터셋에 적합

버킷 인덱스 계산의 실제

해시 테이블 성능을 제대로 이해하려면 “해시값을 버킷 인덱스로 줄이는 단계”를 분리해서 봐야 합니다. 핵심은 해시 혼합(mixing)과 인덱스 축소(index reduction)의 역할이 다르다는 점입니다.

• 해시 혼합 — 입력 키의 패턴(연속 값, 특정 비트 고정)을 깨뜨려 비트 분포를 균일하게 만듭니다. 예: hash_long(), jhash(), siphash().
• 인덱스 축소 — 32/64비트 해시값을 [0, bucket_count) 범위로 투영합니다. 예: & (size - 1), reciprocal_scale().

/* 2의 거듭제곱 버킷 수: hashtable.h 전형 패턴 */
u32 h = hash_long(key, bits);      /* mixing + 상위 bits 추출 */
u32 idx = h & ((1U << bits) - 1); /* range reduction */

/* 버킷 수가 2의 거듭제곱이 아닐 수 있는 경로: conntrack 등 */
u32 hash = jhash2(tuple_words, n, seed);
u32 bucket = reciprocal_scale(hash, hsize);

hlist 구조 (hlist_head / hlist_node)

해시 테이블의 각 버킷은 struct hlist_head로 표현되고, 체인 내의 각 노드는 struct hlist_node입니다. 일반적인 list_head와 달리 hlist는 비원형(non-circular) 단방향 리스트로 설계되었습니다.

/* 개념 예시: include/linux/types.h hlist 기본 정의 */
/* include/linux/types.h */
struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;  /* 이전 노드의 next 포인터를 가리킴 */
};

왜 pprev는 이중 포인터인가?

hlist_node의 pprev가 hlist_node *가 아닌 hlist_node **인 이유는 두 가지 핵심적인 이점 때문입니다:

• 메모리 절약 — hlist_head는 포인터 하나(first)만 가집니다. 원형 이중 연결 리스트인 list_head는 포인터 2개가 필요합니다. 버킷이 수천~수만 개인 해시 테이블에서 이 차이는 상당합니다.
• 통일된 삭제 연산 — pprev는 “이전 노드의 next 필드 주소” 또는 “헤드의 first 필드 주소”를 가리킵니다. 따라서 노드가 리스트의 첫 번째인지 중간인지 구분하지 않고 *pprev = next로 삭제가 가능합니다.

/* hlist 노드 삭제 — 위치에 관계없이 동일한 코드 */
static inline void __hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
    struct hlist_node **pprev = n->pprev;

    WRITE_ONCE(*pprev, next);      /* 이전 → 다음으로 연결 */
    if (next)
        WRITE_ONCE(next->pprev, pprev);
}

hlist vs list_head 비교

주요 hlist 매크로(Macro)/함수

/* 초기화 */
HLIST_HEAD(name);                          /* 정적 선언 + 초기화 */
HLIST_HEAD_INIT                             /* { .first = NULL } */
INIT_HLIST_HEAD(&head);                     /* 동적 초기화 */
INIT_HLIST_NODE(&node);                     /* 노드 초기화 */

/* 삽입/삭제 */
hlist_add_head(&node, &head);               /* 헤드 앞에 삽입 */
hlist_add_before(&node, &next_node);        /* 특정 노드 앞에 삽입 */
hlist_add_behind(&node, &prev_node);        /* 특정 노드 뒤에 삽입 */
hlist_del(&node);                            /* 삭제 */
hlist_del_init(&node);                      /* 삭제 후 초기화 */

/* 순회 */
hlist_for_each(pos, head)                    /* hlist_node* 순회 */
hlist_for_each_safe(pos, n, head)            /* 삭제 안전 순회 */
hlist_for_each_entry(obj, head, member)      /* 구조체 순회 */
hlist_for_each_entry_safe(obj, n, head, member) /* 삭제 안전 구조체 순회 */
hlist_entry(ptr, type, member)               /* container_of wrapper */

hlist 함수/매크로 내부 구현 상세

include/linux/list.h에 정의된 hlist 관련 함수와 매크로의 내부 구현을 한 줄씩 분석합니다. 단순 API 사용법을 넘어 포인터 조작의 원리를 이해하면, 디버깅과 커스텀 자료구조 설계에 큰 도움이 됩니다.

초기화 매크로 내부 구현

/* include/linux/list.h */

/* 정적 선언 + 초기화: 전역/파일 스코프에서 사용 */
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }

/* 동적 초기화: kmalloc 등으로 할당한 헤드를 런타임에 초기화 */
static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
    h->first = NULL;
}

/* 노드 초기화: pprev = NULL은 "어떤 리스트에도 속하지 않음"을 의미 */
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
    h->next = NULL;
    h->pprev = NULL;  /* hlist_unhashed() 판단 기준 */
}

상태 확인 함수 내부 구현

/* 노드가 어떤 hlist에도 연결되지 않았는지 확인 */
static inline int hlist_unhashed(const struct hlist_node *h)
{
    return !h->pprev;
    /* pprev == NULL → 리스트에 없음
     * pprev != NULL → 어딘가에 연결됨 (헤드의 first 또는 이전 노드의 next를 가리킴) */
}

/* 노드가 "fake" 상태인지 확인 (RCU teardown 등에서 사용) */
static inline bool hlist_fake(struct hlist_node *h)
{
    return h->pprev == &h->next;
    /* pprev가 자기 자신의 next를 가리키면 fake.
     * 실제 리스트에 연결되면 pprev는 다른 노드의 필드를 가리킴 */
}

/* hlist가 비어있는지 확인 */
static inline int hlist_empty(const struct hlist_head *h)
{
    return !READ_ONCE(h->first);
    /* READ_ONCE: 컴파일러 최적화로 인한 torn read 방지.
     * 다른 CPU가 동시에 first를 변경할 수 있으므로 원자적 읽기 필요 */
}

/* 노드가 리스트의 유일한 요소인지 확인 */
static inline bool hlist_is_singular_node(
    struct hlist_node *n, struct hlist_head *h)
{
    return !n->next && n->pprev == &h->first;
    /* next == NULL (뒤에 노드 없음) AND
     * pprev가 헤드의 first를 가리킴 (첫 번째 노드) → 유일한 노드 */
}

삽입 함수 내부 구현

/* ───────────────────────────────────────────────
 * hlist_add_head: 헤드의 맨 앞에 노드 삽입
 *
 * 삽입 전: head → [A] → [B] → NULL
 * 삽입 후: head → [N] → [A] → [B] → NULL
 * ─────────────────────────────────────────────── */
static inline void hlist_add_head(
    struct hlist_node *n,
    struct hlist_head *h)
{
    struct hlist_node *first = h->first;

    /* 1단계: n의 next가 기존 첫 노드를 가리킴 */
    n->next = first;

    /* 2단계: 기존 첫 노드가 있으면, 그 pprev를 n의 next로 갱신 */
    if (first)
        first->pprev = &n->next;

    /* 3단계: 헤드의 first가 n을 가리킴 */
    WRITE_ONCE(h->first, n);

    /* 4단계: n의 pprev가 헤드의 first 필드 주소를 가리킴 */
    n->pprev = &h->first;
}

/* ───────────────────────────────────────────────
 * hlist_add_before: 특정 노드 앞에 삽입
 *
 * 삽입 전: ... → [P] → [next] → ...
 * 삽입 후: ... → [P] → [N] → [next] → ...
 * ─────────────────────────────────────────────── */
static inline void hlist_add_before(
    struct hlist_node *n,
    struct hlist_node *next)
{
    /* 1단계: n의 pprev가 next의 pprev를 물려받음
     *         (이전 노드의 next 필드 또는 헤드의 first 필드를 가리킴) */
    n->pprev = next->pprev;

    /* 2단계: n의 next가 next를 가리킴 */
    n->next = next;

    /* 3단계: next의 pprev가 n의 next 필드를 가리킴 */
    next->pprev = &n->next;

    /* 4단계: 이전 노드(또는 헤드)가 n을 가리킴 */
    WRITE_ONCE(*(n->pprev), n);
}

/* ───────────────────────────────────────────────
 * hlist_add_behind: 특정 노드 뒤에 삽입
 *
 * 삽입 전: ... → [prev] → [A] → ...
 * 삽입 후: ... → [prev] → [N] → [A] → ...
 * ─────────────────────────────────────────────── */
static inline void hlist_add_behind(
    struct hlist_node *n,
    struct hlist_node *prev)
{
    /* 1단계: n의 next가 prev의 기존 next를 가리킴 */
    n->next = prev->next;

    /* 2단계: prev의 next가 n을 가리킴 */
    WRITE_ONCE(prev->next, n);

    /* 3단계: n의 pprev가 prev의 next 필드를 가리킴 */
    n->pprev = &prev->next;

    /* 4단계: n 뒤의 노드가 있으면 그 pprev를 갱신 */
    if (n->next)
        n->next->pprev = &n->next;
}

삭제 함수 내부 구현

/* 내부 헬퍼: 실제 포인터 연결 해제 */
static inline void __hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
    struct hlist_node **pprev = n->pprev;

    /* 핵심: 이전 노드(또는 헤드)가 n의 다음 노드를 직접 가리킴
     * pprev가 &head->first이면: head->first = next
     * pprev가 &prev->next이면: prev->next = next */
    WRITE_ONCE(*pprev, next);

    /* 다음 노드가 있으면 pprev를 갱신 */
    if (next)
        WRITE_ONCE(next->pprev, pprev);
}

/* 삭제 후 poison 마킹 — 재사용 시 커널 oops 유발 (버그 감지) */
static inline void hlist_del(struct hlist_node *n)
{
    __hlist_del(n);

    /* LIST_POISON1 = 0x100 + POISON_POINTER_DELTA
     * LIST_POISON2 = 0x122 + POISON_POINTER_DELTA
     * 삭제된 노드를 다시 사용하면 페이지 폴트 발생 → 버그 조기 발견 */
    n->next = LIST_POISON1;
    n->pprev = LIST_POISON2;
}

/* 삭제 후 초기화 — 동일 노드를 다시 삽입할 수 있음 */
static inline void hlist_del_init(struct hlist_node *n)
{
    if (!hlist_unhashed(n)) {
        __hlist_del(n);
        INIT_HLIST_NODE(n);  /* next = NULL, pprev = NULL */
    }
    /* 이미 unhashed 상태이면 아무것도 하지 않음 (안전한 no-op) */
}

이동/교체 함수 내부 구현

/* ───────────────────────────────────────────────
 * hlist_move_list: 한 헤드의 전체 리스트를 다른 헤드로 이동
 *
 * 이동 전: old → [A] → [B] → NULL,  new → (비어있어야 함)
 * 이동 후: old → NULL,              new → [A] → [B] → NULL
 *
 * 용도: 해시 테이블 리사이즈 시 버킷 이동, 배치 처리를 위한
 *       리스트 스냅샷 등에서 사용
 * ─────────────────────────────────────────────── */
static inline void hlist_move_list(
    struct hlist_head *old,
    struct hlist_head *new)
{
    /* 1단계: new가 old의 첫 노드를 가리킴 */
    new->first = old->first;

    /* 2단계: 첫 노드가 있으면, pprev를 new의 first로 갱신
     *         (첫 노드는 이제 new 헤드에 속함) */
    if (new->first)
        new->first->pprev = &new->first;

    /* 3단계: old를 빈 상태로 */
    old->first = NULL;
}

/* ───────────────────────────────────────────────
 * hlist_add_fake: 노드를 "fake" 상태로 설정
 *
 * pprev를 자기 자신의 next로 설정하여, hlist_fake()가 true를 반환하게 함.
 * 실제 리스트에 삽입된 것은 아니지만 hlist_unhashed()는 false를 반환함.
 *
 * 용도: RCU callback에서 아직 처리 중인 노드를 표시하거나,
 *       "삭제 예정이지만 아직 grace period가 끝나지 않은" 상태를 나타냄
 * ─────────────────────────────────────────────── */
static inline void hlist_add_fake(struct hlist_node *n)
{
    n->pprev = &n->next;
    /* 이 상태에서:
     * hlist_unhashed(n) → false (pprev != NULL)
     * hlist_fake(n) → true (pprev == &n->next) */
}

엔트리 접근 매크로 내부 구현

/* hlist_entry: hlist_node 포인터에서 포함하는 구조체의 포인터를 얻음
 * container_of()의 래퍼 — 타입 안전성과 가독성을 위해 별도 매크로로 제공 */
#define hlist_entry(ptr, type, member) \
    container_of(ptr, type, member)

/* hlist_entry_safe: ptr이 NULL일 수 있는 경우 안전한 접근
 * hlist_for_each_entry 내부에서 사용 — 체인 끝(NULL)에서 안전하게 종료 */
#define hlist_entry_safe(ptr, type, member) \
    ({ typeof(ptr) ____ptr = (ptr); \
       ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
    })

/* container_of 실제 동작:
 *
 * struct my_obj {
 *     int key;                    ← offset 0
 *     char data[32];              ← offset 4
 *     struct hlist_node hash;     ← offset 36 (member)
 * };
 *
 * hlist_entry(ptr, struct my_obj, hash)
 * → (struct my_obj *)((char *)ptr - offsetof(struct my_obj, hash))
 * → (struct my_obj *)((char *)ptr - 36)
 *
 * ptr이 hash 필드의 주소이므로, 36바이트를 빼면 구조체 시작 주소 */

순회 매크로 내부 구현

/* ═══════════════════════════════════════════════
 * hlist_for_each: hlist_node* 직접 순회 (raw 순회)
 *
 * 사용 빈도 낮음 — 대부분 hlist_for_each_entry 사용
 * ═══════════════════════════════════════════════ */
#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos ; pos = pos->next)

/* ═══════════════════════════════════════════════
 * hlist_for_each_safe: 순회 중 삭제가 가능한 버전
 *
 * n에 다음 노드를 미리 저장하므로, pos를 삭제해도
 * 순회가 중단되지 않음
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_safe(pos, n, head) \
    for (pos = (head)->first; \
         pos && ({ n = pos->next; 1; }); \
         pos = n)
    /* GCC statement expression ({ ... })으로 n에 다음 포인터를 저장
     * 항상 1을 반환하므로 루프 조건은 pos != NULL과 동일 */

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry: 구조체 레벨 순회 (가장 자주 사용)
 *
 * pos: 구조체 포인터 (struct my_obj *)
 * head: hlist_head 포인터
 * member: 구조체 내 hlist_node 멤버 이름
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry(pos, head, member) \
    for (pos = hlist_entry_safe((head)->first, \
                typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe((pos)->member.next, \
                typeof(*(pos)), member))
    /*
     * 전개 과정:
     * 1. head->first가 NULL이면 pos = NULL → 루프 진입 안 함
     * 2. head->first가 유효하면 hlist_entry_safe로 구조체 포인터 획득
     * 3. 반복: pos->member.next를 통해 다음 hlist_node로 이동,
     *    다시 hlist_entry_safe로 구조체 포인터 변환
     * 4. next가 NULL이면 hlist_entry_safe가 NULL 반환 → 루프 종료
     */

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry_safe: 순회 중 삭제 가능한 구조체 순회
 *
 * tmp: struct hlist_node * 임시 변수 (다음 노드 보관)
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry_safe(pos, tmp, head, member) \
    for (pos = hlist_entry_safe((head)->first, \
                typeof(*(pos)), member); \
         pos && ({ tmp = (pos)->member.next; 1; }); \
         pos = hlist_entry_safe(tmp, typeof(*(pos)), member))
    /* 패턴: 현재 pos의 next를 tmp에 저장 → pos를 삭제/kfree해도
     * tmp에서 다음 노드를 안전하게 추적 */

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry_continue: 지정 위치 다음부터 순회 시작
 *
 * pos가 가리키는 노드의 다음 노드부터 순회.
 * 중간에 순회를 중단했다가 이어서 진행할 때 사용
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry_continue(pos, member) \
    for (pos = hlist_entry_safe((pos)->member.next, \
                typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe((pos)->member.next, \
                typeof(*(pos)), member))

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry_from: 지정 위치부터(포함) 순회 시작
 *
 * pos가 가리키는 노드 자체부터 순회.
 * continue와 달리 현재 노드도 처리 대상에 포함
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry_from(pos, member) \
    for (; pos; \
         pos = hlist_entry_safe((pos)->member.next, \
                typeof(*(pos)), member))

hlist RCU 변형 내부 구현

include/linux/rculist.h에 정의된 RCU 변형은 기본 hlist 함수와 구조가 동일하되, 메모리 배리어와 의존성 순서(dependency ordering)가 추가됩니다. 읽기 측은 lock 없이 RCU read-side critical section에서 순회하고, 쓰기 측은 별도의 lock으로 상호 배제합니다.

/* include/linux/rculist.h */

/* ───────────────────────────────────────────────
 * hlist_add_head_rcu: RCU 보호 삽입
 *
 * hlist_add_head()와 포인터 조작은 동일하지만,
 * 읽기 측에 publish하는 최종 단계에서 rcu_assign_pointer()를 사용
 * ─────────────────────────────────────────────── */
static inline void hlist_add_head_rcu(
    struct hlist_node *n,
    struct hlist_head *h)
{
    struct hlist_node *first = h->first;

    n->next = first;
    WRITE_ONCE(n->pprev, &h->first);
    /* smp_wmb()가 내포됨: n의 모든 필드 초기화가
     * h->first 갱신보다 먼저 다른 CPU에 보임 */
    rcu_assign_pointer(hlist_first_rcu(h), n);
    if (first)
        WRITE_ONCE(first->pprev, &n->next);
}

/* ───────────────────────────────────────────────
 * hlist_add_before_rcu / hlist_add_behind_rcu
 * 기본 함수와 동일한 로직 + rcu_assign_pointer() 사용
 * ─────────────────────────────────────────────── */
static inline void hlist_add_behind_rcu(
    struct hlist_node *n,
    struct hlist_node *prev)
{
    n->next = prev->next;
    WRITE_ONCE(n->pprev, &prev->next);
    rcu_assign_pointer(hlist_next_rcu(prev), n);
    if (n->next)
        WRITE_ONCE(n->next->pprev, &n->next);
}

/* ───────────────────────────────────────────────
 * hlist_del_rcu: RCU 보호 삭제
 *
 * __hlist_del()로 링크를 끊되, next/pprev를 poison으로
 * 설정하지 않음. RCU grace period 동안 읽기 측이
 * 이 노드를 통해 다음 노드로 순회할 수 있어야 하기 때문
 * ─────────────────────────────────────────────── */
static inline void hlist_del_rcu(struct hlist_node *n)
{
    __hlist_del(n);

    /* next는 그대로 유지! poison 설정 안 함.
     * 삭제된 노드를 순회 중인 읽기 측이 next를 따라
     * 다음 노드에 안전하게 도달 가능 */
    n->pprev = LIST_POISON2;
    /* pprev만 poison: 삭제된 노드를 다시 삭제하려는 시도를 감지 */
}

/* ───────────────────────────────────────────────
 * hlist_del_init_rcu: RCU 보호 삭제 + 초기화
 *
 * hlist_del_rcu()와 달리 삭제 후 즉시 다른 리스트에
 * 재삽입할 수 있음. pprev를 NULL로 설정하여
 * hlist_unhashed()가 true를 반환
 * ─────────────────────────────────────────────── */
static inline void hlist_del_init_rcu(struct hlist_node *n)
{
    if (!hlist_unhashed(n)) {
        __hlist_del(n);
        n->pprev = NULL;
    }
}

hlist RCU 순회 매크로

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry_rcu: RCU read-side 구조체 순회
 *
 * rcu_read_lock() 구간 내에서 사용.
 * rcu_dereference()로 포인터를 읽어 의존성 순서를 보장
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry_rcu(pos, head, member) \
    for (pos = hlist_entry_safe( \
                rcu_dereference_raw(hlist_first_rcu(head)), \
                typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe( \
                rcu_dereference_raw(hlist_next_rcu( \
                    &(pos)->member)), \
                typeof(*(pos)), member))

/* RCU 포인터 접근 헬퍼:
 * hlist_first_rcu(head) → rcu_dereference(head->first)
 * hlist_next_rcu(node)  → rcu_dereference(node->next)
 *
 * rcu_dereference(): 포인터 읽기에 데이터 의존성 배리어 삽입.
 * Alpha 아키텍처에서 실제 배리어 명령 발행,
 * 다른 아키텍처에서는 컴파일러 배리어만 (하드웨어가 보장) */

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry_rcu_bh: softirq 보호 RCU 순회
 *
 * rcu_read_lock_bh() 구간에서 사용.
 * 네트워크 수신 경로(softirq)에서 주로 활용
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry_rcu_bh(pos, head, member) \
    for (pos = hlist_entry_safe( \
                rcu_dereference_bh(hlist_first_rcu(head)), \
                typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe( \
                rcu_dereference_bh(hlist_next_rcu( \
                    &(pos)->member)), \
                typeof(*(pos)), member))

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry_srcu: SRCU (Sleepable RCU) 보호 순회
 *
 * 슬립 가능한 RCU 구간에서 사용.
 * SRCU read-side critical section 검증을 위해
 * srcu_read_lock_held() 조건을 전달
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry_srcu(pos, head, member, cond) \
    for (pos = hlist_entry_safe( \
                rcu_dereference_check(hlist_first_rcu(head), (cond)), \
                typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe( \
                rcu_dereference_check(hlist_next_rcu( \
                    &(pos)->member), (cond)), \
                typeof(*(pos)), member))

/* ═══════════════════════════════════════════════
 * hlist_for_each_entry_continue_rcu: RCU 순회 — 현재 다음부터
 * hlist_for_each_entry_from_rcu: RCU 순회 — 현재부터
 *
 * 비-RCU 버전의 continue/from과 동일한 의미,
 * 포인터 읽기에 rcu_dereference() 사용
 * ═══════════════════════════════════════════════ */
#define hlist_for_each_entry_continue_rcu(pos, member) \
    for (pos = hlist_entry_safe( \
                rcu_dereference_raw(hlist_next_rcu( \
                    &(pos)->member)), \
                typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe( \
                rcu_dereference_raw(hlist_next_rcu( \
                    &(pos)->member)), \
                typeof(*(pos)), member))

#define hlist_for_each_entry_from_rcu(pos, member) \
    for (; pos; \
         pos = hlist_entry_safe( \
                rcu_dereference_raw(hlist_next_rcu( \
                    &(pos)->member)), \
                typeof(*(pos)), member))

hlist RCU 교체(replace) 함수

/* ───────────────────────────────────────────────
 * hlist_replace_rcu: 기존 노드를 새 노드로 원자적 교체
 *
 * 교체 전: ... → [P] → [old] → [C] → ...
 * 교체 후: ... → [P] → [new] → [C] → ...
 *
 * old는 grace period 후 안전하게 해제 가능.
 * 읽기 측은 old 또는 new 중 하나를 보게 됨 (둘 다 유효)
 *
 * 용도: 해시 테이블 엔트리의 in-place 업데이트.
 *       삭제 후 삽입보다 원자적이며, 중간에 검색 누락이 없음
 * ─────────────────────────────────────────────── */
static inline void hlist_replace_rcu(
    struct hlist_node *old,
    struct hlist_node *new)
{
    struct hlist_node *next = old->next;

    /* 1단계: new의 next가 old의 next를 가리킴 */
    new->next = next;

    /* 2단계: new의 pprev가 old의 pprev를 물려받음 */
    new->pprev = old->pprev;

    /* 3단계: 이전 노드(또는 헤드)가 new를 가리킴
     *         rcu_assign_pointer로 배리어 보장 */
    rcu_assign_pointer(*((struct hlist_node __rcu **)new->pprev), new);

    /* 4단계: 다음 노드가 있으면 pprev 갱신 */
    if (next)
        WRITE_ONCE(new->next->pprev, &new->pprev);

    /* old->pprev를 poison으로 설정 (재삭제 시도 감지) */
    old->pprev = LIST_POISON2;
}

hlist 전체 API 요약 테이블

hlist 사용 패턴과 관용구

패턴 1: 해시 테이블 검색 (가장 흔한 패턴)

/* 검색 — 버킷 선택 후 체인 순회 */
struct my_obj *find_by_key(struct hlist_head *table,
                           unsigned int bits, u32 key)
{
    struct my_obj *obj;
    u32 hash = hash_long(key, bits);

    hlist_for_each_entry(obj, &table[hash], hash_node) {
        if (obj->key == key)
            return obj;
    }
    return NULL;
}

패턴 2: RCU 보호 검색 + kfree_rcu 삭제

/* 읽기 경로 — lock-free */
struct my_obj *rcu_find(u32 key)
{
    struct my_obj *obj;
    u32 hash = hash_long(key, HASH_BITS);

    rcu_read_lock();
    hlist_for_each_entry_rcu(obj, &table[hash], hash_node) {
        if (obj->key == key) {
            rcu_read_unlock();
            return obj;
        }
    }
    rcu_read_unlock();
    return NULL;
}

/* 쓰기 경로 — spinlock 보호 */
void rcu_remove(struct my_obj *obj)
{
    spin_lock(&table_lock);
    hlist_del_rcu(&obj->hash_node);
    spin_unlock(&table_lock);

    /* grace period 후 자동 해제 — 콜백 함수 불필요 */
    kfree_rcu(obj, rcu_head);
}

/* 교체 경로 — 검색 누락 없는 업데이트 */
void rcu_update(struct my_obj *old, struct my_obj *new)
{
    spin_lock(&table_lock);
    hlist_replace_rcu(&old->hash_node, &new->hash_node);
    spin_unlock(&table_lock);

    kfree_rcu(old, rcu_head);
}

패턴 3: 안전한 전체 정리 (모듈 언로드 등)

/* 모든 버킷을 순회하며 노드 삭제 + 메모리 해제
 * hlist_for_each_entry_safe 필수 — 삭제 중 순회이므로 */
void cleanup_table(struct hlist_head *table, unsigned int size)
{
    struct my_obj *obj;
    struct hlist_node *tmp;
    unsigned int i;

    for (i = 0; i < size; i++) {
        hlist_for_each_entry_safe(obj, tmp, &table[i], hash_node) {
            hlist_del(&obj->hash_node);
            kfree(obj);
        }
    }
}

패턴 4: 리스트 일괄 이동 (배치 처리)

/* 버킷의 모든 노드를 로컬 리스트로 이동 후 배치 처리
 * lock 보유 시간을 최소화하는 패턴 */
void batch_process(struct hlist_head *bucket)
{
    HLIST_HEAD(local);
    struct my_obj *obj;
    struct hlist_node *tmp;

    /* lock 구간: 리스트 이동만 (O(1)) */
    spin_lock(&bucket_lock);
    hlist_move_list(bucket, &local);
    spin_unlock(&bucket_lock);

    /* lock 없이 로컬 리스트에서 배치 처리 */
    hlist_for_each_entry_safe(obj, tmp, &local, hash_node) {
        process(obj);
        hlist_del(&obj->hash_node);
        kfree(obj);
    }
}

hlist 메모리 레이아웃 시각화

hlist_head와 hlist_node의 포인터 관계를 시각적으로 이해하면 pprev 이중 포인터의 필요성과 통일된 삭제 연산이 자연스럽게 납득됩니다. 아래 다이어그램은 hlist_head → Node A → Node B → NULL 체인의 모든 포인터 관계를 보여줍니다.

이 설계의 핵심 이점은 삭제 시 분기문(if)이 불필요하다는 것입니다. list_head는 원형 이중 연결이므로 prev/next가 대칭적이지만, 헤드가 포인터 2개를 차지합니다. hlist는 비대칭(head는 1포인터, node는 2포인터)이지만, pprev 트릭으로 삭제의 통일성을 확보합니다.

hlist 삭제 동작 단계별 시각화

pprev 이중 포인터를 활용한 __hlist_del()의 동작을 3가지 케이스(첫 번째 노드, 중간 노드, 마지막 노드)로 나누어 단계별로 시각화합니다. 모든 경우에 동일한 코드 2줄로 삭제가 완료되는 것이 핵심입니다.

/* include/linux/list.h - hlist 삭제의 핵심 2줄 */
static inline void __hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
    struct hlist_node **pprev = n->pprev;

    /* 1단계: 이전의 next(또는 head.first)를 다음 노드로 연결 */
    WRITE_ONCE(*pprev, next);

    /* 2단계: 다음 노드의 pprev를 현재 노드의 pprev로 갱신 */
    if (next)
        WRITE_ONCE(next->pprev, pprev);
}

hlist_bl (Bit-Locked Hash List)

hlist_bl은 hlist의 변형으로, 헤드 포인터의 최하위 비트(LSB)를 spinlock으로 사용합니다. 별도의 lock 배열 없이 버킷 단위 잠금(Lock)을 구현할 수 있어 메모리를 절약합니다. 리눅스 dcache(dentry_hashtable)에서 사용되며, 수백만 버킷의 해시 테이블에서 lock 배열의 오버헤드(Overhead)를 제거하는 핵심 기법입니다.

/* include/linux/list_bl.h - Bit-locked hlist */

struct hlist_bl_head {
    struct hlist_bl_node *first;
    /* bit 0 of 'first' = spinlock bit */
};

struct hlist_bl_node {
    struct hlist_bl_node *next;
    struct hlist_bl_node **pprev;
};

/* 잠금: first 포인터의 bit 0을 설정 */
static inline void hlist_bl_lock(struct hlist_bl_head *b)
{
    bit_spin_lock(0, (unsigned long *)&b->first);
}

/* 해제: first 포인터의 bit 0을 해제 */
static inline void hlist_bl_unlock(struct hlist_bl_head *b)
{
    __bit_spin_unlock(0, (unsigned long *)&b->first);
}

/* first 포인터 읽기: bit 0을 마스킹 */
static inline struct hlist_bl_node *hlist_bl_first(
    struct hlist_bl_head *h)
{
    return (struct hlist_bl_node *)
        ((unsigned long)h->first & ~1UL);
}

dcache에서의 hlist_bl 사용

/* fs/dcache.c - dentry 해시 테이블 */
static struct hlist_bl_head *dentry_hashtable __read_mostly;

/* dentry 검색 (경로명 룩업 hot path) */
struct dentry *d_lookup(const struct dentry *parent,
                       const struct qstr *name)
{
    unsigned int hash = name->hash;
    struct hlist_bl_head *b = dentry_hashtable +
                              hash_32(hash, d_hash_shift);
    struct dentry *found;

    rcu_read_lock();
    /* RCU 읽기: bit-lock 불필요 (읽기는 lock-free) */
    hlist_bl_for_each_entry_rcu(found, node, b, d_hash) {
        if (found->d_name.hash != hash)
            continue;
        if (found->d_parent != parent)
            continue;
        if (d_unhashed(found))
            continue;
        if (!dentry_cmp(found, name->name, name->len)) {
            rcu_read_unlock();
            return found;
        }
    }
    rcu_read_unlock();
    return NULL;
}

hlist 변형 비교

hlist_nulls 상세 분석 (Nulls Marker Hash List)

include/linux/list_nulls.h에 정의된 hlist_nulls는 체인의 끝을 단순 NULL이 아닌 버킷 인덱스가 인코딩된 마커로 표시합니다. 이를 통해 RCU 읽기 측이 lock 없이도 리사이즈로 인한 버킷 이동을 감지할 수 있습니다. rhashtable과 conntrack 등 고성능 동시성 해시 테이블에서 핵심적으로 사용됩니다.

구조체 정의

/* include/linux/list_nulls.h */

struct hlist_nulls_head {
    struct hlist_nulls_node *first;
};

struct hlist_nulls_node {
    struct hlist_nulls_node *next;
    struct hlist_nulls_node **pprev;
};

/* Nulls 마커 인코딩:
 * 일반 포인터: bit 0 = 0 (정렬된 주소)
 * nulls 마커: bit 0 = 1, 상위 비트 = 버킷 인덱스
 *
 * 체인 끝에서 "이 체인이 어떤 버킷에 속하는지" 알 수 있음 */

#define NULLS_MARKER(value) \
    ((struct hlist_nulls_node *)((unsigned long)(value) << 1 | 0x01UL))

/* 초기화: 체인 끝이 버킷 인덱스를 인코딩한 nulls 마커 */
#define INIT_HLIST_NULLS_HEAD(ptr, nulls) \
    ((ptr)->first = NULLS_MARKER(nulls))

/* nulls 마커인지 확인: bit 0이 1이면 nulls */
static inline int is_a_nulls(
    const struct hlist_nulls_node *ptr)
{
    return ((unsigned long)ptr & 1);
}

/* nulls 마커에서 버킷 인덱스 추출 */
static inline unsigned long get_nulls_value(
    const struct hlist_nulls_node *ptr)
{
    return ((unsigned long)ptr >> 1);
}

hlist_nulls 삽입/삭제 함수

/* 헤드 앞에 삽입 — hlist_add_head와 동일한 로직 */
static inline void hlist_nulls_add_head(
    struct hlist_nulls_node *n,
    struct hlist_nulls_head *h)
{
    struct hlist_nulls_node *first = h->first;

    n->next = first;
    /* first가 nulls 마커일 수 있음 — is_a_nulls()로 확인 필요 */
    if (!is_a_nulls(first))
        first->pprev = &n->next;
    WRITE_ONCE(h->first, n);
    n->pprev = &h->first;
}

/* RCU 보호 삽입 */
static inline void hlist_nulls_add_head_rcu(
    struct hlist_nulls_node *n,
    struct hlist_nulls_head *h)
{
    struct hlist_nulls_node *first = h->first;

    n->next = first;
    WRITE_ONCE(n->pprev, &h->first);
    rcu_assign_pointer(h->first, n);
    if (!is_a_nulls(first))
        WRITE_ONCE(first->pprev, &n->next);
}

/* 삭제 — __hlist_nulls_del 내부 동작 */
static inline void __hlist_nulls_del(
    struct hlist_nulls_node *n)
{
    struct hlist_nulls_node *next = n->next;
    struct hlist_nulls_node **pprev = n->pprev;

    WRITE_ONCE(*pprev, next);
    /* next가 nulls 마커이면 pprev 갱신 불필요 */
    if (!is_a_nulls(next))
        WRITE_ONCE(next->pprev, pprev);
}

static inline void hlist_nulls_del_rcu(
    struct hlist_nulls_node *n)
{
    __hlist_nulls_del(n);
    /* next는 유지 (RCU 읽기 측이 순회 중일 수 있음) */
    n->pprev = LIST_POISON2;
}

hlist_nulls 순회 매크로

/* 기본 순회 — nulls 마커를 만나면 종료 */
#define hlist_nulls_for_each_entry(tpos, pos, head, member) \
    for (pos = (head)->first; \
         (!is_a_nulls(pos)) && \
         ({ tpos = hlist_nulls_entry(pos, typeof(*(tpos)), member); \
            1; }); \
         pos = pos->next)

/* RCU 보호 순회 — rhashtable 내부에서 사용되는 핵심 매크로 */
#define hlist_nulls_for_each_entry_rcu(tpos, pos, head, member) \
    for (pos = rcu_dereference_raw((head)->first); \
         (!is_a_nulls(pos)) && \
         ({ tpos = hlist_nulls_entry(pos, typeof(*(tpos)), member); \
            1; }); \
         pos = rcu_dereference_raw(pos->next))

/* 안전한 순회 (삭제 가능) */
#define hlist_nulls_for_each_entry_safe(tpos, pos, head, member) \
    for (({ pos = (head)->first; }); \
         (!is_a_nulls(pos)) && \
         ({ tpos = hlist_nulls_entry(pos, typeof(*(tpos)), member); \
            pos = pos->next; 1; });)

Nulls 마커 기반 RCU 안전 검색 패턴

다음은 Documentation/RCU/rculist_nulls.rst에 설명된 RCU + hlist_nulls 안전 검색 패턴입니다. 리사이즈나 요소 이동 중에도 검색 누락이 없는 것이 핵심입니다.

/* RCU + hlist_nulls 안전 검색 패턴
 *
 * 핵심 아이디어:
 * 1. RCU 보호 아래 체인을 순회
 * 2. 체인 끝의 nulls 값이 시작 버킷과 일치하는지 확인
 * 3. 불일치하면 리사이즈 발생 → 새 테이블에서 재시도
 */

struct my_obj *nulls_safe_lookup(u32 key)
{
    struct hlist_nulls_head *head;
    struct hlist_nulls_node *node;
    struct my_obj *obj;
    u32 slot;

begin:
    /* 현재 버킷 인덱스 계산 */
    slot = hash_long(key, HASH_BITS);
    head = &table[slot];

    rcu_read_lock();
    hlist_nulls_for_each_entry_rcu(obj, node, head, hash_node) {
        if (obj->key == key) {
            /* refcount 획득 등 추가 검증 */
            if (!atomic_inc_not_zero(&obj->refcnt)) {
                /* 삭제 진행 중 — 못 찾은 것과 동일 */
                rcu_read_unlock();
                goto begin;
            }
            rcu_read_unlock();
            return obj;
        }
    }

    /* 체인 끝 도달: nulls 마커의 버킷 인덱스 확인
     * node는 이 시점에서 nulls 마커를 가리킴 */
    if (get_nulls_value(node) != slot) {
        /* 순회 중 리사이즈 발생 → 버킷 재계산 후 재시도 */
        rcu_read_unlock();
        goto begin;
    }

    rcu_read_unlock();
    return NULL;
}

NULL vs Nulls 마커 비교

커널 해시 함수 (<linux/hash.h>)

좋은 해시 테이블 성능의 핵심은 해시 함수의 품질입니다. 커널은 다양한 용도에 맞는 여러 해시 함수를 제공합니다.

Golden Ratio 해시 (hash_long / hash_32 / hash_64)

가장 기본적인 커널 해시 함수로, 정수 키를 해싱할 때 사용합니다. Fibonacci Hashing이라고도 불리며, 황금비(Golden Ratio)에서 유도된 상수를 곱합니다.

/* include/linux/hash.h */

/* 2^32 / phi = 2^32 * (sqrt(5)-1)/2 */
#define GOLDEN_RATIO_32  0x61C88647

/* 2^64 / phi */
#define GOLDEN_RATIO_64  0x61C8864680B583EBull

static inline u32 hash_64(u64 val, unsigned int bits)
{
    return (u32)(val * GOLDEN_RATIO_64) >> (64 - bits);
}

static inline u32 hash_32(u32 val, unsigned int bits)
{
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

/* 아키텍처 워드 크기에 맞는 해시 */
#if BITS_PER_LONG == 64
#define hash_long(val, bits)  hash_64((u64)(val), bits)
#else
#define hash_long(val, bits)  hash_32((u32)(val), bits)
#endif

포인터 해싱 (hash_ptr)

static inline u32 hash_ptr(const void *ptr, unsigned int bits)
{
    return hash_long((unsigned long)ptr, bits);
}

Jenkins Hash (jhash)

가변 길이 데이터(문자열, 구조체(Struct) 등)를 해싱할 때 사용합니다. Bob Jenkins가 설계한 해시 함수로, <linux/jhash.h>에 정의됩니다. 주로 네트워킹 서브시스템에서 튜플(src IP, dst IP, src port, dst port) 해싱에 사용됩니다.

/* include/linux/jhash.h */

/* 가변 길이 바이트 배열 해싱 */
u32 jhash(const void *key, u32 length, u32 initval);

/* 2개 word 해싱 (빠름) */
u32 jhash_2words(u32 a, u32 b, u32 initval);

/* 3개 word 해싱 */
u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval);

/* 1개 word 해싱 */
u32 jhash_1word(u32 a, u32 initval);

네트워크 튜플 해싱 예시 (conntrack):

static u32 hash_conntrack_raw(const struct nf_conntrack_tuple *tuple,
                              unsigned int zoneid,
                              const struct net *net)
{
    unsigned int n;
    u32 seed;

    get_random_once(&nf_conntrack_hash_rnd, sizeof(nf_conntrack_hash_rnd));
    seed = nf_conntrack_hash_rnd ^ zoneid;

    n = (sizeof(tuple->src) + sizeof(tuple->dst.u3)) / sizeof(u32);
    return jhash2((u32 *)tuple, n,
                  seed ^ (u32)(unsigned long)net ^
                  ((__force __u16)tuple->dst.u.all << 16) |
                  tuple->dst.protonum);
}

기타 해시 함수

보안 민감 경로의 해시 함수 선택 패턴

외부 입력(패킷(Packet), 사용자 문자열, ioctl 인자 등)을 키로 쓰는 경로는 단순 성능보다 충돌 공격 내성이 중요합니다. 특히 공격자가 키를 조작할 수 있는 상황에서는 siphash 기반 설계를 기본값으로 두는 것이 안전합니다.

/* 예시: 외부 입력 키를 siphash로 보호 */
#include <linux/siphash.h>

struct user_key {
    u64 a, b;
};

static siphash_key_t g_hash_key;

static u32 secure_key_hash(const struct user_key *k, u32 bits)
{
    u64 h = siphash(k, sizeof(*k), &g_hash_key);
    return (u32)(h >> (64 - bits));
}

• 키 초기화 — 부팅 시 get_random_bytes()로 비밀 키를 생성하고 전역 고정값 하드코딩을 피합니다.
• 로그 노출 주의 — 해시값/seed를 디버그 로그에 그대로 출력하지 않습니다.
• 성능 균형 — 내부 신뢰 경로는 hash_long/jhash, 외부 입력 경로는 siphash를 구분 적용합니다.

해시 함수 분포와 품질

해시 테이블의 성능은 해시 함수가 키를 버킷에 얼마나 균등하게 분배하느냐에 좌우됩니다. 나쁜 분포는 특정 버킷에 노드가 집중되어 O(1) → O(n) 검색 성능 저하를 초래합니다.

해시 품질 측정 지표

해시 함수 선택 가이드

<linux/hashtable.h> API

커널 3.7에서 도입된 <linux/hashtable.h>는 고정 크기 해시 테이블을 위한 간결한 매크로 세트를 제공합니다. 내부적으로 hlist_head 배열과 hash_long()을 사용합니다.

선언과 초기화

#include <linux/hashtable.h>

/* 정적 해시 테이블 선언 (2^bits 버킷) */
DEFINE_HASHTABLE(my_ht, 10);  /* 1024 버킷 */

/* 또는 동적으로 */
struct hlist_head my_ht[1 << 10];
hash_init(my_ht);  /* 모든 버킷을 NULL로 초기화 */

DEFINE_HASHTABLE(name, bits)는 다음과 동일합니다:

struct hlist_head name[1 << (bits)] =
    { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT };

삽입, 삭제, 검색

struct my_object {
    int key;
    char *data;
    struct hlist_node hash_node;
};

/* 삽입: key를 해시하여 버킷에 추가 */
struct my_object *obj = kmalloc(sizeof(*obj), GFP_KERNEL);
obj->key = 42;
obj->data = "hello";
hash_add(my_ht, &obj->hash_node, obj->key);

/* 삭제 */
hash_del(&obj->hash_node);

/* 검색: 특정 key와 동일한 버킷의 모든 노드를 순회 */
struct my_object *cur;
int search_key = 42;
hash_for_each_possible(my_ht, cur, hash_node, search_key) {
    if (cur->key == search_key) {
        pr_info("found: %s\\n", cur->data);
        break;
    }
}

전체 API 레퍼런스

hashtable.h 매크로 내부 구현 분석

<linux/hashtable.h>의 매크로는 hlist 함수 위에 얇은 래퍼로 구현됩니다. 각 매크로가 어떻게 확장되는지 이해하면, 커스텀 해시 테이블 설계나 디버깅에 도움이 됩니다.

/* include/linux/hashtable.h — 내부 구현 분석 */

/* ─── DEFINE_HASHTABLE ─── */
#define DEFINE_HASHTABLE(name, bits) \
    struct hlist_head name[1 << (bits)] = \
        { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
/* GCC 범위 지정 초기화(range designator)로 모든 버킷을 {.first = NULL}로 설정.
 * bits=10이면 1024개 hlist_head 배열 = 8KB (x86_64) */

/* ─── DECLARE_HASHTABLE ─── */
#define DECLARE_HASHTABLE(name, bits) \
    struct hlist_head name[1 << (bits)]
/* 선언만 하고 초기화는 hash_init()으로 나중에 수행 */

/* ─── hash_init ─── */
#define hash_init(hashtable) \
    __hash_init(hashtable, HASH_SIZE(hashtable))

static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
{
    unsigned int i;
    for (i = 0; i < sz; i++)
        INIT_HLIST_HEAD(&ht[i]);
}

/* ─── HASH_SIZE / HASH_BITS ───
 * 배열 크기로부터 버킷 수와 비트 수를 역산 */
#define HASH_SIZE(name) (ARRAY_SIZE(name))
#define HASH_BITS(name) ilog2(HASH_SIZE(name))

/* ─── hash_add: 키를 해시하여 버킷에 삽입 ─── */
#define hash_add(hashtable, node, key) \
    hlist_add_head(node, \
        &hashtable[hash_min(key, HASH_BITS(hashtable))])

/* hash_min: 키 크기에 따라 hash_32 또는 hash_long 자동 선택
 * sizeof(key) <= 4  → hash_32(key, bits)
 * sizeof(key) >  4  → hash_long(key, bits)   */
#define hash_min(val, bits) \
    (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))

/* 전개 예시: hash_add(my_ht, &obj->node, obj->key)
 * → hlist_add_head(&obj->node,
 *                  &my_ht[hash_32(obj->key, ilog2(ARRAY_SIZE(my_ht)))])
 * → hlist_add_head(&obj->node,
 *                  &my_ht[hash_32(obj->key, 10)])  // bits=10
 * → hlist_add_head(&obj->node, &my_ht[bucket_index]) */

/* ─── hash_add_rcu: RCU 보호 삽입 ─── */
#define hash_add_rcu(hashtable, node, key) \
    hlist_add_head_rcu(node, \
        &hashtable[hash_min(key, HASH_BITS(hashtable))])

/* ─── hash_del / hash_del_rcu ─── */
static inline void hash_del(struct hlist_node *node)
{
    hlist_del_init(node);
    /* hlist_del이 아닌 hlist_del_init 사용 → 노드 재삽입 허용
     * hash_del 후 hash_add로 다시 삽입할 수 있음 */
}

static inline void hash_del_rcu(struct hlist_node *node)
{
    hlist_del_init_rcu(node);
    /* RCU 버전: next 포인터 유지 + pprev를 NULL로 설정
     * 읽기 측이 삭제된 노드를 통해 다음 노드 순회 가능 */
}

/* ─── hash_for_each: 전체 테이블 순회 ─── */
#define hash_for_each(name, bkt, obj, member) \
    for ((bkt) = 0, obj = NULL; \
         obj == NULL && (bkt) < HASH_SIZE(name); (bkt)++) \
        hlist_for_each_entry(obj, &name[bkt], member)

/* 이중 루프 구조:
 * 외부 루프: 버킷 0부터 HASH_SIZE-1까지 순회
 * 내부 루프: 각 버킷의 hlist 체인을 hlist_for_each_entry로 순회
 * obj == NULL 조건: 빈 버킷을 건너뛰는 최적화 */

/* ─── hash_for_each_safe: 삭제 안전 전체 순회 ─── */
#define hash_for_each_safe(name, bkt, tmp, obj, member) \
    for ((bkt) = 0, obj = NULL; \
         obj == NULL && (bkt) < HASH_SIZE(name); (bkt)++) \
        hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)

/* ─── hash_for_each_possible: 특정 키의 버킷만 순회 ─── */
#define hash_for_each_possible(name, obj, member, key) \
    hlist_for_each_entry(obj, \
        &name[hash_min(key, HASH_BITS(name))], member)
/* 단일 버킷의 체인만 순회 — 해시 테이블 검색의 핵심 매크로 */

/* ─── hash_for_each_possible_safe: 삭제 안전 버킷 순회 ─── */
#define hash_for_each_possible_safe(name, obj, tmp, member, key) \
    hlist_for_each_entry_safe(obj, tmp, \
        &name[hash_min(key, HASH_BITS(name))], member)

/* ─── RCU 변형 ─── */
#define hash_for_each_rcu(name, bkt, obj, member) \
    for ((bkt) = 0, obj = NULL; \
         obj == NULL && (bkt) < HASH_SIZE(name); (bkt)++) \
        hlist_for_each_entry_rcu(obj, &name[bkt], member)

#define hash_for_each_possible_rcu(name, obj, member, key) \
    hlist_for_each_entry_rcu(obj, \
        &name[hash_min(key, HASH_BITS(name))], member)

#define hash_for_each_possible_rcu_notrace(name, obj, member, key) \
    hlist_for_each_entry_rcu_notrace(obj, \
        &name[hash_min(key, HASH_BITS(name))], member)
/* notrace 변형: ftrace/lockdep tracing 비활성화.
 * tracing 서브시스템 자체가 해시 테이블을 사용할 때
 * 재귀 tracing을 방지하기 위해 사용 */

/* ─── hash_empty: 테이블이 비어있는지 확인 ─── */
static inline bool hash_empty(struct hlist_head *ht, unsigned int sz)
{
    unsigned int i;
    for (i = 0; i < sz; i++) {
        if (!hlist_empty(&ht[i]))
            return false;
    }
    return true;
}
/* 주의: O(n) 연산 — 전체 버킷을 스캔하므로 hot path에서 사용 금지.
 * 별도의 원자적 카운터(atomic counter)를 유지하는 것이 효율적 */

완전한 사용 예제

/* 실습 예제: DEFINE_HASHTABLE 기반 PID 캐시 모듈 */
#include <linux/module.h>
#include <linux/hashtable.h>
#include <linux/slab.h>

/* 8-bit hash → 256 버킷 */
DEFINE_HASHTABLE(pid_cache, 8);

struct pid_entry {
    pid_t               pid;
    char                comm[TASK_COMM_LEN];
    struct hlist_node   hash_node;
};

static void add_pid(pid_t pid, const char *comm)
{
    struct pid_entry *entry;

    entry = kmalloc(sizeof(*entry), GFP_KERNEL);
    if (!entry)
        return;

    entry->pid = pid;
    strscpy(entry->comm, comm, TASK_COMM_LEN);

    hash_add(pid_cache, &entry->hash_node, pid);
}

static struct pid_entry *find_pid(pid_t pid)
{
    struct pid_entry *entry;

    hash_for_each_possible(pid_cache, entry, hash_node, pid) {
        if (entry->pid == pid)
            return entry;
    }
    return NULL;
}

static void remove_pid(pid_t pid)
{
    struct pid_entry *entry = find_pid(pid);
    if (entry) {
        hash_del(&entry->hash_node);
        kfree(entry);
    }
}

static void dump_all(void)
{
    struct pid_entry *entry;
    unsigned int bkt;

    hash_for_each(pid_cache, bkt, entry, hash_node)
        pr_info("[bucket %u] pid=%d comm=%s\\n",
                bkt, entry->pid, entry->comm);
}

static void cleanup_all(void)
{
    struct pid_entry *entry;
    struct hlist_node *tmp;
    unsigned int bkt;

    hash_for_each_safe(pid_cache, bkt, tmp, entry, hash_node) {
        hash_del(&entry->hash_node);
        kfree(entry);
    }
}

rhashtable (Resizable Hash Table)

<linux/rhashtable.h>는 커널 3.17(Thomas Graf 제안, commit 7e1e7763)에서 도입된 자동 리사이즈 해시 테이블입니다. 고정 크기 hashtable.h와 달리, 요소 수에 따라 버킷 배열을 동적으로 확장/축소하여 로드 팩터를 일정 범위로 유지합니다. 네트워킹 서브시스템의 고성능 요구사항에서 탄생했으며, 현재는 conntrack, nftables, netlabel, TIPC, IMA 등 커널 전반에서 사용됩니다.

rhashtable의 핵심 특징:

• 자동 리사이즈 — 삽입/삭제 시 로드 팩터를 확인하고, work queue를 통해 비동기적으로 리사이즈
• RCU 기반 읽기 — 리사이즈 중에도 읽기 연산은 lock-free로 진행
• 유연한 키 지정 — rhashtable_params로 키 오프셋(Offset), 길이, 해시 함수를 구성
• per-bucket 잠금 — 쓰기 연산은 버킷 단위 spinlock으로 세밀하게 직렬화(Serialization)
• Nulls 마커 — hlist_nulls를 사용하여 리사이즈 중 테이블 전환을 감지
• 중복 키 지원 — rhltable 변형으로 동일 키에 여러 엔트리 허용

내부 구조 (Internal Architecture)

rhashtable은 세 가지 핵심 구조체로 구성됩니다:

/* include/linux/rhashtable-types.h */

/* 해시 테이블 전체를 대표하는 구조체 */
struct rhashtable {
    struct bucket_table __rcu  *tbl;       /* 현재 버킷 테이블 (RCU 보호) */
    unsigned int               key_len;   /* 키 바이트 길이 */
    unsigned int               max_elems; /* 최대 요소 수 (0=무제한) */
    struct rhashtable_params    p;         /* 파라미터 복사본 */
    bool                       rhlist;    /* rhltable 모드 여부 */
    struct work_struct         run_work;  /* 비동기 리사이즈 work */
    struct mutex               mutex;     /* 리사이즈 직렬화 */
    spinlock_t                 lock;      /* 리사이즈 상태 보호 */
    atomic_t                   nelems;    /* 현재 요소 수 */
};

/* 버킷 배열 + 메타데이터 */
struct bucket_table {
    unsigned int               size;       /* 버킷 수 (항상 2의 거듭제곱) */
    unsigned int               nest;       /* 중첩 테이블 깊이 */
    unsigned int               hash_rnd;   /* 랜덤 해시 시드 */
    struct list_head           walkers;    /* 활성 워커 리스트 */
    struct rcu_head            rcu;        /* RCU 해제용 */
    struct bucket_table __rcu  *future_tbl; /* 리사이즈 중 새 테이블 */
    lockdep_map_p              dep_map;    /* lockdep 추적 */
    struct rhash_lock_head __rcu *buckets[] __counted_by(size);
};

/* 각 요소에 내장되는 해시 노드 */
struct rhash_head {
    struct rhash_head __rcu    *next;     /* 체인 내 다음 노드 */
};

Nulls 마커와 테이블 전환 감지

rhashtable은 일반 hlist가 아닌 hlist_nulls 기반 체인을 사용합니다. 체인의 끝(NULL)에 버킷 인덱스를 인코딩한 nulls 마커를 배치하여, 리사이즈 중 읽기 측에서 자신이 올바른 버킷을 순회하고 있는지 검증할 수 있습니다.

/*
 * Nulls 마커 원리:
 *
 * 체인 끝이 단순 NULL이 아닌 (bucket_index << 1) | 1 값.
 * 읽기 측이 체인을 순회한 후, 끝의 nulls 값이
 * 자신이 시작한 버킷과 일치하는지 확인.
 * 불일치하면 리사이즈로 인해 요소가 이동된 것이므로 재시도.
 */

/* 읽기 측 패턴 (내부 구현) */
restart:
    head = rht_bucket(tbl, hash);
    rht_for_each_rcu(he, head) {
        if (rht_key_matches(params, he, key))
            return he;
    }

    /* nulls 마커 검증 */
    if (get_nulls_value(he) != hash)
        goto restart;  /* 버킷이 바뀌었으므로 재시도 */

per-bucket 잠금 전략

rhashtable의 쓰기 연산은 버킷 단위 spinlock으로 직렬화됩니다. 각 버킷의 첫 번째 포인터에 잠금 비트를 인코딩하는 bit-spin-lock 기법을 사용합니다. 이는 별도의 lock 배열 없이 버킷 포인터의 최하위 비트(LSB)를 활용하는 방식입니다.

/*
 * Per-bucket locking 구조:
 *
 * buckets[i]는 struct rhash_lock_head* 타입.
 * 포인터의 bit 0을 spinlock으로 사용:
 *   bit 0 = 0 → 잠금 해제 (unlocked)
 *   bit 0 = 1 → 잠금 설정 (locked)
 *
 * 장점:
 *   - 별도 lock 배열 불필요 → 메모리 절약
 *   - 캐시 라인을 데이터와 공유 → 미스 감소
 *   - 서로 다른 버킷의 삽입/삭제는 완전 병렬
 */

/* 내부 잠금 헬퍼 (lib/rhashtable.c) */
static inline void rht_lock(struct bucket_table *tbl,
                            struct rhash_lock_head __rcu **bkt)
{
    local_bh_disable();
    bit_spin_lock(0, (unsigned long *)bkt);
    lock_map_acquire(&tbl->dep_map);
}

static inline void rht_unlock(struct bucket_table *tbl,
                              struct rhash_lock_head __rcu **bkt)
{
    lock_map_release(&tbl->dep_map);
    bit_spin_unlock(0, (unsigned long *)bkt);
    local_bh_enable();
}

rhashtable_params 상세

rhashtable_params는 해시 테이블의 동작 방식을 결정하는 구성 구조체입니다. rhashtable_init()에 전달하면 내부에 복사되어 테이블 수명 동안 유지됩니다.

struct rhashtable_params {
    u16                  nelem_hint;          /* 초기 요소 수 힌트 (초기 버킷 수 계산) */
    u16                  key_len;             /* 키 바이트 길이 (obj_hashfn 사용 시 0) */
    u16                  key_offset;          /* 구조체 내 키 시작 오프셋 */
    u16                  head_offset;         /* 구조체 내 rhash_head 오프셋 */
    unsigned int         max_size;            /* 최대 버킷 수 (0=무제한) */
    u16                  min_size;            /* 최소 버킷 수 */
    bool                 automatic_shrinking; /* 자동 축소 활성화 */
    rht_hashfn_t         hashfn;              /* 키 → 해시 함수 (기본: jhash) */
    rht_obj_hashfn_t     obj_hashfn;          /* 객체 → 해시 함수 (복합 키용) */
    rht_obj_cmpfn_t      obj_cmpfn;           /* 커스텀 비교 함수 (선택) */
};

기본 사용 예:

#include <linux/rhashtable.h>

struct my_entry {
    u32                    key;
    char                   value[64];
    struct rhash_head      rhash;   /* rhashtable 노드 */
};

static const struct rhashtable_params my_rht_params = {
    .head_offset     = offsetof(struct my_entry, rhash),
    .key_offset      = offsetof(struct my_entry, key),
    .key_len         = sizeof(u32),
    .automatic_shrinking = true,
    .nelem_hint      = 1024,          /* 초기 요소 수 힌트 */
    .min_size        = 256,           /* 최소 버킷 수 */
    .max_size        = 0,             /* 0 = 제한 없음 */
};

복합 키 사용 예 (obj_hashfn + obj_cmpfn):

/* 복합 키: (src_ip, dst_ip, protocol) 3-tuple */
struct flow_key {
    __be32  src_ip;
    __be32  dst_ip;
    u8      protocol;
};

struct flow_entry {
    struct flow_key    fkey;
    u64                packets;
    u64                bytes;
    struct rhash_head  rhash;
};

static u32 flow_obj_hashfn(const void *data, u32 len, u32 seed)
{
    const struct flow_entry *f = data;
    return jhash(&f->fkey, sizeof(f->fkey), seed);
}

static u32 flow_key_hashfn(const void *data, u32 len, u32 seed)
{
    return jhash(data, sizeof(struct flow_key), seed);
}

static int flow_obj_cmpfn(struct rhashtable_compare_arg *arg,
                          const void *obj)
{
    const struct flow_key *key = arg->key;
    const struct flow_entry *f = obj;
    return memcmp(&f->fkey, key, sizeof(*key));
}

static const struct rhashtable_params flow_params = {
    .head_offset  = offsetof(struct flow_entry, rhash),
    .key_offset   = offsetof(struct flow_entry, fkey),
    .key_len      = sizeof(struct flow_key),
    .hashfn       = flow_key_hashfn,
    .obj_hashfn   = flow_obj_hashfn,
    .obj_cmpfn    = flow_obj_cmpfn,
};

기본 API

struct rhashtable my_rht;

/* 초기화: 파라미터 기반으로 버킷 테이블 할당 */
int ret = rhashtable_init(&my_rht, &my_rht_params);
if (ret)
    return ret;  /* -ENOMEM: 초기 버킷 할당 실패 */

/* 삽입: per-bucket lock 획득 후 체인 앞에 삽입 */
struct my_entry *entry = kzalloc(sizeof(*entry), GFP_KERNEL);
entry->key = 100;
ret = rhashtable_insert_fast(&my_rht, &entry->rhash, my_rht_params);
if (ret) {
    kfree(entry);
    return ret;  /* -ENOMEM: 리사이즈 실패, -EEXIST: 키 중복 */
}

/* 검색: RCU 보호 하에 lock-free 수행 */
u32 search_key = 100;
struct my_entry *found;
rcu_read_lock();
found = rhashtable_lookup_fast(&my_rht, &search_key, my_rht_params);
if (found)
    pr_info("found value: %s\\n", found->value);
rcu_read_unlock();

/* 삭제: per-bucket lock 획득 후 체인에서 제거 */
ret = rhashtable_remove_fast(&my_rht, &entry->rhash, my_rht_params);

/* 정리 (모든 요소 제거 후) */
rhashtable_destroy(&my_rht);

전체 API 레퍼런스

원자적 검색+삽입

검색과 삽입을 원자적으로 수행하는 편의 함수:

/* 키가 없으면 삽입, 이미 있으면 -EEXIST */
ret = rhashtable_lookup_insert_fast(&my_rht, &entry->rhash, my_rht_params);

/* 키가 있으면 기존 엔트리 반환, 없으면 삽입 */
struct my_entry *existing;
existing = rhashtable_lookup_get_insert_fast(&my_rht, &entry->rhash, my_rht_params);
if (IS_ERR(existing))
    return PTR_ERR(existing);  /* 에러 (-ENOMEM 등) */
if (existing)
    pr_info("already exists\\n");  /* 기존 엔트리 */
else
    pr_info("newly inserted\\n");  /* 새로 삽입됨 */

원자적 교체 (Replace)

rhashtable_replace_fast()는 동일 키의 기존 요소를 새 요소로 원자적으로 교체합니다. 읽기 측은 교체 전후의 어느 한 쪽만 관측하며, 중간 상태는 보이지 않습니다.

struct my_entry *old_entry = find_entry(&my_rht, key);
struct my_entry *new_entry = kzalloc(sizeof(*new_entry), GFP_KERNEL);
new_entry->key = old_entry->key;
strscpy(new_entry->value, "updated", sizeof(new_entry->value));

ret = rhashtable_replace_fast(&my_rht, &old_entry->rhash,
                              &new_entry->rhash, my_rht_params);
if (!ret) {
    synchronize_rcu();   /* 또는 call_rcu() */
    kfree(old_entry);   /* 이전 요소를 안전하게 해제 */
}

자동 리사이즈 메커니즘

rhashtable의 리사이즈는 다단계 과정으로 진행됩니다:

확장 (Grow) 트리거 조건

• 로드 팩터 초과 — nelems / size > 75% (기본 임계값)
• 체인 탄성 한계 초과 — 단일 체인의 길이가 RHT_ELASTICITY(기본 16)를 초과하면 즉시 삽입 실패(-EAGAIN) 후 리사이즈 예약

축소 (Shrink) 트리거 조건

• automatic_shrinking = true이고 nelems / size < 30%일 때
• min_size 이하로는 축소하지 않음

리사이즈 과정 상세

1. 트리거: 삽입/삭제 시 rht_grow_above_75() 또는 rht_shrink_below_30() 검사
2. 예약: schedule_work(&ht->run_work)로 work queue에 리사이즈 작업 등록
3. Mutex 획득: ht->mutex로 동시 리사이즈 방지
4. 새 테이블 할당: kvmalloc()으로 2배(확장) 또는 1/2(축소) 크기의 bucket_table 할당
5. future_tbl 설정: 현재 tbl->future_tbl = new_tbl로 연결 (RCU publish)
6. 요소 마이그레이션: 버킷별로 lock을 잡고, 각 요소를 재해싱하여 새 테이블로 이동
7. 테이블 교체: rcu_assign_pointer(ht->tbl, new_tbl)로 현재 테이블 전환
8. 이전 테이블 해제: call_rcu()로 grace period 이후 이전 bucket_table 해제

rhashtable 튜닝 플레이북

rhashtable은 기본값만으로도 동작하지만, 워크로드 특성(삽입 폭주, 삭제 편향, 키 분포)에 따라 파라미터를 명시적으로 설정하면 지연(Latency) 편차와 리사이즈 진동을 크게 줄일 수 있습니다.

/* 운영 지향 템플릿 예시 */
static const struct rhashtable_params tuned_params = {
    .head_offset = offsetof(struct my_entry, rhash),
    .key_offset  = offsetof(struct my_entry, key),
    .key_len     = sizeof(u32),
    .nelem_hint  = 1 << 16,
    .min_size    = 1 << 12,
    .max_size    = 1 << 20,
    .automatic_shrinking = true,
};

rhltable (중복 키 허용)

일반 rhashtable은 키 중복을 허용하지 않습니다(-EEXIST 반환). rhltable은 동일 키에 여러 엔트리를 허용하는 변형으로, 각 엔트리를 rhlist_head로 연결합니다. nftables set의 interval element 등에서 사용됩니다.

struct my_multi_entry {
    u32                     key;
    u32                     value;
    struct rhlist_head       rhlist;  /* rhltable 노드 (rhash_head 확장) */
};

struct rhltable my_rhlt;

/* 초기화 */
rhltable_init(&my_rhlt, &my_rht_params);

/* 삽입: 동일 키 허용 (중복 시에도 성공) */
rhltable_insert(&my_rhlt, &entry->rhlist, my_rht_params);

/* 검색: 동일 키의 모든 엔트리를 연결 리스트로 반환 */
struct rhlist_head *list, *tmp;
rcu_read_lock();
list = rhltable_lookup(&my_rhlt, &search_key, my_rht_params);
if (list) {
    rhl_for_each_entry_rcu(entry, tmp, list, rhlist) {
        pr_info("key=%u value=%u\\n", entry->key, entry->value);
    }
}
rcu_read_unlock();

/* 삭제: 특정 엔트리만 제거 */
rhltable_remove(&my_rhlt, &entry->rhlist, my_rht_params);

순회 API (Walk Iterator)

rhashtable은 리사이즈에 안전한 순회 API를 제공합니다. hash_for_each와 달리, 순회 중간에 sleep이 가능하고 리사이즈가 발생해도 정확성이 보장됩니다.

struct rhashtable_iter iter;

/* 1. 반복자 등록 (process 컨텍스트) */
rhashtable_walk_enter(&my_rht, &iter);

/* 2. 순회 시작 (RCU read lock 획득) */
rhashtable_walk_start(&iter);

/* 3. 요소 순회 */
struct my_entry *entry;
while ((entry = rhashtable_walk_next(&iter)) != NULL) {
    if (IS_ERR(entry)) {
        if (PTR_ERR(entry) == -EAGAIN)
            continue;  /* 리사이즈 발생 → 재시도 */
        break;         /* 기타 에러 */
    }
    pr_info("key=%u value=%s\\n", entry->key, entry->value);
}

/* 4. 순회 종료 (RCU read lock 해제) */
rhashtable_walk_stop(&iter);

/* 5. 반복자 해제 */
rhashtable_walk_exit(&iter);

정리와 해제

rhashtable을 해제할 때는 반드시 모든 요소를 먼저 제거해야 합니다. rhashtable_free_and_destroy()는 콜백 함수를 통해 이를 자동화합니다.

/* 방법 1: rhashtable_free_and_destroy (권장) */
static void my_entry_free(void *ptr, void *arg)
{
    struct my_entry *entry = ptr;
    kfree(entry);
}

/* 모든 요소에 대해 my_entry_free 호출 후 테이블 해제 */
rhashtable_free_and_destroy(&my_rht, my_entry_free, NULL);

/* 방법 2: Walk API로 수동 정리 */
struct rhashtable_iter iter;
rhashtable_walk_enter(&my_rht, &iter);
rhashtable_walk_start(&iter);

struct my_entry *entry;
while ((entry = rhashtable_walk_next(&iter)) != NULL) {
    if (IS_ERR(entry))
        continue;
    rhashtable_remove_fast(&my_rht, &entry->rhash, my_rht_params);
    kfree_rcu(entry, rcu);  /* RCU grace period 후 해제 */
}

rhashtable_walk_stop(&iter);
rhashtable_walk_exit(&iter);
rhashtable_destroy(&my_rht);

동시성 모델 요약

rhashtable 전체 라이프사이클

rhashtable의 초기화부터 파괴까지 전체 생명주기를 하나의 흐름도로 정리하면, 각 API의 호출 시점과 내부 동작이 명확해집니다.

hashtable.h vs rhashtable 비교

RCU 해시 테이블

<linux/hashtable.h>는 RCU로 보호되는 해시 테이블 연산을 별도의 _rcu 접미사 매크로로 제공합니다. 이를 사용하면 읽기 측에서 lock 없이 해시 테이블을 안전하게 순회할 수 있습니다.

RCU 해시 테이블 API

/* RCU 보호 삽입 — 쓰기 측에서 적절한 lock 보유 필요 */
hash_add_rcu(ht, &obj->hash_node, key);

/* RCU 보호 삭제 */
hash_del_rcu(&obj->hash_node);

/* RCU 읽기 측 전체 순회 */
rcu_read_lock();
hash_for_each_rcu(ht, bkt, obj, member) {
    /* obj를 읽기 전용으로 접근 */
}
rcu_read_unlock();

/* RCU 읽기 측 버킷 순회 (검색) */
rcu_read_lock();
hash_for_each_possible_rcu(ht, obj, member, key) {
    if (obj->key == search_key) {
        /* found */
        break;
    }
}
rcu_read_unlock();

읽기-쓰기 분리 패턴

static DEFINE_HASHTABLE(my_ht, 10);
static DEFINE_SPINLOCK(my_ht_lock);  /* 쓰기 측 보호 */

/* 읽기 경로: lock-free (RCU 구간에서 필요한 값만 복사) */
bool lookup_value(int key, char *buf, size_t buflen)
{
    struct my_object *obj;
    bool found = false;

    rcu_read_lock();
    hash_for_each_possible_rcu(my_ht, obj, hash_node, key) {
        if (obj->key == key) {
            strscpy(buf, obj->value, buflen);
            found = true;
            break;
        }
    }
    rcu_read_unlock();
    return found;
}

/* 쓰기 경로: spinlock으로 보호 */
void insert(struct my_object *obj)
{
    spin_lock(&my_ht_lock);
    hash_add_rcu(my_ht, &obj->hash_node, obj->key);
    spin_unlock(&my_ht_lock);
}

/* 삭제 경로 */
void delete(struct my_object *obj)
{
    spin_lock(&my_ht_lock);
    hash_del_rcu(&obj->hash_node);
    spin_unlock(&my_ht_lock);

    synchronize_rcu();   /* 또는 call_rcu()로 비동기 */
    kfree(obj);
}

충돌 해결과 성능

체이닝 (Separate Chaining)

커널 해시 테이블은 체이닝 방식으로 해시 충돌을 해결합니다. 동일 버킷에 해시되는 모든 요소는 hlist 체인으로 연결됩니다. Open addressing(선형/이차 탐사)과 비교할 때 다음과 같은 장점이 있습니다:

• 삭제가 단순하고 O(1)
• 로드 팩터가 1을 초과해도 동작 (성능은 저하되지만 장애는 아님)
• 포인터 기반이므로 요소 이동이 불필요

체인 길이 모델과 응답 시간 감각

균등 해시를 가정하면 버킷당 평균 체인 길이는 로드 팩터 α = n / m(요소 수 n, 버킷 수 m)로 근사됩니다. 즉, 평균 조회 비용은 대략 O(1 + α)이며, tail latency는 “가장 긴 체인”의 영향을 강하게 받습니다.

버킷 크기 선택 가이드

DEFINE_HASHTABLE(name, bits)의 bits 값 선택 기준:

캐시 라인(Cache Line) 최적화

해시 테이블 성능에 영향을 미치는 캐시 관련 요소:

• 버킷 배열 접근 — hlist_head는 8바이트이므로 한 캐시 라인(64바이트)에 8개 버킷이 들어감. 인접 버킷 접근 시 캐시 히트 가능
• 체인 순회 — 체인 노드가 서로 다른 slab 객체에 분산되어 있으면 캐시 미스 연쇄 발생. 짧은 체인(로드 팩터 ≤ 1)이 핵심
• 키와 hlist_node 배치 — 구조체에서 키 필드와 hlist_node를 같은 캐시 라인에 배치하면 검색 시 캐시 미스 감소
• Prefetching — 고성능 경로에서는 prefetch(next)로 다음 체인 노드를 미리 로드

Per-CPU 해시와 NUMA 최적화

고성능 네트워킹 경로에서 해시 테이블의 경합(contention)을 줄이기 위해 커널은 Per-CPU 분할 해시 패턴을 사용합니다. 하나의 거대한 해시 테이블 대신, CPU별로 독립된 해시 테이블(또는 버킷 세그먼트)을 운영하여 캐시 바운싱과 lock 경합을 최소화합니다.

주요 Per-CPU 해시 패턴

Per-CPU 해시 구현 예

/* Per-CPU 해시 테이블 패턴: 통계 수집용 */
#include <linux/percpu.h>
#include <linux/hashtable.h>

struct stat_entry {
    u32                 key;
    atomic64_t          count;
    struct hlist_node   node;
};

/* CPU별 256-버킷 해시 테이블 */
struct per_cpu_ht {
    DECLARE_HASHTABLE(ht, 8);
    spinlock_t lock;
};

static DEFINE_PER_CPU(struct per_cpu_ht, cpu_stats);

/* Hot path: 현재 CPU 테이블 사용 + 로컬 lock으로 IRQ/softirq 경합 방지 */
static void count_event(u32 key)
{
    struct per_cpu_ht *pht;
    struct stat_entry *entry;
    unsigned long flags;

    preempt_disable();
    pht = this_cpu_ptr(&cpu_stats);
    spin_lock_irqsave(&pht->lock, flags);

    hash_for_each_possible(pht->ht, entry, node, key) {
        if (entry->key == key) {
            atomic64_inc(&entry->count);
            spin_unlock_irqrestore(&pht->lock, flags);
            preempt_enable();
            return;
        }
    }
    spin_unlock_irqrestore(&pht->lock, flags);
    preempt_enable();
    /* miss: 새 엔트리 할당 후 삽입 (생략) */
}

NUMA 환경 해시 테이블 팁

• 노드 로컬 할당 — kvmalloc_node()로 해시 버킷 배열을 접근 빈도가 높은 NUMA 노드에 할당
• 인터리브 할당 — 대규모 공유 해시는 vmalloc()(페이지 단위 인터리브)로 NUMA 노드 간 균등 분배
• lock 분리 — NUMA 노드 간 lock 공유를 최소화하여 캐시 라인 바운싱 방지
• rhashtable 기본 동작 — kvmalloc() 사용 시 vmalloc 폴백이 자동으로 NUMA 인터리브

커널 활용 사례

conntrack (nf_conntrack)

Netfilter의 연결 추적 테이블은 커널의 가장 대표적인 rhashtable 활용 사례 중 하나입니다. 네트워크 연결의 5-tuple(프로토콜, 소스/목적지 IP, 소스/목적지 포트)을 키로 해시하여 초당 수백만 패킷의 연결 상태를 빠르게 조회합니다.

/* include/net/netfilter/nf_conntrack.h */
struct nf_conntrack_tuple_hash {
    struct hlist_nulls_node    hnnode;    /* nulls 마커가 있는 hlist */
    struct nf_conntrack_tuple  tuple;
};

/* 하나의 연결은 방향별 2개의 tuple_hash를 가짐 */
struct nf_conn {
    struct nf_conntrack_tuple_hash tuplehash[IP_CT_DIR_MAX];
    unsigned long                 status;      /* 연결 상태 비트맵 */
    possible_net_t                ct_net;
    struct hlist_node             nat_bysource;
    /* ... */
    spinlock_t                    lock;
    u32                           timeout;     /* jiffies 기반 만료 */
    u16                           mark;
    /* ... */
};

/* net/netfilter/nf_conntrack_core.c */
/* conntrack 해시 테이블 구조: hlist_nulls_head 배열 */
/* net->ct.hash: 동적 크기 해시, nf_conntrack_htable_size 버킷 */
/* 해시 함수: jhash2() + 랜덤 시드(nf_conntrack_hash_rnd) */

/* 연결 검색 경로 (패킷 수신 hot path) */
static struct nf_conntrack_tuple_hash *
____nf_conntrack_find(struct net *net,
                     const struct nf_conntrack_zone *zone,
                     const struct nf_conntrack_tuple *tuple,
                     u32 hash)
{
    struct nf_conntrack_tuple_hash *h;
    struct hlist_nulls_head *ct_hash;
    struct hlist_nulls_node *n;
    unsigned int bucket, hsize;

begin:
    nf_conntrack_get_ht(&ct_hash, &hsize);
    bucket = reciprocal_scale(hash, hsize);

    hlist_nulls_for_each_entry_rcu(h, n, &ct_hash[bucket], hnnode) {
        if (nf_ct_key_equal(h, tuple, zone, net))
            return h;
    }

    /* nulls 마커 검증: 리사이즈로 인한 버킷 이동 감지 */
    if (get_nulls_value(n) != bucket) {
        /* 테이블이 바뀌었으므로 재시도 */
        goto begin;
    }
    return NULL;
}

inode 해시 테이블

/* fs/inode.c */
static struct hlist_head *inode_hashtable;

/* inode 검색: superblock + inode number로 해시 */
struct inode *ilookup(struct super_block *sb, unsigned long ino)
{
    struct hlist_head *head = inode_hashtable +
                              hash(sb, ino);
    /* head에서 hlist 순회로 검색 */
}

PID 해시

/* kernel/pid.c */
struct pid {
    refcount_t           count;
    unsigned int         level;
    spinlock_t           lock;
    struct hlist_head    tasks[PIDTYPE_MAX];
    struct hlist_head    inodes;
    wait_queue_head_t    wait_pidfd;
    struct rcu_head      rcu;
    struct upid          numbers[];  /* pid namespace 계층 */
};

/* struct upid는 해시 테이블에 연결 */
struct upid {
    int                  nr;        /* PID 번호 */
    struct pid_namespace *ns;
    struct hlist_node    pid_chain; /* pid_hash[]에 연결 */
};

dentry 캐시 (dcache)

/* fs/dcache.c */
static struct hlist_bl_head *dentry_hashtable;

/* 해시 키: parent dentry + 파일명 해시 */
/* full_name_hash()로 파일명 해싱 */
/* hlist_bl: bit-locked hlist (비트 스핀락 내장) */

네트워크 소켓 해시

모듈 심볼 해시

해시 테이블 구조 다이어그램

자료구조 선택 가이드

상황별 의사결정 트리

아래 질문 순서대로 내려가면, 자료구조 후보를 빠르게 좁힐 수 있습니다.

1. 정렬/범위 검색이 필요한가?
   필요하면 rbtree 또는 XArray를 우선 검토합니다.
2. 키가 정수 인덱스 중심인가?
   정수 sparse 인덱스면 XArray, 일반 복합 키면 해시 계열로 갑니다.
3. 정확 매칭 lookup이 압도적인가?
   그렇다면 해시 테이블이 1차 선택입니다.
4. 요소 수 변동이 큰가?
   변동이 크면 rhashtable, 대체로 고정이면 hashtable.h가 단순합니다.
5. 외부 입력 키인가?
   공격 노출 경로면 siphash 기반 해시 정책을 우선합니다.

디버깅 팁

crash 유틸리티로 해시 테이블 덤프

# 실습 예제: crash 셸에서 해시 테이블 구조 확인
crash> struct hlist_head inode_hashtable 10

# 특정 버킷의 체인 순회
crash> list hlist_node -H 0xffff...addr -s my_object.key,data

# DEFINE_HASHTABLE로 선언된 전역 해시 테이블
crash> p my_ht
crash> struct hlist_head my_ht 256

drgn으로 해시 테이블 분석

# 실습 예제: drgn 스크립트로 해시 테이블 통계 수집
import drgn
from drgn.helpers.linux.list import hlist_for_each_entry

prog = drgn.program_from_kernel()

# 각 버킷의 체인 길이 측정
ht = prog["my_ht"]
for i in range(len(ht)):
    count = 0
    for entry in hlist_for_each_entry("struct my_object",
                                       ht[i], "hash_node"):
        count += 1
    if count > 0:
        print(f"bucket[{i}]: {count} entries")

일반적 실수와 해결

운영 장애 트러블슈팅 플레이북

운영 중 해시 테이블 병목(Bottleneck)이 의심될 때는 아래 순서로 점검하면 원인 분리 속도가 빨라집니다.

1. 현상 분류
   증상이 “lookup 지연 증가”인지, “삽입 실패(-ENOMEM/-EAGAIN)”인지 먼저 구분합니다.
2. 분포 확인
   버킷별 체인 길이(평균/최대/분산)를 수집해 편향 여부를 확인합니다.
3. 락 경합 확인
   perf lock, bpftrace로 특정 버킷/경로 lock hot spot을 찾습니다.
4. RCU 수명 확인
   삭제 후 즉시 해제, unlock 이후 포인터 사용 같은 수명 위반 패턴을 점검합니다.
5. 튜닝/수정 적용
   해시 함수 개선, bits/size 조정, rhashtable 파라미터 조정 후 동일 시나리오 재측정합니다.

해시 테이블 모니터링

운영 중인 커널의 해시 테이블 성능을 실시간으로 측정하는 방법입니다. 체인 길이 불균형, 과도한 리사이즈, 캐시 미스 등의 문제를 조기에 발견할 수 있습니다.

conntrack 해시 통계

# conntrack 해시 테이블 크기와 사용량
cat /proc/sys/net/netfilter/nf_conntrack_buckets    # 버킷 수
cat /proc/sys/net/netfilter/nf_conntrack_count      # 현재 연결 수
cat /proc/sys/net/netfilter/nf_conntrack_max        # 최대 연결 수

# 로드 팩터 계산
echo "scale=2; $(cat /proc/sys/net/netfilter/nf_conntrack_count) / \
  $(cat /proc/sys/net/netfilter/nf_conntrack_buckets)" | bc

# conntrack 상세 통계
cat /proc/net/stat/nf_conntrack | head -2

# 동적 버킷 수 변경 (런타임)
echo 65536 > /proc/sys/net/netfilter/nf_conntrack_buckets

bpftrace로 해시 성능 측정

# rhashtable 삽입/삭제 빈도 추적
bpftrace -e '
kprobe:rhashtable_insert_fast { @inserts = count(); }
kprobe:rhashtable_remove_fast { @removes = count(); }
interval:s:5 { print(@inserts); print(@removes);
               clear(@inserts); clear(@removes); }
'

# rhashtable 리사이즈 이벤트 감지
bpftrace -e '
kprobe:rhashtable_rehash_one {
    @rehash_count = count();
    @rehash_cpu = hist(cpu);
}
kprobe:bucket_table_alloc {
    printf("resize: new table alloc at %lld\n", nsecs);
}'

# 해시 함수 호출 빈도 (jhash vs hash_long)
bpftrace -e '
kprobe:jhash { @jhash = count(); }
interval:s:10 { print(@jhash); clear(@jhash); }
'

perf로 캐시 미스 분석

# 해시 테이블 순회 관련 LLC 미스 (conntrack 경로)
perf stat -e cache-misses,cache-references,L1-dcache-load-misses \
    -p $(pgrep ksoftirqd/0) -- sleep 10

# 특정 함수의 캐시 미스 프로파일
perf record -e cache-misses -g -p $(pgrep ksoftirqd/0) -- sleep 5
perf report --symbol-filter=nf_conntrack

# lock 경합 프로파일
perf lock record -- sleep 5
perf lock report

디버깅 관련 커널 설정

해시 테이블 운영 체크리스트

커널 해시는 성능만큼 충돌 관리와 동시성 설계가 중요합니다. 버킷 수, 해시 함수, 락 모델을 함께 설계해야 예측 가능한 성능이 나옵니다.

# 충돌/리사이즈 경로 추적
git grep -n "hash_add\\|hash_for_each\\|rhashtable" -- "*.c"
perf stat -e cache-misses,cache-references -- sleep 5

jhash/xxhash 비교 분석

리눅스 커널은 용도별로 다양한 해시 함수를 제공합니다. 이 섹션에서는 jhash(Jenkins hash), xxhash, siphash의 내부 동작 원리를 비교하고, 각 함수가 어떤 상황에서 최적인지 분석합니다.

jhash 구현 분석

jhash(Jenkins hash)는 Bob Jenkins가 설계한 해시 함수로, 커널에서 <linux/jhash.h>로 제공됩니다. 가변 길이 바이트 배열과 고정 크기 word 배열 모두를 처리할 수 있습니다.

/* include/linux/jhash.h — 핵심 mixing 매크로 */
#define __jhash_mix(a, b, c) \
({ \
    a -= c;  a ^= rol32(c,  4);  c += b; \
    b -= a;  b ^= rol32(a,  6);  a += c; \
    c -= b;  c ^= rol32(b,  8);  b += a; \
    a -= c;  a ^= rol32(c, 16);  c += b; \
    b -= a;  b ^= rol32(a, 19);  a += c; \
    c -= b;  c ^= rol32(b,  4);  b += a; \
})

/* jhash2() — u32 배열을 해싱 (conntrack 5-tuple 등) */
static inline u32 jhash2(const u32 *k, u32 length, u32 initval)
{
    u32 a, b, c;
    a = b = c = JHASH_INITVAL + (length << 2) + initval;

    /* 3 words씩 처리 — mixing loop */
    while (length > 3) {
        a += k[0]; b += k[1]; c += k[2];
        __jhash_mix(a, b, c);
        length -= 3; k += 3;
    }
    /* 나머지 처리 + final mixing */
    switch (length) {
    case 3: c += k[2];  /* fallthrough */
    case 2: b += k[1];  /* fallthrough */
    case 1: a += k[0];
        __jhash_final(a, b, c);
    case 0: break;
    }
    return c;
}

xxhash 구현 분석

xxhash는 Yann Collet이 설계한 고속 해시 함수로, 커널 4.14에서 lib/xxhash.c로 도입되었습니다. 대용량 데이터 처리에서 jhash보다 월등한 처리량을 제공합니다.

/* lib/xxhash.c — 핵심 accumulator 처리 */
static u64 xxh64_round(u64 acc, u64 input)
{
    acc += input * XXH_PRIME64_2;
    acc  = rol64(acc, 31);
    acc *= XXH_PRIME64_1;
    return acc;
}

/* 32바이트 stripe를 4개 accumulator로 병렬 처리 */
while (p + 32 <= b_end) {
    v1 = xxh64_round(v1, get_unaligned_le64(p +  0));
    v2 = xxh64_round(v2, get_unaligned_le64(p +  8));
    v3 = xxh64_round(v3, get_unaligned_le64(p + 16));
    v4 = xxh64_round(v4, get_unaligned_le64(p + 24));
    p  += 32;
}

/* 커널 사용 사례: btrfs 체크섬 */
/* fs/btrfs/hash.c */
u64 btrfs_name_hash(const char *name, int len)
{
    return xxh64(name, len, 0);
}

해시 함수 종합 비교

rhashtable 리사이즈 메커니즘

rhashtable은 로드 팩터에 따라 자동으로 확장(grow)과 축소(shrink)를 수행합니다. 리사이즈 과정에서 두 개의 테이블이 동시에 존재하며, RCU를 활용해 읽기 측은 락 없이 접근할 수 있습니다. 이 섹션에서는 리사이즈의 내부 메커니즘을 단계별로 분석합니다.

rhashtable_init 파라미터

/* lib/rhashtable.c — 초기화 핵심 파라미터 */
struct rhashtable_params params = {
    .nelem_hint         = 1024,      /* 예상 초기 요소 수 → 버킷 수 결정 */
    .key_len            = 16,        /* 고정 키 크기 (바이트) */
    .key_offset         = offsetof(struct my_obj, key),
    .head_offset        = offsetof(struct my_obj, node),
    .max_size           = 1 << 20,   /* 최대 버킷 수 (1M) */
    .min_size           = 64,        /* 최소 버킷 수 */
    .automatic_shrinking = true,     /* 로드 팩터 30% 미만 시 자동 축소 */
    .hashfn             = jhash,
    .obj_hashfn         = my_obj_hash,
};

int ret = rhashtable_init(&my_ht, &params);
if (ret)
    return ret;

리사이즈 트리거 조건

리사이즈 중 동시 접근

/* 리사이즈 중 룩업 — 두 테이블 모두 검색 */
/* lib/rhashtable.c: rhashtable_lookup_fast() 내부 */
rcu_read_lock();
tbl = rht_dereference_rcu(ht->tbl, ht);
restart:
hash = rht_key_hashfn(ht, tbl, key, params);
head = rht_bucket(tbl, hash);

rht_for_each_rcu(he, head) {
    if (params.obj_cmpfn ?
        params.obj_cmpfn(&arg, rht_obj(ht, he)) == 0 :
        rhashtable_compare(&arg, rht_obj(ht, he)) == 0)
        return rht_obj(ht, he);
}

/* 구 테이블에서 못 찾으면 → 신 테이블에서 재시도 */
new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);
if (unlikely(new_tbl)) {
    tbl = new_tbl;
    goto restart;  /* 신 테이블에서 다시 검색 */
}
rcu_read_unlock();

ftrace/perf 디버깅 실습

해시 테이블의 성능 문제는 충돌 편중, 리사이즈 빈도, 락 경합으로 나타납니다. 커널의 ftrace, bpftrace, perf 도구로 이러한 문제를 실시간 진단할 수 있습니다.

ftrace로 해시 연산 추적

# rhashtable 리사이즈 추적
echo 'rhashtable_rehash_one' > /sys/kernel/tracing/set_ftrace_filter
echo function > /sys/kernel/tracing/current_tracer
echo 1 > /sys/kernel/tracing/tracing_on

# 10초 추적 후 결과 확인
sleep 10
echo 0 > /sys/kernel/tracing/tracing_on
cat /sys/kernel/tracing/trace

# function_graph로 리사이즈 호출 흐름 확인
echo 'rhashtable_rehash_table' > /sys/kernel/tracing/set_graph_function
echo function_graph > /sys/kernel/tracing/current_tracer

bpftrace로 해시 분포 분석

# conntrack 해시값 분포 히스토그램
bpftrace -e '
kprobe:nf_conntrack_hash {
    @dist = lhist(arg1 % 1024, 0, 1024, 32);
}
interval:s:10 { exit(); }
'

# rhashtable 체인 길이 측정 (kretprobe 활용)
bpftrace -e '
kprobe:rhashtable_lookup_fast {
    @start[tid] = nsecs;
}
kretprobe:rhashtable_lookup_fast /@start[tid]/ {
    @lookup_ns = hist(nsecs - @start[tid]);
    delete(@start[tid]);
}
interval:s:30 { exit(); }
'

perf로 해시 룩업 지연 측정

# 해시 룩업 관련 캐시 미스 측정
perf stat -e cache-misses,cache-references,instructions \
    -a -G "rhashtable" -- sleep 5

# 해시 테이블 룩업 함수에 동적 프로브 설정
perf probe --add 'rhashtable_lookup_fast'
perf record -e probe:rhashtable_lookup_fast -a -- sleep 10
perf report --sort=comm,dso

# lock contention 분석
perf lock record -a -- sleep 5
perf lock report

성능 벤치마크 비교

자료구조 선택은 워크로드 특성에 따라 성능이 크게 달라집니다. 이 섹션에서는 hashtable, rhashtable, XArray, rbtree의 데이터 크기별 성능 특성과 캐시/NUMA 환경에서의 차이를 분석합니다.

자료구조별 성능 특성 비교

캐시 동작 분석

해시 테이블의 실제 성능은 알고리즘 복잡도보다 캐시 미스 비율에 더 크게 좌우됩니다.

해시 테이블 보안 고려사항

해시 테이블은 외부 입력으로 키가 결정되는 경우 HashDoS(Hash collision Denial of Service) 공격에 취약합니다. 공격자가 동일 버킷에 매핑되는 키를 의도적으로 생성하면 O(1) 성능이 O(n)으로 퇴화하여 서비스 거부가 발생합니다. 이 섹션에서는 커널의 보안 대응 전략과 siphash 도입 과정을 분석합니다.

siphash 도입 과정

커널은 2017년(v4.13 전후)부터 네트워크 스택(Network Stack)의 해시 함수를 jhash에서 siphash로 점진적으로 교체했습니다. 이는 실제 HashDoS 공격 사례에 대한 대응이었습니다.

/* net/core/utils.c — 부팅 시 비밀 시드 생성 */
static siphash_key_t net_secret __read_mostly;
static __always_inline void net_secret_init(void)
{
    net_get_random_once(&net_secret, sizeof(net_secret));
}

/* net/ipv4/inet_hashtables.c — 소켓 해시에서 siphash 사용 */
static u32 inet_ehashfn(const struct net *net,
    const __be32 laddr, const __u16 lport,
    const __be32 faddr, const __be16 fport)
{
    /* siphash로 4-tuple 해싱 — 비밀 키 포함 */
    static siphash_key_t inet_ehash_secret;
    net_get_random_once(&inet_ehash_secret,
                        sizeof(inet_ehash_secret));
    return __inet_ehashfn(laddr, lport, faddr, fport,
                          &inet_ehash_secret);
}

Per-Boot Random Seed

/* include/linux/net.h — net_hash_mix(): NUMA/네임스페이스 혼합 */
static inline u32 net_hash_mix(const struct net *net)
{
    /* 네트워크 네임스페이스별로 서로 다른 해시 결과 */
    return net_hash_31(net_hash(net));
}

/* 사용 예: conntrack 해시에 네임스페이스 시드 혼합 */
static u32 hash_conntrack_raw(
    const struct nf_conntrack_tuple *tuple,
    const struct net *net)
{
    return jhash2((const u32 *)tuple,
        sizeof(*tuple) / sizeof(u32),
        nf_conntrack_hash_rnd ^ net_hash_mix(net));
        /* nf_conntrack_hash_rnd: 부팅 시 랜덤 생성 */
}

보안 체크리스트

커널 핵심 함수 구현 분석

이 섹션에서는 해시 테이블의 핵심 연산(rhashtable_lookup_fast, rhashtable_insert_fast, hlist_for_each_entry 매크로)이 내부적으로 어떻게 동작하는지 소스 레벨에서 분석합니다. 단순 API 사용법을 넘어 포인터 조작과 RCU 프로토콜의 상호작용을 이해하면, 성능 병목 진단과 커스텀 자료구조 설계에 직접적인 도움이 됩니다.

rhashtable_lookup_fast() 내부 구현

rhashtable_lookup_fast()는 rhashtable에서 가장 빈번하게 호출되는 함수입니다. RCU 보호 하에 lock-free로 동작하며, 리사이즈 중에도 정확한 결과를 보장합니다. 내부 흐름을 단계별로 분석합니다.

/* include/linux/rhashtable.h — rhashtable_lookup_fast() 내부 구현 분석 */

/*
 * 호출 전제: rcu_read_lock() 보유 상태여야 합니다.
 *
 * 전체 흐름:
 * 1. 현재 테이블(tbl) 가져오기 (RCU dereference)
 * 2. 키를 해시하여 버킷 인덱스 계산
 * 3. 해당 버킷의 체인을 순회하며 키 비교
 * 4. nulls 마커로 테이블 전환 감지 → 불일치 시 재시도
 * 5. future_tbl이 존재하면 새 테이블에서도 검색
 */

static inline void *rhashtable_lookup_fast(
    struct rhashtable *ht,
    const void *key,
    const struct rhashtable_params params)
{
    struct rhashtable *ht;
    struct bucket_table *tbl;
    struct rhash_head *he;
    unsigned int hash;

    /* ① RCU로 현재 버킷 테이블을 안전하게 가져옴.
     *    다른 CPU가 리사이즈로 tbl을 교체하더라도
     *    이 참조는 grace period 동안 유효 */
    tbl = rht_dereference_rcu(ht->tbl, ht);

restart:
    /* ② 키를 해시하여 버킷 인덱스 계산.
     *    params.hashfn이 지정되어 있으면 사용,
     *    아니면 jhash(key, key_len, tbl->hash_rnd) */
    hash = rht_key_hashfn(ht, tbl, key, params);

    /* ③ 해당 버킷의 체인을 RCU로 순회 */
    rht_for_each_rcu(he, tbl, hash) {
        /* ④ 키 비교: params.obj_cmpfn이 있으면 호출,
         *    없으면 memcmp(key, obj + key_offset, key_len) */
        if (params.obj_cmpfn ?
            params.obj_cmpfn(&arg, rht_obj(ht, he)) == 0 :
            rhashtable_compare(&arg, rht_obj(ht, he)) == 0)
            return rht_obj(ht, he);
    }

    /* ⑤ Nulls 마커 검증:
     *    체인 끝의 nulls 값에 인코딩된 버킷 번호가
     *    현재 계산한 hash와 일치하는지 확인.
     *    불일치 → 리사이즈로 요소가 이동되었으므로 재시도 */
    if (get_nulls_value(he) != (hash & rht_bucket_mask(tbl)))
        goto restart;

    /* ⑥ 리사이즈 진행 중이면 새 테이블에서도 검색.
     *    future_tbl은 리사이즈 완료 전까지 유효.
     *    tbl을 새 테이블로 교체하고 처음부터 다시 검색 */
    tbl = rht_dereference_rcu(tbl->future_tbl, ht);
    if (unlikely(tbl))
        goto restart;

    return NULL;
}

rhashtable_insert_fast() 내부 구현

삽입 함수는 per-bucket lock을 획득한 후 체인 앞에 노드를 추가하며, 로드 팩터 검사 후 필요하면 비동기 리사이즈를 예약합니다. 중복 키 검사, 탄성 한계 검사, 리사이즈 중 삽입 위치 결정 등 복잡한 로직을 포함합니다.

/* lib/rhashtable.c — rhashtable_insert_fast() 핵심 흐름 분석 */

/*
 * 삽입 과정 요약:
 * 1. 키 해시 → 버킷 인덱스 결정
 * 2. per-bucket spinlock 획득 (bit-spin-lock)
 * 3. 중복 키 검사 (체인 순회)
 * 4. 체인 길이 검사 (RHT_ELASTICITY 초과 시 -EAGAIN)
 * 5. hlist_nulls 체인 앞에 노드 삽입 (RCU publish)
 * 6. 요소 카운터 증가 + 리사이즈 필요 여부 검사
 * 7. per-bucket spinlock 해제
 */

static struct bucket_table *rhashtable_insert_one(
    struct rhashtable *ht,
    struct bucket_table *tbl,
    unsigned int hash,
    struct rhash_head *obj,
    void *data)
{
    struct rhash_lock_head __rcu **bkt;
    struct rhash_head __rcu **pprev;
    struct rhash_head *head;
    int elasticity;

    /* ① 버킷 포인터 주소 계산 */
    bkt = rht_bucket_var(tbl, hash);
    if (!bkt)
        return ERR_PTR(-ENOMEM);

    /* ② 버킷 스핀락 이미 획득된 상태에서 호출됨.
     *    체인 첫 요소를 가져옴 (lock bit 마스킹) */
    head = rht_ptr(bkt, tbl, hash);

    /* ③ 중복 키 검사: 체인을 순회하며 동일 키 존재 여부 확인 */
    elasticity = RHT_ELASTICITY;  /* 기본값: 16 */
    rht_for_each(head, tbl, hash) {
        if (unlikely(rht_key_cmp(ht, head, key)))
            return ERR_PTR(-EEXIST);

        /* ④ 탄성 한계 검사: 체인이 너무 길면 삽입 거부 */
        if (!--elasticity)
            return ERR_PTR(-EAGAIN);
    }

    /* ⑤ future_tbl이 존재하면(리사이즈 진행 중)
     *    새 테이블에 삽입해야 하므로 현재 테이블 삽입 포기 */
    if (rht_dereference_bucket_rcu(tbl->future_tbl, tbl, hash))
        return tbl->future_tbl;

    /* ⑥ 체인 앞에 노드 삽입 (RCU-safe publish)
     *    head = 기존 첫 노드, obj->next = head
     *    버킷 포인터 = obj (rcu_assign_pointer) */
    head = rht_ptr(bkt, tbl, hash);
    RCU_INIT_POINTER(obj->next, head);
    rht_assign_locked(bkt, obj);

    /* ⑦ 전체 요소 수 증가 */
    atomic_inc(&ht->nelems);

    /* ⑧ 로드 팩터 검사: 75% 초과 시 비동기 리사이즈 예약 */
    if (rht_grow_above_75(ht, tbl))
        schedule_work(&ht->run_work);

    return NULL;  /* 성공 */
}

hlist_for_each_entry 매크로 확장 분석

hlist_for_each_entry()는 해시 테이블 순회의 기반 매크로입니다. container_of를 통해 hlist_node에서 실제 구조체를 추출하는 방식을 이해하면, 모든 해시 테이블 순회 코드를 자연스럽게 읽을 수 있습니다.

/* include/linux/list.h — 매크로 확장 과정 */

/* 원본 매크로 정의 */
#define hlist_for_each_entry(pos, head, member) \
    for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))

/* hlist_entry_safe 정의 */
#define hlist_entry_safe(ptr, type, member) \
    ({ typeof(ptr) ____ptr = (ptr); \
       ____ptr ? hlist_entry(____ptr, type, member) : NULL; })

/* hlist_entry = container_of 래퍼 */
#define hlist_entry(ptr, type, member) \
    container_of(ptr, type, member)

/* ─────────────────────────────────────────────────
 * 전개 예시:
 *
 * struct my_object { int key; struct hlist_node node; };
 * struct my_object *obj;
 * hlist_for_each_entry(obj, &head, node)
 *
 * →  for (obj = ({ typeof((&head)->first) ____ptr = (&head)->first;
 *                  ____ptr ? container_of(____ptr, struct my_object, node)
 *                          : NULL; });
 *          obj;
 *          obj = ({ typeof((obj)->node.next) ____ptr = (obj)->node.next;
 *                   ____ptr ? container_of(____ptr, struct my_object, node)
 *                           : NULL; }))
 *
 * 핵심: hlist_node 포인터 → container_of로 부모 구조체 주소 역산
 *       NULL 체크로 안전한 순회 종료
 * ───────────────────────────────────────────────── */

container_of 역산 원리

my_object 구조체 메모리 레이아웃 (예시):

+0x00  ┌──────────┐
       │ key (4B)  │
+0x04  │ padding   │
+0x08  ├──────────┤ ← &obj->node (hlist_node 시작)
       │ next (8B) │
+0x10  │ pprev(8B) │
+0x18  └──────────┘

hlist_node의 주소가 0xFFFF1008이면:

container_of(0xFFFF1008, struct my_object, node)
= (struct my_object *)(0xFFFF1008 - offsetof(struct my_object, node))
= (struct my_object *)(0xFFFF1008 - 0x08)
= (struct my_object *)0xFFFF1000

이것이 해시 테이블에서 "노드 → 객체" 변환의 핵심 원리입니다.

rht_for_each_rcu 매크로 내부 구현

rht_for_each_rcu()는 rhashtable의 버킷 체인을 RCU 보호 하에 순회하는 매크로입니다. 일반 hlist_for_each_entry_rcu()와 달리 nulls 마커를 인식하는 것이 핵심 차이입니다.

/* include/linux/rhashtable.h — rht_for_each_rcu 내부 */

/* 버킷에서 첫 번째 요소를 RCU-safe로 가져옴 */
#define rht_for_each_rcu(pos, tbl, hash) \
    for (pos = rht_ptr_rcu(rht_bucket(tbl, hash)); \
         !rht_is_a_nulls(pos); \
         pos = rcu_dereference_raw(pos->next))

/* nulls 마커 판별:
 * 일반 포인터: 정렬 보장으로 LSB=0
 * nulls 마커:  LSB=1, 상위 비트에 버킷 인덱스 인코딩
 *
 * rht_is_a_nulls(ptr) = ((unsigned long)ptr & 1)
 *
 * 체인 예시:
 *   bucket[3] → [obj_A] → [obj_B] → (3 << 1 | 1) = 0x7
 *                                     ↑ nulls 마커 (버킷 3)
 *
 * 읽기 측이 순회 후 nulls 값이 3이 아니면
 * 리사이즈로 인해 버킷이 바뀐 것이므로 재시도합니다.
 */

hash_long() 수학적 원리

hash_long()이 사용하는 Golden Ratio 곱셈 해싱은 Fibonacci Hashing이라고도 불리며, 수학적으로 왜 좋은 분포를 만드는지 분석합니다.

hash_long(val, bits)의 원리: (val * GOLDEN_RATIO_64) >> (64 - bits)

왜 Golden Ratio인가?

황금비(φ) = (1 + √5) / 2 ≈ 1.6180339887이며, 이의 역수 1/φ = φ - 1 ≈ 0.6180339887은 "무리수 중에서 유리수로 근사하기 가장 어려운 수"입니다 (3-distance theorem / Steinhaus theorem). 이 성질 때문에 연속 정수 × φ의 소수 부분이 [0, 1) 구간에서 가장 균등하게 분포합니다.

GOLDEN_RATIO_64 = 2⁶⁴ / φ = 2⁶⁴ × (φ - 1) = 0x61C8864680B583EB

곱셈 후 상위 bits를 추출하는 이유

val × GOLDEN_RATIO_64는 128비트 결과를 산출합니다. 이 중 상위 64비트(C에서는 자연 오버플로)가 가장 좋은 분산을 가집니다. >> (64 - bits)로 상위 bits 비트만 추출하면 [0, 2^bits) 범위에서 균등한 분포를 얻습니다.

연속 정수 해싱 예시 (bits=3, 8 버킷):

0~7까지 모든 버킷에 정확히 1개씩 매핑됩니다. 일반 modulo 방식에서는 연속 정수가 인접 버킷에 몰려 편향이 발생할 수 있습니다.

실전 구현 예제

이 섹션에서는 커널 모듈에서 해시 테이블을 실전적으로 사용하는 완전한 예제를 제공합니다. 각 예제는 독립적으로 컴파일·로드할 수 있으며, 실제 커널 서브시스템에서 사용되는 패턴을 반영합니다.

예제 1: RCU 보호 해시 테이블 커널 모듈

hashtable.h와 RCU를 조합한 완전한 커널 모듈입니다. /proc 인터페이스로 삽입·검색·삭제를 수행하며, 읽기 측은 lock-free, 쓰기 측은 spinlock으로 보호합니다.

/* 실습 예제: RCU 보호 해시 테이블 커널 모듈 (rcu_hashtable_demo.c) */
#include <linux/module.h>
#include <linux/hashtable.h>
#include <linux/slab.h>
#include <linux/rcupdate.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("RCU-protected hash table demo");

/* 10-bit → 1024 버킷 */
static DEFINE_HASHTABLE(demo_ht, 10);
static DEFINE_SPINLOCK(demo_lock);

struct demo_entry {
    u32                key;
    char               value[64];
    struct hlist_node  hash_node;
    struct rcu_head    rcu;       /* kfree_rcu 콜백용 */
};

/* ─── 삽입 (쓰기 경로) ─── */
static int demo_insert(u32 key, const char *val)
{
    struct demo_entry *entry, *existing;

    entry = kzalloc(sizeof(*entry), GFP_KERNEL);
    if (!entry)
        return -ENOMEM;

    entry->key = key;
    strscpy(entry->value, val, sizeof(entry->value));

    spin_lock(&demo_lock);

    /* 중복 키 검사 */
    hash_for_each_possible(demo_ht, existing, hash_node, key) {
        if (existing->key == key) {
            spin_unlock(&demo_lock);
            kfree(entry);
            return -EEXIST;
        }
    }

    hash_add_rcu(demo_ht, &entry->hash_node, key);
    spin_unlock(&demo_lock);

    pr_info("demo_ht: inserted key=%u val=%s\n", key, val);
    return 0;
}

/* ─── 검색 (읽기 경로, lock-free) ─── */
static struct demo_entry *demo_lookup(u32 key)
{
    struct demo_entry *entry;

    /* rcu_read_lock()은 호출자가 보유해야 합니다 */
    hash_for_each_possible_rcu(demo_ht, entry, hash_node, key) {
        if (entry->key == key)
            return entry;
    }
    return NULL;
}

/* ─── 삭제 (쓰기 경로) ─── */
static int demo_delete(u32 key)
{
    struct demo_entry *entry;

    spin_lock(&demo_lock);
    hash_for_each_possible(demo_ht, entry, hash_node, key) {
        if (entry->key == key) {
            hash_del_rcu(&entry->hash_node);
            spin_unlock(&demo_lock);

            /* grace period 후 안전하게 해제 */
            kfree_rcu(entry, rcu);
            pr_info("demo_ht: deleted key=%u\n", key);
            return 0;
        }
    }
    spin_unlock(&demo_lock);
    return -ENOENT;
}

/* ─── /proc/demo_ht 읽기 (전체 테이블 덤프) ─── */
static int demo_show(struct seq_file *m, void *v)
{
    struct demo_entry *entry;
    unsigned int bkt;
    unsigned int count = 0;

    rcu_read_lock();
    hash_for_each_rcu(demo_ht, bkt, entry, hash_node) {
        seq_printf(m, "[bucket %3u] key=%-10u value=%s\n",
                   bkt, entry->key, entry->value);
        count++;
    }
    rcu_read_unlock();

    seq_printf(m, "--- total: %u entries, %u buckets ---\n",
               count, HASH_SIZE(demo_ht));
    return 0;
}

static int demo_open(struct inode *inode, struct file *file)
{
    return single_open(file, demo_show, NULL);
}

static const struct proc_ops demo_proc_ops = {
    .proc_open    = demo_open,
    .proc_read    = seq_read,
    .proc_lseek   = seq_lseek,
    .proc_release = single_release,
};

/* ─── 모듈 초기화/정리 ─── */
static int __init demo_init(void)
{
    proc_create("demo_ht", 0444, NULL, &demo_proc_ops);

    /* 테스트 데이터 삽입 */
    demo_insert(100, "alpha");
    demo_insert(200, "beta");
    demo_insert(300, "gamma");
    demo_insert(1124, "delta");  /* 100과 같은 버킷(해시 충돌 가능) */

    pr_info("demo_ht: module loaded\n");
    return 0;
}

static void __exit demo_exit(void)
{
    struct demo_entry *entry;
    struct hlist_node *tmp;
    unsigned int bkt;

    remove_proc_entry("demo_ht", NULL);

    /* 모든 엔트리 안전하게 삭제 */
    spin_lock(&demo_lock);
    hash_for_each_safe(demo_ht, bkt, tmp, entry, hash_node) {
        hash_del_rcu(&entry->hash_node);
        kfree_rcu(entry, rcu);
    }
    spin_unlock(&demo_lock);

    synchronize_rcu();  /* 모든 RCU 콜백 완료 대기 */
    pr_info("demo_ht: module unloaded\n");
}

module_init(demo_init);
module_exit(demo_exit);

예제 2: rhashtable 완전한 커널 모듈

rhashtable을 사용하는 완전한 커널 모듈입니다. 자동 리사이즈, 원자적 검색+삽입, walker를 통한 안전한 순회를 보여줍니다.

/* 실습 예제: rhashtable 기반 커널 모듈 (rht_demo.c) */
#include <linux/module.h>
#include <linux/rhashtable.h>
#include <linux/slab.h>
#include <linux/random.h>

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("rhashtable demo with walker");

struct rht_entry {
    u32                key;
    u64                counter;
    char               name[32];
    struct rhash_head  rhash;
    struct rcu_head    rcu;
};

static struct rhashtable rht_demo;

/* 파라미터 설정: 자동 축소 활성화, 초기 힌트 128 */
static const struct rhashtable_params rht_demo_params = {
    .head_offset         = offsetof(struct rht_entry, rhash),
    .key_offset          = offsetof(struct rht_entry, key),
    .key_len             = sizeof(u32),
    .automatic_shrinking = true,
    .nelem_hint          = 128,
    .min_size            = 64,
};

/* ─── 삽입 ─── */
static int rht_demo_insert(u32 key, const char *name)
{
    struct rht_entry *entry;
    int ret;

    entry = kzalloc(sizeof(*entry), GFP_KERNEL);
    if (!entry)
        return -ENOMEM;

    entry->key = key;
    entry->counter = 0;
    strscpy(entry->name, name, sizeof(entry->name));

    /* 원자적 삽입: 중복 키 시 -EEXIST 반환 */
    ret = rhashtable_lookup_insert_fast(&rht_demo,
                                        &entry->rhash,
                                        rht_demo_params);
    if (ret) {
        kfree(entry);
        if (ret == -EEXIST)
            pr_info("rht_demo: key %u already exists\n", key);
        return ret;
    }

    pr_info("rht_demo: inserted key=%u name=%s\n", key, name);
    return 0;
}

/* ─── 검색 (RCU 보호) ─── */
static struct rht_entry *rht_demo_lookup(u32 key)
{
    /* rcu_read_lock()은 호출자가 보유해야 합니다 */
    return rhashtable_lookup_fast(&rht_demo, &key,
                                   rht_demo_params);
}

/* ─── 삭제 ─── */
static int rht_demo_delete(u32 key)
{
    struct rht_entry *entry;
    int ret;

    rcu_read_lock();
    entry = rht_demo_lookup(key);
    if (!entry) {
        rcu_read_unlock();
        return -ENOENT;
    }
    rcu_read_unlock();

    ret = rhashtable_remove_fast(&rht_demo,
                                  &entry->rhash,
                                  rht_demo_params);
    if (!ret)
        kfree_rcu(entry, rcu);

    return ret;
}

/* ─── Walker를 통한 안전한 전체 순회 ─── */
static void rht_demo_walk_all(void)
{
    struct rhashtable_iter iter;
    struct rht_entry *entry;
    unsigned int count = 0;

    /* walker 등록: 리사이즈 알림을 받을 수 있도록 등록 */
    rhashtable_walk_enter(&rht_demo, &iter);
    rhashtable_walk_start(&iter);

    while ((entry = rhashtable_walk_next(&iter)) != NULL) {
        /* 리사이즈 중이면 -EAGAIN이 ERR_PTR로 반환됨 */
        if (IS_ERR(entry)) {
            if (PTR_ERR(entry) == -EAGAIN)
                continue;  /* 리사이즈 중 → 재시도 */
            break;         /* 다른 에러 → 중단 */
        }

        pr_info("rht_demo: walk key=%u name=%s counter=%llu\n",
                entry->key, entry->name, entry->counter);
        count++;
    }

    rhashtable_walk_stop(&iter);
    rhashtable_walk_exit(&iter);

    pr_info("rht_demo: walked %u entries\n", count);
}

/* ─── 원자적 교체 예제 ─── */
static int rht_demo_update(u32 key, const char *new_name)
{
    struct rht_entry *old_entry, *new_entry;
    int ret;

    rcu_read_lock();
    old_entry = rht_demo_lookup(key);
    if (!old_entry) {
        rcu_read_unlock();
        return -ENOENT;
    }
    rcu_read_unlock();

    new_entry = kzalloc(sizeof(*new_entry), GFP_KERNEL);
    if (!new_entry)
        return -ENOMEM;

    /* 키와 카운터는 유지, 이름만 갱신 */
    new_entry->key = old_entry->key;
    new_entry->counter = old_entry->counter + 1;
    strscpy(new_entry->name, new_name, sizeof(new_entry->name));

    /* 원자적 교체: 읽기 측은 교체 전후 중 하나만 관측 */
    ret = rhashtable_replace_fast(&rht_demo,
                                   &old_entry->rhash,
                                   &new_entry->rhash,
                                   rht_demo_params);
    if (ret) {
        kfree(new_entry);
        return ret;
    }

    kfree_rcu(old_entry, rcu);
    pr_info("rht_demo: updated key=%u → name=%s counter=%llu\n",
            key, new_name, new_entry->counter);
    return 0;
}

/* ─── 모듈 초기화 ─── */
static int __init rht_demo_init(void)
{
    int ret, i;

    ret = rhashtable_init(&rht_demo, &rht_demo_params);
    if (ret)
        return ret;

    /* 테스트 데이터 대량 삽입 → 자동 리사이즈 트리거 */
    for (i = 0; i < 256; i++) {
        char name[32];
        snprintf(name, sizeof(name), "entry_%d", i);
        rht_demo_insert(i, name);
    }

    /* walker로 전체 순회 */
    rht_demo_walk_all();

    /* 교체 테스트 */
    rht_demo_update(42, "updated_42");

    pr_info("rht_demo: module loaded, %d elements\n",
            atomic_read(&rht_demo.nelems));
    return 0;
}

/* ─── 모듈 정리: rhashtable_free_and_destroy 사용 ─── */
static void rht_free_fn(void *ptr, void *arg)
{
    struct rht_entry *entry = ptr;
    kfree(entry);
}

static void __exit rht_demo_exit(void)
{
    /* 콜백으로 모든 요소 해제 후 테이블 파괴
     * rhashtable_destroy()와 달리 요소가 남아있어도 안전 */
    rhashtable_free_and_destroy(&rht_demo, rht_free_fn, NULL);
    pr_info("rht_demo: module unloaded\n");
}

module_init(rht_demo_init);
module_exit(rht_demo_exit);

예제 3: 복합 키 + siphash 커스텀 해시

네트워크 플로우 추적처럼 복합 키(소스 IP, 목적지 IP, 프로토콜)를 사용하고, 보안을 위해 siphash를 적용하는 rhashtable 설정입니다. 이는 conntrack의 실제 패턴을 단순화한 것입니다.

/* 실습 예제: 복합 키 + siphash rhashtable */
#include <linux/rhashtable.h>
#include <linux/siphash.h>
#include <linux/random.h>

/* 복합 키: 네트워크 3-tuple */
struct flow_key {
    __be32  src_ip;
    __be32  dst_ip;
    u8      protocol;
    u8      __pad[3];  /* 4바이트 정렬 */
} __packed;

struct flow_entry {
    struct flow_key    key;
    u64                packets;
    u64                bytes;
    unsigned long      last_seen;   /* jiffies */
    struct rhash_head  rhash;
    struct rcu_head    rcu;
};

/* 비밀 키: 부팅 시 한 번만 랜덤 생성 */
static siphash_key_t flow_hash_secret;

/* 커스텀 해시 함수: siphash로 복합 키 해싱 */
static u32 flow_key_hashfn(const void *data,
                            u32 len, u32 seed)
{
    const struct flow_key *key = data;

    /* siphash: 비밀 키 기반 → HashDoS 방어 */
    return (u32)siphash(key, sizeof(*key),
                         &flow_hash_secret);
}

/* 객체에서 직접 해시 계산 (obj_hashfn) */
static u32 flow_obj_hashfn(const void *data,
                            u32 len, u32 seed)
{
    const struct flow_entry *f = data;
    return flow_key_hashfn(&f->key, sizeof(f->key), seed);
}

/* 커스텀 비교 함수: 복합 키 전체를 memcmp */
static int flow_obj_cmpfn(struct rhashtable_compare_arg *arg,
                           const void *obj)
{
    const struct flow_key *needle = arg->key;
    const struct flow_entry *f = obj;
    return memcmp(&f->key, needle, sizeof(*needle));
}

static const struct rhashtable_params flow_params = {
    .head_offset  = offsetof(struct flow_entry, rhash),
    .key_offset   = offsetof(struct flow_entry, key),
    .key_len      = sizeof(struct flow_key),
    .hashfn       = flow_key_hashfn,
    .obj_hashfn   = flow_obj_hashfn,
    .obj_cmpfn    = flow_obj_cmpfn,
    .automatic_shrinking = true,
    .nelem_hint   = 4096,
    .min_size     = 256,
};

/* ─── 사용 예: 패킷 수신 경로에서 플로우 카운터 갱신 ─── */
static void flow_account_packet(
    struct rhashtable *ht,
    __be32 src, __be32 dst, u8 proto,
    unsigned int pkt_len)
{
    struct flow_key lookup_key = {
        .src_ip   = src,
        .dst_ip   = dst,
        .protocol = proto,
    };
    struct flow_entry *entry;

    rcu_read_lock();
    entry = rhashtable_lookup_fast(ht, &lookup_key, flow_params);
    if (entry) {
        /* 간단한 카운터 갱신 (정밀 동기화가 필요하면
         * atomic_t 또는 per-CPU 카운터 사용) */
        WRITE_ONCE(entry->packets,
                   READ_ONCE(entry->packets) + 1);
        WRITE_ONCE(entry->bytes,
                   READ_ONCE(entry->bytes) + pkt_len);
        WRITE_ONCE(entry->last_seen, jiffies);
    }
    rcu_read_unlock();

    /* entry가 없으면 새 플로우 생성 (별도 함수) */
}

/* 초기화 시 비밀 키 생성 */
static int __init flow_init(void)
{
    get_random_bytes(&flow_hash_secret,
                     sizeof(flow_hash_secret));
    return rhashtable_init(&flow_ht, &flow_params);
}

예제 4: 해시 테이블 버킷 분포 분석 도구

운영 중인 해시 테이블의 버킷별 체인 길이를 수집하고 통계를 출력하는 유틸리티 함수입니다. 성능 문제 진단 시 편향 여부를 빠르게 확인할 수 있습니다.

/* 실습 예제: 해시 테이블 버킷 분포 분석 함수 */

struct ht_stats {
    unsigned int total_entries;
    unsigned int used_buckets;
    unsigned int empty_buckets;
    unsigned int max_chain;
    unsigned int total_buckets;
    u64          chain_sum_sq;  /* 분산 계산용 */
};

/* DEFINE_HASHTABLE 기반 테이블의 버킷 분포 분석
 * 호출 시 적절한 동기화(RCU 또는 lock) 필요 */
#define analyze_hashtable(ht, stats) do { \
    unsigned int __bkt; \
    memset(&(stats), 0, sizeof(stats)); \
    (stats).total_buckets = HASH_SIZE(ht); \
    for (__bkt = 0; __bkt < HASH_SIZE(ht); __bkt++) { \
        struct hlist_node *__pos; \
        unsigned int __chain_len = 0; \
        hlist_for_each(__pos, &(ht)[__bkt]) \
            __chain_len++; \
        (stats).total_entries += __chain_len; \
        if (__chain_len > 0) \
            (stats).used_buckets++; \
        else \
            (stats).empty_buckets++; \
        if (__chain_len > (stats).max_chain) \
            (stats).max_chain = __chain_len; \
        (stats).chain_sum_sq += (u64)__chain_len * __chain_len; \
    } \
} while (0)

/* 분석 결과 출력 */
static void print_ht_stats(const char *name,
                           const struct ht_stats *s)
{
    unsigned int avg_x100 = s->total_buckets ?
        (s->total_entries * 100) / s->total_buckets : 0;
    u64 var_x100 = s->total_buckets ?
        (s->chain_sum_sq * 100) / s->total_buckets -
        (u64)avg_x100 * avg_x100 / 10000 : 0;

    pr_info("%s stats:\n", name);
    pr_info("  total entries  : %u\n", s->total_entries);
    pr_info("  total buckets  : %u\n", s->total_buckets);
    pr_info("  used buckets   : %u (%.1u%%)\n",
            s->used_buckets,
            s->total_buckets ?
            s->used_buckets * 100 / s->total_buckets : 0);
    pr_info("  load factor    : %u.%02u\n",
            avg_x100 / 100, avg_x100 % 100);
    pr_info("  max chain      : %u\n", s->max_chain);
    pr_info("  chain variance : %llu.%02llu\n",
            var_x100 / 100, var_x100 % 100);

    /* 경고 조건 */
    if (s->max_chain > 8)
        pr_warn("  ⚠ max chain > 8: consider resizing or"
                " improving hash function\n");
    if (avg_x100 > 200)
        pr_warn("  ⚠ load factor > 2.0: high collision"
                " probability\n");
}

/* 사용 예 */
static void check_my_table(void)
{
    struct ht_stats stats;

    rcu_read_lock();
    analyze_hashtable(my_ht, stats);
    rcu_read_unlock();

    print_ht_stats("my_ht", &stats);
}

구현 패턴 비교 요약

jhash() 해시 함수 내부 구현 분석

jhash()는 Bob Jenkins가 설계한 해시 함수로, 커널 네트워킹 서브시스템에서 가장 널리 사용됩니다. include/linux/jhash.h에 정의되어 있으며, 가변 길이 데이터를 32비트 해시값으로 변환합니다. 이 섹션에서는 내부 mixing 과정을 한 줄씩 분석합니다.

__jhash_mix() 매크로 내부 구현

jhash()의 핵심은 세 개의 32비트 변수 a, b, c를 반복적으로 섞는 mixing 함수입니다. 입력 데이터의 비트 패턴을 완전히 분산시키는 것이 목표입니다.

/* include/linux/jhash.h — mixing 매크로 */

/* __jhash_mix: 3개 변수를 비트 단위로 완전히 혼합
 *
 * 설계 목표:
 * - a, b, c 각각의 모든 비트가 결과의 모든 비트에 영향
 * - 역함수 계산이 실질적으로 불가능 (one-way mixing)
 * - 연산 수를 최소화하면서 완전 혼합(full avalanche) 달성
 */
#define __jhash_mix(a, b, c) \
{ \
    a -= c;  a ^= rol32(c, 4);  c += b; \
    b -= a;  b ^= rol32(a, 6);  a += c; \
    c -= b;  c ^= rol32(b, 8);  b += a; \
    a -= c;  a ^= rol32(c, 16); c += b; \
    b -= a;  b ^= rol32(a, 19); a += c; \
    c -= b;  c ^= rol32(b, 4);  b += a; \
}

/* rol32(x, k): x를 왼쪽으로 k비트 순환 시프트
 * 예: rol32(0x80000001, 4) = 0x00000018
 *
 * 6라운드 구조:
 *   라운드 1: a -= c; a ^= rol32(c, 4);  c += b;
 *   라운드 2: b -= a; b ^= rol32(a, 6);  a += c;
 *   라운드 3: c -= b; c ^= rol32(b, 8);  b += a;
 *   라운드 4: a -= c; a ^= rol32(c, 16); c += b;
 *   라운드 5: b -= a; b ^= rol32(a, 19); a += c;
 *   라운드 6: c -= b; c ^= rol32(b, 4);  b += a;
 *
 * 각 라운드에서 세 가지 연산이 수행됩니다:
 * 1. 빼기(subtract) → 비트 차이 확산
 * 2. XOR + 순환 시프트 → 비트 위치 재배치
 * 3. 더하기(add) → 캐리 전파로 추가 혼합
 *
 * 시프트 상수 {4, 6, 8, 16, 19, 4}는 Jenkins가
 * 완전 분산(full avalanche)을 달성하도록 탐색한 값입니다.
 */

__jhash_final() 매크로 내부 구현

__jhash_final()은 마지막 입력 블록을 처리한 후 호출되는 최종 mixing입니다. __jhash_mix()보다 강한 혼합을 수행하여 마지막 바이트까지 결과에 반영합니다.

/* include/linux/jhash.h — 최종 mixing */

#define __jhash_final(a, b, c) \
{ \
    c ^= b; c -= rol32(b, 14); \
    a ^= c; a -= rol32(c, 11); \
    b ^= a; b -= rol32(a, 25); \
    c ^= b; c -= rol32(b, 16); \
    a ^= c; a -= rol32(c, 4);  \
    b ^= a; b -= rol32(a, 14); \
    c ^= b; c -= rol32(b, 24); \
}

/* __jhash_mix와의 차이:
 * - 더하기(add) 대신 XOR+빼기만 사용
 * - 시프트 상수가 다름: {14, 11, 25, 16, 4, 14, 24}
 * - 더 강한 확산 → 짧은 입력에서도 좋은 분포
 *
 * __jhash_mix는 중간 블록 처리용(속도 우선),
 * __jhash_final은 마지막 블록용(품질 우선)으로
 * 역할이 분리되어 있습니다.
 */

jhash() 전체 흐름

/* include/linux/jhash.h — jhash() 전체 구현 분석 */

static inline u32 jhash(const void *key, u32 length, u32 initval)
{
    u32 a, b, c;
    const u8 *k = key;

    /* ① 초기값 설정: 매직 상수 + 입력 길이 + 시드
     *    JHASH_INITVAL = 0xdeadbeef
     *    a = b = c = 0xdeadbeef + length + initval
     *    세 변수 모두 같은 초기값 → mixing이 차이를 만듦 */
    a = b = c = JHASH_INITVAL + length + initval;

    /* ② 12바이트(3 word) 단위로 입력 처리
     *    각 블록을 a, b, c에 더한 후 __jhash_mix()로 혼합 */
    while (length > 12) {
        a += get_unaligned_le32(k);
        b += get_unaligned_le32(k + 4);
        c += get_unaligned_le32(k + 8);
        __jhash_mix(a, b, c);
        length -= 12;
        k += 12;
    }

    /* ③ 남은 바이트 처리 (0~12바이트)
     *    switch-case로 남은 길이에 따라 바이트 단위 로딩 */
    switch (length) {
    case 12: c += (u32)k[11] << 24;  /* fall through */
    case 11: c += (u32)k[10] << 16;  /* fall through */
    case 10: c += (u32)k[9] << 8;   /* fall through */
    case 9:  c += k[8];              /* fall through */
    case 8:  b += (u32)k[7] << 24;   /* fall through */
    case 7:  b += (u32)k[6] << 16;   /* fall through */
    case 6:  b += (u32)k[5] << 8;    /* fall through */
    case 5:  b += k[4];               /* fall through */
    case 4:  a += (u32)k[3] << 24;   /* fall through */
    case 3:  a += (u32)k[2] << 16;   /* fall through */
    case 2:  a += (u32)k[1] << 8;    /* fall through */
    case 1:  a += k[0];
             /* ④ 최종 mixing: 마지막 블록은 더 강한 혼합 */
             __jhash_final(a, b, c);
    case 0:  /* 빈 입력: mixing 없이 초기값 반환 */
             break;
    }

    /* ⑤ c가 최종 해시값: 32비트 해시 반환 */
    return c;
}

jhash2() — 정렬된 워드 배열 해싱

jhash2()는 u32 배열을 직접 입력으로 받아 바이트 단위 로딩 오버헤드를 제거합니다. conntrack 튜플 해싱 등 4바이트 정렬이 보장된 데이터에서 jhash()보다 빠릅니다.

/* include/linux/jhash.h — jhash2() 구현 */

static inline u32 jhash2(const u32 *k, u32 length, u32 initval)
{
    u32 a, b, c;

    /* 초기화: length는 u32 단위 개수 */
    a = b = c = JHASH_INITVAL + (length << 2) + initval;

    /* 3-word 단위 처리 (12바이트가 아닌 3개 u32) */
    while (length > 3) {
        a += k[0];
        b += k[1];
        c += k[2];
        __jhash_mix(a, b, c);
        length -= 3;
        k += 3;
    }

    /* 남은 1~3개 워드 처리 */
    switch (length) {
    case 3: c += k[2];  /* fall through */
    case 2: b += k[1];  /* fall through */
    case 1: a += k[0];
            __jhash_final(a, b, c);
    case 0: break;
    }

    return c;
}

/* conntrack에서의 실제 호출 예:
 *
 * struct nf_conntrack_tuple tuple;
 * u32 n = (sizeof(tuple.src) + sizeof(tuple.dst.u3)) / sizeof(u32);
 *
 * hash = jhash2((u32 *)&tuple, n, seed);
 * bucket = reciprocal_scale(hash, htable_size);
 *
 * jhash2가 jhash보다 빠른 이유:
 * - get_unaligned_le32() 호출 불필요 (이미 u32 정렬)
 * - 컴파일러가 배열 접근을 더 효율적으로 최적화
 * - conntrack 같은 hot path에서 유의미한 차이
 */

hash_32() / hash_64() 내부 동작 상세 분석

hash_32()와 hash_64()는 정수 키 해싱의 기본 함수입니다. Golden Ratio 해시 섹션에서 기본 구현을 소개했으나, 여기서는 비트 레벨에서 어떻게 분산이 이루어지는지 단계별로 추적합니다.

hash_32() 비트 레벨 추적

hash_32(val, bits) 비트 연산 단계별 추적

예시: hash_32(42, 10) — 42를 1024-버킷 해시 테이블에 매핑

1. 입력: val = 42 = 0x0000002A, bits = 10
2. 곱셈: val * GOLDEN_RATIO_32 = 0x0000002A * 0x61C88647 = 68902324134 = 0x000000100E1D5986 (64비트 중간 결과) → u32 절단: 0x0E1D5986
3. 상위 비트 추출: 0x0E1D5986 >> (32 - 10) = 0x0E1D5986 >> 22 = 0x38 = 56
4. 결과: 키 42는 버킷 56에 매핑됩니다.

비교: 단순 모듈로 42 % 1024 = 42이면 연속 키가 인접 버킷에 몰리지만, hash_32()는 42→56, 43→695, 44→310으로 완전히 분산됩니다.

hash_64()도 동일한 원리이며, 더 큰 상수를 사용합니다.

• hash_64(val, bits): result = (u32)(val * GOLDEN_RATIO_64) >> (64 - bits)
• GOLDEN_RATIO_64 = 0x61C8864680B583EB
• 128비트 곱셈의 상위 64비트가 자연 오버플로로 남고, 거기서 상위 bits 비트를 추출합니다.
• 64비트 시스템에서 hash_long()은 hash_64()로 확장되므로, 포인터 키(8바이트)도 올바르게 처리됩니다.

hash_min() — 키 크기별 자동 디스패치

/* include/linux/hashtable.h — hash_min() 내부 */

#define hash_min(val, bits) \
    (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))

/* 왜 hash_min이 필요한가?
 *
 * hash_add(ht, &obj->node, key)에서 key의 타입이
 * u32일 수도, u64일 수도, unsigned long일 수도 있습니다.
 *
 * sizeof(val) <= 4:
 *   → hash_32() 사용 (32비트 곱셈, 더 빠름)
 *   → u8, u16, u32, int, short 등
 *
 * sizeof(val) > 4:
 *   → hash_long() → hash_64() (64비트 곱셈)
 *   → u64, unsigned long (64비트 시스템), 포인터
 *
 * 컴파일 타임에 sizeof()로 분기가 결정되므로
 * 런타임 오버헤드가 없습니다.
 *
 * 주의: 포인터를 키로 사용할 때는 hash_ptr()을 쓰거나
 * hash_long((unsigned long)ptr, bits)을 사용하세요.
 * hash_min은 정수 타입 전용입니다.
 */

RCU 보호 해시 테이블 연산 내부 구현

RCU 해시 테이블 섹션에서 API 사용법을 다루었습니다. 이 섹션에서는 hash_add_rcu(), hash_del_rcu(), hash_for_each_possible_rcu()가 내부적으로 어떤 메모리 배리어와 포인터 조작을 수행하는지 소스 레벨에서 분석합니다.

hash_add_rcu() → hlist_add_head_rcu() 내부

/* hash_add_rcu()의 전개 과정:
 *
 * hash_add_rcu(ht, &obj->hash_node, key)
 * → hlist_add_head_rcu(&obj->hash_node,
 *                       &ht[hash_min(key, HASH_BITS(ht))])
 */

/* include/linux/rculist.h — hlist_add_head_rcu() */
static inline void hlist_add_head_rcu(struct hlist_node *n,
                                       struct hlist_head *h)
{
    struct hlist_node *first = h->first;

    /* ① 새 노드의 next를 현재 첫 번째 노드로 설정 */
    n->next = first;

    /* ② WRITE_ONCE: 새 노드의 pprev를 헤드의 first 필드 주소로 설정
     *    tearing 방지를 위해 WRITE_ONCE 사용 */
    WRITE_ONCE(n->pprev, &h->first);

    /* ③ rcu_assign_pointer: 쓰기 메모리 배리어 포함
     *    이 배리어가 ①②의 초기화가 완료된 후에
     *    새 노드가 공개되도록 보장합니다.
     *    읽기 측(rcu_dereference)은 이 배리어와 쌍을 이룹니다. */
    rcu_assign_pointer(h->first, n);

    /* ④ 기존 첫 노드가 있으면 그 pprev를 갱신 */
    if (first)
        WRITE_ONCE(first->pprev, &n->next);
}

/* 메모리 순서 보장 정리:
 *
 * 쓰기 측 (hash_add_rcu):
 *   n->next = first;           ← 일반 store
 *   n->pprev = &h->first;      ← WRITE_ONCE
 *   smp_store_release(&h->first, n);  ← rcu_assign_pointer 내부
 *   first->pprev = &n->next;   ← WRITE_ONCE
 *
 * 읽기 측 (hash_for_each_possible_rcu):
 *   node = rcu_dereference(h->first);  ← smp_load_acquire
 *   // node의 모든 필드가 초기화된 상태로 관측됨
 *
 * rcu_assign_pointer()가 핵심:
 *   이것이 없으면 읽기 CPU가 h->first = n을 보면서
 *   n->next가 아직 초기화되지 않은 상태를 관측할 수 있습니다.
 */

hash_del_rcu() → hlist_del_init_rcu() 내부

/* include/linux/rculist.h — hlist_del_init_rcu() */
static inline void hlist_del_init_rcu(struct hlist_node *n)
{
    if (!hlist_unhashed(n)) {
        /* ① __hlist_del: 체인에서 노드를 제거
         *    *pprev = next;  // 이전의 next → 다음 노드
         *    if (next) next->pprev = pprev;
         */
        __hlist_del(n);

        /* ② pprev만 NULL로 설정 (unhashed 상태 표시)
         *    핵심: n->next는 변경하지 않음!
         *
         *    이유: 다른 CPU가 RCU read lock 하에
         *    이 노드를 방금 읽었을 수 있습니다.
         *    그 CPU는 n->next를 통해 다음 노드로
         *    이동해야 하므로 next를 유지합니다.
         *
         *    hlist_del()은 next를 POISON으로 설정하지만,
         *    hlist_del_init_rcu()는 next를 건드리지 않습니다. */
        WRITE_ONCE(n->pprev, NULL);
    }
}

/* hash_del()과 hash_del_rcu()의 결정적 차이:
 *
 * hash_del():
 *   → hlist_del_init()
 *   → n->next = NULL, n->pprev = NULL
 *   → 동시 읽기 안전하지 않음
 *
 * hash_del_rcu():
 *   → hlist_del_init_rcu()
 *   → n->next 유지, n->pprev = NULL
 *   → 동시 읽기 측이 next를 통해 순회 가능
 *
 * 삭제 후 반드시 grace period 대기:
 *   kfree_rcu(obj, rcu);       // 비동기 해제
 *   또는
 *   synchronize_rcu();         // 동기 대기
 *   kfree(obj);
 */

hash_for_each_possible_rcu() 내부 순회 메커니즘

/* hash_for_each_possible_rcu()의 전개:
 *
 * hash_for_each_possible_rcu(ht, obj, member, key)
 * → hlist_for_each_entry_rcu(obj,
 *       &ht[hash_min(key, HASH_BITS(ht))], member)
 */

/* include/linux/rculist.h — hlist_for_each_entry_rcu() */
#define hlist_for_each_entry_rcu(pos, head, member) \
    for (pos = hlist_entry_safe( \
             rcu_dereference_raw(hlist_first_rcu(head)), \
             typeof(*(pos)), member); \
         pos; \
         pos = hlist_entry_safe( \
             rcu_dereference_raw(hlist_next_rcu( \
                 &(pos)->member)), \
             typeof(*(pos)), member))

/* 핵심 RCU 헬퍼:
 *
 * hlist_first_rcu(head):
 *   rcu_dereference_check(head->first, ...)
 *   → 읽기 배리어 + RCU read lock 검증
 *
 * hlist_next_rcu(&node):
 *   rcu_dereference_check(node->next, ...)
 *   → 다음 포인터도 RCU-safe로 읽기
 *
 * 일반 hlist_for_each_entry()와의 차이:
 *   일반: head->first, node->next를 직접 읽음
 *   RCU: rcu_dereference()로 읽기 배리어 삽입
 *
 * 이 배리어가 없으면 CPU의 투기적 실행(speculative execution)이
 * 포인터를 먼저 읽고, 가리키는 데이터의 초기화를 나중에 관측하는
 * 순서 역전이 발생할 수 있습니다.
 */

hlist 버킷 체인 상세 구조 다이어그램

hlist_head와 hlist_node의 포인터 연결 관계를 상세하게 시각화합니다. 특히 pprev 이중 포인터가 어떻게 이전 노드의 next 필드(또는 헤드의 first 필드)를 가리키는지 보여줍니다.

해시 충돌 해결 체인 다이어그램

서로 다른 키가 같은 버킷에 매핑될 때 체이닝으로 충돌을 해결하는 과정을 시각화합니다. hash_for_each_possible()이 버킷 체인을 순회하며 키를 비교하는 흐름을 보여줍니다.

/* kernel/pid.c — PID 해시 테이블 정의 */

/* 전역 PID 해시 테이블: pid_hash[]
 * 부팅 시 pidhash_init()에서 동적 할당
 * 크기: 시스템 메모리에 비례 (일반적으로 4096 버킷) */
static struct hlist_head *pid_hash;
static unsigned int pidhash_shift;
/* pidhash_shift = log2(bucket_count)
 * 예: 4096 버킷이면 pidhash_shift = 12 */

/* struct upid: namespace별 PID 번호
 * 하나의 프로세스가 여러 PID namespace에 속할 수 있으므로
 * pid_namespace별로 별도의 upid를 가집니다 */
struct upid {
    int                  nr;        /* namespace 내 PID 번호 */
    struct pid_namespace *ns;       /* 소속 namespace */
    struct hlist_node    pid_chain; /* pid_hash[]에 연결 */
};

/* struct pid: 프로세스 식별자 (namespace 계층 포함)
 * level: 이 PID가 존재하는 최하위 namespace 깊이
 * numbers[]: level+1개의 upid (각 namespace별 PID 번호) */
struct pid {
    refcount_t           count;
    unsigned int         level;
    spinlock_t           lock;
    struct hlist_head    tasks[PIDTYPE_MAX];
    struct hlist_head    inodes;
    wait_queue_head_t    wait_pidfd;
    struct rcu_head      rcu;
    struct upid          numbers[];  /* flexible array: namespace별 PID */
};

/* kernel/pid.c — PID를 해시 테이블 버킷에 매핑 */

static struct hlist_head *pid_hashfn(struct pid_namespace *ns,
                                       int nr)
{
    /* namespace 포인터와 PID 번호를 결합하여 해시
     * pid_hashfn()은 두 값을 결합하여 버킷 인덱스 생성:
     *
     * 1. nr (PID 번호) → 정수 키
     * 2. ns (namespace 포인터) → 주소를 정수로 변환
     *
     * 같은 PID 번호라도 다른 namespace면 다른 버킷에 매핑 */
    return &pid_hash[hash_long((unsigned long)nr +
                                (unsigned long)ns,
                                pidhash_shift)];
}

/* kernel/pid.c — namespace 내에서 PID 번호로 struct pid 검색 */

struct pid *find_pid_ns(int nr, struct pid_namespace *ns)
{
    struct upid *pnr;

    /* ① pid_hashfn()으로 해시 버킷 결정 */
    /* ② 해당 버킷의 hlist 체인을 순회 */
    hlist_for_each_entry_rcu(pnr,
            pid_hashfn(ns, nr), pid_chain) {
        /* ③ PID 번호와 namespace 모두 일치하는지 확인
         *    같은 버킷에 다른 namespace의 같은 PID가
         *    있을 수 있으므로 양쪽 모두 비교해야 합니다 */
        if (pnr->nr == nr && pnr->ns == ns)
            return container_of(pnr, struct pid,
                                numbers[ns->level]);
    }

    return NULL;
}

/* find_pid_ns()에서 find_task_by_vpid()까지의 호출 체인:
 *
 * find_task_by_vpid(pid_t vnr)
 *   → find_task_by_pid_ns(vnr, task_active_pid_ns(current))
 *     → find_pid_ns(nr, ns)      ← 해시 테이블 룩업
 *       → pid_task(pid, PIDTYPE_PID)  ← PID → task_struct
 *
 * 전체 흐름:
 *   PID 번호(int) → 해시 → 버킷 → 체인 순회 →
 *   struct upid → container_of → struct pid →
 *   tasks[PIDTYPE_PID] hlist → struct task_struct
 *
 * 시간 복잡도: O(1) 평균 (해시 + 짧은 체인 순회)
 * 동시성: rcu_read_lock() 하에 lock-free 검색
 */

/* net/netfilter/nf_conntrack_core.c — 삽입 경로 핵심 흐름 */

/* ① 새 연결의 해시값 계산 (원본 + 응답 방향 각각) */
static void __nf_conntrack_hash_insert(
    struct nf_conn *ct,
    unsigned int hash,
    unsigned int reply_hash)
{
    struct nf_conntrack_tuple_hash *h;

    /* 원본 방향(ORIGINAL) 튜플을 해시 테이블에 삽입 */
    h = &ct->tuplehash[IP_CT_DIR_ORIGINAL];
    hlist_nulls_add_head_rcu(&h->hnnode,
            &nf_conntrack_hash[hash]);

    /* 응답 방향(REPLY) 튜플도 해시 테이블에 삽입
     * → 양쪽 방향 패킷 모두에서 O(1) 룩업 가능 */
    h = &ct->tuplehash[IP_CT_DIR_REPLY];
    hlist_nulls_add_head_rcu(&h->hnnode,
            &nf_conntrack_hash[reply_hash]);
}

/* ② 해시값 계산 함수 */
static u32 hash_conntrack_raw(
    const struct nf_conntrack_tuple *tuple,
    unsigned int zoneid,
    const struct net *net)
{
    u32 seed;

    /* 랜덤 시드: 부팅마다 다르게 생성 → HashDoS 방어 */
    get_random_once(&nf_conntrack_hash_rnd,
                    sizeof(nf_conntrack_hash_rnd));
    seed = nf_conntrack_hash_rnd ^ zoneid;

    /* jhash2로 tuple의 소스+목적지 주소를 32비트 해싱
     * tuple을 u32 배열로 캐스트하여 word 단위 처리 */
    unsigned int n;
    n = (sizeof(tuple->src) + sizeof(tuple->dst.u3))
        / sizeof(u32);

    return jhash2((u32 *)tuple, n,
                  seed ^
                  (u32)(unsigned long)net ^
                  ((__force __u16)tuple->dst.u.all << 16) |
                  tuple->dst.protonum);
}

/* ③ 버킷 인덱스 = reciprocal_scale(hash, htable_size)
 *
 * reciprocal_scale()을 사용하는 이유:
 *   conntrack은 버킷 수가 2의 거듭제곱이 아닐 수 있습니다.
 *   (nf_conntrack_buckets 파라미터로 임의 값 설정 가능)
 *   일반 & (size-1) 마스킹은 2의 거듭제곱에서만 동작하므로,
 *   reciprocal_scale()로 [0, size) 범위에 균등 매핑합니다.
 *
 *   reciprocal_scale(val, ep_ro) = (val * ep_ro) >> 32
 *   이는 val / 2^32 * ep_ro와 동일하며, 나눗셈 없이 구현됩니다.
 */

/* 실습 예제: conntrack 패턴 연결 추적 모듈 */
#include <linux/module.h>
#include <linux/list_nulls.h>
#include <linux/jhash.h>
#include <linux/slab.h>
#include <linux/rcupdate.h>
#include <linux/spinlock.h>
#include <linux/random.h>

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("conntrack-style hash table demo");

#define CT_HASH_BITS   10
#define CT_HASH_SIZE   (1 << CT_HASH_BITS)

/* 5-tuple 키 */
struct ct_tuple {
    __be32  src_ip;
    __be32  dst_ip;
    __be16  src_port;
    __be16  dst_port;
    u8      protocol;
    u8      __pad[3];
};

/* 연결 엔트리 */
struct ct_entry {
    struct ct_tuple         tuple;
    u64                     packets;
    u64                     bytes;
    unsigned long           timeout;   /* jiffies 기반 */
    struct hlist_nulls_node hnode;     /* nulls 마커 체인 */
    struct rcu_head         rcu;
};

/* 해시 테이블: hlist_nulls_head 배열 */
static struct hlist_nulls_head ct_hash[CT_HASH_SIZE];
static spinlock_t            ct_locks[CT_HASH_SIZE];
static u32                   ct_hash_rnd;

/* 해시 함수: jhash2로 tuple 해싱 */
static u32 ct_hash_tuple(const struct ct_tuple *t)
{
    return jhash2((u32 *)t,
                  sizeof(*t) / sizeof(u32),
                  ct_hash_rnd) & (CT_HASH_SIZE - 1);
}

/* 검색: RCU + nulls 마커 검증 */
static struct ct_entry *ct_lookup(
    const struct ct_tuple *t)
{
    u32 hash = ct_hash_tuple(t);
    struct ct_entry *entry;
    struct hlist_nulls_node *n;

begin:
    /* rcu_read_lock()은 호출자가 보유 */
    hlist_nulls_for_each_entry_rcu(entry, n,
            &ct_hash[hash], hnode) {
        if (memcmp(&entry->tuple, t, sizeof(*t)) == 0)
            return entry;
    }

    /* nulls 마커 검증: 체인 끝의 nulls 값이
     * 현재 버킷 인덱스와 일치하는지 확인.
     * 불일치 → 리사이즈가 발생했으므로 재시도 */
    if (get_nulls_value(n) != hash)
        goto begin;

    return NULL;
}

/* 삽입: per-bucket lock + RCU publish */
static int ct_insert(struct ct_entry *entry)
{
    u32 hash = ct_hash_tuple(&entry->tuple);

    /* per-bucket lock: 같은 버킷 내 쓰기만 직렬화
     * 다른 버킷의 읽기/쓰기와는 병렬 실행 */
    spin_lock_bh(&ct_locks[hash]);

    /* 중복 검사 (lock 보유 상태이므로 일반 순회 가능) */
    struct ct_entry *existing;
    struct hlist_nulls_node *n;
    hlist_nulls_for_each_entry(existing, n,
            &ct_hash[hash], hnode) {
        if (memcmp(&existing->tuple,
                   &entry->tuple,
                   sizeof(entry->tuple)) == 0) {
            spin_unlock_bh(&ct_locks[hash]);
            return -EEXIST;
        }
    }

    /* RCU-safe 삽입: 읽기 측이 즉시 관측 가능 */
    hlist_nulls_add_head_rcu(&entry->hnode,
                              &ct_hash[hash]);

    spin_unlock_bh(&ct_locks[hash]);
    return 0;
}

/* 삭제: per-bucket lock + RCU grace period */
static void ct_delete(struct ct_entry *entry)
{
    u32 hash = ct_hash_tuple(&entry->tuple);

    spin_lock_bh(&ct_locks[hash]);
    hlist_nulls_del_rcu(&entry->hnode);
    spin_unlock_bh(&ct_locks[hash]);

    /* grace period 후 메모리 해제 */
    kfree_rcu(entry, rcu);
}

/* 초기화: nulls 마커로 각 버킷 초기화 */
static int __init ct_demo_init(void)
{
    int i;

    /* 랜덤 시드 생성 */
    get_random_bytes(&ct_hash_rnd, sizeof(ct_hash_rnd));

    /* 각 버킷을 nulls 마커로 초기화
     * nulls 값 = 버킷 인덱스 → 리사이즈 감지에 사용 */
    for (i = 0; i < CT_HASH_SIZE; i++) {
        INIT_HLIST_NULLS_HEAD(&ct_hash[i], i);
        spin_lock_init(&ct_locks[i]);
    }

    pr_info("ct_demo: %d buckets, seed=0x%08x\n",
            CT_HASH_SIZE, ct_hash_rnd);
    return 0;
}