路由数据库之路由表项的查找

路由数据库的查询是通过调用路由表struct fib_table的tb_lookup回调完成的，该回调函数是在路由表创建的时候就指定的，对于哈希方式的AF_INET路由表，该接口是fn_hash_lookup()，这篇笔记就是来记录该查询过程的。

1. 路由查询条件struct flowi

该结构也会被其他协议族使用，所以使用了很多联合体。

struct flowi {
	//可以指定要匹配的输出接口和输出接口，取值都是设备的index。这两个字段属于层二查询条件
	int	oif;
	int	iif;
	//数据包的mark值，一般来讲，数据包在netfilter时，会根据接收网卡打上不同的标记
	__u32	mark;
	//下面这个联合体包含了层三的地址信息，属于层三查询条件
	union {
		//对于IPv4，地址信息方面可以匹配源IP、目的IP、TOS和作用域
		struct {
			__be32			daddr;
			__be32			saddr;
			__u8			tos;
			__u8			scope;
		} ip4_u;

		struct {
			struct in6_addr		daddr;
			struct in6_addr		saddr;
			__be32			flowlabel;
		} ip6_u;

		struct {
			__le16			daddr;
			__le16			saddr;
			__u8			scope;
		} dn_u;
	} nl_u;
#define fld_dst		nl_u.dn_u.daddr
#define fld_src		nl_u.dn_u.saddr
#define fld_scope	nl_u.dn_u.scope
#define fl6_dst		nl_u.ip6_u.daddr
#define fl6_src		nl_u.ip6_u.saddr
#define fl6_flowlabel	nl_u.ip6_u.flowlabel
#define fl4_dst		nl_u.ip4_u.daddr
#define fl4_src		nl_u.ip4_u.saddr
#define fl4_tos		nl_u.ip4_u.tos
#define fl4_scope	nl_u.ip4_u.scope

	//下面这些字段属于层四查询条件
	__u8	proto;
	__u8	flags;
#define FLOWI_FLAG_ANYSRC 0x01
	union {
		struct {
			__be16	sport;
			__be16	dport;
		} ports;

		struct {
			__u8	type;
			__u8	code;
		} icmpt;

		struct {
			__le16	sport;
			__le16	dport;
		} dnports;

		__be32		spi;

		struct {
			__u8	type;
		} mht;
	} uli_u;
#define fl_ip_sport	uli_u.ports.sport
#define fl_ip_dport	uli_u.ports.dport
#define fl_icmp_type	uli_u.icmpt.type
#define fl_icmp_code	uli_u.icmpt.code
#define fl_ipsec_spi	uli_u.spi
#define fl_mh_type	uli_u.mht.type
	__u32           secid;	/* used by xfrm; see secid.txt */
} __attribute__((__aligned__(BITS_PER_LONG/8)));

2. 路由查询结果struct fib_result

struct fib_result {
	//目的地址的掩码长度
	unsigned char	prefixlen;
	//只是下一跳地址struct fib_nh就是fi->fib_nh[nh_sel]中
	unsigned char	nh_sel;
	//该目的地址的类型
	unsigned char	type;
	//该目的地址的作用域
	unsigned char	scope;
	//指向路由信息结构
	struct fib_info *fi;
#ifdef CONFIG_IP_MULTIPLE_TABLES
	//支持策略路由的场景，指向匹配该路由的的策略路由规则
	struct fib_rule	*r;
#endif
};

3. 路由表查询接口：fn_hash_lookup()

static int fn_hash_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
{
	int err;
	struct fn_zone *fz;
	struct fn_hash *t = (struct fn_hash*)tb->tb_data;

	read_lock(&fib_hash_lock);
	//遍历路由区,因为并不知道该数据包的目的IP地址的子网掩码，所以需要遍历所有的路由区,
	//因为fn_zone_list是按照子网掩码长度由大到小维护的，所以这个匹配顺序就是最长匹配
	for (fz = t->fn_zone_list; fz; fz = fz->fz_next) {
		struct hlist_head *head;
		struct hlist_node *node;
		struct fib_node *f;
		//flp->fl4_dst就是数据包中的目的IP地址，最后的k值就是该IP地址对应的网络号
		__be32 k = fz_key(flp->fl4_dst, fz);
		//遍历路由区中k索引的路由结点冲突链表
		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,
						 f->fn_key, fz->fz_mask,
						 fz->fz_order);
			if (err <= 0)
				goto out;
		}
	}
	err = 1;
