From owner-freebsd-fs@freebsd.org Thu May 9 21:44:00 2019 Return-Path: Delivered-To: freebsd-fs@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 80221158E8CF for ; Thu, 9 May 2019 21:44:00 +0000 (UTC) (envelope-from rmacklem@uoguelph.ca) Received: from CAN01-TO1-obe.outbound.protection.outlook.com (mail-eopbgr670065.outbound.protection.outlook.com [40.107.67.65]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (Client CN "mail.protection.outlook.com", Issuer "GlobalSign Organization Validation CA - SHA256 - G3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4822683421; Thu, 9 May 2019 21:43:58 +0000 (UTC) (envelope-from rmacklem@uoguelph.ca) Received: from YQBPR0101MB2260.CANPRD01.PROD.OUTLOOK.COM (52.132.70.13) by YQBPR0101MB1555.CANPRD01.PROD.OUTLOOK.COM (52.132.68.152) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1856.15; Thu, 9 May 2019 21:43:56 +0000 Received: from YQBPR0101MB2260.CANPRD01.PROD.OUTLOOK.COM ([fe80::e92e:7851:66e9:3967]) by YQBPR0101MB2260.CANPRD01.PROD.OUTLOOK.COM ([fe80::e92e:7851:66e9:3967%7]) with mapi id 15.20.1856.016; Thu, 9 May 2019 21:43:56 +0000 From: Rick Macklem To: "cem@freebsd.org" CC: "freebsd-fs@freebsd.org" Subject: Re: test hash functions for fsid Thread-Topic: test hash functions for fsid Thread-Index: AQHVBauTkubp5doP8E+dPPSC2TDxraZhYDeAgACLOvWAAS5UAIAANU8e Date: Thu, 9 May 2019 21:43:56 +0000 Message-ID: References: , In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: f5844d2c-9986-48cd-ef21-08d6d4c77071 x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600141)(711020)(4605104)(2017052603328)(7193020); SRVR:YQBPR0101MB1555; x-ms-traffictypediagnostic: YQBPR0101MB1555: x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:10000; x-forefront-prvs: 003245E729 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(346002)(376002)(396003)(39860400002)(136003)(366004)(199004)(189003)(51914003)(5660300002)(14454004)(2351001)(9686003)(5640700003)(6916009)(7696005)(478600001)(25786009)(55016002)(6436002)(446003)(71190400001)(229853002)(74482002)(450100002)(2501003)(4326008)(86362001)(66946007)(305945005)(476003)(486006)(53936002)(81156014)(71200400001)(8936002)(81166006)(74316002)(52536014)(33656002)(11346002)(8676002)(14444005)(256004)(1730700003)(6506007)(6246003)(99286004)(76176011)(46003)(186003)(2906002)(68736007)(76116006)(102836004)(786003)(64756008)(66476007)(66556008)(66446008)(316002)(73956011); DIR:OUT; SFP:1101; SCL:1; SRVR:YQBPR0101MB1555; H:YQBPR0101MB2260.CANPRD01.PROD.OUTLOOK.COM; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: uoguelph.ca does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam-message-info: QeUzjVHrx1taItitQVdCRc+8+5T5bgz3NOzgR6//u/YxhTJF3n8KVmy3pZ37NtO7DV55dBvlvYKFaOlbskAMVuaWTEd2xVyIf1gITDb9seiHMmkz7L3CVfTGRtzvrIOUCbdN138iebYkLQEON8T6lLBNYif/AMtFcKi7mx5k2adHrJduu6spiEhRV7rDC9DTVpNxY+MeVcJXcWdhjY/g+FMmm6r15iVdg/PstbjMFihN9Z5p0oU8UOk59i5ZY/xSbDmTG8LuIoae/UXA7zL2MQYMauE5j1t8k0gKCBWVrLNkkSoSPoklx5baTNvwNbi/H+CqLv7pvV31rLjTRFK6QmCEZIYOVnV19GG6r4Ki2YM3z13ybtuFrfVbDNhlDH/74eYOXTqUFMjvC4vk1etnM9ryY1PIHJCmg6MK7qepUbk= Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: uoguelph.ca X-MS-Exchange-CrossTenant-Network-Message-Id: f5844d2c-9986-48cd-ef21-08d6d4c77071 X-MS-Exchange-CrossTenant-originalarrivaltime: 09 May 2019 21:43:56.9139 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: be62a12b-2cad-49a1-a5fa-85f4f3156a7d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-Transport-CrossTenantHeadersStamped: YQBPR0101MB1555 X-Rspamd-Queue-Id: 4822683421 X-Spamd-Bar: / Authentication-Results: mx1.freebsd.org; spf=pass (mx1.freebsd.org: domain of rmacklem@uoguelph.ca designates 40.107.67.65 as permitted sender) smtp.mailfrom=rmacklem@uoguelph.ca X-Spamd-Result: default: False [-0.79 / 15.00]; ARC_NA(0.00)[]; FROM_HAS_DN(0.00)[]; R_SPF_ALLOW(-0.20)[+ip4:40.107.0.0/16]; TO_MATCH_ENVRCPT_ALL(0.00)[]; MIME_GOOD(-0.10)[text/plain]; DMARC_NA(0.00)[uoguelph.ca]; NEURAL_HAM_LONG(-0.98)[-0.981,0]; NEURAL_SPAM_MEDIUM(0.02)[0.015,0]; NEURAL_SPAM_SHORT(0.49)[0.486,0]; RCVD_COUNT_THREE(0.00)[3]; MX_GOOD(-0.01)[cached: mx2.hc184-76.ca.iphmx.com]; RCPT_COUNT_TWO(0.00)[2]; RCVD_IN_DNSWL_NONE(0.00)[65.67.107.40.list.dnswl.org : 127.0.3.0]; TO_DN_EQ_ADDR_ALL(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; R_DKIM_NA(0.00)[]; MIME_TRACE(0.00)[0:+]; RCVD_TLS_LAST(0.00)[] X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 09 May 2019 21:44:00 -0000 Conrad Meyer wrote: >On Wed, May 8, 2019 at 5:41 PM Rick Macklem wrote: >[liberal snipping throughout :-)] >> >> I'll admit I had never heard of PCTRIE, but seems to be >> #ifdef _KERNEL, so it can't be used in userland? > >Ah, you're completely correct. I had considered using PCTRIE for a >userspace application earlier, and had started converting it to be >buildable in userspace, but I never finished. (I determined it >wouldn't be a good fit for that application, unfortunately.) I do >think it might be a good datastructure to expose to base userspace >programs eventually, but you probably don't really want to tackle that >extra work :-). A hash table is totally fine. > >> Yes. I just chose 256 for this test program. Unfortunately, the way moun= td.c is >> currently coded, the hash table must be sized before the getmntinfo() ca= ll, >> so it must be sized before it knows how many file systems there are. >> Since this is userland and table size isn't a memory issue, I'm just tem= pted to >> make it large enough for a large server with something like 25,000 file = systems. > >No objection, so long as people can still run tiny NFS servers on >their Raspberry Pis. :-) I do now think I can dynamically size it based on how many file systems (which is how many structures) will be linked off the table, so this should= n't be a problem. >> (I'd guess somewhere in the 256->1024 range would work. I'm not sure wha= t >> you mean by load factor below 0.8?) > >Load factor is just number of valid entries divided by space in the >table. So if your table has 256 spaces, load factor 0.8 would be >having about 205 valid entries. Hmm. That would suggest a large table size of about 100,000 for Peter's 72,000 file system case. It would result in a list length averaging about 1= entry, but I think a linear search through 10-20 entries won't take long enough to= be a problem for this case. (This happens whenever mountd receives a SIGHUP an= d each time a client does a mount.) As noted in the last post, I was thinking along the lines of 10->20 as a ta= rget linked list length. (Or "table_size =3D num / L", where L is the target ave= rage list length.=20 L =3D 10->20 would be roughly a load average of 10->20.) Does that sound reasonable? (Interested in hearing from anyone on this.) >> Fortunately, neither ZFS nor UFS uses vfs_getnewfsid() unless there is a= collision >> and I don't really care about other file system types. > >Ah, sorry =97 I didn't read carefully enough when looking for fsid initial= ization. > >> After all, it just does >> a linear search down the list of N file systems right and just about an= ything >> should be an improvement.) > >Yes :-). > >> I added a simple (take the low order bits of val[0]) case to the test. I= actually >> suspect any of the hash functions will work well enough, since, as you n= ote, most of the values (val[0] and 24bits of val[1]) are from a random # g= enerator which should >> be pretty uniform in distribution for ZFS. >> UFS now uses a value from the superblock. It appears that newfs sets val= [0] to the >> creation time of the file system and val[1] to a random value. > >Hm, it looks like makefs sets val[1] (fs_id[1]) to a non-random value >generated by the predictable PRNG random(3), for reproducible build >reasons. makefs seeds srandom(3) with either the current time in >seconds (low entropy) or some known timestamp (either from a file, >also in seconds, or an integer) (no entropy). I guess random(3) may >provide better distribution for the table than a plain global counter, >though. Yes. It would be the distribution of values and not their randomness that w= ould matter for this case. Hopefully someone with a large # of UFS file systems = will run the test program and post the results. To be honest, I doubt if anyone = will create a server with enough UFS file systems for it to be important to hash= their fsid well. It works fine for the small number of UFS file systems I have.) >> If it had been the >> reverse, I would be tempted to only use val[0], but I'll see how well th= e test goes >> for Peter. > >Seems like you were right =97 any old function is good enough :-). >From Peter's test, the first three did fine and almost the same. The last t= wo weren't as good, but were still tolerable. Thanks for the comments, rick