该篇笔记记录的是作者阅读代码后对路由表的结构以及查表过程的一些个人理解，记录在这里，以便以后回顾。
路由表的结构
在描述路由表的结构之前先看看路由的组成元素，一条路由包含很多的元素，稍微简化一下，大概包含下面这些：
[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 route
rtmsg
netlink attr
fib_config
via
RTA_GATEWAY
fc_gw4 fc_gw_family = AF_INET
dev
RTA_OIF
fc_oif
PREFIX
rtm_dst_len
RTA_DST
fc_dst_len fc_dst
tos
rtm_tos
fc_tos
metric/priority/preference
RTA_PRIORITY
fc_priority
src
RTA_PREFSRC
fc_prefsrc
scope
rtm_scope
fc_scope
onlink
rtm_flags |= RTNH_F_ONLINK
fc_flags
nhid
RTA_NH_ID
fc_nh_id
protocol
rtm_protocol
fc_protocol
table
rtm_table(<256)
RTA_TABLE
fc_table
type
rtm_type
fc_type
nexthop
RTA_MULTIPATH
fc_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的引用计数
wifi已连接但有感叹号不可上网怎么办 5个实用解决方法
英雄联盟买号平台怎么选 lol买号渠道测评