英语

简体中文

XArray¶

作者:: Matthew Wilcox

概述¶

XArray 是一种抽象数据类型，其行为类似于一个非常大的指针数组。它满足了哈希或传统可调整大小数组的许多相同需求。与哈希不同，它允许您以缓存高效的方式明智地访问下一个或上一个条目。与可调整大小的数组相比，无需复制数据或更改 MMU 映射来增加数组。它比双向链表更节省内存、更易于并行化和缓存友好。它利用 RCU 执行查找而无需锁定。

当使用的索引密集聚类时，XArray 实现是高效的；哈希对象并使用哈希作为索引将不会表现良好。XArray 针对小索引进行了优化，但在大索引下仍然具有良好的性能。如果您的索引可以大于 ULONG_MAX，那么 XArray 不适合您。XArray 最重要的用户是页面缓存。

普通指针可以直接存储在 XArray 中。它们必须是 4 字节对齐的，这对于从 kmalloc() 和 alloc_page() 返回的任何指针都是如此。对于任意用户空间指针或函数指针则不是如此。您可以存储指向静态分配对象的指针，只要这些对象的对齐方式至少为 4。

您还可以在 XArray 中存储 0 到 LONG_MAX 之间的整数。您必须首先使用 xa_mk_value() 将其转换为一个条目。当您从 XArray 中检索条目时，可以通过调用 xa_is_value() 来检查它是否为值条目，并通过调用 xa_to_value() 将其转换回整数。

一些用户希望标记他们存储在 XArray 中的指针。您可以调用 xa_tag_pointer() 来创建一个带有标记的条目，使用 xa_untag_pointer() 将标记的条目转换回未标记的指针，并使用 xa_pointer_tag() 检索条目的标记。标记的指针使用与区分值条目和普通指针相同的位，因此您必须决定是否要在任何特定的 XArray 中存储值条目或标记的指针。

XArray 不支持存储 IS_ERR() 指针，因为某些指针会与值条目或内部条目冲突。

XArray 的一个不寻常的特性是能够创建占用一系列索引的条目。一旦存储到，查找范围内的任何索引将返回与查找范围内的任何其他索引相同的条目。存储到任何索引将存储到所有索引。多索引条目可以显式拆分为较小的条目，或者将 NULL 存储到任何条目将导致 XArray 忘记该范围。

普通 API¶

首先初始化 XArray，对于静态分配的 XArray 使用 DEFINE_XARRAY()，对于动态分配的 XArray 使用 xa_init()。新初始化的 XArray 在每个索引处都包含一个 NULL 指针。

然后，您可以使用 xa_store() 设置条目，并使用 xa_load() 获取条目。xa_store 将使用新条目覆盖任何条目，并返回该索引处存储的上一个条目。您可以使用 xa_erase() 代替调用带有 NULL 条目的 xa_store()。从未存储过的条目、已被擦除的条目和最近存储了 NULL 的条目之间没有区别。

您可以使用 xa_cmpxchg() 有条件地替换索引处的条目。像 cmpxchg() 一样，只有当该索引处的条目具有“旧”值时才会成功。它还返回该索引处的条目；如果它返回与作为“旧”传递的条目相同的条目，则 xa_cmpxchg() 成功。

如果您只想在该索引处的当前条目为 NULL 时将新条目存储到索引，您可以使用 xa_insert()，如果该条目不为空，则返回 -EBUSY。

您可以通过调用 xa_extract() 将 XArray 中的条目复制到一个普通数组中。或者，您可以通过调用 xa_for_each()、xa_for_each_start() 或 xa_for_each_range() 来遍历 XArray 中的当前条目。您可能更喜欢使用 xa_find() 或 xa_find_after() 来移动到 XArray 中的下一个当前条目。

调用 xa_store_range() 将相同的条目存储在一系列索引中。如果您这样做，其他一些操作的行为会有点奇怪。例如，标记一个索引处的条目可能会导致该条目在某些但不是所有其他索引处被标记。存储到一个索引可能会导致某些但不是所有其他索引检索到的条目发生更改。

有时您需要确保后续对 xa_store() 的调用不需要分配内存。xa_reserve() 函数将在指示的索引处存储一个保留条目。普通 API 的用户会将此条目视为包含 NULL。如果您不需要使用保留条目，您可以调用 xa_release() 来删除未使用的条目。如果在此期间其他用户已存储到该条目，则 xa_release() 将不执行任何操作；如果您希望该条目变为 NULL，则应使用 xa_erase()。在保留条目上使用 xa_insert() 将失败。

如果数组中的所有条目均为 NULL，则 xa_empty() 函数将返回 true。

最后，您可以通过调用 xa_destroy() 从 XArray 中删除所有条目。如果 XArray 条目是指针，您可能希望首先释放这些条目。您可以使用 xa_for_each() 迭代器遍历 XArray 中所有存在的条目来完成此操作。

搜索标记¶

数组中的每个条目都有三个与之关联的位，称为标记。每个标记可以独立于其他标记进行设置或清除。您可以使用 xa_for_each_marked() 迭代器遍历标记的条目。

您可以使用 xa_get_mark() 查询是否在条目上设置了标记。如果条目不是 NULL，您可以使用 xa_set_mark() 在其上设置标记，并调用 xa_clear_mark() 从条目中删除标记。您可以通过调用 xa_marked() 来询问 XArray 中是否有任何条目设置了特定的标记。从 XArray 中删除条目会导致与该条目关联的所有标记被清除。

在多索引条目的任何索引上设置或清除标记将影响该条目覆盖的所有索引。查询任何索引上的标记将返回相同的结果。

没有办法遍历未标记的条目；数据结构不允许高效地实现这一点。目前没有迭代器来搜索位的逻辑组合（例如，遍历所有同时设置了 XA_MARK_1 和 XA_MARK_2 的条目，或者遍历所有设置了 XA_MARK_0 或 XA_MARK_2 的条目）。如果用户提出要求，可以添加这些功能。

分配 XArray¶

如果您使用 DEFINE_XARRAY_ALLOC() 来定义 XArray，或者通过将 XA_FLAGS_ALLOC 传递给 xa_init_flags() 来初始化它，则 XArray 会更改为跟踪条目是否正在使用。

您可以调用 xa_alloc() 将条目存储在 XArray 中未使用的索引处。如果您需要从中断上下文修改数组，可以使用 xa_alloc_bh() 或 xa_alloc_irq() 在分配 ID 时禁用中断。

使用 xa_store()、xa_cmpxchg() 或 xa_insert() 也会将条目标记为已分配。与普通 XArray 不同，存储 NULL 将条目标记为正在使用，类似于 xa_reserve()。要释放条目，请使用 xa_erase() （如果您只想在条目为 NULL 时释放它，则使用 xa_release()）。

默认情况下，最低的空闲条目从 0 开始分配。如果您希望从 1 开始分配条目，则使用 DEFINE_XARRAY_ALLOC1() 或 XA_FLAGS_ALLOC1 会更有效率。如果您想分配 ID 到最大值，然后绕回到最低的空闲 ID，则可以使用 xa_alloc_cyclic()。

您不能在分配 XArray 时使用 XA_MARK_0，因为此标记用于跟踪条目是否空闲。其他标记可供您使用。

内存分配¶

xa_store()、xa_cmpxchg()、xa_alloc()、xa_reserve() 和 xa_insert() 函数采用 gfp_t 参数，以防 XArray 需要分配内存来存储此条目。如果正在删除条目，则无需执行内存分配，并且将忽略指定的 GFP 标志。

可能无法分配任何内存，特别是如果您传递了一组限制性的 GFP 标志。在这种情况下，这些函数会返回一个特殊值，该值可以使用 xa_err() 转换为 errno。如果您不需要确切知道发生了哪个错误，则使用 xa_is_err() 会稍微高效一些。

锁定¶

使用 Normal API 时，您无需担心锁定。XArray 使用 RCU 和内部自旋锁来同步访问。

无需锁定

xa_empty()
xa_marked()

获取 RCU 读取锁

xa_load()
xa_for_each()
xa_for_each_start()
xa_for_each_range()
xa_find()
xa_find_after()
xa_extract()
xa_get_mark()

