lib/sbitmap.c

Source file repositories/reference/linux-study-clean/lib/sbitmap.c

File Facts

System
Linux kernel
Corpus path
lib/sbitmap.c
Extension
.c
Size
19766 bytes
Lines
803
Domain
Kernel Services
Bucket
lib
Inferred role
Kernel Services: exported/initcall integration point
Status
integration implementation candidate

Why This File Exists

Shared kernel service surface used by multiple subsystems, including helpers, cryptography, virtualization support, and async I/O infrastructure.

Dependency Surface

Detected Declarations

Annotated Snippet

if (unlikely(nr >= depth)) {
			/*
			 * We started with an offset, and we didn't reset the
			 * offset to 0 in a failure case, so start from 0 to
			 * exhaust the map.
			 */
			if (hint && wrap) {
				hint = 0;
				continue;
			}
			return -1;
		}

		if (!test_and_set_bit_lock(nr, word))
			break;

		hint = nr + 1;
		if (hint >= depth - 1)
			hint = 0;
	}

	return nr;
}

static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
				    unsigned int depth,
				    unsigned int alloc_hint,
				    bool wrap)
{
	int nr;

	do {
		nr = __sbitmap_get_word(&map->word, depth,
					alloc_hint, wrap);
		if (nr != -1)
			break;
		if (!sbitmap_deferred_clear(map, depth, alloc_hint, wrap))
			break;
	} while (1);

	return nr;
}

static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
					     int index,
					     unsigned int shallow_depth)
{
	u64 shallow_word_depth;
	unsigned int word_depth, reminder;

	word_depth = __map_depth(sb, index);
	if (shallow_depth >= sb->depth)
		return word_depth;

	shallow_word_depth = word_depth * shallow_depth;
	reminder = do_div(shallow_word_depth, sb->depth);

	if (reminder >= (index + 1) * word_depth)
		shallow_word_depth++;

	return (unsigned int)shallow_word_depth;
}

static int sbitmap_find_bit(struct sbitmap *sb,
			    unsigned int shallow_depth,
			    unsigned int index,
			    unsigned int alloc_hint,
			    bool wrap)
{
	unsigned int i;
	int nr = -1;

	for (i = 0; i < sb->map_nr; i++) {
		unsigned int depth = __map_depth_with_shallow(sb, index,
							      shallow_depth);

		if (depth)
			nr = sbitmap_find_bit_in_word(&sb->map[index], depth,
						      alloc_hint, wrap);
		if (nr != -1) {
			nr += index << sb->shift;
			break;
		}

		/* Jump to next index. */
		alloc_hint = 0;
		if (++index >= sb->map_nr)
			index = 0;
	}

Annotation

Implementation Notes