commit 02a650786b21e4f3c255d686a3b5df875b2d66b5 Author: Nick Mathewson nickm@torproject.org Date: Thu May 10 17:27:16 2012 -0400
Fix O(n^2) performance when parsing a big pile of extrainfos
We were doing an O(n) strlen in router_get_extrainfo_hash() for every one we tried to parse. Instead, have router_get_extrainfo_hash() take the length of the extrainfo as an argument, so that when it's called from extrainfo_parse_from_string(), it doesn't do a strlen() over the whole pile of extrainfos. --- changes/bug5828 | 3 +++ src/or/router.c | 3 ++- src/or/routerparse.c | 10 +++++----- src/or/routerparse.h | 2 +- 4 files changed, 11 insertions(+), 7 deletions(-)
diff --git a/changes/bug5828 b/changes/bug5828 new file mode 100644 index 0000000..3a1734d --- /dev/null +++ b/changes/bug5828 @@ -0,0 +1,3 @@ + o Minor bugfixes (performance): + - Avoid O(n^2) performance characteristics when parsing a large + extrainfo cache. Fixes bug 5828; bugfix on 0.2.0.1-alpha. diff --git a/src/or/router.c b/src/or/router.c index c51bb5d..35955f3 100644 --- a/src/or/router.c +++ b/src/or/router.c @@ -1655,6 +1655,7 @@ router_rebuild_descriptor(int force) ei->cache_info.signed_descriptor_len = strlen(ei->cache_info.signed_descriptor_body); router_get_extrainfo_hash(ei->cache_info.signed_descriptor_body, + ei->cache_info.signed_descriptor_len, ei->cache_info.signed_descriptor_digest); }
@@ -2359,7 +2360,7 @@ extrainfo_dump_to_string(char **s_out, extrainfo_t *extrainfo, }
memset(sig, 0, sizeof(sig)); - if (router_get_extrainfo_hash(s, digest) < 0 || + if (router_get_extrainfo_hash(s, strlen(s), digest) < 0 || router_append_dirobj_signature(sig, sizeof(sig), digest, DIGEST_LEN, ident_key) < 0) { log_warn(LD_BUG, "Could not append signature to extra-info " diff --git a/src/or/routerparse.c b/src/or/routerparse.c index c5ce174..781c578 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -682,12 +682,12 @@ router_get_networkstatus_v3_hash(const char *s, char *digest, ' ', alg); }
-/** Set <b>digest</b> to the SHA-1 digest of the hash of the extrainfo - * string in <b>s</b>. Return 0 on success, -1 on failure. */ +/** Set <b>digest</b> to the SHA-1 digest of the hash of the <b>s_len</b>-byte + * extrainfo string at <b>s</b>. Return 0 on success, -1 on failure. */ int -router_get_extrainfo_hash(const char *s, char *digest) +router_get_extrainfo_hash(const char *s, size_t s_len, char *digest) { - return router_get_hash_impl(s, strlen(s), digest, "extra-info", + return router_get_hash_impl(s, s_len, digest, "extra-info", "\nrouter-signature",'\n', DIGEST_SHA1); }
@@ -1643,7 +1643,7 @@ extrainfo_parse_entry_from_string(const char *s, const char *end, while (end > s+2 && *(end-1) == '\n' && *(end-2) == '\n') --end;
- if (router_get_extrainfo_hash(s, digest) < 0) { + if (router_get_extrainfo_hash(s, end-s, digest) < 0) { log_warn(LD_DIR, "Couldn't compute router hash."); goto err; } diff --git a/src/or/routerparse.h b/src/or/routerparse.h index b274d21..6486a09 100644 --- a/src/or/routerparse.h +++ b/src/or/routerparse.h @@ -19,7 +19,7 @@ int router_get_networkstatus_v2_hash(const char *s, char *digest); int router_get_networkstatus_v3_hash(const char *s, char *digest, digest_algorithm_t algorithm); int router_get_networkstatus_v3_hashes(const char *s, digests_t *digests); -int router_get_extrainfo_hash(const char *s, char *digest); +int router_get_extrainfo_hash(const char *s, size_t s_len, char *digest); #define DIROBJ_MAX_SIG_LEN 256 int router_append_dirobj_signature(char *buf, size_t buf_len, const char *digest,