Maxw的小站

可加载的内核模块

练习 1

准备好实验报告

练习 2: 编译内核模块

1. 步骤:

   1 2 3 4 5 6 7

   # 在 Linux Lab 集群上 mkdir -p /project/scratch01/compile/your-username/modules cd /project/scratch01/compile/your-username/modules # 保存 simple_module.c 和 Makefile (内容: obj-m := simple_module.o) module add arm-rpi export LINUX_SOURCE=/path/to/your/linux_source/linux # 设置内核源码路径 make -C $LINUX_SOURCE ARCH=arm CROSS_COMPILE=arm-linux-gnueabihf- M=$PWD modules

2. 答案: 提交 make 命令的完整输出。

练习 3: 加载模块与系统日志

1. 步骤 (在树莓派上):

   1 2 3 4 5

   mkdir ~/modules # 使用 sftp 将 simple_module.ko 传输到此目录 sudo dmesg --clear sudo insmod ~/modules/simple_module.ko dmesg # 查看日志

2. 答案: 提交 dmesg 中显示的模块加载信息。

练习 4: 验证模块列表与卸载

1. 步骤:

   1 2 3 4

   lsmod # 确认 simple_module 在列表中 sudo rmmod simple_module lsmod # 确认已移除 dmesg # 查看卸载信息

2. 答案: 提交 lsmod 的输出（证明已卸载）和 dmesg 中显示的模块卸载信息。

练习 5: 访问内核变量 jiffies

1. 步骤:
   • 复制 simple_module.c 为 jiffies_module.c。
   • 修改其 init 和 exit 函数，使用 printk 打印 jiffies 变量（类型 extern unsigned long volatile jiffies;）。
   • 更新 Makefile: obj-m += jiffies_module.o。
   • 重新编译并传输 jiffies_module.ko 到树莓派。
   • 加载并卸载模块，观察 dmesg。
2. 答案:
   • 提交 dmesg 中显示加载和卸载时 jiffies 值的日志消息。
   • 计算并说明两条消息之间发生的滴答数（tick count）。

需提交的内容

请提交一个包含以下内容的压缩包或文档： 1. 答案文件: 包含上述所有练习的答案。 2. 源代码文件: 你新创建的 jiffies_module.c 文件。

可选拓展练习

练习 6: 模块初始化返回值实验

• 任务: 修改 init 函数，使其分别返回正数和负数（错误码，参见 /include/uapi/asm-generic/errno-base.h）。
• 提示: 描述加载模块时发生的情况及其在系统日志中的表现。

练习 7: 探查导出的内核符号

• 任务: 查看 /proc/kallsyms 文件（例如 cat /proc/kallsyms），了解内核符号表。查找带有 __kstrtab_ 和 __ksymtab_ 前缀的符号（这些是可供模块使用的导出符号）。
• 提示: 内核符号是 Linux 内核代码中定义的函数、变量、数据结构等的名称标签。它们代表了在内核地址空间中的一个特定内存地址。 可以将内核符号理解为内核的“公共接口”或“入口点”。主要有两种类型：
• 导出的符号：这些是内核明确声明为可以被外部模块使用的符号。例如，printk（内核的 printf）、kmalloc（内核的内存分配函数）等。模块通过使用 EXPORT_SYMBOL() 或 EXPORT_SYMBOL_GPL() 宏来导出它们的符号，以便其他模块可以使用。
• 非导出的符号：这些是内核内部的静态函数或变量，只在它们被定义的文件或内核的特定部分中使用。它们对于内核模块是不可见的，主要用于内核自身的组织
• EXPORT_SYMBOL(printk) 在编译后创建了两个内部符号：__ksymtab_printk 和 __kstrtab_printk。
  • __ksymtab_printk 是一个结构体，包含了 printk 的地址和指向 __kstrtab_printk 的指针。
  • __kstrtab_printk 是一个字符串，存储着 printk 的名字。
• 内核使用这个结构来高效地通过名字查找函数的地址

练习 8: 实现用户态读取 CPU 周期计数器 (CCNT) 的模块

• 任务 (如果之前在系统调用工作室未完成):
  • 将提供的驱动文件放入你的内核源码树的 arch/arm/include/asm 目录。
  • 下载 enable_ccnt.c 内核模块代码到你的模块目录。
  • 编译、传输并加载此模块 (insmod enable_ccnt.ko)。
  • 使用 dmesg | tail 验证加载成功。
• 任务 (主要部分):
  • 在树莓派上创建一个用户态程序。
  • 该程序应 #include 你获取的驱动头文件。
  • 调用 unsigned long long pmccntr_get(void) 函数两次。
• 答案:
  • 说明运行一次 pmccntr_get() 函数大约需要多少 CPU 周期（计算两次调用的差值）。
  • 如果你在系统调用工作室完成过类似的练习，请对比直接调用此函数与通过系统调用获取周期计数所需的周期数。

文章内容来自 LWN.net

文章摘要 (Summary)

这篇发表于 2013 年 2 月的文章讨论了 Linux 内核中 IDR 子系统 API 的一次重大简化改革，由开发者 Tejun Heo 主导。IDR 机制用于高效分配和管理整数 ID（例如设备名、POSIX 定时器 ID 等），其旧 API 因其复杂性和潜在的竞争条件而闻名。

