[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [tor/master] Add an O(1) map from channel->global_identifier to channel
commit 515e1f663ad4a5f1023ef2d2bbcb2de0152d0a47
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
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;
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits