LC-Trie (FIB Trie) - IP 라우팅(Routing) 트라이

리눅스 커널의 IPv4 라우팅 테이블(Routing Table) 구현체인 LC-Trie(Level Compressed Trie)를 심층 분석합니다. 비트별 분기 트라이에 경로 압축(path compression)과 레벨 압축(level compression)을 결합하여 최장 접두사 매칭(LPM)을 효율적으로 수행하는 원리, key_vector 노드의 pos/bits/slen 인코딩, fib_table_lookup의 backtrace 기반 검색 알고리즘, inflate/halve 리밸런싱, fib_alias/fib_info 계층 구조, NUMA/캐시(Cache) 최적화, /proc/net/fib_trie 디버깅(Debugging)을 커널 소스(net/ipv4/fib_trie.c) 기반으로 분석합니다.

트라이 기본 개념

트라이(Trie, 또는 prefix tree)는 키의 각 자릿수(여기서는 비트)를 기준으로 분기하는 트리 자료구조입니다. IP 라우팅에서 키는 32비트 IPv4 주소이며, 각 내부 노드는 특정 비트 위치에서 0 또는 1로 분기합니다. "Trie"라는 이름은 retrieval에서 유래했습니다.

트라이의 핵심 속성은 공통 접두사를 공유하는 키들이 같은 서브트리에 위치한다는 점입니다. 이 속성 덕분에 접두사 기반 검색(prefix search)을 자연스럽게 지원합니다. IP 라우팅의 CIDR(Classless Inter-Domain Routing) 접두사가 정확히 트라이의 경로에 대응됩니다.

비트별 분기 원리

순수 이진 트라이(1-bit trie)에서 32비트 IP 주소를 저장하면, 최악의 경우 루트에서 리프까지 32단계를 거쳐야 합니다. 네트워크 접두사(/prefix_len)는 트라이의 중간 노드에 라우팅 정보를 부착하는 것으로 표현됩니다.

/* 1-bit trie 개념적 구조 (실제 커널 코드 아님) */
/* 키: 10.0.0.0 = 0000_1010.0000_0000.0000_0000.0000_0000 */
/*       ↑bit0=0 → 왼쪽 자식                           */
/*        ↑bit1=0 → 왼쪽 자식                          */
/*         ↑bit2=0 → 왼쪽 자식                         */
/*          ↑bit3=0 → 왼쪽 자식                        */
/*           ↑bit4=1 → 오른쪽 자식  ... 계속            */

IP 라우팅과 LPM

라우팅 테이블에는 서로 다른 길이의 접두사가 공존합니다. 예를 들어:

목적지 10.1.2.100을 검색하면, 4개 접두사 모두 매칭되지만 가장 긴 10.1.2.0/24가 선택됩니다. 이것이 LPM(Longest Prefix Match)이며, LC-Trie의 핵심 목표입니다.

트라이 vs 다른 자료구조

여기서 W는 키 길이(32), N은 접두사 수, s는 평균 stride(한 번에 검사하는 비트 수)입니다. LC-Trie는 소프트웨어 구현 중 가장 균형 잡힌 성능을 제공합니다.

Classful vs Classless 라우팅

초기 인터넷은 Classful 라우팅(Class A/B/C)을 사용했습니다. 1993년 CIDR(Classless Inter-Domain Routing)이 도입되면서 임의 길이의 접두사가 가능해졌고, 이는 LPM 자료구조의 필요성을 크게 높였습니다:

경로 압축 (Path Compression)

순수 1-bit trie에서는 자식이 하나뿐인 내부 노드가 무수히 발생합니다. 예를 들어 192.168.0.0/16 하나만 저장해도 16개 레벨의 노드가 필요합니다. 경로 압축(path compression)은 이런 단일 자식 체인을 하나의 노드로 압축합니다.

pos 필드의 역할

압축된 노드는 pos 필드를 통해 "어느 비트 위치부터 검사를 시작하는지" 기록합니다. 중간에 건너뛴 비트들은 검사할 필요가 없는(유일한 경로인) 구간입니다.

/* net/ipv4/fib_trie.c -- key_vector 구조체 (간략화) */
struct key_vector {
    t_key           key;    /* 이 노드의 키 (리프) 또는 접두사 (내부) */
    unsigned char   pos;    /* 검사 시작 비트 위치 (MSB 기준) */
    unsigned char   bits;   /* 한 번에 검사할 비트 수 */
    unsigned char   slen;   /* 서브트리 최대 접두사 길이 */
    /* ... */
    struct key_vector __rcu *tnode[];  /* 유연 배열: 자식 포인터 */
};

경로 압축의 효과

경로 압축의 효과는 트라이의 밀도에 따라 달라집니다. 라우팅 테이블의 접두사 분포가 특정 대역에 집중되어 있으면(예: 10.0.0.0/8 대역에 수천 개의 /24 접두사), 해당 대역 외부 경로의 상당 부분이 경로 압축으로 축소됩니다.

/* 경로 압축 예시: 192.168.1.0/24 하나만 존재할 때 */
/* 압축 전: 24레벨의 내부 노드 체인 */
/*   bit0 → bit1 → ... → bit23 → leaf(192.168.1.0) */
/*                                                   */
/* 압축 후: 단일 노드 */
/*   Root → leaf(192.168.1.0, pos=0, bits=0)         */
/*   pos=0은 "bit 0부터 검사"가 아니라                  */
/*   "모든 비트가 이미 고정됨(리프)"을 의미              */

경로 압축 시 검증

검색 시 pos까지의 비트가 일치하는지 반드시 확인해야 합니다. 건너뛴 비트가 다르면 해당 서브트리에는 매칭 엔트리가 없으므로 backtrace해야 합니다.

/* 경로 압축 검증: 키의 비트 [parent_pos..node_pos) 구간이 일치하는지 확인 */
static inline t_key get_index(t_key key, struct key_vector *kv) {
    /* key에서 pos 위치의 bits 비트를 추출하여 자식 인덱스 계산 */
    return (key >> kv->pos) & (((t_key)1 << kv->bits) - 1);
}

레벨 압축 (Level Compression)

경로 압축이 "희소한(sparse) 구간을 건너뛰기"라면, 레벨 압축은 "밀집한(dense) 구간을 한 번에 처리하기"입니다. 트라이의 특정 구간에서 모든(또는 대부분의) 자식이 존재하면, 비트를 하나씩 검사하는 대신 여러 비트를 한 번에 검사하여 한 단계만에 여러 레벨을 건너뜁니다.

bits 필드와 자식 배열

bits 필드는 해당 노드가 한 번에 검사하는 비트 수를 나타냅니다. 자식 배열의 크기는 2^bits입니다.

LC-Trie의 이름

"LC"는 Level Compression을 의미합니다. 1993년 S. Nilsson과 G. Karlsson이 논문에서 제안한 자료구조로, 경로 압축(Patricia trie)에 레벨 압축을 추가하여 IP 라우팅에 최적화했습니다. 리눅스 커널에서는 Robert Olsson이 2005년(v2.6.13)에 구현했습니다.

레벨 압축 알고리즘

레벨 압축의 핵심은 "완전 이진 서브트리(full binary subtree)를 하나의 다중 분기 노드로 대체"하는 것입니다. 깊이 d의 완전 이진 서브트리를 하나의 bits=d 노드로 압축하면, d레벨이 1레벨로 줄어듭니다.

/* 레벨 압축 조건 (개념적) */
/* 노드 N의 자식이 모두 존재하고 (2^1 = 2개), */
/* 각 자식도 모든 자식이 존재하면 (각 2개, 총 4개), */
/* N을 bits=2 노드로 대체 가능: 4개 자식 직접 연결 */
/*                                                 */
/*     N (bits=1)        →     N' (bits=2)          */
/*    / \                      /  |  |  \            */
/*   A   B (bits=1)           C0  C1 C2  C3         */
/*  /\  /\                                           */
/* C0 C1 C2 C3                                       */

실제로는 완전한 서브트리가 아니더라도, 자식 중 충분한 비율이 내부 노드이면 inflate를 적용합니다. 빈 슬롯이 일부 생기더라도 트라이 깊이 감소의 이점이 메모리 손실보다 클 때 압축합니다.

key_vector 노드

key_vector는 LC-Trie의 유일한 노드 타입으로, 내부 노드(tnode)와 리프(leaf) 모두를 표현합니다. bits == 0이면 리프, bits > 0이면 내부 노드입니다.

필드 상세

/* net/ipv4/fib_trie.c */
#define TNODE_SIZE(n)  offsetof(struct key_vector, tnode[n])
#define TNODE_VMALLOC_MAX  ilog2(SIZE_MAX / TNODE_SIZE(1))

/* 리프 식별: bits == 0 */
#define IS_TNODE(n)  ((n)->bits)
#define IS_LEAF(n)   (!(n)->bits)

tnode 메모리 할당

자식 배열 크기에 따라 할당 전략이 달라집니다:

/* net/ipv4/fib_trie.c -- tnode_alloc */
static struct key_vector *tnode_alloc(int bits)
{
    size_t size;

    /* bits가 0이면 리프: 최소 크기 */
    if (bits == 0)
        size = TNODE_SIZE(0);   /* tnode[] 없이 헤더만 */
    else
        size = TNODE_SIZE(1ul << bits);

    /* PAGE_SIZE 이하: kmalloc, 초과: kvmalloc (vmalloc 가능) */
    if (size <= PAGE_SIZE)
        return kmalloc(size, GFP_KERNEL);
    else
        return kvmalloc(size, GFP_KERNEL);
}

empty_children과 full_children

key_vector는 리밸런싱 판단을 위해 두 가지 카운터를 유지합니다:

/* key_vector 내부의 카운터 (개념적) */
unsigned int empty_children;  /* NULL인 자식 슬롯 수 */
unsigned int full_children;  /* 모든 자식이 채워진 내부 노드 수 */

