From owner-freebsd-current@FreeBSD.ORG Wed Aug 24 13:36:38 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 997F9106566B; Wed, 24 Aug 2011 13:36:38 +0000 (UTC) (envelope-from rmacklem@uoguelph.ca) Received: from esa-annu.mail.uoguelph.ca (esa-annu.mail.uoguelph.ca [131.104.91.36]) by mx1.freebsd.org (Postfix) with ESMTP id 257248FC14; Wed, 24 Aug 2011 13:36:38 +0000 (UTC) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ap8EAJ/9VE6DaFvO/2dsb2JhbABCFoQ2pCKBQAEBBAEjVgUWGAICDRkCIzYGExuHVgSpX5ICgSyEDYEQBJMZiXeHIA X-IronPort-AV: E=Sophos;i="4.68,275,1312171200"; d="scan'208";a="132070115" Received: from erie.cs.uoguelph.ca (HELO zcs3.mail.uoguelph.ca) ([131.104.91.206]) by esa-annu-pri.mail.uoguelph.ca with ESMTP; 24 Aug 2011 09:36:37 -0400 Received: from zcs3.mail.uoguelph.ca (localhost.localdomain [127.0.0.1]) by zcs3.mail.uoguelph.ca (Postfix) with ESMTP id 36D69B3F67; Wed, 24 Aug 2011 09:36:37 -0400 (EDT) Date: Wed, 24 Aug 2011 09:36:37 -0400 (EDT) From: Rick Macklem To: Kostik Belousov Message-ID: <1673984146.274156.1314192997207.JavaMail.root@erie.cs.uoguelph.ca> In-Reply-To: <20110824125715.GN17489@deviant.kiev.zoral.com.ua> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Originating-IP: [172.17.91.202] X-Mailer: Zimbra 6.0.10_GA_2692 (ZimbraWebClient - FF3.0 (Win)/6.0.10_GA_2692) 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 13:36:38 -0000 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) = 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? > > 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. > 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?) > Reserve the value '0' to mean that kernel must assign the next unused > value >= 128. This is done to support out-of-tree modules. > > Might be, also reserve the value 0 to mean 'kernel > Main drawback is that is sounds complicated.