LogoLogo
  • 简介
  • 引导
    • 从引导加载程序内核
    • 在内核安装代码的第一步
    • 视频模式初始化和转换到保护模式
    • 过渡到 64 位模式
    • 内核解压缩
  • 初始化
    • 内核解压之后的首要步骤
    • 早期的中断和异常控制
    • 在到达内核入口之前最后的准备
    • 内核入口 - start_kernel
    • 体系架构初始化
    • 进一步初始化指定体系架构
    • 最后对指定体系架构初始化
    • 调度器初始化
    • RCU 初始化
    • 初始化结束
  • 中断
    • 中断和中断处理第一部分
    • 深入 Linux 内核中的中断
    • 初步中断处理
    • 中断处理
    • 异常处理的实现
    • 处理不可屏蔽中断
    • 深入外部硬件中断
    • IRQs的非早期初始化
    • Softirq, Tasklets and Workqueues
    • 最后一部分
  • 系统调用
    • 系统调用概念简介
    • Linux 内核如何处理系统调用
    • vsyscall and vDSO
    • Linux 内核如何运行程序
    • open 系统调用的实现
    • Linux 资源限制
  • 定时器和时钟管理
    • 简介
    • 时钟源框架简介
    • The tick broadcast framework and dyntick
    • 定时器介绍
    • Clockevents 框架简介
    • x86 相关的时钟源
    • Linux 内核中与时钟相关的系统调用
  • 同步原语
    • 自旋锁简介
    • 队列自旋锁
    • 信号量
    • 互斥锁
    • 读者/写者信号量
    • 顺序锁
    • RCU
    • Lockdep
  • 内存管理
    • 内存块
    • 固定映射地址和 ioremap
    • kmemcheck
  • 控制组
    • 控制组简介
  • SMP
  • 概念
    • 每个 CPU 的变量
    • CPU 掩码
    • initcall 机制
    • Linux 内核的通知链
  • Linux 内核中的数据结构
    • 双向链表
    • 基数树
    • 位数组
  • 理论
    • 分页
    • ELF 文件格式
    • 內联汇编
    • CPUID
    • MSR
  • Initial ram disk
  • 杂项
    • Linux 内核开发
    • 内核编译方法
    • 链接器
    • 用户空间的程序启动过程
    • 书写并提交你第一个内核补丁
  • 内核数据结构
    • 中断描述符表
  • 有帮助的链接
  • 贡献者
由 GitBook 提供支持
在本页
  • 基数树
  • Linux 内核基数树 API
  • 链接
  1. Linux 内核中的数据结构

基数树

上一页双向链表下一页位数组

最后更新于1年前

基数树

正如你所知道的 Linux 内核通过许多不同库以及函数提供各种数据结构以及算法实现。 这个部分我们将介绍其中一个数据结构 。Linux 内核中有两个文件与 radix tree 的实现和API相关:

首先说明一下什么是 radix tree 。Radix tree 是一种 压缩 trie,其中 是一种通过保存关联数组(associative array)来提供 关键字-值(key-value) 存储与查找的数据结构。通常关键字是字符串,不过也可以是其他数据类型。

trie 结构的节点与 n-tree 不同,其节点中并不存储关键字,取而代之的是存储单个字符标签。关键字查找时,通过从树的根开始遍历关键字相关的所有字符标签节点,直至到达最终的叶子节点。下面是个例子:

               +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

这个例子中,我们可以看到 trie 所存储的关键字信息 go 与 cat,压缩 trie 或 radix tree 与 trie 所不同的是,所有只存在单个孩子的中间节点将被压缩。

struct radix_tree_root {
         unsigned int            height;
         gfp_t                   gfp_mask;
         struct radix_tree_node  __rcu *rnode;
};

上面这个是 radix 树的 root 节点的结构体,它包括三个成员:

  • height - 从叶节点向上计算出的树高度。

  • gfp_mask - 内存分配标识。

  • rnode - 子节点指针。

这里我们先讨论的结构体成员是 gfp_mask :

