Gleb Kurtsou <gleb.kurtsou_at_gmail.com> wrote in <20110824150235.GA46460_at_tops>: gl> On (24/08/2011 21:34), Hiroki Sato wrote: gl> > Kostik Belousov <kostikbel_at_gmail.com> wrote gl> > in <20110824082119.GJ17489_at_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 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 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
This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:40:17 UTC