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

Read More

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 }
route

ping本机网口的IP地址，tcpdump在lo口才能抓到对应报文

问题背景

Q1：ping 本机eth1口的ip地址时，对应的ICMP报文会被发送到eth1口上吗？

实验： ping本机网口地址

ping本机网口地址实验

通过tcpdump抓包命令，我们发现报文被发送到lo上，而不是对应的物理口 eth1。
虽然ip 地址被配在本机的物理口上，但是报文并没有被发送到物理口。为了理解这个问题，我们需要先看下下面这个问题。

Q2： 当一个IP地址被添加到一个网口后，会引起哪些路由变化呢？
为一个网口增加一个 IP 地址是个很常见的网络操作。
具体添加方式有多种，包括命令行手动添加、通过配置文件在系统启动时候添加，还是通过dhcp自动获取并添加等。
无论哪种场景，添加完IP地址后，系统路由有什么变化。
场景：在本机物理口 eth1上配置192.168.8.8/24，网口状态正常(UP).

Read More

route

fib_unmerge：把local路由从main表里切割出来

fib_unmerge 是内核路由子系统中一个精巧的按需优化设计：

  • 默认状态下，local 表只是 main 表的别名，所有路由合并在一张表里，fib_lookup 只需查一次表，性能最优
  • 添加策略路由时，fib_unmerge 将 local 路由从 main 表中切割出来，放入独立的 local 表，确保策略路由能正确匹配
  • 切割四步走：创建新 local 表 → 复制 local 路由 → 替换旧表 → 清理 main 表中的残留条目
  • 幂等设计：只在首次添加策略路由时执行分离，后续再添加时 fib_trie_unmerge 检测到已分离，直接返回

本文将从调用点入手，逐步分析 fib_unmerge 的实现细节。

Read More

route

lo口与local路由表

小实验

接上篇文章 ping本机网口的IP地址，tcpdump在lo口才能抓到对应报文，我们知道在网口eth1上增加一个IP地址192.168.8.8/24后，内核会生成3条路由：

  • local表：增加192.168.8.8/32的主机路由（RTN_LOCAL）
  • main表：增加192.168.8.8/24的网段路由（RTN_UNICAST）
  • local表：增加广播路由

其中主机路由类型是RTN_LOCAL，网段路由类型是RTN_UNICAST。
那如果把IP地址配到lo口上，会有什么不同呢？

实验题目

  1. ping 本机 lo 口的IP地址 127.0.0.1 能ping通吗？
  2. ping 127.0.0.0/8 网段下的其他地址能ping通吗？
  3. 把一个任意IP地址配置到 lo 口上，又会有什么实验结果呢？

Read More

tcpdump命令与网口`PROMISC`状态标志位

问题现象

tcpdump/iproute2 是很多网络问题下的调试工具，大家也都很熟他的一些特性。比如，

  • 执行tcpdump命令后，如果没有使用-p参数, 网口会进入PROMISC状态。
  • 通过ip link命令可以查看网口状态，其中状态位里有个PROMISC标志。
    但是，后台执行一个在 eth0 口上抓包的tcpdump命令，就会发现一个问题：
  1. 当tcpdump命令在后台运行时，通过查看ip link结果，对应网口的状态标志位没有PROMISC标志位，也没有其他变化。
    tcpdump 执行时， 网口标志位里没有PROMiSC
    为了避免干扰，关闭tcpdump 后，我们又做了另外一个验证操作。
  • 执行ip link set dev eth0 promisc on命令，设置网口混杂模式。这时，网口的PROMISC标志位能正常显示出来。
    ip link设置网口标志位PROMiSC
    这样看来，PROMISC标志位只受 ip link命令控制，与在网口上是否运行tcpdump无关。

看到这里，不免就有疑问了

  • Q1： tcpdump执行时候，对应网口到底进没进入PROMISC混杂模式呢？
    A：进入PROMISC状态了。 因为对应时间段里，dmesg内核日志有明确的记录。
1
2
[5828194.373058] virtio_net virtio0 eth0: entered promiscuous mode
[5828198.130489] virtio_net virtio0 eth0: left promiscuous mode

