^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) * Regression3
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * Description:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Helper radix_tree_iter_retry resets next_index to the current index.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * In following radix_tree_next_slot current chunk size becomes zero.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * This isn't checked and it tries to dereference null pointer in slot.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * Helper radix_tree_iter_resume reset slot to NULL and next_index to index + 1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * for tagger iteraction it also must reset cached tags in iterator to abort
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * next radix_tree_next_slot and go to slow-path into radix_tree_next_chunk.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * Running:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * This test should run to completion immediately. The above bug would
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * cause it to segfault.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * Upstream commit:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * Not yet
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #include <linux/gfp.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) #include <linux/radix-tree.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #include <stdlib.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) #include <stdio.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) #include "regression.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) void regression3_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) RADIX_TREE(root, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) void *ptr0 = (void *)4ul;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) void *ptr = (void *)8ul;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) struct radix_tree_iter iter;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) void **slot;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) bool first;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) printv(1, "running regression test 3 (should take milliseconds)\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) radix_tree_insert(&root, 0, ptr0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) radix_tree_tag_set(&root, 0, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) first = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) printv(2, "tagged %ld %p\n", iter.index, *slot);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) if (first) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) radix_tree_insert(&root, 1, ptr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) radix_tree_tag_set(&root, 1, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) first = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) if (radix_tree_deref_retry(*slot)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) printv(2, "retry at %ld\n", iter.index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) slot = radix_tree_iter_retry(&iter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) radix_tree_delete(&root, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) first = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) radix_tree_for_each_slot(slot, &root, &iter, 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) printv(2, "slot %ld %p\n", iter.index, *slot);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) if (first) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) radix_tree_insert(&root, 1, ptr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) first = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) if (radix_tree_deref_retry(*slot)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) printv(2, "retry at %ld\n", iter.index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) slot = radix_tree_iter_retry(&iter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) radix_tree_for_each_slot(slot, &root, &iter, 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) printv(2, "slot %ld %p\n", iter.index, *slot);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) if (!iter.index) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) printv(2, "next at %ld\n", iter.index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) slot = radix_tree_iter_resume(slot, &iter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) radix_tree_tag_set(&root, 0, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) radix_tree_tag_set(&root, 1, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) printv(2, "tagged %ld %p\n", iter.index, *slot);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) if (!iter.index) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) printv(2, "next at %ld\n", iter.index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) slot = radix_tree_iter_resume(slot, &iter);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) radix_tree_delete(&root, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) radix_tree_delete(&root, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) printv(1, "regression test 3 passed\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags