Changeset 9145 for trunk/third-party/dht/dht.c

Timestamp:

Sep 19, 2009, 6:09:57 PM (13 years ago)

Author:

charles

Message:

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

File:

• trunk/third-party/dht/dht.c (modified) (22 diffs)

trunk/third-party/dht/dht.c

@@ -123 +123 @@
     struct search_node nodes[SEARCH_NODES];
     int numnodes;
+    struct search *next;
 };
 
@@ -134 +135 @@
 #ifndef DHT_MAX_PEERS
 #define DHT_MAX_PEERS 2048
+#endif
+
+/* The maximum number of searches we keep data about. */
+#ifndef DHT_MAX_SEARCHES
+#define DHT_MAX_SEARCHES 1024
+#endif
+
+/* The time after which we consider a search to be expirable. */
+#ifndef DHT_SEARCH_EXPIRE_TIME
+#define DHT_SEARCH_EXPIRE_TIME (62 * 60)
 #endif
 
@@ -208 +219 @@
 static struct storage *storage;
 
-/* The maximum number of concurrent searches. */
-#ifndef DHT_MAX_SEARCHES
-#define DHT_MAX_SEARCHES 20
-#endif
-
-static struct search searches[DHT_MAX_SEARCHES];
+static struct search *searches = NULL;
 static int numsearches;
 static unsigned short search_id;
@@ -645 +651 @@
             n = n->next;
         }
