存档

2011年3月 的存档

浅析Linux Kernel 哈希路由表实现(二)

三月 15th, {2011 1 条评论 16,202 人阅读过  

在向外发送数据包的时候,首先需要查询路由表来确定路由包的路由,主要由ip_route_output_key()函数来完成,该函数又调用了ip_route_output_flow(),而这个函数最终又调用了__ip_route_output_key()这个函数来进行路由的查询,下面主要来看一下这个函数:

int __ip_route_output_key(struct net *net, struct rtable **rp,
			  const struct flowi *flp)
{
	unsigned int hash;
	int res;
	struct rtable *rth;
 
	if (!rt_caching(net))
		goto slow_output;
 
	hash = rt_hash(flp->fl4_dst, flp->fl4_src, flp->oif, rt_genid(net));
 
	rcu_read_lock_bh();
	for (rth = rcu_dereference_bh(rt_hash_table[hash].chain); rth;
		rth = rcu_dereference_bh(rth->dst.rt_next)) {
		if (rth->fl.fl4_dst == flp->fl4_dst &&
		    rth->fl.fl4_src == flp->fl4_src &&
		    rth->fl.iif == 0 &&
		    rth->fl.oif == flp->oif &&
		    rth->fl.mark == flp->mark &&
		    !((rth->fl.fl4_tos ^ flp->fl4_tos) &
			    (IPTOS_RT_MASK | RTO_ONLINK)) &&
		    net_eq(dev_net(rth->dst.dev), net) &&
		    !rt_is_expired(rth)) {
			dst_use(&rth->dst, jiffies);
			RT_CACHE_STAT_INC(out_hit);
			rcu_read_unlock_bh();
			*rp = rth;
			return 0;
		}
		RT_CACHE_STAT_INC(out_hlist_search);
	}
	rcu_read_unlock_bh();
 
slow_output:
	rcu_read_lock();
	res = ip_route_output_slow(net, rp, flp);
	rcu_read_unlock();
	return res;
}

Linux的路由表中的常用路由是存储在路由缓存中的,该路由缓存即是类型为struct rt_hash_bucket的全局列表rt_hash_table,该缓存列表在ip_rt_init()中初始化。

struct flowi结构中包含了查询路由表所需要的请求信息,是一个搜索健值。由代码可看出,首先在路由缓存列表rt_hash_table中查询精确匹配的未过期的路由表项struct rtable,(注,因为是出口路由,所以入口接口号是0),若找到后增加路由表项的引用计数和后即刻返回。若未找到匹配的路由表项,则继续在路由表中查找匹配的路由表项,路由表中的查询速度会比路由缓存中慢,所以ip_route_output_slow()函数的命名就不难理解了,主动的路由解析工作都是在这个函数里面进行的,在看它的定义之前先看下服务类型和路由范围的相关 定义:

#define IPTOS_TOS_MASK		0x1E
#define IPTOS_TOS(tos)		((tos)&IPTOS_TOS_MASK)
#define	IPTOS_LOWDELAY		0x10	/* 最小延时 */
#define	IPTOS_THROUGHPUT	0x08	/* 最大吞吐量 */
#define	IPTOS_RELIABILITY	0x04	/* 最高可靠性 */
#define	IPTOS_MINCOST		0x02	/* 最小消费 */
#define RTO_ONLINK          0x01

由掩码可知,服务类型实际上用了从第2位到第5位共四位的数据,表示四种服务类型,而最低位的RTO_ONLINK如果置位,则scope为RT_SCOPE_LINK,或没有,则scope为RT_SCOPE_UNIVERSE,接下来看看scope的相关定义:

enum rt_scope_t {
	RT_SCOPE_UNIVERSE=0,		/* 表示在空间中的任何位置 */
/* User defined values  */
	RT_SCOPE_SITE=200,
	RT_SCOPE_LINK=253,			/* 与本地直接相连的地址 */
	RT_SCOPE_HOST=254,			/* 本地地址 */
	RT_SCOPE_NOWHERE=255		/* 不可达的地址 */
};

其中值越大所表示的范围便越精确,实际上这也不是什么范围的意思,只不过是到目的地址的某种距离的表示。OK,接下来看ip_route_output_slow()函数的定义:

static int ip_route_output_slow(struct net *net, struct rtable **rp,
				const struct flowi *oldflp)
{
	u32 tos	= RT_FL_TOS(oldflp);
	struct flowi fl = { .nl_u = { .ip4_u =
				      { .daddr = oldflp->fl4_dst,
					.saddr = oldflp->fl4_src,
					.tos = tos & IPTOS_RT_MASK,
					.scope = ((tos & RTO_ONLINK) ?
						  RT_SCOPE_LINK :
						  RT_SCOPE_UNIVERSE),
				      } },
			    .mark = oldflp->mark,
			    .iif = net->loopback_dev->ifindex,
			    .oif = oldflp->oif };
	struct fib_result res;
	unsigned int flags = 0;
	struct net_device *dev_out = NULL;
	int err;
 
 
	res.fi		= NULL;
#ifdef CONFIG_IP_MULTIPLE_TABLES
	res.r		= NULL;
#endif
 
	if (oldflp->fl4_src) {
		/* 若源地址为组播地址,受限广播地址(255.255.255.255)或0地址,
		均不合法,即刻返回 */
		err = -EINVAL;
		if (ipv4_is_multicast(oldflp->fl4_src) ||
		    ipv4_is_lbcast(oldflp->fl4_src) ||
		    ipv4_is_zeronet(oldflp->fl4_src))
			goto out;
 
		if (oldflp->oif == 0 &&
		    (ipv4_is_multicast(oldflp->fl4_dst) ||
		     ipv4_is_lbcast(oldflp->fl4_dst))) {
			/* 等价于inet_addr_type(saddr) == RTN_LOCAL, 
			__ip_dev_find()函数实际是搜索RT_TABLE_LOCAL
			路由表中的路由表项,如果未找到对应设备则返回,因为
			Linux不允许环回接口发组播或受限广播 */
			dev_out = __ip_dev_find(net, oldflp->fl4_src, false);
			if (dev_out == NULL)
				goto out;
 
			/* 给外面接口赋值后转去创建路由缓存 */
			fl.oif = dev_out->ifindex;
			goto make_route;
		}
 
		if (!(oldflp->flags & FLOWI_FLAG_ANYSRC)) {
			/* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
			if (!__ip_dev_find(net, oldflp->fl4_src, false))
				goto out;
		}
	}
 
 
	if (oldflp->oif) {
		dev_out = dev_get_by_index_rcu(net, oldflp->oif);
		err = -ENODEV;
		if (dev_out == NULL)
			goto out;
 
		/* 如果外出接口示启用或外出接口对应的IPv4数据不存在,则返回网络不可达 */
		if (!(dev_out->flags & IFF_UP) || !__in_dev_get_rcu(dev_out)) {
			err = -ENETUNREACH;
			goto out;
		}
		/* 若是本地组播地址或受限广播地址则直接转去创建路由缓存 */
		if (ipv4_is_local_multicast(oldflp->fl4_dst) ||
		    ipv4_is_lbcast(oldflp->fl4_dst)) {
			if (!fl.fl4_src)
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      RT_SCOPE_LINK);
			goto make_route;
		}
 
		/* 若未指定源地址,则根据目地地址类型创建选择一个源地址 */
		if (!fl.fl4_src) {
			if (ipv4_is_multicast(oldflp->fl4_dst))
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      fl.fl4_scope);
			else if (!oldflp->fl4_dst)
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      RT_SCOPE_HOST);
		}
	}
 
	/* 如果目的地址不存在,则令目的地址等于源地址,若都不存在,则使用环回接口,
		路由类型为本地路由,转而创建路由缓存 */
	if (!fl.fl4_dst) {
		fl.fl4_dst = fl.fl4_src;
		if (!fl.fl4_dst)
			fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
		dev_out = net->loopback_dev;
		fl.oif = net->loopback_dev->ifindex;
		res.type = RTN_LOCAL;
		flags |= RTCF_LOCAL;
		goto make_route;
	}
