2019-12-25 17:11:14 duwenhan320712 阅读数 5

Linux内核链表

Linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的,因此不需要占用连续的内存。链表通常由若干节点组成,每个节点的结构都是一样的,由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息,而指针区用来指向链表的前继节点或者后继节点。因此,链表就是利用指针将各个节点串联起来的一种存储结构;

linux中的链表巧妙的解决了这个问题,linux的链表不是将用户数据保存在链表节点中,而是将链表节点保存在用户数据中

 

链表和静态数组的区别:

1. 链表包含的元素都是动态创建并插入链表的,在编译时不知道需要创建多少个元素。

2. 因为链表中每个节点的创建时间各不相同,所以各节点在内存中无需占用连续内存区

 

 

(1)单向链表

单向链表的指针区只包含一个指向下一个节点的指针,因此会形成一个单一方向的链表,如下代码所示。

struct list {

    int data;   /*有效数据可以是单一数据也可以是结构体数据指针等等*/

    struct list *next; /*指向下一个元素的指针*/

};

 

如图所示,单向链表具有单向移动性,也就是只能访问当前的节点的后继节点,而无法访问当前节点的前继节点,因此在实际项目中运用得比较少。

 

 

(2)双向链表

如图所示,双向链表和单向链表的区别是指针区包含了两个指针,一个指向前继节点,另一个指向后继节点,如下代码所示。

struct list {

    int data;   /*有效数据*/

    struct list *next; /*指向下一个元素的指针*/

    struct list *prev; /*指向上一个元素的指针*/

};

 

(3)Linux内核链表实现

单向链表和双向链表在实际使用中有一些局限性,如数据区必须是固定数据,而实际需求是多种多样的。这种方法无法构建一套通用的链表,因为每个不同的数据区需要一套链表。为此,Linux内核把所有链表操作方法的共同部分提取出来,把不同的部分留给代码编程者自己去处理。Linux内核实现了一套纯链表的封装,链表节点数据结构只有指针区而没有数据区,另外还封装了各种操作函数,如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。

可以看到通过list_head结构就把我们的数据层跟驱动层分开了,而内核提供的各种操作方法接口也只关心list_head这个结构,也就是具体链接的时候也只链接这个list_head结构,并不关心你数据层定义了什么类型。

Linux内核链表使用struct list_head数据结构来描述。

<include/linux/types.h>

 

struct list_head {

    struct list_head *next, *prev;

};

链表头的初始化有两种方法,一种是静态初始化,另一种动态初始化。把next和prev指针都初始化并指向自己,这样便初始化了一个带头节点的空链表。

<include/linux/list.h>

/*静态初始化*/

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

}

添加节点到一个链表中,内核提供了几个接口函数,如list_add()是把一个节点添加到表头,list_add_tail()是插入表尾。

<include/linux/list.h>

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

list_add_tail(struct list_head *new, struct list_head *head)

遍历节点的接口函数。

#define list_for_each(pos, head) \

for (pos = (head)->next; pos != (head); pos = pos->next)

那么如何获取节点本身的数据结构呢?这里还需要使用list_entry()宏

#define list_entry(ptr, type, member) \

    container_of(ptr, type, member)

container_of()宏的定义在kernel.h头文件中。

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

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

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

 

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

 

补充:

1: container_of

// 步骤1:将数字0强制转型为type*,然后取得其中的member元素((type *)0)->member  // 相当于((struct student *)0)->list

// 步骤2:定义一个临时变量__mptr,并将其也指向ptr所指向的链表节点const typeof(((type *)0)->member)*__mptr = (ptr);

// 步骤3:计算member字段距离type中第一个字段的距离,也就是type地址和member地址之间的差// offset(type, member)也是一个宏,定义如下:#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

// 步骤4:将__mptr的地址 - type地址和member地址之间的差// 其实也就是获取type的地址

 

 

2018-12-19 16:48:22 qq_35109096 阅读数 757

所有博文已迁移至个人网站:https://www.ravenxrz.ink,请勿再留言评论

linux的世界里,升级、更换内核是很经常的事情,如果你在安装系统的时候给boot分区分小了,偶尔就会出现boot分区的占用率爆掉的情况。这里给出两种删除内核的方式

2. 删除内核

2.1 方式一

step1:
如果你使用debian系发行版本的linux的话,可以使用dpkg命令(fedora系好像是rpm)来查看本机装有了哪些内核,具体命令为 :

dpkg --get-selections|grep linux

