23472
|
1 |
/*
|
|
2 |
* Copyright (c) 2014, 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_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
|
|
26 |
#define SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
|
|
27 |
|
|
28 |
#include "gc_implementation/g1/g1StringDedupStat.hpp"
|
|
29 |
#include "runtime/mutexLocker.hpp"
|
|
30 |
|
|
31 |
class G1StringDedupEntryCache;
|
30175
|
32 |
class G1StringDedupUnlinkOrOopsDoClosure;
|
23472
|
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(outputStream* st);
|
|
228 |
static void verify();
|
|
229 |
};
|
|
230 |
|
|
231 |
#endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
|