1 /* 2 * Copyright (C) 2011 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 #ifndef ART_RUNTIME_MIRROR_ARRAY_INL_H_ 18 #define ART_RUNTIME_MIRROR_ARRAY_INL_H_ 19 20 #include "array.h" 21 22 #include "android-base/stringprintf.h" 23 24 #include "base/bit_utils.h" 25 #include "base/casts.h" 26 #include "base/logging.h" 27 #include "class.h" 28 #include "gc/heap-inl.h" 29 #include "object-inl.h" 30 #include "obj_ptr-inl.h" 31 #include "thread.h" 32 33 namespace art { 34 namespace mirror { 35 36 inline uint32_t Array::ClassSize(PointerSize pointer_size) { 37 uint32_t vtable_entries = Object::kVTableLength; 38 return Class::ComputeClassSize(true, vtable_entries, 0, 0, 0, 0, 0, pointer_size); 39 } 40 41 template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption> 42 inline size_t Array::SizeOf() { 43 // This is safe from overflow because the array was already allocated, so we know it's sane. 44 size_t component_size_shift = GetClass<kVerifyFlags, kReadBarrierOption>()-> 45 template GetComponentSizeShift<kReadBarrierOption>(); 46 // Don't need to check this since we already check this in GetClass. 47 int32_t component_count = 48 GetLength<static_cast<VerifyObjectFlags>(kVerifyFlags & ~kVerifyThis)>(); 49 size_t header_size = DataOffset(1U << component_size_shift).SizeValue(); 50 size_t data_size = component_count << component_size_shift; 51 return header_size + data_size; 52 } 53 54 inline MemberOffset Array::DataOffset(size_t component_size) { 55 DCHECK(IsPowerOfTwo(component_size)) << component_size; 56 size_t data_offset = RoundUp(OFFSETOF_MEMBER(Array, first_element_), component_size); 57 DCHECK_EQ(RoundUp(data_offset, component_size), data_offset) 58 << "Array data offset isn't aligned with component size"; 59 return MemberOffset(data_offset); 60 } 61 62 template<VerifyObjectFlags kVerifyFlags> 63 inline bool Array::CheckIsValidIndex(int32_t index) { 64 if (UNLIKELY(static_cast<uint32_t>(index) >= 65 static_cast<uint32_t>(GetLength<kVerifyFlags>()))) { 66 ThrowArrayIndexOutOfBoundsException(index); 67 return false; 68 } 69 return true; 70 } 71 72 static inline size_t ComputeArraySize(int32_t component_count, size_t component_size_shift) { 73 DCHECK_GE(component_count, 0); 74 75 size_t component_size = 1U << component_size_shift; 76 size_t header_size = Array::DataOffset(component_size).SizeValue(); 77 size_t data_size = static_cast<size_t>(component_count) << component_size_shift; 78 size_t size = header_size + data_size; 79 80 // Check for size_t overflow if this was an unreasonable request 81 // but let the caller throw OutOfMemoryError. 82 #ifdef __LP64__ 83 // 64-bit. No overflow as component_count is 32-bit and the maximum 84 // component size is 8. 85 DCHECK_LE((1U << component_size_shift), 8U); 86 #else 87 // 32-bit. 88 DCHECK_NE(header_size, 0U); 89 DCHECK_EQ(RoundUp(header_size, component_size), header_size); 90 // The array length limit (exclusive). 91 const size_t length_limit = (0U - header_size) >> component_size_shift; 92 if (UNLIKELY(length_limit <= static_cast<size_t>(component_count))) { 93 return 0; // failure 94 } 95 #endif 96 return size; 97 } 98 99 // Used for setting the array length in the allocation code path to ensure it is guarded by a 100 // StoreStore fence. 101 class SetLengthVisitor { 102 public: 103 explicit SetLengthVisitor(int32_t length) : length_(length) { 104 } 105 106 void operator()(ObjPtr<Object> obj, size_t usable_size ATTRIBUTE_UNUSED) const 107 REQUIRES_SHARED(Locks::mutator_lock_) { 108 // Avoid AsArray as object is not yet in live bitmap or allocation stack. 109 ObjPtr<Array> array = ObjPtr<Array>::DownCast(obj); 110 // DCHECK(array->IsArrayInstance()); 111 array->SetLength(length_); 112 } 113 114 private: 115 const int32_t length_; 116 117 DISALLOW_COPY_AND_ASSIGN(SetLengthVisitor); 118 }; 119 120 // Similar to SetLengthVisitor, used for setting the array length to fill the usable size of an 121 // array. 122 class SetLengthToUsableSizeVisitor { 123 public: 124 SetLengthToUsableSizeVisitor(int32_t min_length, size_t header_size, 125 size_t component_size_shift) : 126 minimum_length_(min_length), header_size_(header_size), 127 component_size_shift_(component_size_shift) { 128 } 129 130 void operator()(ObjPtr<Object> obj, size_t usable_size) const 131 REQUIRES_SHARED(Locks::mutator_lock_) { 132 // Avoid AsArray as object is not yet in live bitmap or allocation stack. 133 ObjPtr<Array> array = ObjPtr<Array>::DownCast(obj); 134 // DCHECK(array->IsArrayInstance()); 135 int32_t length = (usable_size - header_size_) >> component_size_shift_; 136 DCHECK_GE(length, minimum_length_); 137 uint8_t* old_end = reinterpret_cast<uint8_t*>(array->GetRawData(1U << component_size_shift_, 138 minimum_length_)); 139 uint8_t* new_end = reinterpret_cast<uint8_t*>(array->GetRawData(1U << component_size_shift_, 140 length)); 141 // Ensure space beyond original allocation is zeroed. 142 memset(old_end, 0, new_end - old_end); 143 array->SetLength(length); 144 } 145 146 private: 147 const int32_t minimum_length_; 148 const size_t header_size_; 149 const size_t component_size_shift_; 150 151 DISALLOW_COPY_AND_ASSIGN(SetLengthToUsableSizeVisitor); 152 }; 153 154 template <bool kIsInstrumented, bool kFillUsable> 155 inline Array* Array::Alloc(Thread* self, 156 ObjPtr<Class> array_class, 157 int32_t component_count, 158 size_t component_size_shift, 159 gc::AllocatorType allocator_type) { 160 DCHECK(allocator_type != gc::kAllocatorTypeLOS); 161 DCHECK(array_class != nullptr); 162 DCHECK(array_class->IsArrayClass()); 163 DCHECK_EQ(array_class->GetComponentSizeShift(), component_size_shift); 164 DCHECK_EQ(array_class->GetComponentSize(), (1U << component_size_shift)); 165 size_t size = ComputeArraySize(component_count, component_size_shift); 166 #ifdef __LP64__ 167 // 64-bit. No size_t overflow. 168 DCHECK_NE(size, 0U); 169 #else 170 // 32-bit. 171 if (UNLIKELY(size == 0)) { 172 self->ThrowOutOfMemoryError(android::base::StringPrintf("%s of length %d would overflow", 173 array_class->PrettyDescriptor().c_str(), 174 component_count).c_str()); 175 return nullptr; 176 } 177 #endif 178 gc::Heap* heap = Runtime::Current()->GetHeap(); 179 Array* result; 180 if (!kFillUsable) { 181 SetLengthVisitor visitor(component_count); 182 result = down_cast<Array*>( 183 heap->AllocObjectWithAllocator<kIsInstrumented, true>(self, array_class, size, 184 allocator_type, visitor)); 185 } else { 186 SetLengthToUsableSizeVisitor visitor(component_count, 187 DataOffset(1U << component_size_shift).SizeValue(), 188 component_size_shift); 189 result = down_cast<Array*>( 190 heap->AllocObjectWithAllocator<kIsInstrumented, true>(self, array_class, size, 191 allocator_type, visitor)); 192 } 193 if (kIsDebugBuild && result != nullptr && Runtime::Current()->IsStarted()) { 194 array_class = result->GetClass(); // In case the array class moved. 195 CHECK_EQ(array_class->GetComponentSize(), 1U << component_size_shift); 196 if (!kFillUsable) { 197 CHECK_EQ(result->SizeOf(), size); 198 } else { 199 CHECK_GE(result->SizeOf(), size); 200 } 201 } 202 return result; 203 } 204 205 template<class T> 206 inline void PrimitiveArray<T>::VisitRoots(RootVisitor* visitor) { 207 array_class_.VisitRootIfNonNull(visitor, RootInfo(kRootStickyClass)); 208 } 209 210 template<typename T> 211 inline PrimitiveArray<T>* PrimitiveArray<T>::AllocateAndFill(Thread* self, 212 const T* data, 213 size_t length) { 214 StackHandleScope<1> hs(self); 215 Handle<PrimitiveArray<T>> arr(hs.NewHandle(PrimitiveArray<T>::Alloc(self, length))); 216 if (!arr.IsNull()) { 217 // Copy it in. Just skip if it's null 218 memcpy(arr->GetData(), data, sizeof(T) * length); 219 } 220 return arr.Get(); 221 } 222 223 template<typename T> 224 inline PrimitiveArray<T>* PrimitiveArray<T>::Alloc(Thread* self, size_t length) { 225 Array* raw_array = Array::Alloc<true>(self, 226 GetArrayClass(), 227 length, 228 ComponentSizeShiftWidth(sizeof(T)), 229 Runtime::Current()->GetHeap()->GetCurrentAllocator()); 230 return down_cast<PrimitiveArray<T>*>(raw_array); 231 } 232 233 template<typename T> 234 inline T PrimitiveArray<T>::Get(int32_t i) { 235 if (!CheckIsValidIndex(i)) { 236 DCHECK(Thread::Current()->IsExceptionPending()); 237 return T(0); 238 } 239 return GetWithoutChecks(i); 240 } 241 242 template<typename T> 243 inline void PrimitiveArray<T>::Set(int32_t i, T value) { 244 if (Runtime::Current()->IsActiveTransaction()) { 245 Set<true>(i, value); 246 } else { 247 Set<false>(i, value); 248 } 249 } 250 251 template<typename T> 252 template<bool kTransactionActive, bool kCheckTransaction> 253 inline void PrimitiveArray<T>::Set(int32_t i, T value) { 254 if (CheckIsValidIndex(i)) { 255 SetWithoutChecks<kTransactionActive, kCheckTransaction>(i, value); 256 } else { 257 DCHECK(Thread::Current()->IsExceptionPending()); 258 } 259 } 260 261 template<typename T> 262 template<bool kTransactionActive, bool kCheckTransaction, VerifyObjectFlags kVerifyFlags> 263 inline void PrimitiveArray<T>::SetWithoutChecks(int32_t i, T value) { 264 if (kCheckTransaction) { 265 DCHECK_EQ(kTransactionActive, Runtime::Current()->IsActiveTransaction()); 266 } 267 if (kTransactionActive) { 268 Runtime::Current()->RecordWriteArray(this, i, GetWithoutChecks(i)); 269 } 270 DCHECK(CheckIsValidIndex<kVerifyFlags>(i)); 271 GetData()[i] = value; 272 } 273 // Backward copy where elements are of aligned appropriately for T. Count is in T sized units. 274 // Copies are guaranteed not to tear when the sizeof T is less-than 64bit. 275 template<typename T> 276 static inline void ArrayBackwardCopy(T* d, const T* s, int32_t count) { 277 d += count; 278 s += count; 279 for (int32_t i = 0; i < count; ++i) { 280 d--; 281 s--; 282 *d = *s; 283 } 284 } 285 286 // Forward copy where elements are of aligned appropriately for T. Count is in T sized units. 287 // Copies are guaranteed not to tear when the sizeof T is less-than 64bit. 288 template<typename T> 289 static inline void ArrayForwardCopy(T* d, const T* s, int32_t count) { 290 for (int32_t i = 0; i < count; ++i) { 291 *d = *s; 292 d++; 293 s++; 294 } 295 } 296 297 template<class T> 298 inline void PrimitiveArray<T>::Memmove(int32_t dst_pos, 299 ObjPtr<PrimitiveArray<T>> src, 300 int32_t src_pos, 301 int32_t count) { 302 if (UNLIKELY(count == 0)) { 303 return; 304 } 305 DCHECK_GE(dst_pos, 0); 306 DCHECK_GE(src_pos, 0); 307 DCHECK_GT(count, 0); 308 DCHECK(src != nullptr); 309 DCHECK_LT(dst_pos, GetLength()); 310 DCHECK_LE(dst_pos, GetLength() - count); 311 DCHECK_LT(src_pos, src->GetLength()); 312 DCHECK_LE(src_pos, src->GetLength() - count); 313 314 // Note for non-byte copies we can't rely on standard libc functions like memcpy(3) and memmove(3) 315 // in our implementation, because they may copy byte-by-byte. 316 if (LIKELY(src != this)) { 317 // Memcpy ok for guaranteed non-overlapping distinct arrays. 318 Memcpy(dst_pos, src, src_pos, count); 319 } else { 320 // Handle copies within the same array using the appropriate direction copy. 321 void* dst_raw = GetRawData(sizeof(T), dst_pos); 322 const void* src_raw = src->GetRawData(sizeof(T), src_pos); 323 if (sizeof(T) == sizeof(uint8_t)) { 324 uint8_t* d = reinterpret_cast<uint8_t*>(dst_raw); 325 const uint8_t* s = reinterpret_cast<const uint8_t*>(src_raw); 326 memmove(d, s, count); 327 } else { 328 const bool copy_forward = (dst_pos < src_pos) || (dst_pos - src_pos >= count); 329 if (sizeof(T) == sizeof(uint16_t)) { 330 uint16_t* d = reinterpret_cast<uint16_t*>(dst_raw); 331 const uint16_t* s = reinterpret_cast<const uint16_t*>(src_raw); 332 if (copy_forward) { 333 ArrayForwardCopy<uint16_t>(d, s, count); 334 } else { 335 ArrayBackwardCopy<uint16_t>(d, s, count); 336 } 337 } else if (sizeof(T) == sizeof(uint32_t)) { 338 uint32_t* d = reinterpret_cast<uint32_t*>(dst_raw); 339 const uint32_t* s = reinterpret_cast<const uint32_t*>(src_raw); 340 if (copy_forward) { 341 ArrayForwardCopy<uint32_t>(d, s, count); 342 } else { 343 ArrayBackwardCopy<uint32_t>(d, s, count); 344 } 345 } else { 346 DCHECK_EQ(sizeof(T), sizeof(uint64_t)); 347 uint64_t* d = reinterpret_cast<uint64_t*>(dst_raw); 348 const uint64_t* s = reinterpret_cast<const uint64_t*>(src_raw); 349 if (copy_forward) { 350 ArrayForwardCopy<uint64_t>(d, s, count); 351 } else { 352 ArrayBackwardCopy<uint64_t>(d, s, count); 353 } 354 } 355 } 356 } 357 } 358 359 template<class T> 360 inline void PrimitiveArray<T>::Memcpy(int32_t dst_pos, 361 ObjPtr<PrimitiveArray<T>> src, 362 int32_t src_pos, 363 int32_t count) { 364 if (UNLIKELY(count == 0)) { 365 return; 366 } 367 DCHECK_GE(dst_pos, 0); 368 DCHECK_GE(src_pos, 0); 369 DCHECK_GT(count, 0); 370 DCHECK(src != nullptr); 371 DCHECK_LT(dst_pos, GetLength()); 372 DCHECK_LE(dst_pos, GetLength() - count); 373 DCHECK_LT(src_pos, src->GetLength()); 374 DCHECK_LE(src_pos, src->GetLength() - count); 375 376 // Note for non-byte copies we can't rely on standard libc functions like memcpy(3) and memmove(3) 377 // in our implementation, because they may copy byte-by-byte. 378 void* dst_raw = GetRawData(sizeof(T), dst_pos); 379 const void* src_raw = src->GetRawData(sizeof(T), src_pos); 380 if (sizeof(T) == sizeof(uint8_t)) { 381 memcpy(dst_raw, src_raw, count); 382 } else if (sizeof(T) == sizeof(uint16_t)) { 383 uint16_t* d = reinterpret_cast<uint16_t*>(dst_raw); 384 const uint16_t* s = reinterpret_cast<const uint16_t*>(src_raw); 385 ArrayForwardCopy<uint16_t>(d, s, count); 386 } else if (sizeof(T) == sizeof(uint32_t)) { 387 uint32_t* d = reinterpret_cast<uint32_t*>(dst_raw); 388 const uint32_t* s = reinterpret_cast<const uint32_t*>(src_raw); 389 ArrayForwardCopy<uint32_t>(d, s, count); 390 } else { 391 DCHECK_EQ(sizeof(T), sizeof(uint64_t)); 392 uint64_t* d = reinterpret_cast<uint64_t*>(dst_raw); 393 const uint64_t* s = reinterpret_cast<const uint64_t*>(src_raw); 394 ArrayForwardCopy<uint64_t>(d, s, count); 395 } 396 } 397 398 template<typename T, VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption> 399 inline T PointerArray::GetElementPtrSize(uint32_t idx, PointerSize ptr_size) { 400 // C style casts here since we sometimes have T be a pointer, or sometimes an integer 401 // (for stack traces). 402 if (ptr_size == PointerSize::k64) { 403 return (T)static_cast<uintptr_t>( 404 AsLongArray<kVerifyFlags, kReadBarrierOption>()->GetWithoutChecks(idx)); 405 } 406 return (T)static_cast<uintptr_t>(static_cast<uint32_t>( 407 AsIntArray<kVerifyFlags, kReadBarrierOption>()->GetWithoutChecks(idx))); 408 } 409 410 template<bool kTransactionActive, bool kUnchecked> 411 inline void PointerArray::SetElementPtrSize(uint32_t idx, uint64_t element, PointerSize ptr_size) { 412 if (ptr_size == PointerSize::k64) { 413 (kUnchecked ? down_cast<LongArray*>(static_cast<Object*>(this)) : AsLongArray())-> 414 SetWithoutChecks<kTransactionActive>(idx, element); 415 } else { 416 DCHECK_LE(element, static_cast<uint64_t>(0xFFFFFFFFu)); 417 (kUnchecked ? down_cast<IntArray*>(static_cast<Object*>(this)) : AsIntArray()) 418 ->SetWithoutChecks<kTransactionActive>(idx, static_cast<uint32_t>(element)); 419 } 420 } 421 422 template<bool kTransactionActive, bool kUnchecked, typename T> 423 inline void PointerArray::SetElementPtrSize(uint32_t idx, T* element, PointerSize ptr_size) { 424 SetElementPtrSize<kTransactionActive, kUnchecked>(idx, 425 reinterpret_cast<uintptr_t>(element), 426 ptr_size); 427 } 428 429 template <VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption, typename Visitor> 430 inline void PointerArray::Fixup(mirror::PointerArray* dest, 431 PointerSize pointer_size, 432 const Visitor& visitor) { 433 for (size_t i = 0, count = GetLength(); i < count; ++i) { 434 void* ptr = GetElementPtrSize<void*, kVerifyFlags, kReadBarrierOption>(i, pointer_size); 435 void* new_ptr = visitor(ptr); 436 if (ptr != new_ptr) { 437 dest->SetElementPtrSize<false, true>(i, new_ptr, pointer_size); 438 } 439 } 440 } 441 442 template<bool kUnchecked> 443 void PointerArray::Memcpy(int32_t dst_pos, 444 ObjPtr<PointerArray> src, 445 int32_t src_pos, 446 int32_t count, 447 PointerSize ptr_size) { 448 DCHECK(!Runtime::Current()->IsActiveTransaction()); 449 DCHECK(!src.IsNull()); 450 if (ptr_size == PointerSize::k64) { 451 LongArray* l_this = (kUnchecked ? down_cast<LongArray*>(static_cast<Object*>(this)) 452 : AsLongArray()); 453 LongArray* l_src = (kUnchecked ? down_cast<LongArray*>(static_cast<Object*>(src.Ptr())) 454 : src->AsLongArray()); 455 l_this->Memcpy(dst_pos, l_src, src_pos, count); 456 } else { 457 IntArray* i_this = (kUnchecked ? down_cast<IntArray*>(static_cast<Object*>(this)) 458 : AsIntArray()); 459 IntArray* i_src = (kUnchecked ? down_cast<IntArray*>(static_cast<Object*>(src.Ptr())) 460 : src->AsIntArray()); 461 i_this->Memcpy(dst_pos, i_src, src_pos, count); 462 } 463 } 464 465 template<typename T> 466 inline void PrimitiveArray<T>::SetArrayClass(ObjPtr<Class> array_class) { 467 CHECK(array_class_.IsNull()); 468 CHECK(array_class != nullptr); 469 array_class_ = GcRoot<Class>(array_class); 470 } 471 472 } // namespace mirror 473 } // namespace art 474 475 #endif // ART_RUNTIME_MIRROR_ARRAY_INL_H_ 476