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