Annotation of src/usr.bin/rsync/blocks.c, Revision 1.6
1.6 ! tb 1: /* $Id: blocks.c,v 1.5 2019/02/11 22:22:52 benno Exp $ */
1.1 benno 2: /*
3: * Copyright (c) 2019 Kristaps Dzonsons <kristaps@bsd.lv>
4: *
5: * Permission to use, copy, modify, and distribute this software for any
6: * purpose with or without fee is hereby granted, provided that the above
7: * copyright notice and this permission notice appear in all copies.
8: *
9: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16: */
17: #include <sys/mman.h>
18: #include <sys/stat.h>
19:
20: #include <assert.h>
21: #include <endian.h>
22: #include <errno.h>
23: #include <fcntl.h>
24: #include <inttypes.h>
25: #include <stdio.h>
26: #include <stdlib.h>
27: #include <string.h>
28: #include <unistd.h>
29:
1.6 ! tb 30: #include <openssl/md4.h>
! 31:
1.1 benno 32: #include "extern.h"
33:
34: /*
35: * Flush out "size" bytes of the buffer, doing all of the appropriate
36: * chunking of the data, then the subsequent token (or zero).
37: * This is symmetrised in blk_merge().
38: * Return zero on failure, non-zero on success.
39: */
40: static int
41: blk_flush(struct sess *sess, int fd,
42: const void *b, off_t size, int32_t token)
43: {
44: off_t i = 0, sz;
45:
46: while (i < size) {
47: sz = MAX_CHUNK < (size - i) ?
48: MAX_CHUNK : (size - i);
1.3 deraadt 49: if (!io_write_int(sess, fd, sz)) {
1.1 benno 50: ERRX1(sess, "io_write_int");
51: return 0;
1.3 deraadt 52: } else if (!io_write_buf(sess, fd, b + i, sz)) {
1.1 benno 53: ERRX1(sess, "io_write_buf");
54: return 0;
55: }
56: i += sz;
57: }
58:
1.3 deraadt 59: if (!io_write_int(sess, fd, token)) {
1.1 benno 60: ERRX1(sess, "io_write_int");
61: return 0;
62: }
63:
64: return 1;
65: }
66:
67: /*
68: * From our current position of "offs" in buffer "buf" of total size
69: * "size", see if we can find a matching block in our list of blocks.
70: * The "hint" refers to the block that *might* work.
71: * Returns the blk or NULL if no matching block was found.
72: */
73: static struct blk *
74: blk_find(struct sess *sess, const void *buf, off_t size, off_t offs,
75: const struct blkset *blks, const char *path, size_t hint)
76: {
77: unsigned char md[MD4_DIGEST_LENGTH];
78: uint32_t fhash;
79: off_t remain, osz;
80: size_t i;
81: int have_md = 0;
82:
83: /*
84: * First, compute our fast hash.
85: * FIXME: yes, this can be a rolling computation, but I'm
86: * deliberately making it simple first.
87: */
88:
89: remain = size - offs;
90: assert(remain);
91: osz = remain < (off_t)blks->len ? remain : (off_t)blks->len;
92: fhash = hash_fast(buf + offs, (size_t)osz);
93: have_md = 0;
94:
95: /*
96: * Start with our match hint.
97: * This just runs the fast and slow check with the hint.
98: */
99:
100: if (hint < blks->blksz &&
101: fhash == blks->blks[hint].chksum_short &&
102: (size_t)osz == blks->blks[hint].len) {
103: hash_slow(buf + offs, (size_t)osz, md, sess);
104: have_md = 1;
1.4 deraadt 105: if (memcmp(md, blks->blks[hint].chksum_long, blks->csum) == 0) {
1.1 benno 106: LOG4(sess, "%s: found matching hinted match: "
107: "position %jd, block %zu "
108: "(position %jd, size %zu)", path,
109: (intmax_t)offs, blks->blks[hint].idx,
110: (intmax_t)blks->blks[hint].offs,
111: blks->blks[hint].len);
112: return &blks->blks[hint];
113: }
114: }
115:
116: /*
117: * Now loop and look for the fast hash.
118: * If it's found, move on to the slow hash.
119: */
120:
121: for (i = 0; i < blks->blksz; i++) {
122: if (fhash != blks->blks[i].chksum_short)
123: continue;
124: if ((size_t)osz != blks->blks[i].len)
125: continue;
126:
127: LOG4(sess, "%s: found matching fast match: "
128: "position %jd, block %zu "
129: "(position %jd, size %zu)", path,
130: (intmax_t)offs, blks->blks[i].idx,
131: (intmax_t)blks->blks[i].offs,
132: blks->blks[i].len);
133:
134: /* Compute slow hash on demand. */
135:
1.4 deraadt 136: if (have_md == 0) {
1.1 benno 137: hash_slow(buf + offs, (size_t)osz, md, sess);
138: have_md = 1;
139: }
140:
141: if (memcmp(md, blks->blks[i].chksum_long, blks->csum))
142: continue;
143:
144: LOG4(sess, "%s: sender verifies slow match", path);
145: return &blks->blks[i];
146: }
147:
148: return NULL;
149: }
150:
151: /*
152: * The main reconstruction algorithm on the sender side.
153: * Scans byte-wise over the input file, looking for matching blocks in
154: * what the server sent us.
155: * If a block is found, emit all data up until the block, then the token
156: * for the block.
157: * The receiving end can then reconstruct the file trivially.
158: * Return zero on failure, non-zero on success.
159: */
160: static int
161: blk_match_send(struct sess *sess, const char *path, int fd,
162: const void *buf, off_t size, const struct blkset *blks)
163: {
1.2 benno 164: off_t offs, last, end, fromcopy = 0, fromdown = 0,
1.1 benno 165: total = 0, sz;
166: int32_t tok;
167: struct blk *blk;
168: size_t hint = 0;
169:
170: /*
171: * Stop searching at the length of the file minus the size of
172: * the last block.
173: * The reason for this being that we don't need to do an
174: * incremental hash within the last block---if it doesn't match,
175: * it doesn't match.
176: */
177:
178: end = size + 1 - blks->blks[blks->blksz - 1].len;
179:
180: for (last = offs = 0; offs < end; offs++) {
181: blk = blk_find(sess, buf, size,
182: offs, blks, path, hint);
1.4 deraadt 183: if (blk == NULL)
1.1 benno 184: continue;
185:
186: sz = offs - last;
187: fromdown += sz;
188: total += sz;
189: LOG4(sess, "%s: flushing %jd B before %zu B "
190: "block %zu", path, (intmax_t)sz, blk->len,
191: blk->idx);
192: tok = -(blk->idx + 1);
193:
194: /*
195: * Write the data we have, then follow it with the tag
196: * of the block that matches.
197: * The receiver will then write our data, then the data
198: * it already has in the matching block.
199: */
200:
1.3 deraadt 201: if (!blk_flush(sess, fd, buf + last, sz, tok)) {
1.1 benno 202: ERRX1(sess, "blk_flush");
203: return 0;
204: }
205:
206: fromcopy += blk->len;
207: total += blk->len;
208: offs += blk->len - 1;
209: last = offs + 1;
210: hint = blk->idx + 1;
211: }
212:
213: /* Emit remaining data and send terminator token. */
214:
215: sz = size - last;
216: total += sz;
217: fromdown += sz;
218:
219: LOG4(sess, "%s: flushing remaining %jd B", path, (intmax_t)sz);
220:
1.3 deraadt 221: if (!blk_flush(sess, fd, buf + last, sz, 0)) {
1.1 benno 222: ERRX1(sess, "blk_flush");
223: return 0;
224: }
225:
226: LOG3(sess, "%s: flushed (chunked) %jd B total, "
227: "%.2f%% upload ratio", path, (intmax_t)total,
228: 100.0 * fromdown / total);
229: return 1;
230: }
231:
232: /*
233: * Given a local file "path" and the blocks created by a remote machine,
234: * find out which blocks of our file they don't have and send them.
235: * Return zero on failure, non-zero on success.
236: */
237: int
238: blk_match(struct sess *sess, int fd,
239: const struct blkset *blks, const char *path)
240: {
1.5 benno 241: int nfd = -1, rc = 0, c;
1.1 benno 242: struct stat st;
243: void *map = MAP_FAILED;
244: size_t mapsz;
245: unsigned char filemd[MD4_DIGEST_LENGTH];
246:
247: /* Start by mapping our file into memory. */
248:
1.4 deraadt 249: if ((nfd = open(path, O_RDONLY, 0)) == -1) {
1.1 benno 250: ERR(sess, "%s: open", path);
1.5 benno 251: goto out;
1.4 deraadt 252: } else if (fstat(nfd, &st) == -1) {
1.1 benno 253: ERR(sess, "%s: fstat", path);
1.5 benno 254: goto out;
1.1 benno 255: }
256:
257: /*
258: * We might possibly have a zero-length file, in which case the
259: * mmap() will fail, so only do this with non-zero files.
260: */
261:
262: if ((mapsz = st.st_size) > 0) {
263: map = mmap(NULL, mapsz, PROT_READ, MAP_SHARED, nfd, 0);
1.4 deraadt 264: if (map == MAP_FAILED) {
1.1 benno 265: ERR(sess, "%s: mmap", path);
1.5 benno 266: goto out;
1.1 benno 267: }
268: }
269:
270: /*
271: * If the file's empty or we don't have any blocks from the
272: * sender, then simply send the whole file.
273: * Otherwise, run the hash matching routine and send raw chunks
274: * and subsequent matching tokens.
275: * This part broadly symmetrises blk_merge().
276: */
277:
278: if (st.st_size && blks->blksz) {
1.5 benno 279: c = blk_match_send(sess, path, fd, map, st.st_size, blks);
1.3 deraadt 280: if (!c) {
1.1 benno 281: ERRX1(sess, "blk_match_send");
282: goto out;
283: }
284: } else {
1.3 deraadt 285: if (!blk_flush(sess, fd, map, st.st_size, 0)) {
1.1 benno 286: ERRX1(sess, "blk_flush");
1.5 benno 287: goto out;
1.1 benno 288: }
1.5 benno 289: LOG3(sess, "%s: flushed (un-chunked) %jd B, 100%% upload ratio",
290: path, (intmax_t)st.st_size);
1.1 benno 291: }
292:
1.2 benno 293: /*
1.1 benno 294: * Now write the full file hash.
295: * Since we're seeding the hash, this always gives us some sort
296: * of data even if the file's zero-length.
297: */
298:
299: hash_file(map, st.st_size, filemd, sess);
300:
1.3 deraadt 301: if (!io_write_buf(sess, fd, filemd, MD4_DIGEST_LENGTH)) {
1.1 benno 302: ERRX1(sess, "io_write_buf");
303: goto out;
304: }
305:
306: rc = 1;
307: out:
1.4 deraadt 308: if (map != MAP_FAILED)
1.1 benno 309: munmap(map, mapsz);
1.5 benno 310: if (-1 != nfd)
311: close(nfd);
1.1 benno 312: return rc;
313: }
314:
315: /* FIXME: remove. */
316: void
317: blkset_free(struct blkset *p)
318: {
319:
1.4 deraadt 320: if (p == NULL)
1.1 benno 321: return;
322: free(p->blks);
323: free(p);
324: }
325:
326: /*
327: * Sent from the sender to the receiver to indicate that the block set
328: * has been received.
329: * Symmetrises blk_send_ack().
330: * Returns zero on failure, non-zero on success.
331: */
332: int
333: blk_recv_ack(struct sess *sess,
334: int fd, const struct blkset *blocks, int32_t idx)
335: {
336:
337: /* FIXME: put into static block. */
338:
1.3 deraadt 339: if (!io_write_int(sess, fd, idx))
1.1 benno 340: ERRX1(sess, "io_write_int");
1.3 deraadt 341: else if (!io_write_int(sess, fd, blocks->blksz))
1.1 benno 342: ERRX1(sess, "io_write_int");
1.3 deraadt 343: else if (!io_write_int(sess, fd, blocks->len))
1.1 benno 344: ERRX1(sess, "io_write_int");
1.3 deraadt 345: else if (!io_write_int(sess, fd, blocks->csum))
1.1 benno 346: ERRX1(sess, "io_write_int");
1.3 deraadt 347: else if (!io_write_int(sess, fd, blocks->rem))
1.1 benno 348: ERRX1(sess, "io_write_int");
349: else
350: return 1;
351:
352: return 0;
353: }
354:
355: /*
356: * Read all of the checksums for a file's blocks.
357: * Returns the set of blocks or NULL on failure.
358: */
359: struct blkset *
360: blk_recv(struct sess *sess, int fd, const char *path)
361: {
362: struct blkset *s;
363: int32_t i;
364: size_t j;
365: struct blk *b;
366: off_t offs = 0;
367:
1.4 deraadt 368: if ((s = calloc(1, sizeof(struct blkset))) == NULL) {
1.1 benno 369: ERR(sess, "calloc");
370: return NULL;
371: }
372:
373: /*
374: * The block prologue consists of a few values that we'll need
375: * in reading the individual blocks for this file.
376: * FIXME: read into buffer and unbuffer.
377: */
378:
1.3 deraadt 379: if (!io_read_size(sess, fd, &s->blksz)) {
1.1 benno 380: ERRX1(sess, "io_read_size");
381: goto out;
1.3 deraadt 382: } else if (!io_read_size(sess, fd, &s->len)) {
1.1 benno 383: ERRX1(sess, "io_read_size");
384: goto out;
1.3 deraadt 385: } else if (!io_read_size(sess, fd, &s->csum)) {
1.1 benno 386: ERRX1(sess, "io_read_int");
387: goto out;
1.3 deraadt 388: } else if (!io_read_size(sess, fd, &s->rem)) {
1.1 benno 389: ERRX1(sess, "io_read_int");
390: goto out;
391: } else if (s->rem && s->rem >= s->len) {
392: ERRX(sess, "block remainder is "
393: "greater than block size");
394: goto out;
395: }
396:
397: LOG3(sess, "%s: read block prologue: %zu blocks of "
398: "%zu B, %zu B remainder, %zu B checksum", path,
399: s->blksz, s->len, s->rem, s->csum);
400:
401: if (s->blksz) {
402: s->blks = calloc(s->blksz, sizeof(struct blk));
1.4 deraadt 403: if (s->blks == NULL) {
1.1 benno 404: ERR(sess, "calloc");
405: goto out;
406: }
407: }
408:
1.2 benno 409: /*
1.1 benno 410: * Read each block individually.
411: * FIXME: read buffer and unbuffer.
412: */
413:
414: for (j = 0; j < s->blksz; j++) {
415: b = &s->blks[j];
1.3 deraadt 416: if (!io_read_int(sess, fd, &i)) {
1.1 benno 417: ERRX1(sess, "io_read_int");
418: goto out;
419: }
420: b->chksum_short = i;
421:
422: assert(s->csum <= sizeof(b->chksum_long));
1.3 deraadt 423: if (!io_read_buf(sess,
1.1 benno 424: fd, b->chksum_long, s->csum)) {
425: ERRX1(sess, "io_read_buf");
426: goto out;
427: }
428:
429: /*
430: * If we're the last block, then we're assigned the
431: * remainder of the data.
432: */
433:
434: b->offs = offs;
435: b->idx = j;
436: b->len = (j == (s->blksz - 1) && s->rem) ?
437: s->rem : s->len;
438: offs += b->len;
439:
440: LOG4(sess, "%s: read block %zu, "
441: "length %zu B", path, b->idx, b->len);
442: }
443:
444: s->size = offs;
445: LOG3(sess, "%s: read blocks: %zu blocks, %jd B total "
446: "blocked data", path, s->blksz, (intmax_t)s->size);
447: return s;
448: out:
449: blkset_free(s);
450: return NULL;
451: }
452:
453: /*
454: * Symmetrise blk_recv_ack(), except w/o the leading identifier.
455: * Return zero on failure, non-zero on success.
456: */
457: int
458: blk_send_ack(struct sess *sess, int fd, struct blkset *p)
459: {
460: char buf[16];
461: size_t pos = 0, sz;
462:
463: /* Put the entire send routine into a buffer. */
464:
465: sz = sizeof(int32_t) + /* block count */
466: sizeof(int32_t) + /* block length */
467: sizeof(int32_t) + /* checksum length */
468: sizeof(int32_t); /* block remainder */
469: assert(sz <= sizeof(buf));
470:
1.3 deraadt 471: if (!io_read_buf(sess, fd, buf, sz)) {
1.1 benno 472: ERRX1(sess, "io_read_buf");
473: return 0;
474: }
475:
1.3 deraadt 476: if (!io_unbuffer_size(sess, buf, &pos, sz, &p->blksz))
1.1 benno 477: ERRX1(sess, "io_unbuffer_size");
1.3 deraadt 478: else if (!io_unbuffer_size(sess, buf, &pos, sz, &p->len))
1.1 benno 479: ERRX1(sess, "io_unbuffer_size");
1.3 deraadt 480: else if (!io_unbuffer_size(sess, buf, &pos, sz, &p->csum))
1.1 benno 481: ERRX1(sess, "io_unbuffer_size");
1.3 deraadt 482: else if (!io_unbuffer_size(sess, buf, &pos, sz, &p->rem))
1.1 benno 483: ERRX1(sess, "io_unbuffer_size");
484: else if (p->len && p->rem >= p->len)
485: ERRX1(sess, "non-zero length is less than remainder");
1.4 deraadt 486: else if (p->csum == 0 || p->csum > 16)
1.1 benno 487: ERRX1(sess, "inappropriate checksum length");
488: else
489: return 1;
490:
491: return 0;
492: }
493:
494: /*
495: * The receiver now reads raw data and block indices from the sender,
496: * and merges them into the temporary file.
497: * Returns zero on failure, non-zero on success.
498: */
499: int
500: blk_merge(struct sess *sess, int fd, int ffd,
501: const struct blkset *block, int outfd, const char *path,
502: const void *map, size_t mapsz, float *stats)
503: {
504: size_t sz, tok;
505: int32_t rawtok;
506: char *buf = NULL;
507: void *pp;
508: ssize_t ssz;
509: int rc = 0;
510: unsigned char md[MD4_DIGEST_LENGTH],
511: ourmd[MD4_DIGEST_LENGTH];
512: off_t total = 0, fromcopy = 0, fromdown = 0;
513: MD4_CTX ctx;
514:
515: MD4_Init(&ctx);
516:
517: rawtok = htole32(sess->seed);
518: MD4_Update(&ctx, (unsigned char *)&rawtok, sizeof(int32_t));
519:
520: for (;;) {
521: /*
522: * This matches the sequence in blk_flush().
523: * We read the size/token, then optionally the data.
524: * The size >0 for reading data, 0 for no more data, and
525: * <0 for a token indicator.
526: */
527:
1.3 deraadt 528: if (!io_read_int(sess, fd, &rawtok)) {
1.1 benno 529: ERRX1(sess, "io_read_int");
530: goto out;
1.4 deraadt 531: } else if (rawtok == 0)
1.1 benno 532: break;
533:
534: if (rawtok > 0) {
535: sz = rawtok;
1.4 deraadt 536: if ((pp = realloc(buf, sz)) == NULL) {
1.1 benno 537: ERR(sess, "realloc");
538: goto out;
539: }
540: buf = pp;
1.3 deraadt 541: if (!io_read_buf(sess, fd, buf, sz)) {
1.1 benno 542: ERRX1(sess, "io_read_int");
543: goto out;
544: }
545:
546: if ((ssz = write(outfd, buf, sz)) < 0) {
547: ERR(sess, "write: temporary file");
548: goto out;
549: } else if ((size_t)ssz != sz) {
550: ERRX(sess, "write: short write");
551: goto out;
552: }
553:
554: fromdown += sz;
555: total += sz;
556: LOG4(sess, "%s: received %zd B block, now %jd "
557: "B total", path, ssz, (intmax_t)total);
558:
559: MD4_Update(&ctx, buf, sz);
560: } else {
561: tok = -rawtok - 1;
562: if (tok >= block->blksz) {
563: ERRX(sess, "token not in block set");
564: goto out;
565: }
566:
567: /*
568: * Now we read from our block.
569: * We should only be at this point if we have a
570: * block to read from, i.e., if we were able to
571: * map our origin file and create a block
572: * profile from it.
573: */
574:
1.4 deraadt 575: assert(map != MAP_FAILED);
1.1 benno 576:
577: ssz = write(outfd,
578: map + block->blks[tok].offs,
579: block->blks[tok].len);
580:
581: if (ssz < 0) {
582: ERR(sess, "write: temporary file");
583: goto out;
584: } else if ((size_t)ssz != block->blks[tok].len) {
585: ERRX(sess, "write: short write");
586: goto out;
587: }
588:
589: fromcopy += block->blks[tok].len;
590: total += block->blks[tok].len;
591: LOG4(sess, "%s: copied %zu B, now %jd "
592: "B total", path, block->blks[tok].len,
593: (intmax_t)total);
594:
1.4 deraadt 595: MD4_Update(&ctx, map + block->blks[tok].offs,
596: block->blks[tok].len);
1.1 benno 597: }
598: }
599:
600:
601: /* Make sure our resulting MD4_ hashes match. */
602:
603: MD4_Final(ourmd, &ctx);
604:
1.3 deraadt 605: if (!io_read_buf(sess, fd, md, MD4_DIGEST_LENGTH)) {
1.1 benno 606: ERRX1(sess, "io_read_buf");
607: goto out;
608: } else if (memcmp(md, ourmd, MD4_DIGEST_LENGTH)) {
609: ERRX(sess, "%s: file hash does not match", path);
610: goto out;
611: }
612:
613: *stats = 100.0 * fromdown / total;
614: rc = 1;
615: out:
616: free(buf);
617: return rc;
618: }
619:
620: /*
621: * Transmit the metadata for set and blocks.
622: * Return zero on failure, non-zero on success.
623: */
624: int
625: blk_send(struct sess *sess, int fd, size_t idx,
626: const struct blkset *p, const char *path)
627: {
628: char *buf;
629: size_t i, pos = 0, sz;
630: int rc = 0;
631:
632: /* Put the entire send routine into a buffer. */
633:
634: sz = sizeof(int32_t) + /* identifier */
1.2 benno 635: sizeof(int32_t) + /* block count */
636: sizeof(int32_t) + /* block length */
637: sizeof(int32_t) + /* checksum length */
638: sizeof(int32_t) + /* block remainder */
639: p->blksz *
640: (sizeof(int32_t) + /* short checksum */
641: p->csum); /* long checksum */
1.1 benno 642:
1.4 deraadt 643: if ((buf = malloc(sz)) == NULL) {
1.1 benno 644: ERR(sess, "malloc");
645: return 0;
646: }
647:
648: io_buffer_int(sess, buf, &pos, sz, idx);
649: io_buffer_int(sess, buf, &pos, sz, p->blksz);
650: io_buffer_int(sess, buf, &pos, sz, p->len);
651: io_buffer_int(sess, buf, &pos, sz, p->csum);
652: io_buffer_int(sess, buf, &pos, sz, p->rem);
653:
654: for (i = 0; i < p->blksz; i++) {
1.2 benno 655: io_buffer_int(sess, buf, &pos,
1.1 benno 656: sz, p->blks[i].chksum_short);
1.2 benno 657: io_buffer_buf(sess, buf, &pos, sz,
1.1 benno 658: p->blks[i].chksum_long, p->csum);
659: }
660:
661: assert(pos == sz);
662:
1.3 deraadt 663: if (!io_write_buf(sess, fd, buf, sz)) {
1.1 benno 664: ERRX1(sess, "io_write_buf");
665: goto out;
666: }
667:
668: LOG3(sess, "%s: sent block prologue: %zu blocks of %zu B, "
669: "%zu B remainder, %zu B checksum", path,
670: p->blksz, p->len, p->rem, p->csum);
671: rc = 1;
672: out:
673: free(buf);
674: return rc;
675: }