[RFC PATCH 6/6] lib: Remove unused assoc_array
Jarkko Sakkinen
jarkko at kernel.org
Fri Oct 16 21:53:04 UTC 2026
Drop the obsolete leaf-count reference from a dm-verity test comment.
Signed-off-by: Jarkko Sakkinen <jarkko at kernel.org>
---
Documentation/core-api/assoc_array.rst | 564 ------
Documentation/core-api/index.rst | 1 -
.../zh_CN/core-api/assoc_array.rst | 473 -----
.../translations/zh_CN/core-api/index.rst | 1 -
include/linux/assoc_array.h | 88 -
include/linux/assoc_array_priv.h | 178 --
lib/Kconfig | 14 -
lib/Makefile | 1 -
lib/assoc_array.c | 1724 -----------------
9 files changed, 3044 deletions(-)
delete mode 100644 Documentation/core-api/assoc_array.rst
delete mode 100644 Documentation/translations/zh_CN/core-api/assoc_array.rst
delete mode 100644 include/linux/assoc_array.h
delete mode 100644 include/linux/assoc_array_priv.h
delete mode 100644 lib/assoc_array.c
diff --git a/Documentation/core-api/assoc_array.rst b/Documentation/core-api/assoc_array.rst
deleted file mode 100644
index 19d89f92bf8d..000000000000
--- a/Documentation/core-api/assoc_array.rst
+++ /dev/null
@@ -1,564 +0,0 @@
-========================================
-Generic Associative Array Implementation
-========================================
-
-Overview
-========
-
-This associative array implementation is an object container with the following
-properties:
-
-1. Objects are opaque pointers. The implementation does not care where they
- point (if anywhere) or what they point to (if anything).
-
- .. note::
-
- Pointers to objects _must_ be zero in the least significant bit.
-
-2. Objects do not need to contain linkage blocks for use by the array. This
- permits an object to be located in multiple arrays simultaneously.
- Rather, the array is made up of metadata blocks that point to objects.
-
-3. Objects require index keys to locate them within the array.
-
-4. Index keys must be unique. Inserting an object with the same key as one
- already in the array will replace the old object.
-
-5. Index keys can be of any length and can be of different lengths.
-
-6. Index keys should encode the length early on, before any variation due to
- length is seen.
-
-7. Index keys can include a hash to scatter objects throughout the array.
-
-8. The array can iterated over. The objects will not necessarily come out in
- key order.
-
-9. The array can be iterated over while it is being modified, provided the
- RCU readlock is being held by the iterator. Note, however, under these
- circumstances, some objects may be seen more than once. If this is a
- problem, the iterator should lock against modification. Objects will not
- be missed, however, unless deleted.
-
-10. Objects in the array can be looked up by means of their index key.
-
-11. Objects can be looked up while the array is being modified, provided the
- RCU readlock is being held by the thread doing the look up.
-
-The implementation uses a tree of 16-pointer nodes internally that are indexed
-on each level by nibbles from the index key in the same manner as in a radix
-tree. To improve memory efficiency, shortcuts can be emplaced to skip over
-what would otherwise be a series of single-occupancy nodes. Further, nodes
-pack leaf object pointers into spare space in the node rather than making an
-extra branch until as such time an object needs to be added to a full node.
-
-
-The Public API
-==============
-
-The public API can be found in ``<linux/assoc_array.h>``. The associative
-array is rooted on the following structure::
-
- struct assoc_array {
- ...
- };
-
-The code is selected by enabling ``CONFIG_ASSOCIATIVE_ARRAY`` with::
-
- ./script/config -e ASSOCIATIVE_ARRAY
-
-
-Edit Script
------------
-
-The insertion and deletion functions produce an 'edit script' that can later be
-applied to effect the changes without risking ``ENOMEM``. This retains the
-preallocated metadata blocks that will be installed in the internal tree and
-keeps track of the metadata blocks that will be removed from the tree when the
-script is applied.
-
-This is also used to keep track of dead blocks and dead objects after the
-script has been applied so that they can be freed later. The freeing is done
-after an RCU grace period has passed - thus allowing access functions to
-proceed under the RCU read lock.
-
-The script appears as outside of the API as a pointer of the type::
-
- struct assoc_array_edit;
-
-There are two functions for dealing with the script:
-
-1. Apply an edit script::
-
- void assoc_array_apply_edit(struct assoc_array_edit *edit);
-
- This will perform the edit functions, interpolating various write barriers
- to permit accesses under the RCU read lock to continue. The edit script
- will then be passed to ``call_rcu()`` to free it and any dead stuff it
- points to.
-
-2. Cancel an edit script::
-
- void assoc_array_cancel_edit(struct assoc_array_edit *edit);
-
- This frees the edit script and all preallocated memory immediately. If
- this was for insertion, the new object is *not* released by this function,
- but must rather be released by the caller.
-
-These functions are guaranteed not to fail.
-
-
-Operations Table
-----------------
-
-Various functions take a table of operations::
-
- struct assoc_array_ops {
- ...
- };
-
-This points to a number of methods, all of which need to be provided:
-
-1. Get a chunk of index key from caller data::
-
- unsigned long (*get_key_chunk)(const void *index_key, int level);
-
- This should return a chunk of caller-supplied index key starting at the
- *bit* position given by the level argument. The level argument will be a
- multiple of ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` and the function should return
- ``ASSOC_ARRAY_KEY_CHUNK_SIZE bits``. No error is possible.
-
-
-2. Get a chunk of an object's index key::
-
- unsigned long (*get_object_key_chunk)(const void *object, int level);
-
- As the previous function, but gets its data from an object in the array
- rather than from a caller-supplied index key.
-
-
-3. See if this is the object we're looking for::
-
- bool (*compare_object)(const void *object, const void *index_key);
-
- Compare the object against an index key and return ``true`` if it matches
- and ``false`` if it doesn't.
-
-
-4. Diff the index keys of two objects::
-
- int (*diff_objects)(const void *object, const void *index_key);
-
- Return the bit position at which the index key of the specified object
- differs from the given index key or -1 if they are the same.
-
-
-5. Free an object::
-
- void (*free_object)(void *object);
-
- Free the specified object. Note that this may be called an RCU grace period
- after ``assoc_array_apply_edit()`` was called, so ``synchronize_rcu()`` may
- be necessary on module unloading.
-
-
-Manipulation Functions
-----------------------
-
-There are a number of functions for manipulating an associative array:
-
-1. Initialise an associative array::
-
- void assoc_array_init(struct assoc_array *array);
-
- This initialises the base structure for an associative array. It can't fail.
-
-
-2. Insert/replace an object in an associative array::
-
- struct assoc_array_edit *
- assoc_array_insert(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key,
- void *object);
-
- This inserts the given object into the array. Note that the least
- significant bit of the pointer must be zero as it's used to type-mark
- pointers internally.
-
- If an object already exists for that key then it will be replaced with the
- new object and the old one will be freed automatically.
-
- The ``index_key`` argument should hold index key information and is
- passed to the methods in the ops table when they are called.
-
- This function makes no alteration to the array itself, but rather returns
- an edit script that must be applied. ``-ENOMEM`` is returned in the case of
- an out-of-memory error.
-
- The caller should lock exclusively against other modifiers of the array.
-
-
-3. Delete an object from an associative array::
-
- struct assoc_array_edit *
- assoc_array_delete(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key);
-
- This deletes an object that matches the specified data from the array.
-
- The ``index_key`` argument should hold index key information and is
- passed to the methods in the ops table when they are called.
-
- This function makes no alteration to the array itself, but rather returns
- an edit script that must be applied. ``-ENOMEM`` is returned in the case of
- an out-of-memory error. ``NULL`` will be returned if the specified object
- is not found within the array.
-
-The caller should lock exclusively against other modifiers of the array.
-
-
-4. Delete all objects from an associative array::
-
- struct assoc_array_edit *
- assoc_array_clear(struct assoc_array *array,
- const struct assoc_array_ops *ops);
-
- This deletes all the objects from an associative array and leaves it
- completely empty.
-
- This function makes no alteration to the array itself, but rather returns
- an edit script that must be applied. ``-ENOMEM`` is returned in the case of
- an out-of-memory error.
-
- The caller should lock exclusively against other modifiers of the array.
-
-
-5. Destroy an associative array, deleting all objects::
-
- void assoc_array_destroy(struct assoc_array *array,
- const struct assoc_array_ops *ops);
-
- This destroys the contents of the associative array and leaves it
- completely empty. It is not permitted for another thread to be traversing
- the array under the RCU read lock at the same time as this function is
- destroying it as no RCU deferral is performed on memory release -
- something that would require memory to be allocated.
-
- The caller should lock exclusively against other modifiers and accessors
- of the array.
-
-
-6. Garbage collect an associative array::
-
- int assoc_array_gc(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- bool (*iterator)(void *object, void *iterator_data),
- void *iterator_data);
-
- This iterates over the objects in an associative array and passes each one
- to ``iterator()``. If ``iterator()`` returns ``true``, the object is kept.
- If it returns ``false``, the object will be freed. If the ``iterator()``
- function returns ``true``, it must perform any appropriate refcount
- incrementing on the object before returning.
-
- The internal tree will be packed down if possible as part of the iteration
- to reduce the number of nodes in it.
-
- The ``iterator_data`` is passed directly to ``iterator()`` and is otherwise
- ignored by the function.
-
- The function will return ``0`` if successful and ``-ENOMEM`` if there wasn't
- enough memory.
-
- It is possible for other threads to iterate over or search the array under
- the RCU read lock while this function is in progress. The caller should
- lock exclusively against other modifiers of the array.
-
-
-Access Functions
-----------------
-
-There are two functions for accessing an associative array:
-
-1. Iterate over all the objects in an associative array::
-
- int assoc_array_iterate(const struct assoc_array *array,
- int (*iterator)(const void *object,
- void *iterator_data),
- void *iterator_data);
-
- This passes each object in the array to the iterator callback function.
- ``iterator_data`` is private data for that function.
-
- This may be used on an array at the same time as the array is being
- modified, provided the RCU read lock is held. Under such circumstances,
- it is possible for the iteration function to see some objects twice. If
- this is a problem, then modification should be locked against. The
- iteration algorithm should not, however, miss any objects.
-
- The function will return ``0`` if no objects were in the array or else it
- will return the result of the last iterator function called. Iteration
- stops immediately if any call to the iteration function results in a
- non-zero return.
-
-
-2. Find an object in an associative array::
-
- void *assoc_array_find(const struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key);
-
- This walks through the array's internal tree directly to the object
- specified by the index key.
-
- This may be used on an array at the same time as the array is being
- modified, provided the RCU read lock is held.
-
- The function will return the object if found (and set ``*_type`` to the
- object type) or will return ``NULL`` if the object was not found.
-
-
-Index Key Form
---------------
-
-The index key can be of any form, but since the algorithms aren't told how long
-the key is, it is strongly recommended that the index key includes its length
-very early on before any variation due to the length would have an effect on
-comparisons.
-
-This will cause leaves with different length keys to scatter away from each
-other - and those with the same length keys to cluster together.
-
-It is also recommended that the index key begin with a hash of the rest of the
-key to maximise scattering throughout keyspace.
-
-The better the scattering, the wider and lower the internal tree will be.
-
-Poor scattering isn't too much of a problem as there are shortcuts and nodes
-can contain mixtures of leaves and metadata pointers.
-
-The index key is read in chunks of machine word. Each chunk is subdivided into
-one nibble (4 bits) per level, so on a 32-bit CPU this is good for 8 levels and
-on a 64-bit CPU, 16 levels. Unless the scattering is really poor, it is
-unlikely that more than one word of any particular index key will have to be
-used.
-
-
-Internal Workings
-=================
-
-The associative array data structure has an internal tree. This tree is
-constructed of two types of metadata blocks: nodes and shortcuts.
-
-A node is an array of slots. Each slot can contain one of four things:
-
-* A NULL pointer, indicating that the slot is empty.
-* A pointer to an object (a leaf).
-* A pointer to a node at the next level.
-* A pointer to a shortcut.
-
-
-Basic Internal Tree Layout
---------------------------
-
-Ignoring shortcuts for the moment, the nodes form a multilevel tree. The index
-key space is strictly subdivided by the nodes in the tree and nodes occur on
-fixed levels. For example::
-
- 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 |
- +---+
-
-In the above example, there are 7 nodes (A-G), each with 16 slots (0-f).
-Assuming no other meta data nodes in the tree, the key space is divided
-thusly:
-
- =========== ====
- 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
- =========== ====
-
-So, for instance, keys with the following example index keys will be found in
-the appropriate nodes:
-
- =============== ======= ====
- 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
- =============== ======= ====
-
-To save memory, if a node can hold all the leaves in its portion of keyspace,
-then the node will have all those leaves in it and will not have any metadata
-pointers - even if some of those leaves would like to be in the same slot.
-
-A node can contain a heterogeneous mix of leaves and metadata pointers.
-Metadata pointers must be in the slots that match their subdivisions of key
-space. The leaves can be in any slot not occupied by a metadata pointer. It
-is guaranteed that none of the leaves in a node will match a slot occupied by a
-metadata pointer. If the metadata pointer is there, any leaf whose key matches
-the metadata key prefix must be in the subtree that the metadata pointer points
-to.
-
-In the above example list of index keys, node A will contain:
-
- ==== =============== ==================
- 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
- ==== =============== ==================
-
-and node B:
-
- ==== =============== ==================
- SLOT CONTENT INDEX KEY (PREFIX)
- ==== =============== ==================
- 3 PTR TO NODE C 13*
- any LEAF 1458952489
- ==== =============== ==================
-
-
-Shortcuts
----------
-
-Shortcuts are metadata records that jump over a piece of keyspace. A shortcut
-is a replacement for a series of single-occupancy nodes ascending through the
-levels. Shortcuts exist to save memory and to speed up traversal.
-
-It is possible for the root of the tree to be a shortcut - say, for example,
-the tree contains at least 17 nodes all with key prefix ``1111``. The
-insertion algorithm will insert a shortcut to skip over the ``1111`` keyspace
-in a single bound and get to the fourth level where these actually become
-different.
-
-
-Splitting And Collapsing Nodes
-------------------------------
-
-Each node has a maximum capacity of 16 leaves and metadata pointers. If the
-insertion algorithm finds that it is trying to insert a 17th object into a
-node, that node will be split such that at least two leaves that have a common
-key segment at that level end up in a separate node rooted on that slot for
-that common key segment.
-
-If the leaves in a full node and the leaf that is being inserted are
-sufficiently similar, then a shortcut will be inserted into the tree.
-
-When the number of objects in the subtree rooted at a node falls to 16 or
-fewer, then the subtree will be collapsed down to a single node - and this will
-ripple towards the root if possible.
-
-
-Non-Recursive Iteration
------------------------
-
-Each node and shortcut contains a back pointer to its parent and the number of
-slot in that parent that points to it. None-recursive iteration uses these to
-proceed rootwards through the tree, going to the parent node, slot N + 1 to
-make sure progress is made without the need for a stack.
-
-The backpointers, however, make simultaneous alteration and iteration tricky.
-
-
-Simultaneous Alteration And Iteration
--------------------------------------
-
-There are a number of cases to consider:
-
-1. Simple insert/replace. This involves simply replacing a NULL or old
- matching leaf pointer with the pointer to the new leaf after a barrier.
- The metadata blocks don't change otherwise. An old leaf won't be freed
- until after the RCU grace period.
-
-2. Simple delete. This involves just clearing an old matching leaf. The
- metadata blocks don't change otherwise. The old leaf won't be freed until
- after the RCU grace period.
-
-3. Insertion replacing part of a subtree that we haven't yet entered. This
- may involve replacement of part of that subtree - but that won't affect
- the iteration as we won't have reached the pointer to it yet and the
- ancestry blocks are not replaced (the layout of those does not change).
-
-4. Insertion replacing nodes that we're actively processing. This isn't a
- problem as we've passed the anchoring pointer and won't switch onto the
- new layout until we follow the back pointers - at which point we've
- already examined the leaves in the replaced node (we iterate over all the
- leaves in a node before following any of its metadata pointers).
-
- We might, however, re-see some leaves that have been split out into a new
- branch that's in a slot further along than we were at.
-
-5. Insertion replacing nodes that we're processing a dependent branch of.
- This won't affect us until we follow the back pointers. Similar to (4).
-
-6. Deletion collapsing a branch under us. This doesn't affect us because the
- back pointers will get us back to the parent of the new node before we
- could see the new node. The entire collapsed subtree is thrown away
- unchanged - and will still be rooted on the same slot, so we shouldn't
- process it a second time as we'll go back to slot + 1.
-
-.. note::
-
- Under some circumstances, we need to simultaneously change the parent
- pointer and the parent slot pointer on a node (say, for example, we
- inserted another node before it and moved it up a level). We cannot do
- this without locking against a read - so we have to replace that node too.
-
- However, when we're changing a shortcut into a node this isn't a problem
- as shortcuts only have one slot and so the parent slot number isn't used
- when traversing backwards over one. This means that it's okay to change
- the slot number first - provided suitable barriers are used to make sure
- the parent slot number is read after the back pointer.
-
-Obsolete blocks and leaves are freed up after an RCU grace period has passed,
-so as long as anyone doing walking or iteration holds the RCU read lock, the
-old superstructure should not go away on them.
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index 92f91c6a0d79..d56c60663b0c 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -38,7 +38,6 @@ Library functionality that is used throughout the kernel.
kobject
kref
cleanup
- assoc_array
folio_queue
xarray
maple_tree
diff --git a/Documentation/translations/zh_CN/core-api/assoc_array.rst b/Documentation/translations/zh_CN/core-api/assoc_array.rst
deleted file mode 100644
index 3649bf0d1488..000000000000
--- a/Documentation/translations/zh_CN/core-api/assoc_array.rst
+++ /dev/null
@@ -1,473 +0,0 @@
-.. include:: ../disclaimer-zh_CN.rst
-
-:Original: Documentation/core-api/assoc_array.rst
-
-:翻译:
-
- å¸å»¶è…¾ Yanteng Si <siyanteng at loongson.cn>
-
-:æ ¡è¯‘:
-
-
-
-.. _cn_core-api_assoc_array:
-
-==================
-通用关è”数组的实现
-==================
-
-简介
-====
-
-这个关è”数组的实现是一个具有以下属性的对象容器:
-
-1. 对象是ä¸é€æ˜Žçš„指针。该实现ä¸å…³å¿ƒå®ƒä»¬æŒ‡å‘哪里（如果有的è¯ï¼‰æˆ–它们指å‘什么（如果有的
- è¯ï¼‰ã€‚
-
- .. note::
-
- 指å‘对象的指针 *å¿…é¡»* 在最å°æœ‰æ•ˆä½ä¸ºé›¶ã€‚
-
-2. 对象ä¸éœ€è¦åŒ…å«ä¾›æ•°ç»„使用的链接å—。这å…许一个对象åŒæ—¶ä½äºŽå¤šä¸ªæ•°ç»„ä¸ã€‚相å，数组是
- 由指å‘对象的元数æ®å—组æˆçš„。
-
-3. 对象需è¦ç´¢å¼•é”®æ¥å®šä½å®ƒä»¬åœ¨é˜µåˆ—ä¸çš„ä½ç½®ã€‚
-
-4. 索引键必须是唯一的。æ’入一个与已ç»åœ¨æ•°ç»„ä¸çš„且具有相åŒé”®å€¼çš„对象将å–代旧的对象。
-
-5. 索引键å¯ä»¥æ˜¯ä»»ä½•é•¿åº¦ï¼Œä¹Ÿå¯ä»¥æ˜¯ä¸åŒçš„长度。
-
-6. 索引键应该在早期就对长度进行编ç ，å³åœ¨ä»»ä½•ç”±äºŽé•¿åº¦å¼•èµ·çš„å˜åŒ–出现之å‰ã€‚
-
-7. 索引键å¯ä»¥åŒ…括一个哈希值，以便将对象分散到整个数组ä¸ã€‚
-
-8. 该数组å¯ä»¥è¿ä»£ã€‚对象ä¸ä¸€å®šä¼šæŒ‰ç´¢å¼•é”®çš„顺åºå‡ºçŽ°ã€‚
-
-9. 数组å¯ä»¥åœ¨è¢«ä¿®æ”¹çš„时候进行è¿ä»£ï¼Œåªè¦RCU的读é”被è¿ä»£å™¨æŒæœ‰ã€‚然而，请注æ„，在这ç§æƒ…
- 况下，一些对象å¯èƒ½ä¼šè¢«çœ‹åˆ°ä¸æ¢ä¸€æ¬¡ã€‚如果这是个问题，è¿ä»£å™¨åº”该é”定以防æ¢ä¿®æ”¹ã€‚然
- 而，除éžåˆ 除，å¦åˆ™å¯¹è±¡ä¸ä¼šè¢«é”™è¿‡ã€‚
-
-10. 数组ä¸çš„对象å¯ä»¥é€šè¿‡å…¶ç´¢å¼•é”®è¿›è¡ŒæŸ¥è¯¢ã€‚
-
-11. 当数组被修改时，对象å¯ä»¥è¢«æŸ¥è¯¢ï¼Œå‰æ是进行查询的线程æŒæœ‰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;
-
-有两个处ç†è„šæœ¬çš„功能:
-
-1. 应用一个编辑脚本::
-
- void assoc_array_apply_edit(struct assoc_array_edit *edit);
-
-这将执行编辑功能，æ’值å„ç§å†™å±éšœï¼Œä»¥å…许在RCU读é”下的访问继ç»è¿›è¡Œã€‚然åŽï¼Œç¼–辑脚本将被
-ä¼ é€’ç»™ ``call_rcu()`` ，以释放它和它所指å‘的任何æ»çš„东西。
-
-2. Cancel an edit script::
-
- void assoc_array_cancel_edit(struct assoc_array_edit *edit);
-
-这将立å³é‡Šæ”¾ç¼–辑脚本和所有预分é…的内å˜ã€‚如果这是为了æ’入，新的对象ä¸ä¼šè¢«è¿™ä¸ªå‡½æ•°é‡Šæ”¾ï¼Œ
-而是必须由调用者释放。
-
-这些函数ä¿è¯ä¸ä¼šå¤±è´¥ã€‚
-
-
-æ“作表
-------
-
-å„ç§åŠŸèƒ½é‡‡ç”¨äº†ä¸€ä¸ªæ“作表::
-
- struct assoc_array_ops {
- ...
- };
-
-这指出了一些方法，所有这些方法都需è¦æä¾›:
-
-1. 从调用者数æ®ä¸èŽ·å–索引键的一个å—::
-
- unsigned long (*get_key_chunk)(const void *index_key, int level);
-
-这应该返回一个由调用者æ供的索引键的å—，从levelå‚数给出的 *比特* ä½ç½®å¼€å§‹ã€‚levelå‚æ•°å°†
-是 ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` çš„å€æ•°ï¼Œè¯¥å‡½æ•°åº”返回 ``ASSOC_ARRAY_KEY_CHUNK_SIZE``
-ä½ã€‚ä¸å¯èƒ½å‡ºçŽ°é”™è¯¯ã€‚
-
-
-2. 获å–一个对象的索引键的一个å—::
-
- unsigned long (*get_object_key_chunk)(const void *object, int level);
-
-å’Œå‰é¢çš„å‡½æ•°ä¸€æ ·ï¼Œä½†æ˜¯ä»Žæ•°ç»„ä¸çš„一个对象而ä¸æ˜¯ä»Žè°ƒç”¨è€…æ供的索引键ä¸èŽ·å–æ•°æ®ã€‚
-
-
-3. 看看这是å¦æ˜¯æˆ‘们è¦æ‰¾çš„对象::
-
- bool (*compare_object)(const void *object, const void *index_key);
-
-将对象与一个索引键进行比较，如果匹é…则返回 ``true`` ，ä¸åŒ¹é…则返回 ``false`` 。
-
-
-4. 对两个对象的索引键进行比较::
-
- int (*diff_objects)(const void *object, const void *index_key);
-
-返回指定对象的索引键与给定索引键ä¸åŒçš„比特ä½ç½®ï¼Œå¦‚果它们相åŒï¼Œåˆ™è¿”回-1。
-
-
-5. 释放一个对象::
-
- void (*free_object)(void *object);
-
-释放指定的对象。注æ„，这å¯èƒ½æ˜¯åœ¨è°ƒç”¨ ``assoc_array_apply_edit()`` åŽçš„一个RCU宽é™æœŸå†…
-调用的，所以在模å—å¸è½½æ—¶å¯èƒ½éœ€è¦ ``synchronize_rcu()`` 。
-
-
-æ“控函数
---------
-
-有一些函数用于æ“控关è”数组:
-
-1. åˆå§‹åŒ–一个关è”数组::
-
- void assoc_array_init(struct assoc_array *array);
-
-这将åˆå§‹åŒ–一个关è”数组的基础结构。它ä¸ä¼šå¤±è´¥ã€‚
-
-
-2. 在一个关è”数组ä¸æ’å…¥/替æ¢ä¸€ä¸ªå¯¹è±¡::
-
- struct assoc_array_edit *
- assoc_array_insert(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key,
- void *object);
-
-这将把给定的对象æ’入数组ä¸ã€‚注æ„，指针的最å°æœ‰æ•ˆä½å¿…须是0ï¼Œå› ä¸ºå®ƒè¢«ç”¨æ¥åœ¨å†…éƒ¨æ ‡è®°æŒ‡é’ˆçš„ç±»
-型。
-
-如果该键已ç»å˜åœ¨ä¸€ä¸ªå¯¹è±¡ï¼Œé‚£ä¹ˆå®ƒå°†è¢«æ–°çš„对象所å–代，旧的对象将被自动释放。
-
-``index_key`` å‚数应æŒæœ‰ç´¢å¼•é”®ä¿¡æ¯ï¼Œå¹¶åœ¨è°ƒç”¨OPP表ä¸çš„æ–¹æ³•æ—¶ä¼ é€’ç»™å®ƒä»¬ã€‚
-
-这个函数ä¸å¯¹æ•°ç»„本身åšä»»ä½•æ”¹åŠ¨ï¼Œè€Œæ˜¯è¿”回一个必须应用的编辑脚本。如果出现内å˜ä¸è¶³çš„错误，会
-返回 ``-ENOMEM`` 。
-
-调用者应专门é”定数组的其他修改器。
-
-
-3. 从一个关è”数组ä¸åˆ 除一个对象::
-
- struct assoc_array_edit *
- assoc_array_delete(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key);
-
-这将从数组ä¸åˆ 除一个符åˆæŒ‡å®šæ•°æ®çš„对象。
-
-``index_key`` å‚数应æŒæœ‰ç´¢å¼•é”®ä¿¡æ¯ï¼Œå¹¶åœ¨è°ƒç”¨OPP表ä¸çš„æ–¹æ³•æ—¶ä¼ é€’ç»™å®ƒä»¬ã€‚
-
-这个函数ä¸å¯¹æ•°ç»„本身åšä»»ä½•æ”¹åŠ¨ï¼Œè€Œæ˜¯è¿”回一个必须应用的编辑脚本。 ``-ENOMEM`` 在出现内å˜ä¸è¶³
-的错误时返回。如果在数组ä¸æ²¡æœ‰æ‰¾åˆ°æŒ‡å®šçš„对象，将返回 ``NULL`` 。
-
-调用者应该对数组的其他修改者进行专门é”定。
-
-
-4. 从一个关è”数组ä¸åˆ 除所有对象::
-
- struct assoc_array_edit *
- assoc_array_clear(struct assoc_array *array,
- const struct assoc_array_ops *ops);
-
-è¿™ä¸ªå‡½æ•°åˆ é™¤äº†ä¸€ä¸ªå…³è”数组ä¸çš„所有对象，使其完全为空。
-
-这个函数没有对数组本身åšä»»ä½•æ”¹åŠ¨ï¼Œè€Œæ˜¯è¿”回一个必须应用的编辑脚本。如果出现内å˜ä¸è¶³
-的错误，则返回 ``-ENOMEM`` 。
-
-调用者应专门é”定数组的其他修改者。
-
-
-5. 销æ¯ä¸€ä¸ªå…³è”æ•°ç»„ï¼Œåˆ é™¤æ‰€æœ‰å¯¹è±¡::
-
- void assoc_array_destroy(struct assoc_array *array,
- const struct assoc_array_ops *ops);
-
-è¿™å°†ç ´åå…³è”数组的内容，使其完全为空。在这个函数销æ¯æ•°ç»„çš„åŒæ—¶ï¼Œä¸å…许å¦ä¸€ä¸ªçº¿ç¨‹åœ¨RCU读é”
-下éåŽ†æ•°ç»„ï¼Œå› ä¸ºåœ¨å†…å˜é‡Šæ”¾æ—¶ä¸æ‰§è¡ŒRCU延迟，这需è¦åˆ†é…内å˜ã€‚
-
-调用者应该专门针对数组的其他修改者和访问者进行é”定。
-
-
-6. 垃圾回收一个关è”数组::
-
- 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`` ，它必须
-在返回之å‰å¯¹è¯¥å¯¹è±¡è¿›è¡Œé€‚当的 ``refcount`` 递增。
-
-如果å¯èƒ½çš„è¯ï¼Œå†…éƒ¨æ ‘å°†è¢«æ‰“åŒ…ä¸‹æ¥ï¼Œä½œä¸ºè¿ä»£çš„一部分，以å‡å°‘å…¶ä¸çš„节点数é‡ã€‚
-
-``iterator_data`` è¢«ç›´æŽ¥ä¼ é€’ç»™ ``iterator()`` ，å¦åˆ™ä¼šè¢«å‡½æ•°å¿½ç•¥ã€‚
-
-如果æˆåŠŸï¼Œè¯¥å‡½æ•°å°†è¿”回 ``0`` ，如果没有足够的内å˜ï¼Œåˆ™è¿”回 ``-ENOMEM`` 。
-
-在这个函数执行过程ä¸ï¼Œå…¶ä»–线程有å¯èƒ½åœ¨RCU读é”下è¿ä»£æˆ–æœç´¢é˜µåˆ—。调用者应该专门针对数组的其他
-修改者进行é”定。
-
-
-访问函数
---------
-
-有两个函数用于访问一个关è”数组:
-
-1. é历一个关è”数组ä¸çš„所有对象::
-
- int assoc_array_iterate(const struct assoc_array *array,
- int (*iterator)(const void *object,
- void *iterator_data),
- void *iterator_data);
-
-这将数组ä¸çš„æ¯ä¸ªå¯¹è±¡ä¼ 递给è¿ä»£å™¨å›žè°ƒå‡½æ•°ã€‚ ``iterator_data`` 是该函数的ç§æœ‰æ•°æ®ã€‚
-
-在数组被修改的åŒæ—¶ï¼Œå¯ä»¥åœ¨æ•°ç»„上使用这个方法，å‰æ是RCU读é”被æŒæœ‰ã€‚在这ç§æƒ…况下，è¿ä»£å‡½æ•°æœ‰
-å¯èƒ½ä¸¤æ¬¡çœ‹åˆ°æŸäº›å¯¹è±¡ã€‚如果这是个问题，那么修改应该被é”定。然而，è¿ä»£ç®—法ä¸åº”该错过任何对象。
-
-如果数组ä¸æ²¡æœ‰å¯¹è±¡ï¼Œè¯¥å‡½æ•°å°†è¿”回 ``0`` ，å¦åˆ™å°†è¿”回最åŽä¸€æ¬¡è°ƒç”¨çš„è¿ä»£å™¨å‡½æ•°çš„结果。如果对è¿ä»£å‡½æ•°
-的任何调用导致éžé›¶è¿”回，è¿ä»£ç«‹å³åœæ¢ã€‚
-
-
-2. 在一个关è”数组ä¸å¯»æ‰¾ä¸€ä¸ªå¯¹è±¡::
-
- void *assoc_array_find(const struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key);
-
-è¿™å°†ç›´æŽ¥ç©¿è¿‡æ•°ç»„çš„å†…éƒ¨æ ‘ï¼Œåˆ°è¾¾ç´¢å¼•é”®æ‰€æŒ‡å®šçš„å¯¹è±¡ã€‚
-
-这个函数å¯ä»¥åœ¨ä¿®æ”¹æ•°ç»„çš„åŒæ—¶ç”¨åœ¨æ•°ç»„上，å‰æ是RCU读é”被æŒæœ‰ã€‚
-
-如果找到对象，该函数将返回对象（并将 ``*_type`` 设置为对象的类型），如果没有找到对象，将返回 ``NULL`` 。
-
-
-索引键形å¼
-----------
-
-索引键å¯ä»¥æ˜¯ä»»ä½•å½¢å¼çš„，但是由于算法没有被告知键有多长，所以强烈建议在任何由于长度而产生的å˜åŒ–
-对比较产生影å“之å‰ï¼Œç´¢å¼•é”®åº”该很早就包括其长度。
-
-这将导致具有ä¸åŒé•¿åº¦é”®çš„å¶å相互分散，而具有相åŒé•¿åº¦é”®çš„å¶å则èšé›†åœ¨ä¸€èµ·ã€‚
-
-我们还建议索引键以键的其余部分的哈希值开始，以最大é™åº¦åœ°æ高整个键空间的散布情况。
-
-åˆ†æ•£æ€§è¶Šå¥½ï¼Œå†…éƒ¨æ ‘å°±è¶Šå®½ï¼Œè¶Šä½Žã€‚
-
-分散性差并ä¸æ˜¯ä¸€ä¸ªå¤ªå¤§çš„é—®é¢˜ï¼Œå› ä¸ºæœ‰å¿«æ·é”®ï¼ŒèŠ‚点å¯ä»¥åŒ…å«å¶å和元数æ®æŒ‡é’ˆçš„æ··åˆç‰©ã€‚
-
-索引键是以机器å—çš„å—状æ¥è¯»å–的。æ¯ä¸ªå—被细分为æ¯å±‚一个nibble（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，以确ä¿åœ¨æ²¡æœ‰å †æ ˆçš„情况下å–得进展。
-
-然而，åå‘指针使得åŒæ—¶æ”¹å˜å’Œè¿ä»£å˜å¾—很棘手。
-
-
-åŒæ—¶æ”¹å˜å’Œè¿ä»£
---------------
-
-有一些情况需è¦è€ƒè™‘:
-
-1. 简å•çš„æ’å…¥/替æ¢ã€‚这涉åŠåˆ°ç®€å•åœ°å°†ä¸€ä¸ªNULL或旧的匹é…å¶å的指针替æ¢ä¸ºå±éšœåŽçš„æ–°å¶å的指针。å¦åˆ™å…ƒæ•°
- æ®å—ä¸ä¼šæ”¹å˜ã€‚一个旧的å¶å直到RCU宽é™æœŸè¿‡åŽæ‰ä¼šè¢«é‡Šæ”¾ã€‚
-
-2. 简å•åˆ 除。这åªæ˜¯æ¶‰åŠåˆ°æ¸…除一个旧的匹é…å¶å。元数æ®å—ä¸ä¼šæœ‰å…¶ä»–å˜åŒ–。旧的å¶å直到RCU宽é™æœŸä¹‹åŽæ‰ä¼š
- 被释放。
-
-3. æ’入，替æ¢æˆ‘们还没有进入的åæ ‘çš„ä¸€éƒ¨åˆ†ã€‚è¿™å¯èƒ½æ¶‰åŠåˆ°æ›¿æ¢è¯¥åæ ‘çš„ä¸€éƒ¨åˆ†â€”â€”ä½†è¿™ä¸ä¼šå½±å“è¿ä»£ï¼Œå› 为我们
- 还没有到达它的指针，而且祖先å—也ä¸ä¼šè¢«æ›¿æ¢ï¼ˆè¿™äº›å—的布局ä¸ä¼šæ”¹å˜ï¼‰ã€‚
-
-4. æ’入替æ¢äº†æˆ‘们æ£åœ¨å¤„ç†çš„节点。这ä¸æ˜¯ä¸€ä¸ªé—®é¢˜ï¼Œå› 为我们已ç»é€šè¿‡äº†é”šå®šæŒ‡é’ˆï¼Œç›´åˆ°æˆ‘们跟éšåŽé¢çš„指针æ‰
- 会切æ¢åˆ°æ–°çš„布局上——这时我们已ç»æ£€æŸ¥äº†è¢«æ›¿æ¢èŠ‚点的å¶å（在跟éšä»»ä½•å…ƒæ•°æ®æŒ‡é’ˆä¹‹å‰ï¼Œæˆ‘们会è¿ä»£ä¸€ä¸ªèŠ‚
- 点的所有å¶å）。
-
- 然而，我们å¯èƒ½ä¼šé‡æ–°çœ‹åˆ°ä¸€äº›å¶å，这些å¶åå·²ç»è¢«åˆ†å‰²æˆä¸€ä¸ªæ–°çš„分支，而这个分支的ä½ç½®æ¯”我们之å‰çš„ä½
- 置更远。
-
-5. æ’入替æ¢äº†æˆ‘们æ£åœ¨å¤„ç†çš„ä¾èµ–分支的节点。这ä¸ä¼šå½±å“到我们，直到我们跟éšåŽé¢çš„指针。与（4）类似。
-
-6. åˆ æŽ‰æˆ‘ä»¬ä¸‹é¢çš„一个分支。这ä¸ä¼šå½±å“æˆ‘ä»¬ï¼Œå› ä¸ºåœ¨æˆ‘ä»¬çœ‹åˆ°æ–°èŠ‚ç‚¹ä¹‹å‰ï¼Œå›žæº¯æŒ‡é’ˆä¼šè®©æˆ‘们回到新节点的父节
- 点。整个崩溃的åæ ‘è¢«æ‰”æŽ‰äº†ï¼Œæ²¡æœ‰ä»»ä½•å˜åŒ–——而且ä»ç„¶ä¼šåœ¨åŒä¸€ä¸ªæ§½ä¸Šç”Ÿæ ¹ï¼Œæ‰€ä»¥æˆ‘们ä¸åº”该第二次处ç†å®ƒï¼Œ
- å› ä¸ºæˆ‘ä»¬ä¼šå›žåˆ°æ§½+1。
-
-.. note::
-
- 在æŸäº›æƒ…况下，我们需è¦åŒæ—¶æ”¹å˜ä¸€ä¸ªèŠ‚点的父指针和父槽指针（比如说，我们在它之å‰æ’入了å¦ä¸€ä¸ªèŠ‚点，
- 并把它往上移了一层）。我们ä¸èƒ½åœ¨ä¸é”定读å–çš„æƒ…å†µä¸‹è¿™æ ·åšâ€”—所以我们必须åŒæ—¶æ›¿æ¢è¯¥èŠ‚点。
-
- 然而，当我们把一个快æ·é”®æ”¹æˆä¸€ä¸ªèŠ‚点时，这ä¸æ˜¯ä¸€ä¸ªé—®é¢˜ï¼Œå› 为快æ·é”®åªæœ‰ä¸€ä¸ªæ§½ï¼Œæ‰€ä»¥å½“å‘åŽé
- 历一个槽时，ä¸ä¼šä½¿ç”¨çˆ¶æ§½å·ã€‚è¿™æ„味ç€å…ˆæ”¹å˜æ§½ä½å·æ˜¯å¯ä»¥çš„——åªè¦ä½¿ç”¨é€‚当的å±éšœæ¥ç¡®ä¿çˆ¶æ§½ä½å·åœ¨åŽ
- 退指针之åŽè¢«è¯»å–。
-
-过时的å—å’Œå¶å在RCU宽é™æœŸè¿‡åŽä¼šè¢«é‡Šæ”¾ï¼Œæ‰€ä»¥åªè¦ä»»ä½•è¿›è¡Œé历或è¿ä»£çš„人æŒæœ‰RCU读é”，旧的上层建ç‘å°±ä¸
-应该在他们身上消失。
diff --git a/Documentation/translations/zh_CN/core-api/index.rst b/Documentation/translations/zh_CN/core-api/index.rst
index 453a02cd1f44..ec4b03b2a0a6 100644
--- a/Documentation/translations/zh_CN/core-api/index.rst
+++ b/Documentation/translations/zh_CN/core-api/index.rst
@@ -41,7 +41,6 @@
kobject
kref
- assoc_array
xarray
rbtree
idr
diff --git a/include/linux/assoc_array.h b/include/linux/assoc_array.h
deleted file mode 100644
index 8b3f230ce894..000000000000
--- a/include/linux/assoc_array.h
+++ /dev/null
@@ -1,88 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0-or-later */
-/* Generic associative array implementation.
- *
- * See Documentation/core-api/assoc_array.rst for information.
- *
- * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
- * Written by David Howells (dhowells at redhat.com)
- */
-
-#ifndef _LINUX_ASSOC_ARRAY_H
-#define _LINUX_ASSOC_ARRAY_H
-
-#ifdef CONFIG_ASSOCIATIVE_ARRAY
-
-#include <linux/types.h>
-
-#define ASSOC_ARRAY_KEY_CHUNK_SIZE BITS_PER_LONG /* Key data retrieved in chunks of this size */
-
-/*
- * Generic associative array.
- */
-struct assoc_array {
- struct assoc_array_ptr *root; /* The node at the root of the tree */
- unsigned long nr_leaves_on_tree;
-};
-
-/*
- * Operations on objects and index keys for use by array manipulation routines.
- */
-struct assoc_array_ops {
- /* Method to get a chunk of an index key from caller-supplied data */
- unsigned long (*get_key_chunk)(const void *index_key, int level);
-
- /* Method to get a piece of an object's index key */
- unsigned long (*get_object_key_chunk)(const void *object, int level);
-
- /* Is this the object we're looking for? */
- bool (*compare_object)(const void *object, const void *index_key);
-
- /* How different is an object from an index key, to a bit position in
- * their keys? (or -1 if they're the same)
- */
- int (*diff_objects)(const void *object, const void *index_key);
-
- /* Method to free an object. */
- void (*free_object)(void *object);
-};
-
-/*
- * Access and manipulation functions.
- */
-struct assoc_array_edit;
-
-static inline void assoc_array_init(struct assoc_array *array)
-{
- array->root = NULL;
- array->nr_leaves_on_tree = 0;
-}
-
-extern int assoc_array_iterate(const struct assoc_array *array,
- int (*iterator)(const void *object,
- void *iterator_data),
- void *iterator_data);
-extern void *assoc_array_find(const struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key);
-extern void assoc_array_destroy(struct assoc_array *array,
- const struct assoc_array_ops *ops);
-extern struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key,
- void *object);
-extern void assoc_array_insert_set_object(struct assoc_array_edit *edit,
- void *object);
-extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key);
-extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
- const struct assoc_array_ops *ops);
-extern void assoc_array_apply_edit(struct assoc_array_edit *edit);
-extern void assoc_array_cancel_edit(struct assoc_array_edit *edit);
-extern int assoc_array_gc(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- bool (*iterator)(void *object, void *iterator_data),
- void *iterator_data);
-
-#endif /* CONFIG_ASSOCIATIVE_ARRAY */
-#endif /* _LINUX_ASSOC_ARRAY_H */
diff --git a/include/linux/assoc_array_priv.h b/include/linux/assoc_array_priv.h
deleted file mode 100644
index dca733ef6750..000000000000
--- a/include/linux/assoc_array_priv.h
+++ /dev/null
@@ -1,178 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0-or-later */
-/* Private definitions for the generic associative array implementation.
- *
- * See Documentation/core-api/assoc_array.rst for information.
- *
- * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
- * Written by David Howells (dhowells at redhat.com)
- */
-
-#ifndef _LINUX_ASSOC_ARRAY_PRIV_H
-#define _LINUX_ASSOC_ARRAY_PRIV_H
-
-#ifdef CONFIG_ASSOCIATIVE_ARRAY
-
-#include <linux/assoc_array.h>
-
-#define ASSOC_ARRAY_FAN_OUT 16 /* Number of slots per node */
-#define ASSOC_ARRAY_FAN_MASK (ASSOC_ARRAY_FAN_OUT - 1)
-#define ASSOC_ARRAY_LEVEL_STEP (ilog2(ASSOC_ARRAY_FAN_OUT))
-#define ASSOC_ARRAY_LEVEL_STEP_MASK (ASSOC_ARRAY_LEVEL_STEP - 1)
-#define ASSOC_ARRAY_KEY_CHUNK_MASK (ASSOC_ARRAY_KEY_CHUNK_SIZE - 1)
-#define ASSOC_ARRAY_KEY_CHUNK_SHIFT (ilog2(BITS_PER_LONG))
-
-/*
- * Undefined type representing a pointer with type information in the bottom
- * two bits.
- */
-struct assoc_array_ptr;
-
-/*
- * An N-way node in the tree.
- *
- * Each slot contains one of four things:
- *
- * (1) Nothing (NULL).
- *
- * (2) A leaf object (pointer types 0).
- *
- * (3) A next-level node (pointer type 1, subtype 0).
- *
- * (4) A shortcut (pointer type 1, subtype 1).
- *
- * The tree is optimised for search-by-ID, but permits reasonable iteration
- * also.
- *
- * The tree is navigated by constructing an index key consisting of an array of
- * segments, where each segment is ilog2(ASSOC_ARRAY_FAN_OUT) bits in size.
- *
- * The segments correspond to levels of the tree (the first segment is used at
- * level 0, the second at level 1, etc.).
- */
-struct assoc_array_node {
- struct assoc_array_ptr *back_pointer;
- u8 parent_slot;
- struct assoc_array_ptr *slots[ASSOC_ARRAY_FAN_OUT];
- unsigned long nr_leaves_on_branch;
-};
-
-/*
- * A shortcut through the index space out to where a collection of nodes/leaves
- * with the same IDs live.
- */
-struct assoc_array_shortcut {
- struct assoc_array_ptr *back_pointer;
- int parent_slot;
- int skip_to_level;
- struct assoc_array_ptr *next_node;
- unsigned long index_key[];
-};
-
-/*
- * Preallocation cache.
- */
-struct assoc_array_edit {
- struct rcu_head rcu;
- struct assoc_array *array;
- const struct assoc_array_ops *ops;
- const struct assoc_array_ops *ops_for_excised_subtree;
- struct assoc_array_ptr *leaf;
- struct assoc_array_ptr **leaf_p;
- struct assoc_array_ptr *dead_leaf;
- struct assoc_array_ptr *new_meta[3];
- struct assoc_array_ptr *excised_meta[1];
- struct assoc_array_ptr *excised_subtree;
- struct assoc_array_ptr **set_backpointers[ASSOC_ARRAY_FAN_OUT];
- struct assoc_array_ptr *set_backpointers_to;
- struct assoc_array_node *adjust_count_on;
- long adjust_count_by;
- struct {
- struct assoc_array_ptr **ptr;
- struct assoc_array_ptr *to;
- } set[2];
- struct {
- u8 *p;
- u8 to;
- } set_parent_slot[1];
- u8 segment_cache[ASSOC_ARRAY_FAN_OUT + 1];
-};
-
-/*
- * Internal tree member pointers are marked in the bottom one or two bits to
- * indicate what type they are so that we don't have to look behind every
- * pointer to see what it points to.
- *
- * We provide functions to test type annotations and to create and translate
- * the annotated pointers.
- */
-#define ASSOC_ARRAY_PTR_TYPE_MASK 0x1UL
-#define ASSOC_ARRAY_PTR_LEAF_TYPE 0x0UL /* Points to leaf (or nowhere) */
-#define ASSOC_ARRAY_PTR_META_TYPE 0x1UL /* Points to node or shortcut */
-#define ASSOC_ARRAY_PTR_SUBTYPE_MASK 0x2UL
-#define ASSOC_ARRAY_PTR_NODE_SUBTYPE 0x0UL
-#define ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE 0x2UL
-
-static inline bool assoc_array_ptr_is_meta(const struct assoc_array_ptr *x)
-{
- return (unsigned long)x & ASSOC_ARRAY_PTR_TYPE_MASK;
-}
-static inline bool assoc_array_ptr_is_leaf(const struct assoc_array_ptr *x)
-{
- return !assoc_array_ptr_is_meta(x);
-}
-static inline bool assoc_array_ptr_is_shortcut(const struct assoc_array_ptr *x)
-{
- return (unsigned long)x & ASSOC_ARRAY_PTR_SUBTYPE_MASK;
-}
-static inline bool assoc_array_ptr_is_node(const struct assoc_array_ptr *x)
-{
- return !assoc_array_ptr_is_shortcut(x);
-}
-
-static inline void *assoc_array_ptr_to_leaf(const struct assoc_array_ptr *x)
-{
- return (void *)((unsigned long)x & ~ASSOC_ARRAY_PTR_TYPE_MASK);
-}
-
-static inline
-unsigned long __assoc_array_ptr_to_meta(const struct assoc_array_ptr *x)
-{
- return (unsigned long)x &
- ~(ASSOC_ARRAY_PTR_SUBTYPE_MASK | ASSOC_ARRAY_PTR_TYPE_MASK);
-}
-static inline
-struct assoc_array_node *assoc_array_ptr_to_node(const struct assoc_array_ptr *x)
-{
- return (struct assoc_array_node *)__assoc_array_ptr_to_meta(x);
-}
-static inline
-struct assoc_array_shortcut *assoc_array_ptr_to_shortcut(const struct assoc_array_ptr *x)
-{
- return (struct assoc_array_shortcut *)__assoc_array_ptr_to_meta(x);
-}
-
-static inline
-struct assoc_array_ptr *__assoc_array_x_to_ptr(const void *p, unsigned long t)
-{
- return (struct assoc_array_ptr *)((unsigned long)p | t);
-}
-static inline
-struct assoc_array_ptr *assoc_array_leaf_to_ptr(const void *p)
-{
- return __assoc_array_x_to_ptr(p, ASSOC_ARRAY_PTR_LEAF_TYPE);
-}
-static inline
-struct assoc_array_ptr *assoc_array_node_to_ptr(const struct assoc_array_node *p)
-{
- return __assoc_array_x_to_ptr(
- p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_NODE_SUBTYPE);
-}
-static inline
-struct assoc_array_ptr *assoc_array_shortcut_to_ptr(const struct assoc_array_shortcut *p)
-{
- return __assoc_array_x_to_ptr(
- p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE);
-}
-
-#endif /* CONFIG_ASSOCIATIVE_ARRAY */
-#endif /* _LINUX_ASSOC_ARRAY_PRIV_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 4e6b34c3346d..9b3dd46c6799 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -349,20 +349,6 @@ config XARRAY_MULTI
Support entries which occupy multiple consecutive indices in the
XArray.
-config ASSOCIATIVE_ARRAY
- bool
- help
- Generic associative array. Can be searched and iterated over whilst
- it is being modified. It is also reasonably quick to search and
- modify. The algorithms are non-recursive, and the trees are highly
- capacious.
-
- See:
-
- Documentation/core-api/assoc_array.rst
-
- for more information.
-
config CLOSURES
bool
diff --git a/lib/Makefile b/lib/Makefile
index dfab958327c5..a2cdff9a60ea 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -141,7 +141,6 @@ obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
obj-$(CONFIG_BTREE) += btree.o
obj-$(CONFIG_INTERVAL_TREE) += interval_tree.o
-obj-$(CONFIG_ASSOCIATIVE_ARRAY) += assoc_array.o
obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
obj-$(CONFIG_LIST_HARDENED) += list_debug.o
obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
diff --git a/lib/assoc_array.c b/lib/assoc_array.c
deleted file mode 100644
index b6c9723e12ce..000000000000
--- a/lib/assoc_array.c
+++ /dev/null
@@ -1,1724 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0-or-later
-/* Generic associative array implementation.
- *
- * See Documentation/core-api/assoc_array.rst for information.
- *
- * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
- * Written by David Howells (dhowells at redhat.com)
- */
-//#define DEBUG
-#include <linux/rcupdate.h>
-#include <linux/slab.h>
-#include <linux/err.h>
-#include <linux/assoc_array_priv.h>
-
-/*
- * Iterate over an associative array. The caller must hold the RCU read lock
- * or better.
- */
-static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
- const struct assoc_array_ptr *stop,
- int (*iterator)(const void *leaf,
- void *iterator_data),
- void *iterator_data)
-{
- const struct assoc_array_shortcut *shortcut;
- const struct assoc_array_node *node;
- const struct assoc_array_ptr *cursor, *ptr, *parent;
- unsigned long has_meta;
- int slot, ret;
-
- cursor = root;
-
-begin_node:
- if (assoc_array_ptr_is_shortcut(cursor)) {
- /* Descend through a shortcut */
- shortcut = assoc_array_ptr_to_shortcut(cursor);
- cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */
- }
-
- node = assoc_array_ptr_to_node(cursor);
- slot = 0;
-
- /* We perform two passes of each node.
- *
- * The first pass does all the leaves in this node. This means we
- * don't miss any leaves if the node is split up by insertion whilst
- * we're iterating over the branches rooted here (we may, however, see
- * some leaves twice).
- */
- has_meta = 0;
- for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
- has_meta |= (unsigned long)ptr;
- if (ptr && assoc_array_ptr_is_leaf(ptr)) {
- /* We need a barrier between the read of the pointer,
- * which is supplied by the above READ_ONCE().
- */
- /* Invoke the callback */
- ret = iterator(assoc_array_ptr_to_leaf(ptr),
- iterator_data);
- if (ret)
- return ret;
- }
- }
-
- /* The second pass attends to all the metadata pointers. If we follow
- * one of these we may find that we don't come back here, but rather go
- * back to a replacement node with the leaves in a different layout.
- *
- * We are guaranteed to make progress, however, as the slot number for
- * a particular portion of the key space cannot change - and we
- * continue at the back pointer + 1.
- */
- if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
- goto finished_node;
- slot = 0;
-
-continue_node:
- node = assoc_array_ptr_to_node(cursor);
- for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
- if (assoc_array_ptr_is_meta(ptr)) {
- cursor = ptr;
- goto begin_node;
- }
- }
-
-finished_node:
- /* Move up to the parent (may need to skip back over a shortcut) */
- parent = READ_ONCE(node->back_pointer); /* Address dependency. */
- slot = node->parent_slot;
- if (parent == stop)
- return 0;
-
- if (assoc_array_ptr_is_shortcut(parent)) {
- shortcut = assoc_array_ptr_to_shortcut(parent);
- cursor = parent;
- parent = READ_ONCE(shortcut->back_pointer); /* Address dependency. */
- slot = shortcut->parent_slot;
- if (parent == stop)
- return 0;
- }
-
- /* Ascend to next slot in parent node */
- cursor = parent;
- slot++;
- goto continue_node;
-}
-
-/**
- * assoc_array_iterate - Pass all objects in the array to a callback
- * @array: The array to iterate over.
- * @iterator: The callback function.
- * @iterator_data: Private data for the callback function.
- *
- * Iterate over all the objects in an associative array. Each one will be
- * presented to the iterator function.
- *
- * If the array is being modified concurrently with the iteration then it is
- * possible that some objects in the array will be passed to the iterator
- * callback more than once - though every object should be passed at least
- * once. If this is undesirable then the caller must lock against modification
- * for the duration of this function.
- *
- * The function will return 0 if no objects were in the array or else it will
- * return the result of the last iterator function called. Iteration stops
- * immediately if any call to the iteration function results in a non-zero
- * return.
- *
- * The caller should hold the RCU read lock or better if concurrent
- * modification is possible.
- */
-int assoc_array_iterate(const struct assoc_array *array,
- int (*iterator)(const void *object,
- void *iterator_data),
- void *iterator_data)
-{
- struct assoc_array_ptr *root = READ_ONCE(array->root); /* Address dependency. */
-
- if (!root)
- return 0;
- return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data);
-}
-
-enum assoc_array_walk_status {
- assoc_array_walk_tree_empty,
- assoc_array_walk_found_terminal_node,
- assoc_array_walk_found_wrong_shortcut,
-};
-
-struct assoc_array_walk_result {
- struct {
- struct assoc_array_node *node; /* Node in which leaf might be found */
- int level;
- int slot;
- } terminal_node;
- struct {
- struct assoc_array_shortcut *shortcut;
- int level;
- int sc_level;
- unsigned long sc_segments;
- unsigned long dissimilarity;
- } wrong_shortcut;
-};
-
-/*
- * Navigate through the internal tree looking for the closest node to the key.
- */
-static enum assoc_array_walk_status
-assoc_array_walk(const struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key,
- struct assoc_array_walk_result *result)
-{
- struct assoc_array_shortcut *shortcut;
- struct assoc_array_node *node;
- struct assoc_array_ptr *cursor, *ptr;
- unsigned long sc_segments, dissimilarity;
- unsigned long segments;
- int level, sc_level, next_sc_level;
- int slot;
-
- pr_devel("-->%s()\n", __func__);
-
- cursor = READ_ONCE(array->root); /* Address dependency. */
- if (!cursor)
- return assoc_array_walk_tree_empty;
-
- level = 0;
-
- /* Use segments from the key for the new leaf to navigate through the
- * internal tree, skipping through nodes and shortcuts that are on
- * route to the destination. Eventually we'll come to a slot that is
- * either empty or contains a leaf at which point we've found a node in
- * which the leaf we're looking for might be found or into which it
- * should be inserted.
- */
-jumped:
- segments = ops->get_key_chunk(index_key, level);
- pr_devel("segments[%d]: %lx\n", level, segments);
-
- if (assoc_array_ptr_is_shortcut(cursor))
- goto follow_shortcut;
-
-consider_node:
- node = assoc_array_ptr_to_node(cursor);
- slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
- slot &= ASSOC_ARRAY_FAN_MASK;
- ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
-
- pr_devel("consider slot %x [ix=%d type=%lu]\n",
- slot, level, (unsigned long)ptr & 3);
-
- if (!assoc_array_ptr_is_meta(ptr)) {
- /* The node doesn't have a node/shortcut pointer in the slot
- * corresponding to the index key that we have to follow.
- */
- result->terminal_node.node = node;
- result->terminal_node.level = level;
- result->terminal_node.slot = slot;
- pr_devel("<--%s() = terminal_node\n", __func__);
- return assoc_array_walk_found_terminal_node;
- }
-
- if (assoc_array_ptr_is_node(ptr)) {
- /* There is a pointer to a node in the slot corresponding to
- * this index key segment, so we need to follow it.
- */
- cursor = ptr;
- level += ASSOC_ARRAY_LEVEL_STEP;
- if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
- goto consider_node;
- goto jumped;
- }
-
- /* There is a shortcut in the slot corresponding to the index key
- * segment. We follow the shortcut if its partial index key matches
- * this leaf's. Otherwise we need to split the shortcut.
- */
- cursor = ptr;
-follow_shortcut:
- shortcut = assoc_array_ptr_to_shortcut(cursor);
- pr_devel("shortcut to %d\n", shortcut->skip_to_level);
- sc_level = level + ASSOC_ARRAY_LEVEL_STEP;
- BUG_ON(sc_level > shortcut->skip_to_level);
-
- do {
- /* Check the leaf against the shortcut's index key a word at a
- * time, trimming the final word (the shortcut stores the index
- * key completely from the root to the shortcut's target).
- */
- if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0)
- segments = ops->get_key_chunk(index_key, sc_level);
-
- sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
- dissimilarity = segments ^ sc_segments;
-
- if (shortcut->skip_to_level < round_down(sc_level,
- ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) {
- /* Trim segments that are beyond the shortcut */
- int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
- dissimilarity &= ~(ULONG_MAX << shift);
- next_sc_level = shortcut->skip_to_level;
- } else {
- next_sc_level = sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE;
- next_sc_level = round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
- }
-
- if (dissimilarity != 0) {
- /* This shortcut points elsewhere */
- result->wrong_shortcut.shortcut = shortcut;
- result->wrong_shortcut.level = level;
- result->wrong_shortcut.sc_level = sc_level;
- result->wrong_shortcut.sc_segments = sc_segments;
- result->wrong_shortcut.dissimilarity = dissimilarity;
- return assoc_array_walk_found_wrong_shortcut;
- }
-
- sc_level = next_sc_level;
- } while (sc_level < shortcut->skip_to_level);
-
- /* The shortcut matches the leaf's index to this point. */
- cursor = READ_ONCE(shortcut->next_node); /* Address dependency. */
- if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0) {
- level = sc_level;
- goto jumped;
- } else {
- level = sc_level;
- goto consider_node;
- }
-}
-
-/**
- * assoc_array_find - Find an object by index key
- * @array: The associative array to search.
- * @ops: The operations to use.
- * @index_key: The key to the object.
- *
- * Find an object in an associative array by walking through the internal tree
- * to the node that should contain the object and then searching the leaves
- * there. NULL is returned if the requested object was not found in the array.
- *
- * The caller must hold the RCU read lock or better.
- */
-void *assoc_array_find(const struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key)
-{
- struct assoc_array_walk_result result;
- const struct assoc_array_node *node;
- const struct assoc_array_ptr *ptr;
- const void *leaf;
- int slot;
-
- if (assoc_array_walk(array, ops, index_key, &result) !=
- assoc_array_walk_found_terminal_node)
- return NULL;
-
- node = result.terminal_node.node;
-
- /* If the target key is available to us, it's has to be pointed to by
- * the terminal node.
- */
- for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- ptr = READ_ONCE(node->slots[slot]); /* Address dependency. */
- if (ptr && assoc_array_ptr_is_leaf(ptr)) {
- /* We need a barrier between the read of the pointer
- * and dereferencing the pointer - but only if we are
- * actually going to dereference it.
- */
- leaf = assoc_array_ptr_to_leaf(ptr);
- if (ops->compare_object(leaf, index_key))
- return (void *)leaf;
- }
- }
-
- return NULL;
-}
-
-/*
- * Destructively iterate over an associative array. The caller must prevent
- * other simultaneous accesses.
- */
-static void assoc_array_destroy_subtree(struct assoc_array_ptr *root,
- const struct assoc_array_ops *ops)
-{
- struct assoc_array_shortcut *shortcut;
- struct assoc_array_node *node;
- struct assoc_array_ptr *cursor, *parent = NULL;
- int slot = -1;
-
- pr_devel("-->%s()\n", __func__);
-
- cursor = root;
- if (!cursor) {
- pr_devel("empty\n");
- return;
- }
-
-move_to_meta:
- if (assoc_array_ptr_is_shortcut(cursor)) {
- /* Descend through a shortcut */
- pr_devel("[%d] shortcut\n", slot);
- BUG_ON(!assoc_array_ptr_is_shortcut(cursor));
- shortcut = assoc_array_ptr_to_shortcut(cursor);
- BUG_ON(shortcut->back_pointer != parent);
- BUG_ON(slot != -1 && shortcut->parent_slot != slot);
- parent = cursor;
- cursor = shortcut->next_node;
- slot = -1;
- BUG_ON(!assoc_array_ptr_is_node(cursor));
- }
-
- pr_devel("[%d] node\n", slot);
- node = assoc_array_ptr_to_node(cursor);
- BUG_ON(node->back_pointer != parent);
- BUG_ON(slot != -1 && node->parent_slot != slot);
- slot = 0;
-
-continue_node:
- pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
- for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- struct assoc_array_ptr *ptr = node->slots[slot];
- if (!ptr)
- continue;
- if (assoc_array_ptr_is_meta(ptr)) {
- parent = cursor;
- cursor = ptr;
- goto move_to_meta;
- }
-
- if (ops) {
- pr_devel("[%d] free leaf\n", slot);
- ops->free_object(assoc_array_ptr_to_leaf(ptr));
- }
- }
-
- parent = node->back_pointer;
- slot = node->parent_slot;
- pr_devel("free node\n");
- kfree(node);
- if (!parent)
- return; /* Done */
-
- /* Move back up to the parent (may need to free a shortcut on
- * the way up) */
- if (assoc_array_ptr_is_shortcut(parent)) {
- shortcut = assoc_array_ptr_to_shortcut(parent);
- BUG_ON(shortcut->next_node != cursor);
- cursor = parent;
- parent = shortcut->back_pointer;
- slot = shortcut->parent_slot;
- pr_devel("free shortcut\n");
- kfree(shortcut);
- if (!parent)
- return;
-
- BUG_ON(!assoc_array_ptr_is_node(parent));
- }
-
- /* Ascend to next slot in parent node */
- pr_devel("ascend to %p[%d]\n", parent, slot);
- cursor = parent;
- node = assoc_array_ptr_to_node(cursor);
- slot++;
- goto continue_node;
-}
-
-/**
- * assoc_array_destroy - Destroy an associative array
- * @array: The array to destroy.
- * @ops: The operations to use.
- *
- * Discard all metadata and free all objects in an associative array. The
- * array will be empty and ready to use again upon completion. This function
- * cannot fail.
- *
- * The caller must prevent all other accesses whilst this takes place as no
- * attempt is made to adjust pointers gracefully to permit RCU readlock-holding
- * accesses to continue. On the other hand, no memory allocation is required.
- */
-void assoc_array_destroy(struct assoc_array *array,
- const struct assoc_array_ops *ops)
-{
- assoc_array_destroy_subtree(array->root, ops);
- array->root = NULL;
-}
-
-/*
- * Handle insertion into an empty tree.
- */
-static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
-{
- struct assoc_array_node *new_n0;
-
- pr_devel("-->%s()\n", __func__);
-
- new_n0 = kzalloc_obj(struct assoc_array_node);
- if (!new_n0)
- return false;
-
- edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
- edit->leaf_p = &new_n0->slots[0];
- edit->adjust_count_on = new_n0;
- edit->set[0].ptr = &edit->array->root;
- edit->set[0].to = assoc_array_node_to_ptr(new_n0);
-
- pr_devel("<--%s() = ok [no root]\n", __func__);
- return true;
-}
-
-/*
- * Handle insertion into a terminal node.
- */
-static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
- const struct assoc_array_ops *ops,
- const void *index_key,
- struct assoc_array_walk_result *result)
-{
- struct assoc_array_shortcut *shortcut, *new_s0;
- struct assoc_array_node *node, *new_n0, *new_n1, *side;
- struct assoc_array_ptr *ptr;
- unsigned long dissimilarity, base_seg, blank;
- size_t keylen;
- bool have_meta;
- int level, diff;
- int slot, next_slot, free_slot, i, j;
-
- node = result->terminal_node.node;
- level = result->terminal_node.level;
- edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;
-
- pr_devel("-->%s()\n", __func__);
-
- /* We arrived at a node which doesn't have an onward node or shortcut
- * pointer that we have to follow. This means that (a) the leaf we
- * want must go here (either by insertion or replacement) or (b) we
- * need to split this node and insert in one of the fragments.
- */
- free_slot = -1;
-
- /* Firstly, we have to check the leaves in this node to see if there's
- * a matching one we should replace in place.
- */
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- ptr = node->slots[i];
- if (!ptr) {
- free_slot = i;
- continue;
- }
- if (assoc_array_ptr_is_leaf(ptr) &&
- ops->compare_object(assoc_array_ptr_to_leaf(ptr),
- index_key)) {
- pr_devel("replace in slot %d\n", i);
- edit->leaf_p = &node->slots[i];
- edit->dead_leaf = node->slots[i];
- pr_devel("<--%s() = ok [replace]\n", __func__);
- return true;
- }
- }
-
- /* If there is a free slot in this node then we can just insert the
- * leaf here.
- */
- if (free_slot >= 0) {
- pr_devel("insert in free slot %d\n", free_slot);
- edit->leaf_p = &node->slots[free_slot];
- edit->adjust_count_on = node;
- pr_devel("<--%s() = ok [insert]\n", __func__);
- return true;
- }
-
- /* The node has no spare slots - so we're either going to have to split
- * it or insert another node before it.
- *
- * Whatever, we're going to need at least two new nodes - so allocate
- * those now. We may also need a new shortcut, but we deal with that
- * when we need it.
- */
- new_n0 = kzalloc_obj(struct assoc_array_node);
- if (!new_n0)
- return false;
- edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
- new_n1 = kzalloc_obj(struct assoc_array_node);
- if (!new_n1)
- return false;
- edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);
-
- /* We need to find out how similar the leaves are. */
- pr_devel("no spare slots\n");
- have_meta = false;
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- ptr = node->slots[i];
- if (assoc_array_ptr_is_meta(ptr)) {
- edit->segment_cache[i] = 0xff;
- have_meta = true;
- continue;
- }
- base_seg = ops->get_object_key_chunk(
- assoc_array_ptr_to_leaf(ptr), level);
- base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
- edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
- }
-
- if (have_meta) {
- pr_devel("have meta\n");
- goto split_node;
- }
-
- /* The node contains only leaves */
- dissimilarity = 0;
- base_seg = edit->segment_cache[0];
- for (i = 1; i < ASSOC_ARRAY_FAN_OUT; i++)
- dissimilarity |= edit->segment_cache[i] ^ base_seg;
-
- pr_devel("only leaves; dissimilarity=%lx\n", dissimilarity);
-
- if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) == 0) {
- /* The old leaves all cluster in the same slot. We will need
- * to insert a shortcut if the new node wants to cluster with them.
- */
- if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
- goto all_leaves_cluster_together;
-
- /* Otherwise all the old leaves cluster in the same slot, but
- * the new leaf wants to go into a different slot - so we
- * create a new node (n0) to hold the new leaf and a pointer to
- * a new node (n1) holding all the old leaves.
- *
- * This can be done by falling through to the node splitting
- * path.
- */
- pr_devel("present leaves cluster but not new leaf\n");
- }
-
-split_node:
- pr_devel("split node\n");
-
- /* We need to split the current node. The node must contain anything
- * from a single leaf (in the one leaf case, this leaf will cluster
- * with the new leaf) and the rest meta-pointers, to all leaves, some
- * of which may cluster.
- *
- * It won't contain the case in which all the current leaves plus the
- * new leaves want to cluster in the same slot.
- *
- * We need to expel at least two leaves out of a set consisting of the
- * leaves in the node and the new leaf. The current meta pointers can
- * just be copied as they shouldn't cluster with any of the leaves.
- *
- * We need a new node (n0) to replace the current one and a new node to
- * take the expelled nodes (n1).
- */
- edit->set[0].to = assoc_array_node_to_ptr(new_n0);
- new_n0->back_pointer = node->back_pointer;
- new_n0->parent_slot = node->parent_slot;
- new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
- new_n1->parent_slot = -1; /* Need to calculate this */
-
-do_split_node:
- pr_devel("do_split_node\n");
-
- new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
- new_n1->nr_leaves_on_branch = 0;
-
- /* Begin by finding two matching leaves. There have to be at least two
- * that match - even if there are meta pointers - because any leaf that
- * would match a slot with a meta pointer in it must be somewhere
- * behind that meta pointer and cannot be here. Further, given N
- * remaining leaf slots, we now have N+1 leaves to go in them.
- */
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- slot = edit->segment_cache[i];
- if (slot != 0xff)
- for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)
- if (edit->segment_cache[j] == slot)
- goto found_slot_for_multiple_occupancy;
- }
-found_slot_for_multiple_occupancy:
- pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
- BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
- BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
- BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);
-
- new_n1->parent_slot = slot;
-
- /* Metadata pointers cannot change slot */
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
- if (assoc_array_ptr_is_meta(node->slots[i]))
- new_n0->slots[i] = node->slots[i];
- else
- new_n0->slots[i] = NULL;
- BUG_ON(new_n0->slots[slot] != NULL);
- new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1);
-
- /* Filter the leaf pointers between the new nodes */
- free_slot = -1;
- next_slot = 0;
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- if (assoc_array_ptr_is_meta(node->slots[i]))
- continue;
- if (edit->segment_cache[i] == slot) {
- new_n1->slots[next_slot++] = node->slots[i];
- new_n1->nr_leaves_on_branch++;
- } else {
- do {
- free_slot++;
- } while (new_n0->slots[free_slot] != NULL);
- new_n0->slots[free_slot] = node->slots[i];
- }
- }
-
- pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot);
-
- if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
- do {
- free_slot++;
- } while (new_n0->slots[free_slot] != NULL);
- edit->leaf_p = &new_n0->slots[free_slot];
- edit->adjust_count_on = new_n0;
- } else {
- edit->leaf_p = &new_n1->slots[next_slot++];
- edit->adjust_count_on = new_n1;
- }
-
- BUG_ON(next_slot <= 1);
-
- edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- if (edit->segment_cache[i] == 0xff) {
- ptr = node->slots[i];
- BUG_ON(assoc_array_ptr_is_leaf(ptr));
- if (assoc_array_ptr_is_node(ptr)) {
- side = assoc_array_ptr_to_node(ptr);
- edit->set_backpointers[i] = &side->back_pointer;
- } else {
- shortcut = assoc_array_ptr_to_shortcut(ptr);
- edit->set_backpointers[i] = &shortcut->back_pointer;
- }
- }
- }
-
- ptr = node->back_pointer;
- if (!ptr)
- edit->set[0].ptr = &edit->array->root;
- else if (assoc_array_ptr_is_node(ptr))
- edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
- else
- edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;
- edit->excised_meta[0] = assoc_array_node_to_ptr(node);
- pr_devel("<--%s() = ok [split node]\n", __func__);
- return true;
-
-all_leaves_cluster_together:
- /* All the leaves, new and old, want to cluster together in this node
- * in the same slot, so we have to replace this node with a shortcut to
- * skip over the identical parts of the key and then place a pair of
- * nodes, one inside the other, at the end of the shortcut and
- * distribute the keys between them.
- *
- * Firstly we need to work out where the leaves start diverging as a
- * bit position into their keys so that we know how big the shortcut
- * needs to be.
- *
- * We only need to make a single pass of N of the N+1 leaves because if
- * any keys differ between themselves at bit X then at least one of
- * them must also differ with the base key at bit X or before.
- */
- pr_devel("all leaves cluster together\n");
- diff = INT_MAX;
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]),
- index_key);
- if (x < diff) {
- BUG_ON(x < 0);
- diff = x;
- }
- }
- BUG_ON(diff == INT_MAX);
- BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP);
-
- keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
- keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
-
- new_s0 = kzalloc_flex(*new_s0, index_key, keylen);
- if (!new_s0)
- return false;
- edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
-
- edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
- new_s0->back_pointer = node->back_pointer;
- new_s0->parent_slot = node->parent_slot;
- new_s0->next_node = assoc_array_node_to_ptr(new_n0);
- new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
- new_n0->parent_slot = 0;
- new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
- new_n1->parent_slot = -1; /* Need to calculate this */
-
- new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK;
- pr_devel("skip_to_level = %d [diff %d]\n", level, diff);
- BUG_ON(level <= 0);
-
- for (i = 0; i < keylen; i++)
- new_s0->index_key[i] =
- ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
-
- if (level & ASSOC_ARRAY_KEY_CHUNK_MASK) {
- blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
- pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);
- new_s0->index_key[keylen - 1] &= ~blank;
- }
-
- /* This now reduces to a node splitting exercise for which we'll need
- * to regenerate the disparity table.
- */
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- ptr = node->slots[i];
- base_seg = ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr),
- level);
- base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
- edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
- }
-
- base_seg = ops->get_key_chunk(index_key, level);
- base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
- edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
- goto do_split_node;
-}
-
-/*
- * Handle insertion into the middle of a shortcut.
- */
-static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
- const struct assoc_array_ops *ops,
- struct assoc_array_walk_result *result)
-{
- struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
- struct assoc_array_node *node, *new_n0, *side;
- unsigned long sc_segments, dissimilarity, blank;
- size_t keylen;
- int level, sc_level, diff;
- int sc_slot;
-
- shortcut = result->wrong_shortcut.shortcut;
- level = result->wrong_shortcut.level;
- sc_level = result->wrong_shortcut.sc_level;
- sc_segments = result->wrong_shortcut.sc_segments;
- dissimilarity = result->wrong_shortcut.dissimilarity;
-
- pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",
- __func__, level, dissimilarity, sc_level);
-
- /* We need to split a shortcut and insert a node between the two
- * pieces. Zero-length pieces will be dispensed with entirely.
- *
- * First of all, we need to find out in which level the first
- * difference was.
- */
- diff = __ffs(dissimilarity);
- diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;
- diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;
- pr_devel("diff=%d\n", diff);
-
- if (!shortcut->back_pointer) {
- edit->set[0].ptr = &edit->array->root;
- } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) {
- node = assoc_array_ptr_to_node(shortcut->back_pointer);
- edit->set[0].ptr = &node->slots[shortcut->parent_slot];
- } else {
- BUG();
- }
-
- edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
-
- /* Create a new node now since we're going to need it anyway */
- new_n0 = kzalloc_obj(struct assoc_array_node);
- if (!new_n0)
- return false;
- edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
- edit->adjust_count_on = new_n0;
-
- /* Insert a new shortcut before the new node if this segment isn't of
- * zero length - otherwise we just connect the new node directly to the
- * parent.
- */
- level += ASSOC_ARRAY_LEVEL_STEP;
- if (diff > level) {
- pr_devel("pre-shortcut %d...%d\n", level, diff);
- keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
- keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
-
- new_s0 = kzalloc_flex(*new_s0, index_key, keylen);
- if (!new_s0)
- return false;
- edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
- edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
- new_s0->back_pointer = shortcut->back_pointer;
- new_s0->parent_slot = shortcut->parent_slot;
- new_s0->next_node = assoc_array_node_to_ptr(new_n0);
- new_s0->skip_to_level = diff;
-
- new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
- new_n0->parent_slot = 0;
-
- memcpy(new_s0->index_key, shortcut->index_key,
- flex_array_size(new_s0, index_key, keylen));
-
- blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
- pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
- new_s0->index_key[keylen - 1] &= ~blank;
- } else {
- pr_devel("no pre-shortcut\n");
- edit->set[0].to = assoc_array_node_to_ptr(new_n0);
- new_n0->back_pointer = shortcut->back_pointer;
- new_n0->parent_slot = shortcut->parent_slot;
- }
-
- side = assoc_array_ptr_to_node(shortcut->next_node);
- new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch;
-
- /* We need to know which slot in the new node is going to take a
- * metadata pointer.
- */
- sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
- sc_slot &= ASSOC_ARRAY_FAN_MASK;
-
- pr_devel("new slot %lx >> %d -> %d\n",
- sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot);
-
- /* Determine whether we need to follow the new node with a replacement
- * for the current shortcut. We could in theory reuse the current
- * shortcut if its parent slot number doesn't change - but that's a
- * 1-in-16 chance so not worth expending the code upon.
- */
- level = diff + ASSOC_ARRAY_LEVEL_STEP;
- if (level < shortcut->skip_to_level) {
- pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
- keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
- keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
-
- new_s1 = kzalloc_flex(*new_s1, index_key, keylen);
- if (!new_s1)
- return false;
- edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
-
- new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);
- new_s1->parent_slot = sc_slot;
- new_s1->next_node = shortcut->next_node;
- new_s1->skip_to_level = shortcut->skip_to_level;
-
- new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
-
- memcpy(new_s1->index_key, shortcut->index_key,
- flex_array_size(new_s1, index_key, keylen));
-
- edit->set[1].ptr = &side->back_pointer;
- edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
- } else {
- pr_devel("no post-shortcut\n");
-
- /* We don't have to replace the pointed-to node as long as we
- * use memory barriers to make sure the parent slot number is
- * changed before the back pointer (the parent slot number is
- * irrelevant to the old parent shortcut).
- */
- new_n0->slots[sc_slot] = shortcut->next_node;
- edit->set_parent_slot[0].p = &side->parent_slot;
- edit->set_parent_slot[0].to = sc_slot;
- edit->set[1].ptr = &side->back_pointer;
- edit->set[1].to = assoc_array_node_to_ptr(new_n0);
- }
-
- /* Install the new leaf in a spare slot in the new node. */
- if (sc_slot == 0)
- edit->leaf_p = &new_n0->slots[1];
- else
- edit->leaf_p = &new_n0->slots[0];
-
- pr_devel("<--%s() = ok [split shortcut]\n", __func__);
- return true;
-}
-
-/**
- * assoc_array_insert - Script insertion of an object into an associative array
- * @array: The array to insert into.
- * @ops: The operations to use.
- * @index_key: The key to insert at.
- * @object: The object to insert.
- *
- * Precalculate and preallocate a script for the insertion or replacement of an
- * object in an associative array. This results in an edit script that can
- * either be applied or cancelled.
- *
- * The function returns a pointer to an edit script or -ENOMEM.
- *
- * The caller should lock against other modifications and must continue to hold
- * the lock until assoc_array_apply_edit() has been called.
- *
- * Accesses to the tree may take place concurrently with this function,
- * provided they hold the RCU read lock.
- */
-struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key,
- void *object)
-{
- struct assoc_array_walk_result result;
- struct assoc_array_edit *edit;
-
- pr_devel("-->%s()\n", __func__);
-
- /* The leaf pointer we're given must not have the bottom bit set as we
- * use those for type-marking the pointer. NULL pointers are also not
- * allowed as they indicate an empty slot but we have to allow them
- * here as they can be updated later.
- */
- BUG_ON(assoc_array_ptr_is_meta(object));
-
- edit = kzalloc_obj(struct assoc_array_edit);
- if (!edit)
- return ERR_PTR(-ENOMEM);
- edit->array = array;
- edit->ops = ops;
- edit->leaf = assoc_array_leaf_to_ptr(object);
- edit->adjust_count_by = 1;
-
- switch (assoc_array_walk(array, ops, index_key, &result)) {
- case assoc_array_walk_tree_empty:
- /* Allocate a root node if there isn't one yet */
- if (!assoc_array_insert_in_empty_tree(edit))
- goto enomem;
- return edit;
-
- case assoc_array_walk_found_terminal_node:
- /* We found a node that doesn't have a node/shortcut pointer in
- * the slot corresponding to the index key that we have to
- * follow.
- */
- if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
- &result))
- goto enomem;
- return edit;
-
- case assoc_array_walk_found_wrong_shortcut:
- /* We found a shortcut that didn't match our key in a slot we
- * needed to follow.
- */
- if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
- goto enomem;
- return edit;
- }
-
-enomem:
- /* Clean up after an out of memory error */
- pr_devel("enomem\n");
- assoc_array_cancel_edit(edit);
- return ERR_PTR(-ENOMEM);
-}
-
-/**
- * assoc_array_insert_set_object - Set the new object pointer in an edit script
- * @edit: The edit script to modify.
- * @object: The object pointer to set.
- *
- * Change the object to be inserted in an edit script. The object pointed to
- * by the old object is not freed. This must be done prior to applying the
- * script.
- */
-void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
-{
- BUG_ON(!object);
- edit->leaf = assoc_array_leaf_to_ptr(object);
-}
-
-struct assoc_array_delete_collapse_context {
- struct assoc_array_node *node;
- const void *skip_leaf;
- int slot;
-};
-
-/*
- * Subtree collapse to node iterator.
- */
-static int assoc_array_delete_collapse_iterator(const void *leaf,
- void *iterator_data)
-{
- struct assoc_array_delete_collapse_context *collapse = iterator_data;
-
- if (leaf == collapse->skip_leaf)
- return 0;
-
- BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
-
- collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
- return 0;
-}
-
-/**
- * assoc_array_delete - Script deletion of an object from an associative array
- * @array: The array to search.
- * @ops: The operations to use.
- * @index_key: The key to the object.
- *
- * Precalculate and preallocate a script for the deletion of an object from an
- * associative array. This results in an edit script that can either be
- * applied or cancelled.
- *
- * The function returns a pointer to an edit script if the object was found,
- * NULL if the object was not found or -ENOMEM.
- *
- * The caller should lock against other modifications and must continue to hold
- * the lock until assoc_array_apply_edit() has been called.
- *
- * Accesses to the tree may take place concurrently with this function,
- * provided they hold the RCU read lock.
- */
-struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- const void *index_key)
-{
- struct assoc_array_delete_collapse_context collapse;
- struct assoc_array_walk_result result;
- struct assoc_array_node *node, *new_n0;
- struct assoc_array_edit *edit;
- struct assoc_array_ptr *ptr;
- bool has_meta;
- int slot, i;
-
- pr_devel("-->%s()\n", __func__);
-
- edit = kzalloc_obj(struct assoc_array_edit);
- if (!edit)
- return ERR_PTR(-ENOMEM);
- edit->array = array;
- edit->ops = ops;
- edit->adjust_count_by = -1;
-
- switch (assoc_array_walk(array, ops, index_key, &result)) {
- case assoc_array_walk_found_terminal_node:
- /* We found a node that should contain the leaf we've been
- * asked to remove - *if* it's in the tree.
- */
- pr_devel("terminal_node\n");
- node = result.terminal_node.node;
-
- for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- ptr = node->slots[slot];
- if (ptr &&
- assoc_array_ptr_is_leaf(ptr) &&
- ops->compare_object(assoc_array_ptr_to_leaf(ptr),
- index_key))
- goto found_leaf;
- }
- fallthrough;
- case assoc_array_walk_tree_empty:
- case assoc_array_walk_found_wrong_shortcut:
- default:
- assoc_array_cancel_edit(edit);
- pr_devel("not found\n");
- return NULL;
- }
-
-found_leaf:
- BUG_ON(array->nr_leaves_on_tree <= 0);
-
- /* In the simplest form of deletion we just clear the slot and release
- * the leaf after a suitable interval.
- */
- edit->dead_leaf = node->slots[slot];
- edit->set[0].ptr = &node->slots[slot];
- edit->set[0].to = NULL;
- edit->adjust_count_on = node;
-
- /* If that concludes erasure of the last leaf, then delete the entire
- * internal array.
- */
- if (array->nr_leaves_on_tree == 1) {
- edit->set[1].ptr = &array->root;
- edit->set[1].to = NULL;
- edit->adjust_count_on = NULL;
- edit->excised_subtree = array->root;
- pr_devel("all gone\n");
- return edit;
- }
-
- /* However, we'd also like to clear up some metadata blocks if we
- * possibly can.
- *
- * We go for a simple algorithm of: if this node has FAN_OUT or fewer
- * leaves in it, then attempt to collapse it - and attempt to
- * recursively collapse up the tree.
- *
- * We could also try and collapse in partially filled subtrees to take
- * up space in this node.
- */
- if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
- struct assoc_array_node *parent, *grandparent;
- struct assoc_array_ptr *ptr;
-
- /* First of all, we need to know if this node has metadata so
- * that we don't try collapsing if all the leaves are already
- * here.
- */
- has_meta = false;
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- ptr = node->slots[i];
- if (assoc_array_ptr_is_meta(ptr)) {
- has_meta = true;
- break;
- }
- }
-
- pr_devel("leaves: %ld [m=%d]\n",
- node->nr_leaves_on_branch - 1, has_meta);
-
- /* Look further up the tree to see if we can collapse this node
- * into a more proximal node too.
- */
- parent = node;
- collapse_up:
- pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch);
-
- ptr = parent->back_pointer;
- if (!ptr)
- goto do_collapse;
- if (assoc_array_ptr_is_shortcut(ptr)) {
- struct assoc_array_shortcut *s = assoc_array_ptr_to_shortcut(ptr);
- ptr = s->back_pointer;
- if (!ptr)
- goto do_collapse;
- }
-
- grandparent = assoc_array_ptr_to_node(ptr);
- if (grandparent->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
- parent = grandparent;
- goto collapse_up;
- }
-
- do_collapse:
- /* There's no point collapsing if the original node has no meta
- * pointers to discard and if we didn't merge into one of that
- * node's ancestry.
- */
- if (has_meta || parent != node) {
- node = parent;
-
- /* Create a new node to collapse into */
- new_n0 = kzalloc_obj(struct assoc_array_node);
- if (!new_n0)
- goto enomem;
- edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
-
- new_n0->back_pointer = node->back_pointer;
- new_n0->parent_slot = node->parent_slot;
- new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
- edit->adjust_count_on = new_n0;
-
- collapse.node = new_n0;
- collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
- collapse.slot = 0;
- assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
- node->back_pointer,
- assoc_array_delete_collapse_iterator,
- &collapse);
- pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
- BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
-
- if (!node->back_pointer) {
- edit->set[1].ptr = &array->root;
- } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
- BUG();
- } else if (assoc_array_ptr_is_node(node->back_pointer)) {
- struct assoc_array_node *p =
- assoc_array_ptr_to_node(node->back_pointer);
- edit->set[1].ptr = &p->slots[node->parent_slot];
- } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
- struct assoc_array_shortcut *s =
- assoc_array_ptr_to_shortcut(node->back_pointer);
- edit->set[1].ptr = &s->next_node;
- }
- edit->set[1].to = assoc_array_node_to_ptr(new_n0);
- edit->excised_subtree = assoc_array_node_to_ptr(node);
- }
- }
-
- return edit;
-
-enomem:
- /* Clean up after an out of memory error */
- pr_devel("enomem\n");
- assoc_array_cancel_edit(edit);
- return ERR_PTR(-ENOMEM);
-}
-
-/**
- * assoc_array_clear - Script deletion of all objects from an associative array
- * @array: The array to clear.
- * @ops: The operations to use.
- *
- * Precalculate and preallocate a script for the deletion of all the objects
- * from an associative array. This results in an edit script that can either
- * be applied or cancelled.
- *
- * The function returns a pointer to an edit script if there are objects to be
- * deleted, NULL if there are no objects in the array or -ENOMEM.
- *
- * The caller should lock against other modifications and must continue to hold
- * the lock until assoc_array_apply_edit() has been called.
- *
- * Accesses to the tree may take place concurrently with this function,
- * provided they hold the RCU read lock.
- */
-struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
- const struct assoc_array_ops *ops)
-{
- struct assoc_array_edit *edit;
-
- pr_devel("-->%s()\n", __func__);
-
- if (!array->root)
- return NULL;
-
- edit = kzalloc_obj(struct assoc_array_edit);
- if (!edit)
- return ERR_PTR(-ENOMEM);
- edit->array = array;
- edit->ops = ops;
- edit->set[1].ptr = &array->root;
- edit->set[1].to = NULL;
- edit->excised_subtree = array->root;
- edit->ops_for_excised_subtree = ops;
- pr_devel("all gone\n");
- return edit;
-}
-
-/*
- * Handle the deferred destruction after an applied edit.
- */
-static void assoc_array_rcu_cleanup(struct rcu_head *head)
-{
- struct assoc_array_edit *edit =
- container_of(head, struct assoc_array_edit, rcu);
- int i;
-
- pr_devel("-->%s()\n", __func__);
-
- if (edit->dead_leaf)
- edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
- for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
- if (edit->excised_meta[i])
- kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
-
- if (edit->excised_subtree) {
- BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
- if (assoc_array_ptr_is_node(edit->excised_subtree)) {
- struct assoc_array_node *n =
- assoc_array_ptr_to_node(edit->excised_subtree);
- n->back_pointer = NULL;
- } else {
- struct assoc_array_shortcut *s =
- assoc_array_ptr_to_shortcut(edit->excised_subtree);
- s->back_pointer = NULL;
- }
- assoc_array_destroy_subtree(edit->excised_subtree,
- edit->ops_for_excised_subtree);
- }
-
- kfree(edit);
-}
-
-/**
- * assoc_array_apply_edit - Apply an edit script to an associative array
- * @edit: The script to apply.
- *
- * Apply an edit script to an associative array to effect an insertion,
- * deletion or clearance. As the edit script includes preallocated memory,
- * this is guaranteed not to fail.
- *
- * The edit script, dead objects and dead metadata will be scheduled for
- * destruction after an RCU grace period to permit those doing read-only
- * accesses on the array to continue to do so under the RCU read lock whilst
- * the edit is taking place.
- */
-void assoc_array_apply_edit(struct assoc_array_edit *edit)
-{
- struct assoc_array_shortcut *shortcut;
- struct assoc_array_node *node;
- struct assoc_array_ptr *ptr;
- int i;
-
- pr_devel("-->%s()\n", __func__);
-
- smp_wmb();
- if (edit->leaf_p)
- *edit->leaf_p = edit->leaf;
-
- smp_wmb();
- for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
- if (edit->set_parent_slot[i].p)
- *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
-
- smp_wmb();
- for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
- if (edit->set_backpointers[i])
- *edit->set_backpointers[i] = edit->set_backpointers_to;
-
- smp_wmb();
- for (i = 0; i < ARRAY_SIZE(edit->set); i++)
- if (edit->set[i].ptr)
- *edit->set[i].ptr = edit->set[i].to;
-
- if (edit->array->root == NULL) {
- edit->array->nr_leaves_on_tree = 0;
- } else if (edit->adjust_count_on) {
- node = edit->adjust_count_on;
- for (;;) {
- node->nr_leaves_on_branch += edit->adjust_count_by;
-
- ptr = node->back_pointer;
- if (!ptr)
- break;
- if (assoc_array_ptr_is_shortcut(ptr)) {
- shortcut = assoc_array_ptr_to_shortcut(ptr);
- ptr = shortcut->back_pointer;
- if (!ptr)
- break;
- }
- BUG_ON(!assoc_array_ptr_is_node(ptr));
- node = assoc_array_ptr_to_node(ptr);
- }
-
- edit->array->nr_leaves_on_tree += edit->adjust_count_by;
- }
-
- call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
-}
-
-/**
- * assoc_array_cancel_edit - Discard an edit script.
- * @edit: The script to discard.
- *
- * Free an edit script and all the preallocated data it holds without making
- * any changes to the associative array it was intended for.
- *
- * NOTE! In the case of an insertion script, this does _not_ release the leaf
- * that was to be inserted. That is left to the caller.
- */
-void assoc_array_cancel_edit(struct assoc_array_edit *edit)
-{
- struct assoc_array_ptr *ptr;
- int i;
-
- pr_devel("-->%s()\n", __func__);
-
- /* Clean up after an out of memory error */
- for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
- ptr = edit->new_meta[i];
- if (ptr) {
- if (assoc_array_ptr_is_node(ptr))
- kfree(assoc_array_ptr_to_node(ptr));
- else
- kfree(assoc_array_ptr_to_shortcut(ptr));
- }
- }
- kfree(edit);
-}
-
-/**
- * assoc_array_gc - Garbage collect an associative array.
- * @array: The array to clean.
- * @ops: The operations to use.
- * @iterator: A callback function to pass judgement on each object.
- * @iterator_data: Private data for the callback function.
- *
- * Collect garbage from an associative array and pack down the internal tree to
- * save memory.
- *
- * The iterator function is asked to pass judgement upon each object in the
- * array. If it returns false, the object is discard and if it returns true,
- * the object is kept. If it returns true, it must increment the object's
- * usage count (or whatever it needs to do to retain it) before returning.
- *
- * This function returns 0 if successful or -ENOMEM if out of memory. In the
- * latter case, the array is not changed.
- *
- * The caller should lock against other modifications and must continue to hold
- * the lock until assoc_array_apply_edit() has been called.
- *
- * Accesses to the tree may take place concurrently with this function,
- * provided they hold the RCU read lock.
- */
-int assoc_array_gc(struct assoc_array *array,
- const struct assoc_array_ops *ops,
- bool (*iterator)(void *object, void *iterator_data),
- void *iterator_data)
-{
- struct assoc_array_shortcut *shortcut, *new_s;
- struct assoc_array_node *node, *new_n;
- struct assoc_array_edit *edit;
- struct assoc_array_ptr *cursor, *ptr;
- struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp;
- unsigned long nr_leaves_on_tree;
- bool retained;
- int keylen, slot, nr_free, next_slot, i;
-
- pr_devel("-->%s()\n", __func__);
-
- if (!array->root)
- return 0;
-
- edit = kzalloc_obj(struct assoc_array_edit);
- if (!edit)
- return -ENOMEM;
- edit->array = array;
- edit->ops = ops;
- edit->ops_for_excised_subtree = ops;
- edit->set[0].ptr = &array->root;
- edit->excised_subtree = array->root;
-
- new_root = new_parent = NULL;
- new_ptr_pp = &new_root;
- cursor = array->root;
-
-descend:
- /* If this point is a shortcut, then we need to duplicate it and
- * advance the target cursor.
- */
- if (assoc_array_ptr_is_shortcut(cursor)) {
- shortcut = assoc_array_ptr_to_shortcut(cursor);
- keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
- keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
- new_s = kmalloc_flex(*new_s, index_key, keylen);
- if (!new_s)
- goto enomem;
- pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
- memcpy(new_s, shortcut, struct_size(new_s, index_key, keylen));
- new_s->back_pointer = new_parent;
- new_s->parent_slot = shortcut->parent_slot;
- *new_ptr_pp = new_parent = assoc_array_shortcut_to_ptr(new_s);
- new_ptr_pp = &new_s->next_node;
- cursor = shortcut->next_node;
- }
-
- /* Duplicate the node at this position */
- node = assoc_array_ptr_to_node(cursor);
- new_n = kzalloc_obj(struct assoc_array_node);
- if (!new_n)
- goto enomem;
- pr_devel("dup node %p -> %p\n", node, new_n);
- new_n->back_pointer = new_parent;
- new_n->parent_slot = node->parent_slot;
- *new_ptr_pp = new_parent = assoc_array_node_to_ptr(new_n);
- new_ptr_pp = NULL;
- slot = 0;
-
-continue_node:
- /* Filter across any leaves and gc any subtrees */
- for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- ptr = node->slots[slot];
- if (!ptr)
- continue;
-
- if (assoc_array_ptr_is_leaf(ptr)) {
- if (iterator(assoc_array_ptr_to_leaf(ptr),
- iterator_data))
- /* The iterator will have done any reference
- * counting on the object for us.
- */
- new_n->slots[slot] = ptr;
- continue;
- }
-
- new_ptr_pp = &new_n->slots[slot];
- cursor = ptr;
- goto descend;
- }
-
-retry_compress:
- pr_devel("-- compress node %p --\n", new_n);
-
- /* Count up the number of empty slots in this node and work out the
- * subtree leaf count.
- */
- new_n->nr_leaves_on_branch = 0;
- nr_free = 0;
- for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- ptr = new_n->slots[slot];
- if (!ptr)
- nr_free++;
- else if (assoc_array_ptr_is_leaf(ptr))
- new_n->nr_leaves_on_branch++;
- }
- pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
-
- /* See what we can fold in */
- retained = false;
- next_slot = 0;
- for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
- struct assoc_array_shortcut *s;
- struct assoc_array_node *child;
-
- ptr = new_n->slots[slot];
- if (!ptr || assoc_array_ptr_is_leaf(ptr))
- continue;
-
- s = NULL;
- if (assoc_array_ptr_is_shortcut(ptr)) {
- s = assoc_array_ptr_to_shortcut(ptr);
- ptr = s->next_node;
- }
-
- child = assoc_array_ptr_to_node(ptr);
- new_n->nr_leaves_on_branch += child->nr_leaves_on_branch;
-
- if (child->nr_leaves_on_branch <= nr_free + 1) {
- /* Fold the child node into this one */
- pr_devel("[%d] fold node %lu/%d [nx %d]\n",
- slot, child->nr_leaves_on_branch, nr_free + 1,
- next_slot);
-
- /* We would already have reaped an intervening shortcut
- * on the way back up the tree.
- */
- BUG_ON(s);
-
- new_n->slots[slot] = NULL;
- nr_free++;
- if (slot < next_slot)
- next_slot = slot;
- for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
- struct assoc_array_ptr *p = child->slots[i];
- if (!p)
- continue;
- BUG_ON(assoc_array_ptr_is_meta(p));
- while (new_n->slots[next_slot])
- next_slot++;
- BUG_ON(next_slot >= ASSOC_ARRAY_FAN_OUT);
- new_n->slots[next_slot++] = p;
- nr_free--;
- }
- kfree(child);
- } else {
- pr_devel("[%d] retain node %lu/%d [nx %d]\n",
- slot, child->nr_leaves_on_branch, nr_free + 1,
- next_slot);
- retained = true;
- }
- }
-
- if (retained && new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
- pr_devel("internal nodes remain despite enough space, retrying\n");
- goto retry_compress;
- }
- pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
-
- nr_leaves_on_tree = new_n->nr_leaves_on_branch;
-
- /* Excise this node if it is singly occupied by a shortcut */
- if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) {
- for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++)
- if ((ptr = new_n->slots[slot]))
- break;
-
- if (assoc_array_ptr_is_meta(ptr) &&
- assoc_array_ptr_is_shortcut(ptr)) {
- pr_devel("excise node %p with 1 shortcut\n", new_n);
- new_s = assoc_array_ptr_to_shortcut(ptr);
- new_parent = new_n->back_pointer;
- slot = new_n->parent_slot;
- kfree(new_n);
- if (!new_parent) {
- new_s->back_pointer = NULL;
- new_s->parent_slot = 0;
- new_root = ptr;
- goto gc_complete;
- }
-
- if (assoc_array_ptr_is_shortcut(new_parent)) {
- /* We can discard any preceding shortcut also */
- struct assoc_array_shortcut *s =
- assoc_array_ptr_to_shortcut(new_parent);
-
- pr_devel("excise preceding shortcut\n");
-
- new_parent = new_s->back_pointer = s->back_pointer;
- slot = new_s->parent_slot = s->parent_slot;
- kfree(s);
- if (!new_parent) {
- new_s->back_pointer = NULL;
- new_s->parent_slot = 0;
- new_root = ptr;
- goto gc_complete;
- }
- }
-
- new_s->back_pointer = new_parent;
- new_s->parent_slot = slot;
- new_n = assoc_array_ptr_to_node(new_parent);
- new_n->slots[slot] = ptr;
- goto ascend_old_tree;
- }
- }
-
- /* Excise any shortcuts we might encounter that point to nodes that
- * only contain leaves.
- */
- ptr = new_n->back_pointer;
- if (!ptr)
- goto gc_complete;
-
- if (assoc_array_ptr_is_shortcut(ptr)) {
- new_s = assoc_array_ptr_to_shortcut(ptr);
- new_parent = new_s->back_pointer;
- slot = new_s->parent_slot;
-
- if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
- struct assoc_array_node *n;
-
- pr_devel("excise shortcut\n");
- new_n->back_pointer = new_parent;
- new_n->parent_slot = slot;
- kfree(new_s);
- if (!new_parent) {
- new_root = assoc_array_node_to_ptr(new_n);
- goto gc_complete;
- }
-
- n = assoc_array_ptr_to_node(new_parent);
- n->slots[slot] = assoc_array_node_to_ptr(new_n);
- }
- } else {
- new_parent = ptr;
- }
- new_n = assoc_array_ptr_to_node(new_parent);
-
-ascend_old_tree:
- ptr = node->back_pointer;
- if (assoc_array_ptr_is_shortcut(ptr)) {
- shortcut = assoc_array_ptr_to_shortcut(ptr);
- slot = shortcut->parent_slot;
- cursor = shortcut->back_pointer;
- if (!cursor)
- goto gc_complete;
- } else {
- slot = node->parent_slot;
- cursor = ptr;
- }
- BUG_ON(!cursor);
- node = assoc_array_ptr_to_node(cursor);
- slot++;
- goto continue_node;
-
-gc_complete:
- edit->set[0].to = new_root;
- assoc_array_apply_edit(edit);
- array->nr_leaves_on_tree = nr_leaves_on_tree;
- return 0;
-
-enomem:
- pr_devel("enomem\n");
- assoc_array_destroy_subtree(new_root, edit->ops);
- kfree(edit);
- return -ENOMEM;
-}
--
2.47.3
More information about the Linux-security-module-archive
mailing list