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 #include "Dalvik.h" 18 #include "native/InternalNativePriv.h" 19 20 #include <stdlib.h> 21 #include <stdint.h> 22 #include <assert.h> 23 24 /* 25 * The VM makes guarantees about the atomicity of accesses to primitive 26 * variables. These guarantees also apply to elements of arrays. 27 * In particular, 8-bit, 16-bit, and 32-bit accesses must be atomic and 28 * must not cause "word tearing". Accesses to 64-bit array elements must 29 * either be atomic or treated as two 32-bit operations. References are 30 * always read and written atomically, regardless of the number of bits 31 * used to represent them. 32 * 33 * We can't rely on standard libc functions like memcpy() and memmove() 34 * in our implementation of System.arraycopy(), because they may copy 35 * byte-by-byte (either for the full run or for "unaligned" parts at the 36 * start or end). We need to use functions that guarantee 16-bit or 32-bit 37 * atomicity as appropriate. 38 * 39 * System.arraycopy() is heavily used, so having an efficient implementation 40 * is important. The bionic libc provides a platform-optimized memory move 41 * function that should be used when possible. If it's not available, 42 * the trivial "reference implementation" versions below can be used until 43 * a proper version can be written. 44 * 45 * For these functions, The caller must guarantee that dest/src are aligned 46 * appropriately for the element type, and that n is a multiple of the 47 * element size. 48 */ 49 50 /* 51 * Works like memmove(), except: 52 * - if all arguments are at least 32-bit aligned, we guarantee that we 53 * will use operations that preserve atomicity of 32-bit values 54 * - if not, we guarantee atomicity of 16-bit values 55 * 56 * If all three arguments are not at least 16-bit aligned, the behavior 57 * of this function is undefined. (We could remove this restriction by 58 * testing for unaligned values and punting to memmove(), but that's 59 * not currently useful.) 60 * 61 * TODO: add loop for 64-bit alignment 62 * TODO: use __builtin_prefetch 63 * TODO: write an ARM-optimized version 64 */ 65 static void memmove_words(void* dest, const void* src, size_t n) { 66 assert((((uintptr_t) dest | (uintptr_t) src | n) & 0x01) == 0); 67 68 char* d = (char*) dest; 69 const char* s = (const char*) src; 70 size_t copyCount; 71 72 /* 73 * If the source and destination pointers are the same, this is 74 * an expensive no-op. Testing for an empty move now allows us 75 * to skip a check later. 76 */ 77 if (n == 0 || d == s) 78 return; 79 80 /* 81 * Determine if the source and destination buffers will overlap if 82 * we copy data forward (i.e. *dest++ = *src++). 83 * 84 * It's okay if the destination buffer starts before the source and 85 * there is some overlap, because the reader is always ahead of the 86 * writer. 87 */ 88 if (__builtin_expect((d < s) || ((size_t)(d - s) >= n), 1)) { 89 /* 90 * Copy forward. We prefer 32-bit loads and stores even for 16-bit 91 * data, so sort that out. 92 */ 93 if ((((uintptr_t) d | (uintptr_t) s) & 0x03) != 0) { 94 /* 95 * Not 32-bit aligned. Two possibilities: 96 * (1) Congruent, we can align to 32-bit by copying one 16-bit val 97 * (2) Non-congruent, we can do one of: 98 * a. copy whole buffer as a series of 16-bit values 99 * b. load/store 32 bits, using shifts to ensure alignment 100 * c. just copy the as 32-bit values and assume the CPU 101 * will do a reasonable job 102 * 103 * We're currently using (a), which is suboptimal. 104 */ 105 if ((((uintptr_t) d ^ (uintptr_t) s) & 0x03) != 0) { 106 copyCount = n; 107 } else { 108 copyCount = 2; 109 } 110 n -= copyCount; 111 copyCount /= sizeof(uint16_t); 112 113 while (copyCount--) { 114 *(uint16_t*)d = *(uint16_t*)s; 115 d += sizeof(uint16_t); 116 s += sizeof(uint16_t); 117 } 118 } 119 120 /* 121 * Copy 32-bit aligned words. 122 */ 123 copyCount = n / sizeof(uint32_t); 124 while (copyCount--) { 125 *(uint32_t*)d = *(uint32_t*)s; 126 d += sizeof(uint32_t); 127 s += sizeof(uint32_t); 128 } 129 130 /* 131 * Check for leftovers. Either we finished exactly, or we have 132 * one remaining 16-bit chunk. 133 */ 134 if ((n & 0x02) != 0) { 135 *(uint16_t*)d = *(uint16_t*)s; 136 } 137 } else { 138 /* 139 * Copy backward, starting at the end. 140 */ 141 d += n; 142 s += n; 143 144 if ((((uintptr_t) d | (uintptr_t) s) & 0x03) != 0) { 145 /* try for 32-bit alignment */ 146 if ((((uintptr_t) d ^ (uintptr_t) s) & 0x03) != 0) { 147 copyCount = n; 148 } else { 149 copyCount = 2; 150 } 151 n -= copyCount; 152 copyCount /= sizeof(uint16_t); 153 154 while (copyCount--) { 155 d -= sizeof(uint16_t); 156 s -= sizeof(uint16_t); 157 *(uint16_t*)d = *(uint16_t*)s; 158 } 159 } 160 161 /* copy 32-bit aligned words */ 162 copyCount = n / sizeof(uint32_t); 163 while (copyCount--) { 164 d -= sizeof(uint32_t); 165 s -= sizeof(uint32_t); 166 *(uint32_t*)d = *(uint32_t*)s; 167 } 168 169 /* copy leftovers */ 170 if ((n & 0x02) != 0) { 171 d -= sizeof(uint16_t); 172 s -= sizeof(uint16_t); 173 *(uint16_t*)d = *(uint16_t*)s; 174 } 175 } 176 } 177 178 #define move16 memmove_words 179 #define move32 memmove_words 180 181 /* 182 * public static void arraycopy(Object src, int srcPos, Object dest, 183 * int destPos, int length) 184 * 185 * The description of this function is long, and describes a multitude 186 * of checks and exceptions. 187 */ 188 static void Dalvik_java_lang_System_arraycopy(const u4* args, JValue* pResult) 189 { 190 ArrayObject* srcArray = (ArrayObject*) args[0]; 191 int srcPos = args[1]; 192 ArrayObject* dstArray = (ArrayObject*) args[2]; 193 int dstPos = args[3]; 194 int length = args[4]; 195 196 /* Check for null pointers. */ 197 if (srcArray == NULL) { 198 dvmThrowNullPointerException("src == null"); 199 RETURN_VOID(); 200 } 201 if (dstArray == NULL) { 202 dvmThrowNullPointerException("dst == null"); 203 RETURN_VOID(); 204 } 205 206 /* Make sure source and destination are arrays. */ 207 if (!dvmIsArray(srcArray)) { 208 dvmThrowArrayStoreExceptionNotArray(((Object*)srcArray)->clazz, "source"); 209 RETURN_VOID(); 210 } 211 if (!dvmIsArray(dstArray)) { 212 dvmThrowArrayStoreExceptionNotArray(((Object*)dstArray)->clazz, "destination"); 213 RETURN_VOID(); 214 } 215 216 /* avoid int overflow */ 217 if (srcPos < 0 || dstPos < 0 || length < 0 || 218 srcPos > (int) srcArray->length - length || 219 dstPos > (int) dstArray->length - length) 220 { 221 dvmThrowExceptionFmt(gDvm.exArrayIndexOutOfBoundsException, 222 "src.length=%d srcPos=%d dst.length=%d dstPos=%d length=%d", 223 srcArray->length, srcPos, dstArray->length, dstPos, length); 224 RETURN_VOID(); 225 } 226 227 ClassObject* srcClass = srcArray->clazz; 228 ClassObject* dstClass = dstArray->clazz; 229 char srcType = srcClass->descriptor[1]; 230 char dstType = dstClass->descriptor[1]; 231 232 /* 233 * If one of the arrays holds a primitive type, the other array must 234 * hold the same type. 235 */ 236 bool srcPrim = (srcType != '[' && srcType != 'L'); 237 bool dstPrim = (dstType != '[' && dstType != 'L'); 238 if (srcPrim || dstPrim) { 239 if (srcPrim != dstPrim || srcType != dstType) { 240 dvmThrowArrayStoreExceptionIncompatibleArrays(srcClass, dstClass); 241 RETURN_VOID(); 242 } 243 244 if (false) ALOGD("arraycopy prim[%c] dst=%p %d src=%p %d len=%d", 245 srcType, dstArray->contents, dstPos, 246 srcArray->contents, srcPos, length); 247 248 switch (srcType) { 249 case 'B': 250 case 'Z': 251 /* 1 byte per element */ 252 memmove((u1*) dstArray->contents + dstPos, 253 (const u1*) srcArray->contents + srcPos, 254 length); 255 break; 256 case 'C': 257 case 'S': 258 /* 2 bytes per element */ 259 move16((u1*) dstArray->contents + dstPos * 2, 260 (const u1*) srcArray->contents + srcPos * 2, 261 length * 2); 262 break; 263 case 'F': 264 case 'I': 265 /* 4 bytes per element */ 266 move32((u1*) dstArray->contents + dstPos * 4, 267 (const u1*) srcArray->contents + srcPos * 4, 268 length * 4); 269 break; 270 case 'D': 271 case 'J': 272 /* 273 * 8 bytes per element. We don't need to guarantee atomicity 274 * of the entire 64-bit word, so we can use the 32-bit copier. 275 */ 276 move32((u1*) dstArray->contents + dstPos * 8, 277 (const u1*) srcArray->contents + srcPos * 8, 278 length * 8); 279 break; 280 default: /* illegal array type */ 281 ALOGE("Weird array type '%s'", srcClass->descriptor); 282 dvmAbort(); 283 } 284 } else { 285 /* 286 * Neither class is primitive. See if elements in "src" are instances 287 * of elements in "dst" (e.g. copy String to String or String to 288 * Object). 289 */ 290 const int width = sizeof(Object*); 291 292 if (srcClass->arrayDim == dstClass->arrayDim && 293 dvmInstanceof(srcClass, dstClass)) 294 { 295 /* 296 * "dst" can hold "src"; copy the whole thing. 297 */ 298 if (false) ALOGD("arraycopy ref dst=%p %d src=%p %d len=%d", 299 dstArray->contents, dstPos * width, 300 srcArray->contents, srcPos * width, 301 length * width); 302 move32((u1*)dstArray->contents + dstPos * width, 303 (const u1*)srcArray->contents + srcPos * width, 304 length * width); 305 dvmWriteBarrierArray(dstArray, dstPos, dstPos+length); 306 } else { 307 /* 308 * The arrays are not fundamentally compatible. However, we 309 * may still be able to do this if the destination object is 310 * compatible (e.g. copy Object[] to String[], but the Object 311 * being copied is actually a String). We need to copy elements 312 * one by one until something goes wrong. 313 * 314 * Because of overlapping moves, what we really want to do 315 * is compare the types and count up how many we can move, 316 * then call move32() to shift the actual data. If we just 317 * start from the front we could do a smear rather than a move. 318 */ 319 Object** srcObj; 320 int copyCount; 321 ClassObject* clazz = NULL; 322 323 srcObj = ((Object**)(void*)srcArray->contents) + srcPos; 324 325 if (length > 0 && srcObj[0] != NULL) 326 { 327 clazz = srcObj[0]->clazz; 328 if (!dvmCanPutArrayElement(clazz, dstClass)) 329 clazz = NULL; 330 } 331 332 for (copyCount = 0; copyCount < length; copyCount++) 333 { 334 if (srcObj[copyCount] != NULL && 335 srcObj[copyCount]->clazz != clazz && 336 !dvmCanPutArrayElement(srcObj[copyCount]->clazz, dstClass)) 337 { 338 /* can't put this element into the array */ 339 break; 340 } 341 } 342 343 if (false) ALOGD("arraycopy iref dst=%p %d src=%p %d count=%d of %d", 344 dstArray->contents, dstPos * width, 345 srcArray->contents, srcPos * width, 346 copyCount, length); 347 move32((u1*)dstArray->contents + dstPos * width, 348 (const u1*)srcArray->contents + srcPos * width, 349 copyCount * width); 350 dvmWriteBarrierArray(dstArray, 0, copyCount); 351 if (copyCount != length) { 352 dvmThrowArrayStoreExceptionIncompatibleArrayElement(srcPos + copyCount, 353 srcObj[copyCount]->clazz, dstClass); 354 RETURN_VOID(); 355 } 356 } 357 } 358 359 RETURN_VOID(); 360 } 361 362 /* 363 * static int identityHashCode(Object x) 364 * 365 * Returns that hash code that the default hashCode() 366 * method would return for "x", even if "x"s class 367 * overrides hashCode(). 368 */ 369 static void Dalvik_java_lang_System_identityHashCode(const u4* args, 370 JValue* pResult) 371 { 372 Object* thisPtr = (Object*) args[0]; 373 RETURN_INT(dvmIdentityHashCode(thisPtr)); 374 } 375 376 const DalvikNativeMethod dvm_java_lang_System[] = { 377 { "arraycopy", "(Ljava/lang/Object;ILjava/lang/Object;II)V", 378 Dalvik_java_lang_System_arraycopy }, 379 { "identityHashCode", "(Ljava/lang/Object;)I", 380 Dalvik_java_lang_System_identityHashCode }, 381 { NULL, NULL, NULL }, 382 }; 383
