Move validator_x86_XX.rl out of unreviewed.

src/trusted/validator_ragel/validator_x86_64.rl

 /*
  * Copyright (c) 2012 The Native Client Authors. All rights reserved.
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 

[Brad Chen, 2012/10/04 17:26:04]

What is this file? Please add a comment.

[khim, 2012/10/05 08:22:53]

Done.

 #include <assert.h>
 #include <errno.h>
 #include <stddef.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
-#include "native_client/src/trusted/validator_ragel/unreviewed/validator_internal.h"
+#include "native_client/src/trusted/validator_ragel/validator_internal.h"
 
 %%{
   machine x86_64_validator;
   alphtype unsigned char;
   variable p current_position;
   variable pe end_of_bundle;
   variable eof end_of_bundle;
   variable cs current_state;
 
   include byte_machine "byte_machines.rl";
@@ skipping 73 matching lines @@
     process_2_operands_zero_extends(&restricted_register,
                                     &instruction_info_collected, rex_prefix,
                                     operand_states);
   }
 
   include decode_x86_64 "validator_x86_64_instruction.rl";
 
   data16condrep = (data16 | condrep data16 | data16 condrep);
   data16rep = (data16 | rep data16 | data16 rep);
 
   # Special %rbp modifications without required sandboxing

[Brad Chen, 2012/10/04 17:26:04]

This comment is unclear. Why don't these special modifications require
sandboxing? Or maybe there should be a TODO(khim) comment that says you are
going to come back and add sandboxing someday? Please clarify.

[khim, 2012/10/05 08:22:53]

These special instructions don't require the sandboxing because they don't
affect the SFI invariants even if they should if you'll only look on the
arguments of these operations.

+  #
+  # Note that there are two different opcodes for “mov”: “mov” with opcode
+  # “0x89” moves from “A” to “B” while “mov” with opcode “0x8b” moves from
+  # “B” to “A”.
   rbp_modifications =
     (b_0100_10x0 0x89 0xe5)                        | # mov %rsp,%rbp
     (b_0100_10x0 0x8b 0xec)                        # | mov %rsp,%rbp
     #(b_0100_1xx0 0x81 0xe5 any{3} (0x80 .. 0xff)) | # and $XXX,%rbp
     #(b_0100_1xx0 0x83 0xe5 (0x80 .. 0xff))          # and $XXX,%rbp

[Brad Chen, 2012/10/04 17:26:04]

The strange positioning of '|' and '#' and the commented-out lines of ragel
input make this quite confusing. Why are these lines commented out? Why do the
comments look like code? Please make this clearer. Maybe start by aligning the
comments?

[khim, 2012/10/05 08:22:53]

These instructions are permitted in the similar block dedicated to %rsp
handling, but not here. This is surprising. I left a commented out description
as a visual clue, but apparently it does not clarify anything and just causes
confusion.

Deleted.

     @process_0_operands;
 
   # Special instructions used for %rbp sandboxing
   rbp_sandboxing =
     (b_0100_11x0 0x01 0xfd            | # add %r15,%rbp
      b_0100_10x1 0x03 0xef            | # add %r15,%rbp
      0x49 0x8d 0x2c 0x2f              | # lea (%r15,%rbp,1),%rbp
      0x4a 0x8d 0x6c 0x3d 0x00)          # lea 0x0(%rbp,%r15,1),%rbp
     @{ if (restricted_register == REG_RBP)
          instruction_info_collected |= RESTRICTED_REGISTER_USED;
        else
          instruction_info_collected |= UNRESTRICTED_RBP_PROCESSED;
        restricted_register = NO_REG;
-       BitmapClearBit(valid_targets, (instruction_start - data));
+       MakeJumpTargetInvalid((instruction_start - data), valid_targets);

[Brad Chen, 2012/10/04 17:26:04]

Are you going to make the instruction at the target of the jump an invalid
instruction? I don't think so. Maybe "MakeInvalidJumpTarget" would be a slightly
better name?

[khim, 2012/10/05 08:22:53]

I have no opinion WRT to the best name. We clear the mark "this is a valid
target for jump here", I'm not sure how this function should be called.

Replaced to MakeInvalidJumpTarget.

     };
 
   # Special %rbp modifications without required sandboxing

[Brad Chen, 2012/10/04 17:26:04]

This line begins a section that is extremely similar to the preceding but
different. It needs a comment to make it clear why there is repetition and how
this version is different.

[khim, 2012/10/05 08:22:53]

Actually this is just bad comment. Previous one described rbp_modifications and
described instruction which change %r*B*p, this one is called rsp_modifications
and as the name implies it handles %r*S*p.

They are similar yet different because existing validator handled %rbp and %rsp
in similar yet different manner.

+  #
+  # Note that there are two different opcodes for “mov”: “mov” with opcode
+  # “0x89” moves from “A” to “B” while “mov” with opcode “0x8b” moves from
+  # “B” to “A”.
   rsp_modifications =
     (b_0100_10x0 0x89 0xec)                        | # mov %rbp,%rsp
     (b_0100_10x0 0x8b 0xe5)                        | # mov %rbp,%rsp
     #(b_0100_1xx0 0x81 0xe4 any{3} (0x80 .. 0xff)) | # and $XXX,%rsp
     #Superfluous bits are not supported:
     # http://code.google.com/p/nativeclient/issues/detail?id=3012
     (b_0100_1000 0x83 0xe4 (0x80 .. 0xff))          # and $XXX,%rsp
     @process_0_operands;
 
   # Special instructions used for %rbp sandboxing
   rsp_sandboxing =
     (b_0100_11x0 0x01 0xfc            | # add %r15,%rsp
      b_0100_10x1 0x03 0xe7            | # add %r15,%rbp
      0x4a 0x8d 0x24 0x3c)               # lea (%rsp,%r15,1),%rsp
     @{ if (restricted_register == REG_RSP)

[Brad Chen, 2012/10/04 17:26:04]

Why isn't this action commented? Please comment all actions.

[khim, 2012/10/05 08:22:53]

Done.

          instruction_info_collected |= RESTRICTED_REGISTER_USED;
        else
          instruction_info_collected |= UNRESTRICTED_RSP_PROCESSED;
        restricted_register = NO_REG;
-       BitmapClearBit(valid_targets, (instruction_start - data));
+       MakeJumpTargetInvalid((instruction_start - data), valid_targets);
     };
 
-  # naclcall or nacljmp.  Note: first "and $~0x1f, %eXX" is a normal instruction
-  # and as such will detect case where %rbp/%rsp is illegally modified.
+  # naclcall or nacljmp.  These are indirect-jump sequences. They include three

[Brad Chen, 2012/10/04 17:26:04]

Before getting into any specific instructions there ought to be a comment 'note
to reader' that explains abbrevitions, Ragel format peculiarities etc. Move the
defn. of abbreviations here. Also explain what '?' means. Also explain the
general structure of things:
  sequence of byte patterns joined with '|'
  action

[khim, 2012/10/05 08:22:53]

This is validator_internals.html.
Are you sure? They are only used in the definition of this one machine
(naclcall_or_nacljmp), they are not used for anything else.
This is explained in validator_internals.html, too.
Again: this is in validator_internals.html

+  # commands:

[Brad Chen, 2012/10/04 17:26:04]

How about "These are three-instruction indirection-jump sequences." Note:
instructions are not commands.

[khim, 2012/10/05 08:22:53]

Done.

+  #    and “and $~0x1f, %eXX”

[Brad Chen, 2012/10/04 17:26:04]

Why repeat the opcode "and" helpful in these comments? Seems like extra clutter.
The quotes are also unhelpful.

[khim, 2012/10/05 08:22:53]

Tried to make easier to see that third command may be call or jump and messed up
with the formatting. Fixed.

+  #    add “and RBASE, %rXX”
+  #    jmpq “*%rXX” or callq “*%rXX”
+  # Note: first "and $~0x1f, %eXX" is a normal instruction and as such will
+  # detect case where %rbp/%rsp is illegally modified.

[Brad Chen, 2012/10/04 17:26:04]

Who will detect this case? I don't understand the comment.

[khim, 2012/10/05 08:22:53]

When this ragel machine will be combined with normal_instruction* machine
additional action will be triggered after first instruction (not
superinstruction!). This action will check if we can actually use this
superinstruction in this particular case.

Here is bad sequence which we want to detect:
  mov %0,%esp
  and $~0x1f,%ebp
  add %r15,%rbp
  jmpq *%rbp
In this case code which is pointed to via %rbp will be executed with %rsp set to
zero.

Thankfully this situation will be detected after first two instructions:
  mov %0,%esp
  and $~0x1f,%ebp
Second instruction will already detect the error and other two instructions can
not clear it (once error is detected it's set for good and ValidateChunkAMD64
fails).

+  #
+  # There are number of variants present which differ by the REX prefix usage:

[Brad Chen, 2012/10/04 17:26:04]

Where are the variants?

[khim, 2012/10/05 08:22:53]

Below. Should I write that?

+  # we need to make sure “%eXX” in “and”, “%rXX” in “add”, and “%eXX” in “jmpq”
+  # or “callq” is the same register and it's much simpler to do if one single
+  # action handles only fixed number of bytes.
+  #
+  # Additional complication arises because x86-64 contains two different “add”
+  # instruction: with “0x01” and “0x03” opcode.  Both are in use in the wild

[Brad Chen, 2012/10/04 17:26:04]

Please avoid colorful language such as "in use in the wild thus we can not
support just one form". You could instead say "Both are allowed." Throughout
please work on making your comments more concise. You make extra work for
everybody when you write too much (or too little).

[khim, 2012/10/05 08:22:53]

The only question is: how to determine if I wrote too much or too little.

This particular comment is directed to future readers who'll want to simplify
our ABI.  They may decide to remove "0x03" version "because noone uses it" only
to find out that Bastion now "mysteriously" fail (it uses "0x01" version in
statically-supplied code, but uses "0x03" version in dynamically-generated
code).

+  # thus we can not support just one form.  They differ in the direction used:
+  # both can add “A” and “B” but one of them stores the result in “A” and other
+  # stores the result in “B” (see AMD/Intel manual for clarification).
+  #
+  # REGISTER USAGE ABBREVIATIONS:
+  #     E32:   legacy ia32 registers (all eight: %eax to %edi)
+  #     R32:   64-bit counterparts for legacy 386 registers (%rax to %rdi)
+  #     R64:   new amd64 registers (only seven: %r8 to %r14)
+  #     R32:   32-bit counterparts for new amd64 registers (%r8d to %r14d)

[Brad Chen, 2012/10/04 17:26:04]

You have defined R32 twice. I think you mean "E32" above. I'm still not entirely
thrilled with these names so if you have a better idea please suggest it. Maybe
"E86/R86" instead of "E32/R32"?

[khim, 2012/10/05 08:22:53]

Yes, and done.

+  #     RBASE: %r15 (used as “base of untrusted world” in NaCl for amd64)
   naclcall_or_nacljmp =
-     # and $~0x1f, %eax/%ecx/%edx/%ebx/%esp/%ebp/%esi/%edi
+     # This block encodes call and jump instructions of the form:
+     #     0: 83 e_ e0    and    $~0x1f,E32
+     #     3: 4_ 01 f_    add    RBASE,R32
+     #     6: ff e_       jmpq   *R32
+     #### INSTRUCTION ONE (three bytes)
+     # and $~0x1f, E32
      (0x83 (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7) 0xe0
-     # add %r15,%rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION TWO (three bytes)
+     # add RBASE, R32 (0x01 opcode)
       b_0100_11x0 0x01 (0xf8|0xf9|0xfa|0xfb|0xfc|0xfd|0xfe|0xff)
-     # callq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION THREE.c (three bytes plus optional REX prefix)

[Brad Chen, 2012/10/04 17:26:04]

three or two bytes?

[khim, 2012/10/05 08:22:53]

Done.

+     # callq R32
      ((REX_WRX? 0xff (0xd0|0xd1|0xd2|0xd3|0xd4|0xd5|0xd6|0xd7)) |
-     # jmpq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION THREE.j (three bytes plus optional REX prefix)

[Brad Chen, 2012/10/04 17:26:04]

Shouldn't 'three' be 'two' here too? Looks like 'j' is a typo.

[khim, 2012/10/05 08:22:53]

Replaced "j" with "jmp".

Now it's "INSTRUCTION THREE: call" and "INSTRUCTION THREE: jmp".

+     # jmpq R32
       (REX_WRX? 0xff (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7))))
+     # This action first compares register numbers in three atomic instructions

[Brad Chen, 2012/10/04 17:26:04]

What do you mean by 'atomic instructions'? That means something very specific;
better not to use it to refer to instructions that are part of a
super-instruction.

[khim, 2012/10/05 08:22:53]

atomic -> component.

+     # described above, then it redefines the range of the super-instruction to
+     # include the preceding sandboxing sequence and invalidates jump targets on
+     # the interior of the super-instructions and finally clears “the restricted
+     # register” variable.
+     #
+     # “Magic numbers” correspond to the structure of this particular variant of
+     # the superinstruction.

[Brad Chen, 2012/10/04 17:26:04]

Please be consistent; use either 'super-instruction' or 'superinstruction' but
not both.

[khim, 2012/10/05 08:22:53]

Done.

      @{
        instruction_start -= 6;
        if (RMFromModRM(instruction_start[1]) !=
                                             RMFromModRM(instruction_start[5]) ||
            RMFromModRM(instruction_start[1]) != RMFromModRM(*current_position))
          instruction_info_collected |= UNRECOGNIZED_INSTRUCTION;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 3);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 6);
+       MakeJumpTargetInvalid((instruction_start - data) + 3, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 6, valid_targets);
        restricted_register = NO_REG;
      } |
 
-     # and $~0x1f, %eax/%ecx/%edx/%ebx/%esp/%ebp/%esi/%edi
+     # This block encodes call and jump instructions of the form:
+     #     0: 83 e_ e0    and    $~0x1f,E32
+     #     3: 4_ 03 f_    add    RBASE,R32
+     #     6: ff e_       jmpq   *R32
+     #### INSTRUCTION ONE (three bytes)
+     # and $~0x1f, E32
      (0x83 (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7) 0xe0
-     # add %r15,%rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION TWO (three bytes)
+     # add RBASE, R32 (0x03 opcode)
       b_0100_10x1 0x03 (0xc7|0xcf|0xd7|0xdf|0xe7|0xef|0xf7|0xff)
-     # callq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION THREE.c (three bytes plus optional REX prefix)

[Brad Chen, 2012/10/04 17:26:04]

Here again I think you mean 'two' instead of 'three'

[khim, 2012/10/05 08:22:53]

Done.

+     # callq R32
      ((REX_WRX? 0xff (0xd0|0xd1|0xd2|0xd3|0xd4|0xd5|0xd6|0xd7)) |
-     # jmpq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION THREE.j (three bytes plus optional REX prefix)
+     # jmpq R32
       (REX_WRX? 0xff (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7))))
+     # This action first compares register numbers in three atomic instructions
+     # described above, then it redefines the range of the super-instruction to
+     # include the preceding sandboxing sequence and invalidates jump targets on
+     # the interior of the super-instructions and finally clears “the restricted
+     # register” variable.
+     #
+     # “Magic numbers” correspond to the structure of this particular variant of
+     # the superinstruction.

[Brad Chen, 2012/10/04 17:26:04]

This action is identical to the previous action. Please make it a procedure and
the action a procedure call.

[khim, 2012/10/05 08:22:53]

All actions are different: where actions are identical or substantially similar
they are already merged (or call the procedure). In particular: this one is not
an exception. Previous one used "RMFromModRM(instruction_start[5])", this one
uses "RegFromModRM(instruction_start[5])", next one uses
RMFromModRM(instruction_start[6]), but offsets are not 3 and 6, but 4 and 7,
etc.

I'm not sure if function call will clarify anything here: we'll need to pass
along:
 - Couple of boolean flags
 - Three pointers
 - Pointer to restricted register
 - Pointer to instruction_info_collected
Ok, let's see if it's simpler or not.

      @{
        instruction_start -= 6;
        if (RMFromModRM(instruction_start[1]) !=
                                            RegFromModRM(instruction_start[5]) ||
            RMFromModRM(instruction_start[1]) != RMFromModRM(*current_position))
          instruction_info_collected |= UNRECOGNIZED_INSTRUCTION;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 3);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 6);
+       MakeJumpTargetInvalid((instruction_start - data) + 3, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 6, valid_targets);
        restricted_register = NO_REG;
      } |
 
-     # rex.R?X? and $~0x1f, %eax/%ecx/%edx/%ebx/%esp/%ebp/%esi/%edi
+     # This block encodes call and jump instructions of the form:
+     #     0: 4_ 83 e_ e0 and    $~0x1f,E32
+     #     4: 4_ 01 f_    add    RBASE,R32
+     #     7: ff e_       jmpq   *R32
+     #### INSTRUCTION ONE (four bytes)
+     # and $~0x1f, E32
     ((REX_RX 0x83 (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7) 0xe0
-     # add %r15,%rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION TWO (three bytes)
+     # add RBASE, R32 (0x01 opcode)
       b_0100_11x0 0x01 (0xf8|0xf9|0xfa|0xfb|0xfc|0xfd|0xfe|0xff)
-     # callq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION THREE.c (three bytes plus optional REX prefix)
+     # callq R32
       ((REX_WRX? 0xff (0xd0|0xd1|0xd2|0xd3|0xd4|0xd5|0xd6|0xd7)) |
-     # jmpq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     # jmpq R32
       (REX_WRX? 0xff (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7)))) |
 
-     # and $~0x1f, %r8d/%r9d/%r10d/%r11d/%r12d/%r13d/%r14d
+     # This block encodes call and jump instructions of the form:
+     #     0: 4_ 83 e_ e0 and    $~0x1f,E64
+     #     4: 4_ 01 f_    add    RBASE,R64
+     #     7: 4_ ff e_    jmpq   *R64
+     #### INSTRUCTION ONE (four bytes)
+     # and $~0x1f, E64
      (b_0100_0xx1 0x83 (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6) 0xe0
-     # add %r15, %r8d/%r9d/%r10d/%r11d/%r12d/%r13d/%r14d
+     #### INSTRUCTION TWO (three bytes)
+     # add RBASE, R64 (0x01 opcode)
       b_0100_11x1 0x01 (0xf8|0xf9|0xfa|0xfb|0xfc|0xfd|0xfe)
-     # callq %r8/%r9/%r10/%r11/%r12/%r13/%r14
+     #### INSTRUCTION THREE.c (four bytes)
+     # callq R64
      ((b_0100_xxx1 0xff (0xd0|0xd1|0xd2|0xd3|0xd4|0xd5|0xd6)) |
-     # jmpq %r8/%r9/%r10/%r11/%r12/%r13/%r14
+     #### INSTRUCTION THREE.j (four bytes)
+     # jmpq R64
       (b_0100_xxx1 0xff (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6)))))
+     # This action first compares register numbers in three atomic instructions
+     # described above, then it redefines the range of the super-instruction to
+     # include the preceding sandboxing sequence and invalidates jump targets on
+     # the interior of the super-instructions and finally clears “the restricted
+     # register” variable.
+     #
+     # “Magic numbers” correspond to the structure of this particular variant of
+     # the superinstruction (we group actions with identical “magic numbers”).
      @{

[Brad Chen, 2012/10/04 17:26:04]

This is much too repetitive. You are increasing my work by making me read this
multiple times. As we discussed F2F, please make it a procedure call. Please
remember 'premature optimization is the root of all evil.'

[khim, 2012/10/05 08:22:53]

You can not make the description of the instruction a procedure call, you can
only turn action into one. Will this actually help readability?

        instruction_start -= 7;
        if (RMFromModRM(instruction_start[2]) !=
                                             RMFromModRM(instruction_start[6]) ||
            RMFromModRM(instruction_start[2]) != RMFromModRM(*current_position))
          instruction_info_collected |= UNRECOGNIZED_INSTRUCTION;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 4);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 7);
+       MakeJumpTargetInvalid((instruction_start - data) + 4, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 7, valid_targets);
        restricted_register = NO_REG;
      } |
 
-     # rex.R?X? and $~0x1f, %eax/%ecx/%edx/%ebx/%esp/%ebp/%esi/%edi
+     # This block encodes call and jump instructions of the form:

[Brad Chen, 2012/10/04 17:26:04]

Here I think you mean "super-instruction" not "instruction". Can you be careful
to use 'super-instruction' or 'instruction' throughout as appropriate?

[khim, 2012/10/05 08:22:53]

Done.

+     #     0: 4_ 83 e_ e0 and    $~0x1f,E32
+     #     4: 4_ 03 f_    add    RBASE,R32
+     #     7: ff e_       jmpq   *R32
+     #### INSTRUCTION ONE (four bytes)
+     # and $~0x1f, E32
     ((REX_RX 0x83 (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7) 0xe0
-     # add %r15,%rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION TWO (three bytes)
+     # add RBASE, R32 (0x03 opcode)
       b_0100_10x1 0x03 (0xc7|0xcf|0xd7|0xdf|0xe7|0xef|0xf7|0xff)
-     # callq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     #### INSTRUCTION THREE.c (three bytes plus optional REX prefix)

[Brad Chen, 2012/10/04 17:26:04]

'two'?

[khim, 2012/10/05 08:22:53]

Done.

+     # callq R32
       ((REX_WRX? 0xff (0xd0|0xd1|0xd2|0xd3|0xd4|0xd5|0xd6|0xd7)) |
-     # jmpq %rax/%rcx/%rdx/%rbx/%rsp/%rbp/%rsi/%rdi
+     # jmpq R32
       (REX_WRX? 0xff (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6|0xe7)))) |

[Brad Chen, 2012/10/04 17:26:04]

It's really hard to figure out what parenthetical  is being closed here, and
what the components of the or statement are for the '|' at the end of the line.
You need go figure out a way to format or comment this stuff to make it
readable. It looks to me like you are being sloppy with indentation. Remember
code reviewers don't get to use emacs to check for paren matching.

[khim, 2012/10/05 08:22:53]

Indeed: indentation was mixed up, sorry.

Fixed.

 
-     # and $~0x1f, %r8d/%r9d/%r10d/%r11d/%r12d/%r13d/%r14d
+     # This block encodes call and jump instructions of the form:
+     #     0: 4_ 83 e_ e0 and    $~0x1f,E64
+     #     4: 4_ 03 f_    add    RBASE,R64
+     #     7: 4_ ff e_    jmpq   *R64
+     #### INSTRUCTION ONE (four bytes)
+     # and $~0x1f, E64
      (b_0100_0xx1 0x83 (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6) 0xe0
-     # add %r15, %r8d/%r9d/%r10d/%r11d/%r12d/%r13d/%r14d
+     #### INSTRUCTION TWO (three bytes)
+     # add RBASE, R64 (0x03 opcode)
       b_0100_11x1 0x03 (0xc7|0xcf|0xd7|0xdf|0xe7|0xef|0xf7)
-     # callq %r8/%r9/%r10/%r11/%r12/%r13/%r14
+     #### INSTRUCTION THREE.c (four bytes)
+     # callq R64
      ((b_0100_xxx1 0xff (0xd0|0xd1|0xd2|0xd3|0xd4|0xd5|0xd6)) |
-     # jmpq %r8/%r9/%r10/%r11/%r12/%r13/%r14
+     #### INSTRUCTION THREE.j (four bytes)
+     # jmpq R64
       (b_0100_xxx1 0xff (0xe0|0xe1|0xe2|0xe3|0xe4|0xe5|0xe6)))))
+     # This action first compares register numbers in three atomic instructions

[Brad Chen, 2012/10/04 17:26:04]

Every place you find yourself repeating a comment word-for-word like this it is
almost surely a situation where you should be using a procedure, commenting it
exactly once, and calling it throughout.

[khim, 2012/10/05 08:22:53]

Done.

+     # described above, then it redefines the range of the super-instruction to
+     # include the preceding sandboxing sequence and invalidates jump targets on
+     # the interior of the super-instructions and finally clears “the restricted
+     # register” variable.
+     #
+     # “Magic numbers” correspond to the structure of this particular variant of
+     # the superinstruction (we group actions with identical “magic numbers”).
      @{
        instruction_start -= 7;
        if (RMFromModRM(instruction_start[2]) !=
                                            RegFromModRM(instruction_start[6]) ||
            RMFromModRM(instruction_start[2]) != RMFromModRM(*current_position))
          instruction_info_collected |= UNRECOGNIZED_INSTRUCTION;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 4);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 7);
+       MakeJumpTargetInvalid((instruction_start - data) + 4, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 7, valid_targets);
        restricted_register = NO_REG;
      };
 
   # EMMS/SSE2/AVX instructions which have implicit %ds:(%rsi) operand
   # maskmovq %mmX,%mmY
   maskmovq =
       REX_WRXB? (0x0f 0xf7)
       @CPUFeature_EMMX modrm_registers;
   # maskmovdqu %xmmX, %xmmY
   maskmovdqu =
@@ skipping 25 matching lines @@
   # String instructions which use both %ds:(%rsi) and %ds:(%rdi)
   string_instruction_rsi_rdi =
     condrep? 0xa6            | # cmpsb    %es:(%rdi),%ds:(%rsi)
     data16condrep 0xa7       | # cmpsw    %es:(%rdi),%ds:(%rsi)
     condrep? REXW_NONE? 0xa7 | # cmps[lq] %es:(%rdi),%ds:(%rsi)
 
     rep? 0xa4                | # movsb    %es:(%rdi),%ds:(%rsi)
     data16rep 0xa5           | # movsw    %es:(%rdi),%ds:(%rsi)
     rep? REXW_NONE? 0xa5     ; # movs[lq] %es:(%rdi),%ds:(%rsi)
 
+  # Superinstruction which handle instructions which require sandboxed %rsi.
+  #
+  # There are two variants which handle spurious REX prefixes.

[Brad Chen, 2012/10/04 17:26:04]

In what sense are the REX prefixes spurious? This comment is unclear. I think
you maybe mean "There are two variants, one with the REX prefix, and one
without." Why are you not using the '?' for optional bytes here? Seems
inconsistent. It would be better for many reasons to avoid this repetition.

[khim, 2012/10/05 08:22:53]

They don't change the meaning of the instruction but change it's length. And we
need to know it's length to correctly handle instruction boundaries in the
following action.

 This comment is unclear. I think

+  #
+  # Note that both “0x89 0xf6” and “0x8b 0xf6” encode “mov %esi,%esi”:
+  # “mov” with opcode “0x89” moves from “A” to “B” while “mov” with opcode
+  # “0x8b” moves from “B” to “A” but when “A” and “B” happen to denote the
+  # same register there are no functional difference between these opcodes.
   sandbox_instruction_rsi_no_rdi =
     (0x89 | 0x8b) 0xf6       . # mov %esi,%esi

[Brad Chen, 2012/10/04 17:26:04]

What does '.' mean here? How is it different from '|'? This would be good to
cover in the lead comment above (where you explain abbreviations etc.

[khim, 2012/10/05 08:22:53]

"." means concatenation which is default action, too. I've used it to just
somehow separate the instructions, but if that's not clear then it's better to
remove it.

Done.

     0x49 0x8d 0x34 0x37      . # lea (%r15,%rsi,1),%rsi
     string_instruction_rsi_no_rdi
+    # This action redefines the range of the super-instruction to include the

[Brad Chen, 2012/10/04 17:26:04]

This same identical comment is repeated at least four times. Not a good use of
your time or my time. Please use a procedure, comment it once, and give it a
useful name. When things are similar but repeated due to necessary differences,
use comments that focus on the interesting differences, e.g. "This is like case
'foo' above except for blah blah blah." 

[khim, 2012/10/05 08:22:53]

Done.

+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 6;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 2);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 6);
+       MakeJumpTargetInvalid((instruction_start - data) + 2, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 6, valid_targets);
        restricted_register = NO_REG;
     } |
 
     REX_X (0x89 | 0x8b) 0xf6 . # mov %esi,%esi
     0x49 0x8d 0x34 0x37      . # lea (%r15,%rsi,1),%rsi
     string_instruction_rsi_no_rdi
+    # This action redefines the range of the super-instruction to include the
+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 7;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 3);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 7);
+       MakeJumpTargetInvalid((instruction_start - data) + 3, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 7, valid_targets);
        restricted_register = NO_REG;
     };
 
+  # Superinstruction which handle instructions which require sandboxed %rdi.
+  #
+  # There are two variants which handle spurious REX prefixes.
+  #
+  # Note that both “0x89 0xff” and “0x8b 0xff” encode “mov %edi,%edi”:
+  # “mov” with opcode “0x89” moves from “A” to “B” while “mov” with opcode
+  # “0x8b” moves from “B” to “A” but when “A” and “B” happen to denote the
+  # same register there are no functional difference between these opcodes.
   sandbox_instruction_rdi_no_rsi =
     (0x89 | 0x8b) 0xff       . # mov %edi,%edi
     0x49 0x8d 0x3c 0x3f      . # lea (%r15,%rdi,1),%rdi
     (string_instruction_rdi_no_rsi | mmx_sse_rdi_instruction)
+    # This action redefines the range of the super-instruction to include the
+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 6;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 2);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 6);
+       MakeJumpTargetInvalid((instruction_start - data) + 2, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 6, valid_targets);
        restricted_register = NO_REG;
     } |
 
     REX_X (0x89 | 0x8b) 0xff . # mov %edi,%edi
     0x49 0x8d 0x3c 0x3f      . # lea (%r15,%rdi,1),%rdi
     (string_instruction_rdi_no_rsi | mmx_sse_rdi_instruction)
+    # This action redefines the range of the super-instruction to include the
+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 7;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 3);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 7);
+       MakeJumpTargetInvalid((instruction_start - data) + 3, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 7, valid_targets);
        restricted_register = NO_REG;
     };
 
 
-  # String instructions which use both %ds:(%rsi) and %ds:(%rdi)
+  # Superinstruction which handle instructions which require both sandboxed %rsi
+  # and sandboxed %rdi.
+  #
+  # There are four variants which handle spurious REX prefixes.
+  #
+  # Note that both “0x89 0xf6” and “0x8b 0xf6” encode “mov %esi,%esi” while both
+  # “0x89 0xff” and “0x8b 0xff” encode “mov %edi,%edi”: “mov” with opcode “0x89”
+  # moves from “A” to “B” while “mov” with opcode “0x8b” moves from “B” to “A”
+  # but when “A” and “B” happen to denote the same register there are no
+  # functional difference between these opcodes.
   sandbox_instruction_rsi_rdi =
     (0x89 | 0x8b) 0xf6       . # mov %esi,%esi
     0x49 0x8d 0x34 0x37      . # lea (%r15,%rsi,1),%rsi
     (0x89 | 0x8b) 0xff       . # mov %edi,%edi
     0x49 0x8d 0x3c 0x3f      . # lea (%r15,%rdi,1),%rdi
     string_instruction_rsi_rdi
+    # This action redefines the range of the super-instruction to include the
+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 12;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 2);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 6);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 8);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 12);
+       MakeJumpTargetInvalid((instruction_start - data) + 2, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 6, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 8, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 12, valid_targets);
        restricted_register = NO_REG;
     } |
 
     (0x89 | 0x8b) 0xf6       . # mov %esi,%esi
     0x49 0x8d 0x34 0x37      . # lea (%r15,%rsi,1),%rsi
     REX_X (0x89 | 0x8b) 0xff . # mov %edi,%edi
     0x49 0x8d 0x3c 0x3f      . # lea (%r15,%rdi,1),%rdi
     string_instruction_rsi_rdi
+    # This action redefines the range of the super-instruction to include the
+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 13;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 2);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 6);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 9);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 13);
+       MakeJumpTargetInvalid((instruction_start - data) + 2, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 6, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 9, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 13, valid_targets);
        restricted_register = NO_REG;
     } |
 
     REX_X (0x89 | 0x8b) 0xf6 . # mov %esi,%esi
     0x49 0x8d 0x34 0x37      . # lea (%r15,%rsi,1),%rsi
     (0x89 | 0x8b) 0xff       . # mov %edi,%edi
     0x49 0x8d 0x3c 0x3f      . # lea (%r15,%rdi,1),%rdi
     string_instruction_rsi_rdi
+    # This action redefines the range of the super-instruction to include the
+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 13;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 3);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 7);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 9);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 13);
+       MakeJumpTargetInvalid((instruction_start - data) + 3, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 7, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 9, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 13, valid_targets);
        restricted_register = NO_REG;
     } |
 
     REX_X (0x89 | 0x8b) 0xf6 . # mov %esi,%esi
     0x49 0x8d 0x34 0x37      . # lea (%r15,%rsi,1),%rsi
     REX_X (0x89 | 0x8b) 0xff . # mov %edi,%edi
     0x49 0x8d 0x3c 0x3f      . # lea (%r15,%rdi,1),%rdi
     string_instruction_rsi_rdi
+    # This action redefines the range of the super-instruction to include the
+    # preceding sandboxing sequence then invalidates jump targets on the
+    # interior of the super-instructions and finally clears “the restricted
+    # register” variable.
+    #
+    # “Magic numbers” correspond to the structure of this particular variant of
+    # the superinstruction.
     @{
        instruction_start -= 14;
-       BitmapClearBit(valid_targets, (instruction_start - data) + 3);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 7);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 10);
-       BitmapClearBit(valid_targets, (instruction_start - data) + 14);
+       MakeJumpTargetInvalid((instruction_start - data) + 3, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 7, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 10, valid_targets);
+       MakeJumpTargetInvalid((instruction_start - data) + 14, valid_targets);
        restricted_register = NO_REG;
     };
 
   special_instruction =
     (rbp_modifications |
      rsp_modifications |
      rbp_sandboxing |
      rsp_sandboxing |
      naclcall_or_nacljmp |
      sandbox_instruction_rsi_no_rdi |
      sandbox_instruction_rdi_no_rsi |
      sandbox_instruction_rsi_rdi)
     @{
        instruction_info_collected |= SPECIAL_INSTRUCTION;
     };
 
   # Remove special instructions which are only allowed in special cases.
   normal_instruction = one_instruction - special_instruction;
 
-  # Check if call is properly aligned
+  # Check if call is properly aligned.
+  #
+  # For direct call we explicitly encode all variations.  For indirect call
+  # we accept all the special instructions which ends with indirect call.
   call_alignment =
     ((normal_instruction &
       # Direct call
       ((data16 REX_RXB? 0xe8 rel16) |
        (REX_WRXB? 0xe8 rel32) |
        (data16 REXW_RXB 0xe8 rel32))) |
      (special_instruction &
       # Indirect call
       (any* data16? REX_WRXB? 0xff ((opcode_2 | opcode_3) any* &
                                     (modrm_memory | modrm_registers)))))
     @{
       if (((current_position - data) & kBundleMask) != kBundleMask)
         instruction_info_collected |= BAD_CALL_ALIGNMENT;
     };
 
 
   main := ((call_alignment | normal_instruction | special_instruction)
      >{
-       BitmapSetBit(valid_targets, current_position - data);
+       MakeJumpTargetValid(current_position - data, valid_targets);
      }
      @{
        if ((instruction_info_collected &
                                (VALIDATION_ERRORS_MASK | BAD_CALL_ALIGNMENT)) ||
            (options & CALL_USER_CALLBACK_ON_EACH_INSTRUCTION)) {
          result &= user_callback(
              instruction_start, current_position,
              instruction_info_collected |
              ((restricted_register << RESTRICTED_REGISTER_SHIFT) &
               RESTRICTED_REGISTER_MASK), callback_data);
        }
        /* On successful match the instruction start must point to the next byte
         * to be able to report the new offset as the start of instruction
         * causing error.  */
        instruction_start = current_position + 1;
        instruction_info_collected = 0;
        SET_REX_PREFIX(FALSE);
