1 /*
   2  * Copyright (c) 2003, 2019, 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/classLoaderData.inline.hpp"
  27 #include "classfile/dictionary.hpp"
  28 #include "classfile/protectionDomainCache.hpp"
  29 #include "classfile/systemDictionary.hpp"
  30 #include "logging/log.hpp"
  31 #include "logging/logStream.hpp"
  32 #include "memory/iterator.hpp"
  33 #include "memory/metaspaceClosure.hpp"
  34 #include "memory/resourceArea.hpp"
  35 #include "oops/oop.inline.hpp"
  36 #include "runtime/atomic.hpp"
  37 #include "runtime/orderAccess.hpp"
  38 #include "runtime/mutexLocker.hpp"
  39 #include "runtime/safepointVerifiers.hpp"
  40 #include "utilities/hashtable.inline.hpp"
  41 
  42 // Optimization: if any dictionary needs resizing, we set this flag,
  43 // so that we dont't have to walk all dictionaries to check if any actually
  44 // needs resizing, which is costly to do at Safepoint.
  45 bool Dictionary::_some_dictionary_needs_resizing = false;
  46 
  47 Dictionary::Dictionary(ClassLoaderData* loader_data, int table_size, bool resizable)
  48   : Hashtable<InstanceKlass*, mtClass>(table_size, (int)sizeof(DictionaryEntry)),
  49     _resizable(resizable), _needs_resizing(false), _loader_data(loader_data) {
  50 };
  51 
  52 
  53 Dictionary::Dictionary(ClassLoaderData* loader_data,
  54                        int table_size, HashtableBucket<mtClass>* t,
  55                        int number_of_entries, bool resizable)
  56   : Hashtable<InstanceKlass*, mtClass>(table_size, (int)sizeof(DictionaryEntry), t, number_of_entries),
  57     _resizable(resizable), _needs_resizing(false), _loader_data(loader_data) {
  58 };
  59 
  60 Dictionary::~Dictionary() {
  61   DictionaryEntry* probe = NULL;
  62   for (int index = 0; index < table_size(); index++) {
  63     for (DictionaryEntry** p = bucket_addr(index); *p != NULL; ) {
  64       probe = *p;
  65       *p = probe->next();
  66       free_entry(probe);
  67     }
  68   }
  69   assert(number_of_entries() == 0, "should have removed all entries");
  70   assert(new_entry_free_list() == NULL, "entry present on Dictionary's free list");
  71 }
  72 
  73 DictionaryEntry* Dictionary::new_entry(unsigned int hash, InstanceKlass* klass) {
  74   DictionaryEntry* entry = (DictionaryEntry*)Hashtable<InstanceKlass*, mtClass>::allocate_new_entry(hash, klass);
  75   entry->set_pd_set(NULL);
  76   assert(klass->is_instance_klass(), "Must be");
  77   return entry;
  78 }
  79 
  80 
  81 void Dictionary::free_entry(DictionaryEntry* entry) {
  82   // avoid recursion when deleting linked list
  83   // pd_set is accessed during a safepoint.
  84   // This doesn't require a lock because nothing is reading this
  85   // entry anymore.  The ClassLoader is dead.
  86   while (entry->pd_set() != NULL) {
  87     ProtectionDomainEntry* to_delete = entry->pd_set();
  88     entry->set_pd_set(to_delete->next());
  89     delete to_delete;
  90   }
  91   // Unlink from the Hashtable prior to freeing
  92   unlink_entry(entry);
  93   FREE_C_HEAP_ARRAY(char, entry);
  94 }
  95 
  96 const int _resize_load_trigger = 5;       // load factor that will trigger the resize
  97 const double _resize_factor    = 2.0;     // by how much we will resize using current number of entries
  98 const int _resize_max_size     = 40423;   // the max dictionary size allowed
  99 const int _primelist[] = {107, 1009, 2017, 4049, 5051, 10103, 20201, _resize_max_size};
 100 const int _prime_array_size = sizeof(_primelist)/sizeof(int);
 101 
 102 // Calculate next "good" dictionary size based on requested count
 103 static int calculate_dictionary_size(int requested) {
 104   int newsize = _primelist[0];
 105   int index = 0;
 106   for (newsize = _primelist[index]; index < (_prime_array_size - 1);
 107        newsize = _primelist[++index]) {
 108     if (requested <= newsize) {
 109       break;
 110     }
 111   }
 112   return newsize;
 113 }
 114 
 115 bool Dictionary::does_any_dictionary_needs_resizing() {
 116   return Dictionary::_some_dictionary_needs_resizing;
 117 }
 118 
 119 void Dictionary::check_if_needs_resize() {
 120   if (_resizable == true) {
 121     if (number_of_entries() > (_resize_load_trigger*table_size())) {
 122       _needs_resizing = true;
 123       Dictionary::_some_dictionary_needs_resizing = true;
 124     }
 125   }
 126 }
 127 
 128 bool Dictionary::resize_if_needed() {
 129   int desired_size = 0;
 130   if (_needs_resizing == true) {
 131     desired_size = calculate_dictionary_size((int)(_resize_factor*number_of_entries()));
 132     if (desired_size >= _resize_max_size) {
 133       desired_size = _resize_max_size;
 134       // We have reached the limit, turn resizing off
 135       _resizable = false;
 136     }
 137     if ((desired_size != 0) && (desired_size != table_size())) {
 138       if (!resize(desired_size)) {
 139         // Something went wrong, turn resizing off
 140         _resizable = false;
 141       }
 142     }
 143   }
 144 
 145   _needs_resizing = false;
 146   Dictionary::_some_dictionary_needs_resizing = false;
 147 
 148   return (desired_size != 0);
 149 }
 150 
 151 bool DictionaryEntry::contains_protection_domain(oop protection_domain) const {
 152   // Lock the pd_set list.  This lock cannot safepoint since the caller holds
 153   // a Dictionary entry, which can be moved if the Dictionary is resized.
 154   MutexLocker ml(ProtectionDomainSet_lock, Mutex::_no_safepoint_check_flag);
 155 #ifdef ASSERT
 156   if (protection_domain == instance_klass()->protection_domain()) {
 157     // Ensure this doesn't show up in the pd_set (invariant)
 158     bool in_pd_set = false;
 159     for (ProtectionDomainEntry* current = pd_set();
 160                                 current != NULL;
 161                                 current = current->next()) {
 162       if (current->object_no_keepalive() == protection_domain) {
 163         in_pd_set = true;
 164         break;
 165       }
 166     }
 167     if (in_pd_set) {
 168       assert(false, "A klass's protection domain should not show up "
 169                     "in its sys. dict. PD set");
 170     }
 171   }
 172 #endif /* ASSERT */
 173 
 174   if (protection_domain == instance_klass()->protection_domain()) {
 175     // Succeeds trivially
 176     return true;
 177   }
 178 
 179   for (ProtectionDomainEntry* current = pd_set();
 180                               current != NULL;
 181                               current = current->next()) {
 182     if (current->object_no_keepalive() == protection_domain) return true;
 183   }
 184   return false;
 185 }
 186 
 187 
 188 void DictionaryEntry::add_protection_domain(Dictionary* dict, Handle protection_domain) {
 189   assert_locked_or_safepoint(SystemDictionary_lock);
 190   if (!contains_protection_domain(protection_domain())) {
 191     ProtectionDomainCacheEntry* entry = SystemDictionary::cache_get(protection_domain);
 192     // The pd_set in the dictionary entry is protected by a low level lock.
 193     // With concurrent PD table cleanup, these links could be broken.
 194     MutexLocker ml(ProtectionDomainSet_lock, Mutex::_no_safepoint_check_flag);
 195     ProtectionDomainEntry* new_head =
 196                 new ProtectionDomainEntry(entry, pd_set());
 197     set_pd_set(new_head);
 198   }
 199   LogTarget(Trace, protectiondomain) lt;
 200   if (lt.is_enabled()) {
 201     LogStream ls(lt);
 202     print_count(&ls);
 203   }
 204 }
 205 
 206 //   Just the classes from defining class loaders
 207 void Dictionary::classes_do(void f(InstanceKlass*)) {
 208   for (int index = 0; index < table_size(); index++) {
 209     for (DictionaryEntry* probe = bucket(index);
 210                           probe != NULL;
 211                           probe = probe->next()) {
 212       InstanceKlass* k = probe->instance_klass();
 213       if (loader_data() == k->class_loader_data()) {
 214         f(k);
 215       }
 216     }
 217   }
 218 }
 219 
 220 // Added for initialize_itable_for_klass to handle exceptions
 221 //   Just the classes from defining class loaders
 222 void Dictionary::classes_do(void f(InstanceKlass*, TRAPS), TRAPS) {
 223   for (int index = 0; index < table_size(); index++) {
 224     for (DictionaryEntry* probe = bucket(index);
 225                           probe != NULL;
 226                           probe = probe->next()) {
 227       InstanceKlass* k = probe->instance_klass();
 228       if (loader_data() == k->class_loader_data()) {
 229         f(k, CHECK);
 230       }
 231     }
 232   }
 233 }
 234 
 235 // All classes, and their class loaders, including initiating class loaders
 236 void Dictionary::all_entries_do(KlassClosure* closure) {
 237   for (int index = 0; index < table_size(); index++) {
 238     for (DictionaryEntry* probe = bucket(index);
 239                           probe != NULL;
 240                           probe = probe->next()) {
 241       InstanceKlass* k = probe->instance_klass();
 242       closure->do_klass(k);
 243     }
 244   }
 245 }
 246 
 247 // Used to scan and relocate the classes during CDS archive dump.
 248 void Dictionary::classes_do(MetaspaceClosure* it) {
 249   assert(DumpSharedSpaces || DynamicDumpSharedSpaces, "dump-time only");
 250   for (int index = 0; index < table_size(); index++) {
 251     for (DictionaryEntry* probe = bucket(index);
 252                           probe != NULL;
 253                           probe = probe->next()) {
 254       it->push(probe->klass_addr());
 255     }
 256   }
 257 }
 258 
 259 
 260 
 261 // Add a loaded class to the dictionary.
 262 // Readers of the SystemDictionary aren't always locked, so _buckets
 263 // is volatile. The store of the next field in the constructor is
 264 // also cast to volatile;  we do this to ensure store order is maintained
 265 // by the compilers.
 266 
 267 void Dictionary::add_klass(unsigned int hash, Symbol* class_name,
 268                            InstanceKlass* obj) {
 269   assert_locked_or_safepoint(SystemDictionary_lock);
 270   assert(obj != NULL, "adding NULL obj");
 271   assert(obj->name() == class_name, "sanity check on name");
 272 
 273   DictionaryEntry* entry = new_entry(hash, obj);
 274   int index = hash_to_index(hash);
 275   add_entry(index, entry);
 276   check_if_needs_resize();
 277 }
 278 
 279 
 280 // This routine does not lock the dictionary.
 281 //
 282 // Since readers don't hold a lock, we must make sure that system
 283 // dictionary entries are only removed at a safepoint (when only one
 284 // thread is running), and are added to in a safe way (all links must
 285 // be updated in an MT-safe manner).
 286 //
 287 // Callers should be aware that an entry could be added just after
 288 // _buckets[index] is read here, so the caller will not see the new entry.
 289 DictionaryEntry* Dictionary::get_entry(int index, unsigned int hash,
 290                                        Symbol* class_name) {
 291   for (DictionaryEntry* entry = bucket(index);
 292                         entry != NULL;
 293                         entry = entry->next()) {
 294     if (entry->hash() == hash && entry->equals(class_name)) {
 295       return entry;
 296     }
 297   }
 298   return NULL;
 299 }
 300 
 301 
 302 InstanceKlass* Dictionary::find(unsigned int hash, Symbol* name,
 303                                 Handle protection_domain) {
 304   NoSafepointVerifier nsv;
 305 
 306   int index = hash_to_index(hash);
 307   DictionaryEntry* entry = get_entry(index, hash, name);
 308   if (entry != NULL && entry->is_valid_protection_domain(protection_domain)) {
 309     return entry->instance_klass();
 310   } else {
 311     return NULL;
 312   }
 313 }
 314 
 315 InstanceKlass* Dictionary::find_class(int index, unsigned int hash,
 316                                       Symbol* name) {
 317   assert_locked_or_safepoint(SystemDictionary_lock);
 318   assert (index == index_for(name), "incorrect index?");
 319 
 320   DictionaryEntry* entry = get_entry(index, hash, name);
 321   return (entry != NULL) ? entry->instance_klass() : NULL;
 322 }
 323 
 324 
 325 void Dictionary::add_protection_domain(int index, unsigned int hash,
 326                                        InstanceKlass* klass,
 327                                        Handle protection_domain,
 328                                        TRAPS) {
 329   Symbol*  klass_name = klass->name();
 330   DictionaryEntry* entry = get_entry(index, hash, klass_name);
 331 
 332   assert(entry != NULL,"entry must be present, we just created it");
 333   assert(protection_domain() != NULL,
 334          "real protection domain should be present");
 335 
 336   entry->add_protection_domain(this, protection_domain);
 337 
 338 #ifdef ASSERT
 339   assert(loader_data() != ClassLoaderData::the_null_class_loader_data(), "doesn't make sense");
 340 #endif
 341 
 342   assert(entry->contains_protection_domain(protection_domain()),
 343          "now protection domain should be present");
 344 }
 345 
 346 
 347 bool Dictionary::is_valid_protection_domain(unsigned int hash,
 348                                             Symbol* name,
 349                                             Handle protection_domain) {
 350   int index = hash_to_index(hash);
 351   DictionaryEntry* entry = get_entry(index, hash, name);
 352   return entry->is_valid_protection_domain(protection_domain);
 353 }
 354 
 355 // During class loading we may have cached a protection domain that has
 356 // since been unreferenced, so this entry should be cleared.
 357 void Dictionary::clean_cached_protection_domains() {
 358   assert_locked_or_safepoint(SystemDictionary_lock);
 359 
 360   if (loader_data()->is_the_null_class_loader_data()) {
 361     // Classes in the boot loader are not loaded with protection domains
 362     return;
 363   }
 364 
 365   for (int index = 0; index < table_size(); index++) {
 366     for (DictionaryEntry* probe = bucket(index);
 367                           probe != NULL;
 368                           probe = probe->next()) {
 369       Klass* e = probe->instance_klass();
 370 
 371       MutexLocker ml(ProtectionDomainSet_lock, Mutex::_no_safepoint_check_flag);
 372       ProtectionDomainEntry* current = probe->pd_set();
 373       ProtectionDomainEntry* prev = NULL;
 374       while (current != NULL) {
 375         if (current->object_no_keepalive() == NULL) {
 376           LogTarget(Debug, protectiondomain) lt;
 377           if (lt.is_enabled()) {
 378             ResourceMark rm;
 379             // Print out trace information
 380             LogStream ls(lt);
 381             ls.print_cr("PD in set is not alive:");
 382             ls.print("class loader: "); loader_data()->class_loader()->print_value_on(&ls);
 383             ls.print(" loading: "); probe->instance_klass()->print_value_on(&ls);
 384             ls.cr();
 385           }
 386           if (probe->pd_set() == current) {
 387             probe->set_pd_set(current->next());
 388           } else {
 389             assert(prev != NULL, "should be set by alive entry");
 390             prev->set_next(current->next());
 391           }
 392           ProtectionDomainEntry* to_delete = current;
 393           current = current->next();
 394           delete to_delete;
 395         } else {
 396           prev = current;
 397           current = current->next();
 398         }
 399       }
 400     }
 401   }
 402 }
 403 
 404 
 405 SymbolPropertyTable::SymbolPropertyTable(int table_size)
 406   : Hashtable<Symbol*, mtSymbol>(table_size, sizeof(SymbolPropertyEntry))
 407 {
 408 }
 409 SymbolPropertyTable::SymbolPropertyTable(int table_size, HashtableBucket<mtSymbol>* t,
 410                                          int number_of_entries)
 411   : Hashtable<Symbol*, mtSymbol>(table_size, sizeof(SymbolPropertyEntry), t, number_of_entries)
 412 {
 413 }
 414 
 415 
 416 SymbolPropertyEntry* SymbolPropertyTable::find_entry(int index, unsigned int hash,
 417                                                      Symbol* sym,
 418                                                      intptr_t sym_mode) {
 419   assert(index == index_for(sym, sym_mode), "incorrect index?");
 420   for (SymbolPropertyEntry* p = bucket(index); p != NULL; p = p->next()) {
 421     if (p->hash() == hash && p->symbol() == sym && p->symbol_mode() == sym_mode) {
 422       return p;
 423     }
 424   }
 425   return NULL;
 426 }
 427 
 428 
 429 SymbolPropertyEntry* SymbolPropertyTable::add_entry(int index, unsigned int hash,
 430                                                     Symbol* sym, intptr_t sym_mode) {
 431   assert_locked_or_safepoint(SystemDictionary_lock);
 432   assert(index == index_for(sym, sym_mode), "incorrect index?");
 433   assert(find_entry(index, hash, sym, sym_mode) == NULL, "no double entry");
 434 
 435   SymbolPropertyEntry* p = new_entry(hash, sym, sym_mode);
 436   Hashtable<Symbol*, mtSymbol>::add_entry(index, p);
 437   return p;
 438 }
 439 
 440 void SymbolPropertyTable::oops_do(OopClosure* f) {
 441   for (int index = 0; index < table_size(); index++) {
 442     for (SymbolPropertyEntry* p = bucket(index); p != NULL; p = p->next()) {
 443       if (p->method_type() != NULL) {
 444         f->do_oop(p->method_type_addr());
 445       }
 446     }
 447   }
 448 }
 449 
 450 void SymbolPropertyTable::methods_do(void f(Method*)) {
 451   for (int index = 0; index < table_size(); index++) {
 452     for (SymbolPropertyEntry* p = bucket(index); p != NULL; p = p->next()) {
 453       Method* prop = p->method();
 454       if (prop != NULL) {
 455         f((Method*)prop);
 456       }
 457     }
 458   }
 459 }
 460 
 461 void DictionaryEntry::verify_protection_domain_set() {
 462   MutexLocker ml(ProtectionDomainSet_lock, Mutex::_no_safepoint_check_flag);
 463   for (ProtectionDomainEntry* current = pd_set(); // accessed at a safepoint
 464                               current != NULL;
 465                               current = current->_next) {
 466     guarantee(oopDesc::is_oop_or_null(current->_pd_cache->object_no_keepalive()), "Invalid oop");
 467   }
 468 }
 469 
 470 void DictionaryEntry::print_count(outputStream *st) {
 471   MutexLocker ml(ProtectionDomainSet_lock, Mutex::_no_safepoint_check_flag);
 472   int count = 0;
 473   for (ProtectionDomainEntry* current = pd_set();  // accessed inside SD lock
 474                               current != NULL;
 475                               current = current->_next) {
 476     count++;
 477   }
 478   st->print_cr("pd set count = #%d", count);
 479 }
 480 
 481 // ----------------------------------------------------------------------------
 482 
 483 void Dictionary::print_on(outputStream* st) const {
 484   ResourceMark rm;
 485 
 486   assert(loader_data() != NULL, "loader data should not be null");
 487   st->print_cr("Java dictionary (table_size=%d, classes=%d, resizable=%s)",
 488                table_size(), number_of_entries(), BOOL_TO_STR(_resizable));
 489   st->print_cr("^ indicates that initiating loader is different from defining loader");
 490 
 491   for (int index = 0; index < table_size(); index++) {
 492     for (DictionaryEntry* probe = bucket(index);
 493                           probe != NULL;
 494                           probe = probe->next()) {
 495       Klass* e = probe->instance_klass();
 496       bool is_defining_class =
 497          (loader_data() == e->class_loader_data());
 498       st->print("%4d: %s%s", index, is_defining_class ? " " : "^", e->external_name());
 499       ClassLoaderData* cld = e->class_loader_data();
 500       if (!loader_data()->is_the_null_class_loader_data()) {
 501         // Class loader output for the dictionary for the null class loader data is
 502         // redundant and obvious.
 503         st->print(", ");
 504         cld->print_value_on(st);
 505       }
 506       st->cr();
 507     }
 508   }
 509   tty->cr();
 510 }
 511 
 512 void DictionaryEntry::verify() {
 513   Klass* e = instance_klass();
 514   guarantee(e->is_instance_klass(),
 515                           "Verify of dictionary failed");
 516   e->verify();
 517   verify_protection_domain_set();
 518 }
 519 
 520 void Dictionary::verify() {
 521   guarantee(number_of_entries() >= 0, "Verify of dictionary failed");
 522 
 523   ClassLoaderData* cld = loader_data();
 524   // class loader must be present;  a null class loader is the
 525   // boostrap loader
 526   guarantee(cld != NULL ||
 527             cld->class_loader() == NULL ||
 528             cld->class_loader()->is_instance(),
 529             "checking type of class_loader");
 530 
 531   ResourceMark rm;
 532   stringStream tempst;
 533   tempst.print("System Dictionary for %s class loader", cld->loader_name_and_id());
 534   verify_table<DictionaryEntry>(tempst.as_string());
 535 }