Merge remote-tracking branch 'asn/bug23387_squashed'

11 files changed, 1431 insertions, 410 deletions

diff --git a/src/or/hs_client.c b/src/or/hs_client.c
index 0e8fc6c24b..e7d316b745 100644
--- a/src/or/hs_client.c
+++ b/src/or/hs_client.c
@@ -6,6 +6,8 @@
  * \brief Implement next generation hidden service client functionality
  **/
 
+#define HS_CLIENT_PRIVATE
+
 #include "or.h"
 #include "hs_circuit.h"
 #include "hs_ident.h"
@@ -29,6 +31,7 @@
 #include "connection.h"
 #include "hs_ntor.h"
 #include "circuitbuild.h"
+#include "networkstatus.h"
 
 /* Get all connections that are waiting on a circuit and flag them back to
  * waiting for a hidden service descriptor for the given service key
@@ -110,7 +113,7 @@ static int
 directory_launch_v3_desc_fetch(const ed25519_public_key_t *onion_identity_pk,
                                const routerstatus_t *hsdir)
 {
-  uint64_t current_time_period = hs_get_time_period_num(approx_time());
+  uint64_t current_time_period = hs_get_time_period_num(0);
   ed25519_public_key_t blinded_pubkey;
   char base64_blinded_pubkey[ED25519_BASE64_LEN + 1];
   hs_ident_dir_conn_t hs_conn_dir_ident;
@@ -157,12 +160,12 @@ directory_launch_v3_desc_fetch(const ed25519_public_key_t *onion_identity_pk,
 
 /** Return the HSDir we should use to fetch the descriptor of the hidden
  *  service with identity key <b>onion_identity_pk</b>. */
-static routerstatus_t *
+STATIC routerstatus_t *
 pick_hsdir_v3(const ed25519_public_key_t *onion_identity_pk)
 {
   int retval;
   char base64_blinded_pubkey[ED25519_BASE64_LEN + 1];
-  uint64_t current_time_period = hs_get_time_period_num(approx_time());
+  uint64_t current_time_period = hs_get_time_period_num(0);
   smartlist_t *responsible_hsdirs;
   ed25519_public_key_t blinded_pubkey;
   routerstatus_t *hsdir_rs = NULL;
@@ -181,8 +184,8 @@ pick_hsdir_v3(const ed25519_public_key_t *onion_identity_pk)
   }
 
   /* Get responsible hsdirs of service for this time period */
-  hs_get_responsible_hsdirs(&blinded_pubkey, current_time_period, 0, 1,
-                            responsible_hsdirs);
+  hs_get_responsible_hsdirs(&blinded_pubkey, current_time_period,
+                            0, 1, responsible_hsdirs);
 
   log_debug(LD_REND, "Found %d responsible HSDirs and about to pick one.",
            smartlist_len(responsible_hsdirs));
@@ -906,7 +909,7 @@ hs_client_decode_descriptor(const char *desc_str,
 
   /* Create subcredential for this HS so that we can decrypt */
   {
-    uint64_t current_time_period = hs_get_time_period_num(approx_time());
+    uint64_t current_time_period = hs_get_time_period_num(0);
     hs_build_blinded_pubkey(service_identity_pk, NULL, 0, current_time_period,
                             &blinded_pubkey);
     hs_get_subcredential(service_identity_pk, &blinded_pubkey, subcredential);
diff --git a/src/or/hs_client.h b/src/or/hs_client.h
index 86784f52c3..d8b8acf750 100644
--- a/src/or/hs_client.h
+++ b/src/or/hs_client.h
@@ -48,5 +48,12 @@ int hs_client_reextend_intro_circuit(origin_circuit_t *circ);
 
 void hs_client_free_all(void);
 
+#ifdef HS_CLIENT_PRIVATE
+
+STATIC routerstatus_t *
+pick_hsdir_v3(const ed25519_public_key_t *onion_identity_pk);
+
+#endif
+
 #endif /* TOR_HS_CLIENT_H */
 
diff --git a/src/or/hs_common.c b/src/or/hs_common.c
index 5ea44b97e7..291d8ae8da 100644
--- a/src/or/hs_common.c
+++ b/src/or/hs_common.c
@@ -99,42 +99,65 @@ add_unix_port(smartlist_t *ports, rend_service_port_config_t *p)
 /* Helper function: The key is a digest that we compare to a node_t object
  * current hsdir_index. */
 static int
-compare_digest_to_current_hsdir_index(const void *_key, const void **_member)
+compare_digest_to_fetch_hsdir_index(const void *_key, const void **_member)
 {
   const char *key = _key;
   const node_t *node = *_member;
-  return tor_memcmp(key, node->hsdir_index->current, DIGEST256_LEN);
+  return tor_memcmp(key, node->hsdir_index->fetch, DIGEST256_LEN);
 }
 
 /* Helper function: The key is a digest that we compare to a node_t object
  * next hsdir_index. */
 static int
-compare_digest_to_next_hsdir_index(const void *_key, const void **_member)
+compare_digest_to_store_first_hsdir_index(const void *_key,
+                                          const void **_member)
 {
   const char *key = _key;
   const node_t *node = *_member;
-  return tor_memcmp(key, node->hsdir_index->next, DIGEST256_LEN);
+  return tor_memcmp(key, node->hsdir_index->store_first, DIGEST256_LEN);
+}
+
+/* Helper function: The key is a digest that we compare to a node_t object
+ * next hsdir_index. */
+static int
+compare_digest_to_store_second_hsdir_index(const void *_key,
+                                          const void **_member)
+{
+  const char *key = _key;
+  const node_t *node = *_member;
+  return tor_memcmp(key, node->hsdir_index->store_second, DIGEST256_LEN);
 }
 
 /* Helper function: Compare two node_t objects current hsdir_index. */
 static int
-compare_node_current_hsdir_index(const void **a, const void **b)
+compare_node_fetch_hsdir_index(const void **a, const void **b)
 {
   const node_t *node1= *a;
   const node_t *node2 = *b;
-  return tor_memcmp(node1->hsdir_index->current,
-                    node2->hsdir_index->current,
+  return tor_memcmp(node1->hsdir_index->fetch,
+                    node2->hsdir_index->fetch,
                     DIGEST256_LEN);
 }
 
 /* Helper function: Compare two node_t objects next hsdir_index. */
 static int
-compare_node_next_hsdir_index(const void **a, const void **b)
+compare_node_store_first_hsdir_index(const void **a, const void **b)
 {
   const node_t *node1= *a;
   const node_t *node2 = *b;
-  return tor_memcmp(node1->hsdir_index->next,
-                    node2->hsdir_index->next,
+  return tor_memcmp(node1->hsdir_index->store_first,
+                    node2->hsdir_index->store_first,
+                    DIGEST256_LEN);
+}
+
+/* Helper function: Compare two node_t objects next hsdir_index. */
+static int
+compare_node_store_second_hsdir_index(const void **a, const void **b)
+{
+  const node_t *node1= *a;
+  const node_t *node2 = *b;
+  return tor_memcmp(node1->hsdir_index->store_second,
+                    node2->hsdir_index->store_second,
                     DIGEST256_LEN);
 }
 
@@ -211,15 +234,26 @@ get_time_period_length(void)
   return (uint64_t) time_period_length;
 }
 
-/** Get the HS time period number at time <b>now</b> */
+/** Get the HS time period number at time <b>now</b>. If <b>now</b> is not set,
+ *  we try to get the time ourselves. */
 uint64_t
 hs_get_time_period_num(time_t now)
 {
   uint64_t time_period_num;
+  time_t current_time;
+
+  /* If no time is specified, set current time based on consensus time, and
+   * only fall back to system time if that fails. */
+  if (now != 0) {
+    current_time = now;
+  } else {
+    networkstatus_t *ns = networkstatus_get_live_consensus(approx_time());
+    current_time = ns ? ns->valid_after : approx_time();
+  }
 
   /* Start by calculating minutes since the epoch */
   uint64_t time_period_length = get_time_period_length();
-  uint64_t minutes_since_epoch = now / 60;
+  uint64_t minutes_since_epoch = current_time / 60;
 
   /* Apply the rotation offset as specified by prop224 (section
    * [TIME-PERIODS]), so that new time periods synchronize nicely with SRV
@@ -242,6 +276,14 @@ hs_get_next_time_period_num(time_t now)
   return hs_get_time_period_num(now) + 1;
 }
 
+/* Get the number of the _previous_ HS time period, given that the current
+ * time is <b>now</b>. */
+uint64_t
+hs_get_previous_time_period_num(time_t now)
+{
+  return hs_get_time_period_num(now) - 1;
+}
+
 /* Return the start time of the upcoming time period based on <b>now</b>. */
 time_t
 hs_get_start_time_of_next_time_period(time_t now)
@@ -547,7 +589,7 @@ compute_disaster_srv(uint64_t time_period_num, uint8_t *srv_out)
  *  would have to do it thousands of times in a row, we always cache the
  *  computer disaster SRV (and its corresponding time period num) in case we
  *  want to reuse it soon after. We need to cache two SRVs, one for each active
- *  time period (in case of overlap mode).
+ *  time period.
  */
 static uint8_t cached_disaster_srv[2][DIGEST256_LEN];
 static uint64_t cached_time_period_nums[2] = {0};
@@ -992,10 +1034,22 @@ hs_build_blinded_keypair(const ed25519_keypair_t *kp,
   memwipe(param, 0, sizeof(param));
 }
 
-/* Return true if overlap mode is active given the date in consensus. If
- * consensus is NULL, then we use the latest live consensus we can find. */
+/* Return true if we are currently in the time segment between a new time
+ * period and a new SRV (in the real network that happens between 12:00 and
+ * 00:00 UTC). Here is a diagram showing exactly when this returns true:
+ *
+ *    +------------------------------------------------------------------+
+ *    |                                                                  |
+ *    | 00:00      12:00       00:00       12:00       00:00       12:00 |
+ *    | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+ *    |                                                                  |
+ *    |  $==========|-----------$===========|-----------$===========|    |
+ *    |             ^^^^^^^^^^^^            ^^^^^^^^^^^^                 |
+ *    |                                                                  |
+ *    +------------------------------------------------------------------+
+ */
 MOCK_IMPL(int,
-hs_overlap_mode_is_active, (const networkstatus_t *consensus, time_t now))
+hs_in_period_between_tp_and_srv,(const networkstatus_t *consensus, time_t now))
 {
   time_t valid_after;
   time_t srv_start_time, tp_start_time;
@@ -1007,19 +1061,18 @@ hs_overlap_mode_is_active, (const networkstatus_t *consensus, time_t now))
     }
   }
 
-  /* We consider to be in overlap mode when we are in the period of time
-   * between a fresh SRV and the beginning of the new time period (in the
-   * normal network this is between 00:00 (inclusive) and 12:00 UTC
-   * (exclusive)) */
+  /* Get start time of next TP and of current SRV protocol run, and check if we
+   * are between them. */
   valid_after = consensus->valid_after;
-  srv_start_time =sr_state_get_start_time_of_current_protocol_run(valid_after);
+  srv_start_time =
+    sr_state_get_start_time_of_current_protocol_run(valid_after);
   tp_start_time = hs_get_start_time_of_next_time_period(srv_start_time);
 
   if (valid_after >= srv_start_time && valid_after < tp_start_time) {
-    return 1;
+    return 0;
   }
 
-  return 0;
+  return 1;
 }
 
 /* Return 1 if any virtual port in ports needs a circuit with good uptime.
@@ -1189,10 +1242,9 @@ hs_get_hsdir_spread_store(void)
 }
 
 /** <b>node</b> is an HSDir so make sure that we have assigned an hsdir index.
- *  If <b>is_for_next_period</b> is set, also check the next HSDir index field.
  *  Return 0 if everything is as expected, else return -1. */
 static int
