^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Regression2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * Description:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Toshiyuki Okajima describes the following radix-tree bug:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * In the following case, we can get a hangup on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * radix_radix_tree_gang_lookup_tag_slot.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * 0. The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * a certain item has PAGECACHE_TAG_DIRTY.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * 1. radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * PAGECACHE_TAG_DIRTY within the range from start to end. As the result,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * PAGECACHE_TAG_TOWRITE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * 2. An item is added into the radix tree and then the level of it is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * extended into 2 from 1. At that time, the new radix tree node succeeds
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * the tag status of the root tag. Therefore the tag of the new radix tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * node has PAGECACHE_TAG_TOWRITE but there is not slot with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * 3. The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * 4. All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * radix tree.) As the result, the slot of the radix tree node is NULL but
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * 5. radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) * __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * change the index that is the input and output parameter. Because the 1st
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * slot of the radix tree node is NULL, but the tag which corresponds to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * the slot has PAGECACHE_TAG_TOWRITE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * Therefore radix_tree_gang_lookup_tag_slot tries to get some items by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * calling __lookup_tag, but it cannot get any items forever.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) * if it doesn't set any tags within the specified range.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) * Running:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) * This test should run to completion immediately. The above bug would cause it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * to hang indefinitely.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) * Upstream commit:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * Not yet
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) #include <linux/gfp.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) #include <linux/radix-tree.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) #include <stdlib.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) #include <stdio.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) #include "regression.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) #include "test.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) #define PAGECACHE_TAG_DIRTY XA_MARK_0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) #define PAGECACHE_TAG_WRITEBACK XA_MARK_1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) #define PAGECACHE_TAG_TOWRITE XA_MARK_2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) static RADIX_TREE(mt_tree, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) unsigned long page_count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) struct page {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) unsigned long index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) static struct page *page_alloc(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) struct page *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) p = malloc(sizeof(struct page));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) p->index = page_count++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) return p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) void regression2_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) struct page *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) int max_slots = RADIX_TREE_MAP_SIZE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) unsigned long int start, end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) struct page *pages[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) printv(1, "running regression test 2 (should take milliseconds)\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) /* 0. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) for (i = 0; i <= max_slots - 1; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) p = page_alloc();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) radix_tree_insert(&mt_tree, i, p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) /* 1. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) start = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) end = max_slots - 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) tag_tagged_items(&mt_tree, start, end, 1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) /* 2. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) p = page_alloc();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) radix_tree_insert(&mt_tree, max_slots, p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) /* 3. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) /* 4. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) for (i = max_slots - 1; i >= 0; i--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) free(radix_tree_delete(&mt_tree, i));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) /* 5. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) // can return.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) start = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) end = max_slots - 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) PAGECACHE_TAG_TOWRITE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) /* We remove all the remained nodes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) free(radix_tree_delete(&mt_tree, max_slots));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) BUG_ON(!radix_tree_empty(&mt_tree));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) printv(1, "regression test 2, done\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags