2 * dm-verity Forward Error Correction (FEC) support
4 * Copyright (C) 2015 Google, Inc. All rights reserved.
5 * Copyright (C) 2017-2020 Red Hat, Inc. All rights reserved.
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.
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.
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.
31 #define FEC_MIN_RSN 231
32 #define FEC_MAX_RSN 253
34 #define FEC_INPUT_DEVICES 2
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 */
45 struct fec_input_device {
46 struct device *device;
59 struct fec_input_device *inputs;
63 /* computes ceil(x / y) */
64 static inline uint64_t FEC_div_round_up(uint64_t x, uint64_t y)
66 return (x / y) + (x % y > 0 ? 1 : 0);
69 /* returns a physical offset for the given RS offset */
70 static inline uint64_t FEC_interleave(struct fec_context *ctx, uint64_t offset)
72 return (offset / ctx->rsn) +
73 (offset % ctx->rsn) * ctx->rounds * ctx->block_size;
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)
81 uint64_t offset = FEC_interleave(ctx, i);
83 /* offsets outside input area are assumed to contain zeros */
84 if (offset >= ctx->size) {
85 memset(output, 0, count);
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;
96 /* FIXME: read_lseek_blockwise candidate */
97 if (lseek(ctx->inputs[n].fd, ctx->inputs[n].start + offset, SEEK_SET) < 0)
99 return (read_buffer(ctx->inputs[n].fd, output, count) == (ssize_t)count) ? 0 : -1;
102 /* should never be reached */
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)
115 struct fec_context ctx;
118 uint8_t rs_block[FEC_RSM];
122 /* initialize parameters */
123 ctx.roots = params->fec_roots;
124 ctx.rsn = FEC_RSM - ctx.roots;
125 ctx.block_size = params->data_block_size;
127 ctx.ninputs = ninputs;
129 rs = init_rs_char(FEC_PARAMS(ctx.roots));
131 log_err(cd, _("Failed to allocate RS context."));
135 /* calculate the total area covered by error correction codes */
137 for (n = 0; n < ctx.ninputs; ++n)
138 ctx.size += ctx.inputs[n].count;
140 /* each byte in a data block is covered by a different code */
141 ctx.blocks = FEC_div_round_up(ctx.size, ctx.block_size);
142 ctx.rounds = FEC_div_round_up(ctx.blocks, ctx.rsn);
144 buf = malloc((size_t)ctx.block_size * ctx.rsn);
146 log_err(cd, _("Failed to allocate buffer."));
151 /* encode/decode input */
152 for (n = 0; n < ctx.rounds; ++n) {
153 for (i = 0; i < ctx.rsn; ++i) {
154 if (FEC_read_interleaved(&ctx, n * ctx.rsn * ctx.block_size + i,
155 &buf[i * ctx.block_size], ctx.block_size)) {
156 log_err(cd, _("Failed to read RS block %" PRIu64 " byte %d."), n, i);
162 for (b = 0; b < ctx.block_size; ++b) {
163 for (i = 0; i < ctx.rsn; ++i)
164 rs_block[i] = buf[i * ctx.block_size + b];
166 /* decoding from parity device */
168 if (read_buffer(fd, &rs_block[ctx.rsn], ctx.roots) < 0) {
169 log_err(cd, _("Failed to read parity for RS block %" PRIu64 "."), n);
174 /* coverity[tainted_data] */
175 r = decode_rs_char(rs, rs_block);
177 log_err(cd, _("Failed to repair parity for block %" PRIu64 "."), n);
180 /* return number of detected errors */
185 /* encoding and writing parity data to fec device */
186 encode_rs_char(rs, rs_block, &rs_block[ctx.rsn]);
187 if (write_buffer(fd, &rs_block[ctx.rsn], ctx.roots) < 0) {
188 log_err(cd, _("Failed to write parity for RS block %" PRIu64 "."), n);
201 int VERITY_FEC_process(struct crypt_device *cd,
202 struct crypt_params_verity *params,
203 struct device *fec_device, int check_fec,
204 unsigned int *errors)
208 struct fec_input_device inputs[FEC_INPUT_DEVICES] = {
210 .device = crypt_data_device(cd),
213 .count = params->data_size * params->data_block_size
215 .device = crypt_metadata_device(cd),
217 .start = VERITY_hash_offset_block(params) * params->data_block_size
221 /* validate parameters */
222 if (params->data_block_size != params->hash_block_size) {
223 log_err(cd, _("Block sizes must match for FEC."));
227 if (params->fec_roots > FEC_RSM - FEC_MIN_RSN ||
228 params->fec_roots < FEC_RSM - FEC_MAX_RSN) {
229 log_err(cd, _("Invalid number of parity bytes."));
236 fd = open(device_path(fec_device), O_RDONLY);
238 fd = open(device_path(fec_device), O_RDWR);
241 log_err(cd, _("Cannot open device %s."), device_path(fec_device));
245 if (lseek(fd, params->fec_area_offset, SEEK_SET) < 0) {
246 log_dbg(cd, "Cannot seek to requested position in FEC device.");
251 inputs[0].fd = open(device_path(inputs[0].device), O_RDONLY);
252 if (inputs[0].fd == -1) {
253 log_err(cd, _("Cannot open device %s."), device_path(inputs[0].device));
256 inputs[1].fd = open(device_path(inputs[1].device), O_RDONLY);
257 if (inputs[1].fd == -1) {
258 log_err(cd, _("Cannot open device %s."), device_path(inputs[1].device));
262 /* cover the entire hash device starting from hash_offset */
263 r = device_size(inputs[1].device, &inputs[1].count);
265 log_err(cd, _("Failed to determine size for device %s."),
266 device_path(inputs[1].device));
269 inputs[1].count -= inputs[1].start;
271 r = FEC_process_inputs(cd, params, inputs, FEC_INPUT_DEVICES, fd, check_fec, errors);
273 if (inputs[0].fd != -1)
275 if (inputs[1].fd != -1)