5 ms·

Are there problem with CPU cache management? IIRC Intel Sandy Bridge and later generations has micro-ops cache (which lie after the decoder). Wouldn't this and

Are there problem with CPU cache management? IIRC Intel Sandy Bridge and later generations has micro-ops cache (which lie after the decoder). Wouldn't this and other instruction-level polymorphism tricks severely mess up such cache?

bogomipz 10y ago
>"Wouldn't this and other instruction-level polymorphism tricks ..." What is "instruction level polymorphism"? I have heard of instruction level parallelism but I am not familiar with polymorphism at the opcode/machine instruction level. Could you elaborate?
- mikeash 10y ago
  I believe it means any situation where a given sequence of bytes can be usefully interpreted as multiple different sequences of instructions, usually based on where you start reading. This can't be done on an architecture like, say, MIPS, where instructions are always the same length and always aligned. There's only one way to interpret any given sequence of bytes. But on an architecture like x86, a byte sequence can mean different things if you start reading it at different offsets. For an interesting example of putting this to use, check out JIT spraying: https://en.wikipedia.org/wiki/JIT_spraying https://en.wikipedia.org/wiki/JIT_spraying The idea is that you get a JIT compiler to generate malicious native code for you by making it generate innocent code that can also be interpreted as malicious code if you can find a bug that causes the CPU to jump into the middle of one of the innocent instructions.
  - bogomipz 10y ago
    That's interesting, thanks and thanks for the link. I do remember reading about JIT spraying when a while back when the term was coined. I had forgotten about it. Cheers.
emcq 10y ago
There has been a microcode cache after the decoder since at least the Pentium 4. In the Pentium 4 it's called the trace cache. Check out "The Microarchitecture of the Pentium 4" if you're curious about the architecture.
- innocenat 10y ago
  If I remember correctly from Agner's book, P4 is the only CPU that has trace cache. It also doesn't have I-cache. Later CPUs doesn't have trace cache anymore until Sandy Bridge.
  - gpderetta 10y ago
    Sandy Bridge and newer CPUs don't have a trace cache, only a uop cache; they are different things. As you said P4 was the only Intel CPU with a trace cache. /Pedantic
userbinator 10y ago
This is different from SMC since the instruction is not actually modified; AFAIK since the target of the jump doesn't need to be predicted, the processor can just continue decoding from there. The decoded uops aren't affected by overlapping instructions. It's when modifying instructions that the cache/pipeline will get flushed.
Cyph0n 10y ago
The issue with jumps/branches during instruction fetch is that the CPU doesn't 100% know whether an instruction is a branch or not. OK, how is this an issue? Well, the instruction prefetcher will end up fetching useless instructions! So "modern" (1980s+) CPUs add a branch predictor[1] to the fetch stage. The job of the branch predictor is to determine two things: (1) Is this instruction a branch? [2] (2) If it's a branch, is it taken or not? For the case of unconditional jumps, we can just focus on (1). Therefore, given that the branch predictor is never 100% accurate, even an unconditional branch can result in garbage instructions fetched into the CPU pipeline. So replacing some key unconditional jumps might in fact improve performance. [1]: Actually, I was lying. There is also the BTB, collapsing buffer, and trace cache. [2]: The fetch stage doesn't know what an instruction is; that's the job of the decode stage.
- innocenat 10y ago
  I understand your point. However, branch prediction is so good nowadays that it rarely matter, especially for short branch [1] My main concern about trace cache/micro-ops buffer is how it would act when it encounter an instruction boundary change? Would it get flushed? Decoding can be bottleneck for some workload (e.g. SIMD Integer). [1]: http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html
  - Cyph0n 10y ago
    I agree, it does seem kind of unusual to need something like this. My hope is that OP wrote about this because his/her workload was somehow struggling with trace cache misses for unconditional jumps. I can't really think of such a workload though...
  - anarazel 10y ago
    Branch prediction has gotten a lot better, that's true. Especially by taking more preceding branches into account. But saying that branch mispredictions rarely matter seems a way too strong statement. In a lot of halfway performance critical software a large number of pipeline stalls are caused by wrongly predicted branches, and utilizing the pipeline efficiently is IMO becoming Mir, not less, important.
