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