diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 20 | ||||
| -rw-r--r-- | src/routing.c | 14 | ||||
| -rw-r--r-- | src/routing.h | 3 | ||||
| -rw-r--r-- | test/routing.c | 91 |
5 files changed, 113 insertions, 16 deletions
@@ -1,3 +1,4 @@ compile_commands.json obj/ /dht +*.gcov @@ -8,10 +8,9 @@ OBJDIR ?= obj LIBS = -lm INCS = -Isrc/ -Igen/ -I. -CFG = -std=gnu11 -fms-extensions -flto - -CFLAGS ?= -O3 -D_FORTIFY_SOURCE=2 -CFLAGS += -Wall +CFLAGS ?= -O3 -D_FORTIFY_SOURCE=2 -Wall +# add all the required Cflags +CFLAGS += -std=gnu11 -fms-extensions -flto APP_MAIN_SOURCES = src/main.c APP_SOURCES = $(filter-out $(APP_MAIN_SOURCES),$(shell find $(SRCDIR) -name "*.c")) @@ -35,18 +34,19 @@ print-% : ; @echo $* = $($*) # 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) + @rm -f "$@" bear -- make $(TEST_EXES) dht dht: $(APP_MAIN_OBJS) $(APP_OBJS) - $(CC) $(CFG) $(CPPFLAGS) $(LDFLAGS) $(CFLAGS) -o $@ $(APP_MAIN_OBJS) $(APP_OBJS) $(LIBS) + $(CC) $(LDFLAGS) $(CFLAGS) -o $@ $(APP_MAIN_OBJS) $(APP_OBJS) $(LIBS) $(OBJDIR)/%.o: %.c @mkdir -p $(dir $@) - $(CC) $(CFG) $(CPPFLAGS) $(CFLAGS) $(INCS) -MMD -o $@ -c $< + $(CC) $(CFLAGS) $(INCS) -MMD -o $@ -c $< clean: @rm -rf $(OBJDIR) - @rm -f dht .compile_commands.json + @rm -f dht .PHONY: version version: @@ -60,7 +60,7 @@ 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) + $(CC) $(LDFLAGS) $(CFLAGS) -o $@ $^ $(LIBS) $(OBJDIR)/test/%.runner.c: test/%.c @mkdir -p $(dir $@) @@ -69,12 +69,12 @@ $(OBJDIR)/test/%.runner.c: test/%.c # Test code needs test includes $(OBJDIR)/test/%.o: test/%.c @mkdir -p $(dir $@) - $(CC) $(CFG) $(CPPFLAGS) $(CFLAGS) $(TEST_LIB_INCS) $(INCS) -MMD -o $@ -c $< + $(CC) $(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 $< + $(CC) $(CFLAGS) $(TEST_LIB_INCS) $(INCS) -MMD -o $@ -c $< .DEFAULT_GOAL := all all: test dht diff --git a/src/routing.c b/src/routing.c index 89fa800..d4eaa3f 100644 --- a/src/routing.c +++ b/src/routing.c @@ -19,6 +19,10 @@ void routing_init(struct nodeid* myid) { myID = *myid; } +void routing_flush() { + memset(table, 0, sizeof(table)); +} + // Calculate the common bit prefix between two node ids. uint8_t prefix(struct nodeid* a, struct nodeid* b) { uint8_t c = 0; @@ -58,7 +62,9 @@ int8_t scan(uint16_t baseIndex, struct nodeid* id) { 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(bucketIndex == IDBITS) { + return false; + } // If they are sufficiently similar they end up in the final bucket. Clamp the index to ensure. bucketIndex = bucketIndex > (IDBITS - BUCKETBITS) ? (IDBITS - BUCKETBITS) : bucketIndex; @@ -69,7 +75,6 @@ bool routing_offer(struct nodeid* id, struct entry **dest) { if(inBucketIndex == -1) { // The bucket either already contains the node, or it has no more space - dbg("discarding node"); return false; } @@ -97,7 +102,7 @@ int compareItem(const void* a_v, const void* b_v) { return memcmp(&a->distance, &b->distance, sizeof(struct nodeid)); } -size_t rounting_closest(struct nodeid* needle, size_t n, struct entry** res) { +size_t routing_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++) { @@ -115,6 +120,9 @@ size_t rounting_closest(struct nodeid* needle, size_t n, struct entry** res) { } } + // @PERFORMANCE: There's an algorithm known as quickselect which can select + // the top k elements from a list while only doing a partial sort. + // I imagine that would be more efficient than this full sort. qsort(items, ROUTINGSIZE, sizeof(struct item), compareItem); size_t read; diff --git a/src/routing.h b/src/routing.h index dc40aa9..b0e9922 100644 --- a/src/routing.h +++ b/src/routing.h @@ -35,5 +35,6 @@ struct entry { }; void routing_init(struct nodeid* myid); +void routing_flush(); bool routing_offer(struct nodeid* id, struct entry **dest); -size_t rounting_closest(struct nodeid* needle, size_t n, struct entry** res); +size_t routing_closest(struct nodeid* needle, size_t n, struct entry** res); diff --git a/test/routing.c b/test/routing.c index adb424d..c4b7730 100644 --- a/test/routing.c +++ b/test/routing.c @@ -1,6 +1,93 @@ #include "unity.h" #include "routing.h" -void test_rt_add() { - TEST_PASS(); +#define IP(a, b, c, d) (a << 24 | b << 16 | c << 8 | d) + +struct nodeid self; + +void setUp() { + self = (struct nodeid){{ 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000 }}; + routing_init(&self); +} + +void test_deny_self_add() { + routing_flush(); + struct entry* entry; + if(!routing_offer(&self, &entry)) + TEST_PASS(); + + TEST_FAIL(); +} + +void test_can_find_added() { + routing_flush(); + + // The address we are going to store + struct addr addr = (struct addr){.ip = IP(128,0,0,1), .port = 0}; + + // Make a nodeid that is one bit different + struct nodeid new = self; + + new.inner[4] += 1; + struct entry* entry; + TEST_ASSERT_TRUE_MESSAGE(routing_offer(&new, &entry), "Did not accept new entry"); + new.inner[4] += 1; + TEST_ASSERT_TRUE_MESSAGE(routing_offer(&new, &entry), "Did not accept new entry"); + + // Set the entries + entry->addr = addr; + entry->last = time(NULL); + + // Ask for 3 nodes + struct entry *out[3] = {0}; + size_t n = routing_closest(&new, 3, out); + // Since we only put 2 in, we should get 2 out + TEST_ASSERT_EQUAL_INT(2, n); + + TEST_ASSERT_EQUAL_MEMORY(&addr, &out[0]->addr, sizeof(struct addr)); + TEST_ASSERT_EQUAL_MEMORY(&new, &out[0]->id, sizeof(struct nodeid)); +} + +void test_discard_offer_when_bucket_full() { + routing_flush(); + + // The address we are going to store + struct addr addr = (struct addr){.ip = IP(128,0,0,1), .port = 0}; + + struct nodeid new = self; + // Flip the top bit of the id to go into the low resolution bucket + new.inner[0] ^= 0x80000000; + + // Fill up the bucket with entries + for(uint8_t i = 0; i < 8; i++) { + struct entry* entry; + TEST_ASSERT_TRUE_MESSAGE(routing_offer(&new, &entry), "Did not accept new entry"); + + // Set the entries + entry->addr = addr; + entry->last = time(NULL); + + new.inner[4] += 1; + } + + struct entry* entry; + TEST_ASSERT_FALSE_MESSAGE(routing_offer(&new, &entry), "Accepted entry when bucket was full"); +} + +void test_discard_offer_when_nodeid_added_twice() { + routing_flush(); + + // The address we are going to store + struct addr addr = (struct addr){.ip = IP(128,0,0,1), .port = 0}; + + struct nodeid new = self; + new.inner[4] ^= 0x00000001; + + struct entry* entry; + TEST_ASSERT_TRUE(routing_offer(&new, &entry)); + entry->addr = addr; + entry->last = time(NULL); + + bool accept = routing_offer(&new, &entry); + TEST_ASSERT_FALSE_MESSAGE(accept, "Accepted entry when bucket was full"); } |