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

[tor/master] Consensus diff backend from Daniel Martí GSOC project.
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit 590ffdb2c9e0e3516fdb113cfa8b7a3f888cb970 Author: Daniel Martí <mvdan(a)mvdan.cc> Date: Tue Mar 7 09:58:30 2017 -0500 Consensus diff backend from Daniel Martí GSOC project. (This commit was extracted by nickm based on the final outcome of the project, taking only the changes in the files touched by this commit from the consdiff_rebased branch. The directory-system changes are going to get worked on separately.) --- src/common/log.c | 2 +- src/common/torlog.h | 4 +- src/or/consdiff.c | 1032 ++++++++++++++++++++++++++++++++++++++++++++++ src/or/consdiff.h | 22 + src/or/include.am | 2 + src/test/Makefile.nmake | 2 +- src/test/include.am | 1 + src/test/test.c | 1 + src/test/test.h | 1 + src/test/test_consdiff.c | 966 +++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 2030 insertions(+), 3 deletions(-) diff --git a/src/common/log.c b/src/common/log.c index 5f7151b..8489002 100644 --- a/src/common/log.c +++ b/src/common/log.c @@ -1177,7 +1177,7 @@ static const char *domain_list[] = { "GENERAL", "CRYPTO", "NET", "CONFIG", "FS", "PROTOCOL", "MM", "HTTP", "APP", "CONTROL", "CIRC", "REND", "BUG", "DIR", "DIRSERV", "OR", "EDGE", "ACCT", "HIST", "HANDSHAKE", "HEARTBEAT", "CHANNEL", - "SCHED", "GUARD", NULL + "SCHED", "GUARD", "CONSDIFF", NULL }; /** Return a bitmask for the log domain for which <b>domain</b> is the name, diff --git a/src/common/torlog.h b/src/common/torlog.h index bc95785..a56f5a8 100644 --- a/src/common/torlog.h +++ b/src/common/torlog.h @@ -101,8 +101,10 @@ #define LD_SCHED (1u<<22) /** Guard nodes */ #define LD_GUARD (1u<<23) +/** Generation and application of consensus diffs. */ +#define LD_CONSDIFF (1u<<24) /** Number of logging domains in the code. */ -#define N_LOGGING_DOMAINS 24 +#define N_LOGGING_DOMAINS 25 /** This log message is not safe to send to a callback-based logger * immediately. Used as a flag, not a log domain. */ diff --git a/src/or/consdiff.c b/src/or/consdiff.c new file mode 100644 index 0000000..7a67498 --- /dev/null +++ b/src/or/consdiff.c @@ -0,0 +1,1032 @@ +/* Copyright (c) 2014, Daniel Martí + * Copyright (c) 2014, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file consdiff.c + * \brief Consensus diff implementation, including both the generation and the + * application of diffs in a minimal ed format. + * + * The consensus diff application is done in consdiff_apply_diff, which relies + * on apply_ed_diff for the main ed diff part and on some digest helper + * functions to check the digest hashes found in the consensus diff header. + * + * The consensus diff generation is more complex. consdiff_gen_diff generates + * it, relying on gen_ed_diff to generate the ed diff and some digest helper + * functions to generate the digest hashes. + * + * gen_ed_diff is the tricky bit. In it simplest form, it will take quadratic + * time and linear space to generate an ed diff given two smartlists. As shown + * in its comment section, calling calc_changes on the entire two consensuses + * will calculate what is to be added and what is to be deleted in the diff. + * Its comment section briefly explains how it works. + * + * In our case specific to consensuses, we take advantage of the fact that + * consensuses list routers sorted by their identities. We use that + * information to avoid running calc_changes on the whole smartlists. + * gen_ed_diff will navigate through the two consensuses identity by identity + * and will send small couples of slices to calc_changes, keeping the running + * time near-linear. This is explained in more detail in the gen_ed_diff + * comments. + **/ + +#include "or.h" +#include "consdiff.h" +#include "routerparse.h" + +static const char* ns_diff_version = "network-status-diff-version 1"; +static const char* hash_token = "hash"; + +/** Data structure to define a slice of a smarltist. */ +typedef struct { + /** + * Smartlist that this slice is made from. + * References the whole original smartlist that the slice was made out of. + * */ + smartlist_t *list; + /** Starting position of the slice in the smartlist. */ + int offset; + /** Length of the slice, i.e. the number of elements it holds. */ + int len; +} smartlist_slice_t; + +/** Create (allocate) a new slice from a smartlist. Assumes that the start + * and the end indexes are within the bounds of the initial smartlist. The end + * element is not part of the resulting slice. If end is -1, the slice is to + * reach the end of the smartlist. + */ +static smartlist_slice_t * +smartlist_slice(smartlist_t *list, int start, int end) +{ + int list_len = smartlist_len(list); + tor_assert(start >= 0); + tor_assert(start <= list_len); + if (end == -1) { + end = list_len; + } + tor_assert(start <= end); + + smartlist_slice_t *slice = tor_malloc(sizeof(smartlist_slice_t)); + slice->list = list; + slice->offset = start; + slice->len = end - start; + return slice; +} + +/** Helper: Compute the longest common subsequence lengths for the two slices. + * Used as part of the diff generation to find the column at which to split + * slice2 while still having the optimal solution. + * If direction is -1, the navigation is reversed. Otherwise it must be 1. + * The length of the resulting integer array is that of the second slice plus + * one. + */ +static int * +lcs_lengths(smartlist_slice_t *slice1, smartlist_slice_t *slice2, + int direction) +{ + size_t a_size = sizeof(int) * (slice2->len+1); + + /* Resulting lcs lengths. */ + int *result = tor_malloc_zero(a_size); + /* Copy of the lcs lengths from the last iteration. */ + int *prev = tor_malloc(a_size); + + tor_assert(direction == 1 || direction == -1); + + int si = slice1->offset; + if (direction == -1) { + si += (slice1->len-1); + } + + for (int i = 0; i < slice1->len; ++i, si+=direction) { + + const char *line1 = smartlist_get(slice1->list, si); + /* Store the last results. */ + memcpy(prev, result, a_size); + + int sj = slice2->offset; + if (direction == -1) { + sj += (slice2->len-1); + } + + for (int j = 0; j < slice2->len; ++j, sj+=direction) { + + const char *line2 = smartlist_get(slice2->list, sj); + if (!strcmp(line1, line2)) { + /* If the lines are equal, the lcs is one line longer. */ + result[j + 1] = prev[j] + 1; + } else { + /* If not, see what lcs parent path is longer. */ + result[j + 1] = MAX(result[j], prev[j + 1]); + } + } + } + tor_free(prev); + return result; +} + +/** Helper: Trim any number of lines that are equally at the start or the end + * of both slices. + */ +static void +trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2) +{ + while (slice1->len>0 && slice2->len>0) { + const char *line1 = smartlist_get(slice1->list, slice1->offset); + const char *line2 = smartlist_get(slice2->list, slice2->offset); + if (strcmp(line1, line2)) { + break; + } + slice1->offset++; slice1->len--; + slice2->offset++; slice2->len--; + } + + int i1 = (slice1->offset+slice1->len)-1; + int i2 = (slice2->offset+slice2->len)-1; + + while (slice1->len>0 && slice2->len>0) { + const char *line1 = smartlist_get(slice1->list, i1); + const char *line2 = smartlist_get(slice2->list, i2); + if (strcmp(line1, line2)) { + break; + } + i1--; + slice1->len--; + i2--; + slice2->len--; + } +} + +/** Like smartlist_string_pos, but limited to the bounds of the slice. + */ +static int +smartlist_slice_string_pos(smartlist_slice_t *slice, const char *string) +{ + int end = slice->offset + slice->len; + for (int i = slice->offset; i < end; ++i) { + const char *el = smartlist_get(slice->list, i); + if (!strcmp(el, string)) { + return i; + } + } + return -1; +} + +/** Helper: Set all the appropriate changed booleans to true. The first slice + * must be of length 0 or 1. All the lines of slice1 and slice2 which are not + * present in the other slice will be set to changed in their bool array. + * The two changed bool arrays are passed in the same order as the slices. + */ +static void +set_changed(bitarray_t *changed1, bitarray_t *changed2, + smartlist_slice_t *slice1, smartlist_slice_t *slice2) +{ + int toskip = -1; + tor_assert(slice1->len == 0 || slice1->len == 1); + + if (slice1->len == 1) { + const char *line_common = smartlist_get(slice1->list, slice1->offset); + toskip = smartlist_slice_string_pos(slice2, line_common); + if (toskip == -1) { + bitarray_set(changed1, slice1->offset); + } + } + int end = slice2->offset + slice2->len; + for (int i = slice2->offset; i < end; ++i) { + if (i != toskip) { + bitarray_set(changed2, i); + } + } +} + +/* + * Helper: Given that slice1 has been split by half into top and bot, we want + * to fetch the column at which to split slice2 so that we are still on track + * to the optimal diff solution, i.e. the shortest one. We use lcs_lengths + * since the shortest diff is just another way to say the longest common + * subsequence. + */ +static int +optimal_column_to_split(smartlist_slice_t *top, smartlist_slice_t *bot, + smartlist_slice_t *slice2) +{ + int *lens_top = lcs_lengths(top, slice2, 1); + int *lens_bot = lcs_lengths(bot, slice2, -1); + int column=0, max_sum=-1; + + for (int i = 0; i < slice2->len+1; ++i) { + int sum = lens_top[i] + lens_bot[slice2->len-i]; + if (sum > max_sum) { + column = i; + max_sum = sum; + } + } + tor_free(lens_top); + tor_free(lens_bot); + + return column; +} + +/** + * Helper: Figure out what elements are new or gone on the second smartlist + * relative to the first smartlist, and store the booleans in the bitarrays. + * True on the first bitarray means the element is gone, true on the second + * bitarray means it's new. + * + * In its base case, either of the smartlists is of length <= 1 and we can + * quickly see what elements are new or are gone. In the other case, we will + * split one smartlist by half and we'll use optimal_column_to_split to find + * the optimal column at which to split the second smartlist so that we are + * finding the smallest diff possible. + */ +static void +calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, + bitarray_t *changed1, bitarray_t *changed2) +{ + trim_slices(slice1, slice2); + + if (slice1->len <= 1) { + set_changed(changed1, changed2, slice1, slice2); + + } else if (slice2->len <= 1) { + set_changed(changed2, changed1, slice2, slice1); + + /* Keep on splitting the slices in two. */ + } else { + + smartlist_slice_t *top, *bot, *left, *right; + + /* Split the first slice in half. */ + int mid = slice1->len/2; + top = smartlist_slice(slice1->list, slice1->offset, slice1->offset+mid); + bot = smartlist_slice(slice1->list, slice1->offset+mid, + slice1->offset+slice1->len); + + /* Split the second slice by the optimal column. */ + int mid2 = optimal_column_to_split(top, bot, slice2); + left = smartlist_slice(slice2->list, slice2->offset, slice2->offset+mid2); + right = smartlist_slice(slice2->list, slice2->offset+mid2, + slice2->offset+slice2->len); + + calc_changes(top, left, changed1, changed2); + calc_changes(bot, right, changed1, changed2); + tor_free(top); + tor_free(bot); + tor_free(left); + tor_free(right); + } +} + +/* This table is from crypto.c. The SP and PAD defines are different. */ +#define X 255 +#define SP X +#define PAD X +static const uint8_t base64_compare_table[256] = { + X, X, X, X, X, X, X, X, X, SP, SP, SP, X, SP, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + SP, X, X, X, X, X, X, X, X, X, X, 62, X, X, X, 63, + 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, X, X, X, PAD, X, X, + X, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, + 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, X, X, X, X, X, + X, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, + 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, + X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, +}; + +/** Helper: Get the identity hash from a router line, assuming that the line + * at least appears to be a router line and thus starts with "r ". + */ +static const char * +get_id_hash(const char *r_line) +{ + r_line += strlen("r "); + + /* Skip the router name. */ + const char *hash = strchr(r_line, ' '); + if (!hash) { + return NULL; + } + + hash++; + const char *hash_end = hash; + /* Stop when the first non-base64 character is found. Use unsigned chars to + * avoid negative indexes causing crashes. + */ + while (base64_compare_table[*((unsigned char*)hash_end)] != X) { + hash_end++; + } + + /* Empty hash. */ + if (hash_end == hash) { + return NULL; + } + + return hash; +} + +/** Helper: Check that a line is a valid router entry. We must at least be + * able to fetch a proper identity hash from it for it to be valid. + */ +static int +is_valid_router_entry(const char *line) +{ + if (strcmpstart(line, "r ") != 0) { + return 0; + } + return (get_id_hash(line) != NULL); +} + +/** Helper: Find the next router line starting at the current position. + * Assumes that cur is lower than the length of the smartlist, i.e. it is a + * line within the bounds of the consensus. The only exception is when we + * don't want to skip the first line, in which case cur will be -1. + */ +static int +next_router(smartlist_t *cons, int cur) +{ + int len = smartlist_len(cons); + tor_assert(cur >= -1 && cur < len); + + if (++cur >= len) { + return len; + } + + const char *line = smartlist_get(cons, cur); + while (!is_valid_router_entry(line)) { + if (++cur >= len) { + return len; + } + line = smartlist_get(cons, cur); + } + return cur; +} + +/** Helper: compare two base64-encoded identity hashes which may be of + * different lengths. Comparison ends when the first non-base64 char is found. + */ +static int +base64cmp(const char *hash1, const char *hash2) +{ + /* NULL is always lower, useful for last_hash which starts at NULL. */ + if (!hash1 && !hash2) { + return 0; + } + if (!hash1) { + return -1; + } + if (!hash2) { + return 1; + } + + /* Don't index with a char; char may be signed. */ + const unsigned char *a = (unsigned char*)hash1; + const unsigned char *b = (unsigned char*)hash2; + while (1) { + uint8_t av = base64_compare_table[*a]; + uint8_t bv = base64_compare_table[*b]; + if (av == X) { + if (bv == X) { + /* Both ended with exactly the same characters. */ + return 0; + } else { + /* hash2 goes on longer than hash1 and thus hash1 is lower. */ + return -1; + } + } else if (bv == X) { + /* hash1 goes on longer than hash2 and thus hash1 is greater. */ + return 1; + } else if (av < bv) { + /* The first difference shows that hash1 is lower. */ + return -1; + } else if (av > bv) { + /* The first difference shows that hash1 is greater. */ + return 1; + } else { + a++; + b++; + } + } +} + +/** Generate an ed diff as a smartlist from two consensuses, also given as + * smartlists. Will return NULL if the diff could not be generated, which can + * happen if any lines the script had to add matched "." or if the routers + * were not properly ordered. + * + * This implementation is consensus-specific. To generate an ed diff for any + * given input in quadratic time, you can replace all the code until the + * navigation in reverse order with the following: + * + * int len1 = smartlist_len(cons1); + * int len2 = smartlist_len(cons2); + * bitarray_t *changed1 = bitarray_init_zero(len1); + * bitarray_t *changed2 = bitarray_init_zero(len2); + * cons1_sl = smartlist_slice(cons1, 0, -1); + * cons2_sl = smartlist_slice(cons2, 0, -1); + * calc_changes(cons1_sl, cons2_sl, changed1, changed2); + */ +static smartlist_t * +gen_ed_diff(smartlist_t *cons1, smartlist_t *cons2) +{ + int len1 = smartlist_len(cons1); + int len2 = smartlist_len(cons2); + smartlist_t *result = smartlist_new(); + + /* Initialize the changed bitarrays to zero, so that calc_changes only needs + * to set the ones that matter and leave the rest untouched. + */ + bitarray_t *changed1 = bitarray_init_zero(len1); + bitarray_t *changed2 = bitarray_init_zero(len2); + int i1=-1, i2=-1; + int start1=0, start2=0; + + const char *hash1 = NULL; + const char *hash2 = NULL; + + /* To check that hashes are ordered properly */ + const char *last_hash1 = NULL; + const char *last_hash2 = NULL; + + /* i1 and i2 are initialized at the first line of each consensus. They never + * reach past len1 and len2 respectively, since next_router doesn't let that + * happen. i1 and i2 are advanced by at least one line at each iteration as + * long as they have not yet reached len1 and len2, so the loop is + * guaranteed to end, and each pair of (i1,i2) will be inspected at most + * once. + */ + while (i1 < len1 || i2 < len2) { + + /* Advance each of the two navigation positions by one router entry if not + * yet at the end. + */ + if (i1 < len1) { + i1 = next_router(cons1, i1); + if (i1 != len1) { + last_hash1 = hash1; + hash1 = get_id_hash(smartlist_get(cons1, i1)); + if (base64cmp(hash1, last_hash1) <= 0) { + log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because " + "the base consensus doesn't have its router entries " + "sorted properly."); + goto error_cleanup; + } + } + } + + if (i2 < len2) { + i2 = next_router(cons2, i2); + if (i2 != len2) { + last_hash2 = hash2; + hash2 = get_id_hash(smartlist_get(cons2, i2)); + if (base64cmp(hash2, last_hash2) <= 0) { + log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because " + "the target consensus doesn't have its router entries " + "sorted properly."); + goto error_cleanup; + } + } + } + + /* If we have reached the end of both consensuses, there is no need to + * compare hashes anymore, since this is the last iteration. + */ + if (i1 < len1 || i2 < len2) { + + /* Keep on advancing the lower (by identity hash sorting) position until + * we have two matching positions. The only other possible outcome is + * that a lower position reaches the end of the consensus before it can + * reach a hash that is no longer the lower one. Since there will always + * be a lower hash for as long as the loop runs, one of the two indexes + * will always be incremented, thus assuring that the loop must end + * after a finite number of iterations. If that cannot be because said + * consensus has already reached the end, both are extended to their + * respecting ends since we are done. + */ + int cmp = base64cmp(hash1, hash2); + while (cmp != 0) { + if (i1 < len1 && cmp < 0) { + i1 = next_router(cons1, i1); + if (i1 == len1) { + /* We finished the first consensus, so grab all the remaining + * lines of the second consensus and finish up. + */ + i2 = len2; + break; + } + last_hash1 = hash1; + hash1 = get_id_hash(smartlist_get(cons1, i1)); + if (base64cmp(hash1, last_hash1) <= 0) { + log_warn(LD_CONSDIFF, "Refusing to generate consensus diff " + "because the base consensus doesn't have its router entries " + "sorted properly."); + goto error_cleanup; + } + } else if (i2 < len2 && cmp > 0) { + i2 = next_router(cons2, i2); + if (i2 == len2) { + /* We finished the second consensus, so grab all the remaining + * lines of the first consensus and finish up. + */ + i1 = len1; + break; + } + last_hash2 = hash2; + hash2 = get_id_hash(smartlist_get(cons2, i2)); + if (base64cmp(hash2, last_hash2) <= 0) { + log_warn(LD_CONSDIFF, "Refusing to generate consensus diff " + "because the target consensus doesn't have its router entries " + "sorted properly."); + goto error_cleanup; + } + } else { + i1 = len1; + i2 = len2; + break; + } + cmp = base64cmp(hash1, hash2); + } + } + + /* Make slices out of these chunks (up to the common router entry) and + * calculate the changes for them. + * Error if any of the two slices are longer than 10K lines. That should + * never happen with any pair of real consensuses. Feeding more than 10K + * lines to calc_changes would be very slow anyway. + */ +#define MAX_LINE_COUNT (10000) + if (i1-start1 > MAX_LINE_COUNT || i2-start2 > MAX_LINE_COUNT) { + log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because " + "we found too few common router ids."); + goto error_cleanup; + } + + smartlist_slice_t *cons1_sl = smartlist_slice(cons1, start1, i1); + smartlist_slice_t *cons2_sl = smartlist_slice(cons2, start2, i2); + calc_changes(cons1_sl, cons2_sl, changed1, changed2); + tor_free(cons1_sl); + tor_free(cons2_sl); + start1 = i1, start2 = i2; + } + + /* Navigate the changes in reverse order and generate one ed command for + * each chunk of changes. + */ + i1=len1-1, i2=len2-1; + while (i1 > 0 || i2 > 0) { + + int start1x, start2x, end1, end2, added, deleted; + + /* We are at a point were no changed bools are true, so just keep going. */ + if (!(i1 >= 0 && bitarray_is_set(changed1, i1)) && + !(i2 >= 0 && bitarray_is_set(changed2, i2))) { + if (i1 >= 0) { + i1--; + } + if (i2 >= 0) { + i2--; + } + continue; + } + + end1 = i1, end2 = i2; + + /* Grab all contiguous changed lines */ + while (i1 >= 0 && bitarray_is_set(changed1, i1)) { + i1--; + } + while (i2 >= 0 && bitarray_is_set(changed2, i2)) { + i2--; + } + + start1x = i1+1, start2x = i2+1; + added = end2-i2, deleted = end1-i1; + + if (added == 0) { + if (deleted == 1) { + smartlist_add_asprintf(result, "%id", start1x+1); + } else { + smartlist_add_asprintf(result, "%i,%id", start1x+1, start1x+deleted); + } + + } else { + int i; + if (deleted == 0) { + smartlist_add_asprintf(result, "%ia", start1x); + } else if (deleted == 1) { + smartlist_add_asprintf(result, "%ic", start1x+1); + } else { + smartlist_add_asprintf(result, "%i,%ic", start1x+1, start1x+deleted); + } + + for (i = start2x; i <= end2; ++i) { + const char *line = smartlist_get(cons2, i); + if (!strcmp(line, ".")) { + log_warn(LD_CONSDIFF, "Cannot generate consensus diff because " + "one of the lines to be added is \".\"."); + goto error_cleanup; + } + smartlist_add(result, tor_strdup(line)); + } + smartlist_add_asprintf(result, "."); + } + } + + bitarray_free(changed1); + bitarray_free(changed2); + + return result; + + error_cleanup: + + bitarray_free(changed1); + bitarray_free(changed2); + + SMARTLIST_FOREACH(result, char*, line, tor_free(line)); + smartlist_free(result); + + return NULL; +} + +/** Apply the ed diff to the consensus and return a new consensus, also as a + * line-based smartlist. Will return NULL if the ed diff is not properly + * formatted. + */ +static smartlist_t * +apply_ed_diff(smartlist_t *cons1, smartlist_t *diff) +{ + int diff_len = smartlist_len(diff); + int j = smartlist_len(cons1); + smartlist_t *cons2 = smartlist_new(); + + for (int i=0; i<diff_len; ++i) { + const char *diff_line = smartlist_get(diff, i); + char *endptr1, *endptr2; + + int start = (int)strtol(diff_line, &endptr1, 10); + int end; + if (endptr1 == diff_line) { + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "an ed command was missing a line number."); + goto error_cleanup; + } + + /* Two-item range */ + if (*endptr1 == ',') { + end = (int)strtol(endptr1+1, &endptr2, 10); + if (endptr2 == endptr1+1) { + goto error_cleanup; + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "an ed command was missing a range end line number."); + } + /* Incoherent range. */ + if (end <= start) { + goto error_cleanup; + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "an invalid range was found in an ed command."); + } + + /* We'll take <n1> as <n1>,<n1> for simplicity. */ + } else { + endptr2 = endptr1; + end = start; + } + + if (end > j) { + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "its commands are not properly sorted in reverse order."); + goto error_cleanup; + } + + if (*(endptr2+1) != '\0') { + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "an ed command longer than one char was found."); + goto error_cleanup; + } + + char action = *endptr2; + + switch (action) { + case 'a': + case 'c': + case 'd': + break; + default: + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "an unrecognised ed command was found."); + goto error_cleanup; + } + + /* Add unchanged lines. */ + for (; j > end; --j) { + const char *cons_line = smartlist_get(cons1, j-1); + smartlist_add(cons2, tor_strdup(cons_line)); + } + + /* Ignore removed lines. */ + if (action == 'c' || action == 'd') { + while (--j >= start) { + /* Skip line */ + } + } + + /* Add new lines in reverse order, since it will all be reversed at the + * end. + */ + if (action == 'a' || action == 'c') { + int added_end = i; + + i++; /* Skip the line with the range and command. */ + while (i < diff_len) { + if (!strcmp(smartlist_get(diff, i), ".")) { + break; + } + if (++i == diff_len) { + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "it has lines to be inserted that don't end with a \".\"."); + goto error_cleanup; + } + } + + int added_i = i-1; + + /* It would make no sense to add zero new lines. */ + if (added_i == added_end) { + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "it has an ed command that tries to insert zero lines."); + goto error_cleanup; + } + + while (added_i > added_end) { + const char *added_line = smartlist_get(diff, added_i--); + smartlist_add(cons2, tor_strdup(added_line)); + } + } + } + + /* Add remaining unchanged lines. */ + for (; j > 0; --j) { + const char *cons_line = smartlist_get(cons1, j-1); + smartlist_add(cons2, tor_strdup(cons_line)); + } + + /* Reverse the whole thing since we did it from the end. */ + smartlist_reverse(cons2); + return cons2; + + error_cleanup: + + SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + smartlist_free(cons2); + + return NULL; +} + +/** Generate a consensus diff as a smartlist from two given consensuses, also + * as smartlists. Will return NULL if the consensus diff could not be + * generated. Neither of the two consensuses are modified in any way, so it's + * up to the caller to free their resources. + */ +smartlist_t * +consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, + common_digests_t *digests1, common_digests_t *digests2) +{ + smartlist_t *ed_diff = gen_ed_diff(cons1, cons2); + /* ed diff could not be generated - reason already logged by gen_ed_diff. */ + if (!ed_diff) { + goto error_cleanup; + } + + /* See that the script actually produces what we want. */ + smartlist_t *ed_cons2 = apply_ed_diff(cons1, ed_diff); + if (!ed_cons2) { + log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because " + "the generated ed diff could not be tested to successfully generate " + "the target consensus."); + goto error_cleanup; + } + + int cons2_eq = smartlist_strings_eq(cons2, ed_cons2); + SMARTLIST_FOREACH(ed_cons2, char*, line, tor_free(line)); + smartlist_free(ed_cons2); + if (!cons2_eq) { + log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because " + "the generated ed diff did not generate the target consensus " + "successfully when tested."); + goto error_cleanup; + } + + char cons1_hash_hex[HEX_DIGEST256_LEN+1]; + char cons2_hash_hex[HEX_DIGEST256_LEN+1]; + base16_encode(cons1_hash_hex, HEX_DIGEST256_LEN+1, + digests1->d[DIGEST_SHA256], DIGEST256_LEN); + base16_encode(cons2_hash_hex, HEX_DIGEST256_LEN+1, + digests2->d[DIGEST_SHA256], DIGEST256_LEN); + + /* Create the resulting consensus diff. */ + smartlist_t *result = smartlist_new(); + smartlist_add_asprintf(result, "%s", ns_diff_version); + smartlist_add_asprintf(result, "%s %s %s", hash_token, + cons1_hash_hex, cons2_hash_hex); smartlist_add_all(result, ed_diff); + smartlist_free(ed_diff); + return result; + + error_cleanup: + + if (ed_diff) { + smartlist_free(ed_diff); + } + + return NULL; +} + +/** Fetch the digest of the base consensus in the consensus diff, encoded in + * base16 as found in the diff itself. digest1 and digest2 must be of length + * DIGEST256_LEN or larger if not NULL. digest1_hex and digest2_hex must be of + * length HEX_DIGEST256_LEN or larger if not NULL. + */ +int +consdiff_get_digests(smartlist_t *diff, + char *digest1, char *digest1_hex, + char *digest2, char *digest2_hex) +{ + smartlist_t *hash_words = NULL; + const char *format; + char cons1_hash[DIGEST256_LEN], cons2_hash[DIGEST256_LEN]; + char *cons1_hash_hex, *cons2_hash_hex; + if (smartlist_len(diff) < 3) { + log_info(LD_CONSDIFF, "The provided consensus diff is too short."); + goto error_cleanup; + } + + /* Check that it's the format and version we know. */ + format = smartlist_get(diff, 0); + if (strcmp(format, ns_diff_version)) { + log_warn(LD_CONSDIFF, "The provided consensus diff format is not known."); + goto error_cleanup; + } + + /* Grab the SHA256 base16 hashes. */ + hash_words = smartlist_new(); + smartlist_split_string(hash_words, smartlist_get(diff, 1), " ", 0, 0); + + /* There have to be three words, the first of which must be hash_token. */ + if (smartlist_len(hash_words) != 3 || + strcmp(smartlist_get(hash_words, 0), hash_token)) { + log_info(LD_CONSDIFF, "The provided consensus diff does not include " + "the necessary sha256 digests."); + goto error_cleanup; + } + + /* Expected hashes as found in the consensus diff header. They must be of + * length HEX_DIGEST256_LEN, normally 64 hexadecimal characters. + * If any of the decodings fail, error to make sure that the hashes are + * proper base16-encoded SHA256 digests. + */ + cons1_hash_hex = smartlist_get(hash_words, 1); + cons2_hash_hex = smartlist_get(hash_words, 2); + if (strlen(cons1_hash_hex) != HEX_DIGEST256_LEN || + strlen(cons2_hash_hex) != HEX_DIGEST256_LEN) { + log_info(LD_CONSDIFF, "The provided consensus diff includes " + "base16-encoded sha256 digests of incorrect size."); + goto error_cleanup; + } + + if (digest1_hex) { + strlcpy(digest1_hex, cons1_hash_hex, HEX_DIGEST256_LEN+1); + } + if (digest2_hex) { + strlcpy(digest2_hex, cons2_hash_hex, HEX_DIGEST256_LEN+1); + } + + if (base16_decode(cons1_hash, DIGEST256_LEN, + cons1_hash_hex, HEX_DIGEST256_LEN) != DIGEST256_LEN || + base16_decode(cons2_hash, DIGEST256_LEN, + cons2_hash_hex, HEX_DIGEST256_LEN) != DIGEST256_LEN) { + log_info(LD_CONSDIFF, "The provided consensus diff includes " + "malformed sha256 digests."); + goto error_cleanup; + } + + if (digest1) { + memcpy(digest1, cons1_hash, DIGEST256_LEN); + } + if (digest2) { + memcpy(digest2, cons2_hash, DIGEST256_LEN); + } + + SMARTLIST_FOREACH(hash_words, char *, cp, tor_free(cp)); + smartlist_free(hash_words); + return 0; + + error_cleanup: + + if (hash_words) { + SMARTLIST_FOREACH(hash_words, char *, cp, tor_free(cp)); + smartlist_free(hash_words); + } + return 1; +} + +/** Apply the consensus diff to the given consensus and return a new + * consensus, also as a line-based smartlist. Will return NULL if the diff + * could not be applied. Neither the consensus nor the diff are modified in + * any way, so it's up to the caller to free their resources. + */ +char * +consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, + common_digests_t *digests1) +{ + smartlist_t *cons2 = NULL; + char *cons2_str = NULL; + char e_cons1_hash[DIGEST256_LEN]; + char e_cons2_hash[DIGEST256_LEN]; + + if (consdiff_get_digests(diff, + e_cons1_hash, NULL, e_cons2_hash, NULL) != 0) { + goto error_cleanup; + } + + /* See that the consensus that was given to us matches its hash. */ + if (fast_memneq(digests1->d[DIGEST_SHA256], e_cons1_hash, + DIGEST256_LEN)) { + char hex_digest1[HEX_DIGEST256_LEN+1]; + char e_hex_digest1[HEX_DIGEST256_LEN+1]; + log_warn(LD_CONSDIFF, "Refusing to apply consensus diff because " + "the base consensus doesn't match its own digest as found in " + "the consensus diff header."); + base16_encode(hex_digest1, HEX_DIGEST256_LEN+1, + digests1->d[DIGEST_SHA256], DIGEST256_LEN); + base16_encode(e_hex_digest1, HEX_DIGEST256_LEN+1, + e_cons1_hash, DIGEST256_LEN); + log_warn(LD_CONSDIFF, "Expected: %s Found: %s\n", + hex_digest1, e_hex_digest1); + goto error_cleanup; + } + + /* Grab the ed diff and calculate the resulting consensus. */ + /* To avoid copying memory or iterating over all the elements, make a + * read-only smartlist without the two header lines. + */ + smartlist_t *ed_diff = tor_malloc(sizeof(smartlist_t)); + ed_diff->list = diff->list+2; + ed_diff->num_used = diff->num_used-2; + ed_diff->capacity = diff->capacity-2; + cons2 = apply_ed_diff(cons1, ed_diff); + tor_free(ed_diff); + + /* ed diff could not be applied - reason already logged by apply_ed_diff. */ + if (!cons2) { + goto error_cleanup; + } + + cons2_str = smartlist_join_strings(cons2, "\n", 1, NULL); + SMARTLIST_FOREACH(cons2, char *, cp, tor_free(cp)); + smartlist_free(cons2); + + common_digests_t cons2_digests; + if (router_get_networkstatus_v3_hashes(cons2_str, + &cons2_digests)<0) { + log_warn(LD_CONSDIFF, "Could not compute digests of the consensus " + "resulting from applying a consensus diff."); + goto error_cleanup; + } + + /* See that the resulting consensus matches its hash. */ + if (fast_memneq(cons2_digests.d[DIGEST_SHA256], e_cons2_hash, + DIGEST256_LEN)) { + log_warn(LD_CONSDIFF, "Refusing to apply consensus diff because " + "the resulting consensus doesn't match its own digest as found in " + "the consensus diff header."); + char hex_digest2[HEX_DIGEST256_LEN+1]; + char e_hex_digest2[HEX_DIGEST256_LEN+1]; + base16_encode(hex_digest2, HEX_DIGEST256_LEN+1, + cons2_digests.d[DIGEST_SHA256], DIGEST256_LEN); + base16_encode(e_hex_digest2, HEX_DIGEST256_LEN+1, + e_cons2_hash, DIGEST256_LEN); + log_warn(LD_CONSDIFF, "Expected: %s Found: %s\n", + hex_digest2, e_hex_digest2); + goto error_cleanup; + } + + return cons2_str; + + error_cleanup: + + if (cons2) { + SMARTLIST_FOREACH(cons2, char *, cp, tor_free(cp)); + smartlist_free(cons2); + } + if (cons2_str) { + tor_free(cons2_str); + } + + return NULL; +} + diff --git a/src/or/consdiff.h b/src/or/consdiff.h new file mode 100644 index 0000000..da8dbac --- /dev/null +++ b/src/or/consdiff.h @@ -0,0 +1,22 @@ +/* Copyright (c) 2014, Daniel Martí + * Copyright (c) 2014, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_CONSDIFF_H +#define TOR_CONSDIFF_H + +#include "or.h" + +smartlist_t * +consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, + common_digests_t *digests1, common_digests_t *digests2); +char * +consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, + common_digests_t *digests1); +int +consdiff_get_digests(smartlist_t *diff, + char *digest1, char *digest1_hex, + char *digest2, char *digest2_hex); + +#endif + diff --git a/src/or/include.am b/src/or/include.am index 4e54dec..d65d0d3 100644 --- a/src/or/include.am +++ b/src/or/include.am @@ -36,6 +36,7 @@ LIBTOR_A_SOURCES = \ src/or/connection.c \ src/or/connection_edge.c \ src/or/connection_or.c \ + src/or/consdiff.c \ src/or/control.c \ src/or/cpuworker.c \ src/or/dircollate.c \ @@ -151,6 +152,7 @@ ORHEADERS = \ src/or/connection.h \ src/or/connection_edge.h \ src/or/connection_or.h \ + src/or/consdiff.h \ src/or/control.h \ src/or/cpuworker.h \ src/or/dircollate.h \ diff --git a/src/test/Makefile.nmake b/src/test/Makefile.nmake index 0ba56d7..5751983 100644 --- a/src/test/Makefile.nmake +++ b/src/test/Makefile.nmake @@ -12,7 +12,7 @@ LIBS = ..\..\..\build-alpha\lib\libevent.lib \ crypt32.lib gdi32.lib user32.lib TEST_OBJECTS = test.obj test_addr.obj test_channel.obj test_channeltls.obj \ - test_containers.obj \ + test_consdiff.obj test_containers.obj \ test_controller_events.obj test_crypto.obj test_data.obj test_dir.obj \ test_checkdir.obj test_microdesc.obj test_pt.obj test_util.obj \ test_config.obj test_connection.obj \ diff --git a/src/test/include.am b/src/test/include.am index 1c0726f..23be3e8 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -86,6 +86,7 @@ src_test_test_SOURCES = \ src/test/test_compat_libevent.c \ src/test/test_config.c \ src/test/test_connection.c \ + src/test/test_consdiff.c \ src/test/test_containers.c \ src/test/test_controller.c \ src/test/test_controller_events.c \ diff --git a/src/test/test.c b/src/test/test.c index 866408e..98c44a9 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -1194,6 +1194,7 @@ struct testgroup_t testgroups[] = { { "compat/libevent/", compat_libevent_tests }, { "config/", config_tests }, { "connection/", connection_tests }, + { "consdiff/", consdiff_tests }, { "container/", container_tests }, { "control/", controller_tests }, { "control/event/", controller_event_tests }, diff --git a/src/test/test.h b/src/test/test.h index 2bd58f5..d390ffc 100644 --- a/src/test/test.h +++ b/src/test/test.h @@ -189,6 +189,7 @@ extern struct testcase_t circuituse_tests[]; extern struct testcase_t compat_libevent_tests[]; extern struct testcase_t config_tests[]; extern struct testcase_t connection_tests[]; +extern struct testcase_t consdiff_tests[]; extern struct testcase_t container_tests[]; extern struct testcase_t controller_tests[]; extern struct testcase_t controller_event_tests[]; diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c new file mode 100644 index 0000000..40fedf1 --- /dev/null +++ b/src/test/test_consdiff.c @@ -0,0 +1,966 @@ +/* Copyright (c) 2014, Daniel Martí + * Copyright (c) 2014, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "or.h" +#include "test.h" + +#include "consdiff.c" + +#ifndef OP_EQ +#define OP_EQ == +#endif +#ifndef OP_NE +#define OP_NE != +#endif + +static void +test_consdiff_smartlist_slice(void *arg) +{ + smartlist_t *sl = smartlist_new(); + smartlist_slice_t *sls; + + /* Create a regular smartlist. */ + (void)arg; + smartlist_add(sl, (void*)1); + smartlist_add(sl, (void*)2); + smartlist_add(sl, (void*)3); + smartlist_add(sl, (void*)4); + smartlist_add(sl, (void*)5); + + /* See if the slice was done correctly. */ + sls = smartlist_slice(sl, 2, 5); + tt_ptr_op(sl, OP_EQ, sls->list); + tt_ptr_op((void*)3, OP_EQ, smartlist_get(sls->list, sls->offset)); + tt_ptr_op((void*)5, OP_EQ, + smartlist_get(sls->list, sls->offset + (sls->len-1))); + tor_free(sls); + + /* See that using -1 as the end does get to the last element. */ + sls = smartlist_slice(sl, 2, -1); + tt_ptr_op(sl, OP_EQ, sls->list); + tt_ptr_op((void*)3, OP_EQ, smartlist_get(sls->list, sls->offset)); + tt_ptr_op((void*)5, OP_EQ, + smartlist_get(sls->list, sls->offset + (sls->len-1))); + + done: + tor_free(sls); + smartlist_free(sl); +} + +static void +test_consdiff_smartlist_slice_string_pos(void *arg) +{ + smartlist_t *sl = smartlist_new(); + smartlist_slice_t *sls; + + /* Create a regular smartlist. */ + (void)arg; + smartlist_split_string(sl, "a:d:c:a:b", ":", 0, 0); + + /* See that smartlist_slice_string_pos respects the bounds of the slice. */ + sls = smartlist_slice(sl, 2, 5); + tt_int_op(3, OP_EQ, smartlist_slice_string_pos(sls, "a")); + tt_int_op(-1, OP_EQ, smartlist_slice_string_pos(sls, "d")); + + done: + tor_free(sls); + if (sl) SMARTLIST_FOREACH(sl, char*, line, tor_free(line)); + smartlist_free(sl); +} + +static void +test_consdiff_lcs_lengths(void *arg) +{ + smartlist_t *sl1 = smartlist_new(); + smartlist_t *sl2 = smartlist_new(); + smartlist_slice_t *sls1, *sls2; + int *lengths1, *lengths2; + + /* Expected lcs lengths in regular and reverse order. */ + int e_lengths1[] = { 0, 1, 2, 3, 3, 4 }; + int e_lengths2[] = { 0, 1, 1, 2, 3, 4 }; + + (void)arg; + smartlist_split_string(sl1, "a:b:c:d:e", ":", 0, 0); + smartlist_split_string(sl2, "a:c:d:i:e", ":", 0, 0); + + sls1 = smartlist_slice(sl1, 0, -1); + sls2 = smartlist_slice(sl2, 0, -1); + + lengths1 = lcs_lengths(sls1, sls2, 1); + lengths2 = lcs_lengths(sls1, sls2, -1); + tt_mem_op(e_lengths1, OP_EQ, lengths1, sizeof(int) * 6); + tt_mem_op(e_lengths2, OP_EQ, lengths2, sizeof(int) * 6); + + done: + tor_free(lengths1); + tor_free(lengths2); + tor_free(sls1); + tor_free(sls2); + if (sl1) SMARTLIST_FOREACH(sl1, char*, line, tor_free(line)); + if (sl2) SMARTLIST_FOREACH(sl2, char*, line, tor_free(line)); + smartlist_free(sl1); + smartlist_free(sl2); +} + +static void +test_consdiff_trim_slices(void *arg) +{ + smartlist_t *sl1 = smartlist_new(); + smartlist_t *sl2 = smartlist_new(); + smartlist_t *sl3 = smartlist_new(); + smartlist_t *sl4 = smartlist_new(); + smartlist_slice_t *sls1, *sls2, *sls3, *sls4; + + (void)arg; + smartlist_split_string(sl1, "a:b:b:b:d", ":", 0, 0); + smartlist_split_string(sl2, "a:c:c:c:d", ":", 0, 0); + smartlist_split_string(sl3, "a:b:b:b:a", ":", 0, 0); + smartlist_split_string(sl4, "c:b:b:b:c", ":", 0, 0); + + sls1 = smartlist_slice(sl1, 0, -1); + sls2 = smartlist_slice(sl2, 0, -1); + sls3 = smartlist_slice(sl3, 0, -1); + sls4 = smartlist_slice(sl4, 0, -1); + + /* They should be trimmed by one line at each end. */ + tt_int_op(5, OP_EQ, sls1->len); + tt_int_op(5, OP_EQ, sls2->len); + trim_slices(sls1, sls2); + tt_int_op(3, OP_EQ, sls1->len); + tt_int_op(3, OP_EQ, sls2->len); + + /* They should not be trimmed at all. */ + tt_int_op(5, OP_EQ, sls3->len); + tt_int_op(5, OP_EQ, sls4->len); + trim_slices(sls3, sls4); + tt_int_op(5, OP_EQ, sls3->len); + tt_int_op(5, OP_EQ, sls4->len); + + done: + tor_free(sls1); + tor_free(sls2); + tor_free(sls3); + tor_free(sls4); + if (sl1) SMARTLIST_FOREACH(sl1, char*, line, tor_free(line)); + if (sl2) SMARTLIST_FOREACH(sl2, char*, line, tor_free(line)); + if (sl3) SMARTLIST_FOREACH(sl3, char*, line, tor_free(line)); + if (sl4) SMARTLIST_FOREACH(sl4, char*, line, tor_free(line)); + smartlist_free(sl1); + smartlist_free(sl2); + smartlist_free(sl3); + smartlist_free(sl4); +} + +static void +test_consdiff_set_changed(void *arg) +{ + smartlist_t *sl1 = smartlist_new(); + smartlist_t *sl2 = smartlist_new(); + bitarray_t *changed1 = bitarray_init_zero(4); + bitarray_t *changed2 = bitarray_init_zero(4); + smartlist_slice_t *sls1, *sls2; + + (void)arg; + smartlist_split_string(sl1, "a:b:a:a", ":", 0, 0); + smartlist_split_string(sl2, "a:a:a:a", ":", 0, 0); + + /* Length of sls1 is 0. */ + sls1 = smartlist_slice(sl1, 0, 0); + sls2 = smartlist_slice(sl2, 1, 3); + set_changed(changed1, changed2, sls1, sls2); + + /* The former is not changed, the latter changes all of its elements. */ + tt_assert(!bitarray_is_set(changed1, 0)); + tt_assert(!bitarray_is_set(changed1, 1)); + tt_assert(!bitarray_is_set(changed1, 2)); + tt_assert(!bitarray_is_set(changed1, 3)); + + tt_assert(!bitarray_is_set(changed2, 0)); + tt_assert(bitarray_is_set(changed2, 1)); + tt_assert(bitarray_is_set(changed2, 2)); + tt_assert(!bitarray_is_set(changed2, 3)); + bitarray_clear(changed2, 1); + bitarray_clear(changed2, 2); + + /* Length of sls1 is 1 and its element is in sls2. */ + tor_free(sls1); + sls1 = smartlist_slice(sl1, 0, 1); + set_changed(changed1, changed2, sls1, sls2); + + /* The latter changes all elements but the (first) common one. */ + tt_assert(!bitarray_is_set(changed1, 0)); + tt_assert(!bitarray_is_set(changed1, 1)); + tt_assert(!bitarray_is_set(changed1, 2)); + tt_assert(!bitarray_is_set(changed1, 3)); + + tt_assert(!bitarray_is_set(changed2, 0)); + tt_assert(!bitarray_is_set(changed2, 1)); + tt_assert(bitarray_is_set(changed2, 2)); + tt_assert(!bitarray_is_set(changed2, 3)); + bitarray_clear(changed2, 2); + + /* Length of sls1 is 1 and its element is not in sls2. */ + tor_free(sls1); + sls1 = smartlist_slice(sl1, 1, 2); + set_changed(changed1, changed2, sls1, sls2); + + /* The former changes its element, the latter changes all elements. */ + tt_assert(!bitarray_is_set(changed1, 0)); + tt_assert(bitarray_is_set(changed1, 1)); + tt_assert(!bitarray_is_set(changed1, 2)); + tt_assert(!bitarray_is_set(changed1, 3)); + + tt_assert(!bitarray_is_set(changed2, 0)); + tt_assert(bitarray_is_set(changed2, 1)); + tt_assert(bitarray_is_set(changed2, 2)); + tt_assert(!bitarray_is_set(changed2, 3)); + + done: + bitarray_free(changed1); + bitarray_free(changed2); + if (sl1) SMARTLIST_FOREACH(sl1, char*, line, tor_free(line)); + if (sl2) SMARTLIST_FOREACH(sl2, char*, line, tor_free(line)); + smartlist_free(sl1); + smartlist_free(sl2); + tor_free(sls1); + tor_free(sls2); +} + +static void +test_consdiff_calc_changes(void *arg) +{ + smartlist_t *sl1 = smartlist_new(); + smartlist_t *sl2 = smartlist_new(); + smartlist_slice_t *sls1, *sls2; + bitarray_t *changed1 = bitarray_init_zero(4); + bitarray_t *changed2 = bitarray_init_zero(4); + + (void)arg; + smartlist_split_string(sl1, "a:a:a:a", ":", 0, 0); + smartlist_split_string(sl2, "a:a:a:a", ":", 0, 0); + + sls1 = smartlist_slice(sl1, 0, -1); + sls2 = smartlist_slice(sl2, 0, -1); + calc_changes(sls1, sls2, changed1, changed2); + + /* Nothing should be set to changed. */ + tt_assert(!bitarray_is_set(changed1, 0)); + tt_assert(!bitarray_is_set(changed1, 1)); + tt_assert(!bitarray_is_set(changed1, 2)); + tt_assert(!bitarray_is_set(changed1, 3)); + + tt_assert(!bitarray_is_set(changed2, 0)); + tt_assert(!bitarray_is_set(changed2, 1)); + tt_assert(!bitarray_is_set(changed2, 2)); + tt_assert(!bitarray_is_set(changed2, 3)); + + SMARTLIST_FOREACH(sl2, char*, line, tor_free(line)); + smartlist_clear(sl2); + smartlist_split_string(sl2, "a:b:a:b", ":", 0, 0); + tor_free(sls1); + tor_free(sls2); + sls1 = smartlist_slice(sl1, 0, -1); + sls2 = smartlist_slice(sl2, 0, -1); + calc_changes(sls1, sls2, changed1, changed2); + + /* Two elements are changed. */ + tt_assert(!bitarray_is_set(changed1, 0)); + tt_assert(bitarray_is_set(changed1, 1)); + tt_assert(bitarray_is_set(changed1, 2)); + tt_assert(!bitarray_is_set(changed1, 3)); + bitarray_clear(changed1, 1); + bitarray_clear(changed1, 2); + + tt_assert(!bitarray_is_set(changed2, 0)); + tt_assert(bitarray_is_set(changed2, 1)); + tt_assert(!bitarray_is_set(changed2, 2)); + tt_assert(bitarray_is_set(changed2, 3)); + bitarray_clear(changed1, 1); + bitarray_clear(changed1, 3); + + SMARTLIST_FOREACH(sl2, char*, line, tor_free(line)); + smartlist_clear(sl2); + smartlist_split_string(sl2, "b:b:b:b", ":", 0, 0); + tor_free(sls1); + tor_free(sls2); + sls1 = smartlist_slice(sl1, 0, -1); + sls2 = smartlist_slice(sl2, 0, -1); + calc_changes(sls1, sls2, changed1, changed2); + + /* All elements are changed. */ + tt_assert(bitarray_is_set(changed1, 0)); + tt_assert(bitarray_is_set(changed1, 1)); + tt_assert(bitarray_is_set(changed1, 2)); + tt_assert(bitarray_is_set(changed1, 3)); + + tt_assert(bitarray_is_set(changed2, 0)); + tt_assert(bitarray_is_set(changed2, 1)); + tt_assert(bitarray_is_set(changed2, 2)); + tt_assert(bitarray_is_set(changed2, 3)); + + done: + bitarray_free(changed1); + bitarray_free(changed2); + if (sl1) SMARTLIST_FOREACH(sl1, char*, line, tor_free(line)); + if (sl2) SMARTLIST_FOREACH(sl2, char*, line, tor_free(line)); + smartlist_free(sl1); + smartlist_free(sl2); + tor_free(sls1); + tor_free(sls2); +} + +static void +test_consdiff_get_id_hash(void *arg) +{ + const char *line, *e_hash; + /* No hash. */ + (void)arg; + tt_ptr_op(NULL, OP_EQ, get_id_hash("r name")); + /* The hash contains characters that are not base64. */ + tt_ptr_op(NULL, OP_EQ, get_id_hash( "r name _hash_isnt_base64 etc")); + + line = "r name hash+valid+base64 etc"; + e_hash = line+7; + tt_ptr_op(e_hash, OP_EQ, get_id_hash(line)); + + done: + ; +} + +static void +test_consdiff_is_valid_router_entry(void *arg) +{ + /* Doesn't start with "r ". */ + (void)arg; + tt_int_op(0, OP_EQ, is_valid_router_entry("foo")); + + /* These are already tested with get_id_hash, but make sure it's run + * properly. */ + + tt_int_op(0, OP_EQ, is_valid_router_entry("r name")); + tt_int_op(0, OP_EQ, is_valid_router_entry("r name _hash_isnt_base64 etc")); + tt_int_op(1, OP_EQ, is_valid_router_entry("r name hash+valid+base64 etc")); + + done: + ; +} + +static void +test_consdiff_next_router(void *arg) +{ + smartlist_t *sl = smartlist_new(); + (void)arg; + smartlist_add(sl, (char*)"foo"); + smartlist_add(sl, + (char*)"r name hash+longer+than+27+chars+and+valid+base64 etc"); + smartlist_add(sl, (char*)"foo"); + smartlist_add(sl, (char*)"foo"); + smartlist_add(sl, + (char*)"r name hash+longer+than+27+chars+and+valid+base64 etc"); + smartlist_add(sl, (char*)"foo"); + + /* Not currently on a router entry line, finding the next one. */ + tt_int_op(1, OP_EQ, next_router(sl, 0)); + tt_int_op(4, OP_EQ, next_router(sl, 2)); + + /* Already at the beginning of a router entry line, ignore it. */ + tt_int_op(4, OP_EQ, next_router(sl, 1)); + + /* There are no more router entries, so return the line after the last. */ + tt_int_op(6, OP_EQ, next_router(sl, 4)); + tt_int_op(6, OP_EQ, next_router(sl, 5)); + + done: + smartlist_free(sl); +} + +static void +test_consdiff_base64cmp(void *arg) +{ + /* NULL arguments. */ + (void)arg; + tt_int_op(0, OP_EQ, base64cmp(NULL, NULL)); + tt_int_op(-1, OP_EQ, base64cmp(NULL, "foo")); + tt_int_op(1, OP_EQ, base64cmp("bar", NULL)); + + /* Nil base64 values. */ + tt_int_op(0, OP_EQ, base64cmp("", "")); + tt_int_op(0, OP_EQ, base64cmp("_", "&")); + + /* Exact same valid strings. */ + tt_int_op(0, OP_EQ, base64cmp("abcABC/+", "abcABC/+")); + /* Both end with an invalid base64 char other than '\0'. */ + tt_int_op(0, OP_EQ, base64cmp("abcABC/+ ", "abcABC/+ ")); + /* Only one ends with an invalid base64 char other than '\0'. */ + tt_int_op(0, OP_EQ, base64cmp("abcABC/+ ", "abcABC/+")); + + /* Comparisons that would return differently with strcmp(). */ + tt_int_op(-1, OP_EQ, strcmp("/foo", "Afoo")); + tt_int_op(1, OP_EQ, base64cmp("/foo", "Afoo")); + tt_int_op(1, OP_EQ, strcmp("Afoo", "0foo")); + tt_int_op(-1, OP_EQ, base64cmp("Afoo", "0foo")); + + /* Comparisons that would return the same as with strcmp(). */ + tt_int_op(1, OP_EQ, strcmp("afoo", "Afoo")); + tt_int_op(1, OP_EQ, base64cmp("afoo", "Afoo")); + + done: + ; +} + +static void +test_consdiff_gen_ed_diff(void *arg) +{ + smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; + int i; + (void)arg; + cons1 = smartlist_new(); + cons2 = smartlist_new(); + + /* Identity hashes are not sorted properly, return NULL. */ + smartlist_add(cons1, (char*)"r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); + smartlist_add(cons1, (char*)"foo"); + smartlist_add(cons1, (char*)"r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc"); + smartlist_add(cons1, (char*)"bar"); + + smartlist_add(cons2, (char*)"r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc"); + smartlist_add(cons2, (char*)"foo"); + smartlist_add(cons2, (char*)"r name ccccccccccccccccccccccccccc etc"); + smartlist_add(cons2, (char*)"bar"); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_EQ, diff); + + /* Same, but now with the second consensus. */ + diff = gen_ed_diff(cons2, cons1); + tt_ptr_op(NULL, OP_EQ, diff); + + /* Identity hashes are repeated, return NULL. */ + smartlist_clear(cons1); + + smartlist_add(cons1, (char*)"r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); + smartlist_add(cons1, (char*)"foo"); + smartlist_add(cons1, (char*)"r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); + smartlist_add(cons1, (char*)"bar"); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_EQ, diff); + + /* We have to add a line that is just a dot, return NULL. */ + smartlist_clear(cons1); + smartlist_clear(cons2); + + smartlist_add(cons1, (char*)"foo1"); + smartlist_add(cons1, (char*)"foo2"); + + smartlist_add(cons2, (char*)"foo1"); + smartlist_add(cons2, (char*)"."); + smartlist_add(cons2, (char*)"foo2"); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_EQ, diff); + +#define MAX_LINE_COUNT (10000) + /* Too many lines to be fed to the quadratic-time function. */ + smartlist_clear(cons1); + smartlist_clear(cons2); + + for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add(cons1, (char*)"a"); + for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add(cons1, (char*)"b"); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_EQ, diff); + + /* We have dot lines, but they don't interfere with the script format. */ + smartlist_clear(cons1); + smartlist_clear(cons2); + + smartlist_add(cons1, (char*)"foo1"); + smartlist_add(cons1, (char*)"."); + smartlist_add(cons1, (char*)"."); + smartlist_add(cons1, (char*)"foo2"); + + smartlist_add(cons2, (char*)"foo1"); + smartlist_add(cons2, (char*)"."); + smartlist_add(cons2, (char*)"foo2"); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_NE, diff); + SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_free(diff); + + /* Empty diff tests. */ + smartlist_clear(cons1); + smartlist_clear(cons2); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, !=, diff); + tt_int_op(0, OP_EQ, smartlist_len(diff)); + smartlist_free(diff); + + smartlist_add(cons1, (char*)"foo"); + smartlist_add(cons1, (char*)"bar"); + + smartlist_add(cons2, (char*)"foo"); + smartlist_add(cons2, (char*)"bar"); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_NE, diff); + tt_int_op(0, OP_EQ, smartlist_len(diff)); + smartlist_free(diff); + + /* Everything is deleted. */ + smartlist_clear(cons2); + + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_NE, diff); + tt_int_op(1, OP_EQ, smartlist_len(diff)); + tt_str_op("1,2d", OP_EQ, smartlist_get(diff, 0)); + + SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_free(diff); + + /* Everything is added. */ + diff = gen_ed_diff(cons2, cons1); + tt_ptr_op(NULL, OP_NE, diff); + tt_int_op(4, OP_EQ, smartlist_len(diff)); + tt_str_op("0a", OP_EQ, smartlist_get(diff, 0)); + tt_str_op("foo", OP_EQ, smartlist_get(diff, 1)); + tt_str_op("bar", OP_EQ, smartlist_get(diff, 2)); + tt_str_op(".", OP_EQ, smartlist_get(diff, 3)); + + SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_free(diff); + + /* Everything is changed. */ + smartlist_add(cons2, (char*)"foo2"); + smartlist_add(cons2, (char*)"bar2"); + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_NE, diff); + tt_int_op(4, OP_EQ, smartlist_len(diff)); + tt_str_op("1,2c", OP_EQ, smartlist_get(diff, 0)); + tt_str_op("foo2", OP_EQ, smartlist_get(diff, 1)); + tt_str_op("bar2", OP_EQ, smartlist_get(diff, 2)); + tt_str_op(".", OP_EQ, smartlist_get(diff, 3)); + + SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_free(diff); + + /* Test 'a', 'c' and 'd' together. See that it is done in reverse order. */ + smartlist_clear(cons1); + smartlist_clear(cons2); + smartlist_split_string(cons1, "A:B:C:D:E", ":", 0, 0); + smartlist_split_string(cons2, "A:C:O:E:U", ":", 0, 0); + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_NE, diff); + tt_int_op(7, OP_EQ, smartlist_len(diff)); + tt_str_op("5a", OP_EQ, smartlist_get(diff, 0)); + tt_str_op("U", OP_EQ, smartlist_get(diff, 1)); + tt_str_op(".", OP_EQ, smartlist_get(diff, 2)); + tt_str_op("4c", OP_EQ, smartlist_get(diff, 3)); + tt_str_op("O", OP_EQ, smartlist_get(diff, 4)); + tt_str_op(".", OP_EQ, smartlist_get(diff, 5)); + tt_str_op("2d", OP_EQ, smartlist_get(diff, 6)); + + /* TODO: small real use-cases, i.e. consensuses. */ + + done: + if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); + if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + smartlist_free(cons1); + smartlist_free(cons2); + if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_free(diff); +} + +static void +test_consdiff_apply_ed_diff(void *arg) +{ + smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; + (void)arg; + cons1 = smartlist_new(); + diff = smartlist_new(); + + smartlist_split_string(cons1, "A:B:C:D:E", ":", 0, 0); + + /* Command without range. */ + smartlist_add(diff, (char*)"a"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Range without command. */ + smartlist_add(diff, (char*)"1"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Range without end. */ + smartlist_add(diff, (char*)"1,"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Incoherent ranges. */ + smartlist_add(diff, (char*)"1,1"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + smartlist_add(diff, (char*)"3,2"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Script is not in reverse order. */ + smartlist_add(diff, (char*)"1d"); + smartlist_add(diff, (char*)"3d"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Script contains unrecognised commands longer than one char. */ + smartlist_add(diff, (char*)"1foo"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Script contains unrecognised commands. */ + smartlist_add(diff, (char*)"1e"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Command that should be followed by at least one line and a ".", but + * isn't. */ + smartlist_add(diff, (char*)"0a"); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* Now it is followed by a ".", but it inserts zero lines. */ + smartlist_add(diff, (char*)"."); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + + smartlist_clear(diff); + + /* Test appending text, 'a'. */ + smartlist_split_string(diff, "3a:U:O:.:0a:V:.", ":", 0, 0); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_NE, cons2); + tt_int_op(8, OP_EQ, smartlist_len(cons2)); + tt_str_op("V", OP_EQ, smartlist_get(cons2, 0)); + tt_str_op("A", OP_EQ, smartlist_get(cons2, 1)); + tt_str_op("B", OP_EQ, smartlist_get(cons2, 2)); + tt_str_op("C", OP_EQ, smartlist_get(cons2, 3)); + tt_str_op("U", OP_EQ, smartlist_get(cons2, 4)); + tt_str_op("O", OP_EQ, smartlist_get(cons2, 5)); + tt_str_op("D", OP_EQ, smartlist_get(cons2, 6)); + tt_str_op("E", OP_EQ, smartlist_get(cons2, 7)); + + SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_clear(diff); + SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + smartlist_free(cons2); + + /* Test deleting text, 'd'. */ + smartlist_split_string(diff, "4d:1,2d", ":", 0, 0); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_NE, cons2); + tt_int_op(2, OP_EQ, smartlist_len(cons2)); + tt_str_op("C", OP_EQ, smartlist_get(cons2, 0)); + tt_str_op("E", OP_EQ, smartlist_get(cons2, 1)); + + SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_clear(diff); + SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + smartlist_free(cons2); + + /* Test changing text, 'c'. */ + smartlist_split_string(diff, "4c:T:X:.:1, 2c:M:.", ":", 0, 0); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_NE, cons2); + tt_int_op(5, OP_EQ, smartlist_len(cons2)); + tt_str_op("M", OP_EQ, smartlist_get(cons2, 0)); + tt_str_op("C", OP_EQ, smartlist_get(cons2, 1)); + tt_str_op("T", OP_EQ, smartlist_get(cons2, 2)); + tt_str_op("X", OP_EQ, smartlist_get(cons2, 3)); + tt_str_op("E", OP_EQ, smartlist_get(cons2, 4)); + + SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_clear(diff); + SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + smartlist_free(cons2); + + /* Test 'a', 'd' and 'c' together. */ + smartlist_split_string(diff, "4c:T:X:.:2d:0a:M:.", ":", 0, 0); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_NE, cons2); + tt_int_op(6, OP_EQ, smartlist_len(cons2)); + tt_str_op("M", OP_EQ, smartlist_get(cons2, 0)); + tt_str_op("A", OP_EQ, smartlist_get(cons2, 1)); + tt_str_op("C", OP_EQ, smartlist_get(cons2, 2)); + tt_str_op("T", OP_EQ, smartlist_get(cons2, 3)); + tt_str_op("X", OP_EQ, smartlist_get(cons2, 4)); + tt_str_op("E", OP_EQ, smartlist_get(cons2, 5)); + + done: + if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); + if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + smartlist_free(cons1); + smartlist_free(cons2); + if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_free(diff); +} + +static void +test_consdiff_gen_diff(void *arg) +{ + char *cons1_str=NULL, *cons2_str=NULL; + smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; + common_digests_t digests1, digests2; + (void)arg; + cons1 = smartlist_new(); + cons2 = smartlist_new(); + + /* Identity hashes are not sorted properly, return NULL. + * Already tested in gen_ed_diff, but see that a NULL ed diff also makes + * gen_diff return NULL. */ + cons1_str = tor_strdup( + "header\nnetwork-status-version foo\n" + "r name bbbbbbbbbbbbbbbbb etc\nfoo\n" + "r name aaaaaaaaaaaaaaaaa etc\nbar\n" + "directory-signature foo bar\nbar\n" + ); + cons2_str = tor_strdup( + "header\nnetwork-status-version foo\n" + "r name aaaaaaaaaaaaaaaaa etc\nfoo\n" + "r name ccccccccccccccccc etc\nbar\n" + "directory-signature foo bar\nbar\n" + ); + + tt_int_op(0, OP_EQ, + router_get_networkstatus_v3_hashes(cons1_str, &digests1)); + tt_int_op(0, OP_EQ, + router_get_networkstatus_v3_hashes(cons2_str, &digests2)); + + tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); + tor_split_lines(cons2, cons2_str, (int)strlen(cons2_str)); + + diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2); + tt_ptr_op(NULL, OP_EQ, diff); + + /* Check that the headers are done properly. */ + tor_free(cons1_str); + cons1_str = tor_strdup( + "header\nnetwork-status-version foo\n" + "r name ccccccccccccccccc etc\nfoo\n" + "r name eeeeeeeeeeeeeeeee etc\nbar\n" + "directory-signature foo bar\nbar\n" + ); + tt_int_op(0, OP_EQ, + router_get_networkstatus_v3_hashes(cons1_str, &digests1)); + smartlist_clear(cons1); + tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); + diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2); + tt_ptr_op(NULL, OP_NE, diff); + tt_int_op(7, OP_EQ, smartlist_len(diff)); + tt_str_op("network-status-diff-version 1", OP_EQ, smartlist_get(diff, 0)); + tt_str_op("hash " + "C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A " + "B193E5FBFE5C009AEDE56F9218E6421A1AE5C19F43E091786A73F43F60409B60", + OP_EQ, smartlist_get(diff, 1)); + tt_str_op("4,5d", OP_EQ, smartlist_get(diff, 2)); + tt_str_op("2a", OP_EQ, smartlist_get(diff, 3)); + tt_str_op("r name aaaaaaaaaaaaaaaaa etc", OP_EQ, smartlist_get(diff, 4)); + tt_str_op("foo", OP_EQ, smartlist_get(diff, 5)); + tt_str_op(".", OP_EQ, smartlist_get(diff, 6)); + + /* TODO: small real use-cases, i.e. consensuses. */ + + done: + tor_free(cons1_str); + tor_free(cons2_str); + smartlist_free(cons1); + smartlist_free(cons2); + if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); + smartlist_free(diff); +} + +static void +test_consdiff_apply_diff(void *arg) +{ + smartlist_t *cons1=NULL, *diff=NULL; + char *cons1_str=NULL, *cons2 = NULL; + common_digests_t digests1; + (void)arg; + cons1 = smartlist_new(); + diff = smartlist_new(); + + cons1_str = tor_strdup( + "header\nnetwork-status-version foo\n" + "r name ccccccccccccccccc etc\nfoo\n" + "r name eeeeeeeeeeeeeeeee etc\nbar\n" + "directory-signature foo bar\nbar\n" + ); + tt_int_op(0, OP_EQ, + router_get_networkstatus_v3_hashes(cons1_str, &digests1)); + tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); + + /* diff doesn't have enough lines. */ + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* first line doesn't match format-version string. */ + smartlist_add(diff, (char*)"foo-bar"); + smartlist_add(diff, (char*)"header-line"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* The first word of the second header line is not "hash". */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"word a b"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* Wrong number of words after "hash". */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash a b c"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* base16 sha256 digests do not have the expected length. */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash aaa bbb"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* base16 sha256 digests contain non-base16 characters. */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + " ????????????????????????????????????????????????????????????????" + " ----------------------------------------------------------------"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* Invalid ed diff. + * As tested in apply_ed_diff, but check that apply_diff does return NULL if + * the ed diff can't be applied. */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + /* sha256 of cons1. */ + " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" + /* sha256 of cons2. */ + " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA"); + smartlist_add(diff, (char*)"foobar"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* Base consensus doesn't match its digest as found in the diff. */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + /* bogus sha256. */ + " 3333333333333333333333333333333333333333333333333333333333333333" + /* sha256 of cons2. */ + " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* Resulting consensus doesn't match its digest as found in the diff. */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + /* sha256 of cons1. */ + " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" + /* bogus sha256. */ + " 3333333333333333333333333333333333333333333333333333333333333333"); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + + /* Very simple test, only to see that nothing errors. */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + /* sha256 of cons1. */ + " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" + /* sha256 of cons2. */ + " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA"); + smartlist_add(diff, (char*)"4c"); + smartlist_add(diff, (char*)"sample"); + smartlist_add(diff, (char*)"."); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_NE, cons2); + tt_str_op( + "header\nnetwork-status-version foo\n" + "r name ccccccccccccccccc etc\nsample\n" + "r name eeeeeeeeeeeeeeeee etc\nbar\n" + "directory-signature foo bar\nbar\n", OP_EQ, + cons2); + tor_free(cons2); + + /* Check that lowercase letters in base16-encoded digests work too. */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + /* sha256 of cons1. */ + " c2199b6827514f39ed9b3f2e2e73735c6c5468fd636240bb454c526220de702a" + /* sha256 of cons2. */ + " 635d34593020c08e5ecd865f9986e29d50028efa62843766a8197ad228a7f6aa"); + smartlist_add(diff, (char*)"4c"); + smartlist_add(diff, (char*)"sample"); + smartlist_add(diff, (char*)"."); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_NE, cons2); + tt_str_op( + "header\nnetwork-status-version foo\n" + "r name ccccccccccccccccc etc\nsample\n" + "r name eeeeeeeeeeeeeeeee etc\nbar\n" + "directory-signature foo bar\nbar\n", OP_EQ, + cons2); + tor_free(cons2); + + smartlist_clear(diff); + + done: + tor_free(cons1_str); + smartlist_free(cons1); + smartlist_free(diff); +} + +#define CONSDIFF_LEGACY(name) \ + { #name, test_consdiff_ ## name , 0, NULL, NULL } + +struct testcase_t consdiff_tests[] = { + CONSDIFF_LEGACY(smartlist_slice), + CONSDIFF_LEGACY(smartlist_slice_string_pos), + CONSDIFF_LEGACY(lcs_lengths), + CONSDIFF_LEGACY(trim_slices), + CONSDIFF_LEGACY(set_changed), + CONSDIFF_LEGACY(calc_changes), + CONSDIFF_LEGACY(get_id_hash), + CONSDIFF_LEGACY(is_valid_router_entry), + CONSDIFF_LEGACY(next_router), + CONSDIFF_LEGACY(base64cmp), + CONSDIFF_LEGACY(gen_ed_diff), + CONSDIFF_LEGACY(apply_ed_diff), + CONSDIFF_LEGACY(gen_diff), + CONSDIFF_LEGACY(apply_diff), + END_OF_TESTCASES +}; +

