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) = get_random_u32_below(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
96 	sb->shift = shift;  in sbitmap_init_node()
97 	sb->depth = depth;  in sbitmap_init_node()
98 	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);  in sbitmap_init_node()
99 	sb->round_robin = round_robin;  in sbitmap_init_node()
102 		sb->map = NULL;  in sbitmap_init_node()
107 		if (init_alloc_hint(sb, flags))  in sbitmap_init_node()
110 		sb->alloc_hint = NULL;  in sbitmap_init_node()
113 	sb->map = kvzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node);  in sbitmap_init_node()
114 	if (!sb->map) {  in sbitmap_init_node()
115 		free_percpu(sb->alloc_hint);  in sbitmap_init_node()
123 void sbitmap_resize(struct sbitmap *sb, unsigned int depth)  in sbitmap_resize()  argument
125 	unsigned int bits_per_word = 1U << sb->shift;  in sbitmap_resize()
128 	for (i = 0; i < sb->map_nr; i++)  in sbitmap_resize()
129 		sbitmap_deferred_clear(&sb->map[i]);  in sbitmap_resize()
131 	sb->depth = depth;  in sbitmap_resize()
132 	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);  in sbitmap_resize()
189 static int sbitmap_find_bit(struct sbitmap *sb,  in sbitmap_find_bit()  argument
198 	for (i = 0; i < sb->map_nr; i++) {  in sbitmap_find_bit()
199 		nr = sbitmap_find_bit_in_word(&sb->map[index],  in sbitmap_find_bit()
201 						    __map_depth(sb, index),  in sbitmap_find_bit()
206 			nr += index << sb->shift;  in sbitmap_find_bit()
212 		if (++index >= sb->map_nr)  in sbitmap_find_bit()
219 static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)  in __sbitmap_get()  argument
223 	index = SB_NR_TO_INDEX(sb, alloc_hint);  in __sbitmap_get()
230 	if (sb->round_robin)  in __sbitmap_get()
231 		alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);  in __sbitmap_get()
235 	return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,  in __sbitmap_get()
236 				!sb->round_robin);  in __sbitmap_get()
239 int sbitmap_get(struct sbitmap *sb)  in sbitmap_get()  argument
244 	if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))  in sbitmap_get()
247 	depth = READ_ONCE(sb->depth);  in sbitmap_get()
248 	hint = update_alloc_hint_before_get(sb, depth);  in sbitmap_get()
249 	nr = __sbitmap_get(sb, hint);  in sbitmap_get()
250 	update_alloc_hint_after_get(sb, depth, hint, nr);  in sbitmap_get()
256 static int __sbitmap_get_shallow(struct sbitmap *sb,  in __sbitmap_get_shallow()  argument
262 	index = SB_NR_TO_INDEX(sb, alloc_hint);  in __sbitmap_get_shallow()
263 	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);  in __sbitmap_get_shallow()
265 	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);  in __sbitmap_get_shallow()
268 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)  in sbitmap_get_shallow()  argument
273 	if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))  in sbitmap_get_shallow()
276 	depth = READ_ONCE(sb->depth);  in sbitmap_get_shallow()
277 	hint = update_alloc_hint_before_get(sb, depth);  in sbitmap_get_shallow()
278 	nr = __sbitmap_get_shallow(sb, hint, shallow_depth);  in sbitmap_get_shallow()
279 	update_alloc_hint_after_get(sb, depth, hint, nr);  in sbitmap_get_shallow()
285 bool sbitmap_any_bit_set(const struct sbitmap *sb)  in sbitmap_any_bit_set()  argument
289 	for (i = 0; i < sb->map_nr; i++) {  in sbitmap_any_bit_set()
290 		if (sb->map[i].word & ~sb->map[i].cleared)  in sbitmap_any_bit_set()
297 static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)  in __sbitmap_weight()  argument
301 	for (i = 0; i < sb->map_nr; i++) {  in __sbitmap_weight()
302 		const struct sbitmap_word *word = &sb->map[i];  in __sbitmap_weight()
303 		unsigned int word_depth = __map_depth(sb, i);  in __sbitmap_weight()
313 static unsigned int sbitmap_cleared(const struct sbitmap *sb)  in sbitmap_cleared()  argument
315 	return __sbitmap_weight(sb, false);  in sbitmap_cleared()
318 unsigned int sbitmap_weight(const struct sbitmap *sb)  in sbitmap_weight()  argument
320 	return __sbitmap_weight(sb, true) - sbitmap_cleared(sb);  in sbitmap_weight()
324 void sbitmap_show(struct sbitmap *sb, struct seq_file *m)  in sbitmap_show()  argument
326 	seq_printf(m, "depth=%u\n", sb->depth);  in sbitmap_show()
327 	seq_printf(m, "busy=%u\n", sbitmap_weight(sb));  in sbitmap_show()
328 	seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb));  in sbitmap_show()
329 	seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);  in sbitmap_show()
330 	seq_printf(m, "map_nr=%u\n", sb->map_nr);  in sbitmap_show()
346 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m)  in sbitmap_bitmap_show()  argument
353 	for (i = 0; i < sb->map_nr; i++) {  in sbitmap_bitmap_show()
354 		unsigned long word = READ_ONCE(sb->map[i].word);  in sbitmap_bitmap_show()
355 		unsigned long cleared = READ_ONCE(sb->map[i].cleared);  in sbitmap_bitmap_show()
356 		unsigned int word_bits = __map_depth(sb, i);  in sbitmap_bitmap_show()
401 	shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth);  in sbq_calc_wake_batch()
402 	depth = ((depth >> sbq->sb.shift) * shallow_depth +  in sbq_calc_wake_batch()
403 		 min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth));  in sbq_calc_wake_batch()
416 	ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node,  in sbitmap_queue_init_node()
430 		sbitmap_free(&sbq->sb);  in sbitmap_queue_init_node()
455 	unsigned int depth = (sbq->sb.depth + users - 1) / users;  in sbitmap_queue_recalculate_wake_batch()
467 	sbitmap_resize(&sbq->sb, depth);  in sbitmap_queue_resize()
473 	return sbitmap_get(&sbq->sb);  in __sbitmap_queue_get()
480 	struct sbitmap *sb = &sbq->sb;  in __sbitmap_queue_get_batch()  local
485 	if (unlikely(sb->round_robin))  in __sbitmap_queue_get_batch()
488 	depth = READ_ONCE(sb->depth);  in __sbitmap_queue_get_batch()
489 	hint = update_alloc_hint_before_get(sb, depth);  in __sbitmap_queue_get_batch()
491 	index = SB_NR_TO_INDEX(sb, hint);  in __sbitmap_queue_get_batch()
493 	for (i = 0; i < sb->map_nr; i++) {  in __sbitmap_queue_get_batch()
494 		struct sbitmap_word *map = &sb->map[index];  in __sbitmap_queue_get_batch()
496 		unsigned int map_depth = __map_depth(sb, index);  in __sbitmap_queue_get_batch()
514 				*offset = nr + (index << sb->shift);  in __sbitmap_queue_get_batch()
515 				update_alloc_hint_after_get(sb, depth, hint,  in __sbitmap_queue_get_batch()
522 		if (++index >= sb->map_nr)  in __sbitmap_queue_get_batch()
534 	return sbitmap_get_shallow(&sbq->sb, shallow_depth);  in sbitmap_queue_get_shallow()
542 	sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth);  in sbitmap_queue_min_shallow_depth()
598 static inline void sbitmap_update_cpu_hint(struct sbitmap *sb, int cpu, int tag)  in sbitmap_update_cpu_hint()  argument
600 	if (likely(!sb->round_robin && tag < sb->depth))  in sbitmap_update_cpu_hint()
601 		data_race(*per_cpu_ptr(sb->alloc_hint, cpu) = tag);  in sbitmap_update_cpu_hint()
607 	struct sbitmap *sb = &sbq->sb;  in sbitmap_queue_clear_batch()  local
618 		this_addr = &sb->map[SB_NR_TO_INDEX(sb, tag)].word;  in sbitmap_queue_clear_batch()
626 		mask |= (1UL << SB_NR_TO_BIT(sb, tag));  in sbitmap_queue_clear_batch()
634 	sbitmap_update_cpu_hint(&sbq->sb, raw_smp_processor_id(),  in sbitmap_queue_clear_batch()
652 	sbitmap_deferred_clear_bit(&sbq->sb, nr);  in sbitmap_queue_clear()
662 	sbitmap_update_cpu_hint(&sbq->sb, cpu, nr);  in sbitmap_queue_clear()
692 	sbitmap_show(&sbq->sb, m);  in sbitmap_queue_show()
700 		seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i));  in sbitmap_queue_show()
716 	seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin);  in sbitmap_queue_show()