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