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

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

Import dht-0.21. This has blacklisting support.

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