深入剖析Linux的Radix树使用方法与原理 (linux radix树)
随着现代计算机技术的不断发展，Linux系统已经成为了世界领先的操作系统之一。而在这个操作系统中，Radix树作为一种非常重要的数据结构，被广泛地应用于网络通信、文件系统以及内核缓存等方面。在本文中，我们将，为读者提供更加全面的了解和认识。
1. Radix树的基础概念
Radix树，也称为基数树（Radix Tree），是一种特殊的树形数据结构，通过对字符串的前缀进行分支，来存储和查询大量的数据。与传统的二叉查找树和红黑树不同，Radix树的每个节点可以有任意数量的子节点，并且每个节点的深度不一定相同。因此，在大规模数据存储和高效查找方面，Radix树具有更好的性能表现。
Radix树的名称“基数”来源于其在存储数据时按照每个字符的基数（比如2进制、8进制、16进制等）进行分支的特性。具体来说，一个字符串的每个字符可以被看作一个数位，Radix树的节点则按照这些数位进行分支。举个例子，对于字符串“ABCD”，我们可以看做是一个长度为4的16进制数，其中A转化为10，B转化为11，C转化为12，D转化为13，因此可以将其作为一个Radix树的关键字插入到树中。如下图所示，Radix树的每个节点表示一个16进制数位，叶子节点表示一个完整的16进制数值。
2. Radix树的应用场景
由于Radix树的高效性能和可扩展性，它在许多领域都得到了广泛的应用。在Linux系统中，Radix树也扮演了非常重要的角色。以下是Radix树在Linux系统下的几个应用场景。
2.1 网络通信
Linux内核中的网络协议栈使用了大量的Radix树来存储和查找各种协议的状态信息。例如，每个套接字连接都对应着一个socket数据结构，这些socket数据结构通过Radix树进行组织和管理。在网络通信的过程中，Linux内核通过查找socket数据结构，来确定每个网络包的接收和发送方向，从而实现了高效可靠的网络通信。
2.2 文件系统
在Linux系统中，文件系统是一个非常重要的组成部分。Radix树被广泛地应用于文件系统中的内存inode缓存（Inode Cache）和页缓存（Page Cache）中。内存inode缓存用于缓存磁盘上的inode节点，提升文件访问速度；页缓存用于缓存文件数据，同样可以加速文件读写效率。在这些缓存中，Linux内核使用Radix树来存储和查找每个inode和页的信息，从而提高了文件系统的性能和可靠性。
2.3 内核缓存
除了文件系统和网络通信，Radix树还被广泛地应用于Linux内核的各种缓存中。例如，Linux内核中的Slab与Slub分配器使用了Radix树来存储和管理缓存页的信息。Radix树可以自适应地调整树的深度和节点数量，根据实际情况来平衡操作的效率和内存使用效率。这些缓存的高效使用，可以大大提高Linux内核的性能和响应速度。
3. Linux中的Radix树实现
Radix树在Linux系统中的应用十分广泛，为了适应不同的应用场景，Linux内核中提供了多种不同的Radix树实现。在本节中，我们将介绍Linux中的三种主要的Radix树实现，并分析其原理和使用方法。
3.1 基本Radix树
基本Radix树（Immediate Mode Radix Tree）是Linux内核中最常用和最基础的一种Radix树实现。它使用数组来存储节点，每个节点最多可以有256个子节点，其中-1表示该节点没有子节点。在插入和查询操作时，基本Radix树从更高位开始逐位匹配关键字，直到最后一位。
基本Radix树的实现非常简单明了，因此在许多场景下都可以发挥出不错的性能表现。不过，由于基本Radix树的存储空间是静态的，无法动态地调整树的深度和节点数量，因此在插入和删除节点时需要重新分配内存空间，存在较大的时间开销。此外，在处理稀疏数据时，基本Radix树的效率可能会较低。
3.2 可扩展哈希表
为了解决基本Radix树存在的动态分配内存和稀疏数据处理问题，Linux内核提供了第二种Radix树实现——可扩展哈希表（eXtensible Hash Table）。可扩展哈希表使用哈希表来存储各个节点，每个节点最多可以有两个子节点，分别表示0和1两种不同的分支。在扩展哈希表中，每个哈希桶包含若干个节点，在每个哈希桶的末尾，会有一个指针指向下一个哈希桶。
与基本Radix树不同，可扩展哈希表采用动态存储空间管理，可以实时调整节点数量和哈希桶数量，并根据哈希冲突情况进行自适应的重哈希操作。这使得可扩展哈希表在插入、删除和查询节点时都具有较高的效率和性能，并且可以应对不同规模、密度和分布的数据。
3.3 多位基数树
多位基数树（Patricia Trie）是Linux内核中的另一种Radix树实现，它在Roberto Grossi和Giuseppe Ottaviano的研究基础上进行了改进和优化。多位基数树用于处理稠密、高速、内存受限的数据，可以支持常规的插入、删除和查询操作，并可以对树进行压缩来节省存储空间。
多位基数树的结构与基本Radix树相似，但是做了一些改进和优化。具体来说，每个节点最多可以有两个子节点，并且除了根节点外，所有节点都必须有一个有效的父节点。这使得多位基数树可以按照路径压缩原理来压缩树的深度和节点数量，从而有效地节省存储空间。在多位基数树中，插入和删除节点的操作是相对较为复杂的，但是查询操作则可以得到相对高效的性能表现。
4.
Radix树作为一种高效可扩展的数据结构，在Linux系统中的应用广泛且重要。在本篇文章中，我们介绍了Radix树的基础概念和应用场景，深入剖析了Linux中的三种主要Radix树实现以及其原理和使用方法。希望这篇文章能够帮助读者更好地理解和使用Linux系统中的Radix树，从而实现更高效可靠的数据存储和检索。
相关问题拓展阅读：
嵌入式系统Linux内核开发实战指南的目录
第1部分 嵌入式系统硬件开发
第1章 嵌入式系统概述 2
这一章对嵌入式系统的概念及其特点和应用作了概括介绍，笔者根据自己多年的经验阐述了对嵌入式系统的理解，并对一些常见的嵌入式处理器的硬件数据进行了比较。
1.1 嵌入式系统概念 2
1.2 嵌入式处理器 3
1.3 嵌入式系统应用 4
1.4 嵌入式系统发展 4
1.5 一些嵌入式处理器的硬件特性比较 5
第2章 ARM处理器概述 16
为了使本书内容完整，从第2章到第7章中的内容大部分是笔者阅读《ARM体系结构与编程》（详情参见附录中的参考文献）的笔记和心得，把与嵌入式系统开发和Linux内核密切相关的硬件知识进行了概括和整理，本章主要介绍了ARM处理器的特点、ARM处理器的体系架构版本和ARM处理器系列。
2.1 ARM发展历程 16
2.2 ARM处理器特点 17
2.3 ARM处理器应用 17
2.4 ARM体系架构 18
2.4.1 ARM体系架构版本 18
2.4.2 ARM体系架构变种（Variant） 20
2.4.3 ARM体系架构版本命名格式 22
2.5 ARM处理器 22
2.5.1 ARM7系列处理器 23
2.5.2 ARM9系列处理器 24
2.5.3 ARM9E系列处理器 24
2.5.4 ARM10E系列处理器 25
2.5.5 SecurCore系列处理器 25
2.5.6 StrongARM处理器 26
2.5.7 Xscale处理器 26
第3章 ARM指令及其寻址方式 27
本章主要介绍了ARM处理器的指令和寻址方式以及ARM汇编伪指令，这是做ARM处理器应用系统底层软件开发必备的知识。
3.1 ARM处理器的程序状态寄存器（PSR） 27
3.2 ARM指令的条件码 28
3.3 ARM指令介绍 29
3.3.1 跳转指令 29
3.3.2 数据处理指令 30
3.3.3 乘法指令 31
3.3.4 杂类算术指令 32
3.3.5 状态寄存器访问指令 32
3.3.6 Load/Store内存访问指令 33
3.3.7 批量Load/Store内存访问指令 34
3.3.8 LDREX和STREX指令 35
3.3.9 信号量操作指令 37
3.3.10 异常中断产生指令 37
3.3.11 ARM协处理器指令 37
3.4 ARM指令寻址方式 39
3.4.1 数据处理指令的操作数的寻址方式 39
3.4.2 字及无符号字节的Load/Store指令的寻址方式 43
3.4.3 杂类Load/Store指令的寻址方式 47
3.4.4 批量Load/Store指令的寻址方式 49
3.4.5 协处理器Load/Store指令的寻址方式 51
3.4.6 ARM指令的寻址方式总结 52
3.5 ARM汇编伪操作（Directive） 53
3.5.1 符号定义伪操作 54
3.5.2 数据定义伪操作 54
3.5.3 汇编控制伪操作 56
3.5.4 栈中数据帧描述伪操作 57
3.5.5 信息报告伪操作 57
3.5.6 其他伪操作 58
3.6 ARM汇编伪指令 59
3.7 Thumb指令介绍 60
第4章 ARM处理器内存管理单元（MMU） 61
本章主要介绍了ARM处理器内存管理单元（MMU）的工作原理，Linux内存管理功能是通过处理器硬件MMU实现的，在没有MMU的处理器系统中，Linux只能工作在物理地址模式，没有虚拟（线性）地址空间的概念。
4.1 ARM处理器中CP15协处理器的寄存器 61
4.1.1 访问CP15寄存器的指令 61
4.1.2 CP15寄存器介绍 62
4.2 MMU简介 70
4.3 系统访问存储空间的过程 71
4.3.1 使能MMU时的情况 71
4.3.2 禁止MMU时的情况 71
4.3.3 使能/禁止MMU时应注意的问题 72
4.4 ARM处理器地址变换过程 72
4.4.1 MMU的一级映射描述符 73
4.4.2 MMU的二级映射描述符 74
4.4.3 基于段的地址变换过程 75
4.4.4 粗粒度大页地址变换过程 75
4.4.5 粗粒度小页地址变换过程 76
4.4.6 细粒度大页地址变换过程 76
4.4.7 细粒度小页地址变换过程 77
4.4.8 细粒度极小页地址变换过程 77
4.5 ARM存储空间访问权限控制 78
4.6 TLB操作 79
4.6.1 使TLB内容无效 79
4.6.2 锁定TLB内容 79
4.6.3 解除TLB中被锁定的地址变换条目 80
4.7 存储访问失效 80
4.7.1 MMU失效（MMU Fault） 80
4.7.2 外部存储访问失效（External Abort） 81
第5章 ARM处理器的Cache和Write Buffer 82
本章主要介绍了ARM处理器高速缓存（Cache）和写缓存（Write Buffer）的工作原理，使读者了解如何提高处理器的性能。
5.1 Cache和Write Buffer一般性介绍 82
5.1.1 Cache工作原理 82
5.1.2 地址映像方式 83
5.1.3 Cache写入方式原理简介 84
5.1.4 关于Write-through和Write-back 85
5.1.5 Cache替换策略 86
5.1.6 使用Cache的必要性 87
5.1.7 使用Cache的可行性 87
5.2 ARM处理器中的Cache和Write Buffer 88
5.2.1 基本概念 88
5.2.2 Cache工作原理 88
5.2.3 Cache地址映射和变换方法 89
5.2.4 Cache分类 90
5.2.5 Cache替换算法 91
5.2.6 Cache内容锁定 91
5.2.7 MMU映射描述符中B位和C位的含义 92
5.2.8 Cache和Writer Buffer编程接口 93
5.3 ARM处理器的快速上下文切换技术 94
5.3.1 FCSE概述 94
5.3.2 FCSE原理 94
5.3.3 FCSE编程接口 95
第6章 ARM处理器存储访问一致性问题 97
本章介绍了在支持MMU、Cache和DMA的系统中可能出现的存储访问一致性问题，以及Linux中解决类似问题的方法。
6.1 存储访问一致性问题介绍 97
6.1.1 地址映射关系变化造成的数据不一致性 97
6.1.2 指令cache的数据不一致性问题 98
6.1.3 DMA造成的数据不一致问题 99
6.1.4 指令预取和自修改代码 99
6.2 Linux中解决存储访问一致性问题的方法 99
第7章 ARM处理器工作模式与异常中断处理 101
本章主要介绍了ARM处理器的工作模式和异常中断处理过程，这是ARM处理器系统启动程序编写者或Bootloader开发人员的必备知识。
7.1 ARM处理器工作模式 101
7.2 ARM处理器异常中断向量表和优先级 103
7.3 ARM处理器异常中断处理 104
7.3.1 进入异常中断处理 104
7.3.2 退出异常中断处理 105
7.4 ARM处理器的中断（IRQ或FIQ） 109
第8章 ARM处理器启动过程 110
本章根据笔者的开发经验介绍了ARM处理器系统的启动过程以及编写ARM处理器系统启动程序需要注意的事项。
8.1 ARM处理器上电/复位操作 110
8.2 ARM处理器系统初始化过程 111
8.3 ARM处理器系统初始化编程注意事项 111
第9章 嵌入式系统设计与调试 113
本章根据笔者10多年的开发经验介绍了嵌入式系统的设计流程和调试方法，列举了大量笔者工作中碰到的实际案例。本章内容对于嵌入式系统硬件开发和调试有较高的参考、指导价值。
9.1 嵌入式系统设计流程 113
9.2 嵌入式系统硬件原理设计与审核 114
9.3 硬件设计工具软件 117
9.4 嵌入式系统调试仿真工具 117
9.5 嵌入式系统调试诊断方法 118
第10章 自制简易JTAG下载烧写工具 123
本章根据笔者自己制作简易JTAG线缆的经验，介绍了简易JTAG线缆的硬件原理和软件流程，这是初学者必备的最廉价的工具，必须掌握。
10.1 JTAG简介 123
10.1.1 一些基本概念 124
10.1.2 JTAG接口信号 124
10.1.3 TAP控制器的状态机 125
10.1.4 JTAG接口指令集 129
10.2 简易JTAG线缆原理 130
10.2.1 PC并口定义 130
10.2.2 PC并口的寄存器 131
10.2.3 简易JTAG线缆原理图 133
10.2.4 简易JTAG线缆烧写连接图（见图10-5） 134
10.3 简易JTAG烧写代码分析 135
10.3.1 简易JTAG烧写程序（flashp）使用说明 135
10.3.2 flash与CPU连接及flash属性描述文件 136
10.3.3 简易JTAG烧写程序的执行逻辑和流程 138
第2部分 Linux内核开发初步
第11章 Bootloader 142
本章根据笔者的工作经验介绍了流行的几种Bootloader、Bootloader应该具备的基本功能以及Bootloader的裁剪与移植。
11.1 Bootloader的任务和作用 142
11.2 各种各样的Bootloader 143
11.3 Bootloader编译环境 144
11.4 Bootloader的移植与裁减 145
11.5 编译Bootloader 145
11.6 烧写Bootloader 146
11.7 Bootloader使用举例 148
11.8 Bootloader修改举例 149
第12章 创建嵌入式Linux开发环境 151
本章介绍了如何创建嵌入式系统Linux内核交叉开发环境，本章和后续3章的内容是嵌入式系统Linux内核开发的基础，必须掌握。
12.1 安装Linux host 151
12.2 在虚拟机中安装Linux host 152
12.3 安装Linux交叉编译环境 157
12.4 在主机上设置TFTP Server 160
12.5 在主机上设置DHCP Server 161
12.6 在主机上设置Telnet server 161
12.7 在开发过程中使用NFS 162
12.8 设置超级终端 163
第13章 编译Linux内核 166
本章介绍了Linux内核的配置和编译方法。
13.1 获取Linux内核源代码 166
13.2 Linux内核目录结构 166
13.3 配置Linux内核 167
13.4 编译Linux内核 168
第14章 创建Linux根文件系统 170
本章介绍了Linux的根文件系统的结构以及创建根文件系统的方法。
14.1 根文件系统概述 170
14.2 根文件系统目录结构 171
14.3 获取根文件系统组件源代码 171
14.4 编译根文件系统源代码 171
14.5 创建一个32MB的RAMDISK根文件系统 173
14.6 在根文件系统中添加驱动模块或者应用程序 173
第15章 固化Linux内核和根文件系统 174
本章介绍了固化（烧写）Linux内核和根文件系统的方法。
第16章 关于Clinux 176
本章简要介绍了Clinux与标准Linux的区别。
16.1 Clinux简介 176
16.2 Clinux源代码目录结构 177
16.3 Clinux与标准Linux的区别 178
16.4 编译Clinux 179
第3部分 Linux 2.6内核原理
第17章 Linux 2.6.10@ARM启动过程 182
本章以start_kernel()和init()函数中调用到的函数说明的方式，介绍了从Linux汇编代码入口到init内核进程最后调用用户空间init命令的Linux整个启动过程。本章内容是笔者之一次阅读Linux内核源代码时对这些函数的注释，仅供读者了解start_kernel()和init()函数中调用到的每个函数的大致功能时使用。
17.1 Linux 2.6.10中与ARM处理器平台硬件相关的结构和全局变量 182
17.1.1 相关数据结构 182
17.1.2 相关全局变量 187
17.2 Linux汇编代码入口 189
17.3 Linux汇编入口处CPU的状态 189
17.4 start_kernel()函数之前的汇编代码执行过程 190
17.5 start_kernel()函数中调用的函数介绍 192
17.5.1 lock_kernel()函数 192
17.5.2 page_address_init()函数 192
17.5.3 printk(linux_banner) 193
17.5.4 setup_arch(&command_line)函数 193
17.5.5 setup_per_cpu_areas()函数 198
17.5.6 p_prepare_boot_cpu()函数 199
17.5.7 sched_init()函数 199
17.5.8 build_all_zonelists()函数 200
17.5.9 page_alloc_init()函数 200
17.5.10 printk(Kernel command line: %s\n, saved_command_line) 201
17.5.11 parse_early_param()函数 201
17.5.12 parse_args()函数 201
17.5.13 sort_main_extable()函数 202
17.5.14 trap_init()函数 202
17.5.15 rcu_init()函数 202
17.5.16 init_IRQ()函数 203
17.5.17 pidhash_init()函数 203
17.5.18 init_timers()函数 203
17.5.19 softirq_init()函数 204
17.5.20 time_init()函数 204
17.5.21 console_init()函数 205
17.5.22 profile_init()函数 206
17.5.23 local_irq_enable()函数 207
17.5.24 vfs_caches_init_early()函数 207
17.5.25 mem_init()函数 208
17.5.26 kmem_cache_init()函数 210
17.5.27 numa_policy_init()函数 225
17.5.28 calibrate_delay()函数 227
17.5.29 pidmap_init()函数 228
17.5.30 pgtable_cache_init()函数 229
17.5.31 prio_tree_init()函数 229
17.5.32 anon_vma_init()函数 229
17.5.33 fork_init(num_physpages)函数 229
17.5.34 proc_caches_init()函数 230
17.5.35 buffer_init()函数 231
17.5.36 unnamed_dev_init()函数 231
17.5.37 security_init()函数 231
17.5.38 vfs_caches_init(num_physpages)函数 232
17.5.39 radix_tree_init()函数 237
17.5.40 signals_init()函数 237
17.5.41 page_writeback_init()函数 237
17.5.42 proc_root_init()函数 238
17.5.43 check_bugs()函数 240
17.5.44 acpi_early_init()函数 244
17.5.45 rest_init()函数 244
17.6 init()进程执行过程 265
17.6.1 p_prepare_cpus(max_cpus)函数 265
17.6.2 do_pre_p_initcalls()函数 265
17.6.3 fixup_cpu_present_map()函数 267
17.6.4 p_init()函数 267
17.6.5 sched_init_p()函数 268
17.6.6 populate_rootfs()函数 268
17.6.7 do_basic_setup()函数 283
17.6.8 sys_access()函数 292
17.6.9 free_initmem()函数 301
17.6.10 unlock_kernel()函数 301
17.6.11 numa_default_policy()函数 302
17.6.12 sys_dup()函数 302
17.6.13 execve()函数 302
第18章 Linux内存管理 305
从本章开始，笔者将带领读者走进神秘的Linux内核世界。笔者在阅读内核源代码以及两本相关参考书（见参考文献）的基础上，以自己的理解和语言总结概括了Linux内核每个组件的原理。笔者对与每个内核组件相关的关键数据结构和全局变量作了尽量详尽的说明，并且对核心函数进行了详细注释，在向读者灌输理论知识的同时引导读者自己去阅读、分析Linux内核源代码。本章讲解了Linux内核之一大核心组件“内存管理”的原理和实现内幕。
18.1 Linux内存管理概述 305
18.1.1 Linux内存管理的一些基本概念 305
18.1.2 内存管理相关数据结构 309
18.1.3 内存管理相关宏和全局变量 330
18.1.4 Linux内存管理的任务 341
18.1.5 Linux中的物理和虚拟存储空间布局 341
18.2 为虚拟（线性地址）存储空间建立页表 345
18.3 设置存储空间的访问控制属性 348
18.4 Linux中的内存分配和释放 350
18.4.1 在系统启动初期申请内存 350
18.4.2 系统启动之后的内存分配与释放 360
第19章 Linux进程管理 480
本章讲解了Linux内核第二大核心组件“进程管理”的原理和实现内幕。
19.1 进程管理概述 480
19.1.1 进程相关概念 480
19.1.2 进程分类 481
19.1.3 0号进程 481
19.1.4 1号进程 481
19.1.5 其他一些内核线程 482
19.1.6 进程描述符（struct task_struct） 482
19.1.7 进程状态 482
19.1.8 进程标识符（PID） 483
19.1.9 current宏定义 484
19.1.10 进程链表 484
19.1.11 PID hash表和链表 485
19.1.12 硬件上下文（Hardware Context） 485
19.1.13 进程资源限制 485
19.1.14 进程管理相关数据结构 486
19.1.15 进程管理相关宏定义 502
19.1.16 进程管理相关全局变量 514
19.2 进程管理相关初始化 520
19.3 进程创建与删除 529
19.4 进程调度 551
19.4.1 进程类型 553
19.4.2 进程调度类型 554
19.4.3 基本时间片计算方法 555
19.4.4 动态优先级算法 556
19.4.5 交互式进程 556
19.4.6 普通进程调度 557
19.4.7 实时进程调度 557
19.4.8 进程调度函数分析 558
19.5 进程切换 576
19.6 用户态进程间通信 581
19.6.1 信号（Signal） 581
19.6.2 管道（pipe）和FIFO（命名管道） 627
19.6.3 进程间通信原语（System V IPC） 641
第20章 Linux文件管理 651
本章讲解了Linux内核第三大核心组件“文件系统”的原理和实现内幕。
20.1 文件系统概述 651
20.1.1 Linux文件管理相关概念 652
20.1.2 Linux文件管理相关数据结构 657
20.1.3 Linux文件管理相关宏定义 682
20.1.4 Linux文件管理相关全局变量 691
20.2 文件管理相关初始化 699
20.3 文件系统类型注册 711
20.4 挂接文件系统 712
20.5 文件系统类型超级块读取 730
20.5.1 get__single()通用超级块读取函数 731
20.5.2 get__nodev()通用超级块读取函数 737
20.5.3 get__bdev()通用超级块读取函数 738
20.5.4 get__pseudo()通用超级块读取函数 740
20.6 路径名查找 747
20.7 访问文件操作 759
20.7.1 打开文件 759
20.7.2 关闭文件 766
20.7.3 读文件 768
20.7.4 写文件 785
20.8 异步I/O系统调用 792
20.9 Linux特殊文件系统 792
20.9.1 rootfs文件系统 793
20.9.2 sysfs文件系统 797
20.9.3 devfs设备文件系统 800
20.9.4 bdev块设备文件系统 803
20.9.5 ramfs文件系统 804
20.9.6 proc文件系统 804
20.10 磁盘文件系统 813
20.10.1 ext2文件系统相关数据结构 813
20.10.2 ext2文件系统磁盘分区格式 819
20.10.3 ext2文件系统的各种文件 820
20.10.4 创建ext2文件系统 821
20.10.5 ext2文件系统的操作方法 822
20.11 关于initramfs 824
20.11.1 initramfs概述 824
20.11.2 initramfs与initrd的区别 824
20.11.3 initramfs相关全局变量 825
20.11.4 initramfs被编译链接的位置 825
20.11.5 initramfs文件的生成过程 825
20.11.6 initramfs二进制文件格式说明（cpio格式） 828
20.11.7 initramfs二进制文件和列表文件对照示例 829
20.11.8 initramfs利弊 830
20.12 关于initrd 830
20.12.1 initrd概述 830
20.12.2 initrd相关全局变量 831
20.13 关于gzip压缩文件 832
第21章 Linux模块设计 834
本章讲解了Linux内核模块程序与应用程序的区别以及如何编写和加载Linux内核模块程序。
21.1 Linux模块设计概述 834
21.2 Linux的内核空间和用户空间 834
21.3 内核模块与应用程序的区别 835
21.4 编译模块 837
21.5 装载和卸载模块 837
21.6 模块层叠 838
21.7 模块版本依赖 839
21.8 模块编程示例 839
第22章 Linux系统异常中断管理 841
本章讲解了Linux内核如何管理系统异常中断以及Linux系统调用的实现内幕。
22.1 Linux异常中断处理 841
22.2 指令预取和数据访问中止异常中断处理 849
22.2.1 指令预取中止异常中断处理 850
22.2.2 数据访问中止异常中断处理 858
22.3 Linux中断处理 863
22.3.1 内核模式下的中断处理 863
22.3.2 用户模式下的中断处理 867
22.4 从中断返回 868
22.5 Linux中断管理 869
22.5.1 Linux中断管理相关数据结构与全局变量 870
22.5.2 Linux中断管理初始化 872
22.5.3 安装和卸载中断处理程序 874
22.5.4 使能和禁止中断 878
22.6 Linux系统调用 880
22.6.1 Linux系统调用内核实现过程 880
22.6.2 从系统调用返回 889
22.6.3 Linux系统调用用户程序接口函数 890
22.6.4 Linux系统调用用户接口函数与内核实现函数之间参数传递 899
第23章 Linux软中断和工作队列 901
本章讲解了Linux内核中的两种延迟处理机制“软中断”和“工作队列”的原理和实现。
23.1 概述 901
23.2 Linux软中断 902
23.2.1 软中断相关数据结构和全局变量 903
23.2.2 软中断初始化 904
23.2.3 软中断的核心操作函数do_softirq() 908
23.2.4 软中断看护进程执行函数ksoftirqd() 912
23.2.5 如何使用软中断 913
23.3 Linux工作队列 918
23.3.1 Linux工作队列相关数据结构和全局变量 918
23.3.2 Linux工作队列初始化 921
23.3.3 将工作加入到工作队列中 924
23.3.4 工作者进程执行函数worker_thread() 928
23.3.5 使用Linux工作队列 931
第24章 Linux并发与竞态 933
本章讲解了Linux内核同步机制，包括几种锁定技术以及免锁算法。
24.1 并发与竞态概述 933
24.1.1 Linux中的并发源 934
24.1.2 竞态可能导致的后果 934
24.1.3 避免竞态的规则 934
24.2 消除竞态的“锁定”技术 935
24.2.1 信号量（semphore）和互斥体（mutual exclusion） 935
24.2.2 读写信号量（rw_semaphore） 938
24.2.3 完成量（completion） 941
24.2.4 自旋锁（spinlock_t） 942
24.2.5 读写自旋锁（rwlock_t） 946
24.2.6 使用“锁定”技术的注意事项 949
24.3 消除竞态的非“锁定”方法 949
24.3.1 免锁算法 949
24.3.2 原子操作 950
24.3.3 位操作 951
24.3.4 顺序锁 952
24.3.5 读-复制-更新（Read-Copy-Update，RCU） 954
第25章 Linux设备驱动程序 958
本章讲解了Linux内核第四大核心组件“设备驱动”的原理和实现内幕。同时还总结归纳了编写各种设备驱动程序的方法和步骤。
25.1 设备驱动程序概述 958
25.1.1 设备驱动程序组成部分 959
25.1.2 设备号 959
25.1.3 设备文件 960
25.1.4 编写设备驱动程序的关键 961
25.2 字符设备驱动程序 961
25.2.1 字符设备相关数据结构 961
25.2.2 字符设备相关全局变量 963
25.2.3 字符设备驱动程序全局初始化 963
25.2.4 为字符设备分配设备号 964
25.2.5 注册字符设备驱动程序 968
25.2.6 字符设备的操作方法 971
25.2.7 用户对字符设备驱动程序的调用过程 972
25.2.8 如何编写字符设备驱动程序 974
25.2.9 关于TTY设备驱动程序 974
25.2.10 控制台设备驱动程序 975
25.3 块设备驱动程序 986
25.3.1 块设备相关数据结构 986
25.3.2 块设备相关宏定义 997
25.3.3 块设备相关全局变量 999
25.3.4 块设备驱动程序全局初始化 1004
25.3.5 为块设备分配主设备号 1006
25.3.6 注册块设备驱动程序 1009
25.3.7 块设备驱动程序的操作方法 1017
25.3.8 调用块设备驱动程序过程 1017
25.3.9 I/O调度 1031
25.3.10 如何编写块设备驱动程序 1032
25.4 网络设备驱动程序 1033
25.4.1 网络设备驱动程序概述 1033
25.4.2 网络设备相关数据结构 1034
25.4.3 网络设备相关宏定义 1044
25.4.4 网络设备相关全局变量 1045
25.4.5 创建net_device结构 1046
25.4.6 注册网络设备 1048
25.4.7 网络设备的操作方法 1050
25.4.8 网络设备中断服务程序 1051
25.4.9 如何编写网络设备驱动程序 1051
25.5 PCI设备驱动程序 1052
25.5.1 PCI接口定义 1053
25.5.2 PCI设备的三个地址空间 1057
25.5.3 PCI总线仲裁 1058
25.5.4 PCI设备编号 1059
25.5.5 如何访问PCI配置空间 1059
25.5.6 如何配置PCI设备 1061
25.5.7 PCI驱动程序相关数据结构 1062
25.5.8 PCI驱动程序相关宏定义 1068
25.5.9 PCI驱动程序相关全局变量 1068
25.5.10 Bootloader和内核做的事 1069
25.5.11 PCI驱动程序注册 1069
25.5.12 PCI驱动程序接口函数 1071
25.5.13 如何编写PCI驱动程序 1072
第4部分 Linux内核开发高级指南
第26章 Linux系统参数设置 1076
从本章开始的后续章节主要讲解了比较高级或者平时较少关注的Linux内核方面的知识，本章讲解了Linux中的4种系统参数格式和设置方法。
26.1 旗语系统参数（tag） 1076
26.1.1 与旗语系统参数相关数据结构和全局变量 1076
26.1.2 旗语系统参数说明 1082
26.1.3 旗语系统参数设置方法 1084
26.2 前期命令行设置的系统参数 1084
26.2.1 与前期命令行系统参数相关数据结构和全局变量 1084
26.2.2 前期命令行设置的系统参数说明 1085
26.2.3 前期命令行系统参数设置方法 1086
26.2.4 如何添加自己的前期命令行设置的系统参数 1087
26.3 老式命令行系统参数 1087
26.3.1 与老式命令行系统参数相关数据结构和全局变量 1087
26.3.2 老式命令行设置的系统参数说明 1088
26.3.3 老式命令行设置的系统参数设置方法 1089
26.3.4 如何添加自己的老式命令行设置的系统参数 1089
26.4 命令行系统参数 1089
26.4.1 与命令行系统参数相关数据结构和全局变量 1089
26.4.2 命令行设置的系统参数说明 1090
26.4.3 命令行设置的系统参数设置方法 1090
第27章 Linux内核调试 1091
本章介绍了Linux内核的调试方法。
27.1 打开Linux内核及其各模块自带的调试开关 1091
27.2 内核剖析（Profiling） 1093
27.3 通过打印调试（printk） 1095
27.3.1 关于printk() 1095
27.3.2 内核信息级别 1096
27.3.3 打印速度限制 1097
27.3.4 控制台重定向 1098
27.4 使用proc文件系统调试 1098
27.5 oops消息 1098
27.6 通过跟踪命令strace调试 1099
27.7 使用gdb、kdb、kgdb调试 1099
第28章 Linux内核移植 1101
本章介绍了Linux内核的移植方法。
第29章 Linux内核优化 1104
本章介绍了Linux内核的优化方法。
29.1 编译优化 1104
29.2 根据CPU特性进行优化 1105
29.3 对内核进行裁减 1105
29.4 优化系统内存配置 1106
29.5 优化系统启动过程以缩减系统启动时间 1106
29.6 内存映射优化 1107
29.7 工具软件辅助优化 1107
第30章 Linux定时器 1109
本章介绍了Linux内核的软件定时器。
30.1 定时器相关数据结构 1109
30.2 定时器相关宏定义 1111
30.3 定时器相关全局变量 1112
30.4 定时器和时钟初始化 1113
30.5 获取系统时间 1114
30.6 延迟函数 1115
30.7 与定时器相关系统调用 1115
30.8 使用定时器方法 1116
第31章 杂项 1117
本章介绍了PER_CPU变量以及Linux中的数据类型定义。
31.1 per_cpu变量 1117
31.2 Linux中的数据类型定义 1118
第32章 编译链接文件说明 1119
本章注释了ARM处理器系统中Linux内核的链接文件，以帮助读者了解编译出来的Linux内核各区段在内存中的存放位置。
参考文献 1125
linux系统C语言的nm是什么意思
就是搜索动态链接库 库函数的
不是C语言吧？是系统命令。用来列举object文件(比如编译出的a.out)的symbols.
用法是：
nm
>
具体而言，nm用来列出目标文件的符号清单。
如果没有为nm命令指出目标文件，则nm假定目标文件是a.out。下面列出该命令的任选项，大部分支持“-”开头的短格式和“-“开头的长格式。
-A、-o或–print-file-name：在找到的各个符号的名字前加上文件名，而不是在此文件的所有符号前只出现文件名一次。
例如nmlibtest.a的输出如下：
CPThread.o:
TMain__8CPThreadPv
TStart__8CPThread
T_._8CPThread
T__8CPThread
?__FRAME_BEGIN__
…………………………………
则nm-A的输出如下：
libtest.a:CPThread.o:TMain__8CPThreadPv
libtest.a:CPThread.o:TStart__8CPThread
libtest.a:CPThread.o:T_._8CPThread
libtest.a:CPThread.o:T__8CPThread
libtest.a:CPThread.o:?__FRAME_BEGIN__
…………………………………………………………..
-a或–debug-syms：显示调试符号。
-B：等同于–format=bsd，用来兼容MIPS的nm。
-C或–demangle：将低级符号名解码(demangle)成用户级名字。这样可以使得C 函数名具有可读性。
-D或–dynamic：显示动态符号。该任选项仅对于动态目标(例如特定类型的共享库)有意义。
-fformat：使用format格式输出。format可以选取bsd、sysv或posix，该选项在GNU的nm中有用。默认为bsd。
-g或–extern-only：仅显示外部符号。
-n、-v或–numeric-sort：按符号对应地址的顺序排序，而非按符号名的字符顺序。
-p或–no-sort：按目标文件中遇到的符号顺序显示，不排序。
-P或–portability：使用POSIX.2标准输出格式代替默认的输出格式。等同于使用任选项-fposix。
-s或–print-armap：当列出库中成员的符号时，包含索引。索引的内容包含：哪些模块包含哪些名字的映射。
-r或–reverse-sort：反转排序的顺序(例如，升序变为降序)。
–size-sort：按大小排列符号顺序。该大小是按照一个符号的值与它下一个符号的值进行计算的。
-tradix或–radix=radix：使用radix进制显示符号值。radix只能为“d”表示十进制、“o”表示八进制或“x”表示十六进制。
–target=bfdname：指定一个目标代码的格式，而非使用系统的默认格式。
-u或–undefined-only：仅显示没有定义的符号(那些外部符号)。
-l或–line-numbers：对每个符号，使用调试信息来试图找到文件名和行号。对于已定义的符号，查找符号地址的行号。对于未定义符号，查找指向符号重定位入口的行号。如果可以找到行号信息，显示在符号信息之后。
-V或–version：显示nm的版本号。
–help：显示nm的任选项。
ar cs libmy.a//创建一个库
ar rs libmy.a 1.o//增加一个模块
ar t libmy.a//显示库里的模块
关于linux radix树的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
