5 ms·

(Asking for my own edification) What does the output of branch predictor get used for in a CPU without speculation?

quasse 9y ago
Avoiding having to empty the instruction pipeline when a branch happens and restart. My favorite simple video explaining pipeline is still this old Apple one from back in the early 2000s: https://youtu.be/PKF9GOE2q38?t=237 https://youtu.be/PKF9GOE2q38?t=237
cwzwarich 9y ago
It is used to determine which instructions to fetch and decode, so that you don't have to wait until the branch is resolved to query the instruction cache, instruction TLB, MMU, DRAM, etc. If the branch was mispredicted, you have to stall to wait for this to complete.
msbarnett 9y ago
In a pipelined CPU, you want to start the memory fetches for which instructions to next feed into the instruction decoder, before the branch instruction has finished the execute stage. Otherwise every branch incurs a pipeline bubble.
- PeterisP 9y ago
  If you're doing speculative memory fetches, wouldn't that also leave a measurable impact on the cache? Simply instead of MOV AX, [something that depends on secret value] as in the original Meltdown paper you'd need to use JMP [something that depends on secret value] to trigger the memory fetch in a branch that's not going to be used.
  - msbarnett 9y ago
    Yeah, it's not 100% obvious to me that you couldn't stage some variant of Spectre against even this more limited form of speculation. In the comments on the article the author argues: "Why don’t speculative instruction (and data) fetches introduce a vulnerability? Because unlike speculative execution they don’t lead to a separation between a read instruction and the process (whether a hardware page fault or a software bounds check) that determines whether that read instruction is allowed." but that would seem to be confusing the details of Spectre with Meltdown (which is happening a lot right now). Spectre doesn't depend on unauthorized reads succeeding.
  - simias 9y ago
    Not if you're just trying to avoid a bubble in you pipeline and not actually executing the opcodes speculatively. In this situation the code will be loaded (and probably decoded etc...) but not executed before the CPU made sure that the branch was actually taken. If it's not the pipeline is flushed and a bubble is introduced after all. It's not as efficient as executing speculatively out of order but at least if you predict correctly you avoid the cost of stalling the CPU on every conditional branch until it's resolved. ARM also has an other trick for that, every opcode in the (full, non-Thumb) instruction set has a condition code that can let you execute an instruction conditionally based on the flags state without requiring an explicit branch. This way from the CPU perspective the flow of the code is linear, it's only late in the pipeline that the condition code is evaluated and the instruction discarded if it doesn't mach the flags. This way you're sure you'll never have a bubble no matter what, although the downside is that you end up fetching instructions that may end up not being executed so it's only worth it for "short" branches.
    - msbarnett 9y ago
      > Not if you're just trying to avoid a bubble in you pipeline and not actually executing the opcodes speculatively. In this situation the code will be loaded (and probably decoded etc...) but not executed before the CPU made sure that the branch was actually taken. Here's what I'm trying to figure out. Let's say there's a JIT-generated instruction that I, an attacker, am interested in learning but cannot directly read from my position in the sandbox. If I can influence the instruction fetch speculator to issue a load for that instruction, then AFAICT it doesn't matter that it never makes it as far as the execute stage -- merely the act of fetching it for decode will have had a side-effect I can probably exploit into determining what it was.
      - simias 9y ago
        Oh yeah you can do that, but I'm not sure if you can extract something useful out of this. Basically you can know whether or not a branch was speculatively loaded by timing the time it takes to go over it (if it was loaded by mistake it'll slow down execution). But then where do you go from there? Execution timings are not supposed to be secret. I can't really imagine how you can construct an attack based on that, but maybe I lack imagination.

Avoiding having to empty the instruction pipeline when a branch happens and restart. My favorite simple video explaining pipeline is still this old Apple one from back in the early 2000s: https://youtu.be/PKF9GOE2q38?t=237 https://youtu.be/PKF9GOE2q38?t=237

cwzwarich 9y ago

It is used to determine which instructions to fetch and decode, so that you don't have to wait until the branch is resolved to query the instruction cache, instruction TLB, MMU, DRAM, etc. If the branch was mispredicted, you have to stall to wait for this to complete.

msbarnett 9y ago

In a pipelined CPU, you want to start the memory fetches for which instructions to next feed into the instruction decoder, before the branch instruction has finished the execute stage. Otherwise every branch incurs a pipeline bubble.

PeterisP 9y ago
If you're doing speculative memory fetches, wouldn't that also leave a measurable impact on the cache? Simply instead of MOV AX, [something that depends on secret value] as in the original Meltdown paper you'd need to use JMP [something that depends on secret value] to trigger the memory fetch in a branch that's not going to be used.
- msbarnett 9y ago
  Yeah, it's not 100% obvious to me that you couldn't stage some variant of Spectre against even this more limited form of speculation. In the comments on the article the author argues: "Why don’t speculative instruction (and data) fetches introduce a vulnerability? Because unlike speculative execution they don’t lead to a separation between a read instruction and the process (whether a hardware page fault or a software bounds check) that determines whether that read instruction is allowed." but that would seem to be confusing the details of Spectre with Meltdown (which is happening a lot right now). Spectre doesn't depend on unauthorized reads succeeding.
- simias 9y ago
  Not if you're just trying to avoid a bubble in you pipeline and not actually executing the opcodes speculatively. In this situation the code will be loaded (and probably decoded etc...) but not executed before the CPU made sure that the branch was actually taken. If it's not the pipeline is flushed and a bubble is introduced after all. It's not as efficient as executing speculatively out of order but at least if you predict correctly you avoid the cost of stalling the CPU on every conditional branch until it's resolved. ARM also has an other trick for that, every opcode in the (full, non-Thumb) instruction set has a condition code that can let you execute an instruction conditionally based on the flags state without requiring an explicit branch. This way from the CPU perspective the flow of the code is linear, it's only late in the pipeline that the condition code is evaluated and the instruction discarded if it doesn't mach the flags. This way you're sure you'll never have a bubble no matter what, although the downside is that you end up fetching instructions that may end up not being executed so it's only worth it for "short" branches.
  - msbarnett 9y ago
    > Not if you're just trying to avoid a bubble in you pipeline and not actually executing the opcodes speculatively. In this situation the code will be loaded (and probably decoded etc...) but not executed before the CPU made sure that the branch was actually taken. Here's what I'm trying to figure out. Let's say there's a JIT-generated instruction that I, an attacker, am interested in learning but cannot directly read from my position in the sandbox. If I can influence the instruction fetch speculator to issue a load for that instruction, then AFAICT it doesn't matter that it never makes it as far as the execute stage -- merely the act of fetching it for decode will have had a side-effect I can probably exploit into determining what it was.
    - simias 9y ago
      Oh yeah you can do that, but I'm not sure if you can extract something useful out of this. Basically you can know whether or not a branch was speculatively loaded by timing the time it takes to go over it (if it was loaded by mistake it'll slow down execution). But then where do you go from there? Execution timings are not supposed to be secret. I can't really imagine how you can construct an attack based on that, but maybe I lack imagination.