1 /*
2 * Copyright (c) 2018, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_CONCURRENTHASHTABLE_HPP
26 #define SHARE_UTILITIES_CONCURRENTHASHTABLE_HPP
27
28 #include "memory/allocation.hpp"
29 #include "utilities/globalCounter.hpp"
30 #include "utilities/globalDefinitions.hpp"
31
32 // A mostly concurrent-hash-table where the read-side is wait-free, inserts are
33 // CAS and deletes mutual exclude each other on per bucket-basis. VALUE is the
34 // type kept inside each Node and CONFIG contains hash and allocation methods.
35 // A CALLBACK_FUNC and LOOKUP_FUNC needs to be provided for get and insert.
36
37 class Thread;
38 class Mutex;
39
40 template <typename VALUE, typename CONFIG, MEMFLAGS F>
41 class ConcurrentHashTable : public CHeapObj<F> {
42 private:
43 // This is the internal node structure.
44 // Only constructed with placement new from memory allocated with MEMFLAGS of
45 // the InternalTable or user-defined memory.
46 class Node {
47 private:
48 Node * volatile _next;
49 VALUE _value;
50 public:
51 Node(const VALUE& value, Node* next = NULL)
52 : _next(next), _value(value) {
53 assert((((uintptr_t)this) & ((uintptr_t)0x3)) == 0,
54 "Must 16 bit aligned.");
55 }
56
57 Node* next() const;
58 void set_next(Node* node) { _next = node; }
59 Node* const volatile * next_ptr() { return &_next; }
60
61 VALUE* value() { return &_value; }
62
63 // Creates a node.
64 static Node* create_node(const VALUE& value, Node* next = NULL) {
65 return new (CONFIG::allocate_node(sizeof(Node), value)) Node(value, next);
66 }
67 // Destroys a node.
68 static void destroy_node(Node* node) {
69 CONFIG::free_node((void*)node, node->_value);
70 }
71
72 void print_on(outputStream* st) const {};
73 void print_value_on(outputStream* st) const {};
74 };
75
76 // Only constructed with placement new from an array allocated with MEMFLAGS
77 // of InternalTable.
78 class Bucket {
79 private:
80
81 // Embedded state in two low bits in first pointer is a spinlock with 3
82 // states, unlocked, locked, redirect. You must never busy-spin on trylock()
83 // or call lock() without _resize_lock, that would deadlock. Redirect can
84 // only be installed by owner and is the final state of a bucket.
85 // The only two valid flows are:
86 // unlocked -> locked -> unlocked
87 // unlocked -> locked -> redirect
88 // Locked state only applies to an updater.
89 // Reader only check for redirect.
90 Node * volatile _first;
91
92 static const uintptr_t STATE_LOCK_BIT = 0x1;
93 static const uintptr_t STATE_REDIRECT_BIT = 0x2;
94 static const uintptr_t STATE_MASK = 0x3;
95
96 // Get the first pointer unmasked.
97 Node* first_raw() const;
98
99 // Methods to manipulate the embedded.
100 static bool is_state(Node* node, uintptr_t bits) {
101 return (bits & (uintptr_t)node) == bits;
102 }
103
104 static Node* set_state(Node* n, uintptr_t bits) {
105 return (Node*)(bits | (uintptr_t)n);
106 }
107
108 static uintptr_t get_state(Node* node) {
109 return (((uintptr_t)node) & STATE_MASK);
110 }
111
112 static Node* clear_state(Node* node) {
113 return (Node*)(((uintptr_t)node) & (~(STATE_MASK)));
114 }
115
116 static Node* clear_set_state(Node* node, Node* state) {
117 return (Node*)(((uintptr_t)clear_state(node)) ^ get_state(state));
118 }
119
120 public:
121 // A bucket is only one pointer with the embedded state.
122 Bucket() : _first(NULL) {};
123
124 // Get the first pointer unmasked.
125 Node* first() const;
126
127 // Get a pointer to the const first pointer. Do not deference this
128 // pointer, the pointer pointed to _may_ contain an embedded state. Such
129 // pointer should only be used as input to release_assign_node_ptr.
130 Node* const volatile * first_ptr() { return &_first; }
131
132 // This is the only place where a pointer to a Node pointer that potentially
133 // is _first should be changed. Otherwise we destroy the embedded state. We
134 // only give out pointer to const Node pointer to avoid accidental
135 // assignment, thus here we must cast const part away. Method is not static
136 // due to an assert.
137 void release_assign_node_ptr(Node* const volatile * dst, Node* node) const;
138
139 // This method assigns this buckets last Node next ptr to input Node.
140 void release_assign_last_node_next(Node* node);
141
142 // Setting the first pointer must be done with CAS.
143 bool cas_first(Node *node, Node* expect);
144
145 // Returns true if this bucket is redirecting to a new table.
146 // Redirect is a terminal state and will never change.
147 bool have_redirect() const;
148
149 // Return true if this bucket is locked for updates.
150 bool is_locked() const;
151
152 // Return true if this bucket was locked.
153 bool trylock();
154
155 // The bucket might be invalid, due to a concurrent resize. The lock()
156 // method do no respect that and can deadlock if caller do not hold
157 // _resize_lock.
158 void lock();
159
160 // Unlocks this bucket.
161 void unlock();
162
163 // Installs redirect in this bucket.
164 // Prior to doing so you must have successfully locked this bucket.
165 void redirect();
166 };
167
168 // The backing storage table holding the buckets and it's size and mask-bits.
169 // Table is always a power of two for two reasons:
170 // - Re-size can only change the size into half or double
171 // (any pow 2 would also be possible).
172 // - Use masking of hash for bucket index.
173 class InternalTable : public CHeapObj<F> {
174 private:
175 Bucket* _buckets; // Bucket array.
176 public:
177 const size_t _log2_size; // Size in log2.
178 const size_t _size; // Size in log10.
179
180 // The mask used on hash for selecting bucket.
181 // The masked value is guaranteed be to inside the buckets array.
182 const size_t _hash_mask;
183
184 // Create a backing table
185 InternalTable(size_t log2_size);
186 ~InternalTable();
187
188 Bucket* get_buckets() { return _buckets; }
189 Bucket* get_bucket(size_t idx) { return &_buckets[idx]; }
190 };
191
192 // Used as default functor when no functor supplied for some methods.
193 struct NoOp {
194 void operator()(VALUE*) {}
195 const VALUE& operator()() {}
196 void operator()(bool, VALUE*) {}
197 } noOp;
198
199 // For materializing a supplied value.
200 class LazyValueRetrieve {
201 private:
202 const VALUE& _val;
203 public:
204 LazyValueRetrieve(const VALUE& val) : _val(val) {}
205 const VALUE& operator()() { return _val; }
206 };
207
208 InternalTable* _table; // Active table.
209 InternalTable* _new_table; // Table we are resizing to.
210
211 // Default sizes
212 static const size_t DEFAULT_MAX_SIZE_LOG2 = 21;
213 static const size_t DEFAULT_START_SIZE_LOG2 = 13;
214 static const size_t DEFAULT_GROW_HINT = 4; // Chain length
215
216 const size_t _log2_size_limit; // The biggest size.
217 const size_t _log2_start_size; // Start size.
218 const size_t _grow_hint; // Number of linked items
219
220 volatile bool _size_limit_reached;
221
222 // We serialize resizers and other bulk operations which do not support
223 // concurrent resize with this lock.
224 Mutex* _resize_lock;
225 // Since we need to drop mutex for safepoints, but stop other threads from
226 // taking the mutex after a safepoint this bool is the actual state. After
227 // acquiring the mutex you must check if this is already locked. If so you
228 // must drop the mutex until the real lock holder grabs the mutex.
229 volatile Thread* _resize_lock_owner;
230
231 // Return true if lock mutex/state succeeded.
232 bool try_resize_lock(Thread* locker);
233 // Returns when both mutex and state are proper locked.
234 void lock_resize_lock(Thread* locker);
235 // Unlocks mutex and state.
236 void unlock_resize_lock(Thread* locker);
237
238 // This method sets the _invisible_epoch and do a write_synchronize.
239 // Subsequent calls check the state of _invisible_epoch and determine if the
240 // write_synchronize can be avoided. If not, it sets the _invisible_epoch
241 // again and do a write_synchronize.
242 void write_synchonize_on_visible_epoch(Thread* thread);
243 // To be-able to avoid write_synchronize in resize and other bulk operation,
244 // this field keep tracks if a version of the hash-table was ever been seen.
245 // We the working thread pointer as tag for debugging. The _invisible_epoch
246 // can only be used by the owner of _resize_lock.
247 volatile Thread* _invisible_epoch;
248
249 // Scoped critical section, which also handles the invisible epochs.
250 // An invisible epoch/version do not need a write_synchronize().
251 class ScopedCS: public StackObj {
252 protected:
253 Thread* _thread;
254 ConcurrentHashTable<VALUE, CONFIG, F>* _cht;
255 GlobalCounter::CSContext _cs_context;
256 public:
257 ScopedCS(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* cht);
258 ~ScopedCS();
259 };
260
261
262 // Max number of deletes in one bucket chain during bulk delete.
263 static const size_t BULK_DELETE_LIMIT = 256;
264
265 // Simple getters and setters for the internal table.
266 InternalTable* get_table() const;
267 InternalTable* get_new_table() const;
268 InternalTable* set_table_from_new();
269
270 // Destroys all nodes.
271 void free_nodes();
272
273 // Mask away high bits of hash.
274 static size_t bucket_idx_hash(InternalTable* table, const uintx hash) {
275 return ((size_t)hash) & table->_hash_mask;
276 }
277
278 // Returns bucket for hash for that internal table.
279 Bucket* get_bucket_in(InternalTable* table, const uintx hash) const {
280 size_t bucket_index = bucket_idx_hash(table, hash);
281 return table->get_bucket(bucket_index);
282 }
283
284 // Return correct bucket for reading and handles resizing.
285 Bucket* get_bucket(const uintx hash) const;
286
287 // Return correct bucket for updates and handles resizing.
288 Bucket* get_bucket_locked(Thread* thread, const uintx hash);
289
290 // Finds a node.
291 template <typename LOOKUP_FUNC>
292 Node* get_node(const Bucket* const bucket, LOOKUP_FUNC& lookup_f,
293 bool* have_dead, size_t* loops = NULL) const;
294
295 // Method for shrinking.
296 bool internal_shrink_prolog(Thread* thread, size_t log2_size);
297 void internal_shrink_epilog(Thread* thread);
298 void internal_shrink_range(Thread* thread, size_t start, size_t stop);
299 bool internal_shrink(Thread* thread, size_t size_limit_log2);
300
301 // Methods for growing.
302 bool unzip_bucket(Thread* thread, InternalTable* old_table,
303 InternalTable* new_table, size_t even_index,
304 size_t odd_index);
305 bool internal_grow_prolog(Thread* thread, size_t log2_size);
306 void internal_grow_epilog(Thread* thread);
307 void internal_grow_range(Thread* thread, size_t start, size_t stop);
308 bool internal_grow(Thread* thread, size_t log2_size);
309
310 // Get a value.
311 template <typename LOOKUP_FUNC>
312 VALUE* internal_get(Thread* thread, LOOKUP_FUNC& lookup_f,
313 bool* grow_hint = NULL);
314
315 // Plain insert.
316 template <typename LOOKUP_FUNC>
317 bool internal_insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value,
318 bool* grow_hint, bool* clean_hint);
319
320 // Returns true if an item matching LOOKUP_FUNC is removed.
321 // Calls DELETE_FUNC before destroying the node.
322 template <typename LOOKUP_FUNC, typename DELETE_FUNC>
323 bool internal_remove(Thread* thread, LOOKUP_FUNC& lookup_f,
324 DELETE_FUNC& delete_f);
325
326 // Visits nodes with FUNC.
327 template <typename FUNC>
328 static bool visit_nodes(Bucket* bucket, FUNC& visitor_f);
329
330 // During shrink/grow we cannot guarantee that we only visit nodes once, with
331 // current algorithm. To keep it simple caller will have locked
332 // _resize_lock.
333 template <typename FUNC>
334 void do_scan_locked(Thread* thread, FUNC& scan_f);
335
336 // Check for dead items in a bucket.
337 template <typename EVALUATE_FUNC>
338 size_t delete_check_nodes(Bucket* bucket, EVALUATE_FUNC& eval_f,
339 size_t num_del, Node** ndel);
340
341 // Check for dead items in this table. During shrink/grow we cannot guarantee
342 // that we only visit nodes once. To keep it simple caller will have locked
343 // _resize_lock.
344 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
345 void do_bulk_delete_locked(Thread* thread, EVALUATE_FUNC& eval_f
346 , DELETE_FUNC& del_f) {
347 do_bulk_delete_locked_for(thread, 0, _table->_size, eval_f, del_f);
348 }
349
350 // To have prefetching for a VALUE that is pointer during
351 // do_bulk_delete_locked, we have this helper classes. One for non-pointer
352 // case without prefect and one for pointer with prefect.
353 template <bool b, typename EVALUATE_FUNC>
354 struct HaveDeletables {
355 static bool have_deletable(Bucket* bucket, EVALUATE_FUNC& eval_f,
356 Bucket* prefetch_bucket);
357 };
358 template<typename EVALUATE_FUNC>
359 struct HaveDeletables<true, EVALUATE_FUNC> {
360 static bool have_deletable(Bucket* bucket, EVALUATE_FUNC& eval_f,
361 Bucket* prefetch_bucket);
362 };
363
364 // Check for dead items in this table with range. During shrink/grow we cannot
365 // guarantee that we only visit nodes once. To keep it simple caller will
366 // have locked _resize_lock.
367 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
368 void do_bulk_delete_locked_for(Thread* thread, size_t start_idx,
369 size_t stop_idx, EVALUATE_FUNC& eval_f,
370 DELETE_FUNC& del_f, bool is_mt = false);
371
372 // Method to delete one items.
373 template <typename LOOKUP_FUNC>
374 void delete_in_bucket(Thread* thread, Bucket* bucket, LOOKUP_FUNC& lookup_f);
375
376 public:
377 ConcurrentHashTable(size_t log2size = DEFAULT_START_SIZE_LOG2,
378 size_t log2size_limit = DEFAULT_MAX_SIZE_LOG2,
379 size_t grow_hint = DEFAULT_GROW_HINT);
380
381 ~ConcurrentHashTable();
382
383 size_t get_size_log2(Thread* thread);
384 size_t get_node_size() const { return sizeof(Node); }
385 bool is_max_size_reached() { return _size_limit_reached; }
386
387 // This means no paused bucket resize operation is going to resume
388 // on this table.
389 bool is_safepoint_safe() { return _resize_lock_owner == NULL; }
390
391 // Re-size operations.
392 bool shrink(Thread* thread, size_t size_limit_log2 = 0);
393 bool grow(Thread* thread, size_t size_limit_log2 = 0);
394
395 // All callbacks for get are under critical sections. Other callbacks may be
396 // under critical section or may have locked parts of table. Calling any
397 // methods on the table during a callback is not supported.Only MultiGetHandle
398 // supports multiple gets.
399
400 // Get methods return true on found item with LOOKUP_FUNC and FOUND_FUNC is
401 // called.
402 template <typename LOOKUP_FUNC, typename FOUND_FUNC>
403 bool get(Thread* thread, LOOKUP_FUNC& lookup_f, FOUND_FUNC& foundf,
404 bool* grow_hint = NULL);
405
406 // Returns true true if the item was inserted, duplicates are found with
407 // LOOKUP_FUNC.
408 template <typename LOOKUP_FUNC>
409 bool insert(Thread* thread, LOOKUP_FUNC& lookup_f, const VALUE& value,
410 bool* grow_hint = NULL, bool* clean_hint = NULL) {
411 return internal_insert(thread, lookup_f, value, grow_hint, clean_hint);
412 }
413
414 // This does a fast unsafe insert and can thus only be used when there is no
415 // risk for a duplicates and no other threads uses this table.
416 bool unsafe_insert(const VALUE& value);
417
418 // Returns true if items was deleted matching LOOKUP_FUNC and
419 // prior to destruction DELETE_FUNC is called.
420 template <typename LOOKUP_FUNC, typename DELETE_FUNC>
421 bool remove(Thread* thread, LOOKUP_FUNC& lookup_f, DELETE_FUNC& del_f) {
422 return internal_remove(thread, lookup_f, del_f);
423 }
424
425 // Same without DELETE_FUNC.
426 template <typename LOOKUP_FUNC>
427 bool remove(Thread* thread, LOOKUP_FUNC& lookup_f) {
428 return internal_remove(thread, lookup_f, noOp);
429 }
430
431 // Visit all items with SCAN_FUNC if no concurrent resize. Takes the resize
432 // lock to avoid concurrent resizes. Else returns false.
433 template <typename SCAN_FUNC>
434 bool try_scan(Thread* thread, SCAN_FUNC& scan_f);
435
436 // Visit all items with SCAN_FUNC when the resize lock is obtained.
437 template <typename SCAN_FUNC>
438 void do_scan(Thread* thread, SCAN_FUNC& scan_f);
439
440 // Visit all items with SCAN_FUNC without any protection.
441 // It will assume there is no other thread accessing this
442 // table during the safepoint. Must be called with VM thread.
443 template <typename SCAN_FUNC>
444 void do_safepoint_scan(SCAN_FUNC& scan_f);
445
446 // Destroying items matching EVALUATE_FUNC, before destroying items
447 // DELETE_FUNC is called, if resize lock is obtained. Else returns false.
448 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
449 bool try_bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f,
450 DELETE_FUNC& del_f);
451
452 // Destroying items matching EVALUATE_FUNC, before destroying items
453 // DELETE_FUNC is called, when the resize lock is successfully obtained.
454 template <typename EVALUATE_FUNC, typename DELETE_FUNC>
455 void bulk_delete(Thread* thread, EVALUATE_FUNC& eval_f, DELETE_FUNC& del_f);
456
457 // Writes statistics to the outputStream. Item sizes are calculated with
458 // VALUE_SIZE_FUNC.
459 template <typename VALUE_SIZE_FUNC>
460 void statistics_to(Thread* thread, VALUE_SIZE_FUNC& vs_f, outputStream* st,
461 const char* table_name);
462
463 // Moves all nodes from this table to to_cht
464 bool try_move_nodes_to(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* to_cht);
465
466 // This is a Curiously Recurring Template Pattern (CRPT) interface for the
467 // specialization.
468 struct BaseConfig {
469 public:
470 // Called when the hash table needs the hash for a VALUE.
471 static uintx get_hash(const VALUE& value, bool* dead) {
472 return CONFIG::get_hash(value, dead);
473 }
474 // Default node allocation.
475 static void* allocate_node(size_t size, const VALUE& value);
476 // Default node reclamation.
477 static void free_node(void* memory, const VALUE& value);
478 };
479
480 // Scoped multi getter.
481 class MultiGetHandle : private ScopedCS {
482 public:
483 MultiGetHandle(Thread* thread, ConcurrentHashTable<VALUE, CONFIG, F>* cht)
484 : ScopedCS(thread, cht) {}
485 // In the MultiGetHandle scope you can lookup items matching LOOKUP_FUNC.
486 // The VALUEs are safe as long as you never save the VALUEs outside the
487 // scope, e.g. after ~MultiGetHandle().
488 template <typename LOOKUP_FUNC>
489 VALUE* get(LOOKUP_FUNC& lookup_f, bool* grow_hint = NULL);
490 };
491
492 private:
493 class BucketsOperation;
494
495 public:
496 class BulkDeleteTask;
497 class GrowTask;
498 };
499
500 #endif // SHARE_UTILITIES_CONCURRENTHASHTABLE_HPP