10fc479b1SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-only */
288459642SOmar Sandoval /*
388459642SOmar Sandoval * Fast and scalable bitmaps.
488459642SOmar Sandoval *
588459642SOmar Sandoval * Copyright (C) 2016 Facebook
688459642SOmar Sandoval * Copyright (C) 2013-2014 Jens Axboe
788459642SOmar Sandoval */
888459642SOmar Sandoval
988459642SOmar Sandoval #ifndef __LINUX_SCALE_BITMAP_H
1088459642SOmar Sandoval #define __LINUX_SCALE_BITMAP_H
1188459642SOmar Sandoval
121fcbd5deSAndy Shevchenko #include <linux/atomic.h>
131fcbd5deSAndy Shevchenko #include <linux/bitops.h>
141fcbd5deSAndy Shevchenko #include <linux/cache.h>
151fcbd5deSAndy Shevchenko #include <linux/list.h>
161fcbd5deSAndy Shevchenko #include <linux/log2.h>
171fcbd5deSAndy Shevchenko #include <linux/minmax.h>
181fcbd5deSAndy Shevchenko #include <linux/percpu.h>
1988459642SOmar Sandoval #include <linux/slab.h>
201fcbd5deSAndy Shevchenko #include <linux/smp.h>
211fcbd5deSAndy Shevchenko #include <linux/types.h>
221fcbd5deSAndy Shevchenko #include <linux/wait.h>
2388459642SOmar Sandoval
2414b470b5SArnd Bergmann struct seq_file;
2514b470b5SArnd Bergmann
2688459642SOmar Sandoval /**
2788459642SOmar Sandoval * struct sbitmap_word - Word in a &struct sbitmap.
2888459642SOmar Sandoval */
2988459642SOmar Sandoval struct sbitmap_word {
3088459642SOmar Sandoval /**
31ea86ea2cSJens Axboe * @word: word holding free bits
32ea86ea2cSJens Axboe */
333301bc53SMing Lei unsigned long word;
34ea86ea2cSJens Axboe
35ea86ea2cSJens Axboe /**
36ea86ea2cSJens Axboe * @cleared: word holding cleared bits
37ea86ea2cSJens Axboe */
38ea86ea2cSJens Axboe unsigned long cleared ____cacheline_aligned_in_smp;
3988459642SOmar Sandoval } ____cacheline_aligned_in_smp;
4088459642SOmar Sandoval
4188459642SOmar Sandoval /**
4288459642SOmar Sandoval * struct sbitmap - Scalable bitmap.
4388459642SOmar Sandoval *
4488459642SOmar Sandoval * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This
4588459642SOmar Sandoval * trades off higher memory usage for better scalability.
4688459642SOmar Sandoval */
4788459642SOmar Sandoval struct sbitmap {
4888459642SOmar Sandoval /**
4988459642SOmar Sandoval * @depth: Number of bits used in the whole bitmap.
5088459642SOmar Sandoval */
5188459642SOmar Sandoval unsigned int depth;
5288459642SOmar Sandoval
5388459642SOmar Sandoval /**
5488459642SOmar Sandoval * @shift: log2(number of bits used per word)
5588459642SOmar Sandoval */
5688459642SOmar Sandoval unsigned int shift;
5788459642SOmar Sandoval
5888459642SOmar Sandoval /**
5988459642SOmar Sandoval * @map_nr: Number of words (cachelines) being used for the bitmap.
6088459642SOmar Sandoval */
6188459642SOmar Sandoval unsigned int map_nr;
6288459642SOmar Sandoval
6388459642SOmar Sandoval /**
64efe1f3a1SMing Lei * @round_robin: Allocate bits in strict round-robin order.
65efe1f3a1SMing Lei */
66efe1f3a1SMing Lei bool round_robin;
67efe1f3a1SMing Lei
68efe1f3a1SMing Lei /**
6988459642SOmar Sandoval * @map: Allocated bitmap.
7088459642SOmar Sandoval */
7188459642SOmar Sandoval struct sbitmap_word *map;
72c548e62bSMing Lei
73c548e62bSMing Lei /*
74c548e62bSMing Lei * @alloc_hint: Cache of last successfully allocated or freed bit.
75c548e62bSMing Lei *
76c548e62bSMing Lei * This is per-cpu, which allows multiple users to stick to different
77c548e62bSMing Lei * cachelines until the map is exhausted.
78c548e62bSMing Lei */
79c548e62bSMing Lei unsigned int __percpu *alloc_hint;
8088459642SOmar Sandoval };
8188459642SOmar Sandoval
8288459642SOmar Sandoval #define SBQ_WAIT_QUEUES 8
8388459642SOmar Sandoval #define SBQ_WAKE_BATCH 8
8488459642SOmar Sandoval
8588459642SOmar Sandoval /**
8688459642SOmar Sandoval * struct sbq_wait_state - Wait queue in a &struct sbitmap_queue.
8788459642SOmar Sandoval */
8888459642SOmar Sandoval struct sbq_wait_state {
8988459642SOmar Sandoval /**
9088459642SOmar Sandoval * @wait: Wait queue.
9188459642SOmar Sandoval */
9288459642SOmar Sandoval wait_queue_head_t wait;
9388459642SOmar Sandoval } ____cacheline_aligned_in_smp;
9488459642SOmar Sandoval
9588459642SOmar Sandoval /**
9688459642SOmar Sandoval * struct sbitmap_queue - Scalable bitmap with the added ability to wait on free
9788459642SOmar Sandoval * bits.
9888459642SOmar Sandoval *
9988459642SOmar Sandoval * A &struct sbitmap_queue uses multiple wait queues and rolling wakeups to
10088459642SOmar Sandoval * avoid contention on the wait queue spinlock. This ensures that we don't hit a
10188459642SOmar Sandoval * scalability wall when we run out of free bits and have to start putting tasks
10288459642SOmar Sandoval * to sleep.
10388459642SOmar Sandoval */
10488459642SOmar Sandoval struct sbitmap_queue {
10588459642SOmar Sandoval /**
10688459642SOmar Sandoval * @sb: Scalable bitmap.
10788459642SOmar Sandoval */
10888459642SOmar Sandoval struct sbitmap sb;
10988459642SOmar Sandoval
11088459642SOmar Sandoval /**
11188459642SOmar Sandoval * @wake_batch: Number of bits which must be freed before we wake up any
11288459642SOmar Sandoval * waiters.
11388459642SOmar Sandoval */
11488459642SOmar Sandoval unsigned int wake_batch;
11588459642SOmar Sandoval
11688459642SOmar Sandoval /**
11788459642SOmar Sandoval * @wake_index: Next wait queue in @ws to wake up.
11888459642SOmar Sandoval */
11988459642SOmar Sandoval atomic_t wake_index;
12088459642SOmar Sandoval
12188459642SOmar Sandoval /**
12288459642SOmar Sandoval * @ws: Wait queues.
12388459642SOmar Sandoval */
12488459642SOmar Sandoval struct sbq_wait_state *ws;
125f4a644dbSOmar Sandoval
1265d2ee712SJens Axboe /*
1275d2ee712SJens Axboe * @ws_active: count of currently active ws waitqueues
1285d2ee712SJens Axboe */
1295d2ee712SJens Axboe atomic_t ws_active;
1305d2ee712SJens Axboe
131f4a644dbSOmar Sandoval /**
132a3275539SOmar Sandoval * @min_shallow_depth: The minimum shallow depth which may be passed to
1333f607293SJohn Garry * sbitmap_queue_get_shallow()
134a3275539SOmar Sandoval */
135a3275539SOmar Sandoval unsigned int min_shallow_depth;
136*4f8126bbSGabriel Krisman Bertazi
137*4f8126bbSGabriel Krisman Bertazi /**
138*4f8126bbSGabriel Krisman Bertazi * @completion_cnt: Number of bits cleared passed to the
139*4f8126bbSGabriel Krisman Bertazi * wakeup function.
140*4f8126bbSGabriel Krisman Bertazi */
141*4f8126bbSGabriel Krisman Bertazi atomic_t completion_cnt;
142*4f8126bbSGabriel Krisman Bertazi
143*4f8126bbSGabriel Krisman Bertazi /**
144*4f8126bbSGabriel Krisman Bertazi * @wakeup_cnt: Number of thread wake ups issued.
145*4f8126bbSGabriel Krisman Bertazi */
146*4f8126bbSGabriel Krisman Bertazi atomic_t wakeup_cnt;
14788459642SOmar Sandoval };
14888459642SOmar Sandoval
14988459642SOmar Sandoval /**
15088459642SOmar Sandoval * sbitmap_init_node() - Initialize a &struct sbitmap on a specific memory node.
15188459642SOmar Sandoval * @sb: Bitmap to initialize.
15288459642SOmar Sandoval * @depth: Number of bits to allocate.
15388459642SOmar Sandoval * @shift: Use 2^@shift bits per word in the bitmap; if a negative number if
15488459642SOmar Sandoval * given, a good default is chosen.
15588459642SOmar Sandoval * @flags: Allocation flags.
15688459642SOmar Sandoval * @node: Memory node to allocate on.
157efe1f3a1SMing Lei * @round_robin: If true, be stricter about allocation order; always allocate
158efe1f3a1SMing Lei * starting from the last allocated bit. This is less efficient
159efe1f3a1SMing Lei * than the default behavior (false).
160c548e62bSMing Lei * @alloc_hint: If true, apply percpu hint for where to start searching for
161c548e62bSMing Lei * a free bit.
16288459642SOmar Sandoval *
16388459642SOmar Sandoval * Return: Zero on success or negative errno on failure.
16488459642SOmar Sandoval */
16588459642SOmar Sandoval int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
166c548e62bSMing Lei gfp_t flags, int node, bool round_robin, bool alloc_hint);
16788459642SOmar Sandoval
1683301bc53SMing Lei /* sbitmap internal helper */
__map_depth(const struct sbitmap * sb,int index)1693301bc53SMing Lei static inline unsigned int __map_depth(const struct sbitmap *sb, int index)
1703301bc53SMing Lei {
1713301bc53SMing Lei if (index == sb->map_nr - 1)
1723301bc53SMing Lei return sb->depth - (index << sb->shift);
1733301bc53SMing Lei return 1U << sb->shift;
1743301bc53SMing Lei }
1753301bc53SMing Lei
17688459642SOmar Sandoval /**
17788459642SOmar Sandoval * sbitmap_free() - Free memory used by a &struct sbitmap.
17888459642SOmar Sandoval * @sb: Bitmap to free.
17988459642SOmar Sandoval */
sbitmap_free(struct sbitmap * sb)18088459642SOmar Sandoval static inline void sbitmap_free(struct sbitmap *sb)
18188459642SOmar Sandoval {
182c548e62bSMing Lei free_percpu(sb->alloc_hint);
183863a66cdSMing Lei kvfree(sb->map);
18488459642SOmar Sandoval sb->map = NULL;
18588459642SOmar Sandoval }
18688459642SOmar Sandoval
18788459642SOmar Sandoval /**
18888459642SOmar Sandoval * sbitmap_resize() - Resize a &struct sbitmap.
18988459642SOmar Sandoval * @sb: Bitmap to resize.
19088459642SOmar Sandoval * @depth: New number of bits to resize to.
19188459642SOmar Sandoval *
19288459642SOmar Sandoval * Doesn't reallocate anything. It's up to the caller to ensure that the new
19388459642SOmar Sandoval * depth doesn't exceed the depth that the sb was initialized with.
19488459642SOmar Sandoval */
19588459642SOmar Sandoval void sbitmap_resize(struct sbitmap *sb, unsigned int depth);
19688459642SOmar Sandoval
19788459642SOmar Sandoval /**
19888459642SOmar Sandoval * sbitmap_get() - Try to allocate a free bit from a &struct sbitmap.
19988459642SOmar Sandoval * @sb: Bitmap to allocate from.
20088459642SOmar Sandoval *
2014ace53f1SOmar Sandoval * This operation provides acquire barrier semantics if it succeeds.
2024ace53f1SOmar Sandoval *
20388459642SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise.
20488459642SOmar Sandoval */
205c548e62bSMing Lei int sbitmap_get(struct sbitmap *sb);
20688459642SOmar Sandoval
20788459642SOmar Sandoval /**
208c05e6673SOmar Sandoval * sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap,
209c05e6673SOmar Sandoval * limiting the depth used from each word.
210c05e6673SOmar Sandoval * @sb: Bitmap to allocate from.
211c05e6673SOmar Sandoval * @shallow_depth: The maximum number of bits to allocate from a single word.
212c05e6673SOmar Sandoval *
213c05e6673SOmar Sandoval * This rather specific operation allows for having multiple users with
214c05e6673SOmar Sandoval * different allocation limits. E.g., there can be a high-priority class that
215c05e6673SOmar Sandoval * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
216c05e6673SOmar Sandoval * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
217c05e6673SOmar Sandoval * class can only allocate half of the total bits in the bitmap, preventing it
218c05e6673SOmar Sandoval * from starving out the high-priority class.
219c05e6673SOmar Sandoval *
220c05e6673SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise.
221c05e6673SOmar Sandoval */
222c548e62bSMing Lei int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth);
223c05e6673SOmar Sandoval
224c05e6673SOmar Sandoval /**
22588459642SOmar Sandoval * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap.
22688459642SOmar Sandoval * @sb: Bitmap to check.
22788459642SOmar Sandoval *
22888459642SOmar Sandoval * Return: true if any bit in the bitmap is set, false otherwise.
22988459642SOmar Sandoval */
23088459642SOmar Sandoval bool sbitmap_any_bit_set(const struct sbitmap *sb);
23188459642SOmar Sandoval
2327930d0a0SMing Lei #define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
2337930d0a0SMing Lei #define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
2347930d0a0SMing Lei
23588459642SOmar Sandoval typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
23688459642SOmar Sandoval
23788459642SOmar Sandoval /**
2387930d0a0SMing Lei * __sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
2397930d0a0SMing Lei * @start: Where to start the iteration.
24088459642SOmar Sandoval * @sb: Bitmap to iterate over.
24188459642SOmar Sandoval * @fn: Callback. Should return true to continue or false to break early.
24288459642SOmar Sandoval * @data: Pointer to pass to callback.
24388459642SOmar Sandoval *
24488459642SOmar Sandoval * This is inline even though it's non-trivial so that the function calls to the
24588459642SOmar Sandoval * callback will hopefully get optimized away.
24688459642SOmar Sandoval */
__sbitmap_for_each_set(struct sbitmap * sb,unsigned int start,sb_for_each_fn fn,void * data)2477930d0a0SMing Lei static inline void __sbitmap_for_each_set(struct sbitmap *sb,
2487930d0a0SMing Lei unsigned int start,
2497930d0a0SMing Lei sb_for_each_fn fn, void *data)
25088459642SOmar Sandoval {
2517930d0a0SMing Lei unsigned int index;
2527930d0a0SMing Lei unsigned int nr;
2537930d0a0SMing Lei unsigned int scanned = 0;
25488459642SOmar Sandoval
2557930d0a0SMing Lei if (start >= sb->depth)
2567930d0a0SMing Lei start = 0;
2577930d0a0SMing Lei index = SB_NR_TO_INDEX(sb, start);
2587930d0a0SMing Lei nr = SB_NR_TO_BIT(sb, start);
25988459642SOmar Sandoval
2607930d0a0SMing Lei while (scanned < sb->depth) {
2618c2def89SOmar Sandoval unsigned long word;
2628c2def89SOmar Sandoval unsigned int depth = min_t(unsigned int,
2633301bc53SMing Lei __map_depth(sb, index) - nr,
2647930d0a0SMing Lei sb->depth - scanned);
2657930d0a0SMing Lei
2667930d0a0SMing Lei scanned += depth;
2678c2def89SOmar Sandoval word = sb->map[index].word & ~sb->map[index].cleared;
2688c2def89SOmar Sandoval if (!word)
2697930d0a0SMing Lei goto next;
27088459642SOmar Sandoval
2717930d0a0SMing Lei /*
2727930d0a0SMing Lei * On the first iteration of the outer loop, we need to add the
2737930d0a0SMing Lei * bit offset back to the size of the word for find_next_bit().
2747930d0a0SMing Lei * On all other iterations, nr is zero, so this is a noop.
2757930d0a0SMing Lei */
2767930d0a0SMing Lei depth += nr;
27788459642SOmar Sandoval while (1) {
2788c2def89SOmar Sandoval nr = find_next_bit(&word, depth, nr);
2797930d0a0SMing Lei if (nr >= depth)
28088459642SOmar Sandoval break;
2817930d0a0SMing Lei if (!fn(sb, (index << sb->shift) + nr, data))
28288459642SOmar Sandoval return;
28388459642SOmar Sandoval
28488459642SOmar Sandoval nr++;
28588459642SOmar Sandoval }
2867930d0a0SMing Lei next:
2877930d0a0SMing Lei nr = 0;
2887930d0a0SMing Lei if (++index >= sb->map_nr)
2897930d0a0SMing Lei index = 0;
29088459642SOmar Sandoval }
29188459642SOmar Sandoval }
29288459642SOmar Sandoval
2937930d0a0SMing Lei /**
2947930d0a0SMing Lei * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
2957930d0a0SMing Lei * @sb: Bitmap to iterate over.
2967930d0a0SMing Lei * @fn: Callback. Should return true to continue or false to break early.
2977930d0a0SMing Lei * @data: Pointer to pass to callback.
2987930d0a0SMing Lei */
sbitmap_for_each_set(struct sbitmap * sb,sb_for_each_fn fn,void * data)2997930d0a0SMing Lei static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
3007930d0a0SMing Lei void *data)
3017930d0a0SMing Lei {
3027930d0a0SMing Lei __sbitmap_for_each_set(sb, 0, fn, data);
3037930d0a0SMing Lei }
30488459642SOmar Sandoval
__sbitmap_word(struct sbitmap * sb,unsigned int bitnr)30588459642SOmar Sandoval static inline unsigned long *__sbitmap_word(struct sbitmap *sb,
30688459642SOmar Sandoval unsigned int bitnr)
30788459642SOmar Sandoval {
30888459642SOmar Sandoval return &sb->map[SB_NR_TO_INDEX(sb, bitnr)].word;
30988459642SOmar Sandoval }
31088459642SOmar Sandoval
31188459642SOmar Sandoval /* Helpers equivalent to the operations in asm/bitops.h and linux/bitmap.h */
31288459642SOmar Sandoval
sbitmap_set_bit(struct sbitmap * sb,unsigned int bitnr)31388459642SOmar Sandoval static inline void sbitmap_set_bit(struct sbitmap *sb, unsigned int bitnr)
31488459642SOmar Sandoval {
31588459642SOmar Sandoval set_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
31688459642SOmar Sandoval }
31788459642SOmar Sandoval
sbitmap_clear_bit(struct sbitmap * sb,unsigned int bitnr)31888459642SOmar Sandoval static inline void sbitmap_clear_bit(struct sbitmap *sb, unsigned int bitnr)
31988459642SOmar Sandoval {
32088459642SOmar Sandoval clear_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
32188459642SOmar Sandoval }
32288459642SOmar Sandoval
323ea86ea2cSJens Axboe /*
324ea86ea2cSJens Axboe * This one is special, since it doesn't actually clear the bit, rather it
325ea86ea2cSJens Axboe * sets the corresponding bit in the ->cleared mask instead. Paired with
3261e4471e7SShenghui Wang * the caller doing sbitmap_deferred_clear() if a given index is full, which
327ea86ea2cSJens Axboe * will clear the previously freed entries in the corresponding ->word.
328ea86ea2cSJens Axboe */
sbitmap_deferred_clear_bit(struct sbitmap * sb,unsigned int bitnr)329ea86ea2cSJens Axboe static inline void sbitmap_deferred_clear_bit(struct sbitmap *sb, unsigned int bitnr)
330ea86ea2cSJens Axboe {
331ea86ea2cSJens Axboe unsigned long *addr = &sb->map[SB_NR_TO_INDEX(sb, bitnr)].cleared;
332ea86ea2cSJens Axboe
333ea86ea2cSJens Axboe set_bit(SB_NR_TO_BIT(sb, bitnr), addr);
334ea86ea2cSJens Axboe }
335ea86ea2cSJens Axboe
336c548e62bSMing Lei /*
337c548e62bSMing Lei * Pair of sbitmap_get, and this one applies both cleared bit and
338c548e62bSMing Lei * allocation hint.
339c548e62bSMing Lei */
sbitmap_put(struct sbitmap * sb,unsigned int bitnr)340c548e62bSMing Lei static inline void sbitmap_put(struct sbitmap *sb, unsigned int bitnr)
341c548e62bSMing Lei {
342c548e62bSMing Lei sbitmap_deferred_clear_bit(sb, bitnr);
343c548e62bSMing Lei
344c548e62bSMing Lei if (likely(sb->alloc_hint && !sb->round_robin && bitnr < sb->depth))
345035e9f47SBart Van Assche *raw_cpu_ptr(sb->alloc_hint) = bitnr;
346c548e62bSMing Lei }
347c548e62bSMing Lei
sbitmap_test_bit(struct sbitmap * sb,unsigned int bitnr)34888459642SOmar Sandoval static inline int sbitmap_test_bit(struct sbitmap *sb, unsigned int bitnr)
34988459642SOmar Sandoval {
35088459642SOmar Sandoval return test_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
35188459642SOmar Sandoval }
35288459642SOmar Sandoval
sbitmap_calculate_shift(unsigned int depth)3532d13b1eaSMing Lei static inline int sbitmap_calculate_shift(unsigned int depth)
3542d13b1eaSMing Lei {
3552d13b1eaSMing Lei int shift = ilog2(BITS_PER_LONG);
3562d13b1eaSMing Lei
3572d13b1eaSMing Lei /*
3582d13b1eaSMing Lei * If the bitmap is small, shrink the number of bits per word so
3592d13b1eaSMing Lei * we spread over a few cachelines, at least. If less than 4
3602d13b1eaSMing Lei * bits, just forget about it, it's not going to work optimally
3612d13b1eaSMing Lei * anyway.
3622d13b1eaSMing Lei */
3632d13b1eaSMing Lei if (depth >= 4) {
3642d13b1eaSMing Lei while ((4U << shift) > depth)
3652d13b1eaSMing Lei shift--;
3662d13b1eaSMing Lei }
3672d13b1eaSMing Lei
3682d13b1eaSMing Lei return shift;
3692d13b1eaSMing Lei }
3702d13b1eaSMing Lei
37188459642SOmar Sandoval /**
37224af1ccfSOmar Sandoval * sbitmap_show() - Dump &struct sbitmap information to a &struct seq_file.
37324af1ccfSOmar Sandoval * @sb: Bitmap to show.
37424af1ccfSOmar Sandoval * @m: struct seq_file to write to.
37524af1ccfSOmar Sandoval *
37624af1ccfSOmar Sandoval * This is intended for debugging. The format may change at any time.
37724af1ccfSOmar Sandoval */
37824af1ccfSOmar Sandoval void sbitmap_show(struct sbitmap *sb, struct seq_file *m);
37924af1ccfSOmar Sandoval
380cbb9950bSMing Lei
381cbb9950bSMing Lei /**
382cbb9950bSMing Lei * sbitmap_weight() - Return how many set and not cleared bits in a &struct
383cbb9950bSMing Lei * sbitmap.
384cbb9950bSMing Lei * @sb: Bitmap to check.
385cbb9950bSMing Lei *
386cbb9950bSMing Lei * Return: How many set and not cleared bits set
387cbb9950bSMing Lei */
388cbb9950bSMing Lei unsigned int sbitmap_weight(const struct sbitmap *sb);
389cbb9950bSMing Lei
39024af1ccfSOmar Sandoval /**
39124af1ccfSOmar Sandoval * sbitmap_bitmap_show() - Write a hex dump of a &struct sbitmap to a &struct
39224af1ccfSOmar Sandoval * seq_file.
39324af1ccfSOmar Sandoval * @sb: Bitmap to show.
39424af1ccfSOmar Sandoval * @m: struct seq_file to write to.
39524af1ccfSOmar Sandoval *
39624af1ccfSOmar Sandoval * This is intended for debugging. The output isn't guaranteed to be internally
39724af1ccfSOmar Sandoval * consistent.
39824af1ccfSOmar Sandoval */
39924af1ccfSOmar Sandoval void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m);
40024af1ccfSOmar Sandoval
40124af1ccfSOmar Sandoval /**
40288459642SOmar Sandoval * sbitmap_queue_init_node() - Initialize a &struct sbitmap_queue on a specific
40388459642SOmar Sandoval * memory node.
40488459642SOmar Sandoval * @sbq: Bitmap queue to initialize.
40588459642SOmar Sandoval * @depth: See sbitmap_init_node().
40688459642SOmar Sandoval * @shift: See sbitmap_init_node().
407f4a644dbSOmar Sandoval * @round_robin: See sbitmap_get().
40888459642SOmar Sandoval * @flags: Allocation flags.
40988459642SOmar Sandoval * @node: Memory node to allocate on.
41088459642SOmar Sandoval *
41188459642SOmar Sandoval * Return: Zero on success or negative errno on failure.
41288459642SOmar Sandoval */
41388459642SOmar Sandoval int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
414f4a644dbSOmar Sandoval int shift, bool round_robin, gfp_t flags, int node);
41588459642SOmar Sandoval
41688459642SOmar Sandoval /**
41788459642SOmar Sandoval * sbitmap_queue_free() - Free memory used by a &struct sbitmap_queue.
41888459642SOmar Sandoval *
41988459642SOmar Sandoval * @sbq: Bitmap queue to free.
42088459642SOmar Sandoval */
sbitmap_queue_free(struct sbitmap_queue * sbq)42188459642SOmar Sandoval static inline void sbitmap_queue_free(struct sbitmap_queue *sbq)
42288459642SOmar Sandoval {
42388459642SOmar Sandoval kfree(sbq->ws);
42488459642SOmar Sandoval sbitmap_free(&sbq->sb);
42588459642SOmar Sandoval }
42688459642SOmar Sandoval
42788459642SOmar Sandoval /**
428180dccb0SLaibin Qiu * sbitmap_queue_recalculate_wake_batch() - Recalculate wake batch
429180dccb0SLaibin Qiu * @sbq: Bitmap queue to recalculate wake batch.
430180dccb0SLaibin Qiu * @users: Number of shares.
431180dccb0SLaibin Qiu *
432180dccb0SLaibin Qiu * Like sbitmap_queue_update_wake_batch(), this will calculate wake batch
433180dccb0SLaibin Qiu * by depth. This interface is for HCTX shared tags or queue shared tags.
434180dccb0SLaibin Qiu */
435180dccb0SLaibin Qiu void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue *sbq,
436180dccb0SLaibin Qiu unsigned int users);
437180dccb0SLaibin Qiu
438180dccb0SLaibin Qiu /**
43988459642SOmar Sandoval * sbitmap_queue_resize() - Resize a &struct sbitmap_queue.
44088459642SOmar Sandoval * @sbq: Bitmap queue to resize.
44188459642SOmar Sandoval * @depth: New number of bits to resize to.
44288459642SOmar Sandoval *
44388459642SOmar Sandoval * Like sbitmap_resize(), this doesn't reallocate anything. It has to do
44488459642SOmar Sandoval * some extra work on the &struct sbitmap_queue, so it's not safe to just
44588459642SOmar Sandoval * resize the underlying &struct sbitmap.
44688459642SOmar Sandoval */
44788459642SOmar Sandoval void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth);
44888459642SOmar Sandoval
44988459642SOmar Sandoval /**
45040aabb67SOmar Sandoval * __sbitmap_queue_get() - Try to allocate a free bit from a &struct
45140aabb67SOmar Sandoval * sbitmap_queue with preemption already disabled.
45240aabb67SOmar Sandoval * @sbq: Bitmap queue to allocate from.
45340aabb67SOmar Sandoval *
45440aabb67SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise.
45540aabb67SOmar Sandoval */
456f4a644dbSOmar Sandoval int __sbitmap_queue_get(struct sbitmap_queue *sbq);
45740aabb67SOmar Sandoval
45840aabb67SOmar Sandoval /**
4599672b0d4SJens Axboe * __sbitmap_queue_get_batch() - Try to allocate a batch of free bits
4609672b0d4SJens Axboe * @sbq: Bitmap queue to allocate from.
4619672b0d4SJens Axboe * @nr_tags: number of tags requested
4629672b0d4SJens Axboe * @offset: offset to add to returned bits
4639672b0d4SJens Axboe *
4649672b0d4SJens Axboe * Return: Mask of allocated tags, 0 if none are found. Each tag allocated is
4659672b0d4SJens Axboe * a bit in the mask returned, and the caller must add @offset to the value to
4669672b0d4SJens Axboe * get the absolute tag value.
4679672b0d4SJens Axboe */
4689672b0d4SJens Axboe unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
4699672b0d4SJens Axboe unsigned int *offset);
4709672b0d4SJens Axboe
4719672b0d4SJens Axboe /**
4723f607293SJohn Garry * sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct
473c05e6673SOmar Sandoval * sbitmap_queue, limiting the depth used from each word, with preemption
474c05e6673SOmar Sandoval * already disabled.
475c05e6673SOmar Sandoval * @sbq: Bitmap queue to allocate from.
476c05e6673SOmar Sandoval * @shallow_depth: The maximum number of bits to allocate from a single word.
477c05e6673SOmar Sandoval * See sbitmap_get_shallow().
478c05e6673SOmar Sandoval *
479a3275539SOmar Sandoval * If you call this, make sure to call sbitmap_queue_min_shallow_depth() after
480a3275539SOmar Sandoval * initializing @sbq.
481a3275539SOmar Sandoval *
482c05e6673SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise.
483c05e6673SOmar Sandoval */
4843f607293SJohn Garry int sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
485c05e6673SOmar Sandoval unsigned int shallow_depth);
486c05e6673SOmar Sandoval
487c05e6673SOmar Sandoval /**
48840aabb67SOmar Sandoval * sbitmap_queue_get() - Try to allocate a free bit from a &struct
48940aabb67SOmar Sandoval * sbitmap_queue.
49040aabb67SOmar Sandoval * @sbq: Bitmap queue to allocate from.
49140aabb67SOmar Sandoval * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to
49240aabb67SOmar Sandoval * sbitmap_queue_clear()).
49340aabb67SOmar Sandoval *
49440aabb67SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise.
49540aabb67SOmar Sandoval */
sbitmap_queue_get(struct sbitmap_queue * sbq,unsigned int * cpu)496f4a644dbSOmar Sandoval static inline int sbitmap_queue_get(struct sbitmap_queue *sbq,
49740aabb67SOmar Sandoval unsigned int *cpu)
49840aabb67SOmar Sandoval {
49940aabb67SOmar Sandoval int nr;
50040aabb67SOmar Sandoval
50140aabb67SOmar Sandoval *cpu = get_cpu();
502f4a644dbSOmar Sandoval nr = __sbitmap_queue_get(sbq);
50340aabb67SOmar Sandoval put_cpu();
50440aabb67SOmar Sandoval return nr;
50540aabb67SOmar Sandoval }
50640aabb67SOmar Sandoval
50740aabb67SOmar Sandoval /**
508a3275539SOmar Sandoval * sbitmap_queue_min_shallow_depth() - Inform a &struct sbitmap_queue of the
509a3275539SOmar Sandoval * minimum shallow depth that will be used.
510a3275539SOmar Sandoval * @sbq: Bitmap queue in question.
511a3275539SOmar Sandoval * @min_shallow_depth: The minimum shallow depth that will be passed to
512a3275539SOmar Sandoval * sbitmap_queue_get_shallow() or __sbitmap_queue_get_shallow().
513a3275539SOmar Sandoval *
514a3275539SOmar Sandoval * sbitmap_queue_clear() batches wakeups as an optimization. The batch size
515a3275539SOmar Sandoval * depends on the depth of the bitmap. Since the shallow allocation functions
516a3275539SOmar Sandoval * effectively operate with a different depth, the shallow depth must be taken
517a3275539SOmar Sandoval * into account when calculating the batch size. This function must be called
518a3275539SOmar Sandoval * with the minimum shallow depth that will be used. Failure to do so can result
519a3275539SOmar Sandoval * in missed wakeups.
520a3275539SOmar Sandoval */
521a3275539SOmar Sandoval void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq,
522a3275539SOmar Sandoval unsigned int min_shallow_depth);
523a3275539SOmar Sandoval
524a3275539SOmar Sandoval /**
52588459642SOmar Sandoval * sbitmap_queue_clear() - Free an allocated bit and wake up waiters on a
52688459642SOmar Sandoval * &struct sbitmap_queue.
52788459642SOmar Sandoval * @sbq: Bitmap to free from.
52888459642SOmar Sandoval * @nr: Bit number to free.
52940aabb67SOmar Sandoval * @cpu: CPU the bit was allocated on.
53088459642SOmar Sandoval */
53140aabb67SOmar Sandoval void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
532f4a644dbSOmar Sandoval unsigned int cpu);
53388459642SOmar Sandoval
5341aec5e4aSJens Axboe /**
5351aec5e4aSJens Axboe * sbitmap_queue_clear_batch() - Free a batch of allocated bits
5361aec5e4aSJens Axboe * &struct sbitmap_queue.
5371aec5e4aSJens Axboe * @sbq: Bitmap to free from.
5381aec5e4aSJens Axboe * @offset: offset for each tag in array
5391aec5e4aSJens Axboe * @tags: array of tags
5401aec5e4aSJens Axboe * @nr_tags: number of tags in array
5411aec5e4aSJens Axboe */
5421aec5e4aSJens Axboe void sbitmap_queue_clear_batch(struct sbitmap_queue *sbq, int offset,
5431aec5e4aSJens Axboe int *tags, int nr_tags);
5441aec5e4aSJens Axboe
sbq_index_inc(int index)54588459642SOmar Sandoval static inline int sbq_index_inc(int index)
54688459642SOmar Sandoval {
54788459642SOmar Sandoval return (index + 1) & (SBQ_WAIT_QUEUES - 1);
54888459642SOmar Sandoval }
54988459642SOmar Sandoval
sbq_index_atomic_inc(atomic_t * index)55088459642SOmar Sandoval static inline void sbq_index_atomic_inc(atomic_t *index)
55188459642SOmar Sandoval {
55288459642SOmar Sandoval int old = atomic_read(index);
55388459642SOmar Sandoval int new = sbq_index_inc(old);
55488459642SOmar Sandoval atomic_cmpxchg(index, old, new);
55588459642SOmar Sandoval }
55688459642SOmar Sandoval
55788459642SOmar Sandoval /**
55888459642SOmar Sandoval * sbq_wait_ptr() - Get the next wait queue to use for a &struct
55988459642SOmar Sandoval * sbitmap_queue.
56088459642SOmar Sandoval * @sbq: Bitmap queue to wait on.
56188459642SOmar Sandoval * @wait_index: A counter per "user" of @sbq.
56288459642SOmar Sandoval */
sbq_wait_ptr(struct sbitmap_queue * sbq,atomic_t * wait_index)56388459642SOmar Sandoval static inline struct sbq_wait_state *sbq_wait_ptr(struct sbitmap_queue *sbq,
56488459642SOmar Sandoval atomic_t *wait_index)
56588459642SOmar Sandoval {
56688459642SOmar Sandoval struct sbq_wait_state *ws;
56788459642SOmar Sandoval
56888459642SOmar Sandoval ws = &sbq->ws[atomic_read(wait_index)];
56988459642SOmar Sandoval sbq_index_atomic_inc(wait_index);
57088459642SOmar Sandoval return ws;
57188459642SOmar Sandoval }
57288459642SOmar Sandoval
57388459642SOmar Sandoval /**
57488459642SOmar Sandoval * sbitmap_queue_wake_all() - Wake up everything waiting on a &struct
57588459642SOmar Sandoval * sbitmap_queue.
57688459642SOmar Sandoval * @sbq: Bitmap queue to wake up.
57788459642SOmar Sandoval */
57888459642SOmar Sandoval void sbitmap_queue_wake_all(struct sbitmap_queue *sbq);
57988459642SOmar Sandoval
58024af1ccfSOmar Sandoval /**
581e6fc4649SMing Lei * sbitmap_queue_wake_up() - Wake up some of waiters in one waitqueue
582e6fc4649SMing Lei * on a &struct sbitmap_queue.
583e6fc4649SMing Lei * @sbq: Bitmap queue to wake up.
5844acb8341SKeith Busch * @nr: Number of bits cleared.
585e6fc4649SMing Lei */
5864acb8341SKeith Busch void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr);
587e6fc4649SMing Lei
588e6fc4649SMing Lei /**
58924af1ccfSOmar Sandoval * sbitmap_queue_show() - Dump &struct sbitmap_queue information to a &struct
59024af1ccfSOmar Sandoval * seq_file.
59124af1ccfSOmar Sandoval * @sbq: Bitmap queue to show.
59224af1ccfSOmar Sandoval * @m: struct seq_file to write to.
59324af1ccfSOmar Sandoval *
59424af1ccfSOmar Sandoval * This is intended for debugging. The format may change at any time.
59524af1ccfSOmar Sandoval */
59624af1ccfSOmar Sandoval void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m);
59724af1ccfSOmar Sandoval
5985d2ee712SJens Axboe struct sbq_wait {
5999f6b7ef6SJens Axboe struct sbitmap_queue *sbq; /* if set, sbq_wait is accounted */
6005d2ee712SJens Axboe struct wait_queue_entry wait;
6015d2ee712SJens Axboe };
6025d2ee712SJens Axboe
6035d2ee712SJens Axboe #define DEFINE_SBQ_WAIT(name) \
6045d2ee712SJens Axboe struct sbq_wait name = { \
6059f6b7ef6SJens Axboe .sbq = NULL, \
6065d2ee712SJens Axboe .wait = { \
6075d2ee712SJens Axboe .private = current, \
6085d2ee712SJens Axboe .func = autoremove_wake_function, \
6095d2ee712SJens Axboe .entry = LIST_HEAD_INIT((name).wait.entry), \
6105d2ee712SJens Axboe } \
6115d2ee712SJens Axboe }
6125d2ee712SJens Axboe
6135d2ee712SJens Axboe /*
6145d2ee712SJens Axboe * Wrapper around prepare_to_wait_exclusive(), which maintains some extra
6155d2ee712SJens Axboe * internal state.
6165d2ee712SJens Axboe */
6175d2ee712SJens Axboe void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq,
6185d2ee712SJens Axboe struct sbq_wait_state *ws,
6195d2ee712SJens Axboe struct sbq_wait *sbq_wait, int state);
6205d2ee712SJens Axboe
6215d2ee712SJens Axboe /*
6225d2ee712SJens Axboe * Must be paired with sbitmap_prepare_to_wait().
6235d2ee712SJens Axboe */
6245d2ee712SJens Axboe void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws,
6255d2ee712SJens Axboe struct sbq_wait *sbq_wait);
6265d2ee712SJens Axboe
6279f6b7ef6SJens Axboe /*
6289f6b7ef6SJens Axboe * Wrapper around add_wait_queue(), which maintains some extra internal state
6299f6b7ef6SJens Axboe */
6309f6b7ef6SJens Axboe void sbitmap_add_wait_queue(struct sbitmap_queue *sbq,
6319f6b7ef6SJens Axboe struct sbq_wait_state *ws,
6329f6b7ef6SJens Axboe struct sbq_wait *sbq_wait);
6339f6b7ef6SJens Axboe
6349f6b7ef6SJens Axboe /*
6359f6b7ef6SJens Axboe * Must be paired with sbitmap_add_wait_queue()
6369f6b7ef6SJens Axboe */
6379f6b7ef6SJens Axboe void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait);
6389f6b7ef6SJens Axboe
63988459642SOmar Sandoval #endif /* __LINUX_SCALE_BITMAP_H */
640