Linux链表操作
在研究linux内核自带的dmatest.c驱动程序过程中发现有部分的链接操作，非常迷惑，故在此记录下来一些查阅资料后的心得体会。0 内核链表的特点 普通的链表操作，通常包含数据域和指针域2个内容 如下所示。typedefstruct node{ ElemType data; //数据域 struct node
在研究linux内核自带的dmatest.c驱动程序过程中发现有部分的链接操作，非常迷惑，故在此记录下来一些查阅资料后的心得体会。
0 内核链表的特点
普通的链表操作，通常包含数据域和指针域2个内容 如下所示。
| typedef struct node { ElemType data; //数据域 struct node *next; //指针域 }node, *list; |
而Linux内核定义的链表不带数据域，只需要两个指针完成链表的操作。具有非常高的扩展性、通用性。链表结构定义如下所示。
| struct list_head { struct list_head *next, *prev; }; |
通常有如下格式的定义，通常建议结合containner_of和offset_of获取更大的灵活可操作性。例如下例，可以根据app_info_head的地址找出app_info的起始地址，即一个完整的app_info结构的起始地址。
| typedef struct application_info { uint32_t app_id; uint32_t up_flow; uint32_t down_flow; struct list_head app_info_head; //链表节点 }app_info; |
1 链表操作及实现原理
（1） 初始化链表头结点
初始化的效果是使得前驱和后继指针都是指向头结点的。
这里需要十分注意Init的接口（一开始没有注意到导致错误理解了代码）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) static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } |
所以有如下两种用法。一种是宏扩展，另一种是函数调用。
| //方式一 static struct info_t{ struct list_head channels; }info = { .channels = LIST_HEAD_INIT(info.channels); } //方式二 INIT_LIST_HEAD(&info.channels); |
（2） 插入操作
list_add和list_add_tail分别是插在表头和表尾，但是都是通过__list_add实现，因为内核实现的链表是双向链表，所以head->prev之后就是表尾，而head->next之后就是表头。内核实现如下表所示。
| 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; }
static inline void list_add(struct list_head *new, struct list_head *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); } |
（3） 删除操作
list_del，即删除该节点的前驱和后继节点。需要注意，删除后还需要将待删除节点的前驱和后继分别指向POSITION1和POSITION2。对POSITION1和POSITION2的操作都将引起页故障。
| static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; }
static inline void list_del(struct list_head *entry) { __list_del(entry->prev, entry->next); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } /* * 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 + POISON_POINTER_DELTA) #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA) |
（4） 判断链表
是否为空（list_empty）是否是最后一结点（list_is_last）。
| /** * list_is_last - tests whether @list is the last entry in list @head * @list: the entry to test * @head: the head of the list */ static inline int list_is_last(const struct list_head *list, const struct list_head *head) { return list->next == head; }
/** * list_empty - tests whether a list is empty * @head: the list to test. */ static inline int list_empty(const struct list_head *head) { return head->next == head; } |
（5） 遍历链表
注意list_for_each只是个宏替代。
| /** * 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) \ container_of(ptr, type, member)
/** * list_first_entry - get the first element from a list * @ptr: the list head to take the element from. * @type: the type of the struct this is embedded in. * @member: the name of the list_struct within the struct. * * Note, that list is expected to be not empty. */ #define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member)
/** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each(pos, head) \ for (pos = (head)->next; prefetch(pos->next), pos != (head); \ pos = pos->next) |
在遍历时经常需要使用container_of和offset，例如list_for_each_entry(pos, head, member)，就是遍历head链表，head链表的指针类型为 member（字符串），member是pos类型结构体的一个成员，再基于container_of得到结构体指针。[这点技巧在内核源码中经常能找到]
2 链表使用举例
下面以dmatest.c为例说明。需求：DMA测试程序需要实现多通道，且通道上支持多线程，需要支持能够互相访问。
首先，因为需求互相访问，所以立即想到struct成员变量的方式，如下代码所示。
| struct channel_t{ struct thread_t used[100]; } struct info_t{ struct channel_t used[100]; }; static struct info_t info; |
但是，缺点也很明显，申请了固定大小空间，要么浪费资源，要么资源不够。写到这，立即可以推出使用链表，但是内核提供的链表并没有数据域都是指针域，如何设计成为了关键。
在这里，dmatest.c给出了参考答案，通过在每个成员中添加一个node节点，作为中介节点。如下所示。
| struct thread_t{ struct list_head node; }
struct channel_t{ struct list_head node; struct list_head threads; }
struct info_t{ struct list_head channels; };
static info_t info = {.channels = LIST_HEAD_INIT(&info.channels)} |
主要的操作包括。
| //构建通道与线程之间的关系 list_add_tail(&thread->node, &dtc->threads); //构建驱动模块与通道之间的关系 list_add_tail(&dtc->node, &info->channels); //构建通道与线程之间的关系 list_add_tail(&thread->node, &dtc->threads); //构建驱动模块与通道之间的关系 list_add_tail(&dtc->node, &info->channels); //遍历，因为已知的是模块内部声明的且唯一的info结构体，所以遍历按如下顺序 list_for_each_entry(dtc, &info->channels, node) { struct dmatest_thread *thread; list_for_each_entry(thread, &dtc->threads, node) { if (!thread->done) return true; } } |
参考文献
[1] http://www.cnblogs.com/Anker/p/3475643.html
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)