通用關聯陣列實現¶
概述¶
此關聯陣列實現是一個物件容器，具有以下特性：
物件是不透明指標。實現不關心它們指向何處（如果存在）或指向什麼（如果存在）。
注意
物件指標的最低有效位必須為零。
物件不需要包含供陣列使用的連結塊。這允許一個物件同時位於多個數組中。相反，陣列由指向物件的元資料塊構成。
物件需要索引鍵才能在陣列中定位它們。
索引鍵必須是唯一的。插入一個鍵與陣列中已有的物件相同的物件將替換舊物件。
索引鍵可以是任何長度，也可以是不同長度。
索引鍵應儘早編碼其長度，在因長度引起任何變化之前。
索引鍵可以包含雜湊值，以便將物件分散到整個陣列中。
陣列可以被遍歷。物件不一定按鍵序出現。
只要迭代器持有 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 讀鎖，舊的超結構就不會消失。