在这里插入图片描述
当然了,我才清理了内核,所以现在只有一个可用的内核版本:linux-4.15.0-42。如果你的主机上安装过多个内核的话,这里应该会显示多个才对。

step2:
接着查看当前自己使用的是哪个版本:

uname -r

在这里插入图片描述

step3:
使用 sudo apt-get purge linux-xxx 把所有不要的内核版本有关文件全部删了,如这里可以把所有包含4.15.0-42的文件删掉。

删除除当前你使用的版本的内核以外的其他内核。

之后在使用dpkg --get-selections|grep linux命令查看一下是不是已经删除了呢。

2.2 方式二

方式一适合于使用官方包管理器来升级内核版本,当我们通过源码编译来安装内核时,上述方法就不适用了,因为你使用dpkg --get-selections|grep linux命令来查看安装了那些内核时,自编译的内核是不会显示出来的,那么该如何删除这样的内核呢?

step1:
来到/boot目录:把下面红框内的文件都给删了,注意自己不需要哪些版本哈。XD

在这里插入图片描述

可以使用通配符来删除:

sudo rm *4.15.0-42*

step2:
来到/lib/modules/目录下,把不要的版本文件删除

在这里插入图片描述
(可选),查看一下/usr/src有没有源码文件,必要的话把源码也删除了

step3:
更新一下启动项: sudo update-grub

完。

2014-10-22 15:09:30 zhaojian1988 阅读数 11077

Linux中,当我们使用rmlinux上删除了大文件,但是如果有进程打开了这个大文件,却没有关闭这个文件的句柄,那么linux内核还是不会释放这个文件的磁盘空间,最后造成磁盘空间占用100%,整个系统无法正常运行。这种情况下,通过dfdu命令查找的磁盘空间,

Linux中,当我们使用rmlinux上删除了大文件,但是如果有进程打开了这个大文件,却没有关闭这个文件的句柄,那么linux内核还是不会释放这个文件的磁盘空间,最后造成磁盘空间占用100%,整个系统无法正常运行。这种情况下,通过dfdu命令查找的磁盘空间,两者是无法匹配的,可能df显示磁盘100%,而du查找目录的磁盘容量占用却很小。

遇到这种情况,基本可以断定是某些大文件被某些程序占用了,并且这些大文件已经被删除了,但是对应的文件句柄没有被某些程序关闭,造成内核无法收回这些文件占用的空间。

那么,如何查找那些文件被某些程序占用呢:

1

2

3

lsof -n | grep deleted

COMMAND     PID      USER   FD      TYPE             DEVICE        SIZE       NODE NAME

dd        31708      higkoo    1w      REG                8,2 5523705856     429590 /data/filetest (deleted)

命令:lsof -n| grep deleted打印出所有针对已删除文件的读写操作,这类操作是无效的,也正是磁盘空间莫名消失的根本原因。

解决办法:kill -9 PID   ----只需把进程删掉就能释放空间


lsof `which httpd` //那个进程在使用apache的可执行文件
lsof /etc/passwd //那个进程在占用/etc/passwd
lsof /dev/hda6 //那个进程在占用hda6
lsof /dev/cdrom //那个进程在占用光驱
lsof -c sendmail //查看sendmail进程的文件使用情况
lsof -c courier -u ^zahn //显示出那些文件被以courier打头的进程打开,但是并不属于用户zahn
lsof -p 30297 //显示那些文件被pid为30297的进程打开
lsof -D /tmp 显示所有在/tmp文件夹中打开的instance和文件的进程。但是symbol文件并不在列

lsof -u1000 //查看uid是100的用户的进程的文件使用情况
lsof -utony //查看用户tony的进程的文件使用情况
lsof -u^tony //查看不是用户tony的进程的文件使用情况(^是取反的意思)
lsof -i //显示所有打开的端口
lsof -i:80 //显示所有打开80端口的进程
lsof -i -U //显示所有打开的端口和UNIX domain文件
lsof -i UDP@[url]www.akadia.com:123 //显示那些进程打开了到www.akadia.com的UDP的123(ntp)端口的链接
lsof -i tcp@ohaha.ks.edu.tw:ftp -r //不断查看目前ftp连接的情况(-r,lsof会永远不断的执行,直到收到中断信号,+r,lsof会一直执行,直到没有档案被显示,缺省是15s刷新)
lsof -i tcp@ohaha.ks.edu.tw:ftp -n //lsof -n 不将IP转换为hostname,缺省是不加上-n参数
复制代码

