Tor  0.4.7.0-alpha-dev
hs_circuitmap.c
Go to the documentation of this file.
1 /* Copyright (c) 2016-2021, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
4 /**
5  * \file hs_circuitmap.c
6  *
7  * \brief Hidden service circuitmap: A hash table that maps binary tokens to
8  * introduction and rendezvous circuits; it's used:
9  * (a) by relays acting as intro points and rendezvous points
10  * (b) by hidden services to find intro and rend circuits and
11  * (c) by HS clients to find rendezvous circuits.
12  **/
13 
14 #define HS_CIRCUITMAP_PRIVATE
15 
16 #include "core/or/or.h"
17 #include "app/config/config.h"
18 #include "core/or/circuitlist.h"
20 
21 #include "core/or/or_circuit_st.h"
23 
24 /************************** HS circuitmap code *******************************/
25 
26 /** This is the hidden service circuitmap. It's a hash table that maps
27  introduction and rendezvous tokens to specific circuits such that given a
28  token it's easy to find the corresponding circuit. */
29 static struct hs_circuitmap_ht *the_hs_circuitmap = NULL;
30 
31 /** This is a helper function used by the hash table code (HT_). It returns 1
32  * if two circuits have the same HS token. */
33 static int
35  const circuit_t *second_circuit)
36 {
37  const hs_token_t *first_token;
38  const hs_token_t *second_token;
39 
40  tor_assert(first_circuit);
41  tor_assert(second_circuit);
42 
43  first_token = first_circuit->hs_token;
44  second_token = second_circuit->hs_token;
45 
46  /* Both circs must have a token */
47  if (BUG(!first_token) || BUG(!second_token)) {
48  return 0;
49  }
50 
51  if (first_token->type != second_token->type) {
52  return 0;
53  }
54 
55  if (first_token->token_len != second_token->token_len)
56  return 0;
57 
58  return tor_memeq(first_token->token,
59  second_token->token,
60  first_token->token_len);
61 }
62 
63 /** This is a helper function for the hash table code (HT_). It hashes a
64  * circuit HS token into an unsigned int for use as a key by the hash table
65  * routines.*/
66 static inline unsigned int
68 {
69  tor_assert(circuit->hs_token);
70 
71  return (unsigned) siphash24g(circuit->hs_token->token,
72  circuit->hs_token->token_len);
73 }
74 
75 /** Register the circuitmap hash table */
76 HT_PROTOTYPE(hs_circuitmap_ht, // The name of the hashtable struct
77  circuit_t, // The name of the element struct,
78  hs_circuitmap_node, // The name of HT_ENTRY member
80 
81 HT_GENERATE2(hs_circuitmap_ht, circuit_t, hs_circuitmap_node,
83  0.6, tor_reallocarray, tor_free_);
84 
85 #ifdef TOR_UNIT_TESTS
86 
87 /** Return the global HS circuitmap. Used by unittests. */
88 hs_circuitmap_ht *
89 get_hs_circuitmap(void)
90 {
91  return the_hs_circuitmap;
92 }
93 
94 #endif /* defined(TOR_UNIT_TESTS) */
95 
96 /****************** HS circuitmap utility functions **************************/
97 
98 /** Return a new HS token of type <b>type</b> containing <b>token</b>. */
99 static hs_token_t *
100 hs_token_new(hs_token_type_t type, size_t token_len,
101  const uint8_t *token)
102 {
103  tor_assert(token);
104 
105  hs_token_t *hs_token = tor_malloc_zero(sizeof(hs_token_t));
106  hs_token->type = type;
107  hs_token->token_len = token_len;
108  hs_token->token = tor_memdup(token, token_len);
109 
110  return hs_token;
111 }
112 
113 #define hs_token_free(val) \
114  FREE_AND_NULL(hs_token_t, hs_token_free_, (val))
115 
116 /** Free memory allocated by this <b>hs_token</b>. */
117 static void
118 hs_token_free_(hs_token_t *hs_token)
119 {
120  if (!hs_token) {
121  return;
122  }
123 
124  tor_free(hs_token->token);
125  tor_free(hs_token);
126 }
127 
128 /** Return the circuit from the circuitmap with token <b>search_token</b>. */
129 static circuit_t *
130 get_circuit_with_token(hs_token_t *search_token)
131 {
133 
134  /* We use a dummy circuit object for the hash table search routine. */
135  circuit_t search_circ;
136  search_circ.hs_token = search_token;
137  return HT_FIND(hs_circuitmap_ht, the_hs_circuitmap, &search_circ);
138 }
139 
140 /** Helper function that registers <b>circ</b> with <b>token</b> on the HS
141  circuitmap. This function steals reference of <b>token</b>. */
142 static void
143 hs_circuitmap_register_impl(circuit_t *circ, hs_token_t *token)
144 {
145  tor_assert(circ);
146  tor_assert(token);
148 
149  /* If this circuit already has a token, clear it. */
150  if (circ->hs_token) {
152  }
153 
154  /* Kill old circuits with the same token. We want new intro/rend circuits to
155  take precedence over old ones, so that HSes and clients and reestablish
156  killed circuits without changing the HS token. */
157  {
158  circuit_t *found_circ;
159  found_circ = get_circuit_with_token(token);
160  if (found_circ) {
161  hs_circuitmap_remove_circuit(found_circ);
162  if (!found_circ->marked_for_close) {
163  circuit_mark_for_close(found_circ, END_CIRC_REASON_FINISHED);
164  }
165  }
166  }
167 
168  /* Register circuit and token to circuitmap. */
169  circ->hs_token = token;
170  HT_INSERT(hs_circuitmap_ht, the_hs_circuitmap, circ);
171 }
172 
173 /** Helper function: Register <b>circ</b> of <b>type</b> on the HS
174  * circuitmap. Use the HS <b>token</b> as the key to the hash table. If
175  * <b>token</b> is not set, clear the circuit of any HS tokens. */
176 static void
178  hs_token_type_t type, size_t token_len,
179  const uint8_t *token)
180 {
181  hs_token_t *hs_token = NULL;
182 
183  /* Create a new token and register it to the circuitmap */
184  tor_assert(token);
185  hs_token = hs_token_new(type, token_len, token);
186  tor_assert(hs_token);
187  hs_circuitmap_register_impl(circ, hs_token);
188 }
189 
190 /** Helper function for hs_circuitmap_get_origin_circuit() and
191  * hs_circuitmap_get_or_circuit(). Because only circuit_t are indexed in the
192  * circuitmap, this function returns object type so the specialized functions
193  * using this helper can upcast it to the right type.
194  *
195  * Return NULL if not such circuit is found. */
196 static circuit_t *
197 hs_circuitmap_get_circuit_impl(hs_token_type_t type,
198  size_t token_len,
199  const uint8_t *token,
200  uint8_t wanted_circ_purpose)
201 {
202  circuit_t *found_circ = NULL;
203 
205 
206  /* Check the circuitmap if we have a circuit with this token */
207  {
208  hs_token_t *search_hs_token = hs_token_new(type, token_len, token);
209  tor_assert(search_hs_token);
210  found_circ = get_circuit_with_token(search_hs_token);
211  hs_token_free(search_hs_token);
212  }
213 
214  /* Check that the circuit is useful to us */
215  if (!found_circ ||
216  found_circ->purpose != wanted_circ_purpose ||
217  found_circ->marked_for_close) {
218  return NULL;
219  }
220 
221  return found_circ;
222 }
223 
224 /** Helper function: Query circuitmap for origin circuit with <b>token</b> of
225  * size <b>token_len</b> and <b>type</b>. Only returns a circuit with purpose
226  * equal to the <b>wanted_circ_purpose</b> parameter and if it is NOT marked
227  * for close. Return NULL if no such circuit is found. */
228 static origin_circuit_t *
229 hs_circuitmap_get_origin_circuit(hs_token_type_t type,
230  size_t token_len,
231  const uint8_t *token,
232  uint8_t wanted_circ_purpose)
233 {
234  circuit_t *circ;
235  tor_assert(token);
236  tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose));
237 
238  circ = hs_circuitmap_get_circuit_impl(type, token_len, token,
239  wanted_circ_purpose);
240  if (!circ) {
241  return NULL;
242  }
243 
245  return TO_ORIGIN_CIRCUIT(circ);
246 }
247 
248 /** Helper function: Query circuitmap for OR circuit with <b>token</b> of size
249  * <b>token_len</b> and <b>type</b>. Only returns a circuit with purpose equal
250  * to the <b>wanted_circ_purpose</b> parameter and if it is NOT marked for
251  * close. Return NULL if no such circuit is found. */
252 static or_circuit_t *
253 hs_circuitmap_get_or_circuit(hs_token_type_t type,
254  size_t token_len,
255  const uint8_t *token,
256  uint8_t wanted_circ_purpose)
257 {
258  circuit_t *circ;
259  tor_assert(token);
260  tor_assert(!CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose));
261 
262  circ = hs_circuitmap_get_circuit_impl(type, token_len, token,
263  wanted_circ_purpose);
264  if (!circ) {
265  return NULL;
266  }
267 
269  return TO_OR_CIRCUIT(circ);
270 }
271 
272 /************** Public circuitmap API ****************************************/
273 
274 /**** Public relay-side getters: */
275 
276 /** Public function: Return v3 introduction circuit to this relay.
277  * Always return a newly allocated list for which it is the caller's
278  * responsibility to free it. */
279 smartlist_t *
281 {
282  circuit_t **iter;
283  smartlist_t *circuit_list = smartlist_new();
284 
285  HT_FOREACH(iter, hs_circuitmap_ht, the_hs_circuitmap) {
286  circuit_t *circ = *iter;
287 
288  /* An origin circuit or purpose is wrong or the hs token is not set to be
289  * a v3 intro relay side type, we ignore the circuit. Else, we have
290  * a match so add it to our list. */
291  if (CIRCUIT_IS_ORIGIN(circ) ||
293  circ->hs_token->type != HS_TOKEN_INTRO_V3_RELAY_SIDE) {
294  continue;
295  }
296  smartlist_add(circuit_list, circ);
297  }
298 
299  return circuit_list;
300 }
301 
302 /** Public function: Return a v3 introduction circuit to this relay with
303  * <b>auth_key</b>. Return NULL if no such circuit is found in the
304  * circuitmap. */
305 or_circuit_t *
307  const ed25519_public_key_t *auth_key)
308 {
309  return hs_circuitmap_get_or_circuit(HS_TOKEN_INTRO_V3_RELAY_SIDE,
310  ED25519_PUBKEY_LEN, auth_key->pubkey,
312 }
313 
314 /** Public function: Return rendezvous circuit to this relay with rendezvous
315  * <b>cookie</b>. Return NULL if no such circuit is found in the circuitmap. */
316 or_circuit_t *
318 {
319  return hs_circuitmap_get_or_circuit(HS_TOKEN_REND_RELAY_SIDE,
320  REND_TOKEN_LEN, cookie,
322 }
323 
324 /** Public relay-side setters: */
325 
326 /** Public function: Register rendezvous circuit with key <b>cookie</b> to the
327  * circuitmap. */
328 void
330  const uint8_t *cookie)
331 {
333  HS_TOKEN_REND_RELAY_SIDE,
334  REND_TOKEN_LEN, cookie);
335 }
336 
337 /** Public function: Register v3 intro circuit with key <b>auth_key</b> to the
338  * circuitmap. */
339 void
341  const ed25519_public_key_t *auth_key)
342 {
344  HS_TOKEN_INTRO_V3_RELAY_SIDE,
345  ED25519_PUBKEY_LEN, auth_key->pubkey);
346 }
347 
348 /**** Public servide-side getters: */
349 
350 /** Public function: Return v3 introduction circuit with <b>auth_key</b>
351  * originating from this hidden service. Return NULL if no such circuit is
352  * found in the circuitmap. */
355  ed25519_public_key_t *auth_key)
356 {
357  origin_circuit_t *circ = NULL;
358 
359  /* Check first for established intro circuits */
360  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE,
361  ED25519_PUBKEY_LEN, auth_key->pubkey,
363  if (circ) {
364  return circ;
365  }
366 
367  /* ...if nothing found, check for pending intro circs */
368  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE,
369  ED25519_PUBKEY_LEN, auth_key->pubkey,
371 
372  return circ;
373 }
374 
375 /** Public function: Return rendezvous circuit originating from this hidden
376  * service with rendezvous <b>cookie</b>. Return NULL if no such circuit is
377  * found in the circuitmap. */
380 {
381  origin_circuit_t *circ = NULL;
382 
383  /* Try to check if we have a connecting circuit. */
384  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE,
385  REND_TOKEN_LEN, cookie,
387  if (circ) {
388  return circ;
389  }
390 
391  /* Then try for connected circuit. */
392  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE,
393  REND_TOKEN_LEN, cookie,
395  return circ;
396 }
397 
398 /** Public function: Return client-side rendezvous circuit with rendezvous
399  * <b>cookie</b>. It will look for circuits with the following purposes:
400 
401  * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received
402  * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for
403  * INTRODUCE_ACK from intro point.
404  *
405  * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and
406  * introduce circuit acked. Waiting for RENDEZVOUS2 from service.
407  *
408  * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received
409  * RENDEZVOUS2 from service.
410  *
411  * d) CIRCUIT_PURPOSE_C_ESTABLISH_REND: Rend circuit open but not yet
412  * established.
413  *
414  * Return NULL if no such circuit is found in the circuitmap. */
417 {
418  origin_circuit_t *circ = NULL;
419 
421  if (circ) {
422  return circ;
423  }
424 
425  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
426  REND_TOKEN_LEN, cookie,
428  return circ;
429 }
430 
431 /** Public function: Return client-side established rendezvous circuit with
432  * rendezvous <b>cookie</b>. It will look for circuits with the following
433  * purposes:
434  *
435  * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received
436  * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for
437  * INTRODUCE_ACK from intro point.
438  *
439  * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and
440  * introduce circuit acked. Waiting for RENDEZVOUS2 from service.
441  *
442  * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received
443  * RENDEZVOUS2 from service.
444  *
445  * Return NULL if no such circuit is found in the circuitmap. */
448 {
449  origin_circuit_t *circ = NULL;
450 
451  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
452  REND_TOKEN_LEN, cookie,
454  if (circ) {
455  return circ;
456  }
457 
458  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
459  REND_TOKEN_LEN, cookie,
461  if (circ) {
462  return circ;
463  }
464 
465  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
466  REND_TOKEN_LEN, cookie,
468  return circ;
469 }
470 
471 /**** Public servide-side setters: */
472 
473 /** Public function: Register v3 intro circuit with key <b>auth_key</b> to the
474  * circuitmap. */
475 void
477  const ed25519_public_key_t *auth_key)
478 {
480  HS_TOKEN_INTRO_V3_SERVICE_SIDE,
481  ED25519_PUBKEY_LEN, auth_key->pubkey);
482 }
483 
484 /** Public function: Register rendezvous circuit with key <b>cookie</b> to the
485  * circuitmap. */
486 void
488  const uint8_t *cookie)
489 {
491  HS_TOKEN_REND_SERVICE_SIDE,
492  REND_TOKEN_LEN, cookie);
493 }
494 
495 /** Public function: Register rendezvous circuit with key <b>cookie</b> to the
496  * client-side circuitmap. */
497 void
499  const uint8_t *cookie)
500 {
501  circuit_t *circ = TO_CIRCUIT(or_circ);
502  { /* Basic circ purpose sanity checking */
503  tor_assert_nonfatal(circ->purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND);
504  }
505 
506  hs_circuitmap_register_circuit(circ, HS_TOKEN_REND_CLIENT_SIDE,
507  REND_TOKEN_LEN, cookie);
508 }
509 
510 /**** Misc public functions: */
511 
512 /** Public function: Remove this circuit from the HS circuitmap. Clear its HS
513  * token, and remove it from the hashtable. */
514 void
516 {
518 
519  if (!circ || !circ->hs_token) {
520  return;
521  }
522 
523  /* Remove circ from circuitmap */
524  circuit_t *tmp;
525  tmp = HT_REMOVE(hs_circuitmap_ht, the_hs_circuitmap, circ);
526  /* ... and ensure the removal was successful. */
527  if (tmp) {
528  tor_assert(tmp == circ);
529  } else {
530  log_warn(LD_BUG, "Could not find circuit (%u) in circuitmap.",
531  circ->n_circ_id);
532  }
533 
534  /* Clear token from circ */
535  hs_token_free(circ->hs_token);
536  circ->hs_token = NULL;
537 }
538 
539 /** Public function: Initialize the global HS circuitmap. */
540 void
542 {
544 
545  the_hs_circuitmap = tor_malloc_zero(sizeof(struct hs_circuitmap_ht));
546  HT_INIT(hs_circuitmap_ht, the_hs_circuitmap);
547 }
548 
549 /** Public function: Free all memory allocated by the global HS circuitmap. */
550 void
552 {
553  if (the_hs_circuitmap) {
554  HT_CLEAR(hs_circuitmap_ht, the_hs_circuitmap);
556  }
557 }
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:166
or_circuit_t * TO_OR_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:154
Header file for circuitlist.c.
#define CIRCUIT_PURPOSE_S_CONNECT_REND
Definition: circuitlist.h:107
#define CIRCUIT_PURPOSE_REND_POINT_WAITING
Definition: circuitlist.h:45
#define CIRCUIT_IS_ORCIRC(c)
Definition: circuitlist.h:154
#define CIRCUIT_PURPOSE_IS_ORIGIN(p)
Definition: circuitlist.h:140
#define CIRCUIT_PURPOSE_C_REND_JOINED
Definition: circuitlist.h:88
#define CIRCUIT_PURPOSE_S_INTRO
Definition: circuitlist.h:104
#define CIRCUIT_PURPOSE_INTRO_POINT
Definition: circuitlist.h:42
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:147
#define CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
Definition: circuitlist.h:86
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:110
#define CIRCUIT_PURPOSE_C_REND_READY
Definition: circuitlist.h:83
#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
Definition: circuitlist.h:101
#define CIRCUIT_PURPOSE_C_ESTABLISH_REND
Definition: circuitlist.h:81
Header file for config.c.
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
static circuit_t * get_circuit_with_token(hs_token_t *search_token)
or_circuit_t * hs_circuitmap_get_intro_circ_v3_relay_side(const ed25519_public_key_t *auth_key)
void hs_circuitmap_free_all(void)
void hs_circuitmap_remove_circuit(circuit_t *circ)
static int hs_circuits_have_same_token(const circuit_t *first_circuit, const circuit_t *second_circuit)
Definition: hs_circuitmap.c:34
static unsigned int hs_circuit_hash_token(const circuit_t *circuit)
Definition: hs_circuitmap.c:67
void hs_circuitmap_register_rend_circ_client_side(origin_circuit_t *or_circ, const uint8_t *cookie)
static hs_token_t * hs_token_new(hs_token_type_t type, size_t token_len, const uint8_t *token)
void hs_circuitmap_init(void)
origin_circuit_t * hs_circuitmap_get_intro_circ_v3_service_side(const ed25519_public_key_t *auth_key)
static void hs_circuitmap_register_circuit(circuit_t *circ, hs_token_type_t type, size_t token_len, const uint8_t *token)
or_circuit_t * hs_circuitmap_get_rend_circ_relay_side(const uint8_t *cookie)
origin_circuit_t * hs_circuitmap_get_established_rend_circ_client_side(const uint8_t *cookie)
void hs_circuitmap_register_intro_circ_v3_service_side(origin_circuit_t *circ, const ed25519_public_key_t *auth_key)
static or_circuit_t * hs_circuitmap_get_or_circuit(hs_token_type_t type, size_t token_len, const uint8_t *token, uint8_t wanted_circ_purpose)
origin_circuit_t * hs_circuitmap_get_rend_circ_client_side(const uint8_t *cookie)
static struct hs_circuitmap_ht * the_hs_circuitmap
Definition: hs_circuitmap.c:29
smartlist_t * hs_circuitmap_get_all_intro_circ_relay_side(void)
HT_PROTOTYPE(hs_circuitmap_ht, circuit_t, hs_circuitmap_node, hs_circuit_hash_token, hs_circuits_have_same_token)
static origin_circuit_t * hs_circuitmap_get_origin_circuit(hs_token_type_t type, size_t token_len, const uint8_t *token, uint8_t wanted_circ_purpose)
static circuit_t * hs_circuitmap_get_circuit_impl(hs_token_type_t type, size_t token_len, const uint8_t *token, uint8_t wanted_circ_purpose)
origin_circuit_t * hs_circuitmap_get_rend_circ_service_side(const uint8_t *cookie)
void hs_circuitmap_register_rend_circ_service_side(origin_circuit_t *circ, const uint8_t *cookie)
static void hs_token_free_(hs_token_t *hs_token)
void hs_circuitmap_register_rend_circ_relay_side(or_circuit_t *circ, const uint8_t *cookie)
static void hs_circuitmap_register_impl(circuit_t *circ, hs_token_t *token)
void hs_circuitmap_register_intro_circ_v3_relay_side(or_circuit_t *circ, const ed25519_public_key_t *auth_key)
Header file for hs_circuitmap.c.
#define LD_BUG
Definition: log.h:86
void tor_free_(void *mem)
Definition: malloc.c:227
#define tor_free(p)
Definition: malloc.h:52
Master header file for Tor-specific functionality.
#define TO_CIRCUIT(x)
Definition: or.h:845
Origin circuit structure.
smartlist_t * smartlist_new(void)
void smartlist_add(smartlist_t *sl, void *element)
struct hs_token_t * hs_token
Definition: circuit_st.h:216
uint16_t marked_for_close
Definition: circuit_st.h:189
uint8_t purpose
Definition: circuit_st.h:111
circid_t n_circ_id
Definition: circuit_st.h:78
#define tor_assert(expr)
Definition: util_bug.h:102
#define ED25519_PUBKEY_LEN
Definition: x25519_sizes.h:27