你知道Linux内核数据结构中双向链表的作用?.doc
《你知道Linux内核数据结构中双向链表的作用?.doc》由会员分享,可在线阅读,更多相关《你知道Linux内核数据结构中双向链表的作用?.doc(11页珍藏版)》请在三一文库上搜索。
1、你知道Linux内核数据结构中双向链表的作用?Linux 内核提供一套双向链表的实现,你可以在 include/linux/list.h 中找到。我们以双向链表着手开始介绍 Linux 内核中的数据结构 ,因为这个是在 Linux 内核中使用最为广泛的数据结构。首先让我们看一下主要的结构体:Cstruct list_head struct list_head *next, *prev;123struct list_head struct list_head *next, *prev;你可以看到其与常见的结构体实现有显著不同,比如 glib 中所使用到的双向链表实现。Cstruct GList
2、gpointer data; GList *next; GList *prev;12345struct GList gpointer data;GList *next;GList *prev;通常来说,链表结构体要包括一个指向数据的指针,不过 Linux 内核的链表却不包含此实现。那么首要的疑问:链表是用什么方式存储数据的?。Linux 内核所实现的是一种被称为侵入式的链表(Intrusive list),这种链表并不在链表结构中包含数据,而仅提供用于维护前向与后向访问结构的指针。这种实现方式使得链表数据结构非常通用,因为它并不需要关注链表所维护的具体数据类型。比如:Cstruct nmi_d
3、esc spinlock_t lock; struct list_head head;1234struct nmi_desc spinlock_t lock;struct list_head head;接下来让我们看一些内核使用 list_head 的具体例子。正如在前文所述的,Linux 内核中诸多模块都使用了 list_head。这里我们以内核杂项字符设备驱动(miscellaneous character drivers)部分实现为例。驱动的 API 在 drivers/char/misc.c 中,其实现了简单硬件外设以及虚拟设备的驱动,这个驱动共享主设备号(Major number):
4、C#define MISC_MAJOR 101#define MISC_MAJOR10每个设备有自己的次设备号,具体可以看这个列子:ls -l /dev | grep 10crw- 1 root root 10, 235 Mar 21 12:01 autofsdrwxr-xr-x 10 root root 200 Mar 21 12:01 cpucrw- 1 root root 10, 62 Mar 21 12:01 cpu_dma_latencycrw- 1 root root 10, 203 Mar 21 12:01 cusedrwxr-xr-x 2 root root 100 Mar 2
5、1 12:01 dricrw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fusecrw- 1 root root 10, 228 Mar 21 12:01 hpetcrw- 1 root root 10, 183 Mar 21 12:01 hwrngcrw-rw-+ 1 root kvm 10, 232 Mar 21 12:01 kvmcrw-rw- 1 root disk 10, 237 Mar 21 12:01 loop-controlcrw- 1 root root 10, 227 Mar 21 12:01 mcelogcrw- 1 root roo
6、t 10, 59 Mar 21 12:01 memory_bandwidthcrw- 1 root root 10, 61 Mar 21 12:01 network_latencycrw- 1 root root 10, 60 Mar 21 12:01 network_throughputcrw-r- 1 root kmem 10, 144 Mar 21 12:01 nvrambrw-rw- 1 root disk 1, 10 Mar 21 12:01 ram10crw-w- 1 root tty 4, 10 Mar 21 12:01 tty10crw-rw- 1 root dialout 4
7、, 74 Mar 21 12:01 ttyS10crw- 1 root root 10, 63 Mar 21 12:01 vga_arbitercrw- 1 root root 10, 137 Mar 21 12:01 vhci123456789101112131415161718192021ls -l /dev |grep 10crw- 1 root root 10, 235 Mar 21 12:01 autofsdrwxr-xr-x10 root root 200 Mar 21 12:01 cpucrw- 1 root root 10,62 Mar 21 12:01 cpu_dma_lat
8、encycrw- 1 root root 10, 203 Mar 21 12:01 cusedrwxr-xr-x 2 root root 100 Mar 21 12:01 dricrw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fusecrw- 1 root root 10, 228 Mar 21 12:01 hpetcrw- 1 root root 10, 183 Mar 21 12:01 hwrngcrw-rw-+1 root kvm10, 232 Mar 21 12:01 kvmcrw-rw- 1 root disk 10, 237 Mar 21 1
9、2:01 loop-controlcrw- 1 root root 10, 227 Mar 21 12:01 mcelogcrw- 1 root root 10,59 Mar 21 12:01 memory_bandwidthcrw- 1 root root 10,61 Mar 21 12:01 network_latencycrw- 1 root root 10,60 Mar 21 12:01 network_throughputcrw-r- 1 root kmem 10, 144 Mar 21 12:01 nvrambrw-rw- 1 root disk1,10 Mar 21 12:01
10、ram10crw-w- 1 root tty 4,10 Mar 21 12:01 tty10crw-rw- 1 root dialout 4,74 Mar 21 12:01 ttyS10crw- 1 root root 10,63 Mar 21 12:01 vga_arbitercrw- 1 root root 10, 137 Mar 21 12:01 vhci现在我们看看设备驱动是如何使用链表维护设备列表的,首先,我们看一下 miscdevice 的 struct 定义:Cstruct miscdevice int minor; const char *name; const struct
11、file_operations *fops; struct list_head list; struct device *parent; struct device *this_device; const char *nodename; mode_t mode;1234567891011struct miscdeviceint minor;const char *name;const struct file_operaTIons *fops;struct list_head list;struct device *parent;struct device *this_device;const
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 知道 Linux 内核 数据结构 双向 作用
链接地址:https://www.31doc.com/p-3381747.html