-node_has_hsdir_index(const node_t *node, int is_for_next_period)
+node_has_hsdir_index(const node_t *node)
 {
   tor_assert(node_supports_v3_hsdir(node));
 
@@ -1204,19 +1256,19 @@ node_has_hsdir_index(const node_t *node, int is_for_next_period)
 
   /* At this point, since the node has a desc, this node must also have an
    * hsdir index. If not, something went wrong, so BUG out. */
-  if (BUG(node->hsdir_index == NULL) ||
-      BUG(tor_mem_is_zero((const char*)node->hsdir_index->current,
+  if (BUG(node->hsdir_index == NULL)) {
+    return 0;
+  }
+  if (BUG(tor_mem_is_zero((const char*)node->hsdir_index->fetch,
                           DIGEST256_LEN))) {
-    log_warn(LD_BUG, "Zero current index (ri: %p, rs: %p, md: %p)",
-             node->ri, node->rs, node->md);
     return 0;
   }
-
-  if (is_for_next_period &&
-      BUG(tor_mem_is_zero((const char*)node->hsdir_index->next,
+  if (BUG(tor_mem_is_zero((const char*)node->hsdir_index->store_first,
+                          DIGEST256_LEN))) {
+    return 0;
+  }
+  if (BUG(tor_mem_is_zero((const char*)node->hsdir_index->store_second,
                           DIGEST256_LEN))) {
-    log_warn(LD_BUG, "Zero next index (ri: %p, rs: %p, md: %p)",
-             node->ri, node->rs, node->md);
     return 0;
   }
 
@@ -1225,19 +1277,19 @@ node_has_hsdir_index(const node_t *node, int is_for_next_period)
 
 /* For a given blinded key and time period number, get the responsible HSDir
  * and put their routerstatus_t object in the responsible_dirs list. If
- * is_next_period is true, the next hsdir_index of the node_t is used. If
- * is_client is true, the spread fetch consensus parameter is used else the
- * spread store is used which is only for upload. This function can't fail but
- * it is possible that the responsible_dirs list contains fewer nodes than
- * expected.
+ * 'use_second_hsdir_index' is true, use the second hsdir_index of the node_t
+ * is used. If 'for_fetching' is true, the spread fetch consensus parameter is
+ * used else the spread store is used which is only for upload. This function
+ * can't fail but it is possible that the responsible_dirs list contains fewer
+ * nodes than expected.
  *
  * This function goes over the latest consensus routerstatus list and sorts it
  * by their node_t hsdir_index then does a binary search to find the closest
  * node. All of this makes it a bit CPU intensive so use it wisely. */
 void
 hs_get_responsible_hsdirs(const ed25519_public_key_t *blinded_pk,
-                          uint64_t time_period_num, int is_next_period,
-                          int is_client, smartlist_t *responsible_dirs)
+                          uint64_t time_period_num, int use_second_hsdir_index,
+                          int for_fetching, smartlist_t *responsible_dirs)
 {
   smartlist_t *sorted_nodes;
   /* The compare function used for the smartlist bsearch. We have two
@@ -1264,7 +1316,7 @@ hs_get_responsible_hsdirs(const ed25519_public_key_t *blinded_pk,
       node_t *n = node_get_mutable_by_id(rs->identity_digest);
       tor_assert(n);
       if (node_supports_v3_hsdir(n) && rs->is_hs_dir) {
-        if (!node_has_hsdir_index(n, is_next_period)) {
+        if (!node_has_hsdir_index(n)) {
           log_info(LD_GENERAL, "Node %s was found without hsdir index.",
                    node_describe(n));
           continue;
@@ -1281,12 +1333,15 @@ hs_get_responsible_hsdirs(const ed25519_public_key_t *blinded_pk,
   /* First thing we have to do is sort all node_t by hsdir_index. The
    * is_next_period tells us if we want the current or the next one. Set the
    * bsearch compare function also while we are at it. */
-  if (is_next_period) {
-    smartlist_sort(sorted_nodes, compare_node_next_hsdir_index);
-    cmp_fct = compare_digest_to_next_hsdir_index;
+  if (for_fetching) {
+    smartlist_sort(sorted_nodes, compare_node_fetch_hsdir_index);
+    cmp_fct = compare_digest_to_fetch_hsdir_index;
+  } else if (use_second_hsdir_index) {
+    smartlist_sort(sorted_nodes, compare_node_store_second_hsdir_index);
+    cmp_fct = compare_digest_to_store_second_hsdir_index;
   } else {
-    smartlist_sort(sorted_nodes, compare_node_current_hsdir_index);
-    cmp_fct = compare_digest_to_current_hsdir_index;
+    smartlist_sort(sorted_nodes, compare_node_store_first_hsdir_index);
+    cmp_fct = compare_digest_to_store_first_hsdir_index;
   }
 
   /* For all replicas, we'll select a set of HSDirs using the consensus
@@ -1297,8 +1352,8 @@ hs_get_responsible_hsdirs(const ed25519_public_key_t *blinded_pk,
     uint8_t hs_index[DIGEST256_LEN] = {0};
     /* Number of node to add to the responsible dirs list depends on if we are
      * trying to fetch or store. A client always fetches. */
-    int n_to_add = (is_client) ? hs_get_hsdir_spread_fetch() :
-                                 hs_get_hsdir_spread_store();
+    int n_to_add = (for_fetching) ? hs_get_hsdir_spread_fetch() :
+                                    hs_get_hsdir_spread_store();
 
     /* Get the index that we should use to select the node. */
     hs_build_hs_index(replica, blinded_pk, time_period_num, hs_index);
diff --git a/src/or/hs_common.h b/src/or/hs_common.h
index 79d92d915f..5851578fd6 100644
--- a/src/or/hs_common.h
+++ b/src/or/hs_common.h
@@ -142,10 +142,14 @@ typedef struct rend_service_port_config_t {
 /* Hidden service directory index used in a node_t which is set once we set
  * the consensus. */
 typedef struct hsdir_index_t {
-  /* The hsdir index for the current time period. */
-  uint8_t current[DIGEST256_LEN];
-  /* The hsdir index for the next time period. */
-  uint8_t next[DIGEST256_LEN];
+  /* HSDir index to use when fetching a descriptor. */
+  uint8_t fetch[DIGEST256_LEN];
+
+  /* HSDir index used by services to store their first and second
+   * descriptor. The first descriptor is chronologically older than the second
+   * one and uses older TP and SRV values. */
+  uint8_t store_first[DIGEST256_LEN];
+  uint8_t store_second[DIGEST256_LEN];
 } hsdir_index_t;
 
 void hs_init(void);
@@ -193,13 +197,14 @@ void hs_get_subcredential(const ed25519_public_key_t *identity_pk,
                           const ed25519_public_key_t *blinded_pk,
                           uint8_t *subcred_out);
 
+uint64_t hs_get_previous_time_period_num(time_t now);
 uint64_t hs_get_time_period_num(time_t now);
 uint64_t hs_get_next_time_period_num(time_t now);
 time_t hs_get_start_time_of_next_time_period(time_t now);
 
 link_specifier_t *hs_link_specifier_dup(const link_specifier_t *lspec);
 
-MOCK_DECL(int, hs_overlap_mode_is_active,
+MOCK_DECL(int, hs_in_period_between_tp_and_srv,
           (const networkstatus_t *consensus, time_t now));
 
 uint8_t *hs_get_current_srv(uint64_t time_period_num,
@@ -219,8 +224,9 @@ int32_t hs_get_hsdir_spread_fetch(void);
 int32_t hs_get_hsdir_spread_store(void);
 
 void hs_get_responsible_hsdirs(const ed25519_public_key_t *blinded_pk,
-                               uint64_t time_period_num, int is_next_period,
-                               int is_client, smartlist_t *responsible_dirs);
+                              uint64_t time_period_num,
+                              int use_second_hsdir_index,
+                              int for_fetching, smartlist_t *responsible_dirs);
 routerstatus_t *hs_pick_hsdir(smartlist_t *responsible_dirs,
                               const char *req_key_str);
 
diff --git a/src/or/hs_descriptor.h b/src/or/hs_descriptor.h
index 3e82746c35..61e7a28c2e 100644
--- a/src/or/hs_descriptor.h
+++ b/src/or/hs_descriptor.h
@@ -33,8 +33,11 @@ struct link_specifier_t;
  * which is 720 minutes or 43200 seconds. */
 #define HS_DESC_MAX_LIFETIME (12 * 60 * 60)
 /* Lifetime of certificate in the descriptor. This defines the lifetime of the
- * descriptor signing key and the cross certification cert of that key. */
-#define HS_DESC_CERT_LIFETIME (36 * 60 * 60)
+ * descriptor signing key and the cross certification cert of that key. It is
+ * set to 54 hours because a descriptor can be around for 48 hours and because
+ * consensuses are used after the hour, add an extra 6 hours to give some time
+ * for the service to stop using it. */
+#define HS_DESC_CERT_LIFETIME (54 * 60 * 60)
 /* Length of the salt needed for the encrypted section of a descriptor. */
 #define HS_DESC_ENCRYPTED_SALT_LEN 16
 /* Length of the secret input needed for the KDF construction which derives
diff --git a/src/or/hs_service.c b/src/or/hs_service.c
index 706890e34f..5759aa8127 100644
--- a/src/or/hs_service.c
+++ b/src/or/hs_service.c
@@ -23,6 +23,7 @@
 #include "router.h"
 #include "routerkeys.h"
 #include "routerlist.h"
+#include "shared_random_state.h"
 #include "statefile.h"
 
 #include "hs_circuit.h"
@@ -769,7 +770,6 @@ move_hs_state(hs_service_t *src_service, hs_service_t *dst_service)
   /* Let's do a shallow copy */
   dst->intro_circ_retry_started_time = src->intro_circ_retry_started_time;
   dst->num_intro_circ_launched = src->num_intro_circ_launched;
-  dst->in_overlap_period = src->in_overlap_period;
   dst->replay_cache_rend_cookie = src->replay_cache_rend_cookie;
 
   src->replay_cache_rend_cookie = NULL; /* steal pointer reference */
@@ -1366,28 +1366,81 @@ build_service_descriptor(hs_service_t *service, time_t now,
   service_descriptor_free(desc);
 }
 
+/* Build both descriptors for the given service that has just booted up.
+ * Because it's a special case, it deserves its special function ;). */
+static void
+build_descriptors_for_new_service(hs_service_t *service, time_t now)
+{
+  uint64_t current_desc_tp, next_desc_tp;
+
+  tor_assert(service);
+  /* These are the conditions for a new service. */
+  tor_assert(!service->desc_current);
+  tor_assert(!service->desc_next);
+
+  /*
+   * +------------------------------------------------------------------+
+   * |                                                                  |
+   * | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   * | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   * |                                                                  |
+   * |  $==========|-----------$===========|-----------$===========|    |
+   * |                             ^         ^                          |
+   * |                             A         B                          |
+   * +------------------------------------------------------------------+
+   *
+   * Case A: The service boots up before a new time period, the current time
+   * period is thus TP#1 and the next is TP#2 which for both we have access to
+   * their SRVs.
+   *
+   * Case B: The service boots up inside TP#2, we can't use the TP#3 for the
+   * next descriptor because we don't have the SRV#3 so the current should be
+   * TP#1 and next TP#2.
+   */
+
+  if (hs_in_period_between_tp_and_srv(NULL, now)) {
+    /* Case B from the above, inside of the new time period. */
+    current_desc_tp = hs_get_previous_time_period_num(0); /* TP#1 */
+    next_desc_tp = hs_get_time_period_num(0);             /* TP#2 */
+  } else {
+    /* Case A from the above, outside of the new time period. */
+    current_desc_tp = hs_get_time_period_num(0);    /* TP#1 */
+    next_desc_tp = hs_get_next_time_period_num(0);  /* TP#2 */
+  }
+
+  /* Build descriptors. */
+  build_service_descriptor(service, now, current_desc_tp,
+                           &service->desc_current);
+  build_service_descriptor(service, now, next_desc_tp,
+                           &service->desc_next);
+  log_info(LD_REND, "Hidden service %s has just started. Both descriptors "
+                    "built. Now scheduled for upload.",
+           safe_str_client(service->onion_address));
+}
+
 /* Build descriptors for each service if needed. There are conditions to build
  * a descriptor which are details in the function. */
 STATIC void
 build_all_descriptors(time_t now)
 {
   FOR_EACH_SERVICE_BEGIN(service) {
-    if (service->desc_current == NULL) {
-      /* This means we just booted up because else this descriptor will never
-       * be NULL as it should always point to the descriptor that was in
-       * desc_next after rotation. */
-      build_service_descriptor(service, now, hs_get_time_period_num(now),
-                               &service->desc_current);
-
-      log_info(LD_REND, "Hidden service %s current descriptor successfully "
-                        "built. Now scheduled for upload.",
-               safe_str_client(service->onion_address));
+
+    /* A service booting up will have both descriptors to NULL. No other cases
+     * makes both descriptor non existent. */
+    if (service->desc_current == NULL && service->desc_next == NULL) {
+      build_descriptors_for_new_service(service, now);
+      continue;
     }
-    /* A next descriptor to NULL indicate that we need to build a fresh one if
-     * we are in the overlap period for the _next_ time period since it means
-     * we either just booted or we just rotated our descriptors. */
-    if (hs_overlap_mode_is_active(NULL, now) && service->desc_next == NULL) {
-      build_service_descriptor(service, now, hs_get_next_time_period_num(now),
+
+    /* Reaching this point means we are pass bootup so at runtime. We should
+     * *never* have an empty current descriptor. If the next descriptor is
+     * empty, we'll try to build it for the next time period. This only
+     * happens when we rotate meaning that we are guaranteed to have a new SRV
+     * at that point for the next time period. */
+    tor_assert(service->desc_current);
+
+    if (service->desc_next == NULL) {
+      build_service_descriptor(service, now, hs_get_next_time_period_num(0),
                                &service->desc_next);
       log_info(LD_REND, "Hidden service %s next descriptor successfully "
                         "built. Now scheduled for upload.",
@@ -1716,53 +1769,81 @@ cleanup_intro_points(hs_service_t *service, time_t now)
   } FOR_EACH_DESCRIPTOR_END;
 }
 
-/** We just entered overlap period and we need to rotate our <b>service</b>
- *  descriptors */
+/* Set the next rotation time of the descriptors for the given service for the
+ * time now. */
 static void
-rotate_service_descriptors(hs_service_t *service)
+set_rotation_time(hs_service_t *service, time_t now)
 {
-  if (service->desc_current) {
-    /* Close all IP circuits for the descriptor. */
-    close_intro_circuits(&service->desc_current->intro_points);
-    /* We don't need this one anymore, we won't serve any clients coming with
-     * this service descriptor. */
-    service_descriptor_free(service->desc_current);
+  time_t valid_after;
+  const networkstatus_t *ns = networkstatus_get_live_consensus(now);
+  if (ns) {
+    valid_after = ns->valid_after;
+  } else {
+    valid_after = now;
+  }
+
+  tor_assert(service);
+  service->state.next_rotation_time =
+    sr_state_get_start_time_of_current_protocol_run(valid_after) +
+    sr_state_get_protocol_run_duration();
+
+  {
+    char fmt_time[ISO_TIME_LEN + 1];
+    format_local_iso_time(fmt_time, service->state.next_rotation_time);
+    log_info(LD_REND, "Next descriptor rotation time set to %s for %s",
+             fmt_time, safe_str_client(service->onion_address));
   }
-  /* The next one become the current one and emptying the next will trigger
-   * a descriptor creation for it. */
-  service->desc_current = service->desc_next;
-  service->desc_next = NULL;
 }
 
-/** Return true if <b>service</b> **just** entered overlap mode. */
-static int
-service_just_entered_overlap_mode(const hs_service_t *service,
-                                  int overlap_mode_is_active)
+/* Return true iff the service should rotate its descriptor. The time now is
+ * only used to fetch the live consensus and if none can be found, this
+ * returns false. */
+static unsigned int
+should_rotate_descriptors(hs_service_t *service, time_t now)
 {
-  if (overlap_mode_is_active && !service->state.in_overlap_period) {
-    return 1;
+  const networkstatus_t *ns;
+
+  tor_assert(service);
+
+  ns = networkstatus_get_live_consensus(now);
+  if (ns == NULL) {
+    goto no_rotation;
   }
 
+  if (ns->valid_after >= service->state.next_rotation_time) {
+    goto rotation;
+  }
+
+ no_rotation:
   return 0;
+ rotation:
+  return 1;
 }
 
-/** Return true if <b>service</b> **just** left overlap mode. */
-static int
-service_just_left_overlap_mode(const hs_service_t *service,
-                               int overlap_mode_is_active)
+/* Rotate the service descriptors of the given service. The current descriptor
+ * will be freed, the next one put in as the current and finally the next
+ * descriptor pointer is NULLified. */
+static void
+rotate_service_descriptors(hs_service_t *service, time_t now)
 {
-  if (!overlap_mode_is_active && service->state.in_overlap_period) {
-    return 1;
+  if (service->desc_current) {
+    /* Close all IP circuits for the descriptor. */
+    close_intro_circuits(&service->desc_current->intro_points);
+    /* We don't need this one anymore, we won't serve any clients coming with
+     * this service descriptor. */
+    service_descriptor_free(service->desc_current);
   }
+  /* The next one become the current one and emptying the next will trigger
+   * a descriptor creation for it. */
+  service->desc_current = service->desc_next;
+  service->desc_next = NULL;
 
-  return 0;
+  /* We've just rotated, set the next time for the rotation. */
+  set_rotation_time(service, now);
 }
 
-/* Rotate descriptors for each service if needed. If we are just entering or
- * leaving the overlap period, rotate them that is point the previous
- * descriptor to the current and cleanup the previous one. A non existing
- * current descriptor will trigger a descriptor build for the next time
- * period. */
+/* Rotate descriptors for each service if needed. A non existing current
+ * descriptor will trigger a descriptor build for the next time period. */
 STATIC void
 rotate_all_descriptors(time_t now)
 {
@@ -1770,56 +1851,26 @@ rotate_all_descriptors(time_t now)
    *     be wise, to rotate service descriptors independently to hide that all
    *     those descriptors are on the same tor instance */
 
-  int overlap_mode_is_active = hs_overlap_mode_is_active(NULL, now);
-
   FOR_EACH_SERVICE_BEGIN(service) {
-    int service_entered_overlap = service_just_entered_overlap_mode(service,
-                                                      overlap_mode_is_active);
-    int service_left_overlap = service_just_left_overlap_mode(service,
-                                             overlap_mode_is_active);
-    /* This should not be possible */
-    if (BUG(service_entered_overlap && service_left_overlap)) {
-      return;
-    }
-
-    /* No changes in overlap mode: nothing to do here */
-    if (!service_entered_overlap && !service_left_overlap) {
-      return;
-    }
-
-    /* To get down there means that some change happened to overlap mode */
-    tor_assert(service_entered_overlap || service_left_overlap);
 
-    /* Update the overlap marks on this service */
-    if (service_entered_overlap) {
-      /* It's the first time the service encounters the overlap period so flag
-       * it in order to make sure we don't rotate at next check. */
-      service->state.in_overlap_period = 1;
-    } else if (service_left_overlap) {
-      service->state.in_overlap_period = 0;
+    /* Note for a service booting up: Both descriptors are NULL in that case
+     * so this function might return true if we are in the timeframe for a
+     * rotation leading to basically swapping two NULL pointers which is
+     * harmless. However, the side effect is that triggering a rotation will
+     * update the service state and avoid doing anymore rotations after the
+     * two descriptors have been built. */
+    if (!should_rotate_descriptors(service, now)) {
+      continue;
     }
 
-    if (service_entered_overlap) {
-      /* We just entered overlap period: recompute all HSDir indices. We need
-       * to do this otherwise nodes can get stuck with old HSDir indices until
-       * we fetch a new consensus, and we might need to reupload our desc
-       * before that. */
-      /* XXX find a better place than rotate_all_descriptors() to do this */
-      nodelist_recompute_all_hsdir_indices();
-    }
+    tor_assert(service->desc_current);
+    tor_assert(service->desc_next);
 
-    /* If we just entered or left overlap mode, rotate our descriptors */
-    log_info(LD_REND, "We just %s overlap period. About to rotate %s "
-             "descriptors (%p / %p).",
-             service_entered_overlap ? "entered" : "left",
-             safe_str_client(service->onion_address),
-             service->desc_current, service->desc_next);
+    log_info(LD_REND, "Time to rotate our descriptors (%p / %p) for %s",
+             service->desc_current, service->desc_next,
+             safe_str_client(service->onion_address));
 
-    /* If we have a next descriptor lined up, rotate the descriptors so that it
-     * becomes current. */
-    if (service->desc_next) {
-      rotate_service_descriptors(service);
-    }
+    rotate_service_descriptors(service, now);
   } FOR_EACH_SERVICE_END;
 }
 
@@ -1833,6 +1884,17 @@ run_housekeeping_event(time_t now)
    * simply moving things around or removing uneeded elements. */
 
   FOR_EACH_SERVICE_BEGIN(service) {
+
+    /* If the service is starting off, set the rotation time. We can't do that
+     * at configure time because the get_options() needs to be set for setting
+     * that time that uses the voting interval. */
+    if (service->state.next_rotation_time == 0) {
+      /* Set the next rotation time of the descriptors. If it's Oct 25th
+       * 23:47:00, the next rotation time is when the next SRV is computed
+       * which is at Oct 26th 00:00:00 that is in 13 minutes. */
+      set_rotation_time(service, now);
+    }
+
     /* Cleanup invalid intro points from the service descriptor. */
     cleanup_intro_points(service, now);
 
@@ -2102,8 +2164,8 @@ upload_descriptor_to_hsdir(const hs_service_t *service,
   /* Logging so we know where it was sent. */
   {
     int is_next_desc = (service->desc_next == desc);
-    const uint8_t *index = (is_next_desc) ? hsdir->hsdir_index->next :
-                                            hsdir->hsdir_index->current;
+    const uint8_t *index = (is_next_desc) ? hsdir->hsdir_index->store_second:
+                                            hsdir->hsdir_index->store_first;
     log_info(LD_REND, "Service %s %s descriptor of revision %" PRIu64
                       " initiated upload request to %s with index %s",
              safe_str_client(service->onion_address),
@@ -2318,7 +2380,7 @@ set_descriptor_revision_counter(hs_descriptor_t *hs_desc)
  * if PublishHidServDescriptors is false. */
 STATIC void
 upload_descriptor_to_all(const hs_service_t *service,
-                         hs_service_descriptor_t *desc, int for_next_period)
+                         hs_service_descriptor_t *desc)
 {
   smartlist_t *responsible_dirs = NULL;
 
@@ -2330,7 +2392,7 @@ upload_descriptor_to_all(const hs_service_t *service,
   /* The parameter 0 means that we aren't a client so tell the function to use
    * the spread store consensus paremeter. */
   hs_get_responsible_hsdirs(&desc->blinded_kp.pubkey, desc->time_period_num,
-                            for_next_period, 0, responsible_dirs);
+                            service->desc_next == desc, 0, responsible_dirs);
 
   /** Clear list of previous hsdirs since we are about to upload to a new
    *  list. Let's keep it up to date. */
@@ -2477,8 +2539,6 @@ run_upload_descriptor_event(time_t now)
   /* Run v3+ check. */
   FOR_EACH_SERVICE_BEGIN(service) {
     FOR_EACH_DESCRIPTOR_BEGIN(service, desc) {
-      int for_next_period = 0;
-
       /* If we were asked to re-examine the hash ring, and it changed, then
          schedule an upload */
       if (consider_republishing_hs_descriptors &&
@@ -2504,13 +2564,7 @@ run_upload_descriptor_event(time_t now)
        * accurate because all circuits have been established. */
       build_desc_intro_points(service, desc, now);
 
-      /* If the service is in the overlap period and this descriptor is the
-       * next one, it has to be uploaded for the next time period meaning
-       * we'll use the next node_t hsdir_index to pick the HSDirs. */
-      if (desc == service->desc_next) {
-        for_next_period = 1;
-      }
-      upload_descriptor_to_all(service, desc, for_next_period);
+      upload_descriptor_to_all(service, desc);
     } FOR_EACH_DESCRIPTOR_END;
   } FOR_EACH_SERVICE_END;
 
@@ -3091,6 +3145,7 @@ hs_service_new(const or_options_t *options)
   /* Allocate the CLIENT_PK replay cache in service state. */
   service->state.replay_cache_rend_cookie =
     replaycache_new(REND_REPLAY_TIME_INTERVAL, REND_REPLAY_TIME_INTERVAL);
+
   return service;
 }
 
diff --git a/src/or/hs_service.h b/src/or/hs_service.h
index 317b9d795d..248df27e10 100644
--- a/src/or/hs_service.h
+++ b/src/or/hs_service.h
@@ -196,16 +196,16 @@ typedef struct hs_service_state_t {
    * should never go over MAX_INTRO_CIRCS_PER_PERIOD. */
   unsigned int num_intro_circ_launched;
 
-  /* Indicate that the service has entered the overlap period. We use this
-   * flag to check for descriptor rotation. */
-  unsigned int in_overlap_period : 1;
-
   /* Replay cache tracking the REND_COOKIE found in INTRODUCE2 cell to detect
    * repeats. Clients may send INTRODUCE1 cells for the same rendezvous point
    * through two or more different introduction points; when they do, this
    * keeps us from launching multiple simultaneous attempts to connect to the
    * same rend point. */
   replaycache_t *replay_cache_rend_cookie;
+
+  /* When is the next time we should rotate our descriptors. This is has to be
+   * done at the start time of the next SRV protocol run. */
+  time_t next_rotation_time;
 } hs_service_state_t;
 
 /* Representation of a service running on this tor instance. */
@@ -229,8 +229,7 @@ typedef struct hs_service_t {
 
   /* Current descriptor. */
   hs_service_descriptor_t *desc_current;
-  /* Next descriptor that we need for the overlap period for which we have to
-   * keep two sets of opened introduction point circuits. */
+  /* Next descriptor. */
   hs_service_descriptor_t *desc_next;
 
   /* XXX: Credential (client auth.) #20700. */
@@ -338,8 +337,7 @@ STATIC int
 write_address_to_file(const hs_service_t *service, const char *fname_);
 
 STATIC void upload_descriptor_to_all(const hs_service_t *service,
-                                     hs_service_descriptor_t *desc,
-                                     int for_next_period);
+                                     hs_service_descriptor_t *desc);
 
 STATIC void service_desc_schedule_upload(hs_service_descriptor_t *desc,
                                          time_t now,
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index 03b315e682..29ef835fba 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -38,6 +38,8 @@
  * used for authorities and fallback directories.)
  */
 
+#define NODELIST_PRIVATE
+
 #include "or.h"
 #include "address.h"
 #include "config.h"
@@ -176,13 +178,14 @@ node_get_or_create(const char *identity_digest)
 /* For a given <b>node</b> for the consensus <b>ns</b>, set the hsdir index
  * for the node, both current and next if possible. This can only fails if the
  * node_t ed25519 identity key can't be found which would be a bug. */
-static void
+STATIC void
 node_set_hsdir_index(node_t *node, const networkstatus_t *ns)
 {
   time_t now = approx_time();
   const ed25519_public_key_t *node_identity_pk;
-  uint8_t *next_hsdir_index_srv = NULL, *current_hsdir_index_srv = NULL;
+  uint8_t *fetch_srv = NULL, *store_first_srv = NULL, *store_second_srv = NULL;
   uint64_t next_time_period_num, current_time_period_num;
+  uint64_t fetch_tp, store_first_tp, store_second_tp;
 
   tor_assert(node);
   tor_assert(ns);
@@ -200,41 +203,59 @@ node_set_hsdir_index(node_t *node, const networkstatus_t *ns)
     goto done;
   }
 
-  /* Get the current and next time period number, we might use them both. */
-  current_time_period_num = hs_get_time_period_num(now);
-  next_time_period_num = hs_get_next_time_period_num(now);
-
-  if (hs_overlap_mode_is_active(ns, now)) {
-    /* We are in overlap mode, this means that our consensus has just cycled
-     * from current SRV to previous SRV so for the _next_ upcoming time
-     * period, we have to use the current SRV and use the previous SRV for the
-     * current time period. If the current or previous SRV can't be found, the
-     * disaster one is returned. */
-    next_hsdir_index_srv = hs_get_current_srv(next_time_period_num, ns);
-    /* The following can be confusing so again, in overlap mode, we use our
-     * previous SRV for our _current_ hsdir index. */
-    current_hsdir_index_srv = hs_get_previous_srv(current_time_period_num, ns);
+  /* Get the current and next time period number. */
+  current_time_period_num = hs_get_time_period_num(0);
+  next_time_period_num = hs_get_next_time_period_num(0);
+
+  /* We always use the current time period for fetching descs */
+  fetch_tp = current_time_period_num;
+
+  /* Now extract the needed SRVs and time periods for building hsdir indices */
+  if (hs_in_period_between_tp_and_srv(ns, now)) {
+    fetch_srv = hs_get_current_srv(fetch_tp, ns);
+
+    store_first_tp = hs_get_previous_time_period_num(0);
+    store_second_tp = current_time_period_num;
   } else {
-    /* If NOT in overlap mode, we only need to compute the current hsdir index
-     * for the ongoing time period and thus the current SRV. If it can't be
-     * found, the disaster one is returned. */
-    current_hsdir_index_srv = hs_get_current_srv(current_time_period_num, ns);
-  }
-
-  /* Build the current hsdir index. */
-  hs_build_hsdir_index(node_identity_pk, current_hsdir_index_srv,
-                       current_time_period_num, node->hsdir_index->current);
-  if (next_hsdir_index_srv) {
-    /* Build the next hsdir index if we have a next SRV that we can use. */
-    hs_build_hsdir_index(node_identity_pk, next_hsdir_index_srv,
-                         next_time_period_num, node->hsdir_index->next);
+    fetch_srv = hs_get_previous_srv(fetch_tp, ns);
+
+    store_first_tp = current_time_period_num;
+    store_second_tp = next_time_period_num;
+  }
+
+  /* We always use the old SRV for storing the first descriptor and the latest
+   * SRV for storing the second descriptor */
+  store_first_srv = hs_get_previous_srv(store_first_tp, ns);
+  store_second_srv = hs_get_current_srv(store_second_tp, ns);
+
+  /* Build the fetch index. */
+  hs_build_hsdir_index(node_identity_pk, fetch_srv, fetch_tp,
+                       node->hsdir_index->fetch);
+
+  /* If we are in the time segment between SRV#N and TP#N, the fetch index is
+     the same as the first store index */
+  if (!hs_in_period_between_tp_and_srv(ns, now)) {
+    memcpy(node->hsdir_index->store_first, node->hsdir_index->fetch,
+           sizeof(node->hsdir_index->store_first));
+  } else {
+    hs_build_hsdir_index(node_identity_pk, store_first_srv, store_first_tp,
+                         node->hsdir_index->store_first);
+  }
+
+  /* If we are in the time segment between TP#N and SRV#N+1, the fetch index is
+     the same as the second store index */
+  if (hs_in_period_between_tp_and_srv(ns, now)) {
+    memcpy(node->hsdir_index->store_second, node->hsdir_index->fetch,
+           sizeof(node->hsdir_index->store_second));
   } else {
-    memset(node->hsdir_index->next, 0, sizeof(node->hsdir_index->next));
+    hs_build_hsdir_index(node_identity_pk, store_second_srv, store_second_tp,
+                         node->hsdir_index->store_second);
   }
 
  done:
-  tor_free(current_hsdir_index_srv);
-  tor_free(next_hsdir_index_srv);
+  tor_free(fetch_srv);
+  tor_free(store_first_srv);
+  tor_free(store_second_srv);
   return;
 }
 
diff --git a/src/or/nodelist.h b/src/or/nodelist.h
index 9676263f75..318bf0e794 100644
--- a/src/or/nodelist.h
+++ b/src/or/nodelist.h
@@ -136,5 +136,16 @@ void router_dir_info_changed(void);
 const char *get_dir_info_status_string(void);
 int count_loading_descriptors_progress(void);
 
+#ifdef NODELIST_PRIVATE
+
+#ifdef TOR_UNIT_TESTS
+
+STATIC void
+node_set_hsdir_index(node_t *node, const networkstatus_t *ns);
+
+#endif /* TOR_UNIT_TESTS */
+
+#endif /* NODELIST_PRIVATE */
+
 #endif
 
diff --git a/src/test/test_hs_common.c b/src/test/test_hs_common.c
index 9980892951..b0e7f5e1e7 100644
--- a/src/test/test_hs_common.c
+++ b/src/test/test_hs_common.c
@@ -7,7 +7,9 @@
  */
 
 #define HS_COMMON_PRIVATE
+#define HS_CLIENT_PRIVATE
 #define HS_SERVICE_PRIVATE
+#define NODELIST_PRIVATE
 
 #include "test.h"
 #include "test_helpers.h"
@@ -16,6 +18,7 @@
 
 #include "connection_edge.h"
 #include "hs_common.h"
+#include "hs_client.h"
 #include "hs_service.h"
 #include "config.h"
 #include "networkstatus.h"
@@ -23,6 +26,9 @@
 #include "nodelist.h"
 #include "routerlist.h"
 #include "statefile.h"
+#include "circuitlist.h"
+#include "shared_random.h"
+#include "util.h"
 
 /** Test the validation of HS v3 addresses */
 static void
@@ -250,115 +256,17 @@ test_start_time_of_next_time_period(void *arg)
   ;
 }
 
-/** Test that our HS overlap period functions work properly. */
+/* Cleanup the global nodelist. It also frees the "md" in the node_t because
+ * we allocate the memory in helper_add_hsdir_to_networkstatus(). */
 static void
-test_desc_overlap_period(void *arg)
+cleanup_nodelist(void)
 {
-  (void) arg;
-  int retval;
-  time_t now = time(NULL);
-  networkstatus_t *dummy_consensus = NULL;
-
-  /* First try with a consensus just inside the overlap period */
-  dummy_consensus = tor_malloc_zero(sizeof(networkstatus_t));
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 00:00:00 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 1);
-
-  /* Now increase the valid_after so that it goes to 11:00:00 UTC. Overlap
-     period is still active. */
-  dummy_consensus->valid_after += 3600*11;
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 1);
-
-  /* Now increase the valid_after so that it goes to 11:59:59 UTC. Overlap
-     period is still active. */
-  dummy_consensus->valid_after += 3599;
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 1);
-
-  /* Now increase the valid_after so that it drifts to noon, and check that
-     overlap mode is not active anymore. */
-  dummy_consensus->valid_after += 1;
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 0);
-
-  /* Check that overlap mode is also inactive at 23:59:59 UTC */
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 23:59:59 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 0);
-
- done:
-  tor_free(dummy_consensus);
-}
-
-/* Test the overlap period functions on a testnet with altered voting
- * schedule */
-static void
-test_desc_overlap_period_testnet(void *arg)
-{
-  int retval;
-  time_t now = approx_time();
-  networkstatus_t *dummy_consensus = NULL;
-  or_options_t *options = get_options_mutable();
-
-  (void) arg;
-
-  /* Set the testnet option and a 10-second voting interval */
-  options->TestingTorNetwork = 1;
-  options->V3AuthVotingInterval = 10;
-  options->TestingV3AuthInitialVotingInterval = 10;
-
-  dummy_consensus = tor_malloc_zero(sizeof(networkstatus_t));
-
-  /* A 10-second voting interval means that the lengths of an SRV run and of a
-   * time period are both 10*24 seconds (4 minutes). The SRV gets published at
-   * 00:00:00 and the TP starts at 00:02:00 (rotation offset: 2 mins). Those
-   * two minutes between SRV publish and TP start is the overlap period
-   * window. Let's test it: */
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 00:00:00 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 1);
-
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 00:01:59 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 1);
-
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 00:02:00 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 0);
-
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 00:04:00 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 1);
-
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 00:05:59 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 1);
-
-  retval = parse_rfc1123_time("Wed, 13 Apr 2016 00:06:00 UTC",
-                              &dummy_consensus->valid_after);
-  tt_int_op(retval, OP_EQ, 0);
-  retval = hs_overlap_mode_is_active(dummy_consensus, now);
-  tt_int_op(retval, OP_EQ, 0);
-
- done:
-  tor_free(dummy_consensus);
+  smartlist_t *nodelist = nodelist_get_list();
+  SMARTLIST_FOREACH_BEGIN(nodelist, node_t *, node) {
+    tor_free(node->md);
+    node->md = NULL;
+  } SMARTLIST_FOREACH_END(node);
+  nodelist_free_all();
 }
 
 static void
@@ -370,11 +278,9 @@ helper_add_hsdir_to_networkstatus(networkstatus_t *ns,
   routerstatus_t *rs = tor_malloc_zero(sizeof(routerstatus_t));
   routerinfo_t *ri = tor_malloc_zero(sizeof(routerinfo_t));
   uint8_t identity[DIGEST_LEN];
-  uint8_t curr_hsdir_index[DIGEST256_LEN];
   tor_addr_t ipv4_addr;
 
   memset(identity, identity_idx, sizeof(identity));
-  memset(curr_hsdir_index, identity_idx, sizeof(curr_hsdir_index));
 
   memcpy(rs->identity_digest, identity, DIGEST_LEN);
   rs->is_hs_dir = is_hsdir;
@@ -386,12 +292,20 @@ helper_add_hsdir_to_networkstatus(networkstatus_t *ns,
   ri->nickname = tor_strdup(nickname);
   ri->protocol_list = tor_strdup("HSDir=1-2 LinkAuth=3");
   memcpy(ri->cache_info.identity_digest, identity, DIGEST_LEN);
+  ri->cache_info.signing_key_cert = tor_malloc_zero(sizeof(tor_cert_t));
+  /* Needed for the HSDir index computation. */
+  memset(&ri->cache_info.signing_key_cert->signing_key,
+         identity_idx, ED25519_PUBKEY_LEN);
   tt_assert(nodelist_set_routerinfo(ri, NULL));
   node_t *node = node_get_mutable_by_id(ri->cache_info.identity_digest);
   tt_assert(node);
   node->rs = rs;
-  memcpy(node->hsdir_index->current, curr_hsdir_index,
-         sizeof(node->hsdir_index->current));
+  /* We need this to exist for node_has_descriptor() to return true. */
+  node->md = tor_malloc_zero(sizeof(microdesc_t));
+  /* Do this now the nodelist_set_routerinfo() function needs a "rs" to set
+   * the indexes which it doesn't have when it is called. */
+  node_set_hsdir_index(node, ns);
+  node->ri = NULL;
   smartlist_add(ns->routerstatus_list, rs);
 
  done:
@@ -424,6 +338,17 @@ mock_networkstatus_get_latest_consensus(void)
   return mock_ns;
 }
 
+static networkstatus_t *
+mock_networkstatus_get_live_consensus(time_t now)
+{
+  (void) now;
+
+  tt_assert(mock_ns);
+
+ done:
+  return mock_ns;
+}
+
 /** Test the responsible HSDirs calculation function */
 static void
 test_responsible_hsdirs(void *arg)
@@ -474,6 +399,7 @@ test_responsible_hsdirs(void *arg)
   smartlist_free(responsible_dirs);
   smartlist_clear(ns->routerstatus_list);
   networkstatus_vote_free(mock_ns);
+  cleanup_nodelist();
 }
 
 static void
@@ -576,7 +502,7 @@ test_desc_reupload_logic(void *arg)
   }
 
   /* Now let's upload our desc to all hsdirs */
-  upload_descriptor_to_all(service, desc, 0);
+  upload_descriptor_to_all(service, desc);
   /* Check that previous hsdirs were populated */
   tt_int_op(smartlist_len(desc->previous_hsdirs), OP_EQ, 6);
 
@@ -593,7 +519,7 @@ test_desc_reupload_logic(void *arg)
     SMARTLIST_FOREACH(ns->routerstatus_list,
                       routerstatus_t *, rs, routerstatus_free(rs));
     smartlist_clear(ns->routerstatus_list);
-    nodelist_free_all();
+    cleanup_nodelist();
     routerlist_free_all();
   }
 
@@ -614,7 +540,7 @@ test_desc_reupload_logic(void *arg)
   tt_int_op(smartlist_len(desc->previous_hsdirs), OP_EQ, 6);
 
   /* Now order another upload and see that we keep having 6 prev hsdirs */
-  upload_descriptor_to_all(service, desc, 0);
+  upload_descriptor_to_all(service, desc);
   /* Check that previous hsdirs were populated */
   tt_int_op(smartlist_len(desc->previous_hsdirs), OP_EQ, 6);
 
@@ -625,7 +551,7 @@ test_desc_reupload_logic(void *arg)
     SMARTLIST_FOREACH(ns->routerstatus_list,
                       routerstatus_t *, rs, routerstatus_free(rs));
     smartlist_clear(ns->routerstatus_list);
-    nodelist_free_all();
+    cleanup_nodelist();
     routerlist_free_all();
   }
 
@@ -647,7 +573,7 @@ test_desc_reupload_logic(void *arg)
   tt_int_op(smartlist_len(desc->previous_hsdirs), OP_EQ, 0);
 
   /* Now reupload again: see that the prev hsdir set got populated again. */
-  upload_descriptor_to_all(service, desc, 0);
+  upload_descriptor_to_all(service, desc);
   tt_int_op(smartlist_len(desc->previous_hsdirs), OP_EQ, 6);
 
  done:
@@ -655,7 +581,7 @@ test_desc_reupload_logic(void *arg)
                     routerstatus_t *, rs, routerstatus_free(rs));
   smartlist_clear(ns->routerstatus_list);
   networkstatus_vote_free(ns);
-  nodelist_free_all();
+  cleanup_nodelist();
   hs_free_all();
 }
 
@@ -851,6 +777,880 @@ test_parse_extended_hostname(void *arg)
  done: ;
 }
 
+static void
+test_time_between_tp_and_srv(void *arg)
+{
+  int ret;
+  networkstatus_t ns;
+  (void) arg;
+
+  /* This function should be returning true where "^" are:
+   *
+   *    +------------------------------------------------------------------+
+   *    |                                                                  |
+   *    | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *    | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *    |                                                                  |
+   *    |  $==========|-----------$===========|-----------$===========|    |
+   *    |             ^^^^^^^^^^^^            ^^^^^^^^^^^^                 |
+   *    |                                                                  |
+   *    +------------------------------------------------------------------+
+   */
+
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 00:00:00 UTC", &ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
+  ret = hs_in_period_between_tp_and_srv(&ns, 0);
+  tt_int_op(ret, OP_EQ, 0);
+
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 11:00:00 UTC", &ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
+  ret = hs_in_period_between_tp_and_srv(&ns, 0);
+  tt_int_op(ret, OP_EQ, 0);
+
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 12:00:00 UTC", &ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
+  ret = hs_in_period_between_tp_and_srv(&ns, 0);
+  tt_int_op(ret, OP_EQ, 1);
+
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 23:00:00 UTC", &ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
+  ret = hs_in_period_between_tp_and_srv(&ns, 0);
+  tt_int_op(ret, OP_EQ, 1);
+
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 00:00:00 UTC", &ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
+  ret = hs_in_period_between_tp_and_srv(&ns, 0);
+  tt_int_op(ret, OP_EQ, 0);
+
+ done:
+  ;
+}
+
+/************ Reachability Test (it is huge) ****************/
+
+/* Simulate different consensus for client and service. Used by the
+ * reachability test. The SRV and responsible HSDir list are used by all
+ * reachability tests so make them common to simplify setup and teardown. */
+static networkstatus_t *mock_service_ns = NULL;
+static networkstatus_t *mock_client_ns = NULL;
+static sr_srv_t current_srv, previous_srv;
+static smartlist_t *service_responsible_hsdirs = NULL;
+static smartlist_t *client_responsible_hsdirs = NULL;
+
+static networkstatus_t *
+mock_networkstatus_get_live_consensus_service(time_t now)
+{
+  (void) now;
+
+  if (mock_service_ns) {
+    return mock_service_ns;
+  }
+
+  mock_service_ns = tor_malloc_zero(sizeof(networkstatus_t));
+  mock_service_ns->routerstatus_list = smartlist_new();
+  mock_service_ns->type = NS_TYPE_CONSENSUS;
+
+  return mock_service_ns;
+}
+
+static networkstatus_t *
+mock_networkstatus_get_latest_consensus_service(void)
+{
+  return mock_networkstatus_get_live_consensus_service(0);
+}
+
+static networkstatus_t *
+mock_networkstatus_get_live_consensus_client(time_t now)
+{
+  (void) now;
+
+  if (mock_client_ns) {
+    return mock_client_ns;
+  }
+
+  mock_client_ns = tor_malloc_zero(sizeof(networkstatus_t));
+  mock_client_ns->routerstatus_list = smartlist_new();
+  mock_client_ns->type = NS_TYPE_CONSENSUS;
+
+  return mock_client_ns;
+}
+
+static networkstatus_t *
+mock_networkstatus_get_latest_consensus_client(void)
+{
+  return mock_networkstatus_get_live_consensus_client(0);
+}
+
+/* Mock function because we are not trying to test the close circuit that does
+ * an awful lot of checks on the circuit object. */
+static void
+mock_circuit_mark_for_close(circuit_t *circ, int reason, int line,
+                            const char *file)
+{
+  (void) circ;
+  (void) reason;
+  (void) line;
+  (void) file;
+  return;
+}
+
+/* Initialize a big HSDir V3 hash ring. */
+static void
+helper_initialize_big_hash_ring(networkstatus_t *ns)
+{
+  int ret;
+
+  /* Generate 250 hsdirs! :) */
+  for (int counter = 1 ; counter < 251 ; counter++) {
+    /* Let's generate random nickname for each hsdir... */
+    char nickname_binary[8];
+    char nickname_str[13] = {0};
+    crypto_rand(nickname_binary, sizeof(nickname_binary));
+    ret = base64_encode(nickname_str, sizeof(nickname_str),
+                        nickname_binary, sizeof(nickname_binary), 0);
+    tt_int_op(ret, OP_EQ, 12);
+    helper_add_hsdir_to_networkstatus(ns, counter, nickname_str, 1);
+  }
+
+  /* Make sure we have 200 hsdirs in our list */
+  tt_int_op(smartlist_len(ns->routerstatus_list), OP_EQ, 250);
+
+ done:
+  ;
+}
+
+/** Initialize service and publish its descriptor as needed. Return the newly
+ *  allocated service object to the caller. */
+static hs_service_t *
+helper_init_service(time_t now)
+{
+  int retval;
+  hs_service_t *service = hs_service_new(get_options());
+  tt_assert(service);
+  service->config.version = HS_VERSION_THREE;
+  ed25519_secret_key_generate(&service->keys.identity_sk, 0);
+  ed25519_public_key_generate(&service->keys.identity_pk,
+                              &service->keys.identity_sk);
+  /* Register service to global map. */
+  retval = register_service(get_hs_service_map(), service);
+  tt_int_op(retval, OP_EQ, 0);
+
+  /* Initialize service descriptor */
+  build_all_descriptors(now);
+  tt_assert(service->desc_current);
+  tt_assert(service->desc_next);
+
+ done:
+  return service;
+}
+
+/* Helper function to set the RFC 1123 time string into t. */
+static void
+set_consensus_times(const char *time, time_t *t)
+{
+  tt_assert(time);
+  tt_assert(t);
+
+  int ret = parse_rfc1123_time(time, t);
+  tt_int_op(ret, OP_EQ, 0);
+
+ done:
+  return;
+}
+
+/* Helper function to cleanup the mock consensus (client and service) */
+static void
+cleanup_mock_ns(void)
+{
+  if (mock_service_ns) {
+    SMARTLIST_FOREACH(mock_service_ns->routerstatus_list,
+                      routerstatus_t *, rs, routerstatus_free(rs));
+    smartlist_clear(mock_service_ns->routerstatus_list);
+    mock_service_ns->sr_info.current_srv = NULL;
+    mock_service_ns->sr_info.previous_srv = NULL;
+    networkstatus_vote_free(mock_service_ns);
+    mock_service_ns = NULL;
+  }
+
+  if (mock_client_ns) {
+    SMARTLIST_FOREACH(mock_client_ns->routerstatus_list,
+                      routerstatus_t *, rs, routerstatus_free(rs));
+    smartlist_clear(mock_client_ns->routerstatus_list);
+    mock_client_ns->sr_info.current_srv = NULL;
+    mock_client_ns->sr_info.previous_srv = NULL;
+    networkstatus_vote_free(mock_client_ns);
+    mock_client_ns = NULL;
+  }
+}
+
+/* Helper function to setup a reachability test. Once called, the
+ * cleanup_reachability_test MUST be called at the end. */
+static void
+setup_reachability_test(void)
+{
+  MOCK(circuit_mark_for_close_, mock_circuit_mark_for_close);
+  MOCK(get_or_state, get_or_state_replacement);
+
+  hs_init();
+
+  /* Baseline to start with. */
+  memset(&current_srv, 0, sizeof(current_srv));
+  memset(&previous_srv, 1, sizeof(previous_srv));
+
+  /* Initialize the consensuses. */
+  mock_networkstatus_get_latest_consensus_service();
+  mock_networkstatus_get_latest_consensus_client();
+
+  service_responsible_hsdirs = smartlist_new();
+  client_responsible_hsdirs = smartlist_new();
+}
+
+/* Helper function to cleanup a reachability test initial setup. */
+static void
+cleanup_reachability_test(void)
+{
+  smartlist_free(service_responsible_hsdirs);
+  service_responsible_hsdirs = NULL;
+  smartlist_free(client_responsible_hsdirs);
+  client_responsible_hsdirs = NULL;
+  hs_free_all();
+  cleanup_mock_ns();
+  UNMOCK(get_or_state);
+  UNMOCK(circuit_mark_for_close_);
+}
+
+/* A reachability test always check if the resulting service and client
+ * responsible HSDir for the given parameters are equal.
+ *
+ * Return true iff the same exact nodes are in both list. */
+static int
+are_responsible_hsdirs_equal(void)
+{
+  int count = 0;
+  tt_int_op(smartlist_len(client_responsible_hsdirs), OP_EQ, 6);
+  tt_int_op(smartlist_len(service_responsible_hsdirs), OP_EQ, 6);
+
+  SMARTLIST_FOREACH_BEGIN(client_responsible_hsdirs,
+                          const routerstatus_t *, c_rs) {
+    SMARTLIST_FOREACH_BEGIN(service_responsible_hsdirs,
+                            const routerstatus_t *, s_rs) {
+      if (tor_memeq(c_rs->identity_digest, s_rs->identity_digest,
+                    DIGEST_LEN)) {
+        count++;
+        break;
+      }
+    } SMARTLIST_FOREACH_END(s_rs);
+  } SMARTLIST_FOREACH_END(c_rs);
+
+ done:
+  return (count == 6);
+}
+
+/* Tor doesn't use such a function to get the previous HSDir, it is only used
+ * in node_set_hsdir_index(). We need it here so we can test the reachability
+ * scenario 6 that requires the previous time period to compute the list of
+ * responsible HSDir because of the client state timing. */
+static uint64_t
+get_previous_time_period(time_t now)
+{
+  return hs_get_time_period_num(now) - 1;
+}
+
+/* Configuration of a reachability test scenario. */
+typedef struct reachability_cfg_t {
+  /* Consensus timings to be set. They have to be compliant with
+   * RFC 1123 time format. */
+  const char *service_valid_after;
+  const char *service_valid_until;
+  const char *client_valid_after;
+  const char *client_valid_until;
+
+  /* SRVs that the service and client should use. */
+  sr_srv_t *service_current_srv;
+  sr_srv_t *service_previous_srv;
+  sr_srv_t *client_current_srv;
+  sr_srv_t *client_previous_srv;
+
+  /* A time period function for the service to use for this scenario. For a
+   * successful reachability test, the client always use the current time
+   * period thus why no client function. */
+  uint64_t (*service_time_period_fn)(time_t);
+
+  /* Is the client and service expected to be in a new time period. After
+   * setting the consensus time, the reachability test checks
+   * hs_in_period_between_tp_and_srv() and test the returned value against
+   * this. */
+  unsigned int service_in_new_tp;
+  unsigned int client_in_new_tp;
+
+  /* Some scenario requires a hint that the client, because of its consensus
+   * time, will request the "next" service descriptor so this indicates if it
+   * is the case or not. */
+  unsigned int client_fetch_next_desc;
+} reachability_cfg_t;
+
+/* Some defines to help with semantic while reading a configuration below. */
+#define NOT_IN_NEW_TP 0
+#define IN_NEW_TP 1
+#define DONT_NEED_NEXT_DESC 0
+#define NEED_NEXT_DESC 1
+
+static reachability_cfg_t reachability_scenarios[] = {
+  /* Scenario 1
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |              ^ ^                                                 |
+   *  |              S C                                                 |
+   *  +------------------------------------------------------------------+
+   *
+   *  S: Service, C: Client
+   *
+   *  Service consensus valid_after time is set to 13:00 and client to 15:00,
+   *  both are after TP#1 thus have access to SRV#1. Service and client should
+   *  be using TP#1.
+   */
+
+  { "Sat, 26 Oct 1985 13:00:00 UTC", /* Service valid_after */
+    "Sat, 26 Oct 1985 14:00:00 UTC", /* Service valid_until */
+    "Sat, 26 Oct 1985 15:00:00 UTC", /* Client valid_after */
+    "Sat, 26 Oct 1985 16:00:00 UTC", /* Client valid_until. */
+    &current_srv, NULL, /* Service current and previous SRV */
+    &current_srv, NULL, /* Client current and previous SRV */
+    hs_get_time_period_num, /* Service time period function. */
+    IN_NEW_TP, /* Is service in new TP? */
+    IN_NEW_TP, /* Is client in new TP? */
+    NEED_NEXT_DESC },
+
+  /* Scenario 2
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |                        ^ ^                                       |
+   *  |                        S C                                       |
+   *  +------------------------------------------------------------------+
+   *
+   *  S: Service, C: Client
+   *
+   *  Service consensus valid_after time is set to 23:00 and client to 01:00,
+   *  which makes the client after the SRV#2 and the service just before. The
+   *  service should only be using TP#1. The client should be using TP#1.
+   */
+
+  { "Sat, 26 Oct 1985 23:00:00 UTC", /* Service valid_after */
+    "Sat, 27 Oct 1985 00:00:00 UTC", /* Service valid_until */
+    "Sat, 27 Oct 1985 01:00:00 UTC", /* Client valid_after */
+    "Sat, 27 Oct 1985 02:00:00 UTC", /* Client valid_until. */
+    &previous_srv, NULL, /* Service current and previous SRV */
+    &current_srv, &previous_srv, /* Client current and previous SRV */
+    hs_get_time_period_num, /* Service time period function. */
+    IN_NEW_TP, /* Is service in new TP? */
+    NOT_IN_NEW_TP, /* Is client in new TP? */
+    NEED_NEXT_DESC },
+
+  /* Scenario 3
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|----------$===========|     |
+   *  |                            ^ ^                                   |
+   *  |                            S C                                   |
+   *  +------------------------------------------------------------------+
+   *
+   *  S: Service, C: Client
+   *
+   *  Service consensus valid_after time is set to 03:00 and client to 05:00,
+   *  which makes both after SRV#2. The service should be using TP#1 as its
+   *  current time period. The client should be using TP#1.
+   */
+
+  { "Sat, 27 Oct 1985 03:00:00 UTC", /* Service valid_after */
+    "Sat, 27 Oct 1985 04:00:00 UTC", /* Service valid_until */
+    "Sat, 27 Oct 1985 05:00:00 UTC", /* Client valid_after */
+    "Sat, 27 Oct 1985 06:00:00 UTC", /* Client valid_until. */
+    &current_srv, &previous_srv, /* Service current and previous SRV */
+    &current_srv, &previous_srv, /* Client current and previous SRV */
+    hs_get_time_period_num, /* Service time period function. */
+    NOT_IN_NEW_TP, /* Is service in new TP? */
+    NOT_IN_NEW_TP, /* Is client in new TP? */
+    DONT_NEED_NEXT_DESC },
+
+  /* Scenario 4
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |                                    ^ ^                           |
+   *  |                                    S C                           |
+   *  +------------------------------------------------------------------+
+   *
+   *  S: Service, C: Client
+   *
+   *  Service consensus valid_after time is set to 11:00 and client to 13:00,
+   *  which makes the service before TP#2 and the client just after. The
+   *  service should be using TP#1 as its current time period and TP#2 as the
+   *  next. The client should be using TP#2 time period.
+   */
+
+  { "Sat, 27 Oct 1985 11:00:00 UTC", /* Service valid_after */
+    "Sat, 27 Oct 1985 12:00:00 UTC", /* Service valid_until */
+    "Sat, 27 Oct 1985 13:00:00 UTC", /* Client valid_after */
+    "Sat, 27 Oct 1985 14:00:00 UTC", /* Client valid_until. */
+    &current_srv, &previous_srv, /* Service current and previous SRV */
+    &current_srv, &previous_srv, /* Client current and previous SRV */
+    hs_get_next_time_period_num, /* Service time period function. */
+    NOT_IN_NEW_TP, /* Is service in new TP? */
+    IN_NEW_TP, /* Is client in new TP? */
+    NEED_NEXT_DESC },
+
+  /* Scenario 5
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |                        ^ ^                                       |
+   *  |                        C S                                       |
+   *  +------------------------------------------------------------------+
+   *
+   *  S: Service, C: Client
+   *
+   *  Service consensus valid_after time is set to 01:00 and client to 23:00,
+   *  which makes the service after SRV#2 and the client just before. The
+   *  service should be using TP#1 as its current time period and TP#2 as the
+   *  next. The client should be using TP#1 time period.
+   */
+
+  { "Sat, 27 Oct 1985 01:00:00 UTC", /* Service valid_after */
+    "Sat, 27 Oct 1985 02:00:00 UTC", /* Service valid_until */
+    "Sat, 26 Oct 1985 23:00:00 UTC", /* Client valid_after */
+    "Sat, 27 Oct 1985 00:00:00 UTC", /* Client valid_until. */
+    &current_srv, &previous_srv, /* Service current and previous SRV */
+    &previous_srv, NULL, /* Client current and previous SRV */
+    hs_get_time_period_num, /* Service time period function. */
+    NOT_IN_NEW_TP, /* Is service in new TP? */
+    IN_NEW_TP, /* Is client in new TP? */
+    DONT_NEED_NEXT_DESC },
+
+  /* Scenario 6
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |                                    ^ ^                           |
+   *  |                                    C S                           |
+   *  +------------------------------------------------------------------+
+   *
+   *  S: Service, C: Client
+   *
+   *  Service consensus valid_after time is set to 13:00 and client to 11:00,
+   *  which makes the service outside after TP#2 and the client just before.
+   *  The service should be using TP#1 as its current time period and TP#2 as
+   *  its next. The client should be using TP#1 time period.
+   */
+
+  { "Sat, 27 Oct 1985 13:00:00 UTC", /* Service valid_after */
+    "Sat, 27 Oct 1985 14:00:00 UTC", /* Service valid_until */
+    "Sat, 27 Oct 1985 11:00:00 UTC", /* Client valid_after */
+    "Sat, 27 Oct 1985 12:00:00 UTC", /* Client valid_until. */
+    &current_srv, &previous_srv, /* Service current and previous SRV */
+    &current_srv, &previous_srv, /* Client current and previous SRV */
+    get_previous_time_period, /* Service time period function. */
+    IN_NEW_TP, /* Is service in new TP? */
+    NOT_IN_NEW_TP, /* Is client in new TP? */
+    DONT_NEED_NEXT_DESC },
+
+  /* End marker. */
+  { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, 0, 0, 0}
+};
+
+/* Run a single reachability scenario. num_scenario is the corresponding
+ * scenario number from the documentation. It is used to log it in case of
+ * failure so we know which scenario fails. */
+static int
+run_reachability_scenario(const reachability_cfg_t *cfg, int num_scenario)
+{
+  int ret = -1;
+  hs_service_t *service;
+  uint64_t service_tp, client_tp;
+  ed25519_public_key_t service_blinded_pk, client_blinded_pk;
+
+  setup_reachability_test();
+
+  tt_assert(cfg);
+
+  /* Set service consensus time. */
+  set_consensus_times(cfg->service_valid_after,
+                      &mock_service_ns->valid_after);
+  set_consensus_times(cfg->service_valid_until,
+                      &mock_service_ns->valid_until);
+  set_consensus_times(cfg->service_valid_until,
+                      &mock_service_ns->fresh_until);
+  /* Set client consensus time. */
+  set_consensus_times(cfg->client_valid_after,
+                      &mock_client_ns->valid_after);
+  set_consensus_times(cfg->client_valid_until,
+                      &mock_client_ns->valid_until);
+  set_consensus_times(cfg->client_valid_until,
+                      &mock_client_ns->fresh_until);
+
+  /* New time period checks for this scenario. */
+  tt_int_op(hs_in_period_between_tp_and_srv(mock_service_ns, 0), OP_EQ,
+            cfg->service_in_new_tp);
+  tt_int_op(hs_in_period_between_tp_and_srv(mock_client_ns, 0), OP_EQ,
+            cfg->client_in_new_tp);
+
+  /* Set the SRVs for this scenario. */
+  mock_client_ns->sr_info.current_srv = cfg->client_current_srv;
+  mock_client_ns->sr_info.previous_srv = cfg->client_previous_srv;
+  mock_service_ns->sr_info.current_srv = cfg->service_current_srv;
+  mock_service_ns->sr_info.previous_srv = cfg->service_previous_srv;
+
+  /* Initialize a service to get keys. */
+  service = helper_init_service(time(NULL));
+
+  /*
+   * === Client setup ===
+   */
+
+  MOCK(networkstatus_get_live_consensus,
+       mock_networkstatus_get_live_consensus_client);
+  MOCK(networkstatus_get_latest_consensus,
+       mock_networkstatus_get_latest_consensus_client);
+
+  /* Make networkstatus_is_live() happy. */
+  update_approx_time(mock_client_ns->valid_after);
+  /* Initialize a big hashring for this consensus with the hsdir index set. */
+  helper_initialize_big_hash_ring(mock_client_ns);
+
+  /* Client ONLY use the current time period. This is the whole point of these
+   * reachability test that is to make sure the client can always reach the
+   * service using only its current time period. */
+  client_tp = hs_get_time_period_num(0);
+
+  hs_build_blinded_pubkey(&service->keys.identity_pk, NULL, 0,
+                          client_tp, &client_blinded_pk);
+  hs_get_responsible_hsdirs(&client_blinded_pk, client_tp, 0, 1,
+                            client_responsible_hsdirs);
+  /* Cleanup the nodelist so we can let the service computes its own set of
+   * node with its own hashring. */
+  cleanup_nodelist();
+  tt_int_op(smartlist_len(client_responsible_hsdirs), OP_EQ, 6);
+
+  UNMOCK(networkstatus_get_latest_consensus);
+  UNMOCK(networkstatus_get_live_consensus);
+
+  /*
+   * === Service setup ===
+   */
+
+  MOCK(networkstatus_get_live_consensus,
+       mock_networkstatus_get_live_consensus_service);
+  MOCK(networkstatus_get_latest_consensus,
+       mock_networkstatus_get_latest_consensus_service);
+
+  /* Make networkstatus_is_live() happy. */
+  update_approx_time(mock_service_ns->valid_after);
+  /* Initialize a big hashring for this consensus with the hsdir index set. */
+  helper_initialize_big_hash_ring(mock_service_ns);
+
+  service_tp = cfg->service_time_period_fn(0);
+
+  hs_build_blinded_pubkey(&service->keys.identity_pk, NULL, 0,
+                          service_tp, &service_blinded_pk);
+
+  /* A service builds two lists of responsible HSDir, for the current and the
+   * next descriptor. Depending on the scenario, the client timing indicate if
+   * it is fetching the current or the next descriptor so we use the
+   * "client_fetch_next_desc" to know which one the client is trying to get to
+   * confirm that the service computes the same hashring for the same blinded
+   * key and service time period function. */
+  hs_get_responsible_hsdirs(&service_blinded_pk, service_tp,
+                            cfg->client_fetch_next_desc, 0,
+                            service_responsible_hsdirs);
+  cleanup_nodelist();
+  tt_int_op(smartlist_len(service_responsible_hsdirs), OP_EQ, 6);
+
+  UNMOCK(networkstatus_get_latest_consensus);
+  UNMOCK(networkstatus_get_live_consensus);
+
+  /* Some testing of the values we just got from the client and service. */
+  tt_mem_op(&client_blinded_pk, OP_EQ, &service_blinded_pk,
+            ED25519_PUBKEY_LEN);
+  tt_int_op(are_responsible_hsdirs_equal(), OP_EQ, 1);
+
+  /* Everything went well. */
+  ret = 0;
+
+ done:
+  cleanup_reachability_test();
+  if (ret == -1) {
+    /* Do this so we can know which scenario failed. */
+    char msg[32];
+    tor_snprintf(msg, sizeof(msg), "Scenario %d failed", num_scenario);
+    tt_fail_msg(msg);
+  }
+  return ret;
+}
+
+static void
+test_reachability(void *arg)
+{
+  (void) arg;
+
+  /* NOTE: An important axiom to understand here is that SRV#N must only be
+   * used with TP#N value. For example, SRV#2 with TP#1 should NEVER be used
+   * together. The HSDir index computation is based on this axiom.*/
+
+  for (int i = 0; reachability_scenarios[i].service_valid_after; ++i) {
+    int ret = run_reachability_scenario(&reachability_scenarios[i], i + 1);
+    if (ret < 0) {
+      return;
+    }
+  }
+}
+
+/** Pick an HSDir for service with <b>onion_identity_pk</b> as a client. Put
+ *  its identity digest in <b>hsdir_digest_out</b>. */
+static void
+helper_client_pick_hsdir(const ed25519_public_key_t *onion_identity_pk,
+                        char *hsdir_digest_out)
+{
+  tt_assert(onion_identity_pk);
+
+  routerstatus_t *client_hsdir = pick_hsdir_v3(onion_identity_pk);
+  tt_assert(client_hsdir);
+  digest_to_base64(hsdir_digest_out, client_hsdir->identity_digest);
+
+ done:
+  ;
+}
+
+/** Set the consensus and system time based on <b>between_srv_and_tp</b>. If
+ *  <b>between_srv_and_tp</b> is set, then set the time to be inside the time
+ *  segment between SRV#N and TP#N. */
+static time_t
+helper_set_consensus_and_system_time(networkstatus_t *ns,
+                                     int between_srv_and_tp)
+{
+  time_t real_time;
+
+  /* The period between SRV#N and TP#N is from 00:00 to 12:00 UTC. Consensus
+   * valid_after is what matters here, the rest is just to specify the voting
+   * period correctly. */
+  if (between_srv_and_tp) {
+    parse_rfc1123_time("Wed, 13 Apr 2016 11:00:00 UTC", &ns->valid_after);
+    parse_rfc1123_time("Wed, 13 Apr 2016 12:00:00 UTC", &ns->fresh_until);
+    parse_rfc1123_time("Wed, 13 Apr 2016 14:00:00 UTC", &ns->valid_until);
+  } else {
+    parse_rfc1123_time("Wed, 13 Apr 2016 13:00:00 UTC", &ns->valid_after);
+    parse_rfc1123_time("Wed, 13 Apr 2016 14:00:00 UTC", &ns->fresh_until);
+    parse_rfc1123_time("Wed, 13 Apr 2016 16:00:00 UTC", &ns->valid_until);
+  }
+
+  /* Set system time: pretend to be just 2 minutes before consensus expiry */
+  real_time = ns->valid_until - 120;
+  update_approx_time(real_time);
+  return real_time;
+}
+
+/** Helper function that carries out the actual test for
+ *  test_client_service_sync() */
+static void
+helper_test_hsdir_sync(networkstatus_t *ns,
+                       int service_between_srv_and_tp,
+                       int client_between_srv_and_tp,
+                       int client_fetches_next_desc)
+{
+  hs_service_descriptor_t *desc;
+  int retval;
+
+  /** Test logic:
+   *   1) Initialize service time: consensus and system time.
+   *   1.1) Initialize service hash ring
+   *   2) Initialize service and publish descriptors.
+   *   3) Initialize client time: consensus and system time.
+   *   3.1) Initialize client hash ring
+   *   4) Try to fetch descriptor as client, and CHECK that the HSDir picked by
+   *      the client was also picked by service.
+   */
+
+  cleanup_nodelist();
+  smartlist_clear(ns->routerstatus_list);
+
+  /* 1) Initialize service time: consensus and real time */
+  time_t now = helper_set_consensus_and_system_time(ns,
+                                                   service_between_srv_and_tp);
+  helper_initialize_big_hash_ring(ns);
+
+  /* 2) Initialize service */
+  hs_service_t *service = helper_init_service(now);
+  desc = client_fetches_next_desc ? service->desc_next : service->desc_current;
+
+  /* Now let's upload our desc to all hsdirs */
+  upload_descriptor_to_all(service, desc);
+  /* Check that previous hsdirs were populated */
+  tt_int_op(smartlist_len(desc->previous_hsdirs), OP_EQ, 6);
+
+  /* 3) Initialize client time */
+  now = helper_set_consensus_and_system_time(ns, client_between_srv_and_tp);
+
+  cleanup_nodelist();
+  smartlist_clear(ns->routerstatus_list);
+  helper_initialize_big_hash_ring(ns);
+
+  /* 4) Fetch desc as client */
+  char client_hsdir_b64_digest[BASE64_DIGEST_LEN+1] = {0};
+  helper_client_pick_hsdir(&service->keys.identity_pk,
+                          client_hsdir_b64_digest);
+
+  /* CHECK: Go through the hsdirs chosen by the service and make sure that it
+   * contains the one picked by the client! */
+  retval = smartlist_contains_string(desc->previous_hsdirs,
+                                     client_hsdir_b64_digest);
+  tt_int_op(retval, OP_EQ, 1);
+
+ done:
+  /* At the end: free all services and initialize the subsystem again, we will
+   * need it for next scenario. */
+  hs_service_free_all();
+  hs_service_init();
+}
+
+/** This test ensures that client and service will pick the same HSDirs, under
+ *  various timing scenarios:
+ *  a) Scenario where both client and service are in the time segment between
+ *     SRV#N and TP#N:
+ *  b) Scenario where both client and service are in the time segment between
+ *     TP#N and SRV#N+1.
+ *  c) Scenario where service is between SRV#N and TP#N, but client is between
+ *     TP#N and SRV#N+1.
+ *  d) Scenario where service is between TP#N and SRV#N+1, but client is
+ *     between SRV#N and TP#N.
+ *
+ * This test is important because it tests that upload_descriptor_to_all() is
+ * in synch with pick_hsdir_v3(). That's not the case for the
+ * test_reachability() test which only compares the responsible hsdir sets.
+ */
+static void
+test_client_service_hsdir_set_sync(void *arg)
+{
+  networkstatus_t *ns = NULL;
+
+  (void) arg;
+
+  MOCK(networkstatus_get_latest_consensus,
+       mock_networkstatus_get_latest_consensus);
+  MOCK(networkstatus_get_live_consensus,
+       mock_networkstatus_get_live_consensus);
+  MOCK(get_or_state,
+       get_or_state_replacement);
+  MOCK(hs_desc_encode_descriptor,
+       mock_hs_desc_encode_descriptor);
+  MOCK(directory_initiate_request,
+       mock_directory_initiate_request);
+
+  hs_init();
+
+  /* Initialize a big hash ring: we want it to be big so that client and
+   * service cannot accidentally select the same HSDirs */
+  ns = networkstatus_get_latest_consensus();
+  tt_assert(ns);
+
+  /** Now test the various synch scenarios. See the helper function for more
+      details: */
+
+  /*  a) Scenario where both client and service are in the time segment between
+   *     SRV#N and TP#N. At this time the client fetches the first HS desc:
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|----------$===========|     |
+   *  |                                  ^ ^                             |
+   *  |                                  S C                             |
+   *  +------------------------------------------------------------------+
+   */
+  helper_test_hsdir_sync(ns, 1, 1, 0);
+
+  /*  b) Scenario where both client and service are in the time segment between
+   *     TP#N and SRV#N+1. At this time the client fetches the second HS
+   *     desc:
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |                      ^ ^                                         |
+   *  |                      S C                                         |
+   *  +------------------------------------------------------------------+
+   */
+  helper_test_hsdir_sync(ns, 0, 0, 1);
+
+  /*  c) Scenario where service is between SRV#N and TP#N, but client is
+   *     between TP#N and SRV#N+1. Client is forward in time so it fetches the
+   *     second HS desc.
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |                                    ^ ^                           |
+   *  |                                    S C                           |
+   *  +------------------------------------------------------------------+
+   */
+  helper_test_hsdir_sync(ns, 1, 0, 1);
+
+  /*  d) Scenario where service is between TP#N and SRV#N+1, but client is
+   *     between SRV#N and TP#N. Client is backwards in time so it fetches the
+   *     first HS desc.
+   *
+   *  +------------------------------------------------------------------+
+   *  |                                                                  |
+   *  | 00:00      12:00       00:00       12:00       00:00       12:00 |
+   *  | SRV#1      TP#1        SRV#2       TP#2        SRV#3       TP#3  |
+   *  |                                                                  |
+   *  |  $==========|-----------$===========|-----------$===========|    |
+   *  |                                    ^ ^                           |
+   *  |                                    C S                           |
+   *  +------------------------------------------------------------------+
+   */
+  helper_test_hsdir_sync(ns, 0, 1, 0);
+
+ done:
+  SMARTLIST_FOREACH(ns->routerstatus_list,
+                    routerstatus_t *, rs, routerstatus_free(rs));
+  smartlist_clear(ns->routerstatus_list);
+  networkstatus_vote_free(ns);
+  nodelist_free_all();
+  hs_free_all();
+}
+
 struct testcase_t hs_common_tests[] = {
   { "build_address", test_build_address, TT_FORK,
     NULL, NULL },
@@ -860,10 +1660,6 @@ struct testcase_t hs_common_tests[] = {
     NULL, NULL },
   { "start_time_of_next_time_period", test_start_time_of_next_time_period,
     TT_FORK, NULL, NULL },
-  { "desc_overlap_period", test_desc_overlap_period, TT_FORK,
-    NULL, NULL },
-  { "desc_overlap_period_testnet", test_desc_overlap_period_testnet, TT_FORK,
-    NULL, NULL },
   { "responsible_hsdirs", test_responsible_hsdirs, TT_FORK,
     NULL, NULL },
   { "desc_reupload_logic", test_desc_reupload_logic, TT_FORK,
@@ -874,7 +1670,12 @@ struct testcase_t hs_common_tests[] = {
     NULL, NULL },
   { "parse_extended_hostname", test_parse_extended_hostname, TT_FORK,
     NULL, NULL },
-
+  { "time_between_tp_and_srv", test_time_between_tp_and_srv, TT_FORK,
+    NULL, NULL },
+  { "reachability", test_reachability, TT_FORK,
+    NULL, NULL },
+  { "client_service_hsdir_set_sync", test_client_service_hsdir_set_sync,
+    TT_FORK, NULL, NULL },
   END_OF_TESTCASES
 };
 
diff --git a/src/test/test_hs_service.c b/src/test/test_hs_service.c
index 4c7880c0ee..441c73e807 100644
--- a/src/test/test_hs_service.c
+++ b/src/test/test_hs_service.c
@@ -45,6 +45,7 @@
 #include "main.h"
 #include "rendservice.h"
 #include "statefile.h"
+#include "shared_random_state.h"
 
 /* Trunnel */
 #include "hs/cell_establish_intro.h"
@@ -98,17 +99,6 @@ mock_relay_send_command_from_edge(streamid_t stream_id, circuit_t *circ,
   return 0;
 }
 
-/* Mock function that always return true so we can test the descriptor
- * creation of the next time period deterministically. */
-static int
-mock_hs_overlap_mode_is_active_true(const networkstatus_t *consensus,
-                                    time_t now)
-{
-  (void) consensus;
-  (void) now;
-  return 1;
-}
-
 /* Helper: from a set of options in conf, configure a service which will add
  * it to the staging list of the HS subsytem. */
 static int
@@ -942,27 +932,30 @@ test_service_event(void *arg)
   UNMOCK(circuit_mark_for_close_);
 }
 
-/** Test that we rotate descriptors correctly in overlap period */
+/** Test that we rotate descriptors correctly. */
 static void
 test_rotate_descriptors(void *arg)
 {
   int ret;
-  time_t now = time(NULL);
+  time_t next_rotation_time, now = time(NULL);
   hs_service_t *service;
   hs_service_descriptor_t *desc_next;
-  hs_service_intro_point_t *ip;
 
   (void) arg;
 
+  dummy_state = tor_malloc_zero(sizeof(or_state_t));
+
   hs_init();
+  MOCK(get_or_state, get_or_state_replacement);
   MOCK(circuit_mark_for_close_, mock_circuit_mark_for_close);
   MOCK(networkstatus_get_live_consensus,
        mock_networkstatus_get_live_consensus);
 
-  /* Setup the valid_after time to be 13:00 UTC, not in overlap period. The
-   * overlap check doesn't care about the year. */
+  /* Descriptor rotation happens with a consensus with a new SRV. */
+
   ret = parse_rfc1123_time("Sat, 26 Oct 1985 13:00:00 UTC",
                            &mock_ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
   ret = parse_rfc1123_time("Sat, 26 Oct 1985 14:00:00 UTC",
                            &mock_ns.fresh_until);
   tt_int_op(ret, OP_EQ, 0);
@@ -970,68 +963,67 @@ test_rotate_descriptors(void *arg)
   /* Create a service with a default descriptor and state. It's added to the
    * global map. */
   service = helper_create_service();
-  ip = helper_create_service_ip();
-  service_intro_point_add(service->desc_current->intro_points.map, ip);
-
-  /* Nothing should happen because we are not in the overlap period. */
-  rotate_all_descriptors(now);
-  tt_int_op(service->state.in_overlap_period, OP_EQ, 0);
+  service_descriptor_free(service->desc_current);
+  service->desc_current = NULL;
+  /* This triggers a build for both descriptors. The time now is only used in
+   * the descriptor certificate which is important to be now else the decoding
+   * will complain that the cert has expired if we use valid_after. */
+  build_all_descriptors(now);
   tt_assert(service->desc_current);
-  tt_int_op(digest256map_size(service->desc_current->intro_points.map),
-            OP_EQ, 1);
+  tt_assert(service->desc_next);
 
-  /* Entering an overlap period. */
-  ret = parse_rfc1123_time("Sat, 26 Oct 1985 01:00:00 UTC",
+  /* Tweak our service next rotation time so we can use a custom time. */
+  service->state.next_rotation_time = next_rotation_time =
+    mock_ns.valid_after + (11 * 60 * 60);
+
+  /* Nothing should happen, we are not at a new SRV. Our next rotation time
+   * should be untouched. */
+  rotate_all_descriptors(mock_ns.valid_after);
+  tt_u64_op(service->state.next_rotation_time, OP_EQ, next_rotation_time);
+  tt_assert(service->desc_current);
+  tt_assert(service->desc_next);
+  tt_u64_op(service->desc_current->time_period_num, OP_EQ,
+            hs_get_previous_time_period_num(0));
+  tt_u64_op(service->desc_next->time_period_num, OP_EQ,
+            hs_get_time_period_num(0));
+  /* Keep a reference so we can compare it after rotation to the current. */
+  desc_next = service->desc_next;
+
+  /* Going right after a new SRV. */
+  ret = parse_rfc1123_time("Sat, 27 Oct 1985 01:00:00 UTC",
                            &mock_ns.valid_after);
-  ret = parse_rfc1123_time("Sat, 26 Oct 1985 02:00:00 UTC",
+  tt_int_op(ret, OP_EQ, 0);
+  ret = parse_rfc1123_time("Sat, 27 Oct 1985 02:00:00 UTC",
                            &mock_ns.fresh_until);
   tt_int_op(ret, OP_EQ, 0);
-  desc_next = service_descriptor_new();
-  desc_next->next_upload_time = 42; /* Our marker to recognize it. */
-  service->desc_next = desc_next;
-  /* We should have our state flagged to be in the overlap period, our current
-   * descriptor cleaned up and the next descriptor becoming the current. */
-  rotate_all_descriptors(now);
-  tt_int_op(service->state.in_overlap_period, OP_EQ, 1);
-  tt_mem_op(service->desc_current, OP_EQ, desc_next, sizeof(*desc_next));
-  tt_int_op(digest256map_size(service->desc_current->intro_points.map),
-            OP_EQ, 0);
-  tt_assert(service->desc_next == NULL);
-  /* A second time should do nothing. */
-  rotate_all_descriptors(now);
-  tt_int_op(service->state.in_overlap_period, OP_EQ, 1);
+
+  /* Note down what to expect for the next rotation time which is 01:00 + 23h
+   * meaning 00:00:00. */
+  next_rotation_time = mock_ns.valid_after + (23 * 60 * 60);
+  /* We should have our next rotation time modified, our current descriptor
+   * cleaned up and the next descriptor becoming the current. */
+  rotate_all_descriptors(mock_ns.valid_after);
+  tt_u64_op(service->state.next_rotation_time, OP_EQ, next_rotation_time);
   tt_mem_op(service->desc_current, OP_EQ, desc_next, sizeof(*desc_next));
-  tt_int_op(digest256map_size(service->desc_current->intro_points.map),
-            OP_EQ, 0);
   tt_assert(service->desc_next == NULL);
 
-  /* Now let's re-create desc_next and get out of overlap period. We should
-     test that desc_current gets replaced by desc_next, and desc_next becomes
-     NULL. */
-  desc_next = service_descriptor_new();
-  desc_next->next_upload_time = 240; /* Our marker to recognize it. */
-  service->desc_next = desc_next;
-
-  /* Going out of the overlap period. */
-  ret = parse_rfc1123_time("Sat, 26 Oct 1985 12:00:00 UTC",
-                           &mock_ns.valid_after);
-  ret = parse_rfc1123_time("Sat, 26 Oct 1985 13:00:00 UTC",
-                           &mock_ns.fresh_until);
-  /* This should reset the state and not touch the current descriptor. */
-  tt_int_op(ret, OP_EQ, 0);
-  rotate_all_descriptors(now);
-  tt_int_op(service->state.in_overlap_period, OP_EQ, 0);
+  /* A second time should do nothing. */
+  rotate_all_descriptors(mock_ns.valid_after);
+  tt_u64_op(service->state.next_rotation_time, OP_EQ, next_rotation_time);
   tt_mem_op(service->desc_current, OP_EQ, desc_next, sizeof(*desc_next));
   tt_assert(service->desc_next == NULL);
 
-  /* Calling rotate_all_descriptors() another time should do nothing */
-  rotate_all_descriptors(now);
-  tt_int_op(service->state.in_overlap_period, OP_EQ, 0);
+  build_all_descriptors(now);
   tt_mem_op(service->desc_current, OP_EQ, desc_next, sizeof(*desc_next));
-  tt_assert(service->desc_next == NULL);
+  tt_u64_op(service->desc_current->time_period_num, OP_EQ,
+            hs_get_time_period_num(0));
+  tt_u64_op(service->desc_next->time_period_num, OP_EQ,
+            hs_get_next_time_period_num(0));
+  tt_assert(service->desc_next);
 
  done:
   hs_free_all();
+  UNMOCK(get_or_state);
   UNMOCK(circuit_mark_for_close_);
   UNMOCK(networkstatus_get_live_consensus);
 }
@@ -1043,38 +1035,46 @@ test_build_update_descriptors(void *arg)
 {
   int ret;
   time_t now = time(NULL);
-  uint64_t period_num = hs_get_time_period_num(now);
-  uint64_t next_period_num = hs_get_next_time_period_num(now);
   node_t *node;
   hs_service_t *service;
   hs_service_intro_point_t *ip_cur, *ip_next;
+  routerinfo_t ri;
 
   (void) arg;
 
   hs_init();
-  MOCK(hs_overlap_mode_is_active, mock_hs_overlap_mode_is_active_true);
+
   MOCK(get_or_state,
        get_or_state_replacement);
+  MOCK(networkstatus_get_live_consensus,
+       mock_networkstatus_get_live_consensus);
 
   dummy_state = tor_malloc_zero(sizeof(or_state_t));
 
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 03:00:00 UTC",
+                           &mock_ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 04:00:00 UTC",
+                           &mock_ns.fresh_until);
+  tt_int_op(ret, OP_EQ, 0);
+
   /* Create a service without a current descriptor to trigger a build. */
-  service = hs_service_new(get_options());
+  service = helper_create_service();
   tt_assert(service);
-  service->config.version = HS_VERSION_THREE;
-  ed25519_secret_key_generate(&service->keys.identity_sk, 0);
-  ed25519_public_key_generate(&service->keys.identity_pk,
-                              &service->keys.identity_sk);
-  /* Register service to global map. */
-  ret = register_service(get_hs_service_map(), service);
-  tt_int_op(ret, OP_EQ, 0);
+  /* Unfortunately, the helper creates a dummy descriptor so get rid of it. */
+  service_descriptor_free(service->desc_current);
+  service->desc_current = NULL;
 
+  /* We have a fresh service so this should trigger a build for both
+   * descriptors for specific time period that we'll test. */
   build_all_descriptors(now);
   /* Check *current* descriptor. */
   tt_assert(service->desc_current);
   tt_assert(service->desc_current->desc);
   tt_assert(service->desc_current->intro_points.map);
-  tt_u64_op(service->desc_current->time_period_num, OP_EQ, period_num);
+  /* The current time period is the one expected when starting at 03:00. */
+  tt_u64_op(service->desc_current->time_period_num, OP_EQ,
+            hs_get_time_period_num(0));
   /* This should be untouched, the update descriptor process changes it. */
   tt_u64_op(service->desc_current->next_upload_time, OP_EQ, 0);
 
@@ -1083,7 +1083,8 @@ test_build_update_descriptors(void *arg)
   tt_assert(service->desc_next->desc);
   tt_assert(service->desc_next->intro_points.map);
   tt_assert(service->desc_current != service->desc_next);
-  tt_u64_op(service->desc_next->time_period_num, OP_EQ, next_period_num);
+  tt_u64_op(service->desc_next->time_period_num, OP_EQ,
+            hs_get_next_time_period_num(0));
   /* This should be untouched, the update descriptor process changes it. */
   tt_u64_op(service->desc_next->next_upload_time, OP_EQ, 0);
 
@@ -1101,7 +1102,6 @@ test_build_update_descriptors(void *arg)
 
   /* Now, we'll setup a node_t. */
   {
-    routerinfo_t ri;
     tor_addr_t ipv4_addr;
     curve25519_secret_key_t curve25519_secret_key;
 
@@ -1184,10 +1184,64 @@ test_build_update_descriptors(void *arg)
   tt_u64_op(ip_cur->time_to_expire, OP_LE, now +
             INTRO_POINT_LIFETIME_MAX_SECONDS);
 
+  /* Now, we will try to set up a service after a new time period has started
+   * and see if it behaves as expected. */
+
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 13:00:00 UTC",
+                           &mock_ns.valid_after);
+  tt_int_op(ret, OP_EQ, 0);
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 14:00:00 UTC",
+                           &mock_ns.fresh_until);
+  tt_int_op(ret, OP_EQ, 0);
+
+  /* Create a service without a current descriptor to trigger a build. */
+  service = helper_create_service();
+  tt_assert(service);
+  /* Unfortunately, the helper creates a dummy descriptor so get rid of it. */
+  service_descriptor_free(service->desc_current);
+  service->desc_current = NULL;
+
+  /* We have a fresh service so this should trigger a build for both
+   * descriptors for specific time period that we'll test. */
+  build_all_descriptors(now);
+  /* Check *current* descriptor. */
+  tt_assert(service->desc_current);
+  tt_assert(service->desc_current->desc);
+  tt_assert(service->desc_current->intro_points.map);
+  /* This should be for the previous time period. */
+  tt_u64_op(service->desc_current->time_period_num, OP_EQ,
+            hs_get_previous_time_period_num(0));
+  /* This should be untouched, the update descriptor process changes it. */
+  tt_u64_op(service->desc_current->next_upload_time, OP_EQ, 0);
+
+  /* Check *next* descriptor. */
+  tt_assert(service->desc_next);
+  tt_assert(service->desc_next->desc);
+  tt_assert(service->desc_next->intro_points.map);
+  tt_assert(service->desc_current != service->desc_next);
+  tt_u64_op(service->desc_next->time_period_num, OP_EQ,
+            hs_get_time_period_num(0));
+  /* This should be untouched, the update descriptor process changes it. */
+  tt_u64_op(service->desc_next->next_upload_time, OP_EQ, 0);
+
+  /* Let's remove the next descriptor to simulate a rotation. */
+  service_descriptor_free(service->desc_next);
+  service->desc_next = NULL;
+
+  build_all_descriptors(now);
+  /* Check *next* descriptor. */
+  tt_assert(service->desc_next);
+  tt_assert(service->desc_next->desc);
+  tt_assert(service->desc_next->intro_points.map);
+  tt_assert(service->desc_current != service->desc_next);
+  tt_u64_op(service->desc_next->time_period_num, OP_EQ,
+            hs_get_next_time_period_num(0));
+  /* This should be untouched, the update descriptor process changes it. */
+  tt_u64_op(service->desc_next->next_upload_time, OP_EQ, 0);
+
  done:
   hs_free_all();
   nodelist_free_all();
-  UNMOCK(hs_overlap_mode_is_active);
 }
 
 static void
@@ -1200,11 +1254,19 @@ test_upload_descriptors(void *arg)
   (void) arg;
 
   hs_init();
-  MOCK(hs_overlap_mode_is_active, mock_hs_overlap_mode_is_active_true);
   MOCK(get_or_state,
        get_or_state_replacement);
+  MOCK(networkstatus_get_live_consensus,
+       mock_networkstatus_get_live_consensus);
+
   dummy_state = tor_malloc_zero(sizeof(or_state_t));
 
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 13:00:00 UTC",
+                           &mock_ns.valid_after);
+  ret = parse_rfc1123_time("Sat, 26 Oct 1985 14:00:00 UTC",
+                           &mock_ns.fresh_until);
+  tt_int_op(ret, OP_EQ, 0);
+
   /* Create a service with no descriptor. It's added to the global map. */
   service = hs_service_new(get_options());
   tt_assert(service);
@@ -1235,7 +1297,6 @@ test_upload_descriptors(void *arg)
 
  done:
   hs_free_all();
-  UNMOCK(hs_overlap_mode_is_active);
   UNMOCK(get_or_state);
 }