fib data struct

综述

fib tie是一个多叉树。其原理可以简化为：
根据前缀每一位是0还是1， 决定走左子树还是右子树。
绝大部分路由树，都没有那么多条目路由，所以再优化下，

  1. 多个联系节点只有一个子树,如
    仅有两条路由：8.8.2.0/24和8.8.3.0/24, 前面16+6位都完全一样。
  2. 多级子树转换成一个节点下多个孩子。
    仅有5条路由：
1
2
3
4
5
8.8.4.0/24
8.8.5.0/24
8.8.6.0/24
8.8.7.0/24
8.8.8.0/24

这就催生了Fib compress tree的产生。

fib data struct overview

fib Trie 节点类型

  1. Trie：是个多叉树。
  2. Tnode/key vector: 每个树节点是个,包含两个关键信息
    • 前缀： 前缀相同继续找孩子。前缀不同，则回溯。
    • 孩子： 前缀相同，根据指定区域位的值，继续在子树里查找。
  3. Leaf:
    • 每个叶子节点是路由终点，但不是对应路由条目。
    • 每个叶子节点有一个FA节点链在一起的list链。
  4. Fib alias:
    • 每个Fib info对应一条路由。
  5. Fib info： 与fib alias一一对应？
  6. Fib nh:
    • 对应每条路由下的每个下一跳。
    • ECMP场景下，会有多个下一跳。

fib data struct overview

Fib Trie 查找逻辑：

  1. 根据目的IP地址，从Trie树根节点开始查找。
  2. 遍历每个节点
    • 如果前缀不相同，回溯上级节点，查找其他膝兄弟节点
    • 如果前缀相同， 查找孩子节点(子树)
  3. 到达叶子节点:
    遍历FA， 查找最长路径匹配。

TODO：

  • 哪些场景需要回溯
  • 如何回溯。

节点类型

trie

1
2
3
4
5
6
167 struct trie {
168         struct key_vector kv[1];
169 #ifdef CONFIG_IP_FIB_TRIE_STATS
170         struct trie_use_stats __percpu *stats;
171 #endif
172 };

fib trie的入口节点，自带一个根节点kv[1]。

1
struct key_vector kv[1];

tnode

1
2
3
4
5
6
7
8
134 struct tnode {
135         struct rcu_head rcu;
136         t_key empty_children;           /* KEYLENGTH bits needed */
137         t_key full_children;            /* KEYLENGTH bits needed */
138         struct key_vector __rcu *parent;
139         struct key_vector kv[1];
140 #define tn_bits kv[0].bits
141 };

【AI总结】tnode 是 key_vector 的”管理外壳”。
empty_children 和 full_children 这两个计数器实时追踪子节点的填充状态，
让 resize() 能快速判断是否需要 inflate（扩大扇出）、halve（缩小扇出）或 collapse（合并节点）。
查找热路径完全绕开 tnode，只在 key_vector 层面操作。
注：只有中间节点有tnode， Leaf节点是纯key_vector.

key_vector

1
2
3
4
5
6
7
8
9
10
11
12
121 struct key_vector {
122         t_key key;
123         unsigned char pos;              /* 2log(KEYLENGTH) bits needed */
124         unsigned char bits;             /* 2log(KEYLENGTH) bits needed */
125         unsigned char slen;
126         union {
127                 /* This list pointer if valid if (pos | bits) == 0 (LEAF) */
128                 struct hlist_head leaf;
129                 /* This array is valid if (pos | bits) > 0 (TNODE) */
130                 DECLARE_FLEX_ARRAY(struct key_vector __rcu *, tnode);
131         };
132 };

key_vector 是fib路由的核心数据结构。
【中间节点】

  • key：路由前缀
  • pos+bits：从pos开始的bits， 根据数值/下标，去key_vector数组里去找child/子树
  • slen：子树中最大的后缀长度 (32-plen) max(pos, 子树中最大的 slen)
  • struct key_vector *tnode：

kv_28c5 tnode and leaf

【叶子】

  • Leaf链接相同前缀的所有路由Fib alias。
  • pos = 0
  • bit = 0
  • slen：挂载路由的最大(fa_slen)

fib_alias

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct fib_alias {
    struct hlist_node   fa_list;        // 链表节点
    struct fib_info     *fa_info;       // 指向路由详细信息
    dscp_t              fa_dscp;        // DSCP 匹配条件
    u8                  fa_type;        // 路由类型, local，broadcast等
    u8                  fa_state;       // 状态标记
    u8                  fa_slen;        // 后缀长度 = 32 - prefix_len
    u32                 tb_id;          // 路由表 ID
    s16                 fa_default;     // 默认路由选择索引
    u8                  offload;        // 硬件卸载标记
    u8                  trap;           // 硬件 trap 标记
    u8                  offload_failed; // 硬件卸载失败标记
    struct rcu_head     rcu;            // RCU 延迟释放
};

