1. 全局路由哈希表

内核将所有的路由表（struct fib_table)组织到哈希表net->ipv4.fib_table_hash中，如下：

//如果不支持策略路由，那么系统中固定只有两张路由表，所以哈希表大小就是2，
//如果支持策略路由，那么系统中可以支持多个表，所以定义一个冲突链数目为256的哈希表
//来保存这些路由表
#ifdef CONFIG_IP_ROUTE_MULTIPATH
#define FIB_TABLE_HASHSZ 2
#else
#define FIB_TABLE_HASHSZ 256
#endif

//分配哈希表并初始化各个冲突链的头结点
static int __net_init ip_fib_net_init(struct net *net)
{
	...
	net->ipv4.fib_table_hash = kzalloc(
			sizeof(struct hlist_head)*FIB_TABLE_HASHSZ, GFP_KERNEL);
	if (net->ipv4.fib_table_hash == NULL)
		return -ENOMEM;
	
	for (i = 0; i < FIB_TABLE_HASHSZ; i++)
		INIT_HLIST_HEAD(&net->ipv4.fib_table_hash[i]);
	   ...
}

2. 路由表struct fib_table

struct fib_table {
	//将该路由表链入系统全局哈希表中
	struct hlist_node tb_hlist;
	//每张路由表在系统中都有一个唯一的ID
	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];
};

3. 路由区struct fn_zone

注意到路由表结构struct fib_table的末尾有一个零长度数组，在实际分配内存时，会在该结构末尾再分配一个struct fn_hash结构，该结构的定义如下：

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

成员fn_zones是一个长度为33的指针数组，系统将路由项按照目的地址的子网掩码长度不同划分为33个区管理（对于IPv4，掩码长度可取的值为0~32，所以是33个），我们后续称fn_zone为路由区。

成员fn_zone_list用于将所有活动的（含有路由表项）的路由区按照子网掩码长度由大到小的顺序串联成单链表，之所以这样设计，是为了更加方便按照最大长度匹配原则进行路由查找。

fib_table和fn_hash的内存结果如下图所示：

一个路由区管理的是一组路由表项，这些路由表项的目的地址的子网掩码长度相同。然而，子网掩码相同，网络地址还可以不同，为了高效的存取，路由区进一步用哈希表来组织这些不同的网络地址（每个网络地址对应一个fib_node，后续我们称该结构为路由结点)，路由区的定义如下：

struct fn_zone {
	//与struct fn_hash结构中的fn_zone_list一起，将所有活动的路由区按照子网掩码长度由大到小的顺序串联成单链表
	struct fn_zone		*fz_next;	/* Next not empty zone	*/
	//保存struct fib_node(即路由结点)的哈希表指针
	struct hlist_head	*fz_hash;	/* Hash table pointer	*/
	//哈希表中路由结点的数目
	int			fz_nent;	/* Number of entries	*/
	//哈希表桶大小，哈希表在实际使用过程中可能会重新分配更大的空间，避免冲突过多
	int			fz_divisor;	/* Hash divisor		*/
	//值为fz_divisor-1，用于计算哈希值
	u32			fz_hashmask;	/* (fz_divisor - 1)	*/
#define FZ_HASHMASK(fz)		((fz)->fz_hashmask)
	//子网掩码中1的数目，即对于子网掩码255.255.255.0，那么fz_order为24
	int			fz_order;	/* Zone order		*/
	//子网掩码的数值大端表示
	__be32			fz_mask;
#define FZ_MASK(fz)		((fz)->fz_mask)
};

4. 路由结点struct fib_node

路由结点将所有目的地址的网络地址相同的路由表项组织到一起，由于目的地址相同，但是还可以根据tos、priority等参数配置不同的路由项，所以路由结点下面也可能会有多个路由表项，路由结点的定义如下：

struct fib_node {
	//用于将路由结点组织到路由区的哈希表中
	struct hlist_node	fn_hash;
	//路由结点将可能存在的多个路由项组织成链表，链表成员为struct fib_alias
	struct list_head	fn_alias;
	//该路由结点代表的网络地址，即IP地址与子网掩码相与后的结果
	__be32			fn_key;
	//分配路由节点的时候同时也分配一个路由别名，所以称为嵌入式的
	struct fib_alias        fn_embedded_alias;
};

5. 路由表项struct fib_alias

真正的路由表项是struct fib_alias,所有的目的地址的网络地址相同的路由表项被组织成一个路由结点，它们被路由结点组织成链表，路由表项的定义如下：

struct fib_alias {
	//路由表项被路由结点组织成一个链表
	struct list_head	fa_list;
	//命中该路由后，对数据包应该执行怎样的操作，即如何路由，这些信息被组织成struct fib_info
	struct fib_info		*fa_info;
	//服务类型TOS，对于IP数据包，对应其头部的TOS字段
	u8			fa_tos;
	//路由类型
	u8			fa_type;
	//路由作用范围
	u8			fa_scope;
	//路由项的状态
	u8			fa_state;
#ifdef CONFIG_IP_FIB_TRIE
	struct rcu_head		rcu;
#endif
};

6. 路由信息struct fib_info

在实际中，可能有很多的路由表项命中后要执行的动作是一样的，这些信息是可以共用的，没有必要每个路由表项都维护一份，所以将这部分信息抽象成路由信息，这就是struct fib_info，该结构定义如下：

/*
 * This structure contains data shared by many of routes.
 */
struct fib_info {
	//用于将所有的fib_info结构组织到fib_info_hash队列中
	struct hlist_node	fib_hash;
	//用于将所有的fib_info结构组织到fib_hash_laddrhash队列中
	struct hlist_node	fib_lhash;
	struct net		*fib_net;
	//该fib_info结构的引用计数
	int			fib_treeref;
	atomic_t		fib_clntref;
	int			fib_dead;
	//RTNH_F_DEAD: 表示该路由信息的下一跳地址无效
	unsigned		fib_flags;
	int			fib_protocol;
	//优选IP地址，当路由所指网卡有多个IP地址时，可以通过该字段指示优先选用什么IP地址
	__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]
	//fib_nh数组的元素个数，即可用下一条地址数目，通常为1，只有在支持多路径路由时
	//该值才有可能大于1
	int			fib_nhs;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
	int			fib_power;
#endif
	//零长度数组，指向一个struct fib_nh，该结构决定了下一跳地址信息
	struct fib_nh		fib_nh[0];
#define fib_dev		fib_nh[0].nh_dev
};

7. 路由下一跳struct fib_nh

进一步考虑，一台机器的网络设备毕竟是有限的，所以需要路由表项最终的下一条地址信息是重复的，将这种下一跳信息抽象出来就是struct fib_nh，定义如下：

struct fib_nh {
	struct net_device	*nh_dev;
	struct hlist_node	nh_hash;
	struct fib_info		*nh_parent;
	unsigned		nh_flags;
	unsigned char		nh_scope;
#ifdef CONFIG_IP_ROUTE_MULTIPATH
	int			nh_weight;
	int			nh_power;
#endif
#ifdef CONFIG_NET_CLS_ROUTE
	__u32			nh_tclassid;
#endif
	int			nh_oif;
	__be32			nh_gw;
};

以上就是路由表本身涉及到的核心数据结构，实际上还是非常复杂的，它们之间的连接关系见下图: