From owner-svn-soc-all@FreeBSD.ORG Mon Jun 4 14:27:07 2012 Return-Path: Delivered-To: svn-soc-all@FreeBSD.org Received: from socsvn.FreeBSD.org (unknown [IPv6:2001:4f8:fff6::2f]) by hub.freebsd.org (Postfix) with SMTP id E1307106564A for ; Mon, 4 Jun 2012 14:27:04 +0000 (UTC) (envelope-from gpf@FreeBSD.org) Received: by socsvn.FreeBSD.org (sSMTP sendmail emulation); Mon, 04 Jun 2012 14:27:04 +0000 Date: Mon, 04 Jun 2012 14:27:04 +0000 From: gpf@FreeBSD.org To: svn-soc-all@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Message-Id: <20120604142704.E1307106564A@hub.freebsd.org> Cc: Subject: socsvn commit: r237063 - soc2012/gpf/pefs_kmod/sbin/pefs X-BeenThere: svn-soc-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for the entire Summer of Code repository List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 04 Jun 2012 14:27:07 -0000 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 #include #include +#include #include #include @@ -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);