▲ 58 points
back
38 comments
That's a cool GC algorithm, but it has two big drawbacks:
1. It works well only if the number of GCed data structures -- i.e. the number of entry/exit points -- is relatively small (in this case, just the method cache).
2. It prevents inlining of the data structure's access functions, which adds quite a bit of overhead to each access (though not as much as two fenced CASes).
It can, however, be very useful for hot code swapping (provided there's no inlining or you have a JIT that can un-inline).
I think the way to look at this is more of as a synchronization technique as opposed to a general-purpose GC algorithm.
I don't understand the objection about inlining--could you explain? You could in principle not use function boundaries to delimit the critical section: a range of PC addresses within a function would do just as well.
> a range of PC addresses within a function would do just as well
Yes, but you'll need to know where those ranges are (i.e. you'll need some feedback from the compiler), and then be very careful that no tool injects any instructions into, or moves code around your executable/library.
Fascinating. I had never considered sending signals to stop all threads and check their PCs as a synchronization technique. But it works, and it brings down the uncontended lock acquisition and release time down to zero in the case where no synchronization needs to be performed.
Now I'm trying to think of other places to use this trick. :)
It isn't actually stopping the threads. The thing to understand is that you don't need to ensure that all threads are outside of a critical section at the time you free the cache, what you need is the weaker guarantee that all threads have to have exited any critical sections they were in at the time of the pointer swap before you can call free.
You don't have to do anything heavy weight like stop all the threads, instead you can just pull their PCs out and check them. Sure, they may have moved on (and even back into the critical section) by the time you call free, but it doesn't matter because they'll be using the new cache buffer. The downside is that you might get false positives for the critical section, but you can either run the dealloc in a loop or defer it and try again later.
No, you pretty much have to stop them. If you observe the PC of other threads at a point in time while they are running, that is no guarantee that they aren't about to enter the unsafe region immediately after you make the check.
Your suggestion sounds akin to replacing a mutex acquire with an "is the lock held?" [like trylock with 0 timeout, then immediate release]. Observing that it's unheld at time t makes no guarantee it won't be held by the time of your next instruction. It therefore becomes a meaningless check, not useful at all for real synchronization.
[PS: mentioned this on HN before, but my favorite "observe the PC as part of a synchronization primitive" hack was this one from Linux on armv5: http://lwn.net/Articles/314561/]
[PPS: How much does objc_msgSend() do inline and how much is external calls? This PC hack seems like it could have huge holes if some of its critical work is done in a non-inlined function.]
Hmm? No I don't think you have to stop them.
Basically you have:
cache = <newval>
if ok() {
free(<oldval>)
}
// maybe someone here gets a reference to <oldval> (1)
cache = <newval>
// from this point onward no one can reference <oldval>
if ok() {
free(<oldval>)
}
Imagine ok() pauses all threads. It sees if any threads threads are in BAD=[PC_BAD_START, PC_BAD_END]. If yes, return false, if no, return true.
Now imagine PC doesn't pause the threads. What can happen?
A thread that was in BAD leaves BAD. That's fine.
A thread that wasn't in BAD enters BAD. But that will use <newval>, so that's fine too.
That thread that was in BAD leaves BAD, and then reenters. That's also fine.
So there's no problem.
(re your question, I believe objc_msgSend is hand optimized assembly that doesn't make any function calls; if it did, you'd just have to make sure to include those functions in the range of bad PC addresses.)
> So ok() only has to check if threads have a reference to <oldval> that they are still using.
Right. The problem with doing this while other threads are running is that ok() can return true, correctly so for its point in time, then immediately after ok() returns another thread could enter objc_msgSend() while you are inside free(). Maybe ok() ran on thread A while thread B was right at unrelated function foo()'s "call objc_msgSend" instruction. The check is OK at a point in time, but perhaps by the time you enter free() thread B did an unsafe read.
> A thread that wasn't in BAD enters BAD. But that will use <newval>, so that's fine too.
You can't make guarantees that it will see newval. Whether or not it does depends on timing. For example, maybe the guy who calls ok() gets a page fault or is on a very busy CPU with lots of preemption happening. That will alter timing in the direction of this being unsafe. Cache coherence may also be an issue here.
You have to be atomically reading and writing cache (which you can do). So then after
cache = <newval>
That's what makes the trick work w/o having to pause threads.
> cache = <newval>
As written, that is not a guarantee that all cores will see <newval> immediately. It's very CPU-specific but you may need memory fences to achieve this.
Further, in my opinion it's kind of playing with fire.
Edit: Also, it is my impression reading the article that <oldval> is actually a shared list of old caches to be freed (gOldCachesList). That makes it a lot more complicated than your example snippet and leaves more potential for nasty synchronization problems.
How do you get the PC of a thread in a POSIX userland without sending it a signal? ptrace(PTRACE_GETREGS), I guess?
Totally platform specific. On OS X you generally use thread_get_state().
Clozure CL and I believe SBCL do this in their GCs to allow threads to be stopped for GC preemptively while dealing with sequences that must be atomic (like allocation). Clozure calls it PC lusering: http://ccl.clozure.com/manual/chapter17.1.html
It's a take on kernel-mode RCU.
Yes, this essentially just a form of RCU. Note however that RCU isn't just for the kernel anymore though: http://urcu.so/
Concurrency Kit (http://concurrencykit.org) also has ck_epoch. Performance comparison to the URCU implementations available at http://concurrencykit.org/presentations/ebr.pdf
Userspace RCU algorithms are experimental, quite brittle, and/or have little in common with RCU. They're certainly not usable as a production-ready scalable synchronization solution.
What makes you say this?
RCU refers to a wide array of reclamation implementations and some URCU implementations do indeed have a lot in common with kernel-space RCU (which also has a myriad of implementations).
Speaking of liburcu in specific, the "brittleness" is a function of your workload and your selection of the URCU implementation. The various implementations have different trade-offs, and it is definitely possible to livelock write-side or degrade read-side if you make the wrong design decisions. For example, there are major differences between signal-based URCU and QSBR URCU. No reclamation mechanism (whether one backed by RCU or something like hazard pointers) is a silver bullet and each will suck in fantastic ways with the right workload.
As far as userspace RCU algorithms in general being "experimental", plenty of people are using RCU or RCU-like mechanisms in user-space for production systems as a scalable synchronization solution. For example, the Concurrency Kit library (http://concurrencykit.org) has an RCU-like system called ck_epoch, and it sees at least billions of transactions in production a day without fail, and even supports freestanding environments.
I haven't actually used it myself and am certainly willing to believe it's immature, but how do you mean it has "little in common with RCU"? Comparing personnel between that library and this set of people --> https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.... there's certainly at least some authorship in common...
RCU basically works by having a critical section only within which a reader may access the data structure. To know when to GC the old copy of the data, you wait until all readers leave the critical section. If you're in the kernel, this can be very efficient: you disable all interrupts within the CS, so you know a thread is never preempted while in it. This means that no matter how many threads there are, only those currently running on the available cores (say, there are 8 of them) can be in the CS, so no matter how many threads there are, you only need to wait for 8, and you know that that waiting period is going to be short because there are no interrupts.
So the efficiency of the algorithms stems from disabling interrupts within the reader's critical section, which can only be done in kernel mode (otherwise you could do really bad things). A similar algorithm in userspace will need to find another mechanism to wait for all readers to exit the CS, which may or may not be efficient. They may share then name "RCU", but not its desirable qualities.
There are, AFAIK, several different algorithms calling themselves userspace RCU. One userspace RCU algorithm I've seen essentially protects the deallocation with a read-write, which isn't known for terrific scalability, but I don't know, they may have come up with something better.
Garbage collection is the Achille's heel of all nonblocking data structures. As far as I know, there is no algorithm more efficient than a general purpose GC just yet, which is both generally applicable and efficient.
Common authorship, BTW, says little. Most concurrent algorithms out there were invented by a handful of people.
1) Efficiency of algorithms stems from disabling interrupts
The efficiency stems from having little to zero synchronization cost for readers in a read-mostly workload or workload that just isn't update-intensive. In addition to that, note that a deferral interface is available so writers basically never have to block until it is actually safe to free memory. URCU and ck_epoch all share those desirable qualities.
2) "RCU algorithm I've seen ... protects with a read-write"
The synchronize portion of RCU and RCU-like systems is almost always heavy-weight. Applications that adopt URCU can typically afford this.
3) "no algorithm more efficient than a general purpose GC"
All the blocking schemes are magnitudes more efficient but the trade-off is that it isn't generally applicable. However, they're still applicable for plenty of workloads. We are starting to see more GC mechanisms adopt SMR-like techniques so that may change.
4) "Common authorship, BTW, says little"
Not in this case.
If you would like to learn more about the performance trade-off with the various mechanisms, I suggest http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf and the URCU paper as a start. I've some additional numbers on something similar at http://concurrencykit.org/presentations/ebr.pdf
Paul also has a good introduction up at https://queue.acm.org/detail.cfm?id=2488549