39 #define CONSDIFF_PRIVATE
46 static const char* ns_diff_version =
"network-status-diff-version 1";
47 static const char* hash_token =
"hash";
55 return a->len == b->len &&
fast_memeq(a->s, b->s, a->len);
62 const size_t len = strlen(b);
64 cdline_t bline = { b, (uint32_t)len };
73 const size_t len = strlen(b);
75 return a->len >= len &&
fast_memeq(a->s, b, len);
83 size_t len = strlen(s);
87 line->len = (uint32_t)len;
105 consensus_digest_t *digest_out))
108 cons, len, DIGEST_SHA3_256);
118 consensus_digest_t *digest_out))
139 STATIC smartlist_slice_t *
142 int list_len = smartlist_len(list);
150 smartlist_slice_t *slice = tor_malloc(
sizeof(smartlist_slice_t));
152 slice->offset = start;
153 slice->len = end - start;
165 lcs_lengths(
const smartlist_slice_t *slice1,
const smartlist_slice_t *slice2,
168 size_t a_size =
sizeof(int) * (slice2->len+1);
171 int *result = tor_malloc_zero(a_size);
173 int *prev = tor_malloc(a_size);
175 tor_assert(direction == 1 || direction == -1);
177 int si = slice1->offset;
178 if (direction == -1) {
179 si += (slice1->len-1);
182 for (
int i = 0; i < slice1->len; ++i, si+=direction) {
184 const cdline_t *line1 = smartlist_get(slice1->list, si);
186 memcpy(prev, result, a_size);
188 int sj = slice2->offset;
189 if (direction == -1) {
190 sj += (slice2->len-1);
193 for (
int j = 0; j < slice2->len; ++j, sj+=direction) {
195 const cdline_t *line2 = smartlist_get(slice2->list, sj);
198 result[j + 1] = prev[j] + 1;
201 result[j + 1] =
MAX(result[j], prev[j + 1]);
215 while (slice1->len>0 && slice2->len>0) {
216 const cdline_t *line1 = smartlist_get(slice1->list, slice1->offset);
217 const cdline_t *line2 = smartlist_get(slice2->list, slice2->offset);
221 slice1->offset++; slice1->len--;
222 slice2->offset++; slice2->len--;
225 int i1 = (slice1->offset+slice1->len)-1;
226 int i2 = (slice2->offset+slice2->len)-1;
228 while (slice1->len>0 && slice2->len>0) {
229 const cdline_t *line1 = smartlist_get(slice1->list, i1);
230 const cdline_t *line2 = smartlist_get(slice2->list, i2);
246 const cdline_t *
string)
248 int end = slice->offset + slice->len;
249 for (
int i = slice->offset; i < end; ++i) {
250 const cdline_t *el = smartlist_get(slice->list, i);
265 const smartlist_slice_t *slice1,
const smartlist_slice_t *slice2)
268 tor_assert(slice1->len == 0 || slice1->len == 1);
270 if (slice1->len == 1) {
271 const cdline_t *line_common = smartlist_get(slice1->list, slice1->offset);
277 int end = slice2->offset + slice2->len;
278 for (
int i = slice2->offset; i < end; ++i) {
293 optimal_column_to_split(
const smartlist_slice_t *top,
294 const smartlist_slice_t *bot,
295 const smartlist_slice_t *slice2)
299 int column=0, max_sum=-1;
301 for (
int i = 0; i < slice2->len+1; ++i) {
302 int sum = lens_top[i] + lens_bot[slice2->len-i];
328 smartlist_slice_t *slice2,
333 if (slice1->len <= 1) {
336 }
else if (slice2->len <= 1) {
341 smartlist_slice_t *top, *bot, *left, *right;
344 int mid = slice1->len/2;
345 top =
smartlist_slice(slice1->list, slice1->offset, slice1->offset+mid);
347 slice1->offset+slice1->len);
350 int mid2 = optimal_column_to_split(top, bot, slice2);
351 left =
smartlist_slice(slice2->list, slice2->offset, slice2->offset+mid2);
353 slice2->offset+slice2->len);
365 #define NOT_VALID_BASE64 255
366 #define X NOT_VALID_BASE64
367 #define SP NOT_VALID_BASE64
368 #define PAD NOT_VALID_BASE64
369 static const uint8_t base64_compare_table[256] = {
370 X,
X,
X,
X,
X,
X,
X,
X,
X, SP, SP, SP,
X, SP,
X,
X,
371 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
372 SP,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X, 62,
X,
X,
X, 63,
373 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
X,
X,
X, PAD,
X,
X,
374 X, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
375 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
X,
X,
X,
X,
X,
376 X, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
377 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
X,
X,
X,
X,
X,
378 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
379 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
380 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
381 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
382 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
383 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
384 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
385 X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
X,
401 const char *hash = memchr(line->s + 2,
' ', line->len - 2);
407 const char *hash_end = hash;
411 while (base64_compare_table[*((
unsigned char*)hash_end)]
412 != NOT_VALID_BASE64 &&
413 hash_end < line->s + line->len) {
418 if (hash_end == hash) {
425 tor_assert((
size_t)(hash_end - hash) <= UINT32_MAX);
426 hash_out->len = (uint32_t)(hash_end - hash);
437 if (line->len < 2 ||
fast_memneq(line->s,
"r ", 2))
451 int len = smartlist_len(cons);
458 const cdline_t *line = smartlist_get(cons, cur);
463 line = smartlist_get(cons, cur);
475 if (!hash1->s && !hash2->s) {
486 const unsigned char *a = (
unsigned char*)hash1->s;
487 const unsigned char *b = (
unsigned char*)hash2->s;
488 const unsigned char *a_end = a + hash1->len;
489 const unsigned char *b_end = b + hash2->len;
491 uint8_t av = base64_compare_table[*a];
492 uint8_t bv = base64_compare_table[*b];
493 if (av == NOT_VALID_BASE64) {
494 if (bv == NOT_VALID_BASE64) {
501 }
else if (bv == NOT_VALID_BASE64) {
504 }
else if (av < bv) {
507 }
else if (av > bv) {
519 }
else if (b == b_end) {
537 #define ROUTER_ID_ITERATOR_INIT { { NULL, 0 }, { NULL, 0 } }
550 const char *consname,
555 if (*idxp < smartlist_len(cons)) {
556 memcpy(&iter->last_hash, &iter->hash,
sizeof(cdline_t));
557 if (
get_id_hash(smartlist_get(cons, *idxp), &iter->hash) < 0 ||
558 base64cmp(&iter->hash, &iter->last_hash) <= 0) {
559 log_warn(
LD_CONSDIFF,
"Refusing to generate consensus diff because "
560 "the %s consensus doesn't have its router entries sorted "
561 "properly.", consname);
570 #define START_OF_SIGNATURES_SECTION "directory-signature "
586 for (idx = 0; idx < smartlist_len(cons); ++idx) {
587 cdline_t *line = smartlist_get(cons, idx);
593 if (dirsig_idx >= 0) {
595 while (smartlist_len(cons) > dirsig_idx)
632 int len1 = smartlist_len(cons1);
633 int len2 = smartlist_len(cons2);
636 if (remove_trailer) {
647 int start1=0, start2=0;
660 while (i1 < len1 || i2 < len2) {
680 if (i1 < len1 || i2 < len2) {
692 int cmp =
base64cmp(&iter1.hash, &iter2.hash);
694 if (i1 < len1 && cmp < 0) {
705 }
else if (i2 < len2 && cmp > 0) {
721 cmp =
base64cmp(&iter1.hash, &iter2.hash);
731 #define MAX_LINE_COUNT (10000)
732 if (i1-start1 > MAX_LINE_COUNT || i2-start2 > MAX_LINE_COUNT) {
733 log_warn(
LD_CONSDIFF,
"Refusing to generate consensus diff because "
734 "we found too few common router ids.");
743 start1 = i1, start2 = i2;
749 i1=len1-1, i2=len2-1;
751 while (i1 >= 0 || i2 >= 0) {
753 int start1x, start2x, end1, end2, added, deleted;
767 end1 = i1, end2 = i2;
777 start1x = i1+1, start2x = i2+1;
778 added = end2-i2, deleted = end1-i1;
785 tor_snprintf(buf,
sizeof(buf),
"%i,%id", start1x+1, start1x+deleted);
793 }
else if (deleted == 1) {
797 tor_snprintf(buf,
sizeof(buf),
"%i,%ic", start1x+1, start1x+deleted);
801 for (i = start2x; i <= end2; ++i) {
802 cdline_t *line = smartlist_get(cons2, i);
804 log_warn(
LD_CONSDIFF,
"Cannot generate consensus diff because "
805 "one of the lines to be added is \".\".");
814 smartlist_free(cons1);
815 bitarray_free(changed1);
816 bitarray_free(changed2);
822 smartlist_free(cons1);
823 bitarray_free(changed1);
824 bitarray_free(changed2);
826 smartlist_free(result);
835 get_linenum(
const char **s,
int *num_out)
839 if (!TOR_ISDIGIT(**s)) {
842 *num_out = (int)
tor_parse_long(*s, 10, 0, INT32_MAX, &ok, &next);
860 int diff_starting_line)
862 int diff_len = smartlist_len(diff);
863 int j = smartlist_len(cons1);
866 for (
int i=diff_starting_line; i<diff_len; ++i) {
867 const cdline_t *diff_cdline = smartlist_get(diff, i);
870 if (diff_cdline->len >
sizeof(diff_line) - 1) {
871 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
872 "an ed command was far too long");
876 memcpy(diff_line, diff_cdline->s, diff_cdline->len);
877 diff_line[diff_cdline->len] = 0;
878 const char *ptr = diff_line;
879 int start = 0, end = 0;
882 if (get_linenum(&ptr, &start) < 0) {
883 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
884 "an ed command was missing a line number.");
893 end = smartlist_len(cons1);
895 }
else if (get_linenum(&ptr, &end) < 0) {
896 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
897 "an ed command was missing a range end line number.");
902 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
903 "an invalid range was found in an ed command.");
912 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
913 "its commands are not properly sorted in reverse order.");
918 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
919 "a line with no ed command was found");
923 if (*(ptr+1) !=
'\0') {
924 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
925 "an ed command longer than one char was found.");
937 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
938 "an unrecognised ed command was found.");
943 if (end_was_eof && action !=
'd') {
944 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
945 "it wanted to use $ with a command other than delete");
950 if (had_range && action ==
'a') {
951 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
952 "it wanted to add lines after a range.");
957 for (; j && j > end; --j) {
958 cdline_t *cons_line = smartlist_get(cons1, j-1);
963 if (action ==
'c' || action ==
'd') {
964 while (--j >= start) {
972 if (action ==
'a' || action ==
'c') {
976 while (i < diff_len) {
980 if (++i == diff_len) {
981 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
982 "it has lines to be inserted that don't end with a \".\".");
990 if (added_i == added_end) {
991 log_warn(
LD_CONSDIFF,
"Could not apply consensus diff because "
992 "it has an ed command that tries to insert zero lines.");
996 while (added_i > added_end) {
997 cdline_t *added_line = smartlist_get(diff, added_i--);
1004 for (; j > 0; --j) {
1005 cdline_t *cons_line = smartlist_get(cons1, j-1);
1015 smartlist_free(cons2);
1028 const consensus_digest_t *digests1,
1029 const consensus_digest_t *digests2,
1043 "the generated ed diff could not be tested to successfully generate "
1044 "the target consensus.");
1050 if (smartlist_len(cons2) == smartlist_len(ed_cons2)) {
1052 const cdline_t *line2 = smartlist_get(ed_cons2, line1_sl_idx);
1057 } SMARTLIST_FOREACH_END(line1);
1061 smartlist_free(ed_cons2);
1065 "the generated ed diff did not generate the target consensus "
1066 "successfully when tested.");
1084 cons1_hash_hex, cons2_hash_hex);
1087 smartlist_free(ed_diff);
1094 smartlist_free(ed_diff);
1111 const cdline_t *format;
1113 char *cons1_hash_hex, *cons2_hash_hex;
1114 if (smartlist_len(diff) < 2) {
1115 log_info(
LD_CONSDIFF,
"The provided consensus diff is too short.");
1120 format = smartlist_get(diff, 0);
1122 log_warn(
LD_CONSDIFF,
"The provided consensus diff format is not known.");
1129 const cdline_t *line2 = smartlist_get(diff, 1);
1130 char *h = tor_memdup_nulterm(line2->s, line2->len);
1136 if (smartlist_len(hash_words) != 3 ||
1137 strcmp(smartlist_get(hash_words, 0), hash_token)) {
1138 log_info(
LD_CONSDIFF,
"The provided consensus diff does not include "
1139 "the necessary digests.");
1148 cons1_hash_hex = smartlist_get(hash_words, 1);
1149 cons2_hash_hex = smartlist_get(hash_words, 2);
1152 log_info(
LD_CONSDIFF,
"The provided consensus diff includes "
1153 "base16-encoded digests of incorrect size.");
1161 log_info(
LD_CONSDIFF,
"The provided consensus diff includes "
1162 "malformed digests.");
1174 smartlist_free(hash_words);
1181 smartlist_free(hash_words);
1194 const consensus_digest_t *digests1)
1197 char *cons2_str = NULL;
1207 (
const uint8_t*)e_cons1_hash)) {
1210 log_warn(
LD_CONSDIFF,
"Refusing to apply consensus diff because "
1211 "the base consensus doesn't match the digest as found in "
1212 "the consensus diff header.");
1218 hex_digest1, e_hex_digest1);
1233 consensus_digest_t cons2_digests;
1235 &cons2_digests) < 0) {
1237 log_warn(
LD_CONSDIFF,
"Could not compute digests of the consensus "
1238 "resulting from applying a consensus diff.");
1245 (
const uint8_t*)e_cons2_hash)) {
1246 log_warn(
LD_CONSDIFF,
"Refusing to apply consensus diff because "
1247 "the resulting consensus doesn't match the digest as found in "
1248 "the consensus diff header.");
1256 hex_digest2, e_hex_digest2);
1267 smartlist_free(cons2);
1274 #define CONSENSUS_LINE_MAX_LEN (1<<20)
1290 const char *s,
size_t len,
1293 const char *end_of_str = s + len;
1295 while (s < end_of_str) {
1296 const char *eol = memchr(s,
'\n', end_of_str - s);
1307 line->len = (uint32_t)(eol - s);
1325 char *result = tor_malloc(n);
1328 memcpy(out, cdline->s, cdline->len);
1331 } SMARTLIST_FOREACH_END(cdline);
1342 const char *cons2,
size_t cons2len)
1344 consensus_digest_t d1, d2;
1345 smartlist_t *lines1 = NULL, *lines2 = NULL, *result_lines = NULL;
1347 char *result = NULL;
1351 if (BUG(r1 < 0 || r2 < 0))
1367 smartlist_free(result_lines);
1371 smartlist_free(lines1);
1372 smartlist_free(lines2);
1382 size_t consensus_len,
1386 consensus_digest_t d1;
1389 char *result = NULL;
1406 smartlist_free(lines1);
1407 smartlist_free(lines2);
1418 return (len >= strlen(ns_diff_version) &&
1419 fast_memeq(document, ns_diff_version, strlen(ns_diff_version)));
int base16_decode(char *dest, size_t destlen, const char *src, size_t srclen)
void base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
static void bitarray_set(bitarray_t *b, int bit)
static unsigned int bitarray_is_set(bitarray_t *b, int bit)
static bitarray_t * bitarray_init_zero(unsigned int n_bits)
char * consensus_diff_apply(const char *consensus, size_t consensus_len, const char *diff, size_t diff_len)
STATIC void smartlist_add_linecpy(smartlist_t *lst, memarea_t *area, const char *s)
#define CONSENSUS_LINE_MAX_LEN
STATIC int line_str_eq(const cdline_t *a, const char *b)
static cdline_t * cdline_linecpy(memarea_t *area, const char *s)
#define ROUTER_ID_ITERATOR_INIT
char * consensus_diff_generate(const char *cons1, size_t cons1len, const char *cons2, size_t cons2len)
STATIC void trim_slices(smartlist_slice_t *slice1, smartlist_slice_t *slice2)
STATIC int * lcs_lengths(const smartlist_slice_t *slice1, const smartlist_slice_t *slice2, int direction)
STATIC void set_changed(bitarray_t *changed1, bitarray_t *changed2, const smartlist_slice_t *slice1, const smartlist_slice_t *slice2)
static int find_next_router_line(const smartlist_t *cons, const char *consname, int *idxp, router_id_iterator_t *iter)
static cdline_t * preprocess_consensus(memarea_t *area, smartlist_t *cons)
STATIC smartlist_t * apply_ed_diff(const smartlist_t *cons1, const smartlist_t *diff, int diff_starting_line)
smartlist_t * consdiff_gen_diff(const smartlist_t *cons1, const smartlist_t *cons2, const consensus_digest_t *digests1, const consensus_digest_t *digests2, memarea_t *area)
STATIC int consensus_digest_eq(const uint8_t *d1, const uint8_t *d2)
STATIC int base64cmp(const cdline_t *hash1, const cdline_t *hash2)
STATIC int next_router(const smartlist_t *cons, int cur)
static int line_starts_with_str(const cdline_t *a, const char *b)
STATIC smartlist_slice_t * smartlist_slice(const smartlist_t *list, int start, int end)
STATIC void calc_changes(smartlist_slice_t *slice1, smartlist_slice_t *slice2, bitarray_t *changed1, bitarray_t *changed2)
STATIC int consensus_compute_digest_as_signed(const char *cons, size_t len, consensus_digest_t *digest_out)
static char * consensus_join_lines(const smartlist_t *inp)
STATIC int is_valid_router_entry(const cdline_t *line)
char * consdiff_apply_diff(const smartlist_t *cons1, const smartlist_t *diff, const consensus_digest_t *digests1)
STATIC int consensus_split_lines(smartlist_t *out, const char *s, size_t len, memarea_t *area)
STATIC smartlist_t * gen_ed_diff(const smartlist_t *cons1_orig, const smartlist_t *cons2, memarea_t *area)
STATIC int get_id_hash(const cdline_t *line, cdline_t *hash_out)
STATIC int lines_eq(const cdline_t *a, const cdline_t *b)
int looks_like_a_consensus_diff(const char *document, size_t len)
STATIC int smartlist_slice_string_pos(const smartlist_slice_t *slice, const cdline_t *string)
#define START_OF_SIGNATURES_SECTION
int consdiff_get_digests(const smartlist_t *diff, char *digest1_out, char *digest2_out)
STATIC int consensus_compute_digest(const char *cons, size_t len, consensus_digest_t *digest_out)
#define HEX_DIGEST256_LEN
int crypto_digest256(char *digest, const char *m, size_t len, digest_algorithm_t algorithm)
#define fast_memeq(a, b, c)
#define fast_memneq(a, b, c)
memarea_t * memarea_new(void)
void * memarea_memdup(memarea_t *area, const void *s, size_t n)
void * memarea_alloc(memarea_t *area, size_t sz)
#define memarea_drop_all(area)
Header file for ns_parse.c.
int router_get_networkstatus_v3_sha3_as_signed(uint8_t *digest_out, const char *s, size_t len)
Master header file for Tor-specific functionality.
long tor_parse_long(const char *s, int base, long min, long max, int *ok, char **next)
int tor_snprintf(char *str, size_t size, const char *format,...)
void smartlist_reverse(smartlist_t *sl)
void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
smartlist_t * smartlist_new(void)
void smartlist_add(smartlist_t *sl, void *element)
void smartlist_del(smartlist_t *sl, int idx)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, int flags, int max)
#define MOCK_IMPL(rv, funcname, arglist)