compiler/linker/arm/relative_patcher_thumb2_test.cc - platform/art - Git at Google

 /*
  * Copyright (C) 2015 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 "linker/relative_patcher_test.h"
 #include "linker/arm/relative_patcher_thumb2.h"
 #include "oat_quick_method_header.h"

 namespace art {
 namespace linker {

 class Thumb2RelativePatcherTest : public RelativePatcherTest {
  public:
   Thumb2RelativePatcherTest() : RelativePatcherTest(kThumb2, "default") { }

  protected:
   static const uint8_t kCallRawCode[];
   static const ArrayRef<const uint8_t> kCallCode;
   static const uint8_t kNopRawCode[];
   static const ArrayRef<const uint8_t> kNopCode;
   static const uint8_t kUnpatchedPcRelativeRawCode[];
   static const ArrayRef<const uint8_t> kUnpatchedPcRelativeCode;
   static const uint32_t kPcInsnOffset;

   // Branches within range [-256, 256) can be created from these by adding the low 8 bits.
   static constexpr uint32_t kBlPlus0 = 0xf000f800;
   static constexpr uint32_t kBlMinus256 = 0xf7ffff00;

   // Special BL values.
   static constexpr uint32_t kBlPlusMax = 0xf3ffd7ff;
   static constexpr uint32_t kBlMinusMax = 0xf400d000;

   bool Create2MethodsWithGap(const ArrayRef<const uint8_t>& method1_code,
                              const ArrayRef<const LinkerPatch>& method1_patches,
                              const ArrayRef<const uint8_t>& method3_code,
                              const ArrayRef<const LinkerPatch>& method3_patches,
                              uint32_t distance_without_thunks) {
     CHECK_EQ(distance_without_thunks % kArmAlignment, 0u);
     const uint32_t method1_offset =
         CompiledCode::AlignCode(kTrampolineSize, kThumb2) + sizeof(OatQuickMethodHeader);
     AddCompiledMethod(MethodRef(1u), method1_code, method1_patches);

     // We want to put the method3 at a very precise offset.
     const uint32_t method3_offset = method1_offset + distance_without_thunks;
     CHECK_ALIGNED(method3_offset - sizeof(OatQuickMethodHeader), kArmAlignment);

     // Calculate size of method2 so that we put method3 at the correct place.
     const uint32_t method2_offset =
         CompiledCode::AlignCode(method1_offset + method1_code.size(), kThumb2) +
         sizeof(OatQuickMethodHeader);
     const uint32_t method2_size = (method3_offset - sizeof(OatQuickMethodHeader) - method2_offset);
     std::vector<uint8_t> method2_raw_code(method2_size);
     ArrayRef<const uint8_t> method2_code(method2_raw_code);
     AddCompiledMethod(MethodRef(2u), method2_code, ArrayRef<const LinkerPatch>());

     AddCompiledMethod(MethodRef(3u), method3_code, method3_patches);

     Link();

     // Check assumptions.
     CHECK_EQ(GetMethodOffset(1), method1_offset);
     CHECK_EQ(GetMethodOffset(2), method2_offset);
     auto result3 = method_offset_map_.FindMethodOffset(MethodRef(3));
     CHECK(result3.first);
     // There may be a thunk before method2.
     if (result3.second == method3_offset + 1 /* thumb mode */) {
       return false;  // No thunk.
     } else {
       uint32_t aligned_thunk_size = CompiledCode::AlignCode(ThunkSize(), kThumb2);
       CHECK_EQ(result3.second, method3_offset + aligned_thunk_size + 1 /* thumb mode */);
       return true;   // Thunk present.
     }
   }

   uint32_t GetMethodOffset(uint32_t method_idx) {
     auto result = method_offset_map_.FindMethodOffset(MethodRef(method_idx));
     CHECK(result.first);
     CHECK_NE(result.second & 1u, 0u);
     return result.second - 1 /* thumb mode */;
   }

   uint32_t ThunkSize() {
     return static_cast<Thumb2RelativePatcher*>(patcher_.get())->thunk_code_.size();
   }

   bool CheckThunk(uint32_t thunk_offset) {
     Thumb2RelativePatcher* patcher = static_cast<Thumb2RelativePatcher*>(patcher_.get());
     ArrayRef<const uint8_t> expected_code(patcher->thunk_code_);
     if (output_.size() < thunk_offset + expected_code.size()) {
       LOG(ERROR) << "output_.size() == " << output_.size() << " < "
           << "thunk_offset + expected_code.size() == " << (thunk_offset + expected_code.size());
       return false;
     }
     ArrayRef<const uint8_t> linked_code(&output_[thunk_offset], expected_code.size());
     if (linked_code == expected_code) {
       return true;
     }
     // Log failure info.
     DumpDiff(expected_code, linked_code);
     return false;
   }

   std::vector<uint8_t> GenNopsAndBl(size_t num_nops, uint32_t bl) {
     std::vector<uint8_t> result;
     result.reserve(num_nops * 2u + 4u);
     for (size_t i = 0; i != num_nops; ++i) {
       result.push_back(0x00);
       result.push_back(0xbf);
     }
     result.push_back(static_cast<uint8_t>(bl >> 16));
     result.push_back(static_cast<uint8_t>(bl >> 24));
     result.push_back(static_cast<uint8_t>(bl));
     result.push_back(static_cast<uint8_t>(bl >> 8));
     return result;
   }

   void TestDexCacheReference(uint32_t dex_cache_arrays_begin, uint32_t element_offset);
   void TestStringReference(uint32_t string_offset);
   void CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches, uint32_t target_offset);
 };

 const uint8_t Thumb2RelativePatcherTest::kCallRawCode[] = {
     0x00, 0xf0, 0x00, 0xf8
 };

 const ArrayRef<const uint8_t> Thumb2RelativePatcherTest::kCallCode(kCallRawCode);

 const uint8_t Thumb2RelativePatcherTest::kNopRawCode[] = {
     0x00, 0xbf
 };

 const ArrayRef<const uint8_t> Thumb2RelativePatcherTest::kNopCode(kNopRawCode);

 const uint8_t Thumb2RelativePatcherTest::kUnpatchedPcRelativeRawCode[] = {
     0x40, 0xf2, 0x00, 0x00,   // MOVW r0, #0 (placeholder)
     0xc0, 0xf2, 0x00, 0x00,   // MOVT r0, #0 (placeholder)
     0x78, 0x44,               // ADD r0, pc
 };
 const ArrayRef<const uint8_t> Thumb2RelativePatcherTest::kUnpatchedPcRelativeCode(
     kUnpatchedPcRelativeRawCode);
 const uint32_t Thumb2RelativePatcherTest::kPcInsnOffset = 8u;

 void Thumb2RelativePatcherTest::TestDexCacheReference(uint32_t dex_cache_arrays_begin,
                                                       uint32_t element_offset) {
   dex_cache_arrays_begin_ = dex_cache_arrays_begin;
   LinkerPatch patches[] = {
       LinkerPatch::DexCacheArrayPatch(0u, nullptr, kPcInsnOffset, element_offset),
       LinkerPatch::DexCacheArrayPatch(4u, nullptr, kPcInsnOffset, element_offset),
   };
   CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches),
                        dex_cache_arrays_begin_ + element_offset);
 }

 void Thumb2RelativePatcherTest::TestStringReference(uint32_t string_offset) {
   constexpr uint32_t kStringIndex = 1u;
   string_index_to_offset_map_.Put(kStringIndex, string_offset);
   LinkerPatch patches[] = {
       LinkerPatch::RelativeStringPatch(0u, nullptr, kPcInsnOffset, kStringIndex),
       LinkerPatch::RelativeStringPatch(4u, nullptr, kPcInsnOffset, kStringIndex),
   };
   CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches), string_offset);
 }

 void Thumb2RelativePatcherTest::CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches,
                                                      uint32_t target_offset) {
   AddCompiledMethod(MethodRef(1u), kUnpatchedPcRelativeCode, ArrayRef<const LinkerPatch>(patches));
   Link();

   uint32_t method1_offset = GetMethodOffset(1u);
   uint32_t pc_base_offset = method1_offset + kPcInsnOffset + 4u /* PC adjustment */;
   uint32_t diff = target_offset - pc_base_offset;
   // Distribute the bits of the diff between the MOVW and MOVT:
   uint32_t diffw = diff & 0xffffu;
   uint32_t difft = diff >> 16;
   uint32_t movw = 0xf2400000u |           // MOVW r0, #0 (placeholder),
       ((diffw & 0xf000u) << (16 - 12)) |  // move imm4 from bits 12-15 to bits 16-19,
       ((diffw & 0x0800u) << (26 - 11)) |  // move imm from bit 11 to bit 26,
       ((diffw & 0x0700u) << (12 - 8)) |   // move imm3 from bits 8-10 to bits 12-14,
       ((diffw & 0x00ffu));                // keep imm8 at bits 0-7.
   uint32_t movt = 0xf2c00000u |           // MOVT r0, #0 (placeholder),
       ((difft & 0xf000u) << (16 - 12)) |  // move imm4 from bits 12-15 to bits 16-19,
       ((difft & 0x0800u) << (26 - 11)) |  // move imm from bit 11 to bit 26,
       ((difft & 0x0700u) << (12 - 8)) |   // move imm3 from bits 8-10 to bits 12-14,
       ((difft & 0x00ffu));                // keep imm8 at bits 0-7.
   const uint8_t expected_code[] = {
       static_cast<uint8_t>(movw >> 16), static_cast<uint8_t>(movw >> 24),
       static_cast<uint8_t>(movw >> 0), static_cast<uint8_t>(movw >> 8),
       static_cast<uint8_t>(movt >> 16), static_cast<uint8_t>(movt >> 24),
       static_cast<uint8_t>(movt >> 0), static_cast<uint8_t>(movt >> 8),
       0x78, 0x44,
   };
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
 }

 TEST_F(Thumb2RelativePatcherTest, CallSelf) {
   LinkerPatch patches[] = {
       LinkerPatch::RelativeCodePatch(0u, nullptr, 1u),
   };
   AddCompiledMethod(MethodRef(1u), kCallCode, ArrayRef<const LinkerPatch>(patches));
   Link();

   static const uint8_t expected_code[] = {
       0xff, 0xf7, 0xfe, 0xff
   };
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
 }

 TEST_F(Thumb2RelativePatcherTest, CallOther) {
   LinkerPatch method1_patches[] = {
       LinkerPatch::RelativeCodePatch(0u, nullptr, 2u),
   };
   AddCompiledMethod(MethodRef(1u), kCallCode, ArrayRef<const LinkerPatch>(method1_patches));
   LinkerPatch method2_patches[] = {
       LinkerPatch::RelativeCodePatch(0u, nullptr, 1u),
   };
   AddCompiledMethod(MethodRef(2u), kCallCode, ArrayRef<const LinkerPatch>(method2_patches));
   Link();

   uint32_t method1_offset = GetMethodOffset(1u);
   uint32_t method2_offset = GetMethodOffset(2u);
   uint32_t diff_after = method2_offset - (method1_offset + 4u /* PC adjustment */);
   ASSERT_EQ(diff_after & 1u, 0u);
   ASSERT_LT(diff_after >> 1, 1u << 8);  // Simple encoding, (diff_after >> 1) fits into 8 bits.
   static const uint8_t method1_expected_code[] = {
       0x00, 0xf0, static_cast<uint8_t>(diff_after >> 1), 0xf8
   };
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(method1_expected_code)));
   uint32_t diff_before = method1_offset - (method2_offset + 4u /* PC adjustment */);
   ASSERT_EQ(diff_before & 1u, 0u);
   ASSERT_GE(diff_before, -1u << 9);  // Simple encoding, -256 <= (diff >> 1) < 0.
   auto method2_expected_code = GenNopsAndBl(0u, kBlMinus256 | ((diff_before >> 1) & 0xffu));
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(2u), ArrayRef<const uint8_t>(method2_expected_code)));
 }

 TEST_F(Thumb2RelativePatcherTest, CallTrampoline) {
   LinkerPatch patches[] = {
       LinkerPatch::RelativeCodePatch(0u, nullptr, 2u),
   };
   AddCompiledMethod(MethodRef(1u), kCallCode, ArrayRef<const LinkerPatch>(patches));
   Link();

   uint32_t method1_offset = GetMethodOffset(1u);
   uint32_t diff = kTrampolineOffset - (method1_offset + 4u);
   ASSERT_EQ(diff & 1u, 0u);
   ASSERT_GE(diff, -1u << 9);  // Simple encoding, -256 <= (diff >> 1) < 0 (checked as unsigned).
   auto expected_code = GenNopsAndBl(0u, kBlMinus256 | ((diff >> 1) & 0xffu));
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
 }

 TEST_F(Thumb2RelativePatcherTest, CallTrampolineTooFar) {
   constexpr uint32_t missing_method_index = 1024u;
   auto method3_raw_code = GenNopsAndBl(3u, kBlPlus0);
   constexpr uint32_t bl_offset_in_method3 = 3u * 2u;  // After NOPs.
   ArrayRef<const uint8_t> method3_code(method3_raw_code);
   ASSERT_EQ(bl_offset_in_method3 + 4u, method3_code.size());
   LinkerPatch method3_patches[] = {
       LinkerPatch::RelativeCodePatch(bl_offset_in_method3, nullptr, missing_method_index),
   };

   constexpr uint32_t just_over_max_negative_disp = 16 * MB + 2 - 4u /* PC adjustment */;
   bool thunk_in_gap = Create2MethodsWithGap(kNopCode,
                                             ArrayRef<const LinkerPatch>(),
                                             method3_code,
                                             ArrayRef<const LinkerPatch>(method3_patches),
                                             just_over_max_negative_disp - bl_offset_in_method3);
   ASSERT_FALSE(thunk_in_gap);  // There should be a thunk but it should be after the method2.
   ASSERT_FALSE(method_offset_map_.FindMethodOffset(MethodRef(missing_method_index)).first);

   // Check linked code.
   uint32_t method3_offset = GetMethodOffset(3u);
   uint32_t thunk_offset = CompiledCode::AlignCode(method3_offset + method3_code.size(), kThumb2);
   uint32_t diff = thunk_offset - (method3_offset + bl_offset_in_method3 + 4u /* PC adjustment */);
   ASSERT_EQ(diff & 1u, 0u);
   ASSERT_LT(diff >> 1, 1u << 8);  // Simple encoding, (diff >> 1) fits into 8 bits.
   auto expected_code = GenNopsAndBl(3u, kBlPlus0 | ((diff >> 1) & 0xffu));
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(3u), ArrayRef<const uint8_t>(expected_code)));
   EXPECT_TRUE(CheckThunk(thunk_offset));
 }

 TEST_F(Thumb2RelativePatcherTest, CallOtherAlmostTooFarAfter) {
   auto method1_raw_code = GenNopsAndBl(3u, kBlPlus0);
   constexpr uint32_t bl_offset_in_method1 = 3u * 2u;  // After NOPs.
   ArrayRef<const uint8_t> method1_code(method1_raw_code);
   ASSERT_EQ(bl_offset_in_method1 + 4u, method1_code.size());
   LinkerPatch method1_patches[] = {
       LinkerPatch::RelativeCodePatch(bl_offset_in_method1, nullptr, 3u),
   };

   constexpr uint32_t max_positive_disp = 16 * MB - 2u + 4u /* PC adjustment */;
   bool thunk_in_gap = Create2MethodsWithGap(method1_code,
                                             ArrayRef<const LinkerPatch>(method1_patches),
                                             kNopCode,
                                             ArrayRef<const LinkerPatch>(),
                                             bl_offset_in_method1 + max_positive_disp);
   ASSERT_FALSE(thunk_in_gap);  // There should be no thunk.

   // Check linked code.
   auto expected_code = GenNopsAndBl(3u, kBlPlusMax);
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
 }

 TEST_F(Thumb2RelativePatcherTest, CallOtherAlmostTooFarBefore) {
   auto method3_raw_code = GenNopsAndBl(2u, kBlPlus0);
   constexpr uint32_t bl_offset_in_method3 = 2u * 2u;  // After NOPs.
   ArrayRef<const uint8_t> method3_code(method3_raw_code);
   ASSERT_EQ(bl_offset_in_method3 + 4u, method3_code.size());
   LinkerPatch method3_patches[] = {
       LinkerPatch::RelativeCodePatch(bl_offset_in_method3, nullptr, 1u),
   };

   constexpr uint32_t just_over_max_negative_disp = 16 * MB - 4u /* PC adjustment */;
   bool thunk_in_gap = Create2MethodsWithGap(kNopCode,
                                             ArrayRef<const LinkerPatch>(),
                                             method3_code,
                                             ArrayRef<const LinkerPatch>(method3_patches),
                                             just_over_max_negative_disp - bl_offset_in_method3);
   ASSERT_FALSE(thunk_in_gap);  // There should be no thunk.

   // Check linked code.
   auto expected_code = GenNopsAndBl(2u, kBlMinusMax);
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(3u), ArrayRef<const uint8_t>(expected_code)));
 }

 TEST_F(Thumb2RelativePatcherTest, CallOtherJustTooFarAfter) {
   auto method1_raw_code = GenNopsAndBl(2u, kBlPlus0);
   constexpr uint32_t bl_offset_in_method1 = 2u * 2u;  // After NOPs.
   ArrayRef<const uint8_t> method1_code(method1_raw_code);
   ASSERT_EQ(bl_offset_in_method1 + 4u, method1_code.size());
   LinkerPatch method1_patches[] = {
       LinkerPatch::RelativeCodePatch(bl_offset_in_method1, nullptr, 3u),
   };

   constexpr uint32_t just_over_max_positive_disp = 16 * MB + 4u /* PC adjustment */;
   bool thunk_in_gap = Create2MethodsWithGap(method1_code,
                                             ArrayRef<const LinkerPatch>(method1_patches),
                                             kNopCode,
                                             ArrayRef<const LinkerPatch>(),
                                             bl_offset_in_method1 + just_over_max_positive_disp);
   ASSERT_TRUE(thunk_in_gap);

   uint32_t method1_offset = GetMethodOffset(1u);
   uint32_t method3_offset = GetMethodOffset(3u);
   uint32_t method3_header_offset = method3_offset - sizeof(OatQuickMethodHeader);
   ASSERT_TRUE(IsAligned<kArmAlignment>(method3_header_offset));
   uint32_t thunk_offset = method3_header_offset - CompiledCode::AlignCode(ThunkSize(), kThumb2);
   ASSERT_TRUE(IsAligned<kArmAlignment>(thunk_offset));
   uint32_t diff = thunk_offset - (method1_offset + bl_offset_in_method1 + 4u /* PC adjustment */);
   ASSERT_EQ(diff & 1u, 0u);
   ASSERT_GE(diff, 16 * MB - (1u << 9));  // Simple encoding, unknown bits fit into the low 8 bits.
   auto expected_code = GenNopsAndBl(2u, 0xf3ffd700 | ((diff >> 1) & 0xffu));
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
   CheckThunk(thunk_offset);
 }

 TEST_F(Thumb2RelativePatcherTest, CallOtherJustTooFarBefore) {
   auto method3_raw_code = GenNopsAndBl(3u, kBlPlus0);
   constexpr uint32_t bl_offset_in_method3 = 3u * 2u;  // After NOPs.
   ArrayRef<const uint8_t> method3_code(method3_raw_code);
   ASSERT_EQ(bl_offset_in_method3 + 4u, method3_code.size());
   LinkerPatch method3_patches[] = {
       LinkerPatch::RelativeCodePatch(bl_offset_in_method3, nullptr, 1u),
   };

   constexpr uint32_t just_over_max_negative_disp = 16 * MB + 2 - 4u /* PC adjustment */;
   bool thunk_in_gap = Create2MethodsWithGap(kNopCode,
                                             ArrayRef<const LinkerPatch>(),
                                             method3_code,
                                             ArrayRef<const LinkerPatch>(method3_patches),
                                             just_over_max_negative_disp - bl_offset_in_method3);
   ASSERT_FALSE(thunk_in_gap);  // There should be a thunk but it should be after the method2.

   // Check linked code.
   uint32_t method3_offset = GetMethodOffset(3u);
   uint32_t thunk_offset = CompiledCode::AlignCode(method3_offset + method3_code.size(), kThumb2);
   uint32_t diff = thunk_offset - (method3_offset + bl_offset_in_method3 + 4u /* PC adjustment */);
   ASSERT_EQ(diff & 1u, 0u);
   ASSERT_LT(diff >> 1, 1u << 8);  // Simple encoding, (diff >> 1) fits into 8 bits.
   auto expected_code = GenNopsAndBl(3u, kBlPlus0 | ((diff >> 1) & 0xffu));
   EXPECT_TRUE(CheckLinkedMethod(MethodRef(3u), ArrayRef<const uint8_t>(expected_code)));
   EXPECT_TRUE(CheckThunk(thunk_offset));
 }

 TEST_F(Thumb2RelativePatcherTest, DexCacheReference1) {
   TestDexCacheReference(0x00ff0000u, 0x00fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 TEST_F(Thumb2RelativePatcherTest, DexCacheReference2) {
   TestDexCacheReference(0x02ff0000u, 0x05fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 TEST_F(Thumb2RelativePatcherTest, DexCacheReference3) {
   TestDexCacheReference(0x08ff0000u, 0x08fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 TEST_F(Thumb2RelativePatcherTest, DexCacheReference4) {
   TestDexCacheReference(0xd0ff0000u, 0x60fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 TEST_F(Thumb2RelativePatcherTest, StringReference1) {
   TestStringReference(0x00ff00fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 TEST_F(Thumb2RelativePatcherTest, StringReference2) {
   TestStringReference(0x02ff05fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 TEST_F(Thumb2RelativePatcherTest, StringReference3) {
   TestStringReference(0x08ff08fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 TEST_F(Thumb2RelativePatcherTest, StringReference4) {
   TestStringReference(0xd0ff60fcu);
   ASSERT_LT(GetMethodOffset(1u), 0xfcu);
 }

 }  // namespace linker
 }  // namespace art
	/*
	* Copyright (C) 2015 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 "linker/relative_patcher_test.h"
	#include "linker/arm/relative_patcher_thumb2.h"
	#include "oat_quick_method_header.h"

	namespace art {
	namespace linker {

	class Thumb2RelativePatcherTest : public RelativePatcherTest {
	public:
	Thumb2RelativePatcherTest() : RelativePatcherTest(kThumb2, "default") { }

	protected:
	static const uint8_t kCallRawCode[];
	static const ArrayRef<const uint8_t> kCallCode;
	static const uint8_t kNopRawCode[];
	static const ArrayRef<const uint8_t> kNopCode;
	static const uint8_t kUnpatchedPcRelativeRawCode[];
	static const ArrayRef<const uint8_t> kUnpatchedPcRelativeCode;
	static const uint32_t kPcInsnOffset;

	// Branches within range [-256, 256) can be created from these by adding the low 8 bits.
	static constexpr uint32_t kBlPlus0 = 0xf000f800;
	static constexpr uint32_t kBlMinus256 = 0xf7ffff00;

	// Special BL values.
	static constexpr uint32_t kBlPlusMax = 0xf3ffd7ff;
	static constexpr uint32_t kBlMinusMax = 0xf400d000;

	bool Create2MethodsWithGap(const ArrayRef<const uint8_t>& method1_code,
	const ArrayRef<const LinkerPatch>& method1_patches,
	const ArrayRef<const uint8_t>& method3_code,
	const ArrayRef<const LinkerPatch>& method3_patches,
	uint32_t distance_without_thunks) {
	CHECK_EQ(distance_without_thunks % kArmAlignment, 0u);
	const uint32_t method1_offset =
	CompiledCode::AlignCode(kTrampolineSize, kThumb2) + sizeof(OatQuickMethodHeader);
	AddCompiledMethod(MethodRef(1u), method1_code, method1_patches);

	// We want to put the method3 at a very precise offset.
	const uint32_t method3_offset = method1_offset + distance_without_thunks;
	CHECK_ALIGNED(method3_offset - sizeof(OatQuickMethodHeader), kArmAlignment);

	// Calculate size of method2 so that we put method3 at the correct place.
	const uint32_t method2_offset =
	CompiledCode::AlignCode(method1_offset + method1_code.size(), kThumb2) +
	sizeof(OatQuickMethodHeader);
	const uint32_t method2_size = (method3_offset - sizeof(OatQuickMethodHeader) - method2_offset);
	std::vector<uint8_t> method2_raw_code(method2_size);
	ArrayRef<const uint8_t> method2_code(method2_raw_code);
	AddCompiledMethod(MethodRef(2u), method2_code, ArrayRef<const LinkerPatch>());

	AddCompiledMethod(MethodRef(3u), method3_code, method3_patches);

	Link();

	// Check assumptions.
	CHECK_EQ(GetMethodOffset(1), method1_offset);
	CHECK_EQ(GetMethodOffset(2), method2_offset);
	auto result3 = method_offset_map_.FindMethodOffset(MethodRef(3));
	CHECK(result3.first);
	// There may be a thunk before method2.
	if (result3.second == method3_offset + 1 /* thumb mode */) {
	return false; // No thunk.
	} else {
	uint32_t aligned_thunk_size = CompiledCode::AlignCode(ThunkSize(), kThumb2);
	CHECK_EQ(result3.second, method3_offset + aligned_thunk_size + 1 /* thumb mode */);
	return true; // Thunk present.
	}
	}

	uint32_t GetMethodOffset(uint32_t method_idx) {
	auto result = method_offset_map_.FindMethodOffset(MethodRef(method_idx));
	CHECK(result.first);
	CHECK_NE(result.second & 1u, 0u);
	return result.second - 1 /* thumb mode */;
	}

	uint32_t ThunkSize() {
	return static_cast<Thumb2RelativePatcher*>(patcher_.get())->thunk_code_.size();
	}

	bool CheckThunk(uint32_t thunk_offset) {
	Thumb2RelativePatcher* patcher = static_cast<Thumb2RelativePatcher*>(patcher_.get());
	ArrayRef<const uint8_t> expected_code(patcher->thunk_code_);
	if (output_.size() < thunk_offset + expected_code.size()) {
	LOG(ERROR) << "output_.size() == " << output_.size() << " < "
	<< "thunk_offset + expected_code.size() == " << (thunk_offset + expected_code.size());
	return false;
	}
	ArrayRef<const uint8_t> linked_code(&output_[thunk_offset], expected_code.size());
	if (linked_code == expected_code) {
	return true;
	}
	// Log failure info.
	DumpDiff(expected_code, linked_code);
	return false;
	}

	std::vector<uint8_t> GenNopsAndBl(size_t num_nops, uint32_t bl) {
	std::vector<uint8_t> result;
	result.reserve(num_nops * 2u + 4u);
	for (size_t i = 0; i != num_nops; ++i) {
	result.push_back(0x00);
	result.push_back(0xbf);
	}
	result.push_back(static_cast<uint8_t>(bl >> 16));
	result.push_back(static_cast<uint8_t>(bl >> 24));
	result.push_back(static_cast<uint8_t>(bl));
	result.push_back(static_cast<uint8_t>(bl >> 8));
	return result;
	}

	void TestDexCacheReference(uint32_t dex_cache_arrays_begin, uint32_t element_offset);
	void TestStringReference(uint32_t string_offset);
	void CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches, uint32_t target_offset);
	};

	const uint8_t Thumb2RelativePatcherTest::kCallRawCode[] = {
	0x00, 0xf0, 0x00, 0xf8
	};

	const ArrayRef<const uint8_t> Thumb2RelativePatcherTest::kCallCode(kCallRawCode);

	const uint8_t Thumb2RelativePatcherTest::kNopRawCode[] = {
	0x00, 0xbf
	};

	const ArrayRef<const uint8_t> Thumb2RelativePatcherTest::kNopCode(kNopRawCode);

	const uint8_t Thumb2RelativePatcherTest::kUnpatchedPcRelativeRawCode[] = {
	0x40, 0xf2, 0x00, 0x00, // MOVW r0, #0 (placeholder)
	0xc0, 0xf2, 0x00, 0x00, // MOVT r0, #0 (placeholder)
	0x78, 0x44, // ADD r0, pc
	};
	const ArrayRef<const uint8_t> Thumb2RelativePatcherTest::kUnpatchedPcRelativeCode(
	kUnpatchedPcRelativeRawCode);
	const uint32_t Thumb2RelativePatcherTest::kPcInsnOffset = 8u;

	void Thumb2RelativePatcherTest::TestDexCacheReference(uint32_t dex_cache_arrays_begin,
	uint32_t element_offset) {
	dex_cache_arrays_begin_ = dex_cache_arrays_begin;
	LinkerPatch patches[] = {
	LinkerPatch::DexCacheArrayPatch(0u, nullptr, kPcInsnOffset, element_offset),
	LinkerPatch::DexCacheArrayPatch(4u, nullptr, kPcInsnOffset, element_offset),
	};
	CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches),
	dex_cache_arrays_begin_ + element_offset);
	}

	void Thumb2RelativePatcherTest::TestStringReference(uint32_t string_offset) {
	constexpr uint32_t kStringIndex = 1u;
	string_index_to_offset_map_.Put(kStringIndex, string_offset);
	LinkerPatch patches[] = {
	LinkerPatch::RelativeStringPatch(0u, nullptr, kPcInsnOffset, kStringIndex),
	LinkerPatch::RelativeStringPatch(4u, nullptr, kPcInsnOffset, kStringIndex),
	};
	CheckPcRelativePatch(ArrayRef<const LinkerPatch>(patches), string_offset);
	}

	void Thumb2RelativePatcherTest::CheckPcRelativePatch(const ArrayRef<const LinkerPatch>& patches,
	uint32_t target_offset) {
	AddCompiledMethod(MethodRef(1u), kUnpatchedPcRelativeCode, ArrayRef<const LinkerPatch>(patches));
	Link();

	uint32_t method1_offset = GetMethodOffset(1u);
	uint32_t pc_base_offset = method1_offset + kPcInsnOffset + 4u /* PC adjustment */;
	uint32_t diff = target_offset - pc_base_offset;
	// Distribute the bits of the diff between the MOVW and MOVT:
	uint32_t diffw = diff & 0xffffu;
	uint32_t difft = diff >> 16;
	uint32_t movw = 0xf2400000u \| // MOVW r0, #0 (placeholder),
	((diffw & 0xf000u) << (16 - 12)) \| // move imm4 from bits 12-15 to bits 16-19,
	((diffw & 0x0800u) << (26 - 11)) \| // move imm from bit 11 to bit 26,
	((diffw & 0x0700u) << (12 - 8)) \| // move imm3 from bits 8-10 to bits 12-14,
	((diffw & 0x00ffu)); // keep imm8 at bits 0-7.
	uint32_t movt = 0xf2c00000u \| // MOVT r0, #0 (placeholder),
	((difft & 0xf000u) << (16 - 12)) \| // move imm4 from bits 12-15 to bits 16-19,
	((difft & 0x0800u) << (26 - 11)) \| // move imm from bit 11 to bit 26,
	((difft & 0x0700u) << (12 - 8)) \| // move imm3 from bits 8-10 to bits 12-14,
	((difft & 0x00ffu)); // keep imm8 at bits 0-7.
	const uint8_t expected_code[] = {
	static_cast<uint8_t>(movw >> 16), static_cast<uint8_t>(movw >> 24),
	static_cast<uint8_t>(movw >> 0), static_cast<uint8_t>(movw >> 8),
	static_cast<uint8_t>(movt >> 16), static_cast<uint8_t>(movt >> 24),
	static_cast<uint8_t>(movt >> 0), static_cast<uint8_t>(movt >> 8),
	0x78, 0x44,
	};
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
	}

	TEST_F(Thumb2RelativePatcherTest, CallSelf) {
	LinkerPatch patches[] = {
	LinkerPatch::RelativeCodePatch(0u, nullptr, 1u),
	};
	AddCompiledMethod(MethodRef(1u), kCallCode, ArrayRef<const LinkerPatch>(patches));
	Link();

	static const uint8_t expected_code[] = {
	0xff, 0xf7, 0xfe, 0xff
	};
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
	}

	TEST_F(Thumb2RelativePatcherTest, CallOther) {
	LinkerPatch method1_patches[] = {
	LinkerPatch::RelativeCodePatch(0u, nullptr, 2u),
	};
	AddCompiledMethod(MethodRef(1u), kCallCode, ArrayRef<const LinkerPatch>(method1_patches));
	LinkerPatch method2_patches[] = {
	LinkerPatch::RelativeCodePatch(0u, nullptr, 1u),
	};
	AddCompiledMethod(MethodRef(2u), kCallCode, ArrayRef<const LinkerPatch>(method2_patches));
	Link();

	uint32_t method1_offset = GetMethodOffset(1u);
	uint32_t method2_offset = GetMethodOffset(2u);
	uint32_t diff_after = method2_offset - (method1_offset + 4u /* PC adjustment */);
	ASSERT_EQ(diff_after & 1u, 0u);
	ASSERT_LT(diff_after >> 1, 1u << 8); // Simple encoding, (diff_after >> 1) fits into 8 bits.
	static const uint8_t method1_expected_code[] = {
	0x00, 0xf0, static_cast<uint8_t>(diff_after >> 1), 0xf8
	};
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(method1_expected_code)));
	uint32_t diff_before = method1_offset - (method2_offset + 4u /* PC adjustment */);
	ASSERT_EQ(diff_before & 1u, 0u);
	ASSERT_GE(diff_before, -1u << 9); // Simple encoding, -256 <= (diff >> 1) < 0.
	auto method2_expected_code = GenNopsAndBl(0u, kBlMinus256 \| ((diff_before >> 1) & 0xffu));
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(2u), ArrayRef<const uint8_t>(method2_expected_code)));
	}

	TEST_F(Thumb2RelativePatcherTest, CallTrampoline) {
	LinkerPatch patches[] = {
	LinkerPatch::RelativeCodePatch(0u, nullptr, 2u),
	};
	AddCompiledMethod(MethodRef(1u), kCallCode, ArrayRef<const LinkerPatch>(patches));
	Link();

	uint32_t method1_offset = GetMethodOffset(1u);
	uint32_t diff = kTrampolineOffset - (method1_offset + 4u);
	ASSERT_EQ(diff & 1u, 0u);
	ASSERT_GE(diff, -1u << 9); // Simple encoding, -256 <= (diff >> 1) < 0 (checked as unsigned).
	auto expected_code = GenNopsAndBl(0u, kBlMinus256 \| ((diff >> 1) & 0xffu));
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
	}

	TEST_F(Thumb2RelativePatcherTest, CallTrampolineTooFar) {
	constexpr uint32_t missing_method_index = 1024u;
	auto method3_raw_code = GenNopsAndBl(3u, kBlPlus0);
	constexpr uint32_t bl_offset_in_method3 = 3u * 2u; // After NOPs.
	ArrayRef<const uint8_t> method3_code(method3_raw_code);
	ASSERT_EQ(bl_offset_in_method3 + 4u, method3_code.size());
	LinkerPatch method3_patches[] = {
	LinkerPatch::RelativeCodePatch(bl_offset_in_method3, nullptr, missing_method_index),
	};

	constexpr uint32_t just_over_max_negative_disp = 16 * MB + 2 - 4u /* PC adjustment */;
	bool thunk_in_gap = Create2MethodsWithGap(kNopCode,
	ArrayRef<const LinkerPatch>(),
	method3_code,
	ArrayRef<const LinkerPatch>(method3_patches),
	just_over_max_negative_disp - bl_offset_in_method3);
	ASSERT_FALSE(thunk_in_gap); // There should be a thunk but it should be after the method2.
	ASSERT_FALSE(method_offset_map_.FindMethodOffset(MethodRef(missing_method_index)).first);

	// Check linked code.
	uint32_t method3_offset = GetMethodOffset(3u);
	uint32_t thunk_offset = CompiledCode::AlignCode(method3_offset + method3_code.size(), kThumb2);
	uint32_t diff = thunk_offset - (method3_offset + bl_offset_in_method3 + 4u /* PC adjustment */);
	ASSERT_EQ(diff & 1u, 0u);
	ASSERT_LT(diff >> 1, 1u << 8); // Simple encoding, (diff >> 1) fits into 8 bits.
	auto expected_code = GenNopsAndBl(3u, kBlPlus0 \| ((diff >> 1) & 0xffu));
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(3u), ArrayRef<const uint8_t>(expected_code)));
	EXPECT_TRUE(CheckThunk(thunk_offset));
	}

	TEST_F(Thumb2RelativePatcherTest, CallOtherAlmostTooFarAfter) {
	auto method1_raw_code = GenNopsAndBl(3u, kBlPlus0);
	constexpr uint32_t bl_offset_in_method1 = 3u * 2u; // After NOPs.
	ArrayRef<const uint8_t> method1_code(method1_raw_code);
	ASSERT_EQ(bl_offset_in_method1 + 4u, method1_code.size());
	LinkerPatch method1_patches[] = {
	LinkerPatch::RelativeCodePatch(bl_offset_in_method1, nullptr, 3u),
	};

	constexpr uint32_t max_positive_disp = 16 * MB - 2u + 4u /* PC adjustment */;
	bool thunk_in_gap = Create2MethodsWithGap(method1_code,
	ArrayRef<const LinkerPatch>(method1_patches),
	kNopCode,
	ArrayRef<const LinkerPatch>(),
	bl_offset_in_method1 + max_positive_disp);
	ASSERT_FALSE(thunk_in_gap); // There should be no thunk.

	// Check linked code.
	auto expected_code = GenNopsAndBl(3u, kBlPlusMax);
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
	}

	TEST_F(Thumb2RelativePatcherTest, CallOtherAlmostTooFarBefore) {
	auto method3_raw_code = GenNopsAndBl(2u, kBlPlus0);
	constexpr uint32_t bl_offset_in_method3 = 2u * 2u; // After NOPs.
	ArrayRef<const uint8_t> method3_code(method3_raw_code);
	ASSERT_EQ(bl_offset_in_method3 + 4u, method3_code.size());
	LinkerPatch method3_patches[] = {
	LinkerPatch::RelativeCodePatch(bl_offset_in_method3, nullptr, 1u),
	};

	constexpr uint32_t just_over_max_negative_disp = 16 * MB - 4u /* PC adjustment */;
	bool thunk_in_gap = Create2MethodsWithGap(kNopCode,
	ArrayRef<const LinkerPatch>(),
	method3_code,
	ArrayRef<const LinkerPatch>(method3_patches),
	just_over_max_negative_disp - bl_offset_in_method3);
	ASSERT_FALSE(thunk_in_gap); // There should be no thunk.

	// Check linked code.
	auto expected_code = GenNopsAndBl(2u, kBlMinusMax);
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(3u), ArrayRef<const uint8_t>(expected_code)));
	}

	TEST_F(Thumb2RelativePatcherTest, CallOtherJustTooFarAfter) {
	auto method1_raw_code = GenNopsAndBl(2u, kBlPlus0);
	constexpr uint32_t bl_offset_in_method1 = 2u * 2u; // After NOPs.
	ArrayRef<const uint8_t> method1_code(method1_raw_code);
	ASSERT_EQ(bl_offset_in_method1 + 4u, method1_code.size());
	LinkerPatch method1_patches[] = {
	LinkerPatch::RelativeCodePatch(bl_offset_in_method1, nullptr, 3u),
	};

	constexpr uint32_t just_over_max_positive_disp = 16 * MB + 4u /* PC adjustment */;
	bool thunk_in_gap = Create2MethodsWithGap(method1_code,
	ArrayRef<const LinkerPatch>(method1_patches),
	kNopCode,
	ArrayRef<const LinkerPatch>(),
	bl_offset_in_method1 + just_over_max_positive_disp);
	ASSERT_TRUE(thunk_in_gap);

	uint32_t method1_offset = GetMethodOffset(1u);
	uint32_t method3_offset = GetMethodOffset(3u);
	uint32_t method3_header_offset = method3_offset - sizeof(OatQuickMethodHeader);
	ASSERT_TRUE(IsAligned<kArmAlignment>(method3_header_offset));
	uint32_t thunk_offset = method3_header_offset - CompiledCode::AlignCode(ThunkSize(), kThumb2);
	ASSERT_TRUE(IsAligned<kArmAlignment>(thunk_offset));
	uint32_t diff = thunk_offset - (method1_offset + bl_offset_in_method1 + 4u /* PC adjustment */);
	ASSERT_EQ(diff & 1u, 0u);
	ASSERT_GE(diff, 16 * MB - (1u << 9)); // Simple encoding, unknown bits fit into the low 8 bits.
	auto expected_code = GenNopsAndBl(2u, 0xf3ffd700 \| ((diff >> 1) & 0xffu));
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(1u), ArrayRef<const uint8_t>(expected_code)));
	CheckThunk(thunk_offset);
	}

	TEST_F(Thumb2RelativePatcherTest, CallOtherJustTooFarBefore) {
	auto method3_raw_code = GenNopsAndBl(3u, kBlPlus0);
	constexpr uint32_t bl_offset_in_method3 = 3u * 2u; // After NOPs.
	ArrayRef<const uint8_t> method3_code(method3_raw_code);
	ASSERT_EQ(bl_offset_in_method3 + 4u, method3_code.size());
	LinkerPatch method3_patches[] = {
	LinkerPatch::RelativeCodePatch(bl_offset_in_method3, nullptr, 1u),
	};

	constexpr uint32_t just_over_max_negative_disp = 16 * MB + 2 - 4u /* PC adjustment */;
	bool thunk_in_gap = Create2MethodsWithGap(kNopCode,
	ArrayRef<const LinkerPatch>(),
	method3_code,
	ArrayRef<const LinkerPatch>(method3_patches),
	just_over_max_negative_disp - bl_offset_in_method3);
	ASSERT_FALSE(thunk_in_gap); // There should be a thunk but it should be after the method2.

	// Check linked code.
	uint32_t method3_offset = GetMethodOffset(3u);
	uint32_t thunk_offset = CompiledCode::AlignCode(method3_offset + method3_code.size(), kThumb2);
	uint32_t diff = thunk_offset - (method3_offset + bl_offset_in_method3 + 4u /* PC adjustment */);
	ASSERT_EQ(diff & 1u, 0u);
	ASSERT_LT(diff >> 1, 1u << 8); // Simple encoding, (diff >> 1) fits into 8 bits.
	auto expected_code = GenNopsAndBl(3u, kBlPlus0 \| ((diff >> 1) & 0xffu));
	EXPECT_TRUE(CheckLinkedMethod(MethodRef(3u), ArrayRef<const uint8_t>(expected_code)));
	EXPECT_TRUE(CheckThunk(thunk_offset));
	}

	TEST_F(Thumb2RelativePatcherTest, DexCacheReference1) {
	TestDexCacheReference(0x00ff0000u, 0x00fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	TEST_F(Thumb2RelativePatcherTest, DexCacheReference2) {
	TestDexCacheReference(0x02ff0000u, 0x05fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	TEST_F(Thumb2RelativePatcherTest, DexCacheReference3) {
	TestDexCacheReference(0x08ff0000u, 0x08fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	TEST_F(Thumb2RelativePatcherTest, DexCacheReference4) {
	TestDexCacheReference(0xd0ff0000u, 0x60fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	TEST_F(Thumb2RelativePatcherTest, StringReference1) {
	TestStringReference(0x00ff00fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	TEST_F(Thumb2RelativePatcherTest, StringReference2) {
	TestStringReference(0x02ff05fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	TEST_F(Thumb2RelativePatcherTest, StringReference3) {
	TestStringReference(0x08ff08fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	TEST_F(Thumb2RelativePatcherTest, StringReference4) {
	TestStringReference(0xd0ff60fcu);
	ASSERT_LT(GetMethodOffset(1u), 0xfcu);
	}

	} // namespace linker
	} // namespace art