核心问题：旧 API 的缺陷 1. 两步分配：需要先调用 idr_pre_get() 预分配内存（可休眠），再调用 idr_get_new() 获取 ID（可原子上下文）。 2. 必须重试循环：idr_get_new() 可能因预分配内存被其他 CPU 耗尽而失败（返回 -EAGAIN），要求调用者编写冗长且易错的循环重试代码。 3. 全局资源竞争：idr_pre_get() 预分配的内存是全局的，多个 CPU 竞争时，后执行的 idr_get_new() 可能因资源不足而失败，迫使代码退出原子上下文进行重试，这条路径往往缺乏测试。

解决方案：新 API 的改进 Tejun Heo 引入了三个新函数来简化流程： 1. idr_preload(gfp_t gfp_mask): 为当前 CPU 预分配内存，并禁用抢占以防止预分配的内存被偷。 2. idr_alloc(...): 单次调用即可完成 ID 分配和关联。它接受 ID 范围参数，并仅在真正需要时（未预分配或预分配不足）才使用 gfp_mask 分配内存。它只会在内存分配彻底失败时报错，消除了对 -EAGAIN 的重试循环需求。 3. idr_preload_end(): 在 idr_alloc 后调用，重新启用抢占。

关键优势： * 更简单：消除了遍布内核的百余处重复、易错的样板代码。 * 更可靠：通过每 CPU 预分配和禁用抢占，基本消除了在原子上下文中因资源竞争而失败的需要。 * 更灵活：idr_alloc 可以指定 ID 范围，并且如果能在进程上下文调用，甚至可以完全省略 idr_preload/idr_preload_end。

社区反应： 尽管大部分开发者接受了这个改动（给出了 Acked-by），但 Eric Biederman 表达了强烈反对，认为新 API 的 idr_preload 像是一种难以理解的“魔法”。然而，文章作者（Jonathan Corbet）预测，新 API 带来的巨大简化优势将使其最终被内核社区接受。

新旧 API 对比总结

结论

这篇文章记录了一个经典的内核优化案例：通过巧妙的设计（利用每 CPU 数据和禁用抢占）将一个复杂、易错、充满竞争条件的旧接口，重构为一个简洁、可靠、高效的新接口。尽管存在一些争议，但简化并提升广泛使用的底层 API 的价值是极其巨大的，这很可能是新方案最终被采纳的原因。这正是 Linux 内核持续演进的一个缩影。

188.买卖股票的最佳时机IV

买卖股票三的扩展版，从最多两次交易扩充到k次交易。注意买入和卖出某个数量的股票都要单列一列dp，并采用不同的状态转移方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2*k+1, 0));
        for(int i = 1; i<=2*k; i++){
            if(i % 2 == 1)dp[0][i] -= prices[0];
        }
        if(prices.size() == 1)return 0;
        for(int i = 1; i < prices.size(); i++){
            for(int j = 1; j<=2*k; j+=2){
                dp[i][j] = max(dp[i-1][j-1] - prices[i], dp[i-1][j]);
            }
            for(int j = 2; j<=2*k; j+=2){
                // printf("index of prices: %d, sold out stock id: %d\n", i, j);
                dp[i][j] = max(dp[i-1][j-1] + prices[i], dp[i-1][j]);
            }
        }
        return dp[prices.size()-1][2*k];
    }
};

309.最佳买卖股票时机含冷冻期

我这道题还是写复杂了。其实不规定买入次数，就不需要每次买卖都开一个状态了，每天都计算持有/非持有状态即可，还可以省空间复杂度 我采用的思路延续了每次买入都有两个不同状态的方案，当计算卖出的时候往前比较两天，就是需要注意第二天持有股票状态的递推公式的特殊情况（选择第二天买入还是第一天买入）。其实采用仅四个状态也可以： 状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有） 不持有股票状态，这里就有两种卖出股票状态 - 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作） - 状态三：今天卖出股票 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1)return 0;
        int status = prices.size()*2;
        vector<vector<int>> dp(prices.size(), vector<int>(status+1, 0));
        for(int i = 1; i <= status; i += 2){
            dp[0][i] -= prices[0];
        }
        for(int i = 1; i < prices.size(); i++){
            for(int j = 1; j <= status; j += 2){
                // printf("prices: %d, hold stock cnt: %d\n", i, j);
                if(i >= 3){
                    dp[i][j] = max(dp[i-2][j-1] - prices[i], dp[i-1][j]);
                }else{
                    dp[i][j] = max(-prices[i], dp[i-1][j]);
                }
            }
            for(int j = 2; j <= status; j += 2){
                dp[i][j] = max(dp[i-1][j-1] + prices[i], dp[i-1][j]);
            }
        }
        // for(auto l: dp){
        //     cout<<"prices line ";
        //     for(auto i: l){
        //         cout<<i<<' ';
        //     }
        //     cout<<endl;
        // }
        return dp[prices.size()-1][status];
    }
};

714.买卖股票的最佳时机含手续费

这题延续 122.买卖股票的最佳时机II 的思路即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size() == 1)return 0;
        int status = prices.size()*2;
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
        dp[0][1] -= prices[0];
        for(int i = 1; i< prices.size(); i++){
            dp[i][0] = max(dp[i-1][1]+prices[i]-fee, dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);
        }
        // for(int i = 0; i<dp.size(); i++){
        //     for(int j = 0; j<dp[0].size(); j++){
        //         cout<<dp[i][j]<<' ';
        //     }
        //     cout<<endl;
        // }
        return dp[prices.size()-1][0];
    }
};

Linux 内核模块开发简介

设备类型分类

伪设备示例：

1
2
3
4
5

/dev/random   # 内核随机数生成器
/dev/null     # 空设备（丢弃所有写入）
/dev/zero     # 零设备（提供无限\0字节）
/dev/full     # 满设备（写入总返回ENOSPC错误）
/dev/mem      # 物理内存访问设备

