[Sheepdog] [PATCH] change the hash function from SHA1 to FNV-1a (client patch)

MORITA Kazutaka morita.kazutaka at lab.ntt.co.jp
Mon Dec 21 11:46:56 CET 2009


This is a patch for the client (qemu-kvm) tree.
=
>From 93549f6fc031d8b95048ba913a8c451fe67c063e Mon Sep 17 00:00:00 2001
From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
Date: Mon, 21 Dec 2009 18:39:36 +0900
Subject: [PATCH] change the hash function from SHA1 (160 bit) to FNV-1a (64 bit)

Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
---
 Makefile         |    2 +-
 Makefile.target  |    2 +-
 block/sheepdog.c |   36 ++++++++++++++++++++++++------------
 3 files changed, 26 insertions(+), 14 deletions(-)

diff --git a/Makefile b/Makefile
index 45969cb..84a39e4 100644
--- a/Makefile
+++ b/Makefile
@@ -16,7 +16,7 @@ endif
 
 VPATH=$(SRC_PATH):$(SRC_PATH)/hw
 
-LIBS+=-lz -lcrypto $(LIBS_TOOLS)
+LIBS+=-lz $(LIBS_TOOLS)
 
 ifdef BUILD_DOCS
 DOCS=qemu-doc.html qemu-tech.html qemu.1 qemu-img.1 qemu-nbd.8
diff --git a/Makefile.target b/Makefile.target
index 08417da..e991fa3 100644
--- a/Makefile.target
+++ b/Makefile.target
@@ -21,7 +21,7 @@ endif
 
 PROGS=$(QEMU_PROG)
 
-LIBS+=-lm -lcrypto
+LIBS+=-lm
 
 kvm.o kvm-all.o: QEMU_CFLAGS+=$(KVM_CFLAGS)
 
diff --git a/block/sheepdog.c b/block/sheepdog.c
index b61aa26..5dd8fcd 100644
--- a/block/sheepdog.c
+++ b/block/sheepdog.c
@@ -21,7 +21,6 @@
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <poll.h>
-#include <openssl/sha.h>
 #include <pthread.h>
 
 #include "qemu-common.h"
@@ -273,7 +272,7 @@ struct bdrv_sd_state {
 };
 
 struct sheepdog_node_list_entry {
-	uint8_t         id[20];
+	uint64_t        id;
 	uint8_t         addr[16];
 	uint16_t        port;
 	uint16_t	pad;
@@ -359,25 +358,38 @@ static inline int is_data_obj(uint64_t oid)
 	return oid & ((1ULL << 18) - 1);
 }
 
+/*
+ * 64 bit FNV-1a non-zero initial basis
+ */
+#define FNV1A_64_INIT ((uint64_t)0xcbf29ce484222325ULL)
+
+/*
+ * 64 bit Fowler/Noll/Vo FNV-1a hash code
+ */
+static inline uint64_t fnv_64a_buf(void *buf, size_t len, uint64_t hval)
+{
+        unsigned char *bp = (unsigned char *) buf;
+        unsigned char *be = bp + len;
+        while (bp < be) {
+                hval ^= (uint64_t) *bp++;
+                hval += (hval << 1) + (hval << 4) + (hval << 5) +
+                        (hval << 7) + (hval << 8) + (hval << 40);
+        }
+        return hval;
+}
+
 static inline int obj_to_sheep(struct sheepdog_node_list_entry *entries,
 			       int nr_entries, uint64_t oid, int idx)
 {
-	SHA_CTX ctx;
-	uint8_t id[20];
+	uint64_t id;
 	int i;
 	struct sheepdog_node_list_entry *e = entries, *n;
 
-	SHA1_Init(&ctx);
-
-	SHA1_Update(&ctx, &oid, sizeof(oid));
-
-	SHA1_Final(id, &ctx);
+	id = fnv_64a_buf(&oid, sizeof(oid), FNV1A_64_INIT);
 
 	for (i = 0; i < nr_entries - 1; i++, e++) {
 		n = e + 1;
-
-		if (memcmp(id, e->id, sizeof(id)) > 0 &&
-		    memcmp(id, n->id, sizeof(id)) <= 0)
+		if (id > e->id && id <= n->id)
 			break;
 	}
 
-- 
1.5.6.5




More information about the sheepdog mailing list