001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.classloader;
014
015import static org.jikesrvm.objectmodel.TIBLayoutConstants.IMT_METHOD_SLOTS;
016import static org.jikesrvm.runtime.UnboxedSizeConstants.LOG_BYTES_IN_ADDRESS;
017
018import org.jikesrvm.VM;
019import org.jikesrvm.compilers.common.CodeArray;
020import org.jikesrvm.mm.mminterface.MemoryManager;
021import org.jikesrvm.objectmodel.IMT;
022import org.jikesrvm.objectmodel.ITable;
023import org.jikesrvm.objectmodel.ITableArray;
024import org.jikesrvm.objectmodel.ObjectModel;
025import org.jikesrvm.objectmodel.TIB;
026import org.jikesrvm.runtime.Entrypoints;
027import org.jikesrvm.runtime.Magic;
028import org.jikesrvm.runtime.RuntimeEntrypoints;
029import org.vmmagic.pragma.Entrypoint;
030
031/**
032 * Runtime system mechanisms and data structures to implement interface invocation.
033 * <p>
034 * We support two mechanisms:
035 * <pre>
036 *   IMT-based (Alpern, Cocchi, Fink, Grove, and Lieber OOPSLA'01).
037 *   ITable-based (searched at dispatch time with 1 entry move-to-front cache)
038  * </pre>
039 */
040public class InterfaceInvocation {
041
042  /*
043   * PART I: runtime routines to implement the invokeinterface bytecode.
044   *         these routines are called from the generated code
045   *         as part of the interface invocation sequence.
046   */
047
048  /**
049   * Resolve an interface method call.
050   * This routine is never called by the IMT-based dispatching code.
051   * It is only called for directly indexed ITables when the table
052   * index was unknown at compile time (i.e. the target Interface was not loaded).
053   *
054   * @param target object to which interface method is to be applied
055   * @param mid id of the MemberReference for the target interface method.
056   * @return machine code corresponding to desired interface method
057   */
058  @Entrypoint
059  public static CodeArray invokeInterface(Object target, int mid) throws IncompatibleClassChangeError {
060
061    MethodReference mref = MemberReference.getMemberRef(mid).asMethodReference();
062    RVMMethod sought = mref.resolveInterfaceMethod();
063    RVMClass I = sought.getDeclaringClass();
064    RVMClass C = Magic.getObjectType(target).asClass();
065    if (VM.BuildForITableInterfaceInvocation) {
066      TIB tib = C.getTypeInformationBlock();
067      ITable iTable = findITable(tib, I.getInterfaceId());
068      return iTable.getCode(getITableIndex(I, mref.getName(), mref.getDescriptor()));
069    } else {
070      if (!RuntimeEntrypoints.isAssignableWith(I, C)) throw new IncompatibleClassChangeError();
071      RVMMethod found = C.findVirtualMethod(sought.getName(), sought.getDescriptor());
072      if (found == null) throw new IncompatibleClassChangeError();
073      return found.getCurrentEntryCodeArray();
074    }
075  }
076
077  /**
078   * Return a reference to the itable for a given class, interface pair
079   * We might not have created the iTable yet, in which case we will do that and then return it.
080   *
081   * @param tib the TIB for the class
082   * @param id interface id of the interface sought (NOT dictionary id!!)
083   * @return iTable for desired interface
084   */
085  @Entrypoint
086  public static ITable findITable(TIB tib, int id) throws IncompatibleClassChangeError {
087    ITableArray iTables = tib.getITableArray();
088    // Search for the right ITable
089    RVMType I = RVMClass.getInterface(id);
090    if (iTables != null) {
091      // check the cache at slot 0
092      ITable iTable = iTables.get(0);
093      if (iTable.isFor(I)) {
094        return iTable; // cache hit :)
095      }
096
097      // cache miss :(
098      // Have to search the 'real' entries for the iTable
099      for (int i = 1; i < iTables.length(); i++) {
100        iTable = iTables.get(i);
101        if (iTable.isFor(I)) {
102          // found it; update cache
103          iTables.set(0, iTable);
104          return iTable;
105        }
106      }
107    }
108
109    // Didn't find the itable, so we don't yet know if
110    // the class implements the interface. :(((
111    // Therefore, we need to establish that and then
112    // look for the iTable again.
113    RVMClass C = (RVMClass) tib.getType();
114    if (!RuntimeEntrypoints.isAssignableWith(I, C)) throw new IncompatibleClassChangeError();
115    synchronized (C) {
116      installITable(C, (RVMClass) I);
117    }
118    ITable iTable = findITable(tib, id);
119    if (VM.VerifyAssertions) VM._assert(iTable != null);
120    return iTable;
121  }
122
123  /**
124   * <code>mid</code> is the dictionary id of an interface method we are trying to invoke
125   * <code>RHStib</code> is the TIB of an object on which we are attempting to invoke it.
126   *
127   * We were unable to resolve the member reference at compile time.
128   * Therefore we must resolve it now and then call invokeinterfaceImplementsTest
129   * with the right LHSclass.
130   *
131   * @param mid     Dictionary id of the {@link MemberReference} for the target interface method.
132   * @param rhsObject  The object on which we are attempting to invoke the interface method
133   */
134  @Entrypoint
135  public static void unresolvedInvokeinterfaceImplementsTest(int mid, Object rhsObject)
136      throws IncompatibleClassChangeError {
137    RVMMethod sought = MemberReference.getMemberRef(mid).asMethodReference().resolveInterfaceMethod();
138    RVMClass LHSclass = sought.getDeclaringClass();
139    if (!LHSclass.isResolved()) {
140      LHSclass.resolve();
141    }
142    /* If the object is not null, ensure that it implements the interface.
143     * If it is null, then we return to our caller and let them raise the
144     * null pointer exception when they attempt to get the object's TIB so
145     * they can actually make the interface call.
146     */
147    if (rhsObject != null) {
148      TIB RHStib = ObjectModel.getTIB(rhsObject);
149      if (LHSclass.isInterface() && DynamicTypeCheck.instanceOfInterface(LHSclass, RHStib)) return;
150      // Raise an IncompatibleClassChangeError.
151      throw new IncompatibleClassChangeError();
152    }
153  }
154
155  /*
156  * PART II: Code to initialize the interface dispatching data structures.
157  *          Called during the instantiate step of class loading.
158  *          Preconditions:
159  *            (1) the caller has the lock on the RVMClass object
160  *                whose data structures and being initialized.
161  *            (2) the VMT for the class contains valid code.
162  */
163
164  /**
165   * Main entrypoint called from RVMClass.instantiate to
166   * initialize the interface dispatching data structures for
167   * the given class.
168   *
169   * @param klass the RVMClass to initialize the dispatch structures for.
170   */
171  public static void initializeDispatchStructures(RVMClass klass) {
172    // if klass is abstract, we'll never use the dispatching structures.
173    if (klass.isAbstract()) return;
174    RVMClass[] interfaces = klass.getAllImplementedInterfaces();
175    if (interfaces.length != 0) {
176      if (VM.BuildForIMTInterfaceInvocation) {
177        IMTDict d = buildIMTDict(klass, interfaces);
178        populateIMT(klass, d);
179      }
180    }
181  }
182
183  /**
184   * Build up a description of the IMT contents for the given class.
185   * NOTE: this structure is only used during class loading, so
186   *       we don't have to worry about making it space efficient.
187   *
188   * @param klass the RVMClass whose IMT we are going to build.
189   * @param interfaces the interfaces that the class implements
190   * @return an IMTDict that describes the IMT we need to build for the class.
191   */
192  private static IMTDict buildIMTDict(RVMClass klass, RVMClass[] interfaces) {
193    IMTDict d = new IMTDict(klass);
194    for (RVMClass i : interfaces) {
195      RVMMethod[] interfaceMethods = i.getDeclaredMethods();
196      for (RVMMethod im : interfaceMethods) {
197        if (im.isClassInitializer()) continue;
198        if (VM.VerifyAssertions) VM._assert(im.isPublic() && im.isAbstract());
199        InterfaceMethodSignature sig = InterfaceMethodSignature.findOrCreate(im.getMemberRef());
200        RVMMethod vm = klass.findVirtualMethod(im.getName(), im.getDescriptor());
201        // NOTE: if there is some error condition, then we are playing a dirty trick and
202        //       pretending that a static method of RuntimeEntrypoints is a virtual method.
203        //       Since the methods in question take no arguments, we can get away with this.
204        if (vm == null || vm.isAbstract()) {
205          vm = Entrypoints.raiseAbstractMethodError;
206        } else if (!vm.isPublic()) {
207          vm = Entrypoints.raiseIllegalAccessError;
208        }
209        d.addElement(sig, vm);
210      }
211    }
212    return d;
213  }
214
215  private static void populateIMT(RVMClass klass, IMTDict d) {
216    TIB tib = klass.getTypeInformationBlock();
217    IMT IMT = MemoryManager.newIMT();
218    klass.setIMT(IMT);
219    d.populateIMT(klass, tib, IMT);
220    tib.setImt(IMT);
221  }
222
223  private static void installITable(RVMClass C, RVMClass I) {
224    TIB tib = C.getTypeInformationBlock();
225    ITableArray iTables = tib.getITableArray();
226
227    if (iTables == null) {
228      iTables = MemoryManager.newITableArray(2);
229      tib.setITableArray(iTables);
230    } else {
231      for (int i = 0; i < iTables.length(); i++) {
232        if (iTables.get(i).isFor(I)) {
233          return; // some other thread just built the iTable
234        }
235      }
236      ITableArray tmp = MemoryManager.newITableArray(iTables.length() + 1);
237      for (int i = 0; i < iTables.length(); i++) {
238        tmp.set(i, iTables.get(i));
239      }
240      iTables = tmp;
241      tib.setITableArray(iTables);
242    }
243    if (VM.VerifyAssertions) VM._assert(iTables.get(iTables.length() - 1) == null);
244    ITable iTable = buildITable(C, I);
245    iTables.set(iTables.length() - 1, iTable);
246    // iTables[0] is a move to front cache; fill it here so we can
247    // assume it always contains some iTable.
248    iTables.set(0, iTable);
249  }
250
251  private static ITable buildITable(RVMClass C, RVMClass I) {
252    RVMMethod[] interfaceMethods = I.getDeclaredMethods();
253    TIB tib = C.getTypeInformationBlock();
254    ITable iTable = MemoryManager.newITable(interfaceMethods.length + 1);
255    iTable.set(0, I);
256    for (RVMMethod im : interfaceMethods) {
257      if (im.isClassInitializer()) continue;
258      if (VM.VerifyAssertions) VM._assert(im.isPublic() && im.isAbstract());
259      RVMMethod vm = C.findVirtualMethod(im.getName(), im.getDescriptor());
260      // NOTE: if there is some error condition, then we are playing a dirty trick and
261      //       pretending that a static method of RuntimeEntrypoints is a virtual method.
262      //       Since the methods in question take no arguments, we can get away with this.
263      if (vm == null || vm.isAbstract()) {
264        vm = Entrypoints.raiseAbstractMethodError;
265      } else if (!vm.isPublic()) {
266        vm = Entrypoints.raiseIllegalAccessError;
267      }
268      if (vm.isStatic()) {
269        vm.compile();
270        iTable.set(getITableIndex(I, im.getName(), im.getDescriptor()), vm.getCurrentEntryCodeArray());
271      } else {
272        iTable.set(getITableIndex(I, im.getName(), im.getDescriptor()), tib.getVirtualMethod(vm.getOffset()));
273      }
274    }
275    return iTable;
276  }
277
278  /*
279  * PART III: Supporting low-level code for manipulating IMTs and ITables
280  */
281
282  /**
283   * @param klass the interface class
284   * @param mname method name
285   * @param mdesc method descriptor
286   * @return the index of the interface method m in the itable or -1 if none found
287   */
288  public static int getITableIndex(RVMClass klass, Atom mname, Atom mdesc) {
289    if (VM.VerifyAssertions) VM._assert(VM.BuildForITableInterfaceInvocation);
290    if (VM.VerifyAssertions) VM._assert(klass.isInterface());
291    RVMMethod[] methods = klass.getDeclaredMethods();
292    for (int i = 0; i < methods.length; i++) {
293      if (methods[i].getName() == mname && methods[i].getDescriptor() == mdesc) {
294        return i + 1;
295      }
296    }
297    return -1;
298  }
299
300  /**
301   * If there is an an IMT or ITable entry that contains
302   * compiled code for the argument method, then update it to
303   * contain the current compiled code for the method.
304   *
305   * @param klass the RVMClass who's IMT/ITable is being reset
306   * @param m the method that needs to be updated.
307   */
308  public static void updateTIBEntry(RVMClass klass, RVMMethod m) {
309    TIB tib = klass.getTypeInformationBlock();
310    if (VM.BuildForIMTInterfaceInvocation) {
311      RVMMethod[] map = klass.noIMTConflictMap;
312      if (map != null) {
313        for (int i = 0; i < IMT_METHOD_SLOTS; i++) {
314          if (map[i] == m) {
315            IMT imt = tib.getImt();
316            imt.set(i, m.getCurrentEntryCodeArray());
317            return; // all done -- a method is in at most 1 IMT slot
318          }
319        }
320      }
321    } else if (VM.BuildForITableInterfaceInvocation) {
322      if (tib.getITableArray() != null) {
323        ITableArray iTables = tib.getITableArray();
324        Atom name = m.getName();
325        Atom desc = m.getDescriptor();
326        for (int i = 0; i < iTables.length(); i++) {
327          ITable iTable = iTables.get(i);
328          if (iTable != null) {
329            RVMClass I = iTable.getInterfaceClass();
330            RVMMethod[] interfaceMethods = I.getDeclaredMethods();
331            for (RVMMethod im : interfaceMethods) {
332              if (im.getName() == name && im.getDescriptor() == desc) {
333                iTable.set(getITableIndex(I, name, desc), m.getCurrentEntryCodeArray());
334              }
335            }
336          }
337        }
338      }
339    }
340  }
341
342  /*
343   * Helper class used for IMT construction
344   */
345  private static final class IMTDict {
346    private final RVMClass klass;
347    private final Link[] links;
348
349    IMTDict(RVMClass c) {
350      klass = c;
351      links = new Link[IMT_METHOD_SLOTS];
352    }
353
354    // Convert from the internally visible IMTOffset to an index
355    // into my internal data structure.
356    private int getIndex(InterfaceMethodSignature sig) {
357      int idx = sig.getIMTOffset().toInt() >> LOG_BYTES_IN_ADDRESS;
358      return idx;
359    }
360
361    // count the number of signatures in the given IMT slot
362    private int populationCount(int index) {
363      Link p = links[index];
364      int count = 0;
365      while (p != null) {
366        count++;
367        p = p.next;
368      }
369      return count;
370    }
371
372    private RVMMethod getSoleTarget(int index) {
373      if (VM.VerifyAssertions) VM._assert(populationCount(index) == 1);
374      return links[index].method;
375    }
376
377    // Add an element to the IMT dictionary (does nothing if already there)
378    public void addElement(InterfaceMethodSignature sig, RVMMethod m) {
379      int index = getIndex(sig);
380      Link p = links[index];
381      if (p == null || p.signature.getId() > sig.getId()) {
382        links[index] = new Link(sig, m, p);
383      } else {
384        Link q = p;
385        while (p != null && p.signature.getId() <= sig.getId()) {
386          if (p.signature.getId() == sig.getId()) return; // already there so nothing to do.
387          q = p;
388          p = p.next;
389        }
390        q.next = new Link(sig, m, p);
391      }
392    }
393
394    // populate the
395    public void populateIMT(RVMClass klass, TIB tib, IMT imt) {
396      for (int slot = 0; slot < links.length; slot++) {
397        int count = populationCount(slot);
398        if (count == 0) {
399          Entrypoints.raiseAbstractMethodError.compile();
400          set(tib, imt, slot, Entrypoints.raiseAbstractMethodError.getCurrentEntryCodeArray());
401        } else if (count == 1) {
402          RVMMethod target = getSoleTarget(slot);
403          if (target.isStatic()) {
404            target.compile();
405            set(tib, imt, slot, target.getCurrentEntryCodeArray());
406          } else {
407            set(tib, imt, slot, tib.getVirtualMethod(target.getOffset()));
408            if (klass.noIMTConflictMap == null) {
409              klass.noIMTConflictMap = new RVMMethod[IMT_METHOD_SLOTS];
410            }
411            klass.noIMTConflictMap[slot] = target;
412          }
413        } else {
414          RVMMethod[] targets = new RVMMethod[count];
415          int[] sigIds = new int[count];
416          int idx = 0;
417          for (Link p = links[slot]; p != null; idx++, p = p.next) {
418            targets[idx] = p.method;
419            sigIds[idx] = p.signature.getId();
420          }
421          CodeArray conflictResolutionStub;
422          if (VM.BuildForIA32) {
423            conflictResolutionStub = org.jikesrvm.ia32.InterfaceMethodConflictResolver.createStub(sigIds, targets);
424          } else {
425            if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
426            conflictResolutionStub = org.jikesrvm.ppc.InterfaceMethodConflictResolver.createStub(sigIds, targets);
427          }
428
429          klass.addCachedObject(Magic.codeArrayAsObject(conflictResolutionStub));
430          set(tib, imt, slot, conflictResolutionStub);
431        }
432      }
433    }
434
435    private void set(TIB tib, IMT imt, int extSlot, CodeArray value) {
436      imt.set(extSlot, value);
437    }
438
439    private static final class Link {
440      final InterfaceMethodSignature signature;
441      final RVMMethod method;
442      Link next;
443
444      Link(InterfaceMethodSignature sig, RVMMethod m, Link n) {
445        signature = sig;
446        method = m;
447        next = n;
448      }
449    }
450  }
451}