免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1198 | 回复: 0
打印 上一主题 下一主题

内核双向循环链表之旅 [复制链接]

论坛徽章:
0
跳转到指定楼层
1 [收藏(0)] [报告]
发表于 2009-10-28 09:45 |只看该作者 |倒序浏览

                                为了完成对内核双向循环链表的彻底掌握,我搜索了一些重要信息。可是到最后还是被内核的代码给卡住了。我的过程如下:
首先在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
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP