英语

中文 (简体)

ID 分配¶

作者:: Matthew Wilcox

概述¶

一个常见的待解决问题是分配标识符 (ID)；通常是用于标识某个事物的较小数字。例如文件描述符、进程 ID、网络协议中的数据包标识符、SCSI 标签和设备实例号。IDR 和 IDA 为此问题提供了合理的解决方案，避免了每个人都发明自己的方案。IDR 提供了将 ID 映射到指针的能力，而 IDA 仅提供 ID 分配，因此内存效率更高。

IDR 接口已弃用；请改用 XArray。

IDR 用法¶

首先初始化一个 IDR，可以通过 DEFINE_IDR() 用于静态分配的 IDR，或者通过 idr_init() 用于动态分配的 IDR。

您可以调用 idr_alloc() 来分配一个未使用的 ID。通过调用 idr_find() 查找与该 ID 关联的指针，并通过调用 idr_remove() 释放该 ID。

如果您需要更改与某个 ID 关联的指针，可以调用 idr_replace()。这样做的常见原因之一是通过向分配函数传递 NULL 指针来保留一个 ID；然后使用保留的 ID 初始化对象，最后将初始化后的对象插入到 IDR 中。

一些用户需要分配大于 INT_MAX 的 ID。到目前为止，所有这些用户都满足于 UINT_MAX 的限制，他们使用 idr_alloc_u32()。如果您需要无法容纳在 u32 中的 ID，我们将与您合作解决您的需求。

如果您需要按顺序分配 ID，可以使用 idr_alloc_cyclic()。IDR 在处理较大 ID 时效率会降低，因此使用此函数会带来轻微的开销。

要对 IDR 使用的所有指针执行操作，可以使用基于回调的 idr_for_each() 或迭代器风格的 idr_for_each_entry()。您可能需要使用 idr_for_each_entry_continue() 来继续迭代。如果迭代器不符合您的需求，您也可以使用 idr_get_next()。

当您使用完一个 IDR 后，可以调用 idr_destroy() 来释放 IDR 使用的内存。这不会释放 IDR 指向的对象；如果您想这样做，请使用其中一个迭代器来完成。

您可以使用 idr_is_empty() 来查明当前是否分配了任何 ID。

如果在从 IDR 分配新 ID 时需要加锁，您可能需要传递一组限制性的 GFP 标志，这可能导致 IDR 无法分配内存。为了解决这个问题，您可以在加锁前调用 idr_preload()，然后在分配后调用 idr_preload_end()。

idr 同步（摘自 radix-tree.h）

idr_find() 能够使用 RCU 无锁调用。调用者必须确保在此函数调用是在 rcu_read_lock() 区域内进行的。其他读者（无锁或其他）和修改可能并发运行。

仍然要求调用者管理项目的同步和生命周期。因此，如果使用 RCU 无锁查找，通常这意味着项目有自己的锁，或者适合无锁访问；并且项目由 RCU 释放（或者仅在从 idr 树中删除后以及经过 synchronize_rcu() 宽限期后才释放）。

IDA 用法¶

IDA 是一种 ID 分配器，它不提供将 ID 与指针关联的能力。因此，它只需为每个 ID 存储一位，从而比 IDR 更节省空间。要使用 IDA，请使用 DEFINE_IDA() 定义它（或将 struct ida 嵌入到数据结构中，然后使用 ida_init() 初始化）。要分配新 ID，请调用 ida_alloc()、ida_alloc_min()、ida_alloc_max() 或 ida_alloc_range()。要释放 ID，请调用 ida_free()。

ida_destroy() 可用于处理 IDA，而无需释放其中的单个 ID。您可以使用 ida_is_empty() 来查明 IDA 当前是否分配了任何 ID。

IDA 处理其自身的锁。在您的代码中，安全地调用任何 IDA 函数都无需同步。

ID 目前限制在 [0-INT_MAX] 范围内。如果这是一个不便的限制，那么提高最大值应该相当简单。

函数和结构¶

IDR_INIT¶

IDR_INIT (name)

初始化一个 IDR。

参数

名称: IDR 的名称。

描述

一个新初始化的 IDR 不包含任何 ID。

