From owner-freebsd-current@FreeBSD.ORG Wed Aug 24 14:03:31 2011 Return-Path: Delivered-To: current@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id BDA27106564A; Wed, 24 Aug 2011 14:03:31 +0000 (UTC) (envelope-from kostikbel@gmail.com) Received: from mail.zoral.com.ua (mx0.zoral.com.ua [91.193.166.200]) by mx1.freebsd.org (Postfix) with ESMTP id 365E68FC12; Wed, 24 Aug 2011 14:03:31 +0000 (UTC) Received: from deviant.kiev.zoral.com.ua (root@deviant.kiev.zoral.com.ua [10.1.1.148]) by mail.zoral.com.ua (8.14.2/8.14.2) with ESMTP id p7OE3MFl052449 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 24 Aug 2011 17:03:27 +0300 (EEST) (envelope-from kostikbel@gmail.com) Received: from deviant.kiev.zoral.com.ua (kostik@localhost [127.0.0.1]) by deviant.kiev.zoral.com.ua (8.14.4/8.14.4) with ESMTP id p7ODfQNi066651; Wed, 24 Aug 2011 16:41:26 +0300 (EEST) (envelope-from kostikbel@gmail.com) Received: (from kostik@localhost) by deviant.kiev.zoral.com.ua (8.14.4/8.14.4/Submit) id p7ODfPmE066650; Wed, 24 Aug 2011 16:41:25 +0300 (EEST) (envelope-from kostikbel@gmail.com) X-Authentication-Warning: deviant.kiev.zoral.com.ua: kostik set sender to kostikbel@gmail.com using -f Date: Wed, 24 Aug 2011 16:41:25 +0300 From: Kostik Belousov To: Rick Macklem Message-ID: <20110824134125.GP17489@deviant.kiev.zoral.com.ua> References: <20110824125715.GN17489@deviant.kiev.zoral.com.ua> <1673984146.274156.1314192997207.JavaMail.root@erie.cs.uoguelph.ca> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="gbc0iEmq9s77YLcW" Content-Disposition: inline In-Reply-To: <1673984146.274156.1314192997207.JavaMail.root@erie.cs.uoguelph.ca> User-Agent: Mutt/1.4.2.3i X-Virus-Scanned: clamav-milter 0.95.2 at skuns.kiev.zoral.com.ua X-Virus-Status: Clean X-Spam-Status: No, score=-3.3 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00, DNS_FROM_OPENWHOIS autolearn=no version=3.2.5 X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on skuns.kiev.zoral.com.ua Cc: pjd@freebsd.org, current@freebsd.org, kaduk@MIT.EDU Subject: Re: fsid change of ZFS? X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 24 Aug 2011 14:03:31 -0000 --gbc0iEmq9s77YLcW Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Aug 24, 2011 at 09:36:37AM -0400, Rick Macklem wrote: > Kostik Belousov wrote: > > On Wed, Aug 24, 2011 at 09:34:58PM +0900, Hiroki Sato wrote: > > > Kostik Belousov wrote > > > in <20110824082119.GJ17489@deviant.kiev.zoral.com.ua>: > > > > > > ko> On Tue, Aug 23, 2011 at 11:23:03PM +0200, Pawel Jakub Dawidek > > > wrote: > > > ko> > On Tue, Aug 23, 2011 at 04:11:20PM -0400, Rick Macklem wrote: > > > ko> > > Pawel Jakub Dawidek wrote: > > > ko> > > > On Tue, Aug 23, 2011 at 10:09:41AM -0400, Rick Macklem > > > wrote: > > > ko> > > > > Ok, I'll admit I wasn't very fond of a fixed table that > > > would > > > ko> > > > > inevitably > > > ko> > > > > get out of date someday, either. > > > ko> > > > > > > > ko> > > > > I didn't think hashing for the cases not in the table > > > was worth the > > > ko> > > > > effort, > > > ko> > > > > but doing a hash instead of a table seems reasonable. > > > ko> > > > > > > > ko> > > > > I see that ZFS only uses the low order 8 bits, so I'll > > > try and come > > > ko> > > > > up > > > ko> > > > > with an 8bit hash solution and will post a patch for > > > testing/review > > > ko> > > > > soon. > > > ko> > > > > > > > ko> > > > > I don't think the vfs_sysctl() is that great a concern, > > > given that > > > ko> > > > > it > > > ko> > > > > appears to be deprecated already anyhow. (With an 8bit > > > hash, > > > ko> > > > > vfs_typenum > > > ko> > > > > won't be that sparse.) I'll also make sure that whatever > > > hash I use > > > ko> > > > > doesn't collide for the current list of file names > > > (although I will > > > ko> > > > > include > > > ko> > > > > code that handles a collision in the patch). > > > ko> > > > > > > ko> > > > Sounds great. Thanks! > > > ko> > > > > > > ko> > > Here's the patch. (Hiroki could you please test this, > > > thanks, rick.) > > > ko> > > ps: If the white space gets trashed, the same patch is at: > > > ko> > > http://people.freebsd.org/~rmacklem/fsid.patch > > > ko> > > > > ko> > The patch is fine by me. Thanks, Rick! > > > ko> > > > ko> Sorry, I am late. > > > ko> > > > ko> It seems that the probability of the collisions for the hash is > > > quite high. > > > ko> Due to the fixup procedure, the resulting typenum will depend on > > > the order > > > ko> of the module initialization, isn't it ? IMO, it makes the patch > > > goal not > > > ko> met. > > > > > > I tried the following two experiments (the complete results are > > > attached) to confirm the probability: > > > > > > 1. [fsidhash1.txt] > > > well-known vfc_name and the names "[a-z]fs" (# of names is 36) > > > with no fix-up recalculation. > > > > > > 2. [fsidhash2.txt] > > > well-known vfc_name and the names "[a-z][a-z]fs" (# of names is > > > 710) > > > with no fix-up recalculation. > > > > > > There is no collision in the case 1. And when [a-z][a-z]fs are > > > included the average number of the collided names in the same hash > > > value is 4.43 (i.e. 160 different hash values are generated, the > > > theoretical best number is (710 entries / 256 buckets) =3D 2.77). > > > > > > At least, vfc_names we currently have in our kernel code have no > > > collision, fortunately. As you noticed "[a-z][a-z]fs" is an > > > impractical data set and these results cannot explain the > > > characteristics for all possible and practical vfc_names, so > > > whether > > > this hash is reasonable or not depends on how we think of them. > > > Comments or other better idea? > >=20 > > Might be, add a new byte field to struct vfsconf, containing the > > suggested > > byte to be used by fsid. Divide the namespace into two half by the > > highest > > bit 7. Use the byte values with the highest bit clear for statically > > assignment for in-tree modules. Kernel will still check for the > > uniquiness > > on initialization. > >=20 > Well, doesn't this result in the same issue as the fixed table? > In other words, the developer has to supply the "suggested byte" for > fsid and make sure that it doesn't conflict with other "suggested byte" > values or suffer the same consequence as forgetting to update the fixed > table. (ie. It just puts the fixed value in a different place, from what > I see, for in-tree modules. Also, with a fixed table, they are all in > one place, so it's easy to choose a non-colliding value?) The reason for my proposal was Pawel note that a porter of the filesystem should be aware of some place in kern/ where to register, besides writing the module. Anyway, do whatever you prefer. >=20 > > Reserve the value '0' to mean that kernel must assign the next unused > > value >=3D 128. This is done to support out-of-tree modules. > >=20 > > Might be, also reserve the value 0 to mean 'kernel > > Main drawback is that is sounds complicated. --gbc0iEmq9s77YLcW Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (FreeBSD) iEYEARECAAYFAk5U/4UACgkQC3+MBN1Mb4iv3wCgpE0FTtSOIyi9i14O2789zK6p N8MAn1uQBBDMjwp3qA9feBeyz7mSJRm1 =QEE4 -----END PGP SIGNATURE----- --gbc0iEmq9s77YLcW--