Backend for compact node-family representation.

This representation is meant to save memory in microdescriptors --
we can't use it in routerinfo_t yet, since those families need to be
encoded losslessly for directory voting to work.

This representation saves memory in three ways:
   1. It uses only one allocation per family.  (The old way used a
      smartlist (2 allocs) plus one strdup per entry.)
   2. It stores identity digests in binary, not hex.
   3. It keeps families in a canonical format, memoizes, and
      reference-counts them.

Part of #27359.

1 files changed, 250 insertions, 1 deletions

diff --git a/src/test/test_nodelist.c b/src/test/test_nodelist.c
index 1af6db68ec..2dbd949b7d 100644
--- a/src/test/test_nodelist.c
+++ b/src/test/test_nodelist.c
@@ -9,12 +9,14 @@
 #include "core/or/or.h"
 #include "lib/crypt_ops/crypto_rand.h"
 #include "feature/nodelist/networkstatus.h"
+#include "feature/nodelist/nodefamily.h"
 #include "feature/nodelist/nodelist.h"
 #include "feature/nodelist/torcert.h"
 
 #include "feature/nodelist/microdesc_st.h"
 #include "feature/nodelist/networkstatus_st.h"
 #include "feature/nodelist/node_st.h"
+#include "feature/nodelist/nodefamily_st.h"
 #include "feature/nodelist/routerinfo_st.h"
 #include "feature/nodelist/routerstatus_st.h"
 
@@ -231,6 +233,251 @@ test_nodelist_ed_id(void *arg)
 #undef N_NODES
 }
 
