benchmark/cliffc-hashtable/cliffc_hashtable.h

   1 #ifndef CLIFFC_HASHTABLE_H
   2 #define CLIFFC_HASHTABLE_H
   3
   4 #include <iostream>
   5 #include <atomic>
   6 //#include <common.h>
   7 #ifdef STANDALONE
   8 #include <assert.h>
   9 #define MODEL_ASSERT assert
  10 #else
  11 #include <model-assert.h>
  12 #endif
  13
  14 #include <spec_lib.h>
  15 #include <stdlib.h>
  16 #include <cdsannotate.h>
  17 #include <specannotation.h>
  18 #include <model_memory.h>
  19 #include "common.h"
  20
  21 using namespace std;
  22
  23 /**
  24         This header file declares and defines a simplified version of Cliff Click's
  25         NonblockingHashMap. It contains all the necessary structrues and main
  26         functions. In simplified_cliffc_hashtable.cc file, it has the definition for
  27         the static fields.
  28 */
  29
  30 template<typename TypeK, typename TypeV>
  31 class cliffc_hashtable;
  32
  33 /**
  34         Corresponding the the Object[] array in Cliff Click's Java implementation.
  35         It keeps the first two slots for CHM (Hashtable control unit) and the hash
  36         records (an array of hash used for fast negative key-equality check).
  37 */
  38 struct kvs_data {
  39         int _size;
  40         atomic<void*> *_data;
  41
  42         kvs_data(int sz) {
  43                 _size = sz;
  44                 int real_size = sz * 2 + 2;
  45                 _data = new atomic<void*>[real_size];
  46                 // The control block should be initialized in resize()
  47                 // Init the hash record array
  48                 int *hashes = new int[_size];
  49                 int i;
  50                 for (i = 0; i < _size; i++) {
  51                         hashes[i] = 0;
  52                 }
  53                 // Init the data to Null slot
  54                 for (i = 2; i < real_size; i++) {
  55                         _data[i].store(NULL, memory_order_relaxed);
  56                 }
  57                 _data[1].store(hashes, memory_order_relaxed);
  58         }
  59
  60         ~kvs_data() {
  61                 int *hashes = (int*) _data[1].load(memory_order_relaxed);
  62                 delete hashes;
  63                 delete[] _data;
  64         }
  65 };
  66
  67 struct slot {
  68         bool _prime;
  69         void *_ptr;
  70
  71         slot(bool prime, void *ptr) {
  72                 _prime = prime;
  73                 _ptr = ptr;
  74         }
  75 };
  76
  77
  78 /**
  79         TypeK must have defined function "int hashCode()" which return the hash
  80         code for the its object, and "int equals(TypeK anotherKey)" which is
  81         used to judge equality.
  82         TypeK and TypeV should define their own copy constructor.
  83 */
  84 /**
  85         @Begin
  86         @Class_begin
  87         @End
  88 */
  89 template<typename TypeK, typename TypeV>
  90 class cliffc_hashtable {
  91         /**
  92                 # The synchronization we have for the hashtable gives us the property of
  93                 # serializability, so we should have a sequential hashtable when we check the
  94                 # correctness. The key thing is to identify all the commit point.
  95
  96                 @Begin
  97                 @Options:
  98                         LANG = CPP;
  99                         CLASS = cliffc_hashtable;
 100                 @Global_define:
 101                         @DeclareVar:
 102                         spec_table *map;
 103                         spec_table *id_map;
 104                         id_tag_t *tag;
 105                         @InitVar:
 106                                 map = new_spec_table_default(equals_key);
 107                                 id_map = new_spec_table_default(equals_id);
 108                                 tag = new_id_tag();
 109
 110                         @DefineFunc:
 111                         bool equals_key(void *ptr1, void *ptr2) {
 112                                 TypeK *key1 = (TypeK*) ptr1,
 113                                         *key2 = (TypeK*) ptr2;
 114                                 if (key1 == NULL || key2 == NULL)
 115                                         return false;
 116                                 return key1->equals(key2);
 117                         }
 118
 119                         @DefineFunc:
 120                         bool equals_val(void *ptr1, void *ptr2) {
 121                                 if (ptr1 == ptr2)
 122                                         return true;
 123                                 TypeV *val1 = (TypeV*) ptr1,
 124                                         *val2 = (TypeV*) ptr2;
 125                                 if (val1 == NULL || val2 == NULL)
 126                                         return false;
 127                                 return val1->equals(val2);
 128                         }
 129
 130                         @DefineFunc:
 131                         bool equals_id(void *ptr1, void *ptr2) {
 132                                 id_tag_t *id1 = (id_tag_t*) ptr1,
 133                                         *id2 = (id_tag_t*) ptr2;
 134                                 if (id1 == NULL || id2 == NULL)
 135                                         return false;
 136                                 return (*id1).tag == (*id2).tag;
 137                         }
 138
 139                         @DefineFunc:
 140                         # Update the tag for the current key slot if the corresponding tag
 141                         # is NULL, otherwise just return that tag. It will update the next
 142                         # available tag too if it requires a new tag for that key slot.
 143                         call_id_t getKeyTag(TypeK *key) {
 144                                 if (!spec_table_contains(id_map, key)) {
 145                                         call_id_t cur_id = current(tag);
 146                                         spec_table_put(id_map, key, (void*) cur_id);
 147                                         next(tag);
 148                                         return cur_id;
 149                                 } else {
 150                                         call_id_t res = (call_id_t) spec_table_get(id_map, key);
 151                                         return res;
 152                                 }
 153                         }
 154
 155                 @Interface_cluster:
 156                         Read_interface = {
 157                                 Get,
 158                                 PutIfAbsent,
 159                                 RemoveAny,
 160                                 RemoveIfMatch,
 161                                 ReplaceAny,
 162                                 ReplaceIfMatch
 163                         }
 164
 165                         Write_interface = {
 166                                 Put,
 167                                 PutIfAbsent(COND_PutIfAbsentSucc),
 168                                 RemoveAny,
 169                                 RemoveIfMatch(COND_RemoveIfMatchSucc),
 170                                 ReplaceAny,
 171                                 ReplaceIfMatch(COND_ReplaceIfMatchSucc)
 172                         }
 173                 @Happens_before:
 174                         //Write_interface -> Read_interface
 175                         Put->Get
 176                         Put->Put
 177                 @End
 178         */
 179
 180 friend class CHM;
 181         /**
 182                 The control structure for the hashtable
 183         */
 184         private:
 185         class CHM {
 186                 friend class cliffc_hashtable;
 187                 private:
 188                 atomic<kvs_data*> _newkvs;
 189
 190                 // Size of active K,V pairs
 191                 atomic_int _size;
 192
 193                 // Count of used slots
 194                 atomic_int _slots;
 195
 196                 // The next part of the table to copy
 197                 atomic_int _copy_idx;
 198
 199                 // Work-done reporting
 200                 atomic_int _copy_done;
 201
 202                 public:
 203                 CHM(int size) {
 204                         _newkvs.store(NULL, memory_order_relaxed);
 205                         _size.store(size, memory_order_relaxed);
 206                         _slots.store(0, memory_order_relaxed);
 207
 208                         _copy_idx.store(0, memory_order_relaxed);
 209                         _copy_done.store(0, memory_order_relaxed);
 210                 }
 211
 212                 ~CHM() {}
 213
 214                 private:
 215
 216                 // Heuristic to decide if the table is too full
 217                 bool table_full(int reprobe_cnt, int len) {
 218                         return
 219                                 reprobe_cnt >= REPROBE_LIMIT &&
 220                                 _slots.load(memory_order_relaxed) >= reprobe_limit(len);
 221                 }
 222
 223                 kvs_data* resize(cliffc_hashtable *topmap, kvs_data *kvs) {
 224                         //model_print("resizing...\n");
 225                         kvs_data *newkvs = _newkvs.load(memory_order_acquire);
 226                         if (newkvs != NULL)
 227                                 return newkvs;
 228
 229                         // No copy in-progress, start one; Only double the table size
 230                         int oldlen = kvs->_size;
 231                         int sz = _size.load(memory_order_relaxed);
 232                         int newsz = sz;
 233
 234                         // Just follow Cliff Click's heuristic to decide the new size
 235                         if (sz >= (oldlen >> 2)) { // If we are 25% full
 236                                 newsz = oldlen << 1; // Double size
 237                                 if (sz >= (oldlen >> 1))
 238                                         newsz = oldlen << 2; // Double double size
 239                         }
 240
 241                         // We do not record the record timestamp
 242                         if (newsz <= oldlen) newsz = oldlen << 1;
 243                         // Do not shrink ever
 244                         if (newsz < oldlen) newsz = oldlen;
 245
 246                         // Last check cause the 'new' below is expensive
 247                         newkvs = _newkvs.load(memory_order_acquire);
 248                         //model_print("hey1\n");
 249                         if (newkvs != NULL) return newkvs;
 250
 251                         newkvs = new kvs_data(newsz);
 252                         void *chm = (void*) new CHM(sz);
 253                         //model_print("hey2\n");
 254                         newkvs->_data[0].store(chm, memory_order_relaxed);
 255
 256                         kvs_data *cur_newkvs;
 257                         // Another check after the slow allocation
 258                         if ((cur_newkvs = _newkvs.load(memory_order_acquire)) != NULL)
 259                                 return cur_newkvs;
 260                         // CAS the _newkvs to the allocated table
 261                         kvs_data *desired = (kvs_data*) NULL;
 262                         kvs_data *expected = (kvs_data*) newkvs;
 263                         if (!_newkvs.compare_exchange_strong(desired, expected, memory_order_release,
 264                                         memory_order_relaxed)) {
 265                                 // Should clean the allocated area
 266                                 delete newkvs;
 267                                 newkvs = _newkvs.load(memory_order_acquire);
 268                         }
 269                         return newkvs;
 270                 }
 271
 272                 void help_copy_impl(cliffc_hashtable *topmap, kvs_data *oldkvs,
 273                         bool copy_all) {
 274                         MODEL_ASSERT (get_chm(oldkvs) == this);
 275                         kvs_data *newkvs = _newkvs.load(memory_order_acquire);
 276                         int oldlen = oldkvs->_size;
 277                         int min_copy_work = oldlen > 1024 ? 1024 : oldlen;
 278
 279                         // Just follow Cliff Click's code here
 280                         int panic_start = -1;
 281                         int copyidx;
 282                         while (_copy_done.load(memory_order_relaxed) < oldlen) {
 283                                 copyidx = _copy_idx.load(memory_order_relaxed);
 284                                 if (panic_start == -1) { // No painc
 285                                         copyidx = _copy_idx.load(memory_order_relaxed);
 286                                         while (copyidx < (oldlen << 1) &&
 287                                                 !_copy_idx.compare_exchange_strong(copyidx, copyidx +
 288                                                         min_copy_work, memory_order_release, memory_order_relaxed))
 289                                                 copyidx = _copy_idx.load(memory_order_relaxed);
 290                                         if (!(copyidx < (oldlen << 1)))
 291                                                 panic_start = copyidx;
 292                                 }
 293
 294                                 // Now copy the chunk of work we claimed
 295                                 int workdone = 0;
 296                                 for (int i = 0; i < min_copy_work; i++)
 297                                         if (copy_slot(topmap, (copyidx + i) & (oldlen - 1), oldkvs,
 298                                                 newkvs))
 299                                                 workdone++;
 300                                 if (workdone > 0)
 301                                         copy_check_and_promote(topmap, oldkvs, workdone);
 302
 303                                 copyidx += min_copy_work;
 304                                 if (!copy_all && panic_start == -1)
 305                                         return; // We are done with the work we claim
 306                         }
 307                         copy_check_and_promote(topmap, oldkvs, 0); // See if we can promote
 308                 }
 309
 310                 kvs_data* copy_slot_and_check(cliffc_hashtable *topmap, kvs_data
 311                         *oldkvs, int idx, void *should_help) {
 312                         kvs_data *newkvs = _newkvs.load(memory_order_acquire);
 313                         // We're only here cause the caller saw a Prime
 314                         if (copy_slot(topmap, idx, oldkvs, newkvs))
 315                                 copy_check_and_promote(topmap, oldkvs, 1); // Record the slot copied
 316                         return (should_help == NULL) ? newkvs : topmap->help_copy(newkvs);
 317                 }
 318
 319                 void copy_check_and_promote(cliffc_hashtable *topmap, kvs_data*
 320                         oldkvs, int workdone) {
 321                         int oldlen = oldkvs->_size;
 322                         int copyDone = _copy_done.load(memory_order_relaxed);
 323                         if (workdone > 0) {
 324                                 while (true) {
 325                                         copyDone = _copy_done.load(memory_order_relaxed);
 326                                         if (_copy_done.compare_exchange_weak(copyDone, copyDone +
 327                                                 workdone, memory_order_relaxed, memory_order_relaxed))
 328                                                 break;
 329                                 }
 330                         }
 331
 332                         // Promote the new table to the current table
 333                         if (copyDone + workdone == oldlen &&
 334                                 topmap->_kvs.load(memory_order_relaxed) == oldkvs) {
 335                                 kvs_data *newkvs = _newkvs.load(memory_order_acquire);
 336                                 topmap->_kvs.compare_exchange_strong(oldkvs, newkvs, memory_order_release,
 337                                         memory_order_relaxed);
 338                         }
 339                 }
 340
 341                 bool copy_slot(cliffc_hashtable *topmap, int idx, kvs_data *oldkvs,
 342                         kvs_data *newkvs) {
 343                         slot *key_slot;
 344                         while ((key_slot = key(oldkvs, idx)) == NULL)
 345                                 CAS_key(oldkvs, idx, NULL, TOMBSTONE);
 346
 347                         // First CAS old to Prime
 348                         slot *oldval = val(oldkvs, idx);
 349                         while (!is_prime(oldval)) {
 350                                 slot *box = (oldval == NULL || oldval == TOMBSTONE)
 351                                         ? TOMBPRIME : new slot(true, oldval->_ptr);
 352                                 if (CAS_val(oldkvs, idx, oldval, box)) {
 353                                         if (box == TOMBPRIME)
 354                                                 return 1; // Copy done
 355                                         // Otherwise we CAS'd the box
 356                                         oldval = box; // Record updated oldval
 357                                         break;
 358                                 }
 359                                 oldval = val(oldkvs, idx); // Else re-try
 360                         }
 361
 362                         if (oldval == TOMBPRIME) return false; // Copy already completed here
 363
 364                         slot *old_unboxed = new slot(false, oldval->_ptr);
 365                         int copied_into_new = (putIfMatch(topmap, newkvs, key_slot, old_unboxed,
 366                                 NULL) == NULL);
 367
 368                         // Old value is exposed in the new table
 369                         while (!CAS_val(oldkvs, idx, oldval, TOMBPRIME))
 370                                 oldval = val(oldkvs, idx);
 371
 372                         return copied_into_new;
 373                 }
 374         };
 375
 376
 377
 378         private:
 379         static const int Default_Init_Size = 4; // Intial table size
 380
 381         static slot* const MATCH_ANY;
 382         static slot* const NO_MATCH_OLD;
 383
 384         static slot* const TOMBPRIME;
 385         static slot* const TOMBSTONE;
 386
 387         static const int REPROBE_LIMIT = 10; // Forces a table-resize
 388
 389         atomic<kvs_data*> _kvs;
 390
 391         public:
 392         cliffc_hashtable() {
 393                 // Should initialize the CHM for the construction of the table
 394                 // For other CHM in kvs_data, they should be initialzed in resize()
 395                 // because the size is determined dynamically
 396                 /**
 397                         @Begin
 398                         @Entry_point
 399                         @End
 400                 */
 401                 kvs_data *kvs = new kvs_data(Default_Init_Size);
 402                 void *chm = (void*) new CHM(0);
 403                 kvs->_data[0].store(chm, memory_order_relaxed);
 404                 _kvs.store(kvs, memory_order_relaxed);
 405         }
 406
 407         cliffc_hashtable(int init_size) {
 408                 // Should initialize the CHM for the construction of the table
 409                 // For other CHM in kvs_data, they should be initialzed in resize()
 410                 // because the size is determined dynamically
 411
 412                 /**
 413                         @Begin
 414                         @Entry_point
 415                         @End
 416                 */
 417                 kvs_data *kvs = new kvs_data(init_size);
 418                 void *chm = (void*) new CHM(0);
 419                 kvs->_data[0].store(chm, memory_order_relaxed);
 420                 _kvs.store(kvs, memory_order_relaxed);
 421         }
 422
 423         /**
 424                 @Begin
 425                 @Interface: Get
 426                 @Commit_point_set: Get_Success_Point1 | Get_Success_Point2 | Get_Success_Point3
 427                 @ID: getKeyTag(key)
 428                 @Action:
 429                         TypeV *_Old_Val = (TypeV*) spec_table_get(map, key);
 430                         //bool passed = equals_val(_Old_Val, __RET__);
 431                         bool passed = false;
 432                         if (!passed) {
 433                                 int old = _Old_Val == NULL ? 0 : _Old_Val->_val;
 434                                 int ret = __RET__ == NULL ? 0 : __RET__->_val;
 435                                 //model_print("Get: key: %d, _Old_Val: %d, RET: %d\n",
 436                                 //key->_val, old, ret);
 437                         }
 438                 @Post_check:
 439                         //__RET__ == NULL ? true : equals_val(_Old_Val, __RET__)
 440                         equals_val(_Old_Val, __RET__)
 441                 @End
 442         */
 443         TypeV* get(TypeK *key) {
 444                 slot *key_slot = new slot(false, key);
 445                 int fullhash = hash(key_slot);
 446                 kvs_data *kvs = _kvs.load(memory_order_acquire);
 447                 slot *V = get_impl(this, kvs, key_slot, fullhash);
 448                 if (V == NULL) return NULL;
 449                 MODEL_ASSERT (!is_prime(V));
 450                 return (TypeV*) V->_ptr;
 451         }
 452
 453         /**
 454                 @Begin
 455                 @Interface: Put
 456                 @Commit_point_set: Write_Success_Point
 457                 @ID: getKeyTag(key)
 458                 @Action:
 459                         # Remember this old value at checking point
 460                         TypeV *_Old_Val = (TypeV*) spec_table_get(map, key);
 461                         spec_table_put(map, key, val);
 462                         //bool passed = equals_val(__RET__, _Old_Val);
 463                         bool passed = false;
 464                         if (!passed) {
 465                                 int old = _Old_Val == NULL ? 0 : _Old_Val->_val;
 466                                 int ret = __RET__ == NULL ? 0 : __RET__->_val;
 467                                 //model_print("Put: key: %d, val: %d, _Old_Val: %d, RET: %d\n",
 468                                 //      key->_val, val->_val, old, ret);
 469                         }
 470                 @Post_check:
 471                         equals_val(__RET__, _Old_Val)
 472                 @End
 473         */
 474         TypeV* put(TypeK *key, TypeV *val) {
 475                 return putIfMatch(key, val, NO_MATCH_OLD);
 476         }
 477
 478         /**
 479 //              @Begin
 480                 @Interface: PutIfAbsent
 481                 @Commit_point_set:
 482                         Write_Success_Point | PutIfAbsent_Fail_Point
 483                 @Condition: !spec_table_contains(map, key)
 484                 @HB_condition:
 485                         COND_PutIfAbsentSucc :: __RET__ == NULL
 486                 @ID: getKeyTag(key)
 487                 @Action:
 488                         void *_Old_Val = spec_table_get(map, key);
 489                         if (__COND_SAT__)
 490                                 spec_table_put(map, key, value);
 491                 @Post_check:
 492                         __COND_SAT__ ? __RET__ == NULL : equals_val(_Old_Val, __RET__)
 493                 @End
 494         */
 495         TypeV* putIfAbsent(TypeK *key, TypeV *value) {
 496                 return putIfMatch(key, val, TOMBSTONE);
 497         }
 498
 499         /**
 500 //              @Begin
 501                 @Interface: RemoveAny
 502                 @Commit_point_set: Write_Success_Point
 503                 @ID: getKeyTag(key)
 504                 @Action:
 505                         void *_Old_Val = spec_table_get(map, key);
 506                         spec_table_put(map, key, NULL);
 507                 @Post_check:
 508                         equals_val(__RET__, _Old_Val)
 509                 @End
 510         */
 511         TypeV* remove(TypeK *key) {
 512                 return putIfMatch(key, TOMBSTONE, NO_MATCH_OLD);
 513         }
 514
 515         /**
 516 //              @Begin
 517                 @Interface: RemoveIfMatch
 518                 @Commit_point_set:
 519                         Write_Success_Point | RemoveIfMatch_Fail_Point
 520                 @Condition:
 521                         equals_val(spec_table_get(map, key), val)
 522                 @HB_condition:
 523                         COND_RemoveIfMatchSucc :: __RET__ == true
 524                 @ID: getKeyTag(key)
 525                 @Action:
 526                         if (__COND_SAT__)
 527                                 spec_table_put(map, key, NULL);
 528                 @Post_check:
 529                         __COND_SAT__ ? __RET__ : !__RET__
 530                 @End
 531         */
 532         bool remove(TypeK *key, TypeV *val) {
 533                 slot *val_slot = val == NULL ? NULL : new slot(false, val);
 534                 return putIfMatch(key, TOMBSTONE, val) == val;
 535
 536         }
 537
 538         /**
 539 //              @Begin
 540                 @Interface: ReplaceAny
 541                 @Commit_point_set:
 542                         Write_Success_Point
 543                 @ID: getKeyTag(key)
 544                 @Action:
 545                         void *_Old_Val = spec_table_get(map, key);
 546                 @Post_check:
 547                         equals_val(__RET__, _Old_Val)
 548                 @End
 549         */
 550         TypeV* replace(TypeK *key, TypeV *val) {
 551                 return putIfMatch(key, val, MATCH_ANY);
 552         }
 553
 554         /**
 555 //              @Begin
 556                 @Interface: ReplaceIfMatch
 557                 @Commit_point_set:
 558                         Write_Success_Point | ReplaceIfMatch_Fail_Point
 559                 @Condition:
 560                         equals_val(spec_table_get(map, key), oldval)
 561                 @HB_condition:
 562                         COND_ReplaceIfMatchSucc :: __RET__ == true
 563                 @ID: getKeyTag(key)
 564                 @Action:
 565                         if (__COND_SAT__)
 566                                 spec_table_put(map, key, newval);
 567                 @Post_check:
 568                         __COND_SAT__ ? __RET__ : !__RET__
 569                 @End
 570         */
 571         bool replace(TypeK *key, TypeV *oldval, TypeV *newval) {
 572                 return putIfMatch(key, newval, oldval) == oldval;
 573         }
 574
 575         private:
 576         static CHM* get_chm(kvs_data* kvs) {
 577                 CHM *res = (CHM*) kvs->_data[0].load(memory_order_relaxed);
 578                 return res;
 579         }
 580
 581         static int* get_hashes(kvs_data *kvs) {
 582                 return (int *) kvs->_data[1].load(memory_order_relaxed);
 583         }
 584
 585         // Preserve happens-before semantics on newly inserted keys
 586         static inline slot* key(kvs_data *kvs, int idx) {
 587                 MODEL_ASSERT (idx >= 0 && idx < kvs->_size);
 588                 // Corresponding to the volatile read in get_impl() and putIfMatch in
 589                 // Cliff Click's Java implementation
 590                 slot *res = (slot*) kvs->_data[idx * 2 + 2].load(memory_order_relaxed);
 591                 /**
 592                         @Begin
 593                         # This is a complicated potential commit point since many many functions are
 594                         # calling val().
 595                         @Potential_commit_point_define: true
 596                         @Label: Read_Key_Point
 597                         @End
 598                 */
 599                 return res;
 600         }
 601
 602         /**
 603                 The atomic operation in val() function is a "potential" commit point,
 604                 which means in some case it is a real commit point while it is not for
 605                 some other cases. This so happens because the val() function is such a
 606                 fundamental function that many internal operation will call. Our
 607                 strategy is that we label any potential commit points and check if they
 608                 really are the commit points later.
 609         */
 610         // Preserve happens-before semantics on newly inserted values
 611         static inline slot* val(kvs_data *kvs, int idx) {
 612                 MODEL_ASSERT (idx >= 0 && idx < kvs->_size);
 613                 // Corresponding to the volatile read in get_impl() and putIfMatch in
 614                 // Cliff Click's Java implementation
 615                 slot *res = (slot*) kvs->_data[idx * 2 + 3].load(memory_order_acquire);
 616                 /**
 617                         @Begin
 618                         # This is a complicated potential commit point since many many functions are
 619                         # calling val().
 620                         @Potential_commit_point_define: true
 621                         @Label: Read_Val_Point
 622                         @End
 623                 */
 624                 return res;
 625
 626
 627         }
 628
 629         static int hash(slot *key_slot) {
 630                 MODEL_ASSERT(key_slot != NULL && key_slot->_ptr != NULL);
 631                 TypeK* key = (TypeK*) key_slot->_ptr;
 632                 int h = key->hashCode();
 633                 // Spread bits according to Cliff Click's code
 634                 h += (h << 15) ^ 0xffffcd7d;
 635                 h ^= (h >> 10);
 636                 h += (h << 3);
 637                 h ^= (h >> 6);
 638                 h += (h << 2) + (h << 14);
 639                 return h ^ (h >> 16);
 640         }
 641
 642         // Heuristic to decide if reprobed too many times.
 643         // Be careful here: Running over the limit on a 'get' acts as a 'miss'; on a
 644         // put it triggers a table resize. Several places MUST have exact agreement.
 645         static int reprobe_limit(int len) {
 646                 return REPROBE_LIMIT + (len >> 2);
 647         }
 648
 649         static inline bool is_prime(slot *val) {
 650                 return (val != NULL) && val->_prime;
 651         }
 652
 653         // Check for key equality. Try direct pointer comparison first (fast
 654         // negative teset) and then the full 'equals' call
 655         static bool keyeq(slot *K, slot *key_slot, int *hashes, int hash,
 656                 int fullhash) {
 657                 // Caller should've checked this.
 658                 MODEL_ASSERT (K != NULL);
 659                 TypeK* key_ptr = (TypeK*) key_slot->_ptr;
 660                 return
 661                         K == key_slot ||
 662                                 ((hashes[hash] == 0 || hashes[hash] == fullhash) &&
 663                                 K != TOMBSTONE &&
 664                                 key_ptr->equals(K->_ptr));
 665         }
 666
 667         static bool valeq(slot *val_slot1, slot *val_slot2) {
 668                 MODEL_ASSERT (val_slot1 != NULL);
 669                 TypeK* ptr1 = (TypeV*) val_slot1->_ptr;
 670                 if (val_slot2 == NULL || ptr1 == NULL) return false;
 671                 return ptr1->equals(val_slot2->_ptr);
 672         }
 673
 674         // Together with key() preserve the happens-before relationship on newly
 675         // inserted keys
 676         static inline bool CAS_key(kvs_data *kvs, int idx, void *expected, void *desired) {
 677                 return kvs->_data[2 * idx + 2].compare_exchange_strong(expected,
 678                         desired, memory_order_relaxed, memory_order_relaxed);
 679         }
 680
 681         /**
 682                 Same as the val() function, we only label the CAS operation as the
 683                 potential commit point.
 684         */
 685         // Together with val() preserve the happens-before relationship on newly
 686         // inserted values
 687         static inline bool CAS_val(kvs_data *kvs, int idx, void *expected, void
 688                 *desired) {
 689                 bool res =  kvs->_data[2 * idx + 3].compare_exchange_strong(expected,
 690                         desired, memory_order_acq_rel, memory_order_relaxed);
 691                 /**
 692                         # If it is a successful put instead of a copy or any other internal
 693                         # operantions, expected != NULL
 694                         @Begin
 695                         @Potential_commit_point_define: res
 696                         @Label: Write_Val_Point
 697                         @End
 698                 */
 699                 return res;
 700         }
 701
 702         slot* get_impl(cliffc_hashtable *topmap, kvs_data *kvs, slot* key_slot, int
 703                 fullhash) {
 704                 int len = kvs->_size;
 705                 CHM *chm = get_chm(kvs);
 706                 int *hashes = get_hashes(kvs);
 707
 708                 int idx = fullhash & (len - 1);
 709                 int reprobe_cnt = 0;
 710                 while (true) {
 711                         slot *K = key(kvs, idx);
 712                         /**
 713                                 @Begin
 714                                 @Commit_point_define: K == NULL
 715                                 @Potential_commit_point_label: Read_Key_Point
 716                                 @Label: Get_Success_Point_1
 717                                 @End
 718                         */
 719                         slot *V = val(kvs, idx);
 720
 721
 722                         if (K == NULL) {
 723                                 //model_print("Key is null\n");
 724                                 return NULL; // A miss
 725                         }
 726
 727                         if (keyeq(K, key_slot, hashes, idx, fullhash)) {
 728                                 // Key hit! Check if table-resize in progress
 729                                 if (!is_prime(V)) {
 730                                         /**
 731                                                 @Begin
 732                                                 @Commit_point_define: true
 733                                                 @Potential_commit_point_label: Read_Val_Point
 734                                                 @Label: Get_Success_Point_2
 735                                                 @End
 736                                         */
 737                                         return (V == TOMBSTONE) ? NULL : V; // Return this value
 738                                 }
 739                                 // Otherwise, finish the copy & retry in the new table
 740                                 return get_impl(topmap, chm->copy_slot_and_check(topmap, kvs,
 741                                         idx, key_slot), key_slot, fullhash);
 742                         }
 743
 744                         if (++reprobe_cnt >= REPROBE_LIMIT ||
 745                                 key_slot == TOMBSTONE) {
 746                                 // Retry in new table
 747                                 // Atomic read can be here
 748                                 kvs_data *newkvs = chm->_newkvs.load(memory_order_acquire);
 749                                 /**
 750                                         @Begin
 751                                         @Commit_point_define_check: newkvs == NULL
 752                                         @Label: Get_Success_Point_3
 753                                         @End
 754                                 */
 755                                 return newkvs == NULL ? NULL : get_impl(topmap,
 756                                         topmap->help_copy(newkvs), key_slot, fullhash);
 757                         }
 758
 759                         idx = (idx + 1) & (len - 1); // Reprobe by 1
 760                 }
 761         }
 762
 763         // A wrapper of the essential function putIfMatch()
 764         TypeV* putIfMatch(TypeK *key, TypeV *value, slot *old_val) {
 765                 // TODO: Should throw an exception rather return NULL
 766                 if (old_val == NULL) {
 767                         return NULL;
 768                 }
 769                 slot *key_slot = new slot(false, key);
 770
 771                 slot *value_slot = new slot(false, value);
 772                 kvs_data *kvs = _kvs.load(memory_order_acquire);
 773                 slot *res = putIfMatch(this, kvs, key_slot, value_slot, old_val);
 774                 // Only when copy_slot() call putIfMatch() will it return NULL
 775                 MODEL_ASSERT (res != NULL);
 776                 MODEL_ASSERT (!is_prime(res));
 777                 return res == TOMBSTONE ? NULL : (TypeV*) res->_ptr;
 778         }
 779
 780         /**
 781                 Put, Remove, PutIfAbsent, etc will call this function. Return the old
 782                 value. If the returned value is equals to the expVal (or expVal is
 783                 NO_MATCH_OLD), then this function puts the val_slot to the table 'kvs'.
 784                 Only copy_slot will pass a NULL expVal, and putIfMatch only returns a
 785                 NULL if passed a NULL expVal.
 786         */
 787         static slot* putIfMatch(cliffc_hashtable *topmap, kvs_data *kvs, slot
 788                 *key_slot, slot *val_slot, slot *expVal) {
 789                 MODEL_ASSERT (val_slot != NULL);
 790                 MODEL_ASSERT (!is_prime(val_slot));
 791                 MODEL_ASSERT (!is_prime(expVal));
 792
 793                 int fullhash = hash(key_slot);
 794                 int len = kvs->_size;
 795                 CHM *chm = get_chm(kvs);
 796                 int *hashes = get_hashes(kvs);
 797                 int idx = fullhash & (len - 1);
 798
 799                 // Claim a key slot
 800                 int reprobe_cnt = 0;
 801                 slot *K;
 802                 slot *V;
 803                 kvs_data *newkvs;
 804
 805                 while (true) { // Spin till we get a key slot
 806                         K = key(kvs, idx);
 807                         V = val(kvs, idx);
 808                         if (K == NULL) { // Get a free slot
 809                                 if (val_slot == TOMBSTONE) return val_slot;
 810                                 // Claim the null key-slot
 811                                 if (CAS_key(kvs, idx, NULL, key_slot)) {
 812                                         chm->_slots.fetch_add(1, memory_order_relaxed); // Inc key-slots-used count
 813                                         hashes[idx] = fullhash; // Memorize full hash
 814                                         break;
 815                                 }
 816                                 K = key(kvs, idx); // CAS failed, get updated value
 817                                 MODEL_ASSERT (K != NULL);
 818                         }
 819
 820                         // Key slot not null, there exists a Key here
 821                         if (keyeq(K, key_slot, hashes, idx, fullhash))
 822                                 break; // Got it
 823
 824                         // Notice that the logic here should be consistent with that of get.
 825                         // The first predicate means too many reprobes means nothing in the
 826                         // old table.
 827                         if (++reprobe_cnt >= reprobe_limit(len) ||
 828                                 K == TOMBSTONE) { // Found a Tombstone key, no more keys
 829                                 newkvs = chm->resize(topmap, kvs);
 830                                 //model_print("resize1\n");
 831                                 // Help along an existing copy
 832                                 if (expVal != NULL) topmap->help_copy(newkvs);
 833                                 return putIfMatch(topmap, newkvs, key_slot, val_slot, expVal);
 834                         }
 835
 836                         idx = (idx + 1) & (len - 1); // Reprobe
 837                 } // End of spinning till we get a Key slot
 838
 839                 if (val_slot == V) return V; // Fast cutout for no-change
 840
 841                 // Here it tries to resize cause it doesn't want other threads to stop
 842                 // its progress (eagerly try to resize soon)
 843                 newkvs = chm->_newkvs.load(memory_order_acquire);
 844                 if (newkvs == NULL &&
 845                         ((V == NULL && chm->table_full(reprobe_cnt, len)) || is_prime(V))) {
 846                         //model_print("resize2\n");
 847                         newkvs = chm->resize(topmap, kvs); // Force the copy to start
 848                 }
 849
 850                 // Finish the copy and then put it in the new table
 851                 if (newkvs != NULL)
 852                         return putIfMatch(topmap, chm->copy_slot_and_check(topmap, kvs, idx,
 853                                 expVal), key_slot, val_slot, expVal);
 854
 855                 // Decided to update the existing table
 856                 while (true) {
 857                         MODEL_ASSERT (!is_prime(V));
 858
 859                         if (expVal != NO_MATCH_OLD &&
 860                                 V != expVal &&
 861                                 (expVal != MATCH_ANY || V == TOMBSTONE || V == NULL) &&
 862                                 !(V == NULL && expVal == TOMBSTONE) &&
 863                                 (expVal == NULL || !valeq(expVal, V))) {
 864                                 /**
 865                                         @Begin
 866                                         @Commit_point_define: expVal == TOMBSTONE
 867                                         @Potential_commit_point_label: Read_Val_Point
 868                                         @Label: PutIfAbsent_Fail_Point
 869                                                 # This is a check for the PutIfAbsent() when the value
 870                                                 # is not absent
 871                                         @End
 872                                 */
 873                                 /**
 874                                         @Begin
 875                                         @Commit_point_define: expVal != NULL && val_slot == TOMBSTONE
 876                                         @Potential_commit_point_label: Read_Val_Point
 877                                         @Label: RemoveIfMatch_Fail_Point
 878                                         @End
 879                                 */
 880                                 /**
 881                                         @Begin
 882                                         @Commit_point_define: expVal != NULL && !valeq(expVal, V)
 883                                         @Potential_commit_point_label: Read_Val_Point
 884                                         @Label: ReplaceIfMatch_Fail_Point
 885                                         @End
 886                                 */
 887                                 return V; // Do not update!
 888                         }
 889
 890                         if (CAS_val(kvs, idx, V, val_slot)) {
 891                                 /**
 892                                         @Begin
 893                                         # The only point where a successful put happens
 894                                         @Commit_point_define: true
 895                                         @Potential_commit_point_label: Write_Val_Point
 896                                         @Label: Write_Success_Point
 897                                         @End
 898                                 */
 899                                 if (expVal != NULL) { // Not called by a table-copy
 900                                         // CAS succeeded, should adjust size
 901                                         // Both normal put's and table-copy calls putIfMatch, but
 902                                         // table-copy does not increase the number of live K/V pairs
 903                                         if ((V == NULL || V == TOMBSTONE) &&
 904                                                 val_slot != TOMBSTONE)
 905                                                 chm->_size.fetch_add(1, memory_order_relaxed);
 906                                         if (!(V == NULL || V == TOMBSTONE) &&
 907                                                 val_slot == TOMBSTONE)
 908                                                 chm->_size.fetch_add(-1, memory_order_relaxed);
 909                                 }
 910                                 return (V == NULL && expVal != NULL) ? TOMBSTONE : V;
 911                         }
 912                         // Else CAS failed
 913                         V = val(kvs, idx);
 914                         if (is_prime(V))
 915                                 return putIfMatch(topmap, chm->copy_slot_and_check(topmap, kvs,
 916                                         idx, expVal), key_slot, val_slot, expVal);
 917                 }
 918         }
 919
 920         // Help along an existing table-resize. This is a fast cut-out wrapper.
 921         kvs_data* help_copy(kvs_data *helper) {
 922                 kvs_data *topkvs = _kvs.load(memory_order_acquire);
 923                 CHM *topchm = get_chm(topkvs);
 924                 // No cpy in progress
 925                 if (topchm->_newkvs.load(memory_order_relaxed) == NULL) return helper;
 926                 topchm->help_copy_impl(this, topkvs, false);
 927                 return helper;
 928         }
 929 };
 930 /**
 931         @Begin
 932         @Class_end
 933         @End
 934 */
 935
 936 #endif