目录

1. 数据结构背景
2. 关键数据结构
3. 核心逻辑详解

数据结构背景

• Trie 结构：Linux^[1] 使用压缩 Trie（也称“LC-trie”变种）存储路由前缀。
• 每个节点是  struct key_vector。内部节点（非叶子）包含子节点指针数组 tnode[]。
• 叶子节点（IS_LEAF(n) 为真）包含一个 hlist 的 fib_alias，每个 fib_alias 对应一条具有相同前缀但不同 TOS/Type 的路由。
• key = ntohl(flp->daddr)：将网络字节序的目标 IP 转为主机字节序的 32 位整数，作为 Trie 查找键。
• 为了便于理解，可以把Trie想像成一个压缩的二叉树，正常的二叉树，每个中间节点只表示一位，要么是0，要么是1，但是Trie的中间节点可以包含多个值，比如1011，它表示与1011相同前缀的路由可以从此节点的子节点下找。
• 每个中间节点n->key的掩码长度32 - n->pos - n->bits，因此(key ^ n->key)>>n->pos表示节点n对应的n->bits子节点索引 ，叶子节点key的掩码长度是32 - n->slen。

关键数据结构

structkey_vector { t_key key;   //该节点代表的前缀（主机序）unsignedchar pos;  // 该节点从第 pos 位开始分叉（0~31）,即从高往低unsignedchar bits;  //本次分叉使用 bits 位，（即子节点数 = 2^bits）unsignedchar slen;     // 32-掩码长度，即子网掩码剩余的长度union {/* This list pointer if valid if (pos | bits) == 0 (LEAF) */structhlist_headleaf;//叶子节点/* This array is valid if (pos | bits) > 0 (TNODE) */structkey_vector __rcu *tnode[0];//中间节点 };};

核心逻辑详解

fib_table_insert是向压缩 Trie 插入新路由节点的核心函数，它首先以key为前缀，从trie树的根节点开始，调用fib_find_node查找与key进行最长匹配的路由信息。初次添加路由时，fib_find_node返回为NULL,tp返回与key最长匹配的父节点。接着它会调用fib_insert_alias->fib_insert_node来进行真正的插入。

intfib_table_insert(struct net *net, struct fib_table *tb,       struct fib_config *cfg, struct netlink_ext_ack *extack){structtrie *t = (structtrie *)tb->tb_data;structfib_alias *fa, *new_fa;structkey_vector *l, *tp; u16 nlflags = NLM_F_EXCL;structfib_info *fi; u8 plen = cfg->fc_dst_len; u8 slen = KEYLENGTH - plen; u8 tos = cfg->fc_tos; u32 key;int err; key = ntohl(cfg->fc_dst);if (!fib_valid_key_len(key, plen, extack))return -EINVAL; pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen); fi = fib_create_info(cfg, extack);if (IS_ERR(fi)) {  err = PTR_ERR(fi);goto err; } l = fib_find_node(t, &tp, key); fa = l ? fib_find_alias(&l->leaf, slen, tos, fi->fib_priority,    tb->tb_id, false) : NULL; ………… nlflags |= NLM_F_CREATE; err = -ENOBUFS; new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);if (!new_fa)goto out; new_fa->fa_info = fi;//fi 表示路由信息，里面包含路由类型,下一跳等信息 new_fa->fa_tos = tos; new_fa->fa_type = cfg->fc_type; new_fa->fa_state = 0; new_fa->fa_slen = slen;//  32 - 掩码长度 new_fa->tb_id = tb->tb_id; new_fa->fa_default = -1; new_fa->offload = 0; new_fa->trap = 0;/* Insert new entry to the list. */ err = fib_insert_alias(t, tp, l, new_fa, fa, key);//插入核心流程if (err)goto out_free_new_fa; …………succeeded:return0;out_remove_new_fa: fib_remove_alias(t, tp, l, new_fa);out_free_new_fa: kmem_cache_free(fn_alias_kmem, new_fa);out: fib_release_info(fi);err:return err;}

fib_insert_node 插入过程：

• 生成叶子节点l。
• 根据 tp->pos 和 tp->bits，从 key 中提取对应位作为子索引，获取 tp->tnode[idx] 指向的子节点 n。此时 n 可能是NULL，该槽位空，可直接插入叶子。如果n不为空，则说明新生成的叶子节点与n可以提取共同的前缀，然后将共同的前缀key赋值给新生成的节点tn。n与l成为tn的两个子节点，tp成为tn的父节点。
• 调用node_push_suffix将叶子节点的剩余掩码长度(slen)冒泡到所有父节点中，方便以后路由查询时进行回溯。
• 调用trie_rebalance进行压缩或展开，可以忽略，对于理解trie树没有帮助。

staticintfib_insert_node(struct trie *t, struct key_vector *tp,      struct fib_alias *new, t_key key){structkey_vector *n, *l; l = leaf_new(key, new);//生成路由叶子节点if (!l)goto noleaf;/* retrieve child from parent node */ n = get_child(tp, get_index(key, tp));/* Case 2: n is a LEAF or a TNODE and the key doesn't match.  *  *  Add a new tnode here  *  first tnode need some special handling  *  leaves us in position for handling as case 3  */if (n) {structkey_vector *tn;  tn = tnode_new(key, __fls(key ^ n->key), 1);if (!tn)goto notnode;/* initialize routes out of node */  NODE_INIT_PARENT(tn, tp);  put_child(tn, get_index(key, tn) ^ 1, n);/* start adding routes into the node */  put_child_root(tp, key, tn);  node_set_parent(n, tn);/* parent now has a NULL spot where the leaf can go */  tp = tn; }/* Case 3: n is NULL, and will just insert a new leaf */ node_push_suffix(tp, new->fa_slen); NODE_INIT_PARENT(l, tp); put_child_root(tp, key, l); trie_rebalance(t, tp);return0;notnode: node_free(l);noleaf:return -ENOMEM;}

参考资料