list_head使用介绍

list_head结构的介绍
list_head结构定义在 里，它是一个double linked list的结构。 底下是它的结构宣告:

struct list_head { struct list_head *next, *prev; };

有的人可能看到这样的结构会觉得很奇怪这样的结构可以存放资料吗? 当然是不行的棉，因为这个结构根本是拿来让人当资料存的。 首先， 我们先来看看两个macro，

#define LIST_HEAD(name) \ struct list_head name = { &name, &name } #define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0)

这两个macro在Kernel里也算蛮常出现的， 是用来将list_head做初始化的，它的初始化就是将next和prev这两个栏位设为跟结构的地址相同。 所以， 如果我们在程序里看到这样的程序， 它的意思就是宣告一个list_head结构的变数hello，并将prev和next都设成hello的地址。

LIST_HEAD(hello)

因此， 如果要检查这个list是否是空的， 只要检查hello.next是否等于&hello就可以了。事实上， Linux也提供了一个叫list_empty()的函式来检查list是否为空的。

static __inline__ int list_empty(struct list_head *head) { return head->next == head; }

现在我们来介绍如何加入或删除list_head到上面的hello串行里。 Linux提供二个函式来做这些事， 分别是list_add()和lis_del()。 这两个函式的定义都放在 里， 而且其程序码也都很简单，只是单纯double linked list的串接和删除而已， 因此我们不对它们做介绍。 有关于这个结构， 其实最重要的应该是它提供的这个macro。

#define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

我们现在来做个实验， 相信各位会更容易了解这个macro的。 请看一下下面这段程序码。

struct HelloWorld {    int x, y;    struct list_head list; } hello;

假设int是4个byte。 那么以下这一行会得到8， 如图5所示

(unsigned long) (&((struct HelloWorld *)0)->list)

有的人会对这一行程序感到奇怪， (struct HelloWorld*)0不就是一个NULL的指标吗? 怎么可以用0->list去参考list这个栏位呢? 难道不怕造成segmentation fault吗? 请注意一下， 我们在0->list的前面还加上了一个&。 如果没有&， 那上面这一行就会segmentation fault了。 如果你加上了&， 那就没问题棉。 Segmentation fault通常是去参考到不合法的记忆体地址内容所造成的， 如果我们加上了&就表示我们没有要去参考这个不合法地址的内容，我们只是要那个栏位的地址而已， 因此， 不会造成segmentation fault。 其实， 结构的配置在记忆体里是连续的。 所以， 如果我们去读取某个栏位时，像&hello->list。 会先取得hello变数的地址， 再然后再计算HelloWorld结构里list栏位所在的offset， 再将hello的地址加上list栏位的offset，求得list栏位真正的地址。 然后再去读list栏位的内容。 这是compiler帮我们做的。 那我们现在就来看看上面那一行究竟是什么意思。 首先， 我们先把上面那一行想象成下面这个样子。

ptr = 0; (unsigned long) (&((struct HelloWorld *)ptr)->list)

这样是不是容易懂了吗， 就是要取得&ptr->list的地址而已。所以， 如果ptr是100的话， 那会得到100+8=108。 因为前面有二个int， 每一个int是4个byte。 经过转型， 就得到了(unsigned long)型态的108。 如果ptr是0的话， 那同理， 我们会得到0+8=8。 也就是这个栏位在HelloWorld结构里的offset。

现在， 如果我们已经知道了list在HelloWorld结构中的offset，而且我们现在也知道hello这个变数里list的地址的话， 那有没有办法得到hello本身的地址呢? 可以的， 就像图6一样， 如果我们知道list的地址， 只要将list的地址减8就可以知道了hello的地址了嘛。

struct list_head *plist = &hello.list; printf( "&hello = %x\n", (char*)plist - (unsigned long) 8 ));

而这种方式就是list_head的用法， 它是专门用来当作别的结构的栏位，只要我们得到这个栏位的位置和包含这个栏位的结构是那一种， 我们可以很轻易的算出包含此栏位的结构地址， 图6就是super block在使用list_head所得到的结果。只要我们知道s_list的地址， 只要呼叫

list_entry( &sb1.s_list, struct super_block, s_list)

就可以得到其sb1这个super_block结构的地址。