1 /*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 /*
17 * Array objects.
18 */
19 #include "Dalvik.h"
20
21 #include <stdlib.h>
22 #include <stddef.h>
23 #include <limits.h>
24
25 /* width of an object reference, for arrays of objects */
26 static size_t kObjectArrayRefWidth = sizeof(Object*);
27
28 static ClassObject* createArrayClass(const char* descriptor, Object* loader);
29
30 /*
31 * Allocate space for a new array object. This is the lowest-level array
32 * allocation function.
33 *
34 * Pass in the array class and the width of each element.
35 *
36 * On failure, returns NULL with an exception raised.
37 */
allocArray(ClassObject * arrayClass,size_t length,size_t elemWidth,int allocFlags)38 static ArrayObject* allocArray(ClassObject* arrayClass, size_t length,
39 size_t elemWidth, int allocFlags)
40 {
41 assert(arrayClass != NULL);
42 assert(arrayClass->descriptor != NULL);
43 assert(arrayClass->descriptor[0] == '[');
44 assert(length <= 0x7fffffff);
45 assert(elemWidth > 0);
46 assert(elemWidth <= 8);
47 assert((elemWidth & (elemWidth - 1)) == 0);
48 size_t elementShift = sizeof(size_t) * CHAR_BIT - 1 - CLZ(elemWidth);
49 size_t elementSize = length << elementShift;
50 size_t headerSize = OFFSETOF_MEMBER(ArrayObject, contents);
51 size_t totalSize = elementSize + headerSize;
52 if (elementSize >> elementShift != length || totalSize < elementSize) {
53 std::string descriptor(dvmHumanReadableDescriptor(arrayClass->descriptor));
54 dvmThrowExceptionFmt(gDvm.exOutOfMemoryError,
55 "%s of length %zd exceeds the VM limit", descriptor.c_str(), length);
56 return NULL;
57 }
58 ArrayObject* newArray = (ArrayObject*)dvmMalloc(totalSize, allocFlags);
59 if (newArray != NULL) {
60 DVM_OBJECT_INIT(newArray, arrayClass);
61 newArray->length = length;
62 dvmTrackAllocation(arrayClass, totalSize);
63 }
64 return newArray;
65 }
66
67 /*
68 * Create a new array, given an array class. The class may represent an
69 * array of references or primitives.
70 */
dvmAllocArrayByClass(ClassObject * arrayClass,size_t length,int allocFlags)71 ArrayObject* dvmAllocArrayByClass(ClassObject* arrayClass,
72 size_t length, int allocFlags)
73 {
74 const char* descriptor = arrayClass->descriptor;
75
76 assert(descriptor[0] == '['); /* must be array class */
77 if (descriptor[1] != '[' && descriptor[1] != 'L') {
78 /* primitive array */
79 assert(descriptor[2] == '\0');
80 return dvmAllocPrimitiveArray(descriptor[1], length, allocFlags);
81 } else {
82 return allocArray(arrayClass, length, kObjectArrayRefWidth,
83 allocFlags);
84 }
85 }
86
87 /*
88 * Find the array class for "elemClassObj", which could itself be an
89 * array class.
90 */
dvmFindArrayClassForElement(ClassObject * elemClassObj)91 ClassObject* dvmFindArrayClassForElement(ClassObject* elemClassObj)
92 {
93 ClassObject* arrayClass;
94
95 assert(elemClassObj != NULL);
96
97 /* Simply prepend "[" to the descriptor. */
98 int nameLen = strlen(elemClassObj->descriptor);
99 char className[nameLen + 2];
100
101 className[0] = '[';
102 memcpy(className+1, elemClassObj->descriptor, nameLen+1);
103 arrayClass = dvmFindArrayClass(className, elemClassObj->classLoader);
104
105 return arrayClass;
106 }
107
108 /*
109 * Create a new array that holds primitive types.
110 *
111 * "type" is the primitive type letter, e.g. 'I' for int or 'J' for long.
112 */
dvmAllocPrimitiveArray(char type,size_t length,int allocFlags)113 ArrayObject* dvmAllocPrimitiveArray(char type, size_t length, int allocFlags)
114 {
115 ArrayObject* newArray;
116 ClassObject* arrayClass;
117 int width;
118
119 switch (type) {
120 case 'I':
121 arrayClass = gDvm.classArrayInt;
122 width = 4;
123 break;
124 case 'C':
125 arrayClass = gDvm.classArrayChar;
126 width = 2;
127 break;
128 case 'B':
129 arrayClass = gDvm.classArrayByte;
130 width = 1;
131 break;
132 case 'Z':
133 arrayClass = gDvm.classArrayBoolean;
134 width = 1; /* special-case this? */
135 break;
136 case 'F':
137 arrayClass = gDvm.classArrayFloat;
138 width = 4;
139 break;
140 case 'D':
141 arrayClass = gDvm.classArrayDouble;
142 width = 8;
143 break;
144 case 'S':
145 arrayClass = gDvm.classArrayShort;
146 width = 2;
147 break;
148 case 'J':
149 arrayClass = gDvm.classArrayLong;
150 width = 8;
151 break;
152 default:
153 ALOGE("Unknown primitive type '%c'", type);
154 dvmAbort();
155 return NULL; // Keeps the compiler happy.
156 }
157
158 newArray = allocArray(arrayClass, length, width, allocFlags);
159
160 /* the caller must dvmReleaseTrackedAlloc if allocFlags==ALLOC_DEFAULT */
161 return newArray;
162 }
163
164 /*
165 * Recursively create an array with multiple dimensions. Elements may be
166 * Objects or primitive types.
167 *
168 * The dimension we're creating is in dimensions[0], so when we recurse
169 * we advance the pointer.
170 */
dvmAllocMultiArray(ClassObject * arrayClass,int curDim,const int * dimensions)171 ArrayObject* dvmAllocMultiArray(ClassObject* arrayClass, int curDim,
172 const int* dimensions)
173 {
174 ArrayObject* newArray;
175 const char* elemName = arrayClass->descriptor + 1; // Advance past one '['.
176
177 LOGVV("dvmAllocMultiArray: class='%s' curDim=%d *dimensions=%d",
178 arrayClass->descriptor, curDim, *dimensions);
179
180 if (curDim == 0) {
181 if (*elemName == 'L' || *elemName == '[') {
182 LOGVV(" end: array class (obj) is '%s'",
183 arrayClass->descriptor);
184 newArray = allocArray(arrayClass, *dimensions,
185 kObjectArrayRefWidth, ALLOC_DEFAULT);
186 } else {
187 LOGVV(" end: array class (prim) is '%s'",
188 arrayClass->descriptor);
189 newArray = dvmAllocPrimitiveArray(
190 dexGetPrimitiveTypeDescriptorChar(arrayClass->elementClass->primitiveType),
191 *dimensions, ALLOC_DEFAULT);
192 }
193 } else {
194 ClassObject* subArrayClass;
195 int i;
196
197 /* if we have X[][], find X[] */
198 subArrayClass = dvmFindArrayClass(elemName, arrayClass->classLoader);
199 if (subArrayClass == NULL) {
200 /* not enough '['s on the initial class? */
201 assert(dvmCheckException(dvmThreadSelf()));
202 return NULL;
203 }
204 assert(dvmIsArrayClass(subArrayClass));
205
206 /* allocate the array that holds the sub-arrays */
207 newArray = allocArray(arrayClass, *dimensions, kObjectArrayRefWidth,
208 ALLOC_DEFAULT);
209 if (newArray == NULL) {
210 assert(dvmCheckException(dvmThreadSelf()));
211 return NULL;
212 }
213
214 /*
215 * Create a new sub-array in every element of the array.
216 */
217 for (i = 0; i < *dimensions; i++) {
218 ArrayObject* newSubArray;
219 newSubArray = dvmAllocMultiArray(subArrayClass, curDim-1,
220 dimensions+1);
221 if (newSubArray == NULL) {
222 dvmReleaseTrackedAlloc((Object*) newArray, NULL);
223 assert(dvmCheckException(dvmThreadSelf()));
224 return NULL;
225 }
226 dvmSetObjectArrayElement(newArray, i, (Object *)newSubArray);
227 dvmReleaseTrackedAlloc((Object*) newSubArray, NULL);
228 }
229 }
230
231 /* caller must call dvmReleaseTrackedAlloc */
232 return newArray;
233 }
234
235
236 /*
237 * Find an array class, by name (e.g. "[I").
238 *
239 * If the array class doesn't exist, we generate it.
240 *
241 * If the element class doesn't exist, we return NULL (no exception raised).
242 */
dvmFindArrayClass(const char * descriptor,Object * loader)243 ClassObject* dvmFindArrayClass(const char* descriptor, Object* loader)
244 {
245 ClassObject* clazz;
246
247 assert(descriptor[0] == '[');
248 //ALOGV("dvmFindArrayClass: '%s' %p", descriptor, loader);
249
250 clazz = dvmLookupClass(descriptor, loader, false);
251 if (clazz == NULL) {
252 ALOGV("Array class '%s' %p not found; creating", descriptor, loader);
253 clazz = createArrayClass(descriptor, loader);
254 if (clazz != NULL)
255 dvmAddInitiatingLoader(clazz, loader);
256 }
257
258 return clazz;
259 }
260
261 /*
262 * Create an array class (i.e. the class object for the array, not the
263 * array itself). "descriptor" looks like "[C" or "[Ljava/lang/String;".
264 *
265 * If "descriptor" refers to an array of primitives, look up the
266 * primitive type's internally-generated class object.
267 *
268 * "loader" is the class loader of the class that's referring to us. It's
269 * used to ensure that we're looking for the element type in the right
270 * context. It does NOT become the class loader for the array class; that
271 * always comes from the base element class.
272 *
273 * Returns NULL with an exception raised on failure.
274 */
createArrayClass(const char * descriptor,Object * loader)275 static ClassObject* createArrayClass(const char* descriptor, Object* loader)
276 {
277 ClassObject* newClass = NULL;
278 ClassObject* elementClass = NULL;
279 int arrayDim;
280 u4 extraFlags;
281
282 assert(descriptor[0] == '[');
283 assert(gDvm.classJavaLangClass != NULL);
284 assert(gDvm.classJavaLangObject != NULL);
285
286 /*
287 * Identify the underlying element class and the array dimension depth.
288 */
289 extraFlags = CLASS_ISARRAY;
290 if (descriptor[1] == '[') {
291 /* array of arrays; keep descriptor and grab stuff from parent */
292 ClassObject* outer;
293
294 outer = dvmFindClassNoInit(&descriptor[1], loader);
295 if (outer != NULL) {
296 /* want the base class, not "outer", in our elementClass */
297 elementClass = outer->elementClass;
298 arrayDim = outer->arrayDim + 1;
299 extraFlags |= CLASS_ISOBJECTARRAY;
300 } else {
301 assert(elementClass == NULL); /* make sure we fail */
302 }
303 } else {
304 arrayDim = 1;
305 if (descriptor[1] == 'L') {
306 /* array of objects; strip off "[" and look up descriptor. */
307 const char* subDescriptor = &descriptor[1];
308 LOGVV("searching for element class '%s'", subDescriptor);
309 elementClass = dvmFindClassNoInit(subDescriptor, loader);
310 extraFlags |= CLASS_ISOBJECTARRAY;
311 } else {
312 /* array of a primitive type */
313 elementClass = dvmFindPrimitiveClass(descriptor[1]);
314 }
315 }
316
317 if (elementClass == NULL) {
318 /* failed */
319 assert(dvmCheckException(dvmThreadSelf()));
320 dvmFreeClassInnards(newClass);
321 dvmReleaseTrackedAlloc((Object*) newClass, NULL);
322 return NULL;
323 }
324
325 /*
326 * See if it's already loaded. Array classes are always associated
327 * with the class loader of their underlying element type -- an array
328 * of Strings goes with the loader for java/lang/String -- so we need
329 * to look for it there. (The caller should have checked for the
330 * existence of the class before calling here, but they did so with
331 * *their* class loader, not the element class' loader.)
332 *
333 * If we find it, the caller adds "loader" to the class' initiating
334 * loader list, which should prevent us from going through this again.
335 *
336 * This call is unnecessary if "loader" and "elementClass->classLoader"
337 * are the same, because our caller (dvmFindArrayClass) just did the
338 * lookup. (Even if we get this wrong we still have correct behavior,
339 * because we effectively do this lookup again when we add the new
340 * class to the hash table -- necessary because of possible races with
341 * other threads.)
342 */
343 if (loader != elementClass->classLoader) {
344 LOGVV("--- checking for '%s' in %p vs. elem %p",
345 descriptor, loader, elementClass->classLoader);
346 newClass = dvmLookupClass(descriptor, elementClass->classLoader, false);
347 if (newClass != NULL) {
348 ALOGV("--- we already have %s in %p, don't need in %p",
349 descriptor, elementClass->classLoader, loader);
350 return newClass;
351 }
352 }
353
354
355 /*
356 * Fill out the fields in the ClassObject.
357 *
358 * It is possible to execute some methods against arrays, because all
359 * arrays are instances of Object, so we need to set up a vtable. We
360 * can just point at the one in Object.
361 *
362 * Array classes are simple enough that we don't need to do a full
363 * link step.
364 */
365 newClass = (ClassObject*) dvmMalloc(sizeof(*newClass), ALLOC_NON_MOVING);
366 if (newClass == NULL)
367 return NULL;
368 DVM_OBJECT_INIT(newClass, gDvm.classJavaLangClass);
369 dvmSetClassSerialNumber(newClass);
370 newClass->descriptorAlloc = strdup(descriptor);
371 newClass->descriptor = newClass->descriptorAlloc;
372 dvmSetFieldObject((Object *)newClass,
373 OFFSETOF_MEMBER(ClassObject, super),
374 (Object *)gDvm.classJavaLangObject);
375 newClass->vtableCount = gDvm.classJavaLangObject->vtableCount;
376 newClass->vtable = gDvm.classJavaLangObject->vtable;
377 newClass->primitiveType = PRIM_NOT;
378 dvmSetFieldObject((Object *)newClass,
379 OFFSETOF_MEMBER(ClassObject, elementClass),
380 (Object *)elementClass);
381 dvmSetFieldObject((Object *)newClass,
382 OFFSETOF_MEMBER(ClassObject, classLoader),
383 (Object *)elementClass->classLoader);
384 newClass->arrayDim = arrayDim;
385 newClass->status = CLASS_INITIALIZED;
386
387 /* don't need to set newClass->objectSize */
388
389 /*
390 * All arrays have java/lang/Cloneable and java/io/Serializable as
391 * interfaces. We need to set that up here, so that stuff like
392 * "instanceof" works right.
393 *
394 * Note: The GC could run during the call to dvmFindSystemClassNoInit(),
395 * so we need to make sure the class object is GC-valid while we're in
396 * there. Do this by clearing the interface list so the GC will just
397 * think that the entries are null.
398 *
399 * TODO?
400 * We may want to cache these two classes to avoid the lookup, though
401 * it's not vital -- we only do it when creating an array class, not
402 * every time we create an array. Better yet, create a single, global
403 * copy of "interfaces" and "iftable" somewhere near the start and
404 * just point to those (and remember not to free them for arrays).
405 */
406 newClass->interfaceCount = 2;
407 newClass->interfaces = (ClassObject**)dvmLinearAlloc(newClass->classLoader,
408 sizeof(ClassObject*) * 2);
409 memset(newClass->interfaces, 0, sizeof(ClassObject*) * 2);
410 newClass->interfaces[0] =
411 dvmFindSystemClassNoInit("Ljava/lang/Cloneable;");
412 newClass->interfaces[1] =
413 dvmFindSystemClassNoInit("Ljava/io/Serializable;");
414 dvmLinearReadOnly(newClass->classLoader, newClass->interfaces);
415 if (newClass->interfaces[0] == NULL || newClass->interfaces[1] == NULL) {
416 ALOGE("Unable to create array class '%s': missing interfaces",
417 descriptor);
418 dvmFreeClassInnards(newClass);
419 dvmThrowInternalError("missing array ifaces");
420 dvmReleaseTrackedAlloc((Object*) newClass, NULL);
421 return NULL;
422 }
423 /*
424 * We assume that Cloneable/Serializable don't have superinterfaces --
425 * normally we'd have to crawl up and explicitly list all of the
426 * supers as well. These interfaces don't have any methods, so we
427 * don't have to worry about the ifviPool either.
428 */
429 newClass->iftableCount = 2;
430 newClass->iftable = (InterfaceEntry*) dvmLinearAlloc(newClass->classLoader,
431 sizeof(InterfaceEntry) * 2);
432 memset(newClass->iftable, 0, sizeof(InterfaceEntry) * 2);
433 newClass->iftable[0].clazz = newClass->interfaces[0];
434 newClass->iftable[1].clazz = newClass->interfaces[1];
435 dvmLinearReadOnly(newClass->classLoader, newClass->iftable);
436
437 /*
438 * Inherit access flags from the element. Arrays can't be used as a
439 * superclass or interface, so we want to add "abstract final" and remove
440 * "interface".
441 */
442 int accessFlags = elementClass->accessFlags;
443 if (!gDvm.optimizing) {
444 // If the element class is an inner class, make sure we get the correct access flags.
445 StringObject* className = NULL;
446 dvmGetInnerClass(elementClass, &className, &accessFlags);
447 dvmReleaseTrackedAlloc((Object*) className, NULL);
448 }
449 accessFlags &= JAVA_FLAGS_MASK;
450 accessFlags &= ~ACC_INTERFACE;
451 accessFlags |= ACC_ABSTRACT | ACC_FINAL;
452
453 // Set the flags we determined above.
454 SET_CLASS_FLAG(newClass, accessFlags | extraFlags);
455
456 if (!dvmAddClassToHash(newClass)) {
457 /*
458 * Another thread must have loaded the class after we
459 * started but before we finished. Discard what we've
460 * done and leave some hints for the GC.
461 *
462 * (Yes, this happens.)
463 */
464
465 /* Clean up the class before letting the
466 * GC get its hands on it.
467 */
468 dvmFreeClassInnards(newClass);
469
470 /* Let the GC free the class.
471 */
472 dvmReleaseTrackedAlloc((Object*) newClass, NULL);
473
474 /* Grab the winning class.
475 */
476 newClass = dvmLookupClass(descriptor, elementClass->classLoader, false);
477 assert(newClass != NULL);
478 return newClass;
479 }
480 dvmReleaseTrackedAlloc((Object*) newClass, NULL);
481
482 ALOGV("Created array class '%s' %p (access=0x%04x.%04x)",
483 descriptor, newClass->classLoader,
484 newClass->accessFlags >> 16,
485 newClass->accessFlags & JAVA_FLAGS_MASK);
486
487 return newClass;
488 }
489
490 /*
491 * Copy the entire contents of one array of objects to another. If the copy
492 * is impossible because of a type clash, we fail and return "false".
493 */
dvmCopyObjectArray(ArrayObject * dstArray,const ArrayObject * srcArray,ClassObject * dstElemClass)494 bool dvmCopyObjectArray(ArrayObject* dstArray, const ArrayObject* srcArray,
495 ClassObject* dstElemClass)
496 {
497 Object** src = (Object**)(void*)srcArray->contents;
498 u4 length, count;
499
500 assert(srcArray->length == dstArray->length);
501 assert(dstArray->clazz->elementClass == dstElemClass ||
502 (dstArray->clazz->elementClass == dstElemClass->elementClass &&
503 dstArray->clazz->arrayDim == dstElemClass->arrayDim+1));
504
505 length = dstArray->length;
506 for (count = 0; count < length; count++) {
507 if (!dvmInstanceof(src[count]->clazz, dstElemClass)) {
508 ALOGW("dvmCopyObjectArray: can't store %s in %s",
509 src[count]->clazz->descriptor, dstElemClass->descriptor);
510 return false;
511 }
512 dvmSetObjectArrayElement(dstArray, count, src[count]);
513 }
514
515 return true;
516 }
517
518 /*
519 * Copy the entire contents of an array of boxed primitives into an
520 * array of primitives. The boxed value must fit in the primitive (i.e.
521 * narrowing conversions are not allowed).
522 */
dvmUnboxObjectArray(ArrayObject * dstArray,const ArrayObject * srcArray,ClassObject * dstElemClass)523 bool dvmUnboxObjectArray(ArrayObject* dstArray, const ArrayObject* srcArray,
524 ClassObject* dstElemClass)
525 {
526 Object** src = (Object**)(void*)srcArray->contents;
527 void* dst = (void*)dstArray->contents;
528 u4 count = dstArray->length;
529 PrimitiveType typeIndex = dstElemClass->primitiveType;
530
531 assert(typeIndex != PRIM_NOT);
532 assert(srcArray->length == dstArray->length);
533
534 while (count--) {
535 JValue result;
536
537 /*
538 * This will perform widening conversions as appropriate. It
539 * might make sense to be more restrictive and require that the
540 * primitive type exactly matches the box class, but it's not
541 * necessary for correctness.
542 */
543 if (!dvmUnboxPrimitive(*src, dstElemClass, &result)) {
544 ALOGW("dvmCopyObjectArray: can't store %s in %s",
545 (*src)->clazz->descriptor, dstElemClass->descriptor);
546 return false;
547 }
548
549 /* would be faster with 4 loops, but speed not crucial here */
550 switch (typeIndex) {
551 case PRIM_BOOLEAN:
552 case PRIM_BYTE:
553 {
554 u1* tmp = (u1*)dst;
555 *tmp++ = result.b;
556 dst = tmp;
557 }
558 break;
559 case PRIM_CHAR:
560 case PRIM_SHORT:
561 {
562 u2* tmp = (u2*)dst;
563 *tmp++ = result.s;
564 dst = tmp;
565 }
566 break;
567 case PRIM_FLOAT:
568 case PRIM_INT:
569 {
570 u4* tmp = (u4*)dst;
571 *tmp++ = result.i;
572 dst = tmp;
573 }
574 break;
575 case PRIM_DOUBLE:
576 case PRIM_LONG:
577 {
578 u8* tmp = (u8*)dst;
579 *tmp++ = result.j;
580 dst = tmp;
581 }
582 break;
583 default:
584 /* should not be possible to get here */
585 dvmAbort();
586 }
587
588 src++;
589 }
590
591 return true;
592 }
593
594 /*
595 * Returns the width, in bytes, required by elements in instances of
596 * the array class.
597 */
dvmArrayClassElementWidth(const ClassObject * arrayClass)598 size_t dvmArrayClassElementWidth(const ClassObject* arrayClass)
599 {
600 const char *descriptor;
601
602 assert(dvmIsArrayClass(arrayClass));
603
604 if (dvmIsObjectArrayClass(arrayClass)) {
605 return sizeof(Object *);
606 } else {
607 descriptor = arrayClass->descriptor;
608 switch (descriptor[1]) {
609 case 'B': return 1; /* byte */
610 case 'C': return 2; /* char */
611 case 'D': return 8; /* double */
612 case 'F': return 4; /* float */
613 case 'I': return 4; /* int */
614 case 'J': return 8; /* long */
615 case 'S': return 2; /* short */
616 case 'Z': return 1; /* boolean */
617 }
618 }
619 ALOGE("class %p has an unhandled descriptor '%s'", arrayClass, descriptor);
620 dvmDumpThread(dvmThreadSelf(), false);
621 dvmAbort();
622 return 0; /* Quiet the compiler. */
623 }
624
dvmArrayObjectSize(const ArrayObject * array)625 size_t dvmArrayObjectSize(const ArrayObject *array)
626 {
627 assert(array != NULL);
628 size_t size = OFFSETOF_MEMBER(ArrayObject, contents);
629 size += array->length * dvmArrayClassElementWidth(array->clazz);
630 return size;
631 }
632