out:
	read_unlock(&fib_hash_lock);
	return err;
}

3.1. fib_semantic_match()

最终的查询条件判决是由fib_semantic_match()完成的，下面看其实现：

/* Note! fib_semantic_match intentionally uses  RCU list functions. */
int fib_semantic_match(struct list_head *head, const struct flowi *flp,
		       struct fib_result *res, __be32 zone, __be32 mask,
			int prefixlen)
{
	struct fib_alias *fa;
	int nh_sel = 0;
	//遍历特定路由结点的路由项列表
	list_for_each_entry_rcu(fa, head, fa_list) {
		int err;
		//如果路由表项中的tos字段设置了值，那么TOS字段需要匹配
		if (fa->fa_tos && fa->fa_tos != flp->fl4_tos)
			continue;
		//路由表项的作用域不能低于IP地址的作用域，即路由表项所指目的地址要比待查询地址更加的精确
		if (fa->fa_scope < flp->fl4_scope)
			continue;
		//后面就要访问该路由表项的内容了，所以这里设置其“访问”标记
		fa->fa_state |= FA_S_ACCESSED;

		//下面检查路由信息中的type、oif是否匹配
		err = fib_props[fa->fa_type].error;
		if (err == 0) {
			struct fib_info *fi = fa->fa_info;
			//跳过下一条地址已经无效的路由信息
			if (fi->fib_flags & RTNH_F_DEAD)
				continue;

			switch (fa->fa_type) {
			case RTN_UNICAST:
			case RTN_LOCAL:
			case RTN_BROADCAST:
			case RTN_ANYCAST:
			case RTN_MULTICAST:
				//对于这些类型的路由项
				for_nexthops(fi) {
					//如果地址已经无效，继续查询
					if (nh->nh_flags&RTNH_F_DEAD)
						continue;
					//如果条件中指定了具体的输出接口，则条件和路由表项的条件要匹配
					//如果查询条件没有指定输出端口，则会选中第一个有效的路由表项
					if (!flp->oif || flp->oif == nh->nh_oif)
						break;
				}
				//如果找到了下一跳地址信息，其索引保存会保存nhsel变量中
#ifdef CONFIG_IP_ROUTE_MULTIPATH
				if (nhsel < fi->fib_nhs) {
					nh_sel = nhsel;
					goto out_fill_res;
				}
#else
				//对于不支持多IP路径的情况，如果找到，该索引一定是0
				if (nhsel < 1) {
					goto out_fill_res;
				}
#endif
				endfor_nexthops(fi);
				continue;

			default:
				printk(KERN_WARNING "fib_semantic_match bad type %#x\n",
					fa->fa_type);
				return -EINVAL;
			}
		}//end of err
		return err;
	}
	return 1;

out_fill_res:
	//到这里，路由查询成功，填充查询结果
	res->prefixlen = prefixlen;
	res->nh_sel = nh_sel;
	res->type = fa->fa_type;
	res->scope = fa->fa_scope;
	res->fi = fa->fa_info;
	//将struct fib_info结构体的引用计数加1
	atomic_inc(&res->fi->fib_clntref);
	return 0;
}

注意到，上面在路由项匹配过程中，遍历struct fib_info的fib_nh数组时使用了两个简单的宏，如下：

#ifdef CONFIG_IP_ROUTE_MULTIPATH
//如果支持多路径路由，需要遍历下一跳数组
#define for_nexthops(fi) { int nhsel; const struct fib_nh * nh; \
for (nhsel=0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++)
#else
//如果不支持多路径路由，只需要遍历一次
/* Hope, that gcc will optimize it to get rid of dummy loop */
#define for_nexthops(fi) { int nhsel = 0; const struct fib_nh * nh = (fi)->fib_nh; \
for (nhsel=0; nhsel < 1; nhsel++)
#endif

#define endfor_nexthops(fi) }

实际上有个疑点，为什么不统一呢，看代码完全可以统一呀，难道和注释所说的gcc优化有关？