/*

 * Copyright (c) 1997, 2016, 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 "classfile/systemDictionary.hpp"

#include "classfile/vmSymbols.hpp"

#include "gc/shared/gcLocker.hpp"

#include "logging/log.hpp"

#include "memory/resourceArea.hpp"

#include "memory/universe.inline.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/handles.inline.hpp"

#include "utilities/copy.hpp"

inline InstanceKlass* klassVtable::ik() const {

  return InstanceKlass::cast(_klass());

}

// 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,

    Handle classloader, Symbol* classname, Array<Klass*>* 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, THREAD)) {

      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);

  *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(KlassHandle super) {

  if (super.is_null()) {

    return 0;

  } 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.

  KlassHandle super (THREAD, klass()->java_super());

  int nofNewEntries = 0;

  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()) {

    // 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) {

          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));

          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);

            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);

    }

    // 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.

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

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

      put_method_at(NULL, initialized);

    }

    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.

// 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, 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);

          outputStream* logst = Log(vtables)::trace_stream();

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

          logst->print("transitive overriding superclass %s with %s::%s index %d, original flags: ",

                       supersuperklass->internal_name(),

                       _klass->internal_name(), sig, vtable_index);

          super_method->print_linkage_flags(logst);

          logst->print("overriders flags: ");

          target_method->print_linkage_flags(logst);

          logst->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, methodHandle target_method,

                        KlassHandle target_klass, Method* super_method,

                        Thread* thread) {

#ifndef PRODUCT

  if (log_develop_is_enabled(Trace, vtables)) {

    ResourceMark rm(thread);

    outputStream* logst = Log(vtables)::trace_stream();

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

    if (overrides) {

      logst->print("overriding with %s::%s index %d, original flags: ",

                   target_klass->internal_name(), sig, i);

    } else {

      logst->print("NOT overriding with %s::%s index %d, original flags: ",

                   target_klass->internal_name(), sig, i);

    }

    super_method->print_linkage_flags(logst);

    logst->print("overriders flags: ");

    target_method->print_linkage_flags(logst);

    logst->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, methodHandle target_method,

                                          int super_vtable_len, int default_index,

                                          bool checkconstraints, TRAPS) {

  ResourceMark rm;

  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 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(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);

  }

  // Static and <init> methods are never in

  if (target_method()->is_static() || target_method()->name() ==  vmSymbols::object_initializer_name()) {

    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

  if (klass->super() == NULL) {

    return allocate_new;

  }

  // private methods in classes always have a new entry in the vtable

  // specification interpretation since classic has

  // private methods not overriding

  // JDK8 adds private methods in interfaces which require invokespecial

  if (target_method()->is_private()) {

    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();

  KlassHandle target_klass(THREAD, 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 = method_at(i);

    // Check if method name matches

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

      // 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;

        }

        if (checkconstraints) {

        // 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

        // to link to the first super, and we get all the others.

          Handle super_loader(THREAD, super_klass->class_loader());

          if (target_loader() != super_loader()) {

            ResourceMark rm(THREAD);

            Symbol* failed_type_symbol =

              SystemDictionary::check_signature_loaders(signature, target_loader,

                                                        super_loader, true,

                                                        CHECK_(false));

            if (failed_type_symbol != NULL) {

              const char* msg = "loader constraint violation: when resolving "

                "overridden method \"%s\" the class loader (instance"

                " of %s) of the current class, %s, and its superclass loader "

                "(instance of %s), have different Class objects for the type "

                "%s used in the signature";

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

              const char* loader1 = SystemDictionary::loader_name(target_loader());

              char* current = target_klass->name()->as_C_string();

              const char* loader2 = SystemDictionary::loader_name(super_loader());

              char* failed_type_name = failed_type_symbol->as_C_string();

              size_t buflen = strlen(msg) + strlen(sig) + strlen(loader1) +

                strlen(current) + strlen(loader2) + strlen(failed_type_name);

              char* buf = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, buflen);

              jio_snprintf(buf, buflen, msg, sig, loader1, current, loader2,

                           failed_type_name);

              THROW_MSG_(vmSymbols::java_lang_LinkageError(), buf, false);

            }

          }

        }

        put_method_at(target_method(), i);

        overrides = true;

        if (!is_default) {

          target_method()->set_vtable_index(i);

        } else {

          if (def_vtable_indices != NULL) {

            def_vtable_indices->at_put(default_index, i);

          }

          assert(super_method->is_default_method() || super_method->is_overpass()

                 || super_method->is_abstract(), "default override error");

        }

      } else {

        overrides = false;

      }

      log_vtables(i, overrides, target_method, target_klass, super_method, THREAD);

    }

  }

  return allocate_new;

}

void klassVtable::put_method_at(Method* m, int index) {

  if (log_develop_is_enabled(Trace, vtables)) {

    ResourceMark rm;

    outputStream* logst = Log(vtables)::trace_stream();

    const char* sig = (m != NULL) ? m->name_and_sig_as_C_string() : "<NULL>";