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