1    :  // Copyright 2012 Google Inc. All Rights Reserved.
   2    :  //
   3    :  // Licensed under the Apache License, Version 2.0 (the "License");
   4    :  // you may not use this file except in compliance with the License.
   5    :  // You may obtain a copy of the License at
   6    :  //
   7    :  //     http://www.apache.org/licenses/LICENSE-2.0
   8    :  //
   9    :  // Unless required by applicable law or agreed to in writing, software
  10    :  // distributed under the License is distributed on an "AS IS" BASIS,
  11    :  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    :  // See the License for the specific language governing permissions and
  13    :  // limitations under the License.
  14    :  
  15    :  #include "syzygy/reorder/orderers/explicit_orderer.h"
  16    :  
  17    :  #include <algorithm>
  18    :  #include <vector>
  19    :  
  20    :  #include "base/strings/stringprintf.h"
  21    :  
  22    :  namespace reorder {
  23    :  namespace orderers {
  24    :  
  25    :  namespace {
  26    :  
  27    :  using block_graph::BlockGraph;
  28    :  using block_graph::BlockVector;
  29    :  using core::RelativeAddress;
  30    :  
  31  E :  void GetSortedBlocks(BlockGraph* block_graph, BlockVector* blocks) {
  32  E :    DCHECK(block_graph != NULL);
  33  E :    DCHECK(blocks != NULL);
  34    :  
  35  E :    blocks->clear();
  36  E :    blocks->reserve(block_graph->blocks().size());
  37    :  
  38    :    BlockGraph::BlockMap::iterator block_it =
  39  E :        block_graph->blocks_mutable().begin();
  40  E :    for (; block_it != block_graph->blocks_mutable().end(); ++block_it) {
  41  E :      BlockGraph::Block* block = &block_it->second;
  42  E :      blocks->push_back(block);
  43  E :    }
  44    :  
  45    :    // Sort by block address.
  46  E :    std::sort(blocks->begin(), blocks->end());
  47  E :  }
  48    :  
  49    :  }  // namespace
  50    :  
  51    :  const char ExplicitOrderer::kOrdererName[] = "ExplicitOrderer";
  52    :  
  53    :  bool ExplicitOrderer::OrderBlockGraph(
  54    :      OrderedBlockGraph* ordered_block_graph,
  55  E :      BlockGraph::Block* /* header_block */) {
  56  E :    DCHECK(ordered_block_graph != NULL);
  57  E :    DCHECK(order_ != NULL);
  58    :  
  59  E :    BlockGraph* bg = ordered_block_graph->block_graph();
  60    :  
  61  E :    BlockVector sorted_blocks;
  62  E :    GetSortedBlocks(bg, &sorted_blocks);
  63    :  
  64    :    Reorderer::Order::SectionSpecVector::const_iterator section_it =
  65  E :        order_->sections.begin();
  66  E :    for (; section_it != order_->sections.end(); ++section_it) {
  67  E :      const Reorderer::Order::SectionSpec& section_spec = *section_it;
  68    :  
  69    :      // The section specification should always refer to a section that already
  70    :      // exists. They should all have been created by this point.
  71  E :      DCHECK_NE(Reorderer::Order::SectionSpec::kNewSectionId, section_spec.id);
  72    :  
  73    :      // You can't specify ordering for 'special' blocks that lie outside of any
  74    :      // explicit section.
  75  E :      DCHECK_NE(BlockGraph::kInvalidSectionId, section_spec.id);
  76    :  
  77    :      // Look up the section.
  78  E :      BlockGraph::Section* section = bg->GetSectionById(section_spec.id);
  79  E :      if (section == NULL) {
  80  E :        LOG(ERROR) << "No section found with ID " << section_spec.id << ".";
  81  E :        return false;
  82    :      }
  83    :  
  84  E :      DCHECK(section != NULL);
  85  E :      LOG(INFO) << "Applying order to section " << section->id()
  86    :                << " (" << section->name() << ").";
  87    :  
  88    :      // We walk through these in reverse order so that we can use PlaceAtHead.
  89  E :      for (size_t i = section_spec.blocks.size(); i > 0;) {
  90  E :        const Reorderer::Order::BlockSpec& block_spec = section_spec.blocks[--i];
  91    :  
  92    :        // Ensure the block-spec specifies a block without BB information. Any
  93    :        // BB ordering must already have been applied.
  94  E :        if (!block_spec.basic_block_offsets.empty()) {
  95  E :          LOG(ERROR) << "ExplicitOrderer can't handle basic-block orders.";
  96  E :          return false;
  97    :        }
  98    :  
  99    :        // Look for the block with the matching address in memory. We do this
 100    :        // just in case the BlockGraph has evolved since the order object was
 101    :        // built.
 102    :        BlockVector::const_iterator block_it =
 103    :            std::lower_bound(sorted_blocks.begin(),
 104    :                             sorted_blocks.end(),
 105  E :                             block_spec.block);
 106    :  
 107    :        // Not found?
 108  E :        if (block_it == sorted_blocks.end() || *block_it != block_spec.block) {
 109  E :          LOG(ERROR) << "Block specified in order does not exist in BlockGraph.";
 110  E :          return false;
 111    :        }
 112    :  
 113    :        // At this point we have a single unique block that we've found, so
 114    :        // place it at the beginning of the section.
 115  E :        ordered_block_graph->PlaceAtHead(section, *block_it);
 116  E :      }
 117  E :    }
 118    :  
 119  E :    return true;
 120  E :  }
 121    :  
 122    :  }  // namespace orderers
 123    :  }  // namespace reorder