sbitmap.h 9.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374
  1. /*
  2. * Fast and scalable bitmaps.
  3. *
  4. * Copyright (C) 2016 Facebook
  5. * Copyright (C) 2013-2014 Jens Axboe
  6. *
  7. * This program is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU General Public
  9. * License v2 as published by the Free Software Foundation.
  10. *
  11. * This program is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14. * General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program. If not, see <https://www.gnu.org/licenses/>.
  18. */
  19. #ifndef __LINUX_SCALE_BITMAP_H
  20. #define __LINUX_SCALE_BITMAP_H
  21. #include <linux/kernel.h>
  22. #include <linux/slab.h>
  23. /**
  24. * struct sbitmap_word - Word in a &struct sbitmap.
  25. */
  26. struct sbitmap_word {
  27. /**
  28. * @word: The bitmap word itself.
  29. */
  30. unsigned long word;
  31. /**
  32. * @depth: Number of bits being used in @word.
  33. */
  34. unsigned long depth;
  35. } ____cacheline_aligned_in_smp;
  36. /**
  37. * struct sbitmap - Scalable bitmap.
  38. *
  39. * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This
  40. * trades off higher memory usage for better scalability.
  41. */
  42. struct sbitmap {
  43. /**
  44. * @depth: Number of bits used in the whole bitmap.
  45. */
  46. unsigned int depth;
  47. /**
  48. * @shift: log2(number of bits used per word)
  49. */
  50. unsigned int shift;
  51. /**
  52. * @map_nr: Number of words (cachelines) being used for the bitmap.
  53. */
  54. unsigned int map_nr;
  55. /**
  56. * @map: Allocated bitmap.
  57. */
  58. struct sbitmap_word *map;
  59. };
  60. #define SBQ_WAIT_QUEUES 8
  61. #define SBQ_WAKE_BATCH 8
  62. /**
  63. * struct sbq_wait_state - Wait queue in a &struct sbitmap_queue.
  64. */
  65. struct sbq_wait_state {
  66. /**
  67. * @wait_cnt: Number of frees remaining before we wake up.
  68. */
  69. atomic_t wait_cnt;
  70. /**
  71. * @wait: Wait queue.
  72. */
  73. wait_queue_head_t wait;
  74. } ____cacheline_aligned_in_smp;
  75. /**
  76. * struct sbitmap_queue - Scalable bitmap with the added ability to wait on free
  77. * bits.
  78. *
  79. * A &struct sbitmap_queue uses multiple wait queues and rolling wakeups to
  80. * avoid contention on the wait queue spinlock. This ensures that we don't hit a
  81. * scalability wall when we run out of free bits and have to start putting tasks
  82. * to sleep.
  83. */
  84. struct sbitmap_queue {
  85. /**
  86. * @sb: Scalable bitmap.
  87. */
  88. struct sbitmap sb;
  89. /*
  90. * @alloc_hint: Cache of last successfully allocated or freed bit.
  91. *
  92. * This is per-cpu, which allows multiple users to stick to different
  93. * cachelines until the map is exhausted.
  94. */
  95. unsigned int __percpu *alloc_hint;
  96. /**
  97. * @wake_batch: Number of bits which must be freed before we wake up any
  98. * waiters.
  99. */
  100. unsigned int wake_batch;
  101. /**
  102. * @wake_index: Next wait queue in @ws to wake up.
  103. */
  104. atomic_t wake_index;
  105. /**
  106. * @ws: Wait queues.
  107. */
  108. struct sbq_wait_state *ws;
  109. /**
  110. * @round_robin: Allocate bits in strict round-robin order.
  111. */
  112. bool round_robin;
  113. };
  114. /**
  115. * sbitmap_init_node() - Initialize a &struct sbitmap on a specific memory node.
  116. * @sb: Bitmap to initialize.
  117. * @depth: Number of bits to allocate.
  118. * @shift: Use 2^@shift bits per word in the bitmap; if a negative number if
  119. * given, a good default is chosen.
  120. * @flags: Allocation flags.
  121. * @node: Memory node to allocate on.
  122. *
  123. * Return: Zero on success or negative errno on failure.
  124. */
  125. int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
  126. gfp_t flags, int node);
  127. /**
  128. * sbitmap_free() - Free memory used by a &struct sbitmap.
  129. * @sb: Bitmap to free.
  130. */
  131. static inline void sbitmap_free(struct sbitmap *sb)
  132. {
  133. kfree(sb->map);
  134. sb->map = NULL;
  135. }
  136. /**
  137. * sbitmap_resize() - Resize a &struct sbitmap.
  138. * @sb: Bitmap to resize.
  139. * @depth: New number of bits to resize to.
  140. *
  141. * Doesn't reallocate anything. It's up to the caller to ensure that the new
  142. * depth doesn't exceed the depth that the sb was initialized with.
  143. */
  144. void sbitmap_resize(struct sbitmap *sb, unsigned int depth);
  145. /**
  146. * sbitmap_get() - Try to allocate a free bit from a &struct sbitmap.
  147. * @sb: Bitmap to allocate from.
  148. * @alloc_hint: Hint for where to start searching for a free bit.
  149. * @round_robin: If true, be stricter about allocation order; always allocate
  150. * starting from the last allocated bit. This is less efficient
  151. * than the default behavior (false).
  152. *
  153. * Return: Non-negative allocated bit number if successful, -1 otherwise.
  154. */
  155. int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin);
  156. /**
  157. * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap.
  158. * @sb: Bitmap to check.
  159. *
  160. * Return: true if any bit in the bitmap is set, false otherwise.
  161. */
  162. bool sbitmap_any_bit_set(const struct sbitmap *sb);
  163. /**
  164. * sbitmap_any_bit_clear() - Check for an unset bit in a &struct
  165. * sbitmap.
  166. * @sb: Bitmap to check.
  167. *
  168. * Return: true if any bit in the bitmap is clear, false otherwise.
  169. */
  170. bool sbitmap_any_bit_clear(const struct sbitmap *sb);
  171. typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
  172. /**
  173. * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
  174. * @sb: Bitmap to iterate over.
  175. * @fn: Callback. Should return true to continue or false to break early.
  176. * @data: Pointer to pass to callback.
  177. *
  178. * This is inline even though it's non-trivial so that the function calls to the
  179. * callback will hopefully get optimized away.
  180. */
  181. static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
  182. void *data)
  183. {
  184. unsigned int i;
  185. for (i = 0; i < sb->map_nr; i++) {
  186. struct sbitmap_word *word = &sb->map[i];
  187. unsigned int off, nr;
  188. if (!word->word)
  189. continue;
  190. nr = 0;
  191. off = i << sb->shift;
  192. while (1) {
  193. nr = find_next_bit(&word->word, word->depth, nr);
  194. if (nr >= word->depth)
  195. break;
  196. if (!fn(sb, off + nr, data))
  197. return;
  198. nr++;
  199. }
  200. }
  201. }
  202. #define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
  203. #define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
  204. static inline unsigned long *__sbitmap_word(struct sbitmap *sb,
  205. unsigned int bitnr)
  206. {
  207. return &sb->map[SB_NR_TO_INDEX(sb, bitnr)].word;
  208. }
  209. /* Helpers equivalent to the operations in asm/bitops.h and linux/bitmap.h */
  210. static inline void sbitmap_set_bit(struct sbitmap *sb, unsigned int bitnr)
  211. {
  212. set_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
  213. }
  214. static inline void sbitmap_clear_bit(struct sbitmap *sb, unsigned int bitnr)
  215. {
  216. clear_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
  217. }
  218. static inline int sbitmap_test_bit(struct sbitmap *sb, unsigned int bitnr)
  219. {
  220. return test_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
  221. }
  222. unsigned int sbitmap_weight(const struct sbitmap *sb);
  223. /**
  224. * sbitmap_queue_init_node() - Initialize a &struct sbitmap_queue on a specific
  225. * memory node.
  226. * @sbq: Bitmap queue to initialize.
  227. * @depth: See sbitmap_init_node().
  228. * @shift: See sbitmap_init_node().
  229. * @round_robin: See sbitmap_get().
  230. * @flags: Allocation flags.
  231. * @node: Memory node to allocate on.
  232. *
  233. * Return: Zero on success or negative errno on failure.
  234. */
  235. int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
  236. int shift, bool round_robin, gfp_t flags, int node);
  237. /**
  238. * sbitmap_queue_free() - Free memory used by a &struct sbitmap_queue.
  239. *
  240. * @sbq: Bitmap queue to free.
  241. */
  242. static inline void sbitmap_queue_free(struct sbitmap_queue *sbq)
  243. {
  244. kfree(sbq->ws);
  245. free_percpu(sbq->alloc_hint);
  246. sbitmap_free(&sbq->sb);
  247. }
  248. /**
  249. * sbitmap_queue_resize() - Resize a &struct sbitmap_queue.
  250. * @sbq: Bitmap queue to resize.
  251. * @depth: New number of bits to resize to.
  252. *
  253. * Like sbitmap_resize(), this doesn't reallocate anything. It has to do
  254. * some extra work on the &struct sbitmap_queue, so it's not safe to just
  255. * resize the underlying &struct sbitmap.
  256. */
  257. void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth);
  258. /**
  259. * __sbitmap_queue_get() - Try to allocate a free bit from a &struct
  260. * sbitmap_queue with preemption already disabled.
  261. * @sbq: Bitmap queue to allocate from.
  262. *
  263. * Return: Non-negative allocated bit number if successful, -1 otherwise.
  264. */
  265. int __sbitmap_queue_get(struct sbitmap_queue *sbq);
  266. /**
  267. * sbitmap_queue_get() - Try to allocate a free bit from a &struct
  268. * sbitmap_queue.
  269. * @sbq: Bitmap queue to allocate from.
  270. * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to
  271. * sbitmap_queue_clear()).
  272. *
  273. * Return: Non-negative allocated bit number if successful, -1 otherwise.
  274. */
  275. static inline int sbitmap_queue_get(struct sbitmap_queue *sbq,
  276. unsigned int *cpu)
  277. {
  278. int nr;
  279. *cpu = get_cpu();
  280. nr = __sbitmap_queue_get(sbq);
  281. put_cpu();
  282. return nr;
  283. }
  284. /**
  285. * sbitmap_queue_clear() - Free an allocated bit and wake up waiters on a
  286. * &struct sbitmap_queue.
  287. * @sbq: Bitmap to free from.
  288. * @nr: Bit number to free.
  289. * @cpu: CPU the bit was allocated on.
  290. */
  291. void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
  292. unsigned int cpu);
  293. static inline int sbq_index_inc(int index)
  294. {
  295. return (index + 1) & (SBQ_WAIT_QUEUES - 1);
  296. }
  297. static inline void sbq_index_atomic_inc(atomic_t *index)
  298. {
  299. int old = atomic_read(index);
  300. int new = sbq_index_inc(old);
  301. atomic_cmpxchg(index, old, new);
  302. }
  303. /**
  304. * sbq_wait_ptr() - Get the next wait queue to use for a &struct
  305. * sbitmap_queue.
  306. * @sbq: Bitmap queue to wait on.
  307. * @wait_index: A counter per "user" of @sbq.
  308. */
  309. static inline struct sbq_wait_state *sbq_wait_ptr(struct sbitmap_queue *sbq,
  310. atomic_t *wait_index)
  311. {
  312. struct sbq_wait_state *ws;
  313. ws = &sbq->ws[atomic_read(wait_index)];
  314. sbq_index_atomic_inc(wait_index);
  315. return ws;
  316. }
  317. /**
  318. * sbitmap_queue_wake_all() - Wake up everything waiting on a &struct
  319. * sbitmap_queue.
  320. * @sbq: Bitmap queue to wake up.
  321. */
  322. void sbitmap_queue_wake_all(struct sbitmap_queue *sbq);
  323. #endif /* __LINUX_SCALE_BITMAP_H */