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
29 #include "feature/relay/onion_queue.h"
30
31 #include "app/config/config.h"
32 #include "core/mainloop/cpuworker.h"
33 #include "core/or/circuitlist.h"
34 #include "core/or/onion.h"
35 #include "feature/nodelist/networkstatus.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;
48 } onion_queue_t;
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
have_room_for_onionskin(uint16_t type)80 have_room_for_onionskin(uint16_t type)
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? */
95 tap_usec = estimated_usec_for_onionskins(
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
onion_pending_add(or_circuit_t * circ,create_cell_t * onionskin)143 onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin)
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);
167 rep_hist_note_circuit_handshake_dropped(onionskin->handshake_type);
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;
203 onion_queue_entry_remove(head);
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
num_ntors_per_tap(void)217 num_ntors_per_tap(void)
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
decide_next_handshake_type(void)235 decide_next_handshake_type(void)
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 *
onion_next_task(create_cell_t ** onionskin_out)275 onion_next_task(create_cell_t **onionskin_out)
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;
300 onion_queue_entry_remove(head);
301 return circ;
302 }
303
304 /** Return the number of <b>handshake_type</b>-style create requests pending.
305 */
306 int
onion_num_pending(uint16_t handshake_type)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
onion_pending_remove(or_circuit_t * circ)316 onion_pending_remove(or_circuit_t *circ)
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
327 cpuworker_cancel_circ_handshake(circ);
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
onion_queue_entry_remove(onion_queue_t * victim)333 onion_queue_entry_remove(onion_queue_t *victim)
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
clear_pending_onions(void)359 clear_pending_onions(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 }
372