From owner-freebsd-hackers@FreeBSD.ORG Thu Dec 23 23:18:05 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id AA0B410656C4 for ; Thu, 23 Dec 2010 23:18:05 +0000 (UTC) (envelope-from gleb.kurtsou@gmail.com) Received: from mail-ew0-f54.google.com (mail-ew0-f54.google.com [209.85.215.54]) by mx1.freebsd.org (Postfix) with ESMTP id 087708FC0C for ; Thu, 23 Dec 2010 23:18:04 +0000 (UTC) Received: by ewy24 with SMTP id 24so3537829ewy.13 for ; Thu, 23 Dec 2010 15:18:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:date:from:to:subject :message-id:mime-version:content-type:content-disposition:user-agent; bh=jSANTUQJOvUu/ZgE7r0t2m2UYBKyTerj4OmxbZJjA8s=; b=C0VQb+HwpJyje5T0ylk20ZHA+OJ7iSQGUEWoltTj4q24lxEosphJx6atAswwvyJEsE KpvKWd37pWQ9ALF07FnyJtuEWMsEjkKkgO18R/FwsTkMb9Pe6S9PX7vIZRydY6gZVH6B 8taaiZ/zeUqrw1U41dI3dJDNZpBAumT4WTexQ= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=date:from:to:subject:message-id:mime-version:content-type :content-disposition:user-agent; b=lbdCr/nZyFf6AXy/a32POqAUB+73un+G4bWOftUpVP7p+mvvCrMHx5W978+7htDjz2 Dykws8g2r3OKNSIK1YwcM5QSQLpqPcoqkHF19adHybQbYyNxhMmSYYoDUBSUryiq5mPq /pXTYGkk5+SlknCoFHxl9LD7zPZ1fj9Jyd1HQ= Received: by 10.213.20.141 with SMTP id f13mr1324081ebb.36.1293144408082; Thu, 23 Dec 2010 14:46:48 -0800 (PST) Received: from localhost ([212.98.186.134]) by mx.google.com with ESMTPS id t5sm5966779eeh.2.2010.12.23.14.46.46 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 23 Dec 2010 14:46:47 -0800 (PST) Date: Fri, 24 Dec 2010 00:46:20 +0200 From: Gleb Kurtsou To: freebsd-hackers@freebsd.org Message-ID: <20101223224619.GA21984@tops> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="J/dobhs11T7y2rNN" Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Subject: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 23 Dec 2010 23:18:05 -0000 --J/dobhs11T7y2rNN Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Hi, I've recently noticed that hash table use in nullfs was inefficient, 1/3 to half of buckets remained unused. I've started investigating it further and came across SuperFastHash hashing function, SFH (SuperFastHash) has BSD license, used in WebKit and other open source projects. Detailed description and Comparision with FNV and Bob Jenkin's hash can be found here: http://www.azillionmonkeys.com/qed/hash.html In my tests SFH (SuperFastHash) was 1.3 to 4 times faster than FNV (it depends on size of data being hashed) e.g. performance of hashing 56 bytes struct (Core i5 CPU, 2 cores + 2 hyperthreads): SFH -- 1339.79 MB/s FNV -- 330.27 MB/s I've prepared a patch to change FNV and hash32 with SFH in the tree. For testing I've used dbench with 16 processes on 1 Gb swap back md device, UFS + SoftUpdates: Old hash (Mb/s): 599.94 600.096 599.536 SFH hash (Mb/s): 612.439 612.341 609.673 It's just ~1% improvement, but dbench is not a VFS metadata intensive benchmark. Subjectively it feels faster accessing maildir mailboxes with ~10.000 messages : ) I'd also wish hash32 (often called Bernstein hash) to be replaced with better function (it might be FNV if not SFH). Hash32 is inappropriate for binary data that results in poor distribution. Thanks, Gleb. --J/dobhs11T7y2rNN Content-Type: text/plain; charset=utf-8 Content-Disposition: attachment; filename="sfh.patch.txt" commit 6e19401826b6769fa95b1e4f9e561dec7101082b Author: Gleb Kurtsou Date: Thu Dec 16 08:05:14 2010 +0200 Import Paul Hsieh's SuperFastHash. Replace FNV and Bernstein hash uses with SFH. In most cases Bernstein is simply inappropriate choice. diff --git a/lib/libkvm/kvm_minidump_amd64.c b/lib/libkvm/kvm_minidump_amd64.c index 15630b1..7c9c4dd 100644 --- a/lib/libkvm/kvm_minidump_amd64.c +++ b/lib/libkvm/kvm_minidump_amd64.c @@ -35,7 +35,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -74,26 +74,26 @@ static void hpt_insert(kvm_t *kd, vm_paddr_t pa, int64_t off) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); hpte = malloc(sizeof(*hpte)); hpte->pa = pa; hpte->off = off; - hpte->next = kd->vmst->hpt_head[fnv]; - kd->vmst->hpt_head[fnv] = hpte; + hpte->next = kd->vmst->hpt_head[hash]; + kd->vmst->hpt_head[hash] = hpte; } static int64_t hpt_find(kvm_t *kd, vm_paddr_t pa) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); - for (hpte = kd->vmst->hpt_head[fnv]; hpte != NULL; hpte = hpte->next) { + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); + for (hpte = kd->vmst->hpt_head[hash]; hpte != NULL; hpte = hpte->next) { if (pa == hpte->pa) return (hpte->off); } diff --git a/lib/libkvm/kvm_minidump_arm.c b/lib/libkvm/kvm_minidump_arm.c index d48c1bc..f42f4ca 100644 --- a/lib/libkvm/kvm_minidump_arm.c +++ b/lib/libkvm/kvm_minidump_arm.c @@ -38,7 +38,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -77,26 +77,26 @@ static void hpt_insert(kvm_t *kd, uint64_t pa, int64_t off) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); hpte = malloc(sizeof(*hpte)); hpte->pa = pa; hpte->off = off; - hpte->next = kd->vmst->hpt_head[fnv]; - kd->vmst->hpt_head[fnv] = hpte; + hpte->next = kd->vmst->hpt_head[hash]; + kd->vmst->hpt_head[hash] = hpte; } static int64_t hpt_find(kvm_t *kd, uint64_t pa) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); - for (hpte = kd->vmst->hpt_head[fnv]; hpte != NULL; hpte = hpte->next) + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); + for (hpte = kd->vmst->hpt_head[hash]; hpte != NULL; hpte = hpte->next) if (pa == hpte->pa) return (hpte->off); diff --git a/lib/libkvm/kvm_minidump_i386.c b/lib/libkvm/kvm_minidump_i386.c index 0d31705..343d70e 100644 --- a/lib/libkvm/kvm_minidump_i386.c +++ b/lib/libkvm/kvm_minidump_i386.c @@ -35,7 +35,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -76,26 +76,26 @@ static void hpt_insert(kvm_t *kd, uint64_t pa, int64_t off) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); hpte = malloc(sizeof(*hpte)); hpte->pa = pa; hpte->off = off; - hpte->next = kd->vmst->hpt_head[fnv]; - kd->vmst->hpt_head[fnv] = hpte; + hpte->next = kd->vmst->hpt_head[hash]; + kd->vmst->hpt_head[hash] = hpte; } static int64_t hpt_find(kvm_t *kd, uint64_t pa) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash ; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); - for (hpte = kd->vmst->hpt_head[fnv]; hpte != NULL; hpte = hpte->next) { + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); + for (hpte = kd->vmst->hpt_head[hash]; hpte != NULL; hpte = hpte->next) { if (pa == hpte->pa) return (hpte->off); } diff --git a/lib/libkvm/kvm_minidump_mips.c b/lib/libkvm/kvm_minidump_mips.c index c82e249..a97da93 100644 --- a/lib/libkvm/kvm_minidump_mips.c +++ b/lib/libkvm/kvm_minidump_mips.c @@ -39,7 +39,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -78,26 +78,26 @@ static void hpt_insert(kvm_t *kd, uint64_t pa, int64_t off) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); hpte = malloc(sizeof(*hpte)); hpte->pa = pa; hpte->off = off; - hpte->next = kd->vmst->hpt_head[fnv]; - kd->vmst->hpt_head[fnv] = hpte; + hpte->next = kd->vmst->hpt_head[hash]; + kd->vmst->hpt_head[hash] = hpte; } static int64_t hpt_find(kvm_t *kd, uint64_t pa) { struct hpte *hpte; - uint32_t fnv = FNV1_32_INIT; + uint32_t hash; - fnv = fnv_32_buf(&pa, sizeof(pa), fnv); - fnv &= (HPT_SIZE - 1); - for (hpte = kd->vmst->hpt_head[fnv]; hpte != NULL; hpte = hpte->next) + hash = hash_sfh_buf(&pa, sizeof(pa), sizeof(pa)); + hash &= (HPT_SIZE - 1); + for (hpte = kd->vmst->hpt_head[hash]; hpte != NULL; hpte = hpte->next) if (pa == hpte->pa) return (hpte->off); diff --git a/sys/dev/drm/drm_hashtab.c b/sys/dev/drm/drm_hashtab.c index 360c02b..b638a11 100644 --- a/sys/dev/drm/drm_hashtab.c +++ b/sys/dev/drm/drm_hashtab.c @@ -62,7 +62,7 @@ void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key) unsigned int hashed_key; int count = 0; - hashed_key = hash32_buf(&key, sizeof(key), ht->order); + hashed_key = hash_sfh_buf(&key, sizeof(key), ht->order); DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key); h_list = &ht->table[hashed_key & ht->mask]; LIST_FOREACH(entry, h_list, head) @@ -76,7 +76,7 @@ drm_ht_find_key(struct drm_open_hash *ht, unsigned long key) struct drm_hash_item_list *h_list; unsigned int hashed_key; - hashed_key = hash32_buf(&key, sizeof(key), ht->order); + hashed_key = hash_sfh_buf(&key, sizeof(key), ht->order); h_list = &ht->table[hashed_key & ht->mask]; LIST_FOREACH(entry, h_list, head) { if (entry->key == key) @@ -95,7 +95,7 @@ int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item) unsigned int hashed_key; unsigned long key = item->key; - hashed_key = hash32_buf(&key, sizeof(key), ht->order); + hashed_key = hash_sfh_buf(&key, sizeof(key), ht->order); h_list = &ht->table[hashed_key & ht->mask]; parent = NULL; LIST_FOREACH(entry, h_list, head) { @@ -125,7 +125,7 @@ int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *it unsigned long mask = (1 << bits) - 1; unsigned long first, unshifted_key = 0; - unshifted_key = hash32_buf(&seed, sizeof(seed), unshifted_key); + unshifted_key = hash_sfh_buf(&seed, sizeof(seed), unshifted_key); first = unshifted_key; do { item->key = (unshifted_key << shift) + add; diff --git a/sys/fs/nfsserver/nfs_nfsdport.c b/sys/fs/nfsserver/nfs_nfsdport.c index 380aa72..cf28457 100644 --- a/sys/fs/nfsserver/nfs_nfsdport.c +++ b/sys/fs/nfsserver/nfs_nfsdport.c @@ -3096,7 +3096,8 @@ nfsrv_hashfh(fhandle_t *fhp) { uint32_t hashval; - hashval = hash32_buf(&fhp->fh_fid, sizeof(struct fid), 0); + hashval = hash_sfh_buf(&fhp->fh_fid, sizeof(struct fid), + sizeof(struct fid)); return (hashval); } diff --git a/sys/kern/uipc_sem.c b/sys/kern/uipc_sem.c index 5270078..b3a8882 100644 --- a/sys/kern/uipc_sem.c +++ b/sys/kern/uipc_sem.c @@ -42,7 +42,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -86,7 +86,7 @@ __FBSDID("$FreeBSD$"); struct ksem_mapping { char *km_path; - Fnv32_t km_fnv; + uint32_t km_hash; struct ksem *km_ksem; LIST_ENTRY(ksem_mapping) km_link; }; @@ -99,7 +99,7 @@ static struct mtx sem_lock; static u_long ksem_hash; static int ksem_dead; -#define KSEM_HASH(fnv) (&ksem_dictionary[(fnv) & ksem_hash]) +#define KSEM_HASH(h) (&ksem_dictionary[(h) & ksem_hash]) static int nsems = 0; SYSCTL_DECL(_p1003_1b); @@ -117,11 +117,11 @@ static int ksem_create(struct thread *td, const char *path, static void ksem_drop(struct ksem *ks); static int ksem_get(struct thread *td, semid_t id, struct file **fpp); static struct ksem *ksem_hold(struct ksem *ks); -static void ksem_insert(char *path, Fnv32_t fnv, struct ksem *ks); -static struct ksem *ksem_lookup(char *path, Fnv32_t fnv); +static void ksem_insert(char *path, uint32_t hash, struct ksem *ks); +static struct ksem *ksem_lookup(char *path, uint32_t hash); static void ksem_module_destroy(void); static int ksem_module_init(void); -static int ksem_remove(char *path, Fnv32_t fnv, struct ucred *ucred); +static int ksem_remove(char *path, uint32_t hash, struct ucred *ucred); static int sem_modload(struct module *module, int cmd, void *arg); static fo_rdwr_t ksem_read; @@ -316,16 +316,16 @@ ksem_access(struct ksem *ks, struct ucred *ucred) /* * Dictionary management. We maintain an in-kernel dictionary to map - * paths to semaphore objects. We use the FNV hash on the path to + * paths to semaphore objects. We use the hash on the path to * store the mappings in a hash table. */ static struct ksem * -ksem_lookup(char *path, Fnv32_t fnv) +ksem_lookup(char *path, uint32_t hash) { struct ksem_mapping *map; - LIST_FOREACH(map, KSEM_HASH(fnv), km_link) { - if (map->km_fnv != fnv) + LIST_FOREACH(map, KSEM_HASH(hash), km_link) { + if (map->km_hash != hash) continue; if (strcmp(map->km_path, path) == 0) return (map->km_ksem); @@ -335,25 +335,25 @@ ksem_lookup(char *path, Fnv32_t fnv) } static void -ksem_insert(char *path, Fnv32_t fnv, struct ksem *ks) +ksem_insert(char *path, uint32_t hash, struct ksem *ks) { struct ksem_mapping *map; map = malloc(sizeof(struct ksem_mapping), M_KSEM, M_WAITOK); map->km_path = path; - map->km_fnv = fnv; + map->km_hash = hash; map->km_ksem = ksem_hold(ks); - LIST_INSERT_HEAD(KSEM_HASH(fnv), map, km_link); + LIST_INSERT_HEAD(KSEM_HASH(hash), map, km_link); } static int -ksem_remove(char *path, Fnv32_t fnv, struct ucred *ucred) +ksem_remove(char *path, uint32_t hash, struct ucred *ucred) { struct ksem_mapping *map; int error; - LIST_FOREACH(map, KSEM_HASH(fnv), km_link) { - if (map->km_fnv != fnv) + LIST_FOREACH(map, KSEM_HASH(hash), km_link) { + if (map->km_hash != hash) continue; if (strcmp(map->km_path, path) == 0) { #ifdef MAC @@ -413,7 +413,8 @@ ksem_create(struct thread *td, const char *name, semid_t *semidp, mode_t mode, struct ksem *ks; struct file *fp; char *path; - Fnv32_t fnv; + size_t pathlen; + uint32_t hash; int error, fd; if (value > SEM_VALUE_MAX) @@ -449,7 +450,7 @@ ksem_create(struct thread *td, const char *name, semid_t *semidp, mode_t mode, ks->ks_flags |= KS_ANONYMOUS; } else { path = malloc(MAXPATHLEN, M_KSEM, M_WAITOK); - error = copyinstr(name, path, MAXPATHLEN, NULL); + error = copyinstr(name, path, MAXPATHLEN, &pathlen); /* Require paths to start with a '/' character. */ if (error == 0 && path[0] != '/') @@ -461,9 +462,9 @@ ksem_create(struct thread *td, const char *name, semid_t *semidp, mode_t mode, return (error); } - fnv = fnv_32_str(path, FNV1_32_INIT); + hash = hash_sfh_buf(path, pathlen, pathlen); sx_xlock(&ksem_dict_lock); - ks = ksem_lookup(path, fnv); + ks = ksem_lookup(path, hash); if (ks == NULL) { /* Object does not exist, create it if requested. */ if (flags & O_CREAT) { @@ -471,7 +472,7 @@ ksem_create(struct thread *td, const char *name, semid_t *semidp, mode_t mode, if (ks == NULL) error = ENFILE; else { - ksem_insert(path, fnv, ks); + ksem_insert(path, hash, ks); path = NULL; } } else @@ -591,19 +592,20 @@ int ksem_unlink(struct thread *td, struct ksem_unlink_args *uap) { char *path; - Fnv32_t fnv; + size_t pathlen; + uint32_t hash; int error; path = malloc(MAXPATHLEN, M_TEMP, M_WAITOK); - error = copyinstr(uap->name, path, MAXPATHLEN, NULL); + error = copyinstr(uap->name, path, MAXPATHLEN, &pathlen); if (error) { free(path, M_TEMP); return (error); } - fnv = fnv_32_str(path, FNV1_32_INIT); + hash = hash_sfh_buf(path, pathlen, pathlen); sx_xlock(&ksem_dict_lock); - error = ksem_remove(path, fnv, td->td_ucred); + error = ksem_remove(path, hash, td->td_ucred); sx_xunlock(&ksem_dict_lock); free(path, M_TEMP); diff --git a/sys/kern/uipc_shm.c b/sys/kern/uipc_shm.c index cef8317..a8f68b7 100644 --- a/sys/kern/uipc_shm.c +++ b/sys/kern/uipc_shm.c @@ -59,7 +59,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -89,7 +89,7 @@ __FBSDID("$FreeBSD$"); struct shm_mapping { char *sm_path; - Fnv32_t sm_fnv; + uint32_t sm_hash; struct shmfd *sm_shmfd; LIST_ENTRY(shm_mapping) sm_link; }; @@ -100,16 +100,16 @@ static struct sx shm_dict_lock; static struct mtx shm_timestamp_lock; static u_long shm_hash; -#define SHM_HASH(fnv) (&shm_dictionary[(fnv) & shm_hash]) +#define SHM_HASH(h) (&shm_dictionary[(h) & shm_hash]) static int shm_access(struct shmfd *shmfd, struct ucred *ucred, int flags); static struct shmfd *shm_alloc(struct ucred *ucred, mode_t mode); static void shm_dict_init(void *arg); static void shm_drop(struct shmfd *shmfd); static struct shmfd *shm_hold(struct shmfd *shmfd); -static void shm_insert(char *path, Fnv32_t fnv, struct shmfd *shmfd); -static struct shmfd *shm_lookup(char *path, Fnv32_t fnv); -static int shm_remove(char *path, Fnv32_t fnv, struct ucred *ucred); +static void shm_insert(char *path, uint32_t hash, struct shmfd *shmfd); +static struct shmfd *shm_lookup(char *path, uint32_t hash); +static int shm_remove(char *path, uint32_t hash, struct ucred *ucred); static int shm_dotruncate(struct shmfd *shmfd, off_t length); static fo_rdwr_t shm_read; @@ -404,7 +404,7 @@ shm_access(struct shmfd *shmfd, struct ucred *ucred, int flags) /* * Dictionary management. We maintain an in-kernel dictionary to map - * paths to shmfd objects. We use the FNV hash on the path to store + * paths to shmfd objects. We use the hash on the path to store * the mappings in a hash table. */ static void @@ -418,12 +418,12 @@ shm_dict_init(void *arg) SYSINIT(shm_dict_init, SI_SUB_SYSV_SHM, SI_ORDER_ANY, shm_dict_init, NULL); static struct shmfd * -shm_lookup(char *path, Fnv32_t fnv) +shm_lookup(char *path, uint32_t hash) { struct shm_mapping *map; - LIST_FOREACH(map, SHM_HASH(fnv), sm_link) { - if (map->sm_fnv != fnv) + LIST_FOREACH(map, SHM_HASH(hash), sm_link) { + if (map->sm_hash != hash) continue; if (strcmp(map->sm_path, path) == 0) return (map->sm_shmfd); @@ -433,25 +433,25 @@ shm_lookup(char *path, Fnv32_t fnv) } static void -shm_insert(char *path, Fnv32_t fnv, struct shmfd *shmfd) +shm_insert(char *path, uint32_t hash, struct shmfd *shmfd) { struct shm_mapping *map; map = malloc(sizeof(struct shm_mapping), M_SHMFD, M_WAITOK); map->sm_path = path; - map->sm_fnv = fnv; + map->sm_hash = hash; map->sm_shmfd = shm_hold(shmfd); - LIST_INSERT_HEAD(SHM_HASH(fnv), map, sm_link); + LIST_INSERT_HEAD(SHM_HASH(hash), map, sm_link); } static int -shm_remove(char *path, Fnv32_t fnv, struct ucred *ucred) +shm_remove(char *path, uint32_t hash, struct ucred *ucred) { struct shm_mapping *map; int error; - LIST_FOREACH(map, SHM_HASH(fnv), sm_link) { - if (map->sm_fnv != fnv) + LIST_FOREACH(map, SHM_HASH(hash), sm_link) { + if (map->sm_hash != hash) continue; if (strcmp(map->sm_path, path) == 0) { #ifdef MAC @@ -482,7 +482,8 @@ shm_open(struct thread *td, struct shm_open_args *uap) struct shmfd *shmfd; struct file *fp; char *path; - Fnv32_t fnv; + size_t pathlen; + uint32_t hash; mode_t cmode; int fd, error; @@ -511,7 +512,7 @@ shm_open(struct thread *td, struct shm_open_args *uap) shmfd = shm_alloc(td->td_ucred, cmode); } else { path = malloc(MAXPATHLEN, M_SHMFD, M_WAITOK); - error = copyinstr(uap->path, path, MAXPATHLEN, NULL); + error = copyinstr(uap->path, path, MAXPATHLEN, &pathlen); /* Require paths to start with a '/' character. */ if (error == 0 && path[0] != '/') @@ -523,14 +524,14 @@ shm_open(struct thread *td, struct shm_open_args *uap) return (error); } - fnv = fnv_32_str(path, FNV1_32_INIT); + hash = hash_sfh_buf(path, pathlen, pathlen); sx_xlock(&shm_dict_lock); - shmfd = shm_lookup(path, fnv); + shmfd = shm_lookup(path, hash); if (shmfd == NULL) { /* Object does not yet exist, create it if requested. */ if (uap->flags & O_CREAT) { shmfd = shm_alloc(td->td_ucred, cmode); - shm_insert(path, fnv, shmfd); + shm_insert(path, hash, shmfd); } else { free(path, M_SHMFD); error = ENOENT; @@ -597,19 +598,20 @@ int shm_unlink(struct thread *td, struct shm_unlink_args *uap) { char *path; - Fnv32_t fnv; + size_t pathlen; + uint32_t hash; int error; path = malloc(MAXPATHLEN, M_TEMP, M_WAITOK); - error = copyinstr(uap->path, path, MAXPATHLEN, NULL); + error = copyinstr(uap->path, path, MAXPATHLEN, &pathlen); if (error) { free(path, M_TEMP); return (error); } - fnv = fnv_32_str(path, FNV1_32_INIT); + hash = hash_sfh_buf(path, pathlen, pathlen); sx_xlock(&shm_dict_lock); - error = shm_remove(path, fnv, td->td_ucred); + error = shm_remove(path, hash, td->td_ucred); sx_xunlock(&shm_dict_lock); free(path, M_TEMP); diff --git a/sys/kern/vfs_cache.c b/sys/kern/vfs_cache.c index 30fb28b..61f87df 100644 --- a/sys/kern/vfs_cache.c +++ b/sys/kern/vfs_cache.c @@ -40,7 +40,7 @@ __FBSDID("$FreeBSD$"); #include #include -#include +#include #include #include #include @@ -455,8 +455,8 @@ retry_wlocked: } } - hash = fnv_32_buf(cnp->cn_nameptr, cnp->cn_namelen, FNV1_32_INIT); - hash = fnv_32_buf(&dvp, sizeof(dvp), hash); + hash = hash_sfh_buf(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_namelen); + hash = hash_sfh_buf(&dvp, sizeof(dvp), hash); LIST_FOREACH(ncp, (NCHHASH(hash)), nc_hash) { numchecks++; if (ncp->nc_dvp == dvp && ncp->nc_nlen == cnp->cn_namelen && @@ -691,9 +691,9 @@ cache_enter(dvp, vp, cnp) ncp->nc_dvp = dvp; ncp->nc_flag = flag; len = ncp->nc_nlen = cnp->cn_namelen; - hash = fnv_32_buf(cnp->cn_nameptr, len, FNV1_32_INIT); + hash = hash_sfh_buf(cnp->cn_nameptr, len, len); strlcpy(ncp->nc_name, cnp->cn_nameptr, len + 1); - hash = fnv_32_buf(&dvp, sizeof(dvp), hash); + hash = hash_sfh_buf(&dvp, sizeof(dvp), hash); CACHE_WLOCK(); /* diff --git a/sys/net/if_lagg.c b/sys/net/if_lagg.c index 8911cee..a587c54 100644 --- a/sys/net/if_lagg.c +++ b/sys/net/if_lagg.c @@ -35,7 +35,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -1414,19 +1414,19 @@ lagg_hashmbuf(struct mbuf *m, uint32_t key) goto out; eh = mtod(m, struct ether_header *); etype = ntohs(eh->ether_type); - p = hash32_buf(&eh->ether_shost, ETHER_ADDR_LEN, key); - p = hash32_buf(&eh->ether_dhost, ETHER_ADDR_LEN, p); + p = hash_sfh_buf(&eh->ether_shost, ETHER_ADDR_LEN, key); + p = hash_sfh_buf(&eh->ether_dhost, ETHER_ADDR_LEN, p); /* Special handling for encapsulating VLAN frames */ if (m->m_flags & M_VLANTAG) { - p = hash32_buf(&m->m_pkthdr.ether_vtag, + p = hash_sfh_buf(&m->m_pkthdr.ether_vtag, sizeof(m->m_pkthdr.ether_vtag), p); } else if (etype == ETHERTYPE_VLAN) { vlan = lagg_gethdr(m, off, sizeof(*vlan), &vlanbuf); if (vlan == NULL) goto out; - p = hash32_buf(&vlan->evl_tag, sizeof(vlan->evl_tag), p); + p = hash_sfh_buf(&vlan->evl_tag, sizeof(vlan->evl_tag), p); etype = ntohs(vlan->evl_proto); off += sizeof(*vlan) - sizeof(*eh); } @@ -1438,8 +1438,8 @@ lagg_hashmbuf(struct mbuf *m, uint32_t key) if (ip == NULL) goto out; - p = hash32_buf(&ip->ip_src, sizeof(struct in_addr), p); - p = hash32_buf(&ip->ip_dst, sizeof(struct in_addr), p); + p = hash_sfh_buf(&ip->ip_src, sizeof(struct in_addr), p); + p = hash_sfh_buf(&ip->ip_dst, sizeof(struct in_addr), p); break; #endif #ifdef INET6 @@ -1448,10 +1448,10 @@ lagg_hashmbuf(struct mbuf *m, uint32_t key) if (ip6 == NULL) goto out; - p = hash32_buf(&ip6->ip6_src, sizeof(struct in6_addr), p); - p = hash32_buf(&ip6->ip6_dst, sizeof(struct in6_addr), p); + p = hash_sfh_buf(&ip6->ip6_src, sizeof(struct in6_addr), p); + p = hash_sfh_buf(&ip6->ip6_dst, sizeof(struct in6_addr), p); flow = ip6->ip6_flow & IPV6_FLOWLABEL_MASK; - p = hash32_buf(&flow, sizeof(flow), p); /* IPv6 flow label */ + p = hash_sfh_buf(&flow, sizeof(flow), p); /* IPv6 flow label */ break; #endif } diff --git a/sys/netinet/in_var.h b/sys/netinet/in_var.h index cd1d904..a4fda4a 100644 --- a/sys/netinet/in_var.h +++ b/sys/netinet/in_var.h @@ -34,7 +34,7 @@ #define _NETINET_IN_VAR_H_ #include -#include +#include #include struct igmp_ifinfo; @@ -113,7 +113,7 @@ VNET_DECLARE(u_long, in_ifaddrhmask); /* mask for hash table */ #define INADDR_NHASH_LOG2 9 #define INADDR_NHASH (1 << INADDR_NHASH_LOG2) -#define INADDR_HASHVAL(x) fnv_32_buf((&(x)), sizeof(x), FNV1_32_INIT) +#define INADDR_HASHVAL(x) hash_sfh_buf((&(x)), sizeof(x), sizeof(x)) #define INADDR_HASH(x) \ (&V_in_ifaddrhashtbl[INADDR_HASHVAL(x) & V_in_ifaddrhmask]) diff --git a/sys/netinet/siftr.c b/sys/netinet/siftr.c index b5db118..6fca4ca 100644 --- a/sys/netinet/siftr.c +++ b/sys/netinet/siftr.c @@ -63,7 +63,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -353,7 +353,7 @@ siftr_process_pkt(struct pkt_node * pkt_node) sizeof(pkt_node->tcp_foreignport)); counter_list = counter_hash + - (hash32_buf(key, sizeof(key), 0) & siftr_hashmask); + (hash_sfh_buf(key, sizeof(key), sizeof(key)) & siftr_hashmask); /* * If the list is not empty i.e. the hash index has @@ -364,7 +364,7 @@ siftr_process_pkt(struct pkt_node * pkt_node) * Loop through the hash nodes in the list. * There should normally only be 1 hash node in the list, * except if there have been collisions at the hash index - * computed by hash32_buf(). + * computed by hash_sfh_buf(). */ LIST_FOREACH(hash_node, counter_list, nodes) { /* @@ -640,7 +640,7 @@ hash_pkt(struct mbuf *m, uint32_t offset) while (m != NULL) { /* Ensure there is data in the mbuf */ if ((m->m_len - offset) > 0) - hash = hash32_buf(m->m_data + offset, + hash = hash_sfh_buf(m->m_data + offset, m->m_len - offset, hash); m = m->m_next; diff --git a/sys/nfsclient/nfs_node.c b/sys/nfsclient/nfs_node.c index 5b43b3d..821dc2a 100644 --- a/sys/nfsclient/nfs_node.c +++ b/sys/nfsclient/nfs_node.c @@ -38,7 +38,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -113,7 +113,7 @@ nfs_nget(struct mount *mntp, nfsfh_t *fhp, int fhsize, struct nfsnode **npp, int nmp = VFSTONFS(mntp); *npp = NULL; - hash = fnv_32_buf(fhp->fh_bytes, fhsize, FNV1_32_INIT); + hash = hash_sfh_buf(fhp->fh_bytes, fhsize, fhsize); ncmp.fhsize = fhsize; ncmp.fh = fhp; diff --git a/sys/sys/hash_sfh.h b/sys/sys/hash_sfh.h new file mode 100644 index 0000000..bd6d687 --- /dev/null +++ b/sys/sys/hash_sfh.h @@ -0,0 +1,89 @@ +/*- + * Copyright (c) 2010, Paul Hsieh + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. My name, Paul Hsieh, and the names of any other contributors to + * the code use may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#ifndef _SYS_HASH_SFH_H_ +#define _SYS_HASH_SFH_H_ +#include + +static __inline uint32_t +hash_sfh_buf(const void *buf, size_t len, uint32_t hash) +{ + const uint8_t *data = buf; + uint32_t tmp; + int rem; + + if (len <= 0 || data == NULL) + return (0); + + rem = len & 3; + len >>= 2; + +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ + +(uint32_t)(((const uint8_t *)(d))[0]) ) + + /* Main loop */ + for (;len > 0; len--) { + hash += get16bits(data); + tmp = (get16bits(data + 2) << 11) ^ hash; + hash = (hash << 16) ^ tmp; + data += 2 * sizeof(uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: hash += get16bits(data); + hash ^= hash << 16; + hash ^= data[sizeof(uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += get16bits(data); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *data; + hash ^= hash << 10; + hash += hash >> 1; + } +#undef get16bits + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return (hash); +} +#endif /* !_SYS_HASH_SFH_H_ */ diff --git a/sys/ufs/ufs/ufs_dirhash.c b/sys/ufs/ufs/ufs_dirhash.c index 9c89689..6cd8d0b 100644 --- a/sys/ufs/ufs/ufs_dirhash.c +++ b/sys/ufs/ufs/ufs_dirhash.c @@ -40,7 +40,7 @@ __FBSDID("$FreeBSD$"); #include #include #include -#include +#include #include #include #include @@ -1039,8 +1039,8 @@ ufsdirhash_hash(struct dirhash *dh, char *name, int namelen) * differing only in the last byte are placed close to one * another in the table, which is bad for linear probing. */ - hash = fnv_32_buf(name, namelen, FNV1_32_INIT); - hash = fnv_32_buf(&dh, sizeof(dh), hash); + hash = hash_sfh_buf(name, namelen, namelen); + hash = hash_sfh_buf(&dh, sizeof(dh), hash); return (hash % dh->dh_hlen); } --J/dobhs11T7y2rNN--