onion_queue.c (11770B)
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 #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 /** Type for a linked list of circuits that are waiting for a free CPU worker 54 * to process a waiting onion handshake. */ 55 typedef struct onion_queue_t { 56 TOR_TAILQ_ENTRY(onion_queue_t) next; 57 or_circuit_t *circ; 58 uint16_t queue_idx; 59 create_cell_t *onionskin; 60 time_t when_added; 61 } onion_queue_t; 62 63 TOR_TAILQ_HEAD(onion_queue_head_t, onion_queue_t); 64 typedef struct onion_queue_head_t onion_queue_head_t; 65 66 /** We have 3 queues: tap, fast, and ntor. (ntorv3 goes into ntor queue). */ 67 #define MAX_QUEUE_IDX ONION_HANDSHAKE_TYPE_NTOR 68 69 /** Array of queues of circuits waiting for CPU workers. An element is NULL 70 * if that queue is empty.*/ 71 static onion_queue_head_t ol_list[MAX_QUEUE_IDX+1] = 72 { TOR_TAILQ_HEAD_INITIALIZER(ol_list[0]), /* tap */ 73 TOR_TAILQ_HEAD_INITIALIZER(ol_list[1]), /* fast */ 74 TOR_TAILQ_HEAD_INITIALIZER(ol_list[2]), /* ntor */ 75 }; 76 77 /** Number of entries of each type currently in each element of ol_list[]. */ 78 static int ol_entries[MAX_QUEUE_IDX+1]; 79 80 static void onion_queue_entry_remove(onion_queue_t *victim); 81 82 /** Consensus parameters. */ 83 static time_t ns_onion_queue_wait_cutoff = ONION_QUEUE_WAIT_CUTOFF_DEFAULT; 84 static uint32_t ns_onion_queue_max_delay = ONION_QUEUE_MAX_DELAY_DEFAULT; 85 86 /** Return the onion queue wait cutoff value from the cached parameter. */ 87 static inline time_t 88 get_onion_queue_wait_cutoff(void) 89 { 90 return ns_onion_queue_wait_cutoff; 91 } 92 93 /** Return the max onion queue delay value either from the torrc options (if 94 * the user explicitly set it) else from the cached parameter. */ 95 static inline uint32_t 96 get_onion_queue_max_delay(const or_options_t *options) 97 { 98 if (options && options->MaxOnionQueueDelay > 0) { 99 return options->MaxOnionQueueDelay; 100 } 101 return ns_onion_queue_max_delay; 102 } 103 104 /** 105 * We combine ntorv3 and ntor into the same queue, so we must 106 * use this function to convert the cell type to a queue index. 107 */ 108 static inline uint16_t 109 onionskin_type_to_queue(uint16_t type) 110 { 111 if (type == ONION_HANDSHAKE_TYPE_NTOR_V3) { 112 return ONION_HANDSHAKE_TYPE_NTOR; 113 } 114 115 if (BUG(type > MAX_QUEUE_IDX)) { 116 return MAX_QUEUE_IDX; // use ntor if out of range 117 } 118 119 return type; 120 } 121 122 /* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN. 123 * 124 * (By which I think I meant, "make sure that no 125 * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than 126 * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN." Also, make sure that we can pass 127 * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/ 128 129 /** Return true iff we have room to queue another onionskin of type 130 * <b>type</b>. */ 131 static int 132 have_room_for_onionskin(uint16_t type) 133 { 134 const or_options_t *options = get_options(); 135 int num_cpus; 136 uint64_t max_onion_queue_delay; 137 uint64_t ntor_usec; 138 139 /* We never allow TAP. */ 140 if (type == ONION_HANDSHAKE_TYPE_TAP) { 141 return 0; 142 } 143 144 /* If we've got fewer than 50 entries, we always have room for one more. */ 145 if (ol_entries[type] < 50) 146 return 1; 147 148 /* If zero, this means our thread pool was never initialized meaning we can't 149 * really get here but make sure we don't have such value because we are 150 * using as a divisor. */ 151 num_cpus = cpuworker_get_n_threads(); 152 tor_assert(num_cpus > 0); 153 154 max_onion_queue_delay = get_onion_queue_max_delay(options); 155 156 /* Compute how many microseconds we'd expect to need to clear all 157 * onionskins in various combinations of the queues. */ 158 159 /* How long would it take to process all the NTor cells in the queue? */ 160 ntor_usec = estimated_usec_for_onionskins( 161 ol_entries[ONION_HANDSHAKE_TYPE_NTOR], 162 ONION_HANDSHAKE_TYPE_NTOR) / num_cpus; 163 164 /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue 165 * this. */ 166 if (type == ONION_HANDSHAKE_TYPE_NTOR && 167 (ntor_usec / 1000) > max_onion_queue_delay) 168 return 0; 169 170 return 1; 171 } 172 173 /** Add <b>circ</b> to the end of ol_list and return 0, except 174 * if ol_list is too long, in which case do nothing and return -1. 175 */ 176 int 177 onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) 178 { 179 onion_queue_t *tmp; 180 time_t now = time(NULL); 181 uint16_t queue_idx = 0; 182 183 if (onionskin->handshake_type > MAX_ONION_HANDSHAKE_TYPE) { 184 /* LCOV_EXCL_START 185 * We should have rejected this far before this point */ 186 log_warn(LD_BUG, "Handshake %d out of range! Dropping.", 187 onionskin->handshake_type); 188 return -1; 189 /* LCOV_EXCL_STOP */ 190 } 191 192 queue_idx = onionskin_type_to_queue(onionskin->handshake_type); 193 194 tmp = tor_malloc_zero(sizeof(onion_queue_t)); 195 tmp->circ = circ; 196 tmp->queue_idx = queue_idx; 197 tmp->onionskin = onionskin; 198 tmp->when_added = now; 199 200 if (!have_room_for_onionskin(queue_idx)) { 201 #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60) 202 static ratelim_t last_warned = 203 RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL); 204 if (!channel_is_client(circ->p_chan)) { 205 // Avoid counting create cells from clients, to go with the same 206 // check in command_process_create_cell(). 207 rep_hist_note_circuit_handshake_dropped(queue_idx); 208 } 209 if (queue_idx == ONION_HANDSHAKE_TYPE_NTOR) { 210 char *m; 211 if ((m = rate_limit_log(&last_warned, approx_time()))) { 212 log_warn(LD_GENERAL, 213 "Your computer is too slow to handle this many circuit " 214 "creation requests! Please consider using the " 215 "MaxAdvertisedBandwidth config option or choosing a more " 216 "restricted exit policy.%s", 217 m); 218 tor_free(m); 219 } 220 } 221 tor_free(tmp); 222 return -1; 223 } 224 225 ++ol_entries[queue_idx]; 226 log_info(LD_OR, "New create (%s). Queues now ntor=%d and tap=%d.", 227 queue_idx == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap", 228 ol_entries[ONION_HANDSHAKE_TYPE_NTOR], 229 ol_entries[ONION_HANDSHAKE_TYPE_TAP]); 230 231 circ->onionqueue_entry = tmp; 232 TOR_TAILQ_INSERT_TAIL(&ol_list[queue_idx], tmp, next); 233 234 /* cull elderly requests. */ 235 while (1) { 236 onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[queue_idx]); 237 if (now - head->when_added < get_onion_queue_wait_cutoff()) 238 break; 239 240 circ = head->circ; 241 circ->onionqueue_entry = NULL; 242 onion_queue_entry_remove(head); 243 log_info(LD_CIRC, 244 "Circuit create request is too old; canceling due to overload."); 245 if (! TO_CIRCUIT(circ)->marked_for_close) { 246 circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_RESOURCELIMIT); 247 } 248 } 249 return 0; 250 } 251 252 /** Choose which onion queue we'll pull from next. If one is empty choose 253 * the other; if they both have elements, load balance across them but 254 * favoring NTOR. */ 255 static uint16_t 256 decide_next_handshake_type(void) 257 { 258 return ONION_HANDSHAKE_TYPE_NTOR; 259 } 260 261 /** Remove the highest priority item from ol_list[] and return it, or 262 * return NULL if the lists are empty. 263 */ 264 or_circuit_t * 265 onion_next_task(create_cell_t **onionskin_out) 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->queue_idx <= MAX_QUEUE_IDX); 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->queue_idx]; 282 log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.", 283 head->queue_idx == 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; 290 onion_queue_entry_remove(head); 291 return circ; 292 } 293 294 /** Return the number of <b>handshake_type</b>-style create requests pending. 295 */ 296 int 297 onion_num_pending(uint16_t handshake_type) 298 { 299 return ol_entries[onionskin_type_to_queue(handshake_type)]; 300 } 301 302 /** Go through ol_list, find the onion_queue_t element which points to 303 * circ, remove and free that element. Leave circ itself alone. 304 */ 305 void 306 onion_pending_remove(or_circuit_t *circ) 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 317 cpuworker_cancel_circ_handshake(circ); 318 } 319 320 /** Remove a queue entry <b>victim</b> from the queue, unlinking it from 321 * its circuit and freeing it and any structures it owns.*/ 322 static void 323 onion_queue_entry_remove(onion_queue_t *victim) 324 { 325 if (victim->queue_idx > MAX_QUEUE_IDX) { 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->queue_idx); 330 /* XXX leaks */ 331 return; 332 /* LCOV_EXCL_STOP */ 333 } 334 335 TOR_TAILQ_REMOVE(&ol_list[victim->queue_idx], victim, next); 336 337 if (victim->circ) 338 victim->circ->onionqueue_entry = NULL; 339 340 if (victim->onionskin) 341 --ol_entries[victim->queue_idx]; 342 343 tor_free(victim->onionskin); 344 tor_free(victim); 345 } 346 347 /** Remove all circuits from the pending list. Called from tor_free_all. */ 348 void 349 clear_pending_onions(void) 350 { 351 onion_queue_t *victim, *next; 352 int i; 353 for (i=0; i<=MAX_QUEUE_IDX; 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 } 362 363 /** Consensus has changed, update the cached parameters. */ 364 void 365 onion_consensus_has_changed(const networkstatus_t *ns) 366 { 367 tor_assert(ns); 368 369 ns_onion_queue_max_delay = 370 networkstatus_get_param(ns, "MaxOnionQueueDelay", 371 ONION_QUEUE_MAX_DELAY_DEFAULT, 372 ONION_QUEUE_MAX_DELAY_MIN, 373 ONION_QUEUE_MAX_DELAY_MAX); 374 375 ns_onion_queue_wait_cutoff = 376 networkstatus_get_param(ns, "onion_queue_wait_cutoff", 377 ONION_QUEUE_WAIT_CUTOFF_DEFAULT, 378 ONION_QUEUE_WAIT_CUTOFF_MIN, 379 ONION_QUEUE_WAIT_CUTOFF_MAX); 380 }