288 lines · c
1// SPDX-License-Identifier: GPL-2.02#include <stdlib.h>3#include <assert.h>4#include <stdio.h>5#include <linux/types.h>6#include <linux/kernel.h>7#include <linux/bitops.h>8 9#include "test.h"10 11struct item *12item_tag_set(struct radix_tree_root *root, unsigned long index, int tag)13{14 return radix_tree_tag_set(root, index, tag);15}16 17struct item *18item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)19{20 return radix_tree_tag_clear(root, index, tag);21}22 23int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)24{25 return radix_tree_tag_get(root, index, tag);26}27 28struct item *item_create(unsigned long index, unsigned int order)29{30 struct item *ret = malloc(sizeof(*ret));31 32 ret->index = index;33 ret->order = order;34 return ret;35}36 37int item_insert(struct radix_tree_root *root, unsigned long index)38{39 struct item *item = item_create(index, 0);40 int err = radix_tree_insert(root, item->index, item);41 if (err)42 free(item);43 return err;44}45 46void item_sanity(struct item *item, unsigned long index)47{48 unsigned long mask;49 assert(!radix_tree_is_internal_node(item));50 assert(item->order < BITS_PER_LONG);51 mask = (1UL << item->order) - 1;52 assert((item->index | mask) == (index | mask));53}54 55void item_free(struct item *item, unsigned long index)56{57 item_sanity(item, index);58 free(item);59}60 61int item_delete(struct radix_tree_root *root, unsigned long index)62{63 struct item *item = radix_tree_delete(root, index);64 65 if (!item)66 return 0;67 68 item_free(item, index);69 return 1;70}71 72static void item_free_rcu(struct rcu_head *head)73{74 struct item *item = container_of(head, struct item, rcu_head);75 76 free(item);77}78 79int item_delete_rcu(struct xarray *xa, unsigned long index)80{81 struct item *item = xa_erase(xa, index);82 83 if (item) {84 item_sanity(item, index);85 call_rcu(&item->rcu_head, item_free_rcu);86 return 1;87 }88 return 0;89}90 91void item_check_present(struct radix_tree_root *root, unsigned long index)92{93 struct item *item;94 95 item = radix_tree_lookup(root, index);96 assert(item != NULL);97 item_sanity(item, index);98}99 100struct item *item_lookup(struct radix_tree_root *root, unsigned long index)101{102 return radix_tree_lookup(root, index);103}104 105void item_check_absent(struct radix_tree_root *root, unsigned long index)106{107 struct item *item;108 109 item = radix_tree_lookup(root, index);110 assert(item == NULL);111}112 113/*114 * Scan only the passed (start, start+nr] for present items115 */116void item_gang_check_present(struct radix_tree_root *root,117 unsigned long start, unsigned long nr,118 int chunk, int hop)119{120 struct item *items[chunk];121 unsigned long into;122 123 for (into = 0; into < nr; ) {124 int nfound;125 int nr_to_find = chunk;126 int i;127 128 if (nr_to_find > (nr - into))129 nr_to_find = nr - into;130 131 nfound = radix_tree_gang_lookup(root, (void **)items,132 start + into, nr_to_find);133 assert(nfound == nr_to_find);134 for (i = 0; i < nfound; i++)135 assert(items[i]->index == start + into + i);136 into += hop;137 }138}139 140/*141 * Scan the entire tree, only expecting present items (start, start+nr]142 */143void item_full_scan(struct radix_tree_root *root, unsigned long start,144 unsigned long nr, int chunk)145{146 struct item *items[chunk];147 unsigned long into = 0;148 unsigned long this_index = start;149 int nfound;150 int i;151 152// printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);153 154 while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,155 chunk))) {156// printf("At 0x%08lx, nfound=%d\n", into, nfound);157 for (i = 0; i < nfound; i++) {158 assert(items[i]->index == this_index);159 this_index++;160 }161// printf("Found 0x%08lx->0x%08lx\n",162// items[0]->index, items[nfound-1]->index);163 into = this_index;164 }165 if (chunk)166 assert(this_index == start + nr);167 nfound = radix_tree_gang_lookup(root, (void **)items,168 this_index, chunk);169 assert(nfound == 0);170}171 172/* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */173int tag_tagged_items(struct xarray *xa, unsigned long start, unsigned long end,174 unsigned batch, xa_mark_t iftag, xa_mark_t thentag)175{176 XA_STATE(xas, xa, start);177 unsigned int tagged = 0;178 struct item *item;179 180 if (batch == 0)181 batch = 1;182 183 xas_lock_irq(&xas);184 xas_for_each_marked(&xas, item, end, iftag) {185 xas_set_mark(&xas, thentag);186 if (++tagged % batch)187 continue;188 189 xas_pause(&xas);190 xas_unlock_irq(&xas);191 rcu_barrier();192 xas_lock_irq(&xas);193 }194 xas_unlock_irq(&xas);195 196 return tagged;197}198 199static int verify_node(struct radix_tree_node *slot, unsigned int tag,200 int tagged)201{202 int anyset = 0;203 int i;204 int j;205 206 slot = entry_to_node(slot);207 208 /* Verify consistency at this level */209 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {210 if (slot->tags[tag][i]) {211 anyset = 1;212 break;213 }214 }215 if (tagged != anyset) {216 printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",217 tag, slot->shift, tagged, anyset);218 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {219 printf("tag %d: ", j);220 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)221 printf("%016lx ", slot->tags[j][i]);222 printf("\n");223 }224 return 1;225 }226 assert(tagged == anyset);227 228 /* Go for next level */229 if (slot->shift > 0) {230 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)231 if (slot->slots[i])232 if (verify_node(slot->slots[i], tag,233 !!test_bit(i, slot->tags[tag]))) {234 printf("Failure at off %d\n", i);235 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {236 printf("tag %d: ", j);237 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)238 printf("%016lx ", slot->tags[j][i]);239 printf("\n");240 }241 return 1;242 }243 }244 return 0;245}246 247void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)248{249 struct radix_tree_node *node = root->xa_head;250 if (!radix_tree_is_internal_node(node))251 return;252 verify_node(node, tag, !!root_tag_get(root, tag));253}254 255void item_kill_tree(struct xarray *xa)256{257 XA_STATE(xas, xa, 0);258 void *entry;259 260 xas_for_each(&xas, entry, ULONG_MAX) {261 if (!xa_is_value(entry)) {262 item_free(entry, xas.xa_index);263 }264 xas_store(&xas, NULL);265 }266 267 assert(xa_empty(xa));268}269 270void tree_verify_min_height(struct radix_tree_root *root, int maxindex)271{272 unsigned shift;273 struct radix_tree_node *node = root->xa_head;274 if (!radix_tree_is_internal_node(node)) {275 assert(maxindex == 0);276 return;277 }278 279 node = entry_to_node(node);280 assert(maxindex <= node_maxindex(node));281 282 shift = node->shift;283 if (shift > 0)284 assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));285 else286 assert(maxindex > 0);287}288