lib/xarray.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * XArray implementation
   4  * Copyright (c) 2017 Microsoft Corporation
   5  * Author: Matthew Wilcox <willy@infradead.org>
   6  */
   7
   8 #include <linux/bitmap.h>
   9 #include <linux/export.h>
  10 #include <linux/xarray.h>
  11
  12 /*
  13  * Coding conventions in this file:
  14  *
  15  * @xa is used to refer to the entire xarray.
  16  * @xas is the 'xarray operation state'.  It may be either a pointer to
  17  * an xa_state, or an xa_state stored on the stack.  This is an unfortunate
  18  * ambiguity.
  19  * @index is the index of the entry being operated on
  20  * @mark is an xa_mark_t; a small number indicating one of the mark bits.
  21  * @node refers to an xa_node; usually the primary one being operated on by
  22  * this function.
  23  * @offset is the index into the slots array inside an xa_node.
  24  * @parent refers to the @xa_node closer to the head than @node.
  25  * @entry refers to something stored in a slot in the xarray
  26  */
  27
  28 static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
  29 {
  30         if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
  31                 xa->xa_flags |= XA_FLAGS_MARK(mark);
  32 }
  33
  34 static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark)
  35 {
  36         if (xa->xa_flags & XA_FLAGS_MARK(mark))
  37                 xa->xa_flags &= ~(XA_FLAGS_MARK(mark));
  38 }
  39
  40 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
  41 {
  42         return node->marks[(__force unsigned)mark];
  43 }
  44
  45 static inline bool node_get_mark(struct xa_node *node,
  46                 unsigned int offset, xa_mark_t mark)
  47 {
  48         return test_bit(offset, node_marks(node, mark));
  49 }
  50
  51 /* returns true if the bit was set */
  52 static inline bool node_set_mark(struct xa_node *node, unsigned int offset,
  53                                 xa_mark_t mark)
  54 {
  55         return __test_and_set_bit(offset, node_marks(node, mark));
  56 }
  57
  58 /* returns true if the bit was set */
  59 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset,
  60                                 xa_mark_t mark)
  61 {
  62         return __test_and_clear_bit(offset, node_marks(node, mark));
  63 }
  64
  65 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
  66 {
  67         return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
  68 }
  69
  70 /* extracts the offset within this node from the index */
  71 static unsigned int get_offset(unsigned long index, struct xa_node *node)
  72 {
  73         return (index >> node->shift) & XA_CHUNK_MASK;
  74 }
  75
  76 /* move the index either forwards (find) or backwards (sibling slot) */
  77 static void xas_move_index(struct xa_state *xas, unsigned long offset)
  78 {
  79         unsigned int shift = xas->xa_node->shift;
  80         xas->xa_index &= ~XA_CHUNK_MASK << shift;
  81         xas->xa_index += offset << shift;
  82 }
  83
  84 static void *set_bounds(struct xa_state *xas)
  85 {
  86         xas->xa_node = XAS_BOUNDS;
  87         return NULL;
  88 }
  89
  90 /*
  91  * Starts a walk.  If the @xas is already valid, we assume that it's on
  92  * the right path and just return where we've got to.  If we're in an
  93  * error state, return NULL.  If the index is outside the current scope
  94  * of the xarray, return NULL without changing @xas->xa_node.  Otherwise
  95  * set @xas->xa_node to NULL and return the current head of the array.
  96  */
  97 static void *xas_start(struct xa_state *xas)
  98 {
  99         void *entry;
 100
 101         if (xas_valid(xas))
 102                 return xas_reload(xas);
 103         if (xas_error(xas))
 104                 return NULL;
 105
 106         entry = xa_head(xas->xa);
 107         if (!xa_is_node(entry)) {
 108                 if (xas->xa_index)
 109                         return set_bounds(xas);
 110         } else {
 111                 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK)
 112                         return set_bounds(xas);
 113         }
 114
 115         xas->xa_node = NULL;
 116         return entry;
 117 }
 118
 119 static void *xas_descend(struct xa_state *xas, struct xa_node *node)
 120 {
 121         unsigned int offset = get_offset(xas->xa_index, node);
 122         void *entry = xa_entry(xas->xa, node, offset);
 123
 124         xas->xa_node = node;
 125         if (xa_is_sibling(entry)) {
 126                 offset = xa_to_sibling(entry);
 127                 entry = xa_entry(xas->xa, node, offset);
 128         }
 129
 130         xas->xa_offset = offset;
 131         return entry;
 132 }
 133
 134 /**
 135  * xas_load() - Load an entry from the XArray (advanced).
 136  * @xas: XArray operation state.
 137  *
 138  * Usually walks the @xas to the appropriate state to load the entry
 139  * stored at xa_index.  However, it will do nothing and return %NULL if
 140  * @xas is in an error state.  xas_load() will never expand the tree.
 141  *
 142  * If the xa_state is set up to operate on a multi-index entry, xas_load()
 143  * may return %NULL or an internal entry, even if there are entries
 144  * present within the range specified by @xas.
 145  *
 146  * Context: Any context.  The caller should hold the xa_lock or the RCU lock.
 147  * Return: Usually an entry in the XArray, but see description for exceptions.
 148  */
 149 void *xas_load(struct xa_state *xas)
 150 {
 151         void *entry = xas_start(xas);
 152
 153         while (xa_is_node(entry)) {
 154                 struct xa_node *node = xa_to_node(entry);
 155
 156                 if (xas->xa_shift > node->shift)
 157                         break;
 158                 entry = xas_descend(xas, node);
 159         }
 160         return entry;
 161 }
 162 EXPORT_SYMBOL_GPL(xas_load);
 163
 164 /**
 165  * xas_get_mark() - Returns the state of this mark.
 166  * @xas: XArray operation state.
 167  * @mark: Mark number.
 168  *
 169  * Return: true if the mark is set, false if the mark is clear or @xas
 170  * is in an error state.
 171  */
 172 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)
 173 {
 174         if (xas_invalid(xas))
 175                 return false;
 176         if (!xas->xa_node)
 177                 return xa_marked(xas->xa, mark);
 178         return node_get_mark(xas->xa_node, xas->xa_offset, mark);
 179 }
 180 EXPORT_SYMBOL_GPL(xas_get_mark);
 181
 182 /**
 183  * xas_set_mark() - Sets the mark on this entry and its parents.
 184  * @xas: XArray operation state.
 185  * @mark: Mark number.
 186  *
 187  * Sets the specified mark on this entry, and walks up the tree setting it
 188  * on all the ancestor entries.  Does nothing if @xas has not been walked to
 189  * an entry, or is in an error state.
 190  */
 191 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)
 192 {
 193         struct xa_node *node = xas->xa_node;
 194         unsigned int offset = xas->xa_offset;
 195
 196         if (xas_invalid(xas))
 197                 return;
 198
 199         while (node) {
 200                 if (node_set_mark(node, offset, mark))
 201                         return;
 202                 offset = node->offset;
 203                 node = xa_parent_locked(xas->xa, node);
 204         }
 205
 206         if (!xa_marked(xas->xa, mark))
 207                 xa_mark_set(xas->xa, mark);
 208 }
 209 EXPORT_SYMBOL_GPL(xas_set_mark);
 210
 211 /**
 212  * xas_clear_mark() - Clears the mark on this entry and its parents.
 213  * @xas: XArray operation state.
 214  * @mark: Mark number.
 215  *
 216  * Clears the specified mark on this entry, and walks back to the head
 217  * attempting to clear it on all the ancestor entries.  Does nothing if
 218  * @xas has not been walked to an entry, or is in an error state.
 219  */
 220 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)
 221 {
 222         struct xa_node *node = xas->xa_node;
 223         unsigned int offset = xas->xa_offset;
 224
 225         if (xas_invalid(xas))
 226                 return;
 227
 228         while (node) {
 229                 if (!node_clear_mark(node, offset, mark))
 230                         return;
 231                 if (node_any_mark(node, mark))
 232                         return;
 233
 234                 offset = node->offset;
 235                 node = xa_parent_locked(xas->xa, node);
 236         }
 237
 238         if (xa_marked(xas->xa, mark))
 239                 xa_mark_clear(xas->xa, mark);
 240 }
 241 EXPORT_SYMBOL_GPL(xas_clear_mark);
 242
 243 /**
 244  * xa_init_flags() - Initialise an empty XArray with flags.
 245  * @xa: XArray.
 246  * @flags: XA_FLAG values.
 247  *
 248  * If you need to initialise an XArray with special flags (eg you need
 249  * to take the lock from interrupt context), use this function instead
 250  * of xa_init().
 251  *
 252  * Context: Any context.
 253  */
 254 void xa_init_flags(struct xarray *xa, gfp_t flags)
 255 {
 256         spin_lock_init(&xa->xa_lock);
 257         xa->xa_flags = flags;
 258         xa->xa_head = NULL;
 259 }
 260 EXPORT_SYMBOL(xa_init_flags);
 261
 262 /**
 263  * xa_load() - Load an entry from an XArray.
 264  * @xa: XArray.
 265  * @index: index into array.
 266  *
 267  * Context: Any context.  Takes and releases the RCU lock.
 268  * Return: The entry at @index in @xa.
 269  */
 270 void *xa_load(struct xarray *xa, unsigned long index)
 271 {
 272         XA_STATE(xas, xa, index);
 273         void *entry;
 274
 275         rcu_read_lock();
 276         do {
 277                 entry = xas_load(&xas);
 278         } while (xas_retry(&xas, entry));
 279         rcu_read_unlock();
 280
 281         return entry;
 282 }
 283 EXPORT_SYMBOL(xa_load);
 284
 285 /**
 286  * __xa_set_mark() - Set this mark on this entry while locked.
 287  * @xa: XArray.
 288  * @index: Index of entry.
 289  * @mark: Mark number.
 290  *
 291  * Attempting to set a mark on a NULL entry does not succeed.
 292  *
 293  * Context: Any context.  Expects xa_lock to be held on entry.
 294  */
 295 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
 296 {
 297         XA_STATE(xas, xa, index);
 298         void *entry = xas_load(&xas);
 299
 300         if (entry)
 301                 xas_set_mark(&xas, mark);
 302 }
 303 EXPORT_SYMBOL_GPL(__xa_set_mark);
 304
 305 /**
 306  * __xa_clear_mark() - Clear this mark on this entry while locked.
 307  * @xa: XArray.
 308  * @index: Index of entry.
 309  * @mark: Mark number.
 310  *
 311  * Context: Any context.  Expects xa_lock to be held on entry.
 312  */
 313 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
 314 {
 315         XA_STATE(xas, xa, index);
 316         void *entry = xas_load(&xas);
 317
 318         if (entry)
 319                 xas_clear_mark(&xas, mark);
 320 }
 321 EXPORT_SYMBOL_GPL(__xa_clear_mark);
 322
 323 /**
 324  * xa_get_mark() - Inquire whether this mark is set on this entry.
 325  * @xa: XArray.
 326  * @index: Index of entry.
 327  * @mark: Mark number.
 328  *
 329  * This function uses the RCU read lock, so the result may be out of date
 330  * by the time it returns.  If you need the result to be stable, use a lock.
 331  *
 332  * Context: Any context.  Takes and releases the RCU lock.
 333  * Return: True if the entry at @index has this mark set, false if it doesn't.
 334  */
 335 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
 336 {
 337         XA_STATE(xas, xa, index);
 338         void *entry;
 339
 340         rcu_read_lock();
 341         entry = xas_start(&xas);
 342         while (xas_get_mark(&xas, mark)) {
 343                 if (!xa_is_node(entry))
 344                         goto found;
 345                 entry = xas_descend(&xas, xa_to_node(entry));
 346         }
 347         rcu_read_unlock();
 348         return false;
 349  found:
 350         rcu_read_unlock();
 351         return true;
 352 }
 353 EXPORT_SYMBOL(xa_get_mark);
 354
 355 /**
 356  * xa_set_mark() - Set this mark on this entry.
 357  * @xa: XArray.
 358  * @index: Index of entry.
 359  * @mark: Mark number.
 360  *
 361  * Attempting to set a mark on a NULL entry does not succeed.
 362  *
 363  * Context: Process context.  Takes and releases the xa_lock.
 364  */
 365 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
 366 {
 367         xa_lock(xa);
 368         __xa_set_mark(xa, index, mark);
 369         xa_unlock(xa);
 370 }
 371 EXPORT_SYMBOL(xa_set_mark);
 372
 373 /**
 374  * xa_clear_mark() - Clear this mark on this entry.
 375  * @xa: XArray.
 376  * @index: Index of entry.
 377  * @mark: Mark number.
 378  *
 379  * Clearing a mark always succeeds.
 380  *
 381  * Context: Process context.  Takes and releases the xa_lock.
 382  */
 383 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
 384 {
 385         xa_lock(xa);
 386         __xa_clear_mark(xa, index, mark);
 387         xa_unlock(xa);
 388 }
 389 EXPORT_SYMBOL(xa_clear_mark);
 390
 391 #ifdef XA_DEBUG
 392 void xa_dump_node(const struct xa_node *node)
 393 {
 394         unsigned i, j;
 395
 396         if (!node)
 397                 return;
 398         if ((unsigned long)node & 3) {
 399                 pr_cont("node %px\n", node);
 400                 return;
 401         }
 402
 403         pr_cont("node %px %s %d parent %px shift %d count %d values %d "
 404                 "array %px list %px %px marks",
 405                 node, node->parent ? "offset" : "max", node->offset,
 406                 node->parent, node->shift, node->count, node->nr_values,
 407                 node->array, node->private_list.prev, node->private_list.next);
 408         for (i = 0; i < XA_MAX_MARKS; i++)
 409                 for (j = 0; j < XA_MARK_LONGS; j++)
 410                         pr_cont(" %lx", node->marks[i][j]);
 411         pr_cont("\n");
 412 }
 413
 414 void xa_dump_index(unsigned long index, unsigned int shift)
 415 {
 416         if (!shift)
 417                 pr_info("%lu: ", index);
 418         else if (shift >= BITS_PER_LONG)
 419                 pr_info("0-%lu: ", ~0UL);
 420         else
 421                 pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1));
 422 }
 423
 424 void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
 425 {
 426         if (!entry)
 427                 return;
 428
 429         xa_dump_index(index, shift);
 430
 431         if (xa_is_node(entry)) {
 432                 if (shift == 0) {
 433                         pr_cont("%px\n", entry);
 434                 } else {
 435                         unsigned long i;
 436                         struct xa_node *node = xa_to_node(entry);
 437                         xa_dump_node(node);
 438                         for (i = 0; i < XA_CHUNK_SIZE; i++)
 439                                 xa_dump_entry(node->slots[i],
 440                                       index + (i << node->shift), node->shift);
 441                 }
 442         } else if (xa_is_value(entry))
 443                 pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
 444                                                 xa_to_value(entry), entry);
 445         else if (!xa_is_internal(entry))
 446                 pr_cont("%px\n", entry);
 447         else if (xa_is_retry(entry))
 448                 pr_cont("retry (%ld)\n", xa_to_internal(entry));
 449         else if (xa_is_sibling(entry))
 450                 pr_cont("sibling (slot %ld)\n", xa_to_sibling(entry));
 451         else
 452                 pr_cont("UNKNOWN ENTRY (%px)\n", entry);
 453 }
 454
 455 void xa_dump(const struct xarray *xa)
 456 {
 457         void *entry = xa->xa_head;
 458         unsigned int shift = 0;
 459
 460         pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry,
 461                         xa->xa_flags, xa_marked(xa, XA_MARK_0),
 462                         xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));
 463         if (xa_is_node(entry))
 464                 shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;
 465         xa_dump_entry(entry, 0, shift);
 466 }
 467 #endif