/*
OK, 走到这里先总结一下不需要查询路由表即可直接创建路由缓存的情况:
1. 指定了源地址,未指定外出接口,目的地址为组播地址或受限广播地址
2. 指定了外出接口,并且目的地址为本地组播地址或受限广播地址
3. 未指定目的地址。
 
若以上三种情况均未满足,则需要进行路由表查询。
*/
 
	if (fib_lookup(net, &fl, &res)) {
		res.fi = NULL;
		if (oldflp->oif) {
			/* 程序走到这里说明查询路由表失败,未找到对应的路由表项,
			但却指定了外出接口,这时候即便没有路由也是可以发送数据包的。
			当然,如果未指定外出接口,则只能返回网络不可达了。 */
			if (fl.fl4_src == 0)
				fl.fl4_src = inet_select_addr(dev_out, 0,
							      RT_SCOPE_LINK);
			res.type = RTN_UNICAST;
			goto make_route;
		}
		err = -ENETUNREACH;
		goto out;
	}
 
	/* 若为本地路由,则使用环回接口 */
	if (res.type == RTN_LOCAL) {
		if (!fl.fl4_src) {
			if (res.fi->fib_prefsrc)
				fl.fl4_src = res.fi->fib_prefsrc;
			else
				fl.fl4_src = fl.fl4_dst;
		}
		dev_out = net->loopback_dev;
		fl.oif = dev_out->ifindex;
		res.fi = NULL;
		flags |= RTCF_LOCAL;
		goto make_route;
	}
 
/*  使用默认路由需要三个条件:
1. 若前缀为0,也即掩码长度为0,默认路由匹配所有的目的地址。
2. 路由类型为RTN_UNICAST,我们知道本地地址,组播地址和广播地址
3. 未指定出口设备,上面我们提到即便是没有路由的情况下提供了出口设备,
数据包也是可以发送的。
	这时候路由是默认路由,因此我们需要选择默认网关 */
	if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
		fib_select_default(net, &fl, &res);
 
	if (!fl.fl4_src)
		fl.fl4_src = FIB_RES_PREFSRC(res);
 
	dev_out = FIB_RES_DEV(res);
	fl.oif = dev_out->ifindex;
 
make_route:
	/* 创建一条路由缓存 */
	err = ip_mkroute_output(rp, &res, &fl, oldflp, dev_out, flags);
 
out:	return err;
}

接下来看下创建路由缓存的函数:

static int ip_mkroute_output(struct rtable **rp,
			     struct fib_result *res,
			     const struct flowi *fl,
			     const struct flowi *oldflp,
			     struct net_device *dev_out,
			     unsigned flags)
{
	struct rtable *rth = NULL;
	int err = __mkroute_output(&rth, res, fl, oldflp, dev_out, flags);
	unsigned hash;
	if (err == 0) {
		hash = rt_hash(oldflp->fl4_dst, oldflp->fl4_src, oldflp->oif,
			       rt_genid(dev_net(dev_out)));
		err = rt_intern_hash(hash, rth, rp, NULL, oldflp->oif);
	}
 
	return err;
}

该函数首先调用__mkroute_output()函数生成一条路由缓存,然后再调用rt_intern_hash()函数写入到缓存列表中去。

 
static int rt_intern_hash(unsigned hash, struct rtable *rt,
			  struct rtable **rp, struct sk_buff *skb, int ifindex)
{
	struct rtable	*rth, *cand;
	struct rtable __rcu **rthp, **candp;
	unsigned long	now;
	u32 		min_score;
	int		chain_length;
	int attempts = !in_softirq();
 
restart:
	chain_length = 0;
	min_score = ~(u32)0;
	cand = NULL;
	candp = NULL;
	now = jiffies;
 
	if (!rt_caching(dev_net(rt->dst.dev))) {
/* 如果路由未进行缓存,那么把路由的DST标示设为DST_NOCACHE,调用者
	便会知道这条路由未进行缓存,使用完成之后可以根据该标志对路由进
	行释放。如果在这里把路由给丢掉的话,那么当没有进行路由缓存的情况
	下调用都就没办不法解析路由信息了。 */
		rt->dst.flags |= DST_NOCACHE;
		if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
			int err = arp_bind_neighbour(&rt->dst);
			if (err) {
				if (net_ratelimit())
					printk(KERN_WARNING
					    "Neighbour table failure & not caching routes.\n");
				ip_rt_put(rt);
				return err;
			}
		}
 
		goto skip_hashing;
	}
 
 
	rthp = &rt_hash_table[hash].chain;
 
	spin_lock_bh(rt_hash_lock_addr(hash));
	/* 开始遍历哈希链表 */
	while ((rth = rcu_dereference_protected(*rthp,
			lockdep_is_held(rt_hash_lock_addr(hash)))) != NULL) {
		/* 如果路由已过期,则直接从列表中删除并释放内存空间 */
		if (rt_is_expired(rth)) {
			*rthp = rth->dst.rt_next;
			rt_free(rth);
			continue;
		}
		/* 如果未过期,并在列表中找到了匹配的路由,则将该路由缓存项拿到
			链表的最新端,并增加引用计数,释放新建待插入的缓存项内存。 */
		if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) {
			*rthp = rth->dst.rt_next;
			rcu_assign_pointer(rth->dst.rt_next,
					   rt_hash_table[hash].chain);
			rcu_assign_pointer(rt_hash_table[hash].chain, rth);
 
			dst_use(&rth->dst, now);
			spin_unlock_bh(rt_hash_lock_addr(hash));
 
			rt_drop(rt);
			if (rp)
				*rp = rth;
			else
				skb_dst_set(skb, &rth->dst);
			return 0;
		}
 
		if (!atomic_read(&rth->dst.__refcnt)) {
			u32 score = rt_score(rth);
 
			if (score <= min_score) {
				cand = rth;
				candp = rthp;
				min_score = score;
			}
		}
 
		chain_length++;
 
		rthp = &rth->dst.rt_next;
	}
 
	if (cand) {
		/* ip_rt_gc_elasticity used to be average length of chain
		 * length, when exceeded gc becomes really aggressive.
		 *
		 * The second limit is less certain. At the moment it allows
		 * only 2 entries per bucket. We will see.
		 */
		if (chain_length > ip_rt_gc_elasticity) {
			*candp = cand->dst.rt_next;
			rt_free(cand);
		}
	} else {
/* 如果某个哈希槽上的链表长度大于所能接受的链表的最大长度,
	则说明哈希碰撞太严重,需要重构哈希表,这个长度目前定义为20。
	如果需要重构则增加重构计数current_rt_cache_rebuild_count的值,
	rt_caching()函数就是简单地判断该值是否超过最大值来断定缓存是否
	正在进行的,最大值为4。 */
		if (chain_length > rt_chain_length_max &&
		    slow_chain_length(rt_hash_table[hash].chain) > rt_chain_length_max) {
			struct net *net = dev_net(rt->dst.dev);
			int num = ++net->ipv4.current_rt_cache_rebuild_count;
			if (!rt_caching(net)) {
				printk(KERN_WARNING "%s: %d rebuilds is over limit, route caching disabled\n",
					rt->dst.dev->name, num);
			}
			/* 重建哈希列表,然后重新开始此函数 */
			rt_emergency_hash_rebuild(net);
			spin_unlock_bh(rt_hash_lock_addr(hash));
 
			hash = rt_hash(rt->fl.fl4_dst, rt->fl.fl4_src,
					ifindex, rt_genid(net));
			goto restart;
		}
	}
 
	/* 当路由为单播路由或者为外出路由(iif为0的情况即为外出路由)
	则需要把路由绑定到arp */
	if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
		int err = arp_bind_neighbour(&rt->dst);
		if (err) {
			spin_unlock_bh(rt_hash_lock_addr(hash));
 
			if (err != -ENOBUFS) {
				rt_drop(rt);
				return err;
			}
 
			/* Neighbour tables are full and nothing
			   can be released. Try to shrink route cache,
			   it is most likely it holds some neighbour records.
			 */
			if (attempts-- > 0) {
				int saved_elasticity = ip_rt_gc_elasticity;
				int saved_int = ip_rt_gc_min_interval;
				ip_rt_gc_elasticity	= 1;
				ip_rt_gc_min_interval	= 0;
				/* 路由表进行垃圾回收,这个以后再写 */
				rt_garbage_collect(&ipv4_dst_ops);
				ip_rt_gc_min_interval	= saved_int;
				ip_rt_gc_elasticity	= saved_elasticity;
				goto restart;
			}
 
			if (net_ratelimit())
				printk(KERN_WARNING "ipv4: Neighbour table overflow.\n");
			rt_drop(rt);
			return -ENOBUFS;
		}
	}
 
	/* 将该表项放至哈希链表的头部 */
	rt->dst.rt_next = rt_hash_table[hash].chain;
 
	/*
	 * Since lookup is lockfree, we must make sure
	 * previous writes to rt are comitted to memory
	 * before making rt visible to other CPUS.
	 */
	rcu_assign_pointer(rt_hash_table[hash].chain, rt);
 
	spin_unlock_bh(rt_hash_lock_addr(hash));
 
