Tor 0.4.9.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"
37
38#include "core/or/or_circuit_st.h"
39#include "core/or/channel.h"
40
41/** Onion queue default, max and min. */
42
43/* In seconds. */
44#define ONION_QUEUE_WAIT_CUTOFF_DEFAULT 5
45#define ONION_QUEUE_WAIT_CUTOFF_MIN 0
46#define ONION_QUEUE_WAIT_CUTOFF_MAX INT32_MAX
47
48/* In msec. */
49#define ONION_QUEUE_MAX_DELAY_DEFAULT 1750
50#define ONION_QUEUE_MAX_DELAY_MIN 1
51#define ONION_QUEUE_MAX_DELAY_MAX INT32_MAX
52
53#define NUM_NTORS_PER_TAP_DEFAULT 10
54#define NUM_NTORS_PER_TAP_MIN 1
55#define NUM_NTORS_PER_TAP_MAX 100000
56
57/** Type for a linked list of circuits that are waiting for a free CPU worker
58 * to process a waiting onion handshake. */
59typedef struct onion_queue_t {
60 TOR_TAILQ_ENTRY(onion_queue_t) next;
61 or_circuit_t *circ;
62 uint16_t queue_idx;
63 create_cell_t *onionskin;
64 time_t when_added;
66
67TOR_TAILQ_HEAD(onion_queue_head_t, onion_queue_t);
68typedef struct onion_queue_head_t onion_queue_head_t;
69
70/** We have 3 queues: tap, fast, and ntor. (ntorv3 goes into ntor queue). */
71#define MAX_QUEUE_IDX ONION_HANDSHAKE_TYPE_NTOR
72
73/** Array of queues of circuits waiting for CPU workers. An element is NULL
74 * if that queue is empty.*/
75static onion_queue_head_t ol_list[MAX_QUEUE_IDX+1] =
76{ TOR_TAILQ_HEAD_INITIALIZER(ol_list[0]), /* tap */
77 TOR_TAILQ_HEAD_INITIALIZER(ol_list[1]), /* fast */
78 TOR_TAILQ_HEAD_INITIALIZER(ol_list[2]), /* ntor */
79};
80
81/** Number of entries of each type currently in each element of ol_list[]. */
83
84static void onion_queue_entry_remove(onion_queue_t *victim);
85
86/** Consensus parameters. */
87static int32_t ns_num_ntors_per_tap = NUM_NTORS_PER_TAP_DEFAULT;
88static time_t ns_onion_queue_wait_cutoff = ONION_QUEUE_WAIT_CUTOFF_DEFAULT;
89static uint32_t ns_onion_queue_max_delay = ONION_QUEUE_MAX_DELAY_DEFAULT;
90
91/** Return the number of ntors per tap from the cached parameter. */
92static inline int32_t
94{
96}
97
98/** Return the onion queue wait cutoff value from the cached parameter. */
99static inline time_t
101{
102 return ns_onion_queue_wait_cutoff;
103}
104
105/** Return the max onion queue delay value either from the torrc options (if
106 * the user explicitly set it) else from the cached parameter. */
107static inline uint32_t
109{
110 if (options && options->MaxOnionQueueDelay > 0) {
111 return options->MaxOnionQueueDelay;
112 }
113 return ns_onion_queue_max_delay;
114}
115
116/**
117 * We combine ntorv3 and ntor into the same queue, so we must
118 * use this function to convert the cell type to a queue index.
119 */
120static inline uint16_t
122{
123 if (type == ONION_HANDSHAKE_TYPE_NTOR_V3) {
124 return ONION_HANDSHAKE_TYPE_NTOR;
125 }
126
127 if (BUG(type > MAX_QUEUE_IDX)) {
128 return MAX_QUEUE_IDX; // use ntor if out of range
129 }
130
131 return type;
132}
133
134/* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN.
135 *
136 * (By which I think I meant, "make sure that no
137 * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than
138 * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN." Also, make sure that we can pass
139 * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/
140
141/** Return true iff we have room to queue another onionskin of type
142 * <b>type</b>. */
143static int
145{
146 const or_options_t *options = get_options();
147 int num_cpus;
148 uint64_t max_onion_queue_delay;
149 uint64_t tap_usec, ntor_usec;
150 uint64_t ntor_during_tap_usec, tap_during_ntor_usec;
151
152 /* If we've got fewer than 50 entries, we always have room for one more. */
153 if (ol_entries[type] < 50)
154 return 1;
155
156 /* If zero, this means our thread pool was never initialized meaning we can't
157 * really get here but make sure we don't have such value because we are
158 * using as a divisor. */
159 num_cpus = cpuworker_get_n_threads();
160 tor_assert(num_cpus > 0);
161
162 max_onion_queue_delay = get_onion_queue_max_delay(options);
163
164 /* Compute how many microseconds we'd expect to need to clear all
165 * onionskins in various combinations of the queues. */
166
167 /* How long would it take to process all the TAP cells in the queue? */
169 ol_entries[ONION_HANDSHAKE_TYPE_TAP],
170 ONION_HANDSHAKE_TYPE_TAP) / num_cpus;
171
172 /* How long would it take to process all the NTor cells in the queue? */
174 ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
175 ONION_HANDSHAKE_TYPE_NTOR) / num_cpus;
176
177 /* How long would it take to process the tap cells that we expect to
178 * process while draining the ntor queue? */
179 tap_during_ntor_usec = estimated_usec_for_onionskins(
180 MIN(ol_entries[ONION_HANDSHAKE_TYPE_TAP],
181 ol_entries[ONION_HANDSHAKE_TYPE_NTOR] / get_num_ntors_per_tap()),
182 ONION_HANDSHAKE_TYPE_TAP) / num_cpus;
183
184 /* How long would it take to process the ntor cells that we expect to
185 * process while draining the tap queue? */
186 ntor_during_tap_usec = estimated_usec_for_onionskins(
187 MIN(ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
188 ol_entries[ONION_HANDSHAKE_TYPE_TAP] * get_num_ntors_per_tap()),
189 ONION_HANDSHAKE_TYPE_NTOR) / num_cpus;
190
191 /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue
192 * this. */
193 if (type == ONION_HANDSHAKE_TYPE_NTOR &&
194 (ntor_usec + tap_during_ntor_usec) / 1000 > max_onion_queue_delay)
195 return 0;
196
197 if (type == ONION_HANDSHAKE_TYPE_TAP &&
198 (tap_usec + ntor_during_tap_usec) / 1000 > max_onion_queue_delay)
199 return 0;
200
201 /* If we support the ntor handshake, then don't let TAP handshakes use
202 * more than 2/3 of the space on the queue. */
203 if (type == ONION_HANDSHAKE_TYPE_TAP &&
204 tap_usec / 1000 > max_onion_queue_delay * 2 / 3)
205 return 0;
206
207 return 1;
208}
209
210/** Add <b>circ</b> to the end of ol_list and return 0, except
211 * if ol_list is too long, in which case do nothing and return -1.
212 */
213int
215{
216 onion_queue_t *tmp;
217 time_t now = time(NULL);
218 uint16_t queue_idx = 0;
219
220 if (onionskin->handshake_type > MAX_ONION_HANDSHAKE_TYPE) {
221 /* LCOV_EXCL_START
222 * We should have rejected this far before this point */
223 log_warn(LD_BUG, "Handshake %d out of range! Dropping.",
224 onionskin->handshake_type);
225 return -1;
226 /* LCOV_EXCL_STOP */
227 }
228
229 queue_idx = onionskin_type_to_queue(onionskin->handshake_type);
230
231 tmp = tor_malloc_zero(sizeof(onion_queue_t));
232 tmp->circ = circ;
233 tmp->queue_idx = queue_idx;
234 tmp->onionskin = onionskin;
235 tmp->when_added = now;
236
237 if (!have_room_for_onionskin(queue_idx)) {
238#define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60)
239 static ratelim_t last_warned =
240 RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL);
241 if (!channel_is_client(circ->p_chan)) {
242 // Avoid counting create cells from clients, to go with the same
243 // check in command_process_create_cell().
245 }
246 if (queue_idx == ONION_HANDSHAKE_TYPE_NTOR) {
247 char *m;
248 if ((m = rate_limit_log(&last_warned, approx_time()))) {
249 log_warn(LD_GENERAL,
250 "Your computer is too slow to handle this many circuit "
251 "creation requests! Please consider using the "
252 "MaxAdvertisedBandwidth config option or choosing a more "
253 "restricted exit policy.%s",
254 m);
255 tor_free(m);
256 }
257 }
258 tor_free(tmp);
259 return -1;
260 }
261
262 ++ol_entries[queue_idx];
263 log_info(LD_OR, "New create (%s). Queues now ntor=%d and tap=%d.",
264 queue_idx == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap",
265 ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
266 ol_entries[ONION_HANDSHAKE_TYPE_TAP]);
267
268 circ->onionqueue_entry = tmp;
269 TOR_TAILQ_INSERT_TAIL(&ol_list[queue_idx], tmp, next);
270
271 /* cull elderly requests. */
272 while (1) {
273 onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[queue_idx]);
274 if (now - head->when_added < get_onion_queue_wait_cutoff())
275 break;
276
277 circ = head->circ;
278 circ->onionqueue_entry = NULL;
280 log_info(LD_CIRC,
281 "Circuit create request is too old; canceling due to overload.");
282 if (! TO_CIRCUIT(circ)->marked_for_close) {
283 circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_RESOURCELIMIT);
284 }
285 }
286 return 0;
287}
288
289/** Choose which onion queue we'll pull from next. If one is empty choose
290 * the other; if they both have elements, load balance across them but
291 * favoring NTOR. */
292static uint16_t
294{
295 /* The number of times we've chosen ntor lately when both were available. */
296 static int recently_chosen_ntors = 0;
297
298 if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR])
299 return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */
300
301 if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) {
302
303 /* Nick wants us to prioritize new tap requests when there aren't
304 * any in the queue and we've processed k ntor cells since the last
305 * tap cell. This strategy is maybe a good idea, since it starves tap
306 * less in the case where tap is rare, or maybe a poor idea, since it
307 * makes the new tap cell unfairly jump in front of ntor cells that
308 * got here first. In any case this edge case will only become relevant
309 * once tap is rare. We should reevaluate whether we like this decision
310 * once tap gets more rare. */
311 if (ol_entries[ONION_HANDSHAKE_TYPE_NTOR] &&
312 recently_chosen_ntors <= get_num_ntors_per_tap())
313 ++recently_chosen_ntors;
314
315 return ONION_HANDSHAKE_TYPE_NTOR; /* no taps? try ntor */
316 }
317
318 /* They both have something queued. Pick ntor if we haven't done that
319 * too much lately. */
320 if (++recently_chosen_ntors <= get_num_ntors_per_tap()) {
321 return ONION_HANDSHAKE_TYPE_NTOR;
322 }
323
324 /* Else, it's time to let tap have its turn. */
325 recently_chosen_ntors = 0;
326 return ONION_HANDSHAKE_TYPE_TAP;
327}
328
329/** Remove the highest priority item from ol_list[] and return it, or
330 * return NULL if the lists are empty.
331 */
334{
335 or_circuit_t *circ;
336 uint16_t handshake_to_choose = decide_next_handshake_type();
337 onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[handshake_to_choose]);
338
339 if (!head)
340 return NULL; /* no onions pending, we're done */
341
342 tor_assert(head->circ);
343 tor_assert(head->queue_idx <= MAX_QUEUE_IDX);
344// tor_assert(head->circ->p_chan); /* make sure it's still valid */
345/* XXX I only commented out the above line to make the unit tests
346 * more manageable. That's probably not good long-term. -RD */
347 circ = head->circ;
348 if (head->onionskin)
349 --ol_entries[head->queue_idx];
350 log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.",
351 head->queue_idx == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap",
352 ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
353 ol_entries[ONION_HANDSHAKE_TYPE_TAP]);
354
355 *onionskin_out = head->onionskin;
356 head->onionskin = NULL; /* prevent free. */
357 circ->onionqueue_entry = NULL;
359 return circ;
360}
361
362/** Return the number of <b>handshake_type</b>-style create requests pending.
363 */
364int
365onion_num_pending(uint16_t handshake_type)
366{
367 return ol_entries[onionskin_type_to_queue(handshake_type)];
368}
369
370/** Go through ol_list, find the onion_queue_t element which points to
371 * circ, remove and free that element. Leave circ itself alone.
372 */
373void
375{
376 onion_queue_t *victim;
377
378 if (!circ)
379 return;
380
381 victim = circ->onionqueue_entry;
382 if (victim)
384
386}
387
388/** Remove a queue entry <b>victim</b> from the queue, unlinking it from
389 * its circuit and freeing it and any structures it owns.*/
390static void
392{
393 if (victim->queue_idx > MAX_QUEUE_IDX) {
394 /* LCOV_EXCL_START
395 * We should have rejected this far before this point */
396 log_warn(LD_BUG, "Handshake %d out of range! Dropping.",
397 victim->queue_idx);
398 /* XXX leaks */
399 return;
400 /* LCOV_EXCL_STOP */
401 }
402
403 TOR_TAILQ_REMOVE(&ol_list[victim->queue_idx], victim, next);
404
405 if (victim->circ)
406 victim->circ->onionqueue_entry = NULL;
407
408 if (victim->onionskin)
409 --ol_entries[victim->queue_idx];
410
411 tor_free(victim->onionskin);
412 tor_free(victim);
413}
414
415/** Remove all circuits from the pending list. Called from tor_free_all. */
416void
418{
419 onion_queue_t *victim, *next;
420 int i;
421 for (i=0; i<=MAX_QUEUE_IDX; i++) {
422 for (victim = TOR_TAILQ_FIRST(&ol_list[i]); victim; victim = next) {
423 next = TOR_TAILQ_NEXT(victim,next);
425 }
426 tor_assert(TOR_TAILQ_EMPTY(&ol_list[i]));
427 }
428 memset(ol_entries, 0, sizeof(ol_entries));
429}
430
431/** Consensus has changed, update the cached parameters. */
432void
434{
435 tor_assert(ns);
436
437 ns_onion_queue_max_delay =
438 networkstatus_get_param(ns, "MaxOnionQueueDelay",
439 ONION_QUEUE_MAX_DELAY_DEFAULT,
440 ONION_QUEUE_MAX_DELAY_MIN,
441 ONION_QUEUE_MAX_DELAY_MAX);
442
443 ns_onion_queue_wait_cutoff =
444 networkstatus_get_param(ns, "onion_queue_wait_cutoff",
446 ONION_QUEUE_WAIT_CUTOFF_MIN,
447 ONION_QUEUE_WAIT_CUTOFF_MAX);
448
450 networkstatus_get_param(ns, "NumNTorsPerTAP",
451 NUM_NTORS_PER_TAP_DEFAULT,
452 NUM_NTORS_PER_TAP_MIN,
453 NUM_NTORS_PER_TAP_MAX);
454}
time_t approx_time(void)
Definition: approx_time.c:32
int channel_is_client(const channel_t *chan)
Definition: channel.c:2918
Header file for channel.c.
Header file for circuitlist.c.
const or_options_t * get_options(void)
Definition: config.c:944
Header file for config.c.
void cpuworker_cancel_circ_handshake(or_circuit_t *circ)
Definition: cpuworker.c:657
unsigned int cpuworker_get_n_threads(void)
Definition: cpuworker.c:150
uint64_t estimated_usec_for_onionskins(uint32_t n_requests, uint16_t onionskin_type)
Definition: cpuworker.c:298
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:56
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:417
static int ol_entries[MAX_QUEUE_IDX+1]
Definition: onion_queue.c:82
static time_t get_onion_queue_wait_cutoff(void)
Definition: onion_queue.c:100
static uint32_t get_onion_queue_max_delay(const or_options_t *options)
Definition: onion_queue.c:108
static int32_t get_num_ntors_per_tap(void)
Definition: onion_queue.c:93
#define ONION_QUEUE_WAIT_CUTOFF_DEFAULT
Definition: onion_queue.c:44
void onion_consensus_has_changed(const networkstatus_t *ns)
Definition: onion_queue.c:433
static onion_queue_head_t ol_list[MAX_QUEUE_IDX+1]
Definition: onion_queue.c:75
int onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin)
Definition: onion_queue.c:214
int onion_num_pending(uint16_t handshake_type)
Definition: onion_queue.c:365
static int have_room_for_onionskin(uint16_t type)
Definition: onion_queue.c:144
static int32_t ns_num_ntors_per_tap
Definition: onion_queue.c:87
void onion_pending_remove(or_circuit_t *circ)
Definition: onion_queue.c:374
or_circuit_t * onion_next_task(create_cell_t **onionskin_out)
Definition: onion_queue.c:333
static void onion_queue_entry_remove(onion_queue_t *victim)
Definition: onion_queue.c:391
static uint16_t onionskin_type_to_queue(uint16_t type)
Definition: onion_queue.c:121
#define MAX_QUEUE_IDX
Definition: onion_queue.c:71
static uint16_t decide_next_handshake_type(void)
Definition: onion_queue.c:293
Header file for onion_queue.c.
Master header file for Tor-specific functionality.
#define TO_CIRCUIT(x)
Definition: or.h:848
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:2393
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
channel_t * p_chan
Definition: or_circuit_st.h:37
#define tor_assert(expr)
Definition: util_bug.h:103