Linux 底层的内存申请接口需要提供一类标识(flag) - gfp_mask ,用于描述内存申请的行为。这个以 GFP_ 前缀开头的内存申请控制标识主要包括,GFP_NOIO 禁止所有IO操作但允许睡眠等待内存,__GFP_HIGHMEM 允许申请内核的高端内存,GFP_ATOMIC 高优先级申请内存且操作不允许被睡眠。

接下来说的结构体成员是rnode:

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

这个结构体中包括这几个内容,节点与父节点的偏移以及到树底端的高度,子节点的个数,节点的存储数据域,具体描述如下:

  • path - 本节点与父节点的偏移以及到树底端的高度。

  • count - 子节点的个数。

  • parent - 父节点的指针。

  • private_data - 存储数据内容缓冲区。

  • rcu_head - 用于节点释放的RCU链表。

  • private_list - 存储数据。

结构体 radix_tree_node 的最后两个成员 tags 与 slots 是非常重要且需要特别注意的。每个 Radix 树节点都可以包括一个指向存储数据指针的 slots 集合,空闲 slots 的指针指向 NULL。 Linux 内核的 Radix 树结构体中还包含用于记录节点存储状态的标签 tags 成员,标签通过位设置指示 Radix 树的数据存储状态。

至此,我们了解到 radix 树的结构,接下来看一下 radix 树所提供的 API。

Linux 内核基数树 API

我们从数据结构的初始化开始看,radix 树支持两种方式初始化。

第一个是使用宏 RADIX_TREE :

RADIX_TREE(name, gfp_mask);

正如你看到,只需要提供 name 参数,就能够使用 RADIX_TREE 宏完成 radix 的定义以及初始化,RADIX_TREE 宏的实现非常简单:

#define RADIX_TREE(name, mask) \
         struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask)   { \
        .height = 0,              \
        .gfp_mask = (mask),       \
        .rnode = NULL,            \
}

RADIX_TREE 宏首先使用 name 定义了一个 radix_tree_root 实例并用 RADIX_TREE_INIT 宏带参数 mask 进行初始化。宏 RADIX_TREE_INIT 将 radix_tree_root 初始化为默认属性并将 gfp_mask 初始化为入参 mask 。 第二种方式是手工定义 radix_tree_root 变量,之后再使用 mask 调用 INIT_RADIX_TREE 宏对变量进行初始化。

struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏定义:

#define INIT_RADIX_TREE(root, mask)  \
do {                                 \
        (root)->height = 0;          \
        (root)->gfp_mask = (mask);   \
        (root)->rnode = NULL;        \
} while (0)

宏 INIT_RADIX_TREE 所初始化的属性与 RADIX_TREE_INIT 一致

接下来是 radix 树的节点插入以及删除,这两个函数:

  • radix_tree_insert;

  • radix_tree_delete.

第一个函数 radix_tree_insert 需要三个入参:

  • radix 树 root 节点结构

  • 索引关键字

  • 需要插入存储的数据

第二个函数 radix_tree_delete 除了不需要存储数据参数外,其他与 radix_tree_insert 一致。

radix 树的查找实现有以下几个函数:The search in a radix tree implemented in two ways:

  • radix_tree_lookup;

  • radix_tree_gang_lookup;

  • radix_tree_lookup_slot.

第一个函数 radix_tree_lookup 需要两个参数:

  • radix 树 root 节点结构

  • 索引关键字

这个函数通过给定的关键字查找 radix 树,并返关键字所对应的结点。

第二个函数 radix_tree_gang_lookup 具有以下特征:

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                    void **results,
                                    unsigned long first_index,
                                    unsigned int max_items);

函数返回查找到记录的条目数,并根据关键字进行排序,返回的总结点数不超过入参 max_items 的大小。

最后一个函数 radix_tree_lookup_slot 返回结点 slot 中所存储的数据。

链接

Linux 内核中的 Radix 树将值映射为整型关键字,Radix 的数据结构定义在 文件中 :

Radix tree
include/linux/radix-tree.h
lib/radix-tree.c
trie
include/linux/radix-tree.h
Radix tree
Trie