[mirror_ubuntu-artful-kernel.git] / tools / testing / radix-tree / tag_check.c

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>

#include <linux/slab.h>
#include <linux/radix-tree.h>

#include "test.h"


static void
__simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
{
	unsigned long first = 0;
	int ret;

	item_check_absent(tree, index);
	assert(item_tag_get(tree, index, tag) == 0);

	item_insert(tree, index);
	assert(item_tag_get(tree, index, tag) == 0);
	item_tag_set(tree, index, tag);
	ret = item_tag_get(tree, index, tag);
	assert(ret != 0);
	ret = tag_tagged_items(tree, NULL, first, ~0UL, 10, tag, !tag);
	assert(ret == 1);
	ret = item_tag_get(tree, index, !tag);
	assert(ret != 0);
	ret = item_delete(tree, index);
	assert(ret != 0);
	item_insert(tree, index);
	ret = item_tag_get(tree, index, tag);
	assert(ret == 0);
	ret = item_delete(tree, index);
	assert(ret != 0);
	ret = item_delete(tree, index);
	assert(ret == 0);
}

void simple_checks(void)
{
	unsigned long index;
	RADIX_TREE(tree, GFP_KERNEL);

	for (index = 0; index < 10000; index++) {
		__simple_checks(&tree, index, 0);
		__simple_checks(&tree, index, 1);
	}
	verify_tag_consistency(&tree, 0);
	verify_tag_consistency(&tree, 1);
	printv(2, "before item_kill_tree: %d allocated\n", nr_allocated);
	item_kill_tree(&tree);
	rcu_barrier();
	printv(2, "after item_kill_tree: %d allocated\n", nr_allocated);
}

/*
 * Check that tags propagate correctly when extending a tree.
 */
static void extend_checks(void)
{
	RADIX_TREE(tree, GFP_KERNEL);

	item_insert(&tree, 43);
	assert(item_tag_get(&tree, 43, 0) == 0);
	item_tag_set(&tree, 43, 0);
	assert(item_tag_get(&tree, 43, 0) == 1);
	item_insert(&tree, 1000000);
	assert(item_tag_get(&tree, 43, 0) == 1);

	item_insert(&tree, 0);
	item_tag_set(&tree, 0, 0);
	item_delete(&tree, 1000000);
	assert(item_tag_get(&tree, 43, 0) != 0);
	item_delete(&tree, 43);
	assert(item_tag_get(&tree, 43, 0) == 0);	/* crash */
	assert(item_tag_get(&tree, 0, 0) == 1);

	verify_tag_consistency(&tree, 0);

	item_kill_tree(&tree);
}

/*
 * Check that tags propagate correctly when contracting a tree.
 */
static void contract_checks(void)
{
	struct item *item;
	int tmp;
	RADIX_TREE(tree, GFP_KERNEL);

	tmp = 1<<RADIX_TREE_MAP_SHIFT;
	item_insert(&tree, tmp);
	item_insert(&tree, tmp+1);
	item_tag_set(&tree, tmp, 0);
	item_tag_set(&tree, tmp, 1);
	item_tag_set(&tree, tmp+1, 0);
	item_delete(&tree, tmp+1);
	item_tag_clear(&tree, tmp, 1);

	assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1);
	assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0);

	assert(item_tag_get(&tree, tmp, 0) == 1);
	assert(item_tag_get(&tree, tmp, 1) == 0);

	verify_tag_consistency(&tree, 0);
	item_kill_tree(&tree);
}

/*
 * Stupid tag thrasher
 *
 * Create a large linear array corresponding to the tree.   Each element in
 * the array is coherent with each node in the tree
 */

enum {
	NODE_ABSENT = 0,
	NODE_PRESENT = 1,
	NODE_TAGGED = 2,
};

#define THRASH_SIZE		(1000 * 1000)
#define N 127
#define BATCH	33

