Hash Table

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> — 자동 리사이즈, 대규모 동적 데이터셋에 적합

버킷 인덱스 계산의 실제

해시 테이블 성능을 제대로 이해하려면 “해시값을 버킷 인덱스로 줄이는 단계”를 분리해서 봐야 합니다. 핵심은 해시 혼합(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 매크로/함수

/* 초기화 */
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 메모리 레이아웃 시각화

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 배열 없이 버킷 단위 잠금을 구현할 수 있어 메모리를 절약합니다. 리눅스 dcache(dentry_hashtable)에서 사용되며, 수백만 버킷의 해시 테이블에서 lock 배열의 오버헤드를 제거하는 핵심 기법입니다.

/* 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 변형 비교

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

기타 해시 함수

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

외부 입력(패킷, 사용자 문자열, 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 레퍼런스

완전한 사용 예제

/* 실습 예제: 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로 키 오프셋, 길이, 해시 함수를 구성
• 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 해제

rhashtable 튜닝 플레이북

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

/* 운영 지향 템플릿 예시 */
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 값 선택 기준:

캐시 라인 최적화

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

• 버킷 배열 접근 — 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")

일반적 실수와 해결

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

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

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 전후)부터 네트워크 스택의 해시 함수를 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: 부팅 시 랜덤 생성 */
}

보안 체크리스트

관련 문서

Hash Table과 관련된 다른 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

권장 학습 경로

학습 목적에 따라 시작점을 다르게 잡으면 이해 속도가 빨라집니다.

1. 자료구조 기초 보강
   Linked List → hlist 섹션 → hashtable API
2. 동시성/RCU 중심
   RCU → 동기화 기법 → RCU 해시 섹션 → rhashtable
3. 네트워킹 실전 경로
   네트워크 스택 → conntrack 헬퍼 → conntrack 사례
4. 대안 자료구조 비교
   Red-Black Tree ↔ XArray ↔ 선택 가이드

• Linked List — hlist의 기반인 연결 리스트 구조와 API
• Red-Black Tree — 범위 검색이 필요할 때의 대안 자료구조
• XArray — 정수 키 + 희소 데이터에 최적화된 자료구조
• VFS — inode_hashtable, dentry_hashtable 활용
• 네트워크 스택 — inet_ehash, udp_table 소켓 해시
• RCU — RCU 보호 해시 테이블과 동시성 모델
• 동기화 기법 — spinlock, mutex, per-CPU 잠금 패턴
• conntrack 헬퍼 — nf_conntrack 해시 테이블 활용