内核模块开发

Hello World 模块示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

/* 模块加载时执行 */
static int __init hello_init(void) 
{
    printk(KERN_INFO "I bear a charmed life.\n"); 
    return 0;  // 返回0表示成功
}

/* 模块卸载时执行 */
static void __exit hello_exit(void) 
{
    printk(KERN_INFO "Out, out, brief candle!\n");
}

/* 注册入口/出口函数 */
module_init(hello_init);  // 不是函数调用，而是宏定义
module_exit(hello_exit);

/* 模块元信息 */
MODULE_LICENSE("GPL");                  // 必须声明许可证
MODULE_AUTHOR("Shakespeare");           // 作者信息
MODULE_DESCRIPTION("Hello World Module"); // 模块描述

关键机制解析

1. 入口函数：
   • 形式：int init_func(void)
   • 职责：注册资源/初始化硬件/分配数据结构
   • 返回值：0=成功，非0=失败
2. 出口函数：
   • 形式：void exit_func(void)
   • 职责：释放资源/复位硬件/清理状态
3. 许可证声明：

   1	MODULE_LICENSE("GPL"); // 合法选项：GPL/MIT/BSD等

   • 非GPL模块会导致内核标记为"tainted"
   • 无法调用GPL-only符号

模块构建指南

集成到内核源码树（推荐）

1. 选择路径：
   • 字符设备 → drivers/char/
   • 块设备 → drivers/block/
   • USB设备 → drivers/usb/
2. 修改Makefile：

   1 2 3 4 5 6 7

   # drivers/char/Makefile 添加 obj-$(CONFIG_FISHING_POLE) += fishing/ # drivers/char/fishing/Makefile 内容 obj-$(CONFIG_FISHING_POLE) += fishing.o fishing-objs := main.o line.o # 多文件模块 EXTRA_CFLAGS += -DTITANIUM_POLE # 自定义编译标志

外部独立构建

1. Makefile示例：

   1 2 3 4 5

   obj-m := fishing.o fishing-objs := fishing-main.o fishing-line.o all: make -C /path/to/kernel/source M=$(PWD) modules

2. 构建命令：

   1 2	# 在模块目录执行 make -C /lib/modules/$(uname -r)/build M=$PWD modules

   ### 模块管理

模块安装路径规范

1
2
3
4
5

# 标准安装路径模板
/lib/modules/$(uname -r)/kernel/<源码树路径>/<模块名>.ko

# 示例：2.6.34内核的钓鱼竿模块
/lib/modules/2.6.34/kernel/drivers/char/fishing.ko

安装命令：

1

sudo make modules_install  # 需root权限

模块依赖管理

1. 依赖关系生成

1
2
3
4
5

# 生成完整依赖关系
sudo depmod

# 增量更新（仅处理新模块）
sudo depmod -A

2. 依赖存储位置

1
2
3
4
5

# 依赖关系文件路径
/lib/modules/$(uname -r)/modules.dep

# 文件内容示例
kernel/drivers/char/fishing.ko: kernel/drivers/net/bait.ko

智能加载原理：
当加载 chum.ko 时，系统自动解析其依赖并先加载 bait.ko

模块加载与卸载

基础工具（不推荐）

高级工具（推荐）

1. 智能加载：

1
2
3
4
5

# 加载模块（自动处理依赖）
sudo modprobe fishing pole_length=300 material=titanium

# 查看加载的模块
lsmod | grep fishing

2. 安全卸载：

1
2
3
4
5

# 卸载模块（自动移除未用依赖）
sudo modprobe -r fishing

# 强制卸载（危险！）
sudo modprobe -rf fishing  # 可能破坏依赖树

内核配置与模块开发高级指南

配置选项管理 (Kconfig)

linux使用kbuild系统，可以通过修改Kconfig文件便捷地管理配置选项

1
2
3
4
5
6
7
8
9

# drivers/char/Kconfig 示例
config FISHING_POLE
    tristate "Fish Master 3000 support"  # 三态选项，表示模块在编译配置中可以内置编译到内核（Y），作为模块编译（M）或者不编译（N）
    default n                            # 默认禁用
    depends on FISH_TANK && !NO_FISHING  # 依赖条件
    select BAIT                          # 强制关联选项
    help                                 # 帮助文档
        Enable support for the Fish Master 3000 computer interface.
        Choose Y to build into kernel, M for module (fishing.ko), or N to disable.

核心指令解析： | 指令 | 功能 | 示例 | |----------------|----------------------------------|-----------------------------------| | tristate | 三态选项 (Y/M/N) | 驱动标准配置 | | bool | 布尔选项 (Y/N) | 特性开关 | | default | 默认值 | default y 默认启用 | | depends on | 依赖关系 | depends on NET 需网络支持 | | select | 强制启用其他选项 | select CRC32 自动启用CRC校验 | | if | 条件显示 | if EMBEDDED 嵌入式场景可见 | | help | 帮助文档 | 用户配置时的说明文本 |

模块参数系统

1. 基础参数声明

1
2
3

static int pole_length = 200;  // 默认值
module_param(pole_length, int, 0644);  // 整型参数
MODULE_PARM_DESC(pole_length, "Pole length in cm");

2. 高级参数类型

3. 参数传递方式

1
2
3
4
5
6
7

# 加载时指定参数
sudo modprobe fishing pole_length=300 material=carbon

# 查看参数信息
modinfo fishing
parm:           pole_length:Pole length in cm (int)
parm:           material:Construction material (charp)

4. sysfs集成

1
2