2019-08-05 11:08:18 xiezhi123456 阅读数 30

链表是Linux内核最简单、最常用的一种数据结构。与数组相比,链表中可以动态插入或删除元素,在编译时不必知道要创建的元素个数。由于链表中每个元素的创建时间各不相同,因此它们在内存无须占用连续的内存单元。因为单元的不连续,所以各元素通过某种方式被链接在一起,于是,每个元素都包含一个指向下一个元素的指针。当有元素插入链表或从链表中删除元素时,只需调整下一个结点的指针就可以了。

1.链表的演化

在C语言中,一个基本的双向链表定义如下:

struct my_list{

void *data;// 数据域

struct my_list *next;//指向下一个结点的指针

struct my_list *prev;//指向前一个结点的指针

};

2.链表的定义和操作

Linux内核实现方式与众不同,对链表给出一种抽象定义。

1)链表定义

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

2)链表的声明和初始化宏

#define LIST_HEAD_INIT(name) { &(name), &(name) }   // 仅初始化

#define LIST_HEAD(name) \
                      struct list_head name = LIST_HEAD_INIT(name)   // 声明并初始化

备注:

如果要声明并初始化自己的链表头mylist_head,则直接调用LIST_HEAD:

LIST_HEAD(mylist_head);

调用之后,mylist_head的next、prev指针都初始化为指向自己,就有一个空链表。

3)在链表中添加一个结点

添加结点的函数为:

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

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

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

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

4)遍历链表

<linux/list.h>中定义遍历链表的宏:

/**
 * list_for_each    -    iterate over a list(遍历链表)
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:    the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

这种遍历仅仅是找到一个个结点在链表中的偏移位置。如何通过pos获得结点的起始地址,从而引用结点中的域?<linux/list.h>中定义list_entry宏:

/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:    the type of the struct this is embedded in.
 * @member:    the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

指针ptr指向结构体type中的成员member;通过指针ptr,返回结构体type的起始地址,也就是list_entry返回指向type类型的指针。

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:        the pointer to the member.
 * @type:       the type of the container struct this is embedded in.
 * @member:     the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

作用:通过结构体变量中某个成员的首地址来获得整个结构体变量的首地址

用于从包含在某个结构体中的指针获得结构体本身的指针。

1.6.3 链表的应用

#include <linux/module.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/slab.h>

#define N 10    // 链表结点个数

typedef struct numlist_st{
    int num;                // 数据
    struct list_head list;    // 指向双链表前后结点的指针
}numlist_st_t;

numlist_st_t numhead;        // 头结点
/** 
 * __init宏告诉编译程序相关的函数和变量仅用于初始化,
 * 编译程序将标有__init的所有代码存储到特殊的内存段中,
 * 初始化结束后就释放这段内存 
 */
static int __init lkp_init(void)
{
    numlist_st_t *listnode;                // 每次申请链表结点时所用的指针
    int i;
    struct list_head *pos;
    numlist_st_t *p;

    printk("doublelist is starting...\n");


    INIT_LIST_HEAD(&numhead.list);
    // 建立N个结点,依次加入到链表中
    for(i = 0; i < N; i++) {
        listnode = (numlist_st_t *)kmalloc(sizeof(numlist_st_t), GFP_KERNEL);
        listnode->num = i + 1;
        list_add_tail(&listnode->list, &numhead.list);
        printk("Node %d has added to the doublelist...\n", i + 1);
    }

    // 遍历链表
    i = 1;
    list_for_each(pos, &numhead.list){
        p = list_entry(pos, numlist_st_t, list);
        printk("Node %d's data:%d\n", i, p->num);
        i++;
    }
    
    return 0;
}

static void __exit lkp_exit(void)
{
    int i;
    struct list_head *pos, *n;
    numlist_st_t *p;


    // 依次删除N个结点
    i = 1;
    list_for_each_safe(pos, n, &numhead.list){    // 为了安全删除结点而进行的遍历
        list_del(pos);                            // 从双链表中删除当前结点
        p = list_entry(pos, numlist_st_t, list);// 得到当前数据结点的首地址,即指针
        kfree(p);
        printk("Node %d has removed from the doublelist...\n", i++);
    }

    printk("doublelist is exiting...\n");
}


/* lkp_init模块的初始化函数 */
module_init(lkp_init);
/* lkp_exit模块的退出和清理函数 */
module_exit(lkp_exit);