1 0

[tor/master] Use "STATIC" to export consdiff fns for testing
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit 360d043ac726ca5354bcb3aa1f138f910defc8ec Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 10:22:00 2017 -0500 Use "STATIC" to export consdiff fns for testing Previously test_consdiff.c just did #include "consdiff.c", which is not great style, and messes up coverage testing. --- src/or/consdiff.c | 39 ++++++++++++++------------------------- src/or/consdiff.h | 41 +++++++++++++++++++++++++++++++++++------ src/test/test_consdiff.c | 5 ++++- 3 files changed, 53 insertions(+), 32 deletions(-) diff --git a/src/or/consdiff.c b/src/or/consdiff.c index 7a67498..52e1eb9 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -30,6 +30,8 @@ * comments. **/ +#define CONSDIFF_PRIVATE + #include "or.h" #include "consdiff.h" #include "routerparse.h" @@ -37,25 +39,12 @@ static const char* ns_diff_version = "network-status-diff-version 1"; static const char* hash_token = "hash"; -/** Data structure to define a slice of a smarltist. */ -typedef struct { - /** - * Smartlist that this slice is made from. - * References the whole original smartlist that the slice was made out of. - * */ - smartlist_t *list; - /** Starting position of the slice in the smartlist. */ - int offset; - /** Length of the slice, i.e. the number of elements it holds. */ - int len; -} smartlist_slice_t; - /** Create (allocate) a new slice from a smartlist. Assumes that the start * and the end indexes are within the bounds of the initial smartlist. The end * element is not part of the resulting slice. If end is -1, the slice is to * reach the end of the smartlist. */ -static smartlist_slice_t * +STATIC smartlist_slice_t * smartlist_slice(smartlist_t *list, int start, int end) { int list_len = smartlist_len(list); @@ -80,7 +69,7 @@ smartlist_slice(smartlist_t *list, int start, int end) * The length of the resulting integer array is that of the second slice plus * one. */ -static int * +STATIC int * lcs_lengths(smartlist_slice_t *slice1, smartlist_slice_t *slice2, int direction) { @@ -128,7 +117,7 @@ lcs_lengths(smartlist_slice_t *slice1, smartlist_slice_t *slice2, /** Helper: Trim any number of lines that are equally at the start or the end * of both slices. */ -static void +STATIC void trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2) { while (slice1->len>0 && slice2->len>0) { @@ -159,7 +148,7 @@ trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2) /** Like smartlist_string_pos, but limited to the bounds of the slice. */ -static int +STATIC int smartlist_slice_string_pos(smartlist_slice_t *slice, const char *string) { int end = slice->offset + slice->len; @@ -177,7 +166,7 @@ smartlist_slice_string_pos(smartlist_slice_t *slice, const char *string) * present in the other slice will be set to changed in their bool array. * The two changed bool arrays are passed in the same order as the slices. */ -static void +STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, smartlist_slice_t *slice1, smartlist_slice_t *slice2) { @@ -239,7 +228,7 @@ optimal_column_to_split(smartlist_slice_t *top, smartlist_slice_t *bot, * the optimal column at which to split the second smartlist so that we are * finding the smallest diff possible. */ -static void +STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, bitarray_t *changed1, bitarray_t *changed2) { @@ -303,7 +292,7 @@ static const uint8_t base64_compare_table[256] = { /** Helper: Get the identity hash from a router line, assuming that the line * at least appears to be a router line and thus starts with "r ". */ -static const char * +STATIC const char * get_id_hash(const char *r_line) { r_line += strlen("r "); @@ -334,7 +323,7 @@ get_id_hash(const char *r_line) /** Helper: Check that a line is a valid router entry. We must at least be * able to fetch a proper identity hash from it for it to be valid. */ -static int +STATIC int is_valid_router_entry(const char *line) { if (strcmpstart(line, "r ") != 0) { @@ -348,7 +337,7 @@ is_valid_router_entry(const char *line) * line within the bounds of the consensus. The only exception is when we * don't want to skip the first line, in which case cur will be -1. */ -static int +STATIC int next_router(smartlist_t *cons, int cur) { int len = smartlist_len(cons); @@ -371,7 +360,7 @@ next_router(smartlist_t *cons, int cur) /** Helper: compare two base64-encoded identity hashes which may be of * different lengths. Comparison ends when the first non-base64 char is found. */ -static int +STATIC int base64cmp(const char *hash1, const char *hash2) { /* NULL is always lower, useful for last_hash which starts at NULL. */ @@ -432,7 +421,7 @@ base64cmp(const char *hash1, const char *hash2) * cons2_sl = smartlist_slice(cons2, 0, -1); * calc_changes(cons1_sl, cons2_sl, changed1, changed2); */ -static smartlist_t * +STATIC smartlist_t * gen_ed_diff(smartlist_t *cons1, smartlist_t *cons2) { int len1 = smartlist_len(cons1); @@ -658,7 +647,7 @@ gen_ed_diff(smartlist_t *cons1, smartlist_t *cons2) * line-based smartlist. Will return NULL if the ed diff is not properly * formatted. */ -static smartlist_t * +STATIC smartlist_t * apply_ed_diff(smartlist_t *cons1, smartlist_t *diff) { int diff_len = smartlist_len(diff); diff --git a/src/or/consdiff.h b/src/or/consdiff.h index da8dbac..7d49419 100644 --- a/src/or/consdiff.h +++ b/src/or/consdiff.h @@ -7,16 +7,45 @@ #include "or.h" -smartlist_t * -consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, +smartlist_t *consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, common_digests_t *digests1, common_digests_t *digests2); -char * -consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, +char *consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, common_digests_t *digests1); -int -consdiff_get_digests(smartlist_t *diff, +int consdiff_get_digests(smartlist_t *diff, char *digest1, char *digest1_hex, char *digest2, char *digest2_hex); +#ifdef CONSDIFF_PRIVATE +/** Data structure to define a slice of a smarltist. */ +typedef struct smartlist_slice_t { + /** + * Smartlist that this slice is made from. + * References the whole original smartlist that the slice was made out of. + * */ + smartlist_t *list; + /** Starting position of the slice in the smartlist. */ + int offset; + /** Length of the slice, i.e. the number of elements it holds. */ + int len; +} smartlist_slice_t; +STATIC smartlist_t *gen_ed_diff(smartlist_t *cons1, smartlist_t *cons2); +STATIC smartlist_t *apply_ed_diff(smartlist_t *cons1, smartlist_t *diff); +STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, + bitarray_t *changed1, bitarray_t *changed2); +STATIC smartlist_slice_t *smartlist_slice(smartlist_t *list, + int start, int end); +STATIC int next_router(smartlist_t *cons, int cur); +STATIC int *lcs_lengths(smartlist_slice_t *slice1, smartlist_slice_t *slice2, + int direction); +STATIC void trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2); +STATIC int base64cmp(const char *hash1, const char *hash2); +STATIC const char *get_id_hash(const char *r_line); +STATIC int is_valid_router_entry(const char *line); +STATIC int smartlist_slice_string_pos(smartlist_slice_t *slice, + const char *string); +STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, + smartlist_slice_t *slice1, smartlist_slice_t *slice2); +#endif + #endif diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 40fedf1..a72b64b 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -2,10 +2,13 @@ * Copyright (c) 2014, The Tor Project, Inc. */ /* See LICENSE for licensing information */ +#define CONSDIFF_PRIVATE + #include "or.h" #include "test.h" -#include "consdiff.c" +#include "consdiff.h" +#include "routerparse.h" #ifndef OP_EQ #define OP_EQ ==