# 参数自动暴露到sysfs
/sys/module/fishing/parameters/pole_length  # 权限0644=rwr--r--

符号导出机制

1. 基础导出

1
2
3
4
5

// 声明可被模块调用的函数
int get_pole_strength(struct pole *p) {
    return p->load_capacity;
}
EXPORT_SYMBOL(get_pole_strength);  // 全局导出

2. GPL受限导出

1

EXPORT_SYMBOL_GPL(calculate_bait_ratio);  // 仅GPL模块可用

3. 导出规则

配置系统元选项

1
2
3
4
5
6
7

config EXPERIMENTAL
    bool "Enable experimental features"  # 高风险功能开关
    default n

config DEBUG_KERNEL
    bool "Kernel debugging"  # 调试选项总开关
    default y if DEBUG

关键元选项： - CONFIG_EMBEDDED：嵌入式系统优化选项 - CONFIG_BROKEN_ON_SMP：标记非SMP安全驱动 - CONFIG_EXPERIMENTAL：实验性功能入口

开发工作流示例

1. 添加新驱动

1
2
3
4
5
6
7
8
9
10
11

# 创建Kconfig
# drivers/char/fishing/Kconfig
config FISHING_PRO
    tristate "Professional Fishing Module"
    select FISHING_ADVANCED
    help
      Support for professional-grade fishing equipment

# 修改上级Kconfig
# drivers/char/Kconfig
source "drivers/char/fishing/Kconfig"

2. 实现参数化模块

1
2
3
4
5
6
7
8
9
10
11

#include <linux/moduleparam.h>

static char material[20] = "fiberglass";
module_param_string(material, material, sizeof(material), 0644);

static int lengths[] = {180, 240};
static int nr_lengths = 2;
module_param_array(lengths, int, &nr_lengths, 0444);

static bool enable_ai;
module_param(enable_ai, bool, 0644);

3. 编译验证

1
2
3
4
5
6
7

# 配置内核
make menuconfig
# -> Device Drivers -> Character devices -> Professional Fishing Module (M)

# 编译安装
make -j$(nproc) modules
sudo make modules_install

生产环境最佳实践

1. 参数安全：

   1 2 3 4 5 6 7 8 9 10

   static int max_load = 100; module_param(max_load, int, 0644); static int __init init_func(void) { if (max_load > MAX_SAFE_LIMIT) { pr_warn("Dangerous load limit %d, capping at %d\n", max_load, MAX_SAFE_LIMIT); max_load = MAX_SAFE_LIMIT; } }

2. 版本兼容：

   1 2 3 4 5 6 7

   #include <linux/version.h> #if LINUX_VERSION_CODE >= KERNEL_VERSION(5,15,0) // 新版内核API #else // 旧版兼容实现 #endif

3. 错误处理：

   1 2 3 4 5 6

   int err = register_device(); if (err) { // 彻底回滚初始化 unregister_previous(); return err; }

性能提示：高频访问的模块参数应复制到局部变量，避免频繁查sysfs

二叉树

1. 二叉搜索树（BST）核心特性

1
2
3

根节点左子树的所有节点值 < 根节点值
根节点右子树的所有节点值 > 根节点值
所有子树都是二叉搜索树

• 操作复杂度：
  • 查找：O(log n)
    
  • 有序遍历：O(n)
• 缺陷：不平衡树可能导致操作退化到O(n)

2. 自平衡二叉搜索树

1

叶子节点深度差 ≤ 1   →   树高度 = O(log n)

• 平衡机制：在插入/删除时自动调整结构
• 常见类型：
  • AVL树（严格平衡）
  • 红黑树（半平衡，Linux首选）

红黑树（Red-Black Trees）

六大约束条件

1. 节点非红即黑
2. 叶子节点（NIL）为黑
3. 叶子节点不存储数据
4. 非叶子节点必有双子
5. 红节点的子节点必为黑（核心约束）
6. 根到任意叶子的黑节点数相同

优势

• 插入/删除只需O(1)次旋转（AVL需O(log n)）
• 查找效率稳定在O(log n)
• 内存开销小（仅1bit存储颜色）

Linux实现（rbtree）

初始化

1
2

#include <linux/rbtree.h>
struct rb_root root = RB_ROOT;  // 声明并初始化根节点

节点定义

1
2
3
4

struct my_node {
    int key;
    struct rb_node rb;  // 嵌入红黑树节点
};

查找实现（页缓存示例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct page *rb_search_page_cache(struct inode *inode, unsigned long offset)
{
    struct rb_node *n = inode->i_rb_page_cache.rb_node;
    while (n) {
        struct page *page = rb_entry(n, struct page, rb_page_cache);
        if (offset < page->offset)
            n = n->rb_left;
        else if (offset > page->offset)
            n = n->rb_right;
        else
            return page;  // 命中
    }
    return NULL;  // 未命中
}

插入实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct page *rb_insert_page_cache(struct inode *inode, unsigned long offset, 
                                  struct rb_node *node)
{
    struct rb_node **p = &inode->i_rb_page_cache.rb_node;
    struct rb_node *parent = NULL;
    // 查找插入位置
    while (*p) {
        parent = *p;
        struct page *page = rb_entry(parent, struct page, rb_page_cache);
        
        if (offset < page->offset)
            p = &(*p)->rb_left;
        else if (offset > page->offset)
            p = &(*p)->rb_right;
        else
            return page;  // 已存在
    }
    // 执行插入
    rb_link_node(node, parent, p);      // 链接新节点
    rb_insert_color(node, &inode->i_rb_page_cache);  // 重平衡
    return NULL;  // 插入成功
}

XArray对比说明

适用场景差异

性能对比

1
2
3
4
5

操作        红黑树        XArray
---------------------------------
插入        O(log n)      O(k)  // k=键长
范围查询     O(log n + m)  O(m)  // m=结果数
内存开销     40字节/节点   8字节/条目

XArray替代红黑树的条件

1. 键为整数类型（非复杂比较键）
2. 无需有序遍历
3. 超高并发需求（XArray内置RCU）

   1 2 3

   // XArray实现类似功能 void *xa_store(struct xarray *xa, unsigned long index, void *entry); void *xa_load(struct xarray *xa, unsigned long index);

关键结论

1. 红黑树适用场景：
   • VFS目录树（dentry缓存）
   • 进程调度器（CFS运行队列）
   • EPoll事件管理
2. XArray优先场景：
   • 文件页缓存（address_space）
   • 内存反向映射
   • UID到指针映射

迁移建议：新代码中整数键映射优先采用XArray；复杂键/范围查询仍需红黑树。
性能数据：XArray在ext4文件系统中减少40%缓存操作耗时（内核5.15测试）

121. 买卖股票的最佳时机

贪心方法：取最左最小值，取最右最大值

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1)return 0;
        int profit = 0;
        int i = 0;
        for(int j = 1; j<prices.size(); j++){
            if((prices[j] - prices[i])>profit)profit = prices[j] - prices[i];
            if(prices[j] < prices[i])i = j;
        }
        return profit;
    }
};

