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