map

[toc]

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 核心映射结构，本质上是一个哈希表。
 */
struct kobj_map {
	/** @struct probe
	 *  @brief 哈希表中的节点，代表一个“探测器”。
	 */
	struct probe {
		struct probe *next; /*!< 指向链表中的下一个探测器 */
		dev_t dev; /*!< 此探测器覆盖的起始设备号 */
		unsigned long range; /*!< 覆盖的设备号数量 */
		struct module *owner; /*!< 提供回调函数的内核模块 */
		kobj_probe_t *get; /*!< 获取kobject的回调函数 */
		int (*lock)(dev_t, void *); /*!< 锁定底层对象的回调函数 */
		void *data; /*!< 传递给回调的私有数据 */
	} *probes[255]; /*!< 哈希桶数组 */
	struct mutex *lock; /*!< 保护整个哈希表的互斥锁 */
};

/**
 * @brief 在一个域中映射一个设备号范围。
 * @param domain 映射域（如cdev_map）。
 * @param dev 起始设备号。
 * @param range 范围大小。
 * @param module 内核模块指针。
 * @param probe 获取kobject的回调。
 * @param lock 锁定对象的回调。
 * @param data 私有数据。
 * @return int 成功返回0，失败返回错误码。
 */
int kobj_map(struct kobj_map *domain, dev_t dev, unsigned long range,
	     struct module *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++) {
		/* 计算哈希桶索引 */
		struct probe **s = &domain->probes[index % 255];
		/* 找到正确的插入位置（按range排序） */
		while (*s && (*s)->range < range)
			s = &(*s)->next;
		/* 将新节点插入链表 */
		p->next = *s;
		*s = p;
	}
	mutex_unlock(domain->lock);
	return 0;
}

/**
 * @brief 从一个域中取消一个映射。
 * @param domain 映射域。
 * @param dev 起始设备号。
 * @param range 范围大小。
 */
void kobj_unmap(struct kobj_map *domain, dev_t dev, unsigned long range)
{
	/* ... 计算需要覆盖的主设备号数量 ... */

	mutex_lock(domain->lock);
	for (i = 0; i < n; i++, index++) {
		struct probe **s;
		/* 遍历哈希桶链表 */
		for (s = &domain->probes[index % 255]; *s; s = &(*s)->next) {
			struct probe *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。
 */
struct kobject *kobj_lookup(struct kobj_map *domain, dev_t dev, 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)
			return kobj;
		goto retry; /* 如果失败，则重试 */
	}
	mutex_unlock(domain->lock);
	return NULL;
}

/**
 * @brief 初始化一个新的kobj_map。
 * @param base_probe 默认的“兜底”探测回调。
 * @param lock 用于保护该map的互斥锁。
 * @return struct kobj_map* 成功则返回新创建的map，否则返回NULL。
 */
struct kobj_map *kobj_map_init(kobj_probe_t *base_probe, struct mutex *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;
	return p;
}