目錄
红黑树 " >红黑树
无锁环形缓冲区 " >无锁环形缓冲区
首頁 運維 linux運維 Linux核心中常用的資料結構和演算法

Linux核心中常用的資料結構和演算法

Jul 31, 2023 pm 05:06 PM
linux

Linux核心中常用的資料結構和演算法

Linux核心程式碼中廣泛使用了資料結構和演算法,其中最常用的兩個是鍊錶和紅黑樹。

鍊錶

#Linux核心程式碼大量使用了鍊錶這種資料結構。鍊錶是在解決數組不能動態擴展這個缺陷而產生的一種資料結構。鍊錶所包含的元素可以動態建立並插入和刪除。鍊錶的每個元素都是離散存放的,因此不需要佔用連續的記憶體。鍊錶通常由若干節點組成,每個節點的結構都是一樣的,由有效資料區和指標區兩部分組成。有效資料區用來儲存有效資料訊息,而指標區則用來指向鍊錶的前繼節點或後繼節點。因此,鍊錶就是利用指標將各個節點串聯起來的一種儲存結構。

(1)單向鍊錶

單向鍊錶的指針區只包含一個指向下一個節點的指針,因此會形成一個單一方向的鍊錶,如下代碼所示。

struct list {
    int data;   /*有效数据*/
    struct list *next; /*指向下一个元素的指针*/
};
登入後複製

如圖所示,單向鍊錶具有單向移動性,也就是只能存取當前的節點的後繼節點,而無法存取目前節點的前繼節點,因此在實際專案中運用得比較少。

Linux核心中常用的資料結構和演算法

單向鍊錶示意圖

(2)雙向鍊錶

如圖所示,雙向鍊錶和單向鍊錶的差異是指針區包含了兩個指針,一個指向前繼節點,另一個指向後繼節點,如下碼所示。

struct list {
    int data;   /*有效数据*/
    struct list *next; /*指向下一个元素的指针*/
    struct list *prev; /*指向上一个元素的指针*/
};
登入後複製
Linux核心中常用的資料結構和演算法

雙向鍊錶示意圖

#(3)Linux內核鍊錶實作

單向鍊錶與雙向鍊錶在實際使用上有一些局限性,如數據區必須是固定數據,而實際需求是多種多樣的。這種方法無法建構一套通用的鍊錶,因為每個不同的資料區都需要一套鍊錶。為此,Linux核心把所有鍊錶操作方法的共同部分提取出來,把不同的部分留給程式碼程式設計者自己去處理。 Linux核心實作了一套純鍊錶的封裝,鍊錶節點資料結構只有指標區而沒有資料區,另外也封裝了各種操作函數,如建立節點函數、插入節點函數、刪除節點函數、遍歷節點函數等。

Linux核心鍊錶使用struct list_head資料結構來描述。

<include/linux/types.h>

struct list_head {
    struct list_head *next, *prev;
};
登入後複製

struct list_head数据结构不包含链表节点的数据区,通常是嵌入其他数据结构,如struct page数据结构中嵌入了一个lru链表节点,通常是把page数据结构挂入LRU链表。

<include/linux/mm_types.h>

struct page {
    ...
    struct list_head lru;
    ...
}
登入後複製

链表头的初始化有两种方法,一种是静态初始化,另一种动态初始化。

把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)
登入後複製

其中offsetof()宏是通过把0地址转换为type类型的指针,然后去获取该结构体中member成员的指针,也就是获取了membertype结构体中的偏移量。最后用指针ptr减去offset,就得到type结构体的真实地址了。

下面是遍历链表的一个例子。

<drivers/block/osdblk.c>

static ssize_t class_osdblk_list(struct class *c,
                struct class_attribute *attr,
                char *data)
{
    int n = 0;
    struct list_head *tmp;

    list_for_each(tmp, &osdblkdev_list) {
        struct osdblk_device *osdev;

        osdev = list_entry(tmp, struct osdblk_device, node);

        n += sprintf(data+n, "%d %d %llu %llu %s\n",
            osdev->id,
            osdev->major,
            osdev->obj.partition,
            osdev->obj.id,
            osdev->osd_path);
    }
    return n;
}
登入後複製

红黑树

红黑树(Red Black Tree)被广泛应用在内核的内存管理和进程调度中,用于将排序的元素组织到树中。红黑树被广泛应用在计算机科学的各个领域中,它在速度和实现复杂度之间提供一个很好的平衡。

红黑树是具有以下特征的二叉树。

每个节点或红或黑。

  • 每个叶节点是黑色的。
  • 如果结点都是红色,那么两个子结点都是黑色。
  • 从一个内部结点到叶结点的简单路径上,对所有叶节点来说,黑色结点的数目都是相同的。

