188459642SOmar Sandoval /* 288459642SOmar Sandoval * Copyright (C) 2016 Facebook 388459642SOmar Sandoval * Copyright (C) 2013-2014 Jens Axboe 488459642SOmar Sandoval * 588459642SOmar Sandoval * This program is free software; you can redistribute it and/or 688459642SOmar Sandoval * modify it under the terms of the GNU General Public 788459642SOmar Sandoval * License v2 as published by the Free Software Foundation. 888459642SOmar Sandoval * 988459642SOmar Sandoval * This program is distributed in the hope that it will be useful, 1088459642SOmar Sandoval * but WITHOUT ANY WARRANTY; without even the implied warranty of 1188459642SOmar Sandoval * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1288459642SOmar Sandoval * General Public License for more details. 1388459642SOmar Sandoval * 1488459642SOmar Sandoval * You should have received a copy of the GNU General Public License 1588459642SOmar Sandoval * along with this program. If not, see <https://www.gnu.org/licenses/>. 1688459642SOmar Sandoval */ 1788459642SOmar Sandoval 1888459642SOmar Sandoval #include <linux/sbitmap.h> 1988459642SOmar Sandoval 2088459642SOmar Sandoval int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, 2188459642SOmar Sandoval gfp_t flags, int node) 2288459642SOmar Sandoval { 2388459642SOmar Sandoval unsigned int bits_per_word; 2488459642SOmar Sandoval unsigned int i; 2588459642SOmar Sandoval 2688459642SOmar Sandoval if (shift < 0) { 2788459642SOmar Sandoval shift = ilog2(BITS_PER_LONG); 2888459642SOmar Sandoval /* 2988459642SOmar Sandoval * If the bitmap is small, shrink the number of bits per word so 3088459642SOmar Sandoval * we spread over a few cachelines, at least. If less than 4 3188459642SOmar Sandoval * bits, just forget about it, it's not going to work optimally 3288459642SOmar Sandoval * anyway. 3388459642SOmar Sandoval */ 3488459642SOmar Sandoval if (depth >= 4) { 3588459642SOmar Sandoval while ((4U << shift) > depth) 3688459642SOmar Sandoval shift--; 3788459642SOmar Sandoval } 3888459642SOmar Sandoval } 3988459642SOmar Sandoval bits_per_word = 1U << shift; 4088459642SOmar Sandoval if (bits_per_word > BITS_PER_LONG) 4188459642SOmar Sandoval return -EINVAL; 4288459642SOmar Sandoval 4388459642SOmar Sandoval sb->shift = shift; 4488459642SOmar Sandoval sb->depth = depth; 4588459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 4688459642SOmar Sandoval 4788459642SOmar Sandoval if (depth == 0) { 4888459642SOmar Sandoval sb->map = NULL; 4988459642SOmar Sandoval return 0; 5088459642SOmar Sandoval } 5188459642SOmar Sandoval 5288459642SOmar Sandoval sb->map = kzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node); 5388459642SOmar Sandoval if (!sb->map) 5488459642SOmar Sandoval return -ENOMEM; 5588459642SOmar Sandoval 5688459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 5788459642SOmar Sandoval sb->map[i].depth = min(depth, bits_per_word); 5888459642SOmar Sandoval depth -= sb->map[i].depth; 5988459642SOmar Sandoval } 6088459642SOmar Sandoval return 0; 6188459642SOmar Sandoval } 6288459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_init_node); 6388459642SOmar Sandoval 6488459642SOmar Sandoval void sbitmap_resize(struct sbitmap *sb, unsigned int depth) 6588459642SOmar Sandoval { 6688459642SOmar Sandoval unsigned int bits_per_word = 1U << sb->shift; 6788459642SOmar Sandoval unsigned int i; 6888459642SOmar Sandoval 6988459642SOmar Sandoval sb->depth = depth; 7088459642SOmar Sandoval sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 7188459642SOmar Sandoval 7288459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 7388459642SOmar Sandoval sb->map[i].depth = min(depth, bits_per_word); 7488459642SOmar Sandoval depth -= sb->map[i].depth; 7588459642SOmar Sandoval } 7688459642SOmar Sandoval } 7788459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_resize); 7888459642SOmar Sandoval 7988459642SOmar Sandoval static int __sbitmap_get_word(struct sbitmap_word *word, unsigned int hint, 8088459642SOmar Sandoval bool wrap) 8188459642SOmar Sandoval { 8288459642SOmar Sandoval unsigned int orig_hint = hint; 8388459642SOmar Sandoval int nr; 8488459642SOmar Sandoval 8588459642SOmar Sandoval while (1) { 8688459642SOmar Sandoval nr = find_next_zero_bit(&word->word, word->depth, hint); 8788459642SOmar Sandoval if (unlikely(nr >= word->depth)) { 8888459642SOmar Sandoval /* 8988459642SOmar Sandoval * We started with an offset, and we didn't reset the 9088459642SOmar Sandoval * offset to 0 in a failure case, so start from 0 to 9188459642SOmar Sandoval * exhaust the map. 9288459642SOmar Sandoval */ 9388459642SOmar Sandoval if (orig_hint && hint && wrap) { 9488459642SOmar Sandoval hint = orig_hint = 0; 9588459642SOmar Sandoval continue; 9688459642SOmar Sandoval } 9788459642SOmar Sandoval return -1; 9888459642SOmar Sandoval } 9988459642SOmar Sandoval 10088459642SOmar Sandoval if (!test_and_set_bit(nr, &word->word)) 10188459642SOmar Sandoval break; 10288459642SOmar Sandoval 10388459642SOmar Sandoval hint = nr + 1; 10488459642SOmar Sandoval if (hint >= word->depth - 1) 10588459642SOmar Sandoval hint = 0; 10688459642SOmar Sandoval } 10788459642SOmar Sandoval 10888459642SOmar Sandoval return nr; 10988459642SOmar Sandoval } 11088459642SOmar Sandoval 11188459642SOmar Sandoval int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin) 11288459642SOmar Sandoval { 11388459642SOmar Sandoval unsigned int i, index; 11488459642SOmar Sandoval int nr = -1; 11588459642SOmar Sandoval 11688459642SOmar Sandoval index = SB_NR_TO_INDEX(sb, alloc_hint); 11788459642SOmar Sandoval 11888459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 11988459642SOmar Sandoval nr = __sbitmap_get_word(&sb->map[index], 12088459642SOmar Sandoval SB_NR_TO_BIT(sb, alloc_hint), 12188459642SOmar Sandoval !round_robin); 12288459642SOmar Sandoval if (nr != -1) { 12388459642SOmar Sandoval nr += index << sb->shift; 12488459642SOmar Sandoval break; 12588459642SOmar Sandoval } 12688459642SOmar Sandoval 12788459642SOmar Sandoval /* Jump to next index. */ 12888459642SOmar Sandoval index++; 12988459642SOmar Sandoval alloc_hint = index << sb->shift; 13088459642SOmar Sandoval 13188459642SOmar Sandoval if (index >= sb->map_nr) { 13288459642SOmar Sandoval index = 0; 13388459642SOmar Sandoval alloc_hint = 0; 13488459642SOmar Sandoval } 13588459642SOmar Sandoval } 13688459642SOmar Sandoval 13788459642SOmar Sandoval return nr; 13888459642SOmar Sandoval } 13988459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_get); 14088459642SOmar Sandoval 14188459642SOmar Sandoval bool sbitmap_any_bit_set(const struct sbitmap *sb) 14288459642SOmar Sandoval { 14388459642SOmar Sandoval unsigned int i; 14488459642SOmar Sandoval 14588459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 14688459642SOmar Sandoval if (sb->map[i].word) 14788459642SOmar Sandoval return true; 14888459642SOmar Sandoval } 14988459642SOmar Sandoval return false; 15088459642SOmar Sandoval } 15188459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_any_bit_set); 15288459642SOmar Sandoval 15388459642SOmar Sandoval bool sbitmap_any_bit_clear(const struct sbitmap *sb) 15488459642SOmar Sandoval { 15588459642SOmar Sandoval unsigned int i; 15688459642SOmar Sandoval 15788459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 15888459642SOmar Sandoval const struct sbitmap_word *word = &sb->map[i]; 15988459642SOmar Sandoval unsigned long ret; 16088459642SOmar Sandoval 16188459642SOmar Sandoval ret = find_first_zero_bit(&word->word, word->depth); 16288459642SOmar Sandoval if (ret < word->depth) 16388459642SOmar Sandoval return true; 16488459642SOmar Sandoval } 16588459642SOmar Sandoval return false; 16688459642SOmar Sandoval } 16788459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear); 16888459642SOmar Sandoval 16988459642SOmar Sandoval unsigned int sbitmap_weight(const struct sbitmap *sb) 17088459642SOmar Sandoval { 17188459642SOmar Sandoval unsigned int i, weight; 17288459642SOmar Sandoval 17388459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 17488459642SOmar Sandoval const struct sbitmap_word *word = &sb->map[i]; 17588459642SOmar Sandoval 17688459642SOmar Sandoval weight += bitmap_weight(&word->word, word->depth); 17788459642SOmar Sandoval } 17888459642SOmar Sandoval return weight; 17988459642SOmar Sandoval } 18088459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_weight); 18188459642SOmar Sandoval 18288459642SOmar Sandoval static unsigned int sbq_calc_wake_batch(unsigned int depth) 18388459642SOmar Sandoval { 18488459642SOmar Sandoval unsigned int wake_batch; 18588459642SOmar Sandoval 18688459642SOmar Sandoval /* 18788459642SOmar Sandoval * For each batch, we wake up one queue. We need to make sure that our 18888459642SOmar Sandoval * batch size is small enough that the full depth of the bitmap is 18988459642SOmar Sandoval * enough to wake up all of the queues. 19088459642SOmar Sandoval */ 19188459642SOmar Sandoval wake_batch = SBQ_WAKE_BATCH; 19288459642SOmar Sandoval if (wake_batch > depth / SBQ_WAIT_QUEUES) 19388459642SOmar Sandoval wake_batch = max(1U, depth / SBQ_WAIT_QUEUES); 19488459642SOmar Sandoval 19588459642SOmar Sandoval return wake_batch; 19688459642SOmar Sandoval } 19788459642SOmar Sandoval 19888459642SOmar Sandoval int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, 199*f4a644dbSOmar Sandoval int shift, bool round_robin, gfp_t flags, int node) 20088459642SOmar Sandoval { 20188459642SOmar Sandoval int ret; 20288459642SOmar Sandoval int i; 20388459642SOmar Sandoval 20488459642SOmar Sandoval ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node); 20588459642SOmar Sandoval if (ret) 20688459642SOmar Sandoval return ret; 20788459642SOmar Sandoval 20840aabb67SOmar Sandoval sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags); 20940aabb67SOmar Sandoval if (!sbq->alloc_hint) { 21040aabb67SOmar Sandoval sbitmap_free(&sbq->sb); 21140aabb67SOmar Sandoval return -ENOMEM; 21240aabb67SOmar Sandoval } 21340aabb67SOmar Sandoval 21488459642SOmar Sandoval sbq->wake_batch = sbq_calc_wake_batch(depth); 21588459642SOmar Sandoval atomic_set(&sbq->wake_index, 0); 21688459642SOmar Sandoval 21748e28166SOmar Sandoval sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node); 21888459642SOmar Sandoval if (!sbq->ws) { 21940aabb67SOmar Sandoval free_percpu(sbq->alloc_hint); 22088459642SOmar Sandoval sbitmap_free(&sbq->sb); 22188459642SOmar Sandoval return -ENOMEM; 22288459642SOmar Sandoval } 22388459642SOmar Sandoval 22488459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 22588459642SOmar Sandoval init_waitqueue_head(&sbq->ws[i].wait); 22688459642SOmar Sandoval atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch); 22788459642SOmar Sandoval } 228*f4a644dbSOmar Sandoval 229*f4a644dbSOmar Sandoval sbq->round_robin = round_robin; 23088459642SOmar Sandoval return 0; 23188459642SOmar Sandoval } 23288459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_init_node); 23388459642SOmar Sandoval 23488459642SOmar Sandoval void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth) 23588459642SOmar Sandoval { 23688459642SOmar Sandoval sbq->wake_batch = sbq_calc_wake_batch(depth); 23788459642SOmar Sandoval sbitmap_resize(&sbq->sb, depth); 23888459642SOmar Sandoval } 23988459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_resize); 24088459642SOmar Sandoval 241*f4a644dbSOmar Sandoval int __sbitmap_queue_get(struct sbitmap_queue *sbq) 24240aabb67SOmar Sandoval { 24340aabb67SOmar Sandoval unsigned int hint; 24440aabb67SOmar Sandoval int nr; 24540aabb67SOmar Sandoval 24640aabb67SOmar Sandoval hint = this_cpu_read(*sbq->alloc_hint); 247*f4a644dbSOmar Sandoval nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin); 24840aabb67SOmar Sandoval 24940aabb67SOmar Sandoval if (nr == -1) { 25040aabb67SOmar Sandoval /* If the map is full, a hint won't do us much good. */ 25140aabb67SOmar Sandoval this_cpu_write(*sbq->alloc_hint, 0); 252*f4a644dbSOmar Sandoval } else if (nr == hint || unlikely(sbq->round_robin)) { 25340aabb67SOmar Sandoval /* Only update the hint if we used it. */ 25440aabb67SOmar Sandoval hint = nr + 1; 25540aabb67SOmar Sandoval if (hint >= sbq->sb.depth - 1) 25640aabb67SOmar Sandoval hint = 0; 25740aabb67SOmar Sandoval this_cpu_write(*sbq->alloc_hint, hint); 25840aabb67SOmar Sandoval } 25940aabb67SOmar Sandoval 26040aabb67SOmar Sandoval return nr; 26140aabb67SOmar Sandoval } 26240aabb67SOmar Sandoval EXPORT_SYMBOL_GPL(__sbitmap_queue_get); 26340aabb67SOmar Sandoval 26488459642SOmar Sandoval static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq) 26588459642SOmar Sandoval { 26688459642SOmar Sandoval int i, wake_index; 26788459642SOmar Sandoval 26888459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index); 26988459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 27088459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index]; 27188459642SOmar Sandoval 27288459642SOmar Sandoval if (waitqueue_active(&ws->wait)) { 27388459642SOmar Sandoval int o = atomic_read(&sbq->wake_index); 27488459642SOmar Sandoval 27588459642SOmar Sandoval if (wake_index != o) 27688459642SOmar Sandoval atomic_cmpxchg(&sbq->wake_index, o, wake_index); 27788459642SOmar Sandoval return ws; 27888459642SOmar Sandoval } 27988459642SOmar Sandoval 28088459642SOmar Sandoval wake_index = sbq_index_inc(wake_index); 28188459642SOmar Sandoval } 28288459642SOmar Sandoval 28388459642SOmar Sandoval return NULL; 28488459642SOmar Sandoval } 28588459642SOmar Sandoval 28688459642SOmar Sandoval static void sbq_wake_up(struct sbitmap_queue *sbq) 28788459642SOmar Sandoval { 28888459642SOmar Sandoval struct sbq_wait_state *ws; 28988459642SOmar Sandoval int wait_cnt; 29088459642SOmar Sandoval 29188459642SOmar Sandoval /* Ensure that the wait list checks occur after clear_bit(). */ 29288459642SOmar Sandoval smp_mb(); 29388459642SOmar Sandoval 29488459642SOmar Sandoval ws = sbq_wake_ptr(sbq); 29588459642SOmar Sandoval if (!ws) 29688459642SOmar Sandoval return; 29788459642SOmar Sandoval 29888459642SOmar Sandoval wait_cnt = atomic_dec_return(&ws->wait_cnt); 29988459642SOmar Sandoval if (unlikely(wait_cnt < 0)) 30088459642SOmar Sandoval wait_cnt = atomic_inc_return(&ws->wait_cnt); 30188459642SOmar Sandoval if (wait_cnt == 0) { 30288459642SOmar Sandoval atomic_add(sbq->wake_batch, &ws->wait_cnt); 30388459642SOmar Sandoval sbq_index_atomic_inc(&sbq->wake_index); 30488459642SOmar Sandoval wake_up(&ws->wait); 30588459642SOmar Sandoval } 30688459642SOmar Sandoval } 30788459642SOmar Sandoval 30840aabb67SOmar Sandoval void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr, 309*f4a644dbSOmar Sandoval unsigned int cpu) 31088459642SOmar Sandoval { 31188459642SOmar Sandoval sbitmap_clear_bit(&sbq->sb, nr); 31288459642SOmar Sandoval sbq_wake_up(sbq); 313*f4a644dbSOmar Sandoval if (likely(!sbq->round_robin)) 31440aabb67SOmar Sandoval *per_cpu_ptr(sbq->alloc_hint, cpu) = nr; 31588459642SOmar Sandoval } 31688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_clear); 31788459642SOmar Sandoval 31888459642SOmar Sandoval void sbitmap_queue_wake_all(struct sbitmap_queue *sbq) 31988459642SOmar Sandoval { 32088459642SOmar Sandoval int i, wake_index; 32188459642SOmar Sandoval 32288459642SOmar Sandoval /* 32388459642SOmar Sandoval * Make sure all changes prior to this are visible from other CPUs. 32488459642SOmar Sandoval */ 32588459642SOmar Sandoval smp_mb(); 32688459642SOmar Sandoval wake_index = atomic_read(&sbq->wake_index); 32788459642SOmar Sandoval for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 32888459642SOmar Sandoval struct sbq_wait_state *ws = &sbq->ws[wake_index]; 32988459642SOmar Sandoval 33088459642SOmar Sandoval if (waitqueue_active(&ws->wait)) 33188459642SOmar Sandoval wake_up(&ws->wait); 33288459642SOmar Sandoval 33388459642SOmar Sandoval wake_index = sbq_index_inc(wake_index); 33488459642SOmar Sandoval } 33588459642SOmar Sandoval } 33688459642SOmar Sandoval EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all); 337