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)));