checksum.c

   1 /*
   2  * Routines to support checksumming of bytes.
   3  *
   4  * Copyright (C) 1996 Andrew Tridgell
   5  * Copyright (C) 1996 Paul Mackerras
   6  * Copyright (C) 2004-2020 Wayne Davison
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 3 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * In addition, as a special exception, the copyright holders give
  14  * permission to dynamically link rsync with the OpenSSL and xxhash
  15  * libraries when those libraries are being distributed in compliance
  16  * with their license terms, and to distribute a dynamically linked
  17  * combination of rsync and these libraries.  This is also considered
  18  * to be covered under the GPL's System Libraries exception.
  19  *
  20  * This program is distributed in the hope that it will be useful,
  21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  * GNU General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License along
  26  * with this program; if not, visit the http://fsf.org website.
  27  */
  28
  29 #include "rsync.h"
  30 #ifdef SUPPORT_XXHASH
  31 #include "xxhash.h"
  32 #endif
  33 #ifdef USE_OPENSSL
  34 #include "openssl/md5.h"
  35 #endif
  36
  37 extern int am_server;
  38 extern int local_server;
  39 extern int whole_file;
  40 extern int read_batch;
  41 extern int checksum_seed;
  42 extern int protocol_version;
  43 extern int proper_seed_order;
  44 extern char *checksum_choice;
  45
  46 #define CSUM_NONE 0
  47 #define CSUM_MD4_ARCHAIC 1
  48 #define CSUM_MD4_BUSTED 2
  49 #define CSUM_MD4_OLD 3
  50 #define CSUM_MD4 4
  51 #define CSUM_MD5 5
  52 #define CSUM_XXHASH 6
  53
  54 #define CSUM_SAW_BUFLEN 10
  55
  56 struct csum_struct {
  57         int num;
  58         const char *name;
  59 } valid_checksums[] = {
  60 #ifdef SUPPORT_XXHASH
  61         { CSUM_XXHASH, "xxhash" },
  62 #endif
  63         { CSUM_MD5, "md5" },
  64         { CSUM_MD4, "md4" },
  65         { CSUM_NONE, "none" },
  66         { -1, NULL }
  67 };
  68
  69 #define MAX_CHECKSUM_LIST 1024
  70
  71 #ifndef USE_OPENSSL
  72 #define MD5_CTX md_context
  73 #define MD5_Init md5_begin
  74 #define MD5_Update md5_update
  75 #define MD5_Final(digest, cptr) md5_result(cptr, digest)
  76 #endif
  77
  78 int xfersum_type = 0; /* used for the file transfer checksums */
  79 int checksum_type = 0; /* used for the pre-transfer (--checksum) checksums */
  80 const char *negotiated_csum_name = NULL;
  81
  82 static int parse_csum_name(const char *name, int len, int allow_auto)
  83 {
  84         struct csum_struct *cs;
  85
  86         if (len < 0 && name)
  87                 len = strlen(name);
  88
  89         if (!name || (allow_auto && len == 4 && strncasecmp(name, "auto", 4) == 0)) {
  90                 if (protocol_version >= 30)
  91                         return CSUM_MD5;
  92                 if (protocol_version >= 27)
  93                         return CSUM_MD4_OLD;
  94                 if (protocol_version >= 21)
  95                         return CSUM_MD4_BUSTED;
  96                 return CSUM_MD4_ARCHAIC;
  97         }
  98
  99         for (cs = valid_checksums; cs->name; cs++) {
 100                 if (strncasecmp(name, cs->name, len) == 0 && cs->name[len] == '\0')
 101                         return cs->num;
 102         }
 103
 104         if (allow_auto) {
 105                 rprintf(FERROR, "unknown checksum name: %s\n", name);
 106                 exit_cleanup(RERR_UNSUPPORTED);
 107         }
 108
 109         return -1;
 110 }
 111
 112 static const char *checksum_name(int num)
 113 {
 114         struct csum_struct *cs;
 115
 116         for (cs = valid_checksums; cs->name; cs++) {
 117                 if (num == cs->num)
 118                         return cs->name;
 119         }
 120
 121         if (num < CSUM_MD4)
 122                 return "MD4";
 123
 124         return "UNKNOWN";
 125 }
 126
 127 void parse_checksum_choice(int final_call)
 128 {
 129         if (!negotiated_csum_name) {
 130                 char *cp = checksum_choice ? strchr(checksum_choice, ',') : NULL;
 131                 if (cp) {
 132                         xfersum_type = parse_csum_name(checksum_choice, cp - checksum_choice, 1);
 133                         checksum_type = parse_csum_name(cp+1, -1, 1);
 134                 } else
 135                         xfersum_type = checksum_type = parse_csum_name(checksum_choice, -1, 1);
 136         }
 137
 138         if (xfersum_type == CSUM_NONE)
 139                 whole_file = 1;
 140
 141         if (final_call && DEBUG_GTE(CSUM, 1)) {
 142                 if (negotiated_csum_name)
 143                         rprintf(FINFO, "[%s] negotiated checksum: %s\n", who_am_i(), negotiated_csum_name);
 144                 else if (xfersum_type == checksum_type) {
 145                         rprintf(FINFO, "[%s] %s checksum: %s\n", who_am_i(),
 146                                 checksum_choice ? "chosen" : "protocol-based",
 147                                 checksum_name(xfersum_type));
 148                 } else {
 149                         rprintf(FINFO, "[%s] chosen transfer checksum: %s\n",
 150                                 who_am_i(), checksum_name(xfersum_type));
 151                         rprintf(FINFO, "[%s] chosen pre-transfer checksum: %s\n",
 152                                 who_am_i(), checksum_name(checksum_type));
 153                 }
 154         }
 155 }
 156
 157 static int parse_checksum_list(const char *from, char *sumbuf, int sumbuf_len, char *saw)
 158 {
 159         char *to = sumbuf, *tok = NULL;
 160         int cnt = 0;
 161
 162         memset(saw, 0, CSUM_SAW_BUFLEN);
 163
 164         while (1) {
 165                 if (*from == ' ' || !*from) {
 166                         if (tok) {
 167                                 int sum_type = parse_csum_name(tok, to - tok, 0);
 168                                 if (sum_type >= 0 && !saw[sum_type])
 169                                         saw[sum_type] = ++cnt;
 170                                 else
 171                                         to = tok - (tok != sumbuf);
 172                                 tok = NULL;
 173                         }
 174                         if (!*from++)
 175                                 break;
 176                         continue;
 177                 }
 178                 if (!tok) {
 179                         if (to != sumbuf)
 180                                 *to++ = ' ';
 181                         tok = to;
 182                 }
 183                 if (to - sumbuf >= sumbuf_len - 1) {
 184                         to = tok - (tok != sumbuf);
 185                         break;
 186                 }
 187                 *to++ = *from++;
 188         }
 189         *to = '\0';
 190
 191         return to - sumbuf;
 192 }
 193
 194 void negotiate_checksum(int f_in, int f_out, const char *csum_list, int saw_fail)
 195 {
 196         char *tok, sumbuf[MAX_CHECKSUM_LIST], saw[CSUM_SAW_BUFLEN];
 197         int sum_type, len;
 198
 199         /* Simplify the user-provided string so that it contains valid
 200          * checksum names without any duplicates. The client side also
 201          * makes use of the saw values when scanning the server's list. */
 202         if (csum_list && *csum_list && (!am_server || local_server)) {
 203                 len = parse_checksum_list(csum_list, sumbuf, sizeof sumbuf, saw);
 204                 if (saw_fail && !len)
 205                         len = strlcpy(sumbuf, "FAIL", sizeof sumbuf);
 206                 csum_list = sumbuf;
 207         } else {
 208                 memset(saw, 0, CSUM_SAW_BUFLEN);
 209                 csum_list = NULL;
 210         }
 211
 212         if (!csum_list || !*csum_list) {
 213                 struct csum_struct *cs;
 214                 int cnt = 0;
 215                 for (cs = valid_checksums, len = 0; cs->name; cs++) {
 216                         if (cs->num == CSUM_NONE)
 217                                 continue;
 218                         if (len)
 219                                 sumbuf[len++]= ' ';
 220                         len += strlcpy(sumbuf+len, cs->name, sizeof sumbuf - len);
 221                         if (len >= (int)sizeof sumbuf - 1)
 222                                 exit_cleanup(RERR_UNSUPPORTED); /* IMPOSSIBLE... */
 223                         saw[cs->num] = ++cnt;
 224                 }
 225         }
 226
 227         /* Each side sends their list of valid checksum names to the other side and
 228          * then both sides pick the first name in the client's list that is also in
 229          * the server's list. */
 230         if (!local_server)
 231                 write_vstring(f_out, sumbuf, len);
 232
 233         if (!local_server || read_batch)
 234                 len = read_vstring(f_in, sumbuf, sizeof sumbuf);
 235
 236         if (len > 0) {
 237                 int best = CSUM_SAW_BUFLEN; /* We want best == 1 from the client list */
 238                 if (am_server)
 239                         memset(saw, 1, CSUM_SAW_BUFLEN); /* The first client's choice is the best choice */
 240                 for (tok = strtok(sumbuf, " \t"); tok; tok = strtok(NULL, " \t")) {
 241                         sum_type = parse_csum_name(tok, -1, 0);
 242                         if (sum_type < 0 || !saw[sum_type] || best < saw[sum_type])
 243                                 continue;
 244                         xfersum_type = checksum_type = sum_type;
 245                         negotiated_csum_name = tok;
 246                         best = saw[sum_type];
 247                         if (best == 1)
 248                                 break;
 249                 }
 250                 if (negotiated_csum_name) {
 251                         negotiated_csum_name = strdup(negotiated_csum_name);
 252                         return;
 253                 }
 254         }
 255
 256         if (!am_server)
 257                 msleep(20);
 258         rprintf(FERROR, "Failed to negotiate a common checksum\n");
 259         exit_cleanup(RERR_UNSUPPORTED);
 260 }
 261
 262 int csum_len_for_type(int cst, BOOL flist_csum)
 263 {
 264         switch (cst) {
 265           case CSUM_NONE:
 266                 return 1;
 267           case CSUM_MD4_ARCHAIC:
 268                 /* The oldest checksum code is rather weird: the file-list code only sent
 269                  * 2-byte checksums, but all other checksums were full MD4 length. */
 270                 return flist_csum ? 2 : MD4_DIGEST_LEN;
 271           case CSUM_MD4:
 272           case CSUM_MD4_OLD:
 273           case CSUM_MD4_BUSTED:
 274                 return MD4_DIGEST_LEN;
 275           case CSUM_MD5:
 276                 return MD5_DIGEST_LEN;
 277 #ifdef SUPPORT_XXHASH
 278           case CSUM_XXHASH:
 279                 return sizeof (XXH64_hash_t);
 280 #endif
 281           default: /* paranoia to prevent missing case values */
 282                 exit_cleanup(RERR_UNSUPPORTED);
 283         }
 284         return 0;
 285 }
 286
 287 int canonical_checksum(int csum_type)
 288 {
 289         return csum_type >= CSUM_MD4 ? 1 : 0;
 290 }
 291
 292 #ifndef HAVE_SIMD /* See simd-checksum-*.cpp. */
 293 /*
 294   a simple 32 bit checksum that can be updated from either end
 295   (inspired by Mark Adler's Adler-32 checksum)
 296   */
 297 uint32 get_checksum1(char *buf1, int32 len)
 298 {
 299         int32 i;
 300         uint32 s1, s2;
 301         schar *buf = (schar *)buf1;
 302
 303         s1 = s2 = 0;
 304         for (i = 0; i < (len-4); i+=4) {
 305                 s2 += 4*(s1 + buf[i]) + 3*buf[i+1] + 2*buf[i+2] + buf[i+3] + 10*CHAR_OFFSET;
 306                 s1 += (buf[i+0] + buf[i+1] + buf[i+2] + buf[i+3] + 4*CHAR_OFFSET);
 307         }
 308         for (; i < len; i++) {
 309                 s1 += (buf[i]+CHAR_OFFSET); s2 += s1;
 310         }
 311         return (s1 & 0xffff) + (s2 << 16);
 312 }
 313 #endif
 314
 315 void get_checksum2(char *buf, int32 len, char *sum)
 316 {
 317         md_context m;
 318         MD5_CTX m5;
 319
 320         switch (xfersum_type) {
 321           case CSUM_MD5: {
 322                 uchar seedbuf[4];
 323                 MD5_Init(&m5);
 324                 if (proper_seed_order) {
 325                         if (checksum_seed) {
 326                                 SIVALu(seedbuf, 0, checksum_seed);
 327                                 MD5_Update(&m5, seedbuf, 4);
 328                         }
 329                         MD5_Update(&m5, (uchar *)buf, len);
 330                 } else {
 331                         MD5_Update(&m5, (uchar *)buf, len);
 332                         if (checksum_seed) {
 333                                 SIVALu(seedbuf, 0, checksum_seed);
 334                                 MD5_Update(&m5, seedbuf, 4);
 335                         }
 336                 }
 337                 MD5_Final((uchar *)sum, &m5);
 338                 break;
 339           }
 340           case CSUM_MD4:
 341           case CSUM_MD4_OLD:
 342           case CSUM_MD4_BUSTED:
 343           case CSUM_MD4_ARCHAIC: {
 344                 int32 i;
 345                 static char *buf1;
 346                 static int32 len1;
 347
 348                 mdfour_begin(&m);
 349
 350                 if (len > len1) {
 351                         if (buf1)
 352                                 free(buf1);
 353                         buf1 = new_array(char, len+4);
 354                         len1 = len;
 355                         if (!buf1)
 356                                 out_of_memory("get_checksum2");
 357                 }
 358
 359                 memcpy(buf1, buf, len);
 360                 if (checksum_seed) {
 361                         SIVAL(buf1,len,checksum_seed);
 362                         len += 4;
 363                 }
 364
 365                 for (i = 0; i + CSUM_CHUNK <= len; i += CSUM_CHUNK)
 366                         mdfour_update(&m, (uchar *)(buf1+i), CSUM_CHUNK);
 367
 368                 /*
 369                  * Prior to version 27 an incorrect MD4 checksum was computed
 370                  * by failing to call mdfour_tail() for block sizes that
 371                  * are multiples of 64.  This is fixed by calling mdfour_update()
 372                  * even when there are no more bytes.
 373                  */
 374                 if (len - i > 0 || xfersum_type > CSUM_MD4_BUSTED)
 375                         mdfour_update(&m, (uchar *)(buf1+i), len-i);
 376
 377                 mdfour_result(&m, (uchar *)sum);
 378                 break;
 379           }
 380 #ifdef SUPPORT_XXHASH
 381           case CSUM_XXHASH:
 382                 SIVAL64(sum, 0, XXH64(buf, len, checksum_seed));
 383                 break;
 384 #endif
 385           default: /* paranoia to prevent missing case values */
 386                 exit_cleanup(RERR_UNSUPPORTED);
 387         }
 388 }
 389
 390 void file_checksum(const char *fname, const STRUCT_STAT *st_p, char *sum)
 391 {
 392         struct map_struct *buf;
 393         OFF_T i, len = st_p->st_size;
 394         md_context m;
 395         MD5_CTX m5;
 396         int32 remainder;
 397         int fd;
 398
 399         memset(sum, 0, MAX_DIGEST_LEN);
 400
 401         fd = do_open(fname, O_RDONLY, 0);
 402         if (fd == -1)
 403                 return;
 404
 405         buf = map_file(fd, len, MAX_MAP_SIZE, CSUM_CHUNK);
 406
 407         switch (checksum_type) {
 408           case CSUM_MD5:
 409                 MD5_Init(&m5);
 410
 411                 for (i = 0; i + CSUM_CHUNK <= len; i += CSUM_CHUNK) {
 412                         MD5_Update(&m5, (uchar *)map_ptr(buf, i, CSUM_CHUNK),
 413                                    CSUM_CHUNK);
 414                 }
 415
 416                 remainder = (int32)(len - i);
 417                 if (remainder > 0)
 418                         MD5_Update(&m5, (uchar *)map_ptr(buf, i, remainder), remainder);
 419
 420                 MD5_Final((uchar *)sum, &m5);
 421                 break;
 422           case CSUM_MD4:
 423           case CSUM_MD4_OLD:
 424           case CSUM_MD4_BUSTED:
 425           case CSUM_MD4_ARCHAIC:
 426                 mdfour_begin(&m);
 427
 428                 for (i = 0; i + CSUM_CHUNK <= len; i += CSUM_CHUNK) {
 429                         mdfour_update(&m, (uchar *)map_ptr(buf, i, CSUM_CHUNK), CSUM_CHUNK);
 430                 }
 431
 432                 /* Prior to version 27 an incorrect MD4 checksum was computed
 433                  * by failing to call mdfour_tail() for block sizes that
 434                  * are multiples of 64.  This is fixed by calling mdfour_update()
 435                  * even when there are no more bytes. */
 436                 remainder = (int32)(len - i);
 437                 if (remainder > 0 || checksum_type > CSUM_MD4_BUSTED)
 438                         mdfour_update(&m, (uchar *)map_ptr(buf, i, remainder), remainder);
 439
 440                 mdfour_result(&m, (uchar *)sum);
 441                 break;
 442 #ifdef SUPPORT_XXHASH
 443           case CSUM_XXHASH: {
 444                 XXH64_state_t* state = XXH64_createState();
 445                 if (state == NULL)
 446                         out_of_memory("file_checksum xx64");
 447
 448                 if (XXH64_reset(state, 0) == XXH_ERROR) {
 449                         rprintf(FERROR, "error resetting XXH64 seed");
 450                         exit_cleanup(RERR_STREAMIO);
 451                 }
 452
 453                 for (i = 0; i + CSUM_CHUNK <= len; i += CSUM_CHUNK) {
 454                         XXH_errorcode const updateResult =
 455                             XXH64_update(state, (uchar *)map_ptr(buf, i, CSUM_CHUNK), CSUM_CHUNK);
 456                         if (updateResult == XXH_ERROR) {
 457                                 rprintf(FERROR, "error computing XX64 hash");
 458                                 exit_cleanup(RERR_STREAMIO);
 459                         }
 460                 }
 461                 remainder = (int32)(len - i);
 462                 if (remainder > 0)
 463                         XXH64_update(state, (uchar *)map_ptr(buf, i, CSUM_CHUNK), remainder);
 464                 SIVAL64(sum, 0, XXH64_digest(state));
 465
 466                 XXH64_freeState(state);
 467                 break;
 468           }
 469 #endif
 470           default:
 471                 rprintf(FERROR, "invalid checksum-choice for the --checksum option (%d)\n", checksum_type);
 472                 exit_cleanup(RERR_UNSUPPORTED);
 473         }
 474
 475         close(fd);
 476         unmap_file(buf);
 477 }
 478
 479 static int32 sumresidue;
 480 static md_context md;
 481 static MD5_CTX m5;
 482 static int cursum_type;
 483 #ifdef SUPPORT_XXHASH
 484 XXH64_state_t* xxh64_state = NULL;
 485 #endif
 486
 487 void sum_init(int csum_type, int seed)
 488 {
 489         char s[4];
 490
 491         if (csum_type < 0)
 492                 csum_type = parse_csum_name(NULL, 0, 1);
 493         cursum_type = csum_type;
 494
 495         switch (csum_type) {
 496           case CSUM_MD5:
 497                 MD5_Init(&m5);
 498                 break;
 499           case CSUM_MD4:
 500                 mdfour_begin(&md);
 501                 sumresidue = 0;
 502                 break;
 503           case CSUM_MD4_OLD:
 504           case CSUM_MD4_BUSTED:
 505           case CSUM_MD4_ARCHAIC:
 506                 mdfour_begin(&md);
 507                 sumresidue = 0;
 508                 SIVAL(s, 0, seed);
 509                 sum_update(s, 4);
 510                 break;
 511 #ifdef SUPPORT_XXHASH
 512           case CSUM_XXHASH:
 513                 if (xxh64_state == NULL) {
 514                         xxh64_state = XXH64_createState();
 515                         if (xxh64_state == NULL)
 516                                 out_of_memory("sum_init xxh64");
 517                 }
 518                 if (XXH64_reset(xxh64_state, 0) == XXH_ERROR) {
 519                         rprintf(FERROR, "error resetting XXH64 state");
 520                         exit_cleanup(RERR_STREAMIO);
 521                 }
 522                 break;
 523 #endif
 524           case CSUM_NONE:
 525                 break;
 526           default: /* paranoia to prevent missing case values */
 527                 exit_cleanup(RERR_UNSUPPORTED);
 528         }
 529 }
 530
 531 /**
 532  * Feed data into an MD4 accumulator, md.  The results may be
 533  * retrieved using sum_end().  md is used for different purposes at
 534  * different points during execution.
 535  *
 536  * @todo Perhaps get rid of md and just pass in the address each time.
 537  * Very slightly clearer and slower.
 538  **/
 539 void sum_update(const char *p, int32 len)
 540 {
 541         switch (cursum_type) {
 542           case CSUM_MD5:
 543                 MD5_Update(&m5, (uchar *)p, len);
 544                 break;
 545           case CSUM_MD4:
 546           case CSUM_MD4_OLD:
 547           case CSUM_MD4_BUSTED:
 548           case CSUM_MD4_ARCHAIC:
 549                 if (len + sumresidue < CSUM_CHUNK) {
 550                         memcpy(md.buffer + sumresidue, p, len);
 551                         sumresidue += len;
 552                         break;
 553                 }
 554
 555                 if (sumresidue) {
 556                         int32 i = CSUM_CHUNK - sumresidue;
 557                         memcpy(md.buffer + sumresidue, p, i);
 558                         mdfour_update(&md, (uchar *)md.buffer, CSUM_CHUNK);
 559                         len -= i;
 560                         p += i;
 561                 }
 562
 563                 while (len >= CSUM_CHUNK) {
 564                         mdfour_update(&md, (uchar *)p, CSUM_CHUNK);
 565                         len -= CSUM_CHUNK;
 566                         p += CSUM_CHUNK;
 567                 }
 568
 569                 sumresidue = len;
 570                 if (sumresidue)
 571                         memcpy(md.buffer, p, sumresidue);
 572                 break;
 573 #ifdef SUPPORT_XXHASH
 574           case CSUM_XXHASH:
 575                 if (XXH64_update(xxh64_state, p, len) == XXH_ERROR) {
 576                         rprintf(FERROR, "error computing XX64 hash");
 577                         exit_cleanup(RERR_STREAMIO);
 578                 }
 579                 break;
 580 #endif
 581           case CSUM_NONE:
 582                 break;
 583           default: /* paranoia to prevent missing case values */
 584                 exit_cleanup(RERR_UNSUPPORTED);
 585         }
 586 }
 587
 588 /* NOTE: all the callers of sum_end() pass in a pointer to a buffer that is
 589  * MAX_DIGEST_LEN in size, so even if the csum-len is shorter that that (i.e.
 590  * CSUM_MD4_ARCHAIC), we don't have to worry about limiting the data we write
 591  * into the "sum" buffer. */
 592 int sum_end(char *sum)
 593 {
 594         switch (cursum_type) {
 595           case CSUM_MD5:
 596                 MD5_Final((uchar *)sum, &m5);
 597                 break;
 598           case CSUM_MD4:
 599           case CSUM_MD4_OLD:
 600                 mdfour_update(&md, (uchar *)md.buffer, sumresidue);
 601                 mdfour_result(&md, (uchar *)sum);
 602                 break;
 603           case CSUM_MD4_BUSTED:
 604           case CSUM_MD4_ARCHAIC:
 605                 if (sumresidue)
 606                         mdfour_update(&md, (uchar *)md.buffer, sumresidue);
 607                 mdfour_result(&md, (uchar *)sum);
 608                 break;
 609 #ifdef SUPPORT_XXHASH
 610           case CSUM_XXHASH:
 611                 SIVAL64(sum, 0, XXH64_digest(xxh64_state));
 612                 break;
 613 #endif
 614           case CSUM_NONE:
 615                 *sum = '\0';
 616                 break;
 617           default: /* paranoia to prevent missing case values */
 618                 exit_cleanup(RERR_UNSUPPORTED);
 619         }
 620
 621         return csum_len_for_type(cursum_type, 0);
 622 }