source: trunk/third-party/dht/dht.c @ 10914

Last change on this file since 10914 was 10914, checked in by charles, 12 years ago

(trunk third-party/dht) #3311 "mingw build of Transmission" -- use jch's upstream win32 portability fixes

File size: 82.0 KB
Line 
1/*
2Copyright (c) 2010 by Juliusz Chroboczek
3
4Permission is hereby granted, free of charge, to any person obtaining a copy
5of this software and associated documentation files (the "Software"), to deal
6in the Software without restriction, including without limitation the rights
7to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8copies of the Software, and to permit persons to whom the Software is
9furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20THE SOFTWARE.
21*/
22
23/* Please, please, please.
24
25   You are welcome to integrate this code in your favourite Bittorrent
26   client.  Please remember, however, that it is meant to be usable by
27   others, including myself.  This means no C++, no relicensing, and no
28   gratuitious changes to the coding style.  And please send back any
29   improvements to the author. */
30
31/* For memmem. */
32#define _GNU_SOURCE
33
34#include <stdio.h>
35#include <stdlib.h>
36#include <errno.h>
37#include <string.h>
38#include <stdarg.h>
39#include <unistd.h>
40#include <fcntl.h>
41#include <sys/time.h>
42
43#ifndef WIN32
44#include <arpa/inet.h>
45#include <sys/types.h>
46#include <sys/socket.h>
47#include <netinet/in.h>
48#else
49#include <w32api.h>
50#define WINVER WindowsXP
51#include <ws2tcpip.h>
52#endif
53
54#include "dht.h"
55
56#ifndef HAVE_MEMMEM
57#ifdef __GLIBC__
58#define HAVE_MEMMEM
59#endif
60#endif
61
62#ifndef MSG_CONFIRM
63#define MSG_CONFIRM 0
64#endif
65
66#ifdef WIN32
67
68#define EAFNOSUPPORT WSAEAFNOSUPPORT
69static int
70set_nonblocking(int fd, int nonblocking)
71{
72    int rc;
73
74    unsigned long mode = !!nonblocking;
75    rc = ioctlsocket(fd, FIONBIO, &mode);
76    if(rc != 0)
77        errno = WSAGetLastError();
78    return (rc == 0 ? 0 : -1);
79}
80
81static int
82random(void)
83{
84    return rand();
85}
86extern const char *inet_ntop(int, const void *, char *, socklen_t);
87
88#else
89
90static int
91set_nonblocking(int fd, int nonblocking)
92{
93    int rc;
94    rc = fcntl(fd, F_GETFL, 0);
95    if(rc < 0)
96        return -1;
97
98    rc = fcntl(fd, F_SETFL, nonblocking?(rc | O_NONBLOCK):(rc & ~O_NONBLOCK));
99    if(rc < 0)
100        return -1;
101
102    return 0;
103}
104
105#endif
106
107/* We set sin_family to 0 to mark unused slots. */
108#if AF_INET == 0 || AF_INET6 == 0
109#error You lose
110#endif
111
112#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
113/* nothing */
114#elif defined(__GNUC__)
115#define inline __inline
116#if  (__GNUC__ >= 3)
117#define restrict __restrict
118#else
119#define restrict /**/
120#endif
121#else
122#define inline /**/
123#define restrict /**/
124#endif
125
126#define MAX(x, y) ((x) >= (y) ? (x) : (y))
127#define MIN(x, y) ((x) <= (y) ? (x) : (y))
128
129struct node {
130    unsigned char id[20];
131    struct sockaddr_storage ss;
132    int sslen;
133    time_t time;                /* time of last message received */
134    time_t reply_time;          /* time of last correct reply received */
135    time_t pinged_time;         /* time of last request */
136    int pinged;                 /* how many requests we sent since last reply */
137    struct node *next;
138};
139
140struct bucket {
141    int af;
142    unsigned char first[20];
143    int count;                  /* number of nodes */
144    int time;                   /* time of last reply in this bucket */
145    struct node *nodes;
146    struct sockaddr_storage cached;  /* the address of a likely candidate */
147    int cachedlen;
148    struct bucket *next;
149};
150
151struct search_node {
152    unsigned char id[20];
153    struct sockaddr_storage ss;
154    int sslen;
155    time_t request_time;        /* the time of the last unanswered request */
156    time_t reply_time;          /* the time of the last reply */
157    int pinged;
158    unsigned char token[40];
159    int token_len;
160    int replied;                /* whether we have received a reply */
161    int acked;                  /* whether they acked our announcement */
162};
163
164/* When performing a search, we search for up to SEARCH_NODES closest nodes
165   to the destination, and use the additional ones to backtrack if any of
166   the target 8 turn out to be dead. */
167#define SEARCH_NODES 14
168
169struct search {
170    unsigned short tid;
171    int af;
172    time_t step_time;           /* the time of the last search_step */
173    unsigned char id[20];
174    unsigned short port;        /* 0 for pure searches */
175    int done;
176    struct search_node nodes[SEARCH_NODES];
177    int numnodes;
178    struct search *next;
179};
180
181struct peer {
182    time_t time;
183    unsigned char ip[16];
184    unsigned short len;
185    unsigned short port;
186};
187
188/* The maximum number of peers we store for a given hash. */
189#ifndef DHT_MAX_PEERS
190#define DHT_MAX_PEERS 2048
191#endif
192
193/* The maximum number of hashes we're willing to track. */
194#ifndef DHT_MAX_HASHES
195#define DHT_MAX_HASHES 16384
196#endif
197
198/* The maximum number of searches we keep data about. */
199#ifndef DHT_MAX_SEARCHES
200#define DHT_MAX_SEARCHES 1024
201#endif
202
203/* The time after which we consider a search to be expirable. */
204#ifndef DHT_SEARCH_EXPIRE_TIME
205#define DHT_SEARCH_EXPIRE_TIME (62 * 60)
206#endif
207
208struct storage {
209    unsigned char id[20];
210    int numpeers, maxpeers;
211    struct peer *peers;
212    struct storage *next;
213};
214
215static int send_ping(struct sockaddr *sa, int salen,
216                     const unsigned char *tid, int tid_len);
217static int send_pong(struct sockaddr *sa, int salen,
218                     const unsigned char *tid, int tid_len);
219static int send_find_node(struct sockaddr *sa, int salen,
220                          const unsigned char *tid, int tid_len,
221                          const unsigned char *target, int want, int confirm);
222static int send_nodes_peers(struct sockaddr *sa, int salen,
223                            const unsigned char *tid, int tid_len,
224                            const unsigned char *nodes, int nodes_len,
225                            const unsigned char *nodes6, int nodes6_len,
226                            int af, struct storage *st,
227                            const unsigned char *token, int token_len);
228static int send_closest_nodes(struct sockaddr *sa, int salen,
229                              const unsigned char *tid, int tid_len,
230                              const unsigned char *id, int want,
231                              int af, struct storage *st,
232                              const unsigned char *token, int token_len);
233static int send_get_peers(struct sockaddr *sa, int salen,
234                          unsigned char *tid, int tid_len,
235                          unsigned char *infohash, int want, int confirm);
236static int send_announce_peer(struct sockaddr *sa, int salen,
237                              unsigned char *tid, int tid_len,
238                              unsigned char *infohas, unsigned short port,
239                              unsigned char *token, int token_len, int confirm);
240static int send_peer_announced(struct sockaddr *sa, int salen,
241                               unsigned char *tid, int tid_len);
242static int send_error(struct sockaddr *sa, int salen,
243                      unsigned char *tid, int tid_len,
244                      int code, const char *message);
245
246#define ERROR 0
247#define REPLY 1
248#define PING 2
249#define FIND_NODE 3
250#define GET_PEERS 4
251#define ANNOUNCE_PEER 5
252
253#define WANT4 1
254#define WANT6 2
255
256static int parse_message(const unsigned char *buf, int buflen,
257                         unsigned char *tid_return, int *tid_len,
258                         unsigned char *id_return,
259                         unsigned char *info_hash_return,
260                         unsigned char *target_return,
261                         unsigned short *port_return,
262                         unsigned char *token_return, int *token_len,
263                         unsigned char *nodes_return, int *nodes_len,
264                         unsigned char *nodes6_return, int *nodes6_len,
265                         unsigned char *values_return, int *values_len,
266                         unsigned char *values6_return, int *values6_len,
267                         int *want_return);
268
269static const unsigned char zeroes[20] = {0};
270static const unsigned char ones[20] = {
271    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
272    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
273    0xFF, 0xFF, 0xFF, 0xFF
274};
275static const unsigned char v4prefix[16] = {
276    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0
277};
278
279static int dht_socket = -1;
280static int dht_socket6 = -1;
281
282static time_t search_time;
283static time_t confirm_nodes_time;
284static time_t rotate_secrets_time;
285
286static unsigned char myid[20];
287static int have_v = 0;
288static unsigned char my_v[9];
289static unsigned char secret[8];
290static unsigned char oldsecret[8];
291
292static struct bucket *buckets = NULL;
293static struct bucket *buckets6 = NULL;
294static struct storage *storage;
295static int numstorage;
296
297static struct search *searches = NULL;
298static int numsearches;
299static unsigned short search_id;
300
301/* The maximum number of nodes that we snub.  There is probably little
302   reason to increase this value. */
303#ifndef DHT_MAX_BLACKLISTED
304#define DHT_MAX_BLACKLISTED 10
305#endif
306static struct sockaddr_storage blacklist[DHT_MAX_BLACKLISTED];
307int next_blacklisted;
308
309static struct timeval now;
310static time_t mybucket_grow_time, mybucket6_grow_time;
311static time_t expire_stuff_time;
312
313#define MAX_TOKEN_BUCKET_TOKENS 40
314static time_t token_bucket_time;
315static int token_bucket_tokens;
316
317FILE *dht_debug = NULL;
318
319#ifdef __GNUC__
320    __attribute__ ((format (printf, 1, 2)))
321#endif
322static void
323debugf(const char *format, ...)
324{
325    va_list args;
326    va_start(args, format);
327    if(dht_debug)
328        vfprintf(dht_debug, format, args);
329    va_end(args);
330    fflush(dht_debug);
331}
332
333static void
334debug_printable(const unsigned char *buf, int buflen)
335{
336    int i;
337    if(dht_debug) {
338        for(i = 0; i < buflen; i++)
339            putc(buf[i] >= 32 && buf[i] <= 126 ? buf[i] : '.', dht_debug);
340    }
341}
342
343static void
344print_hex(FILE *f, const unsigned char *buf, int buflen)
345{
346    int i;
347    for(i = 0; i < buflen; i++)
348        fprintf(f, "%02x", buf[i]);
349}
350
351static int
352is_martian(struct sockaddr *sa)
353{
354    switch(sa->sa_family) {
355    case AF_INET: {
356        struct sockaddr_in *sin = (struct sockaddr_in*)sa;
357        const unsigned char *address = (const unsigned char*)&sin->sin_addr;
358        return sin->sin_port == 0 ||
359            (address[0] == 0) ||
360            (address[0] == 127) ||
361            ((address[0] & 0xE0) == 0xE0);
362    }
363    case AF_INET6: {
364        struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)sa;
365        const unsigned char *address = (const unsigned char*)&sin6->sin6_addr;
366        return sin6->sin6_port == 0 ||
367            (address[0] == 0xFF) ||
368            (address[0] == 0xFE && (address[1] & 0xC0) == 0x80) ||
369            (memcmp(address, zeroes, 15) == 0 &&
370             (address[15] == 0 || address[15] == 1)) ||
371            (memcmp(address, v4prefix, 12) == 0);
372    }
373
374    default:
375        return 0;
376    }
377}
378
379/* Forget about the ``XOR-metric''.  An id is just a path from the
380   root of the tree, so bits are numbered from the start. */
381
382static inline int
383id_cmp(const unsigned char *restrict id1, const unsigned char *restrict id2)
384{
385    /* Memcmp is guaranteed to perform an unsigned comparison. */
386    return memcmp(id1, id2, 20);
387}
388
389/* Find the lowest 1 bit in an id. */
390static int
391lowbit(const unsigned char *id)
392{
393    int i, j;
394    for(i = 19; i >= 0; i--)
395        if(id[i] != 0)
396            break;
397
398    if(i < 0)
399        return -1;
400
401    for(j = 7; j >= 0; j--)
402        if((id[i] & (0x80 >> j)) != 0)
403            break;
404
405    return 8 * i + j;
406}
407
408/* Find how many bits two ids have in common. */
409static int
410common_bits(const unsigned char *id1, const unsigned char *id2)
411{
412    int i, j;
413    unsigned char xor;
414    for(i = 0; i < 20; i++) {
415        if(id1[i] != id2[i])
416            break;
417    }
418
419    if(i == 20)
420        return 160;
421
422    xor = id1[i] ^ id2[i];
423
424    j = 0;
425    while((xor & 0x80) == 0) {
426        xor <<= 1;
427        j++;
428    }
429
430    return 8 * i + j;
431}
432
433/* Determine whether id1 or id2 is closer to ref */
434static int
435xorcmp(const unsigned char *id1, const unsigned char *id2,
436       const unsigned char *ref)
437{
438    int i;
439    for(i = 0; i < 20; i++) {
440        unsigned char xor1, xor2;
441        if(id1[i] == id2[i])
442            continue;
443        xor1 = id1[i] ^ ref[i];
444        xor2 = id2[i] ^ ref[i];
445        if(xor1 < xor2)
446            return -1;
447        else
448            return 1;
449    }
450    return 0;
451}
452
453/* We keep buckets in a sorted linked list.  A bucket b ranges from
454   b->first inclusive up to b->next->first exclusive. */
455static int
456in_bucket(const unsigned char *id, struct bucket *b)
457{
458    return id_cmp(b->first, id) <= 0 &&
459        (b->next == NULL || id_cmp(id, b->next->first) < 0);
460}
461
462static struct bucket *
463find_bucket(unsigned const char *id, int af)
464{
465    struct bucket *b = af == AF_INET ? buckets : buckets6;
466
467    if(b == NULL)
468        return NULL;
469
470    while(1) {
471        if(b->next == NULL)
472            return b;
473        if(id_cmp(id, b->next->first) < 0)
474            return b;
475        b = b->next;
476    }
477}
478
479static struct bucket *
480previous_bucket(struct bucket *b)
481{
482    struct bucket *p = b->af == AF_INET ? buckets : buckets6;
483
484    if(b == p)
485        return NULL;
486
487    while(1) {
488        if(p->next == NULL)
489            return NULL;
490        if(p->next == b)
491            return p;
492        p = p->next;
493    }
494}
495
496/* Every bucket contains an unordered list of nodes. */
497static struct node *
498find_node(const unsigned char *id, int af)
499{
500    struct bucket *b = find_bucket(id, af);
501    struct node *n;
502
503    if(b == NULL)
504        return NULL;
505
506    n = b->nodes;
507    while(n) {
508        if(id_cmp(n->id, id) == 0)
509            return n;
510        n = n->next;
511    }
512    return NULL;
513}
514
515/* Return a random node in a bucket. */
516static struct node *
517random_node(struct bucket *b)
518{
519    struct node *n;
520    int nn;
521
522    if(b->count == 0)
523        return NULL;
524
525    nn = random() % b->count;
526    n = b->nodes;
527    while(nn > 0 && n) {
528        n = n->next;
529        nn--;
530    }
531    return n;
532}
533
534/* Return the middle id of a bucket. */
535static int
536bucket_middle(struct bucket *b, unsigned char *id_return)
537{
538    int bit1 = lowbit(b->first);
539    int bit2 = b->next ? lowbit(b->next->first) : -1;
540    int bit = MAX(bit1, bit2) + 1;
541
542    if(bit >= 160)
543        return -1;
544
545    memcpy(id_return, b->first, 20);
546    id_return[bit / 8] |= (0x80 >> (bit % 8));
547    return 1;
548}
549
550/* Return a random id within a bucket. */
551static int
552bucket_random(struct bucket *b, unsigned char *id_return)
553{
554    int bit1 = lowbit(b->first);
555    int bit2 = b->next ? lowbit(b->next->first) : -1;
556    int bit = MAX(bit1, bit2) + 1;
557    int i;
558
559    if(bit >= 160) {
560        memcpy(id_return, b->first, 20);
561        return 1;
562    }
563
564    memcpy(id_return, b->first, bit / 8);
565    id_return[bit / 8] = b->first[bit / 8] & (0xFF00 >> (bit % 8));
566    id_return[bit / 8] |= random() & 0xFF >> (bit % 8);
567    for(i = bit / 8 + 1; i < 20; i++)
568        id_return[i] = random() & 0xFF;
569    return 1;
570}
571
572/* Insert a new node into a bucket. */
573static struct node *
574insert_node(struct node *node)
575{
576    struct bucket *b = find_bucket(node->id, node->ss.ss_family);
577
578    if(b == NULL)
579        return NULL;
580
581    node->next = b->nodes;
582    b->nodes = node;
583    b->count++;
584    return node;
585}
586
587/* This is our definition of a known-good node. */
588static int
589node_good(struct node *node)
590{
591    return
592        node->pinged <= 2 &&
593        node->reply_time >= now.tv_sec - 7200 &&
594        node->time >= now.tv_sec - 900;
595}
596
597/* Our transaction-ids are 4-bytes long, with the first two bytes identi-
598   fying the kind of request, and the remaining two a sequence number in
599   host order. */
600
601static void
602make_tid(unsigned char *tid_return, const char *prefix, unsigned short seqno)
603{
604    tid_return[0] = prefix[0] & 0xFF;
605    tid_return[1] = prefix[1] & 0xFF;
606    memcpy(tid_return + 2, &seqno, 2);
607}
608
609static int
610tid_match(const unsigned char *tid, const char *prefix,
611          unsigned short *seqno_return)
612{
613    if(tid[0] == (prefix[0] & 0xFF) && tid[1] == (prefix[1] & 0xFF)) {
614        if(seqno_return)
615            memcpy(seqno_return, tid + 2, 2);
616        return 1;
617    } else
618        return 0;
619}
620
621/* Every bucket caches the address of a likely node.  Ping it. */
622static int
623send_cached_ping(struct bucket *b)
624{
625    unsigned char tid[4];
626    int rc;
627    /* We set family to 0 when there's no cached node. */
628    if(b->cached.ss_family == 0)
629        return 0;
630
631    debugf("Sending ping to cached node.\n");
632    make_tid(tid, "pn", 0);
633    rc = send_ping((struct sockaddr*)&b->cached, b->cachedlen, tid, 4);
634    b->cached.ss_family = 0;
635    b->cachedlen = 0;
636    return rc;
637}
638
639/* Split a bucket into two equal parts. */
640static struct bucket *
641split_bucket(struct bucket *b)
642{
643    struct bucket *new;
644    struct node *nodes;
645    int rc;
646    unsigned char new_id[20];
647
648    rc = bucket_middle(b, new_id);
649    if(rc < 0)
650        return NULL;
651
652    new = calloc(1, sizeof(struct bucket));
653    if(new == NULL)
654        return NULL;
655
656    new->af = b->af;
657
658    send_cached_ping(b);
659
660    memcpy(new->first, new_id, 20);
661    new->time = b->time;
662
663    nodes = b->nodes;
664    b->nodes = NULL;
665    b->count = 0;
666    new->next = b->next;
667    b->next = new;
668    while(nodes) {
669        struct node *n;
670        n = nodes;
671        nodes = nodes->next;
672        insert_node(n);
673    }
674    return b;
675}
676
677/* Called whenever we send a request to a node. */
678static void
679pinged(struct node *n, struct bucket *b)
680{
681    n->pinged++;
682    n->pinged_time = now.tv_sec;
683    if(n->pinged >= 3)
684        send_cached_ping(b ? b : find_bucket(n->id, n->ss.ss_family));
685}
686
687/* We just learnt about a node, not necessarily a new one.  Confirm is 1 if
688   the node sent a message, 2 if it sent us a reply. */
689static struct node *
690new_node(const unsigned char *id, struct sockaddr *sa, int salen, int confirm)
691{
692    struct bucket *b = find_bucket(id, sa->sa_family);
693    struct node *n;
694    int mybucket, split;
695
696    if(b == NULL)
697        return NULL;
698
699    if(id_cmp(id, myid) == 0)
700        return NULL;
701
702    if(is_martian(sa))
703        return NULL;
704
705    mybucket = in_bucket(myid, b);
706
707    if(confirm == 2)
708        b->time = now.tv_sec;
709
710    n = b->nodes;
711    while(n) {
712        if(id_cmp(n->id, id) == 0) {
713            if(confirm || n->time < now.tv_sec - 15 * 60) {
714                /* Known node.  Update stuff. */
715                memcpy((struct sockaddr*)&n->ss, sa, salen);
716                if(confirm)
717                    n->time = now.tv_sec;
718                if(confirm >= 2) {
719                    n->reply_time = now.tv_sec;
720                    n->pinged = 0;
721                    n->pinged_time = 0;
722                }
723            }
724            return n;
725        }
726        n = n->next;
727    }
728
729    /* New node. */
730
731    if(mybucket) {
732        if(sa->sa_family == AF_INET)
733            mybucket_grow_time = now.tv_sec;
734        else
735            mybucket6_grow_time = now.tv_sec;
736    }
737
738    /* First, try to get rid of a known-bad node. */
739    n = b->nodes;
740    while(n) {
741        if(n->pinged >= 3 && n->pinged_time < now.tv_sec - 15) {
742            memcpy(n->id, id, 20);
743            memcpy((struct sockaddr*)&n->ss, sa, salen);
744            n->time = confirm ? now.tv_sec : 0;
745            n->reply_time = confirm >= 2 ? now.tv_sec : 0;
746            n->pinged_time = 0;
747            n->pinged = 0;
748            return n;
749        }
750        n = n->next;
751    }
752
753    if(b->count >= 8) {
754        /* Bucket full.  Ping a dubious node */
755        int dubious = 0;
756        n = b->nodes;
757        while(n) {
758            /* Pick the first dubious node that we haven't pinged in the
759               last 15 seconds.  This gives nodes the time to reply, but
760               tends to concentrate on the same nodes, so that we get rid
761               of bad nodes fast. */
762            if(!node_good(n)) {
763                dubious = 1;
764                if(n->pinged_time < now.tv_sec - 15) {
765                    unsigned char tid[4];
766                    debugf("Sending ping to dubious node.\n");
767                    make_tid(tid, "pn", 0);
768                    send_ping((struct sockaddr*)&n->ss, n->sslen,
769                              tid, 4);
770                    n->pinged++;
771                    n->pinged_time = now.tv_sec;
772                    break;
773                }
774            }
775            n = n->next;
776        }
777
778        split = 0;
779        if(mybucket) {
780            if(!dubious)
781                split = 1;
782            /* If there's only one bucket, split eagerly.  This is
783               incorrect unless there's more than 8 nodes in the DHT. */
784            else if(b->af == AF_INET && buckets->next == NULL)
785                split = 1;
786            else if(b->af == AF_INET6 && buckets6->next == NULL)
787                split = 1;
788        }
789
790        if(split) {
791            debugf("Splitting.\n");
792            b = split_bucket(b);
793            return new_node(id, sa, salen, confirm);
794        }
795
796        /* No space for this node.  Cache it away for later. */
797        if(confirm || b->cached.ss_family == 0) {
798            memcpy(&b->cached, sa, salen);
799            b->cachedlen = salen;
800        }
801
802        return NULL;
803    }
804
805    /* Create a new node. */
806    n = calloc(1, sizeof(struct node));
807    if(n == NULL)
808        return NULL;
809    memcpy(n->id, id, 20);
810    memcpy(&n->ss, sa, salen);
811    n->sslen = salen;
812    n->time = confirm ? now.tv_sec : 0;
813    n->reply_time = confirm >= 2 ? now.tv_sec : 0;
814    n->next = b->nodes;
815    b->nodes = n;
816    b->count++;
817    return n;
818}
819
820/* Called periodically to purge known-bad nodes.  Note that we're very
821   conservative here: broken nodes in the table don't do much harm, we'll
822   recover as soon as we find better ones. */
823static int
824expire_buckets(struct bucket *b)
825{
826    while(b) {
827        struct node *n, *p;
828        int changed = 0;
829
830        while(b->nodes && b->nodes->pinged >= 4) {
831            n = b->nodes;
832            b->nodes = n->next;
833            b->count--;
834            changed = 1;
835            free(n);
836        }
837
838        p = b->nodes;
839        while(p) {
840            while(p->next && p->next->pinged >= 4) {
841                n = p->next;
842                p->next = n->next;
843                b->count--;
844                changed = 1;
845                free(n);
846            }
847            p = p->next;
848        }
849
850        if(changed)
851            send_cached_ping(b);
852
853        b = b->next;
854    }
855    expire_stuff_time = now.tv_sec + 120 + random() % 240;
856    return 1;
857}
858
859/* While a search is in progress, we don't necessarily keep the nodes being
860   walked in the main bucket table.  A search in progress is identified by
861   a unique transaction id, a short (and hence small enough to fit in the
862   transaction id of the protocol packets). */
863
864static struct search *
865find_search(unsigned short tid, int af)
866{
867    struct search *sr = searches;
868    while(sr) {
869        if(sr->tid == tid && sr->af == af)
870            return sr;
871        sr = sr->next;
872    }
873    return NULL;
874}
875
876/* A search contains a list of nodes, sorted by decreasing distance to the
877   target.  We just got a new candidate, insert it at the right spot or
878   discard it. */
879
880static int
881insert_search_node(unsigned char *id,
882                   struct sockaddr *sa, int salen,
883                   struct search *sr, int replied,
884                   unsigned char *token, int token_len)
885{
886    struct search_node *n;
887    int i, j;
888
889    if(sa->sa_family != sr->af) {
890        debugf("Attempted to insert node in the wrong family.\n");
891        return 0;
892    }
893
894    for(i = 0; i < sr->numnodes; i++) {
895        if(id_cmp(id, sr->nodes[i].id) == 0) {
896            n = &sr->nodes[i];
897            goto found;
898        }
899        if(xorcmp(id, sr->nodes[i].id, sr->id) < 0)
900            break;
901    }
902
903    if(i == SEARCH_NODES)
904        return 0;
905
906    if(sr->numnodes < SEARCH_NODES)
907        sr->numnodes++;
908
909    for(j = sr->numnodes - 1; j > i; j--) {
910        sr->nodes[j] = sr->nodes[j - 1];
911    }
912
913    n = &sr->nodes[i];
914
915    memset(n, 0, sizeof(struct search_node));
916    memcpy(n->id, id, 20);
917
918found:
919    memcpy(&n->ss, sa, salen);
920    n->sslen = salen;
921
922    if(replied) {
923        n->replied = 1;
924        n->reply_time = now.tv_sec;
925        n->request_time = 0;
926        n->pinged = 0;
927    }
928    if(token) {
929        if(token_len >= 40) {
930            debugf("Eek!  Overlong token.\n");
931        } else {
932            memcpy(n->token, token, token_len);
933            n->token_len = token_len;
934        }
935    }
936
937    return 1;
938}
939
940static void
941flush_search_node(struct search_node *n, struct search *sr)
942{
943    int i = n - sr->nodes, j;
944    for(j = i; j < sr->numnodes - 1; j++)
945        sr->nodes[j] = sr->nodes[j + 1];
946    sr->numnodes--;
947}
948
949static void
950expire_searches(void)
951{
952    struct search *sr = searches, *previous = NULL;
953
954    while(sr) {
955        struct search *next = sr->next;
956        if(sr->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME) {
957            if(previous)
958                previous->next = next;
959            else
960                searches = next;
961            free(sr);
962            numsearches--;
963        } else {
964            previous = sr;
965        }
966        sr = next;
967    }
968}
969
970/* This must always return 0 or 1, never -1, not even on failure (see below). */
971static int
972search_send_get_peers(struct search *sr, struct search_node *n)
973{
974    struct node *node;
975    unsigned char tid[4];
976
977    if(n == NULL) {
978        int i;
979        for(i = 0; i < sr->numnodes; i++) {
980            if(sr->nodes[i].pinged < 3 && !sr->nodes[i].replied &&
981               sr->nodes[i].request_time < now.tv_sec - 15)
982                n = &sr->nodes[i];
983        }
984    }
985
986    if(!n || n->pinged >= 3 || n->replied ||
987       n->request_time >= now.tv_sec - 15)
988        return 0;
989
990    debugf("Sending get_peers.\n");
991    make_tid(tid, "gp", sr->tid);
992    send_get_peers((struct sockaddr*)&n->ss, n->sslen, tid, 4, sr->id, -1,
993                   n->reply_time >= now.tv_sec - 15);
994    n->pinged++;
995    n->request_time = now.tv_sec;
996    /* If the node happens to be in our main routing table, mark it
997       as pinged. */
998    node = find_node(n->id, n->ss.ss_family);
999    if(node) pinged(node, NULL);
1000    return 1;
1001}
1002
1003/* When a search is in progress, we periodically call search_step to send
1004   further requests. */
1005static void
1006search_step(struct search *sr, dht_callback *callback, void *closure)
1007{
1008    int i, j;
1009    int all_done = 1;
1010
1011    /* Check if the first 8 live nodes have replied. */
1012    j = 0;
1013    for(i = 0; i < sr->numnodes && j < 8; i++) {
1014        struct search_node *n = &sr->nodes[i];
1015        if(n->pinged >= 3)
1016            continue;
1017        if(!n->replied) {
1018            all_done = 0;
1019            break;
1020        }
1021        j++;
1022    }
1023
1024    if(all_done) {
1025        if(sr->port == 0) {
1026            goto done;
1027        } else {
1028            int all_acked = 1;
1029            j = 0;
1030            for(i = 0; i < sr->numnodes && j < 8; i++) {
1031                struct search_node *n = &sr->nodes[i];
1032                struct node *node;
1033                unsigned char tid[4];
1034                if(n->pinged >= 3)
1035                    continue;
1036                /* A proposed extension to the protocol consists in
1037                   omitting the token when storage tables are full.  While
1038                   I don't think this makes a lot of sense -- just sending
1039                   a positive reply is just as good --, let's deal with it. */
1040                if(n->token_len == 0)
1041                    n->acked = 1;
1042                if(!n->acked) {
1043                    all_acked = 0;
1044                    debugf("Sending announce_peer.\n");
1045                    make_tid(tid, "ap", sr->tid);
1046                    send_announce_peer((struct sockaddr*)&n->ss,
1047                                       sizeof(struct sockaddr_storage),
1048                                       tid, 4, sr->id, sr->port,
1049                                       n->token, n->token_len,
1050                                       n->reply_time >= now.tv_sec - 15);
1051                    n->pinged++;
1052                    n->request_time = now.tv_sec;
1053                    node = find_node(n->id, n->ss.ss_family);
1054                    if(node) pinged(node, NULL);
1055                }
1056                j++;
1057            }
1058            if(all_acked)
1059                goto done;
1060        }
1061        sr->step_time = now.tv_sec;
1062        return;
1063    }
1064
1065    if(sr->step_time + 15 >= now.tv_sec)
1066        return;
1067
1068    j = 0;
1069    for(i = 0; i < sr->numnodes; i++) {
1070        j += search_send_get_peers(sr, &sr->nodes[i]);
1071        if(j >= 3)
1072            break;
1073    }
1074    sr->step_time = now.tv_sec;
1075    return;
1076
1077 done:
1078    sr->done = 1;
1079    if(callback)
1080        (*callback)(closure,
1081                    sr->af == AF_INET ?
1082                    DHT_EVENT_SEARCH_DONE : DHT_EVENT_SEARCH_DONE6,
1083                    sr->id, NULL, 0);
1084    sr->step_time = now.tv_sec;
1085}
1086
1087static struct search *
1088new_search(void)
1089{
1090    struct search *sr, *oldest = NULL;
1091
1092    /* Find the oldest done search */
1093    sr = searches;
1094    while(sr) {
1095        if(sr->done &&
1096           (oldest == NULL || oldest->step_time > sr->step_time))
1097            oldest = sr;
1098        sr = sr->next;
1099    }
1100
1101    /* The oldest slot is expired. */
1102    if(oldest && oldest->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME)
1103        return oldest;
1104
1105    /* Allocate a new slot. */
1106    if(numsearches < DHT_MAX_SEARCHES) {
1107        sr = calloc(1, sizeof(struct search));
1108        if(sr != NULL) {
1109            sr->next = searches;
1110            searches = sr;
1111            numsearches++;
1112            return sr;
1113        }
1114    }
1115
1116    /* Oh, well, never mind.  Reuse the oldest slot. */
1117    return oldest;
1118}
1119
1120/* Insert the contents of a bucket into a search structure. */
1121static void
1122insert_search_bucket(struct bucket *b, struct search *sr)
1123{
1124    struct node *n;
1125    n = b->nodes;
1126    while(n) {
1127        insert_search_node(n->id, (struct sockaddr*)&n->ss, n->sslen,
1128                           sr, 0, NULL, 0);
1129        n = n->next;
1130    }
1131}
1132
1133/* Start a search.  If port is non-zero, perform an announce when the
1134   search is complete. */
1135int
1136dht_search(const unsigned char *id, int port, int af,
1137           dht_callback *callback, void *closure)
1138{
1139    struct search *sr;
1140    struct bucket *b = find_bucket(id, af);
1141
1142    if(b == NULL) {
1143        errno = EAFNOSUPPORT;
1144        return -1;
1145    }
1146
1147    sr = searches;
1148    while(sr) {
1149        if(sr->af == af && id_cmp(sr->id, id) == 0)
1150            break;
1151        sr = sr->next;
1152    }
1153
1154    if(sr) {
1155        /* We're reusing data from an old search.  Reusing the same tid
1156           means that we can merge replies for both searches. */
1157        int i;
1158        sr->done = 0;
1159    again:
1160        for(i = 0; i < sr->numnodes; i++) {
1161            struct search_node *n;
1162            n = &sr->nodes[i];
1163            /* Discard any doubtful nodes. */
1164            if(n->pinged >= 3 || n->reply_time < now.tv_sec - 7200) {
1165                flush_search_node(n, sr);
1166                goto again;
1167            }
1168            n->pinged = 0;
1169            n->token_len = 0;
1170            n->replied = 0;
1171            n->acked = 0;
1172        }
1173    } else {
1174        sr = new_search();
1175        if(sr == NULL) {
1176            errno = ENOSPC;
1177            return -1;
1178        }
1179        sr->af = af;
1180        sr->tid = search_id++;
1181        sr->step_time = 0;
1182        memcpy(sr->id, id, 20);
1183        sr->done = 0;
1184        sr->numnodes = 0;
1185    }
1186
1187    sr->port = port;
1188
1189    insert_search_bucket(b, sr);
1190
1191    if(sr->numnodes < SEARCH_NODES) {
1192        struct bucket *p = previous_bucket(b);
1193        if(b->next)
1194            insert_search_bucket(b->next, sr);
1195        if(p)
1196            insert_search_bucket(p, sr);
1197    }
1198    if(sr->numnodes < SEARCH_NODES)
1199        insert_search_bucket(find_bucket(myid, af), sr);
1200
1201    search_step(sr, callback, closure);
1202    search_time = now.tv_sec;
1203    return 1;
1204}
1205
1206/* A struct storage stores all the stored peer addresses for a given info
1207   hash. */
1208
1209static struct storage *
1210find_storage(const unsigned char *id)
1211{
1212    struct storage *st = storage;
1213
1214    while(st) {
1215        if(id_cmp(id, st->id) == 0)
1216            break;
1217        st = st->next;
1218    }
1219    return st;
1220}
1221
1222static int
1223storage_store(const unsigned char *id, struct sockaddr *sa)
1224{
1225    int i, len;
1226    struct storage *st = storage;
1227    unsigned char *ip;
1228    unsigned short port;
1229
1230    st = find_storage(id);
1231
1232    if(st == NULL) {
1233        if(numstorage >= DHT_MAX_HASHES)
1234            return -1;
1235        st = calloc(1, sizeof(struct storage));
1236        if(st == NULL) return -1;
1237        memcpy(st->id, id, 20);
1238        st->next = storage;
1239        storage = st;
1240        numstorage++;
1241    }
1242
1243    if(sa->sa_family == AF_INET) {
1244        struct sockaddr_in *sin = (struct sockaddr_in*)sa;
1245        ip = (unsigned char*)&sin->sin_addr;
1246        len = 4;
1247        port = ntohs(sin->sin_port);
1248    } else if(sa->sa_family == AF_INET6) {
1249        struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)sa;
1250        ip = (unsigned char*)&sin6->sin6_addr;
1251        len = 16;
1252        port = ntohs(sin6->sin6_port);
1253    }
1254
1255    for(i = 0; i < st->numpeers; i++) {
1256        if(st->peers[i].port == port && st->peers[i].len == len &&
1257           memcmp(st->peers[i].ip, ip, len) == 0)
1258            break;
1259    }
1260
1261    if(i < st->numpeers) {
1262        /* Already there, only need to refresh */
1263        st->peers[i].time = now.tv_sec;
1264        return 0;
1265    } else {
1266        struct peer *p;
1267        if(i >= st->maxpeers) {
1268            /* Need to expand the array. */
1269            struct peer *new_peers;
1270            int n;
1271            if(st->maxpeers >= DHT_MAX_PEERS)
1272                return 0;
1273            n = st->maxpeers == 0 ? 2 : 2 * st->maxpeers;
1274            n = MIN(n, DHT_MAX_PEERS);
1275            new_peers = realloc(st->peers, n * sizeof(struct peer));
1276            if(new_peers == NULL)
1277                return -1;
1278            st->peers = new_peers;
1279            st->maxpeers = n;
1280        }
1281        p = &st->peers[st->numpeers++];
1282        p->time = now.tv_sec;
1283        p->len = len;
1284        memcpy(p->ip, ip, len);
1285        p->port = port;
1286        return 1;
1287    }
1288}
1289
1290static int
1291expire_storage(void)
1292{
1293    struct storage *st = storage, *previous = NULL;
1294    while(st) {
1295        int i = 0;
1296        while(i < st->numpeers) {
1297            if(st->peers[i].time < now.tv_sec - 32 * 60) {
1298                if(i != st->numpeers - 1)
1299                    st->peers[i] = st->peers[st->numpeers - 1];
1300                st->numpeers--;
1301            } else {
1302                i++;
1303            }
1304        }
1305
1306        if(st->numpeers == 0) {
1307            free(st->peers);
1308            if(previous)
1309                previous->next = st->next;
1310            else
1311                storage = st->next;
1312            free(st);
1313            if(previous)
1314                st = previous->next;
1315            else
1316                st = storage;
1317            numstorage--;
1318            if(numstorage < 0) {
1319                debugf("Eek... numstorage became negative.\n");
1320                numstorage = 0;
1321            }
1322        } else {
1323            previous = st;
1324            st = st->next;
1325        }
1326    }
1327    return 1;
1328}
1329
1330/* We've just found out that a node is buggy. */
1331static void
1332broken_node(const unsigned char *id, struct sockaddr *sa, int salen)
1333{
1334    int i;
1335
1336    debugf("Blacklisting broken node.\n");
1337
1338    if(id) {
1339        struct node *n;
1340        struct search *sr;
1341        /* Make the node easy to discard. */
1342        n = find_node(id, sa->sa_family);
1343        if(n) {
1344            n->pinged = 3;
1345            pinged(n, NULL);
1346        }
1347        /* Discard it from any searches in progress. */
1348        sr = searches;
1349        while(sr) {
1350            for(i = 0; i < sr->numnodes; i++)
1351                if(id_cmp(sr->nodes[i].id, id) == 0)
1352                    flush_search_node(&sr->nodes[i], sr);
1353            sr = sr->next;
1354        }
1355    }
1356    /* And make sure we don't hear from it again. */
1357    memcpy(&blacklist[next_blacklisted], sa, salen);
1358    next_blacklisted = (next_blacklisted + 1) % DHT_MAX_BLACKLISTED;
1359}
1360
1361static int
1362rotate_secrets(void)
1363{
1364    int rc;
1365
1366    rotate_secrets_time = now.tv_sec + 900 + random() % 1800;
1367
1368    memcpy(oldsecret, secret, sizeof(secret));
1369    rc = dht_random_bytes(secret, sizeof(secret));
1370
1371    if(rc < 0)
1372        return -1;
1373
1374    return 1;
1375}
1376
1377#ifndef TOKEN_SIZE
1378#define TOKEN_SIZE 8
1379#endif
1380
1381static void
1382make_token(struct sockaddr *sa, int old, unsigned char *token_return)
1383{
1384    void *ip;
1385    int iplen;
1386    unsigned short port;
1387
1388    if(sa->sa_family == AF_INET) {
1389        struct sockaddr_in *sin = (struct sockaddr_in*)sa;
1390        ip = &sin->sin_addr;
1391        iplen = 4;
1392        port = htons(sin->sin_port);
1393    } else if(sa->sa_family == AF_INET6) {
1394        struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)sa;
1395        ip = &sin6->sin6_addr;
1396        iplen = 16;
1397        port = htons(sin6->sin6_port);
1398    } else {
1399        abort();
1400    }
1401
1402    dht_hash(token_return, TOKEN_SIZE,
1403             old ? oldsecret : secret, sizeof(secret),
1404             ip, iplen, (unsigned char*)&port, 2);
1405}
1406static int
1407token_match(unsigned char *token, int token_len, struct sockaddr *sa)
1408{
1409    unsigned char t[TOKEN_SIZE];
1410    if(token_len != TOKEN_SIZE)
1411        return 0;
1412    make_token(sa, 0, t);
1413    if(memcmp(t, token, TOKEN_SIZE) == 0)
1414        return 1;
1415    make_token(sa, 1, t);
1416    if(memcmp(t, token, TOKEN_SIZE) == 0)
1417        return 1;
1418    return 0;
1419}
1420
1421int
1422dht_nodes(int af, int *good_return, int *dubious_return, int *cached_return,
1423          int *incoming_return)
1424{
1425    int good = 0, dubious = 0, cached = 0, incoming = 0;
1426    struct bucket *b = af == AF_INET ? buckets : buckets6;
1427
1428    while(b) {
1429        struct node *n = b->nodes;
1430        while(n) {
1431            if(node_good(n)) {
1432                good++;
1433                if(n->time > n->reply_time)
1434                    incoming++;
1435            } else {
1436                dubious++;
1437            }
1438            n = n->next;
1439        }
1440        if(b->cached.ss_family > 0)
1441            cached++;
1442        b = b->next;
1443    }
1444    if(good_return)
1445        *good_return = good;
1446    if(dubious_return)
1447        *dubious_return = dubious;
1448    if(cached_return)
1449        *cached_return = cached;
1450    if(incoming_return)
1451        *incoming_return = incoming;
1452    return good + dubious;
1453}
1454
1455static void
1456dump_bucket(FILE *f, struct bucket *b)
1457{
1458    struct node *n = b->nodes;
1459    fprintf(f, "Bucket ");
1460    print_hex(f, b->first, 20);
1461    fprintf(f, " count %d age %d%s%s:\n",
1462            b->count, (int)(now.tv_sec - b->time),
1463            in_bucket(myid, b) ? " (mine)" : "",
1464            b->cached.ss_family ? " (cached)" : "");
1465    while(n) {
1466        char buf[512];
1467        unsigned short port;
1468        fprintf(f, "    Node ");
1469        print_hex(f, n->id, 20);
1470        if(n->ss.ss_family == AF_INET) {
1471            struct sockaddr_in *sin = (struct sockaddr_in*)&n->ss;
1472            inet_ntop(AF_INET, &sin->sin_addr, buf, 512);
1473            port = ntohs(sin->sin_port);
1474        } else if(n->ss.ss_family == AF_INET6) {
1475            struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)&n->ss;
1476            inet_ntop(AF_INET6, &sin6->sin6_addr, buf, 512);
1477            port = ntohs(sin6->sin6_port);
1478        } else {
1479            snprintf(buf, 512, "unknown(%d)", n->ss.ss_family);
1480            port = 0;
1481        }
1482
1483        if(n->ss.ss_family == AF_INET6)
1484            fprintf(f, " [%s]:%d ", buf, port);
1485        else
1486            fprintf(f, " %s:%d ", buf, port);
1487        if(n->time != n->reply_time)
1488            fprintf(f, "age %ld, %ld",
1489                    (long)(now.tv_sec - n->time),
1490                    (long)(now.tv_sec - n->reply_time));
1491        else
1492            fprintf(f, "age %ld", (long)(now.tv_sec - n->time));
1493        if(n->pinged)
1494            fprintf(f, " (%d)", n->pinged);
1495        if(node_good(n))
1496            fprintf(f, " (good)");
1497        fprintf(f, "\n");
1498        n = n->next;
1499    }
1500
1501}
1502
1503void
1504dht_dump_tables(FILE *f)
1505{
1506    int i;
1507    struct bucket *b;
1508    struct storage *st = storage;
1509    struct search *sr = searches;
1510
1511    fprintf(f, "My id ");
1512    print_hex(f, myid, 20);
1513    fprintf(f, "\n");
1514
1515    b = buckets;
1516    while(b) {
1517        dump_bucket(f, b);
1518        b = b->next;
1519    }
1520
1521    fprintf(f, "\n");
1522
1523    b = buckets6;
1524    while(b) {
1525        dump_bucket(f, b);
1526        b = b->next;
1527    }
1528
1529    while(sr) {
1530        fprintf(f, "\nSearch%s id ", sr->af == AF_INET6 ? " (IPv6)" : "");
1531        print_hex(f, sr->id, 20);
1532        fprintf(f, " age %d%s\n", (int)(now.tv_sec - sr->step_time),
1533               sr->done ? " (done)" : "");
1534        for(i = 0; i < sr->numnodes; i++) {
1535            struct search_node *n = &sr->nodes[i];
1536            fprintf(f, "Node %d id ", i);
1537            print_hex(f, n->id, 20);
1538            fprintf(f, " bits %d age ", common_bits(sr->id, n->id));
1539            if(n->request_time)
1540                fprintf(f, "%d, ", (int)(now.tv_sec - n->request_time));
1541            fprintf(f, "%d", (int)(now.tv_sec - n->reply_time));
1542            if(n->pinged)
1543                fprintf(f, " (%d)", n->pinged);
1544            fprintf(f, "%s%s.\n",
1545                    find_node(n->id, AF_INET) ? " (known)" : "",
1546                    n->replied ? " (replied)" : "");
1547        }
1548        sr = sr->next;
1549    }
1550
1551    while(st) {
1552        fprintf(f, "\nStorage ");
1553        print_hex(f, st->id, 20);
1554        fprintf(f, " %d/%d nodes:", st->numpeers, st->maxpeers);
1555        for(i = 0; i < st->numpeers; i++) {
1556            char buf[100];
1557            if(st->peers[i].len == 4) {
1558                inet_ntop(AF_INET, st->peers[i].ip, buf, 100);
1559            } else if(st->peers[i].len == 16) {
1560                buf[0] = '[';
1561                inet_ntop(AF_INET6, st->peers[i].ip, buf + 1, 98);
1562                strcat(buf, "]");
1563            } else {
1564                strcpy(buf, "???");
1565            }
1566            fprintf(f, " %s:%u (%ld)",
1567                    buf, st->peers[i].port,
1568                    (long)(now.tv_sec - st->peers[i].time));
1569        }
1570        st = st->next;
1571    }
1572
1573    fprintf(f, "\n\n");
1574    fflush(f);
1575}
1576
1577int
1578dht_init(int s, int s6, const unsigned char *id, const unsigned char *v)
1579{
1580    int rc;
1581
1582    if(dht_socket >= 0 || dht_socket6 >= 0 || buckets || buckets6) {
1583        errno = EBUSY;
1584        return -1;
1585    }
1586
1587    searches = NULL;
1588    numsearches = 0;
1589
1590    storage = NULL;
1591    numstorage = 0;
1592
1593    if(s >= 0) {
1594        buckets = calloc(sizeof(struct bucket), 1);
1595        if(buckets == NULL)
1596            return -1;
1597        buckets->af = AF_INET;
1598
1599        rc = set_nonblocking(s, 1);
1600        if(rc < 0)
1601            goto fail;
1602    }
1603
1604    if(s6 >= 0) {
1605        buckets6 = calloc(sizeof(struct bucket), 1);
1606        if(buckets6 == NULL)
1607            return -1;
1608        buckets6->af = AF_INET6;
1609
1610        rc = set_nonblocking(s6, 1);
1611        if(rc < 0)
1612            goto fail;
1613    }
1614
1615    memcpy(myid, id, 20);
1616    if(v) {
1617        memcpy(my_v, "1:v4:", 5);
1618        memcpy(my_v + 5, v, 4);
1619        have_v = 1;
1620    } else {
1621        have_v = 0;
1622    }
1623
1624    gettimeofday(&now, NULL);
1625
1626    mybucket_grow_time = now.tv_sec;
1627    mybucket6_grow_time = now.tv_sec;
1628    confirm_nodes_time = now.tv_sec + random() % 3;
1629
1630    search_id = random() & 0xFFFF;
1631    search_time = 0;
1632
1633    next_blacklisted = 0;
1634
1635    token_bucket_time = now.tv_sec;
1636    token_bucket_tokens = MAX_TOKEN_BUCKET_TOKENS;
1637
1638    memset(secret, 0, sizeof(secret));
1639    rc = rotate_secrets();
1640    if(rc < 0)
1641        goto fail;
1642
1643    dht_socket = s;
1644    dht_socket6 = s6;
1645
1646    expire_buckets(buckets);
1647    expire_buckets(buckets6);
1648
1649    return 1;
1650
1651 fail:
1652    free(buckets);
1653    buckets = NULL;
1654    return -1;
1655}
1656
1657int
1658dht_uninit(int dofree)
1659{
1660    if(dht_socket < 0) {
1661        errno = EINVAL;
1662        return -1;
1663    }
1664
1665    if(!dofree)
1666        return 1;
1667
1668    while(buckets) {
1669        struct bucket *b = buckets;
1670        buckets = b->next;
1671        while(b->nodes) {
1672            struct node *n = b->nodes;
1673            b->nodes = n->next;
1674            free(n);
1675        }
1676        free(b);
1677    }
1678
1679    while(storage) {
1680        struct storage *st = storage;
1681        storage = storage->next;
1682        free(st->peers);
1683        free(st);
1684    }
1685
1686    while(searches) {
1687        struct search *sr = searches;
1688        searches = searches->next;
1689        free(sr);
1690    }
1691
1692    return 1;
1693}
1694
1695/* Rate control for requests we receive. */
1696
1697static int
1698token_bucket(void)
1699{
1700    if(token_bucket_tokens == 0) {
1701        token_bucket_tokens = MIN(MAX_TOKEN_BUCKET_TOKENS,
1702                                  4 * (now.tv_sec - token_bucket_time));
1703        token_bucket_time = now.tv_sec;
1704    }
1705
1706    if(token_bucket_tokens == 0)
1707        return 0;
1708
1709    token_bucket_tokens--;
1710    return 1;
1711}
1712
1713static int
1714neighbourhood_maintenance(int af)
1715{
1716    unsigned char id[20];
1717    struct bucket *b = find_bucket(myid, af);
1718    struct bucket *q;
1719    struct node *n;
1720
1721    if(b == NULL)
1722        return 0;
1723
1724    memcpy(id, myid, 20);
1725    id[19] = random() & 0xFF;
1726    q = b;
1727    if(q->next && (q->count == 0 || (random() & 7) == 0))
1728        q = b->next;
1729    if(q->count == 0 || (random() & 7) == 0) {
1730        struct bucket *r;
1731        r = previous_bucket(b);
1732        if(r && r->count > 0)
1733            q = r;
1734    }
1735
1736    if(q) {
1737        /* Since our node-id is the same in both DHTs, it's probably
1738           profitable to query both families. */
1739        int want = dht_socket >= 0 && dht_socket6 >= 0 ? (WANT4 | WANT6) : -1;
1740        n = random_node(q);
1741        if(n) {
1742            unsigned char tid[4];
1743            debugf("Sending find_node for%s neighborhood maintenance.\n",
1744                   af == AF_INET6 ? " IPv6" : "");
1745            make_tid(tid, "fn", 0);
1746            send_find_node((struct sockaddr*)&n->ss, n->sslen,
1747                           tid, 4, id, want,
1748                           n->reply_time >= now.tv_sec - 15);
1749            pinged(n, q);
1750        }
1751        return 1;
1752    }
1753    return 0;
1754}
1755
1756static int
1757bucket_maintenance(int af)
1758{
1759    struct bucket *b;
1760
1761    b = af == AF_INET ? buckets : buckets6;
1762
1763    while(b) {
1764        struct bucket *q;
1765        if(b->time < now.tv_sec - 600) {
1766            /* This bucket hasn't seen any positive confirmation for a long
1767               time.  Pick a random id in this bucket's range, and send
1768               a request to a random node. */
1769            unsigned char id[20];
1770            struct node *n;
1771            int rc;
1772
1773            rc = bucket_random(b, id);
1774            if(rc < 0)
1775                memcpy(id, b->first, 20);
1776
1777            q = b;
1778            /* If the bucket is empty, we try to fill it from a neighbour.
1779               We also sometimes do it gratuitiously to recover from
1780               buckets full of broken nodes. */
1781            if(q->next && (q->count == 0 || (random() & 7) == 0))
1782                q = b->next;
1783            if(q->count == 0 || (random() & 7) == 0) {
1784                struct bucket *r;
1785                r = previous_bucket(b);
1786                if(r && r->count > 0)
1787                    q = r;
1788            }
1789
1790            if(q) {
1791                n = random_node(q);
1792                if(n) {
1793                    unsigned char tid[4];
1794                    int want = -1;
1795
1796                    if(dht_socket >= 0 && dht_socket6 >= 0) {
1797                        struct bucket *otherbucket;
1798                        otherbucket =
1799                            find_bucket(id, af == AF_INET ? AF_INET6 : AF_INET);
1800                        if(otherbucket && otherbucket->count < 8)
1801                            /* The corresponding bucket in the other family
1802                               is emptyish -- querying both is useful. */
1803                            want = WANT4 | WANT6;
1804                        else if(random() % 37 == 0)
1805                            /* Most of the time, this just adds overhead.
1806                               However, it might help stitch back one of
1807                               the DHTs after a network collapse, so query
1808                               both, but only very occasionally. */
1809                            want = WANT4 | WANT6;
1810                    }
1811
1812                    debugf("Sending find_node for%s bucket maintenance.\n",
1813                           af == AF_INET6 ? " IPv6" : "");
1814                    make_tid(tid, "fn", 0);
1815                    send_find_node((struct sockaddr*)&n->ss, n->sslen,
1816                                   tid, 4, id, want,
1817                                   n->reply_time >= now.tv_sec - 15);
1818                    pinged(n, q);
1819                    /* In order to avoid sending queries back-to-back,
1820                       give up for now and reschedule us soon. */
1821                    return 1;
1822                }
1823            }
1824        }
1825        b = b->next;
1826    }
1827    return 0;
1828}
1829
1830int
1831dht_periodic(int available, time_t *tosleep,
1832             dht_callback *callback, void *closure)
1833{
1834    int i;
1835
1836    gettimeofday(&now, NULL);
1837
1838    if(available) {
1839        int rc, message;
1840        unsigned char tid[16], id[20], info_hash[20], target[20];
1841        unsigned char buf[1536], nodes[256], nodes6[1024], token[128];
1842        int tid_len = 16, token_len = 128;
1843        int nodes_len = 256, nodes6_len = 1024;
1844        unsigned short port;
1845        unsigned char values[2048], values6[2048];
1846        int values_len = 2048, values6_len = 2048;
1847        int want, want4, want6;
1848        struct sockaddr_storage source_storage;
1849        struct sockaddr *source = (struct sockaddr*)&source_storage;
1850        socklen_t sourcelen = sizeof(source_storage);
1851        unsigned short ttid;
1852
1853        rc = -1;
1854        if(dht_socket >= 0) {
1855            rc = recvfrom(dht_socket, buf, 1536, 0, source, &sourcelen);
1856            if(rc < 0 && errno != EAGAIN) {
1857                    return rc;
1858            }
1859        }
1860        if(dht_socket6 >= 0 && rc < 0) {
1861            rc = recvfrom(dht_socket6, buf, 1536, 0,
1862                          source, &sourcelen);
1863            if(rc < 0 && errno != EAGAIN) {
1864                    return rc;
1865            }
1866        }
1867
1868        if(rc < 0 || sourcelen > sizeof(struct sockaddr_storage))
1869            goto dontread;
1870
1871        if(is_martian(source))
1872            goto dontread;
1873
1874        for(i = 0; i < DHT_MAX_BLACKLISTED; i++) {
1875            if(memcmp(&blacklist[i], source, sourcelen) == 0) {
1876                debugf("Received packet from blacklisted node.\n");
1877                goto dontread;
1878            }
1879        }
1880
1881        /* There's a bug in parse_message -- it will happily overflow the
1882           buffer if it's not NUL-terminated.  For now, put a NUL at the
1883           end of buffers. */
1884
1885        if(rc < 1536) {
1886            buf[rc] = '\0';
1887        } else {
1888            debugf("Overlong message.\n");
1889            goto dontread;
1890        }
1891
1892        message = parse_message(buf, rc, tid, &tid_len, id, info_hash,
1893                                target, &port, token, &token_len,
1894                                nodes, &nodes_len, nodes6, &nodes6_len,
1895                                values, &values_len, values6, &values6_len,
1896                                &want);
1897
1898        if(message < 0 || message == ERROR || id_cmp(id, zeroes) == 0) {
1899            debugf("Unparseable message: ");
1900            debug_printable(buf, rc);
1901            debugf("\n");
1902            goto dontread;
1903        }
1904
1905        if(id_cmp(id, myid) == 0) {
1906            debugf("Received message from self.\n");
1907            goto dontread;
1908        }
1909
1910        if(message > REPLY) {
1911            /* Rate limit requests. */
1912            if(!token_bucket()) {
1913                debugf("Dropping request due to rate limiting.\n");
1914                goto dontread;
1915            }
1916        }
1917
1918        if(want > 0) {
1919            want4 = (want & WANT4);
1920            want6 = (want & WANT6);
1921        } else {
1922            want4 = source->sa_family == AF_INET;
1923            want6 = source->sa_family == AF_INET6;
1924        }
1925
1926        switch(message) {
1927        case REPLY:
1928            if(tid_len != 4) {
1929                debugf("Broken node truncates transaction ids: ");
1930                debug_printable(buf, rc);
1931                debugf("\n");
1932                /* This is really annoying, as it means that we will
1933                   time-out all our searches that go through this node.
1934                   Kill it. */
1935                broken_node(id, source, sourcelen);
1936                goto dontread;
1937            }
1938            if(tid_match(tid, "pn", NULL)) {
1939                debugf("Pong!\n");
1940                new_node(id, source, sourcelen, 2);
1941            } else if(tid_match(tid, "fn", NULL) ||
1942                      tid_match(tid, "gp", NULL)) {
1943                int gp = 0;
1944                struct search *sr = NULL;
1945                if(tid_match(tid, "gp", &ttid)) {
1946                    gp = 1;
1947                    sr = find_search(ttid, source->sa_family);
1948                }
1949                debugf("Nodes found (%d+%d)%s!\n", nodes_len/26, nodes6_len/38,
1950                       gp ? " for get_peers" : "");
1951                if(nodes_len % 26 != 0 || nodes6_len % 38 != 0) {
1952                    debugf("Unexpected length for node info!\n");
1953                    broken_node(id, source, sourcelen);
1954                } else if(gp && sr == NULL) {
1955                    debugf("Unknown search!\n");
1956                    new_node(id, source, sourcelen, 1);
1957                } else {
1958                    int i;
1959                    new_node(id, source, sourcelen, 2);
1960                    for(i = 0; i < nodes_len / 26; i++) {
1961                        unsigned char *ni = nodes + i * 26;
1962                        struct sockaddr_in sin;
1963                        if(id_cmp(ni, myid) == 0)
1964                            continue;
1965                        memset(&sin, 0, sizeof(sin));
1966                        sin.sin_family = AF_INET;
1967                        memcpy(&sin.sin_addr, ni + 20, 4);
1968                        memcpy(&sin.sin_port, ni + 24, 2);
1969                        new_node(ni, (struct sockaddr*)&sin, sizeof(sin), 0);
1970                        if(sr && sr->af == AF_INET) {
1971                            insert_search_node(ni,
1972                                               (struct sockaddr*)&sin,
1973                                               sizeof(sin),
1974                                               sr, 0, NULL, 0);
1975                        }
1976                    }
1977                    for(i = 0; i < nodes6_len / 38; i++) {
1978                        unsigned char *ni = nodes6 + i * 38;
1979                        struct sockaddr_in6 sin6;
1980                        if(id_cmp(ni, myid) == 0)
1981                            continue;
1982                        memset(&sin6, 0, sizeof(sin6));
1983                        sin6.sin6_family = AF_INET6;
1984                        memcpy(&sin6.sin6_addr, ni + 20, 16);
1985                        memcpy(&sin6.sin6_port, ni + 36, 2);
1986                        new_node(ni, (struct sockaddr*)&sin6, sizeof(sin6), 0);
1987                        if(sr && sr->af == AF_INET6) {
1988                            insert_search_node(ni,
1989                                               (struct sockaddr*)&sin6,
1990                                               sizeof(sin6),
1991                                               sr, 0, NULL, 0);
1992                        }
1993                    }
1994                    if(sr)
1995                        /* Since we received a reply, the number of
1996                           requests in flight has decreased.  Let's push
1997                           another request. */
1998                        search_send_get_peers(sr, NULL);
1999                }
2000                if(sr) {
2001                    insert_search_node(id, source, sourcelen, sr,
2002                                       1, token, token_len);
2003                    if(values_len > 0 || values6_len > 0) {
2004                        debugf("Got values (%d+%d)!\n",
2005                               values_len / 6, values6_len / 18);
2006                        if(callback) {
2007                            if(values_len > 0)
2008                                (*callback)(closure, DHT_EVENT_VALUES, sr->id,
2009                                            (void*)values, values_len);
2010
2011                            if(values6_len > 0)
2012                                (*callback)(closure, DHT_EVENT_VALUES6, sr->id,
2013                                            (void*)values6, values6_len);
2014                        }
2015                    }
2016                }
2017            } else if(tid_match(tid, "ap", &ttid)) {
2018                struct search *sr;
2019                debugf("Got reply to announce_peer.\n");
2020                sr = find_search(ttid, source->sa_family);
2021                if(!sr) {
2022                    debugf("Unknown search!\n");
2023                    new_node(id, source, sourcelen, 1);
2024                } else {
2025                    int i;
2026                    new_node(id, source, sourcelen, 2);
2027                    for(i = 0; i < sr->numnodes; i++)
2028                        if(id_cmp(sr->nodes[i].id, id) == 0) {
2029                            sr->nodes[i].request_time = 0;
2030                            sr->nodes[i].reply_time = now.tv_sec;
2031                            sr->nodes[i].acked = 1;
2032                            sr->nodes[i].pinged = 0;
2033                            break;
2034                        }
2035                    /* See comment for gp above. */
2036                    search_send_get_peers(sr, NULL);
2037                }
2038            } else {
2039                debugf("Unexpected reply: ");
2040                debug_printable(buf, rc);
2041                debugf("\n");
2042            }
2043            break;
2044        case PING:
2045            debugf("Ping (%d)!\n", tid_len);
2046            new_node(id, source, sourcelen, 1);
2047            debugf("Sending pong.\n");
2048            send_pong(source, sourcelen, tid, tid_len);
2049            break;
2050        case FIND_NODE:
2051            debugf("Find node!\n");
2052            new_node(id, source, sourcelen, 1);
2053            debugf("Sending closest nodes (%d).\n", want);
2054            send_closest_nodes(source, sourcelen,
2055                               tid, tid_len, target, want,
2056                               0, NULL, NULL, 0);
2057            break;
2058        case GET_PEERS:
2059            debugf("Get_peers!\n");
2060            new_node(id, source, sourcelen, 1);
2061            if(id_cmp(info_hash, zeroes) == 0) {
2062                debugf("Eek!  Got get_peers with no info_hash.\n");
2063                send_error(source, sourcelen, tid, tid_len,
2064                           203, "Get_peers with no info_hash");
2065                break;
2066            } else {
2067                struct storage *st = find_storage(info_hash);
2068                unsigned char token[TOKEN_SIZE];
2069                make_token(source, 0, token);
2070                if(st && st->numpeers > 0) {
2071                     debugf("Sending found%s peers.\n",
2072                            source->sa_family == AF_INET6 ? " IPv6" : "");
2073                     send_closest_nodes(source, sourcelen,
2074                                        tid, tid_len,
2075                                        info_hash, want,
2076                                        source->sa_family, st,
2077                                        token, TOKEN_SIZE);
2078                } else {
2079                    debugf("Sending nodes for get_peers.\n");
2080                    send_closest_nodes(source, sourcelen,
2081                                       tid, tid_len, info_hash, want,
2082                                       0, NULL, token, TOKEN_SIZE);
2083                }
2084            }
2085            break;
2086        case ANNOUNCE_PEER:
2087            debugf("Announce peer!\n");
2088            new_node(id, source, sourcelen, 1);
2089            if(id_cmp(info_hash, zeroes) == 0) {
2090                debugf("Announce_peer with no info_hash.\n");
2091                send_error(source, sourcelen, tid, tid_len,
2092                           203, "Announce_peer with no info_hash");
2093                break;
2094            }
2095            if(!token_match(token, token_len, source)) {
2096                debugf("Incorrect token for announce_peer.\n");
2097                send_error(source, sourcelen, tid, tid_len,
2098                           203, "Announce_peer with wrong token");
2099                break;
2100            }
2101            if(port == 0) {
2102                debugf("Announce_peer with forbidden port %d.\n", port);
2103                send_error(source, sourcelen, tid, tid_len,
2104                           203, "Announce_peer with forbidden port number");
2105                break;
2106            }
2107            storage_store(info_hash, source);
2108            /* Note that if storage_store failed, we lie to the requestor.
2109               This is to prevent them from backtracking, and hence
2110               polluting the DHT. */
2111            debugf("Sending peer announced.\n");
2112            send_peer_announced(source, sourcelen, tid, tid_len);
2113        }
2114    }
2115
2116 dontread:
2117    if(now.tv_sec >= rotate_secrets_time)
2118        rotate_secrets();
2119
2120    if(now.tv_sec >= expire_stuff_time) {
2121        expire_buckets(buckets);
2122        expire_buckets(buckets6);
2123        expire_storage();
2124        expire_searches();
2125    }
2126
2127    if(search_time > 0 && now.tv_sec >= search_time) {
2128        struct search *sr;
2129        sr = searches;
2130        while(sr) {
2131            if(!sr->done && sr->step_time + 5 <= now.tv_sec) {
2132                search_step(sr, callback, closure);
2133            }
2134            sr = sr->next;
2135        }
2136
2137        search_time = 0;
2138
2139        sr = searches;
2140        while(sr) {
2141            if(!sr->done) {
2142                time_t tm = sr->step_time + 15 + random() % 10;
2143                if(search_time == 0 || search_time > tm)
2144                    search_time = tm;
2145            }
2146            sr = sr->next;
2147        }
2148    }
2149
2150    if(now.tv_sec >= confirm_nodes_time) {
2151        int soon = 0;
2152
2153        soon |= bucket_maintenance(AF_INET);
2154        soon |= bucket_maintenance(AF_INET6);
2155
2156        if(!soon) {
2157            if(mybucket_grow_time >= now.tv_sec - 150)
2158                soon |= neighbourhood_maintenance(AF_INET);
2159            if(mybucket6_grow_time >= now.tv_sec - 150)
2160                soon |= neighbourhood_maintenance(AF_INET6);
2161        }
2162
2163        /* In order to maintain all buckets' age within 600 seconds, worst
2164           case is roughly 27 seconds, assuming the table is 22 bits deep.
2165           We want to keep a margin for neighborhood maintenance, so keep
2166           this within 25 seconds. */
2167        if(soon)
2168            confirm_nodes_time = now.tv_sec + 5 + random() % 20;
2169        else
2170            confirm_nodes_time = now.tv_sec + 60 + random() % 120;
2171    }
2172
2173    if(confirm_nodes_time > now.tv_sec)
2174        *tosleep = confirm_nodes_time - now.tv_sec;
2175    else
2176        *tosleep = 0;
2177
2178    if(search_time > 0) {
2179        if(search_time <= now.tv_sec)
2180            *tosleep = 0;
2181        else if(*tosleep > search_time - now.tv_sec)
2182            *tosleep = search_time - now.tv_sec;
2183    }
2184
2185    return 1;
2186}
2187
2188int
2189dht_get_nodes(struct sockaddr_in *sin, int *num,
2190              struct sockaddr_in6 *sin6, int *num6)
2191{
2192    int i, j;
2193    struct bucket *b;
2194    struct node *n;
2195
2196    i = 0;
2197
2198    /* For restoring to work without discarding too many nodes, the list
2199       must start with the contents of our bucket. */
2200    b = find_bucket(myid, AF_INET);
2201    if(b == NULL)
2202        goto no_ipv4;
2203
2204    n = b->nodes;
2205    while(n && i < *num) {
2206        if(node_good(n)) {
2207            sin[i] = *(struct sockaddr_in*)&n->ss;
2208            i++;
2209        }
2210        n = n->next;
2211    }
2212
2213    b = buckets;
2214    while(b && i < *num) {
2215        if(!in_bucket(myid, b)) {
2216            n = b->nodes;
2217            while(n && i < *num) {
2218                if(node_good(n)) {
2219                    sin[i] = *(struct sockaddr_in*)&n->ss;
2220                    i++;
2221                }
2222                n = n->next;
2223            }
2224        }
2225        b = b->next;
2226    }
2227
2228 no_ipv4:
2229
2230    j = 0;
2231
2232    b = find_bucket(myid, AF_INET6);
2233    if(b == NULL)
2234        goto no_ipv6;
2235
2236    n = b->nodes;
2237    while(n && j < *num6) {
2238        if(node_good(n)) {
2239            sin6[j] = *(struct sockaddr_in6*)&n->ss;
2240            j++;
2241        }
2242        n = n->next;
2243    }
2244
2245    b = buckets6;
2246    while(b && j < *num6) {
2247        if(!in_bucket(myid, b)) {
2248            n = b->nodes;
2249            while(n && j < *num6) {
2250                if(node_good(n)) {
2251                    sin6[j] = *(struct sockaddr_in6*)&n->ss;
2252                    j++;
2253                }
2254                n = n->next;
2255            }
2256        }
2257        b = b->next;
2258    }
2259
2260 no_ipv6:
2261
2262    *num = i;
2263    *num6 = j;
2264    return i + j;
2265}
2266
2267int
2268dht_insert_node(const unsigned char *id, struct sockaddr *sa, int salen)
2269{
2270    struct node *n;
2271
2272    if(sa->sa_family != AF_INET) {
2273        errno = EAFNOSUPPORT;
2274        return -1;
2275    }
2276
2277    n = new_node(id, (struct sockaddr*)sa, salen, 0);
2278    return !!n;
2279}
2280
2281int
2282dht_ping_node(struct sockaddr *sa, int salen)
2283{
2284    unsigned char tid[4];
2285
2286    debugf("Sending ping.\n");
2287    make_tid(tid, "pn", 0);
2288    return send_ping(sa, salen, tid, 4);
2289}
2290
2291/* We could use a proper bencoding printer and parser, but the format of
2292   DHT messages is fairly stylised, so this seemed simpler. */
2293
2294#define CHECK(offset, delta, size)                      \
2295    if(delta < 0 || offset + delta > size) goto fail
2296
2297#define INC(offset, delta, size)                        \
2298    CHECK(offset, delta, size);                         \
2299    offset += delta
2300
2301#define COPY(buf, offset, src, delta, size)             \
2302    CHECK(offset, delta, size);                         \
2303    memcpy(buf + offset, src, delta);                   \
2304    offset += delta;
2305
2306#define ADD_V(buf, offset, size)                        \
2307    if(have_v) {                                        \
2308        COPY(buf, offset, my_v, sizeof(my_v), size);    \
2309    }
2310
2311static int
2312dht_send(const void *buf, size_t len, int flags,
2313         const struct sockaddr *sa, int salen)
2314{
2315    int s;
2316
2317    if(salen == 0)
2318        abort();
2319
2320    if(sa->sa_family == AF_INET)
2321        s = dht_socket;
2322    else if(sa->sa_family == AF_INET6)
2323        s = dht_socket6;
2324    else
2325        s = -1;
2326
2327    if(s < 0) {
2328        errno = EAFNOSUPPORT;
2329        return -1;
2330    }
2331
2332    return sendto(s, buf, len, flags, sa, salen);
2333}
2334
2335int
2336send_ping(struct sockaddr *sa, int salen,
2337          const unsigned char *tid, int tid_len)
2338{
2339    char buf[512];
2340    int i = 0, rc;
2341    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
2342    COPY(buf, i, myid, 20, 512);
2343    rc = snprintf(buf + i, 512 - i, "e1:q4:ping1:t%d:", tid_len);
2344    INC(i, rc, 512);
2345    COPY(buf, i, tid, tid_len, 512);
2346    ADD_V(buf, i, 512);
2347    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
2348    return dht_send(buf, i, 0, sa, salen);
2349
2350 fail:
2351    errno = ENOSPC;
2352    return -1;
2353}
2354
2355int
2356send_pong(struct sockaddr *sa, int salen,
2357          const unsigned char *tid, int tid_len)
2358{
2359    char buf[512];
2360    int i = 0, rc;
2361    rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512);
2362    COPY(buf, i, myid, 20, 512);
2363    rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
2364    COPY(buf, i, tid, tid_len, 512);
2365    ADD_V(buf, i, 512);
2366    rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512);
2367    return dht_send(buf, i, 0, sa, salen);
2368
2369 fail:
2370    errno = ENOSPC;
2371    return -1;
2372}
2373
2374int
2375send_find_node(struct sockaddr *sa, int salen,
2376               const unsigned char *tid, int tid_len,
2377               const unsigned char *target, int want, int confirm)
2378{
2379    char buf[512];
2380    int i = 0, rc;
2381    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
2382    COPY(buf, i, myid, 20, 512);
2383    rc = snprintf(buf + i, 512 - i, "6:target20:"); INC(i, rc, 512);
2384    COPY(buf, i, target, 20, 512);
2385    if(want > 0) {
2386        rc = snprintf(buf + i, 512 - i, "4:wantl%s%se",
2387                      (want & WANT4) ? "2:n4" : "",
2388                      (want & WANT6) ? "2:n6" : "");
2389        INC(i, rc, 512);
2390    }
2391    rc = snprintf(buf + i, 512 - i, "e1:q9:find_node1:t%d:", tid_len);
2392    INC(i, rc, 512);
2393    COPY(buf, i, tid, tid_len, 512);
2394    ADD_V(buf, i, 512);
2395    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
2396    return dht_send(buf, i, confirm ? MSG_CONFIRM : 0, sa, salen);
2397
2398 fail:
2399    errno = ENOSPC;
2400    return -1;
2401}
2402
2403int
2404send_nodes_peers(struct sockaddr *sa, int salen,
2405                 const unsigned char *tid, int tid_len,
2406                 const unsigned char *nodes, int nodes_len,
2407                 const unsigned char *nodes6, int nodes6_len,
2408                 int af, struct storage *st,
2409                 const unsigned char *token, int token_len)
2410{
2411    char buf[2048];
2412    int i = 0, rc, j0, j, k, len;
2413
2414    rc = snprintf(buf + i, 2048 - i, "d1:rd2:id20:"); INC(i, rc, 2048);
2415    COPY(buf, i, myid, 20, 2048);
2416    if(nodes_len > 0) {
2417        rc = snprintf(buf + i, 2048 - i, "5:nodes%d:", nodes_len);
2418        INC(i, rc, 2048);
2419        COPY(buf, i, nodes, nodes_len, 2048);
2420    }
2421    if(nodes6_len > 0) {
2422         rc = snprintf(buf + i, 2048 - i, "6:nodes6%d:", nodes6_len);
2423         INC(i, rc, 2048);
2424         COPY(buf, i, nodes6, nodes6_len, 2048);
2425    }
2426    if(token_len > 0) {
2427        rc = snprintf(buf + i, 2048 - i, "5:token%d:", token_len);
2428        INC(i, rc, 2048);
2429        COPY(buf, i, token, token_len, 2048);
2430    }
2431
2432    if(st && st->numpeers > 0) {
2433        /* We treat the storage as a circular list, and serve a randomly
2434           chosen slice.  In order to make sure we fit within 1024 octets,
2435           we limit ourselves to 50 peers. */
2436
2437        len = af == AF_INET ? 4 : 16;
2438        j0 = random() % st->numpeers;
2439        j = j0;
2440        k = 0;
2441
2442        rc = snprintf(buf + i, 2048 - i, "6:valuesl"); INC(i, rc, 2048);
2443        do {
2444            if(st->peers[j].len == len) {
2445                unsigned short swapped;
2446                swapped = htons(st->peers[j].port);
2447                rc = snprintf(buf + i, 2048 - i, "%d:", len + 2);
2448                INC(i, rc, 2048);
2449                COPY(buf, i, st->peers[j].ip, len, 2048);
2450                COPY(buf, i, &swapped, 2, 2048);
2451                k++;
2452            }
2453            j = (j + 1) % st->numpeers;
2454        } while(j != j0 && k < 50);
2455        rc = snprintf(buf + i, 2048 - i, "e"); INC(i, rc, 2048);
2456    }
2457
2458    rc = snprintf(buf + i, 2048 - i, "e1:t%d:", tid_len); INC(i, rc, 2048);
2459    COPY(buf, i, tid, tid_len, 2048);
2460    ADD_V(buf, i, 2048);
2461    rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048);
2462
2463    return dht_send(buf, i, 0, sa, salen);
2464
2465 fail:
2466    errno = ENOSPC;
2467    return -1;
2468}
2469
2470static int
2471insert_closest_node(unsigned char *nodes, int numnodes,
2472                    const unsigned char *id, struct node *n)
2473{
2474    int i, size;
2475
2476    if(n->ss.ss_family == AF_INET)
2477        size = 26;
2478    else if(n->ss.ss_family == AF_INET6)
2479        size = 38;
2480    else
2481        abort();
2482
2483    for(i = 0; i< numnodes; i++) {
2484        if(id_cmp(n->id, nodes + size * i) == 0)
2485            return numnodes;
2486        if(xorcmp(n->id, nodes + size * i, id) < 0)
2487            break;
2488    }
2489
2490    if(i == 8)
2491        return numnodes;
2492
2493    if(numnodes < 8)
2494        numnodes++;
2495
2496    if(i < numnodes - 1)
2497        memmove(nodes + size * (i + 1), nodes + size * i,
2498                size * (numnodes - i - 1));
2499
2500    if(n->ss.ss_family == AF_INET) {
2501        struct sockaddr_in *sin = (struct sockaddr_in*)&n->ss;
2502        memcpy(nodes + size * i, n->id, 20);
2503        memcpy(nodes + size * i + 20, &sin->sin_addr, 4);
2504        memcpy(nodes + size * i + 24, &sin->sin_port, 2);
2505    } else if(n->ss.ss_family == AF_INET6) {
2506        struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)&n->ss;
2507        memcpy(nodes + size * i, n->id, 20);
2508        memcpy(nodes + size * i + 20, &sin6->sin6_addr, 16);
2509        memcpy(nodes + size * i + 36, &sin6->sin6_port, 2);
2510    } else {
2511        abort();
2512    }
2513
2514    return numnodes;
2515}
2516
2517static int
2518buffer_closest_nodes(unsigned char *nodes, int numnodes,
2519                     const unsigned char *id, struct bucket *b)
2520{
2521    struct node *n = b->nodes;
2522    while(n) {
2523        if(node_good(n))
2524            numnodes = insert_closest_node(nodes, numnodes, id, n);
2525        n = n->next;
2526    }
2527    return numnodes;
2528}
2529
2530int
2531send_closest_nodes(struct sockaddr *sa, int salen,
2532                   const unsigned char *tid, int tid_len,
2533                   const unsigned char *id, int want,
2534                   int af, struct storage *st,
2535                   const unsigned char *token, int token_len)
2536{
2537    unsigned char nodes[8 * 26];
2538    unsigned char nodes6[8 * 38];
2539    int numnodes = 0, numnodes6 = 0;
2540    struct bucket *b;
2541
2542    if(want < 0)
2543        want = sa->sa_family == AF_INET ? WANT4 : WANT6;
2544
2545    if((want & WANT4)) {
2546        b = find_bucket(id, AF_INET);
2547        if(b) {
2548            numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
2549            if(b->next)
2550                numnodes = buffer_closest_nodes(nodes, numnodes, id, b->next);
2551            b = previous_bucket(b);
2552            if(b)
2553                numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
2554        }
2555    }
2556
2557    if((want & WANT6)) {
2558        b = find_bucket(id, AF_INET6);
2559        if(b) {
2560            numnodes6 = buffer_closest_nodes(nodes6, numnodes6, id, b);
2561            if(b->next)
2562                numnodes6 =
2563                    buffer_closest_nodes(nodes6, numnodes6, id, b->next);
2564            b = previous_bucket(b);
2565            if(b)
2566                numnodes6 = buffer_closest_nodes(nodes6, numnodes6, id, b);
2567        }
2568    }
2569    debugf("  (%d+%d nodes.)\n", numnodes, numnodes6);
2570
2571    return send_nodes_peers(sa, salen, tid, tid_len,
2572                            nodes, numnodes * 26,
2573                            nodes6, numnodes6 * 38,
2574                            af, st, token, token_len);
2575}
2576
2577int
2578send_get_peers(struct sockaddr *sa, int salen,
2579               unsigned char *tid, int tid_len, unsigned char *infohash,
2580               int want, int confirm)
2581{
2582    char buf[512];
2583    int i = 0, rc;
2584
2585    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
2586    COPY(buf, i, myid, 20, 512);
2587    rc = snprintf(buf + i, 512 - i, "9:info_hash20:"); INC(i, rc, 512);
2588    COPY(buf, i, infohash, 20, 512);
2589    if(want > 0) {
2590        rc = snprintf(buf + i, 512 - i, "4:wantl%s%se",
2591                      (want & WANT4) ? "2:n4" : "",
2592                      (want & WANT6) ? "2:n6" : "");
2593        INC(i, rc, 512);
2594    }
2595    rc = snprintf(buf + i, 512 - i, "e1:q9:get_peers1:t%d:", tid_len);
2596    INC(i, rc, 512);
2597    COPY(buf, i, tid, tid_len, 512);
2598    ADD_V(buf, i, 512);
2599    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
2600    return dht_send(buf, i, confirm ? MSG_CONFIRM : 0, sa, salen);
2601
2602 fail:
2603    errno = ENOSPC;
2604    return -1;
2605}
2606
2607int
2608send_announce_peer(struct sockaddr *sa, int salen,
2609                   unsigned char *tid, int tid_len,
2610                   unsigned char *infohash, unsigned short port,
2611                   unsigned char *token, int token_len, int confirm)
2612{
2613    char buf[512];
2614    int i = 0, rc;
2615
2616    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
2617    COPY(buf, i, myid, 20, 512);
2618    rc = snprintf(buf + i, 512 - i, "9:info_hash20:"); INC(i, rc, 512);
2619    COPY(buf, i, infohash, 20, 512);
2620    rc = snprintf(buf + i, 512 - i, "4:porti%ue5:token%d:", (unsigned)port,
2621                  token_len);
2622    INC(i, rc, 512);
2623    COPY(buf, i, token, token_len, 512);
2624    rc = snprintf(buf + i, 512 - i, "e1:q13:announce_peer1:t%d:", tid_len);
2625    INC(i, rc, 512);
2626    COPY(buf, i, tid, tid_len, 512);
2627    ADD_V(buf, i, 512);
2628    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
2629
2630    return dht_send(buf, i, confirm ? 0 : MSG_CONFIRM, sa, salen);
2631
2632 fail:
2633    errno = ENOSPC;
2634    return -1;
2635}
2636
2637static int
2638send_peer_announced(struct sockaddr *sa, int salen,
2639                    unsigned char *tid, int tid_len)
2640{
2641    char buf[512];
2642    int i = 0, rc;
2643
2644    rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512);
2645    COPY(buf, i, myid, 20, 512);
2646    rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len);
2647    INC(i, rc, 512);
2648    COPY(buf, i, tid, tid_len, 512);
2649    ADD_V(buf, i, 512);
2650    rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512);
2651    return dht_send(buf, i, 0, sa, salen);
2652
2653 fail:
2654    errno = ENOSPC;
2655    return -1;
2656}
2657
2658static int
2659send_error(struct sockaddr *sa, int salen,
2660           unsigned char *tid, int tid_len,
2661           int code, const char *message)
2662{
2663    char buf[512];
2664    int i = 0, rc;
2665
2666    rc = snprintf(buf + i, 512 - i, "d1:eli%de%d:",
2667                  code, (int)strlen(message));
2668    INC(i, rc, 512);
2669    COPY(buf, i, message, (int)strlen(message), 512);
2670    rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
2671    COPY(buf, i, tid, tid_len, 512);
2672    ADD_V(buf, i, 512);
2673    rc = snprintf(buf + i, 512 - i, "1:y1:ee"); INC(i, rc, 512);
2674    return dht_send(buf, i, 0, sa, salen);
2675
2676 fail:
2677    errno = ENOSPC;
2678    return -1;
2679}
2680
2681#undef CHECK
2682#undef INC
2683#undef COPY
2684#undef ADD_V
2685
2686#ifndef HAVE_MEMMEM
2687static void *
2688memmem(const void *haystack, size_t haystacklen,
2689       const void *needle, size_t needlelen)
2690{
2691    const char *h = haystack;
2692    const char *n = needle;
2693    size_t i;
2694
2695    /* size_t is unsigned */
2696    if(needlelen > haystacklen)
2697        return NULL;
2698
2699    for(i = 0; i <= haystacklen - needlelen; i++) {
2700        if(memcmp(h + i, n, needlelen) == 0)
2701            return (void*)(h + i);
2702    }
2703    return NULL;
2704}
2705#endif
2706
2707static int
2708parse_message(const unsigned char *buf, int buflen,
2709              unsigned char *tid_return, int *tid_len,
2710              unsigned char *id_return, unsigned char *info_hash_return,
2711              unsigned char *target_return, unsigned short *port_return,
2712              unsigned char *token_return, int *token_len,
2713              unsigned char *nodes_return, int *nodes_len,
2714              unsigned char *nodes6_return, int *nodes6_len,
2715              unsigned char *values_return, int *values_len,
2716              unsigned char *values6_return, int *values6_len,
2717              int *want_return)
2718{
2719    const unsigned char *p;
2720
2721    /* This code will happily crash if the buffer is not NUL-terminated. */
2722    if(buf[buflen] != '\0') {
2723        debugf("Eek!  parse_message with unterminated buffer.\n");
2724        return -1;
2725    }
2726
2727#define CHECK(ptr, len)                                                 \
2728    if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow;
2729
2730    if(tid_return) {
2731        p = memmem(buf, buflen, "1:t", 3);
2732        if(p) {
2733            long l;
2734            char *q;
2735            l = strtol((char*)p + 3, &q, 10);
2736            if(q && *q == ':' && l > 0 && l < *tid_len) {
2737                CHECK(q + 1, l);
2738                memcpy(tid_return, q + 1, l);
2739                *tid_len = l;
2740            } else
2741                *tid_len = 0;
2742        }
2743    }
2744    if(id_return) {
2745        p = memmem(buf, buflen, "2:id20:", 7);
2746        if(p) {
2747            CHECK(p + 7, 20);
2748            memcpy(id_return, p + 7, 20);
2749        } else {
2750            memset(id_return, 0, 20);
2751        }
2752    }
2753    if(info_hash_return) {
2754        p = memmem(buf, buflen, "9:info_hash20:", 14);
2755        if(p) {
2756            CHECK(p + 14, 20);
2757            memcpy(info_hash_return, p + 14, 20);
2758        } else {
2759            memset(info_hash_return, 0, 20);
2760        }
2761    }
2762    if(port_return) {
2763        p = memmem(buf, buflen, "porti", 5);
2764        if(p) {
2765            long l;
2766            char *q;
2767            l = strtol((char*)p + 5, &q, 10);
2768            if(q && *q == 'e' && l > 0 && l < 0x10000)
2769                *port_return = l;
2770            else
2771                *port_return = 0;
2772        } else
2773            *port_return = 0;
2774    }
2775    if(target_return) {
2776        p = memmem(buf, buflen, "6:target20:", 11);
2777        if(p) {
2778            CHECK(p + 11, 20);
2779            memcpy(target_return, p + 11, 20);
2780        } else {
2781            memset(target_return, 0, 20);
2782        }
2783    }
2784    if(token_return) {
2785        p = memmem(buf, buflen, "5:token", 7);
2786        if(p) {
2787            long l;
2788            char *q;
2789            l = strtol((char*)p + 7, &q, 10);
2790            if(q && *q == ':' && l > 0 && l < *token_len) {
2791                CHECK(q + 1, l);
2792                memcpy(token_return, q + 1, l);
2793                *token_len = l;
2794            } else
2795                *token_len = 0;
2796        } else
2797            *token_len = 0;
2798    }
2799
2800    if(nodes_len) {
2801        p = memmem(buf, buflen, "5:nodes", 7);
2802        if(p) {
2803            long l;
2804            char *q;
2805            l = strtol((char*)p + 7, &q, 10);
2806            if(q && *q == ':' && l > 0 && l < *nodes_len) {
2807                CHECK(q + 1, l);
2808                memcpy(nodes_return, q + 1, l);
2809                *nodes_len = l;
2810            } else
2811                *nodes_len = 0;
2812        } else
2813            *nodes_len = 0;
2814    }
2815
2816    if(nodes6_len) {
2817        p = memmem(buf, buflen, "6:nodes6", 8);
2818        if(p) {
2819            long l;
2820            char *q;
2821            l = strtol((char*)p + 8, &q, 10);
2822            if(q && *q == ':' && l > 0 && l < *nodes6_len) {
2823                CHECK(q + 1, l);
2824                memcpy(nodes6_return, q + 1, l);
2825                *nodes6_len = l;
2826            } else
2827                *nodes6_len = 0;
2828        } else
2829            *nodes6_len = 0;
2830    }
2831
2832    if(values_len || values6_len) {
2833        p = memmem(buf, buflen, "6:valuesl", 9);
2834        if(p) {
2835            int i = p - buf + 9;
2836            int j = 0, j6 = 0;
2837            while(1) {
2838                long l;
2839                char *q;
2840                l = strtol((char*)buf + i, &q, 10);
2841                if(q && *q == ':' && l > 0) {
2842                    CHECK(q + 1, l);
2843                    if(l == 6) {
2844                        if(j + l > *values_len)
2845                            continue;
2846                        i = q + 1 + l - (char*)buf;
2847                        memcpy((char*)values_return + j, q + 1, l);
2848                        j += l;
2849                    } else if(l == 18) {
2850                        if(j6 + l > *values6_len)
2851                            continue;
2852                        i = q + 1 + l - (char*)buf;
2853                        memcpy((char*)values6_return + j6, q + 1, l);
2854                        j6 += l;
2855                    } else {
2856                        debugf("Received weird value -- %d bytes.\n", (int)l);
2857                        i = q + 1 + l - (char*)buf;
2858                    }
2859                } else {
2860                    break;
2861                }
2862            }
2863            if(i >= buflen || buf[i] != 'e')
2864                debugf("eek... unexpected end for values.\n");
2865            if(values_len)
2866                *values_len = j;
2867            if(values6_len)
2868                *values6_len = j6;
2869        } else {
2870            *values_len = 0;
2871            *values6_len = 0;
2872        }
2873    }
2874
2875    if(want_return) {
2876        p = memmem(buf, buflen, "4:wantl", 7);
2877        if(p) {
2878            int i = p - buf + 7;
2879            *want_return = 0;
2880            while(buf[i] > '0' && buf[i] <= '9' && buf[i + 1] == ':' &&
2881                  i + 2 + buf[i] - '0' < buflen) {
2882                CHECK(buf + i + 2, buf[i] - '0');
2883                if(buf[i] == '2' && memcmp(buf + i + 2, "n4", 2) == 0)
2884                    *want_return |= WANT4;
2885                else if(buf[i] == '2' && memcmp(buf + i + 2, "n6", 2) == 0)
2886                    *want_return |= WANT6;
2887                else
2888                    debugf("eek... unexpected want flag (%c)\n", buf[i]);
2889                i += 2 + buf[i] - '0';
2890            }
2891            if(i >= buflen || buf[i] != 'e')
2892                debugf("eek... unexpected end for want.\n");
2893        } else {
2894            *want_return = -1;
2895        }
2896    }
2897
2898#undef CHECK
2899
2900    if(memmem(buf, buflen, "1:y1:r", 6))
2901        return REPLY;
2902    if(memmem(buf, buflen, "1:y1:e", 6))
2903        return ERROR;
2904    if(!memmem(buf, buflen, "1:y1:q", 6))
2905        return -1;
2906    if(memmem(buf, buflen, "1:q4:ping", 9))
2907        return PING;
2908    if(memmem(buf, buflen, "1:q9:find_node", 14))
2909       return FIND_NODE;
2910    if(memmem(buf, buflen, "1:q9:get_peers", 14))
2911        return GET_PEERS;
2912    if(memmem(buf, buflen, "1:q13:announce_peer", 19))
2913       return ANNOUNCE_PEER;
2914    return -1;
2915
2916 overflow:
2917    debugf("Truncated message.\n");
2918    return -1;
2919}
Note: See TracBrowser for help on using the repository browser.