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/string-alloc-inl.h"
24 #include "obj_ptr-inl.h"
25 #include "runtime.h"
26 
27 namespace art {
28 
29 class StringBuilderAppend::Builder {
30  public:
Builder(uint32_t format,const uint32_t * args,Thread * self)31   Builder(uint32_t format, const uint32_t* args, Thread* self)
32       : format_(format),
33         args_(args),
34         hs_(self) {}
35 
36   int32_t CalculateLengthWithFlag() REQUIRES_SHARED(Locks::mutator_lock_);
37 
38   void operator()(ObjPtr<mirror::Object> obj, size_t usable_size) const
39       REQUIRES_SHARED(Locks::mutator_lock_);
40 
41  private:
42   static size_t Uint64Length(uint64_t value);
43 
Int64Length(int64_t value)44   static size_t Int64Length(int64_t value) {
45     uint64_t v = static_cast<uint64_t>(value);
46     return (value >= 0) ? Uint64Length(v) : 1u + Uint64Length(-v);
47   }
48 
RemainingSpace(ObjPtr<mirror::String> new_string,const uint8_t * data)49   static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint8_t* data)
50       REQUIRES_SHARED(Locks::mutator_lock_) {
51     DCHECK(new_string->IsCompressed());
52     DCHECK_GE(new_string->GetLength(), data - new_string->GetValueCompressed());
53     return new_string->GetLength() - (data - new_string->GetValueCompressed());
54   }
55 
RemainingSpace(ObjPtr<mirror::String> new_string,const uint16_t * data)56   static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint16_t* data)
57       REQUIRES_SHARED(Locks::mutator_lock_) {
58     DCHECK(!new_string->IsCompressed());
59     DCHECK_GE(new_string->GetLength(), data - new_string->GetValue());
60     return new_string->GetLength() - (data - new_string->GetValue());
61   }
62 
63   template <typename CharType, size_t size>
64   static CharType* AppendLiteral(ObjPtr<mirror::String> new_string,
65                                  CharType* data,
66                                  const char (&literal)[size]) REQUIRES_SHARED(Locks::mutator_lock_);
67 
68   template <typename CharType>
69   static CharType* AppendString(ObjPtr<mirror::String> new_string,
70                                 CharType* data,
71                                 ObjPtr<mirror::String> str) REQUIRES_SHARED(Locks::mutator_lock_);
72 
73   template <typename CharType>
74   static CharType* AppendInt64(ObjPtr<mirror::String> new_string,
75                                CharType* data,
76                                int64_t value) REQUIRES_SHARED(Locks::mutator_lock_);
77 
78   template <typename CharType>
79   void StoreData(ObjPtr<mirror::String> new_string, CharType* data) const
80       REQUIRES_SHARED(Locks::mutator_lock_);
81 
82   static constexpr char kNull[] = "null";
83   static constexpr size_t kNullLength = sizeof(kNull) - 1u;
84   static constexpr char kTrue[] = "true";
85   static constexpr size_t kTrueLength = sizeof(kTrue) - 1u;
86   static constexpr char kFalse[] = "false";
87   static constexpr size_t kFalseLength = sizeof(kFalse) - 1u;
88 
89   // The format and arguments to append.
90   const uint32_t format_;
91   const uint32_t* const args_;
92 
93   // References are moved to the handle scope during CalculateLengthWithFlag().
94   StackHandleScope<kMaxArgs> hs_;
95 
96   // The length and flag to store when the AppendBuilder is used as a pre-fence visitor.
97   int32_t length_with_flag_ = 0u;
98 };
99 
Uint64Length(uint64_t value)100 inline size_t StringBuilderAppend::Builder::Uint64Length(uint64_t value)  {
101   if (value == 0u) {
102     return 1u;
103   }
104   // Calculate floor(log2(value)).
105   size_t log2_value = BitSizeOf<uint64_t>() - 1u - CLZ(value);
106   // Calculate an estimate of floor(log10(value)).
107   //   log10(2) = 0.301029996 > 0.296875 = 19/64
108   //   floor(log10(v)) == floor(log2(v) * log10(2))
109   //                   >= floor(log2(v) * 19/64)
110   //                   >= floor(floor(log2(v)) * 19/64)
111   // This estimate is no more that one off from the actual value because log2(value) < 64 and thus
112   //   log2(v) * log10(2) - log2(v) * 19/64 < 64*(log10(2) - 19/64)
113   // for the first approximation and
114   //   log2(v) * 19/64 - floor(log2(v)) * 19/64 < 19/64
115   // for the second one. Together,
116   //   64*(log10(2) - 19/64) + 19/64 = 0.56278 < 1 .
117   size_t log10_value_estimate = log2_value * 19u / 64u;
118   static constexpr uint64_t bounds[] = {
119       UINT64_C(9),
120       UINT64_C(99),
121       UINT64_C(999),
122       UINT64_C(9999),
123       UINT64_C(99999),
124       UINT64_C(999999),
125       UINT64_C(9999999),
126       UINT64_C(99999999),
127       UINT64_C(999999999),
128       UINT64_C(9999999999),
129       UINT64_C(99999999999),
130       UINT64_C(999999999999),
131       UINT64_C(9999999999999),
132       UINT64_C(99999999999999),
133       UINT64_C(999999999999999),
134       UINT64_C(9999999999999999),
135       UINT64_C(99999999999999999),
136       UINT64_C(999999999999999999),
137       UINT64_C(9999999999999999999),
138   };
139   // Add 1 for the lowest digit, add another 1 if the estimate was too low.
140   DCHECK_LT(log10_value_estimate, std::size(bounds));
141   size_t adjustment = (value > bounds[log10_value_estimate]) ? 2u : 1u;
142   return log10_value_estimate + adjustment;
143 }
144 
145 template <typename CharType, size_t size>
AppendLiteral(ObjPtr<mirror::String> new_string,CharType * data,const char (& literal)[size])146 inline CharType* StringBuilderAppend::Builder::AppendLiteral(ObjPtr<mirror::String> new_string,
147                                                              CharType* data,
148                                                              const char (&literal)[size]) {
149   static_assert(size >= 2, "We need something to append.");
150 
151   // Literals are zero-terminated.
152   constexpr size_t length = size - 1u;
153   DCHECK_EQ(literal[length], '\0');
154 
155   DCHECK_LE(length, RemainingSpace(new_string, data));
156   for (size_t i = 0; i != length; ++i) {
157     data[i] = literal[i];
158   }
159   return data + length;
160 }
161 
162 template <typename CharType>
AppendString(ObjPtr<mirror::String> new_string,CharType * data,ObjPtr<mirror::String> str)163 inline CharType* StringBuilderAppend::Builder::AppendString(ObjPtr<mirror::String> new_string,
164                                                             CharType* data,
165                                                             ObjPtr<mirror::String> str) {
166   size_t length = dchecked_integral_cast<size_t>(str->GetLength());
167   DCHECK_LE(length, RemainingSpace(new_string, data));
168   if (sizeof(CharType) == sizeof(uint8_t) || str->IsCompressed()) {
169     DCHECK(str->IsCompressed());
170     const uint8_t* value = str->GetValueCompressed();
171     for (size_t i = 0; i != length; ++i) {
172       data[i] = value[i];
173     }
174   } else {
175     const uint16_t* value = str->GetValue();
176     for (size_t i = 0; i != length; ++i) {
177       data[i] = dchecked_integral_cast<CharType>(value[i]);
178     }
179   }
180   return data + length;
181 }
182 
183 template <typename CharType>
AppendInt64(ObjPtr<mirror::String> new_string,CharType * data,int64_t value)184 inline CharType* StringBuilderAppend::Builder::AppendInt64(ObjPtr<mirror::String> new_string,
185                                                            CharType* data,
186                                                            int64_t value) {
187   DCHECK_GE(RemainingSpace(new_string, data), Int64Length(value));
188   uint64_t v = static_cast<uint64_t>(value);
189   if (value < 0) {
190     *data = '-';
191     ++data;
192     v = -v;
193   }
194   size_t length = Uint64Length(v);
195   // Write the digits from the end, do not write the most significant digit
196   // in the loop to avoid an unnecessary division.
197   for (size_t i = 1; i != length; ++i) {
198     uint64_t digit = v % UINT64_C(10);
199     v /= UINT64_C(10);
200     data[length - i] = '0' + static_cast<char>(digit);
201   }
202   DCHECK_LE(v, 10u);
203   *data = '0' + static_cast<char>(v);
204   return data + length;
205 }
206 
CalculateLengthWithFlag()207 inline int32_t StringBuilderAppend::Builder::CalculateLengthWithFlag() {
208   static_assert(static_cast<size_t>(Argument::kEnd) == 0u, "kEnd must be 0.");
209   bool compressible = mirror::kUseStringCompression;
210   uint64_t length = 0u;
211   const uint32_t* current_arg = args_;
212   for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) {
213     DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast));
214     switch (static_cast<Argument>(f & kArgMask)) {
215       case Argument::kString: {
216         Handle<mirror::String> str =
217             hs_.NewHandle(reinterpret_cast32<mirror::String*>(*current_arg));
218         if (str != nullptr) {
219           length += str->GetLength();
220           compressible = compressible && str->IsCompressed();
221         } else {
222           length += kNullLength;
223         }
224         break;
225       }
226       case Argument::kBoolean: {
227         length += (*current_arg != 0u) ? kTrueLength : kFalseLength;
228         break;
229       }
230       case Argument::kChar: {
231         length += 1u;
232         compressible = compressible &&
233             mirror::String::IsASCII(reinterpret_cast<const uint16_t*>(current_arg)[0]);
234         break;
235       }
236       case Argument::kInt: {
237         length += Int64Length(static_cast<int32_t>(*current_arg));
238         break;
239       }
240       case Argument::kLong: {
241         current_arg = AlignUp(current_arg, sizeof(int64_t));
242         length += Int64Length(*reinterpret_cast<const int64_t*>(current_arg));
243         ++current_arg;  // Skip the low word, let the common code skip the high word.
244         break;
245       }
246 
247       case Argument::kStringBuilder:
248       case Argument::kCharArray:
249       case Argument::kObject:
250       case Argument::kFloat:
251       case Argument::kDouble:
252         LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex
253             << (f & kArgMask) << " full format: 0x" << std::hex << format_;
254         UNREACHABLE();
255       default:
256         LOG(FATAL) << "Unexpected arg format: 0x" << std::hex
257             << (f & kArgMask) << " full format: 0x" << std::hex << format_;
258         UNREACHABLE();
259     }
260     ++current_arg;
261     DCHECK_LE(hs_.NumberOfReferences(), kMaxArgs);
262   }
263 
264   if (length > std::numeric_limits<int32_t>::max()) {
265     // We cannot allocate memory for the entire result.
266     hs_.Self()->ThrowNewException("Ljava/lang/OutOfMemoryError;",
267                                   "Out of memory for StringBuilder append.");
268     return -1;
269   }
270 
271   length_with_flag_ = mirror::String::GetFlaggedCount(length, compressible);
272   return length_with_flag_;
273 }
274 
275 template <typename CharType>
StoreData(ObjPtr<mirror::String> new_string,CharType * data) const276 inline void StringBuilderAppend::Builder::StoreData(ObjPtr<mirror::String> new_string,
277                                                     CharType* data) const {
278   size_t handle_index = 0u;
279   const uint32_t* current_arg = args_;
280   for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) {
281     DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast));
282     switch (static_cast<Argument>(f & kArgMask)) {
283       case Argument::kString: {
284         ObjPtr<mirror::String> str =
285             ObjPtr<mirror::String>::DownCast(hs_.GetReference(handle_index));
286         ++handle_index;
287         if (str != nullptr) {
288           data = AppendString(new_string, data, str);
289         } else {
290           data = AppendLiteral(new_string, data, kNull);
291         }
292         break;
293       }
294       case Argument::kBoolean: {
295         if (*current_arg != 0u) {
296           data = AppendLiteral(new_string, data, kTrue);
297         } else {
298           data = AppendLiteral(new_string, data, kFalse);
299         }
300         break;
301       }
302       case Argument::kChar: {
303         DCHECK_GE(RemainingSpace(new_string, data), 1u);
304         *data = *reinterpret_cast<const CharType*>(current_arg);
305         ++data;
306         break;
307       }
308       case Argument::kInt: {
309         data = AppendInt64(new_string, data, static_cast<int32_t>(*current_arg));
310         break;
311       }
312       case Argument::kLong: {
313         current_arg = AlignUp(current_arg, sizeof(int64_t));
314         data = AppendInt64(new_string, data, *reinterpret_cast<const int64_t*>(current_arg));
315         ++current_arg;  // Skip the low word, let the common code skip the high word.
316         break;
317       }
318 
319       case Argument::kStringBuilder:
320       case Argument::kCharArray:
321       case Argument::kFloat:
322       case Argument::kDouble:
323         LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex
324             << (f & kArgMask) << " full format: 0x" << std::hex << format_;
325         UNREACHABLE();
326       default:
327         LOG(FATAL) << "Unexpected arg format: 0x" << std::hex
328             << (f & kArgMask) << " full format: 0x" << std::hex << format_;
329         UNREACHABLE();
330     }
331     ++current_arg;
332     DCHECK_LE(handle_index, hs_.NumberOfReferences());
333   }
334   DCHECK_EQ(RemainingSpace(new_string, data), 0u) << std::hex << format_;
335 }
336 
operator ()(ObjPtr<mirror::Object> obj,size_t usable_size ATTRIBUTE_UNUSED) const337 inline void StringBuilderAppend::Builder::operator()(ObjPtr<mirror::Object> obj,
338                                                      size_t usable_size ATTRIBUTE_UNUSED) const {
339   ObjPtr<mirror::String> new_string = ObjPtr<mirror::String>::DownCast(obj);
340   new_string->SetCount(length_with_flag_);
341   if (mirror::String::IsCompressed(length_with_flag_)) {
342     StoreData(new_string, new_string->GetValueCompressed());
343   } else {
344     StoreData(new_string, new_string->GetValue());
345   }
346 }
347 
AppendF(uint32_t format,const uint32_t * args,Thread * self)348 ObjPtr<mirror::String> StringBuilderAppend::AppendF(uint32_t format,
349                                                     const uint32_t* args,
350                                                     Thread* self) {
351   Builder builder(format, args, self);
352   self->AssertNoPendingException();
353   int32_t length_with_flag = builder.CalculateLengthWithFlag();
354   if (self->IsExceptionPending()) {
355     return nullptr;
356   }
357   gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator();
358   ObjPtr<mirror::String> result = mirror::String::Alloc(
359       self, length_with_flag, allocator_type, builder);
360 
361   return result;
362 }
363 
364 }  // namespace art
365