libjava/link.cc

   1 // link.cc - Code for linking and resolving classes and pool entries.
   2
   3 /* Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation
   4
   5    This file is part of libgcj.
   6
   7 This software is copyrighted work licensed under the terms of the
   8 Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
   9 details.  */
  10
  11 /* Author: Kresten Krab Thorup <krab@gnu.org>  */
  12
  13 #include <config.h>
  14 #include <platform.h>
  15
  16 #include <stdio.h>
  17
  18 #ifdef USE_LIBFFI
  19 #include <ffi.h>
  20 #endif
  21
  22 #include <java-interp.h>
  23
  24 // Set GC_DEBUG before including gc.h!
  25 #ifdef LIBGCJ_GC_DEBUG
  26 # define GC_DEBUG
  27 #endif
  28 #include <gc.h>
  29
  30 #include <jvm.h>
  31 #include <gcj/cni.h>
  32 #include <string.h>
  33 #include <limits.h>
  34 #include <java-cpool.h>
  35 #include <execution.h>
  36 #include <java/lang/Class.h>
  37 #include <java/lang/String.h>
  38 #include <java/lang/StringBuffer.h>
  39 #include <java/lang/Thread.h>
  40 #include <java/lang/InternalError.h>
  41 #include <java/lang/VirtualMachineError.h>
  42 #include <java/lang/VerifyError.h>
  43 #include <java/lang/NoSuchFieldError.h>
  44 #include <java/lang/NoSuchMethodError.h>
  45 #include <java/lang/ClassFormatError.h>
  46 #include <java/lang/IllegalAccessError.h>
  47 #include <java/lang/InternalError.h>
  48 #include <java/lang/AbstractMethodError.h>
  49 #include <java/lang/NoClassDefFoundError.h>
  50 #include <java/lang/IncompatibleClassChangeError.h>
  51 #include <java/lang/VerifyError.h>
  52 #include <java/lang/VMClassLoader.h>
  53 #include <java/lang/reflect/Modifier.h>
  54 #include <java/security/CodeSource.h>
  55
  56 using namespace gcj;
  57
  58 template<typename T>
  59 struct aligner
  60 {
  61   char c;
  62   T field;
  63 };
  64
  65 #define ALIGNOF(TYPE) (offsetof (aligner<TYPE>, field))
  66
  67 // This returns the alignment of a type as it would appear in a
  68 // structure.  This can be different from the alignment of the type
  69 // itself.  For instance on x86 double is 8-aligned but struct{double}
  70 // is 4-aligned.
  71 int
  72 _Jv_Linker::get_alignment_from_class (jclass klass)
  73 {
  74   if (klass == JvPrimClass (byte))
  75     return ALIGNOF (jbyte);
  76   else if (klass == JvPrimClass (short))
  77     return ALIGNOF (jshort);
  78   else if (klass == JvPrimClass (int))
  79     return ALIGNOF (jint);
  80   else if (klass == JvPrimClass (long))
  81     return ALIGNOF (jlong);
  82   else if (klass == JvPrimClass (boolean))
  83     return ALIGNOF (jboolean);
  84   else if (klass == JvPrimClass (char))
  85     return ALIGNOF (jchar);
  86   else if (klass == JvPrimClass (float))
  87     return ALIGNOF (jfloat);
  88   else if (klass == JvPrimClass (double))
  89     return ALIGNOF (jdouble);
  90   else
  91     return ALIGNOF (jobject);
  92 }
  93
  94 void
  95 _Jv_Linker::resolve_field (_Jv_Field *field, java::lang::ClassLoader *loader)
  96 {
  97   if (! field->isResolved ())
  98     {
  99       _Jv_Utf8Const *sig = (_Jv_Utf8Const *) field->type;
 100       jclass type = _Jv_FindClassFromSignature (sig->chars(), loader);
 101       if (type == NULL)
 102         throw new java::lang::NoClassDefFoundError(field->name->toString());
 103       field->type = type;
 104       field->flags &= ~_Jv_FIELD_UNRESOLVED_FLAG;
 105     }
 106 }
 107
 108 // A helper for find_field that knows how to recursively search
 109 // superclasses and interfaces.
 110 _Jv_Field *
 111 _Jv_Linker::find_field_helper (jclass search, _Jv_Utf8Const *name,
 112                                _Jv_Utf8Const *type_name, jclass type,
 113                                jclass *declarer)
 114 {
 115   while (search)
 116     {
 117       // From 5.4.3.2.  First search class itself.
 118       for (int i = 0; i < search->field_count; ++i)
 119         {
 120           _Jv_Field *field = &search->fields[i];
 121           if (! _Jv_equalUtf8Consts (field->name, name))
 122             continue;
 123
 124           // Checks for the odd situation where we were able to retrieve the
 125           // field's class from signature but the resolution of the field itself
 126           // failed which means a different class was resolved.
 127           if (type != NULL)
 128             {
 129               try
 130                 {
 131                   resolve_field (field, search->loader);
 132                 }
 133               catch (java::lang::Throwable *exc)
 134                 {
 135                   java::lang::LinkageError *le = new java::lang::LinkageError
 136                     (JvNewStringLatin1
 137                       ("field type mismatch with different loaders"));
 138
 139                   le->initCause(exc);
 140
 141                   throw le;
 142                 }
 143             }
 144
 145           // Note that we compare type names and not types.  This is
 146           // bizarre, but we do it because we want to find a field
 147           // (and terminate the search) if it has the correct
 148           // descriptor -- but then later reject it if the class
 149           // loader check results in different classes.  We can't just
 150           // pass in the descriptor and check that way, because when
 151           // the field is already resolved there is no easy way to
 152           // find its descriptor again.
 153           if ((field->isResolved ()
 154                ? _Jv_equalUtf8Classnames (type_name, field->type->name)
 155                : _Jv_equalUtf8Classnames (type_name,
 156                                           (_Jv_Utf8Const *) field->type)))
 157             {
 158               *declarer = search;
 159               return field;
 160             }
 161         }
 162
 163       // Next search direct interfaces.
 164       for (int i = 0; i < search->interface_count; ++i)
 165         {
 166           _Jv_Field *result = find_field_helper (search->interfaces[i], name,
 167                                                  type_name, type, declarer);
 168           if (result)
 169             return result;
 170         }
 171
 172       // Now search superclass.
 173       search = search->superclass;
 174     }
 175
 176   return NULL;
 177 }
 178
 179 bool
 180 _Jv_Linker::has_field_p (jclass search, _Jv_Utf8Const *field_name)
 181 {
 182   for (int i = 0; i < search->field_count; ++i)
 183     {
 184       _Jv_Field *field = &search->fields[i];
 185       if (_Jv_equalUtf8Consts (field->name, field_name))
 186         return true;
 187     }
 188   return false;
 189 }
 190
 191 // Find a field.
 192 // KLASS is the class that is requesting the field.
 193 // OWNER is the class in which the field should be found.
 194 // FIELD_TYPE_NAME is the type descriptor for the field.
 195 // Fill FOUND_CLASS with the address of the class in which the field
 196 // is actually declared.
 197 // This function does the class loader type checks, and
 198 // also access checks.  Returns the field, or throws an
 199 // exception on error.
 200 _Jv_Field *
 201 _Jv_Linker::find_field (jclass klass, jclass owner,
 202                         jclass *found_class,
 203                         _Jv_Utf8Const *field_name,
 204                         _Jv_Utf8Const *field_type_name)
 205 {
 206   // FIXME: this allocates a _Jv_Utf8Const each time.  We should make
 207   // it cheaper.
 208   // Note: This call will resolve the primitive type names ("Z", "B", ...) to
 209   // their Java counterparts ("boolean", "byte", ...) if accessed via
 210   // field_type->name later.  Using these variants of the type name is in turn
 211   // important for the find_field_helper function.  However if the class
 212   // resolution failed then we can only use the already given type name.
 213   jclass field_type
 214     = _Jv_FindClassFromSignatureNoException (field_type_name->chars(),
 215                                              klass->loader);
 216
 217   _Jv_Field *the_field
 218     = find_field_helper (owner, field_name,
 219                          (field_type
 220                            ? field_type->name :
 221                              field_type_name ),
 222                            field_type, found_class);
 223
 224   if (the_field == 0)
 225     {
 226       java::lang::StringBuffer *sb = new java::lang::StringBuffer();
 227       sb->append(JvNewStringLatin1("field "));
 228       sb->append(owner->getName());
 229       sb->append(JvNewStringLatin1("."));
 230       sb->append(_Jv_NewStringUTF(field_name->chars()));
 231       sb->append(JvNewStringLatin1(" was not found."));
 232       throw new java::lang::NoSuchFieldError (sb->toString());
 233     }
 234
 235   // Accept it when the field's class could not be resolved.
 236   if (field_type == NULL)
 237     // Silently ignore that we were not able to retrieve the type to make it
 238     // possible to run code which does not access this field.
 239     return the_field;
 240
 241   if (_Jv_CheckAccess (klass, *found_class, the_field->flags))
 242     {
 243       // Note that the field returned by find_field_helper is always
 244       // resolved.  There's no point checking class loaders here,
 245       // since we already did the work to look up all the types.
 246       // FIXME: being lazy here would be nice.
 247       if (the_field->type != field_type)
 248         throw new java::lang::LinkageError
 249           (JvNewStringLatin1
 250            ("field type mismatch with different loaders"));
 251     }
 252   else
 253     {
 254       java::lang::StringBuffer *sb
 255         = new java::lang::StringBuffer ();
 256       sb->append(klass->getName());
 257       sb->append(JvNewStringLatin1(": "));
 258       sb->append((*found_class)->getName());
 259       sb->append(JvNewStringLatin1("."));
 260       sb->append(_Jv_NewStringUtf8Const (field_name));
 261       throw new java::lang::IllegalAccessError(sb->toString());
 262     }
 263
 264   return the_field;
 265 }
 266
 267 _Jv_Method *
 268 _Jv_Linker::resolve_method_entry (jclass klass, jclass &found_class,
 269                                   int class_index, int name_and_type_index,
 270                                   bool init, bool is_iface)
 271 {
 272   _Jv_Constants *pool = &klass->constants;
 273   jclass owner = resolve_pool_entry (klass, class_index).clazz;
 274
 275   if (init && owner != klass)
 276     _Jv_InitClass (owner);
 277
 278   _Jv_ushort name_index, type_index;
 279   _Jv_loadIndexes (&pool->data[name_and_type_index],
 280                    name_index,
 281                    type_index);
 282
 283   _Jv_Utf8Const *method_name = pool->data[name_index].utf8;
 284   _Jv_Utf8Const *method_signature = pool->data[type_index].utf8;
 285
 286   _Jv_Method *the_method = 0;
 287   found_class = 0;
 288
 289   // We're going to cache a pointer to the _Jv_Method object
 290   // when we find it.  So, to ensure this doesn't get moved from
 291   // beneath us, we first put all the needed Miranda methods
 292   // into the target class.
 293   wait_for_state (klass, JV_STATE_LOADED);
 294
 295   // First search the class itself.
 296   the_method = search_method_in_class (owner, klass,
 297                                        method_name, method_signature);
 298
 299   if (the_method != 0)
 300     {
 301       found_class = owner;
 302       goto end_of_method_search;
 303     }
 304
 305   // If we are resolving an interface method, search the
 306   // interface's superinterfaces (A superinterface is not an
 307   // interface's superclass - a superinterface is implemented by
 308   // the interface).
 309   if (is_iface)
 310     {
 311       _Jv_ifaces ifaces;
 312       ifaces.count = 0;
 313       ifaces.len = 4;
 314       ifaces.list = (jclass *) _Jv_Malloc (ifaces.len
 315                                            * sizeof (jclass *));
 316
 317       get_interfaces (owner, &ifaces);
 318
 319       for (int i = 0; i < ifaces.count; i++)
 320         {
 321           jclass cls = ifaces.list[i];
 322           the_method = search_method_in_class (cls, klass, method_name,
 323                                                method_signature);
 324           if (the_method != 0)
 325             {
 326               found_class = cls;
 327               break;
 328             }
 329         }
 330
 331       _Jv_Free (ifaces.list);
 332
 333       if (the_method != 0)
 334         goto end_of_method_search;
 335     }
 336
 337   // Finally, search superclasses.
 338   the_method = (search_method_in_superclasses
 339                 (owner->getSuperclass (), klass, method_name,
 340                  method_signature, &found_class));
 341
 342
 343  end_of_method_search:
 344
 345   // FIXME: if (cls->loader != klass->loader), then we
 346   // must actually check that the types of arguments
 347   // correspond.  That is, for each argument type, and
 348   // the return type, doing _Jv_FindClassFromSignature
 349   // with either loader should produce the same result,
 350   // i.e., exactly the same jclass object. JVMS 5.4.3.3
 351
 352   if (the_method == 0)
 353     {
 354       java::lang::StringBuffer *sb = new java::lang::StringBuffer();
 355       sb->append(JvNewStringLatin1("method "));
 356       sb->append(owner->getName());
 357       sb->append(JvNewStringLatin1("."));
 358       sb->append(_Jv_NewStringUTF(method_name->chars()));
 359       sb->append(JvNewStringLatin1(" with signature "));
 360       sb->append(_Jv_NewStringUTF(method_signature->chars()));
 361       sb->append(JvNewStringLatin1(" was not found."));
 362       throw new java::lang::NoSuchMethodError (sb->toString());
 363     }
 364
 365   return the_method;
 366 }
 367
 368 _Jv_word
 369 _Jv_Linker::resolve_pool_entry (jclass klass, int index, bool lazy)
 370 {
 371   using namespace java::lang::reflect;
 372
 373   if (GC_base (klass) && klass->constants.data
 374       && ! GC_base (klass->constants.data))
 375     {
 376       jsize count = klass->constants.size;
 377       if (count)
 378         {
 379           _Jv_word* constants
 380             = (_Jv_word*) _Jv_AllocRawObj (count * sizeof (_Jv_word));
 381           memcpy ((void*)constants,
 382                   (void*)klass->constants.data,
 383                   count * sizeof (_Jv_word));
 384           klass->constants.data = constants;
 385         }
 386     }
 387
 388   _Jv_Constants *pool = &klass->constants;
 389
 390   if ((pool->tags[index] & JV_CONSTANT_ResolvedFlag) != 0)
 391     return pool->data[index];
 392
 393   switch (pool->tags[index] & ~JV_CONSTANT_LazyFlag)
 394     {
 395     case JV_CONSTANT_Class:
 396       {
 397         _Jv_Utf8Const *name = pool->data[index].utf8;
 398
 399         jclass found;
 400         if (name->first() == '[')
 401           found = _Jv_FindClassFromSignatureNoException (name->chars(),
 402                                                          klass->loader);
 403         else
 404           found = _Jv_FindClassNoException (name, klass->loader);
 405
 406         // If the class could not be loaded a phantom class is created. Any
 407         // function that deals with such a class but cannot do something useful
 408         // with it should just throw a NoClassDefFoundError with the class'
 409         // name.
 410         if (! found)
 411           if (lazy)
 412             {
 413               found = _Jv_NewClass(name, NULL, NULL);
 414               found->state = JV_STATE_PHANTOM;
 415               pool->tags[index] |= JV_CONSTANT_ResolvedFlag;
 416               pool->data[index].clazz = found;
 417               break;
 418             }
 419           else
 420             throw new java::lang::NoClassDefFoundError (name->toString());
 421
 422         // Check accessibility, but first strip array types as
 423         // _Jv_ClassNameSamePackage can't handle arrays.
 424         jclass check;
 425         for (check = found;
 426              check && check->isArray();
 427              check = check->getComponentType())
 428           ;
 429         if ((found->accflags & Modifier::PUBLIC) == Modifier::PUBLIC
 430             || (_Jv_ClassNameSamePackage (check->name,
 431                                           klass->name)))
 432           {
 433             pool->data[index].clazz = found;
 434             pool->tags[index] |= JV_CONSTANT_ResolvedFlag;
 435           }
 436         else
 437           {
 438             java::lang::StringBuffer *sb = new java::lang::StringBuffer ();
 439             sb->append(klass->getName());
 440             sb->append(JvNewStringLatin1(" can't access class "));
 441             sb->append(found->getName());
 442             throw new java::lang::IllegalAccessError(sb->toString());
 443           }
 444       }
 445       break;
 446
 447     case JV_CONSTANT_String:
 448       {
 449         jstring str;
 450         str = _Jv_NewStringUtf8Const (pool->data[index].utf8);
 451         pool->data[index].o = str;
 452         pool->tags[index] |= JV_CONSTANT_ResolvedFlag;
 453       }
 454       break;
 455
 456     case JV_CONSTANT_Fieldref:
 457       {
 458         _Jv_ushort class_index, name_and_type_index;
 459         _Jv_loadIndexes (&pool->data[index],
 460                          class_index,
 461                          name_and_type_index);
 462         jclass owner = (resolve_pool_entry (klass, class_index, true)).clazz;
 463
 464         // If a phantom class was resolved our field reference is
 465         // unusable because of the missing class.
 466         if (owner->state == JV_STATE_PHANTOM)
 467           throw new java::lang::NoClassDefFoundError(owner->getName());
 468
 469         // We don't initialize 'owner', but we do make sure that its
 470         // fields exist.
 471         wait_for_state (owner, JV_STATE_PREPARED);
 472
 473         _Jv_ushort name_index, type_index;
 474         _Jv_loadIndexes (&pool->data[name_and_type_index],
 475                          name_index,
 476                          type_index);
 477
 478         _Jv_Utf8Const *field_name = pool->data[name_index].utf8;
 479         _Jv_Utf8Const *field_type_name = pool->data[type_index].utf8;
 480
 481         jclass found_class = 0;
 482         _Jv_Field *the_field = find_field (klass, owner,
 483                                            &found_class,
 484                                            field_name,
 485                                            field_type_name);
 486         // Initialize the field's declaring class, not its qualifying
 487         // class.
 488         _Jv_InitClass (found_class);
 489         pool->data[index].field = the_field;
 490         pool->tags[index] |= JV_CONSTANT_ResolvedFlag;
 491       }
 492       break;
 493
 494     case JV_CONSTANT_Methodref:
 495     case JV_CONSTANT_InterfaceMethodref:
 496       {
 497         _Jv_ushort class_index, name_and_type_index;
 498         _Jv_loadIndexes (&pool->data[index],
 499                          class_index,
 500                          name_and_type_index);
 501
 502         _Jv_Method *the_method;
 503         jclass found_class;
 504         the_method = resolve_method_entry (klass, found_class,
 505                                            class_index, name_and_type_index,
 506                                            true,
 507                                            pool->tags[index] == JV_CONSTANT_InterfaceMethodref);
 508
 509         pool->data[index].rmethod
 510           = klass->engine->resolve_method(the_method,
 511                                           found_class,
 512                                           ((the_method->accflags
 513                                             & Modifier::STATIC) != 0));
 514         pool->tags[index] |= JV_CONSTANT_ResolvedFlag;
 515       }
 516       break;
 517     }
 518   return pool->data[index];
 519 }
 520
 521 // This function is used to lazily locate superclasses and
 522 // superinterfaces.  This must be called with the class lock held.
 523 void
 524 _Jv_Linker::resolve_class_ref (jclass klass, jclass *classref)
 525 {
 526   jclass ret = *classref;
 527
 528   // If superclass looks like a constant pool entry, resolve it now.
 529   if (ret && (uaddr) ret < (uaddr) klass->constants.size)
 530     {
 531       if (klass->state < JV_STATE_LINKED)
 532         {
 533           _Jv_Utf8Const *name = klass->constants.data[(uaddr) *classref].utf8;
 534           ret = _Jv_FindClass (name, klass->loader);
 535           if (! ret)
 536             {
 537               throw new java::lang::NoClassDefFoundError (name->toString());
 538             }
 539         }
 540       else
 541         ret = klass->constants.data[(uaddr) classref].clazz;
 542       *classref = ret;
 543     }
 544 }
 545
 546 // Find a method declared in the cls that is referenced from klass and
 547 // perform access checks if CHECK_PERMS is true.
 548 _Jv_Method *
 549 _Jv_Linker::search_method_in_class (jclass cls, jclass klass,
 550                                     _Jv_Utf8Const *method_name,
 551                                     _Jv_Utf8Const *method_signature,
 552                                     bool check_perms)
 553 {
 554   using namespace java::lang::reflect;
 555
 556   for (int i = 0;  i < cls->method_count;  i++)
 557     {
 558       _Jv_Method *method = &cls->methods[i];
 559       if (   (!_Jv_equalUtf8Consts (method->name,
 560                                     method_name))
 561           || (!_Jv_equalUtf8Consts (method->signature,
 562                                     method_signature)))
 563         continue;
 564
 565       if (!check_perms || _Jv_CheckAccess (klass, cls, method->accflags))
 566         return method;
 567       else
 568         {
 569           java::lang::StringBuffer *sb = new java::lang::StringBuffer();
 570           sb->append(klass->getName());
 571           sb->append(JvNewStringLatin1(": "));
 572           sb->append(cls->getName());
 573           sb->append(JvNewStringLatin1("."));
 574           sb->append(_Jv_NewStringUTF(method_name->chars()));
 575           sb->append(_Jv_NewStringUTF(method_signature->chars()));
 576           throw new java::lang::IllegalAccessError (sb->toString());
 577         }
 578     }
 579   return 0;
 580 }
 581
 582 // Like search_method_in_class, but work our way up the superclass
 583 // chain.
 584 _Jv_Method *
 585 _Jv_Linker::search_method_in_superclasses (jclass cls, jclass klass,
 586                                            _Jv_Utf8Const *method_name,
 587                                            _Jv_Utf8Const *method_signature,
 588                                            jclass *found_class, bool check_perms)
 589 {
 590   _Jv_Method *the_method = NULL;
 591
 592   for ( ; cls != 0; cls = cls->getSuperclass ())
 593     {
 594       the_method = search_method_in_class (cls, klass, method_name,
 595                                            method_signature, check_perms);
 596       if (the_method != 0)
 597         {
 598           if (found_class)
 599             *found_class = cls;
 600           break;
 601         }
 602     }
 603
 604   return the_method;
 605 }
 606
 607 #define INITIAL_IOFFSETS_LEN 4
 608 #define INITIAL_IFACES_LEN 4
 609
 610 static _Jv_IDispatchTable null_idt = {SHRT_MAX, 0, {}};
 611
 612 // Generate tables for constant-time assignment testing and interface
 613 // method lookup. This implements the technique described by Per Bothner
 614 // <per@bothner.com> on the java-discuss mailing list on 1999-09-02:
 615 // http://gcc.gnu.org/ml/java/1999-q3/msg00377.html
 616 void
 617 _Jv_Linker::prepare_constant_time_tables (jclass klass)
 618 {
 619   if (klass->isPrimitive () || klass->isInterface ())
 620     return;
 621
 622   // Short-circuit in case we've been called already.
 623   if ((klass->idt != NULL) || klass->depth != 0)
 624     return;
 625
 626   // Calculate the class depth and ancestor table. The depth of a class
 627   // is how many "extends" it is removed from Object. Thus the depth of
 628   // java.lang.Object is 0, but the depth of java.io.FilterOutputStream
 629   // is 2. Depth is defined for all regular and array classes, but not
 630   // interfaces or primitive types.
 631
 632   jclass klass0 = klass;
 633   jboolean has_interfaces = 0;
 634   while (klass0 != &java::lang::Object::class$)
 635     {
 636       has_interfaces += klass0->interface_count;
 637       klass0 = klass0->superclass;
 638       klass->depth++;
 639     }
 640
 641   // We do class member testing in constant time by using a small table
 642   // of all the ancestor classes within each class. The first element is
 643   // a pointer to the current class, and the rest are pointers to the
 644   // classes ancestors, ordered from the current class down by decreasing
 645   // depth. We do not include java.lang.Object in the table of ancestors,
 646   // since it is redundant.  Note that the classes pointed to by
 647   // 'ancestors' will always be reachable by other paths.
 648
 649   klass->ancestors = (jclass *) _Jv_AllocBytes (klass->depth
 650                                                 * sizeof (jclass));
 651   klass0 = klass;
 652   for (int index = 0; index < klass->depth; index++)
 653     {
 654       klass->ancestors[index] = klass0;
 655       klass0 = klass0->superclass;
 656     }
 657
 658   if ((klass->accflags & java::lang::reflect::Modifier::ABSTRACT) != 0)
 659     return;
 660
 661   // Optimization: If class implements no interfaces, use a common
 662   // predefined interface table.
 663   if (!has_interfaces)
 664     {
 665       klass->idt = &null_idt;
 666       return;
 667     }
 668
 669   _Jv_ifaces ifaces;
 670   ifaces.count = 0;
 671   ifaces.len = INITIAL_IFACES_LEN;
 672   ifaces.list = (jclass *) _Jv_Malloc (ifaces.len * sizeof (jclass *));
 673
 674   int itable_size = get_interfaces (klass, &ifaces);
 675
 676   if (ifaces.count > 0)
 677     {
 678       // The classes pointed to by the itable will always be reachable
 679       // via other paths.
 680       int idt_bytes = sizeof (_Jv_IDispatchTable) + (itable_size
 681                                                      * sizeof (void *));
 682       klass->idt = (_Jv_IDispatchTable *) _Jv_AllocBytes (idt_bytes);
 683       klass->idt->itable_length = itable_size;
 684
 685       jshort *itable_offsets =
 686         (jshort *) _Jv_Malloc (ifaces.count * sizeof (jshort));
 687
 688       generate_itable (klass, &ifaces, itable_offsets);
 689
 690       jshort cls_iindex = find_iindex (ifaces.list, itable_offsets,
 691                                        ifaces.count);
 692
 693       for (int i = 0; i < ifaces.count; i++)
 694         {
 695           ifaces.list[i]->ioffsets[cls_iindex] = itable_offsets[i];
 696         }
 697
 698       klass->idt->iindex = cls_iindex;
 699
 700       _Jv_Free (ifaces.list);
 701       _Jv_Free (itable_offsets);
 702     }
 703   else
 704     {
 705       klass->idt->iindex = SHRT_MAX;
 706     }
 707 }
 708
 709 // Return index of item in list, or -1 if item is not present.
 710 inline jshort
 711 _Jv_Linker::indexof (void *item, void **list, jshort list_len)
 712 {
 713   for (int i=0; i < list_len; i++)
 714     {
 715       if (list[i] == item)
 716         return i;
 717     }
 718   return -1;
 719 }
 720
 721 // Find all unique interfaces directly or indirectly implemented by klass.
 722 // Returns the size of the interface dispatch table (itable) for klass, which
 723 // is the number of unique interfaces plus the total number of methods that
 724 // those interfaces declare. May extend ifaces if required.
 725 jshort
 726 _Jv_Linker::get_interfaces (jclass klass, _Jv_ifaces *ifaces)
 727 {
 728   jshort result = 0;
 729
 730   for (int i = 0; i < klass->interface_count; i++)
 731     {
 732       jclass iface = klass->interfaces[i];
 733
 734       /* Make sure interface is linked.  */
 735       wait_for_state(iface, JV_STATE_LINKED);
 736
 737       if (indexof (iface, (void **) ifaces->list, ifaces->count) == -1)
 738         {
 739           if (ifaces->count + 1 >= ifaces->len)
 740             {
 741               /* Resize ifaces list */
 742               ifaces->len = ifaces->len * 2;
 743               ifaces->list
 744                 = (jclass *) _Jv_Realloc (ifaces->list,
 745                                           ifaces->len * sizeof(jclass));
 746             }
 747           ifaces->list[ifaces->count] = iface;
 748           ifaces->count++;
 749
 750           result += get_interfaces (klass->interfaces[i], ifaces);
 751         }
 752     }
 753
 754   if (klass->isInterface())
 755     {
 756       // We want to add 1 plus the number of interface methods here.
 757       // But, we take special care to skip <clinit>.
 758       ++result;
 759       for (int i = 0; i < klass->method_count; ++i)
 760         {
 761           if (klass->methods[i].name->first() != '<')
 762             ++result;
 763         }
 764     }
 765   else if (klass->superclass)
 766     result += get_interfaces (klass->superclass, ifaces);
 767   return result;
 768 }
 769
 770 // Fill out itable in klass, resolving method declarations in each ifaces.
 771 // itable_offsets is filled out with the position of each iface in itable,
 772 // such that itable[itable_offsets[n]] == ifaces.list[n].
 773 void
 774 _Jv_Linker::generate_itable (jclass klass, _Jv_ifaces *ifaces,
 775                                jshort *itable_offsets)
 776 {
 777   void **itable = klass->idt->itable;
 778   jshort itable_pos = 0;
 779
 780   for (int i = 0; i < ifaces->count; i++)
 781     {
 782       jclass iface = ifaces->list[i];
 783       itable_offsets[i] = itable_pos;
 784       itable_pos = append_partial_itable (klass, iface, itable, itable_pos);
 785
 786       /* Create ioffsets table for iface */
 787       if (iface->ioffsets == NULL)
 788         {
 789           // The first element of ioffsets is its length (itself included).
 790           jshort *ioffsets = (jshort *) _Jv_AllocBytes (INITIAL_IOFFSETS_LEN
 791                                                         * sizeof (jshort));
 792           ioffsets[0] = INITIAL_IOFFSETS_LEN;
 793           for (int i = 1; i < INITIAL_IOFFSETS_LEN; i++)
 794             ioffsets[i] = -1;
 795
 796           iface->ioffsets = ioffsets;
 797         }
 798     }
 799 }
 800
 801 // Format method name for use in error messages.
 802 jstring
 803 _Jv_GetMethodString (jclass klass, _Jv_Method *meth,
 804                      jclass derived)
 805 {
 806   using namespace java::lang;
 807   StringBuffer *buf = new StringBuffer (klass->name->toString());
 808   buf->append (jchar ('.'));
 809   buf->append (meth->name->toString());
 810   buf->append ((jchar) ' ');
 811   buf->append (meth->signature->toString());
 812   if (derived)
 813     {
 814       buf->append(JvNewStringLatin1(" in "));
 815       buf->append(derived->name->toString());
 816     }
 817   return buf->toString();
 818 }
 819
 820 void
 821 _Jv_ThrowNoSuchMethodError ()
 822 {
 823   throw new java::lang::NoSuchMethodError;
 824 }
 825
 826 #if defined USE_LIBFFI && FFI_CLOSURES
 827 // A function whose invocation is prepared using libffi. It gets called
 828 // whenever a static method of a missing class is invoked. The data argument
 829 // holds a reference to a String denoting the missing class.
 830 // The prepared function call is stored in a class' atable.
 831 void
 832 _Jv_ThrowNoClassDefFoundErrorTrampoline(ffi_cif *,
 833                                         void *,
 834                                         void **,
 835                                         void *data)
 836 {
 837   throw new java::lang::NoClassDefFoundError(
 838     _Jv_NewStringUtf8Const((_Jv_Utf8Const *) data));
 839 }
 840 #else
 841 // A variant of the NoClassDefFoundError throwing method that can
 842 // be used without libffi.
 843 void
 844 _Jv_ThrowNoClassDefFoundError()
 845 {
 846   throw new java::lang::NoClassDefFoundError();
 847 }
 848 #endif
 849
 850 // Throw a NoSuchFieldError.  Called by compiler-generated code when
 851 // an otable entry is zero.  OTABLE_INDEX is the index in the caller's
 852 // otable that refers to the missing field.  This index may be used to
 853 // print diagnostic information about the field.
 854 void
 855 _Jv_ThrowNoSuchFieldError (int /* otable_index */)
 856 {
 857   throw new java::lang::NoSuchFieldError;
 858 }
 859
 860 // This is put in empty vtable slots.
 861 void
 862 _Jv_ThrowAbstractMethodError ()
 863 {
 864   throw new java::lang::AbstractMethodError();
 865 }
 866
 867 // Each superinterface of a class (i.e. each interface that the class
 868 // directly or indirectly implements) has a corresponding "Partial
 869 // Interface Dispatch Table" whose size is (number of methods + 1) words.
 870 // The first word is a pointer to the interface (i.e. the java.lang.Class
 871 // instance for that interface).  The remaining words are pointers to the
 872 // actual methods that implement the methods declared in the interface,
 873 // in order of declaration.
 874 //
 875 // Append partial interface dispatch table for "iface" to "itable", at
 876 // position itable_pos.
 877 // Returns the offset at which the next partial ITable should be appended.
 878 jshort
 879 _Jv_Linker::append_partial_itable (jclass klass, jclass iface,
 880                                    void **itable, jshort pos)
 881 {
 882   using namespace java::lang::reflect;
 883
 884   itable[pos++] = (void *) iface;
 885   _Jv_Method *meth;
 886
 887   for (int j=0; j < iface->method_count; j++)
 888     {
 889       // Skip '<clinit>' here.
 890       if (iface->methods[j].name->first() == '<')
 891         continue;
 892
 893       meth = NULL;
 894       for (jclass cl = klass; cl; cl = cl->getSuperclass())
 895         {
 896           meth = _Jv_GetMethodLocal (cl, iface->methods[j].name,
 897                                      iface->methods[j].signature);
 898
 899           if (meth)
 900             break;
 901         }
 902
 903       if (meth)
 904         {
 905           if ((meth->accflags & Modifier::STATIC) != 0)
 906             throw new java::lang::IncompatibleClassChangeError
 907               (_Jv_GetMethodString (klass, meth));
 908           if ((meth->accflags & Modifier::PUBLIC) == 0)
 909             throw new java::lang::IllegalAccessError
 910               (_Jv_GetMethodString (klass, meth));
 911
 912           if ((meth->accflags & Modifier::ABSTRACT) != 0)
 913             itable[pos] = (void *) &_Jv_ThrowAbstractMethodError;
 914           else
 915             itable[pos] = meth->ncode;
 916         }
 917       else
 918         {
 919           // The method doesn't exist in klass. Binary compatibility rules
 920           // permit this, so we delay the error until runtime using a pointer
 921           // to a method which throws an exception.
 922           itable[pos] = (void *) _Jv_ThrowNoSuchMethodError;
 923         }
 924       pos++;
 925     }
 926
 927   return pos;
 928 }
 929
 930 static _Jv_Mutex_t iindex_mutex;
 931 static bool iindex_mutex_initialized = false;
 932
 933 // We need to find the correct offset in the Class Interface Dispatch
 934 // Table for a given interface. Once we have that, invoking an interface
 935 // method just requires combining the Method's index in the interface
 936 // (known at compile time) to get the correct method.  Doing a type test
 937 // (cast or instanceof) is the same problem: Once we have a possible Partial
 938 // Interface Dispatch Table, we just compare the first element to see if it
 939 // matches the desired interface. So how can we find the correct offset?
 940 // Our solution is to keep a vector of candiate offsets in each interface
 941 // (ioffsets), and in each class we have an index (idt->iindex) used to
 942 // select the correct offset from ioffsets.
 943 //
 944 // Calculate and return iindex for a new class.
 945 // ifaces is a vector of num interfaces that the class implements.
 946 // offsets[j] is the offset in the interface dispatch table for the
 947 // interface corresponding to ifaces[j].
 948 // May extend the interface ioffsets if required.
 949 jshort
 950 _Jv_Linker::find_iindex (jclass *ifaces, jshort *offsets, jshort num)
 951 {
 952   int i;
 953   int j;
 954
 955   // Acquire a global lock to prevent itable corruption in case of multiple
 956   // classes that implement an intersecting set of interfaces being linked
 957   // simultaneously. We can assume that the mutex will be initialized
 958   // single-threaded.
 959   if (! iindex_mutex_initialized)
 960     {
 961       _Jv_MutexInit (&iindex_mutex);
 962       iindex_mutex_initialized = true;
 963     }
 964
 965   _Jv_MutexLock (&iindex_mutex);
 966
 967   for (i=1;; i++)  /* each potential position in ioffsets */
 968     {
 969       for (j=0;; j++)  /* each iface */
 970         {
 971           if (j >= num)
 972             goto found;
 973           if (i >= ifaces[j]->ioffsets[0])
 974             continue;
 975           int ioffset = ifaces[j]->ioffsets[i];
 976           /* We can potentially share this position with another class. */
 977           if (ioffset >= 0 && ioffset != offsets[j])
 978             break; /* Nope. Try next i. */
 979         }
 980     }
 981   found:
 982   for (j = 0; j < num; j++)
 983     {
 984       int len = ifaces[j]->ioffsets[0];
 985       if (i >= len)
 986         {
 987           // Resize ioffsets.
 988           int newlen = 2 * len;
 989           if (i >= newlen)
 990             newlen = i + 3;
 991
 992           jshort *old_ioffsets = ifaces[j]->ioffsets;
 993           jshort *new_ioffsets = (jshort *) _Jv_AllocBytes (newlen
 994                                                             * sizeof(jshort));
 995           memcpy (&new_ioffsets[1], &old_ioffsets[1],
 996                   (len - 1) * sizeof (jshort));
 997           new_ioffsets[0] = newlen;
 998
 999           while (len < newlen)
1000             new_ioffsets[len++] = -1;
1001
1002           ifaces[j]->ioffsets = new_ioffsets;
1003         }
1004       ifaces[j]->ioffsets[i] = offsets[j];
1005     }
1006
1007   _Jv_MutexUnlock (&iindex_mutex);
1008
1009   return i;
1010 }
1011
1012 #if defined USE_LIBFFI && FFI_CLOSURES
1013 // We use a structure of this type to store the closure that
1014 // represents a missing method.
1015 struct method_closure
1016 {
1017   // This field must come first, since the address of this field will
1018   // be the same as the address of the overall structure.  This is due
1019   // to disabling interior pointers in the GC.
1020   ffi_closure closure;
1021   ffi_cif cif;
1022   ffi_type *arg_types[1];
1023 };
1024
1025 void *
1026 _Jv_Linker::create_error_method (_Jv_Utf8Const *class_name)
1027 {
1028   method_closure *closure
1029     = (method_closure *) _Jv_AllocBytes(sizeof (method_closure));
1030
1031   closure->arg_types[0] = &ffi_type_void;
1032
1033   // Initializes the cif and the closure.  If that worked the closure
1034   // is returned and can be used as a function pointer in a class'
1035   // atable.
1036   if (   ffi_prep_cif (&closure->cif,
1037                        FFI_DEFAULT_ABI,
1038                        1,
1039                        &ffi_type_void,
1040                        closure->arg_types) == FFI_OK
1041       && ffi_prep_closure (&closure->closure,
1042                            &closure->cif,
1043                            _Jv_ThrowNoClassDefFoundErrorTrampoline,
1044                            class_name) == FFI_OK)
1045     return &closure->closure;
1046   else
1047     {
1048       java::lang::StringBuffer *buffer = new java::lang::StringBuffer();
1049       buffer->append(JvNewStringLatin1("Error setting up FFI closure"
1050                                        " for static method of"
1051                                        " missing class: "));
1052       buffer->append (_Jv_NewStringUtf8Const(class_name));
1053       throw new java::lang::InternalError(buffer->toString());
1054     }
1055 }
1056 #else
1057 void *
1058 _Jv_Linker::create_error_method (_Jv_Utf8Const *)
1059 {
1060   // Codepath for platforms which do not support (or want) libffi.
1061   // You have to accept that it is impossible to provide the name
1062   // of the missing class then.
1063   return (void *) _Jv_ThrowNoClassDefFoundError;
1064 }
1065 #endif // USE_LIBFFI && FFI_CLOSURES
1066
1067 // Functions for indirect dispatch (symbolic virtual binding) support.
1068
1069 // There are three tables, atable otable and itable.  atable is an
1070 // array of addresses, and otable is an array of offsets, and these
1071 // are used for static and virtual members respectively.  itable is an
1072 // array of pairs {address, index} where each address is a pointer to
1073 // an interface.
1074
1075 // {a,o,i}table_syms is an array of _Jv_MethodSymbols.  Each such
1076 // symbol is a tuple of {classname, member name, signature}.
1077
1078 // Set this to true to enable debugging of indirect dispatch tables/linking.
1079 static bool debug_link = false;
1080
1081 // link_symbol_table() scans these two arrays and fills in the
1082 // corresponding atable and otable with the addresses of static
1083 // members and the offsets of virtual members.
1084
1085 // The offset (in bytes) for each resolved method or field is placed
1086 // at the corresponding position in the virtual method offset table
1087 // (klass->otable).
1088
1089 // The same otable and atable may be shared by many classes.
1090
1091 // This must be called while holding the class lock.
1092
1093 void
1094 _Jv_Linker::link_symbol_table (jclass klass)
1095 {
1096   int index = 0;
1097   _Jv_MethodSymbol sym;
1098   if (klass->otable == NULL
1099       || klass->otable->state != 0)
1100     goto atable;
1101
1102   klass->otable->state = 1;
1103
1104   if (debug_link)
1105     fprintf (stderr, "Fixing up otable in %s:\n", klass->name->chars());
1106   for (index = 0;
1107        (sym = klass->otable_syms[index]).class_name != NULL;
1108        ++index)
1109     {
1110       jclass target_class = _Jv_FindClass (sym.class_name, klass->loader);
1111       _Jv_Method *meth = NULL;
1112
1113       _Jv_Utf8Const *signature = sym.signature;
1114       uaddr special;
1115       maybe_adjust_signature (signature, special);
1116
1117       if (target_class == NULL)
1118         throw new java::lang::NoClassDefFoundError
1119           (_Jv_NewStringUTF (sym.class_name->chars()));
1120
1121       // We're looking for a field or a method, and we can tell
1122       // which is needed by looking at the signature.
1123       if (signature->first() == '(' && signature->len() >= 2)
1124         {
1125           // Looks like someone is trying to invoke an interface method
1126           if (target_class->isInterface())
1127             {
1128               using namespace java::lang;
1129               StringBuffer *sb = new StringBuffer();
1130               sb->append(JvNewStringLatin1("found interface "));
1131               sb->append(target_class->getName());
1132               sb->append(JvNewStringLatin1(" when searching for a class"));
1133               throw new VerifyError(sb->toString());
1134             }
1135
1136           // If the target class does not have a vtable_method_count yet,
1137           // then we can't tell the offsets for its methods, so we must lay
1138           // it out now.
1139           wait_for_state(target_class, JV_STATE_PREPARED);
1140
1141           try
1142             {
1143               meth = (search_method_in_superclasses
1144                       (target_class, klass, sym.name, signature,
1145                        NULL, special == 0));
1146             }
1147           catch (::java::lang::IllegalAccessError *e)
1148             {
1149             }
1150
1151           // Every class has a throwNoSuchMethodErrorIndex method that
1152           // it inherits from java.lang.Object.  Find its vtable
1153           // offset.
1154           static int throwNoSuchMethodErrorIndex;
1155           if (throwNoSuchMethodErrorIndex == 0)
1156             {
1157               Utf8Const* name
1158                 = _Jv_makeUtf8Const ("throwNoSuchMethodError",
1159                                      strlen ("throwNoSuchMethodError"));
1160               _Jv_Method* meth
1161                 = _Jv_LookupDeclaredMethod (&java::lang::Object::class$,
1162                                             name, gcj::void_signature);
1163               throwNoSuchMethodErrorIndex
1164                 = _Jv_VTable::idx_to_offset (meth->index);
1165             }
1166
1167           // If we don't find a nonstatic method, insert the
1168           // vtable index of Object.throwNoSuchMethodError().
1169           // This defers the missing method error until an attempt
1170           // is made to execute it.
1171           {
1172             int offset;
1173
1174             if (meth != NULL)
1175               offset = _Jv_VTable::idx_to_offset (meth->index);
1176             else
1177               offset = throwNoSuchMethodErrorIndex;
1178
1179             if (offset == -1)
1180               JvFail ("Bad method index");
1181             JvAssert (meth->index < target_class->vtable_method_count);
1182
1183             klass->otable->offsets[index] = offset;
1184           }
1185
1186           if (debug_link)
1187             fprintf (stderr, "  offsets[%d] = %d (class %s@%p : %s(%s))\n",
1188                      (int)index,
1189                      (int)klass->otable->offsets[index],
1190                      (const char*)target_class->name->chars(),
1191                      target_class,
1192                      (const char*)sym.name->chars(),
1193                      (const char*)signature->chars());
1194           continue;
1195         }
1196
1197       // Try fields.
1198       {
1199         wait_for_state(target_class, JV_STATE_PREPARED);
1200         jclass found_class;
1201         _Jv_Field *the_field = NULL;
1202         try
1203           {
1204             the_field = find_field (klass, target_class, &found_class,
1205                                     sym.name, signature);
1206             if ((the_field->flags & java::lang::reflect::Modifier::STATIC))
1207               throw new java::lang::IncompatibleClassChangeError;
1208             else
1209               klass->otable->offsets[index] = the_field->u.boffset;
1210           }
1211         catch (java::lang::NoSuchFieldError *err)
1212           {
1213             klass->otable->offsets[index] = 0;
1214           }
1215       }
1216     }
1217
1218  atable:
1219   if (klass->atable == NULL || klass->atable->state != 0)
1220     goto itable;
1221
1222   klass->atable->state = 1;
1223
1224   for (index = 0;
1225        (sym = klass->atable_syms[index]).class_name != NULL;
1226        ++index)
1227     {
1228       jclass target_class =
1229         _Jv_FindClassNoException (sym.class_name, klass->loader);
1230
1231       _Jv_Method *meth = NULL;
1232
1233       _Jv_Utf8Const *signature = sym.signature;
1234       uaddr special;
1235       maybe_adjust_signature (signature, special);
1236
1237       // ??? Setting this pointer to null will at least get us a
1238       // NullPointerException
1239       klass->atable->addresses[index] = NULL;
1240
1241       // If the target class is missing we prepare a function call
1242       // that throws a NoClassDefFoundError and store the address of
1243       // that newly prepared method in the atable. The user can run
1244       // code in classes where the missing class is part of the
1245       // execution environment as long as it is never referenced.
1246       if (target_class == NULL)
1247         klass->atable->addresses[index] = create_error_method(sym.class_name);
1248       // We're looking for a static field or a static method, and we
1249       // can tell which is needed by looking at the signature.
1250       else if (signature->first() == '(' && signature->len() >= 2)
1251         {
1252           // If the target class does not have a vtable_method_count yet,
1253           // then we can't tell the offsets for its methods, so we must lay
1254           // it out now.
1255           wait_for_state (target_class, JV_STATE_PREPARED);
1256
1257           // Interface methods cannot have bodies.
1258           if (target_class->isInterface())
1259             {
1260               using namespace java::lang;
1261               StringBuffer *sb = new StringBuffer();
1262               sb->append(JvNewStringLatin1("class "));
1263               sb->append(target_class->getName());
1264               sb->append(JvNewStringLatin1(" is an interface: "
1265                                            "class expected"));
1266               throw new VerifyError(sb->toString());
1267             }
1268
1269           try
1270             {
1271               meth = (search_method_in_superclasses
1272                       (target_class, klass, sym.name, signature,
1273                        NULL, special == 0));
1274             }
1275           catch (::java::lang::IllegalAccessError *e)
1276             {
1277             }
1278
1279           if (meth != NULL)
1280             {
1281               if (meth->ncode) // Maybe abstract?
1282                 {
1283                   klass->atable->addresses[index] = meth->ncode;
1284                   if (debug_link)
1285                     fprintf (stderr, "  addresses[%d] = %p (class %s@%p : %s(%s))\n",
1286                              index,
1287                              &klass->atable->addresses[index],
1288                              (const char*)target_class->name->chars(),
1289                              klass,
1290                              (const char*)sym.name->chars(),
1291                              (const char*)signature->chars());
1292                 }
1293             }
1294           else
1295             klass->atable->addresses[index]
1296               = create_error_method(sym.class_name);
1297
1298           continue;
1299         }
1300
1301       // Try fields only if the target class exists.
1302       if (target_class != NULL)
1303       {
1304         wait_for_state(target_class, JV_STATE_PREPARED);
1305         jclass found_class;
1306         _Jv_Field *the_field = find_field (klass, target_class, &found_class,
1307                                            sym.name, signature);
1308         if ((the_field->flags & java::lang::reflect::Modifier::STATIC))
1309           klass->atable->addresses[index] = the_field->u.addr;
1310         else
1311           throw new java::lang::IncompatibleClassChangeError;
1312       }
1313     }
1314
1315  itable:
1316   if (klass->itable == NULL
1317       || klass->itable->state != 0)
1318     return;
1319
1320   klass->itable->state = 1;
1321
1322   for (index = 0;
1323        (sym = klass->itable_syms[index]).class_name != NULL;
1324        ++index)
1325     {
1326       jclass target_class = _Jv_FindClass (sym.class_name, klass->loader);
1327
1328       _Jv_Utf8Const *signature = sym.signature;
1329       uaddr special;
1330       maybe_adjust_signature (signature, special);
1331
1332       jclass cls;
1333       int i;
1334
1335       wait_for_state(target_class, JV_STATE_LOADED);
1336       bool found = _Jv_getInterfaceMethod (target_class, cls, i,
1337                                            sym.name, signature);
1338
1339       if (found)
1340         {
1341           klass->itable->addresses[index * 2] = cls;
1342           klass->itable->addresses[index * 2 + 1] = (void *)(unsigned long) i;
1343           if (debug_link)
1344             {
1345               fprintf (stderr, "  interfaces[%d] = %p (interface %s@%p : %s(%s))\n",
1346                        index,
1347                        klass->itable->addresses[index * 2],
1348                        (const char*)cls->name->chars(),
1349                        cls,
1350                        (const char*)sym.name->chars(),
1351                        (const char*)signature->chars());
1352               fprintf (stderr, "            [%d] = offset %d\n",
1353                        index + 1,
1354                        (int)(unsigned long)klass->itable->addresses[index * 2 + 1]);
1355             }
1356
1357         }
1358       else
1359         throw new java::lang::IncompatibleClassChangeError;
1360     }
1361
1362 }
1363
1364 // For each catch_record in the list of caught classes, fill in the
1365 // address field.
1366 void
1367 _Jv_Linker::link_exception_table (jclass self)
1368 {
1369   struct _Jv_CatchClass *catch_record = self->catch_classes;
1370   if (!catch_record || catch_record->classname)
1371     return;
1372   catch_record++;
1373   while (catch_record->classname)
1374     {
1375       try
1376         {
1377           jclass target_class
1378             = _Jv_FindClass (catch_record->classname,
1379                              self->getClassLoaderInternal ());
1380           *catch_record->address = target_class;
1381         }
1382       catch (::java::lang::Throwable *t)
1383         {
1384           // FIXME: We need to do something better here.
1385           *catch_record->address = 0;
1386         }
1387       catch_record++;
1388     }
1389   self->catch_classes->classname = (_Jv_Utf8Const *)-1;
1390 }
1391
1392 // Set itable method indexes for members of interface IFACE.
1393 void
1394 _Jv_Linker::layout_interface_methods (jclass iface)
1395 {
1396   if (! iface->isInterface())
1397     return;
1398
1399   // itable indexes start at 1.
1400   // FIXME: Static initalizers currently get a NULL placeholder entry in the
1401   // itable so they are also assigned an index here.
1402   for (int i = 0; i < iface->method_count; i++)
1403     iface->methods[i].index = i + 1;
1404 }
1405
1406 // Prepare virtual method declarations in KLASS, and any superclasses
1407 // as required, by determining their vtable index, setting
1408 // method->index, and finally setting the class's vtable_method_count.
1409 // Must be called with the lock for KLASS held.
1410 void
1411 _Jv_Linker::layout_vtable_methods (jclass klass)
1412 {
1413   if (klass->vtable != NULL || klass->isInterface()
1414       || klass->vtable_method_count != -1)
1415     return;
1416
1417   jclass superclass = klass->getSuperclass();
1418
1419   if (superclass != NULL && superclass->vtable_method_count == -1)
1420     {
1421       JvSynchronize sync (superclass);
1422       layout_vtable_methods (superclass);
1423     }
1424
1425   int index = (superclass == NULL ? 0 : superclass->vtable_method_count);
1426
1427   for (int i = 0; i < klass->method_count; ++i)
1428     {
1429       _Jv_Method *meth = &klass->methods[i];
1430       _Jv_Method *super_meth = NULL;
1431
1432       if (! _Jv_isVirtualMethod (meth))
1433         continue;
1434
1435       if (superclass != NULL)
1436         {
1437           jclass declarer;
1438           super_meth = _Jv_LookupDeclaredMethod (superclass, meth->name,
1439                                                  meth->signature, &declarer);
1440           // See if this method actually overrides the other method
1441           // we've found.
1442           if (super_meth)
1443             {
1444               if (! _Jv_isVirtualMethod (super_meth)
1445                   || ! _Jv_CheckAccess (klass, declarer,
1446                                         super_meth->accflags))
1447                 super_meth = NULL;
1448               else if ((super_meth->accflags
1449                         & java::lang::reflect::Modifier::FINAL) != 0)
1450                 {
1451                   using namespace java::lang;
1452                   StringBuffer *sb = new StringBuffer();
1453                   sb->append(JvNewStringLatin1("method "));
1454                   sb->append(_Jv_GetMethodString(klass, meth));
1455                   sb->append(JvNewStringLatin1(" overrides final method "));
1456                   sb->append(_Jv_GetMethodString(declarer, super_meth));
1457                   throw new VerifyError(sb->toString());
1458                 }
1459             }
1460         }
1461
1462       if (super_meth)
1463         meth->index = super_meth->index;
1464       else
1465         meth->index = index++;
1466     }
1467
1468   klass->vtable_method_count = index;
1469 }
1470
1471 // Set entries in VTABLE for virtual methods declared in KLASS.
1472 void
1473 _Jv_Linker::set_vtable_entries (jclass klass, _Jv_VTable *vtable)
1474 {
1475   for (int i = klass->method_count - 1; i >= 0; i--)
1476     {
1477       using namespace java::lang::reflect;
1478
1479       _Jv_Method *meth = &klass->methods[i];
1480       if (meth->index == (_Jv_ushort) -1)
1481         continue;
1482       if ((meth->accflags & Modifier::ABSTRACT))
1483         // FIXME: it might be nice to have a libffi trampoline here,
1484         // so we could pass in the method name and other information.
1485         vtable->set_method(meth->index,
1486                            (void *) &_Jv_ThrowAbstractMethodError);
1487       else
1488         vtable->set_method(meth->index, meth->ncode);
1489     }
1490 }
1491
1492 // Allocate and lay out the virtual method table for KLASS.  This will
1493 // also cause vtables to be generated for any non-abstract
1494 // superclasses, and virtual method layout to occur for any abstract
1495 // superclasses.  Must be called with monitor lock for KLASS held.
1496 void
1497 _Jv_Linker::make_vtable (jclass klass)
1498 {
1499   using namespace java::lang::reflect;
1500
1501   // If the vtable exists, or for interface classes, do nothing.  All
1502   // other classes, including abstract classes, need a vtable.
1503   if (klass->vtable != NULL || klass->isInterface())
1504     return;
1505
1506   // Ensure all the `ncode' entries are set.
1507   klass->engine->create_ncode(klass);
1508
1509   // Class must be laid out before we can create a vtable.
1510   if (klass->vtable_method_count == -1)
1511     layout_vtable_methods (klass);
1512
1513   // Allocate the new vtable.
1514   _Jv_VTable *vtable = _Jv_VTable::new_vtable (klass->vtable_method_count);
1515   klass->vtable = vtable;
1516
1517   // Copy the vtable of the closest superclass.
1518   jclass superclass = klass->superclass;
1519   {
1520     JvSynchronize sync (superclass);
1521     make_vtable (superclass);
1522   }
1523   for (int i = 0; i < superclass->vtable_method_count; ++i)
1524     vtable->set_method (i, superclass->vtable->get_method (i));
1525
1526   // Set the class pointer and GC descriptor.
1527   vtable->clas = klass;
1528   vtable->gc_descr = _Jv_BuildGCDescr (klass);
1529
1530   // For each virtual declared in klass, set new vtable entry or
1531   // override an old one.
1532   set_vtable_entries (klass, vtable);
1533
1534   // Note that we don't check for abstract methods here.  We used to,
1535   // but there is a JVMS clarification that indicates that a check
1536   // here would be too eager.  And, a simple test case confirms this.
1537 }
1538
1539 // Lay out the class, allocating space for static fields and computing
1540 // offsets of instance fields.  The class lock must be held by the
1541 // caller.
1542 void
1543 _Jv_Linker::ensure_fields_laid_out (jclass klass)
1544 {
1545   if (klass->size_in_bytes != -1)
1546     return;
1547
1548   // Compute the alignment for this type by searching through the
1549   // superclasses and finding the maximum required alignment.  We
1550   // could consider caching this in the Class.
1551   int max_align = __alignof__ (java::lang::Object);
1552   jclass super = klass->getSuperclass();
1553   while (super != NULL)
1554     {
1555       // Ensure that our super has its super installed before
1556       // recursing.
1557       wait_for_state(super, JV_STATE_LOADING);
1558       ensure_fields_laid_out(super);
1559       int num = JvNumInstanceFields (super);
1560       _Jv_Field *field = JvGetFirstInstanceField (super);
1561       while (num > 0)
1562         {
1563           int field_align = get_alignment_from_class (field->type);
1564           if (field_align > max_align)
1565             max_align = field_align;
1566           ++field;
1567           --num;
1568         }
1569       super = super->getSuperclass();
1570     }
1571
1572   int instance_size;
1573   // This is the size of the 'static' non-reference fields.
1574   int non_reference_size = 0;
1575   // This is the size of the 'static' reference fields.  We count
1576   // these separately to make it simpler for the GC to scan them.
1577   int reference_size = 0;
1578
1579   // Although java.lang.Object is never interpreted, an interface can
1580   // have a null superclass.  Note that we have to lay out an
1581   // interface because it might have static fields.
1582   if (klass->superclass)
1583     instance_size = klass->superclass->size();
1584   else
1585     instance_size = java::lang::Object::class$.size();
1586
1587   klass->engine->allocate_field_initializers (klass);
1588
1589   for (int i = 0; i < klass->field_count; i++)
1590     {
1591       int field_size;
1592       int field_align;
1593
1594       _Jv_Field *field = &klass->fields[i];
1595
1596       if (! field->isRef ())
1597         {
1598           // It is safe to resolve the field here, since it's a
1599           // primitive class, which does not cause loading to happen.
1600           resolve_field (field, klass->loader);
1601           field_size = field->type->size ();
1602           field_align = get_alignment_from_class (field->type);
1603         }
1604       else
1605         {
1606           field_size = sizeof (jobject);
1607           field_align = __alignof__ (jobject);
1608         }
1609
1610       field->bsize = field_size;
1611
1612       if ((field->flags & java::lang::reflect::Modifier::STATIC))
1613         {
1614           if (field->u.addr == NULL)
1615             {
1616               // This computes an offset into a region we'll allocate
1617               // shortly, and then adds this offset to the start
1618               // address.
1619               if (field->isRef())
1620                 {
1621                   reference_size = ROUND (reference_size, field_align);
1622                   field->u.boffset = reference_size;
1623                   reference_size += field_size;
1624                 }
1625               else
1626                 {
1627                   non_reference_size = ROUND (non_reference_size, field_align);
1628                   field->u.boffset = non_reference_size;
1629                   non_reference_size += field_size;
1630                 }
1631             }
1632         }
1633       else
1634         {
1635           instance_size      = ROUND (instance_size, field_align);
1636           field->u.boffset   = instance_size;
1637           instance_size     += field_size;
1638           if (field_align > max_align)
1639             max_align = field_align;
1640         }
1641     }
1642
1643   if (reference_size != 0 || non_reference_size != 0)
1644     klass->engine->allocate_static_fields (klass, reference_size,
1645                                            non_reference_size);
1646
1647   // Set the instance size for the class.  Note that first we round it
1648   // to the alignment required for this object; this keeps us in sync
1649   // with our current ABI.
1650   instance_size = ROUND (instance_size, max_align);
1651   klass->size_in_bytes = instance_size;
1652 }
1653
1654 // This takes the class to state JV_STATE_LINKED.  The class lock must
1655 // be held when calling this.
1656 void
1657 _Jv_Linker::ensure_class_linked (jclass klass)
1658 {
1659   if (klass->state >= JV_STATE_LINKED)
1660     return;
1661
1662   int state = klass->state;
1663   try
1664     {
1665       // Short-circuit, so that mutually dependent classes are ok.
1666       klass->state = JV_STATE_LINKED;
1667
1668       _Jv_Constants *pool = &klass->constants;
1669
1670       // Compiled classes require that their class constants be
1671       // resolved here.  However, interpreted classes need their
1672       // constants to be resolved lazily.  If we resolve an
1673       // interpreted class' constants eagerly, we can end up with
1674       // spurious IllegalAccessErrors when the constant pool contains
1675       // a reference to a class we can't access.  This can validly
1676       // occur in an obscure case involving the InnerClasses
1677       // attribute.
1678       if (! _Jv_IsInterpretedClass (klass))
1679         {
1680           // Resolve class constants first, since other constant pool
1681           // entries may rely on these.
1682           for (int index = 1; index < pool->size; ++index)
1683             {
1684               if (pool->tags[index] == JV_CONSTANT_Class)
1685                 // Lazily resolve the entries.
1686                 resolve_pool_entry (klass, index, true);
1687             }
1688         }
1689
1690       // Resolve the remaining constant pool entries.
1691       for (int index = 1; index < pool->size; ++index)
1692         {
1693           if (pool->tags[index] == JV_CONSTANT_String)
1694             {
1695               jstring str;
1696
1697               str = _Jv_NewStringUtf8Const (pool->data[index].utf8);
1698               pool->data[index].o = str;
1699               pool->tags[index] |= JV_CONSTANT_ResolvedFlag;
1700             }
1701         }
1702
1703       if (klass->engine->need_resolve_string_fields())
1704         {
1705           jfieldID f = JvGetFirstStaticField (klass);
1706           for (int n = JvNumStaticFields (klass); n > 0; --n)
1707             {
1708               int mod = f->getModifiers ();
1709               // If we have a static String field with a non-null initial
1710               // value, we know it points to a Utf8Const.
1711
1712               // Finds out whether we have to initialize a String without the
1713               // need to resolve the field.
1714               if ((f->isResolved()
1715                    ? (f->type == &java::lang::String::class$)
1716                    : _Jv_equalUtf8Classnames((_Jv_Utf8Const *) f->type,
1717                                              java::lang::String::class$.name))
1718                   && (mod & java::lang::reflect::Modifier::STATIC) != 0)
1719                 {
1720                   jstring *strp = (jstring *) f->u.addr;
1721                   if (*strp)
1722                     *strp = _Jv_NewStringUtf8Const ((_Jv_Utf8Const *) *strp);
1723                 }
1724               f = f->getNextField ();
1725             }
1726         }
1727
1728       klass->notifyAll ();
1729
1730       _Jv_PushClass (klass);
1731     }
1732   catch (java::lang::Throwable *t)
1733     {
1734       klass->state = state;
1735       throw t;
1736     }
1737 }
1738
1739 // This ensures that symbolic superclass and superinterface references
1740 // are resolved for the indicated class.  This must be called with the
1741 // class lock held.
1742 void
1743 _Jv_Linker::ensure_supers_installed (jclass klass)
1744 {
1745   resolve_class_ref (klass, &klass->superclass);
1746   // An interface won't have a superclass.
1747   if (klass->superclass)
1748     wait_for_state (klass->superclass, JV_STATE_LOADING);
1749
1750   for (int i = 0; i < klass->interface_count; ++i)
1751     {
1752       resolve_class_ref (klass, &klass->interfaces[i]);
1753       wait_for_state (klass->interfaces[i], JV_STATE_LOADING);
1754     }
1755 }
1756
1757 // This adds missing `Miranda methods' to a class.
1758 void
1759 _Jv_Linker::add_miranda_methods (jclass base, jclass iface_class)
1760 {
1761   // Note that at this point, all our supers, and the supers of all
1762   // our superclasses and superinterfaces, will have been installed.
1763
1764   for (int i = 0; i < iface_class->interface_count; ++i)
1765     {
1766       jclass interface = iface_class->interfaces[i];
1767
1768       for (int j = 0; j < interface->method_count; ++j)
1769         {
1770           _Jv_Method *meth = &interface->methods[j];
1771           // Don't bother with <clinit>.
1772           if (meth->name->first() == '<')
1773             continue;
1774           _Jv_Method *new_meth = _Jv_LookupDeclaredMethod (base, meth->name,
1775                                                            meth->signature);
1776           if (! new_meth)
1777             {
1778               // We assume that such methods are very unlikely, so we
1779               // just reallocate the method array each time one is
1780               // found.  This greatly simplifies the searching --
1781               // otherwise we have to make sure that each such method
1782               // found is really unique among all superinterfaces.
1783               int new_count = base->method_count + 1;
1784               _Jv_Method *new_m
1785                 = (_Jv_Method *) _Jv_AllocRawObj (sizeof (_Jv_Method)
1786                                                   * new_count);
1787               memcpy (new_m, base->methods,
1788                       sizeof (_Jv_Method) * base->method_count);
1789
1790               // Add new method.
1791               new_m[base->method_count] = *meth;
1792               new_m[base->method_count].index = (_Jv_ushort) -1;
1793               new_m[base->method_count].accflags
1794                 |= java::lang::reflect::Modifier::INVISIBLE;
1795
1796               base->methods = new_m;
1797               base->method_count = new_count;
1798             }
1799         }
1800
1801       wait_for_state (interface, JV_STATE_LOADED);
1802       add_miranda_methods (base, interface);
1803     }
1804 }
1805
1806 // This ensures that the class' method table is "complete".  This must
1807 // be called with the class lock held.
1808 void
1809 _Jv_Linker::ensure_method_table_complete (jclass klass)
1810 {
1811   if (klass->vtable != NULL)
1812     return;
1813
1814   // We need our superclass to have its own Miranda methods installed.
1815   if (! klass->isInterface())
1816     wait_for_state (klass->getSuperclass (), JV_STATE_LOADED);
1817
1818   // A class might have so-called "Miranda methods".  This is a method
1819   // that is declared in an interface and not re-declared in an
1820   // abstract class.  Some compilers don't emit declarations for such
1821   // methods in the class; this will give us problems since we expect
1822   // a declaration for any method requiring a vtable entry.  We handle
1823   // this here by searching for such methods and constructing new
1824   // internal declarations for them.  Note that we do this
1825   // unconditionally, and not just for abstract classes, to correctly
1826   // account for cases where a class is modified to be concrete and
1827   // still incorrectly inherits an abstract method.
1828   int pre_count = klass->method_count;
1829   add_miranda_methods (klass, klass);
1830
1831   // Let the execution engine know that we've added methods.
1832   if (klass->method_count != pre_count)
1833     klass->engine->post_miranda_hook(klass);
1834 }
1835
1836 // Verify a class.  Must be called with class lock held.
1837 void
1838 _Jv_Linker::verify_class (jclass klass)
1839 {
1840   klass->engine->verify(klass);
1841 }
1842
1843 // Check the assertions contained in the type assertion table for KLASS.
1844 // This is the equivilent of bytecode verification for native, BC-ABI code.
1845 void
1846 _Jv_Linker::verify_type_assertions (jclass klass)
1847 {
1848   if (debug_link)
1849     fprintf (stderr, "Evaluating type assertions for %s:\n",
1850              klass->name->chars());
1851
1852   if (klass->assertion_table == NULL)
1853     return;
1854
1855   for (int i = 0;; i++)
1856     {
1857       int assertion_code = klass->assertion_table[i].assertion_code;
1858       _Jv_Utf8Const *op1 = klass->assertion_table[i].op1;
1859       _Jv_Utf8Const *op2 = klass->assertion_table[i].op2;
1860
1861       if (assertion_code == JV_ASSERT_END_OF_TABLE)
1862         return;
1863       else if (assertion_code == JV_ASSERT_TYPES_COMPATIBLE)
1864         {
1865           if (debug_link)
1866             {
1867               fprintf (stderr, "  code=%i, operand A=%s B=%s\n",
1868                        assertion_code, op1->chars(), op2->chars());
1869             }
1870
1871           // The operands are class signatures. op1 is the source,
1872           // op2 is the target.
1873           jclass cl1 = _Jv_FindClassFromSignature (op1->chars(),
1874             klass->getClassLoaderInternal());
1875           jclass cl2 = _Jv_FindClassFromSignature (op2->chars(),
1876             klass->getClassLoaderInternal());
1877
1878           // If the class doesn't exist, ignore the assertion. An exception
1879           // will be thrown later if an attempt is made to actually
1880           // instantiate the class.
1881           if (cl1 == NULL || cl2 == NULL)
1882             continue;
1883
1884           if (! _Jv_IsAssignableFromSlow (cl1, cl2))
1885             {
1886               jstring s = JvNewStringUTF ("Incompatible types: In class ");
1887               s = s->concat (klass->getName());
1888               s = s->concat (JvNewStringUTF (": "));
1889               s = s->concat (cl1->getName());
1890               s = s->concat (JvNewStringUTF (" is not assignable to "));
1891               s = s->concat (cl2->getName());
1892               throw new java::lang::VerifyError (s);
1893             }
1894         }
1895       else if (assertion_code == JV_ASSERT_IS_INSTANTIABLE)
1896         {
1897           // TODO: Implement this.
1898         }
1899       // Unknown assertion codes are ignored, for forwards-compatibility.
1900     }
1901 }
1902
1903 void
1904 _Jv_Linker::print_class_loaded (jclass klass)
1905 {
1906   char *codesource = NULL;
1907   if (klass->protectionDomain != NULL)
1908     {
1909       java::security::CodeSource *cs
1910         = klass->protectionDomain->getCodeSource();
1911       if (cs != NULL)
1912         {
1913           jstring css = cs->toString();
1914           int len = JvGetStringUTFLength(css);
1915           codesource = (char *) _Jv_AllocBytes(len + 1);
1916           JvGetStringUTFRegion(css, 0, css->length(), codesource);
1917           codesource[len] = '\0';
1918         }
1919     }
1920   if (codesource == NULL)
1921     codesource = (char *) "<no code source>";
1922
1923   const char *abi;
1924   if (_Jv_IsInterpretedClass (klass))
1925     abi = "bytecode";
1926   else if (_Jv_IsBinaryCompatibilityABI (klass))
1927     abi = "BC-compiled";
1928   else
1929     abi = "pre-compiled";
1930
1931   fprintf (stderr, "[Loaded (%s) %s from %s]\n", abi, klass->name->chars(),
1932            codesource);
1933 }
1934
1935 // FIXME: mention invariants and stuff.
1936 void
1937 _Jv_Linker::wait_for_state (jclass klass, int state)
1938 {
1939   if (klass->state >= state)
1940     return;
1941
1942   JvSynchronize sync (klass);
1943
1944   // This is similar to the strategy for class initialization.  If we
1945   // already hold the lock, just leave.
1946   java::lang::Thread *self = java::lang::Thread::currentThread();
1947   while (klass->state <= state
1948          && klass->thread
1949          && klass->thread != self)
1950     klass->wait ();
1951
1952   java::lang::Thread *save = klass->thread;
1953   klass->thread = self;
1954
1955   // Allocate memory for static fields and constants.
1956   if (GC_base (klass) && klass->fields && ! GC_base (klass->fields))
1957     {
1958       jsize count = klass->field_count;
1959       if (count)
1960         {
1961           _Jv_Field* fields
1962             = (_Jv_Field*) _Jv_AllocRawObj (count * sizeof (_Jv_Field));
1963           memcpy ((void*)fields,
1964                   (void*)klass->fields,
1965                   count * sizeof (_Jv_Field));
1966           klass->fields = fields;
1967         }
1968     }
1969
1970   // Print some debugging info if requested.  Interpreted classes are
1971   // handled in defineclass, so we only need to handle the two
1972   // pre-compiled cases here.
1973   if ((klass->state == JV_STATE_COMPILED
1974           || klass->state == JV_STATE_PRELOADING)
1975       && ! _Jv_IsInterpretedClass (klass))
1976     {
1977       if (gcj::verbose_class_flag)
1978         print_class_loaded (klass);
1979       ++gcj::loadedClasses;
1980     }
1981
1982   try
1983     {
1984       if (state >= JV_STATE_LOADING && klass->state < JV_STATE_LOADING)
1985         {
1986           ensure_supers_installed (klass);
1987           klass->set_state(JV_STATE_LOADING);
1988         }
1989
1990       if (state >= JV_STATE_LOADED && klass->state < JV_STATE_LOADED)
1991         {
1992           ensure_method_table_complete (klass);
1993           klass->set_state(JV_STATE_LOADED);
1994         }
1995
1996       if (state >= JV_STATE_PREPARED && klass->state < JV_STATE_PREPARED)
1997         {
1998           ensure_fields_laid_out (klass);
1999           make_vtable (klass);
2000           layout_interface_methods (klass);
2001           prepare_constant_time_tables (klass);
2002           klass->set_state(JV_STATE_PREPARED);
2003         }
2004
2005       if (state >= JV_STATE_LINKED && klass->state < JV_STATE_LINKED)
2006         {
2007           if (gcj::verifyClasses)
2008             verify_class (klass);
2009
2010           ensure_class_linked (klass);
2011           link_exception_table (klass);
2012           link_symbol_table (klass);
2013           klass->set_state(JV_STATE_LINKED);
2014         }
2015     }
2016   catch (java::lang::Throwable *exc)
2017     {
2018       klass->thread = save;
2019       klass->set_state(JV_STATE_ERROR);
2020       throw exc;
2021     }
2022
2023   klass->thread = save;
2024
2025   if (klass->state == JV_STATE_ERROR)
2026     throw new java::lang::LinkageError;
2027 }