Merge branch 'bug16389_027_03_squashed'

6 files changed, 339 insertions, 7 deletions

diff --git a/src/or/main.c b/src/or/main.c
index 5bff82b3cf..e564e6c132 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -1488,6 +1488,10 @@ run_scheduled_events(time_t now)
 #define CLEAN_CACHES_INTERVAL (30*60)
     time_to.clean_caches = now + CLEAN_CACHES_INTERVAL;
   }
+  /* We don't keep entries that are more than five minutes old so we try to
+   * clean it as soon as we can since we want to make sure the client waits
+   * as little as possible for reachability reasons. */
+  rend_cache_failure_clean(now);
 
 #define RETRY_DNS_INTERVAL (10*60)
   /* If we're a server and initializing dns failed, retry periodically. */
diff --git a/src/or/rendcache.c b/src/or/rendcache.c
index be94ef4445..9a33046fb6 100644
--- a/src/or/rendcache.c
+++ b/src/or/rendcache.c
@@ -9,7 +9,6 @@
 #include "rendcache.h"
 
 #include "config.h"
-#include "rendcommon.h"
 #include "rephist.h"
 #include "routerlist.h"
 #include "routerparse.h"
@@ -22,6 +21,33 @@ static strmap_t *rend_cache = NULL;
  * directories. */
 static digestmap_t *rend_cache_v2_dir = NULL;
 
+/** (Client side only) Map from service id to rend_cache_failure_t. This
+ * cache is used to track intro point(IP) failures so we know when to keep
+ * or discard a new descriptor we just fetched. Here is a description of the
+ * cache behavior.
+ *
+ * Everytime tor discards an IP (ex: receives a NACK), we add an entry to
+ * this cache noting the identity digest of the IP and it's failure type for
+ * the service ID. The reason we indexed this cache by service ID is to
+ * differentiate errors that can occur only for a specific service like a
+ * NACK for instance. It applies for one but maybe not for the others.
+ *
+ * Once a service descriptor is fetched and considered valid, each IP is
+ * looked up in this cache and if present, it is discarded from the fetched
+ * descriptor. At the end, all IP(s) in the cache, for a specific service
+ * ID, that were NOT present in the descriptor are removed from this cache.
+ * Which means that if at least one IP was not in this cache, thus usuable,
+ * it's considered a new descriptor so we keep it. Else, if all IPs were in
+ * this cache, we discard the descriptor as it's considered unsuable.
+ *
+ * Once a descriptor is removed from the rend cache or expires, the entry
+ * in this cache is also removed for the service ID.
+ *
+ * This scheme allows us to not realy on the descriptor's timestamp (which
+ * is rounded down to the hour) to know if we have a newer descriptor. We
+ * only rely on the usability of intro points from an internal state. */
+static strmap_t *rend_cache_failure = NULL;
+
 /** DOCDOC */
 static size_t rend_cache_total_allocation = 0;
 
@@ -32,6 +58,7 @@ rend_cache_init(void)
 {
   rend_cache = strmap_new();
   rend_cache_v2_dir = digestmap_new();
+  rend_cache_failure = strmap_new();
 }
 
 /** Return the approximate number of bytes needed to hold <b>e</b>. */
@@ -85,6 +112,83 @@ rend_cache_increment_allocation(size_t n)
   }
 }
 
