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

Last change on this file since 9323 was 9323, checked in by livings124, 13 years ago

#2514 update to dht-0.10

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