diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common/log.c | 2 | ||||
| -rw-r--r-- | src/common/torlog.h | 4 | ||||
| -rw-r--r-- | src/or/consdiff.c | 1032 | ||||
| -rw-r--r-- | src/or/consdiff.h | 22 | ||||
| -rw-r--r-- | src/or/include.am | 2 | ||||
| -rw-r--r-- | src/test/Makefile.nmake | 2 | ||||
| -rw-r--r-- | src/test/include.am | 1 | ||||
| -rw-r--r-- | src/test/test.c | 1 | ||||
| -rw-r--r-- | src/test/test.h | 1 | ||||
| -rw-r--r-- | 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 5f7151bf0c..8489002ee0 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 bc957858d9..a56f5a8f1a 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 0000000000..7a67498ceb --- /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 0000000000..da8dbac79b --- /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 4e54deca55..d65d0d3657 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 0ba56d7036..575198388b 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 1c0726fd3a..23be3e8334 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 866408e856..98c44a95fd 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 2bd58f51c8..d390ffc399 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 0000000000..40fedf1156 --- /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 +}; + |