/*

 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "jvm.h"

#include "classfile/classLoaderDataGraph.hpp"

#include "classfile/javaClasses.hpp"

#include "classfile/systemDictionary.hpp"

#include "classfile/vmSymbols.hpp"

#include "interpreter/linkResolver.hpp"

#include "logging/log.hpp"

#include "logging/logStream.hpp"

#include "memory/metaspaceShared.hpp"

#include "memory/resourceArea.hpp"

#include "memory/universe.hpp"

#include "oops/instanceKlass.hpp"

#include "oops/klassVtable.hpp"

#include "oops/method.hpp"

#include "oops/objArrayOop.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/arguments.hpp"

#include "runtime/flags/flagSetting.hpp"

#include "runtime/handles.inline.hpp"

#include "runtime/safepointVerifiers.hpp"

#include "utilities/copy.hpp"

inline InstanceKlass* klassVtable::ik() const {

  return InstanceKlass::cast(_klass);

}

bool klassVtable::is_preinitialized_vtable() {

  return _klass->is_shared() && !MetaspaceShared::remapped_readwrite();

}

// this function computes the vtable size (including the size needed for miranda

// methods) and the number of miranda methods in this class.

// Note on Miranda methods: Let's say there is a class C that implements

// interface I, and none of C's superclasses implements I.

// Let's say there is an abstract method m in I that neither C

// nor any of its super classes implement (i.e there is no method of any access,

// with the same name and signature as m), then m is a Miranda method which is

// entered as a public abstract method in C's vtable.  From then on it should

// treated as any other public method in C for method over-ride purposes.

void klassVtable::compute_vtable_size_and_num_mirandas(

    int* vtable_length_ret, int* num_new_mirandas,

    GrowableArray<Method*>* all_mirandas, const Klass* super,

    Array<Method*>* methods, AccessFlags class_flags, u2 major_version,

    Handle classloader, Symbol* classname, Array<InstanceKlass*>* local_interfaces,

    TRAPS) {

  NoSafepointVerifier nsv;

  // set up default result values

  int vtable_length = 0;

  // start off with super's vtable length

  vtable_length = super == NULL ? 0 : super->vtable_length();

  // go thru each method in the methods table to see if it needs a new entry

  int len = methods->length();

  for (int i = 0; i < len; i++) {

    assert(methods->at(i)->is_method(), "must be a Method*");

    methodHandle mh(THREAD, methods->at(i));

    if (needs_new_vtable_entry(mh, super, classloader, classname, class_flags, major_version, THREAD)) {

      assert(!methods->at(i)->is_private(), "private methods should not need a vtable entry");

      vtable_length += vtableEntry::size(); // we need a new entry

    }

  }

  GrowableArray<Method*> new_mirandas(20);

  // compute the number of mirandas methods that must be added to the end

  get_mirandas(&new_mirandas, all_mirandas, super, methods, NULL, local_interfaces,

               class_flags.is_interface());

  *num_new_mirandas = new_mirandas.length();

  // Interfaces do not need interface methods in their vtables

  // This includes miranda methods and during later processing, default methods

  if (!class_flags.is_interface()) {

     vtable_length += *num_new_mirandas * vtableEntry::size();

  }

  if (Universe::is_bootstrapping() && vtable_length == 0) {

    // array classes don't have their superclass set correctly during

    // bootstrapping

    vtable_length = Universe::base_vtable_size();

  }

  if (super == NULL && vtable_length != Universe::base_vtable_size()) {

    if (Universe::is_bootstrapping()) {

      // Someone is attempting to override java.lang.Object incorrectly on the

      // bootclasspath.  The JVM cannot recover from this error including throwing

      // an exception

      vm_exit_during_initialization("Incompatible definition of java.lang.Object");

    } else {

      // Someone is attempting to redefine java.lang.Object incorrectly.  The

      // only way this should happen is from

      // SystemDictionary::resolve_from_stream(), which will detect this later

      // and throw a security exception.  So don't assert here to let

      // the exception occur.

      vtable_length = Universe::base_vtable_size();

    }

  }

  assert(vtable_length % vtableEntry::size() == 0, "bad vtable length");

  assert(vtable_length >= Universe::base_vtable_size(), "vtable too small");

  *vtable_length_ret = vtable_length;

}

int klassVtable::index_of(Method* m, int len) const {

  assert(m->has_vtable_index(), "do not ask this of non-vtable methods");

  return m->vtable_index();

}

// Copy super class's vtable to the first part (prefix) of this class's vtable,

// and return the number of entries copied.  Expects that 'super' is the Java

// super class (arrays can have "array" super classes that must be skipped).

int klassVtable::initialize_from_super(Klass* super) {

  if (super == NULL) {

    return 0;

  } else if (is_preinitialized_vtable()) {

    // A shared class' vtable is preinitialized at dump time. No need to copy

    // methods from super class for shared class, as that was already done

    // during archiving time. However, if Jvmti has redefined a class,

    // copy super class's vtable in case the super class has changed.

    return super->vtable().length();

  } else {

    // copy methods from superKlass

    klassVtable superVtable = super->vtable();

    assert(superVtable.length() <= _length, "vtable too short");

#ifdef ASSERT

    superVtable.verify(tty, true);

#endif

    superVtable.copy_vtable_to(table());

    if (log_develop_is_enabled(Trace, vtables)) {

      ResourceMark rm;

      log_develop_trace(vtables)("copy vtable from %s to %s size %d",

                                 super->internal_name(), klass()->internal_name(),

                                 _length);

    }

    return superVtable.length();

  }

}

//

// Revised lookup semantics   introduced 1.3 (Kestrel beta)

void klassVtable::initialize_vtable(bool checkconstraints, TRAPS) {

  // Note:  Arrays can have intermediate array supers.  Use java_super to skip them.

  InstanceKlass* super = _klass->java_super();

  int nofNewEntries = 0;

  bool is_shared = _klass->is_shared();

  if (!_klass->is_array_klass()) {

    ResourceMark rm(THREAD);

    log_develop_debug(vtables)("Initializing: %s", _klass->name()->as_C_string());

  }

#ifdef ASSERT

  oop* end_of_obj = (oop*)_klass + _klass->size();

  oop* end_of_vtable = (oop*)&table()[_length];

  assert(end_of_vtable <= end_of_obj, "vtable extends beyond end");

#endif

  if (Universe::is_bootstrapping()) {

    assert(!is_shared, "sanity");

    // just clear everything

    for (int i = 0; i < _length; i++) table()[i].clear();

    return;

  }

  int super_vtable_len = initialize_from_super(super);

  if (_klass->is_array_klass()) {

    assert(super_vtable_len == _length, "arrays shouldn't introduce new methods");

  } else {

    assert(_klass->is_instance_klass(), "must be InstanceKlass");

    Array<Method*>* methods = ik()->methods();

    int len = methods->length();

    int initialized = super_vtable_len;

    // Check each of this class's methods against super;

    // if override, replace in copy of super vtable, otherwise append to end

    for (int i = 0; i < len; i++) {

      // update_inherited_vtable can stop for gc - ensure using handles

      HandleMark hm(THREAD);

      assert(methods->at(i)->is_method(), "must be a Method*");

      methodHandle mh(THREAD, methods->at(i));

      bool needs_new_entry = update_inherited_vtable(ik(), mh, super_vtable_len, -1, checkconstraints, CHECK);

      if (needs_new_entry) {

        put_method_at(mh(), initialized);

        mh()->set_vtable_index(initialized); // set primary vtable index

        initialized++;

      }

    }

    // update vtable with default_methods

    Array<Method*>* default_methods = ik()->default_methods();

    if (default_methods != NULL) {

      len = default_methods->length();

      if (len > 0) {

        Array<int>* def_vtable_indices = NULL;

        if ((def_vtable_indices = ik()->default_vtable_indices()) == NULL) {

          assert(!is_shared, "shared class def_vtable_indices does not exist");

          def_vtable_indices = ik()->create_new_default_vtable_indices(len, CHECK);

        } else {

          assert(def_vtable_indices->length() == len, "reinit vtable len?");

        }

        for (int i = 0; i < len; i++) {

          HandleMark hm(THREAD);

          assert(default_methods->at(i)->is_method(), "must be a Method*");

          methodHandle mh(THREAD, default_methods->at(i));

          assert(!mh->is_private(), "private interface method in the default method list");

          bool needs_new_entry = update_inherited_vtable(ik(), mh, super_vtable_len, i, checkconstraints, CHECK);

          // needs new entry

          if (needs_new_entry) {

            put_method_at(mh(), initialized);

            if (is_preinitialized_vtable()) {

              // At runtime initialize_vtable is rerun for a shared class

              // (loaded by the non-boot loader) as part of link_class_impl().

              // The dumptime vtable index should be the same as the runtime index.

              assert(def_vtable_indices->at(i) == initialized,

                     "dump time vtable index is different from runtime index");

            } else {

              def_vtable_indices->at_put(i, initialized); //set vtable index

            }

            initialized++;

          }

        }

      }

    }

    // add miranda methods; it will also return the updated initialized

    // Interfaces do not need interface methods in their vtables

    // This includes miranda methods and during later processing, default methods

    if (!ik()->is_interface()) {

      initialized = fill_in_mirandas(initialized, THREAD);

    }

    // In class hierarchies where the accessibility is not increasing (i.e., going from private ->

    // package_private -> public/protected), the vtable might actually be smaller than our initial

    // calculation, for classfile versions for which we do not do transitive override

    // calculations.

    if (ik()->major_version() >= VTABLE_TRANSITIVE_OVERRIDE_VERSION) {

      assert(initialized == _length, "vtable initialization failed");

    } else {

      assert(initialized <= _length, "vtable initialization failed");

      for(;initialized < _length; initialized++) {

        table()[initialized].clear();

      }

    }

    NOT_PRODUCT(verify(tty, true));

  }

}

// Called for cases where a method does not override its superclass' vtable entry

// For bytecodes not produced by javac together it is possible that a method does not override

// the superclass's method, but might indirectly override a super-super class's vtable entry

// If none found, return a null superk, else return the superk of the method this does override

// For public and protected methods: if they override a superclass, they will

// also be overridden themselves appropriately.

// Private methods do not override, and are not overridden and are not in the vtable.

// Package Private methods are trickier:

// e.g. P1.A, pub m

// P2.B extends A, package private m

// P1.C extends B, public m

// P1.C.m needs to override P1.A.m and can not override P2.B.m

// Therefore: all package private methods need their own vtable entries for

// them to be the root of an inheritance overriding decision

// Package private methods may also override other vtable entries

InstanceKlass* klassVtable::find_transitive_override(InstanceKlass* initialsuper, const methodHandle& target_method,

                            int vtable_index, Handle target_loader, Symbol* target_classname, Thread * THREAD) {

  InstanceKlass* superk = initialsuper;

  while (superk != NULL && superk->super() != NULL) {

    InstanceKlass* supersuperklass = InstanceKlass::cast(superk->super());

    klassVtable ssVtable = supersuperklass->vtable();

    if (vtable_index < ssVtable.length()) {

      Method* super_method = ssVtable.method_at(vtable_index);

#ifndef PRODUCT

      Symbol* name= target_method()->name();

      Symbol* signature = target_method()->signature();

      assert(super_method->name() == name && super_method->signature() == signature, "vtable entry name/sig mismatch");

#endif

      if (supersuperklass->is_override(super_method, target_loader, target_classname, THREAD)) {

        if (log_develop_is_enabled(Trace, vtables)) {

          ResourceMark rm(THREAD);

          LogTarget(Trace, vtables) lt;

          LogStream ls(lt);

          char* sig = target_method()->name_and_sig_as_C_string();

          ls.print("transitive overriding superclass %s with %s index %d, original flags: ",

                       supersuperklass->internal_name(),

                       sig, vtable_index);

          super_method->print_linkage_flags(&ls);

          ls.print("overriders flags: ");

          target_method->print_linkage_flags(&ls);

          ls.cr();

        }

        break; // return found superk

      }

    } else  {

      // super class has no vtable entry here, stop transitive search

      superk = (InstanceKlass*)NULL;

      break;

    }

    // if no override found yet, continue to search up

    superk = superk->super() == NULL ? NULL : InstanceKlass::cast(superk->super());

  }

  return superk;

}

static void log_vtables(int i, bool overrides, const methodHandle& target_method,

                        Klass* target_klass, Method* super_method,

                        Thread* thread) {

#ifndef PRODUCT

  if (log_develop_is_enabled(Trace, vtables)) {

    ResourceMark rm(thread);

    LogTarget(Trace, vtables) lt;

    LogStream ls(lt);

    char* sig = target_method()->name_and_sig_as_C_string();

    if (overrides) {

      ls.print("overriding with %s index %d, original flags: ",

                   sig, i);

    } else {

      ls.print("NOT overriding with %s index %d, original flags: ",

                   sig, i);

    }

    super_method->print_linkage_flags(&ls);

    ls.print("overriders flags: ");

    target_method->print_linkage_flags(&ls);

    ls.cr();

  }

#endif

}

// Update child's copy of super vtable for overrides

// OR return true if a new vtable entry is required.

// Only called for InstanceKlass's, i.e. not for arrays

// If that changed, could not use _klass as handle for klass

bool klassVtable::update_inherited_vtable(InstanceKlass* klass, const methodHandle& target_method,

                                          int super_vtable_len, int default_index,

                                          bool checkconstraints, TRAPS) {

  ResourceMark rm(THREAD);

  bool allocate_new = true;

  assert(klass->is_instance_klass(), "must be InstanceKlass");

  Array<int>* def_vtable_indices = NULL;

  bool is_default = false;

  // default methods are non-private concrete methods in superinterfaces which are added

  // to the vtable with their real method_holder.

  // Since vtable and itable indices share the same storage, don't touch

  // the default method's real vtable/itable index.

  // default_vtable_indices stores the vtable value relative to this inheritor

  if (default_index >= 0 ) {

    is_default = true;

    def_vtable_indices = klass->default_vtable_indices();

    assert(!target_method()->is_private(), "private interface method flagged as default");

    assert(def_vtable_indices != NULL, "def vtable alloc?");

    assert(default_index <= def_vtable_indices->length(), "def vtable len?");

  } else {

    assert(klass == target_method()->method_holder(), "caller resp.");

    // Initialize the method's vtable index to "nonvirtual".

    // If we allocate a vtable entry, we will update it to a non-negative number.

    target_method()->set_vtable_index(Method::nonvirtual_vtable_index);

  }

  // Private, static and <init> methods are never in

  if (target_method()->is_private() || target_method()->is_static() ||

      (target_method()->name()->fast_compare(vmSymbols::object_initializer_name()) == 0)) {

    return false;

  }

  if (target_method->is_final_method(klass->access_flags())) {

    // a final method never needs a new entry; final methods can be statically

    // resolved and they have to be present in the vtable only if they override

    // a super's method, in which case they re-use its entry

    allocate_new = false;

  } else if (klass->is_interface()) {

    allocate_new = false;  // see note below in needs_new_vtable_entry

    // An interface never allocates new vtable slots, only inherits old ones.

    // This method will either be assigned its own itable index later,

    // or be assigned an inherited vtable index in the loop below.

    // default methods inherited by classes store their vtable indices

    // in the inheritor's default_vtable_indices.

    // default methods inherited by interfaces may already have a

    // valid itable index, if so, don't change it.

    // Overpass methods in an interface will be assigned an itable index later

    // by an inheriting class.

    if ((!is_default || !target_method()->has_itable_index())) {

      target_method()->set_vtable_index(Method::pending_itable_index);

    }

  }

  // we need a new entry if there is no superclass

  Klass* super = klass->super();

  if (super == NULL) {

    return allocate_new;

  }

  // search through the vtable and update overridden entries

  // Since check_signature_loaders acquires SystemDictionary_lock

  // which can block for gc, once we are in this loop, use handles

  // For classfiles built with >= jdk7, we now look for transitive overrides

  Symbol* name = target_method()->name();

  Symbol* signature = target_method()->signature();

  Klass* target_klass = target_method()->method_holder();

  if (target_klass == NULL) {

    target_klass = _klass;

  }

  Handle target_loader(THREAD, target_klass->class_loader());

  Symbol* target_classname = target_klass->name();

  for(int i = 0; i < super_vtable_len; i++) {

    Method* super_method;

    if (is_preinitialized_vtable()) {

      // If this is a shared class, the vtable is already in the final state (fully

      // initialized). Need to look at the super's vtable.

      klassVtable superVtable = super->vtable();

      super_method = superVtable.method_at(i);

    } else {

      super_method = method_at(i);

    }

    // Check if method name matches.  Ignore match if klass is an interface and the

    // matching method is a non-public java.lang.Object method.  (See JVMS 5.4.3.4)

    // This is safe because the method at this slot should never get invoked.

    // (TBD: put in a method to throw NoSuchMethodError if this slot is ever used.)

    if (super_method->name() == name && super_method->signature() == signature &&

        (!_klass->is_interface() ||

         !SystemDictionary::is_nonpublic_Object_method(super_method))) {

      // get super_klass for method_holder for the found method

      InstanceKlass* super_klass =  super_method->method_holder();

      // Whether the method is being overridden

      bool overrides = false;

      // private methods are also never overridden

      if (!super_method->is_private() &&

          (is_default

          || ((super_klass->is_override(super_method, target_loader, target_classname, THREAD))

          || ((klass->major_version() >= VTABLE_TRANSITIVE_OVERRIDE_VERSION)

          && ((super_klass = find_transitive_override(super_klass,

                             target_method, i, target_loader,

                             target_classname, THREAD))

                             != (InstanceKlass*)NULL)))))

        {

        // Package private methods always need a new entry to root their own

        // overriding. They may also override other methods.

        if (!target_method()->is_package_private()) {

          allocate_new = false;

        }

        // Do not check loader constraints for overpass methods because overpass

        // methods are created by the jvm to throw exceptions.

        if (checkconstraints && !target_method()->is_overpass()) {

          // Override vtable entry if passes loader constraint check

          // if loader constraint checking requested

          // No need to visit his super, since he and his super

          // have already made any needed loader constraints.

          // Since loader constraints are transitive, it is enough