1 /* 2 * Copyright 2012-2015 Samy Al Bahra. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 #define CK_HT_IM 28 #include <ck_ht.h> 29 30 /* 31 * This implementation borrows several techniques from Josh Dybnis's 32 * nbds library which can be found at http://code.google.com/p/nbds 33 * 34 * This release currently only includes support for 64-bit platforms. 35 * We can address 32-bit platforms in a future release. 36 */ 37 #include <ck_cc.h> 38 #include <ck_md.h> 39 #include <ck_pr.h> 40 #include <ck_stdint.h> 41 #include <ck_stdbool.h> 42 #include <ck_string.h> 43 44 #include "ck_ht_hash.h" 45 #include "ck_internal.h" 46 47 #ifndef CK_HT_BUCKET_LENGTH 48 49 #ifdef CK_HT_PP 50 #define CK_HT_BUCKET_SHIFT 2ULL 51 #else 52 #define CK_HT_BUCKET_SHIFT 1ULL 53 #endif 54 55 #define CK_HT_BUCKET_LENGTH (1U << CK_HT_BUCKET_SHIFT) 56 #define CK_HT_BUCKET_MASK (CK_HT_BUCKET_LENGTH - 1) 57 #endif 58 59 #ifndef CK_HT_PROBE_DEFAULT 60 #define CK_HT_PROBE_DEFAULT 64ULL 61 #endif 62 63 #if defined(CK_F_PR_LOAD_8) && defined(CK_F_PR_STORE_8) 64 #define CK_HT_WORD uint8_t 65 #define CK_HT_WORD_MAX UINT8_MAX 66 #define CK_HT_STORE(x, y) ck_pr_store_8(x, y) 67 #define CK_HT_LOAD(x) ck_pr_load_8(x) 68 #elif defined(CK_F_PR_LOAD_16) && defined(CK_F_PR_STORE_16) 69 #define CK_HT_WORD uint16_t 70 #define CK_HT_WORD_MAX UINT16_MAX 71 #define CK_HT_STORE(x, y) ck_pr_store_16(x, y) 72 #define CK_HT_LOAD(x) ck_pr_load_16(x) 73 #elif defined(CK_F_PR_LOAD_32) && defined(CK_F_PR_STORE_32) 74 #define CK_HT_WORD uint32_t 75 #define CK_HT_WORD_MAX UINT32_MAX 76 #define CK_HT_STORE(x, y) ck_pr_store_32(x, y) 77 #define CK_HT_LOAD(x) ck_pr_load_32(x) 78 #else 79 #error "ck_ht is not supported on your platform." 80 #endif 81 82 struct ck_ht_map { 83 unsigned int mode; 84 CK_HT_TYPE deletions; 85 CK_HT_TYPE probe_maximum; 86 CK_HT_TYPE probe_length; 87 CK_HT_TYPE probe_limit; 88 CK_HT_TYPE size; 89 CK_HT_TYPE n_entries; 90 CK_HT_TYPE mask; 91 CK_HT_TYPE capacity; 92 CK_HT_TYPE step; 93 CK_HT_WORD *probe_bound; 94 struct ck_ht_entry *entries; 95 }; 96 97 void 98 ck_ht_stat(struct ck_ht *table, 99 struct ck_ht_stat *st) 100 { 101 struct ck_ht_map *map = table->map; 102 103 st->n_entries = map->n_entries; 104 st->probe_maximum = map->probe_maximum; 105 return; 106 } 107 108 void 109 ck_ht_hash(struct ck_ht_hash *h, 110 struct ck_ht *table, 111 const void *key, 112 uint16_t key_length) 113 { 114 115 table->h(h, key, key_length, table->seed); 116 return; 117 } 118 119 void 120 ck_ht_hash_direct(struct ck_ht_hash *h, 121 struct ck_ht *table, 122 uintptr_t key) 123 { 124 125 ck_ht_hash(h, table, &key, sizeof(key)); 126 return; 127 } 128 129 static void 130 ck_ht_hash_wrapper(struct ck_ht_hash *h, 131 const void *key, 132 size_t length, 133 uint64_t seed) 134 { 135 136 h->value = (unsigned long)MurmurHash64A(key, length, seed); 137 return; 138 } 139 140 static struct ck_ht_map * 141 ck_ht_map_create(struct ck_ht *table, CK_HT_TYPE entries) 142 { 143 struct ck_ht_map *map; 144 CK_HT_TYPE size; 145 uintptr_t prefix; 146 uint32_t n_entries; 147 148 n_entries = ck_internal_power_2(entries); 149 if (n_entries < CK_HT_BUCKET_LENGTH) 150 n_entries = CK_HT_BUCKET_LENGTH; 151 152 size = sizeof(struct ck_ht_map) + 153 (sizeof(struct ck_ht_entry) * n_entries + CK_MD_CACHELINE - 1); 154 155 if (table->mode & CK_HT_WORKLOAD_DELETE) { 156 prefix = sizeof(CK_HT_WORD) * n_entries; 157 size += prefix; 158 } else { 159 prefix = 0; 160 } 161 162 map = table->m->malloc(size); 163 if (map == NULL) 164 return NULL; 165 166 map->mode = table->mode; 167 map->size = size; 168 map->probe_limit = ck_internal_max_64(n_entries >> 169 (CK_HT_BUCKET_SHIFT + 2), CK_HT_PROBE_DEFAULT); 170 171 map->deletions = 0; 172 map->probe_maximum = 0; 173 map->capacity = n_entries; 174 map->step = ck_internal_bsf_64(map->capacity); 175 map->mask = map->capacity - 1; 176 map->n_entries = 0; 177 map->entries = (struct ck_ht_entry *)(((uintptr_t)&map[1] + prefix + 178 CK_MD_CACHELINE - 1) & ~(CK_MD_CACHELINE - 1)); 179 180 if (table->mode & CK_HT_WORKLOAD_DELETE) { 181 map->probe_bound = (CK_HT_WORD *)&map[1]; 182 memset(map->probe_bound, 0, prefix); 183 } else { 184 map->probe_bound = NULL; 185 } 186 187 memset(map->entries, 0, sizeof(struct ck_ht_entry) * n_entries); 188 ck_pr_fence_store(); 189 return map; 190 } 191 192 static inline void 193 ck_ht_map_bound_set(struct ck_ht_map *m, 194 struct ck_ht_hash h, 195 CK_HT_TYPE n_probes) 196 { 197 CK_HT_TYPE offset = h.value & m->mask; 198 199 if (n_probes > m->probe_maximum) 200 CK_HT_TYPE_STORE(&m->probe_maximum, n_probes); 201 202 if (m->probe_bound != NULL && m->probe_bound[offset] < n_probes) { 203 if (n_probes >= CK_HT_WORD_MAX) 204 n_probes = CK_HT_WORD_MAX; 205 206 CK_HT_STORE(&m->probe_bound[offset], n_probes); 207 ck_pr_fence_store(); 208 } 209 210 return; 211 } 212 213 static inline CK_HT_TYPE 214 ck_ht_map_bound_get(struct ck_ht_map *m, struct ck_ht_hash h) 215 { 216 CK_HT_TYPE offset = h.value & m->mask; 217 CK_HT_TYPE r = CK_HT_WORD_MAX; 218 219 if (m->probe_bound != NULL) { 220 r = CK_HT_LOAD(&m->probe_bound[offset]); 221 if (r == CK_HT_WORD_MAX) 222 r = CK_HT_TYPE_LOAD(&m->probe_maximum); 223 } else { 224 r = CK_HT_TYPE_LOAD(&m->probe_maximum); 225 } 226 227 return r; 228 } 229 230 static void 231 ck_ht_map_destroy(struct ck_malloc *m, struct ck_ht_map *map, bool defer) 232 { 233 234 m->free(map, map->size, defer); 235 return; 236 } 237 238 static inline size_t 239 ck_ht_map_probe_next(struct ck_ht_map *map, size_t offset, ck_ht_hash_t h, size_t probes) 240 { 241 ck_ht_hash_t r; 242 size_t stride; 243 unsigned long level = (unsigned long)probes >> CK_HT_BUCKET_SHIFT; 244 245 r.value = (h.value >> map->step) >> level; 246 stride = (r.value & ~CK_HT_BUCKET_MASK) << 1 247 | (r.value & CK_HT_BUCKET_MASK); 248 249 return (offset + level + 250 (stride | CK_HT_BUCKET_LENGTH)) & map->mask; 251 } 252 253 bool 254 ck_ht_init(struct ck_ht *table, 255 unsigned int mode, 256 ck_ht_hash_cb_t *h, 257 struct ck_malloc *m, 258 CK_HT_TYPE entries, 259 uint64_t seed) 260 { 261 262 if (m == NULL || m->malloc == NULL || m->free == NULL) 263 return false; 264 265 table->m = m; 266 table->mode = mode; 267 table->seed = seed; 268 269 if (h == NULL) { 270 table->h = ck_ht_hash_wrapper; 271 } else { 272 table->h = h; 273 } 274 275 table->map = ck_ht_map_create(table, entries); 276 return table->map != NULL; 277 } 278 279 static struct ck_ht_entry * 280 ck_ht_map_probe_wr(struct ck_ht_map *map, 281 ck_ht_hash_t h, 282 ck_ht_entry_t *snapshot, 283 ck_ht_entry_t **available, 284 const void *key, 285 uint16_t key_length, 286 CK_HT_TYPE *probe_limit, 287 CK_HT_TYPE *probe_wr) 288 { 289 struct ck_ht_entry *bucket, *cursor; 290 struct ck_ht_entry *first = NULL; 291 size_t offset, i, j; 292 CK_HT_TYPE probes = 0; 293 CK_HT_TYPE limit; 294 295 if (probe_limit == NULL) { 296 limit = ck_ht_map_bound_get(map, h); 297 } else { 298 limit = CK_HT_TYPE_MAX; 299 } 300 301 offset = h.value & map->mask; 302 for (i = 0; i < map->probe_limit; i++) { 303 /* 304 * Probe on a complete cache line first. Scan forward and wrap around to 305 * the beginning of the cache line. Only when the complete cache line has 306 * been scanned do we move on to the next row. 307 */ 308 bucket = (void *)((uintptr_t)(map->entries + offset) & 309 ~(CK_MD_CACHELINE - 1)); 310 311 for (j = 0; j < CK_HT_BUCKET_LENGTH; j++) { 312 uint16_t k; 313 314 if (probes++ > limit) 315 break; 316 317 cursor = bucket + ((j + offset) & (CK_HT_BUCKET_LENGTH - 1)); 318 319 /* 320 * It is probably worth it to encapsulate probe state 321 * in order to prevent a complete reprobe sequence in 322 * the case of intermittent writers. 323 */ 324 if (cursor->key == CK_HT_KEY_TOMBSTONE) { 325 if (first == NULL) { 326 first = cursor; 327 *probe_wr = probes; 328 } 329 330 continue; 331 } 332 333 if (cursor->key == CK_HT_KEY_EMPTY) 334 goto leave; 335 336 if (cursor->key == (uintptr_t)key) 337 goto leave; 338 339 if (map->mode & CK_HT_MODE_BYTESTRING) { 340 void *pointer; 341 342 /* 343 * Check memoized portion of hash value before 344 * expensive full-length comparison. 345 */ 346 k = ck_ht_entry_key_length(cursor); 347 if (k != key_length) 348 continue; 349 350 #ifdef CK_HT_PP 351 if ((cursor->value >> CK_MD_VMA_BITS) != ((h.value >> 32) & CK_HT_KEY_MASK)) 352 continue; 353 #else 354 if (cursor->hash != h.value) 355 continue; 356 #endif 357 358 pointer = ck_ht_entry_key(cursor); 359 if (memcmp(pointer, key, key_length) == 0) 360 goto leave; 361 } 362 } 363 364 offset = ck_ht_map_probe_next(map, offset, h, probes); 365 } 366 367 cursor = NULL; 368 369 leave: 370 if (probe_limit != NULL) { 371 *probe_limit = probes; 372 } else if (first == NULL) { 373 *probe_wr = probes; 374 } 375 376 *available = first; 377 378 if (cursor != NULL) { 379 *snapshot = *cursor; 380 } 381 382 return cursor; 383 } 384 385 bool 386 ck_ht_gc(struct ck_ht *ht, unsigned long cycles, unsigned long seed) 387 { 388 CK_HT_WORD *bounds = NULL; 389 struct ck_ht_map *map = ht->map; 390 CK_HT_TYPE maximum, i; 391 CK_HT_TYPE size = 0; 392 393 if (map->n_entries == 0) { 394 CK_HT_TYPE_STORE(&map->probe_maximum, 0); 395 if (map->probe_bound != NULL) 396 memset(map->probe_bound, 0, sizeof(CK_HT_WORD) * map->capacity); 397 398 return true; 399 } 400 401 if (cycles == 0) { 402 maximum = 0; 403 404 if (map->probe_bound != NULL) { 405 size = sizeof(CK_HT_WORD) * map->capacity; 406 bounds = ht->m->malloc(size); 407 if (bounds == NULL) 408 return false; 409 410 memset(bounds, 0, size); 411 } 412 } else { 413 maximum = map->probe_maximum; 414 } 415 416 for (i = 0; i < map->capacity; i++) { 417 struct ck_ht_entry *entry, *priority, snapshot; 418 struct ck_ht_hash h; 419 CK_HT_TYPE probes_wr; 420 CK_HT_TYPE offset; 421 422 entry = &map->entries[(i + seed) & map->mask]; 423 if (entry->key == CK_HT_KEY_EMPTY || 424 entry->key == CK_HT_KEY_TOMBSTONE) { 425 continue; 426 } 427 428 if (ht->mode & CK_HT_MODE_BYTESTRING) { 429 #ifndef CK_HT_PP 430 h.value = entry->hash; 431 #else 432 ht->h(&h, ck_ht_entry_key(entry), ck_ht_entry_key_length(entry), 433 ht->seed); 434 #endif 435 entry = ck_ht_map_probe_wr(map, h, &snapshot, &priority, 436 ck_ht_entry_key(entry), 437 ck_ht_entry_key_length(entry), 438 NULL, &probes_wr); 439 } else { 440 #ifndef CK_HT_PP 441 h.value = entry->hash; 442 #else 443 ht->h(&h, &entry->key, sizeof(entry->key), ht->seed); 444 #endif 445 entry = ck_ht_map_probe_wr(map, h, &snapshot, &priority, 446 (void *)entry->key, 447 sizeof(entry->key), 448 NULL, &probes_wr); 449 } 450 451 offset = h.value & map->mask; 452 453 if (priority != NULL) { 454 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); 455 ck_pr_fence_store(); 456 #ifndef CK_HT_PP 457 CK_HT_TYPE_STORE(&priority->key_length, entry->key_length); 458 CK_HT_TYPE_STORE(&priority->hash, entry->hash); 459 #endif 460 ck_pr_store_ptr_unsafe(&priority->value, (void *)entry->value); 461 ck_pr_fence_store(); 462 ck_pr_store_ptr_unsafe(&priority->key, (void *)entry->key); 463 ck_pr_fence_store(); 464 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); 465 ck_pr_fence_store(); 466 ck_pr_store_ptr_unsafe(&entry->key, (void *)CK_HT_KEY_TOMBSTONE); 467 ck_pr_fence_store(); 468 } 469 470 if (cycles == 0) { 471 if (probes_wr > maximum) 472 maximum = probes_wr; 473 474 if (probes_wr >= CK_HT_WORD_MAX) 475 probes_wr = CK_HT_WORD_MAX; 476 477 if (bounds != NULL && probes_wr > bounds[offset]) 478 bounds[offset] = probes_wr; 479 } else if (--cycles == 0) 480 break; 481 } 482 483 if (maximum != map->probe_maximum) 484 CK_HT_TYPE_STORE(&map->probe_maximum, maximum); 485 486 if (bounds != NULL) { 487 for (i = 0; i < map->capacity; i++) 488 CK_HT_STORE(&map->probe_bound[i], bounds[i]); 489 490 ht->m->free(bounds, size, false); 491 } 492 493 return true; 494 } 495 496 static struct ck_ht_entry * 497 ck_ht_map_probe_rd(struct ck_ht_map *map, 498 ck_ht_hash_t h, 499 ck_ht_entry_t *snapshot, 500 const void *key, 501 uint16_t key_length) 502 { 503 struct ck_ht_entry *bucket, *cursor; 504 size_t offset, i, j; 505 CK_HT_TYPE probes = 0; 506 CK_HT_TYPE probe_maximum; 507 508 #ifndef CK_HT_PP 509 CK_HT_TYPE d = 0; 510 CK_HT_TYPE d_prime = 0; 511 retry: 512 #endif 513 514 probe_maximum = ck_ht_map_bound_get(map, h); 515 offset = h.value & map->mask; 516 517 for (i = 0; i < map->probe_limit; i++) { 518 /* 519 * Probe on a complete cache line first. Scan forward and wrap around to 520 * the beginning of the cache line. Only when the complete cache line has 521 * been scanned do we move on to the next row. 522 */ 523 bucket = (void *)((uintptr_t)(map->entries + offset) & 524 ~(CK_MD_CACHELINE - 1)); 525 526 for (j = 0; j < CK_HT_BUCKET_LENGTH; j++) { 527 uint16_t k; 528 529 if (probes++ > probe_maximum) 530 return NULL; 531 532 cursor = bucket + ((j + offset) & (CK_HT_BUCKET_LENGTH - 1)); 533 534 #ifdef CK_HT_PP 535 snapshot->key = (uintptr_t)ck_pr_load_ptr(&cursor->key); 536 ck_pr_fence_load(); 537 snapshot->value = (uintptr_t)ck_pr_load_ptr(&cursor->value); 538 #else 539 d = CK_HT_TYPE_LOAD(&map->deletions); 540 snapshot->key = (uintptr_t)ck_pr_load_ptr(&cursor->key); 541 ck_pr_fence_load(); 542 snapshot->key_length = CK_HT_TYPE_LOAD(&cursor->key_length); 543 snapshot->hash = CK_HT_TYPE_LOAD(&cursor->hash); 544 snapshot->value = (uintptr_t)ck_pr_load_ptr(&cursor->value); 545 #endif 546 547 /* 548 * It is probably worth it to encapsulate probe state 549 * in order to prevent a complete reprobe sequence in 550 * the case of intermittent writers. 551 */ 552 if (snapshot->key == CK_HT_KEY_TOMBSTONE) 553 continue; 554 555 if (snapshot->key == CK_HT_KEY_EMPTY) 556 goto leave; 557 558 if (snapshot->key == (uintptr_t)key) 559 goto leave; 560 561 if (map->mode & CK_HT_MODE_BYTESTRING) { 562 void *pointer; 563 564 /* 565 * Check memoized portion of hash value before 566 * expensive full-length comparison. 567 */ 568 k = ck_ht_entry_key_length(snapshot); 569 if (k != key_length) 570 continue; 571 #ifdef CK_HT_PP 572 if ((snapshot->value >> CK_MD_VMA_BITS) != ((h.value >> 32) & CK_HT_KEY_MASK)) 573 continue; 574 #else 575 if (snapshot->hash != h.value) 576 continue; 577 578 d_prime = CK_HT_TYPE_LOAD(&map->deletions); 579 580 /* 581 * It is possible that the slot was 582 * replaced, initiate a re-probe. 583 */ 584 if (d != d_prime) 585 goto retry; 586 #endif 587 588 pointer = ck_ht_entry_key(snapshot); 589 if (memcmp(pointer, key, key_length) == 0) 590 goto leave; 591 } 592 } 593 594 offset = ck_ht_map_probe_next(map, offset, h, probes); 595 } 596 597 return NULL; 598 599 leave: 600 return cursor; 601 } 602 603 CK_HT_TYPE 604 ck_ht_count(struct ck_ht *table) 605 { 606 struct ck_ht_map *map = ck_pr_load_ptr(&table->map); 607 608 return CK_HT_TYPE_LOAD(&map->n_entries); 609 } 610 611 bool 612 ck_ht_next(struct ck_ht *table, 613 struct ck_ht_iterator *i, 614 struct ck_ht_entry **entry) 615 { 616 struct ck_ht_map *map = table->map; 617 uintptr_t key; 618 619 if (i->offset >= map->capacity) 620 return false; 621 622 do { 623 key = map->entries[i->offset].key; 624 if (key != CK_HT_KEY_EMPTY && key != CK_HT_KEY_TOMBSTONE) 625 break; 626 } while (++i->offset < map->capacity); 627 628 if (i->offset >= map->capacity) 629 return false; 630 631 *entry = map->entries + i->offset++; 632 return true; 633 } 634 635 bool 636 ck_ht_reset_size_spmc(struct ck_ht *table, CK_HT_TYPE size) 637 { 638 struct ck_ht_map *map, *update; 639 640 map = table->map; 641 update = ck_ht_map_create(table, size); 642 if (update == NULL) 643 return false; 644 645 ck_pr_store_ptr_unsafe(&table->map, update); 646 ck_ht_map_destroy(table->m, map, true); 647 return true; 648 } 649 650 bool 651 ck_ht_reset_spmc(struct ck_ht *table) 652 { 653 struct ck_ht_map *map = table->map; 654 655 return ck_ht_reset_size_spmc(table, map->capacity); 656 } 657 658 bool 659 ck_ht_grow_spmc(struct ck_ht *table, CK_HT_TYPE capacity) 660 { 661 struct ck_ht_map *map, *update; 662 struct ck_ht_entry *bucket, *previous; 663 struct ck_ht_hash h; 664 size_t k, i, j, offset; 665 CK_HT_TYPE probes; 666 667 restart: 668 map = table->map; 669 670 if (map->capacity >= capacity) 671 return false; 672 673 update = ck_ht_map_create(table, capacity); 674 if (update == NULL) 675 return false; 676 677 for (k = 0; k < map->capacity; k++) { 678 previous = &map->entries[k]; 679 680 if (previous->key == CK_HT_KEY_EMPTY || previous->key == CK_HT_KEY_TOMBSTONE) 681 continue; 682 683 if (table->mode & CK_HT_MODE_BYTESTRING) { 684 #ifdef CK_HT_PP 685 void *key; 686 uint16_t key_length; 687 688 key = ck_ht_entry_key(previous); 689 key_length = ck_ht_entry_key_length(previous); 690 #endif 691 692 #ifndef CK_HT_PP 693 h.value = previous->hash; 694 #else 695 table->h(&h, key, key_length, table->seed); 696 #endif 697 } else { 698 #ifndef CK_HT_PP 699 h.value = previous->hash; 700 #else 701 table->h(&h, &previous->key, sizeof(previous->key), table->seed); 702 #endif 703 } 704 705 offset = h.value & update->mask; 706 probes = 0; 707 708 for (i = 0; i < update->probe_limit; i++) { 709 bucket = (void *)((uintptr_t)(update->entries + offset) & ~(CK_MD_CACHELINE - 1)); 710 711 for (j = 0; j < CK_HT_BUCKET_LENGTH; j++) { 712 struct ck_ht_entry *cursor = bucket + ((j + offset) & (CK_HT_BUCKET_LENGTH - 1)); 713 714 probes++; 715 if (CK_CC_LIKELY(cursor->key == CK_HT_KEY_EMPTY)) { 716 *cursor = *previous; 717 update->n_entries++; 718 ck_ht_map_bound_set(update, h, probes); 719 break; 720 } 721 } 722 723 if (j < CK_HT_BUCKET_LENGTH) 724 break; 725 726 offset = ck_ht_map_probe_next(update, offset, h, probes); 727 } 728 729 if (i == update->probe_limit) { 730 /* 731 * We have hit the probe limit, the map needs to be even 732 * larger. 733 */ 734 ck_ht_map_destroy(table->m, update, false); 735 capacity <<= 1; 736 goto restart; 737 } 738 } 739 740 ck_pr_fence_store(); 741 ck_pr_store_ptr_unsafe(&table->map, update); 742 ck_ht_map_destroy(table->m, map, true); 743 return true; 744 } 745 746 bool 747 ck_ht_remove_spmc(struct ck_ht *table, 748 ck_ht_hash_t h, 749 ck_ht_entry_t *entry) 750 { 751 struct ck_ht_map *map; 752 struct ck_ht_entry *candidate, snapshot; 753 754 map = table->map; 755 756 if (table->mode & CK_HT_MODE_BYTESTRING) { 757 candidate = ck_ht_map_probe_rd(map, h, &snapshot, 758 ck_ht_entry_key(entry), 759 ck_ht_entry_key_length(entry)); 760 } else { 761 candidate = ck_ht_map_probe_rd(map, h, &snapshot, 762 (void *)entry->key, 763 sizeof(entry->key)); 764 } 765 766 /* No matching entry was found. */ 767 if (candidate == NULL || snapshot.key == CK_HT_KEY_EMPTY) 768 return false; 769 770 *entry = snapshot; 771 772 ck_pr_store_ptr_unsafe(&candidate->key, (void *)CK_HT_KEY_TOMBSTONE); 773 ck_pr_fence_store(); 774 CK_HT_TYPE_STORE(&map->n_entries, map->n_entries - 1); 775 return true; 776 } 777 778 bool 779 ck_ht_get_spmc(struct ck_ht *table, 780 ck_ht_hash_t h, 781 ck_ht_entry_t *entry) 782 { 783 struct ck_ht_entry *candidate, snapshot; 784 struct ck_ht_map *map; 785 CK_HT_TYPE d, d_prime; 786 787 restart: 788 map = ck_pr_load_ptr(&table->map); 789 790 /* 791 * Platforms that cannot read key and key_length atomically must reprobe 792 * on the scan of any single entry. 793 */ 794 d = CK_HT_TYPE_LOAD(&map->deletions); 795 796 if (table->mode & CK_HT_MODE_BYTESTRING) { 797 candidate = ck_ht_map_probe_rd(map, h, &snapshot, 798 ck_ht_entry_key(entry), ck_ht_entry_key_length(entry)); 799 } else { 800 candidate = ck_ht_map_probe_rd(map, h, &snapshot, 801 (void *)entry->key, sizeof(entry->key)); 802 } 803 804 d_prime = CK_HT_TYPE_LOAD(&map->deletions); 805 if (d != d_prime) { 806 /* 807 * It is possible we have read (K, V'). Only valid states are 808 * (K, V), (K', V') and (T, V). Restart load operation in face 809 * of concurrent deletions or replacements. 810 */ 811 goto restart; 812 } 813 814 if (candidate == NULL || snapshot.key == CK_HT_KEY_EMPTY) 815 return false; 816 817 *entry = snapshot; 818 return true; 819 } 820 821 bool 822 ck_ht_set_spmc(struct ck_ht *table, 823 ck_ht_hash_t h, 824 ck_ht_entry_t *entry) 825 { 826 struct ck_ht_entry snapshot, *candidate, *priority; 827 struct ck_ht_map *map; 828 CK_HT_TYPE probes, probes_wr; 829 bool empty = false; 830 831 for (;;) { 832 map = table->map; 833 834 if (table->mode & CK_HT_MODE_BYTESTRING) { 835 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, 836 ck_ht_entry_key(entry), 837 ck_ht_entry_key_length(entry), 838 &probes, &probes_wr); 839 } else { 840 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, 841 (void *)entry->key, 842 sizeof(entry->key), 843 &probes, &probes_wr); 844 } 845 846 if (priority != NULL) { 847 probes = probes_wr; 848 break; 849 } 850 851 if (candidate != NULL) 852 break; 853 854 if (ck_ht_grow_spmc(table, map->capacity << 1) == false) 855 return false; 856 } 857 858 if (candidate == NULL) { 859 candidate = priority; 860 empty = true; 861 } 862 863 if (candidate->key != CK_HT_KEY_EMPTY && 864 priority != NULL && candidate != priority) { 865 /* 866 * Entry is moved into another position in probe sequence. 867 * We avoid a state of (K, B) (where [K, B] -> [K', B]) by 868 * guaranteeing a forced reprobe before transitioning from K to 869 * T. (K, B) implies (K, B, D') so we will reprobe successfully 870 * from this transient state. 871 */ 872 probes = probes_wr; 873 874 #ifndef CK_HT_PP 875 CK_HT_TYPE_STORE(&priority->key_length, entry->key_length); 876 CK_HT_TYPE_STORE(&priority->hash, entry->hash); 877 #endif 878 879 /* 880 * Readers must observe version counter change before they 881 * observe re-use. If they observe re-use, it is at most 882 * a tombstone. 883 */ 884 if (priority->value == CK_HT_KEY_TOMBSTONE) { 885 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); 886 ck_pr_fence_store(); 887 } 888 889 ck_pr_store_ptr_unsafe(&priority->value, (void *)entry->value); 890 ck_pr_fence_store(); 891 ck_pr_store_ptr_unsafe(&priority->key, (void *)entry->key); 892 ck_pr_fence_store(); 893 894 /* 895 * Make sure that readers who observe the tombstone would 896 * also observe counter change. 897 */ 898 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); 899 ck_pr_fence_store(); 900 901 ck_pr_store_ptr_unsafe(&candidate->key, (void *)CK_HT_KEY_TOMBSTONE); 902 ck_pr_fence_store(); 903 } else { 904 /* 905 * In this case we are inserting a new entry or replacing 906 * an existing entry. Yes, this can be combined into above branch, 907 * but isn't because you are actually looking at dying code 908 * (ck_ht is effectively deprecated and is being replaced soon). 909 */ 910 bool replace = candidate->key != CK_HT_KEY_EMPTY && 911 candidate->key != CK_HT_KEY_TOMBSTONE; 912 913 if (priority != NULL) { 914 if (priority->key == CK_HT_KEY_TOMBSTONE) { 915 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); 916 ck_pr_fence_store(); 917 } 918 919 candidate = priority; 920 probes = probes_wr; 921 } 922 923 #ifdef CK_HT_PP 924 ck_pr_store_ptr_unsafe(&candidate->value, (void *)entry->value); 925 ck_pr_fence_store(); 926 ck_pr_store_ptr_unsafe(&candidate->key, (void *)entry->key); 927 #else 928 CK_HT_TYPE_STORE(&candidate->key_length, entry->key_length); 929 CK_HT_TYPE_STORE(&candidate->hash, entry->hash); 930 ck_pr_store_ptr_unsafe(&candidate->value, (void *)entry->value); 931 ck_pr_fence_store(); 932 ck_pr_store_ptr_unsafe(&candidate->key, (void *)entry->key); 933 #endif 934 935 /* 936 * If we are insert a new entry then increment number 937 * of entries associated with map. 938 */ 939 if (replace == false) 940 CK_HT_TYPE_STORE(&map->n_entries, map->n_entries + 1); 941 } 942 943 ck_ht_map_bound_set(map, h, probes); 944 945 /* Enforce a load factor of 0.5. */ 946 if (map->n_entries * 2 > map->capacity) 947 ck_ht_grow_spmc(table, map->capacity << 1); 948 949 if (empty == true) { 950 entry->key = CK_HT_KEY_EMPTY; 951 } else { 952 *entry = snapshot; 953 } 954 955 return true; 956 } 957 958 bool 959 ck_ht_put_spmc(struct ck_ht *table, 960 ck_ht_hash_t h, 961 ck_ht_entry_t *entry) 962 { 963 struct ck_ht_entry snapshot, *candidate, *priority; 964 struct ck_ht_map *map; 965 CK_HT_TYPE probes, probes_wr; 966 967 for (;;) { 968 map = table->map; 969 970 if (table->mode & CK_HT_MODE_BYTESTRING) { 971 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, 972 ck_ht_entry_key(entry), 973 ck_ht_entry_key_length(entry), 974 &probes, &probes_wr); 975 } else { 976 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, 977 (void *)entry->key, 978 sizeof(entry->key), 979 &probes, &probes_wr); 980 } 981 982 if (candidate != NULL || priority != NULL) 983 break; 984 985 if (ck_ht_grow_spmc(table, map->capacity << 1) == false) 986 return false; 987 } 988 989 if (priority != NULL) { 990 /* Version counter is updated before re-use. */ 991 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); 992 ck_pr_fence_store(); 993 994 /* Re-use tombstone if one was found. */ 995 candidate = priority; 996 probes = probes_wr; 997 } else if (candidate->key != CK_HT_KEY_EMPTY && 998 candidate->key != CK_HT_KEY_TOMBSTONE) { 999 /* 1000 * If the snapshot key is non-empty and the value field is not 1001 * a tombstone then an identical key was found. As store does 1002 * not implement replacement, we will fail. 1003 */ 1004 return false; 1005 } 1006 1007 ck_ht_map_bound_set(map, h, probes); 1008 1009 #ifdef CK_HT_PP 1010 ck_pr_store_ptr_unsafe(&candidate->value, (void *)entry->value); 1011 ck_pr_fence_store(); 1012 ck_pr_store_ptr_unsafe(&candidate->key, (void *)entry->key); 1013 #else 1014 CK_HT_TYPE_STORE(&candidate->key_length, entry->key_length); 1015 CK_HT_TYPE_STORE(&candidate->hash, entry->hash); 1016 ck_pr_store_ptr_unsafe(&candidate->value, (void *)entry->value); 1017 ck_pr_fence_store(); 1018 ck_pr_store_ptr_unsafe(&candidate->key, (void *)entry->key); 1019 #endif 1020 1021 CK_HT_TYPE_STORE(&map->n_entries, map->n_entries + 1); 1022 1023 /* Enforce a load factor of 0.5. */ 1024 if (map->n_entries * 2 > map->capacity) 1025 ck_ht_grow_spmc(table, map->capacity << 1); 1026 1027 return true; 1028 } 1029 1030 void 1031 ck_ht_destroy(struct ck_ht *table) 1032 { 1033 1034 ck_ht_map_destroy(table->m, table->map, false); 1035 return; 1036 } 1037