链表知识点总结1. 什么是链表链表是一种线性数据结构元素通过指针串联不像数组那样在内存里连续排列。数组连续内存 [0] [1] [2] [3] [4] 链表离散内存 node_A ─→ node_B ─→ node_C ─→ NULL (有指针) (有指针) (有指针)2. Linux 内核链表——双向环形链表结构体定义structlist_head{structlist_head*next;// 指向下一个节点structlist_head*prev;// 指向上一个节点};环形结构┌──────────────────────────────────┐ ↓ │ head ─→ node1 ─→ node2 ─→ node3 ─→ head head ←─ node1 ←─ node2 ←─ node3 ←─ head ↑ │ └──────────────────────────────────┘头节点的prev指向最后一个节点最后一个节点的next指向头节点——环形。遍历时从头走到尾再回到头。空链表INIT_LIST_HEAD(head);head.next head head.prev head自己指向自己表示空链表。3. 链表节点 vs 链表头链表头是一个特殊的 list_head用来标识链表从哪里开始。链表节点是嵌入在数据结构体中的 list_head 字段。在 SPI 中有两种用法用法一链表节点嵌入在 message 里作为 master-queue 的一个元素structspi_message{structlist_headqueue;// ← 这是节点不是链表头// ...};structspi_master{structlist_headqueue;// ← 这是链表头// ...};master-queue链表头 ├── msgA.queue ← 节点 ├── msgB.queue ← 节点 └── msgC.queue ← 节点用法二链表头嵌入在 message 里用来串 transferstructspi_message{structlist_headtransfers;// ← 这是链表头下面挂 transfer// ...};structspi_transfer{structlist_headtransfer_list;// ← 节点// ...};msgA.transfers链表头跟 master-queue 无关 ├── t1.transfer_list ← 节点 ├── t2.transfer_list ← 节点 └── t3.transfer_list ← 节点4. 常用操作初始化链表头INIT_LIST_HEAD(master-queue);判断链表是否为空list_empty(master-queue);返回非零表示空链表head-next head。加入到尾部list_add_tail(msg-queue,master-queue);把 msgA 的 queue 节点加入到 master-queue 链表尾部。执行前head ─→ msgB 执行后head ─→ msgB ─→ msgA取第一个节点list_first_entry(master-queue,structspi_message,queue);取链表头下一个节点然后用container_of反推出外层结构体。从链表中删除list_del_init(msg-queue);修改前后节点的指针把自己从链表中摘除然后把自己初始化成空链表状态。staticinlinevoidlist_del_init(structlist_head*entry){__list_del(entry-prev,entry-next);// 摘除INIT_LIST_HEAD(entry);// 自己指向自己}摘除前 head ─→ msgA ─→ msgB ─→ msgC ─→ head 摘除 msgA 后 head ─────────→ msgB ─→ msgC ─→ head msgA.next msgA.prev msgA (安全状态)遍历链表structspi_message*msg;list_for_each_entry(msg,master-queue,queue){// 遍历 master-queue 链表上的所有 message}宏展开后等价于for(poslist_first_entry(head,type,member);pos-member!(head);poslist_next_entry(pos,member))从头开始走到回到头为止。5. container_of——从节点反推结构体这是内核链表的精髓。链表节点list_head本身不存数据它只是嵌入在数据结构里的一个字段。要拿到数据必须从节点地址反推出整个结构体的地址。#definecontainer_of(ptr,type,member)({\consttypeof(((type*)0)-member)*__mptr(ptr);\(type*)((char*)__mptr-offsetof(type,member));})原理用member在结构体中的偏移量减去这个偏移量得到结构体的起始地址。内存布局 |←────── struct spi_message ────────────────────────────→| msgA 起始地址 msgA 结束 │ │ ├─────────────────────────┬──────────────────────────────┤ │ 其他字段 │ queue 字段 │ │ │ next / prev │ └─────────────────────────┴──────────────────────────────┘ │ ↑ │ │ list_first_entry 拿到的地址msgA.queue │ │ │←── offsetof(queue) ───→│ │ │ │←── container_of 返回 ──→│msgA.queue 地址减去 offset所以在 SPI 里// master-queue.next 是一个 struct list_head 地址// 它实际上是某个 message 里 queue 字段的地址// container_of 减去 queue 在 spi_message 中的偏移// 得到这个 message 的起始地址master-cur_msgcontainer_of(master-queue.next,structspi_message,queue);6. 野指针什么是野指针野指针是指向已释放或无效内存的指针。访问野指针会导致不可预测的后果——可能读/写到了别人的内存。链表中的野指针list_del不带_init只是修改前后节点的指针把自己摘除但不修改自己staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next-prevprev;prev-nextnext;}摘除后entry-next和entry-prev仍然指向之前的前后节点。此时如果误操作再次list_del这个节点list_del(msg-queue);//第一次摘除成功但 msg-queue.next 和 prev 还是野指针list_del(msg-queue);//第二次__list_del 用野指针修改别人的内存 → 内存损坏第一次 list_del 后 msgA.queue.next msgB.queue (指向链表中的一个有效节点——但其实 msgA 已经不在链表里了) msgA.queue.prev head (同上) 如果再 list_del __list_del(msgA.queue.prev, msgA.queue.next) → 修改 head.next msgB.queue (没问题) → 修改 msgB.queue.prev head (没问题) 但是如果第二次 del 时的 prev/next 已经指向了已释放的内存 或者某个中间状态prev/next 指向的节点已经不在链表里了 继续操作那些节点就会导致内存损坏。list_del_init 解决了这个问题staticinlinevoidlist_del_init(structlist_head*entry){__list_del(entry-prev,entry-next);INIT_LIST_HEAD(entry);// entry-next entry-prev entry}摘除后把自己设成空状态再误操作list_del也只是对自己操作不影响别人。7. 链表在 SPI 中的两级嵌套SPI 消息泵用链表实现了一个二级队列结构master-queue链表头——存放所有待处理的 message │ ├── msgA.queue节点 │ └── msgA.transfers链表头——存放这个 message 的所有 transfer │ ├── t1.transfer_list节点 │ ├── t2.transfer_list节点 │ └── t3.transfer_list节点 │ ├── msgB.queue节点 │ └── msgB.transfers链表头 │ ├── t1.transfer_list节点 │ └── t2.transfer_list节点 │ ├── msgC.queue节点 │ ...代码上的操作路径// 从 master-queue 链表取 messagemaster-cur_msglist_first_entry(master-queue,structspi_message,queue);// cur_msg 指向整个 spi_message 结构体// 访问它的 transfers 链表头遍历 transferlist_for_each_entry(xfer,master-cur_msg-transfers,transfer_list){master-transfer_one(master,master-cur_msg-spi,xfer);}第一级通过queue节点找到 message第二级通过transfers链表头找到每个 transfer。container_of是两级之间的桥梁——从queue节点的地址反推出包含它的spi_message结构体然后就可以访问transfers这个链表头了。