-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Nick, here are the four patches for proposal 155. I also put some thoughts into generalizing parallel circuit establishment to all circuits, but for the moment I'd rather stick to the simple patch 2 here. The two code changes in that patch are exactly what is needed for on-demand circuit creation; for pre-established circuits this might be different. Anyway, I hope that the code changes in patch 2 will give hints for the implementation of a similar behavior for general circuits. Thanks, - --Karsten -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFI7KA70M+WPffBEmURAha6AJ9RubChK9KgQYSfrHpKGNpQrdQBDACgh/ym 9EFy7LAlgtrbcv/rcXrDcx8= =498Z -----END PGP SIGNATURE-----
Index: /home/karsten/tor/tor-trunk-155-patch1/ChangeLog
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch1/ChangeLog (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch1/ChangeLog (working copy)
@@ -3,6 +3,8 @@
- Now NodeFamily and MyFamily config options allow spaces in
identity fingerprints, so it's easier to paste them in.
Suggested by Lucky Green.
+ - Reduce extension timeout for introduction circuits from 60 to 30
+ seconds.
Changes in version 0.2.1.6-alpha - 2008-09-30
Index: /home/karsten/tor/tor-trunk-155-patch1/src/or/circuituse.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch1/src/or/circuituse.c (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch1/src/or/circuituse.c (working copy)
@@ -251,8 +251,11 @@
circuit_expire_building(time_t now)
{
circuit_t *victim, *circ = global_circuitlist;
- time_t cutoff = now - get_options()->CircuitBuildTimeout;
+ time_t cutoff;
+ time_t general_cutoff = now - get_options()->CircuitBuildTimeout;
time_t begindir_cutoff = now - get_options()->CircuitBuildTimeout/2;
+#define REND_INTRO_CIRC_TIMEOUT 30
+ time_t introrend_cutoff = now - REND_INTRO_CIRC_TIMEOUT;
cpath_build_state_t *build_state;
while (circ) {
@@ -263,11 +266,21 @@
continue;
build_state = TO_ORIGIN_CIRCUIT(victim)->build_state;
- if (victim->timestamp_created >
- ((build_state && build_state->onehop_tunnel) ?
- begindir_cutoff : cutoff))
+ if (build_state && build_state->onehop_tunnel)
+ cutoff = begindir_cutoff;
+ else if (victim->purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
+ cutoff = introrend_cutoff;
+ else
+ cutoff = general_cutoff;
+ if (victim->timestamp_created > cutoff)
continue; /* it's still young, leave it alone */
+ if (victim->purpose == CIRCUIT_PURPOSE_C_INTRODUCING &&
+ victim->timestamp_created <= introrend_cutoff &&
+ victim->timestamp_created > general_cutoff)
+ log_info(LD_REND|LD_CIRC, "Timing out introduction circuit which we "
+ "would not have done if it had been a general circuit.");
+
#if 0
/* some debug logs, to help track bugs */
if (victim->purpose >= CIRCUIT_PURPOSE_C_INTRODUCING &&
Index: /home/karsten/tor/tor-trunk-155-patch2/ChangeLog
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch2/ChangeLog (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch2/ChangeLog (working copy)
@@ -3,6 +3,8 @@
- Now NodeFamily and MyFamily config options allow spaces in
identity fingerprints, so it's easier to paste them in.
Suggested by Lucky Green.
+ - Start extending introduction circuits in parallel after a delay of
+ 15 seconds (based on work by Christian Wilms).
Changes in version 0.2.1.6-alpha - 2008-09-30
Index: /home/karsten/tor/tor-trunk-155-patch2/src/or/circuituse.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch2/src/or/circuituse.c (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch2/src/or/circuituse.c (working copy)
@@ -194,6 +194,7 @@
{
circuit_t *circ, *best=NULL;
time_t now = time(NULL);
+ int intro_going_on_but_too_old = 0;
tor_assert(conn);
@@ -202,9 +203,16 @@
purpose == CIRCUIT_PURPOSE_C_REND_JOINED);
for (circ=global_circuitlist;circ;circ = circ->next) {
+#define REND_PARALLEL_INTRO_DELAY 15
if (!circuit_is_acceptable(circ,conn,must_be_open,purpose,
need_uptime,need_internal,now))
continue;
+ else if (purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT &&
+ !must_be_open && circ->state != CIRCUIT_STATE_OPEN &&
+ circ->timestamp_created + REND_PARALLEL_INTRO_DELAY < now) {
+ intro_going_on_but_too_old = 1;
+ continue;
+ }
/* now this is an acceptable circ to hand back. but that doesn't
* mean it's the *best* circ to hand back. try to decide.
@@ -213,6 +221,10 @@
best = circ;
}
+ if (!best && intro_going_on_but_too_old)
+ log_info(LD_REND|LD_CIRC, "There is an intro circuit being created "
+ "right now, but it has already taken quite a while. Starting "
+ "one in parallel.");
return best ? TO_ORIGIN_CIRCUIT(best) : NULL;
}
@@ -1436,6 +1448,7 @@
if (retval > 0) {
/* one has already sent the intro. keep waiting. */
+ circuit_t *c = NULL;
tor_assert(introcirc);
log_info(LD_REND, "Intro circ %d present and awaiting ack (rend %d). "
"Stalling. (stream %d sec old)",
@@ -1442,6 +1455,20 @@
introcirc->_base.n_circ_id,
rendcirc ? rendcirc->_base.n_circ_id : 0,
conn_age);
+ /* abort parallel intro circs, if any */
+ for (c = global_circuitlist; c; c = c->next) {
+ if (c->purpose == CIRCUIT_PURPOSE_C_INTRODUCING &&
+ CIRCUIT_IS_ORIGIN(c)) {
+ origin_circuit_t *oc = TO_ORIGIN_CIRCUIT(c);
+ if (oc->rend_data &&
+ !rend_cmp_service_ids(conn->rend_data->onion_address,
+ oc->rend_data->onion_address)) {
+ log_info(LD_REND|LD_CIRC, "Closing introduction circuit that we "
+ "built in parallel.");
+ circuit_mark_for_close(c, END_CIRC_REASON_TIMEOUT);
+ }
+ }
+ }
return 0;
}
Index: /home/karsten/tor/tor-trunk-155-patch3/ChangeLog
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch3/ChangeLog (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch3/ChangeLog (working copy)
@@ -3,6 +3,8 @@
- Now NodeFamily and MyFamily config options allow spaces in
identity fingerprints, so it's easier to paste them in.
Suggested by Lucky Green.
+ - Increase number of server-side introduction points based on number
+ of recent hidden service requests (based on work by Christian Wilms).
Changes in version 0.2.1.6-alpha - 2008-09-30
Index: /home/karsten/tor/tor-trunk-155-patch3/src/or/circuituse.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch3/src/or/circuituse.c (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch3/src/or/circuituse.c (working copy)
@@ -464,7 +464,8 @@
}
/* Third, see if we need any more hidden service (server) circuits. */
- if (num_rend_services() && num_uptime_internal < 3) {
+ if (num_rend_services() &&
+ num_uptime_internal < rend_internal_circuits_needed()) {
flags = (CIRCLAUNCH_NEED_CAPACITY | CIRCLAUNCH_NEED_UPTIME |
CIRCLAUNCH_IS_INTERNAL);
log_info(LD_CIRC,
Index: /home/karsten/tor/tor-trunk-155-patch3/src/or/main.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch3/src/or/main.c (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch3/src/or/main.c (working copy)
@@ -841,6 +841,7 @@
static time_t time_to_recheck_bandwidth = 0;
static time_t time_to_check_for_expired_networkstatus = 0;
static time_t time_to_dump_geoip_stats = 0;
+ static time_t time_to_update_request_history = 0;
or_options_t *options = get_options();
int i;
int have_dir_info;
@@ -1169,6 +1170,14 @@
#define BRIDGE_STATUSFILE_INTERVAL (30*60)
time_to_write_bridge_status_file = now+BRIDGE_STATUSFILE_INTERVAL;
}
+
+ /** 11. Update history of requests to our hidden services, so that
+ * we can better estimate the number of internal circuits. */
+ if (time_to_update_request_history < now) {
+ rend_update_request_history(now);
+#define REND_REQUEST_HISTORY_UPDATE_INTERVAL (5 * 60)
+ time_to_update_request_history = now+REND_REQUEST_HISTORY_UPDATE_INTERVAL;
+ }
}
/** Libevent timer: used to invoke second_elapsed_callback() once per
Index: /home/karsten/tor/tor-trunk-155-patch3/src/or/or.h
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch3/src/or/or.h (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch3/src/or/or.h (working copy)
@@ -4038,6 +4038,10 @@
void rend_service_dump_stats(int severity);
void rend_service_free_all(void);
+int rend_internal_circuits_needed(void);
+void rend_update_request_history(time_t now);
+void rend_service_request_history_free_all(void);
+
/********************************* rendmid.c *******************************/
int rend_mid_establish_intro(or_circuit_t *circ, const char *request,
size_t request_len);
Index: /home/karsten/tor/tor-trunk-155-patch3/src/or/rendservice.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch3/src/or/rendservice.c (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch3/src/or/rendservice.c (working copy)
@@ -831,6 +831,87 @@
} DIGESTMAP_FOREACH_END;
}
+/*
+ * Logic to record requests to our hidden services and set the number
+ * of pre-established internal circuits appropriately.
+ */
+
+/** The duration of our hidden service request history that we use to
+ * better predict the number of internal circuits. */
+#define REND_REQUEST_HISTORY_PERIOD (15 * 60)
+
+/** Number of requests per minute that justify an additional internal
+ * circuit. */
+#define REND_REQUESTS_INTERNAL_CIRCUITS_RATIO 5
+
+/** The maximum number of internal circuits. */
+#define REND_INTERNAL_CIRCUITS_MAX 12
+
+/** History of request to any of our hidden services that is used to help
+ * predict the number of pre-established internal circuits. */
+static smartlist_t *request_history = NULL;
+
+/** Release all the storage held in last_hid_serv_requests.
+ */
+void
+rend_service_request_history_free_all(void)
+{
+ if (!request_history) {
+ return;
+ }
+ SMARTLIST_FOREACH(request_history, time_t *, r, tor_free(r););
+ request_history = NULL;
+}
+
+/** The number of internal circuits that we should hold in stock as a
+ * function of requests. */
+static int internal_circuits_needed = 3;
+
+/** Add a request to one of our hidden services to the request history. */
+static void
+rend_add_request(time_t now)
+{
+ time_t *request_ptr;
+ if (!request_history)
+ request_history = smartlist_create();
+ request_ptr = tor_malloc_zero(sizeof(time_t *));
+ *request_ptr = now;
+ smartlist_add(request_history, request_ptr);
+}
+
+/** Determine the number of internal circuits that we should hold in stock
+ * in the future and prune too old requests. */
+void
+rend_update_request_history(time_t now)
+{
+ time_t cutoff = 0;
+ int num_requests = 0;
+ if (!request_history)
+ return;
+ cutoff = now - REND_REQUEST_HISTORY_PERIOD;
+ SMARTLIST_FOREACH(request_history, time_t *, t, {
+ if (*t < cutoff) {
+ tor_free(t);
+ SMARTLIST_DEL_CURRENT(request_history, t);
+ } else
+ num_requests++;
+ });
+ internal_circuits_needed = 3 + (num_requests /
+ (REND_REQUEST_HISTORY_PERIOD / 60 *
+ REND_REQUESTS_INTERNAL_CIRCUITS_RATIO));
+ if (internal_circuits_needed > REND_INTERNAL_CIRCUITS_MAX)
+ internal_circuits_needed = REND_INTERNAL_CIRCUITS_MAX;
+ log_info(LD_REND, "Setting the number of pre-built internal circuits to %d",
+ internal_circuits_needed);
+}
+
+/** Return the number of internal circuits that we should hold in stock. */
+int
+rend_internal_circuits_needed(void)
+{
+ return internal_circuits_needed;
+}
+
/******
* Handle cells
******/
@@ -1114,6 +1195,10 @@
/* help predict this next time */
rep_hist_note_used_internal(time(NULL), circ_needs_uptime, 1);
+ /* Remember service request to better predict the required number
+ * of internal circuits in the future. */
+ rend_add_request(time(NULL));
+
/* Launch a circuit to alice's chosen rendezvous point.
*/
for (i=0;i<MAX_REND_FAILURES;i++) {
Index: /home/karsten/tor/tor-trunk-155-patch4/ChangeLog
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch4/ChangeLog (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch4/ChangeLog (working copy)
@@ -3,6 +3,9 @@
- Now NodeFamily and MyFamily config options allow spaces in
identity fingerprints, so it's easier to paste them in.
Suggested by Lucky Green.
+ - Start building more server-side introduction circuits than needed
+ (five), pick the first three that succeed, and use the others as
+ general-purpose circuits.
Changes in version 0.2.1.6-alpha - 2008-09-30
Index: /home/karsten/tor/tor-trunk-155-patch4/src/or/circuitlist.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch4/src/or/circuitlist.c (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch4/src/or/circuitlist.c (working copy)
@@ -860,6 +860,28 @@
DIGEST_LEN);
}
+/** Return the number of introduction points that are or have been
+ * established for the given service address and rendezvous version. */
+int
+circuit_get_num_intro_points(const char *query, int rend_version)
+{
+ int num_ipos = 0;
+ circuit_t *circ;
+ for (circ = global_circuitlist; circ; circ = circ->next) {
+ if (!circ->marked_for_close &&
+ circ->state == CIRCUIT_STATE_OPEN &&
+ (circ->purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO ||
+ circ->purpose == CIRCUIT_PURPOSE_S_INTRO)) {
+ origin_circuit_t *oc = TO_ORIGIN_CIRCUIT(circ);
+ if (oc->rend_data &&
+ oc->rend_data->rend_desc_version == rend_version &&
+ !rend_cmp_service_ids(query, oc->rend_data->onion_address))
+ num_ipos++;
+ }
+ }
+ return num_ipos;
+}
+
/** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
* has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
* flags in <b>flags</b>, and if info is defined, does not already use info
Index: /home/karsten/tor/tor-trunk-155-patch4/src/or/or.h
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch4/src/or/or.h (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch4/src/or/or.h (working copy)
@@ -2725,6 +2725,7 @@
const char *digest, uint8_t purpose);
or_circuit_t *circuit_get_rendezvous(const char *cookie);
or_circuit_t *circuit_get_intro_point(const char *digest);
+int circuit_get_num_intro_points(const char *query, int rend_version);
origin_circuit_t *circuit_find_to_cannibalize(uint8_t purpose,
extend_info_t *info, int flags);
void circuit_mark_all_unused_circs(void);
Index: /home/karsten/tor/tor-trunk-155-patch4/src/or/rendservice.c
===================================================================
--- /home/karsten/tor/tor-trunk-155-patch4/src/or/rendservice.c (revision 17050)
+++ /home/karsten/tor/tor-trunk-155-patch4/src/or/rendservice.c (working copy)
@@ -1307,6 +1307,18 @@
goto err;
}
+ /* If we already have enough introduction circuits, redefine this
+ * one as a general circuit. */
+ if (circuit_get_num_intro_points(serviceid,
+ circuit->rend_data->rend_desc_version) > NUM_INTRO_POINTS) {
+ log_info(LD_CIRC|LD_REND, "We have just finished an introduction "
+ "circuit, but we already have enough. Redefining purpose to "
+ "general.");
+ TO_CIRCUIT(circuit)->purpose = CIRCUIT_PURPOSE_C_GENERAL;
+ circuit_has_opened(circuit);
+ return;
+ }
+
log_info(LD_REND,
"Established circuit %d as introduction point for service %s",
circuit->_base.n_circ_id, serviceid);
@@ -1823,9 +1835,12 @@
/* Remember how many introduction circuits we started with. */
prev_intro_nodes = smartlist_len(service->intro_nodes);
-
- /* The directory is now here. Pick three ORs as intro points. */
- for (j=prev_intro_nodes; j < NUM_INTRO_POINTS; ++j) {
+ /* The directory is now here. Pick three ORs as intro points (plus, if
+ * we currently have none at all, two more so that we can pick the first
+ * three afterwards). */
+#define NUM_INTRO_POINTS_INIT (NUM_INTRO_POINTS + 2)
+ for (j=prev_intro_nodes; j < (prev_intro_nodes == 0 ?
+ NUM_INTRO_POINTS_INIT : NUM_INTRO_POINTS); ++j) {
router_crn_flags_t flags = CRN_NEED_UPTIME;
if (get_options()->_AllowInvalid & ALLOW_INVALID_INTRODUCTION)
flags |= CRN_ALLOW_INVALID;
Attachment:
patch-155-1a.txt.sig
Description: Binary data
Attachment:
patch-155-2.txt.sig
Description: Binary data
Attachment:
patch-155-3.txt.sig
Description: Binary data
Attachment:
patch-155-4.txt.sig
Description: Binary data