5 ms·

XACT: Lock-Free Multi-CAS for C++/x64 Built on TSX

56 points by scivey7 10y ago

brudgers 10y ago
If it meets the guidelines, this might make a good 'Show HN'. Show HN guidelines: https://news.ycombinator.com/showhn.html https://news.ycombinator.com/showhn.html
0x0 10y ago
The last time I read about TSX it was a story about how Intel pushed a microcode update to disable TSX because it was flawed. Has this been fixed in newer CPUs? Is there a risk of TSX being flawed on CPUs in the wild (for example, if you're missing the latest microcode updates?) http://www.anandtech.com/show/8376/intel-disables-tsx-instructions-erratum-found-in-haswell-haswelleep-broadwelly http://www.anandtech.com/show/8376/intel-disables-tsx-instru...
- greglindahl 10y ago
  If you have a more-recent-than-2014 kernel, BIOS, or stepping, the feature bit ought to be accurate. So sure, there are some systems in the wild that are broken, but probably not that many.
  - 0x0 10y ago
    Let's say you're deploying to a random cloud VM that may or may not have the latest microcode/BIOS. How do you know if TSX is safe to use? Can it be determined in software by looking at CPUID values? (If so, do all TSX-using libraries/compilers insert such checks?) The risk of subtle locking bugs in multi threaded applications due to CPU bugs makes me want to shy away from the entire feature.
    - wtallis 10y ago
      CPUID values would be sufficient. TSX should be correct on Haswell-EX (Xeon E7), Broadwell except for the tablet SoCs (Core M), and all Skaylake, Kaby Lake and newer.
    - greglindahl 10y ago
      Note that most Linux distros put the latest microcode updates into all of their kernels for any supported version. That means that an updated box with an "old" distro is still going to be OK.
      - 0x0 10y ago
        Does that work under a hypervisor/xen/VM/whatever? Can you apply a microcode update only within a given VM?
- loeg 10y ago
  TSX was broken on Haswell CPUs. I don't know which specific newer microarchitecture fixes TSX. Microcode updates have disabled TSX on Haswell for a long time.
  - bonzini 10y ago
    Haswell Xeon E7 do not have the bug and they do enable TSC.
- htns 10y ago
  I wonder what exactly was the bug? As far as I can google it's not been made public. https://www-ssl.intel.com/content/dam/www/public/us/en/documents/specification-updates/xeon-e3-1200v3-spec-update.pdf https://www-ssl.intel.com/content/dam/www/public/us/en/docum... (errata for the CPU I have, and I just tested and the TSX instructions aren't disabled on it btw. I probably enabled TSX in BIOS and forgot about it) mentions minor issues with string instructions' interaction with TSX, rdrand having a chance of hanging if called within a transaction, but the bug blamed for the disabling of TSX (HSW136) is just described as "unpredictable system behavior" "under a complex set of internal timing conditions and system events".
