Tor  0.4.7.0-alpha-dev
nodefamily.c
Go to the documentation of this file.
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"
19 #include "feature/relay/router.h"
21 
22 #include "ht.h"
23 #include "siphash.h"
24 
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
52 {
53  return (unsigned) siphash24g(nf->family_members,
55 }
56 
57 /**
58  * Hashtable equality implementation.
59  */
60 static inline unsigned int
62 {
63  return (a->n_members == b->n_members) &&
64  fast_memeq(a->family_members, b->family_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,
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  **/
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 *
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,
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
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
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
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
329  const node_t *node)
330 {
331  return
333  ||
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
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]) {
354  node = node_get_by_nickname((char*)ptr+1, NNF_NO_WARN_UNNAMED);
355  break;
357  node = node_get_by_id((char*)ptr+1);
358  break;
359  default:
360  /* LCOV_EXCL_START */
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 *
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]) {
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 */
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
414 {
415  HT_CLEAR(nodefamily_map, &the_node_families);
416 }
void base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:478
const char * name
Definition: config.c:2434
#define HEX_DIGEST_LEN
Definition: crypto_digest.h:35
Headers for di_ops.c.
#define fast_memeq(a, b, c)
Definition: di_ops.h:35
#define fast_memcmp(a, b, c)
Definition: di_ops.h:28
Definitions for common sizes of cryptographic digests.
#define DIGEST_LEN
Definition: digest_sizes.h:20
const char * escaped(const char *s)
Definition: escape.c:126
HT_PROTOTYPE(hs_circuitmap_ht, circuit_t, hs_circuitmap_node, hs_circuit_hash_token, hs_circuits_have_same_token)
typedef HT_HEAD(hs_service_ht, hs_service_t) hs_service_ht
#define log_fn(severity, domain, args,...)
Definition: log.h:283
#define LD_GENERAL
Definition: log.h:62
#define LOG_WARN
Definition: log.h:53
#define LOG_INFO
Definition: log.h:45
void tor_free_(void *mem)
Definition: malloc.c:227
void * tor_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
#define tor_free(p)
Definition: malloc.h:52
int is_legal_nickname(const char *s)
Definition: nickname.c:19
int is_legal_hexdigest(const char *s)
Definition: nickname.c:45
Header file for nickname.c.
bool nodefamily_contains_node(const nodefamily_t *family, const node_t *node)
Definition: nodefamily.c:328
static int compare_members(const void *a, const void *b)
Definition: nodefamily.c:140
nodefamily_t * nodefamily_from_members(const smartlist_t *members, const uint8_t *rsa_id_self, unsigned flags, smartlist_t *unrecognized_out)
Definition: nodefamily.c:159
void nodefamily_add_nodes_to_smartlist(const nodefamily_t *family, smartlist_t *out)
Definition: nodefamily.c:342
bool nodefamily_contains_nickname(const nodefamily_t *family, const char *name)
Definition: nodefamily.c:304
void nodefamily_free_(nodefamily_t *family)
Definition: nodefamily.c:265
static unsigned int nodefamily_eq(const nodefamily_t *a, const nodefamily_t *b)
Definition: nodefamily.c:61
static unsigned int nodefamily_hash(const nodefamily_t *nf)
Definition: nodefamily.c:51
static nodefamily_t * nodefamily_alloc(int n_members)
Definition: nodefamily.c:38
char * nodefamily_canonicalize(const char *s, const uint8_t *rsa_id_self, unsigned flags)
Definition: nodefamily.c:111
bool nodefamily_contains_rsa_id(const nodefamily_t *family, const uint8_t *rsa_id)
Definition: nodefamily.c:283
void nodefamily_free_all(void)
Definition: nodefamily.c:413
char * nodefamily_format(const nodefamily_t *family)
Definition: nodefamily.c:374
Header file for nodefamily.c.
Compact node-family structure.
#define NODEFAMILY_ARRAY_SIZE(n)
Definition: nodefamily_st.h:44
#define NODEFAMILY_BY_RSA_ID
Definition: nodefamily_st.h:36
#define NODEFAMILY_MEMBER_PTR(nf, i)
Definition: nodefamily_st.h:50
#define NODEFAMILY_BY_NICKNAME
Definition: nodefamily_st.h:39
const char * node_get_nickname(const node_t *node)
Definition: nodelist.c:1450
const node_t * node_get_by_nickname(const char *nickname, unsigned flags)
Definition: nodelist.c:1085
const node_t * node_get_by_id(const char *identity_digest)
Definition: nodelist.c:226
const uint8_t * node_get_rsa_id_digest(const node_t *node)
Definition: nodelist.c:1346
Header file for nodelist.c.
Master header file for Tor-specific functionality.
#define MAX_NICKNAME_LEN
Definition: or.h:112
Header file for router.c.
int hex_digest_nickname_decode(const char *hexdigest, char *digest_out, char *nickname_qualifier_char_out, char *nickname_out)
Definition: routerlist.c:684
Header file for routerlist.c.
void smartlist_sort_strings(smartlist_t *sl)
Definition: smartlist.c:549
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
Definition: smartlist.c:279
Header for smartlist.c.
smartlist_t * smartlist_new(void)
void smartlist_add_strdup(struct smartlist_t *sl, const char *string)
void smartlist_add(smartlist_t *sl, void *element)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, int flags, int max)
Definition: node_st.h:34
uint32_t n_members
Definition: nodefamily_st.h:24
uint32_t refcnt
Definition: nodefamily_st.h:22
Macros to manage assertions, fatal and non-fatal.
#define tor_assert_nonfatal_unreached()
Definition: util_bug.h:176
#define tor_assert(expr)
Definition: util_bug.h:102
void tor_strlower(char *s)
Definition: util_string.c:127
void tor_strupper(char *s)
Definition: util_string.c:138