+/** Helper: free a rend cache failure intro object. */
+static void
+rend_cache_failure_intro_entry_free(rend_cache_failure_intro_t *entry)
+{
+  if (entry == NULL) {
+    return;
+  }
+  tor_free(entry);
+}
+
+/** Allocate a rend cache failure intro object and return it. <b>failure</b>
+ * is set into the object. This function can not fail. */
+static rend_cache_failure_intro_t *
+rend_cache_failure_intro_entry_new(rend_intro_point_failure_t failure)
+{
+  rend_cache_failure_intro_t *entry = tor_malloc(sizeof(*entry));
+  entry->failure_type = failure;
+  entry->created_ts = time(NULL);
+  return entry;
+}
+
+/** Helper: free a rend cache failure object. */
+static void
+rend_cache_failure_entry_free(rend_cache_failure_t *entry)
+{
+  if (entry == NULL) {
+    return;
+  }
+
+  /* Free and remove every intro failure object. */
+  DIGESTMAP_FOREACH_MODIFY(entry->intro_failures, key,
+                           rend_cache_failure_intro_t *, e) {
+    rend_cache_failure_intro_entry_free(e);
+    MAP_DEL_CURRENT(key);
+  } DIGESTMAP_FOREACH_END;
+  tor_free(entry);
+}
+
+/** Helper: deallocate a rend_cache_failure_t. (Used with strmap_free(),
+ * which requires a function pointer whose argument is void*). */
+static void
+rend_cache_failure_entry_free_(void *entry)
+{
+  rend_cache_failure_entry_free(entry);
+}
+
+/** Allocate a rend cache failure object and return it. This function can
+ * not fail. */
+static rend_cache_failure_t *
+rend_cache_failure_entry_new(void)
+{
+  rend_cache_failure_t *entry = tor_malloc(sizeof(*entry));
+  entry->intro_failures = digestmap_new();
+  return entry;
+}
+
+/** Remove failure cache entry for the service ID in the given descriptor
+ * <b>desc</b>. */
+static void
+rend_cache_failure_remove(rend_service_descriptor_t *desc)
+{
+  char service_id[REND_SERVICE_ID_LEN_BASE32 + 1];
+  rend_cache_failure_t *entry;
+
+  if (desc == NULL) {
+    return;
+  }
+  if (rend_get_service_id(desc->pk, service_id) < 0) {
+    return;
+  }
+  entry = strmap_get_lc(rend_cache_failure, service_id);
+  if (entry != NULL) {
+    strmap_remove_lc(rend_cache_failure, service_id);
+    rend_cache_failure_entry_free(entry);
+  }
+}
+
 /** Helper: free storage held by a single service descriptor cache entry. */
 static void
 rend_cache_entry_free(rend_cache_entry_t *e)
@@ -92,6 +196,9 @@ rend_cache_entry_free(rend_cache_entry_t *e)
   if (!e)
     return;
   rend_cache_decrement_allocation(rend_cache_entry_allocation(e));
+  /* We are about to remove a descriptor from the cache so remove the entry
+   * in the failure cache. */
+  rend_cache_failure_remove(e->parsed);
   rend_service_descriptor_free(e->parsed);
   tor_free(e->desc);
   tor_free(e);
@@ -111,11 +218,42 @@ rend_cache_free_all(void)
 {
   strmap_free(rend_cache, rend_cache_entry_free_);
   digestmap_free(rend_cache_v2_dir, rend_cache_entry_free_);
+  strmap_free(rend_cache_failure, rend_cache_failure_entry_free_);
   rend_cache = NULL;
   rend_cache_v2_dir = NULL;
+  rend_cache_failure = NULL;
   rend_cache_total_allocation = 0;
 }
 
+/** Remove all entries that re REND_CACHE_FAILURE_MAX_AGE old. This is
+ * called every second.
+ *
+ * We have to clean these regurlarly else if for whatever reasons an hidden
+ * service goes offline and a client tries to connect to it during that
+ * time, a failure entry is created and the client will be unable to connect
+ * for a while even though the service has return online.  */
+void
+rend_cache_failure_clean(time_t now)
+{
+  time_t cutoff = now - REND_CACHE_FAILURE_MAX_AGE;
+  STRMAP_FOREACH_MODIFY(rend_cache_failure, key,
+                        rend_cache_failure_t *, ent) {
+    /* Free and remove every intro failure object that match the cutoff. */
+    DIGESTMAP_FOREACH_MODIFY(ent->intro_failures, ip_key,
+                             rend_cache_failure_intro_t *, ip_ent) {
+      if (ip_ent->created_ts < cutoff) {
+        rend_cache_failure_intro_entry_free(ip_ent);
+        MAP_DEL_CURRENT(ip_key);
+      }
+    } DIGESTMAP_FOREACH_END;
+    /* If the entry is now empty of intro point failures, remove it. */
+    if (digestmap_isempty(ent->intro_failures)) {
+      rend_cache_failure_entry_free(ent);
+      MAP_DEL_CURRENT(key);
+    }
+  } STRMAP_FOREACH_END;
+}
+
 /** Removes all old entries from the service descriptor cache.
 */
 void
@@ -150,6 +288,140 @@ rend_cache_purge(void)
   rend_cache = strmap_new();
 }
 
