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