您的位置 首页 新品

你知道Linux内核数据结构中双向链表的效果?

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

Linux 内核供给一套双向链表的完成,你能够在 include/linux/list.h 中找到。咱们以双向链表着手开端介绍 Linux 内核中的数据结构 ,由于这个是在 Linux 内核中运用最为广泛的数据结构。

首要让咱们看一下首要的结构体:

C

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

1

2

3

struct list_head {

struct list_head *next, *prev;

};

你能够看到其与常见的结构体完成有明显不同,比方 glib 中所运用到的双向链表完成。

C

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

1

2

3

4

5

struct GList {

gpointer data;

GList *next;

GList *prev;

};

一般来说,链表结构体要包括一个指向数据的指针,不过 Linux 内核的链表却不包括此完成。那么首要的疑问:链表是用什么方法存储数据的?。Linux 内核所完成的是一种被称为侵入式的链表(Intrusive list),这种链表并不在链表结构中包括数据,而仅供给用于保护前向与后向拜访结构的指针。这种完成方法使得链表数据结构十分通用,由于它并不需求重视链表所保护的详细数据类型。

比方:

C

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

1

2

3

4

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):

C

#define MISC_MAJOR 10

1

#define MISC_MAJOR              10

每个设备有自己的次设备号,详细能够看这个列子:

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 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 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 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 disk 1, 10 Mar 21 12:01 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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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 界说:

C

struct miscdevice{ int minor; const char *name; const struct file_operations *fops; struct list_head list; struct device *parent; struct device *this_device; const char *nodename; mode_t mode;};

1

2

3

4

5

6

7

8

9

10

11

struct miscdevice

{

int minor;

const char *name;

const struct file_operaTIons *fops;

struct list_head list;

struct device *parent;

struct device *this_device;

const char *nodename;

mode_t mode;

};

能够看到 miscdevice 的第四个成员 list ,这个便是用于保护已注册设备链表的结构。在源代码文的首部,咱们能够看到以下界说:

C

staTIc LIST_HEAD(misc_list);

1

staTIc LIST_HEAD(misc_list);

这个界说宏打开,能够看到是用于界说 list_head 类型变量:

C

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

1

2

#define LIST_HEAD(name)

struct list_head name = LIST_HEAD_INIT(name)

LIST_HEAD_INIT 这个宏用于对界说的变量进行双向指针的初始化:

C

#define LIST_HEAD_INIT(name) { &(name), &(name) }

1

#define LIST_HEAD_INIT(name) { &(name), &(name) }

现在我看能够看一下函数 misc_register 是怎么进行设备注册的。首要是用 INIT_LIST_HEAD 对 miscdevice->list 成员变量进行初始化:

C

INIT_LIST_HEAD(&misc->list);

1

INIT_LIST_HEAD(&misc->list);

这个操作与 LIST_HEAD_INIT 宏共同:

C

static inline void INIT_LIST_HEAD(struct list_head *list){ list->next = list; list->prev = list;}

1

2

3

4

5

staTIc inline void INIT_LIST_HEAD(struct list_head *list)

{

list->next = list;

list->prev = list;

}

接下来,在经过函数 device_create 进行设备创立,一起将设备增加到 Misc 设备列表中:

C

list_add(&misc->list, &misc_list);

1

list_add(&misc->list, &misc_list);

内核的 list.h文件供给向链表增加节点的 API,这儿是增加操作的完成:

C

static inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}

1

2

3

4

static inline void list_add(struct list_head *new, struct list_head *head)

{

__list_add(new, head, head->next);

}

函数完成很简略,便是入参转换为三个参数后调用内部 __list_add :

new – 新节点;

head – 新节点刺进的双向链表头;

head->next – 链表头的下一个节点;

_list_add 函数的完成愈加简略:

C

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;}

1

2

3

4

5

6

7

8

9

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;

}

这儿设置了新增加结点的 prev 与 next 指针,经过这些操作,就将从前运用 LIST_HEAD_INIT 所界说的 misc 链表的双向指针与 miscdevice->list 结构相关起来。

这儿还有一个问题,便是怎么获取链表中的数据,list_head 供给了一个特别的宏用于获取数据指针。

C

#define list_entry(ptr, type, member) container_of(ptr, type, member)

1

2

#define list_entry(ptr, type, member)

container_of(ptr, type, member)

这儿有三个参数

ptr:list_head 结构指针

type:数据对应的 struct 类型

member:数据中 list_head 成员对应的成员变量名

举例如下:

C

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

1

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

接下来咱们就够拜访 miscdevice 的各个成员,如 p->minor、p->name 等等,咱们看一下 list_entry 的完成:

C

#define list_entry(ptr, type, member) container_of(ptr, type, member)

1

2

#define list_entry(ptr, type, member)

container_of(ptr, type, member)

其完成十分简略,便是运用入参调用 container_of 宏,宏的完成如下:

C

#define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr – offsetof(type,member) );})

1

2

3

#define container_of(ptr, type, member) ({                      

const typeof( ((type *)0)->member ) *__mptr = (ptr);    

(type *)( (char *)__mptr – offsetof(type,member) );})

留意,宏运用了大括号表达式,关于大括号表达式,编译器会打开一切表达式,一起运用最终一个表达式的成果进行回来。

举个比如:

C

#include int main() { int i = 0; printf(“i = %dn”, ({++i; ++i;})); return 0;}

1

2

3

4

5

6

7

#include

int main() {

int i = 0;

printf(“i = %dn”, ({++i; ++i;}));

return 0;

}

输出成果为 2 。

另一个关键是 typeof 关键字,这个十分简略,这个正如它的姓名相同,这个关键字回来的成果是变量的类型。当我榜首次看到这个宏时,最让我觉得奇怪的是表达式 ((type*)0) 中的 0 值,实践上,运用 0 值作为地址这个是成员变量获得 struct 内相对偏移地址的奇妙完成,咱们再来看个比如:

C

#include struct s { int field1; char field2; char field3;};int main() { printf(“%pn”, &((struct s*)0)->field3); return 0;}

1

2

3

4

5

6

7

8

9

10

11

12

#include

struct s {

int field1;

char field2;

char field3;

};

int main() {

printf(“%pn”, &((struct s*)0)->field3);

return 0;

}

输出成果为 0x5 。

还有一个专门用于获取结构体中某个成员变量偏移的宏,其完成与前面说到的宏十分相似:

C

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

1

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

这儿对 container_of 宏做个总述,container_of 宏经过 struct 中的 list_head 成员回来 struct 对应数据的内存地址。在宏的榜首行界说了指向 list_head 成员的指针 __mptr ,并将 ptr 地址赋给 __mptr 。从技能完成的视点来看,实践并不需求这一行界说,但这个关于类型查看而言十分有意义。这一行代码保证结构体( type )中存在 member 对应的成员。第二行运用 offsetoff 宏计算出包括 member 的结构体所对应的内存地址,便是这么简略。

当然 list_add 与 list_entry 并非是 中的悉数函数,关于双向链表 list_head ,内核还供给了以下的接口

list_add

list_add_tail

list_del

list_replace

list_move

list_is_last

list_empty

list_cut_position

list_splice

未了,需求说的是,内核代码中并不只是只要上述这些接口。

 

声明:本文内容来自网络转载或用户投稿,文章版权归原作者和原出处所有。文中观点,不代表本站立场。若有侵权请联系本站删除(kf@86ic.com)https://www.86ic.net/xinpin/90251.html

为您推荐

联系我们

联系我们

在线咨询: QQ交谈

邮箱: kf@86ic.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部