红黑树的一个优点是,所有重要的操作(例如插入、删除、搜索)都可以在O(log n)时间内完成,n为树中元素的数目。经典的算法教科书都会讲解红黑树的实现,这里只是列出一个内核中使用红黑树的例子,供读者在实际的驱动和内核编程中参考。这个例子可以在内核代码的documentation/Rbtree.txt文件中找到。

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

MODULE_AUTHOR("figo.zhang");
MODULE_DESCRIPTION(" ");
MODULE_LICENSE("GPL");

  struct mytype { 
     struct rb_node node;
     int key; 
};

/*红黑树根节点*/
 struct rb_root mytree = RB_ROOT;
/*根据key来查找节点*/
struct mytype *my_search(struct rb_root *root, int new)
  {
     struct rb_node *node = root->rb_node;

     while (node) {
          struct mytype *data = container_of(node, struct mytype, node);

          if (data->key > new)
               node = node->rb_left;
          else if (data->key < new)
               node = node->rb_right;
          else
               return data;
     }
     return NULL;
  }

/*插入一个元素到红黑树中*/
  int my_insert(struct rb_root *root, struct mytype *data)
  {
     struct rb_node **new = &(root->rb_node), *parent=NULL;

     /* 寻找可以添加新节点的地方 */
     while (*new) {
          struct mytype *this = container_of(*new, struct mytype, node);

          parent = *new;
          if (this->key > data->key)
               new = &((*new)->rb_left);
          else if (this->key < data->key) {
               new = &((*new)->rb_right);
          } else
               return -1;
     }

     /* 添加一个新节点 */
     rb_link_node(&data->node, parent, new);
     rb_insert_color(&data->node, root);

     return 0;
  }

static int __init my_init(void)
{
     int i;
     struct mytype *data;
     struct rb_node *node;

     /*插入元素*/
     for (i =0; i < 20; i+=2) {
          data = kmalloc(sizeof(struct mytype), GFP_KERNEL);
          data->key = i;
          my_insert(&mytree, data);
     }

     /*遍历红黑树,打印所有节点的key值*/
      for (node = rb_first(&mytree); node; node = rb_next(node)) 
          printk("key=%d\n", rb_entry(node, struct mytype, node)->key);

     return 0;
}

static void __exit my_exit(void)
{
     struct mytype *data;
     struct rb_node *node;
     for (node = rb_first(&mytree); node; node = rb_next(node)) {
          data = rb_entry(node, struct mytype, node);
          if (data) {
                rb_erase(&data->node, &mytree);
                kfree(data);
          }
     }
}
module_init(my_init);
module_exit(my_exit);
登入後複製

mytree是红黑树的根节点,my_insert()实现插入一个元素到红黑树中,my_search()根据key来查找节点。内核大量使用红黑树,如虚拟地址空间VMA的管理。

无锁环形缓冲区

生产者和消费者模型是计算机编程中最常见的一种模型。生产者产生数据,而消费者消耗数据,如一个网络设备,硬件设备接收网络包,然后应用程序读取网络包。环形缓冲区是实现生产者和消费者模型的经典算法。环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据,写指针指向环形缓冲区可写的数据。通过移动读指针和写指针实现缓冲区数据的读取和写入。

在Linux内核中,KFIFO是采用无锁环形缓冲区的实现。FIFO的全称是“First In First Out”,即先进先出的数据结构,它采用环形缓冲区的方法来实现,并提供一个无边界的字节流服务。采用环形缓冲区的好处是,当一个数据元素被消耗之后,其余数据元素不需要移动其存储位置,从而减少复制,提高效率

(1)创建KFIFO

在使用KFIFO之前需要进行初始化,这里有静态初始化和动态初始化两种方式。

<include/linux/kfifo.h>

int kfifo_alloc(fifo, size, gfp_mask)
登入後複製

该函数创建并分配一个大小为size的KFIFO环形缓冲区。第一个参数fifo是指向该环形缓冲区的struct kfifo数据结构;第二个参数size是指定缓冲区元素的数量;第三个参数gfp_mask表示分配KFIFO元素使用的分配掩码。

静态分配可以使用如下的宏。

#define DEFINE_KFIFO(fifo, type, size)
#define INIT_KFIFO(fifo)
登入後複製

(2)入列

把数据写入KFIFO环形缓冲区可以使用kfifo_in()函数接口。

int kfifo_in(fifo, buf, n)
登入後複製

该函数把buf指针指向的n个数据复制到KFIFO环形缓冲区中。第一个参数fifo指的是KFIFO环形缓冲区;第二个参数buf指向要复制的数据的buffer;第三个数据是要复制数据元素的数量。

(3)出列

从KFIFO环形缓冲区中列出或者摘取数据可以使用kfifo_out()函数接口。

#define    kfifo_out(fifo, buf, n)
登入後複製

该函数是从fifo指向的环形缓冲区中复制n个数据元素到buf指向的缓冲区中。如果KFIFO环形缓冲区的数据元素小于n个,那么复制出去的数据元素小于n个。

