tools/testing/radix-tree/multiorder.c

   1 /*
   2  * multiorder.c: Multi-order radix tree entry testing
   3  * Copyright (c) 2016 Intel Corporation
   4  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
   5  * Author: Matthew Wilcox <matthew.r.wilcox@intel.com>
   6  *
   7  * This program is free software; you can redistribute it and/or modify it
   8  * under the terms and conditions of the GNU General Public License,
   9  * version 2, as published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14  * more details.
  15  */
  16 #include <linux/radix-tree.h>
  17 #include <linux/slab.h>
  18 #include <linux/errno.h>
  19 #include <pthread.h>
  20
  21 #include "test.h"
  22
  23 static int item_insert_order(struct xarray *xa, unsigned long index,
  24                         unsigned order)
  25 {
  26         XA_STATE_ORDER(xas, xa, index, order);
  27         struct item *item = item_create(index, order);
  28
  29         do {
  30                 xas_lock(&xas);
  31                 xas_store(&xas, item);
  32                 xas_unlock(&xas);
  33         } while (xas_nomem(&xas, GFP_KERNEL));
  34
  35         if (!xas_error(&xas))
  36                 return 0;
  37
  38         free(item);
  39         return xas_error(&xas);
  40 }
  41
  42 void multiorder_iteration(struct xarray *xa)
  43 {
  44         XA_STATE(xas, xa, 0);
  45         struct item *item;
  46         int i, j, err;
  47
  48 #define NUM_ENTRIES 11
  49         int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
  50         int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};
  51
  52         printv(1, "Multiorder iteration test\n");
  53
  54         for (i = 0; i < NUM_ENTRIES; i++) {
  55                 err = item_insert_order(xa, index[i], order[i]);
  56                 assert(!err);
  57         }
  58
  59         for (j = 0; j < 256; j++) {
  60                 for (i = 0; i < NUM_ENTRIES; i++)
  61                         if (j <= (index[i] | ((1 << order[i]) - 1)))
  62                                 break;
  63
  64                 xas_set(&xas, j);
  65                 xas_for_each(&xas, item, ULONG_MAX) {
  66                         int height = order[i] / XA_CHUNK_SHIFT;
  67                         int shift = height * XA_CHUNK_SHIFT;
  68                         unsigned long mask = (1UL << order[i]) - 1;
  69
  70                         assert((xas.xa_index | mask) == (index[i] | mask));
  71                         assert(xas.xa_node->shift == shift);
  72                         assert(!radix_tree_is_internal_node(item));
  73                         assert((item->index | mask) == (index[i] | mask));
  74                         assert(item->order == order[i]);
  75                         i++;
  76                 }
  77         }
  78
  79         item_kill_tree(xa);
  80 }
  81
  82 void multiorder_tagged_iteration(struct xarray *xa)
  83 {
  84         XA_STATE(xas, xa, 0);
  85         struct item *item;
  86         int i, j;
  87
  88 #define MT_NUM_ENTRIES 9
  89         int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
  90         int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};
  91
  92 #define TAG_ENTRIES 7
  93         int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
  94
  95         printv(1, "Multiorder tagged iteration test\n");
  96
  97         for (i = 0; i < MT_NUM_ENTRIES; i++)
  98                 assert(!item_insert_order(xa, index[i], order[i]));
  99
 100         assert(!xa_marked(xa, XA_MARK_1));
 101
 102         for (i = 0; i < TAG_ENTRIES; i++)
 103                 xa_set_mark(xa, tag_index[i], XA_MARK_1);
 104
 105         for (j = 0; j < 256; j++) {
 106                 int k;
 107
 108                 for (i = 0; i < TAG_ENTRIES; i++) {
 109                         for (k = i; index[k] < tag_index[i]; k++)
 110                                 ;
 111                         if (j <= (index[k] | ((1 << order[k]) - 1)))
 112                                 break;
 113                 }
 114
 115                 xas_set(&xas, j);
 116                 xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_1) {
 117                         unsigned long mask;
 118                         for (k = i; index[k] < tag_index[i]; k++)
 119                                 ;
 120                         mask = (1UL << order[k]) - 1;
 121
 122                         assert((xas.xa_index | mask) == (tag_index[i] | mask));
 123                         assert(!xa_is_internal(item));
 124                         assert((item->index | mask) == (tag_index[i] | mask));
 125                         assert(item->order == order[k]);
 126                         i++;
 127                 }
 128         }
 129
 130         assert(tag_tagged_items(xa, 0, ULONG_MAX, TAG_ENTRIES, XA_MARK_1,
 131                                 XA_MARK_2) == TAG_ENTRIES);
 132
 133         for (j = 0; j < 256; j++) {
 134                 int mask, k;
 135
 136                 for (i = 0; i < TAG_ENTRIES; i++) {
 137                         for (k = i; index[k] < tag_index[i]; k++)
 138                                 ;
 139                         if (j <= (index[k] | ((1 << order[k]) - 1)))
 140                                 break;
 141                 }
 142
 143                 xas_set(&xas, j);
 144                 xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_2) {
 145                         for (k = i; index[k] < tag_index[i]; k++)
 146                                 ;
 147                         mask = (1 << order[k]) - 1;
 148
 149                         assert((xas.xa_index | mask) == (tag_index[i] | mask));
 150                         assert(!xa_is_internal(item));
 151                         assert((item->index | mask) == (tag_index[i] | mask));
 152                         assert(item->order == order[k]);
 153                         i++;
 154                 }
 155         }
 156
 157         assert(tag_tagged_items(xa, 1, ULONG_MAX, MT_NUM_ENTRIES * 2, XA_MARK_1,
 158                                 XA_MARK_0) == TAG_ENTRIES);
 159         i = 0;
 160         xas_set(&xas, 0);
 161         xas_for_each_marked(&xas, item, ULONG_MAX, XA_MARK_0) {
 162                 assert(xas.xa_index == tag_index[i]);
 163                 i++;
 164         }
 165         assert(i == TAG_ENTRIES);
 166
 167         item_kill_tree(xa);
 168 }
 169
 170 bool stop_iteration = false;
 171
 172 static void *creator_func(void *ptr)
 173 {
 174         /* 'order' is set up to ensure we have sibling entries */
 175         unsigned int order = RADIX_TREE_MAP_SHIFT - 1;
 176         struct radix_tree_root *tree = ptr;
 177         int i;
 178
 179         for (i = 0; i < 10000; i++) {
 180                 item_insert_order(tree, 0, order);
 181                 item_delete_rcu(tree, 0);
 182         }
 183
 184         stop_iteration = true;
 185         return NULL;
 186 }
 187
 188 static void *iterator_func(void *ptr)
 189 {
 190         XA_STATE(xas, ptr, 0);
 191         struct item *item;
 192
 193         while (!stop_iteration) {
 194                 rcu_read_lock();
 195                 xas_for_each(&xas, item, ULONG_MAX) {
 196                         if (xas_retry(&xas, item))
 197                                 continue;
 198
 199                         item_sanity(item, xas.xa_index);
 200                 }
 201                 rcu_read_unlock();
 202         }
 203         return NULL;
 204 }
 205
 206 static void multiorder_iteration_race(struct xarray *xa)
 207 {
 208         const int num_threads = sysconf(_SC_NPROCESSORS_ONLN);
 209         pthread_t worker_thread[num_threads];
 210         int i;
 211
 212         pthread_create(&worker_thread[0], NULL, &creator_func, xa);
 213         for (i = 1; i < num_threads; i++)
 214                 pthread_create(&worker_thread[i], NULL, &iterator_func, xa);
 215
 216         for (i = 0; i < num_threads; i++)
 217                 pthread_join(worker_thread[i], NULL);
 218
 219         item_kill_tree(xa);
 220 }
 221
 222 static DEFINE_XARRAY(array);
 223
 224 void multiorder_checks(void)
 225 {
 226         multiorder_iteration(&array);
 227         multiorder_tagged_iteration(&array);
 228         multiorder_iteration_race(&array);
 229
 230         radix_tree_cpu_dead(0);
 231 }
 232
 233 int __weak main(void)
 234 {
 235         radix_tree_init();
 236         multiorder_checks();
 237         return 0;
 238 }