/* 예: bits=3 (8슬롯), 5개 사용, 3개 NULL */
/*   empty_children = 3                     */
/*   full_children = 사용된 5개 중 tnode의 수   */
/*                                            */
/* 이 카운터들은 삽입/삭제 시 O(1)로 갱신됨    */
/* inflate/halve 판단에 사용되어 resize가      */
/* 전체 자식을 스캔하지 않아도 됨              */

key 필드의 이중 역할

내부 노드의 key는 해당 서브트리가 커버하는 접두사 범위를 나타냅니다. 검색 시 키와 노드의 key를 비교하여 경로 압축 구간의 일치 여부를 확인합니다:

/* 키 접두사 비교 매크로 */
#define IS_TKEY_PREFIX(key1, key2, pos, bits) \
    (((key1) ^ (key2)) >> ((pos) + (bits)) == 0)

/* 사용 예: 검색 키와 노드 키의 상위 비트가 일치하는지 확인 */
if (!IS_TKEY_PREFIX(key, n->key, n->pos, n->bits))
    goto backtrace;  /* 경로 압축 구간 불일치 */

fib_table_lookup

fib_table_lookup은 LC-Trie에서 LPM을 수행하는 핵심 함수입니다. 검색 과정은 크게 (1) 전진(descend), (2) 리프 검사, (3) backtrace의 3단계로 구성됩니다.

알고리즘 개요

1. 전진(Descend): 루트에서 시작하여 키의 비트를 pos/bits에 따라 추출하고 자식 인덱스를 계산하여 내려갑니다.
2. 리프 도달: bits=0인 노드(리프)에 도달하면 키가 일치하는지, fib_alias 중 LPM 조건을 만족하는 엔트리가 있는지 확인합니다.
3. Backtrace: 리프에서 적합한 엔트리를 찾지 못하면, 부모로 올라가며 더 짧은 접두사를 시도합니다. slen 필드를 이용해 탐색 가치가 없는 서브트리를 건너뜁니다.

/* net/ipv4/fib_trie.c -- fib_table_lookup (간략화) */
int fib_table_lookup(struct fib_table *tb,
                     const struct flowi4 *flp,
                     struct fib_result *res, int fib_flags)
{
    struct key_vector *n, *pn;
    t_key key = ntohl(flp->daddr);
    unsigned long index;
    t_key cindex;

    n = get_child_rcu(tb->tb_data, 0);  /* 루트 노드 */
    if (!n) return -EAGAIN;

    /* 1단계: 전진 -- 리프에 도달할 때까지 */
    for (;;) {
        index = get_cindex(key, n);
        if (IS_LEAF(n))
            break;  /* 리프 도달 */

        if (index >= (1ul << n->bits))
            break;  /* 범위 초과: backtrace */

        pn = n;
        n = get_child_rcu(n, index);
        if (!n)
            goto backtrace;
    }

    /* 2단계: 리프 검사 */
    if (check_leaf(tb, key, n, flp, res, fib_flags) == 0)
        return 0;  /* LPM 매칭 성공 */

backtrace:
    /* 3단계: 부모로 올라가며 더 짧은 접두사 탐색 */
    while ((pn = node_parent_rcu(n)) != NULL) {
        /* slen을 확인하여 탐색 가치 판단 */
        /* ... 다음 형제 또는 부모의 다른 접두사 시도 */
    }
    return -ENETUNREACH;
}

check_leaf 상세

check_leaf는 리프에 도달한 후 fib_alias 리스트를 순회하며 LPM 후보를 찾습니다:

/* check_leaf 내부 동작 (간략화) */
static int check_leaf(struct fib_table *tb,
                       t_key key,
                       struct key_vector *l,
                       const struct flowi4 *flp,
                       struct fib_result *res,
                       int fib_flags)
{
    struct fib_alias *fa;

    /* fib_alias 리스트는 fa_slen 순 정렬 (가장 긴 접두사 먼저) */
    hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
        int plen = KEYLENGTH - fa->fa_slen;
        t_key mask = ntohl(inet_make_mask(plen));

        /* 1. 키의 접두사 일치 확인 */
        if ((key ^ l->key) & mask)
            continue;

        /* 2. TOS 일치 확인 */
        if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
            continue;

        /* 3. scope 확인 */
        if (fa->fa_info->fib_scope < flp->flowi4_scope)
            continue;

        /* 매칭 성공: 결과 설정 */
        res->fi = fa->fa_info;
        res->type = fa->fa_type;
        res->prefixlen = plen;
        return 0;
    }
    return 1;  /* 매칭 실패 */
}

backtrace 최적화: slen의 역할

backtrace 시 모든 부모를 방문하면 비효율적입니다. slen 필드는 "이 서브트리에 길이 slen 이하의 접두사가 존재"함을 보장하여, backtrace 범위를 제한합니다:

/* backtrace에서 slen 활용 (개념적) */
/* 현재 위치에서 부모로 올라갈 때: */
/*   parent->slen >= 필요한 접두사 길이 이면 → 탐색 가치 있음 */
/*   parent->slen < 필요한 접두사 길이 이면 → 건너뛰기        */
/*                                                             */
/* 예: 10.1.2.100 검색 중 /24 리프에서 실패 후 backtrace       */
/*   부모 slen=16 → /16 이하 접두사 있을 수 있음 → 탐색       */
/*   조부모 slen=8 → /8 이하만 → 이미 /16을 찾았으면 중단     */

RCU 보호

검색 경로는 rcu_read_lock() 보호 하에 수행됩니다. 모든 자식 포인터 접근은 rcu_dereference()를 통하며, 삽입/삭제는 rcu_assign_pointer()로 수행되어 lock-free 검색이 가능합니다.

/* RCU 보호 하의 검색 */
rcu_read_lock();
ret = fib_table_lookup(tb, flp, res, fib_flags);
rcu_read_unlock();
/* 검색 중 삽입/삭제가 동시에 발생해도 안전 */

/* 쓰기(삽입/삭제)는 RTNL 뮤텍스로 직렬화 */
rtnl_lock();
fib_table_insert(tb, cfg, extack);
rtnl_unlock();
/* writer 간 충돌 방지, reader(검색)와는 동시 가능 */

fib_table_lookup 호출 경로

패킷(Packet)이 수신되어 라우팅 결정이 필요할 때의 호출 체인입니다:

/* 패킷 수신 → 라우팅 결정 경로 */
ip_rcv()
  → ip_rcv_finish()
    → ip_route_input_noref()
      → ip_route_input_rcu()
        → fib_lookup()
          → fib_table_lookup()   /* LC-Trie LPM 수행 */

/* 패킷 송신 → 라우팅 결정 경로 */
ip_queue_xmit()
  → ip_route_output_flow()
    → __ip_route_output_key()
      → fib_lookup()
        → fib_table_lookup()

삽입 연산

새 라우팅 엔트리 삽입은 fib_insert_node 함수가 담당합니다. 삽입 시나리오는 크게 3가지입니다:

시나리오 1: 기존 리프에 추가

동일 IP 주소의 리프가 이미 존재하면, 새 fib_alias를 해당 리프의 리스트에 추가합니다. 트라이 구조 자체는 변경되지 않습니다.

시나리오 2: 새 리프 생성

키가 새로운 IP 주소이면, 적절한 위치에 새 리프를 생성합니다. 이 과정에서 가장 중요한 연산은 분기점(divergence point) 계산입니다. 기존 노드의 키와 새 키의 XOR을 취하면, 최상위 불일치 비트를 __fls(find last set)로 즉시 구할 수 있습니다:

/* 새 리프 삽입 과정 (개념적) */
1. 루트에서 내려가며 삽입 위치 탐색
2. 기존 리프와 새 리프의 키가 갈라지는 비트 위치(분기점) 계산
3. 분기점에 새 내부 노드(tnode) 생성 (pos = 분기 비트, bits = 1)
4. 기존 리프와 새 리프를 새 tnode의 자식으로 연결
5. 부모의 자식 포인터를 새 tnode로 갱신 (rcu_assign_pointer)
6. resize 호출: inflate/halve 필요 여부 확인

시나리오 3: 내부 노드 분할

경로 압축된 노드의 중간에 새 분기가 필요하면, 기존 노드를 분할합니다. 예를 들어 pos=16인 노드가 있는데 비트 20에서 분기해야 하면, 원래 노드를 pos=20인 새 부모와 pos=16인 기존 노드로 분리합니다:

/* 노드 분할 시나리오 */
/* 기존: 부모 → [pos=16, bits=2] → 자식들 */
/* 새 키가 비트 20에서 기존 키와 갈라짐      */
/*                                            */
/* 결과:                                      */
/*   부모 → [새 pos=20, bits=1]               */
/*           /           \                     */
/*   [기존 pos=16, bits=2]  [새 리프]          */
/*      → 자식들                               */

/* net/ipv4/fib_trie.c -- fib_insert_node (간략화) */
static struct key_vector *fib_insert_node(
    struct trie *t,
    struct key_vector *tp,  /* 부모 */
    struct fib_alias *new_fa,
    t_key key)
{
    struct key_vector *l, *n;

    l = leaf_new(key);  /* 새 리프 생성 */
    if (!l) return NULL;

    /* 기존 자식과 새 리프의 분기점 계산 */
    n = get_child(tp, get_index(key, tp));
    if (n) {
        struct key_vector *tn;
        t_key newpos = __fls(key ^ n->key);  /* 첫 불일치 비트 */
        tn = tnode_new(key, newpos, 1);       /* 새 내부 노드 */
        put_child(tn, get_index(key, tn), l);
        put_child(tn, get_index(n->key, tn), n);
        put_child_root(tp, key, tn);
    } else {
        put_child(tp, get_index(key, tp), l);
    }

    trie_rebalance(t, tp);  /* resize 체인 */
    return l;
}

삽입 시 slen 갱신