1 0

[tor/master] Mark some warnings as bugs, and as (hopefully) unreachable.
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit ab1fd85c999fe53af9503850c2642bd860e5b250 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 11:13:40 2017 -0500 Mark some warnings as bugs, and as (hopefully) unreachable. --- src/or/consdiff.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/src/or/consdiff.c b/src/or/consdiff.c index a340cfd..ed20e3b 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -801,20 +801,24 @@ consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, /* See that the script actually produces what we want. */ smartlist_t *ed_cons2 = apply_ed_diff(cons1, ed_diff); if (!ed_cons2) { - log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because " + /* LCOV_EXCL_START -- impossible if diff generation is correct */ + log_warn(LD_BUG|LD_CONSDIFF, "Refusing to generate consensus diff because " "the generated ed diff could not be tested to successfully generate " "the target consensus."); goto error_cleanup; + /* LCOV_EXCL_STOP */ } int cons2_eq = smartlist_strings_eq(cons2, ed_cons2); SMARTLIST_FOREACH(ed_cons2, char*, line, tor_free(line)); smartlist_free(ed_cons2); if (!cons2_eq) { - log_warn(LD_CONSDIFF, "Refusing to generate consensus diff because " + /* LCOV_EXCL_START -- impossible if diff generation is correct. */ + log_warn(LD_BUG|LD_CONSDIFF, "Refusing to generate consensus diff because " "the generated ed diff did not generate the target consensus " "successfully when tested."); goto error_cleanup; + /* LCOV_EXCL_STOP */ } char cons1_hash_hex[HEX_DIGEST256_LEN+1]; @@ -832,7 +836,7 @@ consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, smartlist_free(ed_diff); return result; - error_cleanup: + error_cleanup: if (ed_diff) { smartlist_free(ed_diff);

1 0

[tor/master] No need to end a log message with newline.
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit 97620cf18ff510deec07cd98b46cfa7a3f859900 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 10:48:03 2017 -0500 No need to end a log message with newline. --- src/or/consdiff.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/or/consdiff.c b/src/or/consdiff.c index 52e1eb9..65e15f7 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -954,7 +954,7 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, digests1->d[DIGEST_SHA256], DIGEST256_LEN); base16_encode(e_hex_digest1, HEX_DIGEST256_LEN+1, e_cons1_hash, DIGEST256_LEN); - log_warn(LD_CONSDIFF, "Expected: %s Found: %s\n", + log_warn(LD_CONSDIFF, "Expected: %s; found: %s", hex_digest1, e_hex_digest1); goto error_cleanup; } @@ -999,7 +999,7 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, cons2_digests.d[DIGEST_SHA256], DIGEST256_LEN); base16_encode(e_hex_digest2, HEX_DIGEST256_LEN+1, e_cons2_hash, DIGEST256_LEN); - log_warn(LD_CONSDIFF, "Expected: %s Found: %s\n", + log_warn(LD_CONSDIFF, "Expected: %s; found: %s", hex_digest2, e_hex_digest2); goto error_cleanup; }

