| /* | |
| * Copyright (C) 2019 The Android Open Source Project | |
| * | |
| * Licensed under the Apache License, Version 2.0 (the "License"); | |
| * you may not use this file except in compliance with the License. | |
| * You may obtain a copy of the License at | |
| * | |
| * http://www.apache.org/licenses/LICENSE-2.0 | |
| * | |
| * Unless required by applicable law or agreed to in writing, software | |
| * distributed under the License is distributed on an "AS IS" BASIS, | |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| * See the License for the specific language governing permissions and | |
| * limitations under the License. | |
| */ | |
| #include "string_builder_append.h" | |
| #include "base/casts.h" | |
| #include "base/logging.h" | |
| #include "common_throws.h" | |
| #include "gc/heap.h" | |
| #include "mirror/array-inl.h" | |
| #include "mirror/string-alloc-inl.h" | |
| #include "obj_ptr-inl.h" | |
| #include "runtime.h" | |
| #include "well_known_classes.h" | |
| namespace art HIDDEN { | |
| class StringBuilderAppend::Builder { | |
| public: | |
| Builder(uint32_t format, const uint32_t* args, Thread* self) | |
| : format_(format), | |
| args_(args), | |
| hs_(self) {} | |
| int32_t CalculateLengthWithFlag() REQUIRES_SHARED(Locks::mutator_lock_); | |
| void operator()(ObjPtr<mirror::Object> obj, size_t usable_size) const | |
| REQUIRES_SHARED(Locks::mutator_lock_); | |
| private: | |
| static size_t Uint64Length(uint64_t value); | |
| static size_t Int64Length(int64_t value) { | |
| uint64_t v = static_cast<uint64_t>(value); | |
| return (value >= 0) ? Uint64Length(v) : 1u + Uint64Length(-v); | |
| } | |
| static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint8_t* data) | |
| REQUIRES_SHARED(Locks::mutator_lock_) { | |
| DCHECK(new_string->IsCompressed()); | |
| DCHECK_GE(new_string->GetLength(), data - new_string->GetValueCompressed()); | |
| return new_string->GetLength() - (data - new_string->GetValueCompressed()); | |
| } | |
| static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint16_t* data) | |
| REQUIRES_SHARED(Locks::mutator_lock_) { | |
| DCHECK(!new_string->IsCompressed()); | |
| DCHECK_GE(new_string->GetLength(), data - new_string->GetValue()); | |
| return new_string->GetLength() - (data - new_string->GetValue()); | |
| } | |
| template <typename CharType> | |
| CharType* AppendFpArg(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| size_t fp_arg_index) const REQUIRES_SHARED(Locks::mutator_lock_); | |
| template <typename CharType, size_t size> | |
| static CharType* AppendLiteral(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| const char (&literal)[size]) REQUIRES_SHARED(Locks::mutator_lock_); | |
| template <typename CharType> | |
| static CharType* AppendString(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| ObjPtr<mirror::String> str) REQUIRES_SHARED(Locks::mutator_lock_); | |
| template <typename CharType> | |
| static CharType* AppendInt64(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| int64_t value) REQUIRES_SHARED(Locks::mutator_lock_); | |
| int32_t ConvertFpArgs() REQUIRES_SHARED(Locks::mutator_lock_); | |
| template <typename CharType> | |
| void StoreData(ObjPtr<mirror::String> new_string, CharType* data) const | |
| REQUIRES_SHARED(Locks::mutator_lock_); | |
| static constexpr char kNull[] = "null"; | |
| static constexpr size_t kNullLength = sizeof(kNull) - 1u; | |
| static constexpr char kTrue[] = "true"; | |
| static constexpr size_t kTrueLength = sizeof(kTrue) - 1u; | |
| static constexpr char kFalse[] = "false"; | |
| static constexpr size_t kFalseLength = sizeof(kFalse) - 1u; | |
| // The format and arguments to append. | |
| const uint32_t format_; | |
| const uint32_t* const args_; | |
| // References are moved to the handle scope during CalculateLengthWithFlag(). | |
| StackHandleScope<kMaxArgs> hs_; | |
| // We convert float/double values using jdk.internal.math.FloatingDecimal which uses | |
| // a thread-local converter under the hood. As we may have more than one | |
| // float/double argument, we need to copy the data out of the converter. | |
| // Maximum number of characters is 26. See BinaryToASCIIBuffer.buffer in FloatingDecimal.java . | |
| // (This is more than enough for the `ExceptionalBinaryToASCIIBuffer` cases.) | |
| static constexpr size_t kBinaryToASCIIBufferSize = 26; | |
| uint8_t converted_fp_args_[kMaxArgs][kBinaryToASCIIBufferSize]; | |
| int32_t converted_fp_arg_lengths_[kMaxArgs]; | |
| // The length and flag to store when the AppendBuilder is used as a pre-fence visitor. | |
| int32_t length_with_flag_ = 0u; | |
| }; | |
| inline size_t StringBuilderAppend::Builder::Uint64Length(uint64_t value) { | |
| if (value == 0u) { | |
| return 1u; | |
| } | |
| // Calculate floor(log2(value)). | |
| size_t log2_value = BitSizeOf<uint64_t>() - 1u - CLZ(value); | |
| // Calculate an estimate of floor(log10(value)). | |
| // log10(2) = 0.301029996 > 0.296875 = 19/64 | |
| // floor(log10(v)) == floor(log2(v) * log10(2)) | |
| // >= floor(log2(v) * 19/64) | |
| // >= floor(floor(log2(v)) * 19/64) | |
| // This estimate is no more that one off from the actual value because log2(value) < 64 and thus | |
| // log2(v) * log10(2) - log2(v) * 19/64 < 64*(log10(2) - 19/64) | |
| // for the first approximation and | |
| // log2(v) * 19/64 - floor(log2(v)) * 19/64 < 19/64 | |
| // for the second one. Together, | |
| // 64*(log10(2) - 19/64) + 19/64 = 0.56278 < 1 . | |
| size_t log10_value_estimate = log2_value * 19u / 64u; | |
| static constexpr uint64_t bounds[] = { | |
| UINT64_C(9), | |
| UINT64_C(99), | |
| UINT64_C(999), | |
| UINT64_C(9999), | |
| UINT64_C(99999), | |
| UINT64_C(999999), | |
| UINT64_C(9999999), | |
| UINT64_C(99999999), | |
| UINT64_C(999999999), | |
| UINT64_C(9999999999), | |
| UINT64_C(99999999999), | |
| UINT64_C(999999999999), | |
| UINT64_C(9999999999999), | |
| UINT64_C(99999999999999), | |
| UINT64_C(999999999999999), | |
| UINT64_C(9999999999999999), | |
| UINT64_C(99999999999999999), | |
| UINT64_C(999999999999999999), | |
| UINT64_C(9999999999999999999), | |
| }; | |
| // Add 1 for the lowest digit, add another 1 if the estimate was too low. | |
| DCHECK_LT(log10_value_estimate, std::size(bounds)); | |
| size_t adjustment = (value > bounds[log10_value_estimate]) ? 2u : 1u; | |
| return log10_value_estimate + adjustment; | |
| } | |
| template <typename CharType> | |
| inline CharType* StringBuilderAppend::Builder::AppendFpArg(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| size_t fp_arg_index) const { | |
| DCHECK_LE(fp_arg_index, std::size(converted_fp_args_)); | |
| const uint8_t* src = converted_fp_args_[fp_arg_index]; | |
| size_t length = converted_fp_arg_lengths_[fp_arg_index]; | |
| DCHECK_LE(length, kBinaryToASCIIBufferSize); | |
| DCHECK_LE(length, RemainingSpace(new_string, data)); | |
| return std::copy_n(src, length, data); | |
| } | |
| template <typename CharType, size_t size> | |
| inline CharType* StringBuilderAppend::Builder::AppendLiteral(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| const char (&literal)[size]) { | |
| static_assert(size >= 2, "We need something to append."); | |
| // Literals are zero-terminated. | |
| constexpr size_t length = size - 1u; | |
| DCHECK_EQ(literal[length], '\0'); | |
| DCHECK_LE(length, RemainingSpace(new_string, data)); | |
| for (size_t i = 0; i != length; ++i) { | |
| data[i] = literal[i]; | |
| } | |
| return data + length; | |
| } | |
| template <typename CharType> | |
| inline CharType* StringBuilderAppend::Builder::AppendString(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| ObjPtr<mirror::String> str) { | |
| size_t length = dchecked_integral_cast<size_t>(str->GetLength()); | |
| DCHECK_LE(length, RemainingSpace(new_string, data)); | |
| if (sizeof(CharType) == sizeof(uint8_t) || str->IsCompressed()) { | |
| DCHECK(str->IsCompressed()); | |
| const uint8_t* value = str->GetValueCompressed(); | |
| for (size_t i = 0; i != length; ++i) { | |
| data[i] = value[i]; | |
| } | |
| } else { | |
| const uint16_t* value = str->GetValue(); | |
| for (size_t i = 0; i != length; ++i) { | |
| data[i] = dchecked_integral_cast<CharType>(value[i]); | |
| } | |
| } | |
| return data + length; | |
| } | |
| template <typename CharType> | |
| inline CharType* StringBuilderAppend::Builder::AppendInt64(ObjPtr<mirror::String> new_string, | |
| CharType* data, | |
| int64_t value) { | |
| DCHECK_GE(RemainingSpace(new_string, data), Int64Length(value)); | |
| uint64_t v = static_cast<uint64_t>(value); | |
| if (value < 0) { | |
| *data = '-'; | |
| ++data; | |
| v = -v; | |
| } | |
| size_t length = Uint64Length(v); | |
| // Write the digits from the end, do not write the most significant digit | |
| // in the loop to avoid an unnecessary division. | |
| for (size_t i = 1; i != length; ++i) { | |
| uint64_t digit = v % UINT64_C(10); | |
| v /= UINT64_C(10); | |
| data[length - i] = '0' + static_cast<char>(digit); | |
| } | |
| DCHECK_LE(v, 10u); | |
| *data = '0' + static_cast<char>(v); | |
| return data + length; | |
| } | |
| int32_t StringBuilderAppend::Builder::ConvertFpArgs() { | |
| int32_t fp_args_length = 0u; | |
| const uint32_t* current_arg = args_; | |
| size_t fp_arg_index = 0u; | |
| for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) { | |
| DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast)); | |
| bool fp_arg = false; | |
| ObjPtr<mirror::Object> converter; | |
| switch (static_cast<Argument>(f & kArgMask)) { | |
| case Argument::kString: | |
| case Argument::kBoolean: | |
| case Argument::kChar: | |
| case Argument::kInt: | |
| break; | |
| case Argument::kLong: { | |
| current_arg = AlignUp(current_arg, sizeof(int64_t)); | |
| ++current_arg; // Skip the low word, let the common code skip the high word. | |
| break; | |
| } | |
| case Argument::kFloat: { | |
| fp_arg = true; | |
| float arg = bit_cast<float>(*current_arg); | |
| converter = WellKnownClasses::jdk_internal_math_FloatingDecimal_getBinaryToASCIIConverter_F | |
| ->InvokeStatic<'L', 'F'>(hs_.Self(), arg); | |
| break; | |
| } | |
| case Argument::kDouble: { | |
| fp_arg = true; | |
| current_arg = AlignUp(current_arg, sizeof(int64_t)); | |
| double arg = bit_cast<double>( | |
| static_cast<uint64_t>(current_arg[0]) + (static_cast<uint64_t>(current_arg[1]) << 32)); | |
| converter = WellKnownClasses::jdk_internal_math_FloatingDecimal_getBinaryToASCIIConverter_D | |
| ->InvokeStatic<'L', 'D'>(hs_.Self(), arg); | |
| ++current_arg; // Skip the low word, let the common code skip the high word. | |
| break; | |
| } | |
| case Argument::kStringBuilder: | |
| case Argument::kCharArray: | |
| case Argument::kObject: | |
| LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex | |
| << (f & kArgMask) << " full format: 0x" << std::hex << format_; | |
| UNREACHABLE(); | |
| default: | |
| LOG(FATAL) << "Unexpected arg format: 0x" << std::hex | |
| << (f & kArgMask) << " full format: 0x" << std::hex << format_; | |
| UNREACHABLE(); | |
| } | |
| if (fp_arg) { | |
| // If we see an exception (presumably OOME or SOE), keep it as is, even | |
| // though it may be confusing to see the stack trace for FP argument | |
| // conversion continue at the StringBuilder.toString() invoke location. | |
| DCHECK_EQ(converter == nullptr, hs_.Self()->IsExceptionPending()); | |
| if (UNLIKELY(converter == nullptr)) { | |
| return -1; | |
| } | |
| ArtField* btab_buffer_field = | |
| WellKnownClasses::jdk_internal_math_FloatingDecimal_BinaryToASCIIBuffer_buffer; | |
| int32_t length; | |
| if (converter->GetClass() == btab_buffer_field->GetDeclaringClass()) { | |
| // Call `converter.getChars(converter.buffer)`. | |
| StackHandleScope<1u> hs2(hs_.Self()); | |
| Handle<mirror::CharArray> buffer = | |
| hs2.NewHandle(btab_buffer_field->GetObj<mirror::CharArray>(converter)); | |
| DCHECK(buffer != nullptr); | |
| length = WellKnownClasses::jdk_internal_math_FloatingDecimal_BinaryToASCIIBuffer_getChars | |
| ->InvokeInstance<'I', 'L'>(hs_.Self(), converter, buffer.Get()); | |
| if (UNLIKELY(hs_.Self()->IsExceptionPending())) { | |
| return -1; | |
| } | |
| // The converted string is now at the front of the buffer. | |
| DCHECK_GT(length, 0); | |
| DCHECK_LE(length, buffer->GetLength()); | |
| DCHECK_LE(static_cast<size_t>(length), std::size(converted_fp_args_[0])); | |
| DCHECK(mirror::String::AllASCII(buffer->GetData(), length)); | |
| std::copy_n(buffer->GetData(), length, converted_fp_args_[fp_arg_index]); | |
| } else { | |
| ArtField* ebtab_image_field = WellKnownClasses:: | |
| jdk_internal_math_FloatingDecimal_ExceptionalBinaryToASCIIBuffer_image; | |
| DCHECK(converter->GetClass() == ebtab_image_field->GetDeclaringClass()); | |
| ObjPtr<mirror::String> converted = ebtab_image_field->GetObj<mirror::String>(converter); | |
| DCHECK(converted != nullptr); | |
| length = converted->GetLength(); | |
| if (mirror::kUseStringCompression) { | |
| DCHECK(converted->IsCompressed()); | |
| memcpy(converted_fp_args_[fp_arg_index], converted->GetValueCompressed(), length); | |
| } else { | |
| DCHECK(mirror::String::AllASCII(converted->GetValue(), length)); | |
| std::copy_n(converted->GetValue(), length, converted_fp_args_[fp_arg_index]); | |
| } | |
| } | |
| converted_fp_arg_lengths_[fp_arg_index] = length; | |
| fp_args_length += length; | |
| ++fp_arg_index; | |
| } | |
| ++current_arg; | |
| DCHECK_LE(fp_arg_index, kMaxArgs); | |
| } | |
| return fp_args_length; | |
| } | |
| inline int32_t StringBuilderAppend::Builder::CalculateLengthWithFlag() { | |
| static_assert(static_cast<size_t>(Argument::kEnd) == 0u, "kEnd must be 0."); | |
| bool compressible = mirror::kUseStringCompression; | |
| uint64_t length = 0u; | |
| bool has_fp_args = false; | |
| const uint32_t* current_arg = args_; | |
| for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) { | |
| DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast)); | |
| switch (static_cast<Argument>(f & kArgMask)) { | |
| case Argument::kString: { | |
| Handle<mirror::String> str = | |
| hs_.NewHandle(reinterpret_cast32<mirror::String*>(*current_arg)); | |
| if (str != nullptr) { | |
| length += str->GetLength(); | |
| compressible = compressible && str->IsCompressed(); | |
| } else { | |
| length += kNullLength; | |
| } | |
| break; | |
| } | |
| case Argument::kBoolean: { | |
| length += (*current_arg != 0u) ? kTrueLength : kFalseLength; | |
| break; | |
| } | |
| case Argument::kChar: { | |
| length += 1u; | |
| compressible = compressible && | |
| mirror::String::IsASCII(reinterpret_cast<const uint16_t*>(current_arg)[0]); | |
| break; | |
| } | |
| case Argument::kInt: { | |
| length += Int64Length(static_cast<int32_t>(*current_arg)); | |
| break; | |
| } | |
| case Argument::kLong: { | |
| current_arg = AlignUp(current_arg, sizeof(int64_t)); | |
| length += Int64Length(*reinterpret_cast<const int64_t*>(current_arg)); | |
| ++current_arg; // Skip the low word, let the common code skip the high word. | |
| break; | |
| } | |
| case Argument::kDouble: | |
| current_arg = AlignUp(current_arg, sizeof(int64_t)); | |
| ++current_arg; // Skip the low word, let the common code skip the high word. | |
| FALLTHROUGH_INTENDED; | |
| case Argument::kFloat: | |
| // Conversion shall be performed in a separate pass because it calls back to | |
| // managed code and we need to convert reference arguments to `Handle<>`s first. | |
| has_fp_args = true; | |
| break; | |
| case Argument::kStringBuilder: | |
| case Argument::kCharArray: | |
| case Argument::kObject: | |
| LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex | |
| << (f & kArgMask) << " full format: 0x" << std::hex << format_; | |
| UNREACHABLE(); | |
| default: | |
| LOG(FATAL) << "Unexpected arg format: 0x" << std::hex | |
| << (f & kArgMask) << " full format: 0x" << std::hex << format_; | |
| UNREACHABLE(); | |
| } | |
| ++current_arg; | |
| } | |
| if (UNLIKELY(has_fp_args)) { | |
| // Call Java helpers to convert FP args. | |
| int32_t fp_args_length = ConvertFpArgs(); | |
| if (fp_args_length == -1) { | |
| return -1; | |
| } | |
| DCHECK_GT(fp_args_length, 0); | |
| length += fp_args_length; | |
| } | |
| if (length > std::numeric_limits<int32_t>::max()) { | |
| // We cannot allocate memory for the entire result. | |
| hs_.Self()->ThrowNewException("Ljava/lang/OutOfMemoryError;", | |
| "Out of memory for StringBuilder append."); | |
| return -1; | |
| } | |
| length_with_flag_ = mirror::String::GetFlaggedCount(length, compressible); | |
| return length_with_flag_; | |
| } | |
| template <typename CharType> | |
| inline void StringBuilderAppend::Builder::StoreData(ObjPtr<mirror::String> new_string, | |
| CharType* data) const { | |
| size_t handle_index = 0u; | |
| size_t fp_arg_index = 0u; | |
| const uint32_t* current_arg = args_; | |
| for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) { | |
| DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast)); | |
| switch (static_cast<Argument>(f & kArgMask)) { | |
| case Argument::kString: { | |
| DCHECK_LT(handle_index, hs_.Size()); | |
| ObjPtr<mirror::String> str = | |
| ObjPtr<mirror::String>::DownCast(hs_.GetReference(handle_index)); | |
| ++handle_index; | |
| if (str != nullptr) { | |
| data = AppendString(new_string, data, str); | |
| } else { | |
| data = AppendLiteral(new_string, data, kNull); | |
| } | |
| break; | |
| } | |
| case Argument::kBoolean: { | |
| if (*current_arg != 0u) { | |
| data = AppendLiteral(new_string, data, kTrue); | |
| } else { | |
| data = AppendLiteral(new_string, data, kFalse); | |
| } | |
| break; | |
| } | |
| case Argument::kChar: { | |
| DCHECK_GE(RemainingSpace(new_string, data), 1u); | |
| *data = *reinterpret_cast<const CharType*>(current_arg); | |
| ++data; | |
| break; | |
| } | |
| case Argument::kInt: { | |
| data = AppendInt64(new_string, data, static_cast<int32_t>(*current_arg)); | |
| break; | |
| } | |
| case Argument::kLong: { | |
| current_arg = AlignUp(current_arg, sizeof(int64_t)); | |
| data = AppendInt64(new_string, data, *reinterpret_cast<const int64_t*>(current_arg)); | |
| ++current_arg; // Skip the low word, let the common code skip the high word. | |
| break; | |
| } | |
| case Argument::kDouble: | |
| current_arg = AlignUp(current_arg, sizeof(int64_t)); | |
| ++current_arg; // Skip the low word, let the common code skip the high word. | |
| FALLTHROUGH_INTENDED; | |
| case Argument::kFloat: { | |
| data = AppendFpArg(new_string, data, fp_arg_index); | |
| ++fp_arg_index; | |
| break; | |
| } | |
| case Argument::kStringBuilder: | |
| case Argument::kCharArray: | |
| LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex | |
| << (f & kArgMask) << " full format: 0x" << std::hex << format_; | |
| UNREACHABLE(); | |
| default: | |
| LOG(FATAL) << "Unexpected arg format: 0x" << std::hex | |
| << (f & kArgMask) << " full format: 0x" << std::hex << format_; | |
| UNREACHABLE(); | |
| } | |
| ++current_arg; | |
| DCHECK_LE(fp_arg_index, std::size(converted_fp_args_)); | |
| } | |
| DCHECK_EQ(RemainingSpace(new_string, data), 0u) << std::hex << format_; | |
| } | |
| inline void StringBuilderAppend::Builder::operator()(ObjPtr<mirror::Object> obj, | |
| [[maybe_unused]] size_t usable_size) const { | |
| ObjPtr<mirror::String> new_string = ObjPtr<mirror::String>::DownCast(obj); | |
| new_string->SetCount(length_with_flag_); | |
| if (mirror::String::IsCompressed(length_with_flag_)) { | |
| StoreData(new_string, new_string->GetValueCompressed()); | |
| } else { | |
| StoreData(new_string, new_string->GetValue()); | |
| } | |
| } | |
| ObjPtr<mirror::String> StringBuilderAppend::AppendF(uint32_t format, | |
| const uint32_t* args, | |
| Thread* self) { | |
| Builder builder(format, args, self); | |
| self->AssertNoPendingException(); | |
| int32_t length_with_flag = builder.CalculateLengthWithFlag(); | |
| if (self->IsExceptionPending()) { | |
| return nullptr; | |
| } | |
| gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); | |
| ObjPtr<mirror::String> result = mirror::String::Alloc( | |
| self, length_with_flag, allocator_type, builder); | |
| return result; | |
| } | |
| } // namespace art |