x86: instruction decorder API

Add x86 instruction decoder to arch-specific libraries. This decoder can decode all x86 instructions into prefix, opcode, modrm, sib, displacement and immediates. This can also show the length of instructions.

changes from v4:
- make bitmap tables static.

Quoted 7 lines · Masami Hiramatsu

Add x86 instruction decoder to arch-specific libraries. This decoder can decode all x86 instructions into prefix, opcode, modrm, sib, displacement and immediates. This can also show the length of instructions.

changes from v4:
- make bitmap tables static.

Hi Masami,

On the surface the overall structure looks fine, but I have a couple of concerns:

1. is this meant to be able to decode userspace code or just kernel code? If it is supposed to be able to decode userspace code, is there a reason you're not dealing with 16-bit or V86 mode code at all? If not, why are you including the 32-bit decoder in a 64-bit kernel (as well as instructions which we're pretty much guaranteed to never use in the kernel, such as ENTER.)

2. you're already not dealing with all existing three-byte opcode spaces, nor with DREX or VEX encodings for upcoming processors. This doesn't matter so much for the kernel, but it does matter if this is supposed to be used for user-space code.

3. is there any need to deal with instruction set differences among processors? (Again, this depends on the usage model.)

4. you have a bunch of magic opcode constants all over the place. This means that as new instructions come in -- and they're going to be coming in -- this is going to be hard to update. It would be cleaner if we could have an intermediate format that preprocesses down to all the relevant tables and perhaps even some of the code rather than open-coding everything in C.

This matters... for example you have:

arch/x86/lib/insn.c new file +2 -0

+		} else if (opcode == 0xea /* jmp far seg:offs */) {
+			__get_immptr(insn);

... but nothing similar for opcode 0x9a. This is extremely hard to spot with this kind of structure.

The more data-driven we can make it (without bloating the code too much) the better off we are, I believe.

-hpa

Hi Peter,

Quoted 6 lines · H. Peter Anvin

Quoted 5 lines · Masami Hiramatsu

Add x86 instruction decoder to arch-specific libraries. This decoder can decode all x86 instructions into prefix, opcode, modrm, sib, displacement and immediates. This can also show the length of instructions.

Quoted 6 lines

Hi Masami,

On the surface the overall structure looks fine, but I have a couple of concerns:

Quoted 6 lines

1. is this meant to be able to decode userspace code or just kernel code? If it is supposed to be able to decode userspace code, is there a reason you're not dealing with 16-bit or V86 mode code at all? If not, why are you including the 32-bit decoder in a 64-bit kernel (as well as instructions which we're pretty much guaranteed to never use in the kernel, such as ENTER.)

Actually, this aims to decode both of user space and kernel code. At this point, it just needs to cover kernel code, because kprobes just want to decode kernel binary.
However, this is just a starting point, uprobe developers want to use it to decode user-space code. In that case, it needs to be enhanced.

Quoted 14 lines

4. you have a bunch of magic opcode constants all over the place. This means that as new instructions come in -- and they're going to be coming in -- this is going to be hard to update. It would be cleaner if we could have an intermediate format that preprocesses down to all the relevant tables and perhaps even some of the code rather than open-coding everything in C.

This matters... for example you have:

arch/x86/lib/insn.c new file +2 -0

+		} else if (opcode == 0xea /* jmp far seg:offs */) {
+			__get_immptr(insn);

Quoted 2 lines

... but nothing similar for opcode 0x9a. This is extremely hard to spot with this kind of structure.

Oops, that should be a bug. Hmm, I think we'd better bit-flags tables for classifying opcodes.
Jim, can your INAT idea help this situation?

http://sources.redhat.com/ml/systemtap/2009-q2/msg00109.html

Thank you for good advice!

For user-space probing, we've been concentrating on native-built executables. Am I correct in thinking that we'll see 16-bit or V86 mode only on legacy apps built elsewhere? In any case, it only makes sense to build on the kvm folks' work in this regard.

As noted, the INAT tables follow the kvm model of one fat bitmap of attributes per opcode, rather than the kprobes/uprobes model of one or two 256-bit tables per attribute. (This latter approach was due to the gradual accumulation of tables over the years.)

I like the bitmap-per-opcode approach because it's relatively easy to see in one place everything you're saying about a particular opcode. But with all the potential clients for this service, it's not clear that we'll get by with a single bitmap for every opcode. (x86 kvm uses 32 bits per opcode, I think, and the INAT tables use 10. Seems like we could overrun 64 bits pretty quickly.) So I guess that means we'll have to get a little creative as to how we expose these attribute sets to the client.

Quoted 5 lines · Jim Keniston

For user-space probing, we've been concentrating on native-built executables. Am I correct in thinking that we'll see 16-bit or V86 mode only on legacy apps built elsewhere? In any case, it only makes sense to build on the kvm folks' work in this regard.

That's a fair assumption; you will of course need to test it and take appropriate action if it doesn't pan out.

Quoted 5 lines

As noted, the INAT tables follow the kvm model of one fat bitmap of attributes per opcode, rather than the kprobes/uprobes model of one or two 256-bit tables per attribute. (This latter approach was due to the gradual accumulation of tables over the years.)

Quoted 9 lines

I like the bitmap-per-opcode approach because it's relatively easy to see in one place everything you're saying about a particular opcode. But with all the potential clients for this service, it's not clear that we'll get by with a single bitmap for every opcode. (x86 kvm uses 32 bits per opcode, I think, and the INAT tables use 10. Seems like we could overrun 64 bits pretty quickly.) So I guess that means we'll have to get a little creative as to how we expose these attribute sets to the client.

This is another very good reason to use an instruction table which is preprocessed into a usable format: it means that if the internal data structures change -- and they almost certainly will have to at some point -- the raw data isn't lost.

Hmm, I have an idea about instruction table. Usually, instruction tables are encoded with code defined by each decoder/emulator. This method will show their internal code directly, and is hard to maintain when the opcode map is updated. Instead of that, I'd like to suggest using the expressions in the opcode maps in a vender's genuine document (in this case, Intel/AMD's manual) or www.sandpile.org for instruction tables.

e.g.

const insn_attr_t onebyte_attr_table[ATTR_TABLE_SIZE] = { /* 0x00-0x0f */
AT2(Eb,Gb), AT2(Ev,Gv), AT2(Gb,Eb), AT2(Gv,Ev), AT2(AL,Ib), AT2(rAX,Iz), AT2(ES,i64), AT2(ES,i64), AT2(Eb,Gb), AT2(Ev,Gv), AT2(Gb,Eb), AT2(Gv,Ev), AT2(AL,Ib), AT2(rAX,Iz), AT2(CS,i64), AT(ESC),
...

Here, AT and AT2 macros are defined as follows:

Quoted 9 lines · Masami Hiramatsu

Hmm, I have an idea about instruction table. Usually, instruction tables are encoded with code defined by each decoder/emulator. This method will show their internal code directly, and is hard to maintain when the opcode map is updated. Instead of that, I'd like to suggest using the expressions in the opcode maps in a vender's genuine document (in this case, Intel/AMD's manual) or www.sandpile.org for instruction tables.

Yes, we discussed this at the Collab Summit. I think it's the only sane thing.

Quoted 10 lines

e.g.

const insn_attr_t onebyte_attr_table[ATTR_TABLE_SIZE] = { /* 0x00-0x0f */
AT2(Eb,Gb), AT2(Ev,Gv), AT2(Gb,Eb), AT2(Gv,Ev), AT2(AL,Ib), AT2(rAX,Iz), AT2(ES,i64), AT2(ES,i64), AT2(Eb,Gb), AT2(Ev,Gv), AT2(Gb,Eb), AT2(Gv,Ev), AT2(AL,Ib), AT2(rAX,Iz), AT2(CS,i64), AT(ESC),
...

Quoted 2 lines

Here, AT and AT2 macros are defined as follows:

I would suggest using an actual parser, rather than relying on cpp for this. The parser will be much more powerful, and will make it much easier to change data structure radically as we discussed.

Aah, I see. So we'd better make a parser which generates internal data structure from genuine opcode map in compilation time.

And I changed my mind about internal data structure too. In this version, I'll use a smallest bits which are needed for the decoder.

Hmm, I have an idea about instruction table. Usually, instruction tables are encoded with code defined by each decoder/emulator. This method will show their internal code directly, and is hard to maintain when the opcode map is updated. Instead of that, I'd like to suggest using the expressions in the opcode maps in a vender's genuine document (in this case, Intel/AMD's manual) or www.sandpile.org for instruction tables.

e.g.

const insn_attr_t onebyte_attr_table[ATTR_TABLE_SIZE] = { /* 0x00-0x0f */
AT2(Eb,Gb), AT2(Ev,Gv), AT2(Gb,Eb), AT2(Gv,Ev), AT2(AL,Ib), AT2(rAX,Iz), AT2(ES,i64), AT2(ES,i64), AT2(Eb,Gb), AT2(Ev,Gv), AT2(Gb,Eb), AT2(Gv,Ev), AT2(AL,Ib), AT2(rAX,Iz), AT2(CS,i64), AT(ESC),
...

Here, AT and AT2 macros are defined as follows:

#define AT(a) (INAT_OMEXP_##a)
#define AT2(a1, a2) (INAT_OMEXP_##a1 | INAT_OMEXP_##a2)

It looks like AT2(Ev,Gv) would yield the same bits as AT2(Gv,Ev). It'd be nice not to lose the operand-order information. And we'd have to make clear whether which notation we're using -- src,dest as in the gnu assembler, or dest,src as in the AMD (and Intel?) manuals.

Quoted 5 lines · Jim Keniston

It looks like AT2(Ev,Gv) would yield the same bits as AT2(Gv,Ev). It'd be nice not to lose the operand-order information. And we'd have to make clear whether which notation we're using -- src,dest as in the gnu assembler, or dest,src as in the AMD (and Intel?) manuals.

Since the information would come from the manuals, I would recommend following them (dst first.)

Hi Peter and Jim,

Now what I'm doing is making opcode tables like this.

Table: 1-byte opcode
Alias: none
00: ADD Eb,Gb
01: ADD Ev,Gv
02: ADD Gb,Eb
03: ADD Gv,Ev
04: ADD AL,Ib
05: ADD rAX,Iz
06: PUSH ES (i64)
07: POP ES (i64)
08: OR Eb,Gb

09: OR Ev,Gv
0a: OR Gb,Eb
0b: OR Gv,Ev
0c: OR AL,Ib
0d: OR rAX,Iz
0e: PUSH CS
0f: 2-byte escape
...

and a parser script which parses them into,

const insn_attr_t primary_table[INAT_TABLE_SIZE] = {
	[0x04] = INAT_IMM(IMM_SIZE_BYTE)
	[0x05] = INAT_IMM(IMM_SIZE_VWORD32)
	[0x0c] = INAT_IMM(IMM_SIZE_BYTE)
	[0x0d] = INAT_IMM(IMM_SIZE_VWORD32)
	[0x0f] = INAT_ESC(IMM_ESC_2BYTE)

...

(note, instructions which has no attributes for decoder, are just ignored)

By the way, I'm worried about legal things of Intel's instruction encoding expressions. Would you think there is any problem if we have those tables in the kernel tree?

Thanks,

On Tue, 2009-04-21 at 20:17 -0400, Masami Hiramatsu wrote:
...

Quoted 15 lines

Hi Peter and Jim,

Now what I'm doing is making opcode tables like this.

Table: 1-byte opcode
Alias: none
00: ADD Eb,Gb
01: ADD Ev,Gv
02: ADD Gb,Eb
03: ADD Gv,Ev
04: ADD AL,Ib
05: ADD rAX,Iz
06: PUSH ES (i64)
07: POP ES (i64)
08: OR Eb,Gb

Quoted 8 lines

09: OR Ev,Gv
0a: OR Gb,Eb
0b: OR Gv,Ev
0c: OR AL,Ib
0d: OR rAX,Iz
0e: PUSH CS
0f: 2-byte escape
...

We want to keep this info easy to parse. (Who knows how it might be used, and by whom?) Your format seems to be
opcode: mnemonic [comma,separated,operands] [(extra_info)]
which is fine if you stick to it... but your entry for 0f doesn't match that.

Also, something like
+ extra_info
would be easier to parse (using, say, awk) than
(extra_info)

Hmm, maybe, parser can handle "(extra_info)" as a solid keyword. so let's define actual format.

<opcode maps>
Table: table-name
Referrer: escamed-name
opcode: mnemonic|Grp [operand1[,operand2...]] [(extra1)[,(extra2)...] [| 2nd-mnemonic ...]
opcode: ESC # escaped-name

<group maps>
reg: mnemonic ...

On Thu, 2009-04-23 at 13:29 -0400, Masami Hiramatsu wrote:
...

Quoted 7 lines

Hmm, maybe, parser can handle "(extra_info)" as a solid keyword. so let's define actual format.

<opcode maps>
Table: table-name
Referrer: escamed-name
opcode: mnemonic|Grp [operand1[,operand2...]] [(extra1)[,(extra2)...] [| 2nd-mnemonic ...]

Quoted 1 line

opcode: ESC # escaped-name

Quoted 3 lines

<group maps>
reg: mnemonic ...

For some instruction groups -- e.g., Groups 12, 13, 14 -- the instruction prefix (66, f2, f3) and the reg field both affect the instruction type. And for some x87 instructions, the value of the modrm byte's rm field also affects the instruction type. (For others, rm just selects among the st(0)..st(7) registers, as one might expect.)

Of course, that's all about floating-point instructions, which are of more interest to uprobes than kprobes.