+static void
+test_nodelist_nodefamily(void *arg)
+{
+  (void)arg;
+  /* hex ID digests */
+  const char h1[] = "5B435D6869206861206C65207363617270652070";
+  const char h2[] = "75C3B220616E6461726520696E206769726F2061";
+  const char h3[] = "2074726F766172206461206D616E67696172652C";
+  const char h4[] = "206D656E747265206E6F6E2076616C65206C2769";
+  const char h5[] = "6E766572736F2E202D2D5072696D6F204C657669";
+
+  /* binary ID digests */
+  uint8_t d1[DIGEST_LEN], d2[DIGEST_LEN], d3[DIGEST_LEN], d4[DIGEST_LEN],
+    d5[DIGEST_LEN];
+  base16_decode((char*)d1, sizeof(d1), h1, strlen(h1));
+  base16_decode((char*)d2, sizeof(d2), h2, strlen(h2));
+  base16_decode((char*)d3, sizeof(d3), h3, strlen(h3));
+  base16_decode((char*)d4, sizeof(d4), h4, strlen(h4));
+  base16_decode((char*)d5, sizeof(d5), h5, strlen(h5));
+
+  char *enc=NULL, *enc2=NULL;
+
+  nodefamily_t *nf1 = NULL;
+  nodefamily_t *nf2 = NULL;
+  nodefamily_t *nf3 = NULL;
+
+  /* Make sure that sorting and de-duplication work. */
+  tor_asprintf(&enc, "$%s hello", h1);
+  nf1 = nodefamily_parse(enc, NULL, 0);
+  tt_assert(nf1);
+  tor_free(enc);
+
+  tor_asprintf(&enc, "hello hello $%s hello", h1);
+  nf2 = nodefamily_parse(enc, NULL, 0);
+  tt_assert(nf2);
+  tt_ptr_op(nf1, OP_EQ, nf2);
+  tor_free(enc);
+
+  tor_asprintf(&enc, "%s $%s hello", h1, h1);
+  nf3 = nodefamily_parse(enc, NULL, 0);
+  tt_assert(nf3);
+  tt_ptr_op(nf1, OP_EQ, nf3);
+  tor_free(enc);
+
+  tt_assert(nodefamily_contains_rsa_id(nf1, d1));
+  tt_assert(! nodefamily_contains_rsa_id(nf1, d2));
+  tt_assert(nodefamily_contains_nickname(nf1, "hello"));
+  tt_assert(nodefamily_contains_nickname(nf1, "HELLO"));
+  tt_assert(! nodefamily_contains_nickname(nf1, "goodbye"));
+
+  tt_int_op(nf1->refcnt, OP_EQ, 3);
+  nodefamily_free(nf3);
+  tt_int_op(nf1->refcnt, OP_EQ, 2);
+
+  /* Try parsing with a provided self RSA digest. */
+  nf3 = nodefamily_parse("hello ", d1, 0);
+  tt_assert(nf3);
+  tt_ptr_op(nf1, OP_EQ, nf3);
+
+  /* Do we get the expected result when we re-encode? */
+  tor_asprintf(&enc, "hello $%s", h1);
+  enc2 = nodefamily_format(nf1);
+  tt_str_op(enc2, OP_EQ, enc);
+  tor_free(enc2);
+  tor_free(enc);
+
+  /* Make sure that we get a different result if we give a different digest. */
+  nodefamily_free(nf3);
+  tor_asprintf(&enc, "hello $%s hello", h3);
+  nf3 = nodefamily_parse(enc, NULL, 0);
+  tt_assert(nf3);
+  tt_ptr_op(nf1, OP_NE, nf3);
+  tor_free(enc);
+
+  tt_assert(nodefamily_contains_rsa_id(nf3, d3));
+  tt_assert(! nodefamily_contains_rsa_id(nf3, d2));
+  tt_assert(! nodefamily_contains_rsa_id(nf3, d1));
+  tt_assert(nodefamily_contains_nickname(nf3, "hello"));
+  tt_assert(! nodefamily_contains_nickname(nf3, "goodbye"));
+
+  nodefamily_free(nf1);
+  nodefamily_free(nf2);
+  nodefamily_free(nf3);
+
+  /* Try one with several digests, all with nicknames appended, in different
+     formats. */
+  tor_asprintf(&enc, "%s $%s $%s=res $%s~ist", h1, h2, h3, h4);
+  nf1 = nodefamily_parse(enc, d5, 0);
+  tt_assert(nf1);
+  tt_assert(nodefamily_contains_rsa_id(nf1, d1));
+  tt_assert(nodefamily_contains_rsa_id(nf1, d2));
+  tt_assert(nodefamily_contains_rsa_id(nf1, d3));
+  tt_assert(nodefamily_contains_rsa_id(nf1, d4));
+  tt_assert(nodefamily_contains_rsa_id(nf1, d5));
+  /* Nicknames aren't preserved when ids are present, since node naming is
+   * deprecated */
+  tt_assert(! nodefamily_contains_nickname(nf3, "res"));
+  tor_free(enc);
+  tor_asprintf(&enc, "$%s $%s $%s $%s $%s", h4, h3, h1, h5, h2);
+  enc2 = nodefamily_format(nf1);
+  tt_str_op(enc, OP_EQ, enc2);
+  tor_free(enc);
+  tor_free(enc2);
+
+  /* Try ones where we parse the empty string. */
+  nf2 = nodefamily_parse("", NULL, 0);
+  nf3 = nodefamily_parse("", d4, 0);
+  tt_assert(nf2);
+  tt_assert(nf3);
+  tt_ptr_op(nf2, OP_NE, nf3);
+
+  tt_assert(! nodefamily_contains_rsa_id(nf2, d4));
+  tt_assert(nodefamily_contains_rsa_id(nf3, d4));
+  tt_assert(! nodefamily_contains_rsa_id(nf2, d5));
+  tt_assert(! nodefamily_contains_rsa_id(nf3, d5));
+  tt_assert(! nodefamily_contains_nickname(nf2, "fred"));
+  tt_assert(! nodefamily_contains_nickname(nf3, "bosco"));
+
+  /* The NULL family should contain nothing. */
+  tt_assert(! nodefamily_contains_rsa_id(NULL, d4));
+  tt_assert(! nodefamily_contains_rsa_id(NULL, d5));
+
+ done:
+  tor_free(enc);
+  tor_free(enc2);
+  nodefamily_free(nf1);
+  nodefamily_free(nf2);
+  nodefamily_free(nf3);
+}
+
+static void
+test_nodelist_nodefamily_parse_err(void *arg)
+{
+  (void)arg;
+  nodefamily_t *nf1 = NULL;
+  char *enc = NULL;
+  const char *semibogus =
+    "sdakljfdslkfjdsaklfjdkl9sdf " // too long for nickname
+    "$jkASDFLkjsadfjhkl " // not hex
+    "$7468696e67732d696e2d7468656d73656c766573 " // ok
+    "reticulatogranulate "// ok
+    "$73656d69616e7468726f706f6c6f676963616c6c79 " // too long for hex
+    "$616273656e746d696e6465646e6573736573" // too short for hex
+    ;
+
+  setup_capture_of_logs(LOG_WARN);
+
+  // We only get two items when we parse this.
+  for (int reject = 0; reject <= 1; ++reject) {
+    for (int log_at_warn = 0; log_at_warn <= 1; ++log_at_warn) {
+      unsigned flags = log_at_warn ? NF_WARN_MALFORMED : 0;
+      flags |= reject ? NF_REJECT_MALFORMED : 0;
+      nf1 = nodefamily_parse(semibogus, NULL, flags);
+      if (reject) {
+        tt_assert(nf1 == NULL);
+      } else {
+        tt_assert(nf1);
+        enc = nodefamily_format(nf1);
+        tt_str_op(enc, OP_EQ,
+                  "reticulatogranulate "
+                  "$7468696E67732D696E2D7468656D73656C766573");
+        tor_free(enc);
+      }
+
+      if (log_at_warn) {
+        expect_log_msg_containing("$616273656e746d696e6465646e6573736573");
+        expect_log_msg_containing("sdakljfdslkfjdsaklfjdkl9sdf");
+      } else {
+        tt_int_op(mock_saved_log_n_entries(), OP_EQ, 0);
+      }
+      mock_clean_saved_logs();
+    }
+  }
+
+ done:
+  tor_free(enc);
+  nodefamily_free(nf1);
+  teardown_capture_of_logs();
+}
+
+static const node_t *
+mock_node_get_by_id(const char *id)
+{
+  if (fast_memeq(id, "!!!!!!!!!!!!!!!!!!!!", DIGEST_LEN))
+    return NULL;
+
+  // use tor_free, not node_free.
+  node_t *fake_node = tor_malloc_zero(sizeof(node_t));
+  memcpy(fake_node->identity, id, DIGEST_LEN);
+  return fake_node;
+}
+
+static const node_t *
+mock_node_get_by_nickname(const char *nn, unsigned flags)
+{
+  (void)flags;
+  if (!strcmp(nn, "nonesuch"))
+    return NULL;
+
+  // use tor_free, not node_free.
+  node_t *fake_node = tor_malloc_zero(sizeof(node_t));
+  strlcpy(fake_node->identity, nn, DIGEST_LEN);
+  return fake_node;
+}
+
+static void
+test_nodelist_nodefamily_lookup(void *arg)
+{
+  (void)arg;
+  MOCK(node_get_by_nickname, mock_node_get_by_nickname);
+  MOCK(node_get_by_id, mock_node_get_by_id);
+  smartlist_t *sl = smartlist_new();
+  nodefamily_t *nf1 = NULL;
+  char *mem_op_hex_tmp = NULL;
+
+  // 'null' is allowed.
+  nodefamily_add_nodes_to_smartlist(NULL, sl);
+  tt_int_op(smartlist_len(sl), OP_EQ, 0);
+
+  // Try a real family
+  nf1 = nodefamily_parse("$EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE "
+                         "$2121212121212121212121212121212121212121 "
+                         "$3333333333333333333333333333333333333333 "
+                         "erewhon nonesuch", NULL, 0);
+  tt_assert(nf1);
+  nodefamily_add_nodes_to_smartlist(nf1, sl);
+  // There were 5 elements; 2 were dropped because the mocked lookup failed.
+  tt_int_op(smartlist_len(sl), OP_EQ, 3);
+
+  const node_t *n = smartlist_get(sl, 0);
+  tt_str_op(n->identity, OP_EQ, "erewhon");
+  n = smartlist_get(sl, 1);
+  test_memeq_hex(n->identity, "3333333333333333333333333333333333333333");
+  n = smartlist_get(sl, 2);
+  test_memeq_hex(n->identity, "EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE");
+
+ done:
+  UNMOCK(node_get_by_nickname);
+  UNMOCK(node_get_by_id);
+  SMARTLIST_FOREACH(sl, node_t *, fake_node, tor_free(fake_node));
+  smartlist_free(sl);
+  nodefamily_free(nf1);
+  tor_free(mem_op_hex_tmp);
+}
+
 #define NODE(name, flags) \
   { #name, test_nodelist_##name, (flags), NULL, NULL }
 
@@ -239,6 +486,8 @@ struct testcase_t nodelist_tests[] = {
   NODE(node_get_verbose_nickname_not_named, TT_FORK),
   NODE(node_is_dir, TT_FORK),
   NODE(ed_id, TT_FORK),
+  NODE(nodefamily, TT_FORK),
+  NODE(nodefamily_parse_err, TT_FORK),
+  NODE(nodefamily_lookup, TT_FORK),
   END_OF_TESTCASES
 };
-