static void gang_check(struct radix_tree_root *tree,
			char *thrash_state, int tag)
{
	struct item *items[BATCH];
	int nr_found;
	unsigned long index = 0;
	unsigned long last_index = 0;

	while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
					index, BATCH, tag))) {
		int i;

		for (i = 0; i < nr_found; i++) {
			struct item *item = items[i];

			while (last_index < item->index) {
				assert(thrash_state[last_index] != NODE_TAGGED);
				last_index++;
			}
			assert(thrash_state[last_index] == NODE_TAGGED);
			last_index++;
		}
		index = items[nr_found - 1]->index + 1;
	}
}

static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag)
{
	int insert_chunk;
	int delete_chunk;
	int tag_chunk;
	int untag_chunk;
	int total_tagged = 0;
	int total_present = 0;

	for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N)
	for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N)
	for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N)
	for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) {
		int i;
		unsigned long index;
		int nr_inserted = 0;
		int nr_deleted = 0;
		int nr_tagged = 0;
		int nr_untagged = 0;
		int actual_total_tagged;
		int actual_total_present;

		for (i = 0; i < insert_chunk; i++) {
			index = rand() % THRASH_SIZE;
			if (thrash_state[index] != NODE_ABSENT)
				continue;
			item_check_absent(tree, index);
			item_insert(tree, index);
			assert(thrash_state[index] != NODE_PRESENT);
			thrash_state[index] = NODE_PRESENT;
			nr_inserted++;
			total_present++;
		}

		for (i = 0; i < delete_chunk; i++) {
			index = rand() % THRASH_SIZE;
			if (thrash_state[index] == NODE_ABSENT)
				continue;
			item_check_present(tree, index);
			if (item_tag_get(tree, index, tag)) {
				assert(thrash_state[index] == NODE_TAGGED);
				total_tagged--;
			} else {
				assert(thrash_state[index] == NODE_PRESENT);
			}
			item_delete(tree, index);
			assert(thrash_state[index] != NODE_ABSENT);
			thrash_state[index] = NODE_ABSENT;
			nr_deleted++;
			total_present--;
		}

		for (i = 0; i < tag_chunk; i++) {
			index = rand() % THRASH_SIZE;
			if (thrash_state[index] != NODE_PRESENT) {
				if (item_lookup(tree, index))
					assert(item_tag_get(tree, index, tag));
				continue;
			}
			item_tag_set(tree, index, tag);
			item_tag_set(tree, index, tag);
			assert(thrash_state[index] != NODE_TAGGED);
			thrash_state[index] = NODE_TAGGED;
			nr_tagged++;
			total_tagged++;
		}

		for (i = 0; i < untag_chunk; i++) {
			index = rand() % THRASH_SIZE;
			if (thrash_state[index] != NODE_TAGGED)
				continue;
			item_check_present(tree, index);
			assert(item_tag_get(tree, index, tag));
			item_tag_clear(tree, index, tag);
			item_tag_clear(tree, index, tag);
			assert(thrash_state[index] != NODE_PRESENT);
			thrash_state[index] = NODE_PRESENT;
			nr_untagged++;
			total_tagged--;
		}

		actual_total_tagged = 0;
		actual_total_present = 0;
		for (index = 0; index < THRASH_SIZE; index++) {
			switch (thrash_state[index]) {
			case NODE_ABSENT:
				item_check_absent(tree, index);
				break;
			case NODE_PRESENT:
				item_check_present(tree, index);
				assert(!item_tag_get(tree, index, tag));
				actual_total_present++;
				break;
			case NODE_TAGGED:
				item_check_present(tree, index);
				assert(item_tag_get(tree, index, tag));
				actual_total_present++;
				actual_total_tagged++;
				break;
			}
		}

		gang_check(tree, thrash_state, tag);

		printv(2, "%d(%d) %d(%d) %d(%d) %d(%d) / "
				"%d(%d) present, %d(%d) tagged\n",
			insert_chunk, nr_inserted,
			delete_chunk, nr_deleted,
			tag_chunk, nr_tagged,
			untag_chunk, nr_untagged,
			total_present, actual_total_present,
			total_tagged, actual_total_tagged);
	}
}

static void thrash_tags(void)
{
	RADIX_TREE(tree, GFP_KERNEL);
	char *thrash_state;

	thrash_state = malloc(THRASH_SIZE);
	memset(thrash_state, 0, THRASH_SIZE);

	do_thrash(&tree, thrash_state, 0);

	verify_tag_consistency(&tree, 0);
	item_kill_tree(&tree);
	free(thrash_state);
}

