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

Restartable Sequences

justine.lol

Post reply on HN
Print view View original

51–60 of 82 posts

Re: Restartable Sequences

#51

Post by yubblegum »

mota7 wrote: post #46
yubblegum wrote: post #38

Earlier quoted context omitted.

Let's try this again: OP > The issue is this will likely go just as slow if not slower. The mere act of sharing the same 64-byte region of memory (a.k.a. cacheline) between multiple cores, causes the CPU internally to basically use a mutex, and chances are the CPU's internal mutexes aren't as good as the ones you've implemented in userspace. The claim by OP is that "chances are" that userspace mutexes are better than…

If you have two threads on different cores that write to the same cacheline, the CPU has to enforce write ordering. The way it does this is for one of the cores to acquire a write lock on the cacheline. The actual implementation of this is via some variant of the MESI protocol that results in the cacheline on one core going to an Exclusive state, while copies of the cacheline on every other core becomes Invalid. MESI…

Thank you.

Re: Restartable Sequences

#52

Post by Taniwha »

yubblegum wrote: post #38
khuey wrote: post #35

Earlier quoted context omitted.

The "CPU mutex" is just the cache coherency mechanism. If you shard your data to avoid triggering it as suggested, then yes, it's much faster. EDIT: or maybe you're asking if introducing an explicit userspace mutex is better than a lockless algorithm with false sharing issues. The answer is that it's workload dependent but it definitely can be.

Let's try this again: OP > The issue is this will likely go just as slow if not slower. The mere act of sharing the same 64-byte region of memory (a.k.a. cacheline) between multiple cores, causes the CPU internally to basically use a mutex, and chances are the CPU's internal mutexes aren't as good as the ones you've implemented in userspace. The claim by OP is that "chances are" that userspace mutexes are better than…

The cache coherency protocols that sit between the CPUs and DRAM always essentially "use a mutex": when a cpu wants to write it broadcasts to all the other CPUs and either gets the latest copy from whoever wrote it last and shoots down any read-only copies in other CPUs or reads it from DRAM (or converts a read only copy to be writeable)

This happens on every memory access, so the thing you want to avoid is ping ponging writeable cache lines between CPUs (especially before you have a chance to actually write it) - LL/SC instructions sit on top of these protocols and allow instructions to tell is a cache line had been "stolen" before you have a chance to write it

Re: Restartable Sequences

#53

Post by wmf »

senderista wrote: post #11

I'm surprised there was no reference to the librseq library, maintained by the rseq implementer: https://github.com/compudj/librseq This has helpers for common use cases like counters and linked lists. You shouldn't need to write assembly at all to use rseq in most applications.

Justine is writing her own libc and her own malloc so I'm not surprised she wants to use rseq from scratch.

Re: Restartable Sequences

#54

Post by jstimpfle »

GlenTheMachine wrote: post #3

If you had no idea what a restorable sequence is the takeaway is about halfway down the OP: “This is why Linux now provides rseq() which is a much more enlightened solution. With restartable sequences, you actually can get rid of both the mutex and atomics, while the OS continues to fully abstract scheduling. The way it works is you advise the kernel whenever your program enters a critical section of code that you do…

I think it wasn't explained in a very accessible way. If I got the gist right, this essentially brings "per-CPU" synchronization to userland. It's typical in the kernel to have per-cpu data, while per-thread data is rare and typically impractical. There is a high number of threads managed by the kernel, most of which probably belong to a userland process, most of which do not participate in any given synchronisation scheme. Also threads are often too much of an abstraction for parallel programming needs, given that they are hiding for example cache effects. So it's natural to want to use per-cpu data instead of thread_local data in a userland process, I know I've been wishing for that many times.

With rseq, we can allocate in any userland process one instance of a given synchronisation data structure per each CPU. It's important to understand that userland code accessing per-cpu data structures cannot prevent being scheduled away from a CPU and being replaced by another thread (kernel code can block scheduler for short critical sections). Such a replacement thread may subsequently corrupt that same data that was still in the middle of the transaction. But we can make a subset of transactions safe at least: If a transaction gets committed in a single (final) atomic instruction, and we get kernel support for this transaction to be restarted in case there has been a schedule mid-way, this is a guarantee that at the time of commit, the entire transaction hasn't been interrupted by the scheduler. I.e. a kind of "mutual exclusion" guarantee.

Did I get that right?

Re: Restartable Sequences

#55

Post by squirrellous »

IIUC rseq is similar to thread-local data with the additional benefit that it scales with number of CPU cores, not threads. However if you are an application developer and is able to control all the threads in an application, then rseq isn’t that superior.

I fully agree that rseq should be more easily available to Linux developers, though.

Re: Restartable Sequences

#56

Post by senderista »

wmf wrote: post #53
senderista wrote: post #11

I'm surprised there was no reference to the librseq library, maintained by the rseq implementer: https://github.com/compudj/librseq This has helpers for common use cases like counters and linked lists. You shouldn't need to write assembly at all to use rseq in most applications.

Justine is writing her own libc and her own malloc so I'm not surprised she wants to use rseq from scratch.

That's fine, but I think an article claiming to give an introduction to a technology should at least mention that an essential library exists, and that writing assembly is no longer usually required.

Re: Restartable Sequences

#58

Post by smasher164 »

I was having a conversation with someone recently if RSEQ would be a good primitive to build a load-link/store-conditional implementation in user-space. It gives you a critical window, though you still have to deal with spurious restarts, and provide a way for one core to abort another.

Re: Restartable Sequences

#59

Post by dividuum »

senderista wrote: post #11

I'm surprised there was no reference to the librseq library, maintained by the rseq implementer: https://github.com/compudj/librseq This has helpers for common use cases like counters and linked lists. You shouldn't need to write assembly at all to use rseq in most applications.

I'm took a brief look and left confused. The list implementation seems completely bog standard with no special code for synchronization whatsoever. I don't see any counter and the rseq syscall seems unused except for feature detection. I don't think that's a viable replacement for any low level code.

Re: Restartable Sequences

#60

Post by zestyping »

bryanlarsen wrote: post #42
crote wrote: post #27

Earlier quoted context omitted.

> it's a sequence of instructions that either runs to completion atomically or doesn't The way I read it, it either runs to completion in one go, or gets restarted from the beginning. This means the sequence as a whole isn't executed atomically, as the already-executed instructions during an interrupt aren't rolled back. It can be used to build atomic actions, but it is up to the developer to create a sequence of ins…

Yes, it's either atomic or the last instruction is guaranteed not to have run. I made this a little harder to read by inserting another clause in the sentence.

[dead]
Post reply on HN