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
ClassSize(size_t pointer_size)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>
SizeOf()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
DataOffset(size_t component_size)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>
CheckIsValidIndex(int32_t index)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
ComputeArraySize(int32_t component_count,size_t component_size_shift)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:
SetLengthVisitor(int32_t length)100 explicit SetLengthVisitor(int32_t length) : length_(length) {
101 }
102
operator()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.
120 class SetLengthToUsableSizeVisitor {
121 public:
SetLengthToUsableSizeVisitor(int32_t min_length,size_t header_size,size_t component_size_shift)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
operator()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
152 template <bool kIsInstrumented, bool kFillUsable>
Alloc(Thread * self,Class * array_class,int32_t component_count,size_t component_size_shift,gc::AllocatorType allocator_type)153 inline 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
200 template<class T>
VisitRoots(RootVisitor * visitor)201 inline void PrimitiveArray<T>::VisitRoots(RootVisitor* visitor) {
202 array_class_.VisitRootIfNonNull(visitor, RootInfo(kRootStickyClass));
203 }
204
205 template<typename T>
Alloc(Thread * self,size_t length)206 inline 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
213 template<typename T>
Get(int32_t i)214 inline 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
222 template<typename T>
Set(int32_t i,T value)223 inline 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
231 template<typename T>
232 template<bool kTransactionActive, bool kCheckTransaction>
Set(int32_t i,T value)233 inline 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
241 template<typename T>
242 template<bool kTransactionActive, bool kCheckTransaction>
SetWithoutChecks(int32_t i,T value)243 inline 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.
255 template<typename T>
ArrayBackwardCopy(T * d,const T * s,int32_t count)256 static 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.
268 template<typename T>
ArrayForwardCopy(T * d,const T * s,int32_t count)269 static 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
277 template<class T>
Memmove(int32_t dst_pos,PrimitiveArray<T> * src,int32_t src_pos,int32_t count)278 inline 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
337 template<class T>
Memcpy(int32_t dst_pos,PrimitiveArray<T> * src,int32_t src_pos,int32_t count)338 inline 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
374 template<typename T>
GetElementPtrSize(uint32_t idx,size_t ptr_size)375 inline 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
385 template<bool kTransactionActive, bool kUnchecked, typename T>
SetElementPtrSize(uint32_t idx,T element,size_t ptr_size)386 inline 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