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 "code/dependencies.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(unsigned int hashValue) {
  49   BasicHashtableEntry<F>* entry;
  50 
  51   if (_free_list) {
  52     entry = _free_list;
  53     _free_list = _free_list->next();
  54   } else {
  55     if (_first_free_entry + _entry_size >= _end_block) {
  56       int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
  57       int len = _entry_size * block_size;
  58       len = 1 << log2_intptr(len); // round down to power of 2
  59       assert(len >= _entry_size, "");
  60       _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
  61       _end_block = _first_free_entry + len;
  62     }
  63     entry = (BasicHashtableEntry<F>*)_first_free_entry;
  64     _first_free_entry += _entry_size;
  65   }
  66 
  67   assert(_entry_size % HeapWordSize == 0, "");
  68   entry->set_hash(hashValue);
  69   return entry;
  70 }
  71 
  72 
  73 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
  74   HashtableEntry<T, F>* entry;
  75 
  76   entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
  77   entry->set_literal(obj);
  78   return entry;
  79 }
  80 
  81 // Check to see if the hashtable is unbalanced.  The caller set a flag to
  82 // rehash at the next safepoint.  If this bucket is 60 times greater than the
  83 // expected average bucket length, it's an unbalanced hashtable.
  84 // This is somewhat an arbitrary heuristic but if one bucket gets to
  85 // rehash_count which is currently 100, there's probably something wrong.
  86 
  87 template <MEMFLAGS F> bool BasicHashtable<F>::check_rehash_table(int count) {
  88   assert(table_size() != 0, "underflow");
  89   if (count > (((double)number_of_entries()/(double)table_size())*rehash_multiple)) {
  90     // Set a flag for the next safepoint, which should be at some guaranteed
  91     // safepoint interval.
  92     return true;
  93   }
  94   return false;
  95 }
  96 
  97 template <class T, MEMFLAGS F> juint Hashtable<T, F>::_seed = 0;
  98 
  99 // Create a new table and using alternate hash code, populate the new table
 100 // with the existing elements.   This can be used to change the hash code
 101 // and could in the future change the size of the table.
 102 
 103 template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) {
 104 
 105   // Initialize the global seed for hashing.
 106   _seed = AltHashing::compute_seed();
 107   assert(seed() != 0, "shouldn't be zero");
 108 
 109   int saved_entry_count = this->number_of_entries();
 110 
 111   // Iterate through the table and create a new entry for the new table
 112   for (int i = 0; i < new_table->table_size(); ++i) {
 113     for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) {
 114       HashtableEntry<T, F>* next = p->next();
 115       T string = p->literal();
 116       // Use alternate hashing algorithm on the symbol in the first table
 117       unsigned int hashValue = string->new_hash(seed());
 118       // Get a new index relative to the new table (can also change size)
 119       int index = new_table->hash_to_index(hashValue);
 120       p->set_hash(hashValue);
 121       // Keep the shared bit in the Hashtable entry to indicate that this entry
 122       // can't be deleted.   The shared bit is the LSB in the _next field so
 123       // walking the hashtable past these entries requires
 124       // BasicHashtableEntry::make_ptr() call.
 125       bool keep_shared = p->is_shared();
 126       this->unlink_entry(p);
 127       new_table->add_entry(index, p);
 128       if (keep_shared) {
 129         p->set_shared();
 130       }
 131       p = next;
 132     }
 133   }
 134   // give the new table the free list as well
 135   new_table->copy_freelist(this);
 136   assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?");
 137 
 138   // Destroy memory used by the buckets in the hashtable.  The memory
 139   // for the elements has been used in a new table and is not
 140   // destroyed.  The memory reuse will benefit resizing the SystemDictionary
 141   // to avoid a memory allocation spike at safepoint.
 142   BasicHashtable<F>::free_buckets();
 143 }
 144 
 145 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
 146   if (NULL != _buckets) {
 147     // Don't delete the buckets in the shared space.  They aren't
 148     // allocated by os::malloc
 149     if (!UseSharedSpaces ||
 150         !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {
 151        FREE_C_HEAP_ARRAY(HashtableBucket, _buckets, F);
 152     }
 153     _buckets = NULL;
 154   }
 155 }
 156 
 157 
 158 // Reverse the order of elements in the hash buckets.
 159 
 160 template <MEMFLAGS F> void BasicHashtable<F>::reverse() {
 161 
 162   for (int i = 0; i < _table_size; ++i) {
 163     BasicHashtableEntry<F>* new_list = NULL;
 164     BasicHashtableEntry<F>* p = bucket(i);
 165     while (p != NULL) {
 166       BasicHashtableEntry<F>* next = p->next();
 167       p->set_next(new_list);
 168       new_list = p;
 169       p = next;
 170     }
 171     *bucket_addr(i) = new_list;
 172   }
 173 }
 174 
 175 
 176 // Copy the table to the shared space.
 177 
 178 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) {
 179 
 180   // Dump the hash table entries.
 181 
 182   intptr_t *plen = (intptr_t*)(*top);
 183   *top += sizeof(*plen);
 184 
 185   int i;
 186   for (i = 0; i < _table_size; ++i) {
 187     for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
 188                               *p != NULL;
 189                                p = (*p)->next_addr()) {
 190       if (*top + entry_size() > end) {
 191         report_out_of_shared_space(SharedMiscData);
 192       }
 193       *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size());
 194       *top += entry_size();
 195     }
 196   }
 197   *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
 198 
 199   // Set the shared bit.
 200 
 201   for (i = 0; i < _table_size; ++i) {
 202     for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
 203       p->set_shared();
 204     }
 205   }
 206 }
 207 
 208 
 209 
 210 // Reverse the order of elements in the hash buckets.
 211 
 212 template <class T, MEMFLAGS F> void Hashtable<T, F>::reverse(void* boundary) {
 213 
 214   for (int i = 0; i < this->table_size(); ++i) {
 215     HashtableEntry<T, F>* high_list = NULL;
 216     HashtableEntry<T, F>* low_list = NULL;
 217     HashtableEntry<T, F>* last_low_entry = NULL;
 218     HashtableEntry<T, F>* p = bucket(i);
 219     while (p != NULL) {
 220       HashtableEntry<T, F>* next = p->next();
 221       if ((void*)p->literal() >= boundary) {
 222         p->set_next(high_list);
 223         high_list = p;
 224       } else {
 225         p->set_next(low_list);
 226         low_list = p;
 227         if (last_low_entry == NULL) {
 228           last_low_entry = p;
 229         }
 230       }
 231       p = next;
 232     }
 233     if (low_list != NULL) {
 234       *bucket_addr(i) = low_list;
 235       last_low_entry->set_next(high_list);
 236     } else {
 237       *bucket_addr(i) = high_list;
 238     }
 239   }
 240 }
 241 
 242 template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(Symbol *symbol) {
 243   return symbol->size() * HeapWordSize;
 244 }
 245 
 246 template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(oop oop) {
 247   // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
 248   // and the String.value array is shared by several Strings. However, starting from JDK8,
 249   // the String.value array is not shared anymore.
 250   assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
 251   return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;
 252 }
 253 
 254 // Dump footprint and bucket length statistics
 255 //
 256 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
 257 // add a new function Hashtable<T, F>::literal_size(MyNewType lit)
 258 
 259 template <class T, MEMFLAGS F> void Hashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
 260   NumberSeq summary;
 261   int literal_bytes = 0;
 262   for (int i = 0; i < this->table_size(); ++i) {
 263     int count = 0;
 264     for (HashtableEntry<T, F>* e = bucket(i);
 265        e != NULL; e = e->next()) {
 266       count++;
 267       literal_bytes += literal_size(e->literal());
 268     }
 269     summary.add((double)count);
 270   }
 271   double num_buckets = summary.num();
 272   double num_entries = summary.sum();
 273 
 274   int bucket_bytes = (int)num_buckets * sizeof(bucket(0));
 275   int entry_bytes  = (int)num_entries * sizeof(HashtableEntry<T, F>);
 276   int total_bytes = literal_bytes +  bucket_bytes + entry_bytes;
 277 
 278   double bucket_avg  = (num_buckets <= 0) ? 0 : (bucket_bytes  / num_buckets);
 279   double entry_avg   = (num_entries <= 0) ? 0 : (entry_bytes   / num_entries);
 280   double literal_avg = (num_entries <= 0) ? 0 : (literal_bytes / num_entries);
 281 
 282   st->print_cr("%s statistics:", table_name);
 283   st->print_cr("Number of buckets       : %9d = %9d bytes, avg %7.3f", (int)num_buckets, bucket_bytes,  bucket_avg);
 284   st->print_cr("Number of entries       : %9d = %9d bytes, avg %7.3f", (int)num_entries, entry_bytes,   entry_avg);
 285   st->print_cr("Number of literals      : %9d = %9d bytes, avg %7.3f", (int)num_entries, literal_bytes, literal_avg);
 286   st->print_cr("Total footprint         : %9s = %9d bytes", "", total_bytes);
 287   st->print_cr("Average bucket size     : %9.3f", summary.avg());
 288   st->print_cr("Variance of bucket size : %9.3f", summary.variance());
 289   st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
 290   st->print_cr("Maximum bucket size     : %9d", (int)summary.maximum());
 291 }
 292 
 293 
 294 // Dump the hash table buckets.
 295 
 296 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
 297   intptr_t len = _table_size * sizeof(HashtableBucket<F>);
 298   *(intptr_t*)(*top) = len;
 299   *top += sizeof(intptr_t);
 300 
 301   *(intptr_t*)(*top) = _number_of_entries;
 302   *top += sizeof(intptr_t);
 303 
 304   if (*top + len > end) {
 305     report_out_of_shared_space(SharedMiscData);
 306   }
 307   _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
 308   *top += len;
 309 }
 310 
 311 
 312 #ifndef PRODUCT
 313 
 314 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
 315   ResourceMark rm;
 316 
 317   for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
 318     HashtableEntry<T, F>* entry = bucket(i);
 319     while(entry != NULL) {
 320       tty->print("%d : ", i);
 321       entry->literal()->print();
 322       tty->cr();
 323       entry = entry->next();
 324     }
 325   }
 326 }
 327 
 328 
 329 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
 330   int count = 0;
 331   for (int i = 0; i < table_size(); i++) {
 332     for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
 333       ++count;
 334     }
 335   }
 336   assert(count == number_of_entries(), "number of hashtable entries incorrect");
 337 }
 338 
 339 
 340 #endif // PRODUCT
 341 
 342 #ifdef ASSERT
 343 
 344 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
 345   if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
 346     warning("Performance bug: SystemDictionary lookup_count=%d "
 347             "lookup_length=%d average=%lf load=%f",
 348             _lookup_count, _lookup_length,
 349             (double) _lookup_length / _lookup_count, load);
 350   }
 351 }
 352 
 353 #endif
 354 
 355 
 356 template<class T, class M> GenericHashtable<T, M>::GenericHashtable(int size, bool C_heap, MEMFLAGS memflag) {
 357   assert(size > 0, " Invalid hashtable size");
 358   _size    = size;
 359   _C_heap  = C_heap;
 360   _memflag = memflag;
 361   // Perform subtype-specific resource allocation
 362   _items = (C_heap) ?  NEW_C_HEAP_ARRAY(T*, size, memflag) : NEW_RESOURCE_ARRAY(T*, size);
 363   memset(_items, 0, sizeof(T*) * size);
 364 
 365   DEBUG_ONLY(_num_items = 0;)
 366 }
 367 
 368 template<class T, class M> GenericHashtable<T, M>::~GenericHashtable() {
 369   if (on_C_heap()) {
 370     // Check backing array
 371     for (int i = 0; i < size(); i++) {
 372       T* item = head(i);
 373       // Delete all items in linked list
 374       while (item != NULL) {
 375         T* next_item = item->next();
 376         delete item;
 377         DEBUG_ONLY(_num_items--);
 378         item = next_item;
 379       }
 380     }
 381     FREE_C_HEAP_ARRAY(T*, _items, _memflag);
 382     _items = NULL;
 383     assert (_num_items == 0, "Not all memory released");
 384   }
 385 }
 386 
 387 /**
 388  * Return a pointer to the item 'I' that is stored in the hashtable for
 389  * which match_item->equals(I) == true. If no such item is found, NULL
 390  * is returned.
 391  */
 392 template<class T, class F> T* GenericHashtable<T, F>::contains(T* match_item) {
 393   if (match_item != NULL) {
 394     int idx = index(match_item);
 395     return contains_impl(match_item, idx);
 396   }
 397   return NULL;
 398 }
 399 
 400 /**
 401  * Add item to the hashtable. Return 'true' if the item was added
 402  * and false otherwise.
 403  */
 404 template<class T, class F> bool GenericHashtable<T, F>::add(T* item) {
 405   if (item != NULL) {
 406     int idx = index(item);
 407     T* found_item = contains_impl(item, idx);
 408     if (found_item == NULL) {
 409       T* list_head = head(idx);
 410       item->set_next(list_head);
 411       item->set_prev(NULL);
 412 
 413       if (list_head != NULL) {
 414         list_head->set_prev(item);
 415       }
 416       set_head(item, idx);
 417       DEBUG_ONLY(_num_items++);
 418       return true;
 419     }
 420   }
 421   return false;
 422 }
 423 
 424 /**
 425  * Removes an item 'I' from the hashtable, if present. 'I' is removed, if
 426  * match_item->equals(I) == true. Removing an item from the hashtable does
 427  * not free memory.
 428  */
 429 template<class T, class F> T* GenericHashtable<T, F>::remove(T* match_item) {
 430   if (match_item != NULL) {
 431     int idx = index(match_item);
 432     T* found_item = contains_impl(match_item, idx);
 433     if (found_item != NULL) {
 434       // Remove item from linked list
 435       T* prev = found_item->prev();
 436       T* next = found_item->next();
 437       if (prev != NULL) {
 438         prev->set_next(next);
 439       } else {
 440         set_head(next, idx);
 441       }
 442       if (next != NULL) {
 443         next->set_prev(prev);
 444       }
 445 
 446       DEBUG_ONLY(_num_items--);
 447       return found_item;
 448     }
 449   }
 450   return NULL;
 451 }
 452 
 453 
 454 template<class T, class F> T* GenericHashtable<T, F>::contains_impl(T* item, int idx) {
 455   T* current_item = head(idx);
 456   while (current_item != NULL) {
 457     if (current_item->equals(item)) {
 458       return current_item;
 459     }
 460     current_item = current_item->next();
 461   }
 462   return NULL;
 463 }
 464 
 465 
 466 // Explicitly instantiate these types
 467 template class Hashtable<ConstantPool*, mtClass>;
 468 template class Hashtable<Symbol*, mtSymbol>;
 469 template class Hashtable<Klass*, mtClass>;
 470 template class Hashtable<oop, mtClass>;
 471 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
 472 template class Hashtable<oop, mtSymbol>;
 473 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
 474 template class Hashtable<oopDesc*, mtSymbol>;
 475 template class Hashtable<Symbol*, mtClass>;
 476 template class HashtableEntry<Symbol*, mtSymbol>;
 477 template class HashtableEntry<Symbol*, mtClass>;
 478 template class HashtableEntry<oop, mtSymbol>;
 479 template class BasicHashtableEntry<mtSymbol>;
 480 template class BasicHashtableEntry<mtCode>;
 481 template class BasicHashtable<mtClass>;
 482 template class BasicHashtable<mtSymbol>;
 483 template class BasicHashtable<mtCode>;
 484 template class BasicHashtable<mtInternal>;
 485 
 486 template class GenericHashtable<DependencySignature, ResourceObj>;