tor

nodefamily.c (11962B)

---

/* Copyright (c) 2001 Matej Pfajfar.
* Copyright (c) 2001-2004, Roger Dingledine.
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
* Copyright (c) 2007-2021, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
* \file nodefamily.c
* \brief Code to manipulate encoded, reference-counted node families.  We
*  use these tricks to save space, since these families would otherwise
*  require a large number of tiny allocations.
**/

#include "core/or/or.h"
#include "feature/nodelist/nickname.h"
#include "feature/nodelist/nodefamily.h"
#include "feature/nodelist/nodefamily_st.h"
#include "feature/nodelist/nodelist.h"
#include "feature/relay/router.h"
#include "feature/nodelist/routerlist.h"

#include "ht.h"
#include "siphash.h"

#include "lib/container/smartlist.h"
#include "lib/ctime/di_ops.h"
#include "lib/defs/digest_sizes.h"
#include "lib/log/util_bug.h"

#include <stdlib.h>
#include <string.h>

/**
* Allocate and return a blank node family with space to hold <b>n_members</b>
* members.
*/
static nodefamily_t *
nodefamily_alloc(int n_members)
{
 size_t alloc_len = offsetof(nodefamily_t, family_members) +
   NODEFAMILY_ARRAY_SIZE(n_members);
 nodefamily_t *nf = tor_malloc_zero(alloc_len);
 nf->n_members = n_members;
 return nf;
}

/**
* Hashtable hash implementation.
*/
static inline unsigned int
nodefamily_hash(const nodefamily_t *nf)
{
 return (unsigned) siphash24g(nf->family_members,
                              NODEFAMILY_ARRAY_SIZE(nf->n_members));
}

/**
* Hashtable equality implementation.
*/
static inline unsigned int
nodefamily_eq(const nodefamily_t *a, const nodefamily_t *b)
{
 return (a->n_members == b->n_members) &&
   fast_memeq(a->family_members, b->family_members,
              NODEFAMILY_ARRAY_SIZE(a->n_members));
}

static HT_HEAD(nodefamily_map, nodefamily_t) the_node_families
 = HT_INITIALIZER();

HT_PROTOTYPE(nodefamily_map, nodefamily_t, ht_ent, nodefamily_hash,
            nodefamily_eq);
HT_GENERATE2(nodefamily_map, nodefamily_t, ht_ent, nodefamily_hash,
            node_family_eq, 0.6, tor_reallocarray_, tor_free_);

/**
* Parse the family declaration in <b>s</b>, returning the canonical
* <b>nodefamily_t</b> for its members.  Return NULL on error.
*
* If <b>rsa_id_self</b> is provided, it is a DIGEST_LEN-byte digest
* for the router that declared this family: insert it into the
* family declaration if it is not there already.
*
* If NF_WARN_MALFORMED is set in <b>flags</b>, warn about any
* elements that we can't parse.  (By default, we log at info.)
*
* If NF_REJECT_MALFORMED is set in <b>flags</b>, treat any unparseable
* elements as an error. (By default, we simply omit them.)
**/
nodefamily_t *
nodefamily_parse(const char *s, const uint8_t *rsa_id_self,
                unsigned flags)
{
 smartlist_t *sl = smartlist_new();
 smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 nodefamily_t *result = nodefamily_from_members(sl, rsa_id_self, flags, NULL);
 SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 smartlist_free(sl);
 return result;
}

