1 /*
2 * Copyright (c) 2003, 2018, 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/dictionary.hpp"
28 #include "classfile/javaClasses.inline.hpp"
29 #include "classfile/moduleEntry.hpp"
30 #include "classfile/packageEntry.hpp"
31 #include "classfile/placeholders.hpp"
32 #include "classfile/protectionDomainCache.hpp"
33 #include "classfile/stringTable.hpp"
34 #include "memory/allocation.inline.hpp"
35 #include "memory/metaspaceShared.hpp"
36 #include "memory/resourceArea.hpp"
37 #include "oops/oop.inline.hpp"
38 #include "oops/weakHandle.inline.hpp"
39 #include "runtime/safepoint.hpp"
40 #include "utilities/dtrace.hpp"
41 #include "utilities/hashtable.hpp"
42 #include "utilities/hashtable.inline.hpp"
43 #include "utilities/numberSeq.hpp"
44
45
46 // This hashtable is implemented as an open hash table with a fixed number of buckets.
47
48 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
49 BasicHashtableEntry<F>* entry = NULL;
50 if (_free_list != NULL) {
51 entry = _free_list;
52 _free_list = _free_list->next();
53 }
54 return entry;
55 }
56
57 // HashtableEntrys are allocated in blocks to reduce the space overhead.
58 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
59 BasicHashtableEntry<F>* entry = new_entry_free_list();
60
61 if (entry == NULL) {
62 if (_first_free_entry + _entry_size >= _end_block) {
63 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
64 int len = _entry_size * block_size;
65 len = 1 << log2_intptr(len); // round down to power of 2
66 assert(len >= _entry_size, "");
67 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
68 _end_block = _first_free_entry + len;
69 }
70 entry = (BasicHashtableEntry<F>*)_first_free_entry;
71 _first_free_entry += _entry_size;
72 }
73
74 assert(_entry_size % HeapWordSize == 0, "");
75 entry->set_hash(hashValue);
76 return entry;
77 }
78
79
80 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
81 HashtableEntry<T, F>* entry;
82
83 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
84 entry->set_literal(obj);
85 return entry;
86 }
87
88 // Version of hashtable entry allocation that allocates in the C heap directly.
89 // The allocator in blocks is preferable but doesn't have free semantics.
90 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::allocate_new_entry(unsigned int hashValue, T obj) {
91 HashtableEntry<T, F>* entry = (HashtableEntry<T, F>*) NEW_C_HEAP_ARRAY(char, this->entry_size(), F);
92
93 entry->set_hash(hashValue);
94 entry->set_literal(obj);
95 entry->set_next(NULL);
96 return entry;
97 }
98
99 // Check to see if the hashtable is unbalanced. The caller set a flag to
100 // rehash at the next safepoint. If this bucket is 60 times greater than the
101 // expected average bucket length, it's an unbalanced hashtable.
102 // This is somewhat an arbitrary heuristic but if one bucket gets to
103 // rehash_count which is currently 100, there's probably something wrong.
104
105 template <class T, MEMFLAGS F> bool RehashableHashtable<T, F>::check_rehash_table(int count) {
106 assert(this->table_size() != 0, "underflow");
107 if (count > (((double)this->number_of_entries()/(double)this->table_size())*rehash_multiple)) {
108 // Set a flag for the next safepoint, which should be at some guaranteed
109 // safepoint interval.
110 return true;
111 }
112 return false;
113 }
114
115 // Create a new table and using alternate hash code, populate the new table
116 // with the existing elements. This can be used to change the hash code
117 // and could in the future change the size of the table.
118
119 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::move_to(RehashableHashtable<T, F>* new_table) {
120
121 // Initialize the global seed for hashing.
122 _seed = AltHashing::compute_seed();
123 assert(seed() != 0, "shouldn't be zero");
124
125 int saved_entry_count = this->number_of_entries();
126
127 // Iterate through the table and create a new entry for the new table
128 for (int i = 0; i < new_table->table_size(); ++i) {
129 for (HashtableEntry<T, F>* p = this->bucket(i); p != NULL; ) {
130 HashtableEntry<T, F>* next = p->next();
131 T string = p->literal();
132 // Use alternate hashing algorithm on the symbol in the first table
133 unsigned int hashValue = string->new_hash(seed());
134 // Get a new index relative to the new table (can also change size)
135 int index = new_table->hash_to_index(hashValue);
136 p->set_hash(hashValue);
137 // Keep the shared bit in the Hashtable entry to indicate that this entry
138 // can't be deleted. The shared bit is the LSB in the _next field so
139 // walking the hashtable past these entries requires
140 // BasicHashtableEntry::make_ptr() call.
141 bool keep_shared = p->is_shared();
142 this->unlink_entry(p);
143 new_table->add_entry(index, p);
144 if (keep_shared) {
145 p->set_shared();
146 }
147 p = next;
148 }
149 }
150 // give the new table the free list as well
151 new_table->copy_freelist(this);
152
153 // Destroy memory used by the buckets in the hashtable. The memory
154 // for the elements has been used in a new table and is not
155 // destroyed. The memory reuse will benefit resizing the SystemDictionary
156 // to avoid a memory allocation spike at safepoint.
157 BasicHashtable<F>::free_buckets();
158 }
159
160 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
161 if (NULL != _buckets) {
162 // Don't delete the buckets in the shared space. They aren't
163 // allocated by os::malloc
164 if (!MetaspaceShared::is_in_shared_metaspace(_buckets)) {
165 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets);
166 }
167 _buckets = NULL;
168 }
169 }
170
171 template <MEMFLAGS F> void BasicHashtable<F>::BucketUnlinkContext::free_entry(BasicHashtableEntry<F>* entry) {
172 entry->set_next(_removed_head);
173 _removed_head = entry;
174 if (_removed_tail == NULL) {
175 _removed_tail = entry;
176 }
177 _num_removed++;
178 }
179
180 template <MEMFLAGS F> void BasicHashtable<F>::bulk_free_entries(BucketUnlinkContext* context) {
181 if (context->_num_removed == 0) {
182 assert(context->_removed_head == NULL && context->_removed_tail == NULL,
183 "Zero entries in the unlink context, but elements linked from " PTR_FORMAT " to " PTR_FORMAT,
184 p2i(context->_removed_head), p2i(context->_removed_tail));
185 return;
186 }
187
188 // MT-safe add of the list of BasicHashTableEntrys from the context to the free list.
189 BasicHashtableEntry<F>* current = _free_list;
190 while (true) {
191 context->_removed_tail->set_next(current);
192 BasicHashtableEntry<F>* old = Atomic::cmpxchg(context->_removed_head, &_free_list, current);
193 if (old == current) {
194 break;
195 }
196 current = old;
197 }
198 Atomic::add(-context->_num_removed, &_number_of_entries);
199 }
200 // Copy the table to the shared space.
201 template <MEMFLAGS F> size_t BasicHashtable<F>::count_bytes_for_table() {
202 size_t bytes = 0;
203 bytes += sizeof(intptr_t); // len
204
205 for (int i = 0; i < _table_size; ++i) {
206 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
207 *p != NULL;
208 p = (*p)->next_addr()) {
209 bytes += entry_size();
210 }
211 }
212
213 return bytes;
214 }
215
216 // Dump the hash table entries (into CDS archive)
217 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char* top, char* end) {
218 assert(is_aligned(top, sizeof(intptr_t)), "bad alignment");
219 intptr_t *plen = (intptr_t*)(top);
220 top += sizeof(*plen);
221
222 int i;
223 for (i = 0; i < _table_size; ++i) {
224 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
225 *p != NULL;
226 p = (*p)->next_addr()) {
227 *p = (BasicHashtableEntry<F>*)memcpy(top, (void*)*p, entry_size());
228 top += entry_size();
229 }
230 }
231 *plen = (char*)(top) - (char*)plen - sizeof(*plen);
232 assert(top == end, "count_bytes_for_table is wrong");
233 // Set the shared bit.
234
235 for (i = 0; i < _table_size; ++i) {
236 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
237 p->set_shared();
238 }
239 }
240 }
241
242 // For oops and Strings the size of the literal is interesting. For other types, nobody cares.
243 static int literal_size(ConstantPool*) { return 0; }
244 static int literal_size(Klass*) { return 0; }
245 #if INCLUDE_ALL_GCS
246 static int literal_size(nmethod*) { return 0; }
247 #endif
248
249 static int literal_size(Symbol *symbol) {
250 return symbol->size() * HeapWordSize;
251 }
252
253 static int literal_size(oop obj) {
254 // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
255 // and the String.value array is shared by several Strings. However, starting from JDK8,
256 // the String.value array is not shared anymore.
257 if (obj == NULL) {
258 return 0;
259 } else if (obj->klass() == SystemDictionary::String_klass()) {
260 return (obj->size() + java_lang_String::value(obj)->size()) * HeapWordSize;
261 } else {
262 return obj->size();
263 }
264 }
265
266 static int literal_size(ClassLoaderWeakHandle v) {
267 return literal_size(v.peek());
268 }
269
270 template <MEMFLAGS F> bool BasicHashtable<F>::resize(int new_size) {
271 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
272
273 // Allocate new buckets
274 HashtableBucket<F>* buckets_new = NEW_C_HEAP_ARRAY2_RETURN_NULL(HashtableBucket<F>, new_size, F, CURRENT_PC);
275 if (buckets_new == NULL) {
276 return false;
277 }
278
279 // Clear the new buckets
280 for (int i = 0; i < new_size; i++) {
281 buckets_new[i].clear();
282 }
283
284 int table_size_old = _table_size;
285 // hash_to_index() uses _table_size, so switch the sizes now
286 _table_size = new_size;
287
288 // Move entries from the old table to a new table
289 for (int index_old = 0; index_old < table_size_old; index_old++) {
290 for (BasicHashtableEntry<F>* p = _buckets[index_old].get_entry(); p != NULL; ) {
291 BasicHashtableEntry<F>* next = p->next();
292 bool keep_shared = p->is_shared();
293 int index_new = hash_to_index(p->hash());
294
295 p->set_next(buckets_new[index_new].get_entry());
296 buckets_new[index_new].set_entry(p);
297
298 if (keep_shared) {
299 p->set_shared();
300 }
301 p = next;
302 }
303 }
304
305 // The old backets now can be released
306 BasicHashtable<F>::free_buckets();
307
308 // Switch to the new storage
309 _buckets = buckets_new;
310
311 return true;
312 }
313
314 // Dump footprint and bucket length statistics
315 //
316 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
317 // add a new function static int literal_size(MyNewType lit)
318 // because I can't get template <class T> int literal_size(T) to pick the specializations for Symbol and oop.
319 //
320 // The StringTable and SymbolTable dumping print how much footprint is used by the String and Symbol
321 // literals.
322
323 template <class T, MEMFLAGS F> void Hashtable<T, F>::print_table_statistics(outputStream* st,
324 const char *table_name) {
325 NumberSeq summary;
326 int literal_bytes = 0;
327 for (int i = 0; i < this->table_size(); ++i) {
328 int count = 0;
329 for (HashtableEntry<T, F>* e = this->bucket(i);
330 e != NULL; e = e->next()) {
331 count++;
332 literal_bytes += literal_size(e->literal());
333 }
334 summary.add((double)count);
335 }
336 double num_buckets = summary.num();
337 double num_entries = summary.sum();
338
339 int bucket_bytes = (int)num_buckets * sizeof(HashtableBucket<F>);
340 int entry_bytes = (int)num_entries * sizeof(HashtableEntry<T, F>);
341 int total_bytes = literal_bytes + bucket_bytes + entry_bytes;
342
343 int bucket_size = (num_buckets <= 0) ? 0 : (bucket_bytes / num_buckets);
344 int entry_size = (num_entries <= 0) ? 0 : (entry_bytes / num_entries);
345
346 st->print_cr("%s statistics:", table_name);
347 st->print_cr("Number of buckets : %9d = %9d bytes, each %d", (int)num_buckets, bucket_bytes, bucket_size);
348 st->print_cr("Number of entries : %9d = %9d bytes, each %d", (int)num_entries, entry_bytes, entry_size);
349 if (literal_bytes != 0) {
350 double literal_avg = (num_entries <= 0) ? 0 : (literal_bytes / num_entries);
351 st->print_cr("Number of literals : %9d = %9d bytes, avg %7.3f", (int)num_entries, literal_bytes, literal_avg);
352 }
353 st->print_cr("Total footprint : %9s = %9d bytes", "", total_bytes);
354 st->print_cr("Average bucket size : %9.3f", summary.avg());
355 st->print_cr("Variance of bucket size : %9.3f", summary.variance());
356 st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
357 st->print_cr("Maximum bucket size : %9d", (int)summary.maximum());
358 }
359
360
361 // Dump the hash table buckets.
362
363 template <MEMFLAGS F> size_t BasicHashtable<F>::count_bytes_for_buckets() {
364 size_t bytes = 0;
365 bytes += sizeof(intptr_t); // len
366 bytes += sizeof(intptr_t); // _number_of_entries
367 bytes += _table_size * sizeof(HashtableBucket<F>); // the buckets
368
369 return bytes;
370 }
371
372 // Dump the buckets (into CDS archive)
373 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char* top, char* end) {
374 assert(is_aligned(top, sizeof(intptr_t)), "bad alignment");
375 intptr_t len = _table_size * sizeof(HashtableBucket<F>);
376 *(intptr_t*)(top) = len;
377 top += sizeof(intptr_t);
378
379 *(intptr_t*)(top) = _number_of_entries;
380 top += sizeof(intptr_t);
381
382 _buckets = (HashtableBucket<F>*)memcpy(top, (void*)_buckets, len);
383 top += len;
384
385 assert(top == end, "count_bytes_for_buckets is wrong");
386 }
387
388 #ifndef PRODUCT
389 template <class T> void print_literal(T l) {
390 l->print();
391 }
392
393 static void print_literal(ClassLoaderWeakHandle l) {
394 l.print();
395 }
396
397 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
398 ResourceMark rm;
399
400 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
401 HashtableEntry<T, F>* entry = bucket(i);
402 while(entry != NULL) {
403 tty->print("%d : ", i);
404 print_literal(entry->literal());
405 tty->cr();
406 entry = entry->next();
407 }
408 }
409 }
410
411 template <MEMFLAGS F>
412 template <class T> void BasicHashtable<F>::verify_table(const char* table_name) {
413 int element_count = 0;
414 int max_bucket_count = 0;
415 int max_bucket_number = 0;
416 for (int index = 0; index < table_size(); index++) {
417 int bucket_count = 0;
418 for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
419 probe->verify();
420 bucket_count++;
421 }
422 element_count += bucket_count;
423 if (bucket_count > max_bucket_count) {
424 max_bucket_count = bucket_count;
425 max_bucket_number = index;
426 }
427 }
428 guarantee(number_of_entries() == element_count,
429 "Verify of %s failed", table_name);
430
431 // Log some statistics about the hashtable
432 log_info(hashtables)("%s max bucket size %d bucket %d element count %d table size %d", table_name,
433 max_bucket_count, max_bucket_number, _number_of_entries, _table_size);
434 if (_number_of_entries > 0 && log_is_enabled(Debug, hashtables)) {
435 for (int index = 0; index < table_size(); index++) {
436 int bucket_count = 0;
437 for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
438 log_debug(hashtables)("bucket %d hash " INTPTR_FORMAT, index, (intptr_t)probe->hash());
439 bucket_count++;
440 }
441 if (bucket_count > 0) {
442 log_debug(hashtables)("bucket %d count %d", index, bucket_count);
443 }
444 }
445 }
446 }
447 #endif // PRODUCT
448
449 // Explicitly instantiate these types
450 #if INCLUDE_ALL_GCS
451 template class Hashtable<nmethod*, mtGC>;
452 template class HashtableEntry<nmethod*, mtGC>;
453 template class BasicHashtable<mtGC>;
454 #endif
455 template class Hashtable<ConstantPool*, mtClass>;
456 template class RehashableHashtable<Symbol*, mtSymbol>;
457 template class RehashableHashtable<oop, mtSymbol>;
458 template class Hashtable<Symbol*, mtSymbol>;
459 template class Hashtable<Klass*, mtClass>;
460 template class Hashtable<InstanceKlass*, mtClass>;
461 template class Hashtable<ClassLoaderWeakHandle, mtClass>;
462 template class Hashtable<Symbol*, mtModule>;
463 template class Hashtable<oop, mtSymbol>;
464 template class Hashtable<ClassLoaderWeakHandle, mtSymbol>;
465 template class Hashtable<Symbol*, mtClass>;
466 template class HashtableEntry<Symbol*, mtSymbol>;
467 template class HashtableEntry<Symbol*, mtClass>;
468 template class HashtableEntry<oop, mtSymbol>;
469 template class HashtableEntry<ClassLoaderWeakHandle, mtSymbol>;
470 template class HashtableBucket<mtClass>;
471 template class BasicHashtableEntry<mtSymbol>;
472 template class BasicHashtableEntry<mtCode>;
473 template class BasicHashtable<mtClass>;
474 template class BasicHashtable<mtClassShared>;
475 template class BasicHashtable<mtSymbol>;
476 template class BasicHashtable<mtCode>;
477 template class BasicHashtable<mtInternal>;
478 template class BasicHashtable<mtModule>;
479 #if INCLUDE_TRACE
480 template class Hashtable<Symbol*, mtTracing>;
481 template class HashtableEntry<Symbol*, mtTracing>;
482 template class BasicHashtable<mtTracing>;
483 #endif
484 template class BasicHashtable<mtCompiler>;
485
486 template void BasicHashtable<mtClass>::verify_table<DictionaryEntry>(char const*);
487 template void BasicHashtable<mtModule>::verify_table<ModuleEntry>(char const*);
488 template void BasicHashtable<mtModule>::verify_table<PackageEntry>(char const*);
489 template void BasicHashtable<mtClass>::verify_table<ProtectionDomainCacheEntry>(char const*);
490 template void BasicHashtable<mtClass>::verify_table<PlaceholderEntry>(char const*);