Linux 内核网络协议栈 ----- Linux 内核路由机制（一） (2.6.25)

「爱情、让人受尽委屈。」 2022-08-25 08:47 285阅读 0赞

内核的路由部分是是网络中重要部分，目前在Linux内核中默认的路由查找算法使用的是Hash查找，所以你会看到很多的数据结构是XXX\_hash什么之类(例如fn\_hash)。Linux内核从2.1开始就支持基于策略的路由，那么什么是基于策略的路由呢？我们一般的最基本的路由转发是考虑IP包的目的地址，但是有些时候不仅仅是这些，还有例如IP协议，传输端口等之类的考虑因素，所以采用所谓基于策略的路由。

或许这样理解更好，Linux默认有三种策略路由：本地路由，主路由和默认路由，那么与之对应的就是三张路由表：本地路由表，主路由表和默认路由表。

那么我们需要理解是什么呢？当然是路由怎么转的过程。在这之前，先看看所涉及数据结构有哪些。

介绍下面之前我们首先需要知道内核常用的结构之间的操作手法。说道这里不得不先说一下内核的链表结构。

内核的链表结构主要是用来表示连接关系的

struct hlist_head {
             struct hlist_node *first;
     };
     
     struct hlist_node {
             struct hlist_node *next, **pprev;   // 看这个你就知道，内核链表一般是双向链表(其实还是循环链表)
     };

那么下面的很多结构之间的链接都是通过这样的链表的！但是就算我通过一个结构找到另一个结构的链表字段的时候，怎么确定结构真正的首地址呢？其实我们都不用担心，内核采取container\_of这个宏定义来处理的！

#define container_of(ptr, type, member) ({                      \
             const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
             (type *)( (char *)__mptr - offsetof(type,member) );})

很简单，其实就是通过偏移来做的，很easy、

struct fib_table {
             struct hlist_node tb_hlist;// hash节点(通过ipv4的hlist_head可以得到属于自己的路由信息表FIB，这个就是链接字段)
             u32             tb_id;     // 标识符(例如：本地路由，主路由，默认路由)
             unsigned        tb_stamp;  // 时间戳
             int             tb_default;// 路由信息结构队列序号
             int             (*tb_lookup)(struct fib_table *tb, const struct flowi *flp, struct fib_result *res);// 查找函数
             int             (*tb_insert)(struct fib_table *, struct fib_config *);// 插入函数
             int             (*tb_delete)(struct fib_table *, struct fib_config *);// 删除路由函数
             int             (*tb_dump)(struct fib_table *table, struct sk_buff *skb, 
                                          struct netlink_callback *cb);            // 用于路由转发
             int             (*tb_flush)(struct fib_table *table);                 // 移除路由信息结构
             void            (*tb_select_default)(struct fib_table *table,         // 设置默认路由
                                                  const struct flowi *flp, struct fib_result *res);
     
             unsigned char   tb_data[0];   // 注意这个特殊字段，标识结构的结尾，分配fib_table同时分配fn_hash结构
     };                                    // 也就是fib_table之后就是fn_hash结构

// 先介绍一下“路由区”定义：fn\_zone，举个例子，子网掩码长度相同的认为是相同的路由区(ok)

struct fn_hash {     // 路由区结构体的数组( 包含所有的额路由区的情况 )
             struct fn_zone  *fn_zones[33];// 路由区分成33份，why？仔细想想，子网掩码长度是1~32，0长度掩码代表网关，那么加起来就是33，即：fn_zone[0]的掩码是0.0.0.0，fn_zone[1]是10000000.00000000.00000000.0000000这一类  等等
             struct fn_zone  *fn_zone_list;// 指向第一个活动的路由区
     };

struct fn_zone {      // 路由区结构体(所有的子网长度相等的被分在同一个路由区)
             struct fn_zone          *fz_next;       // 指向下一个不为空的路由区结构，那么所有的路由区就能链接起来
             struct hlist_head       *fz_hash;       // 有一个hash数组，用来hash得到一个hlist_head，是很多的fib_node通过自己的字段连接在这个队列中，那么通过这个fz_hahs字段可以找到fib_node所在的队列的头hlist_head，进而找到对应的fib_node ( 注意：上面说的hash数组的长度是fz_divisor长度)
             int                     fz_nent;        // 包含的路由节总数
             int                     fz_divisor;     // hash头数量(上面说了)
             u32                     fz_hashmask;    // 确定hash头的掩码
     #define FZ_HASHMASK(fz)         ((fz)->fz_hashmask)
     
             int                     fz_order;       // 子网掩码位数
             __be32                  fz_mask;        // 子网掩码
    #define FZ_MASK(fz)             ((fz)->fz_mask)  // 获取子网掩码的宏定义
    };

struct fib_node {    // 路由节点结构体( 子网相等的路由被分在一起 )
             struct hlist_node       fn_hash; // 链接到hash表节点( 注意到我们上面所说的fn_zone中的fz_hash了吗？fz_hash哈希之后得到的结果就是fib_node的这个字段，所以这个字段同样仅仅是作为链接作用而已 )
             struct list_head        fn_alias;// 别名？其实更好的理解是这样的：虽然现在所有的路由都是同一个子网了，但是路由之间还会有其他的信息不同例如tos，路由类型，等等。所以依然存在不同的路由，所以这些都是通过fn_alias来区分。
             __be32                  fn_key;  // 路由别名队列：即这个node下面所有的具体路由(不同的fn_alias的)都在这个队列中
             struct fib_alias        fn_embedded_alias; // 分配路由节点的时候同时也分配一个路由别名，所以称为嵌入式的~
     };

struct fib_alias {      // 路由别名结构，这个结构基本就是最后一次路由筛选了
             struct list_head        fa_list;  // 这个是用于链接到fib_node节点中的，看上面的结构体的第二个字段的类型你就懂了~~~~~~
             struct fib_info         *fa_info; // 这是很重要的字段：顾名思义，就是具体怎么处置这个数据包的操作等
             u8                      fa_tos;   // 服务类型TOS
             u8                      fa_type;  // 路由类型
             u8                      fa_scope; // 路由范围
             u8                      fa_state; // 路由状态
     #ifdef CONFIG_IP_FIB_TRIE
             struct rcu_head         rcu;
     #endif
     };

struct fib_info {      // 具体怎么路由这个数据包的信息
             struct hlist_node       fib_hash;      // 链接到fib_info_hash队列
             struct hlist_node       fib_lhash;     // 链接到fib_hash_laddrhash队列
             struct net              *fib_net;      // 所属网络空间
             int                     fib_treeref;   // 路由信息结构使用计数器
             atomic_t                fib_clntref;   // 释放路由信息结构(fib)计数器
             int                     fib_dead;      // 标志路由被删除了
             unsigned                fib_flags;     // 标识位
             int                     fib_protocol;  // 安装路由协议
             __be32                  fib_prefsrc;   // 指定源IP，源地址和目的地址组成一个路由
             u32                     fib_priority;  // 路由优先级
             u32                     fib_metrics[RTAX_MAX]; // 保存负载值(例如MTU，MSS)
     #define fib_mtu fib_metrics[RTAX_MTU-1]        // MTU值
     #define fib_window fib_metrics[RTAX_WINDOW-1]  // 窗口值
     #define fib_rtt fib_metrics[RTAX_RTT-1]        // RTT值
     #define fib_advmss fib_metrics[RTAX_ADVMSS-1]  // MSS值(对外公开的)
             int                     fib_nhs;       // 倒数第二个字段即:跳转结构的数组个数
     #ifdef CONFIG_IP_ROUTE_MULTIPATH
             int                     fib_power;     // 支持多路径时候使用
     #endif
             struct fib_nh           fib_nh[0];     // 跳转结构(就是该怎么路由)
     #define fib_dev         fib_nh[0].nh_dev       
     };

对于上面的fib\_nh\[0\]，这样的操作手法在内核中也是常见的。代表会有这个字段的存在，但是具体是几个并不知道，因为可能是动态的，所以需要一个计数表示，也就是fib\_power

