1 /* 2 * Resizable, Scalable, Concurrent Hash Table 3 * 4 * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch> 5 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net> 6 * 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License version 2 as 9 * published by the Free Software Foundation. 10 */ 11 12 /************************************************************************** 13 * Self Test 14 **************************************************************************/ 15 16 #include <linux/init.h> 17 #include <linux/jhash.h> 18 #include <linux/kernel.h> 19 #include <linux/module.h> 20 #include <linux/rcupdate.h> 21 #include <linux/rhashtable.h> 22 #include <linux/slab.h> 23 #include <linux/sched.h> 24 25 #define MAX_ENTRIES 1000000 26 #define TEST_INSERT_FAIL INT_MAX 27 28 static int entries = 50000; 29 module_param(entries, int, 0); 30 MODULE_PARM_DESC(entries, "Number of entries to add (default: 50000)"); 31 32 static int runs = 4; 33 module_param(runs, int, 0); 34 MODULE_PARM_DESC(runs, "Number of test runs per variant (default: 4)"); 35 36 static int max_size = 65536; 37 module_param(max_size, int, 0); 38 MODULE_PARM_DESC(runs, "Maximum table size (default: 65536)"); 39 40 static bool shrinking = false; 41 module_param(shrinking, bool, 0); 42 MODULE_PARM_DESC(shrinking, "Enable automatic shrinking (default: off)"); 43 44 static int size = 8; 45 module_param(size, int, 0); 46 MODULE_PARM_DESC(size, "Initial size hint of table (default: 8)"); 47 48 struct test_obj { 49 int value; 50 struct rhash_head node; 51 }; 52 53 static struct test_obj array[MAX_ENTRIES]; 54 55 static struct rhashtable_params test_rht_params = { 56 .head_offset = offsetof(struct test_obj, node), 57 .key_offset = offsetof(struct test_obj, value), 58 .key_len = sizeof(int), 59 .hashfn = jhash, 60 .nulls_base = (3U << RHT_BASE_SHIFT), 61 }; 62 63 static int __init test_rht_lookup(struct rhashtable *ht) 64 { 65 unsigned int i; 66 67 for (i = 0; i < entries * 2; i++) { 68 struct test_obj *obj; 69 bool expected = !(i % 2); 70 u32 key = i; 71 72 if (array[i / 2].value == TEST_INSERT_FAIL) 73 expected = false; 74 75 obj = rhashtable_lookup_fast(ht, &key, test_rht_params); 76 77 if (expected && !obj) { 78 pr_warn("Test failed: Could not find key %u\n", key); 79 return -ENOENT; 80 } else if (!expected && obj) { 81 pr_warn("Test failed: Unexpected entry found for key %u\n", 82 key); 83 return -EEXIST; 84 } else if (expected && obj) { 85 if (obj->value != i) { 86 pr_warn("Test failed: Lookup value mismatch %u!=%u\n", 87 obj->value, i); 88 return -EINVAL; 89 } 90 } 91 92 cond_resched_rcu(); 93 } 94 95 return 0; 96 } 97 98 static void test_bucket_stats(struct rhashtable *ht) 99 { 100 unsigned int err, total = 0, chain_len = 0; 101 struct rhashtable_iter hti; 102 struct rhash_head *pos; 103 104 err = rhashtable_walk_init(ht, &hti); 105 if (err) { 106 pr_warn("Test failed: allocation error"); 107 return; 108 } 109 110 err = rhashtable_walk_start(&hti); 111 if (err && err != -EAGAIN) { 112 pr_warn("Test failed: iterator failed: %d\n", err); 113 return; 114 } 115 116 while ((pos = rhashtable_walk_next(&hti))) { 117 if (PTR_ERR(pos) == -EAGAIN) { 118 pr_info("Info: encountered resize\n"); 119 chain_len++; 120 continue; 121 } else if (IS_ERR(pos)) { 122 pr_warn("Test failed: rhashtable_walk_next() error: %ld\n", 123 PTR_ERR(pos)); 124 break; 125 } 126 127 total++; 128 } 129 130 rhashtable_walk_stop(&hti); 131 rhashtable_walk_exit(&hti); 132 133 pr_info(" Traversal complete: counted=%u, nelems=%u, entries=%d, table-jumps=%u\n", 134 total, atomic_read(&ht->nelems), entries, chain_len); 135 136 if (total != atomic_read(&ht->nelems) || total != entries) 137 pr_warn("Test failed: Total count mismatch ^^^"); 138 } 139 140 static s64 __init test_rhashtable(struct rhashtable *ht) 141 { 142 struct test_obj *obj; 143 int err; 144 unsigned int i, insert_fails = 0; 145 s64 start, end; 146 147 /* 148 * Insertion Test: 149 * Insert entries into table with all keys even numbers 150 */ 151 pr_info(" Adding %d keys\n", entries); 152 start = ktime_get_ns(); 153 for (i = 0; i < entries; i++) { 154 struct test_obj *obj = &array[i]; 155 156 obj->value = i * 2; 157 158 err = rhashtable_insert_fast(ht, &obj->node, test_rht_params); 159 if (err == -ENOMEM || err == -EBUSY) { 160 /* Mark failed inserts but continue */ 161 obj->value = TEST_INSERT_FAIL; 162 insert_fails++; 163 } else if (err) { 164 return err; 165 } 166 167 cond_resched(); 168 } 169 170 if (insert_fails) 171 pr_info(" %u insertions failed due to memory pressure\n", 172 insert_fails); 173 174 test_bucket_stats(ht); 175 rcu_read_lock(); 176 test_rht_lookup(ht); 177 rcu_read_unlock(); 178 179 test_bucket_stats(ht); 180 181 pr_info(" Deleting %d keys\n", entries); 182 for (i = 0; i < entries; i++) { 183 u32 key = i * 2; 184 185 if (array[i].value != TEST_INSERT_FAIL) { 186 obj = rhashtable_lookup_fast(ht, &key, test_rht_params); 187 BUG_ON(!obj); 188 189 rhashtable_remove_fast(ht, &obj->node, test_rht_params); 190 } 191 192 cond_resched(); 193 } 194 195 end = ktime_get_ns(); 196 pr_info(" Duration of test: %lld ns\n", end - start); 197 198 return end - start; 199 } 200 201 static struct rhashtable ht; 202 203 static int __init test_rht_init(void) 204 { 205 int i, err; 206 u64 total_time = 0; 207 208 entries = min(entries, MAX_ENTRIES); 209 210 test_rht_params.automatic_shrinking = shrinking; 211 test_rht_params.max_size = max_size; 212 test_rht_params.nelem_hint = size; 213 214 pr_info("Running rhashtable test nelem=%d, max_size=%d, shrinking=%d\n", 215 size, max_size, shrinking); 216 217 for (i = 0; i < runs; i++) { 218 s64 time; 219 220 pr_info("Test %02d:\n", i); 221 memset(&array, 0, sizeof(array)); 222 err = rhashtable_init(&ht, &test_rht_params); 223 if (err < 0) { 224 pr_warn("Test failed: Unable to initialize hashtable: %d\n", 225 err); 226 continue; 227 } 228 229 time = test_rhashtable(&ht); 230 rhashtable_destroy(&ht); 231 if (time < 0) { 232 pr_warn("Test failed: return code %lld\n", time); 233 return -EINVAL; 234 } 235 236 total_time += time; 237 } 238 239 do_div(total_time, runs); 240 pr_info("Average test time: %llu\n", total_time); 241 242 return 0; 243 } 244 245 static void __exit test_rht_exit(void) 246 { 247 } 248 249 module_init(test_rht_init); 250 module_exit(test_rht_exit); 251 252 MODULE_LICENSE("GPL v2"); 253