1    :  // Copyright 2012 Google Inc.
   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/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    :    typedef Reorderer::Order::BlockListMap BlockListMap;
  62    :    typedef Reorderer::Order::BlockList BlockList;
  63    :  
  64  E :    BlockVector sorted_blocks;
  65  E :    GetSortedBlocks(bg, &sorted_blocks);
  66    :  
  67  E :    BlockListMap::const_iterator section_it = order_->section_block_lists.begin();
  68  E :    for (; section_it != order_->section_block_lists.end(); ++section_it) {
  69    :      // Find the section in the original block-graph with the same ID.
  70  E :      BlockGraph::Section* section = bg->GetSectionById(section_it->first);
  71  E :      if (section == NULL) {
  72  E :        LOG(ERROR) << "No section found with ID " << section_it->first << ".";
  73  E :        return false;
  74    :      }
  75    :  
  76  E :      LOG(INFO) << "Applying order to section " << section_it->first
  77    :                << "(" << section->name() << ").";
  78    :  
  79    :      // We walk through these in reverse order so that we can use PlaceAtHead.
  80  E :      for (size_t i = section_it->second.size(); i > 0; --i) {
  81    :        // Look for the block with the matching address in memory. We do this
  82    :        // just in case the BlockGraph has evolved since the order object was
  83    :        // built.
  84  E :        const BlockGraph::Block* block = section_it->second[i - 1];
  85    :        BlockVector::const_iterator block_it =
  86    :            std::lower_bound(sorted_blocks.begin(),
  87    :                             sorted_blocks.end(),
  88  E :                             block);
  89    :  
  90    :        // Not found?
  91  E :        if (block_it == sorted_blocks.end() || *block_it != block) {
  92  E :          LOG(ERROR) << "Block specified in order does not exist in BlockGraph.";
  93  E :          return false;
  94    :        }
  95    :  
  96    :        // At this point we have a single unique block that we've found, so
  97    :        // place it at the beginning of the section.
  98  E :        ordered_block_graph->PlaceAtHead(section, *block_it);
  99  E :      }
 100  E :    }
 101    :  
 102  E :    return true;
 103  E :  }
 104    :  
 105    :  }  // namespace orderers
 106    :  }  // namespace reorder