![[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|
Return to blocks.c CVS log | Up to [local] / src / usr.bin / rsync |
1.3 ! deraadt 1: /* $Id: blocks.c,v 1.2 2019/02/10 23:24:14 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:
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;
104: if (0 == memcmp(md,
105: blks->blks[hint].chksum_long, blks->csum)) {
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:
136: if (0 == have_md) {
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);
183: if (NULL == blk)
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.2 benno 241: int nfd, 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:
249: if (-1 == (nfd = open(path, O_RDONLY, 0))) {
250: ERR(sess, "%s: open", path);
251: return 0;
252: } else if (-1 == fstat(nfd, &st)) {
253: ERR(sess, "%s: fstat", path);
254: close(nfd);
255: return 0;
256: }
257:
258: /*
259: * We might possibly have a zero-length file, in which case the
260: * mmap() will fail, so only do this with non-zero files.
261: */
262:
263: if ((mapsz = st.st_size) > 0) {
264: map = mmap(NULL, mapsz, PROT_READ, MAP_SHARED, nfd, 0);
265: if (MAP_FAILED == map) {
266: ERR(sess, "%s: mmap", path);
267: close(nfd);
268: return 0;
269: }
270: }
271:
272: /*
273: * If the file's empty or we don't have any blocks from the
274: * sender, then simply send the whole file.
275: * Otherwise, run the hash matching routine and send raw chunks
276: * and subsequent matching tokens.
277: * This part broadly symmetrises blk_merge().
278: */
279:
280: if (st.st_size && blks->blksz) {
281: c = blk_match_send(sess, path,
282: fd, map, st.st_size, blks);
1.3 ! deraadt 283: if (!c) {
1.1 benno 284: ERRX1(sess, "blk_match_send");
285: goto out;
286: }
287: } else {
1.3 ! deraadt 288: if (!blk_flush(sess, fd, map, st.st_size, 0)) {
1.1 benno 289: ERRX1(sess, "blk_flush");
290: return 0;
291: }
292: LOG3(sess, "%s: flushed (un-chunked) %jd B, 100%% "
293: "upload ratio", path, (intmax_t)st.st_size);
294: }
295:
1.2 benno 296: /*
1.1 benno 297: * Now write the full file hash.
298: * Since we're seeding the hash, this always gives us some sort
299: * of data even if the file's zero-length.
300: */
301:
302: hash_file(map, st.st_size, filemd, sess);
303:
1.3 ! deraadt 304: if (!io_write_buf(sess, fd, filemd, MD4_DIGEST_LENGTH)) {
1.1 benno 305: ERRX1(sess, "io_write_buf");
306: goto out;
307: }
308:
309: rc = 1;
310: out:
311: if (MAP_FAILED != map)
312: munmap(map, mapsz);
313: close(nfd);
314: return rc;
315: }
316:
317: /* FIXME: remove. */
318: void
319: blkset_free(struct blkset *p)
320: {
321:
322: if (NULL == p)
323: return;
324: free(p->blks);
325: free(p);
326: }
327:
328: /*
329: * Sent from the sender to the receiver to indicate that the block set
330: * has been received.
331: * Symmetrises blk_send_ack().
332: * Returns zero on failure, non-zero on success.
333: */
334: int
335: blk_recv_ack(struct sess *sess,
336: int fd, const struct blkset *blocks, int32_t idx)
337: {
338:
339: /* FIXME: put into static block. */
340:
1.3 ! deraadt 341: if (!io_write_int(sess, fd, idx))
1.1 benno 342: ERRX1(sess, "io_write_int");
1.3 ! deraadt 343: else if (!io_write_int(sess, fd, blocks->blksz))
1.1 benno 344: ERRX1(sess, "io_write_int");
1.3 ! deraadt 345: else if (!io_write_int(sess, fd, blocks->len))
1.1 benno 346: ERRX1(sess, "io_write_int");
1.3 ! deraadt 347: else if (!io_write_int(sess, fd, blocks->csum))
1.1 benno 348: ERRX1(sess, "io_write_int");
1.3 ! deraadt 349: else if (!io_write_int(sess, fd, blocks->rem))
1.1 benno 350: ERRX1(sess, "io_write_int");
351: else
352: return 1;
353:
354: return 0;
355: }
356:
357: /*
358: * Read all of the checksums for a file's blocks.
359: * Returns the set of blocks or NULL on failure.
360: */
361: struct blkset *
362: blk_recv(struct sess *sess, int fd, const char *path)
363: {
364: struct blkset *s;
365: int32_t i;
366: size_t j;
367: struct blk *b;
368: off_t offs = 0;
369:
370: if (NULL == (s = calloc(1, sizeof(struct blkset)))) {
371: ERR(sess, "calloc");
372: return NULL;
373: }
374:
375: /*
376: * The block prologue consists of a few values that we'll need
377: * in reading the individual blocks for this file.
378: * FIXME: read into buffer and unbuffer.
379: */
380:
1.3 ! deraadt 381: if (!io_read_size(sess, fd, &s->blksz)) {
1.1 benno 382: ERRX1(sess, "io_read_size");
383: goto out;
1.3 ! deraadt 384: } else if (!io_read_size(sess, fd, &s->len)) {
1.1 benno 385: ERRX1(sess, "io_read_size");
386: goto out;
1.3 ! deraadt 387: } else if (!io_read_size(sess, fd, &s->csum)) {
1.1 benno 388: ERRX1(sess, "io_read_int");
389: goto out;
1.3 ! deraadt 390: } else if (!io_read_size(sess, fd, &s->rem)) {
1.1 benno 391: ERRX1(sess, "io_read_int");
392: goto out;
393: } else if (s->rem && s->rem >= s->len) {
394: ERRX(sess, "block remainder is "
395: "greater than block size");
396: goto out;
397: }
398:
399: LOG3(sess, "%s: read block prologue: %zu blocks of "
400: "%zu B, %zu B remainder, %zu B checksum", path,
401: s->blksz, s->len, s->rem, s->csum);
402:
403: if (s->blksz) {
404: s->blks = calloc(s->blksz, sizeof(struct blk));
405: if (NULL == s->blks) {
406: ERR(sess, "calloc");
407: goto out;
408: }
409: }
410:
1.2 benno 411: /*
1.1 benno 412: * Read each block individually.
413: * FIXME: read buffer and unbuffer.
414: */
415:
416: for (j = 0; j < s->blksz; j++) {
417: b = &s->blks[j];
1.3 ! deraadt 418: if (!io_read_int(sess, fd, &i)) {
1.1 benno 419: ERRX1(sess, "io_read_int");
420: goto out;
421: }
422: b->chksum_short = i;
423:
424: assert(s->csum <= sizeof(b->chksum_long));
1.3 ! deraadt 425: if (!io_read_buf(sess,
1.1 benno 426: fd, b->chksum_long, s->csum)) {
427: ERRX1(sess, "io_read_buf");
428: goto out;
429: }
430:
431: /*
432: * If we're the last block, then we're assigned the
433: * remainder of the data.
434: */
435:
436: b->offs = offs;
437: b->idx = j;
438: b->len = (j == (s->blksz - 1) && s->rem) ?
439: s->rem : s->len;
440: offs += b->len;
441:
442: LOG4(sess, "%s: read block %zu, "
443: "length %zu B", path, b->idx, b->len);
444: }
445:
446: s->size = offs;
447: LOG3(sess, "%s: read blocks: %zu blocks, %jd B total "
448: "blocked data", path, s->blksz, (intmax_t)s->size);
449: return s;
450: out:
451: blkset_free(s);
452: return NULL;
453: }
454:
455: /*
456: * Symmetrise blk_recv_ack(), except w/o the leading identifier.
457: * Return zero on failure, non-zero on success.
458: */
459: int
460: blk_send_ack(struct sess *sess, int fd, struct blkset *p)
461: {
462: char buf[16];
463: size_t pos = 0, sz;
464:
465: /* Put the entire send routine into a buffer. */
466:
467: sz = sizeof(int32_t) + /* block count */
468: sizeof(int32_t) + /* block length */
469: sizeof(int32_t) + /* checksum length */
470: sizeof(int32_t); /* block remainder */
471: assert(sz <= sizeof(buf));
472:
1.3 ! deraadt 473: if (!io_read_buf(sess, fd, buf, sz)) {
1.1 benno 474: ERRX1(sess, "io_read_buf");
475: return 0;
476: }
477:
1.3 ! deraadt 478: if (!io_unbuffer_size(sess, buf, &pos, sz, &p->blksz))
1.1 benno 479: ERRX1(sess, "io_unbuffer_size");
1.3 ! deraadt 480: else if (!io_unbuffer_size(sess, buf, &pos, sz, &p->len))
1.1 benno 481: ERRX1(sess, "io_unbuffer_size");
1.3 ! deraadt 482: else if (!io_unbuffer_size(sess, buf, &pos, sz, &p->csum))
1.1 benno 483: ERRX1(sess, "io_unbuffer_size");
1.3 ! deraadt 484: else if (!io_unbuffer_size(sess, buf, &pos, sz, &p->rem))
1.1 benno 485: ERRX1(sess, "io_unbuffer_size");
486: else if (p->len && p->rem >= p->len)
487: ERRX1(sess, "non-zero length is less than remainder");
488: else if (0 == p->csum || p->csum > 16)
489: ERRX1(sess, "inappropriate checksum length");
490: else
491: return 1;
492:
493: return 0;
494: }
495:
496: /*
497: * The receiver now reads raw data and block indices from the sender,
498: * and merges them into the temporary file.
499: * Returns zero on failure, non-zero on success.
500: */
501: int
502: blk_merge(struct sess *sess, int fd, int ffd,
503: const struct blkset *block, int outfd, const char *path,
504: const void *map, size_t mapsz, float *stats)
505: {
506: size_t sz, tok;
507: int32_t rawtok;
508: char *buf = NULL;
509: void *pp;
510: ssize_t ssz;
511: int rc = 0;
512: unsigned char md[MD4_DIGEST_LENGTH],
513: ourmd[MD4_DIGEST_LENGTH];
514: off_t total = 0, fromcopy = 0, fromdown = 0;
515: MD4_CTX ctx;
516:
517: MD4_Init(&ctx);
518:
519: rawtok = htole32(sess->seed);
520: MD4_Update(&ctx, (unsigned char *)&rawtok, sizeof(int32_t));
521:
522: for (;;) {
523: /*
524: * This matches the sequence in blk_flush().
525: * We read the size/token, then optionally the data.
526: * The size >0 for reading data, 0 for no more data, and
527: * <0 for a token indicator.
528: */
529:
1.3 ! deraadt 530: if (!io_read_int(sess, fd, &rawtok)) {
1.1 benno 531: ERRX1(sess, "io_read_int");
532: goto out;
533: } else if (0 == rawtok)
534: break;
535:
536: if (rawtok > 0) {
537: sz = rawtok;
538: if (NULL == (pp = realloc(buf, sz))) {
539: ERR(sess, "realloc");
540: goto out;
541: }
542: buf = pp;
1.3 ! deraadt 543: if (!io_read_buf(sess, fd, buf, sz)) {
1.1 benno 544: ERRX1(sess, "io_read_int");
545: goto out;
546: }
547:
548: if ((ssz = write(outfd, buf, sz)) < 0) {
549: ERR(sess, "write: temporary file");
550: goto out;
551: } else if ((size_t)ssz != sz) {
552: ERRX(sess, "write: short write");
553: goto out;
554: }
555:
556: fromdown += sz;
557: total += sz;
558: LOG4(sess, "%s: received %zd B block, now %jd "
559: "B total", path, ssz, (intmax_t)total);
560:
561: MD4_Update(&ctx, buf, sz);
562: } else {
563: tok = -rawtok - 1;
564: if (tok >= block->blksz) {
565: ERRX(sess, "token not in block set");
566: goto out;
567: }
568:
569: /*
570: * Now we read from our block.
571: * We should only be at this point if we have a
572: * block to read from, i.e., if we were able to
573: * map our origin file and create a block
574: * profile from it.
575: */
576:
577: assert(MAP_FAILED != map);
578:
579: ssz = write(outfd,
580: map + block->blks[tok].offs,
581: block->blks[tok].len);
582:
583: if (ssz < 0) {
584: ERR(sess, "write: temporary file");
585: goto out;
586: } else if ((size_t)ssz != block->blks[tok].len) {
587: ERRX(sess, "write: short write");
588: goto out;
589: }
590:
591: fromcopy += block->blks[tok].len;
592: total += block->blks[tok].len;
593: LOG4(sess, "%s: copied %zu B, now %jd "
594: "B total", path, block->blks[tok].len,
595: (intmax_t)total);
596:
597: MD4_Update(&ctx,
598: map + block->blks[tok].offs,
599: block->blks[tok].len);
600: }
601: }
602:
603:
604: /* Make sure our resulting MD4_ hashes match. */
605:
606: MD4_Final(ourmd, &ctx);
607:
1.3 ! deraadt 608: if (!io_read_buf(sess, fd, md, MD4_DIGEST_LENGTH)) {
1.1 benno 609: ERRX1(sess, "io_read_buf");
610: goto out;
611: } else if (memcmp(md, ourmd, MD4_DIGEST_LENGTH)) {
612: ERRX(sess, "%s: file hash does not match", path);
613: goto out;
614: }
615:
616: *stats = 100.0 * fromdown / total;
617: rc = 1;
618: out:
619: free(buf);
620: return rc;
621: }
622:
623: /*
624: * Transmit the metadata for set and blocks.
625: * Return zero on failure, non-zero on success.
626: */
627: int
628: blk_send(struct sess *sess, int fd, size_t idx,
629: const struct blkset *p, const char *path)
630: {
631: char *buf;
632: size_t i, pos = 0, sz;
633: int rc = 0;
634:
635: /* Put the entire send routine into a buffer. */
636:
637: sz = sizeof(int32_t) + /* identifier */
1.2 benno 638: sizeof(int32_t) + /* block count */
639: sizeof(int32_t) + /* block length */
640: sizeof(int32_t) + /* checksum length */
641: sizeof(int32_t) + /* block remainder */
642: p->blksz *
643: (sizeof(int32_t) + /* short checksum */
644: p->csum); /* long checksum */
1.1 benno 645:
646: if (NULL == (buf = malloc(sz))) {
647: ERR(sess, "malloc");
648: return 0;
649: }
650:
651: io_buffer_int(sess, buf, &pos, sz, idx);
652: io_buffer_int(sess, buf, &pos, sz, p->blksz);
653: io_buffer_int(sess, buf, &pos, sz, p->len);
654: io_buffer_int(sess, buf, &pos, sz, p->csum);
655: io_buffer_int(sess, buf, &pos, sz, p->rem);
656:
657: for (i = 0; i < p->blksz; i++) {
1.2 benno 658: io_buffer_int(sess, buf, &pos,
1.1 benno 659: sz, p->blks[i].chksum_short);
1.2 benno 660: io_buffer_buf(sess, buf, &pos, sz,
1.1 benno 661: p->blks[i].chksum_long, p->csum);
662: }
663:
664: assert(pos == sz);
665:
1.3 ! deraadt 666: if (!io_write_buf(sess, fd, buf, sz)) {
1.1 benno 667: ERRX1(sess, "io_write_buf");
668: goto out;
669: }
670:
671: LOG3(sess, "%s: sent block prologue: %zu blocks of %zu B, "
672: "%zu B remainder, %zu B checksum", path,
673: p->blksz, p->len, p->rem, p->csum);
674: rc = 1;
675: out:
676: free(buf);
677: return rc;
678: }