存档

‘Kernel’ 分类的存档

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

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

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

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,444 人阅读过  

链表是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 标签:

浅析linux kernel network之socket创建

二月 20th, {2011 6 条评论 12,954 人阅读过  

去年受@colyli指点,决定花些时间读一些linux kernel network部分的代码,准备把阅读代码的过程记录下来,也希望能有大牛前来指点,下面就先写一下创建socket对象的过程:

首先,创建socket需要执行socket系统调用:

int socket(int domain, int type, int protocol);

该系统调用有3个参数,在内核中由SYSCALL_DEFINE3定义,具体代码如下:

SYSCALL_DEFINE3(socket, int, family, int, type, int, protocol)
{
	int retval;
	struct socket *sock;
	int flags;
 
	flags = type & ~SOCK_TYPE_MASK;
	if (flags & ~(SOCK_CLOEXEC | SOCK_NONBLOCK))
		return -EINVAL;
	type &= SOCK_TYPE_MASK;
 
	if (SOCK_NONBLOCK != O_NONBLOCK && (flags & SOCK_NONBLOCK))
		flags = (flags & ~SOCK_NONBLOCK) | O_NONBLOCK;
 
	retval = sock_create(family, type, protocol, &sock);
	if (retval < 0)
		goto out;
 
	retval = sock_map_fd(sock, flags & (O_CLOEXEC | O_NONBLOCK));
	if (retval < 0)
		goto out_release;
 
out:
	/* It may be already another descriptor 8) Not kernel problem. */
	return retval;
 
out_release:
	sock_release(sock);
	return retval;
}

上述代码中首先做了一个类型检查,type即我们所熟知的SOCK_STREAM,SOCK_DGRAM等sock_type枚举,其取值范围为1-10,均位于type字段的低八位,而SOCK_CLOEXEC 和SOCK_NONBLOCK为于高位,SOCK_TYPE_MASK宏的值为0xF,该检查的作用是检查除了基本的socket类型和SOCK_CLOEXEC和SOCK_NONBLOCK选项之外是否设置了其它选项,如果有,则返回INVLAID。

之后的检查我理解为是一个兼容性检查,如果设置了SOCK_NONBLOCK选项,则不管SOCK_NONBLOCK的值是否定义为与O_NONBLOCK相同,均将socket的O_NONBLOCK位置位,而将SOCK_NONBLOCK位复位。

随便调用sock_create创建一个新的socket对象,之后再调用sock_map_fd将该socket对象影射为文件描述符retval,随即将其返回,从而函数得到一个socket描述符。sock_create函数直接调用了__sock_create函数来创建socket对象,具体看__sock_create函数的实现:

int __sock_create(struct net *net, int family, int type, int protocol,
			 struct socket **res, int kern)
{
	int err;
	struct socket *sock;
	const struct net_proto_family *pf;
 
	if (family < 0 || family >= NPROTO)
		return -EAFNOSUPPORT;
	if (type < 0 || type >= SOCK_MAX)
		return -EINVAL;
 
	if (family == PF_INET && type == SOCK_PACKET) {
		static int warned;
		if (!warned) {
			warned = 1;
			printk(KERN_INFO "%s uses obsolete (PF_INET,SOCK_PACKET)\n",
			       current->comm);
		}
		family = PF_PACKET;
	}
 
	err = security_socket_create(family, type, protocol, kern);
	if (err)
		return err;
 
	sock = sock_alloc();
	if (!sock) {
		if (net_ratelimit())
			printk(KERN_WARNING "socket: no more sockets\n");
		return -ENFILE;	/* Not exactly a match, but its the
				   closest posix thing */
	}
 
	sock->type = type;
 
#ifdef CONFIG_MODULES
	if (net_families[family] == NULL)
		request_module("net-pf-%d", family);
#endif
 
	rcu_read_lock();
	pf = rcu_dereference(net_families[family]);
	err = -EAFNOSUPPORT;
	if (!pf)
		goto out_release;
 
	/*
	 * We will call the ->create function, that possibly is in a loadable
	 * module, so we have to bump that loadable module refcnt first.
	 */
	if (!try_module_get(pf->owner))
		goto out_release;
 
	/* Now protected by module ref count */
	rcu_read_unlock();
 
	err = pf->create(net, sock, protocol, kern);
	if (err < 0)
		goto out_module_put;
 
	/*
	 * Now to bump the refcnt of the [loadable] module that owns this
	 * socket at sock_release time we decrement its refcnt.
	 */
	if (!try_module_get(sock->ops->owner))
		goto out_module_busy;
 
	/*
	 * Now that we're done with the ->create function, the [loadable]
	 * module can have its refcnt decremented
	 */
	module_put(pf->owner);
	err = security_socket_post_create(sock, family, type, protocol, kern);
	if (err)
		goto out_sock_release;
	*res = sock;
 
	return 0;
 
out_module_busy:
	err = -EAFNOSUPPORT;
out_module_put:
	sock->ops = NULL;
	module_put(pf->owner);
out_sock_release:
	sock_release(sock);
	return err;
 
out_release:
	rcu_read_unlock();
	goto out_sock_release;
}

开始先进行安全性检查和兼容性检查,security_socket_create()是个空函数,可以忽略。之后调用sock_alloc()函数在VFS上分配一个struct socket对象,所有的协议类型创建socket时创建的均为这个对象,可以理解为是所有网络层socket的模板或者说父类,上层协议栈在初始化socket时会根据这个已创建好的struct socket对象创建并初始化一个struct sock对象,这个对象包含更多上层协议栈的详细信息。

接下来的net_families数据是一个全局变量,在系统初始化时在inet_init()函数内进行初始化,其定义如下:

static const struct net_proto_family *net_families[NPROTO] __read_mostly;

每个协议族都会在该数据中对应一个net_proto_family结构体,当然,未实现的协议族中对应位置的结构体指针为空,我们只关心最常用的协议族即AF_INET,其值为2,而NPROTO的值等于AF_MAX,在2.6.37内核中值为38。刚才提到该数组在inet_init()中被初始化,查看该函数相关代码可知它调用sock_register()函数注册INET协议族,代码如下:

(void)sock_register(&inet_family_ops);

其中inet_family_ops是一个全局静态变量,其定义如下:

static const struct net_proto_family inet_family_ops = {
	.family = PF_INET,
	.create = inet_create, /* 该函数在我们创建socket的过程中起着很关键的作用 */
	.owner	= THIS_MODULE,
};

再继续查看sock_register()函数,其代码如下:

int sock_register(const struct net_proto_family *ops)
{
	int err;
 
	if (ops->family >= NPROTO) {
		printk(KERN_CRIT "protocol %d >= NPROTO(%d)\n", ops->family,
		       NPROTO);
		return -ENOBUFS;
	}
 
	spin_lock(&net_family_lock);
	if (net_families[ops->family])
		err = -EEXIST;
	else {
		net_families[ops->family] = ops;
		err = 0;
	}
	spin_unlock(&net_family_lock);
 
	printk(KERN_INFO "NET: Registered protocol family %d\n", ops->family);
	return err;
}

代码很简单,即将net_proto_family对象插入到net_families数据对应的位置中,由此来完成对net_families的初始化。

OK,继续返回刚才的__sock_create()函数,看下面的代码:

#ifdef CONFIG_MODULES
	if (net_families[family] == NULL)
		request_module("net-pf-%d", family);
#endif

如果编译时支持可安装模块,则首先检测net_families数组中对应的family是否存在,假设此处为AF_INET,如果不存在,即在系统初始化时没有通过sock_register()函数对该元素进行注册,则调用request_module()动态地安装模块net-pf-2。

再往下通过RCU机制获取net_families中对应的net_proto_family对象,RCU机制主要用于网络层和VFS中,关于RCU机制的更多细节可以参考@gnawux师兄的译文:What is RCU, Fundamentally?

之后由注释可知增加该模块的引用计数,重要的函数为pf->create(),当协议族为AF_INET时,由以上可知,create函数为inet_create(),由这个函数进一步创建该socket,我们再看inet_create()函数的实现:

static int inet_create(struct net *net, struct socket *sock, int protocol,
		       int kern)
{
	struct sock *sk;
	struct inet_protosw *answer;
	struct inet_sock *inet;
	struct proto *answer_prot;
	unsigned char answer_flags;
	char answer_no_check;
	int try_loading_module = 0;
	int err;
 
        /* 检查是否有加密字符串,如果没有则查检socket类型,
           只有TCP需要加密字符串,如果协议类型不是SOCK_RAW和SOCK_DGRAM的话,
            调用build_ehash_secret()函数创建一个加密字符串 */
	if (unlikely(!inet_ehash_secret))
		if (sock->type != SOCK_RAW && sock->type != SOCK_DGRAM)
			build_ehash_secret();
 
        /* 将socket状态设置为未连接 */
	sock->state = SS_UNCONNECTED;
 
	/* Look for the requested type/protocol pair. */
lookup_protocol:
	err = -ESOCKTNOSUPPORT;
	rcu_read_lock();
 
        /* 遍历inetsw数组对应请求类型的链表元素,
           如果protocol不是通配符类型,即IPPROTO_IP,
           该宏的值为0,则在链表中搜索该协议类型,
           如未找到则返回协议类型不支持,如果是通配符类型,
           则选择一个适合的协议类型,至于inetsw数组,见下面分析 */
	list_for_each_entry_rcu(answer, &inetsw[sock->type], list) {
 
		err = 0;
		/* Check the non-wild match. */
		if (protocol == answer->protocol) {
			if (protocol != IPPROTO_IP)
				break;
		} else {
			/* Check for the two wild cases. */
			if (IPPROTO_IP == protocol) {
				protocol = answer->protocol;
				break;
			}
			if (IPPROTO_IP == answer->protocol)
				break;
		}
		err = -EPROTONOSUPPORT;
	}
        /* 动态加载相关协议模块 */
	if (unlikely(err)) {
		if (try_loading_module < 2) {
			rcu_read_unlock();
			/*
			 * Be more specific, e.g. net-pf-2-proto-132-type-1
			 * (net-pf-PF_INET-proto-IPPROTO_SCTP-type-SOCK_STREAM)
			 */
			if (++try_loading_module == 1)
				request_module("net-pf-%d-proto-%d-type-%d",
					       PF_INET, protocol, sock->type);
			/*
			 * Fall back to generic, e.g. net-pf-2-proto-132
			 * (net-pf-PF_INET-proto-IPPROTO_SCTP)
			 */
			else
				request_module("net-pf-%d-proto-%d",
					       PF_INET, protocol);
			goto lookup_protocol;
		} else
			goto out_rcu_unlock;
	}
 
	err = -EPERM;
        /* 众所周知,只有root权限用户才可以创始原始套接字,
           此处检查是否有权限创建SOCK_RAW类型的套接字,
           如果无权限,则返回-EPERM */
	if (sock->type == SOCK_RAW && !kern && !capable(CAP_NET_RAW))
		goto out_rcu_unlock; 
	err = -EAFNOSUPPORT;
       /* 检查协议类型是否支持 */
	if (!inet_netns_ok(net, protocol))
		goto out_rcu_unlock;
 
	sock->ops = answer->ops;
	answer_prot = answer->prot;
	answer_no_check = answer->no_check;
	answer_flags = answer->flags;
	rcu_read_unlock();
 
	WARN_ON(answer_prot->slab == NULL);
 
	err = -ENOBUFS;
	sk = sk_alloc(net, PF_INET, GFP_KERNEL, answer_prot);
	if (sk == NULL)
		goto out;
 
	err = 0;
	sk->sk_no_check = answer_no_check;
	if (INET_PROTOSW_REUSE & answer_flags)
		sk->sk_reuse = 1;
 
	inet = inet_sk(sk);
        /* 是否是基于连接的socket,目前只有SOCK_STREAM是基于连接的socket */
	inet->is_icsk = (INET_PROTOSW_ICSK & answer_flags) != 0;
 
	inet->nodefrag = 0;
 
	if (SOCK_RAW == sock->type) {
		inet->inet_num = protocol;
                /* 如果是原始套接字,则需要创建IP头部 */
		if (IPPROTO_RAW == protocol)
			inet->hdrincl = 1;
	}
 
        /* 是否启用路径MTU发现机制,可以在修改proc文件开启或关闭:
           /proc/sys/net/ipv4/ip_no_pmtu_disc */
	if (ipv4_config.no_pmtu_disc)
		inet->pmtudisc = IP_PMTUDISC_DONT;
	else
		inet->pmtudisc = IP_PMTUDISC_WANT;
 
	inet->inet_id = 0;
 
        /* 该函数利用sock的内容进一步初始化sk */
	sock_init_data(sock, sk);
 
	sk->sk_destruct	   = inet_sock_destruct;
	sk->sk_protocol	   = protocol;
	sk->sk_backlog_rcv = sk->sk_prot->backlog_rcv;
 
	inet->uc_ttl	= -1;
	inet->mc_loop	= 1;
	inet->mc_ttl	= 1;
	inet->mc_all	= 1;
	inet->mc_index	= 0;
	inet->mc_list	= NULL;
 
	sk_refcnt_debug_inc(sk);
 
	if (inet->inet_num) {
		/* It assumes that any protocol which allows
		 * the user to assign a number at socket
		 * creation time automatically
		 * shares.
		 */
		inet->inet_sport = htons(inet->inet_num);
		/* Add to protocol hash chains. */
		sk->sk_prot->hash(sk);
	}
 
	if (sk->sk_prot->init) {
		err = sk->sk_prot->init(sk);
		if (err)
			sk_common_release(sk);
	}
out:
	return err;
out_rcu_unlock:
	rcu_read_unlock();
	goto out;
}

说一下inetsw这个数组,它也是针对于AF_INET协议族而言的,是一个全局静态变量,包含着创建一个新的socket所需要的所有信息,定义如下:

static struct list_head inetsw[SOCK_MAX];

其中每个元素都是一个双向链表,该数据的定义也是在inet_init()函数中完成的,看其中相关代码:

for (r = &inetsw[0]; r < &inetsw[SOCK_MAX]; ++r)
	INIT_LIST_HEAD(r);
for (q = inetsw_array; q < &inetsw_array[INETSW_ARRAY_LEN]; ++q)
	inet_register_protosw(q);

首先初始化每个链表元素的头,接下来将inetsw_array这个数组中的元素使用inet_register_protosw()函数注册到inetsw数组中,inetsw_array也是一个全局的静态变量,其定义如下:

static struct inet_protosw inetsw_array[] =
{
	{
		.type =       SOCK_STREAM,
		.protocol =   IPPROTO_TCP,
		.prot =       &tcp_prot,
		.ops =        &inet_stream_ops,
		.no_check =   0,
		.flags =      INET_PROTOSW_PERMANENT |
			      INET_PROTOSW_ICSK,
	},
 
	{
		.type =       SOCK_DGRAM,
		.protocol =   IPPROTO_UDP,
		.prot =       &udp_prot,
		.ops =        &inet_dgram_ops,
		.no_check =   UDP_CSUM_DEFAULT,
		.flags =      INET_PROTOSW_PERMANENT,
       },
 
 
       {
	       .type =       SOCK_RAW,
	       .protocol =   IPPROTO_IP,	/* wild card */
	       .prot =       &raw_prot,
	       .ops =        &inet_sockraw_ops,
	       .no_check =   UDP_CSUM_DEFAULT,
	       .flags =      INET_PROTOSW_REUSE,
       }
};

它包含了各种协议类型所需要的基本信息。

接下来很重要的一步,就是调用sk_alloc()函数创建一个新的struct sock对象,struct socket和struct sock的区别在于,struct socket是创建每个BSD所必须的,它描述BSD socket的一些基本信息,而struct sock则描述网络层的相关信息,它在struct socket的基础上构建。看一下sk_sock()的定义:

struct sock *sk_alloc(struct net *net, int family, gfp_t priority,
		      struct proto *prot)
{
	struct sock *sk;
 
	sk = sk_prot_alloc(prot, priority | __GFP_ZERO, family);
	if (sk) {
		sk->sk_family = family;
		/*
		 * See comment in struct sock definition to understand
		 * why we need sk_prot_creator -acme
		 */
		sk->sk_prot = sk->sk_prot_creator = prot;
		sock_lock_init(sk);
		sock_net_set(sk, get_net(net));
		atomic_set(&sk->sk_wmem_alloc, 1);
 
		sock_update_classid(sk);
	}
 
	return sk;
}

最后一个参数为当前协议类型对应的struct proto对象,将刚创建的struct sock对象的sk_prot和sk_prot_creator成员初始化为prot。sk_prot_alloc()函数用于创建sock对象,可以在slab分配器上创建,也可以在普通缓存中创建。

接下来贝sock_init_data()函数进一步初始化sk:

void sock_init_data(struct socket *sock, struct sock *sk)
{
        /* 初始化接收/发送/异常缓冲队列,这些队列均为双向链表,
           节点数据内容为struct sk_buff对象, 各种数据包的信息都
           存放在该结构体中。队列sk_error_queue很少使用 */
	skb_queue_head_init(&sk->sk_receive_queue);
	skb_queue_head_init(&sk->sk_write_queue);
	skb_queue_head_init(&sk->sk_error_queue);
#ifdef CONFIG_NET_DMA
	skb_queue_head_init(&sk->sk_async_wait_queue);
#endif
 
	sk->sk_send_head	=	NULL;
 
	init_timer(&sk->sk_timer);
 
	sk->sk_allocation	=	GFP_KERNEL;
        /* 接收缓冲区最大字节数 */
	sk->sk_rcvbuf		=	sysctl_rmem_default;
        /* 发送缓冲区最大字节数 */
	sk->sk_sndbuf		=	sysctl_wmem_default;
        /* 连接状态,SOCK_DGRAM和SOCK_RAW也会共用TCP的一些状态,
         连接刚建立的时候都会使用TCP_CLOSE状态 */
	sk->sk_state		=	TCP_CLOSE;
	sk_set_socket(sk, sock);
 
	sock_set_flag(sk, SOCK_ZAPPED);
 
	if (sock) {
		sk->sk_type	=	sock->type;
		sk->sk_wq	=	sock->wq;
		sock->sk	=	sk;
	} else
		sk->sk_wq	=	NULL;
 
	spin_lock_init(&sk->sk_dst_lock);
	rwlock_init(&sk->sk_callback_lock);
	lockdep_set_class_and_name(&sk->sk_callback_lock,
			af_callback_keys + sk->sk_family,
			af_family_clock_key_strings[sk->sk_family]);
 
	sk->sk_state_change	=	sock_def_wakeup;
	sk->sk_data_ready	=	sock_def_readable;
	sk->sk_write_space	=	sock_def_write_space;
	sk->sk_error_report	=	sock_def_error_report;
	sk->sk_destruct		=	sock_def_destruct;
 
	sk->sk_sndmsg_page	=	NULL;
	sk->sk_sndmsg_off	=	0;
 
	sk->sk_peer_pid 	=	NULL;
	sk->sk_peer_cred	=	NULL;
	sk->sk_write_pending	=	0;
	sk->sk_rcvlowat		=	1;
	sk->sk_rcvtimeo		=	MAX_SCHEDULE_TIMEOUT;
	sk->sk_sndtimeo		=	MAX_SCHEDULE_TIMEOUT;
 
	sk->sk_stamp = ktime_set(-1L, 0);
 
	/*
	 * Before updating sk_refcnt, we must commit prior changes to memory
	 * (Documentation/RCU/rculist_nulls.txt for details)
	 */
	smp_wmb();
	atomic_set(&sk->sk_refcnt, 1);
	atomic_set(&sk->sk_drops, 0);
}

在inet_create()函数的最后还有一个很重要的初始化,下面这段代码:

if (sk->sk_prot->init) {
	err = sk->sk_prot->init(sk);
	if (err)
		sk_common_release(sk);
}

前面在sk_alloc()函数中为sk初始化时将协议类型对应的proto对象指针赋给了sk->sk_prot,这里的init()函数即对应的proto中的init函数,当协议类型为SOCK_STREAM时,prot即为tcp_proto(见inetsw_array), 对应的init()函数即为:

static int tcp_v4_init_sock(struct sock *sk)

分类: Kernel 标签: