Tor  0.4.4.0-alpha-dev
onion_queue.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-2020, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
7 /**
8  * \file onion_queue.c
9  * \brief Functions to queue create cells for processing.
10  *
11  * Relays invoke these functions when they receive a CREATE or EXTEND
12  * cell in command.c or relay.c, in order to queue the pending request.
13  * They also invoke them from cpuworker.c, which handles dispatching
14  * onionskin requests to different worker threads.
15  *
16  * <br>
17  *
18  * This module also handles:
19  * <ul>
20  * <li> Queueing incoming onionskins on the relay side before passing
21  * them to worker threads.
22  * <li>Expiring onionskins on the relay side if they have waited for
23  * too long.
24  * </ul>
25  **/
26 
27 #include "core/or/or.h"
28 
30 
31 #include "app/config/config.h"
33 #include "core/or/circuitlist.h"
34 #include "core/or/onion.h"
36 
37 #include "core/or/or_circuit_st.h"
38 
39 /** Type for a linked list of circuits that are waiting for a free CPU worker
40  * to process a waiting onion handshake. */
41 typedef struct onion_queue_t {
42  TOR_TAILQ_ENTRY(onion_queue_t) next;
43  or_circuit_t *circ;
44  uint16_t handshake_type;
45  create_cell_t *onionskin;
46  time_t when_added;
48 
49 /** 5 seconds on the onion queue til we just send back a destroy */
50 #define ONIONQUEUE_WAIT_CUTOFF 5
51 
52 TOR_TAILQ_HEAD(onion_queue_head_t, onion_queue_t);
53 typedef struct onion_queue_head_t onion_queue_head_t;
54 
55 /** Array of queues of circuits waiting for CPU workers. An element is NULL
56  * if that queue is empty.*/
57 static onion_queue_head_t ol_list[MAX_ONION_HANDSHAKE_TYPE+1] =
58 { TOR_TAILQ_HEAD_INITIALIZER(ol_list[0]), /* tap */
59  TOR_TAILQ_HEAD_INITIALIZER(ol_list[1]), /* fast */
60  TOR_TAILQ_HEAD_INITIALIZER(ol_list[2]), /* ntor */
61 };
62 
63 /** Number of entries of each type currently in each element of ol_list[]. */
64 static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1];
65 
66 static int num_ntors_per_tap(void);
67 static void onion_queue_entry_remove(onion_queue_t *victim);
68 
69 /* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN.
70  *
71  * (By which I think I meant, "make sure that no
72  * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than
73  * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN." Also, make sure that we can pass
74  * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/
75 
76 /** Return true iff we have room to queue another onionskin of type
77  * <b>type</b>. */
78 static int
80 {
81  const or_options_t *options = get_options();
82  int num_cpus;
83  uint64_t tap_usec, ntor_usec;
84  uint64_t ntor_during_tap_usec, tap_during_ntor_usec;
85 
86  /* If we've got fewer than 50 entries, we always have room for one more. */
87  if (ol_entries[type] < 50)
88  return 1;
89  num_cpus = get_num_cpus(options);
90  /* Compute how many microseconds we'd expect to need to clear all
91  * onionskins in various combinations of the queues. */
92 
93  /* How long would it take to process all the TAP cells in the queue? */
95  ol_entries[ONION_HANDSHAKE_TYPE_TAP],
96  ONION_HANDSHAKE_TYPE_TAP) / num_cpus;
97 
98  /* How long would it take to process all the NTor cells in the queue? */
100  ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
101  ONION_HANDSHAKE_TYPE_NTOR) / num_cpus;
102 
103  /* How long would it take to process the tap cells that we expect to
104  * process while draining the ntor queue? */
105  tap_during_ntor_usec = estimated_usec_for_onionskins(
106  MIN(ol_entries[ONION_HANDSHAKE_TYPE_TAP],
107  ol_entries[ONION_HANDSHAKE_TYPE_NTOR] / num_ntors_per_tap()),
108  ONION_HANDSHAKE_TYPE_TAP) / num_cpus;
109 
110  /* How long would it take to process the ntor cells that we expect to
111  * process while draining the tap queue? */
112  ntor_during_tap_usec = estimated_usec_for_onionskins(
113  MIN(ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
114  ol_entries[ONION_HANDSHAKE_TYPE_TAP] * num_ntors_per_tap()),
115  ONION_HANDSHAKE_TYPE_NTOR) / num_cpus;
116 
117  /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue
118  * this. */
119  if (type == ONION_HANDSHAKE_TYPE_NTOR &&
120  (ntor_usec + tap_during_ntor_usec) / 1000 >
121  (uint64_t)options->MaxOnionQueueDelay)
122  return 0;
123 
124  if (type == ONION_HANDSHAKE_TYPE_TAP &&
125  (tap_usec + ntor_during_tap_usec) / 1000 >
126  (uint64_t)options->MaxOnionQueueDelay)
127  return 0;
128 
129  /* If we support the ntor handshake, then don't let TAP handshakes use
130  * more than 2/3 of the space on the queue. */
131  if (type == ONION_HANDSHAKE_TYPE_TAP &&
132  tap_usec / 1000 > (uint64_t)options->MaxOnionQueueDelay * 2 / 3)
133  return 0;
134 
135  return 1;
136 }
137 
138 /** Add <b>circ</b> to the end of ol_list and return 0, except
139  * if ol_list is too long, in which case do nothing and return -1.
140  */
141 int
143 {
144  onion_queue_t *tmp;
145  time_t now = time(NULL);
146 
147  if (onionskin->handshake_type > MAX_ONION_HANDSHAKE_TYPE) {
148  /* LCOV_EXCL_START
149  * We should have rejected this far before this point */
150  log_warn(LD_BUG, "Handshake %d out of range! Dropping.",
151  onionskin->handshake_type);
152  return -1;
153  /* LCOV_EXCL_STOP */
154  }
155 
156  tmp = tor_malloc_zero(sizeof(onion_queue_t));
157  tmp->circ = circ;
158  tmp->handshake_type = onionskin->handshake_type;
159  tmp->onionskin = onionskin;
160  tmp->when_added = now;
161 
162  if (!have_room_for_onionskin(onionskin->handshake_type)) {
163 #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60)
164  static ratelim_t last_warned =
165  RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL);
166  char *m;
167  if (onionskin->handshake_type == ONION_HANDSHAKE_TYPE_NTOR &&
168  (m = rate_limit_log(&last_warned, approx_time()))) {
169  log_warn(LD_GENERAL,
170  "Your computer is too slow to handle this many circuit "
171  "creation requests! Please consider using the "
172  "MaxAdvertisedBandwidth config option or choosing a more "
173  "restricted exit policy.%s",m);
174  tor_free(m);
175  }
176  tor_free(tmp);
177  return -1;
178  }
179 
180  ++ol_entries[onionskin->handshake_type];
181  log_info(LD_OR, "New create (%s). Queues now ntor=%d and tap=%d.",
182  onionskin->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap",
183  ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
184  ol_entries[ONION_HANDSHAKE_TYPE_TAP]);
185 
186  circ->onionqueue_entry = tmp;
187  TOR_TAILQ_INSERT_TAIL(&ol_list[onionskin->handshake_type], tmp, next);
188 
189  /* cull elderly requests. */
190  while (1) {
191  onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[onionskin->handshake_type]);
192  if (now - head->when_added < (time_t)ONIONQUEUE_WAIT_CUTOFF)
193  break;
194 
195  circ = head->circ;
196  circ->onionqueue_entry = NULL;
198  log_info(LD_CIRC,
199  "Circuit create request is too old; canceling due to overload.");
200  if (! TO_CIRCUIT(circ)->marked_for_close) {
201  circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_RESOURCELIMIT);
202  }
203  }
204  return 0;
205 }
206 
207 /** Return a fairness parameter, to prefer processing NTOR style
208  * handshakes but still slowly drain the TAP queue so we don't starve
209  * it entirely. */
210 static int
212 {
213 #define DEFAULT_NUM_NTORS_PER_TAP 10
214 #define MIN_NUM_NTORS_PER_TAP 1
215 #define MAX_NUM_NTORS_PER_TAP 100000
216 
217  int result = networkstatus_get_param(NULL, "NumNTorsPerTAP",
218  DEFAULT_NUM_NTORS_PER_TAP,
219  MIN_NUM_NTORS_PER_TAP,
220  MAX_NUM_NTORS_PER_TAP);
221  tor_assert(result > 0);
222  return result;
223 }
224 
225 /** Choose which onion queue we'll pull from next. If one is empty choose
226  * the other; if they both have elements, load balance across them but
227  * favoring NTOR. */
228 static uint16_t
230 {
231  /* The number of times we've chosen ntor lately when both were available. */
232  static int recently_chosen_ntors = 0;
233 
234  if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR])
235  return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */
236 
237  if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) {
238 
239  /* Nick wants us to prioritize new tap requests when there aren't
240  * any in the queue and we've processed k ntor cells since the last
241  * tap cell. This strategy is maybe a good idea, since it starves tap
242  * less in the case where tap is rare, or maybe a poor idea, since it
243  * makes the new tap cell unfairly jump in front of ntor cells that
244  * got here first. In any case this edge case will only become relevant
245  * once tap is rare. We should reevaluate whether we like this decision
246  * once tap gets more rare. */
247  if (ol_entries[ONION_HANDSHAKE_TYPE_NTOR] &&
248  recently_chosen_ntors <= num_ntors_per_tap())
249  ++recently_chosen_ntors;
250 
251  return ONION_HANDSHAKE_TYPE_NTOR; /* no taps? try ntor */
252  }
253 
254  /* They both have something queued. Pick ntor if we haven't done that
255  * too much lately. */
256  if (++recently_chosen_ntors <= num_ntors_per_tap()) {
257  return ONION_HANDSHAKE_TYPE_NTOR;
258  }
259 
260  /* Else, it's time to let tap have its turn. */
261  recently_chosen_ntors = 0;
262  return ONION_HANDSHAKE_TYPE_TAP;
263 }
264 
265 /** Remove the highest priority item from ol_list[] and return it, or
266  * return NULL if the lists are empty.
267  */
268 or_circuit_t *
270 {
271  or_circuit_t *circ;
272  uint16_t handshake_to_choose = decide_next_handshake_type();
273  onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[handshake_to_choose]);
274 
275  if (!head)
276  return NULL; /* no onions pending, we're done */
277 
278  tor_assert(head->circ);
279  tor_assert(head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE);
280 // tor_assert(head->circ->p_chan); /* make sure it's still valid */
281 /* XXX I only commented out the above line to make the unit tests
282  * more manageable. That's probably not good long-term. -RD */
283  circ = head->circ;
284  if (head->onionskin)
285  --ol_entries[head->handshake_type];
286  log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.",
287  head->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap",
288  ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
289  ol_entries[ONION_HANDSHAKE_TYPE_TAP]);
290 
291  *onionskin_out = head->onionskin;
292  head->onionskin = NULL; /* prevent free. */
293  circ->onionqueue_entry = NULL;
295  return circ;
296 }
297 
298 /** Return the number of <b>handshake_type</b>-style create requests pending.
299  */
300 int
301 onion_num_pending(uint16_t handshake_type)
302 {
303  return ol_entries[handshake_type];
304 }
305 
306 /** Go through ol_list, find the onion_queue_t element which points to
307  * circ, remove and free that element. Leave circ itself alone.
308  */
309 void
311 {
312  onion_queue_t *victim;
313 
314  if (!circ)
315  return;
316 
317  victim = circ->onionqueue_entry;
318  if (victim)
319  onion_queue_entry_remove(victim);
320 
322 }
323 
324 /** Remove a queue entry <b>victim</b> from the queue, unlinking it from
325  * its circuit and freeing it and any structures it owns.*/
326 static void
328 {
329  if (victim->handshake_type > MAX_ONION_HANDSHAKE_TYPE) {
330  /* LCOV_EXCL_START
331  * We should have rejected this far before this point */
332  log_warn(LD_BUG, "Handshake %d out of range! Dropping.",
333  victim->handshake_type);
334  /* XXX leaks */
335  return;
336  /* LCOV_EXCL_STOP */
337  }
338 
339  TOR_TAILQ_REMOVE(&ol_list[victim->handshake_type], victim, next);
340 
341  if (victim->circ)
342  victim->circ->onionqueue_entry = NULL;
343 
344  if (victim->onionskin)
345  --ol_entries[victim->handshake_type];
346 
347  tor_free(victim->onionskin);
348  tor_free(victim);
349 }
350 
351 /** Remove all circuits from the pending list. Called from tor_free_all. */
352 void
354 {
355  onion_queue_t *victim, *next;
356  int i;
357  for (i=0; i<=MAX_ONION_HANDSHAKE_TYPE; i++) {
358  for (victim = TOR_TAILQ_FIRST(&ol_list[i]); victim; victim = next) {
359  next = TOR_TAILQ_NEXT(victim,next);
360  onion_queue_entry_remove(victim);
361  }
362  tor_assert(TOR_TAILQ_EMPTY(&ol_list[i]));
363  }
364  memset(ol_entries, 0, sizeof(ol_entries));
365 }
tor_free
#define tor_free(p)
Definition: malloc.h:52
onion_pending_add
int onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin)
Definition: onion_queue.c:142
approx_time
time_t approx_time(void)
Definition: approx_time.c:32
create_cell_t::handshake_type
uint16_t handshake_type
Definition: onion.h:28
tor_assert
#define tor_assert(expr)
Definition: util_bug.h:102
LD_BUG
#define LD_BUG
Definition: log.h:86
create_cell_t
Definition: onion.h:24
LD_GENERAL
#define LD_GENERAL
Definition: log.h:62
get_num_cpus
int get_num_cpus(const or_options_t *options)
Definition: config.c:6781
onion.h
Header file for onion.c.
onion_queue.h
Header file for onion_queue.c.
have_room_for_onionskin
static int have_room_for_onionskin(uint16_t type)
Definition: onion_queue.c:79
networkstatus.h
Header file for networkstatus.c.
LD_CIRC
#define LD_CIRC
Definition: log.h:82
circuitlist.h
Header file for circuitlist.c.
cpuworker_cancel_circ_handshake
void cpuworker_cancel_circ_handshake(or_circuit_t *circ)
Definition: cpuworker.c:581
rate_limit_log
char * rate_limit_log(ratelim_t *lim, time_t now)
Definition: ratelim.c:41
decide_next_handshake_type
static uint16_t decide_next_handshake_type(void)
Definition: onion_queue.c:229
ol_list
static onion_queue_head_t ol_list[MAX_ONION_HANDSHAKE_TYPE+1]
Definition: onion_queue.c:57
or_circuit_t::onionqueue_entry
struct onion_queue_t * onionqueue_entry
Definition: or_circuit_st.h:26
LD_OR
#define LD_OR
Definition: log.h:92
clear_pending_onions
void clear_pending_onions(void)
Definition: onion_queue.c:353
onion_next_task
or_circuit_t * onion_next_task(create_cell_t **onionskin_out)
Definition: onion_queue.c:269
get_options
const or_options_t * get_options(void)
Definition: config.c:925
ol_entries
static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1]
Definition: onion_queue.c:64
onion_pending_remove
void onion_pending_remove(or_circuit_t *circ)
Definition: onion_queue.c:310
cpuworker.h
Header file for cpuworker.c.
onion_num_pending
int onion_num_pending(uint16_t handshake_type)
Definition: onion_queue.c:301
or_circuit_t
Definition: or_circuit_st.h:21
estimated_usec_for_onionskins
uint64_t estimated_usec_for_onionskins(uint32_t n_requests, uint16_t onionskin_type)
Definition: cpuworker.c:244
config.h
Header file for config.c.
TO_CIRCUIT
#define TO_CIRCUIT(x)
Definition: or.h:951
or_options_t
Definition: or_options_st.h:39
networkstatus_get_param
int32_t networkstatus_get_param(const networkstatus_t *ns, const char *param_name, int32_t default_val, int32_t min_val, int32_t max_val)
Definition: networkstatus.c:2490
ONIONQUEUE_WAIT_CUTOFF
#define ONIONQUEUE_WAIT_CUTOFF
Definition: onion_queue.c:50
onion_queue_t
Definition: onion_queue.c:41
onion_queue_entry_remove
static void onion_queue_entry_remove(onion_queue_t *victim)
Definition: onion_queue.c:327
ratelim_t
Definition: ratelim.h:42
or.h
Master header file for Tor-specific functionality.
num_ntors_per_tap
static int num_ntors_per_tap(void)
Definition: onion_queue.c:211