FIB Trie 路由动画演示

内核 FIB Trie 路由效果演示

通过动画展示下内核路由树(FIB trie)插入路由时，对应节点的变化。
👉 点击这里全屏查看动画
FIB Trie 路由树最终状态

FIB trie 介绍

linux内核里的fib路由树，

如何插入一个fib 路由

查找插入点

一句话：遍历当前节点，如果前缀相同，根据index值，递归找孩子(子树).

【关键点1】get_cindex计算index值

1
2
index = get_cindex(key, n);
// 展开: index = (key ^ n->key) >> n->pos
  • 异或运算后，然后右移pos位。保留（前缀+bits位)
    包含前缀运算

【关键点2】前缀检查：一石二鸟的判断
当前节点n和key的前缀是否一致。

n->bits表示该节点有2^bits个子节点，所以合法的index范围是[0, 2^bits)。如果index >= 2^bits，说明：
key和n->key在前缀部分就已经不同了（差异出现在pos+bits之上的高位）

换句话说：key不属于这个子树，前缀不匹配
备注：因为fib trie的根节点一定不为空。所以第一次算index值一定为0，不会出现前缀不匹配的场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
930 static struct key_vector *fib_find_node(struct trie *t,
931                                         struct key_vector **tp, u32 key)
932 {
933         struct key_vector *pn, *n = t->kv;
934         unsigned long index = 0;
935
936         do {
937                 pn = n;                          // 当前节点保存为父节点
938                 n = get_child_rcu(n, index);     // 根据index值，找孩子
939
940                 if (!n)                          // 孩子为空. 找到了 ==> case1：空的孩子节点（前缀相同的tnode，孩子节点为空）
941                         break;
942                                                  // 孩子非空, 深度+1
943                 index = get_cindex(key, n);      // 根据key和当前节点计算index值
944
...
959                 if (index >= (1ul << n->bits)) { // index越界：前缀不相同 ==> case2: 前缀不同的tnode节点
960                         n = NULL;
961                         break;
962                 }
963                                                  // index合理，继续下次循环
965         } while (IS_TNODE(n));                   //当前节点是叶子时候。 case3: 前缀相同的叶子。
966
967         *tp = pn;
968
969         return n;
970 }

场景1：当前一个节点的叶子

匹配条件：

  • 前缀相同。
  • index值对应的孩子节点指针为空
    处理方式：
  • 创建叶子节点，挂到当前节点的第index个孩子。
    例子：key: 9.9.0.0/16

场景2：前缀不同

匹配条件：

  • 前缀不相同。
  • index >= 2^bits：index值大于或者等于2的bits次方。

处理方式：

  • 创建一个新的中间节点
    • bit位置是根据前缀里不相同的位里，最高的一位。
    • 当前节点挂到中间节点，当孩子。
  • 创建一个叶子节点
    • 新叶子节点挂到中间节点，当孩子。
  • 中间节点，挂到父节点当孩子。
    例如：增加路由9.24.0.0/24

场景3：前缀相同的叶子节点

相同前缀，不同掩码长度的。
在叶子节点里，向FA list里增加fib_alias节点。
例如：9.9.8.0/30 dev veth0

执行插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
     /* fib_insert_alias - 将新的 fib_alias 插入到叶子节点的链表中
      *
      * @t:   trie 根
      * @tp:  父节点 (tnode)
      * @l:   叶子节点 (fib_find_node 找到的)，为 NULL 表示叶子不存在
      * @new: 待插入的 fib_alias
      * @fa:  精确匹配到的已有 fib_alias（同 slen + 同 tb_id + 同 tos + 同 priority），可为 NULL
      * @key: 路由前缀 key
      */
1154 static int fib_insert_alias(struct trie *t, struct key_vector *tp,
1155                             struct key_vector *l, struct fib_alias *new,
1156                             struct fib_alias *fa, t_key key)
1157 {
1158         if (!l)
1159                 return fib_insert_node(t, tp, new, key);  /* 场景1 & 场景2：叶子节点不存在，*/
1160
             /* === 以下是场景3：叶子节点已存在，往叶子的 fa_list 链表中插入 === */
1161         if (fa) { /* 精确匹配到已有 fa（替换/追加场景）：插到它前面*/
1162                 hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
1163         } else {
                     /* 没有精确匹配，需要按排序规则找到合适的插入位置
                      * 排序规则：
                      *   1) fa_slen 升序 (slen = 32 - prefixlen，slen 越小 = 掩码越长 = 越精确)
                      *   2) slen 相同时，tb_id 降序 (local 表 id=255 排在 main 表 id=254 前面) */
1164                 struct fib_alias *last;
1165
1166                 hlist_for_each_entry(last, &l->leaf, fa_list) {
1167                         if (new->fa_slen < last->fa_slen)
1168                                 break;
1169                         if ((new->fa_slen == last->fa_slen) &&
1170                             (new->tb_id > last->tb_id))
1171                                 break;           // 掩码相同，但 tb_id 更大，插到前面
1172                         fa = last;               // 继续往后找，fa 记录"插入点的前一个节点"
1173                 }
1174
1175                 if (fa)
1176                         hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);  // 插到 fa 后面
1177                 else
1178                         hlist_add_head_rcu(&new->fa_list, &l->leaf);        // 链表为空或应插到最前面
1179         }
1180
1181         if (l->slen < new->fa_slen) {  /* 如果新插入的 fa_slen 比叶子当前记录的 slen 更大（掩码更短），需要更新叶子的 slen，并向上传播 suffix 长度*/
1182                 l->slen = new->fa_slen;
1183                 node_push_suffix(tp, new->fa_slen);
1184         }
1185
1186         return 0;
1187 }