tor  0.4.0.1-alpha
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-2019, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
14 #include "core/or/or.h"
17 #include "feature/nodelist/nodefamily_st.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 
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 
50 static inline unsigned int
52 {
53  return (unsigned) siphash24g(nf->family_members,
54  NODEFAMILY_ARRAY_SIZE(nf->n_members));
55 }
56 
60 static inline unsigned int
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,
73 HT_GENERATE2(nodefamily_map, nodefamily_t, ht_ent, nodefamily_hash,
74  node_family_eq, 0.6, tor_reallocarray_, tor_free_)
75 
76 
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 
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 
139 static int
140 compare_members(const void *a, const void *b)
141 {
142  return fast_memcmp(a, b, NODEFAMILY_MEMBER_LEN);
143 }
144 
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 
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 
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 
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 
327 bool
329  const node_t *node)
330 {
331  return
333  ||
335 }
336 
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]) {
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 
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]) {
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 
412 void
414 {
415  HT_CLEAR(nodefamily_map, &the_node_families);
416 }
void nodefamily_free_all(void)
Definition: nodefamily.c:413
void nodefamily_free_(nodefamily_t *family)
Definition: nodefamily.c:265
Definition: node_st.h:28
Header for smartlist.c.
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
Headers for di_ops.c.
Header file for nodefamily.c.
static nodefamily_t * nodefamily_alloc(int n_members)
Definition: nodefamily.c:38
void smartlist_add_strdup(struct smartlist_t *sl, const char *string)
#define LD_GENERAL
Definition: log.h:58
#define LOG_INFO
Definition: log.h:41
Header file for nodelist.c.
HT_PROTOTYPE(HT_GENERATE2(strmap_impl, HT_GENERATE2(strmap_entry_t, HT_GENERATE2(node, HT_GENERATE2(strmap_entry_hash, HT_GENERATE2(strmap_entries_eq)
Definition: map.c:87
bool nodefamily_contains_nickname(const nodefamily_t *family, const char *name)
Definition: nodefamily.c:304
void smartlist_add(smartlist_t *sl, void *element)
#define MAX_NICKNAME_LEN
Definition: or.h:113
void tor_strupper(char *s)
Definition: util_string.c:141
Header file for nickname.c.
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
#define tor_free(p)
Definition: malloc.h:52
void smartlist_sort_strings(smartlist_t *sl)
Definition: smartlist.c:549
static int compare_members(const void *a, const void *b)
Definition: nodefamily.c:140
void * tor_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
uint32_t n_members
Definition: nodefamily_st.h:19
static unsigned int nodefamily_hash(const nodefamily_t *nf)
Definition: nodefamily.c:51
bool nodefamily_contains_rsa_id(const nodefamily_t *family, const uint8_t *rsa_id)
Definition: nodefamily.c:283
int is_legal_hexdigest(const char *s)
Definition: nickname.c:45
tor_assert(buffer)
const char * node_get_nickname(const node_t *node)
Definition: nodelist.c:1194
#define DIGEST_LEN
Definition: digest_sizes.h:20
void nodefamily_add_nodes_to_smartlist(const nodefamily_t *family, smartlist_t *out)
Definition: nodefamily.c:342
Master header file for Tor-specific functionality.
#define LOG_WARN
Definition: log.h:49
void base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:476
char * nodefamily_canonicalize(const char *s, const uint8_t *rsa_id_self, unsigned flags)
Definition: nodefamily.c:111
void tor_free_(void *mem)
Definition: malloc.c:227
void tor_strlower(char *s)
Definition: util_string.c:130
static unsigned int nodefamily_eq(const nodefamily_t *a, const nodefamily_t *b)
Definition: nodefamily.c:61
int is_legal_nickname(const char *s)
Definition: nickname.c:19
#define HEX_DIGEST_LEN
Definition: crypto_digest.h:35
char * nodefamily_format(const nodefamily_t *family)
Definition: nodefamily.c:374
int hex_digest_nickname_decode(const char *hexdigest, char *digest_out, char *nickname_qualifier_char_out, char *nickname_out)
Definition: routerlist.c:598
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
Definition: smartlist.c:279
#define SMARTLIST_FOREACH(sl, type, var, cmd)
Header file for router.c.
const char * escaped(const char *s)
Definition: escape.c:126
uint32_t refcnt
Definition: nodefamily_st.h:17
#define log_fn(severity, domain, args,...)
Definition: log.h:255
#define fast_memcmp(a, b, c)
Definition: di_ops.h:26
Definitions for common sizes of cryptographic digests.
bool nodefamily_contains_node(const nodefamily_t *family, const node_t *node)
Definition: nodefamily.c:328
const uint8_t * node_get_rsa_id_digest(const node_t *node)
Definition: nodelist.c:1186
Macros to manage assertions, fatal and non-fatal.
Header file for routerlist.c.
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, int flags, int max)