array-inl.h revision dfe02f6aafee264478d510b9742ee266ea52e8a8 
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 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.
119class 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
151template <bool kIsInstrumented, bool kFillUsable>
152inline 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
199template<class T>
200inline void PrimitiveArray<T>::VisitRoots(RootVisitor* visitor) {
201  array_class_.VisitRootIfNonNull(visitor, RootInfo(kRootStickyClass));
202}
203
204template<typename T>
205inline 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
212template<typename T>
213inline 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
221template<typename T>
222inline 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
230template<typename T>
231template<bool kTransactionActive, bool kCheckTransaction>
232inline 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
240template<typename T>
241template<bool kTransactionActive, bool kCheckTransaction, VerifyObjectFlags kVerifyFlags>
242inline 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.
254template<typename T>
255static 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.
267template<typename T>
268static 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
276template<class T>
277inline 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
336template<class T>
337inline 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
373template<typename T, VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption>
374inline 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
386template<bool kTransactionActive, bool kUnchecked>
387inline 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
399template<bool kTransactionActive, bool kUnchecked, typename T>
400inline 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
406template <VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption, typename Visitor>
407inline 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