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
ClassSize(PointerSize pointer_size)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>
SizeOf()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
DataOffset(size_t component_size)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>
CheckIsValidIndex(int32_t index)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
ComputeArraySize(int32_t component_count,size_t component_size_shift)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:
SetLengthVisitor(int32_t length)103 explicit SetLengthVisitor(int32_t length) : length_(length) {
104 }
105
operator()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:
SetLengthToUsableSizeVisitor(int32_t min_length,size_t header_size,size_t component_size_shift)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
operator()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>
Alloc(Thread * self,ObjPtr<Class> array_class,int32_t component_count,size_t component_size_shift,gc::AllocatorType allocator_type)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>
VisitRoots(RootVisitor * visitor)206 inline void PrimitiveArray<T>::VisitRoots(RootVisitor* visitor) {
207 array_class_.VisitRootIfNonNull(visitor, RootInfo(kRootStickyClass));
208 }
209
210 template<typename T>
AllocateAndFill(Thread * self,const T * data,size_t length)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>
Alloc(Thread * self,size_t length)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>
Get(int32_t i)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>
Set(int32_t i,T value)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>
Set(int32_t i,T value)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>
SetWithoutChecks(int32_t i,T value)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>
ArrayBackwardCopy(T * d,const T * s,int32_t count)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>
ArrayForwardCopy(T * d,const T * s,int32_t count)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>
Memmove(int32_t dst_pos,ObjPtr<PrimitiveArray<T>> src,int32_t src_pos,int32_t count)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>
Memcpy(int32_t dst_pos,ObjPtr<PrimitiveArray<T>> src,int32_t src_pos,int32_t count)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>
GetElementPtrSize(uint32_t idx,PointerSize ptr_size)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>
SetElementPtrSize(uint32_t idx,uint64_t element,PointerSize ptr_size)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>
SetElementPtrSize(uint32_t idx,T * element,PointerSize ptr_size)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>
Fixup(mirror::PointerArray * dest,PointerSize pointer_size,const Visitor & 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>
Memcpy(int32_t dst_pos,ObjPtr<PointerArray> src,int32_t src_pos,int32_t count,PointerSize ptr_size)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>
SetArrayClass(ObjPtr<Class> array_class)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