src/feature/nodelist/nodefamily.c

   1 /* Copyright (c) 2001 Matej Pfajfar.
   2  * Copyright (c) 2001-2004, Roger Dingledine.
   3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   4  * Copyright (c) 2007-2021, The Tor Project, Inc. */
   5 /* See LICENSE for licensing information */
   6
   7 /**
   8  * \file nodefamily.c
   9  * \brief Code to manipulate encoded, reference-counted node families.  We
  10  *  use these tricks to save space, since these families would otherwise
  11  *  require a large number of tiny allocations.
  12  **/
  13
  14 #include "core/or/or.h"
  15 #include "feature/nodelist/nickname.h"
  16 #include "feature/nodelist/nodefamily.h"
  17 #include "feature/nodelist/nodefamily_st.h"
  18 #include "feature/nodelist/nodelist.h"
  19 #include "feature/relay/router.h"
  20 #include "feature/nodelist/routerlist.h"
  21
  22 #include "ht.h"
  23 #include "siphash.h"
  24
  25 #include "lib/container/smartlist.h"
  26 #include "lib/ctime/di_ops.h"
  27 #include "lib/defs/digest_sizes.h"
  28 #include "lib/log/util_bug.h"
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32
  33 /**
  34  * Allocate and return a blank node family with space to hold <b>n_members</b>
  35  * members.
  36  */
  37 static nodefamily_t *
  38 nodefamily_alloc(int n_members)
  39 {
  40   size_t alloc_len = offsetof(nodefamily_t, family_members) +
  41     NODEFAMILY_ARRAY_SIZE(n_members);
  42   nodefamily_t *nf = tor_malloc_zero(alloc_len);
  43   nf->n_members = n_members;
  44   return nf;
  45 }
  46
  47 /**
  48  * Hashtable hash implementation.
  49  */
  50 static inline unsigned int
  51 nodefamily_hash(const nodefamily_t *nf)
  52 {
  53   return (unsigned) siphash24g(nf->family_members,
  54                                NODEFAMILY_ARRAY_SIZE(nf->n_members));
  55 }
  56
  57 /**
  58  * Hashtable equality implementation.
  59  */
  60 static inline unsigned int
  61 nodefamily_eq(const nodefamily_t *a, const nodefamily_t *b)
  62 {
  63   return (a->n_members == b->n_members) &&
  64     fast_memeq(a->family_members, b->family_members,
  65                NODEFAMILY_ARRAY_SIZE(a->n_members));
  66 }
  67
  68 static HT_HEAD(nodefamily_map, nodefamily_t) the_node_families
  69   = HT_INITIALIZER();
  70
  71 HT_PROTOTYPE(nodefamily_map, nodefamily_t, ht_ent, nodefamily_hash,
  72              nodefamily_eq);
  73 HT_GENERATE2(nodefamily_map, nodefamily_t, ht_ent, nodefamily_hash,
  74              node_family_eq, 0.6, tor_reallocarray_, tor_free_);
  75
  76 /**
  77  * Parse the family declaration in <b>s</b>, returning the canonical
  78  * <b>nodefamily_t</b> for its members.  Return NULL on error.
  79  *
  80  * If <b>rsa_id_self</b> is provided, it is a DIGEST_LEN-byte digest
  81  * for the router that declared this family: insert it into the
  82  * family declaration if it is not there already.
  83  *
  84  * If NF_WARN_MALFORMED is set in <b>flags</b>, warn about any
  85  * elements that we can't parse.  (By default, we log at info.)
  86  *
  87  * If NF_REJECT_MALFORMED is set in <b>flags</b>, treat any unparseable
  88  * elements as an error. (By default, we simply omit them.)
  89  **/
  90 nodefamily_t *
  91 nodefamily_parse(const char *s, const uint8_t *rsa_id_self,
  92                  unsigned flags)
  93 {
  94   smartlist_t *sl = smartlist_new();
  95   smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  96   nodefamily_t *result = nodefamily_from_members(sl, rsa_id_self, flags, NULL);
  97   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
  98   smartlist_free(sl);
  99   return result;
 100 }
 101
 102 /**
 103  * Canonicalize the family list <b>s</b>, returning a newly allocated string.
 104  *
 105  * The canonicalization rules are fully specified in dir-spec.txt, but,
 106  * briefly: $hexid entries are put in caps, $hexid[=~]foo entries are
 107  * truncated, nicknames are put into lowercase, unrecognized entries are left
 108  * alone, and everything is sorted.
 109  **/
 110 char *
 111 nodefamily_canonicalize(const char *s, const uint8_t *rsa_id_self,
 112                         unsigned flags)
 113 {
 114   smartlist_t *sl = smartlist_new();
 115   smartlist_t *result_members = smartlist_new();
 116   smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 117   nodefamily_t *nf = nodefamily_from_members(sl, rsa_id_self, flags,
 118                                              result_members);
 119
 120   char *formatted = nodefamily_format(nf);
 121   smartlist_split_string(result_members, formatted, NULL,
 122                          SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 123   smartlist_sort_strings(result_members);
 124   char *combined = smartlist_join_strings(result_members, " ", 0, NULL);
 125
 126   nodefamily_free(nf);
 127   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 128   smartlist_free(sl);
 129   SMARTLIST_FOREACH(result_members, char *, cp, tor_free(cp));
 130   smartlist_free(result_members);
 131   tor_free(formatted);
 132
 133   return combined;
 134 }
 135
 136 /**
 137  * qsort helper for encoded nodefamily elements.
 138  **/
 139 static int
 140 compare_members(const void *a, const void *b)
 141 {
 142   return fast_memcmp(a, b, NODEFAMILY_MEMBER_LEN);
 143 }
 144
 145 /**
 146  * Parse the member strings in <b>members</b>, returning their canonical
 147  * <b>nodefamily_t</b>.  Return NULL on error.
 148  *
 149  * If <b>rsa_id_self</b> is provided, it is a DIGEST_LEN-byte digest
 150  * for the router that declared this family: insert it into the
 151  * family declaration if it is not there already.
 152  *
 153  * The <b>flags</b> element is interpreted as in nodefamily_parse().
 154  *
 155  * If <b>unrecognized</b> is provided, fill it copies of any unrecognized
 156  * members.  (Note that malformed $hexids are not considered unrecognized.)
 157  **/
 158 nodefamily_t *
 159 nodefamily_from_members(const smartlist_t *members,
 160                         const uint8_t *rsa_id_self,
 161                         unsigned flags,
 162                         smartlist_t *unrecognized_out)
 163 {
 164   const int n_self = rsa_id_self ? 1 : 0;
 165   int n_bad_elements = 0;
 166   int n_members = smartlist_len(members) + n_self;
 167   nodefamily_t *tmp = nodefamily_alloc(n_members);
 168   uint8_t *ptr = NODEFAMILY_MEMBER_PTR(tmp, 0);
 169
 170   SMARTLIST_FOREACH_BEGIN(members, const char *, cp) {
 171     bool bad_element = true;
 172     if (is_legal_nickname(cp)) {
 173       ptr[0] = NODEFAMILY_BY_NICKNAME;
 174       tor_assert(strlen(cp) < DIGEST_LEN); // guaranteed by is_legal_nickname
 175       memcpy(ptr+1, cp, strlen(cp));
 176       tor_strlower((char*) ptr+1);
 177       bad_element = false;
 178     } else if (is_legal_hexdigest(cp)) {
 179       char digest_buf[DIGEST_LEN];
 180       char nn_buf[MAX_NICKNAME_LEN+1];
 181       char nn_char=0;
 182       if (hex_digest_nickname_decode(cp, digest_buf, &nn_char, nn_buf)==0) {
 183         bad_element = false;
 184         ptr[0] = NODEFAMILY_BY_RSA_ID;
 185         memcpy(ptr+1, digest_buf, DIGEST_LEN);
 186       }
 187     } else {
 188       if (unrecognized_out)
 189         smartlist_add_strdup(unrecognized_out, cp);
 190     }
 191
 192     if (bad_element) {
 193       const int severity = (flags & NF_WARN_MALFORMED) ? LOG_WARN : LOG_INFO;
 194       log_fn(severity, LD_GENERAL,
 195              "Bad element %s while parsing a node family.",
 196              escaped(cp));
 197       ++n_bad_elements;
 198     } else {
 199       ptr += NODEFAMILY_MEMBER_LEN;
 200     }
 201   } SMARTLIST_FOREACH_END(cp);
 202
 203   if (n_bad_elements && (flags & NF_REJECT_MALFORMED))
 204     goto err;
 205
 206   if (rsa_id_self) {
 207     /* Add self. */
 208     ptr[0] = NODEFAMILY_BY_RSA_ID;
 209     memcpy(ptr+1, rsa_id_self, DIGEST_LEN);
 210   }
 211
 212   n_members -= n_bad_elements;
 213
 214   /* Sort tmp into canonical order. */
 215   qsort(tmp->family_members, n_members, NODEFAMILY_MEMBER_LEN,
 216         compare_members);
 217
 218   /* Remove duplicates. */
 219   int i;
 220   for (i = 0; i < n_members-1; ++i) {
 221     uint8_t *thisptr = NODEFAMILY_MEMBER_PTR(tmp, i);
 222     uint8_t *nextptr = NODEFAMILY_MEMBER_PTR(tmp, i+1);
 223     if (fast_memeq(thisptr, nextptr, NODEFAMILY_MEMBER_LEN)) {
 224       memmove(thisptr, nextptr, (n_members-i-1)*NODEFAMILY_MEMBER_LEN);
 225       --n_members;
 226       --i;
 227     }
 228   }
 229   int n_members_alloc = tmp->n_members;
 230   tmp->n_members = n_members;
 231
 232   /* See if we already allocated this family. */
 233   nodefamily_t *found = HT_FIND(nodefamily_map, &the_node_families, tmp);
 234   if (found) {
 235     /* If we did, great: incref it and return it. */
 236     ++found->refcnt;
 237     tor_free(tmp);
 238     return found;
 239   } else {
 240     /* If not, insert it into the hashtable. */
 241     if (n_members_alloc != n_members) {
 242       /* Compact the family if needed */
 243       nodefamily_t *tmp2 = nodefamily_alloc(n_members);
 244       memcpy(tmp2->family_members, tmp->family_members,
 245              n_members * NODEFAMILY_MEMBER_LEN);
 246       tor_free(tmp);
 247       tmp = tmp2;
 248     }
 249
 250     tmp->refcnt = 1;
 251     HT_INSERT(nodefamily_map, &the_node_families, tmp);
 252     return tmp;
 253   }
 254
 255  err:
 256   tor_free(tmp);
 257   return NULL;
 258 }
 259
 260 /**
 261  * Drop our reference to <b>family</b>, freeing it if there are no more
 262  * references.
 263  */
 264 void
 265 nodefamily_free_(nodefamily_t *family)
 266 {
 267   if (family == NULL)
 268     return;
 269
 270   --family->refcnt;
 271
 272   if (family->refcnt == 0) {
 273     HT_REMOVE(nodefamily_map, &the_node_families, family);
 274     tor_free(family);
 275   }
 276 }
 277
 278 /**
 279  * Return true iff <b>family</b> contains the SHA1 RSA1024 identity
 280  * <b>rsa_id</b>.
 281  */
 282 bool
 283 nodefamily_contains_rsa_id(const nodefamily_t *family,
 284                            const uint8_t *rsa_id)
 285 {
 286   if (family == NULL)
 287     return false;
 288
 289   unsigned i;
 290   for (i = 0; i < family->n_members; ++i) {
 291     const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
 292     if (ptr[0] == NODEFAMILY_BY_RSA_ID &&
 293         fast_memeq(ptr+1, rsa_id, DIGEST_LEN)) {
 294       return true;
 295     }
 296   }
 297   return false;
 298 }
 299
 300 /**
 301  * Return true iff <b>family</b> contains the nickname <b>name</b>.
 302  */
 303 bool
 304 nodefamily_contains_nickname(const nodefamily_t *family,
 305                              const char *name)
 306 {
 307   if (family == NULL)
 308     return false;
 309
 310   unsigned i;
 311   for (i = 0; i < family->n_members; ++i) {
 312     const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
 313     // note that the strcasecmp() is safe because there is always at least one
 314     // NUL in the encoded nickname, because all legal nicknames are less than
 315     // DIGEST_LEN bytes long.
 316     if (ptr[0] == NODEFAMILY_BY_NICKNAME && !strcasecmp((char*)ptr+1, name)) {
 317       return true;
 318     }
 319   }
 320   return false;
 321 }
 322
 323 /**
 324  * Return true if <b>family</b> contains the nickname or the RSA ID for
 325  * <b>node</b>
 326  **/
 327 bool
 328 nodefamily_contains_node(const nodefamily_t *family,
 329                          const node_t *node)
 330 {
 331   return
 332     nodefamily_contains_nickname(family, node_get_nickname(node))
 333     ||
 334     nodefamily_contains_rsa_id(family, node_get_rsa_id_digest(node));
 335 }
 336
 337 /**
 338  * Look up every entry in <b>family</b>, and add add the corresponding
 339  * node_t to <b>out</b>.
 340  **/
 341 void
 342 nodefamily_add_nodes_to_smartlist(const nodefamily_t *family,
 343                                   smartlist_t *out)
 344 {
 345   if (!family)
 346     return;
 347
 348   unsigned i;
 349   for (i = 0; i < family->n_members; ++i) {
 350     const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
 351     const node_t *node = NULL;
 352     switch (ptr[0]) {
 353       case NODEFAMILY_BY_NICKNAME:
 354         node = node_get_by_nickname((char*)ptr+1, NNF_NO_WARN_UNNAMED);
 355         break;
 356       case NODEFAMILY_BY_RSA_ID:
 357         node = node_get_by_id((char*)ptr+1);
 358         break;
 359       default:
 360         /* LCOV_EXCL_START */
 361         tor_assert_nonfatal_unreached();
 362         break;
 363         /* LCOV_EXCL_STOP */
 364     }
 365     if (node)
 366       smartlist_add(out, (void *)node);
 367   }
 368 }
 369
 370 /**
 371  * Encode <b>family</b> as a space-separated string.
 372  */
 373 char *
 374 nodefamily_format(const nodefamily_t *family)
 375 {
 376   if (!family)
 377     return tor_strdup("");
 378
 379   unsigned i;
 380   smartlist_t *sl = smartlist_new();
 381   for (i = 0; i < family->n_members; ++i) {
 382     const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
 383     switch (ptr[0]) {
 384       case NODEFAMILY_BY_NICKNAME:
 385         smartlist_add_strdup(sl, (char*)ptr+1);
 386         break;
 387       case NODEFAMILY_BY_RSA_ID: {
 388         char buf[HEX_DIGEST_LEN+2];
 389         buf[0]='$';
 390         base16_encode(buf+1, sizeof(buf)-1, (char*)ptr+1, DIGEST_LEN);
 391         tor_strupper(buf);
 392         smartlist_add_strdup(sl, buf);
 393         break;
 394       }
 395       default:
 396         /* LCOV_EXCL_START */
 397         tor_assert_nonfatal_unreached();
 398         break;
 399         /* LCOV_EXCL_STOP */
 400     }
 401   }
 402
 403   char *result = smartlist_join_strings(sl, " ", 0, NULL);
 404   SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 405   smartlist_free(sl);
 406   return result;
 407 }
 408
 409 /**
 410  * Free all storage held in the nodefamily map.
 411  **/
 412 void
 413 nodefamily_free_all(void)
 414 {
 415   HT_CLEAR(nodefamily_map, &the_node_families);
 416 }