+/** Remove ALL entries from the failure cache. This is also called when a
+ * NEWNYM signal is received. */
+void
+rend_cache_failure_purge(void)
+{
+  if (rend_cache_failure) {
+    log_info(LD_REND, "Purging HS failure cache");
+    strmap_free(rend_cache_failure, rend_cache_failure_entry_free_);
+  }
+  rend_cache_failure = strmap_new();
+}
+
+/** Lookup the rend failure cache using a relay identity digest in
+ * <b>identity</b> and service ID <b>service_id</b>. If found, the intro
+ * failure is set in <b>intro_entry</b> else it stays untouched. Return 1
+ * iff found else 0. */
+static int
+cache_failure_intro_lookup(const uint8_t *identity, const char *service_id,
+                           rend_cache_failure_intro_t **intro_entry)
+{
+  rend_cache_failure_t *elem;
+  rend_cache_failure_intro_t *intro_elem;
+
+  tor_assert(rend_cache_failure);
+
+  if (intro_entry) {
+    *intro_entry = NULL;
+  }
+
+  /* Lookup descriptor and return it. */
+  elem = strmap_get_lc(rend_cache_failure, service_id);
+  if (elem == NULL) {
+    goto not_found;
+  }
+  intro_elem = digestmap_get(elem->intro_failures, (char *) identity);
+  if (intro_elem == NULL) {
+    goto not_found;
+  }
+  if (intro_entry) {
+    *intro_entry = intro_elem;
+  }
+  return 1;
+not_found:
+  return 0;
+}
+
+/** Add an intro point failure to the failure cache using the relay
+ * <b>identity</b> and service ID <b>service_id</b>. Record the
+ * <b>failure</b> in that object. */
+static void
+cache_failure_intro_add(const uint8_t *identity, const char *service_id,
+                        rend_intro_point_failure_t failure)
+{
+  rend_cache_failure_t *fail_entry;
+  rend_cache_failure_intro_t *entry;
+
+  /* Make sure we have a failure object for this service ID and if not,
+   * create it with this new intro failure entry. */
+  fail_entry = strmap_get_lc(rend_cache_failure, service_id);
+  if (fail_entry == NULL) {
+    fail_entry = rend_cache_failure_entry_new();
+    /* Add failure entry to global rend failure cache. */
+    strmap_set_lc(rend_cache_failure, service_id, fail_entry);
+  }
+  entry = rend_cache_failure_intro_entry_new(failure);
+  digestmap_set(fail_entry->intro_failures, (char *) identity, entry);
+}
+
+/** Using a parsed descriptor <b>desc</b>, check if the introduction points
+ * are present in the failure cache and if so they are removed from the
+ * descriptor and kept into the failure cache. Then, each intro points that
+ * are NOT in the descriptor but in the failure cache for the given
+ * <b>service_id</b> are removed from the failure cache. */
+static void
+validate_intro_point_failure(const rend_service_descriptor_t *desc,
+                             const char *service_id)
+{
+  rend_cache_failure_t *new_entry, *cur_entry;
+  /* New entry for the service ID that will be replacing the one in the
+   * failure cache since we have a new descriptor. In the case where all
+   * intro points are removed, we are assured that the new entry is the same
+   * as the current one. */
+  new_entry = tor_malloc(sizeof(*new_entry));
+  new_entry->intro_failures = digestmap_new();
+
+  tor_assert(desc);
+
+  SMARTLIST_FOREACH_BEGIN(desc->intro_nodes, rend_intro_point_t *, intro) {
+    int found;
+    rend_cache_failure_intro_t *entry;
+    const uint8_t *identity =
+      (uint8_t *) intro->extend_info->identity_digest;
+
+    found = cache_failure_intro_lookup(identity, service_id, &entry);
+    if (found) {
+      /* This intro point is in our cache, discard it from the descriptor
+       * because chances are that it's unusable. */
+      SMARTLIST_DEL_CURRENT(desc->intro_nodes, intro);
+      rend_intro_point_free(intro);
+      /* Keep it for our new entry. */
+      digestmap_set(new_entry->intro_failures, (char *) identity, entry);
+      continue;
+    }
+  } SMARTLIST_FOREACH_END(intro);
+
+  /* Swap the failure entry in the cache and free the current one. */
+  cur_entry = strmap_get_lc(rend_cache_failure, service_id);
+  if (cur_entry != NULL) {
+    rend_cache_failure_entry_free(cur_entry);
+  }
+  strmap_set_lc(rend_cache_failure, service_id, new_entry);
+}
+
+/** Note down an intro failure in the rend failure cache using the type of
+ * failure in <b>failure</b> for the relay identity digest in
+ * <b>identity</b> and service ID <b>service_id</b>. If an entry already
+ * exists in the cache, the failure type is changed with <b>failure</b>. */
+void
+rend_cache_intro_failure_note(rend_intro_point_failure_t failure,
+                              const uint8_t *identity,
+                              const char *service_id)
+{
+  int found;
+  rend_cache_failure_intro_t *entry;
+
+  found = cache_failure_intro_lookup(identity, service_id, &entry);
+  if (!found) {
+    cache_failure_intro_add(identity, service_id, failure);
+  } else {
+    /* Replace introduction point failure with this one. */
+    entry->failure_type = failure;
+  }
+}
+
 /** Remove all old v2 descriptors and those for which this hidden service
  * directory is not responsible for any more.
  *
@@ -537,20 +809,44 @@ rend_cache_store_v2_desc_as_client(const char *desc,
              "the future.", safe_str_client(service_id));
     goto err;
   }
-  /* Do we already have a newer descriptor? */
+  /* Do we have the same exact copy already in our cache? */
   tor_snprintf(key, sizeof(key), "2%s", service_id);
   e = (rend_cache_entry_t*) strmap_get_lc(rend_cache, key);
