1/*
2 * Copyright (c) 2014, 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_GC_SHARED_STRINGDEDUP_STRINGDEDUPTABLE_HPP
26#define SHARE_GC_SHARED_STRINGDEDUP_STRINGDEDUPTABLE_HPP
27
28#include "gc/shared/stringdedup/stringDedupStat.hpp"
29#include "runtime/mutexLocker.hpp"
30
31class StringDedupEntryCache;
32class StringDedupUnlinkOrOopsDoClosure;
33
34//
35// Table entry in the deduplication hashtable. Points weakly to the
36// character array. Can be chained in a linked list in case of hash
37// collisions or when placed in a freelist in the entry cache.
38//
39class StringDedupEntry : public CHeapObj<mtGC> {
40private:
41 StringDedupEntry* _next;
42 unsigned int _hash;
43 bool _latin1;
44 typeArrayOop _obj;
45
46public:
47 StringDedupEntry() :
48 _next(NULL),
49 _hash(0),
50 _latin1(false),
51 _obj(NULL) {
52 }
53
54 StringDedupEntry* next() {
55 return _next;
56 }
57
58 StringDedupEntry** next_addr() {
59 return &_next;
60 }
61
62 void set_next(StringDedupEntry* next) {
63 _next = next;
64 }
65
66 unsigned int hash() {
67 return _hash;
68 }
69
70 void set_hash(unsigned int hash) {
71 _hash = hash;
72 }
73
74 bool latin1() {
75 return _latin1;
76 }
77
78 void set_latin1(bool latin1) {
79 _latin1 = latin1;
80 }
81
82 typeArrayOop obj() {
83 return _obj;
84 }
85
86 typeArrayOop* obj_addr() {
87 return &_obj;
88 }
89
90 void set_obj(typeArrayOop obj) {
91 _obj = obj;
92 }
93};
94
95//
96// The deduplication hashtable keeps track of all unique character arrays used
97// by String objects. Each table entry weakly points to an character array, allowing
98// otherwise unreachable character arrays to be declared dead and pruned from the
99// table.
100//
101// The table is dynamically resized to accommodate the current number of table entries.
102// The table has hash buckets with chains for hash collision. If the average chain
103// length goes above or below given thresholds the table grows or shrinks accordingly.
104//
105// The table is also dynamically rehashed (using a new hash seed) if it becomes severely
106// unbalanced, i.e., a hash chain is significantly longer than average.
107//
108// All access to the table is protected by the StringDedupTable_lock, except under
109// safepoints in which case GC workers are allowed to access a table partitions they
110// have claimed without first acquiring the lock. Note however, that this applies only
111// the table partition (i.e. a range of elements in _buckets), not other parts of the
112// table such as the _entries field, statistics counters, etc.
113//
114class StringDedupTable : public CHeapObj<mtGC> {
115private:
116 // The currently active hashtable instance. Only modified when
117 // the table is resizes or rehashed.
118 static StringDedupTable* _table;
119
120 // Cache for reuse and fast alloc/free of table entries.
121 static StringDedupEntryCache* _entry_cache;
122
123 StringDedupEntry** _buckets;
124 size_t _size;
125 uintx _entries;
126 uintx _shrink_threshold;
127 uintx _grow_threshold;
128 bool _rehash_needed;
129
130 // The hash seed also dictates which hash function to use. A
131 // zero hash seed means we will use the Java compatible hash
132 // function (which doesn't use a seed), and a non-zero hash
133 // seed means we use the murmur3 hash function.
134 jint _hash_seed;
135
136 // Constants governing table resize/rehash/cache.
137 static const size_t _min_size;
138 static const size_t _max_size;
139 static const double _grow_load_factor;
140 static const double _shrink_load_factor;
141 static const uintx _rehash_multiple;
142 static const uintx _rehash_threshold;
143 static const double _max_cache_factor;
144
145 // Table statistics, only used for logging.
146 static uintx _entries_added;
147 static uintx _entries_removed;
148 static uintx _resize_count;
149 static uintx _rehash_count;
150
151 static volatile size_t _claimed_index;
152
153 static StringDedupTable* _resized_table;
154 static StringDedupTable* _rehashed_table;
155
156 StringDedupTable(size_t size, jint hash_seed = 0);
157 ~StringDedupTable();
158
159 // Returns the hash bucket at the given index.
160 StringDedupEntry** bucket(size_t index) {
161 return _buckets + index;
162 }
163
164 // Returns the hash bucket index for the given hash code.
165 size_t hash_to_index(unsigned int hash) {
166 return (size_t)hash & (_size - 1);
167 }
168
169 // Adds a new table entry to the given hash bucket.
170 void add(typeArrayOop value, bool latin1, unsigned int hash, StringDedupEntry** list);
171
172 // Removes the given table entry from the table.
173 void remove(StringDedupEntry** pentry, uint worker_id);
174
175 // Transfers a table entry from the current table to the destination table.
176 void transfer(StringDedupEntry** pentry, StringDedupTable* dest);
177
178 // Returns an existing character array in the given hash bucket, or NULL
179 // if no matching character array exists.
180 typeArrayOop lookup(typeArrayOop value, bool latin1, unsigned int hash,
181 StringDedupEntry** list, uintx &count);
182
183 // Returns an existing character array in the table, or inserts a new
184 // table entry if no matching character array exists.
185 typeArrayOop lookup_or_add_inner(typeArrayOop value, bool latin1, unsigned int hash);
186
187 // Thread safe lookup or add of table entry
188 static typeArrayOop lookup_or_add(typeArrayOop value, bool latin1, unsigned int hash) {
189 // Protect the table from concurrent access. Also note that this lock
190 // acts as a fence for _table, which could have been replaced by a new
191 // instance if the table was resized or rehashed.
192 MutexLocker ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
193 return _table->lookup_or_add_inner(value, latin1, hash);
194 }
195
196 // Returns true if the hashtable is currently using a Java compatible
197 // hash function.
198 static bool use_java_hash() {
199 return _table->_hash_seed == 0;
200 }
201
202 // Computes the hash code for the given character array, using the
203 // currently active hash function and hash seed.
204 static unsigned int hash_code(typeArrayOop value, bool latin1);
205
206 static uintx unlink_or_oops_do(StringDedupUnlinkOrOopsDoClosure* cl,
207 size_t partition_begin,
208 size_t partition_end,
209 uint worker_id);
210
211 static size_t claim_table_partition(size_t partition_size);
212
213 static bool is_resizing();
214 static bool is_rehashing();
215
216 // If a table resize is needed, returns a newly allocated empty
217 // hashtable of the proper size.
218 static StringDedupTable* prepare_resize();
219
220 // Installs a newly resized table as the currently active table
221 // and deletes the previously active table.
222 static void finish_resize(StringDedupTable* resized_table);
223
224 // If a table rehash is needed, returns a newly allocated empty
225 // hashtable and updates the hash seed.
226 static StringDedupTable* prepare_rehash();
227
228 // Transfers rehashed entries from the currently active table into
229 // the new table. Installs the new table as the currently active table
230 // and deletes the previously active table.
231 static void finish_rehash(StringDedupTable* rehashed_table);
232
233public:
234 static void create();
235
236 // Deduplicates the given String object, or adds its backing
237 // character array to the deduplication hashtable.
238 static void deduplicate(oop java_string, StringDedupStat* stat);
239
240 static void unlink_or_oops_do(StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id);
241
242 static void print_statistics();
243 static void verify();
244
245 // If the table entry cache has grown too large, delete overflowed entries.
246 static void clean_entry_cache();
247
248 // GC support
249 static void gc_prologue(bool resize_and_rehash_table);
250 static void gc_epilogue();
251};
252
253#endif // SHARE_GC_SHARED_STRINGDEDUP_STRINGDEDUPTABLE_HPP
254