Something went wrong. Try again.
(I'm so sorry!) Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel os linux
Something went wrong. Try again.
7.0 kB · 300 lines
C
at master
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301// SPDX-License-Identifier: GPL-2.0-only/* * multiorder.c: Multi-order radix tree entry testing * Copyright (c) 2016 Intel Corporation * Author: Ross Zwisler <ross.zwisler@linux.intel.com> * Author: Matthew Wilcox <matthew.r.wilcox@intel.com> */#include <linux/radix-tree.h>#include <linux/slab.h>#include <linux/errno.h>#include <pthread.h>
#include "test.h"
static int item_insert_order(struct xarray *xa, unsigned long index, unsigned order){ XA_STATE_ORDER(xas, xa, index, order); struct item *item = item_create(index, order);
do { xas_lock(&xas); xas_store(&xas, item); xas_unlock(&xas); } while (xas_nomem(&xas, GFP_KERNEL));
if (!xas_error(&xas)) return 0;
free(item); return xas_error(&xas);}
void multiorder_iteration(struct xarray *xa){ XA_STATE(xas, xa, 0); struct item *item; int i, j, err;
#define NUM_ENTRIES 11 int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128}; int order[NUM_ENTRIES] = {1, 1, 2, 3, 4, 1, 0, 1, 3, 0, 7};
printv(1, "Multiorder iteration test\n");
for (i = 0; i < NUM_ENTRIES; i++) { err = item_insert_order(xa, index[i], order[i]); assert(!err); }
for (j = 0; j < 256; j++) { for (i = 0; i < NUM_ENTRIES; i++) if (j <= (index[i] | ((1 << order[i]) - 1))) break;
xas_set(&xas, j); xas_for_each(&xas, item, ULONG_MAX) { int height = order[i] / XA_CHUNK_SHIFT; int shift = height * XA_CHUNK_SHIFT; unsigned long mask = (1UL << order[i]) - 1;
assert((xas.xa_index | mask) == (index[i] | mask)); assert(xas.xa_node->shift == shift); assert(!radix_tree_is_internal_node(item)); assert((item->index | mask) == (index[i] | mask)); assert(item->order == order[i]); i++; } }
item_kill_tree(xa);}
void multiorder_tagged_iteration(struct xarray *xa){ XA_STATE(xas, xa, 0); struct item *item; int i, j;
#define MT_NUM_ENTRIES 9 int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128}; int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7};
#define TAG_ENTRIES 7 int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
printv(1, "Multiorder tagged iteration test\n");
for (i = 0; i < MT_NUM_ENTRIES; i++) assert(!item_insert_order(xa, index[i], order[i]));
assert(!xa_marked(xa, XA_MARK_1));
for (i = 0; i < TAG_ENTRIES; i++) xa_set_mark(xa, tag_index[i], XA_MARK_1);
for (j = 0; j < 256; j++) { int k;
for (i = 0; i < TAG_ENTRIES; i++) { for (k = i; index[k] < tag_index[i]; k++) ; if (j <= (index[k] | ((1 << order[k]) - 1))) break; }
xas_set(&xas, j); xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_1) { unsigned long mask; for (k = i; index[k] < tag_index[i]; k++) ; mask = (1UL << order[k]) - 1;
assert((xas.xa_index | mask) == (tag_index[i] | mask)); assert(!xa_is_internal(item)); assert((item->index | mask) == (tag_index[i] | mask)); assert(item->order == order[k]); i++; } }
assert(tag_tagged_items(xa, 0, ULONG_MAX, TAG_ENTRIES, XA_MARK_1, XA_MARK_2) == TAG_ENTRIES);
for (j = 0; j < 256; j++) { int mask, k;
for (i = 0; i < TAG_ENTRIES; i++) { for (k = i; index[k] < tag_index[i]; k++) ; if (j <= (index[k] | ((1 << order[k]) - 1))) break; }
xas_set(&xas, j); xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_2) { for (k = i; index[k] < tag_index[i]; k++) ; mask = (1 << order[k]) - 1;
assert((xas.xa_index | mask) == (tag_index[i] | mask)); assert(!xa_is_internal(item)); assert((item->index | mask) == (tag_index[i] | mask)); assert(item->order == order[k]); i++; } }
assert(tag_tagged_items(xa, 1, ULONG_MAX, MT_NUM_ENTRIES * 2, XA_MARK_1, XA_MARK_0) == TAG_ENTRIES); i = 0; xas_set(&xas, 0); xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_0) { assert(xas.xa_index == tag_index[i]); i++; } assert(i == TAG_ENTRIES);
item_kill_tree(xa);}
bool stop_iteration;
static void *creator_func(void *ptr){ /* 'order' is set up to ensure we have sibling entries */ unsigned int order = RADIX_TREE_MAP_SHIFT - 1; struct radix_tree_root *tree = ptr; int i;
for (i = 0; i < 10000; i++) { item_insert_order(tree, 0, order); item_delete_rcu(tree, 0); }
stop_iteration = true; return NULL;}
static void *iterator_func(void *ptr){ XA_STATE(xas, ptr, 0); struct item *item;
while (!stop_iteration) { rcu_read_lock(); xas_for_each(&xas, item, ULONG_MAX) { if (xas_retry(&xas, item)) continue;
item_sanity(item, xas.xa_index); } rcu_read_unlock(); } return NULL;}
static void multiorder_iteration_race(struct xarray *xa){ const int num_threads = sysconf(_SC_NPROCESSORS_ONLN); pthread_t worker_thread[num_threads]; int i;
stop_iteration = false; pthread_create(&worker_thread[0], NULL, &creator_func, xa); for (i = 1; i < num_threads; i++) pthread_create(&worker_thread[i], NULL, &iterator_func, xa);
for (i = 0; i < num_threads; i++) pthread_join(worker_thread[i], NULL);
item_kill_tree(xa);}
static void *load_creator(void *ptr){ /* 'order' is set up to ensure we have sibling entries */ unsigned int order; struct radix_tree_root *tree = ptr; int i;
rcu_register_thread(); item_insert_order(tree, 3 << RADIX_TREE_MAP_SHIFT, 0); item_insert_order(tree, 2 << RADIX_TREE_MAP_SHIFT, 0); for (i = 0; i < 10000; i++) { for (order = 1; order < RADIX_TREE_MAP_SHIFT; order++) { unsigned long index = (3 << RADIX_TREE_MAP_SHIFT) - (1 << order); item_insert_order(tree, index, order); xa_set_mark(tree, index, XA_MARK_1); item_delete_rcu(tree, index); } } rcu_unregister_thread();
stop_iteration = true; return NULL;}
static void *load_worker(void *ptr){ unsigned long index = (3 << RADIX_TREE_MAP_SHIFT) - 1;
rcu_register_thread(); while (!stop_iteration) { unsigned long find_index = (2 << RADIX_TREE_MAP_SHIFT) + 1; struct item *item = xa_load(ptr, index); assert(!xa_is_internal(item)); item = xa_find(ptr, &find_index, index, XA_MARK_1); assert(!xa_is_internal(item)); } rcu_unregister_thread();
return NULL;}
static void load_race(struct xarray *xa){ const int num_threads = sysconf(_SC_NPROCESSORS_ONLN) * 4; pthread_t worker_thread[num_threads]; int i;
stop_iteration = false; pthread_create(&worker_thread[0], NULL, &load_creator, xa); for (i = 1; i < num_threads; i++) pthread_create(&worker_thread[i], NULL, &load_worker, xa);
for (i = 0; i < num_threads; i++) pthread_join(worker_thread[i], NULL);
item_kill_tree(xa);}
static DEFINE_XARRAY(array);
void multiorder_checks(void){ multiorder_iteration(&array); multiorder_tagged_iteration(&array); multiorder_iteration_race(&array); load_race(&array);
radix_tree_cpu_dead(0);}
int __weak main(int argc, char **argv){ int opt;
while ((opt = getopt(argc, argv, "ls:v")) != -1) { if (opt == 'v') test_verbose++; }
rcu_register_thread(); radix_tree_init(); multiorder_checks(); rcu_unregister_thread(); return 0;}