aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/common/log.c2
-rw-r--r--src/common/torlog.h4
-rw-r--r--src/or/consdiff.c1032
-rw-r--r--src/or/consdiff.h22
-rw-r--r--src/or/include.am2
-rw-r--r--src/test/Makefile.nmake2
-rw-r--r--src/test/include.am1
-rw-r--r--src/test/test.c1
-rw-r--r--src/test/test.h1
-rw-r--r--src/test/test_consdiff.c966
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
+};
+
7apu2bq3rhoylwmucxizk54afw5jyda7pho4j5zdcqpwkufke7zdzwad.onion