diff options
Diffstat (limited to 'lib')
46 files changed, 1541 insertions, 3174 deletions
diff --git a/lib/.gitignore b/lib/.gitignore index 54596b634ecb..101a4aa92fb5 100644 --- a/lib/.gitignore +++ b/lib/.gitignore @@ -5,5 +5,3 @@ /gen_crc32table /gen_crc64table /oid_registry_data.c -/test_fortify.log -/test_fortify/*.log diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index a81d452941ce..62fce4ce0b16 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -97,7 +97,7 @@ config BOOT_PRINTK_DELAY using "boot_delay=N". It is likely that you would also need to use "lpj=M" to preset - the "loops per jiffie" value. + the "loops per jiffy" value. See a previous boot log for the "lpj" value to use for your system, and then set "lpj=M" before setting "boot_delay=N". NOTE: Using this option may adversely affect SMP systems. @@ -1614,6 +1614,7 @@ config SCF_TORTURE_TEST config CSD_LOCK_WAIT_DEBUG bool "Debugging for csd_lock_wait(), called from smp_call_function*()" depends on DEBUG_KERNEL + depends on SMP depends on 64BIT default n help @@ -2173,6 +2174,14 @@ config KCOV_IRQ_AREA_SIZE soft interrupts. This specifies the size of those areas in the number of unsigned long words. +config KCOV_SELFTEST + bool "Perform short selftests on boot" + depends on KCOV + help + Run short KCOV coverage collection selftests on boot. + On test failure, causes the kernel to panic. Recommended to be + enabled, ensuring critical functionality works as intended. + menuconfig RUNTIME_TESTING_MENU bool "Runtime Testing" default y @@ -2626,6 +2635,7 @@ config RESOURCE_KUNIT_TEST tristate "KUnit test for resource API" if !KUNIT_ALL_TESTS depends on KUNIT default KUNIT_ALL_TESTS + select GET_FREE_REGION help This builds the resource API unit test. Tests the logic of API provided by resource.c and ioport.h. @@ -3061,3 +3071,19 @@ config RUST_KERNEL_DOCTESTS endmenu # "Rust" endmenu # Kernel hacking + +config INT_POW_TEST + tristate "Integer exponentiation (int_pow) test" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + This option enables the KUnit test suite for the int_pow function, + which performs integer exponentiation. The test suite is designed to + verify that the implementation of int_pow correctly computes the power + of a given base raised to a given exponent. + + Enabling this option will include tests that check various scenarios + and edge cases to ensure the accuracy and reliability of the exponentiation + function. + + If unsure, say N diff --git a/lib/Kconfig.ubsan b/lib/Kconfig.ubsan index bdda600f8dfb..1d4aa7a83b3a 100644 --- a/lib/Kconfig.ubsan +++ b/lib/Kconfig.ubsan @@ -29,8 +29,8 @@ config UBSAN_TRAP Also note that selecting Y will cause your kernel to Oops with an "illegal instruction" error with no further details - when a UBSAN violation occurs. (Except on arm64, which will - report which Sanitizer failed.) This may make it hard to + when a UBSAN violation occurs. (Except on arm64 and x86, which + will report which Sanitizer failed.) This may make it hard to determine whether an Oops was caused by UBSAN or to figure out the details of a UBSAN violation. It makes the kernel log output less useful for bug reports. diff --git a/lib/Makefile b/lib/Makefile index 0fde1c360f32..773adf88af41 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -35,7 +35,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ nmi_backtrace.o win_minmax.o memcat_p.o \ - buildid.o objpool.o + buildid.o objpool.o union_find.o lib-$(CONFIG_PRINTK) += dump_stack.o lib-$(CONFIG_SMP) += cpumask.o @@ -394,40 +394,4 @@ obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o obj-$(CONFIG_FIRMWARE_TABLE) += fw_table.o -# FORTIFY_SOURCE compile-time behavior tests -TEST_FORTIFY_SRCS = $(wildcard $(src)/test_fortify/*-*.c) -TEST_FORTIFY_LOGS = $(patsubst $(src)/%.c, %.log, $(TEST_FORTIFY_SRCS)) -TEST_FORTIFY_LOG = test_fortify.log - -quiet_cmd_test_fortify = TEST $@ - cmd_test_fortify = $(CONFIG_SHELL) $(srctree)/scripts/test_fortify.sh \ - $< $@ "$(NM)" $(CC) $(c_flags) \ - $(call cc-disable-warning,fortify-source) \ - -DKBUILD_EXTRA_WARN1 - -targets += $(TEST_FORTIFY_LOGS) -clean-files += $(TEST_FORTIFY_LOGS) -clean-files += $(addsuffix .o, $(TEST_FORTIFY_LOGS)) -$(obj)/test_fortify/%.log: $(src)/test_fortify/%.c \ - $(src)/test_fortify/test_fortify.h \ - $(srctree)/include/linux/fortify-string.h \ - $(srctree)/scripts/test_fortify.sh \ - FORCE - $(call if_changed,test_fortify) - -quiet_cmd_gen_fortify_log = GEN $@ - cmd_gen_fortify_log = cat </dev/null $(filter-out FORCE,$^) 2>/dev/null > $@ || true - -targets += $(TEST_FORTIFY_LOG) -clean-files += $(TEST_FORTIFY_LOG) -$(obj)/$(TEST_FORTIFY_LOG): $(addprefix $(obj)/, $(TEST_FORTIFY_LOGS)) FORCE - $(call if_changed,gen_fortify_log) - -# Fake dependency to trigger the fortify tests. -ifeq ($(CONFIG_FORTIFY_SOURCE),y) -$(obj)/string.o: $(obj)/$(TEST_FORTIFY_LOG) -endif - -# Some architectures define __NO_FORTIFY if __SANITIZE_ADDRESS__ is undefined. -# Pass CFLAGS_KASAN to avoid warnings. -$(foreach x, $(patsubst %.log,%.o,$(TEST_FORTIFY_LOGS)), $(eval KASAN_SANITIZE_$(x) := y)) +subdir-$(CONFIG_FORTIFY_SOURCE) += test_fortify diff --git a/lib/codetag.c b/lib/codetag.c index 5ace625f2328..afa8a2d4f317 100644 --- a/lib/codetag.c +++ b/lib/codetag.c @@ -125,7 +125,6 @@ static inline size_t range_size(const struct codetag_type *cttype, cttype->desc.tag_size; } -#ifdef CONFIG_MODULES static void *get_symbol(struct module *mod, const char *prefix, const char *name) { DECLARE_SEQ_BUF(sb, KSYM_NAME_LEN); @@ -155,6 +154,15 @@ static struct codetag_range get_section_range(struct module *mod, }; } +static const char *get_mod_name(__maybe_unused struct module *mod) +{ +#ifdef CONFIG_MODULES + if (mod) + return mod->name; +#endif + return "(built-in)"; +} + static int codetag_module_init(struct codetag_type *cttype, struct module *mod) { struct codetag_range range; @@ -164,8 +172,7 @@ static int codetag_module_init(struct codetag_type *cttype, struct module *mod) range = get_section_range(mod, cttype->desc.section); if (!range.start || !range.stop) { pr_warn("Failed to load code tags of type %s from the module %s\n", - cttype->desc.section, - mod ? mod->name : "(built-in)"); + cttype->desc.section, get_mod_name(mod)); return -EINVAL; } @@ -199,6 +206,7 @@ static int codetag_module_init(struct codetag_type *cttype, struct module *mod) return 0; } +#ifdef CONFIG_MODULES void codetag_load_module(struct module *mod) { struct codetag_type *cttype; @@ -248,9 +256,6 @@ bool codetag_unload_module(struct module *mod) return unload_ok; } - -#else /* CONFIG_MODULES */ -static int codetag_module_init(struct codetag_type *cttype, struct module *mod) { return 0; } #endif /* CONFIG_MODULES */ struct codetag_type * diff --git a/lib/crypto/mpi/Makefile b/lib/crypto/mpi/Makefile index 6e6ef9a34fe1..9ad84079025a 100644 --- a/lib/crypto/mpi/Makefile +++ b/lib/crypto/mpi/Makefile @@ -13,14 +13,12 @@ mpi-y = \ generic_mpih-rshift.o \ generic_mpih-sub1.o \ generic_mpih-add1.o \ - ec.o \ mpicoder.o \ mpi-add.o \ mpi-bit.o \ mpi-cmp.o \ mpi-sub-ui.o \ mpi-div.o \ - mpi-inv.o \ mpi-mod.o \ mpi-mul.o \ mpih-cmp.o \ diff --git a/lib/crypto/mpi/ec.c b/lib/crypto/mpi/ec.c deleted file mode 100644 index 4781f00982ef..000000000000 --- a/lib/crypto/mpi/ec.c +++ /dev/null @@ -1,1507 +0,0 @@ -/* ec.c - Elliptic Curve functions - * Copyright (C) 2007 Free Software Foundation, Inc. - * Copyright (C) 2013 g10 Code GmbH - * - * This file is part of Libgcrypt. - * - * Libgcrypt is free software; you can redistribute it and/or modify - * it under the terms of the GNU Lesser General Public License as - * published by the Free Software Foundation; either version 2.1 of - * the License, or (at your option) any later version. - * - * Libgcrypt is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this program; if not, see <http://www.gnu.org/licenses/>. - */ - -#include "mpi-internal.h" -#include "longlong.h" - -#define point_init(a) mpi_point_init((a)) -#define point_free(a) mpi_point_free_parts((a)) - -#define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__) -#define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__) - -#define DIM(v) (sizeof(v)/sizeof((v)[0])) - - -/* Create a new point option. NBITS gives the size in bits of one - * coordinate; it is only used to pre-allocate some resources and - * might also be passed as 0 to use a default value. - */ -MPI_POINT mpi_point_new(unsigned int nbits) -{ - MPI_POINT p; - - (void)nbits; /* Currently not used. */ - - p = kmalloc(sizeof(*p), GFP_KERNEL); - if (p) - mpi_point_init(p); - return p; -} -EXPORT_SYMBOL_GPL(mpi_point_new); - -/* Release the point object P. P may be NULL. */ -void mpi_point_release(MPI_POINT p) -{ - if (p) { - mpi_point_free_parts(p); - kfree(p); - } -} -EXPORT_SYMBOL_GPL(mpi_point_release); - -/* Initialize the fields of a point object. gcry_mpi_point_free_parts - * may be used to release the fields. - */ -void mpi_point_init(MPI_POINT p) -{ - p->x = mpi_new(0); - p->y = mpi_new(0); - p->z = mpi_new(0); -} -EXPORT_SYMBOL_GPL(mpi_point_init); - -/* Release the parts of a point object. */ -void mpi_point_free_parts(MPI_POINT p) -{ - mpi_free(p->x); p->x = NULL; - mpi_free(p->y); p->y = NULL; - mpi_free(p->z); p->z = NULL; -} -EXPORT_SYMBOL_GPL(mpi_point_free_parts); - -/* Set the value from S into D. */ -static void point_set(MPI_POINT d, MPI_POINT s) -{ - mpi_set(d->x, s->x); - mpi_set(d->y, s->y); - mpi_set(d->z, s->z); -} - -static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx) -{ - size_t nlimbs = ctx->p->nlimbs; - - mpi_resize(p->x, nlimbs); - p->x->nlimbs = nlimbs; - mpi_resize(p->z, nlimbs); - p->z->nlimbs = nlimbs; - - if (ctx->model != MPI_EC_MONTGOMERY) { - mpi_resize(p->y, nlimbs); - p->y->nlimbs = nlimbs; - } -} - -static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap, - struct mpi_ec_ctx *ctx) -{ - mpi_swap_cond(d->x, s->x, swap); - if (ctx->model != MPI_EC_MONTGOMERY) - mpi_swap_cond(d->y, s->y, swap); - mpi_swap_cond(d->z, s->z, swap); -} - - -/* W = W mod P. */ -static void ec_mod(MPI w, struct mpi_ec_ctx *ec) -{ - if (ec->t.p_barrett) - mpi_mod_barrett(w, w, ec->t.p_barrett); - else - mpi_mod(w, w, ec->p); -} - -static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_add(w, u, v); - ec_mod(w, ctx); -} - -static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec) -{ - mpi_sub(w, u, v); - while (w->sign) - mpi_add(w, w, ec->p); - /*ec_mod(w, ec);*/ -} - -static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_mul(w, u, v); - ec_mod(w, ctx); -} - -/* W = 2 * U mod P. */ -static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx) -{ - mpi_lshift(w, u, 1); - ec_mod(w, ctx); -} - -static void ec_powm(MPI w, const MPI b, const MPI e, - struct mpi_ec_ctx *ctx) -{ - mpi_powm(w, b, e, ctx->p); - /* mpi_abs(w); */ -} - -/* Shortcut for - * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx); - * for easier optimization. - */ -static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx) -{ - /* Using mpi_mul is slightly faster (at least on amd64). */ - /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */ - ec_mulm(w, b, b, ctx); -} - -/* Shortcut for - * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx); - * for easier optimization. - */ -static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx) -{ - mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p); -} - -static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx) -{ - if (!mpi_invm(x, a, ctx->p)) - log_error("ec_invm: inverse does not exist:\n"); -} - -static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up, - mpi_size_t usize, unsigned long set) -{ - mpi_size_t i; - mpi_limb_t mask = ((mpi_limb_t)0) - set; - mpi_limb_t x; - - for (i = 0; i < usize; i++) { - x = mask & (wp[i] ^ up[i]); - wp[i] = wp[i] ^ x; - } -} - -/* Routines for 2^255 - 19. */ - -#define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) - -static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_ptr_t wp, up, vp; - mpi_size_t wsize = LIMB_SIZE_25519; - mpi_limb_t n[LIMB_SIZE_25519]; - mpi_limb_t borrow; - - if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) - log_bug("addm_25519: different sizes\n"); - - memset(n, 0, sizeof(n)); - up = u->d; - vp = v->d; - wp = w->d; - - mpihelp_add_n(wp, up, vp, wsize); - borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); - mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); - mpihelp_add_n(wp, wp, n, wsize); - wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); -} - -static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_ptr_t wp, up, vp; - mpi_size_t wsize = LIMB_SIZE_25519; - mpi_limb_t n[LIMB_SIZE_25519]; - mpi_limb_t borrow; - - if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) - log_bug("subm_25519: different sizes\n"); - - memset(n, 0, sizeof(n)); - up = u->d; - vp = v->d; - wp = w->d; - - borrow = mpihelp_sub_n(wp, up, vp, wsize); - mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); - mpihelp_add_n(wp, wp, n, wsize); - wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); -} - -static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_ptr_t wp, up, vp; - mpi_size_t wsize = LIMB_SIZE_25519; - mpi_limb_t n[LIMB_SIZE_25519*2]; - mpi_limb_t m[LIMB_SIZE_25519+1]; - mpi_limb_t cy; - int msb; - - (void)ctx; - if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) - log_bug("mulm_25519: different sizes\n"); - - up = u->d; - vp = v->d; - wp = w->d; - - mpihelp_mul_n(n, up, vp, wsize); - memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB); - wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); - - memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); - mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB)); - - memcpy(n, m, wsize * BYTES_PER_MPI_LIMB); - cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4); - m[LIMB_SIZE_25519] = cy; - cy = mpihelp_add_n(m, m, n, wsize); - m[LIMB_SIZE_25519] += cy; - cy = mpihelp_add_n(m, m, n, wsize); - m[LIMB_SIZE_25519] += cy; - cy = mpihelp_add_n(m, m, n, wsize); - m[LIMB_SIZE_25519] += cy; - - cy = mpihelp_add_n(wp, wp, m, wsize); - m[LIMB_SIZE_25519] += cy; - - memset(m, 0, wsize * BYTES_PER_MPI_LIMB); - msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); - m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19; - wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); - mpihelp_add_n(wp, wp, m, wsize); - - m[0] = 0; - cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); - mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL)); - mpihelp_add_n(wp, wp, m, wsize); -} - -static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx) -{ - ec_addm_25519(w, u, u, ctx); -} - -static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx) -{ - ec_mulm_25519(w, b, b, ctx); -} - -/* Routines for 2^448 - 2^224 - 1. */ - -#define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) -#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2) - -static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_ptr_t wp, up, vp; - mpi_size_t wsize = LIMB_SIZE_448; - mpi_limb_t n[LIMB_SIZE_448]; - mpi_limb_t cy; - - if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) - log_bug("addm_448: different sizes\n"); - - memset(n, 0, sizeof(n)); - up = u->d; - vp = v->d; - wp = w->d; - - cy = mpihelp_add_n(wp, up, vp, wsize); - mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); - mpihelp_sub_n(wp, wp, n, wsize); -} - -static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_ptr_t wp, up, vp; - mpi_size_t wsize = LIMB_SIZE_448; - mpi_limb_t n[LIMB_SIZE_448]; - mpi_limb_t borrow; - - if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) - log_bug("subm_448: different sizes\n"); - - memset(n, 0, sizeof(n)); - up = u->d; - vp = v->d; - wp = w->d; - - borrow = mpihelp_sub_n(wp, up, vp, wsize); - mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); - mpihelp_add_n(wp, wp, n, wsize); -} - -static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) -{ - mpi_ptr_t wp, up, vp; - mpi_size_t wsize = LIMB_SIZE_448; - mpi_limb_t n[LIMB_SIZE_448*2]; - mpi_limb_t a2[LIMB_SIZE_HALF_448]; - mpi_limb_t a3[LIMB_SIZE_HALF_448]; - mpi_limb_t b0[LIMB_SIZE_HALF_448]; - mpi_limb_t b1[LIMB_SIZE_HALF_448]; - mpi_limb_t cy; - int i; -#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) - mpi_limb_t b1_rest, a3_rest; -#endif - - if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) - log_bug("mulm_448: different sizes\n"); - - up = u->d; - vp = v->d; - wp = w->d; - - mpihelp_mul_n(n, up, vp, wsize); - - for (i = 0; i < (wsize + 1) / 2; i++) { - b0[i] = n[i]; - b1[i] = n[i+wsize/2]; - a2[i] = n[i+wsize]; - a3[i] = n[i+wsize+wsize/2]; - } - -#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) - b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; - a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; - - b1_rest = 0; - a3_rest = 0; - - for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { - mpi_limb_t b1v, a3v; - b1v = b1[i]; - a3v = a3[i]; - b1[i] = (b1_rest << 32) | (b1v >> 32); - a3[i] = (a3_rest << 32) | (a3v >> 32); - b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); - a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); - } -#endif - - cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); - cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); - for (i = 0; i < (wsize + 1) / 2; i++) - wp[i] = b0[i]; -#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) - wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1); -#endif - -#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) - cy = b0[LIMB_SIZE_HALF_448-1] >> 32; -#endif - - cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); - cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); - cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); - cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); -#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) - b1_rest = 0; - for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { - mpi_limb_t b1v = b1[i]; - b1[i] = (b1_rest << 32) | (b1v >> 32); - b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); - } - wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); -#endif - for (i = 0; i < wsize / 2; i++) - wp[i+(wsize + 1) / 2] = b1[i]; - -#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) - cy = b1[LIMB_SIZE_HALF_448-1]; -#endif - - memset(n, 0, wsize * BYTES_PER_MPI_LIMB); - -#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) - n[LIMB_SIZE_HALF_448-1] = cy << 32; -#else - n[LIMB_SIZE_HALF_448] = cy; -#endif - n[0] = cy; - mpihelp_add_n(wp, wp, n, wsize); - - memset(n, 0, wsize * BYTES_PER_MPI_LIMB); - cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); - mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); - mpihelp_add_n(wp, wp, n, wsize); -} - -static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx) -{ - ec_addm_448(w, u, u, ctx); -} - -static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx) -{ - ec_mulm_448(w, b, b, ctx); -} - -struct field_table { - const char *p; - - /* computation routines for the field. */ - void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); - void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); - void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); - void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); - void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); -}; - -static const struct field_table field_table[] = { - { - "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", - ec_addm_25519, - ec_subm_25519, - ec_mulm_25519, - ec_mul2_25519, - ec_pow2_25519 - }, - { - "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" - "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", - ec_addm_448, - ec_subm_448, - ec_mulm_448, - ec_mul2_448, - ec_pow2_448 - }, - { NULL, NULL, NULL, NULL, NULL, NULL }, -}; - -/* Force recomputation of all helper variables. */ -static void mpi_ec_get_reset(struct mpi_ec_ctx *ec) -{ - ec->t.valid.a_is_pminus3 = 0; - ec->t.valid.two_inv_p = 0; -} - -/* Accessor for helper variable. */ -static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec) -{ - MPI tmp; - - if (!ec->t.valid.a_is_pminus3) { - ec->t.valid.a_is_pminus3 = 1; - tmp = mpi_alloc_like(ec->p); - mpi_sub_ui(tmp, ec->p, 3); - ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp); - mpi_free(tmp); - } - - return ec->t.a_is_pminus3; -} - -/* Accessor for helper variable. */ -static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec) -{ - if (!ec->t.valid.two_inv_p) { - ec->t.valid.two_inv_p = 1; - if (!ec->t.two_inv_p) - ec->t.two_inv_p = mpi_alloc(0); - ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec); - } - return ec->t.two_inv_p; -} - -static const char *const curve25519_bad_points[] = { - "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", - "0x0000000000000000000000000000000000000000000000000000000000000000", - "0x0000000000000000000000000000000000000000000000000000000000000001", - "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0", - "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f", - "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec", - "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee", - NULL -}; - -static const char *const curve448_bad_points[] = { - "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" - "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", - "0x00000000000000000000000000000000000000000000000000000000" - "00000000000000000000000000000000000000000000000000000000", - "0x00000000000000000000000000000000000000000000000000000000" - "00000000000000000000000000000000000000000000000000000001", - "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" - "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe", - "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff" - "00000000000000000000000000000000000000000000000000000000", - NULL -}; - -static const char *const *bad_points_table[] = { - curve25519_bad_points, - curve448_bad_points, -}; - -static void mpi_ec_coefficient_normalize(MPI a, MPI p) -{ - if (a->sign) { - mpi_resize(a, p->nlimbs); - mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs); - a->nlimbs = p->nlimbs; - a->sign = 0; - } -} - -/* This function initialized a context for elliptic curve based on the - * field GF(p). P is the prime specifying this field, A is the first - * coefficient. CTX is expected to be zeroized. - */ -void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model, - enum ecc_dialects dialect, - int flags, MPI p, MPI a, MPI b) -{ - int i; - static int use_barrett = -1 /* TODO: 1 or -1 */; - - mpi_ec_coefficient_normalize(a, p); - mpi_ec_coefficient_normalize(b, p); - - /* Fixme: Do we want to check some constraints? e.g. a < p */ - - ctx->model = model; - ctx->dialect = dialect; - ctx->flags = flags; - if (dialect == ECC_DIALECT_ED25519) - ctx->nbits = 256; - else - ctx->nbits = mpi_get_nbits(p); - ctx->p = mpi_copy(p); - ctx->a = mpi_copy(a); - ctx->b = mpi_copy(b); - - ctx->d = NULL; - ctx->t.two_inv_p = NULL; - - ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; - - mpi_ec_get_reset(ctx); - - if (model == MPI_EC_MONTGOMERY) { - for (i = 0; i < DIM(bad_points_table); i++) { - MPI p_candidate = mpi_scanval(bad_points_table[i][0]); - int match_p = !mpi_cmp(ctx->p, p_candidate); - int j; - - mpi_free(p_candidate); - if (!match_p) - continue; - - for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) - ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]); - } - } else { - /* Allocate scratch variables. */ - for (i = 0; i < DIM(ctx->t.scratch); i++) - ctx->t.scratch[i] = mpi_alloc_like(ctx->p); - } - - ctx->addm = ec_addm; - ctx->subm = ec_subm; - ctx->mulm = ec_mulm; - ctx->mul2 = ec_mul2; - ctx->pow2 = ec_pow2; - - for (i = 0; field_table[i].p; i++) { - MPI f_p; - - f_p = mpi_scanval(field_table[i].p); - if (!f_p) - break; - - if (!mpi_cmp(p, f_p)) { - ctx->addm = field_table[i].addm; - ctx->subm = field_table[i].subm; - ctx->mulm = field_table[i].mulm; - ctx->mul2 = field_table[i].mul2; - ctx->pow2 = field_table[i].pow2; - mpi_free(f_p); - - mpi_resize(ctx->a, ctx->p->nlimbs); - ctx->a->nlimbs = ctx->p->nlimbs; - - mpi_resize(ctx->b, ctx->p->nlimbs); - ctx->b->nlimbs = ctx->p->nlimbs; - - for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) - ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; - - break; - } - - mpi_free(f_p); - } -} -EXPORT_SYMBOL_GPL(mpi_ec_init); - -void mpi_ec_deinit(struct mpi_ec_ctx *ctx) -{ - int i; - - mpi_barrett_free(ctx->t.p_barrett); - - /* Domain parameter. */ - mpi_free(ctx->p); - mpi_free(ctx->a); - mpi_free(ctx->b); - mpi_point_release(ctx->G); - mpi_free(ctx->n); - - /* The key. */ - mpi_point_release(ctx->Q); - mpi_free(ctx->d); - - /* Private data of ec.c. */ - mpi_free(ctx->t.two_inv_p); - - for (i = 0; i < DIM(ctx->t.scratch); i++) - mpi_free(ctx->t.scratch[i]); -} -EXPORT_SYMBOL_GPL(mpi_ec_deinit); - -/* Compute the affine coordinates from the projective coordinates in - * POINT. Set them into X and Y. If one coordinate is not required, - * X or Y may be passed as NULL. CTX is the usual context. Returns: 0 - * on success or !0 if POINT is at infinity. - */ -int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx) -{ - if (!mpi_cmp_ui(point->z, 0)) - return -1; - - switch (ctx->model) { - case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */ - { - MPI z1, z2, z3; - - z1 = mpi_new(0); - z2 = mpi_new(0); - ec_invm(z1, point->z, ctx); /* z1 = z^(-1) mod p */ - ec_mulm(z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ - - if (x) - ec_mulm(x, point->x, z2, ctx); - - if (y) { - z3 = mpi_new(0); - ec_mulm(z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ - ec_mulm(y, point->y, z3, ctx); - mpi_free(z3); - } - - mpi_free(z2); - mpi_free(z1); - } - return 0; - - case MPI_EC_MONTGOMERY: - { - if (x) - mpi_set(x, point->x); - - if (y) { - log_fatal("%s: Getting Y-coordinate on %s is not supported\n", - "mpi_ec_get_affine", "Montgomery"); - return -1; - } - } - return 0; - - case MPI_EC_EDWARDS: - { - MPI z; - - z = mpi_new(0); - ec_invm(z, point->z, ctx); - - mpi_resize(z, ctx->p->nlimbs); - z->nlimbs = ctx->p->nlimbs; - - if (x) { - mpi_resize(x, ctx->p->nlimbs); - x->nlimbs = ctx->p->nlimbs; - ctx->mulm(x, point->x, z, ctx); - } - if (y) { - mpi_resize(y, ctx->p->nlimbs); - y->nlimbs = ctx->p->nlimbs; - ctx->mulm(y, point->y, z, ctx); - } - - mpi_free(z); - } - return 0; - - default: - return -1; - } -} -EXPORT_SYMBOL_GPL(mpi_ec_get_affine); - -/* RESULT = 2 * POINT (Weierstrass version). */ -static void dup_point_weierstrass(MPI_POINT result, - MPI_POINT point, struct mpi_ec_ctx *ctx) -{ -#define x3 (result->x) -#define y3 (result->y) -#define z3 (result->z) -#define t1 (ctx->t.scratch[0]) -#define t2 (ctx->t.scratch[1]) -#define t3 (ctx->t.scratch[2]) -#define l1 (ctx->t.scratch[3]) -#define l2 (ctx->t.scratch[4]) -#define l3 (ctx->t.scratch[5]) - - if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) { - /* P_y == 0 || P_z == 0 => [1:1:0] */ - mpi_set_ui(x3, 1); - mpi_set_ui(y3, 1); - mpi_set_ui(z3, 0); - } else { - if (ec_get_a_is_pminus3(ctx)) { - /* Use the faster case. */ - /* L1 = 3(X - Z^2)(X + Z^2) */ - /* T1: used for Z^2. */ - /* T2: used for the right term. */ - ec_pow2(t1, point->z, ctx); - ec_subm(l1, point->x, t1, ctx); - ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); - ec_addm(t2, point->x, t1, ctx); - ec_mulm(l1, l1, t2, ctx); - } else { - /* Standard case. */ - /* L1 = 3X^2 + aZ^4 */ - /* T1: used for aZ^4. */ - ec_pow2(l1, point->x, ctx); - ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); - ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx); - ec_mulm(t1, t1, ctx->a, ctx); - ec_addm(l1, l1, t1, ctx); - } - /* Z3 = 2YZ */ - ec_mulm(z3, point->y, point->z, ctx); - ec_mul2(z3, z3, ctx); - - /* L2 = 4XY^2 */ - /* T2: used for Y2; required later. */ - ec_pow2(t2, point->y, ctx); - ec_mulm(l2, t2, point->x, ctx); - ec_mulm(l2, l2, mpi_const(MPI_C_FOUR), ctx); - - /* X3 = L1^2 - 2L2 */ - /* T1: used for L2^2. */ - ec_pow2(x3, l1, ctx); - ec_mul2(t1, l2, ctx); - ec_subm(x3, x3, t1, ctx); - - /* L3 = 8Y^4 */ - /* T2: taken from above. */ - ec_pow2(t2, t2, ctx); - ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx); - - /* Y3 = L1(L2 - X3) - L3 */ - ec_subm(y3, l2, x3, ctx); - ec_mulm(y3, y3, l1, ctx); - ec_subm(y3, y3, l3, ctx); - } - -#undef x3 -#undef y3 -#undef z3 -#undef t1 -#undef t2 -#undef t3 -#undef l1 -#undef l2 -#undef l3 -} - -/* RESULT = 2 * POINT (Montgomery version). */ -static void dup_point_montgomery(MPI_POINT result, - MPI_POINT point, struct mpi_ec_ctx *ctx) -{ - (void)result; - (void)point; - (void)ctx; - log_fatal("%s: %s not yet supported\n", - "mpi_ec_dup_point", "Montgomery"); -} - -/* RESULT = 2 * POINT (Twisted Edwards version). */ -static void dup_point_edwards(MPI_POINT result, - MPI_POINT point, struct mpi_ec_ctx *ctx) -{ -#define X1 (point->x) -#define Y1 (point->y) -#define Z1 (point->z) -#define X3 (result->x) -#define Y3 (result->y) -#define Z3 (result->z) -#define B (ctx->t.scratch[0]) -#define C (ctx->t.scratch[1]) -#define D (ctx->t.scratch[2]) -#define E (ctx->t.scratch[3]) -#define F (ctx->t.scratch[4]) -#define H (ctx->t.scratch[5]) -#define J (ctx->t.scratch[6]) - - /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */ - - /* B = (X_1 + Y_1)^2 */ - ctx->addm(B, X1, Y1, ctx); - ctx->pow2(B, B, ctx); - - /* C = X_1^2 */ - /* D = Y_1^2 */ - ctx->pow2(C, X1, ctx); - ctx->pow2(D, Y1, ctx); - - /* E = aC */ - if (ctx->dialect == ECC_DIALECT_ED25519) - ctx->subm(E, ctx->p, C, ctx); - else - ctx->mulm(E, ctx->a, C, ctx); - - /* F = E + D */ - ctx->addm(F, E, D, ctx); - - /* H = Z_1^2 */ - ctx->pow2(H, Z1, ctx); - - /* J = F - 2H */ - ctx->mul2(J, H, ctx); - ctx->subm(J, F, J, ctx); - - /* X_3 = (B - C - D) · J */ - ctx->subm(X3, B, C, ctx); - ctx->subm(X3, X3, D, ctx); - ctx->mulm(X3, X3, J, ctx); - - /* Y_3 = F · (E - D) */ - ctx->subm(Y3, E, D, ctx); - ctx->mulm(Y3, Y3, F, ctx); - - /* Z_3 = F · J */ - ctx->mulm(Z3, F, J, ctx); - -#undef X1 -#undef Y1 -#undef Z1 -#undef X3 -#undef Y3 -#undef Z3 -#undef B -#undef C -#undef D -#undef E -#undef F -#undef H -#undef J -} - -/* RESULT = 2 * POINT */ -static void -mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx) -{ - switch (ctx->model) { - case MPI_EC_WEIERSTRASS: - dup_point_weierstrass(result, point, ctx); - break; - case MPI_EC_MONTGOMERY: - dup_point_montgomery(result, point, ctx); - break; - case MPI_EC_EDWARDS: - dup_point_edwards(result, point, ctx); - break; - } -} - -/* RESULT = P1 + P2 (Weierstrass version).*/ -static void add_points_weierstrass(MPI_POINT result, - MPI_POINT p1, MPI_POINT p2, - struct mpi_ec_ctx *ctx) -{ -#define x1 (p1->x) -#define y1 (p1->y) -#define z1 (p1->z) -#define x2 (p2->x) -#define y2 (p2->y) -#define z2 (p2->z) -#define x3 (result->x) -#define y3 (result->y) -#define z3 (result->z) -#define l1 (ctx->t.scratch[0]) -#define l2 (ctx->t.scratch[1]) -#define l3 (ctx->t.scratch[2]) -#define l4 (ctx->t.scratch[3]) -#define l5 (ctx->t.scratch[4]) -#define l6 (ctx->t.scratch[5]) -#define l7 (ctx->t.scratch[6]) -#define l8 (ctx->t.scratch[7]) -#define l9 (ctx->t.scratch[8]) -#define t1 (ctx->t.scratch[9]) -#define t2 (ctx->t.scratch[10]) - - if ((!mpi_cmp(x1, x2)) && (!mpi_cmp(y1, y2)) && (!mpi_cmp(z1, z2))) { - /* Same point; need to call the duplicate function. */ - mpi_ec_dup_point(result, p1, ctx); - } else if (!mpi_cmp_ui(z1, 0)) { - /* P1 is at infinity. */ - mpi_set(x3, p2->x); - mpi_set(y3, p2->y); - mpi_set(z3, p2->z); - } else if (!mpi_cmp_ui(z2, 0)) { - /* P2 is at infinity. */ - mpi_set(x3, p1->x); - mpi_set(y3, p1->y); - mpi_set(z3, p1->z); - } else { - int z1_is_one = !mpi_cmp_ui(z1, 1); - int z2_is_one = !mpi_cmp_ui(z2, 1); - - /* l1 = x1 z2^2 */ - /* l2 = x2 z1^2 */ - if (z2_is_one) - mpi_set(l1, x1); - else { - ec_pow2(l1, z2, ctx); - ec_mulm(l1, l1, x1, ctx); - } - if (z1_is_one) - mpi_set(l2, x2); - else { - ec_pow2(l2, z1, ctx); - ec_mulm(l2, l2, x2, ctx); - } - /* l3 = l1 - l2 */ - ec_subm(l3, l1, l2, ctx); - /* l4 = y1 z2^3 */ - ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx); - ec_mulm(l4, l4, y1, ctx); - /* l5 = y2 z1^3 */ - ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx); - ec_mulm(l5, l5, y2, ctx); - /* l6 = l4 - l5 */ - ec_subm(l6, l4, l5, ctx); - - if (!mpi_cmp_ui(l3, 0)) { - if (!mpi_cmp_ui(l6, 0)) { - /* P1 and P2 are the same - use duplicate function. */ - mpi_ec_dup_point(result, p1, ctx); - } else { - /* P1 is the inverse of P2. */ - mpi_set_ui(x3, 1); - mpi_set_ui(y3, 1); - mpi_set_ui(z3, 0); - } - } else { - /* l7 = l1 + l2 */ - ec_addm(l7, l1, l2, ctx); - /* l8 = l4 + l5 */ - ec_addm(l8, l4, l5, ctx); - /* z3 = z1 z2 l3 */ - ec_mulm(z3, z1, z2, ctx); - ec_mulm(z3, z3, l3, ctx); - /* x3 = l6^2 - l7 l3^2 */ - ec_pow2(t1, l6, ctx); - ec_pow2(t2, l3, ctx); - ec_mulm(t2, t2, l7, ctx); - ec_subm(x3, t1, t2, ctx); - /* l9 = l7 l3^2 - 2 x3 */ - ec_mul2(t1, x3, ctx); - ec_subm(l9, t2, t1, ctx); - /* y3 = (l9 l6 - l8 l3^3)/2 */ - ec_mulm(l9, l9, l6, ctx); - ec_powm(t1, l3, mpi_const(MPI_C_THREE), ctx); /* fixme: Use saved value*/ - ec_mulm(t1, t1, l8, ctx); - ec_subm(y3, l9, t1, ctx); - ec_mulm(y3, y3, ec_get_two_inv_p(ctx), ctx); - } - } - -#undef x1 -#undef y1 -#undef z1 -#undef x2 -#undef y2 -#undef z2 -#undef x3 -#undef y3 -#undef z3 -#undef l1 -#undef l2 -#undef l3 -#undef l4 -#undef l5 -#undef l6 -#undef l7 -#undef l8 -#undef l9 -#undef t1 -#undef t2 -} - -/* RESULT = P1 + P2 (Montgomery version).*/ -static void add_points_montgomery(MPI_POINT result, - MPI_POINT p1, MPI_POINT p2, - struct mpi_ec_ctx *ctx) -{ - (void)result; - (void)p1; - (void)p2; - (void)ctx; - log_fatal("%s: %s not yet supported\n", - "mpi_ec_add_points", "Montgomery"); -} - -/* RESULT = P1 + P2 (Twisted Edwards version).*/ -static void add_points_edwards(MPI_POINT result, - MPI_POINT p1, MPI_POINT p2, - struct mpi_ec_ctx *ctx) -{ -#define X1 (p1->x) -#define Y1 (p1->y) -#define Z1 (p1->z) -#define X2 (p2->x) -#define Y2 (p2->y) -#define Z2 (p2->z) -#define X3 (result->x) -#define Y3 (result->y) -#define Z3 (result->z) -#define A (ctx->t.scratch[0]) -#define B (ctx->t.scratch[1]) -#define C (ctx->t.scratch[2]) -#define D (ctx->t.scratch[3]) -#define E (ctx->t.scratch[4]) -#define F (ctx->t.scratch[5]) -#define G (ctx->t.scratch[6]) -#define tmp (ctx->t.scratch[7]) - - point_resize(result, ctx); - - /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */ - - /* A = Z1 · Z2 */ - ctx->mulm(A, Z1, Z2, ctx); - - /* B = A^2 */ - ctx->pow2(B, A, ctx); - - /* C = X1 · X2 */ - ctx->mulm(C, X1, X2, ctx); - - /* D = Y1 · Y2 */ - ctx->mulm(D, Y1, Y2, ctx); - - /* E = d · C · D */ - ctx->mulm(E, ctx->b, C, ctx); - ctx->mulm(E, E, D, ctx); - - /* F = B - E */ - ctx->subm(F, B, E, ctx); - - /* G = B + E */ - ctx->addm(G, B, E, ctx); - - /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ - ctx->addm(tmp, X1, Y1, ctx); - ctx->addm(X3, X2, Y2, ctx); - ctx->mulm(X3, X3, tmp, ctx); - ctx->subm(X3, X3, C, ctx); - ctx->subm(X3, X3, D, ctx); - ctx->mulm(X3, X3, F, ctx); - ctx->mulm(X3, X3, A, ctx); - - /* Y_3 = A · G · (D - aC) */ - if (ctx->dialect == ECC_DIALECT_ED25519) { - ctx->addm(Y3, D, C, ctx); - } else { - ctx->mulm(Y3, ctx->a, C, ctx); - ctx->subm(Y3, D, Y3, ctx); - } - ctx->mulm(Y3, Y3, G, ctx); - ctx->mulm(Y3, Y3, A, ctx); - - /* Z_3 = F · G */ - ctx->mulm(Z3, F, G, ctx); - - -#undef X1 -#undef Y1 -#undef Z1 -#undef X2 -#undef Y2 -#undef Z2 -#undef X3 -#undef Y3 -#undef Z3 -#undef A -#undef B -#undef C -#undef D -#undef E -#undef F -#undef G -#undef tmp -} - -/* Compute a step of Montgomery Ladder (only use X and Z in the point). - * Inputs: P1, P2, and x-coordinate of DIF = P1 - P1. - * Outputs: PRD = 2 * P1 and SUM = P1 + P2. - */ -static void montgomery_ladder(MPI_POINT prd, MPI_POINT sum, - MPI_POINT p1, MPI_POINT p2, MPI dif_x, - struct mpi_ec_ctx *ctx) -{ - ctx->addm(sum->x, p2->x, p2->z, ctx); - ctx->subm(p2->z, p2->x, p2->z, ctx); - ctx->addm(prd->x, p1->x, p1->z, ctx); - ctx->subm(p1->z, p1->x, p1->z, ctx); - ctx->mulm(p2->x, p1->z, sum->x, ctx); - ctx->mulm(p2->z, prd->x, p2->z, ctx); - ctx->pow2(p1->x, prd->x, ctx); - ctx->pow2(p1->z, p1->z, ctx); - ctx->addm(sum->x, p2->x, p2->z, ctx); - ctx->subm(p2->z, p2->x, p2->z, ctx); - ctx->mulm(prd->x, p1->x, p1->z, ctx); - ctx->subm(p1->z, p1->x, p1->z, ctx); - ctx->pow2(sum->x, sum->x, ctx); - ctx->pow2(sum->z, p2->z, ctx); - ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ - ctx->mulm(sum->z, sum->z, dif_x, ctx); - ctx->addm(prd->z, p1->x, prd->z, ctx); - ctx->mulm(prd->z, prd->z, p1->z, ctx); -} - -/* RESULT = P1 + P2 */ -void mpi_ec_add_points(MPI_POINT result, - MPI_POINT p1, MPI_POINT p2, - struct mpi_ec_ctx *ctx) -{ - switch (ctx->model) { - case MPI_EC_WEIERSTRASS: - add_points_weierstrass(result, p1, p2, ctx); - break; - case MPI_EC_MONTGOMERY: - add_points_montgomery(result, p1, p2, ctx); - break; - case MPI_EC_EDWARDS: - add_points_edwards(result, p1, p2, ctx); - break; - } -} -EXPORT_SYMBOL_GPL(mpi_ec_add_points); - -/* Scalar point multiplication - the main function for ECC. If takes - * an integer SCALAR and a POINT as well as the usual context CTX. - * RESULT will be set to the resulting point. - */ -void mpi_ec_mul_point(MPI_POINT result, - MPI scalar, MPI_POINT point, - struct mpi_ec_ctx *ctx) -{ - MPI x1, y1, z1, k, h, yy; - unsigned int i, loops; - struct gcry_mpi_point p1, p2, p1inv; - - if (ctx->model == MPI_EC_EDWARDS) { - /* Simple left to right binary method. Algorithm 3.27 from - * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott}, - * title = {Guide to Elliptic Curve Cryptography}, - * year = {2003}, isbn = {038795273X}, - * url = {http://www.cacr.math.uwaterloo.ca/ecc/}, - * publisher = {Springer-Verlag New York, Inc.}} - */ - unsigned int nbits; - int j; - - if (mpi_cmp(scalar, ctx->p) >= 0) - nbits = mpi_get_nbits(scalar); - else - nbits = mpi_get_nbits(ctx->p); - - mpi_set_ui(result->x, 0); - mpi_set_ui(result->y, 1); - mpi_set_ui(result->z, 1); - point_resize(point, ctx); - - point_resize(result, ctx); - point_resize(point, ctx); - - for (j = nbits-1; j >= 0; j--) { - mpi_ec_dup_point(result, result, ctx); - if (mpi_test_bit(scalar, j)) - mpi_ec_add_points(result, result, point, ctx); - } - return; - } else if (ctx->model == MPI_EC_MONTGOMERY) { - unsigned int nbits; - int j; - struct gcry_mpi_point p1_, p2_; - MPI_POINT q1, q2, prd, sum; - unsigned long sw; - mpi_size_t rsize; - - /* Compute scalar point multiplication with Montgomery Ladder. - * Note that we don't use Y-coordinate in the points at all. - * RESULT->Y will be filled by zero. - */ - - nbits = mpi_get_nbits(scalar); - point_init(&p1); - point_init(&p2); - point_init(&p1_); - point_init(&p2_); - mpi_set_ui(p1.x, 1); - mpi_free(p2.x); - p2.x = mpi_copy(point->x); - mpi_set_ui(p2.z, 1); - - point_resize(&p1, ctx); - point_resize(&p2, ctx); - point_resize(&p1_, ctx); - point_resize(&p2_, ctx); - - mpi_resize(point->x, ctx->p->nlimbs); - point->x->nlimbs = ctx->p->nlimbs; - - q1 = &p1; - q2 = &p2; - prd = &p1_; - sum = &p2_; - - for (j = nbits-1; j >= 0; j--) { - sw = mpi_test_bit(scalar, j); - point_swap_cond(q1, q2, sw, ctx); - montgomery_ladder(prd, sum, q1, q2, point->x, ctx); - point_swap_cond(prd, sum, sw, ctx); - swap(q1, prd); - swap(q2, sum); - } - - mpi_clear(result->y); - sw = (nbits & 1); - point_swap_cond(&p1, &p1_, sw, ctx); - - rsize = p1.z->nlimbs; - MPN_NORMALIZE(p1.z->d, rsize); - if (rsize == 0) { - mpi_set_ui(result->x, 1); - mpi_set_ui(result->z, 0); - } else { - z1 = mpi_new(0); - ec_invm(z1, p1.z, ctx); - ec_mulm(result->x, p1.x, z1, ctx); - mpi_set_ui(result->z, 1); - mpi_free(z1); - } - - point_free(&p1); - point_free(&p2); - point_free(&p1_); - point_free(&p2_); - return; - } - - x1 = mpi_alloc_like(ctx->p); - y1 = mpi_alloc_like(ctx->p); - h = mpi_alloc_like(ctx->p); - k = mpi_copy(scalar); - yy = mpi_copy(point->y); - - if (mpi_has_sign(k)) { - k->sign = 0; - ec_invm(yy, yy, ctx); - } - - if (!mpi_cmp_ui(point->z, 1)) { - mpi_set(x1, point->x); - mpi_set(y1, yy); - } else { - MPI z2, z3; - - z2 = mpi_alloc_like(ctx->p); - z3 = mpi_alloc_like(ctx->p); - ec_mulm(z2, point->z, point->z, ctx); - ec_mulm(z3, point->z, z2, ctx); - ec_invm(z2, z2, ctx); - ec_mulm(x1, point->x, z2, ctx); - ec_invm(z3, z3, ctx); - ec_mulm(y1, yy, z3, ctx); - mpi_free(z2); - mpi_free(z3); - } - z1 = mpi_copy(mpi_const(MPI_C_ONE)); - - mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h = 3k */ - loops = mpi_get_nbits(h); - if (loops < 2) { - /* If SCALAR is zero, the above mpi_mul sets H to zero and thus - * LOOPs will be zero. To avoid an underflow of I in the main - * loop we set LOOP to 2 and the result to (0,0,0). - */ - loops = 2; - mpi_clear(result->x); - mpi_clear(result->y); - mpi_clear(result->z); - } else { - mpi_set(result->x, point->x); - mpi_set(result->y, yy); - mpi_set(result->z, point->z); - } - mpi_free(yy); yy = NULL; - - p1.x = x1; x1 = NULL; - p1.y = y1; y1 = NULL; - p1.z = z1; z1 = NULL; - point_init(&p2); - point_init(&p1inv); - - /* Invert point: y = p - y mod p */ - point_set(&p1inv, &p1); - ec_subm(p1inv.y, ctx->p, p1inv.y, ctx); - - for (i = loops-2; i > 0; i--) { - mpi_ec_dup_point(result, result, ctx); - if (mpi_test_bit(h, i) == 1 && mpi_test_bit(k, i) == 0) { - point_set(&p2, result); - mpi_ec_add_points(result, &p2, &p1, ctx); - } - if (mpi_test_bit(h, i) == 0 && mpi_test_bit(k, i) == 1) { - point_set(&p2, result); - mpi_ec_add_points(result, &p2, &p1inv, ctx); - } - } - - point_free(&p1); - point_free(&p2); - point_free(&p1inv); - mpi_free(h); - mpi_free(k); -} -EXPORT_SYMBOL_GPL(mpi_ec_mul_point); - -/* Return true if POINT is on the curve described by CTX. */ -int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx) -{ - int res = 0; - MPI x, y, w; - - x = mpi_new(0); - y = mpi_new(0); - w = mpi_new(0); - - /* Check that the point is in range. This needs to be done here and - * not after conversion to affine coordinates. - */ - if (mpi_cmpabs(point->x, ctx->p) >= 0) - goto leave; - if (mpi_cmpabs(point->y, ctx->p) >= 0) - goto leave; - if (mpi_cmpabs(point->z, ctx->p) >= 0) - goto leave; - - switch (ctx->model) { - case MPI_EC_WEIERSTRASS: - { - MPI xxx; - - if (mpi_ec_get_affine(x, y, point, ctx)) - goto leave; - - xxx = mpi_new(0); - - /* y^2 == x^3 + a·x + b */ - ec_pow2(y, y, ctx); - - ec_pow3(xxx, x, ctx); - ec_mulm(w, ctx->a, x, ctx); - ec_addm(w, w, ctx->b, ctx); - ec_addm(w, w, xxx, ctx); - - if (!mpi_cmp(y, w)) - res = 1; - - mpi_free(xxx); - } - break; - - case MPI_EC_MONTGOMERY: - { -#define xx y - /* With Montgomery curve, only X-coordinate is valid. */ - if (mpi_ec_get_affine(x, NULL, point, ctx)) - goto leave; - - /* The equation is: b * y^2 == x^3 + a · x^2 + x */ - /* We check if right hand is quadratic residue or not by - * Euler's criterion. - */ - /* CTX->A has (a-2)/4 and CTX->B has b^-1 */ - ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx); - ec_addm(w, w, mpi_const(MPI_C_TWO), ctx); - ec_mulm(w, w, x, ctx); - ec_pow2(xx, x, ctx); - ec_addm(w, w, xx, ctx); - ec_addm(w, w, mpi_const(MPI_C_ONE), ctx); - ec_mulm(w, w, x, ctx); - ec_mulm(w, w, ctx->b, ctx); -#undef xx - /* Compute Euler's criterion: w^(p-1)/2 */ -#define p_minus1 y - ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx); - mpi_rshift(p_minus1, p_minus1, 1); - ec_powm(w, w, p_minus1, ctx); - - res = !mpi_cmp_ui(w, 1); -#undef p_minus1 - } - break; - - case MPI_EC_EDWARDS: - { - if (mpi_ec_get_affine(x, y, point, ctx)) - goto leave; - - mpi_resize(w, ctx->p->nlimbs); - w->nlimbs = ctx->p->nlimbs; - - /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */ - ctx->pow2(x, x, ctx); - ctx->pow2(y, y, ctx); - if (ctx->dialect == ECC_DIALECT_ED25519) - ctx->subm(w, ctx->p, x, ctx); - else - ctx->mulm(w, ctx->a, x, ctx); - ctx->addm(w, w, y, ctx); - ctx->mulm(x, x, y, ctx); - ctx->mulm(x, x, ctx->b, ctx); - ctx->subm(w, w, x, ctx); - if (!mpi_cmp_ui(w, 1)) - res = 1; - } - break; - } - -leave: - mpi_free(w); - mpi_free(x); - mpi_free(y); - - return res; -} -EXPORT_SYMBOL_GPL(mpi_ec_curve_point); diff --git a/lib/crypto/mpi/mpi-add.c b/lib/crypto/mpi/mpi-add.c index 9056fc5167fc..3015140d4860 100644 --- a/lib/crypto/mpi/mpi-add.c +++ b/lib/crypto/mpi/mpi-add.c @@ -13,62 +13,12 @@ #include "mpi-internal.h" -/**************** - * Add the unsigned integer V to the mpi-integer U and store the - * result in W. U and V may be the same. - */ -void mpi_add_ui(MPI w, MPI u, unsigned long v) -{ - mpi_ptr_t wp, up; - mpi_size_t usize, wsize; - int usign, wsign; - - usize = u->nlimbs; - usign = u->sign; - wsign = 0; - - /* If not space for W (and possible carry), increase space. */ - wsize = usize + 1; - if (w->alloced < wsize) - mpi_resize(w, wsize); - - /* These must be after realloc (U may be the same as W). */ - up = u->d; - wp = w->d; - - if (!usize) { /* simple */ - wp[0] = v; - wsize = v ? 1:0; - } else if (!usign) { /* mpi is not negative */ - mpi_limb_t cy; - cy = mpihelp_add_1(wp, up, usize, v); - wp[usize] = cy; - wsize = usize + cy; - } else { - /* The signs are different. Need exact comparison to determine - * which operand to subtract from which. - */ - if (usize == 1 && up[0] < v) { - wp[0] = v - up[0]; - wsize = 1; - } else { - mpihelp_sub_1(wp, up, usize, v); - /* Size can decrease with at most one limb. */ - wsize = usize - (wp[usize-1] == 0); - wsign = 1; - } - } - - w->nlimbs = wsize; - w->sign = wsign; -} - - -void mpi_add(MPI w, MPI u, MPI v) +int mpi_add(MPI w, MPI u, MPI v) { mpi_ptr_t wp, up, vp; mpi_size_t usize, vsize, wsize; int usign, vsign, wsign; + int err; if (u->nlimbs < v->nlimbs) { /* Swap U and V. */ usize = v->nlimbs; @@ -76,7 +26,9 @@ void mpi_add(MPI w, MPI u, MPI v) vsize = u->nlimbs; vsign = u->sign; wsize = usize + 1; - RESIZE_IF_NEEDED(w, wsize); + err = RESIZE_IF_NEEDED(w, wsize); + if (err) + return err; /* These must be after realloc (u or v may be the same as w). */ up = v->d; vp = u->d; @@ -86,7 +38,9 @@ void mpi_add(MPI w, MPI u, MPI v) vsize = v->nlimbs; vsign = v->sign; wsize = usize + 1; - RESIZE_IF_NEEDED(w, wsize); + err = RESIZE_IF_NEEDED(w, wsize); + if (err) + return err; /* These must be after realloc (u or v may be the same as w). */ up = u->d; vp = v->d; @@ -128,28 +82,37 @@ void mpi_add(MPI w, MPI u, MPI v) w->nlimbs = wsize; w->sign = wsign; + return 0; } EXPORT_SYMBOL_GPL(mpi_add); -void mpi_sub(MPI w, MPI u, MPI v) +int mpi_sub(MPI w, MPI u, MPI v) { - MPI vv = mpi_copy(v); + int err; + MPI vv; + + vv = mpi_copy(v); + if (!vv) + return -ENOMEM; + vv->sign = !vv->sign; - mpi_add(w, u, vv); + err = mpi_add(w, u, vv); mpi_free(vv); + + return err; } EXPORT_SYMBOL_GPL(mpi_sub); -void mpi_addm(MPI w, MPI u, MPI v, MPI m) +int mpi_addm(MPI w, MPI u, MPI v, MPI m) { - mpi_add(w, u, v); - mpi_mod(w, w, m); + return mpi_add(w, u, v) ?: + mpi_mod(w, w, m); } EXPORT_SYMBOL_GPL(mpi_addm); -void mpi_subm(MPI w, MPI u, MPI v, MPI m) +int mpi_subm(MPI w, MPI u, MPI v, MPI m) { - mpi_sub(w, u, v); - mpi_mod(w, w, m); + return mpi_sub(w, u, v) ?: + mpi_mod(w, w, m); } EXPORT_SYMBOL_GPL(mpi_subm); diff --git a/lib/crypto/mpi/mpi-bit.c b/lib/crypto/mpi/mpi-bit.c index e08fc202ea5c..835a2f0622a0 100644 --- a/lib/crypto/mpi/mpi-bit.c +++ b/lib/crypto/mpi/mpi-bit.c @@ -32,7 +32,6 @@ void mpi_normalize(MPI a) for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--) ; } -EXPORT_SYMBOL_GPL(mpi_normalize); /**************** * Return the number of bits in A. @@ -77,9 +76,10 @@ EXPORT_SYMBOL_GPL(mpi_test_bit); /**************** * Set bit N of A. */ -void mpi_set_bit(MPI a, unsigned int n) +int mpi_set_bit(MPI a, unsigned int n) { unsigned int i, limbno, bitno; + int err; limbno = n / BITS_PER_MPI_LIMB; bitno = n % BITS_PER_MPI_LIMB; @@ -87,106 +87,31 @@ void mpi_set_bit(MPI a, unsigned int n) if (limbno >= a->nlimbs) { for (i = a->nlimbs; i < a->alloced; i++) a->d[i] = 0; - mpi_resize(a, limbno+1); + err = mpi_resize(a, limbno+1); + if (err) + return err; a->nlimbs = limbno+1; } a->d[limbno] |= (A_LIMB_1<<bitno); -} - -/**************** - * Set bit N of A. and clear all bits above - */ -void mpi_set_highbit(MPI a, unsigned int n) -{ - unsigned int i, limbno, bitno; - - limbno = n / BITS_PER_MPI_LIMB; - bitno = n % BITS_PER_MPI_LIMB; - - if (limbno >= a->nlimbs) { - for (i = a->nlimbs; i < a->alloced; i++) - a->d[i] = 0; - mpi_resize(a, limbno+1); - a->nlimbs = limbno+1; - } - a->d[limbno] |= (A_LIMB_1<<bitno); - for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++) - a->d[limbno] &= ~(A_LIMB_1 << bitno); - a->nlimbs = limbno+1; -} -EXPORT_SYMBOL_GPL(mpi_set_highbit); - -/**************** - * clear bit N of A and all bits above - */ -void mpi_clear_highbit(MPI a, unsigned int n) -{ - unsigned int limbno, bitno; - - limbno = n / BITS_PER_MPI_LIMB; - bitno = n % BITS_PER_MPI_LIMB; - - if (limbno >= a->nlimbs) - return; /* not allocated, therefore no need to clear bits :-) */ - - for ( ; bitno < BITS_PER_MPI_LIMB; bitno++) - a->d[limbno] &= ~(A_LIMB_1 << bitno); - a->nlimbs = limbno+1; -} - -/**************** - * Clear bit N of A. - */ -void mpi_clear_bit(MPI a, unsigned int n) -{ - unsigned int limbno, bitno; - - limbno = n / BITS_PER_MPI_LIMB; - bitno = n % BITS_PER_MPI_LIMB; - - if (limbno >= a->nlimbs) - return; /* Don't need to clear this bit, it's far too left. */ - a->d[limbno] &= ~(A_LIMB_1 << bitno); -} -EXPORT_SYMBOL_GPL(mpi_clear_bit); - - -/**************** - * Shift A by COUNT limbs to the right - * This is used only within the MPI library - */ -void mpi_rshift_limbs(MPI a, unsigned int count) -{ - mpi_ptr_t ap = a->d; - mpi_size_t n = a->nlimbs; - unsigned int i; - - if (count >= n) { - a->nlimbs = 0; - return; - } - - for (i = 0; i < n - count; i++) - ap[i] = ap[i+count]; - ap[i] = 0; - a->nlimbs -= count; + return 0; } /* * Shift A by N bits to the right. */ -void mpi_rshift(MPI x, MPI a, unsigned int n) +int mpi_rshift(MPI x, MPI a, unsigned int n) { mpi_size_t xsize; unsigned int i; unsigned int nlimbs = (n/BITS_PER_MPI_LIMB); unsigned int nbits = (n%BITS_PER_MPI_LIMB); + int err; if (x == a) { /* In-place operation. */ if (nlimbs >= x->nlimbs) { x->nlimbs = 0; - return; + return 0; } if (nlimbs) { @@ -201,7 +126,9 @@ void mpi_rshift(MPI x, MPI a, unsigned int n) /* Copy and shift by more or equal bits than in a limb. */ xsize = a->nlimbs; x->sign = a->sign; - RESIZE_IF_NEEDED(x, xsize); + err = RESIZE_IF_NEEDED(x, xsize); + if (err) + return err; x->nlimbs = xsize; for (i = 0; i < a->nlimbs; i++) x->d[i] = a->d[i]; @@ -209,7 +136,7 @@ void mpi_rshift(MPI x, MPI a, unsigned int n) if (nlimbs >= x->nlimbs) { x->nlimbs = 0; - return; + return 0; } for (i = 0; i < x->nlimbs - nlimbs; i++) @@ -223,7 +150,9 @@ void mpi_rshift(MPI x, MPI a, unsigned int n) /* Copy and shift by less than bits in a limb. */ xsize = a->nlimbs; x->sign = a->sign; - RESIZE_IF_NEEDED(x, xsize); + err = RESIZE_IF_NEEDED(x, xsize); + if (err) + return err; x->nlimbs = xsize; if (xsize) { @@ -239,68 +168,7 @@ void mpi_rshift(MPI x, MPI a, unsigned int n) } } MPN_NORMALIZE(x->d, x->nlimbs); -} -EXPORT_SYMBOL_GPL(mpi_rshift); - -/**************** - * Shift A by COUNT limbs to the left - * This is used only within the MPI library - */ -void mpi_lshift_limbs(MPI a, unsigned int count) -{ - mpi_ptr_t ap; - int n = a->nlimbs; - int i; - if (!count || !n) - return; - - RESIZE_IF_NEEDED(a, n+count); - - ap = a->d; - for (i = n-1; i >= 0; i--) - ap[i+count] = ap[i]; - for (i = 0; i < count; i++) - ap[i] = 0; - a->nlimbs += count; -} - -/* - * Shift A by N bits to the left. - */ -void mpi_lshift(MPI x, MPI a, unsigned int n) -{ - unsigned int nlimbs = (n/BITS_PER_MPI_LIMB); - unsigned int nbits = (n%BITS_PER_MPI_LIMB); - - if (x == a && !n) - return; /* In-place shift with an amount of zero. */ - - if (x != a) { - /* Copy A to X. */ - unsigned int alimbs = a->nlimbs; - int asign = a->sign; - mpi_ptr_t xp, ap; - - RESIZE_IF_NEEDED(x, alimbs+nlimbs+1); - xp = x->d; - ap = a->d; - MPN_COPY(xp, ap, alimbs); - x->nlimbs = alimbs; - x->flags = a->flags; - x->sign = asign; - } - - if (nlimbs && !nbits) { - /* Shift a full number of limbs. */ - mpi_lshift_limbs(x, nlimbs); - } else if (n) { - /* We use a very dump approach: Shift left by the number of - * limbs plus one and than fix it up by an rshift. - */ - mpi_lshift_limbs(x, nlimbs+1); - mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits); - } - - MPN_NORMALIZE(x->d, x->nlimbs); + return 0; } +EXPORT_SYMBOL_GPL(mpi_rshift); diff --git a/lib/crypto/mpi/mpi-cmp.c b/lib/crypto/mpi/mpi-cmp.c index 0835b6213235..ceaebe181cd7 100644 --- a/lib/crypto/mpi/mpi-cmp.c +++ b/lib/crypto/mpi/mpi-cmp.c @@ -45,54 +45,28 @@ int mpi_cmp_ui(MPI u, unsigned long v) } EXPORT_SYMBOL_GPL(mpi_cmp_ui); -static int do_mpi_cmp(MPI u, MPI v, int absmode) +int mpi_cmp(MPI u, MPI v) { - mpi_size_t usize; - mpi_size_t vsize; - int usign; - int vsign; + mpi_size_t usize, vsize; int cmp; mpi_normalize(u); mpi_normalize(v); - usize = u->nlimbs; vsize = v->nlimbs; - usign = absmode ? 0 : u->sign; - vsign = absmode ? 0 : v->sign; - - /* Compare sign bits. */ - - if (!usign && vsign) + if (!u->sign && v->sign) return 1; - if (usign && !vsign) + if (u->sign && !v->sign) return -1; - - /* U and V are either both positive or both negative. */ - - if (usize != vsize && !usign && !vsign) + if (usize != vsize && !u->sign && !v->sign) return usize - vsize; - if (usize != vsize && usign && vsign) - return vsize + usize; + if (usize != vsize && u->sign && v->sign) + return vsize - usize; if (!usize) return 0; cmp = mpihelp_cmp(u->d, v->d, usize); - if (!cmp) - return 0; - if ((cmp < 0?1:0) == (usign?1:0)) - return 1; - - return -1; -} - -int mpi_cmp(MPI u, MPI v) -{ - return do_mpi_cmp(u, v, 0); + if (u->sign) + return -cmp; + return cmp; } EXPORT_SYMBOL_GPL(mpi_cmp); - -int mpi_cmpabs(MPI u, MPI v) -{ - return do_mpi_cmp(u, v, 1); -} -EXPORT_SYMBOL_GPL(mpi_cmpabs); diff --git a/lib/crypto/mpi/mpi-div.c b/lib/crypto/mpi/mpi-div.c index 45beab8b9e9e..6e5044e72595 100644 --- a/lib/crypto/mpi/mpi-div.c +++ b/lib/crypto/mpi/mpi-div.c @@ -14,13 +14,13 @@ #include "mpi-internal.h" #include "longlong.h" -void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den); -void mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor); +int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den); -void mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) +int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) { int divisor_sign = divisor->sign; MPI temp_divisor = NULL; + int err; /* We need the original value of the divisor after the remainder has been * preliminary calculated. We have to copy it to temporary space if it's @@ -28,44 +28,22 @@ void mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) */ if (rem == divisor) { temp_divisor = mpi_copy(divisor); + if (!temp_divisor) + return -ENOMEM; divisor = temp_divisor; } - mpi_tdiv_r(rem, dividend, divisor); + err = mpi_tdiv_r(rem, dividend, divisor); + if (err) + goto free_temp_divisor; if (((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs) - mpi_add(rem, rem, divisor); + err = mpi_add(rem, rem, divisor); - if (temp_divisor) - mpi_free(temp_divisor); -} +free_temp_divisor: + mpi_free(temp_divisor); -void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor) -{ - MPI tmp = mpi_alloc(mpi_get_nlimbs(quot)); - mpi_fdiv_qr(quot, tmp, dividend, divisor); - mpi_free(tmp); -} - -void mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor) -{ - int divisor_sign = divisor->sign; - MPI temp_divisor = NULL; - - if (quot == divisor || rem == divisor) { - temp_divisor = mpi_copy(divisor); - divisor = temp_divisor; - } - - mpi_tdiv_qr(quot, rem, dividend, divisor); - - if ((divisor_sign ^ dividend->sign) && rem->nlimbs) { - mpi_sub_ui(quot, quot, 1); - mpi_add(rem, rem, divisor); - } - - if (temp_divisor) - mpi_free(temp_divisor); + return err; } /* If den == quot, den needs temporary storage. @@ -75,12 +53,12 @@ void mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor) * i.e no extra storage should be allocated. */ -void mpi_tdiv_r(MPI rem, MPI num, MPI den) +int mpi_tdiv_r(MPI rem, MPI num, MPI den) { - mpi_tdiv_qr(NULL, rem, num, den); + return mpi_tdiv_qr(NULL, rem, num, den); } -void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) +int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) { mpi_ptr_t np, dp; mpi_ptr_t qp, rp; @@ -93,13 +71,16 @@ void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) mpi_limb_t q_limb; mpi_ptr_t marker[5]; int markidx = 0; + int err; /* Ensure space is enough for quotient and remainder. * We need space for an extra limb in the remainder, because it's * up-shifted (normalized) below. */ rsize = nsize + 1; - mpi_resize(rem, rsize); + err = mpi_resize(rem, rsize); + if (err) + return err; qsize = rsize - dsize; /* qsize cannot be bigger than this. */ if (qsize <= 0) { @@ -115,11 +96,14 @@ void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) quot->nlimbs = 0; quot->sign = 0; } - return; + return 0; } - if (quot) - mpi_resize(quot, qsize); + if (quot) { + err = mpi_resize(quot, qsize); + if (err) + return err; + } /* Read pointers here, when reallocation is finished. */ np = num->d; @@ -141,10 +125,10 @@ void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) rsize = rlimb != 0?1:0; rem->nlimbs = rsize; rem->sign = sign_remainder; - return; + return 0; } - + err = -ENOMEM; if (quot) { qp = quot->d; /* Make sure QP and NP point to different objects. Otherwise the @@ -152,6 +136,8 @@ void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) */ if (qp == np) { /* Copy NP object to temporary space. */ np = marker[markidx++] = mpi_alloc_limb_space(nsize); + if (!np) + goto out_free_marker; MPN_COPY(np, qp, nsize); } } else /* Put quotient at top of remainder. */ @@ -172,6 +158,8 @@ void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) * the original contents of the denominator. */ tp = marker[markidx++] = mpi_alloc_limb_space(dsize); + if (!tp) + goto out_free_marker; mpihelp_lshift(tp, dp, dsize, normalization_steps); dp = tp; @@ -193,6 +181,8 @@ void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) mpi_ptr_t tp; tp = marker[markidx++] = mpi_alloc_limb_space(dsize); + if (!tp) + goto out_free_marker; MPN_COPY(tp, dp, dsize); dp = tp; } @@ -227,8 +217,14 @@ void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) rem->nlimbs = rsize; rem->sign = sign_remainder; + + err = 0; + +out_free_marker: while (markidx) { markidx--; mpi_free_limb_space(marker[markidx]); } + + return err; } diff --git a/lib/crypto/mpi/mpi-internal.h b/lib/crypto/mpi/mpi-internal.h index 554002182db1..8a4f49e3043c 100644 --- a/lib/crypto/mpi/mpi-internal.h +++ b/lib/crypto/mpi/mpi-internal.h @@ -52,11 +52,12 @@ typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */ typedef int mpi_size_t; /* (must be a signed type) */ -#define RESIZE_IF_NEEDED(a, b) \ - do { \ - if ((a)->alloced < (b)) \ - mpi_resize((a), (b)); \ - } while (0) +static inline int RESIZE_IF_NEEDED(MPI a, unsigned b) +{ + if (a->alloced < b) + return mpi_resize(a, b); + return 0; +} /* Copy N limbs from S to D. */ #define MPN_COPY(d, s, n) \ @@ -66,14 +67,6 @@ typedef int mpi_size_t; /* (must be a signed type) */ (d)[_i] = (s)[_i]; \ } while (0) -#define MPN_COPY_INCR(d, s, n) \ - do { \ - mpi_size_t _i; \ - for (_i = 0; _i < (n); _i++) \ - (d)[_i] = (s)[_i]; \ - } while (0) - - #define MPN_COPY_DECR(d, s, n) \ do { \ mpi_size_t _i; \ @@ -181,8 +174,6 @@ int mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size); void mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace); -void mpihelp_mul_n(mpi_ptr_t prodp, - mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size); int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, diff --git a/lib/crypto/mpi/mpi-inv.c b/lib/crypto/mpi/mpi-inv.c deleted file mode 100644 index 61e37d18f793..000000000000 --- a/lib/crypto/mpi/mpi-inv.c +++ /dev/null @@ -1,143 +0,0 @@ -/* mpi-inv.c - MPI functions - * Copyright (C) 1998, 2001, 2002, 2003 Free Software Foundation, Inc. - * - * This file is part of Libgcrypt. - * - * Libgcrypt is free software; you can redistribute it and/or modify - * it under the terms of the GNU Lesser General Public License as - * published by the Free Software Foundation; either version 2.1 of - * the License, or (at your option) any later version. - * - * Libgcrypt is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this program; if not, see <http://www.gnu.org/licenses/>. - */ - -#include "mpi-internal.h" - -/**************** - * Calculate the multiplicative inverse X of A mod N - * That is: Find the solution x for - * 1 = (a*x) mod n - */ -int mpi_invm(MPI x, MPI a, MPI n) -{ - /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X) - * modified according to Michael Penk's solution for Exercise 35 - * with further enhancement - */ - MPI u, v, u1, u2 = NULL, u3, v1, v2 = NULL, v3, t1, t2 = NULL, t3; - unsigned int k; - int sign; - int odd; - - if (!mpi_cmp_ui(a, 0)) - return 0; /* Inverse does not exists. */ - if (!mpi_cmp_ui(n, 1)) - return 0; /* Inverse does not exists. */ - - u = mpi_copy(a); - v = mpi_copy(n); - - for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) { - mpi_rshift(u, u, 1); - mpi_rshift(v, v, 1); - } - odd = mpi_test_bit(v, 0); - - u1 = mpi_alloc_set_ui(1); - if (!odd) - u2 = mpi_alloc_set_ui(0); - u3 = mpi_copy(u); - v1 = mpi_copy(v); - if (!odd) { - v2 = mpi_alloc(mpi_get_nlimbs(u)); - mpi_sub(v2, u1, u); /* U is used as const 1 */ - } - v3 = mpi_copy(v); - if (mpi_test_bit(u, 0)) { /* u is odd */ - t1 = mpi_alloc_set_ui(0); - if (!odd) { - t2 = mpi_alloc_set_ui(1); - t2->sign = 1; - } - t3 = mpi_copy(v); - t3->sign = !t3->sign; - goto Y4; - } else { - t1 = mpi_alloc_set_ui(1); - if (!odd) - t2 = mpi_alloc_set_ui(0); - t3 = mpi_copy(u); - } - - do { - do { - if (!odd) { - if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) { - /* one is odd */ - mpi_add(t1, t1, v); - mpi_sub(t2, t2, u); - } - mpi_rshift(t1, t1, 1); - mpi_rshift(t2, t2, 1); - mpi_rshift(t3, t3, 1); - } else { - if (mpi_test_bit(t1, 0)) - mpi_add(t1, t1, v); - mpi_rshift(t1, t1, 1); - mpi_rshift(t3, t3, 1); - } -Y4: - ; - } while (!mpi_test_bit(t3, 0)); /* while t3 is even */ - - if (!t3->sign) { - mpi_set(u1, t1); - if (!odd) - mpi_set(u2, t2); - mpi_set(u3, t3); - } else { - mpi_sub(v1, v, t1); - sign = u->sign; u->sign = !u->sign; - if (!odd) - mpi_sub(v2, u, t2); - u->sign = sign; - sign = t3->sign; t3->sign = !t3->sign; - mpi_set(v3, t3); - t3->sign = sign; - } - mpi_sub(t1, u1, v1); - if (!odd) - mpi_sub(t2, u2, v2); - mpi_sub(t3, u3, v3); - if (t1->sign) { - mpi_add(t1, t1, v); - if (!odd) - mpi_sub(t2, t2, u); - } - } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */ - /* mpi_lshift( u3, k ); */ - mpi_set(x, u1); - - mpi_free(u1); - mpi_free(v1); - mpi_free(t1); - if (!odd) { - mpi_free(u2); - mpi_free(v2); - mpi_free(t2); - } - mpi_free(u3); - mpi_free(v3); - mpi_free(t3); - - mpi_free(u); - mpi_free(v); - return 1; -} -EXPORT_SYMBOL_GPL(mpi_invm); diff --git a/lib/crypto/mpi/mpi-mod.c b/lib/crypto/mpi/mpi-mod.c index 54fcc01564d9..d5fdaec3d0b6 100644 --- a/lib/crypto/mpi/mpi-mod.c +++ b/lib/crypto/mpi/mpi-mod.c @@ -5,153 +5,9 @@ * This file is part of Libgcrypt. */ - #include "mpi-internal.h" -#include "longlong.h" - -/* Context used with Barrett reduction. */ -struct barrett_ctx_s { - MPI m; /* The modulus - may not be modified. */ - int m_copied; /* If true, M needs to be released. */ - int k; - MPI y; - MPI r1; /* Helper MPI. */ - MPI r2; /* Helper MPI. */ - MPI r3; /* Helper MPI allocated on demand. */ -}; - - - -void mpi_mod(MPI rem, MPI dividend, MPI divisor) -{ - mpi_fdiv_r(rem, dividend, divisor); -} - -/* This function returns a new context for Barrett based operations on - * the modulus M. This context needs to be released using - * _gcry_mpi_barrett_free. If COPY is true M will be transferred to - * the context and the user may change M. If COPY is false, M may not - * be changed until gcry_mpi_barrett_free has been called. - */ -mpi_barrett_t mpi_barrett_init(MPI m, int copy) -{ - mpi_barrett_t ctx; - MPI tmp; - - mpi_normalize(m); - ctx = kcalloc(1, sizeof(*ctx), GFP_KERNEL); - if (!ctx) - return NULL; - - if (copy) { - ctx->m = mpi_copy(m); - ctx->m_copied = 1; - } else - ctx->m = m; - - ctx->k = mpi_get_nlimbs(m); - tmp = mpi_alloc(ctx->k + 1); - - /* Barrett precalculation: y = floor(b^(2k) / m). */ - mpi_set_ui(tmp, 1); - mpi_lshift_limbs(tmp, 2 * ctx->k); - mpi_fdiv_q(tmp, tmp, m); - - ctx->y = tmp; - ctx->r1 = mpi_alloc(2 * ctx->k + 1); - ctx->r2 = mpi_alloc(2 * ctx->k + 1); - - return ctx; -} - -void mpi_barrett_free(mpi_barrett_t ctx) -{ - if (ctx) { - mpi_free(ctx->y); - mpi_free(ctx->r1); - mpi_free(ctx->r2); - if (ctx->r3) - mpi_free(ctx->r3); - if (ctx->m_copied) - mpi_free(ctx->m); - kfree(ctx); - } -} - - -/* R = X mod M - * - * Using Barrett reduction. Before using this function - * _gcry_mpi_barrett_init must have been called to do the - * precalculations. CTX is the context created by this precalculation - * and also conveys M. If the Barret reduction could no be done a - * straightforward reduction method is used. - * - * We assume that these conditions are met: - * Input: x =(x_2k-1 ...x_0)_b - * m =(m_k-1 ....m_0)_b with m_k-1 != 0 - * Output: r = x mod m - */ -void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx) -{ - MPI m = ctx->m; - int k = ctx->k; - MPI y = ctx->y; - MPI r1 = ctx->r1; - MPI r2 = ctx->r2; - int sign; - - mpi_normalize(x); - if (mpi_get_nlimbs(x) > 2*k) { - mpi_mod(r, x, m); - return; - } - - sign = x->sign; - x->sign = 0; - - /* 1. q1 = floor( x / b^k-1) - * q2 = q1 * y - * q3 = floor( q2 / b^k+1 ) - * Actually, we don't need qx, we can work direct on r2 - */ - mpi_set(r2, x); - mpi_rshift_limbs(r2, k-1); - mpi_mul(r2, r2, y); - mpi_rshift_limbs(r2, k+1); - - /* 2. r1 = x mod b^k+1 - * r2 = q3 * m mod b^k+1 - * r = r1 - r2 - * 3. if r < 0 then r = r + b^k+1 - */ - mpi_set(r1, x); - if (r1->nlimbs > k+1) /* Quick modulo operation. */ - r1->nlimbs = k+1; - mpi_mul(r2, r2, m); - if (r2->nlimbs > k+1) /* Quick modulo operation. */ - r2->nlimbs = k+1; - mpi_sub(r, r1, r2); - - if (mpi_has_sign(r)) { - if (!ctx->r3) { - ctx->r3 = mpi_alloc(k + 2); - mpi_set_ui(ctx->r3, 1); - mpi_lshift_limbs(ctx->r3, k + 1); - } - mpi_add(r, r, ctx->r3); - } - - /* 4. while r >= m do r = r - m */ - while (mpi_cmp(r, m) >= 0) - mpi_sub(r, r, m); - - x->sign = sign; -} - -void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx) +int mpi_mod(MPI rem, MPI dividend, MPI divisor) { - mpi_mul(w, u, v); - mpi_mod_barrett(w, w, ctx); + return mpi_fdiv_r(rem, dividend, divisor); } diff --git a/lib/crypto/mpi/mpi-mul.c b/lib/crypto/mpi/mpi-mul.c index 7f4eda8560dc..892a246216b9 100644 --- a/lib/crypto/mpi/mpi-mul.c +++ b/lib/crypto/mpi/mpi-mul.c @@ -13,7 +13,7 @@ #include "mpi-internal.h" -void mpi_mul(MPI w, MPI u, MPI v) +int mpi_mul(MPI w, MPI u, MPI v) { mpi_size_t usize, vsize, wsize; mpi_ptr_t up, vp, wp; @@ -21,6 +21,7 @@ void mpi_mul(MPI w, MPI u, MPI v) int usign, vsign, sign_product; int assign_wp = 0; mpi_ptr_t tmp_limb = NULL; + int err; if (u->nlimbs < v->nlimbs) { /* Swap U and V. */ @@ -46,15 +47,21 @@ void mpi_mul(MPI w, MPI u, MPI v) if (w->alloced < wsize) { if (wp == up || wp == vp) { wp = mpi_alloc_limb_space(wsize); + if (!wp) + return -ENOMEM; assign_wp = 1; } else { - mpi_resize(w, wsize); + err = mpi_resize(w, wsize); + if (err) + return err; wp = w->d; } } else { /* Make U and V not overlap with W. */ if (wp == up) { /* W and U are identical. Allocate temporary space for U. */ up = tmp_limb = mpi_alloc_limb_space(usize); + if (!up) + return -ENOMEM; /* Is V identical too? Keep it identical with U. */ if (wp == vp) vp = up; @@ -63,6 +70,8 @@ void mpi_mul(MPI w, MPI u, MPI v) } else if (wp == vp) { /* W and V are identical. Allocate temporary space for V. */ vp = tmp_limb = mpi_alloc_limb_space(vsize); + if (!vp) + return -ENOMEM; /* Copy to the temporary space. */ MPN_COPY(vp, wp, vsize); } @@ -71,7 +80,12 @@ void mpi_mul(MPI w, MPI u, MPI v) if (!vsize) wsize = 0; else { - mpihelp_mul(wp, up, usize, vp, vsize, &cy); + err = mpihelp_mul(wp, up, usize, vp, vsize, &cy); + if (err) { + if (assign_wp) + mpi_free_limb_space(wp); + goto free_tmp_limb; + } wsize -= cy ? 0:1; } @@ -79,14 +93,17 @@ void mpi_mul(MPI w, MPI u, MPI v) mpi_assign_limb_space(w, wp, wsize); w->nlimbs = wsize; w->sign = sign_product; + +free_tmp_limb: if (tmp_limb) mpi_free_limb_space(tmp_limb); + return err; } EXPORT_SYMBOL_GPL(mpi_mul); -void mpi_mulm(MPI w, MPI u, MPI v, MPI m) +int mpi_mulm(MPI w, MPI u, MPI v, MPI m) { - mpi_mul(w, u, v); - mpi_tdiv_r(w, w, m); + return mpi_mul(w, u, v) ?: + mpi_tdiv_r(w, w, m); } EXPORT_SYMBOL_GPL(mpi_mulm); diff --git a/lib/crypto/mpi/mpicoder.c b/lib/crypto/mpi/mpicoder.c index 3cb6bd148fa9..dde01030807d 100644 --- a/lib/crypto/mpi/mpicoder.c +++ b/lib/crypto/mpi/mpicoder.c @@ -25,7 +25,6 @@ #include <linux/string.h> #include "mpi-internal.h" -#define MAX_EXTERN_SCAN_BYTES (16*1024*1024) #define MAX_EXTERN_MPI_BITS 16384 /** @@ -110,112 +109,6 @@ MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread) } EXPORT_SYMBOL_GPL(mpi_read_from_buffer); -/**************** - * Fill the mpi VAL from the hex string in STR. - */ -int mpi_fromstr(MPI val, const char *str) -{ - int sign = 0; - int prepend_zero = 0; - int i, j, c, c1, c2; - unsigned int nbits, nbytes, nlimbs; - mpi_limb_t a; - - if (*str == '-') { - sign = 1; - str++; - } - - /* Skip optional hex prefix. */ - if (*str == '0' && str[1] == 'x') - str += 2; - - nbits = strlen(str); - if (nbits > MAX_EXTERN_SCAN_BYTES) { - mpi_clear(val); - return -EINVAL; - } - nbits *= 4; - if ((nbits % 8)) - prepend_zero = 1; - - nbytes = (nbits+7) / 8; - nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; - - if (val->alloced < nlimbs) - mpi_resize(val, nlimbs); - - i = BYTES_PER_MPI_LIMB - (nbytes % BYTES_PER_MPI_LIMB); - i %= BYTES_PER_MPI_LIMB; - j = val->nlimbs = nlimbs; - val->sign = sign; - for (; j > 0; j--) { - a = 0; - for (; i < BYTES_PER_MPI_LIMB; i++) { - if (prepend_zero) { - c1 = '0'; - prepend_zero = 0; - } else - c1 = *str++; - - if (!c1) { - mpi_clear(val); - return -EINVAL; - } - c2 = *str++; - if (!c2) { - mpi_clear(val); - return -EINVAL; - } - if (c1 >= '0' && c1 <= '9') - c = c1 - '0'; - else if (c1 >= 'a' && c1 <= 'f') - c = c1 - 'a' + 10; - else if (c1 >= 'A' && c1 <= 'F') - c = c1 - 'A' + 10; - else { - mpi_clear(val); - return -EINVAL; - } - c <<= 4; - if (c2 >= '0' && c2 <= '9') - c |= c2 - '0'; - else if (c2 >= 'a' && c2 <= 'f') - c |= c2 - 'a' + 10; - else if (c2 >= 'A' && c2 <= 'F') - c |= c2 - 'A' + 10; - else { - mpi_clear(val); - return -EINVAL; - } - a <<= 8; - a |= c; - } - i = 0; - val->d[j-1] = a; - } - - return 0; -} -EXPORT_SYMBOL_GPL(mpi_fromstr); - -MPI mpi_scanval(const char *string) -{ - MPI a; - - a = mpi_alloc(0); - if (!a) - return NULL; - - if (mpi_fromstr(a, string)) { - mpi_free(a); - return NULL; - } - mpi_normalize(a); - return a; -} -EXPORT_SYMBOL_GPL(mpi_scanval); - static int count_lzeros(MPI a) { mpi_limb_t alimb; @@ -521,232 +414,3 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) return val; } EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl); - -/* Perform a two's complement operation on buffer P of size N bytes. */ -static void twocompl(unsigned char *p, unsigned int n) -{ - int i; - - for (i = n-1; i >= 0 && !p[i]; i--) - ; - if (i >= 0) { - if ((p[i] & 0x01)) - p[i] = (((p[i] ^ 0xfe) | 0x01) & 0xff); - else if ((p[i] & 0x02)) - p[i] = (((p[i] ^ 0xfc) | 0x02) & 0xfe); - else if ((p[i] & 0x04)) - p[i] = (((p[i] ^ 0xf8) | 0x04) & 0xfc); - else if ((p[i] & 0x08)) - p[i] = (((p[i] ^ 0xf0) | 0x08) & 0xf8); - else if ((p[i] & 0x10)) - p[i] = (((p[i] ^ 0xe0) | 0x10) & 0xf0); - else if ((p[i] & 0x20)) - p[i] = (((p[i] ^ 0xc0) | 0x20) & 0xe0); - else if ((p[i] & 0x40)) - p[i] = (((p[i] ^ 0x80) | 0x40) & 0xc0); - else - p[i] = 0x80; - - for (i--; i >= 0; i--) - p[i] ^= 0xff; - } -} - -int mpi_print(enum gcry_mpi_format format, unsigned char *buffer, - size_t buflen, size_t *nwritten, MPI a) -{ - unsigned int nbits = mpi_get_nbits(a); - size_t len; - size_t dummy_nwritten; - int negative; - - if (!nwritten) - nwritten = &dummy_nwritten; - - /* Libgcrypt does no always care to set clear the sign if the value - * is 0. For printing this is a bit of a surprise, in particular - * because if some of the formats don't support negative numbers but - * should be able to print a zero. Thus we need this extra test - * for a negative number. - */ - if (a->sign && mpi_cmp_ui(a, 0)) - negative = 1; - else - negative = 0; - - len = buflen; - *nwritten = 0; - if (format == GCRYMPI_FMT_STD) { - unsigned char *tmp; - int extra = 0; - unsigned int n; - - tmp = mpi_get_buffer(a, &n, NULL); - if (!tmp) - return -EINVAL; - - if (negative) { - twocompl(tmp, n); - if (!(*tmp & 0x80)) { - /* Need to extend the sign. */ - n++; - extra = 2; - } - } else if (n && (*tmp & 0x80)) { - /* Positive but the high bit of the returned buffer is set. - * Thus we need to print an extra leading 0x00 so that the - * output is interpreted as a positive number. - */ - n++; - extra = 1; - } - - if (buffer && n > len) { - /* The provided buffer is too short. */ - kfree(tmp); - return -E2BIG; - } - if (buffer) { - unsigned char *s = buffer; - - if (extra == 1) - *s++ = 0; - else if (extra) - *s++ = 0xff; - memcpy(s, tmp, n-!!extra); - } - kfree(tmp); - *nwritten = n; - return 0; - } else if (format == GCRYMPI_FMT_USG) { - unsigned int n = (nbits + 7)/8; - - /* Note: We ignore the sign for this format. */ - /* FIXME: for performance reasons we should put this into - * mpi_aprint because we can then use the buffer directly. - */ - - if (buffer && n > len) - return -E2BIG; - if (buffer) { - unsigned char *tmp; - - tmp = mpi_get_buffer(a, &n, NULL); - if (!tmp) - return -EINVAL; - memcpy(buffer, tmp, n); - kfree(tmp); - } - *nwritten = n; - return 0; - } else if (format == GCRYMPI_FMT_PGP) { - unsigned int n = (nbits + 7)/8; - - /* The PGP format can only handle unsigned integers. */ - if (negative) - return -EINVAL; - - if (buffer && n+2 > len) - return -E2BIG; - - if (buffer) { - unsigned char *tmp; - unsigned char *s = buffer; - - s[0] = nbits >> 8; - s[1] = nbits; - - tmp = mpi_get_buffer(a, &n, NULL); - if (!tmp) - return -EINVAL; - memcpy(s+2, tmp, n); - kfree(tmp); - } - *nwritten = n+2; - return 0; - } else if (format == GCRYMPI_FMT_SSH) { - unsigned char *tmp; - int extra = 0; - unsigned int n; - - tmp = mpi_get_buffer(a, &n, NULL); - if (!tmp) - return -EINVAL; - - if (negative) { - twocompl(tmp, n); - if (!(*tmp & 0x80)) { - /* Need to extend the sign. */ - n++; - extra = 2; - } - } else if (n && (*tmp & 0x80)) { - n++; - extra = 1; - } - - if (buffer && n+4 > len) { - kfree(tmp); - return -E2BIG; - } - - if (buffer) { - unsigned char *s = buffer; - - *s++ = n >> 24; - *s++ = n >> 16; - *s++ = n >> 8; - *s++ = n; - if (extra == 1) - *s++ = 0; - else if (extra) - *s++ = 0xff; - memcpy(s, tmp, n-!!extra); - } - kfree(tmp); - *nwritten = 4+n; - return 0; - } else if (format == GCRYMPI_FMT_HEX) { - unsigned char *tmp; - int i; - int extra = 0; - unsigned int n = 0; - - tmp = mpi_get_buffer(a, &n, NULL); - if (!tmp) - return -EINVAL; - if (!n || (*tmp & 0x80)) - extra = 2; - - if (buffer && 2*n + extra + negative + 1 > len) { - kfree(tmp); - return -E2BIG; - } - if (buffer) { - unsigned char *s = buffer; - - if (negative) - *s++ = '-'; - if (extra) { - *s++ = '0'; - *s++ = '0'; - } - - for (i = 0; i < n; i++) { - unsigned int c = tmp[i]; - - *s++ = (c >> 4) < 10 ? '0'+(c>>4) : 'A'+(c>>4)-10; - c &= 15; - *s++ = c < 10 ? '0'+c : 'A'+c-10; - } - *s++ = 0; - *nwritten = s - buffer; - } else { - *nwritten = 2*n + extra + negative + 1; - } - kfree(tmp); - return 0; - } else - return -EINVAL; -} -EXPORT_SYMBOL_GPL(mpi_print); diff --git a/lib/crypto/mpi/mpih-mul.c b/lib/crypto/mpi/mpih-mul.c index e5f1c84e3c48..a93647564054 100644 --- a/lib/crypto/mpi/mpih-mul.c +++ b/lib/crypto/mpi/mpih-mul.c @@ -317,31 +317,6 @@ mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace) } } - -void mpihelp_mul_n(mpi_ptr_t prodp, - mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size) -{ - if (up == vp) { - if (size < KARATSUBA_THRESHOLD) - mpih_sqr_n_basecase(prodp, up, size); - else { - mpi_ptr_t tspace; - tspace = mpi_alloc_limb_space(2 * size); - mpih_sqr_n(prodp, up, size, tspace); - mpi_free_limb_space(tspace); - } - } else { - if (size < KARATSUBA_THRESHOLD) - mul_n_basecase(prodp, up, vp, size); - else { - mpi_ptr_t tspace; - tspace = mpi_alloc_limb_space(2 * size); - mul_n(prodp, up, vp, size, tspace); - mpi_free_limb_space(tspace); - } - } -} - int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, diff --git a/lib/crypto/mpi/mpiutil.c b/lib/crypto/mpi/mpiutil.c index aa8c46544af8..979ece5a81d2 100644 --- a/lib/crypto/mpi/mpiutil.c +++ b/lib/crypto/mpi/mpiutil.c @@ -20,63 +20,6 @@ #include "mpi-internal.h" -/* Constants allocated right away at startup. */ -static MPI constants[MPI_NUMBER_OF_CONSTANTS]; - -/* Initialize the MPI subsystem. This is called early and allows to - * do some initialization without taking care of threading issues. - */ -static int __init mpi_init(void) -{ - int idx; - unsigned long value; - - for (idx = 0; idx < MPI_NUMBER_OF_CONSTANTS; idx++) { - switch (idx) { - case MPI_C_ZERO: - value = 0; - break; - case MPI_C_ONE: - value = 1; - break; - case MPI_C_TWO: - value = 2; - break; - case MPI_C_THREE: - value = 3; - break; - case MPI_C_FOUR: - value = 4; - break; - case MPI_C_EIGHT: - value = 8; - break; - default: - pr_err("MPI: invalid mpi_const selector %d\n", idx); - return -EFAULT; - } - constants[idx] = mpi_alloc_set_ui(value); - constants[idx]->flags = (16|32); - } - - return 0; -} -postcore_initcall(mpi_init); - -/* Return a constant MPI descripbed by NO which is one of the - * MPI_C_xxx macros. There is no need to copy this returned value; it - * may be used directly. - */ -MPI mpi_const(enum gcry_mpi_constants no) -{ - if ((int)no < 0 || no > MPI_NUMBER_OF_CONSTANTS) - pr_err("MPI: invalid mpi_const selector %d\n", no); - if (!constants[no]) - pr_err("MPI: MPI subsystem not initialized\n"); - return constants[no]; -} -EXPORT_SYMBOL_GPL(mpi_const); - /**************** * Note: It was a bad idea to use the number of limbs to allocate * because on a alpha the limbs are large but we normally need @@ -163,15 +106,6 @@ int mpi_resize(MPI a, unsigned nlimbs) return 0; } -void mpi_clear(MPI a) -{ - if (!a) - return; - a->nlimbs = 0; - a->flags = 0; -} -EXPORT_SYMBOL_GPL(mpi_clear); - void mpi_free(MPI a) { if (!a) @@ -199,6 +133,8 @@ MPI mpi_copy(MPI a) if (a) { b = mpi_alloc(a->nlimbs); + if (!b) + return NULL; b->nlimbs = a->nlimbs; b->sign = a->sign; b->flags = a->flags; @@ -210,121 +146,5 @@ MPI mpi_copy(MPI a) return b; } -/**************** - * This function allocates an MPI which is optimized to hold - * a value as large as the one given in the argument and allocates it - * with the same flags as A. - */ -MPI mpi_alloc_like(MPI a) -{ - MPI b; - - if (a) { - b = mpi_alloc(a->nlimbs); - b->nlimbs = 0; - b->sign = 0; - b->flags = a->flags; - } else - b = NULL; - - return b; -} - - -/* Set U into W and release U. If W is NULL only U will be released. */ -void mpi_snatch(MPI w, MPI u) -{ - if (w) { - mpi_assign_limb_space(w, u->d, u->alloced); - w->nlimbs = u->nlimbs; - w->sign = u->sign; - w->flags = u->flags; - u->alloced = 0; - u->nlimbs = 0; - u->d = NULL; - } - mpi_free(u); -} - - -MPI mpi_set(MPI w, MPI u) -{ - mpi_ptr_t wp, up; - mpi_size_t usize = u->nlimbs; - int usign = u->sign; - - if (!w) - w = mpi_alloc(mpi_get_nlimbs(u)); - RESIZE_IF_NEEDED(w, usize); - wp = w->d; - up = u->d; - MPN_COPY(wp, up, usize); - w->nlimbs = usize; - w->flags = u->flags; - w->flags &= ~(16|32); /* Reset the immutable and constant flags. */ - w->sign = usign; - return w; -} -EXPORT_SYMBOL_GPL(mpi_set); - -MPI mpi_set_ui(MPI w, unsigned long u) -{ - if (!w) - w = mpi_alloc(1); - /* FIXME: If U is 0 we have no need to resize and thus possible - * allocating the limbs. - */ - RESIZE_IF_NEEDED(w, 1); - w->d[0] = u; - w->nlimbs = u ? 1 : 0; - w->sign = 0; - w->flags = 0; - return w; -} -EXPORT_SYMBOL_GPL(mpi_set_ui); - -MPI mpi_alloc_set_ui(unsigned long u) -{ - MPI w = mpi_alloc(1); - w->d[0] = u; - w->nlimbs = u ? 1 : 0; - w->sign = 0; - return w; -} - -/**************** - * Swap the value of A and B, when SWAP is 1. - * Leave the value when SWAP is 0. - * This implementation should be constant-time regardless of SWAP. - */ -void mpi_swap_cond(MPI a, MPI b, unsigned long swap) -{ - mpi_size_t i; - mpi_size_t nlimbs; - mpi_limb_t mask = ((mpi_limb_t)0) - swap; - mpi_limb_t x; - - if (a->alloced > b->alloced) - nlimbs = b->alloced; - else - nlimbs = a->alloced; - if (a->nlimbs > nlimbs || b->nlimbs > nlimbs) - return; - - for (i = 0; i < nlimbs; i++) { - x = mask & (a->d[i] ^ b->d[i]); - a->d[i] = a->d[i] ^ x; - b->d[i] = b->d[i] ^ x; - } - - x = mask & (a->nlimbs ^ b->nlimbs); - a->nlimbs = a->nlimbs ^ x; - b->nlimbs = b->nlimbs ^ x; - - x = mask & (a->sign ^ b->sign); - a->sign = a->sign ^ x; - b->sign = b->sign ^ x; -} - MODULE_DESCRIPTION("Multiprecision maths library"); MODULE_LICENSE("GPL"); diff --git a/lib/debugobjects.c b/lib/debugobjects.c index 7cea91e193a8..5ce473ad499b 100644 --- a/lib/debugobjects.c +++ b/lib/debugobjects.c @@ -70,10 +70,10 @@ static HLIST_HEAD(obj_to_free); * made at debug_stats_show(). Both obj_pool_min_free and obj_pool_max_used * can be off. */ -static int obj_pool_min_free = ODEBUG_POOL_SIZE; -static int obj_pool_free = ODEBUG_POOL_SIZE; +static int __data_racy obj_pool_min_free = ODEBUG_POOL_SIZE; +static int __data_racy obj_pool_free = ODEBUG_POOL_SIZE; static int obj_pool_used; -static int obj_pool_max_used; +static int __data_racy obj_pool_max_used; static bool obj_freeing; /* The number of objs on the global free list */ static int obj_nr_tofree; @@ -84,9 +84,9 @@ static int __data_racy debug_objects_fixups __read_mostly; static int __data_racy debug_objects_warnings __read_mostly; static int __data_racy debug_objects_enabled __read_mostly = CONFIG_DEBUG_OBJECTS_ENABLE_DEFAULT; -static int __data_racy debug_objects_pool_size __read_mostly +static int debug_objects_pool_size __ro_after_init = ODEBUG_POOL_SIZE; -static int __data_racy debug_objects_pool_min_level __read_mostly +static int debug_objects_pool_min_level __ro_after_init = ODEBUG_POOL_MIN_LEVEL; static const struct debug_obj_descr *descr_test __read_mostly; @@ -95,8 +95,8 @@ static struct kmem_cache *obj_cache __ro_after_init; /* * Track numbers of kmem_cache_alloc()/free() calls done. */ -static int debug_objects_allocated; -static int debug_objects_freed; +static int __data_racy debug_objects_allocated; +static int __data_racy debug_objects_freed; static void free_obj_work(struct work_struct *work); static DECLARE_DELAYED_WORK(debug_obj_work, free_obj_work); @@ -135,20 +135,19 @@ static void fill_pool(void) return; /* - * Reuse objs from the global free list; they will be reinitialized - * when allocating. + * Reuse objs from the global obj_to_free list; they will be + * reinitialized when allocating. * - * Both obj_nr_tofree and obj_pool_free are checked locklessly; the - * READ_ONCE()s pair with the WRITE_ONCE()s in pool_lock critical - * sections. + * obj_nr_tofree is checked locklessly; the READ_ONCE() pairs with + * the WRITE_ONCE() in pool_lock critical sections. */ - while (READ_ONCE(obj_nr_tofree) && (READ_ONCE(obj_pool_free) < obj_pool_min_free)) { + if (READ_ONCE(obj_nr_tofree)) { raw_spin_lock_irqsave(&pool_lock, flags); /* * Recheck with the lock held as the worker thread might have * won the race and freed the global free list already. */ - while (obj_nr_tofree && (obj_pool_free < obj_pool_min_free)) { + while (obj_nr_tofree && (obj_pool_free < debug_objects_pool_min_level)) { obj = hlist_entry(obj_to_free.first, typeof(*obj), node); hlist_del(&obj->node); WRITE_ONCE(obj_nr_tofree, obj_nr_tofree - 1); diff --git a/lib/fortify_kunit.c b/lib/fortify_kunit.c index f9ad60a9c7bd..ecb638d4cde1 100644 --- a/lib/fortify_kunit.c +++ b/lib/fortify_kunit.c @@ -306,8 +306,7 @@ DEFINE_ALLOC_SIZE_TEST_PAIR(vmalloc) orig = kvmalloc(prev_size, gfp); \ KUNIT_EXPECT_TRUE(test, orig != NULL); \ checker(((expected_pages) * PAGE_SIZE) * 2, \ - kvrealloc(orig, prev_size, \ - ((alloc_pages) * PAGE_SIZE) * 2, gfp), \ + kvrealloc(orig, ((alloc_pages) * PAGE_SIZE) * 2, gfp), \ kvfree(p)); \ } while (0) DEFINE_ALLOC_SIZE_TEST_PAIR(kvmalloc) diff --git a/lib/iov_iter.c b/lib/iov_iter.c index 4a6a9f419bd7..97003155bfac 100644 --- a/lib/iov_iter.c +++ b/lib/iov_iter.c @@ -527,6 +527,39 @@ static void iov_iter_iovec_advance(struct iov_iter *i, size_t size) i->__iov = iov; } +static void iov_iter_folioq_advance(struct iov_iter *i, size_t size) +{ + const struct folio_queue *folioq = i->folioq; + unsigned int slot = i->folioq_slot; + + if (!i->count) + return; + i->count -= size; + + if (slot >= folioq_nr_slots(folioq)) { + folioq = folioq->next; + slot = 0; + } + + size += i->iov_offset; /* From beginning of current segment. */ + do { + size_t fsize = folioq_folio_size(folioq, slot); + + if (likely(size < fsize)) + break; + size -= fsize; + slot++; + if (slot >= folioq_nr_slots(folioq) && folioq->next) { + folioq = folioq->next; + slot = 0; + } + } while (size); + + i->iov_offset = size; + i->folioq_slot = slot; + i->folioq = folioq; +} + void iov_iter_advance(struct iov_iter *i, size_t size) { if (unlikely(i->count < size)) @@ -539,12 +572,40 @@ void iov_iter_advance(struct iov_iter *i, size_t size) iov_iter_iovec_advance(i, size); } else if (iov_iter_is_bvec(i)) { iov_iter_bvec_advance(i, size); + } else if (iov_iter_is_folioq(i)) { + iov_iter_folioq_advance(i, size); } else if (iov_iter_is_discard(i)) { i->count -= size; } } EXPORT_SYMBOL(iov_iter_advance); +static void iov_iter_folioq_revert(struct iov_iter *i, size_t unroll) +{ + const struct folio_queue *folioq = i->folioq; + unsigned int slot = i->folioq_slot; + + for (;;) { + size_t fsize; + + if (slot == 0) { + folioq = folioq->prev; + slot = folioq_nr_slots(folioq); + } + slot--; + + fsize = folioq_folio_size(folioq, slot); + if (unroll <= fsize) { + i->iov_offset = fsize - unroll; + break; + } + unroll -= fsize; + } + + i->folioq_slot = slot; + i->folioq = folioq; +} + void iov_iter_revert(struct iov_iter *i, size_t unroll) { if (!unroll) @@ -576,6 +637,9 @@ void iov_iter_revert(struct iov_iter *i, size_t unroll) } unroll -= n; } + } else if (iov_iter_is_folioq(i)) { + i->iov_offset = 0; + iov_iter_folioq_revert(i, unroll); } else { /* same logics for iovec and kvec */ const struct iovec *iov = iter_iov(i); while (1) { @@ -603,6 +667,9 @@ size_t iov_iter_single_seg_count(const struct iov_iter *i) if (iov_iter_is_bvec(i)) return min(i->count, i->bvec->bv_len - i->iov_offset); } + if (unlikely(iov_iter_is_folioq(i))) + return !i->count ? 0 : + umin(folioq_folio_size(i->folioq, i->folioq_slot), i->count); return i->count; } EXPORT_SYMBOL(iov_iter_single_seg_count); @@ -640,6 +707,36 @@ void iov_iter_bvec(struct iov_iter *i, unsigned int direction, EXPORT_SYMBOL(iov_iter_bvec); /** + * iov_iter_folio_queue - Initialise an I/O iterator to use the folios in a folio queue + * @i: The iterator to initialise. + * @direction: The direction of the transfer. + * @folioq: The starting point in the folio queue. + * @first_slot: The first slot in the folio queue to use + * @offset: The offset into the folio in the first slot to start at + * @count: The size of the I/O buffer in bytes. + * + * Set up an I/O iterator to either draw data out of the pages attached to an + * inode or to inject data into those pages. The pages *must* be prevented + * from evaporation, either by taking a ref on them or locking them by the + * caller. + */ +void iov_iter_folio_queue(struct iov_iter *i, unsigned int direction, + const struct folio_queue *folioq, unsigned int first_slot, + unsigned int offset, size_t count) +{ + BUG_ON(direction & ~1); + *i = (struct iov_iter) { + .iter_type = ITER_FOLIOQ, + .data_source = direction, + .folioq = folioq, + .folioq_slot = first_slot, + .count = count, + .iov_offset = offset, + }; +} +EXPORT_SYMBOL(iov_iter_folio_queue); + +/** * iov_iter_xarray - Initialise an I/O iterator to use the pages in an xarray * @i: The iterator to initialise. * @direction: The direction of the transfer. @@ -765,12 +862,19 @@ bool iov_iter_is_aligned(const struct iov_iter *i, unsigned addr_mask, if (iov_iter_is_bvec(i)) return iov_iter_aligned_bvec(i, addr_mask, len_mask); + /* With both xarray and folioq types, we're dealing with whole folios. */ if (iov_iter_is_xarray(i)) { if (i->count & len_mask) return false; if ((i->xarray_start + i->iov_offset) & addr_mask) return false; } + if (iov_iter_is_folioq(i)) { + if (i->count & len_mask) + return false; + if (i->iov_offset & addr_mask) + return false; + } return true; } @@ -835,6 +939,9 @@ unsigned long iov_iter_alignment(const struct iov_iter *i) if (iov_iter_is_bvec(i)) return iov_iter_alignment_bvec(i); + /* With both xarray and folioq types, we're dealing with whole folios. */ + if (iov_iter_is_folioq(i)) + return i->iov_offset | i->count; if (iov_iter_is_xarray(i)) return (i->xarray_start + i->iov_offset) | i->count; @@ -887,6 +994,62 @@ static int want_pages_array(struct page ***res, size_t size, return count; } +static ssize_t iter_folioq_get_pages(struct iov_iter *iter, + struct page ***ppages, size_t maxsize, + unsigned maxpages, size_t *_start_offset) +{ + const struct folio_queue *folioq = iter->folioq; + struct page **pages; + unsigned int slot = iter->folioq_slot; + size_t extracted = 0, count = iter->count, iov_offset = iter->iov_offset; + + if (slot >= folioq_nr_slots(folioq)) { + folioq = folioq->next; + slot = 0; + if (WARN_ON(iov_offset != 0)) + return -EIO; + } + + maxpages = want_pages_array(ppages, maxsize, iov_offset & ~PAGE_MASK, maxpages); + if (!maxpages) + return -ENOMEM; + *_start_offset = iov_offset & ~PAGE_MASK; + pages = *ppages; + + for (;;) { + struct folio *folio = folioq_folio(folioq, slot); + size_t offset = iov_offset, fsize = folioq_folio_size(folioq, slot); + size_t part = PAGE_SIZE - offset % PAGE_SIZE; + + part = umin(part, umin(maxsize - extracted, fsize - offset)); + count -= part; + iov_offset += part; + extracted += part; + + *pages = folio_page(folio, offset / PAGE_SIZE); + get_page(*pages); + pages++; + maxpages--; + if (maxpages == 0 || extracted >= maxsize) + break; + + if (offset >= fsize) { + iov_offset = 0; + slot++; + if (slot == folioq_nr_slots(folioq) && folioq->next) { + folioq = folioq->next; + slot = 0; + } + } + } + + iter->count = count; + iter->iov_offset = iov_offset; + iter->folioq = folioq; + iter->folioq_slot = slot; + return extracted; +} + static ssize_t iter_xarray_populate_pages(struct page **pages, struct xarray *xa, pgoff_t index, unsigned int nr_pages) { @@ -1034,6 +1197,8 @@ static ssize_t __iov_iter_get_pages_alloc(struct iov_iter *i, } return maxsize; } + if (iov_iter_is_folioq(i)) + return iter_folioq_get_pages(i, pages, maxsize, maxpages, start); if (iov_iter_is_xarray(i)) return iter_xarray_get_pages(i, pages, maxsize, maxpages, start); return -EFAULT; @@ -1118,6 +1283,11 @@ int iov_iter_npages(const struct iov_iter *i, int maxpages) return iov_npages(i, maxpages); if (iov_iter_is_bvec(i)) return bvec_npages(i, maxpages); + if (iov_iter_is_folioq(i)) { + unsigned offset = i->iov_offset % PAGE_SIZE; + int npages = DIV_ROUND_UP(offset + i->count, PAGE_SIZE); + return min(npages, maxpages); + } if (iov_iter_is_xarray(i)) { unsigned offset = (i->xarray_start + i->iov_offset) % PAGE_SIZE; int npages = DIV_ROUND_UP(offset + i->count, PAGE_SIZE); @@ -1399,6 +1569,68 @@ void iov_iter_restore(struct iov_iter *i, struct iov_iter_state *state) } /* + * Extract a list of contiguous pages from an ITER_FOLIOQ iterator. This does + * not get references on the pages, nor does it get a pin on them. + */ +static ssize_t iov_iter_extract_folioq_pages(struct iov_iter *i, + struct page ***pages, size_t maxsize, + unsigned int maxpages, + iov_iter_extraction_t extraction_flags, + size_t *offset0) +{ + const struct folio_queue *folioq = i->folioq; + struct page **p; + unsigned int nr = 0; + size_t extracted = 0, offset, slot = i->folioq_slot; + + if (slot >= folioq_nr_slots(folioq)) { + folioq = folioq->next; + slot = 0; + if (WARN_ON(i->iov_offset != 0)) + return -EIO; + } + + offset = i->iov_offset & ~PAGE_MASK; + *offset0 = offset; + + maxpages = want_pages_array(pages, maxsize, offset, maxpages); + if (!maxpages) + return -ENOMEM; + p = *pages; + + for (;;) { + struct folio *folio = folioq_folio(folioq, slot); + size_t offset = i->iov_offset, fsize = folioq_folio_size(folioq, slot); + size_t part = PAGE_SIZE - offset % PAGE_SIZE; + + if (offset < fsize) { + part = umin(part, umin(maxsize - extracted, fsize - offset)); + i->count -= part; + i->iov_offset += part; + extracted += part; + + p[nr++] = folio_page(folio, offset / PAGE_SIZE); + } + + if (nr >= maxpages || extracted >= maxsize) + break; + + if (i->iov_offset >= fsize) { + i->iov_offset = 0; + slot++; + if (slot == folioq_nr_slots(folioq) && folioq->next) { + folioq = folioq->next; + slot = 0; + } + } + } + + i->folioq = folioq; + i->folioq_slot = slot; + return extracted; +} + +/* * Extract a list of contiguous pages from an ITER_XARRAY iterator. This does not * get references on the pages, nor does it get a pin on them. */ @@ -1618,8 +1850,8 @@ static ssize_t iov_iter_extract_user_pages(struct iov_iter *i, * added to the pages, but refs will not be taken. * iov_iter_extract_will_pin() will return true. * - * (*) If the iterator is ITER_KVEC, ITER_BVEC or ITER_XARRAY, the pages are - * merely listed; no extra refs or pins are obtained. + * (*) If the iterator is ITER_KVEC, ITER_BVEC, ITER_FOLIOQ or ITER_XARRAY, the + * pages are merely listed; no extra refs or pins are obtained. * iov_iter_extract_will_pin() will return 0. * * Note also: @@ -1654,6 +1886,10 @@ ssize_t iov_iter_extract_pages(struct iov_iter *i, return iov_iter_extract_bvec_pages(i, pages, maxsize, maxpages, extraction_flags, offset0); + if (iov_iter_is_folioq(i)) + return iov_iter_extract_folioq_pages(i, pages, maxsize, + maxpages, extraction_flags, + offset0); if (iov_iter_is_xarray(i)) return iov_iter_extract_xarray_pages(i, pages, maxsize, maxpages, extraction_flags, diff --git a/lib/irq_poll.c b/lib/irq_poll.c index 2d5329a42105..08b242bbdbdf 100644 --- a/lib/irq_poll.c +++ b/lib/irq_poll.c @@ -75,7 +75,7 @@ void irq_poll_complete(struct irq_poll *iop) } EXPORT_SYMBOL(irq_poll_complete); -static void __latent_entropy irq_poll_softirq(struct softirq_action *h) +static void __latent_entropy irq_poll_softirq(void) { struct list_head *list = this_cpu_ptr(&blk_cpu_iopoll); int rearm = 0, budget = irq_poll_budget; diff --git a/lib/kunit/device.c b/lib/kunit/device.c index 25c81ed465fb..520c1fccee8a 100644 --- a/lib/kunit/device.c +++ b/lib/kunit/device.c @@ -89,7 +89,7 @@ struct device_driver *kunit_driver_create(struct kunit *test, const char *name) if (!driver) return ERR_PTR(err); - driver->name = name; + driver->name = kunit_kstrdup_const(test, name, GFP_KERNEL); driver->bus = &kunit_bus_type; driver->owner = THIS_MODULE; @@ -192,8 +192,11 @@ void kunit_device_unregister(struct kunit *test, struct device *dev) const struct device_driver *driver = to_kunit_device(dev)->driver; kunit_release_action(test, device_unregister_wrapper, dev); - if (driver) + if (driver) { + const char *driver_name = driver->name; kunit_release_action(test, driver_unregister_wrapper, (void *)driver); + kunit_kfree_const(test, driver_name); + } } EXPORT_SYMBOL_GPL(kunit_device_unregister); diff --git a/lib/kunit/test.c b/lib/kunit/test.c index e8b1b52a19ab..089c832e3cdb 100644 --- a/lib/kunit/test.c +++ b/lib/kunit/test.c @@ -874,6 +874,25 @@ void kunit_kfree(struct kunit *test, const void *ptr) } EXPORT_SYMBOL_GPL(kunit_kfree); +void kunit_kfree_const(struct kunit *test, const void *x) +{ +#if !IS_MODULE(CONFIG_KUNIT) + if (!is_kernel_rodata((unsigned long)x)) +#endif + kunit_kfree(test, x); +} +EXPORT_SYMBOL_GPL(kunit_kfree_const); + +const char *kunit_kstrdup_const(struct kunit *test, const char *str, gfp_t gfp) +{ +#if !IS_MODULE(CONFIG_KUNIT) + if (is_kernel_rodata((unsigned long)str)) + return str; +#endif + return kunit_kstrdup(test, str, gfp); +} +EXPORT_SYMBOL_GPL(kunit_kstrdup_const); + void kunit_cleanup(struct kunit *test) { struct kunit_resource *res; diff --git a/lib/kunit_iov_iter.c b/lib/kunit_iov_iter.c index 27e0c8ee71d8..13e15687675a 100644 --- a/lib/kunit_iov_iter.c +++ b/lib/kunit_iov_iter.c @@ -12,6 +12,7 @@ #include <linux/mm.h> #include <linux/uio.h> #include <linux/bvec.h> +#include <linux/folio_queue.h> #include <kunit/test.h> MODULE_DESCRIPTION("iov_iter testing"); @@ -62,6 +63,9 @@ static void *__init iov_kunit_create_buffer(struct kunit *test, KUNIT_ASSERT_EQ(test, got, npages); } + for (int i = 0; i < npages; i++) + pages[i]->index = i; + buffer = vmap(pages, npages, VM_MAP | VM_MAP_PUT_PAGES, PAGE_KERNEL); KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buffer); @@ -362,6 +366,179 @@ stop: KUNIT_SUCCEED(test); } +static void iov_kunit_destroy_folioq(void *data) +{ + struct folio_queue *folioq, *next; + + for (folioq = data; folioq; folioq = next) { + next = folioq->next; + for (int i = 0; i < folioq_nr_slots(folioq); i++) + if (folioq_folio(folioq, i)) + folio_put(folioq_folio(folioq, i)); + kfree(folioq); + } +} + +static void __init iov_kunit_load_folioq(struct kunit *test, + struct iov_iter *iter, int dir, + struct folio_queue *folioq, + struct page **pages, size_t npages) +{ + struct folio_queue *p = folioq; + size_t size = 0; + int i; + + for (i = 0; i < npages; i++) { + if (folioq_full(p)) { + p->next = kzalloc(sizeof(struct folio_queue), GFP_KERNEL); + KUNIT_ASSERT_NOT_ERR_OR_NULL(test, p->next); + folioq_init(p->next); + p->next->prev = p; + p = p->next; + } + folioq_append(p, page_folio(pages[i])); + size += PAGE_SIZE; + } + iov_iter_folio_queue(iter, dir, folioq, 0, 0, size); +} + +static struct folio_queue *iov_kunit_create_folioq(struct kunit *test) +{ + struct folio_queue *folioq; + + folioq = kzalloc(sizeof(struct folio_queue), GFP_KERNEL); + KUNIT_ASSERT_NOT_ERR_OR_NULL(test, folioq); + kunit_add_action_or_reset(test, iov_kunit_destroy_folioq, folioq); + folioq_init(folioq); + return folioq; +} + +/* + * Test copying to a ITER_FOLIOQ-type iterator. + */ +static void __init iov_kunit_copy_to_folioq(struct kunit *test) +{ + const struct kvec_test_range *pr; + struct iov_iter iter; + struct folio_queue *folioq; + struct page **spages, **bpages; + u8 *scratch, *buffer; + size_t bufsize, npages, size, copied; + int i, patt; + + bufsize = 0x100000; + npages = bufsize / PAGE_SIZE; + + folioq = iov_kunit_create_folioq(test); + + scratch = iov_kunit_create_buffer(test, &spages, npages); + for (i = 0; i < bufsize; i++) + scratch[i] = pattern(i); + + buffer = iov_kunit_create_buffer(test, &bpages, npages); + memset(buffer, 0, bufsize); + + iov_kunit_load_folioq(test, &iter, READ, folioq, bpages, npages); + + i = 0; + for (pr = kvec_test_ranges; pr->from >= 0; pr++) { + size = pr->to - pr->from; + KUNIT_ASSERT_LE(test, pr->to, bufsize); + + iov_iter_folio_queue(&iter, READ, folioq, 0, 0, pr->to); + iov_iter_advance(&iter, pr->from); + copied = copy_to_iter(scratch + i, size, &iter); + + KUNIT_EXPECT_EQ(test, copied, size); + KUNIT_EXPECT_EQ(test, iter.count, 0); + KUNIT_EXPECT_EQ(test, iter.iov_offset, pr->to % PAGE_SIZE); + i += size; + if (test->status == KUNIT_FAILURE) + goto stop; + } + + /* Build the expected image in the scratch buffer. */ + patt = 0; + memset(scratch, 0, bufsize); + for (pr = kvec_test_ranges; pr->from >= 0; pr++) + for (i = pr->from; i < pr->to; i++) + scratch[i] = pattern(patt++); + + /* Compare the images */ + for (i = 0; i < bufsize; i++) { + KUNIT_EXPECT_EQ_MSG(test, buffer[i], scratch[i], "at i=%x", i); + if (buffer[i] != scratch[i]) + return; + } + +stop: + KUNIT_SUCCEED(test); +} + +/* + * Test copying from a ITER_FOLIOQ-type iterator. + */ +static void __init iov_kunit_copy_from_folioq(struct kunit *test) +{ + const struct kvec_test_range *pr; + struct iov_iter iter; + struct folio_queue *folioq; + struct page **spages, **bpages; + u8 *scratch, *buffer; + size_t bufsize, npages, size, copied; + int i, j; + + bufsize = 0x100000; + npages = bufsize / PAGE_SIZE; + + folioq = iov_kunit_create_folioq(test); + + buffer = iov_kunit_create_buffer(test, &bpages, npages); + for (i = 0; i < bufsize; i++) + buffer[i] = pattern(i); + + scratch = iov_kunit_create_buffer(test, &spages, npages); + memset(scratch, 0, bufsize); + + iov_kunit_load_folioq(test, &iter, READ, folioq, bpages, npages); + + i = 0; + for (pr = kvec_test_ranges; pr->from >= 0; pr++) { + size = pr->to - pr->from; + KUNIT_ASSERT_LE(test, pr->to, bufsize); + + iov_iter_folio_queue(&iter, WRITE, folioq, 0, 0, pr->to); + iov_iter_advance(&iter, pr->from); + copied = copy_from_iter(scratch + i, size, &iter); + + KUNIT_EXPECT_EQ(test, copied, size); + KUNIT_EXPECT_EQ(test, iter.count, 0); + KUNIT_EXPECT_EQ(test, iter.iov_offset, pr->to % PAGE_SIZE); + i += size; + } + + /* Build the expected image in the main buffer. */ + i = 0; + memset(buffer, 0, bufsize); + for (pr = kvec_test_ranges; pr->from >= 0; pr++) { + for (j = pr->from; j < pr->to; j++) { + buffer[i++] = pattern(j); + if (i >= bufsize) + goto stop; + } + } +stop: + + /* Compare the images */ + for (i = 0; i < bufsize; i++) { + KUNIT_EXPECT_EQ_MSG(test, scratch[i], buffer[i], "at i=%x", i); + if (scratch[i] != buffer[i]) + return; + } + + KUNIT_SUCCEED(test); +} + static void iov_kunit_destroy_xarray(void *data) { struct xarray *xarray = data; @@ -678,6 +855,85 @@ stop: } /* + * Test the extraction of ITER_FOLIOQ-type iterators. + */ +static void __init iov_kunit_extract_pages_folioq(struct kunit *test) +{ + const struct kvec_test_range *pr; + struct folio_queue *folioq; + struct iov_iter iter; + struct page **bpages, *pagelist[8], **pages = pagelist; + ssize_t len; + size_t bufsize, size = 0, npages; + int i, from; + + bufsize = 0x100000; + npages = bufsize / PAGE_SIZE; + + folioq = iov_kunit_create_folioq(test); + + iov_kunit_create_buffer(test, &bpages, npages); + iov_kunit_load_folioq(test, &iter, READ, folioq, bpages, npages); + + for (pr = kvec_test_ranges; pr->from >= 0; pr++) { + from = pr->from; + size = pr->to - from; + KUNIT_ASSERT_LE(test, pr->to, bufsize); + + iov_iter_folio_queue(&iter, WRITE, folioq, 0, 0, pr->to); + iov_iter_advance(&iter, from); + + do { + size_t offset0 = LONG_MAX; + + for (i = 0; i < ARRAY_SIZE(pagelist); i++) + pagelist[i] = (void *)(unsigned long)0xaa55aa55aa55aa55ULL; + + len = iov_iter_extract_pages(&iter, &pages, 100 * 1024, + ARRAY_SIZE(pagelist), 0, &offset0); + KUNIT_EXPECT_GE(test, len, 0); + if (len < 0) + break; + KUNIT_EXPECT_LE(test, len, size); + KUNIT_EXPECT_EQ(test, iter.count, size - len); + if (len == 0) + break; + size -= len; + KUNIT_EXPECT_GE(test, (ssize_t)offset0, 0); + KUNIT_EXPECT_LT(test, offset0, PAGE_SIZE); + + for (i = 0; i < ARRAY_SIZE(pagelist); i++) { + struct page *p; + ssize_t part = min_t(ssize_t, len, PAGE_SIZE - offset0); + int ix; + + KUNIT_ASSERT_GE(test, part, 0); + ix = from / PAGE_SIZE; + KUNIT_ASSERT_LT(test, ix, npages); + p = bpages[ix]; + KUNIT_EXPECT_PTR_EQ(test, pagelist[i], p); + KUNIT_EXPECT_EQ(test, offset0, from % PAGE_SIZE); + from += part; + len -= part; + KUNIT_ASSERT_GE(test, len, 0); + if (len == 0) + break; + offset0 = 0; + } + + if (test->status == KUNIT_FAILURE) + goto stop; + } while (iov_iter_count(&iter) > 0); + + KUNIT_EXPECT_EQ(test, size, 0); + KUNIT_EXPECT_EQ(test, iter.count, 0); + } + +stop: + KUNIT_SUCCEED(test); +} + +/* * Test the extraction of ITER_XARRAY-type iterators. */ static void __init iov_kunit_extract_pages_xarray(struct kunit *test) @@ -761,10 +1017,13 @@ static struct kunit_case __refdata iov_kunit_cases[] = { KUNIT_CASE(iov_kunit_copy_from_kvec), KUNIT_CASE(iov_kunit_copy_to_bvec), KUNIT_CASE(iov_kunit_copy_from_bvec), + KUNIT_CASE(iov_kunit_copy_to_folioq), + KUNIT_CASE(iov_kunit_copy_from_folioq), KUNIT_CASE(iov_kunit_copy_to_xarray), KUNIT_CASE(iov_kunit_copy_from_xarray), KUNIT_CASE(iov_kunit_extract_pages_kvec), KUNIT_CASE(iov_kunit_extract_pages_bvec), + KUNIT_CASE(iov_kunit_extract_pages_folioq), KUNIT_CASE(iov_kunit_extract_pages_xarray), {} }; diff --git a/lib/lz4/lz4hc_compress.c b/lib/lz4/lz4hc_compress.c index e7ac8694b797..bc45594ad2a8 100644 --- a/lib/lz4/lz4hc_compress.c +++ b/lib/lz4/lz4hc_compress.c @@ -621,6 +621,7 @@ void LZ4_resetStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr, int compressionLevel) LZ4_streamHCPtr->internal_donotuse.base = NULL; LZ4_streamHCPtr->internal_donotuse.compressionLevel = (unsigned int)compressionLevel; } +EXPORT_SYMBOL(LZ4_resetStreamHC); int LZ4_loadDictHC(LZ4_streamHC_t *LZ4_streamHCPtr, const char *dictionary, diff --git a/lib/maple_tree.c b/lib/maple_tree.c index aa3a5df15b8e..20990ecba2dd 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -348,17 +348,17 @@ static inline void *mte_safe_root(const struct maple_enode *node) return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE); } -static inline void *mte_set_full(const struct maple_enode *node) +static inline void __maybe_unused *mte_set_full(const struct maple_enode *node) { return (void *)((unsigned long)node & ~MAPLE_ENODE_NULL); } -static inline void *mte_clear_full(const struct maple_enode *node) +static inline void __maybe_unused *mte_clear_full(const struct maple_enode *node) { return (void *)((unsigned long)node | MAPLE_ENODE_NULL); } -static inline bool mte_has_null(const struct maple_enode *node) +static inline bool __maybe_unused mte_has_null(const struct maple_enode *node) { return (unsigned long)node & MAPLE_ENODE_NULL; } @@ -474,6 +474,7 @@ enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) /* * mas_set_parent() - Set the parent node and encode the slot + * @mas: The maple state * @enode: The encoded maple node. * @parent: The encoded maple node that is the parent of @enode. * @slot: The slot that @enode resides in @parent. @@ -534,7 +535,7 @@ unsigned int mte_parent_slot(const struct maple_enode *enode) /* * mte_parent() - Get the parent of @node. - * @node: The encoded maple node. + * @enode: The encoded maple node. * * Return: The parent maple node. */ @@ -641,8 +642,8 @@ static inline unsigned int mas_alloc_req(const struct ma_state *mas) /* * ma_pivots() - Get a pointer to the maple node pivots. - * @node - the maple node - * @type - the node type + * @node: the maple node + * @type: the node type * * In the event of a dead node, this array may be %NULL * @@ -665,8 +666,8 @@ static inline unsigned long *ma_pivots(struct maple_node *node, /* * ma_gaps() - Get a pointer to the maple node gaps. - * @node - the maple node - * @type - the node type + * @node: the maple node + * @type: the node type * * Return: A pointer to the maple node gaps */ @@ -880,8 +881,6 @@ static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, * @mt: The maple tree * @mn: The maple node * @type: The maple node type - * @offset: The offset of the highest sub-gap in this node. - * @end: The end of the data in this node. */ static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn, enum maple_type type) @@ -939,7 +938,7 @@ static inline unsigned char ma_meta_gap(struct maple_node *mn) /* * ma_set_meta_gap() - Set the largest gap location in a nodes metadata * @mn: The maple node - * @mn: The maple node type + * @mt: The maple node type * @offset: The location of the largest gap. */ static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, @@ -953,8 +952,8 @@ static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, /* * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes. - * @mat - the ma_topiary, a linked list of dead nodes. - * @dead_enode - the node to be marked as dead and added to the tail of the list + * @mat: the ma_topiary, a linked list of dead nodes. + * @dead_enode: the node to be marked as dead and added to the tail of the list * * Add the @dead_enode to the linked list in @mat. */ @@ -977,8 +976,8 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, bool free); /* * mas_mat_destroy() - Free all nodes and subtrees in a dead list. - * @mas - the maple state - * @mat - the ma_topiary linked list of dead nodes to free. + * @mas: the maple state + * @mat: the ma_topiary linked list of dead nodes to free. * * Destroy walk a dead list. */ @@ -999,7 +998,7 @@ static void mas_mat_destroy(struct ma_state *mas, struct ma_topiary *mat) } /* * mas_descend() - Descend into the slot stored in the ma_state. - * @mas - the maple state. + * @mas: the maple state. * * Note: Not RCU safe, only use in write side or debug code. */ @@ -1346,8 +1345,8 @@ static void mas_node_count(struct ma_state *mas, int count) * Return: * - If mas->node is an error or not mas_start, return NULL. * - If it's an empty tree: NULL & mas->status == ma_none - * - If it's a single entry: The entry & mas->status == mas_root - * - If it's a tree: NULL & mas->status == safe root node. + * - If it's a single entry: The entry & mas->status == ma_root + * - If it's a tree: NULL & mas->status == ma_active */ static inline struct maple_enode *mas_start(struct ma_state *mas) { @@ -1372,9 +1371,9 @@ retry: return NULL; } + mas->node = NULL; /* empty tree */ if (unlikely(!root)) { - mas->node = NULL; mas->status = ma_none; mas->offset = MAPLE_NODE_SLOTS; return NULL; @@ -1462,7 +1461,7 @@ static inline unsigned char mas_data_end(struct ma_state *mas) /* * mas_leaf_max_gap() - Returns the largest gap in a leaf node - * @mas - the maple state + * @mas: the maple state * * Return: The maximum gap in the leaf. */ @@ -1544,7 +1543,7 @@ static unsigned long mas_leaf_max_gap(struct ma_state *mas) * @node: The maple node * @gaps: The pointer to the gaps * @mt: The maple node type - * @*off: Pointer to store the offset location of the gap. + * @off: Pointer to store the offset location of the gap. * * Uses the metadata data end to scan backwards across set gaps. * @@ -1651,7 +1650,7 @@ ascend: /* * mas_update_gap() - Update a nodes gaps and propagate up if necessary. - * @mas - the maple state. + * @mas: the maple state. */ static inline void mas_update_gap(struct ma_state *mas) { @@ -1678,8 +1677,8 @@ static inline void mas_update_gap(struct ma_state *mas) /* * mas_adopt_children() - Set the parent pointer of all nodes in @parent to * @parent with the slot encoded. - * @mas - the maple state (for the tree) - * @parent - the maple encoded node containing the children. + * @mas: the maple state (for the tree) + * @parent: the maple encoded node containing the children. */ static inline void mas_adopt_children(struct ma_state *mas, struct maple_enode *parent) @@ -1701,8 +1700,8 @@ static inline void mas_adopt_children(struct ma_state *mas, /* * mas_put_in_tree() - Put a new node in the tree, smp_wmb(), and mark the old * node as dead. - * @mas - the maple state with the new node - * @old_enode - The old maple encoded node to replace. + * @mas: the maple state with the new node + * @old_enode: The old maple encoded node to replace. */ static inline void mas_put_in_tree(struct ma_state *mas, struct maple_enode *old_enode) @@ -1730,8 +1729,8 @@ static inline void mas_put_in_tree(struct ma_state *mas, * mas_replace_node() - Replace a node by putting it in the tree, marking it * dead, and freeing it. * the parent encoding to locate the maple node in the tree. - * @mas - the ma_state with @mas->node pointing to the new node. - * @old_enode - The old maple encoded node. + * @mas: the ma_state with @mas->node pointing to the new node. + * @old_enode: The old maple encoded node. */ static inline void mas_replace_node(struct ma_state *mas, struct maple_enode *old_enode) @@ -1796,7 +1795,6 @@ static inline void mab_shift_right(struct maple_big_node *b_node, /* * mab_middle_node() - Check if a middle node is needed (unlikely) * @b_node: the maple_big_node that contains the data. - * @size: the amount of data in the b_node * @split: the potential split location * @slot_count: the size that can be stored in a single node being considered. * @@ -1844,6 +1842,7 @@ static inline int mab_no_null_split(struct maple_big_node *b_node, /* * mab_calc_split() - Calculate the split location and if there needs to be two * splits. + * @mas: The maple state * @bn: The maple_big_node with the data * @mid_split: The second split, if required. 0 otherwise. * @@ -2177,7 +2176,8 @@ static inline bool mas_next_sibling(struct ma_state *mas) } /* - * mte_node_or_none() - Set the enode and state. + * mas_node_or_none() - Set the enode and state. + * @mas: the maple state * @enode: The encoded maple node. * * Set the node to the enode and the status. @@ -2228,7 +2228,6 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) /* * mast_rebalance_next() - Rebalance against the next node * @mast: The maple subtree state - * @old_r: The encoded maple node to the right (next node). */ static inline void mast_rebalance_next(struct maple_subtree_state *mast) { @@ -2242,7 +2241,6 @@ static inline void mast_rebalance_next(struct maple_subtree_state *mast) /* * mast_rebalance_prev() - Rebalance against the previous node * @mast: The maple subtree state - * @old_l: The encoded maple node to the left (previous node) */ static inline void mast_rebalance_prev(struct maple_subtree_state *mast) { @@ -2393,9 +2391,9 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, /* * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end * pointer. - * @b_node - the big node to add the entry - * @mas - the maple state to get the pivot (mas->max) - * @entry - the entry to add, if NULL nothing happens. + * @b_node: the big node to add the entry + * @mas: the maple state to get the pivot (mas->max) + * @entry: the entry to add, if NULL nothing happens. */ static inline void mab_set_b_end(struct maple_big_node *b_node, struct ma_state *mas, @@ -2414,11 +2412,11 @@ static inline void mab_set_b_end(struct maple_big_node *b_node, * mas_set_split_parent() - combine_then_separate helper function. Sets the parent * of @mas->node to either @left or @right, depending on @slot and @split * - * @mas - the maple state with the node that needs a parent - * @left - possible parent 1 - * @right - possible parent 2 - * @slot - the slot the mas->node was placed - * @split - the split location between @left and @right + * @mas: the maple state with the node that needs a parent + * @left: possible parent 1 + * @right: possible parent 2 + * @slot: the slot the mas->node was placed + * @split: the split location between @left and @right */ static inline void mas_set_split_parent(struct ma_state *mas, struct maple_enode *left, @@ -2438,11 +2436,11 @@ static inline void mas_set_split_parent(struct ma_state *mas, /* * mte_mid_split_check() - Check if the next node passes the mid-split - * @**l: Pointer to left encoded maple node. - * @**m: Pointer to middle encoded maple node. - * @**r: Pointer to right encoded maple node. + * @l: Pointer to left encoded maple node. + * @m: Pointer to middle encoded maple node. + * @r: Pointer to right encoded maple node. * @slot: The offset - * @*split: The split location. + * @split: The split location. * @mid_split: The middle split. */ static inline void mte_mid_split_check(struct maple_enode **l, @@ -2466,10 +2464,10 @@ static inline void mte_mid_split_check(struct maple_enode **l, /* * mast_set_split_parents() - Helper function to set three nodes parents. Slot * is taken from @mast->l. - * @mast - the maple subtree state - * @left - the left node - * @right - the right node - * @split - the split location. + * @mast: the maple subtree state + * @left: the left node + * @right: the right node + * @split: the split location. */ static inline void mast_set_split_parents(struct maple_subtree_state *mast, struct maple_enode *left, @@ -2503,7 +2501,6 @@ static inline void mast_set_split_parents(struct maple_subtree_state *mast, /* * mas_topiary_node() - Dispose of a single node * @mas: The maple state for pushing nodes - * @enode: The encoded maple node * @in_rcu: If the tree is in rcu mode * * The node will either be RCU freed or pushed back on the maple state. @@ -2635,7 +2632,7 @@ static inline void mas_topiary_replace(struct ma_state *mas, /* * mas_wmb_replace() - Write memory barrier and replace * @mas: The maple state - * @old: The old maple encoded node that is being replaced. + * @old_enode: The old maple encoded node that is being replaced. * * Updates gap as necessary. */ @@ -2823,10 +2820,8 @@ dead_node: * orig_l_mas->last is used in mas_consume to find the slots that will need to * be either freed or destroyed. orig_l_mas->depth keeps track of the height of * the new sub-tree in case the sub-tree becomes the full tree. - * - * Return: the number of elements in b_node during the last loop. */ -static int mas_spanning_rebalance(struct ma_state *mas, +static void mas_spanning_rebalance(struct ma_state *mas, struct maple_subtree_state *mast, unsigned char count) { unsigned char split, mid_split; @@ -2942,7 +2937,7 @@ new_root: mas->offset = l_mas.offset; mas_wmb_replace(mas, old_enode); mtree_range_walk(mas); - return mast->bn->b_end; + return; } /* @@ -2952,10 +2947,8 @@ new_root: * * Rebalance two nodes into a single node or two new nodes that are sufficient. * Continue upwards until tree is sufficient. - * - * Return: the number of elements in b_node during the last loop. */ -static inline int mas_rebalance(struct ma_state *mas, +static inline void mas_rebalance(struct ma_state *mas, struct maple_big_node *b_node) { char empty_count = mas_mt_height(mas); @@ -2976,9 +2969,6 @@ static inline int mas_rebalance(struct ma_state *mas, * tries to combine the data in the same way. If one node contains the * entire range of the tree, then that node is used as a new root node. */ - mas_node_count(mas, empty_count * 2 - 1); - if (mas_is_err(mas)) - return 0; mast.orig_l = &l_mas; mast.orig_r = &r_mas; @@ -3029,11 +3019,6 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end /* set up node. */ if (in_rcu) { - /* Allocate for both left and right as well as parent. */ - mas_node_count(mas, 3); - if (mas_is_err(mas)) - return; - newnode = mas_pop_node(mas); } else { newnode = &reuse; @@ -3308,9 +3293,8 @@ static inline bool mas_push_data(struct ma_state *mas, int height, * mas_split() - Split data that is too big for one node into two. * @mas: The maple state * @b_node: The maple big node - * Return: 1 on success, 0 on failure. */ -static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) +static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) { struct maple_subtree_state mast; int height = 0; @@ -3341,10 +3325,6 @@ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) trace_ma_op(__func__, mas); mas->depth = mas_mt_height(mas); - /* Allocation failures will happen early. */ - mas_node_count(mas, 1 + mas->depth * 2); - if (mas_is_err(mas)) - return 0; mast.l = &l_mas; mast.r = &r_mas; @@ -3392,75 +3372,25 @@ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) mas->node = l_mas.node; mas_wmb_replace(mas, old); mtree_range_walk(mas); - return 1; -} - -/* - * mas_reuse_node() - Reuse the node to store the data. - * @wr_mas: The maple write state - * @bn: The maple big node - * @end: The end of the data. - * - * Will always return false in RCU mode. - * - * Return: True if node was reused, false otherwise. - */ -static inline bool mas_reuse_node(struct ma_wr_state *wr_mas, - struct maple_big_node *bn, unsigned char end) -{ - /* Need to be rcu safe. */ - if (mt_in_rcu(wr_mas->mas->tree)) - return false; - - if (end > bn->b_end) { - int clear = mt_slots[wr_mas->type] - bn->b_end; - - memset(wr_mas->slots + bn->b_end, 0, sizeof(void *) * clear--); - memset(wr_mas->pivots + bn->b_end, 0, sizeof(void *) * clear); - } - mab_mas_cp(bn, 0, bn->b_end, wr_mas->mas, false); - return true; + return; } /* * mas_commit_b_node() - Commit the big node into the tree. * @wr_mas: The maple write state * @b_node: The maple big node - * @end: The end of the data. */ -static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas, - struct maple_big_node *b_node, unsigned char end) +static noinline_for_kasan void mas_commit_b_node(struct ma_wr_state *wr_mas, + struct maple_big_node *b_node) { - struct maple_node *node; - struct maple_enode *old_enode; - unsigned char b_end = b_node->b_end; - enum maple_type b_type = b_node->type; - - old_enode = wr_mas->mas->node; - if ((b_end < mt_min_slots[b_type]) && - (!mte_is_root(old_enode)) && - (mas_mt_height(wr_mas->mas) > 1)) - return mas_rebalance(wr_mas->mas, b_node); - - if (b_end >= mt_slots[b_type]) - return mas_split(wr_mas->mas, b_node); + enum store_type type = wr_mas->mas->store_type; - if (mas_reuse_node(wr_mas, b_node, end)) - goto reuse_node; + WARN_ON_ONCE(type != wr_rebalance && type != wr_split_store); - mas_node_count(wr_mas->mas, 1); - if (mas_is_err(wr_mas->mas)) - return 0; + if (type == wr_rebalance) + return mas_rebalance(wr_mas->mas, b_node); - node = mas_pop_node(wr_mas->mas); - node->parent = mas_mn(wr_mas->mas)->parent; - wr_mas->mas->node = mt_mk_node(node, b_type); - mab_mas_cp(b_node, 0, b_end, wr_mas->mas, false); - mas_replace_node(wr_mas->mas, old_enode); -reuse_node: - mas_update_gap(wr_mas->mas); - wr_mas->mas->end = b_end; - return 1; + return mas_split(wr_mas->mas, b_node); } /* @@ -3477,10 +3407,6 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) unsigned long *pivots; int slot = 0; - mas_node_count(mas, 1); - if (unlikely(mas_is_err(mas))) - return 0; - node = mas_pop_node(mas); pivots = ma_pivots(node, type); slots = ma_slots(node, type); @@ -3526,10 +3452,7 @@ static inline void mas_store_root(struct ma_state *mas, void *entry) /* * mas_is_span_wr() - Check if the write needs to be treated as a write that * spans the node. - * @mas: The maple state - * @piv: The pivot value being written - * @type: The maple node type - * @entry: The data to write + * @wr_mas: The maple write state * * Spanning writes are writes that start in one node and end in another OR if * the write of a %NULL will cause the node to end with a %NULL. @@ -3730,10 +3653,8 @@ static void mte_destroy_walk(struct maple_enode *, struct maple_tree *); * @entry: The entry to store. * * Only valid when the index == 0 and the last == ULONG_MAX - * - * Return 0 on error, 1 on success. */ -static inline int mas_new_root(struct ma_state *mas, void *entry) +static inline void mas_new_root(struct ma_state *mas, void *entry) { struct maple_enode *root = mas_root_locked(mas); enum maple_type type = maple_leaf_64; @@ -3749,10 +3670,6 @@ static inline int mas_new_root(struct ma_state *mas, void *entry) goto done; } - mas_node_count(mas, 1); - if (mas_is_err(mas)) - return 0; - node = mas_pop_node(mas); pivots = ma_pivots(node, type); slots = ma_slots(node, type); @@ -3769,7 +3686,7 @@ done: if (xa_is_node(root)) mte_destroy_walk(root, mas->tree); - return 1; + return; } /* * mas_wr_spanning_store() - Create a subtree with the store operation completed @@ -3777,10 +3694,8 @@ done: * Note that mas is expected to point to the node which caused the store to * span. * @wr_mas: The maple write state - * - * Return: 0 on error, positive on success. */ -static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas) +static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas) { struct maple_subtree_state mast; struct maple_big_node b_node; @@ -3815,9 +3730,6 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas) * entries per level plus a new root. */ height = mas_mt_height(mas); - mas_node_count(mas, 1 + height * 3); - if (mas_is_err(mas)) - return 0; /* * Set up right side. Need to get to the next offset after the spanning @@ -3875,10 +3787,8 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas) * @wr_mas: The maple write state * * Attempts to reuse the node, but may allocate. - * - * Return: True if stored, false otherwise */ -static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas, +static inline void mas_wr_node_store(struct ma_wr_state *wr_mas, unsigned char new_end) { struct ma_state *mas = wr_mas->mas; @@ -3889,11 +3799,6 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas, unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type]; bool in_rcu = mt_in_rcu(mas->tree); - /* Check if there is enough data. The room is enough. */ - if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) && - !(mas->mas_flags & MA_STATE_BULK)) - return false; - if (mas->last == wr_mas->end_piv) offset_end++; /* don't copy this offset */ else if (unlikely(wr_mas->r_max == ULONG_MAX)) @@ -3901,10 +3806,6 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas, /* set up node. */ if (in_rcu) { - mas_node_count(mas, 1); - if (mas_is_err(mas)) - return false; - newnode = mas_pop_node(mas); } else { memset(&reuse, 0, sizeof(struct maple_node)); @@ -3960,16 +3861,14 @@ done: trace_ma_write(__func__, mas, 0, wr_mas->entry); mas_update_gap(mas); mas->end = new_end; - return true; + return; } /* * mas_wr_slot_store: Attempt to store a value in a slot. * @wr_mas: the maple write state - * - * Return: True if stored, false otherwise */ -static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas) +static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; unsigned char offset = mas->offset; @@ -4001,7 +3900,7 @@ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas) wr_mas->pivots[offset + 1] = mas->last; mas->offset++; /* Keep mas accurate. */ } else { - return false; + return; } trace_ma_write(__func__, mas, 0, wr_mas->entry); @@ -4012,7 +3911,7 @@ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas) if (!wr_mas->entry || gap) mas_update_gap(mas); - return true; + return; } static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas) @@ -4061,9 +3960,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; else wr_mas->end_piv = wr_mas->mas->max; - - if (!wr_mas->entry) - mas_wr_extend_null(wr_mas); } static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) @@ -4089,23 +3985,13 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) * This is currently unsafe in rcu mode since the end of the node may be cached * by readers while the node contents may be updated which could result in * inaccurate information. - * - * Return: True if appended, false otherwise */ -static inline bool mas_wr_append(struct ma_wr_state *wr_mas, +static inline void mas_wr_append(struct ma_wr_state *wr_mas, unsigned char new_end) { - struct ma_state *mas; + struct ma_state *mas = wr_mas->mas; void __rcu **slots; - unsigned char end; - - mas = wr_mas->mas; - if (mt_in_rcu(mas->tree)) - return false; - - end = mas->end; - if (mas->offset != end) - return false; + unsigned char end = mas->end; if (new_end < mt_pivots[wr_mas->type]) { wr_mas->pivots[new_end] = wr_mas->pivots[end]; @@ -4139,7 +4025,7 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas, mas->end = new_end; trace_ma_write(__func__, mas, new_end, wr_mas->entry); - return true; + return; } /* @@ -4155,76 +4041,235 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas) trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry); memset(&b_node, 0, sizeof(struct maple_big_node)); mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end); - mas_commit_b_node(wr_mas, &b_node, wr_mas->mas->end); + mas_commit_b_node(wr_mas, &b_node); } -static inline void mas_wr_modify(struct ma_wr_state *wr_mas) +/* + * mas_wr_store_entry() - Internal call to store a value + * @wr_mas: The maple write state + */ +static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; - unsigned char new_end; + unsigned char new_end = mas_wr_new_end(wr_mas); - /* Direct replacement */ - if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) { + switch (mas->store_type) { + case wr_invalid: + MT_BUG_ON(mas->tree, 1); + return; + case wr_new_root: + mas_new_root(mas, wr_mas->entry); + break; + case wr_store_root: + mas_store_root(mas, wr_mas->entry); + break; + case wr_exact_fit: rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); if (!!wr_mas->entry ^ !!wr_mas->content) mas_update_gap(mas); - return; + break; + case wr_append: + mas_wr_append(wr_mas, new_end); + break; + case wr_slot_store: + mas_wr_slot_store(wr_mas); + break; + case wr_node_store: + mas_wr_node_store(wr_mas, new_end); + break; + case wr_spanning_store: + mas_wr_spanning_store(wr_mas); + break; + case wr_split_store: + case wr_rebalance: + mas_wr_bnode(wr_mas); + break; + } + + return; +} + +static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas = wr_mas->mas; + + if (!mas_is_active(mas)) { + if (mas_is_start(mas)) + goto set_content; + + if (unlikely(mas_is_paused(mas))) + goto reset; + + if (unlikely(mas_is_none(mas))) + goto reset; + + if (unlikely(mas_is_overflow(mas))) + goto reset; + + if (unlikely(mas_is_underflow(mas))) + goto reset; } /* - * new_end exceeds the size of the maple node and cannot enter the fast - * path. + * A less strict version of mas_is_span_wr() where we allow spanning + * writes within this node. This is to stop partial walks in + * mas_prealloc() from being reset. */ - new_end = mas_wr_new_end(wr_mas); - if (new_end >= mt_slots[wr_mas->type]) - goto slow_path; - - /* Attempt to append */ - if (mas_wr_append(wr_mas, new_end)) - return; + if (mas->last > mas->max) + goto reset; - if (new_end == mas->end && mas_wr_slot_store(wr_mas)) - return; + if (wr_mas->entry) + goto set_content; - if (mas_wr_node_store(wr_mas, new_end)) - return; + if (mte_is_leaf(mas->node) && mas->last == mas->max) + goto reset; - if (mas_is_err(mas)) - return; + goto set_content; -slow_path: - mas_wr_bnode(wr_mas); +reset: + mas_reset(mas); +set_content: + wr_mas->content = mas_start(mas); } -/* - * mas_wr_store_entry() - Internal call to store a value +/** + * mas_prealloc_calc() - Calculate number of nodes needed for a + * given store oepration * @mas: The maple state - * @entry: The entry to store. + * @entry: The entry to store into the tree * - * Return: The contents that was stored at the index. + * Return: Number of nodes required for preallocation. */ -static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) +static inline int mas_prealloc_calc(struct ma_state *mas, void *entry) +{ + int ret = mas_mt_height(mas) * 3 + 1; + + switch (mas->store_type) { + case wr_invalid: + WARN_ON_ONCE(1); + break; + case wr_new_root: + ret = 1; + break; + case wr_store_root: + if (likely((mas->last != 0) || (mas->index != 0))) + ret = 1; + else if (((unsigned long) (entry) & 3) == 2) + ret = 1; + else + ret = 0; + break; + case wr_spanning_store: + ret = mas_mt_height(mas) * 3 + 1; + break; + case wr_split_store: + ret = mas_mt_height(mas) * 2 + 1; + break; + case wr_rebalance: + ret = mas_mt_height(mas) * 2 - 1; + break; + case wr_node_store: + ret = mt_in_rcu(mas->tree) ? 1 : 0; + break; + case wr_append: + case wr_exact_fit: + case wr_slot_store: + ret = 0; + } + + return ret; +} + +/* + * mas_wr_store_type() - Set the store type for a given + * store operation. + * @wr_mas: The maple write state + */ +static inline void mas_wr_store_type(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; + unsigned char new_end; - wr_mas->content = mas_start(mas); - if (mas_is_none(mas) || mas_is_ptr(mas)) { - mas_store_root(mas, wr_mas->entry); + if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) { + mas->store_type = wr_store_root; return; } if (unlikely(!mas_wr_walk(wr_mas))) { - mas_wr_spanning_store(wr_mas); + mas->store_type = wr_spanning_store; return; } /* At this point, we are at the leaf node that needs to be altered. */ mas_wr_end_piv(wr_mas); - /* New root for a single pointer */ - if (unlikely(!mas->index && mas->last == ULONG_MAX)) - mas_new_root(mas, wr_mas->entry); - else - mas_wr_modify(wr_mas); + if (!wr_mas->entry) + mas_wr_extend_null(wr_mas); + + new_end = mas_wr_new_end(wr_mas); + if ((wr_mas->r_min == mas->index) && (wr_mas->r_max == mas->last)) { + mas->store_type = wr_exact_fit; + return; + } + + if (unlikely(!mas->index && mas->last == ULONG_MAX)) { + mas->store_type = wr_new_root; + return; + } + + /* Potential spanning rebalance collapsing a node */ + if (new_end < mt_min_slots[wr_mas->type]) { + if (!mte_is_root(mas->node)) { + mas->store_type = wr_rebalance; + return; + } + mas->store_type = wr_node_store; + return; + } + + if (new_end >= mt_slots[wr_mas->type]) { + mas->store_type = wr_split_store; + return; + } + + if (!mt_in_rcu(mas->tree) && (mas->offset == mas->end)) { + mas->store_type = wr_append; + return; + } + + if ((new_end == mas->end) && (!mt_in_rcu(mas->tree) || + (wr_mas->offset_end - mas->offset == 1))) { + mas->store_type = wr_slot_store; + return; + } + + if (mte_is_root(mas->node) || (new_end >= mt_min_slots[wr_mas->type]) || + (mas->mas_flags & MA_STATE_BULK)) { + mas->store_type = wr_node_store; + return; + } + + mas->store_type = wr_invalid; + MAS_WARN_ON(mas, 1); +} + +/** + * mas_wr_preallocate() - Preallocate enough nodes for a store operation + * @wr_mas: The maple write state + * @entry: The entry that will be stored + * + */ +static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry) +{ + struct ma_state *mas = wr_mas->mas; + int request; + + mas_wr_prealloc_setup(wr_mas); + mas_wr_store_type(wr_mas); + request = mas_prealloc_calc(mas, entry); + if (!request) + return; + + mas_node_count(mas, request); } /** @@ -4257,26 +4302,24 @@ static inline void *mas_insert(struct ma_state *mas, void *entry) if (wr_mas.content) goto exists; - if (mas_is_none(mas) || mas_is_ptr(mas)) { - mas_store_root(mas, entry); + mas_wr_preallocate(&wr_mas, entry); + if (mas_is_err(mas)) return NULL; - } /* spanning writes always overwrite something */ - if (!mas_wr_walk(&wr_mas)) + if (mas->store_type == wr_spanning_store) goto exists; /* At this point, we are at the leaf node that needs to be altered. */ - wr_mas.offset_end = mas->offset; - wr_mas.end_piv = wr_mas.r_max; - - if (wr_mas.content || (mas->last > wr_mas.r_max)) - goto exists; + if (mas->store_type != wr_new_root && mas->store_type != wr_store_root) { + wr_mas.offset_end = mas->offset; + wr_mas.end_piv = wr_mas.r_max; - if (!entry) - return NULL; + if (wr_mas.content || (mas->last > wr_mas.r_max)) + goto exists; + } - mas_wr_modify(&wr_mas); + mas_wr_store_entry(&wr_mas); return wr_mas.content; exists: @@ -4331,6 +4374,7 @@ int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, if (*next == 0) mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED; + mas_destroy(mas); return ret; } EXPORT_SYMBOL(mas_alloc_cyclic); @@ -4440,9 +4484,8 @@ no_entry: * mas_prev_slot() - Get the entry in the previous slot * * @mas: The maple state - * @max: The minimum starting range + * @min: The minimum starting range * @empty: Can be empty - * @set_underflow: Set the @mas->node to underflow state on limit. * * Return: The entry in the previous slot which is possibly NULL */ @@ -4525,6 +4568,7 @@ underflow: /* * mas_next_node() - Get the next node at the same level in the tree. * @mas: The maple state + * @node: The maple node * @max: The maximum pivot value to check. * * The next value will be mas->node[mas->offset] or the status will have @@ -4615,8 +4659,6 @@ overflow: * @mas: The maple state * @max: The maximum starting range * @empty: Can be empty - * @set_overflow: Should @mas->node be set to overflow when the limit is - * reached. * * Return: The entry in the next slot which is possibly NULL */ @@ -5150,9 +5192,9 @@ EXPORT_SYMBOL_GPL(mas_empty_area_rev); /* * mte_dead_leaves() - Mark all leaves of a node as dead. - * @mas: The maple state + * @enode: the encoded node + * @mt: the maple tree * @slots: Pointer to the slot array - * @type: The maple node type * * Must hold the write lock. * @@ -5358,47 +5400,6 @@ static inline void mte_destroy_walk(struct maple_enode *enode, mt_destroy_walk(enode, mt, true); } } - -static void mas_wr_store_setup(struct ma_wr_state *wr_mas) -{ - if (!mas_is_active(wr_mas->mas)) { - if (mas_is_start(wr_mas->mas)) - return; - - if (unlikely(mas_is_paused(wr_mas->mas))) - goto reset; - - if (unlikely(mas_is_none(wr_mas->mas))) - goto reset; - - if (unlikely(mas_is_overflow(wr_mas->mas))) - goto reset; - - if (unlikely(mas_is_underflow(wr_mas->mas))) - goto reset; - } - - /* - * A less strict version of mas_is_span_wr() where we allow spanning - * writes within this node. This is to stop partial walks in - * mas_prealloc() from being reset. - */ - if (wr_mas->mas->last > wr_mas->mas->max) - goto reset; - - if (wr_mas->entry) - return; - - if (mte_is_leaf(wr_mas->mas->node) && - wr_mas->mas->last == wr_mas->mas->max) - goto reset; - - return; - -reset: - mas_reset(wr_mas->mas); -} - /* Interface */ /** @@ -5407,13 +5408,12 @@ reset: * @entry: The entry to store. * * The @mas->index and @mas->last is used to set the range for the @entry. - * Note: The @mas should have pre-allocated entries to ensure there is memory to - * store the entry. Please see mas_expected_entries()/mas_destroy() for more details. * * Return: the first entry between mas->index and mas->last or %NULL. */ void *mas_store(struct ma_state *mas, void *entry) { + int request; MA_WR_STATE(wr_mas, mas, entry); trace_ma_write(__func__, mas, 0, entry); @@ -5434,8 +5434,25 @@ void *mas_store(struct ma_state *mas, void *entry) * want to examine what happens if a single store operation was to * overwrite multiple entries within a self-balancing B-Tree. */ - mas_wr_store_setup(&wr_mas); + mas_wr_prealloc_setup(&wr_mas); + mas_wr_store_type(&wr_mas); + if (mas->mas_flags & MA_STATE_PREALLOC) { + mas_wr_store_entry(&wr_mas); + MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); + return wr_mas.content; + } + + request = mas_prealloc_calc(mas, entry); + if (!request) + goto store; + + mas_node_count(mas, request); + if (mas_is_err(mas)) + return NULL; + +store: mas_wr_store_entry(&wr_mas); + mas_destroy(mas); return wr_mas.content; } EXPORT_SYMBOL_GPL(mas_store); @@ -5451,19 +5468,28 @@ EXPORT_SYMBOL_GPL(mas_store); */ int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp) { + unsigned long index = mas->index; + unsigned long last = mas->last; MA_WR_STATE(wr_mas, mas, entry); + int ret = 0; - mas_wr_store_setup(&wr_mas); - trace_ma_write(__func__, mas, 0, entry); retry: - mas_wr_store_entry(&wr_mas); - if (unlikely(mas_nomem(mas, gfp))) + mas_wr_preallocate(&wr_mas, entry); + if (unlikely(mas_nomem(mas, gfp))) { + if (!entry) + __mas_set_range(mas, index, last); goto retry; + } - if (unlikely(mas_is_err(mas))) - return xa_err(mas->node); + if (mas_is_err(mas)) { + ret = xa_err(mas->node); + goto out; + } - return 0; + mas_wr_store_entry(&wr_mas); +out: + mas_destroy(mas); + return ret; } EXPORT_SYMBOL_GPL(mas_store_gfp); @@ -5477,7 +5503,19 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) { MA_WR_STATE(wr_mas, mas, entry); - mas_wr_store_setup(&wr_mas); + if (mas->store_type == wr_store_root) { + mas_wr_prealloc_setup(&wr_mas); + goto store; + } + + mas_wr_walk_descend(&wr_mas); + if (mas->store_type != wr_spanning_store) { + /* set wr_mas->content to current slot */ + wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); + mas_wr_end_piv(&wr_mas); + } + +store: trace_ma_write(__func__, mas, 0, entry); mas_wr_store_entry(&wr_mas); MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); @@ -5496,70 +5534,25 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc); int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) { MA_WR_STATE(wr_mas, mas, entry); - unsigned char node_size; - int request = 1; - int ret; - - - if (unlikely(!mas->index && mas->last == ULONG_MAX)) - goto ask_now; - - mas_wr_store_setup(&wr_mas); - wr_mas.content = mas_start(mas); - /* Root expand */ - if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) - goto ask_now; - - if (unlikely(!mas_wr_walk(&wr_mas))) { - /* Spanning store, use worst case for now */ - request = 1 + mas_mt_height(mas) * 3; - goto ask_now; - } - - /* At this point, we are at the leaf node that needs to be altered. */ - /* Exact fit, no nodes needed. */ - if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last) - return 0; - - mas_wr_end_piv(&wr_mas); - node_size = mas_wr_new_end(&wr_mas); + int ret = 0; + int request; - /* Slot store, does not require additional nodes */ - if (node_size == mas->end) { - /* reuse node */ - if (!mt_in_rcu(mas->tree)) - return 0; - /* shifting boundary */ - if (wr_mas.offset_end - mas->offset == 1) - return 0; - } + mas_wr_prealloc_setup(&wr_mas); + mas_wr_store_type(&wr_mas); + request = mas_prealloc_calc(mas, entry); + if (!request) + return ret; - if (node_size >= mt_slots[wr_mas.type]) { - /* Split, worst case for now. */ - request = 1 + mas_mt_height(mas) * 2; - goto ask_now; + mas_node_count_gfp(mas, request, gfp); + if (mas_is_err(mas)) { + mas_set_alloc_req(mas, 0); + ret = xa_err(mas->node); + mas_destroy(mas); + mas_reset(mas); + return ret; } - /* New root needs a single node */ - if (unlikely(mte_is_root(mas->node))) - goto ask_now; - - /* Potential spanning rebalance collapsing a node, use worst-case */ - if (node_size - 1 <= mt_min_slots[wr_mas.type]) - request = mas_mt_height(mas) * 2 - 1; - - /* node store, slot store needs one node */ -ask_now: - mas_node_count_gfp(mas, request, gfp); mas->mas_flags |= MA_STATE_PREALLOC; - if (likely(!mas_is_err(mas))) - return 0; - - mas_set_alloc_req(mas, 0); - ret = xa_err(mas->node); - mas_reset(mas); - mas_destroy(mas); - mas_reset(mas); return ret; } EXPORT_SYMBOL_GPL(mas_preallocate); @@ -5585,7 +5578,8 @@ void mas_destroy(struct ma_state *mas) */ if (mas->mas_flags & MA_STATE_REBALANCE) { unsigned char end; - + if (mas_is_err(mas)) + mas_reset(mas); mas_start(mas); mtree_range_walk(mas); end = mas->end + 1; @@ -6245,24 +6239,32 @@ EXPORT_SYMBOL_GPL(mas_find_range_rev); void *mas_erase(struct ma_state *mas) { void *entry; + unsigned long index = mas->index; MA_WR_STATE(wr_mas, mas, NULL); if (!mas_is_active(mas) || !mas_is_start(mas)) mas->status = ma_start; - /* Retry unnecessary when holding the write lock. */ +write_retry: entry = mas_state_walk(mas); if (!entry) return NULL; -write_retry: /* Must reset to ensure spanning writes of last slot are detected */ mas_reset(mas); - mas_wr_store_setup(&wr_mas); - mas_wr_store_entry(&wr_mas); - if (mas_nomem(mas, GFP_KERNEL)) + mas_wr_preallocate(&wr_mas, NULL); + if (mas_nomem(mas, GFP_KERNEL)) { + /* in case the range of entry changed when unlocked */ + mas->index = mas->last = index; goto write_retry; + } + if (mas_is_err(mas)) + goto out; + + mas_wr_store_entry(&wr_mas); +out: + mas_destroy(mas); return entry; } EXPORT_SYMBOL_GPL(mas_erase); @@ -6277,10 +6279,8 @@ EXPORT_SYMBOL_GPL(mas_erase); bool mas_nomem(struct ma_state *mas, gfp_t gfp) __must_hold(mas->tree->ma_lock) { - if (likely(mas->node != MA_ERROR(-ENOMEM))) { - mas_destroy(mas); + if (likely(mas->node != MA_ERROR(-ENOMEM))) return false; - } if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) { mtree_unlock(mas->tree); @@ -6357,7 +6357,7 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index, unsigned long last, void *entry, gfp_t gfp) { MA_STATE(mas, mt, index, last); - MA_WR_STATE(wr_mas, &mas, entry); + int ret = 0; trace_ma_write(__func__, &mas, 0, entry); if (WARN_ON_ONCE(xa_is_advanced(entry))) @@ -6367,16 +6367,10 @@ int mtree_store_range(struct maple_tree *mt, unsigned long index, return -EINVAL; mtree_lock(mt); -retry: - mas_wr_store_entry(&wr_mas); - if (mas_nomem(&mas, gfp)) - goto retry; - + ret = mas_store_gfp(&mas, entry, gfp); mtree_unlock(mt); - if (mas_is_err(&mas)) - return xa_err(mas.node); - return 0; + return ret; } EXPORT_SYMBOL(mtree_store_range); @@ -6412,6 +6406,7 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp) { MA_STATE(ms, mt, first, last); + int ret = 0; if (WARN_ON_ONCE(xa_is_advanced(entry))) return -EINVAL; @@ -6427,9 +6422,10 @@ retry: mtree_unlock(mt); if (mas_is_err(&ms)) - return xa_err(ms.node); + ret = xa_err(ms.node); - return 0; + mas_destroy(&ms); + return ret; } EXPORT_SYMBOL(mtree_insert_range); @@ -6484,6 +6480,7 @@ retry: unlock: mtree_unlock(mt); + mas_destroy(&mas); return ret; } EXPORT_SYMBOL(mtree_alloc_range); @@ -6565,6 +6562,7 @@ retry: unlock: mtree_unlock(mt); + mas_destroy(&mas); return ret; } EXPORT_SYMBOL(mtree_alloc_rrange); @@ -6997,6 +6995,19 @@ void mt_set_non_kernel(unsigned int val) kmem_cache_set_non_kernel(maple_node_cache, val); } +extern void kmem_cache_set_callback(struct kmem_cache *cachep, + void (*callback)(void *)); +void mt_set_callback(void (*callback)(void *)) +{ + kmem_cache_set_callback(maple_node_cache, callback); +} + +extern void kmem_cache_set_private(struct kmem_cache *cachep, void *private); +void mt_set_private(void *private) +{ + kmem_cache_set_private(maple_node_cache, private); +} + extern unsigned long kmem_cache_get_alloc(struct kmem_cache *); unsigned long mt_get_alloc_size(void) { @@ -7181,7 +7192,6 @@ static void mt_dump_arange64(const struct maple_tree *mt, void *entry, enum mt_dump_format format) { struct maple_arange_64 *node = &mte_to_node(entry)->ma64; - bool leaf = mte_is_leaf(entry); unsigned long first = min; int i; @@ -7215,19 +7225,22 @@ static void mt_dump_arange64(const struct maple_tree *mt, void *entry, break; if (last == 0 && i > 0) break; - if (leaf) - mt_dump_entry(mt_slot(mt, node->slot, i), - first, last, depth + 1, format); - else if (node->slot[i]) + if (node->slot[i]) mt_dump_node(mt, mt_slot(mt, node->slot, i), first, last, depth + 1, format); if (last == max) break; if (last > max) { - pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n", + switch(format) { + case mt_dump_hex: + pr_err("node %p last (%lx) > max (%lx) at pivot %d!\n", node, last, max, i); - break; + break; + case mt_dump_dec: + pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n", + node, last, max, i); + } } first = last + 1; } @@ -7566,14 +7579,14 @@ static void mt_validate_nulls(struct maple_tree *mt) * 2. The gap is correctly set in the parents */ void mt_validate(struct maple_tree *mt) + __must_hold(mas->tree->ma_lock) { unsigned char end; MA_STATE(mas, mt, 0, 0); - rcu_read_lock(); mas_start(&mas); if (!mas_is_active(&mas)) - goto done; + return; while (!mte_is_leaf(mas.node)) mas_descend(&mas); @@ -7594,9 +7607,6 @@ void mt_validate(struct maple_tree *mt) mas_dfs_postorder(&mas, ULONG_MAX); } mt_validate_nulls(mt); -done: - rcu_read_unlock(); - } EXPORT_SYMBOL_GPL(mt_validate); @@ -7630,6 +7640,40 @@ void mas_dump(const struct ma_state *mas) break; } + pr_err("Store Type: "); + switch (mas->store_type) { + case wr_invalid: + pr_err("invalid store type\n"); + break; + case wr_new_root: + pr_err("new_root\n"); + break; + case wr_store_root: + pr_err("store_root\n"); + break; + case wr_exact_fit: + pr_err("exact_fit\n"); + break; + case wr_split_store: + pr_err("split_store\n"); + break; + case wr_slot_store: + pr_err("slot_store\n"); + break; + case wr_append: + pr_err("append\n"); + break; + case wr_node_store: + pr_err("node_store\n"); + break; + case wr_spanning_store: + pr_err("spanning_store\n"); + break; + case wr_rebalance: + pr_err("rebalance\n"); + break; + } + pr_err("[%u/%u] index=%lx last=%lx\n", mas->offset, mas->end, mas->index, mas->last); pr_err(" min=%lx max=%lx alloc=%p, depth=%u, flags=%x\n", diff --git a/lib/math/Makefile b/lib/math/Makefile index 981a26127e08..3ef11305f8d2 100644 --- a/lib/math/Makefile +++ b/lib/math/Makefile @@ -5,6 +5,7 @@ obj-$(CONFIG_CORDIC) += cordic.o obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o obj-$(CONFIG_RATIONAL) += rational.o +obj-$(CONFIG_INT_POW_TEST) += tests/int_pow_kunit.o obj-$(CONFIG_TEST_DIV64) += test_div64.o obj-$(CONFIG_TEST_MULDIV64) += test_mul_u64_u64_div_u64.o obj-$(CONFIG_RATIONAL_KUNIT_TEST) += rational-test.o diff --git a/lib/math/tests/Makefile b/lib/math/tests/Makefile new file mode 100644 index 000000000000..6a169123320a --- /dev/null +++ b/lib/math/tests/Makefile @@ -0,0 +1,3 @@ +# SPDX-License-Identifier: GPL-2.0-only + +obj-$(CONFIG_INT_POW_TEST) += int_pow_kunit.o diff --git a/lib/math/tests/int_pow_kunit.c b/lib/math/tests/int_pow_kunit.c new file mode 100644 index 000000000000..34b33677d458 --- /dev/null +++ b/lib/math/tests/int_pow_kunit.c @@ -0,0 +1,52 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <kunit/test.h> +#include <linux/math.h> + +struct test_case_params { + u64 base; + unsigned int exponent; + u64 expected_result; + const char *name; +}; + +static const struct test_case_params params[] = { + { 64, 0, 1, "Power of zero" }, + { 64, 1, 64, "Power of one"}, + { 0, 5, 0, "Base zero" }, + { 1, 64, 1, "Base one" }, + { 2, 2, 4, "Two squared"}, + { 2, 3, 8, "Two cubed"}, + { 5, 5, 3125, "Five raised to the fifth power" }, + { U64_MAX, 1, U64_MAX, "Max base" }, + { 2, 63, 9223372036854775808ULL, "Large result"}, +}; + +static void get_desc(const struct test_case_params *tc, char *desc) +{ + strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE); +} + +KUNIT_ARRAY_PARAM(int_pow, params, get_desc); + +static void int_pow_test(struct kunit *test) +{ + const struct test_case_params *tc = (const struct test_case_params *)test->param_value; + + KUNIT_EXPECT_EQ(test, tc->expected_result, int_pow(tc->base, tc->exponent)); +} + +static struct kunit_case math_int_pow_test_cases[] = { + KUNIT_CASE_PARAM(int_pow_test, int_pow_gen_params), + {} +}; + +static struct kunit_suite int_pow_test_suite = { + .name = "math-int_pow", + .test_cases = math_int_pow_test_cases, +}; + +kunit_test_suites(&int_pow_test_suite); + +MODULE_DESCRIPTION("math.int_pow KUnit test suite"); +MODULE_LICENSE("GPL"); diff --git a/lib/scatterlist.c b/lib/scatterlist.c index 7bc2220fea80..473b2646f71c 100644 --- a/lib/scatterlist.c +++ b/lib/scatterlist.c @@ -11,6 +11,7 @@ #include <linux/kmemleak.h> #include <linux/bvec.h> #include <linux/uio.h> +#include <linux/folio_queue.h> /** * sg_next - return the next scatterlist entry in a list @@ -1262,6 +1263,67 @@ static ssize_t extract_kvec_to_sg(struct iov_iter *iter, } /* + * Extract up to sg_max folios from an FOLIOQ-type iterator and add them to + * the scatterlist. The pages are not pinned. + */ +static ssize_t extract_folioq_to_sg(struct iov_iter *iter, + ssize_t maxsize, + struct sg_table *sgtable, + unsigned int sg_max, + iov_iter_extraction_t extraction_flags) +{ + const struct folio_queue *folioq = iter->folioq; + struct scatterlist *sg = sgtable->sgl + sgtable->nents; + unsigned int slot = iter->folioq_slot; + ssize_t ret = 0; + size_t offset = iter->iov_offset; + + BUG_ON(!folioq); + + if (slot >= folioq_nr_slots(folioq)) { + folioq = folioq->next; + if (WARN_ON_ONCE(!folioq)) + return 0; + slot = 0; + } + + do { + struct folio *folio = folioq_folio(folioq, slot); + size_t fsize = folioq_folio_size(folioq, slot); + + if (offset < fsize) { + size_t part = umin(maxsize - ret, fsize - offset); + + sg_set_page(sg, folio_page(folio, 0), part, offset); + sgtable->nents++; + sg++; + sg_max--; + offset += part; + ret += part; + } + + if (offset >= fsize) { + offset = 0; + slot++; + if (slot >= folioq_nr_slots(folioq)) { + if (!folioq->next) { + WARN_ON_ONCE(ret < iter->count); + break; + } + folioq = folioq->next; + slot = 0; + } + } + } while (sg_max > 0 && ret < maxsize); + + iter->folioq = folioq; + iter->folioq_slot = slot; + iter->iov_offset = offset; + iter->count -= ret; + return ret; +} + +/* * Extract up to sg_max folios from an XARRAY-type iterator and add them to * the scatterlist. The pages are not pinned. */ @@ -1323,8 +1385,8 @@ static ssize_t extract_xarray_to_sg(struct iov_iter *iter, * addition of @sg_max elements. * * The pages referred to by UBUF- and IOVEC-type iterators are extracted and - * pinned; BVEC-, KVEC- and XARRAY-type are extracted but aren't pinned; PIPE- - * and DISCARD-type are not supported. + * pinned; BVEC-, KVEC-, FOLIOQ- and XARRAY-type are extracted but aren't + * pinned; DISCARD-type is not supported. * * No end mark is placed on the scatterlist; that's left to the caller. * @@ -1356,6 +1418,9 @@ ssize_t extract_iter_to_sg(struct iov_iter *iter, size_t maxsize, case ITER_KVEC: return extract_kvec_to_sg(iter, maxsize, sgtable, sg_max, extraction_flags); + case ITER_FOLIOQ: + return extract_folioq_to_sg(iter, maxsize, sgtable, sg_max, + extraction_flags); case ITER_XARRAY: return extract_xarray_to_sg(iter, maxsize, sgtable, sg_max, extraction_flags); diff --git a/lib/slub_kunit.c b/lib/slub_kunit.c index e6667a28c014..6e3a1e5a7142 100644 --- a/lib/slub_kunit.c +++ b/lib/slub_kunit.c @@ -5,6 +5,7 @@ #include <linux/slab.h> #include <linux/module.h> #include <linux/kernel.h> +#include <linux/rcupdate.h> #include "../mm/slab.h" static struct kunit_resource resource; @@ -157,6 +158,34 @@ static void test_kmalloc_redzone_access(struct kunit *test) kmem_cache_destroy(s); } +struct test_kfree_rcu_struct { + struct rcu_head rcu; +}; + +static void test_kfree_rcu(struct kunit *test) +{ + struct kmem_cache *s = test_kmem_cache_create("TestSlub_kfree_rcu", + sizeof(struct test_kfree_rcu_struct), + SLAB_NO_MERGE); + struct test_kfree_rcu_struct *p = kmem_cache_alloc(s, GFP_KERNEL); + + kfree_rcu(p, rcu); + kmem_cache_destroy(s); + + KUNIT_EXPECT_EQ(test, 0, slab_errors); +} + +static void test_leak_destroy(struct kunit *test) +{ + struct kmem_cache *s = test_kmem_cache_create("TestSlub_kfree_rcu", + 64, SLAB_NO_MERGE); + kmem_cache_alloc(s, GFP_KERNEL); + + kmem_cache_destroy(s); + + KUNIT_EXPECT_EQ(test, 1, slab_errors); +} + static int test_init(struct kunit *test) { slab_errors = 0; @@ -177,6 +206,8 @@ static struct kunit_case test_cases[] = { KUNIT_CASE(test_clobber_redzone_free), KUNIT_CASE(test_kmalloc_redzone_access), + KUNIT_CASE(test_kfree_rcu), + KUNIT_CASE(test_leak_destroy), {} }; diff --git a/lib/string_helpers.c b/lib/string_helpers.c index 69ba49b853c7..4f887aa62fa0 100644 --- a/lib/string_helpers.c +++ b/lib/string_helpers.c @@ -321,6 +321,9 @@ int string_unescape(char *src, char *dst, size_t size, unsigned int flags) { char *out = dst; + if (!size) + size = SIZE_MAX; + while (*src && --size) { if (src[0] == '\\' && src[1] != '\0' && size > 1) { src++; diff --git a/lib/test_bpf.c b/lib/test_bpf.c index ca4b0eea81a2..fa5edd6ef7f7 100644 --- a/lib/test_bpf.c +++ b/lib/test_bpf.c @@ -15077,8 +15077,7 @@ static struct skb_segment_test skb_segment_tests[] __initconst = { .build_skb = build_test_skb_linear_no_head_frag, .features = NETIF_F_SG | NETIF_F_FRAGLIST | NETIF_F_HW_VLAN_CTAG_TX | NETIF_F_GSO | - NETIF_F_LLTX | NETIF_F_GRO | - NETIF_F_IPV6_CSUM | NETIF_F_RXCSUM | + NETIF_F_GRO | NETIF_F_IPV6_CSUM | NETIF_F_RXCSUM | NETIF_F_HW_VLAN_STAG_TX } }; diff --git a/lib/test_fortify/.gitignore b/lib/test_fortify/.gitignore new file mode 100644 index 000000000000..c1ba37d14b50 --- /dev/null +++ b/lib/test_fortify/.gitignore @@ -0,0 +1,2 @@ +# SPDX-License-Identifier: GPL-2.0-only +/*.log diff --git a/lib/test_fortify/Makefile b/lib/test_fortify/Makefile new file mode 100644 index 000000000000..1c3f82ad8bb2 --- /dev/null +++ b/lib/test_fortify/Makefile @@ -0,0 +1,28 @@ +# SPDX-License-Identifier: GPL-2.0 + +ccflags-y := $(call cc-disable-warning,fortify-source) + +quiet_cmd_test_fortify = TEST $@ + cmd_test_fortify = $(CONFIG_SHELL) $(src)/test_fortify.sh \ + $< $@ "$(NM)" $(CC) $(c_flags) -DKBUILD_EXTRA_WARN1 + +$(obj)/%.log: $(src)/%.c $(src)/test_fortify.sh FORCE + $(call if_changed_dep,test_fortify) + +logs = $(patsubst $(src)/%.c, %.log, $(wildcard $(src)/*-*.c)) +targets += $(logs) + +quiet_cmd_gen_fortify_log = CAT $@ + cmd_gen_fortify_log = cat $(or $(real-prereqs),/dev/null) > $@ + +$(obj)/test_fortify.log: $(addprefix $(obj)/, $(logs)) FORCE + $(call if_changed,gen_fortify_log) + +# GCC<=7 does not always produce *.d files. +# Run the tests only for GCC>=8 or Clang. +always-$(call gcc-min-version, 80000) += test_fortify.log +always-$(CONFIG_CC_IS_CLANG) += test_fortify.log + +# Some architectures define __NO_FORTIFY if __SANITIZE_ADDRESS__ is undefined. +# Pass CFLAGS_KASAN to avoid warnings. +KASAN_SANITIZE := y diff --git a/lib/test_fortify/test_fortify.sh b/lib/test_fortify/test_fortify.sh new file mode 100644 index 000000000000..c2688ab8281d --- /dev/null +++ b/lib/test_fortify/test_fortify.sh @@ -0,0 +1,66 @@ +#!/bin/sh +# SPDX-License-Identifier: GPL-2.0-only +set -e + +# Argument 1: Source file to build. +IN="$1" +shift +# Extract just the filename for error messages below. +FILE="${IN##*/}" +# Extract the function name for error messages below. +FUNC="${FILE#*-}" +FUNC="${FUNC%%-*}" +FUNC="${FUNC%%.*}" +# Extract the symbol to test for in build/symbol test below. +WANT="__${FILE%%-*}" + +# Argument 2: Where to write the build log. +OUT="$1" +shift +TMP="${OUT}.tmp" + +# Argument 3: Path to "nm" tool. +NM="$1" +shift + +# Remaining arguments are: $(CC) $(c_flags) + +# Clean up temporary file at exit. +__cleanup() { + rm -f "$TMP" +} +trap __cleanup EXIT + +# Function names in warnings are wrapped in backticks under UTF-8 locales. +# Run the commands with LANG=C so that grep output will not change. +export LANG=C + +status= +# Attempt to build a source that is expected to fail with a specific warning. +if "$@" -Werror -c "$IN" -o "$OUT".o 2> "$TMP" ; then + # If the build succeeds, either the test has failed or the + # warning may only happen at link time (Clang). In that case, + # make sure the expected symbol is unresolved in the symbol list. + # If so, FORTIFY is working for this case. + if ! $NM -A "$OUT".o | grep -m1 "\bU ${WANT}$" >>"$TMP" ; then + status="warning: unsafe ${FUNC}() usage lacked '$WANT' symbol in $IN" + fi +else + # If the build failed, check for the warning in the stderr. + # GCC: + # ./include/linux/fortify-string.h:316:25: error: call to '__write_overflow_field' declared with attribute warning: detected write beyond size of field (1st parameter); maybe use struct_group()? [-Werror=attribute-warning] + # Clang 14: + # ./include/linux/fortify-string.h:316:4: error: call to __write_overflow_field declared with 'warning' attribute: detected write beyond size of field (1st parameter); maybe use struct_group()? [-Werror,-Wattribute-warning] + if ! grep -Eq -m1 "error: call to .?\b${WANT}\b.?" "$TMP" ; then + status="warning: unsafe ${FUNC}() usage lacked '$WANT' warning in $IN" + fi +fi + +if [ -n "$status" ]; then + # Report on failure results, including compilation warnings. + echo "$status" | tee "$OUT" >&2 +else + # Report on good results, and save any compilation output to log. + echo "ok: unsafe ${FUNC}() usage correctly detected with '$WANT' in $IN" >"$OUT" +fi +cat "$TMP" >>"$OUT" diff --git a/lib/test_hmm.c b/lib/test_hmm.c index ee20e1f9bae9..056f2e411d7b 100644 --- a/lib/test_hmm.c +++ b/lib/test_hmm.c @@ -799,10 +799,7 @@ static int dmirror_exclusive(struct dmirror *dmirror, unsigned long mapped = 0; int i; - if (end < addr + (ARRAY_SIZE(pages) << PAGE_SHIFT)) - next = end; - else - next = addr + (ARRAY_SIZE(pages) << PAGE_SHIFT); + next = min(end, addr + (ARRAY_SIZE(pages) << PAGE_SHIFT)); ret = make_device_exclusive_range(mm, addr, next, pages, NULL); /* diff --git a/lib/test_printf.c b/lib/test_printf.c index 965cb6f28527..8448b6d02bd9 100644 --- a/lib/test_printf.c +++ b/lib/test_printf.c @@ -641,26 +641,12 @@ page_flags_test(int section, int node, int zone, int last_cpupid, test(cmp_buf, "%pGp", &flags); } -static void __init page_type_test(unsigned int page_type, const char *name, - char *cmp_buf) -{ - unsigned long size; - - size = scnprintf(cmp_buf, BUF_SIZE, "%#x(", page_type); - if (page_type_has_type(page_type)) - size += scnprintf(cmp_buf + size, BUF_SIZE - size, "%s", name); - - snprintf(cmp_buf + size, BUF_SIZE - size, ")"); - test(cmp_buf, "%pGt", &page_type); -} - static void __init flags(void) { unsigned long flags; char *cmp_buffer; gfp_t gfp; - unsigned int page_type; cmp_buffer = kmalloc(BUF_SIZE, GFP_KERNEL); if (!cmp_buffer) @@ -700,18 +686,6 @@ flags(void) gfp |= __GFP_HIGH; test(cmp_buffer, "%pGg", &gfp); - page_type = ~0; - page_type_test(page_type, "", cmp_buffer); - - page_type = 10; - page_type_test(page_type, "", cmp_buffer); - - page_type = ~PG_buddy; - page_type_test(page_type, "buddy", cmp_buffer); - - page_type = ~(PG_table | PG_buddy); - page_type_test(page_type, "table|buddy", cmp_buffer); - kfree(cmp_buffer); } diff --git a/lib/union_find.c b/lib/union_find.c new file mode 100644 index 000000000000..413b0f8adf7a --- /dev/null +++ b/lib/union_find.c @@ -0,0 +1,49 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <linux/union_find.h> + +/** + * uf_find - Find the root of a node and perform path compression + * @node: the node to find the root of + * + * This function returns the root of the node by following the parent + * pointers. It also performs path compression, making the tree shallower. + * + * Returns the root node of the set containing node. + */ +struct uf_node *uf_find(struct uf_node *node) +{ + struct uf_node *parent; + + while (node->parent != node) { + parent = node->parent; + node->parent = parent->parent; + node = parent; + } + return node; +} + +/** + * uf_union - Merge two sets, using union by rank + * @node1: the first node + * @node2: the second node + * + * This function merges the sets containing node1 and node2, by comparing + * the ranks to keep the tree balanced. + */ +void uf_union(struct uf_node *node1, struct uf_node *node2) +{ + struct uf_node *root1 = uf_find(node1); + struct uf_node *root2 = uf_find(node2); + + if (root1 == root2) + return; + + if (root1->rank < root2->rank) { + root1->parent = root2; + } else if (root1->rank > root2->rank) { + root2->parent = root1; + } else { + root2->parent = root1; + root1->rank++; + } +} diff --git a/lib/vdso/Makefile b/lib/vdso/Makefile index 9f031eafc465..cedbf15f8087 100644 --- a/lib/vdso/Makefile +++ b/lib/vdso/Makefile @@ -4,6 +4,7 @@ GENERIC_VDSO_MK_PATH := $(abspath $(lastword $(MAKEFILE_LIST))) GENERIC_VDSO_DIR := $(dir $(GENERIC_VDSO_MK_PATH)) c-gettimeofday-$(CONFIG_GENERIC_GETTIMEOFDAY) := $(addprefix $(GENERIC_VDSO_DIR), gettimeofday.c) +c-getrandom-$(CONFIG_VDSO_GETRANDOM) := $(addprefix $(GENERIC_VDSO_DIR), getrandom.c) # This cmd checks that the vdso library does not contain dynamic relocations. # It has to be called after the linking of the vdso library and requires it diff --git a/lib/vdso/getrandom.c b/lib/vdso/getrandom.c index e1db228bc4f0..938ca539aaa6 100644 --- a/lib/vdso/getrandom.c +++ b/lib/vdso/getrandom.c @@ -3,15 +3,19 @@ * Copyright (C) 2022-2024 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ -#include <linux/cache.h> -#include <linux/kernel.h> -#include <linux/time64.h> +#include <linux/array_size.h> +#include <linux/minmax.h> #include <vdso/datapage.h> #include <vdso/getrandom.h> +#include <vdso/unaligned.h> #include <asm/vdso/getrandom.h> -#include <asm/vdso/vsyscall.h> -#include <asm/unaligned.h> #include <uapi/linux/mman.h> +#include <uapi/linux/random.h> + +#undef PAGE_SIZE +#undef PAGE_MASK +#define PAGE_SIZE (1UL << CONFIG_PAGE_SHIFT) +#define PAGE_MASK (~(PAGE_SIZE - 1)) #define MEMCPY_AND_ZERO_SRC(type, dst, src, len) do { \ while (len >= sizeof(type)) { \ @@ -68,16 +72,17 @@ __cvdso_getrandom_data(const struct vdso_rng_data *rng_info, void *buffer, size_ struct vgetrandom_state *state = opaque_state; size_t batch_len, nblocks, orig_len = len; bool in_use, have_retried = false; - unsigned long current_generation; void *orig_buffer = buffer; + u64 current_generation; u32 counter[2] = { 0 }; if (unlikely(opaque_len == ~0UL && !buffer && !len && !flags)) { - *(struct vgetrandom_opaque_params *)opaque_state = (struct vgetrandom_opaque_params) { - .size_of_opaque_state = sizeof(*state), - .mmap_prot = PROT_READ | PROT_WRITE, - .mmap_flags = MAP_DROPPABLE | MAP_ANONYMOUS - }; + struct vgetrandom_opaque_params *params = opaque_state; + params->size_of_opaque_state = sizeof(*state); + params->mmap_prot = PROT_READ | PROT_WRITE; + params->mmap_flags = MAP_DROPPABLE | MAP_ANONYMOUS; + for (size_t i = 0; i < ARRAY_SIZE(params->reserved); ++i) + params->reserved[i] = 0; return 0; } diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 2d71b1115916..09f022ba1c05 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -2054,25 +2054,6 @@ char *format_page_flags(char *buf, char *end, unsigned long flags) return buf; } -static -char *format_page_type(char *buf, char *end, unsigned int page_type) -{ - buf = number(buf, end, page_type, default_flag_spec); - - if (buf < end) - *buf = '('; - buf++; - - if (page_type_has_type(page_type)) - buf = format_flags(buf, end, ~page_type, pagetype_names); - - if (buf < end) - *buf = ')'; - buf++; - - return buf; -} - static noinline_for_stack char *flags_string(char *buf, char *end, void *flags_ptr, struct printf_spec spec, const char *fmt) @@ -2086,8 +2067,6 @@ char *flags_string(char *buf, char *end, void *flags_ptr, switch (fmt[1]) { case 'p': return format_page_flags(buf, end, *(unsigned long *)flags_ptr); - case 't': - return format_page_type(buf, end, *(unsigned int *)flags_ptr); case 'v': flags = *(unsigned long *)flags_ptr; names = vmaflag_names; diff --git a/lib/zstd/compress/zstd_compress.c b/lib/zstd/compress/zstd_compress.c index f620cafca633..16bb995bc6c4 100644 --- a/lib/zstd/compress/zstd_compress.c +++ b/lib/zstd/compress/zstd_compress.c @@ -4810,6 +4810,8 @@ ZSTD_CDict* ZSTD_createCDict_advanced2( dictLoadMethod, cctxParams.cParams, cctxParams.useRowMatchFinder, cctxParams.enableDedicatedDictSearch, customMem); + if (!cdict) + return NULL; if (ZSTD_isError( ZSTD_initCDict_internal(cdict, dict, dictSize, diff --git a/lib/zstd/zstd_compress_module.c b/lib/zstd/zstd_compress_module.c index 04e1b5c01d9b..bd8784449b31 100644 --- a/lib/zstd/zstd_compress_module.c +++ b/lib/zstd/zstd_compress_module.c @@ -66,6 +66,12 @@ int zstd_max_clevel(void) } EXPORT_SYMBOL(zstd_max_clevel); +int zstd_default_clevel(void) +{ + return ZSTD_defaultCLevel(); +} +EXPORT_SYMBOL(zstd_default_clevel); + size_t zstd_compress_bound(size_t src_size) { return ZSTD_compressBound(src_size); @@ -79,6 +85,13 @@ zstd_parameters zstd_get_params(int level, } EXPORT_SYMBOL(zstd_get_params); +zstd_compression_parameters zstd_get_cparams(int level, + unsigned long long estimated_src_size, size_t dict_size) +{ + return ZSTD_getCParams(level, estimated_src_size, dict_size); +} +EXPORT_SYMBOL(zstd_get_cparams); + size_t zstd_cctx_workspace_bound(const zstd_compression_parameters *cparams) { return ZSTD_estimateCCtxSize_usingCParams(*cparams); @@ -93,6 +106,33 @@ zstd_cctx *zstd_init_cctx(void *workspace, size_t workspace_size) } EXPORT_SYMBOL(zstd_init_cctx); +zstd_cctx *zstd_create_cctx_advanced(zstd_custom_mem custom_mem) +{ + return ZSTD_createCCtx_advanced(custom_mem); +} +EXPORT_SYMBOL(zstd_create_cctx_advanced); + +size_t zstd_free_cctx(zstd_cctx *cctx) +{ + return ZSTD_freeCCtx(cctx); +} +EXPORT_SYMBOL(zstd_free_cctx); + +zstd_cdict *zstd_create_cdict_byreference(const void *dict, size_t dict_size, + zstd_compression_parameters cparams, + zstd_custom_mem custom_mem) +{ + return ZSTD_createCDict_advanced(dict, dict_size, ZSTD_dlm_byRef, + ZSTD_dct_auto, cparams, custom_mem); +} +EXPORT_SYMBOL(zstd_create_cdict_byreference); + +size_t zstd_free_cdict(zstd_cdict *cdict) +{ + return ZSTD_freeCDict(cdict); +} +EXPORT_SYMBOL(zstd_free_cdict); + size_t zstd_compress_cctx(zstd_cctx *cctx, void *dst, size_t dst_capacity, const void *src, size_t src_size, const zstd_parameters *parameters) { @@ -101,6 +141,15 @@ size_t zstd_compress_cctx(zstd_cctx *cctx, void *dst, size_t dst_capacity, } EXPORT_SYMBOL(zstd_compress_cctx); +size_t zstd_compress_using_cdict(zstd_cctx *cctx, void *dst, + size_t dst_capacity, const void *src, size_t src_size, + const ZSTD_CDict *cdict) +{ + return ZSTD_compress_usingCDict(cctx, dst, dst_capacity, + src, src_size, cdict); +} +EXPORT_SYMBOL(zstd_compress_using_cdict); + size_t zstd_cstream_workspace_bound(const zstd_compression_parameters *cparams) { return ZSTD_estimateCStreamSize_usingCParams(*cparams); diff --git a/lib/zstd/zstd_decompress_module.c b/lib/zstd/zstd_decompress_module.c index f4ed952ed485..469fc3059be0 100644 --- a/lib/zstd/zstd_decompress_module.c +++ b/lib/zstd/zstd_decompress_module.c @@ -44,6 +44,33 @@ size_t zstd_dctx_workspace_bound(void) } EXPORT_SYMBOL(zstd_dctx_workspace_bound); +zstd_dctx *zstd_create_dctx_advanced(zstd_custom_mem custom_mem) +{ + return ZSTD_createDCtx_advanced(custom_mem); +} +EXPORT_SYMBOL(zstd_create_dctx_advanced); + +size_t zstd_free_dctx(zstd_dctx *dctx) +{ + return ZSTD_freeDCtx(dctx); +} +EXPORT_SYMBOL(zstd_free_dctx); + +zstd_ddict *zstd_create_ddict_byreference(const void *dict, size_t dict_size, + zstd_custom_mem custom_mem) +{ + return ZSTD_createDDict_advanced(dict, dict_size, ZSTD_dlm_byRef, + ZSTD_dct_auto, custom_mem); + +} +EXPORT_SYMBOL(zstd_create_ddict_byreference); + +size_t zstd_free_ddict(zstd_ddict *ddict) +{ + return ZSTD_freeDDict(ddict); +} +EXPORT_SYMBOL(zstd_free_ddict); + zstd_dctx *zstd_init_dctx(void *workspace, size_t workspace_size) { if (workspace == NULL) @@ -59,6 +86,15 @@ size_t zstd_decompress_dctx(zstd_dctx *dctx, void *dst, size_t dst_capacity, } EXPORT_SYMBOL(zstd_decompress_dctx); +size_t zstd_decompress_using_ddict(zstd_dctx *dctx, + void *dst, size_t dst_capacity, const void* src, size_t src_size, + const zstd_ddict* ddict) +{ + return ZSTD_decompress_usingDDict(dctx, dst, dst_capacity, src, + src_size, ddict); +} +EXPORT_SYMBOL(zstd_decompress_using_ddict); + size_t zstd_dstream_workspace_bound(size_t max_window_size) { return ZSTD_estimateDStreamSize(max_window_size); |