DEFINE_IDR¶

DEFINE_IDR (name)

定义一个静态分配的 IDR。

参数

名称: IDR 的名称。

描述

使用此宏定义的 IDR 可直接使用，无需额外初始化。它不包含任何 ID。

unsigned int idr_get_cursor(const struct idr *idr)¶: 返回循环分配器的当前位置

参数

const struct idr *idr: idr 句柄

描述

返回值是 idr_alloc_cyclic() 下次将返回的值，如果该值是空闲的（否则搜索将从该位置开始）。

void idr_set_cursor(struct idr *idr, unsigned int val)¶: 设置循环分配器的当前位置

参数

struct idr *idr: idr 句柄
unsigned int val: 新位置

描述

下次调用 idr_alloc_cyclic() 将返回 val，如果它空闲（否则搜索将从该位置开始）。

void idr_init_base(struct idr *idr, int base)¶: 初始化一个 IDR。

参数

struct idr *idr: IDR 句柄。
int base: IDR 的基值。

描述

此 idr_init() 变体创建了一个 IDR，它将从 base 开始分配 ID。

void idr_init(struct idr *idr)¶: 初始化一个 IDR。

参数

struct idr *idr: IDR 句柄。

描述

初始化一个动态分配的 IDR。要初始化静态分配的 IDR，请使用 DEFINE_IDR()。

bool idr_is_empty(const struct idr *idr)¶: 是否分配了任何 ID？

参数

const struct idr *idr: IDR 句柄。

返回

如果已从该 IDR 分配了任何 ID，则为 true。

void idr_preload_end(void)¶: 结束由 idr_preload() 开始的预加载段

参数

void: 无参数

描述

每个 idr_preload() 都应该与此函数的调用相匹配。有关详细信息，请参阅 idr_preload()。

idr_for_each_entry¶

idr_for_each_entry (idr, entry, id)

迭代 IDR 中给定类型的元素。

参数

idr: IDR 句柄。
entry: 用作游标的类型 *
id: 条目 ID。

描述

entry 和 id 在循环之前无需初始化，正常终止后 entry 将保留 NULL 值。这对于表示“未找到”的值很方便。

idr_for_each_entry_ul¶

idr_for_each_entry_ul (idr, entry, tmp, id)

迭代 IDR 中给定类型的元素。

参数

idr: IDR 句柄。
entry: 用作游标的类型 *。
tmp: ID 的临时占位符。
id: 条目 ID。

描述

entry 和 id 在循环之前无需初始化，正常终止后 entry 将保留 NULL 值。这对于表示“未找到”的值很方便。

idr_for_each_entry_continue¶

idr_for_each_entry_continue (idr, entry, id)

继续迭代 IDR 中给定类型的元素

参数

idr: IDR 句柄。
entry: 用作游标的类型 *。
id: 条目 ID。

描述

继续迭代条目，从当前位置之后继续。

idr_for_each_entry_continue_ul¶

idr_for_each_entry_continue_ul (idr, entry, tmp, id)

继续迭代 IDR 中给定类型的元素

参数

idr: IDR 句柄。
entry: 用作游标的类型 *。
tmp: ID 的临时占位符。
id: 条目 ID。

描述

继续迭代条目，从当前位置之后继续。正常终止后，entry 将保留 NULL 值。这对于表示“未找到”的值很方便。

int ida_alloc(struct ida *ida, gfp_t gfp)¶: 分配一个未使用的 ID。

参数

struct ida *ida: IDA 句柄。
gfp_t gfp: 内存分配标志。

描述

分配一个介于 0 和 INT_MAX（含）之间的 ID。

上下文

任何上下文。在您的代码中，安全地调用此函数无需加锁。

返回

已分配的 ID，如果无法分配内存则为 -ENOMEM，如果没有空闲 ID 则为 -ENOSPC。

int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp)¶: 分配一个未使用的 ID。

参数

struct ida *ida: IDA 句柄。
unsigned int min: 要分配的最低 ID。
gfp_t gfp: 内存分配标志。

描述

分配一个介于 min 和 INT_MAX（含）之间的 ID。

上下文

任何上下文。在您的代码中，安全地调用此函数无需加锁。

