From owner-tech+M39777@openbsd.org Wed Dec 3 13:50:33 2014 Delivered-To: david@gwynne.id.au Received: by 10.152.48.84 with SMTP id j20csp434781lan; Tue, 2 Dec 2014 19:50:34 -0800 (PST) X-Received: by 10.42.153.131 with SMTP id m3mr5511288icw.28.1417578633593; Tue, 02 Dec 2014 19:50:33 -0800 (PST) Return-Path: Received: from shear.ucar.edu (lists.openbsd.org. [192.43.244.163]) by mx.google.com with ESMTPS id a19si15817932icl.48.2014.12.02.19.50.33 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 02 Dec 2014 19:50:33 -0800 (PST) Received-SPF: pass (google.com: manual fallback record for domain of owner-tech+M39777@openbsd.org designates 192.43.244.163 as permitted sender) client-ip=192.43.244.163; Authentication-Results: mx.google.com; spf=pass (google.com: manual fallback record for domain of owner-tech+M39777@openbsd.org designates 192.43.244.163 as permitted sender) smtp.mail=owner-tech+M39777@openbsd.org Received: from openbsd.org (localhost [127.0.0.1]) by shear.ucar.edu (8.14.8/8.14.5) with ESMTP id sB342dbf001604; Tue, 2 Dec 2014 21:02:39 -0700 (MST) Received: from ox.tedunangst.com (ox.tedunangst.com [208.82.130.146]) by shear.ucar.edu (8.14.8/8.14.8) with ESMTP id sB342Rwc006814 (version=TLSv1/SSLv3 cipher=DHE-DSS-AES256-SHA bits=256 verify=NO) for ; Tue, 2 Dec 2014 21:02:28 -0700 (MST) Received: from localhost.localdomain (localhost [127.0.0.1]); by ox.tedunangst.com (OpenSMTPD) with ESMTP id 604458f6; for ; Tue, 2 Dec 2014 22:49:50 -0500 (EST) Date: Tue, 02 Dec 2014 22:49:30 -0500 From: Ted Unangst To: tech@openbsd.org Message-ID: <3764923848c047a5be005e891a628e9c@tedunangst.com> Subject: siphash in dirhash Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Loop: tech@openbsd.org Precedence: list Sender: owner-tech@openbsd.org Status: RO Content-Length: 1980 Lines: 59 Use now preferred SipHash24 functions. This also means we shouldn't need to hash in the value of the dirhash pointer itself, which confuses me every time I look at it. Index: ufs/ufs_dirhash.c =================================================================== RCS file: /cvs/src/sys/ufs/ufs/ufs_dirhash.c,v retrieving revision 1.30 diff -u -p -r1.30 ufs_dirhash.c --- ufs/ufs_dirhash.c 14 Sep 2014 14:17:27 -0000 1.30 +++ ufs/ufs_dirhash.c 3 Dec 2014 03:47:22 -0000 @@ -42,9 +42,10 @@ __FBSDID("$FreeBSD: src/sys/ufs/ufs/ufs_ #include #include #include -#include #include +#include + #include #include #include @@ -62,6 +63,7 @@ int ufs_dirhashmaxmem; int ufs_dirhashmem; int ufs_dirhashcheck; +SIPHASH_KEY ufsdirhash_key; int ufsdirhash_hash(struct dirhash *dh, char *name, int namelen); void ufsdirhash_adjfree(struct dirhash *dh, doff_t offset, int diff); @@ -857,17 +859,7 @@ ufsdirhash_checkblock(struct inode *ip, int ufsdirhash_hash(struct dirhash *dh, char *name, int namelen) { - u_int32_t hash; - - /* - * We hash the name and then some other bit of data that is - * invariant over the dirhash's lifetime. Otherwise names - * differing only in the last byte are placed close to one - * another in the table, which is bad for linear probing. - */ - hash = hash32_buf(name, namelen, HASHINIT); - hash = hash32_buf(&dh, sizeof(dh), hash); - return (hash % dh->dh_hlen); + return SipHash24(&ufsdirhash_key, name, namelen) % dh->dh_hlen; } /* @@ -1059,6 +1051,7 @@ ufsdirhash_init(void) pool_init(&ufsdirhash_pool, DH_NBLKOFF * sizeof(doff_t), 0, 0, 0, "dirhash", &pool_allocator_nointr); mtx_init(&ufsdirhash_mtx, IPL_NONE); + arc4random_buf(&ufsdirhash_key, sizeof(ufsdirhash_key)); TAILQ_INIT(&ufsdirhash_list); #if defined (__sparc__) && !defined (__sparc64__) if (!CPU_ISSUN4OR4C)