commit 1555876d5f27acaa9326045e33b6e2bfc1013c7f Author: Marek Majkowski <marek@popcount.org> Date: Thu Jun 20 16:56:54 2013 +0100 Fix #9108 - make global_circuitlist a doubly linked list --- changes/bug9108 | 3 ++ src/or/channel.h | 1 - src/or/circuitbuild.c | 2 +- src/or/circuitlist.c | 94 ++++++++++++++++--------------------------------- src/or/circuitlist.h | 4 ++- src/or/circuituse.c | 24 ++++++------- src/or/control.c | 2 +- src/or/onion.c | 1 - src/or/or.h | 4 ++- src/or/relay.c | 2 +- src/or/rendclient.c | 2 +- src/or/rendservice.c | 4 +-- src/or/rephist.c | 2 +- src/or/status.c | 2 +- 14 files changed, 58 insertions(+), 89 deletions(-) diff --git a/changes/bug9108 b/changes/bug9108 new file mode 100644 index 0000000..9d2d3d8 --- /dev/null +++ b/changes/bug9108 @@ -0,0 +1,3 @@ + o Code simplifications and refactoring: + - Make global_circuitlist data structure in circuitlist.c + a doubly-linked list. Bug #9108. diff --git a/src/or/channel.h b/src/or/channel.h index 83d7e90..8f08220 100644 --- a/src/or/channel.h +++ b/src/or/channel.h @@ -10,7 +10,6 @@ #define TOR_CHANNEL_H #include "or.h" -#include "tor_queue.h" #include "circuitmux.h" /* Channel handler function pointer typedefs */ diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 8cdb227..0b5a855 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -2174,7 +2174,7 @@ pathbias_count_circs_in_states(entry_guard_t *guard, int open_circuits = 0; /* Count currently open circuits. Give them the benefit of the doubt. */ - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { origin_circuit_t *ocirc = NULL; if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */ circ->marked_for_close) /* already counted */ diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index 1912b91..6bf1859 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -36,7 +36,8 @@ /********* START VARIABLES **********/ /** A global list of all circuits at this hop. */ -circuit_t *global_circuitlist=NULL; +struct global_circuitlist_s global_circuitlist = + TOR_LIST_HEAD_INITIALIZER(global_circuitlist); /** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */ static smartlist_t *circuits_pending_chans = NULL; @@ -370,21 +371,6 @@ circuit_set_state(circuit_t *circ, uint8_t state) circ->state = state; } -/** Add <b>circ</b> to the global list of circuits. This is called only from - * within circuit_new. - */ -static void -circuit_add(circuit_t *circ) -{ - if (!global_circuitlist) { /* first one */ - global_circuitlist = circ; - circ->next = NULL; - } else { - circ->next = global_circuitlist; - global_circuitlist = circ; - } -} - /** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for * the given connection. */ void @@ -442,33 +428,17 @@ circuit_count_pending_on_channel(channel_t *chan) void circuit_close_all_marked(void) { - circuit_t *tmp,*m; - - while (global_circuitlist && global_circuitlist->marked_for_close) { - tmp = global_circuitlist->next; - circuit_free(global_circuitlist); - global_circuitlist = tmp; - } - - tmp = global_circuitlist; - while (tmp && tmp->next) { - if (tmp->next->marked_for_close) { - m = tmp->next->next; - circuit_free(tmp->next); - tmp->next = m; - /* Need to check new tmp->next; don't advance tmp. */ - } else { - /* Advance tmp. */ - tmp = tmp->next; - } - } + circuit_t *circ, *tmp; + TOR_LIST_FOREACH_SAFE(circ, &global_circuitlist, head, tmp) + if (circ->marked_for_close) + circuit_free(circ); } /** Return the head of the global linked list of circuits. */ -circuit_t * +struct global_circuitlist_s * circuit_get_global_list_(void) { - return global_circuitlist; + return &global_circuitlist; } /** Function to make circ-\>state human-readable */ @@ -684,7 +654,7 @@ init_circuit_base(circuit_t *circ) circ->package_window = circuit_initial_package_window(); circ->deliver_window = CIRCWINDOW_START; - circuit_add(circ); + TOR_LIST_INSERT_HEAD(&global_circuitlist, circ, head); } /** Allocate space for a new circuit, initializing with <b>p_circ_id</b> @@ -802,6 +772,8 @@ circuit_free(circuit_t *circ) extend_info_free(circ->n_hop); tor_free(circ->n_chan_create_cell); + TOR_LIST_REMOVE(circ, head); + /* Remove from map. */ circuit_set_n_circid_chan(circ, 0, NULL); @@ -837,11 +809,11 @@ circuit_free_cpath(crypt_path_t *cpath) void circuit_free_all(void) { - circuit_t *next; - while (global_circuitlist) { - next = global_circuitlist->next; - if (! CIRCUIT_IS_ORIGIN(global_circuitlist)) { - or_circuit_t *or_circ = TO_OR_CIRCUIT(global_circuitlist); + circuit_t *tmp, *tmp2; + + TOR_LIST_FOREACH_SAFE(tmp, &global_circuitlist, head, tmp2) { + if (! CIRCUIT_IS_ORIGIN(tmp)) { + or_circuit_t *or_circ = TO_OR_CIRCUIT(tmp); while (or_circ->resolving_streams) { edge_connection_t *next_conn; next_conn = or_circ->resolving_streams->next_stream; @@ -849,8 +821,7 @@ circuit_free_all(void) or_circ->resolving_streams = next_conn; } } - circuit_free(global_circuitlist); - global_circuitlist = next; + circuit_free(tmp); } smartlist_free(circuits_pending_chans); @@ -920,7 +891,7 @@ circuit_dump_by_conn(connection_t *conn, int severity) circuit_t *circ; edge_connection_t *tmpconn; - for (circ = global_circuitlist; circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { circid_t n_circ_id = circ->n_circ_id, p_circ_id = 0; if (circ->marked_for_close) { @@ -984,7 +955,7 @@ circuit_dump_by_chan(channel_t *chan, int severity) tor_assert(chan); - for (circ = global_circuitlist; circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { circid_t n_circ_id = circ->n_circ_id, p_circ_id = 0; if (circ->marked_for_close) { @@ -1025,7 +996,7 @@ origin_circuit_t * circuit_get_by_global_id(uint32_t id) { circuit_t *circ; - for (circ=global_circuitlist;circ;circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { if (CIRCUIT_IS_ORIGIN(circ) && TO_ORIGIN_CIRCUIT(circ)->global_identifier == id) { if (circ->marked_for_close) @@ -1088,7 +1059,7 @@ circuit_get_by_circid_channel_impl(circid_t circ_id, channel_t *chan, /* We comment it out because coverity complains otherwise. { circuit_t *circ; - for (circ=global_circuitlist;circ;circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { if (! CIRCUIT_IS_ORIGIN(circ)) { or_circuit_t *or_circ = TO_OR_CIRCUIT(circ); if (or_circ->p_chan == chan && or_circ->p_circ_id == circ_id) { @@ -1170,7 +1141,7 @@ circuit_unlink_all_from_channel(channel_t *chan, int reason) channel_unlink_all_circuits(chan); - for (circ = global_circuitlist; circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { int mark = 0; if (circ->n_chan == chan) { circuit_set_n_circid_chan(circ, 0, NULL); @@ -1206,8 +1177,7 @@ origin_circuit_t * circuit_get_ready_rend_circ_by_rend_data(const rend_data_t *rend_data) { circuit_t *circ; - - for (circ = global_circuitlist; circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { if (!circ->marked_for_close && circ->purpose == CIRCUIT_PURPOSE_C_REND_READY) { origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); @@ -1235,11 +1205,11 @@ circuit_get_next_by_pk_and_purpose(origin_circuit_t *start, circuit_t *circ; tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose)); if (start == NULL) - circ = global_circuitlist; + circ = TOR_LIST_FIRST(&global_circuitlist); else - circ = TO_CIRCUIT(start)->next; + circ = TOR_LIST_NEXT(TO_CIRCUIT(start), head); - for ( ; circ; circ = circ->next) { + for ( ; circ; circ = TOR_LIST_NEXT(circ, head)) { if (circ->marked_for_close) continue; if (circ->purpose != purpose) @@ -1262,7 +1232,7 @@ circuit_get_by_rend_token_and_purpose(uint8_t purpose, const char *token, size_t len) { circuit_t *circ; - for (circ = global_circuitlist; circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { if (! circ->marked_for_close && circ->purpose == purpose && tor_memeq(TO_OR_CIRCUIT(circ)->rend_token, token, len)) @@ -1324,7 +1294,7 @@ circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info, "capacity %d, internal %d", purpose, need_uptime, need_capacity, internal); - for (circ_=global_circuitlist; circ_; circ_ = circ_->next) { + TOR_LIST_FOREACH(circ_, &global_circuitlist, head) { if (CIRCUIT_IS_ORIGIN(circ_) && circ_->state == CIRCUIT_STATE_OPEN && !circ_->marked_for_close && @@ -1414,8 +1384,7 @@ void circuit_mark_all_unused_circs(void) { circuit_t *circ; - - for (circ=global_circuitlist; circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { if (CIRCUIT_IS_ORIGIN(circ) && !circ->marked_for_close && !circ->timestamp_dirty) @@ -1434,8 +1403,7 @@ void circuit_mark_all_dirty_circs_as_unusable(void) { circuit_t *circ; - - for (circ=global_circuitlist; circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, &global_circuitlist, head) { if (CIRCUIT_IS_ORIGIN(circ) && !circ->marked_for_close && circ->timestamp_dirty) { @@ -1695,7 +1663,7 @@ circuits_handle_oom(size_t current_allocation) /* This algorithm itself assumes that you've got enough memory slack * to actually run it. */ - for (circ = global_circuitlist; circ; circ = circ->next) + TOR_LIST_FOREACH(circ, &global_circuitlist, head) smartlist_add(circlist, circ); /* This is O(n log n); there are faster algorithms we could use instead. diff --git a/src/or/circuitlist.h b/src/or/circuitlist.h index 03f678c..4726b3b 100644 --- a/src/or/circuitlist.h +++ b/src/or/circuitlist.h @@ -12,7 +12,9 @@ #ifndef TOR_CIRCUITLIST_H #define TOR_CIRCUITLIST_H -circuit_t * circuit_get_global_list_(void); +TOR_LIST_HEAD(global_circuitlist_s, circuit_t); + +struct global_circuitlist_s* circuit_get_global_list_(void); const char *circuit_state_to_string(int state); const char *circuit_purpose_to_controller_string(uint8_t purpose); const char *circuit_purpose_to_controller_hs_state_string(uint8_t purpose); diff --git a/src/or/circuituse.c b/src/or/circuituse.c index 07bdbe6..fdafa3f 100644 --- a/src/or/circuituse.c +++ b/src/or/circuituse.c @@ -280,7 +280,7 @@ circuit_get_best(const entry_connection_t *conn, tor_gettimeofday(&now); - for (circ=circuit_get_global_list_();circ;circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { origin_circuit_t *origin_circ; if (!CIRCUIT_IS_ORIGIN(circ)) continue; @@ -321,7 +321,7 @@ count_pending_general_client_circuits(void) int count = 0; - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { if (circ->marked_for_close || circ->state == CIRCUIT_STATE_OPEN || circ->purpose != CIRCUIT_PURPOSE_C_GENERAL || @@ -369,7 +369,7 @@ circuit_conforms_to_options(const origin_circuit_t *circ, void circuit_expire_building(void) { - circuit_t *victim, *next_circ = circuit_get_global_list_(); + circuit_t *victim, *next_circ; /* circ_times.timeout_ms and circ_times.close_ms are from * circuit_build_times_get_initial_timeout() if we haven't computed * custom timeouts yet */ @@ -387,10 +387,9 @@ circuit_expire_building(void) * we want to be more lenient with timeouts, in case the * user has relocated and/or changed network connections. * See bug #3443. */ - while (next_circ) { + TOR_LIST_FOREACH(next_circ, circuit_get_global_list_(), head) { if (!CIRCUIT_IS_ORIGIN(next_circ) || /* didn't originate here */ next_circ->marked_for_close) { /* don't mess with marked circs */ - next_circ = next_circ->next; continue; } @@ -402,9 +401,7 @@ circuit_expire_building(void) any_opened_circs = 1; break; } - next_circ = next_circ->next; } - next_circ = circuit_get_global_list_(); #define SET_CUTOFF(target, msec) do { \ long ms = tor_lround(msec); \ @@ -475,10 +472,9 @@ circuit_expire_building(void) MAX(circ_times.close_ms*2 + 1000, options->SocksTimeout * 1000)); - while (next_circ) { + TOR_LIST_FOREACH(next_circ, circuit_get_global_list_(), head) { struct timeval cutoff; victim = next_circ; - next_circ = next_circ->next; if (!CIRCUIT_IS_ORIGIN(victim) || /* didn't originate here */ victim->marked_for_close) /* don't mess with marked circs */ continue; @@ -812,7 +808,7 @@ circuit_stream_is_being_handled(entry_connection_t *conn, get_options()->LongLivedPorts, conn ? conn->socks_request->port : port); - for (circ=circuit_get_global_list_();circ;circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { if (CIRCUIT_IS_ORIGIN(circ) && !circ->marked_for_close && circ->purpose == CIRCUIT_PURPOSE_C_GENERAL && @@ -863,7 +859,7 @@ circuit_predict_and_launch_new(void) int flags = 0; /* First, count how many of each type of circuit we have already. */ - for (circ=circuit_get_global_list_();circ;circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { cpath_build_state_t *build_state; origin_circuit_t *origin_circ; if (!CIRCUIT_IS_ORIGIN(circ)) @@ -1087,7 +1083,7 @@ circuit_expire_old_circuits_clientside(void) cutoff.tv_sec -= get_options()->CircuitIdleTimeout; } - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { if (circ->marked_for_close || !CIRCUIT_IS_ORIGIN(circ)) continue; /* If the circuit has been dirty for too long, and there are no streams @@ -1170,7 +1166,7 @@ circuit_expire_old_circuits_serverside(time_t now) or_circuit_t *or_circ; time_t cutoff = now - IDLE_ONE_HOP_CIRC_TIMEOUT; - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { if (circ->marked_for_close || CIRCUIT_IS_ORIGIN(circ)) continue; or_circ = TO_OR_CIRCUIT(circ); @@ -1217,7 +1213,7 @@ circuit_enough_testing_circs(void) if (have_performed_bandwidth_test) return 1; - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { if (!circ->marked_for_close && CIRCUIT_IS_ORIGIN(circ) && circ->purpose == CIRCUIT_PURPOSE_TESTING && circ->state == CIRCUIT_STATE_OPEN) diff --git a/src/or/control.c b/src/or/control.c index cc917c4..a4c674f 100644 --- a/src/or/control.c +++ b/src/or/control.c @@ -1928,7 +1928,7 @@ getinfo_helper_events(control_connection_t *control_conn, if (!strcmp(question, "circuit-status")) { circuit_t *circ_; smartlist_t *status = smartlist_new(); - for (circ_ = circuit_get_global_list_(); circ_; circ_ = circ_->next) { + TOR_LIST_FOREACH(circ_, circuit_get_global_list_(), head) { origin_circuit_t *circ; char *circdesc; const char *state; diff --git a/src/or/onion.c b/src/or/onion.c index d4a6502..5542854 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -21,7 +21,6 @@ #include "relay.h" #include "rephist.h" #include "router.h" -#include "tor_queue.h" /** Type for a linked list of circuits that are waiting for a free CPU worker * to process a waiting onion handshake. */ diff --git a/src/or/or.h b/src/or/or.h index 67478a1..94fbe43 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -99,6 +99,7 @@ #include "ht.h" #include "replaycache.h" #include "crypto_curve25519.h" +#include "tor_queue.h" /* These signals are defined to help handle_control_signal work. */ @@ -2853,7 +2854,8 @@ typedef struct circuit_t { /** Unique ID for measuring tunneled network status requests. */ uint64_t dirreq_id; - struct circuit_t *next; /**< Next circuit in linked list of all circuits. */ + /** Next circuit in linked list of all circuits (global_circuitlist). */ + TOR_LIST_ENTRY(circuit_t) head; /** Next circuit in the doubly-linked ring of circuits waiting to add * cells to n_conn. NULL if we have no cells pending, or if we're not diff --git a/src/or/relay.c b/src/or/relay.c index 251d3ff..2c2a887 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -2111,7 +2111,7 @@ dump_cell_pool_usage(int severity) circuit_t *c; int n_circs = 0; int n_cells = 0; - for (c = circuit_get_global_list_(); c; c = c->next) { + TOR_LIST_FOREACH(c, circuit_get_global_list_(), head) { n_cells += c->n_chan_cells.n; if (!CIRCUIT_IS_ORIGIN(c)) n_cells += TO_OR_CIRCUIT(c)->p_chan_cells.n; diff --git a/src/or/rendclient.c b/src/or/rendclient.c index 7115bf2..ea4512d 100644 --- a/src/or/rendclient.c +++ b/src/or/rendclient.c @@ -358,7 +358,7 @@ rend_client_close_other_intros(const char *onion_address) { circuit_t *c; /* abort parallel intro circs, if any */ - for (c = circuit_get_global_list_(); c; c = c->next) { + TOR_LIST_FOREACH(c, circuit_get_global_list_(), head) { if ((c->purpose == CIRCUIT_PURPOSE_C_INTRODUCING || c->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) && !c->marked_for_close && CIRCUIT_IS_ORIGIN(c)) { diff --git a/src/or/rendservice.c b/src/or/rendservice.c index a8f63dd..7f77191 100644 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@ -543,7 +543,7 @@ rend_config_services(const or_options_t *options, int validate_only) /* XXXX it would be nicer if we had a nicer abstraction to use here, * so we could just iterate over the list of services to close, but * once again, this isn't critical-path code. */ - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { if (!circ->marked_for_close && circ->state == CIRCUIT_STATE_OPEN && (circ->purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO || @@ -2381,7 +2381,7 @@ count_established_intro_points(const char *query) { int num_ipos = 0; circuit_t *circ; - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { if (!circ->marked_for_close && circ->state == CIRCUIT_STATE_OPEN && (circ->purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO || diff --git a/src/or/rephist.c b/src/or/rephist.c index c84322a..0943a34 100644 --- a/src/or/rephist.c +++ b/src/or/rephist.c @@ -2599,7 +2599,7 @@ rep_hist_buffer_stats_write(time_t now) goto done; /* Not ready to write */ /* Add open circuits to the history. */ - for (circ = circuit_get_global_list_(); circ; circ = circ->next) { + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) { rep_hist_buffer_stats_add_circ(circ, now); } diff --git a/src/or/status.c b/src/or/status.c index d239e6e..6fe2f67 100644 --- a/src/or/status.c +++ b/src/or/status.c @@ -23,7 +23,7 @@ count_circuits(void) circuit_t *circ; int nr=0; - for (circ = circuit_get_global_list_(); circ; circ = circ->next) + TOR_LIST_FOREACH(circ, circuit_get_global_list_(), head) nr++; return nr;