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

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

(trunk) #3311 "MingW build of Transmission" -- apply more of rb07's diffs, though edited to lessen the inevitable #ifdefs

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