内部获取 xa_lock

假设入口时已持有 xa_lock

__xa_store()
__xa_insert()
__xa_erase()
__xa_cmpxchg()
__xa_alloc()
__xa_set_mark()
__xa_clear_mark()

如果您想利用锁来保护存储在 XArray 中的数据结构，您可以在调用 xa_load() 之前调用 xa_lock()，然后在调用 xa_unlock() 之前对找到的对象进行引用计数。这将防止在查找对象和增加引用计数之间将对象从数组中删除。您还可以使用 RCU 来避免取消引用已释放的内存，但对此的解释超出了本文档的范围。

XArray 在修改数组时不会禁用中断或软中断。从中断或软中断上下文中读取 XArray 是安全的，因为 RCU 锁提供了足够的保护。

例如，如果您想在进程上下文中将条目存储在 XArray 中，然后在软中断上下文中删除它们，则可以这样做：

void foo_init(struct foo *foo)
{
    xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
}

int foo_store(struct foo *foo, unsigned long index, void *entry)
{
    int err;

    xa_lock_bh(&foo->array);
    err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
    if (!err)
        foo->count++;
    xa_unlock_bh(&foo->array);
    return err;
}

/* foo_erase() is only called from softirq context */
void foo_erase(struct foo *foo, unsigned long index)
{
    xa_lock(&foo->array);
    __xa_erase(&foo->array, index);
    foo->count--;
    xa_unlock(&foo->array);
}

如果要从中断或软中断上下文中修改 XArray，则需要使用 xa_init_flags() 初始化数组，传递 XA_FLAGS_LOCK_IRQ 或 XA_FLAGS_LOCK_BH。

上面的示例还显示了一个常见模式，即希望扩展存储端的 xa_lock 的覆盖范围，以保护与数组关联的一些统计信息。

也可以在中断上下文中使用 XArray，可以使用中断处理程序和进程上下文中的 xa_lock_irqsave()，或者在进程上下文中使用 xa_lock_irq()，在中断处理程序中使用 xa_lock()。一些更常见的模式有辅助函数，例如 xa_store_bh()、 xa_store_irq()、 xa_erase_bh()、 xa_erase_irq()、 xa_cmpxchg_bh() 和 xa_cmpxchg_irq()。

有时您需要使用互斥锁来保护对 XArray 的访问，因为该锁位于锁定层次结构中的另一个互斥锁之上。这并不意味着您可以使用像 __xa_erase() 这样的函数而无需获取 xa_lock；xa_lock 用于 lockdep 验证，将来还将用于其他目的。

__xa_set_mark() 和 __xa_clear_mark() 函数也可用于查找条目并想原子地设置或清除标记的情况。在这种情况下，使用高级 API 可能更有效，因为它会使您免于遍历树两次。

高级 API¶

高级 API 以牺牲接口的易用性及安全保障为代价，提供了更大的灵活性和更好的性能。高级 API 不会为您进行任何锁定，并且您需要在修改数组时使用 xa_lock。您可以选择在对数组执行只读操作时使用 xa_lock 或 RCU 锁。您可以在同一个数组上混合使用高级和普通操作；实际上，普通 API 是根据高级 API 实现的。高级 API 仅适用于具有 GPL 兼容许可证的模块。

高级 API 基于 xa_state。这是一个不透明的数据结构，您可以使用 XA_STATE() 宏在堆栈上声明它。此宏初始化 xa_state，使其准备好开始在 XArray 中移动。它用作游标，以保持在 XArray 中的位置，并允许您将各种操作组合在一起，而无需每次都从顶部重新开始。xa_state 的内容受 rcu_read_lock() 或 xas_lock() 的保护。如果您需要放弃保护您的状态和树的那些锁中的任何一个，则必须调用 xas_pause()，以便将来的调用不会依赖于未受保护的状态部分。

xa_state 还用于存储错误。您可以调用 xas_error() 来检索错误。所有操作都会在继续之前检查 xa_state 是否处于错误状态，因此您无需在每次调用后都检查错误；您可以连续进行多次调用，并且仅在方便的时候检查。目前 XArray 代码本身生成的唯一错误是 ENOMEM 和 EINVAL，但是它支持任意错误，以防您想自己调用 xas_set_err()。

如果 xa_state 持有 ENOMEM 错误，则调用 xas_nomem() 将尝试使用指定的 gfp 标志分配更多内存，并将其缓存在 xa_state 中以供下次尝试。其想法是，您获取 xa_lock，尝试操作并放弃该锁。该操作会在持有锁时尝试分配内存，但更有可能失败。放弃锁后，xas_nomem() 可以尝试更努力地分配更多内存。如果值得重试操作（即存在内存错误且分配了更多内存），它将返回 true。如果它以前分配了内存，并且该内存未使用，并且没有错误（或者某些错误不是 ENOMEM），则它将释放先前分配的内存。

内部条目¶

XArray 保留一些条目供自己使用。这些条目永远不会通过普通 API 公开，但是当使用高级 API 时，可能会看到它们。通常，处理它们的最佳方法是将它们传递给 xas_retry()，如果它返回 true，则重试该操作。

名称	测试	用法
节点	xa_is_node()	一个 XArray 节点。使用多索引 xa_state 时可能可见。
同级	`xa_is_sibling()`	多索引条目的非规范条目。该值指示此节点中哪个槽具有规范条目。
重试	`xa_is_retry()`	该条目当前正由具有 xa_lock 的线程修改。包含此条目的节点可能在此 RCU 周期结束时被释放。您应该从数组的头部重新启动查找。
零	`xa_is_zero()`	零条目通过普通 API 显示为 `NULL`，但在 XArray 中占据一个条目，该条目可用于保留索引以供将来使用。这通过为分配的 `NULL` 条目分配 XArray 来使用。

将来可能会添加其他内部条目。在尽可能的情况下，它们将由 xas_retry() 处理。

其他功能¶

xas_create_range() 函数会分配所有必要的内存以存储范围内的每个条目。如果无法分配内存，它将在 xa_state 中设置 ENOMEM。

您可以使用 xas_init_marks() 将条目上的标记重置为默认状态。通常，所有标记都清除，除非 XArray 标记为 XA_FLAGS_TRACK_FREE，在这种情况下，标记 0 会被设置，而所有其他标记都会被清除。使用 xas_store() 将一个条目替换为另一个条目不会重置该条目上的标记；如果您希望重置标记，则应该显式执行此操作。

xas_load() 会尽可能地将 xa_state 遍历到条目。如果您知道 xa_state 已经遍历到该条目，并且需要检查该条目是否已更改，则可以使用 xas_reload() 来节省一个函数调用。

如果您需要在 XArray 中移动到不同的索引，请调用 xas_set()。这将游标重置到树的顶部，这通常会使下一个操作将游标遍历到树中的所需位置。如果您想移动到下一个或上一个索引，请调用 xas_next() 或 xas_prev()。设置索引不会使游标在数组中移动，因此不需要持有锁，而移动到下一个或上一个索引则需要。

您可以使用 xas_find() 搜索下一个存在的条目。这相当于 xa_find() 和 xa_find_after()；如果游标已移动到某个条目，则它将找到当前引用的条目之后的下一个条目。否则，它将返回 xa_state 索引处的条目。使用 xas_next_entry() 移动到下一个存在的条目，而不是使用 xas_find()，在大多数情况下可以节省一个函数调用，但代价是会发出更多的内联代码。

xas_find_marked() 函数类似。如果 xa_state 没有被遍历过，它将返回 xa_state 索引处的条目（如果已标记）。否则，它将返回 xa_state 引用的条目之后的第一个已标记的条目。xas_next_marked() 函数等同于 xas_next_entry()。

当使用 xas_for_each() 或 xas_for_each_marked() 迭代 XArray 的范围时，可能需要暂时停止迭代。 xas_pause() 函数就是为此目的而存在的。在您完成必要的工作并希望恢复时，xa_state 处于适当的状态，可以在您上次处理的条目之后继续迭代。如果在迭代时禁用了中断，那么最好暂停迭代并在每 XA_CHECK_SCHED 个条目时重新启用中断。

