path: root/lib/sbitmap.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright (C) 2016 Facebook
 * Copyright (C) 2013-2014 Jens Axboe
 */

#include <linux/sched.h>
#include <linux/random.h>
#include <linux/sbitmap.h>
#include <linux/seq_file.h>

static int init_alloc_hint(struct sbitmap *sb, gfp_t flags)
{
	unsigned depth = sb->depth;

	sb->alloc_hint = alloc_percpu_gfp(unsigned int, flags);
	if (!sb->alloc_hint)
		return -ENOMEM;

	if (depth && !sb->round_robin) {
		int i;

		for_each_possible_cpu(i)
			*per_cpu_ptr(sb->alloc_hint, i) = get_random_u32_below(depth);
	}
	return 0;
}

static inline unsigned update_alloc_hint_before_get(struct sbitmap *sb,
						    unsigned int depth)
{
	unsigned hint;

	hint = this_cpu_read(*sb->alloc_hint);
	if (unlikely(hint >= depth)) {
		hint = depth ? get_random_u32_below(depth) : 0;
		this_cpu_write(*sb->alloc_hint, hint);
	}

	return hint;
}

static inline void update_alloc_hint_after_get(struct sbitmap *sb,
					       unsigned int depth,
					       unsigned int hint,
					       unsigned int nr)
{
	if (nr == -1) {
		/* If the map is full, a hint won't do us much good. */
		this_cpu_write(*sb->alloc_hint, 0);
	} else if (nr == hint || unlikely(sb->round_robin)) {
		/* Only update the hint if we used it. */
		hint = nr + 1;
		if (hint >= depth - 1)
			hint = 0;
		this_cpu_write(*sb->alloc_hint, hint);
	}
}

/*
 * See if we have deferred clears that we can batch move
 */
static inline bool sbitmap_deferred_clear(struct sbitmap_word *map,
		unsigned int depth, unsigned int alloc_hint, bool wrap)
{
	unsigned long mask, word_mask;

	guard(raw_spinlock_irqsave)(&map->swap_lock);

	if (!map->cleared) {
		if (depth == 0)
			return false;

		word_mask = (~0UL) >> (BITS_PER_LONG - depth);
		/*
		 * The current behavior is to always retry after moving
		 * ->cleared to word, and we change it to retry in case
		 * of any free bits. To avoid an infinite loop, we need
		 * to take wrap & alloc_hint into account, otherwise a
		 * soft lockup may occur.
		 */
		if (!wrap && alloc_hint)
			word_mask &= ~((1UL << alloc_hint) - 1);

		return (READ_ONCE(map->word) & word_mask) != word_mask;
	}

	/*
	 * First get a stable cleared mask, setting the old mask to 0.
	 */
	mask = xchg(&map->cleared, 0);

	/*
	 * Now clear the masked bits in our free word
	 */
	atomic_long_andnot(mask, (atomic_long_t *)&map->word);
	BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word));
	return true;
}

int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
		      gfp_t flags, int node, bool round_robin,
		      bool alloc_hint)
{
	unsigned int bits_per_word;
	int i;

	if (shift < 0)
		shift = sbitmap_calculate_shift(depth);

	bits_per_word = 1U << shift;
	if (bits_per_word > BITS_PER_LONG)
		return -EINVAL;

	sb->shift = shift;
	sb->depth = depth;
	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
	sb->round_robin = round_robin;

	if (depth == 0) {
		sb->map = NULL;
		return 0;
	}

	if (alloc_hint) {
		if (init_alloc_hint(sb, flags))
			return -ENOMEM;
	} else {
		sb->alloc_hint = NULL;
	}

	sb->map = kvzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node);
	if (!sb->map) {
		free_percpu(sb->alloc_hint);
		return -ENOMEM;
	}

	for (i = 0; i < sb->map_nr; i++)
		raw_spin_lock_init(&sb->map[i].swap_lock);

	return 0;
}
EXPORT_SYMBOL_GPL(sbitmap_init_node);

void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
{
	unsigned int bits_per_word = 1U << sb->shift;
	unsigned int i;

	for (i = 0; i < sb->map_nr; i++)
		sbitmap_deferred_clear(&sb->map[i], 0, 0, 0);

	sb->depth = depth;
	sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word);
}
EXPORT_SYMBOL_GPL(sbitmap_resize);

static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
			      unsigned int hint, bool wrap)
{
	int nr;

	/* don't wrap if starting from 0 */
	wrap = wrap && hint;

	while (1) {
		nr = find_next_zero_bit(word, depth, hint);
		if (unlikely(nr >= </