/src/cryptsetup/lib/verity/verity_fec.c

Source
// SPDX-License-Identifier: LGPL-2.1-or-later
/*
 * dm-verity Forward Error Correction (FEC) support
 *
 * Copyright (C) 2015 Google, Inc. All rights reserved.
 * Copyright (C) 2017-2025 Red Hat, Inc. All rights reserved.
 */

#include <stdlib.h>
#include <errno.h>

#include "verity.h"
#include "internal.h"
#include "rs.h"

/* ecc parameters */
#define FEC_RSM 255
#define FEC_MIN_RSN 231
#define FEC_MAX_RSN 253

#define FEC_INPUT_DEVICES 2

/* parameters to init_rs_char */
#define FEC_PARAMS(roots) \
    8,          /* symbol size in bits */ \
    0x11d,      /* field generator polynomial coefficients */ \
    0,          /* first root of the generator */ \
    1,          /* primitive element to generate polynomial roots */ \
    (roots),    /* polynomial degree (number of roots) */ \
    0           /* padding bytes at the front of shortened block */

struct fec_input_device {
  struct device *device;
  int fd;
  uint64_t start;
  uint64_t count;
};

struct fec_context {
  uint32_t rsn;
  uint32_t roots;
  uint64_t size;
  uint64_t blocks;
  uint64_t rounds;
  uint32_t block_size;
  struct fec_input_device *inputs;
  size_t ninputs;
};

/* computes ceil(x / y) */
static inline uint64_t FEC_div_round_up(uint64_t x, uint64_t y)
{
  return (x / y) + (x % y > 0 ? 1 : 0);
}

/* returns a physical offset for the given RS offset */
static inline uint64_t FEC_interleave(struct fec_context *ctx, uint64_t offset)
{
  return (offset / ctx->rsn) +
      (offset % ctx->rsn) * ctx->rounds * ctx->block_size;
}

/* returns data for a byte at the specified RS offset */
static int FEC_read_interleaved(struct fec_context *ctx, uint64_t i,
        void *output, size_t count)
{
  size_t n;
  uint64_t offset = FEC_interleave(ctx, i);

  /* offsets outside input area are assumed to contain zeros */
  if (offset >= ctx->size) {
    memset(output, 0, count);
    return 0;
  }

  /* find the correct input device and read from it */
  for (n = 0; n < ctx->ninputs; ++n) {
    if (offset >= ctx->inputs[n].count) {
      offset -= ctx->inputs[n].count;
      continue;
    }

    /* FIXME: read_lseek_blockwise candidate */
    if (lseek(ctx->inputs[n].fd, ctx->inputs[n].start + offset, SEEK_SET) < 0)
      return -1;
    return (read_buffer(ctx->inputs[n].fd, output, count) == (ssize_t)count) ? 0 : -1;
  }

  /* should never be reached */
  return -1;
}

/* encodes/decode inputs to/from fd */
static int FEC_process_inputs(struct crypt_device *cd,
            struct crypt_params_verity *params,
            struct fec_input_device *inputs,
            size_t ninputs, int fd,
            int decode, unsigned int *errors)
{
  int r = 0;
  unsigned int i;
  struct fec_context ctx;
  uint32_t b;
  uint64_t n;
  uint8_t rs_block[FEC_RSM];
  uint8_t *buf = NULL;
  void *rs;

  /* initialize parameters */
  ctx.roots = params->fec_roots;
  ctx.rsn = FEC_RSM - ctx.roots;
  ctx.block_size = params->data_block_size;
  ctx.inputs = inputs;
  ctx.ninputs = ninputs;

  rs = init_rs_char(FEC_PARAMS(ctx.roots));
  if (!rs) {
    log_err(cd, _("Failed to allocate RS context."));
    return -ENOMEM;
  }

  /* calculate the total area covered by error correction codes */
  ctx.size = 0;
  for (n = 0; n < ctx.ninputs; ++n) {
    log_dbg(cd, "FEC input %s, offset %" PRIu64 " [bytes], length %" PRIu64 " [bytes]",
      device_path(ctx.inputs[n].device), ctx.inputs[n].start, ctx.inputs[n].count);
    ctx.size += ctx.inputs[n].count;
  }

  /* each byte in a data block is covered by a different code */
  ctx.blocks = FEC_div_round_up(ctx.size, ctx.block_size);
  ctx.rounds = FEC_div_round_up(ctx.blocks, ctx.rsn);

  buf = malloc((size_t)ctx.block_size * ctx.rsn);
  if (!buf) {
    log_err(cd, _("Failed to allocate buffer."));
    r = -ENOMEM;
    goto out;
  }

  /* encode/decode input */
  for (n = 0; n < ctx.rounds; ++n) {
    for (i = 0; i < ctx.rsn; ++i) {
      if (FEC_read_interleaved(&ctx, n * ctx.rsn * ctx.block_size + i,
             &buf[i * ctx.block_size], ctx.block_size)) {
        log_err(cd, _("Failed to read RS block %" PRIu64 " byte %d."), n, i);
        r = -EIO;
        goto out;
      }
    }

    for (b = 0; b < ctx.block_size; ++b) {
      for (i = 0; i < ctx.rsn; ++i)
        rs_block[i] = buf[i * ctx.block_size + b];

      /* decoding from parity device */
      if (decode) {
        if (read_buffer(fd, &rs_block[ctx.rsn], ctx.roots) < 0) {
          log_err(cd, _("Failed to read parity for RS block %" PRIu64 "."), n);
          r = -EIO;
          goto out;
        }

        /* coverity[tainted_data] */
        r = decode_rs_char(rs, rs_block);
        if (r < 0) {
          log_err(cd, _("Failed to repair parity for block %" PRIu64 "."), n);
          r = -EPERM;
          goto out;
        }
        /* return number of detected errors */
        if (errors)
          *errors += r;
        r = 0;
      } else {
        /* encoding and writing parity data to fec device */
        encode_rs_char(rs, rs_block, &rs_block[ctx.rsn]);
        if (write_buffer(fd, &rs_block[ctx.rsn], ctx.roots) < 0) {
          log_err(cd, _("Failed to write parity for RS block %" PRIu64 "."), n);
          r = -EIO;
          goto out;
        }
      }
    }
  }
out:
  free_rs_char(rs);
  free(buf);
  return r;
}

static int VERITY_FEC_validate(struct crypt_device *cd, struct crypt_params_verity *params)
{
  if (params->data_block_size != params->hash_block_size) {
    log_err(cd, _("Block sizes must match for FEC."));
    return -EINVAL;
  }

  if (params->fec_roots > FEC_RSM - FEC_MIN_RSN ||
    params->fec_roots < FEC_RSM - FEC_MAX_RSN) {
    log_err(cd, _("Invalid number of parity bytes."));
    return -EINVAL;
  }

  return 0;
}

int VERITY_FEC_process(struct crypt_device *cd,
          struct crypt_params_verity *params,
          struct device *fec_device, int check_fec,
          unsigned int *errors)
{
  int r = -EIO, fd = -1;
  size_t ninputs = FEC_INPUT_DEVICES;
  struct fec_input_device inputs[FEC_INPUT_DEVICES] = {
    {
      .device = crypt_data_device(cd),
      .fd = -1,
      .start = 0,
      .count =  params->data_size * params->data_block_size
    },{
      .device = crypt_metadata_device(cd),
      .fd = -1,
      .start = VERITY_hash_offset_block(params) * params->data_block_size,
      .count = (VERITY_FEC_blocks(cd, fec_device, params) - params->data_size) * params->data_block_size
    }
  };

  /* validate parameters */
  r = VERITY_FEC_validate(cd, params);
  if (r < 0)
    return r;

  if (!inputs[0].count) {
    log_err(cd, _("Invalid FEC segment length."));
    return -EINVAL;
  }
  if (!inputs[1].count)
    ninputs--;

  if (check_fec)
    fd = open(device_path(fec_device), O_RDONLY);
  else
    fd = open(device_path(fec_device), O_RDWR);

  if (fd == -1) {
    log_err(cd, _("Cannot open device %s."), device_path(fec_device));
    goto out;
  }

  if (lseek(fd, params->fec_area_offset, SEEK_SET) < 0) {
    log_dbg(cd, "Cannot seek to requested position in FEC device.");
    goto out;
  }

  /* input devices */
  inputs[0].fd = open(device_path(inputs[0].device), O_RDONLY);
  if (inputs[0].fd == -1) {
    log_err(cd, _("Cannot open device %s."), device_path(inputs[0].device));
    goto out;
  }
  inputs[1].fd = open(device_path(inputs[1].device), O_RDONLY);
  if (inputs[1].fd == -1) {
    log_err(cd, _("Cannot open device %s."), device_path(inputs[1].device));
    goto out;
  }

  r = FEC_process_inputs(cd, params, inputs, ninputs, fd, check_fec, errors);
out:
  if (inputs[0].fd != -1)
    close(inputs[0].fd);
  if (inputs[1].fd != -1)
    close(inputs[1].fd);
  if (fd != -1)
    close(fd);

  return r;
}

/* All blocks that are covered by FEC */
uint64_t VERITY_FEC_blocks(struct crypt_device *cd,
         struct device *fec_device,
         struct crypt_params_verity *params)
{
  uint64_t blocks = 0;

  if (!fec_device || VERITY_FEC_validate(cd, params) < 0)
    return 0;

  /*
  * FEC covers this data:
  *     | protected data | hash area | padding (optional foreign metadata) |
  *
  * If hash device is in a separate image, metadata covers the whole rest of the image after hash area.
  * If hash and FEC device is in the image, metadata ends on the FEC area offset.
  */
  if (device_is_identical(crypt_metadata_device(cd), fec_device) > 0) {
    log_dbg(cd, "FEC and hash device is the same.");
     blocks = params->fec_area_offset;
  } else {
    /* cover the entire hash device starting from hash_offset */
    if (device_size(crypt_metadata_device(cd), &blocks)) {
      log_err(cd, _("Failed to determine size for device %s."),
          device_path(crypt_metadata_device(cd)));
      return 0;
    }
  }

  blocks /= params->data_block_size;
  if (blocks)
    blocks -= VERITY_hash_offset_block(params);

  /* Protected data */
  blocks += params->data_size;

  return blocks;
}

/* Blocks needed to store FEC data, blocks must be validated/calculated by VERITY_FEC_blocks() */
uint64_t VERITY_FEC_RS_blocks(uint64_t blocks, uint32_t roots)
{
  return FEC_div_round_up(blocks, FEC_RSM - roots) * roots;
}

Coverage Report

Created: 2025-10-12 06:56

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