static void leak_check(void)
{
	RADIX_TREE(tree, GFP_KERNEL);

	item_insert(&tree, 1000000);
	item_delete(&tree, 1000000);
	item_kill_tree(&tree);
}

static void __leak_check(void)
{
	RADIX_TREE(tree, GFP_KERNEL);

	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
	item_insert(&tree, 1000000);
	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
	item_delete(&tree, 1000000);
	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
	item_kill_tree(&tree);
	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
}

static void single_check(void)
{
	struct item *items[BATCH];
	RADIX_TREE(tree, GFP_KERNEL);
	int ret;
	unsigned long first = 0;

	item_insert(&tree, 0);
	item_tag_set(&tree, 0, 0);
	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
	assert(ret == 1);
	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0);
	assert(ret == 0);
	verify_tag_consistency(&tree, 0);
	verify_tag_consistency(&tree, 1);
	ret = tag_tagged_items(&tree, NULL, first, 10, 10, 0, 1);
	assert(ret == 1);
	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
	assert(ret == 1);
	item_tag_clear(&tree, 0, 0);
	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
	assert(ret == 0);
	item_kill_tree(&tree);
}

void radix_tree_clear_tags_test(void)
{
	unsigned long index;
	struct radix_tree_node *node;
	struct radix_tree_iter iter;
	void **slot;

	RADIX_TREE(tree, GFP_KERNEL);

	item_insert(&tree, 0);
	item_tag_set(&tree, 0, 0);
	__radix_tree_lookup(&tree, 0, &node, &slot);
	radix_tree_clear_tags(&tree, node, slot);
	assert(item_tag_get(&tree, 0, 0) == 0);

	for (index = 0; index < 1000; index++) {
		item_insert(&tree, index);
		item_tag_set(&tree, index, 0);
	}

	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
		radix_tree_clear_tags(&tree, iter.node, slot);
		assert(item_tag_get(&tree, iter.index, 0) == 0);
	}

	item_kill_tree(&tree);
}

