1 /* 2 * Copyright 2017 Advanced Micro Devices, Inc. 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included in 12 * all copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17 * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR 18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 20 * OTHER DEALINGS IN THE SOFTWARE. 21 * 22 */ 23 24 #include <linux/types.h> 25 #include <linux/hash.h> 26 #include <linux/bug.h> 27 #include <linux/slab.h> 28 #include <linux/module.h> 29 #include <linux/sched/clock.h> 30 #include <asm/div64.h> 31 #include <linux/chash.h> 32 33 /** 34 * chash_table_alloc - Allocate closed hash table 35 * @table: Pointer to the table structure 36 * @bits: Table size will be 2^bits entries 37 * @key_size: Size of hash keys in bytes, 4 or 8 38 * @value_size: Size of data values in bytes, can be 0 39 */ 40 int chash_table_alloc(struct chash_table *table, u8 bits, u8 key_size, 41 unsigned int value_size, gfp_t gfp_mask) 42 { 43 if (bits > 31) 44 return -EINVAL; 45 46 if (key_size != 4 && key_size != 8) 47 return -EINVAL; 48 49 table->data = kcalloc(__CHASH_DATA_SIZE(bits, key_size, value_size), 50 sizeof(long), gfp_mask); 51 if (!table->data) 52 return -ENOMEM; 53 54 __CHASH_TABLE_INIT(table->table, table->data, 55 bits, key_size, value_size); 56 57 return 0; 58 } 59 EXPORT_SYMBOL(chash_table_alloc); 60 61 /** 62 * chash_table_free - Free closed hash table 63 * @table: Pointer to the table structure 64 */ 65 void chash_table_free(struct chash_table *table) 66 { 67 kfree(table->data); 68 } 69 EXPORT_SYMBOL(chash_table_free); 70 71 #ifdef CONFIG_CHASH_STATS 72 73 #define DIV_FRAC(nom, denom, quot, frac, frac_digits) do { \ 74 u64 __nom = (nom); \ 75 u64 __denom = (denom); \ 76 u64 __quot, __frac; \ 77 u32 __rem; \ 78 \ 79 while (__denom >> 32) { \ 80 __nom >>= 1; \ 81 __denom >>= 1; \ 82 } \ 83 __quot = __nom; \ 84 __rem = do_div(__quot, __denom); \ 85 __frac = __rem * (frac_digits) + (__denom >> 1); \ 86 do_div(__frac, __denom); \ 87 (quot) = __quot; \ 88 (frac) = __frac; \ 89 } while (0) 90 91 void __chash_table_dump_stats(struct __chash_table *table) 92 { 93 struct chash_iter iter = CHASH_ITER_INIT(table, 0); 94 u32 filled = 0, empty = 0, tombstones = 0; 95 u64 quot1, quot2; 96 u32 frac1, frac2; 97 98 do { 99 if (chash_iter_is_valid(iter)) 100 filled++; 101 else if (chash_iter_is_empty(iter)) 102 empty++; 103 else 104 tombstones++; 105 CHASH_ITER_INC(iter); 106 } while (iter.slot); 107 108 pr_debug("chash: key size %u, value size %u\n", 109 table->key_size, table->value_size); 110 pr_debug(" Slots total/filled/empty/tombstones: %u / %u / %u / %u\n", 111 1 << table->bits, filled, empty, tombstones); 112 if (table->hits > 0) { 113 DIV_FRAC(table->hits_steps, table->hits, quot1, frac1, 1000); 114 DIV_FRAC(table->hits * 1000, table->hits_time_ns, 115 quot2, frac2, 1000); 116 } else { 117 quot1 = quot2 = 0; 118 frac1 = frac2 = 0; 119 } 120 pr_debug(" Hits (avg.cost, rate): %llu (%llu.%03u, %llu.%03u M/s)\n", 121 table->hits, quot1, frac1, quot2, frac2); 122 if (table->miss > 0) { 123 DIV_FRAC(table->miss_steps, table->miss, quot1, frac1, 1000); 124 DIV_FRAC(table->miss * 1000, table->miss_time_ns, 125 quot2, frac2, 1000); 126 } else { 127 quot1 = quot2 = 0; 128 frac1 = frac2 = 0; 129 } 130 pr_debug(" Misses (avg.cost, rate): %llu (%llu.%03u, %llu.%03u M/s)\n", 131 table->miss, quot1, frac1, quot2, frac2); 132 if (table->hits + table->miss > 0) { 133 DIV_FRAC(table->hits_steps + table->miss_steps, 134 table->hits + table->miss, quot1, frac1, 1000); 135 DIV_FRAC((table->hits + table->miss) * 1000, 136 (table->hits_time_ns + table->miss_time_ns), 137 quot2, frac2, 1000); 138 } else { 139 quot1 = quot2 = 0; 140 frac1 = frac2 = 0; 141 } 142 pr_debug(" Total (avg.cost, rate): %llu (%llu.%03u, %llu.%03u M/s)\n", 143 table->hits + table->miss, quot1, frac1, quot2, frac2); 144 if (table->relocs > 0) { 145 DIV_FRAC(table->hits + table->miss, table->relocs, 146 quot1, frac1, 1000); 147 DIV_FRAC(table->reloc_dist, table->relocs, quot2, frac2, 1000); 148 pr_debug(" Relocations (freq, avg.dist): %llu (1:%llu.%03u, %llu.%03u)\n", 149 table->relocs, quot1, frac1, quot2, frac2); 150 } else { 151 pr_debug(" No relocations\n"); 152 } 153 } 154 EXPORT_SYMBOL(__chash_table_dump_stats); 155 156 #undef DIV_FRAC 157 #endif 158 159 #define CHASH_INC(table, a) ((a) = ((a) + 1) & (table)->size_mask) 160 #define CHASH_ADD(table, a, b) (((a) + (b)) & (table)->size_mask) 161 #define CHASH_SUB(table, a, b) (((a) - (b)) & (table)->size_mask) 162 #define CHASH_IN_RANGE(table, slot, first, last) \ 163 (CHASH_SUB(table, slot, first) <= CHASH_SUB(table, last, first)) 164 165 /*#define CHASH_DEBUG Uncomment this to enable verbose debug output*/ 166 #ifdef CHASH_DEBUG 167 static void chash_table_dump(struct __chash_table *table) 168 { 169 struct chash_iter iter = CHASH_ITER_INIT(table, 0); 170 171 do { 172 if ((iter.slot & 3) == 0) 173 pr_debug("%04x: ", iter.slot); 174 175 if (chash_iter_is_valid(iter)) 176 pr_debug("[%016llx] ", chash_iter_key(iter)); 177 else if (chash_iter_is_empty(iter)) 178 pr_debug("[ <empty> ] "); 179 else 180 pr_debug("[ <tombstone> ] "); 181 182 if ((iter.slot & 3) == 3) 183 pr_debug("\n"); 184 185 CHASH_ITER_INC(iter); 186 } while (iter.slot); 187 188 if ((iter.slot & 3) != 0) 189 pr_debug("\n"); 190 } 191 192 static int chash_table_check(struct __chash_table *table) 193 { 194 u32 hash; 195 struct chash_iter iter = CHASH_ITER_INIT(table, 0); 196 struct chash_iter cur = CHASH_ITER_INIT(table, 0); 197 198 do { 199 if (!chash_iter_is_valid(iter)) { 200 CHASH_ITER_INC(iter); 201 continue; 202 } 203 204 hash = chash_iter_hash(iter); 205 CHASH_ITER_SET(cur, hash); 206 while (cur.slot != iter.slot) { 207 if (chash_iter_is_empty(cur)) { 208 pr_err("Path to element at %x with hash %x broken at slot %x\n", 209 iter.slot, hash, cur.slot); 210 chash_table_dump(table); 211 return -EINVAL; 212 } 213 CHASH_ITER_INC(cur); 214 } 215 216 CHASH_ITER_INC(iter); 217 } while (iter.slot); 218 219 return 0; 220 } 221 #endif 222 223 static void chash_iter_relocate(struct chash_iter dst, struct chash_iter src) 224 { 225 BUG_ON(src.table == dst.table && src.slot == dst.slot); 226 BUG_ON(src.table->key_size != dst.table->key_size); 227 BUG_ON(src.table->value_size != dst.table->value_size); 228 229 if (dst.table->key_size == 4) 230 dst.table->keys32[dst.slot] = src.table->keys32[src.slot]; 231 else 232 dst.table->keys64[dst.slot] = src.table->keys64[src.slot]; 233 234 if (dst.table->value_size) 235 memcpy(chash_iter_value(dst), chash_iter_value(src), 236 dst.table->value_size); 237 238 chash_iter_set_valid(dst); 239 chash_iter_set_invalid(src); 240 241 #ifdef CONFIG_CHASH_STATS 242 if (src.table == dst.table) { 243 dst.table->relocs++; 244 dst.table->reloc_dist += 245 CHASH_SUB(dst.table, src.slot, dst.slot); 246 } 247 #endif 248 } 249 250 /** 251 * __chash_table_find - Helper for looking up a hash table entry 252 * @iter: Pointer to hash table iterator 253 * @key: Key of the entry to find 254 * @for_removal: set to true if the element will be removed soon 255 * 256 * Searches for an entry in the hash table with a given key. iter must 257 * be initialized by the caller to point to the home position of the 258 * hypothetical entry, i.e. it must be initialized with the hash table 259 * and the key's hash as the initial slot for the search. 260 * 261 * This function also does some local clean-up to speed up future 262 * look-ups by relocating entries to better slots and removing 263 * tombstones that are no longer needed. 264 * 265 * If @for_removal is true, the function avoids relocating the entry 266 * that is being returned. 267 * 268 * Returns 0 if the search is successful. In this case iter is updated 269 * to point to the found entry. Otherwise %-EINVAL is returned and the 270 * iter is updated to point to the first available slot for the given 271 * key. If the table is full, the slot is set to -1. 272 */ 273 static int chash_table_find(struct chash_iter *iter, u64 key, 274 bool for_removal) 275 { 276 #ifdef CONFIG_CHASH_STATS 277 u64 ts1 = local_clock(); 278 #endif 279 u32 hash = iter->slot; 280 struct chash_iter first_redundant = CHASH_ITER_INIT(iter->table, -1); 281 int first_avail = (for_removal ? -2 : -1); 282 283 while (!chash_iter_is_valid(*iter) || chash_iter_key(*iter) != key) { 284 if (chash_iter_is_empty(*iter)) { 285 /* Found an empty slot, which ends the 286 * search. Clean up any preceding tombstones 287 * that are no longer needed because they lead 288 * to no-where 289 */ 290 if ((int)first_redundant.slot < 0) 291 goto not_found; 292 while (first_redundant.slot != iter->slot) { 293 if (!chash_iter_is_valid(first_redundant)) 294 chash_iter_set_empty(first_redundant); 295 CHASH_ITER_INC(first_redundant); 296 } 297 #ifdef CHASH_DEBUG 298 chash_table_check(iter->table); 299 #endif 300 goto not_found; 301 } else if (!chash_iter_is_valid(*iter)) { 302 /* Found a tombstone. Remember it as candidate 303 * for relocating the entry we're looking for 304 * or for adding a new entry with the given key 305 */ 306 if (first_avail == -1) 307 first_avail = iter->slot; 308 /* Or mark it as the start of a series of 309 * potentially redundant tombstones 310 */ 311 else if (first_redundant.slot == -1) 312 CHASH_ITER_SET(first_redundant, iter->slot); 313 } else if (first_redundant.slot >= 0) { 314 /* Found a valid, occupied slot with a 315 * preceding series of tombstones. Relocate it 316 * to a better position that no longer depends 317 * on those tombstones 318 */ 319 u32 cur_hash = chash_iter_hash(*iter); 320 321 if (!CHASH_IN_RANGE(iter->table, cur_hash, 322 first_redundant.slot + 1, 323 iter->slot)) { 324 /* This entry has a hash at or before 325 * the first tombstone we found. We 326 * can relocate it to that tombstone 327 * and advance to the next tombstone 328 */ 329 chash_iter_relocate(first_redundant, *iter); 330 do { 331 CHASH_ITER_INC(first_redundant); 332 } while (chash_iter_is_valid(first_redundant)); 333 } else if (cur_hash != iter->slot) { 334 /* Relocate entry to its home position 335 * or as close as possible so it no 336 * longer depends on any preceding 337 * tombstones 338 */ 339 struct chash_iter new_iter = 340 CHASH_ITER_INIT(iter->table, cur_hash); 341 342 while (new_iter.slot != iter->slot && 343 chash_iter_is_valid(new_iter)) 344 CHASH_ITER_INC(new_iter); 345 346 if (new_iter.slot != iter->slot) 347 chash_iter_relocate(new_iter, *iter); 348 } 349 } 350 351 CHASH_ITER_INC(*iter); 352 if (iter->slot == hash) { 353 iter->slot = -1; 354 goto not_found; 355 } 356 } 357 358 #ifdef CONFIG_CHASH_STATS 359 iter->table->hits++; 360 iter->table->hits_steps += CHASH_SUB(iter->table, iter->slot, hash) + 1; 361 #endif 362 363 if (first_avail >= 0) { 364 CHASH_ITER_SET(first_redundant, first_avail); 365 chash_iter_relocate(first_redundant, *iter); 366 iter->slot = first_redundant.slot; 367 iter->mask = first_redundant.mask; 368 } 369 370 #ifdef CONFIG_CHASH_STATS 371 iter->table->hits_time_ns += local_clock() - ts1; 372 #endif 373 374 return 0; 375 376 not_found: 377 #ifdef CONFIG_CHASH_STATS 378 iter->table->miss++; 379 iter->table->miss_steps += (iter->slot < 0) ? 380 (1 << iter->table->bits) : 381 CHASH_SUB(iter->table, iter->slot, hash) + 1; 382 #endif 383 384 if (first_avail >= 0) 385 CHASH_ITER_SET(*iter, first_avail); 386 387 #ifdef CONFIG_CHASH_STATS 388 iter->table->miss_time_ns += local_clock() - ts1; 389 #endif 390 391 return -EINVAL; 392 } 393 394 int __chash_table_copy_in(struct __chash_table *table, u64 key, 395 const void *value) 396 { 397 u32 hash = (table->key_size == 4) ? 398 hash_32(key, table->bits) : hash_64(key, table->bits); 399 struct chash_iter iter = CHASH_ITER_INIT(table, hash); 400 int r = chash_table_find(&iter, key, false); 401 402 /* Found an existing entry */ 403 if (!r) { 404 if (value && table->value_size) 405 memcpy(chash_iter_value(iter), value, 406 table->value_size); 407 return 1; 408 } 409 410 /* Is there a place to add a new entry? */ 411 if (iter.slot < 0) { 412 pr_err("Hash table overflow\n"); 413 return -ENOMEM; 414 } 415 416 chash_iter_set_valid(iter); 417 418 if (table->key_size == 4) 419 table->keys32[iter.slot] = key; 420 else 421 table->keys64[iter.slot] = key; 422 if (value && table->value_size) 423 memcpy(chash_iter_value(iter), value, table->value_size); 424 425 return 0; 426 } 427 EXPORT_SYMBOL(__chash_table_copy_in); 428 429 int __chash_table_copy_out(struct __chash_table *table, u64 key, 430 void *value, bool remove) 431 { 432 u32 hash = (table->key_size == 4) ? 433 hash_32(key, table->bits) : hash_64(key, table->bits); 434 struct chash_iter iter = CHASH_ITER_INIT(table, hash); 435 int r = chash_table_find(&iter, key, remove); 436 437 if (r < 0) 438 return r; 439 440 if (value && table->value_size) 441 memcpy(value, chash_iter_value(iter), table->value_size); 442 443 if (remove) 444 chash_iter_set_invalid(iter); 445 446 return iter.slot; 447 } 448 EXPORT_SYMBOL(__chash_table_copy_out); 449 450 #ifdef CONFIG_CHASH_SELFTEST 451 /** 452 * chash_self_test - Run a self-test of the hash table implementation 453 * @bits: Table size will be 2^bits entries 454 * @key_size: Size of hash keys in bytes, 4 or 8 455 * @min_fill: Minimum fill level during the test 456 * @max_fill: Maximum fill level during the test 457 * @iterations: Number of test iterations 458 * 459 * The test adds and removes entries from a hash table, cycling the 460 * fill level between min_fill and max_fill entries. Also tests lookup 461 * and value retrieval. 462 */ 463 static int __init chash_self_test(u8 bits, u8 key_size, 464 int min_fill, int max_fill, 465 u64 iterations) 466 { 467 struct chash_table table; 468 int ret; 469 u64 add_count, rmv_count; 470 u64 value; 471 472 if (key_size == 4 && iterations > 0xffffffff) 473 return -EINVAL; 474 if (min_fill >= max_fill) 475 return -EINVAL; 476 477 ret = chash_table_alloc(&table, bits, key_size, sizeof(u64), 478 GFP_KERNEL); 479 if (ret) { 480 pr_err("chash_table_alloc failed: %d\n", ret); 481 return ret; 482 } 483 484 for (add_count = 0, rmv_count = 0; add_count < iterations; 485 add_count++) { 486 /* When we hit the max_fill level, remove entries down 487 * to min_fill 488 */ 489 if (add_count - rmv_count == max_fill) { 490 u64 find_count = rmv_count; 491 492 /* First try to find all entries that we're 493 * about to remove, confirm their value, test 494 * writing them back a second time. 495 */ 496 for (; add_count - find_count > min_fill; 497 find_count++) { 498 ret = chash_table_copy_out(&table, find_count, 499 &value); 500 if (ret < 0) { 501 pr_err("chash_table_copy_out failed: %d\n", 502 ret); 503 goto out; 504 } 505 if (value != ~find_count) { 506 pr_err("Wrong value retrieved for key 0x%llx, expected 0x%llx got 0x%llx\n", 507 find_count, ~find_count, value); 508 #ifdef CHASH_DEBUG 509 chash_table_dump(&table.table); 510 #endif 511 ret = -EFAULT; 512 goto out; 513 } 514 ret = chash_table_copy_in(&table, find_count, 515 &value); 516 if (ret != 1) { 517 pr_err("copy_in second time returned %d, expected 1\n", 518 ret); 519 ret = -EFAULT; 520 goto out; 521 } 522 } 523 /* Remove them until we hit min_fill level */ 524 for (; add_count - rmv_count > min_fill; rmv_count++) { 525 ret = chash_table_remove(&table, rmv_count, 526 NULL); 527 if (ret < 0) { 528 pr_err("chash_table_remove failed: %d\n", 529 ret); 530 goto out; 531 } 532 } 533 } 534 535 /* Add a new value */ 536 value = ~add_count; 537 ret = chash_table_copy_in(&table, add_count, &value); 538 if (ret != 0) { 539 pr_err("copy_in first time returned %d, expected 0\n", 540 ret); 541 ret = -EFAULT; 542 goto out; 543 } 544 } 545 546 chash_table_dump_stats(&table); 547 chash_table_reset_stats(&table); 548 549 out: 550 chash_table_free(&table); 551 return ret; 552 } 553 554 static unsigned int chash_test_bits = 10; 555 MODULE_PARM_DESC(test_bits, 556 "Selftest number of hash bits ([4..20], default=10)"); 557 module_param_named(test_bits, chash_test_bits, uint, 0444); 558 559 static unsigned int chash_test_keysize = 8; 560 MODULE_PARM_DESC(test_keysize, "Selftest keysize (4 or 8, default=8)"); 561 module_param_named(test_keysize, chash_test_keysize, uint, 0444); 562 563 static unsigned int chash_test_minfill; 564 MODULE_PARM_DESC(test_minfill, "Selftest minimum #entries (default=50%)"); 565 module_param_named(test_minfill, chash_test_minfill, uint, 0444); 566 567 static unsigned int chash_test_maxfill; 568 MODULE_PARM_DESC(test_maxfill, "Selftest maximum #entries (default=80%)"); 569 module_param_named(test_maxfill, chash_test_maxfill, uint, 0444); 570 571 static unsigned long chash_test_iters; 572 MODULE_PARM_DESC(test_iters, "Selftest iterations (default=1000 x #entries)"); 573 module_param_named(test_iters, chash_test_iters, ulong, 0444); 574 575 static int __init chash_init(void) 576 { 577 int ret; 578 u64 ts1_ns; 579 580 /* Skip self test on user errors */ 581 if (chash_test_bits < 4 || chash_test_bits > 20) { 582 pr_err("chash: test_bits out of range [4..20].\n"); 583 return 0; 584 } 585 if (chash_test_keysize != 4 && chash_test_keysize != 8) { 586 pr_err("chash: test_keysize invalid. Must be 4 or 8.\n"); 587 return 0; 588 } 589 590 if (!chash_test_minfill) 591 chash_test_minfill = (1 << chash_test_bits) / 2; 592 if (!chash_test_maxfill) 593 chash_test_maxfill = (1 << chash_test_bits) * 4 / 5; 594 if (!chash_test_iters) 595 chash_test_iters = (1 << chash_test_bits) * 1000; 596 597 if (chash_test_minfill >= (1 << chash_test_bits)) { 598 pr_err("chash: test_minfill too big. Must be < table size.\n"); 599 return 0; 600 } 601 if (chash_test_maxfill >= (1 << chash_test_bits)) { 602 pr_err("chash: test_maxfill too big. Must be < table size.\n"); 603 return 0; 604 } 605 if (chash_test_minfill >= chash_test_maxfill) { 606 pr_err("chash: test_minfill must be < test_maxfill.\n"); 607 return 0; 608 } 609 if (chash_test_keysize == 4 && chash_test_iters > 0xffffffff) { 610 pr_err("chash: test_iters must be < 4G for 4 byte keys.\n"); 611 return 0; 612 } 613 614 ts1_ns = local_clock(); 615 ret = chash_self_test(chash_test_bits, chash_test_keysize, 616 chash_test_minfill, chash_test_maxfill, 617 chash_test_iters); 618 if (!ret) { 619 u64 ts_delta_us = local_clock() - ts1_ns; 620 u64 iters_per_second = (u64)chash_test_iters * 1000000; 621 622 do_div(ts_delta_us, 1000); 623 do_div(iters_per_second, ts_delta_us); 624 pr_info("chash: self test took %llu us, %llu iterations/s\n", 625 ts_delta_us, iters_per_second); 626 } else { 627 pr_err("chash: self test failed: %d\n", ret); 628 } 629 630 return ret; 631 } 632 633 module_init(chash_init); 634 635 #endif /* CONFIG_CHASH_SELFTEST */ 636 637 MODULE_DESCRIPTION("Closed hash table"); 638 MODULE_LICENSE("GPL and additional rights"); 639