1 /*
2 * Copyright (c) 2003, 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 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp"
27 #include "classfile/javaClasses.hpp"
28 #include "classfile/stringTable.hpp"
29 #include "memory/allocation.inline.hpp"
30 #include "memory/filemap.hpp"
31 #include "memory/resourceArea.hpp"
32 #include "oops/oop.inline.hpp"
33 #include "runtime/safepoint.hpp"
34 #include "utilities/dtrace.hpp"
35 #include "utilities/hashtable.hpp"
36 #include "utilities/hashtable.inline.hpp"
37 #include "utilities/numberSeq.hpp"
38
39
40 // This is a generic hashtable, designed to be used for the symbol
41 // and string tables.
42 //
43 // It is implemented as an open hash table with a fixed number of buckets.
44 //
45 // %note:
46 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
47
48 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
49 BasicHashtableEntry<F>* entry = NULL;
50 if (_free_list) {
51 entry = _free_list;
52 _free_list = _free_list->next();
53 }
54 return entry;
55 }
56
57 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
58 BasicHashtableEntry<F>* entry = new_entry_free_list();
59
60 if (entry == NULL) {
61 if (_first_free_entry + _entry_size >= _end_block) {
62 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
63 int len = _entry_size * block_size;
64 len = 1 << log2_intptr(len); // round down to power of 2
65 assert(len >= _entry_size, "");
66 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
67 _end_block = _first_free_entry + len;
68 }
69 entry = (BasicHashtableEntry<F>*)_first_free_entry;
70 _first_free_entry += _entry_size;
71 }
72
73 assert(_entry_size % HeapWordSize == 0, "");
74 entry->set_hash(hashValue);
75 return entry;
76 }
77
78
79 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
80 HashtableEntry<T, F>* entry;
81
82 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
83 entry->set_literal(obj);
84 return entry;
85 }
86
87 // Check to see if the hashtable is unbalanced. The caller set a flag to
88 // rehash at the next safepoint. If this bucket is 60 times greater than the
89 // expected average bucket length, it's an unbalanced hashtable.
90 // This is somewhat an arbitrary heuristic but if one bucket gets to
91 // rehash_count which is currently 100, there's probably something wrong.
92
93 template <class T, MEMFLAGS F> bool RehashableHashtable<T, F>::check_rehash_table(int count) {
94 assert(this->table_size() != 0, "underflow");
95 if (count > (((double)this->number_of_entries()/(double)this->table_size())*rehash_multiple)) {
96 // Set a flag for the next safepoint, which should be at some guaranteed
97 // safepoint interval.
98 return true;
99 }
100 return false;
101 }
102
103 template <class T, MEMFLAGS F> juint RehashableHashtable<T, F>::_seed = 0;
104
105 // Create a new table and using alternate hash code, populate the new table
106 // with the existing elements. This can be used to change the hash code
107 // and could in the future change the size of the table.
108
109 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::move_to(RehashableHashtable<T, F>* new_table) {
110
111 // Initialize the global seed for hashing.
112 _seed = AltHashing::compute_seed();
113 assert(seed() != 0, "shouldn't be zero");
114
115 int saved_entry_count = this->number_of_entries();
116
117 // Iterate through the table and create a new entry for the new table
118 for (int i = 0; i < new_table->table_size(); ++i) {
119 for (HashtableEntry<T, F>* p = this->bucket(i); p != NULL; ) {
120 HashtableEntry<T, F>* next = p->next();
121 T string = p->literal();
122 // Use alternate hashing algorithm on the symbol in the first table
123 unsigned int hashValue = string->new_hash(seed());
124 // Get a new index relative to the new table (can also change size)
125 int index = new_table->hash_to_index(hashValue);
126 p->set_hash(hashValue);
127 // Keep the shared bit in the Hashtable entry to indicate that this entry
128 // can't be deleted. The shared bit is the LSB in the _next field so
129 // walking the hashtable past these entries requires
130 // BasicHashtableEntry::make_ptr() call.
131 bool keep_shared = p->is_shared();
132 this->unlink_entry(p);
133 new_table->add_entry(index, p);
134 if (keep_shared) {
135 p->set_shared();
136 }
137 p = next;
138 }
139 }
140 // give the new table the free list as well
141 new_table->copy_freelist(this);
142 assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?");
143
144 // Destroy memory used by the buckets in the hashtable. The memory
145 // for the elements has been used in a new table and is not
146 // destroyed. The memory reuse will benefit resizing the SystemDictionary
147 // to avoid a memory allocation spike at safepoint.
148 BasicHashtable<F>::free_buckets();
149 }
150
151 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
152 if (NULL != _buckets) {
153 // Don't delete the buckets in the shared space. They aren't
154 // allocated by os::malloc
155 if (!UseSharedSpaces ||
156 !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {
157 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets, F);
158 }
159 _buckets = NULL;
160 }
161 }
162
163
164 // Reverse the order of elements in the hash buckets.
165
166 template <MEMFLAGS F> void BasicHashtable<F>::reverse() {
167
168 for (int i = 0; i < _table_size; ++i) {
169 BasicHashtableEntry<F>* new_list = NULL;
170 BasicHashtableEntry<F>* p = bucket(i);
171 while (p != NULL) {
172 BasicHashtableEntry<F>* next = p->next();
173 p->set_next(new_list);
174 new_list = p;
175 p = next;
176 }
177 *bucket_addr(i) = new_list;
178 }
179 }
180
181
182 // Copy the table to the shared space.
183
184 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) {
185
186 // Dump the hash table entries.
187
188 intptr_t *plen = (intptr_t*)(*top);
189 *top += sizeof(*plen);
190
191 int i;
192 for (i = 0; i < _table_size; ++i) {
193 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
194 *p != NULL;
195 p = (*p)->next_addr()) {
196 if (*top + entry_size() > end) {
197 report_out_of_shared_space(SharedMiscData);
198 }
199 *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size());
200 *top += entry_size();
201 }
202 }
203 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
204
205 // Set the shared bit.
206
207 for (i = 0; i < _table_size; ++i) {
208 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
209 p->set_shared();
210 }
211 }
212 }
213
214
215
216 // Reverse the order of elements in the hash buckets.
217
218 template <class T, MEMFLAGS F> void Hashtable<T, F>::reverse(void* boundary) {
219
220 for (int i = 0; i < this->table_size(); ++i) {
221 HashtableEntry<T, F>* high_list = NULL;
222 HashtableEntry<T, F>* low_list = NULL;
223 HashtableEntry<T, F>* last_low_entry = NULL;
224 HashtableEntry<T, F>* p = bucket(i);
225 while (p != NULL) {
226 HashtableEntry<T, F>* next = p->next();
227 if ((void*)p->literal() >= boundary) {
228 p->set_next(high_list);
229 high_list = p;
230 } else {
231 p->set_next(low_list);
232 low_list = p;
233 if (last_low_entry == NULL) {
234 last_low_entry = p;
235 }
236 }
237 p = next;
238 }
239 if (low_list != NULL) {
240 *bucket_addr(i) = low_list;
241 last_low_entry->set_next(high_list);
242 } else {
243 *bucket_addr(i) = high_list;
244 }
245 }
246 }
247
248 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(Symbol *symbol) {
249 return symbol->size() * HeapWordSize;
250 }
251
252 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(oop oop) {
253 // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
254 // and the String.value array is shared by several Strings. However, starting from JDK8,
255 // the String.value array is not shared anymore.
256 assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
257 return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;
258 }
259
260 // Dump footprint and bucket length statistics
261 //
262 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
263 // add a new function Hashtable<T, F>::literal_size(MyNewType lit)
264
265 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
266 NumberSeq summary;
267 int literal_bytes = 0;
268 for (int i = 0; i < this->table_size(); ++i) {
269 int count = 0;
270 for (HashtableEntry<T, F>* e = this->bucket(i);
271 e != NULL; e = e->next()) {
272 count++;
273 literal_bytes += literal_size(e->literal());
274 }
275 summary.add((double)count);
276 }
277 double num_buckets = summary.num();
278 double num_entries = summary.sum();
279
280 int bucket_bytes = (int)num_buckets * sizeof(HashtableBucket<F>);
281 int entry_bytes = (int)num_entries * sizeof(HashtableEntry<T, F>);
282 int total_bytes = literal_bytes + bucket_bytes + entry_bytes;
283
284 double bucket_avg = (num_buckets <= 0) ? 0 : (bucket_bytes / num_buckets);
285 double entry_avg = (num_entries <= 0) ? 0 : (entry_bytes / num_entries);
286 double literal_avg = (num_entries <= 0) ? 0 : (literal_bytes / num_entries);
287
288 st->print_cr("%s statistics:", table_name);
289 st->print_cr("Number of buckets : %9d = %9d bytes, avg %7.3f", (int)num_buckets, bucket_bytes, bucket_avg);
290 st->print_cr("Number of entries : %9d = %9d bytes, avg %7.3f", (int)num_entries, entry_bytes, entry_avg);
291 st->print_cr("Number of literals : %9d = %9d bytes, avg %7.3f", (int)num_entries, literal_bytes, literal_avg);
292 st->print_cr("Total footprint : %9s = %9d bytes", "", total_bytes);
293 st->print_cr("Average bucket size : %9.3f", summary.avg());
294 st->print_cr("Variance of bucket size : %9.3f", summary.variance());
295 st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
296 st->print_cr("Maximum bucket size : %9d", (int)summary.maximum());
297 }
298
299
300 // Dump the hash table buckets.
301
302 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
303 intptr_t len = _table_size * sizeof(HashtableBucket<F>);
304 *(intptr_t*)(*top) = len;
305 *top += sizeof(intptr_t);
306
307 *(intptr_t*)(*top) = _number_of_entries;
308 *top += sizeof(intptr_t);
309
310 if (*top + len > end) {
311 report_out_of_shared_space(SharedMiscData);
312 }
313 _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
314 *top += len;
315 }
316
317
318 #ifndef PRODUCT
319
320 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
321 ResourceMark rm;
322
323 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
324 HashtableEntry<T, F>* entry = bucket(i);
325 while(entry != NULL) {
326 tty->print("%d : ", i);
327 entry->literal()->print();
328 tty->cr();
329 entry = entry->next();
330 }
331 }
332 }
333
334
335 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
336 int count = 0;
337 for (int i = 0; i < table_size(); i++) {
338 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
339 ++count;
340 }
341 }
342 assert(count == number_of_entries(), "number of hashtable entries incorrect");
343 }
344
345
346 #endif // PRODUCT
347
348 #ifdef ASSERT
349
350 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
351 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
352 warning("Performance bug: SystemDictionary lookup_count=%d "
353 "lookup_length=%d average=%lf load=%f",
354 _lookup_count, _lookup_length,
355 (double) _lookup_length / _lookup_count, load);
356 }
357 }
358
359 #endif
360
361
362 // Explicitly instantiate these types
363 template class Hashtable<ConstantPool*, mtClass>;
364 template class RehashableHashtable<Symbol*, mtSymbol>;
365 template class RehashableHashtable<oopDesc*, mtSymbol>;
366 template class Hashtable<Symbol*, mtSymbol>;
367 template class Hashtable<Klass*, mtClass>;
368 template class Hashtable<oop, mtClass>;
369 #if defined(CHECK_UNHANDLED_OOPS)
370 template class Hashtable<oop, mtSymbol>;
371 template class RehashableHashtable<oop, mtSymbol>;
372 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
373 template class Hashtable<oopDesc*, mtSymbol>;
374 template class Hashtable<Symbol*, mtClass>;
375 template class HashtableEntry<Symbol*, mtSymbol>;
376 template class HashtableEntry<Symbol*, mtClass>;
377 template class HashtableEntry<oop, mtSymbol>;
378 template class BasicHashtableEntry<mtSymbol>;
379 template class BasicHashtableEntry<mtCode>;
380 template class BasicHashtable<mtClass>;
381 template class BasicHashtable<mtSymbol>;
382 template class BasicHashtable<mtCode>;
383 template class BasicHashtable<mtInternal>;