void tag_check(void)
{
	single_check();
	extend_checks();
	contract_checks();
	rcu_barrier();
	printv(2, "after extend_checks: %d allocated\n", nr_allocated);
	__leak_check();
	leak_check();
	rcu_barrier();
	printv(2, "after leak_check: %d allocated\n", nr_allocated);
	simple_checks();
	rcu_barrier();
	printv(2, "after simple_checks: %d allocated\n", nr_allocated);
	thrash_tags();
	rcu_barrier();
	printv(2, "after thrash_tags: %d allocated\n", nr_allocated);
	radix_tree_clear_tags_test();
}
Commit	Line	Data
1366c37e MW	1	#include <stdlib.h>
	2	#include <assert.h>
	3	#include <stdio.h>
	4	#include <string.h>
	5
	6	#include <linux/slab.h>
	7	#include <linux/radix-tree.h>
	8
	9	#include "test.h"
	10
	11
	12	static void
	13	__simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
	14	{
070c5ac2	15	unsigned long first = 0;
1366c37e MW	16	int ret;
	17
	18	item_check_absent(tree, index);
	19	assert(item_tag_get(tree, index, tag) == 0);
	20
	21	item_insert(tree, index);
	22	assert(item_tag_get(tree, index, tag) == 0);
	23	item_tag_set(tree, index, tag);
	24	ret = item_tag_get(tree, index, tag);
	25	assert(ret != 0);
268f42de	26	ret = tag_tagged_items(tree, NULL, first, ~0UL, 10, tag, !tag);
070c5ac2 MW	27	assert(ret == 1);
	28	ret = item_tag_get(tree, index, !tag);
	29	assert(ret != 0);
1366c37e MW	30	ret = item_delete(tree, index);
	31	assert(ret != 0);
	32	item_insert(tree, index);
	33	ret = item_tag_get(tree, index, tag);
	34	assert(ret == 0);
	35	ret = item_delete(tree, index);
	36	assert(ret != 0);
	37	ret = item_delete(tree, index);
	38	assert(ret == 0);
	39	}
	40
	41	void simple_checks(void)
	42	{
	43	unsigned long index;
	44	RADIX_TREE(tree, GFP_KERNEL);
	45
	46	for (index = 0; index < 10000; index++) {
	47	__simple_checks(&tree, index, 0);
	48	__simple_checks(&tree, index, 1);
	49	}
	50	verify_tag_consistency(&tree, 0);
	51	verify_tag_consistency(&tree, 1);
73bc029b	52	printv(2, "before item_kill_tree: %d allocated\n", nr_allocated);
1366c37e	53	item_kill_tree(&tree);
af1c5cca	54	rcu_barrier();
73bc029b	55	printv(2, "after item_kill_tree: %d allocated\n", nr_allocated);
1366c37e MW	56	}
	57
	58	/*
	59	* Check that tags propagate correctly when extending a tree.
	60	*/
	61	static void extend_checks(void)
	62	{
	63	RADIX_TREE(tree, GFP_KERNEL);
	64
	65	item_insert(&tree, 43);
	66	assert(item_tag_get(&tree, 43, 0) == 0);
	67	item_tag_set(&tree, 43, 0);
	68	assert(item_tag_get(&tree, 43, 0) == 1);
	69	item_insert(&tree, 1000000);
	70	assert(item_tag_get(&tree, 43, 0) == 1);
	71
	72	item_insert(&tree, 0);
	73	item_tag_set(&tree, 0, 0);
	74	item_delete(&tree, 1000000);
	75	assert(item_tag_get(&tree, 43, 0) != 0);
	76	item_delete(&tree, 43);
	77	assert(item_tag_get(&tree, 43, 0) == 0); /* crash */
	78	assert(item_tag_get(&tree, 0, 0) == 1);
	79
	80	verify_tag_consistency(&tree, 0);
	81
	82	item_kill_tree(&tree);
	83	}
	84
	85	/*
	86	* Check that tags propagate correctly when contracting a tree.
	87	*/
	88	static void contract_checks(void)
	89	{
	90	struct item *item;
	91	int tmp;
	92	RADIX_TREE(tree, GFP_KERNEL);
	93
	94	tmp = 1<<RADIX_TREE_MAP_SHIFT;
	95	item_insert(&tree, tmp);
	96	item_insert(&tree, tmp+1);
	97	item_tag_set(&tree, tmp, 0);
	98	item_tag_set(&tree, tmp, 1);
	99	item_tag_set(&tree, tmp+1, 0);
	100	item_delete(&tree, tmp+1);
	101	item_tag_clear(&tree, tmp, 1);
	102
	103	assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1);
	104	assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0);
	105
	106	assert(item_tag_get(&tree, tmp, 0) == 1);
	107	assert(item_tag_get(&tree, tmp, 1) == 0);
	108
	109	verify_tag_consistency(&tree, 0);
	110	item_kill_tree(&tree);
	111	}
	112
	113	/*
	114	* Stupid tag thrasher
	115	*
	116	* Create a large linear array corresponding to the tree. Each element in
	117	* the array is coherent with each node in the tree
	118	*/
	119
