PATCH: Constant-time interface dispatch, type checking, inlining...

Bryce McKinlay bryce@albatross.co.nz
Thu Dec 9 22:01:00 GMT 1999


This patch contains the libgcj runtime side of my "new" interface dispatch and
type-checking code. In essence it implements constant time interface call and
type tests as specified by Per Bothner @
http://sourceware.cygnus.com/ml/java-discuss/1999-q3/msg00377.html

It works by inserting a new call into the class initialization process
(Class.initializeClass()) to generate interface dispatch tables for the newly
loaded class. This is done after initial class loading and preparation, but
before class initializers are run and before the class's super classes have
necessarily been initialized. It is called with the class mutex held.

_Jv_LookupInterfaceMethod is replaced with a new version with new parameters,
and _Jv_IsAssignableFrom, _Jv_CheckCast, etc, are rewritten to take advantage of
these tables.

The result?

Interface dispatch is now approximately 3X faster than the Netscape scenario (ie
a 100% cache hit rate) under the old code:

(Time for 10M interface method invocations on a P2-233):
Old code without method cache:       172931ms [17293ns / call]
Old code with 100% cache hit rate:   5876ms [587ns / call]
New code, constant time:             1747ms [174ns / call]

Additional speed improvements could be achieved by inlining (selectively?), in
the compiler, calls to _Jv_LookupInterfaceMethod.

This code does not yet work with the interpreter. The itable generation code
itself should work with interpreted classes, assuming the interpreter provides
all the required class metadata fields, but the interpret.cc needs to be updated
to use the new _Jv_LookupInterfaceMethod(). I will look into this if no-one else
beats be to it. For now, libgcj must be configured with "--disable-interpreter".

