谈谈Linux kernel的list结构

编程
目录

最近在解决关于关于cfg80211.ko的问题，需要阅读net/wireless目录下的代码，看到如下代码感觉有点懵逼：
include/net/regulatory.h 

1
2
3
4
5
6
7
8
9
10
11
12
struct regulatory_request {
	struct rcu_head rcu_head;
	int wiphy_idx;
	enum nl80211_reg_initiator initiator;
	enum nl80211_user_reg_hint_type user_reg_hint_type;
	char alpha2[2];
	enum nl80211_dfs_regions dfs_region;
	bool intersect;
	bool processed;
	enum environment_cap country_ie_env;
	struct list_head list;
};

net/wireless/reg.c 

1
2
3
4
5
6
7
8
9
10
11
12
13
static LIST_HEAD(reg_requests_list);
...
static void queue_regulatory_request(struct regulatory_request *request)
{
	request->alpha2[0] = toupper(request->alpha2[0]);
	request->alpha2[1] = toupper(request->alpha2[1]);
	spin_lock(&reg_requests_lock);
	list_add_tail(&request->list, &reg_requests_list);
	spin_unlock(&reg_requests_lock);
	schedule_work(&reg_work);
}

list_add_tail(&request->list, &reg_requests_list); 这行代码把request->list成员的地址(而不是request结构的地址)加到以reg_list_list为head节点的链表中，那么后面怎么访问除了list外的其他成员呢？且看下文分解：
net/wireless/reg.c 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static void reg_process_pending_hints(void)
{
	struct regulatory_request *reg_request, *lr;
	lr = get_last_request();
	/* When last_request->processed becomes true this will be rescheduled */
	if (lr && !lr->processed) {
		reg_process_hint(lr);
		return;
	}
	spin_lock(&reg_requests_lock);
	if (list_empty(&reg_requests_list)) {
		spin_unlock(&reg_requests_lock);
		return;
	
	reg_request = list_first_entry(&reg_requests_list,
				       struct regulatory_request,
				       list);
	list_del_init(&reg_request->list);
	spin_unlock(&reg_requests_lock);
	reg_process_hint(reg_request);
}

list_first_entry方法用于访问reg_requests_list为head的链表的首元素，继续跟踪下其实现，如下(以下代码片段位于include/linux/list.h)： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)
/**
 * list_first_entry - get the first element from a list
 * @ptr:	the list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

接近真相了，奥秘就在container_of这个方法中:
include/stddef.h 

1
2
3
4
5
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

include/kernel.h 

1
2
3
4
5
6
7
8
9
10
/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:	the pointer to the member.
 * @type:	the type of the container struct this is embedded in.
 * @member:	the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	
	(type *)( (char *)__mptr - offsetof(type,member) );})

结合一下，就是 

1
2
#define container_of(ptr, type, member) \
    (type *)((char *)(ptr) - (char *) &((type *)0)->member)

看到这句代码(char ) &((type )0)->member), 还能这样玩，顿时感觉c的指针确实能做很多事，像magic一样，研究了下，这句代码是用于获取type结构的member成员的相对首地址的偏移。
所以kernel中list使用原理：获取结构中list成员的地址，然后－list成员在结构中的相对偏移，从而得到type结构的地址，很巧妙。

下面是我的一段测试代码，不明白的话可以再自己研究下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Returns a pointer to the container of this list element.
 *
 * Example:
 * struct foo* f;
 * f = container_of(&foo->entry, struct foo, entry);
 * assert(f == foo);
 *
 * @param ptr Pointer to the struct list_head.
 * @param type Data type of the list element.
 * @param member Member name of the struct list_head field in the list element.
 * @return A pointer to the data struct containing the list head.
 */
#include <stdio.h>
#ifndef container_of
#define container_of(ptr, type, member) \
    (type *)((char *)(ptr) - (char *) &((type *)0)->member)
#endif
struct entry{
    int a;    
};
struct foo{
    int data;
    int key;
    struct entry list;
};
int  main()
{
    struct foo f;
    struct foo *ptr;
    ptr = container_of(&(f.list), struct foo, list);
    printf("ptr address of foo:  %p \n", (char *)&f);
    printf("ptr address of foo list :  %p \n",(char *) &(f.list));
    printf("ptr address of 0->member: %p \n", (char *)&((struct foo*)0)->list);
    if (ptr == &f)
    {
        printf("return ok\n");
        return 0;
    }
    return -1;
}

编译运行后，输出： 

1
2
3
4
ptr address of foo:  0x7fff587c1af0 
ptr address of foo list :  0x7fff587c1af8 
ptr address of 0->member: 0x8 
return ok
本站总访问量次