April 2017 - tor-commits - lists.torproject.org

[tor/master] Add a hashtable to consdiffmgr to keep track of diff status
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit 7ca86b9cd65ba4c7ed3c36f0c56c97ad4b075585 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat Apr 15 13:23:10 2017 -0400 Add a hashtable to consdiffmgr to keep track of diff status In several places in the old code, we had problems that only an in-memory index of diff status could solve, including: * Remembering which diffs were in-progress, so that we didn't re-launch them. * Remembering which diffs had failed, so that we didn't try to recompute them over and over. * Having a fast way to look up the diff from a given consensus to the latest consensus of a given flavor. This patch adds a hashtable mapping from (flavor, source diff), to solve the problem. It maps to a cache entry handle, rather than to a cache entry directly, so that it doesn't affect the reference counts of the cache entries, and so that we don't otherwise need to worry about lifetime management. --- src/or/consdiffmgr.c | 317 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 307 insertions(+), 10 deletions(-) diff --git a/src/or/consdiffmgr.c b/src/or/consdiffmgr.c index 16778b7..240fe6e 100644 --- a/src/or/consdiffmgr.c +++ b/src/or/consdiffmgr.c @@ -59,6 +59,44 @@ static consensus_cache_t *cons_diff_cache = NULL; */ static int cdm_cache_dirty = 0; /** + * If true, we have scanned the cache to update our hashtable of diffs. + */ +static int cdm_cache_loaded = 0; + +/** + * Possible status values for cdm_diff_t.cdm_diff_status + **/ +typedef enum cdm_diff_status_t { + CDM_DIFF_PRESENT=1, + CDM_DIFF_IN_PROGRESS=2, + CDM_DIFF_ERROR=3, +} cdm_diff_status_t; + +/** Hashtable node used to remember the current status of the diff + * from a given sha3 digest to the current consensus. */ +typedef struct cdm_diff_t { + HT_ENTRY(cdm_diff_t) node; + + /** Consensus flavor for this diff (part of ht key) */ + consensus_flavor_t flavor; + /** SHA3-256 digest of the consensus that this diff is _from_. (part of the + * ht key) */ + uint8_t from_sha3[DIGEST256_LEN]; + + /** One of the CDM_DIFF_* values, depending on whether this diff + * is available, in progress, or impossible to compute. */ + cdm_diff_status_t cdm_diff_status; + /** SHA3-256 digest of the consensus that this diff is _to. */ + uint8_t target_sha3[DIGEST256_LEN]; + /** Handle to the cache entry for this diff, if any. We use a handle here + * to avoid thinking too hard about cache entry lifetime issues. */ + consensus_cache_entry_handle_t *entry; +} cdm_diff_t; + +/** Hashtable mapping flavor and source consensus digest to status. */ +static HT_HEAD(cdm_diff_ht, cdm_diff_t) cdm_diff_ht = HT_INITIALIZER(); + +/** * Configuration for this module */ static consdiff_cfg_t consdiff_cfg = { @@ -69,6 +107,160 @@ static consdiff_cfg_t consdiff_cfg = { static int consensus_diff_queue_diff_work(consensus_cache_entry_t *diff_from, consensus_cache_entry_t *diff_to); static void consdiffmgr_set_cache_flags(void); + +/* ===== + * Hashtable setup + * ===== */ + +/** Helper: hash the key of a cdm_diff_t. */ +static unsigned +cdm_diff_hash(const cdm_diff_t *diff) +{ + uint8_t tmp[DIGEST256_LEN + 1]; + memcpy(tmp, diff->from_sha3, DIGEST256_LEN); + tmp[DIGEST256_LEN] = (uint8_t) diff->flavor; + return (unsigned) siphash24g(tmp, sizeof(tmp)); +} +/** Helper: compare two cdm_diff_t objects for key equality */ +static int +cdm_diff_eq(const cdm_diff_t *diff1, const cdm_diff_t *diff2) +{ + return fast_memeq(diff1->from_sha3, diff2->from_sha3, DIGEST256_LEN) && + diff1->flavor == diff2->flavor; +} + +HT_PROTOTYPE(cdm_diff_ht, cdm_diff_t, node, cdm_diff_hash, cdm_diff_eq) +HT_GENERATE2(cdm_diff_ht, cdm_diff_t, node, cdm_diff_hash, cdm_diff_eq, + 0.6, tor_reallocarray, tor_free_) + +/** Release all storage held in diff. */ +static void +cdm_diff_free(cdm_diff_t *diff) +{ + if (!diff) + return; + consensus_cache_entry_handle_free(diff->entry); + tor_free(diff); +} + +/** Create and return a new cdm_diff_t with the given values. Does not + * add it to the hashtable. */ +static cdm_diff_t * +cdm_diff_new(consensus_flavor_t flav, + const uint8_t *from_sha3, + const uint8_t *target_sha3) +{ + cdm_diff_t *ent; + ent = tor_malloc_zero(sizeof(cdm_diff_t)); + ent->flavor = flav; + memcpy(ent->from_sha3, from_sha3, DIGEST256_LEN); + memcpy(ent->target_sha3, target_sha3, DIGEST256_LEN); + return ent; +} + +/** + * Examine the diff hashtable to see whether we know anything about computing + * a diff of type flav between consensuses with the two provided + * SHA3-256 digests. If a computation is in progress, or if the computation + * has already been tried and failed, return 1. Otherwise, note the + * computation as "in progress" so that we don't reattempt it later, and + * return 0. + */ +static int +cdm_diff_ht_check_and_note_pending(consensus_flavor_t flav, + const uint8_t *from_sha3, + const uint8_t *target_sha3) +{ + struct cdm_diff_t search, *ent; + memset(&search, 0, sizeof(cdm_diff_t)); + search.flavor = flav; + memcpy(search.from_sha3, from_sha3, DIGEST256_LEN); + ent = HT_FIND(cdm_diff_ht, &cdm_diff_ht, &search); + if (ent) { + tor_assert_nonfatal(ent->cdm_diff_status != CDM_DIFF_PRESENT); + return 1; + } + ent = cdm_diff_new(flav, from_sha3, target_sha3); + ent->cdm_diff_status = CDM_DIFF_IN_PROGRESS; + HT_INSERT(cdm_diff_ht, &cdm_diff_ht, ent); + return 0; +} + +/** + * Update the status of the diff of type flav between consensuses with + * the two provided SHA3-256 digests, so that its status becomes + * status, and its value becomes the handle. If handle + * is NULL, then the old handle (if any) is freed, and replaced with NULL. + */ +static void +cdm_diff_ht_set_status(consensus_flavor_t flav, + const uint8_t *from_sha3, + const uint8_t *to_sha3, + int status, + consensus_cache_entry_handle_t *handle) +{ + struct cdm_diff_t search, *ent; + memset(&search, 0, sizeof(cdm_diff_t)); + search.flavor = flav; + memcpy(search.from_sha3, from_sha3, DIGEST256_LEN); + ent = HT_FIND(cdm_diff_ht, &cdm_diff_ht, &search); + if (!ent) { + ent = cdm_diff_new(flav, from_sha3, to_sha3); + ent->cdm_diff_status = CDM_DIFF_IN_PROGRESS; + HT_INSERT(cdm_diff_ht, &cdm_diff_ht, ent); + } else if (fast_memneq(ent->target_sha3, to_sha3, DIGEST256_LEN)) { + // This can happen under certain really pathological conditions + // if we decide we don't care about a diff before it is actually + // done computing. + return; + } + + tor_assert_nonfatal(ent->cdm_diff_status == CDM_DIFF_IN_PROGRESS); + + ent->cdm_diff_status = status; + consensus_cache_entry_handle_free(ent->entry); + ent->entry = handle; +} + +/** + * Helper: Remove from the hash table every present (actually computed) diff + * of type flav whose target digest does not match + * unless_target_sha3_matches. + * + * This function is used for the hash table to throw away references to diffs + * that do not lead to the most given consensus of a given flavor. + */ +static void +cdm_diff_ht_purge(consensus_flavor_t flav, + const uint8_t *unless_target_sha3_matches) +{ + cdm_diff_t **diff, **next; + for (diff = HT_START(cdm_diff_ht, &cdm_diff_ht); diff; diff = next) { + cdm_diff_t *this = *diff; + + if ((*diff)->cdm_diff_status == CDM_DIFF_PRESENT && + flav == (*diff)->flavor) { + + if (consensus_cache_entry_handle_get((*diff)->entry) == NULL) { + /* the underlying entry has gone away; drop this. */ + next = HT_NEXT_RMV(cdm_diff_ht, &cdm_diff_ht, diff); + cdm_diff_free(this); + continue; + } + + if (unless_target_sha3_matches && + fast_memneq(unless_target_sha3_matches, (*diff)->target_sha3, + DIGEST256_LEN)) { + /* target hash doesn't match; drop this. */ + next = HT_NEXT_RMV(cdm_diff_ht, &cdm_diff_ht, diff); + cdm_diff_free(this); + continue; + } + } + next = HT_NEXT(cdm_diff_ht, &cdm_diff_ht, diff); + } +} + /** * Helper: initialize cons_diff_cache. */ @@ -88,6 +280,7 @@ cdm_cache_init(void) consdiffmgr_set_cache_flags(); } cdm_cache_dirty = 1; + cdm_cache_loaded = 0; } /** @@ -160,7 +353,8 @@ cdm_cache_lookup_consensus(consensus_flavor_t flavor, time_t valid_after) /* We'll filter by valid-after time first, since that should * match the fewest documents. */ - // XXXX This is stupid and it should be a hash table. + /* We could add an extra hashtable here, but since we only do this scan + * when adding a new consensus, it probably doesn't matter much. */ smartlist_t *matches = smartlist_new(); consensus_cache_find_all(matches, cdm_cache_get(), LABEL_VALID_AFTER, formatted_time); @@ -289,12 +483,33 @@ consdiffmgr_find_diff_from(consensus_cache_entry_t **entry_out, const uint8_t *digest, size_t digestlen) { - // XXXX actually return IN_PROGRESS some times? if (BUG(digest_type != DIGEST_SHA3_256) || BUG(digestlen != DIGEST256_LEN)) { return CONSDIFF_NOT_FOUND; // LCOV_EXCL_LINE } + // Try to look up the entry in the hashtable. + cdm_diff_t search, *ent; + memset(&search, 0, sizeof(search)); + search.flavor = flavor; + memcpy(search.from_sha3, digest, DIGEST256_LEN); + ent = HT_FIND(cdm_diff_ht, &cdm_diff_ht, &search); + + if (ent == NULL || + ent->cdm_diff_status == CDM_DIFF_ERROR) { + return CONSDIFF_NOT_FOUND; + } else if (ent->cdm_diff_status == CDM_DIFF_IN_PROGRESS) { + return CONSDIFF_IN_PROGRESS; + } else if (BUG(ent->cdm_diff_status != CDM_DIFF_PRESENT)) { + return CONSDIFF_IN_PROGRESS; + } + + *entry_out = consensus_cache_entry_handle_get(ent->entry); + return (*entry_out) ? CONSDIFF_AVAILABLE : CONSDIFF_NOT_FOUND; + +#if 0 + // XXXX Remove this. I'm keeping it around for now in case we need to + // XXXX debug issues in the hashtable. char hex[HEX_DIGEST256_LEN+1]; base16_encode(hex, sizeof(hex), (const char *)digest, digestlen); const char *flavname = networkstatus_get_flavor_name(flavor); @@ -311,6 +526,7 @@ consdiffmgr_find_diff_from(consensus_cache_entry_t **entry_out, smartlist_free(matches); return result; +#endif } /** @@ -495,6 +711,10 @@ consdiffmgr_rescan_flavor_(consensus_flavor_t flavor) consensus_cache_entry_get_value(most_recent, LABEL_VALID_AFTER); if (BUG(most_recent_valid_after == NULL)) goto done; //LCOV_EXCL_LINE + uint8_t most_recent_sha3[DIGEST256_LEN]; + if (BUG(cdm_entry_get_sha3_value(most_recent_sha3, most_recent, + LABEL_SHA3_DIGEST) < 0)) + goto done; //LCOV_EXCL_LINE // 2. Find all the relevant diffs _to_ this consensus. These are ones // that we don't need to compute. @@ -535,13 +755,23 @@ consdiffmgr_rescan_flavor_(consensus_flavor_t flavor) flavname, smartlist_len(compute_diffs_from)); - // 4. Actually launch the requests. + // 4. Update the hashtable; remove entries in this flavor to other + // target consensuses. + cdm_diff_ht_purge(flavor, most_recent_sha3); + + // 5. Actually launch the requests. SMARTLIST_FOREACH_BEGIN(compute_diffs_from, consensus_cache_entry_t *, c) { if (BUG(c == most_recent)) continue; // LCOV_EXCL_LINE - // XXXX how do we know that we are not already computing this????? - // XXXX DO NOT MERGE UNTIL THAT ISSUE IS SOLVED. + uint8_t this_sha3[DIGEST256_LEN]; + if (BUG(cdm_entry_get_sha3_value(this_sha3, c, LABEL_SHA3_DIGEST)<0)) + continue; // LCOV_EXCL_LINE + if (cdm_diff_ht_check_and_note_pending(flavor, + this_sha3, most_recent_sha3)) { + // This is already pending, or we encountered an error. + continue; + } consensus_diff_queue_diff_work(c, most_recent); } SMARTLIST_FOREACH_END(c); @@ -553,6 +783,37 @@ consdiffmgr_rescan_flavor_(consensus_flavor_t flavor) } /** + * Scan the cache for diffs, and add them to the hashtable. + */ +static void +consdiffmgr_diffs_load(void) +{ + smartlist_t *diffs = smartlist_new(); + consensus_cache_find_all(diffs, cdm_cache_get(), + LABEL_DOCTYPE, DOCTYPE_CONSENSUS_DIFF); + SMARTLIST_FOREACH_BEGIN(diffs, consensus_cache_entry_t *, diff) { + const char *lv_flavor = + consensus_cache_entry_get_value(diff, LABEL_FLAVOR); + if (!lv_flavor) + continue; + int flavor = networkstatus_parse_flavor_name(lv_flavor); + if (flavor < 0) + continue; + uint8_t from_sha3[DIGEST256_LEN]; + uint8_t to_sha3[DIGEST256_LEN]; + if (cdm_entry_get_sha3_value(from_sha3, diff, LABEL_FROM_SHA3_DIGEST)<0) + continue; + if (cdm_entry_get_sha3_value(to_sha3, diff, LABEL_TARGET_SHA3_DIGEST)<0) + continue; + + cdm_diff_ht_set_status(flavor, from_sha3, to_sha3, + CDM_DIFF_PRESENT, + consensus_cache_entry_handle_new(diff)); + } SMARTLIST_FOREACH_END(diff); + smartlist_free(diffs); +} + +/** * Build new diffs as needed. */ void @@ -565,6 +826,11 @@ consdiffmgr_rescan(void) // consensuses do not have any entries. consdiffmgr_cleanup(); + if (cdm_cache_loaded == 0) { + consdiffmgr_diffs_load(); + cdm_cache_loaded = 1; + } + for (int flav = 0; flav < N_CONSENSUS_FLAVORS; ++flav) { consdiffmgr_rescan_flavor_((consensus_flavor_t) flav); } @@ -595,6 +861,12 @@ consdiffmgr_set_cache_flags(void) void consdiffmgr_free_all(void) { + cdm_diff_t **diff, **next; + for (diff = HT_START(cdm_diff_ht, &cdm_diff_ht); diff; diff = next) { + cdm_diff_t *this = *diff; + next = HT_NEXT_RMV(cdm_diff_ht, &cdm_diff_ht, diff); + cdm_diff_free(this); + } consensus_cache_free(cons_diff_cache); cons_diff_cache = NULL; } @@ -751,27 +1023,52 @@ consensus_diff_worker_replyfn(void *work_) consensus_cache_entry_get_value(job->diff_from, LABEL_SHA3_DIGEST); const char *lv_to_digest = consensus_cache_entry_get_value(job->diff_to, LABEL_SHA3_DIGEST); + const char *lv_flavor = + consensus_cache_entry_get_value(job->diff_to, LABEL_FLAVOR); if (BUG(lv_from_digest == NULL)) lv_from_digest = "???"; // LCOV_EXCL_LINE if (BUG(lv_to_digest == NULL)) lv_to_digest = "???"; // LCOV_EXCL_LINE + uint8_t from_sha3[DIGEST256_LEN]; + uint8_t to_sha3[DIGEST256_LEN]; + int flav = -1; + int cache = 1; + if (BUG(cdm_entry_get_sha3_value(from_sha3, job->diff_from, + LABEL_SHA3_DIGEST) < 0)) + cache = 0; + if (BUG(cdm_entry_get_sha3_value(to_sha3, job->diff_to, + LABEL_SHA3_DIGEST) < 0)) + cache = 0; + if (BUG(lv_flavor == NULL)) { + cache = 0; + } else if ((flav = networkstatus_parse_flavor_name(lv_flavor)) < 0) { + cache = 0; + } + + int status; + consensus_cache_entry_handle_t *handle = NULL; if (job->body_out && job->bodylen_out && job->labels_out) { /* Success! Store the results */ log_info(LD_DIRSERV, "Adding consensus diff from %s to %s", lv_from_digest, lv_to_digest); - consensus_cache_add(cdm_cache_get(), job->labels_out, - job->body_out, - job->bodylen_out); + consensus_cache_entry_t *ent = + consensus_cache_add(cdm_cache_get(), job->labels_out, + job->body_out, + job->bodylen_out); + status = CDM_DIFF_PRESENT; + handle = consensus_cache_entry_handle_new(ent); } else { /* Failure! Nothing to do but complain */ log_warn(LD_DIRSERV, "Worker was unable to compute consensus diff " "from %s to %s", lv_from_digest, lv_to_digest); - /* XXXX Actually, we should cache this failure and not repeat the - * attempt over and over */ + /* Cache this error so we don't try to compute this one again. */ + status = CDM_DIFF_ERROR; } + if (cache) + cdm_diff_ht_set_status(flav, from_sha3, to_sha3, status, handle); consensus_diff_worker_job_free(job); }

1 0

[tor/master] consdiffmgr: Enable in-progress test that was not previously working
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit 605bcfbf711291d154c69e27fc49e3162cf4d7d0 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Apr 16 11:28:25 2017 -0400 consdiffmgr: Enable in-progress test that was not previously working Also, add a list of additional tests to write. --- src/test/test_consdiffmgr.c | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) diff --git a/src/test/test_consdiffmgr.c b/src/test/test_consdiffmgr.c index 5161587..e637c11 100644 --- a/src/test/test_consdiffmgr.c +++ b/src/test/test_consdiffmgr.c @@ -280,13 +280,10 @@ test_consdiffmgr_make_diffs(void *arg) consdiffmgr_rescan(); tt_ptr_op(NULL, OP_NE, fake_cpuworker_queue); tt_int_op(1, OP_EQ, smartlist_len(fake_cpuworker_queue)); - // XXXX not working yet - /* diff_status = consdiffmgr_find_diff_from(&diff, FLAV_MICRODESC, DIGEST_SHA3_256, md_ns_sha3, DIGEST256_LEN); tt_int_op(CONSDIFF_IN_PROGRESS, OP_EQ, diff_status); - */ // Now run that process and get the diff. r = mock_cpuworker_run_work(); @@ -584,6 +581,17 @@ struct testcase_t consdiffmgr_tests[] = { TEST(cleanup_no_valid_after), TEST(cleanup_old_diffs), + // XXXX Test: Look up consensuses by digest in existing cases. + // XXXX Test: no duplicate diff job is launched when a job is pending. + // XXXX Test: register status when no pending entry existed?? (bug) + // XXXX Test: lookup entry, find in-progress. + // XXXX Test: lookup entry, find error. + // XXXX Test: clean up hashtable after most-recent-consensus changes. + // XXXX Test: cdm_entry_get_sha3_value cases. + // XXXX Test: sha3 mismatch on validation + // XXXX Test: initial loading of diffs from disk. + // XXXX Test: non-cacheing cases of replyfn(). + // (Bug: must release handle) END_OF_TESTCASES };

1 0

[tor/master] Expand diff-management test to cover reloading items from disk
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit de0142cd9d980e3f08caf48d2c0b42c4149c1230 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Apr 16 12:01:45 2017 -0400 Expand diff-management test to cover reloading items from disk --- src/test/test_consdiffmgr.c | 26 +++++++++++++++++++++++++- 1 file changed, 25 insertions(+), 1 deletion(-) diff --git a/src/test/test_consdiffmgr.c b/src/test/test_consdiffmgr.c index 4be36a4..f3cce23 100644 --- a/src/test/test_consdiffmgr.c +++ b/src/test/test_consdiffmgr.c @@ -174,6 +174,14 @@ lookup_apply_and_verify_diff(consensus_flavor_t flav, return match ? 0 : -1; } +static void +cdm_reload(void) +{ + consdiffmgr_free_all(); + cdm_cache_get(); + consdiffmgr_rescan(); +} + // ============================== Beginning of tests #if 0 @@ -451,6 +459,23 @@ test_consdiffmgr_diff_rules(void *arg) tt_int_op(0, OP_EQ, lookup_apply_and_verify_diff(FLAV_NS, ns_body[2], ns_body[5])); + /* Finally: reload, and make sure that the information is still indexed */ + cdm_reload(); + + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_NS, ns_body[0], ns_body[5])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_NS, ns_body[2], ns_body[5])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_NS, ns_body[1], ns_body[5])); + + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[1], md_body[4])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[2], md_body[4])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[3], md_body[4])); + done: for (i = 0; i < N; ++i) { tor_free(md_body[i]); @@ -680,7 +705,6 @@ struct testcase_t consdiffmgr_tests[] = { // in cdm_diff_ht_purge(). // XXXX Test: cdm_entry_get_sha3_value cases. // XXXX Test: sha3 mismatch on validation - // XXXX Test: initial loading of diffs from disk. // XXXX Test: non-cacheing cases of replyfn(). END_OF_TESTCASES

1 0

[tor/master] consdiffmgr tests: add tests to validate diff lookup/application
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit 831e656baa0e43925e106c6029a92866cec6ca74 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Apr 16 11:51:14 2017 -0400 consdiffmgr tests: add tests to validate diff lookup/application This commit adds some helper functions to look up the diff from one consensus and to make sure that applying it leads to another. Then we add them throughout the existing test cases. Doing this turned up a reference-leaking bug in consensus_diff_worker_replyfn. --- src/test/test_consdiffmgr.c | 101 +++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 96 insertions(+), 5 deletions(-) diff --git a/src/test/test_consdiffmgr.c b/src/test/test_consdiffmgr.c index e637c11..4be36a4 100644 --- a/src/test/test_consdiffmgr.c +++ b/src/test/test_consdiffmgr.c @@ -130,6 +130,50 @@ mock_cpuworker_handle_replies(void) fake_cpuworker_queue = NULL; } +// ============================== Other helpers + +static consdiff_status_t +lookup_diff_from(consensus_cache_entry_t **out, + consensus_flavor_t flav, + const char *str1) +{ + uint8_t digest[DIGEST256_LEN]; + crypto_digest256((char*)digest, str1, strlen(str1), DIGEST_SHA3_256); + return consdiffmgr_find_diff_from(out, flav, + DIGEST_SHA3_256, digest, sizeof(digest)); +} + +static int +lookup_apply_and_verify_diff(consensus_flavor_t flav, + const char *str1, + const char *str2) +{ + char *diff_string = NULL; + consensus_cache_entry_t *ent = NULL; + consdiff_status_t status = lookup_diff_from(&ent, flav, str1); + if (ent == NULL || status != CONSDIFF_AVAILABLE) + return -1; + + consensus_cache_entry_incref(ent); + size_t size; + const uint8_t *body; + int r = consensus_cache_entry_get_body(ent, &body, &size); + if (r == 0) + diff_string = tor_memdup_nulterm(body, size); + consensus_cache_entry_decref(ent); + if (diff_string == NULL) + return -1; + + char *applied = consensus_diff_apply(str1, diff_string); + tor_free(diff_string); + if (applied == NULL) + return -1; + + int match = !strcmp(applied, str2); + tor_free(applied); + return match ? 0 : -1; +} + // ============================== Beginning of tests #if 0 @@ -368,6 +412,35 @@ test_consdiffmgr_diff_rules(void *arg) tt_int_op(0, OP_EQ, mock_cpuworker_run_work()); mock_cpuworker_handle_replies(); + /* At this point, we should actually have working diffs! */ + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_NS, ns_body[0], ns_body[5])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_NS, ns_body[1], ns_body[5])); + + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[1], md_body[4])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[2], md_body[4])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[3], md_body[4])); + + /* Self-to-self diff won't be present */ + consensus_cache_entry_t *ent; + tt_int_op(CONSDIFF_NOT_FOUND, OP_EQ, + lookup_diff_from(&ent, FLAV_NS, ns_body[5])); + /* No diff from 2 has been added yet */ + tt_int_op(CONSDIFF_NOT_FOUND, OP_EQ, + lookup_diff_from(&ent, FLAV_NS, ns_body[2])); + /* No diff arriving at old things. */ + tt_int_op(-1, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[1], md_body[2])); + /* No backwards diff */ + tt_int_op(-1, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[4], md_body[3])); + + /* Now, an update: add number 2 and make sure it's the only one whose diff + * is regenerated. */ tt_int_op(0, OP_EQ, consdiffmgr_add_consensus(ns_body[2], ns_ns[2])); consdiffmgr_rescan(); tt_ptr_op(NULL, OP_NE, fake_cpuworker_queue); @@ -375,6 +448,9 @@ test_consdiffmgr_diff_rules(void *arg) tt_int_op(0, OP_EQ, mock_cpuworker_run_work()); mock_cpuworker_handle_replies(); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_NS, ns_body[2], ns_body[5])); + done: for (i = 0; i < N; ++i) { tor_free(md_body[i]); @@ -418,6 +494,11 @@ test_consdiffmgr_diff_failure(void *arg) expect_single_log_msg_containing("Worker was unable to compute consensus " "diff from "); + /* Make sure the diff is not present */ + consensus_cache_entry_t *ent; + tt_int_op(CONSDIFF_NOT_FOUND, OP_EQ, + lookup_diff_from(&ent, FLAV_NS, "foo bar baz\n")); + done: teardown_capture_of_logs(); UNMOCK(cpuworker_queue_work); @@ -547,12 +628,24 @@ test_consdiffmgr_cleanup_old_diffs(void *arg) /* Nothing is deletable now */ tt_int_op(0, OP_EQ, consdiffmgr_cleanup()); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[0], md_body[2])); + tt_int_op(0, OP_EQ, + lookup_apply_and_verify_diff(FLAV_MICRODESC, md_body[1], md_body[2])); /* Now add an even-more-recent consensus; this should make all previous * diffs deletable */ tt_int_op(0, OP_EQ, consdiffmgr_add_consensus(md_body[3], md_ns[3])); tt_int_op(2, OP_EQ, consdiffmgr_cleanup()); + consensus_cache_entry_t *ent; + tt_int_op(CONSDIFF_NOT_FOUND, OP_EQ, + lookup_diff_from(&ent, FLAV_MICRODESC, md_body[0])); + tt_int_op(CONSDIFF_NOT_FOUND, OP_EQ, + lookup_diff_from(&ent, FLAV_MICRODESC, md_body[1])); + tt_int_op(CONSDIFF_NOT_FOUND, OP_EQ, + lookup_diff_from(&ent, FLAV_MICRODESC, md_body[2])); + /* Everything should be valid at this point */ tt_int_op(0, OP_EQ, consdiffmgr_validate()); @@ -581,17 +674,15 @@ struct testcase_t consdiffmgr_tests[] = { TEST(cleanup_no_valid_after), TEST(cleanup_old_diffs), - // XXXX Test: Look up consensuses by digest in existing cases. // XXXX Test: no duplicate diff job is launched when a job is pending. // XXXX Test: register status when no pending entry existed?? (bug) - // XXXX Test: lookup entry, find in-progress. - // XXXX Test: lookup entry, find error. - // XXXX Test: clean up hashtable after most-recent-consensus changes. + // XXXX Test: clean up hashtable after most-recent-consensus changes + // in cdm_diff_ht_purge(). // XXXX Test: cdm_entry_get_sha3_value cases. // XXXX Test: sha3 mismatch on validation // XXXX Test: initial loading of diffs from disk. // XXXX Test: non-cacheing cases of replyfn(). - // (Bug: must release handle) + END_OF_TESTCASES };

1 0

[tor/master] Consdiffmgr: extract "get a sha3 digest" function.
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit 69a212ff3df2020fe67cedb71982b2198c31fe18 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat Apr 15 13:11:39 2017 -0400 Consdiffmgr: extract "get a sha3 digest" function. I'll be using this a lot in the hashtable tweaks here. --- src/or/consdiffmgr.c | 28 +++++++++++++++++++++++----- 1 file changed, 23 insertions(+), 5 deletions(-) diff --git a/src/or/consdiffmgr.c b/src/or/consdiffmgr.c index dce8c8b..16778b7 100644 --- a/src/or/consdiffmgr.c +++ b/src/or/consdiffmgr.c @@ -123,6 +123,29 @@ cdm_labels_prepend_sha3(config_line_t **labels, config_line_prepend(labels, LABEL_SHA3_DIGEST, hexdigest); } +/** Helper: if there is a sha3-256 hex-encoded digest in ent with the + * given label, set digest_out to that value (decoded), and return 0. + * + * Return -1 if there is no such label, and -2 if it is badly formatted. */ +static int +cdm_entry_get_sha3_value(uint8_t *digest_out, + consensus_cache_entry_t *ent, + const char *label) +{ + if (ent == NULL) + return -1; + + const char *hex = consensus_cache_entry_get_value(ent, label); + if (hex == NULL) + return -1; + + int n = base16_decode((char*)digest_out, DIGEST256_LEN, hex, strlen(hex)); + if (n != DIGEST256_LEN) + return -2; + else + return 0; +} + /** * Helper: look for a consensus with the given flavor and * valid_after time in the cache. Return that consensus if it's @@ -403,11 +426,6 @@ consdiffmgr_validate(void) consensus_cache_find_all(objects, cdm_cache_get(), NULL, NULL); SMARTLIST_FOREACH_BEGIN(objects, consensus_cache_entry_t *, obj) { - const char *lv_sha3 = - consensus_cache_entry_get_value(obj, LABEL_SHA3_DIGEST); - if (lv_sha3 == NULL) - continue; - uint8_t sha3_expected[DIGEST256_LEN]; uint8_t sha3_received[DIGEST256_LEN]; int r = cdm_entry_get_sha3_value(sha3_expected, obj, LABEL_SHA3_DIGEST);

1 0

[tor/master] consdiffmgr: add tests for cdm_entry_get_sha3_value
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit 6cc21aa89cc1b9dea6e5256722597e3bf07d1a20 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Apr 16 15:36:20 2017 -0400 consdiffmgr: add tests for cdm_entry_get_sha3_value --- src/or/consdiffmgr.c | 2 +- src/or/consdiffmgr.h | 3 +++ src/test/test_consdiffmgr.c | 41 ++++++++++++++++++++++++++++++++++++++++- 3 files changed, 44 insertions(+), 2 deletions(-) diff --git a/src/or/consdiffmgr.c b/src/or/consdiffmgr.c index 1c9c2a9..59d0f28 100644 --- a/src/or/consdiffmgr.c +++ b/src/or/consdiffmgr.c @@ -320,7 +320,7 @@ cdm_labels_prepend_sha3(config_line_t **labels, * given label, set digest_out to that value (decoded), and return 0. * * Return -1 if there is no such label, and -2 if it is badly formatted. */ -static int +STATIC int cdm_entry_get_sha3_value(uint8_t *digest_out, consensus_cache_entry_t *ent, const char *label) diff --git a/src/or/consdiffmgr.h b/src/or/consdiffmgr.h index 3e89ea2..b6b7555 100644 --- a/src/or/consdiffmgr.h +++ b/src/or/consdiffmgr.h @@ -39,6 +39,9 @@ int consdiffmgr_validate(void); STATIC consensus_cache_t *cdm_cache_get(void); STATIC consensus_cache_entry_t *cdm_cache_lookup_consensus( consensus_flavor_t flavor, time_t valid_after); +STATIC int cdm_entry_get_sha3_value(uint8_t *digest_out, + consensus_cache_entry_t *ent, + const char *label); #endif #endif diff --git a/src/test/test_consdiffmgr.c b/src/test/test_consdiffmgr.c index a1b5983..0035029 100644 --- a/src/test/test_consdiffmgr.c +++ b/src/test/test_consdiffmgr.c @@ -221,6 +221,45 @@ test_consdiffmgr_init_failure(void *arg) #endif static void +test_consdiffmgr_sha3_helper(void *arg) +{ + (void) arg; + consensus_cache_t *cache = cdm_cache_get(); // violate abstraction barrier + config_line_t *lines = NULL; + char *mem_op_hex_tmp = NULL; + config_line_prepend(&lines, "good-sha", + "F00DF00DF00DF00DF00DF00DF00DF00D" + "F00DF00DF00DF00DF00DF00DF00DF00D"); + config_line_prepend(&lines, "short-sha", + "F00DF00DF00DF00DF00DF00DF00DF00D" + "F00DF00DF00DF00DF00DF00DF00DF0"); + config_line_prepend(&lines, "long-sha", + "F00DF00DF00DF00DF00DF00DF00DF00D" + "F00DF00DF00DF00DF00DF00DF00DF00DF00D"); + config_line_prepend(&lines, "not-sha", + "F00DF00DF00DF00DF00DF00DF00DF00D" + "F00DF00DF00DF00DF00DF00DF00DXXXX"); + consensus_cache_entry_t *ent = + consensus_cache_add(cache, lines, (const uint8_t *)"Hi there", 8); + + uint8_t buf[DIGEST256_LEN]; + tt_int_op(-1, OP_EQ, cdm_entry_get_sha3_value(buf, NULL, "good-sha")); + tt_int_op(0, OP_EQ, cdm_entry_get_sha3_value(buf, ent, "good-sha")); + test_memeq_hex(buf, "F00DF00DF00DF00DF00DF00DF00DF00D" + "F00DF00DF00DF00DF00DF00DF00DF00D"); + + tt_int_op(-1, OP_EQ, cdm_entry_get_sha3_value(buf, ent, "missing-sha")); + tt_int_op(-2, OP_EQ, cdm_entry_get_sha3_value(buf, ent, "short-sha")); + tt_int_op(-2, OP_EQ, cdm_entry_get_sha3_value(buf, ent, "long-sha")); + tt_int_op(-2, OP_EQ, cdm_entry_get_sha3_value(buf, ent, "not-sha")); + + done: + consensus_cache_entry_decref(ent); + config_free_lines(lines); + tor_free(mem_op_hex_tmp); +} + +static void test_consdiffmgr_add(void *arg) { (void) arg; @@ -713,6 +752,7 @@ struct testcase_t consdiffmgr_tests[] = { #if 0 { "init_failure", test_consdiffmgr_init_failure, TT_FORK, NULL, NULL }, #endif + TEST(sha3_helper), TEST(add), TEST(make_diffs), TEST(diff_rules), @@ -724,7 +764,6 @@ struct testcase_t consdiffmgr_tests[] = { // XXXX Test: no duplicate diff job is launched when a job is pending. // XXXX Test: register status when no pending entry existed?? (bug) - // XXXX Test: cdm_entry_get_sha3_value cases. // XXXX Test: sha3 mismatch on validation // XXXX Test: non-cacheing cases of replyfn().

1 0

[tor/master] Remove a checklist item that was already tested
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit eb14faa0c1cb9f83d39e8b7aeb35bbe2788bea8c Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun Apr 16 17:13:39 2017 -0400 Remove a checklist item that was already tested The item referred to the cdm_ht_set_status() case where the item was not already in the hashtable. But that already happens naturally when we scan the directory on startup... and we already have a test for that. --- src/test/test_consdiffmgr.c | 1 - 1 file changed, 1 deletion(-) diff --git a/src/test/test_consdiffmgr.c b/src/test/test_consdiffmgr.c index 10da502..ec4e56c 100644 --- a/src/test/test_consdiffmgr.c +++ b/src/test/test_consdiffmgr.c @@ -876,7 +876,6 @@ struct testcase_t consdiffmgr_tests[] = { TEST(cleanup_old_diffs), TEST(validate), - // XXXX Test: register status when no pending entry existed?? (bug) // XXXX Test: non-cacheing cases of replyfn(). END_OF_TESTCASES

1 0

[tor/master] Merge branch 'consdiffmgr_squashed'
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit b7567a6282e0bca38f4412ce0d571445a0ceda50 Merge: 9ba10d7 eb14faa Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Apr 24 11:02:22 2017 -0400 Merge branch 'consdiffmgr_squashed' src/common/confline.c | 18 + src/common/confline.h | 2 + src/common/workqueue.h | 2 +- src/or/conscache.c | 19 +- src/or/conscache.h | 4 + src/or/consdiffmgr.c | 1116 +++++++++++++++++++++++++++++++++++++++++++ src/or/consdiffmgr.h | 48 ++ src/or/cpuworker.c | 14 + src/or/cpuworker.h | 6 + src/or/include.am | 2 + src/test/include.am | 1 + src/test/test.c | 1 + src/test/test.h | 1 + src/test/test_conscache.c | 7 +- src/test/test_consdiffmgr.c | 883 ++++++++++++++++++++++++++++++++++ 15 files changed, 2114 insertions(+), 10 deletions(-)

1 0

[tor/master] Add a config_line_prepend() function
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit 222122450c1e879989c440088c01eaa95e4d6980 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Apr 6 14:18:50 2017 -0400 Add a config_line_prepend() function --- src/common/confline.c | 18 ++++++++++++++++++ src/common/confline.h | 2 ++ 2 files changed, 20 insertions(+) diff --git a/src/common/confline.c b/src/common/confline.c index 36f4c87..d4468f8 100644 --- a/src/common/confline.c +++ b/src/common/confline.c @@ -30,6 +30,24 @@ config_line_append(config_line_t **lst, (*lst) = newline; } +/** Helper: allocate a new configuration option mapping 'key' to 'val', + * and prepend it to *lst */ +void +config_line_prepend(config_line_t **lst, + const char *key, + const char *val) +{ + tor_assert(lst); + + config_line_t *newline; + + newline = tor_malloc_zero(sizeof(config_line_t)); + newline->key = tor_strdup(key); + newline->value = tor_strdup(val); + newline->next = *lst; + *lst = newline; +} + /** Return the first line in lines whose key is exactly key, or * NULL if no such key exists. * diff --git a/src/common/confline.h b/src/common/confline.h index c695bf6..477c692 100644 --- a/src/common/confline.h +++ b/src/common/confline.h @@ -31,6 +31,8 @@ typedef struct config_line_t { void config_line_append(config_line_t **lst, const char *key, const char *val); +void config_line_prepend(config_line_t **lst, + const char *key, const char *val); config_line_t *config_lines_dup(const config_line_t *inp); config_line_t *config_lines_dup_and_filter(const config_line_t *inp, const char *key);

1 0

[tor/master] conscache.c: do not match entries that are slated for removal.
by nickm＠torproject.org 24 Apr '17

24 Apr '17

commit 06ecb9432f4596f10e73f82bb1ff6677060756f9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Apr 11 15:50:06 2017 -0400 conscache.c: do not match entries that are slated for removal. --- src/or/conscache.c | 15 ++++++++++----- src/test/test_conscache.c | 7 +++---- 2 files changed, 13 insertions(+), 9 deletions(-) diff --git a/src/or/conscache.c b/src/or/conscache.c index 2a6e144..a186163 100644 --- a/src/or/conscache.c +++ b/src/or/conscache.c @@ -174,6 +174,8 @@ consensus_cache_find_first(consensus_cache_t *cache, * Given a cache, add every entry to out for which * key=value. If key is NULL, add every entry. * + * Do not add any entry that has been marked for removal. + * * Does not adjust reference counts. */ void @@ -182,12 +184,15 @@ consensus_cache_find_all(smartlist_t *out, const char *key, const char *value) { - if (! key) { - smartlist_add_all(out, cache->entries); - return; - } - SMARTLIST_FOREACH_BEGIN(cache->entries, consensus_cache_entry_t *, ent) { + if (ent->can_remove == 1) { + /* We want to delete this; pretend it isn't there. */ + continue; + } + if (! key) { + smartlist_add(out, ent); + continue; + } const char *found_val = consensus_cache_entry_get_value(ent, key); if (found_val && !strcmp(value, found_val)) { smartlist_add(out, ent); diff --git a/src/test/test_conscache.c b/src/test/test_conscache.c index 12184f0..c316411 100644 --- a/src/test/test_conscache.c +++ b/src/test/test_conscache.c @@ -200,8 +200,7 @@ test_conscache_cleanup(void *arg) tt_assert(e_tmp); tt_assert(consensus_cache_entry_is_mapped(e_tmp)); e_tmp = consensus_cache_find_first(cache, "index", "7"); - tt_assert(e_tmp); - tt_assert(consensus_cache_entry_is_mapped(e_tmp)); + tt_assert(e_tmp == NULL); // not found because pending deletion. /* Delete the pending-deletion items. */ consensus_cache_delete_pending(cache); @@ -210,12 +209,12 @@ test_conscache_cleanup(void *arg) consensus_cache_find_all(entries, cache, NULL, NULL); int n = smartlist_len(entries); smartlist_free(entries); - tt_int_op(n, OP_EQ, 20 - 1); /* 1 entry was deleted */ + tt_int_op(n, OP_EQ, 20 - 2); /* 1 entry was deleted; 1 is not-found. */ } e_tmp = consensus_cache_find_first(cache, "index", "7"); // refcnt == 1... tt_assert(e_tmp == NULL); // so deleted. e_tmp = consensus_cache_find_first(cache, "index", "14"); // refcnt == 2 - tt_assert(e_tmp); // so, not deleted. + tt_assert(e_tmp == NULL); // not deleted; but not found. /* Now do lazy unmapping. */ // should do nothing.

1 0