Lines Matching refs:sb
15 static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) in sbitmap_deferred_clear() argument
21 spin_lock_irqsave(&sb->map[index].swap_lock, flags); in sbitmap_deferred_clear()
23 if (!sb->map[index].cleared) in sbitmap_deferred_clear()
29 mask = xchg(&sb->map[index].cleared, 0); in sbitmap_deferred_clear()
35 val = sb->map[index].word; in sbitmap_deferred_clear()
36 } while (cmpxchg(&sb->map[index].word, val, val & ~mask) != val); in sbitmap_deferred_clear()
40 spin_unlock_irqrestore(&sb->map[index].swap_lock, flags); in sbitmap_deferred_clear()
44 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, in sbitmap_init_node() argument
67 sb->shift = shift; in sbitmap_init_node()
68 sb->depth = depth; in sbitmap_init_node()
69 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); in sbitmap_init_node()
72 sb->map = NULL; in sbitmap_init_node()
76 sb->map = kcalloc_node(sb->map_nr, sizeof(*sb->map), flags, node); in sbitmap_init_node()
77 if (!sb->map) in sbitmap_init_node()
80 for (i = 0; i < sb->map_nr; i++) { in sbitmap_init_node()
81 sb->map[i].depth = min(depth, bits_per_word); in sbitmap_init_node()
82 depth -= sb->map[i].depth; in sbitmap_init_node()
83 spin_lock_init(&sb->map[i].swap_lock); in sbitmap_init_node()
89 void sbitmap_resize(struct sbitmap *sb, unsigned int depth) in sbitmap_resize() argument
91 unsigned int bits_per_word = 1U << sb->shift; in sbitmap_resize()
94 for (i = 0; i < sb->map_nr; i++) in sbitmap_resize()
95 sbitmap_deferred_clear(sb, i); in sbitmap_resize()
97 sb->depth = depth; in sbitmap_resize()
98 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); in sbitmap_resize()
100 for (i = 0; i < sb->map_nr; i++) { in sbitmap_resize()
101 sb->map[i].depth = min(depth, bits_per_word); in sbitmap_resize()
102 depth -= sb->map[i].depth; in sbitmap_resize()
139 static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index, in sbitmap_find_bit_in_index() argument
145 nr = __sbitmap_get_word(&sb->map[index].word, in sbitmap_find_bit_in_index()
146 sb->map[index].depth, alloc_hint, in sbitmap_find_bit_in_index()
150 if (!sbitmap_deferred_clear(sb, index)) in sbitmap_find_bit_in_index()
157 int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin) in sbitmap_get() argument
162 index = SB_NR_TO_INDEX(sb, alloc_hint); in sbitmap_get()
170 alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); in sbitmap_get()
174 for (i = 0; i < sb->map_nr; i++) { in sbitmap_get()
175 nr = sbitmap_find_bit_in_index(sb, index, alloc_hint, in sbitmap_get()
178 nr += index << sb->shift; in sbitmap_get()
184 if (++index >= sb->map_nr) in sbitmap_get()
192 int sbitmap_get_shallow(struct sbitmap *sb, unsigned int alloc_hint, in sbitmap_get_shallow() argument
198 index = SB_NR_TO_INDEX(sb, alloc_hint); in sbitmap_get_shallow()
200 for (i = 0; i < sb->map_nr; i++) { in sbitmap_get_shallow()
202 nr = __sbitmap_get_word(&sb->map[index].word, in sbitmap_get_shallow()
203 min(sb->map[index].depth, shallow_depth), in sbitmap_get_shallow()
204 SB_NR_TO_BIT(sb, alloc_hint), true); in sbitmap_get_shallow()
206 nr += index << sb->shift; in sbitmap_get_shallow()
210 if (sbitmap_deferred_clear(sb, index)) in sbitmap_get_shallow()
215 alloc_hint = index << sb->shift; in sbitmap_get_shallow()
217 if (index >= sb->map_nr) { in sbitmap_get_shallow()
227 bool sbitmap_any_bit_set(const struct sbitmap *sb) in sbitmap_any_bit_set() argument
231 for (i = 0; i < sb->map_nr; i++) { in sbitmap_any_bit_set()
232 if (sb->map[i].word & ~sb->map[i].cleared) in sbitmap_any_bit_set()
239 bool sbitmap_any_bit_clear(const struct sbitmap *sb) in sbitmap_any_bit_clear() argument
243 for (i = 0; i < sb->map_nr; i++) { in sbitmap_any_bit_clear()
244 const struct sbitmap_word *word = &sb->map[i]; in sbitmap_any_bit_clear()
256 static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set) in __sbitmap_weight() argument
260 for (i = 0; i < sb->map_nr; i++) { in __sbitmap_weight()
261 const struct sbitmap_word *word = &sb->map[i]; in __sbitmap_weight()
271 static unsigned int sbitmap_weight(const struct sbitmap *sb) in sbitmap_weight() argument
273 return __sbitmap_weight(sb, true); in sbitmap_weight()
276 static unsigned int sbitmap_cleared(const struct sbitmap *sb) in sbitmap_cleared() argument
278 return __sbitmap_weight(sb, false); in sbitmap_cleared()
281 void sbitmap_show(struct sbitmap *sb, struct seq_file *m) in sbitmap_show() argument
283 seq_printf(m, "depth=%u\n", sb->depth); in sbitmap_show()
284 seq_printf(m, "busy=%u\n", sbitmap_weight(sb) - sbitmap_cleared(sb)); in sbitmap_show()
285 seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb)); in sbitmap_show()
286 seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift); in sbitmap_show()
287 seq_printf(m, "map_nr=%u\n", sb->map_nr); in sbitmap_show()
303 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m) in sbitmap_bitmap_show() argument
310 for (i = 0; i < sb->map_nr; i++) { in sbitmap_bitmap_show()
311 unsigned long word = READ_ONCE(sb->map[i].word); in sbitmap_bitmap_show()
312 unsigned int word_bits = READ_ONCE(sb->map[i].depth); in sbitmap_bitmap_show()
360 shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth); in sbq_calc_wake_batch()
361 depth = ((depth >> sbq->sb.shift) * shallow_depth + in sbq_calc_wake_batch()
362 min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth)); in sbq_calc_wake_batch()
375 ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node); in sbitmap_queue_init_node()
381 sbitmap_free(&sbq->sb); in sbitmap_queue_init_node()
398 sbitmap_free(&sbq->sb); in sbitmap_queue_init_node()
434 sbitmap_resize(&sbq->sb, depth); in sbitmap_queue_resize()
444 depth = READ_ONCE(sbq->sb.depth); in __sbitmap_queue_get()
449 nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin); in __sbitmap_queue_get()
475 depth = READ_ONCE(sbq->sb.depth); in __sbitmap_queue_get_shallow()
480 nr = sbitmap_get_shallow(&sbq->sb, hint, shallow_depth); in __sbitmap_queue_get_shallow()
501 sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth); in sbitmap_queue_min_shallow_depth()
590 sbitmap_deferred_clear_bit(&sbq->sb, nr); in sbitmap_queue_clear()
601 if (likely(!sbq->round_robin && nr < sbq->sb.depth)) in sbitmap_queue_clear()
632 sbitmap_show(&sbq->sb, m); in sbitmap_queue_show()