1 // SPDX-License-Identifier: GPL-2.0-only
3 * Copyright (C) 2016 Facebook
4 * Copyright (C) 2013-2014 Jens Axboe
7 #include <linux/sched.h>
8 #include <linux/random.h>
9 #include <linux/sbitmap.h>
10 #include <linux/seq_file.h>
12 static int init_alloc_hint(struct sbitmap
*sb
, gfp_t flags
)
14 unsigned depth
= sb
->depth
;
16 sb
->alloc_hint
= alloc_percpu_gfp(unsigned int, flags
);
20 if (depth
&& !sb
->round_robin
) {
23 for_each_possible_cpu(i
)
24 *per_cpu_ptr(sb
->alloc_hint
, i
) = get_random_u32_below(depth
);
29 static inline unsigned update_alloc_hint_before_get(struct sbitmap
*sb
,
34 hint
= this_cpu_read(*sb
->alloc_hint
);
35 if (unlikely(hint
>= depth
)) {
36 hint
= depth
? get_random_u32_below(depth
) : 0;
37 this_cpu_write(*sb
->alloc_hint
, hint
);
43 static inline void update_alloc_hint_after_get(struct sbitmap
*sb
,
49 /* If the map is full, a hint won't do us much good. */
50 this_cpu_write(*sb
->alloc_hint
, 0);
51 } else if (nr
== hint
|| unlikely(sb
->round_robin
)) {
52 /* Only update the hint if we used it. */
54 if (hint
>= depth
- 1)
56 this_cpu_write(*sb
->alloc_hint
, hint
);
61 * See if we have deferred clears that we can batch move
63 static inline bool sbitmap_deferred_clear(struct sbitmap_word
*map
)
67 if (!READ_ONCE(map
->cleared
))
71 * First get a stable cleared mask, setting the old mask to 0.
73 mask
= xchg(&map
->cleared
, 0);
76 * Now clear the masked bits in our free word
78 atomic_long_andnot(mask
, (atomic_long_t
*)&map
->word
);
79 BUILD_BUG_ON(sizeof(atomic_long_t
) != sizeof(map
->word
));
83 int sbitmap_init_node(struct sbitmap
*sb
, unsigned int depth
, int shift
,
84 gfp_t flags
, int node
, bool round_robin
,
87 unsigned int bits_per_word
;
90 shift
= sbitmap_calculate_shift(depth
);
92 bits_per_word
= 1U << shift
;
93 if (bits_per_word
> BITS_PER_LONG
)
98 sb
->map_nr
= DIV_ROUND_UP(sb
->depth
, bits_per_word
);
99 sb
->round_robin
= round_robin
;
107 if (init_alloc_hint(sb
, flags
))
110 sb
->alloc_hint
= NULL
;
113 sb
->map
= kvzalloc_node(sb
->map_nr
* sizeof(*sb
->map
), flags
, node
);
115 free_percpu(sb
->alloc_hint
);
121 EXPORT_SYMBOL_GPL(sbitmap_init_node
);
123 void sbitmap_resize(struct sbitmap
*sb
, unsigned int depth
)
125 unsigned int bits_per_word
= 1U << sb
->shift
;
128 for (i
= 0; i
< sb
->map_nr
; i
++)
129 sbitmap_deferred_clear(&sb
->map
[i
]);
132 sb
->map_nr
= DIV_ROUND_UP(sb
->depth
, bits_per_word
);
134 EXPORT_SYMBOL_GPL(sbitmap_resize
);
136 static int __sbitmap_get_word(unsigned long *word
, unsigned long depth
,
137 unsigned int hint
, bool wrap
)
141 /* don't wrap if starting from 0 */
145 nr
= find_next_zero_bit(word
, depth
, hint
);
146 if (unlikely(nr
>= depth
)) {
148 * We started with an offset, and we didn't reset the
149 * offset to 0 in a failure case, so start from 0 to
159 if (!test_and_set_bit_lock(nr
, word
))
163 if (hint
>= depth
- 1)
170 static int sbitmap_find_bit_in_word(struct sbitmap_word
*map
,
172 unsigned int alloc_hint
,
178 nr
= __sbitmap_get_word(&map
->word
, depth
,
182 if (!sbitmap_deferred_clear(map
))
189 static int sbitmap_find_bit(struct sbitmap
*sb
,
192 unsigned int alloc_hint
,
198 for (i
= 0; i
< sb
->map_nr
; i
++) {
199 nr
= sbitmap_find_bit_in_word(&sb
->map
[index
],
201 __map_depth(sb
, index
),
206 nr
+= index
<< sb
->shift
;
210 /* Jump to next index. */
212 if (++index
>= sb
->map_nr
)
219 static int __sbitmap_get(struct sbitmap
*sb
, unsigned int alloc_hint
)
223 index
= SB_NR_TO_INDEX(sb
, alloc_hint
);
226 * Unless we're doing round robin tag allocation, just use the
227 * alloc_hint to find the right word index. No point in looping
228 * twice in find_next_zero_bit() for that case.
231 alloc_hint
= SB_NR_TO_BIT(sb
, alloc_hint
);
235 return sbitmap_find_bit(sb
, UINT_MAX
, index
, alloc_hint
,
239 int sbitmap_get(struct sbitmap
*sb
)
242 unsigned int hint
, depth
;
244 if (WARN_ON_ONCE(unlikely(!sb
->alloc_hint
)))
247 depth
= READ_ONCE(sb
->depth
);
248 hint
= update_alloc_hint_before_get(sb
, depth
);
249 nr
= __sbitmap_get(sb
, hint
);
250 update_alloc_hint_after_get(sb
, depth
, hint
, nr
);
254 EXPORT_SYMBOL_GPL(sbitmap_get
);
256 static int __sbitmap_get_shallow(struct sbitmap
*sb
,
257 unsigned int alloc_hint
,
258 unsigned long shallow_depth
)
262 index
= SB_NR_TO_INDEX(sb
, alloc_hint
);
263 alloc_hint
= SB_NR_TO_BIT(sb
, alloc_hint
);
265 return sbitmap_find_bit(sb
, shallow_depth
, index
, alloc_hint
, true);
268 int sbitmap_get_shallow(struct sbitmap
*sb
, unsigned long shallow_depth
)
271 unsigned int hint
, depth
;
273 if (WARN_ON_ONCE(unlikely(!sb
->alloc_hint
)))
276 depth
= READ_ONCE(sb
->depth
);
277 hint
= update_alloc_hint_before_get(sb
, depth
);
278 nr
= __sbitmap_get_shallow(sb
, hint
, shallow_depth
);
279 update_alloc_hint_after_get(sb
, depth
, hint
, nr
);
283 EXPORT_SYMBOL_GPL(sbitmap_get_shallow
);
285 bool sbitmap_any_bit_set(const struct sbitmap
*sb
)
289 for (i
= 0; i
< sb
->map_nr
; i
++) {
290 if (sb
->map
[i
].word
& ~sb
->map
[i
].cleared
)
295 EXPORT_SYMBOL_GPL(sbitmap_any_bit_set
);
297 static unsigned int __sbitmap_weight(const struct sbitmap
*sb
, bool set
)
299 unsigned int i
, weight
= 0;
301 for (i
= 0; i
< sb
->map_nr
; i
++) {
302 const struct sbitmap_word
*word
= &sb
->map
[i
];
303 unsigned int word_depth
= __map_depth(sb
, i
);
306 weight
+= bitmap_weight(&word
->word
, word_depth
);
308 weight
+= bitmap_weight(&word
->cleared
, word_depth
);
313 static unsigned int sbitmap_cleared(const struct sbitmap
*sb
)
315 return __sbitmap_weight(sb
, false);
318 unsigned int sbitmap_weight(const struct sbitmap
*sb
)
320 return __sbitmap_weight(sb
, true) - sbitmap_cleared(sb
);
322 EXPORT_SYMBOL_GPL(sbitmap_weight
);
324 void sbitmap_show(struct sbitmap
*sb
, struct seq_file
*m
)
326 seq_printf(m
, "depth=%u\n", sb
->depth
);
327 seq_printf(m
, "busy=%u\n", sbitmap_weight(sb
));
328 seq_printf(m
, "cleared=%u\n", sbitmap_cleared(sb
));
329 seq_printf(m
, "bits_per_word=%u\n", 1U << sb
->shift
);
330 seq_printf(m
, "map_nr=%u\n", sb
->map_nr
);
332 EXPORT_SYMBOL_GPL(sbitmap_show
);
334 static inline void emit_byte(struct seq_file
*m
, unsigned int offset
, u8 byte
)
336 if ((offset
& 0xf) == 0) {
339 seq_printf(m
, "%08x:", offset
);
341 if ((offset
& 0x1) == 0)
343 seq_printf(m
, "%02x", byte
);
346 void sbitmap_bitmap_show(struct sbitmap
*sb
, struct seq_file
*m
)
349 unsigned int byte_bits
= 0;
350 unsigned int offset
= 0;
353 for (i
= 0; i
< sb
->map_nr
; i
++) {
354 unsigned long word
= READ_ONCE(sb
->map
[i
].word
);
355 unsigned long cleared
= READ_ONCE(sb
->map
[i
].cleared
);
356 unsigned int word_bits
= __map_depth(sb
, i
);
360 while (word_bits
> 0) {
361 unsigned int bits
= min(8 - byte_bits
, word_bits
);
363 byte
|= (word
& (BIT(bits
) - 1)) << byte_bits
;
365 if (byte_bits
== 8) {
366 emit_byte(m
, offset
, byte
);
376 emit_byte(m
, offset
, byte
);
382 EXPORT_SYMBOL_GPL(sbitmap_bitmap_show
);
384 static unsigned int sbq_calc_wake_batch(struct sbitmap_queue
*sbq
,
387 unsigned int wake_batch
;
388 unsigned int shallow_depth
;
391 * Each full word of the bitmap has bits_per_word bits, and there might
392 * be a partial word. There are depth / bits_per_word full words and
393 * depth % bits_per_word bits left over. In bitwise arithmetic:
395 * bits_per_word = 1 << shift
396 * depth / bits_per_word = depth >> shift
397 * depth % bits_per_word = depth & ((1 << shift) - 1)
399 * Each word can be limited to sbq->min_shallow_depth bits.
401 shallow_depth
= min(1U << sbq
->sb
.shift
, sbq
->min_shallow_depth
);
402 depth
= ((depth
>> sbq
->sb
.shift
) * shallow_depth
+
403 min(depth
& ((1U << sbq
->sb
.shift
) - 1), shallow_depth
));
404 wake_batch
= clamp_t(unsigned int, depth
/ SBQ_WAIT_QUEUES
, 1,
410 int sbitmap_queue_init_node(struct sbitmap_queue
*sbq
, unsigned int depth
,
411 int shift
, bool round_robin
, gfp_t flags
, int node
)
416 ret
= sbitmap_init_node(&sbq
->sb
, depth
, shift
, flags
, node
,
421 sbq
->min_shallow_depth
= UINT_MAX
;
422 sbq
->wake_batch
= sbq_calc_wake_batch(sbq
, depth
);
423 atomic_set(&sbq
->wake_index
, 0);
424 atomic_set(&sbq
->ws_active
, 0);
425 atomic_set(&sbq
->completion_cnt
, 0);
426 atomic_set(&sbq
->wakeup_cnt
, 0);
428 sbq
->ws
= kzalloc_node(SBQ_WAIT_QUEUES
* sizeof(*sbq
->ws
), flags
, node
);
430 sbitmap_free(&sbq
->sb
);
434 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++)
435 init_waitqueue_head(&sbq
->ws
[i
].wait
);
439 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node
);
441 static void sbitmap_queue_update_wake_batch(struct sbitmap_queue
*sbq
,
444 unsigned int wake_batch
;
446 wake_batch
= sbq_calc_wake_batch(sbq
, depth
);
447 if (sbq
->wake_batch
!= wake_batch
)
448 WRITE_ONCE(sbq
->wake_batch
, wake_batch
);
451 void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue
*sbq
,
454 unsigned int wake_batch
;
455 unsigned int depth
= (sbq
->sb
.depth
+ users
- 1) / users
;
457 wake_batch
= clamp_val(depth
/ SBQ_WAIT_QUEUES
,
460 WRITE_ONCE(sbq
->wake_batch
, wake_batch
);
462 EXPORT_SYMBOL_GPL(sbitmap_queue_recalculate_wake_batch
);
464 void sbitmap_queue_resize(struct sbitmap_queue
*sbq
, unsigned int depth
)
466 sbitmap_queue_update_wake_batch(sbq
, depth
);
467 sbitmap_resize(&sbq
->sb
, depth
);
469 EXPORT_SYMBOL_GPL(sbitmap_queue_resize
);
471 int __sbitmap_queue_get(struct sbitmap_queue
*sbq
)
473 return sbitmap_get(&sbq
->sb
);
475 EXPORT_SYMBOL_GPL(__sbitmap_queue_get
);
477 unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue
*sbq
, int nr_tags
,
478 unsigned int *offset
)
480 struct sbitmap
*sb
= &sbq
->sb
;
481 unsigned int hint
, depth
;
482 unsigned long index
, nr
;
485 if (unlikely(sb
->round_robin
))
488 depth
= READ_ONCE(sb
->depth
);
489 hint
= update_alloc_hint_before_get(sb
, depth
);
491 index
= SB_NR_TO_INDEX(sb
, hint
);
493 for (i
= 0; i
< sb
->map_nr
; i
++) {
494 struct sbitmap_word
*map
= &sb
->map
[index
];
495 unsigned long get_mask
;
496 unsigned int map_depth
= __map_depth(sb
, index
);
498 sbitmap_deferred_clear(map
);
499 if (map
->word
== (1UL << (map_depth
- 1)) - 1)
502 nr
= find_first_zero_bit(&map
->word
, map_depth
);
503 if (nr
+ nr_tags
<= map_depth
) {
504 atomic_long_t
*ptr
= (atomic_long_t
*) &map
->word
;
507 get_mask
= ((1UL << nr_tags
) - 1) << nr
;
508 val
= READ_ONCE(map
->word
);
509 while (!atomic_long_try_cmpxchg(ptr
, &val
,
512 get_mask
= (get_mask
& ~val
) >> nr
;
514 *offset
= nr
+ (index
<< sb
->shift
);
515 update_alloc_hint_after_get(sb
, depth
, hint
,
516 *offset
+ nr_tags
- 1);
521 /* Jump to next index. */
522 if (++index
>= sb
->map_nr
)
529 int sbitmap_queue_get_shallow(struct sbitmap_queue
*sbq
,
530 unsigned int shallow_depth
)
532 WARN_ON_ONCE(shallow_depth
< sbq
->min_shallow_depth
);
534 return sbitmap_get_shallow(&sbq
->sb
, shallow_depth
);
536 EXPORT_SYMBOL_GPL(sbitmap_queue_get_shallow
);
538 void sbitmap_queue_min_shallow_depth(struct sbitmap_queue
*sbq
,
539 unsigned int min_shallow_depth
)
541 sbq
->min_shallow_depth
= min_shallow_depth
;
542 sbitmap_queue_update_wake_batch(sbq
, sbq
->sb
.depth
);
544 EXPORT_SYMBOL_GPL(sbitmap_queue_min_shallow_depth
);
546 static void __sbitmap_queue_wake_up(struct sbitmap_queue
*sbq
, int nr
)
548 int i
, wake_index
, woken
;
550 if (!atomic_read(&sbq
->ws_active
))
553 wake_index
= atomic_read(&sbq
->wake_index
);
554 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++) {
555 struct sbq_wait_state
*ws
= &sbq
->ws
[wake_index
];
558 * Advance the index before checking the current queue.
559 * It improves fairness, by ensuring the queue doesn't
560 * need to be fully emptied before trying to wake up
563 wake_index
= sbq_index_inc(wake_index
);
565 if (waitqueue_active(&ws
->wait
)) {
566 woken
= wake_up_nr(&ws
->wait
, nr
);
573 if (wake_index
!= atomic_read(&sbq
->wake_index
))
574 atomic_set(&sbq
->wake_index
, wake_index
);
577 void sbitmap_queue_wake_up(struct sbitmap_queue
*sbq
, int nr
)
579 unsigned int wake_batch
= READ_ONCE(sbq
->wake_batch
);
580 unsigned int wakeups
;
582 if (!atomic_read(&sbq
->ws_active
))
585 atomic_add(nr
, &sbq
->completion_cnt
);
586 wakeups
= atomic_read(&sbq
->wakeup_cnt
);
589 if (atomic_read(&sbq
->completion_cnt
) - wakeups
< wake_batch
)
591 } while (!atomic_try_cmpxchg(&sbq
->wakeup_cnt
,
592 &wakeups
, wakeups
+ wake_batch
));
594 __sbitmap_queue_wake_up(sbq
, wake_batch
);
596 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_up
);
598 static inline void sbitmap_update_cpu_hint(struct sbitmap
*sb
, int cpu
, int tag
)
600 if (likely(!sb
->round_robin
&& tag
< sb
->depth
))
601 data_race(*per_cpu_ptr(sb
->alloc_hint
, cpu
) = tag
);
604 void sbitmap_queue_clear_batch(struct sbitmap_queue
*sbq
, int offset
,
605 int *tags
, int nr_tags
)
607 struct sbitmap
*sb
= &sbq
->sb
;
608 unsigned long *addr
= NULL
;
609 unsigned long mask
= 0;
612 smp_mb__before_atomic();
613 for (i
= 0; i
< nr_tags
; i
++) {
614 const int tag
= tags
[i
] - offset
;
615 unsigned long *this_addr
;
617 /* since we're clearing a batch, skip the deferred map */
618 this_addr
= &sb
->map
[SB_NR_TO_INDEX(sb
, tag
)].word
;
621 } else if (addr
!= this_addr
) {
622 atomic_long_andnot(mask
, (atomic_long_t
*) addr
);
626 mask
|= (1UL << SB_NR_TO_BIT(sb
, tag
));
630 atomic_long_andnot(mask
, (atomic_long_t
*) addr
);
632 smp_mb__after_atomic();
633 sbitmap_queue_wake_up(sbq
, nr_tags
);
634 sbitmap_update_cpu_hint(&sbq
->sb
, raw_smp_processor_id(),
635 tags
[nr_tags
- 1] - offset
);
638 void sbitmap_queue_clear(struct sbitmap_queue
*sbq
, unsigned int nr
,
642 * Once the clear bit is set, the bit may be allocated out.
644 * Orders READ/WRITE on the associated instance(such as request
645 * of blk_mq) by this bit for avoiding race with re-allocation,
646 * and its pair is the memory barrier implied in __sbitmap_get_word.
648 * One invariant is that the clear bit has to be zero when the bit
651 smp_mb__before_atomic();
652 sbitmap_deferred_clear_bit(&sbq
->sb
, nr
);
655 * Pairs with the memory barrier in set_current_state() to ensure the
656 * proper ordering of clear_bit_unlock()/waitqueue_active() in the waker
657 * and test_and_set_bit_lock()/prepare_to_wait()/finish_wait() in the
658 * waiter. See the comment on waitqueue_active().
660 smp_mb__after_atomic();
661 sbitmap_queue_wake_up(sbq
, 1);
662 sbitmap_update_cpu_hint(&sbq
->sb
, cpu
, nr
);
664 EXPORT_SYMBOL_GPL(sbitmap_queue_clear
);
666 void sbitmap_queue_wake_all(struct sbitmap_queue
*sbq
)
671 * Pairs with the memory barrier in set_current_state() like in
672 * sbitmap_queue_wake_up().
675 wake_index
= atomic_read(&sbq
->wake_index
);
676 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++) {
677 struct sbq_wait_state
*ws
= &sbq
->ws
[wake_index
];
679 if (waitqueue_active(&ws
->wait
))
682 wake_index
= sbq_index_inc(wake_index
);
685 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all
);
687 void sbitmap_queue_show(struct sbitmap_queue
*sbq
, struct seq_file
*m
)
692 sbitmap_show(&sbq
->sb
, m
);
694 seq_puts(m
, "alloc_hint={");
696 for_each_possible_cpu(i
) {
700 seq_printf(m
, "%u", *per_cpu_ptr(sbq
->sb
.alloc_hint
, i
));
704 seq_printf(m
, "wake_batch=%u\n", sbq
->wake_batch
);
705 seq_printf(m
, "wake_index=%d\n", atomic_read(&sbq
->wake_index
));
706 seq_printf(m
, "ws_active=%d\n", atomic_read(&sbq
->ws_active
));
708 seq_puts(m
, "ws={\n");
709 for (i
= 0; i
< SBQ_WAIT_QUEUES
; i
++) {
710 struct sbq_wait_state
*ws
= &sbq
->ws
[i
];
711 seq_printf(m
, "\t{.wait=%s},\n",
712 waitqueue_active(&ws
->wait
) ? "active" : "inactive");
716 seq_printf(m
, "round_robin=%d\n", sbq
->sb
.round_robin
);
717 seq_printf(m
, "min_shallow_depth=%u\n", sbq
->min_shallow_depth
);
719 EXPORT_SYMBOL_GPL(sbitmap_queue_show
);
721 void sbitmap_add_wait_queue(struct sbitmap_queue
*sbq
,
722 struct sbq_wait_state
*ws
,
723 struct sbq_wait
*sbq_wait
)
725 if (!sbq_wait
->sbq
) {
727 atomic_inc(&sbq
->ws_active
);
728 add_wait_queue(&ws
->wait
, &sbq_wait
->wait
);
731 EXPORT_SYMBOL_GPL(sbitmap_add_wait_queue
);
733 void sbitmap_del_wait_queue(struct sbq_wait
*sbq_wait
)
735 list_del_init(&sbq_wait
->wait
.entry
);
737 atomic_dec(&sbq_wait
->sbq
->ws_active
);
738 sbq_wait
->sbq
= NULL
;
741 EXPORT_SYMBOL_GPL(sbitmap_del_wait_queue
);
743 void sbitmap_prepare_to_wait(struct sbitmap_queue
*sbq
,
744 struct sbq_wait_state
*ws
,
745 struct sbq_wait
*sbq_wait
, int state
)
747 if (!sbq_wait
->sbq
) {
748 atomic_inc(&sbq
->ws_active
);
751 prepare_to_wait_exclusive(&ws
->wait
, &sbq_wait
->wait
, state
);
753 EXPORT_SYMBOL_GPL(sbitmap_prepare_to_wait
);
755 void sbitmap_finish_wait(struct sbitmap_queue
*sbq
, struct sbq_wait_state
*ws
,
756 struct sbq_wait
*sbq_wait
)
758 finish_wait(&ws
->wait
, &sbq_wait
->wait
);
760 atomic_dec(&sbq
->ws_active
);
761 sbq_wait
->sbq
= NULL
;
764 EXPORT_SYMBOL_GPL(sbitmap_finish_wait
);