Lines Matching +full:depth +full:-
1 // SPDX-License-Identifier: GPL-2.0-only
4 * Copyright (C) 2013-2014 Jens Axboe
14 unsigned depth = sb->depth; in init_alloc_hint() local
16 sb->alloc_hint = alloc_percpu_gfp(unsigned int, flags); in init_alloc_hint()
17 if (!sb->alloc_hint) in init_alloc_hint()
18 return -ENOMEM; in init_alloc_hint()
20 if (depth && !sb->round_robin) { in init_alloc_hint()
24 *per_cpu_ptr(sb->alloc_hint, i) = prandom_u32() % depth; in init_alloc_hint()
30 unsigned int depth) in update_alloc_hint_before_get() argument
34 hint = this_cpu_read(*sb->alloc_hint); in update_alloc_hint_before_get()
35 if (unlikely(hint >= depth)) { in update_alloc_hint_before_get()
36 hint = depth ? prandom_u32() % depth : 0; in update_alloc_hint_before_get()
37 this_cpu_write(*sb->alloc_hint, hint); in update_alloc_hint_before_get()
44 unsigned int depth, in update_alloc_hint_after_get() argument
48 if (nr == -1) { in update_alloc_hint_after_get()
50 this_cpu_write(*sb->alloc_hint, 0); in update_alloc_hint_after_get()
51 } else if (nr == hint || unlikely(sb->round_robin)) { in update_alloc_hint_after_get()
54 if (hint >= depth - 1) in update_alloc_hint_after_get()
56 this_cpu_write(*sb->alloc_hint, hint); in update_alloc_hint_after_get()
67 if (!READ_ONCE(map->cleared)) in sbitmap_deferred_clear()
73 mask = xchg(&map->cleared, 0); in sbitmap_deferred_clear()
78 atomic_long_andnot(mask, (atomic_long_t *)&map->word); in sbitmap_deferred_clear()
79 BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word)); in sbitmap_deferred_clear()
83 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, in sbitmap_init_node() argument
91 shift = sbitmap_calculate_shift(depth); in sbitmap_init_node()
95 return -EINVAL; in sbitmap_init_node()
97 sb->shift = shift; in sbitmap_init_node()
98 sb->depth = depth; in sbitmap_init_node()
99 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); in sbitmap_init_node()
100 sb->round_robin = round_robin; in sbitmap_init_node()
102 if (depth == 0) { in sbitmap_init_node()
103 sb->map = NULL; in sbitmap_init_node()
109 return -ENOMEM; in sbitmap_init_node()
111 sb->alloc_hint = NULL; in sbitmap_init_node()
114 sb->map = kcalloc_node(sb->map_nr, sizeof(*sb->map), flags, node); in sbitmap_init_node()
115 if (!sb->map) { in sbitmap_init_node()
116 free_percpu(sb->alloc_hint); in sbitmap_init_node()
117 return -ENOMEM; in sbitmap_init_node()
120 for (i = 0; i < sb->map_nr; i++) { in sbitmap_init_node()
121 sb->map[i].depth = min(depth, bits_per_word); in sbitmap_init_node()
122 depth -= sb->map[i].depth; in sbitmap_init_node()
128 void sbitmap_resize(struct sbitmap *sb, unsigned int depth) in sbitmap_resize() argument
130 unsigned int bits_per_word = 1U << sb->shift; in sbitmap_resize()
133 for (i = 0; i < sb->map_nr; i++) in sbitmap_resize()
134 sbitmap_deferred_clear(&sb->map[i]); in sbitmap_resize()
136 sb->depth = depth; in sbitmap_resize()
137 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); in sbitmap_resize()
139 for (i = 0; i < sb->map_nr; i++) { in sbitmap_resize()
140 sb->map[i].depth = min(depth, bits_per_word); in sbitmap_resize()
141 depth -= sb->map[i].depth; in sbitmap_resize()
146 static int __sbitmap_get_word(unsigned long *word, unsigned long depth, in __sbitmap_get_word() argument
155 nr = find_next_zero_bit(word, depth, hint); in __sbitmap_get_word()
156 if (unlikely(nr >= depth)) { in __sbitmap_get_word()
166 return -1; in __sbitmap_get_word()
173 if (hint >= depth - 1) in __sbitmap_get_word()
183 struct sbitmap_word *map = &sb->map[index]; in sbitmap_find_bit_in_index()
187 nr = __sbitmap_get_word(&map->word, map->depth, alloc_hint, in sbitmap_find_bit_in_index()
188 !sb->round_robin); in sbitmap_find_bit_in_index()
189 if (nr != -1) in sbitmap_find_bit_in_index()
201 int nr = -1; in __sbitmap_get()
210 if (sb->round_robin) in __sbitmap_get()
215 for (i = 0; i < sb->map_nr; i++) { in __sbitmap_get()
217 if (nr != -1) { in __sbitmap_get()
218 nr += index << sb->shift; in __sbitmap_get()
224 if (++index >= sb->map_nr) in __sbitmap_get()
234 unsigned int hint, depth; in sbitmap_get() local
236 if (WARN_ON_ONCE(unlikely(!sb->alloc_hint))) in sbitmap_get()
237 return -1; in sbitmap_get()
239 depth = READ_ONCE(sb->depth); in sbitmap_get()
240 hint = update_alloc_hint_before_get(sb, depth); in sbitmap_get()
242 update_alloc_hint_after_get(sb, depth, hint, nr); in sbitmap_get()
253 int nr = -1; in __sbitmap_get_shallow()
257 for (i = 0; i < sb->map_nr; i++) { in __sbitmap_get_shallow()
259 nr = __sbitmap_get_word(&sb->map[index].word, in __sbitmap_get_shallow()
260 min(sb->map[index].depth, shallow_depth), in __sbitmap_get_shallow()
262 if (nr != -1) { in __sbitmap_get_shallow()
263 nr += index << sb->shift; in __sbitmap_get_shallow()
267 if (sbitmap_deferred_clear(&sb->map[index])) in __sbitmap_get_shallow()
272 alloc_hint = index << sb->shift; in __sbitmap_get_shallow()
274 if (index >= sb->map_nr) { in __sbitmap_get_shallow()
286 unsigned int hint, depth; in sbitmap_get_shallow() local
288 if (WARN_ON_ONCE(unlikely(!sb->alloc_hint))) in sbitmap_get_shallow()
289 return -1; in sbitmap_get_shallow()
291 depth = READ_ONCE(sb->depth); in sbitmap_get_shallow()
292 hint = update_alloc_hint_before_get(sb, depth); in sbitmap_get_shallow()
294 update_alloc_hint_after_get(sb, depth, hint, nr); in sbitmap_get_shallow()
304 for (i = 0; i < sb->map_nr; i++) { in sbitmap_any_bit_set()
305 if (sb->map[i].word & ~sb->map[i].cleared) in sbitmap_any_bit_set()
316 for (i = 0; i < sb->map_nr; i++) { in __sbitmap_weight()
317 const struct sbitmap_word *word = &sb->map[i]; in __sbitmap_weight()
320 weight += bitmap_weight(&word->word, word->depth); in __sbitmap_weight()
322 weight += bitmap_weight(&word->cleared, word->depth); in __sbitmap_weight()
334 return __sbitmap_weight(sb, true) - sbitmap_cleared(sb); in sbitmap_weight()
340 seq_printf(m, "depth=%u\n", sb->depth); in sbitmap_show()
343 seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift); in sbitmap_show()
344 seq_printf(m, "map_nr=%u\n", sb->map_nr); in sbitmap_show()
367 for (i = 0; i < sb->map_nr; i++) { in sbitmap_bitmap_show()
368 unsigned long word = READ_ONCE(sb->map[i].word); in sbitmap_bitmap_show()
369 unsigned long cleared = READ_ONCE(sb->map[i].cleared); in sbitmap_bitmap_show()
370 unsigned int word_bits = READ_ONCE(sb->map[i].depth); in sbitmap_bitmap_show()
375 unsigned int bits = min(8 - byte_bits, word_bits); in sbitmap_bitmap_show()
377 byte |= (word & (BIT(bits) - 1)) << byte_bits; in sbitmap_bitmap_show()
386 word_bits -= bits; in sbitmap_bitmap_show()
399 unsigned int depth) in sbq_calc_wake_batch() argument
406 * batch size is small enough that the full depth of the bitmap, in sbq_calc_wake_batch()
407 * potentially limited by a shallow depth, is enough to wake up all of in sbq_calc_wake_batch()
411 * be a partial word. There are depth / bits_per_word full words and in sbq_calc_wake_batch()
412 * depth % bits_per_word bits left over. In bitwise arithmetic: in sbq_calc_wake_batch()
415 * depth / bits_per_word = depth >> shift in sbq_calc_wake_batch()
416 * depth % bits_per_word = depth & ((1 << shift) - 1) in sbq_calc_wake_batch()
418 * Each word can be limited to sbq->min_shallow_depth bits. in sbq_calc_wake_batch()
420 shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth); in sbq_calc_wake_batch()
421 depth = ((depth >> sbq->sb.shift) * shallow_depth + in sbq_calc_wake_batch()
422 min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth)); in sbq_calc_wake_batch()
423 wake_batch = clamp_t(unsigned int, depth / SBQ_WAIT_QUEUES, 1, in sbq_calc_wake_batch()
429 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, in sbitmap_queue_init_node() argument
435 ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node, in sbitmap_queue_init_node()
440 sbq->min_shallow_depth = UINT_MAX; in sbitmap_queue_init_node()
441 sbq->wake_batch = sbq_calc_wake_batch(sbq, depth); in sbitmap_queue_init_node()
442 atomic_set(&sbq->wake_index, 0); in sbitmap_queue_init_node()
443 atomic_set(&sbq->ws_active, 0); in sbitmap_queue_init_node()
445 sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node); in sbitmap_queue_init_node()
446 if (!sbq->ws) { in sbitmap_queue_init_node()
447 sbitmap_free(&sbq->sb); in sbitmap_queue_init_node()
448 return -ENOMEM; in sbitmap_queue_init_node()
452 init_waitqueue_head(&sbq->ws[i].wait); in sbitmap_queue_init_node()
453 atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch); in sbitmap_queue_init_node()
461 unsigned int depth) in sbitmap_queue_update_wake_batch() argument
463 unsigned int wake_batch = sbq_calc_wake_batch(sbq, depth); in sbitmap_queue_update_wake_batch()
466 if (sbq->wake_batch != wake_batch) { in sbitmap_queue_update_wake_batch()
467 WRITE_ONCE(sbq->wake_batch, wake_batch); in sbitmap_queue_update_wake_batch()
475 atomic_set(&sbq->ws[i].wait_cnt, 1); in sbitmap_queue_update_wake_batch()
479 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth) in sbitmap_queue_resize() argument
481 sbitmap_queue_update_wake_batch(sbq, depth); in sbitmap_queue_resize()
482 sbitmap_resize(&sbq->sb, depth); in sbitmap_queue_resize()
488 return sbitmap_get(&sbq->sb); in __sbitmap_queue_get()
495 WARN_ON_ONCE(shallow_depth < sbq->min_shallow_depth); in __sbitmap_queue_get_shallow()
497 return sbitmap_get_shallow(&sbq->sb, shallow_depth); in __sbitmap_queue_get_shallow()
504 sbq->min_shallow_depth = min_shallow_depth; in sbitmap_queue_min_shallow_depth()
505 sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth); in sbitmap_queue_min_shallow_depth()
513 if (!atomic_read(&sbq->ws_active)) in sbq_wake_ptr()
516 wake_index = atomic_read(&sbq->wake_index); in sbq_wake_ptr()
518 struct sbq_wait_state *ws = &sbq->ws[wake_index]; in sbq_wake_ptr()
520 if (waitqueue_active(&ws->wait)) { in sbq_wake_ptr()
521 if (wake_index != atomic_read(&sbq->wake_index)) in sbq_wake_ptr()
522 atomic_set(&sbq->wake_index, wake_index); in sbq_wake_ptr()
542 wait_cnt = atomic_dec_return(&ws->wait_cnt); in __sbq_wake_up()
546 wake_batch = READ_ONCE(sbq->wake_batch); in __sbq_wake_up()
560 ret = atomic_cmpxchg(&ws->wait_cnt, wait_cnt, wake_batch); in __sbq_wake_up()
562 sbq_index_atomic_inc(&sbq->wake_index); in __sbq_wake_up()
563 wake_up_nr(&ws->wait, wake_batch); in __sbq_wake_up()
587 * of blk_mq) by this bit for avoiding race with re-allocation, in sbitmap_queue_clear()
594 sbitmap_deferred_clear_bit(&sbq->sb, nr); in sbitmap_queue_clear()
605 if (likely(!sbq->sb.round_robin && nr < sbq->sb.depth)) in sbitmap_queue_clear()
606 *per_cpu_ptr(sbq->sb.alloc_hint, cpu) = nr; in sbitmap_queue_clear()
619 wake_index = atomic_read(&sbq->wake_index); in sbitmap_queue_wake_all()
621 struct sbq_wait_state *ws = &sbq->ws[wake_index]; in sbitmap_queue_wake_all()
623 if (waitqueue_active(&ws->wait)) in sbitmap_queue_wake_all()
624 wake_up(&ws->wait); in sbitmap_queue_wake_all()
636 sbitmap_show(&sbq->sb, m); in sbitmap_queue_show()
644 seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i)); in sbitmap_queue_show()
648 seq_printf(m, "wake_batch=%u\n", sbq->wake_batch); in sbitmap_queue_show()
649 seq_printf(m, "wake_index=%d\n", atomic_read(&sbq->wake_index)); in sbitmap_queue_show()
650 seq_printf(m, "ws_active=%d\n", atomic_read(&sbq->ws_active)); in sbitmap_queue_show()
654 struct sbq_wait_state *ws = &sbq->ws[i]; in sbitmap_queue_show()
657 atomic_read(&ws->wait_cnt), in sbitmap_queue_show()
658 waitqueue_active(&ws->wait) ? "active" : "inactive"); in sbitmap_queue_show()
662 seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin); in sbitmap_queue_show()
663 seq_printf(m, "min_shallow_depth=%u\n", sbq->min_shallow_depth); in sbitmap_queue_show()
671 if (!sbq_wait->sbq) { in sbitmap_add_wait_queue()
672 sbq_wait->sbq = sbq; in sbitmap_add_wait_queue()
673 atomic_inc(&sbq->ws_active); in sbitmap_add_wait_queue()
674 add_wait_queue(&ws->wait, &sbq_wait->wait); in sbitmap_add_wait_queue()
681 list_del_init(&sbq_wait->wait.entry); in sbitmap_del_wait_queue()
682 if (sbq_wait->sbq) { in sbitmap_del_wait_queue()
683 atomic_dec(&sbq_wait->sbq->ws_active); in sbitmap_del_wait_queue()
684 sbq_wait->sbq = NULL; in sbitmap_del_wait_queue()
693 if (!sbq_wait->sbq) { in sbitmap_prepare_to_wait()
694 atomic_inc(&sbq->ws_active); in sbitmap_prepare_to_wait()
695 sbq_wait->sbq = sbq; in sbitmap_prepare_to_wait()
697 prepare_to_wait_exclusive(&ws->wait, &sbq_wait->wait, state); in sbitmap_prepare_to_wait()
704 finish_wait(&ws->wait, &sbq_wait->wait); in sbitmap_finish_wait()
705 if (sbq_wait->sbq) { in sbitmap_finish_wait()
706 atomic_dec(&sbq->ws_active); in sbitmap_finish_wait()
707 sbq_wait->sbq = NULL; in sbitmap_finish_wait()