11 ms·
Destroying x86_64 instruction decoders with differential fuzzing
- stragies 7y agoFrom the great article: "x86_64 is the 64-bit extension of a 32-bit extension of a 40-year-old 16-bit ISA designed to be source-compatible with a 50-year-old 8-bit ISA. In short, it’s a mess, with each generation adding and removing functionality, ..." Nice way of wording that! :) It also explains the complexity of the following 10 pages of text.
- kjs3 7y agoLinus disagrees: https://yarchive.net/comp/linux/x86.html https://yarchive.net/comp/linux/x86.html
- tyoma 7y agoEvery time Intel has tried to more away from x86 (i960? Itanium? Maybe others...) they end up coming back. The years of backwards compatibility are a big selling point.
- wvenable 7y agoThere is value in the fact that the instruction set is an abstraction. CPU's built with more low-level instruction sets became obsolete faster because they couldn't adapt to new features and maintain compatibility as easily.
- setpatchaddress 7y agoSounds like survivorship bias. x86's longevity is due to the amount of money thrown at the problem. You could surely start with a much cleaner instruction set like the M68k and wind up with a same-or-better result after spending billions on multiple projects to invent new ways of ameliorating the complexity of the ISA, some in parallel, over time. Or you can start by eliminating most of the decode complexity and not spend those billions, like ARM.
- jcranmer 7y agoThe decoder doesn't actually take all that much space in the hardware, though. It's going to be smaller than the normal OoO logic, which means it's a pretty minor tax at best for actual hardware.
- baybal2 7y agoSaw die shots of Atom? Decoder makes more than half of the core, and there is no instruction cache. In a loop, you will be spending more joules on decoding than actual computations.
- darkmighty 7y agoInstruction complexities can be used to save bandwidth/delay (and related energy consumption) at the cost of decoder size. Communication limitations are increasingly dominant in processors afaik; so the analysis is not so simple as to decoder size either.
- jabl 7y agoCompressed RISC ISA's (e.g. RISC-V C extension) achieve density comparable to x86, with a much simpler decoder.
- adwn 7y ago> It's going to be smaller than the normal OoO logic, which means it's a pretty minor tax at best for actual hardware. But it's a major tax for designing that hardware, and a potential source of bugs (the more complex, the more difficult to debug and verify).
- cogman10 7y agoI really wish Itanium had taken off. IMO it is a superior architecture that was simply ahead of it's time. Wouldn't it be great if software instead of hardware, had complete control of instruction ordering? Wouldn't it be great to not be limited by the current SIMD restrictions? Wouldn't it be nice if you could choose to spend more compile time to get even faster programs (vs relying on the hardware to do it JIT)? I mean, I get why it didn't happen. Stupid history chose wrong (Like making electrons have a negative charge).
- wolfgke 7y ago> I really wish Itanium had taken off. IMO it is a superior architecture that was simply ahead of it's time. Itanium was an architecture that was designed for "big iron", i.e. fast, powerful computers. It is thus, in my opinion, much harder to "scale down" to, say, mobile devices than x86.
- unlinked_dll 7y agox86 hasn't really proven that it scales down well for mobile devices either.
- toast0 7y agoThere are some x86 Android phones, and Windows 10 Mobile's Continuum looked designed to be run on an x86 phone, but Intel killed that line of processors before Microsoft built a device.
- wolfgke 7y agoIntel produced SoCs for mobile devices, concretely Speatrum SC9853i and Spreadtrum SC9861G-IA. If you want to scale even further down, consider Intel Quark (https://en.wikipedia.org/wiki/Intel_Quark https://en.wikipedia.org/wiki/Intel_Quark). For an analysis why it failed in the market, consider http://linuxgizmos.com/who-killed-the-quark/ http://linuxgizmos.com/who-killed-the-quark/ To me, it seems that the central reason why these chips failed commercially is that at the lower end, SoCs offer a much thinner margins than CPUs for laptops, desktop PCs and servers.
- NPC32419419 7y agoIntel did not create x86_64. AMD did.
- teddyh 7y agoSee also this old Microsoft Windows 95-era joke: “32 bit extensions and a graphical shell for a 16 bit patch to an 8 bit operating system originally coded for a 4 bit microprocessor, written by a 2 bit company, that can't stand 1 bit of competition.”
- wolfgke 7y ago> “32 bit extensions and a graphical shell for a 16 bit patch to an 8 bit operating system originally coded for a 4 bit microprocessor, written by a 2 bit company, that can't stand 1 bit of competition.” DOS was a 16 bit operating system. The 8088 (the processor of the IBM-PC) was an 16 bit (if you consider the instruction set) or 8 bit (if you consider the width of the data bus) processor.
- jstanley 7y agoCP/M was an 8-bit operating system.
- Taniwha 7y agoto be fair the 8088 was essentially the same die as an 8086 with an 8-bit bus .... memory was expensive back then
- kjs3 7y agoThe OP referenced is what is called a 'joke'. Oddly, 'jokes' are not always intended to be pedantically accurate.
- withzombies 7y agoARM64 (aka AArch64) is the best version of x86 yet. It's clean, very little warts, they learned from their mistakes with ARMv7/Thumb2 (specifically the IT instruction). It helps that Apple controls the whole ecosystem and could seamlessly move to ARM64. The Android transition has been making progress also. Maybe someday we'll drop 32bit and 16bit support in x86 systems (and also in "modern" programming languages!).
- shakna 7y ago> ARM64 (aka AArch64) is the best version of x86 yet. Huh? Isn't that ARM and not even remotely compatible with x86?
- withzombies 7y agoARM64 is what Intel would design if they learned from the lessons of x86 and got a chance to restart.
- solarexplorer 7y agoWell, actually they did try a few times. Itanic and the Intel iAPX 432 come to mind...
- unlinked_dll 7y agohttps://en.wikipedia.org/wiki/IA-64 https://en.wikipedia.org/wiki/IA-64
- monocasa 7y agoI'm sure that's not true. I've heard a great rant from an Intel CPU engineer about how CISC is a great fit for large OoO cores. Like how memory RMW instructions can be thought of as allocating physical register file resources with no architectural register file requirements, no extra instruction stream bits required, and no confusions inside the core about register data dependencies of the instruction. It'd be fun to throw together a modern CISC-V or something that does a better job than x86 from an instruction encoding efficiency perspective, and see how it stacks up against modern RISCs.
- SilasX 7y agoEvery mobile app: "Sorry your version is incompatible with the service as it existed three months ago, you have to update."
- Amicius 7y ago“For reverse engineers and program analysts: x86_64 instruction decoding is hard.” An idea that hit me while reading this: Using a tool like this should (help to) make it easy to determine if a commercial app is using GPL libraries illicitly by assembling a syntax tree of method signatures as a first line indicator that the executable contains code matching a GPL library. If first pass indicates a match a deeper analysis of operation codes could reveal “similarities too consistent to be coincidence.” Or an I describing something that had been in use since 2001?
- loeg 7y agoFor simple code match, you can just compared bytes without decoding instructions. If you want to try and identify functionally similar but not more or less identical code from binaries, good luck; it's a very hard problem. Antivirus companies and reverse engineers would love to know how to do that efficiently.
- saagarjha 7y agoOf course, for stupid and/or lazy GPL infringers strings is often a good first check.
- mmcloughlin 7y agoGreat project and write-up. I'm reminded of a couple other projects. MC Hammer project for LLVM tests round-trip properties of the ARM assembler. http://llvm.org/devmtg/2012-04-12/Slides/Richard_Barton.pdf http://llvm.org/devmtg/2012-04-12/Slides/Richard_Barton.pdf Sandsifter x86 fuzzer. https://github.com/xoreaxeaxeax/sandsifter https://github.com/xoreaxeaxeax/sandsifter https://youtu.be/KrksBdWcZgQ https://youtu.be/KrksBdWcZgQ
- woodruffw 7y ago(Author here.) Yep! Both sandsifter and MC Hammer provided inspiration for mishegos.
- Razengan 7y agoReading even a bit about x86_64's complexity makes me see why Apple would want to move Macs to ARM (among other reasons.)
- monocasa 7y agoAt this point, I think they're just waiting out the x86_64 patents and want to release their own core.
- upofadown 7y ago>... a 40-year-old 16-bit ISA designed to be source-compatible with a 50-year-old 8-bit ISA. In fairness to the Intel of that era, they actually did a really good job with this. They gained basically zero warts from the 8080 assembler source compatibility. They mostly set out to make the best variable length 16 bit instruction set they could. They had significant competition at the time and they pretty much had to make the 8086 instruction set something very usable. The x86 instruction set horror mostly came after that.
- kjs3 7y agoLinus has some thoughts on this: https://yarchive.net/comp/linux/x86.html https://yarchive.net/comp/linux/x86.html
- DannyB2 7y agoThe 8086 introduced the abomination of segment registers. That created many software limitations for much of the 80's. Compilers with 64 K limits on array sizes, or code segment sizes, and similar. By comparison the 680x0 on classic Mac was a pleasure to program. A nice large simple flat address space.
- wolf550e 7y agoSegment registers are the source of a bunch of C language rules about undefined behavior.
- monocasa 7y agoSegmentation is really nice, and should have been carried on, IMO. Half the issue with Spectre is that there isn't a clean way to describe to the processor different memory security contexts except with a page table pointer swap. Better segmentation support could have allowed you to sandbox memory without having to jump in and out of the kernel on transitions. Hence why VMWare, and Chrome's NaCL used segmentation hardware on x86-32 when they still could.
- adwn 7y ago
- api 7y agoTangent but: what's the additional overhead on a modern chip of parsing this crazy instruction set vs. a simpler to parse one like PPC64 or ARM64? Is it significant compared to all the other stuff that almost all modern CPUs do like out of order execution, register renaming, SIMD, virtualization, etc. etc. etc.? I've seen many people argue that it's significant but I never see anything in depth from anyone who really knows. People just assume it is. A counterargument I heard once is that there is kind of a fixed complexity to parsing it and that it was significant in the past but as CPU feature sizes have shrunk and transistor counts increased (Moore's law) it's stayed relatively constant and become insignificant today compared to all the other uses of die space.
- jandrese 7y agoI think your intuition is correct that the translation step is cheap on modern silicon. One interesting thing to note is that Intel doesn't allow you to write code as micro-ops to bypass that step. This is an advantage for them as it allows them to optimize (add, modify, and remove) microops with every generation without having to worry about backwards compatibility. As long as your compiler can spit out some crusty old x86 looking instructions it is free to optimize all it wants under the hood. Having a more efficient ISA introduces a lot of pain with backwards compatibility for only a modest reduction in complexity for a step that is cheap already. Not a win.
- api 7y agoA while ago I concluded that this was one of the core conceptual issues with EPIC/VLIW designs that try to shift microcoding to the compiler. It's not that it's impossible, but there is an advantage to having the microcode layer completely hidden. It frees the CPU core engineers almost completely from having to remain backward compatible with the software that runs on the chip. At present I think of CISC instruction sets like X64 as something like a custom compression codec for the instruction stream. They're not an optimal codec but they're not too bad.
- jcranmer 7y agoIt's hard to get accurate numbers for this information, but the entire instruction decode stage on modern x86 decode is roughly the size of the OoO scheduler (see, e.g., https://wccftech.com/amd-ryzen-architecture-detailed/ https://wccftech.com/amd-ryzen-architecture-detailed/ that contains a vague core breakdown for AMD Ryzen). Modern architectures all already execute on micro-ops instead of the actual ISA instructions, so instruction decode is going to have to have the micro-op lookup anyways, as well as the micro-op cache and other functionality in the decode stage. What you might gain in die area is going to be on the order of another execution unit at best--and the value of the extra execution unit may not be all that high if you can't fetch enough instructions per cycle to use that execution unit.
- buckminster 7y agoThis is really nice. I wonder if anyone has tried fuzzing a CPU's instruction decoder? It would be surprising if they didn't have bugs.
- woodruffw 7y agoYep! sandsifter[1] does exactly that. [1]: https://github.com/xoreaxeaxeax/sandsifter https://github.com/xoreaxeaxeax/sandsifter
- bogomipz 7y agoWow, this a wonderfully rich post! I had a question about the following statement: >"In short, it’s a mess, with each generation adding and removing functionality, reusing or overloading instructions and instruction prefixes, and introducing increasingly complicated switching mechanisms between supported modes and privilege boundaries." Can someone elaborate on how a instruction at the machine level can be "overloaded"? At this machine level how can an instruction be mapped to more than one entry in the microcode table? Or does this mean overloading in the regular programming sense of something like an ADD instruction capable of working with ints, strings etc.
- woodruffw 7y agoThanks for the kind words! > Can someone elaborate on how a instruction at the machine level can be "overloaded"? At this machine level how can an instruction be mapped to more than one entry in the microcode table? Yep! Instruction overloading can occur in a few different senses: 1. As different valid permutations of operands and prefixes, e.g. `mov` 2. As having totally different functionalities in different privilege or architecture modes 3. As being repurposed entirely (e.g., inc/dec r32 are now REX prefixes) Instruction-to-microcode translation is, unfortunately, not as simple as a (single) table lookup on x86_64 ;)
- bogomipz 7y agoThanks for the examples. This is helpful. I can't help but wonder if you or anyone else might be to elaborate on your last point: >"Instruction-to-microcode translation is, unfortunately, not as simple as a (single) table lookup on x86_64 ;)" Is the because of the overloading or are there other reasons it's not as simple as a LUT? Cheers.
- woodruffw 7y agoOverloading and variable-length instructions are the two big reasons that I can think of, off the top of my head. That's pushing the limits of my understanding of how decoding and microcode generation work on-silicon, though.
- snoes 7y agoI might be overlooking this as I am on mobile, but what is the license for mishegos?
- fortran77 7y agoFor non-Yiddish speakers here, the name "mishegos" is the Yiddish word for "craziness" ("משוגעת") a Yiddish plural form of the Hebrew word for "crazy" "meshuga" "משוגע".
- jcranmer 7y agoThe x86 decoder is both simpler and more complex than it appears. I've played with the idea of creating the "worst" x86 decoder, which I classify as worst because its goal would not be to reproduce an assembly string but instead represent an oversimplified view of the instruction that makes sense semantically. So the simple part of the decoding is that x86 instructions generally consist of an "opcode", a register number, and a third parameter which is either a register number, immediate, or memory operand. Occasionally, there is also another immediate operand tacked onto the instruction, based on the opcode. The REX prefix tacks on extra bits for the register number, the VEX prefix adds a third register number and provides a way to add some opcode bytes without spending extra bytes to do so, and the EVEX prefix has a few more extra operand types. It's worth noting that if you're mapping semantics, some opcodes have the Mod/RM byte, but use fields in this parameter to add more bits to the opcode instead of as register numbers. If your semantics is prepared to handle per-register special cases (which it probably should, since x86 has per-register semantics in some cases), this isn't actually an issue. The really difficult part, though, is managing prefixes. The new REX, VEX, and EVEX prefixes all have much tighter requirements on how they interact with each other: you can use exactly one of these prefixes, and the functionality in the older ones is completely subsumed by the newer ones. But the legacy prefixes don't have any such restrictions, and thus you can do annoying things like specify several of them at once or tack them on to instructions that don't need them. The sanest way to handle prefixes, especially F0, F2, F3, 66, and 67, is to treat them instead as part of the opcode rather than an optional prefix, albeit ones that can float around a bit (although 66 is required to be the last prefix in a few cases). This also handles issues where the operand size override prefix doesn't actually override operand size. libbfd's hilariously bad results seem almost entirely due to doing the exact opposite of this rule, and not realizing that 66 and F0 actually create illegal instructions if not used correctly. (Another thing you can do with weird prefixes is to just flag the result as "probably attempting to break a disassembler"). Unless you're interested in playing around with writing x86 decoders yourself, just use XED. It's maintained by Intel, and is up-to-date with all known instructions, and it should be capable of handling even most of the weirdest edge cases in handling unusual prefix combinations correctly. That said, it doesn't warn you of the few cases where the AMD x86 decoder and the Intel x86 decoder give inconsistent results.