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

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

(trunk third-party) #2302: revert from dht 0.8 to 0.6 for Transmission 1.74. 0.8 reportedly adds a new crasher <http://forum.transmissionbt.com/viewtopic.php?p=39773#p39773>

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