Date: Wed, 24 Aug 2011 16:41:25 +0300 From: Kostik Belousov <kostikbel@gmail.com> To: Rick Macklem <rmacklem@uoguelph.ca> Cc: pjd@freebsd.org, current@freebsd.org, kaduk@MIT.EDU Subject: Re: fsid change of ZFS? Message-ID: <20110824134125.GP17489@deviant.kiev.zoral.com.ua> In-Reply-To: <1673984146.274156.1314192997207.JavaMail.root@erie.cs.uoguelph.ca> References: <20110824125715.GN17489@deviant.kiev.zoral.com.ua> <1673984146.274156.1314192997207.JavaMail.root@erie.cs.uoguelph.ca>
next in thread | previous in thread | raw e-mail | index | archive | help
--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 <kostikbel@gmail.com> 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--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20110824134125.GP17489>