一．前言

我对linux2.4.18的相关代码进行了阅读，从关键的几个接口函数入手，进而理清了整个路由部分的主要脉胳，理解了一些细节问题的处理，但还是有些问题还没有完全搞清楚。

路由部分代码主要在linux代码树的/net/ipv4/下面：

对于下面报告内容的组织，我想通过由整体到部分到细节的顺序，尽量把我阅读代码学习到的所有的知识做一个有层次有条理的总结。

二．概述

1.       基于策略的路由

目前在计算机网络中使用的传统路由算法都是根据IP包目的地址进行路由选择.然而在现实应用中经常有这样的需求：进行路由选择时不仅仅根据数据报的目的地址，而且根据数据报的其他一些特性如：源地址、IP协议、传输层端口，甚至是数据包的负载部分内容，这种类型的路由选择被称作基于策略的路由。

2.       路由策略数据库

 在Linux中，从2.1版本的内核开始就实现了对基于策略的路由的支持，它是通过使用路由策略数据库(RPDB，routing policy database)替代传统的、基于目的地址的路由表来实现的。RPDB通过包含的一些规则和多张路由表来选定合适的IP路由。这些规则可能会包含很多各种不同类型的键值(key)，因此这些规则没有默认的特定次序，规则查找次序或规则优先级都是由网络或系统管理员设定的。

如下图所示，Linux的RPDB是一个由数字优先级值进行排序的线性规则列表。RPDB能匹配数据报源地址、目的地址、TOS、进入接口和fwmark值等。每个路由策略规则由一个选择器和一个动作指示组成。RPDB按照优先级递增的顺序被扫描，RPDB包含的每条规则的选择器被应用于数据报的源地址、目的地址、进入接口、TOS和fwmark值。若数据报匹配该规则对应于该规则的动作被执行。若动作成功返回，则规则输出将是一个有效的路由或是路由查找失败指示；否则查找RPDB的下一条规则。规则的动作通常是查一张与之对应的路由表，但也可以是如下几种：REJECT(丢弃)，PROHIBIT或决UNRECHABLE(丢弃并向源地址发送ICMP包)，NAT(源地址网络地址转换)等。路由表项的类型除了表示指出下一跳的相关信息外，还可以表示：BLACKHOLE(丢弃)，PROHIBIT或UNREACHABL(丢弃并向源地址发送ICMP包)E，NAT(目的地址网络地址转换)等。

由图中所示，系统默认已经实现了三个策略（本地策略、主策略和默认策略），与之对应的是三张默认路由表（本地路由表、主路由表和默认路由表）

3.       相关代码

我们主要分析了linux2.4.18内核关于路由部分的代码，主要如下：