注意，ip link 命令设置 on 的时候，网口也会进入PROMISC混杂模式。

  • Q2: 既然tcpdump和 iplink都能使网口进入混杂模式，这两个命令又可以独立执行。运行tcpdump命令抓包时，被ip link命令设置了promisc off, 网卡会退出混杂模式，会不会对tcdpump抓包造成影响？
    A：命令可以并发执行，不会相互干扰。这个场景下，ip link不会让网口退出混杂模式，也不会影响后续的 tcpdump 抓包。promisc off 命令只会让 ip link 显示的网口的状态标志位里的PROMISC被清除掉。
  • Q3: 多个tcpdum并行抓包，退出有先后，会不会相互影响？
    A： 并行tcpdump执行，不会影响网口PROMISC。内核有引用计数机制，保证最后一个 tcpdump 退出时候，网口也跟着关闭混杂模式。

Read More

PAWS 在tcp协议栈中的实现

PAWS 检查：

  1. tcp_timewait_state_process 中使用，也就是在syn 报文明中了 tw 状态的 socket 山海，才使用。 不是所有syn报文都做检查
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 91 enum tcp_tw_status
 92 tcp_timewait_state_process(struct inet_timewait_sock *tw, struct sk_buff *skb,
 93                            const struct tcphdr *th)
 94 {
 95         struct tcp_options_received tmp_opt;
 96         struct tcp_timewait_sock *tcptw = tcp_twsk((struct sock *)tw);
 97         bool paws_reject = false;
 98
 99         tmp_opt.saw_tstamp = 0;
100         if (th->doff > (sizeof(*th) >> 2) && tcptw->tw_ts_recent_stamp) {
101                 tcp_parse_options(skb, &tmp_opt, 0, NULL);
102
103                 if (tmp_opt.saw_tstamp) {
104                         tmp_opt.rcv_tsecr       -= tcptw->tw_ts_offset;
105                         tmp_opt.ts_recent       = tcptw->tw_ts_recent;
106                         tmp_opt.ts_recent_stamp = tcptw->tw_ts_recent_stamp;
107                         paws_reject = tcp_paws_reject(&tmp_opt, th->rst);
108                 }
109         }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1142
1143 static inline bool tcp_paws_check(const struct tcp_options_received *rx_opt,
1144                                   int paws_win)
1145 {
1146         if ((s32)(rx_opt->ts_recent - rx_opt->rcv_tsval) <= paws_win)
1147                 return true;
1148         if (unlikely(get_seconds() >= rx_opt->ts_recent_stamp + TCP_PAWS_24DAYS))
1149                 return true;
1150         /*
1151          * Some OSes send SYN and SYNACK messages with tsval=0 tsecr=0,
1152          * then following tcp messages have valid values. Ignore 0 value,
1153          * or else 'negative' tsval might forbid us to accept their packets.
1154          */
1155         if (!rx_opt->ts_recent)
1156                 return true;
1157         return false;
1158 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1160 static inline bool tcp_paws_reject(const struct tcp_options_received *rx_opt,
1161                                    int rst)
1162 {
1163         if (tcp_paws_check(rx_opt, 0))
1164                 return false;
1165
1166         /* RST segments are not recommended to carry timestamp,
1167            and, if they do, it is recommended to ignore PAWS because
1168            "their cleanup function should take precedence over timestamps."
1169            Certainly, it is mistake. It is necessary to understand the reasons
1170            of this constraint to relax it: if peer reboots, clock may go
1171            out-of-sync and half-open connections will not be reset.
1172            Actually, the problem would be not existing if all
1173            the implementations followed draft about maintaining clock
1174            via reboots. Linux-2.2 DOES NOT!
1175
1176            However, we can relax time bounds for RST segments to MSL.
1177          */
1178         if (rst && get_seconds() >= rx_opt->ts_recent_stamp + TCP_PAWS_MSL)
1179                 return false;
1180         return true;
1181 }
socket

tcp三次握手 --- 逐渐消失的tcp半链接队列

概要：十年演进对比

历史实现(v4.3)

网上大部分文档这部分内容讲的比较多，简单来说，可以把半链接队列的逻辑概括如下:

  • 收到syn报文，查找listen socket。
  • 创建一个半链接socket(req socket)，并放入listen socket的半链接队列里，发送syn+ack报文
  • 收到client回复的ack报文，查找到对应的半链接socket(req socket)
  • 基于半链接socket和ack报文创建child socket
  • 把child socket(req)加入到accept队列中，等待accept系统调用/激活

当前实现(v6.14)

在v6.14内核里，三次握手的处理流程如下：

  • step1：收到一个syn请求报文：查找到对应的listen socket
  • step2：创建一个半链接socket(req socket)，记录 syn 请求的一些字段信息，如seq, mss等。
  • step3：构造并发送syn+ack报文
  • step4: 把半链接socket(req socket)放入全局(netns)的ehash链表中，并统计半链接socket个数。通常说的半链接队列长度。
    + 全局：确切说是，当前netns(net namesapce)。一般默认是指当前物理机的内核协议栈。当有 docker实例（启用网络隔离）时候，全局则是指当前 docker 实例的内核协议栈。docker如何使用netsns隔离，不展开。为了理解方便，这里我们以没有docker 隔离的场景为例。
    + ehash链表：一个hash 链表，存放有全部establish状态的socket，当然tw状态的也在这个链表里。关联度不高，不展开。
    不同点 ：使用全局ehash链表，而不是 listen socket的半链接队列
  • step5：收到client回复的ack报文，查找到对应的半链接socket(req socket)
  • step6：基于半链接socket 和ack报文创建child socket
  • step7：把新创建的child socket 插入到 ehash链表中。同时把req socket从链上摘掉。
  • step8：把req socket加入到listen socket的accept队列中，同时让req下的关联socket指针指向child。
  • step9： 发送listen socket的data_ready消息给应用程序， 等待listen socket上的accept系统调用/激活。
  • step10： accept系统调用把req socket从accept队列上拆除。同时，封装child socket，给用户返回其对应的fd.

tcp三次握手概要图

差异点

  • 使用全局ehash 链表而不是listen socket 下的半链接队列, 来存放半链接(req) socket。
    队列只是一个习惯性的叫法，严格意义上说不合适。很早(20+年)之前，内核就已经使用hash链接替换队列存放半链接socket了。
  • 长度检查：半链接个数(队列长度)和accept队列长度的检查
  • ack报文处理逻辑：查找半链接socket，减少锁listen socket的时长。

Read More

socket

创建req scoket时的三个长度检查

创建半链接时的三个长度检查

在处理TCP-SYN首包时候， tcp_conn_request函数里， 会有三个不同条件的长度检查。

  • inet_csk_reqsk_queue_is_full 半链接的个数超过sk_max_ack_backlog， 则丢包。
  • sk_acceptq_is_full： accept 队列长度超过sk_max_ack_backlog，则丢包。
  • sysctl_tcp_syncookies禁用(值为0)时, sysctl_max_syn_backlog 与inet_csk_reqsk_queue_len： 队列长度如果超过sysctl_max_syn_backlog的3/4则丢包

其中，

  • sysctl_max_syn_backlog： 初始化时，最小 128。如果ehash_entries/128比128大，取最大值。ehash_entries是 tcp 的 hash 桶个数。
  • sysctl_tcp_syncookies: 初始值为 1

判断1： 半链接队列是否溢出 inet_csk_reqsk_queue_is_full

虽然不再维护半链接队列了, 但是每次创建req socket后，这个统计值都是在增加的。
因此如果半链接个数超过了最大值sk_max_ack_backlog，则启用cookie(sysctl_tcp_syncookies为1或2)，如果不支持cookie，则丢弃。

1
2
3
4
5
6
7
8
9
278 static inline int inet_csk_reqsk_queue_len(const struct sock *sk)
279 {
280         return reqsk_queue_len(&inet_csk(sk)->icsk_accept_queue);
281 }
282
283 static inline int inet_csk_reqsk_queue_is_full(const struct sock *sk)
284 {
285         return inet_csk_reqsk_queue_len(sk) > READ_ONCE(sk->sk_max_ack_backlog);
286 }

当前内核默认启用syncookie机制(sysctl_tcp_syncookies为1)，队列溢出会触发synccookie 机制。
只有关闭了tcpcookie(0)后，才会在队列溢出时候丢弃syn报文。

Read More

netdev

网口状态标志位解析part2: 内核如何维护网卡carrier的状态

operstate的小插曲

2006年内核引入operstate特性，在当时协议栈的维护者中也是颇有争议的！！！
引入operstat特性的patch
图4: 2006年协议栈加入operstate 特性

标志位IFF_UP

设置/清除标志位IFF_UP

ip link set eth0 up:

  • 每个eth口在内核里有对应的struct net_device。
  • 每个netdev设备里有一个上的flags用来存放标志位
  • ip link set eth0 up 设置 eth0口对应的IFF_UP标志。
  • ip link set eth0 down清除对应的IFF_UP标记。

ip link源码实现

ip link set eth0 up命令实现：

  • 通过ioctol获取eth0口对应的flags，
  • 然后将IFF_UP标志位设置到 flags 上，
  • 再通过ioctol 命令SIOCSIFFLAGS下发会内核。

具体实现在函数do_set和do_chflags中。

  1. do_set： 解析命令，转换为需要设置的标志位。
1
2
3
4
5
6
7
8
9
10
11
12
13
1370 static int do_set(int argc, char **argv)
1371 {
...
1383         while (argc > 0) {
1384                 if (strcmp(*argv, "up") == 0) {
1385                         mask |= IFF_UP;
1386                         flags |= IFF_UP;
1387                 } else if (strcmp(*argv, "down") == 0) {
1388                         mask |= IFF_UP;
1389                         flags &= ~IFF_UP;
...
1536         if (mask)
1537                 return do_chflags(dev, flags, mask);
  1. do_chflags: 借助ioctl函数接口，与内核交互。
    • 首先，读取内核的网口标志位netdev->flags，
    • 把期望更新的标志位更新成期望值。
    • 最后，把期望的标志位状态下发回内核。
1
2
3
4
5
6
7
8
9
static int do_chflags(const char *dev, __u32 flags, __u32 mask)
...
        err = ioctl(fd, SIOCGIFFLAGS, &ifr);
...
        if ((ifr.ifr_flags^flags)&mask) {
                ifr.ifr_flags &= ~mask;
                ifr.ifr_flags |= mask&flags;
                err = ioctl(fd, SIOCSIFFLAGS, &ifr);
...

*** 注意: *** ioctol命令参数里，获取和设置的命令名字, 只有一个字母G和S的差别。

内核代码实现

ioctl在内核的对应实现比较复杂, 避免歪楼，单拉一篇去介绍实现吧。

内核如何维护网卡设备的RUNNING 状态

流程概述

主要几个部分：

  1. 网卡驱动有个看门狗：不同网卡驱动实现可能不太一样 ，功能负责监控网卡硬件上网线的状态， 当网线状态变换的时候，会激发内核的 carrier 处理函数。
  2. 内核两个通用的处理函数：netif_carrier_on和netif_carrier_off。这个函数会
    • 设置或者清除netdev->state上的__LINK_STATE_NOCARRIER标志位。
    • 发送事件消息给linkwatch，做后续处理.
    • 如果是网线插好了状态， 会启动一个通用的看门狗，这个看门狗是负责检测tx队列是否’HUNG’了， 如果’HUNG’了就调用网卡对应的处理函数ndo_tx_timeout， 做一些应急补救，比如对网卡队列复位等操作。这里的看门狗跟网卡驱动里的看门狗还不是同一个看门狗。具体差别待研究。
  3. linkwath模块：linkwatch本身是个workqueue 队列，对接受到的消息按照，分为紧急和非紧急两类。紧急的决定立即处理，非紧急的则挂到一个链表里，等定时器超时后，再集中处理。所有事件处理，最终都交给linkwatch_do_dev(struct net_device *dev)函数进行处理。 该函数更新netdev->operate标志位。同时调用通用的dev_activate或者dev_deactivate对网卡做网卡队列进行处理。 我们这里重点关注跟网卡状态位有管的部分，忽略跟网卡队列的处理。
    这里有两个重要函数rfc2863_policy和default_operstate 后面我们重点介绍。

carrier on 和 off 函数

netif_carrier_on和netif_carrier_off: 内核里的两个通用的处理函数，功能基本对称

carrier标志位

总结：
dev->state下的__LINK_STATE_NOCARRIER是 carrier是否OK 的唯一判断标准。

Read More