From e00efb4381c5123699e4ef9807b67eba54ea06a0 Mon Sep 17 00:00:00 2001 From: Jesper Jensen Date: Sat, 28 Aug 2021 22:27:24 +0200 Subject: Initial fanout implemented --- src/benc.c | 232 ++++++++++++++++++++++++++++++++++++ src/benc.h | 31 +++++ src/log.h | 20 ++++ src/main.c | 360 +++++++++++++++++++++++++++++++++++++++++++++++++++++--- src/routing.c | 22 ++++ src/routing.h | 13 +- test/benc.c | 366 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ test/routing.c | 51 ++++++++ 8 files changed, 1064 insertions(+), 31 deletions(-) create mode 100644 src/benc.c create mode 100644 src/benc.h create mode 100644 src/log.h create mode 100644 test/benc.c diff --git a/src/benc.c b/src/benc.c new file mode 100644 index 0000000..4f61ff7 --- /dev/null +++ b/src/benc.c @@ -0,0 +1,232 @@ +#include "benc.h" +#include "log.h" + +#include +#include +#include +#include +#include + + +#define MAX(a, b) \ + ({ \ + __typeof__ (a) _a = (a); \ + __typeof__ (b) _b = (b); \ + _a > _b ? _a : _b; \ + }) + +#define MIN(a, b) \ + ({ \ + __typeof__ (a) _a = (a); \ + __typeof__ (b) _b = (b); \ + _a < _b ? _a : _b; \ + }) + +bool readint(const char** loc, int64_t* val) { + char* end = NULL; + errno = 0; + *val = strtol(*loc, &end, 10); + *loc = end; + + return errno == 0; +} + +bool digit(const char c) { + return c >= '0' && c <= '9'; +} + +char* nodenames[] = { + "INT", + "STR", + "LIST", + "DICT", + "END", +}; + +void indent(int depth) { + for(int i = 0; i < depth; i++) { + printf(" "); + } +} + +void benc_print(const struct benc_node* stream, size_t stream_len, int* depth) { + const struct benc_node* cursor = stream; + for(; cursor < stream + stream_len; cursor++) { + switch(cursor->type) { + case BNT_INT: + indent(*depth); + printf("INT %.*s\n", cursor->size, cursor->loc); + break; + case BNT_STRING: + indent(*depth); + bool allprint = true; + for (const char* c = cursor->loc; c < cursor->loc + cursor->size; c++) { + if(!isalnum(*c)) { + allprint = false; + break; + } + } + printf("STR "); + if(allprint) { + printf("%.*s", cursor->size, cursor->loc); + } else { + for (const unsigned char* c = (const unsigned char*)cursor->loc; c < (unsigned char*)(cursor->loc + cursor->size); c++) { + printf("\\x%02X", *c); + } + } + printf("\n"); + break; + case BNT_LIST: + indent(*depth); + printf("LIST\n"); + *depth = cursor->depth + 1; + break; + case BNT_DICT: + indent(*depth); + printf("DICT\n"); + *depth = cursor->depth + 1; + break; + case BNT_END: + *depth = cursor->depth; + indent(*depth); + printf("END\n"); + break; + } + } +} + +int64_t benc_decode(const char** cursor, const char* end, int* depth, struct benc_node* stream, size_t stream_len) { + size_t cursor_out = 0; + + while(cursor_out < stream_len) { + struct benc_node* node = &stream[cursor_out]; + + if(**cursor == 'i') { + node->type = BNT_INT; + (*cursor)++; + if(*cursor >= end) { + return -cursor_out; + } + node->loc = *cursor; + while(**cursor != 'e') { + if(**cursor != '-' && !digit(**cursor)) { + return -cursor_out; + } + (*cursor)++; + if(*cursor >= end) { + return -cursor_out; + } + } + node->size = *cursor - node->loc; + (*cursor)++; + } else if(**cursor == 'l') { + node->type = BNT_LIST; + node->depth = *depth; + (*depth)++; + node->loc = *cursor; + (*cursor)++; + if(*cursor >= end) { + return -cursor_out; + } + } else if(**cursor == 'd') { + node->type = BNT_DICT; + node->depth = *depth; + (*depth)++; + node->loc = *cursor; + (*cursor)++; + if(*cursor >= end) { + return -cursor_out; + } + } else if(**cursor == 'e') { + node->type = BNT_END; + (*depth)--; + node->depth = *depth; + node->loc = *cursor; + (*cursor)++; + } else if(digit(**cursor)) { + node->type = BNT_STRING; + int64_t val; + bool rc = readint(cursor, &val); + node->size = val; + if(*cursor >= end) { + return -cursor_out; + } + assert(rc); + if(**cursor != ':') { + return -cursor_out; + } + (*cursor)++; + if(*cursor >= end) { + return -cursor_out; + } + node->loc = *cursor; + (*cursor) += node->size; + if(*cursor > end) { + return -cursor_out; + } + } else { + return -cursor_out; + dbg("Failing on char \"%c\"", **cursor); + assert(false); + } + cursor_out++; + if(*depth == 0) break; + } + return cursor_out; +} + +void skip_sibling(const struct benc_node** cursor, const struct benc_node* end) { + assert((*cursor)->type == BNT_LIST || (*cursor)->type == BNT_DICT); + + if((*cursor)->type == BNT_LIST || (*cursor)->type == BNT_DICT) { + uint32_t tdepth = (*cursor)->depth; + (*cursor)++; + while(true) { + if(*cursor == end) { + fatal("Invalid dict"); + } + + if((*cursor)->type == BNT_END && (*cursor)->depth == tdepth) { + break; + } + + (*cursor)++; + } + (*cursor)++; + } else { + (*cursor)++; + } +} + +// All the arrays should be equal length +ssize_t skip_to_key(const struct benc_node** cursor, const struct benc_node* end, const enum benc_nodetype* keyTypes, const char** keyValues, const size_t* keyLengths, const size_t keys) { + // @ROBUSTNESS: Check if keytypes are anything but strings and ints because that is not supported + + while(true) { + if(*cursor > end-1) { + fatal("Invalid dict"); + } + + // Skip lists + if((*cursor)->type == BNT_LIST || (*cursor)->type == BNT_DICT) { + skip_sibling(cursor, end); + } else { + for(size_t i = 0; i < keys; i++) { + if((*cursor)->type == keyTypes[i] && memcmp((*cursor)->loc, keyValues[i], MIN((*cursor)->size, keyLengths[i])) == 0) { + return i; + } + } + } + + (*cursor) += 2; + + if((*cursor-1)->type == BNT_LIST || (*cursor-1)->type == BNT_DICT) { + (*cursor)--; + skip_sibling(cursor, end); + } + + if((*cursor)->type == BNT_END) { + return -1; + } + } +} diff --git a/src/benc.h b/src/benc.h new file mode 100644 index 0000000..a5734ea --- /dev/null +++ b/src/benc.h @@ -0,0 +1,31 @@ +#pragma once + +#include +#include +#include +#include + +enum benc_nodetype { + BNT_INT, + BNT_STRING, + BNT_LIST, + BNT_DICT, + BNT_END, +}; + +struct benc_node { + enum benc_nodetype type; + const char* loc; + union { + size_t size; + uint32_t depth; + }; +}; + +bool readint(const char** loc, int64_t* val); + +void benc_print(const struct benc_node* stream, size_t stream_len, int* depth); +int64_t benc_decode(const char** cursor, const char* end, int* depth, struct benc_node* stream, size_t stream_len); + +void skip_sibling(const struct benc_node** cursor, const struct benc_node* end); +ssize_t skip_to_key(const struct benc_node** cursor, const struct benc_node* end, const enum benc_nodetype* keyTypes, const char** keyValues, const size_t* keyLengths, const size_t keys); diff --git a/src/log.h b/src/log.h new file mode 100644 index 0000000..1717011 --- /dev/null +++ b/src/log.h @@ -0,0 +1,20 @@ +#pragma once + +#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) + +#define fatal(format, ...) \ + printf(format "\n", ## __VA_ARGS__); \ + fflush(stderr); \ + abort() + diff --git a/src/main.c b/src/main.c index 754721a..0c49797 100644 --- a/src/main.c +++ b/src/main.c @@ -1,8 +1,11 @@ #include "routing.h" +#include "benc.h" +#include "log.h" #include #include #include +#include #include #include #include @@ -10,6 +13,26 @@ #include #include #include +#include +#include +#include +#include +#include +#include + +#define MAX(a, b) \ + ({ \ + __typeof__ (a) _a = (a); \ + __typeof__ (b) _b = (b); \ + _a > _b ? _a : _b; \ + }) + +#define MIN(a, b) \ + ({ \ + __typeof__ (a) _a = (a); \ + __typeof__ (b) _b = (b); \ + _a < _b ? _a : _b; \ + }) void dbgl_id(struct nodeid* id) { @@ -20,35 +43,334 @@ void dbgl_id(struct nodeid* id) { fflush(stderr); } +struct discovery { + uint16_t port; + struct nodeid expected_id; +}; + +int sockaddr_cmp(struct sockaddr* x, struct sockaddr* y) { +#define CMP(a, b) \ + do { \ + typeof(a) cmp = a - b; \ + if(cmp != 0) return cmp; \ + } while(0) + if (x->sa_family == AF_INET) { + struct sockaddr_in *xin = (void*)x; + struct sockaddr_in *yin = (void*)y; + + CMP(ntohl(xin->sin_addr.s_addr), ntohl(yin->sin_addr.s_addr)); + CMP(ntohs(xin->sin_port), ntohs(yin->sin_port)); + } else if (x->sa_family == AF_INET6) { + struct sockaddr_in6 *xin6 = (void*)x, *yin6 = (void*)y; + int r = memcmp(xin6->sin6_addr.s6_addr, yin6->sin6_addr.s6_addr, sizeof(xin6->sin6_addr.s6_addr)); + if (r != 0) + return r; + CMP(ntohs(xin6->sin6_port), ntohs(yin6->sin6_port)); + CMP(xin6->sin6_flowinfo, yin6->sin6_flowinfo); + CMP(xin6->sin6_scope_id, yin6->sin6_scope_id); + } else { + err("Unsupported sa_family"); + abort(); + } + + return 0; +}; + +#define UNDEF_ADDR (struct in_addr){0xC0000200} +#define MAX_DISC 32 +struct in_addr addrs[MAX_DISC]; +struct discovery pending_discover[MAX_DISC]; + +typedef void (*cont)(struct nodeid* self, char* packet, size_t packet_len, int socket, struct sockaddr_in* remote, socklen_t remote_len); + +#define MAX_INFLIGHT 32 +bool reqalloc[MAX_INFLIGHT] = { false }; +struct { + struct sockaddr addr; + cont fun; +} requestdata[MAX_INFLIGHT]; + +bool alloc_req(uint16_t* reqId) { + for(size_t i = 0; i < MAX_INFLIGHT; i++) { + if(!reqalloc[i]) { + reqalloc[i] = true; + *reqId = i; + return true; + } + } + return false; +} + +bool find_req(uint32_t transId, uint16_t* reqId) { + *reqId = transId; + return reqalloc[transId]; +} + +void getclient_response(struct nodeid* self, char* packet, size_t packet_len, int socket, struct sockaddr_in* remote, socklen_t remote_len); + +int send_ping(struct nodeid* self, const int sfd, const struct sockaddr* dest_addr, socklen_t dest_len) { + uint16_t reqId; + if(!alloc_req(&reqId)) { + return ENOBUFS; + } + char buff[128]; + size_t i = 0; + + dbg("Allocating request %d", reqId); + requestdata[reqId].fun = &getclient_response; + requestdata[reqId].addr = *dest_addr; + + int rc = snprintf(buff+i, 128-i, "d1:ad2:id20:"); + i += rc; + memcpy(buff+i, self, sizeof(struct nodeid)); + i += sizeof(struct nodeid); + rc = snprintf(buff+i, 128-i, "6:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t%d:%d1:y1:qe", (reqId/10)+1, reqId); + i += rc; + + //now reply the client with the same data + rc = sendto(sfd, buff, i, 0, dest_addr, dest_len); + if (rc == -1) { + switch(errno) { + case EWOULDBLOCK: case EBADF: + return rc; + } + return EPERM; // Operation not permitted is used as the default "generic" error + } + + return 0; +} + +void getclient_response(struct nodeid* self, char* packet, size_t packet_len, int socket, struct sockaddr_in* remote, socklen_t remote_len) { + struct benc_node stream[256]; + const char* cursor = packet; + int depth = 0; + int len = benc_decode(&cursor, packet+packet_len, &depth, stream, 256); + + if(len <= 0) { + err("Reponse too short"); + exit(EXIT_FAILURE); + } + + struct nodeid id; + uint8_t nodes_len; + struct nodeid nodes[8]; + struct in_addr ips[8]; + uint16_t ports[8]; + + + // Read the payload + { + // Check that we have a dict + struct benc_node* cursor = stream; + if(cursor->type != BNT_DICT) { + err("Response is not a dict"); + exit(EXIT_FAILURE); + } + cursor++; + + skip_to_key((const struct benc_node**)&cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"r"}, (const size_t[]){1}, 1); + // Skip the key + cursor++; + + if(cursor->type != BNT_DICT) { + err("Wrong value type for response"); + exit(EXIT_FAILURE); + } + + // Skip the dict element + cursor++; + + while(cursor->type != BNT_END) { + switch(skip_to_key((const struct benc_node**)&cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING, BNT_STRING}, (const char*[]){"nodes", "id"}, (const size_t[]){5, 2}, 2)) { + case 0: + // Skip the key + cursor++; + + if(cursor->type != BNT_STRING) { + err("Wrong value type for response"); + exit(EXIT_FAILURE); + } + + if((cursor->size % 26) != 0) { + err("get_nodes call returned an incorrect nodes array"); + exit(EXIT_FAILURE); + } + + nodes_len = MIN(cursor->size/26, 8); + dbg("We have %d (%d/26) nodes", nodes_len, cursor->size); + for(int i = 0; i < nodes_len; i++) { + memcpy(nodes+i, cursor->loc+(26*i), 20); + memcpy(ips+i, cursor->loc+(26*i)+20, 4); + memcpy(ports+i, cursor->loc+(26*i)+24, 2); + } + + // Skip the value + cursor++; + break; + case 1: + // Skip the key + cursor++; + + if(cursor->type != BNT_STRING) { + err("Wrong value type for response"); + exit(EXIT_FAILURE); + } + + if(cursor->size != 20) { + err("remote node id was not 20 bytes long"); + exit(EXIT_FAILURE); + } + + memcpy(&id, cursor->loc, 20); + + // Skip the value + cursor++; + break; + } + assert(cursor < stream+len); + } + } + + // Print the candidates + for(uint8_t i = 0; i < nodes_len; i++) { + dbgl_id(&nodes[i]); + printf("Candidate %s:%d\n", inet_ntoa(ips[i]), ntohs(ports[i])); + + struct sockaddr_in dest = { + .sin_family = AF_INET, + .sin_addr = ips[i], + .sin_port = ports[i], + }; + + if(routing_interested(&nodes[i])) { + int rc = send_ping(self, socket, (struct sockaddr*)&dest, sizeof(struct sockaddr_in)); + if(rc != 0) { + err("send_ping failed %d", rc); + } + } else { + dbg("Not interested in node"); + } + } + + struct entry* entry; + routing_offer(&id, &entry); +} + int main(int argc, char** argv) { + for(int i = 0; i < MAX_DISC; i++) { + // 192.0.2.0 + addrs[i] = UNDEF_ADDR; + } + + struct nodeid self = {.inner={0x0034048f, 0x08000020, 0x00888880, 0x02008460, 0x0ab00521}}; + routing_init(&self); + dbgl_id(&self); - struct nodeid a = {0}; - a.inner[1] = 0xFFFFFFFF; - routing_init(&a); + int sfd = socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP); + if(sfd == -1) { + err("Failed creating socket"); + exit(1); + } + struct sockaddr_in bindAddr = {0}; + bindAddr.sin_family = AF_INET; + bindAddr.sin_port = htons(6881); + bindAddr.sin_addr.s_addr = htonl(INADDR_ANY); + bind(sfd, (struct sockaddr*)&bindAddr, sizeof(struct sockaddr_in)); + struct addrinfo hints = {0}; + hints.ai_family = AF_INET; + hints.ai_socktype = SOCK_DGRAM; + hints.ai_protocol = IPPROTO_UDP; + hints.ai_flags = AI_NUMERICSERV; - 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; + struct addrinfo* res; + int rc = getaddrinfo("router.bittorrent.com", "6881", &hints, &res); + if(rc != 0) { + err("Failed getting the bootstrap ip: %s", gai_strerror(rc)); + exit(EXIT_FAILURE); } - b.inner[1] = 0xFFFFFFFF; - b.inner[4] = 0x00000002; - if(routing_offer(&b, &entry)) { - entry->addr.ip = 0; - entry->addr.port = 0; + for(struct addrinfo* cur = res; cur != NULL; cur = cur->ai_next) { + char buff[128]; + inet_ntop(cur->ai_family, &((struct sockaddr_in*)cur->ai_addr)->sin_addr, buff, 128); + dbg("IP %s", buff); + + /* size_t i = 0; */ + /* int rc = snprintf(buff+i, 128-i, "d1:ad2:id20:"); */ + /* i += rc; */ + /* memcpy(buff+i, &self, sizeof(struct nodeid)); */ + /* i += sizeof(struct nodeid); */ + /* rc = snprintf(buff+i, 128-i, "e1:q4:ping1:t2:ab1:y1:qe"); */ + /* i += rc; */ + + send_ping(&self, sfd, cur->ai_addr, cur->ai_addrlen); } - struct entry *found[10]; - size_t nfound = routing_closest(&b, 10, found); + freeaddrinfo(res); + + //keep listening for data + while(1) { + char buff[2049]; + printf("Waiting for data..."); + fflush(stdout); + + //try to receive some data, this is a blocking call + ssize_t recv_len; + struct sockaddr_in remote; + socklen_t remote_len = sizeof(remote); + if ((recv_len = recvfrom(sfd, buff, 2048, 0, (struct sockaddr *)&remote, &remote_len)) == -1) { + fatal("recvfrom failed"); + } + if(recv_len >= 2048) { + fatal("Recv buffer too small"); + } + // Null terminate the packet + buff[recv_len] = '\0'; - for(size_t i = 0; i < nfound; i++) { - dbgl_id(&found[i]->id); + printf("Received packet from %s:%d\n", inet_ntoa(remote.sin_addr), ntohs(remote.sin_port)); + + struct benc_node stream[256]; + const char* cursor = buff; + int depth = 0; + int len = benc_decode(&cursor, buff+recv_len, &depth, stream, 256); + benc_print(stream, len, &depth); + + struct benc_node* stream_cursor = stream; + if(stream_cursor->type != BNT_DICT) { + err("Response is not a dict"); + exit(EXIT_FAILURE); + } + stream_cursor++; + + if(skip_to_key((const struct benc_node**)&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"t"}, (const size_t[]){1}, 1) == -1) { + err("No t key in packet"); + exit(EXIT_FAILURE); + } + stream_cursor++; + + char char_buffer = stream_cursor->loc[stream_cursor->size]; + ((char*)stream_cursor->loc)[stream_cursor->size] = '\0'; + uint32_t transaction = strtol(stream_cursor->loc, NULL, 10); + ((char*)stream_cursor->loc)[stream_cursor->size] = char_buffer; + + uint16_t reqId; + if(!find_req(transaction, &reqId)) { + err("No request with transaction ID %d", transaction); + exit(EXIT_FAILURE); + } + dbg("Transaction id matches requst %d", reqId); + + if(sockaddr_cmp(&requestdata[reqId].addr, (struct sockaddr*)&remote) != 0) { + err("Unexpected IP for valid transaction"); + exit(EXIT_FAILURE); + } + + requestdata[reqId].fun(&self, buff, recv_len, sfd, &remote, remote_len); + + reqalloc[reqId] = false; } + close(sfd); + return 0; } diff --git a/src/routing.c b/src/routing.c index ff7eadc..b8ab037 100644 --- a/src/routing.c +++ b/src/routing.c @@ -82,6 +82,28 @@ int8_t scan(uint16_t baseIndex, struct nodeid* id) { return index; } +bool routing_interested(struct nodeid* id) { + uint16_t bucketIndex = prefix(&myID, id); + // The nodeid is the same as our own + 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; + 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 + return false; + } + + return true; +} + // Offer the routing table a new node bool routing_offer(struct nodeid* id, struct entry **dest) { uint16_t bucketIndex = prefix(&myID, id); diff --git a/src/routing.h b/src/routing.h index b0e9922..540f3f6 100644 --- a/src/routing.h +++ b/src/routing.h @@ -6,18 +6,6 @@ #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) - - struct addr { uint32_t ip; uint16_t port; @@ -36,5 +24,6 @@ struct entry { void routing_init(struct nodeid* myid); void routing_flush(); +bool routing_interested(struct nodeid* id); bool routing_offer(struct nodeid* id, struct entry **dest); size_t routing_closest(struct nodeid* needle, size_t n, struct entry** res); diff --git a/test/benc.c b/test/benc.c new file mode 100644 index 0000000..a60e8f0 --- /dev/null +++ b/test/benc.c @@ -0,0 +1,366 @@ +#include "unity.h" +#include "benc.h" + +#include + +void test_string() { + struct benc_node stream[1]; + char* packet = "3:abc"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 1); + + TEST_ASSERT_EQUAL(1, len); + TEST_ASSERT_EQUAL(BNT_STRING, stream[0].type); + TEST_ASSERT_EQUAL(3, stream[0].size); + TEST_ASSERT_EQUAL_PTR(packet + 2, stream[0].loc); +} + +void test_unfinished_string() { + struct benc_node stream[1]; + // There only 3 chars available + char* packet = "4:abc"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 1); + + TEST_ASSERT_EQUAL(0, len); + TEST_ASSERT_EQUAL(BNT_STRING, stream[0].type); + TEST_ASSERT_EQUAL(4, stream[0].size); + TEST_ASSERT_EQUAL_PTR(packet + 2, stream[0].loc); +} + +void test_positive_int() { + struct benc_node stream[1]; + char* packet = "i3e"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 1); + + TEST_ASSERT_EQUAL(1, len); + TEST_ASSERT_EQUAL(BNT_INT, stream[0].type); + TEST_ASSERT_EQUAL(1, stream[0].size); + TEST_ASSERT_EQUAL_PTR(packet + 1, stream[0].loc); +} + +void test_multiple_int() { + struct benc_node stream[2]; + char* packet = "i3ei3e"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 2); + + // Stop after the first int + TEST_ASSERT_EQUAL(packet + 3, cursor); + TEST_ASSERT_EQUAL(1, len); + TEST_ASSERT_EQUAL(BNT_INT, stream[0].type); + TEST_ASSERT_EQUAL(1, stream[0].size); + TEST_ASSERT_EQUAL_PTR(packet + 1, stream[0].loc); +} + +void test_unfinished_int() { + struct benc_node stream[1]; + char* packet = "i3"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 1); + + TEST_ASSERT_EQUAL(0, len); + TEST_ASSERT_EQUAL(BNT_INT, stream[0].type); + TEST_ASSERT_EQUAL_PTR(packet + 1, stream[0].loc); +} + +void test_negative_int() { + struct benc_node stream[1]; + char* packet = "i-3e"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 1); + + TEST_ASSERT_EQUAL(1, len); + TEST_ASSERT_EQUAL(BNT_INT, stream[0].type); + TEST_ASSERT_EQUAL(2, stream[0].size); + TEST_ASSERT_EQUAL_PTR(packet + 1, stream[0].loc); +} + +void test_incorrect_int_char() { + struct benc_node stream[1]; + char* packet = "i-a3e"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 1); + + TEST_ASSERT_EQUAL(packet + 2, cursor); + TEST_ASSERT_EQUAL(0, len); + TEST_ASSERT_EQUAL(BNT_INT, stream[0].type); + TEST_ASSERT_EQUAL_PTR(packet + 1, stream[0].loc); +} + +void test_list() { + struct benc_node stream[3]; + char* packet = "li1ee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 3); + + TEST_ASSERT_EQUAL(3, len); + size_t nodeCursor = 0; + TEST_ASSERT_EQUAL(BNT_LIST, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(0, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 0, stream[nodeCursor].loc); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_INT, stream[nodeCursor].type); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_END, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(0, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 4, stream[nodeCursor].loc); + nodeCursor++; +} + +void test_dict() { + struct benc_node stream[4]; + char* packet = "d1:a1:be"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 4); + + TEST_ASSERT_EQUAL(4, len); + size_t nodeCursor = 0; + TEST_ASSERT_EQUAL(BNT_DICT, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(0, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 0, stream[nodeCursor].loc); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_STRING, stream[nodeCursor].type); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_STRING, stream[nodeCursor].type); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_END, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(0, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 7, stream[nodeCursor].loc); + nodeCursor++; +} + +void test_nested_list() { + struct benc_node stream[5]; + char* packet = "lli1eee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 5); + + TEST_ASSERT_EQUAL(5, len); + size_t nodeCursor = 0; + TEST_ASSERT_EQUAL(BNT_LIST, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(0, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 0, stream[nodeCursor].loc); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_LIST, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(1, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 1, stream[nodeCursor].loc); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_INT, stream[nodeCursor].type); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_END, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(1, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 5, stream[nodeCursor].loc); + nodeCursor++; + TEST_ASSERT_EQUAL(BNT_END, stream[nodeCursor].type); + TEST_ASSERT_EQUAL(0, stream[nodeCursor].depth); + TEST_ASSERT_EQUAL_PTR(packet + 6, stream[nodeCursor].loc); + nodeCursor++; +} + +void test_parse_int() { + char* packet = "100"; + + const char* cursor = packet; + int64_t val; + bool rc = readint(&cursor, &val); + + TEST_ASSERT_EQUAL(true, rc); + TEST_ASSERT_EQUAL(100, val); + TEST_ASSERT_EQUAL_PTR(packet + 3, cursor); +} + +void test_parse_negative_int() { + char* packet = "-100"; + + const char* cursor = packet; + int64_t val; + bool rc = readint(&cursor, &val); + + TEST_ASSERT_EQUAL(true, rc); + TEST_ASSERT_EQUAL(-100, val); + TEST_ASSERT_EQUAL_PTR(packet + 4, cursor); +} + +void test_stop_at_non_digit() { + char* packet = "10a1"; + + const char* cursor = packet; + int64_t val; + bool rc = readint(&cursor, &val); + + TEST_ASSERT_EQUAL(true, rc); + TEST_ASSERT_EQUAL(10, val); + TEST_ASSERT_EQUAL_PTR(packet + 2, cursor); +} + +void test_stop_embedded_minus() { + char* packet = "10-1"; + + const char* cursor = packet; + int64_t val; + bool rc = readint(&cursor, &val); + + TEST_ASSERT_EQUAL(true, rc); + TEST_ASSERT_EQUAL(10, val); + TEST_ASSERT_EQUAL_PTR(packet + 2, cursor); +} + +void test_find_key_under_cursor() { + struct benc_node stream[4]; + char* packet = "d1:ri1ee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 4); + + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // Skip the dict + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"r"}, (const size_t[]){1}, 1); + + TEST_ASSERT_EQUAL(0, found); + TEST_ASSERT_EQUAL_PTR(stream+1, stream_cursor); +} + +void test_key_not_found() { + struct benc_node stream[4]; + char* packet = "d1:ri1ee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 4); + + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // Skip the dict + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"a"}, (const size_t[]){1}, 1); + + TEST_ASSERT_EQUAL(-1, found); + TEST_ASSERT_EQUAL_PTR(stream+3, stream_cursor); +} + +void test_skip_nested_list_value() { + struct benc_node stream[8]; + char* packet = "d1:al1:re1:ri1ee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 8); + + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // We know the first is a dict + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"r"}, (const size_t[]){1}, 1); + + TEST_ASSERT_EQUAL(0, found); + TEST_ASSERT_EQUAL_PTR(stream+5, stream_cursor); +} + +void test_skip_nested_dict_value() { + struct benc_node stream[9]; + char* packet = "d1:adi2e1:re1:ri1ee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 9); + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // We know the first is a dict + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"r"}, (const size_t[]){1}, 1); + + TEST_ASSERT_EQUAL(0, found); + TEST_ASSERT_EQUAL_PTR(stream+6, stream_cursor); +} + +void test_skip_nested_dict_key() { + struct benc_node stream[9]; + char* packet = "d1:ad1:ri2ee1:ri1ee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 9); + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // We know the first is a dict + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"r"}, (const size_t[]){1}, 1); + + TEST_ASSERT_EQUAL(0, found); + TEST_ASSERT_EQUAL_PTR(stream+6, stream_cursor); +} + +void test_skip_multilevel_list() { + struct benc_node stream[9]; + char* packet = "d1:all1:ree1:ri1ee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 9); + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // We know the first is a dict + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"r"}, (const size_t[]){1}, 1); + + TEST_ASSERT_EQUAL(0, found); + TEST_ASSERT_EQUAL_PTR(stream+7, stream_cursor); +} + +void test_find_any_semantics() { + struct benc_node stream[9]; + char* packet = "d1:a1:a1:b1:be"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 9); + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // We know the first is a dict + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING, BNT_STRING}, (const char*[]){"b", "a"}, (const size_t[]){1, 1}, 2); + + TEST_ASSERT_EQUAL(1, found); + TEST_ASSERT_EQUAL_PTR(stream+1, stream_cursor); + + stream_cursor+=2; // Skip the key and value + found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING, BNT_STRING}, (const char*[]){"b", "a"}, (const size_t[]){1, 1}, 2); + TEST_ASSERT_EQUAL(0, found); + TEST_ASSERT_EQUAL_PTR(stream+3, stream_cursor); +} + +void test_stop_at_end() { + struct benc_node stream[9]; + char* packet = "ld1:a1:aee"; + + const char* cursor = packet; + int depth = 0; + int64_t len = benc_decode(&cursor, cursor + strlen(packet), &depth, stream, 9); + + const struct benc_node* stream_cursor = stream; + stream_cursor++; // We know the first is a list + stream_cursor++; // We know the second is a dict + // X does not exist in the packet + ssize_t found = skip_to_key(&stream_cursor, stream+len, (const enum benc_nodetype[]){BNT_STRING}, (const char*[]){"x"}, (const size_t[]){1}, 1); + + TEST_ASSERT_EQUAL_MESSAGE(-1, found, "Found something"); + TEST_ASSERT_EQUAL_PTR_MESSAGE(stream+4, stream_cursor, "Didn't stop at dict end"); +} diff --git a/test/routing.c b/test/routing.c index c4b7730..60a7f03 100644 --- a/test/routing.c +++ b/test/routing.c @@ -91,3 +91,54 @@ void test_discard_offer_when_nodeid_added_twice() { bool accept = routing_offer(&new, &entry); TEST_ASSERT_FALSE_MESSAGE(accept, "Accepted entry when bucket was full"); } + +void test_interested_when_space_in_bucket() { + routing_flush(); + + struct nodeid new = self; + new.inner[4] ^= 0x00000001; + + bool interest = routing_interested(&new); + + TEST_ASSERT_TRUE_MESSAGE(interest, "Was not interested in node"); +} + +void test_not_interested_when_nodeid_in_table() { + routing_flush(); + + struct nodeid new = self; + new.inner[4] ^= 0x00000001; + + struct entry* entry; + TEST_ASSERT_TRUE(routing_offer(&new, &entry)); + entry->addr = (struct addr){.ip = IP(128,0,0,1), .port = 0}; + entry->last = time(NULL); + + bool interest = routing_interested(&new); + TEST_ASSERT_FALSE_MESSAGE(interest, "Was interested in node"); +} + +void test_not_interested_when_bucket_is_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; + } + + TEST_ASSERT_FALSE_MESSAGE(routing_interested(&new), "Still interested when bucket was full"); +} -- cgit v1.2.3