blob: bfdf6efe0877fb63e21745471ea4069d59d6d885 [file] [log] [blame]
// Copyright (c) 2011 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "courgette/assembly_program.h"
#include <memory.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <vector>
#include "base/logging.h"
#include "base/memory/scoped_ptr.h"
#include "courgette/courgette.h"
#include "courgette/encoded_program.h"
namespace courgette {
// Opcodes of simple assembly language
enum OP {
ORIGIN, // ORIGIN <rva> - set current address for assembly.
MAKEPERELOCS, // Generates a base relocation table.
MAKEELFRELOCS, // Generates a base relocation table.
DEFBYTE, // DEFBYTE <value> - emit a byte literal.
REL32, // REL32 <label> - emit a rel32 encoded reference to 'label'.
ABS32, // REL32 <label> - emit am abs32 encoded reference to 'label'.
REL32ARM, // REL32ARM <c_op> <label> - arm-specific rel32 reference
MAKEELFARMRELOCS, // Generates a base relocation table.
DEFBYTES, // Emits any number of byte literals
LAST_OP
};
// Base class for instructions. Because we have so many instructions we want to
// keep them as small as possible. For this reason we avoid virtual functions.
//
class Instruction {
public:
OP op() const { return static_cast<OP>(op_); }
protected:
explicit Instruction(OP op) : op_(op), info_(0) {}
Instruction(OP op, unsigned int info) : op_(op), info_(info) {}
uint32 op_ : 4; // A few bits to store the OP code.
uint32 info_ : 28; // Remaining bits in first word available to subclass.
private:
DISALLOW_COPY_AND_ASSIGN(Instruction);
};
namespace {
// Sets the current address for the emitting instructions.
class OriginInstruction : public Instruction {
public:
explicit OriginInstruction(RVA rva) : Instruction(ORIGIN, 0), rva_(rva) {}
RVA origin_rva() const { return rva_; }
private:
RVA rva_;
};
// Emits an entire PE base relocation table.
class PeRelocsInstruction : public Instruction {
public:
PeRelocsInstruction() : Instruction(MAKEPERELOCS) {}
};
// Emits an ELF relocation table.
class ElfRelocsInstruction : public Instruction {
public:
ElfRelocsInstruction() : Instruction(MAKEELFRELOCS) {}
};
// Emits an ELF ARM relocation table.
class ElfARMRelocsInstruction : public Instruction {
public:
ElfARMRelocsInstruction() : Instruction(MAKEELFARMRELOCS) {}
};
// Emits a single byte.
class ByteInstruction : public Instruction {
public:
explicit ByteInstruction(uint8 value) : Instruction(DEFBYTE, value) {}
uint8 byte_value() const { return info_; }
};
// Emits a single byte.
class BytesInstruction : public Instruction {
public:
BytesInstruction(const uint8* values, uint32 len)
: Instruction(DEFBYTES, 0),
values_(values),
len_(len) {}
const uint8* byte_values() const { return values_; }
uint32 len() const { return len_; }
private:
const uint8* values_;
uint32 len_;
};
// A ABS32 to REL32 instruction emits a reference to a label's address.
class InstructionWithLabel : public Instruction {
public:
InstructionWithLabel(OP op, Label* label)
: Instruction(op, 0), label_(label) {
if (label == NULL) NOTREACHED();
}
Label* label() const { return label_; }
protected:
Label* label_;
};
// An ARM REL32 instruction emits a reference to a label's address and
// a specially-compressed ARM op.
class InstructionWithLabelARM : public InstructionWithLabel {
public:
InstructionWithLabelARM(OP op, uint16 compressed_op, Label* label,
const uint8* arm_op, uint16 op_size)
: InstructionWithLabel(op, label), compressed_op_(compressed_op),
arm_op_(arm_op), op_size_(op_size) {
if (label == NULL) NOTREACHED();
}
uint16 compressed_op() const { return compressed_op_; }
const uint8* arm_op() const { return arm_op_; }
uint16 op_size() const { return op_size_; }
private:
uint16 compressed_op_;
const uint8* arm_op_;
uint16 op_size_;
};
} // namespace
AssemblyProgram::AssemblyProgram(ExecutableType kind)
: kind_(kind), image_base_(0) {
}
static void DeleteContainedLabels(const RVAToLabel& labels) {
for (RVAToLabel::const_iterator p = labels.begin(); p != labels.end(); ++p)
delete p->second;
}
AssemblyProgram::~AssemblyProgram() {
for (size_t i = 0; i < instructions_.size(); ++i) {
Instruction* instruction = instructions_[i];
if (instruction->op() != DEFBYTE) // Will be in byte_instruction_cache_.
delete instruction;
}
if (byte_instruction_cache_.get()) {
for (size_t i = 0; i < 256; ++i)
delete byte_instruction_cache_[i];
}
DeleteContainedLabels(rel32_labels_);
DeleteContainedLabels(abs32_labels_);
}
CheckBool AssemblyProgram::EmitPeRelocsInstruction() {
return Emit(new(std::nothrow) PeRelocsInstruction());
}
CheckBool AssemblyProgram::EmitElfRelocationInstruction() {
return Emit(new(std::nothrow) ElfRelocsInstruction());
}
CheckBool AssemblyProgram::EmitElfARMRelocationInstruction() {
return Emit(new(std::nothrow) ElfARMRelocsInstruction());
}
CheckBool AssemblyProgram::EmitOriginInstruction(RVA rva) {
return Emit(new(std::nothrow) OriginInstruction(rva));
}
CheckBool AssemblyProgram::EmitByteInstruction(uint8 byte) {
return Emit(GetByteInstruction(byte));
}
CheckBool AssemblyProgram::EmitBytesInstruction(const uint8* values,
uint32 len) {
return Emit(new(std::nothrow) BytesInstruction(values, len));
}
CheckBool AssemblyProgram::EmitRel32(Label* label) {
return Emit(new(std::nothrow) InstructionWithLabel(REL32, label));
}
CheckBool AssemblyProgram::EmitRel32ARM(uint16 op, Label* label,
const uint8* arm_op, uint16 op_size) {
return Emit(new(std::nothrow) InstructionWithLabelARM(REL32ARM, op, label,
arm_op, op_size));
}
CheckBool AssemblyProgram::EmitAbs32(Label* label) {
return Emit(new(std::nothrow) InstructionWithLabel(ABS32, label));
}
Label* AssemblyProgram::FindOrMakeAbs32Label(RVA rva) {
return FindLabel(rva, &abs32_labels_);
}
Label* AssemblyProgram::FindOrMakeRel32Label(RVA rva) {
return FindLabel(rva, &rel32_labels_);
}
void AssemblyProgram::DefaultAssignIndexes() {
DefaultAssignIndexes(&abs32_labels_);
DefaultAssignIndexes(&rel32_labels_);
}
void AssemblyProgram::UnassignIndexes() {
UnassignIndexes(&abs32_labels_);
UnassignIndexes(&rel32_labels_);
}
void AssemblyProgram::AssignRemainingIndexes() {
AssignRemainingIndexes(&abs32_labels_);
AssignRemainingIndexes(&rel32_labels_);
}
Label* AssemblyProgram::InstructionAbs32Label(
const Instruction* instruction) const {
if (instruction->op() == ABS32)
return static_cast<const InstructionWithLabel*>(instruction)->label();
return NULL;
}
Label* AssemblyProgram::InstructionRel32Label(
const Instruction* instruction) const {
if (instruction->op() == REL32 || instruction->op() == REL32ARM) {
Label* label =
static_cast<const InstructionWithLabel*>(instruction)->label();
return label;
}
return NULL;
}
CheckBool AssemblyProgram::Emit(Instruction* instruction) {
if (!instruction)
return false;
bool ok = instructions_.push_back(instruction);
if (!ok)
delete instruction;
return ok;
}
Label* AssemblyProgram::FindLabel(RVA rva, RVAToLabel* labels) {
Label*& slot = (*labels)[rva];
if (slot == NULL) {
slot = new(std::nothrow) Label(rva);
}
slot->count_++;
return slot;
}
void AssemblyProgram::UnassignIndexes(RVAToLabel* labels) {
for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
Label* current = p->second;
current->index_ = Label::kNoIndex;
}
}
// DefaultAssignIndexes takes a set of labels and assigns indexes in increasing
// address order.
//
void AssemblyProgram::DefaultAssignIndexes(RVAToLabel* labels) {
int index = 0;
for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
Label* current = p->second;
if (current->index_ != Label::kNoIndex)
NOTREACHED();
current->index_ = index;
++index;
}
}
// AssignRemainingIndexes assigns indexes to any addresses (labels) that are not
// yet assigned an index.
//
void AssemblyProgram::AssignRemainingIndexes(RVAToLabel* labels) {
// An address table compresses best when each index is associated with an
// address that is slight larger than the previous index.
// First see which indexes have not been used. The 'available' vector could
// grow even bigger, but the number of addresses is a better starting size
// than empty.
std::vector<bool> available(labels->size(), true);
int used = 0;
for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
int index = p->second->index_;
if (index != Label::kNoIndex) {
while (static_cast<size_t>(index) >= available.size())
available.push_back(true);
available.at(index) = false;
++used;
}
}
VLOG(1) << used << " of " << labels->size() << " labels pre-assigned";
// Are there any unused labels that happen to be adjacent following a used
// label?
//
int fill_forward_count = 0;
Label* prev = 0;
for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
Label* current = p->second;
if (current->index_ == Label::kNoIndex) {
int index = 0;
if (prev && prev->index_ != Label::kNoIndex)
index = prev->index_ + 1;
if (index < static_cast<int>(available.size()) && available.at(index)) {
current->index_ = index;
available.at(index) = false;
++fill_forward_count;
}
}
prev = current;
}
// Are there any unused labels that happen to be adjacent preceeding a used
// label?
//
int fill_backward_count = 0;
prev = 0;
for (RVAToLabel::reverse_iterator p = labels->rbegin();
p != labels->rend();
++p) {
Label* current = p->second;
if (current->index_ == Label::kNoIndex) {
int prev_index;
if (prev)
prev_index = prev->index_;
else
prev_index = static_cast<uint32>(available.size());
if (prev_index != 0 &&
prev_index != Label::kNoIndex &&
available.at(prev_index - 1)) {
current->index_ = prev_index - 1;
available.at(current->index_) = false;
++fill_backward_count;
}
}
prev = current;
}
// Fill in any remaining indexes
int fill_infill_count = 0;
int index = 0;
for (RVAToLabel::iterator p = labels->begin(); p != labels->end(); ++p) {
Label* current = p->second;
if (current->index_ == Label::kNoIndex) {
while (!available.at(index)) {
++index;
}
current->index_ = index;
available.at(index) = false;
++index;
++fill_infill_count;
}
}
VLOG(1) << " fill forward " << fill_forward_count
<< " backward " << fill_backward_count
<< " infill " << fill_infill_count;
}
typedef CheckBool (EncodedProgram::*DefineLabelMethod)(int index, RVA value);
#if defined(OS_WIN)
__declspec(noinline)
#endif
static CheckBool DefineLabels(const RVAToLabel& labels,
EncodedProgram* encoded_format,
DefineLabelMethod define_label) {
bool ok = true;
for (RVAToLabel::const_iterator p = labels.begin();
ok && p != labels.end();
++p) {
Label* label = p->second;
ok = (encoded_format->*define_label)(label->index_, label->rva_);
}
return ok;
}
EncodedProgram* AssemblyProgram::Encode() const {
scoped_ptr<EncodedProgram> encoded(new(std::nothrow) EncodedProgram());
if (!encoded.get())
return NULL;
encoded->set_image_base(image_base_);
if (!DefineLabels(abs32_labels_, encoded.get(),
&EncodedProgram::DefineAbs32Label) ||
!DefineLabels(rel32_labels_, encoded.get(),
&EncodedProgram::DefineRel32Label)) {
return NULL;
}
encoded->EndLabels();
for (size_t i = 0; i < instructions_.size(); ++i) {
Instruction* instruction = instructions_[i];
switch (instruction->op()) {
case ORIGIN: {
OriginInstruction* org = static_cast<OriginInstruction*>(instruction);
if (!encoded->AddOrigin(org->origin_rva()))
return NULL;
break;
}
case DEFBYTE: {
uint8 b = static_cast<ByteInstruction*>(instruction)->byte_value();
if (!encoded->AddCopy(1, &b))
return NULL;
break;
}
case DEFBYTES: {
const uint8* byte_values =
static_cast<BytesInstruction*>(instruction)->byte_values();
uint32 len = static_cast<BytesInstruction*>(instruction)->len();
if (!encoded->AddCopy(len, byte_values))
return NULL;
break;
}
case REL32: {
Label* label = static_cast<InstructionWithLabel*>(instruction)->label();
if (!encoded->AddRel32(label->index_))
return NULL;
break;
}
case REL32ARM: {
Label* label =
static_cast<InstructionWithLabelARM*>(instruction)->label();
uint16 compressed_op =
static_cast<InstructionWithLabelARM*>(instruction)->
compressed_op();
if (!encoded->AddRel32ARM(compressed_op, label->index_))
return NULL;
break;
}
case ABS32: {
Label* label = static_cast<InstructionWithLabel*>(instruction)->label();
if (!encoded->AddAbs32(label->index_))
return NULL;
break;
}
case MAKEPERELOCS: {
if (!encoded->AddPeMakeRelocs(kind_))
return NULL;
break;
}
case MAKEELFRELOCS: {
if (!encoded->AddElfMakeRelocs())
return NULL;
break;
}
case MAKEELFARMRELOCS: {
if (!encoded->AddElfARMMakeRelocs())
return NULL;
break;
}
default: {
NOTREACHED() << "Unknown Insn OP kind";
}
}
}
return encoded.release();
}
Instruction* AssemblyProgram::GetByteInstruction(uint8 byte) {
if (!byte_instruction_cache_.get()) {
byte_instruction_cache_.reset(new(std::nothrow) Instruction*[256]);
if (!byte_instruction_cache_.get())
return NULL;
for (int i = 0; i < 256; ++i) {
byte_instruction_cache_[i] =
new(std::nothrow) ByteInstruction(static_cast<uint8>(i));
if (!byte_instruction_cache_[i]) {
for (int j = 0; j < i; ++j)
delete byte_instruction_cache_[j];
byte_instruction_cache_.reset();
return NULL;
}
}
}
return byte_instruction_cache_[byte];
}
// Chosen empirically to give the best reduction in payload size for
// an update from daisy_3701.98.0 to daisy_4206.0.0.
const int AssemblyProgram::kLabelLowerLimit = 5;
CheckBool AssemblyProgram::TrimLabels() {
// For now only trim for ARM binaries
if (kind() != EXE_ELF_32_ARM)
return true;
int lower_limit = kLabelLowerLimit;
VLOG(1) << "TrimLabels: threshold " << lower_limit;
// Remove underused labels from the list of labels
RVAToLabel::iterator it = rel32_labels_.begin();
while (it != rel32_labels_.end()) {
if (it->second->count_ <= lower_limit) {
rel32_labels_.erase(it++);
} else {
++it;
}
}
// Walk through the list of instructions, replacing trimmed labels
// with the original machine instruction
for (size_t i = 0; i < instructions_.size(); ++i) {
Instruction* instruction = instructions_[i];
switch (instruction->op()) {
case REL32ARM: {
Label* label =
static_cast<InstructionWithLabelARM*>(instruction)->label();
if (label->count_ <= lower_limit) {
const uint8* arm_op =
static_cast<InstructionWithLabelARM*>(instruction)->arm_op();
uint16 op_size =
static_cast<InstructionWithLabelARM*>(instruction)->op_size();
if (op_size < 1)
return false;
BytesInstruction* new_instruction =
new(std::nothrow) BytesInstruction(arm_op, op_size);
instructions_[i] = new_instruction;
}
break;
}
default:
break;
}
}
return true;
}
void AssemblyProgram::PrintLabelCounts(RVAToLabel* labels) {
for (RVAToLabel::const_iterator p = labels->begin(); p != labels->end();
++p) {
Label* current = p->second;
if (current->index_ != Label::kNoIndex)
printf("%d\n", current->count_);
}
}
void AssemblyProgram::CountRel32ARM() {
PrintLabelCounts(&rel32_labels_);
}
////////////////////////////////////////////////////////////////////////////////
Status TrimLabels(AssemblyProgram* program) {
if (program->TrimLabels())
return C_OK;
else
return C_TRIM_FAILED;
}
Status Encode(AssemblyProgram* program, EncodedProgram** output) {
*output = NULL;
EncodedProgram *encoded = program->Encode();
if (encoded) {
*output = encoded;
return C_OK;
} else {
return C_GENERAL_ERROR;
}
}
} // namespace courgette