From 590ffdb2c9e0e3516fdb113cfa8b7a3f888cb970 Mon Sep 17 00:00:00 2001 From: Daniel Martí Date: Tue, 7 Mar 2017 09:58:30 -0500 Subject: Consensus diff backend from Daniel Martí GSOC project. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit (This commit was extracted by nickm based on the final outcome of the project, taking only the changes in the files touched by this commit from the consdiff_rebased branch. The directory-system changes are going to get worked on separately.) --- src/test/Makefile.nmake | 2 +- src/test/include.am | 1 + src/test/test.c | 1 + src/test/test.h | 1 + src/test/test_consdiff.c | 966 +++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 970 insertions(+), 1 deletion(-) create mode 100644 src/test/test_consdiff.c (limited to 'src/test') 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 +}; + -- cgit v1.2.3-54-g00ecf From 360d043ac726ca5354bcb3aa1f138f910defc8ec Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 10:22:00 -0500 Subject: Use "STATIC" to export consdiff fns for testing Previously test_consdiff.c just did #include "consdiff.c", which is not great style, and messes up coverage testing. --- src/or/consdiff.c | 39 ++++++++++++++------------------------- src/or/consdiff.h | 41 +++++++++++++++++++++++++++++++++++------ src/test/test_consdiff.c | 5 ++++- 3 files changed, 53 insertions(+), 32 deletions(-) (limited to 'src/test') diff --git a/src/or/consdiff.c b/src/or/consdiff.c index 7a67498ceb..52e1eb98a1 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -30,6 +30,8 @@ * comments. **/ +#define CONSDIFF_PRIVATE + #include "or.h" #include "consdiff.h" #include "routerparse.h" @@ -37,25 +39,12 @@ static const char* ns_diff_version = "network-status-diff-version 1"; static const char* hash_token = "hash"; -/** Data structure to define a slice of a smarltist. */ -typedef struct { - /** - * Smartlist that this slice is made from. - * References the whole original smartlist that the slice was made out of. - * */ - smartlist_t *list; - /** Starting position of the slice in the smartlist. */ - int offset; - /** Length of the slice, i.e. the number of elements it holds. */ - int len; -} smartlist_slice_t; - /** Create (allocate) a new slice from a smartlist. Assumes that the start * and the end indexes are within the bounds of the initial smartlist. The end * element is not part of the resulting slice. If end is -1, the slice is to * reach the end of the smartlist. */ -static smartlist_slice_t * +STATIC smartlist_slice_t * smartlist_slice(smartlist_t *list, int start, int end) { int list_len = smartlist_len(list); @@ -80,7 +69,7 @@ smartlist_slice(smartlist_t *list, int start, int end) * The length of the resulting integer array is that of the second slice plus * one. */ -static int * +STATIC int * lcs_lengths(smartlist_slice_t *slice1, smartlist_slice_t *slice2, int direction) { @@ -128,7 +117,7 @@ lcs_lengths(smartlist_slice_t *slice1, smartlist_slice_t *slice2, /** Helper: Trim any number of lines that are equally at the start or the end * of both slices. */ -static void +STATIC void trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2) { while (slice1->len>0 && slice2->len>0) { @@ -159,7 +148,7 @@ trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2) /** Like smartlist_string_pos, but limited to the bounds of the slice. */ -static int +STATIC int smartlist_slice_string_pos(smartlist_slice_t *slice, const char *string) { int end = slice->offset + slice->len; @@ -177,7 +166,7 @@ smartlist_slice_string_pos(smartlist_slice_t *slice, const char *string) * present in the other slice will be set to changed in their bool array. * The two changed bool arrays are passed in the same order as the slices. */ -static void +STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, smartlist_slice_t *slice1, smartlist_slice_t *slice2) { @@ -239,7 +228,7 @@ optimal_column_to_split(smartlist_slice_t *top, smartlist_slice_t *bot, * the optimal column at which to split the second smartlist so that we are * finding the smallest diff possible. */ -static void +STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, bitarray_t *changed1, bitarray_t *changed2) { @@ -303,7 +292,7 @@ static const uint8_t base64_compare_table[256] = { /** Helper: Get the identity hash from a router line, assuming that the line * at least appears to be a router line and thus starts with "r ". */ -static const char * +STATIC const char * get_id_hash(const char *r_line) { r_line += strlen("r "); @@ -334,7 +323,7 @@ get_id_hash(const char *r_line) /** Helper: Check that a line is a valid router entry. We must at least be * able to fetch a proper identity hash from it for it to be valid. */ -static int +STATIC int is_valid_router_entry(const char *line) { if (strcmpstart(line, "r ") != 0) { @@ -348,7 +337,7 @@ is_valid_router_entry(const char *line) * line within the bounds of the consensus. The only exception is when we * don't want to skip the first line, in which case cur will be -1. */ -static int +STATIC int next_router(smartlist_t *cons, int cur) { int len = smartlist_len(cons); @@ -371,7 +360,7 @@ next_router(smartlist_t *cons, int cur) /** Helper: compare two base64-encoded identity hashes which may be of * different lengths. Comparison ends when the first non-base64 char is found. */ -static int +STATIC int base64cmp(const char *hash1, const char *hash2) { /* NULL is always lower, useful for last_hash which starts at NULL. */ @@ -432,7 +421,7 @@ base64cmp(const char *hash1, const char *hash2) * cons2_sl = smartlist_slice(cons2, 0, -1); * calc_changes(cons1_sl, cons2_sl, changed1, changed2); */ -static smartlist_t * +STATIC smartlist_t * gen_ed_diff(smartlist_t *cons1, smartlist_t *cons2) { int len1 = smartlist_len(cons1); @@ -658,7 +647,7 @@ gen_ed_diff(smartlist_t *cons1, smartlist_t *cons2) * line-based smartlist. Will return NULL if the ed diff is not properly * formatted. */ -static smartlist_t * +STATIC smartlist_t * apply_ed_diff(smartlist_t *cons1, smartlist_t *diff) { int diff_len = smartlist_len(diff); diff --git a/src/or/consdiff.h b/src/or/consdiff.h index da8dbac79b..7d49419145 100644 --- a/src/or/consdiff.h +++ b/src/or/consdiff.h @@ -7,16 +7,45 @@ #include "or.h" -smartlist_t * -consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, +smartlist_t *consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, common_digests_t *digests1, common_digests_t *digests2); -char * -consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, +char *consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, common_digests_t *digests1); -int -consdiff_get_digests(smartlist_t *diff, +int consdiff_get_digests(smartlist_t *diff, char *digest1, char *digest1_hex, char *digest2, char *digest2_hex); +#ifdef CONSDIFF_PRIVATE +/** Data structure to define a slice of a smarltist. */ +typedef struct smartlist_slice_t { + /** + * Smartlist that this slice is made from. + * References the whole original smartlist that the slice was made out of. + * */ + smartlist_t *list; + /** Starting position of the slice in the smartlist. */ + int offset; + /** Length of the slice, i.e. the number of elements it holds. */ + int len; +} smartlist_slice_t; +STATIC smartlist_t *gen_ed_diff(smartlist_t *cons1, smartlist_t *cons2); +STATIC smartlist_t *apply_ed_diff(smartlist_t *cons1, smartlist_t *diff); +STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, + bitarray_t *changed1, bitarray_t *changed2); +STATIC smartlist_slice_t *smartlist_slice(smartlist_t *list, + int start, int end); +STATIC int next_router(smartlist_t *cons, int cur); +STATIC int *lcs_lengths(smartlist_slice_t *slice1, smartlist_slice_t *slice2, + int direction); +STATIC void trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2); +STATIC int base64cmp(const char *hash1, const char *hash2); +STATIC const char *get_id_hash(const char *r_line); +STATIC int is_valid_router_entry(const char *line); +STATIC int smartlist_slice_string_pos(smartlist_slice_t *slice, + const char *string); +STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, + smartlist_slice_t *slice1, smartlist_slice_t *slice2); +#endif + #endif diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 40fedf1156..a72b64ba32 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -2,10 +2,13 @@ * Copyright (c) 2014, The Tor Project, Inc. */ /* See LICENSE for licensing information */ +#define CONSDIFF_PRIVATE + #include "or.h" #include "test.h" -#include "consdiff.c" +#include "consdiff.h" +#include "routerparse.h" #ifndef OP_EQ #define OP_EQ == -- cgit v1.2.3-54-g00ecf From ccb789fe34abc4785bc4bf3e98612bcae7a66f78 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 10:45:13 -0500 Subject: Test two more base64cmp cases. --- src/test/test_consdiff.c | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'src/test') diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index a72b64ba32..c8fb3181a6 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -409,6 +409,10 @@ test_consdiff_base64cmp(void *arg) tt_int_op(1, OP_EQ, strcmp("afoo", "Afoo")); tt_int_op(1, OP_EQ, base64cmp("afoo", "Afoo")); + /* Different lengths */ + tt_int_op(-1, OP_EQ, base64cmp("afoo", "afooo")); + tt_int_op(1, OP_EQ, base64cmp("afooo", "afoo")); + done: ; } -- cgit v1.2.3-54-g00ecf From 687df259c68b5ee371cf69b31a563659a1227189 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 10:45:18 -0500 Subject: Enforce correct log messages on diff generation failure tests --- src/test/test_consdiff.c | 30 ++++++++++++++++++++++++++++-- 1 file changed, 28 insertions(+), 2 deletions(-) (limited to 'src/test') diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index c8fb3181a6..ff5ce81f04 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -9,6 +9,7 @@ #include "consdiff.h" #include "routerparse.h" +#include "log_test_helpers.h" #ifndef OP_EQ #define OP_EQ == @@ -422,6 +423,10 @@ test_consdiff_gen_ed_diff(void *arg) { smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; int i; + int free_cons_entries = 0;/* 1 if the cons1 and cons2 contents are + * heap-allocated */ + setup_capture_of_logs(LOG_WARN); + (void)arg; cons1 = smartlist_new(); cons2 = smartlist_new(); @@ -439,10 +444,17 @@ test_consdiff_gen_ed_diff(void *arg) diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the base consensus doesn't have its router entries sorted " + "properly."); /* Same, but now with the second consensus. */ + mock_clean_saved_logs(); diff = gen_ed_diff(cons2, cons1); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the target consensus doesn't have its router entries sorted " + "properly."); /* Identity hashes are repeated, return NULL. */ smartlist_clear(cons1); @@ -452,8 +464,12 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_add(cons1, (char*)"r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); smartlist_add(cons1, (char*)"bar"); + mock_clean_saved_logs(); diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the base consensus doesn't have its router entries sorted " + "properly."); /* We have to add a line that is just a dot, return NULL. */ smartlist_clear(cons1); @@ -466,8 +482,11 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_add(cons2, (char*)"."); smartlist_add(cons2, (char*)"foo2"); + mock_clean_saved_logs(); diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Cannot generate consensus diff " + "because one of the lines to be added is \".\"."); #define MAX_LINE_COUNT (10000) /* Too many lines to be fed to the quadratic-time function. */ @@ -477,8 +496,11 @@ test_consdiff_gen_ed_diff(void *arg) for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add(cons1, (char*)"a"); for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add(cons1, (char*)"b"); + mock_clean_saved_logs(); diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because we found too few common router ids."); /* We have dot lines, but they don't interfere with the script format. */ smartlist_clear(cons1); @@ -560,6 +582,7 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_clear(cons2); smartlist_split_string(cons1, "A:B:C:D:E", ":", 0, 0); smartlist_split_string(cons2, "A:C:O:E:U", ":", 0, 0); + free_cons_entries = 1; diff = gen_ed_diff(cons1, cons2); tt_ptr_op(NULL, OP_NE, diff); tt_int_op(7, OP_EQ, smartlist_len(diff)); @@ -574,8 +597,11 @@ test_consdiff_gen_ed_diff(void *arg) /* TODO: small real use-cases, i.e. consensuses. */ done: - if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); - if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + teardown_capture_of_logs(); + if (free_cons_entries) { + if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); + if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); + } smartlist_free(cons1); smartlist_free(cons2); if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); -- cgit v1.2.3-54-g00ecf From 05901f2c6d5e2c201158b8c841eec002c758ef7e Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 10:46:24 -0500 Subject: test operator cleanup --- src/test/test_consdiff.c | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) (limited to 'src/test') diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index ff5ce81f04..5014c7aebb 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -11,13 +11,6 @@ #include "routerparse.h" #include "log_test_helpers.h" -#ifndef OP_EQ -#define OP_EQ == -#endif -#ifndef OP_NE -#define OP_NE != -#endif - static void test_consdiff_smartlist_slice(void *arg) { @@ -525,7 +518,7 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_clear(cons2); diff = gen_ed_diff(cons1, cons2); - tt_ptr_op(NULL, !=, diff); + tt_ptr_op(NULL, OP_NE, diff); tt_int_op(0, OP_EQ, smartlist_len(diff)); smartlist_free(diff); -- cgit v1.2.3-54-g00ecf From bb536a2e737b8d23f3514607bc3d6ff54ed19f0f Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 11:08:51 -0500 Subject: Check for expected warnings in apply_ed_diff --- src/test/test_consdiff.c | 26 +++++++++++++++++++++++++- 1 file changed, 25 insertions(+), 1 deletion(-) (limited to 'src/test') diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 5014c7aebb..15f5575d78 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -608,6 +608,7 @@ test_consdiff_apply_ed_diff(void *arg) (void)arg; cons1 = smartlist_new(); diff = smartlist_new(); + setup_capture_of_logs(LOG_WARN); smartlist_split_string(cons1, "A:B:C:D:E", ":", 0, 0); @@ -615,68 +616,90 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"a"); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); - smartlist_clear(diff); + expect_single_log_msg_containing("an ed command was missing a line number"); /* Range without command. */ smartlist_add(diff, (char*)"1"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("a line with no ed command was found"); smartlist_clear(diff); /* Range without end. */ smartlist_add(diff, (char*)"1,"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an ed command was missing a range " + "end line number."); smartlist_clear(diff); /* Incoherent ranges. */ smartlist_add(diff, (char*)"1,1"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an invalid range was found"); smartlist_clear(diff); smartlist_add(diff, (char*)"3,2"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an invalid range was found"); smartlist_clear(diff); /* Script is not in reverse order. */ smartlist_add(diff, (char*)"1d"); smartlist_add(diff, (char*)"3d"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("its commands are not properly sorted"); smartlist_clear(diff); /* Script contains unrecognised commands longer than one char. */ smartlist_add(diff, (char*)"1foo"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an ed command longer than one char was " + "found"); smartlist_clear(diff); /* Script contains unrecognised commands. */ smartlist_add(diff, (char*)"1e"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("an unrecognised ed command was found"); smartlist_clear(diff); /* Command that should be followed by at least one line and a ".", but * isn't. */ smartlist_add(diff, (char*)"0a"); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("it has an ed command that tries to " + "insert zero lines."); /* Now it is followed by a ".", but it inserts zero lines. */ smartlist_add(diff, (char*)"."); + mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("it has an ed command that tries to " + "insert zero lines."); smartlist_clear(diff); @@ -741,6 +764,7 @@ test_consdiff_apply_ed_diff(void *arg) tt_str_op("E", OP_EQ, smartlist_get(cons2, 5)); done: + teardown_capture_of_logs(); if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); smartlist_free(cons1); -- cgit v1.2.3-54-g00ecf From c6046f4db8b182133ccc756529b508522be180c8 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 11:36:07 -0500 Subject: Tweak&test log messages on apply_diff --- src/or/consdiff.c | 11 ++++++----- src/test/test_consdiff.c | 24 ++++++++++++++++++++++++ 2 files changed, 30 insertions(+), 5 deletions(-) (limited to 'src/test') diff --git a/src/or/consdiff.c b/src/or/consdiff.c index defa1cfba5..73ac7977dd 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -879,7 +879,7 @@ consdiff_get_digests(smartlist_t *diff, 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."); + "the necessary digests."); goto error_cleanup; } @@ -893,7 +893,7 @@ consdiff_get_digests(smartlist_t *diff, 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."); + "base16-encoded digests of incorrect size."); goto error_cleanup; } @@ -909,7 +909,7 @@ consdiff_get_digests(smartlist_t *diff, 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."); + "malformed digests."); goto error_cleanup; } @@ -958,7 +958,7 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, 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 base consensus doesn't match the digest as found in " "the consensus diff header."); base16_encode(hex_digest1, HEX_DIGEST256_LEN+1, digests1->d[DIGEST_SHA256], DIGEST256_LEN); @@ -973,6 +973,7 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, /* To avoid copying memory or iterating over all the elements, make a * read-only smartlist without the two header lines. */ + /* XXXX prop140 abstraction violation; never do this. */ smartlist_t *ed_diff = tor_malloc(sizeof(smartlist_t)); ed_diff->list = diff->list+2; ed_diff->num_used = diff->num_used-2; @@ -999,7 +1000,7 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, 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 resulting consensus doesn't match the digest as found in " "the consensus diff header."); char hex_digest2[HEX_DIGEST256_LEN+1]; char e_hex_digest2[HEX_DIGEST256_LEN+1]; diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 15f5575d78..00fba67b05 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -856,6 +856,7 @@ test_consdiff_apply_diff(void *arg) (void)arg; cons1 = smartlist_new(); diff = smartlist_new(); + setup_capture_of_logs(LOG_INFO); cons1_str = tor_strdup( "header\nnetwork-status-version foo\n" @@ -870,33 +871,44 @@ test_consdiff_apply_diff(void *arg) /* diff doesn't have enough lines. */ cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("too short") /* first line doesn't match format-version string. */ smartlist_add(diff, (char*)"foo-bar"); smartlist_add(diff, (char*)"header-line"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("format is not known") /* 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"); + smartlist_add(diff, (char*)"x"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("does not include the necessary digests") /* 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"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("does not include the necessary digests") /* 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"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("includes base16-encoded digests of " + "incorrect size") /* base16 sha256 digests contain non-base16 characters. */ smartlist_clear(diff); @@ -904,8 +916,10 @@ test_consdiff_apply_diff(void *arg) smartlist_add(diff, (char*)"hash" " ????????????????????????????????????????????????????????????????" " ----------------------------------------------------------------"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("includes malformed digests") /* Invalid ed diff. * As tested in apply_ed_diff, but check that apply_diff does return NULL if @@ -918,8 +932,11 @@ test_consdiff_apply_diff(void *arg) /* sha256 of cons2. */ " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA"); smartlist_add(diff, (char*)"foobar"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("because an ed command was missing a line " + "number") /* Base consensus doesn't match its digest as found in the diff. */ smartlist_clear(diff); @@ -929,8 +946,11 @@ test_consdiff_apply_diff(void *arg) " 3333333333333333333333333333333333333333333333333333333333333333" /* sha256 of cons2. */ " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_log_msg_containing("base consensus doesn't match the digest " + "as found"); /* Resulting consensus doesn't match its digest as found in the diff. */ smartlist_clear(diff); @@ -940,8 +960,11 @@ test_consdiff_apply_diff(void *arg) " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" /* bogus sha256. */ " 3333333333333333333333333333333333333333333333333333333333333333"); + mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); + expect_log_msg_containing("resulting consensus doesn't match the " + "digest as found") /* Very simple test, only to see that nothing errors. */ smartlist_clear(diff); @@ -988,6 +1011,7 @@ test_consdiff_apply_diff(void *arg) smartlist_clear(diff); done: + teardown_capture_of_logs(); tor_free(cons1_str); smartlist_free(cons1); smartlist_free(diff); -- cgit v1.2.3-54-g00ecf From c86e77ac20997282ca007ac7347e9910f55f880e Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 12:04:45 -0500 Subject: Cover two more failing cases with unit tests --- src/test/test_consdiff.c | 28 +++++++++++++++++++++++++++- 1 file changed, 27 insertions(+), 1 deletion(-) (limited to 'src/test') diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 00fba67b05..b511d94ec3 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -703,6 +703,17 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); + /* Now it it inserts something, but has no terminator. */ + smartlist_add(diff, (char*)"0a"); + smartlist_add(diff, (char*)"hello"); + mock_clean_saved_logs(); + cons2 = apply_ed_diff(cons1, diff); + tt_ptr_op(NULL, OP_EQ, cons2); + expect_single_log_msg_containing("lines to be inserted that don't end with " + "a \".\"."); + + smartlist_clear(diff); + /* Test appending text, 'a'. */ smartlist_split_string(diff, "3a:U:O:.:0a:V:.", ":", 0, 0); cons2 = apply_ed_diff(cons1, diff); @@ -964,7 +975,22 @@ test_consdiff_apply_diff(void *arg) cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); expect_log_msg_containing("resulting consensus doesn't match the " - "digest as found") + "digest as found"); + + /* Resulting consensus digest cannot be computed */ + smartlist_clear(diff); + smartlist_add(diff, (char*)"network-status-diff-version 1"); + smartlist_add(diff, (char*)"hash" + /* sha256 of cons1. */ + " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" + /* bogus sha256. */ + " 3333333333333333333333333333333333333333333333333333333333333333"); + smartlist_add(diff, (char*)"1,2d"); // remove starting line + mock_clean_saved_logs(); + cons2 = consdiff_apply_diff(cons1, diff, &digests1); + tt_ptr_op(NULL, OP_EQ, cons2); + expect_log_msg_containing("Could not compute digests of the consensus " + "resulting from applying a consensus diff."); /* Very simple test, only to see that nothing errors. */ smartlist_clear(diff); -- cgit v1.2.3-54-g00ecf From d6594bfa8c56a6a6896c8ca8761e39f0c3dd59a2 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 12:30:13 -0500 Subject: Add a couple more cases to reach 100% coverage. --- src/test/test_consdiff.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'src/test') diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index b511d94ec3..bbe3532e5a 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -449,6 +449,25 @@ test_consdiff_gen_ed_diff(void *arg) "because the target consensus doesn't have its router entries sorted " "properly."); + /* Same as the two above, but with the reversed thing immediately after a + match. (The code handles this differently) */ + smartlist_del(cons1, 0); + smartlist_add(cons1, (char*)"r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc"); + + mock_clean_saved_logs(); + diff = gen_ed_diff(cons1, cons2); + tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the base consensus doesn't have its router entries sorted " + "properly."); + + mock_clean_saved_logs(); + diff = gen_ed_diff(cons2, cons1); + tt_ptr_op(NULL, OP_EQ, diff); + expect_single_log_msg_containing("Refusing to generate consensus diff " + "because the target consensus doesn't have its router entries sorted " + "properly."); + /* Identity hashes are repeated, return NULL. */ smartlist_clear(cons1); -- cgit v1.2.3-54-g00ecf From 3647751c2ac093d3fffb6243813f622348bf756d Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 13:02:00 -0500 Subject: prop140: Use sha3-256, not sha2-256 This is a protocol update from recent prop140 changes. Also, per #21673, we need to check the entire document, including signatures. --- src/or/consdiff.c | 38 +++++++++++++++--------- src/or/consdiff.h | 10 +++++-- src/test/test_consdiff.c | 76 +++++++++++++++++++++++++----------------------- 3 files changed, 71 insertions(+), 53 deletions(-) (limited to 'src/test') diff --git a/src/or/consdiff.c b/src/or/consdiff.c index f8cf180402..296b43d38b 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -39,6 +39,15 @@ static const char* ns_diff_version = "network-status-diff-version 1"; static const char* hash_token = "hash"; +STATIC int +consensus_compute_digest(const char *cons, + consensus_digest_t *digest_out) +{ + int r = crypto_digest256((char*)digest_out->sha3_256, + cons, strlen(cons), DIGEST_SHA3_256); + return r; +} + /** 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 @@ -790,7 +799,7 @@ apply_ed_diff(smartlist_t *cons1, smartlist_t *diff) */ smartlist_t * consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, - common_digests_t *digests1, common_digests_t *digests2) + consensus_digest_t *digests1, consensus_digest_t *digests2) { smartlist_t *ed_diff = gen_ed_diff(cons1, cons2); /* ed diff could not be generated - reason already logged by gen_ed_diff. */ @@ -824,9 +833,9 @@ consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, 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); + (const char*)digests1->sha3_256, DIGEST256_LEN); base16_encode(cons2_hash_hex, HEX_DIGEST256_LEN+1, - digests2->d[DIGEST_SHA256], DIGEST256_LEN); + (const char*)digests2->sha3_256, DIGEST256_LEN); /* Create the resulting consensus diff. */ smartlist_t *result = smartlist_new(); @@ -874,7 +883,7 @@ consdiff_get_digests(smartlist_t *diff, goto error_cleanup; } - /* Grab the SHA256 base16 hashes. */ + /* Grab the base16 digests. */ hash_words = smartlist_new(); smartlist_split_string(hash_words, smartlist_get(diff, 1), " ", 0, 0); @@ -889,7 +898,7 @@ consdiff_get_digests(smartlist_t *diff, /* 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. + * proper base16-encoded digests. */ cons1_hash_hex = smartlist_get(hash_words, 1); cons2_hash_hex = smartlist_get(hash_words, 2); @@ -936,7 +945,7 @@ consdiff_get_digests(smartlist_t *diff, */ char * consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, - common_digests_t *digests1) + consensus_digest_t *digests1) { smartlist_t *cons2 = NULL; char *cons2_str = NULL; @@ -948,7 +957,7 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, } /* See that the consensus that was given to us matches its hash. */ - if (fast_memneq(digests1->d[DIGEST_SHA256], e_cons1_hash, + if (fast_memneq(digests1->sha3_256, e_cons1_hash, DIGEST256_LEN)) { char hex_digest1[HEX_DIGEST256_LEN+1]; char e_hex_digest1[HEX_DIGEST256_LEN+1]; @@ -956,9 +965,9 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, "the base consensus doesn't match the digest as found in " "the consensus diff header."); base16_encode(hex_digest1, HEX_DIGEST256_LEN+1, - digests1->d[DIGEST_SHA256], DIGEST256_LEN); + (const char *)digests1->sha3_256, DIGEST256_LEN); base16_encode(e_hex_digest1, HEX_DIGEST256_LEN+1, - e_cons1_hash, DIGEST256_LEN); + e_cons1_hash, DIGEST256_LEN); log_warn(LD_CONSDIFF, "Expected: %s; found: %s", hex_digest1, e_hex_digest1); goto error_cleanup; @@ -983,16 +992,17 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, cons2_str = smartlist_join_strings(cons2, "\n", 1, NULL); - common_digests_t cons2_digests; - if (router_get_networkstatus_v3_hashes(cons2_str, - &cons2_digests)<0) { + consensus_digest_t cons2_digests; + if (consensus_compute_digest(cons2_str, &cons2_digests) < 0) { + /* LCOV_EXCL_START -- digest can't fail */ log_warn(LD_CONSDIFF, "Could not compute digests of the consensus " "resulting from applying a consensus diff."); goto error_cleanup; + /* LCOV_EXCL_STOP */ } /* See that the resulting consensus matches its hash. */ - if (fast_memneq(cons2_digests.d[DIGEST_SHA256], e_cons2_hash, + if (fast_memneq(cons2_digests.sha3_256, e_cons2_hash, DIGEST256_LEN)) { log_warn(LD_CONSDIFF, "Refusing to apply consensus diff because " "the resulting consensus doesn't match the digest as found in " @@ -1000,7 +1010,7 @@ consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, 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); + (const char *)cons2_digests.sha3_256, DIGEST256_LEN); base16_encode(e_hex_digest2, HEX_DIGEST256_LEN+1, e_cons2_hash, DIGEST256_LEN); log_warn(LD_CONSDIFF, "Expected: %s; found: %s", diff --git a/src/or/consdiff.h b/src/or/consdiff.h index 0f4a25a01c..1fffaedb00 100644 --- a/src/or/consdiff.h +++ b/src/or/consdiff.h @@ -7,10 +7,14 @@ #include "or.h" +typedef struct consensus_digest_t { + uint8_t sha3_256[DIGEST256_LEN]; +} consensus_digest_t; + smartlist_t *consdiff_gen_diff(smartlist_t *cons1, smartlist_t *cons2, - common_digests_t *digests1, common_digests_t *digests2); + consensus_digest_t *digests1, consensus_digest_t *digests2); char *consdiff_apply_diff(smartlist_t *cons1, smartlist_t *diff, - common_digests_t *digests1); + consensus_digest_t *digests1); int consdiff_get_digests(smartlist_t *diff, char *digest1_out, char *digest2_out); @@ -45,6 +49,8 @@ STATIC int smartlist_slice_string_pos(smartlist_slice_t *slice, const char *string); STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, smartlist_slice_t *slice1, smartlist_slice_t *slice2); +STATIC int consensus_compute_digest(const char *cons, + consensus_digest_t *digest_out); #endif #endif diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index bbe3532e5a..2afebfe2ab 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -8,7 +8,6 @@ #include "test.h" #include "consdiff.h" -#include "routerparse.h" #include "log_test_helpers.h" static void @@ -808,7 +807,7 @@ 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; + consensus_digest_t digests1, digests2; (void)arg; cons1 = smartlist_new(); cons2 = smartlist_new(); @@ -817,22 +816,22 @@ test_consdiff_gen_diff(void *arg) * 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" + "network-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" + "network-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)); + consensus_compute_digest(cons1_str, &digests1)); tt_int_op(0, OP_EQ, - router_get_networkstatus_v3_hashes(cons2_str, &digests2)); + consensus_compute_digest(cons2_str, &digests2)); tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); tor_split_lines(cons2, cons2_str, (int)strlen(cons2_str)); @@ -843,13 +842,13 @@ test_consdiff_gen_diff(void *arg) /* Check that the headers are done properly. */ tor_free(cons1_str); cons1_str = tor_strdup( - "header\nnetwork-status-version foo\n" + "network-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)); + consensus_compute_digest(cons1_str, &digests1)); smartlist_clear(cons1); tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2); @@ -857,11 +856,11 @@ test_consdiff_gen_diff(void *arg) 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", + "06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4 " + "7AFECEFA4599BA33D603653E3D2368F648DF4AC4723929B0F7CF39281596B0C1", 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("3,4d", OP_EQ, smartlist_get(diff, 2)); + tt_str_op("1a", 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)); @@ -882,20 +881,20 @@ test_consdiff_apply_diff(void *arg) { smartlist_t *cons1=NULL, *diff=NULL; char *cons1_str=NULL, *cons2 = NULL; - common_digests_t digests1; + consensus_digest_t digests1; (void)arg; cons1 = smartlist_new(); diff = smartlist_new(); setup_capture_of_logs(LOG_INFO); cons1_str = tor_strdup( - "header\nnetwork-status-version foo\n" + "network-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)); + consensus_compute_digest(cons1_str, &digests1)); tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); /* diff doesn't have enough lines. */ @@ -930,7 +929,7 @@ test_consdiff_apply_diff(void *arg) tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("does not include the necessary digests") - /* base16 sha256 digests do not have the expected length. */ + /* base16 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"); @@ -940,7 +939,7 @@ test_consdiff_apply_diff(void *arg) expect_single_log_msg_containing("includes base16-encoded digests of " "incorrect size") - /* base16 sha256 digests contain non-base16 characters. */ + /* base16 digests contain non-base16 characters. */ smartlist_clear(diff); smartlist_add(diff, (char*)"network-status-diff-version 1"); smartlist_add(diff, (char*)"hash" @@ -957,8 +956,8 @@ test_consdiff_apply_diff(void *arg) smartlist_clear(diff); smartlist_add(diff, (char*)"network-status-diff-version 1"); smartlist_add(diff, (char*)"hash" - /* sha256 of cons1. */ - " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" + /* sha3 of cons1. */ + " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" /* sha256 of cons2. */ " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA"); smartlist_add(diff, (char*)"foobar"); @@ -986,9 +985,9 @@ test_consdiff_apply_diff(void *arg) smartlist_clear(diff); smartlist_add(diff, (char*)"network-status-diff-version 1"); smartlist_add(diff, (char*)"hash" - /* sha256 of cons1. */ - " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" - /* bogus sha256. */ + /* sha3 of cons1. */ + " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" + /* bogus sha3. */ " 3333333333333333333333333333333333333333333333333333333333333333"); mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); @@ -996,13 +995,15 @@ test_consdiff_apply_diff(void *arg) expect_log_msg_containing("resulting consensus doesn't match the " "digest as found"); +#if 0 + /* XXXX No longer possible, since we aren't using the other algorithm. */ /* Resulting consensus digest cannot be computed */ smartlist_clear(diff); smartlist_add(diff, (char*)"network-status-diff-version 1"); smartlist_add(diff, (char*)"hash" - /* sha256 of cons1. */ - " C2199B6827514F39ED9B3F2E2E73735C6C5468FD636240BB454C526220DE702A" - /* bogus sha256. */ + /* sha3 of cons1. */ + " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" + /* bogus sha3. */ " 3333333333333333333333333333333333333333333333333333333333333333"); smartlist_add(diff, (char*)"1,2d"); // remove starting line mock_clean_saved_logs(); @@ -1010,22 +1011,23 @@ test_consdiff_apply_diff(void *arg) tt_ptr_op(NULL, OP_EQ, cons2); expect_log_msg_containing("Could not compute digests of the consensus " "resulting from applying a consensus diff."); +#endif /* 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"); + /* sha3 of cons1. */ + " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" + /* sha3 of cons2. */ + " 90A418881B2FCAB3D9E60EE02E4D666D56CFA38F8A3B7AA3E0ADBA530DDA9353"); + smartlist_add(diff, (char*)"3c"); 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" + "network-status-version foo\n" "r name ccccccccccccccccc etc\nsample\n" "r name eeeeeeeeeeeeeeeee etc\nbar\n" "directory-signature foo bar\nbar\n", OP_EQ, @@ -1036,17 +1038,17 @@ test_consdiff_apply_diff(void *arg) 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"); + /* sha3 of cons1. */ + " 06646d6cf563a41869d3b02e73254372ae3140046c5e7d83c9f71e54976af9b4" + /* sha3 of cons2. */ + " 90a418881b2fcab3d9e60ee02e4d666d56cfa38f8a3b7aa3e0adba530dda9353"); + smartlist_add(diff, (char*)"3c"); 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" + "network-status-version foo\n" "r name ccccccccccccccccc etc\nsample\n" "r name eeeeeeeeeeeeeeeee etc\nbar\n" "directory-signature foo bar\nbar\n", OP_EQ, -- cgit v1.2.3-54-g00ecf From eff9fbd17d5fb4b1c196c241da4513d51893f52e Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 13:15:43 -0500 Subject: Fix an abstraction violation. Don't alias the insides of smartlist_t; that way lies madness. --- src/or/consdiff.c | 25 +++++++++---------------- src/or/consdiff.h | 3 ++- src/test/test_consdiff.c | 30 +++++++++++++++--------------- 3 files changed, 26 insertions(+), 32 deletions(-) (limited to 'src/test') diff --git a/src/or/consdiff.c b/src/or/consdiff.c index 2b1439569c..6fe8360902 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -654,18 +654,19 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) return NULL; } -/** Apply the ed diff to the consensus and return a new consensus, also as a - * line-based smartlist. Will return NULL if the ed diff is not properly - * formatted. +/** Apply the ed diff, starting at diff_starting_line, to the consensus + * and return a new consensus, also as a line-based smartlist. Will return + * NULL if the ed diff is not properly formatted. */ STATIC smartlist_t * -apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff) +apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, + int diff_starting_line) { int diff_len = smartlist_len(diff); int j = smartlist_len(cons1); smartlist_t *cons2 = smartlist_new(); - for (int i=0; ilist = diff->list+2; - ed_diff->num_used = diff->num_used-2; - ed_diff->capacity = diff->capacity-2; - cons2 = apply_ed_diff(cons1, ed_diff); - tor_free(ed_diff); + /* Skip the first two lines. */ + cons2 = apply_ed_diff(cons1, diff, 2); /* ed diff could not be applied - reason already logged by apply_ed_diff. */ if (!cons2) { diff --git a/src/or/consdiff.h b/src/or/consdiff.h index 3316ed6879..42cd3afa83 100644 --- a/src/or/consdiff.h +++ b/src/or/consdiff.h @@ -37,7 +37,8 @@ typedef struct smartlist_slice_t { STATIC smartlist_t *gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2); STATIC smartlist_t *apply_ed_diff(const smartlist_t *cons1, - const smartlist_t *diff); + const smartlist_t *diff, + int start_line); STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, bitarray_t *changed1, bitarray_t *changed2); STATIC smartlist_slice_t *smartlist_slice(const smartlist_t *list, diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 2afebfe2ab..12213aab64 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -632,7 +632,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Command without range. */ smartlist_add(diff, (char*)"a"); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); smartlist_clear(diff); expect_single_log_msg_containing("an ed command was missing a line number"); @@ -640,7 +640,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Range without command. */ smartlist_add(diff, (char*)"1"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("a line with no ed command was found"); @@ -649,7 +649,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Range without end. */ smartlist_add(diff, (char*)"1,"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an ed command was missing a range " "end line number."); @@ -659,7 +659,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Incoherent ranges. */ smartlist_add(diff, (char*)"1,1"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an invalid range was found"); @@ -667,7 +667,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"3,2"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an invalid range was found"); @@ -677,7 +677,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"1d"); smartlist_add(diff, (char*)"3d"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("its commands are not properly sorted"); @@ -686,7 +686,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Script contains unrecognised commands longer than one char. */ smartlist_add(diff, (char*)"1foo"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an ed command longer than one char was " "found"); @@ -696,7 +696,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Script contains unrecognised commands. */ smartlist_add(diff, (char*)"1e"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("an unrecognised ed command was found"); @@ -706,7 +706,7 @@ test_consdiff_apply_ed_diff(void *arg) * isn't. */ smartlist_add(diff, (char*)"0a"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("it has an ed command that tries to " "insert zero lines."); @@ -714,7 +714,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Now it is followed by a ".", but it inserts zero lines. */ smartlist_add(diff, (char*)"."); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("it has an ed command that tries to " "insert zero lines."); @@ -725,7 +725,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_add(diff, (char*)"0a"); smartlist_add(diff, (char*)"hello"); mock_clean_saved_logs(); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); expect_single_log_msg_containing("lines to be inserted that don't end with " "a \".\"."); @@ -734,7 +734,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test appending text, 'a'. */ smartlist_split_string(diff, "3a:U:O:.:0a:V:.", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(8, OP_EQ, smartlist_len(cons2)); tt_str_op("V", OP_EQ, smartlist_get(cons2, 0)); @@ -753,7 +753,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test deleting text, 'd'. */ smartlist_split_string(diff, "4d:1,2d", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(2, OP_EQ, smartlist_len(cons2)); tt_str_op("C", OP_EQ, smartlist_get(cons2, 0)); @@ -766,7 +766,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test changing text, 'c'. */ smartlist_split_string(diff, "4c:T:X:.:1, 2c:M:.", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(5, OP_EQ, smartlist_len(cons2)); tt_str_op("M", OP_EQ, smartlist_get(cons2, 0)); @@ -782,7 +782,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Test 'a', 'd' and 'c' together. */ smartlist_split_string(diff, "4c:T:X:.:2d:0a:M:.", ":", 0, 0); - cons2 = apply_ed_diff(cons1, diff); + cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(6, OP_EQ, smartlist_len(cons2)); tt_str_op("M", OP_EQ, smartlist_get(cons2, 0)); -- cgit v1.2.3-54-g00ecf From dd92579b63fa012bcbe081ab66ff40d6a036b765 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 7 Mar 2017 15:07:27 -0500 Subject: Add fuzzers for consensus diff backend code This takes two fuzzers: one which generates a diff and makes sure it works, and one which applies a diff. So far, they won't crash, but there's a bug in my string-manipulation code someplace that I'm having to work around, related to the case where you have a blank line at the end of a file, or where you diff a file with itself. --- src/test/fuzz/fuzz_diff.c | 67 +++++++++++++++++++++++++++++++++++++++++ src/test/fuzz/fuzz_diff_apply.c | 65 +++++++++++++++++++++++++++++++++++++++ src/test/fuzz/include.am | 47 ++++++++++++++++++++++++++++- 3 files changed, 178 insertions(+), 1 deletion(-) create mode 100644 src/test/fuzz/fuzz_diff.c create mode 100644 src/test/fuzz/fuzz_diff_apply.c (limited to 'src/test') diff --git a/src/test/fuzz/fuzz_diff.c b/src/test/fuzz/fuzz_diff.c new file mode 100644 index 0000000000..c241f63dc4 --- /dev/null +++ b/src/test/fuzz/fuzz_diff.c @@ -0,0 +1,67 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#define CONSDIFF_PRIVATE + +#include "orconfig.h" +#include "or.h" +#include "consdiff.h" + +#include "fuzzing.h" + +static int +mock_consensus_compute_digest_(const char *c, consensus_digest_t *d) +{ + (void)c; + memset(d->sha3_256, 3, sizeof(d->sha3_256)); + return 0; +} + +int +fuzz_init(void) +{ + MOCK(consensus_compute_digest, mock_consensus_compute_digest_); + return 0; +} + +int +fuzz_cleanup(void) +{ + UNMOCK(consensus_compute_digest); + return 0; +} + +int +fuzz_main(const uint8_t *stdin_buf, size_t data_size) +{ +#define SEP "=====\n" +#define SEPLEN strlen(SEP) + const uint8_t *separator = tor_memmem(stdin_buf, data_size, SEP, SEPLEN); + if (! separator) + return 0; + size_t c1_len = separator - stdin_buf; + char *c1 = tor_memdup_nulterm(stdin_buf, c1_len); + size_t c2_len = data_size - c1_len - SEPLEN; + char *c2 = tor_memdup_nulterm(separator + SEPLEN, c2_len); + + char *c3 = consensus_diff_generate(c1, c2); + + if (c3) { + char *c4 = consensus_diff_apply(c1, c3); + tor_assert(c4); + if (strcmp(c2, c4)) { + printf("%s\n", escaped(c1)); + printf("%s\n", escaped(c2)); + printf("%s\n", escaped(c3)); + printf("%s\n", escaped(c4)); + } + tor_assert(! strcmp(c2, c4)); + tor_free(c3); + tor_free(c4); + } + tor_free(c1); + tor_free(c2); + + return 0; +} + diff --git a/src/test/fuzz/fuzz_diff_apply.c b/src/test/fuzz/fuzz_diff_apply.c new file mode 100644 index 0000000000..8d7bf751bf --- /dev/null +++ b/src/test/fuzz/fuzz_diff_apply.c @@ -0,0 +1,65 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#define CONSDIFF_PRIVATE + +#include "orconfig.h" +#include "or.h" +#include "consdiff.h" + +#include "fuzzing.h" + +static int +mock_consensus_compute_digest_(const char *c, consensus_digest_t *d) +{ + (void)c; + memset(d->sha3_256, 3, sizeof(d->sha3_256)); + return 0; +} + +static int +mock_consensus_digest_eq_(const uint8_t *a, const uint8_t *b) +{ + (void)a; + (void)b; + return 1; +} + +int +fuzz_init(void) +{ + MOCK(consensus_compute_digest, mock_consensus_compute_digest_); + MOCK(consensus_digest_eq, mock_consensus_digest_eq_); + return 0; +} + +int +fuzz_cleanup(void) +{ + UNMOCK(consensus_compute_digest); + UNMOCK(consensus_digest_eq); + return 0; +} + +int +fuzz_main(const uint8_t *stdin_buf, size_t data_size) +{ +#define SEP "=====\n" +#define SEPLEN strlen(SEP) + const uint8_t *separator = tor_memmem(stdin_buf, data_size, SEP, SEPLEN); + if (! separator) + return 0; + size_t c1_len = separator - stdin_buf; + char *c1 = tor_memdup_nulterm(stdin_buf, c1_len); + size_t c2_len = data_size - c1_len - SEPLEN; + char *c2 = tor_memdup_nulterm(separator + SEPLEN, c2_len); + + char *c3 = consensus_diff_apply(c1, c2); + + tor_free(c1); + tor_free(c2); + tor_free(c3); + + return 0; +} + diff --git a/src/test/fuzz/include.am b/src/test/fuzz/include.am index 806710879b..97afd18215 100644 --- a/src/test/fuzz/include.am +++ b/src/test/fuzz/include.am @@ -48,6 +48,22 @@ src_test_fuzz_fuzz_descriptor_CFLAGS = $(FUZZING_CFLAGS) src_test_fuzz_fuzz_descriptor_LDFLAGS = $(FUZZING_LDFLAG) src_test_fuzz_fuzz_descriptor_LDADD = $(FUZZING_LIBS) +src_test_fuzz_fuzz_diff_SOURCES = \ + src/test/fuzz/fuzzing_common.c \ + src/test/fuzz/fuzz_diff.c +src_test_fuzz_fuzz_diff_CPPFLAGS = $(FUZZING_CPPFLAGS) +src_test_fuzz_fuzz_diff_CFLAGS = $(FUZZING_CFLAGS) +src_test_fuzz_fuzz_diff_LDFLAGS = $(FUZZING_LDFLAG) +src_test_fuzz_fuzz_diff_LDADD = $(FUZZING_LIBS) + +src_test_fuzz_fuzz_diff_apply_SOURCES = \ + src/test/fuzz/fuzzing_common.c \ + src/test/fuzz/fuzz_diff_apply.c +src_test_fuzz_fuzz_diff_apply_CPPFLAGS = $(FUZZING_CPPFLAGS) +src_test_fuzz_fuzz_diff_apply_CFLAGS = $(FUZZING_CFLAGS) +src_test_fuzz_fuzz_diff_apply_LDFLAGS = $(FUZZING_LDFLAG) +src_test_fuzz_fuzz_diff_apply_LDADD = $(FUZZING_LIBS) + src_test_fuzz_fuzz_http_SOURCES = \ src/test/fuzz/fuzzing_common.c \ src/test/fuzz/fuzz_http.c @@ -99,6 +115,8 @@ src_test_fuzz_fuzz_vrs_LDADD = $(FUZZING_LIBS) FUZZERS = \ src/test/fuzz/fuzz-consensus \ src/test/fuzz/fuzz-descriptor \ + src/test/fuzz/fuzz-diff \ + src/test/fuzz/fuzz-diff-apply \ src/test/fuzz/fuzz-extrainfo \ src/test/fuzz/fuzz-http \ src/test/fuzz/fuzz-hsdescv2 \ @@ -106,7 +124,6 @@ FUZZERS = \ src/test/fuzz/fuzz-microdesc \ src/test/fuzz/fuzz-vrs - LIBFUZZER = /home/nickm/build/libfuzz/libFuzzer.a LIBFUZZER_CPPFLAGS = $(FUZZING_CPPFLAGS) -DLLVM_FUZZ LIBFUZZER_CFLAGS = $(FUZZING_CFLAGS) @@ -128,6 +145,20 @@ src_test_fuzz_lf_fuzz_descriptor_CFLAGS = $(LIBFUZZER_CFLAGS) src_test_fuzz_lf_fuzz_descriptor_LDFLAGS = $(LIBFUZZER_LDFLAG) src_test_fuzz_lf_fuzz_descriptor_LDADD = $(LIBFUZZER_LIBS) +src_test_fuzz_lf_fuzz_diff_SOURCES = \ + $(src_test_fuzz_fuzz_diff_SOURCES) +src_test_fuzz_lf_fuzz_diff_CPPFLAGS = $(LIBFUZZER_CPPFLAGS) +src_test_fuzz_lf_fuzz_diff_CFLAGS = $(LIBFUZZER_CFLAGS) +src_test_fuzz_lf_fuzz_diff_LDFLAGS = $(LIBFUZZER_LDFLAG) +src_test_fuzz_lf_fuzz_diff_LDADD = $(LIBFUZZER_LIBS) + +src_test_fuzz_lf_fuzz_diff_apply_SOURCES = \ + $(src_test_fuzz_fuzz_diff_apply_SOURCES) +src_test_fuzz_lf_fuzz_diff_apply_CPPFLAGS = $(LIBFUZZER_CPPFLAGS) +src_test_fuzz_lf_fuzz_diff_apply_CFLAGS = $(LIBFUZZER_CFLAGS) +src_test_fuzz_lf_fuzz_diff_apply_LDFLAGS = $(LIBFUZZER_LDFLAG) +src_test_fuzz_lf_fuzz_diff_apply_LDADD = $(LIBFUZZER_LIBS) + src_test_fuzz_lf_fuzz_extrainfo_SOURCES = \ $(src_test_fuzz_fuzz_extrainfo_SOURCES) src_test_fuzz_lf_fuzz_extrainfo_CPPFLAGS = $(LIBFUZZER_CPPFLAGS) @@ -172,6 +203,8 @@ src_test_fuzz_lf_fuzz_vrs_LDADD = $(LIBFUZZER_LIBS) LIBFUZZER_FUZZERS = \ src/test/fuzz/lf-fuzz-consensus \ + src/test/fuzz/lf-fuzz-diff \ + src/test/fuzz/lf-fuzz-diff-apply \ src/test/fuzz/lf-fuzz-descriptor \ src/test/fuzz/lf-fuzz-extrainfo \ src/test/fuzz/lf-fuzz-http \ @@ -198,6 +231,16 @@ src_test_fuzz_liboss_fuzz_descriptor_a_SOURCES = \ src_test_fuzz_liboss_fuzz_descriptor_a_CPPFLAGS = $(LIBOSS_FUZZ_CPPFLAGS) src_test_fuzz_liboss_fuzz_descriptor_a_CFLAGS = $(LIBOSS_FUZZ_CFLAGS) +src_test_fuzz_liboss_fuzz_diff_a_SOURCES = \ + $(src_test_fuzz_fuzz_diff_SOURCES) +src_test_fuzz_liboss_fuzz_diff_a_CPPFLAGS = $(LIBOSS_FUZZ_CPPFLAGS) +src_test_fuzz_liboss_fuzz_diff_a_CFLAGS = $(LIBOSS_FUZZ_CFLAGS) + +src_test_fuzz_liboss_fuzz_diff_apply_a_SOURCES = \ + $(src_test_fuzz_fuzz_diff_apply_SOURCES) +src_test_fuzz_liboss_fuzz_diff_apply_a_CPPFLAGS = $(LIBOSS_FUZZ_CPPFLAGS) +src_test_fuzz_liboss_fuzz_diff_apply_a_CFLAGS = $(LIBOSS_FUZZ_CFLAGS) + src_test_fuzz_liboss_fuzz_extrainfo_a_SOURCES = \ $(src_test_fuzz_fuzz_extrainfo_SOURCES) src_test_fuzz_liboss_fuzz_extrainfo_a_CPPFLAGS = $(LIBOSS_FUZZ_CPPFLAGS) @@ -231,6 +274,8 @@ src_test_fuzz_liboss_fuzz_vrs_a_CFLAGS = $(LIBOSS_FUZZ_CFLAGS) OSS_FUZZ_FUZZERS = \ src/test/fuzz/liboss-fuzz-consensus.a \ src/test/fuzz/liboss-fuzz-descriptor.a \ + src/test/fuzz/liboss-fuzz-diff.a \ + src/test/fuzz/liboss-fuzz-diff-apply.a \ src/test/fuzz/liboss-fuzz-extrainfo.a \ src/test/fuzz/liboss-fuzz-http.a \ src/test/fuzz/liboss-fuzz-hsdescv2.a \ -- cgit v1.2.3-54-g00ecf From d8c129a11ae6310a95522e286a9ebc22a44e3be5 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 14 Mar 2017 15:00:39 -0400 Subject: Avoid all needless memory copies when computing consensus diffs. Previously, we operated on smartlists of NUL-terminated strings, which required us to copy both inputs to produce the NUL-terminated strings. Then we copied parts of _those_ inputs to produce an output smartlist of NUL-terminated strings. And finally, we concatenated everything into a final resulting string. This implementation, instead, uses a pointer-and-extent pattern to represent each line as a pointer into the original inputs and a length. These line objects are then added by reference into the output. No actual bytes are copied from the original strings until we finally concatenate the final result together. Bookkeeping structures and newly allocated strings (like ed commands) are allocated inside a memarea, to avoid needless mallocs or complicated should-I-free-this-or-not bookkeeping. In my measurements, this improves CPU performance by something like 18%. The memory savings should be much, much higher. --- src/or/consdiff.c | 337 +++++++++++++++++++++------------ src/or/consdiff.h | 30 ++- src/test/bench.c | 22 +++ src/test/test_consdiff.c | 478 ++++++++++++++++++++++++----------------------- 4 files changed, 506 insertions(+), 361 deletions(-) (limited to 'src/test') diff --git a/src/or/consdiff.c b/src/or/consdiff.c index dfb97d432a..848ea13ea7 100644 --- a/src/or/consdiff.c +++ b/src/or/consdiff.c @@ -28,12 +28,19 @@ * 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. + * + * The allocation strategy tries to save time and memory by avoiding needless + * copies. Instead of actually splitting the inputs into separate strings, we + * allocate cdline_t objects, each of which represents a line in the original + * object or in the output. We use memarea_t allocators to manage the + * temporary memory we use when generating or applying diffs. **/ #define CONSDIFF_PRIVATE #include "or.h" #include "consdiff.h" +#include "memarea.h" #include "routerparse.h" static const char* ns_diff_version = "network-status-diff-version 1"; @@ -41,6 +48,36 @@ static const char* hash_token = "hash"; static char *consensus_join_lines(const smartlist_t *inp); +/** Return true iff a and b have the same contents. */ +STATIC int +lines_eq(const cdline_t *a, const cdline_t *b) +{ + return a->len == b->len && fast_memeq(a->s, b->s, a->len); +} + +/** Return true iff a has the same contents as the nul-terminated string b. */ +STATIC int +line_str_eq(const cdline_t *a, const char *b) +{ + const size_t len = strlen(b); + tor_assert(len <= UINT32_MAX); + cdline_t bline = { b, (uint32_t)len }; + return lines_eq(a, &bline); +} + +/** Add a cdline_t to lst holding as its contents the nul-terminated + * string s. Use the provided memory area for storage. */ +STATIC void +smartlist_add_linecpy(smartlist_t *lst, memarea_t *area, const char *s) +{ + size_t len = strlen(s); + const char *ss = memarea_memdup(area, s, len); + cdline_t *line = memarea_alloc(area, sizeof(cdline_t)); + line->s = ss; + line->len = (uint32_t)len; + smartlist_add(lst, line); +} + /** Compute the digest of cons, and store the result in * digest_out. Return 0 on success, -1 on failure. */ /* This is a separate, mockable function so that we can override it when @@ -114,7 +151,7 @@ lcs_lengths(const smartlist_slice_t *slice1, const smartlist_slice_t *slice2, for (int i = 0; i < slice1->len; ++i, si+=direction) { - const char *line1 = smartlist_get(slice1->list, si); + const cdline_t *line1 = smartlist_get(slice1->list, si); /* Store the last results. */ memcpy(prev, result, a_size); @@ -125,8 +162,8 @@ lcs_lengths(const smartlist_slice_t *slice1, const smartlist_slice_t *slice2, for (int j = 0; j < slice2->len; ++j, sj+=direction) { - const char *line2 = smartlist_get(slice2->list, sj); - if (!strcmp(line1, line2)) { + const cdline_t *line2 = smartlist_get(slice2->list, sj); + if (lines_eq(line1, line2)) { /* If the lines are equal, the lcs is one line longer. */ result[j + 1] = prev[j] + 1; } else { @@ -146,9 +183,9 @@ 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)) { + const cdline_t *line1 = smartlist_get(slice1->list, slice1->offset); + const cdline_t *line2 = smartlist_get(slice2->list, slice2->offset); + if (!lines_eq(line1, line2)) { break; } slice1->offset++; slice1->len--; @@ -159,9 +196,9 @@ trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2) 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)) { + const cdline_t *line1 = smartlist_get(slice1->list, i1); + const cdline_t *line2 = smartlist_get(slice2->list, i2); + if (!lines_eq(line1, line2)) { break; } i1--; @@ -171,15 +208,17 @@ trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2) } } -/** Like smartlist_string_pos, but limited to the bounds of the slice. +/** Like smartlist_string_pos, but uses a cdline_t, and is restricted to the + * bounds of the slice. */ STATIC int -smartlist_slice_string_pos(const smartlist_slice_t *slice, const char *string) +smartlist_slice_string_pos(const smartlist_slice_t *slice, + const cdline_t *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)) { + const cdline_t *el = smartlist_get(slice->list, i); + if (lines_eq(el, string)) { return i; } } @@ -199,7 +238,7 @@ set_changed(bitarray_t *changed1, bitarray_t *changed2, tor_assert(slice1->len == 0 || slice1->len == 1); if (slice1->len == 1) { - const char *line_common = smartlist_get(slice1->list, slice1->offset); + const cdline_t *line_common = smartlist_get(slice1->list, slice1->offset); toskip = smartlist_slice_string_pos(slice2, line_common); if (toskip == -1) { bitarray_set(changed1, slice1->offset); @@ -318,16 +357,20 @@ static const uint8_t base64_compare_table[256] = { /** Helper: Get the identity hash from a router line, assuming that the line * at least appears to be a router line and thus starts with "r ". + * + * If an identity hash is found, store it (without decoding it) in + * hash_out, and return 0. On failure, return -1. */ -STATIC const char * -get_id_hash(const char *r_line) +STATIC int +get_id_hash(const cdline_t *line, cdline_t *hash_out) { - r_line += strlen("r "); + if (line->len < 2) + return -1; /* Skip the router name. */ - const char *hash = strchr(r_line, ' '); + const char *hash = memchr(line->s + 2, ' ', line->len - 2); if (!hash) { - return NULL; + return -1; } hash++; @@ -335,28 +378,34 @@ get_id_hash(const char *r_line) /* 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) { + while (base64_compare_table[*((unsigned char*)hash_end)] != X && + hash_end < line->s + line->len) { hash_end++; } /* Empty hash. */ if (hash_end == hash) { - return NULL; + return -1; } - return hash; + hash_out->s = hash; + /* Always true because lines are limited to this length */ + tor_assert(hash_end - hash <= UINT32_MAX); + hash_out->len = (uint32_t)(hash_end - hash); + + return 0; } /** 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) +is_valid_router_entry(const cdline_t *line) { - if (strcmpstart(line, "r ") != 0) { + if (line->len < 2 || fast_memneq(line->s, "r ", 2)) return 0; - } - return (get_id_hash(line) != NULL); + cdline_t tmp; + return (get_id_hash(line, &tmp) == 0); } /** Helper: Find the next router line starting at the current position. @@ -374,7 +423,7 @@ next_router(const smartlist_t *cons, int cur) return len; } - const char *line = smartlist_get(cons, cur); + const cdline_t *line = smartlist_get(cons, cur); while (!is_valid_router_entry(line)) { if (++cur >= len) { return len; @@ -384,26 +433,28 @@ next_router(const smartlist_t *cons, int cur) return cur; } -/** Helper: compare two base64-encoded identity hashes which may be of +/** 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) +base64cmp(const cdline_t *hash1, const cdline_t *hash2) { /* NULL is always lower, useful for last_hash which starts at NULL. */ - if (!hash1 && !hash2) { + if (!hash1->s && !hash2->s) { return 0; } - if (!hash1) { + if (!hash1->s) { return -1; } - if (!hash2) { + if (!hash2->s) { 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; + const unsigned char *a = (unsigned char*)hash1->s; + const unsigned char *b = (unsigned char*)hash2->s; + const unsigned char *a_end = a + hash1->len; + const unsigned char *b_end = b + hash2->len; while (1) { uint8_t av = base64_compare_table[*a]; uint8_t bv = base64_compare_table[*b]; @@ -427,6 +478,15 @@ base64cmp(const char *hash1, const char *hash2) } else { a++; b++; + if (a == a_end) { + if (b == b_end) { + return 0; + } else { + return -1; + } + } else if (b == b_end) { + return 1; + } } } } @@ -436,6 +496,9 @@ base64cmp(const char *hash1, const char *hash2) * happen if any lines the script had to add matched "." or if the routers * were not properly ordered. * + * All cdline_t objects in the resulting object are either references to lines + * in one of the inputs, or are newly allocated lines in the provided memarea. + * * 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: @@ -449,7 +512,8 @@ base64cmp(const char *hash1, const char *hash2) * calc_changes(cons1_sl, cons2_sl, changed1, changed2); */ STATIC smartlist_t * -gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) +gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2, + memarea_t *area) { int len1 = smartlist_len(cons1); int len2 = smartlist_len(cons2); @@ -463,12 +527,9 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) 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; + cdline_t hash1 = { NULL, 0 }, hash2 = { NULL, 0 }; + cdline_t last_hash1 = { NULL, 0 }, last_hash2 = { NULL, 0 }; /* 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 @@ -485,9 +546,9 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) 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) { + memcpy(&last_hash1, &hash1, sizeof(cdline_t)); + if (get_id_hash(smartlist_get(cons1, i1), &hash1) < 0 || + 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."); @@ -499,9 +560,9 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) 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) { + memcpy(&last_hash2, &hash2, sizeof(cdline_t)); + if (get_id_hash(smartlist_get(cons2, i2), &hash2) < 0 || + 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."); @@ -525,7 +586,7 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) * consensus has already reached the end, both are extended to their * respecting ends since we are done. */ - int cmp = base64cmp(hash1, hash2); + int cmp = base64cmp(&hash1, &hash2); while (cmp != 0) { if (i1 < len1 && cmp < 0) { i1 = next_router(cons1, i1); @@ -536,9 +597,9 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) i2 = len2; break; } - last_hash1 = hash1; - hash1 = get_id_hash(smartlist_get(cons1, i1)); - if (base64cmp(hash1, last_hash1) <= 0) { + memcpy(&last_hash1, &hash1, sizeof(cdline_t)); + if (get_id_hash(smartlist_get(cons1, i1), &hash1) < 0 || + 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."); @@ -553,9 +614,9 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) i1 = len1; break; } - last_hash2 = hash2; - hash2 = get_id_hash(smartlist_get(cons2, i2)); - if (base64cmp(hash2, last_hash2) <= 0) { + memcpy(&last_hash2, &hash2, sizeof(cdline_t)); + if (get_id_hash(smartlist_get(cons2, i2), &hash2) < 0 || + 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."); @@ -566,7 +627,7 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) i2 = len2; break; } - cmp = base64cmp(hash1, hash2); + cmp = base64cmp(&hash1, &hash2); } } @@ -595,6 +656,7 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) * each chunk of changes. */ i1=len1-1, i2=len2-1; + char buf[128]; while (i1 > 0 || i2 > 0) { int start1x, start2x, end1, end2, added, deleted; @@ -626,31 +688,36 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) if (added == 0) { if (deleted == 1) { - smartlist_add_asprintf(result, "%id", start1x+1); + tor_snprintf(buf, sizeof(buf), "%id", start1x+1); + smartlist_add_linecpy(result, area, buf); } else { - smartlist_add_asprintf(result, "%i,%id", start1x+1, start1x+deleted); + tor_snprintf(buf, sizeof(buf), "%i,%id", start1x+1, start1x+deleted); + smartlist_add_linecpy(result, area, buf); } } else { int i; if (deleted == 0) { - smartlist_add_asprintf(result, "%ia", start1x); + tor_snprintf(buf, sizeof(buf), "%ia", start1x); + smartlist_add_linecpy(result, area, buf); } else if (deleted == 1) { - smartlist_add_asprintf(result, "%ic", start1x+1); + tor_snprintf(buf, sizeof(buf), "%ic", start1x+1); + smartlist_add_linecpy(result, area, buf); } else { - smartlist_add_asprintf(result, "%i,%ic", start1x+1, start1x+deleted); + tor_snprintf(buf, sizeof(buf), "%i,%ic", start1x+1, start1x+deleted); + smartlist_add_linecpy(result, area, buf); } for (i = start2x; i <= end2; ++i) { - const char *line = smartlist_get(cons2, i); - if (!strcmp(line, ".")) { + cdline_t *line = smartlist_get(cons2, i); + if (line_str_eq(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(result, line); } - smartlist_add_asprintf(result, "."); + smartlist_add_linecpy(result, area, "."); } } @@ -664,7 +731,6 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) bitarray_free(changed1); bitarray_free(changed2); - SMARTLIST_FOREACH(result, char*, line, tor_free(line)); smartlist_free(result); return NULL; @@ -673,6 +739,9 @@ gen_ed_diff(const smartlist_t *cons1, const smartlist_t *cons2) /** Apply the ed diff, starting at diff_starting_line, 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. + * + * All cdline_t objects in the resulting object are references to lines + * in one of the inputs; nothing is copied. */ STATIC smartlist_t * apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, @@ -683,9 +752,17 @@ apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, smartlist_t *cons2 = smartlist_new(); for (int i=diff_starting_line; ilen > sizeof(diff_line) - 1) { + log_warn(LD_CONSDIFF, "Could not apply consensus diff because " + "an ed command was far too long"); + goto error_cleanup; + } + memcpy(diff_line, diff_cdline->s, diff_cdline->len); + diff_line[diff_cdline->len] = 0; int start = (int)strtol(diff_line, &endptr1, 10); int end; if (endptr1 == diff_line) { @@ -748,8 +825,8 @@ apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, /* Add unchanged lines. */ for (; j && j > end; --j) { - const char *cons_line = smartlist_get(cons1, j-1); - smartlist_add(cons2, tor_strdup(cons_line)); + cdline_t *cons_line = smartlist_get(cons1, j-1); + smartlist_add(cons2, cons_line); } /* Ignore removed lines. */ @@ -767,7 +844,7 @@ apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, i++; /* Skip the line with the range and command. */ while (i < diff_len) { - if (!strcmp(smartlist_get(diff, i), ".")) { + if (line_str_eq(smartlist_get(diff, i), ".")) { break; } if (++i == diff_len) { @@ -787,16 +864,16 @@ apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, } while (added_i > added_end) { - const char *added_line = smartlist_get(diff, added_i--); - smartlist_add(cons2, tor_strdup(added_line)); + cdline_t *added_line = smartlist_get(diff, added_i--); + smartlist_add(cons2, 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)); + cdline_t *cons_line = smartlist_get(cons1, j-1); + smartlist_add(cons2, cons_line); } /* Reverse the whole thing since we did it from the end. */ @@ -805,7 +882,6 @@ apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, error_cleanup: - SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); smartlist_free(cons2); return NULL; @@ -817,11 +893,13 @@ apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, * up to the caller to free their resources. */ smartlist_t * -consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, +consdiff_gen_diff(const smartlist_t *cons1, + const smartlist_t *cons2, const consensus_digest_t *digests1, - const consensus_digest_t *digests2) + const consensus_digest_t *digests2, + memarea_t *area) { - smartlist_t *ed_diff = gen_ed_diff(cons1, cons2); + smartlist_t *ed_diff = gen_ed_diff(cons1, cons2, area); /* ed diff could not be generated - reason already logged by gen_ed_diff. */ if (!ed_diff) { goto error_cleanup; @@ -838,8 +916,18 @@ consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, /* LCOV_EXCL_STOP */ } - int cons2_eq = smartlist_strings_eq(cons2, ed_cons2); - SMARTLIST_FOREACH(ed_cons2, char*, line, tor_free(line)); + int cons2_eq = 1; + if (smartlist_len(cons2) == smartlist_len(ed_cons2)) { + SMARTLIST_FOREACH_BEGIN(cons2, const cdline_t *, line1) { + const cdline_t *line2 = smartlist_get(ed_cons2, line1_sl_idx); + if (! lines_eq(line1, line2) ) { + cons2_eq = 0; + break; + } + } SMARTLIST_FOREACH_END(line1); + } else { + cons2_eq = 0; + } smartlist_free(ed_cons2); if (!cons2_eq) { /* LCOV_EXCL_START -- impossible if diff generation is correct. */ @@ -858,10 +946,13 @@ consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, (const char*)digests2->sha3_256, DIGEST256_LEN); /* Create the resulting consensus diff. */ + char buf[160]; smartlist_t *result = smartlist_new(); - smartlist_add_asprintf(result, "%s", ns_diff_version); - smartlist_add_asprintf(result, "%s %s %s", hash_token, + tor_snprintf(buf, sizeof(buf), "%s", ns_diff_version); + smartlist_add_linecpy(result, area, buf); + tor_snprintf(buf, sizeof(buf), "%s %s %s", hash_token, cons1_hash_hex, cons2_hash_hex); + smartlist_add_linecpy(result, area, buf); smartlist_add_all(result, ed_diff); smartlist_free(ed_diff); return result; @@ -870,7 +961,6 @@ consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, if (ed_diff) { /* LCOV_EXCL_START -- ed_diff is NULL except in unreachable cases above */ - SMARTLIST_FOREACH(ed_diff, char *, cp, tor_free(cp)); smartlist_free(ed_diff); /* LCOV_EXCL_STOP */ } @@ -888,7 +978,7 @@ consdiff_get_digests(const smartlist_t *diff, char *digest2_out) { smartlist_t *hash_words = NULL; - const char *format; + const cdline_t *format; char cons1_hash[DIGEST256_LEN], cons2_hash[DIGEST256_LEN]; char *cons1_hash_hex, *cons2_hash_hex; if (smartlist_len(diff) < 2) { @@ -898,14 +988,19 @@ consdiff_get_digests(const smartlist_t *diff, /* Check that it's the format and version we know. */ format = smartlist_get(diff, 0); - if (strcmp(format, ns_diff_version)) { + if (!line_str_eq(format, ns_diff_version)) { log_warn(LD_CONSDIFF, "The provided consensus diff format is not known."); goto error_cleanup; } /* Grab the base16 digests. */ hash_words = smartlist_new(); - smartlist_split_string(hash_words, smartlist_get(diff, 1), " ", 0, 0); + { + const cdline_t *line2 = smartlist_get(diff, 1); + char *h = tor_memdup_nulterm(line2->s, line2->len); + smartlist_split_string(hash_words, h, " ", 0, 0); + tor_free(h); + } /* There have to be three words, the first of which must be hash_token. */ if (smartlist_len(hash_words) != 3 || @@ -1038,7 +1133,6 @@ consdiff_apply_diff(const smartlist_t *cons1, done: if (cons2) { - SMARTLIST_FOREACH(cons2, char *, cp, tor_free(cp)); smartlist_free(cons2); } @@ -1046,34 +1140,40 @@ consdiff_apply_diff(const smartlist_t *cons1, } /** - * Helper: For every NL-terminated line in s, add that line - * (without trailing newline) to out. Return -1 if there are any - * non-NL terminated lines; 0 otherwise. - * - * Modifies s in place: don't do anything with s after you're - * done here, besides freeing it. + * Helper: For every NL-terminated line in s, add a cdline referring to + * that line (without trailing newline) to out. Return -1 if there are + * any non-NL terminated lines; 0 otherwise. * * Unlike tor_split_lines, this function avoids ambiguity on its * handling of a final line that isn't NL-terminated. + * + * All cdline_t objects are allocated in the provided memarea. Strings + * are not copied: if s changes or becomes invalid, then all + * generated cdlines will become invalid. */ -static int -consensus_split_lines(smartlist_t *out, char *s) +STATIC int +consensus_split_lines(smartlist_t *out, const char *s, memarea_t *area) { - /* XXXX If we used string slices, we could avoid a bunch of copies here. */ while (*s) { - char *eol = strchr(s, '\n'); + const char *eol = strchr(s, '\n'); if (!eol) { /* File doesn't end with newline. */ return -1; } - *eol = 0; - smartlist_add(out, s); + if (eol - s > UINT32_MAX) { + /* Line is far too long. */ + return -1; + } + cdline_t *line = memarea_alloc(area, sizeof(cdline_t)); + line->s = s; + line->len = (uint32_t)(eol - s); + smartlist_add(out, line); s = eol+1; } return 0; } -/** Given a list of lines, return a newly allocated string containing +/** Given a list of cdline_t, return a newly allocated string containing * all of the lines, terminated with NL, concatenated. * * Unlike smartlist_join_strings(), avoids lossy operations on empty @@ -1082,16 +1182,15 @@ static char * consensus_join_lines(const smartlist_t *inp) { size_t n = 0; - SMARTLIST_FOREACH(inp, const char *, cp, n += strlen(cp) + 1); + SMARTLIST_FOREACH(inp, const cdline_t *, cdline, n += cdline->len + 1); n += 1; char *result = tor_malloc(n); char *out = result; - SMARTLIST_FOREACH_BEGIN(inp, const char *, cp) { - size_t len = strlen(cp); - memcpy(out, cp, len); - out += len; + SMARTLIST_FOREACH_BEGIN(inp, const cdline_t *, cdline) { + memcpy(out, cdline->s, cdline->len); + out += cdline->len; *out++ = '\n'; - } SMARTLIST_FOREACH_END(cp); + } SMARTLIST_FOREACH_END(cdline); *out++ = '\0'; tor_assert(out == result+n); return result; @@ -1114,28 +1213,26 @@ consensus_diff_generate(const char *cons1, if (BUG(r1 < 0 || r2 < 0)) return NULL; // LCOV_EXCL_LINE - char *cons1_copy = tor_strdup(cons1); - char *cons2_copy = tor_strdup(cons2); + memarea_t *area = memarea_new(); lines1 = smartlist_new(); lines2 = smartlist_new(); - if (consensus_split_lines(lines1, cons1_copy) < 0) + if (consensus_split_lines(lines1, cons1, area) < 0) goto done; - if (consensus_split_lines(lines2, cons2_copy) < 0) + if (consensus_split_lines(lines2, cons2, area) < 0) goto done; - result_lines = consdiff_gen_diff(lines1, lines2, &d1, &d2); + result_lines = consdiff_gen_diff(lines1, lines2, &d1, &d2, area); done: - smartlist_free(lines1); - smartlist_free(lines2); - tor_free(cons1_copy); - tor_free(cons2_copy); - if (result_lines) { result = consensus_join_lines(result_lines); - SMARTLIST_FOREACH(result_lines, char *, cp, tor_free(cp)); smartlist_free(result_lines); } + + memarea_drop_all(area); + smartlist_free(lines1); + smartlist_free(lines2); + return result; } @@ -1150,18 +1247,17 @@ consensus_diff_apply(const char *consensus, smartlist_t *lines1 = NULL, *lines2 = NULL; int r1; char *result = NULL; + memarea_t *area = memarea_new(); r1 = consensus_compute_digest(consensus, &d1); if (BUG(r1 < 0)) return NULL; // LCOV_EXCL_LINE - char *cons_copy = tor_strdup(consensus); - char *diff_copy = tor_strdup(diff); lines1 = smartlist_new(); lines2 = smartlist_new(); - if (consensus_split_lines(lines1, cons_copy) < 0) + if (consensus_split_lines(lines1, consensus, area) < 0) goto done; - if (consensus_split_lines(lines2, diff_copy) < 0) + if (consensus_split_lines(lines2, diff, area) < 0) goto done; result = consdiff_apply_diff(lines1, lines2, &d1); @@ -1169,8 +1265,7 @@ consensus_diff_apply(const char *consensus, done: smartlist_free(lines1); smartlist_free(lines2); - tor_free(cons_copy); - tor_free(diff_copy); + memarea_drop_all(area); return result; } diff --git a/src/or/consdiff.h b/src/or/consdiff.h index 7797067f32..e9d175136e 100644 --- a/src/or/consdiff.h +++ b/src/or/consdiff.h @@ -13,6 +13,16 @@ char *consensus_diff_apply(const char *consensus, const char *diff); #ifdef CONSDIFF_PRIVATE +struct memarea_t; + +/** Line type used for constructing consensus diffs. Each of these lines + * refers to a chunk of memory allocated elsewhere, and is not necessarily + * NUL-terminated: this helps us avoid copies and save memory. */ +typedef struct cdline_t { + const char *s; + uint32_t len; +} cdline_t; + typedef struct consensus_digest_t { uint8_t sha3_256[DIGEST256_LEN]; } consensus_digest_t; @@ -20,7 +30,8 @@ typedef struct consensus_digest_t { STATIC smartlist_t *consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, const consensus_digest_t *digests1, - const consensus_digest_t *digests2); + const consensus_digest_t *digests2, + struct memarea_t *area); STATIC char *consdiff_apply_diff(const smartlist_t *cons1, const smartlist_t *diff, const consensus_digest_t *digests1); @@ -41,7 +52,8 @@ typedef struct smartlist_slice_t { int len; } smartlist_slice_t; STATIC smartlist_t *gen_ed_diff(const smartlist_t *cons1, - const smartlist_t *cons2); + const smartlist_t *cons2, + struct memarea_t *area); STATIC smartlist_t *apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, int start_line); @@ -54,14 +66,20 @@ STATIC int *lcs_lengths(const smartlist_slice_t *slice1, const smartlist_slice_t *slice2, int direction); STATIC void trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2); -STATIC int base64cmp(const char *hash1, const char *hash2); -STATIC const char *get_id_hash(const char *r_line); -STATIC int is_valid_router_entry(const char *line); +STATIC int base64cmp(const cdline_t *hash1, const cdline_t *hash2); +STATIC int get_id_hash(const cdline_t *line, cdline_t *hash_out); +STATIC int is_valid_router_entry(const cdline_t *line); STATIC int smartlist_slice_string_pos(const smartlist_slice_t *slice, - const char *string); + const cdline_t *string); STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, const smartlist_slice_t *slice1, const smartlist_slice_t *slice2); +STATIC int consensus_split_lines(smartlist_t *out, const char *s, + struct memarea_t *area); +STATIC void smartlist_add_linecpy(smartlist_t *lst, struct memarea_t *area, + const char *s); +STATIC int lines_eq(const cdline_t *a, const cdline_t *b); +STATIC int line_str_eq(const cdline_t *a, const char *b); MOCK_DECL(STATIC int, consensus_compute_digest,(const char *cons, diff --git a/src/test/bench.c b/src/test/bench.c index 99bc686f30..ee39f0b582 100644 --- a/src/test/bench.c +++ b/src/test/bench.c @@ -28,6 +28,7 @@ const char tor_git_revision[] = ""; #include "crypto_curve25519.h" #include "onion_ntor.h" #include "crypto_ed25519.h" +#include "consdiff.h" #if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_PROCESS_CPUTIME_ID) static uint64_t nanostart; @@ -674,6 +675,27 @@ main(int argc, const char **argv) tor_threads_init(); + if (argc == 4 && !strcmp(argv[1], "diff")) { + init_logging(1); + const int N = 200; + char *f1 = read_file_to_str(argv[2], RFTS_BIN, NULL); + char *f2 = read_file_to_str(argv[3], RFTS_BIN, NULL); + if (! f1 || ! f2) { + perror("X"); + return 1; + } + for (i = 0; i < N; ++i) { + char *diff = consensus_diff_generate(f1, f2); + tor_free(diff); + } + char *diff = consensus_diff_generate(f1, f2); + printf("%s", diff); + tor_free(f1); + tor_free(f2); + tor_free(diff); + return 0; + } + for (i = 1; i < argc; ++i) { if (!strcmp(argv[i], "--list")) { list = 1; diff --git a/src/test/test_consdiff.c b/src/test/test_consdiff.c index 12213aab64..1b4e2ad3c1 100644 --- a/src/test/test_consdiff.c +++ b/src/test/test_consdiff.c @@ -8,8 +8,12 @@ #include "test.h" #include "consdiff.h" +#include "memarea.h" #include "log_test_helpers.h" +#define tt_str_eq_line(a,b) \ + tt_assert(line_str_eq((b),(a))) + static void test_consdiff_smartlist_slice(void *arg) { @@ -49,20 +53,23 @@ test_consdiff_smartlist_slice_string_pos(void *arg) { smartlist_t *sl = smartlist_new(); smartlist_slice_t *sls; + memarea_t *area = memarea_new(); /* Create a regular smartlist. */ (void)arg; - smartlist_split_string(sl, "a:d:c:a:b", ":", 0, 0); + consensus_split_lines(sl, "a\nd\nc\na\nb\n", area); /* 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")); + cdline_t a_line = { "a", 1 }; + tt_int_op(3, OP_EQ, smartlist_slice_string_pos(sls, &a_line)); + cdline_t d_line = { "d", 1 }; + tt_int_op(-1, OP_EQ, smartlist_slice_string_pos(sls, &d_line)); done: tor_free(sls); - if (sl) SMARTLIST_FOREACH(sl, char*, line, tor_free(line)); smartlist_free(sl); + memarea_drop_all(area); } static void @@ -72,14 +79,15 @@ test_consdiff_lcs_lengths(void *arg) smartlist_t *sl2 = smartlist_new(); smartlist_slice_t *sls1, *sls2; int *lengths1, *lengths2; + memarea_t *area = memarea_new(); /* 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); + consensus_split_lines(sl1, "a\nb\nc\nd\ne\n", area); + consensus_split_lines(sl2, "a\nc\nd\ni\ne\n", area); sls1 = smartlist_slice(sl1, 0, -1); sls2 = smartlist_slice(sl2, 0, -1); @@ -94,10 +102,9 @@ test_consdiff_lcs_lengths(void *arg) 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); + memarea_drop_all(area); } static void @@ -108,13 +115,13 @@ test_consdiff_trim_slices(void *arg) smartlist_t *sl3 = smartlist_new(); smartlist_t *sl4 = smartlist_new(); smartlist_slice_t *sls1, *sls2, *sls3, *sls4; + memarea_t *area = memarea_new(); (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); - + consensus_split_lines(sl1, "a\nb\nb\nb\nd\n", area); + consensus_split_lines(sl2, "a\nc\nc\nc\nd\n", area); + consensus_split_lines(sl3, "a\nb\nb\nb\na\n", area); + consensus_split_lines(sl4, "c\nb\nb\nb\nc\n", area); sls1 = smartlist_slice(sl1, 0, -1); sls2 = smartlist_slice(sl2, 0, -1); sls3 = smartlist_slice(sl3, 0, -1); @@ -139,14 +146,11 @@ test_consdiff_trim_slices(void *arg) 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); + memarea_drop_all(area); } static void @@ -157,10 +161,11 @@ test_consdiff_set_changed(void *arg) bitarray_t *changed1 = bitarray_init_zero(4); bitarray_t *changed2 = bitarray_init_zero(4); smartlist_slice_t *sls1, *sls2; + memarea_t *area = memarea_new(); (void)arg; - smartlist_split_string(sl1, "a:b:a:a", ":", 0, 0); - smartlist_split_string(sl2, "a:a:a:a", ":", 0, 0); + consensus_split_lines(sl1, "a\nb\na\na\n", area); + consensus_split_lines(sl2, "a\na\na\na\n", area); /* Length of sls1 is 0. */ sls1 = smartlist_slice(sl1, 0, 0); @@ -216,12 +221,11 @@ test_consdiff_set_changed(void *arg) 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); + memarea_drop_all(area); } static void @@ -232,10 +236,11 @@ test_consdiff_calc_changes(void *arg) smartlist_slice_t *sls1, *sls2; bitarray_t *changed1 = bitarray_init_zero(4); bitarray_t *changed2 = bitarray_init_zero(4); + memarea_t *area = memarea_new(); (void)arg; - smartlist_split_string(sl1, "a:a:a:a", ":", 0, 0); - smartlist_split_string(sl2, "a:a:a:a", ":", 0, 0); + consensus_split_lines(sl1, "a\na\na\na\n", area); + consensus_split_lines(sl2, "a\na\na\na\n", area); sls1 = smartlist_slice(sl1, 0, -1); sls2 = smartlist_slice(sl2, 0, -1); @@ -252,9 +257,8 @@ test_consdiff_calc_changes(void *arg) 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); + consensus_split_lines(sl2, "a\nb\na\nb\n", area); tor_free(sls1); tor_free(sls2); sls1 = smartlist_slice(sl1, 0, -1); @@ -276,9 +280,8 @@ test_consdiff_calc_changes(void *arg) 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); + consensus_split_lines(sl2, "b\nb\nb\nb\n", area); tor_free(sls1); tor_free(sls2); sls1 = smartlist_slice(sl1, 0, -1); @@ -299,27 +302,32 @@ test_consdiff_calc_changes(void *arg) 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); + memarea_drop_all(area); } 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")); + + cdline_t line1 = { "r name", 6 }; + cdline_t line2 = { "r name _hash_isnt_base64 etc", 28 }; + cdline_t line3 = { "r name hash+valid+base64 etc", 28 }; + cdline_t tmp; + + /* No hash. */ + tt_int_op(-1, OP_EQ, get_id_hash(&line1, &tmp)); /* The hash contains characters that are not base64. */ - tt_ptr_op(NULL, OP_EQ, get_id_hash( "r name _hash_isnt_base64 etc")); + tt_int_op(-1, OP_EQ, get_id_hash(&line2, &tmp)); - line = "r name hash+valid+base64 etc"; - e_hash = line+7; - tt_ptr_op(e_hash, OP_EQ, get_id_hash(line)); + /* valid hash. */ + tt_int_op(0, OP_EQ, get_id_hash(&line3, &tmp)); + tt_ptr_op(tmp.s, OP_EQ, line3.s + 7); + tt_uint_op(tmp.len, OP_EQ, line3.len - 11); done: ; @@ -330,14 +338,18 @@ 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")); + cdline_t line0 = { "foo", 3 }; + tt_int_op(0, OP_EQ, is_valid_router_entry(&line0)); /* 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")); + cdline_t line1 = { "r name", 6 }; + cdline_t line2 = { "r name _hash_isnt_base64 etc", 28 }; + cdline_t line3 = { "r name hash+valid+base64 etc", 28 }; + tt_int_op(0, OP_EQ, is_valid_router_entry(&line1)); + tt_int_op(0, OP_EQ, is_valid_router_entry(&line2)); + tt_int_op(1, OP_EQ, is_valid_router_entry(&line3)); done: ; @@ -347,15 +359,16 @@ static void test_consdiff_next_router(void *arg) { smartlist_t *sl = smartlist_new(); + memarea_t *area = memarea_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"); + smartlist_add_linecpy(sl, area, "foo"); + smartlist_add_linecpy(sl, area, + "r name hash+longer+than+27+chars+and+valid+base64 etc"); + smartlist_add_linecpy(sl, area, "foo"); + smartlist_add_linecpy(sl, area, "foo"); + smartlist_add_linecpy(sl, area, + "r name hash+longer+than+27+chars+and+valid+base64 etc"); + smartlist_add_linecpy(sl, area, "foo"); /* Not currently on a router entry line, finding the next one. */ tt_int_op(1, OP_EQ, next_router(sl, 0)); @@ -370,6 +383,15 @@ test_consdiff_next_router(void *arg) done: smartlist_free(sl); + memarea_drop_all(area); +} + +static int +base64cmp_wrapper(const char *a, const char *b) +{ + cdline_t aa = { a, a ? (uint32_t) strlen(a) : 0 }; + cdline_t bb = { b, b ? (uint32_t) strlen(b) : 0 }; + return base64cmp(&aa, &bb); } static void @@ -377,34 +399,34 @@ 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)); + tt_int_op(0, OP_EQ, base64cmp_wrapper(NULL, NULL)); + tt_int_op(-1, OP_EQ, base64cmp_wrapper(NULL, "foo")); + tt_int_op(1, OP_EQ, base64cmp_wrapper("bar", NULL)); /* Nil base64 values. */ - tt_int_op(0, OP_EQ, base64cmp("", "")); - tt_int_op(0, OP_EQ, base64cmp("_", "&")); + tt_int_op(0, OP_EQ, base64cmp_wrapper("", "")); + tt_int_op(0, OP_EQ, base64cmp_wrapper("_", "&")); /* Exact same valid strings. */ - tt_int_op(0, OP_EQ, base64cmp("abcABC/+", "abcABC/+")); + tt_int_op(0, OP_EQ, base64cmp_wrapper("abcABC/+", "abcABC/+")); /* Both end with an invalid base64 char other than '\0'. */ - tt_int_op(0, OP_EQ, base64cmp("abcABC/+ ", "abcABC/+ ")); + tt_int_op(0, OP_EQ, base64cmp_wrapper("abcABC/+ ", "abcABC/+ ")); /* Only one ends with an invalid base64 char other than '\0'. */ - tt_int_op(0, OP_EQ, base64cmp("abcABC/+ ", "abcABC/+")); + tt_int_op(-1, OP_EQ, base64cmp_wrapper("abcABC/+ ", "abcABC/+a")); /* 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, base64cmp_wrapper("/foo", "Afoo")); tt_int_op(1, OP_EQ, strcmp("Afoo", "0foo")); - tt_int_op(-1, OP_EQ, base64cmp("Afoo", "0foo")); + tt_int_op(-1, OP_EQ, base64cmp_wrapper("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")); + tt_int_op(1, OP_EQ, base64cmp_wrapper("afoo", "Afoo")); /* Different lengths */ - tt_int_op(-1, OP_EQ, base64cmp("afoo", "afooo")); - tt_int_op(1, OP_EQ, base64cmp("afooo", "afoo")); + tt_int_op(-1, OP_EQ, base64cmp_wrapper("afoo", "afooo")); + tt_int_op(1, OP_EQ, base64cmp_wrapper("afooo", "afoo")); done: ; @@ -415,8 +437,7 @@ test_consdiff_gen_ed_diff(void *arg) { smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; int i; - int free_cons_entries = 0;/* 1 if the cons1 and cons2 contents are - * heap-allocated */ + memarea_t *area = memarea_new(); setup_capture_of_logs(LOG_WARN); (void)arg; @@ -424,17 +445,17 @@ test_consdiff_gen_ed_diff(void *arg) 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_linecpy(cons1, area, "r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); + smartlist_add_linecpy(cons1, area, "foo"); + smartlist_add_linecpy(cons1, area, "r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc"); + smartlist_add_linecpy(cons1, area, "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"); + smartlist_add_linecpy(cons2, area, "r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc"); + smartlist_add_linecpy(cons2, area, "foo"); + smartlist_add_linecpy(cons2, area, "r name ccccccccccccccccccccccccccc etc"); + smartlist_add_linecpy(cons2, area, "bar"); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); tt_ptr_op(NULL, OP_EQ, diff); expect_single_log_msg_containing("Refusing to generate consensus diff " "because the base consensus doesn't have its router entries sorted " @@ -442,7 +463,7 @@ test_consdiff_gen_ed_diff(void *arg) /* Same, but now with the second consensus. */ mock_clean_saved_logs(); - diff = gen_ed_diff(cons2, cons1); + diff = gen_ed_diff(cons2, cons1, area); tt_ptr_op(NULL, OP_EQ, diff); expect_single_log_msg_containing("Refusing to generate consensus diff " "because the target consensus doesn't have its router entries sorted " @@ -451,17 +472,17 @@ test_consdiff_gen_ed_diff(void *arg) /* Same as the two above, but with the reversed thing immediately after a match. (The code handles this differently) */ smartlist_del(cons1, 0); - smartlist_add(cons1, (char*)"r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc"); + smartlist_add_linecpy(cons1, area, "r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc"); mock_clean_saved_logs(); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); tt_ptr_op(NULL, OP_EQ, diff); expect_single_log_msg_containing("Refusing to generate consensus diff " "because the base consensus doesn't have its router entries sorted " "properly."); mock_clean_saved_logs(); - diff = gen_ed_diff(cons2, cons1); + diff = gen_ed_diff(cons2, cons1, area); tt_ptr_op(NULL, OP_EQ, diff); expect_single_log_msg_containing("Refusing to generate consensus diff " "because the target consensus doesn't have its router entries sorted " @@ -470,13 +491,13 @@ test_consdiff_gen_ed_diff(void *arg) /* 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"); + smartlist_add_linecpy(cons1, area, "r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); + smartlist_add_linecpy(cons1, area, "foo"); + smartlist_add_linecpy(cons1, area, "r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc"); + smartlist_add_linecpy(cons1, area, "bar"); mock_clean_saved_logs(); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); tt_ptr_op(NULL, OP_EQ, diff); expect_single_log_msg_containing("Refusing to generate consensus diff " "because the base consensus doesn't have its router entries sorted " @@ -486,15 +507,15 @@ test_consdiff_gen_ed_diff(void *arg) smartlist_clear(cons1); smartlist_clear(cons2); - smartlist_add(cons1, (char*)"foo1"); - smartlist_add(cons1, (char*)"foo2"); + smartlist_add_linecpy(cons1, area, "foo1"); + smartlist_add_linecpy(cons1, area, "foo2"); - smartlist_add(cons2, (char*)"foo1"); - smartlist_add(cons2, (char*)"."); - smartlist_add(cons2, (char*)"foo2"); + smartlist_add_linecpy(cons2, area, "foo1"); + smartlist_add_linecpy(cons2, area, "."); + smartlist_add_linecpy(cons2, area, "foo2"); mock_clean_saved_logs(); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); tt_ptr_op(NULL, OP_EQ, diff); expect_single_log_msg_containing("Cannot generate consensus diff " "because one of the lines to be added is \".\"."); @@ -504,11 +525,12 @@ test_consdiff_gen_ed_diff(void *arg) 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"); + for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add_linecpy(cons1, area, "a"); + for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add_linecpy(cons1, area, "b"); mock_clean_saved_logs(); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); + tt_ptr_op(NULL, OP_EQ, diff); expect_single_log_msg_containing("Refusing to generate consensus diff " "because we found too few common router ids."); @@ -517,36 +539,35 @@ test_consdiff_gen_ed_diff(void *arg) 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_linecpy(cons1, area, "foo1"); + smartlist_add_linecpy(cons1, area, "."); + smartlist_add_linecpy(cons1, area, "."); + smartlist_add_linecpy(cons1, area, "foo2"); - smartlist_add(cons2, (char*)"foo1"); - smartlist_add(cons2, (char*)"."); - smartlist_add(cons2, (char*)"foo2"); + smartlist_add_linecpy(cons2, area, "foo1"); + smartlist_add_linecpy(cons2, area, "."); + smartlist_add_linecpy(cons2, area, "foo2"); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); 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); + diff = gen_ed_diff(cons1, cons2, area); tt_ptr_op(NULL, OP_NE, 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_linecpy(cons1, area, "foo"); + smartlist_add_linecpy(cons1, area, "bar"); - smartlist_add(cons2, (char*)"foo"); - smartlist_add(cons2, (char*)"bar"); + smartlist_add_linecpy(cons2, area, "foo"); + smartlist_add_linecpy(cons2, area, "bar"); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); tt_ptr_op(NULL, OP_NE, diff); tt_int_op(0, OP_EQ, smartlist_len(diff)); smartlist_free(diff); @@ -554,91 +575,84 @@ test_consdiff_gen_ed_diff(void *arg) /* Everything is deleted. */ smartlist_clear(cons2); - diff = gen_ed_diff(cons1, cons2); + diff = gen_ed_diff(cons1, cons2, area); 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)); + tt_str_eq_line("1,2d", smartlist_get(diff, 0)); - SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); smartlist_free(diff); /* Everything is added. */ - diff = gen_ed_diff(cons2, cons1); + diff = gen_ed_diff(cons2, cons1, area); 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)); + tt_str_eq_line("0a", smartlist_get(diff, 0)); + tt_str_eq_line("foo", smartlist_get(diff, 1)); + tt_str_eq_line("bar", smartlist_get(diff, 2)); + tt_str_eq_line(".", 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); + smartlist_add_linecpy(cons2, area, "foo2"); + smartlist_add_linecpy(cons2, area, "bar2"); + diff = gen_ed_diff(cons1, cons2, area); 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)); + tt_str_eq_line("1,2c", smartlist_get(diff, 0)); + tt_str_eq_line("foo2", smartlist_get(diff, 1)); + tt_str_eq_line("bar2", smartlist_get(diff, 2)); + tt_str_eq_line(".", 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); - free_cons_entries = 1; - diff = gen_ed_diff(cons1, cons2); + consensus_split_lines(cons1, "A\nB\nC\nD\nE\n", area); + consensus_split_lines(cons2, "A\nC\nO\nE\nU\n", area); + diff = gen_ed_diff(cons1, cons2, area); 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)); + tt_str_eq_line("5a", smartlist_get(diff, 0)); + tt_str_eq_line("U", smartlist_get(diff, 1)); + tt_str_eq_line(".", smartlist_get(diff, 2)); + tt_str_eq_line("4c", smartlist_get(diff, 3)); + tt_str_eq_line("O", smartlist_get(diff, 4)); + tt_str_eq_line(".", smartlist_get(diff, 5)); + tt_str_eq_line("2d", smartlist_get(diff, 6)); /* TODO: small real use-cases, i.e. consensuses. */ done: teardown_capture_of_logs(); - if (free_cons_entries) { - if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); - if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); - } smartlist_free(cons1); smartlist_free(cons2); - if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); smartlist_free(diff); + memarea_drop_all(area); } static void test_consdiff_apply_ed_diff(void *arg) { smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; + memarea_t *area = memarea_new(); (void)arg; cons1 = smartlist_new(); diff = smartlist_new(); setup_capture_of_logs(LOG_WARN); - smartlist_split_string(cons1, "A:B:C:D:E", ":", 0, 0); + consensus_split_lines(cons1, "A\nB\nC\nD\nE\n", area); /* Command without range. */ - smartlist_add(diff, (char*)"a"); + smartlist_add_linecpy(diff, area, "a"); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); smartlist_clear(diff); expect_single_log_msg_containing("an ed command was missing a line number"); /* Range without command. */ - smartlist_add(diff, (char*)"1"); + smartlist_add_linecpy(diff, area, "1"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -647,7 +661,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); /* Range without end. */ - smartlist_add(diff, (char*)"1,"); + smartlist_add_linecpy(diff, area, "1,"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -657,7 +671,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); /* Incoherent ranges. */ - smartlist_add(diff, (char*)"1,1"); + smartlist_add_linecpy(diff, area, "1,1"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -665,7 +679,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); - smartlist_add(diff, (char*)"3,2"); + smartlist_add_linecpy(diff, area, "3,2"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -674,8 +688,8 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); /* Script is not in reverse order. */ - smartlist_add(diff, (char*)"1d"); - smartlist_add(diff, (char*)"3d"); + smartlist_add_linecpy(diff, area, "1d"); + smartlist_add_linecpy(diff, area, "3d"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -684,7 +698,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); /* Script contains unrecognised commands longer than one char. */ - smartlist_add(diff, (char*)"1foo"); + smartlist_add_linecpy(diff, area, "1foo"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -694,7 +708,7 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); /* Script contains unrecognised commands. */ - smartlist_add(diff, (char*)"1e"); + smartlist_add_linecpy(diff, area, "1e"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -704,7 +718,7 @@ test_consdiff_apply_ed_diff(void *arg) /* Command that should be followed by at least one line and a ".", but * isn't. */ - smartlist_add(diff, (char*)"0a"); + smartlist_add_linecpy(diff, area, "0a"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -712,7 +726,7 @@ test_consdiff_apply_ed_diff(void *arg) "insert zero lines."); /* Now it is followed by a ".", but it inserts zero lines. */ - smartlist_add(diff, (char*)"."); + smartlist_add_linecpy(diff, area, "."); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -722,8 +736,8 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); /* Now it it inserts something, but has no terminator. */ - smartlist_add(diff, (char*)"0a"); - smartlist_add(diff, (char*)"hello"); + smartlist_add_linecpy(diff, area, "0a"); + smartlist_add_linecpy(diff, area, "hello"); mock_clean_saved_logs(); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_EQ, cons2); @@ -733,73 +747,65 @@ test_consdiff_apply_ed_diff(void *arg) smartlist_clear(diff); /* Test appending text, 'a'. */ - smartlist_split_string(diff, "3a:U:O:.:0a:V:.", ":", 0, 0); + consensus_split_lines(diff, "3a\nU\nO\n.\n0a\nV\n.\n", area); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(8, OP_EQ, smartlist_len(cons2)); - tt_str_op("V", OP_EQ, smartlist_get(cons2, 0)); - 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)); + tt_str_eq_line("V", smartlist_get(cons2, 0)); + tt_str_eq_line("A", smartlist_get(cons2, 1)); + tt_str_eq_line("B", smartlist_get(cons2, 2)); + tt_str_eq_line("C", smartlist_get(cons2, 3)); + tt_str_eq_line("U", smartlist_get(cons2, 4)); + tt_str_eq_line("O", smartlist_get(cons2, 5)); + tt_str_eq_line("D", smartlist_get(cons2, 6)); + tt_str_eq_line("E", smartlist_get(cons2, 7)); + 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); + consensus_split_lines(diff, "4d\n1,2d\n", area); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(2, OP_EQ, smartlist_len(cons2)); - tt_str_op("C", OP_EQ, smartlist_get(cons2, 0)); - tt_str_op("E", OP_EQ, smartlist_get(cons2, 1)); + tt_str_eq_line("C", smartlist_get(cons2, 0)); + tt_str_eq_line("E", 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); + consensus_split_lines(diff, "4c\nT\nX\n.\n1, 2c\nM\n.\n", area); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(5, OP_EQ, smartlist_len(cons2)); - tt_str_op("M", OP_EQ, smartlist_get(cons2, 0)); - 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)); + tt_str_eq_line("M", smartlist_get(cons2, 0)); + tt_str_eq_line("C", smartlist_get(cons2, 1)); + tt_str_eq_line("T", smartlist_get(cons2, 2)); + tt_str_eq_line("X", smartlist_get(cons2, 3)); + tt_str_eq_line("E", 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); + consensus_split_lines(diff, "4c\nT\nX\n.\n2d\n0a\nM\n.\n", area); cons2 = apply_ed_diff(cons1, diff, 0); tt_ptr_op(NULL, OP_NE, cons2); tt_int_op(6, OP_EQ, smartlist_len(cons2)); - tt_str_op("M", OP_EQ, smartlist_get(cons2, 0)); - 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)); + tt_str_eq_line("M", smartlist_get(cons2, 0)); + tt_str_eq_line("A", smartlist_get(cons2, 1)); + tt_str_eq_line("C", smartlist_get(cons2, 2)); + tt_str_eq_line("T", smartlist_get(cons2, 3)); + tt_str_eq_line("X", smartlist_get(cons2, 4)); + tt_str_eq_line("E", smartlist_get(cons2, 5)); done: teardown_capture_of_logs(); - if (cons1) SMARTLIST_FOREACH(cons1, char*, line, tor_free(line)); - if (cons2) SMARTLIST_FOREACH(cons2, char*, line, tor_free(line)); smartlist_free(cons1); smartlist_free(cons2); - if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); smartlist_free(diff); + memarea_drop_all(area); } static void @@ -808,6 +814,7 @@ test_consdiff_gen_diff(void *arg) char *cons1_str=NULL, *cons2_str=NULL; smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL; consensus_digest_t digests1, digests2; + memarea_t *area = memarea_new(); (void)arg; cons1 = smartlist_new(); cons2 = smartlist_new(); @@ -833,10 +840,10 @@ test_consdiff_gen_diff(void *arg) tt_int_op(0, OP_EQ, consensus_compute_digest(cons2_str, &digests2)); - tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); - tor_split_lines(cons2, cons2_str, (int)strlen(cons2_str)); + consensus_split_lines(cons1, cons1_str, area); + consensus_split_lines(cons2, cons2_str, area); - diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2); + diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2, area); tt_ptr_op(NULL, OP_EQ, diff); /* Check that the headers are done properly. */ @@ -850,20 +857,21 @@ test_consdiff_gen_diff(void *arg) tt_int_op(0, OP_EQ, consensus_compute_digest(cons1_str, &digests1)); smartlist_clear(cons1); - tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); - diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2); + consensus_split_lines(cons1, cons1_str, area); + diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2, area); 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 " + tt_assert(line_str_eq(smartlist_get(diff, 0), + "network-status-diff-version 1")); + tt_assert(line_str_eq(smartlist_get(diff, 1), "hash " "06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4 " - "7AFECEFA4599BA33D603653E3D2368F648DF4AC4723929B0F7CF39281596B0C1", - OP_EQ, smartlist_get(diff, 1)); - tt_str_op("3,4d", OP_EQ, smartlist_get(diff, 2)); - tt_str_op("1a", 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)); + "7AFECEFA4599BA33D603653E3D2368F648DF4AC4723929B0F7CF39281596B0C1")); + tt_assert(line_str_eq(smartlist_get(diff, 2), "3,4d")); + tt_assert(line_str_eq(smartlist_get(diff, 3), "1a")); + tt_assert(line_str_eq(smartlist_get(diff, 4), + "r name aaaaaaaaaaaaaaaaa etc")); + tt_assert(line_str_eq(smartlist_get(diff, 5), "foo")); + tt_assert(line_str_eq(smartlist_get(diff, 6), ".")); /* TODO: small real use-cases, i.e. consensuses. */ @@ -872,8 +880,8 @@ test_consdiff_gen_diff(void *arg) tor_free(cons2_str); smartlist_free(cons1); smartlist_free(cons2); - if (diff) SMARTLIST_FOREACH(diff, char*, line, tor_free(line)); smartlist_free(diff); + memarea_drop_all(area); } static void @@ -883,6 +891,7 @@ test_consdiff_apply_diff(void *arg) char *cons1_str=NULL, *cons2 = NULL; consensus_digest_t digests1; (void)arg; + memarea_t *area = memarea_new(); cons1 = smartlist_new(); diff = smartlist_new(); setup_capture_of_logs(LOG_INFO); @@ -895,7 +904,7 @@ test_consdiff_apply_diff(void *arg) ); tt_int_op(0, OP_EQ, consensus_compute_digest(cons1_str, &digests1)); - tor_split_lines(cons1, cons1_str, (int)strlen(cons1_str)); + consensus_split_lines(cons1, cons1_str, area); /* diff doesn't have enough lines. */ cons2 = consdiff_apply_diff(cons1, diff, &digests1); @@ -903,8 +912,8 @@ test_consdiff_apply_diff(void *arg) expect_single_log_msg_containing("too short") /* first line doesn't match format-version string. */ - smartlist_add(diff, (char*)"foo-bar"); - smartlist_add(diff, (char*)"header-line"); + smartlist_add_linecpy(diff, area, "foo-bar"); + smartlist_add_linecpy(diff, area, "header-line"); mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); @@ -912,9 +921,9 @@ test_consdiff_apply_diff(void *arg) /* 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"); - smartlist_add(diff, (char*)"x"); + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "word a b"); + smartlist_add_linecpy(diff, area, "x"); mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); @@ -922,8 +931,8 @@ test_consdiff_apply_diff(void *arg) /* 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"); + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash a b c"); mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); @@ -931,8 +940,8 @@ test_consdiff_apply_diff(void *arg) /* base16 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"); + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash aaa bbb"); mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); @@ -941,8 +950,8 @@ test_consdiff_apply_diff(void *arg) /* base16 digests contain non-base16 characters. */ smartlist_clear(diff); - smartlist_add(diff, (char*)"network-status-diff-version 1"); - smartlist_add(diff, (char*)"hash" + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash" " ????????????????????????????????????????????????????????????????" " ----------------------------------------------------------------"); mock_clean_saved_logs(); @@ -954,13 +963,13 @@ test_consdiff_apply_diff(void *arg) * 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" + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash" /* sha3 of cons1. */ " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" /* sha256 of cons2. */ " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA"); - smartlist_add(diff, (char*)"foobar"); + smartlist_add_linecpy(diff, area, "foobar"); mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); @@ -969,8 +978,8 @@ test_consdiff_apply_diff(void *arg) /* 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" + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash" /* bogus sha256. */ " 3333333333333333333333333333333333333333333333333333333333333333" /* sha256 of cons2. */ @@ -983,8 +992,8 @@ test_consdiff_apply_diff(void *arg) /* 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" + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash" /* sha3 of cons1. */ " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" /* bogus sha3. */ @@ -999,13 +1008,13 @@ test_consdiff_apply_diff(void *arg) /* XXXX No longer possible, since we aren't using the other algorithm. */ /* Resulting consensus digest cannot be computed */ smartlist_clear(diff); - smartlist_add(diff, (char*)"network-status-diff-version 1"); - smartlist_add(diff, (char*)"hash" + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash" /* sha3 of cons1. */ " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" /* bogus sha3. */ " 3333333333333333333333333333333333333333333333333333333333333333"); - smartlist_add(diff, (char*)"1,2d"); // remove starting line + smartlist_add_linecpy(diff, area, "1,2d"); // remove starting line mock_clean_saved_logs(); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_EQ, cons2); @@ -1015,15 +1024,15 @@ test_consdiff_apply_diff(void *arg) /* 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" + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash" /* sha3 of cons1. */ " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4" /* sha3 of cons2. */ " 90A418881B2FCAB3D9E60EE02E4D666D56CFA38F8A3B7AA3E0ADBA530DDA9353"); - smartlist_add(diff, (char*)"3c"); - smartlist_add(diff, (char*)"sample"); - smartlist_add(diff, (char*)"."); + smartlist_add_linecpy(diff, area, "3c"); + smartlist_add_linecpy(diff, area, "sample"); + smartlist_add_linecpy(diff, area, "."); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_NE, cons2); tt_str_op( @@ -1036,15 +1045,15 @@ test_consdiff_apply_diff(void *arg) /* 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" + smartlist_add_linecpy(diff, area, "network-status-diff-version 1"); + smartlist_add_linecpy(diff, area, "hash" /* sha3 of cons1. */ " 06646d6cf563a41869d3b02e73254372ae3140046c5e7d83c9f71e54976af9b4" /* sha3 of cons2. */ " 90a418881b2fcab3d9e60ee02e4d666d56cfa38f8a3b7aa3e0adba530dda9353"); - smartlist_add(diff, (char*)"3c"); - smartlist_add(diff, (char*)"sample"); - smartlist_add(diff, (char*)"."); + smartlist_add_linecpy(diff, area, "3c"); + smartlist_add_linecpy(diff, area, "sample"); + smartlist_add_linecpy(diff, area, "."); cons2 = consdiff_apply_diff(cons1, diff, &digests1); tt_ptr_op(NULL, OP_NE, cons2); tt_str_op( @@ -1062,6 +1071,7 @@ test_consdiff_apply_diff(void *arg) tor_free(cons1_str); smartlist_free(cons1); smartlist_free(diff); + memarea_drop_all(area); } #define CONSDIFF_LEGACY(name) \ -- cgit v1.2.3-54-g00ecf