From owner-freebsd-arch@FreeBSD.ORG Sat Jun 21 23:18:55 2014 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 0E81B5B1; Sat, 21 Jun 2014 23:18:55 +0000 (UTC) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mail.netbsd.org", Issuer "Postmaster NetBSD.org" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id D63412D7A; Sat, 21 Jun 2014 23:18:54 +0000 (UTC) Received: from ws (localhost [IPv6:::1]) by mail.netbsd.org (Postfix) with SMTP id 394A914A2D0; Sat, 21 Jun 2014 23:18:53 +0000 (UTC) Date: Sun, 22 Jun 2014 00:18:52 +0100 From: Mindaugas Rasiukevicius To: Andrey Zonov Subject: Re: PoC: passive serialization In-Reply-To: <539FEBC1.5030501@FreeBSD.org> References: <539FEBC1.5030501@FreeBSD.org> X-Mailer: mail(1) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Message-Id: <20140621231853.394A914A2D0@mail.netbsd.org> Cc: freebsd-arch@FreeBSD.org X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 21 Jun 2014 23:18:55 -0000 Andrey Zonov 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