andikleen2 10y ago
He's assuming that retrying forever is a valid retry strategy, which it is not. For example if a page fault was needed to satisfy one of the memory access it would never finish. See https://software.intel.com/en-us/articles/tsx-anti-patterns-in-lock-elision-code https://software.intel.com/en-us/articles/tsx-anti-patterns-... and https://software.intel.com/en-us/blogs/2013/06/23/tsx-fallback-paths https://software.intel.com/en-us/blogs/2013/06/23/tsx-fallba... for more details/ To make his code work he likely would need a global fallback lock (or a real STM) and guarantee that every change of the touched memory uses those too (which would be hard) So I'm afraid the library is fairly broken.
- loeg 10y ago
  It's really unfortunate semantics that a page fault condition during a transaction doesn't actually raise the fault. Is there a downside I'm not seeing to raising the fault and then aborting the transaction? (That way, retry would succeed.)
  - andikleen2 10y ago
    This would be only useful for "good" page faults that fault something in, but not for "bad" ones (like NULL pointer). If a bad page fault was executed it would allow transactions to crash the program, which wouldn't be very atomic. The transaction mechanism doesn't know in advance if it's a good or a bad page fault. You would need to tell the operating system kernel that the page fault happened in a transaction, and let it ignore it if it was a bad page fault. That would be much more complicated than current TSX. Also there are other cases were retries will not succeed, page fault was just an example. Another common case is the dynamic linker when a library function is first executed.
    - loeg 10y ago
      > If a bad page fault was executed it would allow transactions to crash the program, which wouldn't be very atomic. It would allow bad page faults to crash the program, i.e., ordinary behavior. No? Why do programs need this protection for HTM transactions? > You would need to tell the operating system kernel that the page fault happened in a transaction, and let it ignore it if it was a bad page fault. It wouldn't ignore it. It would fault the thread and probably tear down the process, as usual. No? > Also there are other cases were retries will not succeed, page fault was just an example. Another common case is the dynamic linker when a library function is first executed. That would be an abort due to excessive memory use? Thanks! I'm not as familiar with this stuff as I would like to be.
deleted 10y ago
[deleted]
DSingularity 10y ago
So, I looked through the readme and at the example code. I didn't dig into the implementation code. How do you deal with group size limitations? My understanding is that the hardware transactional support makes no forward progress guarantees specifically because it's bound by what it can monitor in the cache. So if the group size is too large, then transactions can keep failing. Hopefully I am not missunderstsnding this. If this is correct it means libraries of this nature have to take a position with regards to group size limits. So what is your approach?
- scivey7 10y ago
  You're correct: the limits on transaction size are unknown. That's mentioned in the documentation here https://github.com/scivey/xact/blob/master/docs/api/n_way.md https://github.com/scivey/xact/blob/master/docs/api/n_way.md TSX is a black box in many ways, and I think we can expect its behavior to change over time and across implementations. I'm not enforcing an arbitrary limit on transaction size because the primary goal is just to expose a simple C++ API to fundamental primitives. The TSX intrinsics are much more difficult to work with, and assembly is painful. If that seems like a cop-out, consider that DCAS is effectively a transaction size of two. TSX appears to handle this trivially. Yet DCAS is already a very powerful operation, and is useful in itself. As the docs emphasize, the goal is not general transactions but extended versions of the small atomic operations already in common use. In terms of safety and opinionatedness, I think of XACT like a library of locking primitives: pthread_spinlock_t is very useful, but it will not stop you from introducing deadlocks. Likewise, I won't stop you from attempting transactions that are too large to succceed on current hardware. Ultimately, I expect anyone using this to test and benchmark their own code on their own machines. Beyond a certain size, transactions will be less and less valuable even if they can be successfully completed: if you're attempting 64-way CAS, benchmarks are probably going to guide you toward traditional locking anyway.
bcatanzaro 10y ago
Are there any performance benchmarks to show when this kind of approach is useful over less exotic solutions?
- bonzini 10y ago
  We used transactional memory in QEMU to emulate load-locked/store-conditional instructions, and it had much better performance than instrumenting each store manually (20%, I think).
deleted 10y ago
[deleted]
zvrba 10y ago
What is the motivation behind this? Multi-CAS is used as a basic building block for lock-free data structures to emulate more complicated transactional operations. But when you already have TSX, why would you use multi-CAS to emulate them? It's better to modify the algorithm and express the transactions directly using TSX.
- scivey7 10y ago
  In an ideal world yes, but TSX has some significant limitations. andikleen2 has mentioned some of those in his comments. TSX is somewhat unpredictable as a general tool, and there are difficulties with e.g. knowing which transactions are even feasible. Generic "complicated transactional operations" also make lock-based fallbacks very difficult and expensive, which andikleen2 also touched on. After experimenting with more general use of TSX, I very quickly came not to trust it. So the real motivation here is to tame TSX's unpredictability by using it in a very controlled way. TSX simply isn't suitable yet for complicated transactions, but just providing hardware-level support for multi-CAS is already a big deal.

