1 /* 2 * Copyright (C) 2017 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 "compact_dex_writer.h" 18 19 #include "android-base/stringprintf.h" 20 #include "base/logging.h" 21 #include "base/time_utils.h" 22 #include "dex/compact_dex_file.h" 23 #include "dex/compact_offset_table.h" 24 #include "dexlayout.h" 25 26 namespace art { 27 28 CompactDexWriter::CompactDexWriter(DexLayout* dex_layout) 29 : DexWriter(dex_layout, /*compute_offsets=*/ true) { 30 CHECK(GetCompactDexLevel() != CompactDexLevel::kCompactDexLevelNone); 31 } 32 33 CompactDexLevel CompactDexWriter::GetCompactDexLevel() const { 34 return dex_layout_->GetOptions().compact_dex_level_; 35 } 36 37 CompactDexWriter::Container::Container(bool dedupe_code_items) 38 : code_item_dedupe_(dedupe_code_items, &data_section_), 39 data_item_dedupe_(/*enabled=*/ true, &data_section_) {} 40 41 uint32_t CompactDexWriter::WriteDebugInfoOffsetTable(Stream* stream) { 42 const uint32_t start_offset = stream->Tell(); 43 // Debug offsets for method indexes. 0 means no debug info. 44 std::vector<uint32_t> debug_info_offsets(header_->MethodIds().Size(), 0u); 45 46 static constexpr InvokeType invoke_types[] = { 47 kDirect, 48 kVirtual 49 }; 50 51 for (InvokeType invoke_type : invoke_types) { 52 for (auto& class_def : header_->ClassDefs()) { 53 // Skip classes that are not defined in this dex file. 54 dex_ir::ClassData* class_data = class_def->GetClassData(); 55 if (class_data == nullptr) { 56 continue; 57 } 58 for (auto& method : *(invoke_type == InvokeType::kDirect 59 ? class_data->DirectMethods() 60 : class_data->VirtualMethods())) { 61 const dex_ir::MethodId* method_id = method.GetMethodId(); 62 dex_ir::CodeItem* code_item = method.GetCodeItem(); 63 if (code_item != nullptr && code_item->DebugInfo() != nullptr) { 64 const uint32_t debug_info_offset = code_item->DebugInfo()->GetOffset(); 65 const uint32_t method_idx = method_id->GetIndex(); 66 if (debug_info_offsets[method_idx] != 0u) { 67 CHECK_EQ(debug_info_offset, debug_info_offsets[method_idx]); 68 } 69 debug_info_offsets[method_idx] = debug_info_offset; 70 } 71 } 72 } 73 } 74 75 std::vector<uint8_t> data; 76 debug_info_base_ = 0u; 77 debug_info_offsets_table_offset_ = 0u; 78 CompactOffsetTable::Build(debug_info_offsets, 79 &data, 80 &debug_info_base_, 81 &debug_info_offsets_table_offset_); 82 // Align the table and write it out. 83 stream->AlignTo(CompactOffsetTable::kAlignment); 84 debug_info_offsets_pos_ = stream->Tell(); 85 stream->Write(data.data(), data.size()); 86 87 // Verify that the whole table decodes as expected and measure average performance. 88 const bool kMeasureAndTestOutput = dex_layout_->GetOptions().verify_output_; 89 if (kMeasureAndTestOutput && !debug_info_offsets.empty()) { 90 uint64_t start_time = NanoTime(); 91 stream->Begin(); 92 CompactOffsetTable::Accessor accessor(stream->Begin() + debug_info_offsets_pos_, 93 debug_info_base_, 94 debug_info_offsets_table_offset_); 95 96 for (size_t i = 0; i < debug_info_offsets.size(); ++i) { 97 CHECK_EQ(accessor.GetOffset(i), debug_info_offsets[i]); 98 } 99 uint64_t end_time = NanoTime(); 100 VLOG(dex) << "Average lookup time (ns) for debug info offsets: " 101 << (end_time - start_time) / debug_info_offsets.size(); 102 } 103 104 return stream->Tell() - start_offset; 105 } 106 107 CompactDexWriter::ScopedDataSectionItem::ScopedDataSectionItem(Stream* stream, 108 dex_ir::Item* item, 109 size_t alignment, 110 Deduper* deduper) 111 : stream_(stream), 112 item_(item), 113 alignment_(alignment), 114 deduper_(deduper), 115 start_offset_(stream->Tell()) { 116 stream_->AlignTo(alignment_); 117 } 118 119 CompactDexWriter::ScopedDataSectionItem::~ScopedDataSectionItem() { 120 // After having written, maybe dedupe the whole code item (excluding padding). 121 const uint32_t deduped_offset = deduper_->Dedupe(start_offset_, 122 stream_->Tell(), 123 item_->GetOffset()); 124 // If we deduped, only use the deduped offset if the alignment matches the required alignment. 125 // Otherwise, return without deduping. 126 if (deduped_offset != Deduper::kDidNotDedupe && IsAlignedParam(deduped_offset, alignment_)) { 127 // Update the IR offset to the offset of the deduped item. 128 item_->SetOffset(deduped_offset); 129 // Clear the written data for the item so that the stream write doesn't abort in the future. 130 stream_->Clear(start_offset_, stream_->Tell() - start_offset_); 131 // Since we deduped, restore the offset to the original position. 132 stream_->Seek(start_offset_); 133 } 134 } 135 136 size_t CompactDexWriter::ScopedDataSectionItem::Written() const { 137 return stream_->Tell() - start_offset_; 138 } 139 140 void CompactDexWriter::WriteCodeItem(Stream* stream, 141 dex_ir::CodeItem* code_item, 142 bool reserve_only) { 143 DCHECK(code_item != nullptr); 144 DCHECK(!reserve_only) << "Not supported because of deduping."; 145 ScopedDataSectionItem data_item(stream, 146 code_item, 147 CompactDexFile::CodeItem::kAlignment, 148 code_item_dedupe_); 149 150 CompactDexFile::CodeItem disk_code_item; 151 152 uint16_t preheader_storage[CompactDexFile::CodeItem::kMaxPreHeaderSize] = {}; 153 uint16_t* preheader_end = preheader_storage + CompactDexFile::CodeItem::kMaxPreHeaderSize; 154 const uint16_t* preheader = disk_code_item.Create( 155 code_item->RegistersSize(), 156 code_item->InsSize(), 157 code_item->OutsSize(), 158 code_item->TriesSize(), 159 code_item->InsnsSize(), 160 preheader_end); 161 const size_t preheader_bytes = (preheader_end - preheader) * sizeof(preheader[0]); 162 163 static constexpr size_t kPayloadInstructionRequiredAlignment = 4; 164 const uint32_t current_code_item_start = stream->Tell() + preheader_bytes; 165 if (!IsAlignedParam(current_code_item_start, kPayloadInstructionRequiredAlignment) || 166 kIsDebugBuild) { 167 // If the preheader is going to make the code unaligned, consider adding 2 bytes of padding 168 // before if required. 169 IterationRange<DexInstructionIterator> instructions = code_item->Instructions(); 170 SafeDexInstructionIterator it(instructions.begin(), instructions.end()); 171 for (; !it.IsErrorState() && it < instructions.end(); ++it) { 172 // In case the instruction goes past the end of the code item, make sure to not process it. 173 if (std::next(it).IsErrorState()) { 174 break; 175 } 176 const Instruction::Code opcode = it->Opcode(); 177 // Payload instructions possibly require special alignment for their data. 178 if (opcode == Instruction::FILL_ARRAY_DATA || 179 opcode == Instruction::PACKED_SWITCH || 180 opcode == Instruction::SPARSE_SWITCH) { 181 stream->Skip( 182 RoundUp(current_code_item_start, kPayloadInstructionRequiredAlignment) - 183 current_code_item_start); 184 break; 185 } 186 } 187 } 188 189 // Write preheader first. 190 stream->Write(reinterpret_cast<const uint8_t*>(preheader), preheader_bytes); 191 // Registered offset is after the preheader. 192 ProcessOffset(stream, code_item); 193 // Avoid using sizeof so that we don't write the fake instruction array at the end of the code 194 // item. 195 stream->Write(&disk_code_item, OFFSETOF_MEMBER(CompactDexFile::CodeItem, insns_)); 196 // Write the instructions. 197 stream->Write(code_item->Insns(), code_item->InsnsSize() * sizeof(uint16_t)); 198 // Write the post instruction data. 199 WriteCodeItemPostInstructionData(stream, code_item, reserve_only); 200 } 201 202 void CompactDexWriter::WriteDebugInfoItem(Stream* stream, dex_ir::DebugInfoItem* debug_info) { 203 ScopedDataSectionItem data_item(stream, 204 debug_info, 205 SectionAlignment(DexFile::kDexTypeDebugInfoItem), 206 data_item_dedupe_); 207 ProcessOffset(stream, debug_info); 208 stream->Write(debug_info->GetDebugInfo(), debug_info->GetDebugInfoSize()); 209 } 210 211 212 CompactDexWriter::Deduper::Deduper(bool enabled, DexContainer::Section* section) 213 : enabled_(enabled), 214 dedupe_map_(/*__n=*/ 32, 215 HashedMemoryRange::HashEqual(section), 216 HashedMemoryRange::HashEqual(section)) {} 217 218 uint32_t CompactDexWriter::Deduper::Dedupe(uint32_t data_start, 219 uint32_t data_end, 220 uint32_t item_offset) { 221 if (!enabled_) { 222 return kDidNotDedupe; 223 } 224 HashedMemoryRange range {data_start, data_end - data_start}; 225 auto existing = dedupe_map_.emplace(range, item_offset); 226 if (!existing.second) { 227 // Failed to insert means we deduped, return the existing item offset. 228 return existing.first->second; 229 } 230 return kDidNotDedupe; 231 } 232 233 void CompactDexWriter::SortDebugInfosByMethodIndex() { 234 static constexpr InvokeType invoke_types[] = { 235 kDirect, 236 kVirtual 237 }; 238 std::map<const dex_ir::DebugInfoItem*, uint32_t> method_idx_map; 239 for (InvokeType invoke_type : invoke_types) { 240 for (auto& class_def : header_->ClassDefs()) { 241 // Skip classes that are not defined in this dex file. 242 dex_ir::ClassData* class_data = class_def->GetClassData(); 243 if (class_data == nullptr) { 244 continue; 245 } 246 for (auto& method : *(invoke_type == InvokeType::kDirect 247 ? class_data->DirectMethods() 248 : class_data->VirtualMethods())) { 249 const dex_ir::MethodId* method_id = method.GetMethodId(); 250 dex_ir::CodeItem* code_item = method.GetCodeItem(); 251 if (code_item != nullptr && code_item->DebugInfo() != nullptr) { 252 const dex_ir::DebugInfoItem* debug_item = code_item->DebugInfo(); 253 method_idx_map.insert(std::make_pair(debug_item, method_id->GetIndex())); 254 } 255 } 256 } 257 } 258 std::sort(header_->DebugInfoItems().begin(), 259 header_->DebugInfoItems().end(), 260 [&](const std::unique_ptr<dex_ir::DebugInfoItem>& a, 261 const std::unique_ptr<dex_ir::DebugInfoItem>& b) { 262 auto it_a = method_idx_map.find(a.get()); 263 auto it_b = method_idx_map.find(b.get()); 264 uint32_t idx_a = it_a != method_idx_map.end() ? it_a->second : 0u; 265 uint32_t idx_b = it_b != method_idx_map.end() ? it_b->second : 0u; 266 return idx_a < idx_b; 267 }); 268 } 269 270 void CompactDexWriter::WriteHeader(Stream* stream) { 271 CompactDexFile::Header header; 272 CompactDexFile::WriteMagic(&header.magic_[0]); 273 CompactDexFile::WriteCurrentVersion(&header.magic_[0]); 274 header.checksum_ = header_->Checksum(); 275 std::copy_n(header_->Signature(), DexFile::kSha1DigestSize, header.signature_); 276 header.file_size_ = header_->FileSize(); 277 // Since we are not necessarily outputting the same format as the input, avoid using the stored 278 // header size. 279 header.header_size_ = GetHeaderSize(); 280 header.endian_tag_ = header_->EndianTag(); 281 header.link_size_ = header_->LinkSize(); 282 header.link_off_ = header_->LinkOffset(); 283 header.map_off_ = header_->MapListOffset(); 284 header.string_ids_size_ = header_->StringIds().Size(); 285 header.string_ids_off_ = header_->StringIds().GetOffset(); 286 header.type_ids_size_ = header_->TypeIds().Size(); 287 header.type_ids_off_ = header_->TypeIds().GetOffset(); 288 header.proto_ids_size_ = header_->ProtoIds().Size(); 289 header.proto_ids_off_ = header_->ProtoIds().GetOffset(); 290 header.field_ids_size_ = header_->FieldIds().Size(); 291 header.field_ids_off_ = header_->FieldIds().GetOffset(); 292 header.method_ids_size_ = header_->MethodIds().Size(); 293 header.method_ids_off_ = header_->MethodIds().GetOffset(); 294 header.class_defs_size_ = header_->ClassDefs().Size(); 295 header.class_defs_off_ = header_->ClassDefs().GetOffset(); 296 header.data_size_ = header_->DataSize(); 297 header.data_off_ = header_->DataOffset(); 298 header.owned_data_begin_ = owned_data_begin_; 299 header.owned_data_end_ = owned_data_end_; 300 301 // Compact dex specific flags. 302 header.debug_info_offsets_pos_ = debug_info_offsets_pos_; 303 header.debug_info_offsets_table_offset_ = debug_info_offsets_table_offset_; 304 header.debug_info_base_ = debug_info_base_; 305 header.feature_flags_ = 0u; 306 // In cases where apps are converted to cdex during install, maintain feature flags so that 307 // the verifier correctly verifies apps that aren't targetting default methods. 308 if (header_->SupportDefaultMethods()) { 309 header.feature_flags_ |= static_cast<uint32_t>(CompactDexFile::FeatureFlags::kDefaultMethods); 310 } 311 stream->Seek(0); 312 stream->Overwrite(reinterpret_cast<uint8_t*>(&header), sizeof(header)); 313 } 314 315 size_t CompactDexWriter::GetHeaderSize() const { 316 return sizeof(CompactDexFile::Header); 317 } 318 319 void CompactDexWriter::WriteStringData(Stream* stream, dex_ir::StringData* string_data) { 320 ScopedDataSectionItem data_item(stream, 321 string_data, 322 SectionAlignment(DexFile::kDexTypeStringDataItem), 323 data_item_dedupe_); 324 ProcessOffset(stream, string_data); 325 stream->WriteUleb128(CountModifiedUtf8Chars(string_data->Data())); 326 stream->Write(string_data->Data(), strlen(string_data->Data())); 327 // Skip null terminator (already zeroed out, no need to write). 328 stream->Skip(1); 329 } 330 331 bool CompactDexWriter::CanGenerateCompactDex(std::string* error_msg) { 332 static constexpr InvokeType invoke_types[] = { 333 kDirect, 334 kVirtual 335 }; 336 std::vector<bool> saw_method_id(header_->MethodIds().Size(), false); 337 std::vector<dex_ir::CodeItem*> method_id_code_item(header_->MethodIds().Size(), nullptr); 338 std::vector<dex_ir::DebugInfoItem*> method_id_debug_info(header_->MethodIds().Size(), nullptr); 339 for (InvokeType invoke_type : invoke_types) { 340 for (auto& class_def : header_->ClassDefs()) { 341 // Skip classes that are not defined in this dex file. 342 dex_ir::ClassData* class_data = class_def->GetClassData(); 343 if (class_data == nullptr) { 344 continue; 345 } 346 for (auto& method : *(invoke_type == InvokeType::kDirect 347 ? class_data->DirectMethods() 348 : class_data->VirtualMethods())) { 349 const uint32_t idx = method.GetMethodId()->GetIndex(); 350 dex_ir::CodeItem* code_item = method.GetCodeItem(); 351 dex_ir:: DebugInfoItem* debug_info_item = nullptr; 352 if (code_item != nullptr) { 353 debug_info_item = code_item->DebugInfo(); 354 } 355 if (saw_method_id[idx]) { 356 if (method_id_code_item[idx] != code_item) { 357 *error_msg = android::base::StringPrintf("Conflicting code item for method id %u", 358 idx); 359 // Conflicting info, abort generation. 360 return false; 361 } 362 if (method_id_debug_info[idx] != debug_info_item) { 363 *error_msg = android::base::StringPrintf("Conflicting debug info for method id %u", 364 idx); 365 // Conflicting info, abort generation. 366 return false; 367 } 368 } 369 method_id_code_item[idx] = code_item; 370 method_id_debug_info[idx] = debug_info_item; 371 saw_method_id[idx] = true; 372 } 373 } 374 } 375 return true; 376 } 377 378 bool CompactDexWriter::Write(DexContainer* output, std::string* error_msg) { 379 DCHECK(error_msg != nullptr); 380 CHECK(compute_offsets_); 381 CHECK(output->IsCompactDexContainer()); 382 383 if (!CanGenerateCompactDex(error_msg)) { 384 return false; 385 } 386 387 Container* const container = down_cast<Container*>(output); 388 // For now, use the same stream for both data and metadata. 389 Stream temp_main_stream(output->GetMainSection()); 390 CHECK_EQ(output->GetMainSection()->Size(), 0u); 391 Stream temp_data_stream(output->GetDataSection()); 392 Stream* main_stream = &temp_main_stream; 393 Stream* data_stream = &temp_data_stream; 394 395 // We want offset 0 to be reserved for null, seek to the data section alignment or the end of the 396 // section. 397 data_stream->Seek(std::max( 398 static_cast<uint32_t>(output->GetDataSection()->Size()), 399 kDataSectionAlignment)); 400 code_item_dedupe_ = &container->code_item_dedupe_; 401 data_item_dedupe_ = &container->data_item_dedupe_; 402 403 // Starting offset is right after the header. 404 main_stream->Seek(GetHeaderSize()); 405 406 // Based on: https://source.android.com/devices/tech/dalvik/dex-format 407 // Since the offsets may not be calculated already, the writing must be done in the correct order. 408 const uint32_t string_ids_offset = main_stream->Tell(); 409 WriteStringIds(main_stream, /*reserve_only=*/ true); 410 WriteTypeIds(main_stream); 411 const uint32_t proto_ids_offset = main_stream->Tell(); 412 WriteProtoIds(main_stream, /*reserve_only=*/ true); 413 WriteFieldIds(main_stream); 414 WriteMethodIds(main_stream); 415 const uint32_t class_defs_offset = main_stream->Tell(); 416 WriteClassDefs(main_stream, /*reserve_only=*/ true); 417 const uint32_t call_site_ids_offset = main_stream->Tell(); 418 WriteCallSiteIds(main_stream, /*reserve_only=*/ true); 419 WriteMethodHandles(main_stream); 420 421 if (compute_offsets_) { 422 // Data section. 423 data_stream->AlignTo(kDataSectionAlignment); 424 } 425 owned_data_begin_ = data_stream->Tell(); 426 427 // Write code item first to minimize the space required for encoded methods. 428 // For cdex, the code items don't depend on the debug info. 429 WriteCodeItems(data_stream, /*reserve_only=*/ false); 430 431 // Sort the debug infos by method index order, this reduces size by ~0.1% by reducing the size of 432 // the debug info offset table. 433 SortDebugInfosByMethodIndex(); 434 WriteDebugInfoItems(data_stream); 435 436 WriteEncodedArrays(data_stream); 437 WriteAnnotations(data_stream); 438 WriteAnnotationSets(data_stream); 439 WriteAnnotationSetRefs(data_stream); 440 WriteAnnotationsDirectories(data_stream); 441 WriteTypeLists(data_stream); 442 WriteClassDatas(data_stream); 443 WriteStringDatas(data_stream); 444 WriteHiddenapiClassData(data_stream); 445 446 // Write delayed id sections that depend on data sections. 447 { 448 Stream::ScopedSeek seek(main_stream, string_ids_offset); 449 WriteStringIds(main_stream, /*reserve_only=*/ false); 450 } 451 { 452 Stream::ScopedSeek seek(main_stream, proto_ids_offset); 453 WriteProtoIds(main_stream, /*reserve_only=*/ false); 454 } 455 { 456 Stream::ScopedSeek seek(main_stream, class_defs_offset); 457 WriteClassDefs(main_stream, /*reserve_only=*/ false); 458 } 459 { 460 Stream::ScopedSeek seek(main_stream, call_site_ids_offset); 461 WriteCallSiteIds(main_stream, /*reserve_only=*/ false); 462 } 463 464 // Write the map list. 465 if (compute_offsets_) { 466 data_stream->AlignTo(SectionAlignment(DexFile::kDexTypeMapList)); 467 header_->SetMapListOffset(data_stream->Tell()); 468 } else { 469 data_stream->Seek(header_->MapListOffset()); 470 } 471 472 // Map items are included in the data section. 473 GenerateAndWriteMapItems(data_stream); 474 475 // Write link data if it exists. 476 const std::vector<uint8_t>& link_data = header_->LinkData(); 477 if (link_data.size() > 0) { 478 CHECK_EQ(header_->LinkSize(), static_cast<uint32_t>(link_data.size())); 479 if (compute_offsets_) { 480 header_->SetLinkOffset(data_stream->Tell()); 481 } else { 482 data_stream->Seek(header_->LinkOffset()); 483 } 484 data_stream->Write(&link_data[0], link_data.size()); 485 } 486 487 // Write debug info offset table last to make dex file verifier happy. 488 WriteDebugInfoOffsetTable(data_stream); 489 490 data_stream->AlignTo(kDataSectionAlignment); 491 owned_data_end_ = data_stream->Tell(); 492 if (compute_offsets_) { 493 header_->SetDataSize(data_stream->Tell()); 494 if (header_->DataSize() != 0) { 495 // Offset must be zero when the size is zero. 496 main_stream->AlignTo(kDataSectionAlignment); 497 // For now, default to saying the data is right after the main stream. 498 header_->SetDataOffset(main_stream->Tell()); 499 } else { 500 header_->SetDataOffset(0u); 501 } 502 } 503 504 // Write header last. 505 if (compute_offsets_) { 506 header_->SetFileSize(main_stream->Tell()); 507 } 508 WriteHeader(main_stream); 509 510 // Trim sections to make sure they are sized properly. 511 output->GetMainSection()->Resize(header_->FileSize()); 512 output->GetDataSection()->Resize(data_stream->Tell()); 513 514 if (dex_layout_->GetOptions().update_checksum_) { 515 // Compute the cdex section (also covers the used part of the data section). 516 header_->SetChecksum(CompactDexFile::CalculateChecksum(output->GetMainSection()->Begin(), 517 output->GetMainSection()->Size(), 518 output->GetDataSection()->Begin(), 519 output->GetDataSection()->Size())); 520 // Rewrite the header with the calculated checksum. 521 WriteHeader(main_stream); 522 } 523 524 // Clear the dedupe to prevent interdex code item deduping. This does not currently work well with 525 // dex2oat's class unloading. The issue is that verification encounters quickened opcodes after 526 // the first dex gets unloaded. 527 code_item_dedupe_->Clear(); 528 529 return true; 530 } 531 532 std::unique_ptr<DexContainer> CompactDexWriter::CreateDexContainer() const { 533 return std::unique_ptr<DexContainer>( 534 new CompactDexWriter::Container(dex_layout_->GetOptions().dedupe_code_items_)); 535 } 536 537 } // namespace art 538