skip_hashing:
	if (rp)
		*rp = rt;
	else
		skb_dst_set(skb, &rt->dst);
	return 0;
}

简单注释了一下几个比较重要的函数,求大牛批评指正。

分类: Kernel 标签: ,

浅析Linux Kernel 哈希路由表实现(一)

三月 13th, {2011 1 条评论 13,812 人阅读过  

1. 路由表

目前Linux内核中支持两种路由表,一种是Hash路由表,另一种是Trie路由表,Trie算法查找效率很高,但它也因极其消毫内存资源而闻名,因此一般用在大型机上,否则在路由项过多时很可能造成内存的耗尽。在一般的机器上最好还是使用Hash路由表,之前有争论说Linux使用Hash路由表相比于二叉树效率太低,不适合商用,其实只要设计良好的哈希算法,尽量减少哈希碰撞,Hash路由表的查找效率也是很高的,在最好的情况下算法复杂算可以达到O(1),当然,最差也不过是O(n),我们有理由相信Linux中存在各种优秀的哈希算法,这些都是值得我们学习的。

Linux内核中IPv4路由表采用了分层的结构,第一层是是fib_table,表示路由表,最多可以支持256张路由表,用户可以根据策略路由的需求来创建自己的路由表,系统默认的两张路由表为RT_TABLE_LOCAL和RT_TABLE_MAIN。下面是系统保留的路由表标识符:

enum rt_class_t {
	RT_TABLE_UNSPEC=0,
/* User defined values */
	RT_TABLE_COMPAT=252,
	RT_TABLE_DEFAULT=253,
	RT_TABLE_MAIN=254,
	RT_TABLE_LOCAL=255,
	RT_TABLE_MAX=0xFFFFFFFF
};

下面是路由表的定义:

struct fib_table {
	struct hlist_node tb_hlist;
	/* 路由表的标识,即为上面提到的类型 */
	u32		tb_id;
	/* 该路由中默认路由条目在哈希路由表中的索引,
		在fib_table_select_default()函数中计算得出 */
	int		tb_default;
	/* Linux保留内存空间一惯的做法,这块空间留给了struct fn_hash */
	unsigned char	tb_data[0];
};

1.1 根据路由表ID来查找路由表。

struct fib_table *fib_get_table(struct net *net, u32 id)
{
	struct fib_table *tb;
	struct hlist_node *node;
	struct hlist_head *head;
	unsigned int h;
 
	if (id == 0)
		id = RT_TABLE_MAIN;
	h = id & (FIB_TABLE_HASHSZ - 1);
 
	rcu_read_lock();
	head = &net->ipv4.fib_table_hash[h];
	hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
		if (tb->tb_id == id) {
			rcu_read_unlock();
			return tb;
		}
	}
	rcu_read_unlock();
	return NULL;
}

当路由表标识为0时默认返回主路由表,这里的哈希算法也很简单,当支持多径路由时FIB_TABLE_HASHSZ定义为256,否则FIB_TABLE_HASHSZ定义为2。也就是说在不支持多径路由的情况下,fib_table_hash中只有两个元素。

1.2 路由表的创建。

 
struct fib_table *fib_new_table(struct net *net, u32 id)
{
	struct fib_table *tb;
	unsigned int h;
 
	if (id == 0)
		id = RT_TABLE_MAIN;
	tb = fib_get_table(net, id);
	if (tb)
		return tb;
 
	tb = fib_hash_table(id);
	if (!tb)
		return NULL;
	h = id & (FIB_TABLE_HASHSZ - 1);
	hlist_add_head_rcu(&tb->tb_hlist, &net->ipv4.fib_table_hash[h]);
	return tb;
}

在这个函数里面首先在已有的哈希表中根据给出的路由表标识查找已存在的路由表,若找到对应的路由表则直接返回,否则调用fib_hash_table()函数创建一个新的路由表,然后将其添加到fib_table_hash中去。接下来看一下fib_hash_table()这个函数:

struct fib_table *fib_hash_table(u32 id)
{
	struct fib_table *tb;
 
	tb = kmalloc(sizeof(struct fib_table) + sizeof(struct fn_hash),
		     GFP_KERNEL);
	if (tb == NULL)
		return NULL;
 
	tb->tb_id = id;
	tb->tb_default = -1;
 
	memset(tb->tb_data, 0, sizeof(struct fn_hash));
	return tb;
}

这个函数很简单,分配了一块内存空间,大小为sizeof(struct fib_table) + sizeof(struct fn_hash),于是fib_table的最后一个字段tb_data便指向了这个struct fn_hash。接下来该说路由表的第二层了。

2. 路由域struct fn_zone

第二层是fn_zone,表示路由域,Linux根据路由掩码的长度将所有的路由分为32个域。我们先来看下位于fib_table末尾的struct fn_hash的定义:

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

如上路由表分为32个路由域,这32个跌幅域又连成了链表,其中fn_zone_list这个字段指向链表的头。

 
struct fn_zone {
	struct fn_zone __rcu	*fz_next;	/* Next not empty zone	*/
	struct hlist_head __rcu	*fz_hash;	/* Hash table pointer	*/
	seqlock_t		fz_lock;
	u32			fz_hashmask;	/* (fz_divisor - 1)	*/
 
	u8			fz_order;	/* Zone order (0..32)	*/
	u8			fz_revorder;	/* 32 - fz_order	*/
	__be32			fz_mask;	/* inet_make_mask(order) */
#define FZ_MASK(fz)		((fz)->fz_mask)
 
	struct hlist_head	fz_embedded_hash[EMBEDDED_HASH_SIZE];
 
