News for hackers. Stuff that matters.
Re:Secrets of dispatch_once; x86 performance trickery by userbinator on Friday June 06, 2014 @10:20PM (#7861067)
What I would do is have dispatch_once NOP out the call instruction that called it as one of its first operations. Inside, an atomic exchange + compare on the predicate to stop any other threads that slipped past the call, and that's all there is to it. CPUs are optimised for executing NOPs since they're so commonly used for alignment, so the only thing this costs is fetch bandwidth. Here's a quick x86 implementation PoC off the top of my head:

    ; assumptions:
    ; * this function is called via a 2-byte call instruction
    ; * cdecl register allocation
    ; * [esp] : return addr
    ; * [esp+4] : predicate ptr
    ; * [esp+8] : ptr to func() to be called once
    dispatch_once:
        pop edx              ; edx = block
        pop ecx              ; ecx = pred ptr
        mov eax, 1
        xchg eax, [ecx]
        test eax, eax        ; was a different thread here before us?
        jnz dispatch_done
        mov eax, [esp]            ; return address
        mov [eax-2], word 0x9090  ; overwrite the call
        jmp edx                   ; execute the block +return
    dispatch_done:
        ret
As the saying goes, "The fastest way to do something is to not do it at all." In this case, the compare + function call can be completely eliminated after the first time.
Re:Secrets of dispatch_once; x86 performance trickery by eridius on Friday June 06, 2014 @11:51PM (#7861217)
That requires the ability to write to the executable page, which is definitely not allowed on iOS, and not necessarily allowed elsewhere either.

It also makes the assumption that a given call to `dispatch_once()` will only ever be called with the same predicate. If it selects among a set of predicates (or is given a predicate by whatever function called it), then NOPing it out would completely break the application.

Re:Secrets of dispatch_once; x86 performance trickery by Marat_Dukhan on Friday June 06, 2014 @11:28PM (#7861165)
One day the call instruction will cross cache line boundary, the two cache lines will propogate to other cores' instruction caches with a delay, some thread will try to execute partially changed call instruction, and some senior programmer will get mad trying to debug it, a la "look, I swap these two lines and it gets to work" (b/c the call instruction does not cross cache line anymore)
Re:Secrets of dispatch_once; x86 performance trickery by userbinator on Saturday June 07, 2014 @01:57AM (#7861446)
I realise this approach has its assumptions and limitations, I was just trying to show how far you can take things if you're really after absolute performance. NOP'ing out the call instruction is the subtle part, but if you can ensure that all your calls to this function are 2-byte calls and aligned, then everything works out great.

Direct calls on x86 are 5 bytes so NOP'ing them out atomically is a bit more difficult; two ways of doing it I can think of: [1] use an 8-byte load/store, or [2] ensure the displacement part is aligned, and overwrite it with the address of a single RET instruction so the call immediately returns. The first way could be slower but effectively NOPs out the whole call, the second is simpler and faster to do but leaves the useless call/ret (while still eliminating the compare/branch.)

Incidentally, doing this is much easier on RISCs like MIPS and ARM thanks to fixed-length instructions (that automatically align), and they tend to have much shorter pipelines too so the flush penalties are lower.

Re:Secrets of dispatch_once; x86 performance trickery by MichaelGG on Friday June 06, 2014 @10:49PM (#7861102)
This is used in JITs, too - is there a reason why the author wouldn't cover it? Other than being "cheating" so to speak? I suppose environments (like game consoles) where you cannot write to executable pages?
Re:Secrets of dispatch_once; x86 performance trickery by mikeash on Friday June 06, 2014 @10:50PM (#7861106)
Even ignoring W^X problems, how do you ensure that the reads and writes of the data are properly ordered with respect to the reads and writes of the code?
Re:Secrets of dispatch_once; x86 performance trickery by cfallin on Saturday June 07, 2014 @01:00AM (#7861340)
x86 self-modifying code semantics are actually quite strong relative to most other ISAs -- a store to the currently executing code-stream logically takes effect immediately, so you could in theory modify the instruction immediately following the store, and be OK. In other words, instruction memory ordering is exactly as strong as data memory ordering.

(That said, self-modifying code is usually a bad idea when performance is concerned, because the CPU must conservatively flush the pipeline when it detects that any store might have modified the raw bytes of any instruction in the pipeline, and might have to conservatively throw away other state -- probably more expensive than whatever other atomic operations we were playing tricks to avoid.)

Re:Secrets of dispatch_once; x86 performance trickery by k4st on Saturday June 07, 2014 @01:22AM (#7861381)
My understanding is that the semantics are not as strong as they appear, although I have no experience with other architectures, so what is said to be the case and what is the case might still be relatively easier to use than other ISAs.

The optimization and software developer manuals suggest that self- and cross-modifying code must always be used with a synchronizing instruction (e.g. CPUID).

Also, this LKML discussion (https://lkml.org/lkml/2009/3/2/194) suggests that only modifying the first byte of an instruction with an int3 is safe, whereas modifying the other parts of an instruction can result in spurious faults when that instruction is next executed, unless the correct algorithm is followed.

Re:Secrets of dispatch_once; x86 performance trickery by cfallin on Saturday June 07, 2014 @01:30AM (#7861393)
Fair point -- for cross-modifying code (one core's stores affect another core's fetch), this may be true.

For self-modifying code, though (same core doing the store and fetch), the semantics are strong. See the Intel Developer Manual 3A [1], section 11.6: "[the processor] check[s] whether a write to a code segment may modify an instruction that has been prefetched for execution. If the write affects a prefetched instruction, the prefetch queue is invalidated." In other words, stores are checked against instructions already in the pipe.

Also, I was involved in an out-of-order x86 design and know for certain that we cared about getting SMC right. No serializing instructions necessary :-)

[1] http://www.intel.com/content/dam/www/public/us/en/documents/...

Re:Secrets of dispatch_once; x86 performance trickery by k4st on Saturday June 07, 2014 @01:42AM (#7861416)
Good to know! I'm in a funny place in my research project where I recently found out about the limitations of cross-modifying code. I had previously assumed that everything would work out for the best (doing hot-code patching in a DBT system that runs in kernel space), and didn't (appear to) face issues on the last version of my DBT system. For the next version, I'd like to play things safer. However, I suppose I could transparently recover from GP faults, as this is something I already do for other scenarios.

Do you have any suggestions (besides stop_machine-like IPIs for synchronizing all CPUs) on how to go about dynamic code patching in a JIT-based DBT-system? In my case, it's a priori unclear on whether or not the instruction being patched has been prefetched by another core.

Re:Secrets of dispatch_once; x86 performance trickery by cfallin on Saturday June 07, 2014 @02:13AM (#7861464)
That sounds like a tricky/interesting problem -- out of curiosity, what's the higher-level problem you're trying to solve? What are the required semantics? For CMC, synchronizing with the destination core is probably necessary. Details of how the snooping works aren't documented and you probably can't rely on particular uarch implementation details anyhow.

But -- specifically for DBT, and just a guess -- you're trying to avoid an indirection when going between translated blocks/traces, and patching them directly together? Or at least somehow modify blocks/traces already in use by other cores. Then -- at the cost of more memory usage (and icache misses), you might be able to sidestep the IPIs by generating new traces and pushing synchronization up a level to whatever dispatch/map mechanism you use to find translated code. (Think of a persistent datastructure where the only mutable state is the root pointer, not the datastructure nodes -- same concept, same concurrency benefits.)

Re:Secrets of dispatch_once; x86 performance trickery by k4st on Saturday June 07, 2014 @01:23PM (#7862529)
I'm trying to solve a few related high-level problems. One, is that I want Valgrind-like debugging for the kernel. In my last kernel DBT system, I was able to do some pretty neat things, but actually using the DBT system was hell. A lot of this had to do with some of my poor design decisions (e.g. quick hacks that revealed interesting research areas, but were never refactored into good code).

Another problem that I want to solve is turn on/off pervasive profiling. This will sound similar to kprobes / systemtap / dtrace / etc, but what I want you to think about is something like "tainting" some objects (like injecting radioactive die) and then being able to observe their entire lifetime. I want to make it easy for someone without 1) domain specific knowledge of parts of the kernel, and 2) the ability to change the kernel source code to be able to answer the following types of questions: "if I write some data to a socket, how long does it take that data to go out over the wire, where are hold ups, etc."

Specifically for DBT, you hit the nail on the head: I am patching jumps in the code cache to point to other blocks in the code cache. Your suggestion is analogous to a copy-on-write tree/graph. I will have to think more on it, as it is interesting.

If you're curious about my project, then feel free to reach out to me :-) My email is on my HN profile.

Re:Secrets of dispatch_once; x86 performance trickery by hollerith on Saturday June 07, 2014 @01:50AM (#7861431)
DBT == dynamic binary translation, in case anyone else is wondering.