Changeset 8482


Ignore:
Timestamp:
May 22, 2009, 4:45:41 PM (12 years ago)
Author:
charles
Message:

(trunk) #7: update to upstream dht-0.6

Location:
trunk/third-party/dht
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/third-party/dht/CHANGES

    r8440 r8482  
     122 May 2009: dht-0.6
     2
     3  * Fixed a buffer overflow (when reading) in parse_message.
     4  * Fixed slightly inacurrate metric computation when searching.
     5  * Removed a slightly inaccurate shortcut when responding to find_nodes.
     6  * Relaxed the rate-limiting parameters to 4 requests per second.
     7
    1819 May 2009: dht-0.5
    29
  • trunk/third-party/dht/dht-example.c

    r8440 r8482  
    156156
    157157        i++;
     158        if(i >= argc)
     159            goto usage;
    158160
    159161        infop = info;
     
    173175    }
    174176
    175     if(i < argc)
    176         goto usage;
    177 
    178177    /* If you set dht_debug to a stream, every action taken by the DHT will
    179178       be logged. */
  • trunk/third-party/dht/dht.c

    r8478 r8482  
    110110
    111111/* When performing a search, we search for up to SEARCH_NODES closest nodes
    112    to the destinatin, and use the additional ones to backtrack if any of
     112   to the destination, and use the additional ones to backtrack if any of
    113113   the target 8 turn out to be dead. */
    114114#define SEARCH_NODES 14
     
    154154                            const unsigned char *nodes, int nodes_len,
    155155                            const unsigned char *token, int token_len);
    156 static int send_bucket_nodes(int s, struct sockaddr *sa, int salen,
    157                              const unsigned char *tid, int tid_len,
    158                              struct bucket *b,
    159                              const unsigned char *token, int token_len);
     156static int send_closest_nodes(int s, struct sockaddr *sa, int salen,
     157                              const unsigned char *tid, int tid_len,
     158                              const unsigned char *id,
     159                              const unsigned char *token, int token_len);
    160160static int send_get_peers(int s, struct sockaddr *sa, int salen,
    161161                          unsigned char *tid, int tid_len,
     
    318318
    319319    return 8 * i + j;
     320}
     321
     322/* Determine whether id1 or id2 is closer to ref */
     323int
     324xorcmp(const unsigned char *id1, const unsigned char *id2,
     325       const unsigned char *ref)
     326{
     327    int i;
     328    for(i = 0; i < 20; i++) {
     329        unsigned char xor1, xor2;
     330        if(id1[i] == id2[i])
     331            continue;
     332        xor1 = id1[i] ^ ref[i];
     333        xor2 = id2[i] ^ ref[i];
     334        if(xor1 < xor2)
     335            return -1;
     336        else
     337            return 1;
     338    }
     339    return 0;
    320340}
    321341
     
    584604    n = b->nodes;
    585605    while(n) {
    586         if(n->pinged >= 3) {
     606        if(n->pinged >= 3 && n->pinged_time < now.tv_sec - 15) {
    587607            memcpy(n->id, id, 20);
    588608            n->sin = *sin;
     
    605625            /* Pick the first dubious node that we haven't pinged in the
    606626               last 15 seconds.  This gives nodes the time to reply, but
    607                tends to concentrate on the same nodes. */
     627               tends to concentrate on the same nodes, so that we get rid
     628               of bad nodes fast. */
    608629            if(!node_good(n)) {
    609630                dubious = 1;
     
    720741                   unsigned char *token, int token_len)
    721742{
    722     int bits = common_bits(id, sr->id);
    723743    struct search_node *n;
    724744    int i, j;
     
    729749            goto found;
    730750        }
    731         if(common_bits(sr->id, sr->nodes[i].id) < bits)
     751        if(xorcmp(id, sr->nodes[i].id, sr->id) < 0)
    732752            break;
    733753    }
     
    15581578            debugf("Find node!\n");
    15591579            new_node(s, id, &source, 1);
    1560             {
    1561                 struct bucket *b = find_bucket(target);
    1562                 if(b) {
    1563                     debugf("Sending nodes from bucket.\n");
    1564                     send_bucket_nodes(s,
    1565                                       (struct sockaddr*)&source,
    1566                                       sizeof(source),
    1567                                       tid, tid_len, b, NULL, 0);
    1568                 }
    1569             }
     1580            debugf("Sending closest nodes.\n");
     1581            send_closest_nodes(s, (struct sockaddr*)&source, sizeof(source),
     1582                               tid, tid_len, target, NULL, 0);
    15701583            break;
    15711584        case GET_PEERS:
     
    15971610
    15981611                } else {
    1599                     struct bucket *b = find_bucket(info_hash);
    1600                     if(b) {
    1601                         unsigned char token[TOKEN_SIZE];
    1602                         make_token((unsigned char*)&source.sin_addr,
    1603                                    ntohs(source.sin_port),
    1604                                    0, token);
    1605                         debugf("Sending nodes for get_peers.\n");
    1606                         send_bucket_nodes(s, (struct sockaddr*)&source,
    1607                                           sizeof(source),
    1608                                           tid, tid_len, b,
    1609                                           token, TOKEN_SIZE);
    1610                     }
     1612                    unsigned char token[TOKEN_SIZE];
     1613                    make_token((unsigned char*)&source.sin_addr,
     1614                               ntohs(source.sin_port),
     1615                               0, token);
     1616                    debugf("Sending nodes for get_peers.\n");
     1617                    send_closest_nodes(s, (struct sockaddr*)&source,
     1618                                       sizeof(source),
     1619                                       tid, tid_len, info_hash,
     1620                                       token, TOKEN_SIZE);
    16111621                }
    16121622            }
     
    19521962
    19531963static int
    1954 buffer_bucket(unsigned char *buf, int bufsize, struct bucket *b)
    1955 {
    1956     int i = 0;
     1964insert_closest_node(unsigned char *nodes, int numnodes,
     1965                    const unsigned char *id, struct node *n)
     1966{
     1967    int i;
     1968    for(i = 0; i< numnodes; i++) {
     1969        if(id_cmp(nodes + 26 * i, id) == 0)
     1970            return numnodes;
     1971        if(xorcmp(n->id, nodes + 26 * i, id) < 0)
     1972            break;
     1973    }
     1974
     1975    if(i == 8)
     1976        return numnodes;
     1977
     1978    if(numnodes < 8)
     1979        numnodes++;
     1980
     1981    if(i < numnodes - 1)
     1982        memmove(nodes + 26 * (i + 1), nodes + 26 * i, 26 * (numnodes - i - 1));
     1983
     1984    memcpy(nodes + 26 * i, n->id, 20);
     1985    memcpy(nodes + 26 * i + 20, &n->sin.sin_addr, 4);
     1986    memcpy(nodes + 26 * i + 24, &n->sin.sin_port, 2);
     1987
     1988    return numnodes;
     1989}
     1990
     1991static int
     1992buffer_closest_nodes(unsigned char *nodes, int numnodes,
     1993                     const unsigned char *id, struct bucket *b)
     1994{
    19571995    struct node *n = b->nodes;
    1958     while(n && i < bufsize - 26) {
    1959         if(node_good(n)) {
    1960             memcpy(buf + i, n->id, 20);
    1961             memcpy(buf + i + 20, &n->sin.sin_addr, 4);
    1962             memcpy(buf + i + 24, &n->sin.sin_port, 2);
    1963             i += 26;
    1964         }
     1996    while(n) {
     1997        if(node_good(n))
     1998            numnodes = insert_closest_node(nodes, numnodes, id, n);
    19651999        n = n->next;
    19662000    }
    1967     return i;
     2001    return numnodes;
    19682002}
    19692003
    19702004int
    1971 send_bucket_nodes(int s, struct sockaddr *sa, int salen,
    1972                   const unsigned char *tid, int tid_len,
    1973                   struct bucket *b,
    1974                   const unsigned char *token, int token_len)
     2005send_closest_nodes(int s, struct sockaddr *sa, int salen,
     2006                   const unsigned char *tid, int tid_len,
     2007                   const unsigned char *id,
     2008                   const unsigned char *token, int token_len)
    19752009{
    19762010    unsigned char nodes[8 * 26];
    1977     int nodeslen = 0;
    1978 
    1979     nodeslen = buffer_bucket(nodes, 8 * 26, b);
     2011    int numnodes = 0;
     2012    struct bucket *b;
     2013
     2014    b = find_bucket(id);
     2015    numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
     2016    if(b->next)
     2017        numnodes = buffer_closest_nodes(nodes, numnodes, id, b->next);
     2018    b = previous_bucket(b);
     2019    if(b)
     2020        numnodes = buffer_closest_nodes(nodes, numnodes, id, b);
     2021
    19802022    return send_found_nodes(s, sa, salen, tid, tid_len,
    1981                             nodes, nodeslen,
     2023                            nodes, numnodes * 26,
    19822024                            token, token_len);
    19832025}
     
    21112153    size_t i;
    21122154
     2155    /* size_t is unsigned */
    21132156    if(needlelen > haystacklen)
    21142157        return NULL;
Note: See TracChangeset for help on using the changeset viewer.