The new hlist api for linux kernel

Time: 七月 26, 2013
Category: Kernel

今天在写list的时候参考了linux kernel的list实现,发现内核hlist的实现还有一个可以改进的地方,当前linux版本为 redhat 2.6.32-358.14.1.el6.x86_64
关键是这两个API,list_for_each_entry和hlist_for_each_entry

/**
 * list_for_each_entry	-	iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     &pos->member != (head); 	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * hlist_for_each_entry	- iterate over list of given type
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(tpos, pos, head, member)			 \
	for (pos = (head)->first;					 \
	     pos &&							 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

hlist比普通的list多了一个tpos,这是为什么。主要是因为hlist_for_each_entry()函数for循环里的条件判断,仅仅靠一个变量是很难完成的,为什么list_for_each_entry()就可以呢?

  1. list是一个双向列表,所有对象通过 struct list_head { struct list_head *next; struct list_head *prev}; 衔接在一起,链表头在初始化的时候,next域和prev域均是指向自身,也就是说,next域不可能为NULL,在list_for_each_entry宏里,&pos->member总能得到一个合法的地址,所以list的实现里可以很简单的 &pos->member != (head); 作为判断条件,而不会引起segmenfaul
  2. 但是hlist就不同了,hlist_node的next域和hlist_head的first域是可以为NULL的

现在假设一下hlist像list这么实现时会有什么问题,如下:

#define hlist_for_each_entry(pos, head, member)				\
	for (pos = hlist_entry((head)->first, typeof(*pos), member);	\
	     &pos->member != ???; 	\
	     pos = hlist_entry(pos->member.next, typeof(*pos), member))

这里的条件判断还真不好写,因为当first为NULL或者当前某个pos->member.next为NULL的时候,计算出来的pos是个负值,我们首先还要判断first/next域是否为NULL,再做处理。正是多了这个判断条件,仅仅一个pos似乎不够了,所以就引入了多一个成员,tpos,而pos的类型变成了hlist_node

但是hlist_for_each_entry宏还是可以改进的,我今天突然想出了一个办法,不需要tpos,仅仅一个pos就足够了,和list的接口一样。

细看hlist的实现,pos的目的,最主要的还是在条件判断的时候起作用,但是这个工作我们可以巧妙的让tpos来完成,通过强制类型转换。因为tpos和pos都是指针,而指针本质上在编译的时候是没有任何区别的,仅仅当访问结构体变量的时候通过查询其类型来计算偏移量,我的实现是:

//
// hlist_for_each_entry	- iterate over list of given type
// @param pos	the &struct hlist_node to use as a loop counter.
// @param head	the head for your list.
// @param type
// @param member        the name of the hlist_node within the struct.

#define hlist_for_each_entry(pos, head, member)  \
	for (pos = (typeof(pos)) (head)->first; pos && \
		     ({pos = hlist_entry((struct hlist_node *)pos, typeof(*pos), member); 1;}); \
	     pos = (type *)pos->member.next)

我临时借pos来保存hlist_node指针,判断是否为NULL,如果否,再将其转换为原本的类型。

upstream的内核已经有这个了,但是做法不一样,实现更加优雅一点,主要是利用c99里的新特性,如下:

#define hlist_entry_safe(ptr, type, member) \
	({ typeof(ptr) ____ptr = (ptr); \
	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
	})

/**
 * hlist_for_each_entry	- iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(pos, head, member)				\
	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
	     pos;							\
	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))

Leave a Comment