175ca80e4SYanteng Si.. SPDX-License-Identifier: GPL-2.0+ 275ca80e4SYanteng Si.. include:: ../disclaimer-zh_CN.rst 375ca80e4SYanteng Si 475ca80e4SYanteng Si:Original: Documentation/core-api/xarray.rst 575ca80e4SYanteng Si 675ca80e4SYanteng Si:翻译: 775ca80e4SYanteng Si 875ca80e4SYanteng Si 司延腾 Yanteng Si <siyanteng@loongson.cn> 9*4a6d00a4SBinbin Zhou 周彬彬 Binbin Zhou <zhoubinbin@loongson.cn> 1075ca80e4SYanteng Si 1175ca80e4SYanteng Si:校译: 1275ca80e4SYanteng Si 1375ca80e4SYanteng Si 1475ca80e4SYanteng Si 1575ca80e4SYanteng Si.. _cn_core-api_xarray: 1675ca80e4SYanteng Si 1775ca80e4SYanteng Si====== 1875ca80e4SYanteng SiXArray 1975ca80e4SYanteng Si====== 2075ca80e4SYanteng Si 2175ca80e4SYanteng Si:作者: Matthew Wilcox 2275ca80e4SYanteng Si 2375ca80e4SYanteng Si概览 2475ca80e4SYanteng Si==== 2575ca80e4SYanteng Si 2675ca80e4SYanteng SiXArray是一个抽象的数据类型,它的行为就像一个非常大的指针数组。它满足了许多与哈 2775ca80e4SYanteng Si希或传统可调整大小的数组相同的需求。与哈希不同的是,它允许你以一种高效的缓存方 2875ca80e4SYanteng Si式合理地转到下一个或上一个条目。与可调整大小的数组相比,不需要复制数据或改变MMU 2975ca80e4SYanteng Si的映射来增加数组。与双链表相比,它的内存效率更高,可并行,对缓存更友好。它利用 3075ca80e4SYanteng SiRCU的优势来执行查找而不需要锁定。 3175ca80e4SYanteng Si 3275ca80e4SYanteng Si当使用的索引是密集聚集的时候,XArray的实现是有效的;而哈希对象并使用哈希作为索引 3375ca80e4SYanteng Si将不会有好的表现。XArray对小的索引进行了优化,不过对大的索引仍有良好的性能。如果 3475ca80e4SYanteng Si你的索引可以大于 ``ULONG_MAX`` ,那么XArray就不适合你的数据类型。XArray最重要 3575ca80e4SYanteng Si的用户是页面高速缓存。 3675ca80e4SYanteng Si 3775ca80e4SYanteng Si普通指针可以直接存储在XArray中。它们必须是4字节对齐的,这对任何从kmalloc()和 3875ca80e4SYanteng Sialloc_page()返回的指针来说都是如此。这对任意的用户空间指针和函数指针来说都不是 3975ca80e4SYanteng Si真的。你可以存储指向静态分配对象的指针,只要这些对象的对齐方式至少是4(字节)。 4075ca80e4SYanteng Si 4175ca80e4SYanteng Si你也可以在XArray中存储0到 ``LONG_MAX`` 之间的整数。你必须首先使用xa_mk_value() 4275ca80e4SYanteng Si将其转换为一个条目。当你从XArray中检索一个条目时,你可以通过调用xa_is_value()检 4375ca80e4SYanteng Si查它是否是一个值条目,并通过调用xa_to_value()将它转换回一个整数。 4475ca80e4SYanteng Si 4575ca80e4SYanteng Si一些用户希望对他们存储在XArray中的指针进行标记。你可以调用xa_tag_pointer()来创建 4675ca80e4SYanteng Si一个带有标签的条目,xa_untag_pointer()将一个有标签的条目转回一个无标签的指针, 4775ca80e4SYanteng Sixa_pointer_tag()来检索一个条目的标签。标签指针使用相同的位,用于区分值条目和普通 4875ca80e4SYanteng Si指针,所以你必须决定他们是否要在任何特定的XArray中存储值条目或标签指针。 4975ca80e4SYanteng Si 5075ca80e4SYanteng SiXArray不支持存储IS_ERR()指针,因为有些指针与值条目或内部条目冲突。 5175ca80e4SYanteng Si 5275ca80e4SYanteng SiXArray的一个不寻常的特点是能够创建占据一系列索引的条目。一旦存储到其中,查询该范围 5375ca80e4SYanteng Si内的任何索引将返回与查询该范围内任何其他索引相同的条目。存储到任何索引都会存储所有 5475ca80e4SYanteng Si的索引条目。多索引条目可以明确地分割成更小的条目,或者将其存储 ``NULL`` 到任何条目中 5575ca80e4SYanteng Si都会使XArray忘记范围。 5675ca80e4SYanteng Si 5775ca80e4SYanteng Si普通API 5875ca80e4SYanteng Si======= 5975ca80e4SYanteng Si 6075ca80e4SYanteng Si首先初始化一个XArray,对于静态分配的XArray可以用DEFINE_XARRAY(),对于动态分配的 6175ca80e4SYanteng SiXArray可以用xa_init()。一个新初始化的XArray在每个索引处都包含一个 ``NULL`` 指针。 6275ca80e4SYanteng Si 6375ca80e4SYanteng Si然后你可以用xa_store()来设置条目,用xa_load()来获取条目。xa_store将用新的条目覆盖任 6475ca80e4SYanteng Si何条目,并返回存储在该索引的上一个条目。你可以使用xa_erase()来代替调用xa_store()的 6575ca80e4SYanteng Si``NULL`` 条目。一个从未被存储过的条目、一个被擦除的条目和一个最近被存储过 ``NULL`` 的 6675ca80e4SYanteng Si条目之间没有区别。 6775ca80e4SYanteng Si 6875ca80e4SYanteng Si你可以通过使用xa_cmpxchg()有条件地替换一个索引中的条目。和cmpxchg()一样,它只有在该索 6975ca80e4SYanteng Si引的条目有 ‘旧‘ 值时才会成功。它也会返回该索引上的条目;如果它返回与传递的 ‘旧‘ 相同的条 7075ca80e4SYanteng Si目,那么xa_cmpxchg()就成功了。 7175ca80e4SYanteng Si 7275ca80e4SYanteng Si如果你只想在某个索引的当前条目为 ``NULL`` 时将一个新条目存储到该索引,你可以使用xa_insert(), 7375ca80e4SYanteng Si如果该条目不是空的,则返回 ``-EBUSY`` 。 7475ca80e4SYanteng Si 7575ca80e4SYanteng Si你可以通过调用xa_extract()将条目从XArray中复制到一个普通数组中。或者你可以通过调用 7675ca80e4SYanteng Sixa_for_each()、xa_for_each_start()或xa_for_each_range()来遍历XArray中的现有条目。你 7775ca80e4SYanteng Si可能更喜欢使用xa_find()或xa_find_after()来移动到XArray中的下一个当前条目。 7875ca80e4SYanteng Si 7975ca80e4SYanteng Si调用xa_store_range()可以在一个索引范围内存储同一个条目。如果你这样做,其他的一些操作将以 8075ca80e4SYanteng Si一种稍微奇怪的方式进行。例如,在一个索引上标记条目可能会导致该条目在一些,但不是所有其他索 8175ca80e4SYanteng Si引上被标记。储存到一个索引中可能会导致由一些,但不是所有其他索引检索的条目发生变化。 8275ca80e4SYanteng Si 8375ca80e4SYanteng Si有时你需要确保对xa_store()的后续调用将不需要分配内存。xa_reserve()函数将在指定索引处存储 8475ca80e4SYanteng Si一个保留条目。普通API的用户将看到这个条目包含 ``NULL`` 。如果你不需要使用保留的条目,你可 8575ca80e4SYanteng Si以调用xa_release()来删除这个未使用的条目。如果在此期间有其他用户存储到该条目,xa_release() 8675ca80e4SYanteng Si将不做任何事情;相反,如果你想让该条目变成 ``NULL`` ,你应该使用xa_erase()。在一个保留的条 8775ca80e4SYanteng Si目上使用xa_insert()将会失败。 8875ca80e4SYanteng Si 8975ca80e4SYanteng Si如果数组中的所有条目都是 ``NULL`` ,xa_empty()函数将返回 ``true`` 。 9075ca80e4SYanteng Si 9175ca80e4SYanteng Si最后,你可以通过调用xa_destroy()删除XArray中的所有条目。如果XArray的条目是指针,你可能希望 9275ca80e4SYanteng Si先释放这些条目。你可以通过使用xa_for_each()迭代器遍历XArray中所有存在的条目来实现这一目的。 9375ca80e4SYanteng Si 9475ca80e4SYanteng Si搜索标记 9575ca80e4SYanteng Si-------- 9675ca80e4SYanteng Si 9775ca80e4SYanteng Si数组中的每个条目都有三个与之相关的位,称为标记。每个标记可以独立于其他标记被设置或清除。你可以 9875ca80e4SYanteng Si通过使用xa_for_each_marked()迭代器来迭代有标记的条目。 9975ca80e4SYanteng Si 10075ca80e4SYanteng Si你可以通过使用xa_get_mark()来查询某个条目是否设置了标记。如果该条目不是 ``NULL`` ,你可以通过 10175ca80e4SYanteng Si使用xa_set_mark()来设置一个标记,并通过调用xa_clear_mark()来删除条目上的标记。你可以通过调用 10275ca80e4SYanteng Sixa_marked()来询问XArray中的任何条目是否有一个特定的标记被设置。从XArray中删除一个条目会导致与 10375ca80e4SYanteng Si该条目相关的所有标记被清除。 10475ca80e4SYanteng Si 10575ca80e4SYanteng Si在一个多索引条目的任何索引上设置或清除标记将影响该条目所涵盖的所有索引。查询任何索引上的标记将返 10675ca80e4SYanteng Si回相同的结果。 10775ca80e4SYanteng Si 10875ca80e4SYanteng Si没有办法对没有标记的条目进行迭代;数据结构不允许有效地实现这一点。目前没有迭代器来搜索比特的逻辑 10975ca80e4SYanteng Si组合(例如迭代所有同时设置了 ``XA_MARK_1`` 和 ``XA_MARK_2`` 的条目,或者迭代所有设置了 11075ca80e4SYanteng Si``XA_MARK_0`` 或 ``XA_MARK_2`` 的条目)。如果有用户需要,可以增加这些内容。 11175ca80e4SYanteng Si 11275ca80e4SYanteng Si分配XArrays 11375ca80e4SYanteng Si----------- 11475ca80e4SYanteng Si 11575ca80e4SYanteng Si如果你使用DEFINE_XARRAY_ALLOC()来定义XArray,或者通过向xa_init_flags()传递 ``XA_FLAGS_ALLOC`` 11675ca80e4SYanteng Si来初始化它,XArray会改变以跟踪条目是否被使用。 11775ca80e4SYanteng Si 11875ca80e4SYanteng Si你可以调用xa_alloc()将条目存储在XArray中一个未使用的索引上。如果你需要从中断上下文中修改数组,你 11975ca80e4SYanteng Si可以使用xa_alloc_bh()或xa_alloc_irq(),在分配ID的同时禁用中断。 12075ca80e4SYanteng Si 12175ca80e4SYanteng Si使用xa_store()、xa_cmpxchg()或xa_insert()也将标记该条目为正在分配。与普通的XArray不同,存储 ``NULL`` 12275ca80e4SYanteng Si将标记该条目为正在使用中,就像xa_reserve()。要释放一个条目,请使用xa_erase()(或者xa_release(), 12375ca80e4SYanteng Si如果你只想释放一个 ``NULL`` 的条目)。 12475ca80e4SYanteng Si 12575ca80e4SYanteng Si默认情况下,最低的空闲条目从0开始分配。如果你想从1开始分配条目,使用DEFINE_XARRAY_ALLOC1()或 12675ca80e4SYanteng Si``XA_FLAGS_ALLOC1`` 会更有效。如果你想分配ID到一个最大值,然后绕回最低的空闲ID,你可以使用 12775ca80e4SYanteng Sixa_alloc_cyclic()。 12875ca80e4SYanteng Si 12975ca80e4SYanteng Si你不能在分配的XArray中使用 ``XA_MARK_0`` ,因为这个标记是用来跟踪一个条目是否是空闲的。其他的 13075ca80e4SYanteng Si标记可以供你使用。 13175ca80e4SYanteng Si 13275ca80e4SYanteng Si内存分配 13375ca80e4SYanteng Si-------- 13475ca80e4SYanteng Si 13575ca80e4SYanteng Sixa_store(), xa_cmpxchg(), xa_alloc(), xa_reserve()和xa_insert()函数接受一个gfp_t参数,以 13675ca80e4SYanteng Si防XArray需要分配内存来存储这个条目。如果该条目被删除,则不需要进行内存分配,指定的GFP标志将被忽 13775ca80e4SYanteng Si略。 13875ca80e4SYanteng Si 13975ca80e4SYanteng Si没有内存可供分配是可能的,特别是如果你传递了一组限制性的GFP标志。在这种情况下,这些函数会返回一 14075ca80e4SYanteng Si个特殊的值,可以用xa_err()把它变成一个错误值。如果你不需要确切地知道哪个错误发生,使用xa_is_err() 14175ca80e4SYanteng Si会更有效一些。 14275ca80e4SYanteng Si 14375ca80e4SYanteng Si锁 14475ca80e4SYanteng Si-- 14575ca80e4SYanteng Si 14675ca80e4SYanteng Si当使用普通API时,你不必担心锁的问题。XArray使用RCU和一个内部自旋锁来同步访问: 14775ca80e4SYanteng Si 14875ca80e4SYanteng Si不需要锁: 14975ca80e4SYanteng Si * xa_empty() 15075ca80e4SYanteng Si * xa_marked() 15175ca80e4SYanteng Si 15275ca80e4SYanteng Si采取RCU读锁: 15375ca80e4SYanteng Si * xa_load() 15475ca80e4SYanteng Si * xa_for_each() 15575ca80e4SYanteng Si * xa_for_each_start() 15675ca80e4SYanteng Si * xa_for_each_range() 15775ca80e4SYanteng Si * xa_find() 15875ca80e4SYanteng Si * xa_find_after() 15975ca80e4SYanteng Si * xa_extract() 16075ca80e4SYanteng Si * xa_get_mark() 16175ca80e4SYanteng Si 16275ca80e4SYanteng Si内部使用xa_lock: 16375ca80e4SYanteng Si * xa_store() 16475ca80e4SYanteng Si * xa_store_bh() 16575ca80e4SYanteng Si * xa_store_irq() 16675ca80e4SYanteng Si * xa_insert() 16775ca80e4SYanteng Si * xa_insert_bh() 16875ca80e4SYanteng Si * xa_insert_irq() 16975ca80e4SYanteng Si * xa_erase() 17075ca80e4SYanteng Si * xa_erase_bh() 17175ca80e4SYanteng Si * xa_erase_irq() 17275ca80e4SYanteng Si * xa_cmpxchg() 17375ca80e4SYanteng Si * xa_cmpxchg_bh() 17475ca80e4SYanteng Si * xa_cmpxchg_irq() 17575ca80e4SYanteng Si * xa_store_range() 17675ca80e4SYanteng Si * xa_alloc() 17775ca80e4SYanteng Si * xa_alloc_bh() 17875ca80e4SYanteng Si * xa_alloc_irq() 17975ca80e4SYanteng Si * xa_reserve() 18075ca80e4SYanteng Si * xa_reserve_bh() 18175ca80e4SYanteng Si * xa_reserve_irq() 18275ca80e4SYanteng Si * xa_destroy() 18375ca80e4SYanteng Si * xa_set_mark() 18475ca80e4SYanteng Si * xa_clear_mark() 18575ca80e4SYanteng Si 18675ca80e4SYanteng Si假设进入时持有xa_lock: 18775ca80e4SYanteng Si * __xa_store() 18875ca80e4SYanteng Si * __xa_insert() 18975ca80e4SYanteng Si * __xa_erase() 19075ca80e4SYanteng Si * __xa_cmpxchg() 19175ca80e4SYanteng Si * __xa_alloc() 19275ca80e4SYanteng Si * __xa_set_mark() 19375ca80e4SYanteng Si * __xa_clear_mark() 19475ca80e4SYanteng Si 19575ca80e4SYanteng Si如果你想利用锁来保护你存储在XArray中的数据结构,你可以在调用xa_load()之前调用xa_lock(),然后在 19675ca80e4SYanteng Si调用xa_unlock()之前对你找到的对象进行一个引用计数。这将防止存储操作在查找对象和增加refcount期间 19775ca80e4SYanteng Si从数组中删除对象。你也可以使用RCU来避免解除对已释放内存的引用,但对这一点的解释已经超出了本文的范 19875ca80e4SYanteng Si围。 19975ca80e4SYanteng Si 20075ca80e4SYanteng Si在修改数组时,XArray不会禁用中断或softirqs。从中断或softirq上下文中读取XArray是安全的,因为RCU锁 20175ca80e4SYanteng Si提供了足够的保护。 20275ca80e4SYanteng Si 20375ca80e4SYanteng Si例如,如果你想在进程上下文中存储XArray中的条目,然后在softirq上下文中擦除它们,你可以这样做:: 20475ca80e4SYanteng Si 20575ca80e4SYanteng Si void foo_init(struct foo *foo) 20675ca80e4SYanteng Si { 20775ca80e4SYanteng Si xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH); 20875ca80e4SYanteng Si } 20975ca80e4SYanteng Si 21075ca80e4SYanteng Si int foo_store(struct foo *foo, unsigned long index, void *entry) 21175ca80e4SYanteng Si { 21275ca80e4SYanteng Si int err; 21375ca80e4SYanteng Si 21475ca80e4SYanteng Si xa_lock_bh(&foo->array); 21575ca80e4SYanteng Si err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL)); 21675ca80e4SYanteng Si if (!err) 21775ca80e4SYanteng Si foo->count++; 21875ca80e4SYanteng Si xa_unlock_bh(&foo->array); 21975ca80e4SYanteng Si return err; 22075ca80e4SYanteng Si } 22175ca80e4SYanteng Si 22275ca80e4SYanteng Si /* foo_erase()只在软中断上下文中调用 */ 22375ca80e4SYanteng Si void foo_erase(struct foo *foo, unsigned long index) 22475ca80e4SYanteng Si { 22575ca80e4SYanteng Si xa_lock(&foo->array); 22675ca80e4SYanteng Si __xa_erase(&foo->array, index); 22775ca80e4SYanteng Si foo->count--; 22875ca80e4SYanteng Si xa_unlock(&foo->array); 22975ca80e4SYanteng Si } 23075ca80e4SYanteng Si 23175ca80e4SYanteng Si如果你要从中断或softirq上下文中修改XArray,你需要使用xa_init_flags()初始化数组,传递 23275ca80e4SYanteng Si``XA_FLAGS_LOCK_IRQ`` 或 ``XA_FLAGS_LOCK_BH`` (参数)。 23375ca80e4SYanteng Si 23475ca80e4SYanteng Si上面的例子还显示了一个常见的模式,即希望在存储端扩展xa_lock的覆盖范围,以保护与数组相关的一些统计 23575ca80e4SYanteng Si数据。 23675ca80e4SYanteng Si 23775ca80e4SYanteng Si与中断上下文共享XArray也是可能的,可以在中断处理程序和进程上下文中都使用xa_lock_irqsave(),或者 23875ca80e4SYanteng Si在进程上下文中使用xa_lock_irq(),在中断处理程序中使用xa_lock()。一些更常见的模式有一些辅助函数, 23975ca80e4SYanteng Si如xa_store_bh()、xa_store_irq()、xa_erase_bh()、xa_erase_irq()、xa_cmpxchg_bh() 和xa_cmpxchg_irq()。 24075ca80e4SYanteng Si 24175ca80e4SYanteng Si有时你需要用一个mutex来保护对XArray的访问,因为这个锁在锁的层次结构中位于另一个mutex之上。这并不 24275ca80e4SYanteng Si意味着你有权使用像__xa_erase()这样的函数而不占用xa_lock;xa_lock是用来进行lockdep验证的,将来也 24375ca80e4SYanteng Si会用于其他用途。 24475ca80e4SYanteng Si 24575ca80e4SYanteng Si__xa_set_mark() 和 __xa_clear_mark() 函数也适用于你查找一个条目并想原子化地设置或清除一个标记的 24675ca80e4SYanteng Si情况。在这种情况下,使用高级API可能更有效,因为它将使你免于走两次树。 24775ca80e4SYanteng Si 24875ca80e4SYanteng Si高级API 24975ca80e4SYanteng Si======= 25075ca80e4SYanteng Si 25175ca80e4SYanteng Si高级API提供了更多的灵活性和更好的性能,但代价是接口可能更难使用,保障措施更少。高级API没有为你加锁, 25275ca80e4SYanteng Si你需要在修改数组的时候使用xa_lock。在对数组进行只读操作时,你可以选择使用xa_lock或RCU锁。你可以在 25375ca80e4SYanteng Si同一个数组上混合使用高级和普通操作;事实上,普通API是以高级API的形式实现的。高级API只对具有GPL兼容 25475ca80e4SYanteng Si许可证的模块可用。 25575ca80e4SYanteng Si 25675ca80e4SYanteng Si高级API是基于xa_state的。这是一个不透明的数据结构,你使用XA_STATE()宏在堆栈中声明。这个宏初始化了 25775ca80e4SYanteng Sixa_state,准备开始在XArray上移动。它被用作一个游标来保持在XArray中的位置,并让你把各种操作组合在一 258*4a6d00a4SBinbin Zhou起,而不必每次都从头开始。xa_state的内容受rcu_read_lock()或xas_lock()的保护。如果需要删除保护状态 259*4a6d00a4SBinbin Zhou和树的这些锁中的任何一个,你必须调用xas_pause()以便将来的调用不会依赖于状态中未受保护的部分。 26075ca80e4SYanteng Si 26175ca80e4SYanteng Sixa_state也被用来存储错误(store errors)。你可以调用xas_error()来检索错误。所有的操作在进行之前都 26275ca80e4SYanteng Si会检查xa_state是否处于错误状态,所以你没有必要在每次调用之后检查错误;你可以连续进行多次调用,只在 26375ca80e4SYanteng Si方便的时候检查。目前XArray代码本身产生的错误只有 ``ENOMEM`` 和 ``EINVAL`` ,但它支持任意的错误, 26475ca80e4SYanteng Si以防你想自己调用xas_set_err()。 26575ca80e4SYanteng Si 26675ca80e4SYanteng Si如果xa_state持有 ``ENOMEM`` 错误,调用xas_nomem()将尝试使用指定的gfp标志分配更多的内存,并将其缓 26775ca80e4SYanteng Si存在xa_state中供下一次尝试。这个想法是,你拿着xa_lock,尝试操作,然后放弃锁。该操作试图在持有锁的情 26875ca80e4SYanteng Si况下分配内存,但它更有可能失败。一旦你放弃了锁,xas_nomem()可以更努力地尝试分配更多内存。如果值得重 26975ca80e4SYanteng Si试该操作,它将返回 ``true`` (即出现了内存错误,分配了更多的内存)。如果它之前已经分配了内存,并且 27075ca80e4SYanteng Si该内存没有被使用,也没有错误(或者一些不是 ``ENOMEM`` 的错误),那么它将释放之前分配的内存。 27175ca80e4SYanteng Si 27275ca80e4SYanteng Si内部条目 27375ca80e4SYanteng Si-------- 27475ca80e4SYanteng Si 27575ca80e4SYanteng SiXArray为它自己的目的保留了一些条目。这些条目从未通过正常的API暴露出来,但是当使用高级API时,有可能看 27675ca80e4SYanteng Si到它们。通常,处理它们的最好方法是把它们传递给xas_retry(),如果它返回 ``true`` ,就重试操作。 27775ca80e4SYanteng Si 27875ca80e4SYanteng Si.. flat-table:: 27975ca80e4SYanteng Si :widths: 1 1 6 28075ca80e4SYanteng Si 28175ca80e4SYanteng Si * - 名称 28275ca80e4SYanteng Si - 检测 28375ca80e4SYanteng Si - 用途 28475ca80e4SYanteng Si 28575ca80e4SYanteng Si * - Node 28675ca80e4SYanteng Si - xa_is_node() 28775ca80e4SYanteng Si - 一个XArray节点。 在使用多索引xa_state时可能是可见的。 28875ca80e4SYanteng Si 28975ca80e4SYanteng Si * - Sibling 29075ca80e4SYanteng Si - xa_is_sibling() 29175ca80e4SYanteng Si - 一个多索引条目的非典型条目。该值表示该节点中的哪个槽有典型条目。 29275ca80e4SYanteng Si 29375ca80e4SYanteng Si * - Retry 29475ca80e4SYanteng Si - xa_is_retry() 29575ca80e4SYanteng Si - 这个条目目前正在被一个拥有xa_lock的线程修改。在这个RCU周期结束时,包含该条目的节点可能会被释放。 29675ca80e4SYanteng Si 你应该从数组的头部重新开始查找。 29775ca80e4SYanteng Si 29875ca80e4SYanteng Si * - Zero 29975ca80e4SYanteng Si - xa_is_zero() 30075ca80e4SYanteng Si - Zero条目通过普通API显示为 ``NULL`` ,但在XArray中占有一个条目,可用于保留索引供将来使用。这是 30175ca80e4SYanteng Si 通过为分配的条目分配XArrays来使用的,这些条目是 ``NULL`` 。 30275ca80e4SYanteng Si 30375ca80e4SYanteng Si其他内部条目可能会在未来被添加。在可能的情况下,它们将由xas_retry()处理。 30475ca80e4SYanteng Si 30575ca80e4SYanteng Si附加函数 30675ca80e4SYanteng Si-------- 30775ca80e4SYanteng Si 30875ca80e4SYanteng Sixas_create_range()函数分配了所有必要的内存来存储一个范围内的每一个条目。如果它不能分配内存,它将在 30975ca80e4SYanteng Sixa_state中设置ENOMEM。 31075ca80e4SYanteng Si 31175ca80e4SYanteng Si你可以使用xas_init_marks()将一个条目上的标记重置为默认状态。这通常是清空所有标记,除非XArray被标记 31275ca80e4SYanteng Si为 ``XA_FLAGS_TRACK_FREE`` ,在这种情况下,标记0被设置,所有其他标记被清空。使用xas_store()将一个 31375ca80e4SYanteng Si条目替换为另一个条目不会重置该条目上的标记;如果你想重置标记,你应该明确地这样做。 31475ca80e4SYanteng Si 31575ca80e4SYanteng Sixas_load()会尽可能地将xa_state移动到该条目附近。如果你知道xa_state已经移动到了该条目,并且需要检查 31675ca80e4SYanteng Si该条目是否有变化,你可以使用xas_reload()来保存一个函数调用。 31775ca80e4SYanteng Si 31875ca80e4SYanteng Si如果你需要移动到XArray中的不同索引,可以调用xas_set()。这可以将光标重置到树的顶端,这通常会使下一个 31975ca80e4SYanteng Si操作将光标移动到树中想要的位置。如果你想移动到下一个或上一个索引,调用xas_next()或xas_prev()。设置 32075ca80e4SYanteng Si索引不会使光标在数组中移动,所以不需要锁,而移动到下一个或上一个索引则需要锁。 32175ca80e4SYanteng Si 32275ca80e4SYanteng Si你可以使用xas_find()搜索下一个当前条目。这相当于xa_find()和xa_find_after();如果光标已经移动到了 32375ca80e4SYanteng Si一个条目,那么它将找到当前引用的条目之后的下一个条目。如果没有,它将返回xa_state索引处的条目。使用 32475ca80e4SYanteng Sixas_next_entry()而不是xas_find()来移动到下一个当前条目,在大多数情况下会节省一个函数调用,但代价 32575ca80e4SYanteng Si是发出更多内联代码。 32675ca80e4SYanteng Si 32775ca80e4SYanteng Sixas_find_marked()函数也是如此。如果xa_state没有被移动过,它将返回xa_state的索引处的条目,如果它 32875ca80e4SYanteng Si被标记了。否则,它将返回xa_state所引用的条目之后的第一个被标记的条目。xas_next_marked()函数等同 32975ca80e4SYanteng Si于xas_next_entry()。 33075ca80e4SYanteng Si 33175ca80e4SYanteng Si当使用xas_for_each()或xas_for_each_marked()在XArray的某个范围内进行迭代时,可能需要暂时停止迭代。 33275ca80e4SYanteng Sixas_pause()函数的存在就是为了这个目的。在你完成了必要的工作并希望恢复后,xa_state处于适当的状态,在 33375ca80e4SYanteng Si你最后处理的条目后继续迭代。如果你在迭代时禁用了中断,那么暂停迭代并在每一个 ``XA_CHECK_SCHED`` 条目 33475ca80e4SYanteng Si中重新启用中断是很好的做法。 33575ca80e4SYanteng Si 33675ca80e4SYanteng Sixas_get_mark(), xas_set_mark()和xas_clear_mark()函数要求xa_state光标已经被移动到XArray中的适当位 33775ca80e4SYanteng Si置;如果你在之前调用了xas_pause()或xas_set(),它们将不会有任何作用。 33875ca80e4SYanteng Si 33975ca80e4SYanteng Si你可以调用xas_set_update(),让XArray每次更新一个节点时都调用一个回调函数。这被页面缓存的workingset 34075ca80e4SYanteng Si代码用来维护其只包含阴影项的节点列表。 34175ca80e4SYanteng Si 34275ca80e4SYanteng Si多索引条目 34375ca80e4SYanteng Si---------- 34475ca80e4SYanteng Si 34575ca80e4SYanteng SiXArray有能力将多个索引联系在一起,因此对一个索引的操作会影响到所有的索引。例如,存储到任何索引将改变 34675ca80e4SYanteng Si从任何索引检索的条目的值。在任何索引上设置或清除一个标记,都会在每个被绑在一起的索引上设置或清除该标 34775ca80e4SYanteng Si记。目前的实现只允许将2的整数倍的范围绑在一起;例如指数64-127可以绑在一起,但2-6不能。这可以节省大量 34875ca80e4SYanteng Si的内存;例如,将512个条目绑在一起可以节省4kB以上的内存。 34975ca80e4SYanteng Si 35075ca80e4SYanteng Si你可以通过使用XA_STATE_ORDER()或xas_set_order(),然后调用xas_store()来创建一个多索引条目。用一个 35175ca80e4SYanteng Si多索引的xa_state调用xas_load()会把xa_state移动到树中的正确位置,但是返回值没有意义,有可能是一个内 35275ca80e4SYanteng Si部条目或 ``NULL`` ,即使在范围内有一个条目存储。调用xas_find_conflict()将返回该范围内的第一个条目, 35375ca80e4SYanteng Si如果该范围内没有条目,则返回 ``NULL`` 。xas_for_each_conflict()迭代器将遍历每个与指定范围重叠的条目。 35475ca80e4SYanteng Si 35575ca80e4SYanteng Si如果xas_load()遇到一个多索引条目,xa_state中的xa_index将不会被改变。当遍历一个XArray或者调用xas_find() 35675ca80e4SYanteng Si时,如果初始索引在一个多索引条目的中间,它将不会被改变。随后的调用或迭代将把索引移到范围内的第一个索引。 35775ca80e4SYanteng Si每个条目只会被返回一次,不管它占据了多少个索引。 35875ca80e4SYanteng Si 35975ca80e4SYanteng Si不支持使用xas_next()或xas_prev()来处理一个多索引的xa_state。在一个多索引的条目上使用这两个函数中的任 36075ca80e4SYanteng Si何一个都会显示出同级的条目;这些条目应该被调用者跳过。 36175ca80e4SYanteng Si 36275ca80e4SYanteng Si在一个多索引条目的任何一个索引中存储 ``NULL`` ,将把每个索引的条目设置为 ``NULL`` ,并解除绑定。通过调 36375ca80e4SYanteng Si用xas_split_alloc(),在没有xa_lock的情况下,可以将一个多索引条目分割成占据较小范围的条目,然后再取锁并 36475ca80e4SYanteng Si调用xas_split()。 36575ca80e4SYanteng Si 36675ca80e4SYanteng Si函数和结构体 36775ca80e4SYanteng Si============ 36875ca80e4SYanteng Si 36975ca80e4SYanteng Si该API在以下内核代码中: 37075ca80e4SYanteng Si 37175ca80e4SYanteng Siinclude/linux/xarray.h 37275ca80e4SYanteng Si 37375ca80e4SYanteng Silib/xarray.c 374