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

Last change on this file since 11301 was 11301, checked in by charles, 6 years ago

(trunk) #3618 "FreeBSD 8.1 & GCC 4.2.1 compiler warnings" -- fix some compiler warnings.

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