Mercurial > hg > truffle
annotate src/share/vm/utilities/hashtable.cpp @ 6862:8a5ea0a9ccc4
7127708: G1: change task num types from int to uint in concurrent mark
Summary: Change the type of various task num fields, parameters etc to unsigned and rename them to be more consistent with the other collectors. Code changes were also reviewed by Vitaly Davidovich.
Reviewed-by: johnc
Contributed-by: Kaushik Srenevasan <kaushik@twitter.com>
author | johnc |
---|---|
date | Sat, 06 Oct 2012 01:17:44 -0700 |
parents | da91efe96a93 |
children | a5d6f0c3585f |
rev | line source |
---|---|
0 | 1 /* |
6162 | 2 * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
470
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
470
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
470
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
1972 | 25 #include "precompiled.hpp" |
6201
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
26 #include "classfile/altHashing.hpp" |
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
27 #include "classfile/javaClasses.hpp" |
1972 | 28 #include "memory/allocation.inline.hpp" |
6172
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
29 #include "memory/filemap.hpp" |
1972 | 30 #include "memory/resourceArea.hpp" |
31 #include "oops/oop.inline.hpp" | |
32 #include "runtime/safepoint.hpp" | |
33 #include "utilities/dtrace.hpp" | |
34 #include "utilities/hashtable.hpp" | |
35 #include "utilities/hashtable.inline.hpp" | |
0 | 36 |
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
37 |
0 | 38 // This is a generic hashtable, designed to be used for the symbol |
39 // and string tables. | |
40 // | |
41 // It is implemented as an open hash table with a fixed number of buckets. | |
42 // | |
43 // %note: | |
44 // - HashtableEntrys are allocated in blocks to reduce the space overhead. | |
45 | |
6197 | 46 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) { |
47 BasicHashtableEntry<F>* entry; | |
0 | 48 |
49 if (_free_list) { | |
50 entry = _free_list; | |
51 _free_list = _free_list->next(); | |
52 } else { | |
432 | 53 if (_first_free_entry + _entry_size >= _end_block) { |
54 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries)); | |
0 | 55 int len = _entry_size * block_size; |
432 | 56 len = 1 << log2_intptr(len); // round down to power of 2 |
57 assert(len >= _entry_size, ""); | |
6197 | 58 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC); |
0 | 59 _end_block = _first_free_entry + len; |
60 } | |
6197 | 61 entry = (BasicHashtableEntry<F>*)_first_free_entry; |
0 | 62 _first_free_entry += _entry_size; |
63 } | |
64 | |
432 | 65 assert(_entry_size % HeapWordSize == 0, ""); |
0 | 66 entry->set_hash(hashValue); |
67 return entry; | |
68 } | |
69 | |
70 | |
6197 | 71 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) { |
72 HashtableEntry<T, F>* entry; | |
0 | 73 |
6197 | 74 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue); |
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
75 entry->set_literal(obj); |
0 | 76 return entry; |
77 } | |
78 | |
6162 | 79 // Check to see if the hashtable is unbalanced. The caller set a flag to |
80 // rehash at the next safepoint. If this bucket is 60 times greater than the | |
81 // expected average bucket length, it's an unbalanced hashtable. | |
82 // This is somewhat an arbitrary heuristic but if one bucket gets to | |
83 // rehash_count which is currently 100, there's probably something wrong. | |
84 | |
6197 | 85 template <MEMFLAGS F> bool BasicHashtable<F>::check_rehash_table(int count) { |
6162 | 86 assert(table_size() != 0, "underflow"); |
87 if (count > (((double)number_of_entries()/(double)table_size())*rehash_multiple)) { | |
88 // Set a flag for the next safepoint, which should be at some guaranteed | |
89 // safepoint interval. | |
90 return true; | |
91 } | |
92 return false; | |
93 } | |
94 | |
6201
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
95 template <class T, MEMFLAGS F> jint Hashtable<T, F>::_seed = 0; |
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
96 |
6162 | 97 // Create a new table and using alternate hash code, populate the new table |
98 // with the existing elements. This can be used to change the hash code | |
99 // and could in the future change the size of the table. | |
100 | |
6197 | 101 template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) { |
6201
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
102 |
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
103 // Initialize the global seed for hashing. |
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
104 _seed = AltHashing::compute_seed(); |
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
105 assert(seed() != 0, "shouldn't be zero"); |
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
106 |
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
107 int saved_entry_count = this->number_of_entries(); |
6162 | 108 |
109 // Iterate through the table and create a new entry for the new table | |
110 for (int i = 0; i < new_table->table_size(); ++i) { | |
6197 | 111 for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) { |
112 HashtableEntry<T, F>* next = p->next(); | |
6162 | 113 T string = p->literal(); |
114 // Use alternate hashing algorithm on the symbol in the first table | |
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
115 unsigned int hashValue = string->new_hash(seed()); |
6162 | 116 // Get a new index relative to the new table (can also change size) |
117 int index = new_table->hash_to_index(hashValue); | |
118 p->set_hash(hashValue); | |
6172
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
119 // Keep the shared bit in the Hashtable entry to indicate that this entry |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
120 // can't be deleted. The shared bit is the LSB in the _next field so |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
121 // walking the hashtable past these entries requires |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
122 // BasicHashtableEntry::make_ptr() call. |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
123 bool keep_shared = p->is_shared(); |
6260
5e2dc722e70d
7186278: Build error after CR#6995781 / 7151532 with GCC 4.7.0
andrew
parents:
6201
diff
changeset
|
124 this->unlink_entry(p); |
6162 | 125 new_table->add_entry(index, p); |
6172
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
126 if (keep_shared) { |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
127 p->set_shared(); |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
128 } |
6162 | 129 p = next; |
130 } | |
131 } | |
132 // give the new table the free list as well | |
133 new_table->copy_freelist(this); | |
134 assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?"); | |
135 | |
136 // Destroy memory used by the buckets in the hashtable. The memory | |
137 // for the elements has been used in a new table and is not | |
138 // destroyed. The memory reuse will benefit resizing the SystemDictionary | |
139 // to avoid a memory allocation spike at safepoint. | |
6197 | 140 BasicHashtable<F>::free_buckets(); |
6162 | 141 } |
142 | |
6197 | 143 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() { |
6172
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
144 if (NULL != _buckets) { |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
145 // Don't delete the buckets in the shared space. They aren't |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
146 // allocated by os::malloc |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
147 if (!UseSharedSpaces || |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
148 !FileMapInfo::current_info()->is_in_shared_space(_buckets)) { |
6197 | 149 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets, F); |
6172
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
150 } |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
151 _buckets = NULL; |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
152 } |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
153 } |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
154 |
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
155 |
0 | 156 // Reverse the order of elements in the hash buckets. |
157 | |
6197 | 158 template <MEMFLAGS F> void BasicHashtable<F>::reverse() { |
0 | 159 |
160 for (int i = 0; i < _table_size; ++i) { | |
6197 | 161 BasicHashtableEntry<F>* new_list = NULL; |
162 BasicHashtableEntry<F>* p = bucket(i); | |
0 | 163 while (p != NULL) { |
6197 | 164 BasicHashtableEntry<F>* next = p->next(); |
0 | 165 p->set_next(new_list); |
166 new_list = p; | |
167 p = next; | |
168 } | |
169 *bucket_addr(i) = new_list; | |
170 } | |
171 } | |
172 | |
173 | |
174 // Copy the table to the shared space. | |
175 | |
6197 | 176 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) { |
0 | 177 |
178 // Dump the hash table entries. | |
179 | |
180 intptr_t *plen = (intptr_t*)(*top); | |
181 *top += sizeof(*plen); | |
182 | |
183 int i; | |
184 for (i = 0; i < _table_size; ++i) { | |
6197 | 185 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr(); |
0 | 186 *p != NULL; |
187 p = (*p)->next_addr()) { | |
188 if (*top + entry_size() > end) { | |
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
189 report_out_of_shared_space(SharedMiscData); |
0 | 190 } |
6197 | 191 *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size()); |
0 | 192 *top += entry_size(); |
193 } | |
194 } | |
195 *plen = (char*)(*top) - (char*)plen - sizeof(*plen); | |
196 | |
197 // Set the shared bit. | |
198 | |
199 for (i = 0; i < _table_size; ++i) { | |
6197 | 200 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) { |
0 | 201 p->set_shared(); |
202 } | |
203 } | |
204 } | |
205 | |
206 | |
207 | |
208 // Reverse the order of elements in the hash buckets. | |
209 | |
6197 | 210 template <class T, MEMFLAGS F> void Hashtable<T, F>::reverse(void* boundary) { |
0 | 211 |
6197 | 212 for (int i = 0; i < this->table_size(); ++i) { |
213 HashtableEntry<T, F>* high_list = NULL; | |
214 HashtableEntry<T, F>* low_list = NULL; | |
215 HashtableEntry<T, F>* last_low_entry = NULL; | |
216 HashtableEntry<T, F>* p = bucket(i); | |
0 | 217 while (p != NULL) { |
6197 | 218 HashtableEntry<T, F>* next = p->next(); |
0 | 219 if ((void*)p->literal() >= boundary) { |
220 p->set_next(high_list); | |
221 high_list = p; | |
222 } else { | |
223 p->set_next(low_list); | |
224 low_list = p; | |
225 if (last_low_entry == NULL) { | |
226 last_low_entry = p; | |
227 } | |
228 } | |
229 p = next; | |
230 } | |
231 if (low_list != NULL) { | |
232 *bucket_addr(i) = low_list; | |
233 last_low_entry->set_next(high_list); | |
234 } else { | |
235 *bucket_addr(i) = high_list; | |
236 } | |
237 } | |
238 } | |
239 | |
240 | |
241 // Dump the hash table buckets. | |
242 | |
6197 | 243 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) { |
244 intptr_t len = _table_size * sizeof(HashtableBucket<F>); | |
0 | 245 *(intptr_t*)(*top) = len; |
246 *top += sizeof(intptr_t); | |
247 | |
248 *(intptr_t*)(*top) = _number_of_entries; | |
249 *top += sizeof(intptr_t); | |
250 | |
251 if (*top + len > end) { | |
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
252 report_out_of_shared_space(SharedMiscData); |
0 | 253 } |
6197 | 254 _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len); |
0 | 255 *top += len; |
256 } | |
257 | |
258 | |
259 #ifndef PRODUCT | |
260 | |
6197 | 261 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() { |
0 | 262 ResourceMark rm; |
263 | |
6197 | 264 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) { |
265 HashtableEntry<T, F>* entry = bucket(i); | |
0 | 266 while(entry != NULL) { |
267 tty->print("%d : ", i); | |
268 entry->literal()->print(); | |
269 tty->cr(); | |
270 entry = entry->next(); | |
271 } | |
272 } | |
273 } | |
274 | |
275 | |
6197 | 276 template <MEMFLAGS F> void BasicHashtable<F>::verify() { |
0 | 277 int count = 0; |
278 for (int i = 0; i < table_size(); i++) { | |
6197 | 279 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) { |
0 | 280 ++count; |
281 } | |
282 } | |
283 assert(count == number_of_entries(), "number of hashtable entries incorrect"); | |
284 } | |
285 | |
286 | |
287 #endif // PRODUCT | |
288 | |
289 | |
290 #ifdef ASSERT | |
291 | |
6197 | 292 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) { |
0 | 293 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) { |
294 warning("Performance bug: SystemDictionary lookup_count=%d " | |
295 "lookup_length=%d average=%lf load=%f", | |
296 _lookup_count, _lookup_length, | |
297 (double) _lookup_length / _lookup_count, load); | |
298 } | |
299 } | |
300 | |
301 #endif | |
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
302 // Explicitly instantiate these types |
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
303 template class Hashtable<ConstantPool*, mtClass>; |
6197 | 304 template class Hashtable<Symbol*, mtSymbol>; |
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
305 template class Hashtable<Klass*, mtClass>; |
6197 | 306 template class Hashtable<oop, mtClass>; |
307 #ifdef SOLARIS | |
308 template class Hashtable<oop, mtSymbol>; | |
309 #endif | |
310 template class Hashtable<oopDesc*, mtSymbol>; | |
311 template class Hashtable<Symbol*, mtClass>; | |
312 template class HashtableEntry<Symbol*, mtSymbol>; | |
313 template class HashtableEntry<Symbol*, mtClass>; | |
314 template class HashtableEntry<oop, mtSymbol>; | |
315 template class BasicHashtableEntry<mtSymbol>; | |
316 template class BasicHashtableEntry<mtCode>; | |
317 template class BasicHashtable<mtClass>; | |
318 template class BasicHashtable<mtSymbol>; | |
319 template class BasicHashtable<mtCode>; | |
320 template class BasicHashtable<mtInternal>; |