56 points by scivey7 10y ago

If it meets the guidelines, this might make a good 'Show HN'. Show HN guidelines: https://news.ycombinator.com/showhn.html https://news.ycombinator.com/showhn.html

0x0 10y ago

The last time I read about TSX it was a story about how Intel pushed a microcode update to disable TSX because it was flawed. Has this been fixed in newer CPUs? Is there a risk of TSX being flawed on CPUs in the wild (for example, if you're missing the latest microcode updates?) http://www.anandtech.com/show/8376/intel-disables-tsx-instructions-erratum-found-in-haswell-haswelleep-broadwelly http://www.anandtech.com/show/8376/intel-disables-tsx-instru...

greglindahl 10y ago
If you have a more-recent-than-2014 kernel, BIOS, or stepping, the feature bit ought to be accurate. So sure, there are some systems in the wild that are broken, but probably not that many.
- 0x0 10y ago
  Let's say you're deploying to a random cloud VM that may or may not have the latest microcode/BIOS. How do you know if TSX is safe to use? Can it be determined in software by looking at CPUID values? (If so, do all TSX-using libraries/compilers insert such checks?) The risk of subtle locking bugs in multi threaded applications due to CPU bugs makes me want to shy away from the entire feature.
  - wtallis 10y ago
    CPUID values would be sufficient. TSX should be correct on Haswell-EX (Xeon E7), Broadwell except for the tablet SoCs (Core M), and all Skaylake, Kaby Lake and newer.
  - greglindahl 10y ago
    Note that most Linux distros put the latest microcode updates into all of their kernels for any supported version. That means that an updated box with an "old" distro is still going to be OK.
    - 0x0 10y ago
      Does that work under a hypervisor/xen/VM/whatever? Can you apply a microcode update only within a given VM?
loeg 10y ago
TSX was broken on Haswell CPUs. I don't know which specific newer microarchitecture fixes TSX. Microcode updates have disabled TSX on Haswell for a long time.
- bonzini 10y ago
  Haswell Xeon E7 do not have the bug and they do enable TSC.
htns 10y ago
I wonder what exactly was the bug? As far as I can google it's not been made public. https://www-ssl.intel.com/content/dam/www/public/us/en/documents/specification-updates/xeon-e3-1200v3-spec-update.pdf https://www-ssl.intel.com/content/dam/www/public/us/en/docum... (errata for the CPU I have, and I just tested and the TSX instructions aren't disabled on it btw. I probably enabled TSX in BIOS and forgot about it) mentions minor issues with string instructions' interaction with TSX, rdrand having a chance of hanging if called within a transaction, but the bug blamed for the disabling of TSX (HSW136) is just described as "unpredictable system behavior" "under a complex set of internal timing conditions and system events".

andikleen2 10y ago

He's assuming that retrying forever is a valid retry strategy, which it is not. For example if a page fault was needed to satisfy one of the memory access it would never finish. See https://software.intel.com/en-us/articles/tsx-anti-patterns-in-lock-elision-code https://software.intel.com/en-us/articles/tsx-anti-patterns-... and https://software.intel.com/en-us/blogs/2013/06/23/tsx-fallback-paths https://software.intel.com/en-us/blogs/2013/06/23/tsx-fallba... for more details/ To make his code work he likely would need a global fallback lock (or a real STM) and guarantee that every change of the touched memory uses those too (which would be hard) So I'm afraid the library is fairly broken.

