[rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash
Gleb Kurtsou
gleb.kurtsou at gmail.com
Thu Dec 23 23:18:05 UTC 2010
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.
-------------- next part --------------
commit 6e19401826b6769fa95b1e4f9e561dec7101082b
Author: Gleb Kurtsou <gleb.kurtsou at gmail.com>
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 <sys/proc.h>
#include <sys/stat.h>
#include <sys/mman.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
@@ -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 <sys/proc.h>
#include <sys/stat.h>
#include <sys/mman.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
@@ -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 <sys/proc.h>
#include <sys/stat.h>
#include <sys/mman.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
@@ -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 <sys/proc.h>
#include <sys/stat.h>
#include <sys/mman.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
@@ -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 <sys/fcntl.h>
#include <sys/file.h>
#include <sys/filedesc.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <sys/kernel.h>
#include <sys/ksem.h>
#include <sys/lock.h>
@@ -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 <sys/fcntl.h>
#include <sys/file.h>
#include <sys/filedesc.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <sys/kernel.h>
#include <sys/lock.h>
#include <sys/malloc.h>
@@ -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 <sys/param.h>
#include <sys/filedesc.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <sys/kernel.h>
#include <sys/lock.h>
#include <sys/malloc.h>
@@ -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 <sys/priv.h>
#include <sys/systm.h>
#include <sys/proc.h>
-#include <sys/hash.h>
+#include <sys/hash_sfh.h>
#include <sys/lock.h>
#include <sys/rwlock.h>
#include <sys/taskqueue.h>
@@ -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 <sys/queue.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <sys/tree.h>
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 <sys/param.h>
#include <sys/alq.h>
#include <sys/errno.h>
-#include <sys/hash.h>
+#include <sys/hash_sfh.h>
#include <sys/kernel.h>
#include <sys/kthread.h>
#include <sys/lock.h>
@@ -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 <sys/param.h>
#include <sys/systm.h>
#include <sys/fcntl.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <sys/lock.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
@@ -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 <sys/types.h>
+
+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 <sys/lock.h>
#include <sys/mutex.h>
#include <sys/malloc.h>
-#include <sys/fnv_hash.h>
+#include <sys/hash_sfh.h>
#include <sys/proc.h>
#include <sys/bio.h>
#include <sys/buf.h>
@@ -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);
}
More information about the freebsd-hackers
mailing list