Linux链表数据结构及相关操作

定义 

1

/include/linux/types.hstruct list_head { struct list_head *next, *prev; };与响应的结构组成双向链表。

初始化

1
2
3
4

/include/linux/list.h#define LIST_HEAD_INIT(name) { &(name), &(name) }

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

方法

插入

1

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

删除

1

static inline void list_del(struct list_head *entry)

替换

1
2

static inline void list_replace(struct list_head *old,
				struct list_head *new)

交换

1

static inline void list_swap(struct list_head *entry1,                              struct list_head *entry2)

删除

1
2

static inline void list_move(struct list_head *list, 
                             struct list_head *head)

遍历

1
2

#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

获取节点某一成员

1
2

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

      以上是基于2.4内核版本的宏， 2.6版本后引入RCU新的锁机制，相关宏定义后新增_rcu. 

     RCU （read-copy update）, 适用于大量读，小量写入的场景， 核心思想将写分为写，更新两部， 读操作的时候无阻塞， 当执行写操作时， 更新动作会延时到所有读操作完毕后执行。  init_task 第一个进程没有那么复杂，直接使用了LIST_HEAD_INIT初始化

Linux进程列表

      在进程 task_struct结构中 存在一个list_head ，  task 属性用于将当前进程存入进程列表。

      统计init_task为首链时使用RCU模式的链表， 进程内部的 child和sibling还是使用非RCU宏的链表结构处理。 

宏定义了一个循环从init_task开始遍历列表

for_each_process 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

/include/linux/sched.h

#define for_each_process(p) \
	for (p = &init_task ; (p = next_task(p)) != &init_task ; )

获取task，next指针指向task_struct中task也就是下一个进程的task
#define next_task(p) \
	list_entry_rcu((p)->tasks.next, struct task_struct, tasks)

/include/linux/rculist.h 
#define list_entry_rcu(ptr, type, member) \
({typeof (*ptr) __rcu *__ptr = (typeof (*ptr) __rcu __force *)ptr; \
container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
})

找到结构体中member的偏移量
/include/linux/kernel.h
#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

Linux进程遍历及实现

环境： cenos7

kernel： 3.10.0-862.el7.x86_64

gcc： gcc version 4.8.5 20150623 (Red Hat 4.8.5-36) (GCC)

task_list_lr.c 文件：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/sched/signal.h>
#include <linux/sched.h>

int task_list_lr_init(void)
{
printk(KERN_INFO "module task_list_lr init");
struct task_struct *task;
for_each_process(task) {
printk(KERN_INFO "pid %d, name %s , state %d \n", \
task->pid, task->comm, task->state);
}
return 0;
}

void task_list_lr_exit(void)
{
printk(KERN_INFO "module task_list_lr exit");
}

module_init(task_list_lr_init);
module_exit(task_list_lr_exit);

Makefile文件

1
2
3
4
5
6
7
8

obj-m += task_list_lr.o
KERNELDIR := /lib/modules/$(shell uname -r)/build
PWD := $(shell pwd)

all:
$(MAKE) -C $(KERNELDIR) M=$(PWD) modules
clean:
$(MAKE) -C $(KERNELDIR) M=$(PWD) clean

加载自定义模块：

1

[root@centosgpt kmodule]# insmod task_list_lr.ko[root@centosgpt kmodule]# lsmod |grep tasktask_list_lr 12510 0[root@centosgpt kmodule]# rmmod task_list_lr

查看/var/log/messages输出结果：

1

00:24:25 centosgpt kernel: module task_list_lr init00:24:25 centosgpt kernel: pid 1, name systemd , state 100:24:25 centosgpt kernel: pid 2, name kthreadd , state 100:24:25 centosgpt kernel: pid 3, name ksoftirqd/0 , state 100:24:25 centosgpt kernel: pid 5, name kworker/0:0H , state 100:24:25 centosgpt kernel: pid 7, name migration/0 , state 100:24:25 centosgpt kernel: pid 8, name rcu_bh , state 1。。。

问题

报错提示build目录不存：

1

[root@centosgpt kmodule]# makemake -C /lib/modules/3.10.0-862.el7.x86_64/build M=/root/src/kmodule modulesmake: *** /lib/modules/3.10.0-862.el7.x86_64/build: No such file or directory. Stop.make: *** [all] Error 2

处理方法：

查看 build目录属性发现他是一个链接文件：

lrwxrwxrwx. 1 root root 38 Dec 16 15:50 build -> /usr/src/kernels/3.10.0- 862.el7.x86_64

build链接到 /usr/src/kernels/3.10.0- 862.el7.x86_64，但  3.10.0- 862.el7.x86_64不存在实际目录为  3.10.0-957.el7 .x86_64

重新链接build到有效目录：

ln -s -f /usr/src/kernels/3.10.0-957.el7 .x86_64 build

not supported by the compiler

1

[root@centosgpt kmodule]# makemake -C /lib/modules/3.10.0-862.el7.x86_64/build M=/root/src/kmodule modulesmake[1]: Entering directory `/usr/src/kernels/3.10.0-957.el7.x86_64'arch/x86/Makefile:96: stack-protector enabled but compiler support brokenarch/x86/Makefile:166: *** CONFIG_RETPOLINE=y, but not supported by the compiler . Compiler update recommended.. Stop.make[1]: Leaving directory `/usr/src/kernels/3.10.0-957.el7.x86_64'make: *** [all] Error 2

处理方法：

安装GCC编译器：

yum install gcc

未找到Makefile

1

[root@centosgpt kmodule]# makemake -C /lib/modules/3.10.0-862.el7.x86_64/build M=/root/src/kmodule modulesmake[1]: Entering directory `/usr/src/kernels/3.10.0-957.el7.x86_64'scripts/Makefile.build:44: /root/src/kmodule/Makefile: No such file or directorymake[2]: *** No rule to make target `/root/src/kmodule/Makefile'. Stop.make[1]: *** [_module_/root/src/kmodule] Error 2make[1]: Leaving directory `/usr/src/kernels/3.10.0-957.el7.x86_64'make: *** [all] Error 2

处理方法：

将makefile 名称改为Makefile

极客时间 刘超《趣谈Linux操作系统》的课堂作业， 练习后整理了相关知识点。

参考链接中有关于进程列表深度优先的遍历方法。

参考：

/build: No such file or directory

Tasks Lister

Kernel module that iterates over all tasks using depth first tree

Kernel module - List all processes / process information.

list_for_each and list_entry