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 */
013 package org.jikesrvm.classloader;
014
015 import org.jikesrvm.ArchitectureSpecific.CodeArray;
016 import org.jikesrvm.ArchitectureSpecific.InterfaceMethodConflictResolver;
017 import org.jikesrvm.VM;
018 import org.jikesrvm.SizeConstants;
019 import org.jikesrvm.mm.mminterface.MemoryManager;
020 import org.jikesrvm.objectmodel.IMT;
021 import org.jikesrvm.objectmodel.ITable;
022 import org.jikesrvm.objectmodel.ITableArray;
023 import org.jikesrvm.objectmodel.ObjectModel;
024 import org.jikesrvm.objectmodel.TIB;
025 import org.jikesrvm.objectmodel.TIBLayoutConstants;
026 import org.jikesrvm.runtime.Entrypoints;
027 import org.jikesrvm.runtime.Magic;
028 import org.jikesrvm.runtime.RuntimeEntrypoints;
029 import 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 */
040 public class InterfaceInvocation implements TIBLayoutConstants, SizeConstants {
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 * @return an IMTDict that describes the IMT we need to build for the class.
190 */
191 private static IMTDict buildIMTDict(RVMClass klass, RVMClass[] interfaces) {
192 IMTDict d = new IMTDict(klass);
193 for (RVMClass i : interfaces) {
194 RVMMethod[] interfaceMethods = i.getDeclaredMethods();
195 for (RVMMethod im : interfaceMethods) {
196 if (im.isClassInitializer()) continue;
197 if (VM.VerifyAssertions) VM._assert(im.isPublic() && im.isAbstract());
198 InterfaceMethodSignature sig = InterfaceMethodSignature.findOrCreate(im.getMemberRef());
199 RVMMethod vm = klass.findVirtualMethod(im.getName(), im.getDescriptor());
200 // NOTE: if there is some error condition, then we are playing a dirty trick and
201 // pretending that a static method of RuntimeEntrypoints is a virtual method.
202 // Since the methods in question take no arguments, we can get away with this.
203 if (vm == null || vm.isAbstract()) {
204 vm = Entrypoints.raiseAbstractMethodError;
205 } else if (!vm.isPublic()) {
206 vm = Entrypoints.raiseIllegalAccessError;
207 }
208 d.addElement(sig, vm);
209 }
210 }
211 return d;
212 }
213
214 /**
215 * Populate an indirect IMT for C using the IMTDict d
216 */
217 private static void populateIMT(RVMClass klass, IMTDict d) {
218 TIB tib = klass.getTypeInformationBlock();
219 IMT IMT = MemoryManager.newIMT();
220 klass.setIMT(IMT);
221 d.populateIMT(klass, tib, IMT);
222 tib.setImt(IMT);
223 }
224
225 /**
226 * Build and install an iTable for the given class interface pair
227 * (used for iTable miss on searched iTables).
228 */
229 private static void installITable(RVMClass C, RVMClass I) {
230 TIB tib = C.getTypeInformationBlock();
231 ITableArray iTables = tib.getITableArray();
232
233 if (iTables == null) {
234 iTables = MemoryManager.newITableArray(2);
235 tib.setITableArray(iTables);
236 } else {
237 for(int i=0; i < iTables.length(); i++) {
238 if (iTables.get(i).isFor(I)) {
239 return; // some other thread just built the iTable
240 }
241 }
242 ITableArray tmp = MemoryManager.newITableArray(iTables.length() + 1);
243 for(int i=0; i < iTables.length(); i++) {
244 tmp.set(i, iTables.get(i));
245 }
246 iTables = tmp;
247 tib.setITableArray(iTables);
248 }
249 if (VM.VerifyAssertions) VM._assert(iTables.get(iTables.length() - 1) == null);
250 ITable iTable = buildITable(C, I);
251 iTables.set(iTables.length() - 1, iTable);
252 // iTables[0] is a move to front cache; fill it here so we can
253 // assume it always contains some iTable.
254 iTables.set(0, iTable);
255 }
256
257 /**
258 * Build a single ITable for the pair of class C and interface I
259 */
260 private static ITable buildITable(RVMClass C, RVMClass I) {
261 RVMMethod[] interfaceMethods = I.getDeclaredMethods();
262 TIB tib = C.getTypeInformationBlock();
263 ITable iTable = MemoryManager.newITable(interfaceMethods.length + 1);
264 iTable.set(0, I);
265 for (RVMMethod im : interfaceMethods) {
266 if (im.isClassInitializer()) continue;
267 if (VM.VerifyAssertions) VM._assert(im.isPublic() && im.isAbstract());
268 RVMMethod vm = C.findVirtualMethod(im.getName(), im.getDescriptor());
269 // NOTE: if there is some error condition, then we are playing a dirty trick and
270 // pretending that a static method of RuntimeEntrypoints is a virtual method.
271 // Since the methods in question take no arguments, we can get away with this.
272 if (vm == null || vm.isAbstract()) {
273 vm = Entrypoints.raiseAbstractMethodError;
274 } else if (!vm.isPublic()) {
275 vm = Entrypoints.raiseIllegalAccessError;
276 }
277 if (vm.isStatic()) {
278 vm.compile();
279 iTable.set(getITableIndex(I, im.getName(), im.getDescriptor()), vm.getCurrentEntryCodeArray());
280 } else {
281 iTable.set(getITableIndex(I, im.getName(), im.getDescriptor()), tib.getVirtualMethod(vm.getOffset()));
282 }
283 }
284 return iTable;
285 }
286
287 /*
288 * PART III: Supporting low-level code for manipulating IMTs and ITables
289 */
290
291 /**
292 * Return the index of the interface method m in the itable
293 */
294 public static int getITableIndex(RVMClass klass, Atom mname, Atom mdesc) {
295 if (VM.VerifyAssertions) VM._assert(VM.BuildForITableInterfaceInvocation);
296 if (VM.VerifyAssertions) VM._assert(klass.isInterface());
297 RVMMethod[] methods = klass.getDeclaredMethods();
298 for (int i = 0; i < methods.length; i++) {
299 if (methods[i].getName() == mname && methods[i].getDescriptor() == mdesc) {
300 return i + 1;
301 }
302 }
303 return -1;
304 }
305
306 /**
307 * If there is an an IMT or ITable entry that contains
308 * compiled code for the argument method, then update it to
309 * contain the current compiled code for the method.
310 *
311 * @param klass the RVMClass who's IMT/ITable is being reset
312 * @param m the method that needs to be updated.
313 */
314 public static void updateTIBEntry(RVMClass klass, RVMMethod m) {
315 TIB tib = klass.getTypeInformationBlock();
316 if (VM.BuildForIMTInterfaceInvocation) {
317 RVMMethod[] map = klass.noIMTConflictMap;
318 if (map != null) {
319 for (int i = 0; i < IMT_METHOD_SLOTS; i++) {
320 if (map[i] == m) {
321 IMT imt = tib.getImt();
322 imt.set(i, m.getCurrentEntryCodeArray());
323 return; // all done -- a method is in at most 1 IMT slot
324 }
325 }
326 }
327 } else if (VM.BuildForITableInterfaceInvocation) {
328 if (tib.getITableArray() != null) {
329 ITableArray iTables = tib.getITableArray();
330 Atom name = m.getName();
331 Atom desc = m.getDescriptor();
332 for (int i=0; i< iTables.length(); i++) {
333 ITable iTable = iTables.get(i);
334 if (iTable != null) {
335 RVMClass I = iTable.getInterfaceClass();
336 RVMMethod[] interfaceMethods = I.getDeclaredMethods();
337 for (RVMMethod im : interfaceMethods) {
338 if (im.getName() == name && im.getDescriptor() == desc) {
339 iTable.set(getITableIndex(I, name, desc), m.getCurrentEntryCodeArray());
340 }
341 }
342 }
343 }
344 }
345 }
346 }
347
348 /*
349 * Helper class used for IMT construction
350 */
351 private static final class IMTDict {
352 private final RVMClass klass;
353 private final Link[] links;
354
355 IMTDict(RVMClass c) {
356 klass = c;
357 links = new Link[IMT_METHOD_SLOTS];
358 }
359
360 // Convert from the internally visible IMTOffset to an index
361 // into my internal data structure.
362 private int getIndex(InterfaceMethodSignature sig) {
363 int idx = sig.getIMTOffset().toInt() >> LOG_BYTES_IN_ADDRESS;
364 return idx;
365 }
366
367 // count the number of signatures in the given IMT slot
368 private int populationCount(int index) {
369 Link p = links[index];
370 int count = 0;
371 while (p != null) {
372 count++;
373 p = p.next;
374 }
375 return count;
376 }
377
378 private RVMMethod getSoleTarget(int index) {
379 if (VM.VerifyAssertions) VM._assert(populationCount(index) == 1);
380 return links[index].method;
381 }
382
383 // Add an element to the IMT dictionary (does nothing if already there)
384 public void addElement(InterfaceMethodSignature sig, RVMMethod m) {
385 int index = getIndex(sig);
386 Link p = links[index];
387 if (p == null || p.signature.getId() > sig.getId()) {
388 links[index] = new Link(sig, m, p);
389 } else {
390 Link q = p;
391 while (p != null && p.signature.getId() <= sig.getId()) {
392 if (p.signature.getId() == sig.getId()) return; // already there so nothing to do.
393 q = p;
394 p = p.next;
395 }
396 q.next = new Link(sig, m, p);
397 }
398 }
399
400 // populate the
401 public void populateIMT(RVMClass klass, TIB tib, IMT imt) {
402 for (int slot = 0; slot < links.length; slot++) {
403 int count = populationCount(slot);
404 if (count == 0) {
405 Entrypoints.raiseAbstractMethodError.compile();
406 set(tib, imt, slot, Entrypoints.raiseAbstractMethodError.getCurrentEntryCodeArray());
407 } else if (count == 1) {
408 RVMMethod target = getSoleTarget(slot);
409 if (target.isStatic()) {
410 target.compile();
411 set(tib, imt, slot, target.getCurrentEntryCodeArray());
412 } else {
413 set(tib, imt, slot, tib.getVirtualMethod(target.getOffset()));
414 if (klass.noIMTConflictMap == null) {
415 klass.noIMTConflictMap = new RVMMethod[IMT_METHOD_SLOTS];
416 }
417 klass.noIMTConflictMap[slot] = target;
418 }
419 } else {
420 RVMMethod[] targets = new RVMMethod[count];
421 int[] sigIds = new int[count];
422 int idx = 0;
423 for (Link p = links[slot]; p != null; idx++, p = p.next) {
424 targets[idx] = p.method;
425 sigIds[idx] = p.signature.getId();
426 }
427 CodeArray conflictResolutionStub = InterfaceMethodConflictResolver.createStub(sigIds, targets);
428 klass.addCachedObject(Magic.codeArrayAsObject(conflictResolutionStub));
429 set(tib, imt, slot, conflictResolutionStub);
430 }
431 }
432 }
433
434 private void set(TIB tib, IMT imt, int extSlot, CodeArray value) {
435 imt.set(extSlot, value);
436 }
437
438 private static final class Link {
439 final InterfaceMethodSignature signature;
440 final RVMMethod method;
441 Link next;
442
443 Link(InterfaceMethodSignature sig, RVMMethod m, Link n) {
444 signature = sig;
445 method = m;
446 next = n;
447 }
448 }
449 }
450 }