From 8ded9142c1514ab04905e623247a84313a773fa7 Mon Sep 17 00:00:00 2001 From: Jesper Jensen Date: Wed, 16 Jun 2021 21:45:22 +0200 Subject: INITIAL COMMIT --- .gitmodules | 3 + Makefile | 52 ++++++++++++ src/.clang_complete | 8 ++ src/main.c | 225 ++++++++++++++++++++++++++++++++++++++++++++++++++++ thirdparty/Unity | 1 + 5 files changed, 289 insertions(+) create mode 100644 .gitmodules create mode 100644 Makefile create mode 100644 src/.clang_complete create mode 100644 src/main.c create mode 160000 thirdparty/Unity diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..24dbdbe --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "thirdparty/Unity"] + path = thirdparty/Unity + url = https://github.com/ThrowTheSwitch/Unity.git diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..5e90569 --- /dev/null +++ b/Makefile @@ -0,0 +1,52 @@ +CC ?= gcc + +SRCDIR ?= src +GENDIR ?= gen +OBJDIR ?= obj + +LIBS = -lm +INCS = -Isrc/ -Igen/ -I. + +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) + +FFGEN_SOURCES = $(wildcard ffgen/*.c) +FFGEN_DEPS_C = $(FFGEN_OBJS_C:%.o=%.d) +FFGEN_OBJS_C = $(FFGEN_SOURCES:%.c=$(OBJDIR)/%.o) + +.DEFAULT_GOAL := opz + +print-% : ; @echo $* = $($*) + +src/.clang_complete: Makefile + @(for i in $(filter-out -O% -DNDEBUG, $(CFG) $(CPPFLAGS) $(CFLAGS) $(INCS)); do echo "$$i"; done) > $@ + +opz: $(OBJS_C) + $(CC) $(CFG) $(CPPFLAGS) $(LDFLAGS) $(CFLAGS) -o $@ $(OBJS_C) $(LIBS) + +$(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) + +$(OBJDIR)/%.o: %.c + @mkdir -p $(dir $@) + $(CC) $(CFG) $(CPPFLAGS) $(CFLAGS) $(INCS) -MMD -o $@ -c $< + +clean: + @rm -rf $(OBJDIR) + @rm -f opz .clang_complete + +.PHONY: version +version: + @echo "$(COMPTON_VERSION)" diff --git a/src/.clang_complete b/src/.clang_complete new file mode 100644 index 0000000..0b56058 --- /dev/null +++ b/src/.clang_complete @@ -0,0 +1,8 @@ +-std=gnu11 +-fms-extensions +-flto +-D_FORTIFY_SOURCE=2 +-Wall +-Isrc/ +-Igen/ +-I. diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..1113baa --- /dev/null +++ b/src/main.c @@ -0,0 +1,225 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#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. +// +// Initially, this may sound like a binary tree (because we split it in two), +// but looking at it as a flat array leads to some interesting intuitions. +// Since we only expand one half of the "tree", the total size is bounded by +// the depth of the tree log2(2^160) == 160. +// +// As a flat array we notice the intrinsic properties of the routing table. +// With a bucket size of 8, the routing table contains 160 * 8 == 1280 nodes. +// As the node ids get less similar to our own our grouping of them becomes +// less detailed. While the bucket we are in contains node very close to us, +// the nodes furthest away from us are grouped in buckets with nodes they +// barely resemble. +// +// +----------------------------+ +// | n1 | n2 | n3 | ... | n1280 | +// +----------------------------+ +// More Less +// <--------Similarity--------> +// <----------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++) { + fprintf(stderr, "0x%08x ", id->inner[i]); + } + fprintf(stderr, "\n"); + fflush(stderr); +} + +int main(int argc, char** argv) { + + struct nodeid a = {0}; + a.inner[1] = 0xFFFFFFFF; + routing_init(&a); + + + struct nodeid b = {0}; + b.inner[1] = 0xFFFFFFFF; + b.inner[4] = 0x00000001; + struct entry *entry; + if(routing_offer(&b, &entry)) { + entry->addr.ip = 0; + entry->addr.port = 0; + } + + b.inner[1] = 0xFFFFFFFF; + b.inner[4] = 0x00000002; + if(routing_offer(&b, &entry)) { + entry->addr.ip = 0; + entry->addr.port = 0; + } + + struct entry *found[10]; + size_t nfound = rounting_closest(&b, 10, found); + + for(size_t i = 0; i < nfound; i++) { + dbgl_id(&found[i]->id); + } + dbg("%d", prefix(&a, &b)); + + return 0; +} diff --git a/thirdparty/Unity b/thirdparty/Unity new file mode 160000 index 0000000..0b899ae --- /dev/null +++ b/thirdparty/Unity @@ -0,0 +1 @@ +Subproject commit 0b899aec14d3a9abb2bf260ac355f0f28630a6a3 -- cgit v1.2.3