linux 内核链表使用
linux 内核链表使用
·
List
下面是截取内核源码，有部分修改方便自己测试使用
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
// include/linux/types.h
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
// 初始化链表，前驱和后继都指向自己
static inline void INIT_LIST_HEAD(struct list_head *list){
list->next = list;
list->prev = list;
}
// 往链表插入节点内部方法 prv <=> new <=> next
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;
}
// 在head 节点插入 new 节点，head <=> new <=> head->next（利于堆栈实现）
static inline void list_add(struct list_head *new, struct list_head *head){
__list_add(new, head, head->next);
}
// 在head 节点插入 new 节点，head->prev <=> new <=> head （利于队列实现）
static inline void list_add_tail(struct list_head *new, struct list_head *head){
__list_add(new, head->prev, head);
}
// 删除节点内部方法
static inline void __list_del(struct list_head * prev, struct list_head * next){
next->prev = prev;
prev->next = next;
}
// 删除entry节点，并时prev = NULL
static inline void __list_del_clearprev(struct list_head *entry){
__list_del(entry->prev, entry->next);
entry->prev = NULL;
}
// 删除entry节点
static inline void __list_del_entry(struct list_head *entry){
__list_del(entry->prev, entry->next);
}
// 删除entry节点， 使entry->next，prev 为null (在Linux内部为非法值，访问产生缺页中断)
static inline void list_del(struct list_head *entry){
__list_del_entry(entry);
entry->next = NULL;
entry->prev = NULL;
}
// new 节点 替换 old 节点
static inline void list_replace(struct list_head *old,struct list_head *new){
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
// new 节点 替换 old 节点，并初始化 old
static inline void list_replace_init(struct list_head *old, struct list_head *new){
list_replace(old, new);
INIT_LIST_HEAD(old);
}
// 交换两个节点位置
static inline void list_swap(struct list_head *entry1, struct list_head *entry2){
struct list_head *pos = entry2->prev;
list_del(entry2);
list_replace(entry1, entry2);
if (pos == entry1)
pos = entry2;
list_add(entry1, pos);
}
// 删除entry节点，并初始化entry
static inline void list_del_init(struct list_head *entry){
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
// 删除list 节点，并将其添加到head节点后
static inline void list_move(struct list_head *list, struct list_head *head){
__list_del_entry(list);
list_add(list, head);
}
// 删除list 节点，并将其添加到head节点前
static inline void list_move_tail(struct list_head *list, struct list_head *head){
__list_del_entry(list);
list_add_tail(list, head);
}
// 确定MEMBER 成员在TYPE 结构体的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
// 知道type 结构体的 member 成员指针 ptr, 获取该结构体的指针
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define list_entry(ptr, type, member) container_of(ptr, type, member)
// 从链表ptr头 获取第一个元素
#define list_first_entry(ptr, type, member) list_entry((ptr)->next, type, member)
// 从链表ptr头 获取最后一个元素
#define list_last_entry(ptr, type, member) list_entry((ptr)->prev, type, member)
// 从链表ptr头 获取第一个元素，如果链表如空返回 NULL
#define list_first_entry_or_null(ptr, type, member) ({ \
struct list_head *head__ = (ptr); \
struct list_head *pos__ = READ_ONCE(head__->next); \
pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
})
// 从结构体pos 获取下一个元素
#define list_next_entry(pos, member) \
list_entry((pos)->member.next, typeof(*(pos)), member)
// 从结构体pos 获取前一个元素
#define list_prev_entry(pos, member) \
list_entry((pos)->member.prev, typeof(*(pos)), member)
// 链表节点遍历，从表头head开始，逐项向后（next方向）移动pos，直至又回到head，基于列表不变的基础上
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
// 在当前pos 节点继续遍历
#define list_for_each_continue(pos, head) \
for (pos = pos->next; pos != (head); pos = pos->next)
// 在当前pos 节点往前遍历
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
// 安全遍历一个链表，通过传入两个参数pos,n 可以在链表中删除pos
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev)
#define list_entry_is_head(pos, head, member) \
(&pos->member == (head))
// 遍历链表，但是获得是结构体
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
!list_entry_is_head(pos, head, member); \
pos = list_next_entry(pos, member))
// 反向遍历链表
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_last_entry(head, typeof(*pos), member); \
!list_entry_is_head(pos, head, member); \
pos = list_prev_entry(pos, member))
// 以安全的方式遍历链表
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member), \
n = list_next_entry(pos, member); \
!list_entry_is_head(pos, head, member); \
pos = n, n = list_next_entry(n, member))
#endif
用户态测试
形成的数据结果如图
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
/*
整体需求：
type2 组成一条链表，里面的每个节点包含 type1 类型的链表
*/
struct type1{
int value;
struct list_head list;
};
struct type2 {
int id;
struct type1 item;
struct list_head list;
};
int id_count = 0;
struct type2 src;
int find_by_id (int id,struct type2 **tmp) {
struct list_head *pos;
list_for_each(pos, &(src.list)){
*tmp = list_entry(pos, struct type2, list);
if ((*tmp)->id == id) {
return 0;
}
}
return -1;
}
int add_type2(int * id) {
struct type2 *tmp;
tmp = malloc(sizeof(struct type2));
INIT_LIST_HEAD(&(tmp->item.list));
id_count ++;
tmp->id = id_count;
*id = id_count;
list_add(&(tmp->list),&(src.list));
return 0;
}
int del_type2(int id){
struct type2 *tmp;
struct type1 *prev, *next;
int ret = find_by_id(id,&tmp);
if (ret)
return ret;
list_for_each_entry_safe(prev, next, &(tmp->item.list), list) {
if(prev) {
list_del(&(prev->list));
free(prev);
}
}
list_del(&(tmp->list));
free(tmp);
return 0;
}
int add_type1(int id,int value) {
struct type2 *tmp;
struct type1 *item_tmp;
int ret = find_by_id(id,&tmp);
if (ret)
return ret;
item_tmp = malloc(sizeof(struct type1));
item_tmp->value = value;
list_add(&(item_tmp->list),&(tmp->item.list));
return 0;
}
int del_type1(int id,int value) {
struct type2 *tmp;
struct list_head *type1_ptr;
struct type1 *item_tmp;
int ret = find_by_id(id,&tmp);
if (ret)
return ret;
// 释放 plr_sync_item
list_for_each(type1_ptr, &(tmp->item.list)){
item_tmp = list_entry(type1_ptr, struct type1, list);
if (item_tmp->value == value) {
list_del(type1_ptr);
free(item_tmp);
return 0;
}
}
return -1;
}
// 销毁数据
int del() {
struct type2 *tmp_prev,*tmp_next;
struct type1 *type2_prev,*type2_next;
list_for_each_entry_safe(tmp_prev,tmp_next,&(src.list),list) {
if (!tmp_prev) {
printf("error\n");
continue;
}
list_for_each_entry_safe(type2_prev,type2_next,&(tmp_prev->item.list),list) {
if (type2_prev) {
list_del(&(type2_prev->list));
free(type2_prev);
}
}
list_del(&(tmp_prev->list));
free(tmp_prev);
}
return 0;
}
int print_list() {
struct type2 *tmp;
struct type1 *type1_tmp;
printf("----------------------------\n");
list_for_each_entry(tmp,&(src.list),list) {
printf("id=%d:",tmp->id);
list_for_each_entry(type1_tmp,&(tmp->item.list),list) {
printf("%d, ",type1_tmp->value);
}
printf("\n");
}
return 0;
}
int main() {
int opt;
int type1_id;
int value;
INIT_LIST_HEAD(&(src.list));
while(~scanf("%d",&opt)) {
switch (opt) {
case 1: {
add_type2(&type1_id);
break;
}
case 2: {
scanf("%d",&value);
del_type2(value);
break;
}
case 3: {
scanf("%d",&value);
add_type1(type1_id,value);
break;
}
case 4: {
scanf("%d",&value);
del_type1(type1_id,value);
break;
}
}
print_list();
}
del();
print_list();
return 0;
}
输入测试
# test.log
1
3 1
3 2
1
3 3
3 4
4 4
2 1
内核模块测试
内核模块
#include <linux/init.h> // __init,__exit macro
#include <linux/module.h> // included for all kernel modules
#include <linux/ioctl.h>
#include <linux/uaccess.h> // copy_from_user
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/fs.h> // file_operation is defined in this header
#include <linux/device.h>
#include <linux/err.h> // PTR_ERR
/*
整体需求：
type2 组成一条链表，里面的每个节点包含 type1 类型的链表
*/
#define ERR(fmt, args...) printk(KERN_ERR "%s()-%d: " fmt "\n", __func__, __LINE__, ##args)
#define DBG(fmt, args...) printk(KERN_DEBUG "%s()-%d: " fmt "\n", __func__, __LINE__, ##args)
struct type1{
int value;
struct list_head list;
};
struct type2 {
int id;
struct type1 item;
struct list_head list;
};
struct param{
int value;
int id;
};
int majorNumber;
struct class* list_test_module_class = NULL;
struct device* list_test_module_device = NULL;
//define device name
#define DEVICE_NAME "list_test"
#define CLASS_NAME "list_test_module"
int id_count = 0;
struct type2 src;
// iotcl 命令相关定义
#define PLR_SYNC_MAGIC 'l'
#define ADD_TYPE2 _IOR(PLR_SYNC_MAGIC, 1,int)
#define DEL_TYPE2 _IOW(PLR_SYNC_MAGIC, 2,int)
#define ADD_TYPE1 _IOW(PLR_SYNC_MAGIC, 3,struct param)
#define DEL_TYPE1 _IOW(PLR_SYNC_MAGIC, 4,struct param)
#define PRINT _IO(PLR_SYNC_MAGIC,5)
// 用户态调用ioctl 回调函数
static long list_test_module_ioctl(struct file *, unsigned int, unsigned long);
struct file_operations ply_sync_ops = {
.owner = THIS_MODULE,
.unlocked_ioctl = list_test_module_ioctl
};
// 模块初始化，退出函数
static int __init list_test_init(void);
static void __exit list_test_exit(void);
// 链表操作相关函数
int add_type2(int *id);
int del_type2(int id);
int add_type1(int id,int value);
int del_type1(int id,int value);
int del(void);
int print_list(void);
static int __init list_test_init(void) {
DBG("list_test_init enter");
majorNumber = register_chrdev(0, DEVICE_NAME, &ply_sync_ops);
if(majorNumber < 0){
ERR("[TestModule:] Failed to register a major number.");
return majorNumber;
}
DBG("[TestModule:] Successful to register a major number %d.", majorNumber);
//接下来，注册设备类
list_test_module_class = class_create(THIS_MODULE, CLASS_NAME);
if(IS_ERR(list_test_module_class)){
unregister_chrdev(majorNumber, DEVICE_NAME);
ERR("[TestModule:] Class device register failed!");
return PTR_ERR(list_test_module_class);
}
DBG("[TestModule:] Class device register success!");
//最后，使用device_create函数注册设备驱动
list_test_module_device = device_create(list_test_module_class, NULL, MKDEV(majorNumber, 0), NULL, DEVICE_NAME);
if (IS_ERR(list_test_module_device)){
class_destroy(list_test_module_class);
unregister_chrdev(majorNumber, DEVICE_NAME);
ERR("Failed to create the device");
return PTR_ERR(list_test_module_device);
}
// 初始化链表
INIT_LIST_HEAD(&(src.list));
DBG("list_test_init exit");
return 0;
}
static void __exit list_test_exit(void)
{
DBG("list_test_exit enter");
// 退出时，依次清理生成的device, class和chrdev
// 这样就将系统/dev下的设备文件删除，并自动注销了/proc/devices的设备
device_destroy(list_test_module_class, MKDEV(majorNumber, 0));
class_destroy(list_test_module_class);
unregister_chrdev(majorNumber, DEVICE_NAME);
// 销毁链表
del();
DBG("list_test_init exot");
}
//本模块ioctl回调函数的实现
static long list_test_module_ioctl(struct file *file, /* ditto */
unsigned int cmd, /* number and param for ioctl */
unsigned long param)
{
/* ioctl回调函数中一般都使用switch结构来处理不同的输入参数（cmd） */
int ret = -EINVAL; // 表示 无效的参数，包括参数值、类型或数目无效等
struct param info;
switch(cmd){
case ADD_TYPE2:{
ret = add_type2((int *)param);
break;
}
case DEL_TYPE2: {
ret = del_type2(param);
break;
}
case ADD_TYPE1: {
// 先从用户态复制数据
ret = copy_from_user(&info, (struct param __user *)param, sizeof(info));
// 拷贝发生错误
if (ret)
return -EFAULT;
ret = add_type1(info.id,info.value);
break;
}
case DEL_TYPE1: {
// 先从用户态复制数据
ret = copy_from_user(&info, (struct param __user *)param, sizeof(info));
// 拷贝发生错误
if (ret)
return -EFAULT;
ret = del_type1(info.id,info.value);
break;
}
case PRINT: {
print_list();
break;
}
default:
ERR("[TestModule:] Unknown ioctl cmd!");
}
return ret;
}
int find_by_id (int id,struct type2 **tmp) {
struct list_head *pos;
list_for_each(pos, &(src.list)){
*tmp = list_entry(pos, struct type2, list);
if ((*tmp)->id == id) {
return 0;
}
}
return -1;
}
int add_type2(int *id) {
struct type2 *tmp;
tmp = kmalloc(sizeof(struct type2),GFP_KERNEL);
INIT_LIST_HEAD(&(tmp->item.list));
id_count ++;
tmp->id = id_count;
*id = id_count;
list_add(&(tmp->list),&(src.list));
return 0;
}
int del_type2(int id){
struct type2 *tmp;
struct type1 *prev, *next;
int ret = find_by_id(id,&tmp);
if (ret)
return ret;
list_for_each_entry_safe(prev, next, &(tmp->item.list), list) {
if(prev) {
list_del(&(prev->list));
kfree(prev);
}
}
list_del(&(tmp->list));
kfree(tmp);
return 0;
}
int add_type1(int id,int value) {
struct type2 *tmp;
struct type1 *item_tmp;
int ret = find_by_id(id,&tmp);
if (ret)
return ret;
item_tmp = kmalloc(sizeof(struct type1),GFP_KERNEL);
item_tmp->value = value;
list_add(&(item_tmp->list),&(tmp->item.list));
return 0;
}
int del_type1(int id,int value) {
struct type2 *tmp;
struct list_head *type1_ptr;
struct type1 *item_tmp;
int ret = find_by_id(id,&tmp);
if (ret)
return ret;
// 释放 list_test_item
list_for_each(type1_ptr, &(tmp->item.list)){
item_tmp = list_entry(type1_ptr, struct type1, list);
if (item_tmp->value == value) {
list_del(type1_ptr);
kfree(item_tmp);
return 0;
}
}
return -1;
}
int del() {
struct type2 *tmp_prev,*tmp_next;
struct type1 *type2_prev,*type2_next;
list_for_each_entry_safe(tmp_prev,tmp_next,&(src.list),list) {
if (!tmp_prev) {
printk("error\n");
continue;
}
list_for_each_entry_safe(type2_prev,type2_next,&(tmp_prev->item.list),list) {
if (type2_prev) {
list_del(&(type2_prev->list));
kfree(type2_prev);
}
}
list_del(&(tmp_prev->list));
kfree(tmp_prev);
}
return 0;
}
int print_list() {
struct type2 *tmp;
struct type1 *type1_tmp;
printk("----------------------------\n");
list_for_each_entry(tmp,&(src.list),list) {
printk("id=%d:",tmp->id);
list_for_each_entry(type1_tmp,&(tmp->item.list),list) {
printk("%d, ",type1_tmp->value);
}
printk("\n");
}
return 0;
}
module_init(list_test_init);
module_exit(list_test_exit);
MODULE_AUTHOR("antrain");
MODULE_DESCRIPTION("kernel list test");
MODULE_LICENSE("GPL");
makefile
MODULE_NAME := test_list
#MODCFLAGS:=-O2 -Wall -DMODULE -D__KERNEL__ -DLINUX -std=c99
#EXTRA_CFLAGS += $(MODULE_FLAGS) $(CFG_INC) $(CFG_INC)
EXTRA_CFLAGS += -g -std=gnu99 -Wfatal-errors
ifneq ($(KERNELRELEASE),) # kernelspace
obj-m := $(MODULE_NAME).o
else # userspace
CURRENT_PATH ?= $(shell pwd)
LINUX_KERNEL ?= $(shell uname -r)
LINUX_KERNEL_PATH ?= /lib/modules/$(LINUX_KERNEL)/build
CURRENT_PATH := $(shell pwd)
modules:
make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
modules_install:
make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules_install
clean:
make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) clean
rm -f modules.order Module.symvers Module.markers
.PHNOY:
modules modules_install clean
endif
用户态测试程序
#include <stdlib.h>
#include <errno.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/ioctl.h>
#include <stdio.h>
#define PLR_SYNC_MAGIC 'l'
#define ADD_TYPE2 _IOR(PLR_SYNC_MAGIC, 1,int)
#define DEL_TYPE2 _IOW(PLR_SYNC_MAGIC, 2,int)
#define ADD_TYPE1 _IOW(PLR_SYNC_MAGIC, 3,struct param)
#define DEL_TYPE1 _IOW(PLR_SYNC_MAGIC, 4,struct param)
#define PRINT _IO(PLR_SYNC_MAGIC,5)
struct param{
int value;
int id;
};
int main(){
// 打开设备
int opt;
int type1_id;
int value;
int ret;
int fd = open("/dev/list_test",O_RDWR);
if (fd<0) {
perror("Failed to open the device...");
return -1;
}
struct param p;
while(~scanf("%d",&opt)) {
switch (opt) {
case 1: {
ioctl(fd, ADD_TYPE2,&type1_id);
break;
}
case 2: {
scanf("%d",&value);
ioctl(fd, DEL_TYPE2,value);
break;
}
case 3: {
scanf("%d",&value);
p.id = type1_id;
p.value = value;
ioctl(fd, ADD_TYPE1,&p);
break;
}
case 4: {
scanf("%d",&value);
p.id = type1_id;
p.value = value;
ioctl(fd, DEL_TYPE1,&p);
break;
}
case 5: {
ioctl(fd,PRINT);
}
}
}
close(fd);
return 0;
}
测试
在虚拟机进行测试
# 删除缓存数据
sudo dmesg -C
# 编译
make
# 加载模块
sudo insmod test_list.ko
# 编译
gcc -o test test.c
# 测试数据 test.log
1
3 1
3 2
1
3 3
3 4
5
4 4
5
2 1
5
# 测试, 使用sudo 因为默认添加的设备可能需要权限
sudo ./test < test.log
# 卸载模块
sudo rmmod test_list
# 查看内核输出
dmesg
更多推荐
1
0- 0
已为社区贡献3条内容
所有评论(0)