内核的路由部分是是网络中重要部分，目前在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中查找的结构图：
首先通过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，我们需要看一下结构直接的关系：
ok，我们由规则找到了我们需要的三张表，三张表按照优先级的顺序进行查询，现在就以Local表为例进行下面具体的查询，看下图：
从图中我们可以看到四个等级查询：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功能。
说到这来，大致的印象应该是有的，下面需要做的就是深入代码细节。
待续... 后面会介绍相关的代码...