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

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


I'll change the hash function from SHA1 (160 bit) to FNV-1a (64 bit)
because 160 bit id is too long and non-cryptographic function is
enough to use for distributed key-value store. 

This is a patch for the server tree.
=
>From 08bb64a53e8184947a0fa769fe348395138cb03e Mon Sep 17 00:00:00 2001
From: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
Date: Mon, 21 Dec 2009 18:43:35 +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>
---
 collie/Makefile          |    2 +-
 collie/group.c           |   20 ++++++++++++++------
 collie/vdi.c             |    1 -
 include/meta.h           |    1 +
 include/sheepdog_proto.h |   42 +++++++++++++++++++++++++++---------------
 shepherd/Makefile        |    2 +-
 shepherd/shepherd.c      |    5 ++---
 7 files changed, 46 insertions(+), 27 deletions(-)

diff --git a/collie/Makefile b/collie/Makefile
index a3316e1..5e4beb0 100644
--- a/collie/Makefile
+++ b/collie/Makefile
@@ -2,7 +2,7 @@ sbindir ?= $(PREFIX)/sbin
 
 CFLAGS += -g -O2 -Wall -Wstrict-prototypes -I../include
 CFLAGS += -D_GNU_SOURCE
-LIBS += -lpthread -lcrypto -lcpg
+LIBS += -lpthread -lcpg
 
 PROGRAMS = collie
 COLLIE_OBJS = collie.o net.o vdi.o group.o store.o work.o ../lib/event.o ../lib/net.o ../lib/logger.o
diff --git a/collie/group.c b/collie/group.c
index a718afd..7f78f99 100644
--- a/collie/group.c
+++ b/collie/group.c
@@ -87,7 +87,12 @@ static int node_cmp(const void *a, const void *b)
 {
 	const struct sheepdog_node_list_entry *node1 = a;
 	const struct sheepdog_node_list_entry *node2 = b;
-	return memcmp(node1->id, node2->id, sizeof(node1->id));
+
+	if (node1->id < node2->id)
+		return -1;
+	if (node1->id > node2->id)
+		return 1;
+	return 0;
 }
 
 static int send_message(cpg_handle_t handle, struct message_header *msg)
@@ -673,10 +678,11 @@ struct cluster_info *create_cluster(int port)
 	struct cluster_info *ci;
 	struct addrinfo hints, *res;
 	char name[INET6_ADDRSTRLEN];
-	SHA_CTX ctx;
 	struct cpg_name group = { 8, "sheepdog" };
 	cpg_callbacks_t cb = { &sd_deliver, &sd_confch };
 	unsigned int nodeid = 0;
+	uint64_t hval;
+	int i;
 
 	ci = zalloc(sizeof(*ci));
 	if (!ci)
@@ -744,10 +750,12 @@ join_retry:
 
 	ci->this_node.port = port;
 
-	SHA1_Init(&ctx);
-	SHA1_Update(&ctx, ci->this_node.addr, sizeof(ci->this_node.addr));
-	SHA1_Update(&ctx, &ci->this_node.port, sizeof(ci->this_node.port));
-	SHA1_Final(ci->this_node.id, &ctx);
+	hval = fnv_64a_buf(&ci->this_node.port, sizeof(ci->this_node.port),
+			   FNV1A_64_INIT);
+	for (i = ARRAY_SIZE(ci->this_node.addr) - 1; i >= 0; i--)
+		hval = fnv_64a_buf(&ci->this_node.addr[i], 1, hval);
+
+	ci->this_node.id = hval;
 
 	ci->synchronized = 0;
 	INIT_LIST_HEAD(&ci->node_list);
diff --git a/collie/vdi.c b/collie/vdi.c
index 184a22e..298b0bc 100644
--- a/collie/vdi.c
+++ b/collie/vdi.c
@@ -11,7 +11,6 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <sys/time.h>
-#include <openssl/sha.h>
 
 #include "sheepdog_proto.h"
 #include "meta.h"
diff --git a/include/meta.h b/include/meta.h
index 73b63de..f3267fa 100644
--- a/include/meta.h
+++ b/include/meta.h
@@ -13,6 +13,7 @@
 
 #include <stdint.h>
 #include "util.h"
+#include "list.h"
 
 #define SD_DIR_OID 0
 #define SD_DATA_OBJ_SIZE (UINT64_C(1) << 22)
diff --git a/include/sheepdog_proto.h b/include/sheepdog_proto.h
index 40370b6..4147b95 100644
--- a/include/sheepdog_proto.h
+++ b/include/sheepdog_proto.h
@@ -12,7 +12,6 @@
 #define __SHEEPDOG_PROTO_H__
 
 #include <stdint.h>
-#include <openssl/sha.h>
 #include "util.h"
 
 #define SD_LISTEN_PORT 7000
@@ -186,31 +185,44 @@ struct sheepdog_vm_list_entry {
 };
 
 struct sheepdog_node_list_entry {
-	uint8_t         id[20];
+	uint64_t        id;
 	uint8_t         addr[16];
 	uint16_t        port;
 	uint16_t	pad;
 };
 
+/*
+ * 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;
 	}
 
@@ -220,10 +232,10 @@ static inline int obj_to_sheep(struct sheepdog_node_list_entry *entries,
 static inline void print_node_list_entry(struct sheepdog_node_list_entry *e,
 					 char *str, size_t size)
 {
-	uint32_t *p = (uint32_t *)e->id;
+	uint16_t *p = (uint16_t *)&e->id;
 
-	snprintf(str, size, "%08x:%08x:%08x:%08x:%08x - %d.%d.%d.%d:%d",
-		p[0] ,p[1], p[2], p[3] ,p[4],
+	snprintf(str, size, "%04x:%04x:%04x:%04x - %d.%d.%d.%d:%d",
+		p[0] ,p[1], p[2], p[3],
 		e->addr[12], e->addr[13],
 		e->addr[14], e->addr[15], e->port);
 }
diff --git a/shepherd/Makefile b/shepherd/Makefile
index 61cafb3..11e4a47 100644
--- a/shepherd/Makefile
+++ b/shepherd/Makefile
@@ -2,7 +2,7 @@ sbindir ?= $(PREFIX)/sbin
 
 CFLAGS += -g -O2 -Wall -Wstrict-prototypes -I../include
 CFLAGS += -D_GNU_SOURCE
-LIBS += -lncurses -lcrypto
+LIBS += -lncurses
 
 PROGRAMS = shepherd
 SHEPHERD_OBJS = shepherd.o treeview.o ../lib/event.o ../lib/net.o ../lib/logger.o
diff --git a/shepherd/shepherd.c b/shepherd/shepherd.c
index 4ac7e4a..27ed7a1 100644
--- a/shepherd/shepherd.c
+++ b/shepherd/shepherd.c
@@ -25,7 +25,6 @@
 #include <time.h>
 #include <sys/time.h>
 #include <term.h>
-#include <openssl/sha.h>
 #include <curses.h>
 
 #include "meta.h"
@@ -852,8 +851,8 @@ rerun:
 		}
 		break;
 	case INFO_DOG:
-		printf("  Idx\tNode id (SHA1)                               - Host:Port\n");
-		printf("-----------------------------------------------------------------------\n");
+		printf("  Idx\tNode id (FNV-1a)    - Host:Port\n");
+		printf("--------------------------------------------------\n");
 		for (i = 0; i < nr_nodes; i++) {
 			char data[128];
 
-- 
1.5.6.5




More information about the sheepdog mailing list