xas_get_mark()、xas_set_mark() 和 xas_clear_mark() 函数要求 xa_state 游标已移动到 XArray 中的相应位置；如果在调用它们之前立即调用了 xas_pause() 或 xas_set()，则它们将不执行任何操作。

您可以调用 xas_set_update()，以便在 XArray 每次更新节点时调用回调函数。页面缓存工作集代码使用此功能来维护其仅包含影子条目的节点列表。

多索引条目¶

XArray 能够将多个索引绑定在一起，从而使对一个索引的操作影响所有索引。例如，存储到任何索引都将更改从任何索引检索到的条目的值。设置或清除任何索引上的标记都将设置或清除绑定在一起的每个索引上的标记。当前实现仅允许绑定对齐的 2 的幂范围；例如，索引 64-127 可以绑定在一起，但 2-6 不能。这可以节省大量的内存；例如，将 512 个条目绑定在一起将节省超过 4kB 的内存。

您可以使用 XA_STATE_ORDER() 或 xas_set_order() 后跟对 xas_store() 的调用来创建多索引条目。使用多索引 xa_state 调用 xas_load() 将把 xa_state 移动到树中的正确位置，但返回值没有意义，可能是内部条目或 NULL，即使该范围内存储了条目。调用 xas_find_conflict() 将返回范围内的第一个条目，如果范围内没有条目，则返回 NULL。 xas_for_each_conflict() 迭代器将迭代与指定范围重叠的每个条目。

如果 xas_load() 遇到多索引条目，则 xa_state 中的 xa_index 不会更改。当迭代 XArray 或调用 xas_find() 时，如果初始索引位于多索引条目的中间，则它不会更改。后续调用或迭代会将索引移动到范围内的第一个索引。每个条目只会被返回一次，无论它占用多少索引。

不支持对多索引 xa_state 使用 xas_next() 或 xas_prev() 。在多索引条目上使用这些函数中的任何一个都会显示同级条目；调用者应跳过这些条目。

将 NULL 存储到多索引条目的任何索引中，都会将每个索引处的条目设置为 NULL 并解除绑定。可以通过调用不持有 xa_lock 的 xas_split_alloc()，然后获取锁并调用 xas_split()，将多索引条目拆分为占用较小范围的条目。

函数和结构¶

void *xa_mk_value(unsigned long v)¶: 从整数创建 XArray 条目。

参数

unsigned long v: 要存储在 XArray 中的值。

上下文

任何上下文。

返回

适合存储在 XArray 中的条目。

unsigned long xa_to_value(const void *entry)¶: 获取存储在 XArray 条目中的值。

参数

const void *entry: XArray 条目。

上下文

任何上下文。

返回

存储在 XArray 条目中的值。

bool xa_is_value(const void *entry)¶: 确定条目是否为值。

参数

const void *entry: XArray 条目。

上下文

任何上下文。

返回

如果条目为值，则为 True；如果条目为指针，则为 False。

void *xa_tag_pointer(void *p, unsigned long tag)¶: 为带标签的指针创建 XArray 条目。

参数

void *p: 普通指针。
unsigned long tag: 标记值（0、1 或 3）。

描述

如果 XArray 的用户愿意，他们可以标记其指针而不是存储值条目。有三个标记可用（0、1 和 3）。这些与 xa_mark_t 不同，因为它们不会在数组中复制，并且无法搜索到。

上下文

任何上下文。

返回

一个 XArray 条目。

void *xa_untag_pointer(void *entry)¶: 将 XArray 条目转换为普通指针。

参数

void *entry: XArray 条目。

描述

如果已在 XArray 中存储了带标签的指针，请调用此函数以获取指针的未标记版本。

上下文

任何上下文。

返回

一个指针。

unsigned int xa_pointer_tag(void *entry)¶: 获取存储在 XArray 条目中的标记。

参数

void *entry: XArray 条目。

描述

如果已在 XArray 中存储了带标签的指针，请调用此函数以获取该指针的标记。

上下文

任何上下文。

返回

一个标记。

bool xa_is_zero(const void *entry)¶: 判断该条目是否为零条目？

参数

const void *entry: 从 XArray 中检索到的条目

描述

正常的 API 会将包含零条目的槽位的内容返回为 NULL。您只能通过使用高级 API 查看零条目。

返回

如果该条目为零条目，则返回 true。

bool xa_is_err(const void *entry)¶: 报告 XArray 操作是否返回错误

参数

const void *entry: 调用 XArray 函数的结果

描述

如果 XArray 操作无法完成，它将返回一个特殊值来指示错误。此函数会告诉您是否发生了错误；xa_err() 会告诉您发生了哪个错误。

上下文

任何上下文。

返回

如果该条目指示错误，则返回 true。

int xa_err(void *entry)¶: 将 XArray 结果转换为 errno。

参数

void *entry: 调用 XArray 函数的结果。

描述

如果 XArray 操作无法完成，它将返回一个特殊的指针值，该指针值编码了一个 errno。此函数从指针值中提取 errno，如果指针不表示 errno，则返回 0。

上下文

任何上下文。

返回

一个负的 errno 或 0。

struct xa_limit¶: 表示 ID 的范围。

定义:

struct xa_limit {
    u32 max;
    u32 min;
};

成员

max: 要分配的最大 ID（包含）。
min: 要分配的最小 ID（包含）。

描述

此结构直接或通过 XA_LIMIT() 宏使用，以传达对分配有效的 ID 范围。预定义了三个常见的范围：* xa_limit_32b - [0 - UINT_MAX] * xa_limit_31b - [0 - INT_MAX] * xa_limit_16b - [0 - USHRT_MAX]

struct xarray¶: XArray 的锚点。

定义:

struct xarray {
    spinlock_t xa_lock;
};

成员

xa_lock: 保护 XArray 内容的锁。

描述

要使用 xarray，请静态定义它或将其嵌入到您的数据结构中。它是一个非常小的数据结构，因此通常没有必要单独分配它并在您的数据结构中保留指向它的指针。

您也可以使用 xa_lock 来保护您自己的数据结构。

DEFINE_XARRAY_FLAGS¶

DEFINE_XARRAY_FLAGS (name, flags)

定义具有自定义标志的 XArray。

参数

name: 命名您的 XArray 的字符串。
flags: XA_FLAG 值。

描述

这适用于 XArray 的文件作用域定义。它使用所选的名称和标志声明并初始化一个空的 XArray。它等效于在数组上调用 xa_init_flags()，但它是在编译时而不是运行时进行初始化。

DEFINE_XARRAY¶

DEFINE_XARRAY (name)

定义一个 XArray。

参数

name: 命名您的 XArray 的字符串。

描述

这适用于 XArray 的文件作用域定义。它使用所选的名称声明并初始化一个空的 XArray。它等效于在数组上调用 xa_init()，但它是在编译时而不是运行时进行初始化。

DEFINE_XARRAY_ALLOC¶

DEFINE_XARRAY_ALLOC (name)

定义一个从 0 开始分配 ID 的 XArray。

参数

name: 命名您的 XArray 的字符串。

描述

这适用于分配 XArray 的文件作用域定义。另请参见 DEFINE_XARRAY()。

DEFINE_XARRAY_ALLOC1¶

DEFINE_XARRAY_ALLOC1 (name)

定义一个从 1 开始分配 ID 的 XArray。

参数

name: 命名您的 XArray 的字符串。

描述

这适用于分配 XArray 的文件作用域定义。另请参见 DEFINE_XARRAY()。

void xa_init_flags(struct xarray *xa, gfp_t flags)¶: 使用标志初始化一个空的 XArray。

参数

struct xarray *xa: XArray。
gfp_t flags: XA_FLAG 值。

描述

如果您需要使用特殊标志初始化 XArray（例如，您需要从中断上下文获取锁），请使用此函数而不是 xa_init()。

上下文

任何上下文。

void xa_init(struct xarray *xa)¶: 初始化一个空的 XArray。

参数

struct xarray *xa: XArray。

描述

一个空的 XArray 充满了 NULL 条目。

上下文

任何上下文。

bool xa_empty(const struct xarray *xa)¶: 确定数组是否包含任何现有条目。

