一、背景
我在前面的例子中讲解了 内核常用的数据结构， 本机我们就拿 上节中 讲解到的 list、hlist、rbtree、xarray 来写一个 有意义的测试案例。
在汽车电子里，MCU（比如车身域控制器里的 STM32）通过 SPI 向车机 SOC 定期上传各种信号和事件。
这些信号类型包括：
传感器数据（温度、车速、油门位置等）
诊断消息（MCU 自检、故障码上报）
控制命令（开关灯、空调风速等）
异步事件（按钮按下、CAN 报文转发）
驱动需要缓存、分类、调度这些消息，以便车机上层应用（HMI 或中间件）读取。
1. 该如何设计我们的测试demo
驱动模拟：车内 MCU 通过 SPI 向车机发送消息（本 demo 不直接与真实 SPI 硬件交互，而是通过
/proc/spi_demo写入模拟消息）。写入格式（ASCII）：
SEQ:MSGID:DELAY_MS:PAYLOAD，示例：42:7:100:HELLOSEQ：消息序列号 —— 存储 payload 的索引（用于 xarray）。MSGID：消息类型 ID —— 在哈希表（hlist）中查找 handler。DELAY_MS：延迟毫秒 —— 若 >0 则用 rbtree 排序后延迟处理。PAYLOAD：消息的文本数据（不包含:）。
读取
/proc/spi_demo可以查看内部状态：已注册设备（list），handlers（hlist/hash），已排期事件（rbtree），已存储消息（xarray）。
list_head：MCU 数量不多，但需要遍历，双向链表 O(1) 插删最合适。
hlist/hash：消息类型很多（几十/上百种），但分发必须快，hash 平均 O(1) 查找是最佳选择。
xarray：MCU 上报数据可能有几万条 seq，稀疏且需要随机访问，xarray 比数组节省内存，比链表查找更快。
rbtree：事件调度必须严格时间有序，红黑树保证插入 O(log n)，且
rb_first()总能拿到最近到期任务，适合 timer 驱动。
2. 如何映射到四种数据结构
list_head：SPI 设备列表车上可能有多个 SPI MCU（例如 MCU-A 管理车身、MCU-B 管理空调），驱动维护一个链表存放当前挂接的 SPI 从设备。
一对多关系：总线 → 多个 SPI 设备。
hlist（哈希表）：消息处理器表每个消息类型（msg_id）绑定一个 handler。
例如
msg_id=1→ 温度数据解析函数，msg_id=2→ 车速解析函数。查找快，适合 MCU 发来的消息要立刻分发。
xarray：按序号存储原始消息每条 MCU 上报的消息都有一个 seq 序号。
存入
xarray后，可以快速随机访问（比如 HMI 想读取最近 1000 条中第 500 条）。稀疏友好（如果 MCU 序号不是连续的，也没问题）。
rbtree：延迟处理的事件队列某些 MCU 消息需要在未来某个时间点处理（例如“延迟 2 秒开灯”，“500ms 后触发蜂鸣器”）。
驱动把这些事件按到期时间插入红黑树，timer 定时扫描最近要到期的节点，保证事件按时间顺序触发。
3. 场景
MCU-A 通过 SPI 发来以下报文：
报文 1：
seq=101, msg_id=1, delay=0, payload=TEMP=25.5
→ 立即处理，handler=温度解析，结果更新到车机的传感器缓存。报文 2：
seq=102, msg_id=8, delay=500ms, payload=BUZZER_ON
→ 插入 rbtree，定时器 500ms 后执行蜂鸣器打开动作。报文 3：
seq=103, msg_id=7, delay=0, payload=DIAG:0xE101
→ handler 解析诊断信息，存入日志。
最终：
/proc/spi_demo能看到：已注册设备列表（list_head）
handler 哈希表（hlist）
已存消息（xarray）
等待执行的定时任务（rbtree）
二、demo
1. code
/*
* spi_ds_demo.c - demo kernel module combining list_head, hlist, rbtree, xarray
*
* Scenario: 車载 MCUs 通过 SPI 发送消息到车机的 SPI 驱动，驱动负责接收消息，
* 存储原始 payload（按 sequence 使用 xarray），根据消息 ID 查找 handler（使用 hlist/hash），
* 可为消息安排延迟处理（使用 rbtree 以 expires 排序），并维护已注册的 SPI 设备列表（list_head）。
*
* 交互接口：
* - /proc/spi_demo : 读出当前内部状态（devices, handlers, scheduled events, stored messages）
* - 写入 /proc/spi_demo：以 ASCII 写入模拟 MCU 消息，格式为：
* SEQ:MSGID:DELAY_MS:PAYLOAD
* 例如： 42:7:100:HELLO
* - SEQ: 序列号（整数，用于存储 payload 到 xarray）
* - MSGID: 消息 ID（用于哈希查找 handler）
* - DELAY_MS: 延迟毫秒（0 表示立即处理）
* - PAYLOAD: 不包含 ':' 的字符串负载（最大 200 字节）
*
* 数据结构展示映射：
* - list_head: 管理已注册的 spi 设备实例（one-to-many: bus -> devices）
* - hlist/hashtable: map msg_id -> handler （hash 桶）
* - rbtree: 按过期时间排序的延迟事件调度（支持按时间先后顺序处理）
* - xarray: 按序列号存储 payload，支持大稀疏序列空间
*
* 适用于学习/测试数据结构的驱动 demo（不与真实 SPI 硬件通信）。
*/
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/list.h>
#include <linux/hashtable.h>
#include <linux/rbtree.h>
#include <linux/xarray.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/uaccess.h>
#include <linux/jiffies.h>
#include <linux/timer.h>
#include <linux/spinlock.h>
#define PROC_NAME "spi_demo"
#define MAX_PAYLOAD 200
#define HANDLER_BITS 4 /* 16 buckets */
MODULE_LICENSE("GPL");
MODULE_AUTHOR("leo");
MODULE_DESCRIPTION("Demo SPI driver showing list_head, hlist, rbtree, xarray");
/* ---------- list_head: simulated SPI device instances ---------- */
struct spi_dev_entry {
int id; /* device id */
char name[32];
struct list_head list; /* list_head 用于把设备挂到全局 device_list */
};
static LIST_HEAD(device_list);
static spinlock_t device_lock;
/* helper to create/register a fake device */
static struct spi_dev_entry *spi_dev_create(int id, const char *name)
{
struct spi_dev_entry *e;
e = kzalloc(sizeof(*e), GFP_KERNEL);
if (!e)
return NULL;
e->id = id;
strlcpy(e->name, name, sizeof(e->name));
INIT_LIST_HEAD(&e->list);
spin_lock(&device_lock);
list_add_tail(&e->list, &device_list);
spin_unlock(&device_lock);
return e;
}
static void spi_dev_destroy_all(void)
{
struct spi_dev_entry *pos, *tmp;
spin_lock(&device_lock);
list_for_each_entry_safe(pos, tmp, &device_list, list) {
list_del(&pos->list);
kfree(pos);
}
spin_unlock(&device_lock);
}
/* ---------- hlist/hashtable: message id -> handler mapping ---------- */
struct msg_handler {
u32 msg_id;
char name[32];
struct hlist_node hnode;
};
static DEFINE_HASHTABLE(handler_ht, HANDLER_BITS);
static spinlock_t handler_lock;
static void handler_register(u32 id, const char *name)
{
struct msg_handler *h;
h = kzalloc(sizeof(*h), GFP_KERNEL);
if (!h)
return;
h->msg_id = id;
strlcpy(h->name, name, sizeof(h->name));
spin_lock(&handler_lock);
hash_add(handler_ht, &h->hnode, h->msg_id);
spin_unlock(&handler_lock);
}
static void handler_unregister_all(void)
{
int b;
struct msg_handler *h;
struct hlist_node *tmp;
spin_lock(&handler_lock);
hash_for_each_safe(handler_ht, b, tmp, h, hnode) {
hash_del(&h->hnode);
kfree(h);
}
spin_unlock(&handler_lock);
}
static struct msg_handler *handler_find(u32 id)
{
struct msg_handler *h;
spin_lock(&handler_lock);
hash_for_each_possible(handler_ht, h, hnode, id) {
if (h->msg_id == id) {
spin_unlock(&handler_lock);
return h;
}
}
spin_unlock(&handler_lock);
return NULL;
}
/* ---------- xarray: store raw payloads by sequence number ---------- */
static DEFINE_XARRAY(msg_xa); /* seq -> *struct stored_msg */
struct stored_msg {
u32 seq;
u32 msg_id;
size_t len;
char *data; /* allocated payload */
};
static void stored_msg_free(struct stored_msg *m)
{
if (!m) return;
kfree(m->data);
kfree(m);
}
/* ---------- rbtree: scheduled events sorted by expires (jiffies) ---------- */
struct ev_node {
unsigned long expires; /* jiffies */
u32 seq; /* sequence number associated */
struct rb_node node;
};
static struct rb_root ev_tree = RB_ROOT;
static spinlock_t ev_lock; /* protect ev_tree */
static struct timer_list ev_timer;
static unsigned long timer_interval_jiffies = HZ / 10; /* 100ms */
/* insert event into rbtree (sorted by expires then seq) */
static void ev_insert(struct ev_node *en)
{
struct rb_node **link = &ev_tree.rb_node, *parent = NULL;
struct ev_node *entry;
spin_lock(&ev_lock);
while (*link) {
parent = *link;
entry = rb_entry(parent, struct ev_node, node);
if (en->expires < entry->expires ||
(en->expires == entry->expires && en->seq < entry->seq))
link = &(*link)->rb_left;
else
link = &(*link)->rb_right;
}
rb_link_node(&en->node, parent, link);
rb_insert_color(&en->node, &ev_tree);
spin_unlock(&ev_lock);
}
static struct ev_node *ev_first_locked(void)
{
struct rb_node *n = rb_first(&ev_tree);
if (!n) return NULL;
return rb_entry(n, struct ev_node, node);
}
static void ev_remove_node_locked(struct ev_node *en)
{
rb_erase(&en->node, &ev_tree);
}
/* process expired events: pop all with expires <= jiffies */
static void process_expired_events(void)
{
struct rb_node *n;
struct ev_node *en;
unsigned long now = jiffies;
for (;;) {
spin_lock(&ev_lock);
n = rb_first(&ev_tree);
if (!n) {
spin_unlock(&ev_lock);
break;
}
en = rb_entry(n, struct ev_node, node);
if (time_after(en->expires, now)) {
spin_unlock(&ev_lock);
break;
}
/* remove then process */
rb_erase(&en->node, &ev_tree);
spin_unlock(&ev_lock);
/* handle event: in demo just print and free */
pr_info("[ev] processing seq=%u (expires at %lu, now=%lu)\n", en->seq, en->expires, now);
kfree(en);
}
}
static void ev_timer_fn(struct timer_list *t)
{
process_expired_events();
/* re-arm timer if tree still has nodes */
spin_lock(&ev_lock);
if (ev_tree.rb_node)
mod_timer(&ev_timer, jiffies + timer_interval_jiffies);
spin_unlock(&ev_lock);
}
/* schedule an event for seq after delay_ms */
static void schedule_event(u32 seq, unsigned int delay_ms)
{
struct ev_node *en;
en = kzalloc(sizeof(*en), GFP_KERNEL);
if (!en) return;
en->seq = seq;
en->expires = jiffies + msecs_to_jiffies(delay_ms);
ev_insert(en);
/* ensure timer running */
mod_timer(&ev_timer, jiffies + timer_interval_jiffies);
}
/* ---------- procfs interface: read status, write to inject messages ---------- */
static int spi_proc_show(struct seq_file *m, void *v)
{
struct spi_dev_entry *d;
int b;
struct msg_handler *h;
struct stored_msg *sm;
unsigned long idx = 0;
struct rb_node *n;
struct ev_node *en;
seq_puts(m, "=== spi_demo status ===\n");
seq_puts(m, "-- devices (list_head) --\n");
spin_lock(&device_lock);
list_for_each_entry(d, &device_list, list) {
seq_printf(m, "dev id=%d name=%s\n", d->id, d->name);
}
spin_unlock(&device_lock);
seq_puts(m, "-- handlers (hashtable/hlist) --\n");
spin_lock(&handler_lock);
hash_for_each(handler_ht, b, h, hnode)
seq_printf(m, "handler msg_id=%u name=%s\n", h->msg_id, h->name);
spin_unlock(&handler_lock);
seq_puts(m, "-- scheduled events (rbtree) --\n");
spin_lock(&ev_lock);
for (n = rb_first(&ev_tree); n; n = rb_next(n)) {
en = rb_entry(n, struct ev_node, node);
seq_printf(m, "seq=%u expires(in jiffies)=%lu now=%lu\n", en->seq, en->expires, jiffies);
}
spin_unlock(&ev_lock);
seq_puts(m, "-- stored messages (xarray) --\n");
xa_for_each(&msg_xa, idx, sm) {
seq_printf(m, "seq=%lu msg_id=%u len=%zu data=%s\n", idx, sm->msg_id, sm->len, sm->data ? sm->data : "<null>");
}
return 0;
}
static int spi_proc_open(struct inode *inode, struct file *file)
{
return single_open(file, spi_proc_show, NULL);
}
/* parse a line like: SEQ:MSGID:DELAY_MS:PAYLOAD */
static ssize_t spi_proc_write(struct file *file, const char __user *ubuf, size_t count, loff_t *ppos)
{
char buf[256];
char *bufp = buf;
unsigned int seq, msgid, delay;
char payload[MAX_PAYLOAD + 1];
char *p1, *p2, *p3;
int ret;
void *stored;
struct stored_msg *sm;
struct msg_handler *h;
if (count == 0 || count >= sizeof(buf))
return -EINVAL;
if (copy_from_user(buf, ubuf, count))
return -EFAULT;
buf[count] = '\0';
/* simple parse by tokens */
p1 = strsep(&bufp, ":");
p2 = strsep(&bufp, ":");
p3 = strsep(&bufp, ":");
if (!p1 || !p2 || !p3)
return -EINVAL;
/* the rest is payload (trim newline) */
strncpy(payload, buf ? buf : "", MAX_PAYLOAD);
payload[MAX_PAYLOAD] = '\0';
/* strip trailing newline */
ret = strlen(payload);
if (ret && payload[ret-1] == '\n') payload[ret-1] = '\0';
if (kstrtouint(p1, 10, &seq) || kstrtouint(p2, 10, &msgid) || kstrtouint(p3, 10, &delay))
return -EINVAL;
pr_info("[write] got seq=%u msgid=%u delay=%u payload=%s\n", seq, msgid, delay, payload);
/* store payload in xarray */
sm = kzalloc(sizeof(*sm), GFP_KERNEL);
if (!sm) return -ENOMEM;
sm->seq = seq;
sm->msg_id = msgid;
sm->len = strlen(payload) + 1;
sm->data = kzalloc(sm->len, GFP_KERNEL);
if (!sm->data) { kfree(sm); return -ENOMEM; }
strncpy(sm->data, payload, sm->len);
stored = xa_store(&msg_xa, seq, sm, GFP_KERNEL);
if (stored) {
/* existing entry replaced: free old */
stored_msg_free(stored);
}
/* find handler, if none just log; if delay then schedule */
h = handler_find(msgid);
if (!h) {
pr_info("[write] no handler for msgid=%u\n", msgid);
} else {
pr_info("[write] found handler %s for msgid=%u\n", h->name, msgid);
}
if (delay == 0) {
pr_info("[write] immediate process seq=%u\n", seq);
/* immediate processing: in demo just print */
pr_info("[process] seq=%u payload=%s handler=%s\n", seq, sm->data, h ? h->name : "<none>");
} else {
schedule_event(seq, delay);
}
return count;
}
static const struct proc_ops spi_proc_fops = {
.proc_open = spi_proc_open,
.proc_read = seq_read,
.proc_lseek = seq_lseek,
.proc_release = single_release,
.proc_write = spi_proc_write,
};
/* ---------- module init/exit ---------- */
static struct proc_dir_entry *proc_entry;
static int __init spi_demo_init(void)
{
pr_info("spi_ds_demo init\n");
spin_lock_init(&device_lock);
spin_lock_init(&handler_lock);
spin_lock_init(&ev_lock);
/* create some fake spi devices (list_head usage) */
spi_dev_create(1, "spi_mcu_a");
spi_dev_create(2, "spi_mcu_b");
/* register some handlers (hashtable/hlist usage) */
handler_register(1, "power_btn");
handler_register(2, "sensor_update");
handler_register(7, "diag_msg");
/* create proc entry for interaction */
proc_entry = proc_create(PROC_NAME, 0666, NULL, &spi_proc_fops);
if (!proc_entry) {
pr_err("failed to create /proc/%s\n", PROC_NAME);
handler_unregister_all();
spi_dev_destroy_all();
return -ENOMEM;
}
/* setup timer for rbtree event polling */
timer_setup(&ev_timer, ev_timer_fn, 0);
pr_info("spi_ds_demo ready. write to /proc/%s lines like SEQ:MSGID:DELAY_MS:PAYLOAD\n", PROC_NAME);
return 0;
}
static void __exit spi_demo_exit(void)
{
unsigned long idx = 0;
struct stored_msg *sm;
struct rb_node *n;
struct ev_node *en;
pr_info("spi_ds_demo exit\n");
/* remove proc entry */
if (proc_entry)
proc_remove(proc_entry);
/* cancel timer and free rbtree events */
del_timer_sync(&ev_timer);
spin_lock(&ev_lock);
for (n = rb_first(&ev_tree); n;) {
en = rb_entry(n, struct ev_node, node);
n = rb_next(n);
rb_erase(&en->node, &ev_tree);
kfree(en);
}
spin_unlock(&ev_lock);
/* free xarray stored messages */
xa_for_each(&msg_xa, idx, sm) {
xa_erase(&msg_xa, idx);
stored_msg_free(sm);
}
/* unregister handlers and fake devices */
handler_unregister_all();
spi_dev_destroy_all();
pr_info("spi_ds_demo cleaned up\n");
}
module_init(spi_demo_init);
module_exit(spi_demo_exit);
2.测试
# write immediate
echo -n "1:2:0:hello_from_mcu" > /proc/spi_demo
# write delayed by 500 ms
echo -n "2:7:500:diag_message" > /proc/spi_demo
cat /proc/spi_demo
3. 代码要点说明（更详细）
list_head (
device_list)：初始化：
LIST_HEAD(device_list)，并在 init 中调用spi_dev_create(1, "spi_mcu_a")等模拟注册。读取 proc 时遍历：
list_for_each_entry(...)打印设备信息。清理时使用
list_for_each_entry_safe并调用kfree。
hlist/hashtable (
handler_ht)：使用
DEFINE_HASHTABLE(handler_ht, HANDLER_BITS)创建哈希表。handler_register(id, name)添加 handler（hash_add），查找时用hash_for_each_possible。适合 msg_id -> handler 的映射，查找平均 O(1)。
xarray (
msg_xa)：存储
struct stored_msg *，通过xa_store(&msg_xa, seq, sm, GFP_KERNEL)存放。遍历使用
xa_for_each(&msg_xa, idx, sm)来在 proc 中列出。适合按 seq 随机访问与稀疏序号空间。
rbtree (
ev_tree)：用于存储延迟事件节点
struct ev_node { expires, seq, rb_node }，插入通过比较expires（若相同再比较 seq）。采用
rb_link_node/rb_insert_color插入，rb_first/rb_next顺序遍历。Timer 周期性调用
process_expired_events()，将已过期事件弹出并处理。适合需要按时间顺序调度与弹出的场景（例如延迟命令、timeout 管理）。
同步：
每个容器（device_list, handler_ht, ev_tree）都由各自的 spinlock 保护。
xarray 内部有自己的同步约束；写时用
xa_store（带锁），读时用xa_for_each（用于 safe 遍历）。
内存管理：
- 所有 kmalloc 的对象在模块卸载时清理（xarray 元素、rbtree 节点、handler、devices）。
4. 一对多关系的表达方式（在 demo 中体现）
bus (implicit) -> 多个 spi devices：用
list_head把多个spi_dev_entry挂在device_list上（父对象通过维护 list_head 表示它拥有多个孩子）。msg_id -> 多个消息：哈希桶
hashtable（每个桶是 hlist）里可能包含相同 msg_id 的多个 handler（在本 demo 中一对一，但数据结构支持一对多）。seq -> payloads：
xarray用索引 seq 映射到单个 payload；若需要每个 seq 对应多个子项，可以把 xarray 的 v