Changeset 9145


Ignore:
Timestamp:
Sep 19, 2009, 6:09:57 PM (13 years ago)
Author:
charles
Message:

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

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

Legend:

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

    r8985 r9145  
     1dht-0.9 (unreleased):
     2
     3  * Fixed incorrect computation of number of nodes.
     4  * Made the initial bucket split more eagerly.
     5
     628 July 2009: dht-0.8
     7
     8  * Fixed a crash when expiring the first search on the list.
     9  * Fixed freeing of the search list when uniniting with dofree = 1.
     10
     1124 June 2009: dht-0.7
     12
     13  * Removed the fixed limit on the number of concurrent searches, we now
     14    use a linked list.
     15  * Fixed build on FreeBSD (thanks to Humihara and Charles Kerr).
     16
    11722 May 2009: dht-0.6
    218
  • trunk/third-party/dht/README

    r8985 r9145  
    9494This schedules a search for information about the info-hash specified in
    9595id.  If port is not 0, it specifies the TCP port on which the current peer
    96 is litening; in that case, when the search is complete it will be announced
     96is listening; in that case, when the search is complete it will be announced
    9797to the network.  The port is in host order, beware if you got it from
    9898a struct sockaddr_in.
     
    102102additionally be called when the search is complete.
    103103
    104 Up to DHT_MAX_SEARCHES (20) searches can be in progress at a given time;
     104Up to DHT_MAX_SEARCHES (1024) searches can be in progress at a given time;
    105105any more, and dht_search will return -1.  If you specify a new search for
    106106the same info hash as a search still in progress, the previous search is
     
    124124firewalled.
    125125
    126 If you want to display a single figure to the user, you should display good
    127 + doubtful, which is the total number of nodes in your routing table.  Some
    128 clients try to estimate the total number of nodes, but this doesn't make
    129 much sense -- since the result is exponential in the number of nodes in the
    130 routing table, small variations in the latter cause huge jumps in the
    131 former.
     126If you want to display a single figure to the user, you should display
     127good + doubtful, which is the total number of nodes in your routing table.
     128Some clients try to estimate the total number of nodes, but this doesn't
     129make much sense -- since the result is exponential in the number of nodes
     130in the routing table, small variations in the latter cause huge jumps in
     131the former.
    132132
    133133* dht_get_nodes
     
    187187keep both pieces.
    188188
    189 There is currently no good way to save and restore your routing table.
    190 
    191189IPv6 support is deliberately not included: designing a double-stack
    192190distributed hash table raises some tricky issues, and doing it naively may
  • trunk/third-party/dht/dht.c

    r8985 r9145  
    123123    struct search_node nodes[SEARCH_NODES];
    124124    int numnodes;
     125    struct search *next;
    125126};
    126127
     
    134135#ifndef DHT_MAX_PEERS
    135136#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)
    136147#endif
    137148
     
    208219static struct storage *storage;
    209220
    210 /* The maximum number of concurrent searches. */
    211 #ifndef DHT_MAX_SEARCHES
    212 #define DHT_MAX_SEARCHES 20
    213 #endif
    214 
    215 static struct search searches[DHT_MAX_SEARCHES];
     221static struct search *searches = NULL;
    216222static int numsearches;
    217223static unsigned short search_id;
     
    645651            n = n->next;
    646652        }
    647        
    648         if(!dubious && mybucket) {
     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)) {
    649657            debugf("Splitting.\n");
    650658            b = split_bucket(s, b);
     
    725733find_search(unsigned short tid)
    726734{
    727     int i;
    728     for(i = 0; i < numsearches; i++) {
    729         if(searches[i].tid == tid)
    730             return &searches[i];
     735    struct search *sr = searches;
     736    while(sr) {
     737        if(sr->tid == tid)
     738            return sr;
     739        sr = sr->next;
    731740    }
    732741    return NULL;
     
    797806        sr->nodes[j] = sr->nodes[j + 1];
    798807    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    }
    799829}
    800830
     
    910940
    911941static struct search *
    912 find_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;
     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;
    926972}
    927973
     
    946992    struct search *sr;
    947993    struct bucket *b;
    948     int i;
    949 
    950     for(i = 0; i < numsearches; i++) {
    951         if(id_cmp(searches[i].id, id) == 0)
     994
     995    sr = searches;
     996    while(sr) {
     997        if(id_cmp(sr->id, id) == 0)
    952998            break;
    953     }
    954 
    955     if(i < numsearches) {
     999        sr = sr->next;
     1000    }
     1001
     1002    if(sr) {
    9561003        /* We're reusing data from an old search.  Reusing the same tid
    9571004           means that we can merge replies for both searches. */
    958         int j;
    959         sr = searches + i;
     1005        int i;
    9601006        sr->done = 0;
    9611007    again:
    962         for(j = 0; j < sr->numnodes; j++) {
     1008        for(i = 0; i < sr->numnodes; i++) {
    9631009            struct search_node *n;
    964             n = &sr->nodes[j];
     1010            n = &sr->nodes[i];
    9651011            /* Discard any doubtful nodes. */
    9661012            if(n->pinged >= 3 || n->reply_time < now.tv_sec - 7200) {
     
    9741020        }
    9751021    } else {
    976         sr = find_free_search_slot();
     1022        sr = new_search();
    9771023        if(sr == NULL) {
    9781024            errno = ENOSPC;
    9791025            return -1;
    9801026        }
    981         memset(sr, 0, sizeof(struct search));
    9821027        sr->tid = search_id++;
     1028        sr->step_time = 0;
    9831029        memcpy(sr->id, id, 20);
     1030        sr->done = 0;
    9841031        sr->numnodes = 0;
    9851032    }
     
    9901037    insert_search_bucket(b, sr);
    9911038
    992     if(sr->numnodes < 8) {
     1039    if(sr->numnodes < SEARCH_NODES) {
    9931040        struct bucket *p = previous_bucket(b);
    9941041        if(b->next)
     
    11081155broken_node(int s, const unsigned char *id, struct sockaddr_in *sin)
    11091156{
    1110     int i, j;
     1157    int i;
    11111158
    11121159    debugf("Blacklisting broken node.\n");
    11131160
    11141161    if(id) {
     1162        struct node *n;
     1163        struct search *sr;
    11151164        /* Make the node easy to discard. */
    1116         struct node *n;
    11171165        n = find_node(id);
    11181166        if(n) {
     
    11211169        }
    11221170        /* 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]);
     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;
    11281177        }
    11291178    }
     
    12071256        *cached_return = cached;
    12081257    if(incoming_return)
    1209         *incoming_return = cached;
     1258        *incoming_return = incoming;
    12101259    return good + dubious;
    12111260}
     
    12151264dht_dump_tables(FILE *f)
    12161265{
    1217     int i, j;
     1266    int i;
    12181267    struct bucket *b = buckets;
    12191268    struct storage *st = storage;
     1269    struct search *sr = searches;
    12201270
    12211271    fprintf(f, "My id ");
     
    12511301        b = b->next;
    12521302    }
    1253     for(i = 0; i < numsearches; i++) {
    1254         struct search *sr = &searches[i];
    1255         fprintf(f, "\nSearch %d id ", i);
     1303    while(sr) {
     1304        fprintf(f, "\nSearch id ");
    12561305        print_hex(f, sr->id, 20);
    12571306        fprintf(f, " age %d%s\n", (int)(now.tv_sec - sr->step_time),
    12581307               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);
     1308        for(i = 0; i < sr->numnodes; i++) {
     1309            struct search_node *n = &sr->nodes[i];
     1310            fprintf(f, "Node %d id ", i);
    12621311            print_hex(f, n->id, 20);
    12631312            fprintf(f, " bits %d age ", common_bits(sr->id, n->id));
     
    12711320                   n->replied ? " (replied)" : "");
    12721321        }
     1322        sr = sr->next;
    12731323    }
    12741324
     
    13061356        return -1;
    13071357
     1358    searches = NULL;
    13081359    numsearches = 0;
    13091360
     
    13781429        free(st);
    13791430    }
    1380    
     1431
     1432    while(searches) {
     1433        struct search *sr = searches;
     1434        searches = searches->next;
     1435        free(sr);
     1436    }
     1437
    13811438    return 1;
    13821439}
     
    15471604                sr = find_search(ttid);
    15481605                if(!sr) {
    1549                     debugf("Unknown search!");
     1606                    debugf("Unknown search!\n");
    15501607                    new_node(s, id, &source, 1);
    15511608                } else {
     
    15721629            debugf("Ping (%d)!\n", tid_len);
    15731630            new_node(s, id, &source, 1);
    1574             debugf("Sending pong!\n");
     1631            debugf("Sending pong.\n");
    15751632            send_pong(s, (struct sockaddr*)&source, sizeof(source),
    15761633                      tid, tid_len);
     
    16551712        expire_buckets(s);
    16561713        expire_storage();
     1714        expire_searches();
    16571715    }
    16581716
    16591717    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];
     1718        struct search *sr;
     1719        sr = searches;
     1720        while(sr) {
    16631721            if(!sr->done && sr->step_time + 5 <= now.tv_sec) {
    16641722                search_step(s, sr, callback, closure);
    16651723            }
     1724            sr = sr->next;
    16661725        }
    16671726                   
    16681727        search_time = 0;
    1669        
    1670         for(i = 0; i < numsearches; i++) {
    1671             struct search *sr = &searches[i];
     1728
     1729        sr = searches;
     1730        while(sr) {
    16721731            if(!sr->done) {
    16731732                time_t tm = sr->step_time + 15 + random() % 10;
     
    16751734                    search_time = tm;
    16761735            }
     1736            sr = sr->next;
    16771737        }
    16781738    }
Note: See TracChangeset for help on using the changeset viewer.