5 ms·

This just came up today. Anybody know the answer? The problem involves a JIT (for opcodes, not scripting). Chunks of code are generated. Sometimes, a chunk wil

This just came up today. Anybody know the answer? The problem involves a JIT (for opcodes, not scripting). Chunks of code are generated. Sometimes, a chunk will need to branch to a chunk that isn't yet generated or even allocated. Chunks can be cleared away for various reasons like evictions to make room, so the branches to a chunk might need to not go there anymore. One strategy is to use indirect branches. When the destination doesn't exist, the branch goes to code that will resolve that. It's a bit like how dynamic linkers work. Another strategy is to replace the code. The processor may stumble a bit over what is essentially self-modifying code, but then it eventually runs faster. The degree to which the processor will pause is a key consideration here. Anybody know? BTW, if you like digging into this stuff, we're hiring.

jnordwick 8y ago
Can't you place a trap where the target code would go? It would still be self-modifying code, but least you get rid of the indirection in the other way.
- souprock 8y ago
  Not only is that code not produced yet, but the memory isn't allocated yet. The location is thus unknown.
muricula 8y ago
At the end of the first chunk just ret. When the second chunk is generated, also emit a thunk which calls the first chunk and then calls the second chunk. Should be quite nice and efficient and will leverage the return history buffer. You're right, this stuff is fun.
- muricula 8y ago
  Also, self modifying code typically requires full pipeline serialization via an instruction like cpuid (x86) or isb (arm). There are comments about this in the architecture optimization manuals, but in general try not to go around munging code all the time. While I'm thinking about it, you should consider an out of proc JIT architecture like Edge has, as JITs are fragile and easily exploited [1]. [1]: http://wenke.gtisc.gatech.edu/papers/sdcg.pdf http://wenke.gtisc.gatech.edu/papers/sdcg.pdf
  - souprock 8y ago
    Out-of-proc would be too slow to be worthwhile in this case. This JIT isn't doing a high-level language like javascript, where large blobs of code can be generated and the performance is limited anyway by calls into other things. This JIT is for machine instructions. It's something like valgrind or qemu, in which we run modern software.
    - CoolGuySteve 8y ago
      Depending on the size of your JIT code, it's possible to be more cache efficient if the JIT is pinned to its own core and uses lockless ring buffers to enqueue one-cacheline-sized chunks back and forth. But this only works if you spend more time instruction fetching to the JIT and back than it takes to atomic queue/dequeue. In terms of latency, having the JIT in a process or thread is semantics at that point so you might as well process isolate it. It all depends on how often your JIT instruction fetches outside of L2 due to the size of itself and the code that it generates. You can approximately measure it using cachegrind and then multiply the Data + instruction L1/L2 miss values by whatever they cost on your architecture.
dragontamer 8y ago
All JIT code runs into this issue. Modern CPUs are "Harvard" machines which split instruction-fetching and data-fetching. This means you need a memory fence of some kind to synchronize the separate L1 caches. To properly handle all cases means forcing a memory fence whenever you are done writing code. I haven't thought too much about which fence is proper, but at minimum a write fence needs to ensure all data is written out as expected. You might need a full fence. EDIT: Maybe a sfence at the location of the "writing" thread, while the JIT Code needs an lfence (to ensure all caches are properly updated). IIRC, fences on both sides are needed in these cases. The "dynamic linker" idea seems better to my instinct, because it won't require these fences. Of course, testing would be required (Instincts are typically proven wrong in performance questions). IIRC, Intel Skylake and AMD Zen perform branch prediction on dynamic addresses, so you should get okay performance out of the dynamic lookup.
- jawnv6 8y ago
  a memory fence is not required, as per my reading of the Intel documentation. i think you're just guessing and haven't actually written any SMC x86? would you mind sharing what PRM sections back up this reading? maybe a careful re-read will help you figure out what "might" require a full fence.
  - dragontamer 8y ago
    I'm sorry, but I don't think I really should take your bait. I'm generally willing to hold a technical discussion among peers. But it has to be on even terms with a decent amount of respect given both ways. Your tone in the post above, as well as your posting history, does not give me any hope towards having a good discussion with you.
    - jawnv6 8y ago
      bait? regardless of my tone, a memory fence is not required. no reading of the relevant documentation supports that, if you want to be wrong you're free to do so. but please don't pretend to educate others with wild uninformed guesses, that seems worse to me. here's the documentation: https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf https://software.intel.com/sites/default/files/managed/39/c5... Section 8.1.3 Handling Self- and Cross-Modifying code (* OPTION 1 ) Store modified code (as data) into code segment; Jump to new code or an intermediate location; Execute new code; ( OPTION 2 ) Store modified code (as data) into code segment; Execute a serializing instruction; ( For example, CPUID instruction *) Execute new code; this doesn't strike me as contentious, there is no guideline that states a fence is necessary. you're possibly making the assumption that fences are "serializing instructions" and, well, again i'd question what documentation backs that interpretation up. is a sfence or lfence "more" serializing?
CoolGuySteve 8y ago
On a multithreaded implementation, you can do it with 2 stub functions and an array/hash of function pointers (hereto refered to as the "table") that itself acts as a spinlock array. Initialize the table with stub 1 and atomic write stub 1 to the table on eviction. stub 1) upon entry, atomic write stub 2 into the table. Then compile or enqueue onto a compilation thread/process. At the end of compilation, atomic write the newly compiled address to the table. stub 2) spinlock on function pointer array entry != Stub 2 address. At end of spinlock, call new function pointer. If you care about power consumption or timing attacks, the spinlock can have a backoff corresponding with the speed of your JIT compiler. This function should be able to fit into a single cacheline, so it should usually be hot. inlined thunk: Given a function, read address from table and call it. The client uses the thunk to call the function address in the table without knowing if it's compiled or not. On Intel, you shouldn't need a read fence due to MESI rules. The branch/fetch predictor works by hashing the address of the branch instruction into its own lookup table. So by forcing stub 3 to be inlined, you're relying on the hash to prefetch the correct function address and call it directly. You should also be able to put the JIT into a separate process that mmaps with the NX bit set, and have the client load without the NX bit set. So it would be difficult to exploit the JIT compiler itself (but the produced code could still be unsafe). You might want to cachealign the function table or pack similar chunks in the same function table entry to prevent false sharing whenever there's an atomic write. Also, this table is going to thrash your cache by incurring an extra cacheline load for the trampoline that it does every time. Anyways, that's my back of the napkin design for how to do it.
- souprock 8y ago
  Thanks. That is certainly a different way to think about threading. My instinct would be to keep a separate JIT cache for each thread, keeping the threads from stealing resources from each other but also keeping them from sharing the JIT effort. I think your approach is pretty much how /lib/ld-linux.so.2 deals with the PLT. I didn't see an explanation for stub 3, but I guess you mean the part of the JIT output that does the indirect jump. I take it that you believe the speed advantage of a direct jump is not enough to overcome the occasional hit caused by modifying it, with all the invalidations (icache, trace cache, etc.) that it might cause. Being similar to the dynamic linker is probably well-aligned with what Intel is trying to optimize for upcoming chips. OTOH, the spectre problem might limit what Intel does. Putting the JIT in a separate process would have to add latency. Upon hitting a missing chunk of code, translation can't really wait. The idea is to run modern stuff, such as a recent desktop OS, via the JIT. We do use more than one mapping on Linux, as required to keep SE Linux happy.
jawnv6 8y ago
you should probably check the Programmer's Reference Manual (PRM) i mean, they don't try to hide this information? Section 8.1.3 gives two options that are guaranteed to work across future iterations of hardware. the sibling comment that assumes a heavy serializing like CPUID is the ONLY method is shooting from the hip and only really appropriate if you're playing tricks with what LA you're using for the write/read. you'll probably want to skim "11.6 Self-Modifying Code" as well. SMC is guaranteed to work, not work fast. Most folks want that second one and blasting out icache entries is going to put a damper on that.
pag 8y ago
Take a look at the various block chaining approaches of dynamic binary translators (DynamoRIO, PIN, etc.). There is a lot of work done in this space.
pag 8y ago
I found an old paper I wrote about my first DBT, and it has a nice figure about how I implemented indirect branch resolution: https://imgur.com/a/dCpY7V2 https://imgur.com/a/dCpY7V2. Feel free to ping me at pag on the Empire Hacking slack if you like talking about this stuff :-D
caf 8y ago
There has recently been some work in the Linux kernel to implement some infrastructure to allow hot indirections through function pointers to be replaced by dynamically rewritten branches - this is entirely done for performance reasons, so that's at least a data point in favour of the "rewrite the jump target" option. (This is particularly motivated by the fact that Spectre mitigation requires ordinary indirect jumps in the kernel to use a "retpoline", which prevents the processor speculating the jump target but is very slow - are you using retpolines for your indirect jumps?) The most recent "static calls" patch set thread: https://lkml.org/lkml/2019/1/9/1112 https://lkml.org/lkml/2019/1/9/1112