loeg 10y ago
It's really unfortunate semantics that a page fault condition during a transaction doesn't actually raise the fault. Is there a downside I'm not seeing to raising the fault and then aborting the transaction? (That way, retry would succeed.)
- andikleen2 10y ago
  This would be only useful for "good" page faults that fault something in, but not for "bad" ones (like NULL pointer). If a bad page fault was executed it would allow transactions to crash the program, which wouldn't be very atomic. The transaction mechanism doesn't know in advance if it's a good or a bad page fault. You would need to tell the operating system kernel that the page fault happened in a transaction, and let it ignore it if it was a bad page fault. That would be much more complicated than current TSX. Also there are other cases were retries will not succeed, page fault was just an example. Another common case is the dynamic linker when a library function is first executed.
  - loeg 10y ago
    > If a bad page fault was executed it would allow transactions to crash the program, which wouldn't be very atomic. It would allow bad page faults to crash the program, i.e., ordinary behavior. No? Why do programs need this protection for HTM transactions? > You would need to tell the operating system kernel that the page fault happened in a transaction, and let it ignore it if it was a bad page fault. It wouldn't ignore it. It would fault the thread and probably tear down the process, as usual. No? > Also there are other cases were retries will not succeed, page fault was just an example. Another common case is the dynamic linker when a library function is first executed. That would be an abort due to excessive memory use? Thanks! I'm not as familiar with this stuff as I would like to be.

deleted 10y ago

[deleted]

DSingularity 10y ago

So, I looked through the readme and at the example code. I didn't dig into the implementation code. How do you deal with group size limitations? My understanding is that the hardware transactional support makes no forward progress guarantees specifically because it's bound by what it can monitor in the cache. So if the group size is too large, then transactions can keep failing. Hopefully I am not missunderstsnding this. If this is correct it means libraries of this nature have to take a position with regards to group size limits. So what is your approach?

scivey7 10y ago
You're correct: the limits on transaction size are unknown. That's mentioned in the documentation here https://github.com/scivey/xact/blob/master/docs/api/n_way.md https://github.com/scivey/xact/blob/master/docs/api/n_way.md TSX is a black box in many ways, and I think we can expect its behavior to change over time and across implementations. I'm not enforcing an arbitrary limit on transaction size because the primary goal is just to expose a simple C++ API to fundamental primitives. The TSX intrinsics are much more difficult to work with, and assembly is painful. If that seems like a cop-out, consider that DCAS is effectively a transaction size of two. TSX appears to handle this trivially. Yet DCAS is already a very powerful operation, and is useful in itself. As the docs emphasize, the goal is not general transactions but extended versions of the small atomic operations already in common use. In terms of safety and opinionatedness, I think of XACT like a library of locking primitives: pthread_spinlock_t is very useful, but it will not stop you from introducing deadlocks. Likewise, I won't stop you from attempting transactions that are too large to succceed on current hardware. Ultimately, I expect anyone using this to test and benchmark their own code on their own machines. Beyond a certain size, transactions will be less and less valuable even if they can be successfully completed: if you're attempting 64-way CAS, benchmarks are probably going to guide you toward traditional locking anyway.

bcatanzaro 10y ago

Are there any performance benchmarks to show when this kind of approach is useful over less exotic solutions?

bonzini 10y ago
We used transactional memory in QEMU to emulate load-locked/store-conditional instructions, and it had much better performance than instrumenting each store manually (20%, I think).

deleted 10y ago

[deleted]

zvrba 10y ago

What is the motivation behind this? Multi-CAS is used as a basic building block for lock-free data structures to emulate more complicated transactional operations. But when you already have TSX, why would you use multi-CAS to emulate them? It's better to modify the algorithm and express the transactions directly using TSX.

scivey7 10y ago
In an ideal world yes, but TSX has some significant limitations. andikleen2 has mentioned some of those in his comments. TSX is somewhat unpredictable as a general tool, and there are difficulties with e.g. knowing which transactions are even feasible. Generic "complicated transactional operations" also make lock-based fallbacks very difficult and expensive, which andikleen2 also touched on. After experimenting with more general use of TSX, I very quickly came not to trust it. So the real motivation here is to tame TSX's unpredictability by using it in a very controlled way. TSX simply isn't suitable yet for complicated transactions, but just providing hardware-level support for multi-CAS is already a big deal.