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 |