sbitmap.h 16 KB

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