Changeset 8860


Ignore:
Timestamp:
Jul 29, 2009, 3:06:18 AM (13 years ago)
Author:
charles
Message:

(trunk third-party) #2302: upgrade from dht 0.6 to 0.8.

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

Legend:

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

    r8783 r8860  
     128 July 2009: dht-0.8
     2
     3  * Fixed a crash when expiring the first search on the list.
     4  * Fixed freeing of the search list when uniniting with dofree = 1.
     5
     624 June 2009: dht-0.7
     7
     8  * Removed the fixed limit on the number of concurrent searches, we now
     9    use a linked list.
     10  * Fixed build on FreeBSD (thanks to Humihara and Charles Kerr).
     11
    11222 May 2009: dht-0.6
    213
  • trunk/third-party/dht/README

    r8440 r8860  
    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

    r8783 r8860  
    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;
     
    725731find_search(unsigned short tid)
    726732{
    727     int i;
    728     for(i = 0; i < numsearches; i++) {
    729         if(searches[i].tid == tid)
    730             return &searches[i];
     733    struct search *sr = searches;
     734    while(sr) {
     735        if(sr->tid == tid)
     736            return sr;
     737        sr = sr->next;
    731738    }
    732739    return NULL;
     
    797804        sr->nodes[j] = sr->nodes[j + 1];
    798805    sr->numnodes--;
     806}
     807
     808static void
     809expire_searches(void)
     810{
     811    struct search *sr = searches, *previous = NULL;
     812
     813    while(sr) {
     814        struct search *next = sr->next;
     815        if(sr->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME) {
     816            if(previous)
     817                previous->next = next;
     818            else
     819                searches = next;
     820            free(sr);
     821            numsearches--;
     822        } else {
     823            previous = sr;
     824        }
     825        sr = next;
     826    }
    799827}
    800828
     
    910938
    911939static 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;
     940new_search(void)
     941{
     942    struct search *sr, *oldest = NULL;
     943
     944    /* Find the oldest done search */
     945    sr = searches;
     946    while(sr) {
     947        if(sr->done &&
     948           (oldest == NULL || oldest->step_time > sr->step_time))
     949            oldest = sr;
     950        sr = sr->next;
     951    }
     952
     953    /* The oldest slot is expired. */
     954    if(oldest && oldest->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME)
     955        return oldest;
     956
     957    /* Allocate a new slot. */
     958    if(numsearches < DHT_MAX_SEARCHES) {
     959        sr = calloc(1, sizeof(struct search));
     960        if(sr != NULL) {
     961            sr->next = searches;
     962            searches = sr;
     963            numsearches++;
     964            return sr;
     965        }
     966    }
     967
     968    /* Oh, well, never mind.  Reuse the oldest slot. */
     969    return oldest;
    926970}
    927971
     
    946990    struct search *sr;
    947991    struct bucket *b;
    948     int i;
    949 
    950     for(i = 0; i < numsearches; i++) {
    951         if(id_cmp(searches[i].id, id) == 0)
     992
     993    sr = searches;
     994    while(sr) {
     995        if(id_cmp(sr->id, id) == 0)
    952996            break;
    953     }
    954 
    955     if(i < numsearches) {
     997        sr = sr->next;
     998    }
     999
     1000    if(sr) {
    9561001        /* We're reusing data from an old search.  Reusing the same tid
    9571002           means that we can merge replies for both searches. */
    958         int j;
    959         sr = searches + i;
     1003        int i;
    9601004        sr->done = 0;
    9611005    again:
    962         for(j = 0; j < sr->numnodes; j++) {
     1006        for(i = 0; i < sr->numnodes; i++) {
    9631007            struct search_node *n;
    964             n = &sr->nodes[j];
     1008            n = &sr->nodes[i];
    9651009            /* Discard any doubtful nodes. */
    9661010            if(n->pinged >= 3 || n->reply_time < now.tv_sec - 7200) {
     
    9741018        }
    9751019    } else {
    976         sr = find_free_search_slot();
     1020        sr = new_search();
    9771021        if(sr == NULL) {
    9781022            errno = ENOSPC;
    9791023            return -1;
    9801024        }
    981         memset(sr, 0, sizeof(struct search));
    9821025        sr->tid = search_id++;
     1026        sr->step_time = 0;
    9831027        memcpy(sr->id, id, 20);
     1028        sr->done = 0;
    9841029        sr->numnodes = 0;
    9851030    }
     
    11081153broken_node(int s, const unsigned char *id, struct sockaddr_in *sin)
    11091154{
    1110     int i, j;
     1155    int i;
    11111156
    11121157    debugf("Blacklisting broken node.\n");
    11131158
    11141159    if(id) {
     1160        struct node *n;
     1161        struct search *sr;
    11151162        /* Make the node easy to discard. */
    1116         struct node *n;
    11171163        n = find_node(id);
    11181164        if(n) {
     
    11211167        }
    11221168        /* 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]);
     1169        sr = searches;
     1170        while(sr) {
     1171            for(i = 0; i < sr->numnodes; i++)
     1172                if(id_cmp(sr->nodes[i].id, id) == 0)
     1173                    flush_search_node(&sr->nodes[i], sr);
     1174            sr = sr->next;
    11281175        }
    11291176    }
     
    12151262dht_dump_tables(FILE *f)
    12161263{
    1217     int i, j;
     1264    int i;
    12181265    struct bucket *b = buckets;
    12191266    struct storage *st = storage;
     1267    struct search *sr = searches;
    12201268
    12211269    fprintf(f, "My id ");
     
    12511299        b = b->next;
    12521300    }
    1253     for(i = 0; i < numsearches; i++) {
    1254         struct search *sr = &searches[i];
    1255         fprintf(f, "\nSearch %d id ", i);
     1301    while(sr) {
     1302        fprintf(f, "\nSearch id ");
    12561303        print_hex(f, sr->id, 20);
    12571304        fprintf(f, " age %d%s\n", (int)(now.tv_sec - sr->step_time),
    12581305               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);
     1306        for(i = 0; i < sr->numnodes; i++) {
     1307            struct search_node *n = &sr->nodes[i];
     1308            fprintf(f, "Node %d id ", i);
    12621309            print_hex(f, n->id, 20);
    12631310            fprintf(f, " bits %d age ", common_bits(sr->id, n->id));
     
    12711318                   n->replied ? " (replied)" : "");
    12721319        }
     1320        sr = sr->next;
    12731321    }
    12741322
     
    13061354        return -1;
    13071355
     1356    searches = NULL;
    13081357    numsearches = 0;
    13091358
     
    13781427        free(st);
    13791428    }
    1380    
     1429
     1430    while(searches) {
     1431        struct search *sr = searches;
     1432        searches = searches->next;
     1433        free(sr);
     1434    }
     1435
    13811436    return 1;
    13821437}
     
    16551710        expire_buckets(s);
    16561711        expire_storage();
     1712        expire_searches();
    16571713    }
    16581714
    16591715    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];
     1716        struct search *sr;
     1717        sr = searches;
     1718        while(sr) {
    16631719            if(!sr->done && sr->step_time + 5 <= now.tv_sec) {
    16641720                search_step(s, sr, callback, closure);
    16651721            }
     1722            sr = sr->next;
    16661723        }
    16671724                   
    16681725        search_time = 0;
    1669        
    1670         for(i = 0; i < numsearches; i++) {
    1671             struct search *sr = &searches[i];
     1726
     1727        sr = searches;
     1728        while(sr) {
    16721729            if(!sr->done) {
    16731730                time_t tm = sr->step_time + 15 + random() % 10;
     
    16751732                    search_time = tm;
    16761733            }
     1734            sr = sr->next;
    16771735        }
    16781736    }
Note: See TracChangeset for help on using the changeset viewer.