새 접두사가 삽입되면, 리프에서 루트까지 경로의 모든 노드에서 slen이 갱신될 수 있습니다:

/* slen 갱신 로직 (개념적) */
static void update_suffix(struct key_vector *node)
{
    unsigned char new_slen = 0;
    struct key_vector *child;
    int i;

    /* 모든 자식의 slen 중 최대값을 취함 */
    for (i = child_length(node) - 1; i >= 0; i--) {
        child = get_child(node, i);
        if (child && child->slen > new_slen)
            new_slen = child->slen;
    }

    /* 변경 시 부모도 갱신 (루트까지 전파) */
    if (node->slen != new_slen) {
        node->slen = new_slen;
        if (node_parent(node))
            update_suffix(node_parent(node));
    }
}

trie_rebalance 체인

/* trie_rebalance: 삽입/삭제 후 트리거 */
static void trie_rebalance(struct trie *t,
                            struct key_vector *tn)
{
    while (tn) {
        struct key_vector *tp = node_parent(tn);

        /* resize: inflate 또는 halve 수행 */
        tn = resize(t, tn);

        /* 부모로 올라가며 계속 검사 */
        tn = tp;
    }
}

inflate/halve

LC-Trie의 핵심 리밸런싱 메커니즘입니다. inflate는 노드의 bits를 1 증가시키고(자식 배열 2배), halve는 1 감소시킵니다(자식 배열 절반).

inflate (확장)

노드의 자식 중 대부분이 NULL이 아닌 내부 노드이면, 한 레벨을 흡수하여 트라이 깊이를 줄입니다:

/* inflate 판단 기준 (should_inflate) */
/* 조건: non-empty 자식 중 50% 이상이 내부 노드이고,  */
/*        현재 bits가 INFLATE_THRESHOLD_ROOT 미만      */
static bool should_inflate(struct key_vector *tp,
                           struct key_vector *tn)
{
    unsigned long used = child_length(tn);
    unsigned long threshold = used;

    /* 최소 50%가 non-empty이고, 그 중 절반 이상이 tnode */
    threshold *= tn->full_children;  /* 모든 자식이 non-empty인 수 */
    threshold <<= 1;               /* 2배 (50% 기준) */

    return (used > 1) && tn->pos &&
           ((50 * (tn->full_children + tnode_child_length(tn)/2))
            >= tn->full_children * 100);
}

halve (축소)

inflate의 반대로, 자식의 대부분이 NULL이면 bits를 줄여 메모리를 절약합니다:

/* halve 판단 기준 (should_halve) */
/* 조건: non-empty 자식이 전체의 25% 미만 */
static bool should_halve(struct key_vector *tp,
                          struct key_vector *tn)
{
    return (tn->bits > 1) &&
           (100 * (tnode_child_length(tn) - tn->empty_children)
            < 30 * tnode_child_length(tn));
}

resize 함수

resize는 inflate와 halve를 반복 적용하여 최적 상태에 도달할 때까지 동작합니다:

/* resize: should_inflate → inflate, should_halve → halve 반복 */
static struct key_vector *resize(struct trie *t,
                                   struct key_vector *tn)
{
    /* 루트 노드와 일반 노드의 임계값이 다름 */
    bool is_root = (node_parent(tn) == NULL);

    /* inflate 반복 */
    while (should_inflate(tn, is_root)) {
        tn = inflate(t, tn);
        if (IS_ERR(tn))
            break;  /* 메모리 부족 시 중단 */
    }

    /* halve 반복 */
    while (should_halve(tn, is_root)) {
        tn = halve(t, tn);
        if (IS_ERR(tn))
            break;
    }

    /* 자식이 1개이면 부모와 병합 (경로 압축 복원) */
    if (should_collapse(tn))
        tn = collapse(t, tn);

    return tn;
}

inflate 내부 동작

/* inflate: bits를 1 증가시키는 과정 */
static struct key_vector *inflate(struct trie *t,
                                   struct key_vector *oldtnode)
{
    struct key_vector *tn;
    int i;

    /* 새 노드: bits + 1 (자식 배열 2배) */
    tn = tnode_new(oldtnode->key, oldtnode->pos - 1,
                   oldtnode->bits + 1);

    /* 기존 자식의 자식들을 새 노드에 재배치 */
    for (i = child_length(oldtnode) - 1; i >= 0; i--) {
        struct key_vector *node = get_child(oldtnode, i);
        if (!node) continue;

        if (IS_LEAF(node) || node->pos != (oldtnode->pos - 1)) {
            /* 리프이거나 레벨이 맞지 않으면 그대로 복사 */
            put_child(tn, 2 * i, node);
        } else {
            /* 자식의 자식들을 새 노드에 직접 연결 */
            put_child(tn, 2 * i,     get_child(node, 0));
            put_child(tn, 2 * i + 1, get_child(node, 1));
            tnode_free(node);  /* 흡수된 자식 해제 */
        }
    }
    tnode_free(oldtnode);
    return tn;
}

삭제 연산

라우팅 엔트리 삭제는 fib_table_delete가 담당합니다. 리프에서 fib_alias를 제거하고, 리프가 비면 트라이에서 리프를 제거합니다.

삭제 과정

1. fib_alias 제거: 리프의 fib_alias 리스트에서 해당 엔트리를 hlist_del_rcu로 제거합니다.
2. 리프 제거: fib_alias 리스트가 비면, 부모 노드의 자식 포인터를 NULL로 설정합니다.
3. 트라이 수축: 부모의 자식이 하나만 남으면 경로 압축을 적용하여 부모를 제거합니다.
4. resize: 삭제 후에도 halve 조건을 확인하여 메모리를 회수합니다.

/* 리프 제거 후 트라이 수축 */
static void trie_leaf_remove(struct trie *t,
                              struct key_vector *l)
{
    struct key_vector *tp = node_parent(l);

    put_child(tp, get_index(l->key, tp), NULL);
    node_free(l);

    /* 부모의 자식이 하나뿐이면 부모를 제거하고 */
    /* 유일한 자식을 조부모에 직접 연결 (경로 압축 복원) */
    while (tp && tnode_child_length(tp) == 1) {
        struct key_vector *child = tnode_get_child(tp, 0);
        struct key_vector *pp = node_parent(tp);
        put_child(pp, get_index(tp->key, pp), child);
        node_free(tp);
        tp = pp;
    }

    trie_rebalance(t, tp);
}

대량 삭제 최적화

라우팅 데몬(예: BIRD, FRR)이 BGP 세션 리셋으로 수천 개의 경로를 동시에 삭제하는 경우, 개별 삭제마다 resize를 수행하면 비효율적입니다. 커널은 이를 위해 flush 모드를 제공합니다:

/* net/ipv4/fib_trie.c */
/* fib_table_flush: 특정 조건의 모든 엔트리를 일괄 삭제 */
int fib_table_flush(struct net *net,
                     struct fib_table *tb, bool flush_all)
{
    struct trie *t = (struct trie *)tb->tb_data;
    struct key_vector *l, *tp;
    int found = 0;

    /* 모든 리프를 순회하며 조건에 맞는 fib_alias 제거 */
    for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
        found += flush_leaf(net, tb, l, flush_all);
    }

    /* 일괄 삭제 후 한 번만 전체 rebalance */
    if (found)
        trie_rebalance(t, trie_root(t));

    return found;
}

삭제와 FIB notification

경로 삭제 시 커널은 FIB notification chain을 통해 관련 서브시스템(offload 드라이버, 넷필터 등)에 알립니다:

/* 삭제 알림 체인 */
fib_table_delete()
  → rtmsg_fib(RTM_DELROUTE, ...)  /* netlink 알림 */
  → call_fib_entry_notifiers()     /* FIB notification */
    → hw_offload_driver             /* TC flower offload 등 */
    → nftables_fib                  /* nft fib expression */

leaf chain

하나의 IP 주소(리프)에 여러 라우팅 엔트리가 존재할 수 있습니다. 예를 들어 10.1.0.0에 대해 /16과 /24 접두사 길이가 다른 두 엔트리, 또는 같은 접두사이지만 TOS가 다른 엔트리가 공존할 수 있습니다.

fib_alias 리스트

각 리프는 hlist_head를 통해 fib_alias 구조체의 연결 리스트(Linked List)를 유지합니다:

struct fib_alias {
    struct hlist_node  fa_list;      /* 리프의 alias 리스트 */
    struct fib_info    *fa_info;     /* 라우팅 정보 */
    u8                fa_tos;       /* Type of Service */
    u8                fa_type;      /* RTN_UNICAST, RTN_LOCAL 등 */
    u8                fa_state;     /* FA_S_ACCESSED 등 */
    u8                fa_slen;      /* 접두사 길이 (32 - prefix_len) */
    u32               tb_id;        /* 라우팅 테이블 ID */
    s16               fa_default;   /* default route 우선순위 */
    struct rcu_head    rcu;
};

정렬 순서

fib_alias 리스트는 fa_slen 오름차순(접두사 길이 내림차순) → fa_tos 순으로 정렬됩니다. LPM 검색 시 리스트를 순회하며 가장 먼저 매칭되는 엔트리가 최장 접두사입니다. 이 정렬은 삽입 시점에 유지됩니다:

/* fib_alias 삽입 시 정렬 유지 */
/* fa_slen = KEYLENGTH - prefix_len = 32 - prefix_len */
/* fa_slen이 작을수록 접두사가 김 → 리스트 앞에 위치 */
/*                                                      */
/* 예: /24 → fa_slen=8, /16 → fa_slen=16, /8 → fa_slen=24 */
/* 정렬: [fa_slen=8] → [fa_slen=16] → [fa_slen=24]         */
/*       (/24 먼저)    (/16)           (/8)                  */

fib_alias와 fib_info

fib_alias는 트라이 리프에 부착되는 라우팅 엔트리의 "인덱스"이고, 실제 라우팅 정보는 fib_info에 저장됩니다. 이 분리 설계 덕분에 동일한 넥스트홉 정보를 여러 경로가 공유할 수 있습니다.

