Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 25 Aug 2011 01:04:24 +0900 (JST)
From:      Hiroki Sato <hrs@FreeBSD.org>
To:        gleb.kurtsou@gmail.com
Cc:        kostikbel@gmail.com, rmacklem@uoguelph.ca, pjd@FreeBSD.org, current@FreeBSD.org, kaduk@MIT.EDU
Subject:   Re: fsid change of ZFS?
Message-ID:  <20110825.010424.484677638916081204.hrs@allbsd.org>
In-Reply-To: <20110824150235.GA46460@tops>
References:  <20110824082119.GJ17489@deviant.kiev.zoral.com.ua> <20110824.213458.806017948592590395.hrs@allbsd.org> <20110824150235.GA46460@tops>

next in thread | previous in thread | raw e-mail | index | archive | help
----Security_Multipart0(Thu_Aug_25_01_04_24_2011_949)--
Content-Type: Multipart/Mixed;
	boundary="--Next_Part(Thu_Aug_25_01_04_24_2011_827)--"
Content-Transfer-Encoding: 7bit

----Next_Part(Thu_Aug_25_01_04_24_2011_827)--
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Gleb Kurtsou <gleb.kurtsou@gmail.com> wrote
  in <20110824150235.GA46460@tops>:

gl> On (24/08/2011 21:34), Hiroki Sato wrote:
gl> > Kostik Belousov <kostikbel@gmail.com> wrote
gl> >   in <20110824082119.GJ17489@deviant.kiev.zoral.com.ua>:
gl> >
gl> > ko> On Tue, Aug 23, 2011 at 11:23:03PM +0200, Pawel Jakub Dawidek wrote:
gl> > ko> > On Tue, Aug 23, 2011 at 04:11:20PM -0400, Rick Macklem wrote:
gl> > ko> > > Here's the patch. (Hiroki could you please test this, thanks, rick.)
gl> > ko> > > ps: If the white space gets trashed, the same patch is at:
gl> > ko> > >    http://people.freebsd.org/~rmacklem/fsid.patch
gl> > ko> >
gl> > ko> > The patch is fine by me. Thanks, Rick!
gl> > ko>
gl> > ko> Sorry, I am late.
gl> > ko>
gl> > ko> It seems that the probability of the collisions for the hash is quite high.
gl> > ko> Due to the fixup procedure, the resulting typenum will depend on the order
gl> > ko> of the module initialization, isn't it ? IMO, it makes the patch goal not
gl> > ko> met.
gl> >
gl> >  I tried the following two experiments (the complete results are
gl> >  attached) to confirm the probability:
gl> >
gl> >  1. [fsidhash1.txt]
gl> > 	well-known vfc_name and the names "[a-z]fs" (# of names is 36)
gl> > 	with no fix-up recalculation.
gl> >
gl> >  2. [fsidhash2.txt]
gl> > 	well-known vfc_name and the names "[a-z][a-z]fs" (# of names is 710)
gl> > 	with no fix-up recalculation.
gl> >
gl> >  There is no collision in the case 1.  And when [a-z][a-z]fs are
gl> >  included the average number of the collided names in the same hash
gl> >  value is 4.43 (i.e. 160 different hash values are generated, the
gl> >  theoretical best number is (710 entries / 256 buckets) = 2.77).
gl> Could you run the same test with fnv_32_buf()? Collision rate is likely
gl> to be lower.

 The results by fnv_32_str() are attached.  The number of the
 collisions reduced but this time there were four collisions in the
 "well-known ones + [a-z]fs" case though no collision within the
 well-known names.

 The generated hash values for the case 2 was 235, so the rate is
 3.02.  This is certainly better than hash32_str().

-- Hiroki

----Next_Part(Thu_Aug_25_01_04_24_2011_827)--
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="fsidhash_fnv1.txt"

0x0d = yfs
0x13 = mfs
0x19 = procfs
0x1a = kfs
0x30 = bfs
0x34 = ufs
0x3a = gfs
0x40 = sfs, udf
0x56 = jfs
0x5a = ntfs
0x5d = ext2fs
0x61 = devfs
0x6f = hpfs
0x75 = hfs
0x7a = pfs
0x7b = ofs
0x7c = dfs
0x81 = wfs
0x88 = msdosfs
0xa0 = cd9660
0xa1 = lfs, xfs
0xa8 = cfs, tfs
0xbf = tmpfs
0xc0 = afs
0xc2 = reiserfs
0xc6 = ifs
0xc8 = ffs, rfs
0xec = qfs
0xed = zfs
0xee = efs
0xef = nfs
0xf4 = vfs

----Next_Part(Thu_Aug_25_01_04_24_2011_827)--
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="fsidhash_fnv2.txt"

0x01 = mcfs, prfs, xufs
0x02 = iafs, jifs, kpfs, xifs
0x04 = bzfs, dbfs, ehfs, ewfs, klfs, yhfs
0x05 = ycfs
0x06 = dyfs, ecfs, ipfs, qdfs, qpfs
0x07 = pnfs, ywfs
0x08 = qofs, xafs
0x09 = bmfs, iffs, iyfs, kdfs, pufs, vffs
0x0a = imfs
0x0b = bffs, dmfs
0x0c = idfs, yofs
0x0d = adfs, nmfs, pafs, vqfs, yfs
0x0e = aifs, qwfs
0x0f = hafs, nffs, vzfs
0x10 = zafs
0x11 = wcfs
0x12 = zjfs
0x13 = mfs, nqfs, wwfs
0x14 = nefs, vcfs
0x15 = bkfs
0x16 = clfs, zifs
0x17 = njfs, zrfs
0x18 = ocfs, owfs, tvfs, wdfs
0x19 = fefs, procfs, tbfs, vwfs, zffs
0x1a = fnfs, fqfs, kfs
0x1b = gofs, ryfs
0x1d = fzfs, rmfs, rrfs, skfs
0x1e = odfs, tqfs
0x1f = lvfs, oofs, oxfs, rffs, tzfs
0x20 = eefs, gwfs, kmfs, tmfs, xcfs
0x21 = ulfs, yqfs
0x22 = fbfs, hrfs, mtfs, qifs, sxfs, xjfs
0x23 = dofs, sdfs, ssfs, ugfs
0x24 = etfs, kofs, usfs, uxfs
0x25 = kqfs, ljfs, mkfs, opfs, pcfs
0x26 = jrfs, pwfs, qxfs
0x27 = ghfs
0x28 = hjfs, xvfs
0x29 = hufs, ikfs, jpfs, ksfs, slfs
0x2a = byfs, jefs, khfs, ukfs
0x2b = brfs, dhfs, jnfs, ytfs
0x2c = defs, hwfs, msfs
0x2d = apfs, qlfs
0x2e = pdfs, pifs, vefs
0x2f = befs, cgfs, hmfs, iwfs, jlfs, vnfs
0x30 = bfs, bjfs, jwfs
0x31 = csfs, cxfs
0x33 = alfs, axfs, vyfs
0x34 = ufs
0x35 = acfs, jcfs, vvfs
0x36 = awfs, bcfs, vbfs
0x37 = wkfs
0x38 = tofs
0x3a = fmfs, gfs
0x3b = nvfs
0x3c = nbfs, rqfs
0x3d = tgfs, tsfs, zwfs
0x3e = wlfs, zzfs
0x3f = fkfs, wgfs, znfs
0x40 = dvfs, gcfs, sfs, thfs, udf, wpfs
0x41 = fwfs
0x42 = pzfs, rwfs, udfs
0x43 = dgfs, lgfs, sgfs
0x44 = rkfs
0x45 = dnfs, llfs, lsfs, ogfs
0x46 = lxfs, pkfs, wxfs
0x47 = dqfs, eofs, gdfs, xofs
0x48 = dzfs, pbfs, upfs, xdfs, xpfs
0x49 = qcfs
0x4a = dsfs, pvfs, rcfs
0x4b = exfs, jzfs, mhfs, ohfs
0x4c = esfs, gpfs, ylfs
0x4d = qtfs, ygfs
0x4e = hbfs, hofs, ihfs
0x4f = bhfs, hvfs, icfs, uvfs
0x50 = bwfs, ktfs, mnfs, stfs
0x51 = ejfs
0x53 = itfs
0x54 = qffs, vkfs, vtfs
0x56 = bofs, cofs, jfs, jkfs
0x57 = iofs, yjfs
0x59 = qrfs
0x5a = atfs, ntfs, vsfs
0x5b = akfs
0x5d = ccfs, chfs, ctfs, ext2fs, zlfs, zxfs
0x5e = fvfs, wzfs
0x60 = nsfs, rjfs, wsfs
0x61 = devfs, ftfs, nofs, nxfs
0x62 = agfs, fjfs, xbfs
0x63 = ojfs
0x64 = grfs, kgfs, rhfs, rvfs, tkfs, wofs, zcfs, ztfs
0x65 = lofs, ttfs
0x66 = fhfs, gffs
0x67 = mgfs, ngfs, svfs, xsfs
0x68 = fsfs, sbfs
0x69 = ppfs, rtfs, zkfs
0x6a = jxfs, rofs, uhfs
0x6b = dkfs, elfs, kkfs, mefs, mpfs, ucfs
0x6c = omfs, txfs, yxfs
0x6d = egfs, fgfs, pgfs, ysfs
0x6e = gufs, gxfs, kbfs, plfs, uafs, xgfs
0x6f = hpfs
0x70 = myfs, qkfs, sqfs, uzfs
0x71 = epfs, jtfs, kxfs
0x72 = mbfs, ydfs
0x73 = hgfs, hsfs
0x74 = ekfs, ykfs
0x75 = cvfs, hfs, qsfs, unfs
0x76 = btfs, hhfs
0x77 = jgfs, mvfs, qgfs
0x78 = evfs, ybfs
0x7a = pfs
0x7b = ahfs, cjfs, isfs, ofs, qzfs, vhfs
0x7c = bgfs, dfs
0x7d = blfs, cefs, cqfs, igfs
0x7f = anfs
0x80 = osfs
0x81 = aefs, arfs, gkfs, nlfs, vgfs, vpfs, wfs
0x83 = bsfs, obfs, wbfs
0x84 = twfs, wifs
0x85 = sofs, wvfs
0x86 = gzfs, okfs, otfs
0x87 = azfs, ltfs, npfs, vofs
0x88 = glfs, gsfs, msdosfs, nkfs
0x89 = ggfs
0x8a = ovfs, shfs, swfs, xhfs
0x8b = gnfs, tcfs, uwfs, zgfs
0x8c = dtfs, lcfs, scfs, wefs
0x8d = lhfs, mofs, psfs
0x8e = fofs
0x8f = kzfs, pxfs, sjfs
0x90 = kwfs, rsfs, xtfs, zsfs
0x91 = dcfs, dwfs, lqfs, tefs
0x92 = dlfs, ebfs, eifs, kcfs, yifs
0x93 = pofs, yvfs
0x94 = qnfs, qqfs
0x95 = dxfs, xmfs
0x96 = jhfs, qefs, uffs
0x97 = lefs
0x98 = ezfs, ptfs
0x99 = iqfs, ynfs
0x9a = hkfs, xyfs
0x9b = bqfs, qvfs
0x9c = iefs
0x9d = asfs, bxfs, htfs, jofs
0x9e = jdfs, jsfs
0x9f = vmfs
0xa0 = cd9660
0xa1 = aqfs, cffs, ijfs, ivfs, lfs, vdfs, xfs
0xa2 = hlfs
0xa3 = aofs, bdfs, cmfs, crfs
0xa4 = cyfs, wjfs
0xa6 = amfs, nifs
0xa7 = avfs, oyfs, tlfs, vxfs
0xa8 = cfs, fdfs, gafs, ibfs, tfs, zefs, zqfs
0xa9 = fpfs
0xaa = cafs, rxfs, uufs
0xab = mmfs, rgfs, tnfs
0xac = fyfs, lwfs, onfs, rlfs, sefs, tpfs
0xad = abfs, gvfs, oefs
0xae = nwfs, nzfs, refs
0xaf = fcfs, knfs, umfs, xkfs
0xb0 = srfs, zvfs
0xb1 = lkfs, mufs, syfs, tifs, trfs, urfs
0xb2 = kefs, mafs, mjfs, uyfs
0xb4 = ldfs, lpfs, xwfs
0xb6 = jqfs, kffs, krfs, ujfs, xxfs
0xb7 = eufs, xlfs
0xb8 = difs, lmfs, mrfs, yafs
0xb9 = ddfs, eafs, kifs
0xba = pefs, qyfs, yufs
0xbb = dpfs, hcfs, jmfs, phfs, qmfs, xqfs
0xbc = jyfs
0xbd = jbfs
0xbe = erfs, jvfs
0xbf = enfs, eyfs, tmpfs, yffs
0xc0 = afs, hefs, ymfs, yzfs
0xc1 = bifs, hnfs, hyfs, iifs
0xc2 = bbfs, ndfs, qbfs, qufs, reiserfs
0xc3 = bvfs, cnfs
0xc5 = effs, vufs, zhfs
0xc6 = ifs, nufs, vafs, yrfs
0xc7 = qjfs, vjfs
0xc8 = czfs, ffs, hqfs, infs, iufs, rfs, wqfs, zyfs
0xc9 = ncfs, nhfs
0xca = bnfs
0xcb = wffs, zofs, zpfs
0xcc = nafs, ozfs, wmfs, zdfs
0xcd = gbfs, izfs, oqfs
0xce = ajfs, fafs, flfs, gifs, tdfs, vrfs
0xcf = fxfs, zmfs
0xd0 = rpfs, sffs
0xd1 = lffs, offs, orfs, smfs
0xd2 = oifs, rdfs, wtfs
0xd3 = gjfs, lrfs, lyfs
0xd4 = xzfs
0xd5 = gqfs, snfs, szfs, xefs
0xd6 = gefs, uefs, uqfs, xnfs
0xd7 = dffs, sufs
0xd8 = drfs, lafs, safs, tufs
0xd9 = mifs, pjfs
0xdd = bpfs, dafs, edfs, kjfs, ubfs, uifs
0xde = djfs, hxfs, kafs, kufs, mqfs, mzfs, ypfs
0xdf = emfs, mffs, qhfs
0xe0 = pmfs, yyfs
0xe1 = bafs, hzfs, pffs, pqfs
0xe2 = ayfs, jafs, qafs, vlfs
0xe3 = hdfs, jjfs, jufs
0xe4 = dufs, eqfs
0xe5 = cufs, ixfs, kyfs, yefs
0xe7 = aafs, hffs, ilfs, pyfs
0xe8 = bufs
0xe9 = aufs, cwfs, nnfs
0xea = cbfs, jffs
0xeb = cifs, tffs
0xec = qfs, wrfs, zbfs
0xed = hifs, nyfs, vifs, wyfs, zfs
0xee = affs, ckfs, efs, fufs, nrfs
0xef = cpfs, irfs, nfs
0xf0 = rifs, zufs
0xf1 = wnfs
0xf2 = fifs, rbfs, tafs, tjfs
0xf3 = wafs
0xf4 = vfs
0xf5 = cdfs, rufs, wufs
0xf6 = fffs, frfs, rafs
0xf7 = mdfs, rzfs
0xf8 = lnfs, olfs, whfs
0xf9 = gtfs, lzfs, oafs, rnfs, tyfs
0xfa = gyfs, xrfs
0xfb = oufs
0xfc = gmfs, spfs, utfs, xffs
0xfd = kvfs, mlfs, mxfs, uofs
0xfe = mwfs
0xff = lbfs, lifs, lufs, sifs

----Next_Part(Thu_Aug_25_01_04_24_2011_827)----

----Security_Multipart0(Thu_Aug_25_01_04_24_2011_949)--
Content-Type: application/pgp-signature
Content-Transfer-Encoding: 7bit

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (FreeBSD)

iEYEABECAAYFAk5VIQgACgkQTyzT2CeTzy0QiQCfZfD5Yao56/yxNjatrGSi8ld+
P9gAn2tUMb36BF3apcHk6lsgdQH6w6lp
=Ubz3
-----END PGP SIGNATURE-----

----Security_Multipart0(Thu_Aug_25_01_04_24_2011_949)----



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20110825.010424.484677638916081204.hrs>