1 /*
2 * Copyright (C) 2019 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 #include "string_builder_append.h"
18
19 #include "base/casts.h"
20 #include "base/logging.h"
21 #include "common_throws.h"
22 #include "gc/heap.h"
23 #include "mirror/array-inl.h"
24 #include "mirror/string-alloc-inl.h"
25 #include "obj_ptr-inl.h"
26 #include "runtime.h"
27 #include "well_known_classes.h"
28
29 namespace art {
30
31 class StringBuilderAppend::Builder {
32 public:
Builder(uint32_t format,const uint32_t * args,Thread * self)33 Builder(uint32_t format, const uint32_t* args, Thread* self)
34 : format_(format),
35 args_(args),
36 hs_(self) {}
37
38 int32_t CalculateLengthWithFlag() REQUIRES_SHARED(Locks::mutator_lock_);
39
40 void operator()(ObjPtr<mirror::Object> obj, size_t usable_size) const
41 REQUIRES_SHARED(Locks::mutator_lock_);
42
43 private:
44 static size_t Uint64Length(uint64_t value);
45
Int64Length(int64_t value)46 static size_t Int64Length(int64_t value) {
47 uint64_t v = static_cast<uint64_t>(value);
48 return (value >= 0) ? Uint64Length(v) : 1u + Uint64Length(-v);
49 }
50
RemainingSpace(ObjPtr<mirror::String> new_string,const uint8_t * data)51 static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint8_t* data)
52 REQUIRES_SHARED(Locks::mutator_lock_) {
53 DCHECK(new_string->IsCompressed());
54 DCHECK_GE(new_string->GetLength(), data - new_string->GetValueCompressed());
55 return new_string->GetLength() - (data - new_string->GetValueCompressed());
56 }
57
RemainingSpace(ObjPtr<mirror::String> new_string,const uint16_t * data)58 static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint16_t* data)
59 REQUIRES_SHARED(Locks::mutator_lock_) {
60 DCHECK(!new_string->IsCompressed());
61 DCHECK_GE(new_string->GetLength(), data - new_string->GetValue());
62 return new_string->GetLength() - (data - new_string->GetValue());
63 }
64
65 template <typename CharType>
66 CharType* AppendFpArg(ObjPtr<mirror::String> new_string,
67 CharType* data,
68 size_t fp_arg_index) const REQUIRES_SHARED(Locks::mutator_lock_);
69
70 template <typename CharType, size_t size>
71 static CharType* AppendLiteral(ObjPtr<mirror::String> new_string,
72 CharType* data,
73 const char (&literal)[size]) REQUIRES_SHARED(Locks::mutator_lock_);
74
75 template <typename CharType>
76 static CharType* AppendString(ObjPtr<mirror::String> new_string,
77 CharType* data,
78 ObjPtr<mirror::String> str) REQUIRES_SHARED(Locks::mutator_lock_);
79
80 template <typename CharType>
81 static CharType* AppendInt64(ObjPtr<mirror::String> new_string,
82 CharType* data,
83 int64_t value) REQUIRES_SHARED(Locks::mutator_lock_);
84
85 int32_t ConvertFpArgs() REQUIRES_SHARED(Locks::mutator_lock_);
86
87 template <typename CharType>
88 void StoreData(ObjPtr<mirror::String> new_string, CharType* data) const
89 REQUIRES_SHARED(Locks::mutator_lock_);
90
91 static constexpr char kNull[] = "null";
92 static constexpr size_t kNullLength = sizeof(kNull) - 1u;
93 static constexpr char kTrue[] = "true";
94 static constexpr size_t kTrueLength = sizeof(kTrue) - 1u;
95 static constexpr char kFalse[] = "false";
96 static constexpr size_t kFalseLength = sizeof(kFalse) - 1u;
97
98 // The format and arguments to append.
99 const uint32_t format_;
100 const uint32_t* const args_;
101
102 // References are moved to the handle scope during CalculateLengthWithFlag().
103 StackHandleScope<kMaxArgs> hs_;
104
105 // We convert float/double values using jdk.internal.math.FloatingDecimal which uses
106 // a thread-local converter under the hood. As we may have more than one
107 // float/double argument, we need to copy the data out of the converter.
108 // Maximum number of characters is 26. See BinaryToASCIIBuffer.buffer in FloatingDecimal.java .
109 // (This is more than enough for the `ExceptionalBinaryToASCIIBuffer` cases.)
110 static constexpr size_t kBinaryToASCIIBufferSize = 26;
111 uint8_t converted_fp_args_[kMaxArgs][kBinaryToASCIIBufferSize];
112 int32_t converted_fp_arg_lengths_[kMaxArgs];
113
114 // The length and flag to store when the AppendBuilder is used as a pre-fence visitor.
115 int32_t length_with_flag_ = 0u;
116 };
117
Uint64Length(uint64_t value)118 inline size_t StringBuilderAppend::Builder::Uint64Length(uint64_t value) {
119 if (value == 0u) {
120 return 1u;
121 }
122 // Calculate floor(log2(value)).
123 size_t log2_value = BitSizeOf<uint64_t>() - 1u - CLZ(value);
124 // Calculate an estimate of floor(log10(value)).
125 // log10(2) = 0.301029996 > 0.296875 = 19/64
126 // floor(log10(v)) == floor(log2(v) * log10(2))
127 // >= floor(log2(v) * 19/64)
128 // >= floor(floor(log2(v)) * 19/64)
129 // This estimate is no more that one off from the actual value because log2(value) < 64 and thus
130 // log2(v) * log10(2) - log2(v) * 19/64 < 64*(log10(2) - 19/64)
131 // for the first approximation and
132 // log2(v) * 19/64 - floor(log2(v)) * 19/64 < 19/64
133 // for the second one. Together,
134 // 64*(log10(2) - 19/64) + 19/64 = 0.56278 < 1 .
135 size_t log10_value_estimate = log2_value * 19u / 64u;
136 static constexpr uint64_t bounds[] = {
137 UINT64_C(9),
138 UINT64_C(99),
139 UINT64_C(999),
140 UINT64_C(9999),
141 UINT64_C(99999),
142 UINT64_C(999999),
143 UINT64_C(9999999),
144 UINT64_C(99999999),
145 UINT64_C(999999999),
146 UINT64_C(9999999999),
147 UINT64_C(99999999999),
148 UINT64_C(999999999999),
149 UINT64_C(9999999999999),
150 UINT64_C(99999999999999),
151 UINT64_C(999999999999999),
152 UINT64_C(9999999999999999),
153 UINT64_C(99999999999999999),
154 UINT64_C(999999999999999999),
155 UINT64_C(9999999999999999999),
156 };
157 // Add 1 for the lowest digit, add another 1 if the estimate was too low.
158 DCHECK_LT(log10_value_estimate, std::size(bounds));
159 size_t adjustment = (value > bounds[log10_value_estimate]) ? 2u : 1u;
160 return log10_value_estimate + adjustment;
161 }
162
163 template <typename CharType>
AppendFpArg(ObjPtr<mirror::String> new_string,CharType * data,size_t fp_arg_index) const164 inline CharType* StringBuilderAppend::Builder::AppendFpArg(ObjPtr<mirror::String> new_string,
165 CharType* data,
166 size_t fp_arg_index) const {
167 DCHECK_LE(fp_arg_index, std::size(converted_fp_args_));
168 const uint8_t* src = converted_fp_args_[fp_arg_index];
169 size_t length = converted_fp_arg_lengths_[fp_arg_index];
170 DCHECK_LE(length, kBinaryToASCIIBufferSize);
171 DCHECK_LE(length, RemainingSpace(new_string, data));
172 return std::copy_n(src, length, data);
173 }
174
175 template <typename CharType, size_t size>
AppendLiteral(ObjPtr<mirror::String> new_string,CharType * data,const char (& literal)[size])176 inline CharType* StringBuilderAppend::Builder::AppendLiteral(ObjPtr<mirror::String> new_string,
177 CharType* data,
178 const char (&literal)[size]) {
179 static_assert(size >= 2, "We need something to append.");
180
181 // Literals are zero-terminated.
182 constexpr size_t length = size - 1u;
183 DCHECK_EQ(literal[length], '\0');
184
185 DCHECK_LE(length, RemainingSpace(new_string, data));
186 for (size_t i = 0; i != length; ++i) {
187 data[i] = literal[i];
188 }
189 return data + length;
190 }
191
192 template <typename CharType>
AppendString(ObjPtr<mirror::String> new_string,CharType * data,ObjPtr<mirror::String> str)193 inline CharType* StringBuilderAppend::Builder::AppendString(ObjPtr<mirror::String> new_string,
194 CharType* data,
195 ObjPtr<mirror::String> str) {
196 size_t length = dchecked_integral_cast<size_t>(str->GetLength());
197 DCHECK_LE(length, RemainingSpace(new_string, data));
198 if (sizeof(CharType) == sizeof(uint8_t) || str->IsCompressed()) {
199 DCHECK(str->IsCompressed());
200 const uint8_t* value = str->GetValueCompressed();
201 for (size_t i = 0; i != length; ++i) {
202 data[i] = value[i];
203 }
204 } else {
205 const uint16_t* value = str->GetValue();
206 for (size_t i = 0; i != length; ++i) {
207 data[i] = dchecked_integral_cast<CharType>(value[i]);
208 }
209 }
210 return data + length;
211 }
212
213 template <typename CharType>
AppendInt64(ObjPtr<mirror::String> new_string,CharType * data,int64_t value)214 inline CharType* StringBuilderAppend::Builder::AppendInt64(ObjPtr<mirror::String> new_string,
215 CharType* data,
216 int64_t value) {
217 DCHECK_GE(RemainingSpace(new_string, data), Int64Length(value));
218 uint64_t v = static_cast<uint64_t>(value);
219 if (value < 0) {
220 *data = '-';
221 ++data;
222 v = -v;
223 }
224 size_t length = Uint64Length(v);
225 // Write the digits from the end, do not write the most significant digit
226 // in the loop to avoid an unnecessary division.
227 for (size_t i = 1; i != length; ++i) {
228 uint64_t digit = v % UINT64_C(10);
229 v /= UINT64_C(10);
230 data[length - i] = '0' + static_cast<char>(digit);
231 }
232 DCHECK_LE(v, 10u);
233 *data = '0' + static_cast<char>(v);
234 return data + length;
235 }
236
ConvertFpArgs()237 int32_t StringBuilderAppend::Builder::ConvertFpArgs() {
238 int32_t fp_args_length = 0u;
239 const uint32_t* current_arg = args_;
240 size_t fp_arg_index = 0u;
241 for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) {
242 DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast));
243 bool fp_arg = false;
244 ObjPtr<mirror::Object> converter;
245 switch (static_cast<Argument>(f & kArgMask)) {
246 case Argument::kString:
247 case Argument::kBoolean:
248 case Argument::kChar:
249 case Argument::kInt:
250 break;
251 case Argument::kLong: {
252 current_arg = AlignUp(current_arg, sizeof(int64_t));
253 ++current_arg; // Skip the low word, let the common code skip the high word.
254 break;
255 }
256 case Argument::kFloat: {
257 fp_arg = true;
258 float arg = bit_cast<float>(*current_arg);
259 converter = WellKnownClasses::jdk_internal_math_FloatingDecimal_getBinaryToASCIIConverter_F
260 ->InvokeStatic<'L', 'F'>(hs_.Self(), arg);
261 break;
262 }
263 case Argument::kDouble: {
264 fp_arg = true;
265 current_arg = AlignUp(current_arg, sizeof(int64_t));
266 double arg = bit_cast<double>(
267 static_cast<uint64_t>(current_arg[0]) + (static_cast<uint64_t>(current_arg[1]) << 32));
268 converter = WellKnownClasses::jdk_internal_math_FloatingDecimal_getBinaryToASCIIConverter_D
269 ->InvokeStatic<'L', 'D'>(hs_.Self(), arg);
270 ++current_arg; // Skip the low word, let the common code skip the high word.
271 break;
272 }
273 case Argument::kStringBuilder:
274 case Argument::kCharArray:
275 case Argument::kObject:
276 LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex
277 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
278 UNREACHABLE();
279 default:
280 LOG(FATAL) << "Unexpected arg format: 0x" << std::hex
281 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
282 UNREACHABLE();
283 }
284 if (fp_arg) {
285 // If we see an exception (presumably OOME or SOE), keep it as is, even
286 // though it may be confusing to see the stack trace for FP argument
287 // conversion continue at the StringBuilder.toString() invoke location.
288 DCHECK_EQ(converter == nullptr, hs_.Self()->IsExceptionPending());
289 if (UNLIKELY(converter == nullptr)) {
290 return -1;
291 }
292 ArtField* btab_buffer_field =
293 WellKnownClasses::jdk_internal_math_FloatingDecimal_BinaryToASCIIBuffer_buffer;
294 int32_t length;
295 if (converter->GetClass() == btab_buffer_field->GetDeclaringClass()) {
296 // Call `converter.getChars(converter.buffer)`.
297 StackHandleScope<1u> hs2(hs_.Self());
298 Handle<mirror::CharArray> buffer =
299 hs2.NewHandle(btab_buffer_field->GetObj<mirror::CharArray>(converter));
300 DCHECK(buffer != nullptr);
301 length = WellKnownClasses::jdk_internal_math_FloatingDecimal_BinaryToASCIIBuffer_getChars
302 ->InvokeInstance<'I', 'L'>(hs_.Self(), converter, buffer.Get());
303 if (UNLIKELY(hs_.Self()->IsExceptionPending())) {
304 return -1;
305 }
306 // The converted string is now at the front of the buffer.
307 DCHECK_GT(length, 0);
308 DCHECK_LE(length, buffer->GetLength());
309 DCHECK_LE(static_cast<size_t>(length), std::size(converted_fp_args_[0]));
310 DCHECK(mirror::String::AllASCII(buffer->GetData(), length));
311 std::copy_n(buffer->GetData(), length, converted_fp_args_[fp_arg_index]);
312 } else {
313 ArtField* ebtab_image_field = WellKnownClasses::
314 jdk_internal_math_FloatingDecimal_ExceptionalBinaryToASCIIBuffer_image;
315 DCHECK(converter->GetClass() == ebtab_image_field->GetDeclaringClass());
316 ObjPtr<mirror::String> converted = ebtab_image_field->GetObj<mirror::String>(converter);
317 DCHECK(converted != nullptr);
318 length = converted->GetLength();
319 if (mirror::kUseStringCompression) {
320 DCHECK(converted->IsCompressed());
321 memcpy(converted_fp_args_[fp_arg_index], converted->GetValueCompressed(), length);
322 } else {
323 DCHECK(mirror::String::AllASCII(converted->GetValue(), length));
324 std::copy_n(converted->GetValue(), length, converted_fp_args_[fp_arg_index]);
325 }
326 }
327 converted_fp_arg_lengths_[fp_arg_index] = length;
328 fp_args_length += length;
329 ++fp_arg_index;
330 }
331 ++current_arg;
332 DCHECK_LE(fp_arg_index, kMaxArgs);
333 }
334 return fp_args_length;
335 }
336
CalculateLengthWithFlag()337 inline int32_t StringBuilderAppend::Builder::CalculateLengthWithFlag() {
338 static_assert(static_cast<size_t>(Argument::kEnd) == 0u, "kEnd must be 0.");
339 bool compressible = mirror::kUseStringCompression;
340 uint64_t length = 0u;
341 bool has_fp_args = false;
342 const uint32_t* current_arg = args_;
343 for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) {
344 DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast));
345 switch (static_cast<Argument>(f & kArgMask)) {
346 case Argument::kString: {
347 Handle<mirror::String> str =
348 hs_.NewHandle(reinterpret_cast32<mirror::String*>(*current_arg));
349 if (str != nullptr) {
350 length += str->GetLength();
351 compressible = compressible && str->IsCompressed();
352 } else {
353 length += kNullLength;
354 }
355 break;
356 }
357 case Argument::kBoolean: {
358 length += (*current_arg != 0u) ? kTrueLength : kFalseLength;
359 break;
360 }
361 case Argument::kChar: {
362 length += 1u;
363 compressible = compressible &&
364 mirror::String::IsASCII(reinterpret_cast<const uint16_t*>(current_arg)[0]);
365 break;
366 }
367 case Argument::kInt: {
368 length += Int64Length(static_cast<int32_t>(*current_arg));
369 break;
370 }
371 case Argument::kLong: {
372 current_arg = AlignUp(current_arg, sizeof(int64_t));
373 length += Int64Length(*reinterpret_cast<const int64_t*>(current_arg));
374 ++current_arg; // Skip the low word, let the common code skip the high word.
375 break;
376 }
377 case Argument::kDouble:
378 current_arg = AlignUp(current_arg, sizeof(int64_t));
379 ++current_arg; // Skip the low word, let the common code skip the high word.
380 FALLTHROUGH_INTENDED;
381 case Argument::kFloat:
382 // Conversion shall be performed in a separate pass because it calls back to
383 // managed code and we need to convert reference arguments to `Handle<>`s first.
384 has_fp_args = true;
385 break;
386
387 case Argument::kStringBuilder:
388 case Argument::kCharArray:
389 case Argument::kObject:
390 LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex
391 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
392 UNREACHABLE();
393 default:
394 LOG(FATAL) << "Unexpected arg format: 0x" << std::hex
395 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
396 UNREACHABLE();
397 }
398 ++current_arg;
399 DCHECK_LE(hs_.NumberOfReferences(), kMaxArgs);
400 }
401
402 if (UNLIKELY(has_fp_args)) {
403 // Call Java helpers to convert FP args.
404 int32_t fp_args_length = ConvertFpArgs();
405 if (fp_args_length == -1) {
406 return -1;
407 }
408 DCHECK_GT(fp_args_length, 0);
409 length += fp_args_length;
410 }
411
412 if (length > std::numeric_limits<int32_t>::max()) {
413 // We cannot allocate memory for the entire result.
414 hs_.Self()->ThrowNewException("Ljava/lang/OutOfMemoryError;",
415 "Out of memory for StringBuilder append.");
416 return -1;
417 }
418
419 length_with_flag_ = mirror::String::GetFlaggedCount(length, compressible);
420 return length_with_flag_;
421 }
422
423 template <typename CharType>
StoreData(ObjPtr<mirror::String> new_string,CharType * data) const424 inline void StringBuilderAppend::Builder::StoreData(ObjPtr<mirror::String> new_string,
425 CharType* data) const {
426 size_t handle_index = 0u;
427 size_t fp_arg_index = 0u;
428 const uint32_t* current_arg = args_;
429 for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) {
430 DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast));
431 switch (static_cast<Argument>(f & kArgMask)) {
432 case Argument::kString: {
433 ObjPtr<mirror::String> str =
434 ObjPtr<mirror::String>::DownCast(hs_.GetReference(handle_index));
435 ++handle_index;
436 if (str != nullptr) {
437 data = AppendString(new_string, data, str);
438 } else {
439 data = AppendLiteral(new_string, data, kNull);
440 }
441 break;
442 }
443 case Argument::kBoolean: {
444 if (*current_arg != 0u) {
445 data = AppendLiteral(new_string, data, kTrue);
446 } else {
447 data = AppendLiteral(new_string, data, kFalse);
448 }
449 break;
450 }
451 case Argument::kChar: {
452 DCHECK_GE(RemainingSpace(new_string, data), 1u);
453 *data = *reinterpret_cast<const CharType*>(current_arg);
454 ++data;
455 break;
456 }
457 case Argument::kInt: {
458 data = AppendInt64(new_string, data, static_cast<int32_t>(*current_arg));
459 break;
460 }
461 case Argument::kLong: {
462 current_arg = AlignUp(current_arg, sizeof(int64_t));
463 data = AppendInt64(new_string, data, *reinterpret_cast<const int64_t*>(current_arg));
464 ++current_arg; // Skip the low word, let the common code skip the high word.
465 break;
466 }
467 case Argument::kDouble:
468 current_arg = AlignUp(current_arg, sizeof(int64_t));
469 ++current_arg; // Skip the low word, let the common code skip the high word.
470 FALLTHROUGH_INTENDED;
471 case Argument::kFloat: {
472 data = AppendFpArg(new_string, data, fp_arg_index);
473 ++fp_arg_index;
474 break;
475 }
476
477 case Argument::kStringBuilder:
478 case Argument::kCharArray:
479 LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex
480 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
481 UNREACHABLE();
482 default:
483 LOG(FATAL) << "Unexpected arg format: 0x" << std::hex
484 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
485 UNREACHABLE();
486 }
487 ++current_arg;
488 DCHECK_LE(handle_index, hs_.NumberOfReferences());
489 DCHECK_LE(fp_arg_index, std::size(converted_fp_args_));
490 }
491 DCHECK_EQ(RemainingSpace(new_string, data), 0u) << std::hex << format_;
492 }
493
operator ()(ObjPtr<mirror::Object> obj,size_t usable_size ATTRIBUTE_UNUSED) const494 inline void StringBuilderAppend::Builder::operator()(ObjPtr<mirror::Object> obj,
495 size_t usable_size ATTRIBUTE_UNUSED) const {
496 ObjPtr<mirror::String> new_string = ObjPtr<mirror::String>::DownCast(obj);
497 new_string->SetCount(length_with_flag_);
498 if (mirror::String::IsCompressed(length_with_flag_)) {
499 StoreData(new_string, new_string->GetValueCompressed());
500 } else {
501 StoreData(new_string, new_string->GetValue());
502 }
503 }
504
AppendF(uint32_t format,const uint32_t * args,Thread * self)505 ObjPtr<mirror::String> StringBuilderAppend::AppendF(uint32_t format,
506 const uint32_t* args,
507 Thread* self) {
508 Builder builder(format, args, self);
509 self->AssertNoPendingException();
510 int32_t length_with_flag = builder.CalculateLengthWithFlag();
511 if (self->IsExceptionPending()) {
512 return nullptr;
513 }
514 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator();
515 ObjPtr<mirror::String> result = mirror::String::Alloc(
516 self, length_with_flag, allocator_type, builder);
517
518 return result;
519 }
520
521 } // namespace art
522