Lines Matching refs:sb
12 static int init_alloc_hint(struct sbitmap *sb, gfp_t flags) in init_alloc_hint() argument
14 unsigned depth = sb->depth; in init_alloc_hint()
16 sb->alloc_hint = alloc_percpu_gfp(unsigned int, flags); in init_alloc_hint()
17 if (!sb->alloc_hint) 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()
29 static inline unsigned update_alloc_hint_before_get(struct sbitmap *sb, in update_alloc_hint_before_get() argument
34 hint = this_cpu_read(*sb->alloc_hint); in update_alloc_hint_before_get()
37 this_cpu_write(*sb->alloc_hint, hint); in update_alloc_hint_before_get()
43 static inline void update_alloc_hint_after_get(struct sbitmap *sb, in update_alloc_hint_after_get() argument
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()
56 this_cpu_write(*sb->alloc_hint, hint); in update_alloc_hint_after_get()
83 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, in sbitmap_init_node() argument
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()
103 sb->map = NULL; in sbitmap_init_node()
108 if (init_alloc_hint(sb, flags)) 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()
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()
180 static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index, in sbitmap_find_bit_in_index() argument
183 struct sbitmap_word *map = &sb->map[index]; in sbitmap_find_bit_in_index()
188 !sb->round_robin); in sbitmap_find_bit_in_index()
198 static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint) in __sbitmap_get() argument
203 index = SB_NR_TO_INDEX(sb, alloc_hint); in __sbitmap_get()
210 if (sb->round_robin) in __sbitmap_get()
211 alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); in __sbitmap_get()
215 for (i = 0; i < sb->map_nr; i++) { in __sbitmap_get()
216 nr = sbitmap_find_bit_in_index(sb, index, alloc_hint); in __sbitmap_get()
218 nr += index << sb->shift; in __sbitmap_get()
224 if (++index >= sb->map_nr) in __sbitmap_get()
231 int sbitmap_get(struct sbitmap *sb) in sbitmap_get() argument
236 if (WARN_ON_ONCE(unlikely(!sb->alloc_hint))) in sbitmap_get()
239 depth = READ_ONCE(sb->depth); in sbitmap_get()
240 hint = update_alloc_hint_before_get(sb, depth); in sbitmap_get()
241 nr = __sbitmap_get(sb, hint); in sbitmap_get()
242 update_alloc_hint_after_get(sb, depth, hint, nr); in sbitmap_get()
248 static int __sbitmap_get_shallow(struct sbitmap *sb, in __sbitmap_get_shallow() argument
255 index = SB_NR_TO_INDEX(sb, alloc_hint); 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()
261 SB_NR_TO_BIT(sb, alloc_hint), true); 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()
283 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth) in sbitmap_get_shallow() argument
288 if (WARN_ON_ONCE(unlikely(!sb->alloc_hint))) 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()
293 nr = __sbitmap_get_shallow(sb, hint, shallow_depth); in sbitmap_get_shallow()
294 update_alloc_hint_after_get(sb, depth, hint, nr); in sbitmap_get_shallow()
300 bool sbitmap_any_bit_set(const struct sbitmap *sb) in sbitmap_any_bit_set() argument
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()
312 static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set) in __sbitmap_weight() argument
316 for (i = 0; i < sb->map_nr; i++) { in __sbitmap_weight()
317 const struct sbitmap_word *word = &sb->map[i]; in __sbitmap_weight()
327 static unsigned int sbitmap_cleared(const struct sbitmap *sb) in sbitmap_cleared() argument
329 return __sbitmap_weight(sb, false); in sbitmap_cleared()
332 unsigned int sbitmap_weight(const struct sbitmap *sb) in sbitmap_weight() argument
334 return __sbitmap_weight(sb, true) - sbitmap_cleared(sb); in sbitmap_weight()
338 void sbitmap_show(struct sbitmap *sb, struct seq_file *m) in sbitmap_show() argument
340 seq_printf(m, "depth=%u\n", sb->depth); in sbitmap_show()
341 seq_printf(m, "busy=%u\n", sbitmap_weight(sb)); in sbitmap_show()
342 seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb)); 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()
360 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m) in sbitmap_bitmap_show() argument
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()
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()
435 ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node, in sbitmap_queue_init_node()
447 sbitmap_free(&sbq->sb); in sbitmap_queue_init_node()
482 sbitmap_resize(&sbq->sb, depth); in sbitmap_queue_resize()
488 return sbitmap_get(&sbq->sb); in __sbitmap_queue_get()
495 struct sbitmap *sb = &sbq->sb; in __sbitmap_queue_get_batch() local
500 if (unlikely(sb->round_robin)) in __sbitmap_queue_get_batch()
503 depth = READ_ONCE(sb->depth); in __sbitmap_queue_get_batch()
504 hint = update_alloc_hint_before_get(sb, depth); in __sbitmap_queue_get_batch()
506 index = SB_NR_TO_INDEX(sb, hint); in __sbitmap_queue_get_batch()
508 for (i = 0; i < sb->map_nr; i++) { in __sbitmap_queue_get_batch()
509 struct sbitmap_word *map = &sb->map[index]; in __sbitmap_queue_get_batch()
529 *offset = nr + (index << sb->shift); in __sbitmap_queue_get_batch()
530 update_alloc_hint_after_get(sb, depth, hint, in __sbitmap_queue_get_batch()
536 if (++index >= sb->map_nr) in __sbitmap_queue_get_batch()
548 return sbitmap_get_shallow(&sbq->sb, shallow_depth); in __sbitmap_queue_get_shallow()
556 sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth); in sbitmap_queue_min_shallow_depth()
631 static inline void sbitmap_update_cpu_hint(struct sbitmap *sb, int cpu, int tag) in sbitmap_update_cpu_hint() argument
633 if (likely(!sb->round_robin && tag < sb->depth)) in sbitmap_update_cpu_hint()
634 data_race(*per_cpu_ptr(sb->alloc_hint, cpu) = tag); in sbitmap_update_cpu_hint()
640 struct sbitmap *sb = &sbq->sb; in sbitmap_queue_clear_batch() local
651 this_addr = &sb->map[SB_NR_TO_INDEX(sb, tag)].word; in sbitmap_queue_clear_batch()
659 mask |= (1UL << SB_NR_TO_BIT(sb, tag)); in sbitmap_queue_clear_batch()
667 sbitmap_update_cpu_hint(&sbq->sb, raw_smp_processor_id(), in sbitmap_queue_clear_batch()
685 sbitmap_deferred_clear_bit(&sbq->sb, nr); in sbitmap_queue_clear()
695 sbitmap_update_cpu_hint(&sbq->sb, cpu, nr); in sbitmap_queue_clear()
725 sbitmap_show(&sbq->sb, m); in sbitmap_queue_show()
733 seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i)); in sbitmap_queue_show()
751 seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin); in sbitmap_queue_show()