OK，主要的数据结构已经介绍，后面的结构会边说边介绍，下面我们根据路由转发的顺序来梳理一下思路：

数据包的路由是通过函数ip\_route\_input来处理的，看这个函数：

extern int  ip_route_input(struct sk_buff*, __be32 dst, __be32 src, u8 tos, struct net_device *devin);

参数有5个：

skb： IP包缓冲区，

dst： IP包的目的地址，

src： IP包源地址，

tos： 服务类型，

devin： 输入的网络设备。

怎么运行的呢？首先这个函数需要查路由缓存(cache)，如果找到了那么它给skb->dst赋值并返回，如是没找到，它会调用ip\_route\_input\_slow去查询路由数据库。

这里我们需要理解几个问题： 首先路由缓存到底是什么结构，怎么查找，这个我们马上就会说到。再次我们需要知道所谓路由就是最终找到这个路由条目，得到目的地址(吓一跳)，然后赋值给skb->dst，然后通过skb->dst->input(skb)就可以进行操作。第三需要注意，这里的操作分成两类：第一类是投到本地，即数据是发到本机的，那么调用ip\_local\_deliver将数据包发送给上一层进行处理；第二类是转发，调用ip\_forward函数进行处理，转发出去！最后注意：当路由缓冲找不到所需要的路由项，那么最终需要再次到fib中去查找，也就是完整的一个查找过程。

下面具体看看路由缓存问题：

首先是怎么建立这个缓存的呢？其实这个问题不需要特意来说，因为后面肯定会说到，为什么呢？缓存总是由不存在到存在的，当不存在的时候只能使用查询路由信息库来处理，但是同时需要注意：更新缓存cache、这个时候就是建立cache的时候。所以在后面说到的路由信息库查询和cache的建立是一样的，先不说这个，先直接看在cache中处理。

cache的结构定义为：

static struct rt_hash_bucket    *rt_hash_table;

rt\_hash\_table就是路由cache，它是rt\_hash\_bucket结构。

struct rt_hash_bucket {
             struct rtable   *chain;
    }

注意chain是一个rtable结构，看下面：

struct rtable
     {
             union
             {
                     struct dst_entry        dst;   // 这是目的地址
             } u;
     
             /* Cache lookup keys */
             struct flowi            fl;            // 注意在cache中的查找主要是通过路由键值和下面的信息
     
             struct in_device        *idev;         // 设备
             
             int                     rt_genid;      // 路由id
             unsigned                rt_flags;      // 标识
             __u16                   rt_type;       // 路由类型
     
             __be32                  rt_dst;        // 目的地址
             __be32                  rt_src;        // 源地址
             int                     rt_iif;        // 入端口
     
             /* Info on neighbour */
             __be32                  rt_gateway;    // 网关
     
             /* Miscellaneous cached information */
             __be32                  rt_spec_dst;  /* RFC1122 specific destination */
             struct inet_peer        *peer;        /* long-living peer info */
     };

我们看一下查询的一小段代码：

2048         for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;
    2049              rth = rcu_dereference(rth->u.dst.rt_next)) {
    2050                 if (rth->fl.fl4_dst == daddr &&
    2051                     rth->fl.fl4_src == saddr &&
    2052                     rth->fl.iif == iif &&
    2053                     rth->fl.oif == 0 &&
    2054                     rth->fl.mark == skb->mark &&
    2055                     rth->fl.fl4_tos == tos &&
    2056                     rth->u.dst.dev->nd_net == net &&
    2057                     rth->rt_genid == atomic_read(&rt_genid)) {
    2058                         dst_use(&rth->u.dst, jiffies);
    2059                         RT_CACHE_STAT_INC(in_hit);
    2060                         rcu_read_unlock();
    2061                         skb->dst = (struct dst_entry*)rth;
    2062                         return 0;
    2063                 }
    2064                 RT_CACHE_STAT_INC(in_hlist_search);
    2065         }

所以很清晰的看到匹配的所有字段。下面看看我们构造一下在cache中查找的结构图：

![SouthEast][]

