1 #ifndef SIMPLIFIED_CLIFFC_HASHTABLE_H
2 #define SIMPLIFIED_CLIFFC_HASHTABLE_H
14 This header file declares and defines a simplified version of Cliff Click's
15 NonblockingHashMap. It contains all the necessary structrues and main
16 functions. In simplified_cliffc_hashtable.cc file, it has the definition for
20 template<typename TypeK, typename TypeV>
21 class cliffc_hashtable;
24 Corresponding the the Object[] array in Cliff Click's Java implementation.
25 It keeps the first two slots for CHM (Hashtable control unit) and the hash
26 records (an array of hash used for fast negative key-equality check).
34 int real_size = sizeof(atomic<void*>) * 2 + 2;
35 _data = new atomic<void*>[real_size];
36 // The control block should be initialized in resize()
37 // Init the hash record array
38 int *hashes = new int[_size];
40 for (i = 0; i < _size; i++) {
43 _data[1].store(hashes, memory_order_relaxed);
44 // Init the data to Null slot
45 for (i = 2; i < real_size; i++) {
46 _data[i].store(NULL, memory_order_relaxed);
51 int *hashes = (int*) _data[1].load(memory_order_relaxed);
59 shared_ptr<void> _ptr;
61 slot(bool prime, shared_ptr<void> ptr) {
70 TypeK must have defined function "int hashCode()" which return the hash
71 code for the its object, and "int equals(TypeK anotherKey)" which is
72 used to judge equality.
73 TypeK and TypeV should define their own copy constructor.
74 To make the memory management safe and similar to Cliff Click's Java
75 implementation, we use shared_ptr instead of normal pointer in terms of the
76 pointers that point to TypeK and TypeV.
78 template<typename TypeK, typename TypeV>
79 class cliffc_hashtable {
81 # The synchronization we have for the hashtable gives us the property of
82 # serializability, so we should have a sequential hashtable when we check the
83 # correctness. The key thing is to identify all the commit point.
88 spec_hashtable<TypeK, TypeV*> __map;
89 spec_hashtable<TypeK, Tag> __id_map;
92 static bool _val_equals(TypeV *ptr1, TypeV *ptr2) {
96 # Update the tag for the current key slot if the corresponding tag
97 # is NULL, otherwise just return that tag. It will update the next
98 # available tag too if it requires a new tag for that key slot.
99 static Tag _getKeyTag(TypeK &key) {
100 if (__id_map.get(key) == NULL) {
101 Tag cur_tag = tag.current();
102 __id_map.put(key, cur_tag);
106 return __id_map.get(key);
122 PutIfAbsent(COND_PutIfAbsentSucc),
124 RemoveIfMatch(COND_RemoveIfMatchSucc),
126 ReplaceIfMatch(COND_ReplaceIfMatchSucc)
129 Write_interface -> Read_interface
135 The control structure for the hashtable
139 friend class cliffc_hashtable;
141 atomic<kvs_data*> _newkvs;
143 // Size of active K,V pairs
146 // Count of used slots
149 // The next part of the table to copy
150 atomic_int _copy_idx;
152 // Work-done reporting
153 atomic_int _copy_done;
157 _size.store(size, memory_order_relaxed);
158 _slots.store(0, memory_order_relaxed);
160 _copy_idx.store(0, memory_order_relaxed);
161 _copy_done.store(0, memory_order_release);
168 // Heuristic to decide if the table is too full
169 bool table_full(int reprobe_cnt, int len) {
171 reprobe_cnt >= REPROBE_LIMIT &&
172 _slots.load(memory_order_relaxed) >= reprobe_limit(len);
175 kvs_data* resize(cliffc_hashtable *topmap, kvs_data *kvs) {
176 kvs_data *newkvs = _newkvs.load(memory_order_acquire);
180 // No copy in-progress, start one; Only double the table size
181 int oldlen = kvs->_size;
182 int sz = _size.load(memory_order_relaxed);
185 // Just follow Cliff Click's heuristic to decide the new size
186 if (sz >= (oldlen >> 2)) { // If we are 25% full
187 newsz = oldlen << 1; // Double size
188 if (sz >= (oldlen >> 1))
189 newsz = oldlen << 2; // Double double size
192 // We do not record the record timestamp
193 if (newsz <= oldlen) newsz = oldlen << 1;
194 // Do not shrink ever
195 if (newsz < oldlen) newsz = oldlen;
197 // Last check cause the 'new' below is expensive
198 newkvs = _newkvs.load(memory_order_acquire);
199 if (newkvs != NULL) return newkvs;
201 newkvs = new kvs_data(newsz);
202 void *chm = (void*) new CHM(sz);
203 newkvs->_data[0].store(chm, memory_order_relaxed);
205 kvs_data *cur_newkvs;
206 // Another check after the slow allocation
207 if ((cur_newkvs = _newkvs.load(memory_order_acquire)) != NULL)
209 // CAS the _newkvs to the allocated table
210 kvs_data *desired = (kvs_data*) NULL;
211 kvs_data *expected = (kvs_data*) newkvs;
212 if (!_newkvs.compare_exchange_strong(desired, expected, memory_order_release,
213 memory_order_release)) {
214 // Should clean the allocated area
216 newkvs = _newkvs.load(memory_order_acquire);
221 void help_copy_impl(cliffc_hashtable *topmap, kvs_data *oldkvs,
223 assert (get_chm(oldkvs) == this);
224 kvs_data *newkvs = _newkvs.load(memory_order_acquire);
225 int oldlen = oldkvs->_size;
226 int min_copy_work = oldlen > 1024 ? 1024 : oldlen;
228 // Just follow Cliff Click's code here
229 int panic_start = -1;
231 while (_copy_done.load(memory_order_acquire) < oldlen) {
232 copyidx = _copy_idx.load(memory_order_acquire);
233 if (panic_start == -1) { // No painc
234 copyidx = _copy_idx.load(memory_order_acquire);
235 while (copyidx < (oldlen << 1) &&
236 !_copy_idx.compare_exchange_strong(copyidx, copyidx +
237 min_copy_work, memory_order_release, memory_order_release))
238 copyidx = _copy_idx.load(memory_order_relaxed);
239 if (!(copyidx < (oldlen << 1)))
240 panic_start = copyidx;
243 // Now copy the chunk of work we claimed
245 for (int i = 0; i < min_copy_work; i++)
246 if (copy_slot(topmap, (copyidx + i) & (oldlen - 1), oldkvs,
250 copy_check_and_promote(topmap, oldkvs, workdone);
252 copyidx += min_copy_work;
253 if (!copy_all && panic_start == -1)
254 return; // We are done with the work we claim
256 copy_check_and_promote(topmap, oldkvs, 0); // See if we can promote
259 kvs_data* copy_slot_and_check(cliffc_hashtable *topmap, kvs_data
260 *oldkvs, int idx, void *should_help) {
261 kvs_data *newkvs = _newkvs.load(memory_order_acquire);
262 // We're only here cause the caller saw a Prime
263 if (copy_slot(topmap, idx, oldkvs, _newkvs))
264 copy_check_and_promote(topmap, oldkvs, 1); // Record the slot copied
265 return (should_help == NULL) ? newkvs : topmap->help_copy(newkvs);
268 void copy_check_and_promote(cliffc_hashtable *topmap, kvs_data*
269 oldkvs, int workdone) {
270 int oldlen = oldkvs->_size;
271 int copyDone = _copy_done.load(memory_order_relaxed);
274 copyDone = _copy_done.load(memory_order_relaxed);
275 if (_copy_done.compare_exchange_weak(copyDone, copyDone +
276 workdone, memory_order_relaxed, memory_order_relaxed))
281 // Promote the new table to the current table
282 if (copyDone + workdone == oldlen &&
283 topmap->_kvs.load(memory_order_acquire) == oldkvs)
284 topmap->_kvs.compare_exchange_strong(oldkvs, _newkvs, memory_order_release,
285 memory_order_release);
288 bool copy_slot(cliffc_hashtable *topmap, int idx, kvs_data *oldkvs,
291 while ((key_slot = key(oldkvs, idx)) == NULL)
292 CAS_key(oldkvs, idx, NULL, TOMBSTONE);
294 // First CAS old to Prime
295 slot *oldval = val(oldkvs, idx, NULL);
296 while (!is_prime(oldval)) {
297 slot *box = (oldval == NULL || oldval == TOMBSTONE)
298 ? TOMBPRIME : new slot(true, oldval->_ptr);
299 if (CAS_val(oldkvs, idx, oldval, box)) {
300 if (box == TOMBPRIME)
301 return 1; // Copy done
302 // Otherwise we CAS'd the box
303 oldval = box; // Record updated oldval
306 oldval = val(oldkvs, idx, NULL); // Else re-try
309 if (oldval == TOMBPRIME) return false; // Copy already completed here
311 slot *old_unboxed = new slot(false, oldval->_ptr);
312 int copied_into_new = (putIfMatch(topmap, newkvs, key_slot, old_unboxed,
315 // Old value is exposed in the new table
316 while (!CAS_val(oldkvs, idx, oldval, TOMBPRIME))
317 oldval = val(oldkvs, idx, NULL);
319 return copied_into_new;
326 static const int Default_Init_Size = 8; // Intial table size
328 static slot* const MATCH_ANY;
329 static slot* const NO_MATCH_OLD;
331 static slot* const TOMBPRIME;
332 static slot* const TOMBSTONE;
334 static const int REPROBE_LIMIT = 10; // Forces a table-resize
336 atomic<kvs_data*> _kvs;
340 // Should initialize the CHM for the construction of the table
341 // For other CHM in kvs_data, they should be initialzed in resize()
342 // because the size is determined dynamically
343 kvs_data *kvs = new kvs_data(Default_Init_Size);
344 void *chm = (void*) new CHM(0);
345 kvs->_data[0].store(chm, memory_order_relaxed);
346 _kvs.store(kvs, memory_order_release);
349 cliffc_hashtable(int init_size) {
350 // Should initialize the CHM for the construction of the table
351 // For other CHM in kvs_data, they should be initialzed in resize()
352 // because the size is determined dynamically
353 kvs_data *kvs = new kvs_data(init_size);
354 void *chm = (void*) new CHM(0);
355 kvs->_data[0].store(chm, memory_order_relaxed);
356 _kvs.store(kvs, memory_order_release);
362 @Commit_point_set: Read_Val_Point1 | Read_Val_Point2 | Read_Val_Point3
365 @DefineVar: TypeV *_Old_Val = __map.get(key)
367 _equals_val(_Old_Val, __RET__)
370 shared_ptr<TypeV> get(TypeK& key) {
371 void *key_ptr = (void*) new TypeK(key);
372 slot *key_slot = new slot(false, shared_ptr<void>(key_ptr));
373 int fullhash = hash(key_slot);
374 slot *V = get_impl(this, _kvs, key_slot, fullhash);
375 if (V == NULL) return NULL;
376 assert (!is_prime(V));
377 return static_pointer_cast<TypeV>(V->_ptr);
383 @Commit_point_set: Write_Val_Point
386 # Remember this old value at checking point
387 @DefineVar: TypeV *_Old_Val = __map.get(key)
388 @Code: __map.put(key, &val);
390 _equals_val(__RET__, _Old_Val)
393 shared_ptr<TypeV> put(TypeK& key, TypeV& val) {
394 return putIfMatch(key, val, NO_MATCH_OLD);
399 @Interface: PutIfAbsent
401 Write_Val_Point | PutIfAbsent_Fail_Point
402 @Condition: __map.get(key) == NULL
404 COND_PutIfAbsentSucc :: __RET__ == NULL
407 @DefineVar: TypeV *_Old_Val = __map.get(key)
410 __map.put(key, &value);
412 COND_SAT ? __RET__ == NULL : _equals_val(_Old_Val, __RET__)
415 shared_ptr<TypeV> putIfAbsent(TypeK& key, TypeV& value) {
416 return putIfMatch(key, val, TOMBSTONE);
421 @Interface: RemoveAny
422 @Commit_point_set: Write_Val_Point
425 @DefineVar: TypeV *_Old_Val = __map.get(key)
426 @Code: __map.put(key, NULL);
428 _equals_val(__RET__, _Old_Val)
431 shared_ptr<TypeV> remove(TypeK& key) {
432 return putIfMatch(key, TOMBSTONE, NO_MATCH_OLD);
437 @Interface: RemoveIfMatch
439 Write_Val_Point | RemoveIfMatch_Fail_Point
441 _equals_val(__map.get(key), &val)
443 COND_RemoveIfMatchSucc :: __RET__ == true
448 __map.put(key, NULL);
450 COND_SAT ? __RET__ : !__RET__
453 bool remove(TypeK& key, TypeV& val) {
454 slot *val_slot = val == NULL ? NULL : new slot(false, val);
455 return putIfMatch(key, TOMBSTONE, val) == val;
461 @Interface: ReplaceAny
466 @DefineVar: TypeV *_Old_Val = __map.get(key)
468 _equals_val(__RET__, _Old_Val)
471 shared_ptr<TypeV> replace(TypeK& key, TypeV& val) {
472 return putIfMatch(key, val, MATCH_ANY);
477 @Interface: ReplaceIfMatch
479 Write_Val_Point | ReplaceIfMatch_Fail_Point
481 _equals_val(__map.get(key), &oldval)
483 COND_ReplaceIfMatchSucc :: __RET__ == true
488 __map.put(key, &newval);
490 COND_SAT ? __RET__ : !__RET__
493 bool replace(TypeK& key, TypeV& oldval, TypeV& newval) {
494 return putIfMatch(key, newval, oldval) == oldval;
498 static CHM* get_chm(kvs_data* kvs) {
499 return (CHM*) kvs->_data[0].load(memory_order_relaxed);
502 static int* get_hashes(kvs_data *kvs) {
503 return (int *) kvs->_data[1].load(memory_order_relaxed);
506 // Preserve happens-before semantics on newly inserted keys
507 static inline slot* key(kvs_data *kvs, int idx) {
508 assert (idx >= 0 && idx < kvs->_size);
509 // Corresponding to the volatile read in get_impl() and putIfMatch in
510 // Cliff Click's Java implementation
511 return (slot*) kvs->_data[idx * 2 + 2].load(memory_order_acquire);
515 The atomic operation in val() function is a "potential" commit point,
516 which means in some case it is a real commit point while it is not for
517 some other cases. This so happens because the val() function is such a
518 fundamental function that many internal operation will call. Our
519 strategy is that we label any potential commit points and check if they
520 really are the commit points later.
522 // Preserve happens-before semantics on newly inserted values
523 static inline slot* val(kvs_data *kvs, int idx) {
524 assert (idx >= 0 && idx < kvs->_size);
525 // Corresponding to the volatile read in get_impl() and putIfMatch in
526 // Cliff Click's Java implementation
527 slot *res = (slot*) kvs->_data[idx * 2 + 3].load(memory_order_acquire);
530 # This is a complicated potential commit point since many many functions are
532 @Potential_commit_point_define: true
533 @Label: Read_Val_Point
541 static int hash(slot *key_slot) {
542 assert(key_slot != NULL && key_slot->_ptr != NULL);
543 shared_ptr<TypeK> key = static_pointer_cast<TypeK>(key_slot->_ptr);
544 int h = key->hashCode();
545 // Spread bits according to Cliff Click's code
546 h += (h << 15) ^ 0xffffcd7d;
550 h += (h << 2) + (h << 14);
551 return h ^ (h >> 16);
554 // Heuristic to decide if reprobed too many times.
555 // Be careful here: Running over the limit on a 'get' acts as a 'miss'; on a
556 // put it triggers a table resize. Several places MUST have exact agreement.
557 static int reprobe_limit(int len) {
558 return REPROBE_LIMIT + (len >> 2);
561 static inline bool is_prime(slot *val) {
562 return (val != NULL) && val->_prime;
565 // Check for key equality. Try direct pointer comparison first (fast
566 // negative teset) and then the full 'equals' call
567 static bool keyeq(slot *K, slot *key_slot, int *hashes, int hash,
569 // Caller should've checked this.
571 shared_ptr<TypeK> key_ptr = static_pointer_cast<TypeK>(key_slot->_ptr);
574 ((hashes[hash] == 0 || hashes[hash] == fullhash) &&
576 key_ptr->equals(K->_ptr));
579 static bool valeq(slot *val_slot1, slot *val_slot2) {
580 assert (val_slot1 != NULL);
581 shared_ptr<TypeK> ptr1 = static_pointer_cast<TypeV>(val_slot1->_ptr);
582 if (val_slot2 == NULL || ptr1 == NULL) return false;
583 return ptr1->equals(val_slot2->_ptr);
586 // Together with key() preserve the happens-before relationship on newly
588 static inline bool CAS_key(kvs_data *kvs, int idx, void *expected, void *desired) {
589 return kvs->_data[2 * idx + 2].compare_exchange_strong(expected,
590 desired, memory_order_release, memory_order_release);
594 Same as the val() function, we only label the CAS operation as the
595 potential commit point.
597 // Together with val() preserve the happens-before relationship on newly
599 static inline bool CAS_val(kvs_data *kvs, int idx, void *expected, void
601 bool res = kvs->_data[2 * idx + 3].compare_exchange_strong(expected,
602 desired, memory_order_release, memory_order_release);
604 # If it is a successful put instead of a copy or any other internal
605 # operantions, expected != NULL
607 @Potential_commit_point_define: __ATOMIC_RET__ == true
608 @Label: Write_Val_Point
614 slot* get_impl(cliffc_hashtable *topmap, kvs_data *kvs, slot* key_slot, int
616 int len = kvs->_size;
617 CHM *chm = get_chm(kvs);
618 int *hashes = get_hashes(kvs);
620 int idx = fullhash & (len - 1);
623 slot *K = key(kvs, idx);
624 slot *V = val(kvs, idx);
627 @Commit_point_define: V == NULL
628 @Potential_commit_point_label: Read_Val_Point
629 @Label: Get_Success_Point_1
633 if (V == NULL) return NULL; // A miss
635 if (keyeq(K, key_slot, hashes, idx, fullhash)) {
636 // Key hit! Check if table-resize in progress
640 @Commit_point_define: true
641 @Potential_commit_point_label: Read_Val_Point
642 @Label: Get_Success_Point_2
645 return (V == TOMBSTONE) ? NULL : V; // Return this value
647 // Otherwise, finish the copy & retry in the new table
648 return get_impl(topmap, chm->copy_slot_and_check(topmap, kvs,
649 idx, key_slot), key_slot, fullhash);
652 if (++reprobe_cnt >= REPROBE_LIMIT ||
653 key_slot == TOMBSTONE) {
654 // Retry in new table
655 // Atomic read (acquire) can be here
656 kvs_data *newkvs = chm->_newkvs.load(memory_order_acquire);
659 @Commit_point_define_check: newkvs == NULL
660 @Label: Get_Success_Point_3
663 return newkvs == NULL ? NULL : get_impl(topmap,
664 topmap->help_copy(newkvs), key_slot, fullhash);
667 idx = (idx + 1) & (len - 1); // Reprobe by 1
671 // A wrapper of the essential function putIfMatch()
672 shared_ptr<TypeV> putIfMatch(TypeK& key, TypeV& value, slot *old_val) {
673 // TODO: Should throw an exception rather return NULL
674 if (old_val == NULL) {
677 void *key_ptr = (void*) new TypeK(key);
678 slot *key_slot = new slot(false, shared_ptr<void>(key_ptr));
680 void *val_ptr = (void*) new TypeV(value);
681 slot *value_slot = new slot(false, shared_ptr<void>(val_ptr));
682 slot *res = putIfMatch(this, _kvs, key_slot, value_slot, old_val);
683 // Only when copy_slot() call putIfMatch() will it return NULL
684 assert (res != NULL);
685 assert (!is_prime(res));
686 return res == TOMBSTONE ? NULL : static_pointer_cast<TypeV>(res->_ptr);
690 Put, Remove, PutIfAbsent, etc will call this function. Return the old
691 value. If the returned value is equals to the expVal (or expVal is
692 NO_MATCH_OLD), then this function puts the val_slot to the table 'kvs'.
693 Only copy_slot will pass a NULL expVal, and putIfMatch only returns a
694 NULL if passed a NULL expVal.
696 static slot* putIfMatch(cliffc_hashtable *topmap, kvs_data *kvs, slot
697 *key_slot, slot *val_slot, slot *expVal) {
698 assert (val_slot != NULL);
699 assert (!is_prime(val_slot));
700 assert (!is_prime(expVal));
702 int fullhash = hash(key_slot);
703 int len = kvs->_size;
704 CHM *chm = get_chm(kvs);
705 int *hashes = get_hashes(kvs);
706 int idx = fullhash & (len - 1);
714 while (true) { // Spin till we get a key slot
716 V = val(kvs, idx, NULL);
717 if (K == NULL) { // Get a free slot
718 if (val_slot == TOMBSTONE) return val_slot;
719 // Claim the null key-slot
720 if (CAS_key(kvs, idx, NULL, key_slot)) {
721 chm->_slots.fetch_add(1, memory_order_relaxed); // Inc key-slots-used count
722 hashes[idx] = fullhash; // Memorize full hash
725 K = key(kvs, idx); // CAS failed, get updated value
729 // Key slot not null, there exists a Key here
730 if (keyeq(K, key_slot, hashes, idx, fullhash))
733 // Notice that the logic here should be consistent with that of get.
734 // The first predicate means too many reprobes means nothing in the
736 if (++reprobe_cnt >= reprobe_limit(len) ||
737 K == TOMBSTONE) { // Found a Tombstone key, no more keys
738 newkvs = chm->resize(topmap, kvs);
739 // Help along an existing copy
740 if (expVal != NULL) topmap->help_copy(newkvs);
741 return putIfMatch(topmap, newkvs, key_slot, val_slot, expVal);
744 idx = (idx + 1) & (len - 1); // Reprobe
745 } // End of spinning till we get a Key slot
747 if (val_slot == V) return V; // Fast cutout for no-change
749 // Here it tries to resize cause it doesn't want other threads to stop
750 // its progress (eagerly try to resize soon)
751 newkvs = chm->_newkvs.load(memory_order_acquire);
752 if (newkvs == NULL &&
753 ((V == NULL && chm->table_full(reprobe_cnt, len)) || is_prime(V)))
754 newkvs = chm->resize(topmap, kvs); // Force the copy to start
756 // Finish the copy and then put it in the new table
758 return putIfMatch(topmap, chm->copy_slot_and_check(topmap, kvs, idx,
759 expVal), key_slot, val_slot, expVal);
761 // Decided to update the existing table
763 assert (!is_prime(V));
765 if (expVal != NO_MATCH_OLD &&
767 (expVal != MATCH_ANY || V == TOMBSTONE || V == NULL) &&
768 !(V == NULL && expVal == TOMBSTONE) &&
769 (expVal == NULL || !valeq(expVal, V))) {
772 @Commit_point_define: expVal == TOMBSTONE
773 @Potential_commit_point_label: Read_Val_Point
774 @Label: PutIfAbsent_Fail_Point
775 # This is a check for the PutIfAbsent() when the value
781 @Commit_point_define: expVal != NULL && val_slot == TOMBSTONE
782 @Potential_commit_point_label: Read_Val_Point
783 @Label: RemoveIfMatch_Fail_Point
788 @Commit_point_define: !valeq(expVal, V)
789 @Potential_commit_point_label: Read_Val_Point
790 @Label: ReplaceIfMatch_Fail_Point
793 return V; // Do not update!
796 if (CAS_val(kvs, idx, V, val_slot)) {
799 # The only point where a successful put happens
800 @Commit_point_define: true
801 @Potential_commit_point_label: Write_Val_Point
802 @Label: Write_Success_Point
805 if (expVal != NULL) { // Not called by a table-copy
806 // CAS succeeded, should adjust size
807 // Both normal put's and table-copy calls putIfMatch, but
808 // table-copy does not increase the number of live K/V pairs
809 if ((V == NULL || V == TOMBSTONE) &&
810 val_slot != TOMBSTONE)
811 chm->_size.fetch_add(1, memory_order_relaxed);
812 if (!(V == NULL || V == TOMBSTONE) &&
813 val_slot == TOMBSTONE)
814 chm->_size.fetch_add(-1, memory_order_relaxed);
816 return (V == NULL && expVal != NULL) ? TOMBSTONE : V;
819 V = val(kvs, idx, NULL);
821 return putIfMatch(topmap, chm->copy_slot_and_check(topmap, kvs,
822 idx, expVal), key_slot, val_slot, expVal);
826 // Help along an existing table-resize. This is a fast cut-out wrapper.
827 kvs_data* help_copy(kvs_data *helper) {
828 kvs_data *topkvs = _kvs.load(memory_order_acquire);
829 CHM *topchm = get_chm(topkvs);
830 // No cpy in progress
831 if (topchm->_newkvs.load(memory_order_acquire) == NULL) return helper;
832 topchm->help_copy_impl(this, topkvs, false);