LC-trie implementation notes

노드 유형

LC-trie에는 `leaf`와 `trie node` 또는 `tnode`라는 두 종류의 노드가 있습니다. `leaf`는 관련 키의 사본과 라우팅 테이블 항목을 접두사 길이순으로 정렬한 `hlist`를 가진 종단 노드이며, `struct leaf`와 `struct leaf_info`가 이를 나타냅니다.

`tnode`는 자식 `leaf` 또는 `tnode` 포인터 배열을 가진 내부 노드입니다. 키의 일부 비트를 배열 인덱스로 사용하며, 이 배열 구조가 뒤에서 설명하는 레벨 압축의 기반이 됩니다.

.. SPDX-License-Identifier: GPL-2.0

============================
LC-trie implementation notes
============================

Node types
----------
leaf
        An end node with data. This has a copy of the relevant key, along
        with 'hlist' with routing table entries sorted by prefix length.
        See struct leaf and struct leaf_info.

trie node or tnode
        An internal node, holding an array of child (leaf or tnode) pointers,
        indexed        through a subset of the key. See Level Compression.

경로 압축과 레벨 압축

`bits`는 자식 배열 인덱스를 만들 때 사용하는 키 구간의 비트 수이고, `pos`는 그 구간이 키에서 시작하는 위치입니다. 부모의 `pos + bits`와 자식의 `pos`가 바로 이어지지 않으면 그 사이 비트는 분기 없는 단일 경로이므로 생략할 수 있습니다. 이것이 경로 압축입니다. 검색은 생략된 비트를 건너뛰므로 마지막에 `leaf`에 보관한 전체 키로 실제 일치 여부를 확인해야 합니다.

레벨 압축은 가득 찬 자식 노드의 자식을 한 레벨 위로 올려 이진 트리를 더 넓은 자식 배열로 바꿉니다. 반대로 배열 대부분이 비어 있으면 배열을 절반으로 줄이고 일부 자식을 한 레벨 아래로 내립니다. 이 두 방향의 조정으로 배열이 끝없이 커지는 것을 막으면서 트리를 레벨 균형 상태로 유지합니다.

`empty_children`은 자식 배열에서 `NULL`인 위치의 수입니다. `full_children`은 경로 압축되지 않은 자식, 즉 `NULL`이나 `leaf`가 아니면서 자식의 `pos`가 현재 `tnode`의 `pos + bits`와 같은 자식의 수입니다. 여기서 `full`은 빈 상태의 반대라기보다 경로가 완전하게 이어진다는 뜻입니다.

A few concepts explained
------------------------
Bits (tnode)
        The number of bits in the key segment used for indexing into the
        child array - the "child index". See Level Compression.

Pos (tnode)
        The position (in the key) of the key segment used for indexing into
        the child array. See Path Compression.

Path Compression / skipped bits
        Any given tnode is linked to from the child array of its parent, using
        a segment of the key specified by the parent's "pos" and "bits"
        In certain cases, this tnode's own "pos" will not be immediately
        adjacent to the parent (pos+bits), but there will be some bits
        in the key skipped over because they represent a single path with no
        deviations. These "skipped bits" constitute Path Compression.
        Note that the search algorithm will simply skip over these bits when
        searching, making it necessary to save the keys in the leaves to
        verify that they actually do match the key we are searching for.

Level Compression / child arrays
        the trie is kept level balanced moving, under certain conditions, the
        children of a full child (see "full_children") up one level, so that
        instead of a pure binary tree, each internal node ("tnode") may
        contain an arbitrarily large array of links to several children.
        Conversely, a tnode with a mostly empty        child array (see empty_children)
        may be "halved", having some of its children moved downwards one level,
        in order to avoid ever-increasing child arrays.

empty_children
        the number of positions in the child array of a given tnode that are
        NULL.

