Linux 内核数据结构：双向链表(一)

2015-6-24 10:21 |来自: http://blog.jobbole.com/ 2038 0

摘要: Linux 内核提供一套双向链表的实现，你可以在include/linux/list.h中找到。我们以双向链表着手开始介绍Linux内核中的数据结构，因为这个是在 Linux 内核中使用最为广泛的数据结构，具体你可以查看这里。首先让我们 ...

关键词： nbsp root Mar 内核 crw 12 01 21 10 Linux

Linux 内核提供一套双向链表的实现，你可以在 include/linux/list.h 中找到。我们以双向链表着手开始介绍 Linux 内核中的数据结构，因为这个是在 Linux 内核中使用最为广泛的数据结构，具体你可以查看这里。

首先让我们看一下主要的结构体：

struct list_head {
    struct list_head *next, *prev;
};

你可以看到其与常见的结构体实现有显著不同，比如 glib 中所使用到的双向链表实现。

struct GList {
  gpointer data;
  GList *next;
  GList *prev;
};

通常来说，链表结构体要包括一个指向数据的指针，不过 Linux 内核的链表却不包含此实现。那么首要的疑问：链表是用什么方式存储数据的?。Linux 内核所实现的是一种被称为侵入式的链表（Intrusive list），这种链表并不在链表结构中包含数据，而仅提供用于维护前向与后向访问结构的指针。这种实现方式使得链表数据结构非常通用，因为它并不需要关注链表所维护的具体数据类型。

比如：

struct nmi_desc {
    spinlock_t lock;
    struct list_head head;
};

接下来让我们看一些内核使用 list_head 的具体例子。正如在前文所述的，Linux 内核中诸多模块都使用了 list_head。这里我们以内核杂项字符设备驱动（miscellaneous character drivers）部分实现为例。驱动的 API 在 drivers/char/misc.c 中，其实现了简单硬件外设以及虚拟设备的驱动，这个驱动共享主设备号（Major number）：

1	`#define MISC_MAJOR 10`

每个设备有自己的次设备号，具体可以看这个列子：

ls -l /dev |  grep 10
crw-------   1 root root     10, 235 Mar 21 12:01 autofs
drwxr-xr-x  10 root root         200 Mar 21 12:01 cpu
crw-------   1 root root     10,  62 Mar 21 12:01 cpu_dma_latency
crw-------   1 root root     10, 203 Mar 21 12:01 cuse
drwxr-xr-x   2 root root         100 Mar 21 12:01 dri
crw-rw-rw-   1 root root     10, 229 Mar 21 12:01 fuse
crw-------   1 root root     10, 228 Mar 21 12:01 hpet
crw-------   1 root root     10, 183 Mar 21 12:01 hwrng
crw-rw----+  1 root kvm      10, 232 Mar 21 12:01 kvm
crw-rw----   1 root disk     10, 237 Mar 21 12:01 loop-control
crw-------   1 root root     10, 227 Mar 21 12:01 mcelog
crw-------   1 root root     10,  59 Mar 21 12:01 memory_bandwidth
crw-------   1 root root     10,  61 Mar 21 12:01 network_latency
crw-------   1 root root     10,  60 Mar 21 12:01 network_throughput
crw-r-----   1 root kmem     10, 144 Mar 21 12:01 nvram
brw-rw----   1 root disk      1,  10 Mar 21 12:01 ram10
crw--w----   1 root tty       4,  10 Mar 21 12:01 tty10
crw-rw----   1 root dialout   4,  74 Mar 21 12:01 ttyS10
crw-------   1 root root     10,  63 Mar 21 12:01 vga_arbiter
crw-------   1 root root     10, 137 Mar 21 12:01 vhci

现在我们看看设备驱动是如何使用链表维护设备列表的，首先，我们看一下 miscdevice 的 struct 定义：

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除

路过

雷人

握手

鲜花

鸡蛋

收藏分享邀请

上一篇：如何在 Git 里撤销(几乎)任何操作下一篇：Linux 内核数据结构：双向链表（二）

Linux 内核数据结构：双向链表(一)

最新评论

相关分类