1 0

[tor/master] Enforce correct log messages on diff generation failure tests
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit 687df259c68b5ee371cf69b31a563659a1227189 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 10:45:18 2017 -0500 Enforce correct log messages on diff generation failure tests --- src/test/test_consdiff.c | 30 ++++++++++++++++++++++++++++-- 1 file changed, 28 insertions(+), 2 deletions(-) diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index c8fb318..ff5ce81 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -9,6 +9,7 @@ #include "consdiff.h" #include "routerparse.h" +#include "log_test_helpers.h" #ifndef OP_EQ #define OP_EQ == @@ -422,6 +423,10 @@ test_consdiff_gen_ed_diff(void *arg) { smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; int i; + int free_cons_entries = 0;/* 1 if the cons1 and cons2 contents are + * heap-allocated */ + setup_capture_of_logs(LOG_WARN); + (void)arg; cons1 = smartlist_new(); cons2 = smartlist_new(); @@ -439,10 +444,17 @@ test_consdiff_gen_ed_diff(void *arg) diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the base consensus doesn't have its router entries sorted " + "properly."); /* Same, but now with the second consensus. */ + mock_clean_saved_logs(); diff = gen_ed_diff(cons2, cons1); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the target consensus doesn't have its router entries sorted " + "properly."); /* Identity hashes are repeated, return NULL. */ smartlist_clear(cons1); @@ -452,8 +464,12 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_add(cons1, (char*)"r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); smartlist_add(cons1, (char*)"bar"); + mock_clean_saved_logs(); diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the base consensus doesn't have its router entries sorted " + "properly."); /* We have to add a line that is just a dot, return NULL. */ smartlist_clear(cons1); @@ -466,8 +482,11 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_add(cons2, (char*)"."); smartlist_add(cons2, (char*)"foo2"); + mock_clean_saved_logs(); diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Cannot generate consensus diff " + "because one of the lines to be added is \".\"."); #define MAX_LINE_COUNT (10000) /* Too many lines to be fed to the quadratic-time function. */ @@ -477,8 +496,11 @@ test_consdiff_gen_ed_diff(void *arg) for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add(cons1, (char*)"a"); for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add(cons1, (char*)"b"); + mock_clean_saved_logs(); diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because we found too few common router ids."); /* We have dot lines, but they don't interfere with the script format. */ smartlist_clear(cons1); @@ -560,6 +582,7 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_clear(cons2); smartlist_split_string(cons1, "A:B:C:D:E", ":", 0, 0); smartlist_split_string(cons2, "A:C:O:E:U", ":", 0, 0); + free_cons_entries = 1; diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_NE, diff); tt_int_op(7, OP_EQ, smartlist_len(diff)); @@ -574,8 +597,11 @@ test_consdiff_gen_ed_diff(void *arg) /* TODO: small real use-cases, i.e. consensuses. */ done: - if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); - if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + teardown_capture_of_logs(); + if (free_cons_entries) { + if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); + if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + } smartlist_free(cons1); smartlist_free(cons2); if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line));

