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