124 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Regression24 * Description:5 * Toshiyuki Okajima describes the following radix-tree bug:6 *7 * In the following case, we can get a hangup on8 * radix_radix_tree_gang_lookup_tag_slot.9 *10 * 0. The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of11 * a certain item has PAGECACHE_TAG_DIRTY.12 * 1. radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY,13 * PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag14 * for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with15 * PAGECACHE_TAG_DIRTY within the range from start to end. As the result,16 * There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has17 * PAGECACHE_TAG_TOWRITE.18 * 2. An item is added into the radix tree and then the level of it is19 * extended into 2 from 1. At that time, the new radix tree node succeeds20 * the tag status of the root tag. Therefore the tag of the new radix tree21 * node has PAGECACHE_TAG_TOWRITE but there is not slot with22 * PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node.23 * 3. The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY.24 * 4. All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are25 * released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the26 * radix tree.) As the result, the slot of the radix tree node is NULL but27 * the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE.28 * 5. radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls29 * __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't30 * change the index that is the input and output parameter. Because the 1st31 * slot of the radix tree node is NULL, but the tag which corresponds to32 * the slot has PAGECACHE_TAG_TOWRITE.33 * Therefore radix_tree_gang_lookup_tag_slot tries to get some items by34 * calling __lookup_tag, but it cannot get any items forever.35 *36 * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag37 * if it doesn't set any tags within the specified range.38 *39 * Running:40 * This test should run to completion immediately. The above bug would cause it41 * to hang indefinitely.42 *43 * Upstream commit:44 * Not yet45 */46#include <linux/kernel.h>47#include <linux/gfp.h>48#include <linux/slab.h>49#include <linux/radix-tree.h>50#include <stdlib.h>51#include <stdio.h>52 53#include "regression.h"54#include "test.h"55 56#define PAGECACHE_TAG_DIRTY XA_MARK_057#define PAGECACHE_TAG_WRITEBACK XA_MARK_158#define PAGECACHE_TAG_TOWRITE XA_MARK_259 60static RADIX_TREE(mt_tree, GFP_KERNEL);61unsigned long page_count = 0;62 63struct page {64 unsigned long index;65};66 67static struct page *page_alloc(void)68{69 struct page *p;70 p = malloc(sizeof(struct page));71 p->index = page_count++;72 73 return p;74}75 76void regression2_test(void)77{78 int i;79 struct page *p;80 int max_slots = RADIX_TREE_MAP_SIZE;81 unsigned long int start, end;82 struct page *pages[1];83 84 printv(1, "running regression test 2 (should take milliseconds)\n");85 /* 0. */86 for (i = 0; i <= max_slots - 1; i++) {87 p = page_alloc();88 radix_tree_insert(&mt_tree, i, p);89 }90 radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);91 92 /* 1. */93 start = 0;94 end = max_slots - 2;95 tag_tagged_items(&mt_tree, start, end, 1,96 PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);97 98 /* 2. */99 p = page_alloc();100 radix_tree_insert(&mt_tree, max_slots, p);101 102 /* 3. */103 radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);104 105 /* 4. */106 for (i = max_slots - 1; i >= 0; i--)107 free(radix_tree_delete(&mt_tree, i));108 109 /* 5. */110 // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot111 // can return.112 start = 1;113 end = max_slots - 2;114 radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,115 PAGECACHE_TAG_TOWRITE);116 117 /* We remove all the remained nodes */118 free(radix_tree_delete(&mt_tree, max_slots));119 120 BUG_ON(!radix_tree_empty(&mt_tree));121 122 printv(1, "regression test 2, done\n");123}124