diff options
Diffstat (limited to 'src/dht.c')
| -rw-r--r-- | src/dht.c | 748 |
1 files changed, 538 insertions, 210 deletions
@@ -11,6 +11,7 @@ #include <arpa/nameser.h> #include <resolv.h> #include <limits.h> +#include <assert.h> #define ECB 1 #define AES128 1 #include <aes.c> @@ -29,6 +30,27 @@ int family (const unsigned char * addr) { #define K 8 /** + * writes a hexadecimal representation of a binary string. does not NULL terminate destination. + * + * h and b may not overlap. period. + * + * @param h [out] destination (requires 2l space) + * @param b [in] source + * @param l [in] length of source + */ + +void bin2hex (char * h, const unsigned char * b, size_t l) { + for (size_t i = 0; i < l; i++) { + int ms = b[i] >> 4; + int ls = b[i] & 0xF; + assert(ms < 16); + assert(ls < 16); + *h++ = ms < 10 ? '0'+ms : 'a'+ms-10; + *h++ = ls < 10 ? '0'+ls : 'a'+ls-10; + } +} + +/** * node representation */ @@ -50,7 +72,7 @@ struct node * node_init (void) { if (!n) return NULL; n->last_received = seconds(); - n->addr.sin6_family = AF_INET; + n->addr.sin6_family = AF_INET6; return n; } @@ -65,6 +87,23 @@ void node_free (struct node * n) { } /** + * print node to stream, for debugging + * + * @param s [out] the stream to which to print to + * @param n [in] the node to be printed + */ + +void node_print (FILE * s, const struct node * n) { + char buf[41]; + buf[40] = '\0'; + bin2hex(buf, n->id, 20); + char remote[INET6_ADDRSTRLEN + 64]; + if (!inet_ntop(n->addr.sin6_family, n->addr.sin6_addr.s6_addr, remote, INET6_ADDRSTRLEN+7)) + snprintf(remote, sizeof remote, "(inet_ntop: %s)", strerror(errno)); + fprintf(s, "%s %s/%d unans=%d", buf, remote, ntohs(n->addr.sin6_port), n->unanswered); +} + +/** * returns which 20 byte bytestring is closer with XOR metric to target 20 byte bytestring * * at most 20 bytes are read from each pointer @@ -132,6 +171,16 @@ struct peer { }; /** + * init a torrent peer + */ + +struct peer * peer_init () { + struct peer * p = calloc(1, sizeof *p); + p->addr.sin6_family = AF_INET6; + return p; +} + +/** * free a torrent peer */ @@ -140,6 +189,20 @@ void peer_free (struct peer * p) { } /** + * print a peer, for debugging purposes + * + * @param s [out] stream + * @param p [in] peer + */ + +void peer_print (FILE * s, const struct peer * p) { + char remote[INET6_ADDRSTRLEN + 64]; + if (!inet_ntop(p->addr.sin6_family, p->addr.sin6_addr.s6_addr, remote, INET6_ADDRSTRLEN+7)) + snprintf(remote, sizeof remote, "(inet_ntop: %s)", strerror(errno)); + fprintf(s, "%s:%d", remote, ntohs(p->addr.sin6_port)); +} + +/** * reason why a torrent is in our database. 0 just means it is stored as a result of an announce */ @@ -192,6 +255,35 @@ int torrent_compare (const void * a, const void * b) { } /** + * prints a torrent, for debugging purposes + * + * @param s [out] stream to which to write to + * @param t [in] the torrent to print + */ + +void torrent_print (FILE * s, const struct torrent * t) { + char buf[41]; + buf[40] = '\0'; + bin2hex(buf, t->hash, 20); + printf("magnet:?xt=urn:btih:%s\n\t**** PEERS ****\n", buf); + struct peer * p = t->peers; + while (p) { + fprintf(s, "\t"); + peer_print(s, p); + fprintf(s, "\n"); + p = p->next; + } + printf("\t**** NODES ****\n"); + struct node * n = t->nodes; + while (n) { + fprintf(s, "\t"); + node_print(s, n); + fprintf(s, "\n"); + n = n->next; + } +} + +/** * handle for the library */ @@ -220,6 +312,53 @@ struct dht { }; /** + * prints a dht, for debugging + * + * @param s [out] stream + * @param d [in] dht + */ + +void dht_print (FILE * s, const struct dht * d) { + char buf[41]; + buf[40] = '\0'; + bin2hex(buf, d->id, 20); + char secret[17*2]; + secret[17*2+1] = '\0'; + bin2hex(secret, d->secret, 16); + fprintf(s, "id=%s socket=%d dl=%d t=%u p=%u tmax=%u pmax=%u p/t-max=%u runsec=%ld rxp=%u txp=%u rxb=%u txb=%u secret=%s\n", buf, d->socket, d->dl, d->torrents_num, d->peers_num, d->torrents_max, d->peers_max, d->peers_per_torrent_max, seconds()-d->time, d->rxp, d->txp, d->rxb, d->txb, secret); + printf("**** TORRENTS ****\n"); + struct torrent * t = d->torrents; + while (t) { + torrent_print(s, t); + t = t->next; + } + fprintf(s, "**** NODES ****\n"); + int nodes = 0; + for (int i = 0; i <= 1; i++) { + struct bucket * b = d->buckets; + if (i) + b = d->buckets6; + int buckets = 0; + while (b) { + buckets++; + bin2hex(buf, b->id, 20); + fprintf(s, "\tBUCKET id=%s\n", buf); + struct node * n = b->nodes; + while (n) { + nodes++; + fprintf(s, "\t"); + node_print(s, n); + fprintf(s, "\n"); + n = n->next; + } + b = b->next; + } + fprintf(s, "\t**** COUNT OF %s BUCKETS: %d\n", i ? "IPv4" : "IPV6", buckets); + } + fprintf(s, "**** COUNT OF NODES: %d\n", nodes); +} + +/** * a dummy function that does nothing that is set as the default for possible_torrent in struct dht * * @param d [in] the dht library handler @@ -238,7 +377,7 @@ void possible_torrent (struct dht * d __attribute__((unused)), const unsigned ch * @param ... [in] variable arguments to go with f */ -#define L(o, f, ...) do {char t[512]; time_t n = time(NULL); strftime(t, 512, "%c", localtime(&n)); fprintf(o, "[%s] %s()%s:%d: " f "\n", t, __func__, __FILE__, __LINE__ __VA_OPT__(,) __VA_ARGS__);} while (0) +#define L(Lo, Lf, ...) do {char Lt[512]; time_t Ln = time(NULL); strftime(Lt, 512, "%c", localtime(&Ln)); fprintf(Lo, "[%s] %s()%s:%d: " Lf "\n", Lt, __func__, __FILE__, __LINE__ __VA_OPT__(,) __VA_ARGS__);} while (0) /** * sends a bencoding object to the remote node. does not free the input bencoding. inserts a v key to the input bencoding. @@ -249,10 +388,10 @@ void possible_torrent (struct dht * d __attribute__((unused)), const unsigned ch */ void sendb (struct dht * d, struct bencoding * b, const struct sockaddr_in6 * a) { - char remote[INET6_ADDRSTRLEN + 7]; + char remote[INET6_ADDRSTRLEN + 64]; if (!inet_ntop(a->sin6_family, &a->sin6_addr, remote, INET6_ADDRSTRLEN+7)) snprintf(remote, sizeof remote, "(inet_ntop: %s)", strerror(errno)); - sprintf(remote+strlen(remote), ":%d", ntohs(((struct sockaddr_in6 *) a)->sin6_port)); + sprintf(remote+strlen(remote), "/%d", ntohs(((struct sockaddr_in6 *) a)->sin6_port)); struct bencoding * v = bstr(strdup("TK00")); v->key = bstr(strdup("v")); binsert(b, v); @@ -275,6 +414,8 @@ void sendb (struct dht * d, struct bencoding * b, const struct sockaddr_in6 * a) #pragma GCC diagnostic pop } +#define GENERIC_T "a@4" "a.si" /**< generic token that we send if we have no statekeeping to do - developer's email address */ + /** * sends a find_node query to a "raw node" * @@ -286,14 +427,13 @@ void sendb (struct dht * d, struct bencoding * b, const struct sockaddr_in6 * a) void find_node (struct dht * d, const struct sockaddr_in6 * addr, const unsigned char * query) { struct bencoding * b = calloc(1, sizeof *b); b->type = dict; - struct bencoding * t = calloc(1, sizeof *t); - memcpy((t->value = malloc(20)), query, (t->valuelen = 20)); + struct bencoding * t = bstr(strdup(GENERIC_T)); t->key = bstr(strdup("t")); t->type = string; binsert(b, t); struct bencoding * y = bstr(strdup("q")); - t->key = bstr(strdup("y")); - t->type = string; + y->key = bstr(strdup("y")); + y->type = string; binsert(b, y); struct bencoding * q = bstr(strdup("find_node")); q->key = bstr(strdup("q")); @@ -301,10 +441,11 @@ void find_node (struct dht * d, const struct sockaddr_in6 * addr, const unsigned binsert(b, q); struct bencoding * a = calloc(1, sizeof *a); a->type = dict; + a->key = bstr(strdup("a")); struct bencoding * id = calloc(1, sizeof *id); id->type = string; id->valuelen = 20; - id->key = bstr(strdup("key")); + id->key = bstr(strdup("id")); memcpy((id->value = malloc(20)), d->id, 20); binsert(a, id); struct bencoding * want = calloc(1, sizeof *want); // BEP-0032 @@ -316,8 +457,7 @@ void find_node (struct dht * d, const struct sockaddr_in6 * addr, const unsigned struct bencoding * target = calloc(1, sizeof *target); target->key = bstr(strdup("target")); target->type = string; - target->valuelen = 20; - memcpy((target->value = malloc(20)), query, 20); + memcpy((target->value = malloc(20)), query, (target->valuelen = 20)); binsert(a, target); binsert(b, a); sendb(d, b, addr); @@ -399,13 +539,15 @@ struct dht * dht_init (const struct bencoding * c) { if (id && id->type & string && id->valuelen == 20) memcpy(d->id, id->value, 20); bforeach (bpath(c, "nodes"), str) { - struct sockaddr_in6 addr; + struct sockaddr_in6 addr = { + .sin6_family = AF_INET6 + }; char remote[INET6_ADDRSTRLEN + 7]; strncpy(remote, str->value, str->valuelen); char * port = strchr(remote, '/'); port[0] = '\0'; if (port) { - if (inet_pton(AF_INET6, remote, &addr) == 1) { + if (inet_pton(AF_INET6, remote, addr.sin6_addr.s6_addr) == 1) { addr.sin6_port = htons(atoi(++port)); ping_node(d, &addr); } @@ -483,18 +625,22 @@ struct bencoding * persistent (const struct dht * d) { struct bencoding * nodes = calloc(1, sizeof *nodes); nodes->type = list; nodes->key = bstr(strdup("nodes")); - struct bucket * bucket = d->buckets; - while (bucket) { - struct node * node = bucket->nodes; - while (node) { - char remote[INET6_ADDRSTRLEN + 7]; - if (inet_ntop(AF_INET6, &node->addr.sin6_addr, remote, INET6_ADDRSTRLEN+7)) { - sprintf(remote+strlen(remote), "/%u", ntohs(node->addr.sin6_port)); - binsert(nodes, bstr(strdup(remote))); + for (int i = 0; i <= 1; i++) { + struct bucket * bucket = d->buckets; + if (i) + bucket = d->buckets6; + while (bucket) { + struct node * node = bucket->nodes; + while (node) { + char remote[INET6_ADDRSTRLEN + 7]; + if (inet_ntop(AF_INET6, &node->addr.sin6_addr, remote, INET6_ADDRSTRLEN+7)) { + sprintf(remote+strlen(remote), "/%u", ntohs(node->addr.sin6_port)); + binsert(nodes, bstr(strdup(remote))); + } + node = node->next; } - node = node->next; + bucket = bucket->next; } - bucket = bucket->next; } binsert(b, nodes); return b; @@ -591,49 +737,87 @@ struct node * find (const unsigned char * id, struct bucket ** b, struct node ** } if (n) *n = prev; - return node; + if (node && !memcmp((node)->id, id, 20)) + return node; + else + return NULL; } /** - * find the middle point of a bucket/or two 20 byte bytestrings + * add two 20 byte numbers * - * @param r [out] midpoint - * @param a [in] lower boundary - * @param b [in] upper boundary. if NULL, 0xffffffffffffffffffffffffffffffffffffffff is assumed + * @param a [io] result and first operand + * @param b [in] second operand */ -void midpoint (unsigned char * r, const unsigned char * a, const unsigned char * b) { - unsigned char up[20]; - for (int i = 0; i < 20; i++) - up[i] = 0xFF; - if (b) - memcpy(up, b, 20); +void add (unsigned char * a, const unsigned char * b) { unsigned carry = 0; for (int i = 19; i >= 0; i--) { - if (carry + (unsigned) up[i] < (unsigned) a[i]) { - r[i] = (unsigned) up[i] + 255 - (unsigned) a[i]; - carry = 1; - } else { - r[i] = (unsigned) up[i] - (unsigned) a[i]; - carry = 0; - if (r[i] & 1 && i != 19) - r[i+1] |= 1 << 7; - r[i] >>= 1; - } + unsigned cursum = (unsigned) a[i] + (unsigned) b[i] + carry; + carry = 0; + if (cursum > 255) { + carry = cursum / 256; + a[i] = cursum % 256; + } else + a[i] = cursum; } - carry = 0; +} + +/** + * subtract two 20 byte numbers + * + * @param a [io] result and first operand + * @param b [in] second operand + */ + +void subtract (unsigned char * a, const unsigned char * b) { + int carry = 0; for (int i = 19; i >= 0; i--) { - if (carry + (unsigned) r[i] + (unsigned) a[i] > 255) { - r[i] = r[i] + a[i] - 255; - carry = 1; - } else { - r[i] = r[i] + a[i]; - carry = 0; + int cur = (int) a[i] - ((int) b[i] + carry); + carry = 0; + while (cur < 0) { + cur += 256; + carry++; } + a[i] = cur; + } +} + +/** + * divide a 20 byte number with 2 + * + * @param a [io] result and operand + */ + +void divide (unsigned char * a) { + for (int i = 19; i >= 0; i--) { + a[i] >>= 1; + if (i && a[i-1] & 1) + a[i] |= 1 << 7; } } /** + * find the middle point of a bucket/or two 20 byte bytestrings + * + * arguments must not overlap + * + * @param r [out] midpoint. caller must provide 20 bytes here + * @param a [in] lower boundary + * @param b [in] upper boundary. if NULL, 0xffffffffffffffffffffffffffffffffffffffff is assumed + */ + +void midpoint (unsigned char * r, const unsigned char * a, const unsigned char * b) { + for (int i = 0; i < 20; i++) + r[i] = 0xFF; + if (b) + memcpy(r, b, 20); + subtract(r, a); + divide(r); + add(r, a); +} + +/** * splits a bucket * * @param b [in] the bucket to split @@ -724,11 +908,14 @@ int bucket_good (const struct dht * d, const struct bucket * b) { if (in_bucket(d->id, b)) { struct node * n = b->nodes; while (n->next) { - if (distance(n->id, n->next->id) <= 2) // we allow holes of 1, since we don't actually store our ID in the bucket + if (distance(n->id, n->next->id) > 1) // we allow holes of 1, since we don't actually store our ID in the bucket return 0; // it's really impossible that a non-malicious node would by chance get so close + n = n->next; } + // L(d->log, "our bucket filled"); return 1; } + // L(d->log, "not our bucket and filled"); return 1; } else { if (node_count(b->nodes) < K) @@ -750,12 +937,20 @@ int bucket_good (const struct dht * d, const struct bucket * b) { * * if the node is found in a bucket, it's last received time and unanswered are updated * + * TODO: this could be refactored so that it reuses logic from potential_node, like done in replied_torrent_node() below + * * @param d [in] handle * @param id [in] node id that was received * @param addr [in] address from which the id was received */ void replied (const struct dht * d, const unsigned char * id, const struct sockaddr_in6 * addr) { + if (!memcmp(d->id, id, 20)) // WE COULDN'T'VE POSSIBLY REPLIED TO OURSELVES! + return; + char buf[41]; + buf[40] = '\0'; + bin2hex(buf, id, 20); + // L(d->log, "%s replied", buf); struct bucket * b = d->buckets; if (family(addr->sin6_addr.s6_addr) == AF_INET6) b = d->buckets6; @@ -764,10 +959,13 @@ void replied (const struct dht * d, const unsigned char * id, const struct socka if (found) { found->last_received = seconds(); found->unanswered = 0; + // L(d->log, "found"); return; } - if (bucket_good(d, b)) + if (bucket_good(d, b)) { + // L(d->log, "bucket good"); return; + } struct node * node = node_init(); memcpy(&node->addr, addr, sizeof *addr); memcpy(node->id, id, 20); @@ -784,12 +982,6 @@ void replied (const struct dht * d, const unsigned char * id, const struct socka return; } if (in_bucket(d->id, b)) { - struct node * n = b->nodes; - while (n->next) - if (distance(n->id, n->next->id) != 1) // at least one gap, if not, then we have the innermost bucket full - goto ok; - return; - ok: node_free(node); split(b); replied(d, id, addr); // find bucket again @@ -797,43 +989,46 @@ void replied (const struct dht * d, const unsigned char * id, const struct socka } /** - * when we are sure that a node exists on a specific ip:port and we know it's port, but we are unsure if the node is already in the routing table, we call this function, which makes a query to this node if it's a candidate for filling the routing table. this doesn't yet add it to the routing table, because we are unsure if it's a good node / can respond to queries. replied() is called if a node replied to our query. + * when we are sure that a node exists on a specific ip:port and we know it's id, but we are unsure if the node is already in the routing table, we call this function, which makes a query to this node if it's a candidate for filling the routing table. this doesn't yet add it to the routing table, because we are unsure if it's a good node / can respond to queries. replied() is called if a node replied to our query. * * see NOTE02 - * - * if any of d or id is NULL, it's assumed we don't have this node. this is used for bootstrapping - * + * * @param d [in] library handle * @param a [in] pointer to sockaddr of the node * @param id [in] id of the node, 20 bytes is read from this address */ void potential_node (struct dht * d, const struct sockaddr_in6 * a, const unsigned char * id) { - if (!id || !d) - goto j; // just do it + if (!memcmp(d->id, id, 20)) // we are not a potential node of ourselves + return; struct bucket * bucket = d->buckets; if (family(a->sin6_addr.s6_addr) == AF_INET6) bucket = d->buckets6; if (find(id, &bucket, NULL)) return; - if (!bucket_good(d, bucket)) { - j: + if (!bucket_good(d, bucket)) ping_node(d, a); - } } +#define MAXT 15 /**< see NOTE04 */ + /** * find a torrent based on hash * + * NOTE04: full length 20 byte binary hash can't be stored in "t" because some nodes' software discards t if it's longer than MAXT bytes + * + * that's why this function accepts shorter lengths to compare. + * * @param d [in] the library handle - * @param h [in] a 20 byte infohash + * @param h [in] an l-byte infohash + * @param l [in] number of bytes of infohash to compare - for truncated hashes. full hash is 20 bytes long. * @return pointer to torrent or NULL */ -struct torrent * find_torrent (struct dht * d, const unsigned char * h) { +struct torrent * find_torrent (struct dht * d, const unsigned char * h, int l) { struct torrent * t = d->torrents; while (t) { - if (!memcmp(t->hash, h, 20)) + if (!memcmp(t->hash, h, l)) return t; t = t->next; } @@ -891,7 +1086,7 @@ void oom (struct dht * d) { */ struct torrent * add_torrent (struct dht * d, struct torrent * t) { - struct torrent * found = find_torrent(d, t->hash); + struct torrent * found = find_torrent(d, t->hash, 20); if (found) { found->type |= t->type; torrent_free(t); @@ -921,21 +1116,15 @@ struct torrent * add_torrent (struct dht * d, struct torrent * t) { struct peer * add_peer (struct dht * d, struct torrent * t, struct peer * p) { struct peer * peer = t->peers; - unsigned i = 0; while (peer) { if (!memcmp(&peer->addr, &p->addr, sizeof p->addr)) { peer_free(p); return peer; } - if (peer->next && !peer->next->next) - if (++i >= d->peers_per_torrent_max) { - d->peers_num--; - peer_free(peer->next); - peer->next = NULL; - } + peer = peer->next; } - peer->next = t->peers; - t->peers = peer; + p->next = t->peers; + t->peers = p; d->peers_num++; if (d->peers_num >= d->peers_max) oom(d); @@ -943,6 +1132,159 @@ struct peer * add_peer (struct dht * d, struct torrent * t, struct peer * p) { } /** + * sends a get_peers query to a raw node + * + * @param d [in] handle + * @param a [in] address + * @param q [in] 20 byte hash we query for + */ + +void get_peers (struct dht * d, const struct sockaddr_in6 * addr, const unsigned char * q) { + struct bencoding * b = calloc(1, sizeof *b); + b->type = dict; + struct bencoding * t = calloc(1, sizeof *t); + memcpy((t->value = malloc(MAXT)), q, (t->valuelen = MAXT)); + t->key = bstr(strdup("t")); + t->type = string; + binsert(b, t); + struct bencoding * y = bstr(strdup("q")); + y->key = bstr(strdup("y")); + y->type = string; + binsert(b, y); + struct bencoding * q_elem = bstr(strdup("get_peers")); + q_elem->key = bstr(strdup("q")); + q_elem->type = string; + binsert(b, q_elem); + struct bencoding * a = calloc(1, sizeof *a); + a->key = bstr(strdup("a")); + a->type = dict; + struct bencoding * id = calloc(1, sizeof *id); + id->type = string; + id->valuelen = 20; + id->key = bstr(strdup("id")); + memcpy((id->value = malloc(20)), d->id, 20); + binsert(a, id); + struct bencoding * want = calloc(1, sizeof *want); // BEP-0032 + want->key = bstr(strdup("want")); + want->type = list; + binsert(want, bstr(strdup("n4"))); + binsert(want, bstr(strdup("n6"))); + binsert(a, want); + struct bencoding * info_hash = calloc(1, sizeof *info_hash); + info_hash->key = bstr(strdup("info_hash")); + info_hash->type = string; + memcpy((info_hash->value = malloc(20)), q, (info_hash->valuelen = 20)); + binsert(a, info_hash); + binsert(b, a); + sendb(d, b, addr); + free_bencoding(b); +} + +/** + * called from compact() on response to get_peers, this function sends a get_peers to a node if it would improve the node pool of a torrent + * + * @param d [in] library handle. if NULL, get_peers is not sent and it's expected that caller will insert a new node into torrent (because one good will be removed if the potential node is closer and there's no bad node and nodelist is full) + * @param t [in] torrent + * @param a [in] address of node + * @param i [in] 20 byte id of node + * @return the position to which the new node should be written. the caller, if overwrites the pointed memory with this address, must update ->next of inserted node to the value that this address pointed to before + */ + +struct node ** potential_torrent_node (struct dht * d, struct torrent * t, const struct sockaddr_in6 * a, const unsigned char * i) { + if (!t->nodes) { + if (d) + get_peers(d, a, t->hash); + return &t->nodes; + } + int l = 0; + struct node * n = t->nodes; + struct node ** rs = NULL; // return if enough space + struct node ** farthest = &t->nodes; + struct node * prev = NULL; + while (n) { + l++; + if (node_grade(n) == bad) { + if (prev) + prev->next = n->next; + else + t->nodes = n->next; + node_free(n); + l--; + if (prev) + n = prev->next; + else + n = t->nodes; + continue; + } + int cp = memcmp(n->id, i, 20); + if (!cp) + return NULL; + if (!n->next) + rs = &n->next; + else { + int cn = memcmp(i, n->next->id, 20); + if (!cn) + return NULL; + if (cp == 1 && cn == -1) + rs = &n->next; + } + if (!closer(n->id, (*farthest)->id, t->hash)) { + if (prev) + farthest = &t->nodes; + else + farthest = &prev->next; + } + prev = n; + n = n->next; + } + if (l < K) { + if (d) + get_peers(d, a, t->hash); + return rs; + } + if (!closer(i, (*farthest)->id, t->hash)) { + if (!d) { + node_free(*farthest); + *farthest = prev; + if (d) + get_peers(d, a, t->hash); + return farthest; + } + } + return NULL; +} + +/** + * called on a response to get_peers, the node that responded is added to a list of good nodes of a torrent if it's a potential torrent node, if it's already in the list, it's stats are updated. + * + * note that torrent nodelists have no housekeeping like the routing table has with refresh(), so bad nodes are removed only in potential_torrent_node. + * + * @param t [in] torrent + * @param a [in] address of node + * @param i [in] node id + */ + +void replied_torrent_node (struct torrent * t, const struct sockaddr_in6 * a, const unsigned char * i) { + struct node * existing = t->nodes; + int r; + while (existing && (r = memcmp(existing->id, i, 20)) < 0) + existing = existing->next; + if (!r) { + existing->last_received = seconds(); + existing->unanswered = 0; + return; + } + struct node ** dst = potential_torrent_node(NULL, t, a, i); + if (!dst) + return; + struct node * n = node_init(); + memcpy(n->id, i, 20); + memcpy(&n->addr, a, sizeof n->addr); + n->next = *dst; + *dst = n; +} + +/** * parses a compact node description in either ipv4 or ipv6 from nodes or nodes6 and invoke actions. call this for every string in nodes and nodes6 array in incoming response packets. * * if the newly found node is useful for filling the K closest nodes ll of the torrent, it will be added in the LL. it may also replace an existing node if the existing node is bad or furthest away from torrent hash and this one is closer. upon insertion, the node is queried for find_node. @@ -954,46 +1296,54 @@ struct peer * add_peer (struct dht * d, struct torrent * t, struct peer * p) { */ void compact (struct dht * d, const char * value, int len, struct torrent * t) { - if (len != 4+2+20 || len != 16+2+20) { + if (len != 4+2+20 && len != 16+2+20) { L(d->log, "received packet contained an invalid compact node"); return; } - struct node * node = node_init(); - memcpy(node->addr.sin6_addr.s6_addr, "\0\0\0\0\0\0\0\0\0\0\xFF\xFF", 12); - node->addr.sin6_port = *((uint16_t *) (value + len-2)); - memcpy(node->addr.sin6_addr.s6_addr+(len == 4+2+20 ? 8 : 0), value + 20, len == 4+2+20 ? 4 : 16); - memcpy(node->id, value, 20); - potential_node(d, &node->addr, node->id); // NOTE02 at the beginning, a lot of packets will be sent, since every reply of potential_node will generate K replies. naively this would generate an exponentially increasing number of packets, in increasing powers of 8 (8**n). to prevent an absolute resource hog, this is only done when node would be useful and would contribute to the routing table - if (t) { - int i = 0; - struct node ** replaceable = NULL; - struct node ** farthest = &t->nodes; - struct node ** index = &t->nodes; - while (*index) { - i++; - if (node_grade(*index) == bad) - replaceable = index; - if (!closer((*index)->id, (*farthest)->id, t->hash)) - farthest = index; - index = &(*index)->next; - } - if (i <= K) { - node->next = t->nodes; - t->nodes = node->next; - } else if (replaceable) { - node->next = (*replaceable)->next; - node_free(*replaceable); - *replaceable = node; - find_node(d, &node->addr, t->hash); - } else if (!closer(node->id, (*farthest)->id, t->hash)) { - node->next = (*farthest)->next; - node_free(*farthest); - *farthest = node; - find_node(d, &node->addr, t->hash); + struct sockaddr_in6 addr = { + .sin6_family = AF_INET6 + }; + memcpy(addr.sin6_addr.s6_addr, "\0\0\0\0\0\0\0\0\0\0\xFF\xFF", 12); + addr.sin6_port = *((uint16_t *) (value + len-2)); + memcpy(addr.sin6_addr.s6_addr+(len == 4+2+20 ? 12 : 0), value + 20, len == 4+2+20 ? 4 : 16); +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wpointer-sign" + potential_node(d, &addr, value); // NOTE02 at the beginning, a lot of packets will be sent, since every reply of potential_node will generate K replies. naively this would generate an exponentially increasing number of packets, in increasing powers of 8 (8**n). to prevent an absolute resource hog, this is only done when node would be useful and would contribute to the routing table + if (t) + potential_torrent_node(d, t, &addr, value); +#pragma GCC diagnostic pop + /* + if (t) { + int i = 0; + struct node ** replaceable = NULL; + struct node ** farthest = &t->nodes; + struct node ** index = &t->nodes; + while (*index) { + i++; + if (node_grade(*index) == bad) + replaceable = index; + if (!closer((*index)->id, (*farthest)->id, t->hash)) + farthest = index; + index = &(*index)->next; + } + if (i <= K) { + node->next = t->nodes; + t->nodes = node->next; + } else if (replaceable) { + node->next = (*replaceable)->next; + node_free(*replaceable); + *replaceable = node; + find_node(d, &node->addr, t->hash); + } else if (!closer(node->id, (*farthest)->id, t->hash)) { + node->next = (*farthest)->next; + node_free(*farthest); + *farthest = node; + find_node(d, &node->addr, t->hash); + } else + node_free(node); } else node_free(node); - } else - node_free(node); + */ } /** @@ -1009,7 +1359,7 @@ struct bencoding * nodes (const struct dht * d, const unsigned char * id, sa_fam struct bencoding * nodes = calloc(1, sizeof *nodes); nodes->type = list; nodes->key = bstr(strdup(f == AF_INET ? "nodes" : "nodes6")); - struct bucket * bucket = f == AF_INET ? d->buckets : d->buckets6; + struct bucket * bucket = (f == AF_INET ? d->buckets : d->buckets6); struct node * found = find(id, &bucket, NULL); #define ADDRLEN(f) (f == AF_INET ? 4 : 16) if (found) { @@ -1026,9 +1376,9 @@ struct bencoding * nodes (const struct dht * d, const unsigned char * id, sa_fam struct bencoding * compact = calloc(1, sizeof *compact); compact->type = string; compact->value = malloc((compact->valuelen = 20+ADDRLEN(f)+2)); - memcpy(compact->value, found->id, 20); - memcpy(compact->value+20, found->addr.sin6_addr.s6_addr+(16-ADDRLEN(f)), ADDRLEN(f)); - memcpy(compact->value+20+ADDRLEN(f), &found->addr.sin6_port, 2); + memcpy(compact->value, node->id, 20); + memcpy(compact->value+20, node->addr.sin6_addr.s6_addr+(16-ADDRLEN(f)), ADDRLEN(f)); + memcpy(compact->value+20+ADDRLEN(f), &node->addr.sin6_port, 2); binsert(nodes, compact); node = node->next; } @@ -1048,13 +1398,12 @@ struct bencoding * nodes (const struct dht * d, const unsigned char * id, sa_fam void announce_peer (struct dht * d, const struct sockaddr_in6 * addr, struct bencoding * t, const unsigned char * h) { struct bencoding * b = calloc(1, sizeof *b); b->type = dict; - struct bencoding * t_elem = bstr(strdup("a@4_.si")); + struct bencoding * t_elem = bstr(strdup(GENERIC_T)); t_elem->key = bstr(strdup("t")); - t_elem->value[3] = 'a'; binsert(b, t_elem); struct bencoding * y = bstr(strdup("q")); - t->key = bstr(strdup("y")); - t->type = string; + y->key = bstr(strdup("y")); + y->type = string; binsert(b, y); struct bencoding * q = bstr(strdup("announce_peer")); q->key = bstr(strdup("q")); @@ -1065,7 +1414,7 @@ void announce_peer (struct dht * d, const struct sockaddr_in6 * addr, struct ben struct bencoding * id = calloc(1, sizeof *id); id->type = string; id->valuelen = 20; - id->key = bstr(strdup("key")); + id->key = bstr(strdup("id")); memcpy((id->value = malloc(20)), d->id, 20); binsert(a, id); struct bencoding * want = calloc(1, sizeof *want); // BEP-0032 @@ -1117,15 +1466,23 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { struct bencoding * b = bdecode(pkt, len, replace); struct bencoding * v = bpath(b, "v"); char * node_ver = ""; - char remote[INET_ADDRSTRLEN + INET6_ADDRSTRLEN + 7 + (v && v->type & string) ? v->valuelen : 0]; + char remote[INET_ADDRSTRLEN + INET6_ADDRSTRLEN + 64 + (v && v->type & string ? v->valuelen : 0)]; if (!inet_ntop(addr.sin6_family, &addr.sin6_addr, remote, INET6_ADDRSTRLEN+7+INET_ADDRSTRLEN)) { snprintf(remote, sizeof remote, "(inet_ntop: %s)", strerror(errno)); - sprintf(remote+strlen(remote), ":%d", ntohs(addr.sin6_port)); + sprintf(remote+strlen(remote), "/%d", ntohs(addr.sin6_port)); } if (v && v->type & string) { node_ver = v->value; sprintf(remote+strlen(remote), "-%s", node_ver); } + if (b) { + int len = b2json_length(b); + char out[len+1]; + char * end = b2json(out, b); + *end = '\0'; + assert(out+len == end); + L(d->log, "handle(%s): %s", remote, out); + } struct bencoding * y = bpath(b, "y"); char * msg_type = ""; if (y && y->type & string) @@ -1187,6 +1544,7 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { binsert(response, y); binsert(response, bclone(bpath(b, "t"))); r = calloc(1, sizeof *r); + r->key = bstr(strdup("r")); r->type = dict; id = calloc(1, sizeof *id); id->type = string; @@ -1228,6 +1586,7 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { binsert(response, y); binsert(response, bclone(bpath(b, "t"))); r = calloc(1, sizeof *r); + r->key = bstr(strdup("r")); r->type = dict; id = calloc(1, sizeof *id); id->type = string; @@ -1249,21 +1608,23 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { } #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wpointer-sign" - struct torrent * torrent = find_torrent(d, hash->value); + struct torrent * torrent = find_torrent(d, hash->value, 20); #pragma GCC diagnostic pop - struct peer * peer = torrent->peers; - struct bencoding * values = calloc(1, sizeof *values); - values->type = list; - while (peer) { // TODO implement peer preference: prefer sending peers that responded to us - if (family(peer->addr.sin6_addr.s6_addr) == family(addr.sin6_addr.s6_addr)) { // possible - struct bencoding * value = calloc(1, sizeof *value); - memcpy((value->value = malloc((value->valuelen = ADDRLEN(family(peer->addr.sin6_addr.s6_addr))+2))), peer->addr.sin6_addr.s6_addr, ADDRLEN(family(peer->addr.sin6_addr.s6_addr))); - memcpy(value->value+ADDRLEN(family(peer->addr.sin6_addr.s6_addr)), &peer->addr.sin6_port, 2); - binsert(values, value); // possible stack overflow if there are a lot of peers, see limit in bdecode() wrapper - } // TODO add a random IP address for plausible deniability - peer = peer->next; + if (torrent) { + struct peer * peer = torrent->peers; + struct bencoding * values = calloc(1, sizeof *values); + values->type = list; + while (peer) { // TODO implement peer preference: prefer sending peers that responded to us + if (family(peer->addr.sin6_addr.s6_addr) == family(addr.sin6_addr.s6_addr)) { // possible + struct bencoding * value = calloc(1, sizeof *value); + memcpy((value->value = malloc((value->valuelen = ADDRLEN(family(peer->addr.sin6_addr.s6_addr))+2))), peer->addr.sin6_addr.s6_addr, ADDRLEN(family(peer->addr.sin6_addr.s6_addr))); + memcpy(value->value+ADDRLEN(family(peer->addr.sin6_addr.s6_addr)), &peer->addr.sin6_port, 2); + binsert(values, value); // possible stack overflow if there are a lot of peers, see limit in bdecode() wrapper + } // TODO add a random IP address for plausible deniability + peer = peer->next; + } + binsert(r, values); } - binsert(r, values); struct bencoding * tok = calloc(1, sizeof *tok); tok->type = string; tok->key = bstr(strdup("token")); @@ -1305,7 +1666,7 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { torrent = calloc(1, sizeof *torrent); memcpy(torrent->hash, hash->value, 20); torrent = add_torrent(d, torrent); - peer = calloc(1, sizeof *peer); + struct peer * peer = calloc(1, sizeof *peer); memcpy(&peer->addr, &addr, sizeof addr); if (bpath(b, "a/port") && (!bpath(b, "a/implied_port") || !bpath(b, "a/implied_port")->intvalue)) peer->addr.sin6_port = htons(bpath(b, "a/port")->intvalue); @@ -1337,26 +1698,37 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { struct torrent * torrent = NULL; #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wpointer-sign" - if ((t && t->type & string && t->valuelen == 20) && memcmp(d->id, t->value, 20) && (torrent = find_torrent(d, t->value)) && torrent->type) { + if (t && t->type & string && t->valuelen == MAXT) { + if ((torrent = find_torrent(d, t->value, MAXT)) && torrent->type) { #pragma GCC diagnostic pop - bforeach (bpath(b, "r/values"), p) { - if (!(p->type & string) || (p->valuelen != 6 && p->valuelen != 18)) - break; - struct peer * peer = calloc(1, sizeof *peer); - memcpy(peer->addr.sin6_addr.s6_addr, "\0\0\0\0\0\0\0\0\0\0\xFF\xFF", 12); - peer->addr.sin6_port = *((uint16_t *) (p->value + p->valuelen-2)); - memcpy(peer->addr.sin6_addr.s6_addr+(p->valuelen == 6 ? 8 : 0), p->value, p->valuelen == 6 ? 4 : 16); - add_peer(d, torrent, peer); + if (rid && rid->type & string && rid->valuelen == 20) { +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wpointer-sign" + replied_torrent_node(torrent, &addr, rid->value); +#pragma GCC diagnostic pop + } + bforeach (bpath(b, "r/values"), p) { + if (!(p->type & string) || (p->valuelen != 6 && p->valuelen != 18)) + break; + struct peer * peer = peer_init(); + memcpy(peer->addr.sin6_addr.s6_addr, "\0\0\0\0\0\0\0\0\0\0\xFF\xFF", 12); + peer->addr.sin6_port = *((uint16_t *) (p->value + p->valuelen-2)); + memcpy(peer->addr.sin6_addr.s6_addr+(p->valuelen == 6 ? 12 : 0), p->value, p->valuelen == 6 ? 4 : 16); + add_peer(d, torrent, peer); + } + if (torrent->type & announce) + announce_peer(d, &addr, bclone(bpath(b, "r/token")), torrent->hash); } - bforeach (bpath(b, "r/nodes" /* haha subreddit */), n) - if (n->type & string) - compact(d, n->value, n->valuelen, torrent); - bforeach(bpath(b, "r/nodes6"), n) - if (n->type & string) - compact(d, n->value, n->valuelen, torrent); - if (torrent->type & announce) - announce_peer(d, &addr, bclone(bpath(b, "r/token")), torrent->hash); } + struct bencoding * nodes = bpath(b, "r/nodes"); + struct bencoding * nodes6 = bpath(b, "r/nodes6"); + // L(d->log, "r/nodes length: %zu, r/nodes6 length: %zu", nodes ? nodes->valuelen : 0, nodes6 ? nodes6->valuelen : 0); + if (nodes && nodes->type & string && !(nodes->valuelen % 26)) + for (unsigned i = 0; i < nodes->valuelen; i += 26) + compact(d, nodes->value+i, 26, torrent); + if (nodes6 && nodes6->type & string && !(nodes6->valuelen % 38)) + for (unsigned i = 0; i < nodes6->valuelen; i += 38) + compact(d, nodes6->value+i, 38, torrent); break; case 'E': case 'e': @@ -1429,7 +1801,7 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { }; memcpy(a.sin6_addr.s6_addr, "\0\0\0\0\0\0\0\0\0\0\xFF\xFF", 12); memcpy(a.sin6_addr.s6_addr+12, rr.rdata, 4); - potential_node(NULL, &a, NULL); + ping_node(d, &a); break; case 16: if (!inet_ntop(AF_INET6, rr.rdata, address, INET6_ADDRSTRLEN+INET_ADDRSTRLEN+7)) @@ -1441,7 +1813,7 @@ void handle (struct dht * d, char * pkt, int len, struct sockaddr_in6 addr) { .sin6_port = *((uint16_t *) pkt) }; memcpy(aaaa.sin6_addr.s6_addr, rr.rdata, 16); - potential_node(NULL, &a, NULL); + ping_node(d, &aaaa); break; default: // SRV if (rr.rdlength < 3*2+3) // . indicates @@ -1518,55 +1890,6 @@ int refresh (struct bucket * b) { } /** - * sends a get_peers query to a raw node - * - * @param d [in] handle - * @param a [in] address - * @param q [in] 20 byte hash we query for - */ - -void get_peers (struct dht * d, const struct sockaddr_in6 * addr, const unsigned char * q) { - struct bencoding * b = calloc(1, sizeof *b); - b->type = dict; - struct bencoding * t = calloc(1, sizeof *t); - memcpy((t->value = malloc(20)), q, (t->valuelen = 20)); - t->key = bstr(strdup("t")); - t->type = string; - binsert(b, t); - struct bencoding * y = bstr(strdup("q")); - t->key = bstr(strdup("y")); - t->type = string; - binsert(b, y); - struct bencoding * q_elem = bstr(strdup("get_peers")); - q_elem->key = bstr(strdup("q")); - q_elem->type = string; - binsert(b, q_elem); - struct bencoding * a = calloc(1, sizeof *a); - a->type = dict; - struct bencoding * id = calloc(1, sizeof *id); - id->type = string; - id->valuelen = 20; - id->key = bstr(strdup("key")); - memcpy((id->value = malloc(20)), d->id, 20); - binsert(a, id); - struct bencoding * want = calloc(1, sizeof *want); // BEP-0032 - want->key = bstr(strdup("want")); - want->type = list; - binsert(want, bstr(strdup("n4"))); - binsert(want, bstr(strdup("n6"))); - binsert(a, want); - struct bencoding * info_hash = calloc(1, sizeof *info_hash); - info_hash->key = bstr(strdup("info_hash")); - info_hash->type = string; - info_hash->valuelen = 20; - memcpy((info_hash->value = malloc(20)), q, 20); - binsert(a, info_hash); - binsert(b, a); - sendb(d, b, addr); - free_bencoding(b); -} - -/** * does periodic work for the library, called every 13 minutes * * namely, it sends UDP packets: @@ -1621,6 +1944,8 @@ void periodic (struct dht * d) { int sent = 0; while (n) { sent++; + n->unanswered++; + n->last_sent = seconds(); get_peers(d, &n->addr, t->hash); n = n->next; } @@ -1630,6 +1955,8 @@ void periodic (struct dht * d) { struct node * n = b->nodes; \ while (sent < K && n) { \ sent++; \ + n->unanswered++; \ + n->last_sent = seconds(); \ get_peers(d, &n->addr, t->hash); \ n = n->next; \ }} @@ -1642,6 +1969,8 @@ void periodic (struct dht * d) { n = b->nodes; while (sent < K && n) { sent++; + n->unanswered++; + n->last_sent = seconds(); get_peers(d, &n->addr, t->hash); n = n->next; } @@ -1668,7 +1997,6 @@ void periodic (struct dht * d) { */ void work (struct dht * d) { - L(d->log, "work()"); char packet[65536]; struct sockaddr_in6 addr; socklen_t addrlen = sizeof addr; |