1*0fc479b1SThomas 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 12b2dbff1bSJens Axboe /* 13b2dbff1bSJens Axboe * See if we have deferred clears that we can batch move 14b2dbff1bSJens Axboe */ 15b2dbff1bSJens Axboe static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) 16b2dbff1bSJens Axboe { 17b2dbff1bSJens Axboe unsigned long mask, val; 18b2dbff1bSJens Axboe bool ret = false; 19fe76fc6aSMing Lei unsigned long flags; 20b2dbff1bSJens Axboe 21fe76fc6aSMing Lei spin_lock_irqsave(&sb->map[index].swap_lock, flags); 22b2dbff1bSJens Axboe 23b2dbff1bSJens Axboe if (!sb->map[index].cleared) 24b2dbff1bSJens Axboe goto out_unlock; 25b2dbff1bSJens Axboe 26b2dbff1bSJens Axboe /* 27b2dbff1bSJens Axboe * First get a stable cleared mask, setting the old mask to 0. 28b2dbff1bSJens Axboe */ 29b2dbff1bSJens Axboe do { 30b2dbff1bSJens Axboe mask = sb->map[index].cleared; 31b2dbff1bSJens Axboe } while (cmpxchg(&sb->map[index].cleared, mask, 0) != mask); 32b2dbff1bSJens Axboe 33b2dbff1bSJens Axboe /* 34b2dbff1bSJens Axboe * Now clear the masked bits in our free word 35b2dbff1bSJens Axboe */ 36b2dbff1bSJens Axboe do { 37b2dbff1bSJens Axboe val = sb->map[index].word; 38b2dbff1bSJens Axboe } while (cmpxchg(&sb->map[index].word, val, val & ~mask) != val); 39b2dbff1bSJens Axboe 40b2dbff1bSJens Axboe ret = true; 41b2dbff1bSJens Axboe out_unlock: 42fe76fc6aSMing Lei spin_unlock_irqrestore(&sb->map[index].swap_lock, flags); 43b2dbff1bSJens Axboe return ret; 44b2dbff1bSJens Axboe } 45b2dbff1bSJens Axboe 4688459642SOmar Sandoval int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, 4788459642SOmar Sandoval gfp_t flags, int node) 4888459642SOmar Sandoval { 4988459642SOmar Sandoval unsigned int bits_per_word; 5088459642SOmar Sandoval unsigned int i; 5188459642SOmar Sandoval 5288459642SOmar Sandoval if (shift < 0) { 5388459642SOmar Sandoval shift = ilog2(BITS_PER_LONG); 5488459642SOmar Sandoval /* 5588459642SOmar Sandoval * If the bitmap is small, shrink the number of bits per word so 5688459642SOmar Sandoval * we spread over a few cachelines, at least. If less than 4 5788459642SOmar Sandoval * bits, just forget about it, it's not going to work optimally 5888459642SOmar Sandoval * anyway. 5988459642SOmar Sandoval */ 6088459642SOmar Sandoval if (depth >= 4) { 6188459642SOmar Sandoval while ((4U << shift) > depth) 6288459642SOmar Sandoval shift--; 6388459642SOmar Sandoval } 6488459642SOmar Sandoval } 6588459642SOmar Sandoval bits_per_word = 1U << shift; 6688459642SOmar Sandoval if (bits_per_word > BITS_PER_LONG) 6788459642SOmar Sandoval return -EINVAL; 6888459642SOmar Sandoval 6988459642SOmar Sandoval sb->shift = shift; 7088459642SOmar Sandoval sb->depth = depth; 7188459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 7288459642SOmar Sandoval 7388459642SOmar Sandoval if (depth == 0) { 7488459642SOmar Sandoval sb->map = NULL; 7588459642SOmar Sandoval return 0; 7688459642SOmar Sandoval } 7788459642SOmar Sandoval 78590b5b7dSKees Cook sb->map = kcalloc_node(sb->map_nr, sizeof(*sb->map), flags, node); 7988459642SOmar Sandoval if (!sb->map) 8088459642SOmar Sandoval return -ENOMEM; 8188459642SOmar Sandoval 8288459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 8388459642SOmar Sandoval sb->map[i].depth = min(depth, bits_per_word); 8488459642SOmar Sandoval depth -= sb->map[i].depth; 85ea86ea2cSJens Axboe spin_lock_init(&sb->map[i].swap_lock); 8688459642SOmar Sandoval } 8788459642SOmar Sandoval return 0; 8888459642SOmar Sandoval } 8988459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_init_node); 9088459642SOmar Sandoval 9188459642SOmar Sandoval void sbitmap_resize(struct sbitmap *sb, unsigned int depth) 9288459642SOmar Sandoval { 9388459642SOmar Sandoval unsigned int bits_per_word = 1U << sb->shift; 9488459642SOmar Sandoval unsigned int i; 9588459642SOmar Sandoval 96b2dbff1bSJens Axboe for (i = 0; i < sb->map_nr; i++) 97b2dbff1bSJens Axboe sbitmap_deferred_clear(sb, i); 98b2dbff1bSJens Axboe 9988459642SOmar Sandoval sb->depth = depth; 10088459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 10188459642SOmar Sandoval 10288459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 10388459642SOmar Sandoval sb->map[i].depth = min(depth, bits_per_word); 10488459642SOmar Sandoval depth -= sb->map[i].depth; 10588459642SOmar Sandoval } 10688459642SOmar Sandoval } 10788459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_resize); 10888459642SOmar Sandoval 109c05e6673SOmar Sandoval static int __sbitmap_get_word(unsigned long *word, unsigned long depth, 110c05e6673SOmar Sandoval unsigned int hint, bool wrap) 11188459642SOmar Sandoval { 11288459642SOmar Sandoval unsigned int orig_hint = hint; 11388459642SOmar Sandoval int nr; 11488459642SOmar Sandoval 11588459642SOmar Sandoval while (1) { 116c05e6673SOmar Sandoval nr = find_next_zero_bit(word, depth, hint); 117c05e6673SOmar Sandoval if (unlikely(nr >= depth)) { 11888459642SOmar Sandoval /* 11988459642SOmar Sandoval * We started with an offset, and we didn't reset the 12088459642SOmar Sandoval * offset to 0 in a failure case, so start from 0 to 12188459642SOmar Sandoval * exhaust the map. 12288459642SOmar Sandoval */ 12388459642SOmar Sandoval if (orig_hint && hint && wrap) { 12488459642SOmar Sandoval hint = orig_hint = 0; 12588459642SOmar Sandoval continue; 12688459642SOmar Sandoval } 12788459642SOmar Sandoval return -1; 12888459642SOmar Sandoval } 12988459642SOmar Sandoval 1304ace53f1SOmar Sandoval if (!test_and_set_bit_lock(nr, word)) 13188459642SOmar Sandoval break; 13288459642SOmar Sandoval 13388459642SOmar Sandoval hint = nr + 1; 134c05e6673SOmar Sandoval if (hint >= depth - 1) 13588459642SOmar Sandoval hint = 0; 13688459642SOmar Sandoval } 13788459642SOmar Sandoval 13888459642SOmar Sandoval return nr; 13988459642SOmar Sandoval } 14088459642SOmar Sandoval 141ea86ea2cSJens Axboe static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index, 142ea86ea2cSJens Axboe unsigned int alloc_hint, bool round_robin) 143ea86ea2cSJens Axboe { 144ea86ea2cSJens Axboe int nr; 145ea86ea2cSJens Axboe 146ea86ea2cSJens Axboe do { 147ea86ea2cSJens Axboe nr = __sbitmap_get_word(&sb->map[index].word, 148ea86ea2cSJens Axboe sb->map[index].depth, alloc_hint, 149ea86ea2cSJens Axboe !round_robin); 150ea86ea2cSJens Axboe if (nr != -1) 151ea86ea2cSJens Axboe break; 152ea86ea2cSJens Axboe if (!sbitmap_deferred_clear(sb, index)) 153ea86ea2cSJens Axboe break; 154ea86ea2cSJens Axboe } while (1); 155ea86ea2cSJens Axboe 156ea86ea2cSJens Axboe return nr; 157ea86ea2cSJens Axboe } 158ea86ea2cSJens Axboe 15988459642SOmar Sandoval int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin) 16088459642SOmar Sandoval { 16188459642SOmar Sandoval unsigned int i, index; 16288459642SOmar Sandoval int nr = -1; 16388459642SOmar Sandoval 16488459642SOmar Sandoval index = SB_NR_TO_INDEX(sb, alloc_hint); 16588459642SOmar Sandoval 16627fae429SJens Axboe /* 16727fae429SJens Axboe * Unless we're doing round robin tag allocation, just use the 16827fae429SJens Axboe * alloc_hint to find the right word index. No point in looping 16927fae429SJens Axboe * twice in find_next_zero_bit() for that case. 17027fae429SJens Axboe */ 17127fae429SJens Axboe if (round_robin) 17227fae429SJens Axboe alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); 17327fae429SJens Axboe else 17427fae429SJens Axboe alloc_hint = 0; 17527fae429SJens Axboe 17688459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 177ea86ea2cSJens Axboe nr = sbitmap_find_bit_in_index(sb, index, alloc_hint, 178ea86ea2cSJens Axboe round_robin); 17988459642SOmar Sandoval if (nr != -1) { 18088459642SOmar Sandoval nr += index << sb->shift; 18188459642SOmar Sandoval break; 18288459642SOmar Sandoval } 18388459642SOmar Sandoval 18488459642SOmar Sandoval /* Jump to next index. */ 18588459642SOmar Sandoval alloc_hint = 0; 18627fae429SJens Axboe if (++index >= sb->map_nr) 18727fae429SJens Axboe index = 0; 18888459642SOmar Sandoval } 18988459642SOmar Sandoval 19088459642SOmar Sandoval return nr; 19188459642SOmar Sandoval } 19288459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_get); 19388459642SOmar Sandoval 194c05e6673SOmar Sandoval int sbitmap_get_shallow(struct sbitmap *sb, unsigned int alloc_hint, 195c05e6673SOmar Sandoval unsigned long shallow_depth) 196c05e6673SOmar Sandoval { 197c05e6673SOmar Sandoval unsigned int i, index; 198c05e6673SOmar Sandoval int nr = -1; 199c05e6673SOmar Sandoval 200c05e6673SOmar Sandoval index = SB_NR_TO_INDEX(sb, alloc_hint); 201c05e6673SOmar Sandoval 202c05e6673SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 203b2dbff1bSJens Axboe again: 204c05e6673SOmar Sandoval nr = __sbitmap_get_word(&sb->map[index].word, 205c05e6673SOmar Sandoval min(sb->map[index].depth, shallow_depth), 206c05e6673SOmar Sandoval SB_NR_TO_BIT(sb, alloc_hint), true); 207c05e6673SOmar Sandoval if (nr != -1) { 208c05e6673SOmar Sandoval nr += index << sb->shift; 209c05e6673SOmar Sandoval break; 210c05e6673SOmar Sandoval } 211c05e6673SOmar Sandoval 212b2dbff1bSJens Axboe if (sbitmap_deferred_clear(sb, index)) 213b2dbff1bSJens Axboe goto again; 214b2dbff1bSJens Axboe 215c05e6673SOmar Sandoval /* Jump to next index. */ 216c05e6673SOmar Sandoval index++; 217c05e6673SOmar Sandoval alloc_hint = index << sb->shift; 218c05e6673SOmar Sandoval 219c05e6673SOmar Sandoval if (index >= sb->map_nr) { 220c05e6673SOmar Sandoval index = 0; 221c05e6673SOmar Sandoval alloc_hint = 0; 222c05e6673SOmar Sandoval } 223c05e6673SOmar Sandoval } 224c05e6673SOmar Sandoval 225c05e6673SOmar Sandoval return nr; 226c05e6673SOmar Sandoval } 227c05e6673SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_get_shallow); 228c05e6673SOmar Sandoval 22988459642SOmar Sandoval bool sbitmap_any_bit_set(const struct sbitmap *sb) 23088459642SOmar Sandoval { 23188459642SOmar Sandoval unsigned int i; 23288459642SOmar Sandoval 23388459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 234b2dbff1bSJens Axboe if (sb->map[i].word & ~sb->map[i].cleared) 23588459642SOmar Sandoval return true; 23688459642SOmar Sandoval } 23788459642SOmar Sandoval return false; 23888459642SOmar Sandoval } 23988459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_any_bit_set); 24088459642SOmar Sandoval 24188459642SOmar Sandoval bool sbitmap_any_bit_clear(const struct sbitmap *sb) 24288459642SOmar Sandoval { 24388459642SOmar Sandoval unsigned int i; 24488459642SOmar Sandoval 24588459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 24688459642SOmar Sandoval const struct sbitmap_word *word = &sb->map[i]; 247b2dbff1bSJens Axboe unsigned long mask = word->word & ~word->cleared; 24888459642SOmar Sandoval unsigned long ret; 24988459642SOmar Sandoval 250b2dbff1bSJens Axboe ret = find_first_zero_bit(&mask, word->depth); 25188459642SOmar Sandoval if (ret < word->depth) 25288459642SOmar Sandoval return true; 25388459642SOmar Sandoval } 25488459642SOmar Sandoval return false; 25588459642SOmar Sandoval } 25688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear); 25788459642SOmar Sandoval 258ea86ea2cSJens Axboe static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set) 25988459642SOmar Sandoval { 26060658e0dSColin Ian King unsigned int i, weight = 0; 26188459642SOmar Sandoval 26288459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 26388459642SOmar Sandoval const struct sbitmap_word *word = &sb->map[i]; 26488459642SOmar Sandoval 265ea86ea2cSJens Axboe if (set) 26688459642SOmar Sandoval weight += bitmap_weight(&word->word, word->depth); 267ea86ea2cSJens Axboe else 268ea86ea2cSJens Axboe weight += bitmap_weight(&word->cleared, word->depth); 26988459642SOmar Sandoval } 27088459642SOmar Sandoval return weight; 27188459642SOmar Sandoval } 272ea86ea2cSJens Axboe 273ea86ea2cSJens Axboe static unsigned int sbitmap_weight(const struct sbitmap *sb) 274ea86ea2cSJens Axboe { 275ea86ea2cSJens Axboe return __sbitmap_weight(sb, true); 276ea86ea2cSJens Axboe } 277ea86ea2cSJens Axboe 278ea86ea2cSJens Axboe static unsigned int sbitmap_cleared(const struct sbitmap *sb) 279ea86ea2cSJens Axboe { 280ea86ea2cSJens Axboe return __sbitmap_weight(sb, false); 281ea86ea2cSJens Axboe } 28288459642SOmar Sandoval 28324af1ccfSOmar Sandoval void sbitmap_show(struct sbitmap *sb, struct seq_file *m) 28424af1ccfSOmar Sandoval { 28524af1ccfSOmar Sandoval seq_printf(m, "depth=%u\n", sb->depth); 286ea86ea2cSJens Axboe seq_printf(m, "busy=%u\n", sbitmap_weight(sb) - sbitmap_cleared(sb)); 287ea86ea2cSJens Axboe seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb)); 28824af1ccfSOmar Sandoval seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift); 28924af1ccfSOmar Sandoval seq_printf(m, "map_nr=%u\n", sb->map_nr); 29024af1ccfSOmar Sandoval } 29124af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_show); 29224af1ccfSOmar Sandoval 29324af1ccfSOmar Sandoval static inline void emit_byte(struct seq_file *m, unsigned int offset, u8 byte) 29424af1ccfSOmar Sandoval { 29524af1ccfSOmar Sandoval if ((offset & 0xf) == 0) { 29624af1ccfSOmar Sandoval if (offset != 0) 29724af1ccfSOmar Sandoval seq_putc(m, '\n'); 29824af1ccfSOmar Sandoval seq_printf(m, "%08x:", offset); 29924af1ccfSOmar Sandoval } 30024af1ccfSOmar Sandoval if ((offset & 0x1) == 0) 30124af1ccfSOmar Sandoval seq_putc(m, ' '); 30224af1ccfSOmar Sandoval seq_printf(m, "%02x", byte); 30324af1ccfSOmar Sandoval } 30424af1ccfSOmar Sandoval 30524af1ccfSOmar Sandoval void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m) 30624af1ccfSOmar Sandoval { 30724af1ccfSOmar Sandoval u8 byte = 0; 30824af1ccfSOmar Sandoval unsigned int byte_bits = 0; 30924af1ccfSOmar Sandoval unsigned int offset = 0; 31024af1ccfSOmar Sandoval int i; 31124af1ccfSOmar Sandoval 31224af1ccfSOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 31324af1ccfSOmar Sandoval unsigned long word = READ_ONCE(sb->map[i].word); 31424af1ccfSOmar Sandoval unsigned int word_bits = READ_ONCE(sb->map[i].depth); 31524af1ccfSOmar Sandoval 31624af1ccfSOmar Sandoval while (word_bits > 0) { 31724af1ccfSOmar Sandoval unsigned int bits = min(8 - byte_bits, word_bits); 31824af1ccfSOmar Sandoval 31924af1ccfSOmar Sandoval byte |= (word & (BIT(bits) - 1)) << byte_bits; 32024af1ccfSOmar Sandoval byte_bits += bits; 32124af1ccfSOmar Sandoval if (byte_bits == 8) { 32224af1ccfSOmar Sandoval emit_byte(m, offset, byte); 32324af1ccfSOmar Sandoval byte = 0; 32424af1ccfSOmar Sandoval byte_bits = 0; 32524af1ccfSOmar Sandoval offset++; 32624af1ccfSOmar Sandoval } 32724af1ccfSOmar Sandoval word >>= bits; 32824af1ccfSOmar Sandoval word_bits -= bits; 32924af1ccfSOmar Sandoval } 33024af1ccfSOmar Sandoval } 33124af1ccfSOmar Sandoval if (byte_bits) { 33224af1ccfSOmar Sandoval emit_byte(m, offset, byte); 33324af1ccfSOmar Sandoval offset++; 33424af1ccfSOmar Sandoval } 33524af1ccfSOmar Sandoval if (offset) 33624af1ccfSOmar Sandoval seq_putc(m, '\n'); 33724af1ccfSOmar Sandoval } 33824af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_bitmap_show); 33924af1ccfSOmar Sandoval 340a3275539SOmar Sandoval static unsigned int sbq_calc_wake_batch(struct sbitmap_queue *sbq, 341a3275539SOmar Sandoval unsigned int depth) 34288459642SOmar Sandoval { 34388459642SOmar Sandoval unsigned int wake_batch; 344a3275539SOmar Sandoval unsigned int shallow_depth; 34588459642SOmar Sandoval 34688459642SOmar Sandoval /* 34788459642SOmar Sandoval * For each batch, we wake up one queue. We need to make sure that our 348a3275539SOmar Sandoval * batch size is small enough that the full depth of the bitmap, 349a3275539SOmar Sandoval * potentially limited by a shallow depth, is enough to wake up all of 350a3275539SOmar Sandoval * the queues. 351a3275539SOmar Sandoval * 352a3275539SOmar Sandoval * Each full word of the bitmap has bits_per_word bits, and there might 353a3275539SOmar Sandoval * be a partial word. There are depth / bits_per_word full words and 354a3275539SOmar Sandoval * depth % bits_per_word bits left over. In bitwise arithmetic: 355a3275539SOmar Sandoval * 356a3275539SOmar Sandoval * bits_per_word = 1 << shift 357a3275539SOmar Sandoval * depth / bits_per_word = depth >> shift 358a3275539SOmar Sandoval * depth % bits_per_word = depth & ((1 << shift) - 1) 359a3275539SOmar Sandoval * 360a3275539SOmar Sandoval * Each word can be limited to sbq->min_shallow_depth bits. 36188459642SOmar Sandoval */ 362a3275539SOmar Sandoval shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth); 363a3275539SOmar Sandoval depth = ((depth >> sbq->sb.shift) * shallow_depth + 364a3275539SOmar Sandoval min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth)); 365a3275539SOmar Sandoval wake_batch = clamp_t(unsigned int, depth / SBQ_WAIT_QUEUES, 1, 366a3275539SOmar Sandoval SBQ_WAKE_BATCH); 36788459642SOmar Sandoval 36888459642SOmar Sandoval return wake_batch; 36988459642SOmar Sandoval } 37088459642SOmar Sandoval 37188459642SOmar Sandoval int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, 372f4a644dbSOmar Sandoval int shift, bool round_robin, gfp_t flags, int node) 37388459642SOmar Sandoval { 37488459642SOmar Sandoval int ret; 37588459642SOmar Sandoval int i; 37688459642SOmar Sandoval 37788459642SOmar Sandoval ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node); 37888459642SOmar Sandoval if (ret) 37988459642SOmar Sandoval return ret; 38088459642SOmar Sandoval 38140aabb67SOmar Sandoval sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags); 38240aabb67SOmar Sandoval if (!sbq->alloc_hint) { 38340aabb67SOmar Sandoval sbitmap_free(&sbq->sb); 38440aabb67SOmar Sandoval return -ENOMEM; 38540aabb67SOmar Sandoval } 38640aabb67SOmar Sandoval 38798d95416SOmar Sandoval if (depth && !round_robin) { 38898d95416SOmar Sandoval for_each_possible_cpu(i) 38998d95416SOmar Sandoval *per_cpu_ptr(sbq->alloc_hint, i) = prandom_u32() % depth; 39098d95416SOmar Sandoval } 39198d95416SOmar Sandoval 392a3275539SOmar Sandoval sbq->min_shallow_depth = UINT_MAX; 393a3275539SOmar Sandoval sbq->wake_batch = sbq_calc_wake_batch(sbq, depth); 39488459642SOmar Sandoval atomic_set(&sbq->wake_index, 0); 3955d2ee712SJens Axboe atomic_set(&sbq->ws_active, 0); 39688459642SOmar Sandoval 39748e28166SOmar Sandoval sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node); 39888459642SOmar Sandoval if (!sbq->ws) { 39940aabb67SOmar Sandoval free_percpu(sbq->alloc_hint); 40088459642SOmar Sandoval sbitmap_free(&sbq->sb); 40188459642SOmar Sandoval return -ENOMEM; 40288459642SOmar Sandoval } 40388459642SOmar Sandoval 40488459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 40588459642SOmar Sandoval init_waitqueue_head(&sbq->ws[i].wait); 40688459642SOmar Sandoval atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch); 40788459642SOmar Sandoval } 408f4a644dbSOmar Sandoval 409f4a644dbSOmar Sandoval sbq->round_robin = round_robin; 41088459642SOmar Sandoval return 0; 41188459642SOmar Sandoval } 41288459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_init_node); 41388459642SOmar Sandoval 414a3275539SOmar Sandoval static void sbitmap_queue_update_wake_batch(struct sbitmap_queue *sbq, 415a3275539SOmar Sandoval unsigned int depth) 41688459642SOmar Sandoval { 417a3275539SOmar Sandoval unsigned int wake_batch = sbq_calc_wake_batch(sbq, depth); 4186c0ca7aeSOmar Sandoval int i; 4196c0ca7aeSOmar Sandoval 4206c0ca7aeSOmar Sandoval if (sbq->wake_batch != wake_batch) { 4216c0ca7aeSOmar Sandoval WRITE_ONCE(sbq->wake_batch, wake_batch); 4226c0ca7aeSOmar Sandoval /* 423e6fc4649SMing Lei * Pairs with the memory barrier in sbitmap_queue_wake_up() 424e6fc4649SMing Lei * to ensure that the batch size is updated before the wait 425e6fc4649SMing Lei * counts. 4266c0ca7aeSOmar Sandoval */ 427a0934fd2SAndrea Parri smp_mb(); 4286c0ca7aeSOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) 4296c0ca7aeSOmar Sandoval atomic_set(&sbq->ws[i].wait_cnt, 1); 4306c0ca7aeSOmar Sandoval } 431a3275539SOmar Sandoval } 432a3275539SOmar Sandoval 433a3275539SOmar Sandoval void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth) 434a3275539SOmar Sandoval { 435a3275539SOmar Sandoval sbitmap_queue_update_wake_batch(sbq, depth); 43688459642SOmar Sandoval sbitmap_resize(&sbq->sb, depth); 43788459642SOmar Sandoval } 43888459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_resize); 43988459642SOmar Sandoval 440f4a644dbSOmar Sandoval int __sbitmap_queue_get(struct sbitmap_queue *sbq) 44140aabb67SOmar Sandoval { 44205fd095dSOmar Sandoval unsigned int hint, depth; 44340aabb67SOmar Sandoval int nr; 44440aabb67SOmar Sandoval 44540aabb67SOmar Sandoval hint = this_cpu_read(*sbq->alloc_hint); 44605fd095dSOmar Sandoval depth = READ_ONCE(sbq->sb.depth); 44705fd095dSOmar Sandoval if (unlikely(hint >= depth)) { 44805fd095dSOmar Sandoval hint = depth ? prandom_u32() % depth : 0; 44905fd095dSOmar Sandoval this_cpu_write(*sbq->alloc_hint, hint); 45005fd095dSOmar Sandoval } 451f4a644dbSOmar Sandoval nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin); 45240aabb67SOmar Sandoval 45340aabb67SOmar Sandoval if (nr == -1) { 45440aabb67SOmar Sandoval /* If the map is full, a hint won't do us much good. */ 45540aabb67SOmar Sandoval this_cpu_write(*sbq->alloc_hint, 0); 456f4a644dbSOmar Sandoval } else if (nr == hint || unlikely(sbq->round_robin)) { 45740aabb67SOmar Sandoval /* Only update the hint if we used it. */ 45840aabb67SOmar Sandoval hint = nr + 1; 45905fd095dSOmar Sandoval if (hint >= depth - 1) 46040aabb67SOmar Sandoval hint = 0; 46140aabb67SOmar Sandoval this_cpu_write(*sbq->alloc_hint, hint); 46240aabb67SOmar Sandoval } 46340aabb67SOmar Sandoval 46440aabb67SOmar Sandoval return nr; 46540aabb67SOmar Sandoval } 46640aabb67SOmar Sandoval EXPORT_SYMBOL_GPL(__sbitmap_queue_get); 46740aabb67SOmar Sandoval 468c05e6673SOmar Sandoval int __sbitmap_queue_get_shallow(struct sbitmap_queue *sbq, 469c05e6673SOmar Sandoval unsigned int shallow_depth) 470c05e6673SOmar Sandoval { 471c05e6673SOmar Sandoval unsigned int hint, depth; 472c05e6673SOmar Sandoval int nr; 473c05e6673SOmar Sandoval 47461445b56SOmar Sandoval WARN_ON_ONCE(shallow_depth < sbq->min_shallow_depth); 47561445b56SOmar Sandoval 476c05e6673SOmar Sandoval hint = this_cpu_read(*sbq->alloc_hint); 477c05e6673SOmar Sandoval depth = READ_ONCE(sbq->sb.depth); 478c05e6673SOmar Sandoval if (unlikely(hint >= depth)) { 479c05e6673SOmar Sandoval hint = depth ? prandom_u32() % depth : 0; 480c05e6673SOmar Sandoval this_cpu_write(*sbq->alloc_hint, hint); 481c05e6673SOmar Sandoval } 482c05e6673SOmar Sandoval nr = sbitmap_get_shallow(&sbq->sb, hint, shallow_depth); 483c05e6673SOmar Sandoval 484c05e6673SOmar Sandoval if (nr == -1) { 485c05e6673SOmar Sandoval /* If the map is full, a hint won't do us much good. */ 486c05e6673SOmar Sandoval this_cpu_write(*sbq->alloc_hint, 0); 487c05e6673SOmar Sandoval } else if (nr == hint || unlikely(sbq->round_robin)) { 488c05e6673SOmar Sandoval /* Only update the hint if we used it. */ 489c05e6673SOmar Sandoval hint = nr + 1; 490c05e6673SOmar Sandoval if (hint >= depth - 1) 491c05e6673SOmar Sandoval hint = 0; 492c05e6673SOmar Sandoval this_cpu_write(*sbq->alloc_hint, hint); 493c05e6673SOmar Sandoval } 494c05e6673SOmar Sandoval 495c05e6673SOmar Sandoval return nr; 496c05e6673SOmar Sandoval } 497c05e6673SOmar Sandoval EXPORT_SYMBOL_GPL(__sbitmap_queue_get_shallow); 498c05e6673SOmar Sandoval 499a3275539SOmar Sandoval void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq, 500a3275539SOmar Sandoval unsigned int min_shallow_depth) 501a3275539SOmar Sandoval { 502a3275539SOmar Sandoval sbq->min_shallow_depth = min_shallow_depth; 503a3275539SOmar Sandoval sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth); 504a3275539SOmar Sandoval } 505a3275539SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_min_shallow_depth); 506a3275539SOmar Sandoval 50788459642SOmar Sandoval static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq) 50888459642SOmar Sandoval { 50988459642SOmar Sandoval int i, wake_index; 51088459642SOmar Sandoval 5115d2ee712SJens Axboe if (!atomic_read(&sbq->ws_active)) 5125d2ee712SJens Axboe return NULL; 5135d2ee712SJens Axboe 51488459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index); 51588459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 51688459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index]; 51788459642SOmar Sandoval 51888459642SOmar Sandoval if (waitqueue_active(&ws->wait)) { 51988459642SOmar Sandoval int o = atomic_read(&sbq->wake_index); 52088459642SOmar Sandoval 52188459642SOmar Sandoval if (wake_index != o) 52288459642SOmar Sandoval atomic_cmpxchg(&sbq->wake_index, o, wake_index); 52388459642SOmar Sandoval return ws; 52488459642SOmar Sandoval } 52588459642SOmar Sandoval 52688459642SOmar Sandoval wake_index = sbq_index_inc(wake_index); 52788459642SOmar Sandoval } 52888459642SOmar Sandoval 52988459642SOmar Sandoval return NULL; 53088459642SOmar Sandoval } 53188459642SOmar Sandoval 532c854ab57SJens Axboe static bool __sbq_wake_up(struct sbitmap_queue *sbq) 53388459642SOmar Sandoval { 53488459642SOmar Sandoval struct sbq_wait_state *ws; 5356c0ca7aeSOmar Sandoval unsigned int wake_batch; 53688459642SOmar Sandoval int wait_cnt; 53788459642SOmar Sandoval 53888459642SOmar Sandoval ws = sbq_wake_ptr(sbq); 53988459642SOmar Sandoval if (!ws) 540c854ab57SJens Axboe return false; 54188459642SOmar Sandoval 54288459642SOmar Sandoval wait_cnt = atomic_dec_return(&ws->wait_cnt); 5436c0ca7aeSOmar Sandoval if (wait_cnt <= 0) { 544c854ab57SJens Axboe int ret; 545c854ab57SJens Axboe 5466c0ca7aeSOmar Sandoval wake_batch = READ_ONCE(sbq->wake_batch); 547c854ab57SJens Axboe 5486c0ca7aeSOmar Sandoval /* 5496c0ca7aeSOmar Sandoval * Pairs with the memory barrier in sbitmap_queue_resize() to 5506c0ca7aeSOmar Sandoval * ensure that we see the batch size update before the wait 5516c0ca7aeSOmar Sandoval * count is reset. 5526c0ca7aeSOmar Sandoval */ 5536c0ca7aeSOmar Sandoval smp_mb__before_atomic(); 554c854ab57SJens Axboe 5556c0ca7aeSOmar Sandoval /* 556c854ab57SJens Axboe * For concurrent callers of this, the one that failed the 557c854ab57SJens Axboe * atomic_cmpxhcg() race should call this function again 558c854ab57SJens Axboe * to wakeup a new batch on a different 'ws'. 5596c0ca7aeSOmar Sandoval */ 560c854ab57SJens Axboe ret = atomic_cmpxchg(&ws->wait_cnt, wait_cnt, wake_batch); 561c854ab57SJens Axboe if (ret == wait_cnt) { 56288459642SOmar Sandoval sbq_index_atomic_inc(&sbq->wake_index); 5634e5dff41SJens Axboe wake_up_nr(&ws->wait, wake_batch); 564c854ab57SJens Axboe return false; 56588459642SOmar Sandoval } 566c854ab57SJens Axboe 567c854ab57SJens Axboe return true; 568c854ab57SJens Axboe } 569c854ab57SJens Axboe 570c854ab57SJens Axboe return false; 571c854ab57SJens Axboe } 572c854ab57SJens Axboe 573e6fc4649SMing Lei void sbitmap_queue_wake_up(struct sbitmap_queue *sbq) 574c854ab57SJens Axboe { 575c854ab57SJens Axboe while (__sbq_wake_up(sbq)) 576c854ab57SJens Axboe ; 57788459642SOmar Sandoval } 578e6fc4649SMing Lei EXPORT_SYMBOL_GPL(sbitmap_queue_wake_up); 57988459642SOmar Sandoval 58040aabb67SOmar Sandoval void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr, 581f4a644dbSOmar Sandoval unsigned int cpu) 58288459642SOmar Sandoval { 583e6d1fa58SMing Lei /* 584e6d1fa58SMing Lei * Once the clear bit is set, the bit may be allocated out. 585e6d1fa58SMing Lei * 586e6d1fa58SMing Lei * Orders READ/WRITE on the asssociated instance(such as request 587e6d1fa58SMing Lei * of blk_mq) by this bit for avoiding race with re-allocation, 588e6d1fa58SMing Lei * and its pair is the memory barrier implied in __sbitmap_get_word. 589e6d1fa58SMing Lei * 590e6d1fa58SMing Lei * One invariant is that the clear bit has to be zero when the bit 591e6d1fa58SMing Lei * is in use. 592e6d1fa58SMing Lei */ 593e6d1fa58SMing Lei smp_mb__before_atomic(); 594ea86ea2cSJens Axboe sbitmap_deferred_clear_bit(&sbq->sb, nr); 595ea86ea2cSJens Axboe 596e6fc4649SMing Lei /* 597e6fc4649SMing Lei * Pairs with the memory barrier in set_current_state() to ensure the 598e6fc4649SMing Lei * proper ordering of clear_bit_unlock()/waitqueue_active() in the waker 599e6fc4649SMing Lei * and test_and_set_bit_lock()/prepare_to_wait()/finish_wait() in the 600e6fc4649SMing Lei * waiter. See the comment on waitqueue_active(). 601e6fc4649SMing Lei */ 602e6fc4649SMing Lei smp_mb__after_atomic(); 603e6fc4649SMing Lei sbitmap_queue_wake_up(sbq); 604e6fc4649SMing Lei 6055c64a8dfSOmar Sandoval if (likely(!sbq->round_robin && nr < sbq->sb.depth)) 60640aabb67SOmar Sandoval *per_cpu_ptr(sbq->alloc_hint, cpu) = nr; 60788459642SOmar Sandoval } 60888459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_clear); 60988459642SOmar Sandoval 61088459642SOmar Sandoval void sbitmap_queue_wake_all(struct sbitmap_queue *sbq) 61188459642SOmar Sandoval { 61288459642SOmar Sandoval int i, wake_index; 61388459642SOmar Sandoval 61488459642SOmar Sandoval /* 615f66227deSOmar Sandoval * Pairs with the memory barrier in set_current_state() like in 616e6fc4649SMing Lei * sbitmap_queue_wake_up(). 61788459642SOmar Sandoval */ 61888459642SOmar Sandoval smp_mb(); 61988459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index); 62088459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 62188459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index]; 62288459642SOmar Sandoval 62388459642SOmar Sandoval if (waitqueue_active(&ws->wait)) 62488459642SOmar Sandoval wake_up(&ws->wait); 62588459642SOmar Sandoval 62688459642SOmar Sandoval wake_index = sbq_index_inc(wake_index); 62788459642SOmar Sandoval } 62888459642SOmar Sandoval } 62988459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all); 63024af1ccfSOmar Sandoval 63124af1ccfSOmar Sandoval void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m) 63224af1ccfSOmar Sandoval { 63324af1ccfSOmar Sandoval bool first; 63424af1ccfSOmar Sandoval int i; 63524af1ccfSOmar Sandoval 63624af1ccfSOmar Sandoval sbitmap_show(&sbq->sb, m); 63724af1ccfSOmar Sandoval 63824af1ccfSOmar Sandoval seq_puts(m, "alloc_hint={"); 63924af1ccfSOmar Sandoval first = true; 64024af1ccfSOmar Sandoval for_each_possible_cpu(i) { 64124af1ccfSOmar Sandoval if (!first) 64224af1ccfSOmar Sandoval seq_puts(m, ", "); 64324af1ccfSOmar Sandoval first = false; 64424af1ccfSOmar Sandoval seq_printf(m, "%u", *per_cpu_ptr(sbq->alloc_hint, i)); 64524af1ccfSOmar Sandoval } 64624af1ccfSOmar Sandoval seq_puts(m, "}\n"); 64724af1ccfSOmar Sandoval 64824af1ccfSOmar Sandoval seq_printf(m, "wake_batch=%u\n", sbq->wake_batch); 64924af1ccfSOmar Sandoval seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index)); 6505d2ee712SJens Axboe seq_printf(m, "ws_active=%d\n", atomic_read(&sbq->ws_active)); 65124af1ccfSOmar Sandoval 65224af1ccfSOmar Sandoval seq_puts(m, "ws={\n"); 65324af1ccfSOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 65424af1ccfSOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[i]; 65524af1ccfSOmar Sandoval 65624af1ccfSOmar Sandoval seq_printf(m, "\t{.wait_cnt=%d, .wait=%s},\n", 65724af1ccfSOmar Sandoval atomic_read(&ws->wait_cnt), 65824af1ccfSOmar Sandoval waitqueue_active(&ws->wait) ? "active" : "inactive"); 65924af1ccfSOmar Sandoval } 66024af1ccfSOmar Sandoval seq_puts(m, "}\n"); 66124af1ccfSOmar Sandoval 66224af1ccfSOmar Sandoval seq_printf(m, "round_robin=%d\n", sbq->round_robin); 663a3275539SOmar Sandoval seq_printf(m, "min_shallow_depth=%u\n", sbq->min_shallow_depth); 66424af1ccfSOmar Sandoval } 66524af1ccfSOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_show); 6665d2ee712SJens Axboe 6679f6b7ef6SJens Axboe void sbitmap_add_wait_queue(struct sbitmap_queue *sbq, 6689f6b7ef6SJens Axboe struct sbq_wait_state *ws, 6699f6b7ef6SJens Axboe struct sbq_wait *sbq_wait) 6709f6b7ef6SJens Axboe { 6719f6b7ef6SJens Axboe if (!sbq_wait->sbq) { 6729f6b7ef6SJens Axboe sbq_wait->sbq = sbq; 6739f6b7ef6SJens Axboe atomic_inc(&sbq->ws_active); 6749f6b7ef6SJens Axboe } 6759f6b7ef6SJens Axboe add_wait_queue(&ws->wait, &sbq_wait->wait); 6769f6b7ef6SJens Axboe } 6779f6b7ef6SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_add_wait_queue); 6789f6b7ef6SJens Axboe 6799f6b7ef6SJens Axboe void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait) 6809f6b7ef6SJens Axboe { 6819f6b7ef6SJens Axboe list_del_init(&sbq_wait->wait.entry); 6829f6b7ef6SJens Axboe if (sbq_wait->sbq) { 6839f6b7ef6SJens Axboe atomic_dec(&sbq_wait->sbq->ws_active); 6849f6b7ef6SJens Axboe sbq_wait->sbq = NULL; 6859f6b7ef6SJens Axboe } 6869f6b7ef6SJens Axboe } 6879f6b7ef6SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_del_wait_queue); 6889f6b7ef6SJens Axboe 6895d2ee712SJens Axboe void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq, 6905d2ee712SJens Axboe struct sbq_wait_state *ws, 6915d2ee712SJens Axboe struct sbq_wait *sbq_wait, int state) 6925d2ee712SJens Axboe { 6939f6b7ef6SJens Axboe if (!sbq_wait->sbq) { 6945d2ee712SJens Axboe atomic_inc(&sbq->ws_active); 6959f6b7ef6SJens Axboe sbq_wait->sbq = sbq; 6965d2ee712SJens Axboe } 6975d2ee712SJens Axboe prepare_to_wait_exclusive(&ws->wait, &sbq_wait->wait, state); 6985d2ee712SJens Axboe } 6995d2ee712SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_prepare_to_wait); 7005d2ee712SJens Axboe 7015d2ee712SJens Axboe void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws, 7025d2ee712SJens Axboe struct sbq_wait *sbq_wait) 7035d2ee712SJens Axboe { 7045d2ee712SJens Axboe finish_wait(&ws->wait, &sbq_wait->wait); 7059f6b7ef6SJens Axboe if (sbq_wait->sbq) { 7065d2ee712SJens Axboe atomic_dec(&sbq->ws_active); 7079f6b7ef6SJens Axboe sbq_wait->sbq = NULL; 7085d2ee712SJens Axboe } 7095d2ee712SJens Axboe } 7105d2ee712SJens Axboe EXPORT_SYMBOL_GPL(sbitmap_finish_wait); 711