内核链表

610阅读　0评论2014-11-14　644924073
分类：LINUX


  1. 一、概述
  2. linux内核采用一套通用的、一般的、可以用到各种数据结构的队列操作，抽象出来成为一种数据结构list_head。
  3. 这种数据结构既可以寄宿在具体的宿主数据结构内部，成为该数据结构的连接件；也可以独立存在而成为一个队列的头。
  4. struct list_head{
  5.     struct list_head *next,*prev;
  6. };

  8. 二、struct list_head结构的操作
  9. 1.初始化
  10. #define INIT_LIST_HEAD（ptr） do { （ptr）->next = （ptr）;（ptr）->prev = （ptr）;} while （0）

  12. 2. 增加节点的函数
  13. static __inline__ void list_add(struct list_head *new, struct list_head *head)
  14. {
  15.     __list_add(new, head, head->next);
  16. }

  18. //这个函数在prev和next间插入一个节点new。
  19. static __inline__ void __list_add(struct list_head * new,struct list_head * prev, struct list_head * next)
  20. {
  21.     next->prev = new;
  22.     new->next = next;
  23.     new->prev = prev;
  24.     prev->next = new;
  25. }

  27. //在head节点的前面插入new节点
  28. static __inline__ void list_add_tail(struct list_head *new, struct list_head *head)
  29. {
  30.     __list_add(new, head->prev, head);
  31. }

  33. 3.从链表中删除节点的函数
  34. static __inline__ void __list_del(struct list_head * prev, struct list_head * next)
  35. {
  36.     next->prev = prev;
  37.     prev->next = next;
  38. }

  40. //从链表中删除entry节点。
  41. static __inline__ void list_del(struct list_head *entry)
  42. {
  43.     __list_del(entry->prev, entry->next);
  44. }

  46. //从链表中删除节点，还把这个节点的向前向后指针都指向自己，即初始化。
  47. static __inline__ void list_del_init(struct list_head *entry)
  48. {
  49.     __list_del(entry->prev, entry->next);
  50.     INIT_LIST_HEAD(entry);
  51. }

  53. 4.判断空链表
  54. static __inline__ int list_empty(struct list_head *head)
  55. {
  56.     return head->next == head;
  57. }

  59. 5.由链表节点到数据项变量
  60. 我们知道，Linux链表中仅保存了数据项结构中list_head成员变量的地址，那么我们如何通过这个list_head成员访问到作为它的所有者的节点数据呢？Linux为此提供了一个list_entry(ptr,type,member)宏，其中ptr是指向该数据中list_head成员的指针，也就是存储在链表中的地址值，type是数据项的类型，member则是数据项类型定义中list_head成员的变量名。

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

  64. 举例：设有如下结构体定义：
  65. typedef struct xxx
  66. {
  67.      ……（结构体中其他域，令其总大小为size1）
  68.      type1 member;
  69.      ……（结构体中其他域）
  70. }type;


  73. 定义变量：
  74.    type a;
  75.    type * b;
  76.    type1 * ptr;
  77. 执行：
  78.    ptr=&(a.member);
  79.    b=list_entry(ptr,type,member);
  80. 则可使b指向a，得到了a的地址。

  82. 如何做到的呢？

  84. 先看&((type *)0)->member：把“0”强制转化为指针类型，则该指针一定指向“0”（数据段基址）。因为指针是“type *”型的，所以可取到以“0”为基地址的一个type型变量member域的地址。那么这个地址也就等于member域到结构体基地址的偏移字节数。
  85.  
  86. 再来看 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))：(char *)(ptr)使得指针的加减操作步长为一字节，(unsigned long)(&((type *)0)->member)等于ptr指向的member到该member所在结构体基地址的偏移字节数。二者一减便得出该结构体的地址。转换为 (type *)型的指针，大功告成。

  88. 6.
  89. #define container_of(ptr, type, member) ({ \
  90.          const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  91.         (type *)( (char *)__mptr - offsetof(type,member) );})


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

  96. 它的作用显而易见，那就是根据一个结构体变量中的一个域成员变量的指针来获取指向整个结构体变量的指针。比如，有一个结构体变量，其定义如下：

  98. struct demo_struct {
  99.      type1 member1;
  100.      type2 member2;
  101.      type3 member3;
  102.      type4 member4;
  103. };
  104. struct demo_struct demo;

  106. 同时，在另一个地方，获得了变量demo中的某一个域成员变量的指针，比如：
  107. type3 *memp = get_member_pointer_from_somewhere();

  109. 此时，如果需要获取指向整个结构体变量的指针，而不仅仅只是其某一个域成员变量的指针，我们就可以这么做：
  110. struct demo_struct *demop = container_of(memp, struct demo_struct, member3);

  112. 首先，我们将container_of(memp, struct demo_struct, type3)根据宏的定义进行展开如下：
  113. struct demo_struct *demop = ({ /
  114.     const typeof( ((struct demo_struct *)0)->member3 ) *__mptr = (memp); /
  115.     (struct demo_struct *)( (char *)__mptr - offsetof(struct demo_struct, member3) );})

  117. 其中，typeof是GNU C对标准C的扩展，它的作用是根据变量获取变量的类型。因此，上述代码中的第2行的作用是首先使用typeof获取结构体域变量member3的类型为 type3，然后定义了一个type3指针类型的临时变量__mptr，并将实际结构体变量中的域变量的指针memp的值赋给临时变量__mptr。

  119. 假设结构体变量demo在实际内存中的位置如下图所示：
  120.      demo
  121.  +-------------+ 0xA000
  122.  | member1 |
  123.  +-------------+ 0xA004
  124.  | member2 |
  125.  | |
  126.  +-------------+ 0xA010
  127.  | member3 |
  128.  | |
  129.  +-------------+ 0xA018
  130.  | member4 |
  131.  +-------------+

  133. 则，在执行了上述代码的第2行之后__mptr的值即为0xA010。

  135. 再看上述代码的第3行，其中需要说明的是offsetof，它定义在include/linux/stddef.h中，其定义如下：

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

  139. 同样，我们将上述的offsetof调用展开，即为：

  141. (struct demo_struct *)( (char *)__mptr - ((size_t) &((struct demo_struct *)0)->member3) );

  143. 可见，offsetof的实现原理就是取结构体中的域成员相对于地址0的偏移地址，也就是域成员变量相对于结构体变量首地址的偏移。

  145. 因此，offsetof(struct demo_struct, member3)调用返回的值就是member3相对于demo变量的偏移。结合上述给出的变量地址分布图可知，offsetof(struct demo_struct, member3)将返回0x10。

  147. 于是，由上述分析可知，此时，__mptr==0xA010，offsetof(struct demo_struct, member3)==0x10。
  148. 因此， (char *)__mptr - ((size_t) &((struct demo_struct *)0)->member3) == 0xA010 - 0x10 == 0xA000，也就是结构体变量demo的首地址（如上图所示）。

上一篇：linux内核命令行解析
下一篇：Linux中"中断睡眠"的实现