lib/generic-radix-tree.c

Source file repositories/reference/linux-study-clean/lib/generic-radix-tree.c

File Facts

System
Linux kernel
Corpus path
lib/generic-radix-tree.c
Extension
.c
Size
5052 bytes
Lines
231
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 (!new_node) {
			new_node = genradix_alloc_node(gfp_mask);
			if (!new_node)
				return NULL;
		}

		new_node->children[0] = n;
		new_root = ((struct genradix_root *)
			    ((unsigned long) new_node | (n ? level + 1 : 0)));

		if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
			v = new_root;
			new_node = NULL;
		} else {
			new_node->children[0] = NULL;
		}
	}

	while (level--) {
		struct genradix_node **p =
			&n->children[offset >> genradix_depth_shift(level)];
		offset &= genradix_depth_size(level) - 1;

		n = READ_ONCE(*p);
		if (!n) {
			if (!new_node) {
				new_node = genradix_alloc_node(gfp_mask);
				if (!new_node)
					return NULL;
			}

			if (!(n = cmpxchg_release(p, NULL, new_node)))
				swap(n, new_node);
		}
	}

	if (new_node)
		genradix_free_node(new_node);

	return &n->data[offset];
}
EXPORT_SYMBOL(__genradix_ptr_alloc);

void *__genradix_iter_peek(struct genradix_iter *iter,
			   struct __genradix *radix,
			   size_t objs_per_page)
{
	struct genradix_root *r;
	struct genradix_node *n;
	unsigned level, i;

	if (iter->offset == SIZE_MAX)
		return NULL;

restart:
	r = READ_ONCE(radix->root);
	if (!r)
		return NULL;

	n	= genradix_root_to_node(r);
	level	= genradix_root_to_depth(r);

	if (ilog2(iter->offset) >= genradix_depth_shift(level))
		return NULL;

	while (level) {
		level--;

		i = (iter->offset >> genradix_depth_shift(level)) &
			(GENRADIX_ARY - 1);

		while (!n->children[i]) {
			size_t objs_per_ptr = genradix_depth_size(level);

			if (iter->offset + objs_per_ptr < iter->offset) {
				iter->offset	= SIZE_MAX;
				iter->pos	= SIZE_MAX;
				return NULL;
			}

			i++;
			iter->offset = round_down(iter->offset + objs_per_ptr,
						  objs_per_ptr);
			iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) *
				objs_per_page;
			if (i == GENRADIX_ARY)
				goto restart;
		}

		n = n->children[i];

Annotation

Implementation Notes