From owner-freebsd-arch@FreeBSD.ORG Mon Jan 5 10:33:36 2009 Return-Path: Delivered-To: arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 93203106564A; Mon, 5 Jan 2009 10:33:36 +0000 (UTC) (envelope-from des@des.no) Received: from tim.des.no (tim.des.no [194.63.250.121]) by mx1.freebsd.org (Postfix) with ESMTP id 4F8328FC0C; Mon, 5 Jan 2009 10:33:36 +0000 (UTC) (envelope-from des@des.no) Received: from ds4.des.no (des.no [84.49.246.2]) by smtp.des.no (Postfix) with ESMTP id 975FD6D44C; Mon, 5 Jan 2009 10:33:35 +0000 (UTC) Received: by ds4.des.no (Postfix, from userid 1001) id 74E7E844F2; Mon, 5 Jan 2009 11:33:35 +0100 (CET) From: =?utf-8?Q?Dag-Erling_Sm=C3=B8rgrav?= To: "M. Warner Losh" References: <26259E4E-6E26-4DAE-8046-80C7C46B7CD5@gmail.com> <20081227.193308.255407637.imp@bsdimp.com> <86r63p5334.fsf@ds4.des.no> <20081231.233644.1974810120.imp@bsdimp.com> Date: Mon, 05 Jan 2009 11:33:35 +0100 In-Reply-To: <20081231.233644.1974810120.imp@bsdimp.com> (M. Warner Losh's message of "Wed, 31 Dec 2008 23:36:44 -0700 (MST)") Message-ID: <86eizim48w.fsf@ds4.des.no> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.60 (berkeley-unix) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Cc: yanefbsd@gmail.com, bz@freebsd.org, arch@freebsd.org Subject: Re: svn commit: r186519 - head X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 05 Jan 2009 10:33:36 -0000 "M. Warner Losh" writes: > I just tried this, and it doesn't work for me. I didn't say it was sufficient, just that it was necessary. You need an OpenPAM patch as well (r418), but I can't commit it independently of the build system changes. I believe I posted the patch in an earlier discussion. DES --=20 Dag-Erling Sm=C3=B8rgrav - des@des.no From owner-freebsd-arch@FreeBSD.ORG Mon Jan 5 11:06:49 2009 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 1B021106564A for ; Mon, 5 Jan 2009 11:06:49 +0000 (UTC) (envelope-from owner-bugmaster@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:4f8:fff6::28]) by mx1.freebsd.org (Postfix) with ESMTP id E352F8FC20 for ; Mon, 5 Jan 2009 11:06:48 +0000 (UTC) (envelope-from owner-bugmaster@FreeBSD.org) Received: from freefall.freebsd.org (localhost [127.0.0.1]) by freefall.freebsd.org (8.14.3/8.14.3) with ESMTP id n05B6mkg002721 for ; Mon, 5 Jan 2009 11:06:48 GMT (envelope-from owner-bugmaster@FreeBSD.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.3/8.14.3/Submit) id n05B6mMO002717 for freebsd-arch@FreeBSD.org; Mon, 5 Jan 2009 11:06:48 GMT (envelope-from owner-bugmaster@FreeBSD.org) Date: Mon, 5 Jan 2009 11:06:48 GMT Message-Id: <200901051106.n05B6mMO002717@freefall.freebsd.org> X-Authentication-Warning: freefall.freebsd.org: gnats set sender to owner-bugmaster@FreeBSD.org using -f From: FreeBSD bugmaster To: freebsd-arch@FreeBSD.org Cc: Subject: Current problem reports assigned to freebsd-arch@FreeBSD.org X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 05 Jan 2009 11:06:49 -0000 Note: to view an individual PR, use: http://www.freebsd.org/cgi/query-pr.cgi?pr=(number). The following is a listing of current problems submitted by FreeBSD users. These represent problem reports covering all versions including experimental development code and obsolete releases. S Tracker Resp. Description -------------------------------------------------------------------------------- o kern/120749 arch [request] Suggest upping the default kern.ps_arg_cache 1 problem total. From owner-freebsd-arch@FreeBSD.ORG Tue Jan 6 12:25:03 2009 Return-Path: Delivered-To: arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id CCCE5106564A for ; Tue, 6 Jan 2009 12:25:03 +0000 (UTC) (envelope-from luigi@onelab2.iet.unipi.it) Received: from onelab2.iet.unipi.it (onelab2.iet.unipi.it [131.114.9.129]) by mx1.freebsd.org (Postfix) with ESMTP id 8F7738FC0C for ; Tue, 6 Jan 2009 12:25:03 +0000 (UTC) (envelope-from luigi@onelab2.iet.unipi.it) Received: by onelab2.iet.unipi.it (Postfix, from userid 275) id C99677309E; Tue, 6 Jan 2009 13:10:29 +0100 (CET) Date: Tue, 6 Jan 2009 13:10:29 +0100 From: Luigi Rizzo To: arch@freebsd.org Message-ID: <20090106121029.GA83861@onelab2.iet.unipi.it> References: <200812262231.mBQMVjHC052150@svn.freebsd.org> <867i59lvbj.fsf@ds4.des.no> <20090105142929.GA70683@onelab2.iet.unipi.it> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.4.2.3i Cc: des@des.no, Hartmut.Brandt@dlr.de Subject: RFC: adding > and >= to /usr/bin/make conditionals ? X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 06 Jan 2009 12:25:04 -0000 [not sure what is the proper forum for discussing this...] I recently realised (and documented in the manpage) that /usr/bin/make only implements == and != when comparing strings in coditionals, yet it would be totally trivial to add support for > >= < <= as well, because the underlying code already uses strcmp(), and according to Harti (message attached below) there are no restrictions from the standards point of view. There is some value in having this feature, e.g. when comparing package names to find out which one is more recent, etc.; on the other hand, if we add (and start using) this feature, our Makefiles might become harder to reuse on other platforms (e.g. other BSDs, OSX ports) which use the same 'make' program. So, I am polling to see if there is any consensus for or against adding this feature to /usr/bin/make cheers luigi [excerpt from Harti's message explaining the relation with standards] On Mon, Jan 05, 2009 at 05:40:33PM +0100, Hartmut.Brandt@dlr.de wrote: ... > >From the Posix standpoint of view, we can do what we want as long as we > are not syntax compatible with posix-make :-) This is the reason, why > most of our make extensions are compatible with posix. As soon as you > have a construct that is a syntax error according to the Posix > specification you invoke implementation-defined behaviour and as such > you just have to document it. There are several of these escape > mechanisms in the standard: the .POSIX pseudo-target and all targets > that start with a dot and consist of uppercase letters. > > With regard to conditionals: there is no standard. Posix decided to > standard only minimal make, which is roughly compatible to V7 make. If > you change things like conditional semantics you should: (1) document > it, and (2) arrange a full ports build with the portcluster people. This > takes some days, but is a good thing to do. > > harti From owner-freebsd-arch@FreeBSD.ORG Tue Jan 6 19:54:39 2009 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 33F60106574E for ; Tue, 6 Jan 2009 19:54:39 +0000 (UTC) (envelope-from nwhitehorn@freebsd.org) Received: from mail.icecube.wisc.edu (trout.icecube.wisc.edu [128.104.255.119]) by mx1.freebsd.org (Postfix) with ESMTP id 7387B8FC19 for ; Tue, 6 Jan 2009 19:54:37 +0000 (UTC) (envelope-from nwhitehorn@freebsd.org) Received: from localhost (localhost.localdomain [127.0.0.1]) by mail.icecube.wisc.edu (Postfix) with ESMTP id D85CE5823A; Tue, 6 Jan 2009 13:24:31 -0600 (CST) X-Virus-Scanned: amavisd-new at icecube.wisc.edu Received: from mail.icecube.wisc.edu ([127.0.0.1]) by localhost (trout.icecube.wisc.edu [127.0.0.1]) (amavisd-new, port 10030) with ESMTP id AgUHkTUCG6Iz; Tue, 6 Jan 2009 13:24:31 -0600 (CST) Received: from wanderer.tachypleus.net (i3-dhcp-172-16-223-165.icecube.wisc.edu [172.16.223.165]) by mail.icecube.wisc.edu (Postfix) with ESMTP id 9EF0E5823D; Tue, 6 Jan 2009 13:24:31 -0600 (CST) Message-ID: <4963AFE3.5080607@freebsd.org> Date: Tue, 06 Jan 2009 13:24:19 -0600 From: Nathan Whitehorn User-Agent: Thunderbird 2.0.0.19 (X11/20090105) MIME-Version: 1.0 To: "M. Warner Losh" References: <4929C6D8.7090305@freebsd.org> <20081123.170854.-626772149.imp@bsdimp.com> <492AC8DE.6050902@freebsd.org> <20081124.105800.-267230932.imp@bsdimp.com> In-Reply-To: <20081124.105800.-267230932.imp@bsdimp.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Cc: freebsd-arch@FreeBSD.org Subject: Re: Enumerable I2C busses X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 06 Jan 2009 19:54:43 -0000 M. Warner Losh wrote: > In message: <492AC8DE.6050902@freebsd.org> > Nathan Whitehorn writes: > : M. Warner Losh wrote: > : > In message: <4929C6D8.7090305@freebsd.org> > : > Nathan Whitehorn writes: > : > : Rafał Jaworowski wrote: > : > : > > : > : > On 2008-11-23, at 19:18, Dag-Erling Smørgrav wrote: > : > : > > : > : >> Nathan Whitehorn writes: > : > : >>> The current I2C bus mechanism does not support the bus adding its own > : > : >>> children [...] > : > : >> > : > : >> That's because the I2C protocol does not support device enumeration or > : > : >> identification. You have to know in advance what kind of devices are > : > : >> attached and at what address. Even worse, it is not uncommon for > : > : >> similar but not entirely compatible devices to use the same I2C address > : > : >> (for instance, every I2C-capable RTC chip uses the same address, even > : > : >> though they have different feature sets) > : > : > > : > : > Well, hard-coded addresses and conflicting assignments between vendors > : > : > do not technically prevent from scanning the bus; actually, our current > : > : > iicbus code can do bus scaning when compiled with a diag define. The > : > : > problem however is some slave devices are not well-behaved, and they > : > : > don't like to be read/written to other than in very specific scenario: > : > : > if polled during bus scan strange effects occur e.g. they disappear from > : > : > the bus, or do not react to consecutive requests etc. > : > : > : > : All of this is true, but perhaps my question was badly worded. What I am > : > : trying to figure out is how to shove information from an out-of-band > : > : source (Open Firmware, in this case) into newbus without disrupting > : > : existing code. In that way, my question is not I2C specific -- we run > : > : into the same issue with the Open Firmware nexus node and pseudo-devices > : > : like cryptosoft that attach themselves. > : > > : > You are looking at the problem incorrectly. In newbus, a case like > : > this the i2c bus should be a subclass (say i2c_of) that is derived > : > from the normal i2c bus stuff, but replaces the hints insertion of > : > devices with OF enumeration of devices. The OF higher levels will > : > already know to attach this kind of i2c bus to certain i2c > : > controllers, or always on certain platforms. > : > : Yes, this is exactly what I wanted to do, like how ofw_pci works. > : > : > : What I want to do is to have the I2C bus add the children that the > : > : firmware says it has. What the firmware cannot tell in advance, however, > : > : is which FreeBSD driver is responsible for those devices, and so the I2C > : > : bus driver can't know that without a translation table that I would > : > : prefer not to hack in to the bus driver. > : > > : > This is the bigger problem. Today, we are stuck with a lame table > : > that will translate the OF provided properties into FreeBSD driver > : > names. > : > : At the moment, I don't believe Apple uses any of the current very small > : number of I2C device drivers in tree. So I may skip the table for the > : time being, assuming the hack below is OK. In future, this may change, > : since G5 systems require software thermal control. But that will be the > : subject of another mail to this list... > : > : > : It seems reasonable to allow devices to use a real probe routine to look > : > : at the firmware's name and compatible properties, like we allow on other > : > : Open Firmware busses. The trouble is that existing drivers don't do > : > : this, because they expect to be attached with hints, so they will attach > : > : to all devices. I'm trying to figure out how to avoid this. > : > : > : > : My basic question comes down to whether there is a good way in newbus to > : > : handle busses that may be wholly or partially enumerated by firmware or > : > : some other method, and may also have devices that can only attach > : > : themselves if told to by hints. > : > > : > Yes. This is a bit of a problem. The problem is that the existing > : > hints mechanism combines device tree and driver tree into one, and in > : > such a scenario, we wind up with the problem that you have. > : > > : > One could make the probe routines return BUS_PROBE_GENERIC, and that > : > would help somewhat. One could also have the probe routine check to > : > see if a specific driver is assigned to the device or not. That would > : > also help, but does mean changing all the i2c bus attached drivers in > : > the tree. > : > : I think changing existing I2C drivers may be unavoidable. Would there be > : any objection to changing the MI iicbus drivers to return > : BUS_PROBE_NOWILDCARD in their probe routines? It seems to have been > : introduced (by you) to solve more or less exactly this problem. By my > : count, the relevant files are: > : dev/iicbus/ds133x.c > : dev/iicbus/icee.c > : dev/iicbus/ad7418.c > : dev/iicbus/iicsmb.c > : dev/iicbus/ds1672.c > : dev/iicbus/if_ic.c > : dev/iicbus/iic.c > : > : I would also like to change iicbus_probe to return -1000 like > : dev/pci/pci.c to allow it to be overridden by a subclass. Please let me > : know if this is a terrible idea or if I have forgotten any I2C device > : drivers. > > Short term, this is the right fix. There was an objection, I think by > Marcel, to this approach. However, his objections were part of a > larger set of objections and I think that we're working to solve > those. > > Warner > This is now in the tree. Now for part 2, which I had not considered previously: connecting the I2C bus layer to the I2C host adapters. Right now, we have the following: kiic/other i2c adapters ---iicbus ---ofw_iicbus Since kiic provides an Open Firmware node, ofw_iicbus gets priority, attaches, and everything after that is wonderful. The issue is how best to attach the iicbus modules to kiic. Current I2C controllers contain a line like this: DRIVER_MODULE(iicbus, me, iicbus_driver, iicbus_devclass, 0, 0); This explicitly specifies that you want the standard driver, so we need additional glue to allow the ofw_iicbus driver to attach. One solution is that each relevant host adapter can add an additional DRIVER_MODULE line with the ofw_iicbus driver and class, which would have to exported in a header somewhere. This is pretty ugly. Another solution is for the ofw_iicbus module to grow a list of the names of interesting adapters. This is worse. The third option is to do what we do for pci, where all PCI adapters are named 'pcib'. So we could make new I2C host adapters named 'iichb' or something, and then move the DRIVER_MODULE logic for new code into the bus modules, as is done for PCI. This decreases the amount of information in the device names, but seems a bit cleaner. Thoughts? -Nathan From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 02:26:45 2009 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id AFAAC106564A for ; Fri, 9 Jan 2009 02:26:45 +0000 (UTC) (envelope-from delphij@delphij.net) Received: from tarsier.delphij.net (delphij-pt.tunnel.tserv2.fmt.ipv6.he.net [IPv6:2001:470:1f03:2c9::2]) by mx1.freebsd.org (Postfix) with ESMTP id E895F8FC0C for ; Fri, 9 Jan 2009 02:26:44 +0000 (UTC) (envelope-from delphij@delphij.net) Received: from tarsier.geekcn.org (tarsier.geekcn.org [211.166.10.233]) (using TLSv1 with cipher ADH-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by tarsier.delphij.net (Postfix) with ESMTPS id 8AA8C28448 for ; Fri, 9 Jan 2009 10:26:43 +0800 (CST) Received: from localhost (tarsier.geekcn.org [211.166.10.233]) by tarsier.geekcn.org (Postfix) with ESMTP id D6B99EB2DD5; Fri, 9 Jan 2009 10:26:42 +0800 (CST) X-Virus-Scanned: amavisd-new at geekcn.org Received: from tarsier.geekcn.org ([211.166.10.233]) by localhost (mail.geekcn.org [211.166.10.233]) (amavisd-new, port 10024) with ESMTP id 2bZpjbr7zqet; Fri, 9 Jan 2009 10:26:36 +0800 (CST) Received: from charlie.delphij.net (adsl-76-237-33-62.dsl.pltn13.sbcglobal.net [76.237.33.62]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by tarsier.geekcn.org (Postfix) with ESMTPSA id ECE8DEB08E1; Fri, 9 Jan 2009 10:26:33 +0800 (CST) DomainKey-Signature: a=rsa-sha1; s=default; d=delphij.net; c=nofws; q=dns; h=message-id:date:from:reply-to:organization:user-agent: mime-version:to:subject:x-enigmail-version:openpgp:content-type; b=M0aun9tzJRNn/DoBF/Rf8+qJ10+S98TW/bCcTWW7rtUAqaXYF/s//h2K+O7Zs1yR/ qpLxBw0XdlNSru24KH65g== Message-ID: <4966B5D4.7040709@delphij.net> Date: Thu, 08 Jan 2009 18:26:28 -0800 From: Xin LI Organization: The FreeBSD Project User-Agent: Thunderbird 2.0.0.18 (X11/20081125) MIME-Version: 1.0 To: freebsd-arch@FreeBSD.org X-Enigmail-Version: 0.95.7 OpenPGP: id=18EDEBA0; url=http://www.delphij.net/delphij.asc Content-Type: multipart/mixed; boundary="------------060709020407050306010500" Cc: Subject: RFC: MI strlen() X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: d@delphij.net List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 02:26:46 -0000 This is a multi-part message in MIME format. --------------060709020407050306010500 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, Here is a new implementation of strlen() which employed the bitmask skill in order to achieve better performance on modern hardware. For common case, this would be a 5.2x boost on FreeBSD/amd64. The code is intended for MI use when there is no hand-optimized assembly. http://people.freebsd.org/~delphij/for_review/strlen.diff Note that this version of strlen() has suboptimal performance if there are a lot of characters that has their highest bit set (we can change it to have uniform performance at the expense of about ~30% performance penalty). Comments? Cheers, - -- Xin LI http://www.delphij.net/ FreeBSD - The Power to Serve! -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.9 (FreeBSD) iEYEARECAAYFAklmtdQACgkQi+vbBBjt66CltACfY1j+JJnn3PDLOmO1uOpMkMlg 94gAn3v9eSExj84hcNYEI0AhLGWBCxMj =xzFJ -----END PGP SIGNATURE----- --------------060709020407050306010500 Content-Type: text/plain; name="strlen.diff" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="strlen.diff" Index: strlen.c =================================================================== --- strlen.c (revision 186910) +++ strlen.c (working copy) @@ -1,6 +1,6 @@ /*- - * Copyright (c) 1990, 1993 - * The Regents of the University of California. All rights reserved. + * Copyright (c) 2009 Xin LI + * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -10,14 +10,11 @@ * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) @@ -27,21 +24,93 @@ * SUCH DAMAGE. */ -#if defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)strlen.c 8.1 (Berkeley) 6/4/93"; -#endif /* LIBC_SCCS and not lint */ #include __FBSDID("$FreeBSD$"); +#include +#include #include +#ifndef CTASSERT +#define CTASSERT(x) _CTASSERT(x, __LINE__) +#define _CTASSERT(x, y) __CTASSERT(x, y) +#define __CTASSERT(x, y) typedef char __assert_ ## y [(x) ? 1 : -1] +#endif + +CTASSERT(LONG_BIT == 32 || LONG_BIT == 64); + +/* + * Portable strlen() for 32-bit and 64-bit systems. + * + * Rationale: it is generally much more efficient to do word length + * operations and avoid branches on modern computer systems, as + * compared to byte-length operations with a lot of branches. + * + * The expression: + * + * ((x - 0x01....01) & ~x & 0x80....80) + * + * would evaluate to a non-zero value iff any of the bytes in the + * original word is zero. However, we can further reduce ~1/3 of + * time if we consider that strlen() usually operate on 7-bit ASCII + * by employing the following expression, which allows false positive + * when high bit of 1 and use the tail case to catch these case: + * + * ((x - 0x01....01) & 0x80....80) + * + * This is more than 5.2 times as compared to the raw implementation + * on Intel T7300 under EM64T mode. + */ + +/* Magic numbers for the algorithm */ +#if LONG_BIT == 32 +static const unsigned long mask01 = 0x01010101; +static const unsigned long mask80 = 0x80808080; +#elif LONG_BIT == 64 +static const unsigned long mask01 = 0x0101010101010101; +static const unsigned long mask80 = 0x8080808080808080; +#endif + +#define LONGPTR_MASK (sizeof(long) - 1) + +/* + * Helper macro to return string length if we caught the zero + * byte. + */ +#define testbyte(x) \ + do { \ + if (p[x] == '\0') \ + return (p - str + x); \ + } while (0); + size_t -strlen(str) - const char *str; +strlen(const char *str) { - const char *s; + const char *p; + const unsigned long *lp; - for (s = str; *s; ++s); - return(s - str); + /* Skip the first few bytes until we have an aligned p */ + for (p = str; (uintptr_t)p & LONGPTR_MASK; ++p) + if (*p == 0) + return (p - str); + + /* Scan the rest of the string using word sized operation */ + for (lp = (const unsigned long *)p; ; lp++) + if ((*lp - mask01) & mask80) { + p = (const char *)(lp); + testbyte(0); + testbyte(1); + testbyte(2); + testbyte(3); +#if (LONG_BIT >= 64) + testbyte(4); + testbyte(5); + testbyte(6); + testbyte(7); +#endif + } + + /* NOTREACHED */ + return 0; } --------------060709020407050306010500-- From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 04:26:43 2009 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 01C56106566B; Fri, 9 Jan 2009 04:26:43 +0000 (UTC) (envelope-from delphij@delphij.net) Received: from tarsier.delphij.net (delphij-pt.tunnel.tserv2.fmt.ipv6.he.net [IPv6:2001:470:1f03:2c9::2]) by mx1.freebsd.org (Postfix) with ESMTP id 9BD8C8FC12; Fri, 9 Jan 2009 04:26:42 +0000 (UTC) (envelope-from delphij@delphij.net) Received: from tarsier.geekcn.org (tarsier.geekcn.org [211.166.10.233]) (using TLSv1 with cipher ADH-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by tarsier.delphij.net (Postfix) with ESMTPS id 8BA2B28449; Fri, 9 Jan 2009 12:26:41 +0800 (CST) Received: from localhost (tarsier.geekcn.org [211.166.10.233]) by tarsier.geekcn.org (Postfix) with ESMTP id 0EE71EC24E2; Fri, 9 Jan 2009 12:26:41 +0800 (CST) X-Virus-Scanned: amavisd-new at geekcn.org Received: from tarsier.geekcn.org ([211.166.10.233]) by localhost (mail.geekcn.org [211.166.10.233]) (amavisd-new, port 10024) with ESMTP id jKR-gSeRfu9I; Fri, 9 Jan 2009 12:26:36 +0800 (CST) Received: from charlie.delphij.net (c-67-188-86-134.hsd1.ca.comcast.net [67.188.86.134]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by tarsier.geekcn.org (Postfix) with ESMTPSA id 246EFEC225E; Fri, 9 Jan 2009 12:26:34 +0800 (CST) DomainKey-Signature: a=rsa-sha1; s=default; d=delphij.net; c=nofws; q=dns; h=message-id:date:from:reply-to:organization:user-agent: mime-version:to:cc:subject:references:in-reply-to: x-enigmail-version:openpgp:content-type:content-transfer-encoding; b=C9912rRCaArUDyZYUdmihYETouClDKlSYcqZuJx5UN0C6WnwpI1kdHbvJ5iGCbkrY cYWCzsMHaPuREHHkuqT6w== Message-ID: <4966D1F7.1040105@delphij.net> Date: Thu, 08 Jan 2009 20:26:31 -0800 From: Xin LI Organization: The FreeBSD Project User-Agent: Thunderbird 2.0.0.18 (X11/20081125) MIME-Version: 1.0 To: "Sean C. Farley" References: <4966B5D4.7040709@delphij.net> In-Reply-To: X-Enigmail-Version: 0.95.7 OpenPGP: id=18EDEBA0; url=http://www.delphij.net/delphij.asc Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Cc: d@delphij.net, freebsd-arch@FreeBSD.org Subject: Re: RFC: MI strlen() X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: d@delphij.net List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 04:26:43 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, Sean, Sean C. Farley wrote: > On Thu, 8 Jan 2009, Xin LI wrote: > >> Hi, >> >> Here is a new implementation of strlen() which employed the bitmask >> skill in order to achieve better performance on modern hardware. For >> common case, this would be a 5.2x boost on FreeBSD/amd64. The code is >> intended for MI use when there is no hand-optimized assembly. >> >> http://people.freebsd.org/~delphij/for_review/strlen.diff >> >> Note that this version of strlen() has suboptimal performance if there >> are a lot of characters that has their highest bit set (we can change >> it to have uniform performance at the expense of about ~30% >> performance penalty). >> >> Comments? > > I only glanced over it, but I like the idea about having it. > > I see that you investigated this before[1]? Amusingly, I did something Yes, but nothing gets committed :-/ I think I had lost that work due to a hard disk failure. > similar two years later[2] with a C version of strlen()[3]. :) > > Out of curiosity, is an assert (i.e., CTASSERT) better than an #error? Hmm... I did not thought about it, but looking at your code, it seems that using #error makes it more obvious. I have put the revised version at: http://people.freebsd.org/~delphij/for_review/strlen-r1.diff For those who wants to see the file instead of the diff: http://people.freebsd.org/~delphij/for_review/strlen.c Cheers, - -- Xin LI http://www.delphij.net/ FreeBSD - The Power to Serve! -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.9 (FreeBSD) iEYEARECAAYFAklm0fcACgkQi+vbBBjt66DWMgCePfKWpIzThVYBRd41lJ3t85KU UrUAoLyiCnnLBBgWk2YbevkZcxHI6XQy =Qhk+ -----END PGP SIGNATURE----- From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 04:42:26 2009 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id D8AE9106566C for ; Fri, 9 Jan 2009 04:42:26 +0000 (UTC) (envelope-from bright@elvis.mu.org) Received: from elvis.mu.org (elvis.mu.org [192.203.228.196]) by mx1.freebsd.org (Postfix) with ESMTP id C96AC8FC12 for ; Fri, 9 Jan 2009 04:42:26 +0000 (UTC) (envelope-from bright@elvis.mu.org) Received: by elvis.mu.org (Postfix, from userid 1192) id 642241A3C3A; Thu, 8 Jan 2009 20:25:57 -0800 (PST) Date: Thu, 8 Jan 2009 20:25:57 -0800 From: Alfred Perlstein To: d@delphij.net Message-ID: <20090109042557.GH60686@elvis.mu.org> References: <4966B5D4.7040709@delphij.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4966B5D4.7040709@delphij.net> User-Agent: Mutt/1.4.2.3i Cc: freebsd-arch@FreeBSD.org Subject: Re: RFC: MI strlen() X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 04:42:27 -0000 * Xin LI [090108 18:27] wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > Hi, > > Here is a new implementation of strlen() which employed the bitmask > skill in order to achieve better performance on modern hardware. For > common case, this would be a 5.2x boost on FreeBSD/amd64. The code is > intended for MI use when there is no hand-optimized assembly. > > http://people.freebsd.org/~delphij/for_review/strlen.diff > > Note that this version of strlen() has suboptimal performance if there > are a lot of characters that has their highest bit set (we can change it > to have uniform performance at the expense of about ~30% performance > penalty). > > Comments? It's pretty cool, what does valgrind say when you walk past the end of a string, can it figure that out? > > Cheers, > - -- > Xin LI http://www.delphij.net/ > FreeBSD - The Power to Serve! > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v2.0.9 (FreeBSD) > > iEYEARECAAYFAklmtdQACgkQi+vbBBjt66CltACfY1j+JJnn3PDLOmO1uOpMkMlg > 94gAn3v9eSExj84hcNYEI0AhLGWBCxMj > =xzFJ > -----END PGP SIGNATURE----- > Index: strlen.c > =================================================================== > --- strlen.c (revision 186910) > +++ strlen.c (working copy) > @@ -1,6 +1,6 @@ > /*- > - * Copyright (c) 1990, 1993 > - * The Regents of the University of California. All rights reserved. > + * Copyright (c) 2009 Xin LI > + * All rights reserved. > * > * Redistribution and use in source and binary forms, with or without > * modification, are permitted provided that the following conditions > @@ -10,14 +10,11 @@ > * 2. Redistributions in binary form must reproduce the above copyright > * notice, this list of conditions and the following disclaimer in the > * documentation and/or other materials provided with the distribution. > - * 4. Neither the name of the University nor the names of its contributors > - * may be used to endorse or promote products derived from this software > - * without specific prior written permission. > * > - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND > + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND > * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE > * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE > - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE > + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE > * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL > * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS > * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) > @@ -27,21 +24,93 @@ > * SUCH DAMAGE. > */ > > -#if defined(LIBC_SCCS) && !defined(lint) > -static char sccsid[] = "@(#)strlen.c 8.1 (Berkeley) 6/4/93"; > -#endif /* LIBC_SCCS and not lint */ > #include > __FBSDID("$FreeBSD$"); > > +#include > +#include > #include > > +#ifndef CTASSERT > +#define CTASSERT(x) _CTASSERT(x, __LINE__) > +#define _CTASSERT(x, y) __CTASSERT(x, y) > +#define __CTASSERT(x, y) typedef char __assert_ ## y [(x) ? 1 : -1] > +#endif > + > +CTASSERT(LONG_BIT == 32 || LONG_BIT == 64); > + > +/* > + * Portable strlen() for 32-bit and 64-bit systems. > + * > + * Rationale: it is generally much more efficient to do word length > + * operations and avoid branches on modern computer systems, as > + * compared to byte-length operations with a lot of branches. > + * > + * The expression: > + * > + * ((x - 0x01....01) & ~x & 0x80....80) > + * > + * would evaluate to a non-zero value iff any of the bytes in the > + * original word is zero. However, we can further reduce ~1/3 of > + * time if we consider that strlen() usually operate on 7-bit ASCII > + * by employing the following expression, which allows false positive > + * when high bit of 1 and use the tail case to catch these case: > + * > + * ((x - 0x01....01) & 0x80....80) > + * > + * This is more than 5.2 times as compared to the raw implementation > + * on Intel T7300 under EM64T mode. > + */ > + > +/* Magic numbers for the algorithm */ > +#if LONG_BIT == 32 > +static const unsigned long mask01 = 0x01010101; > +static const unsigned long mask80 = 0x80808080; > +#elif LONG_BIT == 64 > +static const unsigned long mask01 = 0x0101010101010101; > +static const unsigned long mask80 = 0x8080808080808080; > +#endif > + > +#define LONGPTR_MASK (sizeof(long) - 1) > + > +/* > + * Helper macro to return string length if we caught the zero > + * byte. > + */ > +#define testbyte(x) \ > + do { \ > + if (p[x] == '\0') \ > + return (p - str + x); \ > + } while (0); > + > size_t > -strlen(str) > - const char *str; > +strlen(const char *str) > { > - const char *s; > + const char *p; > + const unsigned long *lp; > > - for (s = str; *s; ++s); > - return(s - str); > + /* Skip the first few bytes until we have an aligned p */ > + for (p = str; (uintptr_t)p & LONGPTR_MASK; ++p) > + if (*p == 0) > + return (p - str); > + > + /* Scan the rest of the string using word sized operation */ > + for (lp = (const unsigned long *)p; ; lp++) > + if ((*lp - mask01) & mask80) { > + p = (const char *)(lp); > + testbyte(0); > + testbyte(1); > + testbyte(2); > + testbyte(3); > +#if (LONG_BIT >= 64) > + testbyte(4); > + testbyte(5); > + testbyte(6); > + testbyte(7); > +#endif > + } > + > + /* NOTREACHED */ > + return 0; > } > > _______________________________________________ > freebsd-arch@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-arch > To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org" -- - Alfred Perlstein From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 04:43:56 2009 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id C196D106566C for ; Fri, 9 Jan 2009 04:43:56 +0000 (UTC) (envelope-from scf@FreeBSD.org) Received: from mail.farley.org (farley.org [67.64.95.201]) by mx1.freebsd.org (Postfix) with ESMTP id 8C4F18FC0C for ; Fri, 9 Jan 2009 04:43:56 +0000 (UTC) (envelope-from scf@FreeBSD.org) Received: from [192.168.1.204] (baba.farley.org [192.168.1.204]) by mail.farley.org (8.14.3/8.14.3) with ESMTP id n0944UYO026420; Thu, 8 Jan 2009 22:04:30 -0600 (CST) (envelope-from scf@FreeBSD.org) Date: Thu, 8 Jan 2009 22:04:30 -0600 (CST) From: "Sean C. Farley" To: d@delphij.net In-Reply-To: <4966B5D4.7040709@delphij.net> Message-ID: References: <4966B5D4.7040709@delphij.net> User-Agent: Alpine 2.00 (BSF 1167 2008-08-23) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII X-Spam-Status: No, score=-4.4 required=3.0 tests=ALL_TRUSTED,BAYES_00 autolearn=ham version=3.2.5 X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on mail.farley.org Cc: freebsd-arch@FreeBSD.org Subject: Re: RFC: MI strlen() X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 04:43:57 -0000 On Thu, 8 Jan 2009, Xin LI wrote: > Hi, > > Here is a new implementation of strlen() which employed the bitmask > skill in order to achieve better performance on modern hardware. For > common case, this would be a 5.2x boost on FreeBSD/amd64. The code is > intended for MI use when there is no hand-optimized assembly. > > http://people.freebsd.org/~delphij/for_review/strlen.diff > > Note that this version of strlen() has suboptimal performance if there > are a lot of characters that has their highest bit set (we can change > it to have uniform performance at the expense of about ~30% > performance penalty). > > Comments? I only glanced over it, but I like the idea about having it. I see that you investigated this before[1]? Amusingly, I did something similar two years later[2] with a C version of strlen()[3]. :) Out of curiosity, is an assert (i.e., CTASSERT) better than an #error? Sean 1. http://lists.freebsd.org/mailman/htdig/freebsd-arch/2005-August/004076.html 2. http://lists.freebsd.org/pipermail/freebsd-arch/2007-July/006636.html 3. http://www.farley.org/freebsd/tmp/strlen/strlen.c -- scf@FreeBSD.org From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 05:01:03 2009 Return-Path: Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 11523106566B; Fri, 9 Jan 2009 05:01:03 +0000 (UTC) (envelope-from delphij@delphij.net) Received: from tarsier.delphij.net (delphij-pt.tunnel.tserv2.fmt.ipv6.he.net [IPv6:2001:470:1f03:2c9::2]) by mx1.freebsd.org (Postfix) with ESMTP id AB85C8FC0A; Fri, 9 Jan 2009 05:01:02 +0000 (UTC) (envelope-from delphij@delphij.net) Received: from tarsier.geekcn.org (tarsier.geekcn.org [211.166.10.233]) (using TLSv1 with cipher ADH-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by tarsier.delphij.net (Postfix) with ESMTPS id 5FB9028459; Fri, 9 Jan 2009 13:01:01 +0800 (CST) Received: from localhost (tarsier.geekcn.org [211.166.10.233]) by tarsier.geekcn.org (Postfix) with ESMTP id 19D18EC25B8; Fri, 9 Jan 2009 13:01:01 +0800 (CST) X-Virus-Scanned: amavisd-new at geekcn.org Received: from tarsier.geekcn.org ([211.166.10.233]) by localhost (mail.geekcn.org [211.166.10.233]) (amavisd-new, port 10024) with ESMTP id i0wGNyDolD5P; Fri, 9 Jan 2009 13:00:56 +0800 (CST) Received: from charlie.delphij.net (c-67-188-86-134.hsd1.ca.comcast.net [67.188.86.134]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by tarsier.geekcn.org (Postfix) with ESMTPSA id 78CEDEB3FAB; Fri, 9 Jan 2009 13:00:54 +0800 (CST) DomainKey-Signature: a=rsa-sha1; s=default; d=delphij.net; c=nofws; q=dns; h=message-id:date:from:reply-to:organization:user-agent: mime-version:to:cc:subject:references:in-reply-to: x-enigmail-version:openpgp:content-type:content-transfer-encoding; b=PyRuaEA2vWiE7t9fygbazzyUcOlC6Q5wxLYYopkjp0DAvb8oLu0gBEGj9AEFhznQc VJawheBminvvExO1e6ZWw== Message-ID: <4966DA02.6060508@delphij.net> Date: Thu, 08 Jan 2009 21:00:50 -0800 From: Xin LI Organization: The FreeBSD Project User-Agent: Thunderbird 2.0.0.18 (X11/20081125) MIME-Version: 1.0 To: Alfred Perlstein References: <4966B5D4.7040709@delphij.net> <20090109042557.GH60686@elvis.mu.org> In-Reply-To: <20090109042557.GH60686@elvis.mu.org> X-Enigmail-Version: 0.95.7 OpenPGP: id=18EDEBA0; url=http://www.delphij.net/delphij.asc Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Cc: d@delphij.net, freebsd-arch@FreeBSD.org Subject: Re: RFC: MI strlen() X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: d@delphij.net List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 05:01:03 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Alfred Perlstein wrote: > * Xin LI [090108 18:27] wrote: > Hi, > > Here is a new implementation of strlen() which employed the bitmask > skill in order to achieve better performance on modern hardware. For > common case, this would be a 5.2x boost on FreeBSD/amd64. The code is > intended for MI use when there is no hand-optimized assembly. > > http://people.freebsd.org/~delphij/for_review/strlen.diff > > Note that this version of strlen() has suboptimal performance if there > are a lot of characters that has their highest bit set (we can change it > to have uniform performance at the expense of about ~30% performance > penalty). > > Comments? > >> It's pretty cool, what does valgrind say when you walk past >> the end of a string, can it figure that out? I don't have a runnable valgrind at hand so can't say about it :( This type of walk past should not cause problem though, as page is always word aligned and it does not do more speculative read than the old strlen() implementation (read past a word vs read past a byte against the page when overrun happen). Cheers, - -- Xin LI http://www.delphij.net/ FreeBSD - The Power to Serve! -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.9 (FreeBSD) iEYEARECAAYFAklm2gAACgkQi+vbBBjt66C0KACfctSU8/o2ciuu79XYZ21G0VRY qC0AoIeC/cKp1bHJqxNsVr391BBvzyK9 =kxFV -----END PGP SIGNATURE----- From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 13:04:10 2009 Return-Path: Delivered-To: arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 697801065670 for ; Fri, 9 Jan 2009 13:04:10 +0000 (UTC) (envelope-from luigi@onelab2.iet.unipi.it) Received: from onelab2.iet.unipi.it (onelab2.iet.unipi.it [131.114.9.129]) by mx1.freebsd.org (Postfix) with ESMTP id 301828FC13 for ; Fri, 9 Jan 2009 13:04:09 +0000 (UTC) (envelope-from luigi@onelab2.iet.unipi.it) Received: by onelab2.iet.unipi.it (Postfix, from userid 275) id 0141D7309E; Fri, 9 Jan 2009 14:09:12 +0100 (CET) Date: Fri, 9 Jan 2009 14:09:11 +0100 From: Luigi Rizzo To: arch@freebsd.org Message-ID: <20090109130911.GA17017@onelab2.iet.unipi.it> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.3i Cc: fabio@gandalf.sssup.it Subject: tagging disk requests (geom-related) X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 13:04:10 -0000 Hi, together with Fabio Checconi we are working on some disk schedulers using a geom class. One of the things we have is to do is tag requests (struct bio) with the identity of the thread issuing the request (or some other classification information, but which one is irrelevant here). We cannot do the tagging when we reach our geom class because at this point we have lost the thread information (curthread is "g_down" at this point). So there are two issues here: 1) where to store the tag, 2) who does the tagging. (Background for non geom-aware people: each request is identified by a 'struct bio' (BIO); when moving from a GEOM class to the next one downstream, a BIO is cloned and possibly split (e.g., to do slicing, RAID, or simply breaking up large requests) and each child BIO has a pointer to the parent BIO, so overall they are connected in a tree even though more frequently there is just a linear chain.) For #1, to avoid adding a field to 'struct bio', we store the tag in the bio_caller1 field (if available) of the root element of the BIO tree, bio_caller1 is normally unused (except by ZFS), and we say it is available if it contains NULL. For the reasons stated above, we cannot store the mark in the BIO associated to our geom class because it does not exist yet when we need to store the mark. Re #2, we can put the code that does the marking either in the place where the root BIO is created (but there may be many such places, and especially they can be in external modules that we are not even aware of), or hook into a central place, g_io_request(), and walk up the BIO tree until we find the root: { struct bio *top = bp; while (top->bio_parent) top = top->bio_parent; if (top->bio_caller1 == NULL) top->bio_caller1 = (void *)curthread->td_tid; } We opted for the latter. The drawbacks of this approach are that we are writing in a BIO that is not ours, also that bio_caller1 might be unavailable (e.g. in the ZFS case). The alternative approach is adding one field to the struct bio -- in this case the marking could just be done on the current BIO in g_io_request, and propagated down in g_clone_bio() (or just in the lookup, walk up the tree to the topmost marked bio). So, do you have any better ideas, e.g. other fields in the topmost bio that we can use ? cheers luigi From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 14:31:39 2009 Return-Path: Delivered-To: arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 2A546106564A for ; Fri, 9 Jan 2009 14:31:39 +0000 (UTC) (envelope-from luigi@onelab2.iet.unipi.it) Received: from onelab2.iet.unipi.it (onelab2.iet.unipi.it [131.114.9.129]) by mx1.freebsd.org (Postfix) with ESMTP id E29178FC16 for ; Fri, 9 Jan 2009 14:31:38 +0000 (UTC) (envelope-from luigi@onelab2.iet.unipi.it) Received: by onelab2.iet.unipi.it (Postfix, from userid 275) id 1840773098; Fri, 9 Jan 2009 15:36:41 +0100 (CET) Date: Fri, 9 Jan 2009 15:36:41 +0100 From: Luigi Rizzo To: Poul-Henning Kamp Message-ID: <20090109143641.GA19478@onelab2.iet.unipi.it> References: <20090109130911.GA17017@onelab2.iet.unipi.it> <22308.1231510855@critter.freebsd.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <22308.1231510855@critter.freebsd.dk> User-Agent: Mutt/1.4.2.3i Cc: arch@freebsd.org, fabio@gandalf.sssup.it Subject: Re: tagging disk requests (geom-related) X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 14:31:39 -0000 On Fri, Jan 09, 2009 at 02:20:55PM +0000, Poul-Henning Kamp wrote: > In message <20090109130911.GA17017@onelab2.iet.unipi.it>, Luigi Rizzo writes: > > > (Background for non geom-aware people: each request is identified > > by a 'struct bio' (BIO); > > Strictly speaking, the bio *is* the request :-) > > >For #1, to avoid adding a field to 'struct bio', we store the tag > >in the bio_caller1 field (if available) of the root element of the > >BIO tree, bio_caller1 is normally unused (except by ZFS), and we > >say it is available if it contains NULL. > > This is wrong, bio_caller1 is for the caller to store private > information, you should not hi-jack it. > > >Re #2, we can put the code that does the marking either in the place > >where the root BIO is created (but there may be many such places, > >and especially they can be in external modules that we are not even > >aware of), or hook into a central place, g_io_request(), and walk > >up the BIO tree until we find the root: > > This will not work, some GEOM classes initiate bios, (RAID5 parity > stripes for instance. > > It is also really stupid to walk the chain repeatedly like this. > > >The alternative approach is adding one field to the struct bio -- in this > >case the marking could just be done on the current BIO in g_io_request, > >and propagated down in g_clone_bio() (or just in the lookup, walk > >up the tree to the topmost marked bio). > > That's the way to go. I agree. Probably there is no other reliable way. The unfortunate drawback of this approach is that it changes the size of the bio (so you need a full rebuild of kernel and modules), that's why I was hoping for a possibly unused field in the topmost bio to store the tag. > Also, and please make sure you understand the depth of this suggestion > before you dismiss it: > > Instead of recording the identity of the originator, you should > record a struct containing capabilities of the originator, one > of which could be the identity. yes, as i said in the original post the details are irrelevant now, i just needed a place to hook the additional info to the bio. Once i have that, i can do all details i need. thanks luigi From owner-freebsd-arch@FreeBSD.ORG Fri Jan 9 14:36:30 2009 Return-Path: Delivered-To: arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 439911065670 for ; Fri, 9 Jan 2009 14:36:30 +0000 (UTC) (envelope-from phk@critter.freebsd.dk) Received: from phk.freebsd.dk (phk.freebsd.dk [130.225.244.222]) by mx1.freebsd.org (Postfix) with ESMTP id 07A918FC13 for ; Fri, 9 Jan 2009 14:36:29 +0000 (UTC) (envelope-from phk@critter.freebsd.dk) Received: from critter.freebsd.dk (critter.freebsd.dk [192.168.61.3]) by phk.freebsd.dk (Postfix) with ESMTP id 07E873F12F; Fri, 9 Jan 2009 14:20:55 +0000 (UTC) Received: from critter.freebsd.dk (localhost [127.0.0.1]) by critter.freebsd.dk (8.14.3/8.14.3) with ESMTP id n09EKtaY022309; Fri, 9 Jan 2009 14:20:55 GMT (envelope-from phk@critter.freebsd.dk) To: Luigi Rizzo From: "Poul-Henning Kamp" In-Reply-To: Your message of "Fri, 09 Jan 2009 14:09:11 +0100." <20090109130911.GA17017@onelab2.iet.unipi.it> Date: Fri, 09 Jan 2009 14:20:55 +0000 Message-ID: <22308.1231510855@critter.freebsd.dk> Sender: phk@critter.freebsd.dk Cc: arch@freebsd.org, fabio@gandalf.sssup.it Subject: Re: tagging disk requests (geom-related) X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jan 2009 14:36:30 -0000 In message <20090109130911.GA17017@onelab2.iet.unipi.it>, Luigi Rizzo writes: > (Background for non geom-aware people: each request is identified > by a 'struct bio' (BIO); Strictly speaking, the bio *is* the request :-) >For #1, to avoid adding a field to 'struct bio', we store the tag >in the bio_caller1 field (if available) of the root element of the >BIO tree, bio_caller1 is normally unused (except by ZFS), and we >say it is available if it contains NULL. This is wrong, bio_caller1 is for the caller to store private information, you should not hi-jack it. >Re #2, we can put the code that does the marking either in the place >where the root BIO is created (but there may be many such places, >and especially they can be in external modules that we are not even >aware of), or hook into a central place, g_io_request(), and walk >up the BIO tree until we find the root: This will not work, some GEOM classes initiate bios, (RAID5 parity stripes for instance. It is also really stupid to walk the chain repeatedly like this. >The alternative approach is adding one field to the struct bio -- in this >case the marking could just be done on the current BIO in g_io_request, >and propagated down in g_clone_bio() (or just in the lookup, walk >up the tree to the topmost marked bio). That's the way to go. Also, and please make sure you understand the depth of this suggestion before you dismiss it: Instead of recording the identity of the originator, you should record a struct containing capabilities of the originator, one of which could be the identity. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence.