linux内核里的数据结构双向链表

《linux内核里的数据结构双向链表》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、双向链表Linux内核中自己实现了双向链表，可以在include/linux/list.h找到定义。我们将会首先从双向链表数据结构开始介绍内核里的数据结构。为什么？因为它在内核里使用的很广泛，你只需耍在free-electrons.com检索一下就知进了。首先让我们看一下在include/linux/types.h里的主结构体:structlist_head{structlist_head*next,*prev;}；你可能注意到这和你以前见过的双昀链表的实现方法是不同的。举个例子来说，在glib库里足这样实现的：structGList{g

2、pointerdata;GList*next;GList*prev;}；通常来说一个链表结构会包含一个指昀某个项tJ的指针。似是Linux内核中的链表实现外没有这样做。所以1'小题來了：链表在哪里保存数据呢？。实际上，内核里实现的链表是侵入式链表(Intrusivelist)0侵入式链表并不在节点内保存数据-它的节点仅仅包含指叫前后节点的指针，以及指h'd链表节点数裾部分的指针——数裾就是这样附加在链表上的。这就使得这个数据结构是通用的，使用起来就不需要考虑节点数裾的类型了。比如：structnmi_desc{spinlock」lock;

3、structlist_headhead;}；让我们看几个例子来理解一下在内核里是如何使用list_head的。如上所述，在内核風有很多很多不同的地方都用到丫链表。我们來看一个在杂项字符驱动里而的使川的例了。在drivers/char/misc.c的來项字符嫩动API被川來编写处理小型硬件或虚拟设备的小观动。这些驱动共享相同的主设备号：#defineMISC_MAJOR10但是都有各自不M的次设备号。比如：ls-1/devIgreplOcrw1rootroot10,235Mar2112:01autofsdrwxr-xr-x10rootroo

4、t200Mar2112:01cpucrw1rootroot10,62Mar2112:01cpu_dma_latencycrw1rootroot10,203Mar2112:01cusedrwxr-xr-x2rootroot100Mar2112:01dricrw-rw-rw-1rootroot10,229Mar2112:01fusecrw1rootroot10,228Mar2112:01hpetcrw1rootroot10,183Mar2112:01hwrngcrw-rw----+1rootkvm10,232Mar2112:01kvmcrw-

5、rw-…1rootdisk10,237Mar2112:01loop-controlcrw1rootroot10,227Mar2112:01mcelogcrw1rootroot10,59Mar2112:01memory_bandwidthcrw1rootroot10,61Mar2112:01networkjatencycrw1rootroot10,60Mar2112:01network_throughputcrw-r——1rootkmem10,144Mar2112:01nvrambrw-rw----1rootdiskl,10Mar2112:

6、01ramlOcrw-w-™1roottty4,10Mar2112:01ttylOcrw-rw-—1rootdialout4,74Mar2112:01ttySlOcrw1rootroot10,63Mar2112:01vga_arbitercrw1rootroot10,137Mar2112:01vhci现在让我们看看它楚如何使用链表的。首先看一下结构体miscdevice：structmiscdevice{intminor;constchar*name;conststructfile_operations*fops;structlist_h

7、eadlist;structdevice*parent;structdevice*this_device;constchar*nodename;mode_tmode;};可以看到结构体miscdevice的笫叫个变跫list是所有注册过的设备的链表。在源代码文件的开始可以看到这个链表的定义：staticLIST_HEAD(misc_list);它实际上是对用list.head类型定义的变贷的扩展。#defineLIST_HEAD(name)structlist_headname=LIST_HEAD」NIT(name>然后使川宏UST_H

8、EADJNIT进行初始化，这会使川变finame的地址來填充prev和next结构体的两个变量。#defineLIST_HEAD_INIT(name){&(name),&(name)}现在来看