4 ms·

> For releasing a lock, it is obvious enough that a single atomic store is sufficient It is not obvious at all. You need a fence plus a store (or a fenced stor

> For releasing a lock, it is obvious enough that a single atomic store is sufficient It is not obvious at all. You need a fence plus a store (or a fenced store). And for a long time many locks implementations used a full fence. IIRC, for example, only relatively recentish there was enough confidence to relax the spinlock release to a release barrier on Linux.

moonchild 3y ago
You don't need a fence if you can thread a data dependency through from all memory operations inside the critical section to the release.
- gpderetta 3y ago
  Clever. But aside that that it would be hardly appropriate for a generic spinlock implementation, I'm not sure how would you thread a store-store dependency without a store fence (a load-store dependency would work of course, but that's not enough). I.e. how do you make your spin lock release store depend on all stores in the critical section? A store->load->store wouldn't work because of store buffers and load forwarding. [Edit: another way of saying this is that there is no store equivalent of load_consume] But I'm really only familiar with x86 and I do not know all the control and data dependency tricks used in more relaxed arches.
  - moonchild 3y ago
    > store-store dependency You can make it an exchange rather than a plain store. Questionably worthwhile but you can do it. swp is only 3 cycles on firestorm https://dougallj.github.io/applecpu/firestorm-int.html https://dougallj.github.io/applecpu/firestorm-int.html
    - gpderetta 3y ago
      Only 3-cycle swap is nice. I can see how you could write very specialized code for some critical sections completely omitting all barriers even on the acquire side. But 3-cycles is low even for plain loads. Is the address-to-use latency so low on firestorm?
      - moonchild 3y ago
        3 cycles is throughput, not latency; latency for normal loads is not very different from desktop parts. They win for atomic ops because they don't have a fence built in; I don't understand why intel hasn't specced non-fencing atomic ops (there are far atomics, but those are different).
        gpderetta 3y ago
        Ah, right, misread the table. I think the latency would be more relevant in this case. Re Intel atomics, yes being fully fenced by default is annoying, but it kind of falls out of TSO: it would be strange if an RMW were to be more relaxed than normal stores, so, like all stores, it has to wait for prior stores to be flushed out from the store buffer before continuing, which is high latency. Normally the latency is not observable for stores, but an RMW necessarily cannot execute the load ahead of the store. I haven't really found much documentation on them, but it is possible the far atomics might end up having these relaxed semantics (and I suspect most of the time they won't be implemented as actual far atomics). Do you have any more info on them than what's on the Intel docs?
adrian_b 3y ago
You are right, but I have not mentioned this detail because it is common for all kinds of locks and I wanted to point out which are the important differences between them, not to give an exhaustive description of a spin lock algorithm. Releasing a lock must be done with a release barrier followed by an atomic store. On ISAs that do not have release barriers, a full memory barrier is required instead. All x86 stores include an implicit release barrier and the 64-bit Armv8 and Armv9 CPUs have store-release instructions that include an implicit release barrier, so on such CPUs an explicit release barrier is not needed.

moonchild 3y ago

You don't need a fence if you can thread a data dependency through from all memory operations inside the critical section to the release.

gpderetta 3y ago
Clever. But aside that that it would be hardly appropriate for a generic spinlock implementation, I'm not sure how would you thread a store-store dependency without a store fence (a load-store dependency would work of course, but that's not enough). I.e. how do you make your spin lock release store depend on all stores in the critical section? A store->load->store wouldn't work because of store buffers and load forwarding. [Edit: another way of saying this is that there is no store equivalent of load_consume] But I'm really only familiar with x86 and I do not know all the control and data dependency tricks used in more relaxed arches.
- moonchild 3y ago
  > store-store dependency You can make it an exchange rather than a plain store. Questionably worthwhile but you can do it. swp is only 3 cycles on firestorm https://dougallj.github.io/applecpu/firestorm-int.html https://dougallj.github.io/applecpu/firestorm-int.html
  - gpderetta 3y ago
    Only 3-cycle swap is nice. I can see how you could write very specialized code for some critical sections completely omitting all barriers even on the acquire side. But 3-cycles is low even for plain loads. Is the address-to-use latency so low on firestorm?
    - moonchild 3y ago
      3 cycles is throughput, not latency; latency for normal loads is not very different from desktop parts. They win for atomic ops because they don't have a fence built in; I don't understand why intel hasn't specced non-fencing atomic ops (there are far atomics, but those are different).
      - gpderetta 3y ago
        Ah, right, misread the table. I think the latency would be more relevant in this case. Re Intel atomics, yes being fully fenced by default is annoying, but it kind of falls out of TSO: it would be strange if an RMW were to be more relaxed than normal stores, so, like all stores, it has to wait for prior stores to be flushed out from the store buffer before continuing, which is high latency. Normally the latency is not observable for stores, but an RMW necessarily cannot execute the load ahead of the store. I haven't really found much documentation on them, but it is possible the far atomics might end up having these relaxed semantics (and I suspect most of the time they won't be implemented as actual far atomics). Do you have any more info on them than what's on the Intel docs?

adrian_b 3y ago

You are right, but I have not mentioned this detail because it is common for all kinds of locks and I wanted to point out which are the important differences between them, not to give an exhaustive description of a spin lock algorithm. Releasing a lock must be done with a release barrier followed by an atomic store. On ISAs that do not have release barriers, a full memory barrier is required instead. All x86 stores include an implicit release barrier and the 64-bit Armv8 and Armv9 CPUs have store-release instructions that include an implicit release barrier, so on such CPUs an explicit release barrier is not needed.