PoC: passive serialization

[Mindaugas Rasiukevicius]

Andrey Zonov <zont at FreeBSD.org> wrote:
> Hi,
> 
> I'd like to introduce my implementation of passive serialization [1]
> (RCU-like algorithm) which based on expired patent #4809168 [2].
> 
> This algorithm allows one to access data structures in non-blocking
> lock-less manner, but it is not just read-write lock alternative it is
> something different.  It is like delayed garbage collector or if you
> know what RCU is, passive serialization basically the same (RCU based on
> that).  Unlike NetBSD's implementation [3] my version is light-weight,
> with no additional locks.  One atomic operation per context switch is
> the only overhead.  To demonstrate how it works I converted process
> limits to use that mechanism [4].  There is also simple test [5] if you
> interested in measurements.  Just configure which type of lock do you
> want to use (mutex/rwlock/rmlock/psz), duration (LOOPS) and load
> (LENGTH) and run `make -s run' to get numbers.

Just a note on passive serialization in NetBSD: there is a lot of space for
optimisations, simplifications or improvements to that code, but it was a
deliberate choice to avoid them.  The goal was to carefully implement the
logic described in the expired patent (or at least attempt to be as close as
our interpretation skills allow us to be).  Any deviation from that logic
increases the risk of falling under some other technique, primarily RCU,
covered by other patent.

RCU is not a single patent.  It is a portfolio of multiple patents covering
various aspects of RCU.  Some of the original RCU patents have expired or
lapsed (see 5,608,893; 5,727,209; 6,219,690; 6,886,162; 5,442,758 is still
unclear), however there are plenty of others covering optimisations or
variations of RCU (e.g. 8,055,860 and 8,706,706) as well as or particular
applications (e.g. 8,666,952).  More are being filled.  RCU-like techniques
are a patent minefield.

So, to clarify my point: be careful with simplifications.

-- 
Mindaugas