Compare and Swap with PMDK

[Anirudh Narayanan]

Hi, 

Does PMDK have compare and swap operation support, similar to the DRAM CAS. If so how does it scale in performance?

[Jonathan Halliday]

The CPU's CAS instructions operate against L1 cache lines and don't care if those lines are backed by DRAM or pmem DIMMs.

Jonathan

[代栋]

Hi, Jonathan,

What happens if we apply CAS on a PMEM address? CAS might still be correct regarding exclusive access, but Is it possible that a power failure after CAS may cause the swapped data lost?

- Dong

On Sep 20, 2019, at 4:59 AM, Jonathan Halliday <goo...@the-transcend.com> wrote:



--
You received this message because you are subscribed to the Google Groups "pmem" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pmem+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pmem/cd58b270-04cc-40f4-b0c2-0a341d0f236d%40googlegroups.com.

[Jonathan Halliday]

Yes. That's the problem I mentioned in another thread - L1 line changes, CAS or otherwise, can become visible to other processes before they are persisted, at which point that other process can act on the updated value and persist its own updates, still before the original update is itself persisted. If you want locking that isolates the new value until its persisted, you need to build that yourself in software. The CAS hardware won't help you there. CAS is only giving you atomic change, not atomic change+persist. AFAIK the PMDK doesn't expose a primitive for that either - it's tricky to enforce without hardware or O/S support.

Jonathan

On Saturday, September 21, 2019 at 1:03:29 AM UTC+1, Dong Dai wrote:

Hi, Jonathan,

What happens if we apply CAS on a PMEM address? CAS might still be correct regarding exclusive access, but Is it possible that a power failure after CAS may cause the swapped data lost?

- Dong

On Sep 20, 2019, at 4:59 AM, Jonathan Halliday <goo...@the-transcend.com> wrote:



The CPU's CAS instructions operate against L1 cache lines and don't care if those lines are backed by DRAM or pmem DIMMs.

Jonathan

On Thursday, September 19, 2019 at 10:08:16 PM UTC+1, Anirudh Narayanan wrote:

Hi, 

Does PMDK have compare and swap operation support, similar to the DRAM CAS. If so how does it scale in performance?

--
You received this message because you are subscribed to the Google Groups "pmem" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pm...@googlegroups.com.

[Anatole Lefort]

Le samedi 21 septembre 2019 10:31:40 UTC+2, Jonathan Halliday a écrit :

Yes. That's the problem I mentioned in another thread - L1 line changes, CAS or otherwise, can become visible to other processes before they are persisted, at which point that other process can act on the updated value and persist its own updates, still before the original update is itself persisted. If you want locking that isolates the new value until its persisted, you need to build that yourself in software.

CLWB documentation got me to think that atomic instructions (any lock prefixed instruction actually) were also acting as store barriers, thus were sequentially ordered among other CLWBs ; wouldn't it mean hw CAS would always reach the persistency domain before subsequent memory updates acting on the updated CAS value ?

Anatole

[Andy Rudoff]

Hi Anatole,

CLWB documentation got me to think that atomic instructions (any lock prefixed instruction actually) were also acting as store barriers, thus were sequentially ordered among other CLWBs ; wouldn't it mean hw CAS would always reach the persistency domain before subsequent memory updates acting on the updated CAS value ?

While it is true that "serializing" instructions, like LOCK CMPXCHG will act like a fence, it won't act like a flush+fence which is what you need for a store barrier.  Since there's no "compare-and-swap-and-flush" atomic instruction, the CMPXCHG only provides atomicity with respect to visibility, not persistence.  Future systems that provide persistent CPU caches will make visibility and persistence the same thing, so LOCK CMPXCHG will work as expected even on pmem on those systems.

I've seem some code use flushes before each LOCK CMPXCHG to create the logic: If the CMPXCHG succeeds, I know the previous value was persistent and hasn't changed since I read it.  This, coupled with a flush+fence after the LOCK CMPXCHG might meet the needs of some non-blocking algorithms, but I have to say I think the code is difficult to write, maintain, and not as useful as it may seem.  Here's why I say that:

Imagine a non-blocking algorithm for adding a node to a linked list in DRAM.  The algorithm allocates the new node, fills it in, and then uses CAS operations to link it in without grabbing traditional mutex locks.  If the program crashes before the operation is complete, the memory allocated isn't a memory leak because it was all volatile and it goes back to the system when the program exits.

Now convert that algorithm to pmem.  Even with the most carefully coded non-blocking code, you will need to handle the memory allocation in a way that avoids a persistent memory leak if the program crashes.  Is it possible to do that with entirely non-blocking code?  Perhaps.  More likely you'd just use a transactional memory allocator like the one we have in libpmemobj.  It has been tuned and optimized for several years now and provide a high-performing, crash safe allocator.  But it uses transaction-style logic to do that (and other tricks like thread-local locks and caches to help it scale).  So if the algorithm already uses a transaction to create the new node, why not just link in the new node in under that transaction instead of creating a complex non-blocking code path?

Of course, I'm not trying to discourage you from working on non-blocking pmem code, I'm just pointing out that in many of the cases we looked at, where someone was converting a non-blocking algorithm to work with pmem, just switching the code to use transactions often turned out to be much easier and still performant.

We've talked a few times about adding a CAS operation to PMDK.  I'm still interested in hearing about specific use cases and I'm happy to see it get added if it makes sense.  So far, the demand for it really hasn't been there, but I'm keeping an open mind about it.