参数

const struct xarray *xa: XArray。

上下文

任何上下文。

返回

如果数组仅包含 NULL 指针，则返回 true。

bool xa_marked(const struct xarray *xa, xa_mark_t mark)¶: 查询此数组中的任何条目是否设置了标记

参数

const struct xarray *xa: 数组
xa_mark_t mark: 标记值

上下文

任何上下文。

返回

如果任何条目设置了此标记，则返回 true。

xa_for_each_range¶

xa_for_each_range (xa, index, entry, start, last)

迭代 XArray 的一部分。

参数

xa: XArray。
index: entry 的索引。
entry: 从数组中检索到的条目。
start: 要从数组中检索的第一个索引。
last: 要从数组中检索的最后一个索引。

描述

在迭代期间，entry 将具有存储在 xa 中 index 处的条目的值。如果想要跳过或重新处理索引，您可以在迭代期间修改 index。在迭代期间修改数组是安全的。在迭代结束时，entry 将设置为 NULL，并且 index 的值将小于或等于 max。

xa_for_each_range() 是 O(n.log(n))，而 xas_for_each() 是 O(n)。您必须使用 xas_for_each() 处理自己的锁定，并且如果您必须在每次迭代后解锁，它最终也将是 O(n.log(n))。xa_for_each_range() 如果遇到重试条目，则会循环等待；如果您打算查看重试条目，则应改用 xas_for_each() 迭代器。xas_for_each() 迭代器将扩展为比 xa_for_each_range() 更多的内联代码。

上下文

任何上下文。获取和释放 RCU 锁。

xa_for_each_start¶

xa_for_each_start (xa, index, entry, start)

迭代 XArray 的一部分。

参数

xa: XArray。
index: entry 的索引。
entry: 从数组中检索到的条目。
start: 要从数组中检索的第一个索引。

描述

在迭代期间，entry 将具有存储在 xa 中 index 处的条目的值。如果想要跳过或重新处理索引，您可以在迭代期间修改 index。在迭代期间修改数组是安全的。在迭代结束时，entry 将设置为 NULL，并且 index 的值将小于或等于 max。

xa_for_each_start() 的时间复杂度为 O(n.log(n))，而 xas_for_each() 的时间复杂度为 O(n)。使用 xas_for_each() 时，您必须自己处理锁定，并且如果在每次迭代后都必须解锁，那么最终的时间复杂度也将变为 O(n.log(n))。xa_for_each_start() 如果遇到重试条目，将会自旋；如果您打算查看重试条目，则应该改用 xas_for_each() 迭代器。 xas_for_each() 迭代器将比 xa_for_each_start() 扩展成更多的内联代码。

上下文

任何上下文。获取和释放 RCU 锁。

xa_for_each¶

xa_for_each (xa, index, entry)

迭代 XArray 中的现有条目。

参数

xa: XArray。
index: entry 的索引。
entry: 从数组中检索到的条目。

描述

在迭代期间，entry 将具有存储在 xa 中 index 处的条目的值。如果想要跳过或重新处理索引，您可以在迭代期间修改 index。在迭代期间修改数组是安全的。在迭代结束时，entry 将设置为 NULL，并且 index 的值将小于或等于 max。

xa_for_each() 的时间复杂度为 O(n.log(n))，而 xas_for_each() 的时间复杂度为 O(n)。使用 xas_for_each() 时，您必须自己处理锁定，并且如果在每次迭代后都必须解锁，那么最终的时间复杂度也将变为 O(n.log(n))。xa_for_each() 如果遇到重试条目，将会自旋；如果您打算查看重试条目，则应该改用 xas_for_each() 迭代器。 xas_for_each() 迭代器将比 xa_for_each() 扩展成更多的内联代码。

上下文

任何上下文。获取和释放 RCU 锁。

xa_for_each_marked¶

xa_for_each_marked (xa, index, entry, filter)

迭代 XArray 中已标记的条目。

参数

xa: XArray。
index: entry 的索引。
entry: 从数组中检索到的条目。
filter: 选择标准。

描述

在迭代期间，**entry** 将具有 **xa** 中 **index** 处存储的条目的值。迭代将跳过数组中所有不匹配 **filter** 的条目。如果您想跳过或重新处理索引，您可以在迭代期间修改 **index**。在迭代期间修改数组是安全的。在迭代结束时，**entry** 将被设置为 NULL，并且 **index** 将具有小于或等于 max 的值。

xa_for_each_marked() 的时间复杂度为 O(n.log(n))，而 xas_for_each_marked() 的时间复杂度为 O(n)。使用 xas_for_each() 时，您必须自己处理锁定，并且如果在每次迭代后都必须解锁，那么最终的时间复杂度也将变为 O(n.log(n))。xa_for_each_marked() 如果遇到重试条目，将会自旋；如果您打算查看重试条目，则应该改用 xas_for_each_marked() 迭代器。 xas_for_each_marked() 迭代器将比 xa_for_each_marked() 扩展成更多的内联代码。

上下文

任何上下文。获取和释放 RCU 锁。

