commit 515e1f663ad4a5f1023ef2d2bbcb2de0152d0a47 Author: Nick Mathewson nickm@torproject.org Date: Sat Jan 23 16:30:44 2016 -0500

Add an O(1) map from channel->global_identifier to channel --- changes/fast_channel_lookup | 2 ++ src/or/channel.c | 53 +++++++++++++++++++++++++++++++++++---------- src/or/channel.h | 5 ++++- 3 files changed, 47 insertions(+), 13 deletions(-)

diff --git a/changes/fast_channel_lookup b/changes/fast_channel_lookup new file mode 100644 index 0000000..7d60fe6 --- /dev/null +++ b/changes/fast_channel_lookup @@ -0,0 +1,2 @@ + o Minor features: + - Add an O(1) implementation of channel_find_by_global_id(). diff --git a/src/or/channel.c b/src/or/channel.c index 45f1602..a1ccb2c 100644 --- a/src/or/channel.c +++ b/src/or/channel.c @@ -84,6 +84,27 @@ static smartlist_t *active_listeners = NULL; /* All channel_listener_t instances in LISTENING state */ static smartlist_t *finished_listeners = NULL;

+ +/** Map from channel->global_identifier to channel. Contains the same + * elements as all_channels. */ +HT_HEAD(channel_gid_map, channel_s) channel_gid_map = HT_INITIALIZER(); + +static unsigned +channel_id_hash(const channel_t *chan) +{ + return (unsigned) chan->global_identifier; +} +static int +channel_id_eq(const channel_t *a, const channel_t *b) +{ + return a->global_identifier == b->global_identifier; +} +HT_PROTOTYPE(channel_gid_map, channel_s, gidmap_node, + channel_id_hash, channel_id_eq); +HT_GENERATE2(channel_gid_map, channel_s, gidmap_node, + channel_id_hash, channel_id_eq, + 0.6, tor_reallocarray_, tor_free_); + /* Counter for ID numbers */ static uint64_t n_channels_allocated = 0; /* @@ -429,6 +450,7 @@ void channel_register(channel_t *chan) { tor_assert(chan); + tor_assert(chan->global_identifier);

/* No-op if already registered */ if (chan->registered) return; @@ -443,6 +465,8 @@ channel_register(channel_t *chan) /* Make sure we have all_channels, then add it */ if (!all_channels) all_channels = smartlist_new(); smartlist_add(all_channels, chan); + channel_t *oldval = HT_REPLACE(channel_gid_map, &channel_gid_map, chan); + tor_assert(! oldval);

/* Is it finished? */ if (CHANNEL_FINISHED(chan)) { @@ -498,7 +522,9 @@ channel_unregister(channel_t *chan) }

/* Get it out of all_channels */ - if (all_channels) smartlist_remove(all_channels, chan); + if (all_channels) smartlist_remove(all_channels, chan); + channel_t *oldval = HT_REMOVE(channel_gid_map, &channel_gid_map, chan); + tor_assert(oldval == NULL || oldval == chan);

/* Mark it as unregistered */ chan->registered = 0; @@ -533,7 +559,7 @@ channel_listener_register(channel_listener_t *chan_l) channel_listener_state_to_string(chan_l->state), chan_l->state);

- /* Make sure we have all_channels, then add it */ + /* Make sure we have all_listeners, then add it */ if (!all_listeners) all_listeners = smartlist_new(); smartlist_add(all_listeners, chan_l);

@@ -578,7 +604,7 @@ channel_listener_unregister(channel_listener_t *chan_l) if (active_listeners) smartlist_remove(active_listeners, chan_l); }

- /* Get it out of all_channels */ + /* Get it out of all_listeners */ if (all_listeners) smartlist_remove(all_listeners, chan_l);

/* Mark it as unregistered */ @@ -719,15 +745,13 @@ channel_remove_from_digest_map(channel_t *chan) channel_t * channel_find_by_global_id(uint64_t global_identifier) { + channel_t lookup; channel_t *rv = NULL;

- if (all_channels && smartlist_len(all_channels) > 0) { - SMARTLIST_FOREACH_BEGIN(all_channels, channel_t *, curr) { - if (curr->global_identifier == global_identifier) { - rv = curr; - break; - } - } SMARTLIST_FOREACH_END(curr); + lookup.global_identifier = global_identifier; + rv = HT_FIND(channel_gid_map, &channel_gid_map, &lookup); + if (rv) { + tor_assert(rv->global_identifier == global_identifier); }

return rv; @@ -822,7 +846,7 @@ channel_init(channel_t *chan) tor_assert(chan);

/* Assign an ID and bump the counter */ - chan->global_identifier = n_channels_allocated++; + chan->global_identifier = ++n_channels_allocated;

/* Init timestamp */ chan->timestamp_last_had_circuits = time(NULL); @@ -861,7 +885,7 @@ channel_init_listener(channel_listener_t *chan_l) tor_assert(chan_l);

/* Assign an ID and bump the counter */ - chan_l->global_identifier = n_channels_allocated++; + chan_l->global_identifier = ++n_channels_allocated;

/* Timestamp it */ channel_listener_timestamp_created(chan_l); @@ -3232,6 +3256,11 @@ channel_free_all(void) /* Geez, anything still left over just won't die ... let it leak then */ HT_CLEAR(channel_idmap, &channel_identity_map);

+ /* Same with channel_gid_map */ + log_debug(LD_CHANNEL, + "Freeing channel_gid_map"); + HT_CLEAR(channel_gid_map, &channel_gid_map); + log_debug(LD_CHANNEL, "Done cleaning up after channels"); } diff --git a/src/or/channel.h b/src/or/channel.h index 26aa93b..0b8f599 100644 --- a/src/or/channel.h +++ b/src/or/channel.h @@ -34,11 +34,14 @@ struct channel_s { /** Magic number for type-checking cast macros */ uint32_t magic;

+ /** List entry for hashtable for global-identifier lookup. */ + HT_ENTRY(channel_s) gidmap_node; + /** Current channel state */ channel_state_t state;

/** Globally unique ID number for a channel over the lifetime of a Tor - * process. + * process. This may not be 0. */ uint64_t global_identifier;