1 0

[tor/master] Check for expected warnings in apply_ed_diff
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit bb536a2e737b8d23f3514607bc3d6ff54ed19f0f Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 11:08:51 2017 -0500 Check for expected warnings in apply_ed_diff --- src/test/test_consdiff.c | 26 +++++++++++++++++++++++++- 1 file changed, 25 insertions(+), 1 deletion(-) diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 5014c7a..15f5575 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -608,6 +608,7 @@ test_consdiff_apply_ed_diff(void *arg) (void)arg; cons1 = smartlist_new(); diff = smartlist_new(); + setup_capture_of_logs(LOG_WARN); smartlist_split_string(cons1, "A:B:C:D:E", ":", 0, 0); @@ -615,68 +616,90 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"a"); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); - smartlist_clear(diff); + expect_single_log_msg_containing("an ed command was missing a line number"); /* Range without command. */ smartlist_add(diff, (char*)"1"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("a line with no ed command was found"); smartlist_clear(diff); /* Range without end. */ smartlist_add(diff, (char*)"1,"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an ed command was missing a range " + "end line number."); smartlist_clear(diff); /* Incoherent ranges. */ smartlist_add(diff, (char*)"1,1"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an invalid range was found"); smartlist_clear(diff); smartlist_add(diff, (char*)"3,2"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an invalid range was found"); smartlist_clear(diff); /* Script is not in reverse order. */ smartlist_add(diff, (char*)"1d"); smartlist_add(diff, (char*)"3d"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("its commands are not properly sorted"); smartlist_clear(diff); /* Script contains unrecognised commands longer than one char. */ smartlist_add(diff, (char*)"1foo"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an ed command longer than one char was " + "found"); smartlist_clear(diff); /* Script contains unrecognised commands. */ smartlist_add(diff, (char*)"1e"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an unrecognised ed command was found"); smartlist_clear(diff); /* Command that should be followed by at least one line and a ".", but * isn't. */ smartlist_add(diff, (char*)"0a"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("it has an ed command that tries to " + "insert zero lines."); /* Now it is followed by a ".", but it inserts zero lines. */ smartlist_add(diff, (char*)"."); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("it has an ed command that tries to " + "insert zero lines."); smartlist_clear(diff); @@ -741,6 +764,7 @@ test_consdiff_apply_ed_diff(void *arg) tt_str_op("E", OP_EQ, smartlist_get(cons2, 5)); done: + teardown_capture_of_logs(); if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); smartlist_free(cons1);

1 0

[tor/master] Fix some logging on failed apply_ed_diff
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit 06017f35e8c9bd821ee10ceb79476e6f5cd1f5d4 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 11:08:18 2017 -0500 Fix some logging on failed apply_ed_diff --- src/or/consdiff.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/src/or/consdiff.c b/src/or/consdiff.c index 65e15f7..a340cfd 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -670,15 +670,15 @@ apply_ed_diff(smartlist_t *cons1, smartlist_t *diff) if (*endptr1 == ',') { end = (int)strtol(endptr1+1, &endptr2, 10); if (endptr2 == endptr1+1) { - goto error_cleanup; log_warn(LD_CONSDIFF, "Could not apply consensus diff because " "an ed command was missing a range end line number."); + goto error_cleanup; } /* Incoherent range. */ if (end <= start) { - goto error_cleanup; log_warn(LD_CONSDIFF, "Could not apply consensus diff because " "an invalid range was found in an ed command."); + goto error_cleanup; } /* We'll take <n1> as <n1>,<n1> for simplicity. */ @@ -693,6 +693,12 @@ apply_ed_diff(smartlist_t *cons1, smartlist_t *diff) goto error_cleanup; } + if (*endptr2 == '\0') { + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "a line with no ed command was found"); + goto error_cleanup; + } + if (*(endptr2+1) != '\0') { log_warn(LD_CONSDIFF, "Could not apply consensus diff because " "an ed command longer than one char was found.");

1 0

[tor/master] Fixes when applying diffs: Allow 2-line diffs, fix bogus free
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit 5766eed38f3fbf150691bcae84d82a1c16dbeb48 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 11:35:50 2017 -0500 Fixes when applying diffs: Allow 2-line diffs, fix bogus free The 2-line diff changs is needed to make the unit tests actually test the cases that they thought they were testing. The bogus free was found while testing those cases --- src/or/consdiff.c | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-) diff --git a/src/or/consdiff.c b/src/or/consdiff.c index ed20e3b..defa1cf 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -859,7 +859,7 @@ consdiff_get_digests(smartlist_t *diff, const char *format; char cons1_hash[DIGEST256_LEN], cons2_hash[DIGEST256_LEN]; char *cons1_hash_hex, *cons2_hash_hex; - if (smartlist_len(diff) < 3) { + if (smartlist_len(diff) < 2) { log_info(LD_CONSDIFF, "The provided consensus diff is too short."); goto error_cleanup; } @@ -986,8 +986,6 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, } cons2_str = smartlist_join_strings(cons2, "\n", 1, NULL); - SMARTLIST_FOREACH(cons2, char *, cp, tor_free(cp)); - smartlist_free(cons2); common_digests_t cons2_digests; if (router_get_networkstatus_v3_hashes(cons2_str, @@ -1014,18 +1012,17 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, goto error_cleanup; } - return cons2_str; + goto done; - error_cleanup: + error_cleanup: + tor_free(cons2_str); /* Sets it to NULL */ + done: if (cons2) { SMARTLIST_FOREACH(cons2, char *, cp, tor_free(cp)); smartlist_free(cons2); } - if (cons2_str) { - tor_free(cons2_str); - } - return NULL; + return cons2_str; }

1 0

[tor/master] Cover two more failing cases with unit tests
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit c86e77ac20997282ca007ac7347e9910f55f880e Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 12:04:45 2017 -0500 Cover two more failing cases with unit tests --- src/test/test_consdiff.c | 28 +++++++++++++++++++++++++++- 1 file changed, 27 insertions(+), 1 deletion(-) diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 00fba67..b511d94 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -703,6 +703,17 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); + /* Now it it inserts something, but has no terminator. */ + smartlist_add(diff, (char*)"0a"); + smartlist_add(diff, (char*)"hello"); + mock_clean_saved_logs(); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("lines to be inserted that don't end with " + "a \".\"."); + + smartlist_clear(diff); + /* Test appending text, 'a'. */ smartlist_split_string(diff, "3a:U:O:.:0a:V:.", ":", 0, 0); cons2 = apply_ed_diff(cons1, diff); @@ -964,7 +975,22 @@ test_consdiff_apply_diff(void *arg) cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); expect_log_msg_containing("resulting consensus doesn't match the " - "digest as found") + "digest as found"); + + /* Resulting consensus digest cannot be computed */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + /* sha256 of cons1. */ + " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" + /* bogus sha256. */ + " 3333333333333333333333333333333333333333333333333333333333333333"); + smartlist_add(diff, (char*)"1,2d"); // remove starting line + mock_clean_saved_logs(); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + expect_log_msg_containing("Could not compute digests of the consensus " + "resulting from applying a consensus diff."); /* Very simple test, only to see that nothing errors. */ smartlist_clear(diff);

