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

Last change on this file since 9145 was 9145, checked in by charles, 13 years ago

(trunk third-party) #2302: upgrade libdht to newer version

File size: 66.6 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 there's only one bucket, split even if there remain doubtful
655           nodes.  This violates the spec, but it speeds up bootstrapping. */
656        if(mybucket && (!dubious || buckets->next == NULL)) {
657            debugf("Splitting.\n");
658            b = split_bucket(s, b);
659            mybucket_grow_time = now.tv_sec;
660            return new_node(s, id, sin, confirm);
661        }
662
663        /* No space for this node.  Cache it away for later. */
664        if(confirm || b->cached.sin_family == 0)
665            b->cached = *sin;
666
667        return NULL;
668    }
669
670    /* Create a new node. */
671    n = calloc(1, sizeof(struct node));
672    if(n == NULL)
673        return NULL;
674    memcpy(n->id, id, 20);
675    n->sin = *sin;
676    n->time = confirm ? now.tv_sec : 0;
677    n->reply_time = confirm >= 2 ? now.tv_sec : 0;
678    n->next = b->nodes;
679    b->nodes = n;
680    b->count++;
681    if(mybucket)
682        mybucket_grow_time = now.tv_sec;
683    return n;
684}
685
686/* Called periodically to purge known-bad nodes.  Note that we're very
687   conservative here: broken nodes in the table don't do much harm, we'll
688   recover as soon as we find better ones. */
689static int
690expire_buckets(int s)
691{
692    struct bucket *b = buckets;
693
694    while(b) {
695        struct node *n, *p;
696        int changed = 0;
697
698        while(b->nodes && b->nodes->pinged >= 4) {
699            n = b->nodes;
700            b->nodes = n->next;
701            b->count--;
702            changed = 1;
703            free(n);
704        }
705
706        p = b->nodes;
707        while(p) {
708            while(p->next && p->next->pinged >= 4) {
709                n = p->next;
710                p->next = n->next;
711                b->count--;
712                changed = 1;
713                free(n);
714            }
715            p = p->next;
716        }
717
718        if(changed)
719            send_cached_ping(s, b);
720
721        b = b->next;
722    }
723    expire_stuff_time = now.tv_sec + 120 + random() % 240;
724    return 1;
725}
726
727/* While a search is in progress, we don't necessarily keep the nodes being
728   walked in the main bucket table.  A search in progress is identified by
729   a unique transaction id, a short (and hence small enough to fit in the
730   transaction id of the protocol packets). */
731
732static struct search *
733find_search(unsigned short tid)
734{
735    struct search *sr = searches;
736    while(sr) {
737        if(sr->tid == tid)
738            return sr;
739        sr = sr->next;
740    }
741    return NULL;
742}
743
744/* A search contains a list of nodes, sorted by decreasing distance to the
745   target.  We just got a new candidate, insert it at the right spot or
746   discard it. */
747
748static int
749insert_search_node(unsigned char *id, struct sockaddr_in *sin,
750                   struct search *sr, int replied,
751                   unsigned char *token, int token_len)
752{
753    struct search_node *n;
754    int i, j;
755
756    for(i = 0; i < sr->numnodes; i++) {
757        if(id_cmp(id, sr->nodes[i].id) == 0) {
758            n = &sr->nodes[i];
759            goto found;
760        }
761        if(xorcmp(id, sr->nodes[i].id, sr->id) < 0)
762            break;
763    }
764
765    if(i == SEARCH_NODES)
766        return 0;
767
768    if(sr->numnodes < SEARCH_NODES)
769        sr->numnodes++;
770
771    for(j = sr->numnodes - 1; j > i; j--) {
772        sr->nodes[j] = sr->nodes[j - 1];
773    }
774
775    n = &sr->nodes[i];
776
777    memset(n, 0, sizeof(struct search_node));
778    memcpy(n->id, id, 20);
779
780found:
781    n->sin = *sin;
782
783    if(replied) {
784        n->replied = 1;
785        n->reply_time = now.tv_sec;
786        n->request_time = 0;
787        n->pinged = 0;
788    }
789    if(token) {
790        if(token_len >= 40) {
791            debugf("Eek!  Overlong token.\n");
792        } else {
793            memcpy(n->token, token, token_len);
794            n->token_len = token_len;
795        }
796    }
797
798    return 1;
799}
800
801static void
802flush_search_node(struct search_node *n, struct search *sr)
803{
804    int i = n - sr->nodes, j;
805    for(j = i; j < sr->numnodes - 1; j++)
806        sr->nodes[j] = sr->nodes[j + 1];
807    sr->numnodes--;
808}
809
810static void
811expire_searches(void)
812{
813    struct search *sr = searches, *previous = NULL;
814
815    while(sr) {
816        struct search *next = sr->next;
817        if(sr->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME) {
818            if(previous)
819                previous->next = next;
820            else
821                searches = next;
822            free(sr);
823            numsearches--;
824        } else {
825            previous = sr;
826        }
827        sr = next;
828    }
829}
830
831/* This must always return 0 or 1, never -1, not even on failure (see below). */
832static int
833search_send_get_peers(int s, struct search *sr, struct search_node *n)
834{
835    struct node *node;
836    unsigned char tid[4];
837
838    if(n == NULL) {
839        int i;
840        for(i = 0; i < sr->numnodes; i++) {
841            if(sr->nodes[i].pinged < 3 && !sr->nodes[i].replied &&
842               sr->nodes[i].request_time < now.tv_sec - 15)
843                n = &sr->nodes[i];
844        }
845    }
846
847    if(!n || n->pinged >= 3 || n->replied ||
848       n->request_time >= now.tv_sec - 15)
849        return 0;
850
851    debugf("Sending get_peers.\n");
852    make_tid(tid, "gp", sr->tid);
853    send_get_peers(s, (struct sockaddr*)&n->sin,
854                   sizeof(struct sockaddr_in), tid, 4, sr->id,
855                   n->reply_time >= now.tv_sec - 15);
856    n->pinged++;
857    n->request_time = now.tv_sec;
858    /* If the node happens to be in our main routing table, mark it
859       as pinged. */
860    node = find_node(n->id);
861    if(node) pinged(s, node, NULL);
862    return 1;
863}
864
865/* When a search is in progress, we periodically call search_step to send
866   further requests. */
867static void
868search_step(int s, struct search *sr, dht_callback *callback, void *closure)
869{
870    int i, j;
871    int all_done = 1;
872
873    /* Check if the first 8 live nodes have replied. */
874    j = 0;
875    for(i = 0; i < sr->numnodes && j < 8; i++) {
876        struct search_node *n = &sr->nodes[i];
877        if(n->pinged >= 3)
878            continue;
879        if(!n->replied) {
880            all_done = 0;
881            break;
882        }
883        j++;
884    }
885
886    if(all_done) {
887        if(sr->port == 0) {
888            goto done;
889        } else {
890            int all_acked = 1;
891            j = 0;
892            for(i = 0; i < sr->numnodes && j < 8; i++) {
893                struct search_node *n = &sr->nodes[i];
894                struct node *node;
895                unsigned char tid[4];
896                if(n->pinged >= 3)
897                    continue;
898                if(!n->acked) {
899                    all_acked = 0;
900                    debugf("Sending announce_peer.\n");
901                    make_tid(tid, "ap", sr->tid);
902                    send_announce_peer(s,
903                                       (struct sockaddr*)&n->sin,
904                                       sizeof(struct sockaddr_in),
905                                       tid, 4, sr->id, sr->port,
906                                       n->token, n->token_len,
907                                       n->reply_time >= now.tv_sec - 15);
908                    n->pinged++;
909                    n->request_time = now.tv_sec;
910                    node = find_node(n->id);
911                    if(node) pinged(s, node, NULL);
912                }
913                j++;
914            }
915            if(all_acked)
916                goto done;
917        }
918        sr->step_time = now.tv_sec;
919        return;
920    }
921
922    if(sr->step_time + 15 >= now.tv_sec)
923        return;
924
925    j = 0;
926    for(i = 0; i < sr->numnodes; i++) {
927        j += search_send_get_peers(s, sr, &sr->nodes[i]);
928        if(j >= 3)
929            break;
930    }
931    sr->step_time = now.tv_sec;
932    return;
933
934 done:
935    sr->done = 1;
936    if(callback)
937        (*callback)(closure, DHT_EVENT_SEARCH_DONE, sr->id, NULL, 0);
938    sr->step_time = now.tv_sec;
939}
940
941static struct search *
942new_search(void)
943{
944    struct search *sr, *oldest = NULL;
945
946    /* Find the oldest done search */
947    sr = searches;
948    while(sr) {
949        if(sr->done &&
950           (oldest == NULL || oldest->step_time > sr->step_time))
951            oldest = sr;
952        sr = sr->next;
953    }
954
955    /* The oldest slot is expired. */
956    if(oldest && oldest->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME)
957        return oldest;
958
959    /* Allocate a new slot. */
960    if(numsearches < DHT_MAX_SEARCHES) {
961        sr = calloc(1, sizeof(struct search));
962        if(sr != NULL) {
963            sr->next = searches;
964            searches = sr;
965            numsearches++;
966            return sr;
967        }
968    }
969
970    /* Oh, well, never mind.  Reuse the oldest slot. */
971    return oldest;
972}
973
974/* Insert the contents of a bucket into a search structure. */
975static void
976insert_search_bucket(struct bucket *b, struct search *sr)
977{
978    struct node *n;
979    n = b->nodes;
980    while(n) {
981        insert_search_node(n->id, &n->sin, sr, 0, NULL, 0);
982        n = n->next;
983    }
984}
985
986/* Start a search.  If port is non-zero, perform an announce when the
987   search is complete. */
988int 
989dht_search(int s, const unsigned char *id, int port,
990           dht_callback *callback, void *closure)
991{
992    struct search *sr;
993    struct bucket *b;
994
995    sr = searches;
996    while(sr) {
997        if(id_cmp(sr->id, id) == 0)
998            break;
999        sr = sr->next;
1000    }
1001
1002    if(sr) {
1003        /* We're reusing data from an old search.  Reusing the same tid
1004           means that we can merge replies for both searches. */
1005        int i;
1006        sr->done = 0;
1007    again:
1008        for(i = 0; i < sr->numnodes; i++) {
1009            struct search_node *n;
1010            n = &sr->nodes[i];
1011            /* Discard any doubtful nodes. */
1012            if(n->pinged >= 3 || n->reply_time < now.tv_sec - 7200) {
1013                flush_search_node(n, sr);
1014                goto again;
1015            }
1016            n->pinged = 0;
1017            n->token_len = 0;
1018            n->replied = 0;
1019            n->acked = 0;
1020        }
1021    } else {
1022        sr = new_search();
1023        if(sr == NULL) {
1024            errno = ENOSPC;
1025            return -1;
1026        }
1027        sr->tid = search_id++;
1028        sr->step_time = 0;
1029        memcpy(sr->id, id, 20);
1030        sr->done = 0;
1031        sr->numnodes = 0;
1032    }
1033
1034    sr->port = port;
1035
1036    b = find_bucket(id);
1037    insert_search_bucket(b, sr);
1038
1039    if(sr->numnodes < SEARCH_NODES) {
1040        struct bucket *p = previous_bucket(b);
1041        if(b->next)
1042            insert_search_bucket(b->next, sr);
1043        if(p)
1044            insert_search_bucket(p, sr);
1045    }
1046    if(sr->numnodes < SEARCH_NODES)
1047        insert_search_bucket(find_bucket(myid), sr);
1048
1049    search_step(s, sr, callback, closure);
1050    search_time = now.tv_sec;
1051    return 1;
1052}
1053
1054/* A struct storage stores all the stored peer addresses for a given info
1055   hash. */
1056
1057static struct storage *
1058find_storage(const unsigned char *id)
1059{
1060    struct storage *st = storage;
1061
1062    while(st) {
1063        if(id_cmp(id, st->id) == 0)
1064            break;
1065        st = st->next;
1066    }
1067    return st;
1068}
1069
1070static int
1071storage_store(const unsigned char *id, const unsigned char *ip,
1072              unsigned short port)
1073{
1074    int i;
1075    struct storage *st = storage;
1076
1077    st = find_storage(id);
1078
1079    if(st == NULL) {
1080        st = calloc(1, sizeof(struct storage));
1081        if(st == NULL) return -1;
1082        memcpy(st->id, id, 20);
1083        st->next = storage;
1084        storage = st;
1085    }
1086
1087    for(i = 0; i < st->numpeers; i++) {
1088        if(st->peers[i].port == port && memcmp(st->peers[i].ip, ip, 4) == 0)
1089            break;
1090    }
1091    if(i < st->numpeers) {
1092        /* Already there, only need to refresh */
1093        st->peers[i].time = now.tv_sec;
1094        return 0;
1095    } else {
1096        struct peer *p;
1097        if(i >= st->maxpeers) {
1098            /* Need to expand the array. */
1099            struct peer *new_peers;
1100            int n;
1101            if(st->maxpeers > DHT_MAX_PEERS / 2)
1102                return 0;
1103            n = st->maxpeers == 0 ? 2 : 2 * st->maxpeers;
1104            new_peers = realloc(st->peers, n * sizeof(struct peer));
1105            if(new_peers == NULL)
1106                return -1;
1107            st->peers = new_peers;
1108            st->maxpeers = n;
1109        }
1110        p = &st->peers[st->numpeers++];
1111        p->time = now.tv_sec;
1112        memcpy(p->ip, ip, 4);
1113        p->port = port;
1114        return 1;
1115    }
1116}
1117
1118static int
1119expire_storage(void)
1120{
1121    struct storage *st = storage, *previous = NULL;
1122    while(st) {
1123        int i = 0;
1124        while(i < st->numpeers) {
1125            if(st->peers[i].time < now.tv_sec - 32 * 60) {
1126                if(i != st->numpeers - 1)
1127                    st->peers[i] = st->peers[st->numpeers - 1];
1128                st->numpeers--;
1129            } else {
1130                i++;
1131            }
1132        }
1133
1134        if(st->numpeers == 0) {
1135            free(st->peers);
1136            if(previous)
1137                previous->next = st->next;
1138            else
1139                storage = st->next;
1140            free(st);
1141            if(previous)
1142                st = previous->next;
1143            else
1144                st = storage;
1145        } else {
1146            previous = st;
1147            st = st->next;
1148        }
1149    }
1150    return 1;
1151}
1152
1153/* We've just found out that a node is buggy. */
1154static void
1155broken_node(int s, const unsigned char *id, struct sockaddr_in *sin)
1156{
1157    int i;
1158
1159    debugf("Blacklisting broken node.\n");
1160
1161    if(id) {
1162        struct node *n;
1163        struct search *sr;
1164        /* Make the node easy to discard. */
1165        n = find_node(id);
1166        if(n) {
1167            n->pinged = 3;
1168            pinged(s, n, NULL);
1169        }
1170        /* Discard it from any searches in progress. */
1171        sr = searches;
1172        while(sr) {
1173            for(i = 0; i < sr->numnodes; i++)
1174                if(id_cmp(sr->nodes[i].id, id) == 0)
1175                    flush_search_node(&sr->nodes[i], sr);
1176            sr = sr->next;
1177        }
1178    }
1179    /* And make sure we don't hear from it again. */
1180    blacklist[next_blacklisted] = *sin;
1181    next_blacklisted = (next_blacklisted + 1) % DHT_MAX_BLACKLISTED;
1182}
1183
1184static int
1185rotate_secrets(void)
1186{
1187    int rc;
1188
1189    rotate_secrets_time = now.tv_sec + 900 + random() % 1800;
1190
1191    memcpy(oldsecret, secret, sizeof(secret));
1192    rc = dht_random_bytes(secret, sizeof(secret));
1193
1194    if(rc < 0)
1195        return -1;
1196
1197    return 1;
1198}
1199
1200#ifndef TOKEN_SIZE
1201#define TOKEN_SIZE 8
1202#endif
1203
1204static void
1205make_token(const unsigned char *ipv4, unsigned short port, int old,
1206           unsigned char *token_return)
1207{
1208    dht_hash(token_return, TOKEN_SIZE,
1209             old ? oldsecret : secret, sizeof(secret),
1210             ipv4, 4,
1211             (unsigned char*)&port, 2);
1212}
1213static int
1214token_match(unsigned char *token, int token_len,
1215            const unsigned char *ipv4, unsigned short port)
1216{
1217    unsigned char t[TOKEN_SIZE];
1218    if(token_len != TOKEN_SIZE)
1219        return 0;
1220    make_token(ipv4, port, 0, t);
1221    if(memcmp(t, token, TOKEN_SIZE) == 0)
1222        return 1;
1223    make_token(ipv4, port, 1, t);
1224    if(memcmp(t, token, TOKEN_SIZE) == 0)
1225        return 1;
1226    return 0;
1227}
1228
1229int
1230dht_nodes(int *good_return, int *dubious_return, int *cached_return,
1231          int *incoming_return)
1232{
1233    int good = 0, dubious = 0, cached = 0, incoming = 0;
1234    struct bucket *b = buckets;
1235    while(b) {
1236        struct node *n = b->nodes;
1237        while(n) {
1238            if(node_good(n)) {
1239                good++;
1240                if(n->time > n->reply_time)
1241                    incoming++;
1242            } else {
1243                dubious++;
1244            }
1245            n = n->next;
1246        }
1247        if(b->cached.sin_family == AF_INET)
1248            cached++;
1249        b = b->next;
1250    }
1251    if(good_return)
1252        *good_return = good;
1253    if(dubious_return)
1254        *dubious_return = dubious;
1255    if(cached_return)
1256        *cached_return = cached;
1257    if(incoming_return)
1258        *incoming_return = incoming;
1259    return good + dubious;
1260}
1261               
1262
1263void
1264dht_dump_tables(FILE *f)
1265{
1266    int i;
1267    struct bucket *b = buckets;
1268    struct storage *st = storage;
1269    struct search *sr = searches;
1270
1271    fprintf(f, "My id ");
1272    print_hex(f, myid, 20);
1273    fprintf(f, "\n");
1274    while(b) {
1275        struct node *n = b->nodes;
1276        fprintf(f, "Bucket ");
1277        print_hex(f, b->first, 20);
1278        fprintf(f, " count %d age %d%s%s:\n",
1279               b->count, (int)(now.tv_sec - b->time),
1280               in_bucket(myid, b) ? " (mine)" : "",
1281               b->cached.sin_family ? " (cached)" : "");
1282        while(n) {
1283            char buf[512];
1284            fprintf(f, "    Node ");
1285            print_hex(f, n->id, 20);
1286            inet_ntop(AF_INET, &n->sin.sin_addr, buf, 512);
1287            fprintf(f, " %s:%d ", buf, ntohs(n->sin.sin_port));
1288            if(n->time != n->reply_time)
1289                fprintf(f, "age %ld, %ld",
1290                       (long)(now.tv_sec - n->time),
1291                       (long)(now.tv_sec - n->reply_time));
1292            else
1293                fprintf(f, "age %ld", (long)(now.tv_sec - n->time));
1294            if(n->pinged)
1295                fprintf(f, " (%d)", n->pinged);
1296            if(node_good(n))
1297                fprintf(f, " (good)");
1298            fprintf(f, "\n");
1299            n = n->next;
1300        }
1301        b = b->next;
1302    }
1303    while(sr) {
1304        fprintf(f, "\nSearch id ");
1305        print_hex(f, sr->id, 20);
1306        fprintf(f, " age %d%s\n", (int)(now.tv_sec - sr->step_time),
1307               sr->done ? " (done)" : "");
1308        for(i = 0; i < sr->numnodes; i++) {
1309            struct search_node *n = &sr->nodes[i];
1310            fprintf(f, "Node %d id ", i);
1311            print_hex(f, n->id, 20);
1312            fprintf(f, " bits %d age ", common_bits(sr->id, n->id));
1313            if(n->request_time)
1314                fprintf(f, "%d, ", (int)(now.tv_sec - n->request_time));
1315            fprintf(f, "%d", (int)(now.tv_sec - n->reply_time));
1316            if(n->pinged)
1317                fprintf(f, " (%d)", n->pinged);
1318            fprintf(f, "%s%s.\n",
1319                   find_node(n->id) ? " (known)" : "",
1320                   n->replied ? " (replied)" : "");
1321        }
1322        sr = sr->next;
1323    }
1324
1325   
1326    while(st) {
1327        fprintf(f, "\nStorage ");
1328        print_hex(f, st->id, 20);
1329        fprintf(f, " %d/%d nodes:", st->numpeers, st->maxpeers);
1330        for(i = 0; i < st->numpeers; i++) {
1331            char buf[20];
1332            inet_ntop(AF_INET, st->peers[i].ip, buf, 20);
1333            fprintf(f, " %s:%u (%ld)",
1334                    buf, st->peers[i].port,
1335                    (long)(now.tv_sec - st->peers[i].time));
1336        }
1337        st = st->next;
1338    }
1339   
1340    fprintf(f, "\n\n");
1341    fflush(f);
1342}
1343
1344int
1345dht_init(int s, const unsigned char *id, const unsigned char *v)
1346{
1347    int rc;
1348
1349    if(buckets) {
1350        errno = EBUSY;
1351        return -1;
1352    }
1353
1354    buckets = calloc(sizeof(struct bucket), 1);
1355    if(buckets == NULL)
1356        return -1;
1357
1358    searches = NULL;
1359    numsearches = 0;
1360
1361    storage = NULL;
1362
1363    rc = fcntl(s, F_GETFL, 0);
1364    if(rc < 0)
1365        goto fail;
1366
1367    rc = fcntl(s, F_SETFL, (rc | O_NONBLOCK));
1368    if(rc < 0)
1369        goto fail;
1370
1371    memcpy(myid, id, 20);
1372    if(v) {
1373        memcpy(my_v, "1:v4:", 5);
1374        memcpy(my_v + 5, v, 4);
1375        have_v = 1;
1376    } else {
1377        have_v = 0;
1378    }
1379
1380    gettimeofday(&now, NULL);
1381
1382    mybucket_grow_time = now.tv_sec;
1383    confirm_nodes_time = now.tv_sec + random() % 3;
1384
1385    search_id = random() & 0xFFFF;
1386    search_time = 0;
1387
1388    next_blacklisted = 0;
1389
1390    leaky_bucket_time = now.tv_sec;
1391    leaky_bucket_tokens = MAX_LEAKY_BUCKET_TOKENS;
1392
1393    memset(secret, 0, sizeof(secret));
1394    rc = rotate_secrets();
1395    if(rc < 0)
1396        goto fail;
1397
1398    expire_buckets(s);
1399
1400    return 1;
1401
1402 fail:
1403    free(buckets);
1404    buckets = NULL;
1405    return -1;
1406}
1407
1408int
1409dht_uninit(int s, int dofree)
1410{
1411    if(!dofree)
1412        return 1;
1413
1414    while(buckets) {
1415        struct bucket *b = buckets;
1416        buckets = b->next;
1417        while(b->nodes) {
1418            struct node *n = b->nodes;
1419            b->nodes = n->next;
1420            free(n);
1421        }
1422        free(b);
1423    }
1424
1425    while(storage) {
1426        struct storage *st = storage;
1427        storage = storage->next;
1428        free(st->peers);
1429        free(st);
1430    }
1431
1432    while(searches) {
1433        struct search *sr = searches;
1434        searches = searches->next;
1435        free(sr);
1436    }
1437
1438    return 1;
1439}
1440
1441/* Rate control for requests we receive. */
1442
1443static int
1444leaky_bucket(void)
1445{
1446    if(leaky_bucket_tokens == 0) {
1447        leaky_bucket_tokens = MIN(MAX_LEAKY_BUCKET_TOKENS,
1448                                  4 * (now.tv_sec - leaky_bucket_time));
1449        leaky_bucket_time = now.tv_sec;
1450    }
1451
1452    if(leaky_bucket_tokens == 0)
1453        return 0;
1454
1455    leaky_bucket_tokens--;
1456    return 1;
1457}
1458
1459int
1460dht_periodic(int s, int available, time_t *tosleep,
1461             dht_callback *callback, void *closure)
1462{
1463    gettimeofday(&now, NULL);
1464
1465    if(available) {
1466        int rc, i, message;
1467        unsigned char tid[16], id[20], info_hash[20], target[20];
1468        unsigned char buf[1536], nodes[256], token[128];
1469        int tid_len = 16, token_len = 128;
1470        int nodes_len = 256;
1471        unsigned short port;
1472        unsigned char values[2048];
1473        int values_len = 2048;
1474        struct sockaddr_in source;
1475        socklen_t source_len = sizeof(struct sockaddr_in);
1476        unsigned short ttid;
1477
1478        rc = recvfrom(s, buf, 1536, 0,
1479                      (struct sockaddr*)&source, &source_len);
1480        if(rc < 0) {
1481            if(errno == EAGAIN)
1482                goto dontread;
1483            else
1484                return rc;
1485        }
1486
1487        if(source_len != sizeof(struct sockaddr_in)) {
1488            /* Hmm... somebody gave us an IPv6 socket. */
1489            errno = EINVAL;
1490            return -1;
1491        }
1492
1493        for(i = 0; i < DHT_MAX_BLACKLISTED; i++) {
1494            if(blacklist[i].sin_family == AF_INET &&
1495               blacklist[i].sin_port == source.sin_port &&
1496               memcmp(&blacklist[i].sin_addr, &source.sin_addr, 4) == 0) {
1497                debugf("Received packet from blacklisted node.\n");
1498                goto dontread;
1499            }
1500        }
1501
1502        /* There's a bug in parse_message -- it will happily overflow the
1503           buffer if it's not NUL-terminated.  For now, put a NUL at the
1504           end of buffers. */
1505
1506        if(rc < 1536) {
1507            buf[rc] = '\0';
1508        } else {
1509            debugf("Overlong message.\n");
1510            goto dontread;
1511        }
1512
1513        message = parse_message(buf, rc, tid, &tid_len, id, info_hash,
1514                                target, &port, token, &token_len,
1515                                nodes, &nodes_len, values, &values_len);
1516        if(id_cmp(id, zeroes) == 0) {
1517            debugf("Message with no id: ");
1518            debug_printable(buf, rc);
1519            debugf("\n");
1520            goto dontread;
1521        }
1522
1523        if(id_cmp(id, myid) == 0) {
1524            debugf("Received message from self.\n");
1525            goto dontread;
1526        }
1527
1528        if(message > REPLY) {
1529            /* Rate limit requests. */
1530            if(!leaky_bucket()) {
1531                debugf("Dropping request due to rate limiting.\n");
1532                goto dontread;
1533            }
1534        }
1535
1536        switch(message) {
1537        case REPLY:
1538            if(tid_len != 4) {
1539                debugf("Broken node truncates transaction ids: ");
1540                debug_printable(buf, rc);
1541                printf("\n");
1542                /* This is really annoying, as it means that we will
1543                   time-out all our searches that go through this node.
1544                   Kill it. */
1545                broken_node(s, id, &source);
1546                goto dontread;
1547            }
1548            if(tid_match(tid, "pn", NULL)) {
1549                debugf("Pong!\n");
1550                new_node(s, id, &source, 2);
1551            } else if(tid_match(tid, "fn", NULL) ||
1552                      tid_match(tid, "gp", NULL)) {
1553                int gp = 0;
1554                struct search *sr = NULL;
1555                if(tid_match(tid, "gp", &ttid)) {
1556                    gp = 1;
1557                    sr = find_search(ttid);
1558                }
1559                debugf("Nodes found (%d)%s!\n", nodes_len / 26,
1560                       gp ? " for get_peers" : "");
1561                if(nodes_len % 26 != 0) {
1562                    debugf("Unexpected length for node info!\n");
1563                    broken_node(s, id, &source);
1564                } else if(gp && sr == NULL) {
1565                    debugf("Unknown search!\n");
1566                    new_node(s, id, &source, 1);
1567                } else {
1568                    int i;
1569                    new_node(s, id, &source, 2);
1570                    for(i = 0; i < nodes_len / 26; i++) {
1571                        unsigned char *ni = nodes + i * 26;
1572                        struct sockaddr_in sin;
1573                        if(id_cmp(ni, myid) == 0)
1574                            continue;
1575                        memset(&sin, 0, sizeof(sin));
1576                        sin.sin_family = AF_INET;
1577                        memcpy(&sin.sin_addr, ni + 20, 4);
1578                        memcpy(&sin.sin_port, ni + 24, 2);
1579                        new_node(s, ni, &sin, 0);
1580                        if(sr) {
1581                            insert_search_node(ni, &sin, sr, 0, NULL, 0);
1582                        }
1583                    }
1584                    if(sr)
1585                        /* Since we received a reply, the number of
1586                           requests in flight has decreased.  Let's push
1587                           another request. */
1588                        search_send_get_peers(s, sr, NULL);
1589                }
1590                if(sr) {
1591                    insert_search_node(id, &source, sr,
1592                                       1, token, token_len);
1593                    if(values_len > 0) {
1594                        debugf("Got values (%d)!\n", values_len / 6);
1595                        if(callback) {
1596                            (*callback)(closure, DHT_EVENT_VALUES,
1597                                        sr->id, (void*)values, values_len);
1598                        }
1599                    }
1600                }
1601            } else if(tid_match(tid, "ap", &ttid)) {
1602                struct search *sr;
1603                debugf("Got reply to announce_peer.\n");
1604                sr = find_search(ttid);
1605                if(!sr) {
1606                    debugf("Unknown search!\n");
1607                    new_node(s, id, &source, 1);
1608                } else {
1609                    int i;
1610                    new_node(s, id, &source, 2);
1611                    for(i = 0; i < sr->numnodes; i++)
1612                        if(id_cmp(sr->nodes[i].id, id) == 0) {
1613                            sr->nodes[i].request_time = 0;
1614                            sr->nodes[i].reply_time = now.tv_sec;
1615                            sr->nodes[i].acked = 1;
1616                            sr->nodes[i].pinged = 0;
1617                            break;
1618                        }
1619                    /* See comment for gp above. */
1620                    search_send_get_peers(s, sr, NULL);
1621                }
1622            } else {
1623                debugf("Unexpected reply: ");
1624                debug_printable(buf, rc);
1625                debugf("\n");
1626            }
1627            break;
1628        case PING:
1629            debugf("Ping (%d)!\n", tid_len);
1630            new_node(s, id, &source, 1);
1631            debugf("Sending pong.\n");
1632            send_pong(s, (struct sockaddr*)&source, sizeof(source),
1633                      tid, tid_len);
1634            break;
1635        case FIND_NODE:
1636            debugf("Find node!\n");
1637            new_node(s, id, &source, 1);
1638            debugf("Sending closest nodes.\n");
1639            send_closest_nodes(s, (struct sockaddr*)&source, sizeof(source),
1640                               tid, tid_len, target, NULL, 0);
1641            break;
1642        case GET_PEERS:
1643            debugf("Get_peers!\n");
1644            new_node(s, id, &source, 1);
1645            if(id_cmp(info_hash, zeroes) == 0) {
1646                debugf("Eek!  Got get_peers with no info_hash.\n");
1647                break;
1648            } else {
1649                struct storage *st = find_storage(info_hash);
1650                if(st && st->numpeers > 0) {
1651                    int i0, n0, n1;
1652                    unsigned char token[TOKEN_SIZE];
1653                    make_token((unsigned char*)&source.sin_addr,
1654                               ntohs(source.sin_port),
1655                               0, token);
1656                    i0 = random() % st->numpeers;
1657                    /* We treat peers as a circular list, and choose 50
1658                       peers starting at i0. */
1659                    n0 = MIN(st->numpeers - i0, 50);
1660                    n1 = n0 >= 50 ? 0 : MIN(50, i0);
1661
1662                    debugf("Sending found peers (%d).\n", n0 + n1);
1663                    send_peers_found(s, (struct sockaddr*)&source,
1664                                     sizeof(source), tid, tid_len,
1665                                     st->peers + i0, n0,
1666                                     st->peers, n1,
1667                                     token, TOKEN_SIZE);
1668
1669                } else {
1670                    unsigned char token[TOKEN_SIZE];
1671                    make_token((unsigned char*)&source.sin_addr,
1672                               ntohs(source.sin_port),
1673                               0, token);
1674                    debugf("Sending nodes for get_peers.\n");
1675                    send_closest_nodes(s, (struct sockaddr*)&source,
1676                                       sizeof(source),
1677                                       tid, tid_len, info_hash,
1678                                       token, TOKEN_SIZE);
1679                }
1680            }
1681            break;
1682        case ANNOUNCE_PEER:
1683            debugf("Announce peer!\n");
1684            new_node(s, id, &source, 1);
1685            if(id_cmp(info_hash, zeroes) == 0) {
1686                debugf("Announce_peer with no info_hash.\n");
1687                break;
1688            }
1689            if(!token_match(token, token_len,
1690                            (unsigned char*)&source.sin_addr,
1691                            ntohs(source.sin_port))) {
1692                debugf("Incorrect token for announce_peer.\n");
1693                break;
1694            }
1695            if(port == 0) {
1696                debugf("Announce_peer with forbidden port %d.\n", port);
1697                break;
1698            }
1699            storage_store(info_hash,
1700                          (unsigned char*)&source.sin_addr, port);
1701            debugf("Sending peer announced.\n");
1702            send_peer_announced(s, (struct sockaddr*)&source,
1703                                sizeof(source), tid, tid_len);
1704        }
1705    }
1706
1707 dontread:
1708    if(now.tv_sec >= rotate_secrets_time)
1709        rotate_secrets();
1710
1711    if(now.tv_sec >= expire_stuff_time) {
1712        expire_buckets(s);
1713        expire_storage();
1714        expire_searches();
1715    }
1716
1717    if(search_time > 0 && now.tv_sec >= search_time) {
1718        struct search *sr;
1719        sr = searches;
1720        while(sr) {
1721            if(!sr->done && sr->step_time + 5 <= now.tv_sec) {
1722                search_step(s, sr, callback, closure);
1723            }
1724            sr = sr->next;
1725        }
1726                   
1727        search_time = 0;
1728
1729        sr = searches;
1730        while(sr) {
1731            if(!sr->done) {
1732                time_t tm = sr->step_time + 15 + random() % 10;
1733                if(search_time == 0 || search_time > tm)
1734                    search_time = tm;
1735            }
1736            sr = sr->next;
1737        }
1738    }
1739
1740    if(now.tv_sec >= confirm_nodes_time) {
1741        struct bucket *b;
1742        int soon = 0;
1743        b = buckets;
1744        while(!soon && b) {
1745            struct bucket *q;
1746            if(b->time < now.tv_sec - 900) {
1747                /* This bucket hasn't seen any activity for a long
1748                   time.  Pick a random id in this bucket's range, and
1749                   send a request to a random node. */
1750                unsigned char id[20];
1751                struct node *n;
1752                int rc;
1753               
1754                rc = bucket_random(b, id);
1755                if(rc < 0)
1756                    memcpy(id, b->first, 20);
1757               
1758                q = b;
1759                /* If the bucket is empty, we try to fill it from
1760                   a neighbour.  We also sometimes do it gratuitiously
1761                   to recover from buckets full of broken nodes. */
1762                if(q->next && (q->count == 0 || random() % 7 == 0))
1763                    q = b->next;
1764                if(q->count == 0 || random() % 7 == 0) {
1765                    struct bucket *r;
1766                    r = previous_bucket(b);
1767                    if(r && r->count > 0)
1768                        q = r;
1769                }
1770
1771                if(q) {
1772                    n = random_node(q);
1773                    if(n) {
1774                        unsigned char tid[4];
1775                        debugf("Sending find_node "
1776                               "for bucket maintenance.\n");
1777                        make_tid(tid, "fn", 0);
1778                        send_find_node(s, (struct sockaddr*)&n->sin,
1779                                       sizeof(struct sockaddr_in),
1780                                       tid, 4, id,
1781                                       n->reply_time >= now.tv_sec - 15);
1782                        pinged(s, n, q);
1783                        /* In order to avoid sending queries back-to-back,
1784                           give up for now and reschedule us soon. */
1785                        soon = 1;
1786                    }
1787                }
1788            }
1789            b = b->next;
1790        }
1791
1792        if(!soon && mybucket_grow_time >= now.tv_sec - 150) {
1793            /* We've seen updates to our own bucket recently.  Try to
1794               improve our neighbourship. */
1795            unsigned char id[20];
1796            struct bucket *b, *q;
1797            struct node *n;
1798           
1799            memcpy(id, myid, 20);
1800            id[19] = random() % 0xFF;
1801            b = find_bucket(myid);
1802            q = b;
1803            if(q->next && (q->count == 0 || random() % 7 == 0))
1804                q = b->next;
1805            if(q->count == 0 || random() % 7 == 0) {
1806                struct bucket *r;
1807                r = previous_bucket(b);
1808                if(r && r->count > 0)
1809                    q = r;
1810            }
1811
1812            if(q) {
1813                n = random_node(q);
1814                if(n) {
1815                    unsigned char tid[4];
1816                    debugf("Sending find_node "
1817                           "for neighborhood maintenance.\n");
1818                    make_tid(tid, "fn", 0);
1819                    send_find_node(s, (struct sockaddr*)&n->sin,
1820                                   sizeof(struct sockaddr_in),
1821                                   tid, 4, id,
1822                                   n->reply_time >= now.tv_sec - 15);
1823                    pinged(s, n, q);
1824                }
1825            }
1826            soon = 1;
1827        }
1828
1829        /* In order to maintain all buckets' age within 900 seconds, worst
1830           case is roughly 40 seconds, assuming the table is 22 bits deep.
1831           We want to keep a margin for neighborhood maintenance, so keep
1832           this within 30 seconds. */
1833        if(soon)
1834            confirm_nodes_time = now.tv_sec + 10 + random() % 20;
1835        else
1836            confirm_nodes_time = now.tv_sec + 60 + random() % 120;
1837    }
1838
1839    if(confirm_nodes_time > now.tv_sec)
1840        *tosleep = confirm_nodes_time - now.tv_sec;
1841    else
1842        *tosleep = 0;
1843
1844    if(search_time > 0) {
1845        if(search_time <= now.tv_sec)
1846            *tosleep = 0;
1847        else if(*tosleep > search_time - now.tv_sec)
1848            *tosleep = search_time - now.tv_sec;
1849    }
1850   
1851    return find_bucket(myid)->count > 2;
1852}
1853
1854int
1855dht_get_nodes(struct sockaddr_in *sins, int num)
1856{
1857    int i;
1858    struct bucket *b;
1859    struct node *n;
1860
1861    i = 0;
1862
1863    /* For restoring to work without discarding too many nodes, the list
1864       must start with the contents of our bucket. */
1865    b = find_bucket(myid);
1866    n = b->nodes;
1867    while(n && i < num) {
1868        if(node_good(n)) {
1869            sins[i] = n->sin;
1870            i++;
1871        }
1872        n = n->next;
1873    }
1874
1875    b = buckets;
1876    while(b && i < num) {
1877        if(!in_bucket(myid, b)) {
1878            n = b->nodes;
1879            while(n && i < num) {
1880                if(node_good(n)) {
1881                    sins[i] = n->sin;
1882                    i++;
1883                }
1884                n = n->next;
1885            }
1886        }
1887        b = b->next;
1888    }
1889    return i;
1890}
1891
1892int
1893dht_insert_node(int s, const unsigned char *id, struct sockaddr_in *sin)
1894{
1895    struct node *n;
1896    n = new_node(s, id, sin, 0);
1897    return !!n;
1898}
1899
1900int
1901dht_ping_node(int s, struct sockaddr_in *sin)
1902{
1903    unsigned char tid[4];
1904    debugf("Sending ping.\n");
1905    make_tid(tid, "pn", 0);
1906    return send_ping(s, (struct sockaddr*)sin, sizeof(struct sockaddr_in),
1907                     tid, 4);
1908}
1909
1910/* We could use a proper bencoding printer and parser, but the format of
1911   DHT messages is fairly stylised, so this seemed simpler. */
1912
1913#define CHECK(offset, delta, size)                      \
1914    if(delta < 0 || offset + delta > size) goto fail
1915
1916#define INC(offset, delta, size)                        \
1917    CHECK(offset, delta, size);                         \
1918    offset += delta
1919
1920#define COPY(buf, offset, src, delta, size)             \
1921    CHECK(offset, delta, size);                         \
1922    memcpy(buf + offset, src, delta);                   \
1923    i += delta;
1924
1925#define ADD_V(buf, offset, size)                        \
1926    if(have_v) {                                        \
1927        COPY(buf, offset, my_v, sizeof(my_v), size);    \
1928    }
1929
1930int
1931send_ping(int s, struct sockaddr *sa, int salen,
1932          const unsigned char *tid, int tid_len)
1933{
1934    char buf[512];
1935    int i = 0, rc;
1936    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
1937    COPY(buf, i, myid, 20, 512);
1938    rc = snprintf(buf + i, 512 - i, "e1:q4:ping1:t%d:", tid_len);
1939    INC(i, rc, 512);
1940    COPY(buf, i, tid, tid_len, 512);
1941    ADD_V(buf, i, 512);
1942    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
1943    return sendto(s, buf, i, 0, sa, salen);
1944
1945 fail:
1946    errno = ENOSPC;
1947    return -1;
1948}
1949
1950int
1951send_pong(int s, struct sockaddr *sa, int salen,
1952          const unsigned char *tid, int tid_len)
1953{
1954    char buf[512];
1955    int i = 0, rc;
1956    rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512);
1957    COPY(buf, i, myid, 20, 512);
1958    rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
1959    COPY(buf, i, tid, tid_len, 512);
1960    ADD_V(buf, i, 512);
1961    rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512);
1962    return sendto(s, buf, i, 0, sa, salen);
1963
1964 fail:
1965    errno = ENOSPC;
1966    return -1;
1967}
1968
1969int
1970send_find_node(int s, struct sockaddr *sa, int salen,
1971               const unsigned char *tid, int tid_len,
1972               const unsigned char *target, int confirm)
1973{
1974    char buf[512];
1975    int i = 0, rc;
1976    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
1977    COPY(buf, i, myid, 20, 512);
1978    rc = snprintf(buf + i, 512 - i, "6:target20:"); INC(i, rc, 512);
1979    COPY(buf, i, target, 20, 512);
1980    rc = snprintf(buf + i, 512 - i, "e1:q9:find_node1:t%d:", tid_len);
1981    INC(i, rc, 512);
1982    COPY(buf, i, tid, tid_len, 512);
1983    ADD_V(buf, i, 512);
1984    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
1985    return sendto(s, buf, i, confirm ? MSG_CONFIRM : 0, sa, salen);
1986
1987 fail:
1988    errno = ENOSPC;
1989    return -1;
1990}
1991
1992int
1993send_found_nodes(int s, struct sockaddr *sa, int salen,
1994                 const unsigned char *tid, int tid_len,
1995                 const unsigned char *nodes, int nodes_len,
1996                 const unsigned char *token, int token_len)
1997{
1998    char buf[2048];
1999    int i = 0, rc;
2000    rc = snprintf(buf + i, 2048 - i, "d1:rd2:id20:"); INC(i, rc, 2048);
2001    COPY(buf, i, myid, 20, 2048);
2002    if(nodes) {
2003        rc = snprintf(buf + i, 2048 - i, "5:nodes%d:", nodes_len);
2004        INC(i, rc, 2048);
2005        COPY(buf, i, nodes, nodes_len, 2048);
2006    }
2007    if(token) {
2008        rc = snprintf(buf + i, 2048 - i, "5:token%d:", token_len);
2009        INC(i, rc, 2048);
2010        COPY(buf, i, token, token_len, 2048);
2011    }
2012    rc = snprintf(buf + i, 2048 - i, "e1:t%d:", tid_len); INC(i, rc, 2048);
2013    COPY(buf, i, tid, tid_len, 2048);
2014    ADD_V(buf, i, 2048);
2015    rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048);
2016
2017    return sendto(s, buf, i, 0, sa, salen);
2018
2019 fail:
2020    errno = ENOSPC;
2021    return -1;
2022}
2023
2024static int
2025insert_closest_node(unsigned char *nodes, int numnodes,
2026                    const unsigned char *id, struct node *n)
2027{
2028    int i;
2029    for(i = 0; i< numnodes; i++) {
2030        if(id_cmp(nodes + 26 * i, id) == 0)
2031            return numnodes;
2032        if(xorcmp(n->id, nodes + 26 * i, id) < 0)
2033            break;
2034    }
2035
2036    if(i == 8)
2037        return numnodes;
2038
2039    if(numnodes < 8)
2040        numnodes++;
2041
2042    if(i < numnodes - 1)
2043        memmove(nodes + 26 * (i + 1), nodes + 26 * i, 26 * (numnodes - i - 1));
2044
2045    memcpy(nodes + 26 * i, n->id, 20);
2046    memcpy(nodes + 26 * i + 20, &n->sin.sin_addr, 4);
2047    memcpy(nodes + 26 * i + 24, &n->sin.sin_port, 2);
2048
2049    return numnodes;
2050}
2051
2052static int
2053buffer_closest_nodes(unsigned char *nodes, int numnodes,
2054                     const unsigned char *id, struct bucket *b)
2055{
2056    struct node *n = b->nodes;
2057    while(n) {
2058        if(node_good(n))
2059            numnodes = insert_closest_node(nodes, numnodes, id, n);
2060        n = n->next;
2061    }
2062    return numnodes;
2063}
2064
2065int
2066send_closest_nodes(int s, struct sockaddr *sa, int salen,
2067                   const unsigned char *tid, int tid_len,
2068                   const unsigned char *id,
2069                   const unsigned char *token, int token_len)
2070{
2071    unsigned char nodes[8 * 26];
2072    int numnodes = 0;
2073    struct bucket *b;
2074
2075    b = find_bucket(id);
2076    numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
2077    if(b->next)
2078        numnodes = buffer_closest_nodes(nodes, numnodes, id, b->next);
2079    b = previous_bucket(b);
2080    if(b)
2081        numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
2082
2083    return send_found_nodes(s, sa, salen, tid, tid_len,
2084                            nodes, numnodes * 26,
2085                            token, token_len);
2086}
2087
2088int
2089send_get_peers(int s, struct sockaddr *sa, int salen,
2090               unsigned char *tid, int tid_len, unsigned char *infohash,
2091               int confirm)
2092{
2093    char buf[512];
2094    int i = 0, rc;
2095
2096    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
2097    COPY(buf, i, myid, 20, 512);
2098    rc = snprintf(buf + i, 512 - i, "9:info_hash20:"); INC(i, rc, 512);
2099    COPY(buf, i, infohash, 20, 512);
2100    rc = snprintf(buf + i, 512 - i, "e1:q9:get_peers1:t%d:", tid_len);
2101    INC(i, rc, 512);
2102    COPY(buf, i, tid, tid_len, 512);
2103    ADD_V(buf, i, 512);
2104    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
2105    return sendto(s, buf, i, confirm ? MSG_CONFIRM : 0, sa, salen);
2106
2107 fail:
2108    errno = ENOSPC;
2109    return -1;
2110}
2111
2112int
2113send_announce_peer(int s, struct sockaddr *sa, int salen,
2114                   unsigned char *tid, int tid_len,
2115                   unsigned char *infohash, unsigned short port,
2116                   unsigned char *token, int token_len, int confirm)
2117{
2118    char buf[512];
2119    int i = 0, rc;
2120
2121    rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
2122    COPY(buf, i, myid, 20, 512);
2123    rc = snprintf(buf + i, 512 - i, "9:info_hash20:"); INC(i, rc, 512);
2124    COPY(buf, i, infohash, 20, 512);
2125    rc = snprintf(buf + i, 512 - i, "4:porti%ue5:token%d:", (unsigned)port,
2126                  token_len);
2127    INC(i, rc, 512);
2128    COPY(buf, i, token, token_len, 512);
2129    rc = snprintf(buf + i, 512 - i, "e1:q13:announce_peer1:t%d:", tid_len);
2130    INC(i, rc, 512);
2131    COPY(buf, i, tid, tid_len, 512);
2132    ADD_V(buf, i, 512);
2133    rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
2134
2135    return sendto(s, buf, i, confirm ? 0 : MSG_CONFIRM, sa, salen);
2136
2137 fail:
2138    errno = ENOSPC;
2139    return -1;
2140}
2141
2142int
2143send_peers_found(int s, struct sockaddr *sa, int salen,
2144                 unsigned char *tid, int tid_len,
2145                 struct peer *peers1, int numpeers1,
2146                 struct peer *peers2, int numpeers2,
2147                 unsigned char *token, int token_len)
2148{
2149    char buf[1400];
2150    int i = 0, rc, j;
2151
2152    rc = snprintf(buf + i, 1400 - i, "d1:rd2:id20:"); INC(i, rc, 1400);
2153    COPY(buf, i, myid, 20, 1400);
2154    rc = snprintf(buf + i, 1400 - i, "5:token%d:", token_len); INC(i, rc, 1400);
2155    COPY(buf, i, token, token_len, 1400);
2156    rc = snprintf(buf + i, 1400 - i, "6:valuesl"); INC(i, rc, 1400);
2157    for(j = 0; j < numpeers1; j++) {
2158        unsigned short swapped = htons(peers1[j].port);
2159        rc = snprintf(buf + i, 1400 - i, "6:"); INC(i, rc, 1400);
2160        COPY(buf, i, peers1[j].ip, 4, 1400);
2161        COPY(buf, i, &swapped, 2, 1400);
2162    }
2163    for(j = 0; j < numpeers2; j++) {
2164        unsigned short swapped = htons(peers2[j].port);
2165        rc = snprintf(buf + i, 1400 - i, "6:"); INC(i, rc, 1400);
2166        COPY(buf, i, peers2[j].ip, 4, 1400);
2167        COPY(buf, i, &swapped, 2, 1400);
2168    }
2169    rc = snprintf(buf + i, 1400 - i, "ee1:t%d:", tid_len);
2170    INC(i, rc, 1400);
2171    COPY(buf, i, tid, tid_len, 1400);
2172    ADD_V(buf, i, 512);
2173    rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048);
2174    return sendto(s, buf, i, 0, sa, salen);
2175
2176 fail:
2177    errno = ENOSPC;
2178    return -1;
2179}
2180
2181int
2182send_peer_announced(int s, struct sockaddr *sa, int salen,
2183                    unsigned char *tid, int tid_len)
2184{
2185    char buf[512];
2186    int i = 0, rc;
2187
2188    rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512);
2189    COPY(buf, i, myid, 20, 512);
2190    rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len);
2191    INC(i, rc, 512);
2192    COPY(buf, i, tid, tid_len, 512);
2193    ADD_V(buf, i, 2048);
2194    rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048);
2195    return sendto(s, buf, i, 0, sa, salen);
2196
2197 fail:
2198    errno = ENOSPC;
2199    return -1;
2200}
2201
2202#undef CHECK
2203#undef INC
2204#undef COPY
2205#undef ADD_V
2206
2207#ifndef HAVE_MEMMEM
2208static void *
2209memmem(const void *haystack, size_t haystacklen,
2210       const void *needle, size_t needlelen)
2211{
2212    const char *h = haystack;
2213    const char *n = needle;
2214    size_t i;
2215
2216    /* size_t is unsigned */
2217    if(needlelen > haystacklen)
2218        return NULL;
2219
2220    for(i = 0; i <= haystacklen - needlelen; i++) {
2221        if(memcmp(h + i, n, needlelen) == 0)
2222            return (void*)(h + i);
2223    }
2224    return NULL;
2225}
2226#endif
2227
2228static int
2229parse_message(const unsigned char *buf, int buflen,
2230              unsigned char *tid_return, int *tid_len,
2231              unsigned char *id_return, unsigned char *info_hash_return,
2232              unsigned char *target_return, unsigned short *port_return,
2233              unsigned char *token_return, int *token_len,
2234              unsigned char *nodes_return, int *nodes_len,
2235              const unsigned char *values_return, int *values_len)
2236{
2237    const unsigned char *p;
2238
2239#define CHECK(ptr, len)                                                 \
2240    if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow;
2241
2242    if(tid_return) {
2243        p = memmem(buf, buflen, "1:t", 3);
2244        if(p) {
2245            long l;
2246            char *q;
2247            l = strtol((char*)p + 3, &q, 10);
2248            if(q && *q == ':' && l > 0 && l < *tid_len) {
2249                CHECK(q + 1, l);
2250                memcpy(tid_return, q + 1, l);
2251                *tid_len = l;
2252            } else
2253                *tid_len = 0;
2254        }
2255    }
2256    if(id_return) {
2257        p = memmem(buf, buflen, "2:id20:", 7);
2258        if(p) {
2259            CHECK(p + 7, 20);
2260            memcpy(id_return, p + 7, 20);
2261        } else {
2262            memset(id_return, 0, 20);
2263        }
2264    }
2265    if(info_hash_return) {
2266        p = memmem(buf, buflen, "9:info_hash20:", 14);
2267        if(p) {
2268            CHECK(p + 14, 20);
2269            memcpy(info_hash_return, p + 14, 20);
2270        } else {
2271            memset(info_hash_return, 0, 20);
2272        }
2273    }
2274    if(port_return) {
2275        p = memmem(buf, buflen, "porti", 5);
2276        if(p) {
2277            long l;
2278            char *q;
2279            l = strtol((char*)p + 5, &q, 10);
2280            if(q && *q == 'e' && l > 0 && l < 0x10000)
2281                *port_return = l;
2282            else
2283                *port_return = 0;
2284        } else
2285            *port_return = 0;
2286    }
2287    if(target_return) {
2288        p = memmem(buf, buflen, "6:target20:", 11);
2289        if(p) {
2290            CHECK(p + 11, 20);
2291            memcpy(target_return, p + 11, 20);
2292        } else {
2293            memset(target_return, 0, 20);
2294        }
2295    }
2296    if(token_return) {
2297        p = memmem(buf, buflen, "5:token", 7);
2298        if(p) {
2299            long l;
2300            char *q;
2301            l = strtol((char*)p + 7, &q, 10);
2302            if(q && *q == ':' && l > 0 && l < *token_len) {
2303                CHECK(q + 1, l);
2304                memcpy(token_return, q + 1, l);
2305                *token_len = l;
2306            } else
2307                *token_len = 0;
2308        } else
2309            *token_len = 0;
2310    }
2311       
2312    if(nodes_return) {
2313        p = memmem(buf, buflen, "5:nodes", 7);
2314        if(p) {
2315            long l;
2316            char *q;
2317            l = strtol((char*)p + 7, &q, 10);
2318            if(q && *q == ':' && l > 0 && l < *nodes_len) {
2319                CHECK(q + 1, l);
2320                memcpy(nodes_return, q + 1, l);
2321                *nodes_len = l;
2322            } else
2323                *nodes_len = 0;
2324        } else
2325            *nodes_len = 0;
2326    }
2327
2328    if(values_return) {
2329        p = memmem(buf, buflen, "6:valuesl", 9);
2330        if(p) {
2331            int i = p - buf + 9;
2332            int j = 0;
2333            while(buf[i] == '6' && buf[i + 1] == ':' && i + 8 < buflen) {
2334                if(j + 6 > *values_len)
2335                    break;
2336                CHECK(buf + i + 2, 6);
2337                memcpy((char*)values_return + j, buf + i + 2, 6);
2338                i += 8;
2339                j += 6;
2340            }
2341            if(i >= buflen || buf[i] != 'e')
2342                debugf("eek... unexpected end for values.\n");
2343            *values_len = j;
2344        } else {
2345            *values_len = 0;
2346        }
2347    }
2348
2349#undef CHECK
2350               
2351    if(memmem(buf, buflen, "1:y1:r", 6))
2352        return REPLY;
2353    if(!memmem(buf, buflen, "1:y1:q", 6))
2354        return -1;
2355    if(memmem(buf, buflen, "1:q4:ping", 9))
2356        return PING;
2357    if(memmem(buf, buflen, "1:q9:find_node", 14))
2358       return FIND_NODE;
2359    if(memmem(buf, buflen, "1:q9:get_peers", 14))
2360        return GET_PEERS;
2361    if(memmem(buf, buflen, "1:q13:announce_peer", 19))
2362       return ANNOUNCE_PEER;
2363    return -1;
2364
2365 overflow:
2366    debugf("Truncated message.\n");
2367    return -1;
2368}
Note: See TracBrowser for help on using the repository browser.