Lines Matching refs:sb
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);
17 if (!sb->alloc_hint)
20 if (depth && !sb->round_robin) {
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);
37 this_cpu_write(*sb->alloc_hint, hint);
43 static inline void update_alloc_hint_after_get(struct sbitmap *sb,
50 this_cpu_write(*sb->alloc_hint, 0);
51 } else if (nr == hint || unlikely(sb->round_robin)) {
56 this_cpu_write(*sb->alloc_hint, hint);
83 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
96 sb->shift = shift;
97 sb->depth = depth;
98 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
99 sb->round_robin = round_robin;
102 sb->map = NULL;
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);
114 if (!sb->map) {
115 free_percpu(sb->alloc_hint);
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]);
131 sb->depth = depth;
132 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
189 static int sbitmap_find_bit(struct sbitmap *sb,
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;
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);
230 if (sb->round_robin)
231 alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
235 return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
236 !sb->round_robin);
239 int sbitmap_get(struct sbitmap *sb)
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);
256 static int __sbitmap_get_shallow(struct sbitmap *sb,
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)
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);
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)
297 static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)
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);
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);
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);
346 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m)
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);
406 shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth);
407 depth = ((depth >> sbq->sb.shift) * shallow_depth +
408 min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth));
421 ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node,
435 sbitmap_free(&sbq->sb);
460 unsigned int depth = (sbq->sb.depth + users - 1) / users;
472 sbitmap_resize(&sbq->sb, depth);
478 return sbitmap_get(&sbq->sb);
485 struct sbitmap *sb = &sbq->sb;
490 if (unlikely(sb->round_robin))
493 depth = READ_ONCE(sb->depth);
494 hint = update_alloc_hint_before_get(sb, depth);
496 index = SB_NR_TO_INDEX(sb, hint);
498 for (i = 0; i < sb->map_nr; i++) {
499 struct sbitmap_word *map = &sb->map[index];
501 unsigned int map_depth = __map_depth(sb, index);
519 *offset = nr + (index << sb->shift);
520 update_alloc_hint_after_get(sb, depth, hint,
527 if (++index >= sb->map_nr)
539 return sbitmap_get_shallow(&sbq->sb, shallow_depth);
547 sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth);
603 static inline void sbitmap_update_cpu_hint(struct sbitmap *sb, int cpu, int tag)
605 if (likely(!sb->round_robin && tag < sb->depth))
606 data_race(*per_cpu_ptr(sb->alloc_hint, cpu) = tag);
612 struct sbitmap *sb = &sbq->sb;
623 this_addr = &sb->map[SB_NR_TO_INDEX(sb, tag)].word;
631 mask |= (1UL << SB_NR_TO_BIT(sb, tag));
639 sbitmap_update_cpu_hint(&sbq->sb, raw_smp_processor_id(),
657 sbitmap_deferred_clear_bit(&sbq->sb, nr);
667 sbitmap_update_cpu_hint(&sbq->sb, cpu, nr);
697 sbitmap_show(&sbq->sb, m);
705 seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i));
721 seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin);