1 /*
   2  * Copyright (c) 2012, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "classfile/bytecodeAssembler.hpp"
  27 #include "classfile/defaultMethods.hpp"
  28 #include "classfile/symbolTable.hpp"
  29 #include "classfile/systemDictionary.hpp"
  30 #include "logging/log.hpp"
  31 #include "logging/logStream.hpp"
  32 #include "memory/allocation.hpp"
  33 #include "memory/metadataFactory.hpp"
  34 #include "memory/resourceArea.hpp"
  35 #include "runtime/handles.inline.hpp"
  36 #include "runtime/signature.hpp"
  37 #include "runtime/thread.hpp"
  38 #include "oops/instanceKlass.hpp"
  39 #include "oops/klass.hpp"
  40 #include "oops/method.hpp"
  41 #include "utilities/accessFlags.hpp"
  42 #include "utilities/exceptions.hpp"
  43 #include "utilities/ostream.hpp"
  44 #include "utilities/pair.hpp"
  45 #include "utilities/resourceHash.hpp"
  46 
  47 typedef enum { QUALIFIED, DISQUALIFIED } QualifiedState;
  48 
  49 // Because we use an iterative algorithm when iterating over the type
  50 // hierarchy, we can't use traditional scoped objects which automatically do
  51 // cleanup in the destructor when the scope is exited.  PseudoScope (and
  52 // PseudoScopeMark) provides a similar functionality, but for when you want a
  53 // scoped object in non-stack memory (such as in resource memory, as we do
  54 // here).  You've just got to remember to call 'destroy()' on the scope when
  55 // leaving it (and marks have to be explicitly added).
  56 class PseudoScopeMark : public ResourceObj {
  57  public:
  58   virtual void destroy() = 0;
  59 };
  60 
  61 class PseudoScope : public ResourceObj {
  62  private:
  63   GrowableArray<PseudoScopeMark*> _marks;
  64  public:
  65 
  66   static PseudoScope* cast(void* data) {
  67     return static_cast<PseudoScope*>(data);
  68   }
  69 
  70   void add_mark(PseudoScopeMark* psm) {
  71    _marks.append(psm);
  72   }
  73 
  74   void destroy() {
  75     for (int i = 0; i < _marks.length(); ++i) {
  76       _marks.at(i)->destroy();
  77     }
  78   }
  79 };
  80 
  81 static void print_slot(outputStream* str, Symbol* name, Symbol* signature) {
  82   str->print("%s%s", name->as_C_string(), signature->as_C_string());
  83 }
  84 
  85 static void print_method(outputStream* str, Method* mo, bool with_class=true) {
  86   if (with_class) {
  87     str->print("%s.", mo->klass_name()->as_C_string());
  88   }
  89   print_slot(str, mo->name(), mo->signature());
  90 }
  91 
  92 /**
  93  * Perform a depth-first iteration over the class hierarchy, applying
  94  * algorithmic logic as it goes.
  95  *
  96  * This class is one half of the inheritance hierarchy analysis mechanism.
  97  * It is meant to be used in conjunction with another class, the algorithm,
  98  * which is indicated by the ALGO template parameter.  This class can be
  99  * paired with any algorithm class that provides the required methods.
 100  *
 101  * This class contains all the mechanics for iterating over the class hierarchy
 102  * starting at a particular root, without recursing (thus limiting stack growth
 103  * from this point).  It visits each superclass (if present) and superinterface
 104  * in a depth-first manner, with callbacks to the ALGO class as each class is
 105  * encountered (visit()), The algorithm can cut-off further exploration of a
 106  * particular branch by returning 'false' from a visit() call.
 107  *
 108  * The ALGO class, must provide a visit() method, which each of which will be
 109  * called once for each node in the inheritance tree during the iteration.  In
 110  * addition, it can provide a memory block via new_node_data(InstanceKlass*),
 111  * which it can use for node-specific storage (and access via the
 112  * current_data() and data_at_depth(int) methods).
 113  *
 114  * Bare minimum needed to be an ALGO class:
 115  * class Algo : public HierarchyVisitor<Algo> {
 116  *   void* new_node_data(InstanceKlass* cls) { return NULL; }
 117  *   void free_node_data(void* data) { return; }
 118  *   bool visit() { return true; }
 119  * };
 120  */
 121 template <class ALGO>
 122 class HierarchyVisitor : StackObj {
 123  private:
 124 
 125   class Node : public ResourceObj {
 126    public:
 127     InstanceKlass* _class;
 128     bool _super_was_visited;
 129     int _interface_index;
 130     void* _algorithm_data;
 131 
 132     Node(InstanceKlass* cls, void* data, bool visit_super)
 133         : _class(cls), _super_was_visited(!visit_super),
 134           _interface_index(0), _algorithm_data(data) {}
 135 
 136     int number_of_interfaces() { return _class->local_interfaces()->length(); }
 137     int interface_index() { return _interface_index; }
 138     void set_super_visited() { _super_was_visited = true; }
 139     void increment_visited_interface() { ++_interface_index; }
 140     void set_all_interfaces_visited() {
 141       _interface_index = number_of_interfaces();
 142     }
 143     bool has_visited_super() { return _super_was_visited; }
 144     bool has_visited_all_interfaces() {
 145       return interface_index() >= number_of_interfaces();
 146     }
 147     InstanceKlass* interface_at(int index) {
 148       return InstanceKlass::cast(_class->local_interfaces()->at(index));
 149     }
 150     InstanceKlass* next_super() { return _class->java_super(); }
 151     InstanceKlass* next_interface() {
 152       return interface_at(interface_index());
 153     }
 154   };
 155 
 156   bool _visited_Object;
 157   GrowableArray<Node*> _path;
 158 
 159   Node* current_top() const { return _path.top(); }
 160   bool has_more_nodes() const { return !_path.is_empty(); }
 161   void push(InstanceKlass* cls, void* data) {
 162     assert(cls != NULL, "Requires a valid instance class");
 163     Node* node = new Node(cls, data, has_super(cls));
 164     if (cls == SystemDictionary::Object_klass()) {
 165       _visited_Object = true;
 166     }
 167     _path.push(node);
 168   }
 169   void pop() { _path.pop(); }
 170 
 171   // Since the starting point can be an interface, we must ensure we catch
 172   // j.l.Object as the super once in those cases. The _visited_Object flag
 173   // only ensures we don't then repeatedly enqueue Object for each interface
 174   // in the class hierarchy.
 175   bool has_super(InstanceKlass* cls) {
 176     return cls->super() != NULL && (!_visited_Object || !cls->is_interface());
 177   }
 178 
 179   Node* node_at_depth(int i) const {
 180     return (i >= _path.length()) ? NULL : _path.at(_path.length() - i - 1);
 181   }
 182 
 183  protected:
 184 
 185   // Accessors available to the algorithm
 186   int current_depth() const { return _path.length() - 1; }
 187 
 188   InstanceKlass* class_at_depth(int i) {
 189     Node* n = node_at_depth(i);
 190     return n == NULL ? NULL : n->_class;
 191   }
 192   InstanceKlass* current_class() { return class_at_depth(0); }
 193 
 194   void* data_at_depth(int i) {
 195     Node* n = node_at_depth(i);
 196     return n == NULL ? NULL : n->_algorithm_data;
 197   }
 198   void* current_data() { return data_at_depth(0); }
 199 
 200  public:
 201 
 202   void run(InstanceKlass* root) {
 203     ALGO* algo = static_cast<ALGO*>(this);
 204 
 205     void* algo_data = algo->new_node_data(root);
 206     push(root, algo_data);
 207     bool top_needs_visit = true;
 208 
 209     do {
 210       Node* top = current_top();
 211       if (top_needs_visit) {
 212         if (algo->visit() == false) {
 213           // algorithm does not want to continue along this path.  Arrange
 214           // it so that this state is immediately popped off the stack
 215           top->set_super_visited();
 216           top->set_all_interfaces_visited();
 217         }
 218         top_needs_visit = false;
 219       }
 220 
 221       if (top->has_visited_super() && top->has_visited_all_interfaces()) {
 222         algo->free_node_data(top->_algorithm_data);
 223         pop();
 224       } else {
 225         InstanceKlass* next = NULL;
 226         if (top->has_visited_super() == false) {
 227           next = top->next_super();
 228           top->set_super_visited();
 229         } else {
 230           next = top->next_interface();
 231           top->increment_visited_interface();
 232         }
 233         assert(next != NULL, "Otherwise we shouldn't be here");
 234         algo_data = algo->new_node_data(next);
 235         push(next, algo_data);
 236         top_needs_visit = true;
 237       }
 238     } while (has_more_nodes());
 239   }
 240 };
 241 
 242 class PrintHierarchy : public HierarchyVisitor<PrintHierarchy> {
 243  private:
 244    outputStream* _st;
 245  public:
 246   bool visit() {
 247     InstanceKlass* cls = current_class();
 248     streamIndentor si(_st, current_depth() * 2);
 249     _st->indent().print_cr("%s", cls->name()->as_C_string());
 250     return true;
 251   }
 252 
 253   void* new_node_data(InstanceKlass* cls) { return NULL; }
 254   void free_node_data(void* data) { return; }
 255 
 256   PrintHierarchy(outputStream* st = tty) : _st(st) {}
 257 };
 258 
 259 // Used to register InstanceKlass objects and all related metadata structures
 260 // (Methods, ConstantPools) as "in-use" by the current thread so that they can't
 261 // be deallocated by class redefinition while we're using them.  The classes are
 262 // de-registered when this goes out of scope.
 263 //
 264 // Once a class is registered, we need not bother with methodHandles or
 265 // constantPoolHandles for it's associated metadata.
 266 class KeepAliveRegistrar : public StackObj {
 267  private:
 268   Thread* _thread;
 269   GrowableArray<ConstantPool*> _keep_alive;
 270 
 271  public:
 272   KeepAliveRegistrar(Thread* thread) : _thread(thread), _keep_alive(20) {
 273     assert(thread == Thread::current(), "Must be current thread");
 274   }
 275 
 276   ~KeepAliveRegistrar() {
 277     for (int i = _keep_alive.length() - 1; i >= 0; --i) {
 278       ConstantPool* cp = _keep_alive.at(i);
 279       int idx = _thread->metadata_handles()->find_from_end(cp);
 280       assert(idx > 0, "Must be in the list");
 281       _thread->metadata_handles()->remove_at(idx);
 282     }
 283   }
 284 
 285   // Register a class as 'in-use' by the thread.  It's fine to register a class
 286   // multiple times (though perhaps inefficient)
 287   void register_class(InstanceKlass* ik) {
 288     ConstantPool* cp = ik->constants();
 289     _keep_alive.push(cp);
 290     _thread->metadata_handles()->push(cp);
 291   }
 292 };
 293 
 294 class KeepAliveVisitor : public HierarchyVisitor<KeepAliveVisitor> {
 295  private:
 296   KeepAliveRegistrar* _registrar;
 297 
 298  public:
 299   KeepAliveVisitor(KeepAliveRegistrar* registrar) : _registrar(registrar) {}
 300 
 301   void* new_node_data(InstanceKlass* cls) { return NULL; }
 302   void free_node_data(void* data) { return; }
 303 
 304   bool visit() {
 305     _registrar->register_class(current_class());
 306     return true;
 307   }
 308 };
 309 
 310 
 311 // A method family contains a set of all methods that implement a single
 312 // erased method. As members of the set are collected while walking over the
 313 // hierarchy, they are tagged with a qualification state.  The qualification
 314 // state for an erased method is set to disqualified if there exists a path
 315 // from the root of hierarchy to the method that contains an interleaving
 316 // erased method defined in an interface.
 317 
 318 class MethodFamily : public ResourceObj {
 319  private:
 320 
 321   GrowableArray<Pair<Method*,QualifiedState> > _members;
 322   ResourceHashtable<Method*, int> _member_index;
 323 
 324   Method* _selected_target;  // Filled in later, if a unique target exists
 325   Symbol* _exception_message; // If no unique target is found
 326   Symbol* _exception_name;    // If no unique target is found
 327 
 328   bool contains_method(Method* method) {
 329     int* lookup = _member_index.get(method);
 330     return lookup != NULL;
 331   }
 332 
 333   void add_method(Method* method, QualifiedState state) {
 334     Pair<Method*,QualifiedState> entry(method, state);
 335     _member_index.put(method, _members.length());
 336     _members.append(entry);
 337   }
 338 
 339   void disqualify_method(Method* method) {
 340     int* index = _member_index.get(method);
 341     guarantee(index != NULL && *index >= 0 && *index < _members.length(), "bad index");
 342     _members.at(*index).second = DISQUALIFIED;
 343   }
 344 
 345   Symbol* generate_no_defaults_message(TRAPS) const;
 346   Symbol* generate_method_message(Symbol *klass_name, Method* method, TRAPS) const;
 347   Symbol* generate_conflicts_message(GrowableArray<Method*>* methods, TRAPS) const;
 348 
 349  public:
 350 
 351   MethodFamily()
 352       : _selected_target(NULL), _exception_message(NULL), _exception_name(NULL) {}
 353 
 354   void set_target_if_empty(Method* m) {
 355     if (_selected_target == NULL && !m->is_overpass()) {
 356       _selected_target = m;
 357     }
 358   }
 359 
 360   void record_qualified_method(Method* m) {
 361     // If the method already exists in the set as qualified, this operation is
 362     // redundant.  If it already exists as disqualified, then we leave it as
 363     // disqualfied.  Thus we only add to the set if it's not already in the
 364     // set.
 365     if (!contains_method(m)) {
 366       add_method(m, QUALIFIED);
 367     }
 368   }
 369 
 370   void record_disqualified_method(Method* m) {
 371     // If not in the set, add it as disqualified.  If it's already in the set,
 372     // then set the state to disqualified no matter what the previous state was.
 373     if (!contains_method(m)) {
 374       add_method(m, DISQUALIFIED);
 375     } else {
 376       disqualify_method(m);
 377     }
 378   }
 379 
 380   bool has_target() const { return _selected_target != NULL; }
 381   bool throws_exception() { return _exception_message != NULL; }
 382 
 383   Method* get_selected_target() { return _selected_target; }
 384   Symbol* get_exception_message() { return _exception_message; }
 385   Symbol* get_exception_name() { return _exception_name; }
 386 
 387   // Either sets the target or the exception error message
 388   void determine_target(InstanceKlass* root, TRAPS) {
 389     if (has_target() || throws_exception()) {
 390       return;
 391     }
 392 
 393     // Qualified methods are maximally-specific methods
 394     // These include public, instance concrete (=default) and abstract methods
 395     GrowableArray<Method*> qualified_methods;
 396     int num_defaults = 0;
 397     int default_index = -1;
 398     int qualified_index = -1;
 399     for (int i = 0; i < _members.length(); ++i) {
 400       Pair<Method*,QualifiedState> entry = _members.at(i);
 401       if (entry.second == QUALIFIED) {
 402         qualified_methods.append(entry.first);
 403         qualified_index++;
 404         if (entry.first->is_default_method()) {
 405           num_defaults++;
 406           default_index = qualified_index;
 407 
 408         }
 409       }
 410     }
 411 
 412     if (num_defaults == 0) {
 413       // If the root klass has a static method with matching name and signature
 414       // then do not generate an overpass method because it will hide the
 415       // static method during resolution.
 416       if (qualified_methods.length() == 0) {
 417         _exception_message = generate_no_defaults_message(CHECK);
 418       } else {
 419         assert(root != NULL, "Null root class");
 420         _exception_message = generate_method_message(root->name(), qualified_methods.at(0), CHECK);
 421       }
 422       _exception_name = vmSymbols::java_lang_AbstractMethodError();
 423 
 424     // If only one qualified method is default, select that
 425     } else if (num_defaults == 1) {
 426         _selected_target = qualified_methods.at(default_index);
 427 
 428     } else if (num_defaults > 1) {
 429       _exception_message = generate_conflicts_message(&qualified_methods,CHECK);
 430       _exception_name = vmSymbols::java_lang_IncompatibleClassChangeError();
 431       LogTarget(Debug, defaultmethods) lt;
 432       if (lt.is_enabled()) {
 433         LogStream ls(lt);
 434         _exception_message->print_value_on(&ls);
 435         ls.cr();
 436       }
 437     }
 438   }
 439 
 440   void print_selected(outputStream* str, int indent) const {
 441     assert(has_target(), "Should be called otherwise");
 442     streamIndentor si(str, indent * 2);
 443     str->indent().print("Selected method: ");
 444     print_method(str, _selected_target);
 445     Klass* method_holder = _selected_target->method_holder();
 446     if (!method_holder->is_interface()) {
 447       str->print(" : in superclass");
 448     }
 449     str->cr();
 450   }
 451 
 452   void print_exception(outputStream* str, int indent) {
 453     assert(throws_exception(), "Should be called otherwise");
 454     assert(_exception_name != NULL, "exception_name should be set");
 455     streamIndentor si(str, indent * 2);
 456     str->indent().print_cr("%s: %s", _exception_name->as_C_string(), _exception_message->as_C_string());
 457   }
 458 };
 459 
 460 Symbol* MethodFamily::generate_no_defaults_message(TRAPS) const {
 461   return SymbolTable::new_symbol("No qualifying defaults found", THREAD);
 462 }
 463 
 464 Symbol* MethodFamily::generate_method_message(Symbol *klass_name, Method* method, TRAPS) const {
 465   stringStream ss;
 466   ss.print("Method ");
 467   Symbol* name = method->name();
 468   Symbol* signature = method->signature();
 469   ss.write((const char*)klass_name->bytes(), klass_name->utf8_length());
 470   ss.print(".");
 471   ss.write((const char*)name->bytes(), name->utf8_length());
 472   ss.write((const char*)signature->bytes(), signature->utf8_length());
 473   ss.print(" is abstract");
 474   return SymbolTable::new_symbol(ss.base(), (int)ss.size(), THREAD);
 475 }
 476 
 477 Symbol* MethodFamily::generate_conflicts_message(GrowableArray<Method*>* methods, TRAPS) const {
 478   stringStream ss;
 479   ss.print("Conflicting default methods:");
 480   for (int i = 0; i < methods->length(); ++i) {
 481     Method* method = methods->at(i);
 482     Symbol* klass = method->klass_name();
 483     Symbol* name = method->name();
 484     ss.print(" ");
 485     ss.write((const char*)klass->bytes(), klass->utf8_length());
 486     ss.print(".");
 487     ss.write((const char*)name->bytes(), name->utf8_length());
 488   }
 489   return SymbolTable::new_symbol(ss.base(), (int)ss.size(), THREAD);
 490 }
 491 
 492 
 493 class StateRestorer;
 494 
 495 // StatefulMethodFamily is a wrapper around a MethodFamily that maintains the
 496 // qualification state during hierarchy visitation, and applies that state
 497 // when adding members to the MethodFamily
 498 class StatefulMethodFamily : public ResourceObj {
 499   friend class StateRestorer;
 500  private:
 501   QualifiedState _qualification_state;
 502 
 503   void set_qualification_state(QualifiedState state) {
 504     _qualification_state = state;
 505   }
 506 
 507  protected:
 508   MethodFamily _method_family;
 509 
 510  public:
 511   StatefulMethodFamily() {
 512    _qualification_state = QUALIFIED;
 513   }
 514 
 515   void set_target_if_empty(Method* m) { _method_family.set_target_if_empty(m); }
 516 
 517   MethodFamily* get_method_family() { return &_method_family; }
 518 
 519   StateRestorer* record_method_and_dq_further(Method* mo);
 520 };
 521 
 522 class StateRestorer : public PseudoScopeMark {
 523  private:
 524   StatefulMethodFamily* _method;
 525   QualifiedState _state_to_restore;
 526  public:
 527   StateRestorer(StatefulMethodFamily* dm, QualifiedState state)
 528       : _method(dm), _state_to_restore(state) {}
 529   ~StateRestorer() { destroy(); }
 530   void restore_state() { _method->set_qualification_state(_state_to_restore); }
 531   virtual void destroy() { restore_state(); }
 532 };
 533 
 534 StateRestorer* StatefulMethodFamily::record_method_and_dq_further(Method* mo) {
 535   StateRestorer* mark = new StateRestorer(this, _qualification_state);
 536   if (_qualification_state == QUALIFIED) {
 537     _method_family.record_qualified_method(mo);
 538   } else {
 539     _method_family.record_disqualified_method(mo);
 540   }
 541   // Everything found "above"??? this method in the hierarchy walk is set to
 542   // disqualified
 543   set_qualification_state(DISQUALIFIED);
 544   return mark;
 545 }
 546 
 547 // Represents a location corresponding to a vtable slot for methods that
 548 // neither the class nor any of it's ancestors provide an implementaion.
 549 // Default methods may be present to fill this slot.
 550 class EmptyVtableSlot : public ResourceObj {
 551  private:
 552   Symbol* _name;
 553   Symbol* _signature;
 554   int _size_of_parameters;
 555   MethodFamily* _binding;
 556 
 557  public:
 558   EmptyVtableSlot(Method* method)
 559       : _name(method->name()), _signature(method->signature()),
 560         _size_of_parameters(method->size_of_parameters()), _binding(NULL) {}
 561 
 562   Symbol* name() const { return _name; }
 563   Symbol* signature() const { return _signature; }
 564   int size_of_parameters() const { return _size_of_parameters; }
 565 
 566   void bind_family(MethodFamily* lm) { _binding = lm; }
 567   bool is_bound() { return _binding != NULL; }
 568   MethodFamily* get_binding() { return _binding; }
 569 
 570   void print_on(outputStream* str) const {
 571     print_slot(str, name(), signature());
 572   }
 573 };
 574 
 575 static bool already_in_vtable_slots(GrowableArray<EmptyVtableSlot*>* slots, Method* m) {
 576   bool found = false;
 577   for (int j = 0; j < slots->length(); ++j) {
 578     if (slots->at(j)->name() == m->name() &&
 579         slots->at(j)->signature() == m->signature() ) {
 580       found = true;
 581       break;
 582     }
 583   }
 584   return found;
 585 }
 586 
 587 static void find_empty_vtable_slots(GrowableArray<EmptyVtableSlot*>* slots,
 588     InstanceKlass* klass, const GrowableArray<Method*>* mirandas, TRAPS) {
 589 
 590   assert(klass != NULL, "Must be valid class");
 591 
 592   // All miranda methods are obvious candidates
 593   for (int i = 0; i < mirandas->length(); ++i) {
 594     Method* m = mirandas->at(i);
 595     if (!already_in_vtable_slots(slots, m)) {
 596       slots->append(new EmptyVtableSlot(m));
 597     }
 598   }
 599 
 600   // Also any overpasses in our superclasses, that we haven't implemented.
 601   // (can't use the vtable because it is not guaranteed to be initialized yet)
 602   InstanceKlass* super = klass->java_super();
 603   while (super != NULL) {
 604     for (int i = 0; i < super->methods()->length(); ++i) {
 605       Method* m = super->methods()->at(i);
 606       if (m->is_overpass() || m->is_static()) {
 607         // m is a method that would have been a miranda if not for the
 608         // default method processing that occurred on behalf of our superclass,
 609         // so it's a method we want to re-examine in this new context.  That is,
 610         // unless we have a real implementation of it in the current class.
 611         if (!already_in_vtable_slots(slots, m)) {
 612           Method *impl = klass->lookup_method(m->name(), m->signature());
 613           if (impl == NULL || impl->is_overpass() || impl->is_static()) {
 614             slots->append(new EmptyVtableSlot(m));
 615           }
 616         }
 617       }
 618     }
 619 
 620     // also any default methods in our superclasses
 621     if (super->default_methods() != NULL) {
 622       for (int i = 0; i < super->default_methods()->length(); ++i) {
 623         Method* m = super->default_methods()->at(i);
 624         // m is a method that would have been a miranda if not for the
 625         // default method processing that occurred on behalf of our superclass,
 626         // so it's a method we want to re-examine in this new context.  That is,
 627         // unless we have a real implementation of it in the current class.
 628         if (!already_in_vtable_slots(slots, m)) {
 629           Method* impl = klass->lookup_method(m->name(), m->signature());
 630           if (impl == NULL || impl->is_overpass() || impl->is_static()) {
 631             slots->append(new EmptyVtableSlot(m));
 632           }
 633         }
 634       }
 635     }
 636     super = super->java_super();
 637   }
 638 
 639   LogTarget(Debug, defaultmethods) lt;
 640   if (lt.is_enabled()) {
 641     lt.print("Slots that need filling:");
 642     ResourceMark rm;
 643     LogStream ls(lt);
 644     streamIndentor si(&ls);
 645     for (int i = 0; i < slots->length(); ++i) {
 646       ls.indent();
 647       slots->at(i)->print_on(&ls);
 648       ls.cr();
 649     }
 650   }
 651 }
 652 
 653 // Iterates over the superinterface type hierarchy looking for all methods
 654 // with a specific erased signature.
 655 class FindMethodsByErasedSig : public HierarchyVisitor<FindMethodsByErasedSig> {
 656  private:
 657   // Context data
 658   Symbol* _method_name;
 659   Symbol* _method_signature;
 660   StatefulMethodFamily*  _family;
 661   bool _cur_class_is_interface;
 662 
 663  public:
 664   FindMethodsByErasedSig(Symbol* name, Symbol* signature, bool is_interf) :
 665       _method_name(name), _method_signature(signature), _family(NULL),
 666       _cur_class_is_interface(is_interf) {}
 667 
 668   void get_discovered_family(MethodFamily** family) {
 669       if (_family != NULL) {
 670         *family = _family->get_method_family();
 671       } else {
 672         *family = NULL;
 673       }
 674   }
 675 
 676   void* new_node_data(InstanceKlass* cls) { return new PseudoScope(); }
 677   void free_node_data(void* node_data) {
 678     PseudoScope::cast(node_data)->destroy();
 679   }
 680 
 681   // Find all methods on this hierarchy that match this
 682   // method's erased (name, signature)
 683   bool visit() {
 684     PseudoScope* scope = PseudoScope::cast(current_data());
 685     InstanceKlass* iklass = current_class();
 686 
 687     Method* m = iklass->find_method(_method_name, _method_signature);
 688     // Private interface methods are not candidates for default methods.
 689     // invokespecial to private interface methods doesn't use default method logic.
 690     // Private class methods are not candidates for default methods.
 691     // Private methods do not override default methods, so need to perform
 692     // default method inheritance without including private methods.
 693     // The overpasses are your supertypes' errors, we do not include them.
 694     // Non-public methods in java.lang.Object are not candidates for default
 695     // methods.
 696     // Future: take access controls into account for superclass methods
 697     if (m != NULL && !m->is_static() && !m->is_overpass() && !m->is_private() &&
 698      (!_cur_class_is_interface || !SystemDictionary::is_nonpublic_Object_method(m))) {
 699       if (_family == NULL) {
 700         _family = new StatefulMethodFamily();
 701       }
 702 
 703       if (iklass->is_interface()) {
 704         StateRestorer* restorer = _family->record_method_and_dq_further(m);
 705         scope->add_mark(restorer);
 706       } else {
 707         // This is the rule that methods in classes "win" (bad word) over
 708         // methods in interfaces. This works because of single inheritance.
 709         // Private methods in classes do not "win", they will be found
 710         // first on searching, but overriding for invokevirtual needs
 711         // to find default method candidates for the same signature
 712         _family->set_target_if_empty(m);
 713       }
 714     }
 715     return true;
 716   }
 717 
 718 };
 719 
 720 
 721 
 722 static void create_defaults_and_exceptions(
 723     GrowableArray<EmptyVtableSlot*>* slots, InstanceKlass* klass, TRAPS);
 724 
 725 static void generate_erased_defaults(
 726      InstanceKlass* klass, EmptyVtableSlot* slot, bool is_intf, TRAPS) {
 727 
 728   // sets up a set of methods with the same exact erased signature
 729   FindMethodsByErasedSig visitor(slot->name(), slot->signature(), is_intf);
 730   visitor.run(klass);
 731 
 732   MethodFamily* family;
 733   visitor.get_discovered_family(&family);
 734   if (family != NULL) {
 735     family->determine_target(klass, CHECK);
 736     slot->bind_family(family);
 737   }
 738 }
 739 
 740 static void merge_in_new_methods(InstanceKlass* klass,
 741     GrowableArray<Method*>* new_methods, TRAPS);
 742 static void create_default_methods( InstanceKlass* klass,
 743     GrowableArray<Method*>* new_methods, TRAPS);
 744 
 745 // This is the guts of the default methods implementation.  This is called just
 746 // after the classfile has been parsed if some ancestor has default methods.
 747 //
 748 // First it finds any name/signature slots that need any implementation (either
 749 // because they are miranda or a superclass's implementation is an overpass
 750 // itself).  For each slot, iterate over the hierarchy, to see if they contain a
 751 // signature that matches the slot we are looking at.
 752 //
 753 // For each slot filled, we either record the default method candidate in the
 754 // klass default_methods list or, only to handle exception cases, we create an
 755 // overpass method that throws an exception and add it to the klass methods list.
 756 // The JVM does not create bridges nor handle generic signatures here.
 757 void DefaultMethods::generate_default_methods(
 758     InstanceKlass* klass, const GrowableArray<Method*>* mirandas, TRAPS) {
 759   assert(klass != NULL, "invariant");
 760   assert(klass != SystemDictionary::Object_klass(), "Shouldn't be called for Object");
 761 
 762   // This resource mark is the bound for all memory allocation that takes
 763   // place during default method processing.  After this goes out of scope,
 764   // all (Resource) objects' memory will be reclaimed.  Be careful if adding an
 765   // embedded resource mark under here as that memory can't be used outside
 766   // whatever scope it's in.
 767   ResourceMark rm(THREAD);
 768 
 769   // Keep entire hierarchy alive for the duration of the computation
 770   constantPoolHandle cp(THREAD, klass->constants());
 771   KeepAliveRegistrar keepAlive(THREAD);
 772   KeepAliveVisitor loadKeepAlive(&keepAlive);
 773   loadKeepAlive.run(klass);
 774 
 775   LogTarget(Debug, defaultmethods) lt;
 776   if (lt.is_enabled()) {
 777     ResourceMark rm;
 778     lt.print("%s %s requires default method processing",
 779              klass->is_interface() ? "Interface" : "Class",
 780              klass->name()->as_klass_external_name());
 781     LogStream ls(lt);
 782     PrintHierarchy printer(&ls);
 783     printer.run(klass);
 784   }
 785 
 786   GrowableArray<EmptyVtableSlot*> empty_slots;
 787   find_empty_vtable_slots(&empty_slots, klass, mirandas, CHECK);
 788 
 789   if (empty_slots.length() > 0) {
 790     for (int i = 0; i < empty_slots.length(); ++i) {
 791       EmptyVtableSlot* slot = empty_slots.at(i);
 792       LogTarget(Debug, defaultmethods) lt;
 793       if (lt.is_enabled()) {
 794         LogStream ls(lt);
 795         streamIndentor si(&ls, 2);
 796         ls.indent().print("Looking for default methods for slot ");
 797         slot->print_on(&ls);
 798         ls.cr();
 799       }
 800       generate_erased_defaults(klass, slot, klass->is_interface(), CHECK);
 801     }
 802     log_debug(defaultmethods)("Creating defaults and overpasses...");
 803     create_defaults_and_exceptions(&empty_slots, klass, CHECK);
 804   }
 805   log_debug(defaultmethods)("Default method processing complete");
 806 }
 807 
 808 static int assemble_method_error(
 809     BytecodeConstantPool* cp, BytecodeBuffer* buffer, Symbol* errorName, Symbol* message, TRAPS) {
 810 
 811   Symbol* init = vmSymbols::object_initializer_name();
 812   Symbol* sig = vmSymbols::string_void_signature();
 813 
 814   BytecodeAssembler assem(buffer, cp);
 815 
 816   assem._new(errorName);
 817   assem.dup();
 818   assem.load_string(message);
 819   assem.invokespecial(errorName, init, sig);
 820   assem.athrow();
 821 
 822   return 3; // max stack size: [ exception, exception, string ]
 823 }
 824 
 825 static Method* new_method(
 826     BytecodeConstantPool* cp, BytecodeBuffer* bytecodes, Symbol* name,
 827     Symbol* sig, AccessFlags flags, int max_stack, int params,
 828     ConstMethod::MethodType mt, TRAPS) {
 829 
 830   address code_start = 0;
 831   int code_length = 0;
 832   InlineTableSizes sizes;
 833 
 834   if (bytecodes != NULL && bytecodes->length() > 0) {
 835     code_start = static_cast<address>(bytecodes->adr_at(0));
 836     code_length = bytecodes->length();
 837   }
 838 
 839   Method* m = Method::allocate(cp->pool_holder()->class_loader_data(),
 840                                code_length, flags, &sizes,
 841                                mt, CHECK_NULL);
 842 
 843   m->set_constants(NULL); // This will get filled in later
 844   m->set_name_index(cp->utf8(name));
 845   m->set_signature_index(cp->utf8(sig));
 846   ResultTypeFinder rtf(sig);
 847   m->constMethod()->set_result_type(rtf.type());
 848   m->set_size_of_parameters(params);
 849   m->set_max_stack(max_stack);
 850   m->set_max_locals(params);
 851   m->constMethod()->set_stackmap_data(NULL);
 852   m->set_code(code_start);
 853 
 854   return m;
 855 }
 856 
 857 static void switchover_constant_pool(BytecodeConstantPool* bpool,
 858     InstanceKlass* klass, GrowableArray<Method*>* new_methods, TRAPS) {
 859 
 860   if (new_methods->length() > 0) {
 861     ConstantPool* cp = bpool->create_constant_pool(CHECK);
 862     if (cp != klass->constants()) {
 863       // Copy resolved anonymous class into new constant pool.
 864       if (klass->is_unsafe_anonymous() || klass->is_nonfindable()) {
 865         cp->klass_at_put(klass->this_class_index(), klass);
 866       }
 867       klass->class_loader_data()->add_to_deallocate_list(klass->constants());
 868       klass->set_constants(cp);
 869       cp->set_pool_holder(klass);
 870 
 871       for (int i = 0; i < new_methods->length(); ++i) {
 872         new_methods->at(i)->set_constants(cp);
 873       }
 874       for (int i = 0; i < klass->methods()->length(); ++i) {
 875         Method* mo = klass->methods()->at(i);
 876         mo->set_constants(cp);
 877       }
 878     }
 879   }
 880 }
 881 
 882 // Create default_methods list for the current class.
 883 // With the VM only processing erased signatures, the VM only
 884 // creates an overpass in a conflict case or a case with no candidates.
 885 // This allows virtual methods to override the overpass, but ensures
 886 // that a local method search will find the exception rather than an abstract
 887 // or default method that is not a valid candidate.
 888 //
 889 // Note that if overpass method are ever created that are not exception
 890 // throwing methods then the loader constraint checking logic for vtable and
 891 // itable creation needs to be changed to check loader constraints for the
 892 // overpass methods that do not throw exceptions.
 893 static void create_defaults_and_exceptions(GrowableArray<EmptyVtableSlot*>* slots,
 894     InstanceKlass* klass, TRAPS) {
 895 
 896   GrowableArray<Method*> overpasses;
 897   GrowableArray<Method*> defaults;
 898   BytecodeConstantPool bpool(klass->constants());
 899 
 900   for (int i = 0; i < slots->length(); ++i) {
 901     EmptyVtableSlot* slot = slots->at(i);
 902 
 903     if (slot->is_bound()) {
 904       MethodFamily* method = slot->get_binding();
 905       BytecodeBuffer buffer;
 906 
 907       LogTarget(Debug, defaultmethods) lt;
 908       if (lt.is_enabled()) {
 909         ResourceMark rm(THREAD);
 910         LogStream ls(lt);
 911         ls.print("for slot: ");
 912         slot->print_on(&ls);
 913         ls.cr();
 914         if (method->has_target()) {
 915           method->print_selected(&ls, 1);
 916         } else if (method->throws_exception()) {
 917           method->print_exception(&ls, 1);
 918         }
 919       }
 920 
 921       if (method->has_target()) {
 922         Method* selected = method->get_selected_target();
 923         if (selected->method_holder()->is_interface()) {
 924           assert(!selected->is_private(), "pushing private interface method as default");
 925           defaults.push(selected);
 926         }
 927       } else if (method->throws_exception()) {
 928         int max_stack = assemble_method_error(&bpool, &buffer,
 929            method->get_exception_name(), method->get_exception_message(), CHECK);
 930         AccessFlags flags = accessFlags_from(
 931           JVM_ACC_PUBLIC | JVM_ACC_SYNTHETIC | JVM_ACC_BRIDGE);
 932          Method* m = new_method(&bpool, &buffer, slot->name(), slot->signature(),
 933           flags, max_stack, slot->size_of_parameters(),
 934           ConstMethod::OVERPASS, CHECK);
 935         // We push to the methods list:
 936         // overpass methods which are exception throwing methods
 937         if (m != NULL) {
 938           overpasses.push(m);
 939         }
 940       }
 941     }
 942   }
 943 
 944 
 945   log_debug(defaultmethods)("Created %d overpass methods", overpasses.length());
 946   log_debug(defaultmethods)("Created %d default  methods", defaults.length());
 947 
 948   if (overpasses.length() > 0) {
 949     switchover_constant_pool(&bpool, klass, &overpasses, CHECK);
 950     merge_in_new_methods(klass, &overpasses, CHECK);
 951   }
 952   if (defaults.length() > 0) {
 953     create_default_methods(klass, &defaults, CHECK);
 954   }
 955 }
 956 
 957 static void create_default_methods(InstanceKlass* klass,
 958     GrowableArray<Method*>* new_methods, TRAPS) {
 959 
 960   int new_size = new_methods->length();
 961   Array<Method*>* total_default_methods = MetadataFactory::new_array<Method*>(
 962       klass->class_loader_data(), new_size, NULL, CHECK);
 963   for (int index = 0; index < new_size; index++ ) {
 964     total_default_methods->at_put(index, new_methods->at(index));
 965   }
 966   Method::sort_methods(total_default_methods, /*set_idnums=*/false);
 967 
 968   klass->set_default_methods(total_default_methods);
 969 }
 970 
 971 static void sort_methods(GrowableArray<Method*>* methods) {
 972   // Note that this must sort using the same key as is used for sorting
 973   // methods in InstanceKlass.
 974   bool sorted = true;
 975   for (int i = methods->length() - 1; i > 0; --i) {
 976     for (int j = 0; j < i; ++j) {
 977       Method* m1 = methods->at(j);
 978       Method* m2 = methods->at(j + 1);
 979       if ((uintptr_t)m1->name() > (uintptr_t)m2->name()) {
 980         methods->at_put(j, m2);
 981         methods->at_put(j + 1, m1);
 982         sorted = false;
 983       }
 984     }
 985     if (sorted) break;
 986     sorted = true;
 987   }
 988 #ifdef ASSERT
 989   uintptr_t prev = 0;
 990   for (int i = 0; i < methods->length(); ++i) {
 991     Method* mh = methods->at(i);
 992     uintptr_t nv = (uintptr_t)mh->name();
 993     assert(nv >= prev, "Incorrect overpass method ordering");
 994     prev = nv;
 995   }
 996 #endif
 997 }
 998 
 999 static void merge_in_new_methods(InstanceKlass* klass,
1000     GrowableArray<Method*>* new_methods, TRAPS) {
1001 
1002   enum { ANNOTATIONS, PARAMETERS, DEFAULTS, NUM_ARRAYS };
1003 
1004   Array<Method*>* original_methods = klass->methods();
1005   Array<int>* original_ordering = klass->method_ordering();
1006   Array<int>* merged_ordering = Universe::the_empty_int_array();
1007 
1008   int new_size = klass->methods()->length() + new_methods->length();
1009 
1010   Array<Method*>* merged_methods = MetadataFactory::new_array<Method*>(
1011       klass->class_loader_data(), new_size, NULL, CHECK);
1012 
1013   // original_ordering might be empty if this class has no methods of its own
1014   if (JvmtiExport::can_maintain_original_method_order() || DumpSharedSpaces) {
1015     merged_ordering = MetadataFactory::new_array<int>(
1016         klass->class_loader_data(), new_size, CHECK);
1017   }
1018   int method_order_index = klass->methods()->length();
1019 
1020   sort_methods(new_methods);
1021 
1022   // Perform grand merge of existing methods and new methods
1023   int orig_idx = 0;
1024   int new_idx = 0;
1025 
1026   for (int i = 0; i < new_size; ++i) {
1027     Method* orig_method = NULL;
1028     Method* new_method = NULL;
1029     if (orig_idx < original_methods->length()) {
1030       orig_method = original_methods->at(orig_idx);
1031     }
1032     if (new_idx < new_methods->length()) {
1033       new_method = new_methods->at(new_idx);
1034     }
1035 
1036     if (orig_method != NULL &&
1037         (new_method == NULL || orig_method->name() < new_method->name())) {
1038       merged_methods->at_put(i, orig_method);
1039       original_methods->at_put(orig_idx, NULL);
1040       if (merged_ordering->length() > 0) {
1041         assert(original_ordering != NULL && original_ordering->length() > 0,
1042                "should have original order information for this method");
1043         merged_ordering->at_put(i, original_ordering->at(orig_idx));
1044       }
1045       ++orig_idx;
1046     } else {
1047       merged_methods->at_put(i, new_method);
1048       if (merged_ordering->length() > 0) {
1049         merged_ordering->at_put(i, method_order_index++);
1050       }
1051       ++new_idx;
1052     }
1053     // update idnum for new location
1054     merged_methods->at(i)->set_method_idnum(i);
1055     merged_methods->at(i)->set_orig_method_idnum(i);
1056   }
1057 
1058   // Verify correct order
1059 #ifdef ASSERT
1060   uintptr_t prev = 0;
1061   for (int i = 0; i < merged_methods->length(); ++i) {
1062     Method* mo = merged_methods->at(i);
1063     uintptr_t nv = (uintptr_t)mo->name();
1064     assert(nv >= prev, "Incorrect method ordering");
1065     prev = nv;
1066   }
1067 #endif
1068 
1069   // Replace klass methods with new merged lists
1070   klass->set_methods(merged_methods);
1071   klass->set_initial_method_idnum(new_size);
1072   klass->set_method_ordering(merged_ordering);
1073 
1074   // Free metadata
1075   ClassLoaderData* cld = klass->class_loader_data();
1076   if (original_methods->length() > 0) {
1077     MetadataFactory::free_array(cld, original_methods);
1078   }
1079   if (original_ordering != NULL && original_ordering->length() > 0) {
1080     MetadataFactory::free_array(cld, original_ordering);
1081   }
1082 }