2 * dm-verity Forward Error Correction (FEC) support
4 * Copyright (C) 2015 Google, Inc. All rights reserved.
5 * Copyright (C) 2017-2021 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 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;
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);
147 buf = malloc((size_t)ctx.block_size * ctx.rsn);
149 log_err(cd, _("Failed to allocate buffer."));
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);
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];
169 /* decoding from parity device */
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);
177 /* coverity[tainted_data] */
178 r = decode_rs_char(rs, rs_block);
180 log_err(cd, _("Failed to repair parity for block %" PRIu64 "."), n);
183 /* return number of detected errors */
188 /* encoding and writing parity data to fec device */
189 encode_rs_char(rs, rs_block, &rs_block[ctx.rsn]);
190 if (write_buffer(fd, &rs_block[ctx.rsn], ctx.roots) < 0) {
191 log_err(cd, _("Failed to write parity for RS block %" PRIu64 "."), n);
204 int VERITY_FEC_process(struct crypt_device *cd,
205 struct crypt_params_verity *params,
206 struct device *fec_device, int check_fec,
207 unsigned int *errors)
209 int r = -EIO, fd = -1;
210 size_t ninputs = FEC_INPUT_DEVICES;
211 struct fec_input_device inputs[FEC_INPUT_DEVICES] = {
213 .device = crypt_data_device(cd),
216 .count = params->data_size * params->data_block_size
218 .device = crypt_metadata_device(cd),
220 .start = VERITY_hash_offset_block(params) * params->data_block_size,
221 .count = (VERITY_FEC_blocks(cd, fec_device, params) - params->data_size) * params->data_block_size
225 /* validate parameters */
226 if (params->data_block_size != params->hash_block_size) {
227 log_err(cd, _("Block sizes must match for FEC."));
231 if (params->fec_roots > FEC_RSM - FEC_MIN_RSN ||
232 params->fec_roots < FEC_RSM - FEC_MAX_RSN) {
233 log_err(cd, _("Invalid number of parity bytes."));
237 if (!inputs[0].count) {
238 log_err(cd, _("Invalid FEC segment length."));
241 if (!inputs[1].count)
245 fd = open(device_path(fec_device), O_RDONLY);
247 fd = open(device_path(fec_device), O_RDWR);
250 log_err(cd, _("Cannot open device %s."), device_path(fec_device));
254 if (lseek(fd, params->fec_area_offset, SEEK_SET) < 0) {
255 log_dbg(cd, "Cannot seek to requested position in FEC device.");
260 inputs[0].fd = open(device_path(inputs[0].device), O_RDONLY);
261 if (inputs[0].fd == -1) {
262 log_err(cd, _("Cannot open device %s."), device_path(inputs[0].device));
265 inputs[1].fd = open(device_path(inputs[1].device), O_RDONLY);
266 if (inputs[1].fd == -1) {
267 log_err(cd, _("Cannot open device %s."), device_path(inputs[1].device));
271 r = FEC_process_inputs(cd, params, inputs, ninputs, fd, check_fec, errors);
273 if (inputs[0].fd != -1)
275 if (inputs[1].fd != -1)
283 uint64_t VERITY_FEC_blocks(struct crypt_device *cd,
284 struct device *fec_device,
285 struct crypt_params_verity *params)
290 * FEC covers this data:
291 * | protected data | hash area | padding (optional foreign metadata) |
293 * If hash device is in a separate image, metadata covers the whole rest of the image after hash area.
294 * If hash and FEC device is in the image, metadata ends on the FEC area offset.
296 if (device_is_identical(crypt_metadata_device(cd), fec_device) > 0) {
297 log_dbg(cd, "FEC and hash device is the same.");
298 blocks = params->fec_area_offset;
300 /* cover the entire hash device starting from hash_offset */
301 if (device_size(crypt_metadata_device(cd), &blocks)) {
302 log_err(cd, _("Failed to determine size for device %s."),
303 device_path(crypt_metadata_device(cd)));
308 blocks /= params->data_block_size;
310 blocks -= VERITY_hash_offset_block(params);
313 blocks += params->data_size;