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
30namespace art {
31namespace mirror {
32
33inline 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
38template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption>
39inline 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
51inline 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
59template<VerifyObjectFlags kVerifyFlags>
60inline 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
69static 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.
98class SetLengthVisitor {
99 public:
100  explicit SetLengthVisitor(int32_t length) : length_(length) {
101  }
102
103  void operator()(Object* obj, size_t usable_size) const
104      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
105    UNUSED(usable_size);
106    // Avoid AsArray as object is not yet in live bitmap or allocation stack.
107    Array* array = down_cast<Array*>(obj);
108    // DCHECK(array->IsArrayInstance());
109    array->SetLength(length_);
110  }
111
112 private:
113  const int32_t length_;
114
115  DISALLOW_COPY_AND_ASSIGN(SetLengthVisitor);
116};
117
118// Similar to SetLengthVisitor, used for setting the array length to fill the usable size of an
119// array.
120class SetLengthToUsableSizeVisitor {
121 public:
122  SetLengthToUsableSizeVisitor(int32_t min_length, size_t header_size,
123                               size_t component_size_shift) :
124      minimum_length_(min_length), header_size_(header_size),
125      component_size_shift_(component_size_shift) {
126  }
127
128  void operator()(Object* obj, size_t usable_size) const
129      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
130    // Avoid AsArray as object is not yet in live bitmap or allocation stack.
131    Array* array = down_cast<Array*>(obj);
132    // DCHECK(array->IsArrayInstance());
133    int32_t length = (usable_size - header_size_) >> component_size_shift_;
134    DCHECK_GE(length, minimum_length_);
135    uint8_t* old_end = reinterpret_cast<uint8_t*>(array->GetRawData(1U << component_size_shift_,
136                                                                    minimum_length_));
137    uint8_t* new_end = reinterpret_cast<uint8_t*>(array->GetRawData(1U << component_size_shift_,
138                                                                    length));
139    // Ensure space beyond original allocation is zeroed.
140    memset(old_end, 0, new_end - old_end);
141    array->SetLength(length);
142  }
143
144 private:
145  const int32_t minimum_length_;
146  const size_t header_size_;
147  const size_t component_size_shift_;
148
149  DISALLOW_COPY_AND_ASSIGN(SetLengthToUsableSizeVisitor);
150};
151
152template <bool kIsInstrumented, bool kFillUsable>
153inline Array* Array::Alloc(Thread* self, Class* array_class, int32_t component_count,
154                           size_t component_size_shift, gc::AllocatorType allocator_type) {
155  DCHECK(allocator_type != gc::kAllocatorTypeLOS);
156  DCHECK(array_class != nullptr);
157  DCHECK(array_class->IsArrayClass());
158  DCHECK_EQ(array_class->GetComponentSizeShift(), component_size_shift);
159  DCHECK_EQ(array_class->GetComponentSize(), (1U << component_size_shift));
160  size_t size = ComputeArraySize(component_count, component_size_shift);
161#ifdef __LP64__
162  // 64-bit. No size_t overflow.
163  DCHECK_NE(size, 0U);
164#else
165  // 32-bit.
166  if (UNLIKELY(size == 0)) {
167    self->ThrowOutOfMemoryError(StringPrintf("%s of length %d would overflow",
168                                             PrettyDescriptor(array_class).c_str(),
169                                             component_count).c_str());
170    return nullptr;
171  }
172#endif
173  gc::Heap* heap = Runtime::Current()->GetHeap();
174  Array* result;
175  if (!kFillUsable) {
176    SetLengthVisitor visitor(component_count);
177    result = down_cast<Array*>(
178        heap->AllocObjectWithAllocator<kIsInstrumented, true>(self, array_class, size,
179                                                              allocator_type, visitor));
180  } else {
181    SetLengthToUsableSizeVisitor visitor(component_count,
182                                         DataOffset(1U << component_size_shift).SizeValue(),
183                                         component_size_shift);
184    result = down_cast<Array*>(
185        heap->AllocObjectWithAllocator<kIsInstrumented, true>(self, array_class, size,
186                                                              allocator_type, visitor));
187  }
188  if (kIsDebugBuild && result != nullptr && Runtime::Current()->IsStarted()) {
189    array_class = result->GetClass();  // In case the array class moved.
190    CHECK_EQ(array_class->GetComponentSize(), 1U << component_size_shift);
191    if (!kFillUsable) {
192      CHECK_EQ(result->SizeOf(), size);
193    } else {
194      CHECK_GE(result->SizeOf(), size);
195    }
196  }
197  return result;
198}
199
200template<class T>
201inline void PrimitiveArray<T>::VisitRoots(RootVisitor* visitor) {
202  array_class_.VisitRootIfNonNull(visitor, RootInfo(kRootStickyClass));
203}
204
205template<typename T>
206inline PrimitiveArray<T>* PrimitiveArray<T>::Alloc(Thread* self, size_t length) {
207  Array* raw_array = Array::Alloc<true>(self, GetArrayClass(), length,
208                                        ComponentSizeShiftWidth(sizeof(T)),
209                                        Runtime::Current()->GetHeap()->GetCurrentAllocator());
210  return down_cast<PrimitiveArray<T>*>(raw_array);
211}
212
213template<typename T>
214inline T PrimitiveArray<T>::Get(int32_t i) {
215  if (!CheckIsValidIndex(i)) {
216    DCHECK(Thread::Current()->IsExceptionPending());
217    return T(0);
218  }
219  return GetWithoutChecks(i);
220}
221
222template<typename T>
223inline void PrimitiveArray<T>::Set(int32_t i, T value) {
224  if (Runtime::Current()->IsActiveTransaction()) {
225    Set<true>(i, value);
226  } else {
227    Set<false>(i, value);
228  }
229}
230
231template<typename T>
232template<bool kTransactionActive, bool kCheckTransaction>
233inline void PrimitiveArray<T>::Set(int32_t i, T value) {
234  if (CheckIsValidIndex(i)) {
235    SetWithoutChecks<kTransactionActive, kCheckTransaction>(i, value);
236  } else {
237    DCHECK(Thread::Current()->IsExceptionPending());
238  }
239}
240
241template<typename T>
242template<bool kTransactionActive, bool kCheckTransaction>
243inline void PrimitiveArray<T>::SetWithoutChecks(int32_t i, T value) {
244  if (kCheckTransaction) {
245    DCHECK_EQ(kTransactionActive, Runtime::Current()->IsActiveTransaction());
246  }
247  if (kTransactionActive) {
248    Runtime::Current()->RecordWriteArray(this, i, GetWithoutChecks(i));
249  }
250  DCHECK(CheckIsValidIndex(i));
251  GetData()[i] = value;
252}
253// Backward copy where elements are of aligned appropriately for T. Count is in T sized units.
254// Copies are guaranteed not to tear when the sizeof T is less-than 64bit.
255template<typename T>
256static inline void ArrayBackwardCopy(T* d, const T* s, int32_t count) {
257  d += count;
258  s += count;
259  for (int32_t i = 0; i < count; ++i) {
260    d--;
261    s--;
262    *d = *s;
263  }
264}
265
266// Forward copy where elements are of aligned appropriately for T. Count is in T sized units.
267// Copies are guaranteed not to tear when the sizeof T is less-than 64bit.
268template<typename T>
269static inline void ArrayForwardCopy(T* d, const T* s, int32_t count) {
270  for (int32_t i = 0; i < count; ++i) {
271    *d = *s;
272    d++;
273    s++;
274  }
275}
276
277template<class T>
278inline void PrimitiveArray<T>::Memmove(int32_t dst_pos, PrimitiveArray<T>* src, int32_t src_pos,
279                                       int32_t count) {
280  if (UNLIKELY(count == 0)) {
281    return;
282  }
283  DCHECK_GE(dst_pos, 0);
284  DCHECK_GE(src_pos, 0);
285  DCHECK_GT(count, 0);
286  DCHECK(src != nullptr);
287  DCHECK_LT(dst_pos, GetLength());
288  DCHECK_LE(dst_pos, GetLength() - count);
289  DCHECK_LT(src_pos, src->GetLength());
290  DCHECK_LE(src_pos, src->GetLength() - count);
291
292  // Note for non-byte copies we can't rely on standard libc functions like memcpy(3) and memmove(3)
293  // in our implementation, because they may copy byte-by-byte.
294  if (LIKELY(src != this)) {
295    // Memcpy ok for guaranteed non-overlapping distinct arrays.
296    Memcpy(dst_pos, src, src_pos, count);
297  } else {
298    // Handle copies within the same array using the appropriate direction copy.
299    void* dst_raw = GetRawData(sizeof(T), dst_pos);
300    const void* src_raw = src->GetRawData(sizeof(T), src_pos);
301    if (sizeof(T) == sizeof(uint8_t)) {
302      uint8_t* d = reinterpret_cast<uint8_t*>(dst_raw);
303      const uint8_t* s = reinterpret_cast<const uint8_t*>(src_raw);
304      memmove(d, s, count);
305    } else {
306      const bool copy_forward = (dst_pos < src_pos) || (dst_pos - src_pos >= count);
307      if (sizeof(T) == sizeof(uint16_t)) {
308        uint16_t* d = reinterpret_cast<uint16_t*>(dst_raw);
309        const uint16_t* s = reinterpret_cast<const uint16_t*>(src_raw);
310        if (copy_forward) {
311          ArrayForwardCopy<uint16_t>(d, s, count);
312        } else {
313          ArrayBackwardCopy<uint16_t>(d, s, count);
314        }
315      } else if (sizeof(T) == sizeof(uint32_t)) {
316        uint32_t* d = reinterpret_cast<uint32_t*>(dst_raw);
317        const uint32_t* s = reinterpret_cast<const uint32_t*>(src_raw);
318        if (copy_forward) {
319          ArrayForwardCopy<uint32_t>(d, s, count);
320        } else {
321          ArrayBackwardCopy<uint32_t>(d, s, count);
322        }
323      } else {
324        DCHECK_EQ(sizeof(T), sizeof(uint64_t));
325        uint64_t* d = reinterpret_cast<uint64_t*>(dst_raw);
326        const uint64_t* s = reinterpret_cast<const uint64_t*>(src_raw);
327        if (copy_forward) {
328          ArrayForwardCopy<uint64_t>(d, s, count);
329        } else {
330          ArrayBackwardCopy<uint64_t>(d, s, count);
331        }
332      }
333    }
334  }
335}
336
337template<class T>
338inline void PrimitiveArray<T>::Memcpy(int32_t dst_pos, PrimitiveArray<T>* src, int32_t src_pos,
339                                      int32_t count) {
340  if (UNLIKELY(count == 0)) {
341    return;
342  }
343  DCHECK_GE(dst_pos, 0);
344  DCHECK_GE(src_pos, 0);
345  DCHECK_GT(count, 0);
346  DCHECK(src != nullptr);
347  DCHECK_LT(dst_pos, GetLength());
348  DCHECK_LE(dst_pos, GetLength() - count);
349  DCHECK_LT(src_pos, src->GetLength());
350  DCHECK_LE(src_pos, src->GetLength() - count);
351
352  // Note for non-byte copies we can't rely on standard libc functions like memcpy(3) and memmove(3)
353  // in our implementation, because they may copy byte-by-byte.
354  void* dst_raw = GetRawData(sizeof(T), dst_pos);
355  const void* src_raw = src->GetRawData(sizeof(T), src_pos);
356  if (sizeof(T) == sizeof(uint8_t)) {
357    memcpy(dst_raw, src_raw, count);
358  } else if (sizeof(T) == sizeof(uint16_t)) {
359    uint16_t* d = reinterpret_cast<uint16_t*>(dst_raw);
360    const uint16_t* s = reinterpret_cast<const uint16_t*>(src_raw);
361    ArrayForwardCopy<uint16_t>(d, s, count);
362  } else if (sizeof(T) == sizeof(uint32_t)) {
363    uint32_t* d = reinterpret_cast<uint32_t*>(dst_raw);
364    const uint32_t* s = reinterpret_cast<const uint32_t*>(src_raw);
365    ArrayForwardCopy<uint32_t>(d, s, count);
366  } else {
367    DCHECK_EQ(sizeof(T), sizeof(uint64_t));
368    uint64_t* d = reinterpret_cast<uint64_t*>(dst_raw);
369    const uint64_t* s = reinterpret_cast<const uint64_t*>(src_raw);
370    ArrayForwardCopy<uint64_t>(d, s, count);
371  }
372}
373
374template<typename T>
375inline T PointerArray::GetElementPtrSize(uint32_t idx, size_t ptr_size) {
376  // C style casts here since we sometimes have T be a pointer, or sometimes an integer
377  // (for stack traces).
378  if (ptr_size == 8) {
379    return (T)static_cast<uintptr_t>(AsLongArray()->GetWithoutChecks(idx));
380  }
381  DCHECK_EQ(ptr_size, 4u);
382  return (T)static_cast<uintptr_t>(AsIntArray()->GetWithoutChecks(idx));
383}
384
385template<bool kTransactionActive, bool kUnchecked, typename T>
386inline void PointerArray::SetElementPtrSize(uint32_t idx, T element, size_t ptr_size) {
387  if (ptr_size == 8) {
388    (kUnchecked ? down_cast<LongArray*>(static_cast<Object*>(this)) : AsLongArray())->
389        SetWithoutChecks<kTransactionActive>(idx, (uint64_t)(element));
390  } else {
391    DCHECK_EQ(ptr_size, 4u);
392    DCHECK_LE((uintptr_t)element, 0xFFFFFFFFu);
393    (kUnchecked ? down_cast<IntArray*>(static_cast<Object*>(this)) : AsIntArray())
394        ->SetWithoutChecks<kTransactionActive>(idx, static_cast<uint32_t>((uintptr_t)element));
395  }
396}
397
398}  // namespace mirror
399}  // namespace art
400
401#endif  // ART_RUNTIME_MIRROR_ARRAY_INL_H_
402