存档

文章标签 ‘Linux’

武汉Deepin Linux DAU会议见闻

六月 1st, {2011 7 条评论 9,181 人阅读过  

上次在ubuntu11.04 release party北京站遇到deepin linux负责人刘文欢,他也就是deepin本人,邀请我去参加上个周末在武汉举行的deepin linux DAU大会,当时没有马上答应他,因为怕实验室太忙时间安排不开,后来跟领导商量了下领导表示支持,于是就趁周末跑了过去,一方面是希望能见到开源社区的朋友,另一方面也是很想看看deepin这个出自国人之手的linux发行版会做到什么水准。

会议到场人数很多,我作为特邀嘉宾很惭愧地坐在了前排,会议第一部分是deepin主题演讲,deepin操作系统创始人hiweed介绍深度的发展以及现状,接着是深度软件中心的主要开发者王勇介绍软件中心的相关情况,我个人感觉软件中心还是一个很不错的软件,虽然看上去很容易让人联想到360的软件中心,但不能不说这确实是一个很符合用户使用习惯的软件,从软件的搜索和安装都比ubuntu软件中心要舒服一些,当然这也是我个人的感受,据deepin介绍,软件中心的开发者王勇只有22岁,而且并没有读过大学,当时我就对他特别敬佩,像我们这些读了这么多年书现在还是这样技术平平的人真应该感到惭愧。最后由deepin本人介绍开源社区的管理与运营,让大家对深度这个社区有了一个比较深入的认识。

会议的第二部分是主题嘉宾演讲,第一位是国内开源界的名人袁萌教授,讲永中Office的事情,袁萌可以说是相当有争议的人物了,之前在ubuntu 10.10和11.04的release party现场都见过袁老出现,而且对于这种开源活动袁老似乎每次都不会缺席,这种活动每次出现的为数不多的老年人身影也就只有袁老了,但不管是他在新浪博客上还是在其它地方,大家对他的评论都是褒贬不一,我之前对袁老不熟悉,后来在twitter上打听袁老的事情,有人表示袁老人不错,但口头老挂着永中和U盘的事情就让人有点烦了,确实,袁老讲话我听不太明白(口音原因),但言谈中总会提到永中和U盘的事情,我对此到没什么特别的看法,可能年纪大了人会比较偏执,遇到自己觉得好的东西就会一直推崇。再看他的新浪博客,有人支持也有人很负面地骂,确实让人感觉到袁老真是中国开源界最有争议的人物,其实我觉得像袁老这样一位古希老人,不图名利,仍然能对中国的开源事业如此热心,已经实属不易了,即便大家对他的观点不认同,也不至于用那么偏激的语言去骂他,除非你让我去相信这样一位风烛残年的退休老教授还在用某种低劣的手段去谋取私利,与袁老见面听他言谈,感觉他人非常正直,绝不是什么小人,所以我觉得大家可以不喜欢他,但真的没有必要去骂他。

会议袁老讲完后我也给大家就我的一些经历做了个小报告,简单介绍了一个飞信的开发过程以及我个人的Linux使用经验等,接下来是中科大的张成同学讲在校园同推广Linux,张成是mirrors.ustc.edu.cn的现任维护者,中科大开源协会的副会长,感觉中科大的开源协会做得蛮不错的,大家都很热心地在做一些很有意义的事情,张成技术也非常不错,再一次让我表示汗颜。再之后便是在场的用户提问,具体都问了哪些问题我也记不清了,我也没有刻意地去做会议记录。

会议结束后第二天晚上我和deepin在他们公司单独聊了两个多小时,deepin确实是想在Linux发行版这一块做些事情出来的,在中国做这样的事情难免会遇到种种阻力,包括舆论上的政策上的等等,红旗这样一个烂到根的公司似乎让国人对国产Linux发行版很是绝望,雨林木枫反对的人也很多,我到不太了解原因是什么,我个人不太喜欢它是因为它之前山寨了Windows的UI来适应中国用户的使用习惯,其实说起来如果没有什么版权协议的问题的话也没什么不好。做操作系统是个很漫长的过程,不可能在一两年内就得到用户的普遍认可,即便是ubuntu也是经历了一个长期的过程,Canonical公司也出资做了那么久的公益,说实话,哪家做Linux的公司纯粹做公益我们都没法相信,包括Canonical也是想用ubuntu做出一个品牌再去拓展其它的业务,如ubuntu server. 当然,深度的经济实力远不如Canonical,但做发行版在最开始是很难有经济回报的,我们所能期望的就是深度能坚持下去,毕竟深度和红旗是两家完全不同性质的公司,应该不会像红旗那样腐化,而做这样一个发行版也一直是hiweed和deepin的梦想,其实我个人还是对他们挺有信心的,即便中国人做不出来自己自主研发的操作系统,能出一个被国际认同的Linux发行版也确实是一件好事。

我是站在一个中立的立场,我支持我认为好的东西,如果有一天深度变成了红旗那我也会跟着去骂的。当时deepin在北京给我演示深度系统的时候我真地觉得很不错,起码它降低了新手的技术门坎,通过虚拟化的手段让OFFICE和QQ都跑在了上面,可以说这两个软件对很多新用户来说都是很大的壁垒,这个问题解决了就解决了很多新手的烦恼,我个人觉得任何一家第三方的OFFICE都很难与MS OFFICE兼容,即便是永中它的公式编辑器也完全跟不上。他们没有集成这两款软件,也就不涉及到版权协议之类的问题了。

总之这一行还是受益匪浅的,希望几年之后deepin能成为让国人为之骄傲的发行版,当然也希望它千万不要成为第二个红旗。

分类: Linux 标签: ,

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

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

在向外发送数据包的时候,首先需要查询路由表来确定路由包的路由,主要由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,323 人阅读过  

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 标签: ,

openfetion cli功能开发手记

十二月 19th, {2010 11 条评论 32,118 人阅读过  

之前一直有用户提出的命令行短信功能终于被我落实了下来,不过却让很多网友失望,因为所谓的命令行并非是纯命令行,而是需要先有openfetion GUI版本登录以作为server,cli程序通过IPC将数据交由server转发,自己并不进行与sipc server的直接数据通信,也就是必须有X图形界面的支持,当然如果要把现在的openfetion server做成不需要图形界面支持的deamon server还存在很多问题,如deamon在收到短信时该怎么处理等,另外deamon server的开发应该也需要花些时间,这个暂时未做考虑,而基于目前的飞信协议如果要发送短信则必须进行身份验证,也就是纯命令行不需要deamon server支持的飞信必须在每次发短信之前都需要登录一次,考虑到这个问题就迟迟没有开发纯命令行的版本,主要是觉得这种形式的短信发送方式存在的意义不大,不仅速度慢而且需要经过复杂的身份验证,但很多用户想用它管理server的话那也就只能这样来实现了,技术上其实问题不大,调用libofetion的api很简单就能实现,过几天抽点时间写一个看看,今天先把已经实现的CLI功能的开发过程总结一下。

首先,先看一下CLI的使用方法:

程序很简单,只加了三个个文件,分别是src/fx_server.c,src/fx_cli.c和include/fx_server.h

服务器端初始化init_server函数来初始化server,函数如下:

int init_server(FxMain *fxmain)
{
	int   fifo;
	User *user = fxmain->user;
 
	char server_fifo[128];
	snprintf(server_fifo, sizeof(server_fifo) - 1, OPENFETION_FIFO_FILE, user->mobileno);
 
	if(mkfifo(server_fifo, FIFO_FILE_MODE) == -1
			&& errno != EEXIST) {
		debug_error("create fifo %s:%s\n", server_fifo, strerror(errno));
		return -1;
	}
 
	if((fifo = open(server_fifo, O_RDONLY, 0)) == -1) {
		debug_error("open fifo %s:%s\n", server_fifo, strerror(errno));
		return -1;
	}
 
	if((idlefifo = open(server_fifo, O_WRONLY, 0)) == -1) {
		debug_error("open fifo %s:%s\n", server_fifo, strerror(errno));
		close(fifo);
		return -1;
	}
 
	return fifo;
}

这个函数对IPC进行了一些初始化,首先创建以“openfetion_fifo_登录手机号 ”命名的命名管道文件,分别打开两次,一次为只读,用于监听client发来的IPC请求,另一个为只写,这个描述符打开之后从来没有使用过,这也是UNP第二卷里面提到的小技巧,当client关闭时会关闭打开的命名管道描述符,这里server中的read函数便会返回0,从而标识client关闭,这时server便需要关闭描述符重新打开关监听,为了避免这样一种情况,server自己以只写的方式打开这个通用描述符而不写入任何数据,这样server在收不到数据时read函数便会一直阻塞。

FIFO也是基于流的通信方式,所以需要自定义消息,没有什么复杂的数据需要传输,我就简单定义了两种消息,请求消息和应答消息:

struct fifo_mesg {
	unsigned short type;
	unsigned short length;
	unsigned int  pid;
};
 
struct fifo_resp {
	unsigned short code;
	unsigned short length;
};

请求消息中的pid字段为client进程的pid,client在向server发起请求之后会打开openfetion_fifo_pid命名的FIFO等待server返回响应,而server在收到请求之后可以提取出请求消息中的pid,从来找到client用于监听的命名管道文件,将返回消息通过命名管道再反馈给client。
目前请求信令的类型只有两种:

/* 发送短信 */
#define CLI_SEND_MESSAGE    1
/* 获取用户信息 */
#define CLI_GET_INFORMATION 2

应答信令的应答码也只有两种:

/* 操作已成功 */
#define CLI_EXEC_OK   200
/* 操作失败 */
#define CLI_EXEC_FAIL 400

请求消息体中为XML格式,应答消息体中为纯文本提示消息。请求信令消息体如下:

<r><m no="15200000000" bd="hello world" p="1" /></r>

其中no表示要发送的好友手机号码,注意该好友必须在好友列表中,并且必须对你已设置公开手机号,bd为要发送的短信,p为是否用直接发送到用户手机。该消息发送到server后,server发现请求的号码与自己的号码相同时,会将消息发送至用户自己的手机中。

OK,过程就这么多吧,没有超过1K行代码,也复杂不到哪里去,接下来看看时间来不来得及写一个纯命令行的版本,有需要的同学请关注。

分类: C/C++ 标签: , , ,

linux终端中输出彩色字体(C/SHELL)

十二月 15th, {2010 3 条评论 14,522 人阅读过  

这几天在用libvlc的时候看到它在terminal里面输出彩色字体觉得挺好玩的,以为是用ncurses实现的,后来一查原来用ANSI C的转义字符就可以实现,不过好现只在linux下有效吧, windows神马的貌似不行,把项目终端凌乱的输出信息整理了一下,关键字符也都用彩色显示,看上去舒服多了,写一下用法以防止以后忘了再去查。

先把控制码列出来(从网上搜来的):

\033[0m               关闭所有属性
\033[1m                       设置高亮度
\033[4m                       下划线
\033[5m                        闪烁
\033[7m                        反显
\033[8m                        消隐
\033[30m----\33[37m 设置前景色
\033[40m----\33[47m 设置背景色
\033[nA                        光标上移n行
\033[nB                       光标下移n行
\033[nC                       光标右移n行
\033[nD                       光标左移n行
\033[y;xH                     设置光标位置
\033[2J                        清屏
\033[K                         清除从光标到行尾的内容
\033[s                          保存光标位置
\033[u                          恢复光标位置
\033[?25l                      隐藏光标
\033[?25h                     显示光标 
背景色:
40:黑 41:深红 42:绿 43:黄色 44:蓝色 45:紫色 46:深绿 47:白色
前景色:
30:黑 31:红 32:绿 33:黄 34:蓝色 35:紫色 36:深绿 37:白色

控制字符是打开某种样式,输出完成时需要再关闭样式才能使terminal恢复到原来状态,简单例子:

printf("\e[32m%s\e[0m\n", "hello world");

\033\e是一回事,使用\e会更简单一些,输出为绿色字体,如下图:

\e[32m为打开绿色前景色样式,\e[0m为关闭所有样式,如果未关闭,则所有输出字体均为绿色前景色,如下代码:

	printf("\e[32m%s\e[0m\n", "hello world");

输出效果如下:

绿色高亮代码如下:

printf("\e[32m\e[1m%s\e[0m\n", "hello world");

输出效果如下:

另外光标移动的控制码在输出类似于下载进度的信息时用得到。

在shell中也可以直接用echo输出,需要加-e选项打开转义字符解释,如输出高亮的绿色字体为:

echo -e "\e[32m\e[1mhello world\e[0m"

其它的我也没怎么看,觉得也就改变字体颜色和移动光标位置能用得到,觉得挺好玩的就写下来以后忘了查一查。

分类: Linux 标签: , ,

linux网络编程手记

十二月 12th, {2010 4 条评论 12,812 人阅读过  

做linux下的网络编程有一段时间了,中间遇到过很多问题,其中不少是因为自己对网络编程和网络协议的一些基本概念搞不清楚,趁着今天没心情干活就把自己在网络编程方面的理解和一些经验总结一下,Request For Comments。

在诸多的网络协议中接触的最多也最紧密的无疑是TCP和UDP,SCTP之前因为项目原因也研究过,不过最终由于方案修改给抛弃了,TCP年代已经很久远,在网上的资料也非常多,而且我感觉它是一种非常复杂的协议,感觉要把编好基于TCP的程序光简单地了解几个socket API是不够的,刚开始接触网络编程的时候自己确实也吃了不少苦头,后来我还专门拿时间出来阅读了一下RFC,再加上长时间的实践总算也对TCP有所了解,把自己的一些经验和教训都总结一下。

首先说一下TCP的状态转移图,这个应该是很重要的,了解TCP运行周期的各种状态才能更好地运用netstat之类的应用程序去对程序进行调试,我这里收藏了一张图,是TCP的状态图,记不清是从哪里找来的,也不知道直接版权该给谁,但这张图应该最终是出自于UNP第一卷的,那copyright就是UNP了吧。

1.TCP连接状态

连接建立的几个状态没什么可说的,TCP的三次握手众所周知,更重要的是TCP连接中止的几个状态,应该可以说是连接中止需要四次握手吧。

当Client调用close函数主动关闭socket时,连接状态被标记为FIN_WAIT_1,Server在收到FIN之后read函数会返回0,这里server知道Client已经关闭连接,回复ACK,这里client连接状态被标记为FIN_WAIT_2,接下来Server调用close函数关闭连接,这时候Server向client发送FIN,Client收到之后将状态标记为TIME_WAIT,并回复ACK。

TIME_WAIT这个状态存在的意义在于Client回复的ACK未必会被Server收到,可能在传输过程中导致包的丢失,而这里Server未收到ACK之后会重新向Client发送FIN,如果client未将状态标记为TIME_WAIT而是直接标记为CLOSED,则Server发送的FIN会直接收到RST,导致Server端的发送错误,因此Client需要保证有一个TIME_WAIT状态,而这个状态会持续两位的MSL(最大段生命周期),从而保证Server成功发送FIN并发送ACK,为了保证两个数据段传输的最大时间,因此TIME_WAIT持续的时间为两倍的MSL。

Server在收到第一个FIN之后会将状态标记为CLOSE_WAIT,此时是client主动关闭连接,这里Server也需要调用Close给Client发送FIN(如上所述),之后Server的状态标记为LAST_ACK,表示Server正在等待Client发送的最后一个ACK,当Server收到最后一个ACK便会将连接标记为CLOSED,这时连接结束。TIME_WAIT这个状态和套接字的SO_REUSEADDR选项是有关系的,这个留做后面讨论。

2.TCP连接异常情况

TCP连接异常分为很多种情况,无论是客户端程序还是服务器端程序都需要考虑周全的。

Server在连接的过程中程序崩溃或者CTRL+C中止程序,或者kill接Server进程。这时会导致Server立即发送一个FIN数据包给Client,Client如果此时正在调用recv函数,则recv函数返回0,表示服务器已关闭连接,如果Client调用send函数继续向Server发送数据,Server在收到后会回复RST,而此时send方法会触发SIGPIPE信号,表示通信管道已断开,在程序中如果对该信号不做处理则会导致程序的崩溃,一般在程序开始时会忽略此信号,则在这种情况下send函数会返回-1,表示发送失败,处理SIGPIPE的代码如下:

前几天实验室这个破项目非要加上什么流媒体的功能,简单起见使用了VLC来实现,客户端这边就得需要把相关的播放界面整合到现有的界面里面来,之前的客户端UI我都是用GTK实现的,没办法,GTK用得比较多,相对熟练一些就用GTK来做了,没想到要把VLC整到GTK里面来那么麻烦,原生的libvlc是不支持GTK的,需要加一层libvlc-gtk,从网上好不容易下载到了libvlc-gtk的源码,从哪里下的也记不清了,反正就是零散地几个文件,没有README甚至连Makefile都没有,没办法首先得先写个Makefile把它编译一下,libvlc-gtk一共有八个文件,Makefile如下:

struct sigaction sa;
sa.sa_handler = SIG_IGN;
sigaction(SIGPIPE, &sa, 0 );

另外在这种情况下select函数也会立即返回,socket描述符会被设置,而试图从该socket中recv数据,则会返回-1。

另外一种情况是Server系统崩溃或者网络直接异常或断开,这时候Server不可能再给Client发送FIN包,而Client调用send函数后会导致数据包一直重传直接超时后返回-1,而recv函数也会一直阻塞直接超时后返回-1。这种情况就很难判断是Server端进程关闭还是网络异常,这种情况一般会用TCP的KEEP ALIVE机制,每隔一定的时间向对方发送一个只有一字节数据内容的数据包,对端收到后会返回一个ACK,以此来确保连接正常,如果未收到ACK,会尝试重传,直到重试规定次数后可以将与对端的连接标记为断开,send和recv将会返回-1。KEEP ALIVE的使用方法如下:

int tcp_keep_alive(int socketfd)
{
	int keepAlive = 1;
	int keepIdle = 10;         /* 开始发送KEEP ALIVE数据包之前经历的时间 */
	int keepInterval = 10;   /* KEEP ALIVE数据包之前间隔的时间 */
	int keepCount = 10;     /* 重试的最大次数 */
 
	if(setsockopt(socketfd , SOL_SOCKET , SO_KEEPALIVE
				,(void*)&keepAlive,sizeof(keepAlive)) == -1){
		debug_info("set SO_KEEPALIVE failed\n");
		return -1;
	}
 
	if(setsockopt(socketfd , SOL_TCP , TCP_KEEPIDLE
				,(void *)&keepIdle,sizeof(keepIdle)) == -1){
		debug_info("set TCP_KEEPIDEL failed\n");
		return -1;
	}
 
	if(setsockopt(socketfd , SOL_TCP , TCP_KEEPINTVL
				,(void *)&keepInterval,sizeof(keepInterval)) == -1){
		debug_info("set TCP_KEEPINTVL failed\n");
		return -1;
	}
 
	if(setsockopt(socketfd , SOL_TCP , TCP_KEEPCNT
				,(void *)&keepCount,sizeof(keepCount)) == -1){
		debug_info("set TCP_KEEPCNT failed\n");
		return -1;
	}
	return 1;
}

上面这个函数只针对Linux,昨天有网友告知在Mac OS上TCP_KEEPIDLE ,TCP_KEEPINTVL, TCP_KEEPCNT这些宏将未定义。另外对于这些参数的设置也是需要注意的,很多系统中它们的设置并不是对单个socket描述符起作用的,而是该机器上的所有socket描述符起作用的,所以这个需要注意(这个是从UNP里面看到的)。

3.关于字节顺序
Linux的主机字节顺序是采用little-endian字节顺序,而网络字节顺序是采用big-endian字节顺序,字节顺序转换是必需的。写了一个小程序来检测字节顺序,不知道对不对,Request For Comment.

#include 
 
int main(int argc, char **argv)
{
	short s = 0x0102;
	if((*(unsigned char*)&s) == 2)
		printf("little endian\n");
	else if((*(unsigned char*)&s) == 1)
		printf("big endian\n");
	else
		printf("unknown endian\n");
 
	return 0;
}

3.关于send和recv

写过socket程序的人肯定都会知道send和recv函数并不会总是返回要求发送或读取的字节数,如:

int ret = recv(sk, buf, 2096, 0);

这句话并不总是读取到完整地2096个字节,相反地,大多数情况下都不能将buf读满,recv只能返回当前可以读取到的字节数,如果协议规定本次读取肯定会读取到N个字节,那我一般的做法会写一个这样的函数来确保读取到固定的字节数:

int buf_recv(int sock, void *buf, size_t len, int flags)
{
	int n, ret;
	if(len == 0) return 0;
	for(n=0;n!=len &&(ret = recv(sock, buf+n, len-n, flags)) != -1 &&ret; n += ret);
	return (n!=len)? -1:n;
}

关于这两个函数还有很重要的一点是应该尽可能大地一次发送或接收更多地数据,当然前提是缓冲区中有这些数据的话,原因很简单,当通信链路很好的时候数据可能会填满系统缓冲区,而recv便是从缓冲区中读取数据,这时候一次读取更多地字节就意味着可以少调用几次recv函数,而这些函数通常都是调用了系统调用,需要进行内核态和用户态上下文的切换,也就意味着多调用几次recv会带来额外的开销,之前写的一个代理服务器的程序数据传输速度一直很低,后来修改了recv和send的缓冲区大小后速率提高了近一倍。

4.关于非阻塞模式

一般应用的时候都是使用阻塞式IO,至少我在大多数情况下都用的阻塞式IO,非阻塞很少应用,但存在便我价值,我用到的非阻塞IO的情况一般是用来进行超时connect,首先将socket设为非阻塞模式,connect立即返回-1,此时已向对端发送FIN,而并未来得及收到任何ACK,于是直接返回-1,但并不代表连接失败,errno会被置为EINPROGRESS ,表示连接正在进行中,然后通过select来设置socket可写的超时时间,如果规定时间内可写,且socket并无出错,则表示连接成功,socket出错则表示连接失败,或规定时间内不可写则表示连接超时,简单地写了如下代码:

#include
#include
#include
#include
#include
#include
#include 
 
int main(int argc, char *argv[])
{
	int                sk;
	int                flags;
	int                err = 0;
	int                ret;
	socklen_t          len;
	struct sockaddr_in addr;
	fd_set             fd_write;
	struct timeval     tv;
 
	if( (sk = socket(AF_INET, SOCK_STREAM, 0)) == -1 ) {
		perror("socket");
		return 1;
	}
 
	if( (flags = fcntl(sk, F_GETFL, 0)) == -1 ){
		perror("fcntl GET flags failed");
		return 1;
	}
 
	if(fcntl(sk, F_SETFL, flags | O_NONBLOCK) == -1) {
		perror("fcntl SET flags failed");
		return 1;
	}
 
	memset(&addr, 0, sizeof(addr));
	addr.sin_family = AF_INET;
	addr.sin_addr.s_addr = inet_addr("59.64.129.169");
	addr.sin_port = htons(808);
 
	if(connect(sk, (struct sockaddr*)&addr, sizeof(addr)) == -1	) {
		if(errno != EINPROGRESS) {
			perror("connect");
			return 1;
		}
		FD_ZERO(&fd_write);
		FD_SET(sk, &fd_write);
		tv.tv_sec = 5;
		tv.tv_usec = 0;
 
		ret = select(sk + 1, (fd_set*)0, &fd_write, (fd_set*)0, &tv);
 
		if(ret > 0){
 
			if(FD_ISSET(sk, &fd_write)) {
				len = sizeof(int);
 
				if(getsockopt(sk, SOL_SOCKET, SO_ERROR, &err, &len) == 0) {
					if(err == 0) { printf("connect success\n"); return 0; }
					else { fprintf(stderr, "connect:%s\n", strerror(err)); return 1; }
				}else{
					fprintf(stderr, "getsockopt:%s\n", strerror(err));
					return 1;
				}
			}else{
				fprintf(stderr, "connect(FD_ISSET) failed\n");
				return 1;
			}
 
		}else if(ret == 0) {
			fprintf(stderr, "connect timeout\n");
			return 1;
		}else {
			fprintf(stderr, "connect(select):%s\n", strerror(errno));
			return 1;
		}
	}else{
		fprintf(stderr, "connect:%s\n", strerror(errno));
		return 1;
	}
	return 0;
}

5.关于select多路复用

select是网络编程中很常用的函数,用来进行IO多路复用,但之前我一直忽略了一个问题,当select返回时会将本次检查中不可用的描述符(如不可读或不可写)的描述符从描述符集中删除,只保留当前可用的描述符,在对多个socketfd进行利用的时候需要注意,每次循环select之前都需要在select之前用FD_SET重新设置描述符,否则之后便只能返回第一次可读的描述符了。

6.关于UDP广播

UDP广播这个也简单说一下,首先255.255.255.255这个地址是不能被路由的,只能被本物理网络的数据包接收。UDP广播之前需要给socket设置SO_BROADCAST选项:

int brodopt = 1;
setsockopt(cp_usock, SOL_SOCKET, SO_BROADCAST, &brodopt, sizeof(brodopt));

UDP广播需要注意的一点是广播接收时接收端bind的本地地址的问题,接收端必须绑定INADDR_ANY这个地址才可以接收广播包,如果是绑定的某个特定的地址则无法接收广播包。

OK,简单说这么几条,都是我编程时候遇到的经验总结,以后再遇到什么问题再接着补充。

分类: Linux 标签: , ,

OpenFetion V2.0正式版发布

十月 24th, {2010 74 条评论 21,554 人阅读过  


经过近一个月的修改测试,Openfetion 2.0正式版今天release出来了,相比于之前的1.x版本相比,2.0有更多的优点和特性,最重要的是2.0稳定性较之于之前版本登录速度更快,稳定性更高。

这次版本主要集中在解决历史版本中所存在的登录崩溃,运行时崩溃的问题,以及用户所普遍反映的登录速度过慢的问题,引入了SQLITE3来实现了数据的本地化,使登录过程需要下载的数据量很小,从而大大提高了用户登录速度,也因为实现了数据的本地化,新版本也增加了离线和离线登录功能。

新版本另一个重要的特性是检测网络状态,可以实现断线检测并自动重连,失败时会显示用户离线,而不是之前离线时直接退出程序。检测网络状态需要NetworkManager的支持,此依赖库为可选,如果安装时disable,则不具有自动重连功能。

另外新版本增加了空闲时间自动离开功能,空闲时间目前固定为3分钟。此功能需要XScreenSaver的支持,此依赖库也为可选。

另外新版本再一次更换了图标,新图标由@riku设计,由@xhacker修改,感谢二位对OpenFetion做出的贡献。

下面是ChangeLog:

2010-10-24 levin

* 修复了登录和运行时的崩溃问题
* 修复了群发短信时的崩溃问题
* 修复了添加好友时的崩溃问题
* 添加了数据本地化,实现了离线登录功能
* 添加了断线自动重连功能
* 添加了空闲时间自动离开功能
* 添加了关闭上线提示的功能
* 优化了登录过程,登录速度更快
* 更换了新版图标,更美观

程序添加的依赖库为libsqlite3,NetworkManager,XScreenSaver,Ubuntu下的安装方法如下:

sudo apt-get install libxml2-dev
sudo apt-get install libgtk2.0-dev
sudo apt-get install libssl-dev
sudo apt-get install libnotify-dev
sudo apt-get install libgstreamer0.10-dev
sudo apt-get install intltool
sudo apt-get install libsqlite3-dev
sudo apt-get install libnm-glib-dev
sudo apt-get install libxss-dev

ubuntu用户推荐使用happyaron制作的PPA安装,该PPA于10.24日晚将会更新到最新版本,安装方法如下:

sudo apt-add-repository ppa:happyaron/ppa
sudo apt-get update
sudo apt-get install openfetion

Fedora用户依赖库安装方法如下:

pkcon install gcc gstreamer-devel gtk2-devel libxml2-devel openssl-devel intltool 
sqlite-devel NetworkManager-devel libXScrnSaver-devel libnotify-devel

期待各方打包人士制作相关安装包

源码下载地址:
http://code.google.com/p/ofetion/downloads/list

Follow Me @levin108

分类: Linux 标签: , , ,

Openfetion近期开发手记(相关功能实现技术)

十月 18th, {2010 29 条评论 8,252 人阅读过  

离上Openfetion上一个版本发布至今过了有将近一个月的时间了,上个版本放出的时候本以为已经解决了很多bug,但发布之后才发现用户遇到的问题还是很多,软件测试还是很重要的,当然有些协议上的问题只能交由用户去测试,我没有那么多飞信号,有些问题有很难遇到的,也很难复现的,所以就在这样不断地与用户沟通中解决问题。

其实做共享软件是件很开心的事情,不管你做得好不好,都会有人支持你,这个是很重要的,因为在最初开发openfetion的时候并没有想过要把它做为一个专业的飞信客户端放出来大家一起使用,可发布之后得到了广大linux用户的支持,即使那时候的bug比现在多得多,仍然有用户乐此不彼地帮我测试,反溃问题,提供建议,当然我也乐此不彼地修改程序,希望有朝一日它能让所有的用户都能稳定地运行,这也是自由软件的优势,如果当初这做为一个商业软件发布,我想毫无疑问,收到的会是一片骂声,然后这个项目也便会匆匆截止,而现在即便很忙也会拿出一些时间来加强它,因为总会有用户支持着它,也会有开源爱好者加入进来做一些贡献。

Openfetion下一个的版本号应该是2.0了,我想2.0应该和之前的1.x版本有所区别,功能上这个不是特别重要,因为之前的版本已经有了几乎所有的基本功能,其它的一些不常用的功能我也没考虑过,因为开发那些功能是一件性价比很低的事情,现在所能想到的2.0和1.x的区别应该是让2.0更加稳定,功能再丰富如果不能稳定运行这个软件就永远成不了优秀的软件,因为我在新版本里面做了大批量的代码修改,甚至包括以前一些很不专业的编码习惯,尽可能将所有潜在的问题都消灭掉,当然也加了一些用户一直以来要求的功能,下面简单地说一下。

首先,是在之前版本中,用户反映登录速度过慢,这个我承认,是因为在之前的版本中没有加入数据的本地缓存,每次用户登录的时候都会需要重新从服务器上请求自己相关的所有数据,包括用户列表和配置文件这样庞大到几个K甚至十几个K的数据,这不可避免地会导致登录过程过慢,甚至网络状况不好的时候,会导致在获取配置文件的时候卡在那里,这些问题都降低了用户体验,解决这些问题的方法毫无疑问是加入本地用户缓存,这也是网络软件所常用的方式,之前我把一些本地配置信息和聊天记录保存在本地所用的方法是直接使用二进制写入dat文件,那种方法灵活性非常差,而且效率也很低,所有就没有对其它的动态数据做缓存,现在在新版本中引用了sqlite3,这个轻量级的数据库无疑是实现这个功能的绝佳选择,使用起来很简单,而且灵活性也很高,基本的SQL语句几乎都支持,之前只是知道有这么个东西,但一直没用过,这次试了一下,发现使用起来也非常简单,于是毫不犹豫就把它给引入了,我想加入了这样一个依赖所带来的用户体验的提高是很大的,希望不会有用户抱怨引赖关系增多。

另外,在将数据进行本地缓存之后便为另一个功能的实现提供了基础,那就是离线登录功能,和IM的离线功能一样,就是在没有网络连接的情况下登录Openfetion,可以查看好友列表,当然这些好友信息都是存储在本地数据中的,通过sqlite3从数据库中提取出来的。

聊天记录改用sqlite3存储之后提取和写入也都方便了很多,而且还添加了删除聊天记录的功能,之前用二进制数据直接写入的方式保存聊天记录所带来的不便就是不能方便地删除聊天记录,如果要删除只能先把整个聊天记录都加载到内存中,然后从中删掉要删除的信息,之后再重新写入磁盘覆盖掉原来的文件,这样效率是非常低的,而用sqlite3直接可以用一条DELETE语句删掉想要删除的信息。

同样这次也加入了本地用户列表删除功能,用户登录完后记录在本地的用户名密码数据也同样都可以删除。

另一个很重要的功能是空闲时间自动离开功能,这个功能之前一直不知道该怎么实现,纠结于当焦点不在Openfetion中时,如何获取全局的鼠标键盘动作,而即便获取到了又如何检测是否空闲,这些问题都非常麻烦,后来查看了一下pidgin的源码,才发现其实IM软件所实现的空闲时间检测功能一般都是通过调用XScreenSaver来实现的,包括之前的evaqq也是之样实现的,过程很简单,下面的几行代码便是获取空闲时间的函数,通过周期性地检测空闲时间便可以判断出IM是否需要进行离开状态。

gint idle_timesec(void)
{
 
#ifdef USE_LIBXSS
	static XScreenSaverInfo *mit_info = NULL;
	static gint has_extension = -1;
	gint event_base, error_base;
 
	if (has_extension == -1)
		has_extension = XScreenSaverQueryExtension(
				GDK_DISPLAY(), &event_base, &error_base);
 
	if(has_extension){
		if (mit_info == NULL)
			mit_info = XScreenSaverAllocInfo();
 
		XScreenSaverQueryInfo(GDK_DISPLAY(), GDK_ROOT_WINDOW(), mit_info);
		return (mit_info->idle)/1000;
	}
#endif
	return 0;
}

这需要XScreenSaver的支持才行,于是加入了条件编译,在ubuntu或者debian中可以通过下面的命令安装XScreenSaver开发包:

sudo apt-get install libxss-dev

另外一个很重要的功能是断线自动离开功能,这个用tcp的相关特性来检测链路状态灵敏性太低,参考了一下pidgin和empathy,它们用的方法都是调用NetworkManager的相关API来实现的,NetworkManager是基于dbus的,之前在slackware13.1上因为安装NetworkManager失败,而导致之前同学写的基于nm和dbus的程序在我这里不能跑,从而对这个一直留有某种恐惧感,当然现在也意识到要让程序在网络状态改变的时候即刻感知到,最佳方法还是使用libnm,下面的函数便是初始化libnm的函数,它为网络状态改变的事件注册了回调函数nm_state_change()

void fx_conn_init(FxMain *fxmain)
{
#ifdef USE_NETWORKMANAGER
	GError *error = NULL;
        DBusGConnection *nm_conn = NULL;
        DBusGProxy *nm_proxy = NULL;
 
	nm_conn = dbus_g_bus_get(DBUS_BUS_SYSTEM, &error);
	if (!nm_conn) {
		debug_error("Error connecting to DBus System service: %s.\n", error->message);
	} else {
		nm_proxy = dbus_g_proxy_new_for_name(nm_conn,
		                                     NM_DBUS_SERVICE,
		                                     NM_DBUS_PATH,
		                                     NM_DBUS_INTERFACE);
		dbus_g_proxy_add_signal(nm_proxy, "StateChange", G_TYPE_UINT, G_TYPE_INVALID);
		dbus_g_proxy_connect_signal(nm_proxy, "StateChange",
		                        G_CALLBACK(nm_state_change), fxmain, NULL);
	}
#endif
}

下面的代码是回调函数的代码,在它里面能过检测各种网络状态而做出相应的动作:

static void
nm_state_change(DBusGProxy *proxy, NMState state, gpointer data)
{
	switch(state)
	{
		case NM_STATE_CONNECTED:
			debug_info("network is connected");
			break;
		case NM_STATE_ASLEEP:
			debug_info("network is sleeping...");
			break;
		case NM_STATE_CONNECTING:
			debug_info("network is connecting...");
			break;
		case NM_STATE_DISCONNECTED:
			debug_info("network is disconnected");
			break;
		case NM_STATE_UNKNOWN:
			debug_info("unknown network state");
		default:
			break;
	}
}

ubuntu或debian中NetworkManager开发包的安装方法如下:

sudo apt-get install libnm-glib-deb

要说的是,XScreenSaver和NetworkManager的使用都是可选项,为了避免不愿意引入这些库的用户抱怨,可以在configure的时候用–disable-screensaver和–disable-nm将其禁用。

另外也解决几个崩溃的bug,比如添加好友时崩溃,这个纯粹是我编码过程中出现的失误,还有群发短信时崩溃的问题,这个也是我编码的失误,都已经修改过来了,有时候收到的信息会显示发送失败,这个也修改好了,一个比较重要的bug是多人同时聊天在窗口切换的时候可能会崩溃的问题,这个问题现在也已经解决了。

有时候程序会出现 ”Program received signal SIGPIPE, Broken pipe.“这样的错误,这个信号一般是在服务器端主动关闭连接时客户端会收到的来自操作系统的信号,理论上服务器端主动关闭连接这个可能性不大,但它有时候确实会出现,之前没有对这个信号进行处理,这次把这个信号直接忽略了,然后在send和recv的时候就会返回-1,通过返回值就可以检测连接状态。

 struct sigaction sa;
 sa.sa_handler = SIG_IGN;
 sigaction( SIGPIPE, &sa, 0 );

还有用户提到在登录时登录按钮状态不变,这个之前没怎么在意,这次也修改过来了,不过没有加取消登录的功能,这个也考虑过,不过没想到实现的方法,因为登录线程用的是gthread库,而它没有像pthread一样提供取消线程的方法,一时间也不知道该怎么去实现,这个先暂时一放,希望有了解这个的朋友可以提供些帮助,现在的实现方法是像官方飞信一样在点击登录后改变登录界面,自己还用GIMP做了个登录正在进行的gif,就是让Openfetion的图标一直在转,哈哈,很有成就感,上两个登录界面的图吧。

image image

图片里面没有打码,这个飞信号是我测试用的小号,无所谓了,反正也不用。

这次新版本想多测试一段时间再发,肯定还存在问题,尽可能在发布之前能解决更多的问题,能让2.0正式版更稳定,能让用户更满意,同时也欢迎大家到svn上co最新的版本试用,并帮忙测试,如果你有问题,请向我反溃,这样我才能帮你解决问题。svn :

svn checkout http://ofetion.googlecode.com/svn/trunk/ ofetion-read-only

分类: C/C++ 标签: , , ,

linux0.11里面发现的好玩的链表指针迭代方法

八月 30th, {2010 2 条评论 7,329 人阅读过  

linux的内存管理一直是让我最困惑的,2.6版本内核里面各种复杂的机制搞得我云里雾里,甚至搞不明白内存管理最基本的原理是什么,于是翻阅早期版本的内核0.11,最底层的内存分段和分页我都已经在我的plinux上实践过了,读到malloc的时候发现了linus用了一种很好玩的指针迭代方法,至少我以前没见过,见识短浅,大家莫笑。

linus把一页内存分成一个个具有相同大小的内存块,然后又将这些个内存块组成一个链表,而这些内存块都是将来要分配出来的空闲内存,它们内部并不包含有任何对象,要组成链表就必然要求有指针,linus把每块内存的前4个字节拿出来作为指针,指向下一块内存的首地址:

char  *cp;
/* 在这里获取一页空闲内存 */
(void*)cp = get_free_page();
 
for(i = PAGE_SIZE/bdir->size; i > 1; i --){
/* 我觉得这里很有意思,把一个字符指针强制转换成指向字符指针的指针,
然后再对其解引用赋值,相当于把cp开始的前4个字节作为一个指针并对它进行定向 */
    *((char**)cp) = cp + bdir->size;
    cp += bdir->size;
}

然后在指针迭代的时候用了下面这种方法,不复杂,只是觉得挺有意思的:

void *retval = (void*)freeptr;
freeptr = *((void**)retval);

这样freeptr就指向了下一块空闲内存。

分类: C/C++ 标签: ,

Automake生成Makefile过程简介

二月 26th, {2010 1 条评论 10,768 人阅读过  

有校友在byr上看了我发的openfetion,发信息问我关于automake的东西,其实我了解的也并不多,只是自己查了些资料,然后借鉴了一下别人的项目中相关文件的写法,于是就想照着openfetion中的相关文件把自己对它的理解简单写一下,算是整理一下学过的知识,以后也好有个参考。
Automake支持三种目录层次:flat,shadow,deep
1.flat 所有的源文件及相关文件都放在顶层目录中。
2.shadow 主要的源文件存放在顶层目录中,其它的存放在各个子目录中。
3.deep 所有的源文件都分别存放在各个子目录中。

我的程序用了deep模式,所有的源文件都放在了src目录中。下面写一下automake生成Makefile的步骤:
1.运行autoscan命令,生成configure.scan。

configure.scan就是configure.in的模板,对它做一些修改,然后改名为configure.in或者configure.ac就可以了(新版本的automake好像是configure.ac)。
configure.in:

AC_INIT(src/openfetion.cpp)
AM_INIT_AUTOMAKE(openfetion,0.1)
AM_CONFIG_HEADER(config.h)
AM_PATH_GTK_2_0(,,AC_MSG_ERROR(openfetion 0.1 needs GTK+ 2.0))
AM_PATH_XML2(,,AC_MSG_ERROR(openfetion 0.1 needs LIBXML2))
AC_PROG_CC
AC_PROG_CXX
AC_PROG_INSTALL
AC_OUTPUT(src/Makefile)
AC_INIT宏以任何一个源文件作为参数,它只是检查这个源文件的存在,也说意味着着源文件所在的目录存在
AM_INIT_AUTOMAKE 增加了几个标准的检查,它以程序名称和版本号作为参数
AC_PROG_CC 指出源代码可能是用C写的,如果源代码是用C++写的我们就需要AC_PROP_CXX
AC_PROG_INSTALL 会生成一个install目录文件,这样用户就可以通过输入“make install”来安装这个软件
AC_OUTPUT 指出将会生成的Makefile文件的名字
AC_CONFIG_HEADER 表示将会使用config.h文件,autoconf需要一个config.h.in文件,用它来生成config.h,config.h.in可以通过autoheader工具生成
AM_PATH_GTK_2_0(,,AC_MSG_ERROR(openfetion 0.1 needs GTK+ 2.0))
AM_PATH_XML2(,,AC_MSG_ERROR(openfetion 0.1 needs LIBXML2)) 这两句话检查系统中是否安装了程序所需要共享库, GTK+2.0和libxml2,这两个库在安装的时候分别安装了AM_PATH_GTK_2_0和 AM_PATH_XML2这两个宏,所以可以用这种方法检测,如果系统中没有安装libxml2,configure脚本就会执行失败,并报错:openfetion 0.1 needs LIBXML2
关于library的检查可参见文章:Using C/C++ libraries with Automake and Autoconf

其它的就不详细说了,需要的时候可以谷歌。
2.在顶层目录中创建一个Makefile.am,在其它各级需要的子目录中也创建Makefile.am。

我的顶层目录Makefile.am中只有下面几句话:

1
2
3
4
5
6
7
8
9
10
#子目录变量,用于递归处理各级子目录
SUBDIRS=src
#安装路径,可使用./configure --prefix=/usr/local/openfetion修改
prefix=/usr/local
#数据文件的安装路径
datadir=$(prefix)/skin
#数据文件的具体内容,这里的意思是要将skin目录下的所有文件安装到/usr/local/skin中
data_DATA=skin/* 
#程序打包时要加入的其它文件,使用make dist生成tar.gz文件时会放进去的东西
EXTRA_DIST=skin

src目录下的Makefile.am文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#libxml2 , GTK+2.0和GThread-2.0的cflags和libs
#libxml2安装了xml2-config脚本,GTK+2.0和GThread-2.0安装了.pc pkg-config文件
AM_CPPFLAGS=`xml2-config --cflags` `pkg-config --cflags gtk+-2.0 gthread-2.0`
AM_LDFLAGS=`xml2-config --libs` `pkg-config --libs gtk+-2.0 gthread-2.0`
#预定义的目录,prefix已经说过了
prefix=/usr/local
#这个是可执行文件安装的目录
bindir=$(prefix)/bin
#这个是自定义的目录,用来安装包含协议实现部分的静态库的
slibdir=/usr/lib
#编译生成可执行文件名称
bin_PROGRAMS=openfetion
#这里必须以上一步定义的名称为前缀,编译openfetion所需要的源文件
openfetion_SOURCES=openfetion.cpp  fetion_ui.cpp  ... login_ui.cpp
#编译openfetion所需要的库文件,libfx.a是我事先编译好了的。
openfetion_LDADD=libfx.a
#这个变量前面也说了,要把下面这些文件打包放到tar.gz中
EXTRA_DIST= 	   fetion_ui.h  main_ui.h  .... libfx.a
#要安装的头文件,执行完make install后,这些文件将被安装到/usr/include里面
include_HEADERS=   fgroup.h   flogin.h ... common.h
#自定义目录的数据文件,执行完make install后,这个文件就会被安装到/usr/lib里面
slib_DATA=libfx.a
3.生成GNU风格的项目时需要在顶层目录中你创建NEWS、 README、 ChangeLog 、AUTHOR这几个文件。
touch NEWS README ChangeLog AUTHOR
如果不需要生成GNU风格的项目就不需要创建这几个文件,而是需要在Makefile.am中加入
AUTOMAKE_OPTIONS = foreign
这是执行automake命令时的选项
4.执行aclocal。
由configure.in生成aclocal.m4
5.执行autoconf
由configure.in和aclocal.m4生成configure脚本
6.执行automake
由Makefile.am和configure.in生成各级目录下的Makefile.in
./configure执行的时候会扫描各个目录下的Makefile.in生成不同的Makefile。然后就可以执行make和make install了

GNU Automake工具集的功能远不止这些,我了解地也不够深刻,继续学习。

分类: Linux 标签: , , ,