1 0

[tor/master] Fix an abstraction violation.
by nickm＠torproject.org 16 Mar '17

16 Mar '17

commit eff9fbd17d5fb4b1c196c241da4513d51893f52e Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 7 13:15:43 2017 -0500 Fix an abstraction violation. Don't alias the insides of smartlist_t; that way lies madness. --- src/or/consdiff.c | 25 +++++++++---------------- src/or/consdiff.h | 3 ++- src/test/test_consdiff.c | 30 +++++++++++++++--------------- 3 files changed, 26 insertions(+), 32 deletions(-) diff --git a/src/or/consdiff.c b/src/or/consdiff.c index 2b14395..6fe8360 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -654,18 +654,19 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) return NULL; } -/** Apply the ed diff to the consensus and return a new consensus, also as a - * line-based smartlist. Will return NULL if the ed diff is not properly - * formatted. +/** Apply the ed diff, starting at <b>diff_starting_line</b>, to the consensus + * and return a new consensus, also as a line-based smartlist. Will return + * NULL if the ed diff is not properly formatted. */ STATIC smartlist_t * -apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff) +apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, + int diff_starting_line) { int diff_len = smartlist_len(diff); int j = smartlist_len(cons1); smartlist_t *cons2 = smartlist_new(); - for (int i=0; i<diff_len; ++i) { + for (int i=diff_starting_line; i<diff_len; ++i) { const char *diff_line = smartlist_get(diff, i); char *endptr1, *endptr2; @@ -811,7 +812,7 @@ consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, } /* See that the script actually produces what we want. */ - smartlist_t *ed_cons2 = apply_ed_diff(cons1, ed_diff); + smartlist_t *ed_cons2 = apply_ed_diff(cons1, ed_diff, 0); if (!ed_cons2) { /* LCOV_EXCL_START -- impossible if diff generation is correct */ log_warn(LD_BUG|LD_CONSDIFF, "Refusing to generate consensus diff because " @@ -978,16 +979,8 @@ consdiff_apply_diff(const smartlist_t *cons1, } /* Grab the ed diff and calculate the resulting consensus. */ - /* To avoid copying memory or iterating over all the elements, make a - * read-only smartlist without the two header lines. - */ - /* XXXX prop140 abstraction violation; never do this. */ - smartlist_t *ed_diff = tor_malloc(sizeof(smartlist_t)); - ed_diff->list = diff->list+2; - ed_diff->num_used = diff->num_used-2; - ed_diff->capacity = diff->capacity-2; - cons2 = apply_ed_diff(cons1, ed_diff); - tor_free(ed_diff); + /* Skip the first two lines. */ + cons2 = apply_ed_diff(cons1, diff, 2); /* ed diff could not be applied - reason already logged by apply_ed_diff. */ if (!cons2) { diff --git a/src/or/consdiff.h b/src/or/consdiff.h index 3316ed6..42cd3af 100644 --- a/src/or/consdiff.h +++ b/src/or/consdiff.h @@ -37,7 +37,8 @@ typedef struct smartlist_slice_t { STATIC smartlist_t *gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2); STATIC smartlist_t *apply_ed_diff(const smartlist_t *cons1, - const smartlist_t *diff); + const smartlist_t *diff, + int start_line); STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, bitarray_t *changed1, bitarray_t *changed2); STATIC smartlist_slice_t *smartlist_slice(const smartlist_t *list, diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 2afebfe..12213aa 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -632,7 +632,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Command without range. */ smartlist_add(diff, (char*)"a"); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); smartlist_clear(diff); expect_single_log_msg_containing("an ed command was missing a line number"); @@ -640,7 +640,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Range without command. */ smartlist_add(diff, (char*)"1"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("a line with no ed command was found"); @@ -649,7 +649,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Range without end. */ smartlist_add(diff, (char*)"1,"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an ed command was missing a range " "end line number."); @@ -659,7 +659,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Incoherent ranges. */ smartlist_add(diff, (char*)"1,1"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an invalid range was found"); @@ -667,7 +667,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"3,2"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an invalid range was found"); @@ -677,7 +677,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"1d"); smartlist_add(diff, (char*)"3d"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("its commands are not properly sorted"); @@ -686,7 +686,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Script contains unrecognised commands longer than one char. */ smartlist_add(diff, (char*)"1foo"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an ed command longer than one char was " "found"); @@ -696,7 +696,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Script contains unrecognised commands. */ smartlist_add(diff, (char*)"1e"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an unrecognised ed command was found"); @@ -706,7 +706,7 @@ test_consdiff_apply_ed_diff(void *arg) * isn't. */ smartlist_add(diff, (char*)"0a"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("it has an ed command that tries to " "insert zero lines."); @@ -714,7 +714,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Now it is followed by a ".", but it inserts zero lines. */ smartlist_add(diff, (char*)"."); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("it has an ed command that tries to " "insert zero lines."); @@ -725,7 +725,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"0a"); smartlist_add(diff, (char*)"hello"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("lines to be inserted that don't end with " "a \".\"."); @@ -734,7 +734,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test appending text, 'a'. */ smartlist_split_string(diff, "3a:U:O:.:0a:V:.", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(8, OP_EQ, smartlist_len(cons2)); tt_str_op("V", OP_EQ, smartlist_get(cons2, 0)); @@ -753,7 +753,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test deleting text, 'd'. */ smartlist_split_string(diff, "4d:1,2d", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(2, OP_EQ, smartlist_len(cons2)); tt_str_op("C", OP_EQ, smartlist_get(cons2, 0)); @@ -766,7 +766,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test changing text, 'c'. */ smartlist_split_string(diff, "4c:T:X:.:1, 2c:M:.", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(5, OP_EQ, smartlist_len(cons2)); tt_str_op("M", OP_EQ, smartlist_get(cons2, 0)); @@ -782,7 +782,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test 'a', 'd' and 'c' together. */ smartlist_split_string(diff, "4c:T:X:.:2d:0a:M:.", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(6, OP_EQ, smartlist_len(cons2)); tt_str_op("M", OP_EQ, smartlist_get(cons2, 0));

1 0