该篇笔记记录的是作者阅读代码后对路由表的结构以及查表过程的一些个人理解，记录在这里，以便以后回顾。
路由表的结构
在描述路由表的结构之前先看看路由的组成元素，一条路由包含很多的元素，稍微简化一下，大概包含下面这些：
[pre_val/pre_len] [table id] [tos] [priority] [scope] [src] [type] [nexthop]
pre_val: 前缀值
pre_len：前缀长度
table: 路由所属路由表的id
tos: tos，配置了tos的路由只会匹配带特定tos的ip报文
priority: 优先级，决定路由的排列顺序
scope: 路由的距离
src: 路由被命中后，若报文没有源地址（比如socket 绑定anyaddr）,则可能会使用src指定的地址作为源地址
type: 路由的类型，该类型影响路由查找后对报文的处理行为，可取值unicast | local | broadcast | multicast | throw | unreachable | prohibit | blackhole | nat
nexthop: 下一跳信息（出口设备、下一跳地址），可以通过dev/via/gateway/nexthop这些关键字添加
内核使用树+链表的形式来组织路由，如下所示：
每个路由表(fib_table)都会关联一棵前缀树(trie)，前缀树会随路由表的创建而创建，多个路由表之间也可能共享同一棵树。前缀树创建时，树上没有节点(key_vector)，随着路由的添加，树上的节点会逐渐增多。
从上图中可以看到，前缀树(trie)的每个叶子节点都连接着一个链表，链表上的每个fib_alias都代表着一条路由，叶子节点与路由是一对多的关系，路由具体会映射到哪个节点由它的前缀值来确定。
在叶子节点所连接的同一个链表上，路由(fib_alias)按照前缀长度从大到小的顺序排列，前缀长度相同的路由则按照路由表id从大到小的顺序排列，前缀长度和路由表id相同时则按照tos值从大到小的顺序排列，前缀长度、路由表id和TOS都相同的路由则按照优先级从高到低(priority值越小优先级越高)排列。
前缀树的构建过程
前缀树有根、枝干和叶子三种节点，内核使用struct key_vector来描述他们，struct key_vector的成员如下：
struct key_vector {
t_key key; // 节点的前缀值，根节点前缀值为0.0.0.0
unsigned char pos; // 叶子节点pos为0，枝干节点pos不为0， 根节点pos为32
unsigned char bits; // 叶子节点bits为0，枝干节点bits不为0
unsigned char slen; // 对于叶子节点而言slen是链接的fib_alias的最大slen，对于枝干节点而言slen是子节点的最大slen，根节点slen为32
union {
struct hlist_head leaf; // leaf是链接前缀值相同的路由（fib_alias）的链表头，leaf由叶子节点使用
struct key_vector __rcu *tnode[0]; // tnode[]是一个指针数组，用来存储子节点的地址，tnode[]由枝干节点和根节点使用
};
};
接下来通过一个例子来感受前缀树的构建过程以及节点key/pos/bits/slen等值的含义，稍微需要注意的是，内核使用slen来间接描述前缀长度(对于IPv4路由而言: slen = 32 - pre_len)
假设路由表一开始为空，给路由表添加了这样一条路由
// 1号路由
ip route add 1.0.0.0/8 dev eth1
此时的前缀树如下所示:
此时只有根节点和一个叶子节点，没有枝干节点，叶子节点的key值与路由的前缀值相同1.0.0.0，slen值为链表上路由(fib_alias)的最大slen，此时链表上只有一个fib_alias，所以叶子节点的slen为24。
假设又添加了一条路由
// 2号路由
ip route add 1.1.0.0/16 dev eth2
此时的前缀树如下所示:
这时产生了一个枝干节点A，它的key/pos/bit取值如下所示：
枝干节点的key值的[pos至bits - 31]这些比特位取自于子节点key值相同的部分，枝干节点key值的[0 至 pos+bits-1]这些比特位为0。
子节点key值从pos起的bits个比特位用于描述子节点在枝干节点中的位置，比如说上面例子中A节点pos为16，bits为1，B节点key值的第16位为0，所以节点B的地址就记录在A.tnode[0]，C节点key值的第16位为1，所以节点C的地址就记录在A.tnode[1]。
枝干节点刚创建时，它下面只会有两个子节点，所以枝干节点的bits初始值为1，pos初始值取决于子节点key值出现不同的位置，比如说B和C两个子节点key值从bit31到bit17是相同的，bit16不同，那A节点的pos初始值就是16。随着前缀树上节点的增多，前缀树会对节点的位置进行一些调整以平衡自身，pos值和bits值也会随着一起调整。
对于一个节点而言，[pos+bits 至 31]这些比特位是节点key值的有效部分，在添加路由的过程中，会使用待添加路由的前缀值与节点key值有效部分相比，若相同则认为待添加的路由的前缀值与节点匹配。根节点的pos为特殊值32，它与任何前缀值都是匹配的。
假设又添加了两条路由
// 3号路由
ip route add 1.0.0.0/24 dev eth3
// 4号路由
ip route add 1.1.1.0/24 dev eth4
添加3号路由时，它的前缀值与节点A的key值有效部分是相同的，3号路由和节点A能匹配上。3号路由的前缀值的bit16为0，而A.tnode[0]指向节点B，所以会进一步看3号路由与节点B是否匹配，3号路由的前缀值与节点B的key值有效部分相同，所以3号路由最终就映射到节点B上。在B节点所连接的链表上，3号路由前缀长度比1号路由前缀长度更长，所以3号排在1号前面。
添加4号路由时，它的前缀值与节点A的key值有效部分相同，故匹配。4号路由的[A.pos 至A.pos+A.bits - 1]这些比特位为1，而A.tnode[1]指向节点C，故继续比对节点C。节点C与4号路由不匹配， 这种情况下会给4号路由新建一个叶子节点，同时会新建一个枝干节点用来连接新的叶子节点和节点C，此时的前缀树如下所示：
节点E是为4号路由新建的叶子节点，节点D是新建的枝干节点，节点D的key值取自节点C和节点E的key值相同部分，节点C和节点E的key值从bit31到bit9是相同的，bit8开始出现不同，所以节点D的pos值为8。
假设又添加了一条路由
// 5号路由
ip route add 1.2.0.0/16 dev eth5
5号路由与节点A不匹配，所以会给5号路由新建一个叶子节点G，并在A前面新加一个枝干节点F用来连接节点A和节点G，如下所示：
可以发现节点B、D、G三个节点key值从bit31到bit18是相同的，bit17到bit16分别是00、01、10，这种情况下，前缀树会平衡自身，最终形成如下结构：
路由查表过程
使用目的ip来查表的过程大致有下面几个步骤：
步骤1： 从前缀树根节点开始，逐级比对目的ip与节点key值有效部分，直到找到完全匹配的叶子节点或者不匹配的节点(可能是叶子也可能是枝干)
1.1 若是完全匹配的叶子节点则进入步骤4
1.2 若不匹配则进入步骤2。
步骤2： 判断目的ip与节点key值的[slen至31]这些bit位是否相同，
2.1 若不同则进入步骤3
2.2 若相同则说明该节点上有可能有合适的路由(比如key=1.1.0.0 pos=8 bits=1 slen=16的枝干节点下有1.1.0.0/16的路由，目的ip 1.1.0.1虽然与枝干节点的key值不匹配但与路由1.1.0.0/16的前缀是匹配的)
2.2.1 若是该节点为叶子节点则进入步骤4
2.2.2 若该节点为枝干节点则移动到枝干节点下index为0的节点再执行步骤2，此时只有index为0的节点上才可能有合适的路由(比如枝干节点的key=1.1.0.0 pos=8 bits=1 slen=16，目的ip 1.1.0.1只可能与1.1.0.0/16,1.1.0.0/17,1.1.0.0/18…1.1.0.0/32这些路由匹配上，是不可与诸如1.1.1.0/8这样的路由匹配上的，1.1.0.0/16,1.1.0.0/17,1.1.0.0/18…1.1.0.0/32这些路由只可能位于index为0的节点上)。
步骤3： backtrace， 假设前缀树上某个枝干节点A和它的子节点如下所示，圆中心是它们的key值（为了方便描述，假设IP和key值长度只有6个bit）
假如某个IP为 111111，在步骤2中会命中节点B，假设节点B的type/scope这些参数不能满足此次路由查找的期望，此时会进入backtrace的流程。
3.1 对节点B执行backtrace，回到节点A，获取节点B在节点A下的index: old_index
3.2 尝试从节点A的其它子节点中选择一个，新选则的节点的index满足这个公式：new_index &= old_index - 1（试想一下，节点B的index是11，那么只有index为10、00的这两个节点有机会能够匹配上，这个公式保证了依次被选中的节点是11->10->00），C节点会被选中，选中新的节点后就再次进入步骤2的流程。C节点进入步骤2的流程中经过2.2.2步骤时会直接选择index为0的G节点。
3.3 假设C节点下的路由也不满足此次路由查找的期望，又执行backtrace选中节点E，节点E也不满足此次路由查找的期望，又执行backtrace，此时A节点下已经没有子节点可用，则对A节点执行backtrace，回到A的父节点，去A的父节点下查看其它子节点，若A的父节点是根节点，则路由查找失败
步骤4：
查看叶子节点的leaf链表上的路由的type/scope等值是否满足此次路由查找的期望，若满足则查找成功，若所有路由都不满足那就执行步骤3
基于前面五条路由构建出的前缀树来看个路由查找的例子。
假设有个目的ip为1.1.1.1报文进入了路由器，经过步骤1节点E会被选中，节点E的key值有效部分与1.1.1.1不能匹配进入步骤2。经过步骤2.2的判断后发现节点E上面可能有合适的路由(4号路由：1.1.1.0/24)故进入步骤4，如果4号路由的type/scope等值满足此次路由查找的期望那路由查找就成功了。假设4号路由的type/scope等值不满足此次路由查找的期望，执行步骤3，步骤3.2会选中节点C，如果节点C上的2号路由满足路由查找期望那路由查找就成功了。假设2号路由也不满足，那么又继续执行步骤3，接下来F节点被选中，然后是B节点被选中，若B节点也不满足路由查找的期望，最终会backtrace到根节点，路由查找就失败了。
代码流程
接下来看看添加路由和查找路由的代码
添加路由
应用层的ip route工具使用netlink将添加路由的请求传递到内核，使用的netlink命令是RTM_NEWROUTE，内核的inet_rtm_newroute 函数处理应用层的RTM_NEWROUTE请求, 它分为三个步骤，如下
// linux-5.4.246/net/ipv4/fib_frontend.c
inet_rtm_newroute
rtm_to_fib_config // 将netlink请求转存到struct fib_config类型的结构体变量中
fib_new_table // 查找目标路由表，路由表不存在时则创建新的路由表
fib_table_insert // 将路由插入路由表
处理应用层传递的参数
添加路由时，ip route会将一部分路由参数会封装到一个struct rtmsg类型的结构体中传递，一部分路由参数会以netlink attr的形式进行传递，struct rtmsg的结构和netlink attr的类型可以参考include/uapi/linux/rtnetlink.h文件。内核收到应用层新建路由的请求后会将应用层传递的参数转存到一个struct fib_config类型的结构体中，struct fib_config结构体成员如下:
// include/net/ip_fib.h
struct fib_config {
u8 fc_dst_len; // 前缀长度， 192.168.0.1/24-->fc_dst_len 24
u8 fc_tos; // tos， 默认0
u8 fc_protocol; // protocol ， 默认RTPROT_BOOT
u8 fc_scope; // scope, 默认RT_SCOPE_UNIVERSE
u8 fc_type; // 路由类型，默认 RTN_UNICAST
u8 fc_gw_family; // family, 默认AF_UNSPEC，通过via或者gateway参数指定下一跳后，该参数会被赋值
u32 fc_table; // 路由表 id, 默认RT_TABLE_MAIN
__be32 fc_dst; // 前缀值
union {
__be32 fc_gw4; // 当使用via或者gateway指定下一跳信息时，fc_gw4将存储下一跳地址
struct in6_addr fc_gw6;
};
int fc_oif; // 使用dev参数指定的出口设备
u32 fc_flags;
u32 fc_priority; // 路由的优先级
__be32 fc_prefsrc; // 命中该路由后优先使用的源地址
u32 fc_nh_id;
struct nlattr *fc_mx;
struct rtnexthop *fc_mp; // 当通过nexthop参数指定了多个下一跳时, fc_mp将指向装有下一跳信息的netlink attr
int fc_mx_len;
int fc_mp_len; // fc_mp的占用的空间
u32 fc_flow;
u32 fc_nlflags;
struct nl_info fc_nlinfo;
struct nlattr *fc_encap;
u16 fc_encap_type;
};
部分ip route参数与结构体成员的转化关系如下表所示:
ip routertmsgnetlink attrfib_configviaRTA_GATEWAYfc_gw4 fc_gw_family = AF_INETdevRTA_OIFfc_oifPREFIXrtm_dst_lenRTA_DSTfc_dst_len fc_dsttosrtm_tosfc_tosmetric/priority/preferenceRTA_PRIORITYfc_prioritysrcRTA_PREFSRCfc_prefsrcscopertm_scopefc_scopeonlinkrtm_flags |= RTNH_F_ONLINKfc_flagsnhidRTA_NH_IDfc_nh_idprotocolrtm_protocolfc_protocoltablertm_table(<256)RTA_TABLEfc_tabletypertm_typefc_typenexthopRTA_MULTIPATHfc_mp fc_mp_len查找目标路由表
内核使用struct fib_table来描述路由表，它的成员如下：
struct fib_table {
struct hlist_node tb_hlist; // 同一网络命名空间中的所有ipv4路由表都位于同一个hash表中，这个tb_hlist是链接到hash表的链表节点
u32 tb_id; // 路由表 id
int tb_num_default; // 路由表中路由的数目
struct rcu_head rcu;
unsigned long *tb_data; // 指向trie树的指针
unsigned long __data[0]; // 分配路由表时，如果不和其它路由表共享trie树，就会在fib_table尾部额外分配一个struct trie类型的结构变量结构体
};
struct trie {
struct key_vector kv[1]; // trie树的节点使用struct key_vector来描述，这里的kv[1]是根节点
#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats __percpu *stats;
#endif
};
fib_new_table会根据应用层指定的路由表id找到目标路由表，过程如下：
// // linux-5.4.246/net/ipv4/fib_frontend.c
// 入参id为路由表id,由ip route指定
struct fib_table *fib_new_table(struct net *net, u32 id)
{
struct fib_table *tb, *alias = NULL;
unsigned int h;
// 1 ip route指定没有指定路由表id,则使用main表
if (id == 0)
id = RT_TABLE_MAIN;
// 2 从net->ipv4.fib_table_hash指向的hash表去查找路由表,
tb = fib_get_table(net, id);
if (tb)
return tb; // 找到了则直接返回
// 3 没找到就新建路由表
// 3.1 当没有创建策略路由时，创建local表时会先创建main表，local表会和main表使用同一棵trie树
if (id == RT_TABLE_LOCAL && !net->ipv4.fib_has_custom_rules)
alias = fib_new_table(net, RT_TABLE_MAIN);
// 3.2 新建路由表
tb = fib_trie_table(id, alias); // 分配用于描述路由表的 struct fib_table结构体变量和用于描述前缀树的struct trie结构体变量，若alias不为空，则新建的路由表和alias共用trie树
if (!tb)
return NULL;
......
// 3.3 将新建的路由表放入hash表
h = id & (FIB_TABLE_HASHSZ - 1); // 数组下标取决于table id的低8位
hlist_add_head_rcu(&tb->tb_hlist, &net->ipv4.fib_table_hash[h]); // 将新建的路由表链入net->ipv4.fib_table_hash[h]
return tb;
}
将路由插入路由表合适位置
找到目标路由表后，接下来就是在路由表中找个合适的位置插入新的路由，fib_table_insert函数会完成这个工作，在看fib_table_insert函数之前先看看内核用来描述路由的结构体struct fib_alias，它的成员如下：
struct fib_alias {
struct hlist_node fa_list; // 用于链接到trie叶子节点
struct fib_info *fa_info; // 指向fib_info, fib_info存储着路由的其它信息
u8 fa_tos; // tos
u8 fa_type; // type
u8 fa_state;
u8 fa_slen; // 32 - pre_len
u32 tb_id; // 路由表id（因为trie树与路由表可以是一对多的关系，所以fib_alias需要用该字段来表明自己属于哪个路由表）
s16 fa_default;
struct rcu_head rcu;
};
内核把一部分路由参数存储在fib_alias中，一部分存储在fib_info中，struct fib_info结构体的成员如下所示：
struct fib_info {
struct hlist_node fib_hash; // 用于链接到全局的hash桶 （fib_info_hash）
struct hlist_node fib_lhash; // 用于链接到全局的hash桶 （fib_info_laddrhash）
struct list_head nh_list;
struct net *fib_net; // 指向网络命名空间结构体，表示该fib_info属于哪个网络命名空间
int fib_treeref; // fib_info的引用计数
refcount_t fib_clntref;
unsigned int fib_flags;
unsigned char fib_dead; // 该fib info不能使用了
unsigned char fib_protocol; // 添加路由时由`proto`指定的参数
unsigned char fib_scope; // 路由scope
unsigned char fib_type; // 路由类型
__be32 fib_prefsrc; // 添加路由时由`src`指定的参数
u32 fib_tb_id; // fib_info所属路由表
u32 fib_priority; // 路由优先级，会影响路由被查找时的顺序
......
int fib_nhs; // fib_nhs表示该路由有多少个nexthop
bool fib_nh_is_v6;
bool nh_updated;
struct nexthop *nh; // 指向共享的nexthop的指针
struct rcu_head rcu;
struct fib_nh fib_nh[0]; // 用于存储私有nexthop的数组
};
需要注意的是系统中的fib_info是可以被多条路由共享的，如果两条路由的table\priority\scope\src\type\nexthop这些参数全都相同，那么这两条路由就共享同一个fib_info。
此外，路由的nexthop也是可以被共享的，添加路由时若使用nhid关键字为路由指定下一跳id，则内核会去查找全局共享的nexthop，并引用它，全局共享的nexthop通过红黑树组织在一起，在应用层可以通过ip nexthop 指令来添加共享的nexthop。
添加路由时若使用nexthop关键字或者dev和via关键字指定下一跳，则内核不会使用共享的nexthop，内核会根据下一跳信息的个数来分配相同数目的struct fib_info，然后用它们来存储私有的下一跳信息。
fib_table_insert函数新建路由并插入路由表的过程大致如下(fib_table_insert函数也会负责路由的修改和替换)：
// // linux-5.4.246/net/ipv4/fib_frontend.c
cfg: 暂存着应用层传递的参数
tb: 指向路由表的指针
int fib_table_insert(struct net *net, struct fib_table *tb,
struct fib_config *cfg, struct netlink_ext_ack *extack)
{
enum fib_event_type event = FIB_EVENT_ENTRY_ADD;
struct trie *t = (struct trie *)tb->tb_data;
struct fib_alias *fa, *new_fa;
struct key_vector *l, *tp;
u16 nlflags = NLM_F_EXCL;
struct fib_info *fi;
u8 plen = cfg->fc_dst_len; // 前缀长度
u8 slen = KEYLENGTH - plen; // 32 - plen
u8 tos = cfg->fc_tos;
u32 key;
int err;
key = ntohl(cfg->fc_dst); // key代表路由前缀值
......
// 1 根据应用层传递的参数创建fib_info和fib_nh, 当系统中存在完全table\priority\scope\src\type\nexthop相同的fib_info时，则直接引用它
fi = fib_create_info(cfg, extack);
......
// 2 使用路由前缀去trie树上寻找匹配叶子节点，可能会找不到。tp指针将指向与路由前缀匹配的枝干节点，后面若是需要新建节点，就会在该枝干节点下面建立
l = fib_find_node(t, &tp, key);
// 3 若找到了叶子节点，则查找叶子节点上是否有相同slen的fib_alias
fa = l ? fib_find_alias(&l->leaf, slen, tos, fi->fib_priority,tb->tb_id) : NULL;
// 4 若fa不为空，则存在相同slen的fib_alias，进而判断其tos和priority是否相同
if (fa && fa->fa_tos == tos && fa->fa_info->fib_priority == fi->fib_priority) {
// 4.1 进入该分支则代表有[slen tos priority table]相同的路由，此时只允许对该路由执行追加、替换和修改操作（ip route replace/change/append），不允许执行添加操作（ip route add）
struct fib_alias *fa_first, *fa_match;
err = -EEXIST;
// 4.1.1 ip route add会配置NLM_F_EXCL标志位，所以add走到这里直接报错-EEXIST
if (cfg->fc_nlflags & NLM_F_EXCL)
goto out;
nlflags &= ~NLM_F_EXCL;
// 4.1.2 fa_list上的fib_alias按照slen 从小到大，tos从大到小，priority从小到大的顺序排列，接下来的循环中查找一个合适的位置用于append
// 该循环也查找是否存在[prefix table tos priority scope src type nexthop]完全相同的路由, 找到完全相同的路由后会给fa_match赋值
fa_match = NULL;
fa_first = fa;
hlist_for_each_entry_from(fa, fa_list) {
if ((fa->fa_slen != slen) ||
(fa->tb_id != tb->tb_id) ||
(fa->fa_tos != tos))
break;
if (fa->fa_info->fib_priority != fi->fib_priority)
break;
if (fa->fa_type == cfg->fc_type &&
fa->fa_info == fi) { // fa_match不为空表示存在完全相同的路由
fa_match = fa;
break;
}
}
// 4.1.3 如果指定了 NLM_F_REPLACE标志(ip route replace/change)，则将原fa的fib_alias以及fib_info释放掉，并将新的fib_alias链接上去
if (cfg->fc_nlflags & NLM_F_REPLACE) {
struct fib_info *fi_drop;
u8 state;
nlflags |= NLM_F_REPLACE;
fa = fa_first;
// 4.1.3.1 完全一样的路由，就不需要再replace/change了，直接返回成功
if (fa_match) {
if (fa == fa_match)
err = 0;
goto out;
}
// 4.1.3.2 不存在完全一样的路由，则分配新的fib_alias, 替换fa
err = -ENOBUFS;
new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
if (!new_fa)
goto out;
fi_drop = fa->fa_info;
new_fa->fa_tos = fa->fa_tos;
new_fa->fa_info = fi;
new_fa->fa_type = cfg->fc_type;
state = fa->fa_state;
new_fa->fa_state = state & ~FA_S_ACCESSED;
new_fa->fa_slen = fa->fa_slen;
new_fa->tb_id = tb->tb_id;
new_fa->fa_default = -1;
......
// 新的fib_alias替代原来的fib_alias插入trie叶子节点的链表上
hlist_replace_rcu(&fa->fa_list, &new_fa->fa_list);
// 释放原来的fib_alias
alias_free_mem_rcu(fa);
// 释放原fib_info，其实是减少引用次数，引用次数为0的时候才会真正的释放它
fib_release_info(fi_drop);
goto succeeded;
}
// 4.1.4 ip route append会走到这一步
if (fa_match) // fa_match代表找到了完全相同的路由
goto out; // append是不允许append完全相同的路由的，直接报错
if (cfg->fc_nlflags & NLM_F_APPEND) {
event = FIB_EVENT_ENTRY_APPEND;
nlflags |= NLM_F_APPEND;
} else {
fa = fa_first;
}
}
// 5 新建路由时会走到这里
err = -ENOENT;
if (!(cfg->fc_nlflags & NLM_F_CREATE))
goto out;
nlflags |= NLM_F_CREATE;
err = -ENOBUFS;
// 5.1 创建新的fib_alias，记录tos/type/table id/slen等参数
new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
if (!new_fa)
goto out;
new_fa->fa_info = fi;
new_fa->fa_tos = tos;
new_fa->fa_type = cfg->fc_type;
new_fa->fa_state = 0;
new_fa->fa_slen = slen;
new_fa->tb_id = tb->tb_id;
new_fa->fa_default = -1;
......
// 5.2 fib_insert_alias函数会根据l是否为空来决定是否需要新建trie树叶子节点，将新分配的fib_alias链入trie树叶子节点的fib_alias链表上
err = fib_insert_alias(t, tp, l, new_fa, fa, key);
......
}
fib_create_info函数创建fib_info和fib_nh的过程如下：
// linux-5.4.246/net/ipv4/fib_semantics.c
struct fib_info *fib_create_info(struct fib_config *cfg,
struct netlink_ext_ack *extack)
{
int err;
struct fib_info *fi = NULL;
struct nexthop *nh = NULL;
struct fib_info *ofi;
int nhs = 1; // nhs变量代表着需要分配多少个fib_nh
struct net *net = cfg->fc_nlinfo.nl_net;
......
// 1 判断地址类型和scope是否匹配，比如类型为local，scope为RT_SCOPE_UNIVERSE就是非法的
if (fib_props[cfg->fc_type].scope > cfg->fc_scope) {
NL_SET_ERR_MSG(extack, "Invalid scope");
goto err_inval;
}
......
// 2 有两种指定nexthop的方法, 通过nhid关键字引用公用的nexthop或者通过nexthop(dev via)关键字指定私有的nexthop
if (cfg->fc_nh_id) { // 2.1 通过nhid指定了nexthop id
......
// 2.1.1 则通过id来查找nexthop, 这里的nexthop是通过ip nexthop命令添加的
nh = nexthop_find_by_id(net, cfg->fc_nh_id);
......
// 2.1.2 指定了nethop id的情况下就不再分配私有的nexthop (fib_nh)，所以将nhs置为0
nhs = 0;
}
#ifdef CONFIG_IP_ROUTE_MULTIPATH
if (cfg->fc_mp) {
// 2.2 应用层通过nexthop关键字指定了下一跳信息， 则计算有多少个私有的nexthop，若是通过dev或者via关键字指定的下一跳信息，则nhs默认为1
nhs = fib_count_nexthops(cfg->fc_mp, cfg->fc_mp_len, extack);
if (nhs == 0)
goto err_inval;
}
#endif
err = -ENOBUFS;
// 3 所有的fib_info都会链接到系统全局的hash桶中，这里的 fib_info_cnt代表着系统中fib_info的数目，fib_info_hash_size代表着hash桶的大小，这里会根据系统现有的fib_info数目调整hash桶的大小
if (fib_info_cnt >= fib_info_hash_size) {
unsigned int new_size = fib_info_hash_size << 1;
struct hlist_head *new_info_hash;
struct hlist_head *new_laddrhash;
unsigned int bytes;
if (!new_size)
new_size = 16;
bytes = new_size * sizeof(struct hlist_head *);
new_info_hash = fib_info_hash_alloc(bytes);
new_laddrhash = fib_info_hash_alloc(bytes);
if (!new_info_hash || !new_laddrhash) {
fib_info_hash_free(new_info_hash, bytes);
fib_info_hash_free(new_laddrhash, bytes);
} else
fib_info_hash_move(new_info_hash, new_laddrhash, new_size);
if (!fib_info_hash_size)
goto failure;
}
// 4 分配新的fib_info, 顺带分配nhs个私有的nexthop （fib_nh）
fi = kzalloc(struct_size(fi, fib_nh, nhs), GFP_KERNEL);
if (!fi)
goto failure;
......
// 增加fib_info的计数
fib_info_cnt++;
// 记录net scope type priority prefsrc table nhs这些参数
fi->fib_net = net;
fi->fib_protocol = cfg->fc_protocol;
fi->fib_scope = cfg->fc_scope;
fi->fib_flags = cfg->fc_flags;
fi->fib_priority = cfg->fc_priority;
fi->fib_prefsrc = cfg->fc_prefsrc;
fi->fib_type = cfg->fc_type;
fi->fib_tb_id = cfg->fc_table;
fi->fib_nhs = nhs;
// 5 引用公有的nexthop或者初始化私有的nexthop
if (nh) {
// 5.1 如果使用公有的nexthop,则增加公有nexthop的引用计数
if (!nexthop_get(nh)) {
NL_SET_ERR_MSG(extack, "Nexthop has been deleted");
err = -EINVAL;
} else {
err = 0;
fi->nh = nh;
}
} else {
//5.2 使用私有nexthop
change_nexthops(fi) {
nexthop_nh->nh_parent = fi;
} endfor_nexthops(fi)
// 5.2.1 应用层使用nexthop关键字传递了多个下一跳信息，则解析cfg->fc_mp（RTA_MULTIPATH）指向的下一跳信息
if (cfg->fc_mp)
err = fib_get_nhs(fi, cfg->fc_mp, cfg->fc_mp_len, cfg,
extack);
else // 5.2.2 应用层使用dev或者via关键字指定了下一跳信息，那就只初始化一个私有的fib_nh
err = fib_nh_init(net, fi->fib_nh, cfg, 1, extack);
}
......
// 6 检查nexthop的scope，基本检查原则就是：nexthop的scope值应该比路由自身的scope值大（也就是到nexthop的距离应该比到目的网络的距离更近）
if (fi->nh) {
// 6.1 检查公用nexthop的scope
err = fib_check_nexthop(fi->nh, cfg->fc_scope, extack);
if (err)
goto failure;
} else if (cfg->fc_scope == RT_SCOPE_HOST) {
struct fib_nh *nh = fi->fib_nh;
// 6.2 cfg->fc_scope == RT_SCOPE_HOST代表该路由是到本机的路由
// 6.2.1 到本机的路由不应该有多路径
if (nhs != 1) {
NL_SET_ERR_MSG(extack,
"Route with host scope can not have multiple nexthops");
goto err_inval;
}
// 6.2.2 到本机的路由不应该有有gateway, fib_nh_gw_family不为0表示指定了gateway
if (nh->fib_nh_gw_family) {
NL_SET_ERR_MSG(extack,
"Route with host scope can not have a gateway");
goto err_inval;
}
// 6.2.3 路由的scope为RT_SCOPE_HOST，则nexthop的scope为RT_SCOPE_NOWHERE
nh->fib_nh_scope = RT_SCOPE_NOWHERE;
nh->fib_nh_dev = dev_get_by_index(net, nh->fib_nh_oif);
err = -ENODEV;
if (!nh->fib_nh_dev)
goto failure;
} else {
int linkdown = 0;
// 6.3 fib_check_nh函数将为所有私有的nexthop配置scope，大致规律如下
// 未使用via指定网关，路由的scope小于等于RT_SCOPE_LINK，则nexthop的scope为 RT_SCOPE_LINK
// 使用via指定网关，路由的scope等于RT_SCOPE_LINK，使用via指定的地址去路由表中查找scope大于等于RT_SCOPE_HOST的路由，nexthop的scope由查找到的路由决定
// 使用via指定网关，路由的scope小于RT_SCOPE_LINK，使用via指定的地址去路由表中查找scope大于等于RT_SCOPE_LINK的路由，nexthop的scope由查找到的路由决定
change_nexthops(fi) {
err = fib_check_nh(cfg->fc_nlinfo.nl_net, nexthop_nh,
cfg->fc_table, cfg->fc_scope,
extack);
if (err != 0)
goto failure;
if (nexthop_nh->fib_nh_flags & RTNH_F_LINKDOWN)
linkdown++;
} endfor_nexthops(fi)
if (linkdown == fi->fib_nhs)
fi->fib_flags |= RTNH_F_LINKDOWN;
}
// 7 如果添加路由时通过src关键字指定了presrc，则它应该是本机地址中的一个
if (fi->fib_prefsrc && !fib_valid_prefsrc(cfg, fi->fib_prefsrc)) {
NL_SET_ERR_MSG(extack, "Invalid prefsrc address");
goto err_inval;
}
......
link_it:
// 8 遍历全局的fib_info，将它们与新建的fib_info进行比较，若是存在完全相同的fib_info（[table priority scope src type nexthop]相同），直接引用并释放掉新建的fib_info
ofi = fib_find_info(fi);
if (ofi) {
fi->fib_dead = 1;
free_fib_info(fi);
ofi->fib_treeref++;
return ofi;
}
// 增加引用计数
fi->fib_treeref++;
......
// 9 将fib_info放入全局的hash桶
hlist_add_head(&fi->fib_hash,&fib_info_hash[fib_info_hashfn(fi)]);
......
}
fib_insert_alias函数将fib_alias插入路由表的过程如下：
// linux-5.4.246/net/ipv4/fib_trie.c
t: trie树
tp: 与路由前缀匹配的枝干节点或者根节点
l: 与路由前缀匹配的叶子点，可能为空
new: 新建的fib_alias
fa: 要在fa前面插入new
static int fib_insert_alias(struct trie *t, struct key_vector *tp,
struct key_vector *l, struct fib_alias *new,
struct fib_alias *fa, t_key key)
{
// 1 如果叶子节点不存在，则先在trie树上tp下面创建叶子节点
if (!l)
return fib_insert_node(t, tp, new, key);
if (fa) {
// 2 若fa不为空，则在fa前面插入new
hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
} else {
// 3 若fa不为空，证明fa_list上没有slen与new->fa_slen相同的fib_alias, 此时只需按照slen从小到大的原则来找到一个位置插入新的fib_alias，无需考虑tos和priority
struct fib_alias *last;
hlist_for_each_entry(last, &l->leaf, fa_list) {
if (new->fa_slen < last->fa_slen)
break;
if ((new->fa_slen == last->fa_slen) &&
(new->tb_id > last->tb_id))
break;
fa = last;
}
if (fa)
hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);
else
hlist_add_head_rcu(&new->fa_list, &l->leaf);
}
// 4 叶子节点的slen记录着fib_alias中最大的slen值
if (l->slen < new->fa_slen) {
l->slen = new->fa_slen;
node_push_suffix(tp, new->fa_slen); // 更新枝干节点的slen，枝干节点的slen为子节点slen中的最大值
}
return 0;
}
fib_insert_node的入参：
tp: 与路由前缀匹配的枝干节点，父节点
new: 新的fib_alias
key: 路由前缀值
static int fib_insert_node(struct trie *t, struct key_vector *tp,
struct fib_alias *new, t_key key)
{
struct key_vector *n, *l;
// 1 创建新的叶子节点， key=路由prefix, pos = 0, bits = 0
l = leaf_new(key, new);
if (!l)
goto noleaf;
// 2 使用key值来获取tp的子节点
n = get_child(tp, get_index(key, tp));
/*
* 3 如果n不为空，则需要额外创建一个枝干节点用于连接l和n, 例如
* tp: key 192.168.0.0 , pos 15, bits 1
* n: key 192.168.0.1, pos 0, bits 0
* l: key 192.168.0.2, pos 0, bits 0
* l在tp的index为0，它应当被存储在tp->tnode[0], 但tp->tnode[0]已经有一个key为192.168.0.1的节点了，所以需要新建一个枝干节点用于连接节点n和节点l
* 192.168.0.0 pos 15 bits 1 // 枝干节点tp
+-- 192.168.0.0 pos 1 bits 1 // 新增的枝干节点
|-- 192.168.0.1 pos 0 bits 0 //节点l
|-- 192.168.0.2 pos 0 bits 0 //节点n
*/
if (n) {
struct key_vector *tn;
// 3.1 创建新的枝干节点，枝干节点的pos取决于n和l的key值，它们key值出现不相同的那个比特位的位置就是pos的值
tn = tnode_new(key, __fls(key ^ n->key), 1);
if (!tn)
goto notnode;
/* initialize routes out of node */
NODE_INIT_PARENT(tn, tp);
// 3.2 将节点n放到新创建的枝干节点下
put_child(tn, get_index(key, tn) ^ 1, n);
// 3.3 将新建的枝干节点放到tp下
put_child_root(tp, key, tn);
node_set_parent(n, tn);
// 将tp指向新的枝干节点
tp = tn;
}
// 4 更新tp的slen
node_push_suffix(tp, new->fa_slen);
NODE_INIT_PARENT(l, tp);
// 5 将为路由新建的叶子节点l放到tp下
put_child_root(tp, key, l);
// 6 平衡trie树
trie_rebalance(t, tp);
return 0;
notnode:
node_free(l);
noleaf:
return -ENOMEM;
}
查表过程
查找IPv4路由表时，经过一系列的函数调用，最终会调用到fib_table_lookup函数，调用方会将此次路由查找的期望参数放入struct flowi4类型的结构体变量中，它的结构大致如下
struct flowi4 {
struct flowi_common __fl_common;
#define flowi4_oif __fl_common.flowic_oif // 期望的输出设备，比如有的socket配置SO_BINDTODEV之类的socket option，那么通过该socket输出的数据包查表时就会给flowi4_oif赋值
#define flowi4_iif __fl_common.flowic_iif // 输入设备，它不会被当作期望参数
#define flowi4_mark __fl_common.flowic_mark // 报文携带的mark，它不会被当作期望参数
#define flowi4_tos __fl_common.flowic_tos // 期望的tos，一般来自报文自身或者ip option IP_TOS
#define flowi4_scope __fl_common.flowic_scope // 期望的scope，正常情况下输入或输出报文时，该值会传递RT_SCOPE_UNIVERSE
#define flowi4_proto __fl_common.flowic_proto // 报文的protocol，一般来自报文的协议字段，不会被当作期望参数
#define flowi4_flags __fl_common.flowic_flags
#define flowi4_secid __fl_common.flowic_secid
#define flowi4_tun_key __fl_common.flowic_tun_key
#define flowi4_uid __fl_common.flowic_uid
#define flowi4_multipath_hash __fl_common.flowic_multipath_hash
/* (saddr,daddr) must be grouped, same order as in IP header */
__be32 saddr;
__be32 daddr; // 目的ip，会用于查找前缀树节点
union flowi_uli uli;
#define fl4_sport uli.ports.sport // 源端口， 不会被当作期望参数
#define fl4_dport uli.ports.dport // 目的端口， 不会被当作期望参数
#define fl4_icmp_type uli.icmpt.type
#define fl4_icmp_code uli.icmpt.code
#define fl4_ipsec_spi uli.spi
#define fl4_mh_type uli.mht.type
#define fl4_gre_key uli.gre_key
} __attribute__((__aligned__(BITS_PER_LONG/8)));
fib_table_lookup函数大致如下：
// linux-5.4.246/net/ipv4/fib_trie.c
int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
struct fib_result *res, int fib_flags)
{
struct trie *t = (struct trie *) tb->tb_data;
#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats __percpu *stats = t->stats;
#endif
const t_key key = ntohl(flp->daddr); // key值代表目的ip
struct key_vector *n, *pn;
struct fib_alias *fa;
unsigned long index;
t_key cindex;
pn = t->kv; // pn指向trie树根节点
cindex = 0;
// 1 取根节点的第一个子节点，根节点只会有一个子节点
n = get_child_rcu(pn, cindex);
if (!n) { // n为空代表该路由表为空，直接返回
trace_fib_table_lookup(tb->tb_id, flp, NULL, -EAGAIN);
return -EAGAIN;
}
#ifdef CONFIG_IP_FIB_TRIE_STATS
this_cpu_inc(stats->gets);
#endif
// 2 从根节点开始，向下查找key值有效部分与目的ip相同的节点，直到找到完全匹配的叶子节点或者不匹配的节点（不匹配的节点可能是叶子节点也可能是枝干节点）
for (;;) {
// 2.1 获取key在n这个节点下的index
// index >= (1ul << n->bits)则表明当前节点n的有效部分与key是不匹配的，则找到了不匹配的节点（比如目的ip(key)是1.1.2.1，节点key=1.1.0.0 slen=16 pos=0 bits=0，get_cindex返回的结果将会是2）
index = get_cindex(key, n);
if (index >= (1ul << n->bits))
break;
// 2.2 节点的key值与目的ip匹配且该节点是叶子节点，则跳转到found处，去比对scope/type那些值是否符合期望
if (IS_LEAF(n))
goto found;
// 2.3 节点的key值与目的ip匹配，但该节点是枝干节点，那么进一步判断它的子节点的key值有效部分与目的ip是否匹配
if (n->slen > n->pos) {
pn = n;
cindex = index;
}
// 根据index获取子节点
n = get_child_rcu(n, index);
// 2.4 子节点为空，则需要回退到上一级节点去判断上一级节点的其它子节点是否key匹配
if (unlikely(!n))
goto backtrace;
}
// 3 上述注释2.1处找到了不匹配的节点后或者backtrace选中了一个节点后都会到达这里，节点的key值有效部分虽然与目的ip不匹配，但节点上面的路由可能是匹配的（比如目的ip(key)是1.1.2.1，节点[key=1.1.0.0 slen=16 pos=0 bits=0]与目的ip不匹配，但它上面的的路由[1.1.0.0/16]可能是匹配的）
for (;;) {
// cptr 指向n的首个子节点，如果n已经是叶子节点，那么cptr为NULL
struct key_vector __rcu **cptr = n->tnode;
// 3.1 prefix_mismatch和n->slen == n->pos两个判断条件其实就等同于比对节点key值与目的ip的slen至31]这些bit为是否相同，就能判断出节点上面是否有路由能够与目的ip匹配，如果没有就回退到上一级节点去查看其它子节点
if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))
goto backtrace;
// 3.2 节点上的路由能够与目的ip匹配，且该节点是叶子节点，则退出循环到found标签处去查看该节点上的fib_alias
if (unlikely(IS_LEAF(n)))
break;
// 3.3 这里这个while循环稍微有点复杂，对于从注释3.2处走到这里的节点而言，节点上的路由能够与目的ip匹配，但该节点是枝干节点，那么就取枝干节点的首个子节点来判断
// 对于跳转到backtrace标签这种情形而言，这个while循环是在尝试从当前父节点其它子节点中选出一个子节点
while ((n = rcu_dereference(*cptr)) == NULL) {
backtrace:
// 4 backtrace，从当前父节点的其它子节点中选择一个
// 比如当前节点是index 111，它的scope、type那些参数不满足，进入了backtrace的流程，那么接下来就会选择index为110的节点（110过后100、000）
....
while (!cindex) { // 4.1 cindex为0，则当前pn已经没有合适的子节点可以用来匹配了，那么再回退一级去执行backtrace
t_key pkey = pn->key;
// 4.1.1 如果pn已经指向了根节点，则查找失败了，没有合适的前缀能匹配上，直接返回
if (IS_TRIE(pn)) {
trace_fib_table_lookup(tb->tb_id, flp,
NULL, -EAGAIN);
return -EAGAIN;
}
// 4.1.2 pn还没指向根节点，回退一级
pn = node_parent_rcu(pn); // pn指向当前父节点的父节点
cindex = get_index(pkey, pn); // cindex 更新为父节点在它的父节点下的index，稍后又对它的index执行 111->110->100->000类似的操作
}
4.2 cindex不为0，表示当前pn下还有子节点可以查看
cindex &= cindex - 1; // 111 - > 110, 110 -> 100 , 100 - > 000
// 获取子节点，这里如果获取到的子节点不为空，那么就会跳出当前这个while循环，然后去走注释3处的那些逻辑
cptr = &pn->tnode[cindex];
}
}
found:
/* this line carries forward the xor from earlier in the function */
index = key ^ n->key;
// 5 一个叶子节点被选中后，判断它leaf链表上的路由(fib_alias)是否符合查找预期
hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
struct fib_info *fi = fa->fa_info;
int nhsel, err;
if ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen < KEYLENGTH)) {
// 5.1 过滤slen不匹配的路由（比如说目的ip为1.1.2.1，节点leaf链表上有1.1.0.0/16和1.1.0.0/24两条路由，1.1.0.0/24这条路由是不匹配的，这里会把它pass掉）
if (index >= (1ul << fa->fa_slen))
continue;
}
// 5.2 如果路由配置了tos，就需要比较tos
if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
continue;
// 5.3 如果fi->fib_dead大于0则表示该路由不可用了
if (fi->fib_dead)
continue;
// 5.4过滤scope大于flowi4_scope的路由，也就是路由的距离只能比期望的距离更近
if (fa->fa_info->fib_scope < flp->flowi4_scope)
continue;
fib_alias_accessed(fa);
// 5.5 如果给路由配置了throw | unreachable | prohibit | blackhole | nat之类的type, 那么这里得到的err就会小于0，路由查找就会报错
err = fib_props[fa->fa_type].error;
if (unlikely(err < 0)) {
out_reject:
......
return err;
}
if (fi->fib_flags & RTNH_F_DEAD)
continue;
// 5.6 判断nexthop是否是backhole，通过nexthop关键字指定下一跳信息时传递了blackhole参数就会导致nexthop变成backhole
if (unlikely(fi->nh && nexthop_is_blackhole(fi->nh))) {
err = fib_props[RTN_BLACKHOLE].error;
goto out_reject;
}
// 5.6 从下一跳信息中找到一个合适的下一跳
for (nhsel = 0; nhsel < fib_info_num_path(fi); nhsel++) {
struct fib_nh_common *nhc = fib_info_nhc(fi, nhsel);
......
if (!(flp->flowi4_flags & FLOWI_FLAG_SKIP_NH_OIF)) {
// 与期望的输出设备不符，跳过该nhc
if (flp->flowi4_oif &&
flp->flowi4_oif != nhc->nhc_oif)
continue;
}
if (!(fib_flags & FIB_LOOKUP_NOREF))
refcount_inc(&fi->fib_clntref);
// 将路由查找的结果通过struct fib_result 返回给调用者，包含很多信息，比如路由前缀值、前缀长度、路由type、路由scope、fib_info、路由表、下一跳信息等
res->prefix = htonl(n->key);
res->prefixlen = KEYLENGTH - fa->fa_slen;
res->nh_sel = nhsel;
res->nhc = nhc;
res->type = fa->fa_type;
res->scope = fi->fib_scope;
res->fi = fi;
res->table = tb;
res->fa_head = &n->leaf;
......
return err; // 查找成功，返回
}
}
......
// 6 走到这里代表着节点上的路由不满足查找期望，则尝试从当前父节点的其它子节点去查找路由
goto backtrace;
}
内核中好些功能模块都会进行路由查找，比如说接收到IP报文后会通过路由查找以确定报文是该本地输入还是转发、本地输出报文时会查找路由以确定出口设备和源IP等信息，不同的模块传入的路由查找的期望参数和对查找结果的使用都有不同，这部分内容比较分散，以后分析到具体的功能模块时再详细分析它们是如何使用路由查找的。