返回

已分配的 ID，如果无法分配内存则为 -ENOMEM，如果没有空闲 ID 则为 -ENOSPC。

int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp)¶: 分配一个未使用的 ID。

参数

struct ida *ida: IDA 句柄。
unsigned int max: 要分配的最高 ID。
gfp_t gfp: 内存分配标志。

描述

分配一个介于 0 和 max（含）之间的 ID。

上下文

任何上下文。在您的代码中，安全地调用此函数无需加锁。

返回

已分配的 ID，如果无法分配内存则为 -ENOMEM，如果没有空闲 ID 则为 -ENOSPC。

int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, unsigned long max, gfp_t gfp)¶: 分配一个 ID。

参数

struct idr *idr: IDR 句柄。
void *ptr: 与新 ID 关联的指针。
u32 *nextid: 指向一个 ID 的指针。
unsigned long max: 要分配的最大 ID（含）。
gfp_t gfp: 内存分配标志。

描述

在由 nextid 和 max 指定的范围内分配一个未使用的 ID。请注意，max 是包含的，而 idr_alloc() 的 end 参数是排他的。新 ID 在指针插入 IDR 之前被分配给 nextid，因此如果 nextid 指向 ptr 所指向的对象，并发查找将不会找到未初始化的 ID。

调用者应提供自己的锁，以确保不可能对 IDR 进行两次并发修改。对 IDR 的只读访问可以在 RCU 读锁下进行，或者可以排除同时写入。

返回

如果分配了 ID 则为 0，如果内存分配失败则为 -ENOMEM，如果找不到空闲 ID 则为 -ENOSPC。如果发生错误，nextid 不变。

int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)¶: 分配一个 ID。

参数

struct idr *idr: IDR 句柄。
void *ptr: 与新 ID 关联的指针。
int start: 最小 ID（含）。
int end: 最大 ID（不含）。
gfp_t gfp: 内存分配标志。

描述

在由 start 和 end 指定的范围内分配一个未使用的 ID。如果 end <= 0，则将其视为比 INT_MAX 大一。这允许调用者使用 start + N 作为 end，只要 N 在整数范围内即可。

调用者应提供自己的锁，以确保不可能对 IDR 进行两次并发修改。对 IDR 的只读访问可以在 RCU 读锁下进行，或者可以排除同时写入。

返回

新分配的 ID；如果内存分配失败则为 -ENOMEM；如果找不到空闲 ID 则为 -ENOSPC。

int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)¶: 循环分配一个 ID。

参数

struct idr *idr: IDR 句柄。
void *ptr: 与新 ID 关联的指针。
int start: 最小 ID（含）。
int end: 最大 ID（不含）。
gfp_t gfp: 内存分配标志。

描述

在由 start 和 end 指定的范围内分配一个未使用的 ID。如果 end <= 0，则将其视为比 INT_MAX 大一。这允许调用者使用 start + N 作为 end，只要 N 在整数范围内即可。对未使用 ID 的搜索将从上次分配的 ID 开始，如果未在到达 end 之前找到空闲 ID，则将环绕到 start。

调用者应提供自己的锁，以确保不可能对 IDR 进行两次并发修改。对 IDR 的只读访问可以在 RCU 读锁下进行，或者可以排除同时写入。

返回

新分配的 ID；如果内存分配失败则为 -ENOMEM；如果找不到空闲 ID 则为 -ENOSPC。

void *idr_remove(struct idr *idr, unsigned long id)¶: 从 IDR 中移除一个 ID。

参数

struct idr *idr: IDR 句柄。
unsigned long id: 指针 ID。

描述

从 IDR 中移除此 ID。如果此 ID 之前不在 IDR 中，此函数返回 NULL。

由于此函数修改 IDR，调用者应提供自己的锁以确保不可能对同一 IDR 进行并发修改。

返回

以前与此 ID 关联的指针。

void *idr_find(const struct idr *idr, unsigned long id)¶: 返回给定 ID 的指针。

参数

const struct idr *idr: IDR 句柄。
unsigned long id: 指针 ID。

描述

查找与此 ID 关联的指针。NULL 指针可能表示 id 未分配，或者 NULL 指针与此 ID 关联。

