Date: Sun, 22 Jun 2014 00:18:52 +0100 From: Mindaugas Rasiukevicius <rmind@netbsd.org> To: Andrey Zonov <zont@FreeBSD.org> Cc: freebsd-arch@FreeBSD.org Subject: Re: PoC: passive serialization Message-ID: <20140621231853.394A914A2D0@mail.netbsd.org> In-Reply-To: <539FEBC1.5030501@FreeBSD.org> References: <539FEBC1.5030501@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Andrey Zonov <zont@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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20140621231853.394A914A2D0>