1.. include:: ../disclaimer-zh_CN.rst 2 3:Original: Documentation/core-api/assoc_array.rst 4 5:翻译: 6 7 司延腾 Yanteng Si <siyanteng@loongson.cn> 8 9:校译: 10 11 12 13.. _cn_core-api_assoc_array: 14 15================== 16通用关联数组的实现 17================== 18 19简介 20==== 21 22这个关联数组的实现是一个具有以下属性的对象容器: 23 241. 对象是不透明的指针。该实现不关心它们指向哪里（如果有的话）或它们指向什么（如果有的 25 话）。 26 27 .. note:: 28 29 指向对象的指针 *必须* 在最小有效位为零。 30 312. 对象不需要包含供数组使用的链接块。这允许一个对象同时位于多个数组中。相反，数组是 32 由指向对象的元数据块组成的。 33 343. 对象需要索引键来定位它们在阵列中的位置。 35 364. 索引键必须是唯一的。插入一个与已经在数组中的且具有相同键值的对象将取代旧的对象。 37 385. 索引键可以是任何长度，也可以是不同的长度。 39 406. 索引键应该在早期就对长度进行编码，即在任何由于长度引起的变化出现之前。 41 427. 索引键可以包括一个哈希值，以便将对象分散到整个数组中。 43 448. 该数组可以迭代。对象不一定会按索引键的顺序出现。 45 469. 数组可以在被修改的时候进行迭代，只要RCU的读锁被迭代器持有。然而，请注意，在这种情 47 况下，一些对象可能会被看到不止一次。如果这是个问题，迭代器应该锁定以防止修改。然 48 而，除非删除，否则对象不会被错过。 49 5010. 数组中的对象可以通过其索引键进行查询。 51 5211. 当数组被修改时，对象可以被查询，前提是进行查询的线程持有RCU的读锁。 53 54该实现在内部使用了一棵由16个指针节点组成的树，这些节点在每一层都由索引键的小数点进行索 55引，其方式与基数树相同。为了提高内存效率，可以放置快捷键，以跳过本来是一系列单占节点的地 56方。此外，节点将叶子对象指针打包到节点的空闲空间中，而不是做一个额外的分支，直到有对象 57需要被添加到一个完整的节点中。 58 59公用API 60======= 61 62公用API可以在 ``<linux/assoc_array.h>`` 中找到。关联数组的根是以下结构:: 63 64 struct assoc_array { 65 ... 66 }; 67 68该代码是通过启用 ``CONFIG_ASSOCIATIVE_ARRAY`` 来选择的，以:: 69 70 ./script/config -e ASSOCIATIVE_ARRAY 71 72 73编辑脚本 74-------- 75 76插入和删除功能会产生一个“编辑脚本”，以后可以应用这个脚本来实现更改，而不会造成 ``ENOMEM`` 77风险。这保留了将被安装在内部树中的预分配的元数据块，并跟踪应用脚本时将从树中删除的元数 78据块。 79 80在脚本应用后，这也被用来跟踪死块和死对象，以便以后可以释放它们。释放是在RCU宽限期过后 81进行的--因此允许访问功能在RCU读锁下进行。 82 83脚本在API之外显示为一个类型为:: 84 85 struct assoc_array_edit; 86 87有两个处理脚本的功能: 88 891. 应用一个编辑脚本:: 90 91 void assoc_array_apply_edit(struct assoc_array_edit *edit); 92 93这将执行编辑功能，插值各种写屏障，以允许在RCU读锁下的访问继续进行。然后，编辑脚本将被 94传递给 ``call_rcu()`` ，以释放它和它所指向的任何死的东西。 95 962. Cancel an edit script:: 97 98 void assoc_array_cancel_edit(struct assoc_array_edit *edit); 99 100这将立即释放编辑脚本和所有预分配的内存。如果这是为了插入，新的对象不会被这个函数释放， 101而是必须由调用者释放。 102 103这些函数保证不会失败。 104 105 106操作表 107------ 108 109各种功能采用了一个操作表:: 110 111 struct assoc_array_ops { 112 ... 113 }; 114 115这指出了一些方法，所有这些方法都需要提供: 116 1171. 从调用者数据中获取索引键的一个块:: 118 119 unsigned long (*get_key_chunk)(const void *index_key, int level); 120 121这应该返回一个由调用者提供的索引键的块，从level参数给出的 *比特* 位置开始。level参数将 122是 ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` 的倍数，该函数应返回 ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` 123位。不可能出现错误。 124 125 1262. 获取一个对象的索引键的一个块:: 127 128 unsigned long (*get_object_key_chunk)(const void *object, int level); 129 130和前面的函数一样，但是从数组中的一个对象而不是从调用者提供的索引键中获取数据。 131 132 1333. 看看这是否是我们要找的对象:: 134 135 bool (*compare_object)(const void *object, const void *index_key); 136 137将对象与一个索引键进行比较，如果匹配则返回 ``true`` ，不匹配则返回 ``false`` 。 138 139 1404. 对两个对象的索引键进行比较:: 141 142 int (*diff_objects)(const void *object, const void *index_key); 143 144返回指定对象的索引键与给定索引键不同的比特位置，如果它们相同，则返回-1。 145 146 1475. 释放一个对象:: 148 149 void (*free_object)(void *object); 150 151释放指定的对象。注意，这可能是在调用 ``assoc_array_apply_edit()`` 后的一个RCU宽限期内 152调用的，所以在模块卸载时可能需要 ``synchronize_rcu()`` 。 153 154 155操控函数 156-------- 157 158有一些函数用于操控关联数组: 159 1601. 初始化一个关联数组:: 161 162 void assoc_array_init(struct assoc_array *array); 163 164这将初始化一个关联数组的基础结构。它不会失败。 165 166 1672. 在一个关联数组中插入/替换一个对象:: 168 169 struct assoc_array_edit * 170 assoc_array_insert(struct assoc_array *array, 171 const struct assoc_array_ops *ops, 172 const void *index_key, 173 void *object); 174 175这将把给定的对象插入数组中。注意，指针的最小有效位必须是0，因为它被用来在内部标记指针的类 176型。 177 178如果该键已经存在一个对象，那么它将被新的对象所取代，旧的对象将被自动释放。 179 180``index_key`` 参数应持有索引键信息，并在调用OPP表中的方法时传递给它们。 181 182这个函数不对数组本身做任何改动，而是返回一个必须应用的编辑脚本。如果出现内存不足的错误，会 183返回 ``-ENOMEM`` 。 184 185调用者应专门锁定数组的其他修改器。 186 187 1883. 从一个关联数组中删除一个对象:: 189 190 struct assoc_array_edit * 191 assoc_array_delete(struct assoc_array *array, 192 const struct assoc_array_ops *ops, 193 const void *index_key); 194 195这将从数组中删除一个符合指定数据的对象。 196 197``index_key`` 参数应持有索引键信息，并在调用OPP表中的方法时传递给它们。 198 199这个函数不对数组本身做任何改动，而是返回一个必须应用的编辑脚本。 ``-ENOMEM`` 在出现内存不足 200的错误时返回。如果在数组中没有找到指定的对象，将返回 ``NULL`` 。 201 202调用者应该对数组的其他修改者进行专门锁定。 203 204 2054. 从一个关联数组中删除所有对象:: 206 207 struct assoc_array_edit * 208 assoc_array_clear(struct assoc_array *array, 209 const struct assoc_array_ops *ops); 210 211这个函数删除了一个关联数组中的所有对象，使其完全为空。 212 213这个函数没有对数组本身做任何改动，而是返回一个必须应用的编辑脚本。如果出现内存不足 214的错误，则返回 ``-ENOMEM`` 。 215 216调用者应专门锁定数组的其他修改者。 217 218 2195. 销毁一个关联数组，删除所有对象:: 220 221 void assoc_array_destroy(struct assoc_array *array, 222 const struct assoc_array_ops *ops); 223 224这将破坏关联数组的内容，使其完全为空。在这个函数销毁数组的同时，不允许另一个线程在RCU读锁 225下遍历数组，因为在内存释放时不执行RCU延迟，这需要分配内存。 226 227调用者应该专门针对数组的其他修改者和访问者进行锁定。 228 229 2306. 垃圾回收一个关联数组:: 231 232 int assoc_array_gc(struct assoc_array *array, 233 const struct assoc_array_ops *ops, 234 bool (*iterator)(void *object, void *iterator_data), 235 void *iterator_data); 236 237这是对一个关联数组中的对象进行迭代，并将每个对象传递给 ``iterator()`` 。如果 ``iterator()`` 返回 238true，该对象被保留。如果它返回 ``false`` ，该对象将被释放。如果 ``iterator()`` 函数返回 ``true`` ，它必须 239在返回之前对该对象进行适当的 ``refcount`` 递增。 240 241如果可能的话，内部树将被打包下来，作为迭代的一部分，以减少其中的节点数量。 242 243``iterator_data`` 被直接传递给 ``iterator()`` ，否则会被函数忽略。 244 245如果成功，该函数将返回 ``0`` ，如果没有足够的内存，则返回 ``-ENOMEM`` 。 246 247在这个函数执行过程中，其他线程有可能在RCU读锁下迭代或搜索阵列。调用者应该专门针对数组的其他 248修改者进行锁定。 249 250 251访问函数 252-------- 253 254有两个函数用于访问一个关联数组: 255 2561. 遍历一个关联数组中的所有对象:: 257 258 int assoc_array_iterate(const struct assoc_array *array, 259 int (*iterator)(const void *object, 260 void *iterator_data), 261 void *iterator_data); 262 263这将数组中的每个对象传递给迭代器回调函数。 ``iterator_data`` 是该函数的私有数据。 264 265在数组被修改的同时，可以在数组上使用这个方法，前提是RCU读锁被持有。在这种情况下，迭代函数有 266可能两次看到某些对象。如果这是个问题，那么修改应该被锁定。然而，迭代算法不应该错过任何对象。 267 268如果数组中没有对象，该函数将返回 ``0`` ，否则将返回最后一次调用的迭代器函数的结果。如果对迭代函数 269的任何调用导致非零返回，迭代立即停止。 270 271 2722. 在一个关联数组中寻找一个对象:: 273 274 void *assoc_array_find(const struct assoc_array *array, 275 const struct assoc_array_ops *ops, 276 const void *index_key); 277 278这将直接穿过数组的内部树，到达索引键所指定的对象。 279 280这个函数可以在修改数组的同时用在数组上，前提是RCU读锁被持有。 281 282如果找到对象，该函数将返回对象（并将 ``*_type`` 设置为对象的类型），如果没有找到对象，将返回 ``NULL`` 。 283 284 285索引键形式 286---------- 287 288索引键可以是任何形式的，但是由于算法没有被告知键有多长，所以强烈建议在任何由于长度而产生的变化 289对比较产生影响之前，索引键应该很早就包括其长度。 290 291这将导致具有不同长度键的叶子相互分散，而具有相同长度键的叶子则聚集在一起。 292 293我们还建议索引键以键的其余部分的哈希值开始，以最大限度地提高整个键空间的散布情况。 294 295分散性越好，内部树就越宽，越低。 296 297分散性差并不是一个太大的问题，因为有快捷键，节点可以包含叶子和元数据指针的混合物。 298 299索引键是以机器字的块状来读取的。每个块被细分为每层一个nibble（4比特），所以在32位CPU上这适合8层， 300在64位CPU上适合16层。除非散布情况真的很差，否则不太可能有超过一个字的任何特定索引键需要被使用。 301 302 303内部工作机制 304============ 305 306关联数组数据结构有一个内部树。这个树由两种类型的元数据块构成：节点和快捷键。 307 308一个节点是一个槽的数组。每个槽可以包含以下四种东西之一: 309 310* 一个NULL的指针，表示槽是空的。 311* 一个指向对象（叶子）的指针。 312* 一个指向下一级节点的指针。 313* 一个指向快捷键的指针。 314 315 316基本的内部树形布局 317------------------ 318 319暂时不考虑快捷键，节点形成一个多级树。索引键空间被树上的节点严格细分，节点出现在固定的层次上。例如:: 320 321 Level: 0 1 2 3 322 =============== =============== =============== =============== 323 NODE D 324 NODE B NODE C +------>+---+ 325 +------>+---+ +------>+---+ | | 0 | 326 NODE A | | 0 | | | 0 | | +---+ 327 +---+ | +---+ | +---+ | : : 328 | 0 | | : : | : : | +---+ 329 +---+ | +---+ | +---+ | | f | 330 | 1 |---+ | 3 |---+ | 7 |---+ +---+ 331 +---+ +---+ +---+ 332 : : : : | 8 |---+ 333 +---+ +---+ +---+ | NODE E 334 | e |---+ | f | : : +------>+---+ 335 +---+ | +---+ +---+ | 0 | 336 | f | | | f | +---+ 337 +---+ | +---+ : : 338 | NODE F +---+ 339 +------>+---+ | f | 340 | 0 | NODE G +---+ 341 +---+ +------>+---+ 342 : : | | 0 | 343 +---+ | +---+ 344 | 6 |---+ : : 345 +---+ +---+ 346 : : | f | 347 +---+ +---+ 348 | f | 349 +---+ 350 351在上述例子中，有7个节点（A-G），每个节点有16个槽（0-f）。假设树上没有其他元数据节点，那么密钥空间 352是这样划分的:: 353 354 KEY PREFIX NODE 355 ========== ==== 356 137* D 357 138* E 358 13[0-69-f]* C 359 1[0-24-f]* B 360 e6* G 361 e[0-57-f]* F 362 [02-df]* A 363 364因此，例如，具有以下示例索引键的键将在适当的节点中被找到:: 365 366 INDEX KEY PREFIX NODE 367 =============== ======= ==== 368 13694892892489 13 C 369 13795289025897 137 D 370 13889dde88793 138 E 371 138bbb89003093 138 E 372 1394879524789 12 C 373 1458952489 1 B 374 9431809de993ba - A 375 b4542910809cd - A 376 e5284310def98 e F 377 e68428974237 e6 G 378 e7fffcbd443 e F 379 f3842239082 - A 380 381为了节省内存，如果一个节点可以容纳它的那部分键空间中的所有叶子，那么这个节点将有所有这些叶子，而不 382会有任何元数据指针——即使其中一些叶子想在同一个槽中。 383 384一个节点可以包含叶子和元数据指针的异质性混合。元数据指针必须在与它们的关键空间的细分相匹配的槽中。 385叶子可以在任何没有被元数据指针占据的槽中。保证一个节点中没有一个叶子会与元数据指针占据的槽相匹配。 386如果元数据指针在那里，任何键与元数据键前缀相匹配的叶必须在元数据指针指向的子树中。 387 388在上面的索引键的例子列表中，节点A将包含:: 389 390 SLOT CONTENT INDEX KEY (PREFIX) 391 ==== =============== ================== 392 1 PTR TO NODE B 1* 393 any LEAF 9431809de993ba 394 any LEAF b4542910809cd 395 e PTR TO NODE F e* 396 any LEAF f3842239082 397 398和节点B:: 399 400 3 PTR TO NODE C 13* 401 any LEAF 1458952489 402 403 404快捷键 405--------- 406 407快捷键是跳过一块键空间的元数据记录。快捷键是一系列通过层次上升的单占节点的替代物。快捷键的存在是 408为了节省内存和加快遍历速度。 409 410树的根部有可能是一个快捷键——比如说，树至少包含17个节点，都有键前缀 ``1111`` 。插入算法将插入一个快捷键， 411以单次跳过 ``1111`` 的键位，并到达第四层，在这里，这些键位实际上变得不同。 412 413 414拆分和合并节点 415------------------------------ 416 417每个节点的最大容量为16个叶子和元数据指针。如果插入算法发现它正试图将一个第17个对象插入到一个节点中， 418该节点将被拆分，使得至少两个在该层有一个共同的关键段的叶子最终在一个单独的节点中，该共同的关键段的根 419在该槽上。 420 421如果一个完整的节点中的叶子和被插入的叶子足够相似，那么就会在树中插入一个快捷键。 422 423当根植于某个节点的子树中的对象数量下降到16个或更少时，那么该子树将被合并成一个单独的节点——如果可能的 424话，这将向根部扩散。 425 426 427非递归式迭代 428------------ 429 430每个节点和快捷键都包含一个指向其父节点的后置指针，以及该父节点中指向它的槽数。非递归迭代使用这些来 431通过树的根部进行，前往父节点，槽N+1，以确保在没有堆栈的情况下取得进展。 432 433然而，反向指针使得同时改变和迭代变得很棘手。 434 435 436同时改变和迭代 437-------------- 438 439有一些情况需要考虑: 440 4411. 简单的插入/替换。这涉及到简单地将一个NULL或旧的匹配叶子的指针替换为屏障后的新叶子的指针。否则元数 442 据块不会改变。一个旧的叶子直到RCU宽限期过后才会被释放。 443 4442. 简单删除。这只是涉及到清除一个旧的匹配叶子。元数据块不会有其他变化。旧的叶子直到RCU宽限期之后才会 445 被释放。 446 4473. 插入，替换我们还没有进入的子树的一部分。这可能涉及到替换该子树的一部分——但这不会影响迭代，因为我们 448 还没有到达它的指针，而且祖先块也不会被替换（这些块的布局不会改变）。 449 4504. 插入替换了我们正在处理的节点。这不是一个问题，因为我们已经通过了锚定指针，直到我们跟随后面的指针才 451 会切换到新的布局上——这时我们已经检查了被替换节点的叶子（在跟随任何元数据指针之前，我们会迭代一个节 452 点的所有叶子）。 453 454 然而，我们可能会重新看到一些叶子，这些叶子已经被分割成一个新的分支，而这个分支的位置比我们之前的位 455 置更远。 456 4575. 插入替换了我们正在处理的依赖分支的节点。这不会影响到我们，直到我们跟随后面的指针。与（4）类似。 458 4596. 删掉我们下面的一个分支。这不会影响我们，因为在我们看到新节点之前，回溯指针会让我们回到新节点的父节 460 点。整个崩溃的子树被扔掉了，没有任何变化——而且仍然会在同一个槽上生根，所以我们不应该第二次处理它， 461 因为我们会回到槽+1。 462 463.. note:: 464 465 在某些情况下，我们需要同时改变一个节点的父指针和父槽指针（比如说，我们在它之前插入了另一个节点， 466 并把它往上移了一层）。我们不能在不锁定读取的情况下这样做——所以我们必须同时替换该节点。 467 468 然而，当我们把一个快捷键改成一个节点时，这不是一个问题，因为快捷键只有一个槽，所以当向后遍 469 历一个槽时，不会使用父槽号。这意味着先改变槽位号是可以的——只要使用适当的屏障来确保父槽位号在后 470 退指针之后被读取。 471 472过时的块和叶子在RCU宽限期过后会被释放，所以只要任何进行遍历或迭代的人持有RCU读锁，旧的上层建筑就不 473应该在他们身上消失。 474