From 188666dc51233051985715b01631e069a7939442 Mon Sep 17 00:00:00 2001 From: Jesper Jensen Date: Wed, 16 Apr 2025 23:34:03 +0200 Subject: Add a first approximation of a lookup algorithm This isn't really "correct" but it's probably going to work. It's a rough implementation of the Kademlia lookup algorithm, with the modification that we don't keep track of anything behind the frontier. We are therefore counting on peers being ok with us potentially sending them the "same" request multiple times. If they respond in a reasonable time, the double request rate _should_ be minimal, but that of course carries the risk that an already overloaded peer would get even more queries. I don't know. It's a first try at something. I need to see it work before I write it off completely. --- src/main.c | 40 ++++++++++++++-------------------------- 1 file changed, 14 insertions(+), 26 deletions(-) (limited to 'src/main.c') diff --git a/src/main.c b/src/main.c index a18cb78..267f324 100644 --- a/src/main.c +++ b/src/main.c @@ -129,18 +129,6 @@ void flush_messages(int sfd, struct message* cursor, const struct message* const } } -struct lookup { - struct nodeid target; - - struct nodeid closest[8]; - struct addr closest_addr[8]; - bool closest_valid[8]; // @SLOP: This could be a single word - - uint64_t outstanding; - - time_t wake; -}; - #define OUTBOX_SIZE 32 int main(int argc, char** argv) { srand(time(NULL)); @@ -183,20 +171,20 @@ int main(int argc, char** argv) { proto_begin(&dht, time(NULL), &message_cursor, outbuff+32); flush_messages(dht.sfd, outbuff, message_cursor); - /* struct lookup lookup; */ - /* // Init the lookup */ - /* { */ - /* lookup.wake = 0; */ - /* lookup.target = (struct nodeid){.inner={0x19b8a941, 0x38fa0191, 0x1403fac2, 0x581000ab, 0x19583cda}}; */ - - /* struct entry* entry[8]; */ - /* int found = routing_closest(&lookup.target, 8, entry); */ - /* for(size_t i = 0; i < found; i++) { */ - /* lookup.closest[i] = entry[i]->id; */ - /* lookup.closest_addr[i] = entry[i]->addr; */ - /* lookup.closest_valid[i] = true; */ - /* } */ - /* } */ + // Init the lookup + struct lookup *lookup = &dht.lookup; + { + lookup->timeout = 0; + lookup->target = (struct nodeid){.inner={0x19b8a941, 0x38fa0191, 0x1403fac2, 0x581000ab, 0x19583cda}}; + + struct entry* entry[8]; + int found = routing_closest(&lookup->target, sizeof(entry)/sizeof(entry[0]), entry); + assert(found == 8); + for(size_t i = 0; i < found; i++) { + lookup->closest[i] = entry[i]->id; + lookup->closest_addr[i] = entry[i]->addr; + } + } #define RECV_BUFF_SIZE 4096 char buff_storage[RECV_BUFF_SIZE+1]; -- cgit v1.2.3