lib/verity/verity_fec.c

   1 /*
   2  * dm-verity Forward Error Correction (FEC) support
   3  *
   4  * Copyright (C) 2015 Google, Inc. All rights reserved.
   5  * Copyright (C) 2017-2023 Red Hat, Inc. All rights reserved.
   6  *
   7  * This file is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This file is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this file; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20  */
  21
  22 #include <stdlib.h>
  23 #include <errno.h>
  24
  25 #include "verity.h"
  26 #include "internal.h"
  27 #include "rs.h"
  28
  29 /* ecc parameters */
  30 #define FEC_RSM 255
  31 #define FEC_MIN_RSN 231
  32 #define FEC_MAX_RSN 253
  33
  34 #define FEC_INPUT_DEVICES 2
  35
  36 /* parameters to init_rs_char */
  37 #define FEC_PARAMS(roots) \
  38     8,          /* symbol size in bits */ \
  39     0x11d,      /* field generator polynomial coefficients */ \
  40     0,          /* first root of the generator */ \
  41     1,          /* primitive element to generate polynomial roots */ \
  42     (roots),    /* polynomial degree (number of roots) */ \
  43     0           /* padding bytes at the front of shortened block */
  44
  45 struct fec_input_device {
  46         struct device *device;
  47         int fd;
  48         uint64_t start;
  49         uint64_t count;
  50 };
  51
  52 struct fec_context {
  53         uint32_t rsn;
  54         uint32_t roots;
  55         uint64_t size;
  56         uint64_t blocks;
  57         uint64_t rounds;
  58         uint32_t block_size;
  59         struct fec_input_device *inputs;
  60         size_t ninputs;
  61 };
  62
  63 /* computes ceil(x / y) */
  64 static inline uint64_t FEC_div_round_up(uint64_t x, uint64_t y)
  65 {
  66         return (x / y) + (x % y > 0 ? 1 : 0);
  67 }
  68
  69 /* returns a physical offset for the given RS offset */
  70 static inline uint64_t FEC_interleave(struct fec_context *ctx, uint64_t offset)
  71 {
  72         return (offset / ctx->rsn) +
  73                         (offset % ctx->rsn) * ctx->rounds * ctx->block_size;
  74 }
  75
  76 /* returns data for a byte at the specified RS offset */
  77 static int FEC_read_interleaved(struct fec_context *ctx, uint64_t i,
  78                                 void *output, size_t count)
  79 {
  80         size_t n;
  81         uint64_t offset = FEC_interleave(ctx, i);
  82
  83         /* offsets outside input area are assumed to contain zeros */
  84         if (offset >= ctx->size) {
  85                 memset(output, 0, count);
  86                 return 0;
  87         }
  88
  89         /* find the correct input device and read from it */
  90         for (n = 0; n < ctx->ninputs; ++n) {
  91                 if (offset >= ctx->inputs[n].count) {
  92                         offset -= ctx->inputs[n].count;
  93                         continue;
  94                 }
  95
  96                 /* FIXME: read_lseek_blockwise candidate */
  97                 if (lseek(ctx->inputs[n].fd, ctx->inputs[n].start + offset, SEEK_SET) < 0)
  98                         return -1;
  99                 return (read_buffer(ctx->inputs[n].fd, output, count) == (ssize_t)count) ? 0 : -1;
 100         }
 101
 102         /* should never be reached */
 103         return -1;
 104 }
 105
 106 /* encodes/decode inputs to/from fd */
 107 static int FEC_process_inputs(struct crypt_device *cd,
 108                               struct crypt_params_verity *params,
 109                               struct fec_input_device *inputs,
 110                               size_t ninputs, int fd,
 111                               int decode, unsigned int *errors)
 112 {
 113         int r = 0;
 114         unsigned int i;
 115         struct fec_context ctx;
 116         uint32_t b;
 117         uint64_t n;
 118         uint8_t rs_block[FEC_RSM];
 119         uint8_t *buf = NULL;
 120         void *rs;
 121
 122         /* initialize parameters */
 123         ctx.roots = params->fec_roots;
 124         ctx.rsn = FEC_RSM - ctx.roots;
 125         ctx.block_size = params->data_block_size;
 126         ctx.inputs = inputs;
 127         ctx.ninputs = ninputs;
 128
 129         rs = init_rs_char(FEC_PARAMS(ctx.roots));
 130         if (!rs) {
 131                 log_err(cd, _("Failed to allocate RS context."));
 132                 return -ENOMEM;
 133         }
 134
 135         /* calculate the total area covered by error correction codes */
 136         ctx.size = 0;
 137         for (n = 0; n < ctx.ninputs; ++n) {
 138                 log_dbg(cd, "FEC input %s, offset %" PRIu64 " [bytes], length %" PRIu64 " [bytes]",
 139                         device_path(ctx.inputs[n].device), ctx.inputs[n].start, ctx.inputs[n].count);
 140                 ctx.size += ctx.inputs[n].count;
 141         }
 142
 143         /* each byte in a data block is covered by a different code */
 144         ctx.blocks = FEC_div_round_up(ctx.size, ctx.block_size);
 145         ctx.rounds = FEC_div_round_up(ctx.blocks, ctx.rsn);
 146
 147         buf = malloc((size_t)ctx.block_size * ctx.rsn);
 148         if (!buf) {
 149                 log_err(cd, _("Failed to allocate buffer."));
 150                 r = -ENOMEM;
 151                 goto out;
 152         }
 153
 154         /* encode/decode input */
 155         for (n = 0; n < ctx.rounds; ++n) {
 156                 for (i = 0; i < ctx.rsn; ++i) {
 157                         if (FEC_read_interleaved(&ctx, n * ctx.rsn * ctx.block_size + i,
 158                                                  &buf[i * ctx.block_size], ctx.block_size)) {
 159                                 log_err(cd, _("Failed to read RS block %" PRIu64 " byte %d."), n, i);
 160                                 r = -EIO;
 161                                 goto out;
 162                         }
 163                 }
 164
 165                 for (b = 0; b < ctx.block_size; ++b) {
 166                         for (i = 0; i < ctx.rsn; ++i)
 167                                 rs_block[i] = buf[i * ctx.block_size + b];
 168
 169                         /* decoding from parity device */
 170                         if (decode) {
 171                                 if (read_buffer(fd, &rs_block[ctx.rsn], ctx.roots) < 0) {
 172                                         log_err(cd, _("Failed to read parity for RS block %" PRIu64 "."), n);
 173                                         r = -EIO;
 174                                         goto out;
 175                                 }
 176
 177                                 /* coverity[tainted_data] */
 178                                 r = decode_rs_char(rs, rs_block);
 179                                 if (r < 0) {
 180                                         log_err(cd, _("Failed to repair parity for block %" PRIu64 "."), n);
 181                                         r = -EPERM;
 182                                         goto out;
 183                                 }
 184                                 /* return number of detected errors */
 185                                 if (errors)
 186                                         *errors += r;
 187                                 r = 0;
 188                         } else {
 189                                 /* encoding and writing parity data to fec device */
 190                                 encode_rs_char(rs, rs_block, &rs_block[ctx.rsn]);
 191                                 if (write_buffer(fd, &rs_block[ctx.rsn], ctx.roots) < 0) {
 192                                         log_err(cd, _("Failed to write parity for RS block %" PRIu64 "."), n);
 193                                         r = -EIO;
 194                                         goto out;
 195                                 }
 196                         }
 197                 }
 198         }
 199 out:
 200         free_rs_char(rs);
 201         free(buf);
 202         return r;
 203 }
 204
 205 static int VERITY_FEC_validate(struct crypt_device *cd, struct crypt_params_verity *params)
 206 {
 207         if (params->data_block_size != params->hash_block_size) {
 208                 log_err(cd, _("Block sizes must match for FEC."));
 209                 return -EINVAL;
 210         }
 211
 212         if (params->fec_roots > FEC_RSM - FEC_MIN_RSN ||
 213                 params->fec_roots < FEC_RSM - FEC_MAX_RSN) {
 214                 log_err(cd, _("Invalid number of parity bytes."));
 215                 return -EINVAL;
 216         }
 217
 218         return 0;
 219 }
 220
 221 int VERITY_FEC_process(struct crypt_device *cd,
 222                       struct crypt_params_verity *params,
 223                       struct device *fec_device, int check_fec,
 224                       unsigned int *errors)
 225 {
 226         int r = -EIO, fd = -1;
 227         size_t ninputs = FEC_INPUT_DEVICES;
 228         struct fec_input_device inputs[FEC_INPUT_DEVICES] = {
 229                 {
 230                         .device = crypt_data_device(cd),
 231                         .fd = -1,
 232                         .start = 0,
 233                         .count =  params->data_size * params->data_block_size
 234                 },{
 235                         .device = crypt_metadata_device(cd),
 236                         .fd = -1,
 237                         .start = VERITY_hash_offset_block(params) * params->data_block_size,
 238                         .count = (VERITY_FEC_blocks(cd, fec_device, params) - params->data_size) * params->data_block_size
 239                 }
 240         };
 241
 242         /* validate parameters */
 243         r = VERITY_FEC_validate(cd, params);
 244         if (r < 0)
 245                 return r;
 246
 247         if (!inputs[0].count) {
 248                 log_err(cd, _("Invalid FEC segment length."));
 249                 return -EINVAL;
 250         }
 251         if (!inputs[1].count)
 252                 ninputs--;
 253
 254         if (check_fec)
 255                 fd = open(device_path(fec_device), O_RDONLY);
 256         else
 257                 fd = open(device_path(fec_device), O_RDWR);
 258
 259         if (fd == -1) {
 260                 log_err(cd, _("Cannot open device %s."), device_path(fec_device));
 261                 goto out;
 262         }
 263
 264         if (lseek(fd, params->fec_area_offset, SEEK_SET) < 0) {
 265                 log_dbg(cd, "Cannot seek to requested position in FEC device.");
 266                 goto out;
 267         }
 268
 269         /* input devices */
 270         inputs[0].fd = open(device_path(inputs[0].device), O_RDONLY);
 271         if (inputs[0].fd == -1) {
 272                 log_err(cd, _("Cannot open device %s."), device_path(inputs[0].device));
 273                 goto out;
 274         }
 275         inputs[1].fd = open(device_path(inputs[1].device), O_RDONLY);
 276         if (inputs[1].fd == -1) {
 277                 log_err(cd, _("Cannot open device %s."), device_path(inputs[1].device));
 278                 goto out;
 279         }
 280
 281         r = FEC_process_inputs(cd, params, inputs, ninputs, fd, check_fec, errors);
 282 out:
 283         if (inputs[0].fd != -1)
 284                 close(inputs[0].fd);
 285         if (inputs[1].fd != -1)
 286                 close(inputs[1].fd);
 287         if (fd != -1)
 288                 close(fd);
 289
 290         return r;
 291 }
 292
 293 /* All blocks that are covered by FEC */
 294 uint64_t VERITY_FEC_blocks(struct crypt_device *cd,
 295                            struct device *fec_device,
 296                            struct crypt_params_verity *params)
 297 {
 298         uint64_t blocks = 0;
 299
 300         if (!fec_device || VERITY_FEC_validate(cd, params) < 0)
 301                 return 0;
 302
 303         /*
 304         * FEC covers this data:
 305         *     | protected data | hash area | padding (optional foreign metadata) |
 306         *
 307         * If hash device is in a separate image, metadata covers the whole rest of the image after hash area.
 308         * If hash and FEC device is in the image, metadata ends on the FEC area offset.
 309         */
 310         if (device_is_identical(crypt_metadata_device(cd), fec_device) > 0) {
 311                 log_dbg(cd, "FEC and hash device is the same.");
 312                  blocks = params->fec_area_offset;
 313         } else {
 314                 /* cover the entire hash device starting from hash_offset */
 315                 if (device_size(crypt_metadata_device(cd), &blocks)) {
 316                         log_err(cd, _("Failed to determine size for device %s."),
 317                                         device_path(crypt_metadata_device(cd)));
 318                         return 0;
 319                 }
 320         }
 321
 322         blocks /= params->data_block_size;
 323         if (blocks)
 324                 blocks -= VERITY_hash_offset_block(params);
 325
 326         /* Protected data */
 327         blocks += params->data_size;
 328
 329         return blocks;
 330 }
 331
 332 /* Blocks needed to store FEC data, blocks must be validated/calculated by VERITY_FEC_blocks() */
 333 uint64_t VERITY_FEC_RS_blocks(uint64_t blocks, uint32_t roots)
 334 {
 335         return FEC_div_round_up(blocks, FEC_RSM - roots) * roots;
 336 }