ARM binaries seen by Courgette have three ISAs, ARM, thumb, and thumb-2. Courgette currently identified branch instructions from these ISAs heuristically, which leads to false positives. This patch improves on the heuristic by ignoring branches to addresses that aren't used very much in the binary.

Currently, the lower threshold for the number of times an address is used is 5, which was found empirically.  ARM versions of chrome OS from daisy_3701.98.0 to daisy_4206.0.0 double the bytes saved by Courgette.

BUG=266019

Review URL: https://chromiumcodereview.appspot.com/21428006

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@215737 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 123 insertions, 0 deletions

diff --git a/courgette/assembly_program.cc b/courgette/assembly_program.cc
index 64830c2..f577b98 100644
--- a/courgette/assembly_program.cc
+++ b/courgette/assembly_program.cc
@@ -29,6 +29,7 @@ enum OP {
   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
 };
 
@@ -86,6 +87,21 @@ class ByteInstruction : public Instruction {
   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:
@@ -162,6 +178,11 @@ 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));
 }
@@ -397,6 +418,14 @@ EncodedProgram* AssemblyProgram::Encode() const {
           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_))
@@ -464,6 +493,59 @@ Instruction* AssemblyProgram::GetByteInstruction(uint8 byte) {
   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) {
@@ -479,6 +561,13 @@ void AssemblyProgram::CountRel32ARM() {
 
 ////////////////////////////////////////////////////////////////////////////////
 
+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();
diff --git a/courgette/assembly_program.h b/courgette/assembly_program.h
index af4ecfb..701b476 100644
--- a/courgette/assembly_program.h
+++ b/courgette/assembly_program.h
@@ -86,6 +86,10 @@ class AssemblyProgram {
   // Generates a single byte of data or machine instruction.
   CheckBool EmitByteInstruction(uint8 byte) WARN_UNUSED_RESULT;
 
+  // Generates multiple bytes of data or machine instructions.
+  CheckBool EmitBytesInstruction(const uint8* value, uint32 len)
+      WARN_UNUSED_RESULT;
+
   // Generates 4-byte relative reference to address of 'label'.
   CheckBool EmitRel32(Label* label) WARN_UNUSED_RESULT;
 
@@ -122,6 +126,9 @@ class AssemblyProgram {
   // otherwise returns NULL.
   Label* InstructionRel32Label(const Instruction* instruction) const;
 
+  // Trim underused labels
+  CheckBool TrimLabels();
+
   void PrintLabelCounts(RVAToLabel* labels);
   void CountRel32ARM();
 
@@ -130,6 +137,8 @@ class AssemblyProgram {
 
   CheckBool Emit(Instruction* instruction) WARN_UNUSED_RESULT;
 
+  static const int kLabelLowerLimit;
+
   // Looks up a label or creates a new one.  Might return NULL.
   Label* FindLabel(RVA rva, RVAToLabel* labels);
 
diff --git a/courgette/courgette.h b/courgette/courgette.h
index 4831228..542c43f 100644
--- a/courgette/courgette.h
+++ b/courgette/courgette.h
@@ -48,6 +48,7 @@ enum Status {
   C_DISASSEMBLY_FAILED = 25,      //
   C_ASSEMBLY_FAILED = 26,         //
   C_ADJUSTMENT_FAILED = 27,       //
+  C_TRIM_FAILED = 28,             // TrimLabels failed
 };
 
 // What type of executable is something
@@ -107,6 +108,10 @@ Status DetectExecutableType(const void* buffer, size_t length,
 Status ParseDetectedExecutable(const void* buffer, size_t length,
                                AssemblyProgram** output);
 
+// Trims labels used fewer than a given number of times from an
+// assembly program in-place.
+Status TrimLabels(AssemblyProgram* program);
+
 // Converts |program| into encoded form, returning it as |*output|.
 // Returns C_OK if succeeded, otherwise returns an error status and
 // sets |*output| to NULL
diff --git a/courgette/patch_generator_x86_32.h b/courgette/patch_generator_x86_32.h
index f68185e..084bdc3 100644
--- a/courgette/patch_generator_x86_32.h
+++ b/courgette/patch_generator_x86_32.h
@@ -81,6 +81,19 @@ class PatchGeneratorX86_32 : public TransformationPatchGenerator {
       return new_parse_status;
     }
 
+    // Trim labels below a certain threshold
+    Status trim_old_status = TrimLabels(old_program);
+    if (trim_old_status != C_OK) {
+      DeleteAssemblyProgram(old_program);
+      return trim_old_status;
+    }
+
+    Status trim_new_status = TrimLabels(new_program);
+    if (trim_new_status != C_OK) {
+      DeleteAssemblyProgram(new_program);
+      return trim_new_status;
+    }
+
     EncodedProgram* old_encoded = NULL;
     Status old_encode_status = Encode(old_program, &old_encoded);
     if (old_encode_status != C_OK) {
diff --git a/courgette/patcher_x86_32.h b/courgette/patcher_x86_32.h
index cf8ac00..9488270 100644
--- a/courgette/patcher_x86_32.h
+++ b/courgette/patcher_x86_32.h
@@ -54,6 +54,13 @@ class PatcherX86_32 : public TransformationPatcher {
     if (status != C_OK)
       return status;
 
+    // Trim labels below a certain threshold
+    Status trim_status = TrimLabels(program);
+    if (trim_status != C_OK) {
+      DeleteAssemblyProgram(program);
+      return trim_status;
+    }
+
     EncodedProgram* encoded = NULL;
     status = Encode(program, &encoded);
     DeleteAssemblyProgram(program);