jnordwick 8y ago

Can't you place a trap where the target code would go? It would still be self-modifying code, but least you get rid of the indirection in the other way.

souprock 8y ago
Not only is that code not produced yet, but the memory isn't allocated yet. The location is thus unknown.

muricula 8y ago

At the end of the first chunk just ret. When the second chunk is generated, also emit a thunk which calls the first chunk and then calls the second chunk. Should be quite nice and efficient and will leverage the return history buffer. You're right, this stuff is fun.

muricula 8y ago
Also, self modifying code typically requires full pipeline serialization via an instruction like cpuid (x86) or isb (arm). There are comments about this in the architecture optimization manuals, but in general try not to go around munging code all the time. While I'm thinking about it, you should consider an out of proc JIT architecture like Edge has, as JITs are fragile and easily exploited [1]. [1]: http://wenke.gtisc.gatech.edu/papers/sdcg.pdf http://wenke.gtisc.gatech.edu/papers/sdcg.pdf
- souprock 8y ago
  Out-of-proc would be too slow to be worthwhile in this case. This JIT isn't doing a high-level language like javascript, where large blobs of code can be generated and the performance is limited anyway by calls into other things. This JIT is for machine instructions. It's something like valgrind or qemu, in which we run modern software.
  - CoolGuySteve 8y ago
    Depending on the size of your JIT code, it's possible to be more cache efficient if the JIT is pinned to its own core and uses lockless ring buffers to enqueue one-cacheline-sized chunks back and forth. But this only works if you spend more time instruction fetching to the JIT and back than it takes to atomic queue/dequeue. In terms of latency, having the JIT in a process or thread is semantics at that point so you might as well process isolate it. It all depends on how often your JIT instruction fetches outside of L2 due to the size of itself and the code that it generates. You can approximately measure it using cachegrind and then multiply the Data + instruction L1/L2 miss values by whatever they cost on your architecture.

dragontamer 8y ago

All JIT code runs into this issue. Modern CPUs are "Harvard" machines which split instruction-fetching and data-fetching. This means you need a memory fence of some kind to synchronize the separate L1 caches. To properly handle all cases means forcing a memory fence whenever you are done writing code. I haven't thought too much about which fence is proper, but at minimum a write fence needs to ensure all data is written out as expected. You might need a full fence. EDIT: Maybe a sfence at the location of the "writing" thread, while the JIT Code needs an lfence (to ensure all caches are properly updated). IIRC, fences on both sides are needed in these cases. The "dynamic linker" idea seems better to my instinct, because it won't require these fences. Of course, testing would be required (Instincts are typically proven wrong in performance questions). IIRC, Intel Skylake and AMD Zen perform branch prediction on dynamic addresses, so you should get okay performance out of the dynamic lookup.

jawnv6 8y ago
a memory fence is not required, as per my reading of the Intel documentation. i think you're just guessing and haven't actually written any SMC x86? would you mind sharing what PRM sections back up this reading? maybe a careful re-read will help you figure out what "might" require a full fence.
- dragontamer 8y ago
  I'm sorry, but I don't think I really should take your bait. I'm generally willing to hold a technical discussion among peers. But it has to be on even terms with a decent amount of respect given both ways. Your tone in the post above, as well as your posting history, does not give me any hope towards having a good discussion with you.
  - jawnv6 8y ago
    bait? regardless of my tone, a memory fence is not required. no reading of the relevant documentation supports that, if you want to be wrong you're free to do so. but please don't pretend to educate others with wild uninformed guesses, that seems worse to me. here's the documentation: https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf https://software.intel.com/sites/default/files/managed/39/c5... Section 8.1.3 Handling Self- and Cross-Modifying code (* OPTION 1 ) Store modified code (as data) into code segment; Jump to new code or an intermediate location; Execute new code; ( OPTION 2 ) Store modified code (as data) into code segment; Execute a serializing instruction; ( For example, CPUID instruction *) Execute new code; this doesn't strike me as contentious, there is no guideline that states a fence is necessary. you're possibly making the assumption that fences are "serializing instructions" and, well, again i'd question what documentation backs that interpretation up. is a sfence or lfence "more" serializing?

