courgette/disassembler.cc

   1 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "courgette/disassembler.h"
   6
   7 #include <algorithm>
   8 #include <string>
   9 #include <vector>
  10
  11 #include "base/basictypes.h"
  12 #include "base/logging.h"
  13
  14 #include "courgette/assembly_program.h"
  15 #include "courgette/courgette.h"
  16 #include "courgette/encoded_program.h"
  17 #include "courgette/image_info.h"
  18
  19 // COURGETTE_HISTOGRAM_TARGETS prints out a histogram of how frequently
  20 // different target addresses are referenced.  Purely for debugging.
  21 #define COURGETTE_HISTOGRAM_TARGETS 0
  22
  23 namespace courgette {
  24
  25 class DisassemblerWin32X86 : public Disassembler {
  26  public:
  27   explicit DisassemblerWin32X86(PEInfo* pe_info)
  28       : pe_info_(pe_info),
  29         incomplete_disassembly_(false) {
  30   }
  31
  32   virtual bool Disassemble(AssemblyProgram* target);
  33
  34   virtual void Destroy() { delete this; }
  35
  36  protected:
  37   PEInfo& pe_info() { return *pe_info_; }
  38
  39   void ParseFile(AssemblyProgram* target);
  40   bool ParseAbs32Relocs();
  41   void ParseRel32RelocsFromSections();
  42   void ParseRel32RelocsFromSection(const Section* section);
  43
  44   void ParseNonSectionFileRegion(uint32 start_file_offset,
  45                                  uint32 end_file_offset,
  46                                  AssemblyProgram* program);
  47   void ParseFileRegion(const Section* section,
  48                        uint32 start_file_offset, uint32 end_file_offset,
  49                        AssemblyProgram* program);
  50
  51 #if COURGETTE_HISTOGRAM_TARGETS
  52   void HistogramTargets(const char* kind, const std::map<RVA, int>& map);
  53 #endif
  54
  55   PEInfo* pe_info_;
  56   bool incomplete_disassembly_;  // 'true' if can leave out 'uninteresting' bits
  57
  58   std::vector<RVA> abs32_locations_;
  59   std::vector<RVA> rel32_locations_;
  60
  61 #if COURGETTE_HISTOGRAM_TARGETS
  62   std::map<RVA, int> abs32_target_rvas_;
  63   std::map<RVA, int> rel32_target_rvas_;
  64 #endif
  65 };
  66
  67 bool DisassemblerWin32X86::Disassemble(AssemblyProgram* target) {
  68   if (!pe_info().ok())
  69     return false;
  70
  71   target->set_image_base(pe_info().image_base());
  72
  73   if (!ParseAbs32Relocs())
  74     return false;
  75
  76   ParseRel32RelocsFromSections();
  77
  78   ParseFile(target);
  79
  80   target->DefaultAssignIndexes();
  81   return true;
  82 }
  83
  84 static uint32 Read32LittleEndian(const void* address) {
  85   return *reinterpret_cast<const uint32*>(address);
  86 }
  87
  88 bool DisassemblerWin32X86::ParseAbs32Relocs() {
  89   abs32_locations_.clear();
  90   if (!pe_info().ParseRelocs(&abs32_locations_))
  91     return false;
  92
  93   std::sort(abs32_locations_.begin(), abs32_locations_.end());
  94
  95 #if COURGETTE_HISTOGRAM_TARGETS
  96   for (size_t i = 0;  i < abs32_locations_.size(); ++i) {
  97     RVA rva = abs32_locations_[i];
  98     // The 4 bytes at the relocation are a reference to some address.
  99     uint32 target_address = Read32LittleEndian(pe_info().RVAToPointer(rva));
 100     ++abs32_target_rvas_[target_address - pe_info().image_base()];
 101   }
 102 #endif
 103   return true;
 104 }
 105
 106 void DisassemblerWin32X86::ParseRel32RelocsFromSections() {
 107   uint32 file_offset = 0;
 108   while (file_offset < pe_info().length()) {
 109     const Section* section = pe_info().FindNextSection(file_offset);
 110     if (section == NULL)
 111       break;
 112     if (file_offset < section->file_offset_of_raw_data)
 113       file_offset = section->file_offset_of_raw_data;
 114     ParseRel32RelocsFromSection(section);
 115     file_offset += section->size_of_raw_data;
 116   }
 117   std::sort(rel32_locations_.begin(), rel32_locations_.end());
 118
 119 #if COURGETTE_HISTOGRAM_TARGETS
 120   LOG(INFO) << "abs32_locations_ " << abs32_locations_.size();
 121   LOG(INFO) << "rel32_locations_ " << rel32_locations_.size();
 122   LOG(INFO) << "abs32_target_rvas_ " << abs32_target_rvas_.size();
 123   LOG(INFO) << "rel32_target_rvas_ " << rel32_target_rvas_.size();
 124
 125   int common = 0;
 126   std::map<RVA, int>::iterator abs32_iter = abs32_target_rvas_.begin();
 127   std::map<RVA, int>::iterator rel32_iter = rel32_target_rvas_.begin();
 128   while (abs32_iter != abs32_target_rvas_.end() &&
 129          rel32_iter != rel32_target_rvas_.end()) {
 130     if (abs32_iter->first < rel32_iter->first)
 131       ++abs32_iter;
 132     else if (rel32_iter->first < abs32_iter->first)
 133       ++rel32_iter;
 134     else {
 135       ++common;
 136       ++abs32_iter;
 137       ++rel32_iter;
 138     }
 139   }
 140   LOG(INFO) << "common " << common;
 141 #endif
 142 }
 143
 144 void DisassemblerWin32X86::ParseRel32RelocsFromSection(const Section* section) {
 145   // TODO(sra): use characteristic.
 146   bool isCode = strcmp(section->name, ".text") == 0;
 147   if (!isCode)
 148     return;
 149
 150   uint32 start_file_offset = section->file_offset_of_raw_data;
 151   uint32 end_file_offset = start_file_offset + section->size_of_raw_data;
 152   RVA relocs_start_rva = pe_info().base_relocation_table().address_;
 153
 154   const uint8* start_pointer = pe_info().FileOffsetToPointer(start_file_offset);
 155   const uint8* end_pointer = pe_info().FileOffsetToPointer(end_file_offset);
 156
 157   RVA start_rva = pe_info().FileOffsetToRVA(start_file_offset);
 158   RVA end_rva = start_rva + section->virtual_size;
 159
 160   // Quick way to convert from Pointer to RVA within a single Section is to
 161   // subtract 'pointer_to_rva'.
 162   const uint8* const adjust_pointer_to_rva = start_pointer - start_rva;
 163
 164   std::vector<RVA>::iterator abs32_pos = abs32_locations_.begin();
 165
 166   // Find the rel32 relocations.
 167   const uint8* p = start_pointer;
 168   while (p < end_pointer) {
 169     RVA current_rva = p - adjust_pointer_to_rva;
 170     if (current_rva == relocs_start_rva) {
 171       uint32 relocs_size = pe_info().base_relocation_table().size_;
 172       if (relocs_size) {
 173         p += relocs_size;
 174         continue;
 175       }
 176     }
 177
 178     //while (abs32_pos != abs32_locations_.end() && *abs32_pos < current_rva)
 179     //  ++abs32_pos;
 180
 181     // Heuristic discovery of rel32 locations in instruction stream: are the
 182     // next few bytes the start of an instruction containing a rel32
 183     // addressing mode?
 184     const uint8* rel32 = NULL;
 185
 186     if (p + 5 < end_pointer) {
 187       if (*p == 0xE8 || *p == 0xE9) {  // jmp rel32 and call rel32
 188         rel32 = p + 1;
 189       }
 190     }
 191     if (p + 6 < end_pointer) {
 192       if (*p == 0x0F  &&  (*(p+1) & 0xF0) == 0x80) {  // Jcc long form
 193         if (p[1] != 0x8A && p[1] != 0x8B)  // JPE/JPO unlikely
 194           rel32 = p + 2;
 195       }
 196     }
 197     if (rel32) {
 198       RVA rel32_rva = rel32 - adjust_pointer_to_rva;
 199
 200       // Is there an abs32 reloc overlapping the candidate?
 201       while (abs32_pos != abs32_locations_.end() && *abs32_pos < rel32_rva - 3)
 202         ++abs32_pos;
 203       // Now: (*abs32_pos > rel32_rva - 4) i.e. the lowest addressed 4-byte
 204       // region that could overlap rel32_rva.
 205       if (abs32_pos != abs32_locations_.end()) {
 206         if (*abs32_pos < rel32_rva + 4) {
 207           // Beginning of abs32 reloc is before end of rel32 reloc so they
 208           // overlap.  Skip four bytes past the abs32 reloc.
 209           p += (*abs32_pos + 4) - current_rva;
 210           continue;
 211         }
 212       }
 213
 214       RVA target_rva = rel32_rva + 4 + Read32LittleEndian(rel32);
 215       // To be valid, rel32 target must be within image, and within this
 216       // section.
 217       if (pe_info().IsValidRVA(target_rva) &&
 218           start_rva <= target_rva && target_rva < end_rva) {
 219         rel32_locations_.push_back(rel32_rva);
 220 #if COURGETTE_HISTOGRAM_TARGETS
 221         ++rel32_target_rvas_[target_rva];
 222 #endif
 223         p += 4;
 224         continue;
 225       }
 226     }
 227     p += 1;
 228   }
 229 }
 230
 231 void DisassemblerWin32X86::ParseFile(AssemblyProgram* program) {
 232   // Walk all the bytes in the file, whether or not in a section.
 233   uint32 file_offset = 0;
 234   while (file_offset < pe_info().length()) {
 235     const Section* section = pe_info().FindNextSection(file_offset);
 236     if (section == NULL) {
 237       // No more sections.  There should not be extra stuff following last
 238       // section.
 239       //   ParseNonSectionFileRegion(file_offset, pe_info().length(), program);
 240       break;
 241     }
 242     if (file_offset < section->file_offset_of_raw_data) {
 243       uint32 section_start_offset = section->file_offset_of_raw_data;
 244       ParseNonSectionFileRegion(file_offset, section_start_offset, program);
 245       file_offset = section_start_offset;
 246     }
 247     uint32 end = file_offset + section->size_of_raw_data;
 248     ParseFileRegion(section, file_offset, end, program);
 249     file_offset = end;
 250   }
 251
 252 #if COURGETTE_HISTOGRAM_TARGETS
 253   HistogramTargets("abs32 relocs", abs32_target_rvas_);
 254   HistogramTargets("rel32 relocs", rel32_target_rvas_);
 255 #endif
 256 }
 257
 258 void DisassemblerWin32X86::ParseNonSectionFileRegion(
 259     uint32 start_file_offset,
 260     uint32 end_file_offset,
 261     AssemblyProgram* program) {
 262   if (incomplete_disassembly_)
 263     return;
 264
 265   const uint8* start = pe_info().FileOffsetToPointer(start_file_offset);
 266   const uint8* end = pe_info().FileOffsetToPointer(end_file_offset);
 267
 268   const uint8* p = start;
 269
 270   while (p < end) {
 271     program->EmitByteInstruction(*p);
 272     ++p;
 273   }
 274 }
 275
 276 void DisassemblerWin32X86::ParseFileRegion(
 277     const Section* section,
 278     uint32 start_file_offset, uint32 end_file_offset,
 279     AssemblyProgram* program) {
 280   RVA relocs_start_rva = pe_info().base_relocation_table().address_;
 281
 282   const uint8* start_pointer = pe_info().FileOffsetToPointer(start_file_offset);
 283   const uint8* end_pointer = pe_info().FileOffsetToPointer(end_file_offset);
 284
 285   RVA start_rva = pe_info().FileOffsetToRVA(start_file_offset);
 286   RVA end_rva = start_rva + section->virtual_size;
 287
 288   // Quick way to convert from Pointer to RVA within a single Section is to
 289   // subtract 'pointer_to_rva'.
 290   const uint8* const adjust_pointer_to_rva = start_pointer - start_rva;
 291
 292   std::vector<RVA>::iterator rel32_pos = rel32_locations_.begin();
 293   std::vector<RVA>::iterator abs32_pos = abs32_locations_.begin();
 294
 295   program->EmitOriginInstruction(start_rva);
 296
 297   const uint8* p = start_pointer;
 298
 299   while (p < end_pointer) {
 300     RVA current_rva = p - adjust_pointer_to_rva;
 301
 302     // The base relocation table is usually in the .relocs section, but it could
 303     // actually be anywhere.  Make sure we skip it because we will regenerate it
 304     // during assembly.
 305     if (current_rva == relocs_start_rva) {
 306       program->EmitMakeRelocsInstruction();
 307       uint32 relocs_size = pe_info().base_relocation_table().size_;
 308       if (relocs_size) {
 309         p += relocs_size;
 310         continue;
 311       }
 312     }
 313
 314     while (abs32_pos != abs32_locations_.end() && *abs32_pos < current_rva)
 315       ++abs32_pos;
 316
 317     if (abs32_pos != abs32_locations_.end() && *abs32_pos == current_rva) {
 318       uint32 target_address = Read32LittleEndian(p);
 319       RVA target_rva = target_address - pe_info().image_base();
 320       // TODO(sra): target could be Label+offset.  It is not clear how to guess
 321       // which it might be.  We assume offset==0.
 322       program->EmitAbs32(program->FindOrMakeAbs32Label(target_rva));
 323       p += 4;
 324       continue;
 325     }
 326
 327     while (rel32_pos != rel32_locations_.end() && *rel32_pos < current_rva)
 328       ++rel32_pos;
 329
 330     if (rel32_pos != rel32_locations_.end() && *rel32_pos == current_rva) {
 331       RVA target_rva = current_rva + 4 + Read32LittleEndian(p);
 332       program->EmitRel32(program->FindOrMakeRel32Label(target_rva));
 333       p += 4;
 334       continue;
 335     }
 336
 337     if (incomplete_disassembly_) {
 338       if ((abs32_pos == abs32_locations_.end() || end_rva <= *abs32_pos) &&
 339           (rel32_pos == rel32_locations_.end() || end_rva <= *rel32_pos) &&
 340           (end_rva <= relocs_start_rva || current_rva >= relocs_start_rva)) {
 341         // No more relocs in this section, don't bother encoding bytes.
 342         break;
 343       }
 344     }
 345
 346     program->EmitByteInstruction(*p);
 347     p += 1;
 348   }
 349 }
 350
 351 #if COURGETTE_HISTOGRAM_TARGETS
 352 // Histogram is printed to std::cout.  It is purely for debugging the algorithm
 353 // and is only enabled manually in 'exploration' builds.  I don't want to add
 354 // command-line configuration for this feature because this code has to be
 355 // small, which means compiled-out.
 356 void DisassemblerWin32X86::HistogramTargets(const char* kind,
 357                                             const std::map<RVA, int>& map) {
 358   int total = 0;
 359   std::map<int, std::vector<RVA> > h;
 360   for (std::map<RVA, int>::const_iterator p = map.begin();
 361        p != map.end();
 362        ++p) {
 363     h[p->second].push_back(p->first);
 364     total += p->second;
 365   }
 366
 367   std::cout << total << " " << kind << " to "
 368             << map.size() << " unique targets" << std::endl;
 369
 370   std::cout << "indegree: #targets-with-indegree (example)" << std::endl;
 371   const int kFirstN = 15;
 372   bool someSkipped = false;
 373   int index = 0;
 374   for (std::map<int, std::vector<RVA> >::reverse_iterator p = h.rbegin();
 375        p != h.rend();
 376        ++p) {
 377     ++index;
 378     if (index <= kFirstN || p->first <= 3) {
 379       if (someSkipped) {
 380         std::cout << "..." << std::endl;
 381       }
 382       size_t count = p->second.size();
 383       std::cout << std::dec << p->first << ": " << count;
 384       if (count <= 2) {
 385         for (size_t i = 0;  i < count;  ++i)
 386           std::cout << "  " << pe_info().DescribeRVA(p->second[i]);
 387       }
 388       std::cout << std::endl;
 389       someSkipped = false;
 390     } else {
 391       someSkipped = true;
 392     }
 393   }
 394 }
 395 #endif  // COURGETTE_HISTOGRAM_TARGETS
 396
 397 Disassembler* Disassembler::MakeDisassemberWin32X86(PEInfo* pe_info) {
 398   return new DisassemblerWin32X86(pe_info);
 399 }
 400
 401 ////////////////////////////////////////////////////////////////////////////////
 402
 403 Status ParseWin32X86PE(const void* buffer, size_t length,
 404                        AssemblyProgram** output) {
 405   *output = NULL;
 406
 407   PEInfo* pe_info = new PEInfo();
 408   pe_info->Init(buffer, length);
 409
 410   if (!pe_info->ParseHeader()) {
 411     delete pe_info;
 412     return C_INPUT_NOT_RECOGNIZED;
 413   }
 414
 415   Disassembler* disassembler = Disassembler::MakeDisassemberWin32X86(pe_info);
 416   AssemblyProgram* program = new AssemblyProgram();
 417
 418   if (!disassembler->Disassemble(program)) {
 419     delete program;
 420     disassembler->Destroy();
 421     delete pe_info;
 422     return C_DISASSEMBLY_FAILED;
 423   }
 424
 425   disassembler->Destroy();
 426   delete pe_info;
 427   *output = program;
 428   return C_OK;
 429 }
 430
 431 void DeleteAssemblyProgram(AssemblyProgram* program) {
 432   delete program;
 433 }
 434
 435 }  // namespace courgette