LCOV - code coverage report
Current view: top level - lib - xarray.c (source / functions) Hit Total Coverage
Test: gcov_data_raspi2_real_modules_combined.info Lines: 366 600 61.0 %
Date: 2020-09-30 20:25:40 Functions: 24 46 52.2 %
Branches: 270 522 51.7 %

           Branch data     Line data    Source code
       1                 :            : // SPDX-License-Identifier: GPL-2.0+
       2                 :            : /*
       3                 :            :  * XArray implementation
       4                 :            :  * Copyright (c) 2017-2018 Microsoft Corporation
       5                 :            :  * Copyright (c) 2018-2020 Oracle
       6                 :            :  * Author: Matthew Wilcox <willy@infradead.org>
       7                 :            :  */
       8                 :            : 
       9                 :            : #include <linux/bitmap.h>
      10                 :            : #include <linux/export.h>
      11                 :            : #include <linux/list.h>
      12                 :            : #include <linux/slab.h>
      13                 :            : #include <linux/xarray.h>
      14                 :            : 
      15                 :            : /*
      16                 :            :  * Coding conventions in this file:
      17                 :            :  *
      18                 :            :  * @xa is used to refer to the entire xarray.
      19                 :            :  * @xas is the 'xarray operation state'.  It may be either a pointer to
      20                 :            :  * an xa_state, or an xa_state stored on the stack.  This is an unfortunate
      21                 :            :  * ambiguity.
      22                 :            :  * @index is the index of the entry being operated on
      23                 :            :  * @mark is an xa_mark_t; a small number indicating one of the mark bits.
      24                 :            :  * @node refers to an xa_node; usually the primary one being operated on by
      25                 :            :  * this function.
      26                 :            :  * @offset is the index into the slots array inside an xa_node.
      27                 :            :  * @parent refers to the @xa_node closer to the head than @node.
      28                 :            :  * @entry refers to something stored in a slot in the xarray
      29                 :            :  */
      30                 :            : 
      31                 :            : static inline unsigned int xa_lock_type(const struct xarray *xa)
      32                 :            : {
      33                 :        414 :         return (__force unsigned int)xa->xa_flags & 3;
      34                 :            : }
      35                 :            : 
      36                 :          0 : static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type)
      37                 :            : {
      38         [ #  # ]:          0 :         if (lock_type == XA_LOCK_IRQ)
      39                 :          0 :                 xas_lock_irq(xas);
      40         [ #  # ]:          0 :         else if (lock_type == XA_LOCK_BH)
      41                 :          0 :                 xas_lock_bh(xas);
      42                 :            :         else
      43                 :          0 :                 xas_lock(xas);
      44                 :          0 : }
      45                 :            : 
      46                 :          0 : static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type)
      47                 :            : {
      48         [ #  # ]:          0 :         if (lock_type == XA_LOCK_IRQ)
      49                 :          0 :                 xas_unlock_irq(xas);
      50         [ #  # ]:          0 :         else if (lock_type == XA_LOCK_BH)
      51                 :          0 :                 xas_unlock_bh(xas);
      52                 :            :         else
      53                 :          0 :                 xas_unlock(xas);
      54                 :          0 : }
      55                 :            : 
      56                 :            : static inline bool xa_track_free(const struct xarray *xa)
      57                 :            : {
      58                 :    7920119 :         return xa->xa_flags & XA_FLAGS_TRACK_FREE;
      59                 :            : }
      60                 :            : 
      61                 :            : static inline bool xa_zero_busy(const struct xarray *xa)
      62                 :            : {
      63                 :     775832 :         return xa->xa_flags & XA_FLAGS_ZERO_BUSY;
      64                 :            : }
      65                 :            : 
      66                 :            : static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
      67                 :            : {
      68   [ +  -  +  - ]:     586405 :         if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
      69                 :     586405 :                 xa->xa_flags |= XA_FLAGS_MARK(mark);
      70                 :            : }
      71                 :            : 
      72                 :            : static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark)
      73                 :            : {
      74   [ #  #  +  -  :     395481 :         if (xa->xa_flags & XA_FLAGS_MARK(mark))
                   #  # ]
      75                 :     395482 :                 xa->xa_flags &= ~(XA_FLAGS_MARK(mark));
      76                 :            : }
      77                 :            : 
      78                 :            : static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
      79                 :            : {
      80                 :    9103440 :         return node->marks[(__force unsigned)mark];
      81                 :            : }
      82                 :            : 
      83                 :            : static inline bool node_get_mark(struct xa_node *node,
      84                 :            :                 unsigned int offset, xa_mark_t mark)
      85                 :            : {
      86                 :          0 :         return test_bit(offset, node_marks(node, mark));
      87                 :            : }
      88                 :            : 
      89                 :            : /* returns true if the bit was set */
      90                 :            : static inline bool node_set_mark(struct xa_node *node, unsigned int offset,
      91                 :            :                                 xa_mark_t mark)
      92                 :            : {
      93                 :    1117307 :         return __test_and_set_bit(offset, node_marks(node, mark));
      94                 :            : }
      95                 :            : 
      96                 :            : /* returns true if the bit was set */
      97                 :            : static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,
      98                 :            :                                 xa_mark_t mark)
      99                 :            : {
     100                 :    7889488 :         return __test_and_clear_bit(offset, node_marks(node, mark));
     101                 :            : }
     102                 :            : 
     103                 :            : static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
     104                 :            : {
     105                 :     768447 :         return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
     106                 :            : }
     107                 :            : 
     108                 :            : static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
     109                 :            : {
     110                 :            :         bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
     111                 :            : }
     112                 :            : 
     113                 :            : #define mark_inc(mark) do { \
     114                 :            :         mark = (__force xa_mark_t)((__force unsigned)(mark) + 1); \
     115                 :            : } while (0)
     116                 :            : 
     117                 :            : /*
     118                 :            :  * xas_squash_marks() - Merge all marks to the first entry
     119                 :            :  * @xas: Array operation state.
     120                 :            :  *
     121                 :            :  * Set a mark on the first entry if any entry has it set.  Clear marks on
     122                 :            :  * all sibling entries.
     123                 :            :  */
     124                 :          0 : static void xas_squash_marks(const struct xa_state *xas)
     125                 :            : {
     126                 :            :         unsigned int mark = 0;
     127                 :          0 :         unsigned int limit = xas->xa_offset + xas->xa_sibs + 1;
     128                 :            : 
     129         [ #  # ]:          0 :         if (!xas->xa_sibs)
     130                 :          0 :                 return;
     131                 :            : 
     132                 :            :         do {
     133                 :          0 :                 unsigned long *marks = xas->xa_node->marks[mark];
     134         [ #  # ]:          0 :                 if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit)
     135                 :          0 :                         continue;
     136                 :          0 :                 __set_bit(xas->xa_offset, marks);
     137                 :          0 :                 bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);
     138         [ #  # ]:          0 :         } while (mark++ != (__force unsigned)XA_MARK_MAX);
     139                 :            : }
     140                 :            : 
     141                 :            : /* extracts the offset within this node from the index */
     142                 :            : static unsigned int get_offset(unsigned long index, struct xa_node *node)
     143                 :            : {
     144                 :  219064332 :         return (index >> node->shift) & XA_CHUNK_MASK;
     145                 :            : }
     146                 :            : 
     147                 :            : static void xas_set_offset(struct xa_state *xas)
     148                 :            : {
     149                 :    2645868 :         xas->xa_offset = get_offset(xas->xa_index, xas->xa_node);
     150                 :            : }
     151                 :            : 
     152                 :            : /* move the index either forwards (find) or backwards (sibling slot) */
     153                 :            : static void xas_move_index(struct xa_state *xas, unsigned long offset)
     154                 :            : {
     155                 :   47014715 :         unsigned int shift = xas->xa_node->shift;
     156                 :   47014715 :         xas->xa_index &= ~XA_CHUNK_MASK << shift;
     157                 :   47014715 :         xas->xa_index += offset << shift;
     158                 :            : }
     159                 :            : 
     160                 :            : static void xas_advance(struct xa_state *xas)
     161                 :            : {
     162                 :   46685538 :         xas->xa_offset++;
     163                 :   46685538 :         xas_move_index(xas, xas->xa_offset);
     164                 :            : }
     165                 :            : 
     166                 :            : static void *set_bounds(struct xa_state *xas)
     167                 :            : {
     168                 :    2805572 :         xas->xa_node = XAS_BOUNDS;
     169                 :            :         return NULL;
     170                 :            : }
     171                 :            : 
     172                 :            : /*
     173                 :            :  * Starts a walk.  If the @xas is already valid, we assume that it's on
     174                 :            :  * the right path and just return where we've got to.  If we're in an
     175                 :            :  * error state, return NULL.  If the index is outside the current scope
     176                 :            :  * of the xarray, return NULL without changing @xas->xa_node.  Otherwise
     177                 :            :  * set @xas->xa_node to NULL and return the current head of the array.
     178                 :            :  */
     179                 :  125993807 : static void *xas_start(struct xa_state *xas)
     180                 :            : {
     181                 :            :         void *entry;
     182                 :            : 
     183         [ +  + ]:  125993807 :         if (xas_valid(xas))
     184                 :     574539 :                 return xas_reload(xas);
     185         [ +  - ]:  125419268 :         if (xas_error(xas))
     186                 :            :                 return NULL;
     187                 :            : 
     188                 :  125429992 :         entry = xa_head(xas->xa);
     189         [ +  + ]:  125429992 :         if (!xa_is_node(entry)) {
     190         [ +  + ]:    6042383 :                 if (xas->xa_index)
     191                 :     841954 :                         return set_bounds(xas);
     192                 :            :         } else {
     193         [ +  + ]:  238775218 :                 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
     194                 :     193428 :                         return set_bounds(xas);
     195                 :            :         }
     196                 :            : 
     197                 :  124394610 :         xas->xa_node = NULL;
     198                 :  124394610 :         return entry;
     199                 :            : }
     200                 :            : 
     201                 :            : static void *xas_descend(struct xa_state *xas, struct xa_node *node)
     202                 :            : {
     203                 :  217714276 :         unsigned int offset = get_offset(xas->xa_index, node);
     204                 :            :         void *entry = xa_entry(xas->xa, node, offset);
     205                 :            : 
     206                 :  217714276 :         xas->xa_node = node;
     207                 :            :         if (xa_is_sibling(entry)) {
     208                 :            :                 offset = xa_to_sibling(entry);
     209                 :            :                 entry = xa_entry(xas->xa, node, offset);
     210                 :            :         }
     211                 :            : 
     212                 :  217714276 :         xas->xa_offset = offset;
     213                 :            :         return entry;
     214                 :            : }
     215                 :            : 
     216                 :            : /**
     217                 :            :  * xas_load() - Load an entry from the XArray (advanced).
     218                 :            :  * @xas: XArray operation state.
     219                 :            :  *
     220                 :            :  * Usually walks the @xas to the appropriate state to load the entry
     221                 :            :  * stored at xa_index.  However, it will do nothing and return %NULL if
     222                 :            :  * @xas is in an error state.  xas_load() will never expand the tree.
     223                 :            :  *
     224                 :            :  * If the xa_state is set up to operate on a multi-index entry, xas_load()
     225                 :            :  * may return %NULL or an internal entry, even if there are entries
     226                 :            :  * present within the range specified by @xas.
     227                 :            :  *
     228                 :            :  * Context: Any context.  The caller should hold the xa_lock or the RCU lock.
     229                 :            :  * Return: Usually an entry in the XArray, but see description for exceptions.
     230                 :            :  */
     231                 :  124740351 : void *xas_load(struct xa_state *xas)
     232                 :            : {
     233                 :  124740351 :         void *entry = xas_start(xas);
     234                 :            : 
     235         [ +  + ]:  347684742 :         while (xa_is_node(entry)) {
     236                 :            :                 struct xa_node *node = xa_to_node(entry);
     237                 :            : 
     238         [ +  + ]:  214075793 :                 if (xas->xa_shift > node->shift)
     239                 :            :                         break;
     240                 :            :                 entry = xas_descend(xas, node);
     241         [ +  + ]:  214034604 :                 if (node->shift == 0)
     242                 :            :                         break;
     243                 :            :         }
     244                 :  124757074 :         return entry;
     245                 :            : }
     246                 :            : EXPORT_SYMBOL_GPL(xas_load);
     247                 :            : 
     248                 :            : /* Move the radix tree node cache here */
     249                 :            : extern struct kmem_cache *radix_tree_node_cachep;
     250                 :            : extern void radix_tree_node_rcu_free(struct rcu_head *head);
     251                 :            : 
     252                 :            : #define XA_RCU_FREE     ((struct xarray *)1)
     253                 :            : 
     254                 :            : static void xa_node_free(struct xa_node *node)
     255                 :            : {
     256                 :            :         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
     257                 :      61008 :         node->array = XA_RCU_FREE;
     258                 :      61008 :         call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
     259                 :            : }
     260                 :            : 
     261                 :            : /*
     262                 :            :  * xas_destroy() - Free any resources allocated during the XArray operation.
     263                 :            :  * @xas: XArray operation state.
     264                 :            :  *
     265                 :            :  * This function is now internal-only.
     266                 :            :  */
     267                 :            : static void xas_destroy(struct xa_state *xas)
     268                 :            : {
     269                 :   10457244 :         struct xa_node *node = xas->xa_alloc;
     270                 :            : 
     271   [ -  +  -  + ]:   10457244 :         if (!node)
     272                 :            :                 return;
     273                 :            :         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
     274                 :          0 :         kmem_cache_free(radix_tree_node_cachep, node);
     275                 :          0 :         xas->xa_alloc = NULL;
     276                 :            : }
     277                 :            : 
     278                 :            : /**
     279                 :            :  * xas_nomem() - Allocate memory if needed.
     280                 :            :  * @xas: XArray operation state.
     281                 :            :  * @gfp: Memory allocation flags.
     282                 :            :  *
     283                 :            :  * If we need to add new nodes to the XArray, we try to allocate memory
     284                 :            :  * with GFP_NOWAIT while holding the lock, which will usually succeed.
     285                 :            :  * If it fails, @xas is flagged as needing memory to continue.  The caller
     286                 :            :  * should drop the lock and call xas_nomem().  If xas_nomem() succeeds,
     287                 :            :  * the caller should retry the operation.
     288                 :            :  *
     289                 :            :  * Forward progress is guaranteed as one node is allocated here and
     290                 :            :  * stored in the xa_state where it will be found by xas_alloc().  More
     291                 :            :  * nodes will likely be found in the slab allocator, but we do not tie
     292                 :            :  * them up here.
     293                 :            :  *
     294                 :            :  * Return: true if memory was needed, and was successfully allocated.
     295                 :            :  */
     296                 :   10456830 : bool xas_nomem(struct xa_state *xas, gfp_t gfp)
     297                 :            : {
     298         [ +  - ]:   10456830 :         if (xas->xa_node != XA_ERROR(-ENOMEM)) {
     299                 :            :                 xas_destroy(xas);
     300                 :            :                 return false;
     301                 :            :         }
     302         [ #  # ]:          0 :         if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
     303                 :          0 :                 gfp |= __GFP_ACCOUNT;
     304                 :          0 :         xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
     305         [ #  # ]:          0 :         if (!xas->xa_alloc)
     306                 :            :                 return false;
     307                 :            :         XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
     308                 :          0 :         xas->xa_node = XAS_RESTART;
     309                 :          0 :         return true;
     310                 :            : }
     311                 :            : EXPORT_SYMBOL_GPL(xas_nomem);
     312                 :            : 
     313                 :            : /*
     314                 :            :  * __xas_nomem() - Drop locks and allocate memory if needed.
     315                 :            :  * @xas: XArray operation state.
     316                 :            :  * @gfp: Memory allocation flags.
     317                 :            :  *
     318                 :            :  * Internal variant of xas_nomem().
     319                 :            :  *
     320                 :            :  * Return: true if memory was needed, and was successfully allocated.
     321                 :            :  */
     322                 :        414 : static bool __xas_nomem(struct xa_state *xas, gfp_t gfp)
     323                 :            :         __must_hold(xas->xa->xa_lock)
     324                 :            : {
     325                 :        414 :         unsigned int lock_type = xa_lock_type(xas->xa);
     326                 :            : 
     327         [ +  - ]:        414 :         if (xas->xa_node != XA_ERROR(-ENOMEM)) {
     328                 :            :                 xas_destroy(xas);
     329                 :            :                 return false;
     330                 :            :         }
     331         [ #  # ]:          0 :         if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
     332                 :          0 :                 gfp |= __GFP_ACCOUNT;
     333         [ #  # ]:          0 :         if (gfpflags_allow_blocking(gfp)) {
     334                 :          0 :                 xas_unlock_type(xas, lock_type);
     335                 :          0 :                 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
     336                 :          0 :                 xas_lock_type(xas, lock_type);
     337                 :            :         } else {
     338                 :          0 :                 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp);
     339                 :            :         }
     340         [ #  # ]:          0 :         if (!xas->xa_alloc)
     341                 :            :                 return false;
     342                 :            :         XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list));
     343                 :          0 :         xas->xa_node = XAS_RESTART;
     344                 :          0 :         return true;
     345                 :            : }
     346                 :            : 
     347                 :            : static void xas_update(struct xa_state *xas, struct xa_node *node)
     348                 :            : {
     349   [ +  +  +  +  :   11179931 :         if (xas->xa_update)
          #  #  +  +  +  
                -  +  + ]
     350                 :    9099003 :                 xas->xa_update(node);
     351                 :            :         else
     352                 :            :                 XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
     353                 :            : }
     354                 :            : 
     355                 :     469427 : static void *xas_alloc(struct xa_state *xas, unsigned int shift)
     356                 :            : {
     357                 :     469427 :         struct xa_node *parent = xas->xa_node;
     358                 :     469427 :         struct xa_node *node = xas->xa_alloc;
     359                 :            : 
     360         [ +  + ]:     469427 :         if (xas_invalid(xas))
     361                 :            :                 return NULL;
     362                 :            : 
     363         [ -  + ]:     469161 :         if (node) {
     364                 :          0 :                 xas->xa_alloc = NULL;
     365                 :            :         } else {
     366                 :            :                 gfp_t gfp = GFP_NOWAIT | __GFP_NOWARN;
     367                 :            : 
     368         [ +  + ]:     469161 :                 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT)
     369                 :            :                         gfp |= __GFP_ACCOUNT;
     370                 :            : 
     371                 :     469161 :                 node = kmem_cache_alloc(radix_tree_node_cachep, gfp);
     372         [ -  + ]:     469511 :                 if (!node) {
     373                 :            :                         xas_set_err(xas, -ENOMEM);
     374                 :          0 :                         return NULL;
     375                 :            :                 }
     376                 :            :         }
     377                 :            : 
     378         [ +  + ]:     469511 :         if (parent) {
     379                 :     212809 :                 node->offset = xas->xa_offset;
     380                 :     212809 :                 parent->count++;
     381                 :            :                 XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);
     382                 :            :                 xas_update(xas, parent);
     383                 :            :         }
     384                 :            :         XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
     385                 :            :         XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
     386                 :     469490 :         node->shift = shift;
     387                 :     469490 :         node->count = 0;
     388                 :     469490 :         node->nr_values = 0;
     389                 :     469490 :         RCU_INIT_POINTER(node->parent, xas->xa_node);
     390                 :     469490 :         node->array = xas->xa;
     391                 :            : 
     392                 :     469490 :         return node;
     393                 :            : }
     394                 :            : 
     395                 :            : #ifdef CONFIG_XARRAY_MULTI
     396                 :            : /* Returns the number of indices covered by a given xa_state */
     397                 :            : static unsigned long xas_size(const struct xa_state *xas)
     398                 :            : {
     399                 :            :         return (xas->xa_sibs + 1UL) << xas->xa_shift;
     400                 :            : }
     401                 :            : #endif
     402                 :            : 
     403                 :            : /*
     404                 :            :  * Use this to calculate the maximum index that will need to be created
     405                 :            :  * in order to add the entry described by @xas.  Because we cannot store a
     406                 :            :  * multiple-index entry at index 0, the calculation is a little more complex
     407                 :            :  * than you might expect.
     408                 :            :  */
     409                 :            : static unsigned long xas_max(struct xa_state *xas)
     410                 :            : {
     411                 :    1082755 :         unsigned long max = xas->xa_index;
     412                 :            : 
     413                 :            : #ifdef CONFIG_XARRAY_MULTI
     414                 :            :         if (xas->xa_shift || xas->xa_sibs) {
     415                 :            :                 unsigned long mask = xas_size(xas) - 1;
     416                 :            :                 max |= mask;
     417                 :            :                 if (mask == max)
     418                 :            :                         max++;
     419                 :            :         }
     420                 :            : #endif
     421                 :            : 
     422                 :            :         return max;
     423                 :            : }
     424                 :            : 
     425                 :            : /* The maximum index that can be contained in the array without expanding it */
     426                 :            : static unsigned long max_index(void *entry)
     427                 :            : {
     428   [ +  +  +  + ]:    1757328 :         if (!xa_is_node(entry))
     429                 :            :                 return 0;
     430                 :     609605 :         return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1;
     431                 :            : }
     432                 :            : 
     433                 :      26728 : static void xas_shrink(struct xa_state *xas)
     434                 :            : {
     435                 :      26728 :         struct xarray *xa = xas->xa;
     436                 :      26728 :         struct xa_node *node = xas->xa_node;
     437                 :            : 
     438                 :            :         for (;;) {
     439                 :            :                 void *entry;
     440                 :            : 
     441                 :            :                 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
     442         [ +  + ]:      26740 :                 if (node->count != 1)
     443                 :            :                         break;
     444                 :            :                 entry = xa_entry_locked(xa, node, 0);
     445         [ +  + ]:       4889 :                 if (!entry)
     446                 :            :                         break;
     447   [ -  +  #  # ]:         12 :                 if (!xa_is_node(entry) && node->shift)
     448                 :            :                         break;
     449   [ -  +  #  # ]:         12 :                 if (xa_is_zero(entry) && xa_zero_busy(xa))
     450                 :            :                         entry = NULL;
     451                 :         12 :                 xas->xa_node = XAS_BOUNDS;
     452                 :            : 
     453                 :            :                 RCU_INIT_POINTER(xa->xa_head, entry);
     454   [ -  +  #  # ]:         12 :                 if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK))
     455                 :            :                         xa_mark_clear(xa, XA_FREE_MARK);
     456                 :            : 
     457                 :         12 :                 node->count = 0;
     458                 :         12 :                 node->nr_values = 0;
     459         [ -  + ]:         12 :                 if (!xa_is_node(entry))
     460                 :            :                         RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
     461                 :            :                 xas_update(xas, node);
     462                 :            :                 xa_node_free(node);
     463         [ +  - ]:         12 :                 if (!xa_is_node(entry))
     464                 :            :                         break;
     465                 :            :                 node = xa_to_node(entry);
     466                 :         12 :                 node->parent = NULL;
     467                 :         12 :         }
     468                 :      26728 : }
     469                 :            : 
     470                 :            : /*
     471                 :            :  * xas_delete_node() - Attempt to delete an xa_node
     472                 :            :  * @xas: Array operation state.
     473                 :            :  *
     474                 :            :  * Attempts to delete the @xas->xa_node.  This will fail if xa->node has
     475                 :            :  * a non-zero reference count.
     476                 :            :  */
     477                 :    1423143 : static void xas_delete_node(struct xa_state *xas)
     478                 :            : {
     479                 :    1423143 :         struct xa_node *node = xas->xa_node;
     480                 :            : 
     481                 :            :         for (;;) {
     482                 :            :                 struct xa_node *parent;
     483                 :            : 
     484                 :            :                 XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
     485         [ +  + ]:    1478849 :                 if (node->count)
     486                 :            :                         break;
     487                 :            : 
     488                 :            :                 parent = xa_parent_locked(xas->xa, node);
     489                 :      60996 :                 xas->xa_node = parent;
     490                 :      60996 :                 xas->xa_offset = node->offset;
     491                 :            :                 xa_node_free(node);
     492                 :            : 
     493         [ +  + ]:      60996 :                 if (!parent) {
     494                 :       5290 :                         xas->xa->xa_head = NULL;
     495                 :       5290 :                         xas->xa_node = XAS_BOUNDS;
     496                 :    1428433 :                         return;
     497                 :            :                 }
     498                 :            : 
     499                 :      55706 :                 parent->slots[xas->xa_offset] = NULL;
     500                 :      55706 :                 parent->count--;
     501                 :            :                 XA_NODE_BUG_ON(parent, parent->count > XA_CHUNK_SIZE);
     502                 :            :                 node = parent;
     503                 :            :                 xas_update(xas, node);
     504                 :            :         }
     505                 :            : 
     506         [ +  + ]:    1417853 :         if (!node->parent)
     507                 :      26728 :                 xas_shrink(xas);
     508                 :            : }
     509                 :            : 
     510                 :            : /**
     511                 :            :  * xas_free_nodes() - Free this node and all nodes that it references
     512                 :            :  * @xas: Array operation state.
     513                 :            :  * @top: Node to free
     514                 :            :  *
     515                 :            :  * This node has been removed from the tree.  We must now free it and all
     516                 :            :  * of its subnodes.  There may be RCU walkers with references into the tree,
     517                 :            :  * so we must replace all entries with retry markers.
     518                 :            :  */
     519                 :          0 : static void xas_free_nodes(struct xa_state *xas, struct xa_node *top)
     520                 :            : {
     521                 :            :         unsigned int offset = 0;
     522                 :            :         struct xa_node *node = top;
     523                 :            : 
     524                 :            :         for (;;) {
     525                 :            :                 void *entry = xa_entry_locked(xas->xa, node, offset);
     526                 :            : 
     527   [ #  #  #  # ]:          0 :                 if (node->shift && xa_is_node(entry)) {
     528                 :            :                         node = xa_to_node(entry);
     529                 :            :                         offset = 0;
     530                 :          0 :                         continue;
     531                 :            :                 }
     532         [ #  # ]:          0 :                 if (entry)
     533                 :          0 :                         RCU_INIT_POINTER(node->slots[offset], XA_RETRY_ENTRY);
     534                 :          0 :                 offset++;
     535         [ #  # ]:          0 :                 while (offset == XA_CHUNK_SIZE) {
     536                 :            :                         struct xa_node *parent;
     537                 :            : 
     538                 :            :                         parent = xa_parent_locked(xas->xa, node);
     539                 :          0 :                         offset = node->offset + 1;
     540                 :          0 :                         node->count = 0;
     541                 :          0 :                         node->nr_values = 0;
     542                 :            :                         xas_update(xas, node);
     543                 :            :                         xa_node_free(node);
     544         [ #  # ]:          0 :                         if (node == top)
     545                 :          0 :                                 return;
     546                 :            :                         node = parent;
     547                 :            :                 }
     548                 :            :         }
     549                 :            : }
     550                 :            : 
     551                 :            : /*
     552                 :            :  * xas_expand adds nodes to the head of the tree until it has reached
     553                 :            :  * sufficient height to be able to contain @xas->xa_index
     554                 :            :  */
     555                 :    1082755 : static int xas_expand(struct xa_state *xas, void *head)
     556                 :            : {
     557                 :    1082755 :         struct xarray *xa = xas->xa;
     558                 :            :         struct xa_node *node = NULL;
     559                 :            :         unsigned int shift = 0;
     560                 :            :         unsigned long max = xas_max(xas);
     561                 :            : 
     562         [ +  + ]:    1082755 :         if (!head) {
     563         [ +  + ]:     776435 :                 if (max == 0)
     564                 :            :                         return 0;
     565         [ +  + ]:      15484 :                 while ((max >> shift) >= XA_CHUNK_SIZE)
     566                 :       8061 :                         shift += XA_CHUNK_SHIFT;
     567                 :       7423 :                 return shift + XA_CHUNK_SHIFT;
     568         [ +  + ]:     306320 :         } else if (xa_is_node(head)) {
     569                 :            :                 node = xa_to_node(head);
     570                 :      19214 :                 shift = node->shift + XA_CHUNK_SHIFT;
     571                 :            :         }
     572                 :     306320 :         xas->xa_node = NULL;
     573                 :            : 
     574         [ +  + ]:     861888 :         while (max > max_index(head)) {
     575                 :            :                 xa_mark_t mark = 0;
     576                 :            : 
     577                 :            :                 XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
     578                 :     249049 :                 node = xas_alloc(xas, shift);
     579         [ +  + ]:     249266 :                 if (!node)
     580                 :            :                         return -ENOMEM;
     581                 :            : 
     582                 :     249034 :                 node->count = 1;
     583         [ -  + ]:     249034 :                 if (xa_is_value(head))
     584                 :          0 :                         node->nr_values = 1;
     585                 :            :                 RCU_INIT_POINTER(node->slots[0], head);
     586                 :            : 
     587                 :            :                 /* Propagate the aggregated mark info to the new child */
     588                 :            :                 for (;;) {
     589   [ +  +  +  + ]:     747068 :                         if (xa_track_free(xa) && mark == XA_FREE_MARK) {
     590                 :            :                                 node_mark_all(node, XA_FREE_MARK);
     591         [ +  - ]:        414 :                                 if (!xa_marked(xa, XA_FREE_MARK)) {
     592                 :            :                                         node_clear_mark(node, 0, XA_FREE_MARK);
     593                 :            :                                         xa_mark_set(xa, XA_FREE_MARK);
     594                 :            :                                 }
     595         [ +  + ]:     746654 :                         } else if (xa_marked(xa, mark)) {
     596                 :            :                                 node_set_mark(node, 0, mark);
     597                 :            :                         }
     598         [ +  + ]:     747068 :                         if (mark == XA_MARK_MAX)
     599                 :            :                                 break;
     600                 :     498034 :                         mark_inc(mark);
     601                 :     498034 :                 }
     602                 :            : 
     603                 :            :                 /*
     604                 :            :                  * Now that the new node is fully initialised, we can add
     605                 :            :                  * it to the tree
     606                 :            :                  */
     607         [ +  + ]:     249034 :                 if (xa_is_node(head)) {
     608                 :      20518 :                         xa_to_node(head)->offset = 0;
     609                 :      20518 :                         rcu_assign_pointer(xa_to_node(head)->parent, node);
     610                 :            :                 }
     611                 :            :                 head = xa_mk_node(node);
     612                 :     249034 :                 rcu_assign_pointer(xa->xa_head, head);
     613                 :            :                 xas_update(xas, node);
     614                 :            : 
     615                 :     249248 :                 shift += XA_CHUNK_SHIFT;
     616                 :            :         }
     617                 :            : 
     618                 :     306519 :         xas->xa_node = node;
     619                 :     306519 :         return shift;
     620                 :            : }
     621                 :            : 
     622                 :            : /*
     623                 :            :  * xas_create() - Create a slot to store an entry in.
     624                 :            :  * @xas: XArray operation state.
     625                 :            :  * @allow_root: %true if we can store the entry in the root directly
     626                 :            :  *
     627                 :            :  * Most users will not need to call this function directly, as it is called
     628                 :            :  * by xas_store().  It is useful for doing conditional store operations
     629                 :            :  * (see the xa_cmpxchg() implementation for an example).
     630                 :            :  *
     631                 :            :  * Return: If the slot already existed, returns the contents of this slot.
     632                 :            :  * If the slot was newly created, returns %NULL.  If it failed to create the
     633                 :            :  * slot, returns %NULL and indicates the error in @xas.
     634                 :            :  */
     635                 :   11337367 : static void *xas_create(struct xa_state *xas, bool allow_root)
     636                 :            : {
     637                 :   11337367 :         struct xarray *xa = xas->xa;
     638                 :            :         void *entry;
     639                 :            :         void __rcu **slot;
     640                 :   11337367 :         struct xa_node *node = xas->xa_node;
     641                 :            :         int shift;
     642                 :   11337367 :         unsigned int order = xas->xa_shift;
     643                 :            : 
     644         [ +  + ]:   11337367 :         if (xas_top(node)) {
     645                 :            :                 entry = xa_head_locked(xa);
     646                 :    1083226 :                 xas->xa_node = NULL;
     647   [ +  +  -  + ]:    1859058 :                 if (!entry && xa_zero_busy(xa))
     648                 :            :                         entry = XA_ZERO_ENTRY;
     649                 :    1083226 :                 shift = xas_expand(xas, entry);
     650         [ +  + ]:    1083110 :                 if (shift < 0)
     651                 :            :                         return NULL;
     652         [ -  + ]:    1083537 :                 if (!shift && !allow_root)
     653                 :            :                         shift = XA_CHUNK_SHIFT;
     654                 :            :                 entry = xa_head_locked(xa);
     655                 :    1083537 :                 slot = &xa->xa_head;
     656         [ +  + ]:   10254141 :         } else if (xas_error(xas)) {
     657                 :            :                 return NULL;
     658         [ +  - ]:   10198255 :         } else if (node) {
     659                 :   10198255 :                 unsigned int offset = xas->xa_offset;
     660                 :            : 
     661                 :   10198255 :                 shift = node->shift;
     662                 :            :                 entry = xa_entry_locked(xa, node, offset);
     663                 :   10198255 :                 slot = &node->slots[offset];
     664                 :            :         } else {
     665                 :            :                 shift = 0;
     666                 :            :                 entry = xa_head_locked(xa);
     667                 :          0 :                 slot = &xa->xa_head;
     668                 :            :         }
     669                 :            : 
     670         [ +  + ]:   11749702 :         while (shift > order) {
     671                 :     468194 :                 shift -= XA_CHUNK_SHIFT;
     672         [ +  + ]:     468194 :                 if (!entry) {
     673                 :     220259 :                         node = xas_alloc(xas, shift);
     674         [ +  + ]:     220235 :                         if (!node)
     675                 :            :                                 break;
     676         [ -  + ]:     220230 :                         if (xa_track_free(xa))
     677                 :            :                                 node_mark_all(node, XA_FREE_MARK);
     678                 :     220230 :                         rcu_assign_pointer(*slot, xa_mk_node(node));
     679         [ +  + ]:     247935 :                 } else if (xa_is_node(entry)) {
     680                 :            :                         node = xa_to_node(entry);
     681                 :            :                 } else {
     682                 :            :                         break;
     683                 :            :                 }
     684                 :            :                 entry = xas_descend(xas, node);
     685                 :     467910 :                 slot = &node->slots[xas->xa_offset];
     686                 :            :         }
     687                 :            : 
     688                 :   11281473 :         return entry;
     689                 :            : }
     690                 :            : 
     691                 :            : /**
     692                 :            :  * xas_create_range() - Ensure that stores to this range will succeed
     693                 :            :  * @xas: XArray operation state.
     694                 :            :  *
     695                 :            :  * Creates all of the slots in the range covered by @xas.  Sets @xas to
     696                 :            :  * create single-index entries and positions it at the beginning of the
     697                 :            :  * range.  This is for the benefit of users which have not yet been
     698                 :            :  * converted to use multi-index entries.
     699                 :            :  */
     700                 :    1249961 : void xas_create_range(struct xa_state *xas)
     701                 :            : {
     702                 :    1249961 :         unsigned long index = xas->xa_index;
     703                 :    1249961 :         unsigned char shift = xas->xa_shift;
     704                 :    1249961 :         unsigned char sibs = xas->xa_sibs;
     705                 :            : 
     706                 :    1249961 :         xas->xa_index |= ((sibs + 1) << shift) - 1;
     707   [ +  +  +  + ]:    1249961 :         if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift)
     708                 :    1188726 :                 xas->xa_offset |= sibs;
     709                 :    1249961 :         xas->xa_shift = 0;
     710                 :    1249961 :         xas->xa_sibs = 0;
     711                 :            : 
     712                 :            :         for (;;) {
     713                 :    1249961 :                 xas_create(xas, true);
     714         [ +  - ]:    1249893 :                 if (xas_error(xas))
     715                 :            :                         goto restore;
     716         [ -  + ]:    1249893 :                 if (xas->xa_index <= (index | XA_CHUNK_MASK))
     717                 :            :                         goto success;
     718                 :          0 :                 xas->xa_index -= XA_CHUNK_SIZE;
     719                 :            : 
     720                 :            :                 for (;;) {
     721                 :          0 :                         struct xa_node *node = xas->xa_node;
     722                 :          0 :                         xas->xa_node = xa_parent_locked(xas->xa, node);
     723                 :          0 :                         xas->xa_offset = node->offset - 1;
     724         [ #  # ]:          0 :                         if (node->offset != 0)
     725                 :            :                                 break;
     726                 :            :                 }
     727                 :            :         }
     728                 :            : 
     729                 :            : restore:
     730                 :          0 :         xas->xa_shift = shift;
     731                 :          0 :         xas->xa_sibs = sibs;
     732                 :          0 :         xas->xa_index = index;
     733                 :    1249893 :         return;
     734                 :            : success:
     735                 :    1249893 :         xas->xa_index = index;
     736         [ +  + ]:    1249893 :         if (xas->xa_node)
     737                 :            :                 xas_set_offset(xas);
     738                 :            : }
     739                 :            : EXPORT_SYMBOL_GPL(xas_create_range);
     740                 :            : 
     741                 :   11476863 : static void update_node(struct xa_state *xas, struct xa_node *node,
     742                 :            :                 int count, int values)
     743                 :            : {
     744   [ +  +  +  + ]:   11476863 :         if (!node || (!count && !values))
     745                 :   11477288 :                 return;
     746                 :            : 
     747                 :   10662132 :         node->count += count;
     748                 :   10662132 :         node->nr_values += values;
     749                 :            :         XA_NODE_BUG_ON(node, node->count > XA_CHUNK_SIZE);
     750                 :            :         XA_NODE_BUG_ON(node, node->nr_values > XA_CHUNK_SIZE);
     751                 :            :         xas_update(xas, node);
     752         [ +  + ]:   10662557 :         if (count < 0)
     753                 :    1423143 :                 xas_delete_node(xas);
     754                 :            : }
     755                 :            : 
     756                 :            : /**
     757                 :            :  * xas_store() - Store this entry in the XArray.
     758                 :            :  * @xas: XArray operation state.
     759                 :            :  * @entry: New entry.
     760                 :            :  *
     761                 :            :  * If @xas is operating on a multi-index entry, the entry returned by this
     762                 :            :  * function is essentially meaningless (it may be an internal entry or it
     763                 :            :  * may be %NULL, even if there are non-NULL entries at some of the indices
     764                 :            :  * covered by the range).  This is not a problem for any current users,
     765                 :            :  * and can be changed if needed.
     766                 :            :  *
     767                 :            :  * Return: The old entry at this index.
     768                 :            :  */
     769                 :   11533462 : void *xas_store(struct xa_state *xas, void *entry)
     770                 :            : {
     771                 :            :         struct xa_node *node;
     772                 :   11533462 :         void __rcu **slot = &xas->xa->xa_head;
     773                 :            :         unsigned int offset, max;
     774                 :            :         int count = 0;
     775                 :            :         int values = 0;
     776                 :            :         void *first, *next;
     777                 :            :         bool value = xa_is_value(entry);
     778                 :            : 
     779         [ +  + ]:   11533462 :         if (entry) {
     780   [ +  +  +  + ]:   20174448 :                 bool allow_root = !xa_is_node(entry) && !xa_is_zero(entry);
     781                 :   10087460 :                 first = xas_create(xas, allow_root);
     782                 :            :         } else {
     783                 :    1446002 :                 first = xas_load(xas);
     784                 :            :         }
     785                 :            : 
     786         [ +  + ]:   11532537 :         if (xas_invalid(xas))
     787                 :            :                 return first;
     788                 :            :         node = xas->xa_node;
     789   [ +  +  -  + ]:   11476645 :         if (node && (xas->xa_shift < node->shift))
     790                 :          0 :                 xas->xa_sibs = 0;
     791   [ -  +  #  # ]:   11476645 :         if ((first == entry) && !xas->xa_sibs)
     792                 :            :                 return first;
     793                 :            : 
     794                 :            :         next = first;
     795                 :   11477504 :         offset = xas->xa_offset;
     796                 :   11477504 :         max = xas->xa_offset + xas->xa_sibs;
     797         [ +  + ]:   11477504 :         if (node) {
     798                 :   10668042 :                 slot = &node->slots[offset];
     799         [ -  + ]:   10668042 :                 if (xas->xa_sibs)
     800                 :          0 :                         xas_squash_marks(xas);
     801                 :            :         }
     802         [ +  + ]:   11477504 :         if (!entry)
     803                 :    1446002 :                 xas_init_marks(xas);
     804                 :            : 
     805                 :            :         for (;;) {
     806                 :            :                 /*
     807                 :            :                  * Must clear the marks before setting the entry to NULL,
     808                 :            :                  * otherwise xas_for_each_marked may find a NULL entry and
     809                 :            :                  * stop early.  rcu_assign_pointer contains a release barrier
     810                 :            :                  * so the mark clearing will appear to happen before the
     811                 :            :                  * entry is set to NULL.
     812                 :            :                  */
     813                 :   11477504 :                 rcu_assign_pointer(*slot, entry);
     814   [ -  +  #  #  :   11477296 :                 if (xa_is_node(next) && (!node || node->shift))
                   #  # ]
     815                 :        444 :                         xas_free_nodes(xas, xa_to_node(next));
     816         [ +  + ]:   11476893 :                 if (!node)
     817                 :            :                         break;
     818                 :   10668687 :                 count += !next - !entry;
     819                 :   10668687 :                 values += !xa_is_value(first) - !value;
     820         [ +  + ]:   10668687 :                 if (entry) {
     821         [ -  + ]:    9245544 :                         if (offset == max)
     822                 :            :                                 break;
     823                 :            :                         if (!xa_is_sibling(entry))
     824                 :          0 :                                 entry = xa_mk_sibling(xas->xa_offset);
     825                 :            :                 } else {
     826         [ +  + ]:    1423143 :                         if (offset == XA_CHUNK_MASK)
     827                 :            :                                 break;
     828                 :            :                 }
     829                 :    1399348 :                 next = xa_entry_locked(xas->xa, node, ++offset);
     830                 :            :                 if (!xa_is_sibling(next)) {
     831         [ -  + ]:    1399348 :                         if (!entry && (offset > max))
     832                 :            :                                 break;
     833                 :            :                         first = next;
     834                 :            :                 }
     835                 :          0 :                 slot++;
     836                 :          0 :         }
     837                 :            : 
     838                 :   11476893 :         update_node(xas, node, count, values);
     839                 :   11477543 :         return first;
     840                 :            : }
     841                 :            : EXPORT_SYMBOL_GPL(xas_store);
     842                 :            : 
     843                 :            : /**
     844                 :            :  * xas_get_mark() - Returns the state of this mark.
     845                 :            :  * @xas: XArray operation state.
     846                 :            :  * @mark: Mark number.
     847                 :            :  *
     848                 :            :  * Return: true if the mark is set, false if the mark is clear or @xas
     849                 :            :  * is in an error state.
     850                 :            :  */
     851                 :          0 : bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)
     852                 :            : {
     853         [ #  # ]:          0 :         if (xas_invalid(xas))
     854                 :            :                 return false;
     855         [ #  # ]:          0 :         if (!xas->xa_node)
     856                 :          0 :                 return xa_marked(xas->xa, mark);
     857                 :          0 :         return node_get_mark(xas->xa_node, xas->xa_offset, mark);
     858                 :            : }
     859                 :            : EXPORT_SYMBOL_GPL(xas_get_mark);
     860                 :            : 
     861                 :            : /**
     862                 :            :  * xas_set_mark() - Sets the mark on this entry and its parents.
     863                 :            :  * @xas: XArray operation state.
     864                 :            :  * @mark: Mark number.
     865                 :            :  *
     866                 :            :  * Sets the specified mark on this entry, and walks up the tree setting it
     867                 :            :  * on all the ancestor entries.  Does nothing if @xas has not been walked to
     868                 :            :  * an entry, or is in an error state.
     869                 :            :  */
     870                 :    1242567 : void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)
     871                 :            : {
     872                 :    1242567 :         struct xa_node *node = xas->xa_node;
     873                 :    1242567 :         unsigned int offset = xas->xa_offset;
     874                 :            : 
     875         [ +  + ]:    1242567 :         if (xas_invalid(xas))
     876                 :            :                 return;
     877                 :            : 
     878         [ +  + ]:    2060244 :         while (node) {
     879         [ +  + ]:    1117307 :                 if (node_set_mark(node, offset, mark))
     880                 :            :                         return;
     881                 :     817685 :                 offset = node->offset;
     882                 :            :                 node = xa_parent_locked(xas->xa, node);
     883                 :            :         }
     884                 :            : 
     885         [ +  + ]:    1885874 :         if (!xa_marked(xas->xa, mark))
     886                 :            :                 xa_mark_set(xas->xa, mark);
     887                 :            : }
     888                 :            : EXPORT_SYMBOL_GPL(xas_set_mark);
     889                 :            : 
     890                 :            : /**
     891                 :            :  * xas_clear_mark() - Clears the mark on this entry and its parents.
     892                 :            :  * @xas: XArray operation state.
     893                 :            :  * @mark: Mark number.
     894                 :            :  *
     895                 :            :  * Clears the specified mark on this entry, and walks back to the head
     896                 :            :  * attempting to clear it on all the ancestor entries.  Does nothing if
     897                 :            :  * @xas has not been walked to an entry, or is in an error state.
     898                 :            :  */
     899                 :    8294887 : void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)
     900                 :            : {
     901                 :    8294887 :         struct xa_node *node = xas->xa_node;
     902                 :    8294887 :         unsigned int offset = xas->xa_offset;
     903                 :            : 
     904         [ +  + ]:    8294887 :         if (xas_invalid(xas))
     905                 :            :                 return;
     906                 :            : 
     907         [ +  + ]:    8538514 :         while (node) {
     908         [ +  + ]:    7889488 :                 if (!node_clear_mark(node, offset, mark))
     909                 :            :                         return;
     910         [ +  + ]:     768449 :                 if (node_any_mark(node, mark))
     911                 :            :                         return;
     912                 :            : 
     913                 :     245224 :                 offset = node->offset;
     914                 :            :                 node = xa_parent_locked(xas->xa, node);
     915                 :            :         }
     916                 :            : 
     917         [ +  + ]:    1298052 :         if (xa_marked(xas->xa, mark))
     918                 :            :                 xa_mark_clear(xas->xa, mark);
     919                 :            : }
     920                 :            : EXPORT_SYMBOL_GPL(xas_clear_mark);
     921                 :            : 
     922                 :            : /**
     923                 :            :  * xas_init_marks() - Initialise all marks for the entry
     924                 :            :  * @xas: Array operations state.
     925                 :            :  *
     926                 :            :  * Initialise all marks for the entry specified by @xas.  If we're tracking
     927                 :            :  * free entries with a mark, we need to set it on all entries.  All other
     928                 :            :  * marks are cleared.
     929                 :            :  *
     930                 :            :  * This implementation is not as efficient as it could be; we may walk
     931                 :            :  * up the tree multiple times.
     932                 :            :  */
     933                 :    2317465 : void xas_init_marks(const struct xa_state *xas)
     934                 :            : {
     935                 :            :         xa_mark_t mark = 0;
     936                 :            : 
     937                 :            :         for (;;) {
     938   [ +  +  +  + ]:   13904790 :                 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)
     939                 :        621 :                         xas_set_mark(xas, mark);
     940                 :            :                 else
     941                 :    6951774 :                         xas_clear_mark(xas, mark);
     942         [ +  + ]:    6952395 :                 if (mark == XA_MARK_MAX)
     943                 :            :                         break;
     944                 :    4634930 :                 mark_inc(mark);
     945                 :    4634930 :         }
     946                 :    2317465 : }
     947                 :            : EXPORT_SYMBOL_GPL(xas_init_marks);
     948                 :            : 
     949                 :            : /**
     950                 :            :  * xas_pause() - Pause a walk to drop a lock.
     951                 :            :  * @xas: XArray operation state.
     952                 :            :  *
     953                 :            :  * Some users need to pause a walk and drop the lock they're holding in
     954                 :            :  * order to yield to a higher priority thread or carry out an operation
     955                 :            :  * on an entry.  Those users should call this function before they drop
     956                 :            :  * the lock.  It resets the @xas to be suitable for the next iteration
     957                 :            :  * of the loop after the user has reacquired the lock.  If most entries
     958                 :            :  * found during a walk require you to call xas_pause(), the xa_for_each()
     959                 :            :  * iterator may be more appropriate.
     960                 :            :  *
     961                 :            :  * Note that xas_pause() only works for forward iteration.  If a user needs
     962                 :            :  * to pause a reverse iteration, we will need a xas_pause_rev().
     963                 :            :  */
     964                 :          0 : void xas_pause(struct xa_state *xas)
     965                 :            : {
     966                 :          0 :         struct xa_node *node = xas->xa_node;
     967                 :            : 
     968         [ #  # ]:          0 :         if (xas_invalid(xas))
     969                 :          0 :                 return;
     970                 :            : 
     971                 :          0 :         xas->xa_node = XAS_RESTART;
     972         [ #  # ]:          0 :         if (node) {
     973                 :          0 :                 unsigned long offset = xas->xa_offset;
     974         [ #  # ]:          0 :                 while (++offset < XA_CHUNK_SIZE) {
     975                 :            :                         if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
     976                 :            :                                 break;
     977                 :            :                 }
     978                 :          0 :                 xas->xa_index += (offset - xas->xa_offset) << node->shift;
     979         [ #  # ]:          0 :                 if (xas->xa_index == 0)
     980                 :          0 :                         xas->xa_node = XAS_BOUNDS;
     981                 :            :         } else {
     982                 :          0 :                 xas->xa_index++;
     983                 :            :         }
     984                 :            : }
     985                 :            : EXPORT_SYMBOL_GPL(xas_pause);
     986                 :            : 
     987                 :            : /*
     988                 :            :  * __xas_prev() - Find the previous entry in the XArray.
     989                 :            :  * @xas: XArray operation state.
     990                 :            :  *
     991                 :            :  * Helper function for xas_prev() which handles all the complex cases
     992                 :            :  * out of line.
     993                 :            :  */
     994                 :      48166 : void *__xas_prev(struct xa_state *xas)
     995                 :            : {
     996                 :            :         void *entry;
     997                 :            : 
     998         [ +  + ]:      96332 :         if (!xas_frozen(xas->xa_node))
     999                 :        129 :                 xas->xa_index--;
    1000         [ -  + ]:      48166 :         if (!xas->xa_node)
    1001                 :          0 :                 return set_bounds(xas);
    1002         [ +  + ]:      48166 :         if (xas_not_node(xas->xa_node))
    1003                 :      48038 :                 return xas_load(xas);
    1004                 :            : 
    1005         [ +  + ]:        256 :         if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
    1006                 :        127 :                 xas->xa_offset--;
    1007                 :            : 
    1008         [ +  - ]:        127 :         while (xas->xa_offset == 255) {
    1009                 :        127 :                 xas->xa_offset = xas->xa_node->offset - 1;
    1010                 :        127 :                 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
    1011         [ -  + ]:        127 :                 if (!xas->xa_node)
    1012                 :        128 :                         return set_bounds(xas);
    1013                 :            :         }
    1014                 :            : 
    1015                 :            :         for (;;) {
    1016                 :          0 :                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
    1017         [ #  # ]:          0 :                 if (!xa_is_node(entry))
    1018                 :          0 :                         return entry;
    1019                 :            : 
    1020                 :          0 :                 xas->xa_node = xa_to_node(entry);
    1021                 :            :                 xas_set_offset(xas);
    1022                 :            :         }
    1023                 :            : }
    1024                 :            : EXPORT_SYMBOL_GPL(__xas_prev);
    1025                 :            : 
    1026                 :            : /*
    1027                 :            :  * __xas_next() - Find the next entry in the XArray.
    1028                 :            :  * @xas: XArray operation state.
    1029                 :            :  *
    1030                 :            :  * Helper function for xas_next() which handles all the complex cases
    1031                 :            :  * out of line.
    1032                 :            :  */
    1033                 :     137118 : void *__xas_next(struct xa_state *xas)
    1034                 :            : {
    1035                 :            :         void *entry;
    1036                 :            : 
    1037         [ +  + ]:     274236 :         if (!xas_frozen(xas->xa_node))
    1038                 :      18067 :                 xas->xa_index++;
    1039         [ -  + ]:     137118 :         if (!xas->xa_node)
    1040                 :          0 :                 return set_bounds(xas);
    1041         [ +  + ]:     137118 :         if (xas_not_node(xas->xa_node))
    1042                 :     119051 :                 return xas_load(xas);
    1043                 :            : 
    1044         [ +  + ]:      36134 :         if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node))
    1045                 :      18065 :                 xas->xa_offset++;
    1046                 :            : 
    1047         [ +  + ]:      36130 :         while (xas->xa_offset == XA_CHUNK_SIZE) {
    1048                 :      18063 :                 xas->xa_offset = xas->xa_node->offset + 1;
    1049                 :      18063 :                 xas->xa_node = xa_parent(xas->xa, xas->xa_node);
    1050         [ +  - ]:      18063 :                 if (!xas->xa_node)
    1051                 :          0 :                         return set_bounds(xas);
    1052                 :            :         }
    1053                 :            : 
    1054                 :            :         for (;;) {
    1055                 :      35921 :                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
    1056         [ +  + ]:      35921 :                 if (!xa_is_node(entry))
    1057                 :      18067 :                         return entry;
    1058                 :            : 
    1059                 :      17854 :                 xas->xa_node = xa_to_node(entry);
    1060                 :            :                 xas_set_offset(xas);
    1061                 :            :         }
    1062                 :            : }
    1063                 :            : EXPORT_SYMBOL_GPL(__xas_next);
    1064                 :            : 
    1065                 :            : /**
    1066                 :            :  * xas_find() - Find the next present entry in the XArray.
    1067                 :            :  * @xas: XArray operation state.
    1068                 :            :  * @max: Highest index to return.
    1069                 :            :  *
    1070                 :            :  * If the @xas has not yet been walked to an entry, return the entry
    1071                 :            :  * which has an index >= xas.xa_index.  If it has been walked, the entry
    1072                 :            :  * currently being pointed at has been processed, and so we move to the
    1073                 :            :  * next entry.
    1074                 :            :  *
    1075                 :            :  * If no entry is found and the array is smaller than @max, the iterator
    1076                 :            :  * is set to the smallest index not yet in the array.  This allows @xas
    1077                 :            :  * to be immediately passed to xas_store().
    1078                 :            :  *
    1079                 :            :  * Return: The entry, if found, otherwise %NULL.
    1080                 :            :  */
    1081                 :   85646933 : void *xas_find(struct xa_state *xas, unsigned long max)
    1082                 :            : {
    1083                 :            :         void *entry;
    1084                 :            : 
    1085   [ +  +  +  + ]:   85646933 :         if (xas_error(xas) || xas->xa_node == XAS_BOUNDS)
    1086                 :            :                 return NULL;
    1087         [ -  + ]:   85636965 :         if (xas->xa_index > max)
    1088                 :          0 :                 return set_bounds(xas);
    1089                 :            : 
    1090         [ +  + ]:   85636965 :         if (!xas->xa_node) {
    1091                 :    1172500 :                 xas->xa_index = 1;
    1092                 :    1172500 :                 return set_bounds(xas);
    1093         [ +  + ]:   84464465 :         } else if (xas->xa_node == XAS_RESTART) {
    1094                 :   41470177 :                 entry = xas_load(xas);
    1095   [ +  +  +  + ]:   41739463 :                 if (entry || xas_not_node(xas->xa_node))
    1096                 :            :                         return entry;
    1097   [ +  +  -  + ]:   85950945 :         } else if (!xas->xa_node->shift &&
    1098                 :   42956657 :                     xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) {
    1099                 :          0 :                 xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1;
    1100                 :            :         }
    1101                 :            : 
    1102                 :            :         xas_advance(xas);
    1103                 :            : 
    1104   [ +  +  +  + ]:   52711028 :         while (xas->xa_node && (xas->xa_index <= max)) {
    1105         [ +  + ]:   12609460 :                 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
    1106                 :    3022975 :                         xas->xa_offset = xas->xa_node->offset + 1;
    1107                 :    3022975 :                         xas->xa_node = xa_parent(xas->xa, xas->xa_node);
    1108                 :    3022975 :                         continue;
    1109                 :            :                 }
    1110                 :            : 
    1111                 :    9586485 :                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
    1112         [ +  + ]:    9586485 :                 if (xa_is_node(entry)) {
    1113                 :    3002515 :                         xas->xa_node = xa_to_node(entry);
    1114                 :    3002515 :                         xas->xa_offset = 0;
    1115                 :    3002515 :                         continue;
    1116                 :            :                 }
    1117         [ +  + ]:    6583970 :                 if (entry && !xa_is_sibling(entry))
    1118                 :    3067413 :                         return entry;
    1119                 :            : 
    1120                 :            :                 xas_advance(xas);
    1121                 :            :         }
    1122                 :            : 
    1123         [ +  + ]:   40101568 :         if (!xas->xa_node)
    1124                 :      29075 :                 xas->xa_node = XAS_BOUNDS;
    1125                 :            :         return NULL;
    1126                 :            : }
    1127                 :            : EXPORT_SYMBOL_GPL(xas_find);
    1128                 :            : 
    1129                 :            : /**
    1130                 :            :  * xas_find_marked() - Find the next marked entry in the XArray.
    1131                 :            :  * @xas: XArray operation state.
    1132                 :            :  * @max: Highest index to return.
    1133                 :            :  * @mark: Mark number to search for.
    1134                 :            :  *
    1135                 :            :  * If the @xas has not yet been walked to an entry, return the marked entry
    1136                 :            :  * which has an index >= xas.xa_index.  If it has been walked, the entry
    1137                 :            :  * currently being pointed at has been processed, and so we return the
    1138                 :            :  * first marked entry with an index > xas.xa_index.
    1139                 :            :  *
    1140                 :            :  * If no marked entry is found and the array is smaller than @max, @xas is
    1141                 :            :  * set to the bounds state and xas->xa_index is set to the smallest index
    1142                 :            :  * not yet in the array.  This allows @xas to be immediately passed to
    1143                 :            :  * xas_store().
    1144                 :            :  *
    1145                 :            :  * If no entry is found before @max is reached, @xas is set to the restart
    1146                 :            :  * state.
    1147                 :            :  *
    1148                 :            :  * Return: The entry, if found, otherwise %NULL.
    1149                 :            :  */
    1150                 :    1632015 : void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
    1151                 :            : {
    1152                 :            :         bool advance = true;
    1153                 :            :         unsigned int offset;
    1154                 :            :         void *entry;
    1155                 :            : 
    1156         [ +  - ]:    1632015 :         if (xas_error(xas))
    1157                 :            :                 return NULL;
    1158         [ +  - ]:    1632015 :         if (xas->xa_index > max)
    1159                 :            :                 goto max;
    1160                 :            : 
    1161         [ +  + ]:    1632015 :         if (!xas->xa_node) {
    1162                 :     267540 :                 xas->xa_index = 1;
    1163                 :     267540 :                 goto out;
    1164         [ +  + ]:    1364475 :         } else if (xas_top(xas->xa_node)) {
    1165                 :            :                 advance = false;
    1166                 :    1201760 :                 entry = xa_head(xas->xa);
    1167                 :    1201760 :                 xas->xa_node = NULL;
    1168         [ +  + ]:    1201760 :                 if (xas->xa_index > max_index(entry))
    1169                 :            :                         goto out;
    1170         [ +  + ]:    1064229 :                 if (!xa_is_node(entry)) {
    1171         [ +  + ]:     726441 :                         if (xa_marked(xas->xa, mark))
    1172                 :            :                                 return entry;
    1173                 :     107330 :                         xas->xa_index = 1;
    1174                 :     107330 :                         goto out;
    1175                 :            :                 }
    1176                 :     337788 :                 xas->xa_node = xa_to_node(entry);
    1177                 :     337788 :                 xas->xa_offset = xas->xa_index >> xas->xa_node->shift;
    1178                 :            :         }
    1179                 :            : 
    1180         [ +  - ]:     788910 :         while (xas->xa_index <= max) {
    1181         [ +  + ]:     788910 :                 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
    1182                 :     266943 :                         xas->xa_offset = xas->xa_node->offset + 1;
    1183                 :     266943 :                         xas->xa_node = xa_parent(xas->xa, xas->xa_node);
    1184         [ +  + ]:     266943 :                         if (!xas->xa_node)
    1185                 :            :                                 break;
    1186                 :            :                         advance = false;
    1187                 :      78310 :                         continue;
    1188                 :            :                 }
    1189                 :            : 
    1190         [ +  - ]:     521967 :                 if (!advance) {
    1191                 :     521967 :                         entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
    1192                 :            :                         if (xa_is_sibling(entry)) {
    1193                 :            :                                 xas->xa_offset = xa_to_sibling(entry);
    1194                 :            :                                 xas_move_index(xas, xas->xa_offset);
    1195                 :            :                         }
    1196                 :            :                 }
    1197                 :            : 
    1198                 :            :                 offset = xas_find_chunk(xas, advance, mark);
    1199         [ +  + ]:     521967 :                 if (offset > xas->xa_offset) {
    1200                 :            :                         advance = false;
    1201                 :            :                         xas_move_index(xas, offset);
    1202                 :            :                         /* Mind the wrap */
    1203         [ +  + ]:     329177 :                         if ((xas->xa_index - 1) >= max)
    1204                 :            :                                 goto max;
    1205                 :     280796 :                         xas->xa_offset = offset;
    1206         [ +  + ]:     280796 :                         if (offset == XA_CHUNK_SIZE)
    1207                 :     104228 :                                 continue;
    1208                 :            :                 }
    1209                 :            : 
    1210                 :     369358 :                 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
    1211   [ -  +  #  #  :     369358 :                 if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))
                   #  # ]
    1212                 :          0 :                         continue;
    1213         [ +  + ]:     369358 :                 if (!xa_is_node(entry))
    1214                 :     263489 :                         return entry;
    1215                 :     105869 :                 xas->xa_node = xa_to_node(entry);
    1216                 :            :                 xas_set_offset(xas);
    1217                 :            :         }
    1218                 :            : 
    1219                 :            : out:
    1220         [ +  + ]:     701034 :         if (xas->xa_index > max)
    1221                 :            :                 goto max;
    1222                 :     597562 :         return set_bounds(xas);
    1223                 :            : max:
    1224                 :     151853 :         xas->xa_node = XAS_RESTART;
    1225                 :     151853 :         return NULL;
    1226                 :            : }
    1227                 :            : EXPORT_SYMBOL_GPL(xas_find_marked);
    1228                 :            : 
    1229                 :            : /**
    1230                 :            :  * xas_find_conflict() - Find the next present entry in a range.
    1231                 :            :  * @xas: XArray operation state.
    1232                 :            :  *
    1233                 :            :  * The @xas describes both a range and a position within that range.
    1234                 :            :  *
    1235                 :            :  * Context: Any context.  Expects xa_lock to be held.
    1236                 :            :  * Return: The next entry in the range covered by @xas or %NULL.
    1237                 :            :  */
    1238                 :    1249968 : void *xas_find_conflict(struct xa_state *xas)
    1239                 :            : {
    1240                 :            :         void *curr;
    1241                 :            : 
    1242         [ +  + ]:    1249968 :         if (xas_error(xas))
    1243                 :            :                 return NULL;
    1244                 :            : 
    1245         [ +  - ]:    1249771 :         if (!xas->xa_node)
    1246                 :            :                 return NULL;
    1247                 :            : 
    1248         [ +  + ]:    1249948 :         if (xas_top(xas->xa_node)) {
    1249                 :    1249957 :                 curr = xas_start(xas);
    1250         [ +  + ]:    1249946 :                 if (!curr)
    1251                 :            :                         return NULL;
    1252         [ +  + ]:    4418572 :                 while (xa_is_node(curr)) {
    1253                 :            :                         struct xa_node *node = xa_to_node(curr);
    1254                 :            :                         curr = xas_descend(xas, node);
    1255                 :            :                 }
    1256         [ -  + ]:    1206810 :                 if (curr)
    1257                 :          0 :                         return curr;
    1258                 :            :         }
    1259                 :            : 
    1260         [ +  + ]:    1206801 :         if (xas->xa_node->shift > xas->xa_shift)
    1261                 :            :                 return NULL;
    1262                 :            : 
    1263                 :            :         for (;;) {
    1264         [ +  - ]:    1188726 :                 if (xas->xa_node->shift == xas->xa_shift) {
    1265         [ -  + ]:    1188726 :                         if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs)
    1266                 :            :                                 break;
    1267         [ #  # ]:          0 :                 } else if (xas->xa_offset == XA_CHUNK_MASK) {
    1268                 :          0 :                         xas->xa_offset = xas->xa_node->offset;
    1269                 :          0 :                         xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node);
    1270         [ #  # ]:          0 :                         if (!xas->xa_node)
    1271                 :            :                                 break;
    1272                 :          0 :                         continue;
    1273                 :            :                 }
    1274                 :          0 :                 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset);
    1275                 :            :                 if (xa_is_sibling(curr))
    1276                 :            :                         continue;
    1277         [ #  # ]:          0 :                 while (xa_is_node(curr)) {
    1278                 :          0 :                         xas->xa_node = xa_to_node(curr);
    1279                 :          0 :                         xas->xa_offset = 0;
    1280                 :            :                         curr = xa_entry_locked(xas->xa, xas->xa_node, 0);
    1281                 :            :                 }
    1282         [ #  # ]:          0 :                 if (curr)
    1283                 :          0 :                         return curr;
    1284                 :            :         }
    1285                 :    1188726 :         xas->xa_offset -= xas->xa_sibs;
    1286                 :    1188726 :         return NULL;
    1287                 :            : }
    1288                 :            : EXPORT_SYMBOL_GPL(xas_find_conflict);
    1289                 :            : 
    1290                 :            : /**
    1291                 :            :  * xa_load() - Load an entry from an XArray.
    1292                 :            :  * @xa: XArray.
    1293                 :            :  * @index: index into array.
    1294                 :            :  *
    1295                 :            :  * Context: Any context.  Takes and releases the RCU lock.
    1296                 :            :  * Return: The entry at @index in @xa.
    1297                 :            :  */
    1298                 :    9278489 : void *xa_load(struct xarray *xa, unsigned long index)
    1299                 :            : {
    1300                 :    9278489 :         XA_STATE(xas, xa, index);
    1301                 :            :         void *entry;
    1302                 :            : 
    1303                 :            :         rcu_read_lock();
    1304                 :            :         do {
    1305                 :    9278618 :                 entry = xas_load(&xas);
    1306         [ -  + ]:    9280248 :                 if (xa_is_zero(entry))
    1307                 :            :                         entry = NULL;
    1308         [ +  + ]:    9280248 :         } while (xas_retry(&xas, entry));
    1309                 :            :         rcu_read_unlock();
    1310                 :            : 
    1311                 :    9279854 :         return entry;
    1312                 :            : }
    1313                 :            : EXPORT_SYMBOL(xa_load);
    1314                 :            : 
    1315                 :            : static void *xas_result(struct xa_state *xas, void *curr)
    1316                 :            : {
    1317   [ #  #  #  #  :          0 :         if (xa_is_zero(curr))
                   #  # ]
    1318                 :            :                 return NULL;
    1319   [ #  #  #  #  :          0 :         if (xas_error(xas))
                   #  # ]
    1320                 :            :                 curr = xas->xa_node;
    1321                 :            :         return curr;
    1322                 :            : }
    1323                 :            : 
    1324                 :            : /**
    1325                 :            :  * __xa_erase() - Erase this entry from the XArray while locked.
    1326                 :            :  * @xa: XArray.
    1327                 :            :  * @index: Index into array.
    1328                 :            :  *
    1329                 :            :  * After this function returns, loading from @index will return %NULL.
    1330                 :            :  * If the index is part of a multi-index entry, all indices will be erased
    1331                 :            :  * and none of the entries will be part of a multi-index entry.
    1332                 :            :  *
    1333                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.
    1334                 :            :  * Return: The entry which used to be at this index.
    1335                 :            :  */
    1336                 :          0 : void *__xa_erase(struct xarray *xa, unsigned long index)
    1337                 :            : {
    1338                 :          0 :         XA_STATE(xas, xa, index);
    1339                 :          0 :         return xas_result(&xas, xas_store(&xas, NULL));
    1340                 :            : }
    1341                 :            : EXPORT_SYMBOL(__xa_erase);
    1342                 :            : 
    1343                 :            : /**
    1344                 :            :  * xa_erase() - Erase this entry from the XArray.
    1345                 :            :  * @xa: XArray.
    1346                 :            :  * @index: Index of entry.
    1347                 :            :  *
    1348                 :            :  * After this function returns, loading from @index will return %NULL.
    1349                 :            :  * If the index is part of a multi-index entry, all indices will be erased
    1350                 :            :  * and none of the entries will be part of a multi-index entry.
    1351                 :            :  *
    1352                 :            :  * Context: Any context.  Takes and releases the xa_lock.
    1353                 :            :  * Return: The entry which used to be at this index.
    1354                 :            :  */
    1355                 :          0 : void *xa_erase(struct xarray *xa, unsigned long index)
    1356                 :            : {
    1357                 :            :         void *entry;
    1358                 :            : 
    1359                 :            :         xa_lock(xa);
    1360                 :          0 :         entry = __xa_erase(xa, index);
    1361                 :            :         xa_unlock(xa);
    1362                 :            : 
    1363                 :          0 :         return entry;
    1364                 :            : }
    1365                 :            : EXPORT_SYMBOL(xa_erase);
    1366                 :            : 
    1367                 :            : /**
    1368                 :            :  * __xa_store() - Store this entry in the XArray.
    1369                 :            :  * @xa: XArray.
    1370                 :            :  * @index: Index into array.
    1371                 :            :  * @entry: New entry.
    1372                 :            :  * @gfp: Memory allocation flags.
    1373                 :            :  *
    1374                 :            :  * You must already be holding the xa_lock when calling this function.
    1375                 :            :  * It will drop the lock if needed to allocate memory, and then reacquire
    1376                 :            :  * it afterwards.
    1377                 :            :  *
    1378                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.  May
    1379                 :            :  * release and reacquire xa_lock if @gfp flags permit.
    1380                 :            :  * Return: The old entry at this index or xa_err() if an error happened.
    1381                 :            :  */
    1382                 :          0 : void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
    1383                 :            : {
    1384                 :          0 :         XA_STATE(xas, xa, index);
    1385                 :            :         void *curr;
    1386                 :            : 
    1387   [ #  #  #  #  :          0 :         if (WARN_ON_ONCE(xa_is_advanced(entry)))
                   #  # ]
    1388                 :            :                 return XA_ERROR(-EINVAL);
    1389   [ #  #  #  # ]:          0 :         if (xa_track_free(xa) && !entry)
    1390                 :            :                 entry = XA_ZERO_ENTRY;
    1391                 :            : 
    1392                 :            :         do {
    1393                 :          0 :                 curr = xas_store(&xas, entry);
    1394         [ #  # ]:          0 :                 if (xa_track_free(xa))
    1395                 :          0 :                         xas_clear_mark(&xas, XA_FREE_MARK);
    1396         [ #  # ]:          0 :         } while (__xas_nomem(&xas, gfp));
    1397                 :            : 
    1398                 :          0 :         return xas_result(&xas, curr);
    1399                 :            : }
    1400                 :            : EXPORT_SYMBOL(__xa_store);
    1401                 :            : 
    1402                 :            : /**
    1403                 :            :  * xa_store() - Store this entry in the XArray.
    1404                 :            :  * @xa: XArray.
    1405                 :            :  * @index: Index into array.
    1406                 :            :  * @entry: New entry.
    1407                 :            :  * @gfp: Memory allocation flags.
    1408                 :            :  *
    1409                 :            :  * After this function returns, loads from this index will return @entry.
    1410                 :            :  * Storing into an existing multislot entry updates the entry of every index.
    1411                 :            :  * The marks associated with @index are unaffected unless @entry is %NULL.
    1412                 :            :  *
    1413                 :            :  * Context: Any context.  Takes and releases the xa_lock.
    1414                 :            :  * May sleep if the @gfp flags permit.
    1415                 :            :  * Return: The old entry at this index on success, xa_err(-EINVAL) if @entry
    1416                 :            :  * cannot be stored in an XArray, or xa_err(-ENOMEM) if memory allocation
    1417                 :            :  * failed.
    1418                 :            :  */
    1419                 :          0 : void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
    1420                 :            : {
    1421                 :            :         void *curr;
    1422                 :            : 
    1423                 :            :         xa_lock(xa);
    1424                 :          0 :         curr = __xa_store(xa, index, entry, gfp);
    1425                 :            :         xa_unlock(xa);
    1426                 :            : 
    1427                 :          0 :         return curr;
    1428                 :            : }
    1429                 :            : EXPORT_SYMBOL(xa_store);
    1430                 :            : 
    1431                 :            : /**
    1432                 :            :  * __xa_cmpxchg() - Store this entry in the XArray.
    1433                 :            :  * @xa: XArray.
    1434                 :            :  * @index: Index into array.
    1435                 :            :  * @old: Old value to test against.
    1436                 :            :  * @entry: New entry.
    1437                 :            :  * @gfp: Memory allocation flags.
    1438                 :            :  *
    1439                 :            :  * You must already be holding the xa_lock when calling this function.
    1440                 :            :  * It will drop the lock if needed to allocate memory, and then reacquire
    1441                 :            :  * it afterwards.
    1442                 :            :  *
    1443                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.  May
    1444                 :            :  * release and reacquire xa_lock if @gfp flags permit.
    1445                 :            :  * Return: The old entry at this index or xa_err() if an error happened.
    1446                 :            :  */
    1447                 :          0 : void *__xa_cmpxchg(struct xarray *xa, unsigned long index,
    1448                 :            :                         void *old, void *entry, gfp_t gfp)
    1449                 :            : {
    1450                 :          0 :         XA_STATE(xas, xa, index);
    1451                 :            :         void *curr;
    1452                 :            : 
    1453   [ #  #  #  #  :          0 :         if (WARN_ON_ONCE(xa_is_advanced(entry)))
                   #  # ]
    1454                 :            :                 return XA_ERROR(-EINVAL);
    1455                 :            : 
    1456                 :            :         do {
    1457                 :          0 :                 curr = xas_load(&xas);
    1458         [ #  # ]:          0 :                 if (curr == old) {
    1459                 :          0 :                         xas_store(&xas, entry);
    1460   [ #  #  #  # ]:          0 :                         if (xa_track_free(xa) && entry && !curr)
    1461                 :          0 :                                 xas_clear_mark(&xas, XA_FREE_MARK);
    1462                 :            :                 }
    1463         [ #  # ]:          0 :         } while (__xas_nomem(&xas, gfp));
    1464                 :            : 
    1465                 :          0 :         return xas_result(&xas, curr);
    1466                 :            : }
    1467                 :            : EXPORT_SYMBOL(__xa_cmpxchg);
    1468                 :            : 
    1469                 :            : /**
    1470                 :            :  * __xa_insert() - Store this entry in the XArray if no entry is present.
    1471                 :            :  * @xa: XArray.
    1472                 :            :  * @index: Index into array.
    1473                 :            :  * @entry: New entry.
    1474                 :            :  * @gfp: Memory allocation flags.
    1475                 :            :  *
    1476                 :            :  * Inserting a NULL entry will store a reserved entry (like xa_reserve())
    1477                 :            :  * if no entry is present.  Inserting will fail if a reserved entry is
    1478                 :            :  * present, even though loading from this index will return NULL.
    1479                 :            :  *
    1480                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.  May
    1481                 :            :  * release and reacquire xa_lock if @gfp flags permit.
    1482                 :            :  * Return: 0 if the store succeeded.  -EBUSY if another entry was present.
    1483                 :            :  * -ENOMEM if memory could not be allocated.
    1484                 :            :  */
    1485                 :          0 : int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
    1486                 :            : {
    1487                 :          0 :         XA_STATE(xas, xa, index);
    1488                 :            :         void *curr;
    1489                 :            : 
    1490   [ #  #  #  #  :          0 :         if (WARN_ON_ONCE(xa_is_advanced(entry)))
                   #  # ]
    1491                 :            :                 return -EINVAL;
    1492         [ #  # ]:          0 :         if (!entry)
    1493                 :            :                 entry = XA_ZERO_ENTRY;
    1494                 :            : 
    1495                 :            :         do {
    1496                 :          0 :                 curr = xas_load(&xas);
    1497         [ #  # ]:          0 :                 if (!curr) {
    1498                 :          0 :                         xas_store(&xas, entry);
    1499         [ #  # ]:          0 :                         if (xa_track_free(xa))
    1500                 :          0 :                                 xas_clear_mark(&xas, XA_FREE_MARK);
    1501                 :            :                 } else {
    1502                 :            :                         xas_set_err(&xas, -EBUSY);
    1503                 :            :                 }
    1504         [ #  # ]:          0 :         } while (__xas_nomem(&xas, gfp));
    1505                 :            : 
    1506                 :          0 :         return xas_error(&xas);
    1507                 :            : }
    1508                 :            : EXPORT_SYMBOL(__xa_insert);
    1509                 :            : 
    1510                 :            : #ifdef CONFIG_XARRAY_MULTI
    1511                 :            : static void xas_set_range(struct xa_state *xas, unsigned long first,
    1512                 :            :                 unsigned long last)
    1513                 :            : {
    1514                 :            :         unsigned int shift = 0;
    1515                 :            :         unsigned long sibs = last - first;
    1516                 :            :         unsigned int offset = XA_CHUNK_MASK;
    1517                 :            : 
    1518                 :            :         xas_set(xas, first);
    1519                 :            : 
    1520                 :            :         while ((first & XA_CHUNK_MASK) == 0) {
    1521                 :            :                 if (sibs < XA_CHUNK_MASK)
    1522                 :            :                         break;
    1523                 :            :                 if ((sibs == XA_CHUNK_MASK) && (offset < XA_CHUNK_MASK))
    1524                 :            :                         break;
    1525                 :            :                 shift += XA_CHUNK_SHIFT;
    1526                 :            :                 if (offset == XA_CHUNK_MASK)
    1527                 :            :                         offset = sibs & XA_CHUNK_MASK;
    1528                 :            :                 sibs >>= XA_CHUNK_SHIFT;
    1529                 :            :                 first >>= XA_CHUNK_SHIFT;
    1530                 :            :         }
    1531                 :            : 
    1532                 :            :         offset = first & XA_CHUNK_MASK;
    1533                 :            :         if (offset + sibs > XA_CHUNK_MASK)
    1534                 :            :                 sibs = XA_CHUNK_MASK - offset;
    1535                 :            :         if ((((first + sibs + 1) << shift) - 1) > last)
    1536                 :            :                 sibs -= 1;
    1537                 :            : 
    1538                 :            :         xas->xa_shift = shift;
    1539                 :            :         xas->xa_sibs = sibs;
    1540                 :            : }
    1541                 :            : 
    1542                 :            : /**
    1543                 :            :  * xa_store_range() - Store this entry at a range of indices in the XArray.
    1544                 :            :  * @xa: XArray.
    1545                 :            :  * @first: First index to affect.
    1546                 :            :  * @last: Last index to affect.
    1547                 :            :  * @entry: New entry.
    1548                 :            :  * @gfp: Memory allocation flags.
    1549                 :            :  *
    1550                 :            :  * After this function returns, loads from any index between @first and @last,
    1551                 :            :  * inclusive will return @entry.
    1552                 :            :  * Storing into an existing multislot entry updates the entry of every index.
    1553                 :            :  * The marks associated with @index are unaffected unless @entry is %NULL.
    1554                 :            :  *
    1555                 :            :  * Context: Process context.  Takes and releases the xa_lock.  May sleep
    1556                 :            :  * if the @gfp flags permit.
    1557                 :            :  * Return: %NULL on success, xa_err(-EINVAL) if @entry cannot be stored in
    1558                 :            :  * an XArray, or xa_err(-ENOMEM) if memory allocation failed.
    1559                 :            :  */
    1560                 :            : void *xa_store_range(struct xarray *xa, unsigned long first,
    1561                 :            :                 unsigned long last, void *entry, gfp_t gfp)
    1562                 :            : {
    1563                 :            :         XA_STATE(xas, xa, 0);
    1564                 :            : 
    1565                 :            :         if (WARN_ON_ONCE(xa_is_internal(entry)))
    1566                 :            :                 return XA_ERROR(-EINVAL);
    1567                 :            :         if (last < first)
    1568                 :            :                 return XA_ERROR(-EINVAL);
    1569                 :            : 
    1570                 :            :         do {
    1571                 :            :                 xas_lock(&xas);
    1572                 :            :                 if (entry) {
    1573                 :            :                         unsigned int order = BITS_PER_LONG;
    1574                 :            :                         if (last + 1)
    1575                 :            :                                 order = __ffs(last + 1);
    1576                 :            :                         xas_set_order(&xas, last, order);
    1577                 :            :                         xas_create(&xas, true);
    1578                 :            :                         if (xas_error(&xas))
    1579                 :            :                                 goto unlock;
    1580                 :            :                 }
    1581                 :            :                 do {
    1582                 :            :                         xas_set_range(&xas, first, last);
    1583                 :            :                         xas_store(&xas, entry);
    1584                 :            :                         if (xas_error(&xas))
    1585                 :            :                                 goto unlock;
    1586                 :            :                         first += xas_size(&xas);
    1587                 :            :                 } while (first <= last);
    1588                 :            : unlock:
    1589                 :            :                 xas_unlock(&xas);
    1590                 :            :         } while (xas_nomem(&xas, gfp));
    1591                 :            : 
    1592                 :            :         return xas_result(&xas, NULL);
    1593                 :            : }
    1594                 :            : EXPORT_SYMBOL(xa_store_range);
    1595                 :            : #endif /* CONFIG_XARRAY_MULTI */
    1596                 :            : 
    1597                 :            : /**
    1598                 :            :  * __xa_alloc() - Find somewhere to store this entry in the XArray.
    1599                 :            :  * @xa: XArray.
    1600                 :            :  * @id: Pointer to ID.
    1601                 :            :  * @limit: Range for allocated ID.
    1602                 :            :  * @entry: New entry.
    1603                 :            :  * @gfp: Memory allocation flags.
    1604                 :            :  *
    1605                 :            :  * Finds an empty entry in @xa between @limit.min and @limit.max,
    1606                 :            :  * stores the index into the @id pointer, then stores the entry at
    1607                 :            :  * that index.  A concurrent lookup will not see an uninitialised @id.
    1608                 :            :  *
    1609                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.  May
    1610                 :            :  * release and reacquire xa_lock if @gfp flags permit.
    1611                 :            :  * Return: 0 on success, -ENOMEM if memory could not be allocated or
    1612                 :            :  * -EBUSY if there are no free entries in @limit.
    1613                 :            :  */
    1614                 :        414 : int __xa_alloc(struct xarray *xa, u32 *id, void *entry,
    1615                 :            :                 struct xa_limit limit, gfp_t gfp)
    1616                 :            : {
    1617                 :        414 :         XA_STATE(xas, xa, 0);
    1618                 :            : 
    1619   [ -  +  #  #  :        414 :         if (WARN_ON_ONCE(xa_is_advanced(entry)))
                   +  - ]
    1620                 :            :                 return -EINVAL;
    1621   [ -  +  #  #  :        414 :         if (WARN_ON_ONCE(!xa_track_free(xa)))
                   +  - ]
    1622                 :            :                 return -EINVAL;
    1623                 :            : 
    1624         [ -  + ]:        414 :         if (!entry)
    1625                 :            :                 entry = XA_ZERO_ENTRY;
    1626                 :            : 
    1627                 :            :         do {
    1628                 :        414 :                 xas.xa_index = limit.min;
    1629                 :        414 :                 xas_find_marked(&xas, limit.max, XA_FREE_MARK);
    1630         [ -  + ]:        414 :                 if (xas.xa_node == XAS_RESTART)
    1631                 :            :                         xas_set_err(&xas, -EBUSY);
    1632                 :            :                 else
    1633                 :        414 :                         *id = xas.xa_index;
    1634                 :        414 :                 xas_store(&xas, entry);
    1635                 :        414 :                 xas_clear_mark(&xas, XA_FREE_MARK);
    1636         [ -  + ]:        414 :         } while (__xas_nomem(&xas, gfp));
    1637                 :            : 
    1638                 :        414 :         return xas_error(&xas);
    1639                 :            : }
    1640                 :            : EXPORT_SYMBOL(__xa_alloc);
    1641                 :            : 
    1642                 :            : /**
    1643                 :            :  * __xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
    1644                 :            :  * @xa: XArray.
    1645                 :            :  * @id: Pointer to ID.
    1646                 :            :  * @entry: New entry.
    1647                 :            :  * @limit: Range of allocated ID.
    1648                 :            :  * @next: Pointer to next ID to allocate.
    1649                 :            :  * @gfp: Memory allocation flags.
    1650                 :            :  *
    1651                 :            :  * Finds an empty entry in @xa between @limit.min and @limit.max,
    1652                 :            :  * stores the index into the @id pointer, then stores the entry at
    1653                 :            :  * that index.  A concurrent lookup will not see an uninitialised @id.
    1654                 :            :  * The search for an empty entry will start at @next and will wrap
    1655                 :            :  * around if necessary.
    1656                 :            :  *
    1657                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.  May
    1658                 :            :  * release and reacquire xa_lock if @gfp flags permit.
    1659                 :            :  * Return: 0 if the allocation succeeded without wrapping.  1 if the
    1660                 :            :  * allocation succeeded after wrapping, -ENOMEM if memory could not be
    1661                 :            :  * allocated or -EBUSY if there are no free entries in @limit.
    1662                 :            :  */
    1663                 :          0 : int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,
    1664                 :            :                 struct xa_limit limit, u32 *next, gfp_t gfp)
    1665                 :            : {
    1666                 :            :         u32 min = limit.min;
    1667                 :            :         int ret;
    1668                 :            : 
    1669                 :          0 :         limit.min = max(min, *next);
    1670                 :          0 :         ret = __xa_alloc(xa, id, entry, limit, gfp);
    1671   [ #  #  #  # ]:          0 :         if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {
    1672                 :          0 :                 xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;
    1673                 :            :                 ret = 1;
    1674                 :            :         }
    1675                 :            : 
    1676   [ #  #  #  # ]:          0 :         if (ret < 0 && limit.min > min) {
    1677                 :            :                 limit.min = min;
    1678                 :          0 :                 ret = __xa_alloc(xa, id, entry, limit, gfp);
    1679         [ #  # ]:          0 :                 if (ret == 0)
    1680                 :            :                         ret = 1;
    1681                 :            :         }
    1682                 :            : 
    1683         [ #  # ]:          0 :         if (ret >= 0) {
    1684                 :          0 :                 *next = *id + 1;
    1685         [ #  # ]:          0 :                 if (*next == 0)
    1686                 :          0 :                         xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;
    1687                 :            :         }
    1688                 :          0 :         return ret;
    1689                 :            : }
    1690                 :            : EXPORT_SYMBOL(__xa_alloc_cyclic);
    1691                 :            : 
    1692                 :            : /**
    1693                 :            :  * __xa_set_mark() - Set this mark on this entry while locked.
    1694                 :            :  * @xa: XArray.
    1695                 :            :  * @index: Index of entry.
    1696                 :            :  * @mark: Mark number.
    1697                 :            :  *
    1698                 :            :  * Attempting to set a mark on a %NULL entry does not succeed.
    1699                 :            :  *
    1700                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.
    1701                 :            :  */
    1702                 :     739475 : void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
    1703                 :            : {
    1704                 :     739475 :         XA_STATE(xas, xa, index);
    1705                 :     739475 :         void *entry = xas_load(&xas);
    1706                 :            : 
    1707         [ +  - ]:     739475 :         if (entry)
    1708                 :     739476 :                 xas_set_mark(&xas, mark);
    1709                 :     739475 : }
    1710                 :            : EXPORT_SYMBOL(__xa_set_mark);
    1711                 :            : 
    1712                 :            : /**
    1713                 :            :  * __xa_clear_mark() - Clear this mark on this entry while locked.
    1714                 :            :  * @xa: XArray.
    1715                 :            :  * @index: Index of entry.
    1716                 :            :  * @mark: Mark number.
    1717                 :            :  *
    1718                 :            :  * Context: Any context.  Expects xa_lock to be held on entry.
    1719                 :            :  */
    1720                 :     446343 : void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
    1721                 :            : {
    1722                 :     446343 :         XA_STATE(xas, xa, index);
    1723                 :     446343 :         void *entry = xas_load(&xas);
    1724                 :            : 
    1725         [ +  - ]:     446343 :         if (entry)
    1726                 :     446343 :                 xas_clear_mark(&xas, mark);
    1727                 :     446343 : }
    1728                 :            : EXPORT_SYMBOL(__xa_clear_mark);
    1729                 :            : 
    1730                 :            : /**
    1731                 :            :  * xa_get_mark() - Inquire whether this mark is set on this entry.
    1732                 :            :  * @xa: XArray.
    1733                 :            :  * @index: Index of entry.
    1734                 :            :  * @mark: Mark number.
    1735                 :            :  *
    1736                 :            :  * This function uses the RCU read lock, so the result may be out of date
    1737                 :            :  * by the time it returns.  If you need the result to be stable, use a lock.
    1738                 :            :  *
    1739                 :            :  * Context: Any context.  Takes and releases the RCU lock.
    1740                 :            :  * Return: True if the entry at @index has this mark set, false if it doesn't.
    1741                 :            :  */
    1742                 :          0 : bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
    1743                 :            : {
    1744                 :          0 :         XA_STATE(xas, xa, index);
    1745                 :            :         void *entry;
    1746                 :            : 
    1747                 :            :         rcu_read_lock();
    1748                 :          0 :         entry = xas_start(&xas);
    1749         [ #  # ]:          0 :         while (xas_get_mark(&xas, mark)) {
    1750         [ #  # ]:          0 :                 if (!xa_is_node(entry))
    1751                 :            :                         goto found;
    1752                 :            :                 entry = xas_descend(&xas, xa_to_node(entry));
    1753                 :            :         }
    1754                 :            :         rcu_read_unlock();
    1755                 :          0 :         return false;
    1756                 :            :  found:
    1757                 :            :         rcu_read_unlock();
    1758                 :          0 :         return true;
    1759                 :            : }
    1760                 :            : EXPORT_SYMBOL(xa_get_mark);
    1761                 :            : 
    1762                 :            : /**
    1763                 :            :  * xa_set_mark() - Set this mark on this entry.
    1764                 :            :  * @xa: XArray.
    1765                 :            :  * @index: Index of entry.
    1766                 :            :  * @mark: Mark number.
    1767                 :            :  *
    1768                 :            :  * Attempting to set a mark on a %NULL entry does not succeed.
    1769                 :            :  *
    1770                 :            :  * Context: Process context.  Takes and releases the xa_lock.
    1771                 :            :  */
    1772                 :          0 : void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
    1773                 :            : {
    1774                 :            :         xa_lock(xa);
    1775                 :          0 :         __xa_set_mark(xa, index, mark);
    1776                 :            :         xa_unlock(xa);
    1777                 :          0 : }
    1778                 :            : EXPORT_SYMBOL(xa_set_mark);
    1779                 :            : 
    1780                 :            : /**
    1781                 :            :  * xa_clear_mark() - Clear this mark on this entry.
    1782                 :            :  * @xa: XArray.
    1783                 :            :  * @index: Index of entry.
    1784                 :            :  * @mark: Mark number.
    1785                 :            :  *
    1786                 :            :  * Clearing a mark always succeeds.
    1787                 :            :  *
    1788                 :            :  * Context: Process context.  Takes and releases the xa_lock.
    1789                 :            :  */
    1790                 :          0 : void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
    1791                 :            : {
    1792                 :            :         xa_lock(xa);
    1793                 :          0 :         __xa_clear_mark(xa, index, mark);
    1794                 :            :         xa_unlock(xa);
    1795                 :          0 : }
    1796                 :            : EXPORT_SYMBOL(xa_clear_mark);
    1797                 :            : 
    1798                 :            : /**
    1799                 :            :  * xa_find() - Search the XArray for an entry.
    1800                 :            :  * @xa: XArray.
    1801                 :            :  * @indexp: Pointer to an index.
    1802                 :            :  * @max: Maximum index to search to.
    1803                 :            :  * @filter: Selection criterion.
    1804                 :            :  *
    1805                 :            :  * Finds the entry in @xa which matches the @filter, and has the lowest
    1806                 :            :  * index that is at least @indexp and no more than @max.
    1807                 :            :  * If an entry is found, @indexp is updated to be the index of the entry.
    1808                 :            :  * This function is protected by the RCU read lock, so it may not find
    1809                 :            :  * entries which are being simultaneously added.  It will not return an
    1810                 :            :  * %XA_RETRY_ENTRY; if you need to see retry entries, use xas_find().
    1811                 :            :  *
    1812                 :            :  * Context: Any context.  Takes and releases the RCU lock.
    1813                 :            :  * Return: The entry, if found, otherwise %NULL.
    1814                 :            :  */
    1815                 :          0 : void *xa_find(struct xarray *xa, unsigned long *indexp,
    1816                 :            :                         unsigned long max, xa_mark_t filter)
    1817                 :            : {
    1818                 :          0 :         XA_STATE(xas, xa, *indexp);
    1819                 :            :         void *entry;
    1820                 :            : 
    1821                 :            :         rcu_read_lock();
    1822                 :            :         do {
    1823         [ #  # ]:          0 :                 if ((__force unsigned int)filter < XA_MAX_MARKS)
    1824                 :          0 :                         entry = xas_find_marked(&xas, max, filter);
    1825                 :            :                 else
    1826                 :          0 :                         entry = xas_find(&xas, max);
    1827         [ #  # ]:          0 :         } while (xas_retry(&xas, entry));
    1828                 :            :         rcu_read_unlock();
    1829                 :            : 
    1830         [ #  # ]:          0 :         if (entry)
    1831                 :          0 :                 *indexp = xas.xa_index;
    1832                 :          0 :         return entry;
    1833                 :            : }
    1834                 :            : EXPORT_SYMBOL(xa_find);
    1835                 :            : 
    1836                 :            : static bool xas_sibling(struct xa_state *xas)
    1837                 :            : {
    1838                 :            :         struct xa_node *node = xas->xa_node;
    1839                 :            :         unsigned long mask;
    1840                 :            : 
    1841         [ #  # ]:          0 :         if (!node)
    1842                 :            :                 return false;
    1843                 :          0 :         mask = (XA_CHUNK_SIZE << node->shift) - 1;
    1844                 :          0 :         return (xas->xa_index & mask) >
    1845                 :          0 :                 ((unsigned long)xas->xa_offset << node->shift);
    1846                 :            : }
    1847                 :            : 
    1848                 :            : /**
    1849                 :            :  * xa_find_after() - Search the XArray for a present entry.
    1850                 :            :  * @xa: XArray.
    1851                 :            :  * @indexp: Pointer to an index.
    1852                 :            :  * @max: Maximum index to search to.
    1853                 :            :  * @filter: Selection criterion.
    1854                 :            :  *
    1855                 :            :  * Finds the entry in @xa which matches the @filter and has the lowest
    1856                 :            :  * index that is above @indexp and no more than @max.
    1857                 :            :  * If an entry is found, @indexp is updated to be the index of the entry.
    1858                 :            :  * This function is protected by the RCU read lock, so it may miss entries
    1859                 :            :  * which are being simultaneously added.  It will not return an
    1860                 :            :  * %XA_RETRY_ENTRY; if you need to see retry entries, use xas_find().
    1861                 :            :  *
    1862                 :            :  * Context: Any context.  Takes and releases the RCU lock.
    1863                 :            :  * Return: The pointer, if found, otherwise %NULL.
    1864                 :            :  */
    1865                 :          0 : void *xa_find_after(struct xarray *xa, unsigned long *indexp,
    1866                 :            :                         unsigned long max, xa_mark_t filter)
    1867                 :            : {
    1868                 :          0 :         XA_STATE(xas, xa, *indexp + 1);
    1869                 :            :         void *entry;
    1870                 :            : 
    1871         [ #  # ]:          0 :         if (xas.xa_index == 0)
    1872                 :            :                 return NULL;
    1873                 :            : 
    1874                 :            :         rcu_read_lock();
    1875                 :            :         for (;;) {
    1876         [ #  # ]:          0 :                 if ((__force unsigned int)filter < XA_MAX_MARKS)
    1877                 :          0 :                         entry = xas_find_marked(&xas, max, filter);
    1878                 :            :                 else
    1879                 :          0 :                         entry = xas_find(&xas, max);
    1880                 :            : 
    1881         [ #  # ]:          0 :                 if (xas_invalid(&xas))
    1882                 :            :                         break;
    1883         [ #  # ]:          0 :                 if (xas_sibling(&xas))
    1884                 :          0 :                         continue;
    1885         [ #  # ]:          0 :                 if (!xas_retry(&xas, entry))
    1886                 :            :                         break;
    1887                 :            :         }
    1888                 :            :         rcu_read_unlock();
    1889                 :            : 
    1890         [ #  # ]:          0 :         if (entry)
    1891                 :          0 :                 *indexp = xas.xa_index;
    1892                 :          0 :         return entry;
    1893                 :            : }
    1894                 :            : EXPORT_SYMBOL(xa_find_after);
    1895                 :            : 
    1896                 :          0 : static unsigned int xas_extract_present(struct xa_state *xas, void **dst,
    1897                 :            :                         unsigned long max, unsigned int n)
    1898                 :            : {
    1899                 :            :         void *entry;
    1900                 :            :         unsigned int i = 0;
    1901                 :            : 
    1902                 :            :         rcu_read_lock();
    1903         [ #  # ]:          0 :         xas_for_each(xas, entry, max) {
    1904         [ #  # ]:          0 :                 if (xas_retry(xas, entry))
    1905                 :          0 :                         continue;
    1906                 :          0 :                 dst[i++] = entry;
    1907         [ #  # ]:          0 :                 if (i == n)
    1908                 :            :                         break;
    1909                 :            :         }
    1910                 :            :         rcu_read_unlock();
    1911                 :            : 
    1912                 :          0 :         return i;
    1913                 :            : }
    1914                 :            : 
    1915                 :          0 : static unsigned int xas_extract_marked(struct xa_state *xas, void **dst,
    1916                 :            :                         unsigned long max, unsigned int n, xa_mark_t mark)
    1917                 :            : {
    1918                 :            :         void *entry;
    1919                 :            :         unsigned int i = 0;
    1920                 :            : 
    1921                 :            :         rcu_read_lock();
    1922         [ #  # ]:          0 :         xas_for_each_marked(xas, entry, max, mark) {
    1923         [ #  # ]:          0 :                 if (xas_retry(xas, entry))
    1924                 :          0 :                         continue;
    1925                 :          0 :                 dst[i++] = entry;
    1926         [ #  # ]:          0 :                 if (i == n)
    1927                 :            :                         break;
    1928                 :            :         }
    1929                 :            :         rcu_read_unlock();
    1930                 :            : 
    1931                 :          0 :         return i;
    1932                 :            : }
    1933                 :            : 
    1934                 :            : /**
    1935                 :            :  * xa_extract() - Copy selected entries from the XArray into a normal array.
    1936                 :            :  * @xa: The source XArray to copy from.
    1937                 :            :  * @dst: The buffer to copy entries into.
    1938                 :            :  * @start: The first index in the XArray eligible to be selected.
    1939                 :            :  * @max: The last index in the XArray eligible to be selected.
    1940                 :            :  * @n: The maximum number of entries to copy.
    1941                 :            :  * @filter: Selection criterion.
    1942                 :            :  *
    1943                 :            :  * Copies up to @n entries that match @filter from the XArray.  The
    1944                 :            :  * copied entries will have indices between @start and @max, inclusive.
    1945                 :            :  *
    1946                 :            :  * The @filter may be an XArray mark value, in which case entries which are
    1947                 :            :  * marked with that mark will be copied.  It may also be %XA_PRESENT, in
    1948                 :            :  * which case all entries which are not %NULL will be copied.
    1949                 :            :  *
    1950                 :            :  * The entries returned may not represent a snapshot of the XArray at a
    1951                 :            :  * moment in time.  For example, if another thread stores to index 5, then
    1952                 :            :  * index 10, calling xa_extract() may return the old contents of index 5
    1953                 :            :  * and the new contents of index 10.  Indices not modified while this
    1954                 :            :  * function is running will not be skipped.
    1955                 :            :  *
    1956                 :            :  * If you need stronger guarantees, holding the xa_lock across calls to this
    1957                 :            :  * function will prevent concurrent modification.
    1958                 :            :  *
    1959                 :            :  * Context: Any context.  Takes and releases the RCU lock.
    1960                 :            :  * Return: The number of entries copied.
    1961                 :            :  */
    1962                 :          0 : unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start,
    1963                 :            :                         unsigned long max, unsigned int n, xa_mark_t filter)
    1964                 :            : {
    1965                 :          0 :         XA_STATE(xas, xa, start);
    1966                 :            : 
    1967         [ #  # ]:          0 :         if (!n)
    1968                 :            :                 return 0;
    1969                 :            : 
    1970         [ #  # ]:          0 :         if ((__force unsigned int)filter < XA_MAX_MARKS)
    1971                 :          0 :                 return xas_extract_marked(&xas, dst, max, n, filter);
    1972                 :          0 :         return xas_extract_present(&xas, dst, max, n);
    1973                 :            : }
    1974                 :            : EXPORT_SYMBOL(xa_extract);
    1975                 :            : 
    1976                 :            : /**
    1977                 :            :  * xa_destroy() - Free all internal data structures.
    1978                 :            :  * @xa: XArray.
    1979                 :            :  *
    1980                 :            :  * After calling this function, the XArray is empty and has freed all memory
    1981                 :            :  * allocated for its internal data structures.  You are responsible for
    1982                 :            :  * freeing the objects referenced by the XArray.
    1983                 :            :  *
    1984                 :            :  * Context: Any context.  Takes and releases the xa_lock, interrupt-safe.
    1985                 :            :  */
    1986                 :          0 : void xa_destroy(struct xarray *xa)
    1987                 :            : {
    1988                 :          0 :         XA_STATE(xas, xa, 0);
    1989                 :            :         unsigned long flags;
    1990                 :            :         void *entry;
    1991                 :            : 
    1992                 :          0 :         xas.xa_node = NULL;
    1993                 :          0 :         xas_lock_irqsave(&xas, flags);
    1994                 :            :         entry = xa_head_locked(xa);
    1995                 :            :         RCU_INIT_POINTER(xa->xa_head, NULL);
    1996                 :          0 :         xas_init_marks(&xas);
    1997         [ #  # ]:          0 :         if (xa_zero_busy(xa))
    1998                 :            :                 xa_mark_clear(xa, XA_FREE_MARK);
    1999                 :            :         /* lockdep checks we're still holding the lock in xas_free_nodes() */
    2000         [ #  # ]:          0 :         if (xa_is_node(entry))
    2001                 :          0 :                 xas_free_nodes(&xas, xa_to_node(entry));
    2002                 :          0 :         xas_unlock_irqrestore(&xas, flags);
    2003                 :          0 : }
    2004                 :            : EXPORT_SYMBOL(xa_destroy);
    2005                 :            : 
    2006                 :            : #ifdef XA_DEBUG
    2007                 :            : void xa_dump_node(const struct xa_node *node)
    2008                 :            : {
    2009                 :            :         unsigned i, j;
    2010                 :            : 
    2011                 :            :         if (!node)
    2012                 :            :                 return;
    2013                 :            :         if ((unsigned long)node & 3) {
    2014                 :            :                 pr_cont("node %px\n", node);
    2015                 :            :                 return;
    2016                 :            :         }
    2017                 :            : 
    2018                 :            :         pr_cont("node %px %s %d parent %px shift %d count %d values %d "
    2019                 :            :                 "array %px list %px %px marks",
    2020                 :            :                 node, node->parent ? "offset" : "max", node->offset,
    2021                 :            :                 node->parent, node->shift, node->count, node->nr_values,
    2022                 :            :                 node->array, node->private_list.prev, node->private_list.next);
    2023                 :            :         for (i = 0; i < XA_MAX_MARKS; i++)
    2024                 :            :                 for (j = 0; j < XA_MARK_LONGS; j++)
    2025                 :            :                         pr_cont(" %lx", node->marks[i][j]);
    2026                 :            :         pr_cont("\n");
    2027                 :            : }
    2028                 :            : 
    2029                 :            : void xa_dump_index(unsigned long index, unsigned int shift)
    2030                 :            : {
    2031                 :            :         if (!shift)
    2032                 :            :                 pr_info("%lu: ", index);
    2033                 :            :         else if (shift >= BITS_PER_LONG)
    2034                 :            :                 pr_info("0-%lu: ", ~0UL);
    2035                 :            :         else
    2036                 :            :                 pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1));
    2037                 :            : }
    2038                 :            : 
    2039                 :            : void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
    2040                 :            : {
    2041                 :            :         if (!entry)
    2042                 :            :                 return;
    2043                 :            : 
    2044                 :            :         xa_dump_index(index, shift);
    2045                 :            : 
    2046                 :            :         if (xa_is_node(entry)) {
    2047                 :            :                 if (shift == 0) {
    2048                 :            :                         pr_cont("%px\n", entry);
    2049                 :            :                 } else {
    2050                 :            :                         unsigned long i;
    2051                 :            :                         struct xa_node *node = xa_to_node(entry);
    2052                 :            :                         xa_dump_node(node);
    2053                 :            :                         for (i = 0; i < XA_CHUNK_SIZE; i++)
    2054                 :            :                                 xa_dump_entry(node->slots[i],
    2055                 :            :                                       index + (i << node->shift), node->shift);
    2056                 :            :                 }
    2057                 :            :         } else if (xa_is_value(entry))
    2058                 :            :                 pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
    2059                 :            :                                                 xa_to_value(entry), entry);
    2060                 :            :         else if (!xa_is_internal(entry))
    2061                 :            :                 pr_cont("%px\n", entry);
    2062                 :            :         else if (xa_is_retry(entry))
    2063                 :            :                 pr_cont("retry (%ld)\n", xa_to_internal(entry));
    2064                 :            :         else if (xa_is_sibling(entry))
    2065                 :            :                 pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry));
    2066                 :            :         else if (xa_is_zero(entry))
    2067                 :            :                 pr_cont("zero (%ld)\n", xa_to_internal(entry));
    2068                 :            :         else
    2069                 :            :                 pr_cont("UNKNOWN ENTRY (%px)\n", entry);
    2070                 :            : }
    2071                 :            : 
    2072                 :            : void xa_dump(const struct xarray *xa)
    2073                 :            : {
    2074                 :            :         void *entry = xa->xa_head;
    2075                 :            :         unsigned int shift = 0;
    2076                 :            : 
    2077                 :            :         pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,
    2078                 :            :                         xa->xa_flags, xa_marked(xa, XA_MARK_0),
    2079                 :            :                         xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));
    2080                 :            :         if (xa_is_node(entry))
    2081                 :            :                 shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;
    2082                 :            :         xa_dump_entry(entry, 0, shift);
    2083                 :            : }
    2084                 :            : #endif

Generated by: LCOV version 1.14