通用关联数组实现¶
概述¶
此关联数组实现是一个具有以下属性的对象容器
对象是不透明的指针。该实现不关心它们指向哪里（如果有的话）或它们指向什么（如果有的话）。
注意
对象指针的最低有效位_必须_为零。
对象不需要包含供数组使用的链接块。这允许一个对象同时位于多个数组中。相反，数组由指向对象的元数据块组成。
对象需要索引键才能在数组中找到它们。
索引键必须是唯一的。插入与数组中已有的对象具有相同键的对象将替换旧对象。
索引键可以具有任何长度，并且可以具有不同的长度。
索引键应在早期对长度进行编码，然后再看到任何因长度而产生的变化。
索引键可以包含一个哈希值，以将对象分散在整个数组中。
可以迭代数组。对象不一定会按键顺序出现。
可以在修改数组的同时对其进行迭代，前提是迭代器持有 RCU 读锁。但是请注意，在这种情况下，某些对象可能会被多次看到。如果这是一个问题，则迭代器应锁定以防止修改。但是，除非删除对象，否则不会遗漏对象。
可以通过索引键查找数组中的对象。
可以在修改数组的同时查找对象，前提是执行查找的线程持有 RCU 读锁。
该实现内部使用一个 16 指针节点树，这些节点在每一层都通过索引键中的半字节进行索引，方式与基数树相同。为了提高内存效率，可以设置快捷方式来跳过原本会是一系列单占用节点的节点。此外，节点会将叶对象指针打包到节点的空闲空间中，而不是在需要向完整节点添加对象之前才创建一个额外的分支。
公共 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 层。除非散射真的很差，否则不太可能需要使用任何特定索引键的多个字。
内部工作原理¶
关联数组数据结构具有一个内部树。此树由两种类型的元数据块构成：节点和快捷方式。
节点是一个槽数组。每个槽可以包含以下四种内容之一
一个 NULL 指针，指示该槽为空。
指向对象（叶子）的指针。
指向下一层节点的指针。
指向快捷方式的指针。
基本内部树布局¶
暂时忽略快捷方式，节点形成一个多级树。索引键空间由树中的节点严格细分，节点出现在固定的层级上。例如
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 读取锁，旧的上层结构就不会消失。