Memoize summarize_protover_flags()

Our tests showed that this function is responsible for a huge number
of our malloc/free() calls.  It's a prime candidate for being
memoized.

Closes ticket 27225.

1 files changed, 67 insertions, 15 deletions

diff --git a/src/core/or/versions.c b/src/core/or/versions.c
index 06274996a7..6f8eea7a67 100644
--- a/src/core/or/versions.c
+++ b/src/core/or/versions.c
@@ -377,6 +377,62 @@ sort_version_list(smartlist_t *versions, int remove_duplicates)
     smartlist_uniq(versions, compare_tor_version_str_ptr_, tor_free_);
 }
 
+/** If there are more than this many entries, we're probably under
+ * some kind of weird DoS. */
+static const int MAX_PROTOVER_SUMMARY_MAP_LEN = 1024;
+
+/**
+ * Map from protover string to protover_summary_flags_t.
+ */
+static strmap_t *protover_summary_map = NULL;
+
+/**
+ * Helper.  Given a non-NULL protover string <b>protocols</b>, set <b>out</b>
+ * to its summary, and memoize the result in <b>protover_summary_map</b>.
+ */
+static void
+memoize_protover_summary(protover_summary_flags_t *out,
+                         const char *protocols)
+{
+  if (!protover_summary_map)
+    protover_summary_map = strmap_new();
+
+  if (strmap_size(protover_summary_map) >= MAX_PROTOVER_SUMMARY_MAP_LEN) {
+    protover_summary_cache_free_all();
+  }
+
+  const protover_summary_flags_t *cached =
+    strmap_get(protover_summary_map, protocols);
+
+  if (cached != NULL) {
+    /* We found a cached entry; no need to parse this one. */
+    memcpy(out, cached, sizeof(protover_summary_flags_t));
+    tor_assert(out->protocols_known);
+    return;
+  }
+
+  memset(out, 0, sizeof(*out));
+  out->protocols_known = 1;
+  out->supports_extend2_cells =
+    protocol_list_supports_protocol(protocols, PRT_RELAY, 2);
+  out->supports_ed25519_link_handshake_compat =
+    protocol_list_supports_protocol(protocols, PRT_LINKAUTH, 3);
+  out->supports_ed25519_link_handshake_any =
+    protocol_list_supports_protocol_or_later(protocols, PRT_LINKAUTH, 3);
+  out->supports_ed25519_hs_intro =
+    protocol_list_supports_protocol(protocols, PRT_HSINTRO, 4);
+  out->supports_v3_hsdir =
+    protocol_list_supports_protocol(protocols, PRT_HSDIR,
+                                    PROTOVER_HSDIR_V3);
+  out->supports_v3_rendezvous_point =
+    protocol_list_supports_protocol(protocols, PRT_HSREND,
+                                    PROTOVER_HS_RENDEZVOUS_POINT_V3);
+
+  protover_summary_flags_t *new_cached = tor_memdup(out, sizeof(*out));
+  cached = strmap_set(protover_summary_map, protocols, new_cached);
+  tor_assert(!cached);
+}
+
 /** Summarize the protocols listed in <b>protocols</b> into <b>out</b>,
  * falling back or correcting them based on <b>version</b> as appropriate.
  */
@@ -388,21 +444,7 @@ summarize_protover_flags(protover_summary_flags_t *out,
   tor_assert(out);
   memset(out, 0, sizeof(*out));
   if (protocols) {
-    out->protocols_known = 1;
-    out->supports_extend2_cells =
-      protocol_list_supports_protocol(protocols, PRT_RELAY, 2);
-    out->supports_ed25519_link_handshake_compat =
-      protocol_list_supports_protocol(protocols, PRT_LINKAUTH, 3);
-    out->supports_ed25519_link_handshake_any =
-      protocol_list_supports_protocol_or_later(protocols, PRT_LINKAUTH, 3);
-    out->supports_ed25519_hs_intro =
-      protocol_list_supports_protocol(protocols, PRT_HSINTRO, 4);
-    out->supports_v3_hsdir =
-      protocol_list_supports_protocol(protocols, PRT_HSDIR,
-                                      PROTOVER_HSDIR_V3);
-    out->supports_v3_rendezvous_point =
-      protocol_list_supports_protocol(protocols, PRT_HSREND,
-                                      PROTOVER_HS_RENDEZVOUS_POINT_V3);
+    memoize_protover_summary(out, protocols);
   }
   if (version && !strcmpstart(version, "Tor ")) {
     if (!out->protocols_known) {
@@ -420,3 +462,13 @@ summarize_protover_flags(protover_summary_flags_t *out,
     }
   }
 }
+
+/**
+ * Free all space held in the protover_summary_map.
+ */
+void
+protover_summary_cache_free_all(void)
+{
+  strmap_free(protover_summary_map, tor_free_);
+  protover_summary_map = NULL;
+}