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

-
 
 

Han 通过 Google 阅读器发送给您的内容：

 
 

于 11-3-15 通过 basic coder 作者：levin

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

评论

发表评论

此博客中的热门博文

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

-
    Han 通过 Google 阅读器发送给您的内容：     浅析Linux Kernel 哈希路由表实现(一) 于 11-3-13 通过 basic coder 作者：levin 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 ; /* 该路由中默认路由条目在哈希路由表中的索...
阅读全文

通过blktrace, debugfs分析磁盘IO

-
    Han 通过 Google 阅读器发送给您的内容：     通过blktrace, debugfs分析磁盘IO 于 12-11-14 通过 Linux Kernel and Tao 作者：admin 前几天微博上有同学问我磁盘util达到了100%时程序性能下降的问题，由于信息实在有限，我也没有办法帮太大的忙，这篇blog只是想给他列一下在磁盘util很高的时候如何通过blktrace+debugfs找到发生IO的文件，然后再结合自己的应用程序，分析出这些IO到底是谁产生的，最终目的当然是尽量减少不必要的IO干扰，提高程序的性能。 blktrace是Jens Axobe写的一个跟踪IO请求的工具，Linux系统发起的IO请求都可以通过blktrace捕获并分析，关于这个工具的介绍请自行google之，这里推荐我们部门的褚霸同学的 blog ，里面有好几篇文章分别介绍了blktrace, blkparse以及blkiomon等工具的使用。 debugfs是ext2, ext3, ext4文件系统提供的文件系统访问工具，通过它我们可以不通过mount文件系统而直接访问文件系统的内容，它是e2fsprogs的一部分，默认应该都是安装的，详细的说明可以通过man debugfs得到。 下面我来演示一下如何通过这两个工具的配合来找到磁盘IO的源头。 先看一个简单的例子： 在一个终端会输入如下命令： while [ 1 ];do dd if=/dev/zero of=test_file bs=4k count=20 seek=$RANDOM oflag=sync;done 随机的在test_file里面写数据造成较大的IO压力，现在看看如何通过blktrace和debugfs抓到它。 1. 通过iostat观察到有很大的磁盘压力 Device: rrqm/s wrqm/s r/s w/s rsec/s wsec/s avgrq-sz avgqu-sz await svctm %util sdb ...
阅读全文

ext4 bigalloc 答疑

-
    Han 通过 Google 阅读器发送给您的内容：     ext4 bigalloc 答疑 于 13-2-20 通过 斯巴达第二季 问题都来自 pamirs 的信，感谢他对bigalloc特性的关注。 问：文件分配的时候，ext4文件系统请求的时候是按照blocks来请求,但是ext4文件系统自己会按照cluster来分配（这个的理解是否正确呢？） 答：应该说，不太准确，事实上, ext4文件系统请求分配磁盘空间的时候也是按照cluster来请求的了，ext4_ext_map_blocks() 函数是用来检查文件的逻辑位置对应的物理块的，里面申请新磁盘空间的调用是：         ar.len = EXT4_NUM_B2C(sbi, offset+allocated);         ......         newblock = ext4_mb_new_blocks(handle, &ar, &err); ar.len的单位是cluster，所以实际上申请空间就是以cluster为单位 问：如果cluster为32K(8个blocks), 那么对于一个3k的文件来说,一次就分配了一个cluster,这样就有7个blocks不能在被其他文件使用了。group desc中的block_bitmap中将cluster对应的bit位置1，那么后续这个文件在增加的时候,是否按照增加的blocks数量,以及当前该文件占用的cluster,计算出已经占用的cluster中有多少blocks是空闲的,还可以继续分配呢? 答：是的，需要一些琐碎的计算，这些计算的代码都放在了函数get_implied_cluster_alloc()里 问：ext4_group_desc中的bg_free_blocks_count_lo字段表示当前group中有多少空闲的blocks,使用了bigalloc之后,该字段的意义并没有发生变化吧?好像没有看到有新增一个字段来表示free_clusters数量,这个是否不需要保存这样的变量?通过bitmap查询得知呢? 答：bg_free_blocks_coun...
阅读全文