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/dead_code_finder.h"
  16    :  
  17    :  #include "gtest/gtest.h"
  18    :  #include "syzygy/block_graph/block_graph.h"
  19    :  #include "syzygy/core/address.h"
  20    :  #include "syzygy/core/random_number_generator.h"
  21    :  #include "syzygy/reorder/order_generator_test.h"
  22    :  
  23    :  namespace reorder {
  24    :  
  25    :  class DeadCodeFinderTest : public testing::OrderGeneratorTest {
  26    :   protected:
  27    :    typedef std::set<const block_graph::BlockGraph::Block*> BlockSet;
  28    :    typedef BlockSet::iterator BlockIter;
  29    :  
  30  E :    DeadCodeFinderTest() : random_(12345) {
  31  E :    }
  32    :  
  33    :    DeadCodeFinder dead_code_finder_;
  34    :    BlockSet live_blocks_;
  35    :    BlockSet dead_blocks_;
  36    :    core::RandomNumberGenerator random_;
  37    :  };
  38    :  
  39  E :  TEST_F(DeadCodeFinderTest, TestDLL) {
  40  E :    const size_t kNumBlocks = 20;
  41  E :    const char kSectionName[] = ".text";
  42    :    // Get the .text code section.
  43  E :    size_t section_index = input_dll_.GetSectionIndex(kSectionName);
  44    :    const IMAGE_SECTION_HEADER* section =
  45  E :        input_dll_.section_header(section_index);
  46  E :    ASSERT_TRUE(section != NULL);
  47    :  
  48    :    // Get a bunch of random blocks to visit (and consider live).
  49  E :    ASSERT_TRUE(live_blocks_.size() == 0);
  50  E :    while (live_blocks_.size() < kNumBlocks) {
  51    :      core::RelativeAddress addr(
  52  E :          section->VirtualAddress + random_(section->Misc.VirtualSize));
  53    :      const block_graph::BlockGraph::Block* block =
  54  E :          image_layout_.blocks.GetBlockByAddress(addr);
  55  E :      ASSERT_TRUE(block->addr() <= addr);
  56  E :      ASSERT_TRUE(addr <= block->addr() + block->size());
  57  E :      live_blocks_.insert(block);
  58  E :    }
  59    :  
  60    :    // Get a bunch of random blocks to NOT visit (and consider dead).
  61  E :    ASSERT_TRUE(dead_blocks_.size() == 0);
  62  E :    while (dead_blocks_.size() < kNumBlocks) {
  63    :      core::RelativeAddress addr(
  64  E :          section->VirtualAddress + random_(section->Misc.VirtualSize));
  65    :      const block_graph::BlockGraph::Block* block =
  66  E :          image_layout_.blocks.GetBlockByAddress(addr);
  67    :      if ((block->attributes() & block_graph::BlockGraph::GAP_BLOCK) == 0 &&
  68  E :          (live_blocks_.find(block) == live_blocks_.end())) {
  69  E :        dead_blocks_.insert(block);
  70    :      }
  71  E :    }
  72    :  
  73    :    // Generate calls to the live blocks.
  74  E :    dead_code_finder_.OnProcessStarted(1, GetSystemTime());
  75  E :    for (BlockIter it = live_blocks_.begin();  it != live_blocks_.end(); ++it) {
  76    :      dead_code_finder_.OnCodeBlockEntry(
  77  E :          *it, (*it)->addr(), 1, 1, GetSystemTime());
  78  E :    }
  79  E :    dead_code_finder_.OnProcessEnded(1, GetSystemTime());
  80    :  
  81    :    // Do the reordering.
  82    :    ASSERT_TRUE(dead_code_finder_.CalculateReordering(input_dll_,
  83    :                                                      image_layout_,
  84    :                                                      true,
  85    :                                                      false,
  86  E :                                                      &order_));
  87    :  
  88  E :    ExpectNoDuplicateBlocks();
  89    :  
  90    :    // Check the live blocks.
  91  E :    for (BlockIter it = live_blocks_.begin();  it != live_blocks_.end(); ++it) {
  92  E :      EXPECT_FALSE(dead_code_finder_.IsDead(*it))
  93    :          << "Block '" << (*it)->name() << "' was not expected to be dead.";
  94  E :    }
  95    :  
  96    :    // Check the dead blocks.
  97  E :    for (BlockIter it = dead_blocks_.begin();  it != dead_blocks_.end(); ++it) {
  98  E :      EXPECT_TRUE(dead_code_finder_.IsDead(*it))
  99    :          << "Block '" << (*it)->name() << "' was expected to be dead.";
 100  E :    }
 101    :  
 102    :    // Check the ordering.
 103  E :    ASSERT_EQ(image_layout_.sections.size(), order_.sections.size());
 104  E :    for (size_t i = 0; i < order_.sections.size(); ++i) {
 105  E :      EXPECT_EQ(image_layout_.sections[i].name, order_.sections[i].name);
 106    :      EXPECT_EQ(image_layout_.sections[i].characteristics,
 107  E :                order_.sections[i].characteristics);
 108  E :      if (i != section_index)
 109  E :        continue;
 110  E :      ASSERT_EQ(kSectionName, order_.sections[i].name);
 111  E :      EXPECT_GE(order_.sections[i].blocks.size(), dead_blocks_.size());
 112    :      Reorderer::Order::BlockSpecVector::const_iterator it =
 113  E :          order_.sections[0].blocks.begin();
 114  E :      for (; it != order_.sections[0].blocks.end(); ++it) {
 115  E :        EXPECT_TRUE(dead_code_finder_.IsDead(it->block));
 116  E :        EXPECT_TRUE(live_blocks_.find(it->block) == live_blocks_.end());
 117  E :      }
 118  E :    }
 119  E :  }
 120    :  
 121    :  }  // namespace reorder