	int			fz_nent;	/* Number of entries	*/
	int			fz_divisor;	/* Hash size (mask+1)	*/
};

2.1 fn_zone的创建

 
static struct fn_zone *
fn_new_zone(struct fn_hash *table, int z)
{
	int i;
	struct fn_zone *fz = kzalloc(sizeof(struct fn_zone), GFP_KERNEL);
	if (!fz)
		return NULL;
 
	seqlock_init(&fz->fz_lock);
	fz->fz_divisor = z ? EMBEDDED_HASH_SIZE : 1;
	fz->fz_hashmask = fz->fz_divisor - 1;
	RCU_INIT_POINTER(fz->fz_hash, fz->fz_embedded_hash);
	fz->fz_order = z;
	fz->fz_revorder = 32 - z;
	fz->fz_mask = inet_make_mask(z);
 
	/* Find the first not empty zone with more specific mask */
	for (i = z + 1; i <= 32; i++)
		if (table->fn_zones[i])
			break;
	if (i > 32) {
		/* No more specific masks, we are the first. */
		rcu_assign_pointer(fz->fz_next,
				   rtnl_dereference(table->fn_zone_list));
		rcu_assign_pointer(table->fn_zone_list, fz);
	} else {
		rcu_assign_pointer(fz->fz_next,
				   rtnl_dereference(table->fn_zones[i]->fz_next));
		rcu_assign_pointer(table->fn_zones[i]->fz_next, fz);
	}
	table->fn_zones[z] = fz;
	fib_hash_genid++;
	return fz;
}

首先在内存中给struct fn_zone分配内存空间,然后按规则对一些基本的变量进行初始化,之后就是安排各个fn_zone在fn_zone_list的位置了,fn_zone_list中的节点都是按照fz_order从大到小排列的,所以首先一个for循环找出比当前fn_zone的fz_order大的最小fn_zone,如果存在,就将当前节点插到该节点之后;如果不存在,则表示当前节点是目前zn_order最大的节点,则它会成为链表的头。

3. 路由节点fib_node

第三层为路由节点fib_node,在同一个路由域中的路由项有相同的掩码长度,但它们的网络号可以不同,则根据不同路由的网络号将同一个域划分为不同的路由节点,如到地址10.10.65.0和10.10.64.0的路由便是属于同一个路由域里面两个不同路由节点的两条路由。在路由节点中又有根据路由的服务类型,路由类型,路由寻址范围以前路由状态的不同将同一个路由节点中的路由划分成不同的路由

struct fib_node {
	/* 哈希链表指针,针向同一个Hash槽中的相临节点 */
	struct hlist_node	fn_hash;
	/* 属于该节点的alias链表的头 */
	struct list_head	fn_alias;
	/* 该节点对应的网络key */
	__be32			fn_key;
	/* 预先分配了空间的别名,在fib_fast_alloc()中使用 */
	struct fib_alias        fn_embedded_alias;
};

3.1 fib_alias结构

struct fib_alias {
	/* 指向链表中的相邻节点 */
	struct list_head	fa_list;
	/* fa_info是最终的路由信息 */
	struct fib_info		*fa_info;
	/* 服务类型,对于一般服务取值为0 */
	u8			fa_tos;
	/* 路由类型 */
	u8			fa_type;
	/* 路由范围 */
	u8			fa_scope;
	/* 路由状态 */
	u8			fa_state;
	struct rcu_head		rcu;
};

路由类型和路由范围的对应关系如下结构:

 
static const struct
{
	int	error;
	u8	scope;
} fib_props[RTN_MAX + 1] = {
	[RTN_UNSPEC] = {
		.error	= 0,
		.scope	= RT_SCOPE_NOWHERE,
	},
	[RTN_UNICAST] = {
		.error	= 0,
		.scope	= RT_SCOPE_UNIVERSE,
	},
	[RTN_LOCAL] = {
		.error	= 0,
		.scope	= RT_SCOPE_HOST,
	},
	[RTN_BROADCAST] = {
		.error	= 0,
		.scope	= RT_SCOPE_LINK,
	},
	[RTN_ANYCAST] = {
		.error	= 0,
		.scope	= RT_SCOPE_LINK,
	},
	[RTN_MULTICAST] = {
		.error	= 0,
		.scope	= RT_SCOPE_UNIVERSE,
	},
	[RTN_BLACKHOLE] = {
		.error	= -EINVAL,
		.scope	= RT_SCOPE_UNIVERSE,
	},
	[RTN_UNREACHABLE] = {
		.error	= -EHOSTUNREACH,
		.scope	= RT_SCOPE_UNIVERSE,
	},
	[RTN_PROHIBIT] = {
		.error	= -EACCES,
		.scope	= RT_SCOPE_UNIVERSE,
	},
	[RTN_THROW] = {
		.error	= -EAGAIN,
		.scope	= RT_SCOPE_UNIVERSE,
	},
	[RTN_NAT] = {
		.error	= -EINVAL,
		.scope	= RT_SCOPE_NOWHERE,
	},
	[RTN_XRESOLVE] = {
		.error	= -EINVAL,
		.scope	= RT_SCOPE_NOWHERE,
	},
};

3.2 fib_info结构

fib_alias中的fib_info为最终的路由信息,来看一下它的定义:

 
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]
	/* 路由的跃点数,当支持多径路由时,fib_nhs为跃点数目,
	当不支持多径路由时,到达目前地址都只有一跳,则该值为1 */
	int			fib_nhs;
	struct rcu_head		rcu;
	/* 下一跳信息 */
	struct fib_nh		fib_nh[0];
#define fib_dev		fib_nh[0].nh_dev
};

3.3 fib_info的创建

struct fib_config中包含了创建一条路由条目所需要的信息。本文中不考虑路由多径的情况,即假设宏CONFIG_IP_ROUTE_MULTIPATH未定义。

struct fib_info *fib_create_info(struct fib_config *cfg)
{
	int err;
	struct fib_info *fi = NULL;
	struct fib_info *ofi;
	int nhs = 1;
	struct net *net = cfg->fc_nlinfo.nl_net;
 
	/* 检测该请求创建的路由信息范围与类型是否对应 */
	if (fib_props[cfg->fc_type].scope > cfg->fc_scope)
		goto err_inval;
 
	/* 路由信息除依附于上述所提到的几种数据结构外,同时系统会维护
		两个全局的哈希链表,一个用于保存路由信息,另一个用于保存本地地址,
		fib_info_cnt全局变量表示路由表项的数目,fib_hash_size表示哈希表
		的大小,当路由表项数目大于路由哈希表大小时,为了防止哈希碰撞导致的
		查找效率降低,需要扩大哈希表大小为原来的两倍 */
	err = -ENOBUFS;
	if (fib_info_cnt >= fib_hash_size) {
		unsigned int new_size = fib_hash_size << 1;
		struct hlist_head *new_info_hash;
		struct hlist_head *new_laddrhash;
		unsigned int bytes;
 
		if (!new_size)
			new_size = 1;
		/* 按新的哈希表尺寸为哈希表分配内存空间 */
		bytes = new_size * sizeof(struct hlist_head *);
		new_info_hash = fib_hash_alloc(bytes);
		new_laddrhash = fib_hash_alloc(bytes);
		if (!new_info_hash || !new_laddrhash) {
			fib_hash_free(new_info_hash, bytes);
			fib_hash_free(new_laddrhash, bytes);
		} else
			/* 如果内存空间分配成功,则将旧的列表中的内容移动到新的链表中,
			 	并释放旧列表的内存空间 */
			fib_hash_move(new_info_hash, new_laddrhash, new_size);
 
		/* 列表大小溢出,则出错返回 */
		if (!fib_hash_size)
			goto failure;
	}
 
