diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | Makefile | 68 | ||||
| -rw-r--r-- | src/.clang_complete | 8 | ||||
| -rw-r--r-- | src/main.c | 151 | ||||
| -rw-r--r-- | src/routing.c | 129 | ||||
| -rw-r--r-- | src/routing.h | 39 | ||||
| -rw-r--r-- | test/routing.c | 6 |
7 files changed, 227 insertions, 177 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..f8a1367 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +compile_commands.json +obj/ +/dht @@ -1,6 +1,7 @@ CC ?= gcc SRCDIR ?= src +TSTDIR ?= test GENDIR ?= gen OBJDIR ?= obj @@ -12,32 +13,32 @@ CFG = -std=gnu11 -fms-extensions -flto CFLAGS ?= -O3 -D_FORTIFY_SOURCE=2 CFLAGS += -Wall -SOURCES = $(shell find $(SRCDIR) -name "*.c") -DEPS_C = $(OBJS_C:%.o=%.d) -OBJS_C = $(SOURCES:%.c=$(OBJDIR)/%.o) +APP_MAIN_SOURCES = src/main.c +APP_SOURCES = $(filter-out $(APP_MAIN_SOURCES),$(shell find $(SRCDIR) -name "*.c")) +APP_OBJS = $(APP_SOURCES:%.c=$(OBJDIR)/%.o) +APP_MAIN_OBJS = $(APP_MAIN_SOURCES:%.c=$(OBJDIR)/%.o) +APP_DEPS = $(APP_OBJS:%.o=%.d) +APP_MAIN_DEPS = $(APP_MAIN_OBJS:%.o=%.d) -FFGEN_SOURCES = $(wildcard ffgen/*.c) -FFGEN_DEPS_C = $(FFGEN_OBJS_C:%.o=%.d) -FFGEN_OBJS_C = $(FFGEN_SOURCES:%.c=$(OBJDIR)/%.o) +TEST_LIB_SOURCES = thirdparty/Unity/src/unity.c +TEST_LIB_OBJS = $(TEST_LIB_SOURCES:%.c=$(OBJDIR)/%.o) +TEST_LIB_DEPS = $(TEST_LIB_SOURCES:%.c=%.d) +TEST_LIB_INCS = -Ithirdparty/Unity/src -.DEFAULT_GOAL := opz +TEST_SOURCES = $(shell find $(TSTDIR) -name "*.c") +TEST_EXES = $(TEST_SOURCES:%.c=$(OBJDIR)/%) +TEST_DEPS = $(TEST_SOURCES:%.c=%.d) print-% : ; @echo $* = $($*) -src/.clang_complete: Makefile - @(for i in $(filter-out -O% -DNDEBUG, $(CFG) $(CPPFLAGS) $(CFLAGS) $(INCS)); do echo "$$i"; done) > $@ +-include $(APP_DEPS) $(TEST_LIB_DEPS) $(TEST_DEPS) -opz: $(OBJS_C) - $(CC) $(CFG) $(CPPFLAGS) $(LDFLAGS) $(CFLAGS) -o $@ $(OBJS_C) $(LIBS) +# We don't really need to run the tests for bear to record them +compile_commands.json: clean Makefile $(APP_SOURCES) $(TEST_LIB_SOURCES) $(TEST_SOURCES) + bear -- make $(TEST_EXES) dht -$(OBJDIR)/ffgen/ffgen: $(FFGEN_OBJS_C) - $(CC) $(CFG) $(CPPFLAGS) $(LDFLAGS) $(CFLAGS) -o $@ $^ - -$(GENDIR)/ffgen/opz.h: $(SRCDIR)/opz.ff $(OBJDIR)/ffgen/ffgen - @mkdir -p $(dir $@) - $(OBJDIR)/ffgen/ffgen <$< >$@ - --include $(DEPS_C) $(FFGEN_DEPS_C) +dht: $(APP_MAIN_OBJS) $(APP_OBJS) + $(CC) $(CFG) $(CPPFLAGS) $(LDFLAGS) $(CFLAGS) -o $@ $(APP_MAIN_OBJS) $(APP_OBJS) $(LIBS) $(OBJDIR)/%.o: %.c @mkdir -p $(dir $@) @@ -45,8 +46,35 @@ $(OBJDIR)/%.o: %.c clean: @rm -rf $(OBJDIR) - @rm -f opz .clang_complete + @rm -f dht .compile_commands.json .PHONY: version version: @echo "$(COMPTON_VERSION)" + +# Unit tests! + +# Run all tests +.PHONY: test +test: $(TEST_EXES) + $(foreach test,$(TEST_EXES),./$(test);) + +$(OBJDIR)/test/%: $(APP_OBJS) $(TEST_LIB_OBJS) $(OBJDIR)/test/%.o $(OBJDIR)/test/%.runner.o + $(CC) $(CFG) $(CPPFLAGS) $(LDFLAGS) $(CFLAGS) -o $@ $^ $(LIBS) + +$(OBJDIR)/test/%.runner.c: test/%.c + @mkdir -p $(dir $@) + ruby thirdparty/Unity/auto/generate_test_runner.rb $< $@ + +# Test code needs test includes +$(OBJDIR)/test/%.o: test/%.c + @mkdir -p $(dir $@) + $(CC) $(CFG) $(CPPFLAGS) $(CFLAGS) $(TEST_LIB_INCS) $(INCS) -MMD -o $@ -c $< + +# Generated test sources are located under obj +$(OBJDIR)/test/%.o: $(OBJDIR)/test/%.c + @mkdir -p $(dir $@) + $(CC) $(CFG) $(CPPFLAGS) $(CFLAGS) $(TEST_LIB_INCS) $(INCS) -MMD -o $@ -c $< + +.DEFAULT_GOAL := all +all: test dht diff --git a/src/.clang_complete b/src/.clang_complete deleted file mode 100644 index 0b56058..0000000 --- a/src/.clang_complete +++ /dev/null @@ -1,8 +0,0 @@ --std=gnu11 --fms-extensions --flto --D_FORTIFY_SOURCE=2 --Wall --Isrc/ --Igen/ --I. @@ -1,4 +1,5 @@ -#include <stdio.h> +#include "routing.h" + #include <errno.h> #include <sys/stat.h> #include <fcntl.h> @@ -10,17 +11,6 @@ #include <stdbool.h> #include <string.h> -#define dbg(format, ...) \ - dbgl(format "\n", ## __VA_ARGS__) - -#define dbgl(format, ...) \ - printf(format, ## __VA_ARGS__); \ - fflush(stderr) - -#define err(format, ...) \ - printf(format "\n", ## __VA_ARGS__); \ - fflush(stderr) - // The DHT routing table has a keyspace of 0 -- 2^160 split into buckets of 8. // When a bucket becomes full, we split it in half. As we further expand the // routing table we only continue to split the buckets on the side we fall on. @@ -45,142 +35,6 @@ // <----------Detail----------> // -struct addr { - uint32_t ip; - uint16_t port; -}; - -struct nodeid { - uint32_t inner[5]; -}; - -struct entry { - bool set; - struct nodeid id; - time_t last; - struct addr addr; -}; - -#define IDBITS 160 -#define BUCKETSIZE 8 -// The 3 here is log2(BUCKETSIZE), since the final bucket will contain all those combinations -#define BUCKETBITS 3 -#define ROUTINGSIZE (IDBITS * BUCKETSIZE) - -struct nodeid myID; -struct entry table[ROUTINGSIZE]; - -void routing_init(struct nodeid* myid) { - myID = *myid; -} - -// Calculate the common bit prefix between two node ids. -uint8_t prefix(struct nodeid* a, struct nodeid* b) { - uint8_t c = 0; - for(uint8_t i = 0; i < 5; i++) { - uint32_t word = a->inner[i] ^ b->inner[i]; - - // This word is different, find the location of the difference - if(word != 0) - return c + __builtin_clz(word); - - // This word is completely the same - c += sizeof(word) * CHAR_BIT; - } - - return c; -} - -int8_t scan(uint16_t baseIndex, struct nodeid* id) { - assert(baseIndex < ROUTINGSIZE - BUCKETSIZE); - int8_t index = -1; - - for(size_t i = baseIndex; i < baseIndex + BUCKETSIZE; i++) { - if(!table[i].set) { - index = index == -1 ? i - baseIndex : index; - continue; - } - - if(memcmp(&table[i].id, id, sizeof(struct nodeid)) == 0) { - return -1; - } - } - - return index; -} - -// Offer the routing table a new node -bool routing_offer(struct nodeid* id, struct entry **dest) { - uint16_t bucketIndex = prefix(&myID, id); - // The nodeid is the same as our own - assert(bucketIndex != IDBITS); - - // If they are sufficiently similar they end up in the final bucket. Clamp the index to ensure. - bucketIndex = bucketIndex > (IDBITS - BUCKETBITS) ? (IDBITS - BUCKETBITS) : bucketIndex; - assert(bucketIndex <= IDBITS - BUCKETBITS); - - uint16_t baseIndex = bucketIndex * BUCKETSIZE; - int8_t inBucketIndex = scan(baseIndex, id); - - if(inBucketIndex == -1) { - // The bucket either already contains the node, or it has no more space - dbg("discarding node"); - return false; - } - - struct entry* entry = &table[baseIndex + inBucketIndex]; - entry->set = true; - entry->id = *id; - - *dest = entry; - return true; -} - -struct item { - struct nodeid distance; - bool set; - uint16_t index; -}; -int compareItem(const void* a_v, const void* b_v) { - struct item* a = (struct item*)a_v; - struct item* b = (struct item*)b_v; - - // If either of the two are not set, the one that is set comes before the - // one that isn't. - if(!a->set || !b->set) return b->set - a->set; - - return memcmp(&a->distance, &b->distance, sizeof(struct nodeid)); -} - -size_t rounting_closest(struct nodeid* needle, size_t n, struct entry** res) { - assert(n <= ROUTINGSIZE); - static struct item items[ROUTINGSIZE] = {0}; - for(uint16_t i = 0; i < ROUTINGSIZE; i++) { - items[i].index = i; - } - - { - struct item* item; - struct entry* entry; - for(item = &items[0], entry = &table[0]; item < &items[ROUTINGSIZE] && entry < &table[ROUTINGSIZE]; item++, entry++){ - item->set = entry->set; - for(uint8_t j = 0; j < 5; j++) { - item->distance.inner[j] = entry->id.inner[j] ^ needle->inner[j]; - } - } - } - - qsort(items, ROUTINGSIZE, sizeof(struct item), compareItem); - - size_t read; - for(read = 0; read < n; read++) { - if(!items[read].set) - break; - res[read] = &table[items[read].index]; - } - - return read; -} void dbgl_id(struct nodeid* id) { for(uint8_t i = 0; i < 5; i++) { @@ -219,7 +73,6 @@ int main(int argc, char** argv) { for(size_t i = 0; i < nfound; i++) { dbgl_id(&found[i]->id); } - dbg("%d", prefix(&a, &b)); return 0; } diff --git a/src/routing.c b/src/routing.c new file mode 100644 index 0000000..89fa800 --- /dev/null +++ b/src/routing.c @@ -0,0 +1,129 @@ +#include "routing.h" + +#include <assert.h> +#include <limits.h> +#include <string.h> +#include <stdbool.h> +#include <stdlib.h> + +#define IDBITS 160 +#define BUCKETSIZE 8 +// The 3 here is log2(BUCKETSIZE), since the final bucket will contain all those combinations +#define BUCKETBITS 3 +#define ROUTINGSIZE (IDBITS * BUCKETSIZE) + +struct nodeid myID; +struct entry table[ROUTINGSIZE]; + +void routing_init(struct nodeid* myid) { + myID = *myid; +} + +// Calculate the common bit prefix between two node ids. +uint8_t prefix(struct nodeid* a, struct nodeid* b) { + uint8_t c = 0; + for(uint8_t i = 0; i < 5; i++) { + uint32_t word = a->inner[i] ^ b->inner[i]; + + // This word is different, find the location of the difference + if(word != 0) + return c + __builtin_clz(word); + + // This word is completely the same + c += sizeof(word) * CHAR_BIT; + } + + return c; +} + +int8_t scan(uint16_t baseIndex, struct nodeid* id) { + assert(baseIndex < ROUTINGSIZE - BUCKETSIZE); + int8_t index = -1; + + for(size_t i = baseIndex; i < baseIndex + BUCKETSIZE; i++) { + if(!table[i].set) { + index = index == -1 ? i - baseIndex : index; + continue; + } + + if(memcmp(&table[i].id, id, sizeof(struct nodeid)) == 0) { + return -1; + } + } + + return index; +} + +// Offer the routing table a new node +bool routing_offer(struct nodeid* id, struct entry **dest) { + uint16_t bucketIndex = prefix(&myID, id); + // The nodeid is the same as our own + assert(bucketIndex != IDBITS); + + // If they are sufficiently similar they end up in the final bucket. Clamp the index to ensure. + bucketIndex = bucketIndex > (IDBITS - BUCKETBITS) ? (IDBITS - BUCKETBITS) : bucketIndex; + assert(bucketIndex <= IDBITS - BUCKETBITS); + + uint16_t baseIndex = bucketIndex * BUCKETSIZE; + int8_t inBucketIndex = scan(baseIndex, id); + + if(inBucketIndex == -1) { + // The bucket either already contains the node, or it has no more space + dbg("discarding node"); + return false; + } + + struct entry* entry = &table[baseIndex + inBucketIndex]; + entry->set = true; + entry->id = *id; + + *dest = entry; + return true; +} + +struct item { + struct nodeid distance; + bool set; + uint16_t index; +}; +int compareItem(const void* a_v, const void* b_v) { + struct item* a = (struct item*)a_v; + struct item* b = (struct item*)b_v; + + // If either of the two are not set, the one that is set comes before the + // one that isn't. + if(!a->set || !b->set) return b->set - a->set; + + return memcmp(&a->distance, &b->distance, sizeof(struct nodeid)); +} + +size_t rounting_closest(struct nodeid* needle, size_t n, struct entry** res) { + assert(n <= ROUTINGSIZE); + static struct item items[ROUTINGSIZE] = {0}; + for(uint16_t i = 0; i < ROUTINGSIZE; i++) { + items[i].index = i; + } + + { + struct item* item; + struct entry* entry; + for(item = &items[0], entry = &table[0]; item < &items[ROUTINGSIZE] && entry < &table[ROUTINGSIZE]; item++, entry++){ + item->set = entry->set; + for(uint8_t j = 0; j < 5; j++) { + item->distance.inner[j] = entry->id.inner[j] ^ needle->inner[j]; + } + } + } + + qsort(items, ROUTINGSIZE, sizeof(struct item), compareItem); + + size_t read; + for(read = 0; read < n; read++) { + if(!items[read].set) + break; + res[read] = &table[items[read].index]; + } + + return read; +} + diff --git a/src/routing.h b/src/routing.h new file mode 100644 index 0000000..dc40aa9 --- /dev/null +++ b/src/routing.h @@ -0,0 +1,39 @@ +#pragma once + +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <time.h> +#include <stdio.h> + +#define dbg(format, ...) \ + dbgl(format "\n", ## __VA_ARGS__) + +#define dbgl(format, ...) \ + printf(format, ## __VA_ARGS__); \ + fflush(stderr) + +#define err(format, ...) \ + printf(format "\n", ## __VA_ARGS__); \ + fflush(stderr) + + +struct addr { + uint32_t ip; + uint16_t port; +}; + +struct nodeid { + uint32_t inner[5]; +}; + +struct entry { + bool set; + struct nodeid id; + time_t last; + struct addr addr; +}; + +void routing_init(struct nodeid* myid); +bool routing_offer(struct nodeid* id, struct entry **dest); +size_t rounting_closest(struct nodeid* needle, size_t n, struct entry** res); diff --git a/test/routing.c b/test/routing.c new file mode 100644 index 0000000..adb424d --- /dev/null +++ b/test/routing.c @@ -0,0 +1,6 @@ +#include "unity.h" +#include "routing.h" + +void test_rt_add() { + TEST_PASS(); +} |