void *xa_store_bh(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

此函数类似于调用 xa_store()，不同之处在于它在持有数组锁时禁用软中断。

上下文

任何上下文。在禁用软中断的同时获取和释放 xa_lock。

返回

此索引处的旧条目，或者如果发生错误则返回 xa_err()。

void *xa_store_irq(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

此函数类似于调用 xa_store()，不同之处在于它在持有数组锁时禁用中断。

上下文

进程上下文。在禁用中断的同时获取和释放 xa_lock。

返回

此索引处的旧条目，或者如果发生错误则返回 xa_err()。

void *xa_erase_bh(struct xarray *xa, unsigned long index)¶: 从 XArray 中擦除此条目。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。

描述

在此函数返回后，从 **index** 加载将返回 NULL。如果索引是多索引条目的一部分，则所有索引都将被擦除，并且没有条目将是多索引条目的一部分。

上下文

任何上下文。在禁用软中断的同时获取和释放 xa_lock。

返回

此索引处曾经的条目。

void *xa_erase_irq(struct xarray *xa, unsigned long index)¶: 从 XArray 中擦除此条目。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。

描述

在此函数返回后，从 **index** 加载将返回 NULL。如果索引是多索引条目的一部分，则所有索引都将被擦除，并且没有条目将是多索引条目的一部分。

上下文

进程上下文。在禁用中断的同时获取和释放 xa_lock。

返回

此索引处曾经的条目。

void *xa_cmpxchg(struct xarray *xa, unsigned long index, void *old, void *entry, gfp_t gfp)¶: 有条件地替换 XArray 中的条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *old: 要测试的旧值。
void *entry: 要放入数组的新值。
gfp_t gfp: 内存分配标志。

描述

如果 **index** 处的条目与 **old** 相同，则将其替换为 **entry**。如果返回值等于 **old**，则交换成功。

上下文

任何上下文。获取和释放 xa_lock。如果 **gfp** 标志允许，则可能会睡眠。

返回

此索引处的旧值，如果发生错误，则返回 xa_err()。

void *xa_cmpxchg_bh(struct xarray *xa, unsigned long index, void *old, void *entry, gfp_t gfp)¶: 有条件地替换 XArray 中的条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *old: 要测试的旧值。
void *entry: 要放入数组的新值。
gfp_t gfp: 内存分配标志。

描述

此函数类似于调用 xa_cmpxchg()，不同之处在于它在持有数组锁的同时禁用软中断。

上下文

任何上下文。在禁用软中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

此索引处的旧值，如果发生错误，则返回 xa_err()。

void *xa_cmpxchg_irq(struct xarray *xa, unsigned long index, void *old, void *entry, gfp_t gfp)¶: 有条件地替换 XArray 中的条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *old: 要测试的旧值。
void *entry: 要放入数组的新值。
gfp_t gfp: 内存分配标志。

描述

此函数类似于调用 xa_cmpxchg()，不同之处在于它在持有数组锁的同时禁用中断。

上下文

进程上下文。在禁用中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

此索引处的旧值，如果发生错误，则返回 xa_err()。

int xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中，除非已存在另一个条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

如果不存在条目，插入 NULL 条目将存储保留条目（如 xa_reserve()）。如果存在保留条目，则插入将失败，即使从此索引加载将返回 NULL。

上下文

任何上下文。获取和释放 xa_lock。如果 **gfp** 标志允许，则可能会睡眠。

返回

如果存储成功，则为 0。如果存在另一个条目，则为 -EBUSY。如果无法分配内存，则为 -ENOMEM。

int xa_insert_bh(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中，除非已存在另一个条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

如果不存在条目，插入 NULL 条目将存储保留条目（如 xa_reserve()）。如果存在保留条目，则插入将失败，即使从此索引加载将返回 NULL。

上下文

任何上下文。在禁用软中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

如果存储成功，则为 0。如果存在另一个条目，则为 -EBUSY。如果无法分配内存，则为 -ENOMEM。

int xa_insert_irq(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中，除非已存在另一个条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

如果不存在条目，插入 NULL 条目将存储保留条目（如 xa_reserve()）。如果存在保留条目，则插入将失败，即使从此索引加载将返回 NULL。

上下文

进程上下文。在禁用中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

如果存储成功，则为 0。如果存在另一个条目，则为 -EBUSY。如果无法分配内存，则为 -ENOMEM。

int xa_alloc(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 要分配的 ID 范围。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

任何上下文。获取和释放 xa_lock。如果 **gfp** 标志允许，则可能会睡眠。

返回

成功时为 0，如果无法分配内存，则为 -ENOMEM，如果 limit 中没有空闲条目，则为 -EBUSY。

int xa_alloc_bh(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 要分配的 ID 范围。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

任何上下文。在禁用软中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

成功时为 0，如果无法分配内存，则为 -ENOMEM，如果 limit 中没有空闲条目，则为 -EBUSY。

int xa_alloc_irq(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 要分配的 ID 范围。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

进程上下文。在禁用中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

成功时为 0，如果无法分配内存，则为 -ENOMEM，如果 limit 中没有空闲条目，则为 -EBUSY。

int xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, u32 *next, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 已分配 ID 的范围。
u32 *next: 指向要分配的下一个 ID 的指针。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。搜索空条目将从 next 开始，必要时会环绕。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

任何上下文。获取和释放 xa_lock。如果 **gfp** 标志允许，则可能会睡眠。

返回

如果分配成功且没有回绕，则返回 0。如果分配在回绕后成功，则返回 1；如果无法分配内存，则返回 -ENOMEM；如果 limit 中没有空闲条目，则返回 -EBUSY。

int xa_alloc_cyclic_bh(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, u32 *next, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 已分配 ID 的范围。
u32 *next: 指向要分配的下一个 ID 的指针。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。搜索空条目将从 next 开始，必要时会环绕。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

任何上下文。在禁用软中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

如果分配成功且没有回绕，则返回 0。如果分配在回绕后成功，则返回 1；如果无法分配内存，则返回 -ENOMEM；如果 limit 中没有空闲条目，则返回 -EBUSY。

int xa_alloc_cyclic_irq(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, u32 *next, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 已分配 ID 的范围。
u32 *next: 指向要分配的下一个 ID 的指针。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。搜索空条目将从 next 开始，必要时会环绕。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

进程上下文。在禁用中断的同时获取和释放 xa_lock。如果 gfp 标志允许，则可能会休眠。

返回

如果分配成功且没有回绕，则返回 0。如果分配在回绕后成功，则返回 1；如果无法分配内存，则返回 -ENOMEM；如果 limit 中没有空闲条目，则返回 -EBUSY。

int xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp)¶: 在 XArray 中预留此索引。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
gfp_t gfp: 内存分配标志。

描述

确保在数组中 index 位置有存储条目的空间。如果 index 位置已经存储了内容，此函数不执行任何操作。如果该位置没有内容，则该条目被标记为预留。从预留的条目加载会返回一个 NULL 指针。

如果您没有使用您预留的条目，请调用 xa_release() 或 xa_erase() 来释放任何不必要的内存。

上下文

任何上下文。获取和释放 xa_lock。如果 **gfp** 标志允许，则可能会睡眠。

返回

如果预留成功，则返回 0；如果失败，则返回 -ENOMEM。

int xa_reserve_bh(struct xarray *xa, unsigned long index, gfp_t gfp)¶: 在 XArray 中预留此索引。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
gfp_t gfp: 内存分配标志。

描述

xa_reserve() 的软中断禁用版本。

上下文

任何上下文。在禁用软中断的同时获取和释放 xa_lock。

返回

如果预留成功，则返回 0；如果失败，则返回 -ENOMEM。

int xa_reserve_irq(struct xarray *xa, unsigned long index, gfp_t gfp)¶: 在 XArray 中预留此索引。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
gfp_t gfp: 内存分配标志。

描述

xa_reserve() 的中断禁用版本。

上下文

进程上下文。在禁用中断的同时获取和释放 xa_lock。

返回

如果预留成功，则返回 0；如果失败，则返回 -ENOMEM。

void xa_release(struct xarray *xa, unsigned long index)¶: 释放预留的条目。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。

描述

在调用 xa_reserve() 之后，您可以调用此函数来释放预留。如果 index 位置的条目已存储，此函数将不执行任何操作。

bool xa_is_sibling(const void *entry)¶: 条目是否为同级条目？

参数

const void *entry: 从 XArray 中检索到的条目

返回

如果条目是同级条目，则返回 true。

bool xa_is_retry(const void *entry)¶: 条目是否为重试条目？

参数

const void *entry: 从 XArray 中检索到的条目

返回

如果条目是重试条目，则返回 true。

bool xa_is_advanced(const void *entry)¶: 此条目是否仅允许用于高级 API？

参数

const void *entry: 要存储在 XArray 中的条目。

返回

如果该条目不能通过普通 API 存储，则返回 true。

xa_update_node_t¶: Typedef: 来自 XArray 的回调函数。

语法

void xa_update_node_t (struct xa_node *node)

参数

struct xa_node *node: 正在处理的节点

描述

每次 XArray 更新节点中存在和值条目的计数时，都会调用此函数。它允许高级用户维护节点中的 private_list。

上下文

xa_lock 被持有，并且中断可能被禁用。实现不应放弃 xa_lock，也不应重新启用中断。

XA_STATE¶

XA_STATE (name, array, index)

声明一个 XArray 操作状态。

参数

name: 此操作状态的名称（通常为 xas）。
数组: 要操作的数组。
index: 感兴趣的初始索引。

描述

在堆栈上声明并初始化 xa_state。

XA_STATE_ORDER¶

XA_STATE_ORDER (name, array, index, order)

声明一个 XArray 操作状态。

参数

name: 此操作状态的名称（通常为 xas）。
数组: 要操作的数组。
index: 感兴趣的初始索引。
顺序: 条目的顺序。

描述

在堆栈上声明并初始化 xa_state。此 XA_STATE() 的变体允许您指定要操作的元素的“顺序”。

int xas_error(const struct xa_state *xas)¶: 返回存储在 xa_state 中的 errno。

参数

const struct xa_state *xas: XArray 操作状态。

返回

如果未记录任何错误，则返回 0。如果记录了错误，则返回负 errno。

void xas_set_err(struct xa_state *xas, long err)¶: 在 xa_state 中记录错误。

参数

struct xa_state *xas: XArray 操作状态。
long err: 负错误编号。

描述

只能使用负的 err 调用此函数；零或正的错误可能不会按您预期的那样运行。如果要清除 xa_state 中的错误，请使用 xas_reset()。

bool xas_invalid(const struct xa_state *xas)¶: xas 是否处于重试或错误状态？

参数

const struct xa_state *xas: XArray 操作状态。

返回

如果 xas 不能用于操作，则返回 true。

bool xas_valid(const struct xa_state *xas)¶: xas 是否是数组中的有效游标？

参数

const struct xa_state *xas: XArray 操作状态。

返回

如果 xas 可以用于操作，则返回 true。

bool xas_is_node(const struct xa_state *xas)¶: xas 是否指向一个节点？

参数

const struct xa_state *xas: XArray 操作状态。

返回

如果 xas 当前引用一个节点，则返回 true。

void xas_reset(struct xa_state *xas)¶: 重置 XArray 操作状态。

参数

struct xa_state *xas: XArray 操作状态。

描述

重置 xas 的错误或遍历状态，以便未来对数组的遍历将从根开始。如果您已释放 xarray 锁并想重用 xa_state，请使用此方法。

上下文

任何上下文。

bool xas_retry(struct xa_state *xas, const void *entry)¶: 如果合适，重试操作。

参数

struct xa_state *xas: XArray 操作状态。
const void *entry: 来自 xarray 的条目。

描述

高级函数有时可能会返回一个内部条目，例如重试条目或零条目。如果需要，此函数会设置 xas 以从数组头部重新开始遍历。

上下文

任何上下文。

返回

如果需要重试操作，则返回 true。

void *xas_reload(struct xa_state *xas)¶: 从 xarray 重新获取条目。

参数

struct xa_state *xas: XArray 操作状态。

描述

使用此函数来检查先前加载的条目是否仍然具有相同的值。这对于无锁页面缓存查找非常有用，我们在其中仅使用 RCU 锁来保护我们遍历数组，锁定页面，然后检查自从我们查找页面以来页面是否已移动。

调用方保证 xas 仍然有效。如果它可能处于错误或重新启动状态，请改为调用 xas_load()。

返回

此位置在 xarray 中的条目。

void xas_set(struct xa_state *xas, unsigned long index)¶: 为不同的索引设置 XArray 操作状态。

参数

struct xa_state *xas: XArray 操作状态。
unsigned long index: XArray 中的新索引。

描述

移动操作状态以引用不同的索引。这将具有从顶部开始遍历的效果；请参阅 xas_next() 以移动到相邻的索引。

void xas_advance(struct xa_state *xas, unsigned long index)¶: 跳过兄弟条目。

参数

struct xa_state *xas: XArray 操作状态。
unsigned long index: 最后一个兄弟条目的索引。

描述

移动操作状态以引用最后一个兄弟条目。这对于通常想查看兄弟条目但有时又想跳过它们的循环很有用。如果要移动到不属于此条目的索引，请使用 xas_set()。

void xas_set_order(struct xa_state *xas, unsigned long index, unsigned int order)¶: 为多槽条目设置 XArray 操作状态。

参数

struct xa_state *xas: XArray 操作状态。
unsigned long index: 操作的目标。
unsigned int order: 条目占用 2^**order** 个索引。

void xas_set_update(struct xa_state *xas, xa_update_node_t update)¶: 为回调设置 XArray 操作状态。

参数

struct xa_state *xas: XArray 操作状态。
xa_update_node_t update: 更新节点时要调用的函数。

描述

XArray 可以在更新 xa_node 后通知调用方。这是高级功能，仅页面缓存和交换缓存需要此功能。

void *xas_next_entry(struct xa_state *xas, unsigned long max)¶: 将迭代器前进到下一个存在的条目。

参数

struct xa_state *xas: XArray 操作状态。
unsigned long max: 要返回的最高索引。

描述

xas_next_entry() 是一个内联函数，用于优化 xarray 遍历的速度。它等效于调用 xas_find()，并将为所有困难情况调用 xas_find()。

返回

当前由 xas 引用的条目之后的下一个存在的条目。

void *xas_next_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)¶: 将迭代器前进到下一个标记的条目。

参数

struct xa_state *xas: XArray 操作状态。
unsigned long max: 要返回的最高索引。
xa_mark_t mark: 要搜索的标记。

描述

xas_next_marked() 是一个内联函数，用于优化 xarray 遍历的速度。它等效于调用 xas_find_marked()，并将为所有困难情况调用 xas_find_marked()。

返回

当前由 xas 引用的条目之后的下一个标记的条目。

xas_for_each¶

xas_for_each (xas, entry, max)

遍历 XArray 的一个范围。

参数

xas: XArray 操作状态。
entry: 从数组中检索的条目。
max: 从数组中检索的最大索引。

描述

对于 xarray 中当前 xas 位置和 max 之间的每个条目，将执行循环体。entry 将设置为从 xarray 检索的条目。在循环体中删除数组中的条目是安全的。在迭代时，您应持有 RCU 锁或 xa_lock。如果需要释放锁，请首先调用 xas_pause()。

xas_for_each_marked¶

xas_for_each_marked (xas, entry, max, mark)

遍历 XArray 的一个范围。

参数

xas: XArray 操作状态。
entry: 从数组中检索的条目。
max: 从数组中检索的最大索引。
标记: 要搜索的标记。

描述

循环体将为 xarray 中当前 xas 位置和 max 之间每个标记的条目执行。 entry 将设置为从 xarray 中检索的条目。在循环体中删除数组中的条目是安全的。在迭代时，你应该持有 RCU 锁或 xa_lock。如果你需要释放锁，请先调用 xas_pause()。

xas_for_each_conflict¶

xas_for_each_conflict (xas, entry)

遍历 XArray 的一个范围。

参数

xas: XArray 操作状态。
entry: 从数组中检索的条目。

描述

循环体将为 XArray 中 xas 指定范围内的每个条目执行。如果循环正常终止，则 entry 将为 NULL。用户可以跳出循环，这将使 entry 设置为冲突的条目。调用者还可以调用 xa_set_err() 来退出循环，同时设置一个错误来记录原因。

void *xas_prev(struct xa_state *xas)¶: 将迭代器移动到上一个索引。

参数

struct xa_state *xas: XArray 操作状态。

描述

如果 xas 处于错误状态，它将保持错误状态，并且此函数将返回 NULL。如果 xas 从未被遍历过，它将具有调用 xas_load() 的效果。否则，索引将减 1，并且状态将遍历到数组中的正确位置以进行下一次操作。

如果迭代器引用索引 0，则此函数将回绕到 ULONG_MAX。

返回

新索引处的条目。这可能是 NULL 或内部条目。

void *xas_next(struct xa_state *xas)¶: 将状态移动到下一个索引。

参数

struct xa_state *xas: XArray 操作状态。

描述

如果 xas 处于错误状态，它将保持错误状态，并且此函数将返回 NULL。如果 xas 从未被遍历过，它将具有调用 xas_load() 的效果。否则，索引将加 1，并且状态将遍历到数组中的正确位置以进行下一次操作。

如果迭代器引用索引 ULONG_MAX，则此函数将回绕到 0。

返回

新索引处的条目。这可能是 NULL 或内部条目。

void *xas_load(struct xa_state *xas)¶: 从 XArray 加载条目（高级）。

参数

struct xa_state *xas: XArray 操作状态。

描述

通常将 xas 遍历到适当的状态以加载存储在 xa_index 处的条目。但是，如果 xas 处于错误状态，它将不执行任何操作并返回 NULL。 xas_load() 永远不会扩展树。

如果 xa_state 设置为对多索引条目进行操作，则即使 xas 指定的范围内存在条目，xas_load() 也可能返回 NULL 或内部条目。

上下文

任何上下文。调用者应持有 xa_lock 或 RCU 锁。

返回

通常是 XArray 中的条目，但请参阅异常描述。

bool xas_nomem(struct xa_state *xas, gfp_t gfp)¶: 如果需要，分配内存。

参数

struct xa_state *xas: XArray 操作状态。
gfp_t gfp: 内存分配标志。

描述

如果我们需要向 XArray 添加新节点，我们会尝试在持有锁的同时使用 GFP_NOWAIT 分配内存，这通常会成功。如果它失败，则将 xas 标记为需要内存才能继续。调用者应释放锁并调用 xas_nomem()。如果 xas_nomem() 成功，则调用者应重试操作。

保证向前进行，因为在此处分配了一个节点并将其存储在 xa_state 中，xas_alloc() 将在此处找到它。可能会在 slab 分配器中找到更多节点，但我们不会在此处将它们绑定在一起。

返回

如果需要内存，并且已成功分配，则为 true。

void xas_free_nodes(struct xa_state *xas, struct xa_node *top)¶: 释放此节点及其引用的所有节点

参数

struct xa_state *xas: 数组操作状态。
struct xa_node *top: 要释放的节点

描述

此节点已从树中删除。我们现在必须释放它及其所有子节点。可能存在 RCU 遍历器引用树中，因此我们必须将所有条目替换为重试标记。

void xas_create_range(struct xa_state *xas)¶: 确保对此范围的存储会成功

参数

struct xa_state *xas: XArray 操作状态。

描述

创建 xas 所涵盖范围内的所有槽。将 xas 设置为创建单索引条目，并将其放置在范围的开头。这是为了尚未转换为使用多索引条目的用户的好处。

void *xas_store(struct xa_state *xas, void *entry)¶: 将此条目存储在 XArray 中。

参数

struct xa_state *xas: XArray 操作状态。
void *entry: 新条目。

描述

如果 xas 正在对多索引条目进行操作，则此函数返回的条目本质上毫无意义（它可能是内部条目，也可能是 NULL，即使在范围内覆盖的某些索引处存在非 NULL 条目）。这对于任何当前用户来说都不是问题，并且如果需要可以更改。

返回

此索引处的旧条目。

bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)¶: 返回此标记的状态。

参数

const struct xa_state *xas: XArray 操作状态。
xa_mark_t mark: 标记编号。

返回

如果标记已设置，则为 true；如果标记已清除或 xas 处于错误状态，则为 false。

void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)¶: 在此条目及其父条目上设置标记。

参数

const struct xa_state *xas: XArray 操作状态。
xa_mark_t mark: 标记编号。

描述

在此条目上设置指定的标记，并向上遍历树，将其设置在所有祖先条目上。如果 xas 未遍历到条目或处于错误状态，则不执行任何操作。

void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)¶: 清除此条目及其父条目上的标记。

参数

const struct xa_state *xas: XArray 操作状态。
xa_mark_t mark: 标记编号。

描述

清除此条目上指定的标记，并返回头尝试清除所有祖先条目上的标记。如果 xas 未遍历到条目或处于错误状态，则不执行任何操作。

void xas_init_marks(const struct xa_state *xas)¶: 初始化条目的所有标记

参数

const struct xa_state *xas: 数组操作状态。

描述

初始化 xas 指定的条目的所有标记。如果我们正在使用标记跟踪空闲条目，则我们需要在所有条目上设置它。所有其他标记都已清除。

此实现效率可能不高；我们可能会多次遍历树。

void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order, gfp_t gfp)¶: 为拆分条目分配内存。

参数

struct xa_state *xas: XArray 操作状态。
void *entry: 将存储在数组中的新条目。
unsigned int order: 当前条目的顺序。
gfp_t gfp: 内存分配标志。

描述

此函数应在调用 xas_split() 之前调用。如有必要，它将分配新的节点（并用 entry 填充它们），为即将到来的将大小为 order 的条目拆分为存储在 xas 中的顺序的条目做好准备。

上下文

如果 gfp 标志允许，则可能会休眠。

void xas_split(struct xa_state *xas, void *entry, unsigned int order)¶: 将多索引条目拆分为较小的条目。

参数

struct xa_state *xas: XArray 操作状态。
void *entry: 要存储在数组中的新条目。
unsigned int order: 当前条目的顺序。

描述

新条目的大小在 xas 中设置。 entry 中的值将复制到所有替换条目。

上下文

任何上下文。调用者应持有 xa_lock。

void xas_pause(struct xa_state *xas)¶: 暂停遍历以释放锁。

参数

struct xa_state *xas: XArray 操作状态。

描述

一些用户需要暂停遍历并释放他们持有的锁，以便让步于更高优先级的线程或对条目执行操作。这些用户应在释放锁之前调用此函数。它会重置 xas，使其适合用户重新获取锁后循环的下一次迭代。如果遍历期间发现的大多数条目都需要您调用 xas_pause()，则 xa_for_each() 迭代器可能更合适。

请注意，xas_pause() 仅适用于正向迭代。如果用户需要暂停反向迭代，我们将需要一个 xas_pause_rev()。

void *xas_find(struct xa_state *xas, unsigned long max)¶: 在 XArray 中查找下一个存在的条目。

参数

struct xa_state *xas: XArray 操作状态。
unsigned long max: 要返回的最高索引。

描述

如果 xas 尚未遍历到某个条目，则返回索引 >= xas.xa_index 的条目。如果已经遍历过，则当前指向的条目已被处理，因此我们移动到下一个条目。

如果没有找到任何条目，并且数组小于 max，则迭代器设置为数组中尚未存在的最小索引。这允许将 xas 立即传递给 xas_store()。

返回

如果找到，则返回条目，否则返回 NULL。

void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)¶: 在 XArray 中查找下一个标记的条目。

参数

struct xa_state *xas: XArray 操作状态。
unsigned long max: 要返回的最高索引。
xa_mark_t mark: 要搜索的标记号。

描述

如果 xas 尚未遍历到某个条目，则返回索引 >= xas.xa_index 的标记条目。如果已经遍历过，则当前指向的条目已被处理，因此我们返回索引 > xas.xa_index 的第一个标记条目。

如果没有找到标记的条目，并且数组小于 max，则将 xas 设置为边界状态，并将 xas->xa_index 设置为数组中尚未存在的最小索引。这允许将 xas 立即传递给 xas_store()。

如果在达到 max 之前没有找到任何条目，则将 xas 设置为重新启动状态。

返回

如果找到，则返回条目，否则返回 NULL。

void *xas_find_conflict(struct xa_state *xas)¶: 查找范围内的下一个存在的条目。

参数

struct xa_state *xas: XArray 操作状态。

描述

xas 描述范围和该范围内的位置。

上下文

任何上下文。期望持有 xa_lock。

返回

xas 所覆盖范围内的下一个条目，或 NULL。

void *xa_load(struct xarray *xa, unsigned long index)¶: 从 XArray 加载条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。

上下文

任何上下文。获取和释放 RCU 锁。

返回

xa 中 index 处的条目。

void *__xa_erase(struct xarray *xa, unsigned long index)¶: 在锁定时从 XArray 中删除此条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。

描述

在此函数返回后，从 **index** 加载将返回 NULL。如果索引是多索引条目的一部分，则所有索引都将被擦除，并且没有条目将是多索引条目的一部分。

上下文

任何上下文。期望在进入时持有 xa_lock。

返回

此索引处曾经的条目。

void *xa_erase(struct xarray *xa, unsigned long index)¶: 从 XArray 中擦除此条目。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。

描述

在此函数返回后，从 **index** 加载将返回 NULL。如果索引是多索引条目的一部分，则所有索引都将被擦除，并且没有条目将是多索引条目的一部分。

上下文

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

返回

此索引处曾经的条目。

void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

调用此函数时，您必须已经持有 xa_lock。如果需要分配内存，它将释放锁，然后在之后重新获取锁。

上下文

任何上下文。期望在进入时持有 xa_lock。如果 gfp 标志允许，可能会释放并重新获取 xa_lock。

返回

此索引处的旧条目，或者如果发生错误则返回 xa_err()。

void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

此函数返回后，从此索引加载将返回 entry。存储到现有的多索引条目中会更新每个索引的条目。与 index 关联的标记不受影响，除非 entry 为 NULL。

上下文

任何上下文。获取和释放 xa_lock。如果 **gfp** 标志允许，则可能会睡眠。

返回

成功时此索引处的旧条目，如果无法将 entry 存储在 XArray 中，则返回 xa_err(-EINVAL)；如果内存分配失败，则返回 xa_err(-ENOMEM)。

void *__xa_cmpxchg(struct xarray *xa, unsigned long index, void *old, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *old: 要测试的旧值。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

调用此函数时，您必须已经持有 xa_lock。如果需要分配内存，它将释放锁，然后在之后重新获取锁。

上下文

任何上下文。期望在进入时持有 xa_lock。如果 gfp 标志允许，可能会释放并重新获取 xa_lock。

返回

此索引处的旧条目，或者如果发生错误则返回 xa_err()。

int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)¶: 如果 XArray 中不存在条目，则存储此条目。

参数

struct xarray *xa: XArray。
unsigned long index: 数组中的索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

如果不存在条目，插入 NULL 条目将存储保留条目（如 xa_reserve()）。如果存在保留条目，则插入将失败，即使从此索引加载将返回 NULL。

上下文

任何上下文。期望在进入时持有 xa_lock。如果 gfp 标志允许，可能会释放并重新获取 xa_lock。

返回

如果存储成功，则为 0。如果存在另一个条目，则为 -EBUSY。如果无法分配内存，则为 -ENOMEM。

void *xa_store_range(struct xarray *xa, unsigned long first, unsigned long last, void *entry, gfp_t gfp)¶: 将此条目存储在 XArray 中的一系列索引处。

参数

struct xarray *xa: XArray。
unsigned long first: 要影响的第一个索引。
unsigned long last: 要影响的最后一个索引。
void *entry: 新条目。
gfp_t gfp: 内存分配标志。

描述

在此函数返回后，从**first**和**last**（包括两者）之间的任何索引加载都将返回**entry**。存储到现有的多索引条目会更新每个索引的条目。与**index**关联的标记不受影响，除非**entry**是 NULL。

上下文

进程上下文。获取并释放 xa_lock。如果**gfp**标志允许，可能会休眠。

返回

成功时为 NULL，如果**entry**无法存储在 XArray 中，则为 xa_err(-EINVAL)，如果内存分配失败，则为 xa_err(-ENOMEM)。

int xas_get_order(struct xa_state *xas)¶: 获取条目的顺序。

参数

struct xa_state *xas: XArray 操作状态。

描述

在 xas_load 之后调用，xas 不应处于错误状态。

返回

一个介于 0 和 63 之间的数字，表示条目的顺序。

int xa_get_order(struct xarray *xa, unsigned long index)¶: 获取条目的顺序。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。

返回

一个介于 0 和 63 之间的数字，表示条目的顺序。

int __xa_alloc(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 已分配 ID 的范围。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

任何上下文。期望在进入时持有 xa_lock。如果 gfp 标志允许，可能会释放并重新获取 xa_lock。

返回

成功时为 0，如果无法分配内存，则为 -ENOMEM，如果 limit 中没有空闲条目，则为 -EBUSY。

int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, u32 *next, gfp_t gfp)¶: 在 XArray 中找到存储此条目的位置。

参数

struct xarray *xa: XArray。
u32 *id: 指向 ID 的指针。
void *entry: 新条目。
struct xa_limit limit: 已分配 ID 的范围。
u32 *next: 指向要分配的下一个 ID 的指针。
gfp_t gfp: 内存分配标志。

描述

在 xa 中找到 limit.min 和 limit.max 之间的空条目，将索引存储到 id 指针中，然后将条目存储在该索引处。并发查找不会看到未初始化的 id。搜索空条目将从 next 开始，必要时会环绕。

必须仅在使用 xa_init_flags() 中设置的标志 XA_FLAGS_ALLOC 初始化的 xarray 上操作。

上下文

任何上下文。期望在进入时持有 xa_lock。如果 gfp 标志允许，可能会释放并重新获取 xa_lock。

返回

如果分配成功且没有回绕，则返回 0。如果分配在回绕后成功，则返回 1；如果无法分配内存，则返回 -ENOMEM；如果 limit 中没有空闲条目，则返回 -EBUSY。

void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)¶: 在锁定时在此条目上设置此标记。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。
xa_mark_t mark: 标记编号。

描述

尝试在 NULL 条目上设置标记不会成功。

上下文

任何上下文。期望在进入时持有 xa_lock。

void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)¶: 在锁定时清除此条目上的此标记。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。
xa_mark_t mark: 标记编号。

