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