精华内容
下载资源
问答
  • Linux内核数据结构

    千次阅读 2019-03-19 09:50:23
    内核数据结构贯穿于整个内核代码中,这里介绍4个基本的内核数据结构。 主要内容: 链表 队列 映射 红黑树 链表 链表是linux内核中最简单,同时也是应用最广泛的数据结构。 内核中定义的是双向链表。 头文件简介 ...

    本文转自: https://www.cnblogs.com/wang_yb/archive/2013/04/16/3023892.html

    内核数据结构贯穿于整个内核代码中,这里介绍4个基本的内核数据结构。

    主要内容:

    • 链表
    • 队列
    • 映射
    • 红黑树

    链表

    链表是linux内核中最简单,同时也是应用最广泛的数据结构。

    内核中定义的是双向链表。

    头文件简介
    内核中关于链表定义的代码位于: include/linux/list.h

    list.h 文件中对每个函数都有注释,这里就不详细说了。

    其实刚开始只要先了解一个常用的链表操作(追加,删除,遍历)的实现方法,

    其他方法基本都是基于这些常用操作的。

    链表代码的注意点
    在阅读 list.h 文件之前,有一点必须注意:linux内核中的链表使用方法和一般数据结构中定义的链表是有所不同的。

    一般的双向链表一般是如下的结构,

    • 有个单独的头结点(head)
    • 每个节点(node)除了包含必要的数据之外,还有2个指针(pre,next)
    • pre指针指向前一个节点(node),next指针指向后一个节点(node)
    • 头结点(head)的pre指针指向链表的最后一个节点
    • 最后一个节点的next指针指向头结点(head)

    具体见下图:
    在这里插入图片描述
    传统的链表有个最大的缺点就是不好共通化,因为每个node中的data1,data2等等都是不确定的(无论是个数还是类型)。

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

    linux的链表节点只有2个指针(pre和next),这样的话,链表的节点将独立于用户数据之外,便于实现链表的共同操作。

    具体见下图:
    在这里插入图片描述

    整个list.h文件中,我觉得最复杂的代码就是获取用户数据的宏定义

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

    这个宏没什么特别的,主要是container_of这个宏

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

    这里面的type一般是个结构体,也就是包含用户数据和链表节点的结构体。

    ptr是指向type中链表节点的指针

    member则是type中定义链表节点是用的名字

    比如:

    struct student
    {
        int id;
        char* name;
        struct list_head list;
    };
    
    • type 是 struct student ptr 是指向 stuct
    • list 的指针,也就是指向 member 类型的指针
    • member 就是 list

    下面分析一下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的地址
    

    步骤1,2,4比较容易理解,下面的图以sturct student为例进行说明步骤3:

    首先需要知道 ((TYPE *)0) 表示将地址0转换为 TYPE 类型的地址

    由于TYPE的地址是0,所以((TYPE *)0)->MEMBER 也就是 MEMBER的地址和TYPE地址的差,如下图所示:

    在这里插入图片描述
    使用示例
    构造了一个内核模块来实际使用一下内核中的链表,代码在CentOS6.3 x64上运行通过。

    C代码:

    #include<linux/init.h>
    #include<linux/slab.h>
    #include<linux/module.h>
    #include<linux/kernel.h>
    #include<linux/list.h>
    
    MODULE_LICENSE("Dual BSD/GPL");
    struct student
    {
        int id;
        char* name;
        struct list_head list;
    };
    
    void print_student(struct student*);
    
    static int testlist_init(void)
    {
        struct student *stu1, *stu2, *stu3, *stu4;
        struct student *stu;
        
        // init a list head
        LIST_HEAD(stu_head);
    
        // init four list nodes
        stu1 = kmalloc(sizeof(*stu1), GFP_KERNEL);
        stu1->id = 1;
        stu1->name = "wyb";
        INIT_LIST_HEAD(&stu1->list);
    
        stu2 = kmalloc(sizeof(*stu2), GFP_KERNEL);
        stu2->id = 2;
        stu2->name = "wyb2";
        INIT_LIST_HEAD(&stu2->list);
    
        stu3 = kmalloc(sizeof(*stu3), GFP_KERNEL);
        stu3->id = 3;
        stu3->name = "wyb3";
        INIT_LIST_HEAD(&stu3->list);
    
        stu4 = kmalloc(sizeof(*stu4), GFP_KERNEL);
        stu4->id = 4;
        stu4->name = "wyb4";
        INIT_LIST_HEAD(&stu4->list);
    
        // add the four nodes to head
        list_add (&stu1->list, &stu_head);
        list_add (&stu2->list, &stu_head);
        list_add (&stu3->list, &stu_head);
        list_add (&stu4->list, &stu_head);
    
        // print each student from 4 to 1
        list_for_each_entry(stu, &stu_head, list)
        {
            print_student(stu);
        }
        // print each student from 1 to 4
        list_for_each_entry_reverse(stu, &stu_head, list)
        {
            print_student(stu);
        }
    
        // delete a entry stu2
        list_del(&stu2->list);
        list_for_each_entry(stu, &stu_head, list)
        {
            print_student(stu);
        }
    
        // replace stu3 with stu2
        list_replace(&stu3->list, &stu2->list);
        list_for_each_entry(stu, &stu_head, list)
        {
            print_student(stu);
        }
    
        return 0;
    }
    
    static void testlist_exit(void)
    {
        printk(KERN_ALERT "*************************\n");
        printk(KERN_ALERT "testlist is exited!\n");
        printk(KERN_ALERT "*************************\n");
    }
    
    void print_student(struct student *stu)
    {
        printk (KERN_ALERT "======================\n");
        printk (KERN_ALERT "id  =%d\n", stu->id);
        printk (KERN_ALERT "name=%s\n", stu->name);
        printk (KERN_ALERT "======================\n");
    }
    
    module_init(testlist_init);
    module_exit(testlist_exit);
    

    Makefile:

    obj-m += testlist.o
    
    #generate the path
    CURRENT_PATH:=$(shell pwd)
    #the current kernel version number
    LINUX_KERNEL:=$(shell uname -r)
    #the absolute path
    LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
    #complie object
    all:
        make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
    #clean
    clean:
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned
    

    安装,卸载内核模块以及查看内核模块的运行结果:

    insmod testlist.ko
    rmmod testlist
    dmesg | tail -100
    

    队列

    内核中的队列是以字节形式保存数据的,所以获取数据的时候,需要知道数据的大小。

    如果从队列中取得数据时指定的大小不对的话,取得数据会不完整或过大。

    头文件简介
    内核中关于队列定义的头文件位于:<linux/kfifo.h> include/linux/kfifo.h

    头文件中定义的函数的实现位于:kernel/kfifo.c

    队列代码的注意点
    内核队列编程需要注意的是:

    1. 队列的size在初始化时,始终设定为2的n次方
    2. 使用队列之前将队列结构体中的锁(spinlock)释放

    使用示例
    构造了一个内核模块来实际使用一下内核中的队列,代码在CentOS6.3 x64上运行通过。

    C代码:

    #include "kn_common.h"
    
    MODULE_LICENSE("Dual BSD/GPL");
    struct student
    {
        int id;
        char* name;
    };
    
    static void print_student(struct student*);
    
    static int testkfifo_init(void)
    {
        struct kfifo *fifo;
        struct student *stu1, *stu2, *stu3, *stu4;
        struct student *stu_tmp;
        char* c_tmp;
        int i;
        // !!importent  init a unlocked lock
        spinlock_t sl = SPIN_LOCK_UNLOCKED;
    
        // init kfifo
        fifo = kfifo_alloc(4*sizeof(struct student), GFP_KERNEL, &sl);
        
        stu1 = kmalloc(sizeof(struct student), GFP_KERNEL);
        stu1->id = 1;
        stu1->name = "wyb1";
        kfifo_put(fifo, (char *)stu1, sizeof(struct student));
    
        stu2 = kmalloc(sizeof(struct student), GFP_KERNEL);
        stu2->id = 1;
        stu2->name = "wyb2";
        kfifo_put(fifo, (char *)stu2, sizeof(struct student));
    
        stu3 = kmalloc(sizeof(struct student), GFP_KERNEL);
        stu3->id = 1;
        stu3->name = "wyb3";
        kfifo_put(fifo, (char *)stu3, sizeof(struct student));
    
        stu4 = kmalloc(sizeof(struct student), GFP_KERNEL);
        stu4->id = 1;
        stu4->name = "wyb4";
        kfifo_put(fifo, (char *)stu4, sizeof(struct student));
    
        c_tmp = kmalloc(sizeof(struct student), GFP_KERNEL);
        printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
        for (i=0; i < 4; i++) {
    
            kfifo_get(fifo, c_tmp, sizeof(struct student));
            stu_tmp = (struct student *)c_tmp;
            print_student(stu_tmp);
            printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
        }
        
        printk(KERN_ALERT "current fifo length is : %d\n", kfifo_len(fifo));
        kfifo_free(fifo);
        kfree(c_tmp);
        return 0;
    }
    
    static void print_student(struct student *stu)
    {
        printk(KERN_ALERT "=========================\n");
        print_current_time(1);
        printk(KERN_ALERT "id = %d\n", stu->id);
        printk(KERN_ALERT "name = %s\n", stu->name);
        printk(KERN_ALERT "=========================\n");
    }
    
    static void testkfifo_exit(void)
    {
        printk(KERN_ALERT "*************************\n");
        printk(KERN_ALERT "testkfifo is exited!\n");
        printk(KERN_ALERT "*************************\n");
    }
    
    module_init(testkfifo_init);
    module_exit(testkfifo_exit);
    

    其中引用的kn_common.h文件:

    #include<linux/init.h>
    #include<linux/slab.h>
    #include<linux/module.h>
    #include<linux/kernel.h>
    #include<linux/kfifo.h>
    #include<linux/time.h>
    
    void print_current_time(int);
    

    kn_common.h 对应的 kn_common.c:

    #include "kn_common.h"
    
    void print_current_time(int is_new_line)
    {
        struct timeval *tv;
        struct tm *t;
        tv = kmalloc(sizeof(struct timeval), GFP_KERNEL);
        t = kmalloc(sizeof(struct tm), GFP_KERNEL);
    
        do_gettimeofday(tv);
        time_to_tm(tv->tv_sec, 0, t);
    
        printk(KERN_ALERT "%ld-%d-%d %d:%d:%d",
               t->tm_year + 1900,
               t->tm_mon + 1,
               t->tm_mday,
               (t->tm_hour + 8) % 24,
               t->tm_min,
               t->tm_sec);
    
        if (is_new_line == 1)
            printk(KERN_ALERT "\n");
        
        kfree(tv);
        kfree(t);
    }
    

    Makefile:

    obj-m += fifo.o
    fifo-objs := testkfifo.o kn_common.o
    
    #generate the path
    CURRENT_PATH:=$(shell pwd)
    #the current kernel version number
    LINUX_KERNEL:=$(shell uname -r)
    #the absolute path
    LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
    #complie object
    all:
        make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
    #clean
    clean:
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned
    

    映射

    映射的有点想其他语言(C#或者python)中的字典类型,每个唯一的id对应一个自定义的数据结构。

    头文件简介
    内核中关于映射定义的头文件位于:<linux/idr.h> include/linux/idr.h

    头文件中定义的函数的实现位于:lib/idr.c

    映射代码的注意点
    映射的使用需要注意的是,给自定义的数据结构申请一个id的时候,不能直接申请id,先要分配id(函数idr_pre_get),分配成功后,在获取一个id(函数idr_get_new)。

    idr的结构比较复杂,我也没有很好的理解,但是csdn上有篇介绍linux idr结构的博客写的挺好,图文并茂:http://blog.csdn.net/paomadi/article/details/8539794

    使用示例
    构造了一个内核模块来实际使用一下内核中的映射,代码在CentOS6.3 x64上运行通过。

    C代码:

    #include<linux/idr.h>
    #include "kn_common.h"
    
    MODULE_LICENSE("Dual BSD/GPL");
    struct student
    {
        int id;
        char* name;
    };
    
    static int print_student(int, void*, void*);
    
    static int testidr_init(void)
    {
        DEFINE_IDR(idp);
        struct student *stu[4];
        //    struct student *stu_tmp;
        int id, ret, i;
    
        // init 4 struct student
        for (i=0; i<4; i++) {
    
            stu[i] = kmalloc(sizeof(struct student), GFP_KERNEL);
            stu[i]->id = i;
            stu[i]->name = "wyb";
        }
    
        // add 4 student to idr
        print_current_time(0);
        for (i=0; i < 4; i++) {
    
            do {
                if (!idr_pre_get(&idp, GFP_KERNEL))
                    return -ENOSPC;
                ret = idr_get_new(&idp, stu[i], &id);
                printk(KERN_ALERT "id=%d\n", id);
            } while(ret == -EAGAIN);
        }
    
        // display all student in idr
        idr_for_each(&idp, print_student, NULL);
    
        idr_destroy(&idp);
        kfree(stu[0]);
        kfree(stu[1]);
        kfree(stu[2]);
        kfree(stu[3]);
        return 0;
    }
    
    static int print_student(int id, void *p, void *data)
    {
        struct student* stu = p;
           
        printk(KERN_ALERT "=========================\n");
        print_current_time(0);
        printk(KERN_ALERT "id = %d\n", stu->id);
        printk(KERN_ALERT "name = %s\n", stu->name);
        printk(KERN_ALERT "=========================\n");
    
        return 0;
    }
    
    static void testidr_exit(void)
    {
        printk(KERN_ALERT "*************************\n");
        print_current_time(0);
        printk(KERN_ALERT "testidr is exited!\n");
        printk(KERN_ALERT "*************************\n");
    }
    
    module_init(testidr_init);
    module_exit(testidr_exit);
    

    注:其中用到的kn_common.h和kn_common.c文件与队列的示例中一样。

    Makefile:

    obj-m += idr.o
    idr-objs := testidr.o kn_common.o
    
    #generate the path
    CURRENT_PATH:=$(shell pwd)
    #the current kernel version number
    LINUX_KERNEL:=$(shell uname -r)
    #the absolute path
    LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
    #complie object
    all:
        make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
    #clean
    clean:
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned
    

    安装,卸载内核模块以及查看内核模块的运行结果:

    insmod idr.ko
    rmmod idr
    dmesg | tail -30
    

    红黑树

    红黑树由于节点颜色的特性,保证其是一种自平衡的二叉搜索树。

    红黑树的一系列规则虽然实现起来比较复杂,但是遵循起来却比较简单,而且红黑树的插入,删除性能也还不错。

    所以红黑树在内核中的应用非常广泛,掌握好红黑树,即有利于阅读内核源码,也可以在自己的代码中借鉴这种数据结构。

    红黑树必须满足的规则:

    • 所有节点都有颜色,要么红色,要么黑色
    • 根节点是黑色,所有叶子节点也是黑色
    • 叶子节点中不包含数据
    • 非叶子节点都有2个子节点
    • 如果一个节点是红色,那么它的父节点和子节点都是黑色的
    • 从任何一个节点开始,到其下叶子节点的路径中都包含相同数目的黑节点

    红黑树中最长的路径就是红黑交替的路径,最短的路径是全黑节点的路径,再加上根节点和叶子节点都是黑色,从而可以保证红黑树中最长路径的长度不会超过最短路径的2倍。

    头文件简介
    内核中关于红黑树定义的头文件位于:<linux/rbtree.h> include/linux/rbtree.h

    头文件中定义的函数的实现位于:lib/rbtree.c

    红黑树代码的注意点
    内核中红黑树的使用和链表(list)有些类似,是将红黑树的节点放入自定义的数据结构中来使用的。

    首先需要注意的一点是红黑树节点的定义:

    struct rb_node
    {
        unsigned long  rb_parent_color;
    #define    RB_RED        0
    #define    RB_BLACK    1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
    } __attribute__((aligned(sizeof(long))));
    

    刚开始看到这个定义的时候,我觉得很奇怪,等到看懂了之后,才知道原来作者巧妙的利用内存对齐来将2个内容存入到一个字段中(不服不行啊_!)。

    字段 rb_parent_color 中保存了2个信息:

    1. 父节点的地址
    2. 本节点的颜色

    这2个信息是如何存入一个字段的呢?主要在于 __attribute__((aligned(sizeof(long))));

    这行代码的意思就是 struct rb_node 在内存中的地址需要按照4 bytes或者8 bytes对齐。

    注:sizeof(long) 在32bit系统中是4 bytes,在64bit系统中是8 bytes。

    struct rb_node的地址按4 bytes对齐,意味着分配的地址都是4的倍数。

    4 的二进制为 100 ,所以申请分配的 struct rb_node 的地址的最后2位始终是零,

    struct rb_node 的字段 rb_parent_color 就是利用最后一位来保存节点的颜色信息的。

    明白了这点之后,rb_tree.h 中很多宏的定义也就很好懂了。

    /* rb_parent_color 保存了父节点的地址和本节点的颜色 */
    
    /* 将 rb_parent_color 的最后2位置成0,即将颜色信息去掉,剩下的就是parent节点的地址 */
    #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
    
    /* 取得 rb_parent_color 二进制表示的最后一位,即用于保存颜色信息的那一位 */
    #define rb_color(r)   ((r)->rb_parent_color & 1)
    
    /* 将 rb_parent_color 二进制表示的最后一位置为0,即置为红色 */
    #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
    
    /* 将 rb_parent_color 二进制表示的最后一位置为1,即置为黑色 */
    #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
    

    还有需要重点看的就是rb_tree.c中的5个函数,下面对这5个函数进行一些注释:

    函数1:左旋操作,当右子树的长度过大导致树不平衡时,进行左旋操作

    /*
     *  左旋操作其实就3个动作:见图left
     *  1. node的右子树关联到right的左子树
     *  2. right的左子树关联到node
     *  3. right取代node的位置
     *  其他带代码都是一些相应的parent指针的变化
     */
    static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
    {
        /* 初始化相对于node节点的父节点(图中的P)和右节点(图中的R) */
        struct rb_node *right = node->rb_right;
        struct rb_node *parent = rb_parent(node);
    
        /* 步骤1  */
        if ((node->rb_right = right->rb_left))
            rb_set_parent(right->rb_left, node);
    
        /* 步骤2 */
        right->rb_left = node;
        rb_set_parent(right, parent);
    
        /* node的parent NOT NULL 时,right取代原先的node的位置 */
        if (parent)
        {
            if (node == parent->rb_left)
                parent->rb_left = right;
            else
                parent->rb_right = right;
        }
    
        /* node的parent NULL 时,说明node原先时root节点,将新的root指向root即可 */
        else
            root->rb_node = right;
        rb_set_parent(node, right);
    }
    

    左旋操作图解:
    在这里插入图片描述
    函数2:右旋操作,和左旋操作类似。

    函数3:追加节点后,设置此节点的颜色。

    /*
     *  本函数没有插入节点的功能,只是在插入新节点后,设置新节点的颜色,从而保证红黑树的平衡性。
     *  新插入的节点默认都是红色的。
     *  
     *  下面的代码看着复杂,其实只要时时记住红黑树的几个重要特性,就会发现下面的都是在尽量保持住红黑树的这些特性。
     *  1. 无论从哪个节点开始,到其叶子节点的路径中包含的黑色节点个数时一样的
     *  2. 不能有连续的2个红色节点,即父节点和子节点不能同时为红色
     *  所以最简单的情况就是:插入节点的父节点是黑色的。那么插入一个红节点后不会有任何影响。
     *  3. 左旋操作有减少右子树高度的作用
     *  4. 同理,右旋操作有减少左子树高度的作用
     */
    void rb_insert_color(struct rb_node *node, struct rb_root *root)
    {
        struct rb_node *parent, *gparent;
    
        while ((parent = rb_parent(node)) && rb_is_red(parent))
        {
            gparent = rb_parent(parent);
    
            /* parent 是 gparent的左子树时 */
            if (parent == gparent->rb_left)
            {
                {
                    /* gparent的左右子树的黑色节点都增加一个,仍然平衡 */
                    register struct rb_node *uncle = gparent->rb_right;
                    if (uncle && rb_is_red(uncle))
                    {
                        rb_set_black(uncle);
                        rb_set_black(parent);
                        rb_set_red(gparent);
                        node = gparent;
                        continue;
                    }
                }
    
                /* node为parent右子树时 */
                if (parent->rb_right == node)
                {
                    register struct rb_node *tmp;
                    /* 左旋后,parent的位置被node取代,然后再交换parent和node的位置,
                     * 相当于node是parent的左子树
                     * 由于node和parent都是红色(否则到不了这一步),parent左右子树的黑色节点数仍然是相等的
                     */
                    __rb_rotate_left(parent, root);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }
    
                /* parent 红->黑,gparent左子树比右子树多一个黑色节点
                 * 右旋后,gparent左子树高度减一,减少的节点即parent,减少了一个黑色节点,parent变为新的gparent。
                 * 所以右旋后,新的gparent的左右子树的黑色节点数再次平衡了
                 */
                rb_set_black(parent);
                rb_set_red(gparent);
                __rb_rotate_right(gparent, root);
            /* parent 是 gparent的右子树时,和上面的过程类似 */
            } else {
                {
                    register struct rb_node *uncle = gparent->rb_left;
                    if (uncle && rb_is_red(uncle))
                    {
                        rb_set_black(uncle);
                        rb_set_black(parent);
                        rb_set_red(gparent);
                        node = gparent;
                        continue;
                    }
                }
    
                if (parent->rb_left == node)
                {
                    register struct rb_node *tmp;
                    __rb_rotate_right(parent, root);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }
    
                rb_set_black(parent);
                rb_set_red(gparent);
                __rb_rotate_left(gparent, root);
            }
        }
    
        rb_set_black(root->rb_node);
    }
    

    函数4:删除一个节点,并且调整删除后各节点的颜色。其中调整节点颜色其实是另一个单独的函数。

    /* 删除节点时,如果被删除的节点左子树==NULL或右子树==NULL或左右子树都==NULL
     * 那么只要把被删除节点的左子树或右子树直接关联到被删节点的父节点上即可,剩下的就是调整各节点颜色。
     * 只有被删节点是黑色才需要调整颜色,因为删除红色节点不影响红黑树的特性。
     *
     * 被删节点左右子树都存在的情况下,其实就是用中序遍历中被删节点的下一个节点来替代被删节点。
     * 代码中的操作只是将各个指针指向新的位置而已。
     */
    void rb_erase(struct rb_node *node, struct rb_root *root)
    {
        struct rb_node *child, *parent;
        int color;
    
        if (!node->rb_left)
            child = node->rb_right;
        else if (!node->rb_right)
            child = node->rb_left;
        else
        {
            struct rb_node *old = node, *left;
    
            /* 寻找中序遍历中被删节点的下一个节点 */
            node = node->rb_right;
            while ((left = node->rb_left) != NULL)
                node = left;
    
            /* 替换要删除的节点old */
            if (rb_parent(old)) {
                if (rb_parent(old)->rb_left == old)
                    rb_parent(old)->rb_left = node;
                else
                    rb_parent(old)->rb_right = node;
            } else
                root->rb_node = node;
    
            child = node->rb_right;
            parent = rb_parent(node);
            color = rb_color(node);
    
            if (parent == old) {
                parent = node;
            } else {
                if (child)
                    rb_set_parent(child, parent);
                parent->rb_left = child;
    
                node->rb_right = old->rb_right;
                rb_set_parent(old->rb_right, node);
            }
    
            node->rb_parent_color = old->rb_parent_color;
            node->rb_left = old->rb_left;
            rb_set_parent(old->rb_left, node);
    
            goto color;
        }
    
        parent = rb_parent(node);
        color = rb_color(node);
    
        if (child)
            rb_set_parent(child, parent);
        if (parent)
        {
            if (parent->rb_left == node)
                parent->rb_left = child;
            else
                parent->rb_right = child;
        }
        else
            root->rb_node = child;
    
     color:
        if (color == RB_BLACK)
            __rb_erase_color(child, parent, root);
    }
    

    函数5:删除一个黑色节点后,重新调整相关节点的颜色。

    /* 这里的node就是上面函数中的child,所有node节点的左右子树肯定都是NULL
     * 不满足红黑树规则的就是从parent节点开始的子树,只要给从parent开始的子树增加一个黑色节点就行
     * 如果从parent节点开始的节点全是黑色,node和parent都继续向上移动
     */
    static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                     struct rb_root *root)
    {
        struct rb_node *other;
    
        /* (node不为NULL 且 node是黑色的) 或者 node == NULL */
        while ((!node || rb_is_black(node)) && node != root->rb_node)
        {
            if (parent->rb_left == node)
            {
                other = parent->rb_right;
                if (rb_is_red(other))
                {
                    rb_set_black(other);
                    rb_set_red(parent);
                    __rb_rotate_left(parent, root);
                    other = parent->rb_right;
                }
                /* 如果从parent节点开始的节点全是黑色,node和parent都继续向上移动 */
                if ((!other->rb_left || rb_is_black(other->rb_left)) &&
                    (!other->rb_right || rb_is_black(other->rb_right)))
                {
                    rb_set_red(other);
                    node = parent;
                    parent = rb_parent(node);
                }
                else
                {
                    if (!other->rb_right || rb_is_black(other->rb_right))
                    {
                        rb_set_black(other->rb_left);
                        rb_set_red(other);
                        __rb_rotate_right(other, root);
                        other = parent->rb_right;
                    }
                    rb_set_color(other, rb_color(parent));
                    rb_set_black(parent);
                    rb_set_black(other->rb_right);
                    __rb_rotate_left(parent, root);
                    node = root->rb_node;
                    break;
                }
            }
            else
            {
                other = parent->rb_left;
                if (rb_is_red(other))
                {
                    rb_set_black(other);
                    rb_set_red(parent);
                    __rb_rotate_right(parent, root);
                    other = parent->rb_left;
                }
                if ((!other->rb_left || rb_is_black(other->rb_left)) &&
                    (!other->rb_right || rb_is_black(other->rb_right)))
                {
                    rb_set_red(other);
                    node = parent;
                    parent = rb_parent(node);
                }
                else
                {
                    if (!other->rb_left || rb_is_black(other->rb_left))
                    {
                        rb_set_black(other->rb_right);
                        rb_set_red(other);
                        __rb_rotate_left(other, root);
                        other = parent->rb_left;
                    }
                    rb_set_color(other, rb_color(parent));
                    rb_set_black(parent);
                    rb_set_black(other->rb_left);
                    __rb_rotate_right(parent, root);
                    node = root->rb_node;
                    break;
                }
            }
        }
        if (node)
            rb_set_black(node);
    }
    

    使用示例
    构造了一个内核模块来实际使用一下内核中的红黑树,代码在CentOS6.3 x64上运行通过。

    C代码:

    #include<linux/rbtree.h>
    #include <linux/string.h>
    #include "kn_common.h"
    
    MODULE_LICENSE("Dual BSD/GPL");
    struct student
    {
        int id;
        char* name;
        struct rb_node node;
    };
    
    static int insert_student(struct student*, struct rb_root*);
    static int remove_student(struct student*, struct rb_root*);
    static int display_student(struct rb_root*, int);
    static void display_student_from_small(struct rb_node*);
    static void display_student_from_big(struct rb_node*);
    static void print_student(struct student*);
    
    static int testrbtree_init(void)
    {
    #define N 10
        struct rb_root root = RB_ROOT;
        struct student *stu[N];
        char tmp_name[5] = {'w', 'y', 'b', '0', '\0'};
        int i;
    
        // init N struct student
        for (i=0; i<N; i++)
        {
            stu[i] = kmalloc(sizeof(struct student), GFP_KERNEL);
            stu[i]->id = i;
            stu[i]->name = kmalloc(sizeof(char)*5, GFP_KERNEL);
            tmp_name[3] = (char)(i+48);
            strcpy(stu[i]->name, tmp_name);
            // stu_name[3] = (char)(i+48);
            stu[i]->node.rb_left = NULL;
            stu[i]->node.rb_right = NULL;
        }
    
        for (i=0; i < N; ++i)
        {
            printk(KERN_ALERT "id=%d   name=%s\n", stu[i]->id, stu[i]->name);
        }
        
        // add N student to rbtree
        print_current_time(0);
        for (i=0; i < N; i++)
            insert_student(stu[i], &root);
    
        // display all students
        printk(KERN_ALERT "print from small to big!\n");
        display_student(&root, -1);
        printk(KERN_ALERT "print from big to small!\n");
        display_student(&root, 1);
    
        // delete student 8
        remove_student(stu[7], &root);
        display_student(&root, -1);
        
        // free all student
        for (i=0; i<N; ++i)
        {
            kfree(stu[i]->name);
            kfree(stu[i]);
        }
                        
        return 0;
    }
    
    static int insert_student(struct student* stu, struct rb_root* root)
    {
        struct rb_node* parent;
        struct rb_node* tmp_rb;
        struct student* tmp_stu;
    
        /* first time to insert node */
        if (!root->rb_node) 
        {
            root->rb_node = &(stu->node);
            rb_set_parent(&(stu->node), NULL);
            rb_set_black(&(stu->node));
            return 0;
        }
    
        /* find where to insert node */
        tmp_rb = root->rb_node;
        while(tmp_rb)
        {
            parent = tmp_rb;
            tmp_stu = rb_entry(tmp_rb, struct student, node);
    
            if (tmp_stu->id > stu->id) 
                tmp_rb = parent->rb_left;
            else if (tmp_stu->id < stu->id)
                tmp_rb = parent->rb_right;
            else
                break;
        }
    
        /* the student's id  is already in the rbtree */
        if (tmp_rb)
        {
            printk(KERN_ALERT "this student has been inserted!\n");
            return 1;
        }
        
        if (tmp_stu->id > stu->id)
            parent->rb_left = &(stu->node);
        else
            parent->rb_right = &(stu->node);
    
        rb_set_parent(&(stu->node), parent);
        rb_insert_color(&(stu->node), root);
        
        return 0;
    }
    
    static int remove_student(struct student* stu, struct rb_root* root)
    {
        rb_erase(&(stu->node), root);
        
        return 0;
    }
    
    static int display_student(struct rb_root *root, int order)
    {
        if (!root->rb_node)
            return 1;
        if (order < 0)
            display_student_from_small(root->rb_node);
        else
            display_student_from_big(root->rb_node);
        
        return 0;
    }
    
    static void display_student_from_small(struct rb_node* node)
    {
        struct student *tmp_stu;
        
        if (node)
        {
            display_student_from_small(node->rb_left);
            tmp_stu = rb_entry(node, struct student, node);
            print_student(tmp_stu);
            display_student_from_small(node->rb_right);
        }
    }
    
    static void display_student_from_big(struct rb_node* node)
    {
        struct student *tmp_stu;
        
        if (node)
        {
            display_student_from_big(node->rb_right);
            tmp_stu = rb_entry(node, struct student, node);
            print_student(tmp_stu);
            display_student_from_big(node->rb_left);
        }
    }
    
    static void print_student(struct student* stu)
    {
        printk(KERN_ALERT "=========================\n");
        print_current_time(0);
        printk(KERN_ALERT "id=%d\tname=%s\n", stu->id, stu->name);
        printk(KERN_ALERT "=========================\n");
    }
    
    static void testrbtree_exit(void)
    {
        printk(KERN_ALERT "*************************\n");
        print_current_time(0);
        printk(KERN_ALERT "testrbtree is exited!\n");
        printk(KERN_ALERT "*************************\n");
            
    }
    
    module_init(testrbtree_init);
    module_exit(testrbtree_exit);
    

    注:其中用到的kn_common.h和kn_common.c文件与队列的示例中一样。

    Makefile:

    obj-m += rbtree.o
    rbtree-objs := testrbtree.o kn_common.o
    
    #generate the path
    CURRENT_PATH:=$(shell pwd)
    #the current kernel version number
    LINUX_KERNEL:=$(shell uname -r)
    #the absolute path
    LINUX_KERNEL_PATH:=/usr/src/kernels/$(LINUX_KERNEL)
    #complie object
    all:
        make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c .tmp_versions *.unsigned
    #clean
    clean:
        rm -rf modules.order Module.symvers .*.cmd *.o *.mod.c *.ko .tmp_versions *.unsigned
    

    安装,卸载内核模块以及查看内核模块的运行结果:

    insmod rbtree.ko
    rmmod rbtree
    dmesg | tail -135
    
    展开全文
  • 正如你所知道的, Linux 内核通过许多不同库以及函数提供各种数据结构以及算法。这个部分我们将介绍其中一个数据结构 Radix tree。Linux 内核中有两个文件与 radix tree 的实现和 API 相关:  include/linux/radix...
  • linux内核数据结构以及内核调试

    千次阅读 2013-11-19 21:51:10
    内核数据使用的数据类型分为 3 个主要类型 标准C类型明确大小的类型用作特定内核对象的类型 1.1.1 标准 C 类型 使用标准C类型时,必须知道它们的长度在不同架构上可能是会变的,标准C对每种类型的长度没有一个很...

    一、可移植性

    1.1 数据类型可移植性

    由于内核可能运行在不同的架构上,不同的架构具有不同的机器字长,因而可移植性对内核编程非常重要。内核数据使用的数据类型分为 3 个主要类型
    • 标准C类型
    • 明确大小的类型
    • 用作特定内核对象的类型

    1.1.1 标准 C 类型

    使用标准C类型时,必须知道它们的长度在不同架构上可能是会变的,标准C对每种类型的长度没有一个很严格的规定,对于很多类型,它们的长度都可能是会变化的。

    1.1.2明确大小的类型

    有时内核代码需要一个特定大小的数据,内核提供了下列数据类型来使用:
    u8; /* unsigned byte (8 bits) */
    u16; /* unsigned word (16 bits) */
    u32; /* unsigned 32-bit value */
    u64; /* unsigned 64-bit value */
    如果需要带符号的固定长度的类型,可以用
    s8; /* unsigned byte (8 bits) */
    s16; /* unsigned word (16 bits) */
    s32; /* unsigned 32-bit value */
    s64; /* unsigned 64-bit value */
    或者也可以使用以下数据类型:
    u_int8_t;
    u_int16_t;
    u_int32_t;
    u_int64_t

    int8_t;
    int16_t;
    int32_t;
    int64_t

    1.1.3 接口特定的类型

    内核中一些场景中使用的数据类型是特别定义的类型,使用这种类型可以具有很好的可移植性。比如进程标识符的类型时pid_t,其它的一些包括:uid_t,timer_t等等,具体的可见include/linux/types.h文件。

    2.2 时间可移植性

    对于时间可移植性来说,linux保证HZ个时钟滴答需要时间为1秒。

    2.3 页大小

    对于内存页,内核保证每个内存页大小为PAGE_SIZE。

    2.4 对齐

    当需要存取不对齐数据时(比如读写非4字节对齐的4字节值),需要考虑该问题,因为不是所有架构都支持非对齐地址上的访问。在文件asm/unaligned.h中定义了两个宏:
    get_unaligned(ptr);
    put_unaligned(val, ptr);
    用于支持这种访问。

    2.5字节序

    由于内核可能运行在不同的架构上,不同架构的字节序是不同的,编写程序时应该尽量不要依赖于字节序,当确实需要特定的字节序时,有两个方法:
    • 根据内核提供的大小端宏来编写相应代码,如果是大端模式,则内核会定义宏__BIG_ENDIAN,如果是小端模式,内核会定义宏__LITTLE_ENDIAN
    • 使用内核提供的转换函数在不同的类型之间进行转换,可以通过asm/byteorder.h文件找到最终被包含的文件并找到这些定义

    二、内核数据结构

    2.1 链表

    链表是最常见的基本数据结构,内核提供了一套操作链表的API,这些API包含了链表的所有操作。这套API定义在linux/list.h中。其中包括两个版本:
    • 常规的双向循环链表
    • 用于散列表的双向链表
    其相关数据结构如下:
    struct list_head {
    struct list_head *next, *prev;
    };

    该结构既用于常规链表的头,也用于常规链表的节点。当一个数据结构包含该结构或者指向该结构的指针时,它就可以使用常规链表的API来操作,因为API只需要该结构的地址作为参数。

    struct hlist_head {
    struct hlist_node *first;
    };

    它是用于散列表版本的链表的头部数据结构。
    struct hlist_node {
    struct hlist_node *next, **pprev;
    };
    它是用于散列表版本的链表的节点数据结构,使用该版本的链表的数据结构需要包含该结构或者指向该结构的指针,在使用链表API时,将该结构的指针作为参数传递给API即可。
    二者的区别:
    • 当使用常规版本时,需要使用链表的数据结构只需要包括一个struct list_head结构或其指针,即可使用API进行操作,链表头包含两个指针,一个指向链表尾部,一个指向链表头部。
    • 而使用用于散列表版本时,链表头使用数据结构struct hlist_head,它只包含一个链表指向链表第一个元素的指针,使用链表的数据结构需要包含的是struct hlist_node数据结构或其指针,然后即可使用API进行操作。之所以有这个区别是因为当使用散列表时,可以期望链表的长度较短,使用两个头会浪费宝贵的内存。
    • 用于散列表的版本不是循环链表
    使用用于散列表版本的链表的一个图示如下:
     
    另外需要注意的是这些API没有提供任何的同步、互斥支持。
    详细的API接口可以参考该文件。

    2.2 kref

    kref是一个引用计数器,它被嵌套进其它的结构中,记录所嵌套结构的引用计数。其定义如下:
    struct kref {
    atomic_t refcount;
    };
    它用于跟踪它所嵌入的结构的使用情况。一般情况下,当其为0时,就要执行清理动作了。
    相关API也比较简单,可以参考文件include/linux/kref.h,不过需要说明的是当调用kref_put时,如果引用计数变为了0,则kref_put会执行调用者提供的release函数,调用者可以在该函数中左自己想要的清理工作。
    初始化之后,kref的使用应该遵循以下三条规则:
    1. 如果你创建了一个该结构,除非它不给被人使用,否则必须对它调用kref_get增加引用计数。
    2. 当不在使用该结构时,必须对它调用kref_put
    3. 如果代码试图在还没拥有引用计数的情况下就调用kref_get,就必须串行化kref_put和kref_get的执行。因为很可能在kref_get执行之前或者执行中,kref_put就被调用并把整个结构释放掉了。内核的文档中给出了一个例子:
    static DEFINE_MUTEX(mutex);
    static LIST_HEAD(q);
    struct my_data
    {
    	struct kref      refcount;
    	struct list_head link;
    };
    
    static struct my_data *get_entry()
    {
    	struct my_data *entry = NULL;
    	mutex_lock(&mutex);
    	if (!list_empty(&q)) {
    		entry = container_of(q.next, struct my_data, link);
    		kref_get(&entry->refcount);
    	}
    	mutex_unlock(&mutex);
    	return entry;
    }
    
    static void release_entry(struct kref *ref)
    {
    	struct my_data *entry = container_of(ref, struct my_data, refcount);
    
    	list_del(&entry->link);
    	kfree(entry);
    }
    
    static void put_entry(struct my_data *entry)
    {
    	mutex_lock(&mutex);
    	kref_put(&entry->refcount, release_entry);
    	mutex_unlock(&mutex);
    }
    

    由于在kref_put时可能会调用提供的release函数,因此API也提供了两个其它版本的put接口:

    1. kref_put_spinlock_irqsave:该版本需要多提东一个spinlock作为参数,它保证减小ref计数和调release函数的操作在锁住该自旋锁并关闭中断的情况下进行,也就是说在SMP架构下也是中断安全的。
    1. kref_put_mutex:该版本需要多提东一个mutex作为参数,它保证减小ref计数和掉release函数的操作在该mutex的保护下进行,因而是“线程”安全的。

    2.3 klist

    klist是一种增强的链表,主要用于设备驱动模型中,它是为了适应动态变化的设备和驱动而专门设计的链表。相关数据结构定义如下:
    struct klist_node;
    struct klist {
    	spinlock_t		k_lock;
    	struct list_head	k_list;
    	void			(*get)(struct klist_node *);
    	void			(*put)(struct klist_node *);
    } __attribute__ ((aligned (sizeof(void *))));
    
    #define KLIST_INIT(_name, _get, _put)					\
    	{ .k_lock	= __SPIN_LOCK_UNLOCKED(_name.k_lock),		\
    	  .k_list	= LIST_HEAD_INIT(_name.k_list),			\
    	  .get		= _get,						\
    	  .put		= _put, }
    
    #define DEFINE_KLIST(_name, _get, _put)					\
    	struct klist _name = KLIST_INIT(_name, _get, _put)
    
    extern void klist_init(struct klist *k, void (*get)(struct klist_node *),
    		       void (*put)(struct klist_node *));
    
    struct klist_node {
    	void			*n_klist;	/* never access directly */
    	struct list_head	n_node;
    	struct kref		n_ref;
    };
    由这些数据结构可知struct klist结构是klist的链表头,klist的链表节点使用的是struct klist_node结构。
    klist链表头的四个域分别为:
    • 链表头k_list,它就是klist的链表头
    • 自旋锁k_lock,用于保护链表
    • get,引用链表中的节点时将被调用
    • put,当不在引用链表中的节点时将被调用,它和get一起维护了klist_node中的引用计数。
    klist_node包含三个域:
    • n_klist:指向节点所在的klist头,由于klist是4字节对齐的,因而该指针的最低两个比特必为0,其中第0比特有特殊用途。
    • n_node:链表元素
    • n_ref:kref引用计数,跟踪记录了该节点被引用的次数,引用次数由链表头的get和put维护。
    相关API可以查看include/linux/klist.h。
    需要说明的是:
    • klist中删除节点时,可能节点的引用计数还不为0,因此节点并不会被删除,但是有的场景下,使用者可能期望节点确实被删除后再继续进行操作,为此klist提供了两个API接口来进行删除的:
      • klist_remove,该API不仅会递减引用计数并提交删除请求,并且会等待节点确实被删除
      • klist_del,该API仅仅递减引用计数,并提交删除请求,但是不会等待,不过如果它触发了真正的删除动作,则会唤醒等待删除真正完成的任务

    另外当提交删除请求时,klist会将节点中n_klist的0比特设置为1,表示该节点已经被请求删除了,只是暂时还没真正删除。标记了该比特的节点在遍历时将会被忽略

    • 由于需要考虑被忽略的节点,即已经被请求删除的节点,因而klist的遍历稍微复杂些。它用函数实现,并用struct klist_iter记录中间状态。klist机制也提供了两个API用于遍历:
      • klist_iter_init_node用于从klist中的某个节点开始遍历,使用它初始化遍历时,可以直接访问当前节点或者用klist_next访问下一节点
      • klist_iter_init用于从链表头开始遍历的,使用它初始化遍历时,只能用klist_next访问下一节点

    2.4 红黑树

    内核在include/linux/rbtree.h中提供了红黑树API,想要使用红黑树的内核代码可以直接使用它。有兴趣的可以查看其代码。

    三、内核调试

    由于内核的特殊性,内核代码很难在调试器控制下运行,也很难跟踪,并且由于内核代码用于服务整个系统,无法简单的将某个故障与特定的“任务”关联起来,因而内核程序的调试是比较特殊的。

    3.1内核对调试的支持

    为了方便调试,内核提供了很多选项,这些选项为内核调试提供了比较丰富的调试支持,它们覆盖了内存管理、分配,内核同步、互斥,驱动子系统等等内核的基本子系统,因而对于内核开发者来说是很有用的。以下是一些其中一些选项(大多选项都位于kernel hacking菜单中)。
    • CONFIG_DEBUG_KERNEL:这个用于使能内核调试选项,它本身不激活任何调试特性。CONFIG_DEBUG_SLAB:使能内存分配的调试功能,打开该选项,则slab子系统会在申请和释放内存时进行一些检查。
    • CONFIG_DEBUG_PAGEALLOC:使能页面的分配调试。
    • CONFIG_DEBUG_SPINLOCK:使能自旋锁的调试支持,可用于检测是否存在重复解锁同
    • CONFIG_MAGIC_SYSRQ:使能"魔术 SysRq"键
    • CONFIG_DEBUG_STACKOVERFLOW:使能栈溢出的检查。
    • CONFIG_DEBUG_STACK_USAGE:使能栈使用信息的调试支持。内核会监测堆栈使用并作一些统计, 这些统计可以用魔术 SysRq 键得到
    • CONFIG_KALLSYMS和CONFIG_KALLSYMS_ALL:它们位于"Generl setup"菜单中,用于将内核符号表包含在系统中。如果没有内核符号表,则oops信息无法给出回溯的符号信息,只能给出16进制的地址信息。
    • CONFIG_IKCONFIG和CONFIG_IKCONFIG_PROC:它们位于"Generl setup"菜单中,使能它后才能在/proc/config.gz中来访问内核配置信息。
    • CONFIG_DEBUG_DRIVER:该选项在”Device Drivers->Generic Driver Options”菜单中,用于使能驱动框架的调试信息。
    • CONFIG_INPUT_EVBUG:该选项在"Device drivers-> Input device support "菜单中,它用于大卖输入事件的详细日志,需要注意的是它会记录了输入设备的所有输入,包括密码。
    • CONFIG_PROFILING:该选项位于"Profiling support"菜单中。用于打开系统系能调试跟踪的功能,它对于剖析系统系能非常有用,也可用于系统挂起的调试。
    以上只是一些例子,具体的调试选项可以查看kernel hacking菜单,里边有很多的调试支持用于支持内核开发调试。

    3.2 用log调试

    用打开来进行调试或者说用log来调试是最基本的调试手段,无论是内核还是用户程序,因为有些bug是在特定场合和应用场景下才出现的,换了环境后很难复现,而有的bug需要长时间运行才能复现,这时候一个精心设计的log系统就能起到大的用途,通过精心选择log点和所要记录的信息,我们可以收集bug现场的所有我们想要的信息,还可以跟踪bug产生的过程,因而log是一个非常重要的调试手段。
    内核中打印需要用printk来实现。

    3.2.1 printk

    printk类似于用户空间的printf,但是也有不同,printk允许调用者指定消息的log等级,系统定义的log等级定义在include/linux/kern_levels.h中,包括: 
    • KERN_EMERG:用于紧急消息, 常常是那些崩溃前的消息.
    • KERN_ALERT:需要立刻动作的情形.
    • KERN_CRIT:严重情况, 常常与严重的硬件或者软件失效有关.
    • KERN_ERR:用来报告错误情况; 设备驱动常常使用 KERN_ERR 来报告硬件故障.
    • KERN_WARNING:有问题的情况的警告, 这些情况自己不会引起系统的严重问题.
    • KERN_NOTICE:正常情况, 但是仍然值得注意. 在这个级别一些安全相关的情况会报告.
    • KERN_INFO:信息型消息. 在这个级别, 很多驱动在启动时打印它们发现的硬件的信息.
    • KERN_DEBUG:用作调试消息
    它们的等级依次下降。
    如果调用printk时没有指定消息的log等级,则将使用默认的log等级。
    系统也有一个log等级,如果printk的log等级大于等于当前系统的log等级,则消息会被打印到当前控制台。用户空间对于系统log的处理涉及到两个daemon:klogd和syslogd。
    • klogd会通过syslog()系统调用或者读取proc文件系统来获取内核的log信息,如果 klogd 没有运行,则用户空间只能通过读 /proc/kmsg 来获取信息或者使用dmesg来获取信息。
    • syslogd这个守护进程根据/etc/syslog.conf,将不同的服务产生的log记录到不同的文件中,它是通过klogd来读取系统内核log信息的,如果 klogd 和 syslogd 都在运行,则无论内核log等级为多少,内核都会将消息添加到/var/log/messages(如果syslog的配置文件有某个log的等级的设置,就按照syslogd的配置进行处理)。

    即:如果 klogd 进程在运行, 它获取内核消息并分发给 syslogd, syslogd 接着检查/etc/syslog.conf 来找出如何处理它们. syslogd 根据log类型和一个优先级来区分消息; log类型和优先级的允许值在 <sys/syslog.h> 中定义, 内核消息由 LOG_KERN 来表示.如果 klogd 没有运行, 数据保留在printk的环形缓存中直到有人读它或者缓存被覆盖.

    全局变量console_loglevel记录了系统当前的log等级,可以通过/proc/sys/kernel/printk文件读写它,这个文件有 4 个整型值,分别为:

    当前log级别,适用没有明确log级别的消息的缺省级别,允许的最小log级别,启动时缺省log级别。

    写单个值到这个文件将修改当前log级别为这个值。另外使用dmesg –n {数值}也可以用于修改系统的当前log等级为{数值}
    系统的log被记录在一个环形缓存中,缓存的长度可以使用dmesg –s {大小}来修改,printk将信息写入该环形缓存,如果环形缓存填满,printk 绕回并在缓存的开头增加新数据,覆盖掉最老的数据。

    3.2.2 速率限制

    采用log机制时,有时候需要限制打印的速率,否则打印信息可能将系统拖垮,内核提供了一个函数用于进行打印速率限制printk_ratelimit,如果要使用它来限制打印速率,则应该首先调用它,如果它返回非零值则可以继续打印,否则不打印。

    3.3 通过查询来调试

    Linux系统提供了一些机制用于向用户空间提供查询内核信息的接口。这些信息也可以帮我们分析定位问题。
    用log机制不失为一种很好的调试方式,但是大量的log会影响系统性能。而Linux内核提供的查询机制可以让我们在需要某些信息时再来获取信息,而不是随时打印,这有助于降低系统的负载。*nix系统提供许多工具来获取系统消息:ps, netstat, vmstat, 等等。
    内核提供的两个重要的查询内核信息的机制是:/proc文件系统,/sysfs文件系统以及ioctl,这几种方式都可以用于向用户空间提供内核信息。它们提供了一套机制给内核部件使用,内核部件只要使用这些API就能很方便的向用户空间开发接口。不同的是:
    • 使用两个文件系统时,接口会出现在这两个文件系统相应的位置,即接口以文件的形式存在,可以直接使用cat/echo等命令来操作,而使用ioctl时则开发的接口是编程接口,需要写程序来使用。
    • ioctl比使用文件系统要快。
    • 通过ioctl实现的调试机制,如果不公开其它人无法知道无法使用。

    3.4 使用strace来调试

    使用strace命令可以跟踪所有的用户空间程序发出的系统调用。它不仅显示调用, 还以符号形式显示调用的参数和返回值。当一个系统调用失败,错误的符号值和对应的字符串都会被输出出来。该命令有助于我们分析是哪个调用导致程序无法运行了。

    3.5调试系统故障

    内核程序出现异常(比如oops时)时,一般都会打印一些log信息出来,这些信息对于分析定位问题是很有帮助的,下边的信心是从kernel的git tree里取的一个oops信息:
    On CONFIG_X86_32 this results in the following oops:


      BUG: unable to handle kernel paging request at f7f22280
      IP: [<c10257b9>] reserve_ram_pages_type+0x89/0x210
      *pdpt = 0000000001978001 *pde = 0000000001ffb067 *pte = 0000000000000000
      Oops: 0000 [#1] PREEMPT SMP
      Modules linked in:


      Pid: 0, comm: swapper Not tainted 3.0.0-acpi-efi-0805 #3
       EIP: 0060:[<c10257b9>] EFLAGS: 00010202 CPU: 0
       EIP is at reserve_ram_pages_type+0x89/0x210
       EAX: 0070e280 EBX: 38714000 ECX: f7814000 EDX: 00000000
       ESI: 00000000 EDI: 38715000 EBP: c189fef0 ESP: c189fea8
       DS: 007b ES: 007b FS: 00d8 GS: 0000 SS: 0068
      Process swapper (pid: 0, ti=c189e000 task=c18bbe60 task.ti=c189e000)
      Stack:
       80000200 ff108000 00000000 c189ff00 00038714 00000000 00000000 c189fed0
       c104f8ca 00038714 00000000 00038715 00000000 00000000 00038715 00000000
       00000010 38715000 c189ff48 c1025aff 38715000 00000000 00000010 00000000
      Call Trace:
       [<c104f8ca>] ? page_is_ram+0x1a/0x40
       [<c1025aff>] reserve_memtype+0xdf/0x2f0
       [<c1024dc9>] set_memory_uc+0x49/0xa0
       [<c19334d0>] efi_enter_virtual_mode+0x1c2/0x3aa
       [<c19216d4>] start_kernel+0x291/0x2f2
       [<c19211c7>] ? loglevel+0x1b/0x1b
       [<c19210bf>] i386_start_kernel+0xbf/0xc8
    当在内核代码中使用一个非法指针时,内核通常会给出一个oops消息。Oops消息包含了是什么样的错误,出错时的处理器状态,包括CPU 寄存器内容和一些其它的信息。比较重要的是EIP和Call Trace,通常通过它们就可以找到出问题的位置和原因。
    • EIP包含出问题的位置,比如EIP is at reserve_ram_pages_type+0x89/0x210表明问题出在reserve_ram_pages_type中,该函数大小为0x210,问题出在该函数起始地址偏移0x89处。
    • Call Trace包含了出问题时的内核栈,如果内核没有包含符号表,则这个打印是以16进制地址打印的。
    在找到出问题的位置之后(通过EIP)还要进一步找是哪一条指令导致的问题,这个时候就要分析汇编指令了。得到对应汇编指令的方法有:

    3.5.1 有编译好的内核镜像

    gdb vmlinux
    (gdb)b *func+offset
    或者
    (gdb)l *func+offset

    3.5.2 有编译好的二进制文件, 用objdump看

    objdump -S file.o > /tmp/file.s
    然后查看该反汇编指令文件

    3.5.3 有编译好的内核镜像,用addr2line看

    addr2line -e vmlinux func+offset
    另外, 内核源代码目录的./scripts/decodecode文件是用来解码Oops的:
    ./scripts/decodecode < Oops.txt

    3.6 系统挂起

    尽管内核代码的大部分 bug 以 oops 消息结束,但有时候bug也可能导致系统完全挂起,没有任何打印消息。例如如果代码进入一个死循环,内核就会停止调度。
    调试这种问题的一种方式是在自己的代码中加入log,定期打印一些信息到控制台,如果一段时间log没有被更新,就可以根据这个信息找到哪里导致挂起了。
    另外一个可用的工具是SysRq魔法键。通过该机制我们能够获取很多当前系统的信息。魔法键的功能可以在编译内核时通过配置文件打开,也可以在系统启动后通过修改文件/proc/sys/kernel/sysrq来打开或者关闭该功能,sysrq的取值及其含义:
    • 0:关闭该功能
    • 1:打开所有的功能表示打开
    • 大于1:所允许的功能的掩码(具体每个比特位表示什么含义,最好查看Documents/sysrq.txt文件
    在该功能打开后,可以通过按下魔法键来触发特定的功能(魔法键在不同的架构是不同的,具体的可参见Documents/sysrq.txt文件),也可以通过向文件/proc/sysrq-trigger写入字符来触发特定的SysRq功能。其中一些字符及其含义如下:
    • b:立刻重启系统,并且不会对磁盘进行同步也不会卸载磁盘
    • d:显示所有被持有的锁
    • e:向除init进程之外的所有进程发送SIGTERM信号
    • i:向除init进程之外的所有进程发送SIGKILL信号
    • l:为所有在活动状态的CPU打印其堆栈信息
    • m:打印当前内存信息
    • p:打印当前的寄存器状态以及标记
    • q:为所有CPU打印armed的高精度定时器以及所有的时钟设备的详细信息。
    • t:打印当前任务以及它们的堆栈信息
    • w:打印处于不可中断阻塞状态的任务的信息


    展开全文
  • Linux内核常用数据结构

    千次阅读 2018-03-05 20:41:55
    Linux中最重要最常用如下四种:LIST:链表 &lt;linux/list.h&gt;Linux内核的标准链表就是采用“环形、双向”链表...称为“头指针”,可以方便的找到链表的“起始端”Linux内核实现特殊性:不是将数据结构塞...


    Linux中最重要最常用如下四种:

    LIST:链表 <linux/list.h>
    • Linux内核的标准链表就是采用“环形、双向”链表形式实现
    • 沿着链表移动智能是线性移动
    • 需要随机访问的数据,一般不使用链表
    • 链表存放数据的理想情况是:需要遍历所有数据、或者需要动态加入/删除数据
    • 有时首元素会用一个特殊的指针表示,称为“头指针”,可以方便的找到链表的“起始端”
    • Linux内核实现特殊性:不是将数据结构塞入链表,而是将链表结点塞入数据结构
    • Linux内核链表操作函数的复杂度都是O(1),而不管链表中元素数目的多少
      • list_add\__list_add
      • list_add_tail\__list_add_tail
      • list_del\__list_del
      • list_del_init\__list_del_init
      • list_move\__list_move
      • list_move_tail\__list_move_tail
      • list_empty\__list_empty
      • list_entry\__list_entry
      • list_splice\__list_splice
      • list_splice_init\__list_splice_init
    • Linux内核遍历链表的复杂度是O(n),n是链表元素数目
      • list_for_each
      • list_for_each_entry
      • list_for_each_entry_reverse 反向遍历链表,有二原因:①当反向遍历性能好时;②当遍历顺序很重要时;
      • list_for_each_entry_safe 该函数允许在遍历链表循环体中删除元素,普通遍历函数不允许这样做
      • list_for_each_entry_safe_reverse
    • 链表操作函数分为外部函数、内部函数,函数同名,只差双下划线__,内部函数用prev、next参数

    FIFO:队列 <linux/kfifo.h>
    • Linux内核通用队列实现称为kfifo,实现在文件kernel/kfifo.c中
    • 维护两个偏移量:
      • 入口偏移(下一次入队时位置)>=出口偏移(下一次出队时位置);
      • 入口偏移==出口偏移,说明队列空了;
      • 入口偏移==队列长度,说明队列重置前不能再有入队操作;
    • 提供两个主要操作:
      • 入队enqueue(copy数据到队列入口偏移位置)
      • 出队dequeue(从队列出口偏移copy数据)
    • 队列操作:
      • kfifo_alloc 动态创建、初始化 (size需是2的n次幂)
      • kfifo_init 动态创建、初始化,但使用已分配内存 (size同上)
      • DECLARE_KFIFO/INIT_KFIFO 静态声明,不常用(size同上)
      • kfifo_in   入队
      • kfifo_out   出队
      • kfifo_out_peek   不出队,只返回数据
      • kfifo_size   队列总体空间(长度)
      • kfifo_len   队列已用空间
      • kfifo_avail   队列剩余空间
      • kfifo_is_empty   判定队列空
      • kfifo_is_full   判定队列满
      • kfifo_reset   重置队列(抛弃所有元素)
      • kfifo_free   释放kfifo_alloc创建的队列

    映射:
    • 称为关联数组,由“键<==>值”对儿组成的集合; 
    • “键”是唯一的,“值”关联到键;
    • 映射操作:
      • Add (key, value)   增加
      • Remove (key)   删除
      • Value = Lookup (key)   查找
      • Allocate   插入键值对,产生UID
    • Linux内核提供了简单、有效的映射数据结构。但是它并非一个通用的映射;
    • Linux内核提供它的目标是:映射一个唯一的标识数(UID)到一个指针; (因此并不适合其它场景)
    • idr数据结构:用于映射用户空间的UID
      • idr_init   初始化静态/动态分配的idr
    • ...

    二叉树:
    • 树,是一个能提供分层的“树”型数据结构的特定数据结构;
    • 树,是一个无环、连接的有向图;
    • 树,任何一个节点具有0~n个出边,1个入边;
    • 节点深度,是从根节点起到达该节点止一共需要经过的父节点数目;
    • 树的高度,是叶子节点的深度;
    • 二叉树,任何一个节点最多有2个出边的树,即只能有0、1、2个出边;
    • BST:二叉搜索树
      • 规则1:根左分支节点值 < 根节点值
      • 规则2:根右分支节点值 > 根节点值
      • 规则3:所有子树都是二叉搜索树
      • 前序遍历:根节点->左子树->右子树
      • 中序遍历:左子树->根节点->右子树
      • 后序遍历:左子树->右子树->根节点
      • 在树中搜索给定值、按序遍历都相当快捷;中序遍历二叉搜索树时会按照节点值从小到大的顺序排序;
    • 自平衡二叉搜索树
      • 平衡二叉搜索树:所有叶子节点深度差值都不超过1的二叉搜索树
      • 自平衡二叉搜索树:操作都试图维持平衡(半平衡)的二叉搜索树
    • 红黑树
      • 是一种“自平衡二叉搜索树”
      • 是Linux主要的平衡二叉搜索树
      • 具有特殊的着色属性(或红色、或黑色)
      • 能维持半平衡结构,其6属性:
        • 属性1:所有节点要么着红色、要么着黑色
        • 属性2:叶子节点都是黑色
        • 属性3:叶子节点不包含数据
        • 属性4:非叶子节点都有2个子节点
        • 属性5:如果节点是红色,则它子节点都是黑色
        • 属性6:一个节点到该节点的叶子节点的所有路径中,总是包含相同数目的黑色节点;
      • 上述属性确保:
        • 一个红色节点不能是其它红色节点的子节点(或者父节点),即两个红色节点不能相连;
        • 从树的任何一个节点到其叶子节点的路径都具有相同数目的黑色节点;即最长路径是红黑交替路径,最短路径是全黑路径;
        • 所以,最深叶子节点深度,不会大于2倍最浅叶子节点深度; 红黑树总是半平衡的;
      • rbtree: <linux/rbtree.h>
        • Linux实现的红黑树
        • 实现在lib/rbtree.c中
        • 插入效率和树中节点数目呈现对数关系;(即:时间复杂度与节点数目是对数关系)
        • 根节点由数据结构rb_root描述,创建新红黑树,需要分配新的rb_root结构并初始化为RB_ROOT
        • 其它节点由数据结构rb_node描述
        • 未提供搜索和插入操作函数,需要由用户自己实现(可以使用rbtree提供的辅助函数,但要实现比较操作算子)

    其它较少用的:
    • radixtree:基数树


    数据结构的选择:
    • 原则一:遍历操作为主时,优先考虑链表;(没有数据结构能提供比线性算法复杂度更好的算法去遍历元素)
    • 原则二:排除性能因素,当需要相对较少数据项时,优先考虑链表;
    • 原则三:当需要与其它选择链表的代码交互时,优先考虑链表;
    • 原则四:需要大小不明的数据集合,优先选择链表;
    • 原则五:代码架构复合"生产者/消费者"模式,优先选择队列;
    • 原则六:当需要一个定长的缓冲,选择队列;
    • 原则七:如果需要映射一个UID到一个对象,选择映射;
    • 原则八:如果需要存储大量数据,并且快速检索,选择红黑树;

    本文转自 http://blog.csdn.net/ace_an/article/details/53813242

    展开全文
  • Linux内核数据结构——链表

    千次阅读 2015-03-17 22:02:18
    Linux内核中的链表实现 offsetof container_of container_of 第一部分 container_of 第二部分 链表初始化 向链表中增加一个节点 删除节点 移动节点 判断链表是否为空 遍历链表 Demo测试 tlisth mlistc 执行结果简介...

    目录


    简介

    最近在学习Android Binder驱动程序实现的时候,发现里面的数据结构用到了struct list_head。而我google发现struct list_head是Linux内核实现的链表数据结构。本身我就对数据结构这块比较感兴趣,正好借这个机会学习一下Linux内核中链表的实现。(ps:主要是堆积代码,自我学习哈,大家吐槽请轻轻吐)。

    链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。链表和的静态数据的不同之处在于,它所包含的元素都是动态创建并插入链表的,在编译时不必知道具体需要创建多少个元素。另外,也因为链表中每个元素的创建时间各不相同,所以它们在内存中无须占用连续内存区。正是因为链表中的元素不连续存放,所以各元素需要通过某种方式被连接在一起。于是,每个元素都包含一个指向下一个元素的指针,当有元素加入链表或从链表中删除元素元素时,只需要简单的调整节点指针就可以了。

    由于链表是一种非常基本的数据结构,我先简单介绍一下大学数据结构课本中是如何描述这种数据结构的。


    单向链表

    可以用一种最简单的数据结构来表示这样一个链表:

    struct list_element {
        void *data; /*有效数据*/
        struct list_element *next; /*指向下一个元素的指针*/
    };

    下图描述了一个单链表结构:
    单向链表


    双向链表

    在有些链表中,每个元素还包含一个指向前一个元素的指针,因为它们可以同时向前或者向后相互连接,所以这种链表被称作双向链表。表示双向链表的数据结构如下:

    struct list_element {
        void* data; /*有效数据*/
        struct list_element *next; /*指向下一个元素的指针*/
        struct list_element *prev; /*指向上一个元素的指针*/
    };

    下图描述了一个双向链表结构体:
    双向链表


    环形链表

    通常情况下,因为链表中最后一个元素不再有下一个元素,所以将链表尾元素中的后指针设置为NULL,以此证明它是链表中的最后一个元素。但是,在有些链表中,末尾元素并不指向特殊值,相反,它指回链表的首元素。并且,在环形双向链表中,首节点的前驱节点指向尾节点。

    因为环形双向链表提供了最大的灵活性,所以Linux内核标准的链表就是环形双向链表


    Linux内核中的链表实现

    在介绍Linux内核链表的源码实现之前,我们先来学习一下两个非常重要的宏:offsetof和container_of。


    offsetof

    它定义在include/linux/stddef.h中,其源码如下:

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

    解释一下这个宏的运行原理:

    1. ((TYPE *) 0):将0转型为TYPE类型的指针。
    2. ((TYPE *)0)->MEMBER:访问结构中的数据成员。
    3. &((TYPE *)0)->MEMBER:取出数据成员的地址。
    4. (size_t)&((TYPE )0)->MEMBER:结果转换类型。巧妙之处在于将0转换为(TYPE ),以内存空间首地址0作为起始地址,则成员地址自然为偏移地址。

    所以这个宏的作用是:计算TYPE类型中MEMBER成员的内存偏移量。


    container_of

    它定义在include/lunux/kernel.h中,其源码如下:

    /**
     * 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)); })

    这里需要简单的解释一下container_of宏。这个宏的作用很简单,就是通过一个容器(结构体)中某个成员的指针得到指向这个容器(结构体)的指针。这个宏的实现代码只有两行,我们逐行的分析一下container_of宏的实现。

    container_of 第一部分

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

    这里需要解释几点:

    1. typeof是GNU C对标准C的扩展,它的作用是根据变量获取变量类型。
    2. typeof获取了type结构体的member成员的变量类型,然后定义了一个指向该变量类型的指针__mptr,并将实际结构体该成员变量的指针的值赋值给__mptr。
    3. 通过这行代码,临时变量__mptr中保存了type结构体成员变量member在内存中分配的地址值。

    container_of 第二部分

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

    这块代码是利用__mptr的地址,减去type结构体成员member相对于结构体首地址的偏移地址,得到的自然是结构体首地址,即该结构体指针。


    链表初始化

    Linux内核实现链表的方式可以说是独树一帜。简介中提到的链表数据结构,都是需要在具体数据的结构体内部增加一个指向数据的next(或者prev)节点指针,才能串联在链表中。但是,Linux的内核实现方式与众不同,它不是将整个数据结构塞入链表,而是将链表节点塞入数据结构。
    链表代码在头文件include/linux/types.h中声明,其数据结构很简单:

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

    next是指向下一个链表节点,prev是指向前一个链表节点。然而,这里似乎看不出它们有多大的作用。到底什么才是链表存储的具体内容呢?其实关键在于理解list_head结构是如何使用的。
    接下来介绍一下链表头节点初始化的源码,定义在include/linux/list.h中:

    /**
     * Simple doubly linked list implementation.
     *
     * Some of the internal functions ("__xxx") are useful when
     * manipulating whole lists rather than single entries, as
     * sometimes we already know the next/prev entries and we can
     * generate better code by using them directly rather than
     * using the generic single-entry routines.
     */
    
    #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_HEAD宏创建一个链表头节点,并用LIST_HEAD_INIT宏对头节点进行赋值,使得头节点的前驱指针和后继指针均指向自己。
    INIT_LIST_HEAD函数也是对链表头节点进行初始化,使得头节点list的前驱和后继指针均指向自己。


    向链表中增加一个节点

    /**
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    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;
    }
    
    /**
     * list_add - add a new entry
     * @new: new entry to be added
     * @head: list head to add it after
     *
     * Insert a new entry after the specified head.
     * This is good for implementing stacks.
     */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head, head->next);
    }
    
    
    /**
     * list_add_tail - add a new entry
     * @new: new entry to be added
     * @head: list head to add it before
     *
     * Insert a new entry before the specified head.
     * This is useful for implementing queues.
     */
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head->prev, head);
    }
    

    插入节点分为从链表头部插入list_add和从链表尾部插入list_add_tail,这两个函数均是通过调用__list_add函数来实现的。


    删除节点

    /**
     * Delete a list entry by making the prev/next entries
     * point to each other.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
        next->prev = prev;
        prev->next = next;
    }
    
    /**
     * list_del - deletes entry from list.
     * @entry: the element to delete from the list.
     * Note: list_empty() on entry does not return true after this, the entry is
     * in an undefined state.
     */
    static inline void list_del(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
    }

    需要注意的是:该函数并没有接收list的头节点,它只是接受一个特定的需要删除的节点,并修改该特定节点的前后指针,这样该节点就从链表中删除了。


    移动节点

    /**
     * list_move - delete from one list and add as another's head
     * @list: the entry to move
     * @head: the head that will precede our entry
     */
    static inline void list_move(struct list_head *list, struct list_head *head)
    {
        __list_del(list);
        list_add(list, head);
    }

    该函数从链表中先移除list节点,然后将其加入到一个以head节点为头节点的链表中。

    /**
     * list_move_tail - delete from one list and add as another's tail
     * @list: the entry to move
     * @head: the head that will follow our entry
     */
    static inline void list_move_tail(struct list_head *list,
                      struct list_head *head)
    {
        __list_del(list);
        list_add_tail(list, head);
    }

    该函数从一个链表中移除list项,然后将其加入到以head为头节点的链表的末尾。


    判断链表是否为空

    /**
     * list_empty - tests whether a list is empty
     * @head: the list to test.
     */
    static inline int list_empty(const struct list_head *head)
    {
        return head->next == head;
    }

    这个函数用来判断链表是否为空。


    遍历链表

    前面介绍了内核中如何初始化、插入、删除一个链表节点。但是,如果无法访问链表中的数据,那这些操作就没有任何意义。链表仅仅是一个能够包含重要数据的容器,我们必须利用链表移动并访问包含我们数据的结构体。

    注意:链表操作的时间复杂度为O(1),遍历链表的复杂度为O(n),n是链表所包含的元素数目。

    遍历链表最简单的方法是使用list_for_each()宏。

    /**
     * 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)

    该宏使用了两个list_head类型参数,第一个参数用来指向当前项,这是一个你必须提供的临时变量,第二个参数是需要遍历的链表的头节点。每次遍历中,第一个参数在链表中不断移动指向下一个元素,直到链表中的所有元素都被访问为止。

    但是,这里一个指向链表结构的指针通常是无用的,我们所需要的是一个指向包含list_head的结构体的指针。这时,我们就可以用之前讨论的container_of方法,来获取list_head所在的结构体的指针。

    /**
     * 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_struct within the struct.
     */
    #define list_entry(ptr, type, member) \
        container_of(ptr, type, member)
    
    /**
     * list_for_each_entry  -   iterate over list of given type
     * @pos:    the type * to use as a loop cursor.
     * @head:   the head for your list.
     * @member: the name of the list_struct within the struct.
     */
    #define list_for_each_entry(pos, head, member)              \
        for (pos = list_entry((head)->next, typeof(*pos), member);  \
             &pos->member != (head);    \
             pos = list_entry(pos->member.next, typeof(*pos), member))

    Demo测试

    这里我也编写一个简单的链表使用程序,参考了Linux 内核链表的实现。

    mlist.h

    #define POISON_POINTER_DELTA 0
    #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
    #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
    
    #define offsetof(type, member) \
        (size_t)(&((type*)0)->member)
    
    #define container_of(ptr, type, member) ({ \
        const typeof(((type *)0)->member)* __mptr = (ptr); \
        (type *)((char *)__mptr - offsetof(type, member)); })
    
    struct list_head
    {
        struct list_head *next, *prev;
    };
    
    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
        list->next = list;
        list->prev = list;
    }
    
    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);
    }
    
    static inline void __list_del(struct list_head *prev, struct list_head *next)
    {
        next->prev = prev;
        prev->next = next;
    }
    
    static inline void list_del(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
        entry->prev = LIST_POISON1;
        entry->next = LIST_POISON2;
    }
    
    static inline void list_move(struct list_head *list, struct list_head *head)
    {
        list_del(list);
        list_add(list, head);
    }
    
    static inline void list_move_tail(struct list_head *list, struct list_head *head)
    {
        list_del(list);
        list_add_tail(list, head);
    }
    
    static inline int list_empty(const struct list_head *head)
    {
        return head->next == head;
    }
    
    #define list_entry(ptr, type, member) \
        container_of(ptr, type, member)
    
    #define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)
    
    #define list_for_each(pos, head) \
        for(pos = (head)->next; pos != (head); pos = pos->next)

    mlist.c

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include "mlist.h"
    
    struct fox {
        int tail_length;
        int weight;
        struct list_head list_node;
    };
    
    
    struct fox* create_fox(int length, int weight)
    {
        struct fox* tmp_fox = (struct fox*)malloc(sizeof(struct fox));
        if (tmp_fox == NULL) {
            return NULL;
        }
    
        tmp_fox->tail_length = length;
        tmp_fox->weight = weight;
    
        return tmp_fox;
    }
    
    static inline void for_each_fox(const struct list_head* head)
    {
        struct list_head *pos;
        struct fox *tmp_fox;
    
        list_for_each(pos, head) {
            tmp_fox = list_entry(pos, struct fox, list_node);
            printf("fox info: %d --- %d\n", tmp_fox->tail_length, tmp_fox->weight);
        }
    }
    
    int main()
    {
        struct fox * fox_list = (struct fox *)malloc(sizeof(struct fox));
        struct fox * fox;
    
        if (fox_list == NULL) {
            printf("malloc failed!");
            return -1;
        }
    
        // 初始化链表头节点
        struct list_head *head = &(fox_list->list_node);
        INIT_LIST_HEAD(head);
        printf("初始化头节点完成!\n");
    
        // 插入4个fox
        fox = create_fox(100, 100);
        list_add_tail(&(fox->list_node), head);
    
        fox = create_fox(105, 105);
        list_add_tail(&(fox->list_node), head);
    
        fox = create_fox(110, 110);
        list_add_tail(&(fox->list_node), head);
    
        fox = create_fox(115, 115);
        list_add_tail(&(fox->list_node), head);
        printf("插入4个狐狸节点\n");
    
        // 遍历
        for_each_fox(head);
    
        // 移动节点
        list_move_tail(head->next, head);
        printf("将第一个节点移动到末尾\n");
        for_each_fox(head);
    
        // 删除节点
        list_del(head->next);
        printf("删除当前第一个节点\n");
        for_each_fox(head);
    
    
        return 0;
    }

    执行结果

    执行结果如图所示:
    执行结果

    展开全文
  • 学习嵌入式一段时间了,开始学习Linux...本期课程主要侧重于数据结构基本功的学习和Linux内核中的面向对象思想。掌握了这两项技能,再去分析Linux内核中复杂的子系统和驱动代码,相信你会跟以前有不一样的体验和收获。
  • Linux内核数据结构—链表

    千次阅读 2018-01-09 00:00:00
    (点击上方蓝字,快速关注)链表(循环双向链表)是Linux内核中最简单、最常用的一种数据结构。内核中关于链表定义的代码位于: include/linux/list.h。list.h文件中对每个函数都有注释,这里就不详细说了。其实刚开始...
  • 详细分析了linux内核中sock和socket数据结构的含义
  • linux内核主要是有C和汇编写成的,C是面向过程的语言,但是linux内核却用C实现了一套面向对象的设计模式,linux内核中处处体现着面向对象的思想 传统的链表实现之前我们前面提到的链表都是在我们原数据结构的基础上...
  • 很久之前研读过Linux的内核源码(后来终止了,水太深,吾辈驾驭不了),看到其中的内核数据结构,对链表的实现叹为观止,是迄今为止我见过的最为经典的链表实现(不是数据内嵌到链表中,而是把链表内嵌到数据对象中...
  • Linux内核源码学习之 数据结构

    千次阅读 2014-09-26 21:00:16
    本篇记录在学习Linux内核源码过程中对一些知道但不熟悉不会用的数据结构进行记录。 union 是在学习进程复制函数do_fork中遇到的:   union thread_union {  struct thread_info thread_info;  unsigned long ...
  • 包含了linux内核各个数据结构的图解,是广大内核爱好者学习内核源代码的辅助材料
  • 嵌入式linuxc语言基础——armlinux内核常见数据结构.pptx
  • linux内核数据结构---hash表

    千次阅读 2013-05-23 08:51:43
    关于linux内核链表请参考“linux内核数据结构---链表”。 链表虽然是最常见的数据结构,但实际使用中,由于链表的检索能力较差,更多的是作为队列和栈结构使用,如果需要查询,比如通过pid查找进程,通过描述符...
  • Linux内核常用数据结构要点

    千次阅读 2016-12-22 13:56:07
    简单总结一下Linux Kernel常用数据结构和选取原则
  • Linux内核目录结构介绍(超详细)

    千次阅读 2019-09-25 14:45:30
    现在介绍一下Linux内核(kernel)的目录结构。 内核在系统目录下的路径,一般为:/usr/src/(我的ubuntu下测试的) 你也可以自己在/home目录下创建一个文件夹命名为work,作为自己开发内核的工作目录,...
  • linux内核数据结构链表

    千次阅读 2015-04-12 18:37:26
    结构体能存放数据 结构体嵌入链表能够让数据串联成为整体 如何通过结构体的链表找到对应结构体  container_of宏定义 /*#define container_of(ptr, type, member) ({ \  const typeof( ((type *)0)->member ) *__mp
  • 1、内核架构常见架构范式:Linux内核上下层通信方式横向系统和纵向系统横向系统如cgroup,proc,sys文件系统,系统调用的组织,调试系统,Core Dump,信号,内存管理等;纵向系统是指具体的功能模块,如USB功能,一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 251,774
精华内容 100,709
关键字:

linux内核数据结构

linux 订阅
数据结构 订阅