[RFC PATCH 6/6] lib: Remove unused assoc_array

@@ -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.

@@ -38,7 +38,6 @@ Library functionality that is used throughout the kernel.
    kobject
    kref
    cleanup
-   assoc_array
    folio_queue
    xarray
    maple_tree

@@ -1,473 +0,0 @@
-.. include:: ../disclaimer-zh_CN.rst
-
-:Original: Documentation/core-api/assoc_array.rst
-
-:翻译:
-
- 司延è

@@ -41,7 +41,6 @@
 
    kobject
    kref
-   assoc_array
    xarray
    rbtree
    idr

@@ -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@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 */

@@ -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@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 */

@@ -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
 

@@ -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

@@ -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@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;
-}