libfec/fec_read.cpp

   1 /*
   2  * Copyright (C) 2015 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <fcntl.h>
  18 #include <stdlib.h>
  19 #include <sys/mman.h>
  20
  21 extern "C" {
  22     #include <fec.h>
  23 }
  24
  25 #include "fec_private.h"
  26
  27 using rs_unique_ptr = std::unique_ptr<void, decltype(&free_rs_char)>;
  28
  29 /* prints a hexdump of `data' using warn(...) */
  30 static void dump(const char *name, uint64_t value, const uint8_t *data,
  31         size_t size)
  32 {
  33     const int bytes_per_line = 16;
  34     char hex[bytes_per_line * 3 + 1];
  35     char prn[bytes_per_line + 1];
  36
  37     warn("%s (%" PRIu64 ") (%zu bytes):", name ? name : "", value, size);
  38
  39     if (!data) {
  40         warn("    (null)");
  41         return;
  42     }
  43
  44     for (size_t n = 0; n < size; n += bytes_per_line) {
  45         memset(hex, 0, sizeof(hex));
  46         memset(prn, 0, sizeof(prn));
  47
  48         for (size_t m = 0; m < bytes_per_line; ++m) {
  49             if (n + m < size) {
  50                 sprintf(&hex[m * 3], "%02x ", data[n + m]);
  51
  52                 if (isprint(data[n + m])) {
  53                     prn[m] = data[n + m];
  54                 } else {
  55                     prn[m] = '.';
  56                 }
  57             } else {
  58                 strcpy(&hex[m * 3], "   ");
  59             }
  60         }
  61
  62         warn("    %04zu   %s  %s", n, hex, prn);
  63     }
  64 }
  65
  66 /* checks if `offset' is within a corrupted block */
  67 static inline bool is_erasure(fec_handle *f, uint64_t offset,
  68         const uint8_t *data)
  69 {
  70     if (unlikely(offset >= f->data_size)) {
  71         return false;
  72     }
  73
  74     /* ideally, we would like to know if a specific byte on this block has
  75        been corrupted, but knowing whether any of them is can be useful as
  76        well, because often the entire block is corrupted */
  77
  78     uint64_t n = offset / FEC_BLOCKSIZE;
  79
  80     return !verity_check_block(f, &f->verity.hash[n * SHA256_DIGEST_LENGTH],
  81                 data);
  82 }
  83
  84 /* check if `offset' is within a block expected to contain zeros */
  85 static inline bool is_zero(fec_handle *f, uint64_t offset)
  86 {
  87     verity_info *v = &f->verity;
  88
  89     if (!v->hash || unlikely(offset >= f->data_size)) {
  90         return false;
  91     }
  92
  93     uint64_t hash_offset = (offset / FEC_BLOCKSIZE) * SHA256_DIGEST_LENGTH;
  94
  95     if (unlikely(hash_offset >
  96             v->hash_data_blocks * FEC_BLOCKSIZE - SHA256_DIGEST_LENGTH)) {
  97         return false;
  98     }
  99
 100     return !memcmp(v->zero_hash, &v->hash[hash_offset], SHA256_DIGEST_LENGTH);
 101 }
 102
 103 /* reads and decodes a single block starting from `offset', returns the number
 104    of bytes corrected in `errors' */
 105 static int __ecc_read(fec_handle *f, void *rs, uint8_t *dest, uint64_t offset,
 106         bool use_erasures, uint8_t *ecc_data, size_t *errors)
 107 {
 108     check(offset % FEC_BLOCKSIZE == 0);
 109     ecc_info *e = &f->ecc;
 110
 111     /* reverse interleaving: calculate the RS block that includes the requested
 112        offset */
 113     uint64_t rsb = offset - (offset / (e->rounds * FEC_BLOCKSIZE)) *
 114                         e->rounds * FEC_BLOCKSIZE;
 115     int data_index = -1;
 116     int erasures[e->rsn];
 117     int neras = 0;
 118
 119     /* verity is required to check for erasures */
 120     check(!use_erasures || f->verity.hash);
 121
 122     for (int i = 0; i < e->rsn; ++i) {
 123         uint64_t interleaved = fec_ecc_interleave(rsb * e->rsn + i, e->rsn,
 124                                     e->rounds);
 125
 126         if (interleaved == offset) {
 127             data_index = i;
 128         }
 129
 130         /* to improve our chances of correcting IO errors, initialize the
 131            buffer to zeros even if we are going to read to it later */
 132         uint8_t bbuf[FEC_BLOCKSIZE] = {0};
 133
 134         if (likely(interleaved < e->start) && !is_zero(f, interleaved)) {
 135             /* copy raw data to reconstruct the RS block */
 136             if (!raw_pread(f, bbuf, FEC_BLOCKSIZE, interleaved)) {
 137                 warn("failed to read: %s", strerror(errno));
 138
 139                 /* treat errors as corruption */
 140                 if (use_erasures && neras <= e->roots) {
 141                     erasures[neras++] = i;
 142                 }
 143             } else if (use_erasures && neras <= e->roots &&
 144                             is_erasure(f, interleaved, bbuf)) {
 145                 erasures[neras++] = i;
 146             }
 147         }
 148
 149         for (int j = 0; j < FEC_BLOCKSIZE; ++j) {
 150             ecc_data[j * FEC_RSM + i] = bbuf[j];
 151         }
 152     }
 153
 154     check(data_index >= 0);
 155
 156     size_t nerrs = 0;
 157     uint8_t copy[FEC_RSM];
 158
 159     for (int i = 0; i < FEC_BLOCKSIZE; ++i) {
 160         /* copy parity data */
 161         if (!raw_pread(f, &ecc_data[i * FEC_RSM + e->rsn], e->roots,
 162                 e->start + (i + rsb) * e->roots)) {
 163             error("failed to read ecc data: %s", strerror(errno));
 164             return -1;
 165         }
 166
 167         /* for debugging decoding failures, because decode_rs_char can mangle
 168            ecc_data */
 169         if (unlikely(use_erasures)) {
 170             memcpy(copy, &ecc_data[i * FEC_RSM], FEC_RSM);
 171         }
 172
 173         /* decode */
 174         int rc = decode_rs_char(rs, &ecc_data[i * FEC_RSM], erasures, neras);
 175
 176         if (unlikely(rc < 0)) {
 177             if (use_erasures) {
 178                 error("RS block %" PRIu64 ": decoding failed (%d erasures)",
 179                     rsb, neras);
 180                 dump("raw RS block", rsb, copy, FEC_RSM);
 181             } else if (!f->verity.hash) {
 182                 warn("RS block %" PRIu64 ": decoding failed", rsb);
 183             } else {
 184                 debug("RS block %" PRIu64 ": decoding failed", rsb);
 185             }
 186
 187             errno = EIO;
 188             return -1;
 189         } else if (unlikely(rc > 0)) {
 190             check(rc <= (use_erasures ? e->roots : e->roots / 2));
 191             nerrs += rc;
 192         }
 193
 194         dest[i] = ecc_data[i * FEC_RSM + data_index];
 195     }
 196
 197     if (nerrs) {
 198         warn("RS block %" PRIu64 ": corrected %zu errors", rsb, nerrs);
 199         *errors += nerrs;
 200     }
 201
 202     return FEC_BLOCKSIZE;
 203 }
 204
 205 /* initializes RS decoder and allocates memory for interleaving */
 206 static int ecc_init(fec_handle *f, rs_unique_ptr& rs,
 207         std::unique_ptr<uint8_t[]>& ecc_data)
 208 {
 209     check(f);
 210
 211     rs.reset(init_rs_char(FEC_PARAMS(f->ecc.roots)));
 212
 213     if (unlikely(!rs)) {
 214         error("failed to initialize RS");
 215         errno = ENOMEM;
 216         return -1;
 217     }
 218
 219     ecc_data.reset(new (std::nothrow) uint8_t[FEC_RSM * FEC_BLOCKSIZE]);
 220
 221     if (unlikely(!ecc_data)) {
 222         error("failed to allocate ecc buffer");
 223         errno = ENOMEM;
 224         return -1;
 225     }
 226
 227     return 0;
 228 }
 229
 230 /* reads `count' bytes from `offset' and corrects possible errors without
 231    erasure detection, returning the number of corrected bytes in `errors' */
 232 static ssize_t ecc_read(fec_handle *f, uint8_t *dest, size_t count,
 233         uint64_t offset, size_t *errors)
 234 {
 235     check(f);
 236     check(dest);
 237     check(offset < f->data_size);
 238     check(offset + count <= f->data_size);
 239     check(errors);
 240
 241     debug("[%" PRIu64 ", %" PRIu64 ")", offset, offset + count);
 242
 243     rs_unique_ptr rs(NULL, free_rs_char);
 244     std::unique_ptr<uint8_t[]> ecc_data;
 245
 246     if (ecc_init(f, rs, ecc_data) == -1) {
 247         return -1;
 248     }
 249
 250     uint64_t curr = offset / FEC_BLOCKSIZE;
 251     size_t coff = (size_t)(offset - curr * FEC_BLOCKSIZE);
 252     size_t left = count;
 253
 254     uint8_t data[FEC_BLOCKSIZE];
 255
 256     while (left > 0) {
 257         /* there's no erasure detection without verity metadata */
 258         if (__ecc_read(f, rs.get(), data, curr * FEC_BLOCKSIZE, false,
 259                 ecc_data.get(), errors) == -1) {
 260             return -1;
 261         }
 262
 263         size_t copy = FEC_BLOCKSIZE - coff;
 264
 265         if (copy > left) {
 266             copy = left;
 267         }
 268
 269         memcpy(dest, &data[coff], copy);
 270
 271         dest += copy;
 272         left -= copy;
 273         coff = 0;
 274         ++curr;
 275     }
 276
 277     return count;
 278 }
 279
 280 /* reads `count' bytes from `offset', corrects possible errors with
 281    erasure detection, and verifies the integrity of read data using
 282    verity hash tree; returns the number of corrections in `errors' */
 283 static ssize_t verity_read(fec_handle *f, uint8_t *dest, size_t count,
 284         uint64_t offset, size_t *errors)
 285 {
 286     check(f);
 287     check(dest);
 288     check(offset < f->data_size);
 289     check(offset + count <= f->data_size);
 290     check(f->verity.hash);
 291     check(errors);
 292
 293     debug("[%" PRIu64 ", %" PRIu64 ")", offset, offset + count);
 294
 295     rs_unique_ptr rs(NULL, free_rs_char);
 296     std::unique_ptr<uint8_t[]> ecc_data;
 297
 298     if (f->ecc.start && ecc_init(f, rs, ecc_data) == -1) {
 299         return -1;
 300     }
 301
 302     uint64_t curr = offset / FEC_BLOCKSIZE;
 303     size_t coff = (size_t)(offset - curr * FEC_BLOCKSIZE);
 304     size_t left = count;
 305     uint8_t data[FEC_BLOCKSIZE];
 306
 307     uint64_t max_hash_block = (f->verity.hash_data_blocks * FEC_BLOCKSIZE -
 308                                 SHA256_DIGEST_LENGTH) / SHA256_DIGEST_LENGTH;
 309
 310     while (left > 0) {
 311         check(curr <= max_hash_block);
 312
 313         uint8_t *hash = &f->verity.hash[curr * SHA256_DIGEST_LENGTH];
 314         uint64_t curr_offset = curr * FEC_BLOCKSIZE;
 315
 316         bool expect_zeros = is_zero(f, curr_offset);
 317
 318         /* if we are in read-only mode and expect to read a zero block,
 319            skip reading and just return zeros */
 320         if (f->mode & O_RDONLY && expect_zeros) {
 321             memset(data, 0, FEC_BLOCKSIZE);
 322             goto valid;
 323         }
 324
 325         /* copy raw data without error correction */
 326         if (!raw_pread(f, data, FEC_BLOCKSIZE, curr_offset)) {
 327             error("failed to read: %s", strerror(errno));
 328             return -1;
 329         }
 330
 331         if (likely(verity_check_block(f, hash, data))) {
 332             goto valid;
 333         }
 334
 335         /* we know the block is supposed to contain zeros, so return zeros
 336            instead of trying to correct it */
 337         if (expect_zeros) {
 338             memset(data, 0, FEC_BLOCKSIZE);
 339             goto corrected;
 340         }
 341
 342         if (!f->ecc.start) {
 343             /* fatal error without ecc */
 344             error("[%" PRIu64 ", %" PRIu64 "): corrupted block %" PRIu64,
 345                 offset, offset + count, curr);
 346             return -1;
 347         } else {
 348             debug("[%" PRIu64 ", %" PRIu64 "): corrupted block %" PRIu64,
 349                 offset, offset + count, curr);
 350         }
 351
 352         /* try to correct without erasures first, because checking for
 353            erasure locations is slower */
 354         if (__ecc_read(f, rs.get(), data, curr_offset, false, ecc_data.get(),
 355                 errors) == FEC_BLOCKSIZE &&
 356             verity_check_block(f, hash, data)) {
 357             goto corrected;
 358         }
 359
 360         /* try to correct with erasures */
 361         if (__ecc_read(f, rs.get(), data, curr_offset, true, ecc_data.get(),
 362                 errors) == FEC_BLOCKSIZE &&
 363             verity_check_block(f, hash, data)) {
 364             goto corrected;
 365         }
 366
 367         error("[%" PRIu64 ", %" PRIu64 "): corrupted block %" PRIu64
 368             " (offset %" PRIu64 ") cannot be recovered",
 369             offset, offset + count, curr, curr_offset);
 370         dump("decoded block", curr, data, FEC_BLOCKSIZE);
 371
 372         errno = EIO;
 373         return -1;
 374
 375 corrected:
 376         /* update the corrected block to the file if we are in r/w mode */
 377         if (f->mode & O_RDWR &&
 378                 !raw_pwrite(f, data, FEC_BLOCKSIZE, curr_offset)) {
 379             error("failed to write: %s", strerror(errno));
 380             return -1;
 381         }
 382
 383 valid:
 384         size_t copy = FEC_BLOCKSIZE - coff;
 385
 386         if (copy > left) {
 387             copy = left;
 388         }
 389
 390         memcpy(dest, &data[coff], copy);
 391
 392         dest += copy;
 393         left -= copy;
 394         coff = 0;
 395         ++curr;
 396     }
 397
 398     return count;
 399 }
 400
 401 /* sets the internal file position to `offset' relative to `whence' */
 402 int fec_seek(struct fec_handle *f, int64_t offset, int whence)
 403 {
 404     check(f);
 405
 406     if (whence == SEEK_SET) {
 407         if (offset < 0) {
 408             errno = EOVERFLOW;
 409             return -1;
 410         }
 411
 412         f->pos = offset;
 413     } else if (whence == SEEK_CUR) {
 414         if (offset < 0 && f->pos < (uint64_t)-offset) {
 415             errno = EOVERFLOW;
 416             return -1;
 417         } else if (offset > 0 && (uint64_t)offset > UINT64_MAX - f->pos) {
 418             errno = EOVERFLOW;
 419             return -1;
 420         }
 421
 422         f->pos += offset;
 423     } else if (whence == SEEK_END) {
 424         if (offset >= 0) {
 425             errno = ENXIO;
 426             return -1;
 427         } else if ((uint64_t)-offset > f->size) {
 428             errno = EOVERFLOW;
 429             return -1;
 430         }
 431
 432         f->pos = f->size + offset;
 433     } else {
 434         errno = EINVAL;
 435         return -1;
 436     }
 437
 438     return 0;
 439 }
 440
 441 /* reads up to `count' bytes starting from the internal file position using
 442    error correction and integrity validation, if available */
 443 ssize_t fec_read(struct fec_handle *f, void *buf, size_t count)
 444 {
 445     ssize_t rc = fec_pread(f, buf, count, f->pos);
 446
 447     if (rc > 0) {
 448         check(f->pos < UINT64_MAX - rc);
 449         f->pos += rc;
 450     }
 451
 452     return rc;
 453 }
 454
 455 /* for a file with size `max', returns the number of bytes we can read starting
 456    from `offset', up to `count' bytes */
 457 static inline size_t get_max_count(uint64_t offset, size_t count, uint64_t max)
 458 {
 459     if (offset >= max) {
 460         return 0;
 461     } else if (offset > max - count) {
 462         return (size_t)(max - offset);
 463     }
 464
 465     return count;
 466 }
 467
 468 /* reads `count' bytes from `f->fd' starting from `offset', and copies the
 469    data to `buf' */
 470 bool raw_pread(fec_handle *f, void *buf, size_t count, uint64_t offset)
 471 {
 472     check(f);
 473     check(buf);
 474
 475     uint8_t *p = (uint8_t *)buf;
 476     size_t remaining = count;
 477
 478     while (remaining > 0) {
 479         ssize_t n = TEMP_FAILURE_RETRY(pread64(f->fd, p, remaining, offset));
 480
 481         if (n <= 0) {
 482             return false;
 483         }
 484
 485         p += n;
 486         remaining -= n;
 487         offset += n;
 488     }
 489
 490     return true;
 491 }
 492
 493 /* writes `count' bytes from `buf' to `f->fd' to a file position `offset' */
 494 bool raw_pwrite(fec_handle *f, const void *buf, size_t count, uint64_t offset)
 495 {
 496     check(f);
 497     check(buf);
 498
 499     const uint8_t *p = (const uint8_t *)buf;
 500     size_t remaining = count;
 501
 502     while (remaining > 0) {
 503         ssize_t n = TEMP_FAILURE_RETRY(pwrite64(f->fd, p, remaining, offset));
 504
 505         if (n <= 0) {
 506             return false;
 507         }
 508
 509         p += n;
 510         remaining -= n;
 511         offset += n;
 512     }
 513
 514     return true;
 515 }
 516
 517 /* reads up to `count' bytes starting from `offset' using error correction and
 518    integrity validation, if available */
 519 ssize_t fec_pread(struct fec_handle *f, void *buf, size_t count,
 520         uint64_t offset)
 521 {
 522     check(f);
 523     check(buf);
 524
 525     if (unlikely(offset > UINT64_MAX - count)) {
 526         errno = EOVERFLOW;
 527         return -1;
 528     }
 529
 530     if (f->verity.hash) {
 531         return process(f, (uint8_t *)buf,
 532                     get_max_count(offset, count, f->data_size), offset,
 533                     verity_read);
 534     } else if (f->ecc.start) {
 535         check(f->ecc.start < f->size);
 536
 537         count = get_max_count(offset, count, f->data_size);
 538         ssize_t rc = process(f, (uint8_t *)buf, count, offset, ecc_read);
 539
 540         if (rc >= 0) {
 541             return rc;
 542         }
 543
 544         /* return raw data if pure ecc read fails; due to interleaving
 545            the specific blocks the caller wants may still be fine */
 546     } else {
 547         count = get_max_count(offset, count, f->size);
 548     }
 549
 550     if (raw_pread(f, buf, count, offset)) {
 551         return count;
 552     }
 553
 554     return -1;
 555 }