[Linux]学习笔记系列 --[drivers][base]map

title: map
categories:

• linux
• drivers
• base
  tags:
• linux
• drivers
• base
  abbrlink: 93adaabb
  date: 2025-10-21 14:00:06

https://github.com/wdfk-prog/linux-study

drivers/base/map.c

kobj_map: 一个通用的设备号到内核对象的映射引擎

本代码片段是Linux内核中一个相对底层但非常关键的通用映射子系统——kobj_map。其核心功能是提供一个可扩展的、基于回调的哈希表，用于将一个设备号（dev_t）高效地映射到一个内核对象（kobject）。这个机制是cdev（字符设备）、bdev（块设备）等许多与设备号相关的子系统的基础引擎。它通过一种链式哈希表和回调函数的设计，实现了设备注册、注销和查找的核心逻辑。

实现原理分析

如代码开头的注释所言，这是一个历史悠久的设计，虽然性能可能不是最优，但其设计思想非常精巧。

1. 核心数据结构 (kobj_map):

   • probes[255]:这是一个哈希表。它的大小是固定的255个桶（bucket）。
   • 哈希函数:MAJOR(dev) % 255。它使用设备号的主设备号（Major number）对255取模，来决定一个设备应该被放入哪个桶中。
   • struct probe: 这是哈希表中的节点。它不是直接存储kobject，而是存储一个**“探测器”**。这个探测器包含了：
     • dev和range: 定义了这个探测器所覆盖的设备号范围。
     • get(kobj_probe_t *): 一个回调函数指针。当查找到这个探测器时，系统会调用这个函数来动态地获取最终的kobject。
     • lock: 另一个回调函数，用于在使用get回调之前锁定底层对象。
     • data: 一个私有数据指针，会传递给get和lock回调。
   • lock: 一个互斥锁，用于保护整个哈希表的并发访问。

2. 映射/注册 (kobj_map):

   • 职责: 将一个新的设备号范围及其对应的探测器（回调函数等）添加到哈希表中。
   • 实现:
     • 它首先为要覆盖的所有主设备号（最多255个）分配一组probe结构体。
     • 然后，它锁定互斥锁。
     • 对于每一个受影响的主设备号，它计算出哈希桶的索引（index % 255）。
     • 它将新的probe节点以头插法的方式插入到对应哈希桶的链表中。链表是根据range大小排序的，范围小的排在前面，这是一种优化，使得查找时能更快地找到最精确匹配的范围。

3. 查找 (kobj_lookup):

   • 职责: 这是kobj_map的核心服务。给定一个设备号dev，找到对应的kobject。
   • 实现:
     • 计算哈希桶索引MAJOR(dev) % 255，并遍历该桶的probe链表。
     • 对于链表中的每个probe节点，检查dev是否落在[p->dev, p->dev + p->range - 1]的范围内。
     • 最佳匹配: 它会寻找覆盖范围最小（p->range - 1最小）的那个probe节点，这被称为“最佳匹配”（best match）。
     • 找到最佳匹配后，它会：
       1. 增加probe所属模块的引用计数（try_module_get）。
       2. 调用probe节点中的lock回调函数（如cdev的exact_lock，它会增加cdev的引用计数）。
       3. 调用probe节点中的get回调函数（如cdev的exact_match），这个回调真正返回kobject指针。
       4. 递减模块引用计数。
   • goto retry: 这是一个处理竞态条件的机制。如果在解锁后、调用probe回调期间，底层对象发生了变化（例如，probe返回NULL），它会重新加锁并进行重试。

代码分析