122.买卖股票的最佳时机II

尝试一下动态规划方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    void printdp(vector<vector<int>> dp){
        for(auto i: dp){
            for(auto j: i){
                cout<<j<<' ';
            }
            cout<<endl;
        }
    }
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1)return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
        // printdp(dp);
        dp[0][1] -= prices[0];
        for(int i = 1; i < prices.size(); i++){
            dp[i][0] = max(dp[i-1][1]+prices[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]);
        }
        // printdp(dp);
        return dp[prices.size()-1][0];
    }
};

123.买卖股票的最佳时机III

为什么“选择两个最大的上升区间”这种解决方式不正确： 由于交易次数限制，并不是所有上升区间都需要被单独考虑。有时一笔交易可能覆盖多个上升区间

本题建议使用动态规划，推导四个状态： - 第一次持有股票 - 第一次不持有股票 - 第二次持有股票 - 第二次不持有股票

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1)return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][1] -= prices[0];
        dp[0][3] -= prices[0];
        for(int i = 1; i<prices.size(); i++){
            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);
            dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = max(dp[i-1][2]-prices[i], dp[i-1][3]);
            dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        return dp[prices.size()-1][4];
    }
};

映射（Maps）

基本概念

映射（又称关联数组）是由唯一键组成的集合，每个键关联一个特定值。键与值的关系称为映射关系，支持以下基本操作：
- 添加（Add）：插入键值对
- 移除（Remove）：删除指定键
- 查找（Lookup）：通过键获取值

尽管哈希表是一种映射实现，但并非所有映射都基于哈希。映射也可使用自平衡二叉搜索树存储数据：
- 哈希表：平均时间复杂度更优（O(1)），但最坏情况为线性（O(n)）
- 二叉搜索树：最坏情况为对数复杂度（O(log n)），且支持有序遍历，无需哈希函数（仅需定义比较操作符）

在Linux内核中，映射的特定实现称为idr（ID Radix Tree-旧版实现，现为XArray），专用于将唯一ID（UID）映射到指针。

初始化idr

1
2
3
4

#include <linux/idr.h>

struct idr id_huh;       // 静态定义  
idr_init(&id_huh);      // 初始化  

分配UID

1. 预分配资源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int idr_pre_get(struct idr *idp, gfp_t gfp_mask);  
```  
- **功能**：必要时调整底层树结构，准备分配新UID  
- **参数**：  
  - `idp`：目标idr结构  
  - `gfp_mask`：内存分配标志（如`GFP_KERNEL`）  
- **返回值**：成功返回1，失败返回0（与其他内核函数相反！）  

##### 2. 分配UID并关联指针  
```c
int idr_get_new(struct idr *idp, void *ptr, int *id);  
```  
- **功能**：分配新UID，将其与`ptr`关联  
- **返回值**：  
  - 成功：返回0，UID存储在`id`中  
  - 失败：返回`-EAGAIN`（需重试`idr_pre_get`）或`-ENOSPC`（idr已满）  

##### 示例：分配UID  
```c
int id, ret;
do {
    if (!idr_pre_get(&id_huh, GFP_KERNEL)) 
        return -ENOSPC;
    ret = idr_get_new(&id_huh, ptr, &id); 
} while (ret == -EAGAIN);

分配指定最小UID

1
2
3
4
5
6
7

int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);  
```  
- **功能**：分配不小于`starting_id`的UID，确保UID单调递增  
```c
static int next_id = 1;  // 全局计数器
if (!idr_get_new_above(&id_huh, ptr, next_id, &id))
    next_id = id + 1;    // 更新下一个起始ID  

XArray方式 (Linux 4.2以后)

1
2
3
4
5
6
7

/* 原子分配 (无需预分配) */
int xa_alloc(struct xarray *xa, unsigned int *id, 
             void *entry, struct xa_limit limit, gfp_t gfp);
/* 分配递增ID示例 */
unsigned int next_id = 1;
xa_alloc(&xa_huh, &next_id, ptr, XA_LIMIT(next_id, UINT_MAX), GFP_KERNEL);
// 成功后 next_id 自动递增