(4)获取缓冲区大小

KFIFO提供了几个接口函数来查询环形缓冲区的状态。

#define kfifo_size(fifo)
#define kfifo_len(fifo)
#define kfifo_is_empty(fifo)
#define kfifo_is_full(fifo)
登入後複製

kfifo_size()用来获取环形缓冲区的大小,也就是最大可以容纳多少个数据元素。kfifo_len()用来获取当前环形缓冲区中有多少个有效数据元素。kfifo_is_empty()判断环形缓冲区是否为空。kfifo_is_full()判断环形缓冲区是否为满。

(5)与用户空间数据交互

KFIFO还封装了两个函数与用户空间数据交互。

#define    kfifo_from_user(fifo, from, len, copied)
#define    kfifo_to_user(fifo, to, len, copied)
登入後複製

kfifo_from_user()是把from指向的用户空间的len个数据元素复制到KFIFO中,最后一个参数copied表示成功复制了几个数据元素。

kfifo_to_user()則相反,把KFIFO的資料元素複製到使用者空間。這兩個巨集結合了copy_to_user()copy_from_user()以及KFIFO的機制,給了驅動開發者方便。


#

以上是Linux核心中常用的資料結構和演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1659
14
CakePHP 教程
1415
52
Laravel 教程
1310
25
PHP教程
1258
29
C# 教程
1232
24
Linux體系結構:揭示5個基本組件 Linux體系結構:揭示5個基本組件 Apr 20, 2025 am 12:04 AM

Linux系統的五個基本組件是:1.內核,2.系統庫,3.系統實用程序,4.圖形用戶界面,5.應用程序。內核管理硬件資源,系統庫提供預編譯函數,系統實用程序用於系統管理,GUI提供可視化交互,應用程序利用這些組件實現功能。

vscode終端使用教程 vscode終端使用教程 Apr 15, 2025 pm 10:09 PM

vscode 內置終端是一個開發工具,允許在編輯器內運行命令和腳本,以簡化開發流程。如何使用 vscode 終端:通過快捷鍵 (Ctrl/Cmd ) 打開終端。輸入命令或運行腳本。使用熱鍵 (如 Ctrl L 清除終端)。更改工作目錄 (如 cd 命令)。高級功能包括調試模式、代碼片段自動補全和交互式命令歷史。

git怎麼查看倉庫地址 git怎麼查看倉庫地址 Apr 17, 2025 pm 01:54 PM

要查看 Git 倉庫地址,請執行以下步驟:1. 打開命令行並導航到倉庫目錄;2. 運行 "git remote -v" 命令;3. 查看輸出中的倉庫名稱及其相應的地址。

vscode在哪寫代碼 vscode在哪寫代碼 Apr 15, 2025 pm 09:54 PM

在 Visual Studio Code(VSCode)中編寫代碼簡單易行,只需安裝 VSCode、創建項目、選擇語言、創建文件、編寫代碼、保存並運行即可。 VSCode 的優點包括跨平台、免費開源、強大功能、擴展豐富,以及輕量快速。

vscode終端命令不能用 vscode終端命令不能用 Apr 15, 2025 pm 10:03 PM

VS Code 終端命令無法使用的原因及解決辦法:未安裝必要的工具(Windows:WSL;macOS:Xcode 命令行工具)路徑配置錯誤(添加可執行文件到 PATH 環境變量中)權限問題(以管理員身份運行 VS Code)防火牆或代理限制(檢查設置,解除限制)終端設置不正確(啟用使用外部終端)VS Code 安裝損壞(重新安裝或更新)終端配置不兼容(嘗試不同的終端類型或命令)特定環境變量缺失(設置必要的環境變量)

vscode上一步下一步快捷鍵 vscode上一步下一步快捷鍵 Apr 15, 2025 pm 10:51 PM

VS Code 一步/下一步快捷鍵的使用方法:一步(向後):Windows/Linux:Ctrl ←;macOS:Cmd ←下一步(向前):Windows/Linux:Ctrl →;macOS:Cmd →

sublime寫好代碼後如何運行 sublime寫好代碼後如何運行 Apr 16, 2025 am 08:51 AM

在 Sublime 中運行代碼的方法有六種:通過熱鍵、菜單、構建系統、命令行、設置默認構建系統和自定義構建命令,並可通過右鍵單擊項目/文件運行單個文件/項目,構建系統可用性取決於 Sublime Text 的安裝情況。

notepad怎麼運行java代碼 notepad怎麼運行java代碼 Apr 16, 2025 pm 07:39 PM

雖然 Notepad 無法直接運行 Java 代碼,但可以通過借助其他工具實現:使用命令行編譯器 (javac) 編譯代碼,生成字節碼文件 (filename.class)。使用 Java 解釋器 (java) 解釋字節碼,執行代碼並輸出結果。

See all articles