120	enum {
121	NODE_ABSENT = 0,
122	NODE_PRESENT = 1,
123	NODE_TAGGED = 2,
124	};
125
b301aac5	126	#define THRASH_SIZE (1000 * 1000)
1366c37e MW	127	#define N 127
	128	#define BATCH 33
	129
	130	static void gang_check(struct radix_tree_root *tree,
	131	char *thrash_state, int tag)
	132	{
	133	struct item *items[BATCH];
	134	int nr_found;
	135	unsigned long index = 0;
	136	unsigned long last_index = 0;
	137
	138	while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
	139	index, BATCH, tag))) {
	140	int i;
	141
	142	for (i = 0; i < nr_found; i++) {
	143	struct item *item = items[i];
	144
	145	while (last_index < item->index) {
	146	assert(thrash_state[last_index] != NODE_TAGGED);
	147	last_index++;
	148	}
	149	assert(thrash_state[last_index] == NODE_TAGGED);
	150	last_index++;
	151	}
	152	index = items[nr_found - 1]->index + 1;
	153	}
	154	}
	155
	156	static void do_thrash(struct radix_tree_root tree, char thrash_state, int tag)
	157	{
	158	int insert_chunk;
	159	int delete_chunk;
	160	int tag_chunk;
	161	int untag_chunk;
	162	int total_tagged = 0;
	163	int total_present = 0;
	164
	165	for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N)
	166	for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N)
	167	for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N)
	168	for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) {
	169	int i;
	170	unsigned long index;
	171	int nr_inserted = 0;
	172	int nr_deleted = 0;
	173	int nr_tagged = 0;
	174	int nr_untagged = 0;
	175	int actual_total_tagged;
	176	int actual_total_present;
	177
	178	for (i = 0; i < insert_chunk; i++) {
	179	index = rand() % THRASH_SIZE;
	180	if (thrash_state[index] != NODE_ABSENT)
	181	continue;
	182	item_check_absent(tree, index);
	183	item_insert(tree, index);
	184	assert(thrash_state[index] != NODE_PRESENT);
	185	thrash_state[index] = NODE_PRESENT;
	186	nr_inserted++;
	187	total_present++;
	188	}
	189
	190	for (i = 0; i < delete_chunk; i++) {
191	index = rand() % THRASH_SIZE;
192	if (thrash_state[index] == NODE_ABSENT)
193	continue;
194	item_check_present(tree, index);
195	if (item_tag_get(tree, index, tag)) {
196	assert(thrash_state[index] == NODE_TAGGED);
197	total_tagged--;
198	} else {
199	assert(thrash_state[index] == NODE_PRESENT);
200	}
201	item_delete(tree, index);
202	assert(thrash_state[index] != NODE_ABSENT);
203	thrash_state[index] = NODE_ABSENT;
204	nr_deleted++;
205	total_present--;
206	}
207
208	for (i = 0; i < tag_chunk; i++) {
209	index = rand() % THRASH_SIZE;
210	if (thrash_state[index] != NODE_PRESENT) {
211	if (item_lookup(tree, index))
212	assert(item_tag_get(tree, index, tag));
213	continue;
214	}
215	item_tag_set(tree, index, tag);
216	item_tag_set(tree, index, tag);
217	assert(thrash_state[index] != NODE_TAGGED);
218	thrash_state[index] = NODE_TAGGED;
219	nr_tagged++;
220	total_tagged++;
221	}
222
223	for (i = 0; i < untag_chunk; i++) {
224	index = rand() % THRASH_SIZE;
225	if (thrash_state[index] != NODE_TAGGED)
226	continue;
227	item_check_present(tree, index);
228	assert(item_tag_get(tree, index, tag));
229	item_tag_clear(tree, index, tag);
230	item_tag_clear(tree, index, tag);
231	assert(thrash_state[index] != NODE_PRESENT);
232	thrash_state[index] = NODE_PRESENT;
233	nr_untagged++;
234	total_tagged--;
235	}
236
237	actual_total_tagged = 0;
238	actual_total_present = 0;
239	for (index = 0; index < THRASH_SIZE; index++) {
240	switch (thrash_state[index]) {
241	case NODE_ABSENT:
242	item_check_absent(tree, index);
243	break;
244	case NODE_PRESENT:
245	item_check_present(tree, index);
246	assert(!item_tag_get(tree, index, tag));
247	actual_total_present++;
248	break;
249	case NODE_TAGGED:
250	item_check_present(tree, index);
251	assert(item_tag_get(tree, index, tag));
252	actual_total_present++;
253	actual_total_tagged++;
254	break;
255	}
256	}
257
258	gang_check(tree, thrash_state, tag);
259
73bc029b	260	printv(2, "%d(%d) %d(%d) %d(%d) %d(%d) / "
1366c37e MW	261	"%d(%d) present, %d(%d) tagged\n",
	262	insert_chunk, nr_inserted,
	263	delete_chunk, nr_deleted,
	264	tag_chunk, nr_tagged,
	265	untag_chunk, nr_untagged,
	266	total_present, actual_total_present,
	267	total_tagged, actual_total_tagged);
	268	}
	269	}
	270
	271	static void thrash_tags(void)
	272	{
	273	RADIX_TREE(tree, GFP_KERNEL);
	274	char *thrash_state;
	275
	276	thrash_state = malloc(THRASH_SIZE);
	277	memset(thrash_state, 0, THRASH_SIZE);
	278
	279	do_thrash(&tree, thrash_state, 0);
	280
	281	verify_tag_consistency(&tree, 0);
	282	item_kill_tree(&tree);
	283	free(thrash_state);
	284	}
	285
	286	static void leak_check(void)
	287	{
	288	RADIX_TREE(tree, GFP_KERNEL);
	289
	290	item_insert(&tree, 1000000);
	291	item_delete(&tree, 1000000);
	292	item_kill_tree(&tree);
	293	}
	294
	295	static void __leak_check(void)
	296	{
	297	RADIX_TREE(tree, GFP_KERNEL);
	298
73bc029b	299	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
1366c37e	300	item_insert(&tree, 1000000);
73bc029b	301	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
1366c37e	302	item_delete(&tree, 1000000);
73bc029b	303	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
1366c37e	304	item_kill_tree(&tree);
73bc029b	305	printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
1366c37e MW	306	}
	307
	308	static void single_check(void)
	309	{
	310	struct item *items[BATCH];
	311	RADIX_TREE(tree, GFP_KERNEL);
	312	int ret;
070c5ac2	313	unsigned long first = 0;
1366c37e MW	314
	315	item_insert(&tree, 0);
	316	item_tag_set(&tree, 0, 0);
	317	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
	318	assert(ret == 1);
	319	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0);
	320	assert(ret == 0);
	321	verify_tag_consistency(&tree, 0);
	322	verify_tag_consistency(&tree, 1);