查找与删除

查找UID

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void *idr_find(struct idr *idp, int id);  
```  
- **返回值**：成功返回关联指针，失败返回`NULL`  
- **注意**：在分配UID时，禁止将`NULL`作为有效idr值映射，否则无法区分查找失败与有效`NULL`  

##### 移除UID  
```c
void idr_remove(struct idr *idp, int id);  
```  
- **注意**：无错误返回值，需调用者确保UID存在  

##### XArray方式
```c
/* 查找 */
void *xa_load(struct xarray *xa, unsigned long index);
/* 删除并返回删除项 */
void *xa_erase(struct xarray *xa, unsigned long index);

销毁

1
2
3
4
5
6
7
8

void idr_destroy(struct idr *idp);                  // 释放未使用内存  
void idr_remove_all(struct idr *idp);               // 强制移除所有UID  
```  
**典型流程**：  
```c
idr_remove_all(&id_huh);  // 先清空所有映射  
idr_destroy(&id_huh);     // 再释放内存，确保所有idr内存被释放  
kfree(user_data_ptr);  // 释放实际业务数据

XArray方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/* 销毁并释放所有资源 */
void xa_destroy(struct xarray *xa);

/* 安全销毁流程示例 */
void module_exit(void)
{
    unsigned long id;
    void *entry;
    // 遍历释放关联资源
    xa_for_each(&xa_huh, id, entry) {
        xa_erase(&xa_huh, id);
        kfree(entry);
    }
    xa_destroy(&xa_huh); // 释放XArray管理内存
}

关键注意事项

1. 并发控制：
   • idr_pre_get无需加锁
     
   • idr_get_new等操作需自旋锁保护（参见第9/10章）

队列

任何操作系统内核中常见的编程模式是生产者与消费者。实现此模式的最简单方式通常是使用队列，即先进先出（FIFO）。

Linux内核的通用队列实现称为kfifo，代码位于kernel/kfifo.c，头文件为<linux/kfifo.h>。本节讨论2.6.33版本更新后的API（早期版本用法略有不同，编写代码前请确认头文件）。

kfifo

Linux的kfifo与其他队列抽象类似，提供两个核心操作：
- 入队（in）：将数据写入队列
- 出队（out）：从队列中读取数据

kfifo对象维护两个偏移量：
- in偏移量：下一次入队的起始位置
- out偏移量：下一次出队的起始位置

规则：
1. out偏移量始终≤in偏移量（否则会读取未入队的数据）。
2. 当out == in时，队列为空（无法出队）。
3. 当in到达队列末尾时，需重置队列才能继续入队。

创建队列

动态初始化（常用）

1
2
3
4
5
6
7
8
9
10

int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);
```  
- **功能**：分配大小为`size`字节的队列（`size`必须为2的幂次），内存分配标志为`gfp_mask`（参见第12章“内存管理”）。  
- **返回值**：成功返回`0`，失败返回错误码。  
- **示例**：  
  ```c
  struct kfifo fifo;
  int ret = kfifo_alloc(&fifo, PAGE_SIZE, GFP_KERNEL);
  if (ret)
      return ret; // 初始化失败

自定义缓冲区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size);
```  
- **功能**：使用用户提供的`buffer`初始化队列，`size`必须为2的幂次。  

##### 静态声明（较少用）  
```c
DECLARE_KFIFO(name, size);  // 声明队列
INIT_KFIFO(name);           // 初始化队列
```  
- **要求**：`size`必须为2的幂次。  

---

#### 数据入队  
```c
unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len);
```  
- **功能**：从`from`复制`len`字节到队列`fifo`。  
- **返回值**：实际入队的字节数（若空间不足，可能小于`len`）。  


#### 数据出队  
##### 标准出队  
```c
unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len);
```  
- **功能**：从队列`fifo`复制最多`len`字节到`to`缓冲区。  
- **返回值**：实际出队的字节数。  
- **注意**：出队后数据不再保留在队列中。  

##### 查看数据（不删除）  
```c
unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len, unsigned offset);
```  
- **功能**：与`kfifo_out`类似，但**不移动out偏移量**，数据仍可后续读取。  
- **参数**：`offset`指定队列中的起始位置（0表示队头）。  

---

#### 获取队列信息
1. **获取队列总容量**
```c
static inline unsigned int kfifo_size(struct kfifo *fifo);

• 返回队列底层缓冲区的总字节数

2. 获取已入队数据量

   1	static inline unsigned int kfifo_len(struct kfifo *fifo);

• 返回当前队列中已存储的字节数
• （注：内核命名存在不一致性，需特别注意）

3. 获取剩余空间

   1	static inline unsigned int kfifo_avail(struct kfifo *fifo);

• 返回可继续写入的剩余字节数

4. 队列状态检查

   1 2	static inline int kfifo_is_empty(struct kfifo *fifo); static inline int kfifo_is_full(struct kfifo *fifo);

• 返回非零值表示队列为空/满
• 返回零表示非空/非满

重置与销毁队列

1. 重置队列

   1	static inline void kfifo_reset(struct kfifo *fifo);

• 清空队列所有内容（不释放内存）

2. 销毁动态分配的队列

   1	void kfifo_free(struct kfifo *fifo);

• 释放通过kfifo_alloc()创建的队列
• 注意：使用kfifo_init()创建的队列需手动释放关联缓冲区

实际应用示例

创建8KB大小的kfifo队列：

1
2
3
4
5
6
7
8
9
10
11