full_children
        the number of children of a given tnode that aren't path compressed.
        (in other words, they aren't NULL or leaves and their "pos" is equal
        to this        tnode's "pos"+"bits").

        (The word "full" here is used more in the sense of "complete" than
        as the opposite of "empty", which might be a tad confusing.)

주요 함수

코드 구조는 검증과 검토를 쉽게 하려고 가능한 한 `fib_hash`와 비슷하게 유지되었습니다. `fib_find_node()`는 단순한 trie 검색을 구현하므로 코드를 이해하기 좋은 출발점입니다. `fib_insert_node()`는 새 `leaf`를 삽입한 뒤 필요하면 일부 trie에 레벨 압축을 적용하고, `trie_leaf_remove()`는 키를 찾아 삭제한 뒤 다시 레벨 압축을 수행합니다.

`trie_rebalance()`는 변경된 `tnode`에서 루트 방향으로 올라가며 각 단계에서 `resize()`를 호출하는 동적 trie의 핵심 재구성 함수입니다. `resize()`는 최적 레벨 압축 기준을 만족할 때까지 자식 배열을 반복해서 팽창하거나 축소합니다. `inflate()`는 배열 크기를 두 배로 늘리고 `halve()`는 그 역으로 절반으로 줄입니다. 이 부분은 원래 LC-trie 논문을 비교적 충실히 따릅니다.

`fn_trie_insert()`, `fn_trie_delete()`, `fn_trie_select_default()`는 `fib_hash`의 대응 함수와 유사한 경로 조작 함수입니다. `fn_trie_flush()`는 `nextleaf()`로 전체 trie를 순회하며 비어 있는 leaf를 제거합니다. `fn_trie_dump()`는 접두사 길이순으로 라우팅 테이블을 출력하지만, 접두사 길이마다 전체 trie를 걸어야 하므로 길이별 zone/hash를 가진 `fib_hash`보다 다소 느립니다.

Comments
---------

We have tried to keep the structure of the code as close to fib_hash as
possible to allow verification and help up reviewing.

fib_find_node()
        A good start for understanding this code. This function implements a
        straightforward trie lookup.

fib_insert_node()
        Inserts a new leaf node in the trie. This is bit more complicated than
        fib_find_node(). Inserting a new node means we might have to run the
        level compression algorithm on part of the trie.

trie_leaf_remove()
        Looks up a key, deletes it and runs the level compression algorithm.

trie_rebalance()
        The key function for the dynamic trie after any change in the trie
        it is run to optimize and reorganize. It will walk the trie upwards
        towards the root from a given tnode, doing a resize() at each step
        to implement level compression.

resize()
        Analyzes a tnode and optimizes the child array size by either inflating
        or shrinking it repeatedly until it fulfills the criteria for optimal
        level compression. This part follows the original paper pretty closely
        and there may be some room for experimentation here.

inflate()
        Doubles the size of the child array within a tnode. Used by resize().

halve()
        Halves the size of the child array within a tnode - the inverse of
        inflate(). Used by resize();

fn_trie_insert(), fn_trie_delete(), fn_trie_select_default()
        The route manipulation functions. Should conform pretty closely to the
        corresponding functions in fib_hash.

fn_trie_flush()
        This walks the full trie (using nextleaf()) and searches for empty
        leaves which have to be removed.

fn_trie_dump()
        Dumps the routing table ordered by prefix length. This is somewhat
        slower than the corresponding fib_hash function, as we have to walk the
        entire trie for each prefix length. In comparison, fib_hash is organized
        as one "zone"/hash per prefix length.

잠금

`fib_lock`은 `fib_hash`와 같은 방식의 읽기/쓰기 잠금으로 사용됩니다. 다만 다른 잠금 전략도 적용할 수 있도록 함수들이 어느 정도 분리되어 있습니다. 향후 `trie_rebalance()`를 RCU로 실행하면 `fn_trie_lookup()`의 `read_lock`을 피할 가능성도 있습니다.

Locking
-------

fib_lock is used for an RW-lock in the same way that this is done in fib_hash.
However, the functions are somewhat separated for other possible locking
scenarios. It might conceivably be possible to run trie_rebalance via RCU
to avoid read_lock in the fn_trie_lookup() function.

주 검색 메커니즘

주 검색 함수는 `fn_trie_lookup()`입니다. 먼저 `fib_find_node()`처럼 키 구간을 차례로 소비하며 trie를 내려가 `leaf`를 찾습니다. `check_leaf()`는 leaf 안에서 접두사 길이순으로 정렬된 `hlist`를 대상으로 `fib_semantic_match()`를 수행하며, 일치하면 검색이 끝납니다.

일치하지 않으면 키 길이에서 시작해 접두사 길이를 한 단계씩 줄이며 가장 긴 일치 접두사를 찾는 모드로 들어갑니다. 각 `tnode`에서는 자식 인덱스의 최하위 1비트를 차례로 0으로 만들며 일치하는 자식 또는 0 인덱스를 찾습니다. 더 이상 찾지 못하면 `t->stats.backtrack++`를 증가시키고 상위 trie로 되돌아가 키 일부를 계속 잘라 냅니다.

검색은 후보 하위 trie로 반복해서 내려갑니다. `HL_OPTIMIZE` 구간에는 일치할 수 없는 막다른 경로를 피하는 지름길이 구현되어 있습니다. 경로 선택의 정확성을 검증할 수 있도록 `NETLINK_FIB_LOOKUP` 연산이 추가되었으며, 사용자 공간에서 `fib_lookup()` 결과를 직접 확인할 수 있습니다.

Main lookup mechanism
---------------------
fn_trie_lookup() is the main lookup function.

The lookup is in its simplest form just like fib_find_node(). We descend the
trie, key segment by key segment, until we find a leaf. check_leaf() does
the fib_semantic_match in the leaf's sorted prefix hlist.

If we find a match, we are done.

If we don't find a match, we enter prefix matching mode. The prefix length,
starting out at the same as the key length, is reduced one step at a time,
and we backtrack upwards through the trie trying to find a longest matching
prefix. The goal is always to reach a leaf and get a positive result from the
fib_semantic_match mechanism.

Inside each tnode, the search for longest matching prefix consists of searching
through the child array, chopping off (zeroing) the least significant "1" of
the child index until we find a match or the child index consists of nothing but
zeros.

At this point we backtrack (t->stats.backtrack++) up the trie, continuing to
chop off part of the key in order to find the longest matching prefix.

At this point we will repeatedly descend subtries to look for a match, and there
are some optimizations available that can provide us with "shortcuts" to avoid
descending into dead ends. Look for "HL_OPTIMIZE" sections in the code.

To alleviate any doubts about the correctness of the route selection process,
a new netlink operation has been added. Look for NETLINK_FIB_LOOKUP, which
gives userland access to fib_lookup().