通用关联数组实现¶
概述¶
此关联数组实现是一个对象容器，具有以下特性：
对象是不透明指针。实现不关心它们指向何处（如果存在）或指向什么（如果存在）。
注意
对象指针的最低有效位必须为零。
对象不需要包含供数组使用的链接块。这允许一个对象同时位于多个数组中。相反，数组由指向对象的元数据块构成。
对象需要索引键才能在数组中定位它们。
索引键必须是唯一的。插入一个键与数组中已有的对象相同的对象将替换旧对象。
索引键可以是任何长度，也可以是不同长度。
索引键应尽早编码其长度，在因长度引起任何变化之前。
索引键可以包含哈希值，以便将对象分散到整个数组中。
数组可以被遍历。对象不一定按键序出现。
只要迭代器持有 RCU 读锁，就可以在数组被修改的同时对其进行迭代。但请注意，在这种情况下，某些对象可能会被多次看到。如果这是一个问题，迭代器应锁定以防止修改。然而，除非被删除，否则不会遗漏对象。
数组中的对象可以通过其索引键进行查找。
只要执行查找的线程持有 RCU 读锁，就可以在数组被修改的同时查找对象。
该实现内部使用一个由 16 指针节点组成的树，这些节点在每个级别上都通过索引键中的半字节（nibbles）进行索引，方式与基数树相同。为了提高内存效率，可以放置快捷方式以跳过原本将是一系列单占用节点的结构。此外，节点将叶对象指针打包到节点中的空闲空间中，而不是创建额外的分支，直到需要将对象添加到已满的节点时。
公共 API¶
公共 API 位于 <linux/assoc_array.h> 中。关联数组基于以下结构：
struct assoc_array {
...
};
通过启用 CONFIG_ASSOCIATIVE_ARRAY 来选择代码：
./script/config -e ASSOCIATIVE_ARRAY
编辑脚本¶
插入和删除函数会生成一个“编辑脚本”，该脚本稍后可以应用以实现更改，而不会有 ENOMEM 风险。这会保留将安装在内部树中的预分配元数据块，并跟踪在应用脚本时将从树中删除的元数据块。
这还用于在脚本应用后跟踪已失效的块和对象，以便稍后释放它们。释放操作在 RCU 宽限期过后进行，从而允许访问函数在 RCU 读锁下继续执行。
脚本以 API 外部的指针形式出现，类型为：
struct assoc_array_edit;
有两个函数用于处理脚本：
应用编辑脚本
void assoc_array_apply_edit(struct assoc_array_edit *edit);
这将执行编辑功能，插入各种写屏障以允许在 RCU 读锁下的访问继续。编辑脚本随后将被传递给 call_rcu() 以释放它及其指向的任何已失效内容。
取消编辑脚本
void assoc_array_cancel_edit(struct assoc_array_edit *edit);
这会立即释放编辑脚本和所有预分配的内存。如果这是用于插入的，则新对象不会由该函数释放，而是必须由调用者释放。
这些函数保证不会失败。
操作表¶
各种函数接受一个操作表：
struct assoc_array_ops {
...
};
这指向许多方法，所有这些方法都需要提供：
从调用者数据中获取索引键块
unsigned long (*get_key_chunk)(const void *index_key, int level);
这应该返回从 level 参数给定的位位置开始的调用者提供的索引键块。level 参数将是 ASSOC_ARRAY_KEY_CHUNK_SIZE 的倍数，并且函数应返回 ASSOC_ARRAY_KEY_CHUNK_SIZE bits。不可能出错。
获取对象索引键的块
unsigned long (*get_object_key_chunk)(const void *object, int level);
与前一个函数相同，但从数组中的对象而不是从调用者提供的索引键中获取数据。
查看这是否是我们要查找的对象
bool (*compare_object)(const void *object, const void *index_key);
将对象与索引键进行比较，如果匹配则返回 true，否则返回 false。
比较两个对象的索引键差异
int (*diff_objects)(const void *object, const void *index_key);
返回指定对象的索引键与给定索引键不同的位位置，如果它们相同则返回 -1。
释放对象
void (*free_object)(void *object);
释放指定的对象。请注意，这可能在调用 assoc_array_apply_edit() 之后的一个 RCU 宽限期内被调用，因此在模块卸载时可能需要 synchronize_rcu()。
操作函数¶
有许多用于操作关联数组的函数：
初始化关联数组
void assoc_array_init(struct assoc_array *array);
这会初始化关联数组的基本结构。它不会失败。
在关联数组中插入/替换对象
struct assoc_array_edit * assoc_array_insert(struct assoc_array *array, const struct assoc_array_ops *ops, const void *index_key, void *object);
这会将给定对象插入数组。请注意，指针的最低有效位必须为零，因为它在内部用于类型标记指针。
如果该键已存在对象，则它将被新对象替换，旧对象将自动释放。
index_key 参数应包含索引键信息，并在调用 ops 表中的方法时传递给它们。
此函数不修改数组本身，而是返回一个必须应用的编辑脚本。如果发生内存不足错误，则返回 -ENOMEM。
调用者应独占锁定以防止数组的其他修改者。
从关联数组中删除对象
struct assoc_array_edit * assoc_array_delete(struct assoc_array *array, const struct assoc_array_ops *ops, const void *index_key);
这会从数组中删除与指定数据匹配的对象。
index_key 参数应包含索引键信息，并在调用 ops 表中的方法时传递给它们。
此函数不修改数组本身，而是返回一个必须应用的编辑脚本。如果发生内存不足错误，则返回 -ENOMEM。如果在数组中未找到指定对象，则返回 NULL。
调用者应独占锁定以防止数组的其他修改者。
从关联数组中删除所有对象
struct assoc_array_edit * assoc_array_clear(struct assoc_array *array, const struct assoc_array_ops *ops);
这会删除关联数组中的所有对象，使其完全为空。
此函数不修改数组本身，而是返回一个必须应用的编辑脚本。如果发生内存不足错误，则返回 -ENOMEM。
调用者应独占锁定以防止数组的其他修改者。
销毁关联数组，删除所有对象
void assoc_array_destroy(struct assoc_array *array, const struct assoc_array_ops *ops);
这会销毁关联数组的内容并使其完全为空。不允许其他线程在 RCU 读锁下遍历数组的同时此函数正在销毁它，因为内存释放时没有执行 RCU 延迟——这需要分配内存。
调用者应独占锁定以防止数组的其他修改者和访问器。
垃圾回收关联数组
int assoc_array_gc(struct assoc_array *array, const struct assoc_array_ops *ops, bool (*iterator)(void *object, void *iterator_data), void *iterator_data);
这会迭代关联数组中的对象，并将每个对象传递给 iterator()。如果 iterator() 返回 true，则保留该对象。如果返回 false，则该对象将被释放。如果 iterator() 函数返回 true，它必须在返回之前对对象执行任何适当的引用计数增加。
如果可能，内部树将在迭代过程中被压缩，以减少其中的节点数量。
iterator_data 直接传递给 iterator()，否则函数会忽略它。
如果成功，函数将返回 0；如果内存不足，则返回 -ENOMEM。
在此函数执行期间，其他线程可能在 RCU 读锁下遍历或搜索数组。调用者应独占锁定以防止数组的其他修改者。
访问函数¶
有两个函数用于访问关联数组：
遍历关联数组中的所有对象
int assoc_array_iterate(const struct assoc_array *array, int (*iterator)(const void *object, void *iterator_data), void *iterator_data);
这会将数组中的每个对象传递给迭代器回调函数。iterator_data 是该函数的私有数据。
只要持有 RCU 读锁，就可以在数组被修改的同时对其进行此操作。在这种情况下，迭代函数可能会两次看到某些对象。如果这是一个问题，则应锁定修改。但是，迭代算法不应遗漏任何对象。
如果数组中没有对象，函数将返回 0；否则，它将返回最后一次调用迭代函数的结果。如果对迭代函数的任何调用导致非零返回，则迭代会立即停止。
在关联数组中查找对象
void *assoc_array_find(const struct assoc_array *array, const struct assoc_array_ops *ops, const void *index_key);
这会直接通过数组的内部树，找到由索引键指定的对象。
只要持有 RCU 读锁，就可以在数组被修改的同时对其进行此操作。
如果找到对象，函数将返回该对象（并将 *\_type 设置为对象类型），如果未找到对象，则返回 NULL。
索引键形式¶
索引键可以是任何形式，但由于算法不知道键的长度，因此强烈建议索引键尽早包含其长度，以免长度变化对比较产生影响。
这将导致不同长度键的叶子相互分散，而相同长度键的叶子聚集在一起。
还建议索引键以键其余部分的哈希值开头，以最大限度地分散到整个键空间中。
分散性越好，内部树就越宽、越矮。
分散性差也不是大问题，因为存在快捷方式，并且节点可以包含叶子和元数据指针的混合。
索引键以机器字块的形式读取。每个块被细分为每层一个半字节（4 位），因此在 32 位 CPU 上这适用于 8 层，在 64 位 CPU 上适用于 16 层。除非分散性非常差，否则不太可能需要使用任何特定索引键的一个以上字。
内部工作原理¶
关联数组数据结构有一个内部树。该树由两种类型的元数据块构成：节点和快捷方式。
节点是槽位的数组。每个槽位可以包含以下四种内容之一：
空指针，表示该槽位为空。
指向对象（叶子）的指针。
指向下一级节点的指针。
指向快捷方式的指针。
基本内部树布局¶
暂时忽略快捷方式，节点形成一个多级树。索引键空间被树中的节点严格细分，并且节点出现在固定级别上。例如：
Level: 0 1 2 3
=============== =============== =============== ===============
NODE D
NODE B NODE C +------>+---+
+------>+---+ +------>+---+ | | 0 |
NODE A | | 0 | | | 0 | | +---+
+---+ | +---+ | +---+ | : :
| 0 | | : : | : : | +---+
+---+ | +---+ | +---+ | | f |
| 1 |---+ | 3 |---+ | 7 |---+ +---+
+---+ +---+ +---+
: : : : | 8 |---+
+---+ +---+ +---+ | NODE E
| e |---+ | f | : : +------>+---+
+---+ | +---+ +---+ | 0 |
| f | | | f | +---+
+---+ | +---+ : :
| NODE F +---+
+------>+---+ | f |
| 0 | NODE G +---+
+---+ +------>+---+
: : | | 0 |
+---+ | +---+
| 6 |---+ : :
+---+ +---+
: : | f |
+---+ +---+
| f |
+---+
在上述示例中，有 7 个节点 (A-G)，每个节点有 16 个槽位 (0-f)。假设树中没有其他元数据节点，则键空间划分如下：
KEY PREFIX NODE
========== ====
137* D
138* E
13[0-69-f]* C
1[0-24-f]* B
e6* G
e[0-57-f]* F
[02-df]* A
因此，例如，具有以下示例索引键的键将在相应的节点中找到：
INDEX KEY PREFIX NODE
=============== ======= ====
13694892892489 13 C
13795289025897 137 D
13889dde88793 138 E
138bbb89003093 138 E
1394879524789 12 C
1458952489 1 B
9431809de993ba - A
b4542910809cd - A
e5284310def98 e F
e68428974237 e6 G
e7fffcbd443 e F
f3842239082 - A
为了节省内存，如果一个节点可以容纳其键空间部分中的所有叶子，那么该节点将包含所有这些叶子，并且不会有任何元数据指针——即使其中一些叶子希望位于同一个槽位中。
一个节点可以包含叶子和元数据指针的异构混合。元数据指针必须位于与其键空间细分相匹配的槽位中。叶子可以位于未被元数据指针占用的任何槽位中。保证节点中的任何叶子都不会与被元数据指针占用的槽位匹配。如果元数据指针存在，则任何其键与元数据键前缀匹配的叶子必须位于元数据指针指向的子树中。
在上述索引键示例列表中，节点 A 将包含：
SLOT CONTENT INDEX KEY (PREFIX)
==== =============== ==================
1 PTR TO NODE B 1*
any LEAF 9431809de993ba
any LEAF b4542910809cd
e PTR TO NODE F e*
any LEAF f3842239082
节点 B 将包含：
3 PTR TO NODE C 13*
any LEAF 1458952489
快捷方式¶
快捷方式是元数据记录，可以跳过键空间的一部分。快捷方式是替代一系列逐级上升的单占用节点的方法。快捷方式的存在是为了节省内存并加快遍历速度。
树的根节点可以是快捷方式——例如，如果树包含至少 17 个节点，并且它们的键前缀都是 1111。插入算法将插入一个快捷方式，以一次性跳过 1111 键空间，并到达这些节点实际开始不同的第四级。
节点分裂和折叠¶
每个节点的最大容量为 16 个叶子和元数据指针。如果插入算法发现它试图将第 17 个对象插入一个节点，则该节点将被分裂，以便在该级别上具有共同键段的至少两个叶子最终位于以该共同键段的槽位为根的独立节点中。
如果满节点中的叶子和正在插入的叶子足够相似，则将在树中插入一个快捷方式。
当以某个节点为根的子树中的对象数量减少到 16 个或更少时，该子树将折叠成单个节点——如果可能，这将向根节点方向级联。
非递归迭代¶
每个节点和快捷方式都包含一个指向其父节点的反向指针，以及父节点中指向它的槽位号。非递归迭代利用这些信息，通过转到父节点，槽位 N + 1 来向根方向遍历树，确保无需栈即可进行。
然而，反向指针使得同时进行修改和迭代变得棘手。
同时修改和迭代¶
有几种情况需要考虑：
简单插入/替换。这仅仅涉及在屏障之后用指向新叶子的指针替换 NULL 或旧的匹配叶子指针。元数据块没有其他变化。旧叶子直到 RCU 宽限期过后才会被释放。
简单删除。这仅仅涉及清除一个旧的匹配叶子。元数据块没有其他变化。旧叶子直到 RCU 宽限期过后才会被释放。
插入替换了我们尚未进入的子树的一部分。这可能涉及替换该子树的一部分——但这不会影响迭代，因为我们尚未到达指向它的指针，并且祖先块没有被替换（它们的布局没有改变）。
插入替换我们正在主动处理的节点。这不是问题，因为我们已经通过了锚定指针，并且在跟随反向指针之前不会切换到新布局——届时我们已经检查了被替换节点中的叶子（在跟随任何元数据指针之前，我们遍历节点中的所有叶子）。
然而，我们可能会再次看到一些叶子，这些叶子已经被分裂到一个新的分支中，该分支位于比我们之前位置更靠后的槽位中。
插入替换我们正在处理的依赖分支的节点。这不会影响我们，直到我们跟随反向指针。类似于 (4)。
删除折叠我们下面的分支。这不会影响我们，因为反向指针会在我们看到新节点之前将我们带回新节点的父节点。整个折叠的子树被原样丢弃——并且仍将以相同的槽位为根，所以我们不应该第二次处理它，因为我们会回到槽位 + 1。
注意
在某些情况下，我们需要同时更改节点的父指针和父槽位指针（例如，我们在其前面插入另一个节点并将其向上移动了一级）。如果没有对读操作进行锁定，我们无法做到这一点——因此我们也必须替换该节点。
然而，当我们把一个快捷方式改变成一个节点时，这不是问题，因为快捷方式只有一个槽位，所以在向后遍历时，父槽位号不会被使用。这意味着可以先改变槽位号——只要使用合适的屏障来确保在读取反向指针之后再读取父槽位号。
过时的块和叶子在 RCU 宽限期过后才会被释放，因此只要任何进行遍历或迭代的线程持有 RCU 读锁，旧的超结构就不会消失。