Documentation/networking/fib_trie.rst

Source file repositories/reference/linux-study-clean/Documentation/networking/fib_trie.rst

File Facts

System
Linux kernel
Corpus path
Documentation/networking/fib_trie.rst
Extension
.rst
Size
5973 bytes
Lines
150
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

.. 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.

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

Annotation

Implementation Notes