CoolGuySteve 8y ago

On a multithreaded implementation, you can do it with 2 stub functions and an array/hash of function pointers (hereto refered to as the "table") that itself acts as a spinlock array. Initialize the table with stub 1 and atomic write stub 1 to the table on eviction. stub 1) upon entry, atomic write stub 2 into the table. Then compile or enqueue onto a compilation thread/process. At the end of compilation, atomic write the newly compiled address to the table. stub 2) spinlock on function pointer array entry != Stub 2 address. At end of spinlock, call new function pointer. If you care about power consumption or timing attacks, the spinlock can have a backoff corresponding with the speed of your JIT compiler. This function should be able to fit into a single cacheline, so it should usually be hot. inlined thunk: Given a function, read address from table and call it. The client uses the thunk to call the function address in the table without knowing if it's compiled or not. On Intel, you shouldn't need a read fence due to MESI rules. The branch/fetch predictor works by hashing the address of the branch instruction into its own lookup table. So by forcing stub 3 to be inlined, you're relying on the hash to prefetch the correct function address and call it directly. You should also be able to put the JIT into a separate process that mmaps with the NX bit set, and have the client load without the NX bit set. So it would be difficult to exploit the JIT compiler itself (but the produced code could still be unsafe). You might want to cachealign the function table or pack similar chunks in the same function table entry to prevent false sharing whenever there's an atomic write. Also, this table is going to thrash your cache by incurring an extra cacheline load for the trampoline that it does every time. Anyways, that's my back of the napkin design for how to do it.

souprock 8y ago
Thanks. That is certainly a different way to think about threading. My instinct would be to keep a separate JIT cache for each thread, keeping the threads from stealing resources from each other but also keeping them from sharing the JIT effort. I think your approach is pretty much how /lib/ld-linux.so.2 deals with the PLT. I didn't see an explanation for stub 3, but I guess you mean the part of the JIT output that does the indirect jump. I take it that you believe the speed advantage of a direct jump is not enough to overcome the occasional hit caused by modifying it, with all the invalidations (icache, trace cache, etc.) that it might cause. Being similar to the dynamic linker is probably well-aligned with what Intel is trying to optimize for upcoming chips. OTOH, the spectre problem might limit what Intel does. Putting the JIT in a separate process would have to add latency. Upon hitting a missing chunk of code, translation can't really wait. The idea is to run modern stuff, such as a recent desktop OS, via the JIT. We do use more than one mapping on Linux, as required to keep SE Linux happy.

jawnv6 8y ago

you should probably check the Programmer's Reference Manual (PRM) i mean, they don't try to hide this information? Section 8.1.3 gives two options that are guaranteed to work across future iterations of hardware. the sibling comment that assumes a heavy serializing like CPUID is the ONLY method is shooting from the hip and only really appropriate if you're playing tricks with what LA you're using for the write/read. you'll probably want to skim "11.6 Self-Modifying Code" as well. SMC is guaranteed to work, not work fast. Most folks want that second one and blasting out icache entries is going to put a damper on that.

pag 8y ago

Take a look at the various block chaining approaches of dynamic binary translators (DynamoRIO, PIN, etc.). There is a lot of work done in this space.

pag 8y ago

I found an old paper I wrote about my first DBT, and it has a nice figure about how I implemented indirect branch resolution: https://imgur.com/a/dCpY7V2 https://imgur.com/a/dCpY7V2. Feel free to ping me at pag on the Empire Hacking slack if you like talking about this stuff :-D

caf 8y ago

There has recently been some work in the Linux kernel to implement some infrastructure to allow hot indirections through function pointers to be replaced by dynamically rewritten branches - this is entirely done for performance reasons, so that's at least a data point in favour of the "rewrite the jump target" option. (This is particularly motivated by the fact that Spectre mitigation requires ordinary indirect jumps in the kernel to use a "retpoline", which prevents the processor speculating the jump target but is very slow - are you using retpolines for your indirect jumps?) The most recent "static calls" patch set thread: https://lkml.org/lkml/2019/1/9/1112 https://lkml.org/lkml/2019/1/9/1112