fib_info 구조

struct fib_info {
    struct hlist_node  fib_hash;     /* fib_info 해시 테이블 */
    struct hlist_node  fib_lhash;    /* 로컬 해시 */
    struct list_head   nh_list;      /* nexthop 그룹 */
    struct net         *fib_net;     /* 네트워크 네임스페이스 */
    int               fib_treeref;  /* 참조 카운트 */
    refcount_t        fib_clntref;  /* 클라이언트 참조 */
    unsigned int      fib_flags;    /* RTNH_F_* */
    unsigned char     fib_dead;     /* 삭제 예정 */
    unsigned char     fib_protocol; /* RTPROT_* */
    unsigned char     fib_scope;    /* RT_SCOPE_* */
    unsigned char     fib_type;     /* RTN_* */
    __be32            fib_prefsrc;  /* 선호 소스 IP */
    u32               fib_tb_id;    /* 테이블 ID */
    u32               fib_priority; /* 메트릭 */
    struct dst_metrics *fib_metrics; /* MTU, window 등 */
    int               fib_nhs;      /* nexthop 개수 */
    struct fib_nh      fib_nh[];    /* nexthop 배열 (유연 배열) */
};

fib_nh (nexthop)

각 fib_nh는 하나의 넥스트홉을 나타내며, 게이트웨이 주소, 출력 디바이스, 가중치(weight) 등을 포함합니다.

struct fib_nh {
    struct net_device  *fib_nh_dev;     /* 출력 인터페이스 */
    struct fib_nh_common nh_common;     /* 공통 필드 */
    __be32            fib_nh_gw4;     /* IPv4 게이트웨이 */
    int               fib_nh_weight;  /* ECMP 가중치 */
    /* ... */
};

nexthop 오브젝트 (v5.3+)

커널 v5.3부터 넥스트홉이 별도의 오브젝트로 분리되어, 여러 경로가 동일한 넥스트홉 그룹을 공유할 수 있습니다:

/* 기존 방식: fib_info 내에 fib_nh 배열 직접 포함 */
struct fib_info {
    int fib_nhs;
    struct fib_nh fib_nh[];  /* 직접 소유 */
};

/* 새 방식: nexthop 오브젝트 참조 */
struct fib_info {
    struct nexthop *nh;  /* 공유 가능한 nexthop 오브젝트 */
};

/* nexthop 오브젝트 */
struct nexthop {
    struct rb_node  rb_node;   /* ID로 검색 */
    u32            id;         /* 고유 ID */
    u8             protocol;
    u8             nh_flags;
    bool           is_group;   /* 그룹 여부 */
    refcount_t     refcnt;
    struct rcu_head rcu;
    union {
        struct nh_info __rcu *nh_info;   /* 단일 */
        struct nh_group __rcu *nh_grp;   /* 그룹 */
    };
};

fib_info 참조 카운팅

fib_info는 참조 카운트(Reference Count)로 수명을 관리합니다. 여러 fib_alias가 같은 fib_info를 가리킬 수 있으며, 마지막 참조가 해제될 때 메모리가 반환됩니다:

/* fib_info 참조 관리 */
static inline void fib_info_hold(struct fib_info *fi)
{
    refcount_inc(&fi->fib_clntref);
}

void fib_info_put(struct fib_info *fi)
{
    if (refcount_dec_and_test(&fi->fib_clntref))
        free_fib_info(fi);  /* call_rcu로 지연 해제 */
}

NUMA/캐시 최적화

대규모 라우팅 테이블(BGP full table: ~100만 엔트리)에서는 메모리 접근 패턴이 성능에 직접적인 영향을 미칩니다. LC-Trie 검색의 주요 병목(Bottleneck)은 CPU 연산이 아니라 메모리 접근 지연(memory latency)입니다. 검색의 각 레벨에서 다른 캐시라인에 위치한 노드를 읽어야 하기 때문입니다. 커널의 LC-Trie 구현은 다양한 최적화를 적용합니다.

tnode 할당 전략

캐시 친화적 설계

• key_vector 압축: key, pos, bits, slen이 첫 캐시라인(64바이트)에 모두 위치하여, 검색 시 노드당 1~2회 캐시라인 접근으로 충분합니다.
• RCU read-side: 검색 경로에 락이 없으므로 캐시 바운싱(cache bouncing)이 발생하지 않습니다.
• 프리페치: 자식 포인터를 따라가기 전에 다음 노드를 prefetch하는 최적화가 가능합니다.

/* 프리페치 힌트 (개념적) */
n = get_child_rcu(pn, index);
prefetch(n);  /* 다음 반복에서 사용할 노드를 L1에 미리 로드 */

NUMA 고려사항

NUMA 시스템에서는 패킷 처리 CPU와 라우팅 테이블 메모리의 노드 거리가 중요합니다. 커널 6.x에서는 per-CPU 캐시나 NUMA-local 복제 등의 추가 최적화가 논의되고 있습니다.

라우팅 캐시 (route cache)

최신 커널에서는 별도의 라우팅 캐시(FIB nexthop exception cache)를 통해 자주 사용되는 경로의 검색을 가속합니다. 이전 커널(~3.6)에는 전역 route cache가 있었으나, DDoS 공격에 취약하여 제거되었습니다.

/* 현재 커널의 라우팅 캐시 전략 */
/* 1. dst_entry 캐시: 소켓에 바인딩된 경로 캐시 */
/* 2. nexthop exception: PMTU, redirect 정보 캐시 */
/* 3. FIB 검색은 매 패킷마다 수행 (캐시 미스 시) */
/*    → LC-Trie의 빠른 검색이 더욱 중요해짐       */

/proc/net/fib_trie

/proc/net/fib_trie는 전체 LC-Trie 구조를 텍스트로 덤프하는 procfs 인터페이스입니다. 라우팅 트라이의 구조를 직접 확인하고 디버깅하는 데 핵심적인 도구입니다.

출력 형식

# cat /proc/net/fib_trie
Main:
  +-- 0.0.0.0/0 3 0 2
     +-- 0.0.0.0/1 2 0 2
        |-- 0.0.0.0
           /0 universe UNICAST
        +-- 10.0.0.0/8 2 0 2
           +-- 10.0.0.0/16 2 0 1
              |-- 10.0.0.0
                 /16 universe UNICAST
              |-- 10.0.1.0
                 /24 link UNICAST
           |-- 10.1.0.0
              /16 universe UNICAST
     +-- 192.168.0.0/16 2 0 2
        |-- 192.168.1.0
           /24 link UNICAST
        |-- 192.168.1.1
           /32 host LOCAL
Local:
  +-- 0.0.0.0/0 3 0 2
     ...

활용 방법

# 전체 트라이 구조 확인
$ cat /proc/net/fib_trie

# 특정 IP의 매칭 확인
$ ip route get 10.1.2.100
10.1.2.100 via 10.1.2.1 dev eth0 src 10.1.2.10 uid 1000
    cache

# 트라이에서 해당 경로 추적
$ grep -A2 "10.1.2" /proc/net/fib_trie
        |-- 10.1.2.0
           /24 link UNICAST

# 트라이의 리프 수 카운트
$ grep -c "^.*|--" /proc/net/fib_trie

# 내부 노드 수 카운트
$ grep -c "^.*+--" /proc/net/fib_trie

# 특정 테이블(Main/Local)만 필터링
$ awk '/^Main:$/,/^Local:$/' /proc/net/fib_trie

fib_trie 출력의 구조적 이해

들여쓰기 깊이는 트라이의 레벨을 나타냅니다. +--는 내부 노드(tnode), |--는 리프입니다. 내부 노드 뒤의 3개 숫자는 순서대로 bits, full_children, empty_children입니다:

/* 출력 해석 예시 */
Main:
  +-- 0.0.0.0/0 8 6 245
  ↑               ↑ ↑  ↑
  접두사/길이     |  |  empty_children=245 (256-11=245 빈 슬롯)
                  |  full_children=6 (모든 자식이 채워진 tnode 수)
                  bits=8 → 2^8 = 256 자식 배열
                  → 11개 사용 중 (256-245=11)
                  → 사용률 4.3% (11/256)

/proc/net/fib_triestat

/proc/net/fib_triestat는 트라이의 통계 정보를 제공합니다. 노드 수, 메모리 사용량, 트라이 깊이 분포 등을 확인할 수 있습니다.

출력 예시 및 해석

# cat /proc/net/fib_triestat
Basic info: size of leaf: 48 bytes, size of tnode: 40 bytes.
Main:
	Aver depth:     2.85
	Max depth:      7
	Leaves:         42
	Prefixes:       47
	Internal nodes: 19
	  1: 8  2: 6  3: 3  4: 2
	Pointers: 140
	  Null ptrs: 83
	Total size: 12  kB
Local:
	Aver depth:     3.10
	Max depth:      5
	Leaves:         38
	Prefixes:       38
	Internal nodes: 16
	  1: 5  2: 6  3: 3  4: 2
	Pointers: 120
	  Null ptrs: 70
	Total size: 10  kB

bits 분포 해석

# fib_triestat의 bits 분포 예시
Internal nodes: 19
  1: 8  2: 6  3: 3  4: 2

# 해석:
# bits=1 노드 8개: 이진 분기 (최소 크기, 2 자식)
# bits=2 노드 6개: 4-way 분기
# bits=3 노드 3개: 8-way 분기
# bits=4 노드 2개: 16-way 분기
#
# BGP full table의 전형적 분포:
# 루트: bits=8 (256-way)
# 레벨 1: bits=4~6 (16~64-way)
# 레벨 2+: bits=1~3 (2~8-way)
# 총 메모리: 루트 2KB + 수천 개의 작은 노드

모니터링 스크립트

#!/bin/bash
# 주기적으로 트라이 통계를 모니터링