	/* 为路由表项分配内存空间,大小为struct fib_info的大小加上nhs个下一跳信息
	struct fib_nh的大小,不支持多径路由的路由时nhs始终为1 */
	fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);
	if (fi == NULL)
		goto failure;
	fib_info_cnt++;
 
	fi->fib_net = hold_net(net);
	fi->fib_protocol = cfg->fc_protocol;
	fi->fib_flags = cfg->fc_flags;
	fi->fib_priority = cfg->fc_priority;
	fi->fib_prefsrc = cfg->fc_prefsrc;
 
	fi->fib_nhs = nhs;
	/* 遍历fib_nh信息,此处仅执行一次,设置fib_nh的nh_parent */
	change_nexthops(fi) {
		nexthop_nh->nh_parent = fi;
	} endfor_nexthops(fi)
 
	/* 如果给出了路由属性信信,则通过遍历路由属性信息来确定fib_metrics的值 */
	if (cfg->fc_mx) {
		struct nlattr *nla;
		int remaining;
 
		nla_for_each_attr(nla, cfg->fc_mx, cfg->fc_mx_len, remaining) {
			int type = nla_type(nla);
 
			if (type) {
				if (type > RTAX_MAX)
					goto err_inval;
				fi->fib_metrics[type - 1] = nla_get_u32(nla);
			}
		}
	}
 
	struct fib_nh *nh = fi->fib_nh;
 
	nh->nh_oif = cfg->fc_oif;
	nh->nh_gw = cfg->fc_gw;
	nh->nh_flags = cfg->fc_flags;
 
	if (fib_props[cfg->fc_type].error) {
		if (cfg->fc_gw || cfg->fc_oif || cfg->fc_mp)
			goto err_inval;
		goto link_it;
	}
 
	if (cfg->fc_scope > RT_SCOPE_HOST)
		goto err_inval;
 
	if (cfg->fc_scope == RT_SCOPE_HOST) {
		struct fib_nh *nh = fi->fib_nh;
		/* 当前添加的是本地路由信息,只可能有一跳,即便是开启了
			多径路由,下一跳数目不为1则报错,同时本地路由也不需要
			指定网关,如果指定则报错 */
 
		if (nhs != 1 || nh->nh_gw)
			goto err_inval;
		nh->nh_scope = RT_SCOPE_NOWHERE;
		nh->nh_dev = dev_get_by_index(net, fi->fib_nh->nh_oif);
		err = -ENODEV;
		if (nh->nh_dev == NULL)
			goto failure;
	} else {
		/* 如果添加的不是本地路由信息,则检查下一跳信息 */
		change_nexthops(fi) {
			err = fib_check_nh(cfg, fi, nexthop_nh);
			if (err != 0)
				goto failure;
		} endfor_nexthops(fi)
	}
 
	if (fi->fib_prefsrc) {
		if (cfg->fc_type != RTN_LOCAL || !cfg->fc_dst ||
		    fi->fib_prefsrc != cfg->fc_dst)
			if (inet_addr_type(net, fi->fib_prefsrc) != RTN_LOCAL)
				goto err_inval;
	}
 
link_it:
	/* 查找路由条目,返回与当前路由条目精确匹配的条目,
		若存在,则释放当前创建的新条目,增加已找到的路由条目
		的引用计数,并返回已找到的旧路由条目 */
	ofi = fib_find_info(fi);
	if (ofi) {
		fi->fib_dead = 1;
		free_fib_info(fi);
		ofi->fib_treeref++;
		return ofi;
	}
 
	/* 当前路由表中未找到已存在的符合要求的路由条目, 则增加
		新建路由条目的引用计数 */
	fi->fib_treeref++;
	atomic_inc(&fi->fib_clntref);
	spin_lock_bh(&fib_info_lock);
	/* 将新建的路由插入到全局路由列表中,其中fib_info_hashfh
		为散列函数 */
	hlist_add_head(&fi->fib_hash,
		       &fib_info_hash[fib_info_hashfn(fi)]);
 
	/* 如果指定了源地址,则将源地址插入到全局本地地址列表中 */
	if (fi->fib_prefsrc) {
		struct hlist_head *head;
		head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)];
		hlist_add_head(&fi->fib_lhash, head);
	}
	/* 将下一跳信息写入全局列表中,由上述知本迭代只进行一次,
		散列函数为fib_devindex_hashfn() */
	change_nexthops(fi) {
		struct hlist_head *head;
		unsigned int hash;
 
		if (!nexthop_nh->nh_dev)
			continue;
		hash = fib_devindex_hashfn(nexthop_nh->nh_dev->ifindex);
		head = &fib_info_devhash[hash];
		hlist_add_head(&nexthop_nh->nh_hash, head);
	} endfor_nexthops(fi)
	spin_unlock_bh(&fib_info_lock);
	return fi;
 
err_inval:
	err = -EINVAL;
 
failure:
	if (fi) {
		fi->fib_dead = 1;
		free_fib_info(fi);
	}
 
	return ERR_PTR(err);
}