268f42de	323	ret = tag_tagged_items(&tree, NULL, first, 10, 10, 0, 1);
070c5ac2 MW	324	assert(ret == 1);
	325	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
	326	assert(ret == 1);
092bc0b2 MW	327	item_tag_clear(&tree, 0, 0);
	328	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
	329	assert(ret == 0);
1366c37e MW	330	item_kill_tree(&tree);
	331	}
	332
c629a344 RS	333	void radix_tree_clear_tags_test(void)
	334	{
	335	unsigned long index;
	336	struct radix_tree_node *node;
	337	struct radix_tree_iter iter;
	338	void **slot;
	339
	340	RADIX_TREE(tree, GFP_KERNEL);
	341
	342	item_insert(&tree, 0);
	343	item_tag_set(&tree, 0, 0);
	344	__radix_tree_lookup(&tree, 0, &node, &slot);
	345	radix_tree_clear_tags(&tree, node, slot);
	346	assert(item_tag_get(&tree, 0, 0) == 0);
	347
	348	for (index = 0; index < 1000; index++) {
	349	item_insert(&tree, index);
	350	item_tag_set(&tree, index, 0);
	351	}
	352
	353	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
	354	radix_tree_clear_tags(&tree, iter.node, slot);
	355	assert(item_tag_get(&tree, iter.index, 0) == 0);
	356	}
	357
	358	item_kill_tree(&tree);
	359	}
	360
1366c37e MW	361	void tag_check(void)
	362	{
	363	single_check();
	364	extend_checks();
	365	contract_checks();
af1c5cca	366	rcu_barrier();
73bc029b	367	printv(2, "after extend_checks: %d allocated\n", nr_allocated);
1366c37e MW	368	__leak_check();
1366c37e MW	369	leak_check();
af1c5cca	370	rcu_barrier();
73bc029b	371	printv(2, "after leak_check: %d allocated\n", nr_allocated);
1366c37e	372	simple_checks();
af1c5cca	373	rcu_barrier();
73bc029b	374	printv(2, "after simple_checks: %d allocated\n", nr_allocated);
1366c37e	375	thrash_tags();
af1c5cca	376	rcu_barrier();
73bc029b	377	printv(2, "after thrash_tags: %d allocated\n", nr_allocated);
c629a344	378	radix_tree_clear_tags_test();
1366c37e	379	}