[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