3.4 向路由表中插入路由信息。

 
int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
{
	struct fn_hash *table = (struct fn_hash *) tb->tb_data;
	struct fib_node *new_f = NULL;
	struct fib_node *f;
	struct fib_alias *fa, *new_fa;
	struct fn_zone *fz;
	struct fib_info *fi;
	u8 tos = cfg->fc_tos;
	__be32 key;
	int err;
 
	if (cfg->fc_dst_len > 32)
		return -EINVAL;
 
	/* 根据目的地址长度找出对应的路由域 */
	fz = table->fn_zones[cfg->fc_dst_len];
	/* 如果路由域不存在,则调用fn_new_zone()函数创建一个新的路由域 */
	if (!fz && !(fz = fn_new_zone(table, cfg->fc_dst_len)))
		return -ENOBUFS;
 
	key = 0;
 
	/* 如果指定了目的地址,如果目的地址主机位不为0,则出错返回 */
	if (cfg->fc_dst) {
		if (cfg->fc_dst & ~FZ_MASK(fz))
			return -EINVAL;
		key = fz_key(cfg->fc_dst, fz);
	}
 
	/* 创建一个新的fib_info对象 */
	fi = fib_create_info(cfg);
	if (IS_ERR(fi))
		return PTR_ERR(fi);
 
	/* 如果当前路由域中路由节点的数目大于散列表大小的两倍,
		并且相关数据都合法的情况下,需要重构散列表以减小
		哈希碰撞 */
	if (fz->fz_nent > (fz->fz_divisor<<1) &&
	    fz->fz_divisor < FZ_MAX_DIVISOR &&
	    (cfg->fc_dst_len == 32 ||
	     (1 << cfg->fc_dst_len) > fz->fz_divisor))
		fn_rehash_zone(fz);
 
	/* 通过网络号key找出对应的路由节点fn_node */
	f = fib_find_node(fz, key);
 
	if (!f)
		fa = NULL;
	else
		fa = fib_find_alias(&f->fn_alias, tos, fi->fib_priority);
 
	if (fa && fa->fa_tos == tos &&
	    fa->fa_info->fib_priority == fi->fib_priority) {
		struct fib_alias *fa_first, *fa_match;
 
		err = -EEXIST;
		/* 如果具有与新建路由项相同属性的fib_alias存在,并且添加路由项标志中
			设置了NLM_F_EXCL(排它选项),则返回路由已存在 */
		if (cfg->fc_nlflags & NLM_F_EXCL)
			goto out;
 
		/* We have 2 goals:
		 * 1. Find exact match for type, scope, fib_info to avoid
		 * duplicate routes
		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
		 */
		fa_match = NULL;
		fa_first = fa;
		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
		list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
			if (fa->fa_tos != tos)
				break;
			if (fa->fa_info->fib_priority != fi->fib_priority)
				break;
			if (fa->fa_type == cfg->fc_type &&
			    fa->fa_scope == cfg->fc_scope &&
			    fa->fa_info == fi) {
				fa_match = fa;
				break;
			}
		}
 
		if (cfg->fc_nlflags & NLM_F_REPLACE) {
			u8 state;
 
			/* 如果存在一条精确匹配的路由项fib_alias,并且在设置了NLM_F_REPLACE
				标志的情况下,不做处理直接返回 */
			fa = fa_first;
			if (fa_match) {
				if (fa == fa_match)
					err = 0;
				goto out;
			}
 
			/* 并没有精确匹配的路由项fib_alias,即便有匹配的fib_alias,也是
				仅tos和priority两个选项匹配,因此需要新建一个路由别名fib_alias */
			err = -ENOBUFS;
			new_fa = fib_fast_alloc(f);
			if (new_fa == NULL)
				goto out;
 
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
			new_fa->fa_type = cfg->fc_type;
			new_fa->fa_scope = cfg->fc_scope;
			state = fa->fa_state;
			new_fa->fa_state = state & ~FA_S_ACCESSED;
			fib_hash_genid++;
			/* 因为设置了NLM_F_REPLACE选项,所以用新fib_alias对象替换掉
				列表中旧的fib_alias对象,并释放旧对象的内存 */
			list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
 
			fn_free_alias(fa, f);
			if (state & FA_S_ACCESSED)
				rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
			/* 这里留做以后再讨论 */
			rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len,
				  tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
			return 0;
		}
 
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
		if (fa_match)
			goto out;
 
		if (!(cfg->fc_nlflags & NLM_F_APPEND))
			fa = fa_first;
	}
 
	/* 对应的fib_alias对象并不存在,如果没有设置NLM_F_CREATE则返回出错 */
	err = -ENOENT;
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
		goto out;
 
	err = -ENOBUFS;
 
	/* 新建一个路由节点项fib_node并初始化 */
	if (!f) {
		new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);
		if (new_f == NULL)
			goto out;
 
		INIT_HLIST_NODE(&new_f->fn_hash);
		INIT_LIST_HEAD(&new_f->fn_alias);
		new_f->fn_key = key;
		f = new_f;
	}
 
	/* 新建一个路由别名项fib_alias并初始化 */
	new_fa = fib_fast_alloc(f);
	if (new_fa == NULL)
		goto out;
 
	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_scope = cfg->fc_scope;
	new_fa->fa_state = 0;
 
	/* 将路由信息项,路由别名项,路由节点项按规则组织起来
		后刷新路由表 */
	if (new_f)
		fib_insert_node(fz, new_f);
	list_add_tail_rcu(&new_fa->fa_list,
		 (fa ? &fa->fa_list : &f->fn_alias));
	fib_hash_genid++;
 
	if (new_f)
		fz->fz_nent++;
	rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
 
	rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len, tb->tb_id,
		  &cfg->fc_nlinfo, 0);
	return 0;
 
out:
	if (new_f)
		kmem_cache_free(fn_hash_kmem, new_f);
	fib_release_info(fi);
	return err;
}

3.5 查询路由信息

这个这个函数先在RT_TABLE_LOCAL表中查询路由信息,成功则返回,如果失败则再从RT_TABLE_MAIN表中查询路由信息,如果失败则返回网络不可达,成功则返回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, FIB_LOOKUP_NOREF))
		return 0;
 
	table = fib_get_table(net, RT_TABLE_MAIN);
	if (!fib_table_lookup(table, flp, res, FIB_LOOKUP_NOREF))
		return 0;
	return -ENETUNREACH;
}

接下来再看fib_table_lookup()函数的定义:

int fib_table_lookup(struct fib_table *tb,
		     const struct flowi *flp, struct fib_result *res,
		     int fib_flags)
{
	int err;
	struct fn_zone *fz;
	struct fn_hash *t = (struct fn_hash *)tb->tb_data;
 
	rcu_read_lock();
	for (fz = rcu_dereference(t->fn_zone_list);
	     fz != NULL;
	     fz = rcu_dereference(fz->fz_next)) {
		struct hlist_head *head;
		struct hlist_node *node;
		struct fib_node *f;
		__be32 k;
		unsigned int seq;
 
		do {
			seq = read_seqbegin(&fz->fz_lock);
			k = fz_key(flp->fl4_dst, fz);
 
			head = rcu_dereference(fz->fz_hash) + fn_hash(k, fz);
			hlist_for_each_entry_rcu(f, node, head, fn_hash) {
				if (f->fn_key != k)
					continue;
 
				err = fib_semantic_match(&f->fn_alias,
						 flp, res,
						 fz->fz_order, fib_flags);
				if (err <= 0)
					goto out;
			}
		} while (read_seqretry(&fz->fz_lock, seq));
	}
	err = 1;
out:
	rcu_read_unlock();
	return err;
}

该函数从fn_zone_list开始遍历fn_zone链表,上面创建fn_zone的过程中我们提到过,fn_zone在fn_zone_list中是按掩码长度从大到小排列的,即该搜索先匹配掩码最大的zone,若不匹配则转而去匹配下一个掩码稍小的路由域,其中fn_key是匹配的关键,如果key不匹配则该路由项肯定不匹配,key匹配之后还要再调用fib_semantic_match()函数再做进一步的检查,并在该函数中利用查询到的路由信息给查询结果对象fib_result初始化。当没有一个掩码长度不为0的zone中有路由项与其匹配时,函数最后一次循环会检测掩码长度为0的zone,该域便为默认路由域,在这里fn_key与k的值均为0,它们始终匹配,也就是说如果检查不到匹配的路由项,则交由默认路由来处理(不知道这样表达合不合理,大体就是这个意思),接下来再来检验证TOS,SCOPE等信息。接下来看fib_semantic_match()函数:

 
int fib_semantic_match(struct list_head *head, const struct flowi *flp,
		       struct fib_result *res, int prefixlen, int fib_flags)
{
	struct fib_alias *fa;
	int nh_sel = 0;
 
	list_for_each_entry_rcu(fa, head, fa_list) {
		int err;
 
		if (fa->fa_tos &&
		    fa->fa_tos != flp->fl4_tos)
			continue;
 
		if (fa->fa_scope < flp->fl4_scope)
			continue;
 
		fib_alias_accessed(fa);
 
		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;
				}
				goto out_fill_res;
				endfor_nexthops(fi);
				continue;
 
			default:
				pr_warning("fib_semantic_match bad type %#x\n",
					   fa->fa_type);
				return -EINVAL;
			}
		}
		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;
	if (!(fib_flags & FIB_LOOKUP_NOREF))
		atomic_inc(&res->fi->fib_clntref);
	return 0;
}

该函数返回1时表示没有匹配的路由项,返回0时表示匹配成功,返回负值时表示管理失败,即fa->fa_type类型有问题,可查询fib_props数组来确定对应的fa_type是否有错误,如果类型为RTN_BLACKHOLE,RTN_UNREACHABLE,RTN_PROHIBIT,RTN_THROW,RTN_NAT,RTN_XRESOLVE时表示存在对应的错误。

函数先检验TOS,如果搜索健值中指定了TOS,则必须对TOS进行严格匹配,否则当前路由项即不符合要求。如果未指定TOS,则可以匹配任意TOS。