上下文

任何上下文。期望在进入时持有 xa_lock。

bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)¶: 查询是否在此条目上设置了此标记。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。
xa_mark_t mark: 标记编号。

描述

此函数使用 RCU 读取锁，因此结果在返回时可能已过时。如果您需要结果稳定，请使用锁。

上下文

任何上下文。获取和释放 RCU 锁。

返回

如果**index**处的条目已设置此标记，则为 True，否则为 False。

void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)¶: 在此条目上设置此标记。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。
xa_mark_t mark: 标记编号。

描述

尝试在 NULL 条目上设置标记不会成功。

上下文

进程上下文。获取并释放 xa_lock。

void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)¶: 清除此条目上的此标记。

参数

struct xarray *xa: XArray。
unsigned long index: 条目的索引。
xa_mark_t mark: 标记编号。

描述

清除标记总是成功。

上下文

进程上下文。获取并释放 xa_lock。

void *xa_find(struct xarray *xa, unsigned long *indexp, unsigned long max, xa_mark_t filter)¶: 在 XArray 中搜索条目。

参数

struct xarray *xa: XArray。
unsigned long *indexp: 指向索引的指针。
unsigned long max: 要搜索的最大索引。
xa_mark_t filter: 选择标准。

描述

在 xa 中查找与 filter 匹配，且索引值不小于 indexp 且不大于 max 的最小索引项。如果找到条目，则 indexp 将更新为该条目的索引。此函数受 RCU 读取锁保护，因此它可能找不到同时添加的条目。它不会返回 XA_RETRY_ENTRY；如果您需要查看重试条目，请使用 xas_find()。

