summaryrefslogtreecommitdiffstats
path: root/Documentation/networking/fib_trie.txt
diff options
context:
space:
mode:
authorMauro Carvalho Chehab <mchehab+huawei@kernel.org>2020-04-28 00:01:35 +0200
committerDavid S. Miller <davem@davemloft.net>2020-04-28 23:39:46 +0200
commitaee113427c5d205730b2c1a023661799f41aca23 (patch)
treef5e4ccfe241bf33d70f3e0d18e89fba5358efee0 /Documentation/networking/fib_trie.txt
parentdocs: networking: convert eql.txt to ReST (diff)
downloadlinux-aee113427c5d205730b2c1a023661799f41aca23.tar.xz
linux-aee113427c5d205730b2c1a023661799f41aca23.zip
docs: networking: convert fib_trie.txt to ReST
- add SPDX header; - adjust title markup; - adjust identation, whitespaces and blank lines; - add to networking/index.rst. Signed-off-by: Mauro Carvalho Chehab <mchehab+huawei@kernel.org> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'Documentation/networking/fib_trie.txt')
-rw-r--r--Documentation/networking/fib_trie.txt145
1 files changed, 0 insertions, 145 deletions
diff --git a/Documentation/networking/fib_trie.txt b/Documentation/networking/fib_trie.txt
deleted file mode 100644
index fe719388518b..000000000000
--- a/Documentation/networking/fib_trie.txt
+++ /dev/null
@@ -1,145 +0,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.
-
-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.)
-
-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.
-
-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.
-
-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().