2 * Copyright (C) 2016 Facebook
3 * Copyright (C) 2013-2014 Jens Axboe
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public
7 * License v2 as published by the Free Software Foundation.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <https://www.gnu.org/licenses/>.
18 #include <linux/random.h>
19 #include <linux/sbitmap.h>
20 #include <linux/seq_file.h>
22 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
23 gfp_t flags, int node)
25 unsigned int bits_per_word;
29 shift = ilog2(BITS_PER_LONG);
31 * If the bitmap is small, shrink the number of bits per word so
32 * we spread over a few cachelines, at least. If less than 4
33 * bits, just forget about it, it's not going to work optimally
37 while ((4U << shift) > depth)
41 bits_per_word = 1U << shift;
42 if (bits_per_word > BITS_PER_LONG)
47 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
54 sb->map = kzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node);
58 for (i = 0; i < sb->map_nr; i++) {
59 sb->map[i].depth = min(depth, bits_per_word);
60 depth -= sb->map[i].depth;
64 EXPORT_SYMBOL_GPL(sbitmap_init_node);
66 void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
68 unsigned int bits_per_word = 1U << sb->shift;
72 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
74 for (i = 0; i < sb->map_nr; i++) {
75 sb->map[i].depth = min(depth, bits_per_word);
76 depth -= sb->map[i].depth;
79 EXPORT_SYMBOL_GPL(sbitmap_resize);
81 static int __sbitmap_get_word(struct sbitmap_word *word, unsigned int hint,
84 unsigned int orig_hint = hint;
88 nr = find_next_zero_bit(&word->word, word->depth, hint);
89 if (unlikely(nr >= word->depth)) {
91 * We started with an offset, and we didn't reset the
92 * offset to 0 in a failure case, so start from 0 to
95 if (orig_hint && hint && wrap) {
102 if (!test_and_set_bit(nr, &word->word))
106 if (hint >= word->depth - 1)
113 int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin)
115 unsigned int i, index;
118 index = SB_NR_TO_INDEX(sb, alloc_hint);
120 for (i = 0; i < sb->map_nr; i++) {
121 nr = __sbitmap_get_word(&sb->map[index],
122 SB_NR_TO_BIT(sb, alloc_hint),
125 nr += index << sb->shift;
129 /* Jump to next index. */
131 alloc_hint = index << sb->shift;
133 if (index >= sb->map_nr) {
141 EXPORT_SYMBOL_GPL(sbitmap_get);
143 bool sbitmap_any_bit_set(const struct sbitmap *sb)
147 for (i = 0; i < sb->map_nr; i++) {
153 EXPORT_SYMBOL_GPL(sbitmap_any_bit_set);
155 bool sbitmap_any_bit_clear(const struct sbitmap *sb)
159 for (i = 0; i < sb->map_nr; i++) {
160 const struct sbitmap_word *word = &sb->map[i];
163 ret = find_first_zero_bit(&word->word, word->depth);
164 if (ret < word->depth)
169 EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear);
171 unsigned int sbitmap_weight(const struct sbitmap *sb)
173 unsigned int i, weight = 0;
175 for (i = 0; i < sb->map_nr; i++) {
176 const struct sbitmap_word *word = &sb->map[i];
178 weight += bitmap_weight(&word->word, word->depth);
182 EXPORT_SYMBOL_GPL(sbitmap_weight);
184 void sbitmap_show(struct sbitmap *sb, struct seq_file *m)
186 seq_printf(m, "depth=%u\n", sb->depth);
187 seq_printf(m, "busy=%u\n", sbitmap_weight(sb));
188 seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);
189 seq_printf(m, "map_nr=%u\n", sb->map_nr);
191 EXPORT_SYMBOL_GPL(sbitmap_show);
193 static inline void emit_byte(struct seq_file *m, unsigned int offset, u8 byte)
195 if ((offset & 0xf) == 0) {
198 seq_printf(m, "%08x:", offset);
200 if ((offset & 0x1) == 0)
202 seq_printf(m, "%02x", byte);
205 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m)
208 unsigned int byte_bits = 0;
209 unsigned int offset = 0;
212 for (i = 0; i < sb->map_nr; i++) {
213 unsigned long word = READ_ONCE(sb->map[i].word);
214 unsigned int word_bits = READ_ONCE(sb->map[i].depth);
216 while (word_bits > 0) {
217 unsigned int bits = min(8 - byte_bits, word_bits);
219 byte |= (word & (BIT(bits) - 1)) << byte_bits;
221 if (byte_bits == 8) {
222 emit_byte(m, offset, byte);
232 emit_byte(m, offset, byte);
238 EXPORT_SYMBOL_GPL(sbitmap_bitmap_show);
240 static unsigned int sbq_calc_wake_batch(unsigned int depth)
242 unsigned int wake_batch;
245 * For each batch, we wake up one queue. We need to make sure that our
246 * batch size is small enough that the full depth of the bitmap is
247 * enough to wake up all of the queues.
249 wake_batch = SBQ_WAKE_BATCH;
250 if (wake_batch > depth / SBQ_WAIT_QUEUES)
251 wake_batch = max(1U, depth / SBQ_WAIT_QUEUES);
256 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
257 int shift, bool round_robin, gfp_t flags, int node)
262 ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node);
266 sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags);
267 if (!sbq->alloc_hint) {
268 sbitmap_free(&sbq->sb);
272 if (depth && !round_robin) {
273 for_each_possible_cpu(i)
274 *per_cpu_ptr(sbq->alloc_hint, i) = prandom_u32() % depth;
277 sbq->wake_batch = sbq_calc_wake_batch(depth);
278 atomic_set(&sbq->wake_index, 0);
280 sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node);
282 free_percpu(sbq->alloc_hint);
283 sbitmap_free(&sbq->sb);
287 for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
288 init_waitqueue_head(&sbq->ws[i].wait);
289 atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
292 sbq->round_robin = round_robin;
295 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node);
297 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth)
299 unsigned int wake_batch = sbq_calc_wake_batch(depth);
302 if (sbq->wake_batch != wake_batch) {
303 WRITE_ONCE(sbq->wake_batch, wake_batch);
305 * Pairs with the memory barrier in sbq_wake_up() to ensure that
306 * the batch size is updated before the wait counts.
308 smp_mb__before_atomic();
309 for (i = 0; i < SBQ_WAIT_QUEUES; i++)
310 atomic_set(&sbq->ws[i].wait_cnt, 1);
312 sbitmap_resize(&sbq->sb, depth);
314 EXPORT_SYMBOL_GPL(sbitmap_queue_resize);
316 int __sbitmap_queue_get(struct sbitmap_queue *sbq)
318 unsigned int hint, depth;
321 hint = this_cpu_read(*sbq->alloc_hint);
322 depth = READ_ONCE(sbq->sb.depth);
323 if (unlikely(hint >= depth)) {
324 hint = depth ? prandom_u32() % depth : 0;
325 this_cpu_write(*sbq->alloc_hint, hint);
327 nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin);
330 /* If the map is full, a hint won't do us much good. */
331 this_cpu_write(*sbq->alloc_hint, 0);
332 } else if (nr == hint || unlikely(sbq->round_robin)) {
333 /* Only update the hint if we used it. */
335 if (hint >= depth - 1)
337 this_cpu_write(*sbq->alloc_hint, hint);
342 EXPORT_SYMBOL_GPL(__sbitmap_queue_get);
344 static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq)
348 wake_index = atomic_read(&sbq->wake_index);
349 for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
350 struct sbq_wait_state *ws = &sbq->ws[wake_index];
352 if (waitqueue_active(&ws->wait)) {
353 int o = atomic_read(&sbq->wake_index);
356 atomic_cmpxchg(&sbq->wake_index, o, wake_index);
360 wake_index = sbq_index_inc(wake_index);
366 static void sbq_wake_up(struct sbitmap_queue *sbq)
368 struct sbq_wait_state *ws;
369 unsigned int wake_batch;
373 * Pairs with the memory barrier in set_current_state() to ensure the
374 * proper ordering of clear_bit()/waitqueue_active() in the waker and
375 * test_and_set_bit()/prepare_to_wait()/finish_wait() in the waiter. See
376 * the comment on waitqueue_active(). This is __after_atomic because we
377 * just did clear_bit() in the caller.
379 smp_mb__after_atomic();
381 ws = sbq_wake_ptr(sbq);
385 wait_cnt = atomic_dec_return(&ws->wait_cnt);
387 wake_batch = READ_ONCE(sbq->wake_batch);
389 * Pairs with the memory barrier in sbitmap_queue_resize() to
390 * ensure that we see the batch size update before the wait
393 smp_mb__before_atomic();
395 * If there are concurrent callers to sbq_wake_up(), the last
396 * one to decrement the wait count below zero will bump it back
397 * up. If there is a concurrent resize, the count reset will
398 * either cause the cmpxchg to fail or overwrite after the
401 atomic_cmpxchg(&ws->wait_cnt, wait_cnt, wait_cnt + wake_batch);
402 sbq_index_atomic_inc(&sbq->wake_index);
407 void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
410 sbitmap_clear_bit(&sbq->sb, nr);
412 if (likely(!sbq->round_robin && nr < sbq->sb.depth))
413 *per_cpu_ptr(sbq->alloc_hint, cpu) = nr;
415 EXPORT_SYMBOL_GPL(sbitmap_queue_clear);
417 void sbitmap_queue_wake_all(struct sbitmap_queue *sbq)
422 * Pairs with the memory barrier in set_current_state() like in
426 wake_index = atomic_read(&sbq->wake_index);
427 for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
428 struct sbq_wait_state *ws = &sbq->ws[wake_index];
430 if (waitqueue_active(&ws->wait))
433 wake_index = sbq_index_inc(wake_index);
436 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all);
438 void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m)
443 sbitmap_show(&sbq->sb, m);
445 seq_puts(m, "alloc_hint={");
447 for_each_possible_cpu(i) {
451 seq_printf(m, "%u", *per_cpu_ptr(sbq->alloc_hint, i));
455 seq_printf(m, "wake_batch=%u\n", sbq->wake_batch);
456 seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index));
458 seq_puts(m, "ws={\n");
459 for (i = 0; i < SBQ_WAIT_QUEUES; i++) {
460 struct sbq_wait_state *ws = &sbq->ws[i];
462 seq_printf(m, "\t{.wait_cnt=%d, .wait=%s},\n",
463 atomic_read(&ws->wait_cnt),
464 waitqueue_active(&ws->wait) ? "active" : "inactive");
468 seq_printf(m, "round_robin=%d\n", sbq->round_robin);
470 EXPORT_SYMBOL_GPL(sbitmap_queue_show);