Wed, 04 Jul 2012 15:55:45 -0400
7181200: JVM new hashing code breaks SA in product mode
Summary: Made new_hash() overloaded rather than a virtual function so SA code doesn't need to be changed.
Reviewed-by: kvn, acorn, dholmes, fparain
1 /*
2 * Copyright (c) 2003, 2012, 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 */
25 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp"
27 #include "classfile/javaClasses.hpp"
28 #include "memory/allocation.inline.hpp"
29 #include "memory/filemap.hpp"
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"
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.
46 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
47 BasicHashtableEntry<F>* entry;
49 if (_free_list) {
50 entry = _free_list;
51 _free_list = _free_list->next();
52 } else {
53 if (_first_free_entry + _entry_size >= _end_block) {
54 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
55 int len = _entry_size * block_size;
56 len = 1 << log2_intptr(len); // round down to power of 2
57 assert(len >= _entry_size, "");
58 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
59 _end_block = _first_free_entry + len;
60 }
61 entry = (BasicHashtableEntry<F>*)_first_free_entry;
62 _first_free_entry += _entry_size;
63 }
65 assert(_entry_size % HeapWordSize == 0, "");
66 entry->set_hash(hashValue);
67 return entry;
68 }
71 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
72 HashtableEntry<T, F>* entry;
74 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
75 entry->set_literal(obj);
76 return entry;
77 }
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.
85 template <MEMFLAGS F> bool BasicHashtable<F>::check_rehash_table(int count) {
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 }
95 template <class T, MEMFLAGS F> jint Hashtable<T, F>::_seed = 0;
97 template <class T, MEMFLAGS F> unsigned int Hashtable<T, F>::new_hash(Symbol* sym) {
98 ResourceMark rm;
99 // Use alternate hashing algorithm on this symbol.
100 return AltHashing::murmur3_32(seed(), (const jbyte*)sym->as_C_string(), sym->utf8_length());
101 }
103 template <class T, MEMFLAGS F> unsigned int Hashtable<T, F>::new_hash(oop string) {
104 ResourceMark rm;
105 int length;
106 jchar* chars = java_lang_String::as_unicode_string(string, length);
107 // Use alternate hashing algorithm on the string
108 return AltHashing::murmur3_32(seed(), chars, length);
109 }
111 // Create a new table and using alternate hash code, populate the new table
112 // with the existing elements. This can be used to change the hash code
113 // and could in the future change the size of the table.
115 template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) {
117 // Initialize the global seed for hashing.
118 _seed = AltHashing::compute_seed();
119 assert(seed() != 0, "shouldn't be zero");
121 int saved_entry_count = this->number_of_entries();
123 // Iterate through the table and create a new entry for the new table
124 for (int i = 0; i < new_table->table_size(); ++i) {
125 for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) {
126 HashtableEntry<T, F>* next = p->next();
127 T string = p->literal();
128 // Use alternate hashing algorithm on the symbol in the first table
129 unsigned int hashValue = new_hash(string);
130 // Get a new index relative to the new table (can also change size)
131 int index = new_table->hash_to_index(hashValue);
132 p->set_hash(hashValue);
133 // Keep the shared bit in the Hashtable entry to indicate that this entry
134 // can't be deleted. The shared bit is the LSB in the _next field so
135 // walking the hashtable past these entries requires
136 // BasicHashtableEntry::make_ptr() call.
137 bool keep_shared = p->is_shared();
138 unlink_entry(p);
139 new_table->add_entry(index, p);
140 if (keep_shared) {
141 p->set_shared();
142 }
143 p = next;
144 }
145 }
146 // give the new table the free list as well
147 new_table->copy_freelist(this);
148 assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?");
150 // Destroy memory used by the buckets in the hashtable. The memory
151 // for the elements has been used in a new table and is not
152 // destroyed. The memory reuse will benefit resizing the SystemDictionary
153 // to avoid a memory allocation spike at safepoint.
154 BasicHashtable<F>::free_buckets();
155 }
157 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
158 if (NULL != _buckets) {
159 // Don't delete the buckets in the shared space. They aren't
160 // allocated by os::malloc
161 if (!UseSharedSpaces ||
162 !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {
163 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets, F);
164 }
165 _buckets = NULL;
166 }
167 }
170 // Reverse the order of elements in the hash buckets.
172 template <MEMFLAGS F> void BasicHashtable<F>::reverse() {
174 for (int i = 0; i < _table_size; ++i) {
175 BasicHashtableEntry<F>* new_list = NULL;
176 BasicHashtableEntry<F>* p = bucket(i);
177 while (p != NULL) {
178 BasicHashtableEntry<F>* next = p->next();
179 p->set_next(new_list);
180 new_list = p;
181 p = next;
182 }
183 *bucket_addr(i) = new_list;
184 }
185 }
188 // Copy the table to the shared space.
190 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) {
192 // Dump the hash table entries.
194 intptr_t *plen = (intptr_t*)(*top);
195 *top += sizeof(*plen);
197 int i;
198 for (i = 0; i < _table_size; ++i) {
199 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
200 *p != NULL;
201 p = (*p)->next_addr()) {
202 if (*top + entry_size() > end) {
203 report_out_of_shared_space(SharedMiscData);
204 }
205 *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size());
206 *top += entry_size();
207 }
208 }
209 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
211 // Set the shared bit.
213 for (i = 0; i < _table_size; ++i) {
214 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
215 p->set_shared();
216 }
217 }
218 }
222 // Reverse the order of elements in the hash buckets.
224 template <class T, MEMFLAGS F> void Hashtable<T, F>::reverse(void* boundary) {
226 for (int i = 0; i < this->table_size(); ++i) {
227 HashtableEntry<T, F>* high_list = NULL;
228 HashtableEntry<T, F>* low_list = NULL;
229 HashtableEntry<T, F>* last_low_entry = NULL;
230 HashtableEntry<T, F>* p = bucket(i);
231 while (p != NULL) {
232 HashtableEntry<T, F>* next = p->next();
233 if ((void*)p->literal() >= boundary) {
234 p->set_next(high_list);
235 high_list = p;
236 } else {
237 p->set_next(low_list);
238 low_list = p;
239 if (last_low_entry == NULL) {
240 last_low_entry = p;
241 }
242 }
243 p = next;
244 }
245 if (low_list != NULL) {
246 *bucket_addr(i) = low_list;
247 last_low_entry->set_next(high_list);
248 } else {
249 *bucket_addr(i) = high_list;
250 }
251 }
252 }
255 // Dump the hash table buckets.
257 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
258 intptr_t len = _table_size * sizeof(HashtableBucket<F>);
259 *(intptr_t*)(*top) = len;
260 *top += sizeof(intptr_t);
262 *(intptr_t*)(*top) = _number_of_entries;
263 *top += sizeof(intptr_t);
265 if (*top + len > end) {
266 report_out_of_shared_space(SharedMiscData);
267 }
268 _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
269 *top += len;
270 }
273 #ifndef PRODUCT
275 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
276 ResourceMark rm;
278 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
279 HashtableEntry<T, F>* entry = bucket(i);
280 while(entry != NULL) {
281 tty->print("%d : ", i);
282 entry->literal()->print();
283 tty->cr();
284 entry = entry->next();
285 }
286 }
287 }
290 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
291 int count = 0;
292 for (int i = 0; i < table_size(); i++) {
293 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
294 ++count;
295 }
296 }
297 assert(count == number_of_entries(), "number of hashtable entries incorrect");
298 }
301 #endif // PRODUCT
304 #ifdef ASSERT
306 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
307 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
308 warning("Performance bug: SystemDictionary lookup_count=%d "
309 "lookup_length=%d average=%lf load=%f",
310 _lookup_count, _lookup_length,
311 (double) _lookup_length / _lookup_count, load);
312 }
313 }
315 #endif
316 // Explicitly instantiate these types
317 template class Hashtable<constantPoolOop, mtClass>;
318 template class Hashtable<Symbol*, mtSymbol>;
319 template class Hashtable<klassOop, mtClass>;
320 template class Hashtable<oop, mtClass>;
321 #ifdef SOLARIS
322 template class Hashtable<oop, mtSymbol>;
323 #endif
324 template class Hashtable<oopDesc*, mtSymbol>;
325 template class Hashtable<Symbol*, mtClass>;
326 template class HashtableEntry<Symbol*, mtSymbol>;
327 template class HashtableEntry<Symbol*, mtClass>;
328 template class HashtableEntry<oop, mtSymbol>;
329 template class BasicHashtableEntry<mtSymbol>;
330 template class BasicHashtableEntry<mtCode>;
331 template class BasicHashtable<mtClass>;
332 template class BasicHashtable<mtSymbol>;
333 template class BasicHashtable<mtCode>;
334 template class BasicHashtable<mtInternal>;