-        
-        if(!dubious && mybucket) {
+
+        /* If there's only one bucket, split even if there remain doubtful
+           nodes.  This violates the spec, but it speeds up bootstrapping. */
+        if(mybucket && (!dubious || buckets->next == NULL)) {
             debugf("Splitting.\n");
             b = split_bucket(s, b);
@@ -725 +733 @@
 find_search(unsigned short tid)
 {
-    int i;
-    for(i = 0; i < numsearches; i++) {
-        if(searches[i].tid == tid)
-            return &searches[i];
+    struct search *sr = searches;
+    while(sr) {
+        if(sr->tid == tid)
+            return sr;
+        sr = sr->next;
     }
     return NULL;
@@ -797 +806 @@
         sr->nodes[j] = sr->nodes[j + 1];
     sr->numnodes--;
+}
+
+static void
+expire_searches(void)
+{
+    struct search *sr = searches, *previous = NULL;
+
+    while(sr) {
+        struct search *next = sr->next;
+        if(sr->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME) {
+            if(previous)
+                previous->next = next;
+            else
+                searches = next;
+            free(sr);
+            numsearches--;
+        } else {
+            previous = sr;
+        }
+        sr = next;
+    }
 }
 
@@ -910 +940 @@
 
 static struct search *
-find_free_search_slot(void)
-{
-    int i;
-    struct search *sr = NULL;
-
-    if(numsearches < DHT_MAX_SEARCHES)
-        return &searches[numsearches++];
-
-    for(i = 0; i < numsearches; i++) {
-        if(searches[i].done &&
-           (sr == NULL || searches[i].step_time < sr->step_time))
-            sr = &searches[i];
-    }
-    return sr;
+new_search(void)
+{
+    struct search *sr, *oldest = NULL;
+
+    /* Find the oldest done search */
+    sr = searches;
+    while(sr) {
+        if(sr->done &&
+           (oldest == NULL || oldest->step_time > sr->step_time))
+            oldest = sr;
+        sr = sr->next;
+    }
+
+    /* The oldest slot is expired. */
+    if(oldest && oldest->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME)
+        return oldest;
+
+    /* Allocate a new slot. */
+    if(numsearches < DHT_MAX_SEARCHES) {
+        sr = calloc(1, sizeof(struct search));
+        if(sr != NULL) {
+            sr->next = searches;
+            searches = sr;
+            numsearches++;
+            return sr;
+        }
+    }
+
+    /* Oh, well, never mind.  Reuse the oldest slot. */
+    return oldest;
 }
 
@@ -946 +992 @@
     struct search *sr;
     struct bucket *b;
-    int i;
-
-    for(i = 0; i < numsearches; i++) {
-        if(id_cmp(searches[i].id, id) == 0)
+
+    sr = searches;
+    while(sr) {
+        if(id_cmp(sr->id, id) == 0)
             break;
-    }
-
-    if(i < numsearches) {
+        sr = sr->next;
+    }
+
+    if(sr) {
         /* We're reusing data from an old search.  Reusing the same tid
            means that we can merge replies for both searches. */
-        int j;
-        sr = searches + i;
+        int i;
         sr->done = 0;
     again:
-        for(j = 0; j < sr->numnodes; j++) {
+        for(i = 0; i < sr->numnodes; i++) {
             struct search_node *n;
-            n = &sr->nodes[j];
+            n = &sr->nodes[i];
             /* Discard any doubtful nodes. */
             if(n->pinged >= 3 || n->reply_time < now.tv_sec - 7200) {
@@ -974 +1020 @@
         }
     } else {
-        sr = find_free_search_slot();
+        sr = new_search();
         if(sr == NULL) {
             errno = ENOSPC;
             return -1;
         }
-        memset(sr, 0, sizeof(struct search));
         sr->tid = search_id++;
+        sr->step_time = 0;
         memcpy(sr->id, id, 20);
+        sr->done = 0;
         sr->numnodes = 0;
     }
@@ -990 +1037 @@
     insert_search_bucket(b, sr);
 
-    if(sr->numnodes < 8) {
+    if(sr->numnodes < SEARCH_NODES) {
         struct bucket *p = previous_bucket(b);
         if(b->next)
@@ -1108 +1155 @@
 broken_node(int s, const unsigned char *id, struct sockaddr_in *sin)
 {
-    int i, j;
+    int i;
 
     debugf("Blacklisting broken node.\n");
 
     if(id) {
+        struct node *n;
+        struct search *sr;
         /* Make the node easy to discard. */
-        struct node *n;
         n = find_node(id);
         if(n) {
@@ -1121 +1169 @@
         }
         /* Discard it from any searches in progress. */
-        for(i = 0; i < numsearches; i++) {
-            for(j = 0; j < searches[i].numnodes; j++)
-                if(id_cmp(searches[i].nodes[j].id, id) == 0)
-                    flush_search_node(&searches[i].nodes[j],
-                                      &searches[i]);
+        sr = searches;
+        while(sr) {
+            for(i = 0; i < sr->numnodes; i++)
+                if(id_cmp(sr->nodes[i].id, id) == 0)
+                    flush_search_node(&sr->nodes[i], sr);
+            sr = sr->next;
         }
     }
@@ -1207 +1256 @@
         *cached_return = cached;
     if(incoming_return)
-        *incoming_return = cached;
+        *incoming_return = incoming;
     return good + dubious;
 }
@@ -1215 +1264 @@
 dht_dump_tables(FILE *f)
 {
-    int i, j;
+    int i;
     struct bucket *b = buckets;
     struct storage *st = storage;
+    struct search *sr = searches;
 
     fprintf(f, "My id ");
@@ -1251 +1301 @@
         b = b->next;
     }
-    for(i = 0; i < numsearches; i++) {
-        struct search *sr = &searches[i];
-        fprintf(f, "\nSearch %d id ", i);
+    while(sr) {
+        fprintf(f, "\nSearch id ");
         print_hex(f, sr->id, 20);
         fprintf(f, " age %d%s\n", (int)(now.tv_sec - sr->step_time),
                sr->done ? " (done)" : "");
-        for(j = 0; j < sr->numnodes; j++) {
-            struct search_node *n = &sr->nodes[j];
-            fprintf(f, "Node %d id ", j);
+        for(i = 0; i < sr->numnodes; i++) {
+            struct search_node *n = &sr->nodes[i];
+            fprintf(f, "Node %d id ", i);
             print_hex(f, n->id, 20);
             fprintf(f, " bits %d age ", common_bits(sr->id, n->id));
@@ -1271 +1320 @@
                    n->replied ? " (replied)" : "");
         }
+        sr = sr->next;
     }
 
@@ -1306 +1356 @@
         return -1;
 
+    searches = NULL;
     numsearches = 0;
 
@@ -1378 +1429 @@
         free(st);
     }
-    
+
+    while(searches) {
+        struct search *sr = searches;
+        searches = searches->next;
+        free(sr);
+    }
+
     return 1;
 }
@@ -1547 +1604 @@
                 sr = find_search(ttid);
                 if(!sr) {
-                    debugf("Unknown search!");
+                    debugf("Unknown search!\n");
                     new_node(s, id, &source, 1);
                 } else {
@@ -1572 +1629 @@
             debugf("Ping (%d)!\n", tid_len);
             new_node(s, id, &source, 1);
-            debugf("Sending pong!\n");
+            debugf("Sending pong.\n");
             send_pong(s, (struct sockaddr*)&source, sizeof(source),
                       tid, tid_len);
@@ -1655 +1712 @@
         expire_buckets(s);
         expire_storage();
+        expire_searches();
     }
 
     if(search_time > 0 && now.tv_sec >= search_time) {
-        int i;
-        for(i = 0; i < numsearches; i++) {
-            struct search *sr = &searches[i];
+        struct search *sr;
+        sr = searches;
+        while(sr) {
             if(!sr->done && sr->step_time + 5 <= now.tv_sec) {
                 search_step(s, sr, callback, closure);
             }
+            sr = sr->next;
         }
                    
         search_time = 0;
-        
-        for(i = 0; i < numsearches; i++) {
-            struct search *sr = &searches[i];
+
+        sr = searches;
+        while(sr) {
             if(!sr->done) {
                 time_t tm = sr->step_time + 15 + random() % 10;
@@ -1675 +1734 @@
                     search_time = tm;
             }
+            sr = sr->next;
         }
     }