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