From owner-freebsd-current@FreeBSD.ORG Wed Aug 24 15:27:40 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 523A1106564A; Wed, 24 Aug 2011 15:27:40 +0000 (UTC) (envelope-from gleb.kurtsou@gmail.com) Received: from mail-fx0-f54.google.com (mail-fx0-f54.google.com [209.85.161.54]) by mx1.freebsd.org (Postfix) with ESMTP id B0CCC8FC12; Wed, 24 Aug 2011 15:27:39 +0000 (UTC) Received: by fxe4 with SMTP id 4so1381078fxe.13 for ; Wed, 24 Aug 2011 08:27:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=date:from:to:cc:subject:message-id:references:mime-version :content-type:content-disposition:in-reply-to:user-agent; bh=zYu10u4PSZzmMbm+A5Cq2c2/34BVRLl69ZQO9gnqn9E=; b=dbJg4UudsXlpg/RNBxvmUILKSAt/kKsC0HLnu2AoY3QoeciAcpfN7isiPs3HVH9E/P 32pp/c7LgUHCtYUGjhrhyO04FuvlDvUZ8BYUqf9iU7TE1BMRWOp7glHjkaBoRv3qIwXn zIl2cbwxSeJ9XwJeq7dwH6mXTdXOFZqis+PrA= Received: by 10.223.55.203 with SMTP id v11mr7337019fag.78.1314198253060; Wed, 24 Aug 2011 08:04:13 -0700 (PDT) Received: from localhost (lan-78-157-92-5.vln.skynet.lt [78.157.92.5]) by mx.google.com with ESMTPS id r12sm903172fam.14.2011.08.24.08.04.10 (version=SSLv3 cipher=OTHER); Wed, 24 Aug 2011 08:04:11 -0700 (PDT) Date: Wed, 24 Aug 2011 18:02:35 +0300 From: Gleb Kurtsou To: Hiroki Sato Message-ID: <20110824150235.GA46460@tops> References: <1614657395.247867.1314130280524.JavaMail.root@erie.cs.uoguelph.ca> <20110823212301.GE1697@garage.freebsd.pl> <20110824082119.GJ17489@deviant.kiev.zoral.com.ua> <20110824.213458.806017948592590395.hrs@allbsd.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <20110824.213458.806017948592590395.hrs@allbsd.org> User-Agent: Mutt/1.5.21 (2010-09-15) Cc: kostikbel@gmail.com, rmacklem@uoguelph.ca, 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 15:27:40 -0000 On (24/08/2011 21:34), 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> > > 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). Could you run the same test with fnv_32_buf()? Collision rate is likely to be lower. > 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? > > -- Hiroki