Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

11–20 of 31 posts

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

#11

Post by andikleen2 »

loeg wrote: post #7
andikleen2 wrote: post #5

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-... and 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 gu…

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.)

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.

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

#12

Post by scivey7 »

andikleen2 wrote: post #10
scivey7 wrote: post #9

Earlier quoted context omitted.

I'm aware of the issue with non-terminating transactions, though I wasn't aware of the role played by page faults -- thanks for adding that detail. Looking back over the readme, I can see how the loops used in the examples are a little misleading. This is mostly a documentation issue: the core XACT code doesn't use infinite retry loops, and actually does not retry transactions at all. As with std::atomic, the goal is…

Practically all valid fallback schemes require putting the lock (or something else like a sequence counter for a STM) into the read set of the transaction to properly synchronize between transactions and non transactions. Since you hide the transaction in your library it's not possible to do that with your current API. It would be very hard to construct a fallback path that is not racy. (See Anti pattern #4 in the li…

Agreed that the basic "store to 8 locations" API would need tweaking to allow locking.

Re: adding a counter into the read set, I think the new generalized API here will support that out of the box: https://github.com/scivey/xact/blob/master/docs/api/generali...

Thoughts?

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

#13

Post by andikleen2 »

scivey7 wrote: post #12
andikleen2 wrote: post #10

Earlier quoted context omitted.

Practically all valid fallback schemes require putting the lock (or something else like a sequence counter for a STM) into the read set of the transaction to properly synchronize between transactions and non transactions. Since you hide the transaction in your library it's not possible to do that with your current API. It would be very hard to construct a fallback path that is not racy. (See Anti pattern #4 in the li…

Agreed that the basic "store to 8 locations" API would need tweaking to allow locking. Re: adding a counter into the read set, I think the new generalized API here will support that out of the box: https://github.com/scivey/xact/blob/master/docs/api/generali... Thoughts?

Yes with a read primitive it could be done in theory. It will be just quite awkward to use however as every caller has to do all that: define a lock, pass it always in, make sure the check for "lock is free" is correct etc.

Your unit tests don't seem to do it right.

It would probably be easier to hide the lock in your library, and enforce all other access to follow the right protocol using some ADTs. But then you just have a simple hardware TM accelerated STM.

FWIW the sweet spots for nice to use TM APIs are currently either lock elision, or compiler assisted TM (like __transaction* in gcc), or higher level libraries.

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

#14

Post by DSingularity »

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?

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

#16

Post by loeg »

andikleen2 wrote: post #11
loeg wrote: post #7

Earlier quoted context omitted.

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.)

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…

> 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.

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

#17

Post by htns »

0x0 wrote: post #3

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-instru...

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/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".

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

#18

Post by bonzini »

loeg wrote: post #16
andikleen2 wrote: post #11

Earlier quoted context omitted.

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…

> 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 ig…

A bad page fault might arise just from reading a partially-updated data structure. For example you could write two locations in one thread and read them in another. If the read side assumes that "location 1 nonzero" implies "location 2 nonzero", and then dereferences location 2, an inconsistent read would cause such a bad page fault. The only correct way to handle this is to abort the transaction.

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

#19

Post by bonzini »

loeg wrote: post #8
0x0 wrote: post #3

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-instru...

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.

Haswell Xeon E7 do not have the bug and they do enable TSC.

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

#20

Post by bonzini »

bcatanzaro wrote: post #15

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

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).
Post reply on HN