diff options
| -rw-r--r-- | ChangeLog | 5 | ||||
| -rw-r--r-- | src/or/or.h | 4 | ||||
| -rw-r--r-- | src/or/router.c | 1 | ||||
| -rw-r--r-- | src/or/routerlist.c | 151 | ||||
| -rw-r--r-- | src/or/routerparse.c | 1 |
5 files changed, 101 insertions, 61 deletions
@@ -1,8 +1,9 @@ Changes in version 0.1.2.2-alpha - 2006-??-?? o Minor Bugfixes - - Small performance improvements on parsing and inserting - descriptors. + - Small performance improvements on parsing descriptors. + - Major performance descriptor on inserting descriptors; change + algorithm from O(n^2) to O(n). [Mostly.] - Make the common memory allocation path faster on machines where malloc(0) returns a pointer. diff --git a/src/or/or.h b/src/or/or.h index d7fba9c83..09d9778ac 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -928,6 +928,10 @@ typedef struct { /** How many times has a descriptor been posted and we believed * this router to be unreachable? We only actually warn on the third. */ int num_unreachable_notifications; + + /** What position is this descriptor within routerlist->routers? -1 for + * none. */ + int routerlist_index; } routerinfo_t; /** Contents of a single router entry in a network status object. diff --git a/src/or/router.c b/src/or/router.c index a5d9b7253..73de2ddc2 100644 --- a/src/or/router.c +++ b/src/or/router.c @@ -805,6 +805,7 @@ router_rebuild_descriptor(int force) } ri = tor_malloc_zero(sizeof(routerinfo_t)); + ri->routerlist_index = -1; ri->address = tor_dup_addr(addr); ri->nickname = tor_strdup(options->Nickname); ri->addr = addr; diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 1d067667b..54e2657c0 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1343,6 +1343,7 @@ routerlist_insert(routerlist_t *rl, routerinfo_t *ri) digestmap_set(rl->desc_digest_map, ri->cache_info.signed_descriptor_digest, &(ri->cache_info)); smartlist_add(rl->routers, ri); + ri->routerlist_index = smartlist_len(rl->routers) - 1; router_dir_info_changed(); // routerlist_assert_ok(rl); } @@ -1356,6 +1357,7 @@ routerlist_insert_old(routerlist_t *rl, routerinfo_t *ri) signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri); digestmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd); smartlist_add(rl->old_routers, sd); + ri->routerlist_index = -1; } else { routerinfo_free(ri); } @@ -1374,7 +1376,13 @@ routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int idx, int make_old) idx = _routerlist_find_elt(rl->routers, ri, idx); if (idx < 0) return; + ri->routerlist_index = -1; smartlist_del(rl->routers, idx); + if (idx < smartlist_len(rl->routers)) { + routerinfo_t *r = smartlist_get(rl->routers, idx); + r->routerlist_index = idx; + } + ri_tmp = digestmap_remove(rl->identity_map, ri->cache_info.identity_digest); router_dir_info_changed(); tor_assert(ri_tmp == ri); @@ -1423,6 +1431,8 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, router_dir_info_changed(); if (idx >= 0) { smartlist_set(rl->routers, idx, ri_new); + ri_old->routerlist_index = -1; + ri_new->routerlist_index = idx; } else { log_warn(LD_BUG, "Appending entry from routerlist_replace."); routerlist_insert(rl, ri_new); @@ -1606,10 +1616,10 @@ int router_add_to_routerlist(routerinfo_t *router, const char **msg, int from_cache, int from_fetch) { - int i; const char *id_digest; int authdir = get_options()->AuthoritativeDir; int authdir_believes_valid = 0; + routerinfo_t *old_router; tor_assert(msg); @@ -1665,71 +1675,91 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, rs->need_to_mirror = 0; }); - /* If we have a router with this name, and the identity key is the same, - * choose the newer one. If the identity key has changed, and one of the + /* If we have a router with the same identity key, choose the newer one. */ + old_router = digestmap_get(routerlist->identity_map, + router->cache_info.identity_digest); + if (old_router) { + int pos = old_router->routerlist_index; + tor_assert(smartlist_get(routerlist->routers, pos) == old_router); + + if (router->cache_info.published_on <= + old_router->cache_info.published_on) { + /* Same key, but old */ + log_debug(LD_DIR, "Skipping not-new descriptor for router '%s'", + router->nickname); + /* Only journal this desc if we'll be serving it. */ + if (!from_cache && get_options()->DirPort) + router_append_to_journal(&router->cache_info); + routerlist_insert_old(routerlist, router); + *msg = "Router descriptor was not new."; + return -1; + } else { + /* Same key, new. */ + int unreachable = 0; + log_debug(LD_DIR, "Replacing entry for router '%s/%s' [%s]", + router->nickname, old_router->nickname, + hex_str(id_digest,DIGEST_LEN)); + if (router->addr == old_router->addr && + router->or_port == old_router->or_port) { + /* these carry over when the address and orport are unchanged.*/ + router->last_reachable = old_router->last_reachable; + router->testing_since = old_router->testing_since; + router->num_unreachable_notifications = + old_router->num_unreachable_notifications; + } + if (authdir && !from_cache && !from_fetch && + router_have_minimum_dir_info() && + dirserv_thinks_router_is_blatantly_unreachable(router, + time(NULL))) { + if (router->num_unreachable_notifications >= 3) { + unreachable = 1; + log_notice(LD_DIR, "Notifying server '%s' that it's unreachable. " + "(ContactInfo '%s', platform '%s').", + router->nickname, + router->contact_info ? router->contact_info : "", + router->platform ? router->platform : ""); + } else { + log_info(LD_DIR,"'%s' may be unreachable -- the %d previous " + "descriptors were thought to be unreachable.", + router->nickname, router->num_unreachable_notifications); + router->num_unreachable_notifications++; + } + } + routerlist_replace(routerlist, old_router, router, pos, 1); + if (!from_cache) { + router_append_to_journal(&router->cache_info); + } + directory_set_dirty(); + *msg = unreachable ? "Dirserver believes your ORPort is unreachable" : + authdir_believes_valid ? "Valid server updated" : + ("Invalid server updated. (This dirserver is marking your " + "server as unapproved.)"); + return unreachable ? 1 : 0; + } + } + +#if 1 + /* XXXX This block is slow, and could be smarter. All it does is ensure + * that if we have a named server called "Foo", we will never have another + * server called "Foo." router_get_by_nickname() already knows to prefer + * named routers, so the problem only arises when there is a named router + * called 'foo', but we don't have it. If, instead, we kept a + * name-to-identity-key mapping for each named router in the networkstatus + * list, we could eliminate this block. + * + * Hm. perhaps we should; I don't see how this code is non-broken wrt named + * routers. -NM + */ + + /* If the identity key has changed, and one of the * routers is named, drop the unnamed ones. (If more than one are named, * drop the old ones.) */ for (i = 0; i < smartlist_len(routerlist->routers); ++i) { routerinfo_t *old_router = smartlist_get(routerlist->routers, i); - /* XXXX This might be a slow point; can't we just look up in one of the - * digestmaps? -NM */ if (!memcmp(router->cache_info.identity_digest, old_router->cache_info.identity_digest, DIGEST_LEN)) { - if (router->cache_info.published_on <= - old_router->cache_info.published_on) { - /* Same key, but old */ - log_debug(LD_DIR, "Skipping not-new descriptor for router '%s'", - router->nickname); - /* Only journal this desc if we'll be serving it. */ - if (!from_cache && get_options()->DirPort) - router_append_to_journal(&router->cache_info); - routerlist_insert_old(routerlist, router); - *msg = "Router descriptor was not new."; - return -1; - } else { - /* Same key, new. */ - int unreachable = 0; - log_debug(LD_DIR, "Replacing entry for router '%s/%s' [%s]", - router->nickname, old_router->nickname, - hex_str(id_digest,DIGEST_LEN)); - if (router->addr == old_router->addr && - router->or_port == old_router->or_port) { - /* these carry over when the address and orport are unchanged.*/ - router->last_reachable = old_router->last_reachable; - router->testing_since = old_router->testing_since; - router->num_unreachable_notifications = - old_router->num_unreachable_notifications; - } - if (authdir && !from_cache && !from_fetch && - router_have_minimum_dir_info() && - dirserv_thinks_router_is_blatantly_unreachable(router, - time(NULL))) { - if (router->num_unreachable_notifications >= 3) { - unreachable = 1; - log_notice(LD_DIR, "Notifying server '%s' that it's unreachable. " - "(ContactInfo '%s', platform '%s').", - router->nickname, - router->contact_info ? router->contact_info : "", - router->platform ? router->platform : ""); - } else { - log_info(LD_DIR,"'%s' may be unreachable -- the %d previous " - "descriptors were thought to be unreachable.", - router->nickname, router->num_unreachable_notifications); - router->num_unreachable_notifications++; - } - } - routerlist_replace(routerlist, old_router, router, i, 1); - if (!from_cache) { - router_append_to_journal(&router->cache_info); - } - directory_set_dirty(); - *msg = unreachable ? "Dirserver believes your ORPort is unreachable" : - authdir_believes_valid ? "Valid server updated" : - ("Invalid server updated. (This dirserver is marking your " - "server as unapproved.)"); - return unreachable ? 1 : 0; - } + } else if (!strcasecmp(router->nickname, old_router->nickname)) { /* nicknames match, keys don't. */ if (router->is_named) { @@ -1760,6 +1790,8 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, } } } +#endif + /* We haven't seen a router with this name before. Add it to the end of * the list. */ routerlist_insert(routerlist, router); @@ -3970,6 +4002,7 @@ routerlist_assert_ok(routerlist_t *rl) sd2 = digestmap_get(rl->desc_digest_map, r->cache_info.signed_descriptor_digest); tor_assert(&(r->cache_info) == sd2); + tor_assert(r->routerlist_index == r_sl_idx); }); SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd, { diff --git a/src/or/routerparse.c b/src/or/routerparse.c index ce564a511..12ff72d38 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -752,6 +752,7 @@ router_parse_entry_from_string(const char *s, const char *end, } router = tor_malloc_zero(sizeof(routerinfo_t)); + router->routerlist_index = -1; if (cache_copy) router->cache_info.signed_descriptor_body = tor_strndup(s, end-s); router->cache_info.signed_descriptor_len = end-s; |