文章目录Linux 内核底层机制设备树Device Tree的数据结构与内存组织一、核心结论二、属性层级单向链表struct property2.1 内核结构体定义2.2 内存组织示例2.3 为什么采用单向链表三、节点层级First Child / Next Sibling 多叉树struct device_node3.1 内核结构体定义3.2 为什么不是子节点数组3.3 内存组织示例3.4 节点遍历方式3.5 Overlay 与 RCU四、核心对比五、总结六、设备树的生命周期从 DTB 到驱动绑定6.1 阶段一获取基础启动信息 —— early_init_dt_scan()6.2 阶段二构建内存设备树 —— unflatten_device_tree()6.3 阶段三生成总线设备触发驱动匹配 —— of_platform_populate()6.4 核心流程总结图Linux 内核底层机制设备树Device Tree的数据结构与内存组织Linux 内核中的设备树Device Tree简称 DT用于描述硬件平台信息。内核启动时会将设备树二进制文件DTB解析为一系列struct device_node和struct property对象并组织成一棵完整的设备树供驱动程序查询和匹配。设备树在内存中的组织主要分为两个层级节点Device Node表示一个硬件设备或总线。属性Property表示节点内部的配置项例如compatible、reg、status等。由于两者承担的职责不同因此 Linux 内核采用了不同的数据结构进行组织。一、核心结论Linux 内核针对设备树的两个层级采用了不同的数据结构设备树属性Property采用单向链表组织。设备树节点Device Node采用First Child / Next Sibling左孩子-右兄弟表示法构建一棵多叉树。对于现代 Linux5.x/6.x内核节点遍历主要依赖树形结构和遍历接口Iterator而早期 Linux 内核4.x 及以前曾额外维护一条allnext全局单向链表用于快速遍历所有节点。二、属性层级单向链表struct property设备树中的属性Property表示节点的具体配置项例如compatibleregstatusinterruptsmax-brightness-levels每个节点都拥有自己的属性链表。2.1 内核结构体定义源码位置include/linux/of.hstructproperty{char*name;/* 属性名称 */intlength;/* 属性值长度字节 */void*value;/* 属性值 */structproperty*next;/* 下一个属性 */unsignedlong_flags;unsignedintunique_id;};其中真正用于组织属性链表的是structproperty*next;因此一个节点内部所有属性都是通过单向链表连接起来的。2.2 内存组织示例例如下面的设备树i2c1 { status okay; gp710158 { compatible gp7101-backlight; reg 0x58; max-brightness-levels 255; default-brightness-level 100; }; };解析后的属性组织如下properties │ ▼ ------------------------------ | compatible | | value gp7101-backlight | | next ----------------------┐ | ----------------------------│- ▼ ------------------------------ | reg | | value 0x58 | | next ----------------------┐ | ----------------------------│- ▼ ------------------------------ | max-brightness-levels | | value 255 | | next ----------------------┐ | ----------------------------│- ▼ ------------------------------ | default-brightness-level | | value 100 | | next NULL | ------------------------------整个节点内部形成一条单向链表。2.3 为什么采用单向链表设备树属性具有以下特点每个节点通常只有几个到十几个属性驱动程序主要根据属性名顺序查找对应属性属性数量较少不需要复杂的数据结构大多数情况下属性在设备树展开后保持稳定驱动主要以只读方式访问。因此Linux 采用最简单的单向链表即可满足需求实现简单且内存开销较低。例如of_property_read_u32(np,reg,value);其内部最终就是遍历属性链表根据name找到对应的 Property。需要说明的是对于支持 Device Tree Overlay 的系统属性也可能在运行时动态增加或删除因此内核保留了deadprops等机制管理失效属性并通过 RCU 保证并发访问的安全性。三、节点层级First Child / Next Sibling 多叉树struct device_node设备树中的节点Device Node表示一个硬件设备。例如i2c40000000 serial50000000 gp710158 gpio10000000每个节点对应一个structdevice_node对象。3.1 内核结构体定义源码位置include/linux/of.hstructdevice_node{constchar*name;phandle phandle;constchar*full_name;structfwnode_handlefwnode;structproperty*properties;structproperty*deadprops;structdevice_node*parent;structdevice_node*child;structdevice_node*sibling;#ifdefined(CONFIG_OF_KOBJ)structkobjectkobj;#endifunsignedlong_flags;void*data;};描述树结构的关键成员只有三个parent child sibling3.2 为什么不是子节点数组Linux 并没有为每个节点维护children[100]这样的子节点数组。原因是不同节点拥有的子设备数量完全不同。例如root ├── cpu ├── memory ├── gpio ├── uart ├── spi ├── i2c ├── usb └── ...有的节点只有一个子节点有的可能几十个。如果使用数组需要预留大量空间插入删除效率低内存浪费严重。因此 Linux 采用了经典的数据结构First Child / Next Sibling左孩子-右兄弟表示法每个节点只需要三个指针parent child sibling即可表示任意规模的多叉树。3.3 内存组织示例例如/ { i2c40000000 { gp710158 { }; sensor60 { }; }; uart50000000 { }; };解析后形成如下关系[ root ] │ │ child (大儿子) ▼ [ i2c ] ───────── sibling (二弟) ────────▶ [ uart ] ── sibling ──▶ NULL │ │ │ child (大儿子) │ child (无子节点 无子节点) ▼ ▼ [ gp7101 ] ─────── sibling (二弟) ────▶ [ sensor ] ── sibling ──▶ NULL │ │ │ child │ child ▼ ▼ NULL NULL对应关系root ├── i2c │ ├── gp7101 │ └── sensor │ └── uart整个树只依赖parent child sibling三个指针即可表示。3.4 节点遍历方式现代 Linux 内核5.x/6.x主要基于树形结构进行遍历例如遍历子节点查找父节点深度优先遍历DFS使用设备树遍历接口Iterator。例如for_each_child_of_node(parent,child)就是沿着child → sibling → sibling依次访问所有子节点。需要注意的是**早期 Linux 内核4.x 及以前**曾在struct device_node中维护一个allnext指针将所有节点串成一条全局单向链表方便快速遍历整个设备树。而在现代 Linux 内核中allnext成员已经移除节点遍历主要依赖树形结构和专门的遍历接口不再维护独立的全局节点链表。3.5 Overlay 与 RCU现代 Linux 支持 Device Tree Overlay可以在系统运行过程中动态增加或删除节点及属性。为了保证遍历期间的数据一致性设备树相关数据结构采用RCURead-Copy-Update机制进行保护读端通常无需加锁即可访问设备树写端修改节点或属性时会在 RCU 机制下更新指针待所有读者退出临界区后再释放旧数据。因此无论节点还是属性在支持 Overlay 的场景下都能够实现安全的并发访问。四、核心对比对比项PropertyDevice Node对应结构体struct propertystruct device_node数据结构单向链表First Child / Next Sibling左孩子-右兄弟表示的多叉树关键指针nextparent、child、sibling典型访问方式顺序遍历属性链表遍历父子关系、兄弟关系或使用 Iterator生命周期基本稳定可被 Overlay 修改基本稳定可被 Overlay 动态增删并发保护Overlay 修改时由 RCU 保护RCU设计目标保存节点配置项表达硬件拓扑关系五、总结Linux 内核根据设备树不同层级的特点采用了不同的数据结构**属性Property**采用单向链表组织。由于每个节点的属性数量较少驱动主要按照属性名顺序查找因此单向链表实现简单、内存占用低能够满足绝大多数访问需求。**节点Device Node**采用First Child / Next Sibling左孩子-右兄弟表示法构建多叉树仅依靠parent、child和sibling三个指针即可描述任意复杂的硬件拓扑关系。此外现代 Linux 内核支持 Device Tree Overlay允许设备树在运行时动态增删节点和属性。为了保证遍历期间的并发安全内核使用RCURead-Copy-Update对相关数据结构进行保护使读操作无需加锁同时保证写操作的安全性。理解设备树节点与属性在内存中的组织方式有助于深入理解 Linux 内核中设备树的解析过程、驱动匹配机制以及设备枚举流程也能够帮助开发者更准确地使用设备树相关 API 进行驱动开发。六、设备树的生命周期从 DTB 到驱动绑定前面我们了解了设备树在内存中的数据结构单向链表与多叉树那么内核是如何一步步将编译好的二进制文件DTB转化为这些数据结构并最终和驱动程序绑定起来的呢整个过程主要经历三个核心阶段早期扫描、解构设备树、以及平台设备转换。这三步对应了三个至关重要的内核函数6.1 阶段一获取基础启动信息 ——early_init_dt_scan()在内核启动极早期setup_arch()阶段内存管理子系统如 buddy system还未建立。此时内核无法大规模分配内存来构建树形结构只能对 DTB 进行原地扫描。执行动作内核直接读取物理内存中扁平的 DTB 数据。核心任务校验 DTB 的 Magic Number确认设备树合法。扫描/chosen节点获取内核启动参数bootargs和 initrd 地址。扫描根节点获取#address-cells和#size-cells。扫描/memory节点获取系统物理内存的基地址和大小从而初始化早期内存分配器memblock。状态总结此时设备树依然是扁平的二进制数据FDT并没有生成struct device_node。6.2 阶段二构建内存设备树 ——unflatten_device_tree()当 memblock 早期内存分配器就绪后内核终于有了分配内存的能力。此时内核会将扁平的 DTB “解压”成我们在第三节提到的First Child / Next Sibling 多叉树。执行动作解析 DTB动态分配内存实例化节点与属性。核心任务通常包含两轮遍历Pass 1 Pass 2第一轮快速遍历一遍 DTB计算出所有的device_node和property需要占用多少总内存空间并一次性分配。第二轮真正开始解析数据填充各个struct device_node和struct property的指针成员即前面提到的parent、child、sibling和next建立完整的树形和链表关系。状态总结执行完毕后全局指针of_root指向设备树的根节点此时逻辑设备树已经在内存中完全建立。6.3 阶段三生成总线设备触发驱动匹配 ——of_platform_populate()设备树只是提供硬件信息的“数据库”要让驱动程序跑起来内核需要将这些信息转化为 Linux 设备模型Device Model认识的struct platform_device对象。执行动作遍历of_root设备树将符合条件的节点转换为平台设备Platform Device并注册到内核的 platform 总线上。核心任务遍历根节点下的子节点以及带有simple-bus等兼容属性的节点。为这些节点分配并初始化struct platform_device。将设备树节点指针np绑定到platform_device.dev.of_node上。调用device_register()将设备挂载到 platform 总线上。状态总结一旦设备挂载到总线上就会触发总线的match机制。总线会对比设备的compatible属性与驱动程序的of_match_table。一旦匹配成功就会调用驱动程序的probe()函数完成最终的驱动绑定。6.4 核心流程总结图为了更直观地理解你可以用下面这张图来记忆整个生命周期------------------- | DTB 文件 | (Bootloader 传递到内存) ------------------ │ ▼ [ early_init_dt_scan() ] 提取 memory、chosen 参数初始化早期内存 │ ▼ [ unflatten_device_tree() ] 构建 struct device_node (左孩子-右兄弟) 构建 struct property (单向链表) │ ▼ [ of_platform_populate() ] 遍历树实例化 struct platform_device注册到总线 │ ▼ ------------------- | Platform Bus匹配 | (根据 compatible 属性) ------------------ │ ▼ [ 驱动 probe() 运行 ] 通过 dev-of_node 再次读取特定 Property初始化硬件面试连招提醒大厂面试官如果在考察这部分时通常会追问“是不是所有的设备树节点都会被转换成platform_device”你的回答应该是不是。比如 I2C 和 SPI 总线下的子设备节点是由对应的 I2C/SPI 总线控制器驱动在自身的probe()函数中解析并注册为i2c_client或spi_device的它们挂在对应的 I2C/SPI 总线上而不是直接挂在顶层的 Platform 总线上。
Linux 内核底层机制：设备树（Device Tree）的数据结构与内存组织
文章目录Linux 内核底层机制设备树Device Tree的数据结构与内存组织一、核心结论二、属性层级单向链表struct property2.1 内核结构体定义2.2 内存组织示例2.3 为什么采用单向链表三、节点层级First Child / Next Sibling 多叉树struct device_node3.1 内核结构体定义3.2 为什么不是子节点数组3.3 内存组织示例3.4 节点遍历方式3.5 Overlay 与 RCU四、核心对比五、总结六、设备树的生命周期从 DTB 到驱动绑定6.1 阶段一获取基础启动信息 —— early_init_dt_scan()6.2 阶段二构建内存设备树 —— unflatten_device_tree()6.3 阶段三生成总线设备触发驱动匹配 —— of_platform_populate()6.4 核心流程总结图Linux 内核底层机制设备树Device Tree的数据结构与内存组织Linux 内核中的设备树Device Tree简称 DT用于描述硬件平台信息。内核启动时会将设备树二进制文件DTB解析为一系列struct device_node和struct property对象并组织成一棵完整的设备树供驱动程序查询和匹配。设备树在内存中的组织主要分为两个层级节点Device Node表示一个硬件设备或总线。属性Property表示节点内部的配置项例如compatible、reg、status等。由于两者承担的职责不同因此 Linux 内核采用了不同的数据结构进行组织。一、核心结论Linux 内核针对设备树的两个层级采用了不同的数据结构设备树属性Property采用单向链表组织。设备树节点Device Node采用First Child / Next Sibling左孩子-右兄弟表示法构建一棵多叉树。对于现代 Linux5.x/6.x内核节点遍历主要依赖树形结构和遍历接口Iterator而早期 Linux 内核4.x 及以前曾额外维护一条allnext全局单向链表用于快速遍历所有节点。二、属性层级单向链表struct property设备树中的属性Property表示节点的具体配置项例如compatibleregstatusinterruptsmax-brightness-levels每个节点都拥有自己的属性链表。2.1 内核结构体定义源码位置include/linux/of.hstructproperty{char*name;/* 属性名称 */intlength;/* 属性值长度字节 */void*value;/* 属性值 */structproperty*next;/* 下一个属性 */unsignedlong_flags;unsignedintunique_id;};其中真正用于组织属性链表的是structproperty*next;因此一个节点内部所有属性都是通过单向链表连接起来的。2.2 内存组织示例例如下面的设备树i2c1 { status okay; gp710158 { compatible gp7101-backlight; reg 0x58; max-brightness-levels 255; default-brightness-level 100; }; };解析后的属性组织如下properties │ ▼ ------------------------------ | compatible | | value gp7101-backlight | | next ----------------------┐ | ----------------------------│- ▼ ------------------------------ | reg | | value 0x58 | | next ----------------------┐ | ----------------------------│- ▼ ------------------------------ | max-brightness-levels | | value 255 | | next ----------------------┐ | ----------------------------│- ▼ ------------------------------ | default-brightness-level | | value 100 | | next NULL | ------------------------------整个节点内部形成一条单向链表。2.3 为什么采用单向链表设备树属性具有以下特点每个节点通常只有几个到十几个属性驱动程序主要根据属性名顺序查找对应属性属性数量较少不需要复杂的数据结构大多数情况下属性在设备树展开后保持稳定驱动主要以只读方式访问。因此Linux 采用最简单的单向链表即可满足需求实现简单且内存开销较低。例如of_property_read_u32(np,reg,value);其内部最终就是遍历属性链表根据name找到对应的 Property。需要说明的是对于支持 Device Tree Overlay 的系统属性也可能在运行时动态增加或删除因此内核保留了deadprops等机制管理失效属性并通过 RCU 保证并发访问的安全性。三、节点层级First Child / Next Sibling 多叉树struct device_node设备树中的节点Device Node表示一个硬件设备。例如i2c40000000 serial50000000 gp710158 gpio10000000每个节点对应一个structdevice_node对象。3.1 内核结构体定义源码位置include/linux/of.hstructdevice_node{constchar*name;phandle phandle;constchar*full_name;structfwnode_handlefwnode;structproperty*properties;structproperty*deadprops;structdevice_node*parent;structdevice_node*child;structdevice_node*sibling;#ifdefined(CONFIG_OF_KOBJ)structkobjectkobj;#endifunsignedlong_flags;void*data;};描述树结构的关键成员只有三个parent child sibling3.2 为什么不是子节点数组Linux 并没有为每个节点维护children[100]这样的子节点数组。原因是不同节点拥有的子设备数量完全不同。例如root ├── cpu ├── memory ├── gpio ├── uart ├── spi ├── i2c ├── usb └── ...有的节点只有一个子节点有的可能几十个。如果使用数组需要预留大量空间插入删除效率低内存浪费严重。因此 Linux 采用了经典的数据结构First Child / Next Sibling左孩子-右兄弟表示法每个节点只需要三个指针parent child sibling即可表示任意规模的多叉树。3.3 内存组织示例例如/ { i2c40000000 { gp710158 { }; sensor60 { }; }; uart50000000 { }; };解析后形成如下关系[ root ] │ │ child (大儿子) ▼ [ i2c ] ───────── sibling (二弟) ────────▶ [ uart ] ── sibling ──▶ NULL │ │ │ child (大儿子) │ child (无子节点 无子节点) ▼ ▼ [ gp7101 ] ─────── sibling (二弟) ────▶ [ sensor ] ── sibling ──▶ NULL │ │ │ child │ child ▼ ▼ NULL NULL对应关系root ├── i2c │ ├── gp7101 │ └── sensor │ └── uart整个树只依赖parent child sibling三个指针即可表示。3.4 节点遍历方式现代 Linux 内核5.x/6.x主要基于树形结构进行遍历例如遍历子节点查找父节点深度优先遍历DFS使用设备树遍历接口Iterator。例如for_each_child_of_node(parent,child)就是沿着child → sibling → sibling依次访问所有子节点。需要注意的是**早期 Linux 内核4.x 及以前**曾在struct device_node中维护一个allnext指针将所有节点串成一条全局单向链表方便快速遍历整个设备树。而在现代 Linux 内核中allnext成员已经移除节点遍历主要依赖树形结构和专门的遍历接口不再维护独立的全局节点链表。3.5 Overlay 与 RCU现代 Linux 支持 Device Tree Overlay可以在系统运行过程中动态增加或删除节点及属性。为了保证遍历期间的数据一致性设备树相关数据结构采用RCURead-Copy-Update机制进行保护读端通常无需加锁即可访问设备树写端修改节点或属性时会在 RCU 机制下更新指针待所有读者退出临界区后再释放旧数据。因此无论节点还是属性在支持 Overlay 的场景下都能够实现安全的并发访问。四、核心对比对比项PropertyDevice Node对应结构体struct propertystruct device_node数据结构单向链表First Child / Next Sibling左孩子-右兄弟表示的多叉树关键指针nextparent、child、sibling典型访问方式顺序遍历属性链表遍历父子关系、兄弟关系或使用 Iterator生命周期基本稳定可被 Overlay 修改基本稳定可被 Overlay 动态增删并发保护Overlay 修改时由 RCU 保护RCU设计目标保存节点配置项表达硬件拓扑关系五、总结Linux 内核根据设备树不同层级的特点采用了不同的数据结构**属性Property**采用单向链表组织。由于每个节点的属性数量较少驱动主要按照属性名顺序查找因此单向链表实现简单、内存占用低能够满足绝大多数访问需求。**节点Device Node**采用First Child / Next Sibling左孩子-右兄弟表示法构建多叉树仅依靠parent、child和sibling三个指针即可描述任意复杂的硬件拓扑关系。此外现代 Linux 内核支持 Device Tree Overlay允许设备树在运行时动态增删节点和属性。为了保证遍历期间的并发安全内核使用RCURead-Copy-Update对相关数据结构进行保护使读操作无需加锁同时保证写操作的安全性。理解设备树节点与属性在内存中的组织方式有助于深入理解 Linux 内核中设备树的解析过程、驱动匹配机制以及设备枚举流程也能够帮助开发者更准确地使用设备树相关 API 进行驱动开发。六、设备树的生命周期从 DTB 到驱动绑定前面我们了解了设备树在内存中的数据结构单向链表与多叉树那么内核是如何一步步将编译好的二进制文件DTB转化为这些数据结构并最终和驱动程序绑定起来的呢整个过程主要经历三个核心阶段早期扫描、解构设备树、以及平台设备转换。这三步对应了三个至关重要的内核函数6.1 阶段一获取基础启动信息 ——early_init_dt_scan()在内核启动极早期setup_arch()阶段内存管理子系统如 buddy system还未建立。此时内核无法大规模分配内存来构建树形结构只能对 DTB 进行原地扫描。执行动作内核直接读取物理内存中扁平的 DTB 数据。核心任务校验 DTB 的 Magic Number确认设备树合法。扫描/chosen节点获取内核启动参数bootargs和 initrd 地址。扫描根节点获取#address-cells和#size-cells。扫描/memory节点获取系统物理内存的基地址和大小从而初始化早期内存分配器memblock。状态总结此时设备树依然是扁平的二进制数据FDT并没有生成struct device_node。6.2 阶段二构建内存设备树 ——unflatten_device_tree()当 memblock 早期内存分配器就绪后内核终于有了分配内存的能力。此时内核会将扁平的 DTB “解压”成我们在第三节提到的First Child / Next Sibling 多叉树。执行动作解析 DTB动态分配内存实例化节点与属性。核心任务通常包含两轮遍历Pass 1 Pass 2第一轮快速遍历一遍 DTB计算出所有的device_node和property需要占用多少总内存空间并一次性分配。第二轮真正开始解析数据填充各个struct device_node和struct property的指针成员即前面提到的parent、child、sibling和next建立完整的树形和链表关系。状态总结执行完毕后全局指针of_root指向设备树的根节点此时逻辑设备树已经在内存中完全建立。6.3 阶段三生成总线设备触发驱动匹配 ——of_platform_populate()设备树只是提供硬件信息的“数据库”要让驱动程序跑起来内核需要将这些信息转化为 Linux 设备模型Device Model认识的struct platform_device对象。执行动作遍历of_root设备树将符合条件的节点转换为平台设备Platform Device并注册到内核的 platform 总线上。核心任务遍历根节点下的子节点以及带有simple-bus等兼容属性的节点。为这些节点分配并初始化struct platform_device。将设备树节点指针np绑定到platform_device.dev.of_node上。调用device_register()将设备挂载到 platform 总线上。状态总结一旦设备挂载到总线上就会触发总线的match机制。总线会对比设备的compatible属性与驱动程序的of_match_table。一旦匹配成功就会调用驱动程序的probe()函数完成最终的驱动绑定。6.4 核心流程总结图为了更直观地理解你可以用下面这张图来记忆整个生命周期------------------- | DTB 文件 | (Bootloader 传递到内存) ------------------ │ ▼ [ early_init_dt_scan() ] 提取 memory、chosen 参数初始化早期内存 │ ▼ [ unflatten_device_tree() ] 构建 struct device_node (左孩子-右兄弟) 构建 struct property (单向链表) │ ▼ [ of_platform_populate() ] 遍历树实例化 struct platform_device注册到总线 │ ▼ ------------------- | Platform Bus匹配 | (根据 compatible 属性) ------------------ │ ▼ [ 驱动 probe() 运行 ] 通过 dev-of_node 再次读取特定 Property初始化硬件面试连招提醒大厂面试官如果在考察这部分时通常会追问“是不是所有的设备树节点都会被转换成platform_device”你的回答应该是不是。比如 I2C 和 SPI 总线下的子设备节点是由对应的 I2C/SPI 总线控制器驱动在自身的probe()函数中解析并注册为i2c_client或spi_device的它们挂在对应的 I2C/SPI 总线上而不是直接挂在顶层的 Platform 总线上。
