Date: Mon, 04 Jun 2012 14:27:04 +0000 From: gpf@FreeBSD.org To: svn-soc-all@FreeBSD.org Subject: socsvn commit: r237063 - soc2012/gpf/pefs_kmod/sbin/pefs Message-ID: <20120604142704.E1307106564A@hub.freebsd.org>
next in thread | raw e-mail | index | archive | help
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);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20120604142704.E1307106564A>