tools/testing/radix-tree/idr-test.c

Source file repositories/reference/linux-study-clean/tools/testing/radix-tree/idr-test.c

File Facts

System
Linux kernel
Corpus path
tools/testing/radix-tree/idr-test.c
Extension
.c
Size
13816 bytes
Lines
624
Domain
Support Tooling And Documentation
Bucket
tools
Inferred role
Support Tooling And Documentation: exported/initcall integration point
Status
integration implementation candidate

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

#define module_init(x)
#define module_exit(x)
#define MODULE_AUTHOR(x)
#define MODULE_DESCRIPTION(X)
#define MODULE_LICENSE(x)
#define dump_stack()    assert(0)
void ida_dump(struct ida *);

#include "../../../lib/test_ida.c"

/*
 * Check that we get the correct error when we run out of memory doing
 * allocations.  In userspace, GFP_NOWAIT will always fail an allocation.
 * The first test is for not having a bitmap available, and the second test
 * is for not being able to allocate a level of the radix tree.
 */
void ida_check_nomem(void)
{
	DEFINE_IDA(ida);
	int id;

	id = ida_alloc_min(&ida, 256, GFP_NOWAIT);
	IDA_BUG_ON(&ida, id != -ENOMEM);
	id = ida_alloc_min(&ida, 1UL << 30, GFP_NOWAIT);
	IDA_BUG_ON(&ida, id != -ENOMEM);
	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
}

/*
 * Check handling of conversions between exceptional entries and full bitmaps.
 */
void ida_check_conv_user(void)
{
	DEFINE_IDA(ida);
	unsigned long i;

	for (i = 0; i < 1000000; i++) {
		int id = ida_alloc(&ida, GFP_NOWAIT);
		if (id == -ENOMEM) {
			IDA_BUG_ON(&ida, ((i % IDA_BITMAP_BITS) !=
					  BITS_PER_XA_VALUE) &&
					 ((i % IDA_BITMAP_BITS) != 0));
			id = ida_alloc(&ida, GFP_KERNEL);
		} else {
			IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) ==
					BITS_PER_XA_VALUE);
		}
		IDA_BUG_ON(&ida, id != i);
	}
	ida_destroy(&ida);
}

void ida_check_random(void)
{
	DEFINE_IDA(ida);
	DECLARE_BITMAP(bitmap, 2048);
	unsigned int i;
	time_t s = time(NULL);

 repeat:
	memset(bitmap, 0, sizeof(bitmap));
	for (i = 0; i < 100000; i++) {
		int i = rand();
		int bit = i & 2047;
		if (test_bit(bit, bitmap)) {
			__clear_bit(bit, bitmap);
			ida_free(&ida, bit);
		} else {
			__set_bit(bit, bitmap);
			IDA_BUG_ON(&ida, ida_alloc_min(&ida, bit, GFP_KERNEL)
					!= bit);
		}
	}
	ida_destroy(&ida);
	if (time(NULL) < s + 10)
		goto repeat;
}

void ida_alloc_free_test(void)
{
	DEFINE_IDA(ida);
	unsigned long i;

	for (i = 0; i < 10000; i++)
		assert(ida_alloc_max(&ida, 20000, GFP_KERNEL) == i);
	assert(ida_alloc_range(&ida, 5, 30, GFP_KERNEL) < 0);

	for (i = 0; i < 10000; i++)
		ida_free(&ida, i);
	assert(ida_is_empty(&ida));

Annotation

Implementation Notes