1 /*
   2  * Copyright (c) 1997, 2021, 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 "jvm.h"
  27 #include "cds/metaspaceShared.hpp"
  28 #include "classfile/classLoaderDataGraph.hpp"
  29 #include "classfile/javaClasses.hpp"
  30 #include "classfile/systemDictionary.hpp"
  31 #include "classfile/vmSymbols.hpp"
  32 #include "interpreter/linkResolver.hpp"
  33 #include "logging/log.hpp"
  34 #include "logging/logStream.hpp"
  35 #include "memory/resourceArea.hpp"
  36 #include "memory/universe.hpp"
  37 #include "oops/instanceKlass.inline.hpp"
  38 #include "oops/klass.inline.hpp"
  39 #include "oops/klassVtable.hpp"
  40 #include "oops/method.hpp"
  41 #include "oops/objArrayOop.hpp"
  42 #include "oops/oop.inline.hpp"
  43 #include "runtime/flags/flagSetting.hpp"
  44 #include "runtime/java.hpp"
  45 #include "runtime/handles.inline.hpp"
  46 #include "runtime/safepointVerifiers.hpp"
  47 #include "utilities/copy.hpp"
  48 
  49 inline InstanceKlass* klassVtable::ik() const {
  50   return InstanceKlass::cast(_klass);
  51 }
  52 
  53 bool klassVtable::is_preinitialized_vtable() {
  54   return _klass->is_shared() && !MetaspaceShared::remapped_readwrite() && _klass->verified_at_dump_time();
  55 }
  56 
  57 
  58 // this function computes the vtable size (including the size needed for miranda
  59 // methods) and the number of miranda methods in this class.
  60 // Note on Miranda methods: Let's say there is a class C that implements
  61 // interface I, and none of C's superclasses implements I.
  62 // Let's say there is an abstract method m in I that neither C
  63 // nor any of its super classes implement (i.e there is no method of any access,
  64 // with the same name and signature as m), then m is a Miranda method which is
  65 // entered as a public abstract method in C's vtable.  From then on it should
  66 // treated as any other public method in C for method over-ride purposes.
  67 void klassVtable::compute_vtable_size_and_num_mirandas(
  68     int* vtable_length_ret, int* num_new_mirandas,
  69     GrowableArray<Method*>* all_mirandas, const Klass* super,
  70     Array<Method*>* methods, AccessFlags class_flags, u2 major_version,
  71     Handle classloader, Symbol* classname, Array<InstanceKlass*>* local_interfaces) {
  72   NoSafepointVerifier nsv;
  73 
  74   // set up default result values
  75   int vtable_length = 0;
  76 
  77   // start off with super's vtable length
  78   vtable_length = super == NULL ? 0 : super->vtable_length();
  79 
  80   // go thru each method in the methods table to see if it needs a new entry
  81   int len = methods->length();
  82   for (int i = 0; i < len; i++) {
  83     Method* method = methods->at(i);
  84 
  85     if (needs_new_vtable_entry(method, super, classloader, classname, class_flags, major_version)) {
  86       assert(!method->is_private(), "private methods should not need a vtable entry");
  87       vtable_length += vtableEntry::size(); // we need a new entry
  88     }
  89   }
  90 
  91   GrowableArray<Method*> new_mirandas(20);
  92   // compute the number of mirandas methods that must be added to the end
  93   get_mirandas(&new_mirandas, all_mirandas, super, methods, NULL, local_interfaces,
  94                class_flags.is_interface());
  95   *num_new_mirandas = new_mirandas.length();
  96 
  97   // Interfaces do not need interface methods in their vtables
  98   // This includes miranda methods and during later processing, default methods
  99   if (!class_flags.is_interface()) {
 100      vtable_length += *num_new_mirandas * vtableEntry::size();
 101   }
 102 
 103   if (Universe::is_bootstrapping() && vtable_length == 0) {
 104     // array classes don't have their superclass set correctly during
 105     // bootstrapping
 106     vtable_length = Universe::base_vtable_size();
 107   }
 108 
 109   if (super == NULL && vtable_length != Universe::base_vtable_size()) {
 110     if (Universe::is_bootstrapping()) {
 111       // Someone is attempting to override java.lang.Object incorrectly on the
 112       // bootclasspath.  The JVM cannot recover from this error including throwing
 113       // an exception
 114       vm_exit_during_initialization("Incompatible definition of java.lang.Object");
 115     } else {
 116       // Someone is attempting to redefine java.lang.Object incorrectly.  The
 117       // only way this should happen is from
 118       // SystemDictionary::resolve_from_stream(), which will detect this later
 119       // and throw a security exception.  So don't assert here to let
 120       // the exception occur.
 121       vtable_length = Universe::base_vtable_size();
 122     }
 123   }
 124   assert(vtable_length % vtableEntry::size() == 0, "bad vtable length");
 125   assert(vtable_length >= Universe::base_vtable_size(), "vtable too small");
 126 
 127   *vtable_length_ret = vtable_length;
 128 }
 129 
 130 // Copy super class's vtable to the first part (prefix) of this class's vtable,
 131 // and return the number of entries copied.  Expects that 'super' is the Java
 132 // super class (arrays can have "array" super classes that must be skipped).
 133 int klassVtable::initialize_from_super(Klass* super) {
 134   if (super == NULL) {
 135     return 0;
 136   } else if (is_preinitialized_vtable()) {
 137     // A shared class' vtable is preinitialized at dump time. No need to copy
 138     // methods from super class for shared class, as that was already done
 139     // during archiving time. However, if Jvmti has redefined a class,
 140     // copy super class's vtable in case the super class has changed.
 141     return super->vtable().length();
 142   } else {
 143     // copy methods from superKlass
 144     klassVtable superVtable = super->vtable();
 145     assert(superVtable.length() <= _length, "vtable too short");
 146 #ifdef ASSERT
 147     superVtable.verify(tty, true);
 148 #endif
 149     superVtable.copy_vtable_to(table());
 150     if (log_develop_is_enabled(Trace, vtables)) {
 151       ResourceMark rm;
 152       log_develop_trace(vtables)("copy vtable from %s to %s size %d",
 153                                  super->internal_name(), klass()->internal_name(),
 154                                  _length);
 155     }
 156     return superVtable.length();
 157   }
 158 }
 159 
 160 //
 161 // Revised lookup semantics   introduced 1.3 (Kestrel beta)
 162 void klassVtable::initialize_vtable(GrowableArray<InstanceKlass*>* supers) {
 163 
 164   // Note:  Arrays can have intermediate array supers.  Use java_super to skip them.
 165   InstanceKlass* super = _klass->java_super();
 166 
 167   bool is_shared = _klass->is_shared();
 168   Thread* current = Thread::current();
 169 
 170   if (!_klass->is_array_klass()) {
 171     ResourceMark rm(current);
 172     log_develop_debug(vtables)("Initializing: %s", _klass->name()->as_C_string());
 173   }
 174 
 175 #ifdef ASSERT
 176   oop* end_of_obj = (oop*)_klass + _klass->size();
 177   oop* end_of_vtable = (oop*)&table()[_length];
 178   assert(end_of_vtable <= end_of_obj, "vtable extends beyond end");
 179 #endif
 180 
 181   if (Universe::is_bootstrapping()) {
 182     assert(!is_shared, "sanity");
 183     // just clear everything
 184     for (int i = 0; i < _length; i++) table()[i].clear();
 185     return;
 186   }
 187 
 188   int super_vtable_len = initialize_from_super(super);
 189   if (_klass->is_array_klass()) {
 190     assert(super_vtable_len == _length, "arrays shouldn't introduce new methods");
 191   } else {
 192     assert(_klass->is_instance_klass(), "must be InstanceKlass");
 193 
 194     Array<Method*>* methods = ik()->methods();
 195     int len = methods->length();
 196     int initialized = super_vtable_len;
 197 
 198     // Check each of this class's methods against super;
 199     // if override, replace in copy of super vtable, otherwise append to end
 200     for (int i = 0; i < len; i++) {
 201       // update_inherited_vtable can stop for gc - ensure using handles
 202       methodHandle mh(current, methods->at(i));
 203 
 204       bool needs_new_entry = update_inherited_vtable(current, mh, super_vtable_len, -1, supers);
 205 
 206       if (needs_new_entry) {
 207         put_method_at(mh(), initialized);
 208         mh->set_vtable_index(initialized); // set primary vtable index
 209         initialized++;
 210       }
 211     }
 212 
 213     // update vtable with default_methods
 214     Array<Method*>* default_methods = ik()->default_methods();
 215     if (default_methods != NULL) {
 216       len = default_methods->length();
 217       if (len > 0) {
 218         Array<int>* def_vtable_indices = ik()->default_vtable_indices();
 219         assert(def_vtable_indices != NULL, "should be created");
 220         assert(def_vtable_indices->length() == len, "reinit vtable len?");
 221         for (int i = 0; i < len; i++) {
 222           bool needs_new_entry;
 223           {
 224             // Reduce the scope of this handle so that it is fetched again.
 225             // The methodHandle keeps it from being deleted by RedefineClasses while
 226             // we're using it.
 227             methodHandle mh(current, default_methods->at(i));
 228             assert(!mh->is_private(), "private interface method in the default method list");
 229             needs_new_entry = update_inherited_vtable(current, mh, super_vtable_len, i, supers);
 230           }
 231 
 232           // needs new entry
 233           if (needs_new_entry) {
 234             // Refetch this default method in case of redefinition that might
 235             // happen during constraint checking in the update_inherited_vtable call above.
 236             Method* method = default_methods->at(i);
 237             put_method_at(method, initialized);
 238             if (is_preinitialized_vtable()) {
 239               // At runtime initialize_vtable is rerun for a shared class
 240               // (loaded by the non-boot loader) as part of link_class_impl().
 241               // The dumptime vtable index should be the same as the runtime index.
 242               assert(def_vtable_indices->at(i) == initialized,
 243                      "dump time vtable index is different from runtime index");
 244             } else {
 245               def_vtable_indices->at_put(i, initialized); //set vtable index
 246             }
 247             initialized++;
 248           }
 249         }
 250       }
 251     }
 252 
 253     // add miranda methods; it will also return the updated initialized
 254     // Interfaces do not need interface methods in their vtables
 255     // This includes miranda methods and during later processing, default methods
 256     if (!ik()->is_interface()) {
 257       initialized = fill_in_mirandas(current, initialized);
 258     }
 259 
 260     // In class hierarchies where the accessibility is not increasing (i.e., going from private ->
 261     // package_private -> public/protected), the vtable might actually be smaller than our initial
 262     // calculation, for classfile versions for which we do not do transitive override
 263     // calculations.
 264     if (ik()->major_version() >= VTABLE_TRANSITIVE_OVERRIDE_VERSION) {
 265       assert(initialized == _length, "vtable initialization failed");
 266     } else {
 267       assert(initialized <= _length, "vtable initialization failed");
 268       for(;initialized < _length; initialized++) {
 269         table()[initialized].clear();
 270       }
 271     }
 272     NOT_PRODUCT(verify(tty, true));
 273   }
 274 }
 275 
 276 // Returns true iff super_method can be overridden by a method in targetclassname
 277 // See JLS 3rd edition 8.4.6.1
 278 // Assumes name-signature match
 279 // Note that the InstanceKlass of the method in the targetclassname has not always been created yet
 280 static bool can_be_overridden(Method* super_method, Handle targetclassloader, Symbol* targetclassname) {
 281    // Private methods can not be overridden
 282    assert(!super_method->is_private(), "shouldn't call with a private method");
 283 
 284    // If super method is accessible, then override
 285    if ((super_method->is_protected()) ||
 286        (super_method->is_public())) {
 287      return true;
 288    }
 289    // Package-private methods are not inherited outside of package
 290    assert(super_method->is_package_private(), "must be package private");
 291    return(super_method->method_holder()->is_same_class_package(targetclassloader(), targetclassname));
 292 }
 293 
 294 
 295 // Called for cases where a method does not override its superclass' vtable entry
 296 // For bytecodes not produced by javac together it is possible that a method does not override
 297 // the superclass's method, but might indirectly override a super-super class's vtable entry
 298 // If none found, return a null superk, else return the superk of the method this does override
 299 // For public and protected methods: if they override a superclass, they will
 300 // also be overridden themselves appropriately.
 301 // Private methods do not override, and are not overridden and are not in the vtable.
 302 // Package Private methods are trickier:
 303 // e.g. P1.A, pub m
 304 // P2.B extends A, package private m
 305 // P1.C extends B, public m
 306 // P1.C.m needs to override P1.A.m and can not override P2.B.m
 307 // Therefore: all package private methods need their own vtable entries for
 308 // them to be the root of an inheritance overriding decision
 309 // Package private methods may also override other vtable entries
 310 InstanceKlass* klassVtable::find_transitive_override(InstanceKlass* initialsuper,
 311                                                      const methodHandle& target_method,
 312                                                      int vtable_index,
 313                                                      Handle target_loader,
 314                                                      Symbol* target_classname) {
 315 
 316   InstanceKlass* superk = initialsuper;
 317   while (superk != NULL && superk->super() != NULL) {
 318     klassVtable ssVtable = (superk->super())->vtable();
 319     if (vtable_index < ssVtable.length()) {
 320       Method* super_method = ssVtable.method_at(vtable_index);
 321 #ifndef PRODUCT
 322       Symbol* name= target_method()->name();
 323       Symbol* signature = target_method()->signature();
 324       assert(super_method->name() == name && super_method->signature() == signature, "vtable entry name/sig mismatch");
 325 #endif
 326 
 327       if (can_be_overridden(super_method, target_loader, target_classname)) {
 328         if (log_develop_is_enabled(Trace, vtables)) {
 329           ResourceMark rm;
 330           LogTarget(Trace, vtables) lt;
 331           LogStream ls(lt);
 332           char* sig = target_method()->name_and_sig_as_C_string();
 333           ls.print("transitive overriding superclass %s with %s index %d, original flags: ",
 334                        super_method->method_holder()->internal_name(),
 335                        sig, vtable_index);
 336           super_method->print_linkage_flags(&ls);
 337           ls.print("overriders flags: ");
 338           target_method->print_linkage_flags(&ls);
 339           ls.cr();
 340         }
 341 
 342         break; // return found superk
 343       }
 344     } else  {
 345       // super class has no vtable entry here, stop transitive search
 346       superk = (InstanceKlass*)NULL;
 347       break;
 348     }
 349     // if no override found yet, continue to search up
 350     superk = superk->super() == NULL ? NULL : InstanceKlass::cast(superk->super());
 351   }
 352 
 353   return superk;
 354 }
 355 
 356 static void log_vtables(int i, bool overrides, const methodHandle& target_method,
 357                         Klass* target_klass, Method* super_method) {
 358 #ifndef PRODUCT
 359   if (log_develop_is_enabled(Trace, vtables)) {
 360     ResourceMark rm;
 361     LogTarget(Trace, vtables) lt;
 362     LogStream ls(lt);
 363     char* sig = target_method()->name_and_sig_as_C_string();
 364     if (overrides) {
 365       ls.print("overriding with %s index %d, original flags: ",
 366                    sig, i);
 367     } else {
 368       ls.print("NOT overriding with %s index %d, original flags: ",
 369                    sig, i);
 370     }
 371     super_method->print_linkage_flags(&ls);
 372     ls.print("overriders flags: ");
 373     target_method->print_linkage_flags(&ls);
 374     ls.cr();
 375   }
 376 #endif
 377 }
 378 
 379 // Update child's copy of super vtable for overrides
 380 // OR return true if a new vtable entry is required.
 381 // Only called for InstanceKlass's, i.e. not for arrays
 382 // If that changed, could not use _klass as handle for klass
 383 bool klassVtable::update_inherited_vtable(Thread* current,
 384                                           const methodHandle& target_method,
 385                                           int super_vtable_len, int default_index,
 386                                           GrowableArray<InstanceKlass*>* supers) {
 387   bool allocate_new = true;
 388 
 389   InstanceKlass* klass = ik();
 390 
 391   Array<int>* def_vtable_indices = NULL;
 392   bool is_default = false;
 393 
 394   // default methods are non-private concrete methods in superinterfaces which are added
 395   // to the vtable with their real method_holder.
 396   // Since vtable and itable indices share the same storage, don't touch
 397   // the default method's real vtable/itable index.
 398   // default_vtable_indices stores the vtable value relative to this inheritor
 399   if (default_index >= 0 ) {
 400     is_default = true;
 401     def_vtable_indices = klass->default_vtable_indices();
 402     assert(!target_method->is_private(), "private interface method flagged as default");
 403     assert(def_vtable_indices != NULL, "def vtable alloc?");
 404     assert(default_index <= def_vtable_indices->length(), "def vtable len?");
 405   } else {
 406     assert(klass == target_method->method_holder(), "caller resp.");
 407     // Initialize the method's vtable index to "nonvirtual".
 408     // If we allocate a vtable entry, we will update it to a non-negative number.
 409     target_method->set_vtable_index(Method::nonvirtual_vtable_index);
 410   }
 411 
 412   // Private, static and <init> methods are never in
 413   if (target_method->is_private() || target_method->is_static() ||
 414       (target_method->name()->fast_compare(vmSymbols::object_initializer_name()) == 0)) {
 415     return false;
 416   }
 417 
 418   if (target_method->is_final_method(klass->access_flags())) {
 419     // a final method never needs a new entry; final methods can be statically
 420     // resolved and they have to be present in the vtable only if they override
 421     // a super's method, in which case they re-use its entry
 422     allocate_new = false;
 423   } else if (klass->is_interface()) {
 424     allocate_new = false;  // see note below in needs_new_vtable_entry
 425     // An interface never allocates new vtable slots, only inherits old ones.
 426     // This method will either be assigned its own itable index later,
 427     // or be assigned an inherited vtable index in the loop below.
 428     // default methods inherited by classes store their vtable indices
 429     // in the inheritor's default_vtable_indices.
 430     // default methods inherited by interfaces may already have a
 431     // valid itable index, if so, don't change it.
 432     // Overpass methods in an interface will be assigned an itable index later
 433     // by an inheriting class.
 434     if ((!is_default || !target_method->has_itable_index())) {
 435       target_method->set_vtable_index(Method::pending_itable_index);
 436     }
 437   }
 438 
 439   // we need a new entry if there is no superclass
 440   Klass* super = klass->super();
 441   if (super == NULL) {
 442     return allocate_new;
 443   }
 444 
 445   // search through the vtable and update overridden entries
 446   // Since check_signature_loaders acquires SystemDictionary_lock
 447   // which can block for gc, once we are in this loop, use handles
 448   // For classfiles built with >= jdk7, we now look for transitive overrides
 449 
 450   Symbol* name = target_method->name();
 451   Symbol* signature = target_method->signature();
 452 
 453   Klass* target_klass = target_method->method_holder();
 454   assert(target_klass != NULL, "impossible");
 455   if (target_klass == NULL) {
 456     target_klass = _klass;
 457   }
 458 
 459   HandleMark hm(current);
 460   Handle target_loader(current, target_klass->class_loader());
 461 
 462   Symbol* target_classname = target_klass->name();
 463   for(int i = 0; i < super_vtable_len; i++) {
 464     Method* super_method;
 465     if (is_preinitialized_vtable()) {
 466       // If this is a shared class, the vtable is already in the final state (fully
 467       // initialized). Need to look at the super's vtable.
 468       klassVtable superVtable = super->vtable();
 469       super_method = superVtable.method_at(i);
 470     } else {
 471       super_method = method_at(i);
 472     }
 473     // Check if method name matches.  Ignore match if klass is an interface and the
 474     // matching method is a non-public java.lang.Object method.  (See JVMS 5.4.3.4)
 475     // This is safe because the method at this slot should never get invoked.
 476     // (TBD: put in a method to throw NoSuchMethodError if this slot is ever used.)
 477     if (super_method->name() == name && super_method->signature() == signature &&
 478         (!klass->is_interface() ||
 479          !SystemDictionary::is_nonpublic_Object_method(super_method))) {
 480 
 481       // get super_klass for method_holder for the found method
 482       InstanceKlass* super_klass =  super_method->method_holder();
 483 
 484       // Whether the method is being overridden
 485       bool overrides = false;
 486 
 487       // private methods are also never overridden
 488       if (!super_method->is_private() &&
 489           (is_default ||
 490            can_be_overridden(super_method, target_loader, target_classname) ||
 491            (klass->major_version() >= VTABLE_TRANSITIVE_OVERRIDE_VERSION &&
 492              (super_klass = find_transitive_override(super_klass,
 493                                                      target_method, i, target_loader,
 494                                                      target_classname)) != NULL))) {
 495 
 496         // Package private methods always need a new entry to root their own
 497         // overriding. They may also override other methods.
 498         if (!target_method->is_package_private()) {
 499           allocate_new = false;
 500         }
 501 
 502         // Set the vtable index before the constraint check safepoint, which potentially
 503         // redefines this method if this method is a default method belonging to a
 504         // super class or interface.
 505         put_method_at(target_method(), i);
 506         // Save super for constraint checking.
 507         if (supers != NULL) {
 508           supers->at_put(i, super_klass);
 509         }
 510 
 511         overrides = true;
 512         if (!is_default) {
 513           target_method->set_vtable_index(i);
 514         } else {
 515           if (def_vtable_indices != NULL) {
 516             if (is_preinitialized_vtable()) {
 517               // At runtime initialize_vtable is rerun as part of link_class_impl()
 518               // for a shared class loaded by the non-boot loader.
 519               // The dumptime vtable index should be the same as the runtime index.
 520               assert(def_vtable_indices->at(default_index) == i,
 521                      "dump time vtable index is different from runtime index");
 522             } else {
 523               def_vtable_indices->at_put(default_index, i);
 524             }
 525           }
 526           assert(super_method->is_default_method() || super_method->is_overpass()
 527                  || super_method->is_abstract(), "default override error");
 528         }
 529       } else {
 530         overrides = false;
 531       }
 532       log_vtables(i, overrides, target_method, target_klass, super_method);
 533     }
 534   }
 535   return allocate_new;
 536 }
 537 
 538 void klassVtable::put_method_at(Method* m, int index) {
 539   assert(!m->is_private(), "private methods should not be in vtable");
 540   JVMTI_ONLY(assert(!m->is_old() || ik()->is_being_redefined(), "old methods should not be in vtable"));
 541   if (is_preinitialized_vtable()) {
 542     // At runtime initialize_vtable is rerun as part of link_class_impl()
 543     // for shared class loaded by the non-boot loader to obtain the loader
 544     // constraints based on the runtime classloaders' context. The dumptime
 545     // method at the vtable index should be the same as the runtime method.
 546     assert(table()[index].method() == m,
 547            "archived method is different from the runtime method");
 548   } else {
 549     if (log_develop_is_enabled(Trace, vtables)) {
 550       ResourceMark rm;
 551       LogTarget(Trace, vtables) lt;
 552       LogStream ls(lt);
 553       const char* sig = (m != NULL) ? m->name_and_sig_as_C_string() : "<NULL>";
 554       ls.print("adding %s at index %d, flags: ", sig, index);
 555       if (m != NULL) {
 556         m->print_linkage_flags(&ls);
 557       }
 558       ls.cr();
 559     }
 560     table()[index].set(m);
 561   }
 562 }
 563 
 564 void klassVtable::check_constraints(GrowableArray<InstanceKlass*>* supers, TRAPS) {
 565   assert(supers->length() == length(), "lengths are different");
 566   // For each method in the vtable, check constraints against any super class
 567   // if overridden.
 568   for (int i = 0; i < length(); i++) {
 569     methodHandle target_method(THREAD, unchecked_method_at(i));
 570     InstanceKlass* super_klass = supers->at(i);
 571     if (target_method() != NULL && super_klass != NULL) {
 572       // Do not check loader constraints for overpass methods because overpass
 573       // methods are created by the jvm to throw exceptions.
 574       if (!target_method->is_overpass()) {
 575         // Override vtable entry if passes loader constraint check
 576         // if loader constraint checking requested
 577         // No need to visit his super, since he and his super
 578         // have already made any needed loader constraints.
 579         // Since loader constraints are transitive, it is enough
 580         // to link to the first super, and we get all the others.
 581         Handle super_loader(THREAD, super_klass->class_loader());
 582         InstanceKlass* target_klass = target_method->method_holder();
 583         Handle target_loader(THREAD, target_klass->class_loader());
 584 
 585         if (target_loader() != super_loader()) {
 586           ResourceMark rm(THREAD);
 587           Symbol* failed_type_symbol =
 588             SystemDictionary::check_signature_loaders(target_method->signature(),
 589                                                       _klass,
 590                                                       target_loader, super_loader,
 591                                                       true);
 592           if (failed_type_symbol != NULL) {
 593             stringStream ss;
 594             ss.print("loader constraint violation for class %s: when selecting "
 595                      "overriding method '", _klass->external_name());
 596             target_method->print_external_name(&ss),
 597             ss.print("' the class loader %s of the "
 598                      "selected method's type %s, and the class loader %s for its super "
 599                      "type %s have different Class objects for the type %s used in the signature (%s; %s)",
 600                      target_klass->class_loader_data()->loader_name_and_id(),
 601                      target_klass->external_name(),
 602                      super_klass->class_loader_data()->loader_name_and_id(),
 603                      super_klass->external_name(),
 604                      failed_type_symbol->as_klass_external_name(),
 605                      target_klass->class_in_module_of_loader(false, true),
 606                      super_klass->class_in_module_of_loader(false, true));
 607             THROW_MSG(vmSymbols::java_lang_LinkageError(), ss.as_string());
 608           }
 609         }
 610       }
 611     }
 612   }
 613 }
 614 
 615 void klassVtable::initialize_vtable_and_check_constraints(TRAPS) {
 616   // Save a superclass from each vtable entry to do constraint checking
 617   ResourceMark rm(THREAD);
 618   GrowableArray<InstanceKlass*>* supers = new GrowableArray<InstanceKlass*>(_length, _length, NULL);
 619   initialize_vtable(supers);
 620   check_constraints(supers, CHECK);
 621 }
 622 
 623 
 624 // Find out if a method "m" with superclass "super", loader "classloader" and
 625 // name "classname" needs a new vtable entry.  Let P be a class package defined
 626 // by "classloader" and "classname".
 627 // NOTE: The logic used here is very similar to the one used for computing
 628 // the vtables indices for a method. We cannot directly use that function because,
 629 // we allocate the InstanceKlass at load time, and that requires that the
 630 // superclass has been loaded.
 631 // However, the vtable entries are filled in at link time, and therefore
 632 // the superclass' vtable may not yet have been filled in.
 633 bool klassVtable::needs_new_vtable_entry(Method* target_method,
 634                                          const Klass* super,
 635                                          Handle classloader,
 636                                          Symbol* classname,
 637                                          AccessFlags class_flags,
 638                                          u2 major_version) {
 639   if (class_flags.is_interface()) {
 640     // Interfaces do not use vtables, except for java.lang.Object methods,
 641     // so there is no point to assigning
 642     // a vtable index to any of their local methods.  If we refrain from doing this,
 643     // we can use Method::_vtable_index to hold the itable index
 644     return false;
 645   }
 646 
 647   if (target_method->is_final_method(class_flags) ||
 648       // a final method never needs a new entry; final methods can be statically
 649       // resolved and they have to be present in the vtable only if they override
 650       // a super's method, in which case they re-use its entry
 651       (target_method->is_private()) ||
 652       // private methods don't need to be in vtable
 653       (target_method->is_static()) ||
 654       // static methods don't need to be in vtable
 655       (target_method->name()->fast_compare(vmSymbols::object_initializer_name()) == 0)
 656       // <init> is never called dynamically-bound
 657       ) {
 658     return false;
 659   }
 660 
 661   // Concrete interface methods do not need new entries, they override
 662   // abstract method entries using default inheritance rules
 663   if (target_method->method_holder() != NULL &&
 664       target_method->method_holder()->is_interface()  &&
 665       !target_method->is_abstract()) {
 666     assert(target_method->is_default_method(),
 667            "unexpected interface method type");
 668     return false;
 669   }
 670 
 671   // we need a new entry if there is no superclass
 672   if (super == NULL) {
 673     return true;
 674   }
 675 
 676   // Package private methods always need a new entry to root their own
 677   // overriding. This allows transitive overriding to work.
 678   if (target_method->is_package_private()) {
 679     return true;
 680   }
 681 
 682   // search through the super class hierarchy to see if we need
 683   // a new entry
 684   Symbol* name = target_method->name();
 685   Symbol* signature = target_method->signature();
 686   const Klass* k = super;
 687   Method* super_method = NULL;
 688   InstanceKlass *holder = NULL;
 689   Method* recheck_method =  NULL;
 690   bool found_pkg_prvt_method = false;
 691   while (k != NULL) {
 692     // lookup through the hierarchy for a method with matching name and sign.
 693     super_method = InstanceKlass::cast(k)->lookup_method(name, signature);
 694     if (super_method == NULL) {
 695       break; // we still have to search for a matching miranda method
 696     }
 697     // get the class holding the matching method
 698     InstanceKlass* superk = super_method->method_holder();
 699     // we want only instance method matches
 700     // ignore private methods found via lookup_method since they do not participate in overriding,
 701     // and since we do override around them: e.g. a.m pub/b.m private/c.m pub,
 702     // ignore private, c.m pub does override a.m pub
 703     // For classes that were not javac'd together, we also do transitive overriding around
 704     // methods that have less accessibility
 705     if (!super_method->is_static() &&
 706         !super_method->is_private()) {
 707       if (can_be_overridden(super_method, classloader, classname)) {
 708         return false;
 709         // else keep looking for transitive overrides
 710       }
 711       // If we get here then one of the super classes has a package private method
 712       // that will not get overridden because it is in a different package.  But,
 713       // that package private method does "override" any matching methods in super
 714       // interfaces, so there will be no miranda vtable entry created.  So, set flag
 715       // to TRUE for use below, in case there are no methods in super classes that
 716       // this target method overrides.
 717       assert(super_method->is_package_private(), "super_method must be package private");
 718       assert(!superk->is_same_class_package(classloader(), classname),
 719              "Must be different packages");
 720       found_pkg_prvt_method = true;
 721     }
 722 
 723     // Start with lookup result and continue to search up, for versions supporting transitive override
 724     if (major_version >= VTABLE_TRANSITIVE_OVERRIDE_VERSION) {
 725       k = superk->super(); // haven't found an override match yet; continue to look
 726     } else {
 727       break;
 728     }
 729   }
 730 
 731   // If found_pkg_prvt_method is set, then the ONLY matching method in the
 732   // superclasses is package private in another package. That matching method will
 733   // prevent a miranda vtable entry from being created. Because the target method can not
 734   // override the package private method in another package, then it needs to be the root
 735   // for its own vtable entry.
 736   if (found_pkg_prvt_method) {
 737      return true;
 738   }
 739 
 740   // if the target method is public or protected it may have a matching
 741   // miranda method in the super, whose entry it should re-use.
 742   // Actually, to handle cases that javac would not generate, we need
 743   // this check for all access permissions.
 744   const InstanceKlass *sk = InstanceKlass::cast(super);
 745   if (sk->has_miranda_methods()) {
 746     if (sk->lookup_method_in_all_interfaces(name, signature, Klass::DefaultsLookupMode::find) != NULL) {
 747       return false; // found a matching miranda; we do not need a new entry
 748     }
 749   }
 750   return true; // found no match; we need a new entry
 751 }
 752 
 753 // Support for miranda methods
 754 
 755 // get the vtable index of a miranda method with matching "name" and "signature"
 756 int klassVtable::index_of_miranda(Symbol* name, Symbol* signature) {
 757   // search from the bottom, might be faster
 758   for (int i = (length() - 1); i >= 0; i--) {
 759     Method* m = table()[i].method();
 760     if (is_miranda_entry_at(i) &&
 761         m->name() == name && m->signature() == signature) {
 762       return i;
 763     }
 764   }
 765   return Method::invalid_vtable_index;
 766 }
 767 
 768 // check if an entry at an index is miranda
 769 // requires that method m at entry be declared ("held") by an interface.
 770 bool klassVtable::is_miranda_entry_at(int i) {
 771   Method* m = method_at(i);
 772   InstanceKlass* holder = m->method_holder();
 773 
 774   // miranda methods are public abstract instance interface methods in a class's vtable
 775   if (holder->is_interface()) {
 776     assert(m->is_public(), "should be public");
 777     assert(ik()->implements_interface(holder) , "this class should implement the interface");
 778     if (is_miranda(m, ik()->methods(), ik()->default_methods(), ik()->super(), klass()->is_interface())) {
 779       return true;
 780     }
 781   }
 782   return false;
 783 }
 784 
 785 // Check if a method is a miranda method, given a class's methods array,
 786 // its default_method table and its super class.
 787 // "Miranda" means an abstract non-private method that would not be
 788 // overridden for the local class.
 789 // A "miranda" method should only include non-private interface
 790 // instance methods, i.e. not private methods, not static methods,
 791 // not default methods (concrete interface methods), not overpass methods.
 792 // If a given class already has a local (including overpass) method, a
 793 // default method, or any of its superclasses has the same which would have
 794 // overridden an abstract method, then this is not a miranda method.
 795 //
 796 // Miranda methods are checked multiple times.
 797 // Pass 1: during class load/class file parsing: before vtable size calculation:
 798 // include superinterface abstract and default methods (non-private instance).
 799 // We include potential default methods to give them space in the vtable.
 800 // During the first run, the current instanceKlass has not yet been
 801 // created, the superclasses and superinterfaces do have instanceKlasses
 802 // but may not have vtables, the default_methods list is empty, no overpasses.
 803 // Default method generation uses the all_mirandas array as the starter set for
 804 // maximally-specific default method calculation.  So, for both classes and
 805 // interfaces, it is necessary that the first pass will find all non-private
 806 // interface instance methods, whether or not they are concrete.
 807 //
 808 // Pass 2: recalculated during vtable initialization: only include abstract methods.
 809 // The goal of pass 2 is to walk through the superinterfaces to see if any of
 810 // the superinterface methods (which were all abstract pre-default methods)
 811 // need to be added to the vtable.
 812 // With the addition of default methods, we have three new challenges:
 813 // overpasses, static interface methods and private interface methods.
 814 // Static and private interface methods do not get added to the vtable and
 815 // are not seen by the method resolution process, so we skip those.
 816 // Overpass methods are already in the vtable, so vtable lookup will
 817 // find them and we don't need to add a miranda method to the end of
 818 // the vtable. So we look for overpass methods and if they are found we
 819 // return false. Note that we inherit our superclasses vtable, so
 820 // the superclass' search also needs to use find_overpass so that if
 821 // one is found we return false.
 822 // False means - we don't need a miranda method added to the vtable.
 823 //
 824 // During the second run, default_methods is set up, so concrete methods from
 825 // superinterfaces with matching names/signatures to default_methods are already
 826 // in the default_methods list and do not need to be appended to the vtable
 827 // as mirandas. Abstract methods may already have been handled via
 828 // overpasses - either local or superclass overpasses, which may be
 829 // in the vtable already.
 830 //
 831 // Pass 3: They are also checked by link resolution and selection,
 832 // for invocation on a method (not interface method) reference that
 833 // resolves to a method with an interface as its method_holder.
 834 // Used as part of walking from the bottom of the vtable to find
 835 // the vtable index for the miranda method.
 836 //
 837 // Part of the Miranda Rights in the US mean that if you do not have
 838 // an attorney one will be appointed for you.
 839 bool klassVtable::is_miranda(Method* m, Array<Method*>* class_methods,
 840                              Array<Method*>* default_methods, const Klass* super,
 841                              bool is_interface) {
 842   if (m->is_static() || m->is_private() || m->is_overpass()) {
 843     return false;
 844   }
 845   Symbol* name = m->name();
 846   Symbol* signature = m->signature();
 847 
 848   // First look in local methods to see if already covered
 849   if (InstanceKlass::find_local_method(class_methods, name, signature,
 850                                        Klass::OverpassLookupMode::find,
 851                                        Klass::StaticLookupMode::skip,
 852                                        Klass::PrivateLookupMode::skip) != NULL)
 853   {
 854     return false;
 855   }
 856 
 857   // Check local default methods
 858   if ((default_methods != NULL) &&
 859     (InstanceKlass::find_method(default_methods, name, signature) != NULL))
 860    {
 861      return false;
 862    }
 863 
 864   // Iterate on all superclasses, which should be InstanceKlasses.
 865   // Note that we explicitly look for overpasses at each level.
 866   // Overpasses may or may not exist for supers for pass 1,
 867   // they should have been created for pass 2 and later.
 868 
 869   for (const Klass* cursuper = super; cursuper != NULL; cursuper = cursuper->super())
 870   {
 871      Method* found_mth = InstanceKlass::cast(cursuper)->find_local_method(name, signature,
 872                                                                           Klass::OverpassLookupMode::find,
 873                                                                           Klass::StaticLookupMode::skip,
 874                                                                           Klass::PrivateLookupMode::skip);
 875      // Ignore non-public methods in java.lang.Object if klass is an interface.
 876      if (found_mth != NULL && (!is_interface ||
 877          !SystemDictionary::is_nonpublic_Object_method(found_mth))) {
 878        return false;
 879      }
 880   }
 881 
 882   return true;
 883 }
 884 
 885 // Scans current_interface_methods for miranda methods that do not
 886 // already appear in new_mirandas, or default methods,  and are also not defined-and-non-private
 887 // in super (superclass).  These mirandas are added to all_mirandas if it is
 888 // not null; in addition, those that are not duplicates of miranda methods
 889 // inherited by super from its interfaces are added to new_mirandas.
 890 // Thus, new_mirandas will be the set of mirandas that this class introduces,
 891 // all_mirandas will be the set of all mirandas applicable to this class
 892 // including all defined in superclasses.
 893 void klassVtable::add_new_mirandas_to_lists(
 894     GrowableArray<Method*>* new_mirandas, GrowableArray<Method*>* all_mirandas,
 895     Array<Method*>* current_interface_methods, Array<Method*>* class_methods,
 896     Array<Method*>* default_methods, const Klass* super, bool is_interface) {
 897 
 898   // iterate thru the current interface's method to see if it a miranda
 899   int num_methods = current_interface_methods->length();
 900   for (int i = 0; i < num_methods; i++) {
 901     Method* im = current_interface_methods->at(i);
 902     bool is_duplicate = false;
 903     int num_of_current_mirandas = new_mirandas->length();
 904     // check for duplicate mirandas in different interfaces we implement
 905     for (int j = 0; j < num_of_current_mirandas; j++) {
 906       Method* miranda = new_mirandas->at(j);
 907       if ((im->name() == miranda->name()) &&
 908           (im->signature() == miranda->signature())) {
 909         is_duplicate = true;
 910         break;
 911       }
 912     }
 913 
 914     if (!is_duplicate) { // we don't want duplicate miranda entries in the vtable
 915       if (is_miranda(im, class_methods, default_methods, super, is_interface)) { // is it a miranda at all?
 916         const InstanceKlass *sk = InstanceKlass::cast(super);
 917         // check if it is a duplicate of a super's miranda
 918         if (sk->lookup_method_in_all_interfaces(im->name(), im->signature(), Klass::DefaultsLookupMode::find) == NULL) {
 919           new_mirandas->append(im);
 920         }
 921         if (all_mirandas != NULL) {
 922           all_mirandas->append(im);
 923         }
 924       }
 925     }
 926   }
 927 }
 928 
 929 void klassVtable::get_mirandas(GrowableArray<Method*>* new_mirandas,
 930                                GrowableArray<Method*>* all_mirandas,
 931                                const Klass* super,
 932                                Array<Method*>* class_methods,
 933                                Array<Method*>* default_methods,
 934                                Array<InstanceKlass*>* local_interfaces,
 935                                bool is_interface) {
 936   assert((new_mirandas->length() == 0) , "current mirandas must be 0");
 937 
 938   // iterate thru the local interfaces looking for a miranda
 939   int num_local_ifs = local_interfaces->length();
 940   for (int i = 0; i < num_local_ifs; i++) {
 941     InstanceKlass *ik = local_interfaces->at(i);
 942     add_new_mirandas_to_lists(new_mirandas, all_mirandas,
 943                               ik->methods(), class_methods,
 944                               default_methods, super, is_interface);
 945     // iterate thru each local's super interfaces
 946     Array<InstanceKlass*>* super_ifs = ik->transitive_interfaces();
 947     int num_super_ifs = super_ifs->length();
 948     for (int j = 0; j < num_super_ifs; j++) {
 949       InstanceKlass *sik = super_ifs->at(j);
 950       add_new_mirandas_to_lists(new_mirandas, all_mirandas,
 951                                 sik->methods(), class_methods,
 952                                 default_methods, super, is_interface);
 953     }
 954   }
 955 }
 956 
 957 // Discover miranda methods ("miranda" = "interface abstract, no binding"),
 958 // and append them into the vtable starting at index initialized,
 959 // return the new value of initialized.
 960 // Miranda methods use vtable entries, but do not get assigned a vtable_index
 961 // The vtable_index is discovered by searching from the end of the vtable
 962 int klassVtable::fill_in_mirandas(Thread* current, int initialized) {
 963   ResourceMark rm(current);
 964   GrowableArray<Method*> mirandas(20);
 965   get_mirandas(&mirandas, NULL, ik()->super(), ik()->methods(),
 966                ik()->default_methods(), ik()->local_interfaces(),
 967                klass()->is_interface());
 968   for (int i = 0; i < mirandas.length(); i++) {
 969     if (log_develop_is_enabled(Trace, vtables)) {
 970       Method* meth = mirandas.at(i);
 971       LogTarget(Trace, vtables) lt;
 972       LogStream ls(lt);
 973       if (meth != NULL) {
 974         char* sig = meth->name_and_sig_as_C_string();
 975         ls.print("fill in mirandas with %s index %d, flags: ",
 976                      sig, initialized);
 977         meth->print_linkage_flags(&ls);
 978         ls.cr();
 979       }
 980     }
 981     put_method_at(mirandas.at(i), initialized);
 982     ++initialized;
 983   }
 984   return initialized;
 985 }
 986 
 987 // Copy this class's vtable to the vtable beginning at start.
 988 // Used to copy superclass vtable to prefix of subclass's vtable.
 989 void klassVtable::copy_vtable_to(vtableEntry* start) {
 990   Copy::disjoint_words((HeapWord*)table(), (HeapWord*)start, _length * vtableEntry::size());
 991 }
 992 
 993 #if INCLUDE_JVMTI
 994 bool klassVtable::adjust_default_method(int vtable_index, Method* old_method, Method* new_method) {
 995   // If old_method is default, find this vtable index in default_vtable_indices
 996   // and replace that method in the _default_methods list
 997   bool updated = false;
 998 
 999   Array<Method*>* default_methods = ik()->default_methods();
1000   if (default_methods != NULL) {
1001     int len = default_methods->length();
1002     for (int idx = 0; idx < len; idx++) {
1003       if (vtable_index == ik()->default_vtable_indices()->at(idx)) {
1004         if (default_methods->at(idx) == old_method) {
1005           default_methods->at_put(idx, new_method);
1006           updated = true;
1007         }
1008         break;
1009       }
1010     }
1011   }
1012   return updated;
1013 }
1014 
1015 // search the vtable for uses of either obsolete or EMCP methods
1016 void klassVtable::adjust_method_entries(bool * trace_name_printed) {
1017   int prn_enabled = 0;
1018   ResourceMark rm;
1019 
1020   for (int index = 0; index < length(); index++) {
1021     Method* old_method = unchecked_method_at(index);
1022     if (old_method == NULL || !old_method->is_old()) {
1023       continue; // skip uninteresting entries
1024     }
1025     assert(!old_method->is_deleted(), "vtable methods may not be deleted");
1026 
1027     Method* new_method = old_method->get_new_method();
1028     put_method_at(new_method, index);
1029 
1030     // For default methods, need to update the _default_methods array
1031     // which can only have one method entry for a given signature
1032     bool updated_default = false;
1033     if (old_method->is_default_method()) {
1034       updated_default = adjust_default_method(index, old_method, new_method);
1035     }
1036 
1037     if (!(*trace_name_printed)) {
1038       log_info(redefine, class, update)
1039         ("adjust: klassname=%s for methods from name=%s",
1040          _klass->external_name(), old_method->method_holder()->external_name());
1041       *trace_name_printed = true;
1042     }
1043     log_trace(redefine, class, update, vtables)
1044       ("vtable method update: class: %s method: %s, updated default = %s",
1045        _klass->external_name(), new_method->external_name(), updated_default ? "true" : "false");
1046   }
1047 }
1048 
1049 // a vtable should never contain old or obsolete methods
1050 bool klassVtable::check_no_old_or_obsolete_entries() {
1051   ResourceMark rm;
1052 
1053   for (int i = 0; i < length(); i++) {
1054     Method* m = unchecked_method_at(i);
1055     if (m != NULL &&
1056         (NOT_PRODUCT(!m->is_valid() ||) m->is_old() || m->is_obsolete())) {
1057       log_trace(redefine, class, update, vtables)
1058         ("vtable check found old method entry: class: %s old: %d obsolete: %d, method: %s",
1059          _klass->external_name(), m->is_old(), m->is_obsolete(), m->external_name());
1060       return false;
1061     }
1062   }
1063   return true;
1064 }
1065 
1066 void klassVtable::dump_vtable() {
1067   tty->print_cr("vtable dump --");
1068   for (int i = 0; i < length(); i++) {
1069     Method* m = unchecked_method_at(i);
1070     if (m != NULL) {
1071       tty->print("      (%5d)  ", i);
1072       m->access_flags().print_on(tty);
1073       if (m->is_default_method()) {
1074         tty->print("default ");
1075       }
1076       if (m->is_overpass()) {
1077         tty->print("overpass");
1078       }
1079       tty->print(" --  ");
1080       m->print_name(tty);
1081       tty->cr();
1082     }
1083   }
1084 }
1085 #endif // INCLUDE_JVMTI
1086 
1087 //-----------------------------------------------------------------------------------------
1088 // Itable code
1089 
1090 // Initialize a itableMethodEntry
1091 void itableMethodEntry::initialize(InstanceKlass* klass, Method* m) {
1092   if (m == NULL) return;
1093 
1094 #ifdef ASSERT
1095   if (MetaspaceShared::is_in_shared_metaspace((void*)&_method) &&
1096      !MetaspaceShared::remapped_readwrite() &&
1097      m->method_holder()->verified_at_dump_time() &&
1098      klass->verified_at_dump_time()) {
1099     // At runtime initialize_itable is rerun as part of link_class_impl()
1100     // for a shared class loaded by the non-boot loader.
1101     // The dumptime itable method entry should be the same as the runtime entry.
1102     // For a shared old class which was not linked during dump time, we can't compare the dumptime
1103     // itable method entry with the runtime entry.
1104     assert(_method == m, "sanity");
1105   }
1106 #endif
1107   _method = m;
1108 }
1109 
1110 klassItable::klassItable(InstanceKlass* klass) {
1111   _klass = klass;
1112 
1113   if (klass->itable_length() > 0) {
1114     itableOffsetEntry* offset_entry = (itableOffsetEntry*)klass->start_of_itable();
1115     if (offset_entry  != NULL && offset_entry->interface_klass() != NULL) { // Check that itable is initialized
1116       // First offset entry points to the first method_entry
1117       intptr_t* method_entry  = (intptr_t *)(((address)klass) + offset_entry->offset());
1118       intptr_t* end         = klass->end_of_itable();
1119 
1120       _table_offset      = (intptr_t*)offset_entry - (intptr_t*)klass;
1121       _size_offset_table = (method_entry - ((intptr_t*)offset_entry)) / itableOffsetEntry::size();
1122       _size_method_table = (end - method_entry)                  / itableMethodEntry::size();
1123       assert(_table_offset >= 0 && _size_offset_table >= 0 && _size_method_table >= 0, "wrong computation");
1124       return;
1125     }
1126   }
1127 
1128   // The length of the itable was either zero, or it has not yet been initialized.
1129   _table_offset      = 0;
1130   _size_offset_table = 0;
1131   _size_method_table = 0;
1132 }
1133 
1134 static int initialize_count = 0;
1135 
1136 // Initialization
1137 void klassItable::initialize_itable(GrowableArray<Method*>* supers) {
1138   if (_klass->is_interface()) {
1139     // This needs to go after vtable indices are assigned but
1140     // before implementors need to know the number of itable indices.
1141     assign_itable_indices_for_interface(InstanceKlass::cast(_klass));
1142   }
1143 
1144   // Cannot be setup doing bootstrapping, interfaces don't have
1145   // itables, and klass with only ones entry have empty itables
1146   if (Universe::is_bootstrapping() ||
1147       _klass->is_interface() ||
1148       _klass->itable_length() == itableOffsetEntry::size()) return;
1149 
1150   // There's alway an extra itable entry so we can null-terminate it.
1151   guarantee(size_offset_table() >= 1, "too small");
1152   int num_interfaces = size_offset_table() - 1;
1153   if (num_interfaces > 0) {
1154     if (log_develop_is_enabled(Debug, itables)) {
1155       ResourceMark rm;
1156       log_develop_debug(itables)("%3d: Initializing itables for %s", ++initialize_count,
1157                        _klass->name()->as_C_string());
1158     }
1159 
1160     // Iterate through all interfaces
1161     for(int i = 0; i < num_interfaces; i++) {
1162       itableOffsetEntry* ioe = offset_entry(i);
1163       InstanceKlass* interf = ioe->interface_klass();
1164       assert(interf != NULL && ioe->offset() != 0, "bad offset entry in itable");
1165       initialize_itable_for_interface(ioe->offset(), interf, supers,
1166                        (ioe->offset() - offset_entry(0)->offset())/wordSize);
1167     }
1168   }
1169   // Check that the last entry is empty
1170   itableOffsetEntry* ioe = offset_entry(size_offset_table() - 1);
1171   guarantee(ioe->interface_klass() == NULL && ioe->offset() == 0, "terminator entry missing");
1172 }
1173 
1174 void klassItable::check_constraints(GrowableArray<Method*>* supers, TRAPS) {
1175 
1176   assert(_size_method_table == supers->length(), "wrong size");
1177   itableMethodEntry* ime = method_entry(0);
1178   for (int i = 0; i < _size_method_table; i++) {
1179     Method* target = ime->method();
1180     Method* interface_method = supers->at(i); // method overridden
1181 
1182     if (target != NULL && interface_method != NULL) {
1183       InstanceKlass* method_holder = target->method_holder();
1184       InstanceKlass* interf = interface_method->method_holder();
1185       HandleMark hm(THREAD);
1186       Handle method_holder_loader(THREAD, method_holder->class_loader());
1187       Handle interface_loader(THREAD, interf->class_loader());
1188 
1189       if (method_holder_loader() != interface_loader()) {
1190         ResourceMark rm(THREAD);
1191         Symbol* failed_type_symbol =
1192           SystemDictionary::check_signature_loaders(target->signature(),
1193                                                     _klass,
1194                                                     method_holder_loader,
1195                                                     interface_loader,
1196                                                     true);
1197         if (failed_type_symbol != NULL) {
1198           stringStream ss;
1199           ss.print("loader constraint violation in interface itable"
1200                    " initialization for class %s: when selecting method '",
1201                    _klass->external_name());
1202           interface_method->print_external_name(&ss),
1203           ss.print("' the class loader %s for super interface %s, and the class"
1204                    " loader %s of the selected method's %s, %s have"
1205                    " different Class objects for the type %s used in the signature (%s; %s)",
1206                    interf->class_loader_data()->loader_name_and_id(),
1207                    interf->external_name(),
1208                    method_holder->class_loader_data()->loader_name_and_id(),
1209                    method_holder->external_kind(),
1210                    method_holder->external_name(),
1211                    failed_type_symbol->as_klass_external_name(),
1212                    interf->class_in_module_of_loader(false, true),
1213                    method_holder->class_in_module_of_loader(false, true));
1214           THROW_MSG(vmSymbols::java_lang_LinkageError(), ss.as_string());
1215         }
1216       }
1217     }
1218     ime++;
1219   }
1220 }
1221 
1222 void klassItable::initialize_itable_and_check_constraints(TRAPS) {
1223   // Save a super interface from each itable entry to do constraint checking
1224   ResourceMark rm(THREAD);
1225   GrowableArray<Method*>* supers =
1226     new GrowableArray<Method*>(_size_method_table, _size_method_table, NULL);
1227   initialize_itable(supers);
1228   check_constraints(supers, CHECK);
1229 }
1230 
1231 inline bool interface_method_needs_itable_index(Method* m) {
1232   if (m->is_static())           return false;   // e.g., Stream.empty
1233   if (m->is_initializer())      return false;   // <init> or <clinit>
1234   if (m->is_private())          return false;   // uses direct call
1235   // If an interface redeclares a method from java.lang.Object,
1236   // it should already have a vtable index, don't touch it.
1237   // e.g., CharSequence.toString (from initialize_vtable)
1238   // if (m->has_vtable_index())  return false; // NO!
1239   return true;
1240 }
1241 
1242 int klassItable::assign_itable_indices_for_interface(InstanceKlass* klass) {
1243   // an interface does not have an itable, but its methods need to be numbered
1244   if (log_develop_is_enabled(Trace, itables)) {
1245     ResourceMark rm;
1246     log_develop_debug(itables)("%3d: Initializing itable indices for interface %s",
1247                                ++initialize_count, klass->name()->as_C_string());
1248   }
1249 
1250   Array<Method*>* methods = klass->methods();
1251   int nof_methods = methods->length();
1252   int ime_num = 0;
1253   for (int i = 0; i < nof_methods; i++) {
1254     Method* m = methods->at(i);
1255     if (interface_method_needs_itable_index(m)) {
1256       assert(!m->is_final_method(), "no final interface methods");
1257       // If m is already assigned a vtable index, do not disturb it.
1258       if (log_develop_is_enabled(Trace, itables)) {
1259         ResourceMark rm;
1260         LogTarget(Trace, itables) lt;
1261         LogStream ls(lt);
1262         assert(m != NULL, "methods can never be null");
1263         const char* sig = m->name_and_sig_as_C_string();
1264         if (m->has_vtable_index()) {
1265           ls.print("vtable index %d for method: %s, flags: ", m->vtable_index(), sig);
1266         } else {
1267           ls.print("itable index %d for method: %s, flags: ", ime_num, sig);
1268         }
1269         m->print_linkage_flags(&ls);
1270         ls.cr();
1271       }
1272       if (!m->has_vtable_index()) {
1273         // A shared method could have an initialized itable_index that
1274         // is < 0.
1275         assert(m->vtable_index() == Method::pending_itable_index ||
1276                m->is_shared(),
1277                "set by initialize_vtable");
1278         m->set_itable_index(ime_num);
1279         // Progress to next itable entry
1280         ime_num++;
1281       }
1282     }
1283   }
1284   assert(ime_num == method_count_for_interface(klass), "proper sizing");
1285   return ime_num;
1286 }
1287 
1288 int klassItable::method_count_for_interface(InstanceKlass* interf) {
1289   assert(interf->is_interface(), "must be");
1290   Array<Method*>* methods = interf->methods();
1291   int nof_methods = methods->length();
1292   int length = 0;
1293   while (nof_methods > 0) {
1294     Method* m = methods->at(nof_methods-1);
1295     if (m->has_itable_index()) {
1296       length = m->itable_index() + 1;
1297       break;
1298     }
1299     nof_methods -= 1;
1300   }
1301 #ifdef ASSERT
1302   int nof_methods_copy = nof_methods;
1303   while (nof_methods_copy > 0) {
1304     Method* mm = methods->at(--nof_methods_copy);
1305     assert(!mm->has_itable_index() || mm->itable_index() < length, "");
1306   }
1307 #endif //ASSERT
1308   // return the rightmost itable index, plus one; or 0 if no methods have
1309   // itable indices
1310   return length;
1311 }
1312 
1313 
1314 void klassItable::initialize_itable_for_interface(int method_table_offset, InstanceKlass* interf,
1315                                                   GrowableArray<Method*>* supers,
1316                                                   int start_offset) {
1317   assert(interf->is_interface(), "must be");
1318   Array<Method*>* methods = interf->methods();
1319   int nof_methods = methods->length();
1320 
1321   int ime_count = method_count_for_interface(interf);
1322   for (int i = 0; i < nof_methods; i++) {
1323     Method* m = methods->at(i);
1324     Method* target = NULL;
1325     if (m->has_itable_index()) {
1326       // This search must match the runtime resolution, i.e. selection search for invokeinterface
1327       // to correctly enforce loader constraints for interface method inheritance.
1328       // Private methods are skipped as a private class method can never be the implementation
1329       // of an interface method.
1330       // Invokespecial does not perform selection based on the receiver, so it does not use
1331       // the cached itable.
1332       target = LinkResolver::lookup_instance_method_in_klasses(_klass, m->name(), m->signature(),
1333                                                                Klass::PrivateLookupMode::skip);
1334     }
1335     if (target == NULL || !target->is_public() || target->is_abstract() || target->is_overpass()) {
1336       assert(target == NULL || !target->is_overpass() || target->is_public(),
1337              "Non-public overpass method!");
1338       // Entry does not resolve. Leave it empty for AbstractMethodError or other error.
1339       if (!(target == NULL) && !target->is_public()) {
1340         // Stuff an IllegalAccessError throwing method in there instead.
1341         itableOffsetEntry::method_entry(_klass, method_table_offset)[m->itable_index()].
1342             initialize(_klass, Universe::throw_illegal_access_error());
1343       }
1344     } else {
1345 
1346       int ime_num = m->itable_index();
1347       assert(ime_num < ime_count, "oob");
1348 
1349       // Save super interface method to perform constraint checks.
1350       // The method is in the error message, that's why.
1351       if (supers != NULL) {
1352         supers->at_put(start_offset + ime_num, m);
1353       }
1354 
1355       itableOffsetEntry::method_entry(_klass, method_table_offset)[ime_num].initialize(_klass, target);
1356       if (log_develop_is_enabled(Trace, itables)) {
1357         ResourceMark rm;
1358         if (target != NULL) {
1359           LogTarget(Trace, itables) lt;
1360           LogStream ls(lt);
1361           char* sig = target->name_and_sig_as_C_string();
1362           ls.print("interface: %s, ime_num: %d, target: %s, method_holder: %s ",
1363                        interf->internal_name(), ime_num, sig,
1364                        target->method_holder()->internal_name());
1365           ls.print("target_method flags: ");
1366           target->print_linkage_flags(&ls);
1367           ls.cr();
1368         }
1369       }
1370     }
1371   }
1372 }
1373 
1374 #if INCLUDE_JVMTI
1375 // search the itable for uses of either obsolete or EMCP methods
1376 void klassItable::adjust_method_entries(bool * trace_name_printed) {
1377   ResourceMark rm;
1378   itableMethodEntry* ime = method_entry(0);
1379 
1380   for (int i = 0; i < _size_method_table; i++, ime++) {
1381     Method* old_method = ime->method();
1382     if (old_method == NULL || !old_method->is_old()) {
1383       continue; // skip uninteresting entries
1384     }
1385     assert(!old_method->is_deleted(), "itable methods may not be deleted");
1386     Method* new_method = old_method->get_new_method();
1387     ime->initialize(_klass, new_method);
1388 
1389     if (!(*trace_name_printed)) {
1390       log_info(redefine, class, update)("adjust: name=%s", old_method->method_holder()->external_name());
1391       *trace_name_printed = true;
1392     }
1393     log_trace(redefine, class, update, itables)
1394       ("itable method update: class: %s method: %s", _klass->external_name(), new_method->external_name());
1395   }
1396 }
1397 
1398 // an itable should never contain old or obsolete methods
1399 bool klassItable::check_no_old_or_obsolete_entries() {
1400   ResourceMark rm;
1401   itableMethodEntry* ime = method_entry(0);
1402 
1403   for (int i = 0; i < _size_method_table; i++) {
1404     Method* m = ime->method();
1405     if (m != NULL &&
1406         (NOT_PRODUCT(!m->is_valid() ||) m->is_old() || m->is_obsolete())) {
1407       log_trace(redefine, class, update, itables)
1408         ("itable check found old method entry: class: %s old: %d obsolete: %d, method: %s",
1409          _klass->external_name(), m->is_old(), m->is_obsolete(), m->external_name());
1410       return false;
1411     }
1412     ime++;
1413   }
1414   return true;
1415 }
1416 
1417 void klassItable::dump_itable() {
1418   itableMethodEntry* ime = method_entry(0);
1419   tty->print_cr("itable dump --");
1420   for (int i = 0; i < _size_method_table; i++) {
1421     Method* m = ime->method();
1422     if (m != NULL) {
1423       tty->print("      (%5d)  ", i);
1424       m->access_flags().print_on(tty);
1425       if (m->is_default_method()) {
1426         tty->print("default ");
1427       }
1428       tty->print(" --  ");
1429       m->print_name(tty);
1430       tty->cr();
1431     }
1432     ime++;
1433   }
1434 }
1435 #endif // INCLUDE_JVMTI
1436 
1437 // Setup
1438 class InterfaceVisiterClosure : public StackObj {
1439  public:
1440   virtual void doit(InstanceKlass* intf, int method_count) = 0;
1441 };
1442 
1443 // Visit all interfaces with at least one itable method
1444 void visit_all_interfaces(Array<InstanceKlass*>* transitive_intf, InterfaceVisiterClosure *blk) {
1445   // Handle array argument
1446   for(int i = 0; i < transitive_intf->length(); i++) {
1447     InstanceKlass* intf = transitive_intf->at(i);
1448     assert(intf->is_interface(), "sanity check");
1449 
1450     // Find no. of itable methods
1451     int method_count = 0;
1452     // method_count = klassItable::method_count_for_interface(intf);
1453     Array<Method*>* methods = intf->methods();
1454     if (methods->length() > 0) {
1455       for (int i = methods->length(); --i >= 0; ) {
1456         if (interface_method_needs_itable_index(methods->at(i))) {
1457           method_count++;
1458         }
1459       }
1460     }
1461 
1462     // Visit all interfaces which either have any methods or can participate in receiver type check.
1463     // We do not bother to count methods in transitive interfaces, although that would allow us to skip
1464     // this step in the rare case of a zero-method interface extending another zero-method interface.
1465     if (method_count > 0 || intf->transitive_interfaces()->length() > 0) {
1466       blk->doit(intf, method_count);
1467     }
1468   }
1469 }
1470 
1471 class CountInterfacesClosure : public InterfaceVisiterClosure {
1472  private:
1473   int _nof_methods;
1474   int _nof_interfaces;
1475  public:
1476    CountInterfacesClosure() { _nof_methods = 0; _nof_interfaces = 0; }
1477 
1478    int nof_methods() const    { return _nof_methods; }
1479    int nof_interfaces() const { return _nof_interfaces; }
1480 
1481    void doit(InstanceKlass* intf, int method_count) { _nof_methods += method_count; _nof_interfaces++; }
1482 };
1483 
1484 class SetupItableClosure : public InterfaceVisiterClosure  {
1485  private:
1486   itableOffsetEntry* _offset_entry;
1487   itableMethodEntry* _method_entry;
1488   address            _klass_begin;
1489  public:
1490   SetupItableClosure(address klass_begin, itableOffsetEntry* offset_entry, itableMethodEntry* method_entry) {
1491     _klass_begin  = klass_begin;
1492     _offset_entry = offset_entry;
1493     _method_entry = method_entry;
1494   }
1495 
1496   itableMethodEntry* method_entry() const { return _method_entry; }
1497 
1498   void doit(InstanceKlass* intf, int method_count) {
1499     int offset = ((address)_method_entry) - _klass_begin;
1500     _offset_entry->initialize(intf, offset);
1501     _offset_entry++;
1502     _method_entry += method_count;
1503   }
1504 };
1505 
1506 int klassItable::compute_itable_size(Array<InstanceKlass*>* transitive_interfaces) {
1507   // Count no of interfaces and total number of interface methods
1508   CountInterfacesClosure cic;
1509   visit_all_interfaces(transitive_interfaces, &cic);
1510 
1511   // There's alway an extra itable entry so we can null-terminate it.
1512   int itable_size = calc_itable_size(cic.nof_interfaces() + 1, cic.nof_methods());
1513 
1514   // Statistics
1515   update_stats(itable_size * wordSize);
1516 
1517   return itable_size;
1518 }
1519 
1520 
1521 // Fill out offset table and interface klasses into the itable space
1522 void klassItable::setup_itable_offset_table(InstanceKlass* klass) {
1523   if (klass->itable_length() == 0) return;
1524   assert(!klass->is_interface(), "Should have zero length itable");
1525 
1526   // Count no of interfaces and total number of interface methods
1527   CountInterfacesClosure cic;
1528   visit_all_interfaces(klass->transitive_interfaces(), &cic);
1529   int nof_methods    = cic.nof_methods();
1530   int nof_interfaces = cic.nof_interfaces();
1531 
1532   // Add one extra entry so we can null-terminate the table
1533   nof_interfaces++;
1534 
1535   assert(compute_itable_size(klass->transitive_interfaces()) ==
1536          calc_itable_size(nof_interfaces, nof_methods),
1537          "mismatch calculation of itable size");
1538 
1539   // Fill-out offset table
1540   itableOffsetEntry* ioe = (itableOffsetEntry*)klass->start_of_itable();
1541   itableMethodEntry* ime = (itableMethodEntry*)(ioe + nof_interfaces);
1542   intptr_t* end               = klass->end_of_itable();
1543   assert((oop*)(ime + nof_methods) <= (oop*)klass->start_of_nonstatic_oop_maps(), "wrong offset calculation (1)");
1544   assert((oop*)(end) == (oop*)(ime + nof_methods),                      "wrong offset calculation (2)");
1545 
1546   // Visit all interfaces and initialize itable offset table
1547   SetupItableClosure sic((address)klass, ioe, ime);
1548   visit_all_interfaces(klass->transitive_interfaces(), &sic);
1549 
1550 #ifdef ASSERT
1551   ime  = sic.method_entry();
1552   oop* v = (oop*) klass->end_of_itable();
1553   assert( (oop*)(ime) == v, "wrong offset calculation (2)");
1554 #endif
1555 }
1556 
1557 void klassVtable::verify(outputStream* st, bool forced) {
1558   // make sure table is initialized
1559   if (!Universe::is_fully_initialized()) return;
1560 #ifndef PRODUCT
1561   // avoid redundant verifies
1562   if (!forced && _verify_count == Universe::verify_count()) return;
1563   _verify_count = Universe::verify_count();
1564 #endif
1565   oop* end_of_obj = (oop*)_klass + _klass->size();
1566   oop* end_of_vtable = (oop *)&table()[_length];
1567   if (end_of_vtable > end_of_obj) {
1568     ResourceMark rm;
1569     fatal("klass %s: klass object too short (vtable extends beyond end)",
1570           _klass->internal_name());
1571   }
1572 
1573   for (int i = 0; i < _length; i++) table()[i].verify(this, st);
1574   // verify consistency with superKlass vtable
1575   Klass* super = _klass->super();
1576   if (super != NULL) {
1577     InstanceKlass* sk = InstanceKlass::cast(super);
1578     klassVtable vt = sk->vtable();
1579     for (int i = 0; i < vt.length(); i++) {
1580       verify_against(st, &vt, i);
1581     }
1582   }
1583 }
1584 
1585 void klassVtable::verify_against(outputStream* st, klassVtable* vt, int index) {
1586   vtableEntry* vte = &vt->table()[index];
1587   if (vte->method()->name()      != table()[index].method()->name() ||
1588       vte->method()->signature() != table()[index].method()->signature()) {
1589     fatal("mismatched name/signature of vtable entries");
1590   }
1591 }
1592 
1593 #ifndef PRODUCT
1594 void klassVtable::print() {
1595   ResourceMark rm;
1596   tty->print("klassVtable for klass %s (length %d):\n", _klass->internal_name(), length());
1597   for (int i = 0; i < length(); i++) {
1598     table()[i].print();
1599     tty->cr();
1600   }
1601 }
1602 #endif
1603 
1604 void vtableEntry::verify(klassVtable* vt, outputStream* st) {
1605   Klass* vtklass = vt->klass();
1606   if (vtklass->is_instance_klass() &&
1607      (InstanceKlass::cast(vtklass)->major_version() >= klassVtable::VTABLE_TRANSITIVE_OVERRIDE_VERSION)) {
1608     assert(method() != NULL, "must have set method");
1609   }
1610   if (method() != NULL) {
1611     method()->verify();
1612     // we sub_type, because it could be a miranda method
1613     if (!vtklass->is_subtype_of(method()->method_holder())) {
1614 #ifndef PRODUCT
1615       print();
1616 #endif
1617       fatal("vtableEntry " PTR_FORMAT ": method is from subclass", p2i(this));
1618     }
1619  }
1620 }
1621 
1622 #ifndef PRODUCT
1623 
1624 void vtableEntry::print() {
1625   ResourceMark rm;
1626   tty->print("vtableEntry %s: ", method()->name()->as_C_string());
1627   if (Verbose) {
1628     tty->print("m " PTR_FORMAT " ", p2i(method()));
1629   }
1630 }
1631 
1632 class VtableStats : AllStatic {
1633  public:
1634   static int no_klasses;                // # classes with vtables
1635   static int no_array_klasses;          // # array classes
1636   static int no_instance_klasses;       // # instanceKlasses
1637   static int sum_of_vtable_len;         // total # of vtable entries
1638   static int sum_of_array_vtable_len;   // total # of vtable entries in array klasses only
1639   static int fixed;                     // total fixed overhead in bytes
1640   static int filler;                    // overhead caused by filler bytes
1641   static int entries;                   // total bytes consumed by vtable entries
1642   static int array_entries;             // total bytes consumed by array vtable entries
1643 
1644   static void do_class(Klass* k) {
1645     Klass* kl = k;
1646     klassVtable vt = kl->vtable();
1647     no_klasses++;
1648     if (kl->is_instance_klass()) {
1649       no_instance_klasses++;
1650       kl->array_klasses_do(do_class);
1651     }
1652     if (kl->is_array_klass()) {
1653       no_array_klasses++;
1654       sum_of_array_vtable_len += vt.length();
1655     }
1656     sum_of_vtable_len += vt.length();
1657   }
1658 
1659   static void compute() {
1660     LockedClassesDo locked_do_class(&do_class);
1661     ClassLoaderDataGraph::classes_do(&locked_do_class);
1662     fixed  = no_klasses * oopSize;      // vtable length
1663     // filler size is a conservative approximation
1664     filler = oopSize * (no_klasses - no_instance_klasses) * (sizeof(InstanceKlass) - sizeof(ArrayKlass) - 1);
1665     entries = sizeof(vtableEntry) * sum_of_vtable_len;
1666     array_entries = sizeof(vtableEntry) * sum_of_array_vtable_len;
1667   }
1668 };
1669 
1670 int VtableStats::no_klasses = 0;
1671 int VtableStats::no_array_klasses = 0;
1672 int VtableStats::no_instance_klasses = 0;
1673 int VtableStats::sum_of_vtable_len = 0;
1674 int VtableStats::sum_of_array_vtable_len = 0;
1675 int VtableStats::fixed = 0;
1676 int VtableStats::filler = 0;
1677 int VtableStats::entries = 0;
1678 int VtableStats::array_entries = 0;
1679 
1680 void klassVtable::print_statistics() {
1681   ResourceMark rm;
1682   VtableStats::compute();
1683   tty->print_cr("vtable statistics:");
1684   tty->print_cr("%6d classes (%d instance, %d array)", VtableStats::no_klasses, VtableStats::no_instance_klasses, VtableStats::no_array_klasses);
1685   int total = VtableStats::fixed + VtableStats::filler + VtableStats::entries;
1686   tty->print_cr("%6d bytes fixed overhead (refs + vtable object header)", VtableStats::fixed);
1687   tty->print_cr("%6d bytes filler overhead", VtableStats::filler);
1688   tty->print_cr("%6d bytes for vtable entries (%d for arrays)", VtableStats::entries, VtableStats::array_entries);
1689   tty->print_cr("%6d bytes total", total);
1690 }
1691 
1692 int    klassItable::_total_classes;   // Total no. of classes with itables
1693 size_t klassItable::_total_size;      // Total no. of bytes used for itables
1694 
1695 void klassItable::print_statistics() {
1696  tty->print_cr("itable statistics:");
1697  tty->print_cr("%6d classes with itables", _total_classes);
1698  tty->print_cr(SIZE_FORMAT_W(6) " K uses for itables (average by class: " SIZE_FORMAT " bytes)",
1699                _total_size / K, _total_size / _total_classes);
1700 }
1701 
1702 #endif // PRODUCT