Writing a self-modifying x86 factorial program | Hacker News Reader

Writing a self-modifying x86 factorial program

brianstadnicki.github.io

46 pointsFastEatSlow28 comments

Doesn't self-modifying code cause massive cache flushes and stalls on modern x86 archs?

Not even that modern. The self-modifying code in the article would be slow even on chips produced in the 1990s.

Any processor using pipelines suffers from self modifying code. The Intel 80486 was the first x86 chip to have a pipeline, and it was released in April 1989(!). Granted, it only had a 5 stage pipeline, so you'd only lose a few clocks each time, but modern x86 architectures have pipelines dozens of stages deep.

I am wondering: Does it make sense to write self-modifying code not for obfuscation but for optimization? Can we have such code to speed up calculations in a way that is not possible with static code?

Does anybody know? I would be very interested in an example.

It doesn't really, a NOP is equivalent to most jumps now, I'll try to dig up a source for that in a few hours. It used to be the case 10-20 years ago, I remember reading about it on an llvm thread.

Self-modifying code was useful for optimisation back in the 80s, but these days it's usually awful for performance (with JIT compilation as the main exception to this rule).

Your CPU has an instruction cache and a data cache, and on ARM (and x86, too, but I'm not sure) these caches are not coherent. So if you modify your instruction stream with a write, you have to clear the instruction cache to ensure that your modified instructions are actually executed by the processor. If you do this a lot, this will make things S-L-O-W, because it forces you to go all the way to main memory to find the next instruction to execute.

This means that if you do want to generate code at runtime, you want to batch the modifications into large groups, so that you have to invalidate the i-cache less frequently. This actually is useful -- it's what JIT compilation is! The reason that JIT can be helpful (even in statically typed languages like Java or Haskell) is that programs often get passed functions as arguments (eg, qsort in C). A static compiler can't optimise these functions much, because you have to know what the function argument will be to do much. But at runtime, you do know what the function is, and by inlining it your code can be made much faster.

Inlining passed function pointer is not really a JIT only optimization. As long as the pointer is a constant it only requires interprocedural optimizations and/or link time optimization.

The jit can help if the value of the pointer varies dynamically and in an unpredictable way (otherwise PGO would also help).

Came here to hope someone wrote this. Wasted many hours of my young life trying to figure out why my self-modifying assembler program worked perfect in the debugger but not without it.

Could you elaborate? I feel like the OP is saying that it works just painfully slowly but your comment/problem indicates it didn't work at all without the debugger. Can you say how these relate? Am I missing something obvious?

Self modifying code on x86 has always been a bit microarch dependent as in the past there was a minimum distance required for the processor to notice the change. This is was one of the tricks anti piracy code used to keep people from reverse engineering it. Changes made close enough to the IP wouldn't be hazarded properly so the stale instruction would be executed anyway. If this code is run under a debugger the extra break/traps would change the behavior and the newer instruction would get executed rather than the stale one. Someone who plays with this on more recent x86's could talk about how this presumably works on modern x86's, but I would guess that if the CPU detects a hazard and has to roll back to a previous state, it probably goes into some kind of strong in order mode around the code in question. This might mean modern processors behave better than some older models, but likely there is a absolutely massive perf hit when this happens (think > 10x). On something like an arm or risc-v(?) without coherent I-D caches this "window" could basically be forever, it makes an interesting question around security because in theory its possible to have code being executed for extended periods of time which isn't actually visible anywhere due to page/cache invalidation not clearing stale cache lines.

This is really fascinating subject and seems like a rich area for research.

I was curious about your comment regarding arm and risc-v not having coherent instruction and data caches. Is this a toggle on these chips hen for turning it on and off? I think I remember reading about some SoC that have this configurable.

On older x86 chips - anything before the 486 - there was no cache, but opcode bytes were prefetched into a queue, ranging from 4 bytes (on the 8088) to 16 bytes on the 386. The 286 and 386 had an additional queue holding up to 3 decoded instructions (regardless of length).

These queues where "visible" in their effect on self-modifying code. After modifying one of the instructions that could be already in the queue, you had to do a jump to flush it.

If you know about this, it is obvious how certain code only works when single-stepped through, or perhaps when run on an 8088 with its shorter queue. But few people did, even among experienced programmers.

IIRC the 486 and everything newer can detect when a cache line containing code is changed, so this is no longer necessary (but bad for performance as other commenters said).

Oh wow this is fascinating bit of history. I wonder how the i-cache drift detection is implemented. Cheers.

On x86 you can use self-modifying code without explicitly flushing caches. However, if you execute the modified code soon after writing it, the penalty can be tens to hundreds of cycles (source: Agner Fog’s optimization manual).

ARM quite famously requires the explicit cache flush, and will usually fail to work without it. However, some emulators, e.g. QEMU, don’t require the cache flush, which can lead to confusion if you usually test on emulators.

Sibling answer about the cache is correct: there's very little benefit to doing this on a modern system. And it tends to trip security systems. Many exploits are some form of "trick code that wasn't self modifying into modifying itself, or jumping into this buffer in data space that I've just given you".

There might be benefits to "modify-once" code in some circumstances because of how branch prediction works. If you determine that a branch is being consistently mispredicted you can speed it up by changing the code so that it is correctly predicted - invert the test, swap the branch targets, apply a prefix instruction, etc.

It is not unusual to have CPU-specific bits of code gated behind a CPUID check; you could maybe gain a bit by doing the check and then hardwiring a branch or pasting the code into the middle of a loop.

A related trick is the "micro-interpreter". You build a hyper-specialised language and run short programs in that - which can then use self-modification as well, because they're counted as "data" and not code. I think there was a game that used this (Flashback maybe?)

Linux does this, actually. It's called "static calls", and it saves on an indirect branch by directly overwriting jmp instructions to point elsewhere: https://blog.yossarian.net/2020/12/16/Static-calls-in-Linux-.... As others have mentioned, doing this repeatedly has performance implications.

> Does it make sense to write self-modifying code not for obfuscation but for optimization? Can we have such code to speed up calculations in a way that is not possible with static code?

That depends; how broad is your definition of "self"? Within a process, this is a fairly common approach already (JIT).

Misread it as "factorio program", and was quite excited someone had ported an x86 emulator to Factorio...

>>This is quite simple, if it needs explanation then this isn’t for you.

It's for me, because you can definitely do one less loop by modifying:

cmp ebx, 0

cmp ebx, 1

> ; could exit at 1, but then it doesn't handle 0x2

that's a comment for another variant. For this, at beginning, it could simply stop at 1

You do not need the "cmp ebx, ..." because "sub ebx, 1" already sets the zero flag.

Thanks, I forgot about that

There was an edge case where when the input was 0x2, it returned 0x1, that was my quick way of handling that.

Let's see, step by step, if we put 2 in EAX what happens:

Init: EBX = 2; EAX = 2;

Loop: EBX = 1;//gets decremented

CMP EBX, 1;//it's 1 so we exit

Final result is 2. Sounds the edge case is not that of an edge after all

Also, if we're to be pedantic about the code across the article, if they used dec (directly on memory) rather than sub, in the self modifying code, they wouldn't need a load/sub/store sequence. The zero flag would still be appropriately modified.

Thanks, I forgot about dec.

adventofcode.com did something like this last year (or two years ago?)

Reply on news.ycombinator.com