Naturally there is some overhead incurred at class initialization time building
the interface dispatch tables, but this seems surprisingly small (it doesn't
break above the 0.00s threshold in gprof for my small test applications that
load < 50 classes). The technique should also be fairly memory efficient (see
Per's message for details). In fact, memory usage for my test apps as observed
by 'ps' actually decreased by ~1% using the new code. Go figure.

This patch also reflects my observation that there is a huge performance drain
associated with multiple calls occurring inside the frequently compiler called
methods, such as _Jv_CheckArrayStore and _Jv_AllocObj. By shuffling some methods
around and some gratuitous inlining, I was able to achieve some significant
improvements on many apps. For example, ShellSort
( http://waitaki.otago.ac.nz/~bryce/gcj/ShellSort.java ) now performs about 35%
faster thanks to optimization of _Jv_CheckArrayStore. It is ~70% faster than the
IBM JDK now! The additional runtime size from doing this is, again, minimal -
around 1-2K on ia32. I think there is still plenty more optimization that could
be done with regard to arrays and object allocation, simply by reducing the
number of calls that are made here.

I've attached a simple regression test I wrote to test this stuff, it might be
helpful in diagnosing any problems.

Thats about it. Please test this stuff and let me know how it works for you. I'm
sure there is a bug or two ;-)

enjoy

  [ bryce ]


1999-12-09  Bryce McKinlay  <bryce@albatross.co.nz>

        * java/lang/Class.h (union _Jv_IDispatchTable): New declaration.
        (struct _Jv_ifaces): New declaration.
        JV_CLASS: New macro definition.
        (getComponentType): Relocate below isArray() for inlining.
        (getModifiers): Declare `inline'.
        (getSuperclass): Ditto.
        (isArray): Ditto.
        (isPrimitive): Ditto.
        (_Jv_IsAssignableFrom): New prototype.
        (_Jv_LookupInterfaceMethod0): Ditto.
        (_Jv_InitClass): Move from natClass.cc. Declare `inline'. Check for
        JV_STATE_DONE before invoking initializeClass().
        (_Jv_PrepareConstantTimeTables): New prototype.
        (_Jv_GetInterfaces): Ditto.
        (_Jv_GenerateITable): Ditto.
        (_Jv_GetMethodString): Ditto.
        (_Jv_AppendPartialITable): Ditto.
        (_Jv_FindIIndex): Ditto.
        depth, ancestors, idt: New fields.

        * java/lang/natObject.cc (getClass): Use JV_CLASS.

        * java/lang/natClass.cc (isAssignableFrom): Move functionality to
        inline function `_Jv_IsAssignableFrom'. Use that function.
        (isInstance): Declare `inline'.
        (initializeClass): Enter class monitor before checking `state'. Exit
        class monitor before calling resolveClass0. Call
        _Jv_PrepareConstantTimeTables with the class monitor held.
        (_Jv_LookupInterfaceMethod0): New inline function. Rewritten
        _Jv_LookupInterfaceMethod implementation for new interface dispatch.
        (_Jv_IsAssignableFrom): Ditto.
        (_Jv_IsInstanceOf): Use _Jv_IsAssignableFrom.
        (_Jv_CheckCast): Move from prims.cc. Use JV_CLASS and
        _Jv_IsAssignableFrom.
        (_Jv_CheckArrayStore): Ditto.
        (_Jv_LookupInterfaceMethod): New arguments: `iface' and `idx'.
        Remove old arguments `name' and `signature'. Use
        _Jv_LookupInterfaceMethod0.
        INITIAL_IOFFSETS_LEN, INITIAL_IFACES_LEN: New #defines.
        (_Jv_PrepareConstantTimeTables): New function.
        (_Jv_GetInterfaces): Ditto.
        (_Jv_GenerateITable): Ditto.
        (_Jv_GetMethodString): Ditto.
        (_Jv_AppendPartialITable): Ditto.
        iindex_mutex, iindex_mutex_initialized: New static fields.
        (_Jv_FindIIndex): New function.

        * java/lang/natClassLoader.cc (_Jv_NewClass): Set new jclass fields.

        * prims.cc (_Jv_CheckCast): Moved to natClass.cc.
        (_Jv_CheckArrayStore): Ditto.
        (JvNewCharArray, JvNewBooleanArray, JvNewByteArray, JvNewShortArray,
        JvNewIntArray, JvNewLongArray, JvNewFloatArray, JvNewDoubleArray):
        Moved to gcj/array.h.
        (_Jv_Realloc): New function.

        * gcj/cni.h: Move _Jv_PrimClass definitions to gcj/array.h.

        * gcj/array.h: _Jv_PrimClass definitions moved from gcj/cni.h.
        (JvNewCharArray, JvNewBooleanArray, JvNewByteArray,
        JvNewShortArray, JvNewIntArray, JvNewLongArray, JvNewFloatArray,
        JvNewDoubleArray): Implementations moved from prims.cc and declared
        `inline'.

        * gcj/javaprims.h (_Jv_Realloc): Prototype.

        * include/jvm.h (_Jv_LookupInterfaceMethod): New parameters.
Index: libjava/java/lang/Class.h
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/lang/Class.h,v
retrieving revision 1.7
diff -u -r1.7 Class.h
--- Class.h	1999/09/10 22:03:08	1.7
+++ Class.h	1999/12/09 23:48:36
@@ -62,8 +62,37 @@
   void *ncode;
 };
 
+// Interface Dispatch Tables 
+union _Jv_IDispatchTable
+{
+  struct
+  {
+    // Index into interface's ioffsets.
+    short iindex;
+    short itable_length;
+    // Class Interface dispatch table.
+    void **itable;
+  } cls;
+
+  struct
+  {
+    // Offsets into implementation class itables.
+    short *ioffsets;
+  } iface;
+};
+
+// Used by _Jv_GetInterfaces ()
+struct _Jv_ifaces
+{
+  jclass *list;
+  short len;
+  short count;
+};
+
 #define JV_PRIMITIVE_VTABLE ((_Jv_VTable *) -1)
 
+#define JV_CLASS(Obj) ((jclass) (*(_Jv_VTable **) Obj)->clas)
+
 class java::lang::Class : public java::lang::Object
 {
 public:
@@ -75,11 +104,6 @@
       return loader;
     }
 
-  jclass getComponentType (void)
-    {
-      return isArray () ? (* (jclass *) &methods) : 0;
-    }
-
   java::lang::reflect::Constructor *getConstructor (JArray<jclass> *);
   JArray<java::lang::reflect::Constructor *> *getConstructors (void);
   java::lang::reflect::Constructor *getDeclaredConstructor (JArray<jclass> *);
@@ -103,7 +127,7 @@
   java::lang::reflect::Method *getMethod (jstring, JArray<jclass> *);
   JArray<java::lang::reflect::Method *> *getMethods (void);
 
-  jint getModifiers (void)
+  inline jint getModifiers (void)
     {
       return accflags;
     }
@@ -114,21 +138,26 @@
   java::io::InputStream *getResourceAsStream (jstring resourceName);
   JArray<jobject> *getSigners (void);
 
-  jclass getSuperclass (void)
+  inline jclass getSuperclass (void)
     {
       return superclass;
     }
 
-  jboolean isArray (void)
+  inline jboolean isArray (void)
     {
       return name->data[0] == '[';
     }
 
+  inline jclass getComponentType (void)
+    {
+      return isArray () ? (* (jclass *) &methods) : 0;
+    }
+
   jboolean isAssignableFrom (jclass cls);
   jboolean isInstance (jobject obj);
   jboolean isInterface (void);
-
-  jboolean isPrimitive (void)
+  
+  inline jboolean isPrimitive (void)
     {
       return vtable == JV_PRIMITIVE_VTABLE;
     }
@@ -141,11 +170,12 @@
     {
       return size_in_bytes;
     }
-
+    
   // finalization
   void finalize ();
 
-private:
+private:   
+
   void checkMemberAccess (jint flags);
 
   // Various functions to handle class initialization.
@@ -156,7 +186,17 @@
   // Friend functions implemented in natClass.cc.
   friend _Jv_Method *_Jv_GetMethodLocal (jclass klass, _Jv_Utf8Const *name,
 					 _Jv_Utf8Const *signature);
-  friend void _Jv_InitClass (jclass klass);
+  friend int _Jv_IsAssignableFrom(jclass, jclass);
+
+  friend void *_Jv_LookupInterfaceMethod0 (jclass klass, jclass iface, 
+					   int method_idx);
+
+  inline friend void 
+  _Jv_InitClass (jclass klass)
+  {
+    if (klass->state != JV_STATE_DONE)
+      klass->initializeClass ();
+  }
 
   friend jfieldID JvGetFirstInstanceField (jclass);
   friend jint JvNumInstanceFields (jclass);
@@ -186,6 +226,14 @@
 			      java::lang::ClassLoader *loader);
 
   friend void _Jv_PrepareCompiledClass (jclass);
+  					    
+  friend void _Jv_PrepareConstantTimeTables (jclass);
+  friend short _Jv_GetInterfaces (jclass, _Jv_ifaces *);
+  friend void _Jv_GenerateITable (jclass, _Jv_ifaces *, short *);
+  friend jstring _Jv_GetMethodString(jclass, _Jv_Utf8Const *);
+  friend short _Jv_AppendPartialITable (jclass, jclass, void **, short);
+  friend short _Jv_FindIIndex (jclass *, short *, short);
+  
 
 #ifdef INTERPRETER
   friend jboolean _Jv_IsInterpretedClass (jclass);
@@ -248,6 +296,12 @@
   // The thread which has locked this class.  Used during class
   // initialization.
   java::lang::Thread *thread;
+  // How many levels of "extends" this class is removed from Object.
+  short depth;
+  // Vector of this class's superclasses, ordered by decreasing depth.
+  jclass *ancestors;
+  // Interface Dispatch Table.
+  _Jv_IDispatchTable *idt;
 };
 
 #endif /* __JAVA_LANG_CLASS_H__ */
Index: libjava/java/lang/natObject.cc
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/lang/natObject.cc,v
retrieving revision 1.4
diff -u -r1.4 natObject.cc
--- natObject.cc	1999/11/25 00:36:51	1.4
+++ natObject.cc	1999/12/09 23:48:36
@@ -49,8 +49,7 @@
 jclass
 java::lang::Object::getClass (void)
 {
-  _Jv_VTable **dt = (_Jv_VTable **) this;
-  return (*dt)->clas;
+  return JV_CLASS (this);
 }
 
 jint
@@ -175,7 +174,8 @@
     sync_init ();
   _Jv_SyncInfo *si = (_Jv_SyncInfo *) sync_info;
   if (_Jv_CondNotify (&si->condition, &si->mutex))
-    JvThrow (new IllegalMonitorStateException);
+    JvThrow (new IllegalMonitorStateException(JvNewStringLatin1 
+                                              ("current thread not owner")));
 }
 
 void
@@ -185,7 +185,8 @@
     sync_init ();
   _Jv_SyncInfo *si = (_Jv_SyncInfo *) sync_info;
   if (_Jv_CondNotifyAll (&si->condition, &si->mutex))
-    JvThrow (new IllegalMonitorStateException);
+    JvThrow (new IllegalMonitorStateException(JvNewStringLatin1 
+                                              ("current thread not owner")));
 }
 
 void
@@ -197,7 +198,8 @@
     JvThrow (new IllegalArgumentException);
   _Jv_SyncInfo *si = (_Jv_SyncInfo *) sync_info;
   if (_Jv_CondWait (&si->condition, &si->mutex, timeout, nanos))
-    JvThrow (new IllegalMonitorStateException);
+    JvThrow (new IllegalMonitorStateException(JvNewStringLatin1 
+                                              ("current thread not owner")));
   if (Thread::interrupted())
     JvThrow (new InterruptedException);
 }
Index: libjava/java/lang/natClass.cc
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/lang/natClass.cc,v
retrieving revision 1.8
diff -u -r1.8 natClass.cc
--- natClass.cc	1999/11/18 07:19:00	1.8
+++ natClass.cc	1999/12/09 23:48:37
@@ -10,13 +10,17 @@
 
 #include <config.h>
 
+#include <limits.h>
 #include <stdlib.h>
+#include <stdio.h>
 #include <string.h>
 
 #pragma implementation "Class.h"
 
 #include <gcj/cni.h>
 #include <jvm.h>
+#include <java-threads.h>
+
 #include <java/lang/Class.h>
 #include <java/lang/ClassLoader.h>
 #include <java/lang/String.h>
@@ -26,6 +30,8 @@
 #include <java/lang/reflect/Field.h>
 #include <java/lang/reflect/Constructor.h>
 #include <java/lang/AbstractMethodError.h>
+#include <java/lang/ArrayStoreException.h>
+#include <java/lang/ClassCastException.h>
 #include <java/lang/ClassNotFoundException.h>
 #include <java/lang/IllegalAccessException.h>
 #include <java/lang/IllegalAccessError.h>
@@ -33,6 +39,7 @@
 #include <java/lang/InstantiationException.h>
 #include <java/lang/NoClassDefFoundError.h>
 #include <java/lang/NoSuchFieldException.h>
+#include <java/lang/NoSuchMethodError.h>
 #include <java/lang/NoSuchMethodException.h>
 #include <java/lang/Thread.h>
 #include <java/lang/NullPointerException.h>
@@ -289,40 +296,10 @@
 jboolean
 java::lang::Class::isAssignableFrom (jclass klass)
 {
-  if (this == klass)
-    return true;
-  // Primitive types must be equal, which we just tested for.
-  if (isPrimitive () || ! klass || klass->isPrimitive())
-    return false;
-
-  // If target is array, so must source be.
-  if (isArray ())
-    {
-      if (! klass->isArray())
-	return false;
-      return getComponentType()->isAssignableFrom(klass->getComponentType());
-    }
-
-  if (isAssignableFrom (klass->getSuperclass()))
-    return true;
-
-  if (isInterface())
-    {
-      // See if source implements this interface.
-      for (int i = 0; i < klass->interface_count; ++i)
-	{
-	  jclass interface = klass->interfaces[i];
-	  // FIXME: ensure that class is prepared here.
-	  // See Spec 12.3.2.
-	  if (isAssignableFrom (interface))
-	    return true;
-	}
-    }
-
-  return false;
+  return _Jv_IsAssignableFrom (this, klass);
 }
 
-jboolean
+inline jboolean
 java::lang::Class::isInstance (jobject obj)
 {
   if (! obj || isPrimitive ())
@@ -330,7 +307,7 @@
   return isAssignableFrom (obj->getClass());
 }
 
-jboolean
+inline jboolean
 java::lang::Class::isInterface (void)
 {
   return (accflags & java::lang::reflect::Modifier::INTERFACE) != 0;
@@ -389,33 +366,27 @@
   // Short-circuit to avoid needless locking.
   if (state == JV_STATE_DONE)
     return;
+
+  // Step 1.
+  _Jv_MonitorEnter (this);
 
-  // do this before we enter the monitor below, since this can cause
-  // exceptions.  Here we assume, that reading "state" is an atomic
-  // operation, I pressume that is true? --Kresten
   if (state < JV_STATE_LINKED)
-    {
+    {    
 #ifdef INTERPRETER
       if (_Jv_IsInterpretedClass (this))
 	{
+	  // this can throw exceptions, so exit the monitor as a precaution.
+	  _Jv_MonitorExit (this);
 	  java::lang::ClassLoader::resolveClass0 (this);
-
-	  // Step 1.
 	  _Jv_MonitorEnter (this);
 	}
       else
 #endif
         {
-          // Step 1.
-	  _Jv_MonitorEnter (this);
 	  _Jv_PrepareCompiledClass (this);
-	}
+	}	
+      _Jv_PrepareConstantTimeTables (this);
     }
-  else
-    {
-      // Step 1.
-      _Jv_MonitorEnter (this);
-    }
 
   // Step 2.
   java::lang::Thread *self = java::lang::Thread::currentThread();
@@ -506,96 +477,403 @@
     }
   return NULL;
 }
-
-// NOTE: MCACHE_SIZE should be a power of 2 minus one.
-#define MCACHE_SIZE 1023
 
-struct _Jv_mcache
+inline void *
+_Jv_LookupInterfaceMethod0 (jclass klass, jclass iface, int method_idx)
 {
-  jclass klass;
-  _Jv_Method *method;
-};
-
-static _Jv_mcache method_cache[MCACHE_SIZE + 1];
-
-static void *
-_Jv_FindMethodInCache (jclass klass,
-		       _Jv_Utf8Const *name,
-		       _Jv_Utf8Const *signature)
-{
-  int index = name->hash & MCACHE_SIZE;
-  _Jv_mcache *mc = method_cache + index;
-  _Jv_Method *m = mc->method;
-
-  if (mc->klass == klass
-      && m != NULL		// thread safe check
-      && _Jv_equalUtf8Consts (m->name, name)
-      && _Jv_equalUtf8Consts (m->signature, signature))
-    return mc->method->ncode;
-  return NULL;
+  _Jv_IDispatchTable *cldt = klass->idt;
+  int idx = iface->idt->iface.ioffsets[cldt->cls.iindex] + method_idx;
+  return cldt->cls.itable[idx];
 }
 
-static void
-_Jv_AddMethodToCache (jclass klass,
-			_Jv_Method *method)
+void *
+_Jv_LookupInterfaceMethod (jclass klass, jclass iface, int method_idx)
 {
-  _Jv_MonitorEnter (&ClassClass); 
+  return _Jv_LookupInterfaceMethod0 (klass, iface, method_idx);
+}
 
-  int index = method->name->hash & MCACHE_SIZE;
+// Defined as int instead of jboolean to hack around gcc 2.95.2 miscompiling 
+// this (gcc 2.96 seems ok).
+inline int
+_Jv_IsAssignableFrom(jclass target, jclass source)
+{
+  if (target == &ObjectClass ||
+      source == target ||
+      (source->ancestors != NULL && 
+       source->ancestors[source->depth - target->depth] == target))
+     return true;
+     
+  // If target is array, so must source be.  
+  if (target->isArray ())
+    {
+      if (! source->isArray())
+	return false;
+      return _Jv_IsAssignableFrom(target->getComponentType(), 
+                                  source->getComponentType());
+    }
+    
+  if (target->isInterface())
+    {
+      _Jv_IDispatchTable *cl_idt = source->idt;
+      _Jv_IDispatchTable *if_idt = target->idt;
+      short cl_iindex = cl_idt->cls.iindex;
+      if (cl_iindex <= if_idt->iface.ioffsets[0])
+        {
+	  short offset = if_idt->iface.ioffsets[cl_iindex];
+	  if (offset < cl_idt->cls.itable_length
+	      && cl_idt->cls.itable[offset] == target)
+	    return true;
+	}
+      return false;
+    }
+    
+  return false;
+}
 
-  method_cache[index].method = method;
-  method_cache[index].klass = klass;
+jboolean
+_Jv_IsInstanceOf(jobject obj, jclass cl)
+{
+  return (obj ? _Jv_IsAssignableFrom (cl, JV_CLASS (obj)) : false);
+}
 
-  _Jv_MonitorExit (&ClassClass);
+void*
+_Jv_CheckCast (jclass c, jobject obj)
+{
+  if (obj != NULL && ! _Jv_IsAssignableFrom(c, JV_CLASS (obj)))
+    JvThrow (new java::lang::ClassCastException);
+  return obj;
 }
 
-void *
-_Jv_LookupInterfaceMethod (jclass klass, _Jv_Utf8Const *name,
-			   _Jv_Utf8Const *signature)
+void
+_Jv_CheckArrayStore (jobject arr, jobject obj)
+{
+  if (obj)
+    {
+      JvAssert (arr != NULL);
+      jclass elt_class = (JV_CLASS (arr))->getComponentType();
+      jclass obj_class = JV_CLASS (obj);
+      if (! _Jv_IsAssignableFrom (elt_class, obj_class))
+	JvThrow (new java::lang::ArrayStoreException);
+    }
+}
+
+#define INITIAL_IOFFSETS_LEN 4
+#define INITIAL_IFACES_LEN 4
+
+// Generate tables for constant-time assignment testing and interface dispatch.
+void 
+_Jv_PrepareConstantTimeTables (jclass klass)
 {
-  // FIXME: can't do this until we have a working class loader.
-  // This probably isn't the right thing to do anyway, since we can't
-  // call a method of a class until the class is linked.  But this
-  // captures the general idea.
-  // klass->getClassLoader()->resolveClass(klass);
-  // 
-  // KKT: This is unnessecary, exactly for the reason you present: 
-  // _Jv_LookupInterfaceMethod is only called on object instances, and
-  // such have already been initialized (which includes resolving).
-
-  void *ncode = _Jv_FindMethodInCache (klass, name, signature);
-  if (ncode != 0)
-    return ncode;
+  if (klass->isPrimitive () || klass->isInterface ())
+    return;
 
-  for (; klass; klass = klass->getSuperclass())
+  // Calculate the class depth and ancestor table.
+  // The depth of a class is how many "extends" it is removed from Object.
+  // Thus the depth of java.lang.Object is 0, but the depth of
+  // java.io.FilterOutputStream is 2. Depth is defined for
+  // all regular and array classes, but not interfaces or primitive types.
+   
+  jclass klass0 = klass;
+  while (klass0 != &ObjectClass)
+    {
+      klass0 = klass0->superclass;
+      klass->depth++;
+    }
+
+  // We can do class member testing in constant time adding in each class
+  // using a small extra table of all the ancestor classes.
+  // Note also we do not need to include the java.lang.Object in the table
+  // of ancestors, since it is redundant.
+  // If we order this table from current classes down by decreasing depth,
+  // we can combine the ancestors table with the pointer to the actual classs.
+	
+  klass->ancestors = (jclass *) _Jv_Malloc (klass->depth * sizeof (jclass));
+  klass0 = klass;
+  for (int index = 0; index < klass->depth; index++)
+    {
+      klass->ancestors[index] = klass0;
+      klass0 = klass0->superclass;
+    }
+    
+  if (klass->isArray () 
+      || java::lang::reflect::Modifier::isAbstract (klass->accflags))
+    return;
+
+  klass->idt = 
+    (_Jv_IDispatchTable *) _Jv_Malloc (sizeof (_Jv_IDispatchTable));
+    
+  _Jv_ifaces ifaces;
+
+  ifaces.count = 0;
+  ifaces.len = INITIAL_IFACES_LEN;
+  ifaces.list = (jclass *) _Jv_Malloc (ifaces.len * sizeof (jclass *));
+
+  int itable_size = _Jv_GetInterfaces (klass, &ifaces);
+
+  if (ifaces.count > 0)
     {
-      _Jv_Method *meth = _Jv_GetMethodLocal (klass, name, signature);
-      if (! meth)
-	continue;
+      klass->idt->cls.itable = 
+	(void **) _Jv_Malloc (itable_size * sizeof (void *));
+      klass->idt->cls.itable_length = itable_size;
+    
+      short *itable_offsets = 
+	(short *) _Jv_Malloc (ifaces.count * sizeof (short));
 
-      if (java::lang::reflect::Modifier::isStatic(meth->accflags))
-	JvThrow (new java::lang::IncompatibleClassChangeError);
-      if (java::lang::reflect::Modifier::isAbstract(meth->accflags))
-	JvThrow (new java::lang::AbstractMethodError);
-      if (! java::lang::reflect::Modifier::isPublic(meth->accflags))
-	JvThrow (new java::lang::IllegalAccessError);
+      _Jv_GenerateITable (klass, &ifaces, itable_offsets);
 
-      _Jv_AddMethodToCache (klass, meth);
+      short cls_iindex = 
+	_Jv_FindIIndex (ifaces.list, itable_offsets, ifaces.count);
 
-      return meth->ncode;
+      for (int i=0; i < ifaces.count; i++)
+	{
+	  ifaces.list[i]->idt->iface.ioffsets[cls_iindex] =
+	    itable_offsets[i];
+	}
+
+      klass->idt->cls.iindex = cls_iindex;	    
+
+      _Jv_Free (ifaces.list);
+      _Jv_Free (itable_offsets);
     }
-  JvThrow (new java::lang::IncompatibleClassChangeError);
-  return NULL;			// Placate compiler.
+  else 
+    {
+      klass->idt->cls.iindex = SHRT_MAX;
+    }
+}
+
+// Return index of item in list, or -1 if item is not present.
+short
+_Jv_IndexOf (void *item, void **list, short list_len)
+{
+  for (int i=0; i < list_len; i++)
+    {
+      if (list[i] == item)
+        return i;
+    }
+  return -1;
 }
 
+// Find all unique interfaces directly or indirectly implemented by klass.
+// Returns the size of the interface dispatch table (itable) for klass, which 
+// is the number of unique interfaces plus the total number of methods that 
+// those interfaces declare. May extend ifaces if required.
+short
+_Jv_GetInterfaces (jclass klass, _Jv_ifaces *ifaces)
+{
+  short result = 0;
+  
+  for (int i=0; i < klass->interface_count; i++)
+    {
+      jclass iface = klass->interfaces[i];
+      if (_Jv_IndexOf (iface, (void **) ifaces->list, ifaces->count) == -1)
+        {
+	  if (ifaces->count + 1 >= ifaces->len)
+	    {
+	      /* Resize ifaces list */
+	      ifaces->len = ifaces->len * 2;
+	      ifaces->list = (jclass *) _Jv_Realloc (ifaces->list, 
+	                     ifaces->len * sizeof(jclass));
+	    }
+	  ifaces->list[ifaces->count] = iface;
+	  ifaces->count++;
+
+	  result += _Jv_GetInterfaces (klass->interfaces[i], ifaces);
+	}
+    }
+    
+  if (klass->isInterface())
+    {
+      result += klass->method_count + 1;
+    }
+  else
+    {
+      if (klass->superclass)
+        {
+	  result += _Jv_GetInterfaces (klass->superclass, ifaces);
+	}
+    }
+  return result;
+}
+
+// Fill out itable in klass, resolving method declarations in each ifaces 
+// itable_offsets is filled out with the position of each iface in itable,
+// such that itable[itable_offsets[n]] == ifaces.list[n].
 void
-_Jv_InitClass (jclass klass)
+_Jv_GenerateITable (jclass klass, _Jv_ifaces *ifaces, short *itable_offsets)
 {
-  klass->initializeClass();
+  void **itable = klass->idt->cls.itable;
+  short itable_pos = 0;
+
+  for (int i=0; i < ifaces->count; i++)
+    { 
+      jclass iface = ifaces->list[i];
+      itable_offsets[i] = itable_pos;
+      itable_pos = _Jv_AppendPartialITable (klass, iface, itable,
+                   itable_pos);
+      
+      /* Create interface dispatch table for iface */
+      if (iface->idt == NULL)
+	{
+	  iface->idt = 
+	    (_Jv_IDispatchTable *) _Jv_Malloc (sizeof (_Jv_IDispatchTable));
+
+	  // The first element of ioffsets is its length (itself included).
+	  short *ioffsets = 
+	    (short *) _Jv_Malloc (INITIAL_IOFFSETS_LEN * sizeof (short));
+	  ioffsets[0] = INITIAL_IOFFSETS_LEN;
+	  for (int i=1; i < INITIAL_IOFFSETS_LEN; i++)
+	    ioffsets[i] = -1;
+
+	  iface->idt->iface.ioffsets = ioffsets;	    
+	}
+    }
 }
 
-jboolean
-_Jv_IsInstanceOf(jobject obj, jclass cl)
+jstring
+_Jv_GetMethodString(jclass cl, _Jv_Utf8Const *name)
+{
+  char *str = NULL;
+  asprintf (&str, "%s.%s", cl->name->data, name->data);
+  return JvNewStringUTF (str);
+}
+
+// Each superinterface of a class (i.e. each interface that the class
+// directly or indirectly implements) has a corresponding "Partial
+// Interface Dispatch Table" whose size is (number of methods + 1) words.
+// The first word is a pointer to the interface (i.e. the java.lang.Class
+// instance for that interface).  The remaining words are pointers to the
+// actual methods that implement the methods declared in the interface,
+// in order of declaration.
+
+// Append partial interface dispatch table for "iface" to "itable", at
+// position itable_pos.
+// Returns the itable position at which the following partial ITable should be 
+// appended.
+short
+_Jv_AppendPartialITable (jclass klass, jclass iface, void **itable, 
+                         short pos)
+{
+  itable[pos++] = (void *) iface;
+  _Jv_Method *meth;
+  
+  for (int j=0; j < iface->method_count; j++)
+    {
+      meth = NULL;
+      for (jclass cl = klass; cl; cl = cl->getSuperclass())
+        {
+	  meth = _Jv_GetMethodLocal (cl, iface->methods[j].name,
+                 iface->methods[j].signature);
+		 
+	  if (meth)
+	    break;
+	}
+	
+      if (meth)
+        {
+	  if (java::lang::reflect::Modifier::isStatic(meth->accflags)
+	      && ! _Jv_equalUtf8Consts (iface->methods[j].name, clinit_name))
+	    JvThrow (new java::lang::IncompatibleClassChangeError
+	             (_Jv_GetMethodString (klass, meth->name)));
+	  if (java::lang::reflect::Modifier::isAbstract(meth->accflags))
+	    JvThrow (new java::lang::AbstractMethodError
+	             (_Jv_GetMethodString (klass, meth->name)));
+	  if (! java::lang::reflect::Modifier::isPublic(meth->accflags)
+	      && ! _Jv_equalUtf8Consts (iface->methods[j].name, clinit_name))
+	    JvThrow (new java::lang::IllegalAccessError
+	             (_Jv_GetMethodString (klass, meth->name)));
+
+	  itable[pos] = meth->ncode;
+	}
+      else
+        {
+	  if (! _Jv_equalUtf8Consts (iface->methods[j].name, clinit_name))
+	    JvThrow (new java::lang::NoSuchMethodError
+	             (_Jv_GetMethodString (klass, iface->methods[j].name)));
+
+          itable[pos] = NULL;
+	}
+      pos++;		
+    }
+    
+  return pos;
+}
+
+// We need to find the correct offset in the Class Interface Dispatch 
+// Table for a given interface. Once we have that, invoking an interface 
+// method just requires combining the Method's index in the interface 
+// (known at compile time) to get the correct method.  Doing a type test 
+// (cast or instanceof) is the same problem: Once we have a possible Partial 
+// Interface Dispatch Table, we just compare the first element to see if it 
+// matches the desired interface.
+
+// So how can we find the correct offset?  Our solution is to keep a vector 
+// of candiate offsets in each interface (idt->iface.ioffsets), and in each 
+// class we have an index (idt->cls.iindex) used to select the correct offset 
+// from ioffsets.
+
+static _Jv_Mutex_t iindex_mutex;
+bool iindex_mutex_initialized = false;
+
+// Calculate and return iindex for a new class. 
+// ifaces is a vector of num interfaces that the class implements.
+// offsets[j] is the offset in the interface dispatch table for the
+// interface corresponding to ifaces[j].
+// May extend the interface ioffsets if required.
+short
+_Jv_FindIIndex (jclass *ifaces, short *offsets, short num)
 {
-  return cl->isInstance(obj);
+  int i;
+  int j;
+  
+  //  Acquire a global lock to prevent itable corruption in case of multiple 
+  //  classes that implement an intersecting set of interfaces being linked
+  //  simultaneously. 
+  if (! iindex_mutex_initialized)
+    {
+      _Jv_MutexInit (&iindex_mutex);
+      iindex_mutex_initialized = true;
+    }
+  
+  _Jv_MutexLock (&iindex_mutex);
+  
+  for (i=1;; i++)  /* each potential position in ioffsets */
+    {
+      for (j=0;; j++)  /* each iface */
+        {
+	  if (j >= num)
+	    goto found;
+	  if (i > ifaces[j]->idt->iface.ioffsets[0])
+	    continue;
+	  int ioffset = ifaces[j]->idt->iface.ioffsets[i];
+	  /* We can potentially share this position with another class. */
+	  if (ioffset >= 0 && ioffset != offsets[j])
+	    break; /* Nope. Try next i. */	  
+	}
+    }
+  found:
+  for (j = 0; j < num; j++)
+    {
+      int len = ifaces[j]->idt->iface.ioffsets[0];
+      if (i >= len) 
+	{
+	  /* Resize ioffsets. */
+	  int newlen = 2 * len;
+	  if (i >= newlen)
+	    newlen = i + 3;
+	  short *old_ioffsets = ifaces[j]->idt->iface.ioffsets;
+	  short *new_ioffsets = (short *) _Jv_Realloc (old_ioffsets, 
+	                                  newlen * sizeof(short));	  
+	  new_ioffsets[0] = newlen;
+
+	  while (len < newlen)
+	    new_ioffsets[len++] = -1;
+	  
+	  ifaces[j]->idt->iface.ioffsets = new_ioffsets;
+	}
+      ifaces[j]->idt->iface.ioffsets[i] = offsets[j];
+    }
+
+  _Jv_MutexUnlock (&iindex_mutex);
+
+  return i;
 }
Index: libjava/java/lang/natClassLoader.cc
===================================================================
RCS file: /cvs/java/libgcj/libjava/java/lang/natClassLoader.cc,v
retrieving revision 1.12
diff -u -r1.12 natClassLoader.cc
--- natClassLoader.cc	1999/10/22 19:43:41	1.12
+++ natClassLoader.cc	1999/12/09 23:48:37
@@ -249,11 +249,10 @@
 	  pool->tags[index] |= JV_CONSTANT_ResolvedFlag;
 	}
     }
-
+      
   klass->notifyAll ();
 }
 
-
 //
 //  A single class can have many "initiating" class loaders,
 //  and a single "defining" class loader.  The Defining
@@ -309,7 +308,7 @@
 	    {
 	      klass = info->klass;
 	      break;
-	    }
+	    }	  
 	}
     }
 
@@ -532,7 +531,10 @@
   ret->interface_count = 0;
   ret->state = JV_STATE_NOTHING;
   ret->thread = NULL;
-
+  ret->depth = 0;
+  ret->ancestors = NULL;
+  ret->idt = NULL;
+  
   _Jv_RegisterClass (ret);
 
   return ret;
@@ -630,5 +632,3 @@
 
   return array_class;
 }
-
-
Index: libjava/prims.cc
===================================================================
RCS file: /cvs/java/libgcj/libjava/prims.cc,v
retrieving revision 1.14
diff -u -r1.14 prims.cc
--- prims.cc	1999/11/25 00:36:51	1.14
+++ prims.cc	1999/12/09 23:48:37
@@ -40,11 +40,9 @@
 #include <java/lang/ArrayIndexOutOfBoundsException.h>
 #include <java/lang/ArithmeticException.h>
 #include <java/lang/ClassFormatError.h>
-#include <java/lang/ClassCastException.h>
 #include <java/lang/NegativeArraySizeException.h>
 #include <java/lang/NullPointerException.h>
 #include <java/lang/OutOfMemoryError.h>
-#include <java/lang/ArrayStoreException.h>
 #include <java/lang/System.h>
 #include <java/lang/reflect/Modifier.h>
 #include <java/io/PrintStream.h>
@@ -258,31 +256,6 @@
 	   (java::lang::String::valueOf(bad_index)));
 }
 
-void*
-_Jv_CheckCast (jclass c, jobject obj)
-{
-  if (obj != NULL && ! c->isAssignableFrom(obj->getClass()))
-    JvThrow (new java::lang::ClassCastException);
-  return obj;
-}
-
-void
-_Jv_CheckArrayStore (jobject arr, jobject obj)
-{
-  if (obj)
-    {
-      JvAssert (arr != NULL);
-      jclass arr_class = arr->getClass();
-      JvAssert (arr_class->isArray());
-      jclass elt_class = arr_class->getComponentType();
-      jclass obj_class = obj->getClass();
-      if (! elt_class->isAssignableFrom(obj_class))
-	JvThrow (new java::lang::ArrayStoreException);
-    }
-}
-
-
-
 // Allocate some unscanned memory and throw an exception if no memory.
 void *
 _Jv_AllocBytesChecked (jsize size)
@@ -393,54 +366,6 @@
   return arr;
 }
 
-jcharArray
-JvNewCharArray (jint length)
-{
-  return (jcharArray) _Jv_NewPrimArray (JvPrimClass (char), length);
-}
-
-jbooleanArray
-JvNewBooleanArray (jint length)
-{
-  return (jbooleanArray) _Jv_NewPrimArray (JvPrimClass (boolean), length);
-}
-
-jbyteArray
-JvNewByteArray (jint length)
-{
-  return (jbyteArray) _Jv_NewPrimArray (JvPrimClass (byte), length);
-}
-
-jshortArray
-JvNewShortArray (jint length)
-{
-  return (jshortArray) _Jv_NewPrimArray (JvPrimClass (short), length);
-}
-
-jintArray
-JvNewIntArray (jint length)
-{
-  return (jintArray) _Jv_NewPrimArray (JvPrimClass (int), length);
-}
-
-jlongArray
-JvNewLongArray (jint length)
-{
-  return (jlongArray) _Jv_NewPrimArray (JvPrimClass (long), length);
-}
-
-jfloatArray
-JvNewFloatArray (jint length)
-{
-  return (jfloatArray) _Jv_NewPrimArray (JvPrimClass (float), length);
-}
-
-jdoubleArray
-JvNewDoubleArray (jint length)
-{
-  return (jdoubleArray) _Jv_NewPrimArray (JvPrimClass (double), length);
-}
-
 jobject
 _Jv_NewArray (jint type, jint size)
 {
@@ -864,6 +789,17 @@
   if (size == 0)
     size = 1;
   void *ptr = malloc ((size_t) size);
+  if (ptr == NULL)
+    JvThrow (no_memory);
+  return ptr;
+}
+
+void *
+_Jv_Realloc (void *ptr, jsize size)
+{
+  if (size == 0)
+    size = 1;
+  ptr = realloc (ptr, (size_t) size);
   if (ptr == NULL)
     JvThrow (no_memory);
   return ptr;
Index: libjava/gcj/array.h
===================================================================
RCS file: /cvs/java/libgcj/libjava/gcj/array.h,v
retrieving revision 1.2
diff -u -r1.2 array.h
--- array.h	1999/10/22 19:43:40	1.2
+++ array.h	1999/12/09 23:48:37
@@ -55,18 +55,68 @@
 typedef JArray<jdouble> *jdoubleArray;
 typedef JArray<jstring> *jstringArray;
 
-extern "C" jbooleanArray JvNewBooleanArray (jint length);
-extern "C" jbyteArray JvNewByteArray (jint length);
-extern "C" jcharArray JvNewCharArray (jint length);
-extern "C" jshortArray JvNewShortArray (jint length);
-extern "C" jintArray JvNewIntArray (jint length);
-extern "C" jlongArray JvNewLongArray (jint length);
-extern "C" jfloatArray JvNewFloatArray (jint length);
-extern "C" jdoubleArray JvNewDoubleArray (jint length);
+extern class _Jv_PrimClass _Jv_byteClass, _Jv_shortClass, _Jv_intClass,
+  _Jv_longClass, _Jv_booleanClass, _Jv_charClass, _Jv_floatClass,
+  _Jv_doubleClass, _Jv_voidClass;
+#define JvPrimClass(TYPE) ((jclass) & _Jv_##TYPE##Class)
+
 extern "C" jobjectArray _Jv_NewObjectArray(jsize length, jclass, jobject init);
+extern "C" jobject _Jv_NewPrimArray (jclass eltype, jint count);
+
+extern inline jobjectArray 
+JvNewObjectArray (jsize length, jclass cls, jobject init)
+{ 
+  return _Jv_NewObjectArray (length, cls, init); 
+}
+
+extern inline jcharArray 
+JvNewCharArray (jint length)
+{
+  return (jcharArray) _Jv_NewPrimArray (JvPrimClass (char), length);
+}
+
+extern inline jbooleanArray 
+JvNewBooleanArray (jint length)
+{
+  return (jbooleanArray) _Jv_NewPrimArray (JvPrimClass (boolean), length);
+}
+
+extern inline jbyteArray 
+JvNewByteArray (jint length)
+{
+  return (jbyteArray) _Jv_NewPrimArray (JvPrimClass (byte), length);
+}
+
+extern inline jshortArray 
+JvNewShortArray (jint length)
+{
+  return (jshortArray) _Jv_NewPrimArray (JvPrimClass (short), length);
+}
+
+extern inline jintArray 
+JvNewIntArray (jint length)
+{
+  return (jintArray) _Jv_NewPrimArray (JvPrimClass (int), length);
+}
+
+extern inline jlongArray 
+JvNewLongArray (jint length)
+{
+  return (jlongArray) _Jv_NewPrimArray (JvPrimClass (long), length);
+}
+
+extern inline jfloatArray 
+JvNewFloatArray (jint length)
+{
+  return (jfloatArray) _Jv_NewPrimArray (JvPrimClass (float), length);
+}
+
+extern inline jdoubleArray 
+JvNewDoubleArray (jint length)
+{
+  return (jdoubleArray) _Jv_NewPrimArray (JvPrimClass (double), length);
+}
 
-inline jobjectArray JvNewObjectArray (jsize length, jclass cls, jobject init)
-{ return _Jv_NewObjectArray (length, cls, init); }
 
 extern "C" jstringArray JvConvertArgv(int argc, const char **argv);
 
Index: libjava/gcj/cni.h
===================================================================
RCS file: /cvs/java/libgcj/libjava/gcj/cni.h,v
retrieving revision 1.2
diff -u -r1.2 cni.h
--- cni.h	1999/11/19 19:13:42	1.2
+++ cni.h	1999/12/09 23:48:37
@@ -93,11 +93,6 @@
   return _Jv_NewStringUTF (bytes);
 }
 
-extern class _Jv_PrimClass _Jv_byteClass, _Jv_shortClass, _Jv_intClass,
-  _Jv_longClass, _Jv_booleanClass, _Jv_charClass, _Jv_floatClass,
-  _Jv_doubleClass, _Jv_voidClass;
-#define JvPrimClass(TYPE) ((jclass) & _Jv_##TYPE##Class)
-
 class JvSynchronize
 {
 private:
Index: libjava/gcj/javaprims.h
===================================================================
RCS file: /cvs/java/libgcj/libjava/gcj/javaprims.h,v
retrieving revision 1.3
diff -u -r1.3 javaprims.h
--- javaprims.h	1999/12/06 06:33:56	1.3
+++ javaprims.h	1999/12/09 23:48:37
@@ -273,6 +273,7 @@
 extern "C" void _Jv_Throw (void *) __attribute__ ((__noreturn__));
 extern "C" void _Jv_Sjlj_Throw (void *) __attribute__ ((__noreturn__));
 extern "C" void* _Jv_Malloc (jsize) __attribute__((__malloc__));
+extern "C" void* _Jv_Realloc (void *, jsize);
 extern "C" void _Jv_Free (void*);
 
 typedef unsigned short _Jv_ushort __attribute__((__mode__(__HI__)));
Index: libjava/include/jvm.h
===================================================================
RCS file: /cvs/java/libgcj/libjava/include/jvm.h,v
retrieving revision 1.8
diff -u -r1.8 jvm.h
--- jvm.h	1999/12/06 06:33:56	1.8
+++ jvm.h	1999/12/09 23:48:37
@@ -150,8 +150,8 @@
 extern "C" jobject _Jv_NewMultiArray (jclass klass, jint dims, ...)
   __attribute__((__malloc__));
 extern "C" void *_Jv_CheckCast (jclass klass, jobject obj);
-extern "C" void *_Jv_LookupInterfaceMethod (jclass klass, Utf8Const *name,
-					    Utf8Const *signature);
+extern "C" void *_Jv_LookupInterfaceMethod (jclass klass, jclass iface, 
+                                            int meth_idx);
 extern "C" void _Jv_CheckArrayStore (jobject array, jobject obj);
 extern "C" void _Jv_RegisterClass (jclass klass);
 extern "C" void _Jv_RegisterClasses (jclass *classes);

-------------- next part --------------
A non-text attachment was scrubbed...
Name: idispatch-test.tar
Type: application/x-tar
Size: 20480 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/java-patches/attachments/19991209/cff7a914/attachment.tar>


More information about the Java-patches mailing list