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

Last change on this file since 12537 was 12537, checked in by jch, 10 years ago

Import dht-0.20.

This fixes compilation on systems that have memmem, but don't define
HAVE_MEMMEM.

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