Date: Wed, 24 Aug 2011 15:57:15 +0300 From: Kostik Belousov <kostikbel@gmail.com> To: Hiroki Sato <hrs@freebsd.org> Cc: kostikbel@gmail.com, rmacklem@uoguelph.ca, pjd@freebsd.org, current@freebsd.org, kaduk@MIT.EDU Subject: Re: fsid change of ZFS? Message-ID: <20110824125715.GN17489@deviant.kiev.zoral.com.ua> In-Reply-To: <20110824.213458.806017948592590395.hrs@allbsd.org> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
--cgvqJugwi0EWj/n7 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Aug 24, 2011 at 09:34:58PM +0900, Hiroki Sato wrote: > Kostik Belousov <kostikbel@gmail.com> wrote > in <20110824082119.GJ17489@deviant.kiev.zoral.com.ua>: >=20 > 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 wor= th 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 an= d 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, ric= k.) > 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. >=20 > I tried the following two experiments (the complete results are > attached) to confirm the probability: >=20 > 1. [fsidhash1.txt] > well-known vfc_name and the names "[a-z]fs" (# of names is 36) > with no fix-up recalculation. >=20 > 2. [fsidhash2.txt] > well-known vfc_name and the names "[a-z][a-z]fs" (# of names is 710) > with no fix-up recalculation. >=20 > 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). >=20 > 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= =20 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. 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. Might be, also reserve the value 0 to mean 'kernel Main drawback is that is sounds complicated. --cgvqJugwi0EWj/n7 Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (FreeBSD) iEYEARECAAYFAk5U9SsACgkQC3+MBN1Mb4ikBACgkHDdtJysuFjPe8eO1bl8ef+c IG0An1LPRgk1iHPhTqjV1PXahAhErB4d =CpRt -----END PGP SIGNATURE----- --cgvqJugwi0EWj/n7--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20110824125715.GN17489>