接下来检验scope,路由项的范围必须比请求的范围更”窄“才能符合要求,如果请求查找的scope为RTN_UNIVERSE,则RTN_LINK即不匹配;类似的,如果请求查找的是RTN_HOST,则RTN_LINK,RTN_UNIVERSE都是可以匹配的。

scope检查完成之后即开始检查路由类型,即刚才提到的fa->fa_type,不再说了。如果类型没有问题则接下来检查下一跳信息,首先得确保下一跳信息不是待删除的,其次如果指定了出口设备,则出口设备要和下一跳信息中的出口设备匹配。如果到这一步全都匹配,则函数跳到out_fill_res,填充fib_result,之后返回0,表示成功。

分类: Kernel 标签: ,

浅析Linux Kernel中的那些链表

三月 6th, {2011 14 条评论 10,631 人阅读过  

链表是Linux内核中最重要的数据结构,但Linux内核中的链表与传统的数据结构书中看到的链表结构略有不同。这里简单写一下我对于Linux内核中链表的理解,不足之处欢迎路过的大牛给出批评意见。

1.传统形式的链表

数据结构书中的链表一般是下面这种形式:

struct list {
	struct list *pre;
	struct list *next;
	void *data;
};

每一个链表结构中都包括两个同类型的指针,分别指向链表的上一个节点和下一个节点。这样当该节点处于一个循环链表中时,链表的首节点一般不用于保存数据,但首节点也需要是一个struct list类型,当结构庞大时首节点也必须分配同样大小的空间,这样就造成了内存的浪费。

2. Linux内核中的双向循环链表

Linux内核中定义了一个struct list_head类型用于保存链表信息指针:

struct list_head {
	struct list_head *next, *prev;
};

如此在链表中链表头只需用一个struct list_head类型来表示即可,不管链表中节点的数据结构多么庞大,链表头只需要占8个字节,链表中的节点则如下定义:

struct list {
	struct list_head list_head;
	void *data;
};

如此一来类似于list_add()和list_del()这些函数只需要接收struct list_head类型的参数即可,不失通用性。

在链表这种结构中最好玩的地方在于对于这种形式的链表的遍历,Linux中定义的以下的宏:

#define __list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

这个宏其实没什么神奇的地方,很典型的对于循环链表的迭代,但对于Linux内核中的链表,迭代的指针只能是一个struct list_head类型,对于这个类型来说我们只能对它做一些移动或者添加的操作,并不能取出该list_head对应的节点。这个迭代过程对于节点的删除操作其实是不安全的,假设我们在迭代中移除了pos节点,则进入下一次迭代时,pos = pos->next这个就不知会指向哪里去了,Linux中也定义了对于删除安全的迭代宏:

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

这个宏中使用了n这个struct list_head类型的临时变量,每次迭代之后pos的下一个节点储存在临时变量n中,则在迭代中删除pos节点后,下一次迭代会重新给pos赋值为临时变量n,然后再做迭代。这样在迭代的过程中就可以安全地删除节点pos了。

刚才说过这种迭代每次迭代的变量都只是一个struct list_head类型,而更多时候我们遍历一个链表是为了读取或者修改链表的节点数据,这个时候我们就需要用到另外一种宏:

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     prefetch(pos->member.next), &pos->member != (head); 	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

在这个宏里面每次迭代pos所指向的都是struct list_head所对应的节点对象,该节点是通过list_entry()这个宏来获取的,接下来看它的定义:

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

继续看下去就是container_of()这个宏,该宏在/include/linux/kernel.h里面定义。

#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

该宏的作用就是返回一个结构体中的某成员变量对应的包含它的结构体的指针。在这里ptr这个参数便是一个struct list_head类型,type为包含这个struct list_head成员变量的结构体的类型,member为ptr这个参数作为成员变量的变量名。

第一句话的作用比较有意思,它跟offsetof()这个函数采用了同样的方法,通过欺骗编译器,告诉它在内存地址0处有一个type类型的结构,然后取出member的数据类型(当然,在这里我们要讨论member是个struct list_head类型,该函数不失通用性),定义一个该类型的临时指针让它指向ptr。第二句话将_mptr转换成一个char*指针(大家都知道char是一个字节,当我没说),通过offsetof()宏取出member在结构体中的节字偏移,也就是_mptr在它的父结构体中的字节偏移,于是_mptr减去它偏移的字节便是它的父结构体的内存地址,做一下指针类型转换便得到了父结构体的地址,很有趣哈。

既然说到了这里,不防也看一下offsetof()这个函数的实现,可通过man 3 offsetof命令查看offsetof函数的介绍,这里我们简单看下它的实现。

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

这一句话就可以搞定,TYPE为父类型的类型名,MEMBER为子类型的变量名,通过欺骗编译器在内存地址0处有一个TYPE类型的对象,然后强制转换成TYPE类型,取出MEMBER的地址,这个内存地址便是相对于0地址的偏移字节数,刚才我们已经假设TYPE类型在0地址处,这样取出的内存地址便是子类型在父类型中的偏移字节数,整个过程实际上就是对编译器的欺骗,我们并没有对这些不合法的内存地址进行写操作,所以该宏是安全的。

3. 用于散列表中的双向链表。

众所周知,在哈希节点冲突的时候需要把冲突的节点存储在链表中,如此说来便会有大量的链表存在(例如HASH路由表),这样链表头的8个字节对于Linux开发者来说可能也会成为一种负担,于是他们设计了另外一种链表,用来将链表头缩减为只有一个字节,看来面这种定义:

/* 链表头 */
struct hlist_head {
	struct hlist_node *first;
};
/* 链表节点 */
struct hlist_node {
	struct hlist_node *next, **pprev;
};

链表头只有一个指向第一个节点的指针,链表节点分别有指向下一个和上一个节点的指针,如此上一个节点便不能和下一个节点使用相同的类型,因为第一个节点的上一个节点是一个struct hlist_head类型而不是hlist_node类型,于是这里巧妙地使用了指向上一个节点的next指针的地址作为上一个节点的指针,我们知道在获取上一个节点的时候一般是为了对它进行插入操作,而插入操作只需要操作上一个节点的next指针(hlist_head和hlist_node的指向下个节点的指针类型相同,这样便可以在插入和删除操作对于首节点和普通节点不失通用性了),而不需要操作pre指针,于是这种设计便足够使用了,为上一个节点的next指针赋值时只需要为*(node->pprev)赋值始可。参考如下函数:

/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
					struct hlist_node *next)
{
	n->pprev = next->pprev;
	n->next = next;
	next->pprev = &n->next;
	*(n->pprev) = n;
}

对于hlist链表操作的方法与list操作的方法大同小异,只不过在include/linux/list.h中没有定义对hlist逆向迭代的方法。

分类: Kernel 标签:

Tweets2PDF开发手记

三月 1st, {2011 5 条评论 8,725 人阅读过  

之前一直想学一下Python却迟迟未曾下手,直到过年前几天好不容易闲下来,突然有个想法想把Twitter上发的tweets备份成PDF,我这个人一有了什么想法就会立马动手去做,于是正好借这个机会学下Python,没有太多时间,用Python比用C会节省很多开发时间,于是折腾了几天就有了这样一个小工具,Tweets2PDF,趁着还没把看过的东西忘光就先记录下写开发过程。

Twitter使用OAuth认证,其实之前对OAuth的原理也不是很了解,正好也借这个机会简单看了一下它的原理。

首先,程序需要向Twitter官网申请一个consumer token,每个客户端需要持有这个token,OAuth开始的时候向Twitter的Request Token URL发送请求来获取一个Request Token,当然HTTP请求中需要加上一些参数,这些参数中包含了Consumer Token相关的值,当然不止这些,具体的参数内容就去参考Twitter上OAuth的介绍或者去读OAuth的RFC。

获取到Request Token之后再根据这个Token生成一个URL,在浏览器中打开这个URL就可以对应用程序进行认证,有一个请求参数是Callback参数,它可以是一个URL,表示验证成功之后程序跳转到该URL,这个URL是Consumer的URL,这适合Web形式的第三方程序,桌面应用程序大家如果用过肯定都知道是需要一个PIN码的,如果要让Twitter返回这个PIN码,只需要把Callback的值设为oob即可,这样在认证之后Twitter后给出一个PIN码。

将这个PIN码由用户交回桌面应用程序,应用程序便再利用这个PIN码和Request Token再生成一个HTTP请求,这个请求成功之后会获取一个Access Token,这个Token是需要用户保存的,之后对于Twitter的访问只需要在请求中根据这个Token生成添加相应的HTTP请求参数即可,Twitter就会知道这个应用程序是经过认证的。

关于Twitter OAuth认证的详细资料见:Authenticating Requests with OAuth

OAuth认证过程中设计到对请求参数的处理比较繁琐,这方面的工作已经有人做过了,我没有必要做无用功,用了这个OAuth库: http://oauth.googlecode.com/svn/code/python/ 不过这个库貌似有些问题,用它的Demo跑的时候会出问题,我对它做了一些修改,并在它之上完成了Twitter的OAuth认证。

不得不说OAuth这种认证机制是Web2.0的开放平台的必然产物,也是这种开放平台所必不可少的,它可以让不同的服务或者程序访问彼此开放的资源,这种开放平台策略也是互联网发展的趋势,可不明白的是为什么国内这么多SNS服务却没有一个能把开放地平台给做好,Twitter有非常多优秀的第三方客户端,可没有听说谁觉得有哪个什么第三方的新浪微博客户端好用,可能他们认为开放会带来风险,但开放更多地会带来商机,更多的人使用Twitter的第三方官户端去发推,但Twitter却越做越好,这是开放平台的魅力。

晕,扯远了,接着说Tweet2PDF,经过认证之后就可以很简单地通过Twitter提供的API来获取相关的数据了,Twitter的API非常丰富,用官方版本能做的事情用API都可以做,它的API除了每小时有访问限制(可能出于服务器负载的考虑)之外,它的API非常完整,当然说到API的限制我也遇到了问题,对于一般的第三方官户端程序来说API是够用的,但我要做的是抓取用户发过的所有Tweets将其生成PDF,这个过程中会一直不间段地大量抓取,难免会遇到API受限,这种情况下我只能进行重试,由最初的3次重试调整为现在的10次,基本可以保证用户正常抓取完所有的推后中止,但还有一个问题,Twitter的API只允许抓取最新的3200条Tweets,对于再旧的Tweets就抓取不到了,这便降低了这个软件的可用性,因此它只能用来给用户进行定期备份了。

抓取到数据之后便要生成PDF文件了,生成PDF用的是Reportlab这个库,很幸运,它是用Python写的,用Python对它进行调用很完美,而且它有开源版本,Reportlab需要PIL(Python Imaging Library)的支持,来进行图片的处理,实现的细节就不说了,官方有很详细的文档,遇到几个小问题:

因为每生成一条Tweet都会在前面附上发推人的Profile Image,Reportlab对JPEG格式的图片支持很好,但如果图片是其它格式,例如PNG,当生成页数过多时在调用Build函数进行生成时便可能出错,这个错误是无法挽回的,也就是说前出抓取到的Tweet可能全部都前功尽弃了,我尝试了很多方法都没有解决这个问题,不确定是不是Reportlab自身的BUG,但我也有自己的解决方法,既然JPEG格式完美支持,那就在抓取到Image之后将先用PIL转换成JPEG再进行Build,这样便不会有问题了,不过对效率有少许的影响,因为转换的过程会花一些时间,图片一多的话会比较慢,但这个可以忽略,别人不会天天都拿来用,而且小数据量不会感觉到慢,偶尔过个几个月用一次多花点时间备份也无所谓了,只要保证可以正确生成就好了。

PDF可以不出错地生成之后我便发布了第一个Beta版本,虽然用的人不多,不过用过的人评价还不错,这也让我这个Python新手很受鼓舞,于是用PyGTK开发了GUI版本,之前用GTK给OPENFETION作的UI,对GTK比较熟悉,PyGTK就更简单不过了,花了一个晚上就把界面给做好了,当然很多细节的功能花了我一天多去完善,最后一天完全扔在了Windows打包上,太痛苦了。。。

接下来记录几个写Python几个小的Tips吧

1. 给PDF页面加脚注和页码:

Reportlab 对生首页和后续页面的处理,定义两个回调函数,如下:

def on_first_page(canvas, doc):   
	canvas.saveState()   
	canvas.setFont('song', 9)
	canvas.setFillColor('grey')
	footer = 'Generated by Tweets2pdf at %s' % \
	time.strftime('%a %b %d %H:%M:%S %Y', time.localtime())
	footer += ' Powered by @levin108'
	canvas.drawCentredString((PAGE_WIDTH)/2, 25, footer)
	canvas.restoreState() 
 
def on_later_pages(canvas, doc):   
	canvas.saveState()   
	canvas.setFont('song', 9)   
	canvas.drawString((PAGE_WIDTH/2)-5, 25, u"%d" % (doc.page - 1))   
	canvas.restoreState()
 
pdfdoc.build(elements, onFirstPage = on_first_page, onLaterPages = on_later_pages)

两个回调函数分别表示对首页和后续页面的处理,然后将这两个回调函数传给Build函数进行生成,在这里我给首页加了脚标,给后续页底部加了页码,最终Build在生成PDF的过程中会给每个页面做相应的处理。

2. 中文自动换行的设置

下面这段代码是我从网上搜到的,具体我没去研究,给Paragraph这个Flowable控件重定wrap方法便可以Paragraph中的内容实现自动换行:

def wrap(self, availWidth, availHeight):
	# work out widths array for breaking
	self.width = availWidth
	leftIndent = self.style.leftIndent
	first_line_width = availWidth - (leftIndent+self.style.firstLineIndent) - self.style.rightIndent
	later_widths = availWidth - leftIndent - self.style.rightIndent
	try:
		self.blPara = self.breakLinesCJK([first_line_width, later_widths])
	except:
		self.blPara = self.breakLines([first_line_width, later_widths])
	self.height = len(self.blPara.lines) * self.style.leading
	return (self.width, self.height)
Paragraph.wrap = wrap

3. PIL转换转换图片格式

img = Image.open(filename)
if img.mode != 'RGB':
	img = img.convert('RGB')
img.save(outname, 'JPEG')

其实只要第一行和最后一行便可以实现格式转换,但在其它格式转成JPEG的时候可能会有异常,所以需要先转换成RGB模式,然后再保存在JPEG。

4. 关于在浏览器中打开URL

之前一直都是用system(‘xdg-open …’)来在浏览器中打开URL的,但这种方法不能保证跨平台,Python有自己的相关模块Webbrowser

import webbrowser
webbrowser.open_new_tab(URL)

上面的语句表示在新标签页中打开URL

5. Windows移植
关于在Windows系统中的移植到是没花太多功夫,主要是一些关于路径的设置,但打包折腾了近一天的时间对弄了个勉强可以在Win7下面跑的版本,p2exe问题太多了,不搞了,还是等有兴趣有经验的牛人来搞吧。

以上是我开发过程的总结,新手欢迎拍砖~~~

分类: Python 标签: ,