courgette/description.md

   1 Courgette Internals
   2 ===================
   3
   4 Patch Generation
   5 ----------------
   6
   7 ![Patch Generation](generation.png)
   8
   9 - courgette\_tool.cc:GenerateEnsemblePatch kicks off the patch
  10   generation by calling ensemble\_create.cc:GenerateEnsemblePatch
  11
  12 - The files are read in by in courgette:SourceStream objects
  13
  14 - ensemble\_create.cc:GenerateEnsemblePatch uses FindGenerators, which
  15   uses MakeGenerator to create
  16   patch\_generator\_x86\_32.h:PatchGeneratorX86\_32 classes.
  17
  18 - PatchGeneratorX86\_32's Transform method transforms the input file
  19   using Courgette's core techniques that make the bsdiff delta
  20   smaller.  The steps it takes are the following:
  21
  22   - _disassemble_ the old and new binaries into AssemblyProgram
  23     objects,
  24
  25   - _adjust_ the new AssemblyProgram object, and
  26
  27   - _encode_ the AssemblyProgram object back into raw bytes.
  28
  29 ### Disassemble
  30
  31 - The input is a pointer to a buffer containing the raw bytes of the
  32   input file.
  33
  34 - Disassembly converts certain machine instructions that reference
  35   addresses to Courgette instructions.  It is not actually
  36   disassembly, but this is the term the code-base uses.  Specifically,
  37   it detects instructions that use absolute addresses given by the
  38   binary file's relocation table, and relative addresses used in
  39   relative branches.
  40
  41 - Done by disassemble:ParseDetectedExecutable, which selects the
  42   appropriate Disassembler subclass by looking at the binary file's
  43   headers.
  44
  45   - disassembler\_win32\_x86.h defines the PE/COFF x86 disassembler
  46
  47   - disassembler\_elf\_32\_x86.h defines the ELF 32-bit x86 disassembler
  48
  49 - The Disassembler replaces the relocation table with a Courgette
  50   instruction that can regenerate the relocation table.
  51
  52 - The Disassembler builds a list of addresses referenced by the
  53   machine code, numbering each one.
  54
  55 - The Disassembler replaces and address used in machine instructions
  56   with its index number.
  57
  58 - The output is an assembly\_program.h:AssemblyProgram class, which
  59   contains a list of instructions, machine or Courgette, and a mapping
  60   of indices to actual addresses.
  61
  62 ### Adjust
  63
  64 - This step takes the AssemblyProgram for the old file and reassigns
  65   the indices that map to actual addresses.  It is performed by
  66   adjustment_method.cc:Adjust().
  67
  68 - The goal is the match the indices from the old program to the new
  69   program as closely as possible.
  70
  71 - When matched correctly, machine instructions that jump to the
  72   function in both the new and old binary will look the same to
  73   bsdiff, even the function is located in a different part of the
  74   binary.
  75
  76 ### Encode
  77
  78 - This step takes an AssemblyProgram object and encodes both the
  79   instructions and the mapping of indices to addresses as byte
  80   vectors.  This format can be written to a file directly, and is also
  81   more appropriate for bsdiffing.  It is done by
  82   AssemblyProgram.Encode().
  83
  84 - encoded_program.h:EncodedProgram defines the binary format and a
  85   WriteTo method that writes to a file.
  86
  87 ### bsdiff
  88
  89 - simple_delta.c:GenerateSimpleDelta
  90
  91 Patch Application
  92 -----------------
  93
  94 ![Patch Application](application.png)
  95
  96 - courgette\_tool.cc:ApplyEnsemblePatch kicks off the patch generation
  97   by calling ensemble\_apply.cc:ApplyEnsemblePatch
  98
  99 - ensemble\_create.cc:ApplyEnsemblePatch, reads and verifies the
 100   patch's header, then calls the overloaded version of
 101   ensemble\_create.cc:ApplyEnsemblePatch.
 102
 103 - The patch is read into an ensemble_apply.cc:EnsemblePatchApplication
 104   object, which generates a set of patcher_x86_32.h:PatcherX86_32
 105   objects for the sections in the patch.
 106
 107 - The original file is disassembled and encoded via a call
 108   EnsemblePatchApplication.TransformUp, which in turn call
 109   patcher_x86_32.h:PatcherX86_32.Transform.
 110
 111 - The transformed file is then bspatched via
 112   EnsemblePatchApplication.SubpatchTransformedElements, which calls
 113   EnsemblePatchApplication.SubpatchStreamSets, which calls
 114   simple_delta.cc:ApplySimpleDelta, Courgette's built-in
 115   implementation of bspatch.
 116
 117 - Finally, EnsemblePatchApplication.TransformDown assembles, i.e.,
 118   reverses the encoding and disassembly, on the patched binary data.
 119   This is done by calling PatcherX86_32.Reform, which in turn calls
 120   the global function encoded_program.cc:Assemble, which calls
 121   EncodedProgram.AssembleTo.
 122
 123
 124 Glossary
 125 --------
 126
 127 **Adjust**: Reassign address indices in the new program to match more
 128   closely those from the old.
 129
 130 **Assembly program**: The output of _disassembly_.  Contains a list of
 131   _Courgette instructions_ and an index of branch target addresses.
 132
 133 **Assemble**: Convert an _assembly program_ back into an object file
 134   by evaluating the _Courgette instructions_ and leaving the machine
 135   instructions in place.
 136
 137 **Courgette instruction**: Replaces machine instructions in the
 138   program.  Courgette instructions replace branches with an index to
 139   the target addresses and replace part of the relocation table.
 140
 141 **Disassembler**: Takes a binary file and produces an _assembly
 142   program_.
 143
 144 **Encode**: Convert an _assembly program_ into an _encoded program_ by
 145   serializing its data structures into byte vectors more appropriate
 146   for storage in a file.
 147
 148 **Encoded Program**: The output of encoding.
 149
 150 **Ensemble**: A Courgette-style patch containing sections for the list
 151   of branch addresses, the encoded program.  It supports patching
 152   multiple object files at once.
 153
 154 **Opcode**: The number corresponding to either a machine or _Courgette
 155   instruction_.