上下文

任何上下文。获取和释放 RCU 锁。

返回

如果找到，则返回条目，否则返回 NULL。

void *xa_find_after(struct xarray *xa, unsigned long *indexp, unsigned long max, xa_mark_t filter)¶: 在 XArray 中搜索存在的条目。

参数

struct xarray *xa: XArray。
unsigned long *indexp: 指向索引的指针。
unsigned long max: 要搜索的最大索引。
xa_mark_t filter: 选择标准。

描述

在 xa 中查找与 filter 匹配，且索引值大于 indexp 且不大于 max 的最小索引项。如果找到条目，则 indexp 将更新为该条目的索引。此函数受 RCU 读取锁保护，因此它可能会错过同时添加的条目。它不会返回 XA_RETRY_ENTRY；如果您需要查看重试条目，请使用 xas_find()。

上下文

任何上下文。获取和释放 RCU 锁。

返回

如果找到，则返回指针，否则返回 NULL。

unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start, unsigned long max, unsigned int n, xa_mark_t filter)¶: 将选定的条目从 XArray 复制到普通数组中。

参数

struct xarray *xa: 要从中复制的源 XArray。
void **dst: 要将条目复制到的缓冲区。
unsigned long start: XArray 中符合选择条件的首个索引。
unsigned long max: XArray 中符合选择条件的最后一个索引。
unsigned int n: 要复制的最大条目数。
xa_mark_t filter: 选择标准。

