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-2010, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief Handle relay cell encryption/decryption, plus packaging and
10 * receiving from circuits, plus queuing on circuits.
17 static int relay_crypt(circuit_t
*circ
, cell_t
*cell
,
18 cell_direction_t cell_direction
,
19 crypt_path_t
**layer_hint
, char *recognized
);
20 static edge_connection_t
*relay_lookup_conn(circuit_t
*circ
, cell_t
*cell
,
21 cell_direction_t cell_direction
,
22 crypt_path_t
*layer_hint
);
25 connection_edge_process_relay_cell(cell_t
*cell
, circuit_t
*circ
,
26 edge_connection_t
*conn
,
27 crypt_path_t
*layer_hint
);
29 circuit_consider_sending_sendme(circuit_t
*circ
, crypt_path_t
*layer_hint
);
31 circuit_resume_edge_reading(circuit_t
*circ
, crypt_path_t
*layer_hint
);
33 circuit_resume_edge_reading_helper(edge_connection_t
*conn
,
35 crypt_path_t
*layer_hint
);
37 circuit_consider_stop_edge_reading(circuit_t
*circ
, crypt_path_t
*layer_hint
);
39 /** Cache the current hi-res time; the cache gets reset when libevent
42 static struct timeval cached_time_hires
= {0, 0};
45 tor_gettimeofday_cached(struct timeval
*tv
)
47 if (cached_time_hires
.tv_sec
== 0) {
48 tor_gettimeofday(&cached_time_hires
);
50 *tv
= cached_time_hires
;
54 tor_gettimeofday_cache_clear(void)
56 cached_time_hires
.tv_sec
= 0;
59 /** Stats: how many relay cells have originated at this hop, or have
60 * been relayed onward (not recognized at this hop)?
62 uint64_t stats_n_relay_cells_relayed
= 0;
63 /** Stats: how many relay cells have been delivered to streams at this
66 uint64_t stats_n_relay_cells_delivered
= 0;
68 /** Update digest from the payload of cell. Assign integrity part to
72 relay_set_digest(crypto_digest_env_t
*digest
, cell_t
*cell
)
77 crypto_digest_add_bytes(digest
, cell
->payload
, CELL_PAYLOAD_SIZE
);
78 crypto_digest_get_digest(digest
, integrity
, 4);
79 // log_fn(LOG_DEBUG,"Putting digest of %u %u %u %u into relay cell.",
80 // integrity[0], integrity[1], integrity[2], integrity[3]);
81 relay_header_unpack(&rh
, cell
->payload
);
82 memcpy(rh
.integrity
, integrity
, 4);
83 relay_header_pack(cell
->payload
, &rh
);
86 /** Does the digest for this circuit indicate that this cell is for us?
88 * Update digest from the payload of cell (with the integrity part set
89 * to 0). If the integrity part is valid, return 1, else restore digest
90 * and cell to their original state and return 0.
93 relay_digest_matches(crypto_digest_env_t
*digest
, cell_t
*cell
)
95 char received_integrity
[4], calculated_integrity
[4];
97 crypto_digest_env_t
*backup_digest
=NULL
;
99 backup_digest
= crypto_digest_dup(digest
);
101 relay_header_unpack(&rh
, cell
->payload
);
102 memcpy(received_integrity
, rh
.integrity
, 4);
103 memset(rh
.integrity
, 0, 4);
104 relay_header_pack(cell
->payload
, &rh
);
106 // log_fn(LOG_DEBUG,"Reading digest of %u %u %u %u from relay cell.",
107 // received_integrity[0], received_integrity[1],
108 // received_integrity[2], received_integrity[3]);
110 crypto_digest_add_bytes(digest
, cell
->payload
, CELL_PAYLOAD_SIZE
);
111 crypto_digest_get_digest(digest
, calculated_integrity
, 4);
113 if (memcmp(received_integrity
, calculated_integrity
, 4)) {
114 // log_fn(LOG_INFO,"Recognized=0 but bad digest. Not recognizing.");
115 // (%d vs %d).", received_integrity, calculated_integrity);
116 /* restore digest to its old form */
117 crypto_digest_assign(digest
, backup_digest
);
118 /* restore the relay header */
119 memcpy(rh
.integrity
, received_integrity
, 4);
120 relay_header_pack(cell
->payload
, &rh
);
121 crypto_free_digest_env(backup_digest
);
124 crypto_free_digest_env(backup_digest
);
128 /** Apply <b>cipher</b> to CELL_PAYLOAD_SIZE bytes of <b>in</b>
131 * If <b>encrypt_mode</b> is 1 then encrypt, else decrypt.
133 * Return -1 if the crypto fails, else return 0.
136 relay_crypt_one_payload(crypto_cipher_env_t
*cipher
, char *in
,
141 r
= crypto_cipher_crypt_inplace(cipher
, in
, CELL_PAYLOAD_SIZE
);
144 log_warn(LD_BUG
,"Error during relay encryption");
150 /** Receive a relay cell:
151 * - Crypt it (encrypt if headed toward the origin or if we <b>are</b> the
152 * origin; decrypt if we're headed toward the exit).
153 * - Check if recognized (if exitward).
154 * - If recognized and the digest checks out, then find if there's a stream
155 * that the cell is intended for, and deliver it to the right
157 * - If not recognized, then we need to relay it: append it to the appropriate
158 * cell_queue on <b>circ</b>.
160 * Return -<b>reason</b> on failure.
163 circuit_receive_relay_cell(cell_t
*cell
, circuit_t
*circ
,
164 cell_direction_t cell_direction
)
166 or_connection_t
*or_conn
=NULL
;
167 crypt_path_t
*layer_hint
=NULL
;
173 tor_assert(cell_direction
== CELL_DIRECTION_OUT
||
174 cell_direction
== CELL_DIRECTION_IN
);
175 if (circ
->marked_for_close
)
178 if (relay_crypt(circ
, cell
, cell_direction
, &layer_hint
, &recognized
) < 0) {
179 log_warn(LD_BUG
,"relay crypt failed. Dropping connection.");
180 return -END_CIRC_REASON_INTERNAL
;
184 edge_connection_t
*conn
= relay_lookup_conn(circ
, cell
, cell_direction
,
186 if (cell_direction
== CELL_DIRECTION_OUT
) {
187 ++stats_n_relay_cells_delivered
;
188 log_debug(LD_OR
,"Sending away from origin.");
189 if ((reason
=connection_edge_process_relay_cell(cell
, circ
, conn
, NULL
))
191 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
192 "connection_edge_process_relay_cell (away from origin) "
197 if (cell_direction
== CELL_DIRECTION_IN
) {
198 ++stats_n_relay_cells_delivered
;
199 log_debug(LD_OR
,"Sending to origin.");
200 if ((reason
= connection_edge_process_relay_cell(cell
, circ
, conn
,
203 "connection_edge_process_relay_cell (at origin) failed.");
210 /* not recognized. pass it on. */
211 if (cell_direction
== CELL_DIRECTION_OUT
) {
212 cell
->circ_id
= circ
->n_circ_id
; /* switch it */
213 or_conn
= circ
->n_conn
;
214 } else if (! CIRCUIT_IS_ORIGIN(circ
)) {
215 cell
->circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
; /* switch it */
216 or_conn
= TO_OR_CIRCUIT(circ
)->p_conn
;
218 log_fn(LOG_PROTOCOL_WARN
, LD_OR
,
219 "Dropping unrecognized inbound cell on origin circuit.");
224 // XXXX Can this splice stuff be done more cleanly?
225 if (! CIRCUIT_IS_ORIGIN(circ
) &&
226 TO_OR_CIRCUIT(circ
)->rend_splice
&&
227 cell_direction
== CELL_DIRECTION_OUT
) {
228 or_circuit_t
*splice
= TO_OR_CIRCUIT(circ
)->rend_splice
;
229 tor_assert(circ
->purpose
== CIRCUIT_PURPOSE_REND_ESTABLISHED
);
230 tor_assert(splice
->_base
.purpose
== CIRCUIT_PURPOSE_REND_ESTABLISHED
);
231 cell
->circ_id
= splice
->p_circ_id
;
232 cell
->command
= CELL_RELAY
; /* can't be relay_early anyway */
233 if ((reason
= circuit_receive_relay_cell(cell
, TO_CIRCUIT(splice
),
234 CELL_DIRECTION_IN
)) < 0) {
235 log_warn(LD_REND
, "Error relaying cell across rendezvous; closing "
237 /* XXXX Do this here, or just return -1? */
238 circuit_mark_for_close(circ
, -reason
);
243 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
244 "Didn't recognize cell, but circ stops here! Closing circ.");
245 return -END_CIRC_REASON_TORPROTOCOL
;
248 log_debug(LD_OR
,"Passing on unrecognized cell.");
250 ++stats_n_relay_cells_relayed
; /* XXXX no longer quite accurate {cells}
251 * we might kill the circ before we relay
254 append_cell_to_circuit_queue(circ
, or_conn
, cell
, cell_direction
);
258 /** Do the appropriate en/decryptions for <b>cell</b> arriving on
259 * <b>circ</b> in direction <b>cell_direction</b>.
261 * If cell_direction == CELL_DIRECTION_IN:
262 * - If we're at the origin (we're the OP), for hops 1..N,
263 * decrypt cell. If recognized, stop.
264 * - Else (we're not the OP), encrypt one hop. Cell is not recognized.
266 * If cell_direction == CELL_DIRECTION_OUT:
267 * - decrypt one hop. Check if recognized.
269 * If cell is recognized, set *recognized to 1, and set
270 * *layer_hint to the hop that recognized it.
272 * Return -1 to indicate that we should mark the circuit for close,
276 relay_crypt(circuit_t
*circ
, cell_t
*cell
, cell_direction_t cell_direction
,
277 crypt_path_t
**layer_hint
, char *recognized
)
283 tor_assert(recognized
);
284 tor_assert(cell_direction
== CELL_DIRECTION_IN
||
285 cell_direction
== CELL_DIRECTION_OUT
);
287 if (cell_direction
== CELL_DIRECTION_IN
) {
288 if (CIRCUIT_IS_ORIGIN(circ
)) { /* We're at the beginning of the circuit.
289 * We'll want to do layered decrypts. */
290 crypt_path_t
*thishop
, *cpath
= TO_ORIGIN_CIRCUIT(circ
)->cpath
;
292 if (thishop
->state
!= CPATH_STATE_OPEN
) {
293 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
294 "Relay cell before first created cell? Closing.");
297 do { /* Remember: cpath is in forward order, that is, first hop first. */
300 if (relay_crypt_one_payload(thishop
->b_crypto
, cell
->payload
, 0) < 0)
303 relay_header_unpack(&rh
, cell
->payload
);
304 if (rh
.recognized
== 0) {
305 /* it's possibly recognized. have to check digest to be sure. */
306 if (relay_digest_matches(thishop
->b_digest
, cell
)) {
308 *layer_hint
= thishop
;
313 thishop
= thishop
->next
;
314 } while (thishop
!= cpath
&& thishop
->state
== CPATH_STATE_OPEN
);
315 log_fn(LOG_PROTOCOL_WARN
, LD_OR
,
316 "Incoming cell at client not recognized. Closing.");
318 } else { /* we're in the middle. Just one crypt. */
319 if (relay_crypt_one_payload(TO_OR_CIRCUIT(circ
)->p_crypto
,
320 cell
->payload
, 1) < 0)
322 // log_fn(LOG_DEBUG,"Skipping recognized check, because we're not "
325 } else /* cell_direction == CELL_DIRECTION_OUT */ {
326 /* we're in the middle. Just one crypt. */
328 if (relay_crypt_one_payload(TO_OR_CIRCUIT(circ
)->n_crypto
,
329 cell
->payload
, 0) < 0)
332 relay_header_unpack(&rh
, cell
->payload
);
333 if (rh
.recognized
== 0) {
334 /* it's possibly recognized. have to check digest to be sure. */
335 if (relay_digest_matches(TO_OR_CIRCUIT(circ
)->n_digest
, cell
)) {
344 /** Package a relay cell from an edge:
345 * - Encrypt it to the right layer
346 * - Append it to the appropriate cell_queue on <b>circ</b>.
349 circuit_package_relay_cell(cell_t
*cell
, circuit_t
*circ
,
350 cell_direction_t cell_direction
,
351 crypt_path_t
*layer_hint
)
353 or_connection_t
*conn
; /* where to send the cell */
355 if (cell_direction
== CELL_DIRECTION_OUT
) {
356 crypt_path_t
*thishop
; /* counter for repeated crypts */
358 if (!CIRCUIT_IS_ORIGIN(circ
) || !conn
) {
359 log_warn(LD_BUG
,"outgoing relay cell has n_conn==NULL. Dropping.");
360 return 0; /* just drop it */
363 relay_set_digest(layer_hint
->f_digest
, cell
);
365 thishop
= layer_hint
;
366 /* moving from farthest to nearest hop */
369 /* XXXX RD This is a bug, right? */
370 log_debug(LD_OR
,"crypting a layer of the relay cell.");
371 if (relay_crypt_one_payload(thishop
->f_crypto
, cell
->payload
, 1) < 0) {
375 thishop
= thishop
->prev
;
376 } while (thishop
!= TO_ORIGIN_CIRCUIT(circ
)->cpath
->prev
);
378 } else { /* incoming cell */
379 or_circuit_t
*or_circ
;
380 if (CIRCUIT_IS_ORIGIN(circ
)) {
381 /* We should never package an _incoming_ cell from the circuit
382 * origin; that means we messed up somewhere. */
383 log_warn(LD_BUG
,"incoming relay cell at origin circuit. Dropping.");
384 assert_circuit_ok(circ
);
385 return 0; /* just drop it */
387 or_circ
= TO_OR_CIRCUIT(circ
);
388 conn
= or_circ
->p_conn
;
389 relay_set_digest(or_circ
->p_digest
, cell
);
390 if (relay_crypt_one_payload(or_circ
->p_crypto
, cell
->payload
, 1) < 0)
393 ++stats_n_relay_cells_relayed
;
395 append_cell_to_circuit_queue(circ
, conn
, cell
, cell_direction
);
399 /** If cell's stream_id matches the stream_id of any conn that's
400 * attached to circ, return that conn, else return NULL.
402 static edge_connection_t
*
403 relay_lookup_conn(circuit_t
*circ
, cell_t
*cell
,
404 cell_direction_t cell_direction
, crypt_path_t
*layer_hint
)
406 edge_connection_t
*tmpconn
;
409 relay_header_unpack(&rh
, cell
->payload
);
414 /* IN or OUT cells could have come from either direction, now
415 * that we allow rendezvous *to* an OP.
418 if (CIRCUIT_IS_ORIGIN(circ
)) {
419 for (tmpconn
= TO_ORIGIN_CIRCUIT(circ
)->p_streams
; tmpconn
;
420 tmpconn
=tmpconn
->next_stream
) {
421 if (rh
.stream_id
== tmpconn
->stream_id
&&
422 !tmpconn
->_base
.marked_for_close
&&
423 tmpconn
->cpath_layer
== layer_hint
) {
424 log_debug(LD_APP
,"found conn for stream %d.", rh
.stream_id
);
429 for (tmpconn
= TO_OR_CIRCUIT(circ
)->n_streams
; tmpconn
;
430 tmpconn
=tmpconn
->next_stream
) {
431 if (rh
.stream_id
== tmpconn
->stream_id
&&
432 !tmpconn
->_base
.marked_for_close
) {
433 log_debug(LD_EXIT
,"found conn for stream %d.", rh
.stream_id
);
434 if (cell_direction
== CELL_DIRECTION_OUT
||
435 connection_edge_is_rendezvous_stream(tmpconn
))
439 for (tmpconn
= TO_OR_CIRCUIT(circ
)->resolving_streams
; tmpconn
;
440 tmpconn
=tmpconn
->next_stream
) {
441 if (rh
.stream_id
== tmpconn
->stream_id
&&
442 !tmpconn
->_base
.marked_for_close
) {
443 log_debug(LD_EXIT
,"found conn for stream %d.", rh
.stream_id
);
448 return NULL
; /* probably a begin relay cell */
451 /** Pack the relay_header_t host-order structure <b>src</b> into
452 * network-order in the buffer <b>dest</b>. See tor-spec.txt for details
453 * about the wire format.
456 relay_header_pack(char *dest
, const relay_header_t
*src
)
458 *(uint8_t*)(dest
) = src
->command
;
460 set_uint16(dest
+1, htons(src
->recognized
));
461 set_uint16(dest
+3, htons(src
->stream_id
));
462 memcpy(dest
+5, src
->integrity
, 4);
463 set_uint16(dest
+9, htons(src
->length
));
466 /** Unpack the network-order buffer <b>src</b> into a host-order
467 * relay_header_t structure <b>dest</b>.
470 relay_header_unpack(relay_header_t
*dest
, const char *src
)
472 dest
->command
= *(uint8_t*)(src
);
474 dest
->recognized
= ntohs(get_uint16(src
+1));
475 dest
->stream_id
= ntohs(get_uint16(src
+3));
476 memcpy(dest
->integrity
, src
+5, 4);
477 dest
->length
= ntohs(get_uint16(src
+9));
480 /** Convert the relay <b>command</b> into a human-readable string. */
482 relay_command_to_string(uint8_t command
)
485 case RELAY_COMMAND_BEGIN
: return "BEGIN";
486 case RELAY_COMMAND_DATA
: return "DATA";
487 case RELAY_COMMAND_END
: return "END";
488 case RELAY_COMMAND_CONNECTED
: return "CONNECTED";
489 case RELAY_COMMAND_SENDME
: return "SENDME";
490 case RELAY_COMMAND_EXTEND
: return "EXTEND";
491 case RELAY_COMMAND_EXTENDED
: return "EXTENDED";
492 case RELAY_COMMAND_TRUNCATE
: return "TRUNCATE";
493 case RELAY_COMMAND_TRUNCATED
: return "TRUNCATED";
494 case RELAY_COMMAND_DROP
: return "DROP";
495 case RELAY_COMMAND_RESOLVE
: return "RESOLVE";
496 case RELAY_COMMAND_RESOLVED
: return "RESOLVED";
497 case RELAY_COMMAND_BEGIN_DIR
: return "BEGIN_DIR";
498 case RELAY_COMMAND_ESTABLISH_INTRO
: return "ESTABLISH_INTRO";
499 case RELAY_COMMAND_ESTABLISH_RENDEZVOUS
: return "ESTABLISH_RENDEZVOUS";
500 case RELAY_COMMAND_INTRODUCE1
: return "INTRODUCE1";
501 case RELAY_COMMAND_INTRODUCE2
: return "INTRODUCE2";
502 case RELAY_COMMAND_RENDEZVOUS1
: return "RENDEZVOUS1";
503 case RELAY_COMMAND_RENDEZVOUS2
: return "RENDEZVOUS2";
504 case RELAY_COMMAND_INTRO_ESTABLISHED
: return "INTRO_ESTABLISHED";
505 case RELAY_COMMAND_RENDEZVOUS_ESTABLISHED
:
506 return "RENDEZVOUS_ESTABLISHED";
507 case RELAY_COMMAND_INTRODUCE_ACK
: return "INTRODUCE_ACK";
508 default: return "(unrecognized)";
512 /** Make a relay cell out of <b>relay_command</b> and <b>payload</b>, and send
513 * it onto the open circuit <b>circ</b>. <b>stream_id</b> is the ID on
514 * <b>circ</b> for the stream that's sending the relay cell, or 0 if it's a
515 * control cell. <b>cpath_layer</b> is NULL for OR->OP cells, or the
516 * destination hop for OP->OR cells.
518 * If you can't send the cell, mark the circuit for close and return -1. Else
522 relay_send_command_from_edge(uint16_t stream_id
, circuit_t
*circ
,
523 uint8_t relay_command
, const char *payload
,
524 size_t payload_len
, crypt_path_t
*cpath_layer
)
528 cell_direction_t cell_direction
;
529 /* XXXX NM Split this function into a separate versions per circuit type? */
532 tor_assert(payload_len
<= RELAY_PAYLOAD_SIZE
);
534 memset(&cell
, 0, sizeof(cell_t
));
535 cell
.command
= CELL_RELAY
;
537 cell
.circ_id
= circ
->n_circ_id
;
538 cell_direction
= CELL_DIRECTION_OUT
;
539 } else if (! CIRCUIT_IS_ORIGIN(circ
)) {
540 cell
.circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
541 cell_direction
= CELL_DIRECTION_IN
;
546 memset(&rh
, 0, sizeof(rh
));
547 rh
.command
= relay_command
;
548 rh
.stream_id
= stream_id
;
549 rh
.length
= payload_len
;
550 relay_header_pack(cell
.payload
, &rh
);
552 memcpy(cell
.payload
+RELAY_HEADER_SIZE
, payload
, payload_len
);
554 log_debug(LD_OR
,"delivering %d cell %s.", relay_command
,
555 cell_direction
== CELL_DIRECTION_OUT
? "forward" : "backward");
557 /* If we are sending an END cell and this circuit is used for a tunneled
558 * directory request, advance its state. */
559 if (relay_command
== RELAY_COMMAND_END
&& circ
->dirreq_id
)
560 geoip_change_dirreq_state(circ
->dirreq_id
, DIRREQ_TUNNELED
,
561 DIRREQ_END_CELL_SENT
);
563 if (cell_direction
== CELL_DIRECTION_OUT
&& circ
->n_conn
) {
564 /* if we're using relaybandwidthrate, this conn wants priority */
565 circ
->n_conn
->client_used
= approx_time();
568 if (cell_direction
== CELL_DIRECTION_OUT
) {
569 origin_circuit_t
*origin_circ
= TO_ORIGIN_CIRCUIT(circ
);
570 if (origin_circ
->remaining_relay_early_cells
> 0 &&
571 (relay_command
== RELAY_COMMAND_EXTEND
||
572 (cpath_layer
!= origin_circ
->cpath
&&
573 !CIRCUIT_PURPOSE_IS_ESTABLISHED_REND(circ
->purpose
)))) {
574 /* If we've got any relay_early cells left, and we're sending
575 * an extend cell or (we're not talking to the first hop and we're
576 * not talking to a rendezvous circuit), use one of them.
577 * Don't worry about the conn protocol version:
578 * append_cell_to_circuit_queue will fix it up. */
579 /* XXX For now, clients don't use RELAY_EARLY cells when sending
580 * relay cells on rendezvous circuits. See bug 1038. Once no relays
581 * (and thus no rendezvous points) are running 0.2.1.3-alpha through
582 * 0.2.1.18, we can take out that exception. -RD */
583 cell
.command
= CELL_RELAY_EARLY
;
584 --origin_circ
->remaining_relay_early_cells
;
585 log_debug(LD_OR
, "Sending a RELAY_EARLY cell; %d remaining.",
586 (int)origin_circ
->remaining_relay_early_cells
);
587 /* Memorize the command that is sent as RELAY_EARLY cell; helps debug
589 origin_circ
->relay_early_commands
[
590 origin_circ
->relay_early_cells_sent
++] = relay_command
;
591 } else if (relay_command
== RELAY_COMMAND_EXTEND
) {
592 /* If no RELAY_EARLY cells can be sent over this circuit, log which
593 * commands have been sent as RELAY_EARLY cells before; helps debug
595 smartlist_t
*commands_list
= smartlist_create();
597 char *commands
= NULL
;
598 for (; i
< origin_circ
->relay_early_cells_sent
; i
++)
599 smartlist_add(commands_list
, (char *)
600 relay_command_to_string(origin_circ
->relay_early_commands
[i
]));
601 commands
= smartlist_join_strings(commands_list
, ",", 0, NULL
);
602 log_warn(LD_BUG
, "Uh-oh. We're sending a RELAY_COMMAND_EXTEND cell, "
603 "but we have run out of RELAY_EARLY cells on that circuit. "
604 "Commands sent before: %s", commands
);
606 smartlist_free(commands_list
);
610 if (circuit_package_relay_cell(&cell
, circ
, cell_direction
, cpath_layer
)
612 log_warn(LD_BUG
,"circuit_package_relay_cell failed. Closing.");
613 circuit_mark_for_close(circ
, END_CIRC_REASON_INTERNAL
);
619 /** Make a relay cell out of <b>relay_command</b> and <b>payload</b>, and
620 * send it onto the open circuit <b>circ</b>. <b>fromconn</b> is the stream
621 * that's sending the relay cell, or NULL if it's a control cell.
622 * <b>cpath_layer</b> is NULL for OR->OP cells, or the destination hop
625 * If you can't send the cell, mark the circuit for close and
626 * return -1. Else return 0.
629 connection_edge_send_command(edge_connection_t
*fromconn
,
630 uint8_t relay_command
, const char *payload
,
633 /* XXXX NM Split this function into a separate versions per circuit type? */
635 tor_assert(fromconn
);
636 circ
= fromconn
->on_circuit
;
638 if (fromconn
->_base
.marked_for_close
) {
640 "called on conn that's already marked for close at %s:%d.",
641 fromconn
->_base
.marked_for_close_file
,
642 fromconn
->_base
.marked_for_close
);
647 if (fromconn
->_base
.type
== CONN_TYPE_AP
) {
648 log_info(LD_APP
,"no circ. Closing conn.");
649 connection_mark_unattached_ap(fromconn
, END_STREAM_REASON_INTERNAL
);
651 log_info(LD_EXIT
,"no circ. Closing conn.");
652 fromconn
->edge_has_sent_end
= 1; /* no circ to send to */
653 fromconn
->end_reason
= END_STREAM_REASON_INTERNAL
;
654 connection_mark_for_close(TO_CONN(fromconn
));
659 return relay_send_command_from_edge(fromconn
->stream_id
, circ
,
660 relay_command
, payload
,
661 payload_len
, fromconn
->cpath_layer
);
664 /** How many times will I retry a stream that fails due to DNS
665 * resolve failure or misc error?
667 #define MAX_RESOLVE_FAILURES 3
669 /** Return 1 if reason is something that you should retry if you
670 * get the end cell before you've connected; else return 0. */
672 edge_reason_is_retriable(int reason
)
674 return reason
== END_STREAM_REASON_HIBERNATING
||
675 reason
== END_STREAM_REASON_RESOURCELIMIT
||
676 reason
== END_STREAM_REASON_EXITPOLICY
||
677 reason
== END_STREAM_REASON_RESOLVEFAILED
||
678 reason
== END_STREAM_REASON_MISC
;
681 /** Called when we receive an END cell on a stream that isn't open yet,
682 * from the client side.
683 * Arguments are as for connection_edge_process_relay_cell().
686 connection_ap_process_end_not_open(
687 relay_header_t
*rh
, cell_t
*cell
, origin_circuit_t
*circ
,
688 edge_connection_t
*conn
, crypt_path_t
*layer_hint
)
691 routerinfo_t
*exitrouter
;
692 int reason
= *(cell
->payload
+RELAY_HEADER_SIZE
);
693 int control_reason
= reason
| END_STREAM_REASON_FLAG_REMOTE
;
694 (void) layer_hint
; /* unused */
696 if (rh
->length
> 0 && edge_reason_is_retriable(reason
) &&
697 !connection_edge_is_rendezvous_stream(conn
) /* avoid retry if rend */
699 log_info(LD_APP
,"Address '%s' refused due to '%s'. Considering retrying.",
700 safe_str(conn
->socks_request
->address
),
701 stream_end_reason_to_string(reason
));
703 router_get_by_digest(circ
->build_state
->chosen_exit
->identity_digest
);
705 case END_STREAM_REASON_EXITPOLICY
:
706 if (rh
->length
>= 5) {
707 uint32_t addr
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
+1));
710 log_info(LD_APP
,"Address '%s' resolved to 0.0.0.0. Closing,",
711 safe_str(conn
->socks_request
->address
));
712 connection_mark_unattached_ap(conn
, END_STREAM_REASON_TORPROTOCOL
);
716 ttl
= (int)ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
+5));
720 if (get_options()->ClientDNSRejectInternalAddresses
&&
721 is_internal_IP(addr
, 0)) {
722 log_info(LD_APP
,"Address '%s' resolved to internal. Closing,",
723 safe_str(conn
->socks_request
->address
));
724 connection_mark_unattached_ap(conn
, END_STREAM_REASON_TORPROTOCOL
);
727 client_dns_set_addressmap(conn
->socks_request
->address
, addr
,
728 conn
->chosen_exit_name
, ttl
);
730 /* check if he *ought* to have allowed it */
733 (tor_inet_aton(conn
->socks_request
->address
, &in
) &&
734 !conn
->chosen_exit_name
))) {
736 "Exitrouter '%s' seems to be more restrictive than its exit "
737 "policy. Not using this router as exit for now.",
738 exitrouter
->nickname
);
739 policies_set_router_exitpolicy_to_reject_all(exitrouter
);
741 /* rewrite it to an IP if we learned one. */
742 if (addressmap_rewrite(conn
->socks_request
->address
,
743 sizeof(conn
->socks_request
->address
),
745 control_event_stream_status(conn
, STREAM_EVENT_REMAP
, 0);
747 if (conn
->chosen_exit_optional
||
748 conn
->chosen_exit_retries
) {
749 /* stop wanting a specific exit */
750 conn
->chosen_exit_optional
= 0;
751 /* A non-zero chosen_exit_retries can happen if we set a
752 * TrackHostExits for this address under a port that the exit
753 * relay allows, but then try the same address with a different
754 * port that it doesn't allow to exit. We shouldn't unregister
755 * the mapping, since it is probably still wanted on the
756 * original port. But now we give away to the exit relay that
757 * we probably have a TrackHostExits on it. So be it. */
758 conn
->chosen_exit_retries
= 0;
759 tor_free(conn
->chosen_exit_name
); /* clears it */
761 if (connection_ap_detach_retriable(conn
, circ
, control_reason
) >= 0)
763 /* else, conn will get closed below */
765 case END_STREAM_REASON_CONNECTREFUSED
:
766 if (!conn
->chosen_exit_optional
)
767 break; /* break means it'll close, below */
768 /* Else fall through: expire this circuit, clear the
769 * chosen_exit_name field, and try again. */
770 case END_STREAM_REASON_RESOLVEFAILED
:
771 case END_STREAM_REASON_TIMEOUT
:
772 case END_STREAM_REASON_MISC
:
773 if (client_dns_incr_failures(conn
->socks_request
->address
)
774 < MAX_RESOLVE_FAILURES
) {
775 /* We haven't retried too many times; reattach the connection. */
776 circuit_log_path(LOG_INFO
,LD_APP
,circ
);
777 tor_assert(circ
->_base
.timestamp_dirty
);
778 circ
->_base
.timestamp_dirty
-= get_options()->MaxCircuitDirtiness
;
780 if (conn
->chosen_exit_optional
) {
781 /* stop wanting a specific exit */
782 conn
->chosen_exit_optional
= 0;
783 tor_free(conn
->chosen_exit_name
); /* clears it */
785 if (connection_ap_detach_retriable(conn
, circ
, control_reason
) >= 0)
787 /* else, conn will get closed below */
790 "Have tried resolving or connecting to address '%s' "
791 "at %d different places. Giving up.",
792 safe_str(conn
->socks_request
->address
),
793 MAX_RESOLVE_FAILURES
);
794 /* clear the failures, so it will have a full try next time */
795 client_dns_clear_failures(conn
->socks_request
->address
);
798 case END_STREAM_REASON_HIBERNATING
:
799 case END_STREAM_REASON_RESOURCELIMIT
:
801 policies_set_router_exitpolicy_to_reject_all(exitrouter
);
803 if (conn
->chosen_exit_optional
) {
804 /* stop wanting a specific exit */
805 conn
->chosen_exit_optional
= 0;
806 tor_free(conn
->chosen_exit_name
); /* clears it */
808 if (connection_ap_detach_retriable(conn
, circ
, control_reason
) >= 0)
810 /* else, will close below */
813 log_info(LD_APP
,"Giving up on retrying; conn can't be handled.");
817 "Edge got end (%s) before we're connected. Marking for close.",
818 stream_end_reason_to_string(rh
->length
> 0 ? reason
: -1));
819 circuit_log_path(LOG_INFO
,LD_APP
,circ
);
820 /* need to test because of detach_retriable */
821 if (!conn
->_base
.marked_for_close
)
822 connection_mark_unattached_ap(conn
, control_reason
);
826 /** Helper: change the socks_request->address field on conn to the
827 * dotted-quad representation of <b>new_addr</b> (given in host order),
828 * and send an appropriate REMAP event. */
830 remap_event_helper(edge_connection_t
*conn
, uint32_t new_addr
)
834 in
.s_addr
= htonl(new_addr
);
835 tor_inet_ntoa(&in
, conn
->socks_request
->address
,
836 sizeof(conn
->socks_request
->address
));
837 control_event_stream_status(conn
, STREAM_EVENT_REMAP
,
838 REMAP_STREAM_SOURCE_EXIT
);
841 /** An incoming relay cell has arrived from circuit <b>circ</b> to
842 * stream <b>conn</b>.
844 * The arguments here are the same as in
845 * connection_edge_process_relay_cell() below; this function is called
846 * from there when <b>conn</b> is defined and not in an open state.
849 connection_edge_process_relay_cell_not_open(
850 relay_header_t
*rh
, cell_t
*cell
, circuit_t
*circ
,
851 edge_connection_t
*conn
, crypt_path_t
*layer_hint
)
853 if (rh
->command
== RELAY_COMMAND_END
) {
854 if (CIRCUIT_IS_ORIGIN(circ
) && conn
->_base
.type
== CONN_TYPE_AP
) {
855 return connection_ap_process_end_not_open(rh
, cell
,
856 TO_ORIGIN_CIRCUIT(circ
), conn
,
859 /* we just got an 'end', don't need to send one */
860 conn
->edge_has_sent_end
= 1;
861 conn
->end_reason
= *(cell
->payload
+RELAY_HEADER_SIZE
) |
862 END_STREAM_REASON_FLAG_REMOTE
;
863 connection_mark_for_close(TO_CONN(conn
));
868 if (conn
->_base
.type
== CONN_TYPE_AP
&&
869 rh
->command
== RELAY_COMMAND_CONNECTED
) {
870 tor_assert(CIRCUIT_IS_ORIGIN(circ
));
871 if (conn
->_base
.state
!= AP_CONN_STATE_CONNECT_WAIT
) {
872 log_fn(LOG_PROTOCOL_WARN
, LD_APP
,
873 "Got 'connected' while not in state connect_wait. Dropping.");
876 conn
->_base
.state
= AP_CONN_STATE_OPEN
;
877 log_info(LD_APP
,"'connected' received after %d seconds.",
878 (int)(time(NULL
) - conn
->_base
.timestamp_lastread
));
879 if (rh
->length
>= 4) {
880 uint32_t addr
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
882 if (!addr
|| (get_options()->ClientDNSRejectInternalAddresses
&&
883 is_internal_IP(addr
, 0))) {
884 char buf
[INET_NTOA_BUF_LEN
];
886 a
.s_addr
= htonl(addr
);
887 tor_inet_ntoa(&a
, buf
, sizeof(buf
));
889 "...but it claims the IP address was %s. Closing.", buf
);
890 connection_edge_end(conn
, END_STREAM_REASON_TORPROTOCOL
);
891 connection_mark_unattached_ap(conn
, END_STREAM_REASON_TORPROTOCOL
);
895 ttl
= (int)ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
+4));
898 client_dns_set_addressmap(conn
->socks_request
->address
, addr
,
899 conn
->chosen_exit_name
, ttl
);
901 remap_event_helper(conn
, addr
);
903 circuit_log_path(LOG_INFO
,LD_APP
,TO_ORIGIN_CIRCUIT(circ
));
904 /* don't send a socks reply to transparent conns */
905 if (!conn
->socks_request
->has_finished
)
906 connection_ap_handshake_socks_reply(conn
, NULL
, 0, 0);
908 /* Was it a linked dir conn? If so, a dir request just started to
909 * fetch something; this could be a bootstrap status milestone. */
910 log_debug(LD_APP
, "considering");
911 if (TO_CONN(conn
)->linked_conn
&&
912 TO_CONN(conn
)->linked_conn
->type
== CONN_TYPE_DIR
) {
913 connection_t
*dirconn
= TO_CONN(conn
)->linked_conn
;
914 log_debug(LD_APP
, "it is! %d", dirconn
->purpose
);
915 switch (dirconn
->purpose
) {
916 case DIR_PURPOSE_FETCH_CERTIFICATE
:
917 if (consensus_is_waiting_for_certs())
918 control_event_bootstrap(BOOTSTRAP_STATUS_LOADING_KEYS
, 0);
920 case DIR_PURPOSE_FETCH_CONSENSUS
:
921 control_event_bootstrap(BOOTSTRAP_STATUS_LOADING_STATUS
, 0);
923 case DIR_PURPOSE_FETCH_SERVERDESC
:
924 control_event_bootstrap(BOOTSTRAP_STATUS_LOADING_DESCRIPTORS
,
925 count_loading_descriptors_progress());
930 /* handle anything that might have queued */
931 if (connection_edge_package_raw_inbuf(conn
, 1) < 0) {
932 /* (We already sent an end cell if possible) */
933 connection_mark_for_close(TO_CONN(conn
));
938 if (conn
->_base
.type
== CONN_TYPE_AP
&&
939 rh
->command
== RELAY_COMMAND_RESOLVED
) {
943 if (conn
->_base
.state
!= AP_CONN_STATE_RESOLVE_WAIT
) {
944 log_fn(LOG_PROTOCOL_WARN
, LD_APP
, "Got a 'resolved' cell while "
945 "not in state resolve_wait. Dropping.");
948 tor_assert(SOCKS_COMMAND_IS_RESOLVE(conn
->socks_request
->command
));
949 answer_len
= cell
->payload
[RELAY_HEADER_SIZE
+1];
950 if (rh
->length
< 2 || answer_len
+2>rh
->length
) {
951 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
952 "Dropping malformed 'resolved' cell");
953 connection_mark_unattached_ap(conn
, END_STREAM_REASON_TORPROTOCOL
);
956 answer_type
= cell
->payload
[RELAY_HEADER_SIZE
];
957 if (rh
->length
>= answer_len
+6)
958 ttl
= (int)ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
+
962 if (answer_type
== RESOLVED_TYPE_IPV4
&& answer_len
== 4) {
963 uint32_t addr
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
+2));
964 if (get_options()->ClientDNSRejectInternalAddresses
&&
965 is_internal_IP(addr
, 0)) {
966 char buf
[INET_NTOA_BUF_LEN
];
968 a
.s_addr
= htonl(addr
);
969 tor_inet_ntoa(&a
, buf
, sizeof(buf
));
970 log_info(LD_APP
,"Got a resolve with answer %s. Rejecting.", buf
);
971 connection_ap_handshake_socks_resolved(conn
,
972 RESOLVED_TYPE_ERROR_TRANSIENT
,
973 0, NULL
, 0, TIME_MAX
);
974 connection_mark_unattached_ap(conn
, END_STREAM_REASON_TORPROTOCOL
);
978 connection_ap_handshake_socks_resolved(conn
,
980 cell
->payload
[RELAY_HEADER_SIZE
+1], /*answer_len*/
981 cell
->payload
+RELAY_HEADER_SIZE
+2, /*answer*/
984 if (answer_type
== RESOLVED_TYPE_IPV4
&& answer_len
== 4) {
985 uint32_t addr
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
+2));
986 remap_event_helper(conn
, addr
);
988 connection_mark_unattached_ap(conn
,
989 END_STREAM_REASON_DONE
|
990 END_STREAM_REASON_FLAG_ALREADY_SOCKS_REPLIED
);
994 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
995 "Got an unexpected relay command %d, in state %d (%s). Dropping.",
996 rh
->command
, conn
->_base
.state
,
997 conn_state_to_string(conn
->_base
.type
, conn
->_base
.state
));
998 return 0; /* for forward compatibility, don't kill the circuit */
999 // connection_edge_end(conn, END_STREAM_REASON_TORPROTOCOL);
1000 // connection_mark_for_close(conn);
1004 /** An incoming relay cell has arrived on circuit <b>circ</b>. If
1005 * <b>conn</b> is NULL this is a control cell, else <b>cell</b> is
1006 * destined for <b>conn</b>.
1008 * If <b>layer_hint</b> is defined, then we're the origin of the
1009 * circuit, and it specifies the hop that packaged <b>cell</b>.
1011 * Return -reason if you want to warn and tear down the circuit, else 0.
1014 connection_edge_process_relay_cell(cell_t
*cell
, circuit_t
*circ
,
1015 edge_connection_t
*conn
,
1016 crypt_path_t
*layer_hint
)
1018 static int num_seen
=0;
1020 unsigned domain
= layer_hint
?LD_APP
:LD_EXIT
;
1026 relay_header_unpack(&rh
, cell
->payload
);
1027 // log_fn(LOG_DEBUG,"command %d stream %d", rh.command, rh.stream_id);
1029 log_debug(domain
, "Now seen %d relay cells here (command %d, stream %d).",
1030 num_seen
, rh
.command
, rh
.stream_id
);
1032 if (rh
.length
> RELAY_PAYLOAD_SIZE
) {
1033 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
1034 "Relay cell length field too long. Closing circuit.");
1035 return - END_CIRC_REASON_TORPROTOCOL
;
1038 /* either conn is NULL, in which case we've got a control cell, or else
1039 * conn points to the recognized stream. */
1041 if (conn
&& !connection_state_is_open(TO_CONN(conn
)))
1042 return connection_edge_process_relay_cell_not_open(
1043 &rh
, cell
, circ
, conn
, layer_hint
);
1045 switch (rh
.command
) {
1046 case RELAY_COMMAND_DROP
:
1047 // log_info(domain,"Got a relay-level padding cell. Dropping.");
1049 case RELAY_COMMAND_BEGIN
:
1050 case RELAY_COMMAND_BEGIN_DIR
:
1052 circ
->purpose
!= CIRCUIT_PURPOSE_S_REND_JOINED
) {
1053 log_fn(LOG_PROTOCOL_WARN
, LD_APP
,
1054 "Relay begin request unsupported at AP. Dropping.");
1057 if (circ
->purpose
== CIRCUIT_PURPOSE_S_REND_JOINED
&&
1058 layer_hint
!= TO_ORIGIN_CIRCUIT(circ
)->cpath
->prev
) {
1059 log_fn(LOG_PROTOCOL_WARN
, LD_APP
,
1060 "Relay begin request to Hidden Service "
1061 "from intermediary node. Dropping.");
1065 log_fn(LOG_PROTOCOL_WARN
, domain
,
1066 "Begin cell for known stream. Dropping.");
1069 if (rh
.command
== RELAY_COMMAND_BEGIN_DIR
) {
1070 /* Assign this circuit and its app-ward OR connection a unique ID,
1071 * so that we can measure download times. The local edge and dir
1072 * connection will be assigned the same ID when they are created
1074 static uint64_t next_id
= 0;
1075 circ
->dirreq_id
= ++next_id
;
1076 TO_CONN(TO_OR_CIRCUIT(circ
)->p_conn
)->dirreq_id
= circ
->dirreq_id
;
1079 return connection_exit_begin_conn(cell
, circ
);
1080 case RELAY_COMMAND_DATA
:
1081 ++stats_n_data_cells_received
;
1082 if (( layer_hint
&& --layer_hint
->deliver_window
< 0) ||
1083 (!layer_hint
&& --circ
->deliver_window
< 0)) {
1084 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
1085 "(relay data) circ deliver_window below 0. Killing.");
1086 connection_edge_end(conn
, END_STREAM_REASON_TORPROTOCOL
);
1087 connection_mark_for_close(TO_CONN(conn
));
1088 return -END_CIRC_REASON_TORPROTOCOL
;
1090 log_debug(domain
,"circ deliver_window now %d.", layer_hint
?
1091 layer_hint
->deliver_window
: circ
->deliver_window
);
1093 circuit_consider_sending_sendme(circ
, layer_hint
);
1096 log_info(domain
,"data cell dropped, unknown stream (streamid %d).",
1101 if (--conn
->deliver_window
< 0) { /* is it below 0 after decrement? */
1102 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
1103 "(relay data) conn deliver_window below 0. Killing.");
1104 return -END_CIRC_REASON_TORPROTOCOL
;
1107 stats_n_data_bytes_received
+= rh
.length
;
1108 connection_write_to_buf(cell
->payload
+ RELAY_HEADER_SIZE
,
1109 rh
.length
, TO_CONN(conn
));
1110 connection_edge_consider_sending_sendme(conn
);
1112 case RELAY_COMMAND_END
:
1113 reason
= rh
.length
> 0 ?
1114 *(uint8_t *)(cell
->payload
+RELAY_HEADER_SIZE
) : END_STREAM_REASON_MISC
;
1116 log_info(domain
,"end cell (%s) dropped, unknown stream.",
1117 stream_end_reason_to_string(reason
));
1120 /* XXX add to this log_fn the exit node's nickname? */
1121 log_info(domain
,"%d: end cell (%s) for stream %d. Removing stream.",
1123 stream_end_reason_to_string(reason
),
1125 if (conn
->socks_request
&& !conn
->socks_request
->has_finished
)
1127 "open stream hasn't sent socks answer yet? Closing.");
1128 /* We just *got* an end; no reason to send one. */
1129 conn
->edge_has_sent_end
= 1;
1130 if (!conn
->end_reason
)
1131 conn
->end_reason
= reason
| END_STREAM_REASON_FLAG_REMOTE
;
1132 if (!conn
->_base
.marked_for_close
) {
1133 /* only mark it if not already marked. it's possible to
1134 * get the 'end' right around when the client hangs up on us. */
1135 connection_mark_for_close(TO_CONN(conn
));
1136 conn
->_base
.hold_open_until_flushed
= 1;
1139 case RELAY_COMMAND_EXTEND
:
1141 log_fn(LOG_PROTOCOL_WARN
, domain
,
1142 "'extend' cell received for non-zero stream. Dropping.");
1145 return circuit_extend(cell
, circ
);
1146 case RELAY_COMMAND_EXTENDED
:
1148 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
1149 "'extended' unsupported at non-origin. Dropping.");
1152 log_debug(domain
,"Got an extended cell! Yay.");
1153 if ((reason
= circuit_finish_handshake(TO_ORIGIN_CIRCUIT(circ
),
1155 cell
->payload
+RELAY_HEADER_SIZE
)) < 0) {
1156 log_warn(domain
,"circuit_finish_handshake failed.");
1159 if ((reason
=circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ
)))<0) {
1160 log_info(domain
,"circuit_send_next_onion_skin() failed.");
1164 case RELAY_COMMAND_TRUNCATE
:
1166 log_fn(LOG_PROTOCOL_WARN
, LD_APP
,
1167 "'truncate' unsupported at origin. Dropping.");
1171 uint8_t trunc_reason
= *(uint8_t*)(cell
->payload
+ RELAY_HEADER_SIZE
);
1172 connection_or_send_destroy(circ
->n_circ_id
, circ
->n_conn
,
1174 circuit_set_n_circid_orconn(circ
, 0, NULL
);
1176 log_debug(LD_EXIT
, "Processed 'truncate', replying.");
1179 payload
[0] = (char)END_CIRC_REASON_REQUESTED
;
1180 relay_send_command_from_edge(0, circ
, RELAY_COMMAND_TRUNCATED
,
1181 payload
, sizeof(payload
), NULL
);
1184 case RELAY_COMMAND_TRUNCATED
:
1186 log_fn(LOG_PROTOCOL_WARN
, LD_EXIT
,
1187 "'truncated' unsupported at non-origin. Dropping.");
1190 circuit_truncated(TO_ORIGIN_CIRCUIT(circ
), layer_hint
);
1192 case RELAY_COMMAND_CONNECTED
:
1194 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
1195 "'connected' unsupported while open. Closing circ.");
1196 return -END_CIRC_REASON_TORPROTOCOL
;
1199 "'connected' received, no conn attached anymore. Ignoring.");
1201 case RELAY_COMMAND_SENDME
:
1204 layer_hint
->package_window
+= CIRCWINDOW_INCREMENT
;
1205 log_debug(LD_APP
,"circ-level sendme at origin, packagewindow %d.",
1206 layer_hint
->package_window
);
1207 circuit_resume_edge_reading(circ
, layer_hint
);
1209 circ
->package_window
+= CIRCWINDOW_INCREMENT
;
1211 "circ-level sendme at non-origin, packagewindow %d.",
1212 circ
->package_window
);
1213 circuit_resume_edge_reading(circ
, layer_hint
);
1217 conn
->package_window
+= STREAMWINDOW_INCREMENT
;
1218 log_debug(domain
,"stream-level sendme, packagewindow now %d.",
1219 conn
->package_window
);
1220 connection_start_reading(TO_CONN(conn
));
1221 /* handle whatever might still be on the inbuf */
1222 if (connection_edge_package_raw_inbuf(conn
, 1) < 0) {
1223 /* (We already sent an end cell if possible) */
1224 connection_mark_for_close(TO_CONN(conn
));
1228 case RELAY_COMMAND_RESOLVE
:
1230 log_fn(LOG_PROTOCOL_WARN
, LD_APP
,
1231 "resolve request unsupported at AP; dropping.");
1234 log_fn(LOG_PROTOCOL_WARN
, domain
,
1235 "resolve request for known stream; dropping.");
1237 } else if (circ
->purpose
!= CIRCUIT_PURPOSE_OR
) {
1238 log_fn(LOG_PROTOCOL_WARN
, domain
,
1239 "resolve request on circ with purpose %d; dropping",
1243 connection_exit_begin_resolve(cell
, TO_OR_CIRCUIT(circ
));
1245 case RELAY_COMMAND_RESOLVED
:
1247 log_fn(LOG_PROTOCOL_WARN
, domain
,
1248 "'resolved' unsupported while open. Closing circ.");
1249 return -END_CIRC_REASON_TORPROTOCOL
;
1252 "'resolved' received, no conn attached anymore. Ignoring.");
1254 case RELAY_COMMAND_ESTABLISH_INTRO
:
1255 case RELAY_COMMAND_ESTABLISH_RENDEZVOUS
:
1256 case RELAY_COMMAND_INTRODUCE1
:
1257 case RELAY_COMMAND_INTRODUCE2
:
1258 case RELAY_COMMAND_INTRODUCE_ACK
:
1259 case RELAY_COMMAND_RENDEZVOUS1
:
1260 case RELAY_COMMAND_RENDEZVOUS2
:
1261 case RELAY_COMMAND_INTRO_ESTABLISHED
:
1262 case RELAY_COMMAND_RENDEZVOUS_ESTABLISHED
:
1263 rend_process_relay_cell(circ
, layer_hint
,
1264 rh
.command
, rh
.length
,
1265 cell
->payload
+RELAY_HEADER_SIZE
);
1268 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
1269 "Received unknown relay command %d. Perhaps the other side is using "
1270 "a newer version of Tor? Dropping.",
1272 return 0; /* for forward compatibility, don't kill the circuit */
1275 /** How many relay_data cells have we built, ever? */
1276 uint64_t stats_n_data_cells_packaged
= 0;
1277 /** How many bytes of data have we put in relay_data cells have we built,
1278 * ever? This would be RELAY_PAYLOAD_SIZE*stats_n_data_cells_packaged if
1279 * every relay cell we ever sent were completely full of data. */
1280 uint64_t stats_n_data_bytes_packaged
= 0;
1281 /** How many relay_data cells have we received, ever? */
1282 uint64_t stats_n_data_cells_received
= 0;
1283 /** How many bytes of data have we received relay_data cells, ever? This would
1284 * be RELAY_PAYLOAD_SIZE*stats_n_data_cells_packaged if every relay cell we
1285 * ever received were completely full of data. */
1286 uint64_t stats_n_data_bytes_received
= 0;
1288 /** While conn->inbuf has an entire relay payload of bytes on it,
1289 * and the appropriate package windows aren't empty, grab a cell
1290 * and send it down the circuit.
1292 * Return -1 (and send a RELAY_COMMAND_END cell if necessary) if conn should
1293 * be marked for close, else return 0.
1296 connection_edge_package_raw_inbuf(edge_connection_t
*conn
, int package_partial
)
1298 size_t amount_to_process
, length
;
1299 char payload
[CELL_PAYLOAD_SIZE
];
1301 unsigned domain
= conn
->cpath_layer
? LD_APP
: LD_EXIT
;
1305 if (conn
->_base
.marked_for_close
) {
1307 "called on conn that's already marked for close at %s:%d.",
1308 conn
->_base
.marked_for_close_file
, conn
->_base
.marked_for_close
);
1312 repeat_connection_edge_package_raw_inbuf
:
1314 circ
= circuit_get_by_edge_conn(conn
);
1316 log_info(domain
,"conn has no circuit! Closing.");
1317 conn
->end_reason
= END_STREAM_REASON_CANT_ATTACH
;
1321 if (circuit_consider_stop_edge_reading(circ
, conn
->cpath_layer
))
1324 if (conn
->package_window
<= 0) {
1325 log_info(domain
,"called with package_window %d. Skipping.",
1326 conn
->package_window
);
1327 connection_stop_reading(TO_CONN(conn
));
1331 amount_to_process
= buf_datalen(conn
->_base
.inbuf
);
1333 if (!amount_to_process
)
1336 if (!package_partial
&& amount_to_process
< RELAY_PAYLOAD_SIZE
)
1339 if (amount_to_process
> RELAY_PAYLOAD_SIZE
) {
1340 length
= RELAY_PAYLOAD_SIZE
;
1342 length
= amount_to_process
;
1344 stats_n_data_bytes_packaged
+= length
;
1345 stats_n_data_cells_packaged
+= 1;
1347 connection_fetch_from_buf(payload
, length
, TO_CONN(conn
));
1349 log_debug(domain
,"(%d) Packaging %d bytes (%d waiting).", conn
->_base
.s
,
1350 (int)length
, (int)buf_datalen(conn
->_base
.inbuf
));
1352 if (connection_edge_send_command(conn
, RELAY_COMMAND_DATA
,
1353 payload
, length
) < 0 )
1354 /* circuit got marked for close, don't continue, don't need to mark conn */
1357 if (!conn
->cpath_layer
) { /* non-rendezvous exit */
1358 tor_assert(circ
->package_window
> 0);
1359 circ
->package_window
--;
1360 } else { /* we're an AP, or an exit on a rendezvous circ */
1361 tor_assert(conn
->cpath_layer
->package_window
> 0);
1362 conn
->cpath_layer
->package_window
--;
1365 if (--conn
->package_window
<= 0) { /* is it 0 after decrement? */
1366 connection_stop_reading(TO_CONN(conn
));
1367 log_debug(domain
,"conn->package_window reached 0.");
1368 circuit_consider_stop_edge_reading(circ
, conn
->cpath_layer
);
1369 return 0; /* don't process the inbuf any more */
1371 log_debug(domain
,"conn->package_window is now %d",conn
->package_window
);
1373 /* handle more if there's more, or return 0 if there isn't */
1374 goto repeat_connection_edge_package_raw_inbuf
;
1377 /** Called when we've just received a relay data cell, or when
1378 * we've just finished flushing all bytes to stream <b>conn</b>.
1380 * If conn->outbuf is not too full, and our deliver window is
1381 * low, send back a suitable number of stream-level sendme cells.
1384 connection_edge_consider_sending_sendme(edge_connection_t
*conn
)
1388 if (connection_outbuf_too_full(TO_CONN(conn
)))
1391 circ
= circuit_get_by_edge_conn(conn
);
1393 /* this can legitimately happen if the destroy has already
1394 * arrived and torn down the circuit */
1395 log_info(LD_APP
,"No circuit associated with conn. Skipping.");
1399 while (conn
->deliver_window
<= STREAMWINDOW_START
- STREAMWINDOW_INCREMENT
) {
1400 log_debug(conn
->cpath_layer
?LD_APP
:LD_EXIT
,
1401 "Outbuf %d, Queuing stream sendme.",
1402 (int)conn
->_base
.outbuf_flushlen
);
1403 conn
->deliver_window
+= STREAMWINDOW_INCREMENT
;
1404 if (connection_edge_send_command(conn
, RELAY_COMMAND_SENDME
,
1406 log_warn(LD_APP
,"connection_edge_send_command failed. Skipping.");
1407 return; /* the circuit's closed, don't continue */
1412 /** The circuit <b>circ</b> has received a circuit-level sendme
1413 * (on hop <b>layer_hint</b>, if we're the OP). Go through all the
1414 * attached streams and let them resume reading and packaging, if
1415 * their stream windows allow it.
1418 circuit_resume_edge_reading(circuit_t
*circ
, crypt_path_t
*layer_hint
)
1421 log_debug(layer_hint
?LD_APP
:LD_EXIT
,"resuming");
1423 if (CIRCUIT_IS_ORIGIN(circ
))
1424 circuit_resume_edge_reading_helper(TO_ORIGIN_CIRCUIT(circ
)->p_streams
,
1427 circuit_resume_edge_reading_helper(TO_OR_CIRCUIT(circ
)->n_streams
,
1431 /** A helper function for circuit_resume_edge_reading() above.
1432 * The arguments are the same, except that <b>conn</b> is the head
1433 * of a linked list of edge streams that should each be considered.
1436 circuit_resume_edge_reading_helper(edge_connection_t
*conn
,
1438 crypt_path_t
*layer_hint
)
1440 for ( ; conn
; conn
=conn
->next_stream
) {
1441 if (conn
->_base
.marked_for_close
)
1443 if ((!layer_hint
&& conn
->package_window
> 0) ||
1444 (layer_hint
&& conn
->package_window
> 0 &&
1445 conn
->cpath_layer
== layer_hint
)) {
1446 connection_start_reading(TO_CONN(conn
));
1447 /* handle whatever might still be on the inbuf */
1448 if (connection_edge_package_raw_inbuf(conn
, 1)<0) {
1449 /* (We already sent an end cell if possible) */
1450 connection_mark_for_close(TO_CONN(conn
));
1454 /* If the circuit won't accept any more data, return without looking
1455 * at any more of the streams. Any connections that should be stopped
1456 * have already been stopped by connection_edge_package_raw_inbuf. */
1457 if (circuit_consider_stop_edge_reading(circ
, layer_hint
))
1464 /** Check if the package window for <b>circ</b> is empty (at
1465 * hop <b>layer_hint</b> if it's defined).
1467 * If yes, tell edge streams to stop reading and return 1.
1471 circuit_consider_stop_edge_reading(circuit_t
*circ
, crypt_path_t
*layer_hint
)
1473 edge_connection_t
*conn
= NULL
;
1474 unsigned domain
= layer_hint
? LD_APP
: LD_EXIT
;
1477 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
1478 log_debug(domain
,"considering circ->package_window %d",
1479 circ
->package_window
);
1480 if (circ
->package_window
<= 0) {
1481 log_debug(domain
,"yes, not-at-origin. stopped.");
1482 for (conn
= or_circ
->n_streams
; conn
; conn
=conn
->next_stream
)
1483 connection_stop_reading(TO_CONN(conn
));
1488 /* else, layer hint is defined, use it */
1489 log_debug(domain
,"considering layer_hint->package_window %d",
1490 layer_hint
->package_window
);
1491 if (layer_hint
->package_window
<= 0) {
1492 log_debug(domain
,"yes, at-origin. stopped.");
1493 for (conn
= TO_ORIGIN_CIRCUIT(circ
)->p_streams
; conn
;
1494 conn
=conn
->next_stream
)
1495 if (conn
->cpath_layer
== layer_hint
)
1496 connection_stop_reading(TO_CONN(conn
));
1502 /** Check if the deliver_window for circuit <b>circ</b> (at hop
1503 * <b>layer_hint</b> if it's defined) is low enough that we should
1504 * send a circuit-level sendme back down the circuit. If so, send
1505 * enough sendmes that the window would be overfull if we sent any
1509 circuit_consider_sending_sendme(circuit_t
*circ
, crypt_path_t
*layer_hint
)
1511 // log_fn(LOG_INFO,"Considering: layer_hint is %s",
1512 // layer_hint ? "defined" : "null");
1513 while ((layer_hint
? layer_hint
->deliver_window
: circ
->deliver_window
) <=
1514 CIRCWINDOW_START
- CIRCWINDOW_INCREMENT
) {
1515 log_debug(LD_CIRC
,"Queuing circuit sendme.");
1517 layer_hint
->deliver_window
+= CIRCWINDOW_INCREMENT
;
1519 circ
->deliver_window
+= CIRCWINDOW_INCREMENT
;
1520 if (relay_send_command_from_edge(0, circ
, RELAY_COMMAND_SENDME
,
1521 NULL
, 0, layer_hint
) < 0) {
1523 "relay_send_command_from_edge failed. Circuit's closed.");
1524 return; /* the circuit's closed, don't continue */
1529 /** Stop reading on edge connections when we have this many cells
1530 * waiting on the appropriate queue. */
1531 #define CELL_QUEUE_HIGHWATER_SIZE 256
1532 /** Start reading from edge connections again when we get down to this many
1534 #define CELL_QUEUE_LOWWATER_SIZE 64
1536 #ifdef ACTIVE_CIRCUITS_PARANOIA
1537 #define assert_active_circuits_ok_paranoid(conn) \
1538 assert_active_circuits_ok(conn)
1540 #define assert_active_circuits_ok_paranoid(conn)
1543 /** The total number of cells we have allocated from the memory pool. */
1544 static int total_cells_allocated
= 0;
1546 /** A memory pool to allocate packed_cell_t objects. */
1547 static mp_pool_t
*cell_pool
= NULL
;
1549 /** Memory pool to allocate insertion_time_elem_t objects used for cell
1551 static mp_pool_t
*it_pool
= NULL
;
1553 /** Allocate structures to hold cells. */
1555 init_cell_pool(void)
1557 tor_assert(!cell_pool
);
1558 cell_pool
= mp_pool_new(sizeof(packed_cell_t
), 128*1024);
1561 /** Free all storage used to hold cells (and insertion times if we measure
1562 * cell statistics). */
1564 free_cell_pool(void)
1566 /* Maybe we haven't called init_cell_pool yet; need to check for it. */
1568 mp_pool_destroy(cell_pool
);
1572 mp_pool_destroy(it_pool
);
1577 /** Free excess storage in cell pool. */
1579 clean_cell_pool(void)
1581 tor_assert(cell_pool
);
1582 mp_pool_clean(cell_pool
, 0, 1);
1585 /** Release storage held by <b>cell</b>. */
1587 packed_cell_free_unchecked(packed_cell_t
*cell
)
1589 --total_cells_allocated
;
1590 mp_pool_release(cell
);
1593 /** Allocate and return a new packed_cell_t. */
1594 static INLINE packed_cell_t
*
1595 packed_cell_alloc(void)
1597 ++total_cells_allocated
;
1598 return mp_pool_get(cell_pool
);
1601 /** Log current statistics for cell pool allocation at log level
1602 * <b>severity</b>. */
1604 dump_cell_pool_usage(int severity
)
1609 for (c
= _circuit_get_global_list(); c
; c
= c
->next
) {
1610 n_cells
+= c
->n_conn_cells
.n
;
1611 if (!CIRCUIT_IS_ORIGIN(c
))
1612 n_cells
+= TO_OR_CIRCUIT(c
)->p_conn_cells
.n
;
1615 log(severity
, LD_MM
, "%d cells allocated on %d circuits. %d cells leaked.",
1616 n_cells
, n_circs
, total_cells_allocated
- n_cells
);
1617 mp_pool_log_status(cell_pool
, severity
);
1620 /** Allocate a new copy of packed <b>cell</b>. */
1621 static INLINE packed_cell_t
*
1622 packed_cell_copy(const cell_t
*cell
)
1624 packed_cell_t
*c
= packed_cell_alloc();
1630 /** Append <b>cell</b> to the end of <b>queue</b>. */
1632 cell_queue_append(cell_queue_t
*queue
, packed_cell_t
*cell
)
1635 tor_assert(!queue
->tail
->next
);
1636 queue
->tail
->next
= cell
;
1645 /** Append a newly allocated copy of <b>cell</b> to the end of <b>queue</b> */
1647 cell_queue_append_packed_copy(cell_queue_t
*queue
, const cell_t
*cell
)
1649 packed_cell_t
*copy
= packed_cell_copy(cell
);
1650 /* Remember the time when this cell was put in the queue. */
1651 if (get_options()->CellStatistics
) {
1654 insertion_time_queue_t
*it_queue
= queue
->insertion_times
;
1656 it_pool
= mp_pool_new(sizeof(insertion_time_elem_t
), 1024);
1657 tor_gettimeofday_cached(&now
);
1658 #define SECONDS_IN_A_DAY 86400L
1659 added
= (uint32_t)(((now
.tv_sec
% SECONDS_IN_A_DAY
) * 100L)
1660 + ((uint32_t)now
.tv_usec
/ (uint32_t)10000L));
1662 it_queue
= tor_malloc_zero(sizeof(insertion_time_queue_t
));
1663 queue
->insertion_times
= it_queue
;
1665 if (it_queue
->last
&& it_queue
->last
->insertion_time
== added
) {
1666 it_queue
->last
->counter
++;
1668 insertion_time_elem_t
*elem
= mp_pool_get(it_pool
);
1670 elem
->insertion_time
= added
;
1672 if (it_queue
->last
) {
1673 it_queue
->last
->next
= elem
;
1674 it_queue
->last
= elem
;
1676 it_queue
->first
= it_queue
->last
= elem
;
1680 cell_queue_append(queue
, copy
);
1683 /** Remove and free every cell in <b>queue</b>. */
1685 cell_queue_clear(cell_queue_t
*queue
)
1687 packed_cell_t
*cell
, *next
;
1691 packed_cell_free_unchecked(cell
);
1694 queue
->head
= queue
->tail
= NULL
;
1696 if (queue
->insertion_times
) {
1697 while (queue
->insertion_times
->first
) {
1698 insertion_time_elem_t
*elem
= queue
->insertion_times
->first
;
1699 queue
->insertion_times
->first
= elem
->next
;
1700 mp_pool_release(elem
);
1702 tor_free(queue
->insertion_times
);
1706 /** Extract and return the cell at the head of <b>queue</b>; return NULL if
1707 * <b>queue</b> is empty. */
1708 static INLINE packed_cell_t
*
1709 cell_queue_pop(cell_queue_t
*queue
)
1711 packed_cell_t
*cell
= queue
->head
;
1714 queue
->head
= cell
->next
;
1715 if (cell
== queue
->tail
) {
1716 tor_assert(!queue
->head
);
1723 /** Return a pointer to the "next_active_on_{n,p}_conn" pointer of <b>circ</b>,
1724 * depending on whether <b>conn</b> matches n_conn or p_conn. */
1725 static INLINE circuit_t
**
1726 next_circ_on_conn_p(circuit_t
*circ
, or_connection_t
*conn
)
1730 if (conn
== circ
->n_conn
) {
1731 return &circ
->next_active_on_n_conn
;
1733 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
1734 tor_assert(conn
== orcirc
->p_conn
);
1735 return &orcirc
->next_active_on_p_conn
;
1739 /** Return a pointer to the "prev_active_on_{n,p}_conn" pointer of <b>circ</b>,
1740 * depending on whether <b>conn</b> matches n_conn or p_conn. */
1741 static INLINE circuit_t
**
1742 prev_circ_on_conn_p(circuit_t
*circ
, or_connection_t
*conn
)
1746 if (conn
== circ
->n_conn
) {
1747 return &circ
->prev_active_on_n_conn
;
1749 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
1750 tor_assert(conn
== orcirc
->p_conn
);
1751 return &orcirc
->prev_active_on_p_conn
;
1755 /** Helper for sorting cell_ewma_t values in their priority queue. */
1757 compare_cell_ewma_counts(const void *p1
, const void *p2
)
1759 const cell_ewma_t
*e1
=p1
, *e2
=p2
;
1760 if (e1
->cell_count
< e2
->cell_count
)
1762 else if (e1
->cell_count
> e2
->cell_count
)
1768 /** Given a cell_ewma_t, return a pointer to the circuit containing it. */
1770 cell_ewma_to_circuit(cell_ewma_t
*ewma
)
1772 if (ewma
->is_for_p_conn
) {
1773 /* This is an or_circuit_t's p_cell_ewma. */
1774 or_circuit_t
*orcirc
= SUBTYPE_P(ewma
, or_circuit_t
, p_cell_ewma
);
1775 return TO_CIRCUIT(orcirc
);
1777 /* This is some circuit's n_cell_ewma. */
1778 return SUBTYPE_P(ewma
, circuit_t
, n_cell_ewma
);
1782 /* ==== Functions for scaling cell_ewma_t ====
1784 When choosing which cells to relay first, we favor circuits that have been
1785 quiet recently. This gives better latency on connections that aren't
1786 pushing lots of data, and makes the network feel more interactive.
1788 Conceptually, we take an exponentially weighted mean average of the number
1789 of cells a circuit has sent, and allow active circuits (those with cells to
1790 relay) to send cells in reverse order of their exponentially-weighted mean
1791 average (EWMA) cell count. [That is, a cell sent N seconds ago 'counts'
1792 F^N times as much as a cell sent now, for 0<F<1.0, and we favor the
1793 circuit that has sent the fewest cells]
1795 If 'double' had infinite precision, we could do this simply by counting a
1796 cell sent at startup as having weight 1.0, and a cell sent N seconds later
1797 as having weight F^-N. This way, we would never need to re-scale
1798 any already-sent cells.
1800 To prevent double from overflowing, we could count a cell sent now as
1801 having weight 1.0 and a cell sent N seconds ago as having weight F^N.
1802 This, however, would mean we'd need to re-scale *ALL* old circuits every
1803 time we wanted to send a cell.
1805 So as a compromise, we divide time into 'ticks' (currently, 10-second
1806 increments) and say that a cell sent at the start of a current tick is
1807 worth 1.0, a cell sent N seconds before the start of the current tick is
1808 worth F^N, and a cell sent N seconds after the start of the current tick is
1809 worth F^-N. This way we don't overflow, and we don't need to constantly
1813 /** How long does a tick last (seconds)? */
1814 #define EWMA_TICK_LEN 10
1816 /** The default per-tick scale factor, if it hasn't been overridden by a
1817 * consensus or a configuration setting. zero means "disabled". */
1818 #define EWMA_DEFAULT_HALFLIFE 0.0
1820 /** Given a timeval <b>now</b>, compute the cell_ewma tick in which it occurs
1821 * and the fraction of the tick that has elapsed between the start of the tick
1822 * and <b>now</b>. Return the former and store the latter in
1823 * *<b>remainder_out</b>.
1825 * These tick values are not meant to be shared between Tor instances, or used
1826 * for other purposes. */
1828 cell_ewma_tick_from_timeval(const struct timeval
*now
,
1829 double *remainder_out
)
1831 unsigned res
= (unsigned) (now
->tv_sec
/ EWMA_TICK_LEN
);
1833 double rem
= (now
->tv_sec
% EWMA_TICK_LEN
) +
1834 ((double)(now
->tv_usec
)) / 1.0e6
;
1835 *remainder_out
= rem
/ EWMA_TICK_LEN
;
1839 /** Compute and return the current cell_ewma tick. */
1841 cell_ewma_get_tick(void)
1843 return ((unsigned)approx_time() / EWMA_TICK_LEN
);
1846 /** The per-tick scale factor to be used when computing cell-count EWMA
1847 * values. (A cell sent N ticks before the start of the current tick
1848 * has value ewma_scale_factor ** N.)
1850 static double ewma_scale_factor
= 0.1;
1851 static int ewma_enabled
= 0;
1853 #define EPSILON 0.00001
1854 #define LOG_ONEHALF -0.69314718055994529
1856 /** Adjust the global cell scale factor based on <b>options</b> */
1858 cell_ewma_set_scale_factor(or_options_t
*options
, networkstatus_t
*consensus
)
1860 int32_t halflife_ms
;
1863 if (options
&& options
->CircuitPriorityHalflife
>= -EPSILON
) {
1864 halflife
= options
->CircuitPriorityHalflife
;
1865 source
= "CircuitPriorityHalflife in configuration";
1866 } else if (consensus
&&
1867 (halflife_ms
= networkstatus_get_param(
1868 consensus
, "CircuitPriorityHalflifeMsec", -1)) >= 0) {
1869 halflife
= ((double)halflife_ms
)/1000.0;
1870 source
= "CircuitPriorityHalflifeMsec in consensus";
1872 halflife
= EWMA_DEFAULT_HALFLIFE
;
1873 source
= "Default value";
1876 if (halflife
<= EPSILON
) {
1877 /* The cell EWMA algorithm is disabled. */
1878 ewma_scale_factor
= 0.1;
1881 "Disabled cell_ewma algorithm because of value in %s",
1884 /* convert halflife into halflife-per-tick. */
1885 halflife
/= EWMA_TICK_LEN
;
1886 /* compute per-tick scale factor. */
1887 ewma_scale_factor
= exp( LOG_ONEHALF
/ halflife
);
1890 "Enabled cell_ewma algorithm because of value in %s; "
1891 "scale factor is %lf per %d seconds",
1892 source
, ewma_scale_factor
, EWMA_TICK_LEN
);
1896 /** Return the multiplier necessary to convert the value of a cell sent in
1897 * 'from_tick' to one sent in 'to_tick'. */
1898 static INLINE
double
1899 get_scale_factor(unsigned from_tick
, unsigned to_tick
)
1901 /* This math can wrap around, but that's okay: unsigned overflow is
1903 int diff
= (int)(to_tick
- from_tick
);
1904 return pow(ewma_scale_factor
, diff
);
1907 /** Adjust the cell count of <b>ewma</b> so that it is scaled with respect to
1908 * <b>cur_tick</b> */
1910 scale_single_cell_ewma(cell_ewma_t
*ewma
, unsigned cur_tick
)
1912 double factor
= get_scale_factor(ewma
->last_adjusted_tick
, cur_tick
);
1913 ewma
->cell_count
*= factor
;
1914 ewma
->last_adjusted_tick
= cur_tick
;
1917 /** Adjust the cell count of every active circuit on <b>conn</b> so
1918 * that they are scaled with respect to <b>cur_tick</b> */
1920 scale_active_circuits(or_connection_t
*conn
, unsigned cur_tick
)
1923 double factor
= get_scale_factor(
1924 conn
->active_circuit_pqueue_last_recalibrated
,
1926 /** Ordinarily it isn't okay to change the value of an element in a heap,
1927 * but it's okay here, since we are preserving the order. */
1928 SMARTLIST_FOREACH(conn
->active_circuit_pqueue
, cell_ewma_t
*, e
, {
1929 tor_assert(e
->last_adjusted_tick
==
1930 conn
->active_circuit_pqueue_last_recalibrated
);
1931 e
->cell_count
*= factor
;
1932 e
->last_adjusted_tick
= cur_tick
;
1934 conn
->active_circuit_pqueue_last_recalibrated
= cur_tick
;
1937 /** Rescale <b>ewma</b> to the same scale as <b>conn</b>, and add it to
1938 * <b>conn</b>'s priority queue of active circuits */
1940 add_cell_ewma_to_conn(or_connection_t
*conn
, cell_ewma_t
*ewma
)
1942 tor_assert(ewma
->heap_index
== -1);
1943 scale_single_cell_ewma(ewma
,
1944 conn
->active_circuit_pqueue_last_recalibrated
);
1946 smartlist_pqueue_add(conn
->active_circuit_pqueue
,
1947 compare_cell_ewma_counts
,
1948 STRUCT_OFFSET(cell_ewma_t
, heap_index
),
1952 /** Remove <b>ewma</b> from <b>conn</b>'s priority queue of active circuits */
1954 remove_cell_ewma_from_conn(or_connection_t
*conn
, cell_ewma_t
*ewma
)
1956 tor_assert(ewma
->heap_index
!= -1);
1957 smartlist_pqueue_remove(conn
->active_circuit_pqueue
,
1958 compare_cell_ewma_counts
,
1959 STRUCT_OFFSET(cell_ewma_t
, heap_index
),
1963 /** Remove and return the first cell_ewma_t from conn's priority queue of
1964 * active circuits. Requires that the priority queue is nonempty. */
1965 static cell_ewma_t
*
1966 pop_first_cell_ewma_from_conn(or_connection_t
*conn
)
1968 return smartlist_pqueue_pop(conn
->active_circuit_pqueue
,
1969 compare_cell_ewma_counts
,
1970 STRUCT_OFFSET(cell_ewma_t
, heap_index
));
1973 /** Add <b>circ</b> to the list of circuits with pending cells on
1974 * <b>conn</b>. No effect if <b>circ</b> is already linked. */
1976 make_circuit_active_on_conn(circuit_t
*circ
, or_connection_t
*conn
)
1978 circuit_t
**nextp
= next_circ_on_conn_p(circ
, conn
);
1979 circuit_t
**prevp
= prev_circ_on_conn_p(circ
, conn
);
1981 if (*nextp
&& *prevp
) {
1982 /* Already active. */
1986 assert_active_circuits_ok_paranoid(conn
);
1988 if (! conn
->active_circuits
) {
1989 conn
->active_circuits
= circ
;
1990 *prevp
= *nextp
= circ
;
1992 circuit_t
*head
= conn
->active_circuits
;
1993 circuit_t
*old_tail
= *prev_circ_on_conn_p(head
, conn
);
1994 *next_circ_on_conn_p(old_tail
, conn
) = circ
;
1996 *prev_circ_on_conn_p(head
, conn
) = circ
;
2000 if (circ
->n_conn
== conn
) {
2001 add_cell_ewma_to_conn(conn
, &circ
->n_cell_ewma
);
2003 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
2004 tor_assert(conn
== orcirc
->p_conn
);
2005 add_cell_ewma_to_conn(conn
, &orcirc
->p_cell_ewma
);
2008 assert_active_circuits_ok_paranoid(conn
);
2011 /** Remove <b>circ</b> from the list of circuits with pending cells on
2012 * <b>conn</b>. No effect if <b>circ</b> is already unlinked. */
2014 make_circuit_inactive_on_conn(circuit_t
*circ
, or_connection_t
*conn
)
2016 circuit_t
**nextp
= next_circ_on_conn_p(circ
, conn
);
2017 circuit_t
**prevp
= prev_circ_on_conn_p(circ
, conn
);
2018 circuit_t
*next
= *nextp
, *prev
= *prevp
;
2020 if (!next
&& !prev
) {
2021 /* Already inactive. */
2025 assert_active_circuits_ok_paranoid(conn
);
2027 tor_assert(next
&& prev
);
2028 tor_assert(*prev_circ_on_conn_p(next
, conn
) == circ
);
2029 tor_assert(*next_circ_on_conn_p(prev
, conn
) == circ
);
2032 conn
->active_circuits
= NULL
;
2034 *prev_circ_on_conn_p(next
, conn
) = prev
;
2035 *next_circ_on_conn_p(prev
, conn
) = next
;
2036 if (conn
->active_circuits
== circ
)
2037 conn
->active_circuits
= next
;
2039 *prevp
= *nextp
= NULL
;
2041 if (circ
->n_conn
== conn
) {
2042 remove_cell_ewma_from_conn(conn
, &circ
->n_cell_ewma
);
2044 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
2045 tor_assert(conn
== orcirc
->p_conn
);
2046 remove_cell_ewma_from_conn(conn
, &orcirc
->p_cell_ewma
);
2049 assert_active_circuits_ok_paranoid(conn
);
2052 /** Remove all circuits from the list of circuits with pending cells on
2055 connection_or_unlink_all_active_circs(or_connection_t
*orconn
)
2057 circuit_t
*head
= orconn
->active_circuits
;
2058 circuit_t
*cur
= head
;
2062 circuit_t
*next
= *next_circ_on_conn_p(cur
, orconn
);
2063 *prev_circ_on_conn_p(cur
, orconn
) = NULL
;
2064 *next_circ_on_conn_p(cur
, orconn
) = NULL
;
2066 } while (cur
!= head
);
2067 orconn
->active_circuits
= NULL
;
2069 SMARTLIST_FOREACH(orconn
->active_circuit_pqueue
, cell_ewma_t
*, e
,
2070 e
->heap_index
= -1);
2071 smartlist_clear(orconn
->active_circuit_pqueue
);
2074 /** Block (if <b>block</b> is true) or unblock (if <b>block</b> is false)
2075 * every edge connection that is using <b>circ</b> to write to <b>orconn</b>,
2076 * and start or stop reading as appropriate. */
2078 set_streams_blocked_on_circ(circuit_t
*circ
, or_connection_t
*orconn
,
2081 edge_connection_t
*edge
= NULL
;
2082 if (circ
->n_conn
== orconn
) {
2083 circ
->streams_blocked_on_n_conn
= block
;
2084 if (CIRCUIT_IS_ORIGIN(circ
))
2085 edge
= TO_ORIGIN_CIRCUIT(circ
)->p_streams
;
2087 circ
->streams_blocked_on_p_conn
= block
;
2088 tor_assert(!CIRCUIT_IS_ORIGIN(circ
));
2089 edge
= TO_OR_CIRCUIT(circ
)->n_streams
;
2092 for (; edge
; edge
= edge
->next_stream
) {
2093 connection_t
*conn
= TO_CONN(edge
);
2094 edge
->edge_blocked_on_circ
= block
;
2096 if (!conn
->read_event
) {
2097 /* This connection is a placeholder for something; probably a DNS
2098 * request. It can't actually stop or start reading.*/
2103 if (connection_is_reading(conn
))
2104 connection_stop_reading(conn
);
2106 /* Is this right? */
2107 if (!connection_is_reading(conn
))
2108 connection_start_reading(conn
);
2113 /** Pull as many cells as possible (but no more than <b>max</b>) from the
2114 * queue of the first active circuit on <b>conn</b>, and write them to
2115 * <b>conn</b>->outbuf. Return the number of cells written. Advance
2116 * the active circuit pointer to the next active circuit in the ring. */
2118 connection_or_flush_from_first_active_circuit(or_connection_t
*conn
, int max
,
2122 cell_queue_t
*queue
;
2124 int streams_blocked
;
2126 /* The current (hi-res) time */
2127 struct timeval now_hires
;
2129 /* The EWMA cell counter for the circuit we're flushing. */
2130 cell_ewma_t
*cell_ewma
= NULL
;
2131 double ewma_increment
= -1;
2133 circ
= conn
->active_circuits
;
2134 if (!circ
) return 0;
2135 assert_active_circuits_ok_paranoid(conn
);
2137 /* See if we're doing the ewma circuit selection algorithm. */
2140 double fractional_tick
;
2141 tor_gettimeofday_cached(&now_hires
);
2142 tick
= cell_ewma_tick_from_timeval(&now_hires
, &fractional_tick
);
2144 if (tick
!= conn
->active_circuit_pqueue_last_recalibrated
) {
2145 scale_active_circuits(conn
, tick
);
2148 ewma_increment
= pow(ewma_scale_factor
, -fractional_tick
);
2150 cell_ewma
= smartlist_get(conn
->active_circuit_pqueue
, 0);
2151 circ
= cell_ewma_to_circuit(cell_ewma
);
2154 if (circ
->n_conn
== conn
) {
2155 queue
= &circ
->n_conn_cells
;
2156 streams_blocked
= circ
->streams_blocked_on_n_conn
;
2158 queue
= &TO_OR_CIRCUIT(circ
)->p_conn_cells
;
2159 streams_blocked
= circ
->streams_blocked_on_p_conn
;
2161 tor_assert(*next_circ_on_conn_p(circ
,conn
));
2163 for (n_flushed
= 0; n_flushed
< max
&& queue
->head
; ) {
2164 packed_cell_t
*cell
= cell_queue_pop(queue
);
2165 tor_assert(*next_circ_on_conn_p(circ
,conn
));
2167 /* Calculate the exact time that this cell has spent in the queue. */
2168 if (get_options()->CellStatistics
&& !CIRCUIT_IS_ORIGIN(circ
)) {
2171 uint32_t cell_waiting_time
;
2172 insertion_time_queue_t
*it_queue
= queue
->insertion_times
;
2173 tor_gettimeofday_cached(&now
);
2174 flushed
= (uint32_t)((now
.tv_sec
% SECONDS_IN_A_DAY
) * 100L +
2175 (uint32_t)now
.tv_usec
/ (uint32_t)10000L);
2176 if (!it_queue
|| !it_queue
->first
) {
2177 log_warn(LD_BUG
, "Cannot determine insertion time of cell.");
2179 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
2180 insertion_time_elem_t
*elem
= it_queue
->first
;
2182 (uint32_t)((flushed
* 10L + SECONDS_IN_A_DAY
* 1000L -
2183 elem
->insertion_time
* 10L) %
2184 (SECONDS_IN_A_DAY
* 1000L));
2185 #undef SECONDS_IN_A_DAY
2187 if (elem
->counter
< 1) {
2188 it_queue
->first
= elem
->next
;
2189 if (elem
== it_queue
->last
)
2190 it_queue
->last
= NULL
;
2191 mp_pool_release(elem
);
2193 orcirc
->total_cell_waiting_time
+= cell_waiting_time
;
2194 orcirc
->processed_cells
++;
2198 /* If we just flushed our queue and this circuit is used for a
2199 * tunneled directory request, possibly advance its state. */
2200 if (queue
->n
== 0 && TO_CONN(conn
)->dirreq_id
)
2201 geoip_change_dirreq_state(TO_CONN(conn
)->dirreq_id
,
2203 DIRREQ_CIRC_QUEUE_FLUSHED
);
2205 connection_write_to_buf(cell
->body
, CELL_NETWORK_SIZE
, TO_CONN(conn
));
2207 packed_cell_free_unchecked(cell
);
2211 cell_ewma
->cell_count
+= ewma_increment
;
2212 /* We pop and re-add the cell_ewma_t here, not above, since we need to
2213 * re-add it immediately to keep the priority queue consistent with
2214 * the linked-list implementation */
2215 tmp
= pop_first_cell_ewma_from_conn(conn
);
2216 tor_assert(tmp
== cell_ewma
);
2217 add_cell_ewma_to_conn(conn
, cell_ewma
);
2219 if (circ
!= conn
->active_circuits
) {
2220 /* If this happens, the current circuit just got made inactive by
2221 * a call in connection_write_to_buf(). That's nothing to worry about:
2222 * circuit_make_inactive_on_conn() already advanced conn->active_circuits
2225 assert_active_circuits_ok_paranoid(conn
);
2229 tor_assert(*next_circ_on_conn_p(circ
,conn
));
2230 assert_active_circuits_ok_paranoid(conn
);
2231 conn
->active_circuits
= *next_circ_on_conn_p(circ
, conn
);
2233 /* Is the cell queue low enough to unblock all the streams that are waiting
2234 * to write to this circuit? */
2235 if (streams_blocked
&& queue
->n
<= CELL_QUEUE_LOWWATER_SIZE
)
2236 set_streams_blocked_on_circ(circ
, conn
, 0); /* unblock streams */
2238 /* Did we just run out of cells on this circuit's queue? */
2239 if (queue
->n
== 0) {
2240 log_debug(LD_GENERAL
, "Made a circuit inactive.");
2241 make_circuit_inactive_on_conn(circ
, conn
);
2245 conn
->timestamp_last_added_nonpadding
= now
;
2249 /** Add <b>cell</b> to the queue of <b>circ</b> writing to <b>orconn</b>
2250 * transmitting in <b>direction</b>. */
2252 append_cell_to_circuit_queue(circuit_t
*circ
, or_connection_t
*orconn
,
2253 cell_t
*cell
, cell_direction_t direction
)
2255 cell_queue_t
*queue
;
2256 int streams_blocked
;
2257 if (direction
== CELL_DIRECTION_OUT
) {
2258 queue
= &circ
->n_conn_cells
;
2259 streams_blocked
= circ
->streams_blocked_on_n_conn
;
2261 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
2262 queue
= &orcirc
->p_conn_cells
;
2263 streams_blocked
= circ
->streams_blocked_on_p_conn
;
2265 if (cell
->command
== CELL_RELAY_EARLY
&& orconn
->link_proto
< 2) {
2266 /* V1 connections don't understand RELAY_EARLY. */
2267 cell
->command
= CELL_RELAY
;
2270 cell_queue_append_packed_copy(queue
, cell
);
2272 /* If we have too many cells on the circuit, we should stop reading from
2273 * the edge streams for a while. */
2274 if (!streams_blocked
&& queue
->n
>= CELL_QUEUE_HIGHWATER_SIZE
)
2275 set_streams_blocked_on_circ(circ
, orconn
, 1); /* block streams */
2277 if (queue
->n
== 1) {
2278 /* This was the first cell added to the queue. We need to make this
2279 * circuit active. */
2280 log_debug(LD_GENERAL
, "Made a circuit active.");
2281 make_circuit_active_on_conn(circ
, orconn
);
2284 if (! buf_datalen(orconn
->_base
.outbuf
)) {
2285 /* There is no data at all waiting to be sent on the outbuf. Add a
2286 * cell, so that we can notice when it gets flushed, flushed_some can
2287 * get called, and we can start putting more data onto the buffer then.
2289 log_debug(LD_GENERAL
, "Primed a buffer.");
2290 connection_or_flush_from_first_active_circuit(orconn
, 1, approx_time());
2294 /** Append an encoded value of <b>addr</b> to <b>payload_out</b>, which must
2295 * have at least 18 bytes of free space. The encoding is, as specified in
2297 * RESOLVED_TYPE_IPV4 or RESOLVED_TYPE_IPV6 [1 byte]
2299 * ADDRESS [length bytes]
2300 * Return the number of bytes added, or -1 on error */
2302 append_address_to_payload(char *payload_out
, const tor_addr_t
*addr
)
2305 switch (tor_addr_family(addr
)) {
2307 payload_out
[0] = RESOLVED_TYPE_IPV4
;
2309 a
= tor_addr_to_ipv4n(addr
);
2310 memcpy(payload_out
+2, &a
, 4);
2313 payload_out
[0] = RESOLVED_TYPE_IPV6
;
2314 payload_out
[1] = 16;
2315 memcpy(payload_out
+2, tor_addr_to_in6_addr8(addr
), 16);
2323 /** Given <b>payload_len</b> bytes at <b>payload</b>, starting with an address
2324 * encoded as by append_address_to_payload(), try to decode the address into
2325 * *<b>addr_out</b>. Return the next byte in the payload after the address on
2326 * success, or NULL on failure. */
2328 decode_address_from_payload(tor_addr_t
*addr_out
, const char *payload
,
2331 if (payload_len
< 2)
2333 if (payload_len
< 2+(uint8_t)payload
[1])
2336 switch (payload
[0]) {
2337 case RESOLVED_TYPE_IPV4
:
2338 if (payload
[1] != 4)
2340 tor_addr_from_ipv4n(addr_out
, get_uint32(payload
+2));
2342 case RESOLVED_TYPE_IPV6
:
2343 if (payload
[1] != 16)
2345 tor_addr_from_ipv6_bytes(addr_out
, payload
+2);
2348 tor_addr_make_unspec(addr_out
);
2351 return payload
+ 2 + (uint8_t)payload
[1];
2354 /** Fail with an assert if the active circuits ring on <b>orconn</b> is
2357 assert_active_circuits_ok(or_connection_t
*orconn
)
2359 circuit_t
*head
= orconn
->active_circuits
;
2360 circuit_t
*cur
= head
;
2365 circuit_t
*next
= *next_circ_on_conn_p(cur
, orconn
);
2366 circuit_t
*prev
= *prev_circ_on_conn_p(cur
, orconn
);
2370 tor_assert(*next_circ_on_conn_p(prev
, orconn
) == cur
);
2371 tor_assert(*prev_circ_on_conn_p(next
, orconn
) == cur
);
2372 if (orconn
== cur
->n_conn
) {
2373 ewma
= &cur
->n_cell_ewma
;
2374 tor_assert(!ewma
->is_for_p_conn
);
2376 ewma
= &TO_OR_CIRCUIT(cur
)->p_cell_ewma
;
2377 tor_assert(ewma
->is_for_p_conn
);
2379 tor_assert(ewma
->heap_index
!= -1);
2380 tor_assert(ewma
== smartlist_get(orconn
->active_circuit_pqueue
,
2384 } while (cur
!= head
);
2386 tor_assert(n
== smartlist_len(orconn
->active_circuit_pqueue
));