When requesting or serving resources via fingerprint/digest, request and respond in-order, removing duplicates.

svn:r6673

6 files changed, 65 insertions, 23 deletions

diff --git a/src/common/container.c b/src/common/container.c
index 06e810a14..94f7f84df 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -461,6 +461,20 @@ smartlist_sort_strings(smartlist_t *sl)
   smartlist_sort(sl, _compare_string_ptrs);
 }
 
+/** Helper: compare two DIGEST_LEN digests. */
+static int
+_compare_digests(const void **_a, const void **_b)
+{
+  return memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
+}
+
+/** Sort the list of DIGEST_LEN-byte digests into ascending order. */
+void
+smartlist_sort_digests(smartlist_t *sl)
+{
+  smartlist_sort(sl, _compare_string_ptrs);
+}
+
 #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
   typedef struct prefix ## entry_t {                      \
     HT_ENTRY(prefix ## entry_t) node;                     \
diff --git a/src/common/container.h b/src/common/container.h
index 40cf13f4f..1031a6ef1 100644
--- a/src/common/container.h
+++ b/src/common/container.h
@@ -72,6 +72,7 @@ void smartlist_insert(smartlist_t *sl, int idx, void *val);
 void smartlist_sort(smartlist_t *sl,
                     int (*compare)(const void **a, const void **b));
 void smartlist_sort_strings(smartlist_t *sl);
+void smartlist_sort_digests(smartlist_t *sl);
 void *smartlist_bsearch(smartlist_t *sl, const void *key,
                         int (*compare)(const void *key, const void **member));
 
diff --git a/src/or/directory.c b/src/or/directory.c
index 84b2db7d7..3430e12c2 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -306,7 +306,7 @@ connection_dir_download_networkstatus_failed(connection_t *conn)
      * failed, and possibly retry them later.*/
     smartlist_t *failed = smartlist_create();
     dir_split_resource_into_fingerprints(conn->requested_resource+3,
-                                         failed, NULL, 0);
+                                         failed, NULL, 0, 0);
     if (smartlist_len(failed)) {
       dir_networkstatus_download_failed(failed);
       SMARTLIST_FOREACH(failed, char *, cp, tor_free(cp));
@@ -997,7 +997,7 @@ connection_dir_client_reached_eof(connection_t *conn)
         !strcmpstart(conn->requested_resource,"fp/")) {
       which = smartlist_create();
       dir_split_resource_into_fingerprints(conn->requested_resource+3,
-                                           which, NULL, 0);
+                                           which, NULL, 0, 0);
     } else if (conn->requested_resource &&
                !strcmpstart(conn->requested_resource, "all")) {
       which = smartlist_create();
@@ -1045,7 +1045,7 @@ connection_dir_client_reached_eof(connection_t *conn)
         !strcmpstart(conn->requested_resource,"d/")) {
       which = smartlist_create();
       dir_split_resource_into_fingerprints(conn->requested_resource+2,
-                                           which, NULL, 0);
+                                           which, NULL, 0, 0);
       n_asked_for = smartlist_len(which);
     }
     if (status_code != 200) {
@@ -1906,21 +1906,21 @@ dir_routerdesc_download_failed(smartlist_t *failed)
  * the strings, in order, into <b>fp_out</b>.  If <b>compressed_out</b> is
  * non-NULL, set it to 1 if the resource ends in ".z", else set it to 0.  If
  * decode_hex is true, then delete all elements that aren't hex digests, and
- * decode the rest.
+ * decode the rest.  If sort_uniq is true, then sort the list and remove
+ * all duplicates.
  */
 int
 dir_split_resource_into_fingerprints(const char *resource,
                                      smartlist_t *fp_out, int *compressed_out,
-                                     int decode_hex)
+                                     int decode_hex, int sort_uniq)
 {
-  int old_len;
+  smartlist_t *fp_tmp = smartlist_create();
   tor_assert(fp_out);
-  old_len = smartlist_len(fp_out);
-  smartlist_split_string(fp_out, resource, "+", 0, 0);
+  smartlist_split_string(fp_tmp, resource, "+", 0, 0);
   if (compressed_out)
     *compressed_out = 0;
-  if (smartlist_len(fp_out) > old_len) {
-    char *last = smartlist_get(fp_out,smartlist_len(fp_out)-1);
+  if (smartlist_len(fp_tmp)) {
+    char *last = smartlist_get(fp_tmp,smartlist_len(fp_tmp)-1);
     size_t last_len = strlen(last);
     if (last_len > 2 && !strcmp(last+last_len-2, ".z")) {
       last[last_len-2] = '\0';
@@ -1931,27 +1931,51 @@ dir_split_resource_into_fingerprints(const char *resource,
   if (decode_hex) {
     int i;
     char *cp, *d = NULL;
-    for (i = old_len; i < smartlist_len(fp_out); ++i) {
-      cp = smartlist_get(fp_out, i);
+    for (i = 0; i < smartlist_len(fp_tmp); ++i) {
+      cp = smartlist_get(fp_tmp, i);
       if (strlen(cp) != HEX_DIGEST_LEN) {
         log_info(LD_DIR,
                  "Skipping digest %s with non-standard length.", escaped(cp));
-        smartlist_del(fp_out, i--);
+        smartlist_del_keeporder(fp_tmp, i--);
         goto again;
       }
       d = tor_malloc_zero(DIGEST_LEN);
       if (base16_decode(d, DIGEST_LEN, cp, HEX_DIGEST_LEN)<0) {
         log_info(LD_DIR, "Skipping non-decodable digest %s", escaped(cp));
-        smartlist_del(fp_out, i--);
+        smartlist_del_keeporder(fp_tmp, i--);
         goto again;
       }
-      smartlist_set(fp_out, i, d);
+      smartlist_set(fp_tmp, i, d);
       d = NULL;
     again:
       tor_free(cp);
       tor_free(d);
     }
   }
+  if (sort_uniq) {
+    smartlist_t *fp_tmp2 = smartlist_create();
+    int i;
+    if (decode_hex)
+      smartlist_sort_digests(fp_tmp);
+    else
+      smartlist_sort_strings(fp_tmp);
+    if (smartlist_len(fp_tmp))
+      smartlist_add(fp_tmp2, smartlist_get(fp_tmp, 0));
+    for (i = 1; i < smartlist_len(fp_tmp); ++i) {
+      char *cp = smartlist_get(fp_tmp, i);
+      char *last = smartlist_get(fp_tmp2, smartlist_len(fp_tmp2)-1);
+      
+      if ((decode_hex && memcmp(cp, last, DIGEST_LEN))
+	  || (!decode_hex && strcasecmp(cp, last)))
+	smartlist_add(fp_tmp2, cp);
+      else
+	tor_free(cp);
+    }
+    smartlist_free(fp_tmp);
+    fp_tmp = fp_tmp2;
+  }
+  smartlist_add_all(fp_out, fp_tmp);
+  smartlist_free(fp_tmp);
   return 0;
 }
 
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 9f6002e40..562fad491 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -1533,11 +1533,12 @@ dirserv_get_networkstatus_v2_fingerprints(smartlist_t *result,
       smartlist_add(result, tor_memdup(ident, DIGEST_LEN));
       iter = digestmap_iter_next(cached_v2_networkstatus, iter);
     }
+    smartlist_sort_digests(result);
     if (smartlist_len(result) == 0)
       log_warn(LD_DIRSERV,
                "Client requested 'all' network status objects; we have none.");
   } else if (!strcmpstart(key, "fp/")) {
-    dir_split_resource_into_fingerprints(key+3, result, NULL, 1);
+    dir_split_resource_into_fingerprints(key+3, result, NULL, 1, 1);
   }
 }
 
@@ -1586,7 +1587,7 @@ dirserv_get_networkstatus_v2(smartlist_t *result,
                "Client requested 'all' network status objects; we have none.");
   } else if (!strcmpstart(key, "fp/")) {
     smartlist_t *digests = smartlist_create();
-    dir_split_resource_into_fingerprints(key+3, digests, NULL, 1);
+    dir_split_resource_into_fingerprints(key+3, digests, NULL, 1, 1);
     SMARTLIST_FOREACH(digests, char *, cp,
         {
           cached_dir_t *cached;
@@ -1629,10 +1630,10 @@ dirserv_get_routerdesc_fingerprints(smartlist_t *fps_out, const char *key,
                     tor_memdup(ri->cache_info.identity_digest, DIGEST_LEN));
   } else if (!strcmpstart(key, "/tor/server/d/")) {
     key += strlen("/tor/server/d/");
-    dir_split_resource_into_fingerprints(key, fps_out, NULL, 1);
+    dir_split_resource_into_fingerprints(key, fps_out, NULL, 1, 1);
   } else if (!strcmpstart(key, "/tor/server/fp/")) {
     key += strlen("/tor/server/fp/");
-    dir_split_resource_into_fingerprints(key, fps_out, NULL, 1);
+    dir_split_resource_into_fingerprints(key, fps_out, NULL, 1, 1);
   } else {
     *msg = "Key not recognized";
     return -1;
@@ -1680,7 +1681,7 @@ dirserv_get_routerdescs(smartlist_t *descs_out, const char *key,
   } else if (!strcmpstart(key, "/tor/server/d/")) {
     smartlist_t *digests = smartlist_create();
     key += strlen("/tor/server/d/");
-    dir_split_resource_into_fingerprints(key, digests, NULL, 1);
+    dir_split_resource_into_fingerprints(key, digests, NULL, 1, 1);
     SMARTLIST_FOREACH(digests, const char *, d,
        {
          signed_descriptor_t *sd = router_get_by_descriptor_digest(d);
@@ -1693,7 +1694,7 @@ dirserv_get_routerdescs(smartlist_t *descs_out, const char *key,
     smartlist_t *digests = smartlist_create();
     time_t cutoff = time(NULL) - ROUTER_MAX_AGE_TO_PUBLISH;
     key += strlen("/tor/server/fp/");
-    dir_split_resource_into_fingerprints(key, digests, NULL, 1);
+    dir_split_resource_into_fingerprints(key, digests, NULL, 1, 1);
     SMARTLIST_FOREACH(digests, const char *, d,
        {
          if (router_digest_is_me(d)) {
diff --git a/src/or/or.h b/src/or/or.h
index 7346e225e..92742848d 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1910,7 +1910,7 @@ int connection_dir_finished_connecting(connection_t *conn);
 void connection_dir_request_failed(connection_t *conn);
 int dir_split_resource_into_fingerprints(const char *resource,
                                     smartlist_t *fp_out, int *compresseed_out,
-                                    int decode_hex);
+                                    int decode_hex, int sort_uniq);
 char *directory_dump_request_log(void);
 
 /********************************* dirserv.c ***************************/
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index f5cd052c2..2223e319b 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -2507,6 +2507,7 @@ update_networkstatus_client_downloads(time_t now)
   resource = tor_malloc(resource_len);
   memcpy(resource, "fp/", 3);
   cp = resource+3;
+  smartlist_sort_digests(missing);
   needed = smartlist_len(missing);
   SMARTLIST_FOREACH(missing, const char *, d,
     {
@@ -3252,7 +3253,7 @@ list_pending_descriptor_downloads(digestmap_t *result)
         !conn->marked_for_close) {
       if (!strcmpstart(conn->requested_resource, prefix))
         dir_split_resource_into_fingerprints(conn->requested_resource+p_len,
-                                             tmp, NULL, 1);
+                                             tmp, NULL, 1, 0);
     }
   }
   SMARTLIST_FOREACH(tmp, char *, d,
@@ -3487,6 +3488,7 @@ update_router_descriptor_client_downloads(time_t now)
              (n_downloadable+n_per_request-1)/n_per_request,
              n_downloadable>n_per_request?"s":"",
              n_downloadable, n_downloadable>1?"s":"", n_per_request);
+    smartlist_sort_digests(downloadable);
     for (i=0; i < n_downloadable; i += n_per_request) {
       initiate_descriptor_downloads(NULL, downloadable, i, i+n_per_request);
     }