Line data Source code
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 38 : nodefamily_alloc(int n_members)
39 : {
40 38 : size_t alloc_len = offsetof(nodefamily_t, family_members) +
41 38 : NODEFAMILY_ARRAY_SIZE(n_members);
42 38 : nodefamily_t *nf = tor_malloc_zero(alloc_len);
43 38 : nf->n_members = n_members;
44 38 : return nf;
45 : }
46 :
47 : /**
48 : * Hashtable hash implementation.
49 : */
50 : static inline unsigned int
51 78 : nodefamily_hash(const nodefamily_t *nf)
52 : {
53 156 : return (unsigned) siphash24g(nf->family_members,
54 78 : NODEFAMILY_ARRAY_SIZE(nf->n_members));
55 : }
56 :
57 : /**
58 : * Hashtable equality implementation.
59 : */
60 : static inline unsigned int
61 28 : nodefamily_eq(const nodefamily_t *a, const nodefamily_t *b)
62 : {
63 28 : return (a->n_members == b->n_members) &&
64 28 : 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 132 : HT_PROTOTYPE(nodefamily_map, nodefamily_t, ht_ent, nodefamily_hash,
72 : nodefamily_eq);
73 9 : 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 22 : nodefamily_parse(const char *s, const uint8_t *rsa_id_self,
92 : unsigned flags)
93 : {
94 22 : smartlist_t *sl = smartlist_new();
95 22 : smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
96 22 : nodefamily_t *result = nodefamily_from_members(sl, rsa_id_self, flags, NULL);
97 87 : SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
98 22 : smartlist_free(sl);
99 22 : 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 3 : nodefamily_canonicalize(const char *s, const uint8_t *rsa_id_self,
112 : unsigned flags)
113 : {
114 3 : smartlist_t *sl = smartlist_new();
115 3 : smartlist_t *result_members = smartlist_new();
116 3 : smartlist_split_string(sl, s, NULL, SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
117 3 : nodefamily_t *nf = nodefamily_from_members(sl, rsa_id_self, flags,
118 : result_members);
119 :
120 3 : char *formatted = nodefamily_format(nf);
121 3 : smartlist_split_string(result_members, formatted, NULL,
122 : SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
123 3 : smartlist_sort_strings(result_members);
124 3 : char *combined = smartlist_join_strings(result_members, " ", 0, NULL);
125 :
126 3 : nodefamily_free(nf);
127 13 : SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
128 3 : smartlist_free(sl);
129 15 : SMARTLIST_FOREACH(result_members, char *, cp, tor_free(cp));
130 3 : smartlist_free(result_members);
131 3 : tor_free(formatted);
132 :
133 3 : return combined;
134 : }
135 :
136 : /**
137 : * qsort helper for encoded nodefamily elements.
138 : **/
139 : static int
140 71 : compare_members(const void *a, const void *b)
141 : {
142 71 : 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 31 : nodefamily_from_members(const smartlist_t *members,
160 : const uint8_t *rsa_id_self,
161 : unsigned flags,
162 : smartlist_t *unrecognized_out)
163 : {
164 31 : const int n_self = rsa_id_self ? 1 : 0;
165 31 : int n_bad_elements = 0;
166 31 : int n_members = smartlist_len(members) + n_self;
167 31 : nodefamily_t *tmp = nodefamily_alloc(n_members);
168 31 : uint8_t *ptr = NODEFAMILY_MEMBER_PTR(tmp, 0);
169 :
170 120 : SMARTLIST_FOREACH_BEGIN(members, const char *, cp) {
171 89 : bool bad_element = true;
172 89 : if (is_legal_nickname(cp)) {
173 34 : ptr[0] = NODEFAMILY_BY_NICKNAME;
174 34 : tor_assert(strlen(cp) < DIGEST_LEN); // guaranteed by is_legal_nickname
175 34 : memcpy(ptr+1, cp, strlen(cp));
176 34 : tor_strlower((char*) ptr+1);
177 34 : bad_element = false;
178 55 : } else if (is_legal_hexdigest(cp)) {
179 34 : char digest_buf[DIGEST_LEN];
180 34 : char nn_buf[MAX_NICKNAME_LEN+1];
181 34 : char nn_char=0;
182 34 : if (hex_digest_nickname_decode(cp, digest_buf, &nn_char, nn_buf)==0) {
183 34 : bad_element = false;
184 34 : ptr[0] = NODEFAMILY_BY_RSA_ID;
185 34 : memcpy(ptr+1, digest_buf, DIGEST_LEN);
186 : }
187 : } else {
188 21 : if (unrecognized_out)
189 3 : smartlist_add_strdup(unrecognized_out, cp);
190 : }
191 :
192 71 : if (bad_element) {
193 21 : const int severity = (flags & NF_WARN_MALFORMED) ? LOG_WARN : LOG_INFO;
194 21 : log_fn(severity, LD_GENERAL,
195 : "Bad element %s while parsing a node family.",
196 : escaped(cp));
197 21 : ++n_bad_elements;
198 : } else {
199 68 : ptr += NODEFAMILY_MEMBER_LEN;
200 : }
201 89 : } SMARTLIST_FOREACH_END(cp);
202 :
203 31 : if (n_bad_elements && (flags & NF_REJECT_MALFORMED))
204 2 : goto err;
205 :
206 29 : if (rsa_id_self) {
207 : /* Add self. */
208 11 : ptr[0] = NODEFAMILY_BY_RSA_ID;
209 11 : memcpy(ptr+1, rsa_id_self, DIGEST_LEN);
210 : }
211 :
212 29 : n_members -= n_bad_elements;
213 :
214 : /* Sort tmp into canonical order. */
215 29 : qsort(tmp->family_members, n_members, NODEFAMILY_MEMBER_LEN,
216 : compare_members);
217 :
218 : /* Remove duplicates. */
219 29 : int i;
220 106 : for (i = 0; i < n_members-1; ++i) {
221 48 : uint8_t *thisptr = NODEFAMILY_MEMBER_PTR(tmp, i);
222 48 : uint8_t *nextptr = NODEFAMILY_MEMBER_PTR(tmp, i+1);
223 48 : if (fast_memeq(thisptr, nextptr, NODEFAMILY_MEMBER_LEN)) {
224 5 : memmove(thisptr, nextptr, (n_members-i-1)*NODEFAMILY_MEMBER_LEN);
225 5 : --n_members;
226 5 : --i;
227 : }
228 : }
229 29 : int n_members_alloc = tmp->n_members;
230 29 : tmp->n_members = n_members;
231 :
232 : /* See if we already allocated this family. */
233 29 : nodefamily_t *found = HT_FIND(nodefamily_map, &the_node_families, tmp);
234 29 : if (found) {
235 : /* If we did, great: incref it and return it. */
236 4 : ++found->refcnt;
237 4 : tor_free(tmp);
238 4 : return found;
239 : } else {
240 : /* If not, insert it into the hashtable. */
241 25 : if (n_members_alloc != n_members) {
242 : /* Compact the family if needed */
243 7 : nodefamily_t *tmp2 = nodefamily_alloc(n_members);
244 7 : memcpy(tmp2->family_members, tmp->family_members,
245 7 : n_members * NODEFAMILY_MEMBER_LEN);
246 7 : tor_free(tmp);
247 7 : tmp = tmp2;
248 : }
249 :
250 25 : tmp->refcnt = 1;
251 25 : HT_INSERT(nodefamily_map, &the_node_families, tmp);
252 25 : return tmp;
253 : }
254 :
255 2 : err:
256 2 : tor_free(tmp);
257 2 : 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 81 : nodefamily_free_(nodefamily_t *family)
266 : {
267 81 : if (family == NULL)
268 : return;
269 :
270 27 : --family->refcnt;
271 :
272 27 : if (family->refcnt == 0) {
273 24 : HT_REMOVE(nodefamily_map, &the_node_families, family);
274 24 : 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 44 : nodefamily_contains_rsa_id(const nodefamily_t *family,
284 : const uint8_t *rsa_id)
285 : {
286 44 : if (family == NULL)
287 : return false;
288 :
289 : unsigned i;
290 36 : for (i = 0; i < family->n_members; ++i) {
291 28 : const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
292 28 : if (ptr[0] == NODEFAMILY_BY_RSA_ID &&
293 23 : 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 36 : nodefamily_contains_nickname(const nodefamily_t *family,
305 : const char *name)
306 : {
307 36 : if (family == NULL)
308 : return false;
309 :
310 : unsigned i;
311 22 : for (i = 0; i < family->n_members; ++i) {
312 15 : 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 15 : 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 28 : nodefamily_contains_node(const nodefamily_t *family,
329 : const node_t *node)
330 : {
331 28 : return
332 28 : nodefamily_contains_nickname(family, node_get_nickname(node))
333 56 : ||
334 28 : 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 3 : nodefamily_add_nodes_to_smartlist(const nodefamily_t *family,
343 : smartlist_t *out)
344 : {
345 3 : if (!family)
346 : return;
347 :
348 : unsigned i;
349 9 : for (i = 0; i < family->n_members; ++i) {
350 7 : const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
351 7 : const node_t *node = NULL;
352 7 : switch (ptr[0]) {
353 3 : case NODEFAMILY_BY_NICKNAME:
354 3 : node = node_get_by_nickname((char*)ptr+1, NNF_NO_WARN_UNNAMED);
355 3 : break;
356 4 : case NODEFAMILY_BY_RSA_ID:
357 4 : node = node_get_by_id((char*)ptr+1);
358 4 : break;
359 0 : default:
360 : /* LCOV_EXCL_START */
361 : tor_assert_nonfatal_unreached();
362 : break;
363 : /* LCOV_EXCL_STOP */
364 : }
365 7 : if (node)
366 5 : smartlist_add(out, (void *)node);
367 : }
368 : }
369 :
370 : /**
371 : * Encode <b>family</b> as a space-separated string.
372 : */
373 : char *
374 15 : nodefamily_format(const nodefamily_t *family)
375 : {
376 15 : if (!family)
377 1 : return tor_strdup("");
378 :
379 14 : unsigned i;
380 14 : smartlist_t *sl = smartlist_new();
381 70 : for (i = 0; i < family->n_members; ++i) {
382 42 : const uint8_t *ptr = NODEFAMILY_MEMBER_PTR(family, i);
383 42 : switch (ptr[0]) {
384 13 : case NODEFAMILY_BY_NICKNAME:
385 13 : smartlist_add_strdup(sl, (char*)ptr+1);
386 13 : break;
387 29 : case NODEFAMILY_BY_RSA_ID: {
388 29 : char buf[HEX_DIGEST_LEN+2];
389 29 : buf[0]='$';
390 29 : base16_encode(buf+1, sizeof(buf)-1, (char*)ptr+1, DIGEST_LEN);
391 29 : tor_strupper(buf);
392 29 : smartlist_add_strdup(sl, buf);
393 29 : break;
394 : }
395 0 : default:
396 : /* LCOV_EXCL_START */
397 : tor_assert_nonfatal_unreached();
398 : break;
399 : /* LCOV_EXCL_STOP */
400 : }
401 : }
402 :
403 14 : char *result = smartlist_join_strings(sl, " ", 0, NULL);
404 56 : SMARTLIST_FOREACH(sl, char *, cp, tor_free(cp));
405 14 : smartlist_free(sl);
406 14 : return result;
407 : }
408 :
409 : /**
410 : * Free all storage held in the nodefamily map.
411 : **/
412 : void
413 1 : nodefamily_free_all(void)
414 : {
415 1 : HT_CLEAR(nodefamily_map, &the_node_families);
416 1 : }
|