while true; do
    echo "$(date +%H:%M:%S)"
    awk '/^Main:/,/^$/ {
      if (/Aver depth/) printf "  평균깊이: %s\n", $3
      if (/Max depth/)  printf "  최대깊이: %s\n", $3
      if (/Leaves/)     printf "  리프수: %s\n", $2
      if (/Prefixes/)   printf "  접두사수: %s\n", $2
      if (/Total size/) printf "  메모리: %s KB\n", $3
    }' /proc/net/fib_triestat
    echo "---"
    sleep 10
done

fib_hash 역사

LC-Trie 이전에 리눅스 커널은 해시 테이블 기반의 fib_hash를 사용했습니다. 이 역사를 이해하면 LC-Trie의 설계 결정을 더 잘 이해할 수 있습니다.

연대기

fib_hash의 한계

fib_hash는 접두사 길이(0~32)별로 별도의 해시 테이블을 유지했습니다. LPM 수행 시 가장 긴 접두사부터 하나씩 해시 테이블을 검색하므로, 최악의 경우 33번의 해시 조회가 필요했습니다.

/* fib_hash의 LPM (제거된 코드, 개념적) */
for (prefix_len = 32; prefix_len >= 0; prefix_len--) {
    /* hash_table[prefix_len]에서 검색 */
    if (hash_lookup(fz[prefix_len], key, prefix_len))
        return found;
}
/* 최악: 33번 해시 조회 */

주요 커밋 히스토리

CONFIG_IP_FIB_TRIE_STATS

커널 설정에서 CONFIG_IP_FIB_TRIE_STATS=y를 활성화하면 트라이 연산의 상세 통계를 수집합니다:

# 커널 설정
CONFIG_IP_FIB_TRIE_STATS=y

# /proc/net/fib_triestat에 추가 통계 출력:
# - 검색 횟수, 평균 비교 횟수
# - backtrace 발생 횟수
# - 캐시 미스 추정치
# 프로덕션에서는 성능 오버헤드로 비활성 권장

IPv6 비교

IPv4의 LC-Trie와 달리, IPv6 라우팅은 다른 자료구조를 사용합니다.

IPv6 FIB: fib6_table

왜 IPv4와 같은 구현이 아닌가?

• 키 길이 4배: 128비트 키에 LC-Trie를 그대로 적용하면 트라이 깊이가 매우 깊어질 수 있습니다.
• 접두사 분포 차이: IPv6는 /48, /64 등 소수의 접두사 길이에 집중되어, 트라이 압축의 이점이 다릅니다.
• 역사적 이유: IPv6 FIB는 별도의 개발자가 다른 시기에 구현했습니다.

fib6_node 구조

/* net/ipv6/ip6_fib.c */
struct fib6_node {
    struct fib6_node __rcu *parent;
    struct fib6_node __rcu *left;    /* bit=0 */
    struct fib6_node __rcu *right;   /* bit=1 */
    struct fib6_info __rcu *leaf;    /* 라우팅 정보 */
    __u16           fn_bit;   /* pos에 해당 (검사 비트 위치) */
    __u16           fn_flags;
    int             fn_sernum;
    struct rcu_head  rcu;
};
/* IPv6 FIB는 항상 1-bit trie (left/right 이진 분기) */
/* LC-Trie의 multi-bit 분기(레벨 압축)가 없음        */
/* 128비트 키에 대해 최대 128레벨 깊이 가능           */

듀얼스택 시스템에서의 고려사항

IPv4/IPv6 듀얼스택 환경에서는 두 개의 독립된 FIB가 동시에 동작합니다:

정책 라우팅과 다중 FIB 테이블

정책 라우팅(policy routing)은 소스 IP, TOS, fwmark 등 추가 조건에 따라 서로 다른 FIB 테이블을 선택합니다. 각 FIB 테이블은 독립된 LC-Trie를 가지므로, 정책 라우팅 환경에서는 여러 개의 LC-Trie가 병렬로 존재합니다. fib4_rule_action()이 규칙에 매칭된 테이블의 fib_table_lookup()을 호출하는 구조입니다.

멀티패스 라우팅 (ECMP)

ECMP(Equal-Cost Multi-Path)는 하나의 fib_info에 여러 fib_nh를 연결하여 동일 목적지에 대해 여러 넥스트홉으로 트래픽을 분산하는 기법입니다. LC-Trie 관점에서 리프 노드의 fib_alias가 가리키는 fib_info에 복수의 넥스트홉이 포함되며, fib_select_multipath()가 패킷의 해시 값으로 넥스트홉을 선택합니다.

성능 분석

LC-Trie의 성능은 라우팅 테이블 크기, 접두사 분포, 하드웨어 특성에 따라 달라집니다.

시간 복잡도

대규모 테이블 벤치마크

메모리 사용량

패킷 포워딩 성능 측정

# iperf3로 스루풋 측정
$ iperf3 -c 10.1.2.1 -t 30 -P 4

# perf로 fib_table_lookup 비용 프로파일링
$ perf record -g -a -- sleep 10
$ perf report --symbol-filter=fib_table_lookup
# 일반적으로 전체 패킷 처리의 2~5% 차지

# nftables/iptables 없는 순수 포워딩 성능
# 10Gbps NIC, BGP full table 기준:
# - 소형 패킷(64B): ~10Mpps (주로 캐시 미스가 병목)
# - 대형 패킷(1500B): 라인레이트 도달 가능

XDP/eBPF와의 비교

극한 성능이 필요한 경우, XDP(eXpress Data Path)를 사용하여 커널 네트워크 스택(Network Stack)을 우회할 수 있습니다:

라우팅 테이블 최적화 팁

• 경로 집약(aggregation): 10.1.0.0/24, 10.1.1.0/24, ..., 10.1.255.0/24를 10.1.0.0/16 하나로 집약하면 리프 255개가 1개로 줄어듭니다. BGP에서는 aggregate-address 명령을 사용합니다.
• 불필요한 경로 제거: default route로 충분한 경로는 개별 등록하지 않습니다.
• 테이블 분리: 대량의 정적 경로와 동적 경로를 별도 테이블로 분리하면 각 트라이의 깊이를 줄일 수 있습니다.
• nexthop 오브젝트 활용: 공통 넥스트홉을 nexthop 오브젝트로 공유하면 fib_info 중복을 줄입니다.

하드웨어 오프로드

최신 네트워크 스위치 칩(예: Memory Switch Barefoot/Tofino, Broadcom Memory, Mellanox Spectrum)은 TCAM이나 알고리즘 기반 LPM을 하드웨어로 지원합니다. 리눅스 커널은 switchdev 프레임워크를 통해 소프트웨어 FIB의 변경을 하드웨어에 동기화합니다:

/* 하드웨어 오프로드 경로 */
fib_table_insert()
  → call_fib_entry_notifiers(FIB_EVENT_ENTRY_ADD)
    → switchdev driver
      → TCAM/ALU 프로그래밍

/* 오프로드 상태 확인 */
$ ip route show
10.0.0.0/8 via 192.168.1.1 dev eth0 offload  ← offload 표시

디버깅 가이드

LC-Trie 관련 문제를 진단하는 체계적인 접근법입니다.

일반적 문제와 해결

진단 명령어

# 1. 특정 목적지의 실제 라우팅 결과 확인
$ ip route get 10.1.2.100
10.1.2.100 via 10.1.2.1 dev eth0 src 10.1.2.10 uid 0
    cache

# 2. 라우팅 테이블 확인
$ ip route show table main
$ ip route show table all

# 3. 트라이 구조 확인
$ cat /proc/net/fib_trie | head -50

# 4. 트라이 통계 확인
$ cat /proc/net/fib_triestat

# 5. 정책 라우팅 규칙 확인
$ ip rule show

# 6. ECMP nexthop 상태 확인
$ ip nexthop show
$ ip -s nexthop show id 10

# 7. ftrace로 fib_table_lookup 추적
$ echo 1 > /sys/kernel/debug/tracing/events/fib/fib_table_lookup/enable
$ cat /sys/kernel/debug/tracing/trace_pipe

ftrace를 이용한 심층 디버깅

# fib_table_lookup 이벤트 활성화
$ cd /sys/kernel/debug/tracing
$ echo fib:fib_table_lookup > set_event
$ echo 1 > tracing_on

# 트레이스 확인
$ cat trace_pipe
 ping-1234 [002] .... 12345.678: fib_table_lookup:
    table=254 oif=0 iif=1 src=10.0.0.1 dst=10.1.2.100 tos=0
    scope=0 flags=0 result=10.1.2.0/24 via 10.1.2.1 dev eth0

# 비활성화
$ echo 0 > tracing_on

# perf로 fib_table_lookup 성능 측정
$ perf stat -e cache-misses,cache-references,instructions \
    -p $(pgrep -f "softirq") -- sleep 10

# fib_table_lookup 호출 빈도
$ perf top -g --call-graph dwarf | grep fib_table

트라이 구조 시각화 스크립트

#!/bin/bash
# fib_trie 구조를 요약하는 간단한 스크립트

echo "=== FIB Trie 요약 ==="
echo "--- 라우팅 테이블 ---"
ip route show table main | wc -l
echo "개 경로 (main table)"

echo ""
echo "--- Trie 통계 ---"
cat /proc/net/fib_triestat | head -20

echo ""
echo "--- 가장 깊은 경로 ---"
# 들여쓰기 깊이로 최대 깊이 추정
awk '/^\s+\+--|^\s+\|--/ {
  depth = (length($0) - length(ltrim($0))) / 3;
  if (depth > max) { max = depth; line = $0 }
}
function ltrim(s) { sub(/^\s+/, "", s); return s }
END { print "최대 깊이:", max; print line }' /proc/net/fib_trie

echo ""
echo "--- NULL 포인터 비율 ---"
awk '/Null ptrs:/ { null=$3 }
     /Pointers:/ { total=$2 }
     END { if (total > 0) printf "%.1f%% (%d/%d)\n", null*100/total, null, total }' \
  /proc/net/fib_triestat