例:一个Leaf下有三条不同掩码和table的路由。

1
2
3
192.168.1.1/32, local表
192.168.1.0/24, main表
192.168.0.0/16, main表

fa_slen从小到大排序（前缀越长越靠前），查找时优先匹配最长前缀。

1
2
3
4
5
6
7
8
9
10
11
12
Leaf (key_vector, bits=0)
  │
  └── leaf (hlist_head)
        │
        ├── fib_alias [fa_slen=0,  tb_id=255]  ──→ fib_info ──→ fib_nh[]
        │   (192.168.1.1/32, local表)
        │
        ├── fib_alias [fa_slen=8,  tb_id=254]  ──→ fib_info ──→ fib_nh[]
        │   (192.168.1.0/24, main表)
        │
        └── fib_alias [fa_slen=16, tb_id=254]  ──→ fib_info ──→ fib_nh[]
            (192.168.0.0/16, main表)

fa_state:
目前就是一个 1-bit 的 “脏标记”.
核心目的是：在路由变更时，避免对从未使用过的路由执行不必要的缓存刷新。
目前只用了 bit 0（FA_S_ACCESSED）。

fib_info

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
struct fib_info {
    struct hlist_node   fib_hash;       // 全局 fib_info 哈希表节点（按路由属性去重）
    struct hlist_node   fib_lhash;      // local地址哈希表节点（按 fib_prefsrc 索引）
    struct list_head    nh_list;        // 挂载到 nexthop->fi_list，用于 nexthop 更新时遍历
    struct net          *fib_net;       // 所属 netname space
    refcount_t          fib_treeref;    // Trie 树引用计数（fib_alias 引用）
    refcount_t          fib_clntref;    // 外部引用计数（路由缓存等）
    unsigned int        fib_flags;      // 路由标志, 如 RTNH_F_DEAD, RTNH_F_ONLINK
    unsigned char       fib_dead;       // 标记路由已删除，阻止新引用
    unsigned char       fib_protocol;   // 路由来源协议, 如 RTPROT_STATIC, RTPROT_BOOT
    unsigned char       fib_scope;      // 路由作用域, 如 RT_SCOPE_LINK, RT_SCOPE_UNIVERSE
    unsigned char       fib_type;       // 路由类型, 如 RTN_UNICAST, RTN_LOCAL
    __be32              fib_prefsrc;    // 首选源地址（src hint）
    u32                 fib_tb_id;      // 路由表 ID, main,local or 其他
    u32                 fib_priority;   // 路由优先级（metric）
    struct dst_metrics  *fib_metrics;   // 路由度量指标（MTU, MSS, RTT等）
#define fib_mtu fib_metrics->metrics[RTAX_MTU-1]
#define fib_window fib_metrics->metrics[RTAX_WINDOW-1]
#define fib_rtt fib_metrics->metrics[RTAX_RTT-1]
#define fib_advmss fib_metrics->metrics[RTAX_ADVMSS-1]
    int                 fib_nhs;        // 下一跳数量（ECMP 场景 >1）
    bool                fib_nh_is_v6;   // 下一跳是否为 IPv6 地址
    bool                nh_updated;     // nexthop 对象更新标记，触发路由重新评估
    bool                pfsrc_removed;  // 首选源地址被删除标记
    struct nexthop      *nh;            // 新版 nexthop 对象指针（与 fib_nh[] 互斥）
    struct rcu_head     rcu;            // RCU 延迟释放
    struct fib_nh       fib_nh[];       // 下一跳数组（传统模式, 长度 = fib_nhs）
};

fib_nh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
107 struct fib_nh {
108         struct fib_nh_common    nh_common;
109         struct hlist_node       nh_hash;
110         struct fib_info         *nh_parent;
111 #ifdef CONFIG_IP_ROUTE_CLASSID
112         __u32                   nh_tclassid;
113 #endif
114         __be32                  nh_saddr;
115         int                     nh_saddr_genid;
116 #define fib_nh_family           nh_common.nhc_family
117 #define fib_nh_dev              nh_common.nhc_dev
118 #define fib_nh_dev_tracker      nh_common.nhc_dev_tracker
119 #define fib_nh_oif              nh_common.nhc_oif
120 #define fib_nh_flags            nh_common.nhc_flags
121 #define fib_nh_lws              nh_common.nhc_lwtstate
122 #define fib_nh_scope            nh_common.nhc_scope
123 #define fib_nh_gw_family        nh_common.nhc_gw_family
124 #define fib_nh_gw4              nh_common.nhc_gw.ipv4
125 #define fib_nh_gw6              nh_common.nhc_gw.ipv6
126 #define fib_nh_weight           nh_common.nhc_weight
127 #define fib_nh_upper_bound      nh_common.nhc_upper_bound
128 };