dex2oat/linker/arm/relative_patcher_arm_base.cc - LeafOS-Project/android_art - Gitiles

 /*
  * 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/arm/relative_patcher_arm_base.h"

 #include "base/stl_util.h"
 #include "compiled_method-inl.h"
 #include "debug/method_debug_info.h"
 #include "dex/dex_file_types.h"
 #include "linker/linker_patch.h"
 #include "oat.h"
 #include "oat_quick_method_header.h"
 #include "stream/output_stream.h"

 namespace art {
 namespace linker {

 class ArmBaseRelativePatcher::ThunkData {
  public:
   ThunkData(ArrayRef<const uint8_t> code, const std::string& debug_name, uint32_t max_next_offset)
       : code_(code),
         debug_name_(debug_name),
         offsets_(),
         max_next_offset_(max_next_offset),
         pending_offset_(0u) {
     DCHECK(NeedsNextThunk());  // The data is constructed only when we expect to need the thunk.
   }

   ThunkData(ThunkData&& src) = default;

   size_t CodeSize() const {
     return code_.size();
   }

   ArrayRef<const uint8_t> GetCode() const {
     return code_;
   }

   const std::string& GetDebugName() const {
     return debug_name_;
   }

   bool NeedsNextThunk() const {
     return max_next_offset_ != 0u;
   }

   uint32_t MaxNextOffset() const {
     DCHECK(NeedsNextThunk());
     return max_next_offset_;
   }

   void ClearMaxNextOffset() {
     DCHECK(NeedsNextThunk());
     max_next_offset_ = 0u;
   }

   void SetMaxNextOffset(uint32_t max_next_offset) {
     DCHECK(!NeedsNextThunk());
     max_next_offset_ = max_next_offset;
   }

   // Adjust the MaxNextOffset() down if needed to fit the code before the next thunk.
   // Returns true if it was adjusted, false if the old value was kept.
   bool MakeSpaceBefore(const ThunkData& next_thunk, size_t alignment) {
     DCHECK(NeedsNextThunk());
     DCHECK(next_thunk.NeedsNextThunk());
     DCHECK_ALIGNED_PARAM(MaxNextOffset(), alignment);
     DCHECK_ALIGNED_PARAM(next_thunk.MaxNextOffset(), alignment);
     if (next_thunk.MaxNextOffset() - CodeSize() < MaxNextOffset()) {
       max_next_offset_ = RoundDown(next_thunk.MaxNextOffset() - CodeSize(), alignment);
       return true;
     } else {
       return false;
     }
   }

   uint32_t ReserveOffset(size_t offset) {
     DCHECK(NeedsNextThunk());
     DCHECK_LE(offset, max_next_offset_);
     max_next_offset_ = 0u;  // The reserved offset should satisfy all pending references.
     offsets_.push_back(offset);
     return offset + CodeSize();
   }

   bool HasReservedOffset() const {
     return !offsets_.empty();
   }

   uint32_t LastReservedOffset() const {
     DCHECK(HasReservedOffset());
     return offsets_.back();
   }

   bool HasPendingOffset() const {
     return pending_offset_ != offsets_.size();
   }

   uint32_t GetPendingOffset() const {
     DCHECK(HasPendingOffset());
     return offsets_[pending_offset_];
   }

   void MarkPendingOffsetAsWritten() {
     DCHECK(HasPendingOffset());
     ++pending_offset_;
   }

   bool HasWrittenOffset() const {
     return pending_offset_ != 0u;
   }

   uint32_t LastWrittenOffset() const {
     DCHECK(HasWrittenOffset());
     return offsets_[pending_offset_ - 1u];
   }

   size_t IndexOfFirstThunkAtOrAfter(uint32_t offset) const {
     size_t number_of_thunks = NumberOfThunks();
     for (size_t i = 0; i != number_of_thunks; ++i) {
       if (GetThunkOffset(i) >= offset) {
         return i;
       }
     }
     return number_of_thunks;
   }

   size_t NumberOfThunks() const {
     return offsets_.size();
   }

   uint32_t GetThunkOffset(size_t index) const {
     DCHECK_LT(index, NumberOfThunks());
     return offsets_[index];
   }

  private:
   const ArrayRef<const uint8_t> code_;  // The code of the thunk.
   const std::string debug_name_;        // The debug name of the thunk.
   std::vector<uint32_t> offsets_;       // Offsets at which the thunk needs to be written.
   uint32_t max_next_offset_;            // The maximum offset at which the next thunk can be placed.
   uint32_t pending_offset_;             // The index of the next offset to write.
 };

 class ArmBaseRelativePatcher::PendingThunkComparator {
  public:
   bool operator()(const ThunkData* lhs, const ThunkData* rhs) const {
     DCHECK(lhs->HasPendingOffset());
     DCHECK(rhs->HasPendingOffset());
     // The top of the heap is defined to contain the highest element and we want to pick
     // the thunk with the smallest pending offset, so use the reverse ordering, i.e. ">".
     return lhs->GetPendingOffset() > rhs->GetPendingOffset();
   }
 };

 uint32_t ArmBaseRelativePatcher::ReserveSpace(uint32_t offset,
                                               const CompiledMethod* compiled_method,
                                               MethodReference method_ref) {
   return ReserveSpaceInternal(offset, compiled_method, method_ref, 0u);
 }

 uint32_t ArmBaseRelativePatcher::ReserveSpaceEnd(uint32_t offset) {
   // For multi-oat compilations (boot image), ReserveSpaceEnd() is called for each oat file.
   // Since we do not know here whether this is the last file or whether the next opportunity
   // to place thunk will be soon enough, we need to reserve all needed thunks now. Code for
   // subsequent oat files can still call back to them.
   if (!unprocessed_method_call_patches_.empty()) {
     ResolveMethodCalls(offset, MethodReference(nullptr, dex::kDexNoIndex));
   }
   for (ThunkData* data : unreserved_thunks_) {
     uint32_t thunk_offset = CompiledCode::AlignCode(offset, instruction_set_);
     offset = data->ReserveOffset(thunk_offset);
   }
   unreserved_thunks_.clear();
   // We also need to delay initiating the pending_thunks_ until the call to WriteThunks().
   // Check that the `pending_thunks_.capacity()` indicates that no WriteThunks() has taken place.
   DCHECK_EQ(pending_thunks_.capacity(), 0u);
   return offset;
 }

 uint32_t ArmBaseRelativePatcher::WriteThunks(OutputStream* out, uint32_t offset) {
   if (pending_thunks_.capacity() == 0u) {
     if (thunks_.empty()) {
       return offset;
     }
     // First call to WriteThunks(), prepare the thunks for writing.
     pending_thunks_.reserve(thunks_.size());
     for (auto& entry : thunks_) {
       ThunkData* data = &entry.second;
       if (data->HasPendingOffset()) {
         pending_thunks_.push_back(data);
       }
     }
     std::make_heap(pending_thunks_.begin(), pending_thunks_.end(), PendingThunkComparator());
   }
   uint32_t aligned_offset = CompiledMethod::AlignCode(offset, instruction_set_);
   while (!pending_thunks_.empty() &&
          pending_thunks_.front()->GetPendingOffset() == aligned_offset) {
     // Write alignment bytes and code.
     uint32_t aligned_code_delta = aligned_offset - offset;
     if (aligned_code_delta != 0u && UNLIKELY(!WriteCodeAlignment(out, aligned_code_delta))) {
       return 0u;
     }
     if (UNLIKELY(!WriteThunk(out, pending_thunks_.front()->GetCode()))) {
       return 0u;
     }
     offset = aligned_offset + pending_thunks_.front()->CodeSize();
     // Mark the thunk as written at the pending offset and update the `pending_thunks_` heap.
     std::pop_heap(pending_thunks_.begin(), pending_thunks_.end(), PendingThunkComparator());
     pending_thunks_.back()->MarkPendingOffsetAsWritten();
     if (pending_thunks_.back()->HasPendingOffset()) {
       std::push_heap(pending_thunks_.begin(), pending_thunks_.end(), PendingThunkComparator());
     } else {
       pending_thunks_.pop_back();
     }
     aligned_offset = CompiledMethod::AlignCode(offset, instruction_set_);
   }
   DCHECK(pending_thunks_.empty() || pending_thunks_.front()->GetPendingOffset() > aligned_offset);
   return offset;
 }

 std::vector<debug::MethodDebugInfo> ArmBaseRelativePatcher::GenerateThunkDebugInfo(
     uint32_t executable_offset) {
   // For multi-oat compilation (boot image), `thunks_` records thunks for all oat files.
   // To return debug info for the current oat file, we must ignore thunks before the
   // `executable_offset` as they are in the previous oat files and this function must be
   // called before reserving thunk positions for subsequent oat files.
   size_t number_of_thunks = 0u;
   for (auto&& entry : thunks_) {
     const ThunkData& data = entry.second;
     number_of_thunks += data.NumberOfThunks() - data.IndexOfFirstThunkAtOrAfter(executable_offset);
   }
   std::vector<debug::MethodDebugInfo> result;
   result.reserve(number_of_thunks);
   for (auto&& entry : thunks_) {
     const ThunkData& data = entry.second;
     size_t start = data.IndexOfFirstThunkAtOrAfter(executable_offset);
     if (start == data.NumberOfThunks()) {
       continue;
     }
     // Get the base name to use for the first occurrence of the thunk.
     const std::string& base_name = data.GetDebugName();
     for (size_t i = start, num = data.NumberOfThunks(); i != num; ++i) {
       debug::MethodDebugInfo info = {};
       if (i == 0u) {
         info.custom_name = base_name;
       } else {
         // Add a disambiguating tag for subsequent identical thunks. Since the `thunks_`
         // keeps records also for thunks in previous oat files, names based on the thunk
         // index shall be unique across the whole multi-oat output.
         info.custom_name = base_name + "_" + std::to_string(i);
       }
       info.isa = instruction_set_;
       info.is_code_address_text_relative = true;
       info.code_address = data.GetThunkOffset(i) - executable_offset;
       info.code_size = data.CodeSize();
       result.push_back(std::move(info));
     }
   }
   return result;
 }

 ArmBaseRelativePatcher::ArmBaseRelativePatcher(RelativePatcherThunkProvider* thunk_provider,
                                                RelativePatcherTargetProvider* target_provider,
                                                InstructionSet instruction_set)
     : thunk_provider_(thunk_provider),
       target_provider_(target_provider),
       instruction_set_(instruction_set),
       thunks_(),
       unprocessed_method_call_patches_(),
       method_call_thunk_(nullptr),
       pending_thunks_() {
 }

 ArmBaseRelativePatcher::~ArmBaseRelativePatcher() {
   // All work done by member destructors.
 }

 uint32_t ArmBaseRelativePatcher::ReserveSpaceInternal(uint32_t offset,
                                                       const CompiledMethod* compiled_method,
                                                       MethodReference method_ref,
                                                       uint32_t max_extra_space) {
   // Adjust code size for extra space required by the subclass.
   uint32_t max_code_size = compiled_method->GetQuickCode().size() + max_extra_space;
   uint32_t code_offset;
   uint32_t next_aligned_offset;
   while (true) {
     code_offset = compiled_method->AlignCode(offset + sizeof(OatQuickMethodHeader));
     next_aligned_offset = compiled_method->AlignCode(code_offset + max_code_size);
     if (unreserved_thunks_.empty() ||
         unreserved_thunks_.front()->MaxNextOffset() >= next_aligned_offset) {
       break;
     }
     ThunkData* thunk = unreserved_thunks_.front();
     if (thunk == method_call_thunk_) {
       ResolveMethodCalls(code_offset, method_ref);
       // This may have changed `method_call_thunk_` data, so re-check if we need to reserve.
       if (unreserved_thunks_.empty() ||
           unreserved_thunks_.front()->MaxNextOffset() >= next_aligned_offset) {
         break;
       }
       // We need to process the new `front()` whether it's still the `method_call_thunk_` or not.
       thunk = unreserved_thunks_.front();
     }
     unreserved_thunks_.pop_front();
     uint32_t thunk_offset = CompiledCode::AlignCode(offset, instruction_set_);
     offset = thunk->ReserveOffset(thunk_offset);
     if (thunk == method_call_thunk_) {
       // All remaining method call patches will be handled by this thunk.
       DCHECK(!unprocessed_method_call_patches_.empty());
       DCHECK_LE(thunk_offset - unprocessed_method_call_patches_.front().GetPatchOffset(),
                 MaxPositiveDisplacement(GetMethodCallKey()));
       unprocessed_method_call_patches_.clear();
     }
   }

   // Process patches and check that adding thunks for the current method did not push any
   // thunks (previously existing or newly added) before `next_aligned_offset`. This is
   // essentially a check that we never compile a method that's too big. The calls or branches
   // from the method should be able to reach beyond the end of the method and over any pending
   // thunks. (The number of different thunks should be relatively low and their code short.)
   ProcessPatches(compiled_method, code_offset);
   CHECK(unreserved_thunks_.empty() ||
         unreserved_thunks_.front()->MaxNextOffset() >= next_aligned_offset);

   return offset;
 }

 uint32_t ArmBaseRelativePatcher::CalculateMethodCallDisplacement(uint32_t patch_offset,
                                                                  uint32_t target_offset) {
   DCHECK(method_call_thunk_ != nullptr);
   // Unsigned arithmetic with its well-defined overflow behavior is just fine here.
   uint32_t displacement = target_offset - patch_offset;
   uint32_t max_positive_displacement = MaxPositiveDisplacement(GetMethodCallKey());
   uint32_t max_negative_displacement = MaxNegativeDisplacement(GetMethodCallKey());
   // NOTE: With unsigned arithmetic we do mean to use && rather than || below.
   if (displacement > max_positive_displacement && displacement < -max_negative_displacement) {
     // Unwritten thunks have higher offsets, check if it's within range.
     DCHECK(!method_call_thunk_->HasPendingOffset() ||
            method_call_thunk_->GetPendingOffset() > patch_offset);
     if (method_call_thunk_->HasPendingOffset() &&
         method_call_thunk_->GetPendingOffset() - patch_offset <= max_positive_displacement) {
       displacement = method_call_thunk_->GetPendingOffset() - patch_offset;
     } else {
       // We must have a previous thunk then.
       DCHECK(method_call_thunk_->HasWrittenOffset());
       DCHECK_LT(method_call_thunk_->LastWrittenOffset(), patch_offset);
       displacement = method_call_thunk_->LastWrittenOffset() - patch_offset;
       DCHECK_GE(displacement, -max_negative_displacement);
     }
   }
   return displacement;
 }

 uint32_t ArmBaseRelativePatcher::GetThunkTargetOffset(const ThunkKey& key, uint32_t patch_offset) {
   auto it = thunks_.find(key);
   CHECK(it != thunks_.end());
   const ThunkData& data = it->second;
   if (data.HasWrittenOffset()) {
     uint32_t offset = data.LastWrittenOffset();
     DCHECK_LT(offset, patch_offset);
     if (patch_offset - offset <= MaxNegativeDisplacement(key)) {
       return offset;
     }
   }
   DCHECK(data.HasPendingOffset());
   uint32_t offset = data.GetPendingOffset();
   DCHECK_GT(offset, patch_offset);
   DCHECK_LE(offset - patch_offset, MaxPositiveDisplacement(key));
   return offset;
 }

 ArmBaseRelativePatcher::ThunkKey ArmBaseRelativePatcher::GetMethodCallKey() {
   return ThunkKey(ThunkType::kMethodCall);
 }

 ArmBaseRelativePatcher::ThunkKey ArmBaseRelativePatcher::GetEntrypointCallKey(
     const LinkerPatch& patch) {
   DCHECK_EQ(patch.GetType(), LinkerPatch::Type::kCallEntrypoint);
   return ThunkKey(ThunkType::kEntrypointCall, patch.EntrypointOffset());
 }

 ArmBaseRelativePatcher::ThunkKey ArmBaseRelativePatcher::GetBakerThunkKey(
     const LinkerPatch& patch) {
   DCHECK_EQ(patch.GetType(), LinkerPatch::Type::kBakerReadBarrierBranch);
   return ThunkKey(ThunkType::kBakerReadBarrier,
                   patch.GetBakerCustomValue1(),
                   patch.GetBakerCustomValue2());
 }

 void ArmBaseRelativePatcher::ProcessPatches(const CompiledMethod* compiled_method,
                                             uint32_t code_offset) {
   for (const LinkerPatch& patch : compiled_method->GetPatches()) {
     uint32_t patch_offset = code_offset + patch.LiteralOffset();
     ThunkKey key(static_cast<ThunkType>(-1));
     bool simple_thunk_patch = false;
     ThunkData* old_data = nullptr;
     if (patch.GetType() == LinkerPatch::Type::kCallRelative) {
       key = GetMethodCallKey();
       unprocessed_method_call_patches_.emplace_back(patch_offset, patch.TargetMethod());
       if (method_call_thunk_ == nullptr) {
         uint32_t max_next_offset = CalculateMaxNextOffset(patch_offset, key);
         auto it = thunks_.Put(key, ThunkDataForPatch(patch, max_next_offset));
         method_call_thunk_ = &it->second;
         AddUnreservedThunk(method_call_thunk_);
       } else {
         old_data = method_call_thunk_;
       }
     } else if (patch.GetType() == LinkerPatch::Type::kCallEntrypoint) {
       key = GetEntrypointCallKey(patch);
       simple_thunk_patch = true;
     } else if (patch.GetType() == LinkerPatch::Type::kBakerReadBarrierBranch) {
       key = GetBakerThunkKey(patch);
       simple_thunk_patch = true;
     }
     if (simple_thunk_patch) {
       auto lb = thunks_.lower_bound(key);
       if (lb == thunks_.end() || thunks_.key_comp()(key, lb->first)) {
         uint32_t max_next_offset = CalculateMaxNextOffset(patch_offset, key);
         auto it = thunks_.PutBefore(lb, key, ThunkDataForPatch(patch, max_next_offset));
         AddUnreservedThunk(&it->second);
       } else {
         old_data = &lb->second;
       }
     }
     if (old_data != nullptr) {
       // Shared path where an old thunk may need an update.
       DCHECK(key.GetType() != static_cast<ThunkType>(-1));
       DCHECK(!old_data->HasReservedOffset() || old_data->LastReservedOffset() < patch_offset);
       if (old_data->NeedsNextThunk()) {
         // Patches for a method are ordered by literal offset, so if we still need to place
         // this thunk for a previous patch, that thunk shall be in range for this patch.
         DCHECK_LE(old_data->MaxNextOffset(), CalculateMaxNextOffset(patch_offset, key));
       } else {
         if (!old_data->HasReservedOffset() ||
             patch_offset - old_data->LastReservedOffset() > MaxNegativeDisplacement(key)) {
           old_data->SetMaxNextOffset(CalculateMaxNextOffset(patch_offset, key));
           AddUnreservedThunk(old_data);
         }
       }
     }
   }
 }

 void ArmBaseRelativePatcher::AddUnreservedThunk(ThunkData* data) {
   DCHECK(data->NeedsNextThunk());
   size_t index = unreserved_thunks_.size();
   while (index != 0u && data->MaxNextOffset() < unreserved_thunks_[index - 1u]->MaxNextOffset()) {
     --index;
   }
   unreserved_thunks_.insert(unreserved_thunks_.begin() + index, data);
   // We may need to update the max next offset(s) if the thunk code would not fit.
   size_t alignment = GetInstructionSetAlignment(instruction_set_);
   if (index + 1u != unreserved_thunks_.size()) {
     // Note: Ignore the return value as we need to process previous thunks regardless.
     data->MakeSpaceBefore(*unreserved_thunks_[index + 1u], alignment);
   }
   // Make space for previous thunks. Once we find a pending thunk that does
   // not need an adjustment, we can stop.
   while (index != 0u && unreserved_thunks_[index - 1u]->MakeSpaceBefore(*data, alignment)) {
     --index;
     data = unreserved_thunks_[index];
   }
 }

 void ArmBaseRelativePatcher::ResolveMethodCalls(uint32_t quick_code_offset,
                                                 MethodReference method_ref) {
   DCHECK(!unreserved_thunks_.empty());
   DCHECK(!unprocessed_method_call_patches_.empty());
   DCHECK(method_call_thunk_ != nullptr);
   uint32_t max_positive_displacement = MaxPositiveDisplacement(GetMethodCallKey());
   uint32_t max_negative_displacement = MaxNegativeDisplacement(GetMethodCallKey());
   // Process as many patches as possible, stop only on unresolved targets or calls too far back.
   while (!unprocessed_method_call_patches_.empty()) {
     MethodReference target_method = unprocessed_method_call_patches_.front().GetTargetMethod();
     uint32_t patch_offset = unprocessed_method_call_patches_.front().GetPatchOffset();
     DCHECK(!method_call_thunk_->HasReservedOffset() ||
            method_call_thunk_->LastReservedOffset() <= patch_offset);
     if (!method_call_thunk_->HasReservedOffset() ||
         patch_offset - method_call_thunk_->LastReservedOffset() > max_negative_displacement) {
       // No previous thunk in range, check if we can reach the target directly.
       if (target_method == method_ref) {
         DCHECK_GT(quick_code_offset, patch_offset);
         if (quick_code_offset - patch_offset > max_positive_displacement) {
           break;
         }
       } else {
         auto result = target_provider_->FindMethodOffset(target_method);
         if (!result.first) {
           break;
         }
         uint32_t target_offset = result.second - CompiledCode::CodeDelta(instruction_set_);
         if (target_offset >= patch_offset) {
           DCHECK_LE(target_offset - patch_offset, max_positive_displacement);
         } else if (patch_offset - target_offset > max_negative_displacement) {
           break;
         }
       }
     }
     unprocessed_method_call_patches_.pop_front();
   }
   if (!unprocessed_method_call_patches_.empty()) {
     // Try to adjust the max next offset in `method_call_thunk_`. Do this conservatively only if
     // the thunk shall be at the end of the `unreserved_thunks_` to avoid dealing with overlaps.
     uint32_t new_max_next_offset =
         unprocessed_method_call_patches_.front().GetPatchOffset() + max_positive_displacement;
     if (new_max_next_offset >
         unreserved_thunks_.back()->MaxNextOffset() + unreserved_thunks_.back()->CodeSize()) {
       method_call_thunk_->ClearMaxNextOffset();
       method_call_thunk_->SetMaxNextOffset(new_max_next_offset);
       if (method_call_thunk_ != unreserved_thunks_.back()) {
         RemoveElement(unreserved_thunks_, method_call_thunk_);
         unreserved_thunks_.push_back(method_call_thunk_);
       }
     }
   } else {
     // We have resolved all method calls, we do not need a new thunk anymore.
     method_call_thunk_->ClearMaxNextOffset();
     RemoveElement(unreserved_thunks_, method_call_thunk_);
   }
 }

 inline uint32_t ArmBaseRelativePatcher::CalculateMaxNextOffset(uint32_t patch_offset,
                                                                const ThunkKey& key) {
   return RoundDown(patch_offset + MaxPositiveDisplacement(key),
                    GetInstructionSetAlignment(instruction_set_));
 }

 inline ArmBaseRelativePatcher::ThunkData ArmBaseRelativePatcher::ThunkDataForPatch(
     const LinkerPatch& patch, uint32_t max_next_offset) {
   ArrayRef<const uint8_t> code;
   std::string debug_name;
   thunk_provider_->GetThunkCode(patch, &code, &debug_name);
   DCHECK(!code.empty());
   return ThunkData(code, debug_name, max_next_offset);
 }

 }  // 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/arm/relative_patcher_arm_base.h"

	#include "base/stl_util.h"
	#include "compiled_method-inl.h"
	#include "debug/method_debug_info.h"
	#include "dex/dex_file_types.h"
	#include "linker/linker_patch.h"
	#include "oat.h"
	#include "oat_quick_method_header.h"
	#include "stream/output_stream.h"

	namespace art {
	namespace linker {

	class ArmBaseRelativePatcher::ThunkData {
	public:
	ThunkData(ArrayRef<const uint8_t> code, const std::string& debug_name, uint32_t max_next_offset)
	: code_(code),
	debug_name_(debug_name),
	offsets_(),
	max_next_offset_(max_next_offset),
	pending_offset_(0u) {
	DCHECK(NeedsNextThunk()); // The data is constructed only when we expect to need the thunk.
	}

	ThunkData(ThunkData&& src) = default;

	size_t CodeSize() const {
	return code_.size();
	}

	ArrayRef<const uint8_t> GetCode() const {
	return code_;
	}

	const std::string& GetDebugName() const {
	return debug_name_;
	}

	bool NeedsNextThunk() const {
	return max_next_offset_ != 0u;
	}

	uint32_t MaxNextOffset() const {
	DCHECK(NeedsNextThunk());
	return max_next_offset_;
	}

	void ClearMaxNextOffset() {
	DCHECK(NeedsNextThunk());
	max_next_offset_ = 0u;
	}

	void SetMaxNextOffset(uint32_t max_next_offset) {
	DCHECK(!NeedsNextThunk());
	max_next_offset_ = max_next_offset;
	}

	// Adjust the MaxNextOffset() down if needed to fit the code before the next thunk.
	// Returns true if it was adjusted, false if the old value was kept.
	bool MakeSpaceBefore(const ThunkData& next_thunk, size_t alignment) {
	DCHECK(NeedsNextThunk());
	DCHECK(next_thunk.NeedsNextThunk());
	DCHECK_ALIGNED_PARAM(MaxNextOffset(), alignment);
	DCHECK_ALIGNED_PARAM(next_thunk.MaxNextOffset(), alignment);
	if (next_thunk.MaxNextOffset() - CodeSize() < MaxNextOffset()) {
	max_next_offset_ = RoundDown(next_thunk.MaxNextOffset() - CodeSize(), alignment);
	return true;
	} else {
	return false;
	}
	}

	uint32_t ReserveOffset(size_t offset) {
	DCHECK(NeedsNextThunk());
	DCHECK_LE(offset, max_next_offset_);
	max_next_offset_ = 0u; // The reserved offset should satisfy all pending references.
	offsets_.push_back(offset);
	return offset + CodeSize();
	}

	bool HasReservedOffset() const {
	return !offsets_.empty();
	}

	uint32_t LastReservedOffset() const {
	DCHECK(HasReservedOffset());
	return offsets_.back();
	}

	bool HasPendingOffset() const {
	return pending_offset_ != offsets_.size();
	}

	uint32_t GetPendingOffset() const {
	DCHECK(HasPendingOffset());
	return offsets_[pending_offset_];
	}

	void MarkPendingOffsetAsWritten() {
	DCHECK(HasPendingOffset());
	++pending_offset_;
	}

	bool HasWrittenOffset() const {
	return pending_offset_ != 0u;
	}

	uint32_t LastWrittenOffset() const {
	DCHECK(HasWrittenOffset());
	return offsets_[pending_offset_ - 1u];
	}

	size_t IndexOfFirstThunkAtOrAfter(uint32_t offset) const {
	size_t number_of_thunks = NumberOfThunks();
	for (size_t i = 0; i != number_of_thunks; ++i) {
	if (GetThunkOffset(i) >= offset) {
	return i;
	}
	}
	return number_of_thunks;
	}

	size_t NumberOfThunks() const {
	return offsets_.size();
	}

	uint32_t GetThunkOffset(size_t index) const {
	DCHECK_LT(index, NumberOfThunks());
	return offsets_[index];
	}

	private:
	const ArrayRef<const uint8_t> code_; // The code of the thunk.
	const std::string debug_name_; // The debug name of the thunk.
	std::vector<uint32_t> offsets_; // Offsets at which the thunk needs to be written.
	uint32_t max_next_offset_; // The maximum offset at which the next thunk can be placed.
	uint32_t pending_offset_; // The index of the next offset to write.
	};

	class ArmBaseRelativePatcher::PendingThunkComparator {
	public:
	bool operator()(const ThunkData* lhs, const ThunkData* rhs) const {
	DCHECK(lhs->HasPendingOffset());
	DCHECK(rhs->HasPendingOffset());
	// The top of the heap is defined to contain the highest element and we want to pick
	// the thunk with the smallest pending offset, so use the reverse ordering, i.e. ">".
	return lhs->GetPendingOffset() > rhs->GetPendingOffset();
	}
	};

	uint32_t ArmBaseRelativePatcher::ReserveSpace(uint32_t offset,
	const CompiledMethod* compiled_method,
	MethodReference method_ref) {
	return ReserveSpaceInternal(offset, compiled_method, method_ref, 0u);
	}

	uint32_t ArmBaseRelativePatcher::ReserveSpaceEnd(uint32_t offset) {
	// For multi-oat compilations (boot image), ReserveSpaceEnd() is called for each oat file.
	// Since we do not know here whether this is the last file or whether the next opportunity
	// to place thunk will be soon enough, we need to reserve all needed thunks now. Code for
	// subsequent oat files can still call back to them.
	if (!unprocessed_method_call_patches_.empty()) {
	ResolveMethodCalls(offset, MethodReference(nullptr, dex::kDexNoIndex));
	}
	for (ThunkData* data : unreserved_thunks_) {
	uint32_t thunk_offset = CompiledCode::AlignCode(offset, instruction_set_);
	offset = data->ReserveOffset(thunk_offset);
	}
	unreserved_thunks_.clear();
	// We also need to delay initiating the pending_thunks_ until the call to WriteThunks().
	// Check that the `pending_thunks_.capacity()` indicates that no WriteThunks() has taken place.
	DCHECK_EQ(pending_thunks_.capacity(), 0u);
	return offset;
	}

	uint32_t ArmBaseRelativePatcher::WriteThunks(OutputStream* out, uint32_t offset) {
	if (pending_thunks_.capacity() == 0u) {
	if (thunks_.empty()) {
	return offset;
	}
	// First call to WriteThunks(), prepare the thunks for writing.
	pending_thunks_.reserve(thunks_.size());
	for (auto& entry : thunks_) {
	ThunkData* data = &entry.second;
	if (data->HasPendingOffset()) {
	pending_thunks_.push_back(data);
	}
	}
	std::make_heap(pending_thunks_.begin(), pending_thunks_.end(), PendingThunkComparator());
	}
	uint32_t aligned_offset = CompiledMethod::AlignCode(offset, instruction_set_);
	while (!pending_thunks_.empty() &&
	pending_thunks_.front()->GetPendingOffset() == aligned_offset) {
	// Write alignment bytes and code.
	uint32_t aligned_code_delta = aligned_offset - offset;
	if (aligned_code_delta != 0u && UNLIKELY(!WriteCodeAlignment(out, aligned_code_delta))) {
	return 0u;
	}
	if (UNLIKELY(!WriteThunk(out, pending_thunks_.front()->GetCode()))) {
	return 0u;
	}
	offset = aligned_offset + pending_thunks_.front()->CodeSize();
	// Mark the thunk as written at the pending offset and update the `pending_thunks_` heap.
	std::pop_heap(pending_thunks_.begin(), pending_thunks_.end(), PendingThunkComparator());
	pending_thunks_.back()->MarkPendingOffsetAsWritten();
	if (pending_thunks_.back()->HasPendingOffset()) {
	std::push_heap(pending_thunks_.begin(), pending_thunks_.end(), PendingThunkComparator());
	} else {
	pending_thunks_.pop_back();
	}
	aligned_offset = CompiledMethod::AlignCode(offset, instruction_set_);
	}
	DCHECK(pending_thunks_.empty() \|\| pending_thunks_.front()->GetPendingOffset() > aligned_offset);
	return offset;
	}

	std::vector<debug::MethodDebugInfo> ArmBaseRelativePatcher::GenerateThunkDebugInfo(
	uint32_t executable_offset) {
	// For multi-oat compilation (boot image), `thunks_` records thunks for all oat files.
	// To return debug info for the current oat file, we must ignore thunks before the
	// `executable_offset` as they are in the previous oat files and this function must be
	// called before reserving thunk positions for subsequent oat files.
	size_t number_of_thunks = 0u;
	for (auto&& entry : thunks_) {
	const ThunkData& data = entry.second;
	number_of_thunks += data.NumberOfThunks() - data.IndexOfFirstThunkAtOrAfter(executable_offset);
	}
	std::vector<debug::MethodDebugInfo> result;
	result.reserve(number_of_thunks);
	for (auto&& entry : thunks_) {
	const ThunkData& data = entry.second;
	size_t start = data.IndexOfFirstThunkAtOrAfter(executable_offset);
	if (start == data.NumberOfThunks()) {
	continue;
	}
	// Get the base name to use for the first occurrence of the thunk.
	const std::string& base_name = data.GetDebugName();
	for (size_t i = start, num = data.NumberOfThunks(); i != num; ++i) {
	debug::MethodDebugInfo info = {};
	if (i == 0u) {
	info.custom_name = base_name;
	} else {
	// Add a disambiguating tag for subsequent identical thunks. Since the `thunks_`
	// keeps records also for thunks in previous oat files, names based on the thunk
	// index shall be unique across the whole multi-oat output.
	info.custom_name = base_name + "_" + std::to_string(i);
	}
	info.isa = instruction_set_;
	info.is_code_address_text_relative = true;
	info.code_address = data.GetThunkOffset(i) - executable_offset;
	info.code_size = data.CodeSize();
	result.push_back(std::move(info));
	}
	}
	return result;
	}

	ArmBaseRelativePatcher::ArmBaseRelativePatcher(RelativePatcherThunkProvider* thunk_provider,
	RelativePatcherTargetProvider* target_provider,
	InstructionSet instruction_set)
	: thunk_provider_(thunk_provider),
	target_provider_(target_provider),
	instruction_set_(instruction_set),
	thunks_(),
	unprocessed_method_call_patches_(),
	method_call_thunk_(nullptr),
	pending_thunks_() {
	}

	ArmBaseRelativePatcher::~ArmBaseRelativePatcher() {
	// All work done by member destructors.
	}

	uint32_t ArmBaseRelativePatcher::ReserveSpaceInternal(uint32_t offset,
	const CompiledMethod* compiled_method,
	MethodReference method_ref,
	uint32_t max_extra_space) {
	// Adjust code size for extra space required by the subclass.
	uint32_t max_code_size = compiled_method->GetQuickCode().size() + max_extra_space;
	uint32_t code_offset;
	uint32_t next_aligned_offset;
	while (true) {
	code_offset = compiled_method->AlignCode(offset + sizeof(OatQuickMethodHeader));
	next_aligned_offset = compiled_method->AlignCode(code_offset + max_code_size);
	if (unreserved_thunks_.empty() \|\|
	unreserved_thunks_.front()->MaxNextOffset() >= next_aligned_offset) {
	break;
	}
	ThunkData* thunk = unreserved_thunks_.front();
	if (thunk == method_call_thunk_) {
	ResolveMethodCalls(code_offset, method_ref);
	// This may have changed `method_call_thunk_` data, so re-check if we need to reserve.
	if (unreserved_thunks_.empty() \|\|
	unreserved_thunks_.front()->MaxNextOffset() >= next_aligned_offset) {
	break;
	}
	// We need to process the new `front()` whether it's still the `method_call_thunk_` or not.
	thunk = unreserved_thunks_.front();
	}
	unreserved_thunks_.pop_front();
	uint32_t thunk_offset = CompiledCode::AlignCode(offset, instruction_set_);
	offset = thunk->ReserveOffset(thunk_offset);
	if (thunk == method_call_thunk_) {
	// All remaining method call patches will be handled by this thunk.
	DCHECK(!unprocessed_method_call_patches_.empty());
	DCHECK_LE(thunk_offset - unprocessed_method_call_patches_.front().GetPatchOffset(),
	MaxPositiveDisplacement(GetMethodCallKey()));
	unprocessed_method_call_patches_.clear();
	}
	}

	// Process patches and check that adding thunks for the current method did not push any
	// thunks (previously existing or newly added) before `next_aligned_offset`. This is
	// essentially a check that we never compile a method that's too big. The calls or branches
	// from the method should be able to reach beyond the end of the method and over any pending
	// thunks. (The number of different thunks should be relatively low and their code short.)
	ProcessPatches(compiled_method, code_offset);
	CHECK(unreserved_thunks_.empty() \|\|
	unreserved_thunks_.front()->MaxNextOffset() >= next_aligned_offset);

	return offset;
	}

	uint32_t ArmBaseRelativePatcher::CalculateMethodCallDisplacement(uint32_t patch_offset,
	uint32_t target_offset) {
	DCHECK(method_call_thunk_ != nullptr);
	// Unsigned arithmetic with its well-defined overflow behavior is just fine here.
	uint32_t displacement = target_offset - patch_offset;
	uint32_t max_positive_displacement = MaxPositiveDisplacement(GetMethodCallKey());
	uint32_t max_negative_displacement = MaxNegativeDisplacement(GetMethodCallKey());
	// NOTE: With unsigned arithmetic we do mean to use && rather than \|\| below.
	if (displacement > max_positive_displacement && displacement < -max_negative_displacement) {
	// Unwritten thunks have higher offsets, check if it's within range.
	DCHECK(!method_call_thunk_->HasPendingOffset() \|\|
	method_call_thunk_->GetPendingOffset() > patch_offset);
	if (method_call_thunk_->HasPendingOffset() &&
	method_call_thunk_->GetPendingOffset() - patch_offset <= max_positive_displacement) {
	displacement = method_call_thunk_->GetPendingOffset() - patch_offset;
	} else {
	// We must have a previous thunk then.
	DCHECK(method_call_thunk_->HasWrittenOffset());
	DCHECK_LT(method_call_thunk_->LastWrittenOffset(), patch_offset);
	displacement = method_call_thunk_->LastWrittenOffset() - patch_offset;
	DCHECK_GE(displacement, -max_negative_displacement);
	}
	}
	return displacement;
	}

	uint32_t ArmBaseRelativePatcher::GetThunkTargetOffset(const ThunkKey& key, uint32_t patch_offset) {
	auto it = thunks_.find(key);
	CHECK(it != thunks_.end());
	const ThunkData& data = it->second;
	if (data.HasWrittenOffset()) {
	uint32_t offset = data.LastWrittenOffset();
	DCHECK_LT(offset, patch_offset);
	if (patch_offset - offset <= MaxNegativeDisplacement(key)) {
	return offset;
	}
	}
	DCHECK(data.HasPendingOffset());
	uint32_t offset = data.GetPendingOffset();
	DCHECK_GT(offset, patch_offset);
	DCHECK_LE(offset - patch_offset, MaxPositiveDisplacement(key));
	return offset;
	}

	ArmBaseRelativePatcher::ThunkKey ArmBaseRelativePatcher::GetMethodCallKey() {
	return ThunkKey(ThunkType::kMethodCall);
	}

	ArmBaseRelativePatcher::ThunkKey ArmBaseRelativePatcher::GetEntrypointCallKey(
	const LinkerPatch& patch) {
	DCHECK_EQ(patch.GetType(), LinkerPatch::Type::kCallEntrypoint);
	return ThunkKey(ThunkType::kEntrypointCall, patch.EntrypointOffset());
	}

	ArmBaseRelativePatcher::ThunkKey ArmBaseRelativePatcher::GetBakerThunkKey(
	const LinkerPatch& patch) {
	DCHECK_EQ(patch.GetType(), LinkerPatch::Type::kBakerReadBarrierBranch);
	return ThunkKey(ThunkType::kBakerReadBarrier,
	patch.GetBakerCustomValue1(),
	patch.GetBakerCustomValue2());
	}

	void ArmBaseRelativePatcher::ProcessPatches(const CompiledMethod* compiled_method,
	uint32_t code_offset) {
	for (const LinkerPatch& patch : compiled_method->GetPatches()) {
	uint32_t patch_offset = code_offset + patch.LiteralOffset();
	ThunkKey key(static_cast<ThunkType>(-1));
	bool simple_thunk_patch = false;
	ThunkData* old_data = nullptr;
	if (patch.GetType() == LinkerPatch::Type::kCallRelative) {
	key = GetMethodCallKey();
	unprocessed_method_call_patches_.emplace_back(patch_offset, patch.TargetMethod());
	if (method_call_thunk_ == nullptr) {
	uint32_t max_next_offset = CalculateMaxNextOffset(patch_offset, key);
	auto it = thunks_.Put(key, ThunkDataForPatch(patch, max_next_offset));
	method_call_thunk_ = &it->second;
	AddUnreservedThunk(method_call_thunk_);
	} else {
	old_data = method_call_thunk_;
	}
	} else if (patch.GetType() == LinkerPatch::Type::kCallEntrypoint) {
	key = GetEntrypointCallKey(patch);
	simple_thunk_patch = true;
	} else if (patch.GetType() == LinkerPatch::Type::kBakerReadBarrierBranch) {
	key = GetBakerThunkKey(patch);
	simple_thunk_patch = true;
	}
	if (simple_thunk_patch) {
	auto lb = thunks_.lower_bound(key);
	if (lb == thunks_.end() \|\| thunks_.key_comp()(key, lb->first)) {
	uint32_t max_next_offset = CalculateMaxNextOffset(patch_offset, key);
	auto it = thunks_.PutBefore(lb, key, ThunkDataForPatch(patch, max_next_offset));
	AddUnreservedThunk(&it->second);
	} else {
	old_data = &lb->second;
	}
	}
	if (old_data != nullptr) {
	// Shared path where an old thunk may need an update.
	DCHECK(key.GetType() != static_cast<ThunkType>(-1));
	DCHECK(!old_data->HasReservedOffset() \|\| old_data->LastReservedOffset() < patch_offset);
	if (old_data->NeedsNextThunk()) {
	// Patches for a method are ordered by literal offset, so if we still need to place
	// this thunk for a previous patch, that thunk shall be in range for this patch.
	DCHECK_LE(old_data->MaxNextOffset(), CalculateMaxNextOffset(patch_offset, key));
	} else {
	if (!old_data->HasReservedOffset() \|\|
	patch_offset - old_data->LastReservedOffset() > MaxNegativeDisplacement(key)) {
	old_data->SetMaxNextOffset(CalculateMaxNextOffset(patch_offset, key));
	AddUnreservedThunk(old_data);
	}
	}
	}
	}
	}

	void ArmBaseRelativePatcher::AddUnreservedThunk(ThunkData* data) {
	DCHECK(data->NeedsNextThunk());
	size_t index = unreserved_thunks_.size();
	while (index != 0u && data->MaxNextOffset() < unreserved_thunks_[index - 1u]->MaxNextOffset()) {
	--index;
	}
	unreserved_thunks_.insert(unreserved_thunks_.begin() + index, data);
	// We may need to update the max next offset(s) if the thunk code would not fit.
	size_t alignment = GetInstructionSetAlignment(instruction_set_);
	if (index + 1u != unreserved_thunks_.size()) {
	// Note: Ignore the return value as we need to process previous thunks regardless.
	data->MakeSpaceBefore(*unreserved_thunks_[index + 1u], alignment);
	}
	// Make space for previous thunks. Once we find a pending thunk that does
	// not need an adjustment, we can stop.
	while (index != 0u && unreserved_thunks_[index - 1u]->MakeSpaceBefore(*data, alignment)) {
	--index;
	data = unreserved_thunks_[index];
	}
	}

	void ArmBaseRelativePatcher::ResolveMethodCalls(uint32_t quick_code_offset,
	MethodReference method_ref) {
	DCHECK(!unreserved_thunks_.empty());
	DCHECK(!unprocessed_method_call_patches_.empty());
	DCHECK(method_call_thunk_ != nullptr);
	uint32_t max_positive_displacement = MaxPositiveDisplacement(GetMethodCallKey());
	uint32_t max_negative_displacement = MaxNegativeDisplacement(GetMethodCallKey());
	// Process as many patches as possible, stop only on unresolved targets or calls too far back.
	while (!unprocessed_method_call_patches_.empty()) {
	MethodReference target_method = unprocessed_method_call_patches_.front().GetTargetMethod();
	uint32_t patch_offset = unprocessed_method_call_patches_.front().GetPatchOffset();
	DCHECK(!method_call_thunk_->HasReservedOffset() \|\|
	method_call_thunk_->LastReservedOffset() <= patch_offset);
	if (!method_call_thunk_->HasReservedOffset() \|\|
	patch_offset - method_call_thunk_->LastReservedOffset() > max_negative_displacement) {
	// No previous thunk in range, check if we can reach the target directly.
	if (target_method == method_ref) {
	DCHECK_GT(quick_code_offset, patch_offset);
	if (quick_code_offset - patch_offset > max_positive_displacement) {
	break;
	}
	} else {
	auto result = target_provider_->FindMethodOffset(target_method);
	if (!result.first) {
	break;
	}
	uint32_t target_offset = result.second - CompiledCode::CodeDelta(instruction_set_);
	if (target_offset >= patch_offset) {
	DCHECK_LE(target_offset - patch_offset, max_positive_displacement);
	} else if (patch_offset - target_offset > max_negative_displacement) {
	break;
	}
	}
	}
	unprocessed_method_call_patches_.pop_front();
	}
	if (!unprocessed_method_call_patches_.empty()) {
	// Try to adjust the max next offset in `method_call_thunk_`. Do this conservatively only if
	// the thunk shall be at the end of the `unreserved_thunks_` to avoid dealing with overlaps.
	uint32_t new_max_next_offset =
	unprocessed_method_call_patches_.front().GetPatchOffset() + max_positive_displacement;
	if (new_max_next_offset >
	unreserved_thunks_.back()->MaxNextOffset() + unreserved_thunks_.back()->CodeSize()) {
	method_call_thunk_->ClearMaxNextOffset();
	method_call_thunk_->SetMaxNextOffset(new_max_next_offset);
	if (method_call_thunk_ != unreserved_thunks_.back()) {
	RemoveElement(unreserved_thunks_, method_call_thunk_);
	unreserved_thunks_.push_back(method_call_thunk_);
	}
	}
	} else {
	// We have resolved all method calls, we do not need a new thunk anymore.
	method_call_thunk_->ClearMaxNextOffset();
	RemoveElement(unreserved_thunks_, method_call_thunk_);
	}
	}

	inline uint32_t ArmBaseRelativePatcher::CalculateMaxNextOffset(uint32_t patch_offset,
	const ThunkKey& key) {
	return RoundDown(patch_offset + MaxPositiveDisplacement(key),
	GetInstructionSetAlignment(instruction_set_));
	}

	inline ArmBaseRelativePatcher::ThunkData ArmBaseRelativePatcher::ThunkDataForPatch(
	const LinkerPatch& patch, uint32_t max_next_offset) {
	ArrayRef<const uint8_t> code;
	std::string debug_name;
	thunk_provider_->GetThunkCode(patch, &code, &debug_name);
	DCHECK(!code.empty());
	return ThunkData(code, debug_name, max_next_offset);
	}

	} // namespace linker
	} // namespace art