10fc479b1SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only
288459642SOmar Sandoval /*
388459642SOmar Sandoval * Copyright (C) 2016 Facebook
488459642SOmar Sandoval * Copyright (C) 2013-2014 Jens Axboe
588459642SOmar Sandoval */
688459642SOmar Sandoval
7af8601adSIngo Molnar #include <linux/sched.h>
898d95416SOmar Sandoval #include <linux/random.h>
988459642SOmar Sandoval #include <linux/sbitmap.h>
1024af1ccfSOmar Sandoval #include <linux/seq_file.h>
1188459642SOmar Sandoval
init_alloc_hint(struct sbitmap * sb,gfp_t flags)12c548e62bSMing Lei static int init_alloc_hint(struct sbitmap *sb, gfp_t flags)
13bf2c4282SMing Lei {
14c548e62bSMing Lei unsigned depth = sb->depth;
15bf2c4282SMing Lei
16c548e62bSMing Lei sb->alloc_hint = alloc_percpu_gfp(unsigned int, flags);
17c548e62bSMing Lei if (!sb->alloc_hint)
18bf2c4282SMing Lei return -ENOMEM;
19bf2c4282SMing Lei
20c548e62bSMing Lei if (depth && !sb->round_robin) {
21bf2c4282SMing Lei int i;
22bf2c4282SMing Lei
23bf2c4282SMing Lei for_each_possible_cpu(i)
248032bf12SJason A. Donenfeld *per_cpu_ptr(sb->alloc_hint, i) = get_random_u32_below(depth);
25bf2c4282SMing Lei }
26bf2c4282SMing Lei return 0;
27bf2c4282SMing Lei }
28bf2c4282SMing Lei
update_alloc_hint_before_get(struct sbitmap * sb,unsigned int depth)29c548e62bSMing Lei static inline unsigned update_alloc_hint_before_get(struct sbitmap *sb,
30bf2c4282SMing Lei unsigned int depth)
31bf2c4282SMing Lei {
32bf2c4282SMing Lei unsigned hint;
33bf2c4282SMing Lei
34c548e62bSMing Lei hint = this_cpu_read(*sb->alloc_hint);
35bf2c4282SMing Lei if (unlikely(hint >= depth)) {
368032bf12SJason A. Donenfeld hint = depth ? get_random_u32_below(depth) : 0;
37c548e62bSMing Lei this_cpu_write(*sb->alloc_hint, hint);
38bf2c4282SMing Lei }
39bf2c4282SMing Lei
40bf2c4282SMing Lei return hint;
41bf2c4282SMing Lei }
42bf2c4282SMing Lei
update_alloc_hint_after_get(struct sbitmap * sb,unsigned int depth,unsigned int hint,unsigned int nr)43c548e62bSMing Lei static inline void update_alloc_hint_after_get(struct sbitmap *sb,
44bf2c4282SMing Lei unsigned int depth,
45bf2c4282SMing Lei unsigned int hint,
46bf2c4282SMing Lei unsigned int nr)
47bf2c4282SMing Lei {
48bf2c4282SMing Lei if (nr == -1) {
49bf2c4282SMing Lei /* If the map is full, a hint won't do us much good. */
50c548e62bSMing Lei this_cpu_write(*sb->alloc_hint, 0);
51c548e62bSMing Lei } else if (nr == hint || unlikely(sb->round_robin)) {
52bf2c4282SMing Lei /* Only update the hint if we used it. */
53bf2c4282SMing Lei hint = nr + 1;
54bf2c4282SMing Lei if (hint >= depth - 1)
55bf2c4282SMing Lei hint = 0;
56c548e62bSMing Lei this_cpu_write(*sb->alloc_hint, hint);
57bf2c4282SMing Lei }
58bf2c4282SMing Lei }
59bf2c4282SMing Lei
60b2dbff1bSJens Axboe /*
61b2dbff1bSJens Axboe * See if we have deferred clears that we can batch move
62b2dbff1bSJens Axboe */
sbitmap_deferred_clear(struct sbitmap_word * map,unsigned int depth,unsigned int alloc_hint,bool wrap)6372d04bdcSYang Yang static inline bool sbitmap_deferred_clear(struct sbitmap_word *map,
6472d04bdcSYang Yang unsigned int depth, unsigned int alloc_hint, bool wrap)
65b2dbff1bSJens Axboe {
6672d04bdcSYang Yang unsigned long mask, word_mask;
67b2dbff1bSJens Axboe
68*65f666c6SMing Lei guard(raw_spinlock_irqsave)(&map->swap_lock);
6972d04bdcSYang Yang
7072d04bdcSYang Yang if (!map->cleared) {
7172d04bdcSYang Yang if (depth == 0)
72661d4f55SPavel Begunkov return false;
73b2dbff1bSJens Axboe
7472d04bdcSYang Yang word_mask = (~0UL) >> (BITS_PER_LONG - depth);
7572d04bdcSYang Yang /*
7672d04bdcSYang Yang * The current behavior is to always retry after moving
7772d04bdcSYang Yang * ->cleared to word, and we change it to retry in case
7872d04bdcSYang Yang * of any free bits. To avoid an infinite loop, we need
7972d04bdcSYang Yang * to take wrap & alloc_hint into account, otherwise a
8072d04bdcSYang Yang * soft lockup may occur.
8172d04bdcSYang Yang */
8272d04bdcSYang Yang if (!wrap && alloc_hint)
8372d04bdcSYang Yang word_mask &= ~((1UL << alloc_hint) - 1);
8472d04bdcSYang Yang
8572d04bdcSYang Yang return (READ_ONCE(map->word) & word_mask) != word_mask;
8672d04bdcSYang Yang }
8772d04bdcSYang Yang
88b2dbff1bSJens Axboe /*
89b2dbff1bSJens Axboe * First get a stable cleared mask, setting the old mask to 0.
90b2dbff1bSJens Axboe */
91b78beea0SPavel Begunkov mask = xchg(&map->cleared, 0);
92b2dbff1bSJens Axboe
93b2dbff1bSJens Axboe /*
94b2dbff1bSJens Axboe * Now clear the masked bits in our free word
95b2dbff1bSJens Axboe */
96c3250c8dSPavel Begunkov atomic_long_andnot(mask, (atomic_long_t *)&map->word);
97c3250c8dSPavel Begunkov BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word));
98661d4f55SPavel Begunkov return true;
99b2dbff1bSJens Axboe }
100b2dbff1bSJens Axboe
sbitmap_init_node(struct sbitmap * sb,unsigned int depth,int shift,gfp_t flags,int node,bool round_robin,bool alloc_hint)10188459642SOmar Sandoval int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
102c548e62bSMing Lei gfp_t flags, int node, bool round_robin,
103c548e62bSMing Lei bool alloc_hint)
10488459642SOmar Sandoval {
10588459642SOmar Sandoval unsigned int bits_per_word;
10672d04bdcSYang Yang int i;
10788459642SOmar Sandoval
1082d13b1eaSMing Lei if (shift < 0)
1092d13b1eaSMing Lei shift = sbitmap_calculate_shift(depth);
1102d13b1eaSMing Lei
11188459642SOmar Sandoval bits_per_word = 1U << shift;
11288459642SOmar Sandoval if (bits_per_word > BITS_PER_LONG)
11388459642SOmar Sandoval return -EINVAL;
11488459642SOmar Sandoval
11588459642SOmar Sandoval sb->shift = shift;
11688459642SOmar Sandoval sb->depth = depth;
11788459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
118efe1f3a1SMing Lei sb->round_robin = round_robin;
11988459642SOmar Sandoval
12088459642SOmar Sandoval if (depth == 0) {
12188459642SOmar Sandoval sb->map = NULL;
12288459642SOmar Sandoval return 0;
12388459642SOmar Sandoval }
12488459642SOmar Sandoval
125c548e62bSMing Lei if (alloc_hint) {
126c548e62bSMing Lei if (init_alloc_hint(sb, flags))
12788459642SOmar Sandoval return -ENOMEM;
128c548e62bSMing Lei } else {
129c548e62bSMing Lei sb->alloc_hint = NULL;
130c548e62bSMing Lei }
131c548e62bSMing Lei
132863a66cdSMing Lei sb->map = kvzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node);
133c548e62bSMing Lei if (!sb->map) {
134c548e62bSMing Lei free_percpu(sb->alloc_hint);
135c548e62bSMing Lei return -ENOMEM;
136c548e62bSMing Lei }
13788459642SOmar Sandoval
13872d04bdcSYang Yang for (i = 0; i < sb->map_nr; i++)
139*65f666c6SMing Lei raw_spin_lock_init(&sb->map[i].swap_lock);
14072d04bdcSYang Yang
14188459642SOmar Sandoval return 0;
14288459642SOmar Sandoval }
14388459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_init_node);
14488459642SOmar Sandoval
sbitmap_resize(struct sbitmap * sb,unsigned int depth)14588459642SOmar Sandoval void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
14688459642SOmar Sandoval {
14788459642SOmar Sandoval unsigned int bits_per_word = 1U << sb->shift;
14888459642SOmar Sandoval unsigned int i;
14988459642SOmar Sandoval
150b2dbff1bSJens Axboe for (i = 0; i < sb->map_nr; i++)
15172d04bdcSYang Yang sbitmap_deferred_clear(&sb->map[i], 0, 0, 0);
152b2dbff1bSJens Axboe
15388459642SOmar Sandoval sb->depth = depth;
15488459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
15588459642SOmar Sandoval }
15688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_resize);
15788459642SOmar Sandoval
__sbitmap_get_word(unsigned long * word,unsigned long depth,unsigned int hint,bool wrap)158c05e6673SOmar Sandoval static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
159c05e6673SOmar Sandoval unsigned int hint, bool wrap)
16088459642SOmar Sandoval {
16188459642SOmar Sandoval int nr;
16288459642SOmar Sandoval
1630eff1f1aSPavel Begunkov /* don't wrap if starting from 0 */
1640eff1f1aSPavel Begunkov wrap = wrap && hint;
1650eff1f1aSPavel Begunkov
16688459642SOmar Sandoval while (1) {
167c05e6673SOmar Sandoval nr = find_next_zero_bit(word, depth, hint);
168c05e6673SOmar Sandoval if (unlikely(nr >= depth)) {
16988459642SOmar Sandoval /*
17088459642SOmar Sandoval * We started with an offset, and we didn't reset the
17188459642SOmar Sandoval * offset to 0 in a failure case, so start from 0 to
17288459642SOmar Sandoval * exhaust the map.
17388459642SOmar Sandoval */
1740eff1f1aSPavel Begunkov if (hint && wrap) {
1750eff1f1aSPavel Begunkov hint = 0;
17688459642SOmar Sandoval continue;
17788459642SOmar Sandoval }
17888459642SOmar Sandoval return -1;
17988459642SOmar Sandoval }
18088459642SOmar Sandoval
1814ace53f1SOmar Sandoval if (!test_and_set_bit_lock(nr, word))
18288459642SOmar Sandoval break;
18388459642SOmar Sandoval
18488459642SOmar Sandoval hint = nr + 1;
185c05e6673SOmar Sandoval if (hint >= depth - 1)
18688459642SOmar Sandoval hint = 0;
18788459642SOmar Sandoval }
18888459642SOmar Sandoval
18988459642SOmar Sandoval return nr;
19088459642SOmar Sandoval }
19188459642SOmar Sandoval
sbitmap_find_bit_in_word(struct sbitmap_word * map,unsigned int depth,unsigned int alloc_hint,bool wrap)19208470a98SKemeng Shi static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
19308470a98SKemeng Shi unsigned int depth,
19408470a98SKemeng Shi unsigned int alloc_hint,
19508470a98SKemeng Shi bool wrap)
196ea86ea2cSJens Axboe {
197ea86ea2cSJens Axboe int nr;
198ea86ea2cSJens Axboe
199ea86ea2cSJens Axboe do {
20008470a98SKemeng Shi nr = __sbitmap_get_word(&map->word, depth,
20108470a98SKemeng Shi alloc_hint, wrap);
202ea86ea2cSJens Axboe if (nr != -1)
203ea86ea2cSJens Axboe break;
20472d04bdcSYang Yang if (!sbitmap_deferred_clear(map, depth, alloc_hint, wrap))
205ea86ea2cSJens Axboe break;
206ea86ea2cSJens Axboe } while (1);
207ea86ea2cSJens Axboe
208ea86ea2cSJens Axboe return nr;
209ea86ea2cSJens Axboe }
210ea86ea2cSJens Axboe
sbitmap_find_bit(struct sbitmap * sb,unsigned int depth,unsigned int index,unsigned int alloc_hint,bool wrap)211678418c6SKemeng Shi static int sbitmap_find_bit(struct sbitmap *sb,
212678418c6SKemeng Shi unsigned int depth,
213678418c6SKemeng Shi unsigned int index,
214678418c6SKemeng Shi unsigned int alloc_hint,
215678418c6SKemeng Shi bool wrap)
216678418c6SKemeng Shi {
217678418c6SKemeng Shi unsigned int i;
218678418c6SKemeng Shi int nr = -1;
219678418c6SKemeng Shi
220678418c6SKemeng Shi for (i = 0; i < sb->map_nr; i++) {
221678418c6SKemeng Shi nr = sbitmap_find_bit_in_word(&sb->map[index],
222678418c6SKemeng Shi min_t(unsigned int,
223678418c6SKemeng Shi __map_depth(sb, index),
224678418c6SKemeng Shi depth),
225678418c6SKemeng Shi alloc_hint, wrap);
226678418c6SKemeng Shi
227678418c6SKemeng Shi if (nr != -1) {
228678418c6SKemeng Shi nr += index << sb->shift;
229678418c6SKemeng Shi break;
230678418c6SKemeng Shi }
231678418c6SKemeng Shi
232678418c6SKemeng Shi /* Jump to next index. */
233678418c6SKemeng Shi alloc_hint = 0;
234678418c6SKemeng Shi if (++index >= sb->map_nr)
235678418c6SKemeng Shi index = 0;
236678418c6SKemeng Shi }
237678418c6SKemeng Shi
238678418c6SKemeng Shi return nr;
239678418c6SKemeng Shi }
240678418c6SKemeng Shi
__sbitmap_get(struct sbitmap * sb,unsigned int alloc_hint)241c548e62bSMing Lei static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
24288459642SOmar Sandoval {
243678418c6SKemeng Shi unsigned int index;
24488459642SOmar Sandoval
24588459642SOmar Sandoval index = SB_NR_TO_INDEX(sb, alloc_hint);
24688459642SOmar Sandoval
24727fae429SJens Axboe /*
24827fae429SJens Axboe * Unless we're doing round robin tag allocation, just use the
24927fae429SJens Axboe * alloc_hint to find the right word index. No point in looping
25027fae429SJens Axboe * twice in find_next_zero_bit() for that case.
25127fae429SJens Axboe */
252efe1f3a1SMing Lei if (sb->round_robin)
25327fae429SJens Axboe alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
25427fae429SJens Axboe else
25527fae429SJens Axboe alloc_hint = 0;
25627fae429SJens Axboe
257678418c6SKemeng Shi return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
258678418c6SKemeng Shi !sb->round_robin);
25988459642SOmar Sandoval }
260c548e62bSMing Lei
sbitmap_get(struct sbitmap * sb)261c548e62bSMing Lei int sbitmap_get(struct sbitmap *sb)
262c548e62bSMing Lei {
263c548e62bSMing Lei int nr;
264c548e62bSMing Lei unsigned int hint, depth;
265c548e62bSMing Lei
266c548e62bSMing Lei if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))
267c548e62bSMing Lei return -1;
268c548e62bSMing Lei
269c548e62bSMing Lei depth = READ_ONCE(sb->depth);
270c548e62bSMing Lei hint = update_alloc_hint_before_get(sb, depth);
271c548e62bSMing Lei nr = __sbitmap_get(sb, hint);
272c548e62bSMing Lei update_alloc_hint_after_get(sb, depth, hint, nr);
273c548e62bSMing Lei
274c548e62bSMing Lei return nr;
275c548e62bSMing Lei }
27688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_get);
27788459642SOmar Sandoval
__sbitmap_get_shallow(struct sbitmap * sb,unsigned int alloc_hint,unsigned long shallow_depth)278c548e62bSMing Lei static int __sbitmap_get_shallow(struct sbitmap *sb,
279c548e62bSMing Lei unsigned int alloc_hint,
280c05e6673SOmar Sandoval unsigned long shallow_depth)
281c05e6673SOmar Sandoval {
282678418c6SKemeng Shi unsigned int index;
283c05e6673SOmar Sandoval
284c05e6673SOmar Sandoval index = SB_NR_TO_INDEX(sb, alloc_hint);
285f1591a8bSKemeng Shi alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
286c05e6673SOmar Sandoval
287678418c6SKemeng Shi return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
288c05e6673SOmar Sandoval }
289c548e62bSMing Lei
sbitmap_get_shallow(struct sbitmap * sb,unsigned long shallow_depth)290c548e62bSMing Lei int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
291c548e62bSMing Lei {
292c548e62bSMing Lei int nr;
293c548e62bSMing Lei unsigned int hint, depth;
294c548e62bSMing Lei
295c548e62bSMing Lei if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))
296c548e62bSMing Lei return -1;
297c548e62bSMing Lei
298c548e62bSMing Lei depth = READ_ONCE(sb->depth);
299c548e62bSMing Lei hint = update_alloc_hint_before_get(sb, depth);
300c548e62bSMing Lei nr = __sbitmap_get_shallow(sb, hint, shallow_depth);
301c548e62bSMing Lei update_alloc_hint_after_get(sb, depth, hint, nr);
302c548e62bSMing Lei
303c548e62bSMing Lei return nr;
304c548e62bSMing Lei }
305c05e6673SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_get_shallow);
306c05e6673SOmar Sandoval
sbitmap_any_bit_set(const struct sbitmap * sb)30788459642SOmar Sandoval bool sbitmap_any_bit_set(const struct sbitmap *sb)
30888459642SOmar Sandoval {
30988459642SOmar Sandoval unsigned int i;
31088459642SOmar Sandoval
31188459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) {
312b2dbff1bSJens Axboe if (sb->map[i].word & ~sb->map[i].cleared)
31388459642SOmar Sandoval return true;
31488459642SOmar Sandoval }
31588459642SOmar Sandoval return false;
31688459642SOmar Sandoval }
31788459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_any_bit_set);
31888459642SOmar Sandoval
__sbitmap_weight(const struct sbitmap * sb,bool set)319ea86ea2cSJens Axboe static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)
32088459642SOmar Sandoval {
32160658e0dSColin Ian King unsigned int i, weight = 0;
32288459642SOmar Sandoval
32388459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) {
32488459642SOmar Sandoval const struct sbitmap_word *word = &sb->map[i];
3253301bc53SMing Lei unsigned int word_depth = __map_depth(sb, i);
32688459642SOmar Sandoval
327ea86ea2cSJens Axboe if (set)
3283301bc53SMing Lei weight += bitmap_weight(&word->word, word_depth);
329ea86ea2cSJens Axboe else
3303301bc53SMing Lei weight += bitmap_weight(&word->cleared, word_depth);
33188459642SOmar Sandoval }
33288459642SOmar Sandoval return weight;
33388459642SOmar Sandoval }
334ea86ea2cSJens Axboe
sbitmap_cleared(const struct sbitmap * sb)335ea86ea2cSJens Axboe static unsigned int sbitmap_cleared(const struct sbitmap *sb)
336ea86ea2cSJens Axboe {
337ea86ea2cSJens Axboe return __sbitmap_weight(sb, false);
338ea86ea2cSJens Axboe }
33988459642SOmar Sandoval
sbitmap_weight(const struct sbitmap * sb)340cbb9950bSMing Lei unsigned int sbitmap_weight(const struct sbitmap *sb)
341cbb9950bSMing Lei {
342cbb9950bSMing Lei return __sbitmap_weight(sb, true) - sbitmap_cleared(sb);
343cbb9950bSMing Lei }
344cbb9950bSMing Lei EXPORT_SYMBOL_GPL(sbitmap_weight);
345cbb9950bSMing Lei
sbitmap_show(struct sbitmap * sb,struct seq_file * m)34624af1ccfSOmar Sandoval void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
34724af1ccfSOmar Sandoval {
34824af1ccfSOmar Sandoval seq_printf(m, "depth=%u\n", sb->depth);
349cbb9950bSMing Lei seq_printf(m, "busy=%u\n", sbitmap_weight(sb));
350ea86ea2cSJens Axboe seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb));
35124af1ccfSOmar Sandoval seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);
35224af1ccfSOmar Sandoval seq_printf(m, "map_nr=%u\n", sb->map_nr);
35324af1ccfSOmar Sandoval }
35424af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_show);
35524af1ccfSOmar Sandoval
emit_byte(struct seq_file * m,unsigned int offset,u8 byte)35624af1ccfSOmar Sandoval static inline void emit_byte(struct seq_file *m, unsigned int offset, u8 byte)
35724af1ccfSOmar Sandoval {
35824af1ccfSOmar Sandoval if ((offset & 0xf) == 0) {
35924af1ccfSOmar Sandoval if (offset != 0)
36024af1ccfSOmar Sandoval seq_putc(m, '\n');
36124af1ccfSOmar Sandoval seq_printf(m, "%08x:", offset);
36224af1ccfSOmar Sandoval }
36324af1ccfSOmar Sandoval if ((offset & 0x1) == 0)
36424af1ccfSOmar Sandoval seq_putc(m, ' ');
36524af1ccfSOmar Sandoval seq_printf(m, "%02x", byte);
36624af1ccfSOmar Sandoval }
36724af1ccfSOmar Sandoval
sbitmap_bitmap_show(struct sbitmap * sb,struct seq_file * m)36824af1ccfSOmar Sandoval void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m)
36924af1ccfSOmar Sandoval {
37024af1ccfSOmar Sandoval u8 byte = 0;
37124af1ccfSOmar Sandoval unsigned int byte_bits = 0;
37224af1ccfSOmar Sandoval unsigned int offset = 0;
37324af1ccfSOmar Sandoval int i;
37424af1ccfSOmar Sandoval
37524af1ccfSOmar Sandoval for (i = 0; i < sb->map_nr; i++) {
37624af1ccfSOmar Sandoval unsigned long word = READ_ONCE(sb->map[i].word);
3776bf0eb55SJohn Garry unsigned long cleared = READ_ONCE(sb->map[i].cleared);
3783301bc53SMing Lei unsigned int word_bits = __map_depth(sb, i);
37924af1ccfSOmar Sandoval
3806bf0eb55SJohn Garry word &= ~cleared;
3816bf0eb55SJohn Garry
38224af1ccfSOmar Sandoval while (word_bits > 0) {
38324af1ccfSOmar Sandoval unsigned int bits = min(8 - byte_bits, word_bits);
38424af1ccfSOmar Sandoval
38524af1ccfSOmar Sandoval byte |= (word & (BIT(bits) - 1)) << byte_bits;
38624af1ccfSOmar Sandoval byte_bits += bits;
38724af1ccfSOmar Sandoval if (byte_bits == 8) {
38824af1ccfSOmar Sandoval emit_byte(m, offset, byte);
38924af1ccfSOmar Sandoval byte = 0;
39024af1ccfSOmar Sandoval byte_bits = 0;
39124af1ccfSOmar Sandoval offset++;
39224af1ccfSOmar Sandoval }
39324af1ccfSOmar Sandoval word >>= bits;
39424af1ccfSOmar Sandoval word_bits -= bits;
39524af1ccfSOmar Sandoval }
39624af1ccfSOmar Sandoval }
39724af1ccfSOmar Sandoval if (byte_bits) {
39824af1ccfSOmar Sandoval emit_byte(m, offset, byte);
39924af1ccfSOmar Sandoval offset++;
40024af1ccfSOmar Sandoval }
40124af1ccfSOmar Sandoval if (offset)
40224af1ccfSOmar Sandoval seq_putc(m, '\n');
40324af1ccfSOmar Sandoval }
40424af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_bitmap_show);
40524af1ccfSOmar Sandoval
sbq_calc_wake_batch(struct sbitmap_queue * sbq,unsigned int depth)406a3275539SOmar Sandoval static unsigned int sbq_calc_wake_batch(struct sbitmap_queue *sbq,
407a3275539SOmar Sandoval unsigned int depth)
40888459642SOmar Sandoval {
40988459642SOmar Sandoval unsigned int wake_batch;
410a3275539SOmar Sandoval unsigned int shallow_depth;
41188459642SOmar Sandoval
41288459642SOmar Sandoval /*
413a3275539SOmar Sandoval * Each full word of the bitmap has bits_per_word bits, and there might
414a3275539SOmar Sandoval * be a partial word. There are depth / bits_per_word full words and
415a3275539SOmar Sandoval * depth % bits_per_word bits left over. In bitwise arithmetic:
416a3275539SOmar Sandoval *
417a3275539SOmar Sandoval * bits_per_word = 1 << shift
418a3275539SOmar Sandoval * depth / bits_per_word = depth >> shift
419a3275539SOmar Sandoval * depth % bits_per_word = depth & ((1 << shift) - 1)
420a3275539SOmar Sandoval *
421a3275539SOmar Sandoval * Each word can be limited to sbq->min_shallow_depth bits.
42288459642SOmar Sandoval */
423a3275539SOmar Sandoval shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth);
424a3275539SOmar Sandoval depth = ((depth >> sbq->sb.shift) * shallow_depth +
425a3275539SOmar Sandoval min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth));
426a3275539SOmar Sandoval wake_batch = clamp_t(unsigned int, depth / SBQ_WAIT_QUEUES, 1,
427a3275539SOmar Sandoval SBQ_WAKE_BATCH);
42888459642SOmar Sandoval
42988459642SOmar Sandoval return wake_batch;
43088459642SOmar Sandoval }
43188459642SOmar Sandoval
sbitmap_queue_init_node(struct sbitmap_queue * sbq,unsigned int depth,int shift,bool round_robin,gfp_t flags,int node)43288459642SOmar Sandoval int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
433f4a644dbSOmar Sandoval int shift, bool round_robin, gfp_t flags, int node)
43488459642SOmar Sandoval {
43588459642SOmar Sandoval int ret;
43688459642SOmar Sandoval int i;
43788459642SOmar Sandoval
438efe1f3a1SMing Lei ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node,
439c548e62bSMing Lei round_robin, true);
44088459642SOmar Sandoval if (ret)
44188459642SOmar Sandoval return ret;
44288459642SOmar Sandoval
443a3275539SOmar Sandoval sbq->min_shallow_depth = UINT_MAX;
444a3275539SOmar Sandoval sbq->wake_batch = sbq_calc_wake_batch(sbq, depth);
44588459642SOmar Sandoval atomic_set(&sbq->wake_index, 0);
4465d2ee712SJens Axboe atomic_set(&sbq->ws_active, 0);
4474f8126bbSGabriel Krisman Bertazi atomic_set(&sbq->completion_cnt, 0);
4484f8126bbSGabriel Krisman Bertazi atomic_set(&sbq->wakeup_cnt, 0);
44988459642SOmar Sandoval
45048e28166SOmar Sandoval sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node);
45188459642SOmar Sandoval if (!sbq->ws) {
45288459642SOmar Sandoval sbitmap_free(&sbq->sb);
45388459642SOmar Sandoval return -ENOMEM;
45488459642SOmar Sandoval }
45588459642SOmar Sandoval
4564f8126bbSGabriel Krisman Bertazi for (i = 0; i < SBQ_WAIT_QUEUES; i++)
45788459642SOmar Sandoval init_waitqueue_head(&sbq->ws[i].wait);
458f4a644dbSOmar Sandoval
45988459642SOmar Sandoval return 0;
46088459642SOmar Sandoval }
46188459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);
46288459642SOmar Sandoval
sbitmap_queue_update_wake_batch(struct sbitmap_queue * sbq,unsigned int depth)463180dccb0SLaibin Qiu static void sbitmap_queue_update_wake_batch(struct sbitmap_queue *sbq,
464180dccb0SLaibin Qiu unsigned int depth)
465180dccb0SLaibin Qiu {
466180dccb0SLaibin Qiu unsigned int wake_batch;
467180dccb0SLaibin Qiu
468180dccb0SLaibin Qiu wake_batch = sbq_calc_wake_batch(sbq, depth);
4694f8126bbSGabriel Krisman Bertazi if (sbq->wake_batch != wake_batch)
4704f8126bbSGabriel Krisman Bertazi WRITE_ONCE(sbq->wake_batch, wake_batch);
471180dccb0SLaibin Qiu }
472180dccb0SLaibin Qiu
sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue * sbq,unsigned int users)473180dccb0SLaibin Qiu void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue *sbq,
474180dccb0SLaibin Qiu unsigned int users)
475180dccb0SLaibin Qiu {
476180dccb0SLaibin Qiu unsigned int wake_batch;
47710825410SLaibin Qiu unsigned int depth = (sbq->sb.depth + users - 1) / users;
478180dccb0SLaibin Qiu
47910825410SLaibin Qiu wake_batch = clamp_val(depth / SBQ_WAIT_QUEUES,
480b5fcf787SKemeng Shi 1, SBQ_WAKE_BATCH);
4814f8126bbSGabriel Krisman Bertazi
4824f8126bbSGabriel Krisman Bertazi WRITE_ONCE(sbq->wake_batch, wake_batch);
483180dccb0SLaibin Qiu }
484180dccb0SLaibin Qiu EXPORT_SYMBOL_GPL(sbitmap_queue_recalculate_wake_batch);
485180dccb0SLaibin Qiu
sbitmap_queue_resize(struct sbitmap_queue * sbq,unsigned int depth)486a3275539SOmar Sandoval void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth)
487a3275539SOmar Sandoval {
488a3275539SOmar Sandoval sbitmap_queue_update_wake_batch(sbq, depth);
48988459642SOmar Sandoval sbitmap_resize(&sbq->sb, depth);
49088459642SOmar Sandoval }
49188459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
49288459642SOmar Sandoval
__sbitmap_queue_get(struct sbitmap_queue * sbq)493f4a644dbSOmar Sandoval int __sbitmap_queue_get(struct sbitmap_queue *sbq)
49440aabb67SOmar Sandoval {
495c548e62bSMing Lei return sbitmap_get(&sbq->sb);
49640aabb67SOmar Sandoval }
49740aabb67SOmar Sandoval EXPORT_SYMBOL_GPL(__sbitmap_queue_get);
49840aabb67SOmar Sandoval
__sbitmap_queue_get_batch(struct sbitmap_queue * sbq,int nr_tags,unsigned int * offset)4999672b0d4SJens Axboe unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags,
5009672b0d4SJens Axboe unsigned int *offset)
5019672b0d4SJens Axboe {
5029672b0d4SJens Axboe struct sbitmap *sb = &sbq->sb;
5039672b0d4SJens Axboe unsigned int hint, depth;
5049672b0d4SJens Axboe unsigned long index, nr;
5059672b0d4SJens Axboe int i;
5069672b0d4SJens Axboe
5079672b0d4SJens Axboe if (unlikely(sb->round_robin))
5089672b0d4SJens Axboe return 0;
5099672b0d4SJens Axboe
5109672b0d4SJens Axboe depth = READ_ONCE(sb->depth);
5119672b0d4SJens Axboe hint = update_alloc_hint_before_get(sb, depth);
5129672b0d4SJens Axboe
5139672b0d4SJens Axboe index = SB_NR_TO_INDEX(sb, hint);
5149672b0d4SJens Axboe
5159672b0d4SJens Axboe for (i = 0; i < sb->map_nr; i++) {
5169672b0d4SJens Axboe struct sbitmap_word *map = &sb->map[index];
5179672b0d4SJens Axboe unsigned long get_mask;
5183301bc53SMing Lei unsigned int map_depth = __map_depth(sb, index);
519c35227d4SUros Bizjak unsigned long val;
5209672b0d4SJens Axboe
52172d04bdcSYang Yang sbitmap_deferred_clear(map, 0, 0, 0);
5229672b0d4SJens Axboe val = READ_ONCE(map->word);
5236ad0d7e0Slinke li if (val == (1UL << (map_depth - 1)) - 1)
5246ad0d7e0Slinke li goto next;
5256ad0d7e0Slinke li
5266ad0d7e0Slinke li nr = find_first_zero_bit(&val, map_depth);
5276ad0d7e0Slinke li if (nr + nr_tags <= map_depth) {
5286ad0d7e0Slinke li atomic_long_t *ptr = (atomic_long_t *) &map->word;
5296ad0d7e0Slinke li
5306ad0d7e0Slinke li get_mask = ((1UL << nr_tags) - 1) << nr;
531903e86f3SKemeng Shi while (!atomic_long_try_cmpxchg(ptr, &val,
532903e86f3SKemeng Shi get_mask | val))
533903e86f3SKemeng Shi ;
534c35227d4SUros Bizjak get_mask = (get_mask & ~val) >> nr;
5359672b0d4SJens Axboe if (get_mask) {
5369672b0d4SJens Axboe *offset = nr + (index << sb->shift);
5379672b0d4SJens Axboe update_alloc_hint_after_get(sb, depth, hint,
538ddbfc34fSLiu Song *offset + nr_tags - 1);
5399672b0d4SJens Axboe return get_mask;
5409672b0d4SJens Axboe }
5419672b0d4SJens Axboe }
542fbb564a5Swuchi next:
5439672b0d4SJens Axboe /* Jump to next index. */
5449672b0d4SJens Axboe if (++index >= sb->map_nr)
5459672b0d4SJens Axboe index = 0;
5469672b0d4SJens Axboe }
5479672b0d4SJens Axboe
5489672b0d4SJens Axboe return 0;
5499672b0d4SJens Axboe }
5509672b0d4SJens Axboe
sbitmap_queue_get_shallow(struct sbitmap_queue * sbq,unsigned int shallow_depth)5513f607293SJohn Garry int sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
552c05e6673SOmar Sandoval unsigned int shallow_depth)
553c05e6673SOmar Sandoval {
55461445b56SOmar Sandoval WARN_ON_ONCE(shallow_depth < sbq->min_shallow_depth);
55561445b56SOmar Sandoval
556c548e62bSMing Lei return sbitmap_get_shallow(&sbq->sb, shallow_depth);
557c05e6673SOmar Sandoval }
5583f607293SJohn Garry EXPORT_SYMBOL_GPL(sbitmap_queue_get_shallow);
559c05e6673SOmar Sandoval
sbitmap_queue_min_shallow_depth(struct sbitmap_queue * sbq,unsigned int min_shallow_depth)560a3275539SOmar Sandoval void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq,
561a3275539SOmar Sandoval unsigned int min_shallow_depth)
562a3275539SOmar Sandoval {
563a3275539SOmar Sandoval sbq->min_shallow_depth = min_shallow_depth;
564a3275539SOmar Sandoval sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth);
565a3275539SOmar Sandoval }
566a3275539SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_min_shallow_depth);
567a3275539SOmar Sandoval
__sbitmap_queue_wake_up(struct sbitmap_queue * sbq,int nr)56826edb30dSGabriel Krisman Bertazi static void __sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
56988459642SOmar Sandoval {
57010639737SDavid Jeffery int i, wake_index, woken;
57188459642SOmar Sandoval
5725d2ee712SJens Axboe if (!atomic_read(&sbq->ws_active))
57326edb30dSGabriel Krisman Bertazi return;
5745d2ee712SJens Axboe
57588459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index);
57688459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
57788459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index];
57888459642SOmar Sandoval
579976570b4SGabriel Krisman Bertazi /*
580976570b4SGabriel Krisman Bertazi * Advance the index before checking the current queue.
581976570b4SGabriel Krisman Bertazi * It improves fairness, by ensuring the queue doesn't
582976570b4SGabriel Krisman Bertazi * need to be fully emptied before trying to wake up
583976570b4SGabriel Krisman Bertazi * from the next one.
584976570b4SGabriel Krisman Bertazi */
585976570b4SGabriel Krisman Bertazi wake_index = sbq_index_inc(wake_index);
586976570b4SGabriel Krisman Bertazi
58710639737SDavid Jeffery if (waitqueue_active(&ws->wait)) {
58810639737SDavid Jeffery woken = wake_up_nr(&ws->wait, nr);
58910639737SDavid Jeffery if (woken == nr)
59026edb30dSGabriel Krisman Bertazi break;
59110639737SDavid Jeffery nr -= woken;
59210639737SDavid Jeffery }
59388459642SOmar Sandoval }
59488459642SOmar Sandoval
59588459642SOmar Sandoval if (wake_index != atomic_read(&sbq->wake_index))
59688459642SOmar Sandoval atomic_set(&sbq->wake_index, wake_index);
597c854ab57SJens Axboe }
598c854ab57SJens Axboe
sbitmap_queue_wake_up(struct sbitmap_queue * sbq,int nr)5994acb8341SKeith Busch void sbitmap_queue_wake_up(struct sbitmap_queue *sbq, int nr)
600c854ab57SJens Axboe {
6014f8126bbSGabriel Krisman Bertazi unsigned int wake_batch = READ_ONCE(sbq->wake_batch);
6024f8126bbSGabriel Krisman Bertazi unsigned int wakeups;
6034f8126bbSGabriel Krisman Bertazi
6044f8126bbSGabriel Krisman Bertazi if (!atomic_read(&sbq->ws_active))
6054f8126bbSGabriel Krisman Bertazi return;
6064f8126bbSGabriel Krisman Bertazi
6074f8126bbSGabriel Krisman Bertazi atomic_add(nr, &sbq->completion_cnt);
6084f8126bbSGabriel Krisman Bertazi wakeups = atomic_read(&sbq->wakeup_cnt);
6094f8126bbSGabriel Krisman Bertazi
6104f8126bbSGabriel Krisman Bertazi do {
6114f8126bbSGabriel Krisman Bertazi if (atomic_read(&sbq->completion_cnt) - wakeups < wake_batch)
6124f8126bbSGabriel Krisman Bertazi return;
6134f8126bbSGabriel Krisman Bertazi } while (!atomic_try_cmpxchg(&sbq->wakeup_cnt,
6144f8126bbSGabriel Krisman Bertazi &wakeups, wakeups + wake_batch));
6154f8126bbSGabriel Krisman Bertazi
61626edb30dSGabriel Krisman Bertazi __sbitmap_queue_wake_up(sbq, wake_batch);
61788459642SOmar Sandoval }
618bce1b56cSJens Axboe EXPORT_SYMBOL_GPL(sbitmap_queue_wake_up);
61988459642SOmar Sandoval
sbitmap_update_cpu_hint(struct sbitmap * sb,int cpu,int tag)6201aec5e4aSJens Axboe static inline void sbitmap_update_cpu_hint(struct sbitmap *sb, int cpu, int tag)
6211aec5e4aSJens Axboe {
6221aec5e4aSJens Axboe if (likely(!sb->round_robin && tag < sb->depth))
6239f8b93a7SJens Axboe data_race(*per_cpu_ptr(sb->alloc_hint, cpu) = tag);
6241aec5e4aSJens Axboe }
6251aec5e4aSJens Axboe
sbitmap_queue_clear_batch(struct sbitmap_queue * sbq,int offset,int * tags,int nr_tags)6261aec5e4aSJens Axboe void sbitmap_queue_clear_batch(struct sbitmap_queue *sbq, int offset,
6271aec5e4aSJens Axboe int *tags, int nr_tags)
6281aec5e4aSJens Axboe {
6291aec5e4aSJens Axboe struct sbitmap *sb = &sbq->sb;
6301aec5e4aSJens Axboe unsigned long *addr = NULL;
6311aec5e4aSJens Axboe unsigned long mask = 0;
6321aec5e4aSJens Axboe int i;
6331aec5e4aSJens Axboe
6341aec5e4aSJens Axboe smp_mb__before_atomic();
6351aec5e4aSJens Axboe for (i = 0; i < nr_tags; i++) {
6361aec5e4aSJens Axboe const int tag = tags[i] - offset;
6371aec5e4aSJens Axboe unsigned long *this_addr;
6381aec5e4aSJens Axboe
6391aec5e4aSJens Axboe /* since we're clearing a batch, skip the deferred map */
6401aec5e4aSJens Axboe this_addr = &sb->map[SB_NR_TO_INDEX(sb, tag)].word;
6411aec5e4aSJens Axboe if (!addr) {
6421aec5e4aSJens Axboe addr = this_addr;
6431aec5e4aSJens Axboe } else if (addr != this_addr) {
6441aec5e4aSJens Axboe atomic_long_andnot(mask, (atomic_long_t *) addr);
6451aec5e4aSJens Axboe mask = 0;
6461aec5e4aSJens Axboe addr = this_addr;
6471aec5e4aSJens Axboe }
6481aec5e4aSJens Axboe mask |= (1UL << SB_NR_TO_BIT(sb, tag));
6491aec5e4aSJens Axboe }
6501aec5e4aSJens Axboe
6511aec5e4aSJens Axboe if (mask)
6521aec5e4aSJens Axboe atomic_long_andnot(mask, (atomic_long_t *) addr);
6531aec5e4aSJens Axboe
6541aec5e4aSJens Axboe smp_mb__after_atomic();
6554acb8341SKeith Busch sbitmap_queue_wake_up(sbq, nr_tags);
6561aec5e4aSJens Axboe sbitmap_update_cpu_hint(&sbq->sb, raw_smp_processor_id(),
6571aec5e4aSJens Axboe tags[nr_tags - 1] - offset);
6581aec5e4aSJens Axboe }
6591aec5e4aSJens Axboe
sbitmap_queue_clear(struct sbitmap_queue * sbq,unsigned int nr,unsigned int cpu)66040aabb67SOmar Sandoval void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
661f4a644dbSOmar Sandoval unsigned int cpu)
66288459642SOmar Sandoval {
663e6d1fa58SMing Lei /*
664e6d1fa58SMing Lei * Once the clear bit is set, the bit may be allocated out.
665e6d1fa58SMing Lei *
6669dbbc3b9SZhen Lei * Orders READ/WRITE on the associated instance(such as request
667e6d1fa58SMing Lei * of blk_mq) by this bit for avoiding race with re-allocation,
668e6d1fa58SMing Lei * and its pair is the memory barrier implied in __sbitmap_get_word.
669e6d1fa58SMing Lei *
670e6d1fa58SMing Lei * One invariant is that the clear bit has to be zero when the bit
671e6d1fa58SMing Lei * is in use.
672e6d1fa58SMing Lei */
673e6d1fa58SMing Lei smp_mb__before_atomic();
674ea86ea2cSJens Axboe sbitmap_deferred_clear_bit(&sbq->sb, nr);
675ea86ea2cSJens Axboe
676e6fc4649SMing Lei /*
677e6fc4649SMing Lei * Pairs with the memory barrier in set_current_state() to ensure the
678e6fc4649SMing Lei * proper ordering of clear_bit_unlock()/waitqueue_active() in the waker
679e6fc4649SMing Lei * and test_and_set_bit_lock()/prepare_to_wait()/finish_wait() in the
680e6fc4649SMing Lei * waiter. See the comment on waitqueue_active().
681e6fc4649SMing Lei */
682e6fc4649SMing Lei smp_mb__after_atomic();
6834acb8341SKeith Busch sbitmap_queue_wake_up(sbq, 1);
6841aec5e4aSJens Axboe sbitmap_update_cpu_hint(&sbq->sb, cpu, nr);
68588459642SOmar Sandoval }
68688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_clear);
68788459642SOmar Sandoval
sbitmap_queue_wake_all(struct sbitmap_queue * sbq)68888459642SOmar Sandoval void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
68988459642SOmar Sandoval {
69088459642SOmar Sandoval int i, wake_index;
69188459642SOmar Sandoval
69288459642SOmar Sandoval /*
693f66227deSOmar Sandoval * Pairs with the memory barrier in set_current_state() like in
694e6fc4649SMing Lei * sbitmap_queue_wake_up().
69588459642SOmar Sandoval */
69688459642SOmar Sandoval smp_mb();
69788459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index);
69888459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
69988459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index];
70088459642SOmar Sandoval
70188459642SOmar Sandoval if (waitqueue_active(&ws->wait))
70288459642SOmar Sandoval wake_up(&ws->wait);
70388459642SOmar Sandoval
70488459642SOmar Sandoval wake_index = sbq_index_inc(wake_index);
70588459642SOmar Sandoval }
70688459642SOmar Sandoval }
70788459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all);
70824af1ccfSOmar Sandoval
sbitmap_queue_show(struct sbitmap_queue * sbq,struct seq_file * m)70924af1ccfSOmar Sandoval void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
71024af1ccfSOmar Sandoval {
71124af1ccfSOmar Sandoval bool first;
71224af1ccfSOmar Sandoval int i;
71324af1ccfSOmar Sandoval
71424af1ccfSOmar Sandoval sbitmap_show(&sbq->sb, m);
71524af1ccfSOmar Sandoval
71624af1ccfSOmar Sandoval seq_puts(m, "alloc_hint={");
71724af1ccfSOmar Sandoval first = true;
71824af1ccfSOmar Sandoval for_each_possible_cpu(i) {
71924af1ccfSOmar Sandoval if (!first)
72024af1ccfSOmar Sandoval seq_puts(m, ", ");
72124af1ccfSOmar Sandoval first = false;
722c548e62bSMing Lei seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i));
72324af1ccfSOmar Sandoval }
72424af1ccfSOmar Sandoval seq_puts(m, "}\n");
72524af1ccfSOmar Sandoval
72624af1ccfSOmar Sandoval seq_printf(m, "wake_batch=%u\n", sbq->wake_batch);
72724af1ccfSOmar Sandoval seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index));
7285d2ee712SJens Axboe seq_printf(m, "ws_active=%d\n", atomic_read(&sbq->ws_active));
72924af1ccfSOmar Sandoval
73024af1ccfSOmar Sandoval seq_puts(m, "ws={\n");
73124af1ccfSOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
73224af1ccfSOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[i];
7334f8126bbSGabriel Krisman Bertazi seq_printf(m, "\t{.wait=%s},\n",
73424af1ccfSOmar Sandoval waitqueue_active(&ws->wait) ? "active" : "inactive");
73524af1ccfSOmar Sandoval }
73624af1ccfSOmar Sandoval seq_puts(m, "}\n");
73724af1ccfSOmar Sandoval
738efe1f3a1SMing Lei seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin);
739a3275539SOmar Sandoval seq_printf(m, "min_shallow_depth=%u\n", sbq->min_shallow_depth);
74024af1ccfSOmar Sandoval }
74124af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_show);
7425d2ee712SJens Axboe
sbitmap_add_wait_queue(struct sbitmap_queue * sbq,struct sbq_wait_state * ws,struct sbq_wait * sbq_wait)7439f6b7ef6SJens Axboe void sbitmap_add_wait_queue(struct sbitmap_queue *sbq,
7449f6b7ef6SJens Axboe struct sbq_wait_state *ws,
7459f6b7ef6SJens Axboe struct sbq_wait *sbq_wait)
7469f6b7ef6SJens Axboe {
7479f6b7ef6SJens Axboe if (!sbq_wait->sbq) {
7489f6b7ef6SJens Axboe sbq_wait->sbq = sbq;
7499f6b7ef6SJens Axboe atomic_inc(&sbq->ws_active);
7509f6b7ef6SJens Axboe add_wait_queue(&ws->wait, &sbq_wait->wait);
7519f6b7ef6SJens Axboe }
752df034c93SDavid Jeffery }
7539f6b7ef6SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_add_wait_queue);
7549f6b7ef6SJens Axboe
sbitmap_del_wait_queue(struct sbq_wait * sbq_wait)7559f6b7ef6SJens Axboe void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait)
7569f6b7ef6SJens Axboe {
7579f6b7ef6SJens Axboe list_del_init(&sbq_wait->wait.entry);
7589f6b7ef6SJens Axboe if (sbq_wait->sbq) {
7599f6b7ef6SJens Axboe atomic_dec(&sbq_wait->sbq->ws_active);
7609f6b7ef6SJens Axboe sbq_wait->sbq = NULL;
7619f6b7ef6SJens Axboe }
7629f6b7ef6SJens Axboe }
7639f6b7ef6SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_del_wait_queue);
7649f6b7ef6SJens Axboe
sbitmap_prepare_to_wait(struct sbitmap_queue * sbq,struct sbq_wait_state * ws,struct sbq_wait * sbq_wait,int state)7655d2ee712SJens Axboe void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq,
7665d2ee712SJens Axboe struct sbq_wait_state *ws,
7675d2ee712SJens Axboe struct sbq_wait *sbq_wait, int state)
7685d2ee712SJens Axboe {
7699f6b7ef6SJens Axboe if (!sbq_wait->sbq) {
7705d2ee712SJens Axboe atomic_inc(&sbq->ws_active);
7719f6b7ef6SJens Axboe sbq_wait->sbq = sbq;
7725d2ee712SJens Axboe }
7735d2ee712SJens Axboe prepare_to_wait_exclusive(&ws->wait, &sbq_wait->wait, state);
7745d2ee712SJens Axboe }
7755d2ee712SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_prepare_to_wait);
7765d2ee712SJens Axboe
sbitmap_finish_wait(struct sbitmap_queue * sbq,struct sbq_wait_state * ws,struct sbq_wait * sbq_wait)7775d2ee712SJens Axboe void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws,
7785d2ee712SJens Axboe struct sbq_wait *sbq_wait)
7795d2ee712SJens Axboe {
7805d2ee712SJens Axboe finish_wait(&ws->wait, &sbq_wait->wait);
7819f6b7ef6SJens Axboe if (sbq_wait->sbq) {
7825d2ee712SJens Axboe atomic_dec(&sbq->ws_active);
7839f6b7ef6SJens Axboe sbq_wait->sbq = NULL;
7845d2ee712SJens Axboe }
7855d2ee712SJens Axboe }
7865d2ee712SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_finish_wait);
787