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