英语

简体中文

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()。当处理较大的 ID 时，IDR 的效率会降低，因此使用此函数会带来轻微的成本。

要对 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。

参数

name: IDR 的名称。

描述

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

DEFINE_IDR¶

DEFINE_IDR (name)

定义一个静态分配的 IDR。

参数

name: 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 大 1 的值。这允许调用者使用 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 大 1 的值。这允许调用者使用 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_alloc() 和 idr_remove() 并发调用 idr_for_each()。可能看不到新添加的条目，也可能看到已删除的条目，但是添加和删除条目不会导致跳过其他条目，也不会看到虚假的条目。

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。

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 的用法¶

函数和结构¶