// SPDX-License-Identifier: GPL-2.0/* * Regression2 * Description: * Toshiyuki Okajima describes the following radix-tree bug: * * In the following case, we can get a hangup on *   radix_radix_tree_gang_lookup_tag_slot. * * 0.  The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of *     a certain item has PAGECACHE_TAG_DIRTY. * 1.  radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY, *     PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag *     for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with *     PAGECACHE_TAG_DIRTY within the range from start to end. As the result, *     There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has *     PAGECACHE_TAG_TOWRITE. * 2.  An item is added into the radix tree and then the level of it is *     extended into 2 from 1. At that time, the new radix tree node succeeds *     the tag status of the root tag. Therefore the tag of the new radix tree *     node has PAGECACHE_TAG_TOWRITE but there is not slot with *     PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node. * 3.  The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY. * 4.  All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are *     released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the *     radix tree.) As the result, the slot of the radix tree node is NULL but *     the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE. * 5.  radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls *     __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't *     change the index that is the input and output parameter. Because the 1st *     slot of the radix tree node is NULL, but the tag which corresponds to *     the slot has PAGECACHE_TAG_TOWRITE. *     Therefore radix_tree_gang_lookup_tag_slot tries to get some items by *     calling __lookup_tag, but it cannot get any items forever. * * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag * if it doesn't set any tags within the specified range. * * Running: * This test should run to completion immediately. The above bug would cause it * to hang indefinitely. * * Upstream commit: * Not yet */#include <linux/kernel.h>#include <linux/gfp.h>#include <linux/slab.h>#include <linux/radix-tree.h>#include <stdlib.h>#include <stdio.h> #include "regression.h"#include "test.h" #define PAGECACHE_TAG_DIRTY     XA_MARK_0#define PAGECACHE_TAG_WRITEBACK XA_MARK_1#define PAGECACHE_TAG_TOWRITE   XA_MARK_2 static RADIX_TREE(mt_tree, GFP_KERNEL);unsigned long page_count = 0; struct page {	unsigned long index;}; static struct page *page_alloc(void){	struct page *p;	p = malloc(sizeof(struct page));	p->index = page_count++; 	return p;} void regression2_test(void){	int i;	struct page *p;	int max_slots = RADIX_TREE_MAP_SIZE;	unsigned long int start, end;	struct page *pages[1]; 	printv(1, "running regression test 2 (should take milliseconds)\n");	/* 0. */	for (i = 0; i <= max_slots - 1; i++) {		p = page_alloc();		radix_tree_insert(&mt_tree, i, p);	}	radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); 	/* 1. */	start = 0;	end = max_slots - 2;	tag_tagged_items(&mt_tree, start, end, 1,				PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE); 	/* 2. */	p = page_alloc();	radix_tree_insert(&mt_tree, max_slots, p); 	/* 3. */	radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); 	/* 4. */	for (i = max_slots - 1; i >= 0; i--)		free(radix_tree_delete(&mt_tree, i)); 	/* 5. */	// NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot	//       can return.	start = 1;	end = max_slots - 2;	radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,		PAGECACHE_TAG_TOWRITE); 	/* We remove all the remained nodes */	free(radix_tree_delete(&mt_tree, max_slots)); 	BUG_ON(!radix_tree_empty(&mt_tree)); 	printv(1, "regression test 2, done\n");}