描述

从 XArray 中复制最多 n 个与 filter 匹配的条目。复制的条目的索引将在 start 和 max 之间（包括两者）。

filter 可以是 XArray 标记值，在这种情况下，将复制标记有该标记的条目。它也可以是 XA_PRESENT，在这种情况下，将复制所有不为 NULL 的条目。

返回的条目可能不代表 XArray 在某一时刻的快照。例如，如果另一个线程存储到索引 5，然后存储到索引 10，则调用 xa_extract() 可能会返回索引 5 的旧内容和索引 10 的新内容。在此函数运行时未修改的索引将不会被跳过。

如果您需要更强的保证，在调用此函数时持有 xa_lock 将防止并发修改。

上下文

任何上下文。获取和释放 RCU 锁。

返回

已复制的条目数。

void xa_delete_node(struct xa_node *node, xa_update_node_t update)¶: 供工作集代码使用的私有接口。

参数

struct xa_node *node: 要从树中删除的节点。
xa_update_node_t update: 用于更新祖先节点的函数。

上下文

必须在进入时持有 xa_lock，并且不会释放。

void xa_destroy(struct xarray *xa)¶: 释放所有内部数据结构。

参数

struct xarray *xa: XArray。

描述

调用此函数后，XArray 将为空，并已释放为其内部数据结构分配的所有内存。您负责释放 XArray 引用的对象。

上下文

任何上下文。获取并释放 xa_lock，中断安全。

Linux 内核

目录

本页

XArray¶

概述¶

普通 API¶

搜索标记¶

分配 XArray¶

内存分配¶

锁定¶

高级 API¶

内部条目¶

其他功能¶

多索引条目¶

函数和结构¶