Add layout scheme to dexlayout for dex file reordering.

Currently takes startup classes from profile and groups them together
with the lowest class indexes. Moves the ClassDef, ClassData, and
CodeItem sections.

Results gathered from 5 second systrace of app startup (no other input):
Maps
base.vdex - 24.70MB -> 19.35MB (30.50MB file size)
base.odex - 13.22MB -> 12.82MB (13.22MB file size)
Running time of dex2oat: 27.5s -> 37.1s

Photos
base.vdex - 12.98MB ->  9.77MB (15.10MB file size)
base.odex -  6.84MB ->  6.24MB ( 6.84MB file size)
Running time of dex2oat: 15.6s -> 19.9s

Plus
base.vdex - 14.09MB -> 13.29MB (16.72MB file size)
base.odex -  2.47MB ->  2.47MB ( 2.47MB file size)
Running time of dex2oat: 14.1s -> 18.5s

Performance and memory tracking bug: b/33017139

Test: mm test-art-host-gtest-dexlayout_test
Bug: 29921113
Change-Id: Ib500ed353d71a606e2db0dd80378750c5f7b8e33

5 files changed, 268 insertions, 12 deletions

diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index e52e502ecc..20b5bba0ed 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -1480,13 +1480,15 @@ class Dex2Oat FINAL {
         // Unzip or copy dex files straight to the oat file.
         std::unique_ptr<MemMap> opened_dex_files_map;
         std::vector<std::unique_ptr<const DexFile>> opened_dex_files;
+        // Dexlayout verifies the dex file, so disable dex file verification in that case.
+        bool verify = compiler_options_->GetCompilerFilter() != CompilerFilter::kLayoutProfile;
         if (!oat_writers_[i]->WriteAndOpenDexFiles(
             kIsVdexEnabled ? vdex_files_[i].get() : oat_files_[i].get(),
             rodata_.back(),
             instruction_set_,
             instruction_set_features_.get(),
             key_value_store_.get(),
-            /* verify */ true,
+            verify,
             &opened_dex_files_map,
             &opened_dex_files)) {
           return false;
diff --git a/dex2oat/dex2oat_test.cc b/dex2oat/dex2oat_test.cc
index 2f34019d06..714a58c8e5 100644
--- a/dex2oat/dex2oat_test.cc
+++ b/dex2oat/dex2oat_test.cc
@@ -552,8 +552,7 @@ TEST_F(Dex2oatVeryLargeTest, UseVeryLarge) {
   RunTest(CompilerFilter::kSpeed, true, { "--very-large-app-threshold=100" });
 }
 
-static const char kDexFileLayoutInputProfile[] =
-    "cHJvADAwMgABAAsAAAABAPUpbf5jbGFzc2VzLmRleAEA";
+static const char kDexFileLayoutInputProfile[] = "cHJvADAwMgABAAwAAQABAOqMEeFEZXhOb09hdC5qYXIBAAEA";
 
 static void WriteFileBase64(const char* base64, const char* location) {
   // Decode base64.
@@ -608,11 +607,26 @@ class Dex2oatLayoutTest : public Dex2oatTest {
                                                      &error_msg));
     ASSERT_TRUE(odex_file.get() != nullptr) << error_msg;
 
+    const char* location = dex_location.c_str();
+    std::vector<std::unique_ptr<const DexFile>> dex_files;
+    ASSERT_TRUE(DexFile::Open(location, location, true, &error_msg, &dex_files));
+    EXPECT_EQ(dex_files.size(), 1U);
+    std::unique_ptr<const DexFile>& old_dex_file = dex_files[0];
+
     for (const OatDexFile* oat_dex_file : odex_file->GetOatDexFiles()) {
-      std::unique_ptr<const DexFile> dex_file = oat_dex_file->OpenDexFile(&error_msg);
-      ASSERT_TRUE(dex_file != nullptr);
-      uint32_t class_def_count = dex_file->NumClassDefs();
+      std::unique_ptr<const DexFile> new_dex_file = oat_dex_file->OpenDexFile(&error_msg);
+      ASSERT_TRUE(new_dex_file != nullptr);
+      uint32_t class_def_count = new_dex_file->NumClassDefs();
       ASSERT_LT(class_def_count, std::numeric_limits<uint16_t>::max());
+      ASSERT_GE(class_def_count, 2U);
+
+      // The new layout swaps the classes at indexes 0 and 1.
+      std::string old_class0 = old_dex_file->PrettyType(old_dex_file->GetClassDef(0).class_idx_);
+      std::string old_class1 = old_dex_file->PrettyType(old_dex_file->GetClassDef(1).class_idx_);
+      std::string new_class0 = new_dex_file->PrettyType(new_dex_file->GetClassDef(0).class_idx_);
+      std::string new_class1 = new_dex_file->PrettyType(new_dex_file->GetClassDef(1).class_idx_);
+      EXPECT_EQ(old_class0, new_class1);
+      EXPECT_EQ(old_class1, new_class0);
     }
 
     EXPECT_EQ(odex_file->GetCompilerFilter(), CompilerFilter::kLayoutProfile);
diff --git a/dexlayout/dexlayout.cc b/dexlayout/dexlayout.cc
index 634bb633c9..cfe48378ae 100644
--- a/dexlayout/dexlayout.cc
+++ b/dexlayout/dexlayout.cc
@@ -1486,6 +1486,153 @@ void DexLayout::DumpDexFile() {
   }
 }
 
+std::vector<dex_ir::ClassDef*> DexLayout::LayoutClassDefsAndClassData(const DexFile* dex_file) {
+  std::vector<dex_ir::ClassDef*> new_class_def_order;
+  for (std::unique_ptr<dex_ir::ClassDef>& class_def : header_->GetCollections().ClassDefs()) {
+    dex::TypeIndex type_idx(class_def->ClassType()->GetIndex());
+    if (info_->ContainsClass(*dex_file, type_idx)) {
+      new_class_def_order.push_back(class_def.get());
+    }
+  }
+  for (std::unique_ptr<dex_ir::ClassDef>& class_def : header_->GetCollections().ClassDefs()) {
+    dex::TypeIndex type_idx(class_def->ClassType()->GetIndex());
+    if (!info_->ContainsClass(*dex_file, type_idx)) {
+      new_class_def_order.push_back(class_def.get());
+    }
+  }
+  uint32_t class_defs_offset = header_->GetCollections().ClassDefsOffset();
+  uint32_t class_data_offset = header_->GetCollections().ClassDatasOffset();
+  for (uint32_t i = 0; i < new_class_def_order.size(); ++i) {
+    dex_ir::ClassDef* class_def = new_class_def_order[i];
+    class_def->SetIndex(i);
+    class_def->SetOffset(class_defs_offset);
+    class_defs_offset += dex_ir::ClassDef::ItemSize();
+    if (class_def->GetClassData() != nullptr) {
+      class_def->GetClassData()->SetOffset(class_data_offset);
+      class_data_offset += class_def->GetClassData()->GetSize();
+    }
+  }
+  return new_class_def_order;
+}
+
+int32_t DexLayout::LayoutCodeItems(std::vector<dex_ir::ClassDef*> new_class_def_order) {
+  int32_t diff = 0;
+  uint32_t offset = header_->GetCollections().CodeItemsOffset();
+  for (dex_ir::ClassDef* class_def : new_class_def_order) {
+    dex_ir::ClassData* class_data = class_def->GetClassData();
+    if (class_data != nullptr) {
+      class_data->SetOffset(class_data->GetOffset() + diff);
+      for (auto& method : *class_data->DirectMethods()) {
+        dex_ir::CodeItem* code_item = method->GetCodeItem();
+        if (code_item != nullptr) {
+          diff += UnsignedLeb128Size(offset) - UnsignedLeb128Size(code_item->GetOffset());
+          code_item->SetOffset(offset);
+          offset += RoundUp(code_item->GetSize(), 4);
+        }
+      }
+      for (auto& method : *class_data->VirtualMethods()) {
+        dex_ir::CodeItem* code_item = method->GetCodeItem();
+        if (code_item != nullptr) {
+          diff += UnsignedLeb128Size(offset) - UnsignedLeb128Size(code_item->GetOffset());
+          code_item->SetOffset(offset);
+          offset += RoundUp(code_item->GetSize(), 4);
+        }
+      }
+    }
+  }
+
+  return diff;
+}
+
+// Adjust offsets of every item in the specified section by diff bytes.
+template<class T> void DexLayout::FixupSection(std::map<uint32_t, std::unique_ptr<T>>& map,
+                                               uint32_t diff) {
+  for (auto& pair : map) {
+    std::unique_ptr<T>& item = pair.second;
+    item->SetOffset(item->GetOffset() + diff);
+  }
+}
+
+// Adjust offsets of all sections with an address after the specified offset by diff bytes.
+void DexLayout::FixupSections(uint32_t offset, uint32_t diff) {
+  dex_ir::Collections& collections = header_->GetCollections();
+  uint32_t map_list_offset = collections.MapListOffset();
+  if (map_list_offset > offset) {
+    collections.SetMapListOffset(map_list_offset + diff);
+  }
+
+  uint32_t type_lists_offset = collections.TypeListsOffset();
+  if (type_lists_offset > offset) {
+    collections.SetTypeListsOffset(type_lists_offset + diff);
+    FixupSection(collections.TypeLists(), diff);
+  }
+
+  uint32_t annotation_set_ref_lists_offset = collections.AnnotationSetRefListsOffset();
+  if (annotation_set_ref_lists_offset > offset) {
+    collections.SetAnnotationSetRefListsOffset(annotation_set_ref_lists_offset + diff);
+    FixupSection(collections.AnnotationSetRefLists(), diff);
+  }
+
+  uint32_t annotation_set_items_offset = collections.AnnotationSetItemsOffset();
+  if (annotation_set_items_offset > offset) {
+    collections.SetAnnotationSetItemsOffset(annotation_set_items_offset + diff);
+    FixupSection(collections.AnnotationSetItems(), diff);
+  }
+
+  uint32_t class_datas_offset = collections.ClassDatasOffset();
+  if (class_datas_offset > offset) {
+    collections.SetClassDatasOffset(class_datas_offset + diff);
+    FixupSection(collections.ClassDatas(), diff);
+  }
+
+  uint32_t code_items_offset = collections.CodeItemsOffset();
+  if (code_items_offset > offset) {
+    collections.SetCodeItemsOffset(code_items_offset + diff);
+    FixupSection(collections.CodeItems(), diff);
+  }
+
+  uint32_t string_datas_offset = collections.StringDatasOffset();
+  if (string_datas_offset > offset) {
+    collections.SetStringDatasOffset(string_datas_offset + diff);
+    FixupSection(collections.StringDatas(), diff);
+  }
+
+  uint32_t debug_info_items_offset = collections.DebugInfoItemsOffset();
+  if (debug_info_items_offset > offset) {
+    collections.SetDebugInfoItemsOffset(debug_info_items_offset + diff);
+    FixupSection(collections.DebugInfoItems(), diff);
+  }
+
+  uint32_t annotation_items_offset = collections.AnnotationItemsOffset();
+  if (annotation_items_offset > offset) {
+    collections.SetAnnotationItemsOffset(annotation_items_offset + diff);
+    FixupSection(collections.AnnotationItems(), diff);
+  }
+
+  uint32_t encoded_array_items_offset = collections.EncodedArrayItemsOffset();
+  if (encoded_array_items_offset > offset) {
+    collections.SetEncodedArrayItemsOffset(encoded_array_items_offset + diff);
+    FixupSection(collections.EncodedArrayItems(), diff);
+  }
+
+  uint32_t annotations_directory_items_offset = collections.AnnotationsDirectoryItemsOffset();
+  if (annotations_directory_items_offset > offset) {
+    collections.SetAnnotationsDirectoryItemsOffset(annotations_directory_items_offset + diff);
+    FixupSection(collections.AnnotationsDirectoryItems(), diff);
+  }
+}
+
+void DexLayout::LayoutOutputFile(const DexFile* dex_file) {
+  std::vector<dex_ir::ClassDef*> new_class_def_order = LayoutClassDefsAndClassData(dex_file);
+  int32_t diff = LayoutCodeItems(new_class_def_order);
+  // Adjust diff to be 4-byte aligned.
+  diff = RoundUp(diff, 4);
+  // Move sections after ClassData by diff bytes.
+  FixupSections(header_->GetCollections().ClassDatasOffset(), diff);
+  // Update file size.
+  header_->SetFileSize(header_->FileSize() + diff);
+}
+
 void DexLayout::OutputDexFile(const std::string& dex_file_location) {
   std::string error_msg;
   std::unique_ptr<File> new_file;
@@ -1547,6 +1694,9 @@ void DexLayout::ProcessDexFile(const char* file_name,
 
   // Output dex file as file or memmap.
   if (options_.output_dex_directory_ != nullptr || options_.output_to_memmap_) {
+    if (info_ != nullptr) {
+      LayoutOutputFile(dex_file);
+    }
     OutputDexFile(dex_file->GetLocation());
   }
 }
diff --git a/dexlayout/dexlayout.h b/dexlayout/dexlayout.h
index 179e90edc0..ac1a4a6efb 100644
--- a/dexlayout/dexlayout.h
+++ b/dexlayout/dexlayout.h
@@ -103,12 +103,15 @@ class DexLayout {
   void DumpMethod(uint32_t idx, uint32_t flags, const dex_ir::CodeItem* code, int i);
   void DumpPositionInfo(const dex_ir::CodeItem* code);
   void DumpSField(uint32_t idx, uint32_t flags, int i, dex_ir::EncodedValue* init);
-
   void DumpDexFile();
+
   std::vector<dex_ir::ClassDef*> LayoutClassDefsAndClassData(const DexFile* dex_file);
   int32_t LayoutCodeItems(std::vector<dex_ir::ClassDef*> new_class_def_order);
   template<class T> void FixupSection(std::map<uint32_t, std::unique_ptr<T>>& map, uint32_t diff);
   void FixupSections(uint32_t offset, uint32_t diff);
+
+  // Creates a new layout for the dex file based on profile info.
+  // Currently reorders ClassDefs, ClassDataItems, and CodeItems.
   void LayoutOutputFile(const DexFile* dex_file);
   void OutputDexFile(const std::string& dex_file_location);
 
diff --git a/dexlayout/dexlayout_test.cc b/dexlayout/dexlayout_test.cc
index c7f36be905..665baa6c73 100644
--- a/dexlayout/dexlayout_test.cc
+++ b/dexlayout/dexlayout_test.cc
@@ -22,11 +22,57 @@
 #include <unistd.h>
 
 #include "base/stringprintf.h"
+#include "base/unix_file/fd_file.h"
 #include "common_runtime_test.h"
 #include "utils.h"
 
 namespace art {
 
+static const char kDexFileLayoutInputDex[] =
+    "ZGV4CjAzNQD1KW3+B8NAB0f2A/ZVIBJ0aHrGIqcpVTAUAgAAcAAAAHhWNBIAAAAAAAAAAIwBAAAH"
+    "AAAAcAAAAAQAAACMAAAAAQAAAJwAAAAAAAAAAAAAAAMAAACoAAAAAgAAAMAAAAAUAQAAAAEAADAB"
+    "AAA4AQAAQAEAAEgBAABNAQAAUgEAAGYBAAADAAAABAAAAAUAAAAGAAAABgAAAAMAAAAAAAAAAAAA"
+    "AAAAAAABAAAAAAAAAAIAAAAAAAAAAAAAAAAAAAACAAAAAAAAAAEAAAAAAAAAdQEAAAAAAAABAAAA"
+    "AAAAAAIAAAAAAAAAAgAAAAAAAAB/AQAAAAAAAAEAAQABAAAAaQEAAAQAAABwEAIAAAAOAAEAAQAB"
+    "AAAAbwEAAAQAAABwEAIAAAAOAAY8aW5pdD4ABkEuamF2YQAGQi5qYXZhAANMQTsAA0xCOwASTGph"
+    "dmEvbGFuZy9PYmplY3Q7AAFWAAQABw48AAQABw48AAAAAQAAgIAEgAIAAAEAAYCABJgCAAAACwAA"
+    "AAAAAAABAAAAAAAAAAEAAAAHAAAAcAAAAAIAAAAEAAAAjAAAAAMAAAABAAAAnAAAAAUAAAADAAAA"
+    "qAAAAAYAAAACAAAAwAAAAAEgAAACAAAAAAEAAAIgAAAHAAAAMAEAAAMgAAACAAAAaQEAAAAgAAAC"
+    "AAAAdQEAAAAQAAABAAAAjAEAAA==";
+
+static const char kDexFileLayoutInputProfile[] =
+    "cHJvADAwMgABAAsAAAABAPUpbf5jbGFzc2VzLmRleAEA";
+
+static const char kDexFileLayoutExpectedOutputDex[] =
+    "ZGV4CjAzNQD1KW3+B8NAB0f2A/ZVIBJ0aHrGIqcpVTAUAgAAcAAAAHhWNBIAAAAAAAAAAIwBAAAH"
+    "AAAAcAAAAAQAAACMAAAAAQAAAJwAAAAAAAAAAAAAAAMAAACoAAAAAgAAAMAAAAAUAQAAAAEAADAB"
+    "AAA4AQAAQAEAAEgBAABNAQAAUgEAAGYBAAADAAAABAAAAAUAAAAGAAAABgAAAAMAAAAAAAAAAAAA"
+    "AAAAAAABAAAAAAAAAAIAAAAAAAAAAQAAAAAAAAACAAAAAAAAAAIAAAAAAAAAdQEAAAAAAAAAAAAA"
+    "AAAAAAIAAAAAAAAAAQAAAAAAAAB/AQAAAAAAAAEAAQABAAAAbwEAAAQAAABwEAIAAAAOAAEAAQAB"
+    "AAAAaQEAAAQAAABwEAIAAAAOAAY8aW5pdD4ABkEuamF2YQAGQi5qYXZhAANMQTsAA0xCOwASTGph"
+    "dmEvbGFuZy9PYmplY3Q7AAFWAAQABw48AAQABw48AAAAAQABgIAEgAIAAAEAAICABJgCAAAACwAA"
+    "AAAAAAABAAAAAAAAAAEAAAAHAAAAcAAAAAIAAAAEAAAAjAAAAAMAAAABAAAAnAAAAAUAAAADAAAA"
+    "qAAAAAYAAAACAAAAwAAAAAEgAAACAAAAAAEAAAIgAAAHAAAAMAEAAAMgAAACAAAAaQEAAAAgAAAC"
+    "AAAAdQEAAAAQAAABAAAAjAEAAA==";
+
+static void WriteFileBase64(const char* base64, const char* location) {
+  // Decode base64.
+  CHECK(base64 != nullptr);
+  size_t length;
+  std::unique_ptr<uint8_t[]> bytes(DecodeBase64(base64, &length));
+  CHECK(bytes.get() != nullptr);
+
+  // Write to provided file.
+  std::unique_ptr<File> file(OS::CreateEmptyFile(location));
+  CHECK(file.get() != nullptr);
+  if (!file->WriteFully(bytes.get(), length)) {
+    PLOG(FATAL) << "Failed to write base64 as file";
+  }
+  if (file->FlushCloseOrErase() != 0) {
+    PLOG(FATAL) << "Could not flush and close test file.";
+  }
+}
+
 class DexLayoutTest : public CommonRuntimeTest {
  protected:
   virtual void SetUp() {
@@ -51,7 +97,6 @@ class DexLayoutTest : public CommonRuntimeTest {
           { dexdump, "-d", "-f", "-h", "-l", "plain", "-o", dexdump_filename, dex_file };
       std::vector<std::string> dexlayout_exec_argv =
           { dexlayout, "-d", "-f", "-h", "-l", "plain", "-o", dexlayout_filename, dex_file };
-
       if (!::art::Exec(dexdump_exec_argv, error_msg)) {
         return false;
       }
@@ -78,13 +123,11 @@ class DexLayoutTest : public CommonRuntimeTest {
 
     for (const std::string &dex_file : GetLibCoreDexFileNames()) {
       std::vector<std::string> dexlayout_exec_argv =
-          { dexlayout, "-d", "-f", "-h", "-l", "plain", "-w", tmp_dir, "-o", tmp_name, dex_file };
-
+          { dexlayout, "-w", tmp_dir, "-o", tmp_name, dex_file };
       if (!::art::Exec(dexlayout_exec_argv, error_msg)) {
         return false;
       }
-
-      size_t dex_file_last_slash = dex_file.rfind('/');
+      size_t dex_file_last_slash = dex_file.rfind("/");
       std::string dex_file_name = dex_file.substr(dex_file_last_slash + 1);
       std::vector<std::string> unzip_exec_argv =
           { "/usr/bin/unzip", dex_file, "classes.dex", "-d", tmp_dir};
@@ -105,7 +148,44 @@ class DexLayoutTest : public CommonRuntimeTest {
         return false;
       }
     }
+    return true;
+  }
+
+  // Runs DexFileOutput test.
+  bool DexFileLayoutExec(std::string* error_msg) {
+    ScratchFile tmp_file;
+    std::string tmp_name = tmp_file.GetFilename();
+    size_t tmp_last_slash = tmp_name.rfind("/");
+    std::string tmp_dir = tmp_name.substr(0, tmp_last_slash + 1);
+
+    // Write inputs and expected outputs.
+    std::string dex_file = tmp_dir + "classes.dex";
+    WriteFileBase64(kDexFileLayoutInputDex, dex_file.c_str());
+    std::string profile_file = tmp_dir + "primary.prof";
+    WriteFileBase64(kDexFileLayoutInputProfile, profile_file.c_str());
+    std::string expected_output = tmp_dir + "expected.dex";
+    WriteFileBase64(kDexFileLayoutExpectedOutputDex, expected_output.c_str());
+    std::string output_dex = tmp_dir + "classes.dex.new";
+
+    std::string dexlayout = GetTestAndroidRoot() + "/bin/dexlayout";
+    EXPECT_TRUE(OS::FileExists(dexlayout.c_str())) << dexlayout << " should be a valid file path";
+
+    std::vector<std::string> dexlayout_exec_argv =
+    { dexlayout, "-w", tmp_dir, "-o", tmp_name, "-p", profile_file, dex_file };
+    if (!::art::Exec(dexlayout_exec_argv, error_msg)) {
+      return false;
+    }
+    std::vector<std::string> diff_exec_argv =
+        { "/usr/bin/diff", expected_output, output_dex };
+    if (!::art::Exec(diff_exec_argv, error_msg)) {
+      return false;
+    }
 
+    std::vector<std::string> rm_exec_argv =
+        { "/bin/rm", dex_file, profile_file, expected_output, output_dex };
+    if (!::art::Exec(rm_exec_argv, error_msg)) {
+      return false;
+    }
     return true;
   }
 };
@@ -125,4 +205,11 @@ TEST_F(DexLayoutTest, DexFileOutput) {
   ASSERT_TRUE(DexFileOutputExec(&error_msg)) << error_msg;
 }
 
+TEST_F(DexLayoutTest, DexFileLayout) {
+  // Disable test on target.
+  TEST_DISABLED_FOR_TARGET();
+  std::string error_msg;
+  ASSERT_TRUE(DexFileLayoutExec(&error_msg)) << error_msg;
+}
+
 }  // namespace art