-  if (e && e->parsed->timestamp >= parsed->timestamp) {
+  if (e && !strcmp(desc, e->desc)) {
+    log_info(LD_REND,"We already have this service descriptor %s.",
+             safe_str_client(service_id));
+    goto okay;
+  }
+  /* Verify that we are not replacing an older descriptor. It's important to
+   * avoid an evil HSDir serving old descriptor. We validate if the
+   * timestamp is greater than and not equal because it's a rounded down
+   * timestamp to the hour so if the descriptor changed in the same hour,
+   * the rend cache failure will tells us if we have a new descriptor. */
+  if (e && e->parsed->timestamp > parsed->timestamp) {
     log_info(LD_REND, "We already have a new enough service descriptor for "
              "service ID %s with the same desc ID and version.",
              safe_str_client(service_id));
     goto okay;
   }
+  /* Lookup our failure cache for intro point that might be unsuable. */
+  validate_intro_point_failure(parsed, service_id);
+  /* It's now possible that our intro point list is empty, this means that
+   * this descriptor is useless to us because intro points have all failed
+   * somehow before. Discard the descriptor. */
+  if (smartlist_len(parsed->intro_nodes) == 0) {
+    log_info(LD_REND, "Service descriptor with service ID %s, every "
+             "intro points are unusable. Discarding it.",
+             safe_str_client(service_id));
+    goto err;
+  }
+  /* Now either purge the current one and replace it's content or create a
+   * new one and add it to the rend cache. */
   if (!e) {
     e = tor_malloc_zero(sizeof(rend_cache_entry_t));
     strmap_set_lc(rend_cache, key, e);
   } else {
     rend_cache_decrement_allocation(rend_cache_entry_allocation(e));
+    rend_cache_failure_remove(e->parsed);
     rend_service_descriptor_free(e->parsed);
     tor_free(e->desc);
   }
diff --git a/src/or/rendcache.h b/src/or/rendcache.h
index f61f02a8e6..0512058054 100644
--- a/src/or/rendcache.h
+++ b/src/or/rendcache.h
@@ -10,6 +10,7 @@
 #define TOR_RENDCACHE_H
 
 #include "or.h"
+#include "rendcommon.h"
 
 /** How old do we let hidden service descriptors get before discarding
  * them as too old? */
@@ -17,6 +18,8 @@
 /** How wrong do we assume our clock may be when checking whether hidden
  * services are too old or too new? */
 #define REND_CACHE_MAX_SKEW (24*60*60)
+/** How old do we keep an intro point failure entry in the failure cache? */
+#define REND_CACHE_FAILURE_MAX_AGE (5*60)
 
 /* Do not allow more than this many introduction points in a hidden service
  * descriptor */
@@ -31,8 +34,23 @@ typedef struct rend_cache_entry_t {
   rend_service_descriptor_t *parsed; /**< Parsed value of 'desc' */
 } rend_cache_entry_t;
 
+/* Introduction point failure type. */
+typedef struct rend_cache_failure_intro_t {
+  /* When this intro point failure occured thus we allocated this object and
+   * cache it. */
+  time_t created_ts;
+  rend_intro_point_failure_t failure_type;
+} rend_cache_failure_intro_t;
+
+/** Cache failure object indexed by service ID. */
+typedef struct rend_cache_failure_t {
+  /* Contains rend_cache_failure_intro_t indexed by identity digest. */
+  digestmap_t *intro_failures;
+} rend_cache_failure_t;
+
 void rend_cache_init(void);
 void rend_cache_clean(time_t now);
+void rend_cache_failure_clean(time_t now);
 void rend_cache_clean_v2_descs_as_dir(time_t now, size_t min_to_remove);
 void rend_cache_purge(void);
 void rend_cache_free_all(void);
@@ -53,5 +71,10 @@ rend_cache_store_status_t rend_cache_store_v2_desc_as_client(const char *desc,
                                                 rend_cache_entry_t **entry);
 size_t rend_cache_get_total_allocation(void);
 
+void rend_cache_intro_failure_note(rend_intro_point_failure_t failure,
+                                   const uint8_t *identity,
+                                   const char *service_id);
+void rend_cache_failure_purge(void);
+
 #endif /* TOR_RENDCACHE_H */
 
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index 59e938e89c..c6f29a7707 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -38,6 +38,7 @@ void
 rend_client_purge_state(void)
 {
   rend_cache_purge();
+  rend_cache_failure_purge();
   rend_client_cancel_descriptor_fetches();
   rend_client_purge_last_hid_serv_requests();
 }
@@ -1019,6 +1020,9 @@ rend_client_report_intro_point_failure(extend_info_t *failed_intro,
         tor_fragile_assert();
         /* fall through */
       case INTRO_POINT_FAILURE_GENERIC:
+        rend_cache_intro_failure_note(failure_type,
+                                      (uint8_t *) failed_intro->identity_digest,
+                                      rend_query->onion_address);
         rend_intro_point_free(intro);
         smartlist_del(ent->parsed->intro_nodes, i);
         break;
@@ -1034,6 +1038,9 @@ rend_client_report_intro_point_failure(extend_info_t *failed_intro,
                    intro->unreachable_count,
                    zap_intro_point ? " Removing from descriptor.": "");
           if (zap_intro_point) {
+            rend_cache_intro_failure_note(failure_type,
+                                          (uint8_t *) failed_intro->identity_digest,
+                                          rend_query->onion_address);
             rend_intro_point_free(intro);
             smartlist_del(ent->parsed->intro_nodes, i);
           }
diff --git a/src/or/rendclient.h b/src/or/rendclient.h
index 439f42875b..124433ef31 100644
--- a/src/or/rendclient.h
+++ b/src/or/rendclient.h
@@ -26,10 +26,6 @@ int rend_client_fetch_v2_desc(rend_data_t *query, smartlist_t *hsdirs);
 void rend_client_cancel_descriptor_fetches(void);
 void rend_client_purge_last_hid_serv_requests(void);
 
-#define INTRO_POINT_FAILURE_GENERIC 0
-#define INTRO_POINT_FAILURE_TIMEOUT 1
-#define INTRO_POINT_FAILURE_UNREACHABLE 2
-
 int rend_client_report_intro_point_failure(extend_info_t *failed_intro,
                                            rend_data_t *rend_query,
                                            unsigned int failure_type);
diff --git a/src/or/rendcommon.h b/src/or/rendcommon.h
index ba5e077642..3b2f86d614 100644
--- a/src/or/rendcommon.h
+++ b/src/or/rendcommon.h
@@ -12,6 +12,12 @@
 #ifndef TOR_RENDCOMMON_H
 #define TOR_RENDCOMMON_H
 
+typedef enum rend_intro_point_failure_t {
+  INTRO_POINT_FAILURE_GENERIC     = 0,
+  INTRO_POINT_FAILURE_TIMEOUT     = 1,
+  INTRO_POINT_FAILURE_UNREACHABLE = 2,
+} rend_intro_point_failure_t;
+
 /** Free all storage associated with <b>data</b> */
 static INLINE void
 rend_data_free(rend_data_t *data)