精华内容
下载资源
问答
  • linux管理进程链表

    2017-02-15 22:51:01
    linux管理进程链表  linux2.6.11的内核中,为了方便管理linux进程,主要建了5种linux链表。每个链表节点之间的互联有两种方式,一种是hash节点之间的互联,通过hlist_node的数据结构来实现;另一种...

    linux管理进程的链表

      linux2.6.11的内核中,为了方便管理linux的进程,主要建了5种linux链表。每个链表节点之间的互联有两种方式,一种是hash节点之间的互联,通过hlist_node的数据结构来实现;另一种就是list_head类型的数据结构来互联。看linux内核的人对这两种类型的数据结构肯定是不会陌生的,因为它们在linux内核中无处不在。

     

    1 进程直接的互连

      通过任务描述符结构task_struct结构中的tasks成员来实现各个节点之间的互连,它是list_head类型。这个链表是一个循环的双向链表,开始的时候只有init_task这一个进程,它是内核的第一个进程,它的初始化是通过静态分配内存,"手动"(其它的进程初始化都是通过动态分配内存初始化的)进行的,每新建一个进程,就通过SET_LINKS宏将该进程的task_struct结构加入到这条双向链表中,不过要注意的是如果一个进程新建一个线程(不包括主线程),也就是轻量级进程,它是不会加入该链表的。通过宏for_each_process可以从init_task开始遍历所有的进程。

     

    2 TASK_RUNNING状态的进程链表

      为了能让调度程序在固定的时间内选出”最佳“可运行的进程,与队列中可运行的进程数无关,建立了多个可运行进程链表,每个优先级对应一个,总共有140个。linux内核定义了一个prio_array_t类型的结构体来管理这140个链表。每个可运行的进程都在这140个链表中的一个,通过进程描述符结构中的run_list来实现,它也是一个list_head类型。enqueue_task是把进程描述符插入到某个可运行链表中,dequeue_task则从某个可运行链表中删除该进程描述符。TASK_RUNNING状态的prio_array_t类型的结构体是runqueue结构的arrays[1]成员。

     

    3 进程间的关系

      linux进程间的关系有两种,一种是父进程与子进程间的父子关系,一种是进程同属一个父进程的兄弟关系。linux中是通过进程描述符中的children和sibling来实现这种关系的,它们都是list_head类型的。children的next指向的是该进程最新的子进程,prev指向的是该该进程最老的子进程,sibling的next指向的是它父进程中比它更老的子进程,prev指向的是它父进程中比它更新的子进程。最新子进程的slibling.prev指向的是父进程,最老子进程的slibling.next也是指向父进程。这样通过children和sibling实现了一个循环的双向链表,该双向链表以父进程描述符为头节点。

    进程间亲属关系

     

    4 pidhash链表

      为了通过pid找到进程的描述符,如果直接遍历进程间互联的链表来查找进程id为pid的进程描述符显然是低效的,所以为了更为高效的查找,linux内核使用了4个hash散列表来加快查找,之所以使用4个散列表,是为了能根据不同的pid类型来查找进程描述符,它们分别是进程的pid,线程组领头进程的pid,进程组领头进程的pid,会话领头进程的pid。每个类型的散列表中是通过宏pid_hashfn(x)来进行散列值的计算的。每个进程都可能同时处于这是个散列表中,所以在进程描述符中有一个类型为pid结构的pids成员,通过它可以将进程加入散列表中,pid结构中包含解决散列冲突的pid_chain成员,它是hlist_node类型的,还有一个是将相同pid链起来的pid_list,它是list_head类型。

    pid散列表

     

    5 等待队列

      linux把等待同一个事件发生或资源的进程都链接在一起形成一个带头节点的双向链表。等待队列的头是用类型wait_queue_head_t描述,里面包含了list_head类型的task_list成员。等待队列中节点的类型用wait_queue_t描述,该结构里有task_struct类型的指针task和list_head类型的task_list成员。为什么不像前面4个队列中一样,将list_head类型的task_list成员放到进程的描述符里来形成链表呢?原因是linux等待队列太多了,每个事件,每个资源都可以形成一个等待队列,一个进程还可以等待多个事件的发生,所以通过一个单独的类型来形成队列是需要的。linux通过sleep_on函数来将某个进程加入到某个等待队列中和从等待队列中删除。调用sleep_on的进程都会主动让出cpu进入等待状态,可以通过wake_up来唤醒某个等待状态的进程。

    分类:  linux内核
    展开全文
  • 全面解析Linux 内核 3.10.x - 进程链表

    千次阅读 2016-01-05 20:51:20
    From: 全面解析Linux 内核 3.10.x - 进程管理 把你的心、我的心、串一串串一株幸运草、串一个同心圆 - Love一、双向链表在内核中的运用传统的双向链表即表示链表有双头,双连表的好处在于不管是插入亦或是查找,其...

    From: 全面解析Linux 内核 3.10.x - 进程管理

    把你的心、我的心、串一串串一株幸运草、串一个同心圆 - Love

    2016,又是新的一年,新的起点。嗯嗯,最近文章产量不多,因为在公司帮助同事在调试某某驱动。刚开始三天的时候用他们给的代码,进展不大。后三天我一怒之下,重新把代码梳理并且修改了一遍,然后问题解决了。这里有一个心得(其实好几次想说),与其步履维艰的去按照他们的代码风格去调试,不如彻底打破,按照解决问题的流程重新写一遍(你懂的)。
    下面我继续Go … Kernel. 总结完此处内核进程的一些基本用法和概念可以告一段落了,之后就去研究具体的进程调度。嗯嗯,就这。

    一、双向链表在内核中的运用

    传统的双向链表即表示链表有双头,双连表的好处在于不管是插入亦或是查找,其算法复杂度明显比单链表要优化很多,但是双连表由于其本身的复杂性,故而很多程序员都是避而不见,或者视而不见!
    但是在这里我们必须将此重新掌握!
    还记得链表的定义吗? 有指针域,数据域。
    双连表有两个指针域,即直接前驱,直接后继!

    1、list_head 结构

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

    字段next 和 prev 分别表示通用双向链表向前和向后的指针元素!list_head字段的指针中存放的是另一个list_head字段的元素,而不是本身的数据结构地址。如图
    list_head

    新链表是用LIST_HEAD(list_name)宏创建的,它声明类型为list_head的新变量list_name,该变量作为新链表头的占位符,是一个哑元素,LIST_HEAD(list_name)宏还初始化list_head数据结构的prev和next字段,让它们指向list_name变量本身。

    1.1、LIST_HEAD 示例用法
    #include <linux/module.h>
    #include <linux/init.h>
    #include<linux/sched.h>
    #include<linux/sem.h>
    #include <linux/slab.h>
    #include <linux/list.h>
    #define N 10
    typedef struct info{
     char id;
     char character;
     char parent_id;
     struct list_head   member;
    }info_s; 
    
    int List_Demo_init(void)
    {
        int i = 0,ret = 0;
        struct  info info_head={
            .id = 0,
            .character = 'a',
            .parent_id = 1,
            .member = LIST_HEAD_INIT(info_head.member),
        };
         //插入N个元素
         for(i = 0;i < N; i++)                            
         {
             struct info *info_tmp;
             info_tmp = kmalloc(sizeof(struct info),GFP_KERNEL);
             if(info_tmp==NULL) 
                 return -1;
             info_tmp->id = i;
             info_tmp->character =(char)(64 + i);
             info_tmp->parent_id = i + 1;
             list_add(&info_tmp->member,&info_head.member);
         }
         //遍历N个元素    
         struct info *info_p, *p;
               struct list_head *pos;
               int count = 0;
               info_p=&info_head;
               list_for_each(pos,&info_p->member)
                    {
                        p = list_entry(pos,struct info,member);
                    count++;
                    printk("ID - %d -- Name = %c\nparent_id - %d.\n",p->id,p->character,p->parent_id);
                    }
    
            //删除元素
            list_del(&p->member);
            count = 0;
    
         //遍历N-1剩余元素
         list_for_each(pos,&info_p->member)
                    {
                        p = list_entry(pos,struct info,member);
                        count++;
                        printk("ID - %d -- Name = %c\nparent_id - %d.\n",p->id,p->character,p->parent_id);
                    }
         return 0;
    }
    static void List_Demo_Exit(void)
    {
        printk("Exit\n");
    }
    
    module_init(List_Demo_init);
    module_exit(List_Demo_Exit);
    MODULE_AUTHOR("Keven");
    MODULE_DESCRIPTION("List Head Description");
    MODULE_LICENSE("GPL");
    

    List_Head 在驱动中经常会使用,其语法简洁,使用方便。
    Linux 2.6内核支持一种双向链表,其与list_head 有着明显的区别,因为它不是循环链表,主要用于散列表,对散列表而言重要的是空间而不是固定的时间内找到表中的最后一个元素。

    进程链表

    我们首先介绍双向链表的第一个例子 – 进程链表,进程链表把所有的进程的描述符链接起来,每个task_struct 结构都包含一个list_head类型的tasks字段,这个类型的prev 和 next字段分别指向前面和后面的task_struct 元素。
    进程链表的头是init_task 描述符,本质位0号进程(swapper or idle)的描述符。
    其中还有相关宏用来将进程间的父子关系的联系。

    运行状态的进程链表

    操作系统跑起来后有很多个进程在进行一系列状态改变以及开销的更改,以及CPU调度,
    当内核寻找一个新进程在CPU上运行时,必须考虑可运行进程的状态。
    提高调度程序运行速度的诀窍是建立多个可运行进程链表,每种进程优先权对应一个不同的链表。每个task_struct 描述包含一个list_head类型的字段run_list.


    By: Keven - 点滴积累

    展开全文
  • Linux中TASK_RUNNING状态的进程链表

    千次阅读 2012-02-08 16:25:30
    早先的Linux版本把所有处于TASK_RUNNING状态的进程组织在一个叫做运行队列(runqueue)的...为了实现在固定的时间内选出“最佳”的可运行程序,内核将可运行进程的优先级划分为0-139,并为此建立了140个可运行进程链表


    早先的Linux版本把所有处于TASK_RUNNING状态的进程组织在一个叫做运行队列(runqueue)的链表中,由于维持链表中的进程按优先级排序的开销过大,因此,早期的调试程序需扫描整个队列以选择“最佳”的可运行程序。


    Linux2.6实现的运行队列有所不同。为了实现在固定的时间内选出“最佳”的可运行程序,内核将可运行进程的优先级划分为0-139,并为此建立了140个可运行进程链表,用以组织处于TASK_RUNNING状态的进程,每个进程优先权对应一个不同的链表。此外,在多处理器系统中,每个CPU都有它自己的运行队列。


    Linux2.6实现的运行队列结构如下:

    类型字段描述
    intnr_active链表中进程描述符的数量
    unsigned long[5]bitmap优先权位图:当且仅当某个优先权的进程链表不为空时设置相应的位标志
    struct list_head[140]queue140个优先权队列的头结点


    进程描述符的结构都包含一个list_head类型的tasks字段,这个类型的prev和next字段分别指向前面和后面的task_struct元素,实现双向链表。

     



     



    展开全文
  • Linux内核链表分析

    千次阅读 2016-12-13 19:31:25
    从Ubuntu系统中获取内核链表头文件方式: cp list.h /home/gec/Download/linux-2.6.35.7-gec/include/linux /home/gec/Download/linux-2.6.35.7-gec/include/linux是list.h的路径 或者cp list.h /usr/src/linux...
    从Ubuntu系统中获取内核链表头文件方式:

    cp list.h /home/gec/Download/linux-2.6.35.7-gec/include/linux

    /home/gec/Download/linux-2.6.35.7-gec/include/linux是list.h的路径

    或者cp list.h /usr/src/linux-headers-3.5.0-23/include/linux/list.h


     

     

    本文详解了内核中面向对象的list结构的原理,以及如何以list为内嵌对象来构造自己的链表结构,如何从内嵌list对象获得自定义的对象指针;探讨了各种宏或者函数的详细使用方法及怎样以通用list结构来操作自定义对象。

    【关键字】双向循环链表,list,list_entry,typeof,containerof,list_for_each, list_for_each_entry

     

    1、双循环链表传统实现

    2、Linux内核中双循环链表实现

    3、定义和初始化

    4、通用链表操作接口

    4.1添加节点

    4.2删除节点

    4.3移动节点

    4.4链表判空

    4.5链表合并

    5、获取宿主对象指针

    6、遍历

    6.1 List-head链表遍历

    6.2遍历宿主对象

    7、如何使用Linux中的双循环链表

     

    、双循环链表传统实现

    在传统的双循环链表实现中,如果创建某种数据结构的双循环链表,通常采用的办法是在这个数据结构的类型定义中加入两个(指向该类型对象的)指针next和prev。例如:

    typedef struct foo {

        …

        struct foo *prev;

        struct foo *next;

        …

    } foo_t;

    这里给出了对应的节点结构、空的双循环链表和非空的双循环链表示意图。

     

     

    Linux内核中双循环链表实现

    linux内核中,有大量的数据结构需要用到双循环链表,例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式,需要为这些数据结构维护各自的链表,并且为每个链表都要设计插入、删除等操作函数。因为用来维持链表的next和prev指针指向对应类型的对象,因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。

     

    Linux源代码树的include/linux/list.h文件中,采用了一种类型无关的双循环链表实现方式。其思想是将指针prev和next从具体的数据结构中提取出来构成一种通用的"双链表"数据结构list_head。如果需要构造某类对象的特定链表,则在其结构(被称为宿主数据结构)中定义一个类型为list_head类型的成员,通过这个成员将这类对象连接起来,形成所需链表,并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数,即可构造和操作不同对象的链表,而无需为每类对象的每种列表编写专用函数,实现了代码的重用。

     

    list_head结构

    -----------struct list_head{}及初始化宏---------

    struct list_head

    {

           struct list_head *next, *prev;

    };

    当用此类型定义一个独立的变量时,其为头结点。当其为某个结构体的一个成员时,其为普通结点。尽管形式一样,但表达的意义不同,是否应该定义为两个类型list_head和list_node???无法分开,空链表时指向了自己

     

    list_head成员作为"连接件",把宿主数据结构链接起来。如下图所示:

     

    Linux内核中的双循环链表实现方式下:

    1. list_head类型的变量作为一个成员嵌入到宿主数据结构内;

    2. 可以将链表结构放在宿主结构内的任何地方;

    3. 可以为链表结构取任何名字;

    4. 宿主结构可以有多个链表结构;

    5. 用list_head中的成员和相对应的处理函数来对链表进行遍历;

    6. 如果想得到宿主结构的指针,使用list_entry可以算出来。

     

    、定义和初始化

    --LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------

    #define LIST_HEAD_INIT(name) { &(name), &(name) }

    #define LIST_HEAD(name) \

           struct list_head name = LIST_HEAD_INIT(name)

     

    需要注意的是,Linux 的每个双循环链表都有一个链表头,链表头也是一个节点,只不过它不嵌入到宿主数据结构中,即不能利用链表头定位到对应的宿主结构,但可以由之获得虚拟的宿主结构指针。

     

    LIST_HEAD()宏可以同时完成定义链表头,并初始化这个双循环链表为空。

    静态定义一个list_head 类型变量,该变量一定为头节点。name为struct list_head{}类型的一个变量,&(name)为该结构体变量的地址。用name结构体变量的始地址将该结构体变量进行初始化。

     

    #define INIT_LIST_HEAD(ptr) do { \

           (ptr)->next = (ptr); (ptr)->prev = (ptr); \

    } while (0)

    动态初始化一个已经存在的list_head对象,ptr为一个结构体的指针,这样可以初始化堆栈以及全局区定义的list_head对象。ptr使用时候,当用括号,(ptr),避免ptr为表达式时宏扩展带来的异常问题。此宏很少用于动态初始化内嵌的list对象,主要是链表合并或者删除后重新初始化头部。若是在堆中申请了这个链表头,调用INIT_LIST_HEAD()宏初始化链表节点,将next和prev指针都指向其自身,我们就构造了一个空的双循环链表。

     

    2.6内核中内联函数版本如下:

    static inline void INIT_LIST_HEAD(struct list_head *list)

    {

           list->next = list;

           list->prev = list;

    }

    此时的参数有明确的类型信息struct list_head,同时可以看出其为指针,list无须象宏中那样(),即使参数为表达式,其也是求值后再作为参数传入的。内联函数有严格的参数类型检查,同时不会出现宏函数扩展带来的异常问题,但是运行效率和空间效率与宏函数一致。

     

    、通用链表操作接口

    添加节点

    在上面的设计下,所有链表(包括添加、删除、移动和拼接等)操作都是针对数据结构list_head进行的。提供给用户的的添加链表的操作有两种:表头添加和表尾添加。注意到,Linux双循环链表中有一个链表头,表头添加是指添加到链表头之后,而表尾添加则是添加到链表头的prev所指链表节点之后。

     

    ------------__list_add()------list_add()------list_add_tail()-------

    static inline void __list_add(struct list_head *new, struct list_head *prev,  struct list_head *next)

    {

           next->prev = new;

           new->next = next;

           new->prev = prev;

           prev->next = new;

    }

    普通的在两个非空结点中插入一个结点,注意new、prev、next都不能是空值。

    Prev可以等于next,此时在只含头节点的链表中插入新节点。

     

    static inline void list_add(struct list_head *new, struct  list_head *head)

    {

           __list_add(new, head, head->next);

    }

    head和head->next两指针所指向的结点之间插入new所指向的结点。

    即:在head指针后面插入new所指向的结点。Head并非一定为头结点。

    当现有链表只含有一个头节点时,上述__list_add(new, head, head->next)仍然成立。

     

    static inline void list_add_tail(struct list_head *new, struct list_head *head)

    {

           __list_add(new, head->prev, head);

    }

    在结点指针head所指向结点的前面插入new所指向的结点。当head指向头节点时,也相当于在尾结点后面增加一个new所指向的结点。

    注意:

    head->prev不能为空,即若head为头结点,其head->prev当指向一个数值,一般为指向尾结点,构成循环链表。

     

    上述三个函数实现了添加一个节点的任务,其中__list_add()为底层函数,“__”通常表示该函数是底层函数,供其他模块调用,此处实现了较好的代码复用,list_add和list_add_tail虽然原型一样,但调用底层函数__list_add时传递了不同的参数,从而实现了在head指向节点之前或之后添加新的对象。

     

    删除节点

    如果要从链表中删除某个链表节点,则可以调用list_del或list_del_init。

    需要注意的是,上述操作均仅仅是把节点从双循环链表中拿掉,用户需要自己负责释放该节点对应的数据结构所占用的空间,而这个空间本来就是用户分配的。

     

    -----------__list_del()---list_del()-----list_del_init()----------

    static inline void __list_del(struct list_head * prev, struct list_head * next)

    {

           next->prev = prev;

           prev->next = next;

    }

    prev和next指针所指向的结点之间,两者互相所指。在后面会看到:prev为待删除的结点的前面一个结点,next为待删除的结点的后面一个结点。

     

    static inline void list_del(struct list_head *entry)

    {

           __list_del(entry->prev, entry->next);

           entry->next = LIST_POISON1;

           entry->prev = LIST_POISON2;

    }

    删除entry所指的结点,同时将entry所指向的结点指针域封死。

    LIST_POISON1,LIST_POISON2的解释说明:

    Linux 内核中解释:These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses  non-initialized list entries.

    #define LIST_POISON1  ((void *) 0x00100100)

    #define LIST_POISON2  ((void *) 0x00200200)

    常规思想是:entry->next = NULL; entry->prev = NULL; 保证不可通过该节点进行访问。

     

    ---------------list_del_init()--------------------

    static inline void list_del_init(struct list_head *entry)

    {

           __list_del(entry->prev, entry->next);

           INIT_LIST_HEAD(entry);

    }

    删除entry所指向的结点,同时调用LIST_INIT_HEAD()把被删除节点为作为链表头构建一个新的空双循环链表。

     

    移动节点

    Linux还提供了两个移动操作:list_move和list_move_tail。

    -----------list_move()--list_move_tail()----------

    static inline void list_move(struct list_head *list, struct list_head *head)

    {

            __list_del(list->prev, list->next);

            list_add(list, head);

    }

    list结点前后两个结点互相指向彼此,删除list指针所指向的结点,再将此结点插入head,和head->next两个指针所指向的结点之间。

    即:将list所指向的结点移动到head所指向的结点的后面。

     

    static inline void list_move_tail(struct list_head *list,    struct list_head *head)

    {

            __list_del(list->prev, list->next);

            list_add_tail(list, head);

    }

    删除了list所指向的结点,将其插入到head所指向的结点的前面,如果head->prev指向链表的尾结点的话,就是将list所指向的结点插入到链表的结尾。

     

    链表判空

    list-head构成的双向循环链表中,通常有一个头节点,其不含有有效信息,初始化时prev和next都指向自身。判空操作是判断除了头节点外是否有其他节点。

    ---------------------list_empty()-------------

    static inline int list_empty(const struct list_head *head)

    {

           return head->next == head;

    }

    测试链表是否为空,如果是只有一个结点,head,head->next,head->prev都指向同一个结点,则这里会返回1,表示空;但这个空不是没有任何结点,而是只有一个头结点,因为头节点只是纯粹的list节点,没有有效信息,故认为为空。

     

    --------------------list_empty_careful()---------

    static inline int list_empty_careful(const struct list_head *head)

    {

           struct list_head *next = head->next;

           return (next == head) && (next == head->prev);

    }

    分析:

    1.只有一个头结点head,这时head指向这个头结点,head->next,head->prev指向head,即:head==head->next==head->prev,这时候list_empty_careful()函数返回1。

    2.有两个结点,head指向头结点,head->next,head->prev均指向后面那个结点,即:head->next==head->prev,而head!=head->next,head!=head->prev.所以函数将返回0

    3.有三个及三个以上的结点,这是一般的情况,自己容易分析了。

    注意:这里empty list是指只有一个空的头结点,而不是毫无任何结点。并且该头结点必须其head->next==head->prev==head

     

    链表合并

    Linux还支持两个链表的拼接,提供给用户的具体函数是list_splice和list_splice_init:

     

    ---------------__list_splice()------------------

    static inline void __list_splice(struct list_head *list,      struct list_head *head)

    {

           struct list_head *first = list->next;

           struct list_head *last  = list->prev;

           struct list_head *at    = head->next;

     

           first->prev = head;

           head->next = first;

     

           last->next = at;

           at->prev = last;

    }

    将一个非空链表插入到另外一个链表中。不作链表是否为空的检查,由调用者默认保证。因为每个链表只有一个头节点,将空链表插入到另外一个链表中是没有意义的。但被插入的链表可以是空的。

     

    --------------------list_splice()----------------

    /**

     * list_splice - join two lists

     * @list: 被合并的链表的头节点.

     * @head: the place to add it in the first list.

     */

    static inline void list_splice(struct list_head *list, struct list_head *head)

    {

           if (!list_empty(list))

                  __list_splice(list, head);

    }

     

    这种情况会丢弃list所指向的头结点,这是特意设计的,因为两个链表有两个头结点,要去掉一个头结点。只要list非空链,head无任何限制,该程序都可以实现链表合并。

     

    --------------------list_splice_init()-----------------------------------

    /**

     * list_splice_init - join two lists and reinitialise the emptied list.

     * @list: the new list to add.

     * @head: the place to add it in the first list.

     *

     * The list at @list is reinitialised

     */

    static inline void list_splice_init(struct list_head *list,

                                    struct list_head *head)

    {

           if (!list_empty(list)) 0

           {

                  __list_splice(list, head);

                  INIT_LIST_HEAD(list);

           }

    }

    将一个链表的有效信息合并到另外一个链表后,重新初始化空的链表头。

     

    、获取宿主对象指针

    如果需要有某种数据结构的队列,就在这种数据结构定义内部放上一个list_head数据结构。例如,建立数据结构foo链表的方式是,在foo的定义中,嵌入了一个list_head成员list。这里foo就是所指的"宿主"。

    typedef struct foo {

        …

        struct list_head list;

        …

    };

     

    但是,如何通过list_head成员访问到宿主结构项呢?毕竟list_head不过是个连接件,而我们需要的是一个"特定"的数据结构链表。

    先介绍几个基本宏:offsetof、typeof、containerof

    -------\linux\stddef.h-----offsetof()-----------

    #define __compiler_offsetof(a,b)  __builtin_offsetof(a,b)

    __builtin_offsetof()宏就是在编译器中已经设计好了的函数,直接调用即可。

    -------------------------------

    #undef offsetof  //取消先前的任何定义,可以保证下面的定义生效

    #ifdef __compiler_offsetof

    #define offsetof(TYPE,MEMBER)  __compiler_offsetof(TYPE,MEMBER)

    #else

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    #endif

     

    一共4步

    1. ( (TYPE *)0 ) 0地址强制 "转换" 为 TYPE结构的指针;

    2. ((TYPE *)0)->MEMBER   访问结构中的数据成员;

    3.  &( ( (TYPE *)0 )->MEMBER)取出数据成员的地址;

    4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型.巧妙之处在于将0转换成(TYPE*),结构以内存空间首地址0作为起始地址,则成员地址自然为偏移地址;

    举例说明:

    #include

    typedef struct _test

    {

         char i;

         int j;

         char k;

    }Test;

    int main()

    {

         Test *p = 0;

         printf("%p\n", &(p->k));

    }

    这里使用的是一个利用编译器技术的小技巧(编译器自动算出成员的偏移量),即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址,然后根据结构体的首地址为0,从而得出该偏移地址就是该结构体变量在该结构体中的偏移,即:该结构体成员变量距离结构体首的距离。在offsetof()中,这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结构,offsetof(type,member)是一个常量,list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。

     

    ---------------------typeof()--------------------

    unsigned int i;

    typeof(i) x;

    x=100;

    printf("x:%d\n",x);

    typeof() 是 gcc 的扩展,和 sizeof() 类似。

     

    ------------------------

    container_of 宏中,它用来给 typeof() 提供参数,以获得 member 成员的数据类型;

    ---------------container_of()--------------------

    container_of() 来自\linux\kernel.h

    内核中的注释: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.(type *)0->member为设计一个type类型的结构体,起始地址为0,编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变量的地址,由于结构体起始地址为0,所以此结构体成员变量的偏移地址就等于其成员变量在结构体内距离结构体开始部分的偏移量。即:&(type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为:(size_t)(& ((type *)0)->member)经过size_t的强制类型转换后,其数值为结构体内的偏移量。该偏移量这里由offsetof()求出。

     

    2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr指针.ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针,其指向ptr所指向的变量处。

     

    3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member) )用来求出结构体起始地址(为char *型指针),然后(type *)( (char *)__mptr - offsetof(type,member) )在(type *)作用下进行将字节型的结构体起始指针转换为type *型的结构体起始指针。

    这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。

     

    介绍了上面的几种基本宏后,对list_entry的理解就容易了。

    ----------------list_entry()--------------------

    list_entry()宏,获取当前list_head链表节点所在的宿主结构项。第一个参数为当前list_head节点的指针,即指向宿主结构项的list_head成员。第二个参数是宿主数据结构的定义类型。第三个参数为宿主结构类型定义中list_head成员名。

    #define list_entry(ptr, type, member) \

           container_of(ptr, type, member)

    扩展替换即为:

    #define list_entry(ptr, type, member) \

        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

    例如,我们要访问foo链表(链表头为head)中首个元素,则如此调用:

    list_entry(head->next, struct foo, list);

    经过C预处理的文字替换,这一行的内容就成为:

    ((struct foo *)((char *)(head->next) - (unsigned long)(&((struct foo *)0)->list)))

     

    获取宿主对象指针的原理如上图所示。我们考虑list_head类型成员member相对于宿主结构(类型为type)起始地址的偏移量。对于所有该类型的宿主对象,这个偏移量是固定的。并且可以在假设宿主对象地址值为0,通过返回member成员的地址获得,即等于(unsigned long)(&((type *)0)->member)。这样,将当前宿主对象的"连接件"地址(ptr)减去这个偏移量,得到宿主对象地址,再将它转换为宿主数据结构类型的指针。

    需要重申的是,链表头没有被嵌入到宿主对象中,因此对链表头执行宿主对象指针获取操作是没有意义的。

     

    、遍历

    链表遍历

    遍历是双循环链表的基本操作,为此Linux定义了一些宏。

    list_for_each对遍历链表中的所有list_head节点,不涉及到对宿主结构的处理。list_for_each实际是一个 for 循环,利用传入的指向list_head结构的指针作为循环变量,从链表头开始(并跳过链表头),逐项向后移动指针,直至又回到链表头。

     

    ----------------list_for_each()------------------

    #define list_for_each(pos, head) \

           for (pos = (head)->next; prefetch(pos->next), pos != (head); \

                   pos = pos->next)

    head为头节点,遍历过程中首先从(head)->next开始,当pos==head时退出,故head节点并没有访问,这和list结构设计有关,通常头节点就是纯粹的list结构,不含有其他有效信息,或者头节点含有其他信息,如内核PCB链表中的头节点为idle任务,但其不参予比较优先级,因此此时头节点只是作为双向链表遍历一遍的检测标志。

     

    为提高遍历速度,还使用了预取。

    -----asm-x86_64\processor.h---prefetch()---------

    static inline void prefetch(void *x)

    {

           asm volatile("prefetcht0 %0" :: "m" (*(unsigned long *)x));

    }

    x指针作强制类型转换为unsigned long *型,然后取出该内存操作数,送入高速缓存。

     

     

    ----------------__list_for_each()-----------------

    #define __list_for_each(pos, head) \

           for (pos = (head)->next; pos != (head); pos = pos->next)

    list_for_each()有prefetch()用于复杂的表的遍历,而__list_for_each()无prefetch()用于简单的表的遍历,此时表项比较少,无需缓存。

     

    ----------------list_for_each_prev()-------------

    #define list_for_each_prev(pos, head) \

           for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \

                   pos = pos->prev)

    反向遍历节点

     

    ----------------list_for_each_safe()--------------

    如果在遍历过程中,包含有删除或移动当前链接节点的操作,由于这些操作会修改遍历指针,这样会导致遍历的中断。这种情况下,必须使用list_for_each_safe宏,在操作之前将遍历指针缓存下来:

    内核中解释的精华部分:

    /*

     * list_for_each_safe     -      iterate over a list safe against removal of list entry

      */

    #define list_for_each_safe(pos, n, head) \

           for (pos = (head)->next, n = pos->next; pos != (head); \

                  pos = n, n = pos->next)

    for循环中n暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。也就是说你可以遍历完当前节点后将其删除,同时可以接着访问下一个节点,遍历完毕后就只剩下一个头节点。这就叫safe。十分精彩。典型用途是多个进程等待在同一个等待队列上,若事件发生时唤醒所有进程,则可以唤醒后将其依次从等待队列中删除。

     

    遍历宿主对象

    如果只提供对list_head结构的遍历操作是远远不够的,我们希望实现的是对宿主结构的遍历,即在遍历时直接获得当前链表节点所在的宿主结构项,而不是每次要同时调用list_for_each和list_entry。对此,Linux提供了list_for_each_entry()宏,第一个参数为传入的遍历指针,指向宿主数据结构,第二个参数为链表头,为list_head结构,第三个参数为list_head结构在宿主结构中的成员名。

    -------------list_for_each_entry()---------------

    #define list_for_each_entry(pos, head, member)                       \

           for (pos = list_entry((head)->next, typeof(*pos), member);       \

                prefetch(pos->member.next), &pos->member != (head);        \

                pos = list_entry(pos->member.next, typeof(*pos), member))

     

    这是用于嵌套的结构体中的宏:

    struct example_struct

    {

           struct list_head list;

           int priority;

           ... //其他结构体成员

    };

    struct example_struct *node = list_entry(ptr,struct example_struct,list);

     

    自己分析:对比list_entry(ptr,type,member)可知有以下结果:

    其中list相当于member成员,struct example_struct相当于type成员,ptr相当于ptr成员。而list{}成员嵌套于example_struct{}里面。ptr指向example_struct{}中的list成员变量的。在list_entry()作用下,将ptr指针回转指向struct example_struct{}结构体的开始处。

     

    pos当指向外层结构体,比如指向struct example_struct{}的结点,最开始时候,head指向链表结构体struct list_head{}的头结点,头节点不含有有效信息,(head)->next则指向第一个外层结点的内嵌的链表结点struct list_head{} list,由此得出的pos当指向第一个有效结点。member即是指出该 list为其内嵌的结点。

    思路:用pos指向外层结构体的结点,用head指向内层嵌入的结构体的结点。用(head)->next,pos->member.next(即:ptr->list.next)来在内嵌的结构体结点链表中遍历。每遍历一个结点,就用list_entry()将内嵌的pos->member.next指针回转为指向该结点外层结构体起始处的指针,并将指针进行指针类型转换为外层结构体型pos。&pos->member! = (head)用pos外层指针引用member即:list成员,与内层嵌入的链表之头结点比较来为循环结束条件。

    当遍历到头节点时,此时并没有pos这样一个type类型数据指针,而是以member域强制扩展了一个type类型的pos指针,此时其member域的地址就是head指针所指向的头节点,遍历结束,头节点的信息没有被访问。

     

    -------------list_for_each_entry_reverse()-------

    #define list_for_each_entry_reverse(pos, head, member)                  \

           for (pos = list_entry((head)->prev, typeof(*pos), m+ember);     \

                prefetch(pos->member.prev), &pos->member != (head);        \

                pos = list_entry(pos->member.prev, typeof(*pos), member))

    分析类似上面。

     

    ---------------list_prepare_entry()---------------

    如果遍历不是从链表头开始,而是从已知的某个pos结点开始,则可以使用list_for_each_entry_continue(pos,head,member)。但为了确保pos的初始值有效,Linux专门提供了一个list_prepare_entry(pos,head,member)宏,如果pos有值,则其不变;如果没有,则从链表头强制扩展一个虚pos指针。将它的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。

     

    内核中的list_prepare_entry()的代码:

    #define list_prepare_entry(pos, head, member) \

           ((pos) ? : list_entry(head, typeof(*pos), member))

    分析:

    :前面是个空值,即:若pos不为空,则pos为其自身。等效于:

    (pos)? (pos): list_entry(head,typeof(*pos),member)

    注意内核格式::前后都加了空格。

     

    ------------list_for_each_entry_continue()--------

    内核中的list_for_each_entry_continue()的代码:

    #define list_for_each_entry_continue(pos, head, member)         \

           for (pos = list_entry(pos->member.next, typeof(*pos), member);      \

                prefetch(pos->member.next), &pos->member != (head);  \

                pos = list_entry(pos->member.next, typeof(*pos), member))

    此时不是从头节点开始遍历的,但仍然是以头节点为结束点的,即没有遍历完整个链表。

    要注意并不是从pos开始的,而是从其下一个节点开始的,因为第一个有效pos是从pos->member.next扩展得到的。

     

    -------------list_for_each_entry_safe()-----------

    它们要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。

     

    内核中的注释与源代码:

    /**

     * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry

     * @pos: the type * to use as a loop counter.

     * @n:           another type * to use as temporary storage

     * @head:      the head for your list.

     * @member: the name of the list_struct within the struct.

     */

     

    #define list_for_each_entry_safe(pos, n, head, member)                   \

           for (pos = list_entry((head)->next, typeof(*pos), member),       \

                  n = list_entry(pos->member.next, typeof(*pos), member);  \

                &pos->member != (head);                              \

                pos = n, n = list_entry(n->member.next, typeof(*n), member))

    分析类似上面。容易明白。

     

    --------list_for_each_entry_safe_continue()-------

    #define list_for_each_entry_safe_continue(pos, n, head, member)           \

           for (pos = list_entry(pos->member.next, typeof(*pos), member),            \

                  n = list_entry(pos->member.next, typeof(*pos), member);         \

                &pos->member != (head);                                      \

                pos = n, n = list_entry(n->member.next, typeof(*n), member))

     

    、如何使用Linux中的双循环链表

    本文例子来自http://isis.poly.edu/kulesh/stuff/src/klist/,只是对其中注释部分作了翻译。

    #include

    #include

    #include "list.h"

    struct kool_list{

        int to;

        struct list_head list;

        int from;

    };

    int main(int argc, char **argv){

        struct kool_list *tmp;

        struct list_head *pos, *q;

        unsigned int i;

        struct kool_list mylist;

        INIT_LIST_HEAD(&mylist.list);

        /* 您也可以使用宏LIST_HEAD(mylist)来声明并初始化这个链表 */

        /*向链表中添加元素*/

        for(i=5; i!=0; --i){

            tmp= (struct kool_list *)malloc(sizeof(struct kool_list));

     

            /*INIT_LIST_HEAD(&tmp->list); 调用这个函数将初始化一个动态分配的list_head。也可以不调用它,因为在后面调用的add_list()中将设置next和prev域。*/

            printf("enter to and from:");

            scanf("%d %d", &tmp->to, &tmp->from);

            /*将tmp添加到mylist链表中*/

            list_add(&(tmp->list), &(mylist.list));

            /*也可以使用list_add_tail()将新元素添加到链表的尾部。*/

        }

        printf("\n");

        /*现在我们得到了数据结构struct kool_list的一个循环链表,我们将遍历这个链表,并打印其中的元素。*/

        /*list_for_each()定义了一个for循环宏,第一个参数用作for循环的计数器,换句话说,在整个循环过程中它指向了当前项的list_head。第二个参数是指向链表的指针,在宏中保持不变。*/

        printf("traversing the list using list_for_each()\n");

        list_for_each(pos, &mylist.list){

            /*此刻:pos->next指向了下一项的list变量,而pos->prev指向上一项的list变量。而每项都是struct kool_list类型。但是,我们需要访问的是这些项,而不是项中的list变量。因此需要调用list_entry()宏。*/

            tmp= list_entry(pos, struct kool_list, list);

            /*给定指向struct list_head的指针,它所属的宿主数据结构的类型,以及它在宿主数据结构中的名称,list_entry返回指向宿主数据结构的指针。例如,在上面一行, list_entry()返回指向pos所属struct kool_list项的指针。*/

            printf("to= %d from= %d\n", tmp->to, tmp->from);

        }

        printf("\n");

        /* 因为这是一个循环链表,我们也可以向前遍历。只需要将list_for_each替换为list_for_each_prev。我们也可以使用list_for_each_entry()遍历链表,在给定类型的项间进行循环。例如:*/

        printf("traversing the list using list_for_each_entry()\n");

        list_for_each_entry(tmp, &mylist.list, list)

        printf("to= %d from= %d\n", tmp->to, tmp->from);

        printf("\n");

     

        /*下面将释放这些项。因为我们调用list_del()从链表中删除各项,因此需要使用list_for_each()宏的"安全"版本,即list_for_each_safe()。务必注意,如果在循环中有删除项(或把项从一个链表移动到另一个链表)的操作,必须使用这个宏。*/

        printf("deleting the list using list_for_each_safe()\n");

        list_for_each_safe(pos, q, &mylist.list){

            tmp= list_entry(pos, struct kool_list, list);

            printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);

            list_del(pos);

            free(tmp);

        }

        return 0;

    }

    注意:上述代码在使用gcc编译时需要加上__KERNEL__定义。

     

    Linux内核源码分析-链表代码分析

    **************************************************

    -------------双向循环链表---------------------------

    来源于:list.h

    设计思想:尽可能的代码重用,化大堆的链表设计为单个链表。

    链表的构造:如果需要构造某类对象的特定列表,则在其结构中定义一个类型为list_head指针的成员,通过这个成员将这类对象连接起来,形成

    所需列表,并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数,即可构造和操作不同对象的列表,而无需为每类对象的每种列表编写专用函数,实

    现了代码的重用。

    如果想对某种类型创建链表,就把一个list_head类型的变量嵌入到该类型中,用list_head中的成员和相对应的处理函数来对链表进行遍历。如果想得到相应的结构的指针,使用list_entry可以算出来。

    -------------防止重复包含同一个头文件---------------

    #ifndef _LINUX_LIST_H

    #define _LINUX_LIST_H

    ...

    #endif

    用于防止重复包含同一个list.h头文件

    -----------struct list_head{}及初始化宏---------

    struct list_head 

    {

            struct list_head *next, *prev;

    };

    list_head从字面上理解,好像是头结点的意思。但从这里的代码来看却是普通结点的结构体。在后面的代码中将list_head当成普通的结点来处理。

    --LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------

    #define LIST_HEAD_INIT(name) { &(name), &(name) }

    #define LIST_HEAD(name) \

            struct list_head name = LIST_HEAD_INIT(name)

    分析:name当为结构体struct list_head{}的一个结构体变量,&(name)为该结构体变量的地址。用name结构体变量的始地址将该结构体变量进行初始化。

    #define INIT_LIST_HEAD(ptr) do { \

            (ptr)->next = (ptr); (ptr)->prev = (ptr); \

    } while (0)

    1.ptr为一个结构体的指针,而name为一个结构体变量;

    2.ptr使用时候,当用括号,(ptr);

    ------------__list_add()---list_add()-------------

    static inline void __list_add(struct list_head *new, struct list_head *prev,  struct list_head *next)

    {

            next->prev = new;

            new->next = next;

            new->prev = prev;

            prev->next = new;

    }

    1.普通的在两个非空结点中插入一个结点,注意new,prev,next都不能是空值。

    2.即:适用于中间结点插入。首结点和尾结点则由于指针为空,不能用此函数。

    3.在prev指针和next指针所指向的结点之间插入new指针所指向的结点。

    static inline void list_add(struct list_head *new, struct  list_head *head)

    {

            __list_add(new, head, head->next);

    }

    head和head->next两指针所指向的结点之间插入new所指向的结点。

    即:在head指针后面插入new所指向的结点。此函数用于在头结点后面插入结点。

    注意:对只有一个单个结点的链表,则head->next为空,list_add()不能用。

    -------------list_add_tail()-------------------

    static inline void list_add_tail(struct list_head *new, struct list_head *head)

    {

            __list_add(new, head->prev, head);

    }

    在头结点指针head所指向结点的前面插入new所指向的结点。也相当于在尾结点后面增加一个new所指向的结点。(条件是:head->prev当指向尾结点)

    注意:

    1.head->prev不能为空,即若head为头结点,其head->prev当指向一个数值,一般为指向尾结点,构成循环链表。

    2.对只有单个结点的头结点调用此函数则会出错。

    -----------__list_del()---list_del()--------------

    static inline void __list_del(struct list_head * prev, struct list_head * next)

    {

            next->prev = prev;

            prev->next = next;

    }

    prev和next指针所指向的结点之间,两者互相所指。在后面会看到:prev为待删除的结点的前面一个结点,next为待删除的结点的后面一个结点。

    static inline void list_del(struct list_head *entry)

    {

            __list_del(entry->prev, entry->next);

            entry->next = LIST_POISON1;

            entry->prev = LIST_POISON2;

    }

    删除entry所指的结点,同时将entry所指向的结点指针域封死。

    LIST_POISON1,LIST_POISON2的解释说明:

    Linux 内核中解释:These are non-NULL pointers that will result in page

    faults under normal circumstances, used to verify that nobody uses

    non-initialized list entries.

    #define LIST_POISON1  ((void *) 0x00100100)

    #define LIST_POISON2  ((void *) 0x00200200)

    常规思想是:entry->next = NULL; entry->prev = NULL;

    注意:Linux内核中的‘=’都与前后隔了一个空格,这样比紧靠前后要清晰。

    ---------------list_del_init()--------------------

    static inline void list_del_init(struct list_head *entry)

    {

            __list_del(entry->prev, entry->next);

            INIT_LIST_HEAD(entry);

    }

    删除entry所指向的结点,同时将entry所指向的结点的next,prev指针域指向自身。

    -----------list_move()--list_move_tail()----------

    static inline void list_move(struct list_head *list, struct list_head *head)

    {

            __list_del(list->prev, list->next);

            list_add(list, head);

    }

    list结点前后两个结点互相指向彼此,删除list指针所指向的结点,再将此结点插入head,和head->next两个指针所指向的结点之间。

    即:将list所指向的结点移动到head所指向的结点的后面。

    static inline void list_move_tail(struct list_head *list,        struct list_head *head)

    {

            __list_del(list->prev, list->next);

            list_add_tail(list, head);

    }

    删除了list所指向的结点,将其插入到head所指向的结点的前面,如果head->prev指向链表的尾结点的话,就是将list所指向的结点插入到链表的结尾。

    ---------------------list_empty()-------------

    static inline int list_empty(const struct list_head *head)

    {

            return head->next == head;

    }

    注意:

    1.如果是只有一个结点,head,head->next,head->prev都指向同一个结点,则这里会返回1,但链表却不为空,仍有一个头结点

    2.return 后面不带括号,且为一个表达式。

    3.测试链表是否为空,但这个空不是没有任何结点,而是只有一个头结点。

    --------------------list_empty_careful()---------

    static inline int list_empty_careful(const struct list_head *head)

    {

            struct list_head *next = head->next;

            return (next == head) && (next == head->prev);

    }

    分析:

    1.只有一个头结点head,这时head指向这个头结点,head->next,head->prev指向head,即:head==head->next==head->prev,这时候list_empty_careful()函数返回1。

    2.有两个结点,head指向头结点,head->next,head->prev均指向后面那个结点,即:head->

    next==head->prev,而head!=head->next,head!=head->prev.所以函数将返回0

    3.有三个及三个以上的结点,这是一般的情况,自己容易分析了。

    注意:这里empty list是指只有一个空的头结点,而不是毫无任何结点。并且该头结点必须其head->next==head->prev==head

    ---------------__list_splice()------------------

    static inline void __list_splice(struct list_head *list,         struct list_head *head)

    {

            struct list_head *first = list->next;

            struct list_head *last  = list->prev;

            struct list_head *at    = head->next;

            first->prev = head;

            head->next = first;

            last->next = at;

            at->prev = last;

    }

    --------------------list_splice()----------------

    /**

    * list_splice - join two lists

    * @list: the new list to add.

    * @head: the place to add it in the first list.

    */

    static inline void list_splice(struct list_head *list, struct list_head *head)

    {

            if (!list_empty(list))

                    __list_splice(list, head);

    }

    分析:

    情况1:

    普遍的情况,每个链表都至少有3个以上的结点:

    ====>此处作者画了图,可显示不出来,郁闷!!!

    ========》待作者上传一个word文档,图在里面。

    -------------------------------------------------------------------------------------------

    这种情况会丢弃list所指向的结点,这是特意设计的,因为两个链表有两个头结点,要去掉一个头结点。只要一个头结点。

    ---------------------------------------------------------------------------------------------------------------

     

    特殊情况1:

    初始情况:

    ------------------------------------------------------------------------

    特殊情况2:

    初始情况:

    --------------------list_splice_init()-----------------------------------

    /**

    * list_splice_init - join two lists and reinitialise the emptied list.

    * @list: the new list to add.

    * @head: the place to add it in the first list.

    *

    * The list at @list is reinitialised

    */

    static inline void list_splice_init(struct list_head *list,

                                        struct list_head *head)

    {

            if (!list_empty(list)) 

            {

                    __list_splice(list, head);

                    INIT_LIST_HEAD(list);

            }

    }

    --------------------\asm-i386\posix_types.h-------

    typedef unsigned int        __kernel_size_t;

    ------\linux\types.h---------size_t---------------

    #ifndef _SIZE_T

    #define _SIZE_T

    typedef __kernel_size_t                size_t;

    #endif

    -------------\linux\compiler-gcc4.h--------------

    #define __compiler_offsetof(a,b)  __builtin_offsetof(a,b)

    分析准备:__compiler_offsetof(),为gcc编译器中的编译方面的参数,查阅gcc方面的文档:

    --->gcc.pdf.Download from 

    www.gnu.org

    。其中解释如下:

    #define offsetof(type, member) __builtin_offsetof (type, member) 

    自己分析:即:__builtin_offsetof(a,b)就是#define offsetof(TYPE, MEMBER)

    ((size_t) &((TYPE

    *)0)->MEMBER)。__builtin_offsetof(a,b)和offsetof(TYPE,MEMBER)本质一样的,只是

    offsetof()宏是由程序员自己来设计(详见后面讲解)。而__builtin_offsetof()宏就是在编译器中已经设计好了的函数,直接调

    用即可。明白了这个区别后,下面的代码很好理解。 

    -------\linux\stddef.h-----offsetof()-----------

    #define __compiler_offsetof(a,b)  __builtin_offsetof(a,b)

    -------------------------------

    #undef offsetof

    #ifdef __compiler_offsetof

    #define offsetof(TYPE,MEMBER)  __compiler_offsetof(TYPE,MEMBER)

    #else

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    #endif

    1.对__compiler_offsetof()宏的分析:

    __compiler_offsetof来确认编译器中是否内建了功能同offsetof()宏一样的宏。若已经内建了这样的宏,则

    offsetof()就是使用这个内建宏__compiler_offsetof()即:__builtin_offsetof()宏。如果没有定义

    __compiler_offsetof()宏,则offsetof()宏就由程序员来设计之。

    2.对offsetof()宏的分析:(以下引用论坛)---曾经的腾讯QQ的笔试题。

    宿舍舍友参加qq笔试,回来讨论一道选择题,求结构中成员偏移。

    想起Linux内核链表,数据节点携带链表节点,通过链表访问数据的方法,用到offsetof宏,今天把它翻了出来:

    #define   offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER   ) 

    一共4步

    1. ( (TYPE *)0 ) 将零转型为TYPE类型指针;

    2. ((TYPE *)0)->MEMBER   访问结构中的数据成员;

    3.  &(  ( (TYPE *)0 )->MEMBER  )取出数据成员的地址;

    4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型.巧妙之处在于将0转换成(TYPE*),结构以内存空间首地址0作为起始地址,则成员地址自然为偏移地址;

    举例说明:

    #include 

    typedef struct _test

    {

         char i; 

         int j;

         char k;

    }Test;

    int main()

    {

         Test *p = 0;

         printf("%p\n", &(p->k));

    }

    自己分析:这里使用的是一个利用编译器技术的小技巧,即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址,然后根据结构体的首地址

    0,从而得出该偏移地址就是该结构体变量在该结构体中的偏移,即:该结构体成员变量距离结构体首的距离。在offsetof()中,这个member成

    员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结构,offsetof(type,member)是一个常

    量,list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。

    ---------------------typeof()--------------------

    --->我开始不懂,源代码中也查不到,网上发贴请教。由liubo1977在www.linuxforum.net上的Linux内核技术论坛上解答,QQ:84915771 

    答复:

    unsigned int i; 

    typeof(i) x; 

    x=100; 

    printf("x:%d\n",x); 

    typeof() 是 gcc 的扩展,和 sizeof() 类似。

    ------------------------

    container_of()和offsetof()并不仅用于链表操作,这里最有趣的地方是 ((type

    *)0)->member,它将0地址强制 "转换" 为 type 结构的指针,再访问到 type 结构中的 member 成员。在

    container_of 宏中,它用来给 typeof() 提供参数,以获得 member 成员的数据类型; 

    ---------------container_of()--------------------

    container_of() 来自\linux\kernel.h

    内核中的注释:container_of - cast a member of a tructure 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 truct.

    #define container_of(ptr, type, member) ({                        \

            const typeof( ((type *)0)->member ) *__mptr = (ptr);        \

            (type *)( (char *)__mptr - offsetof(type,member) );})

    自己分析:

    1.(type

    *)0->member为设计一个type类型的结构体,起始地址为0,编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变

    量的偏移地址,由于结构体起始地址为0,所以此结构体成员变量的偏移地址就等于其成员变量在结构体内的距离结构体开始部分的偏移量。即:&

    (type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为:(size_t)(&

    ((type

    *)0)->member)经过size_t的强制类型转换后,其数值为结构体内的偏移量。该偏移量这里由offsetof()求出。

    2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr指针.ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针,其指向ptr所指向的变量处。

    3.(char *)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member)

    )用来求出结构体起始地址(为char *型指针),然后(type *)( (char *)__mptr -

    offsetof(type,member) )在(type *)作用下进行将字节型的结构体起始指针转换为type *型的结构体起始指针。

    这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。

    -----------茶余饭后一点小资料----------------------

    学辛苦了,看点收集的小东东:

    以下文字摘自微软中国研究院前任院长,现微软高级副总裁李开复先生《一封写给中国学生的信》:

    “我的老板

    Rick室Rashid博士是目前微软公司主管研究的高级副总裁,他已经功成名就,却始终保持一颗学习和进取的心。现在,他每年仍然编写大约50,000

    行程序。他认为:用最新的技术编程可以使他保持对计算机最前沿技术的敏感,使自己能够不断进步。今天,有些博士生带低年级的本科生和硕士生做项目,就自满

    地认为自己已经没有必要再编程了。其实,这样的做法是很不明智的。

    --------------arch-v32\cache.h------------------

    #ifndef _ASM_CRIS_ARCH_CACHE_H

    #define _ASM_CRIS_ARCH_CACHE_H

    /* A cache-line is 32 bytes. */

    #define L1_CACHE_BYTES 32

    #define L1_CACHE_SHIFT 5

    #define L1_CACHE_SHIFT_MAX 5

    #endif /* _ASM_CRIS_ARCH_CACHE_H */

    分析:

    也可用#define L1_CACHE_BYTES  (1UL预取读

            prefetchw(x)        - prefetches the cacheline at "x" for write-->预取写

            spin_lock_prefetch(x) - prefectches the spinlock *x for taking

            

            there is also PREFETCH_STRIDE which is the architecure-prefered 

            "lookahead" size for prefetching streamed operations.

            PREFETCH_STRIDE用于预取操作流。

            These cannot be do{}while(0) macros.

    */

    #define _LINUX_PREFETCH_H

    #ifndef ARCH_HAS_PREFETCH

    static inline void prefetch(const void *x) {;}

    #endif

    #ifndef ARCH_HAS_PREFETCHW

    static inline void prefetchw(const void *x) {;}

    #endif

    #ifndef ARCH_HAS_SPINLOCK_PREFETCH

    #define spin_lock_prefetch(x) prefetchw(x)

    #endif

    #ifndef PREFETCH_STRIDE

    #define PREFETCH_STRIDE (4*L1_CACHE_BYTES)

    #endif  //PREFETCH_STRIDE

    static inline void prefetch_range(void *addr, size_t len)

    {

            #ifdef ARCH_HAS_PREFETCH

                    char *cp;

                    char *end = addr + len;

                    for (cp = addr; cp next; prefetch(pos->next), pos != (head); \

                    pos = pos->next)

    ----------------__list_for_each()-----------------

    Linux Kernel 2.6.14中的解释中的精华部分:

    /**

    * This variant differs from list_for_each() in that it's the

    simplest possible list iteration code, no prefetching is done.Use this

    for code that knows the list to be very short (empty or 1 entry) most

    of the time.

    */

    #define __list_for_each(pos, head) \

            for (pos = (head)->next; pos != (head); pos = pos->next)

    list_for_each()有prefetch()用于复杂的表的遍历,而__list_for_each()无prefetch()用于简单的表的遍历.

    注意:head在宏定义中用了括号将其括起来.

    ----------------list_for_each_prev()-------------

    #define list_for_each_prev(pos, head) \

            for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \

                    pos = pos->prev)

    解释类似上面的list_for_each()。

    ----------------list_for_each_safe()--------------

    内核中解释的精华部分:

    /*

    * list_for_each_safe        -        iterate over a list safe against removal of list entry

      */

    #define list_for_each_safe(pos, n, head) \

            for (pos = (head)->next, n = pos->next; pos != (head); \

                    pos = n, n = pos->next)

    这是说你可以边遍历边删除,这就叫safe。十分精彩。刚开始时,我也一直不理解safe的意思,后来在www.linuxforum.net论坛上搜索list_for_each_safe找到了解答。

    ----------------list_entry()--------------------

    #define list_entry(ptr, type, member) \

            container_of(ptr, type, member)

    分析:

    list_entry()函数用于将指向某链表结点成员的指针调整到该链表的开始处,并指针转换为该链表结点的类型。

    -------------list_for_each_entry()---------------

    #define list_for_each_entry(pos, head, member)                                \

            for (pos = list_entry((head)->next, t        ypeof(*pos), member);        \

                 prefetch(pos->member.next), &pos->member != (head);         \

                 pos = list_entry(pos->member.next, typeof(*pos), member))

    分析:

    1.杨沙洲--国防科技大学计算机学院--2004年8月指出: 

    大多数情况下,遍历链表的时候都需要获得链表节点数据项,也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏。

    2.这是用于嵌套的结构体中的宏:(这个程序例子来自:《Linux内核分析及编程》作者:倪继利 电子工业出版社)

    struct example_struct

    {

            struct list_head list;

            int priority;

            ... //其他结构体成员

    };

    struct example_struct *node = list_entry(ptr,struct example_struct,list);

    自己分析:对比list_entry(ptr,type,member)可知有以下结果:

    其中list相当于member成员,struct

    example_struct相当于type成员,ptr相当于ptr成员。而list{}成员嵌套于example_struct{}里面。ptr指向

    example_struct{}中的list成员变量的。在list_entry()作用下,将ptr指针回转指向struct

    example_struct{}结构体的开始处。

    3.pos当指向外层结构体,比如指向struct

    example_struct{}的结点,最开始时候,pos当指向第一个结点。而head开始时候也是指向第一个外层结点的里面的这个内嵌的链表结构体

    struct list_head{},(head)->next则指向后继的一个外层结点的内嵌的链表结点struct

    list_head{} list。member即是指出该list为其内嵌的结点。

    思路:用pos指向外层结构体的结点,用head指向内层嵌入的结构体的结点。用(head)->next,pos->

    member.next(即:ptr->list.next)来在内嵌的结构体结点链表中遍历。每遍历一个结点,就用list_entry()将内

    嵌的pos->member.next指针回转为指向该结点外层结构体起始处的指针,并将指针进行指针类型转换为外层结构体型pos。&

    pos->member! =

    (head)用pos外层指针引用member即:list成员,与内层嵌入的链表之头结点比较来为循环结束条件。

    -------------list_for_each_entry_reverse()-------

    #define list_for_each_entry_reverse(pos, head, member)                        \

            for (pos = list_entry((head)->prev, typeof(*pos), m+ember);        \

                 prefetch(pos->member.prev), &pos->member != (head);         \

                 pos = list_entry(pos->member.prev, typeof(*pos), member))

    分析类似上面。

    ---------------list_prepare_entry()---------------

    1.函数背景:来自杨沙洲.国防科技大学计算机学院.2004年8月.www.linuxforum.net Linux 内核技术论坛:

    杨在贴子中指出:如果遍历不是从链表头开始,而是从已知的某个pos结点开始,则可以使用

    list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求,即经过一系列计算后,如果pos

    有值,则从pos开始遍历,如果没有,则从链表头开始,为此,Linux专门提供了一个list_prepare_entry(pos,head,

    member)宏,将它的返回值作为list_for_each_entry_continue()的pos参数,就可以满足这一要求。

    2.内核中的list_prepare_entry()的注释及代码:

    /**

    * list_prepare_entry - prepare a pos entry for use as a start point in

    * @pos:        the type * to use as a start point

    * @head:        the head of the list

    * @member:        the name of the list_struct within the struct.

    */

    内核源代码:

    #define list_prepare_entry(pos, head, member) \

            ((pos) ? : list_entry(head, typeof(*pos), member))

    分析:

    :前面是个空值,即:若pos不为空,则pos为其自身。等效于:

    (pos)? (pos): list_entry(head,typeof(*pos),member)

    注意内核格式::前后都加了空格。

    ------------list_for_each_entry_continue()--------

    3.内核中的list_for_each_entry_continue()的注释及代码:

    /**

    * list_for_each_entry_continue -        iterate over list of given type

    *continuing after existing point

    * @pos:        the type * to use as a loop counter.

    * @head:        the head for your list.

    * @member:        the name of the list_struct within the struct.

    */

    内核源代码:

    #define list_for_each_entry_continue(pos, head, member)                 \

            for (pos = list_entry(pos->member.next, typeof(*pos), member);        \

                 prefetch(pos->member.next), &pos->member != (head);        \

                 pos = list_entry(pos->member.next, typeof(*pos), member))

    分析见list_prepare_entry()中的函数背景。

    -------------list_for_each_entry_safe()-----------

    1.函数背景:来自杨沙洲.国防科技大学计算机学院.2004年8月.www.linuxforum.net Linux 内核技术论坛:

    杨在贴子中指出:list_for_each_entry_safe(pos, n, head,member),它们要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。 

    2.内核中的注释与源代码:

    /**

    * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry

    * @pos:        the type * to use as a loop counter.

    * @n:                another type * to use as temporary storage

    * @head:        the head for your list.

    * @member:        the name of the list_struct within the struct.

    */

    #define list_for_each_entry_safe(pos, n, head, member)                        \

            for (pos = list_entry((head)->next, typeof(*pos), member),        \

                    n = list_entry(pos->member.next, typeof(*pos), member);        \

                 &pos->member != (head);                                         \

                 pos = n, n = list_entry(n->member.next, typeof(*n), member))

    分析类似上面。容易明白。

    --------list_for_each_entry_safe_continue()-------

    #define list_for_each_entry_safe_continue(pos, n, head, member)                 \

            for (pos = list_entry(pos->member.next, typeof(*pos), member),                 \

                    n = list_entry(pos->member.next, typeof(*pos), member);                \

                 &pos->member != (head);                                                \

                 pos = n, n = list_entry(n->member.next, typeof(*n), member))

    ------------------------------------------------

    Linux内核中的双循环链表

    在传统的双循环链表实现中,如果创建某种数据结构的双循环链表,通常采用的办法是在这个数据结构的类型定义中加入两个(指向该类型对象的)指针next和prev。例如:

    typedef struct foo {

        …

        struct foo *prev;

        struct foo *next;

        …

    } foo_t;

    这里给出了对应的节点结构、空的双循环链表和非空的双循环链表示意图。

    Linux内核中双循环链表实现

    linux内核中,有大量的数据结构需要用到双循环链表,例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式,需要为这些数据结构维护各自的链表,并且为每个链表都要设计插入、删除等操作函数。(由于用来维持链表的next和prev指针指向对应类型的对象,因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。)

    Linux源代码树的include/linux/list.h文件中,采用了一种(数据结构)类型无关的双循环链表实现方式。其思想是将指针prev和next从具体的数据结构中提取处理构成一种通用的"双链表"数据结构list_head,而 list_head被作为一个成员嵌入到要拉链的数据结构(被称为宿主数据结构)中。这样,只需要一套通用的链表操作函数就可以将list_head成员作为"连接件",把宿主数据结构链接起来。如下图所示:

    Linux内核中的双循环链表实现方式下:

    1. 链表结构作为一个成员嵌入到宿主数据结构内; 

    2. 可以将链表结构放在宿主结构内的任何地方;

    3. 可以为链表结构取任何名字; 

    4. 宿主结构可以有多个链表结构。

    下面我们将基于Linux 2.4.21分析Linux内核双循环链表的实现及应用。

    声明和初始化

    链表结构定义如下:

    struct list_head {

        struct list_head *next, *prev;

    };

    我们可以用struct list_head声明一个链表节点。需要注意的是,Linux 的每个双循环链表都有一个链表头,链表头也是一个节点,只不过它不嵌入到宿主数据结构中,即不能利用链表头定位到对应的宿主结构。

    我们可以调用INIT_LIST_HEAD()宏初始化链表节点,将next和prev指针都指向其自身。如果这个节点是链表头,我们就构造了一个空的双循环链表。

    #define INIT_LIST_HEAD(ptr) do { \

        (ptr)->next = (ptr); (ptr)->prev = (ptr); \

    } while (0)

    LIST_HEAD()宏可以同时完成声明链表头,并初始化这个双循环链表为空。

    #define LIST_HEAD_INIT(name) { &(name), &(name) }

    #define LIST_HEAD(name) \

        struct list_head name = LIST_HEAD_INIT(name)

    添加

    在上面的设计下,所有链表(包括添加、删除、移动和拼接等)操作都是针对数据结构list_head进行的。

    对链表的添加操作有两种:表头添加和表尾添加。注意到,Linux双循环链表中有一个链表头,表头添加是指添加到链表头之后,而表尾添加则是添加到链表头的prev所指链表节点(如果是空链表,这个链表节点为链表头自身)之后。Linux为此提供了两个接口: 

    static inline void list_add(struct list_head *new, struct list_head *head);

    static inline void list_add_tail(struct list_head *new, struct list_head *head);

    具体添加是调用__list_add完成的,我们不予赘述。

    static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next);

    删除

    如果要从链表中删除某个链表节点,则可以调用list_del或list_del_init。

    static inline void list_del(struct list_head *entry);

    static inline void list_del_init(struct list_head *entry);

    两者都调用__list_del将节点从链表中取出,之后,list_del将要删除节点的prev和next指针均设为NULL,保证不可通过该节点进行访问;而list_del则调用LIST_INIT_HEAD()把被删除节点为作为链表头构建一个新的双循环链表。

    需要注意的是,上述操作均仅仅是把节点从双循环链表中拿掉,用户需要自己负责释放该节点对应的数据结构所占用的空间,而这个空间本来就是用户分配的。

    移动

    Linux还提供了两个移动操作:list_move和list_move_tail。前者将指定节点从其所在链表中取出,添加到另一个链表的头部。而后者在取出后添加到新链表的尾部。

    static inline void list_move(struct list_head *list, struct list_head *head);

    static inline void list_move_tail(struct list_head *list, struct list_head *head);

    拼接

    Linux还支持两个链表的拼接,具体函数是list_splice和list_splice_init:

    static inline void list_splice(struct list_head *list, struct list_head *head);

    static inline void list_splice_init(struct list_head *list, struct list_head *head);

    两个函数都将一个链表的所有节点依次添加到另一个链表的头部,新链表将一原链表的第一个节点为首节点,而尾节点不变。区别在于:前者,原链表头的next和prev仍然指向原来的地方;而后者调用INIT_LIST_HEAD()为原链表头初始化一个空的双循环链表。

    获取宿主对象指针

    如果需要有某种数据结构的队列,就在这种数据结构定义内部放上一个list_head数据结构。例如,建立数据结构foo链表的方式是,在foo的定义中,嵌入了一个list_head成员list。这里foo就是所指的"宿主"。

    typedef struct foo {

        …

        struct list_head list;

        …

    };

    上述的添加、删除、移动和合并都是针对list进行的,后面要讲到的遍历操作也基于list。但是,如何通过list_head成员访问到宿主结构项呢?毕竟list_head不过是个连接件,而我们需要的是一个"特定"的数据结构链表。

    Linux 为此提供了list_entry()宏,获取当前list_head链表节点所在的宿主结构项。第一个参数为当前list_head节点的指针,即指向宿主结构项的list_head成员。第二个参数是宿主数据结构的定义类型。第三个参数为宿主结构类型定义中list_head成员名。

    #define list_entry(ptr, type, member) \

        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

    例如,我们要访问foo链表(链表头为head)中首个元素,则如此调用:

    list_entry(head->next, struct foo, list);

    经过C预处理的文字替换,这一行的内容就成为:

    ((struct foo *)((char *)(head->next) - (unsigned long)(&((struct page *)0)->list)))

    获取宿主对象指针的原理如上图所示。我们考虑list_head成员member相对于宿主结构(类型为type)起始地址的偏移量。对于所有该类型的宿主对象,这个偏移量是固定的。并且可以在假设宿主对象地址值为0,通过返回member成员的地址获得,即等于(unsigned long)(&((type *)0)->member)。这样,将当前宿主对象的"连接件"地址(ptr)减去这个偏移量,得到宿主对象地址,再将它转换为宿主数据结构类型的指针。

    需要重申的是,链表头没有被嵌入到宿主对象中,因此对链表头执行宿主对象指针获取操作是没有意义的。

    遍历

    遍历是双循环链表的基本操作,为此Linux定义了一些宏。

    list_for_each 对遍历链表中的所有list_head节点,不涉及到对宿主结构的处理。list_for_each实际是一个 for 循环,利用传入的指向list_head结构的指针作为循环变量,从链表头开始(并跳过链表头),逐项向后移动指针,直至又回到链表头。为提高遍历速度,还使用了预取。

    #define list_for_each(pos, head) \

        for (pos = (head)->next, prefetch(pos->next); pos != (head); \

            pos = pos->next, prefetch(pos->next))

    如果需要反向遍历list_head链表,可以使用list_for_each_prev宏。

    #define list_for_each_prev(pos, head) \

        for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \

            pos = pos->prev, prefetch(pos->prev))

    上述两个操作都是通过移动(指向list_head结构的)指针来达到遍历的目的。但如果在遍历过程中,包含有删除或移动当前链接节点的操作,由于这些操作会修改遍历指针,这样会导致遍历的中断。这种情况下,必须使用list_for_each_safe宏,在操作之前将遍历指针缓存下来:

    #define list_for_each_safe(pos, n, head) \

        for (pos = (head)->next, n = pos->next; pos != (head); \

            pos = n, n = pos->next)

    如果只提供对list_head结构的遍历操作是远远不够的,我们希望实现的是对宿主结构的遍历,即在遍历时直接获得当前链表节点所在的宿主结构项,而不是每次要同时调用list_for_each和list_entry。对此,Linux提供了list_for_each_entry()宏,第一个参数为传入的遍历指针,指向宿主数据结构,第二个参数为链表头,为list_head结构,第三个参数为list_head结构在宿主结构中的成员名。

    #define list_for_each_entry(pos, head, member)    \

        for (pos = list_entry((head)->next, typeof(*pos), member), \

            prefetch(pos->member.next);   \

           &pos->member != (head);      \

           pos = list_entry(pos->member.next, typeof(*pos), member), \

           prefetch(pos->member.next))

    如何使用Linux中的双循环链表

    本文例子来自http://isis.poly.edu/kulesh/stuff/src/klist/,只是对其中注释部分作了翻译。

    #include

    #include

    #include "list.h"

    struct kool_list{

        int to;

        struct list_head list;

        int from;

    };

    int main(int argc, char **argv){

        struct kool_list *tmp;

        struct list_head *pos, *q;

        unsigned int i;

        struct kool_list mylist;

        INIT_LIST_HEAD(&mylist.list);

        /* 您也可以使用宏LIST_HEAD(mylist)来声明并初始化这个链表 */

        /*向链表中添加元素*/

        for(i=5; i!=0; --i){

            tmp= (struct kool_list *)malloc(sizeof(struct kool_list));

      

            /*INIT_LIST_HEAD(&tmp->list); 调用这个函数将初始化一个动态分配的list_head。也可以不调用它,因为在后面调用的add_list()中将设置next和prev域。*/

            printf("enter to and from:");

            scanf("%d %d", &tmp->to, &tmp->from);

            /*将tmp添加到mylist链表中*/

            list_add(&(tmp->list), &(mylist.list));

            /*也可以使用list_add_tail()将新元素添加到链表的尾部。*/

        }

        printf("\n");

        /*现在我们得到了数据结构struct kool_list的一个循环链表,我们将遍历这个链表,并打印其中的元素。*/

        /*list_for_each()定义了一个for循环宏,第一个参数用作for循环的计数器,换句话说,在整个循环过程中它指向了当前项的list_head。第二个参数是指向链表的指针,在宏中保持不变。*/

        printf("traversing the list using list_for_each()\n");

        list_for_each(pos, &mylist.list){

            /* 此刻:pos->next指向了下一项的list变量,而pos->prev指向上一项的list变量。而每项都是struct kool_list类型。但是,我们需要访问的是这些项,而不是项中的list变量。因此需要调用list_entry()宏。*/

            tmp= list_entry(pos, struct kool_list, list);

            /* 给定指向struct list_head的指针,它所属的宿主数据结构的类型,以及它在宿主数据结构中的名称,list_entry返回指向宿主数据结构的指针。例如,在上面一行, list_entry()返回指向pos所属struct kool_list项的指针。*/

            printf("to= %d from= %d\n", tmp->to, tmp->from);

        }

        printf("\n");

        /* 因为这是一个循环链表,我们也可以向前遍历。只需要将list_for_each替换为list_for_each_prev。我们也可以使用list_for_each_entry()遍历链表,在给定类型的项间进行循环。例如:*/

        printf("traversing the list using list_for_each_entry()\n");

        list_for_each_entry(tmp, &mylist.list, list)

        printf("to= %d from= %d\n", tmp->to, tmp->from);

        printf("\n");

     

        /*下面将释放这些项。因为我们调用list_del()从链表中删除各项,因此需要使用list_for_each()宏的"安全"版本,即 list_for_each_safe()。务必注意,如果在循环中有删除项(或把项从一个链表移动到另一个链表)的操作,必须使用这个宏。*/

        printf("deleting the list using list_for_each_safe()\n");

        list_for_each_safe(pos, q, &mylist.list){

            tmp= list_entry(pos, struct kool_list, list);

            printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);

            list_del(pos);

            free(tmp);

        }

        return 0;

    }

    注意:上述代码在使用gcc编译时需要加上__KERNEL__定义。

    hlist哈希链表 

    hlist哈希链表是内核中常用的一个数据结构,由于它不同于普通的链表,所以这里对hlist哈希链表进行一下分析,希望对大家有所帮助。

    include/Linux/list.h中有list链表与hlist哈希链表结构的定义,下面都列出它们的定义,可以对比一下:

    struct list_head {

    struct list_head *next, *prev;

    };

    struct hlist_head {

    struct hlist_node *first;

    };

    struct hlist_node {

    struct hlist_node *next, **pprev;

    };

    头(next,prev)的双链表对于Hash表来说“过于浪费”,因而另行设计了一套Hash表专用的hlist数据结构——单指针表头双循环 链表,hlist的表头仅有一个指向首节点的指针,而没有指向尾节点的指针,这样在可能是海量的Hash表中存储的表头就能减少一半的空间消耗。

    pprev 因为hlist不是一个完整的循环链表而不得不使用。在list中,表头和节点是同一个数据结构,直接用prev没问题;在hlist中,表头 没有prev,也没有next,只有一个first。为了能统一地修改表头的first指针,即表头的first指针必须修改指向新插入的节点, hlist就设计了pprev。hlist节点的pprev不再是指向前一个节点的指针,而是指向前一个节点(可能是表头)中的next(对于表头则是 first)指针(struct list_head **pprev),从而在表头插入的操作可以通过一致的“*(node->pprev)”访问和修改前节点的next(或first)指针。

    注:pprev是指向前一个节点中的next指针,next是指向hlist_node的指针,所以pprev是一个指向hlist_node的指针的指针。

     

     

    注意:

    pprev 可以理解成向list的prev一样,是一个指向hlist_node的指针,又由于hlist_node的第一个元素next是一个指向 hlist_node的指针,pprev也是一个指向next的指针,即pprev是一个指向hlist_node的指针的指针。

    struct hlist_node Prev;

    struct hlist_node *pprev = (struct hlist_node *) Prev = (struct hlist_node *) (struct hlist_node * next) = struct hlist_node ** next;

    下面是hlist中常用的几个宏:

    #define HLIST_HEAD_INIT { .first = NULL }

    #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }

    #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

    #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

    下面只列出hlist_add_before操作函数,其他hlist链表操作函数操作方法类似。这个函数中的参数next不能为空。它在next前面加入了n节点。函数的实现与list中对应函数类似。

    static inline void __hlist_del(struct hlist_node *n)

    {

    struct hlist_node *next = n->next;

    struct hlist_node **pprev = n->pprev;

    *pprev = next;

    if (next)

    next->pprev = pprev;

    }

    static inline void hlist_add_before(struct hlist_node *n,struct hlist_node *next)

    {

    n->pprev = next->pprev;

    n->next = next;

    next->pprev = &n->next;

    *(n->pprev) = n;

    }

    #ifndef __DLIST_H
    #define __DLIST_H
    
    /* This file is from Linux Kernel (include/linux/list.h)
    * and modified by simply removing hardware prefetching of list items.
    * Here by copyright, credits attributed to wherever they belong.
    * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu)
    */
    
    /*
    * Simple doubly linked list implementation.
    *
    * Some of the internal functions (“__xxx”) are useful when
    * manipulating whole lists rather than single entries, as
    * sometimes we already know the next/prev entries and we can
    * generate better code by using them directly rather than
    * using the generic single-entry routines.
    */
    /**
     * 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 offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    
    #define container_of(ptr, type, member) ({			\
            const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
            (type *)( (char *)__mptr - offsetof(type,member) );})
    /*
     * These are non-NULL pointers that will result in page faults
     * under normal circumstances, used to verify that nobody uses
     * non-initialized list entries.
     */
    #define LIST_POISON1  ((void *) 0x00100100)
    #define LIST_POISON2  ((void *) 0x00200)
    
    struct list_head {
    	struct list_head *next, *prev;
    };
    
    
    
    // 定义一个叫做name的小结构体,并且初始化
    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
    #define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
    
    
    
    // 将一个由ptr指向的小结构体,初始化(常用)
    #define INIT_LIST_HEAD(ptr) do { \
    	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
    } while (0)
    
    
    
    
    /*
    * Insert a new entry between two known consecutive entries.
    *
    * This is only for internal list manipulation where we know
    * the prev/next entries already!
    */
    static inline void __list_add(struct list_head *new,
    				struct list_head *prev,
    				struct list_head *next)
    {
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	prev->next = new;
    }
    
    /**
    * list_add – add a new entry
    * @new: new entry to be added
    * @head: list head to add it after
    *
    * Insert a new entry after the specified head.
    * This is good for implementing stacks.
    */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }
    
    /**
    * list_add_tail – add a new entry
    * @new: new entry to be added
    * @head: list head to add it before
    *
    * Insert a new entry before the specified head.
    * This is useful for implementing queues.
    */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }
    
    /*
    * Delete a list entry by making the prev/next entries
    * point to each other.
    *
    * This is only for internal list manipulation where we know
    * the prev/next entries already!
    */
    static inline void __list_del(struct list_head *prev, struct list_head *next)
    {
    	next->prev = prev;
    	prev->next = next;
    }
    
    /**
    * list_del – deletes entry from list.
    * @entry: the element to delete from the list.
    * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
    */
    static inline void list_del(struct list_head *entry)
    {
    	__list_del(entry->prev, entry->next);
    	entry->next = (void *) 0;
    	entry->prev = (void *) 0;
    }
    
    /**
    * list_del_init – deletes entry from list and reinitialize it.
    * @entry: the element to delete from the list.
    */
    static inline void list_del_init(struct list_head *entry)
    {
    	__list_del(entry->prev, entry->next);
    	INIT_LIST_HEAD(entry);
    }
    
    /**
    * list_move – delete from one list and add as another’s head
    * @list: the entry to move
    * @head: the head that will precede our entry
    */
    static inline void list_move(struct list_head *list,
    				struct list_head *head)
    {
    	__list_del(list->prev, list->next);
    	list_add(list, head);
    }
    
    
    
    
    // 将节点list移动到head的前面
    /**
    * list_move_tail – delete from one list and add as another’s tail
    * @list: the entry to move
    * @head: the head that will follow our entry
    */
    static inline void list_move_tail(struct list_head *list,
    					struct list_head *head)
    {
    	__list_del(list->prev, list->next);
    	list_add_tail(list, head);
    }
    
    /**
    * list_empty – tests whether a list is empty
    * @head: the list to test.
    */
    static inline int list_empty(struct list_head *head)
    {
    	return head->next == head;
    }
    
    static inline void __list_splice(struct list_head *list,
    					struct list_head *head)
    {
    	struct list_head *first = list->next;
    	struct list_head *last = list->prev;
    	struct list_head *at = head->next;
    
    	first->prev = head;
    	head->next = first;
    
    	last->next = at;
    	at->prev = last;
    }
    
    /**
    * list_splice – join two lists
    * @list: the new list to add.
    * @head: the place to add it in the first list.
    */
    static inline void list_splice(struct list_head *list, struct list_head *head)
    {
    if (!list_empty(list))
    __list_splice(list, head);
    }
    
    /**
    * list_splice_init – join two lists and reinitialise the emptied list.
    * @list: the new list to add.
    * @head: the place to add it in the first list.
    *
    * The list at @list is reinitialised
    */
    static inline void list_splice_init(struct list_head *list,
    struct list_head *head)
    {
    if (!list_empty(list)) {
    __list_splice(list, head);
    INIT_LIST_HEAD(list);
    }
    }
    
    
    
    
    // 由小指针,获取大指针
    /**
    * 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) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
    
    /**
    * list_for_each    -    iterate over a list
    * @pos:    the &struct list_head to use as a loop counter.
    * @head:    the head for your list.
    */
    #define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); \
    pos = pos->next)
    /**
    * list_for_each_prev    -    iterate over a list backwards
    * @pos:    the &struct list_head to use as a loop counter.
    * @head:    the head for your list.
    */
    #define list_for_each_prev(pos, head) \
    for (pos = (head)->prev; pos != (head); \
    pos = pos->prev)
    
    /**
    * list_for_each_safe    -    iterate over a list safe against removal of list entry
    * @pos:    the &struct list_head to use as a loop counter.
    * @n:        another &struct list_head to use as temporary storage
    * @head:    the head for your list.
    */
    #define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
    pos = n, n = pos->next)
    
    /**
    * list_for_each_entry    -    iterate over list of given type
    * @pos:    the type * to use as a loop counter.
    * @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))
    
    /**
    * list_for_each_entry_safe – iterate over list of given type safe against removal of list entry
    * @pos:    the type * to use as a loop counter.
    * @n:        another type * to use as temporary storage
    * @head:    the head for your list.
    * @member:    the name of the list_struct within the struct.
    */
    #define list_for_each_entry_safe(pos, n, head, member)            \
    for (pos = list_entry((head)->next, typeof(*pos), member),    \
    n = list_entry(pos->member.next, typeof(*pos), member);    \
    &pos->member != (head);                     \
    pos = n, n = list_entry(n->member.next, typeof(*n), member))
    
    #endif
    

    #define hlist_entry(ptr, type, member) container_of(ptr,type,member)

    #define hlist_for_each(pos, head) \

    for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \

    pos = pos->next)

     


    展开全文
  • 遍历进程链表

    千次阅读 2012-10-07 17:54:59
    我们知道,一个进程是由进程控制块(PCB),代码段和数据段组成的;并且,OS通常是通过PCB来感知一个...多个进程则常常使用双链表等来进行组织。比如可运行状态的进程组成可运行队列,等待状态的进程组成等待队列等。
  • 早先的linux版本把所有的可运行进程都放在同一个运行队列中(链表),由于维持这个链表按优先级... 提高调度运行速度的方法是建立多个可运行进程链表,每种进程优先权对应一个不同的链表。如果某个进程的优先权等于
  • linux链表函数问题

    2011-12-08 13:59:47
    [ 标签:linux,链表函数 ] 在学习内核链表时,有下列函数希望比较懂的人来回答以下这些函数及结构体的作用struct list_head *ptr,这个定义定义的是什么?是链表头指针ptr吗?那接上面的一句是INIT_LIST_HEAD...
  • 为了减少重复代码的数量,内核开发者建立了一套标准...该链表文件实现在内核源码树下include/linux/list.h 一: 链表数据结构的定义   struct list_head {  struct list_head *next, *prev; };  list_h
  • 编写简单的内核模块以及实现linux简单链表功能 什么是模块 模块是具有独立功能的程序,它可以被单独编译,但不能独立运行。它在运行时被链接到内核作为内核的一部分在内核空间运行,这与运行在用户空间的进程是...
  • 例说Linux内核链表(一)

    千次阅读 2014-10-13 23:59:03
    在include/linux/list.h文件中用C实现了一个好用的循环链表。它是有效而且易于操作的,否则它也不会被内核使用(译者注:在kernel中大量的使用了循环双链表结构,比如在在进程描述符实体中我们就可以看到很多struct ...
  • Linux系统简介 Linux系统的结构及特点 Linux系统的结构图如下图所示: ...Linux进程管理的系统调用包括:进程的创建、调度、中止、等待等。 Linux支持内存管理控制器MMU,使用虚拟内存管理机制。虚拟...
  • 哈希表的主要作用是根据进程的pid可以快速地找到对应的进程,但它没有反映进程创建的顺序,也无法反映进程之间的亲属关系,因此引入进程双向循环链表。 union task_union {  struct task_struct task;  ...
  • 为了较快的从给定的pid值得到相应的宿主结构(进程描述符)指针,内核采用了pid哈希链表结构。 首先,以下的问题要理解: 1)为什么pid哈希链表只定义2048或者4096项(根据你的内存大小确定)?直接定义为pid最大...
  • 日期 内核版本 架构 作者 GitHub CSDN 2016-05-12 Linux-4.6 ...Linux进程的退出linux下进程退出的方式正常退出 从main函数返回return 调用exit 调用_exit 异常退出 调用abort 由信号终止 _exit
  • linux链表和哈希表应用浅析一

    千次阅读 2016-01-31 16:01:25
    如果每一个数据结构描述一个物体或者发生的事件的单一的实例,比如一个进程或一个网络设备,核心必须能够找出所有的实例。在链表中,根指针包括第一个数据结构或单元的地址,列表中的每一个数据结构包含指向列表下一...
  • Linux进程ID号--Linux进程的管理与调度(三)

    万次阅读 多人点赞 2016-05-12 13:31:31
    日期 内核版本 架构 作者 GitHub CSDN 2016-05-12 ...Linux 内核使用 task_struct 数据结构来关联所有与进程有关的数据和结构,Linux 内核所有涉及到进程和程序的所有算法都是围绕该数据结构建立的,是内
  • 日期 内核版本 ... Linux进程管理与调度 1 前景回顾1.1 进程调度内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间,
  • Linux进程调度器概述--Linux进程的管理与调度(十五)

    万次阅读 多人点赞 2016-06-17 14:50:16
    日期 ... Linux进程管理与调度 内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为
  • Linux进程模型

    千次阅读 2015-01-31 09:52:25
    -------------原文链接:http://www.cnblogs.com/biyeymyhjob/archive/2012/08/01/2617884.html-----------------------------------Linux进程通过一个task_struct结构体描述,在linux/sched.h中定义,通过理解该结构...
  • Linux进程管理(一)进程数据结构

    千次阅读 2019-10-27 16:59:46
    文章目录Linux进程管理(一)进程数据结构双向链表任务ID信号处理进程状态进程调度运行统计信息进程亲缘关系内存管理文件与文件系统进程内核栈栈结构current宏 Linux内核中使用 task_struct 结构来表示一个进程,这...
  • Linux-进程管理与调度 进程是处于执行期的程序以及它所管理的资源(如打开的文件、挂起的信号、进程状态、地址空间等等)的总称。注意,程序并不是进程,实际上两个或多个进程不仅有可能执行同一程序
  • 前言 数据结构中的链表在任何教程里面都是放在最前面讲解,这不仅仅体现它的重要性,而且说明了它的基础性。...向左,向右,向前看,Linux要拐几个弯才来遇见(《遇见》),后来,终于在Linux中明白,有些地方
  • 日期 内核版本 ... Linux进程管理与调度 1 前言1.1 进程调度内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创
  • Linux进程调度CFS调度器 日期 内核版本 架构 作者 GitHub CSDN 2016-06-14 Linux-4.6 X86 & arm gatieme LinuxDeviceDrivers Linux进程管理与调度 1 前景回顾1.1 进程调度内存中保存了对每个进程的唯一...
  • Linux进程调度与进程结构

    千次阅读 2014-05-28 15:06:56
    Linux进程调度  一、调度策略类型 Linux内核的进程是通过双链表的方式将进程的struct  task_struct结构连接在一起, task_struct结构里面包含了与一个进程相关的全部信息(比如进程的状态、优先级、进程的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,410
精华内容 26,564
关键字:

linux进程链表

linux 订阅