/**
* Canonicalize the family list <b>s</b>, returning a newly allocated string.
*
* The canonicalization rules are fully specified in dir-spec.txt, but,
* briefly: $hexid entries are put in caps, $hexid[=~]foo entries are
* truncated, nicknames are put into lowercase, unrecognized entries are left
* alone, and everything is sorted.
**/
char *
nodefamily_canonicalize(const char *s, const uint8_t *rsa_id_self,
                       unsigned flags)
{
 smartlist_t *sl = smartlist_new();
 smartlist_t *result_members = smartlist_new();
 smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 nodefamily_t *nf = nodefamily_from_members(sl, rsa_id_self, flags,
                                            result_members);

 char *formatted = nodefamily_format(nf);
 smartlist_split_string(result_members, formatted, NULL,
                        SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
 smartlist_sort_strings(result_members);
 char *combined = smartlist_join_strings(result_members, " ", 0, NULL);

 nodefamily_free(nf);
 SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 smartlist_free(sl);
 SMARTLIST_FOREACH(result_members, char *, cp, tor_free(cp));
 smartlist_free(result_members);
 tor_free(formatted);

 return combined;
}

/**
* qsort helper for encoded nodefamily elements.
**/
static int
compare_members(const void *a, const void *b)
{
 return fast_memcmp(a, b, NODEFAMILY_MEMBER_LEN);
}

/**
* Parse the member strings in <b>members</b>, returning their canonical
* <b>nodefamily_t</b>.  Return NULL on error.
*
* If <b>rsa_id_self</b> is provided, it is a DIGEST_LEN-byte digest
* for the router that declared this family: insert it into the
* family declaration if it is not there already.
*
* The <b>flags</b> element is interpreted as in nodefamily_parse().
*
* If <b>unrecognized</b> is provided, fill it copies of any unrecognized
* members.  (Note that malformed $hexids are not considered unrecognized.)
**/
nodefamily_t *
nodefamily_from_members(const smartlist_t *members,
                       const uint8_t *rsa_id_self,
                       unsigned flags,
                       smartlist_t *unrecognized_out)
{
 const int n_self = rsa_id_self ? 1 : 0;
 int n_bad_elements = 0;
 int n_members = smartlist_len(members) + n_self;
 nodefamily_t *tmp = nodefamily_alloc(n_members);
 uint8_t *ptr = NODEFAMILY_MEMBER_PTR(tmp, 0);

 SMARTLIST_FOREACH_BEGIN(members, const char *, cp) {
   bool bad_element = true;
   if (is_legal_nickname(cp)) {
     ptr[0] = NODEFAMILY_BY_NICKNAME;
     tor_assert(strlen(cp) < DIGEST_LEN); // guaranteed by is_legal_nickname
     memcpy(ptr+1, cp, strlen(cp));
     tor_strlower((char*) ptr+1);
     bad_element = false;
   } else if (is_legal_hexdigest(cp)) {
     char digest_buf[DIGEST_LEN];
     char nn_buf[MAX_NICKNAME_LEN+1];
     char nn_char=0;
     if (hex_digest_nickname_decode(cp, digest_buf, &nn_char, nn_buf)==0) {
       bad_element = false;
       ptr[0] = NODEFAMILY_BY_RSA_ID;
       memcpy(ptr+1, digest_buf, DIGEST_LEN);
     }
   } else {
     if (unrecognized_out)
       smartlist_add_strdup(unrecognized_out, cp);
   }

   if (bad_element) {
     const int severity = (flags & NF_WARN_MALFORMED) ? LOG_WARN : LOG_INFO;
     log_fn(severity, LD_GENERAL,
            "Bad element %s while parsing a node family.",
            escaped(cp));
     ++n_bad_elements;
   } else {
     ptr += NODEFAMILY_MEMBER_LEN;
   }
 } SMARTLIST_FOREACH_END(cp);

 if (n_bad_elements && (flags & NF_REJECT_MALFORMED))
   goto err;

 if (rsa_id_self) {
   /* Add self. */
   ptr[0] = NODEFAMILY_BY_RSA_ID;
   memcpy(ptr+1, rsa_id_self, DIGEST_LEN);
 }

 n_members -= n_bad_elements;

 /* Sort tmp into canonical order. */
 qsort(tmp->family_members, n_members, NODEFAMILY_MEMBER_LEN,
       compare_members);

 /* Remove duplicates. */
 int i;
 for (i = 0; i < n_members-1; ++i) {
   uint8_t *thisptr = NODEFAMILY_MEMBER_PTR(tmp, i);
   uint8_t *nextptr = NODEFAMILY_MEMBER_PTR(tmp, i+1);
   if (fast_memeq(thisptr, nextptr, NODEFAMILY_MEMBER_LEN)) {
     memmove(thisptr, nextptr, (n_members-i-1)*NODEFAMILY_MEMBER_LEN);
     --n_members;
     --i;
   }
 }
 int n_members_alloc = tmp->n_members;
 tmp->n_members = n_members;

 /* See if we already allocated this family. */
 nodefamily_t *found = HT_FIND(nodefamily_map, &the_node_families, tmp);
 if (found) {
   /* If we did, great: incref it and return it. */
   ++found->refcnt;
   tor_free(tmp);
   return found;
 } else {
   /* If not, insert it into the hashtable. */
   if (n_members_alloc != n_members) {
     /* Compact the family if needed */
     nodefamily_t *tmp2 = nodefamily_alloc(n_members);
     memcpy(tmp2->family_members, tmp->family_members,
            n_members * NODEFAMILY_MEMBER_LEN);
     tor_free(tmp);
     tmp = tmp2;
   }

   tmp->refcnt = 1;
   HT_INSERT(nodefamily_map, &the_node_families, tmp);
   return tmp;
 }

err:
 tor_free(tmp);
 return NULL;
}

/**
* Drop our reference to <b>family</b>, freeing it if there are no more
* references.
*/
void
nodefamily_free_(nodefamily_t *family)
{
 if (family == NULL)
   return;

 --family->refcnt;

 if (family->refcnt == 0) {
   HT_REMOVE(nodefamily_map, &the_node_families, family);
   tor_free(family);
 }
}

/**
* Return true iff <b>family</b> contains the SHA1 RSA1024 identity
* <b>rsa_id</b>.
*/
bool
nodefamily_contains_rsa_id(const nodefamily_t *family,
                          const uint8_t *rsa_id)
{
 if (family == NULL)
   return false;

 unsigned i;
 for (i = 0; i < family->n_members; ++i) {
   const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
   if (ptr[0] == NODEFAMILY_BY_RSA_ID &&
       fast_memeq(ptr+1, rsa_id, DIGEST_LEN)) {
     return true;
   }
 }
 return false;
}

/**
* Return true iff <b>family</b> contains the nickname <b>name</b>.
*/
bool
nodefamily_contains_nickname(const nodefamily_t *family,
                            const char *name)
{
 if (family == NULL)
   return false;

 unsigned i;
 for (i = 0; i < family->n_members; ++i) {
   const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
   // note that the strcasecmp() is safe because there is always at least one
   // NUL in the encoded nickname, because all legal nicknames are less than
   // DIGEST_LEN bytes long.
   if (ptr[0] == NODEFAMILY_BY_NICKNAME && !strcasecmp((char*)ptr+1, name)) {
     return true;
   }
 }
 return false;
}

/**
* Return true if <b>family</b> contains the nickname or the RSA ID for
* <b>node</b>
**/
bool
nodefamily_contains_node(const nodefamily_t *family,
                        const node_t *node)
{
 return
   nodefamily_contains_nickname(family, node_get_nickname(node))
   ||
   nodefamily_contains_rsa_id(family, node_get_rsa_id_digest(node));
}

/**
* Look up every entry in <b>family</b>, and add add the corresponding
* node_t to <b>out</b>.
**/
void
nodefamily_add_nodes_to_smartlist(const nodefamily_t *family,
                                 smartlist_t *out)
{
 if (!family)
   return;

 unsigned i;
 for (i = 0; i < family->n_members; ++i) {
   const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
   const node_t *node = NULL;
   switch (ptr[0]) {
     case NODEFAMILY_BY_NICKNAME:
       node = node_get_by_nickname((char*)ptr+1, NNF_NO_WARN_UNNAMED);
       break;
     case NODEFAMILY_BY_RSA_ID:
       node = node_get_by_id((char*)ptr+1);
       break;
     default:
       /* LCOV_EXCL_START */
       tor_assert_nonfatal_unreached();
       break;
       /* LCOV_EXCL_STOP */
   }
   if (node)
     smartlist_add(out, (void *)node);
 }
}

/**
* Encode <b>family</b> as a space-separated string.
*/
char *
nodefamily_format(const nodefamily_t *family)
{
 if (!family)
   return tor_strdup("");

 unsigned i;
 smartlist_t *sl = smartlist_new();
 for (i = 0; i < family->n_members; ++i) {
   const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
   switch (ptr[0]) {
     case NODEFAMILY_BY_NICKNAME:
       smartlist_add_strdup(sl, (char*)ptr+1);
       break;
     case NODEFAMILY_BY_RSA_ID: {
       char buf[HEX_DIGEST_LEN+2];
       buf[0]='$';
       base16_encode(buf+1, sizeof(buf)-1, (char*)ptr+1, DIGEST_LEN);
       tor_strupper(buf);
       smartlist_add_strdup(sl, buf);
       break;
     }
     default:
       /* LCOV_EXCL_START */
       tor_assert_nonfatal_unreached();
       break;
       /* LCOV_EXCL_STOP */
   }
 }

 char *result = smartlist_join_strings(sl, " ", 0, NULL);
 SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
 smartlist_free(sl);
 return result;
}

/**
* Free all storage held in the nodefamily map.
**/
void
nodefamily_free_all(void)
{
 HT_CLEAR(nodefamily_map, &the_node_families);
}