ajross 10y ago
Presumably the uop cache is just indexed by address and would work fine. Sure, the stored instructions in the cache might overlap in their original encoding, but I don't see why that would inherently be a problem for the architecture. Would be interesting to see benchmarks though.

bogomipz 10y ago

>"Wouldn't this and other instruction-level polymorphism tricks ..." What is "instruction level polymorphism"? I have heard of instruction level parallelism but I am not familiar with polymorphism at the opcode/machine instruction level. Could you elaborate?

mikeash 10y ago
I believe it means any situation where a given sequence of bytes can be usefully interpreted as multiple different sequences of instructions, usually based on where you start reading. This can't be done on an architecture like, say, MIPS, where instructions are always the same length and always aligned. There's only one way to interpret any given sequence of bytes. But on an architecture like x86, a byte sequence can mean different things if you start reading it at different offsets. For an interesting example of putting this to use, check out JIT spraying: https://en.wikipedia.org/wiki/JIT_spraying https://en.wikipedia.org/wiki/JIT_spraying The idea is that you get a JIT compiler to generate malicious native code for you by making it generate innocent code that can also be interpreted as malicious code if you can find a bug that causes the CPU to jump into the middle of one of the innocent instructions.
- bogomipz 10y ago
  That's interesting, thanks and thanks for the link. I do remember reading about JIT spraying when a while back when the term was coined. I had forgotten about it. Cheers.

emcq 10y ago

There has been a microcode cache after the decoder since at least the Pentium 4. In the Pentium 4 it's called the trace cache. Check out "The Microarchitecture of the Pentium 4" if you're curious about the architecture.

innocenat 10y ago
If I remember correctly from Agner's book, P4 is the only CPU that has trace cache. It also doesn't have I-cache. Later CPUs doesn't have trace cache anymore until Sandy Bridge.
- gpderetta 10y ago
  Sandy Bridge and newer CPUs don't have a trace cache, only a uop cache; they are different things. As you said P4 was the only Intel CPU with a trace cache. /Pedantic

userbinator 10y ago

This is different from SMC since the instruction is not actually modified; AFAIK since the target of the jump doesn't need to be predicted, the processor can just continue decoding from there. The decoded uops aren't affected by overlapping instructions. It's when modifying instructions that the cache/pipeline will get flushed.

Cyph0n 10y ago

The issue with jumps/branches during instruction fetch is that the CPU doesn't 100% know whether an instruction is a branch or not. OK, how is this an issue? Well, the instruction prefetcher will end up fetching useless instructions! So "modern" (1980s+) CPUs add a branch predictor[1] to the fetch stage. The job of the branch predictor is to determine two things: (1) Is this instruction a branch? [2] (2) If it's a branch, is it taken or not? For the case of unconditional jumps, we can just focus on (1). Therefore, given that the branch predictor is never 100% accurate, even an unconditional branch can result in garbage instructions fetched into the CPU pipeline. So replacing some key unconditional jumps might in fact improve performance. [1]: Actually, I was lying. There is also the BTB, collapsing buffer, and trace cache. [2]: The fetch stage doesn't know what an instruction is; that's the job of the decode stage.

innocenat 10y ago
I understand your point. However, branch prediction is so good nowadays that it rarely matter, especially for short branch [1] My main concern about trace cache/micro-ops buffer is how it would act when it encounter an instruction boundary change? Would it get flushed? Decoding can be bottleneck for some workload (e.g. SIMD Integer). [1]: http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html
- Cyph0n 10y ago
  I agree, it does seem kind of unusual to need something like this. My hope is that OP wrote about this because his/her workload was somehow struggling with trace cache misses for unconditional jumps. I can't really think of such a workload though...
- anarazel 10y ago
  Branch prediction has gotten a lot better, that's true. Especially by taking more preceding branches into account. But saying that branch mispredictions rarely matter seems a way too strong statement. In a lot of halfway performance critical software a large number of pipeline stalls are caused by wrongly predicted branches, and utilizing the pipeline efficiently is IMO becoming Mir, not less, important.

ajross 10y ago

Presumably the uop cache is just indexed by address and would work fine. Sure, the stored instructions in the cache might overlap in their original encoding, but I don't see why that would inherently be a problem for the architecture. Would be interesting to see benchmarks though.