首先通过hash找到这个队列首部的chain，然后在chain的队列中进行匹配，如果匹配到那么OK，否则进行完整的查询。

OK，假如现在在缓存cache中并没有找到，那么执行ip\_route\_input\_slow函数进行完整查询。

我们知道Linux最多可以支持255张路由表，默认有三张路由表，即本地路由表，主路由表和默认路由表，三个优先级递减(数字越大优先级越小)，也就是查询顺序递减。我们先需要知道怎么样得到这三张路由表先。三张路由表就是三个规则，所以需要看看下面的路由信息结构规则结构体。

表255： 本地路由表（local ） 本地接口地址，广播地址，已及NAT地址都放在这个表。该路由表由系统自动维护，管理员不能直接修改。  
　　表254： 主路由表（main ） 如果没有指明路由所属的表，所有的路由都默认都放在这个表里，一般来说，旧的路由工具（如route）所添加的路由都会加到这个表。一般是普通的路由。  
　　表253： 默认路由表 （default ） 一般来说默认的路由都放在这张表。  
　　表 0 ：保留

看一下它们是怎么被初始化的：

static int fib_default_rules_init(struct fib_rules_ops *ops)
     {
             int err;
     
             err = fib_default_rule_add(ops, 0, RT_TABLE_LOCAL, FIB_RULE_PERMANENT);  // 本地路由规则(本地路由表)
             if (err < 0)
                     return err;
             err = fib_default_rule_add(ops, 0x7FFE, RT_TABLE_MAIN, 0);               // 主路由规则(主路由表)
             if (err < 0)
                     return err;
             err = fib_default_rule_add(ops, 0x7FFF, RT_TABLE_DEFAULT, 0);            // 默认路由规则(默认路由表)
             if (err < 0)
                     return err;
             return 0;
     }

// 本地规则local_rule
    static struct fib_rule local_rule = {
    r_next: &main_rule,            //下一条规则是主规则
    r_clntref: ATOMIC_INIT(2),
    r_table: RT_TABLE_LOCAL,       // 指向本地路由表
    r_action: RTN_UNICAST,         // 动作是返回路由
    };

// 主规则main_rule
    static struct fib_rule main_rule = {
    r_next: &default_rule,         // 下一条规则是默认规则
    r_clntref: ATOMIC_INIT(2),
    r_preference: 0x7FFE,          // 默认规则的优先级32766
    r_table: RT_TABLE_MAIN,        // 指向主路由表 
    r_action: RTN_UNICAST,         // 动作是返回路由
    };

// 默认规则default rule
    static struct fib_rule default_rule = {
    r_clntref: ATOMIC_INIT(2),
    r_preference: 0x7FFF,          // 默认规则的优先级32767
    r_table: RT_TABLE_DEFAULT,     // 指默认路由表
    r_action: RTN_UNICAST,         // 动作是返回路由
    };

注意：规则链的链头指向本地规则。

下面我们需要看看这个结构体：

struct fib_rule    // 规则结构体(在初始化的时候，会注册上面的三种规则，生成默认的三张表)
     {
             struct list_head        list;              // 用来链入路由规则函数队列中(fib_rules_ops,下面介绍)
             atomic_t                refcnt;            // 计数器
             int                     ifindex;           // 网络设备id
             char                    ifname[IFNAMSIZ];  // 设备名称
             u32                     mark;              // 用于过滤作用
             u32                     mark_mask;         // 掩码
             u32                     pref;              // 优先级(例如上面代码中分别是0,0x7FEE，0x7FFF)
             u32                     flags;             // 标识位
             u32                     table;             // 路由函数表id(例如本地LOCAL，主路由MAIN...)
             u8                      action;            // 动作，即怎么去处理这个数据包
             u32                     target;
             struct fib_rule *       ctarget;           // 当前规则
             struct rcu_head         rcu;
             struct net *            fr_net;            // 网络空间结构指针
     };

同时看一下rule的规则函数：

