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         /* copy raw data to reconstruct the RS block */
 131         uint8_t bbuf[FEC_BLOCKSIZE];
 132
 133         if (unlikely(interleaved >= e->start) ||
 134                 is_zero(f, interleaved)) {
 135             memset(bbuf, 0, FEC_BLOCKSIZE);
 136         } else {
 137             if (!raw_pread(f, bbuf, FEC_BLOCKSIZE, interleaved)) {
 138                 error("failed to read: %s", strerror(errno));
 139                 return -1;
 140             }
 141
 142             if (use_erasures && neras <= e->roots &&
 143                     is_erasure(f, interleaved, bbuf)) {
 144                 erasures[neras++] = i;
 145             }
 146         }
 147
 148         for (int j = 0; j < FEC_BLOCKSIZE; ++j) {
 149             ecc_data[j * FEC_RSM + i] = bbuf[j];
 150         }
 151     }
 152
 153     check(data_index >= 0);
 154
 155     size_t nerrs = 0;
 156     uint8_t copy[FEC_RSM];
 157
 158     for (int i = 0; i < FEC_BLOCKSIZE; ++i) {
 159         /* copy parity data */
 160         if (!raw_pread(f, &ecc_data[i * FEC_RSM + e->rsn], e->roots,
 161                 e->start + (i + rsb) * e->roots)) {
 162             error("failed to read ecc data: %s", strerror(errno));
 163             return -1;
 164         }
 165
 166         /* for debugging decoding failures, because decode_rs_char can mangle
 167            ecc_data */
 168         if (unlikely(use_erasures)) {
 169             memcpy(copy, &ecc_data[i * FEC_RSM], FEC_RSM);
 170         }
 171
 172         /* decode */
 173         int rc = decode_rs_char(rs, &ecc_data[i * FEC_RSM], erasures, neras);
 174
 175         if (unlikely(rc < 0)) {
 176             if (use_erasures) {
 177                 error("RS block %" PRIu64 ": decoding failed (%d erasures)",
 178                     rsb, neras);
 179                 dump("raw RS block", rsb, copy, FEC_RSM);
 180             } else if (!f->verity.hash) {
 181                 warn("RS block %" PRIu64 ": decoding failed", rsb);
 182             } else {
 183                 debug("RS block %" PRIu64 ": decoding failed", rsb);
 184             }
 185
 186             errno = EIO;
 187             return -1;
 188         } else if (unlikely(rc > 0)) {
 189             check(rc <= (use_erasures ? e->roots : e->roots / 2));
 190             nerrs += rc;
 191         }
 192
 193         dest[i] = ecc_data[i * FEC_RSM + data_index];
 194     }
 195
 196     if (nerrs) {
 197         warn("RS block %" PRIu64 ": corrected %zu errors", rsb, nerrs);
 198         *errors += nerrs;
 199     }
 200
 201     return FEC_BLOCKSIZE;
 202 }
 203
 204 /* initializes RS decoder and allocates memory for interleaving */
 205 static int ecc_init(fec_handle *f, rs_unique_ptr& rs,
 206         std::unique_ptr<uint8_t[]>& ecc_data)
 207 {
 208     check(f);
 209
 210     rs.reset(init_rs_char(FEC_PARAMS(f->ecc.roots)));
 211
 212     if (unlikely(!rs)) {
 213         error("failed to initialize RS");
 214         errno = ENOMEM;
 215         return -1;
 216     }
 217
 218     ecc_data.reset(new (std::nothrow) uint8_t[FEC_RSM * FEC_BLOCKSIZE]);
 219
 220     if (unlikely(!ecc_data)) {
 221         error("failed to allocate ecc buffer");
 222         errno = ENOMEM;
 223         return -1;
 224     }
 225
 226     return 0;
 227 }
 228
 229 /* reads `count' bytes from `offset' and corrects possible errors without
 230    erasure detection, returning the number of corrected bytes in `errors' */
 231 static ssize_t ecc_read(fec_handle *f, uint8_t *dest, size_t count,
 232         uint64_t offset, size_t *errors)
 233 {
 234     check(f);
 235     check(dest);
 236     check(offset < f->data_size);
 237     check(offset + count <= f->data_size);
 238     check(errors);
 239
 240     debug("[%" PRIu64 ", %" PRIu64 ")", offset, offset + count);
 241
 242     rs_unique_ptr rs(NULL, free_rs_char);
 243     std::unique_ptr<uint8_t[]> ecc_data;
 244
 245     if (ecc_init(f, rs, ecc_data) == -1) {
 246         return -1;
 247     }
 248
 249     uint64_t curr = offset / FEC_BLOCKSIZE;
 250     size_t coff = (size_t)(offset - curr * FEC_BLOCKSIZE);
 251     size_t left = count;
 252
 253     uint8_t data[FEC_BLOCKSIZE];
 254
 255     while (left > 0) {
 256         /* there's no erasure detection without verity metadata */
 257         if (__ecc_read(f, rs.get(), data, curr * FEC_BLOCKSIZE, false,
 258                 ecc_data.get(), errors) == -1) {
 259             return -1;
 260         }
 261
 262         size_t copy = FEC_BLOCKSIZE - coff;
 263
 264         if (copy > left) {
 265             copy = left;
 266         }
 267
 268         memcpy(dest, &data[coff], copy);
 269
 270         dest += copy;
 271         left -= copy;
 272         coff = 0;
 273         ++curr;
 274     }
 275
 276     return count;
 277 }
 278
 279 /* reads `count' bytes from `offset', corrects possible errors with
 280    erasure detection, and verifies the integrity of read data using
 281    verity hash tree; returns the number of corrections in `errors' */
 282 static ssize_t verity_read(fec_handle *f, uint8_t *dest, size_t count,
 283         uint64_t offset, size_t *errors)
 284 {
 285     check(f);
 286     check(dest);
 287     check(offset < f->data_size);
 288     check(offset + count <= f->data_size);
 289     check(f->verity.hash);
 290     check(errors);
 291
 292     debug("[%" PRIu64 ", %" PRIu64 ")", offset, offset + count);
 293
 294     rs_unique_ptr rs(NULL, free_rs_char);
 295     std::unique_ptr<uint8_t[]> ecc_data;
 296
 297     if (f->ecc.start && ecc_init(f, rs, ecc_data) == -1) {
 298         return -1;
 299     }
 300
 301     uint64_t curr = offset / FEC_BLOCKSIZE;
 302     size_t coff = (size_t)(offset - curr * FEC_BLOCKSIZE);
 303     size_t left = count;
 304     uint8_t data[FEC_BLOCKSIZE];
 305
 306     uint64_t max_hash_block = (f->verity.hash_data_blocks * FEC_BLOCKSIZE -
 307                                 SHA256_DIGEST_LENGTH) / SHA256_DIGEST_LENGTH;
 308
 309     while (left > 0) {
 310         check(curr <= max_hash_block);
 311
 312         uint8_t *hash = &f->verity.hash[curr * SHA256_DIGEST_LENGTH];
 313         uint64_t curr_offset = curr * FEC_BLOCKSIZE;
 314
 315         bool expect_zeros = is_zero(f, curr_offset);
 316
 317         /* if we are in read-only mode and expect to read a zero block,
 318            skip reading and just return zeros */
 319         if (f->mode & O_RDONLY && expect_zeros) {
 320             memset(data, 0, FEC_BLOCKSIZE);
 321             goto valid;
 322         }
 323
 324         /* copy raw data without error correction */
 325         if (!raw_pread(f, data, FEC_BLOCKSIZE, curr_offset)) {
 326             error("failed to read: %s", strerror(errno));
 327             return -1;
 328         }
 329
 330         if (likely(verity_check_block(f, hash, data))) {
 331             goto valid;
 332         }
 333
 334         /* we know the block is supposed to contain zeros, so return zeros
 335            instead of trying to correct it */
 336         if (expect_zeros) {
 337             memset(data, 0, FEC_BLOCKSIZE);
 338             goto corrected;
 339         }
 340
 341         if (!f->ecc.start) {
 342             /* fatal error without ecc */
 343             error("[%" PRIu64 ", %" PRIu64 "): corrupted block %" PRIu64,
 344                 offset, offset + count, curr);
 345             return -1;
 346         } else {
 347             debug("[%" PRIu64 ", %" PRIu64 "): corrupted block %" PRIu64,
 348                 offset, offset + count, curr);
 349         }
 350
 351         /* try to correct without erasures first, because checking for
 352            erasure locations is slower */
 353         if (__ecc_read(f, rs.get(), data, curr_offset, false, ecc_data.get(),
 354                 errors) == FEC_BLOCKSIZE &&
 355             verity_check_block(f, hash, data)) {
 356             goto corrected;
 357         }
 358
 359         /* try to correct with erasures */
 360         if (__ecc_read(f, rs.get(), data, curr_offset, true, ecc_data.get(),
 361                 errors) == FEC_BLOCKSIZE &&
 362             verity_check_block(f, hash, data)) {
 363             goto corrected;
 364         }
 365
 366         error("[%" PRIu64 ", %" PRIu64 "): corrupted block %" PRIu64
 367             " (offset %" PRIu64 ") cannot be recovered",
 368             offset, offset + count, curr, curr_offset);
 369         dump("decoded block", curr, data, FEC_BLOCKSIZE);
 370
 371         errno = EIO;
 372         return -1;
 373
 374 corrected:
 375         /* update the corrected block to the file if we are in r/w mode */
 376         if (f->mode & O_RDWR &&
 377                 !raw_pwrite(f, data, FEC_BLOCKSIZE, curr_offset)) {
 378             error("failed to write: %s", strerror(errno));
 379             return -1;
 380         }
 381
 382 valid:
 383         size_t copy = FEC_BLOCKSIZE - coff;
 384
 385         if (copy > left) {
 386             copy = left;
 387         }
 388
 389         memcpy(dest, &data[coff], copy);
 390
 391         dest += copy;
 392         left -= copy;
 393         coff = 0;
 394         ++curr;
 395     }
 396
 397     return count;
 398 }
 399
 400 /* sets the internal file position to `offset' relative to `whence' */
 401 int fec_seek(struct fec_handle *f, int64_t offset, int whence)
 402 {
 403     check(f);
 404
 405     if (whence == SEEK_SET) {
 406         if (offset < 0) {
 407             errno = EOVERFLOW;
 408             return -1;
 409         }
 410
 411         f->pos = offset;
 412     } else if (whence == SEEK_CUR) {
 413         if (offset < 0 && f->pos < (uint64_t)-offset) {
 414             errno = EOVERFLOW;
 415             return -1;
 416         } else if (offset > 0 && (uint64_t)offset > UINT64_MAX - f->pos) {
 417             errno = EOVERFLOW;
 418             return -1;
 419         }
 420
 421         f->pos += offset;
 422     } else if (whence == SEEK_END) {
 423         if (offset >= 0) {
 424             errno = ENXIO;
 425             return -1;
 426         } else if ((uint64_t)-offset > f->size) {
 427             errno = EOVERFLOW;
 428             return -1;
 429         }
 430
 431         f->pos = f->size + offset;
 432     } else {
 433         errno = EINVAL;
 434         return -1;
 435     }
 436
 437     return 0;
 438 }
 439
 440 /* reads up to `count' bytes starting from the internal file position using
 441    error correction and integrity validation, if available */
 442 ssize_t fec_read(struct fec_handle *f, void *buf, size_t count)
 443 {
 444     ssize_t rc = fec_pread(f, buf, count, f->pos);
 445
 446     if (rc > 0) {
 447         check(f->pos < UINT64_MAX - rc);
 448         f->pos += rc;
 449     }
 450
 451     return rc;
 452 }
 453
 454 /* for a file with size `max', returns the number of bytes we can read starting
 455    from `offset', up to `count' bytes */
 456 static inline size_t get_max_count(uint64_t offset, size_t count, uint64_t max)
 457 {
 458     if (offset >= max) {
 459         return 0;
 460     } else if (offset > max - count) {
 461         return (size_t)(max - offset);
 462     }
 463
 464     return count;
 465 }
 466
 467 /* reads `count' bytes from `f->fd' starting from `offset', and copies the
 468    data to `buf' */
 469 bool raw_pread(fec_handle *f, void *buf, size_t count, uint64_t offset)
 470 {
 471     check(f);
 472     check(buf);
 473
 474     uint8_t *p = (uint8_t *)buf;
 475     size_t remaining = count;
 476
 477     while (remaining > 0) {
 478         ssize_t n = TEMP_FAILURE_RETRY(pread64(f->fd, p, remaining, offset));
 479
 480         if (n <= 0) {
 481             return false;
 482         }
 483
 484         p += n;
 485         remaining -= n;
 486         offset += n;
 487     }
 488
 489     return true;
 490 }
 491
 492 /* writes `count' bytes from `buf' to `f->fd' to a file position `offset' */
 493 bool raw_pwrite(fec_handle *f, const void *buf, size_t count, uint64_t offset)
 494 {
 495     check(f);
 496     check(buf);
 497
 498     const uint8_t *p = (const uint8_t *)buf;
 499     size_t remaining = count;
 500
 501     while (remaining > 0) {
 502         ssize_t n = TEMP_FAILURE_RETRY(pwrite64(f->fd, p, remaining, offset));
 503
 504         if (n <= 0) {
 505             return false;
 506         }
 507
 508         p += n;
 509         remaining -= n;
 510         offset += n;
 511     }
 512
 513     return true;
 514 }
 515
 516 /* reads up to `count' bytes starting from `offset' using error correction and
 517    integrity validation, if available */
 518 ssize_t fec_pread(struct fec_handle *f, void *buf, size_t count,
 519         uint64_t offset)
 520 {
 521     check(f);
 522     check(buf);
 523
 524     if (unlikely(offset > UINT64_MAX - count)) {
 525         errno = EOVERFLOW;
 526         return -1;
 527     }
 528
 529     if (f->verity.hash) {
 530         return process(f, (uint8_t *)buf,
 531                     get_max_count(offset, count, f->data_size), offset,
 532                     verity_read);
 533     } else if (f->ecc.start) {
 534         check(f->ecc.start < f->size);
 535
 536         count = get_max_count(offset, count, f->data_size);
 537         ssize_t rc = process(f, (uint8_t *)buf, count, offset, ecc_read);
 538
 539         if (rc >= 0) {
 540             return rc;
 541         }
 542
 543         /* return raw data if pure ecc read fails; due to interleaving
 544            the specific blocks the caller wants may still be fine */
 545     } else {
 546         count = get_max_count(offset, count, f->size);
 547     }
 548
 549     if (raw_pread(f, buf, count, offset)) {
 550         return count;
 551     }
 552
 553     return -1;
 554 }