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 12*c548e62bSMing Lei static int init_alloc_hint(struct sbitmap *sb, gfp_t flags) 13bf2c4282SMing Lei { 14*c548e62bSMing Lei unsigned depth = sb->depth; 15bf2c4282SMing Lei 16*c548e62bSMing Lei sb->alloc_hint = alloc_percpu_gfp(unsigned int, flags); 17*c548e62bSMing Lei if (!sb->alloc_hint) 18bf2c4282SMing Lei return -ENOMEM; 19bf2c4282SMing Lei 20*c548e62bSMing Lei if (depth && !sb->round_robin) { 21bf2c4282SMing Lei int i; 22bf2c4282SMing Lei 23bf2c4282SMing Lei for_each_possible_cpu(i) 24*c548e62bSMing Lei *per_cpu_ptr(sb->alloc_hint, i) = prandom_u32() % depth; 25bf2c4282SMing Lei } 26bf2c4282SMing Lei return 0; 27bf2c4282SMing Lei } 28bf2c4282SMing Lei 29*c548e62bSMing 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 34*c548e62bSMing Lei hint = this_cpu_read(*sb->alloc_hint); 35bf2c4282SMing Lei if (unlikely(hint >= depth)) { 36bf2c4282SMing Lei hint = depth ? prandom_u32() % depth : 0; 37*c548e62bSMing Lei this_cpu_write(*sb->alloc_hint, hint); 38bf2c4282SMing Lei } 39bf2c4282SMing Lei 40bf2c4282SMing Lei return hint; 41bf2c4282SMing Lei } 42bf2c4282SMing Lei 43*c548e62bSMing 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. */ 50*c548e62bSMing Lei this_cpu_write(*sb->alloc_hint, 0); 51*c548e62bSMing 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; 56*c548e62bSMing 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 */ 63b78beea0SPavel Begunkov static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) 64b2dbff1bSJens Axboe { 65c3250c8dSPavel Begunkov unsigned long mask; 66b2dbff1bSJens Axboe 67661d4f55SPavel Begunkov if (!READ_ONCE(map->cleared)) 68661d4f55SPavel Begunkov return false; 69b2dbff1bSJens Axboe 70b2dbff1bSJens Axboe /* 71b2dbff1bSJens Axboe * First get a stable cleared mask, setting the old mask to 0. 72b2dbff1bSJens Axboe */ 73b78beea0SPavel Begunkov mask = xchg(&map->cleared, 0); 74b2dbff1bSJens Axboe 75b2dbff1bSJens Axboe /* 76b2dbff1bSJens Axboe * Now clear the masked bits in our free word 77b2dbff1bSJens Axboe */ 78c3250c8dSPavel Begunkov atomic_long_andnot(mask, (atomic_long_t *)&map->word); 79c3250c8dSPavel Begunkov BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word)); 80661d4f55SPavel Begunkov return true; 81b2dbff1bSJens Axboe } 82b2dbff1bSJens Axboe 8388459642SOmar Sandoval int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, 84*c548e62bSMing Lei gfp_t flags, int node, bool round_robin, 85*c548e62bSMing Lei bool alloc_hint) 8688459642SOmar Sandoval { 8788459642SOmar Sandoval unsigned int bits_per_word; 8888459642SOmar Sandoval unsigned int i; 8988459642SOmar Sandoval 9088459642SOmar Sandoval if (shift < 0) { 9188459642SOmar Sandoval shift = ilog2(BITS_PER_LONG); 9288459642SOmar Sandoval /* 9388459642SOmar Sandoval * If the bitmap is small, shrink the number of bits per word so 9488459642SOmar Sandoval * we spread over a few cachelines, at least. If less than 4 9588459642SOmar Sandoval * bits, just forget about it, it's not going to work optimally 9688459642SOmar Sandoval * anyway. 9788459642SOmar Sandoval */ 9888459642SOmar Sandoval if (depth >= 4) { 9988459642SOmar Sandoval while ((4U << shift) > depth) 10088459642SOmar Sandoval shift--; 10188459642SOmar Sandoval } 10288459642SOmar Sandoval } 10388459642SOmar Sandoval bits_per_word = 1U << shift; 10488459642SOmar Sandoval if (bits_per_word > BITS_PER_LONG) 10588459642SOmar Sandoval return -EINVAL; 10688459642SOmar Sandoval 10788459642SOmar Sandoval sb->shift = shift; 10888459642SOmar Sandoval sb->depth = depth; 10988459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 110efe1f3a1SMing Lei sb->round_robin = round_robin; 11188459642SOmar Sandoval 11288459642SOmar Sandoval if (depth == 0) { 11388459642SOmar Sandoval sb->map = NULL; 11488459642SOmar Sandoval return 0; 11588459642SOmar Sandoval } 11688459642SOmar Sandoval 117*c548e62bSMing Lei if (alloc_hint) { 118*c548e62bSMing Lei if (init_alloc_hint(sb, flags)) 11988459642SOmar Sandoval return -ENOMEM; 120*c548e62bSMing Lei } else { 121*c548e62bSMing Lei sb->alloc_hint = NULL; 122*c548e62bSMing Lei } 123*c548e62bSMing Lei 124*c548e62bSMing Lei sb->map = kcalloc_node(sb->map_nr, sizeof(*sb->map), flags, node); 125*c548e62bSMing Lei if (!sb->map) { 126*c548e62bSMing Lei free_percpu(sb->alloc_hint); 127*c548e62bSMing Lei return -ENOMEM; 128*c548e62bSMing Lei } 12988459642SOmar Sandoval 13088459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 13188459642SOmar Sandoval sb->map[i].depth = min(depth, bits_per_word); 13288459642SOmar Sandoval depth -= sb->map[i].depth; 13388459642SOmar Sandoval } 13488459642SOmar Sandoval return 0; 13588459642SOmar Sandoval } 13688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_init_node); 13788459642SOmar Sandoval 13888459642SOmar Sandoval void sbitmap_resize(struct sbitmap *sb, unsigned int depth) 13988459642SOmar Sandoval { 14088459642SOmar Sandoval unsigned int bits_per_word = 1U << sb->shift; 14188459642SOmar Sandoval unsigned int i; 14288459642SOmar Sandoval 143b2dbff1bSJens Axboe for (i = 0; i < sb->map_nr; i++) 144b78beea0SPavel Begunkov sbitmap_deferred_clear(&sb->map[i]); 145b2dbff1bSJens Axboe 14688459642SOmar Sandoval sb->depth = depth; 14788459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 14888459642SOmar Sandoval 14988459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 15088459642SOmar Sandoval sb->map[i].depth = min(depth, bits_per_word); 15188459642SOmar Sandoval depth -= sb->map[i].depth; 15288459642SOmar Sandoval } 15388459642SOmar Sandoval } 15488459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_resize); 15588459642SOmar Sandoval 156c05e6673SOmar Sandoval static int __sbitmap_get_word(unsigned long *word, unsigned long depth, 157c05e6673SOmar Sandoval unsigned int hint, bool wrap) 15888459642SOmar Sandoval { 15988459642SOmar Sandoval int nr; 16088459642SOmar Sandoval 1610eff1f1aSPavel Begunkov /* don't wrap if starting from 0 */ 1620eff1f1aSPavel Begunkov wrap = wrap && hint; 1630eff1f1aSPavel Begunkov 16488459642SOmar Sandoval while (1) { 165c05e6673SOmar Sandoval nr = find_next_zero_bit(word, depth, hint); 166c05e6673SOmar Sandoval if (unlikely(nr >= depth)) { 16788459642SOmar Sandoval /* 16888459642SOmar Sandoval * We started with an offset, and we didn't reset the 16988459642SOmar Sandoval * offset to 0 in a failure case, so start from 0 to 17088459642SOmar Sandoval * exhaust the map. 17188459642SOmar Sandoval */ 1720eff1f1aSPavel Begunkov if (hint && wrap) { 1730eff1f1aSPavel Begunkov hint = 0; 17488459642SOmar Sandoval continue; 17588459642SOmar Sandoval } 17688459642SOmar Sandoval return -1; 17788459642SOmar Sandoval } 17888459642SOmar Sandoval 1794ace53f1SOmar Sandoval if (!test_and_set_bit_lock(nr, word)) 18088459642SOmar Sandoval break; 18188459642SOmar Sandoval 18288459642SOmar Sandoval hint = nr + 1; 183c05e6673SOmar Sandoval if (hint >= depth - 1) 18488459642SOmar Sandoval hint = 0; 18588459642SOmar Sandoval } 18688459642SOmar Sandoval 18788459642SOmar Sandoval return nr; 18888459642SOmar Sandoval } 18988459642SOmar Sandoval 190ea86ea2cSJens Axboe static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index, 191efe1f3a1SMing Lei unsigned int alloc_hint) 192ea86ea2cSJens Axboe { 193b78beea0SPavel Begunkov struct sbitmap_word *map = &sb->map[index]; 194ea86ea2cSJens Axboe int nr; 195ea86ea2cSJens Axboe 196ea86ea2cSJens Axboe do { 197b78beea0SPavel Begunkov nr = __sbitmap_get_word(&map->word, map->depth, alloc_hint, 198efe1f3a1SMing Lei !sb->round_robin); 199ea86ea2cSJens Axboe if (nr != -1) 200ea86ea2cSJens Axboe break; 201b78beea0SPavel Begunkov if (!sbitmap_deferred_clear(map)) 202ea86ea2cSJens Axboe break; 203ea86ea2cSJens Axboe } while (1); 204ea86ea2cSJens Axboe 205ea86ea2cSJens Axboe return nr; 206ea86ea2cSJens Axboe } 207ea86ea2cSJens Axboe 208*c548e62bSMing Lei static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint) 20988459642SOmar Sandoval { 21088459642SOmar Sandoval unsigned int i, index; 21188459642SOmar Sandoval int nr = -1; 21288459642SOmar Sandoval 21388459642SOmar Sandoval index = SB_NR_TO_INDEX(sb, alloc_hint); 21488459642SOmar Sandoval 21527fae429SJens Axboe /* 21627fae429SJens Axboe * Unless we're doing round robin tag allocation, just use the 21727fae429SJens Axboe * alloc_hint to find the right word index. No point in looping 21827fae429SJens Axboe * twice in find_next_zero_bit() for that case. 21927fae429SJens Axboe */ 220efe1f3a1SMing Lei if (sb->round_robin) 22127fae429SJens Axboe alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); 22227fae429SJens Axboe else 22327fae429SJens Axboe alloc_hint = 0; 22427fae429SJens Axboe 22588459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 226efe1f3a1SMing Lei nr = sbitmap_find_bit_in_index(sb, index, alloc_hint); 22788459642SOmar Sandoval if (nr != -1) { 22888459642SOmar Sandoval nr += index << sb->shift; 22988459642SOmar Sandoval break; 23088459642SOmar Sandoval } 23188459642SOmar Sandoval 23288459642SOmar Sandoval /* Jump to next index. */ 23388459642SOmar Sandoval alloc_hint = 0; 23427fae429SJens Axboe if (++index >= sb->map_nr) 23527fae429SJens Axboe index = 0; 23688459642SOmar Sandoval } 23788459642SOmar Sandoval 23888459642SOmar Sandoval return nr; 23988459642SOmar Sandoval } 240*c548e62bSMing Lei 241*c548e62bSMing Lei int sbitmap_get(struct sbitmap *sb) 242*c548e62bSMing Lei { 243*c548e62bSMing Lei int nr; 244*c548e62bSMing Lei unsigned int hint, depth; 245*c548e62bSMing Lei 246*c548e62bSMing Lei if (WARN_ON_ONCE(unlikely(!sb->alloc_hint))) 247*c548e62bSMing Lei return -1; 248*c548e62bSMing Lei 249*c548e62bSMing Lei depth = READ_ONCE(sb->depth); 250*c548e62bSMing Lei hint = update_alloc_hint_before_get(sb, depth); 251*c548e62bSMing Lei nr = __sbitmap_get(sb, hint); 252*c548e62bSMing Lei update_alloc_hint_after_get(sb, depth, hint, nr); 253*c548e62bSMing Lei 254*c548e62bSMing Lei return nr; 255*c548e62bSMing Lei } 25688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_get); 25788459642SOmar Sandoval 258*c548e62bSMing Lei static int __sbitmap_get_shallow(struct sbitmap *sb, 259*c548e62bSMing Lei unsigned int alloc_hint, 260c05e6673SOmar Sandoval unsigned long shallow_depth) 261c05e6673SOmar Sandoval { 262c05e6673SOmar Sandoval unsigned int i, index; 263c05e6673SOmar Sandoval int nr = -1; 264c05e6673SOmar Sandoval 265c05e6673SOmar Sandoval index = SB_NR_TO_INDEX(sb, alloc_hint); 266c05e6673SOmar Sandoval 267c05e6673SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 268b2dbff1bSJens Axboe again: 269c05e6673SOmar Sandoval nr = __sbitmap_get_word(&sb->map[index].word, 270c05e6673SOmar Sandoval min(sb->map[index].depth, shallow_depth), 271c05e6673SOmar Sandoval SB_NR_TO_BIT(sb, alloc_hint), true); 272c05e6673SOmar Sandoval if (nr != -1) { 273c05e6673SOmar Sandoval nr += index << sb->shift; 274c05e6673SOmar Sandoval break; 275c05e6673SOmar Sandoval } 276c05e6673SOmar Sandoval 277b78beea0SPavel Begunkov if (sbitmap_deferred_clear(&sb->map[index])) 278b2dbff1bSJens Axboe goto again; 279b2dbff1bSJens Axboe 280c05e6673SOmar Sandoval /* Jump to next index. */ 281c05e6673SOmar Sandoval index++; 282c05e6673SOmar Sandoval alloc_hint = index << sb->shift; 283c05e6673SOmar Sandoval 284c05e6673SOmar Sandoval if (index >= sb->map_nr) { 285c05e6673SOmar Sandoval index = 0; 286c05e6673SOmar Sandoval alloc_hint = 0; 287c05e6673SOmar Sandoval } 288c05e6673SOmar Sandoval } 289c05e6673SOmar Sandoval 290c05e6673SOmar Sandoval return nr; 291c05e6673SOmar Sandoval } 292*c548e62bSMing Lei 293*c548e62bSMing Lei int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth) 294*c548e62bSMing Lei { 295*c548e62bSMing Lei int nr; 296*c548e62bSMing Lei unsigned int hint, depth; 297*c548e62bSMing Lei 298*c548e62bSMing Lei if (WARN_ON_ONCE(unlikely(!sb->alloc_hint))) 299*c548e62bSMing Lei return -1; 300*c548e62bSMing Lei 301*c548e62bSMing Lei depth = READ_ONCE(sb->depth); 302*c548e62bSMing Lei hint = update_alloc_hint_before_get(sb, depth); 303*c548e62bSMing Lei nr = __sbitmap_get_shallow(sb, hint, shallow_depth); 304*c548e62bSMing Lei update_alloc_hint_after_get(sb, depth, hint, nr); 305*c548e62bSMing Lei 306*c548e62bSMing Lei return nr; 307*c548e62bSMing Lei } 308c05e6673SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_get_shallow); 309c05e6673SOmar Sandoval 31088459642SOmar Sandoval bool sbitmap_any_bit_set(const struct sbitmap *sb) 31188459642SOmar Sandoval { 31288459642SOmar Sandoval unsigned int i; 31388459642SOmar Sandoval 31488459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 315b2dbff1bSJens Axboe if (sb->map[i].word & ~sb->map[i].cleared) 31688459642SOmar Sandoval return true; 31788459642SOmar Sandoval } 31888459642SOmar Sandoval return false; 31988459642SOmar Sandoval } 32088459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_any_bit_set); 32188459642SOmar Sandoval 322ea86ea2cSJens Axboe static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set) 32388459642SOmar Sandoval { 32460658e0dSColin Ian King unsigned int i, weight = 0; 32588459642SOmar Sandoval 32688459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 32788459642SOmar Sandoval const struct sbitmap_word *word = &sb->map[i]; 32888459642SOmar Sandoval 329ea86ea2cSJens Axboe if (set) 33088459642SOmar Sandoval weight += bitmap_weight(&word->word, word->depth); 331ea86ea2cSJens Axboe else 332ea86ea2cSJens Axboe weight += bitmap_weight(&word->cleared, word->depth); 33388459642SOmar Sandoval } 33488459642SOmar Sandoval return weight; 33588459642SOmar Sandoval } 336ea86ea2cSJens Axboe 337ea86ea2cSJens Axboe static unsigned int sbitmap_weight(const struct sbitmap *sb) 338ea86ea2cSJens Axboe { 339ea86ea2cSJens Axboe return __sbitmap_weight(sb, true); 340ea86ea2cSJens Axboe } 341ea86ea2cSJens Axboe 342ea86ea2cSJens Axboe static unsigned int sbitmap_cleared(const struct sbitmap *sb) 343ea86ea2cSJens Axboe { 344ea86ea2cSJens Axboe return __sbitmap_weight(sb, false); 345ea86ea2cSJens Axboe } 34688459642SOmar Sandoval 34724af1ccfSOmar Sandoval void sbitmap_show(struct sbitmap *sb, struct seq_file *m) 34824af1ccfSOmar Sandoval { 34924af1ccfSOmar Sandoval seq_printf(m, "depth=%u\n", sb->depth); 350ea86ea2cSJens Axboe seq_printf(m, "busy=%u\n", sbitmap_weight(sb) - sbitmap_cleared(sb)); 351ea86ea2cSJens Axboe seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb)); 35224af1ccfSOmar Sandoval seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift); 35324af1ccfSOmar Sandoval seq_printf(m, "map_nr=%u\n", sb->map_nr); 35424af1ccfSOmar Sandoval } 35524af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_show); 35624af1ccfSOmar Sandoval 35724af1ccfSOmar Sandoval static inline void emit_byte(struct seq_file *m, unsigned int offset, u8 byte) 35824af1ccfSOmar Sandoval { 35924af1ccfSOmar Sandoval if ((offset & 0xf) == 0) { 36024af1ccfSOmar Sandoval if (offset != 0) 36124af1ccfSOmar Sandoval seq_putc(m, '\n'); 36224af1ccfSOmar Sandoval seq_printf(m, "%08x:", offset); 36324af1ccfSOmar Sandoval } 36424af1ccfSOmar Sandoval if ((offset & 0x1) == 0) 36524af1ccfSOmar Sandoval seq_putc(m, ' '); 36624af1ccfSOmar Sandoval seq_printf(m, "%02x", byte); 36724af1ccfSOmar Sandoval } 36824af1ccfSOmar Sandoval 36924af1ccfSOmar Sandoval void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m) 37024af1ccfSOmar Sandoval { 37124af1ccfSOmar Sandoval u8 byte = 0; 37224af1ccfSOmar Sandoval unsigned int byte_bits = 0; 37324af1ccfSOmar Sandoval unsigned int offset = 0; 37424af1ccfSOmar Sandoval int i; 37524af1ccfSOmar Sandoval 37624af1ccfSOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 37724af1ccfSOmar Sandoval unsigned long word = READ_ONCE(sb->map[i].word); 3786bf0eb55SJohn Garry unsigned long cleared = READ_ONCE(sb->map[i].cleared); 37924af1ccfSOmar Sandoval unsigned int word_bits = READ_ONCE(sb->map[i].depth); 38024af1ccfSOmar Sandoval 3816bf0eb55SJohn Garry word &= ~cleared; 3826bf0eb55SJohn Garry 38324af1ccfSOmar Sandoval while (word_bits > 0) { 38424af1ccfSOmar Sandoval unsigned int bits = min(8 - byte_bits, word_bits); 38524af1ccfSOmar Sandoval 38624af1ccfSOmar Sandoval byte |= (word & (BIT(bits) - 1)) << byte_bits; 38724af1ccfSOmar Sandoval byte_bits += bits; 38824af1ccfSOmar Sandoval if (byte_bits == 8) { 38924af1ccfSOmar Sandoval emit_byte(m, offset, byte); 39024af1ccfSOmar Sandoval byte = 0; 39124af1ccfSOmar Sandoval byte_bits = 0; 39224af1ccfSOmar Sandoval offset++; 39324af1ccfSOmar Sandoval } 39424af1ccfSOmar Sandoval word >>= bits; 39524af1ccfSOmar Sandoval word_bits -= bits; 39624af1ccfSOmar Sandoval } 39724af1ccfSOmar Sandoval } 39824af1ccfSOmar Sandoval if (byte_bits) { 39924af1ccfSOmar Sandoval emit_byte(m, offset, byte); 40024af1ccfSOmar Sandoval offset++; 40124af1ccfSOmar Sandoval } 40224af1ccfSOmar Sandoval if (offset) 40324af1ccfSOmar Sandoval seq_putc(m, '\n'); 40424af1ccfSOmar Sandoval } 40524af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_bitmap_show); 40624af1ccfSOmar Sandoval 407a3275539SOmar Sandoval static unsigned int sbq_calc_wake_batch(struct sbitmap_queue *sbq, 408a3275539SOmar Sandoval unsigned int depth) 40988459642SOmar Sandoval { 41088459642SOmar Sandoval unsigned int wake_batch; 411a3275539SOmar Sandoval unsigned int shallow_depth; 41288459642SOmar Sandoval 41388459642SOmar Sandoval /* 41488459642SOmar Sandoval * For each batch, we wake up one queue. We need to make sure that our 415a3275539SOmar Sandoval * batch size is small enough that the full depth of the bitmap, 416a3275539SOmar Sandoval * potentially limited by a shallow depth, is enough to wake up all of 417a3275539SOmar Sandoval * the queues. 418a3275539SOmar Sandoval * 419a3275539SOmar Sandoval * Each full word of the bitmap has bits_per_word bits, and there might 420a3275539SOmar Sandoval * be a partial word. There are depth / bits_per_word full words and 421a3275539SOmar Sandoval * depth % bits_per_word bits left over. In bitwise arithmetic: 422a3275539SOmar Sandoval * 423a3275539SOmar Sandoval * bits_per_word = 1 << shift 424a3275539SOmar Sandoval * depth / bits_per_word = depth >> shift 425a3275539SOmar Sandoval * depth % bits_per_word = depth & ((1 << shift) - 1) 426a3275539SOmar Sandoval * 427a3275539SOmar Sandoval * Each word can be limited to sbq->min_shallow_depth bits. 42888459642SOmar Sandoval */ 429a3275539SOmar Sandoval shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth); 430a3275539SOmar Sandoval depth = ((depth >> sbq->sb.shift) * shallow_depth + 431a3275539SOmar Sandoval min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth)); 432a3275539SOmar Sandoval wake_batch = clamp_t(unsigned int, depth / SBQ_WAIT_QUEUES, 1, 433a3275539SOmar Sandoval SBQ_WAKE_BATCH); 43488459642SOmar Sandoval 43588459642SOmar Sandoval return wake_batch; 43688459642SOmar Sandoval } 43788459642SOmar Sandoval 43888459642SOmar Sandoval int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, 439f4a644dbSOmar Sandoval int shift, bool round_robin, gfp_t flags, int node) 44088459642SOmar Sandoval { 44188459642SOmar Sandoval int ret; 44288459642SOmar Sandoval int i; 44388459642SOmar Sandoval 444efe1f3a1SMing Lei ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node, 445*c548e62bSMing Lei round_robin, true); 44688459642SOmar Sandoval if (ret) 44788459642SOmar Sandoval return ret; 44888459642SOmar Sandoval 449a3275539SOmar Sandoval sbq->min_shallow_depth = UINT_MAX; 450a3275539SOmar Sandoval sbq->wake_batch = sbq_calc_wake_batch(sbq, depth); 45188459642SOmar Sandoval atomic_set(&sbq->wake_index, 0); 4525d2ee712SJens Axboe atomic_set(&sbq->ws_active, 0); 45388459642SOmar Sandoval 45448e28166SOmar Sandoval sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node); 45588459642SOmar Sandoval if (!sbq->ws) { 45688459642SOmar Sandoval sbitmap_free(&sbq->sb); 45788459642SOmar Sandoval return -ENOMEM; 45888459642SOmar Sandoval } 45988459642SOmar Sandoval 46088459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 46188459642SOmar Sandoval init_waitqueue_head(&sbq->ws[i].wait); 46288459642SOmar Sandoval atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch); 46388459642SOmar Sandoval } 464f4a644dbSOmar Sandoval 46588459642SOmar Sandoval return 0; 46688459642SOmar Sandoval } 46788459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_init_node); 46888459642SOmar Sandoval 469a3275539SOmar Sandoval static void sbitmap_queue_update_wake_batch(struct sbitmap_queue *sbq, 470a3275539SOmar Sandoval unsigned int depth) 47188459642SOmar Sandoval { 472a3275539SOmar Sandoval unsigned int wake_batch = sbq_calc_wake_batch(sbq, depth); 4736c0ca7aeSOmar Sandoval int i; 4746c0ca7aeSOmar Sandoval 4756c0ca7aeSOmar Sandoval if (sbq->wake_batch != wake_batch) { 4766c0ca7aeSOmar Sandoval WRITE_ONCE(sbq->wake_batch, wake_batch); 4776c0ca7aeSOmar Sandoval /* 478e6fc4649SMing Lei * Pairs with the memory barrier in sbitmap_queue_wake_up() 479e6fc4649SMing Lei * to ensure that the batch size is updated before the wait 480e6fc4649SMing Lei * counts. 4816c0ca7aeSOmar Sandoval */ 482a0934fd2SAndrea Parri smp_mb(); 4836c0ca7aeSOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) 4846c0ca7aeSOmar Sandoval atomic_set(&sbq->ws[i].wait_cnt, 1); 4856c0ca7aeSOmar Sandoval } 486a3275539SOmar Sandoval } 487a3275539SOmar Sandoval 488a3275539SOmar Sandoval void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth) 489a3275539SOmar Sandoval { 490a3275539SOmar Sandoval sbitmap_queue_update_wake_batch(sbq, depth); 49188459642SOmar Sandoval sbitmap_resize(&sbq->sb, depth); 49288459642SOmar Sandoval } 49388459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_resize); 49488459642SOmar Sandoval 495f4a644dbSOmar Sandoval int __sbitmap_queue_get(struct sbitmap_queue *sbq) 49640aabb67SOmar Sandoval { 497*c548e62bSMing Lei return sbitmap_get(&sbq->sb); 49840aabb67SOmar Sandoval } 49940aabb67SOmar Sandoval EXPORT_SYMBOL_GPL(__sbitmap_queue_get); 50040aabb67SOmar Sandoval 501c05e6673SOmar Sandoval int __sbitmap_queue_get_shallow(struct sbitmap_queue *sbq, 502c05e6673SOmar Sandoval unsigned int shallow_depth) 503c05e6673SOmar Sandoval { 50461445b56SOmar Sandoval WARN_ON_ONCE(shallow_depth < sbq->min_shallow_depth); 50561445b56SOmar Sandoval 506*c548e62bSMing Lei return sbitmap_get_shallow(&sbq->sb, shallow_depth); 507c05e6673SOmar Sandoval } 508c05e6673SOmar Sandoval EXPORT_SYMBOL_GPL(__sbitmap_queue_get_shallow); 509c05e6673SOmar Sandoval 510a3275539SOmar Sandoval void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq, 511a3275539SOmar Sandoval unsigned int min_shallow_depth) 512a3275539SOmar Sandoval { 513a3275539SOmar Sandoval sbq->min_shallow_depth = min_shallow_depth; 514a3275539SOmar Sandoval sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth); 515a3275539SOmar Sandoval } 516a3275539SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_min_shallow_depth); 517a3275539SOmar Sandoval 51888459642SOmar Sandoval static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq) 51988459642SOmar Sandoval { 52088459642SOmar Sandoval int i, wake_index; 52188459642SOmar Sandoval 5225d2ee712SJens Axboe if (!atomic_read(&sbq->ws_active)) 5235d2ee712SJens Axboe return NULL; 5245d2ee712SJens Axboe 52588459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index); 52688459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 52788459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index]; 52888459642SOmar Sandoval 52988459642SOmar Sandoval if (waitqueue_active(&ws->wait)) { 53041723288SPavel Begunkov if (wake_index != atomic_read(&sbq->wake_index)) 53141723288SPavel Begunkov atomic_set(&sbq->wake_index, wake_index); 53288459642SOmar Sandoval return ws; 53388459642SOmar Sandoval } 53488459642SOmar Sandoval 53588459642SOmar Sandoval wake_index = sbq_index_inc(wake_index); 53688459642SOmar Sandoval } 53788459642SOmar Sandoval 53888459642SOmar Sandoval return NULL; 53988459642SOmar Sandoval } 54088459642SOmar Sandoval 541c854ab57SJens Axboe static bool __sbq_wake_up(struct sbitmap_queue *sbq) 54288459642SOmar Sandoval { 54388459642SOmar Sandoval struct sbq_wait_state *ws; 5446c0ca7aeSOmar Sandoval unsigned int wake_batch; 54588459642SOmar Sandoval int wait_cnt; 54688459642SOmar Sandoval 54788459642SOmar Sandoval ws = sbq_wake_ptr(sbq); 54888459642SOmar Sandoval if (!ws) 549c854ab57SJens Axboe return false; 55088459642SOmar Sandoval 55188459642SOmar Sandoval wait_cnt = atomic_dec_return(&ws->wait_cnt); 5526c0ca7aeSOmar Sandoval if (wait_cnt <= 0) { 553c854ab57SJens Axboe int ret; 554c854ab57SJens Axboe 5556c0ca7aeSOmar Sandoval wake_batch = READ_ONCE(sbq->wake_batch); 556c854ab57SJens Axboe 5576c0ca7aeSOmar Sandoval /* 5586c0ca7aeSOmar Sandoval * Pairs with the memory barrier in sbitmap_queue_resize() to 5596c0ca7aeSOmar Sandoval * ensure that we see the batch size update before the wait 5606c0ca7aeSOmar Sandoval * count is reset. 5616c0ca7aeSOmar Sandoval */ 5626c0ca7aeSOmar Sandoval smp_mb__before_atomic(); 563c854ab57SJens Axboe 5646c0ca7aeSOmar Sandoval /* 565c854ab57SJens Axboe * For concurrent callers of this, the one that failed the 566c854ab57SJens Axboe * atomic_cmpxhcg() race should call this function again 567c854ab57SJens Axboe * to wakeup a new batch on a different 'ws'. 5686c0ca7aeSOmar Sandoval */ 569c854ab57SJens Axboe ret = atomic_cmpxchg(&ws->wait_cnt, wait_cnt, wake_batch); 570c854ab57SJens Axboe if (ret == wait_cnt) { 57188459642SOmar Sandoval sbq_index_atomic_inc(&sbq->wake_index); 5724e5dff41SJens Axboe wake_up_nr(&ws->wait, wake_batch); 573c854ab57SJens Axboe return false; 57488459642SOmar Sandoval } 575c854ab57SJens Axboe 576c854ab57SJens Axboe return true; 577c854ab57SJens Axboe } 578c854ab57SJens Axboe 579c854ab57SJens Axboe return false; 580c854ab57SJens Axboe } 581c854ab57SJens Axboe 582e6fc4649SMing Lei void sbitmap_queue_wake_up(struct sbitmap_queue *sbq) 583c854ab57SJens Axboe { 584c854ab57SJens Axboe while (__sbq_wake_up(sbq)) 585c854ab57SJens Axboe ; 58688459642SOmar Sandoval } 587e6fc4649SMing Lei EXPORT_SYMBOL_GPL(sbitmap_queue_wake_up); 58888459642SOmar Sandoval 58940aabb67SOmar Sandoval void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr, 590f4a644dbSOmar Sandoval unsigned int cpu) 59188459642SOmar Sandoval { 592e6d1fa58SMing Lei /* 593e6d1fa58SMing Lei * Once the clear bit is set, the bit may be allocated out. 594e6d1fa58SMing Lei * 595e6d1fa58SMing Lei * Orders READ/WRITE on the asssociated instance(such as request 596e6d1fa58SMing Lei * of blk_mq) by this bit for avoiding race with re-allocation, 597e6d1fa58SMing Lei * and its pair is the memory barrier implied in __sbitmap_get_word. 598e6d1fa58SMing Lei * 599e6d1fa58SMing Lei * One invariant is that the clear bit has to be zero when the bit 600e6d1fa58SMing Lei * is in use. 601e6d1fa58SMing Lei */ 602e6d1fa58SMing Lei smp_mb__before_atomic(); 603ea86ea2cSJens Axboe sbitmap_deferred_clear_bit(&sbq->sb, nr); 604ea86ea2cSJens Axboe 605e6fc4649SMing Lei /* 606e6fc4649SMing Lei * Pairs with the memory barrier in set_current_state() to ensure the 607e6fc4649SMing Lei * proper ordering of clear_bit_unlock()/waitqueue_active() in the waker 608e6fc4649SMing Lei * and test_and_set_bit_lock()/prepare_to_wait()/finish_wait() in the 609e6fc4649SMing Lei * waiter. See the comment on waitqueue_active(). 610e6fc4649SMing Lei */ 611e6fc4649SMing Lei smp_mb__after_atomic(); 612e6fc4649SMing Lei sbitmap_queue_wake_up(sbq); 613e6fc4649SMing Lei 614efe1f3a1SMing Lei if (likely(!sbq->sb.round_robin && nr < sbq->sb.depth)) 615*c548e62bSMing Lei *per_cpu_ptr(sbq->sb.alloc_hint, cpu) = nr; 61688459642SOmar Sandoval } 61788459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_clear); 61888459642SOmar Sandoval 61988459642SOmar Sandoval void sbitmap_queue_wake_all(struct sbitmap_queue *sbq) 62088459642SOmar Sandoval { 62188459642SOmar Sandoval int i, wake_index; 62288459642SOmar Sandoval 62388459642SOmar Sandoval /* 624f66227deSOmar Sandoval * Pairs with the memory barrier in set_current_state() like in 625e6fc4649SMing Lei * sbitmap_queue_wake_up(). 62688459642SOmar Sandoval */ 62788459642SOmar Sandoval smp_mb(); 62888459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index); 62988459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 63088459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index]; 63188459642SOmar Sandoval 63288459642SOmar Sandoval if (waitqueue_active(&ws->wait)) 63388459642SOmar Sandoval wake_up(&ws->wait); 63488459642SOmar Sandoval 63588459642SOmar Sandoval wake_index = sbq_index_inc(wake_index); 63688459642SOmar Sandoval } 63788459642SOmar Sandoval } 63888459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all); 63924af1ccfSOmar Sandoval 64024af1ccfSOmar Sandoval void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m) 64124af1ccfSOmar Sandoval { 64224af1ccfSOmar Sandoval bool first; 64324af1ccfSOmar Sandoval int i; 64424af1ccfSOmar Sandoval 64524af1ccfSOmar Sandoval sbitmap_show(&sbq->sb, m); 64624af1ccfSOmar Sandoval 64724af1ccfSOmar Sandoval seq_puts(m, "alloc_hint={"); 64824af1ccfSOmar Sandoval first = true; 64924af1ccfSOmar Sandoval for_each_possible_cpu(i) { 65024af1ccfSOmar Sandoval if (!first) 65124af1ccfSOmar Sandoval seq_puts(m, ", "); 65224af1ccfSOmar Sandoval first = false; 653*c548e62bSMing Lei seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i)); 65424af1ccfSOmar Sandoval } 65524af1ccfSOmar Sandoval seq_puts(m, "}\n"); 65624af1ccfSOmar Sandoval 65724af1ccfSOmar Sandoval seq_printf(m, "wake_batch=%u\n", sbq->wake_batch); 65824af1ccfSOmar Sandoval seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index)); 6595d2ee712SJens Axboe seq_printf(m, "ws_active=%d\n", atomic_read(&sbq->ws_active)); 66024af1ccfSOmar Sandoval 66124af1ccfSOmar Sandoval seq_puts(m, "ws={\n"); 66224af1ccfSOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 66324af1ccfSOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[i]; 66424af1ccfSOmar Sandoval 66524af1ccfSOmar Sandoval seq_printf(m, "\t{.wait_cnt=%d, .wait=%s},\n", 66624af1ccfSOmar Sandoval atomic_read(&ws->wait_cnt), 66724af1ccfSOmar Sandoval waitqueue_active(&ws->wait) ? "active" : "inactive"); 66824af1ccfSOmar Sandoval } 66924af1ccfSOmar Sandoval seq_puts(m, "}\n"); 67024af1ccfSOmar Sandoval 671efe1f3a1SMing Lei seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin); 672a3275539SOmar Sandoval seq_printf(m, "min_shallow_depth=%u\n", sbq->min_shallow_depth); 67324af1ccfSOmar Sandoval } 67424af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_show); 6755d2ee712SJens Axboe 6769f6b7ef6SJens Axboe void sbitmap_add_wait_queue(struct sbitmap_queue *sbq, 6779f6b7ef6SJens Axboe struct sbq_wait_state *ws, 6789f6b7ef6SJens Axboe struct sbq_wait *sbq_wait) 6799f6b7ef6SJens Axboe { 6809f6b7ef6SJens Axboe if (!sbq_wait->sbq) { 6819f6b7ef6SJens Axboe sbq_wait->sbq = sbq; 6829f6b7ef6SJens Axboe atomic_inc(&sbq->ws_active); 6839f6b7ef6SJens Axboe add_wait_queue(&ws->wait, &sbq_wait->wait); 6849f6b7ef6SJens Axboe } 685df034c93SDavid Jeffery } 6869f6b7ef6SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_add_wait_queue); 6879f6b7ef6SJens Axboe 6889f6b7ef6SJens Axboe void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait) 6899f6b7ef6SJens Axboe { 6909f6b7ef6SJens Axboe list_del_init(&sbq_wait->wait.entry); 6919f6b7ef6SJens Axboe if (sbq_wait->sbq) { 6929f6b7ef6SJens Axboe atomic_dec(&sbq_wait->sbq->ws_active); 6939f6b7ef6SJens Axboe sbq_wait->sbq = NULL; 6949f6b7ef6SJens Axboe } 6959f6b7ef6SJens Axboe } 6969f6b7ef6SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_del_wait_queue); 6979f6b7ef6SJens Axboe 6985d2ee712SJens Axboe void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq, 6995d2ee712SJens Axboe struct sbq_wait_state *ws, 7005d2ee712SJens Axboe struct sbq_wait *sbq_wait, int state) 7015d2ee712SJens Axboe { 7029f6b7ef6SJens Axboe if (!sbq_wait->sbq) { 7035d2ee712SJens Axboe atomic_inc(&sbq->ws_active); 7049f6b7ef6SJens Axboe sbq_wait->sbq = sbq; 7055d2ee712SJens Axboe } 7065d2ee712SJens Axboe prepare_to_wait_exclusive(&ws->wait, &sbq_wait->wait, state); 7075d2ee712SJens Axboe } 7085d2ee712SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_prepare_to_wait); 7095d2ee712SJens Axboe 7105d2ee712SJens Axboe void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws, 7115d2ee712SJens Axboe struct sbq_wait *sbq_wait) 7125d2ee712SJens Axboe { 7135d2ee712SJens Axboe finish_wait(&ws->wait, &sbq_wait->wait); 7149f6b7ef6SJens Axboe if (sbq_wait->sbq) { 7155d2ee712SJens Axboe atomic_dec(&sbq->ws_active); 7169f6b7ef6SJens Axboe sbq_wait->sbq = NULL; 7175d2ee712SJens Axboe } 7185d2ee712SJens Axboe } 7195d2ee712SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_finish_wait); 720