#include <linux/kfifo.h>
struct kfifo my_fifo;  // 声明 kfifo 结构体
int ret;
// 分配 8KB 队列
ret = kfifo_alloc(&my_fifo, 8192, GFP_KERNEL);  // 8192 = 8 * 1024
if (ret) {
    pr_err("Failed to allocate kfifo: error %d\n", ret);
    return ret;
}
// 验证大小
pr_info("Created FIFO size: %u bytes\n", kfifo_size(&my_fifo));  // 输出 8192

入队操作：

1
2
3
4

/* 入队0-31的整数 */
unsigned int i;
for (i = 0; i < 32; i++)
    kfifo_in(fifo, &i, sizeof(i));

查看队首元素（不移除）：

1
2
3
4
5

unsigned int val;
int ret = kfifo_out_peek(fifo, &val, sizeof(val), 0);
if (ret != sizeof(val))
    return -EINVAL;
printk(KERN_INFO "%u\n", val); /* 输出: 0 */

完整出队操作：

1
2
3
4
5
6
7
8

while (kfifo_avail(fifo)) {
    unsigned int val;
    int ret = kfifo_out(fifo, &val, sizeof(val));
    if (ret != sizeof(val))
        return -EINVAL;
    printk(KERN_INFO "%u\n", val); 
}
/* 输出: 0 1 2 ... 31 (严格保持FIFO顺序) */

链表（Linked Lists）

单链表与双链表

• 单链表：每个节点只包含指向下一个节点的指针。

  1 2 3 4

  struct list_element { void *data; // 数据 struct list_element *next; // 指向下一个节点 };

• 双链表：每个节点包含指向前一个和后一个节点的指针。

  1 2 3 4 5

  struct list_element { void *data; // 数据 struct list_element *next; // 指向下一个节点 struct list_element *prev; // 指向前一个节点 };

循环链表（Circular Linked Lists）

• 普通链表的最后一个节点的 next 指针通常指向 NULL，表示结束。
• 循环链表的最后一个节点的 next 指针指向第一个节点，形成环状结构。循环链表可以是单向或双向的。
• Linux 内核的链表实现本质上是循环双链表，灵活性最高。

链表的遍历

• 链表的遍历是线性的：从头节点开始，依次通过 next 指针访问每个节点。
• 非循环链表的最后一个节点 next 为 NULL；循环链表的最后一个节点 next 指向头节点。
• 双链表可以支持从尾节点向前遍历。
• 链表适合需要频繁插入、删除和遍历全部元素的场景，不适合随机访问。

Linux 内核链表实现方式

1. 与传统链表的区别

• 传统链表通常是在数据结构里直接加 next 和 prev 指针，把结构本身变成链表节点。
• Linux 内核采用嵌入链表节点的方式：在自定义结构体里嵌入一个 struct list_head 成员，而不是直接用 next/prev 指针。

2. 内核链表节点结构

1
2
3
4

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

• 只包含指向前后节点的指针，不存储数据。

3. 如何使用

• 在你的结构体里嵌入 struct list_head 成员，例如：

  1 2 3 4 5 6

  struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct list_head list; // 链表节点 };

• 这样，fox.list.next 指向下一个 fox，fox.list.prev 指向上一个 fox。

4. 链表操作

• 内核提供了丰富的链表操作函数（如 list_add()），这些函数只操作 list_head，不关心具体数据类型。
• 通过 container_of 宏，可以从 list_head 指针反查到包含它的结构体：

  1 2 3 4

  #define container_of(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member))) #define list_entry(ptr, type, member) \ container_of(ptr, type, member)

• 用 list_entry() 可以从链表节点指针获取到完整的结构体数据。

5. 链表初始化

• 动态分配结构体后，用 INIT_LIST_HEAD(&obj->list) 在运行时初始化链表节点。

  1 2 3 4 5 6

  struct fox *red_fox; red_fox = kmalloc(sizeof(*red_fox), GFP_KERNEL); red_fox->tail_length = 40; red_fox->weight = 6; red_fox->is_fantastic = false; INIT_LIST_HEAD(&red_fox->list);

• 静态定义时可用 LIST_HEAD_INIT() 宏在编译时初始化。

  1 2 3 4 5

  struct fox red_fox = { .tail_length = 40, .weight = 6, .list = LIST_HEAD_INIT(red_fox.list), };

6. 链表头

• 通常会定义一个专门的 list_head 变量作为链表头，用于管理整个链表：

  1	static LIST_HEAD(fox_list);

• 这个链表头本质上也是一个 list_head 节点，但不存储实际数据，只作为入口。

Linux 内核链表的操作方法

1. 所有链表操作函数都只操作 struct list_head 指针，和具体数据类型无关。

   • 这些函数都定义在 <linux/list.h>，实现为内联函数，效率高。
   • 所有操作都是 O(1) 常数时间，无论链表长度如何，插入、删除等操作速度都一样。

2. 常用操作函数：

   • 添加节点（底层的循环链表特性，每一个节点都可以填入head）
     • list_add(new, head)：把新节点插入到 head 节点之后（将最后一个节点填入head，实现栈）。
     • list_add_tail(new, head)：把新节点插入到 head 节点之前（将第一个节点填入head，实现队列）。
   • 删除节点
     • list_del(entry)：把 entry 节点从链表中移除，但不释放内存。
     • list_del_init(entry)：移除节点并重新初始化它，方便后续复用。
   • 移动节点
     • list_move(list, head)：把节点 list 移到 head 节点之后。
     • list_move_tail(list, head)：把节点 list 移到 head 节点之前。
   • 拼接链表
     • list_splice(list, head)：把 list 指向的链表拼接到 head 节点之后。
     • list_splice_init(list, head)：拼接后把原链表重新初始化。
   • 判断链表是否为空
     • list_empty(head)：判断链表是否为空，返回非零表示空。

3. 内部函数优化

   • 如果你已经有了节点的 next 和 prev 指针，可以直接调用内部函数（如 __list_del(prev, next)），省去多余的指针解引用。
   • 这些内部函数一般以双下划线 __ 开头，只有在你已经拿到指针时才建议用。

Linux 内核链表的遍历

完整遍历包含n个节点的链表是O(n)时间复杂度操作。

基础遍历方法

最基础的遍历宏是list_for_each()，接收两个list_head参数： - 第一个参数：指向当前项的指针（需调用者提供的临时变量） - 第二个参数：要遍历的链表头节点

1
2
3
4

struct list_head *p;
list_for_each(p, fox_list) {
    /* p指向链表中的某个节点 */
}

但仅获取list_head指针通常无用，我们需要的是包含该链表节点的结构体（前文已讨论）指针。此时应使用list_entry()宏：

1
2
3
4
5

struct list_head *p;
struct fox *f;
list_for_each(p, &fox_list) {
    f = list_entry(p, struct fox, list); // 获取包含list_head的fox结构体
}

实用遍历方法

上述方法不够直观，因此内核主要使用list_for_each_entry()宏，该宏自动完成list_entry()转换：

1

list_for_each_entry(pos, head, member)

参数说明： - pos：包含list_head的结构体指针（相当于list_entry()返回值） - head：链表头节点指针（如fox_list） - member：list_head在结构体中的成员名（如list）

示例：

1
2
3
4

struct fox *f;
list_for_each_entry(f, &fox_list, list) {
    /* 每次迭代f指向下一个fox结构体 */
}

实际案例（来自内核文件系统通知系统inotify）：

1
2
3
4
5
6
7
8
9
10

static struct inotify_watch *inode_find_handle(struct inode *inode, 
                                              struct inotify_handle *ih)
{
    struct inotify_watch *watch;
    list_for_each_entry(watch, &inode->inotify_watches, i_list) {
        if (watch->ih == ih)
            return watch;
    }
    return NULL;
}

反向遍历

list_for_each_entry_reverse()功能与正向遍历相同，但沿prev指针逆向移动：

1

list_for_each_entry_reverse(pos, head, member)

安全删除遍历

标准遍历方法在迭代过程中删除节点会导致问题（后续迭代无法获取正确的next/prev指针）。内核提供安全版本：

1

list_for_each_entry_safe(pos, next, head, member)

inotify示例：

1
2
3
4
5
6
7
8
9
10
11
12

void inotify_inode_is_dead(struct inode *inode)
{
    struct inotify_watch *watch, *next;
    mutex_lock(&inode->inotify_mutex);
    list_for_each_entry_safe(watch, next, &inode->inotify_watches, i_list) {
        struct inotify_handle *ih = watch->ih;
        mutex_lock(&ih->mutex);
        inotify_remove_watch_locked(ih, watch); // 删除watch节点
        mutex_unlock(&ih->mutex);
    }
    mutex_unlock(&inode->inotify_mutex);
}

逆向安全遍历版本：

1

list_for_each_entry_safe_reverse(pos, n, head, member)

注意事项

1. "safe"宏仅防护循环体内的删除操作，若存在并发操作仍需加锁
2. 更多链表操作方法详见<linux/list.h>

198.打家劫舍

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size()+1, 0);
        dp[1] = nums[0];
        for(int i = 2; i <= nums.size(); i++){
            dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]);
        }
        return dp[nums.size()];
    }
};

