socsvn commit: r237063 - soc2012/gpf/pefs_kmod/sbin/pefs
gpf at FreeBSD.org
gpf at FreeBSD.org
Mon Jun 4 14:27:07 UTC 2012
Author: gpf
Date: Mon Jun 4 14:27:04 2012
New Revision: 237063
URL: http://svnweb.FreeBSD.org/socsvn/?view=rev&rev=237063
Log:
use FNV as hash function no2
Modified:
soc2012/gpf/pefs_kmod/sbin/pefs/pefs_checksum.c
Modified: soc2012/gpf/pefs_kmod/sbin/pefs/pefs_checksum.c
==============================================================================
--- soc2012/gpf/pefs_kmod/sbin/pefs/pefs_checksum.c Mon Jun 4 13:41:22 2012 (r237062)
+++ soc2012/gpf/pefs_kmod/sbin/pefs/pefs_checksum.c Mon Jun 4 14:27:04 2012 (r237063)
@@ -34,6 +34,7 @@
#include <sys/queue.h>
#include <sys/types.h>
#include <sys/stat.h>
+#include <sys/fnv_hash.h>
#include <ctype.h>
#include <dirent.h>
@@ -266,7 +267,7 @@
chtp->buckets1 = NULL;
chtp->buckets2 = NULL;
}
-
+
static int
pefs_allocate_hash_table(struct cuckoo_hash_table *chtp, uint32_t nelements, char reallocate)
{
@@ -362,26 +363,18 @@
uint32_t nbucket;
nbucket = fhp->file_id % chtp->size;
- dprintf(("hash1: goto bucket %d\n", nbucket));
+ printf("hash1: goto bucket %d\n", nbucket);
return (nbucket);
}
-/*
- * XXXgpf: [TODO] change hash2
- * gleb says:
- * http://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
- * Yes, I've mentioned it because it's available under
- * /usr/include/sys/fnv_hash.h
- * murmur3 has good performance/collisions characteristics.
- */
-
static uint32_t
pefs_hash2(struct cuckoo_hash_table *chtp, struct file_header *fhp)
{
uint32_t nbucket;
- nbucket = (fhp->file_id / chtp->size) % chtp->size;
- dprintf(("hash2: goto bucket %d\n", nbucket));
+ nbucket = fnv_64_buf(&(fhp->file_id), sizeof(fhp->file_id), FNV1_64_INIT) % chtp->size;
+ printf("hash2: goto bucket %d\n", nbucket);
+
return (nbucket);
}
@@ -433,6 +426,7 @@
elem = elem2;
}
+ /* XXXgpf: should be left as a warning at least during development phase */
pefs_warn("cuckoo_insert resulted in infinite loop!");
return (PEFS_ERR_GENERIC);
}
@@ -615,7 +609,7 @@
* C) Cuckoo insertion:
* We try to populate our hash tables using the cuckoo algorithm. Should we fall
* into an infinite loop during insertion, we re-allocate larger hash tables
- * and try again until we succeed. The possibility to fail twice in a row is
+ * and try again until we succeed. The possibility to fail twice in a row is
* 1.5% * 1.5% = 0.0225%
*/
static int
@@ -659,9 +653,9 @@
}
cuckoo_insert:
- TAILQ_FOREACH(fhp, &fh_head, file_header_entries) {
+ TAILQ_FOREACH(fhp, &fh_head, file_header_entries) {
error = pefs_add_to_hash_table(chtp, fhp);
- /*
+ /*
* cuckoo insertion algorithm fell into an infinite loop!
* Create new, larger hash tables where size = next_prime(old_size)
* and try again.
@@ -674,7 +668,6 @@
goto cuckoo_insert;
}
}
-
pefs_print_hash_table(chtp, hash_len);
return (error);
More information about the svn-soc-all
mailing list