0001 .. SPDX-License-Identifier: GPL-2.0+
0002 .. include:: ../disclaimer-zh_CN.rst
0003
0004 :Original: Documentation/core-api/xarray.rst
0005
0006 :翻译:
0007
0008 司延腾 Yanteng Si <siyanteng@loongson.cn>
0009 周彬彬 Binbin Zhou <zhoubinbin@loongson.cn>
0010
0011 :校译:
0012
0013
0014
0015 .. _cn_core-api_xarray:
0016
0017 ======
0018 XArray
0019 ======
0020
0021 :作者: Matthew Wilcox
0022
0023 概览
0024 ====
0025
0026 XArray是一个抽象的数据类型，它的行为就像一个非常大的指针数组。它满足了许多与哈
0027 希或传统可调整大小的数组相同的需求。与哈希不同的是，它允许你以一种高效的缓存方
0028 式合理地转到下一个或上一个条目。与可调整大小的数组相比，不需要复制数据或改变MMU
0029 的映射来增加数组。与双链表相比，它的内存效率更高，可并行，对缓存更友好。它利用
0030 RCU的优势来执行查找而不需要锁定。
0031
0032 当使用的索引是密集聚集的时候，XArray的实现是有效的；而哈希对象并使用哈希作为索引
0033 将不会有好的表现。XArray对小的索引进行了优化，不过对大的索引仍有良好的性能。如果
0034 你的索引可以大于 ``ULONG_MAX`` ，那么XArray就不适合你的数据类型。XArray最重要
0035 的用户是页面高速缓存。
0036
0037 普通指针可以直接存储在XArray中。它们必须是4字节对齐的，这对任何从kmalloc()和
0038 alloc_page()返回的指针来说都是如此。这对任意的用户空间指针和函数指针来说都不是
0039 真的。你可以存储指向静态分配对象的指针，只要这些对象的对齐方式至少是4（字节）。
0040
0041 你也可以在XArray中存储0到 ``LONG_MAX`` 之间的整数。你必须首先使用xa_mk_value()
0042 将其转换为一个条目。当你从XArray中检索一个条目时，你可以通过调用xa_is_value()检
0043 查它是否是一个值条目，并通过调用xa_to_value()将它转换回一个整数。
0044
0045 一些用户希望对他们存储在XArray中的指针进行标记。你可以调用xa_tag_pointer()来创建
0046 一个带有标签的条目，xa_untag_pointer()将一个有标签的条目转回一个无标签的指针，
0047 xa_pointer_tag()来检索一个条目的标签。标签指针使用相同的位，用于区分值条目和普通
0048 指针，所以你必须决定他们是否要在任何特定的XArray中存储值条目或标签指针。
0049
0050 XArray不支持存储IS_ERR()指针，因为有些指针与值条目或内部条目冲突。
0051
0052 XArray的一个不寻常的特点是能够创建占据一系列索引的条目。一旦存储到其中，查询该范围
0053 内的任何索引将返回与查询该范围内任何其他索引相同的条目。存储到任何索引都会存储所有
0054 的索引条目。多索引条目可以明确地分割成更小的条目，或者将其存储 ``NULL`` 到任何条目中
0055 都会使XArray忘记范围。
0056
0057 普通API
0058 =======
0059
0060 首先初始化一个XArray，对于静态分配的XArray可以用DEFINE_XARRAY()，对于动态分配的
0061 XArray可以用xa_init()。一个新初始化的XArray在每个索引处都包含一个 ``NULL`` 指针。
0062
0063 然后你可以用xa_store()来设置条目，用xa_load()来获取条目。xa_store将用新的条目覆盖任
0064 何条目，并返回存储在该索引的上一个条目。你可以使用xa_erase()来代替调用xa_store()的
0065 ``NULL`` 条目。一个从未被存储过的条目、一个被擦除的条目和一个最近被存储过 ``NULL`` 的
0066 条目之间没有区别。
0067
0068 你可以通过使用xa_cmpxchg()有条件地替换一个索引中的条目。和cmpxchg()一样，它只有在该索
0069 引的条目有 ‘旧‘ 值时才会成功。它也会返回该索引上的条目；如果它返回与传递的 ‘旧‘ 相同的条
0070 目，那么xa_cmpxchg()就成功了。
0071
0072 如果你只想在某个索引的当前条目为 ``NULL`` 时将一个新条目存储到该索引，你可以使用xa_insert()，
0073 如果该条目不是空的，则返回 ``-EBUSY`` 。
0074
0075 你可以通过调用xa_extract()将条目从XArray中复制到一个普通数组中。或者你可以通过调用
0076 xa_for_each()、xa_for_each_start()或xa_for_each_range()来遍历XArray中的现有条目。你
0077 可能更喜欢使用xa_find()或xa_find_after()来移动到XArray中的下一个当前条目。
0078
0079 调用xa_store_range()可以在一个索引范围内存储同一个条目。如果你这样做，其他的一些操作将以
0080 一种稍微奇怪的方式进行。例如，在一个索引上标记条目可能会导致该条目在一些，但不是所有其他索
0081 引上被标记。储存到一个索引中可能会导致由一些，但不是所有其他索引检索的条目发生变化。
0082
0083 有时你需要确保对xa_store()的后续调用将不需要分配内存。xa_reserve()函数将在指定索引处存储
0084 一个保留条目。普通API的用户将看到这个条目包含 ``NULL`` 。如果你不需要使用保留的条目，你可
0085 以调用xa_release()来删除这个未使用的条目。如果在此期间有其他用户存储到该条目，xa_release()
0086 将不做任何事情；相反，如果你想让该条目变成 ``NULL`` ，你应该使用xa_erase()。在一个保留的条
0087 目上使用xa_insert()将会失败。
0088
0089 如果数组中的所有条目都是 ``NULL`` ，xa_empty()函数将返回 ``true`` 。
0090
0091 最后，你可以通过调用xa_destroy()删除XArray中的所有条目。如果XArray的条目是指针，你可能希望
0092 先释放这些条目。你可以通过使用xa_for_each()迭代器遍历XArray中所有存在的条目来实现这一目的。
0093
0094 搜索标记
0095 --------
0096
0097 数组中的每个条目都有三个与之相关的位，称为标记。每个标记可以独立于其他标记被设置或清除。你可以
0098 通过使用xa_for_each_marked()迭代器来迭代有标记的条目。
0099
0100 你可以通过使用xa_get_mark()来查询某个条目是否设置了标记。如果该条目不是 ``NULL`` ，你可以通过
0101 使用xa_set_mark()来设置一个标记，并通过调用xa_clear_mark()来删除条目上的标记。你可以通过调用
0102 xa_marked()来询问XArray中的任何条目是否有一个特定的标记被设置。从XArray中删除一个条目会导致与
0103 该条目相关的所有标记被清除。
0104
0105 在一个多索引条目的任何索引上设置或清除标记将影响该条目所涵盖的所有索引。查询任何索引上的标记将返
0106 回相同的结果。
0107
0108 没有办法对没有标记的条目进行迭代；数据结构不允许有效地实现这一点。目前没有迭代器来搜索比特的逻辑
0109 组合（例如迭代所有同时设置了 ``XA_MARK_1`` 和 ``XA_MARK_2`` 的条目，或者迭代所有设置了
0110 ``XA_MARK_0`` 或 ``XA_MARK_2`` 的条目）。如果有用户需要，可以增加这些内容。
0111
0112 分配XArrays
0113 -----------
0114
0115 如果你使用DEFINE_XARRAY_ALLOC()来定义XArray，或者通过向xa_init_flags()传递 ``XA_FLAGS_ALLOC``
0116 来初始化它，XArray会改变以跟踪条目是否被使用。
0117
0118 你可以调用xa_alloc()将条目存储在XArray中一个未使用的索引上。如果你需要从中断上下文中修改数组，你
0119 可以使用xa_alloc_bh()或xa_alloc_irq()，在分配ID的同时禁用中断。
0120
0121 使用xa_store()、xa_cmpxchg()或xa_insert()也将标记该条目为正在分配。与普通的XArray不同，存储 ``NULL``
0122 将标记该条目为正在使用中，就像xa_reserve()。要释放一个条目，请使用xa_erase()（或者xa_release()，
0123 如果你只想释放一个 ``NULL`` 的条目）。
0124
0125 默认情况下，最低的空闲条目从0开始分配。如果你想从1开始分配条目，使用DEFINE_XARRAY_ALLOC1()或
0126 ``XA_FLAGS_ALLOC1`` 会更有效。如果你想分配ID到一个最大值，然后绕回最低的空闲ID，你可以使用
0127 xa_alloc_cyclic()。
0128
0129 你不能在分配的XArray中使用 ``XA_MARK_0`` ，因为这个标记是用来跟踪一个条目是否是空闲的。其他的
0130 标记可以供你使用。
0131
0132 内存分配
0133 --------
0134
0135 xa_store(), xa_cmpxchg(), xa_alloc(), xa_reserve()和xa_insert()函数接受一个gfp_t参数，以
0136 防XArray需要分配内存来存储这个条目。如果该条目被删除，则不需要进行内存分配，指定的GFP标志将被忽
0137 略。
0138
0139 没有内存可供分配是可能的，特别是如果你传递了一组限制性的GFP标志。在这种情况下，这些函数会返回一
0140 个特殊的值，可以用xa_err()把它变成一个错误值。如果你不需要确切地知道哪个错误发生，使用xa_is_err()
0141 会更有效一些。
0142
0143 锁
0144 --
0145
0146 当使用普通API时，你不必担心锁的问题。XArray使用RCU和一个内部自旋锁来同步访问:
0147
0148 不需要锁:
0149 * xa_empty()
0150 * xa_marked()
0151
0152 采取RCU读锁:
0153 * xa_load()
0154 * xa_for_each()
0155 * xa_for_each_start()
0156 * xa_for_each_range()
0157 * xa_find()
0158 * xa_find_after()
0159 * xa_extract()
0160 * xa_get_mark()
0161
0162 内部使用xa_lock:
0163 * xa_store()
0164 * xa_store_bh()
0165 * xa_store_irq()
0166 * xa_insert()
0167 * xa_insert_bh()
0168 * xa_insert_irq()
0169 * xa_erase()
0170 * xa_erase_bh()
0171 * xa_erase_irq()
0172 * xa_cmpxchg()
0173 * xa_cmpxchg_bh()
0174 * xa_cmpxchg_irq()
0175 * xa_store_range()
0176 * xa_alloc()
0177 * xa_alloc_bh()
0178 * xa_alloc_irq()
0179 * xa_reserve()
0180 * xa_reserve_bh()
0181 * xa_reserve_irq()
0182 * xa_destroy()
0183 * xa_set_mark()
0184 * xa_clear_mark()
0185
0186 假设进入时持有xa_lock:
0187 * __xa_store()
0188 * __xa_insert()
0189 * __xa_erase()
0190 * __xa_cmpxchg()
0191 * __xa_alloc()
0192 * __xa_set_mark()
0193 * __xa_clear_mark()
0194
0195 如果你想利用锁来保护你存储在XArray中的数据结构，你可以在调用xa_load()之前调用xa_lock()，然后在
0196 调用xa_unlock()之前对你找到的对象进行一个引用计数。这将防止存储操作在查找对象和增加refcount期间
0197 从数组中删除对象。你也可以使用RCU来避免解除对已释放内存的引用，但对这一点的解释已经超出了本文的范
0198 围。
0199
0200 在修改数组时，XArray不会禁用中断或softirqs。从中断或softirq上下文中读取XArray是安全的，因为RCU锁
0201 提供了足够的保护。
0202
0203 例如，如果你想在进程上下文中存储XArray中的条目，然后在softirq上下文中擦除它们，你可以这样做::
0204
0205 void foo_init(struct foo *foo)
0206 {
0207 xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
0208 }
0209
0210 int foo_store(struct foo *foo, unsigned long index, void *entry)
0211 {
0212 int err;
0213
0214 xa_lock_bh(&foo->array);
0215 err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
0216 if (!err)
0217 foo->count++;
0218 xa_unlock_bh(&foo->array);
0219 return err;
0220 }
0221
0222 /* foo_erase()只在软中断上下文中调用 */
0223 void foo_erase(struct foo *foo, unsigned long index)
0224 {
0225 xa_lock(&foo->array);
0226 __xa_erase(&foo->array, index);
0227 foo->count--;
0228 xa_unlock(&foo->array);
0229 }
0230
0231 如果你要从中断或softirq上下文中修改XArray，你需要使用xa_init_flags()初始化数组，传递
0232 ``XA_FLAGS_LOCK_IRQ`` 或 ``XA_FLAGS_LOCK_BH`` （参数）。
0233
0234 上面的例子还显示了一个常见的模式，即希望在存储端扩展xa_lock的覆盖范围，以保护与数组相关的一些统计
0235 数据。
0236
0237 与中断上下文共享XArray也是可能的，可以在中断处理程序和进程上下文中都使用xa_lock_irqsave()，或者
0238 在进程上下文中使用xa_lock_irq()，在中断处理程序中使用xa_lock()。一些更常见的模式有一些辅助函数，
0239 如xa_store_bh()、xa_store_irq()、xa_erase_bh()、xa_erase_irq()、xa_cmpxchg_bh() 和xa_cmpxchg_irq()。
0240
0241 有时你需要用一个mutex来保护对XArray的访问，因为这个锁在锁的层次结构中位于另一个mutex之上。这并不
0242 意味着你有权使用像__xa_erase()这样的函数而不占用xa_lock；xa_lock是用来进行lockdep验证的，将来也
0243 会用于其他用途。
0244
0245 __xa_set_mark() 和 __xa_clear_mark() 函数也适用于你查找一个条目并想原子化地设置或清除一个标记的
0246 情况。在这种情况下，使用高级API可能更有效，因为它将使你免于走两次树。
0247
0248 高级API
0249 =======
0250
0251 高级API提供了更多的灵活性和更好的性能，但代价是接口可能更难使用，保障措施更少。高级API没有为你加锁，
0252 你需要在修改数组的时候使用xa_lock。在对数组进行只读操作时，你可以选择使用xa_lock或RCU锁。你可以在
0253 同一个数组上混合使用高级和普通操作；事实上，普通API是以高级API的形式实现的。高级API只对具有GPL兼容
0254 许可证的模块可用。
0255
0256 高级API是基于xa_state的。这是一个不透明的数据结构，你使用XA_STATE()宏在堆栈中声明。这个宏初始化了
0257 xa_state，准备开始在XArray上移动。它被用作一个游标来保持在XArray中的位置，并让你把各种操作组合在一
0258 起，而不必每次都从头开始。xa_state的内容受rcu_read_lock()或xas_lock()的保护。如果需要删除保护状态
0259 和树的这些锁中的任何一个，你必须调用xas_pause()以便将来的调用不会依赖于状态中未受保护的部分。
0260
0261 xa_state也被用来存储错误(store errors)。你可以调用xas_error()来检索错误。所有的操作在进行之前都
0262 会检查xa_state是否处于错误状态，所以你没有必要在每次调用之后检查错误；你可以连续进行多次调用，只在
0263 方便的时候检查。目前XArray代码本身产生的错误只有 ``ENOMEM`` 和 ``EINVAL`` ，但它支持任意的错误，
0264 以防你想自己调用xas_set_err()。
0265
0266 如果xa_state持有 ``ENOMEM`` 错误，调用xas_nomem()将尝试使用指定的gfp标志分配更多的内存，并将其缓
0267 存在xa_state中供下一次尝试。这个想法是，你拿着xa_lock，尝试操作，然后放弃锁。该操作试图在持有锁的情
0268 况下分配内存，但它更有可能失败。一旦你放弃了锁，xas_nomem()可以更努力地尝试分配更多内存。如果值得重
0269 试该操作，它将返回 ``true`` （即出现了内存错误，分配了更多的内存）。如果它之前已经分配了内存，并且
0270 该内存没有被使用，也没有错误（或者一些不是 ``ENOMEM`` 的错误），那么它将释放之前分配的内存。
0271
0272 内部条目
0273 --------
0274
0275 XArray为它自己的目的保留了一些条目。这些条目从未通过正常的API暴露出来，但是当使用高级API时，有可能看
0276 到它们。通常，处理它们的最好方法是把它们传递给xas_retry()，如果它返回 ``true`` ，就重试操作。
0277
0278 .. flat-table::
0279 :widths: 1 1 6
0280
0281 * - 名称
0282 - 检测
0283 - 用途
0284
0285 * - Node
0286 - xa_is_node()
0287 - 一个XArray节点。 在使用多索引xa_state时可能是可见的。
0288
0289 * - Sibling
0290 - xa_is_sibling()
0291 - 一个多索引条目的非典型条目。该值表示该节点中的哪个槽有典型条目。
0292
0293 * - Retry
0294 - xa_is_retry()
0295 - 这个条目目前正在被一个拥有xa_lock的线程修改。在这个RCU周期结束时，包含该条目的节点可能会被释放。
0296 你应该从数组的头部重新开始查找。
0297
0298 * - Zero
0299 - xa_is_zero()
0300 - Zero条目通过普通API显示为 ``NULL`` ，但在XArray中占有一个条目，可用于保留索引供将来使用。这是
0301 通过为分配的条目分配XArrays来使用的，这些条目是 ``NULL`` 。
0302
0303 其他内部条目可能会在未来被添加。在可能的情况下，它们将由xas_retry()处理。
0304
0305 附加函数
0306 --------
0307
0308 xas_create_range()函数分配了所有必要的内存来存储一个范围内的每一个条目。如果它不能分配内存，它将在
0309 xa_state中设置ENOMEM。
0310
0311 你可以使用xas_init_marks()将一个条目上的标记重置为默认状态。这通常是清空所有标记，除非XArray被标记
0312 为 ``XA_FLAGS_TRACK_FREE`` ，在这种情况下，标记0被设置，所有其他标记被清空。使用xas_store()将一个
0313 条目替换为另一个条目不会重置该条目上的标记；如果你想重置标记，你应该明确地这样做。
0314
0315 xas_load()会尽可能地将xa_state移动到该条目附近。如果你知道xa_state已经移动到了该条目，并且需要检查
0316 该条目是否有变化，你可以使用xas_reload()来保存一个函数调用。
0317
0318 如果你需要移动到XArray中的不同索引，可以调用xas_set()。这可以将光标重置到树的顶端，这通常会使下一个
0319 操作将光标移动到树中想要的位置。如果你想移动到下一个或上一个索引，调用xas_next()或xas_prev()。设置
0320 索引不会使光标在数组中移动，所以不需要锁，而移动到下一个或上一个索引则需要锁。
0321
0322 你可以使用xas_find()搜索下一个当前条目。这相当于xa_find()和xa_find_after()；如果光标已经移动到了
0323 一个条目，那么它将找到当前引用的条目之后的下一个条目。如果没有，它将返回xa_state索引处的条目。使用
0324 xas_next_entry()而不是xas_find()来移动到下一个当前条目，在大多数情况下会节省一个函数调用，但代价
0325 是发出更多内联代码。
0326
0327 xas_find_marked()函数也是如此。如果xa_state没有被移动过，它将返回xa_state的索引处的条目，如果它
0328 被标记了。否则，它将返回xa_state所引用的条目之后的第一个被标记的条目。xas_next_marked()函数等同
0329 于xas_next_entry()。
0330
0331 当使用xas_for_each()或xas_for_each_marked()在XArray的某个范围内进行迭代时，可能需要暂时停止迭代。
0332 xas_pause()函数的存在就是为了这个目的。在你完成了必要的工作并希望恢复后，xa_state处于适当的状态，在
0333 你最后处理的条目后继续迭代。如果你在迭代时禁用了中断，那么暂停迭代并在每一个 ``XA_CHECK_SCHED`` 条目
0334 中重新启用中断是很好的做法。
0335
0336 xas_get_mark(), xas_set_mark()和xas_clear_mark()函数要求xa_state光标已经被移动到XArray中的适当位
0337 置；如果你在之前调用了xas_pause()或xas_set()，它们将不会有任何作用。
0338
0339 你可以调用xas_set_update()，让XArray每次更新一个节点时都调用一个回调函数。这被页面缓存的workingset
0340 代码用来维护其只包含阴影项的节点列表。
0341
0342 多索引条目
0343 ----------
0344
0345 XArray有能力将多个索引联系在一起，因此对一个索引的操作会影响到所有的索引。例如，存储到任何索引将改变
0346 从任何索引检索的条目的值。在任何索引上设置或清除一个标记，都会在每个被绑在一起的索引上设置或清除该标
0347 记。目前的实现只允许将2的整数倍的范围绑在一起；例如指数64-127可以绑在一起，但2-6不能。这可以节省大量
0348 的内存；例如，将512个条目绑在一起可以节省4kB以上的内存。
0349
0350 你可以通过使用XA_STATE_ORDER()或xas_set_order()，然后调用xas_store()来创建一个多索引条目。用一个
0351 多索引的xa_state调用xas_load()会把xa_state移动到树中的正确位置，但是返回值没有意义，有可能是一个内
0352 部条目或 ``NULL`` ，即使在范围内有一个条目存储。调用xas_find_conflict()将返回该范围内的第一个条目，
0353 如果该范围内没有条目，则返回 ``NULL`` 。xas_for_each_conflict()迭代器将遍历每个与指定范围重叠的条目。
0354
0355 如果xas_load()遇到一个多索引条目，xa_state中的xa_index将不会被改变。当遍历一个XArray或者调用xas_find()
0356 时，如果初始索引在一个多索引条目的中间，它将不会被改变。随后的调用或迭代将把索引移到范围内的第一个索引。
0357 每个条目只会被返回一次，不管它占据了多少个索引。
0358
0359 不支持使用xas_next()或xas_prev()来处理一个多索引的xa_state。在一个多索引的条目上使用这两个函数中的任
0360 何一个都会显示出同级的条目；这些条目应该被调用者跳过。
0361
0362 在一个多索引条目的任何一个索引中存储 ``NULL`` ，将把每个索引的条目设置为 ``NULL`` ，并解除绑定。通过调
0363 用xas_split_alloc()，在没有xa_lock的情况下，可以将一个多索引条目分割成占据较小范围的条目，然后再取锁并
0364 调用xas_split()。
0365
0366 函数和结构体
0367 ============
0368
0369 该API在以下内核代码中:
0370
0371 include/linux/xarray.h
0372
0373 lib/xarray.c
