annotate hotspot/src/share/vm/utilities/hashtable.cpp @ 46545:b970b6e40209

8181450: assert in BasicHashtable::verify_table Summary: remove assert as it has small probability of happening and added logging Reviewed-by: kbarrett, sspitsyn
author coleenp
date Fri, 16 Jun 2017 09:13:56 -0400
parents 01c282163d38
children 75aa3e39d02c
rev   line source
duke@1 1 /*
coleenp@46475 2 * Copyright (c) 2003, 2017, Oracle and/or its affiliates. All rights reserved.
duke@1 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1 4 *
duke@1 5 * This code is free software; you can redistribute it and/or modify it
duke@1 6 * under the terms of the GNU General Public License version 2 only, as
duke@1 7 * published by the Free Software Foundation.
duke@1 8 *
duke@1 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@1 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@1 13 * accompanied this code).
duke@1 14 *
duke@1 15 * You should have received a copy of the GNU General Public License version
duke@1 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@1 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1 18 *
trims@5547 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@5547 20 * or visit www.oracle.com if you need additional information or have any
trims@5547 21 * questions.
duke@1 22 *
duke@1 23 */
duke@1 24
stefank@7397 25 #include "precompiled.hpp"
coleenp@13199 26 #include "classfile/altHashing.hpp"
coleenp@46475 27 #include "classfile/dictionary.hpp"
goetz@35498 28 #include "classfile/javaClasses.inline.hpp"
coleenp@46475 29 #include "classfile/moduleEntry.hpp"
coleenp@46475 30 #include "classfile/packageEntry.hpp"
coleenp@46545 31 #include "classfile/placeholders.hpp"
coleenp@46475 32 #include "classfile/protectionDomainCache.hpp"
gziemski@24426 33 #include "classfile/stringTable.hpp"
stefank@7397 34 #include "memory/allocation.inline.hpp"
coleenp@13097 35 #include "memory/filemap.hpp"
stefank@7397 36 #include "memory/resourceArea.hpp"
stefank@7397 37 #include "oops/oop.inline.hpp"
stefank@7397 38 #include "runtime/safepoint.hpp"
stefank@7397 39 #include "utilities/dtrace.hpp"
stefank@7397 40 #include "utilities/hashtable.hpp"
stefank@7397 41 #include "utilities/hashtable.inline.hpp"
iklam@17610 42 #include "utilities/numberSeq.hpp"
duke@1 43
coleenp@8076 44
mgerdin@26421 45 // This hashtable is implemented as an open hash table with a fixed number of buckets.
duke@1 46
mgerdin@26421 47 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
mgerdin@26421 48 BasicHashtableEntry<F>* entry = NULL;
mgerdin@26421 49 if (_free_list != NULL) {
duke@1 50 entry = _free_list;
duke@1 51 _free_list = _free_list->next();
mgerdin@26421 52 }
mgerdin@26421 53 return entry;
mgerdin@26421 54 }
mgerdin@26421 55
mgerdin@26421 56 // HashtableEntrys are allocated in blocks to reduce the space overhead.
mgerdin@26421 57 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
mgerdin@26421 58 BasicHashtableEntry<F>* entry = new_entry_free_list();
mgerdin@26421 59
mgerdin@26421 60 if (entry == NULL) {
jrose@1551 61 if (_first_free_entry + _entry_size >= _end_block) {
jrose@1551 62 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
duke@1 63 int len = _entry_size * block_size;
jrose@1551 64 len = 1 << log2_intptr(len); // round down to power of 2
jrose@1551 65 assert(len >= _entry_size, "");
zgu@13195 66 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
duke@1 67 _end_block = _first_free_entry + len;
duke@1 68 }
zgu@13195 69 entry = (BasicHashtableEntry<F>*)_first_free_entry;
duke@1 70 _first_free_entry += _entry_size;
duke@1 71 }
duke@1 72
jrose@1551 73 assert(_entry_size % HeapWordSize == 0, "");
duke@1 74 entry->set_hash(hashValue);
duke@1 75 return entry;
duke@1 76 }
duke@1 77
duke@1 78
zgu@13195 79 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
zgu@13195 80 HashtableEntry<T, F>* entry;
duke@1 81
zgu@13195 82 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
coleenp@8076 83 entry->set_literal(obj);
duke@1 84 return entry;
duke@1 85 }
duke@1 86
coleenp@13087 87 // Check to see if the hashtable is unbalanced. The caller set a flag to
coleenp@13087 88 // rehash at the next safepoint. If this bucket is 60 times greater than the
coleenp@13087 89 // expected average bucket length, it's an unbalanced hashtable.
coleenp@13087 90 // This is somewhat an arbitrary heuristic but if one bucket gets to
coleenp@13087 91 // rehash_count which is currently 100, there's probably something wrong.
coleenp@13087 92
mgerdin@26421 93 template <class T, MEMFLAGS F> bool RehashableHashtable<T, F>::check_rehash_table(int count) {
mgerdin@26421 94 assert(this->table_size() != 0, "underflow");
mgerdin@26421 95 if (count > (((double)this->number_of_entries()/(double)this->table_size())*rehash_multiple)) {
coleenp@13087 96 // Set a flag for the next safepoint, which should be at some guaranteed
coleenp@13087 97 // safepoint interval.
coleenp@13087 98 return true;
coleenp@13087 99 }
coleenp@13087 100 return false;
coleenp@13087 101 }
coleenp@13087 102
mgerdin@26421 103 template <class T, MEMFLAGS F> juint RehashableHashtable<T, F>::_seed = 0;
coleenp@13199 104
coleenp@13087 105 // Create a new table and using alternate hash code, populate the new table
coleenp@13087 106 // with the existing elements. This can be used to change the hash code
coleenp@13087 107 // and could in the future change the size of the table.
coleenp@13087 108
mgerdin@26421 109 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::move_to(RehashableHashtable<T, F>* new_table) {
coleenp@13199 110
coleenp@13199 111 // Initialize the global seed for hashing.
coleenp@13199 112 _seed = AltHashing::compute_seed();
coleenp@13199 113 assert(seed() != 0, "shouldn't be zero");
coleenp@13199 114
coleenp@13199 115 int saved_entry_count = this->number_of_entries();
coleenp@13087 116
coleenp@13087 117 // Iterate through the table and create a new entry for the new table
coleenp@13087 118 for (int i = 0; i < new_table->table_size(); ++i) {
mgerdin@26421 119 for (HashtableEntry<T, F>* p = this->bucket(i); p != NULL; ) {
zgu@13195 120 HashtableEntry<T, F>* next = p->next();
coleenp@13087 121 T string = p->literal();
coleenp@13087 122 // Use alternate hashing algorithm on the symbol in the first table
coleenp@13728 123 unsigned int hashValue = string->new_hash(seed());
coleenp@13087 124 // Get a new index relative to the new table (can also change size)
coleenp@13087 125 int index = new_table->hash_to_index(hashValue);
coleenp@13087 126 p->set_hash(hashValue);
coleenp@13097 127 // Keep the shared bit in the Hashtable entry to indicate that this entry
coleenp@13097 128 // can't be deleted. The shared bit is the LSB in the _next field so
coleenp@13097 129 // walking the hashtable past these entries requires
coleenp@13097 130 // BasicHashtableEntry::make_ptr() call.
coleenp@13097 131 bool keep_shared = p->is_shared();
andrew@13342 132 this->unlink_entry(p);
coleenp@13087 133 new_table->add_entry(index, p);
coleenp@13097 134 if (keep_shared) {
coleenp@13097 135 p->set_shared();
coleenp@13097 136 }
coleenp@13087 137 p = next;
coleenp@13087 138 }
coleenp@13087 139 }
coleenp@13087 140 // give the new table the free list as well
coleenp@13087 141 new_table->copy_freelist(this);
coleenp@13087 142 assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?");
coleenp@13087 143
coleenp@13087 144 // Destroy memory used by the buckets in the hashtable. The memory
coleenp@13087 145 // for the elements has been used in a new table and is not
coleenp@13087 146 // destroyed. The memory reuse will benefit resizing the SystemDictionary
coleenp@13087 147 // to avoid a memory allocation spike at safepoint.
zgu@13195 148 BasicHashtable<F>::free_buckets();
coleenp@13087 149 }
coleenp@13087 150
zgu@13195 151 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
coleenp@13097 152 if (NULL != _buckets) {
coleenp@13097 153 // Don't delete the buckets in the shared space. They aren't
coleenp@13097 154 // allocated by os::malloc
coleenp@13097 155 if (!UseSharedSpaces ||
coleenp@13097 156 !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {
coleenp@27880 157 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets);
coleenp@13097 158 }
coleenp@13097 159 _buckets = NULL;
coleenp@13097 160 }
coleenp@13097 161 }
coleenp@13097 162
tschatzl@45114 163 template <MEMFLAGS F> void BasicHashtable<F>::BucketUnlinkContext::free_entry(BasicHashtableEntry<F>* entry) {
tschatzl@45114 164 entry->set_next(_removed_head);
tschatzl@45114 165 _removed_head = entry;
tschatzl@45114 166 if (_removed_tail == NULL) {
tschatzl@45114 167 _removed_tail = entry;
tschatzl@45114 168 }
tschatzl@45114 169 _num_removed++;
tschatzl@45114 170 }
tschatzl@45114 171
tschatzl@45114 172 template <MEMFLAGS F> void BasicHashtable<F>::bulk_free_entries(BucketUnlinkContext* context) {
tschatzl@45114 173 if (context->_num_removed == 0) {
tschatzl@45114 174 assert(context->_removed_head == NULL && context->_removed_tail == NULL,
tschatzl@45114 175 "Zero entries in the unlink context, but elements linked from " PTR_FORMAT " to " PTR_FORMAT,
tschatzl@45114 176 p2i(context->_removed_head), p2i(context->_removed_tail));
tschatzl@45114 177 return;
tschatzl@45114 178 }
tschatzl@45114 179
tschatzl@45114 180 // MT-safe add of the list of BasicHashTableEntrys from the context to the free list.
tschatzl@45114 181 BasicHashtableEntry<F>* current = _free_list;
tschatzl@45114 182 while (true) {
tschatzl@45114 183 context->_removed_tail->set_next(current);
tschatzl@45114 184 BasicHashtableEntry<F>* old = (BasicHashtableEntry<F>*)Atomic::cmpxchg_ptr(context->_removed_head, &_free_list, current);
tschatzl@45114 185 if (old == current) {
tschatzl@45114 186 break;
tschatzl@45114 187 }
tschatzl@45114 188 current = old;
tschatzl@45114 189 }
tschatzl@45114 190 Atomic::add(-context->_num_removed, &_number_of_entries);
tschatzl@45114 191 }
coleenp@13097 192
duke@1 193 // Copy the table to the shared space.
duke@1 194
zgu@13195 195 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) {
duke@1 196
duke@1 197 // Dump the hash table entries.
duke@1 198
duke@1 199 intptr_t *plen = (intptr_t*)(*top);
duke@1 200 *top += sizeof(*plen);
duke@1 201
duke@1 202 int i;
duke@1 203 for (i = 0; i < _table_size; ++i) {
zgu@13195 204 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
duke@1 205 *p != NULL;
duke@1 206 p = (*p)->next_addr()) {
duke@1 207 if (*top + entry_size() > end) {
coleenp@8076 208 report_out_of_shared_space(SharedMiscData);
duke@1 209 }
zgu@13195 210 *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size());
duke@1 211 *top += entry_size();
duke@1 212 }
duke@1 213 }
duke@1 214 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
duke@1 215
duke@1 216 // Set the shared bit.
duke@1 217
duke@1 218 for (i = 0; i < _table_size; ++i) {
zgu@13195 219 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
duke@1 220 p->set_shared();
duke@1 221 }
duke@1 222 }
duke@1 223 }
duke@1 224
mgerdin@26421 225 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(Symbol *symbol) {
iklam@17610 226 return symbol->size() * HeapWordSize;
iklam@17610 227 }
iklam@17610 228
mgerdin@26421 229 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(oop oop) {
iklam@17610 230 // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
iklam@17610 231 // and the String.value array is shared by several Strings. However, starting from JDK8,
iklam@17610 232 // the String.value array is not shared anymore.
iklam@17610 233 assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
iklam@17610 234 return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;
iklam@17610 235 }
iklam@17610 236
iklam@17610 237 // Dump footprint and bucket length statistics
iklam@17610 238 //
iklam@17610 239 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
iklam@17610 240 // add a new function Hashtable<T, F>::literal_size(MyNewType lit)
iklam@17610 241
mgerdin@26421 242 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
iklam@17610 243 NumberSeq summary;
iklam@17610 244 int literal_bytes = 0;
iklam@17610 245 for (int i = 0; i < this->table_size(); ++i) {
iklam@17610 246 int count = 0;
mgerdin@26421 247 for (HashtableEntry<T, F>* e = this->bucket(i);
iklam@17610 248 e != NULL; e = e->next()) {
iklam@17610 249 count++;
iklam@17610 250 literal_bytes += literal_size(e->literal());
iklam@17610 251 }
iklam@17610 252 summary.add((double)count);
iklam@17610 253 }
iklam@17610 254 double num_buckets = summary.num();
iklam@17610 255 double num_entries = summary.sum();
iklam@17610 256
mgerdin@26421 257 int bucket_bytes = (int)num_buckets * sizeof(HashtableBucket<F>);
iklam@17610 258 int entry_bytes = (int)num_entries * sizeof(HashtableEntry<T, F>);
iklam@17610 259 int total_bytes = literal_bytes + bucket_bytes + entry_bytes;
iklam@17610 260
iklam@17610 261 double bucket_avg = (num_buckets <= 0) ? 0 : (bucket_bytes / num_buckets);
iklam@17610 262 double entry_avg = (num_entries <= 0) ? 0 : (entry_bytes / num_entries);
iklam@17610 263 double literal_avg = (num_entries <= 0) ? 0 : (literal_bytes / num_entries);
iklam@17610 264
iklam@17610 265 st->print_cr("%s statistics:", table_name);
iklam@17610 266 st->print_cr("Number of buckets : %9d = %9d bytes, avg %7.3f", (int)num_buckets, bucket_bytes, bucket_avg);
iklam@17610 267 st->print_cr("Number of entries : %9d = %9d bytes, avg %7.3f", (int)num_entries, entry_bytes, entry_avg);
iklam@17610 268 st->print_cr("Number of literals : %9d = %9d bytes, avg %7.3f", (int)num_entries, literal_bytes, literal_avg);
iklam@17610 269 st->print_cr("Total footprint : %9s = %9d bytes", "", total_bytes);
iklam@17610 270 st->print_cr("Average bucket size : %9.3f", summary.avg());
iklam@17610 271 st->print_cr("Variance of bucket size : %9.3f", summary.variance());
iklam@17610 272 st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
iklam@17610 273 st->print_cr("Maximum bucket size : %9d", (int)summary.maximum());
iklam@17610 274 }
iklam@17610 275
duke@1 276
duke@1 277 // Dump the hash table buckets.
duke@1 278
zgu@13195 279 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
zgu@13195 280 intptr_t len = _table_size * sizeof(HashtableBucket<F>);
duke@1 281 *(intptr_t*)(*top) = len;
duke@1 282 *top += sizeof(intptr_t);
duke@1 283
duke@1 284 *(intptr_t*)(*top) = _number_of_entries;
duke@1 285 *top += sizeof(intptr_t);
duke@1 286
duke@1 287 if (*top + len > end) {
coleenp@8076 288 report_out_of_shared_space(SharedMiscData);
duke@1 289 }
zgu@13195 290 _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
duke@1 291 *top += len;
duke@1 292 }
duke@1 293
duke@1 294
duke@1 295 #ifndef PRODUCT
duke@1 296
zgu@13195 297 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
duke@1 298 ResourceMark rm;
duke@1 299
zgu@13195 300 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
zgu@13195 301 HashtableEntry<T, F>* entry = bucket(i);
duke@1 302 while(entry != NULL) {
duke@1 303 tty->print("%d : ", i);
duke@1 304 entry->literal()->print();
duke@1 305 tty->cr();
duke@1 306 entry = entry->next();
duke@1 307 }
duke@1 308 }
duke@1 309 }
duke@1 310
coleenp@46475 311 template <MEMFLAGS F>
coleenp@46475 312 template <class T> void BasicHashtable<F>::verify_table(const char* table_name) {
coleenp@46475 313 int element_count = 0;
coleenp@46475 314 int max_bucket_count = 0;
coleenp@46545 315 int max_bucket_number = 0;
coleenp@46475 316 for (int index = 0; index < table_size(); index++) {
coleenp@46475 317 int bucket_count = 0;
coleenp@46475 318 for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
coleenp@46475 319 probe->verify();
coleenp@46475 320 bucket_count++;
duke@1 321 }
coleenp@46475 322 element_count += bucket_count;
coleenp@46545 323 if (bucket_count > max_bucket_count) {
coleenp@46545 324 max_bucket_count = bucket_count;
coleenp@46545 325 max_bucket_number = index;
coleenp@46545 326 }
duke@1 327 }
coleenp@46475 328 guarantee(number_of_entries() == element_count,
coleenp@46475 329 "Verify of %s failed", table_name);
coleenp@46545 330
coleenp@46545 331 // Log some statistics about the hashtable
coleenp@46545 332 log_info(hashtables)("%s max bucket size %d bucket %d element count %d table size %d", table_name,
coleenp@46545 333 max_bucket_count, max_bucket_number, _number_of_entries, _table_size);
coleenp@46545 334 if (_number_of_entries > 0 && log_is_enabled(Debug, hashtables)) {
coleenp@46545 335 for (int index = 0; index < table_size(); index++) {
coleenp@46545 336 int bucket_count = 0;
coleenp@46545 337 for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
coleenp@46545 338 log_debug(hashtables)("bucket %d hash " INTPTR_FORMAT, index, (intptr_t)probe->hash());
coleenp@46545 339 bucket_count++;
coleenp@46545 340 }
coleenp@46545 341 if (bucket_count > 0) {
coleenp@46545 342 log_debug(hashtables)("bucket %d count %d", index, bucket_count);
coleenp@46545 343 }
coleenp@46545 344 }
coleenp@46545 345 }
duke@1 346 }
duke@1 347 #endif // PRODUCT
duke@1 348
coleenp@8076 349 // Explicitly instantiate these types
mgerdin@26422 350 #if INCLUDE_ALL_GCS
mgerdin@26422 351 template class Hashtable<nmethod*, mtGC>;
mgerdin@26422 352 template class HashtableEntry<nmethod*, mtGC>;
mgerdin@26422 353 template class BasicHashtable<mtGC>;
mgerdin@26422 354 #endif
coleenp@13728 355 template class Hashtable<ConstantPool*, mtClass>;
mgerdin@26421 356 template class RehashableHashtable<Symbol*, mtSymbol>;
mgerdin@26421 357 template class RehashableHashtable<oopDesc*, mtSymbol>;
zgu@13195 358 template class Hashtable<Symbol*, mtSymbol>;
coleenp@13728 359 template class Hashtable<Klass*, mtClass>;
iklam@34257 360 template class Hashtable<InstanceKlass*, mtClass>;
zgu@13195 361 template class Hashtable<oop, mtClass>;
hseigel@20282 362 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
zgu@13195 363 template class Hashtable<oop, mtSymbol>;
mgerdin@26421 364 template class RehashableHashtable<oop, mtSymbol>;
hseigel@20282 365 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
zgu@13195 366 template class Hashtable<oopDesc*, mtSymbol>;
zgu@13195 367 template class Hashtable<Symbol*, mtClass>;
zgu@13195 368 template class HashtableEntry<Symbol*, mtSymbol>;
zgu@13195 369 template class HashtableEntry<Symbol*, mtClass>;
zgu@13195 370 template class HashtableEntry<oop, mtSymbol>;
zgu@13195 371 template class BasicHashtableEntry<mtSymbol>;
zgu@13195 372 template class BasicHashtableEntry<mtCode>;
zgu@13195 373 template class BasicHashtable<mtClass>;
iklam@34257 374 template class BasicHashtable<mtClassShared>;
zgu@13195 375 template class BasicHashtable<mtSymbol>;
zgu@13195 376 template class BasicHashtable<mtCode>;
zgu@13195 377 template class BasicHashtable<mtInternal>;
hseigel@38733 378 template class BasicHashtable<mtModule>;
mgronlun@36384 379 #if INCLUDE_TRACE
mgronlun@36384 380 template class Hashtable<Symbol*, mtTracing>;
mgronlun@36384 381 template class HashtableEntry<Symbol*, mtTracing>;
mgronlun@36384 382 template class BasicHashtable<mtTracing>;
mgronlun@36384 383 #endif
kvn@30593 384 template class BasicHashtable<mtCompiler>;
coleenp@46475 385
coleenp@46475 386 template void BasicHashtable<mtClass>::verify_table<DictionaryEntry>(char const*);
coleenp@46475 387 template void BasicHashtable<mtModule>::verify_table<ModuleEntry>(char const*);
coleenp@46475 388 template void BasicHashtable<mtModule>::verify_table<PackageEntry>(char const*);
coleenp@46475 389 template void BasicHashtable<mtClass>::verify_table<ProtectionDomainCacheEntry>(char const*);
coleenp@46545 390 template void BasicHashtable<mtClass>::verify_table<PlaceholderEntry>(char const*);
coleenp@46545 391