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()
101 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,  in sbitmap_init_node()  argument
115 	sb->shift = shift;  in sbitmap_init_node()
116 	sb->depth = depth;  in sbitmap_init_node()
117 	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);  in sbitmap_init_node()
118 	sb->round_robin = round_robin;  in sbitmap_init_node()
121 		sb->map = NULL;  in sbitmap_init_node()
126 		if (init_alloc_hint(sb, flags))  in sbitmap_init_node()
129 		sb->alloc_hint = NULL;  in sbitmap_init_node()
132 	sb->map = kvzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node);  in sbitmap_init_node()
133 	if (!sb->map) {  in sbitmap_init_node()
134 		free_percpu(sb->alloc_hint);  in sbitmap_init_node()
138 	for (i = 0; i < sb->map_nr; i++)  in sbitmap_init_node()
139 		raw_spin_lock_init(&sb->map[i].swap_lock);  in sbitmap_init_node()
145 void sbitmap_resize(struct sbitmap *sb, unsigned int depth)  in sbitmap_resize()  argument
147 	unsigned int bits_per_word = 1U << sb->shift;  in sbitmap_resize()
150 	for (i = 0; i < sb->map_nr; i++)  in sbitmap_resize()
151 		sbitmap_deferred_clear(&sb->map[i], 0, 0, 0);  in sbitmap_resize()
153 	sb->depth = depth;  in sbitmap_resize()
154 	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);  in sbitmap_resize()
211 static int sbitmap_find_bit(struct sbitmap *sb,  in sbitmap_find_bit()  argument
220 	for (i = 0; i < sb->map_nr; i++) {  in sbitmap_find_bit()
221 		nr = sbitmap_find_bit_in_word(&sb->map[index],  in sbitmap_find_bit()
223 						    __map_depth(sb, index),  in sbitmap_find_bit()
228 			nr += index << sb->shift;  in sbitmap_find_bit()
234 		if (++index >= sb->map_nr)  in sbitmap_find_bit()
241 static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)  in __sbitmap_get()  argument
245 	index = SB_NR_TO_INDEX(sb, alloc_hint);  in __sbitmap_get()
252 	if (sb->round_robin)  in __sbitmap_get()
253 		alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);  in __sbitmap_get()
257 	return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,  in __sbitmap_get()
258 				!sb->round_robin);  in __sbitmap_get()
261 int sbitmap_get(struct sbitmap *sb)  in sbitmap_get()  argument
266 	if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))  in sbitmap_get()
269 	depth = READ_ONCE(sb->depth);  in sbitmap_get()
270 	hint = update_alloc_hint_before_get(sb, depth);  in sbitmap_get()
271 	nr = __sbitmap_get(sb, hint);  in sbitmap_get()
272 	update_alloc_hint_after_get(sb, depth, hint, nr);  in sbitmap_get()
278 static int __sbitmap_get_shallow(struct sbitmap *sb,  in __sbitmap_get_shallow()  argument
284 	index = SB_NR_TO_INDEX(sb, alloc_hint);  in __sbitmap_get_shallow()
285 	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);  in __sbitmap_get_shallow()
287 	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);  in __sbitmap_get_shallow()
290 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)  in sbitmap_get_shallow()  argument
295 	if (WARN_ON_ONCE(unlikely(!sb->alloc_hint)))  in sbitmap_get_shallow()
298 	depth = READ_ONCE(sb->depth);  in sbitmap_get_shallow()
299 	hint = update_alloc_hint_before_get(sb, depth);  in sbitmap_get_shallow()
300 	nr = __sbitmap_get_shallow(sb, hint, shallow_depth);  in sbitmap_get_shallow()
301 	update_alloc_hint_after_get(sb, depth, hint, nr);  in sbitmap_get_shallow()
307 bool sbitmap_any_bit_set(const struct sbitmap *sb)  in sbitmap_any_bit_set()  argument
311 	for (i = 0; i < sb->map_nr; i++) {  in sbitmap_any_bit_set()
312 		if (sb->map[i].word & ~sb->map[i].cleared)  in sbitmap_any_bit_set()
319 static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)  in __sbitmap_weight()  argument
323 	for (i = 0; i < sb->map_nr; i++) {  in __sbitmap_weight()
324 		const struct sbitmap_word *word = &sb->map[i];  in __sbitmap_weight()
325 		unsigned int word_depth = __map_depth(sb, i);  in __sbitmap_weight()
335 static unsigned int sbitmap_cleared(const struct sbitmap *sb)  in sbitmap_cleared()  argument
337 	return __sbitmap_weight(sb, false);  in sbitmap_cleared()
340 unsigned int sbitmap_weight(const struct sbitmap *sb)  in sbitmap_weight()  argument
342 	return __sbitmap_weight(sb, true) - sbitmap_cleared(sb);  in sbitmap_weight()
346 void sbitmap_show(struct sbitmap *sb, struct seq_file *m)  in sbitmap_show()  argument
348 	seq_printf(m, "depth=%u\n", sb->depth);  in sbitmap_show()
349 	seq_printf(m, "busy=%u\n", sbitmap_weight(sb));  in sbitmap_show()
350 	seq_printf(m, "cleared=%u\n", sbitmap_cleared(sb));  in sbitmap_show()
351 	seq_printf(m, "bits_per_word=%u\n", 1U << sb->shift);  in sbitmap_show()
352 	seq_printf(m, "map_nr=%u\n", sb->map_nr);  in sbitmap_show()
368 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m)  in sbitmap_bitmap_show()  argument
375 	for (i = 0; i < sb->map_nr; i++) {  in sbitmap_bitmap_show()
376 		unsigned long word = READ_ONCE(sb->map[i].word);  in sbitmap_bitmap_show()
377 		unsigned long cleared = READ_ONCE(sb->map[i].cleared);  in sbitmap_bitmap_show()
378 		unsigned int word_bits = __map_depth(sb, i);  in sbitmap_bitmap_show()
423 	shallow_depth = min(1U << sbq->sb.shift, sbq->min_shallow_depth);  in sbq_calc_wake_batch()
424 	depth = ((depth >> sbq->sb.shift) * shallow_depth +  in sbq_calc_wake_batch()
425 		 min(depth & ((1U << sbq->sb.shift) - 1), shallow_depth));  in sbq_calc_wake_batch()
438 	ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node,  in sbitmap_queue_init_node()
452 		sbitmap_free(&sbq->sb);  in sbitmap_queue_init_node()
477 	unsigned int depth = (sbq->sb.depth + users - 1) / users;  in sbitmap_queue_recalculate_wake_batch()
489 	sbitmap_resize(&sbq->sb, depth);  in sbitmap_queue_resize()
495 	return sbitmap_get(&sbq->sb);  in __sbitmap_queue_get()
502 	struct sbitmap *sb = &sbq->sb;  in __sbitmap_queue_get_batch()  local
507 	if (unlikely(sb->round_robin))  in __sbitmap_queue_get_batch()
510 	depth = READ_ONCE(sb->depth);  in __sbitmap_queue_get_batch()
511 	hint = update_alloc_hint_before_get(sb, depth);  in __sbitmap_queue_get_batch()
513 	index = SB_NR_TO_INDEX(sb, hint);  in __sbitmap_queue_get_batch()
515 	for (i = 0; i < sb->map_nr; i++) {  in __sbitmap_queue_get_batch()
516 		struct sbitmap_word *map = &sb->map[index];  in __sbitmap_queue_get_batch()
518 		unsigned int map_depth = __map_depth(sb, index);  in __sbitmap_queue_get_batch()
536 				*offset = nr + (index << sb->shift);  in __sbitmap_queue_get_batch()
537 				update_alloc_hint_after_get(sb, depth, hint,  in __sbitmap_queue_get_batch()
544 		if (++index >= sb->map_nr)  in __sbitmap_queue_get_batch()
556 	return sbitmap_get_shallow(&sbq->sb, shallow_depth);  in sbitmap_queue_get_shallow()
564 	sbitmap_queue_update_wake_batch(sbq, sbq->sb.depth);  in sbitmap_queue_min_shallow_depth()
620 static inline void sbitmap_update_cpu_hint(struct sbitmap *sb, int cpu, int tag)  in sbitmap_update_cpu_hint()  argument
622 	if (likely(!sb->round_robin && tag < sb->depth))  in sbitmap_update_cpu_hint()
623 		data_race(*per_cpu_ptr(sb->alloc_hint, cpu) = tag);  in sbitmap_update_cpu_hint()
629 	struct sbitmap *sb = &sbq->sb;  in sbitmap_queue_clear_batch()  local
640 		this_addr = &sb->map[SB_NR_TO_INDEX(sb, tag)].word;  in sbitmap_queue_clear_batch()
648 		mask |= (1UL << SB_NR_TO_BIT(sb, tag));  in sbitmap_queue_clear_batch()
656 	sbitmap_update_cpu_hint(&sbq->sb, raw_smp_processor_id(),  in sbitmap_queue_clear_batch()
674 	sbitmap_deferred_clear_bit(&sbq->sb, nr);  in sbitmap_queue_clear()
684 	sbitmap_update_cpu_hint(&sbq->sb, cpu, nr);  in sbitmap_queue_clear()
714 	sbitmap_show(&sbq->sb, m);  in sbitmap_queue_show()
722 		seq_printf(m, "%u", *per_cpu_ptr(sbq->sb.alloc_hint, i));  in sbitmap_queue_show()
738 	seq_printf(m, "round_robin=%d\n", sbq->sb.round_robin);  in sbitmap_queue_show()