Destroying x86_64 instruction decoders with differential fuzzing • Hacker News Board

Re: Destroying x86_64 instruction decoders with differential fuzzing

#51

Post by nipxx » Thu, Oct 31, 2019, 7:24 PM UTC

gok wrote: post #47

cogman10 wrote: post #24

Earlier quoted context omitted.

I 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…

VLIW has ultimately failed several times outside of IA-64. It was briefly tried for GPUs too.

It's alive and kicking on the Texas Instruments DSP chips. You can get incredible performance out of them, but you pay with horrible compile times.

To give you a taste what these chips do:

- 64 registers, 8 execution units, so 8 instruction can execute per cycle. Each instruction executes in a single cycle but may writes back the result later (multiplications do this for example). It's your responsibility to make sure you don't generate a conflict.

- for loops the hardware has a very complicated hardware scheduling mechanism that effectively lets you split the instruction pointer into 8 different pointers, so you can run multiple instances of a loop at the same time.

I wrote assembler code for that. Sudoku is a piece of cake compared to it.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#52

Post by adwn » Thu, Oct 31, 2019, 7:24 PM UTC

monocasa wrote: post #45

DannyB2 wrote: post #39

Earlier quoted context omitted.

The 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.

Segmentation 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 har…

One major issue was that the segments overlapped, so two different pointers could actually point to the same address.

> 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.

You don't need segments for that. A flat address space where the 2 MSBs (or however many you need) of a pointer encode the context would also work.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#53

Post by woodruffw » Thu, Oct 31, 2019, 7:27 PM UTC

bogomipz wrote: post #49

woodruffw wrote: post #42

Earlier quoted context omitted.

Thanks 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 privil…

Thanks 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.

Overloading 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.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#54

Post by cesarb » Thu, Oct 31, 2019, 7:28 PM UTC

monocasa wrote: post #43

pcwalton wrote: post #32

Earlier quoted context omitted.

The variable length nature of the ISA is a big pain for out-of-order implementations. My understanding is that, to parse ahead in your instruction stream, you basically have to take every possible byte location starting at your PC and, in parallel, decode the instruction starting there. You'll eventually end up throwing away most of the results. Naturally, this costs a fair bit of power.

You only have to do enough to figure out instruction sizes from each byte, not the full decode. RISC-V C and Arm Thumb have to to the same thing, albeit on 16-bit boundaries rather than byte boundaries.

At least for RISC-V (I haven't looked at Thumb2), the decoder only has to look at the first byte of any instruction (RISC-V instructions are always little-endian) to know how long the instruction is. For x86, it's much more complicated; the decoder has to read several bytes to find out the length of each instruction, and some of these bytes might or might not be present depending on other preceding bytes.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#55

Post by adwn » Thu, Oct 31, 2019, 7:30 PM UTC

jcranmer wrote: post #12

setpatchaddress wrote: post #11

Earlier quoted context omitted.

Sounds 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…

The 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.

> 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).

Re: Destroying x86_64 instruction decoders with differential fuzzing

#56

Post by roca » Thu, Oct 31, 2019, 7:36 PM UTC

rayiner wrote: post #38

cogman10 wrote: post #24

Earlier quoted context omitted.

I 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…

Itanium was one of those scenarios where theory blew up in practice. In theory it’s great for software to have complete control of instruction ordering. In practice, software simply doesn’t have enough information at compile time to do that. As proven by the fact that even Itanium moved to an OOO architecture in Paulson. It comes down to memory latency. Even an L3 cache hit these days is 30-40 cycles. It’s hard to pr…

Right. Generally, memory accesses in real-world software are unpredictable enough (no matter how good the compiler is) that single-threaded execution is always going to get a big boost from OOO.

An interesting question is why Intel believed otherwise when they created IA64. I think there's a strong case that publication bias and other pathologies of academic compuer science destroyed billions of dollars in value, and would have killed Intel had it not had monopoly power.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#57

Post by adwn » Thu, Oct 31, 2019, 7:38 PM UTC

withzombies wrote: post #17

stragies wrote: post #2

From 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.

ARM64 (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!).

> Maybe someday we'll drop 32bit and 16bit support in x86 systems (and also in "modern" programming languages!).

You do realize that there exists a world beyond desktop and server CPUs, right? There are plenty of 32-bit embedded microprocessors, and plenty of applications where a 64-bit processor would be overkill.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#58

Post by wtarreau » Thu, Oct 31, 2019, 7:41 PM UTC

withzombies wrote: post #17

stragies wrote: post #2

From 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.

ARM64 (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!).

Thumb2 was good. The main issue with AArch64 is that they dropped the variable instruction length. As such all instructions are huge and this significantly slows down code, especially after a mispredicted branch. I'm observing on average a 20% performance loss from thumb2 to aarch64 on the exact same CPU and same kernel, just switching executables, an d 40% larger code or so. Also something to consider, an A53 can only read 64 bits per cycle from the cache, i.e. just two instructions. That doesn't even allow it to fetch a bit more and start to decode in advance.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#59

Post by toast0 » Thu, Oct 31, 2019, 7:41 PM UTC

unlinked_dll wrote: post #33

wolfgke wrote: post #29

Earlier quoted context omitted.

> 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.

x86 hasn't really proven that it scales down well for mobile devices either.

There 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.

Re: Destroying x86_64 instruction decoders with differential fuzzing

#60

Post by jcranmer » Thu, Oct 31, 2019, 7:41 PM UTC

bogomipz wrote: post #49

woodruffw wrote: post #42

Earlier quoted context omitted.

Thanks 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 privil…

Thanks 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.

Reading Appendix A of the x86 instruction manual, which lists the opcode maps of the x86 instruction set. Section A.4 in particular gives strong insight into the answer to your question--several opcodes are represented by varying the register bits in the Mod/RM byte.

For example, opcode 0f01 is actually several opcodes depending on the Mod/RM byte. If the Mod/RM byte indicates a memory operand, then it's a SGDT, SIDT, LGDT, LIDT, LMSW, or INVLPG instruction (depending on what the first register number is). If it's a register-register form, it can be any one of 17 other instructions depending on the pair of registers.