include/linux/sbitmap.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Fast and scalable bitmaps.
   4  *
   5  * Copyright (C) 2016 Facebook
   6  * Copyright (C) 2013-2014 Jens Axboe
   7  */
   8
   9 #ifndef __LINUX_SCALE_BITMAP_H
  10 #define __LINUX_SCALE_BITMAP_H
  11
  12 #include <linux/atomic.h>
  13 #include <linux/bitops.h>
  14 #include <linux/cache.h>
  15 #include <linux/list.h>
  16 #include <linux/log2.h>
  17 #include <linux/minmax.h>
  18 #include <linux/percpu.h>
  19 #include <linux/slab.h>
  20 #include <linux/smp.h>
  21 #include <linux/types.h>
  22 #include <linux/wait.h>
  23
  24 struct seq_file;
  25
  26 /**
  27  * struct sbitmap_word - Word in a &struct sbitmap.
  28  */
  29 struct sbitmap_word {
  30         /**
  31          * @word: word holding free bits
  32          */
  33         unsigned long word;
  34
  35         /**
  36          * @cleared: word holding cleared bits
  37          */
  38         unsigned long cleared ____cacheline_aligned_in_smp;
  39 } ____cacheline_aligned_in_smp;
  40
  41 /**
  42  * struct sbitmap - Scalable bitmap.
  43  *
  44  * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This
  45  * trades off higher memory usage for better scalability.
  46  */
  47 struct sbitmap {
  48         /**
  49          * @depth: Number of bits used in the whole bitmap.
  50          */
  51         unsigned int depth;
  52
  53         /**
  54          * @shift: log2(number of bits used per word)
  55          */
  56         unsigned int shift;
  57
  58         /**
  59          * @map_nr: Number of words (cachelines) being used for the bitmap.
  60          */
  61         unsigned int map_nr;
  62
  63         /**
  64          * @round_robin: Allocate bits in strict round-robin order.
  65          */
  66         bool round_robin;
  67
  68         /**
  69          * @map: Allocated bitmap.
  70          */
  71         struct sbitmap_word *map;
  72
  73         /*
  74          * @alloc_hint: Cache of last successfully allocated or freed bit.
  75          *
  76          * This is per-cpu, which allows multiple users to stick to different
  77          * cachelines until the map is exhausted.
  78          */
  79         unsigned int __percpu *alloc_hint;
  80 };
  81
  82 #define SBQ_WAIT_QUEUES 8
  83 #define SBQ_WAKE_BATCH 8
  84
  85 /**
  86  * struct sbq_wait_state - Wait queue in a &struct sbitmap_queue.
  87  */
  88 struct sbq_wait_state {
  89         /**
  90          * @wait: Wait queue.
  91          */
  92         wait_queue_head_t wait;
  93 } ____cacheline_aligned_in_smp;
  94
  95 /**
  96  * struct sbitmap_queue - Scalable bitmap with the added ability to wait on free
  97  * bits.
  98  *
  99  * A &struct sbitmap_queue uses multiple wait queues and rolling wakeups to
 100  * avoid contention on the wait queue spinlock. This ensures that we don't hit a
 101  * scalability wall when we run out of free bits and have to start putting tasks
 102  * to sleep.
 103  */
 104 struct sbitmap_queue {
 105         /**
 106          * @sb: Scalable bitmap.
 107          */
 108         struct sbitmap sb;
 109
 110         /**
 111          * @wake_batch: Number of bits which must be freed before we wake up any
 112          * waiters.
 113          */
 114         unsigned int wake_batch;
 115
 116         /**
 117          * @wake_index: Next wait queue in @ws to wake up.
 118          */
 119         atomic_t wake_index;
 120
 121         /**
 122          * @ws: Wait queues.
 123          */
 124         struct sbq_wait_state *ws;
 125
 126         /*
 127          * @ws_active: count of currently active ws waitqueues
 128          */
 129         atomic_t ws_active;
 130
 131         /**
 132          * @min_shallow_depth: The minimum shallow depth which may be passed to
 133          * sbitmap_queue_get_shallow()
 134          */
 135         unsigned int min_shallow_depth;
 136
 137         /**
 138          * @completion_cnt: Number of bits cleared passed to the
 139          * wakeup function.
 140          */
 141         atomic_t completion_cnt;
 142
 143         /**
 144          * @wakeup_cnt: Number of thread wake ups issued.
 145          */
 146         atomic_t wakeup_cnt;
 147 };
 148
 149 /**
 150  * sbitmap_init_node() - Initialize a &struct sbitmap on a specific memory node.
 151  * @sb: Bitmap to initialize.
 152  * @depth: Number of bits to allocate.
 153  * @shift: Use 2^@shift bits per word in the bitmap; if a negative number if
 154  *         given, a good default is chosen.
 155  * @flags: Allocation flags.
 156  * @node: Memory node to allocate on.
 157  * @round_robin: If true, be stricter about allocation order; always allocate
 158  *               starting from the last allocated bit. This is less efficient
 159  *               than the default behavior (false).
 160  * @alloc_hint: If true, apply percpu hint for where to start searching for
 161  *              a free bit.
 162  *
 163  * Return: Zero on success or negative errno on failure.
 164  */
 165 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
 166                       gfp_t flags, int node, bool round_robin, bool alloc_hint);
 167
 168 /* sbitmap internal helper */
 169 static inline unsigned int __map_depth(const struct sbitmap *sb, int index)
 170 {
 171         if (index == sb->map_nr - 1)
 172                 return sb->depth - (index << sb->shift);
 173         return 1U << sb->shift;
 174 }
 175
 176 /**
 177  * sbitmap_free() - Free memory used by a &struct sbitmap.
 178  * @sb: Bitmap to free.
 179  */
 180 static inline void sbitmap_free(struct sbitmap *sb)
 181 {
 182         free_percpu(sb->alloc_hint);
 183         kvfree(sb->map);
 184         sb->map = NULL;
 185 }
 186
 187 /**
 188  * sbitmap_resize() - Resize a &struct sbitmap.
 189  * @sb: Bitmap to resize.
 190  * @depth: New number of bits to resize to.
 191  *
 192  * Doesn't reallocate anything. It's up to the caller to ensure that the new
 193  * depth doesn't exceed the depth that the sb was initialized with.
 194  */
 195 void sbitmap_resize(struct sbitmap *sb, unsigned int depth);
 196
 197 /**
 198  * sbitmap_get() - Try to allocate a free bit from a &struct sbitmap.
 199  * @sb: Bitmap to allocate from.
 200  *
 201  * This operation provides acquire barrier semantics if it succeeds.
 202  *
 203  * Return: Non-negative allocated bit number if successful, -1 otherwise.
 204  */
 205 int sbitmap_get(struct sbitmap *sb);
 206
 207 /**
 208  * sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap,
 209  * limiting the depth used from each word.
 210  * @sb: Bitmap to allocate from.
 211  * @shallow_depth: The maximum number of bits to allocate from a single word.
 212  *
 213  * This rather specific operation allows for having multiple users with
 214  * different allocation limits. E.g., there can be a high-priority class that
 215  * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
 216  * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
 217  * class can only allocate half of the total bits in the bitmap, preventing it
 218  * from starving out the high-priority class.
 219  *
 220  * Return: Non-negative allocated bit number if successful, -1 otherwise.
 221  */
 222 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth);
 223
 224 /**
 225  * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap.
 226  * @sb: Bitmap to check.
 227  *
 228  * Return: true if any bit in the bitmap is set, false otherwise.
 229  */
 230 bool sbitmap_any_bit_set(const struct sbitmap *sb);
 231
 232 #define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
 233 #define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
 234
 235 typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
 236
 237 /**
 238  * __sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
 239  * @start: Where to start the iteration.
 240  * @sb: Bitmap to iterate over.
 241  * @fn: Callback. Should return true to continue or false to break early.
 242  * @data: Pointer to pass to callback.
 243  *
 244  * This is inline even though it's non-trivial so that the function calls to the
 245  * callback will hopefully get optimized away.
 246  */
 247 static inline void __sbitmap_for_each_set(struct sbitmap *sb,
 248                                           unsigned int start,
 249                                           sb_for_each_fn fn, void *data)
 250 {
 251         unsigned int index;
 252         unsigned int nr;
 253         unsigned int scanned = 0;
 254
 255         if (start >= sb->depth)
 256                 start = 0;
 257         index = SB_NR_TO_INDEX(sb, start);
 258         nr = SB_NR_TO_BIT(sb, start);
 259
 260         while (scanned < sb->depth) {
 261                 unsigned long word;
 262                 unsigned int depth = min_t(unsigned int,
 263                                            __map_depth(sb, index) - nr,
 264                                            sb->depth - scanned);
 265
 266                 scanned += depth;
 267                 word = sb->map[index].word & ~sb->map[index].cleared;
 268                 if (!word)
 269                         goto next;
 270
 271                 /*
 272                  * On the first iteration of the outer loop, we need to add the
 273                  * bit offset back to the size of the word for find_next_bit().
 274                  * On all other iterations, nr is zero, so this is a noop.
 275                  */
 276                 depth += nr;
 277                 while (1) {
 278                         nr = find_next_bit(&word, depth, nr);
 279                         if (nr >= depth)
 280                                 break;
 281                         if (!fn(sb, (index << sb->shift) + nr, data))
 282                                 return;
 283
 284                         nr++;
 285                 }
 286 next:
 287                 nr = 0;
 288                 if (++index >= sb->map_nr)
 289                         index = 0;
 290         }
 291 }
 292
 293 /**
 294  * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
 295  * @sb: Bitmap to iterate over.
 296  * @fn: Callback. Should return true to continue or false to break early.
 297  * @data: Pointer to pass to callback.
 298  */
 299 static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
 300                                         void *data)
 301 {
 302         __sbitmap_for_each_set(sb, 0, fn, data);
 303 }
 304
 305 static inline unsigned long *__sbitmap_word(struct sbitmap *sb,
 306                                             unsigned int bitnr)
 307 {
 308         return &sb->map[SB_NR_TO_INDEX(sb, bitnr)].word;
 309 }
 310
 311 /* Helpers equivalent to the operations in asm/bitops.h and linux/bitmap.h */
 312
 313 static inline void sbitmap_set_bit(struct sbitmap *sb, unsigned int bitnr)
 314 {
 315         set_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
 316 }
 317
 318 static inline void sbitmap_clear_bit(struct sbitmap *sb, unsigned int bitnr)
 319 {
 320         clear_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
 321 }
 322
 323 /*
 324  * This one is special, since it doesn't actually clear the bit, rather it
 325  * sets the corresponding bit in the ->cleared mask instead. Paired with
 326  * the caller doing sbitmap_deferred_clear() if a given index is full, which
 327  * will clear the previously freed entries in the corresponding ->word.
 328  */
 329 static inline void sbitmap_deferred_clear_bit(struct sbitmap *sb, unsigned int bitnr)
 330 {
 331         unsigned long *addr = &sb->map[SB_NR_TO_INDEX(sb, bitnr)].cleared;
 332
 333         set_bit(SB_NR_TO_BIT(sb, bitnr), addr);
 334 }
 335
 336 /*
 337  * Pair of sbitmap_get, and this one applies both cleared bit and
 338  * allocation hint.
 339  */
 340 static inline void sbitmap_put(struct sbitmap *sb, unsigned int bitnr)
 341 {
 342         sbitmap_deferred_clear_bit(sb, bitnr);
 343
 344         if (likely(sb->alloc_hint && !sb->round_robin && bitnr < sb->depth))
 345                 *raw_cpu_ptr(sb->alloc_hint) = bitnr;
 346 }
 347
 348 static inline int sbitmap_test_bit(struct sbitmap *sb, unsigned int bitnr)
 349 {
 350         return test_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
 351 }
 352
 353 static inline int sbitmap_calculate_shift(unsigned int depth)
 354 {
 355         int     shift = ilog2(BITS_PER_LONG);
 356
 357         /*
 358          * If the bitmap is small, shrink the number of bits per word so
 359          * we spread over a few cachelines, at least. If less than 4
 360          * bits, just forget about it, it's not going to work optimally
 361          * anyway.
 362          */
 363         if (depth >= 4) {
 364                 while ((4U << shift) > depth)
 365                         shift--;
 366         }
 367
 368         return shift;
 369 }
 370
 371 /**
 372  * sbitmap_show() - Dump &struct sbitmap information to a &struct seq_file.
 373  * @sb: Bitmap to show.
 374  * @m: struct seq_file to write to.
 375  *
 376  * This is intended for debugging. The format may change at any time.
 377  */
 378 void sbitmap_show(struct sbitmap *sb, struct seq_file *m);
 379
 380
 381 /**
 382  * sbitmap_weight() - Return how many set and not cleared bits in a &struct
 383  * sbitmap.
 384  * @sb: Bitmap to check.
 385  *
 386  * Return: How many set and not cleared bits set
 387  */
 388 unsigned int sbitmap_weight(const struct sbitmap *sb);
 389
 390 /**
 391  * sbitmap_bitmap_show() - Write a hex dump of a &struct sbitmap to a &struct
 392  * seq_file.
 393  * @sb: Bitmap to show.
 394  * @m: struct seq_file to write to.
 395  *
 396  * This is intended for debugging. The output isn't guaranteed to be internally
 397  * consistent.
 398  */
 399 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m);
 400
 401 /**
 402  * sbitmap_queue_init_node() - Initialize a &struct sbitmap_queue on a specific
 403  * memory node.
 404  * @sbq: Bitmap queue to initialize.
 405  * @depth: See sbitmap_init_node().
 406  * @shift: See sbitmap_init_node().
 407  * @round_robin: See sbitmap_get().
 408  * @flags: Allocation flags.
 409  * @node: Memory node to allocate on.
 410  *
 411  * Return: Zero on success or negative errno on failure.
 412  */
 413 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
 414                             int shift, bool round_robin, gfp_t flags, int node);
 415
 416 /**
 417  * sbitmap_queue_free() - Free memory used by a &struct sbitmap_queue.
 418  *
 419  * @sbq: Bitmap queue to free.
 420  */
 421 static inline void sbitmap_queue_free(struct sbitmap_queue *sbq)
 422 {
 423         kfree(sbq->ws);
 424         sbitmap_free(&sbq->sb);
 425 }
 426
 427 /**
 428  * sbitmap_queue_recalculate_wake_batch() - Recalculate wake batch
 429  * @sbq: Bitmap queue to recalculate wake batch.
 430  * @users: Number of shares.
 431  *
 432  * Like sbitmap_queue_update_wake_batch(), this will calculate wake batch
 433  * by depth. This interface is for HCTX shared tags or queue shared tags.
 434  */
 435 void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue *sbq,
 436                                             unsigned int users);
 437
 438 /**
 439  * sbitmap_queue_resize() - Resize a &struct sbitmap_queue.
 440  * @sbq: Bitmap queue to resize.
 441  * @depth: New number of bits to resize to.
 442  *
 443  * Like sbitmap_resize(), this doesn't reallocate anything. It has to do
 444  * some extra work on the &struct sbitmap_queue, so it's not safe to just
 445  * resize the underlying &struct sbitmap.
 446  */
 447 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth);
 448
 449 /**
 450  * __sbitmap_queue_get() - Try to allocate a free bit from a &struct
 451  * sbitmap_queue with preemption already disabled.
 452  * @sbq: Bitmap queue to allocate from.
 453  *
 454  * Return: Non-negative allocated bit number if successful, -1 otherwise.
 455  */
 456 int __sbitmap_queue_get(struct sbitmap_queue *sbq);
 457
 458 /**
 459  * __sbitmap_queue_get_batch() - Try to allocate a batch of free bits
 460  * @sbq: Bitmap queue to allocate from.
 461  * @nr_tags: number of tags requested
 462  * @offset: offset to add to returned bits
 463  *
 464  * Return: Mask of allocated tags, 0 if none are found. Each tag allocated is
 465  * a bit in the mask returned, and the caller must add @offset to the value to
 466  * get the absolute tag value.
 467  */
 468 unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
 469                                         unsigned int *offset);
 470
 471 /**
 472  * sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct
 473  * sbitmap_queue, limiting the depth used from each word, with preemption
 474  * already disabled.
 475  * @sbq: Bitmap queue to allocate from.
 476  * @shallow_depth: The maximum number of bits to allocate from a single word.
 477  * See sbitmap_get_shallow().
 478  *
 479  * If you call this, make sure to call sbitmap_queue_min_shallow_depth() after
 480  * initializing @sbq.
 481  *
 482  * Return: Non-negative allocated bit number if successful, -1 otherwise.
 483  */
 484 int sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
 485                               unsigned int shallow_depth);
 486
 487 /**
 488  * sbitmap_queue_get() - Try to allocate a free bit from a &struct
 489  * sbitmap_queue.
 490  * @sbq: Bitmap queue to allocate from.
 491  * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to
 492  *       sbitmap_queue_clear()).
 493  *
 494  * Return: Non-negative allocated bit number if successful, -1 otherwise.
 495  */
 496 static inline int sbitmap_queue_get(struct sbitmap_queue *sbq,
 497                                     unsigned int *cpu)
 498 {
 499         int nr;
 500
 501         *cpu = get_cpu();
 502         nr = __sbitmap_queue_get(sbq);
 503         put_cpu();
 504         return nr;
 505 }
 506
 507 /**
 508  * sbitmap_queue_min_shallow_depth() - Inform a &struct sbitmap_queue of the
 509  * minimum shallow depth that will be used.
 510  * @sbq: Bitmap queue in question.
 511  * @min_shallow_depth: The minimum shallow depth that will be passed to
 512  * sbitmap_queue_get_shallow() or __sbitmap_queue_get_shallow().
 513  *
 514  * sbitmap_queue_clear() batches wakeups as an optimization. The batch size
 515  * depends on the depth of the bitmap. Since the shallow allocation functions
 516  * effectively operate with a different depth, the shallow depth must be taken
 517  * into account when calculating the batch size. This function must be called
 518  * with the minimum shallow depth that will be used. Failure to do so can result
 519  * in missed wakeups.
 520  */
 521 void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq,
 522                                      unsigned int min_shallow_depth);
 523
 524 /**
 525  * sbitmap_queue_clear() - Free an allocated bit and wake up waiters on a
 526  * &struct sbitmap_queue.
 527  * @sbq: Bitmap to free from.
 528  * @nr: Bit number to free.
 529  * @cpu: CPU the bit was allocated on.
 530  */
 531 void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
 532                          unsigned int cpu);
 533
 534 /**
 535  * sbitmap_queue_clear_batch() - Free a batch of allocated bits
 536  * &struct sbitmap_queue.
 537  * @sbq: Bitmap to free from.
 538  * @offset: offset for each tag in array
 539  * @tags: array of tags
 540  * @nr_tags: number of tags in array
 541  */
 542 void sbitmap_queue_clear_batch(struct sbitmap_queue *sbq, int offset,
 543                                 int *tags, int nr_tags);
 544
 545 static inline int sbq_index_inc(int index)
 546 {
 547         return (index + 1) & (SBQ_WAIT_QUEUES - 1);
 548 }
 549
 550 static inline void sbq_index_atomic_inc(atomic_t *index)
 551 {
 552         int old = atomic_read(index);
 553         int new = sbq_index_inc(old);
 554         atomic_cmpxchg(index, old, new);
 555 }
 556
 557 /**
 558  * sbq_wait_ptr() - Get the next wait queue to use for a &struct
 559  * sbitmap_queue.
 560  * @sbq: Bitmap queue to wait on.
 561  * @wait_index: A counter per "user" of @sbq.
 562  */
 563 static inline struct sbq_wait_state *sbq_wait_ptr(struct sbitmap_queue *sbq,
 564                                                   atomic_t *wait_index)
 565 {
 566         struct sbq_wait_state *ws;
 567
 568         ws = &sbq->ws[atomic_read(wait_index)];
 569         sbq_index_atomic_inc(wait_index);
 570         return ws;
 571 }
 572
 573 /**
 574  * sbitmap_queue_wake_all() - Wake up everything waiting on a &struct
 575  * sbitmap_queue.
 576  * @sbq: Bitmap queue to wake up.
 577  */
 578 void sbitmap_queue_wake_all(struct sbitmap_queue *sbq);
 579
 580 /**
 581  * sbitmap_queue_wake_up() - Wake up some of waiters in one waitqueue
 582  * on a &struct sbitmap_queue.
 583  * @sbq: Bitmap queue to wake up.
 584  * @nr: Number of bits cleared.
 585  */
 586 void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr);
 587
 588 /**
 589  * sbitmap_queue_show() - Dump &struct sbitmap_queue information to a &struct
 590  * seq_file.
 591  * @sbq: Bitmap queue to show.
 592  * @m: struct seq_file to write to.
 593  *
 594  * This is intended for debugging. The format may change at any time.
 595  */
 596 void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m);
 597
 598 struct sbq_wait {
 599         struct sbitmap_queue *sbq;      /* if set, sbq_wait is accounted */
 600         struct wait_queue_entry wait;
 601 };
 602
 603 #define DEFINE_SBQ_WAIT(name)                                                   \
 604         struct sbq_wait name = {                                                \
 605                 .sbq = NULL,                                                    \
 606                 .wait = {                                                       \
 607                         .private        = current,                              \
 608                         .func           = autoremove_wake_function,             \
 609                         .entry          = LIST_HEAD_INIT((name).wait.entry),    \
 610                 }                                                               \
 611         }
 612
 613 /*
 614  * Wrapper around prepare_to_wait_exclusive(), which maintains some extra
 615  * internal state.
 616  */
 617 void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq,
 618                                 struct sbq_wait_state *ws,
 619                                 struct sbq_wait *sbq_wait, int state);
 620
 621 /*
 622  * Must be paired with sbitmap_prepare_to_wait().
 623  */
 624 void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws,
 625                                 struct sbq_wait *sbq_wait);
 626
 627 /*
 628  * Wrapper around add_wait_queue(), which maintains some extra internal state
 629  */
 630 void sbitmap_add_wait_queue(struct sbitmap_queue *sbq,
 631                             struct sbq_wait_state *ws,
 632                             struct sbq_wait *sbq_wait);
 633
 634 /*
 635  * Must be paired with sbitmap_add_wait_queue()
 636  */
 637 void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait);
 638
 639 #endif /* __LINUX_SCALE_BITMAP_H */