/* 告诉内核该模块具有GNU公共许可证 */
MODULE_LICENSE("GPL");
MODULE_VERSION("v1.0");
MODULE_AUTHOR("xz@vichip.com.cn");
执行结果

1、加载内核模块

sudo insmod test.ko

2、查看已安装的内核模块

lsmod

3、卸载内核模块

sudo rmmod test

4、查看消息

dmesg

[  491.475028] doublelist is starting...
[  491.475028] Node 1 has added to the doublelist...
[  491.475029] Node 2 has added to the doublelist...
[  491.475029] Node 3 has added to the doublelist...
[  491.475029] Node 4 has added to the doublelist...
[  491.475030] Node 5 has added to the doublelist...
[  491.475030] Node 6 has added to the doublelist...
[  491.475030] Node 7 has added to the doublelist...
[  491.475030] Node 8 has added to the doublelist...
[  491.475031] Node 9 has added to the doublelist...
[  491.475031] Node 10 has added to the doublelist...
[  491.475032] Node 1's data:1
[  491.475032] Node 2's data:2
[  491.475032] Node 3's data:3
[  491.475033] Node 4's data:4
[  491.475033] Node 5's data:5
[  491.475034] Node 6's data:6
[  491.475034] Node 7's data:7
[  491.475034] Node 8's data:8
[  491.475035] Node 9's data:9
[  491.475035] Node 10's data:10
[  538.061100] Node 1 has removed from the doublelist...
[  538.061102] Node 2 has removed from the doublelist...
[  538.061102] Node 3 has removed from the doublelist...
[  538.061103] Node 4 has removed from the doublelist...
[  538.061103] Node 5 has removed from the doublelist...
[  538.061104] Node 6 has removed from the doublelist...
[  538.061104] Node 7 has removed from the doublelist...
[  538.061105] Node 8 has removed from the doublelist...
[  538.061105] Node 9 has removed from the doublelist...
[  538.061106] Node 10 has removed from the doublelist...
[  538.061106] doublelist is exiting...

 

