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

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

finish #2281 - apply DHT 0.8 typo fix

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