커널 로그 디버깅

# FIB 관련 netlink 메시지 모니터링
$ ip monitor route

# 커널 라우팅 결정 추적 (커널 4.17+)
$ perf trace -e 'fib:*' -- sleep 5

# dropwatch로 라우팅 드롭 감지
$ dropwatch -l kas
dropwatch> start
# ENETUNREACH 등 라우팅 실패로 인한 드롭 확인

일반적 실수와 해결

커널 소스 참조

LC-Trie 관련 핵심 소스 파일과 함수 위치입니다:

전체 LPM 검색 추적 예제

실제 라우팅 테이블에서 목적지 10.1.2.100을 검색하는 전체 과정을 비트 단위로 추적합니다. 아래 라우팅 테이블이 존재한다고 가정합니다:

검색 키 분해

/* 목적지: 10.1.2.100 */
/* 이진 표현: */
10      = 0000_1010
1       = 0000_0001
2       = 0000_0010
100     = 0110_0100

/* 32비트 키 (MSB first): */
key = 0000_1010 . 0000_0001 . 0000_0010 . 0110_0100
      bit31                                      bit0
      ←── 네트워크 부분 ──→←── 호스트 부분 ──→

단계별 트라이 워크

/* Step-by-step 의사 코드 */

/* key = ntohl(10.1.2.100) = 0x0A010264 */
t_key key = 0x0A010264;

/* Step 1: Root (pos=31, bits=1) */
index = (key >> 31) & 1;          /* = 0  (10.x = MSB가 0) */
n = get_child(root, 0);            /* 0.0.0.0~127.x.x.x 서브트리 */

/* Step 2: (pos=23, bits=8) -- 레벨 압축으로 8비트 한번에 */
index = (key >> 23) & 0xFF;       /* = 0x0A = 10 */
n = get_child(node, 10);           /* 10.x.x.x 서브트리 */

/* Step 3: (pos=15, bits=8) */
index = (key >> 15) & 0xFF;       /* = 0x01 = 1 */
n = get_child(node, 1);            /* 10.1.x.x 서브트리 */

/* Step 4: (pos=7, bits=8) */
index = (key >> 7) & 0xFF;        /* = 0x02 = 2 */
n = get_child(node, 2);            /* 10.1.2.x 서브트리 → leaf */

/* Step 5: IS_LEAF(n) == true → check_leaf */
check_leaf: key == 0x0A010200? /* 10.1.2.0 */
  → prefix 0x0A010200/24: match!
  → return nexthop 10.1.2.1 via eth0;

Backtrace 시나리오

만약 10.1.3.100을 검색하는데 10.1.3.0/24 경로가 없다면, backtrace가 발생합니다:

/* 10.1.3.100 검색 -- backtrace 발생 시나리오 */

/* Step 1~3: 동일하게 10.1.x.x 내부 노드까지 도달 */

/* Step 4: (pos=7, bits=8) */
index = (key >> 7) & 0xFF;        /* = 0x03 = 3 */
n = get_child(node, 3);            /* → NULL! 10.1.3.x 엔트리 없음 */

/* Backtrace 시작 */
/* Step B1: 부모(10.1.x.x 노드)로 올라감 */
/*   이 노드의 slen=16 → /16 이하 접두사 존재 가능 */
/*   check_leaf: 10.1.0.0/16 → match! */
→ return nexthop 10.1.0.1;

/* 만약 10.1.0.0/16도 없었다면: */
/* Step B2: 조부모(10.x.x.x 노드)로 올라감, slen=8 */
/*   check_leaf: 10.0.0.0/8 → match! */

/* 만약 10.0.0.0/8도 없었다면: */
/* Step B3: 루트, slen=0 */
/*   check_leaf: 0.0.0.0/0 (default route) → match! */

ip route get으로 검증

# 실제 시스템에서 LPM 결과 확인
$ ip route get 10.1.2.100
10.1.2.100 via 10.1.2.1 dev eth0 src 10.1.2.10 uid 0
    cache

# 10.1.3.100: /24 없으므로 /16이 매칭
$ ip route get 10.1.3.100
10.1.3.100 via 10.1.0.1 dev eth1 src 10.1.0.10 uid 0
    cache

# 8.8.8.8: /8, /16, /24 모두 없으므로 default route
$ ip route get 8.8.8.8
8.8.8.8 via 192.168.1.1 dev eth0 src 192.168.1.10 uid 0
    cache

# ftrace로 내부 동작 추적
$ echo 1 > /sys/kernel/debug/tracing/events/fib/fib_table_lookup/enable
$ ip route get 10.1.2.100
$ cat /sys/kernel/debug/tracing/trace_pipe
  ip-12345 [000] .... 1234.567890: fib_table_lookup: table=254 oif=0
    iif=1 src=0.0.0.0 dst=10.1.2.100 tos=0 scope=0 flags=0
    result=10.1.2.0/24 nhc=10.1.2.1/32 dev=eth0

key_vector 메모리 레이아웃

key_vector는 LC-Trie의 유일한 노드 타입으로, 내부 노드와 리프를 모두 표현합니다. 메모리 효율을 위해 비트 필드와 유니온을 적극 활용합니다.

구조체 상세 분석

/* net/ipv4/fib_trie.c */
struct key_vector {
    t_key key;                /* 32비트 키 (IP 주소) */
    unsigned char pos;        /* 검사 시작 비트 위치 (0~31) */
    unsigned char bits;       /* 한 번에 검사할 비트 수 (0=leaf) */
    unsigned char slen;       /* 서브트리 최대 접두사 길이 (suffix length) */
    union {
        /* 내부 노드: 자식 포인터 배열 (1 << bits 개) */
        struct key_vector __rcu *tnode[0];
        /* 리프 노드: fib_alias 리스트 헤더 */
        struct hlist_head leaf;
    };
};

/* tnode 래퍼 -- key_vector + 메타데이터 */
struct tnode {
    struct rcu_head rcu;       /* RCU callback (해제 시 사용) */
    t_key empty_children;      /* NULL 자식 수 */
    t_key full_children;       /* 가득 찬 자식 수 */
    struct key_vector __rcu *parent; /* 부모 포인터 */
    struct key_vector kv[1];  /* key_vector 본체 (flexible array) */
};

pos/bits 인코딩 규칙

tnode 크기 클래스

tnode 생명주기

tnode의 할당부터 RCU grace period를 거쳐 해제되기까지의 전체 생명주기를 분석합니다.

/* tnode 할당: bits 크기에 따라 kmalloc/kvmalloc 선택 */
static struct tnode *tnode_alloc(int bits)
{
    size_t size;

    if (bits == 0)
        return kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);

    size = offsetof(struct tnode, kv[0].tnode[1ul << bits]);

    if (size <= PAGE_SIZE)
        return kzalloc(size, GFP_KERNEL);
    else
        return kvzalloc(size, GFP_KERNEL);
}

/* tnode 해제: RCU callback */
static void tnode_free(struct tnode *tn)
{
    if (tn->kv[0].bits == 0)
        kmem_cache_free(trie_leaf_kmem, tn);
    else
        kvfree(tn);
}

/* RCU를 통한 안전한 교체 */
static void replace(struct trie *t,
                    struct key_vector *oldtnode,
                    struct key_vector *tn)
{
    struct key_vector *tp = node_parent(oldtnode);

    /* 새 노드를 부모에 연결 (reader에게 즉시 보임) */
    put_child_root(tp, t, tn->key, tn);

    /* 구 노드는 RCU grace period 후 해제 */
    node_set_parent(tn, tp);
    tnode_free_safe(oldtnode);  /* → call_rcu() */
}

리프 전용 kmem_cache

/* 리프 전용 슬랩 캐시 -- 빈번한 할당/해제 최적화 */
static struct kmem_cache *trie_leaf_kmem;

void __init fib_trie_init(void)
{
    trie_leaf_kmem = kmem_cache_create(
        "ip_fib_trie",
        LEAF_SIZE,               /* ~56 bytes */
        0,                         /* align */
        SLAB_PANIC | SLAB_ACCOUNT,
        NULL
    );
}

/* LEAF_SIZE = offsetof(struct tnode, kv[0].tnode[0])
 *           + sizeof(struct hlist_head)
 * 리프는 자식 배열이 없고 hlist_head(fib_alias 리스트)만 가짐 */

RCU 동시성 심층 분석

LC-Trie의 동시성 모델은 reader는 RCU로 lock-free, writer는 RTNL 뮤텍스(Mutex)로 직렬화(Serialization)하는 구조입니다. 이 설계 덕분에 패킷 포워딩 경로(softirq)에서 잠금(Lock) 없이 라우팅 검색이 가능합니다.

RCU 포인터 접근 패턴

/* Reader 측: lock-free 검색 */
static inline struct key_vector *
get_child_rcu(const struct key_vector *tn, unsigned long i)
{
    /* rcu_dereference: 읽기 메모리 배리어 + 컴파일러 배리어
     * 이전에 rcu_assign_pointer로 설정된 포인터를 안전하게 읽음 */
    return rcu_dereference(tn->tnode[i]);
}

/* Writer 측: 새 자식 설정 */
static inline void
put_child(struct key_vector *tn, unsigned long i,
          struct key_vector *n)
{
    struct key_vector *chi = get_child(tn, i);

    /* empty_children / full_children 카운터 갱신 */
    update_children(tn, chi, n);

    /* rcu_assign_pointer: 쓰기 메모리 배리어 + 포인터 발행
     * 이후 reader가 get_child_rcu로 읽으면 새 노드가 보임 */
    rcu_assign_pointer(tn->tnode[i], n);
}

resize 중 동시성

