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

Last change on this file since 10423 was 10423, checked in by charles, 11 years ago

(trunk third-party) #2767 "DHT-formatted dictionaries are incorrect" -- fixed by upgrading our DHT snapshot to dht-0.15 from http://www.pps.jussieu.fr/~jch/software/files/dht-0.15.tar.gz

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