src/native_client/src/trusted/validator/x86/ncval_seg_sfi/ncdecode.h

   1 /*
   2  * Copyright (c) 2012 The Native Client Authors. All rights reserved.
   3  * Use of this source code is governed by a BSD-style license that can be
   4  * found in the LICENSE file.
   5  */
   6
   7 /*
   8  * ncdecode.h - table driven decoder for Native Client.
   9  *
  10  * This header file contains type declarations and constants
  11  * used by the decoder input table
  12  */
  13 #ifndef NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_X86_NCVAL_SEG_SFI_NCDECODE_H_
  14 #define NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_X86_NCVAL_SEG_SFI_NCDECODE_H_
  15
  16 #include "native_client/src/shared/utils/types.h"
  17 #include "native_client/src/trusted/validator/ncvalidate.h"
  18 #include "native_client/src/trusted/validator/x86/error_reporter.h"
  19 #include "native_client/src/trusted/validator/x86/ncinstbuffer.h"
  20 #include "native_client/src/trusted/validator/x86/x86_insts.h"
  21
  22 EXTERN_C_BEGIN
  23
  24 struct NCDecoderInst;
  25 struct NCDecoderState;
  26
  27 /* Function type for a decoder action. Returns TRUE if action
  28  * was applied successfully.
  29  */
  30 typedef Bool (*NCDecoderStateAction)(const struct NCDecoderInst* dinst);
  31
  32 /* Function type for other decoder state methods. */
  33 typedef void (*NCDecoderStateMethod)(struct NCDecoderState* vstate);
  34
  35 typedef enum {
  36   NOGROUP = 0,
  37   GROUP1,
  38   GROUP2,
  39   GROUP3,
  40   GROUP4,
  41   /* these comments facilitate counting */
  42   GROUP5,
  43   GROUP6,
  44   GROUP7,
  45   GROUP8,
  46   GROUP9,
  47   /* these comments facilitate counting */
  48   GROUP10,
  49   GROUP11,
  50   GROUP12,
  51   GROUP13,
  52   GROUP14,
  53   /* these comments facilitate counting */
  54   GROUP15,
  55   GROUP16,
  56   GROUP17,
  57   GROUP1A,
  58   GROUPP
  59 } NaClMRMGroups;
  60 /* kModRMOpcodeGroups doesn't work as a const int since it is used */
  61 /* as an array dimension */
  62 #define kNaClMRMGroupsRange 20
  63
  64 /* Define the maximum value that can be encoded in the modrm mod field. */
  65 #define kModRMOpcodeGroupSize 8
  66
  67 /* Define the maximum register value that can be encoded into the opcode
  68  * byte.
  69  */
  70 #define kMaxRegisterIndexInOpcode 7
  71
  72 /* information derived from the opcode, wherever it happens to be */
  73 typedef enum {
  74   IMM_UNKNOWN = 0,
  75   IMM_NONE = 1,
  76   IMM_FIXED1 = 2,
  77   IMM_FIXED2 = 3,
  78   IMM_FIXED3 = 4,
  79   IMM_FIXED4 = 5,
  80   IMM_DATAV = 6,
  81   IMM_ADDRV = 7,
  82   IMM_GROUP3_F6 = 8,
  83   IMM_GROUP3_F7 = 9,
  84   IMM_FARPTR = 10,
  85   IMM_MOV_DATAV,     /* Special case for 64-bits MOVs (b8 through bf). */
  86   /* Don't add to this enum without update kNCDecodeImmediateTypeRange */
  87   /* and updating the tables below which are sized using this constant */
  88 } NCDecodeImmediateType;
  89 #define kNCDecodeImmediateTypeRange 12
  90
  91 /* 255 will force an error */
  92 static const uint8_t kImmTypeToSize66[kNCDecodeImmediateTypeRange] =
  93   { 0, 0, 1, 2, 3, 4, 2, (NACL_TARGET_SUBARCH == 64 ? 8 : 4), 0, 0, 6, 2};
  94 static const uint8_t kImmTypeToSize67[kNCDecodeImmediateTypeRange] =
  95   { 0, 0, 1, 2, 3, 4, 4, 2, 0, 0, 4, 4};
  96 static const uint8_t kImmTypeToSize[kNCDecodeImmediateTypeRange] =
  97   { 0, 0, 1, 2, 3, 4, 4, (NACL_TARGET_SUBARCH == 64 ? 8 : 4), 0, 0, 6, 4 };
  98
  99 /* Defines how to decode operands for byte codes. */
 100 typedef enum {
 101   /* Assume the default size of the operands is 64-bits (if
 102    * not specified in prefix bits).
 103    */
 104   DECODE_OPS_DEFAULT_64,
 105   /* Assume the default size of the operands is 32-bits (if
 106    * not specified in prefix bits).
 107    */
 108   DECODE_OPS_DEFAULT_32,
 109   /* Force the size of the operands to 64 bits (prefix bits are
 110    * ignored).
 111    */
 112   DECODE_OPS_FORCE_64
 113 } DecodeOpsKind;
 114
 115 /* Models information on an x86-32 bit instruction. */
 116 struct OpInfo {
 117   NaClInstType insttype;
 118   uint8_t hasmrmbyte;   /* 1 if this inst has an mrm byte, else 0 */
 119   uint8_t immtype;      /* IMM_NONE, IMM_FIXED1, etc. */
 120   uint8_t opinmrm;      /* set to 1..8 if you must find opcode in MRM byte */
 121 };
 122
 123 /* Models a node in a trie of NOP instructions. */
 124 typedef struct NCNopTrieNode {
 125   /* The matching byte for the trie node. */
 126   uint8_t matching_byte;
 127   /* The matching modeled nop, if byte matched. */
 128   struct OpInfo *matching_opinfo;
 129   /* Node to match remaining bytes. */
 130   struct NCNopTrieNode* success;
 131   /* Node to match remaining bytes. */
 132   struct NCNopTrieNode* fail;
 133 } NCNopTrieNode;
 134
 135 /* Predefined value to communicate that the lock prefix was not
 136  * found in an instruction.
 137  */
 138 static const uint8_t kNoLockPrefixIndex = 0xFF;
 139
 140 /* Models a parsed x86-32 bit instruction. */
 141 struct InstInfo {
 142   /* The bytes used to parse the x86-32 instruction (may have added
 143    * zero filler if the instruction straddles the memory segment).
 144    */
 145   NCInstBytes bytes;
 146   /* The number of prefix bytes in the instruction. */
 147   uint8_t prefixbytes;  /* 0..4 */
 148   /* Number of opcode bytes in the instruction. */
 149   uint8_t num_opbytes;
 150   /* non-zero if the instruction contains an SIB byte. */
 151   uint8_t hassibbyte;
 152   /* The ModRm byte. */
 153   uint8_t mrm;
 154   /* A NCDecodeImmediateType describing the type of immediate value(s)
 155    * the instruction has.
 156    */
 157   uint8_t immtype;
 158   /* The number of bytes that define the immediate value(s). */
 159   uint8_t immbytes;
 160   /* The number of displacement bytes defined by the instruction. */
 161   uint8_t dispbytes;
 162   /* The set of prefix masks defined by the prefix bytes. */
 163   uint32_t prefixmask;
 164   /* The prefix form used to select multibyte instructions, or 0 if
 165    * not used. That is, if 66, f2, or f3 is used to select the instruction,
 166    * then this value is non-zero. For example SSE3 instructions.
 167    */
 168   uint32_t opcode_prefixmask;
 169   /* True if it has a rex prefix. */
 170   uint8_t rexprefix;
 171   /* Index of lock prefix (F0), or kNoLockPrefixIndex if the lock prefix
 172    * isn't specified.
 173    */
 174   uint8_t lock_prefix_index;
 175 };
 176
 177 /* Models data collected about the parsed instruction. */
 178 typedef struct NCDecoderInst {
 179   /* The address of the instruction, relative to the begining of the code
 180    * segment.
 181    */
 182   NaClPcAddress inst_addr;
 183   /* The instruction rule used to decode the instruction. */
 184   const struct OpInfo* opinfo;
 185   /* The low level details of the instructionm, extracted during parsing. */
 186   struct InstInfo inst;
 187   /* Pointer to bytes of the parsed instruction (int inst) for easier access. */
 188   const NCInstBytesPtr inst_bytes;
 189   /* The decoder state the instruction appears in. */
 190   struct NCDecoderState* dstate;
 191   /* Corresopnding index of this instruction wrt to inst_buffer in
 192    * in the corresponding decoder state NCDecoderState.
 193    */
 194   size_t inst_index;
 195   /* The number of instructions parsed so far (including this instrruction).
 196    * Used to detect when one tries to get a previous instruction that doesn't
 197    * exist.
 198    */
 199   size_t inst_count;
 200   /* True if the instruction is unchanged while dynamically replacing code.
 201    * False if the instruction has changed or if code replacement is not being
 202    * performed (i.e. normal validation.)
 203    */
 204   Bool unchanged;
 205 } NCDecoderInst;
 206
 207 /* Given a (decoded) instruction, return the instruction that appeared
 208  * n elements before it, or NULL if no such instruction exists.
 209  *
 210  * Parameters:
 211  *    dinst - The instruction to look up relative to.
 212  *    n - number of elements back to look.
 213  */
 214 extern NCDecoderInst *PreviousInst(const NCDecoderInst* dinst, int n);
 215
 216 /* Models decoding instructions in a memory region.
 217  *
 218  * Note: This struct is modeling a notion of a (virtual) base class to parse
 219  * a window of k instructions. In this model, we consider NCDecoderState a
 220  * class that can be (singly) inherited by derived classes. This code
 221  * assumes that the "this" pointer can be cast to a derived class
 222  * using a C cast. This implies that derived classes should have the
 223  * field NCDecoderState as its first field.
 224  *
 225  * Typical use is:
 226  *
 227  *    NCDecoderState dstate;
 228  *    NCDecoder inst_buffer[BUF_SIZE]; // window of BUF_SIZE instructions.
 229  *    NCDecoderStateConstruct(&dstate, mbase, vbase, size,
 230  *                            inst_buffer, BUF_SIZE);
 231  *    NCDecoderStateDecode(&dstate);
 232  *    NCDecoderStateDestruct(&dstate);
 233  *
 234  * Note: The old API for this class is further down in this file,
 235  * and should be considered deprecated.
 236  */
 237 typedef struct NCDecoderState {
 238   /* PROTECTED: */
 239
 240   /* The instruction buffer is an array of instructions, used
 241    * by the decoder to define a window of decoded instructions.
 242    * This window automatically moves as instructions are decoded
 243    * so that one can always see the current decoded instruction,
 244    * and some (fixed) number of previously decoded instructions.
 245    */
 246   NCDecoderInst* inst_buffer;
 247
 248   /* The number of elements in inst_buffer. Must be greater than zero. */
 249   size_t inst_buffer_size;
 250
 251   /* Remaining memory to decode. It is allocated on
 252    * the stack to make it thread-local, and included here
 253    * so that all decoder states have access to it.
 254    */
 255   NCRemainingMemory memory;
 256
 257   /* The begining of the memory segment to decode. */
 258   uint8_t* mbase;
 259
 260   /* The (virtual) base address of the memory segment. */
 261   NaClPcAddress vbase;
 262
 263   /* The number of bytes in the memory segment. */
 264   NaClMemorySize size;
 265
 266   /* The index of the current instruction within inst_buffer. */
 267   size_t cur_inst_index;
 268
 269   /* Holds the error reporting object to use. */
 270   NaClErrorReporter* error_reporter;
 271
 272   /* Member function to apply actions to a decoded instruction. */
 273   NCDecoderStateAction action_fn;
 274
 275   /* Member function to process new segment. */
 276   NCDecoderStateMethod new_segment_fn;
 277
 278   /* Member function called to report an error with the validity of the
 279    * memory segment.
 280    */
 281   NCDecoderStateMethod segmentation_error_fn;
 282
 283   /* Member function called to report other errors while processing the
 284    * memory segment.
 285    */
 286   NCDecoderStateMethod internal_error_fn;
 287 } NCDecoderState;
 288
 289 /*
 290  * Construct a decoder state.
 291  *
 292  * Parameters are:
 293  *   this  - The instance to be constructed.
 294  *   mbase - The begining of the memory segment to decode.
 295  *   vbase - The (virtual) base address of the memory segment.
 296  *   sz - The number of bytes in the memory segment.
 297  *
 298  * Note: Constructors of subclasses of NCDecoderState should
 299  * call this constructor first, to initialize the decoder state.
 300  */
 301 extern void NCDecoderStateConstruct(NCDecoderState* tthis,
 302                                     uint8_t* mbase, NaClPcAddress vbase,
 303                                     NaClMemorySize sz,
 304                                     NCDecoderInst* inst_buffer,
 305                                     size_t inst_buffer_size);
 306
 307 /* Define an error reporter to use to report error messages.
 308  * Note: By default, a decoder state uses the null error reporter,
 309  * which doesn't report error messages.
 310  *
 311  * WARNING: Be sure the error reporter is expecting a NCDecoderInst* for
 312  * the print_inst method.
 313  */
 314 void NCDecoderStateSetErrorReporter(NCDecoderState* tthis,
 315                                     NaClErrorReporter* reporter);
 316
 317
 318 /* A default, null error reporter for a NCDecoderInst* instruction. */
 319 extern NaClErrorReporter kNCNullErrorReporter;
 320
 321 /*
 322  * Decodes the memory segment associated with the decoder state.
 323  * Returns TRUE if able to apply action to all decoded instructions.
 324  *
 325  * Parameters are:
 326  *   this  - The decoder state.
 327  */
 328 extern Bool NCDecoderStateDecode(NCDecoderState* tthis);
 329
 330 /*
 331  * Destruct a decoder state.
 332  *
 333  * Parameters are:
 334  *   this  - The decoder state.
 335  *
 336  * Note: Destructors of subclasses of NCDecoderState should
 337  * call this destructor last, after the subinstance has been destructed.
 338  */
 339 extern void NCDecoderStateDestruct(NCDecoderState* tthis);
 340
 341 /* "Printable" means the value returned by this function can be used for
 342  * printing user-readable output, but it should not be used to influence if the
 343  * validation algorithm passes or fails.  The validation algorithm should not
 344  * depend on vbase - in other words, it should not depend on where the code is
 345  * being mapped in memory.
 346  */
 347 static INLINE NaClPcAddress NCPrintableInstructionAddress(
 348     const NCDecoderInst *dinst) {
 349   return dinst->dstate->vbase + dinst->inst_addr;
 350 }
 351
 352 struct NCDecoderStatePair;
 353
 354 /* Models a method that does a compare/update on a pair of instructions from
 355  * the pairwise instruction decoder. Returns true if the action succeeded.
 356  */
 357 typedef Bool (*NCDecoderStatePairAction)(struct NCDecoderStatePair* tthis,
 358                                          struct NCDecoderInst* dinst_old,
 359                                          struct NCDecoderInst* dinst_new);
 360
 361 /* Models decoding a pair of instruction segments, compariing/updating
 362  * them as appropriate. Assumes that two instruction segments are the same,
 363  * except for some (constant-sized) changes. At the instruction level,
 364  * the instruction lengths are assumed to be the same. Typically, this is
 365  * because the one instruction segment was an updated version of a
 366  * previous instruction segment.
 367  *
 368  * Typical use is:
 369  *
 370  * NCDecoderState dstate_old;
 371  * NCDecoderState dstate_new;
 372  * NCDecoderStatePair dstate_pair;
 373  * ... Code that constructs dstate_old and dstate_new.
 374  * NCDecoderStatePair Construct(&dstate_pair, &dstate_old, &dstate_new);
 375  * NCDecoderStatePairDecode(&dstate_pair);
 376  * NCDecoderStatePairDestruct(&dstate_pair);
 377  */
 378 typedef struct NCDecoderStatePair {
 379   /* PROTECTED: */
 380
 381   /* The old decoder state. */
 382   NCDecoderState* old_dstate;
 383
 384   /* The new decoder state. */
 385   NCDecoderState* new_dstate;
 386
 387   /* The (virtual method) action to apply to each instruction. */
 388   NCDecoderStatePairAction action_fn;
 389
 390   /* Utility function that copies a single instruction in memory, can be used in
 391    * actions.
 392    */
 393   NaClCopyInstructionFunc copy_func;
 394 } NCDecoderStatePair;
 395
 396 /*
 397  * Construct a decoder state pair.
 398  *
 399  * Parameters are:
 400  *    tthis - The decoder state pair to construct.
 401  *    old_dstate - A constructed old decoder state to use.
 402  *    new_dstate - A constructed new decoder state to use.
 403  *
 404  * Note: Constructors of subclasses of NCDecoderStatePair should
 405  * call this constructor first, to initialize the decoder pair fields.
 406  */
 407 extern void NCDecoderStatePairConstruct(
 408     NCDecoderStatePair* tthis,
 409     NCDecoderState* old_dstate,
 410     NCDecoderState* new_dstate,
 411     NaClCopyInstructionFunc copy_func);
 412
 413 /*
 414  * Decode the memory segments in each instruction state, applying
 415  * the appropriate action on each instruction till either:
 416  * (1) The instruction lengths differ.
 417  * (2) The action returns false.
 418  * Returns true if no instruction lengths differ, and the action
 419  * returns true for all found instructions.
 420  */
 421 extern Bool NCDecoderStatePairDecode(NCDecoderStatePair* tthis);
 422
 423 /*
 424  * Destruct a decoder state pair.
 425  *
 426  * Note: Destructors of subclasses of NCDecoderStatePair should
 427  * call this distructor last, after the subinstance has been destructed.
 428  */
 429 extern void NCDecoderStatePairDestruct(NCDecoderStatePair* tthis);
 430
 431 EXTERN_C_END
 432
 433 #endif  /* NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_X86_NCVAL_SEG_SFI_NCDECODE_H_ */