Line data Source code
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
80 2 : have_room_for_onionskin(uint16_t type)
81 : {
82 2 : const or_options_t *options = get_options();
83 2 : int num_cpus;
84 2 : uint64_t tap_usec, ntor_usec;
85 2 : 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 2 : if (ol_entries[type] < 50)
89 : return 1;
90 0 : 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 0 : tap_usec = estimated_usec_for_onionskins(
96 0 : ol_entries[ONION_HANDSHAKE_TYPE_TAP],
97 0 : ONION_HANDSHAKE_TYPE_TAP) / num_cpus;
98 :
99 : /* How long would it take to process all the NTor cells in the queue? */
100 0 : ntor_usec = estimated_usec_for_onionskins(
101 0 : 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 0 : tap_during_ntor_usec = estimated_usec_for_onionskins(
107 0 : 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 0 : ntor_during_tap_usec = estimated_usec_for_onionskins(
114 0 : 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 0 : if (type == ONION_HANDSHAKE_TYPE_NTOR &&
121 0 : (ntor_usec + tap_during_ntor_usec) / 1000 >
122 0 : (uint64_t)options->MaxOnionQueueDelay)
123 : return 0;
124 :
125 0 : if (type == ONION_HANDSHAKE_TYPE_TAP &&
126 0 : (tap_usec + ntor_during_tap_usec) / 1000 >
127 0 : (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 0 : if (type == ONION_HANDSHAKE_TYPE_TAP &&
133 0 : tap_usec / 1000 > (uint64_t)options->MaxOnionQueueDelay * 2 / 3)
134 0 : 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
143 2 : onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin)
144 : {
145 2 : onion_queue_t *tmp;
146 2 : time_t now = time(NULL);
147 :
148 2 : 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 2 : tmp = tor_malloc_zero(sizeof(onion_queue_t));
158 2 : tmp->circ = circ;
159 2 : tmp->handshake_type = onionskin->handshake_type;
160 2 : tmp->onionskin = onionskin;
161 2 : tmp->when_added = now;
162 :
163 2 : if (!have_room_for_onionskin(onionskin->handshake_type)) {
164 : #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60)
165 0 : static ratelim_t last_warned =
166 : RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL);
167 0 : rep_hist_note_circuit_handshake_dropped(onionskin->handshake_type);
168 0 : if (onionskin->handshake_type == ONION_HANDSHAKE_TYPE_NTOR) {
169 0 : char *m;
170 : /* Note this ntor onionskin drop as an overload */
171 0 : rep_hist_note_overload(OVERLOAD_GENERAL);
172 0 : if ((m = rate_limit_log(&last_warned, approx_time()))) {
173 0 : 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 0 : tor_free(m);
180 : }
181 : }
182 0 : tor_free(tmp);
183 0 : return -1;
184 : }
185 :
186 2 : ++ol_entries[onionskin->handshake_type];
187 3 : 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 2 : circ->onionqueue_entry = tmp;
193 2 : TOR_TAILQ_INSERT_TAIL(&ol_list[onionskin->handshake_type], tmp, next);
194 :
195 : /* cull elderly requests. */
196 2 : while (1) {
197 2 : onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[onionskin->handshake_type]);
198 2 : if (now - head->when_added < (time_t)ONIONQUEUE_WAIT_CUTOFF)
199 : break;
200 :
201 0 : circ = head->circ;
202 0 : circ->onionqueue_entry = NULL;
203 0 : onion_queue_entry_remove(head);
204 0 : log_info(LD_CIRC,
205 : "Circuit create request is too old; canceling due to overload.");
206 0 : if (! TO_CIRCUIT(circ)->marked_for_close) {
207 0 : 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
217 1 : 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 1 : 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 1 : tor_assert(result > 0);
228 1 : 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
235 1 : decide_next_handshake_type(void)
236 : {
237 : /* The number of times we've chosen ntor lately when both were available. */
238 1 : static int recently_chosen_ntors = 0;
239 :
240 1 : if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR])
241 : return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */
242 :
243 1 : 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 0 : if (ol_entries[ONION_HANDSHAKE_TYPE_NTOR] &&
254 0 : recently_chosen_ntors <= num_ntors_per_tap())
255 0 : ++recently_chosen_ntors;
256 :
257 0 : 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 1 : 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 0 : recently_chosen_ntors = 0;
268 0 : 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 *
275 1 : onion_next_task(create_cell_t **onionskin_out)
276 : {
277 1 : or_circuit_t *circ;
278 1 : uint16_t handshake_to_choose = decide_next_handshake_type();
279 1 : onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[handshake_to_choose]);
280 :
281 1 : if (!head)
282 : return NULL; /* no onions pending, we're done */
283 :
284 1 : tor_assert(head->circ);
285 1 : 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 1 : circ = head->circ;
290 1 : if (head->onionskin)
291 1 : --ol_entries[head->handshake_type];
292 1 : 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 1 : *onionskin_out = head->onionskin;
298 1 : head->onionskin = NULL; /* prevent free. */
299 1 : circ->onionqueue_entry = NULL;
300 1 : onion_queue_entry_remove(head);
301 1 : return circ;
302 : }
303 :
304 : /** Return the number of <b>handshake_type</b>-style create requests pending.
305 : */
306 : int
307 8 : onion_num_pending(uint16_t handshake_type)
308 : {
309 8 : 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
316 0 : onion_pending_remove(or_circuit_t *circ)
317 : {
318 0 : onion_queue_t *victim;
319 :
320 0 : if (!circ)
321 : return;
322 :
323 0 : victim = circ->onionqueue_entry;
324 0 : if (victim)
325 0 : onion_queue_entry_remove(victim);
326 :
327 0 : 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
333 2 : onion_queue_entry_remove(onion_queue_t *victim)
334 : {
335 2 : 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 2 : TOR_TAILQ_REMOVE(&ol_list[victim->handshake_type], victim, next);
346 :
347 2 : if (victim->circ)
348 2 : victim->circ->onionqueue_entry = NULL;
349 :
350 2 : if (victim->onionskin)
351 1 : --ol_entries[victim->handshake_type];
352 :
353 2 : tor_free(victim->onionskin);
354 2 : tor_free(victim);
355 : }
356 :
357 : /** Remove all circuits from the pending list. Called from tor_free_all. */
358 : void
359 236 : clear_pending_onions(void)
360 : {
361 236 : onion_queue_t *victim, *next;
362 236 : int i;
363 944 : for (i=0; i<=MAX_ONION_HANDSHAKE_TYPE; i++) {
364 709 : for (victim = TOR_TAILQ_FIRST(&ol_list[i]); victim; victim = next) {
365 1 : next = TOR_TAILQ_NEXT(victim,next);
366 1 : onion_queue_entry_remove(victim);
367 : }
368 708 : tor_assert(TOR_TAILQ_EMPTY(&ol_list[i]));
369 : }
370 236 : memset(ol_entries, 0, sizeof(ol_entries));
371 236 : }
|
