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