commit ebbb0348dc3ad57f6be8208a90f3c2fd9fe2cbf7 Author: Nick Mathewson nickm@torproject.org Date: Tue Jun 26 13:20:54 2018 -0400
Finish renaming digestset_contains to digestset_probably_contains
Since bloom filters are probabilistic, it's nice to make it clear that the "contains" operation can have false positives. --- src/lib/crypt_ops/digestset.h | 3 --- src/or/entrynodes.c | 2 +- src/or/routerlist.c | 7 ++++--- src/test/bench.c | 10 ++++++---- src/test/test_containers.c | 6 +++--- 5 files changed, 14 insertions(+), 14 deletions(-)
diff --git a/src/lib/crypt_ops/digestset.h b/src/lib/crypt_ops/digestset.h index 3b5d62c31..328979ae0 100644 --- a/src/lib/crypt_ops/digestset.h +++ b/src/lib/crypt_ops/digestset.h @@ -26,7 +26,4 @@ void digestset_add(digestset_t *set, const char *addr); int digestset_probably_contains(const digestset_t *set, const char *addr);
-// XXXX to remove. -#define digestset_contains digestset_probably_contains - #endif diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index 9d27d80a8..47e689b5c 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -1065,7 +1065,7 @@ get_eligible_guards(const or_options_t *options, continue; } ++n_guards; - if (digestset_contains(sampled_guard_ids, node->identity)) + if (digestset_probably_contains(sampled_guard_ids, node->identity)) continue; smartlist_add(eligible_guards, (node_t*)node); } SMARTLIST_FOREACH_END(node); diff --git a/src/or/routerlist.c b/src/or/routerlist.c index a7dda68a5..66967f13f 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -4116,7 +4116,8 @@ routerlist_remove_old_cached_routers_with_id(time_t now, signed_descriptor_t *r_next; lifespans[i-lo].idx = i; if (r->last_listed_as_valid_until >= now || - (retain && digestset_contains(retain, r->signed_descriptor_digest))) { + (retain && digestset_probably_contains(retain, + r->signed_descriptor_digest))) { must_keep[i-lo] = 1; } if (i < hi) { @@ -4211,7 +4212,7 @@ routerlist_remove_old_routers(void) router = smartlist_get(routerlist->routers, i); if (router->cache_info.published_on <= cutoff && router->cache_info.last_listed_as_valid_until < now && - !digestset_contains(retain, + !digestset_probably_contains(retain, router->cache_info.signed_descriptor_digest)) { /* Too old: remove it. (If we're a cache, just move it into * old_routers.) */ @@ -4232,7 +4233,7 @@ routerlist_remove_old_routers(void) sd = smartlist_get(routerlist->old_routers, i); if (sd->published_on <= cutoff && sd->last_listed_as_valid_until < now && - !digestset_contains(retain, sd->signed_descriptor_digest)) { + !digestset_probably_contains(retain, sd->signed_descriptor_digest)) { /* Too old. Remove it. */ routerlist_remove_old(routerlist, sd, i--); } diff --git a/src/test/bench.c b/src/test/bench.c index aa4af703f..6653f4942 100644 --- a/src/test/bench.c +++ b/src/test/bench.c @@ -404,18 +404,20 @@ bench_dmap(void) NANOCOUNT(pt3, pt4, iters*elts));
for (i = 0; i < iters; ++i) { - SMARTLIST_FOREACH(sl, const char *, cp, n += digestset_contains(ds, cp)); - SMARTLIST_FOREACH(sl2, const char *, cp, n += digestset_contains(ds, cp)); + SMARTLIST_FOREACH(sl, const char *, cp, + n += digestset_probably_contains(ds, cp)); + SMARTLIST_FOREACH(sl2, const char *, cp, + n += digestset_probably_contains(ds, cp)); } end = perftime(); - printf("digestset_contains: %.2f ns per element.\n", + printf("digestset_probably_contains: %.2f ns per element.\n", NANOCOUNT(pt4, end, iters*elts*2)); /* We need to use this, or else the whole loop gets optimized out. */ printf("Hits == %d\n", n);
for (i = 0; i < fpostests; ++i) { crypto_rand(d, 20); - if (digestset_contains(ds, d)) ++fp; + if (digestset_probably_contains(ds, d)) ++fp; } printf("False positive rate on digestset: %.2f%%\n", (fp/(double)fpostests)*100); diff --git a/src/test/test_containers.c b/src/test/test_containers.c index acb7543b3..5c712a9b1 100644 --- a/src/test/test_containers.c +++ b/src/test/test_containers.c @@ -644,18 +644,18 @@ test_container_digestset(void *arg) } set = digestset_new(1000); SMARTLIST_FOREACH(included, const char *, cp, - if (digestset_contains(set, cp)) + if (digestset_probably_contains(set, cp)) ok = 0); tt_assert(ok); SMARTLIST_FOREACH(included, const char *, cp, digestset_add(set, cp)); SMARTLIST_FOREACH(included, const char *, cp, - if (!digestset_contains(set, cp)) + if (!digestset_probably_contains(set, cp)) ok = 0); tt_assert(ok); for (i = 0; i < 1000; ++i) { crypto_rand(d, DIGEST_LEN); - if (digestset_contains(set, d)) + if (digestset_probably_contains(set, d)) ++false_positives; } tt_int_op(50, OP_GT, false_positives); /* Should be far lower. */