/* inflate(확장) 중에도 reader는 안전하게 검색 가능 */
/*
 * inflate는 3단계로 수행:
 *
 * 1) 새 큰 노드(newtn) 할당
 * 2) 자식들을 새 노드로 복사/재배치
 *    → 각 자식에 대해 rcu_assign_pointer로 한 개씩 이동
 *    → 중간 상태에서도 reader는 구 노드 또는 신 노드 중 하나를 봄
 *    → 어느 쪽이든 올바른 검색 결과 보장
 * 3) 부모의 자식 포인터를 구 노드 → 신 노드로 교체
 *    → rcu_assign_pointer(parent->tnode[i], newtn)
 *    → 이 시점 이후 새 reader는 신 노드만 봄
 * 4) 구 노드를 call_rcu로 지연 해제
 */

/* 핵심 불변식(invariant): */
/* "reader가 어떤 시점에 트라이를 읽더라도
 *  올바른 LPM 결과를 얻는다"
 *
 * 이를 위해 inflate/halve는 자식을 한 개씩 이동하며,
 * 각 이동이 원자적(atomic)으로 보이도록 보장한다. */

reader/writer 충돌 시나리오

FIB 알림 체인 (Notification Chain)

라우팅 엔트리가 추가/삭제/변경될 때, FIB 코어는 call_fib_entry_notifiers()를 통해 switchdev, netfilter, BPF, rtnetlink 등 관심 있는 서브시스템에 이벤트를 전파합니다. 하드웨어 오프로드(switchdev) 드라이버는 이 알림을 받아 TCAM에 경로를 동기화합니다.

라우팅 캐시 진화사

Linux IPv4의 라우팅 캐시는 v3.6(커밋 89aef8a)에서 전면 제거되었습니다. 기존 전역 해시 기반 route cache는 DDoS 공격 시 메모리 폭발과 해시 충돌 취약점이 있었습니다. LC-Trie의 O(W) 검색이 충분히 빨라 모든 패킷에 FIB lookup을 직접 수행해도 되며, PMTU/redirect 정보는 nexthop exception으로 대체되었습니다.

Nexthop 예외 처리 (PMTU, Redirect)

Route cache 제거 후, PMTU 발견 결과나 ICMP Redirect 정보를 저장하기 위해 fib_nh_exception 구조체가 도입되었습니다(v4.2+). 넥스트홉별로 해시 테이블(FNHE_HASH_SIZE=2048)에 저장되며, find_exception()으로 조회합니다.

inet_addr_type과 fib_validate_source

FIB Trie는 라우팅 결정 외에도 inet_addr_type()으로 주소 유형(RTN_LOCAL, RTN_UNICAST 등)을 분류하고, fib_validate_source()로 역경로 필터링(rp_filter)을 수행합니다. 두 기능 모두 내부적으로 fib_table_lookup()을 호출하여 LC-Trie를 조회합니다.

FIB Netlink 인터페이스

사용자 공간(iproute2, FRR/BIRD)은 netlink 소켓의 RTM_NEWROUTE/RTM_DELROUTE/RTM_GETROUTE 메시지로 FIB 테이블을 조작합니다. inet_rtm_newroute() → fib_table_insert()로 LC-Trie에 삽입되고, 변경 시 RTMGRP_IPV4_ROUTE 그룹으로 알림이 전파됩니다.

BGP Full Table 최적화

인터넷 BGP full routing table은 2024년 기준 100만 개 이상의 IPv4 접두사를 포함합니다. 이 대규모 테이블을 LC-Trie로 효율적으로 처리하기 위한 최적화 기법을 분석합니다.

대규모 테이블 튜닝

# netlink 수신 버퍼 확대 (BGP 대량 주입 시)
$ sysctl net.core.rmem_max=16777216
$ sysctl net.core.rmem_default=8388608

# BGP convergence 시간 측정
$ time birdc show route count
1045382 of 1045382 routes

# fib_triestat로 트라이 효율성 확인
$ cat /proc/net/fib_triestat
Basic info: size of leaf: 56 bytes, size of tnode: 40 bytes.
Main:
    Aver depth:     4.24
    Max depth:      9
    Leaves:         1045382
    Prefixes:       1048921
    Internal nodes: 413256
      1: 98234  2: 182450  3: 45601  4: 38291
      5: 22103  6: 14281  7: 8890   8: 3406
    Pointers: 2648192
      Null ptrs:  1218554  /* 46% -- 양호 */

# NULL 포인터 비율이 80% 이상이면 halve가 적극적으로 작동해야 함
# 30% 미만이면 inflate가 부족 → 검색 깊이 증가 가능

convergence 최적화 기법

/* BGP convergence 시 수십만 경로가 한꺼번에 추가/제거됨 */

/* 1. FRR의 netlink 배치 전송 */
/* zebra/rt_netlink.c: 여러 경로를 하나의 sendmsg에 패킹 */
/* NLM_F_ACK를 마지막 메시지에만 설정 → 커널 응답 대기 최소화 */

/* 2. nexthop 오브젝트 활용 (v5.3+) */
/* 동일 AS의 수천 경로가 같은 nexthop을 공유 */
/* nexthop 변경 시 한 번의 수정으로 모든 경로에 반영 */
$ ip nexthop replace id 100 via 10.0.0.2 dev eth0
/* → 이 nh를 참조하는 모든 경로의 nexthop이 즉시 변경 */
/* → 각 경로를 개별 수정할 필요 없음 */

/* 3. 경로 집약 (aggregation) */
/* 인접한 /24 4개를 /22 하나로 집약 */
/* 10.1.0.0/24 + 10.1.1.0/24 + 10.1.2.0/24 + 10.1.3.0/24
 * → 10.1.0.0/22 (동일 nexthop인 경우) */
/* LC-Trie 리프 4개 → 1개로 축소 */

/* 4. graceful restart */
/* BGP 세션 재설정 시 기존 경로 유지 → FIB 변경 최소화 */
/* "stale" 경로를 유지하다가 새 세션에서 확인 후 제거 */

fib_trie_walk 이터레이터

/proc/net/fib_trie와 ip route show는 LC-Trie를 순회(iterate)하여 모든 경로를 나열합니다. 이 순회는 fib_trie_seq_ops / fib_route_seq_ops를 통해 구현됩니다.

seq_file 기반 순회

/* net/ipv4/fib_trie.c -- /proc/net/fib_trie */
static const struct seq_operations fib_trie_seq_ops = {
    .start = fib_trie_seq_start,
    .next  = fib_trie_seq_next,
    .stop  = fib_trie_seq_stop,
    .show  = fib_trie_seq_show,
};

/* 순회 상태 */
struct fib_trie_iter {
    struct seq_net_private p;
    struct fib_table *tb;      /* 현재 테이블 */
    struct key_vector *tnode;   /* 현재 노드 */
    unsigned int index;         /* 현재 자식 인덱스 */
    unsigned int depth;         /* 현재 깊이 */
};

/* 순회 알고리즘: 깊이 우선 탐색 (DFS)
 *
 * 시작: 루트 노드
 * 반복:
 *   1) 현재 노드가 내부 노드이면
 *      → 첫 번째 non-NULL 자식으로 내려감
 *   2) 현재 노드가 리프이면
 *      → show()로 출력
 *      → 다음 형제로 이동
 *   3) 형제가 없으면
 *      → 부모로 올라가서 다음 형제 탐색
 *   4) 루트를 넘어서면 다음 FIB 테이블로 이동
 */

ip route show의 내부

/* ip route show는 netlink RTM_GETROUTE + NLM_F_DUMP을 사용 */

/* 1. iproute2 → 커널: FIB 덤프 요청 */
sendmsg(fd, {
    nlh: { type=RTM_GETROUTE, flags=NLM_F_DUMP|NLM_F_REQUEST },
    rtm: { family=AF_INET, table=RT_TABLE_MAIN }
});

/* 2. 커널: inet_dump_fib → fib_table_dump → LC-Trie 순회 */
inet_dump_fib(skb, cb)
{
    /* 모든 FIB 테이블을 순회 */
    hlist_for_each_entry_rcu(tb, head, tb_hlist) {
        fib_table_dump(tb, skb, cb, &filter);
        /* → LC-Trie의 모든 리프를 방문
         * → 각 리프의 fib_alias 리스트를 순회
         * → netlink 메시지로 변환하여 skb에 추가 */
    }
}

/* 3. 대규모 테이블 덤프 시 주의점 */
/* 100만 경로 덤프 → 수십 MB의 netlink 메시지
 * cb->args[]에 순회 위치를 저장하여 여러 recvmsg에 걸쳐 분할 전송
 * RCU 보호 하에 실행되므로 덤프 중 삽입/삭제도 안전 */

fib_validate_source 심층 분석

__fib_validate_source()는 수신 패킷의 소스 IP를 목적지로 역방향 FIB 검색하여, 해당 경로의 출력 인터페이스가 패킷의 입력 인터페이스와 일치하는지 확인합니다. strict 모드(rp_filter=1)는 인터페이스 일치까지 검증하고, loose 모드(rp_filter=2)는 경로 존재만 확인합니다.

fib_info 공유와 해시

동일한 넥스트홉, 프로토콜, scope을 가진 라우팅 엔트리는 fib_info 구조체를 공유합니다. 이 공유 메커니즘은 해시 테이블 기반으로 구현되어 대규모 라우팅 테이블에서 메모리를 크게 절약합니다.

fib_info 해시 검색

/* net/ipv4/fib_semantics.c */

/* fib_info 해시 테이블 -- 동일 fi를 공유하기 위한 검색 */
static struct hlist_head *fib_info_hash;
static unsigned int fib_info_hash_size;

/* 해시 키: nexthop IP + oif + protocol + scope + priority 조합 */
static inline unsigned int fib_info_hashfn(
    struct net *net,
    const struct fib_config *cfg)
{
    return jhash_2words(
        (__force u32)cfg->fc_prefsrc,
        cfg->fc_priority,
        fib_info_hash_secret) % fib_info_hash_size;
}

/* 삽입 시: 동일 fib_info가 이미 존재하는지 확인 */
fib_create_info()
{
    /* 1. 새 fib_info 구성 */
    fi = kzalloc(fib_info_size(cfg), GFP_KERNEL);
    /* nexthop, protocol, scope 등 설정 */

    /* 2. 해시 테이블에서 동일 fi 검색 */
    ofi = fib_find_info(fi);
    if (ofi) {
        /* 기존 fi 발견 → 참조 카운트 증가 후 재사용 */
        fib_info_put(fi);  /* 새로 만든 것 해제 */
        fi = ofi;
        refcount_inc(&fi->fib_clntref);
        return fi;
    }

    /* 3. 새 fi를 해시 테이블에 등록 */
    hlist_add_head(&fi->fib_hash, &fib_info_hash[hash]);
    return fi;
}

fib_info 공유 조건

커널 버전별 주요 변경사항

LC-Trie 관련 커널 소스의 주요 변경을 버전별로 정리합니다.

주요 리팩토링: tnode/leaf 통합 (v3.14)

/* Before (v3.13 이전): tnode와 leaf이 별도 구조체 */
struct tnode {
    t_key key;
    unsigned char pos;
    unsigned char bits;
    unsigned int full_children;
    unsigned int empty_children;
    struct rcu_head rcu;
    union { struct work_struct work; struct tnode *tnode_free; };
    struct rt_trie_node __rcu *child[0];
};
struct leaf {
    t_key key;
    struct hlist_head list;      /* fib_alias 리스트 */
    struct rcu_head rcu;
};

/* After (v3.14+): key_vector로 통합 */
struct key_vector {
    t_key key;
    unsigned char pos;
    unsigned char bits;    /* bits==0 이면 leaf */
    unsigned char slen;
    union {
        struct key_vector __rcu *tnode[0];
        struct hlist_head leaf;
    };
};
/* 장점: 코드 단순화, IS_TNODE/IS_LEAF 매크로 통합,
 *        캐시 효율 개선 (동일 캐시 라인) */

resilient nexthop groups (v5.13)

/* 기존 ECMP: nexthop 추가/제거 시 전체 플로우 리해싱 */
/* 문제: 서버 1대 제거 시 나머지 모든 연결이 재배분됨 */

/* resilient: 고정 해시 슬롯 테이블 */
$ ip nexthop add id 100 group 1/2/3 type resilient buckets 128
/* 128개 슬롯을 3개 nexthop에 균등 배분
 * 슬롯: [1,2,3,1,2,3,...,1,2,3,1,2] */

/* nexthop 3 제거 시: */
$ ip nexthop replace id 100 group 1/2 type resilient
/* 슬롯 3이었던 것만 1 또는 2로 재배분
 * 나머지 슬롯은 변경 없음 → 기존 연결 유지!
 * [1,2,→1,1,2,→2,...] */

/* 슬롯 상태 확인 */
$ ip nexthop bucket show id 100
id 100 index 0 idle_time 3.52 nhid 1
id 100 index 1 idle_time 3.52 nhid 2
id 100 index 2 idle_time 0.84 nhid 1  ← 재배분됨
...

BPF fib_lookup과 XDP 가속

eBPF 프로그램에서 bpf_fib_lookup() 헬퍼를 호출하면 LC-Trie에 직접 LPM 검색을 수행합니다. XDP 경로에서 sk_buff 할당, netfilter, conntrack을 모두 우회하여 일반 IP 포워딩 대비 5~50배 성능 향상이 가능합니다.

실전 시나리오별 분석

LC-Trie의 실제 동작은 배포 환경에 따라 크게 달라집니다. 소규모 서버(경로 10~50개)에서는 깊이 2~3의 작은 트라이가 L1 캐시에 들어가고, 컨테이너 호스트(100~10K개)에서는 Pod 생성/삭제에 따른 빈번한 resize가 발생하며, BGP 라우터(100만+)에서는 NUMA 배치와 nexthop 오브젝트 공유가 핵심 최적화입니다.

고급 디버깅 기법

LC-Trie의 내부 상태를 심층적으로 분석하는 고급 디버깅 기법을 정리합니다.

crash 도구로 트라이 직접 분석

# crash(kdump 분석 도구)로 LC-Trie 노드 직접 검사
crash> struct fib_table.tb_data ffff8881234abcde
  tb_data = 0xffff8881234abce0

crash> struct key_vector 0xffff8881234abce0
  key = 0x00000000
  pos = 24
  bits = 8
  slen = 32

# 자식 배열 확인 (bits=8 → 256 슬롯)
crash> rd -64 0xffff8881234abce0+0x10 256 | grep -v "0000000000000000"
ffff888123500000  ← [10] = 10.x.x.x 서브트리
ffff888123600000  ← [172] = 172.x.x.x 서브트리
ffff888123700000  ← [192] = 192.x.x.x 서브트리

# 리프 노드의 fib_alias 확인
crash> struct key_vector 0xffff888123500100
  key = 0x0a010200     ← 10.1.2.0
  pos = 0
  bits = 0              ← 리프
  slen = 24
  leaf.first = 0xffff888123500200

crash> struct fib_alias 0xffff888123500200
  fa_list = {...}
  fa_info = 0xffff888123500300
  fa_slen = 8            ← 32 - 24 = 8 (접두사 길이 24)
  fa_tos = 0
  fa_type = 1            ← RTN_UNICAST
  fa_state = 0

BPF 기반 실시간 관찰

# bpftrace로 fib_table_lookup 성능 측정
$ bpftrace -e '
kprobe:fib_table_lookup {
    @start[tid] = nsecs;
}
kretprobe:fib_table_lookup /@start[tid]/ {
    @ns = hist(nsecs - @start[tid]);
    delete(@start[tid]);
}
interval:s:10 { exit(); }
'
@ns:
[64, 128)         1234 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@      |
[128, 256)         567 |@@@@@@@@@@@@@@                      |
[256, 512)          89 |@@                                  |
[512, 1K)           12 |                                    |

# backtrace 빈도 추적
$ bpftrace -e '
kprobe:fib_table_lookup {
    @lookup = count();
}
' -c 'sleep 10'
# 초당 fib_table_lookup 호출 횟수 확인

# 특정 목적지에 대한 검색 추적
$ bpftrace -e '
tracepoint:fib:fib_table_lookup {
    if (args->dst == 0x0A010264) {  /* 10.1.2.100 */
        printf("table=%d result=%s\n", args->tb_id,
               str(args->err == 0 ? "found" : "miss"));
    }
}'

systemtap으로 트라이 깊이 프로파일링(Profiling)

#!/usr/bin/stap
# LC-Trie 검색 깊이 분포 측정

global depth_hist

probe kernel.function("fib_table_lookup") {
    depth_hist[0] = 0  /* 초기화 */
}

/* get_child_rcu 호출 횟수 = 트라이 깊이 */
probe kernel.function("get_child_rcu").return {
    depth_hist[tid()]++
}

probe kernel.function("fib_table_lookup").return {
    d = depth_hist[tid()]
    @depth = hist(d)
    delete depth_hist[tid()]
}

probe timer.s(30) { exit() }

관련 문서

관련 커널 설정

관련 sysctl 파라미터

• Radix Tree -- LC-Trie의 기반인 Patricia trie와 커널의 radix tree 구현
• 해시 테이블 -- fib_info 해시, nexthop 해시 등 라우팅 내부의 해시 활용
• 네트워킹 기초 -- 소켓, sk_buff, 네트워크 스택 개요
• XDP/eBPF -- BPF 기반 라우팅 우회 및 가속
• RCU -- LC-Trie 검색의 lock-free 보장 메커니즘
• 메모리 관리(Memory Management) -- kmalloc/kvmalloc tnode 할당 전략

참고 자료

• net/ipv4/fib_trie.c — Bootlin Elixir — LC-Trie(FIB Trie)의 핵심 구현체로, trie 삽입·삭제·검색·리밸런싱(inflate/halve) 로직이 포함되어 있습니다.
• include/net/ip_fib.h — Bootlin Elixir — FIB 테이블, fib_alias, fib_info 등 라우팅 서브시스템의 핵심 자료 구조가 정의되어 있습니다.
• net/ipv4/fib_semantics.c — Bootlin Elixir — fib_info 할당·해시·해제 등 FIB 항목의 의미론적 처리를 담당하는 소스입니다.
• net/ipv4/fib_lookup.h — Bootlin Elixir — FIB 검색 관련 내부 헤더로, fib_alias 구조체 등이 정의되어 있습니다.
• IP-address Lookup Using LC-Tries (Nilsson & Karlsson, 1999) — LC-Trie의 원본 논문으로, 경로 압축(Path Compression)과 레벨 압축(Level Compression)의 이론적 기반을 제시합니다.
• LWN.net — The FIB TRIE — 리눅스 커널에서 해시 기반 FIB를 LC-Trie로 대체한 과정과 설계 철학을 설명하는 LWN 기사입니다.
• LWN.net — Routing table changes — FIB 테이블의 구조 변경 및 최적화에 관한 LWN 기사입니다.
• Linux Kernel Documentation — IP Sysctl — FIB 멀티패스 해시 정책, 역경로 필터링 등 라우팅 관련 sysctl 파라미터의 공식 문서입니다.
• Linux Kernel Documentation — FIB Trie — /proc/net/fib_trie, /proc/net/fib_triestat의 출력 형식과 해석 방법을 설명하는 공식 문서입니다.
• IPv4 route lookup on Linux (Vincent Bernat) — 리눅스 커널의 IPv4 라우팅 검색 과정을 LC-Trie 구조와 함께 상세히 분석한 블로그 글입니다.
• The Linux Kernel FIB Trie (Code Capsule) — FIB Trie의 내부 구조와 inflate/halve 알고리즘을 코드 수준에서 해설한 블로그 글입니다.