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