Hash Table 심화 (Kernel Hash Table In-Depth)

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

개요 (Overview)

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

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

• inode 캐시 — 파일시스템 inode를 빠르게 검색하는 inode_hashtable
• dentry 캐시 — 경로명 룩업을 가속하는 dentry_hashtable
• PID 해시 — find_task_by_vpid() 등에서 PID → task_struct 변환
• conntrack — Netfilter 연결 추적 테이블 (nf_conntrack)
• 네트워크 소켓 — TCP/UDP 소켓 룩업 해시 (inet_ehash, udp_table)
• 모듈 심볼 — 커널 심볼 테이블 룩업
• 페이지 캐시 — XArray 전환 이전의 radix tree 기반 해시 (역사적)

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

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

hlist 구조 (hlist_head / hlist_node)

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

/* 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 매크로/함수

/* 초기화 */
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 */

커널 해시 함수 (<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)

가변 길이 데이터(문자열, 구조체 등)를 해싱할 때 사용합니다. 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);
}

기타 해시 함수

<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 레퍼런스

완전한 사용 예제

#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로 키 오프셋, 길이, 해시 함수를 구성
• per-bucket 잠금 — 쓰기 연산은 버킷 단위 spinlock으로 세밀하게 직렬화
• 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 해제

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);

동시성 모델 요약

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 */
struct my_object *lookup(int key)
{
    struct my_object *obj;

    rcu_read_lock();
    hash_for_each_possible_rcu(my_ht, obj, hash_node, key) {
        if (obj->key == key) {
            rcu_read_unlock();
            return obj;
        }
    }
    rcu_read_unlock();
    return NULL;
}

/* 쓰기 경로: 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을 초과해도 동작 (성능은 저하되지만 장애는 아님)
• 포인터 기반이므로 요소 이동이 불필요

버킷 크기 선택 가이드

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

캐시 라인 최적화

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

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

커널 활용 사례

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 (비트 스핀락 내장) */

네트워크 소켓 해시

/* TCP established 소켓 해시 (inet_ehash_bucket) */
/* 키: local addr/port + remote addr/port */
/* 빠른 수신 패킷 → 소켓 매핑에 핵심 */

/* UDP 소켓 해시 (udp_table) */
/* 키: local addr/port */
/* reuseport 지원 시 추가 해시로 분산 */

모듈 심볼 해시

/* kernel/module/main.c */
/* EXPORT_SYMBOL로 등록된 심볼을 해시 테이블로 검색 */
/* 모듈 로딩 시 심볼 해석(symbol resolution)에 사용 */

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

자료구조 선택 가이드

디버깅 팁

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")

일반적 실수와 해결