Weekly Edition
Return to the Development page
| ||||||||||||||||||||||
|
| ||||||||||||||||||||||
User space RCU library relicensed to LGPLv2.1
I hereby announce the relicensing of the userspace RCU (liburcu) library to LGPLv2.1. liburcu is a LGPLv2.1 userspace RCU (read-copy-update) library. This data synchronization library provides read-side access which scales linearly with the number of cores. It does so by allowing multiples copies of a given data structure to live at the same time, and by monitoring the data structure accesses to detect grace periods after which memory reclamation is possible. Website : http://lttng.org/?q=node/18 Gitweb interface : http://www.lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git The library is available for download in this git repository : git clone git://lttng.org/userspace-rcu.git It currently supports x86 and powerpc. LGPL-compatible low-level primitive headers will be required for other architectures. Note that the build system is at best rudimentary at the moment. Many thanks to IBM for allowing the RCU code to be released under LGPL license. This will allow much broader use of RCU synchronization. License details are available in the LICENSE file of the userspace-rcu tree. Mathieu -- Mathieu Desnoyers OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68 (Log in to post comments)
User space RCU library relicensed to LGPLv2.1 Posted May 14, 2009 19:28 UTC (Thu) by cma (subscriber, #49905) [Link] Any useful examples? What's for?
User space RCU library relicensed to LGPLv2.1 Posted May 14, 2009 19:55 UTC (Thu) by nix (subscriber, #2304) [Link]
It's for making multithreaded apps more comprehensible and scalable by
avoiding or reducing the need for locking horrors.
User space RCU library relicensed to LGPLv2.1 Posted May 14, 2009 20:27 UTC (Thu) by dtlin (✭ supporter ✭, #36537) [Link] Are you wondering why RCU is useful? As the Wikipedia page on rwlocks touches on, rwlocks are a solution to the readers- writers problem, but with concurrently-running readers and writer, one or the other is forced to wait. seqlocks help in the sense that neither readers nor a writer need to wait, but the readers have to loop and re-test in case a writer has updated data while the reader was doing work. RCU eliminates that case, as it allows readers to use a consistent, though possibly older, version of the shared data while other readers and a writer can go on using and creating newer versions. RCU has been quite useful in the Linux kernel; I imagine it would also be useful for any concurrent, scalable applications in userspace.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 8:48 UTC (Fri) by simlo (subscriber, #10866) [Link]
If you write code in a language with a garbage collector (which in principle could scale well over many CPUs...) you don't need it because GC is a superset of RCU, but in C it is usefull as a kind of primitive, manual garbage collector.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 14:39 UTC (Fri) by clugstj (subscriber, #4020) [Link]
Huh? I don't think garbage collection is the same thing as a mutex.
User space RCU library relicensed to LGPLv2.1 Posted May 16, 2009 14:09 UTC (Sat) by compudj (subscriber, #43335) [Link]
You are right, GC and mutex is not the same thing, but you are making wrong connexions here :
- mutex is a kind of synchronization primitive.
- RCU is another kind of synchronization primitive.
- RCU is a subset of garbage collection, because it is based on keeping a copy of the old data alive after an update. The synchronization implies discovering when all readers cannot hold any reference to this data (a grace period has to be waited for), and only then the updater is allowed to free or re-use the old data, given it does not have any public reference anymore.
But ! mutex is not a subset of garbage collection, because it uses an explicit exclusion of other critical section access, which implies sharing a variable (the "mutex") with other cores, which permits to update the data structure in-place (without copy), but this does not scale well when the number of cores increases, due to cache-line bouncing caused by exchanging the mutex variable (same applies for reader-writer locks, because readers exclude writers).
You might want to have a look at this paper for more explanation :
What is RCU, Fundamentally? http://lwn.net/Articles/262464/
Mathieu
User space RCU library relicensed to LGPLv2.1 Posted May 16, 2009 7:09 UTC (Sat) by butlerm (subscriber, #13312) [Link]
Pigs will fly before garbage collection is used in a real world kernel
User space RCU library relicensed to LGPLv2.1 Posted May 16, 2009 13:42 UTC (Sat) by nix (subscriber, #2304) [Link]
AF_UNIX sockets have always required garbage collection (admittedly to
handle a corner case involving sending fds and especially AF_UNIX sockets endpoints over other AF_UNIX sockets which are then closed), but if you don't handle it you get a trivial DoS): see net/unix/garbage.c. Also routes and dst cache entries get GCed periodically.
drivers/ieee1394/dv1394.c also contains a really simple GC.
NFS's lock manager GCs its list of hosts periodically.
fs/jffs2/gc.c contains a GC (more generally, *any* log-structured
Time to get strapping wings to those pigs...
User space RCU library relicensed to LGPLv2.1 Posted May 16, 2009 22:45 UTC (Sat) by sergey (guest, #31763) [Link]
Are all these really GC implementations? That is, do they all detect that an item previously used cannot be used anymore (i.e. is unreachable) and get rid of it? Or are they just caches with eviction policies?
User space RCU library relicensed to LGPLv2.1 Posted May 16, 2009 23:29 UTC (Sat) by nix (subscriber, #2304) [Link]
I don't know about all of them, but the AF_UNIX one is a full-blown
mark-sweep collector. The log-structured FS collectors are real garbage collectors, too, but the entities that are being collected don't correspond to allocated memory blocks (but rather *disk* blocks), so maybe that's not quite the same thing.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 3:25 UTC (Fri) by kjp (subscriber, #39639) [Link]
As nice as RCU is, it's pretty sad it was patentable. It seems quite similar to oracle's row multiversioning which has been around for ages and is really slick for concurrency.
I hate software patents.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 5:58 UTC (Fri) by jengelh (subscriber, #33263) [Link]
Only in the US ... ;-)
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 7:49 UTC (Fri) by trasz (guest, #45786) [Link]
By the way, RCU is an interesting example of what really the IBM's patent policy is - it's ok for them
to give away patents that are useless, but they have no intentions of giving away any patents - including software patents - they could actually use to successfully sue their competitors.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 14:42 UTC (Fri) by clugstj (subscriber, #4020) [Link]
You have facts, I assume, to back up your accusation?
User space RCU library relicensed to LGPLv2.1 Posted May 17, 2009 8:31 UTC (Sun) by trasz (guest, #45786) [Link]
IBM is holding full rights for the RCU patent. If they were against software patents, they would e.g.
pass it to some 3rd party, such as Linux Foundation - or just give away the patent.
User space RCU library relicensed to LGPLv2.1 Posted May 21, 2009 12:27 UTC (Thu) by addw (guest, #1771) [Link]
You don't understand why companies like IBM hold patents. It is generally NOT to sue someone who might have infringed, but as a defense if someone sues them -- You sue us and we will sue you -- a variant of the cold war MAD (Mutually Assured Destruction).
If IBM gave them away they would not be able to use them for MAD. As far as FLOSS is concerned they have done the next best thing -- a promise not to use against GPL s/ware.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 10:01 UTC (Fri) by gozdal (guest, #58595) [Link]
When I read the articles about RCU I had the impression it is viable only in kernel-space - when you have the insider scheduler information when threads holding references to data are rescheduled and by definition they do not own those references anymore. Am I wrong? If I am correct how liburcu deals with this problem?
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 13:38 UTC (Fri) by nevets (subscriber, #11875) [Link]
Yes you are wrong ;-)
You can do RCU with having scheduling be your grace period, but that is not mandatory. With scheduling, all you need to do for an RCU effect is to disable preemption in the read sections and then when you need to make sure all readers are no longer referencing the data you are about to write, you just need to do a synchronize scheduler (wait for all CPUs to schedule).
But that is the "big hammer" to RCU. The kernel now has "preemptable RCU", where a task may schedule while holding an RCU lock. Thus, waiting for all schedules is not good enough, and is very similar to what is needed in userspace.
I have yet to look at Mathieu's code, but it probably has some kind of counters when taking the rcu read lock. The trick is to have some mechanism to detect a grace period. The grace period is when all current holders of an rcu read lock release their locks. New takers of the RCU lock only affect the next grace period.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 19:23 UTC (Fri) by rks (guest, #55908) [Link]
but isn't the point of RCU to avoid read locks?
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 19:34 UTC (Fri) by nevets (subscriber, #11875) [Link]
The difference between an RCU read lock and a normal read lock is that RCU read locks do not block (like an rwlock), nor does it need to repeat (like a seq_lock). An RCU read lock can be thought more of a "marker" than a lock. It just marks code that must finish before another grace period can pass.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 21:02 UTC (Fri) by ikm (subscriber, #493) [Link]
Patenting this is ludicrous. And sad at the same time. Patents were made to protect things like complex formulas for chemical substances which have had a lot of time, effort and money invested in it to be found right, working, tested, complying to a multitude of factors etc. But now we're patenting simple ideas. As simple as 'build something privately, make everything ready, then atomically unveil it to general public/users'. Wow. The world has known this approach long before there were any computers at all. What a novelty.
User space RCU library relicensed to LGPLv2.1 Posted May 15, 2009 22:03 UTC (Fri) by nevets (subscriber, #11875) [Link]
First, I hate software patents tremendously. And I'm not too thrilled about other types of patents (although it helped that dude with the intermittent windshield wipers)
But RCU is much more complex than 'build something privately, make everything ready, then atomically unveil it to general public/users'. Actually it is the opposite. You have something public, you want to remove it, but you need to wait for all users to finish with it. Usually we have rwlocks for such a purpose, but that does not scale well with SMP (cache line bouncing).
What RCU allows is to make what is public, hidden from the world. But we need to wait until those that already know about it, to finish with it. Then we can write or free it.
Mainframe coupling facility is more interesting and relevant than RCU for application concurrency/performance improvement Posted May 18, 2009 5:48 UTC (Mon) by dayan (guest, #58635) [Link]
I find it interesting that RCU generates such interest when IBM has a superior technology and approach used in mainframes, particularly in the context of zOS and/or TPF operating system environments.
The 'coupling facility', as IBM calls it, is a mainframe processor engine with special microcode that implements list, cache, and lock structures which can be used by mainframes linked together by high speed optical fiber links specific to the coupling facility architecture. Applications must be specially written to take advantage of these shared structures. Examples of applications under zOS which do this are ADABAS, DB2, IMS, and CICS.
Interestingly enough, there are applications probably more familiar to the general computing population which essentially implement the coupling facility approach. SAP's SAPDB/MAXDB has a mode of operation known as LiveCache which is used to improve the Advanced Planning and Optimizing component by providing a shared cache structure used by multiple distributed application instances. Oracle's TimesTen product implements a means by which applications can do synchronization through shared structures similar to the coupling facility.
The point is that RCU is a fraction of the capacity and ability of one of IBM's most prized and useful multiprocessor performance enhancement tools. Perhaps one day the coupling facility will join the open source realm.
Mainframe coupling facility is more interesting and relevant than RCU for application concurrency/performance improvement Posted May 21, 2009 21:35 UTC (Thu) by vonbrand (subscriber, #4458) [Link] Being able to lock stuff over a high-speed network is a bit different than not having to lock working in the same memory...
|
|
|||||||||||||||||||||