/**
 * list_for_each_safe - iterate over a list safe against removal of list entry
 * @pos:    the &struct list_head to use as a loop cursor.
 * @n:        another &struct list_head to use as temporary storage
 * @head:    the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

备注:

采用一个同pos同样类型的指针n来暂存将要被删除的结点指针pos,从而使得操作不影响pos指针。

2019-04-08 21:41:56 u010521366 阅读数 69

第六章 内核数据结构

小结:

  • 链表:环形双向链表,container_of, list_for_each(), list_for_each_entry
  • 队列: kfifo
  • 映射: uid映射到指针
  • 二叉树:rbtree
  • 其他:基树,位图,散列表

6.1 链表

特点:(1). 动态创建,不需要知道具体多少个元素;(2). 无需占用连续内存区;(3). 加入或删除链表时调整节点指针即可。

  1. 单向链表和双向链表,环形链表(将尾指针指向链表首指针)
    linux的标准链表就是采用环形双向链表

6.1.4 linux内核中的实现

linux不是将数据结构塞入链表,而是将链表塞入数据结构

  1. 链表数据结构简介
    <linux/list.h>中声明:
struct list_head{
	struct list_head *next;
	struct list_head *prev;
};

(1). 链表塞入数据结构

struct fox{
	unsigned long weight;
	struct list_head list;
};

linux中list操作函数统一特点:只接受list_head结构作为参数

  • container_of()通过一个结构变量中一个成员的地址找到这个结构体变量的首地址
#define container_of(ptr, type, member)({							\
	const typeof(((type *)0)->member) *__mptr = (ptr);				\		//检查ptr是否是指向结构成员member的
	(type *) ( ( char* __mptr - offsetof(type, member) );})
  • list_entry(): 返回包括list_head的父类型结构体,内核提供了创建、操作以及其他链表管理的各种例程 - 所有这些方法都不需要知道list_head所嵌入对象的数据结构
#define list_entry(ptr, type, member) 	\
		container_of(ptr, type, member)
  1. 定义一个链表
    动态创建: INIT_LIST_HEAD(&red_fox->list);
    静态创建:LIST_HEAD_INIT(red_fox.list);
  2. 链表头
    定义并初始化一个fox_list的链表例程:static LIST_HEAD(fox_list);
    其实linux链表是环形链表,可以用任意节点作为头。
  3. 操作链表
  • head后增加一个节点:list_add(struct list_head *new, struct list_head *head);如:list_add(&f->list, &fox_list)
  • head前增加一个节点:list_add_tail(xxx new, xxx head)
  • 删除一个节点:list_del(struct list_head *entry),但不包括释放entry的数据结构
  • 删除一个节点并重新初始化:list_del_init(struct list_head* entry),重用entry
  • 移动链表到head后:list_move(struct list_head *list, struct list_head *head)
  • 移动链表到head头(即另一个链表的末尾):list_move_tail(struct list_head *list, struct list_head *head)
  • 检查链表是否为空:list_empty(struct list_head *head)
  • 合并链表(插入head后面):list_splice(struct list_head *list, struct list_head *head)
  • 合并,并初始化原来的链表:list_splice_init(struct list_head *list, struct list_head *head)
  • 遍历链表:list_for_each()宏,p为当前项指针,list为需要遍历的链表
struct list_head *p;
struct fox *f;
list_for_each(p, &for_list){
	f = list_entry(p, struct fox, list);	//	得到所需的fox结构体
}
  • 遍历链表2:list_for_each_entry(pos, head, member), 这里的pos是节点对象的指针
struct fox *f;
list_for_each_entry(f, &fox_list, list){	//f指向下一个fox结构
}
  • 反向遍历链表:list_for_each_entry_reverse(pos, head, member)
  • 遍历的同时删除:list_for_each_entry_safe()启用next指针将下一项存进表中,以使得能安全删除当前项。仍然需要锁定,如果有其他并发操作,在删除时需要加锁.
  • 遍历的反向删除:list_for_each_entry_safe_reverse(pos, n ,head, member)

6.2 队列

内核通过队列实现kfifo。

6.2.1 kfifo

两个主要操作:enqueue和dequeue

  1. 创建队列:
    动态创建:int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);创建并初始化大小为size的kfifo.
    自行分配缓冲区:void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size);创建并初始化一个kfifo对象,使用由buffer指向的size字节的内存
    静态声明:DECLARE_KFIFO(name, size); INIT_KFIFO(name);
  2. 入队
    unsigned int kfifo_in(struct kfifo *fifo, const void* from, unsigned int len);将from指针所指的len字节拷入fifo
  3. 出队
    unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len);到to的缓冲区
  4. 查看但不出队: kfifo_out_peek(fifo, to, len, offset);
  5. 获取队列长度:
    kfifo_size() - 队列中间总大小
    kfifo_len() - 已入队数据大小
    kfifo_avail() - 还有多少可用空间
    kfifo_is_empty()/ kfifo_is_full()
  6. 重置或撤销队列
    kfifo_reset() - 重置 kfifo
    kfifo_free() - 撤销队列

6.3 映射

key-value
linux内核提供一个映射数据结构idr,将一个唯一的标识数(UID)映射到一个指针,如将一个inodify watch的描述符或POSIX定时器ID映射到内核相关的数据结构上。

  1. 初始化一个idr
    struct idr id_huh; //静态定义idr结构
    idr_init(&id_huh); //初始化idr结构
  2. 分配一个新的UID
    包括两步:(1). 告诉idr你需要分配新的UID,允许其在必要时调整后备树的大小;(2). 真正请求新的UID。
    (1). idr_pre_get()
    (2). idr_get_new(struct idr* idp, void *ptr, int *id); 使用idp所指向的idr去分配一个新的UID,且将其关联到指针ptr上,新的UID放入id中
    (2). idr_get_new_above(),同上,除了它确保新的UID大于或等于一个starting_id。
  3. 查找UID
    void * idr_find(idp, id);返回id关联的指针
  4. 删除UID
    idr_remove(idp, id);
  5. 撤销idr
    void idr_destroy(idp);只释放idr中未使用的内存
    void idr_remove_all(idp); 强制删除所有UID

6.4 二叉树

6.4.2 红黑树

linux实现的红黑树称为rbtree,定义在lib/rbtree.c中

  1. 初始化:初始化为特殊值RB_ROOTS
    struct rb_root root = RB_ROOT;
    rbtree的实现没有提供搜索和插入例程,自己定义,但rbtree提供了辅助函数,如rb_link_node() 插入,rb_insert_color() 执行再平衡操作

6.5 数据结构以及选择

  1. 遍历 - 链表
  2. 生产者/消费者模式 - 队列
  3. UID与对象关联 - 映射
  4. 大量数据的检索 - 红黑树
  5. 其他:基树(trie类型),位图,散列表
没有更多推荐了,返回首页