TCP/IP学习(38)——Kernel中路由表的实现(1)

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。
作者：[e-mail]
博客：linuxfocus.blog.chinaunix.net   

今天开始学习kernel中的路由表FIB的实现，kernel支持两种FIB的存储方式：一种是hash，另外一种是单词查找树trie。分别由编译选项CONFIG_IP_FIB_HASH和CONFIG_IP_FIB_TRIE决定。

（据说新版本的kernel已经去掉了hash的实现方式）

下面首先看一下FIB中的数据结构，大部分数据结构都在文件ip_fib.h中

1. struct fib_config {
   
2.     //目的地址的掩码
3.     u8            fc_dst_len;
   
4.     //TOS
5.     u8            fc_tos;
   
6.     //路由协议，其实更像是指该条路由是从何而来，参见RTPROT_STATIC等宏
7.     //RTPROT_STATIC表示该route为管理员添加的静态路由，RTPROT_ZEBRA为由zebra添加的路由
8.     u8            fc_protocol;
   
9.     //参见rt_scope_t的定义
10.     u8            fc_scope;
    
11.     //类型如RTN_UNICAST：直连路由，参见类似的定义
12.     u8            fc_type;
    
13.     /* 3 bytes unused */
    
14.     //指示哪个路由表，如RT6_TABLE_MAIN
15.     u32            fc_table;
    
16.     //目的地址
17.     __be32            fc_dst;
    
18.     //网关
19.     __be32            fc_gw;
    
20.     //出口的网卡
21.     int            fc_oif;
    
22.     //路由标志
23.     u32            fc_flags;
    
24.     //优先级
25.     u32            fc_priority;
    
26.     //prefer 源地址，暂不知道用途
27.     __be32            fc_prefsrc;
    
28.     
29.     struct nlattr        *fc_mx;
    
30.     struct rtnexthop    *fc_mp;
    
31.     int            fc_mx_len;
    
32.     int            fc_mp_len;
    
33.     u32            fc_flow;
    
34.     u32            fc_nlflags;
    
35.     struct nl_info        fc_nlinfo;
    
36.  };

struct fib_config主要用于将外部的route的配置/参数形式转为FIB的内部配置形式。如使用IP命令添加/删除route时，或者路由daemon向linux添加/删除时，都需要将其传入系统API的参数转为FIB的内部配置结构。

/*
 * This structure contains data shared by many of routes.
 */

struct fib_info {
    struct hlist_node    fib_hash;
    struct hlist_node    fib_lhash;
    struct net        *fib_net;
    int            fib_treeref;
    atomic_t        fib_clntref;
    int            fib_dead;
    unsigned        fib_flags;
    int            fib_protocol;
    __be32            fib_prefsrc;
    u32            fib_priority;
    u32            fib_metrics[RTAX_MAX];
#define fib_mtu fib_metrics[RTAX_MTU-1]
#define fib_window fib_metrics[RTAX_WINDOW-1]
#define fib_rtt fib_metrics[RTAX_RTT-1]
#define fib_advmss fib_metrics[RTAX_ADVMSS-1]
    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
};

struct fib_info用于存储路由条目的一些共用的参数。

struct fib_table {
    /* 负载成员，用于将所有的fib_table链接起来 */
    struct hlist_node tb_hlist;
    u32        tb_id;
    int        tb_default;
    /* 路由表数据：因为有hash和trie两种方式，所以使用零长数组 */
    unsigned char    tb_data[0];
};

恩，下面开始学习代码，对于路由来说，最重要的就是路由的查询：

static inline int fib_lookup(struct net *net, const struct flowi *flp,
                 struct fib_result *res)
{
    struct fib_table *table;

     /* 

     先查询本地地址路由表

     本地路由表保存本地地址，多播等，属于需要发送到本机的地址信息。

     */

    table = fib_get_table(net, RT_TABLE_LOCAL);
    if (!fib_table_lookup(table, flp, res))
        return 0;

     /*

     再查询main路由表，这个是咱们设置路由或路由daemon设置的路由表 

     */

    table = fib_get_table(net, RT_TABLE_MAIN);
    if (!fib_table_lookup(table, flp, res))
        return 0;
    return -ENETUNREACH;
}

fib_get_table比较简单，就是通过id，从net->ipv4.fib_table_hash中取出对应的路由表——对于IPv4来说。

那么查找路由的核心函数就为fib_table_lookup，这个函数的实现依赖于编译选项，共有两种实现方式，hash和trie。其中hash的实现比较简单，今天先学习hash的实现方式。

int fib_table_lookup(struct fib_table *tb,
             const struct flowi *flp, struct fib_result *res)
{
    int err;
    struct fn_zone *fz;
    /* 得到真正的route hash表 */
    struct fn_hash *t = (struct fn_hash *)tb->tb_data;

    read_lock(&fib_hash_lock);
    /* 按顺序从fn_zone中查找路由，详细解释见后文 */
    for (fz = t->fn_zone_list; fz; fz = fz->fz_next) {
        struct hlist_head *head;
        struct hlist_node *node;
        struct fib_node *f;
/* 计算key，实际就是dst的网络部分 */
        __be32 k = fz_key(flp->fl4_dst, fz);

         /* 计算hash */

        head = &fz->fz_hash[fn_hash(k, fz)];

 /* 在桶中遍历所有路由条目 */

        hlist_for_each_entry(f, node, head, fn_hash) {
            /* 地址网络部分的值不同，该路由肯定不符，跳过 */
            if (f->fn_key != k)
                continue;

             /* 对路由进行其它的比较，如tos等 */

            err = fib_semantic_match(&f->fn_alias,
                         flp, res,
                         fz->fz_order);
            if (err <= 0)
                goto out;
        }
    }
    err = 1;
out:
    read_unlock(&fib_hash_lock);
    return err;
}

从上面看，路由表的hash查找是比较简单的。唯一的疑惑就是这个struct fn_zone。

下面是路由hash表的数据结构

struct fn_hash {
    struct fn_zone    *fn_zones[33];
    struct fn_zone    *fn_zone_list;
};

路由hash表将路由条目按照掩码长度分到不同的33个fn_zones中，掩码长度为0即对应fn_zones[0]，掩码长度为1即fn_zones[1]，一直到掩码长度为32，则对应fn_zones[32]。而fn_zone_list指向的是最长的有路由条目的fn_zones。这样查找路由的时候，通过fn_zone_list顺序查找，从而实现了路由的最佳匹配。

今天基本上学习了kernel的路由表的hash实现方式。下面有可能将hash实现的完整的路由数据组织结构写出来，或者转到路由表trie的实现方式。