Thanks,

-andy

[Wei]

On Tuesday, September 24, 2019 at 2:26:06 PM UTC+1 Andy Rudoff wrote:

Hi Anatole,

CLWB documentation got me to think that atomic instructions (any lock prefixed instruction actually) were also acting as store barriers, thus were sequentially ordered among other CLWBs ; wouldn't it mean hw CAS would always reach the persistency domain before subsequent memory updates acting on the updated CAS value ?

While it is true that "serializing" instructions, like LOCK CMPXCHG will act like a fence, it won't act like a flush+fence which is what you need for a store barrier.  Since there's no "compare-and-swap-and-flush" atomic instruction, the CMPXCHG only provides atomicity with respect to visibility, not persistence.  Future systems that provide persistent CPU caches will make visibility and persistence the same thing, so LOCK CMPXCHG will work as expected even on pmem on those systems.

The 'persistent CPU caches' feature sounds great, but it's a micro-architectural feature, which means code written with the assumption in mind won't necessarily run on platforms without the persistent CPU caches. The other option as you mention is an architectural feature "compare-and-swap-and-flush", any code written with this feature in mind will be guaranteed to run across micro-architectural implementations. What's the rationale of having the micro-architectural support versus the architectural support? Thanks.

[Andy Rudoff]

Hi Wei,

Let's make sure we mean the same thing by "architectural" and "micro-architectural".  By my definition, a feature is architectural if it is a published part of the architecture, published in specifications (SDM, standards, etc) so that you know you can depend on the feature in your application.  A feature is micro-architectural if it requires knowledge about how the hardware is implemented that is not guaranteed to be true between different implementations.

On Intel systems, we've defined the architecture to support persistent CPU caches ever since we added the property to the ACPI spec a few years ago.  Applications which follow the persistent memory programming model will check this property and decide if instructions like CLWB are required to make a store to pmem persistent.  If your application correctly follows the programming model, it will work on machines with this feature and without this feature, it will just be faster when it encounters a machine where it can skip the CLWBs.  PMDK follows this model, so applications built on it will automatically benefit from persistent CPU caches.  There's no dependency on micro-architectural details as long as you follow the programming model.  We describe this in much more detail in the book (free on pmem.io) and I am also giving a talk about this topic at SDC this week if you're interested.

As to why Intel decided not to make a compare-and-swap-and-flush instruction, it was a costs versus benefit decision.  There are several academic papers showing it is possible to write non-blocking algorithms on pmem without a new instruction, and there are emerging pmem platforms where the existing instruction works as expected.  All the mechanisms are there for a program to check if CPU caches are persistent and choose the right CAS operation for that platform.

Thanks,

-andy

[Andy Rudoff]

>I am also giving a talk about this topic at SDC this week if you're interested

I meant *next* week at SDC:

https://www.snia.org/events/storage-developer

[steve]

Hi Andy,

I have spent quite a bit of time creating a minimal program that uses PMDK for persistence and works properly in the presence of power failures on
Ubuntu but loses data in the presence of power failures on Windows.

I have posted the program on this list with complete instructions on how to repro the issue and have gotten no response. Is there some way I can get
Intel to investigate this?

Thanks.
------------
Steve Heller

[Andy Rudoff]

Hi Steve,

I took a quick look at your program and I'll ask someone from the PMDK team to look at it further.  Can you confirm my quick reading of the code: your makefile seems to be linking with libpmemobj but the code you sent is only using libpmem.  In other words, you are only using PMDK to flush caches, but not for transactions.  Instead, I think you are creating your own transactions and that's what is not working on Windows.  Please let me know if I'm understanding the code correctly.

Thanks,

-andy

p.s.  I recommend starting new topics in their own thread, not replying in unrelated threads since that will bury your topic under another one.  Replying to an existing thread and editing the Subject can do the wrong thing.

[steve]

On Mon, 14 Sep 2020 06:52:44 -0700 (PDT), Andy Rudoff <an...@rudoff.com> wrote:

>Hi Steve,
>
>I took a quick look at your program and I'll ask someone from the PMDK team
>to look at it further. Can you confirm my quick reading of the code: your
>makefile seems to be linking with libpmemobj but the code you sent is only
>using libpmem. In other words, you are only using PMDK to flush caches,
>but not for transactions. Instead, I think you are creating your own
>transactions and that's what is not working on Windows. Please let me know
>if I'm understanding the code correctly.

Correct, I'm doing my own transactions, and that's what isn't working on Windows.
Thanks!

>Thanks,
>
>-andy
>
>p.s. I recommend starting new topics in their own thread, not replying in
>unrelated threads since that will bury your topic under another one.
>Replying to an existing thread and editing the Subject can do the wrong
>thing.

I read the group posts in my email, not on googlegroups, so I don't see that issue.
Should I just post to pm...@googlegroups.com with a new subject, as I did with this message, or do I need to do something else?
------------
Steve Heller

[Andy Rudoff]

Thanks Steve.  Another quick question: can you change the program to verify is_pmem is true?  If you don't get back is_pmem, you cannot use userspace flushing.

Thanks.

On the posting thing, I'm not 100% sure why your messages are getting threaded under existing topics.  My guess is it is the difference between creating a new email message to the address and starting from a reply to an existing message, but that was just a guess.