struct fib_rules_ops
     {
             int                     family;              // 协议族ID
             struct list_head        list;                // 用于链接到网络空间队列中
             int                     rule_size;           // 规则结构大小
             int                     addr_size;           // 地址大小
             int                     unresolved_rules;
             int                     nr_goto_rules;
     
             int                     (*action)(struct fib_rule *,         // 动作函数指针
                                               struct flowi *, int,
                                               struct fib_lookup_arg *); 
             int                     (*match)(struct fib_rule *,          // 匹配函数指针
                                              struct flowi *, int);
             int                     (*configure)(struct fib_rule *,      // 配置函数指针
                                                  struct sk_buff *,
                                                  struct nlmsghdr *,
                                                  struct fib_rule_hdr *,
                                                  struct nlattr **);
             int                     (*compare)(struct fib_rule *,        // 对比函数指针
                                                struct fib_rule_hdr *,
                                                struct nlattr **);
             int                     (*fill)(struct fib_rule *, struct sk_buff *,
                                             struct nlmsghdr *,           // 填写函数指针
                                             struct fib_rule_hdr *);
             u32                     (*default_pref)(struct fib_rules_ops *ops);  // 查找优先级函数指针
             size_t                  (*nlmsg_payload)(struct fib_rule *); // 统计负载数据能力函数指针
     
             /* Called after modifications to the rules set, must flush
              * the route cache if one exists. */
             void                    (*flush_cache)(void);     // 修改规则之后刷新缓存函数指针
     
             int                     nlgroup;      // 路由netlink组划分标识
             const struct nla_policy *policy;      // netlink属性优先级
             struct list_head        rules_list;   // 路由规则队列
             struct module           *owner;       // 
             struct net              *fro_net;     // 网络空间结构指针
     };

现在我们从宏观上应该有一个认识，当我们进入策略查找的时候，根据优先级，分别查找本地路由表\->主路由表\->默认路由表。

OK，我们需要看一下结构直接的关系：

![SouthEast 1][]

ok，我们由规则找到了我们需要的三张表，三张表按照优先级的顺序进行查询，现在就以Local表为例进行下面具体的查询，看下图：

![SouthEast 2][]

从图中我们可以看到四个等级查询：fib\_table ---> fn\_zone ---> fib\_node ---> fib\_info

> fib\_table结构后面紧接着就是fn\_hash数组，里面是33个数组元素，fn\_hash\[0\]代表网关，fn\_hash\[1\]代表子网掩码长度为一的情况... 为什么需要这样划分，因为我们知道，在匹配地址的时候遵循最长掩码优先原则，所以，精确度递减。  同时注意fn\_zone\_list指向第一个活动的路由区，将所有的路由区都链接在一起，从而提高查找的效率。fn\_zone结构中最重要的就是fz\_hash域了，它指向了一个hash table，这个hash table组织了这个区域下的所有路由项。( 一个fn\_zone其实就是所有掩码长度相等的路由聚集在一起... )

> fn\_zone路由区通过再次计算hash值，可以获得和自己相关的fib\_node节点，fib\_node节点是所有的子网相等的路由聚集在一起。

fn\_key子网地址，也就是hash查找的关键字；fn\_type表示路由类型，即到底要怎处理数据，例如：单播转发，本地，丢弃，NAT等等对于大多数情况，路由项都是单播转发类型的；fn\_info就是保存下一跳的信息，它指向一个fib\_info结构。

> 需要注意的是，一个fib\_node对应着很多fib\_info，因为即使是子网相等，也不一定是相等的路由，还有很多其他的因素。fib\_info结构被组织成一个双向链表，表头为fib\_info\_list。下一跳的具体信息是fib\_nh\[\]数组，它表示一个下一跳动作可以对应着多个物理的下一跳，这是linux支持的一个MULITPATH功能。

说到这来，大致的印象应该是有的，下面需要做的就是深入代码细节。

待续...  后面会介绍相关的代码...

[SouthEast]: /images/20220824/fd0d2fbfb0a74182861b6f0b8168d60d.png
[SouthEast 1]: /images/20220824/1bbab1b8dcb74787918552650672ab87.png
[SouthEast 2]: /images/20220824/efdb0f622b504aeaaa8359c2aece3745.png