内核双向循环链表之旅

lanlovehua

                                为了完成对内核双向循环链表的彻底掌握，我搜索了一些重要信息。可是到最后还是被内核的代码给卡住了。我的过程如下：
首先在linux-2.6.30.4/include/linux/list.h里找到内核的双向链表结构：
struct list_head {
    struct list_head *next, *prev;
};
它是一个只有指针域而没有数据域的结构，这样的好处就是灵活性很强！并且控制起来也很方便。但是有个小问题：
例如我使用了这样一个结构：
struct mylist{
    char data;
    struct list_head *list;
}*a;
而我们平时建立双向循环链表时会这样：
struct mylist{
    char data;
    struct mylist *next, *prev;
}*b;
这两者的区别在于：
当我们要选择下一个链表时：
b = b->next;
而a链表却不能这样。因为指针域的类型和struct mylist类型不一致。如果直接使用a->list = a->list->next的话只是改变了a->list域，而整体并没有移到下一个链表。其实要想移动整体，我们只要知道struct list_head和struct mylist之间的偏移量就可以了。然后使用已经移动的a->list域减去偏移量就是下一个链表的首地址了。为了看到内核对这一问题的解决办法，我又继续寻找。
很巧，在内核里有这样一个宏，它的功能是：对于给定的进程，获取链表的下一个进程：
list_entry(task->tasks.next, struct task_struct, tasks)
(其中：
struct task_struct *task;
struct list_head tasks;
)
这样看当然不知道它是如何实现的，于是就到内核找它的源代码：linux-2.6.30.4/include/linux/list.h：
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
接下来就是要寻找container_of(ptr, type, member)这个宏，在linux-2.6.30.4/include/linux/kernel.h:
#define container_of(ptr, type, member) ({            \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})
挺复杂的一个宏定义，让我们来慢慢分析吧：
const定义了一个只读变量*__mptr,它首先是一个指针。typeof()是取参数的数据类型。对于((type *)0->member),来看一下它的实质,我们把list_entry()的参数带入到这里：((struct task_struct *)0->tasks)它把struct task_struct的首地址虚拟为0x00000000,然后指向struct list_head结构.这样简化后就是：const struct list_head *__mptr = task->tasks.next;即为下一个链表的struct list_head域。
第二行我们首先要找到offsetof(type, member)宏。它在linux-2.6.30.4/include/linux/stddef.h:
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
#endif /* __KERNEL__ */
这里明显看到是执行#else,也就是((size_t) &((TYPE *)0)->MEMBER)
size_t的定义在linux-2.6.30.4/include/linux/types.h:
typedef __kernel_size_t        size_t;
而__kernel_size_t在linux-2.6.30.4/arch/x86/include/asm/posix_types_32.h:
typedef unsigned int    __kernel_size_t;
即size_t是unsigned int类型的。＆((TYPE *)0)->MEMBER)这里就是得到了MEMBER成员与TYPE首地址的偏移量。再将地址强制转换为unsigned int型。那么(type *)( (char *)__mptr - offsetof(type,member) );这句话意思就是：
(struct task_struct *)((char *)__mptr - 偏移量).这样一来就把struct task_struct这个结构整体移动到下一个链表了。
这样对于struct list_head的结构就可以完全使用了。
然而内核里也提供了遍历某个进程的所用子进程的宏：linux-2.6.30.4/include/linux/list.h：
#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)
我们可以这样使用它：
struct task_struct *task;
struct list_head *list;
list_for_each(list, &current->children){
    task = list_entry(list, struct task_struct, sibling);
    /*task现在指向当前的某个子进程*/
}
在内核里，children和sibling(兄弟)都是这样定义的：
struct list_head children;    /* list of my children */
struct list_head sibling;    /* linkage in my parent's children list */
而父进程是这样定义的：
struct task_struct *parent; /* recipient of SIGCHLD, wait4() reports */
或许这也是某种需求吧。这样的话父进程可以直接找到：struct task_struct *my_parent = current->parent;莫非还有玄机？请高手指点。
我又对list_for_each(pos, head)的prefetch()这个宏产生了兴趣，于是寻找之：
两个地方找到了这个perfetch():
linux-2.6.30.4/include/linux/perfetch.h:
#ifndef ARCH_HAS_PREFETCH
#define prefetch(x) __builtin_prefetch(x)
#endif
这里我又找__builtin_prefetch(x)这个宏，可是没有的。后来才知道这个__builtin_前缀叫做"编译器选项"。是在GCC内部的，内核里找不到。
这里还要请高手指点。
还有一个地方是X86的体系架构里：linux-2.6.30.4/arch/x86/include/asm/processor.h:
/*
* Prefetch instructions for Pentium III (+) and AMD Athlon (+)
*
* It's not worth to care about 3dnow prefetches for the K6
* because they are microcoded there and very slow.
*/
static inline void prefetch(const void *x)
{
    alternative_input(BASE_PREFETCH,
              "prefetchnta (%1)",
              X86_FEATURE_XMM,
              "r" (x));
}
这里就有些模糊了。不过我还是继续寻找alternative_input()这个东西：linux-2.6.30.4/arch/x86/include/asm/alternative.h:
#define alternative_input(oldinstr, newinstr, feature, input...)        \
114         asm volatile ("661:\n\t" oldinstr "\n662:\n"                    \
115                       ".section .altinstructions,\"a\"\n"               \
116                       _ASM_ALIGN "\n"                                   \
117                       _ASM_PTR "661b\n"         /* label */             \
118                       _ASM_PTR "663f\n"         /* new instruction */   \
119                       "  .byte %c0\n"           /* feature bit */       \
120                       "  .byte 662b-661b\n"     /* sourcelen */         \
121                       "  .byte 664f-663f\n"     /* replacementlen */    \
122                       ".previous\n"                                     \
123                       ".section .altinstr_replacement,\"ax\"\n"         \
124                       "663:\n\t" newinstr "\n664:\n"  /* replacement */ \
125                       ".previous" :: "i" (feature), ##input)
这次我彻底崩溃了。朋友说“你不能这样看内核。”内核里的庞大我彻底领教了。
希望所有学习Linux内核的朋友我们一起开辟这条道路，学习内核是一条漫长之路，如果大家有什么好的意见或建议都提出来阿！谢谢。
               
               
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/94212/showart_2080581.html