/** @struct kobj_map * @brief 核心映射结构，本质上是一个哈希表。 */structkobj_map{/** @struct probe * @brief 哈希表中的节点，代表一个“探测器”。 */structprobe{structprobe*next;/*!< 指向链表中的下一个探测器 */dev_tdev;/*!< 此探测器覆盖的起始设备号 */unsignedlongrange;/*!< 覆盖的设备号数量 */structmodule*owner;/*!< 提供回调函数的内核模块 */kobj_probe_t*get;/*!< 获取kobject的回调函数 */int(*lock)(dev_t,void*);/*!< 锁定底层对象的回调函数 */void*data;/*!< 传递给回调的私有数据 */}*probes[255];/*!< 哈希桶数组 */structmutex*lock;/*!< 保护整个哈希表的互斥锁 */};/** * @brief 在一个域中映射一个设备号范围。 * @param domain 映射域（如cdev_map）。 * @param dev 起始设备号。 * @param range 范围大小。 * @param module 内核模块指针。 * @param probe 获取kobject的回调。 * @param lock 锁定对象的回调。 * @param data 私有数据。 * @return int 成功返回0，失败返回错误码。 */intkobj_map(structkobj_map*domain,dev_tdev,unsignedlongrange,structmodule*module,kobj_probe_t*probe,int(*lock)(dev_t,void*),void*data){/* ... 计算需要覆盖的主设备号数量 ... *//* ... 分配probe节点内存 ... */mutex_lock(domain->lock);/* 锁定哈希表 */for(i=0,p-=n;i<n;i++,p++,index++){/* 计算哈希桶索引 */structprobe**s=&domain->probes[index%255];/* 找到正确的插入位置（按range排序） */while(*s&&(*s)->range<range)s=&(*s)->next;/* 将新节点插入链表 */p->next=*s;*s=p;}mutex_unlock(domain->lock);return0;}/** * @brief 从一个域中取消一个映射。 * @param domain 映射域。 * @param dev 起始设备号。 * @param range 范围大小。 */voidkobj_unmap(structkobj_map*domain,dev_tdev,unsignedlongrange){/* ... 计算需要覆盖的主设备号数量 ... */mutex_lock(domain->lock);for(i=0;i<n;i++,index++){structprobe**s;/* 遍历哈希桶链表 */for(s=&domain->probes[index%255];*s;s=&(*s)->next){structprobe*p=*s;/* 找到完全匹配的节点 */if(p->dev==dev&&p->range==range){*s=p->next;/* 从链表中移除 */if(!found)found=p;break;}}}mutex_unlock(domain->lock);kfree(found);/* 释放之前分配的probe节点内存 */}/** * @brief 在一个域中查找一个设备号对应的kobject。 * @param domain 映射域。 * @param dev 要查找的设备号。 * @param index 指向输出变量的指针，用于存储dev在范围内的偏移量。 * @return struct kobject* 成功则返回找到的kobject，否则返回NULL。 */structkobject*kobj_lookup(structkobj_map*domain,dev_tdev,int*index){/* ... */retry:mutex_lock(domain->lock);/* 计算哈希桶索引并遍历链表 */for(p=domain->probes[MAJOR(dev)%255];p;p=p->next){/* ... *//* 检查dev是否在probe节点的范围内 */if(p->dev>dev||p->dev+p->range-1<dev)continue;/* 寻找范围最小的最佳匹配 */if(p->range-1>=best)break;/* ... *//* 增加模块引用计数 */if(!try_module_get(p->owner))continue;/* ... 保存回调和数据 ... *//* 调用lock回调 */if(p->lock&&p->lock(dev,data)<0){module_put(owner);continue;}mutex_unlock(domain->lock);/* 解锁以调用probe回调 *//* 调用get回调来获取kobject */kobj=probe(dev,index,data);module_put(owner);if(kobj)returnkobj;gotoretry;/* 如果失败，则重试 */}mutex_unlock(domain->lock);returnNULL;}/** * @brief 初始化一个新的kobj_map。 * @param base_probe 默认的“兜底”探测回调。 * @param lock 用于保护该map的互斥锁。 * @return struct kobj_map* 成功则返回新创建的map，否则返回NULL。 */structkobj_map*kobj_map_init(kobj_probe_t*base_probe,structmutex*lock){/* ... 分配内存 ... *//* * 创建一个“基础”probe节点，它覆盖所有设备号（range = ~0）， * 作为默认的、最低优先级的匹配项。 */base->dev=1;base->range=~0;base->get=base_probe;for(i=0;i<255;i++)p->probes[i]=base;p->lock=lock;returnp;}