在叶指针生命周期正确管理的情况下，此函数可以在 rcu_read_lock() 下调用。

返回

与此 ID 关联的指针。

int idr_for_each(const struct idr *idr, int (*fn)(int id, void *p, void *data), void *data)¶: 迭代所有存储的指针。

参数

const struct idr *idr: IDR 句柄。
int (*fn)(int id, void *p, void *data): 为每个指针调用的函数。
void *data: 传递给回调函数的数据。

描述

将为 idr 中的每个条目调用回调函数，并传递 ID、条目和 data。

如果 fn 返回非 0 的值，则迭代停止，并从此函数返回该值。

如果受 RCU 保护，idr_for_each() 可以与 idr_alloc() 和 idr_remove() 并发调用。新添加的条目可能不会被看到，已删除的条目可能会被看到，但添加和删除条目不会导致其他条目被跳过，也不会导致虚假条目被看到。

void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)¶: 查找下一个已填充的条目。

参数

struct idr *idr: IDR 句柄。
unsigned long *nextid: 指向一个 ID 的指针。

描述

返回树中 ID 大于或等于 nextid 所指向的值的下一个已填充条目。退出时，nextid 将更新为找到的值的 ID。要在循环中使用，用户必须递增 nextid 所指向的值。

void *idr_get_next(struct idr *idr, int *nextid)¶: 查找下一个已填充的条目。

参数

struct idr *idr: IDR 句柄。
int *nextid: 指向一个 ID 的指针。

描述

返回树中 ID 大于或等于 nextid 所指向的值的下一个已填充条目。退出时，nextid 将更新为找到的值的 ID。要在循环中使用，用户必须递增 nextid 所指向的值。

void *idr_replace(struct idr *idr, void *ptr, unsigned long id)¶: 替换给定 ID 的指针。

参数

struct idr *idr: IDR 句柄。
void *ptr: 与 ID 关联的新指针。
unsigned long id: 要更改的 ID。

描述

替换已注册 ID 的指针并返回旧值。此函数可以在 RCU 读锁下与 idr_alloc() 和 idr_remove() 并发调用（只要被移除的 ID 不是被替换的 ID！）。

返回

成功时的旧值。-ENOENT 表示未找到 id。-EINVAL 表示 ptr 无效。

int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp)¶: 分配一个未使用的 ID。

参数

struct ida *ida: IDA 句柄。
unsigned int min: 要分配的最低 ID。
unsigned int max: 要分配的最高 ID。
gfp_t gfp: 内存分配标志。

描述

分配一个介于 min 和 max（含）之间的 ID。即使 max 更大，分配的 ID 也不会超过 INT_MAX。

上下文

任何上下文。在您的代码中，安全地调用此函数无需加锁。

返回

已分配的 ID，如果无法分配内存则为 -ENOMEM，如果没有空闲 ID 则为 -ENOSPC。

int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max)¶: 获取最低使用的 ID。

参数

struct ida *ida: IDA 句柄。
unsigned int min: 要获取的最低 ID。
unsigned int max: 要获取的最高 ID。

描述

获取介于 min 和 max（含）之间的最低已使用 ID。即使 max 更大，返回的 ID 也不会超过 INT_MAX。

上下文

任何上下文。获取并释放 xa_lock。

返回

最低使用的 ID，如果未找到使用的 ID 则返回 errno。

void ida_free(struct ida *ida, unsigned int id)¶: 释放一个已分配的 ID。

参数

struct ida *ida: IDA 句柄。
unsigned int id: 先前分配的 ID。

上下文

任何上下文。在您的代码中，安全地调用此函数无需加锁。

void ida_destroy(struct ida *ida)¶: 释放所有 ID。

参数

struct ida *ida: IDA 句柄。

描述

调用此函数将释放所有 ID 并释放 IDA 使用的所有资源。此调用返回后，IDA 将为空，可以重复使用或释放。如果 IDA 已为空，则无需调用此函数。

上下文

任何上下文。在您的代码中，安全地调用此函数无需加锁。

Linux 内核

目录

本页

ID 分配¶

概述¶

IDR 用法¶

IDA 用法¶

函数和结构¶