213.打家劫舍II

三种情况的动态规划： - 不考虑头尾元素 - 考虑头元素，不考虑尾元素 - 考虑尾元素，不考虑头元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1)return nums[nums.size()-1];
        int res_front = rob_range(nums, 0, nums.size()-2);
        int res_back = rob_range(nums, 1, nums.size()-1);
        int res = max(res_front, res_back);
        if(nums.size() >= 3)res = max(res,rob_range(nums, 1, nums.size()-2));
        return res;
    }
    int rob_range(vector<int>& nums, int start, int end){
        vector<int> dp(nums.size()+1, 0);
        if(start == end)return nums[start];
        dp[start] = nums[start];
        dp[start+1] = max(nums[start], nums[start+1]);
        if((start+1) == end)return dp[start+1];
        for(int i = start+2; i<=end; i++){
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[end];
    }
};

337.打家劫舍III

直接使用递归，计算抢当前节点还是不抢当前节点时，对相同的子树进行了多次独立的递归调用。会超时，推荐记忆化： 利用递归，每层返回一个保存当前节点偷还是不偷的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// struct TreeNode{
//     int val;
//     TreeNode* left;
//     TreeNode* right;
//     TreeNode(int v) : val(v), left(nullptr), right(nullptr){}
// };
class Solution {
public:
    vector<int> rob_tree(TreeNode* root){
        if(root == nullptr)return vector<int>{0, 0};
        vector<int> left = rob_tree(root->left);
        vector<int> right = rob_tree(root->right);

        // ↓不抢当前节点时，既可以选择抢子节点，也可选择不抢，可能会有跳过两个节点抢更优的情况
        int next_h = max(left[0], left[1])+max(right[0], right[1]);
        int this_h = root->val+left[0]+right[0];
        
        return {next_h, this_h};
    }
    int rob(TreeNode* root) {
        vector<int> res = rob_tree(root);
        return max(res[0], res[1]);
    }
};