1 /*
2 * Copyright (c) 2017, 2018, Red Hat, Inc. All rights reserved.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 *
22 */
23
24 #ifndef SHARE_VM_GC_SHENANDOAHSTRDEDUPTABLE_HPP
25 #define SHARE_VM_GC_SHENANDOAHSTRDEDUPTABLE_HPP
26
27 #include "utilities/ostream.hpp"
28
29 class ShenandoahStrDedupEntry : public CHeapObj<mtGC> {
30 private:
31 ShenandoahStrDedupEntry* volatile _next;
32 unsigned int _hash;
33 typeArrayOop _obj;
34
35 public:
36 ShenandoahStrDedupEntry() : _next(NULL), _hash(0), _obj(NULL) {
37 }
38
39 ShenandoahStrDedupEntry* volatile next() {
40 return _next;
41 }
42
43 ShenandoahStrDedupEntry* volatile* next_addr() {
44 return &_next;
45 }
46
47 void set_next(ShenandoahStrDedupEntry* next) {
48 _next = next;
49 }
50
51 bool cas_set_next(ShenandoahStrDedupEntry* next);
52
53 unsigned int hash() const {
54 return _hash;
55 }
56
57 void set_hash(unsigned int hash) {
58 _hash = hash;
59 }
60
61 typeArrayOop obj() const {
62 return _obj;
63 }
64
65 typeArrayOop* obj_addr() {
66 return &_obj;
67 }
68
69 void set_obj(typeArrayOop obj) {
70 _obj = obj;
71 }
72
73 bool equals(typeArrayOop value, unsigned int hash) const {
74 return (hash == this->hash() &&
75 equals(value, obj()));
76 }
77
78 void do_oop(OopClosure* cl) {
79 oop* p = (oop*)obj_addr();
80 cl->do_oop(p);
81 }
82
83 private:
84 static bool equals(typeArrayOop value1, typeArrayOop value2) {
85 return (value1 == value2 ||
86 (value1->length() == value2->length() &&
87 (!memcmp(value1->base(T_CHAR),
88 value2->base(T_CHAR),
89 value1->length() * sizeof(jchar)))));
90 }
91 };
92
93 /* ShenandoahStringDedupTable:
94 * - Lookup and add are lock free
95 * - Cleanup, resize and rehash are at safepoints
96 */
97 class ShenandoahStrDedupTable : public CHeapObj<mtGC> {
98 friend class ShenandoahStrDedupTableUnlinkTask;
99 friend class ShenandoahStrDedupTableRehashTask;
100 friend class ShenandoahStrDedupShrinkTableTask;
101 friend class ShenandoahStrDedupExpandTableTask;
102
103 private:
104 ShenandoahStrDedupEntry* volatile * _buckets;
105 size_t _size;
106 volatile size_t _entries;
107
108 uintx _shrink_threshold;
109 uintx _grow_threshold;
110 bool _rehash_needed;
111
112 // The hash seed also dictates which hash function to use. A
113 // zero hash seed means we will use the Java compatible hash
114 // function (which doesn't use a seed), and a non-zero hash
115 // seed means we use the murmur3 hash function.
116 jint _hash_seed;
117
118 // Constants governing table resize/rehash/cache.
119 static const size_t _min_size;
120 static const size_t _max_size;
121 static const double _grow_load_factor;
122 static const double _shrink_load_factor;
123 static const uintx _rehash_multiple;
124 static const uintx _rehash_threshold;
125 static const double _max_cache_factor;
126
127 volatile size_t _claimed;
128 size_t _partition_size;
129
130 public:
131 ShenandoahStrDedupTable(size_t size = _min_size, jint hash_seed = 0);
132 ~ShenandoahStrDedupTable();
133
134 jint hash_seed() const { return _hash_seed; }
135 size_t size() const { return _size; }
136 bool need_rehash() const { return _rehash_needed; }
137 bool need_expand() const { return _entries >= _grow_threshold && size() < max_size(); }
138 bool need_shrink() const { return _entries <= _shrink_threshold && size() > min_size(); }
139
140 // parallel scanning the table
141 void clear_claimed();
142 size_t claim();
143 void parallel_oops_do(OopClosure* cl);
144
145 // For verification only
146 void oops_do_slow(OopClosure* cl);
147
148 bool deduplicate(oop java_string);
149
150 // Returns an existing character array in the table, or inserts a new
151 // table entry if no matching character array exists.
152 typeArrayOop lookup_or_add(typeArrayOop value, unsigned int hash, uintx& count);
153
154 void print_statistics(outputStream* out) const;
155
156 static size_t min_size() { return _min_size; }
157 static size_t max_size() { return _max_size; }
158
159 void verify() PRODUCT_RETURN;
160
161 private:
162 inline bool use_java_hash() {
163 return _hash_seed == 0;
164 }
165
166 // Returns the hash bucket index for the given hash code.
167 size_t hash_to_index(unsigned int hash) {
168 return (size_t)hash & (size() - 1);
169 }
170
171 ShenandoahStrDedupEntry* volatile * bucket_addr(size_t index) const {
172 assert(index < size(), "Index out of bound");
173 return &_buckets[index];
174 }
175
176 // Returns the hash bucket at the given index.
177 ShenandoahStrDedupEntry* volatile bucket(size_t index) const {
178 assert(index < size(), "Index out of bound");
179 return _buckets[index];
180 }
181
182 size_t partition_size() const { return _partition_size; }
183
184 ShenandoahStrDedupEntry* allocate_entry(typeArrayOop value, unsigned int hash);
185 void release_entry(ShenandoahStrDedupEntry* entry);
186
187 unsigned int hash_code(oop java_string, typeArrayOop value);
188 unsigned int java_hash_code(typeArrayOop value);
189 unsigned int alt_hash_code(typeArrayOop value);
190
191 // Adds a new table entry to the given hash bucket.
192 void add(ShenandoahStrDedupEntry* entry);
193
194 // Clean up a bucket, return number of entries removed
195 size_t cleanup_bucket(size_t index);
196 };
197
198 class ShenandoahHeap;
199
200 class ShenandoahStrDedupTableCleanupTask : public CHeapObj<mtGC> {
201 private:
202 ShenandoahMarkingContext* const _mark_context;
203
204 public:
205 ShenandoahStrDedupTableCleanupTask();
206 virtual ~ShenandoahStrDedupTableCleanupTask() {};
207 virtual void do_parallel_cleanup() = 0;
208
209 protected:
210 bool is_alive(oop obj) const;
211 };
212
213 // Cleanup current string dedup table, remove all dead entries
214 class ShenandoahStrDedupTableUnlinkTask : public ShenandoahStrDedupTableCleanupTask {
215 private:
216 ShenandoahStrDedupTable* const _table;
217
218 public:
219 ShenandoahStrDedupTableUnlinkTask(ShenandoahStrDedupTable* const table);
220 void do_parallel_cleanup();
221 };
222
223 // The task transfers live entries from source table to destination table
224 class ShenandoahStrDedupTableRemapTask : public ShenandoahStrDedupTableCleanupTask {
225 protected:
226 ShenandoahStrDedupTable* const _src_table;
227 ShenandoahStrDedupTable* const _dest_table;
228
229 public:
230 ShenandoahStrDedupTableRemapTask(ShenandoahStrDedupTable* const src,
231 ShenandoahStrDedupTable* const dest);
232 protected:
233 ShenandoahStrDedupTable* const src_table() const { return _src_table; }
234 ShenandoahStrDedupTable* const dest_table() const { return _dest_table; }
235 };
236
237 // The task rehashes live entries from source table to destination table.
238 // Source and destination tables are not necessary the same size.
239 class ShenandoahStrDedupTableRehashTask : public ShenandoahStrDedupTableRemapTask {
240 public:
241 ShenandoahStrDedupTableRehashTask(ShenandoahStrDedupTable* const src,
242 ShenandoahStrDedupTable* const dest);
243 void do_parallel_cleanup();
244 };
245
246 /* The task remaps live entries from source table into destination table of
247 * the half size.
248 * Hash function should *not* be changed during shrinking of the table,
249 * so we can merge buckets from source table into destination table.
250 * bucket [index ] and bucket [index + half_table_size] -> bucket [index]
251 */
252 class ShenandoahStrDedupShrinkTableTask : public ShenandoahStrDedupTableRemapTask {
253 public:
254 ShenandoahStrDedupShrinkTableTask(ShenandoahStrDedupTable* const src,
255 ShenandoahStrDedupTable* const dest);
256 void do_parallel_cleanup();
257
258 protected:
259 size_t transfer_bucket(ShenandoahStrDedupEntry* volatile src,
260 ShenandoahStrDedupEntry* volatile * dest);
261 };
262
263 /* The task remaps live entries from source table into destination table of
264 * twice the size.
265 * Hash function should *not* be changed during shrinking of the table,
266 * so we can split buckets from source table into destination table.
267 * bucket [index ] -> bucket [index] or bucket [index + half_table_size]
268 */
269 class ShenandoahStrDedupExpandTableTask : public ShenandoahStrDedupTableRemapTask {
270 private:
271 int _bit_mask;
272
273 public:
274 ShenandoahStrDedupExpandTableTask(ShenandoahStrDedupTable* const src,
275 ShenandoahStrDedupTable* const dest);
276 void do_parallel_cleanup();
277
278 protected:
279 size_t split_bucket(ShenandoahStrDedupEntry* volatile src,
280 ShenandoahStrDedupEntry* volatile * dest_low,
281 ShenandoahStrDedupEntry* volatile * dest_high);
282 };
283
284 #endif // SHARE_VM_GC_SHENANDOAHSTRDEDUPTABLE_HPP