tor  0.4.1.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  return networkstatus_get_param(NULL, "NumNTorsPerTAP",
216  DEFAULT_NUM_NTORS_PER_TAP,
217  MIN_NUM_NTORS_PER_TAP,
218  MAX_NUM_NTORS_PER_TAP);
219 }
220 
224 static uint16_t
226 {
227  /* The number of times we've chosen ntor lately when both were available. */
228  static int recently_chosen_ntors = 0;
229 
230  if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR])
231  return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */
232 
233  if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) {
234 
235  /* Nick wants us to prioritize new tap requests when there aren't
236  * any in the queue and we've processed k ntor cells since the last
237  * tap cell. This strategy is maybe a good idea, since it starves tap
238  * less in the case where tap is rare, or maybe a poor idea, since it
239  * makes the new tap cell unfairly jump in front of ntor cells that
240  * got here first. In any case this edge case will only become relevant
241  * once tap is rare. We should reevaluate whether we like this decision
242  * once tap gets more rare. */
243  if (ol_entries[ONION_HANDSHAKE_TYPE_NTOR] &&
244  recently_chosen_ntors <= num_ntors_per_tap())
245  ++recently_chosen_ntors;
246 
247  return ONION_HANDSHAKE_TYPE_NTOR; /* no taps? try ntor */
248  }
249 
250  /* They both have something queued. Pick ntor if we haven't done that
251  * too much lately. */
252  if (++recently_chosen_ntors <= num_ntors_per_tap()) {
253  return ONION_HANDSHAKE_TYPE_NTOR;
254  }
255 
256  /* Else, it's time to let tap have its turn. */
257  recently_chosen_ntors = 0;
258  return ONION_HANDSHAKE_TYPE_TAP;
259 }
260 
264 or_circuit_t *
266 {
267  or_circuit_t *circ;
268  uint16_t handshake_to_choose = decide_next_handshake_type();
269  onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[handshake_to_choose]);
270 
271  if (!head)
272  return NULL; /* no onions pending, we're done */
273 
274  tor_assert(head->circ);
275  tor_assert(head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE);
276 // tor_assert(head->circ->p_chan); /* make sure it's still valid */
277 /* XXX I only commented out the above line to make the unit tests
278  * more manageable. That's probably not good long-term. -RD */
279  circ = head->circ;
280  if (head->onionskin)
281  --ol_entries[head->handshake_type];
282  log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.",
283  head->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap",
284  ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
285  ol_entries[ONION_HANDSHAKE_TYPE_TAP]);
286 
287  *onionskin_out = head->onionskin;
288  head->onionskin = NULL; /* prevent free. */
289  circ->onionqueue_entry = NULL;
291  return circ;
292 }
293 
296 int
297 onion_num_pending(uint16_t handshake_type)
298 {
299  return ol_entries[handshake_type];
300 }
301 
305 void
307 {
308  onion_queue_t *victim;
309 
310  if (!circ)
311  return;
312 
313  victim = circ->onionqueue_entry;
314  if (victim)
315  onion_queue_entry_remove(victim);
316 
318 }
319 
322 static void
324 {
325  if (victim->handshake_type > MAX_ONION_HANDSHAKE_TYPE) {
326  /* LCOV_EXCL_START
327  * We should have rejected this far before this point */
328  log_warn(LD_BUG, "Handshake %d out of range! Dropping.",
329  victim->handshake_type);
330  /* XXX leaks */
331  return;
332  /* LCOV_EXCL_STOP */
333  }
334 
335  TOR_TAILQ_REMOVE(&ol_list[victim->handshake_type], victim, next);
336 
337  if (victim->circ)
338  victim->circ->onionqueue_entry = NULL;
339 
340  if (victim->onionskin)
341  --ol_entries[victim->handshake_type];
342 
343  tor_free(victim->onionskin);
344  tor_free(victim);
345 }
346 
348 void
350 {
351  onion_queue_t *victim, *next;
352  int i;
353  for (i=0; i<=MAX_ONION_HANDSHAKE_TYPE; i++) {
354  for (victim = TOR_TAILQ_FIRST(&ol_list[i]); victim; victim = next) {
355  next = TOR_TAILQ_NEXT(victim,next);
356  onion_queue_entry_remove(victim);
357  }
358  tor_assert(TOR_TAILQ_EMPTY(&ol_list[i]));
359  }
360  memset(ol_entries, 0, sizeof(ol_entries));
361 }
static uint16_t decide_next_handshake_type(void)
Definition: onion_queue.c:225
int onion_num_pending(uint16_t handshake_type)
Definition: onion_queue.c:297
#define LD_GENERAL
Definition: log.h:59
void clear_pending_onions(void)
Definition: onion_queue.c:349
#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:947
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:306
struct onion_queue_t onion_queue_t
struct onion_queue_t * onionqueue_entry
Definition: or_circuit_st.h:24
tor_assert(buffer)
#define LD_CIRC
Definition: log.h:79
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:89
static void onion_queue_entry_remove(onion_queue_t *victim)
Definition: onion_queue.c:323
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:265
time_t approx_time(void)
Definition: approx_time.c:32
int get_num_cpus(const or_options_t *options)
Definition: config.c:7972
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:83
static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1]
Definition: onion_queue.c:59