RyanGlScott
commented
2 years ago I've been working on a fix for (1)—that is, de-duplicating all of the different combinations of prefixes from the opcode table—for a while. I've pushed my current WIP branch here in case you'd like to follow along. That branch is a bit messy at the moment, since I'm adding a separate disassembler, named defaultX64Disassembler', that de-duplicates prefixes alongside the existing defaultX64Disassembler. I've also copied a fair bit of related functionality, giving them apostrophe suffixes as well to distinguish them from the existing functionality. Once I'm confident that the new disassembler is bug-free, I'll consolidate all of these functions.
First, here is the general approach that I'm taking in this branch:
-
The structure of the opcode table has changed from this:
data OpcodeTable = OpcodeTable !NextOpcodeTable | SkipModRM !Prefixes !Def | ReadModRMTable !(V.Vector ModTable) | ReadModRMUnchecked !ModTableTo this:
data OpcodeTable' = OpcodeTable' !NextOpcodeTable' | OpcodeTableEntry ![Def] -- Defs expecting a ModR/M byte ![Def] -- Defs not expecting a ModR/M bytePreviously, the
OpcodeTabledata constructor was used any time there was an instruction opcode or a prefix byte. In the new design, theOpcodeTable'data constructor is only used for instruction opcodes—prefixes are not encoded into the structure of the table at all.One consequence of this choice is that there can sometimes be multiple instruction definitions that use a particular set of opcodes. For instance, both the
addand thevpshufbinstructions use00as their opcode. For this reason, theOpcodeTableEntrydata constructor, which represents a leaf entry in the opcode table, must contain a list ofDefs rather than just a single one. In practice, these lists are quite small, and we may want to consider using aSmallArrayto represent them.Once we have an
OpcodeTableEntry, we then use the list of parsed prefixes to disambiguate among all of the potentialDefs in the list. (Actually, there are two lists, sinceDefs with a ModR/M byte have to be disassembled in a slightly different way. In principle, we could combine these into a single list, however.) Implementing the function that performs this disambiguation is one of the main challenges of this patch—more on this in a bit. -
Instead of encoding all possible combinations of prefixes in the branching structure of the opcode table, we instead perform a parsing pass upfront that parses as many prefixes as possible before parsing instruction opcodes. Here is what this parsing pass looks like at the moment:
loopPrefixBytes :: Seq.Seq Word8 -> m InstructionInstance loopPrefixBytes prefixBytes = do b <- readByte if | b `elem` simplePrefixBytes -> loopPrefixBytes (prefixBytes Seq.|> b) | b `elem` segPrefixBytes -> loopPrefixBytes (prefixBytes Seq.|> b) | b `elem` rexPrefixBytes -> loopPrefixBytes (prefixBytes Seq.|> b) -- Two-byte VEX prefix | b == 0xc5 -> do b2 <- readByte loopPrefixBytes (prefixBytes Seq.>< Seq.fromList [b, b2]) -- Three-byte VEX prefix | b == 0xc4 -> do b2 <- readByte b3 <- readByte loopPrefixBytes (prefixBytes Seq.>< Seq.fromList [b, b2, b3]) | otherwise -> loopOpcodes prefixBytes tr0 b -- Disassemble instruction based on opcodesIf this looks too simplistic to work, that's because that is. More on this later.
-
Once we have all of the prefixes and instruction opcodes, we have to use the prefixes to disambiguate among all of the possible
Defs. My branch contains avalidatePrefixBytesfunction that performs this disambiguation. The implementation is a bit too long to go into here, but among other things, it checks that:- An instruction actually accepts all of the parsed prefixes
- If the instruction has a required prefix, then that prefix has been parsed
- The instruction has appropriate address and operand sizes as dictated by the prefixes (see the
validPrefixfuntion) - etc.
There are an enormous number of possible checks that we could put into this function—see this page for some ideas. It might be best to only implement the checks we need to disambiguate instructions and add more later if they become necessary.
-
Remove some ugly hacks in the XML file representing all x86_64 instructions (see
data/optable.xml). For instance, there are quite a fewnopdefinitions that have dummy66prefixes to accommodate the way opcode table parsing currently works, accompanied by this comment:Since we now parse prefixes upfront, I believe this hack should no longer be necessary, so we can remove these silly
66-prefixed definitions.Another similar
66prefix hack can be found in one of the definitions ofxchg:Similarly, I think we can just remove the
66here now that we handle prefixes differently.
This approach was enough to get nearly the entire flexdis86 test suite to pass, save for one exception:
pause: FAIL
Exception: TODO RGS: No parse
CallStack (from HasCallStack):
error, called at src/Flexdis86/Disassembler.hs:1115:10 in flexdis86-0.1.5-inplace:Flexdis86.Disassembler
Use -p '/pause/' to rerun this test only.Let's talk about why this happens. The prefix parsing approach that I took in step (2) makes a key assumption: bytes that can be used as prefixes will never be used as the first byte in an instruction's opcodes. After all, the only way we know how to stop disassembling prefixes is to encounter a byte that isn't in the set of known prefix bytes, which we interpret as an instruction's first opcode byte. Unfortunately, this assumption turns out not to be true. In the case of the pause instruction, we have:
But the 0xf3 byte is also used for the repz prefix:
As a result, we mistakenly parse pause's first instruction opcode as a prefix, which prevents us from finding pause in the opcode table later. One idea for working around this is to check if an instruction's opcodes start with bytes that could be interpreted as prefixes, and if so, "backtrack" through the list of parsed prefixes to remove the prefixes that were mistakenly classified as prefixes. This is essentially how the Haskell disassembler library handles parsing pause.
VEX prefixes (which the disassembler library does not handle, AFAICT) complicate matters further. The lds and les instructions have opcodes which clash with 0xc5 and 0xc4, the two-byte and three-byte VEX prefixes, respectively:
https://github.com/GaloisInc/flexdis86/blob/7109bdc9990a3e756eb7fb07419737d15ad41da0/data/optable.xml#L4256-L4263 https://github.com/GaloisInc/flexdis86/blob/7109bdc9990a3e756eb7fb07419737d15ad41da0/data/optable.xml#L4274-L4281
What's more, these prefixes are expected to be followed by some number of additional bytes, so not only would need to "backtrack" over parsing the VEX prefix, we would also need to backtrack over parsing the additional bytes that follow the prefix. Moreover, since lds and les' opcodes are each one byte, the additional bytes that we mistakenly parse upfront would correspond to the operands to the instruction! Hoo boy. It's a bit scary that the flexdis86 test suite doesn't catch this.
In short, I think we need some kind of way to perform this backtracking. I have some ideas for how to do this, but before I set out on implementing this idea, I wanted to do a quick sanity check with @travitch to make sure I'm on the right path. Can you see a simpler way to solve these problems?
travitch
The parse tables occupy about 400MB in memory after they are constructed, as can be seen in this profile collected by @RyanGlScott: verify-RSA.saw.pdf. There are two factors to this memory consumption:
Addressing the former is tricky. One could use a simple DFA to parse prefix bytes separately to save an enormous amount of space. However, not all prefixes are valid for all instructions; those restrictions are currently properly encoded in the fully elaborated tables. To separate out prefix parsing, it would be necessary to add a post-parsing check to see if the parse was valid or not.
Addressing the latter might be less tricky, as we could change the representation of the tables. Another disassembler uses a mostly unboxed structure: https://github.com/travitch/dismantle/blob/48433e7ccb02924b2f4695c8c9f09fb9cfccdfc4/dismantle-tablegen/src/Dismantle/Tablegen/LinearizedTrie.hs#L34. The x86 case is a bit trickier as the parser has more states than the parsers generated by dismantle. However, we might be able to take inspiration from the more compact parse table representation and adapt it for flexdis.