+       /* Top three bis of VEX2 are inverted: see AMD/Intel manual.  */
        SET_VEX_PREFIX2(0xe0);
        SET_VEX_PREFIX3(0x00);
        operand_states = 0;
      })*
     $err{
         result &= user_callback(instruction_start, current_position,
                                 UNRECOGNIZED_INSTRUCTION, callback_data);
         continue;
     };
 
 }%%
 
 %% write data;
 
 Bool ValidateChunkAMD64(const uint8_t *data, size_t size,
                         enum validation_options options,
                         const NaClCPUFeaturesX86 *cpu_features,
-                        validation_callback_func user_callback,
+                        ValidationCallbackFunc user_callback,
                         void *callback_data) {
   bitmap_word valid_targets_small;
   bitmap_word jump_dests_small;
   bitmap_word *valid_targets;
   bitmap_word *jump_dests;
   const uint8_t *current_position;
   const uint8_t *end_of_bundle;
   int result = TRUE;
 
   CHECK(sizeof valid_targets_small == sizeof jump_dests_small);
@@ skipping 26 matching lines @@
        current_position = end_of_bundle,
        end_of_bundle = current_position + kBundleSize) {
     /* Start of the instruction being processed.  */
     const uint8_t *instruction_start = current_position;
     int current_state;
     uint32_t instruction_info_collected = 0;
     /* Keeps one byte of information per operand in the current instruction:
      *  2 bits for register kinds,
      *  5 bits for register numbers (16 regs plus RIZ). */
     uint32_t operand_states = 0;
-    enum register_name base = NO_REG;
-    enum register_name index = NO_REG;
-    enum register_name restricted_register = NO_REG;
+    enum OperandName base = NO_REG;
+    enum OperandName index = NO_REG;
+    enum OperandName restricted_register = NO_REG;
     uint8_t rex_prefix = FALSE;
     uint8_t vex_prefix2 = 0xe0;
     uint8_t vex_prefix3 = 0x00;
 
     %% write init;
     %% write exec;
 
     if (restricted_register == REG_RBP)
       result &= user_callback(end_of_bundle, end_of_bundle,
                               RESTRICTED_RBP_UNPROCESSED |
@@ skipping 10 matching lines @@
                                       user_callback, callback_data);
 
   /* We only use malloc for a large code sequences  */
   if (size > sizeof valid_targets_small) {
     free(jump_dests);
     free(valid_targets);
   }
   if (!result) errno = EINVAL;
   return result;
 }