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