[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[or-cvs] [tor/master 01/15] Implement a basic node and nodelist type
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date: Tue, 28 Sep 2010 13:29:31 -0400
Subject: Implement a basic node and nodelist type
Commit: fe309e7ad633bee36e175e600f0b9a0ac18cf981
The node_t type is meant to serve two key functions:
1) Abstracting difference between routerinfo_t and microdesc_t
so that clients can use microdesc_t instead of routerinfo_t.
2) Being a central place to hold mutable state about nodes
formerly held in routerstatus_t and routerinfo_t.
This patch implements a nodelist type that holds a node for every
router that we would consider using.
---
src/common/container.c | 1 -
src/or/Makefile.am | 3 +-
src/or/main.c | 11 ++
src/or/microdesc.c | 7 +
src/or/networkstatus.c | 3 +
src/or/nodelist.c | 328 ++++++++++++++++++++++++++++++++++++++++++++++++
src/or/nodelist.h | 28 ++++
src/or/or.h | 13 ++
src/or/routerlist.c | 7 +
9 files changed, 399 insertions(+), 2 deletions(-)
create mode 100644 src/or/nodelist.c
create mode 100644 src/or/nodelist.h
diff --git a/src/common/container.c b/src/common/container.c
index 72f3470..0a95f33 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -268,7 +268,6 @@ smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
/** Remove the <b>idx</b>th element of sl; if idx is not the last
* element, swap the last element of sl into the <b>idx</b>th space.
- * Return the old value of the <b>idx</b>th element.
*/
void
smartlist_del(smartlist_t *sl, int idx)
diff --git a/src/or/Makefile.am b/src/or/Makefile.am
index 9d8fb66..ef9c990 100644
--- a/src/or/Makefile.am
+++ b/src/or/Makefile.am
@@ -21,7 +21,7 @@ libtor_a_SOURCES = buffers.c circuitbuild.c circuitlist.c \
cpuworker.c directory.c dirserv.c dirvote.c \
dns.c dnsserv.c geoip.c hibernate.c main.c $(tor_platform_source) \
microdesc.c \
- networkstatus.c onion.c policies.c \
+ networkstatus.c nodelist.c onion.c policies.c \
reasons.c relay.c rendcommon.c rendclient.c rendmid.c \
rendservice.c rephist.c router.c routerlist.c routerparse.c \
$(evdns_source) config_codedigest.c
@@ -56,6 +56,7 @@ noinst_HEADERS = buffers.h circuitbuild.h circuitlist.h circuituse.h \
command.h config.h connection_edge.h connection.h connection_or.h \
control.h cpuworker.h directory.h dirserv.h dirvote.h dns.h \
dnsserv.h geoip.h hibernate.h main.h microdesc.h networkstatus.h \
+ nodelist.h \
ntmain.h onion.h policies.h reasons.h relay.h rendclient.h \
rendcommon.h rendmid.h rendservice.h rephist.h router.h routerlist.h \
routerparse.h or.h eventdns.h eventdns_tor.h micro-revision.i
diff --git a/src/or/main.c b/src/or/main.c
index ddd5da3..072fd93 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -33,6 +33,7 @@
#include "main.h"
#include "microdesc.h"
#include "networkstatus.h"
+#include "nodelist.h"
#include "ntmain.h"
#include "onion.h"
#include "policies.h"
@@ -1039,6 +1040,15 @@ run_scheduled_events(time_t now)
*/
consider_hibernation(now);
+ /* XXXX NM REMOVE THIS. XXXX NM XXXX NM XXXX NM*/
+ {
+ static time_t nl_check_time = 0;
+ if (nl_check_time <= now) {
+ nodelist_assert_ok();
+ nl_check_time = now + 30;
+ }
+ }
+
/* 0b. If we've deferred a signewnym, make sure it gets handled
* eventually. */
if (signewnym_is_pending &&
@@ -2205,6 +2215,7 @@ tor_free_all(int postfork)
connection_free_all();
buf_shrink_freelists(1);
memarea_clear_freelist();
+ nodelist_free_all();
microdesc_free_all();
if (!postfork) {
config_free_all();
diff --git a/src/or/microdesc.c b/src/or/microdesc.c
index 2752d15..19970aa 100644
--- a/src/or/microdesc.c
+++ b/src/or/microdesc.c
@@ -5,6 +5,7 @@
#include "config.h"
#include "directory.h"
#include "microdesc.h"
+#include "nodelist.h"
#include "routerparse.h"
#include "networkstatus.h"
#include "routerlist.h"
@@ -249,6 +250,12 @@ microdescs_add_list_to_cache(microdesc_cache_t *cache,
microdesc_cache_rebuild(cache);
}
+ {
+ networkstatus_t *ns = networkstatus_get_latest_consensus();
+ if (ns && ns->flavor == FLAV_MICRODESC)
+ SMARTLIST_FOREACH(added, microdesc_t *, md, nodelist_add_microdesc(md));
+ }
+
return added;
}
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index cba02f3..c41bcab 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -22,6 +22,7 @@
#include "main.h"
#include "microdesc.h"
#include "networkstatus.h"
+#include "nodelist.h"
#include "relay.h"
#include "router.h"
#include "routerlist.h"
@@ -1833,6 +1834,8 @@ networkstatus_set_current_consensus(const char *consensus,
/* XXXXNM Microdescs: needs a non-ns variant. */
update_consensus_networkstatus_fetch_time(now);
+ nodelist_set_consensus(current_consensus);
+
dirvote_recalculate_timing(options, now);
routerstatus_list_update_named_server_map();
cell_ewma_set_scale_factor(options, current_consensus);
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
new file mode 100644
index 0000000..9c8714c
--- /dev/null
+++ b/src/or/nodelist.c
@@ -0,0 +1,328 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2010, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or.h"
+#include "nodelist.h"
+#include "microdesc.h"
+#include "networkstatus.h"
+#include "routerlist.h"
+
+#include <string.h>
+
+static void nodelist_drop_node(node_t *node);
+static void node_free(node_t *node);
+
+/** A nodelist_t holds a node_t object for every router we're "willing to use
+ * for something". Specifically, it should hold a node_t for every node that
+ * is currently in the routerlist, or currently in the consensus we're using.
+ */
+typedef struct nodelist_t {
+ /* A list of all the nodes. */
+ smartlist_t *nodes;
+ /* Hash table to map from node ID digest to node. */
+ HT_HEAD(nodelist_map, node_t) nodes_by_id;
+} nodelist_t;
+
+static INLINE unsigned int
+node_id_hash(const node_t *node)
+{
+#if SIZEOF_INT == 4
+ const uint32_t *p = (const uint32_t*)node->identity;
+ return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
+#elif SIZEOF_INT == 8
+ const uint64_t *p = (const uint32_t*)node->identity;
+ const uint32_t *p32 = (const uint32_t*)node->identity;
+ return p[0] ^ p[1] ^ p32[4];
+#endif
+}
+
+static INLINE unsigned int
+node_id_eq(const node_t *node1, const node_t *node2)
+{
+ return 0 == memcmp(node1->identity, node2->identity, DIGEST_LEN);
+}
+
+HT_PROTOTYPE(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq);
+HT_GENERATE(nodelist_map, node_t, ht_ent, node_id_hash, node_id_eq,
+ 0.6, malloc, realloc, free);
+
+/** The global nodelist. */
+static nodelist_t *the_nodelist=NULL;
+
+/** Create an empty nodelist if we haven't done so already. */
+static void
+init_nodelist(void)
+{
+ if (PREDICT_UNLIKELY(the_nodelist == NULL)) {
+ the_nodelist = tor_malloc_zero(sizeof(nodelist_t));
+ HT_INIT(nodelist_map, &the_nodelist->nodes_by_id);
+ the_nodelist->nodes = smartlist_create();
+ }
+}
+
+/** Return the node_t whose identity is <b>identity_digest</b>, or NULL
+ * if no such node exists. */
+node_t *
+node_get_by_id(const char *identity_digest)
+{
+ node_t search, *node;
+ if (PREDICT_UNLIKELY(the_nodelist == NULL))
+ return NULL;
+
+ memcpy(&search.identity, identity_digest, DIGEST_LEN);
+ node = HT_FIND(nodelist_map, &the_nodelist->nodes_by_id, &search);
+ return node;
+}
+
+/** Internal: return the node_t whose identity_digest is
+ * <b>identity_digest</b>. If none exists, create a new one, add it to the
+ * nodelist, and return it.
+ *
+ * Requires that the nodelist be initialized.
+ */
+static node_t *
+node_get_or_create(const char *identity_digest)
+{
+ node_t *node;
+
+ if ((node = node_get_by_id(identity_digest)))
+ return node;
+
+ node = tor_malloc_zero(sizeof(node_t));
+ memcpy(node->identity, identity_digest, DIGEST_LEN);
+ HT_INSERT(nodelist_map, &the_nodelist->nodes_by_id, node);
+
+ smartlist_add(the_nodelist->nodes, node);
+ node->nodelist_idx = smartlist_len(the_nodelist->nodes) - 1;
+
+ return node;
+}
+
+/** Add <b>ri</b> to the nodelist. */
+node_t *
+nodelist_add_routerinfo(routerinfo_t *ri)
+{
+ node_t *node;
+ init_nodelist();
+ node = node_get_or_create(ri->cache_info.identity_digest);
+ node->ri = ri;
+ return node;
+}
+
+/** Set the appropriate node_t to use <b>md</b> as its microdescriptor.
+ *
+ * Called when a new microdesc has arrived and the usable consensus flavor
+ * is "microdesc".
+ **/
+node_t *
+nodelist_add_microdesc(microdesc_t *md)
+{
+ networkstatus_t *ns =
+ networkstatus_get_latest_consensus_by_flavor(FLAV_MICRODESC);
+ routerstatus_t *rs;
+ node_t *node;
+ if (ns == NULL)
+ return NULL;
+ init_nodelist();
+
+ /* Microdescriptors don't carry an identity digest, so we need to figure
+ * it out by looking up the routerstatus. */
+ rs = router_get_consensus_status_by_descriptor_digest(ns, md->digest);
+ if (rs == NULL)
+ return NULL;
+ node = node_get_by_id(rs->identity_digest);
+ if (node)
+ node->md = md;
+ return node;
+}
+
+/** Tell the nodelist that the current usable consensus to <b>ns</b>.
+ * This makes the nodelist change all of the routerstatus entries for
+ * the nodes, drop nodes that no longer have enough info to get used,
+ * and grab microdescriptors into nodes as appropriate.
+ */
+void
+nodelist_set_consensus(networkstatus_t *ns)
+{
+ init_nodelist();
+
+ SMARTLIST_FOREACH(the_nodelist->nodes, node_t *, node,
+ node->rs = NULL);
+
+ SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
+ node_t *node = node_get_or_create(rs->identity_digest);
+ node->rs = rs;
+ if (ns->flavor == FLAV_MICRODESC) {
+ if (node->md == NULL ||
+ 0!=memcmp(node->md->digest,rs->descriptor_digest,DIGEST256_LEN)) {
+ node->md = microdesc_cache_lookup_by_digest256(NULL,
+ rs->descriptor_digest);
+ }
+ }
+ } SMARTLIST_FOREACH_END(rs);
+ nodelist_purge();
+}
+
+/** Helper: return true iff a node has a usable amount of information*/
+static INLINE int
+node_is_usable(const node_t *node)
+{
+ return (node->rs) || (node->ri);
+}
+
+/** Tell the nodelist that <b>md</b> is no longer a microdescriptor for the
+ * node with <b>identity_digest</b>. */
+void
+nodelist_remove_microdesc(const char *identity_digest, microdesc_t *md)
+{
+ node_t *node = node_get_by_id(identity_digest);
+ if (node && node->md == md)
+ node->md = NULL;
+}
+
+/** Tell the nodelist that <b>ri</b> is no longer in the routerlist. */
+void
+nodelist_remove_routerinfo(routerinfo_t *ri)
+{
+ node_t *node = node_get_by_id(ri->cache_info.identity_digest);
+ if (node && node->ri == ri) {
+ node->ri = NULL;
+ if (! node_is_usable(node)) {
+ nodelist_drop_node(node);
+ node_free(node);
+ }
+ }
+}
+
+/** Remove <b>node</b> from the nodelist. (Asserts that it was there to begin
+ * with.) */
+static void
+nodelist_drop_node(node_t *node)
+{
+ node_t *tmp;
+ int idx;
+ tmp = HT_REMOVE(nodelist_map, &the_nodelist->nodes_by_id, node);
+ tor_assert(tmp == node);
+
+ idx = node->nodelist_idx;
+ tor_assert(idx >= 0);
+
+ tor_assert(node == smartlist_get(the_nodelist->nodes, idx));
+ smartlist_del(the_nodelist->nodes, idx);
+ if (idx < smartlist_len(the_nodelist->nodes)) {
+ tmp = smartlist_get(the_nodelist->nodes, idx);
+ tmp->nodelist_idx = idx;
+ }
+ node->nodelist_idx = -1;
+}
+
+/** Release storage held by <b>node</b> */
+static void
+node_free(node_t *node)
+{
+ if (!node)
+ return;
+ tor_assert(node->nodelist_idx == -1);
+ tor_free(node);
+}
+
+/** Remove all entries from the nodelist that don't have enough info to be
+ * usable for anything. */
+void
+nodelist_purge(void)
+{
+ node_t **iter;
+ if (PREDICT_UNLIKELY(the_nodelist == NULL))
+ return;
+
+ for (iter = HT_START(nodelist_map, &the_nodelist->nodes_by_id); iter; ) {
+ node_t *node = *iter;
+
+ if (node_is_usable(node)) {
+ iter = HT_NEXT(nodelist_map, &the_nodelist->nodes_by_id, iter);
+ } else {
+ iter = HT_NEXT_RMV(nodelist_map, &the_nodelist->nodes_by_id, iter);
+ nodelist_drop_node(node);
+ node_free(node);
+ }
+ }
+
+}
+
+/** Release all storage held by the nodelist. */
+void
+nodelist_free_all(void)
+{
+ if (PREDICT_UNLIKELY(the_nodelist == NULL))
+ return;
+
+ HT_CLEAR(nodelist_map, &the_nodelist->nodes_by_id);
+ SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
+ node->nodelist_idx = -1;
+ node_free(node);
+ } SMARTLIST_FOREACH_END(node);
+
+ smartlist_free(the_nodelist->nodes);
+
+ tor_free(the_nodelist);
+}
+
+/** Check that the nodelist is internally consistent, and consistent with
+ * the directory info it's derived from.
+ */
+void
+nodelist_assert_ok(void)
+{
+ routerlist_t *rl = router_get_routerlist();
+ networkstatus_t *ns = networkstatus_get_latest_consensus();
+ digestmap_t *dm = digestmap_new();
+
+ if (!the_nodelist)
+ return;
+
+ /* every routerinfo in rl->routers should be in the nodelist. */
+ if (rl) {
+ SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) {
+ node_t *node = node_get_by_id(ri->cache_info.identity_digest);
+ tor_assert(node && node->ri == ri);
+ tor_assert(0 == memcmp(ri->cache_info.identity_digest,
+ node->identity, DIGEST_LEN));
+ tor_assert(! digestmap_get(dm, node->identity));
+ digestmap_set(dm, node->identity, node);
+ } SMARTLIST_FOREACH_END(ri);
+ }
+
+ /* every routerstatus in ns should be in the nodelist */
+ if (ns) {
+ SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, routerstatus_t *, rs) {
+ node_t *node = node_get_by_id(rs->identity_digest);
+ tor_assert(node && node->rs == rs);
+ tor_assert(0 == memcmp(rs->identity_digest, node->identity, DIGEST_LEN));
+ digestmap_set(dm, node->identity, node);
+ if (ns->flavor == FLAV_MICRODESC) {
+ /* If it's a microdesc consensus, every entry that has a microdescriptor
+ * should be in the nodelist.
+ */
+ microdesc_t *md =
+ microdesc_cache_lookup_by_digest256(NULL, rs->descriptor_digest);
+ tor_assert(md == node->md);
+ }
+ } SMARTLIST_FOREACH_END(rs);
+ }
+
+ /* The nodelist should have no other entries, and its entries should be
+ * well-formed. */
+ SMARTLIST_FOREACH_BEGIN(the_nodelist->nodes, node_t *, node) {
+ tor_assert(digestmap_get(dm, node->identity) != NULL);
+ tor_assert(node_sl_idx == node->nodelist_idx);
+ } SMARTLIST_FOREACH_END(node);
+
+ tor_assert((long)smartlist_len(the_nodelist->nodes) ==
+ (long)HT_SIZE(&the_nodelist->nodes_by_id));
+
+ digestmap_free(dm, NULL);
+}
+
diff --git a/src/or/nodelist.h b/src/or/nodelist.h
new file mode 100644
index 0000000..6a77ba6
--- /dev/null
+++ b/src/or/nodelist.h
@@ -0,0 +1,28 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2010, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file microdesc.h
+ * \brief Header file for microdesc.c.
+ **/
+
+#ifndef _TOR_NODELIST_H
+#define _TOR_NODELIST_H
+
+node_t *node_get_by_id(const char *identity_digest);
+node_t *nodelist_add_routerinfo(routerinfo_t *ri);
+node_t *nodelist_add_microdesc(microdesc_t *md);
+void nodelist_set_consensus(networkstatus_t *ns);
+
+void nodelist_remove_microdesc(const char *identity_digest, microdesc_t *md);
+void nodelist_remove_routerinfo(routerinfo_t *ri);
+void nodelist_purge(void);
+
+void nodelist_free_all(void);
+void nodelist_assert_ok(void);
+
+#endif
+
diff --git a/src/or/or.h b/src/or/or.h
index 673a392..e46237c 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1698,6 +1698,19 @@ typedef struct microdesc_t {
* XXX this probably should not stay a string. */
} microdesc_t;
+/** DOCDOC */
+typedef struct node_t {
+ /** Used to look up the node_t by its identity digest. */
+ HT_ENTRY(node_t) ht_ent;
+ /** Position of the node within the list of nodes */
+ int nodelist_idx;
+
+ char identity[DIGEST_LEN];
+ microdesc_t *md;
+ routerinfo_t *ri;
+ routerstatus_t *rs;
+} node_t;
+
/** How many times will we try to download a router's descriptor before giving
* up? */
#define MAX_ROUTERDESC_DOWNLOAD_FAILURES 8
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 43be834..3c38f9c 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -24,6 +24,7 @@
#include "main.h"
#include "microdesc.h"
#include "networkstatus.h"
+#include "nodelist.h"
#include "policies.h"
#include "reasons.h"
#include "rendcommon.h"
@@ -2783,6 +2784,7 @@ routerlist_insert(routerlist_t *rl, routerinfo_t *ri)
&ri->cache_info);
smartlist_add(rl->routers, ri);
ri->cache_info.routerlist_index = smartlist_len(rl->routers) - 1;
+ nodelist_add_routerinfo(ri);
router_dir_info_changed();
#ifdef DEBUG_ROUTERLIST
routerlist_assert_ok(rl);
@@ -2890,6 +2892,8 @@ routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old, time_t now)
tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
tor_assert(smartlist_get(rl->routers, idx) == ri);
+ nodelist_remove_routerinfo(ri);
+
/* make sure the rephist module knows that it's not running */
rep_hist_note_router_unreachable(ri->cache_info.identity_digest, now);
@@ -3011,6 +3015,9 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old,
tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
tor_assert(smartlist_get(rl->routers, idx) == ri_old);
+ nodelist_remove_routerinfo(ri_old);
+ nodelist_add_routerinfo(ri_new);
+
router_dir_info_changed();
if (idx >= 0) {
smartlist_set(rl->routers, idx, ri_new);
--
1.7.1