1/* $OpenBSD: blocks.c,v 1.23 2024/02/28 09:36:11 claudio Exp $ */ 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/queue.h> 18#include <sys/stat.h> 19 20#include <assert.h> 21#include <endian.h> 22#include <errno.h> 23#include <inttypes.h> 24#include <stdio.h> 25#include <stdlib.h> 26#include <string.h> 27#include <unistd.h> 28 29#include <openssl/md4.h> 30 31#include "extern.h" 32 33struct blkhash { 34 const struct blk *blk; 35 TAILQ_ENTRY(blkhash) entries; 36}; 37 38TAILQ_HEAD(blkhashq, blkhash); 39 40/* 41 * Table used by the sender for looking up blocks. 42 * The blocks are those sent by the receiver; we're looking up using 43 * hashes computed from our local file. 44 */ 45struct blktab { 46 struct blkhashq *q; /* entries in the hashtable */ 47 size_t qsz; /* size of the hashtable */ 48 struct blkhash *blks; /* pre-allocated hashtable entries */ 49}; 50 51/* 52 * This is the number of buckets in the hashtable. 53 * Use the same that GPL rsync uses. 54 * (It should be dynamic?) 55 */ 56#define BLKTAB_SZ 65536 57 58/* 59 * Initialise an empty hashtable with BLKTAB_SZ entries in it. 60 * Populate it for each file with blkhash_set. 61 * When we've processed all files, call blkhash_free. 62 * Returns NULL on allocation failure. 63 */ 64struct blktab * 65blkhash_alloc(void) 66{ 67 struct blktab *p; 68 69 if ((p = calloc(1, sizeof(struct blktab))) == NULL) { 70 ERR("calloc"); 71 return NULL; 72 } 73 p->qsz = BLKTAB_SZ; 74 p->q = calloc(p->qsz, sizeof(struct blkhashq)); 75 if (p->q == NULL) { 76 ERR("calloc"); 77 free(p); 78 return NULL; 79 } 80 return p; 81} 82 83/* 84 * Populate the hashtable with an incoming file's blocks. 85 * This will clear out any existing hashed data. 86 * Returns zero on allocation failure, non-zero otherwise. 87 */ 88int 89blkhash_set(struct blktab *p, const struct blkset *bset) 90{ 91 size_t i, idx; 92 93 if (bset == NULL) 94 return 1; 95 96 /* Wipe clean the table. */ 97 98 for (i = 0; i < p->qsz; i++) 99 TAILQ_INIT(&p->q[i]); 100 101 /* Fill in the hashtable. */ 102 103 p->blks = reallocarray(p->blks, bset->blksz, sizeof(struct blkhash)); 104 if (p->blks == NULL) { 105 ERR("reallocarray"); 106 return 0; 107 } 108 for (i = 0; i < bset->blksz; i++) { 109 p->blks[i].blk = &bset->blks[i]; 110 idx = bset->blks[i].chksum_short % p->qsz; 111 assert(idx < p->qsz); 112 TAILQ_INSERT_TAIL(&p->q[idx], &p->blks[i], entries); 113 } 114 115 return 1; 116} 117 118/* 119 * Free as allocated with blkhash_alloc(). 120 */ 121void 122blkhash_free(struct blktab *p) 123{ 124 125 free(p->blks); 126 free(p); 127} 128 129/* 130 * From our current position of "offs" in buffer "buf" of total size 131 * "size", see if we can find a matching block in our list of blocks. 132 * The "hint" refers to the block that *might* work. 133 * Returns the blk or NULL if no matching block was found. 134 */ 135static const struct blk * 136blk_find(struct sess *sess, struct blkstat *st, 137 const struct blkset *blks, const char *path, int recomp) 138{ 139 unsigned char md[MD4_DIGEST_LENGTH]; 140 uint32_t fhash; 141 off_t remain, osz; 142 int have_md = 0; 143 char *map; 144 const struct blkhashq *q; 145 const struct blkhash *ent; 146 147 remain = st->mapsz - st->offs; 148 assert(remain); 149 osz = MINIMUM(remain, (off_t)blks->len); 150 151 /* 152 * First, compute our fast hash the hard way (if we're 153 * reentering this function from a previous block match, or the 154 * first time) or from our existing s1 and s2 values. 155 */ 156 157 if (!recomp) { 158 fhash = (st->s1 & 0xFFFF) | (st->s2 << 16); 159 } else { 160 fhash = hash_fast(st->map + st->offs, (size_t)osz); 161 st->s1 = fhash & 0xFFFF; 162 st->s2 = fhash >> 16; 163 } 164 165 /* 166 * Start with our match hint. 167 * This just runs the fast and slow check with the hint. 168 */ 169 170 if (st->hint < blks->blksz && 171 fhash == blks->blks[st->hint].chksum_short && 172 (size_t)osz == blks->blks[st->hint].len) { 173 hash_slow(st->map + st->offs, (size_t)osz, md, sess); 174 have_md = 1; 175 if (memcmp(md, blks->blks[st->hint].chksum_long, blks->csum) == 0) { 176 LOG4("%s: found matching hinted match: " 177 "position %jd, block %zu (position %jd, size %zu)", 178 path, 179 (intmax_t)st->offs, blks->blks[st->hint].idx, 180 (intmax_t)blks->blks[st->hint].offs, 181 blks->blks[st->hint].len); 182 return &blks->blks[st->hint]; 183 } 184 } 185 186 /* 187 * Look for the fast hash modulus in our hashtable, filter for 188 * those matching the full hash and length, then move to the 189 * slow hash. 190 * The slow hash is computed only once. 191 */ 192 193 q = &st->blktab->q[fhash % st->blktab->qsz]; 194 195 TAILQ_FOREACH(ent, q, entries) { 196 if (fhash != ent->blk->chksum_short || 197 (size_t)osz != ent->blk->len) 198 continue; 199 200 LOG4("%s: found matching fast match: " 201 "position %jd, block %zu (position %jd, size %zu)", 202 path, (intmax_t)st->offs, ent->blk->idx, 203 (intmax_t)ent->blk->offs, ent->blk->len); 204 205 if (have_md == 0) { 206 hash_slow(st->map + st->offs, (size_t)osz, md, sess); 207 have_md = 1; 208 } 209 210 if (memcmp(md, ent->blk->chksum_long, blks->csum)) 211 continue; 212 213 LOG4("%s: sender verifies slow match", path); 214 return ent->blk; 215 } 216 217 /* 218 * Adjust our partial sums for the hashing. 219 * We first remove the first byte from the sum. 220 * We then, if we have space, add the first byte of the next 221 * block in the sequence. 222 */ 223 224 map = st->map + st->offs; 225 st->s1 -= map[0]; 226 st->s2 -= osz * map[0]; 227 228 if (osz < remain) { 229 st->s1 += map[osz]; 230 st->s2 += st->s1; 231 } 232 233 return NULL; 234} 235 236/* 237 * Given a local file "path" and the blocks created by a remote machine, 238 * find out which blocks of our file they don't have and send them. 239 * This function is reentrant: it must be called while there's still 240 * data to send. 241 */ 242void 243blk_match(struct sess *sess, const struct blkset *blks, 244 const char *path, struct blkstat *st) 245{ 246 off_t last, end = 0, sz; 247 int32_t tok; 248 size_t i; 249 const struct blk *blk; 250 251 /* 252 * If the file's empty or we don't have any blocks from the 253 * sender, then simply send the whole file. 254 * Otherwise, run the hash matching routine and send raw chunks 255 * and subsequent matching tokens. 256 */ 257 258 if (st->mapsz && blks->blksz) { 259 /* 260 * Stop searching at the length of the file minus the 261 * size of the last block. 262 * The reason for this being that we don't need to do an 263 * incremental hash within the last block---if it 264 * doesn't match, it doesn't match. 265 */ 266 267 end = st->mapsz + 1 - blks->blks[blks->blksz - 1].len; 268 } 269 270 last = st->offs; 271 for (i = 0; st->offs < end; st->offs++, i++) { 272 blk = blk_find(sess, st, blks, path, i == 0); 273 if (blk == NULL) 274 continue; 275 276 sz = st->offs - last; 277 st->dirty += sz; 278 st->total += sz; 279 LOG4("%s: flushing %jd B before %zu B block %zu", 280 path, (intmax_t)sz, 281 blk->len, blk->idx); 282 tok = -(blk->idx + 1); 283 284 hash_file_buf(&st->ctx, st->map + last, sz + blk->len); 285 286 /* 287 * Write the data we have, then follow it with 288 * the tag of the block that matches. 289 */ 290 291 st->curpos = last; 292 st->curlen = st->curpos + sz; 293 st->curtok = tok; 294 assert(st->curtok != 0); 295 st->curst = sz ? BLKSTAT_DATA : BLKSTAT_TOK; 296 st->total += blk->len; 297 st->offs += blk->len; 298 st->hint = blk->idx + 1; 299 300 return; 301 } 302 303 /* Emit remaining data and send terminator token. */ 304 305 sz = st->mapsz - last; 306 LOG4("%s: flushing %s %jd B", path, 307 last == 0 ? "whole" : "remaining", (intmax_t)sz); 308 309 hash_file_buf(&st->ctx, st->map + last, sz); 310 311 st->total += sz; 312 st->dirty += sz; 313 st->curpos = last; 314 st->curlen = st->curpos + sz; 315 st->curtok = 0; 316 st->curst = sz ? BLKSTAT_DATA : BLKSTAT_TOK; 317} 318 319/* 320 * Buffer the message from sender to the receiver indicating that the 321 * block set has been received. 322 * Symmetrises blk_send_ack(). 323 */ 324void 325blk_recv_ack(char buf[20], const struct blkset *blocks, int32_t idx) 326{ 327 size_t pos = 0, sz; 328 329 sz = sizeof(int32_t) + /* index */ 330 sizeof(int32_t) + /* block count */ 331 sizeof(int32_t) + /* block length */ 332 sizeof(int32_t) + /* checksum length */ 333 sizeof(int32_t); /* block remainder */ 334 assert(sz == 20); 335 336 io_buffer_int(buf, &pos, sz, idx); 337 io_buffer_int(buf, &pos, sz, blocks->blksz); 338 io_buffer_int(buf, &pos, sz, blocks->len); 339 io_buffer_int(buf, &pos, sz, blocks->csum); 340 io_buffer_int(buf, &pos, sz, blocks->rem); 341 assert(pos == sz); 342} 343 344/* 345 * Read all of the checksums for a file's blocks. 346 * Returns the set of blocks or NULL on failure. 347 */ 348struct blkset * 349blk_recv(struct sess *sess, int fd, const char *path) 350{ 351 struct blkset *s; 352 int32_t i; 353 size_t j; 354 struct blk *b; 355 off_t offs = 0; 356 357 if ((s = calloc(1, sizeof(struct blkset))) == NULL) { 358 ERR("calloc"); 359 return NULL; 360 } 361 362 /* 363 * The block prologue consists of a few values that we'll need 364 * in reading the individual blocks for this file. 365 * FIXME: read into buffer and unbuffer. 366 */ 367 368 if (!io_read_size(sess, fd, &s->blksz)) { 369 ERRX1("io_read_size"); 370 goto out; 371 } else if (!io_read_size(sess, fd, &s->len)) { 372 ERRX1("io_read_size"); 373 goto out; 374 } else if (!io_read_size(sess, fd, &s->csum)) { 375 ERRX1("io_read_int"); 376 goto out; 377 } else if (!io_read_size(sess, fd, &s->rem)) { 378 ERRX1("io_read_int"); 379 goto out; 380 } else if (s->rem && s->rem >= s->len) { 381 ERRX("block remainder is " 382 "greater than block size"); 383 goto out; 384 } 385 386 LOG3("%s: read block prologue: %zu blocks of " 387 "%zu B, %zu B remainder, %zu B checksum", path, 388 s->blksz, s->len, s->rem, s->csum); 389 390 if (s->blksz) { 391 s->blks = calloc(s->blksz, sizeof(struct blk)); 392 if (s->blks == NULL) { 393 ERR("calloc"); 394 goto out; 395 } 396 } 397 398 /* 399 * Read each block individually. 400 * FIXME: read buffer and unbuffer. 401 */ 402 403 for (j = 0; j < s->blksz; j++) { 404 b = &s->blks[j]; 405 if (!io_read_int(sess, fd, &i)) { 406 ERRX1("io_read_int"); 407 goto out; 408 } 409 b->chksum_short = i; 410 411 assert(s->csum <= sizeof(b->chksum_long)); 412 if (!io_read_buf(sess, 413 fd, b->chksum_long, s->csum)) { 414 ERRX1("io_read_buf"); 415 goto out; 416 } 417 418 /* 419 * If we're the last block, then we're assigned the 420 * remainder of the data. 421 */ 422 423 b->offs = offs; 424 b->idx = j; 425 b->len = (j == (s->blksz - 1) && s->rem) ? 426 s->rem : s->len; 427 offs += b->len; 428 429 LOG4("%s: read block %zu, length %zu B", 430 path, b->idx, b->len); 431 } 432 433 s->size = offs; 434 LOG3("%s: read blocks: %zu blocks, %jd B total blocked data", 435 path, s->blksz, (intmax_t)s->size); 436 return s; 437out: 438 free(s->blks); 439 free(s); 440 return NULL; 441} 442 443/* 444 * Symmetrise blk_recv_ack(), except w/o the leading identifier. 445 * Return zero on failure, non-zero on success. 446 */ 447int 448blk_send_ack(struct sess *sess, int fd, struct blkset *p) 449{ 450 char buf[16]; 451 size_t pos = 0, sz; 452 453 /* Put the entire send routine into a buffer. */ 454 455 sz = sizeof(int32_t) + /* block count */ 456 sizeof(int32_t) + /* block length */ 457 sizeof(int32_t) + /* checksum length */ 458 sizeof(int32_t); /* block remainder */ 459 assert(sz <= sizeof(buf)); 460 461 if (!io_read_buf(sess, fd, buf, sz)) { 462 ERRX1("io_read_buf"); 463 return 0; 464 } 465 466 if (!io_unbuffer_size(buf, &pos, sz, &p->blksz)) 467 ERRX1("io_unbuffer_size"); 468 else if (!io_unbuffer_size(buf, &pos, sz, &p->len)) 469 ERRX1("io_unbuffer_size"); 470 else if (!io_unbuffer_size(buf, &pos, sz, &p->csum)) 471 ERRX1("io_unbuffer_size"); 472 else if (!io_unbuffer_size(buf, &pos, sz, &p->rem)) 473 ERRX1("io_unbuffer_size"); 474 else if (p->len && p->rem >= p->len) 475 ERRX1("non-zero length is less than remainder"); 476 else if (p->csum == 0 || p->csum > 16) 477 ERRX1("inappropriate checksum length"); 478 else 479 return 1; 480 481 return 0; 482} 483 484/* 485 * Transmit the metadata for set and blocks. 486 * Return zero on failure, non-zero on success. 487 */ 488int 489blk_send(struct sess *sess, int fd, size_t idx, 490 const struct blkset *p, const char *path) 491{ 492 char *buf; 493 size_t i, pos = 0, sz; 494 int rc = 0; 495 496 /* Put the entire send routine into a buffer. */ 497 498 sz = sizeof(int32_t) + /* identifier */ 499 sizeof(int32_t) + /* block count */ 500 sizeof(int32_t) + /* block length */ 501 sizeof(int32_t) + /* checksum length */ 502 sizeof(int32_t) + /* block remainder */ 503 p->blksz * 504 (sizeof(int32_t) + /* short checksum */ 505 p->csum); /* long checksum */ 506 507 if ((buf = malloc(sz)) == NULL) { 508 ERR("malloc"); 509 return 0; 510 } 511 512 io_buffer_int(buf, &pos, sz, idx); 513 io_buffer_int(buf, &pos, sz, p->blksz); 514 io_buffer_int(buf, &pos, sz, p->len); 515 io_buffer_int(buf, &pos, sz, p->csum); 516 io_buffer_int(buf, &pos, sz, p->rem); 517 518 for (i = 0; i < p->blksz; i++) { 519 io_buffer_int(buf, &pos, sz, p->blks[i].chksum_short); 520 io_buffer_buf(buf, &pos, sz, p->blks[i].chksum_long, p->csum); 521 } 522 523 assert(pos == sz); 524 525 if (!io_write_buf(sess, fd, buf, sz)) { 526 ERRX1("io_write_buf"); 527 goto out; 528 } 529 530 LOG3("%s: sent block prologue: %zu blocks of %zu B, " 531 "%zu B remainder, %zu B checksum", 532 path, p->blksz, p->len, p->rem, p->csum); 533 rc = 1; 534out: 535 free(buf); 536 return rc; 537} 538