From owner-freebsd-arch@FreeBSD.ORG Tue Jun 17 07:18:37 2014 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id F3DC3EEB for ; Tue, 17 Jun 2014 07:18:36 +0000 (UTC) Received: from mail-pd0-f180.google.com (mail-pd0-f180.google.com [209.85.192.180]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id C5BFE2CF7 for ; Tue, 17 Jun 2014 07:18:36 +0000 (UTC) Received: by mail-pd0-f180.google.com with SMTP id fp1so1987832pdb.25 for ; Tue, 17 Jun 2014 00:18:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:message-id:date:from:user-agent :mime-version:to:subject:content-type; bh=zxOFt937E5uh0pCE53TaCy7LKEsnqJKgly3P7fIf9Ic=; b=Smj/XD2XuGL8Z7Cz9E5ZMWIrRFM9YPcp+KG6OVM3YGSqNfcDggNyUZkMUgXM7Mg3c6 kPndAItw+cBVPCUryGDUAZQi759HMKUlNwPTY7vlS2898if/jupduoOs0boQ/jXLD95p SWrcE1Y1T3lP87x3nGNnq7V/EQnhp1G/PWoO3++hMjJ5ucopQMZcjLs5+nuwe5MJpM7d aYxBWgE3g9JYHoNUYjTPG4xzlAtISPESMQVTaC+DIQLAS+PpX9Ue1fmuEkwMrq+M4dZX 40kG9VCNbWMF+r+k9MNScitMr/khA614TnRFL1F7HfNUJmw37WyYWRzwHsYQAA9mos5Z QeZg== X-Gm-Message-State: ALoCoQnz14+BArjcUh2F0ro6M4JyVRtNfB5V895zXkeUuiPT90avENSAK/OBkokSX/X3VvQ5p347 X-Received: by 10.68.193.193 with SMTP id hq1mr30061872pbc.107.1402989510498; Tue, 17 Jun 2014 00:18:30 -0700 (PDT) Received: from zont-osx.local (c-69-181-251-166.hsd1.ca.comcast.net. [69.181.251.166]) by mx.google.com with ESMTPSA id zx1sm22371055pbc.60.2014.06.17.00.18.29 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 17 Jun 2014 00:18:29 -0700 (PDT) Sender: Andrey Zonov Message-ID: <539FEBC1.5030501@FreeBSD.org> Date: Tue, 17 Jun 2014 00:18:25 -0700 From: Andrey Zonov User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:24.0) Gecko/20100101 Thunderbird/24.5.0 MIME-Version: 1.0 To: freebsd-arch@FreeBSD.org Subject: PoC: passive serialization X-Enigmail-Version: 1.6 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="9C79jEh6Nhnolpe5kdFQIWCAcqc6O1Pl4" 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: Tue, 17 Jun 2014 07:18:37 -0000 This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --9C79jEh6Nhnolpe5kdFQIWCAcqc6O1Pl4 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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. Any questions, comments or suggestions are welcome. [1] http://people.freebsd.org/~zont/patches/psz/0001-Implement-passive-serial= ization.patch [2] http://www.google.com/patents/US4809168 [3] http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/kern/subr_pserialize.c?rev=3D= 1.7&content-type=3Dtext/x-cvsweb-markup [4] http://people.freebsd.org/~zont/patches/psz/0002-Lock-less-limits.pat= ch [5] http://people.freebsd.org/~zont/patches/psz/lock_test/ --=20 Andrey Zonov --9C79jEh6Nhnolpe5kdFQIWCAcqc6O1Pl4 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG/MacGPG2 v2.0.22 (Darwin) Comment: GPGTools - http://gpgtools.org iQEcBAEBAgAGBQJTn+vEAAoJEBWLemxX/CvTD/0IAKF+iXe7dVrEyYiWDQD+P6Iu Fsa/W+eTVuql2/pQlSteIAgL0lR19uKi7OmUjneQU2jCARtm+KQSh9Kwvj1cx7Hq ULZWX1144Ihl5IrEhclcN9r4WlOLKxviG30c7PCgmysMwHhJahAul/5FpRehZ727 ip+Pd8cEdCDuW4szuyKtRWMBQ3wrCjsXdvWjxYF24VXyajhLUthLewfn2IcW4/LF 1n643CjAtmV6Pu+WCHlNP0LinfF0IqJnHtvzpml6Bs6Ah9P0K+Q/3PMmH1lQbqgI RF2yUwgL0v/22TBosZXG1UsyBM0pbXIu90ace59U/Y2gIA5Z7T7i02Fvr28Q8CI= =0XOP -----END PGP SIGNATURE----- --9C79jEh6Nhnolpe5kdFQIWCAcqc6O1Pl4--