linux/net/ipv4/*

• route.c　提供了路由部分给IP层调用的接口。
• fib_rules.c　提供对路由策略数据库的查找接口，并维护策略表。
• fib_hash.c 　对路由表的查找，维护等。
• fib_semantics.c　路由表的语义操作，维护路由项信息表(fib_info_list)。
• fib_frontend.c　提供对路由表进行操作的接口。
• linux/include/net/*
• route.h　路由cache中相关的一些数据结构。
• ip_fib.h　定义了路由部分很多重要的结构。
• neighbour.h　struct neighbour的定义。
• dst.h　对路由cache结点中dst_entry结构的定义。
• linux/net/core/*
• dst.c　对路由cache结点分配等动作。
• neighbour.c　neighbour结构相关操作。

三．路由部分结构

1.       总体结构

内核路由部分代码实际上是ipv4协议栈的一部分，它被ip层的代码所调用。主要的调用时机有两个：一个是IP包输出时，需要确定由哪个端口出去；另一个是IP包输入时，需要确定是发给本机还是选择一个端口发送出去。

整个路由系统可以分成三部分：IP层调用接口，路由策略数据库，和前后端接口。

1． IP层调用接口主要是提供一组调用接口给IP层代码，这些接口最终完成了整个的路由工作。为了提高效率，这部分代码维护了一个路由策略数据库的缓存或者叫cache，这部分代码另一个主要功能就是维护这个缓存了。这部分的代码主要在route.c文件中。

2． 路由策略数据库部分主要包括一个策略库和多张路由表，还有一些相关的操作它们的函数。当路由缓存没有命中的情况下，就要由这部分完成最后的查找工作。这部分的代码主要在fib_rules.c，fib_hash.c，fib_semantics.c中。

3．前底端接口部分主要是给用户提供的一些对路由策略数据库增删改的操作函数，对/proc接口的实现，以及一些定时器的操作。这部分代码主要在fib_frontend.c中，还有一些分散在其它文件中。

2.       IP接口部分结构

这部分即是route.c的内容，主要定义了路由cache还有提供给IP层调用的几个接口函数。

我们先来介绍一下路由cache的定义：

这个rt_hash_table即是路由cache，它是一个rt_hash_bucket结构：

struct rtable的结构定义如下：

实际上这个rt_hash_table就是一张hash table。每个hash值相同的结点都挂在一个list上即struct rt_hash_bucket的chain成员，它的lock成员用于对这个list进行加锁以实现临界资源的互斥访问。

每个结点是一个rtable结构，这个结构比较重要，实际上路由查询的最终结果就是把一个对应的rtable结构的地址赋给skb->dst。这个结构的域key就是hash表检索时所用来比较的关键字，这个结构包含了dst(目标地址),src(源地址),iif(入端口),oif(出端口),tos(服务类型),scope(目标地址的范围)，这些也就是查找路由缓存时所要匹配的值，即如果这些都匹配了，那么说明cache命中，否则还要继续检索。

下面这个图显示了路由缓存的完整结构：

这一部分主要提供了两个供IP层调用的入口函数：

int ip_route_input( struct sk_buff* skb, u32 dst, u32src, u8 tos, 

struct net_device *dev );

int ip_route_output( struct rtable **rp, u32 daddr, u32 saddr, 

u32 tos, int oif )

其中ip_route_input函数即是在处理从网络上进来的IP包时调用的路由函数，它的结果主要有两个：即如果是本地包则传给上层协议层，如果不是则选则一个出端口再发送出去。函数的参数有5个：skb表示ip包的缓冲区，dst目的地址，src源地址，tos表示IP包服务类型，dev表示入端口。函数返回值指示错误，如果成功查到路由，函数返回后，skb->dst会被赋值。

与之相对ip_route_output函数则是处理本机发出的IP包时调用的路由函数，它的结果只是为其选择一个下一跳以及出端口。参数也是5个：rp是个输出参数，返回时*rp指向一个返回的rtable结构的路由结点；daddr目的地址，saddr源地址，tos服务类型，oif出接口。函数返回值指示错误。

这一部分其它一些比较重要的函数有：

ip_route_input_slow：当ip_route_input查cache不命中时调用此函数，此函数进而调用路由策略数据库的查询接口进行查询，然后更新路由cache。

ip_route_output_slow：当ip_route_output查cahe不命中是调用此函数，此函数进而调用路由策略数据库的查询接口进行查询，然后更新路由cache。

rt_intern_hash：将新rtable结构的结点插入到路由缓存中。

rt_garbage_collect：对路由缓存进和垃圾收集。

3.       路由策略数据库部分结构

这一部分主要包括策略表及路由表的定义，以及查询等操作。

①　策略表

static struct fib_rule *fib_rules = &local_rule;

fib_rules即是策略表，它是一个fib_rule结构：

struct fib_rule　{

        struct fib_rule *r_next;

        atomic_t        r_clntref;

        u32             r_preference;

        unsigned char   r_table;

        unsigned char   r_action;

        unsigned char   r_dst_len;

        unsigned char   r_src_len;

        u32             r_src;

        u32             r_srcmask;

        u32             r_dst;

        u32             r_dstmask;

        u32             r_srcmap;

        u8              r_flags;

        u8              r_tos;

        int             r_ifindex;

        char            r_ifname[IFNAMSIZ];

        int             r_dead;

};

整个策略表的结构如下图：

这个策略表实际上就是一个单链表，整个单链表按策略的优先级由高到低的顺序排列，表头指针即是fib_rule。每个策略是一个fib_rule结构。这个结构有几个重要的域：

r_preference 这个策略的优先级。

r_table 这个策略对应的路由表，它是路由表索引表fib_tables的一个索引值。

r_action 策略的动作，如单播，丢弃，NAT等。

r_src,r_srcmask,r_dst,r_dstmask,r_tos等　策略的选择器，即描述什么样的IP包匹配这条策略。

系统默认已经定义了三个策略：

static struct fib_ruledefault_rule = {

        r_clntref:      ATOMIC_INIT(2),

        r_preference:   0x7FFF,

        r_table:        RT_TABLE_DEFAULT,

        r_action:       RTN_UNICAST,

};

static struct fib_rulemain_rule = {

        r_next:         &default_rule,

        r_clntref:      ATOMIC_INIT(2),

        r_preference:   0x7FFE,

        r_table:        RT_TABLE_MAIN,

        r_action:       RTN_UNICAST,

};

static struct fib_rulelocal_rule = {

        r_next:         &main_rule,

        r_clntref:      ATOMIC_INIT(2),

        r_table:        RT_TABLE_LOCAL,

        r_action:       RTN_UNICAST,

};

可以看到这三个策略（本地策略，主策略，默认策略）按照优先级的由高到低的次序排列，它们的选择器都是0，即表示匹配所有类型的IP包。它们的动作都是单播就表示都是查对应的路由表。它们分别对应三张路由表（本地路由表，主路由表，默认路由表）。其意义就是对于一个IP包，系统总是按本地路由表->主路由表->默认路由表的次序进行查找的。

 ②　路由表

定义如下：

struct fib_table *local_table;

struct fib_table *main_table;

struct fib_table *fib_tables[RT_TABLE_MAX+1];

它的数据结构是：

struct fib_table

{

        unsigned char   tb_id;

        unsigned        tb_stamp;

        int 　　　　　　(*tb_lookup)(struct fib_table *tb, const struct rt_key *key, struct fib_result *res);

        int             (*tb_insert)(…);

       int             (*tb_delete)(…);

       int             (*tb_dump)(…);

       int             (*tb_flush)(struct fib_table *table);

       int             (*tb_get_info)(…);

       void            (*tb_select_default)(…);

       unsigned char   tb_data[0];

};

fib_table[]是系统中所有路由表的索引数组。系统另外定义了两个路由表指针local_table和main_table，分别指向默认定义的两个路由表。在前面我们曾介绍系统定义了三张路由表，还有一张即是默认路由表，实际上它只是一张空表，一般并没有用到。

实际上,fib_table结构只是一个路由表结构中最上层的一个结构，它下面还很多的层次，下面这张图描绘了整个路由表的数据结构：

整个结构看起来比较复杂，我们可以把它分成4个层次来看：

第一个层次是fib_table和fn_hash结构。实际上，fn_hash结构即是fib_table的tb_data域。这一层主要是包括一个路由表所对应的标识符(tb_id)，操作函数指针(tb_looup等)，以及对所有路由项的一个总索引(fn_hash结构)。最为重要的就是这个索引，一个路由表把它所有的路由项划分成33个区域，划分的原则即是子网掩码的长度（从0到32），这33个区域分别对应着fn_hash结构中的fz_zone[0]到fz_zone[32]。之所以这么划分的原因就因为，路由的表的查找要从最精确到最不精确，也就是说要从掩码最长的路由项查起。

第二个层次是fn_zone结构。每个fn_zone代表了一个区域，由于并不是33个区域都会同时存在，一般往往只有常用到的掩码长度（如0,16,24,32位）对应的区域才存在，所以所有存在的区域按从大到小的顺序被链成一个list，从而提高查找的效率。这人fn_zone结构中最重要的就是fz_hash域了，它指向了一个hash table，这个hash table组织了这个区域下的所有路由项。

第三个层次是代表路由项的fn_node结构。它是hash table的结点，其中fn_key域即是hash查找的关键字，它实际上就是路由项的目标网络号。这个结构的提供了路由查找的结果信息，fn_type这个域指示了这个路由项的含义：单播转发，本地，丢弃，NAT等等。对于大多数情况，路由项都是单播转发类型的，这时关于下一跳的信息就入在fn_info中了，它指向一个fib_info结构。

第四个层次即是fib_info结构。因为很多的路由项具有相同的下一跳信息，即fn_node与fib_info结构是多对一的关系。所以fn_node中只存放一个指向fib_info的指针fn_info。所有fib_info结构被单独管理，它们被组织成一个双向链表，表头为fib_info_list。关于下一跳的具体信息由fib_nh[]数组指示，它是一个数组意味着一个下一跳决策可以对应着多个物理的下一跳，这是linux支持的一个MULITPATH功能。

③　处理函数

这部分的处理函数中最为重要的就是对路由策略数据库的查找函数fib_lookup，以及对单个路由表进行查找的fn_hash_lookup函数。

fib_lookup的定义:

int fib_lookup(const struct rt_key *key, struct fib_result *res)

这个函数的工作就是对整个路由策略数据库进行查找，它会在需要的时候调用fn_hash_lookup查找特定的路由表。函数有两个参数，key是查找的关键字，它与路由缓存查找时的key是一致的。res是输出参数，函数返回后如果成功则在res存入查找结果。函数的返回值用来指示错误。

static int　fn_hash_lookup(struct fib_table *tb, const struct rt_key *key, struct fib_result *res)

这个函数的即是对路由进行查找。参数有3个，tb指示待查的路由表，key查找关键字，res指向的结构存放查找的结果。函数返回值指示错误。

4.       接口部分结构

这一部分主要实现以下几个功能：

1．对路由表，策略表进行增加项，删除项，创建表，表空路由缓存等操作。

2．为路由策略数据库，路由缓存提供/proc接口。

3．设置定时器，以定时对路由缓存进行清理工作。