summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig7
-rw-r--r--lib/Kconfig.debug13
-rw-r--r--lib/Kconfig.kasan31
-rw-r--r--lib/Kconfig.kcsan5
-rw-r--r--lib/Makefile5
-rw-r--r--lib/bootconfig.c38
-rw-r--r--lib/checksum.c11
-rw-r--r--lib/crypto/chacha20poly1305.c4
-rw-r--r--lib/debugobjects.c55
-rw-r--r--lib/fonts/font_10x18.c9
-rw-r--r--lib/fonts/font_6x10.c9
-rw-r--r--lib/fonts/font_6x11.c9
-rw-r--r--lib/fonts/font_7x14.c9
-rw-r--r--lib/fonts/font_8x16.c9
-rw-r--r--lib/fonts/font_8x8.c9
-rw-r--r--lib/fonts/font_acorn_8x8.c9
-rw-r--r--lib/fonts/font_mini_4x6.c8
-rw-r--r--lib/fonts/font_pearl_8x8.c9
-rw-r--r--lib/fonts/font_sun12x22.c9
-rw-r--r--lib/fonts/font_sun8x16.c7
-rw-r--r--lib/fonts/font_ter16x32.c9
-rw-r--r--lib/iov_iter.c247
-rw-r--r--lib/kunit/test.c13
-rw-r--r--lib/locking-selftest.c445
-rw-r--r--lib/memregion.c1
-rw-r--r--lib/mpi/Makefile6
-rw-r--r--lib/mpi/ec.c1509
-rw-r--r--lib/mpi/mpi-add.c155
-rw-r--r--lib/mpi/mpi-bit.c251
-rw-r--r--lib/mpi/mpi-cmp.c46
-rw-r--r--lib/mpi/mpi-div.c234
-rw-r--r--lib/mpi/mpi-internal.h53
-rw-r--r--lib/mpi/mpi-inv.c143
-rw-r--r--lib/mpi/mpi-mod.c155
-rw-r--r--lib/mpi/mpi-mul.c91
-rw-r--r--lib/mpi/mpicoder.c336
-rw-r--r--lib/mpi/mpih-div.c294
-rw-r--r--lib/mpi/mpih-mul.c25
-rw-r--r--lib/mpi/mpiutil.c204
-rw-r--r--lib/percpu-refcount.c131
-rw-r--r--lib/percpu_counter.c4
-rw-r--r--lib/random32.c2
-rw-r--r--lib/string.c24
-rw-r--r--lib/string_helpers.c23
-rw-r--r--lib/test_free_pages.c42
-rw-r--r--lib/test_hmm.c65
-rw-r--r--lib/test_kasan.c728
-rw-r--r--lib/test_kasan_module.c111
-rw-r--r--lib/test_rhashtable.c2
-rw-r--r--lib/vsprintf.c4
50 files changed, 4883 insertions, 735 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index b4b98a03ff98..b46a9fd122c8 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -635,7 +635,12 @@ config UACCESS_MEMCPY
config ARCH_HAS_UACCESS_FLUSHCACHE
bool
-config ARCH_HAS_UACCESS_MCSAFE
+# arch has a concept of a recoverable synchronous exception due to a
+# memory-read error like x86 machine-check or ARM data-abort, and
+# implements copy_mc_to_{user,kernel} to abort and report
+# 'bytes-transferred' if that exception fires when accessing the source
+# buffer.
+config ARCH_HAS_COPY_MC
bool
# Temporary. Goes away when all archs are cleaned up
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e068c3c7189a..491789a793ae 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -520,8 +520,8 @@ config DEBUG_FS_ALLOW_NONE
endchoice
source "lib/Kconfig.kgdb"
-
source "lib/Kconfig.ubsan"
+source "lib/Kconfig.kcsan"
endmenu
@@ -1620,8 +1620,6 @@ config PROVIDE_OHCI1394_DMA_INIT
source "samples/Kconfig"
-source "lib/Kconfig.kcsan"
-
config ARCH_HAS_DEVMEM_IS_ALLOWED
bool
@@ -2369,6 +2367,15 @@ config TEST_HMM
If unsure, say N.
+config TEST_FREE_PAGES
+ tristate "Test freeing pages"
+ help
+ Test that a memory leak does not occur due to a race between
+ freeing a block of pages and a speculative page reference.
+ Loading this module is safe if your kernel has the bug fixed.
+ If the bug is not fixed, it will leak gigabytes of memory and
+ probably OOM your system.
+
config TEST_FPU
tristate "Test floating point operations in kernel space"
depends on X86 && !KCOV_INSTRUMENT_ALL
diff --git a/lib/Kconfig.kasan b/lib/Kconfig.kasan
index 047b53dbfd58..542a9c18398e 100644
--- a/lib/Kconfig.kasan
+++ b/lib/Kconfig.kasan
@@ -54,9 +54,9 @@ config KASAN_GENERIC
Enables generic KASAN mode.
This mode is supported in both GCC and Clang. With GCC it requires
- version 8.3.0 or later. With Clang it requires version 7.0.0 or
- later, but detection of out-of-bounds accesses for global variables
- is supported only since Clang 11.
+ version 8.3.0 or later. Any supported Clang version is compatible,
+ but detection of out-of-bounds accesses for global variables is
+ supported only since Clang 11.
This mode consumes about 1/8th of available memory at kernel start
and introduces an overhead of ~x1.5 for the rest of the allocations.
@@ -78,8 +78,7 @@ config KASAN_SW_TAGS
Enables software tag-based KASAN mode.
This mode requires Top Byte Ignore support by the CPU and therefore
- is only supported for arm64. This mode requires Clang version 7.0.0
- or later.
+ is only supported for arm64. This mode requires Clang.
This mode consumes about 1/16th of available memory at kernel start
and introduces an overhead of ~20% for the rest of the allocations.
@@ -167,12 +166,24 @@ config KASAN_VMALLOC
for KASAN to detect more sorts of errors (and to support vmapped
stacks), but at the cost of higher memory usage.
-config TEST_KASAN
- tristate "Module for testing KASAN for bug detection"
- depends on m
+config KASAN_KUNIT_TEST
+ tristate "KUnit-compatible tests of KASAN bug detection capabilities" if !KUNIT_ALL_TESTS
+ depends on KASAN && KUNIT
+ default KUNIT_ALL_TESTS
help
- This is a test module doing various nasty things like
- out of bounds accesses, use after free. It is useful for testing
+ This is a KUnit test suite doing various nasty things like
+ out of bounds and use after free accesses. It is useful for testing
kernel debugging features like KASAN.
+ For more information on KUnit and unit tests in general, please refer
+ to the KUnit documentation in Documentation/dev-tools/kunit
+
+config TEST_KASAN_MODULE
+ tristate "KUnit-incompatible tests of KASAN bug detection capabilities"
+ depends on m && KASAN
+ help
+ This is a part of the KASAN test suite that is incompatible with
+ KUnit. Currently includes tests that do bad copy_from/to_user
+ accesses.
+
endif # KASAN
diff --git a/lib/Kconfig.kcsan b/lib/Kconfig.kcsan
index 3d282d51849b..f271ff5fbb5a 100644
--- a/lib/Kconfig.kcsan
+++ b/lib/Kconfig.kcsan
@@ -40,6 +40,11 @@ menuconfig KCSAN
if KCSAN
+# Compiler capabilities that should not fail the test if they are unavailable.
+config CC_HAS_TSAN_COMPOUND_READ_BEFORE_WRITE
+ def_bool (CC_IS_CLANG && $(cc-option,-fsanitize=thread -mllvm -tsan-compound-read-before-write=1)) || \
+ (CC_IS_GCC && $(cc-option,-fsanitize=thread --param tsan-compound-read-before-write=1))
+
config KCSAN_VERBOSE
bool "Show verbose reports with more information about system state"
depends on PROVE_LOCKING
diff --git a/lib/Makefile b/lib/Makefile
index a4a4c6864f51..49a2a9e36224 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -65,9 +65,11 @@ CFLAGS_test_bitops.o += -Werror
obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o
obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
obj-$(CONFIG_TEST_IDA) += test_ida.o
-obj-$(CONFIG_TEST_KASAN) += test_kasan.o
+obj-$(CONFIG_KASAN_KUNIT_TEST) += test_kasan.o
CFLAGS_test_kasan.o += -fno-builtin
CFLAGS_test_kasan.o += $(call cc-disable-warning, vla)
+obj-$(CONFIG_TEST_KASAN_MODULE) += test_kasan_module.o
+CFLAGS_test_kasan_module.o += -fno-builtin
obj-$(CONFIG_TEST_UBSAN) += test_ubsan.o
CFLAGS_test_ubsan.o += $(call cc-disable-warning, vla)
UBSAN_SANITIZE_test_ubsan.o := y
@@ -99,6 +101,7 @@ obj-$(CONFIG_TEST_BLACKHOLE_DEV) += test_blackhole_dev.o
obj-$(CONFIG_TEST_MEMINIT) += test_meminit.o
obj-$(CONFIG_TEST_LOCKUP) += test_lockup.o
obj-$(CONFIG_TEST_HMM) += test_hmm.o
+obj-$(CONFIG_TEST_FREE_PAGES) += test_free_pages.o
#
# CFLAGS for compiling floating point code inside the kernel. x86/Makefile turns
diff --git a/lib/bootconfig.c b/lib/bootconfig.c
index 2c905a91d4eb..649ed44f199c 100644
--- a/lib/bootconfig.c
+++ b/lib/bootconfig.c
@@ -31,6 +31,8 @@ static size_t xbc_data_size __initdata;
static struct xbc_node *last_parent __initdata;
static const char *xbc_err_msg __initdata;
static int xbc_err_pos __initdata;
+static int open_brace[XBC_DEPTH_MAX] __initdata;
+static int brace_index __initdata;
static int __init xbc_parse_error(const char *msg, const char *p)
{
@@ -431,27 +433,27 @@ static char *skip_spaces_until_newline(char *p)
return p;
}
-static int __init __xbc_open_brace(void)
+static int __init __xbc_open_brace(char *p)
{
- /* Mark the last key as open brace */
- last_parent->next = XBC_NODE_MAX;
+ /* Push the last key as open brace */
+ open_brace[brace_index++] = xbc_node_index(last_parent);
+ if (brace_index >= XBC_DEPTH_MAX)
+ return xbc_parse_error("Exceed max depth of braces", p);
return 0;
}
static int __init __xbc_close_brace(char *p)
{
- struct xbc_node *node;
-
- if (!last_parent || last_parent->next != XBC_NODE_MAX)
+ brace_index--;
+ if (!last_parent || brace_index < 0 ||
+ (open_brace[brace_index] != xbc_node_index(last_parent)))
return xbc_parse_error("Unexpected closing brace", p);
- node = last_parent;
- node->next = 0;
- do {
- node = xbc_node_get_parent(node);
- } while (node && node->next != XBC_NODE_MAX);
- last_parent = node;
+ if (brace_index == 0)
+ last_parent = NULL;
+ else
+ last_parent = &xbc_nodes[open_brace[brace_index - 1]];
return 0;
}
@@ -492,8 +494,8 @@ static int __init __xbc_parse_value(char **__v, char **__n)
break;
}
if (strchr(",;\n#}", c)) {
- v = strim(v);
*p++ = '\0';
+ v = strim(v);
break;
}
}
@@ -661,7 +663,7 @@ static int __init xbc_open_brace(char **k, char *n)
return ret;
*k = n;
- return __xbc_open_brace();
+ return __xbc_open_brace(n - 1);
}
static int __init xbc_close_brace(char **k, char *n)
@@ -681,6 +683,13 @@ static int __init xbc_verify_tree(void)
int i, depth, len, wlen;
struct xbc_node *n, *m;
+ /* Brace closing */
+ if (brace_index) {
+ n = &xbc_nodes[open_brace[brace_index]];
+ return xbc_parse_error("Brace is not closed",
+ xbc_node_get_data(n));
+ }
+
/* Empty tree */
if (xbc_node_num == 0) {
xbc_parse_error("Empty config", xbc_data);
@@ -745,6 +754,7 @@ void __init xbc_destroy_all(void)
xbc_node_num = 0;
memblock_free(__pa(xbc_nodes), sizeof(struct xbc_node) * XBC_NODE_MAX);
xbc_nodes = NULL;
+ brace_index = 0;
}
/**
diff --git a/lib/checksum.c b/lib/checksum.c
index c7861e84c526..6860d6b05a17 100644
--- a/lib/checksum.c
+++ b/lib/checksum.c
@@ -145,17 +145,6 @@ __sum16 ip_compute_csum(const void *buff, int len)
}
EXPORT_SYMBOL(ip_compute_csum);
-/*
- * copy from ds while checksumming, otherwise like csum_partial
- */
-__wsum
-csum_partial_copy_nocheck(const void *src, void *dst, int len, __wsum sum)
-{
- memcpy(dst, src, len);
- return csum_partial(dst, len, sum);
-}
-EXPORT_SYMBOL(csum_partial_copy_nocheck);
-
#ifndef csum_tcpudp_nofold
static inline u32 from64to32(u64 x)
{
diff --git a/lib/crypto/chacha20poly1305.c b/lib/crypto/chacha20poly1305.c
index 431e04280332..5850f3b87359 100644
--- a/lib/crypto/chacha20poly1305.c
+++ b/lib/crypto/chacha20poly1305.c
@@ -251,9 +251,7 @@ bool chacha20poly1305_crypt_sg_inplace(struct scatterlist *src,
poly1305_update(&poly1305_state, pad0, 0x10 - (ad_len & 0xf));
}
- flags = SG_MITER_TO_SG;
- if (!preemptible())
- flags |= SG_MITER_ATOMIC;
+ flags = SG_MITER_TO_SG | SG_MITER_ATOMIC;
sg_miter_start(&miter, src, sg_nents(src), flags);
diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index fe4557955d97..9e14ae02306b 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -19,6 +19,7 @@
#include <linux/slab.h>
#include <linux/hash.h>
#include <linux/kmemleak.h>
+#include <linux/cpu.h>
#define ODEBUG_HASH_BITS 14
#define ODEBUG_HASH_SIZE (1 << ODEBUG_HASH_BITS)
@@ -90,7 +91,7 @@ static int debug_objects_pool_size __read_mostly
= ODEBUG_POOL_SIZE;
static int debug_objects_pool_min_level __read_mostly
= ODEBUG_POOL_MIN_LEVEL;
-static struct debug_obj_descr *descr_test __read_mostly;
+static const struct debug_obj_descr *descr_test __read_mostly;
static struct kmem_cache *obj_cache __read_mostly;
/*
@@ -223,7 +224,7 @@ static struct debug_obj *__alloc_object(struct hlist_head *list)
* Must be called with interrupts disabled.
*/
static struct debug_obj *
-alloc_object(void *addr, struct debug_bucket *b, struct debug_obj_descr *descr)
+alloc_object(void *addr, struct debug_bucket *b, const struct debug_obj_descr *descr)
{
struct debug_percpu_free *percpu_pool = this_cpu_ptr(&percpu_obj_pool);
struct debug_obj *obj;
@@ -433,6 +434,25 @@ static void free_object(struct debug_obj *obj)
}
}
+#ifdef CONFIG_HOTPLUG_CPU
+static int object_cpu_offline(unsigned int cpu)
+{
+ struct debug_percpu_free *percpu_pool;
+ struct hlist_node *tmp;
+ struct debug_obj *obj;
+
+ /* Remote access is safe as the CPU is dead already */
+ percpu_pool = per_cpu_ptr(&percpu_obj_pool, cpu);
+ hlist_for_each_entry_safe(obj, tmp, &percpu_pool->free_objs, node) {
+ hlist_del(&obj->node);
+ kmem_cache_free(obj_cache, obj);
+ }
+ percpu_pool->obj_free = 0;
+
+ return 0;
+}
+#endif
+
/*
* We run out of memory. That means we probably have tons of objects
* allocated.
@@ -475,7 +495,7 @@ static struct debug_bucket *get_bucket(unsigned long addr)
static void debug_print_object(struct debug_obj *obj, char *msg)
{
- struct debug_obj_descr *descr = obj->descr;
+ const struct debug_obj_descr *descr = obj->descr;
static int limit;
if (limit < 5 && descr != descr_test) {
@@ -529,7 +549,7 @@ static void debug_object_is_on_stack(void *addr, int onstack)
}
static void
-__debug_object_init(void *addr, struct debug_obj_descr *descr, int onstack)
+__debug_object_init(void *addr, const struct debug_obj_descr *descr, int onstack)
{
enum debug_obj_state state;
bool check_stack = false;
@@ -587,7 +607,7 @@ __debug_object_init(void *addr, struct debug_obj_descr *descr, int onstack)
* @addr: address of the object
* @descr: pointer to an object specific debug description structure
*/
-void debug_object_init(void *addr, struct debug_obj_descr *descr)
+void debug_object_init(void *addr, const struct debug_obj_descr *descr)
{
if (!debug_objects_enabled)
return;
@@ -602,7 +622,7 @@ EXPORT_SYMBOL_GPL(debug_object_init);
* @addr: address of the object
* @descr: pointer to an object specific debug description structure
*/
-void debug_object_init_on_stack(void *addr, struct debug_obj_descr *descr)
+void debug_object_init_on_stack(void *addr, const struct debug_obj_descr *descr)
{
if (!debug_objects_enabled)
return;
@@ -617,7 +637,7 @@ EXPORT_SYMBOL_GPL(debug_object_init_on_stack);
* @descr: pointer to an object specific debug description structure
* Returns 0 for success, -EINVAL for check failed.
*/
-int debug_object_activate(void *addr, struct debug_obj_descr *descr)
+int debug_object_activate(void *addr, const struct debug_obj_descr *descr)
{
enum debug_obj_state state;
struct debug_bucket *db;
@@ -695,7 +715,7 @@ EXPORT_SYMBOL_GPL(debug_object_activate);
* @addr: address of the object
* @descr: pointer to an object specific debug description structure
*/
-void debug_object_deactivate(void *addr, struct debug_obj_descr *descr)
+void debug_object_deactivate(void *addr, const struct debug_obj_descr *descr)
{
struct debug_bucket *db;
struct debug_obj *obj;
@@ -747,7 +767,7 @@ EXPORT_SYMBOL_GPL(debug_object_deactivate);
* @addr: address of the object
* @descr: pointer to an object specific debug description structure
*/
-void debug_object_destroy(void *addr, struct debug_obj_descr *descr)
+void debug_object_destroy(void *addr, const struct debug_obj_descr *descr)
{
enum debug_obj_state state;
struct debug_bucket *db;
@@ -797,7 +817,7 @@ EXPORT_SYMBOL_GPL(debug_object_destroy);
* @addr: address of the object
* @descr: pointer to an object specific debug description structure
*/
-void debug_object_free(void *addr, struct debug_obj_descr *descr)
+void debug_object_free(void *addr, const struct debug_obj_descr *descr)
{
enum debug_obj_state state;
struct debug_bucket *db;
@@ -838,7 +858,7 @@ EXPORT_SYMBOL_GPL(debug_object_free);
* @addr: address of the object
* @descr: pointer to an object specific debug description structure
*/
-void debug_object_assert_init(void *addr, struct debug_obj_descr *descr)
+void debug_object_assert_init(void *addr, const struct debug_obj_descr *descr)
{
struct debug_bucket *db;
struct debug_obj *obj;
@@ -886,7 +906,7 @@ EXPORT_SYMBOL_GPL(debug_object_assert_init);
* @next: state to move to if expected state is found
*/
void
-debug_object_active_state(void *addr, struct debug_obj_descr *descr,
+debug_object_active_state(void *addr, const struct debug_obj_descr *descr,
unsigned int expect, unsigned int next)
{
struct debug_bucket *db;
@@ -934,7 +954,7 @@ EXPORT_SYMBOL_GPL(debug_object_active_state);
static void __debug_check_no_obj_freed(const void *address, unsigned long size)
{
unsigned long flags, oaddr, saddr, eaddr, paddr, chunks;
- struct debug_obj_descr *descr;
+ const struct debug_obj_descr *descr;
enum debug_obj_state state;
struct debug_bucket *db;
struct hlist_node *tmp;
@@ -1052,7 +1072,7 @@ struct self_test {
unsigned long dummy2[3];
};
-static __initdata struct debug_obj_descr descr_type_test;
+static __initconst const struct debug_obj_descr descr_type_test;
static bool __init is_static_object(void *addr)
{
@@ -1177,7 +1197,7 @@ out:
return res;
}
-static __initdata struct debug_obj_descr descr_type_test = {
+static __initconst const struct debug_obj_descr descr_type_test = {
.name = "selftest",
.is_static_object = is_static_object,
.fixup_init = fixup_init,
@@ -1367,6 +1387,11 @@ void __init debug_objects_mem_init(void)
} else
debug_objects_selftest();
+#ifdef CONFIG_HOTPLUG_CPU
+ cpuhp_setup_state_nocalls(CPUHP_DEBUG_OBJ_DEAD, "object:offline", NULL,
+ object_cpu_offline);
+#endif
+
/*
* Increase the thresholds for allocating and freeing objects
* according to the number of possible CPUs available in the system.
diff --git a/lib/fonts/font_10x18.c b/lib/fonts/font_10x18.c
index 532f0ff89a96..0e2deac97da0 100644
--- a/lib/fonts/font_10x18.c
+++ b/lib/fonts/font_10x18.c
@@ -8,8 +8,8 @@
#define FONTDATAMAX 9216
-static const unsigned char fontdata_10x18[FONTDATAMAX] = {
-
+static struct font_data fontdata_10x18 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, 0x00, /* 0000000000 */
0x00, 0x00, /* 0000000000 */
@@ -5129,8 +5129,7 @@ static const unsigned char fontdata_10x18[FONTDATAMAX] = {
0x00, 0x00, /* 0000000000 */
0x00, 0x00, /* 0000000000 */
0x00, 0x00, /* 0000000000 */
-
-};
+} };
const struct font_desc font_10x18 = {
@@ -5138,7 +5137,7 @@ const struct font_desc font_10x18 = {
.name = "10x18",
.width = 10,
.height = 18,
- .data = fontdata_10x18,
+ .data = fontdata_10x18.data,
#ifdef __sparc__
.pref = 5,
#else
diff --git a/lib/fonts/font_6x10.c b/lib/fonts/font_6x10.c
index 09b2cc03435b..87da8acd07db 100644
--- a/lib/fonts/font_6x10.c
+++ b/lib/fonts/font_6x10.c
@@ -1,8 +1,10 @@
// SPDX-License-Identifier: GPL-2.0
#include <linux/font.h>
-static const unsigned char fontdata_6x10[] = {
+#define FONTDATAMAX 2560
+static struct font_data fontdata_6x10 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, /* 00000000 */
0x00, /* 00000000 */
@@ -3074,14 +3076,13 @@ static const unsigned char fontdata_6x10[] = {
0x00, /* 00000000 */
0x00, /* 00000000 */
0x00, /* 00000000 */
-
-};
+} };
const struct font_desc font_6x10 = {
.idx = FONT6x10_IDX,
.name = "6x10",
.width = 6,
.height = 10,
- .data = fontdata_6x10,
+ .data = fontdata_6x10.data,
.pref = 0,
};
diff --git a/lib/fonts/font_6x11.c b/lib/fonts/font_6x11.c
index d7136c33f1f0..5e975dfa10a5 100644
--- a/lib/fonts/font_6x11.c
+++ b/lib/fonts/font_6x11.c
@@ -9,8 +9,8 @@
#define FONTDATAMAX (11*256)
-static const unsigned char fontdata_6x11[FONTDATAMAX] = {
-
+static struct font_data fontdata_6x11 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, /* 00000000 */
0x00, /* 00000000 */
@@ -3338,8 +3338,7 @@ static const unsigned char fontdata_6x11[FONTDATAMAX] = {
0x00, /* 00000000 */
0x00, /* 00000000 */
0x00, /* 00000000 */
-
-};
+} };
const struct font_desc font_vga_6x11 = {
@@ -3347,7 +3346,7 @@ const struct font_desc font_vga_6x11 = {
.name = "ProFont6x11",
.width = 6,
.height = 11,
- .data = fontdata_6x11,
+ .data = fontdata_6x11.data,
/* Try avoiding this font if possible unless on MAC */
.pref = -2000,
};
diff --git a/lib/fonts/font_7x14.c b/lib/fonts/font_7x14.c
index 89752d0b23e8..86d298f38505 100644
--- a/lib/fonts/font_7x14.c
+++ b/lib/fonts/font_7x14.c
@@ -8,8 +8,8 @@
#define FONTDATAMAX 3584
-static const unsigned char fontdata_7x14[FONTDATAMAX] = {
-
+static struct font_data fontdata_7x14 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, /* 0000000 */
0x00, /* 0000000 */
@@ -4105,8 +4105,7 @@ static const unsigned char fontdata_7x14[FONTDATAMAX] = {
0x00, /* 0000000 */
0x00, /* 0000000 */
0x00, /* 0000000 */
-
-};
+} };
const struct font_desc font_7x14 = {
@@ -4114,6 +4113,6 @@ const struct font_desc font_7x14 = {
.name = "7x14",
.width = 7,
.height = 14,
- .data = fontdata_7x14,
+ .data = fontdata_7x14.data,
.pref = 0,
};
diff --git a/lib/fonts/font_8x16.c b/lib/fonts/font_8x16.c
index b7ab1f5fbdb8..37cedd36ca5e 100644
--- a/lib/fonts/font_8x16.c
+++ b/lib/fonts/font_8x16.c
@@ -10,8 +10,8 @@
#define FONTDATAMAX 4096
-static const unsigned char fontdata_8x16[FONTDATAMAX] = {
-
+static struct font_data fontdata_8x16 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, /* 00000000 */
0x00, /* 00000000 */
@@ -4619,8 +4619,7 @@ static const unsigned char fontdata_8x16[FONTDATAMAX] = {
0x00, /* 00000000 */
0x00, /* 00000000 */
0x00, /* 00000000 */
-
-};
+} };
const struct font_desc font_vga_8x16 = {
@@ -4628,7 +4627,7 @@ const struct font_desc font_vga_8x16 = {
.name = "VGA8x16",
.width = 8,
.height = 16,
- .data = fontdata_8x16,
+ .data = fontdata_8x16.data,
.pref = 0,
};
EXPORT_SYMBOL(font_vga_8x16);
diff --git a/lib/fonts/font_8x8.c b/lib/fonts/font_8x8.c
index 2328ebc8bab5..8ab695538395 100644
--- a/lib/fonts/font_8x8.c
+++ b/lib/fonts/font_8x8.c
@@ -9,8 +9,8 @@
#define FONTDATAMAX 2048
-static const unsigned char fontdata_8x8[FONTDATAMAX] = {
-
+static struct font_data fontdata_8x8 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, /* 00000000 */
0x00, /* 00000000 */
@@ -2570,8 +2570,7 @@ static const unsigned char fontdata_8x8[FONTDATAMAX] = {
0x00, /* 00000000 */
0x00, /* 00000000 */
0x00, /* 00000000 */
-
-};
+} };
const struct font_desc font_vga_8x8 = {
@@ -2579,6 +2578,6 @@ const struct font_desc font_vga_8x8 = {
.name = "VGA8x8",
.width = 8,
.height = 8,
- .data = fontdata_8x8,
+ .data = fontdata_8x8.data,
.pref = 0,
};
diff --git a/lib/fonts/font_acorn_8x8.c b/lib/fonts/font_acorn_8x8.c
index 0ff0e85d4481..069b3e80c434 100644
--- a/lib/fonts/font_acorn_8x8.c
+++ b/lib/fonts/font_acorn_8x8.c
@@ -3,7 +3,10 @@
#include <linux/font.h>
-static const unsigned char acorndata_8x8[] = {
+#define FONTDATAMAX 2048
+
+static struct font_data acorndata_8x8 = {
+{ 0, 0, FONTDATAMAX, 0 }, {
/* 00 */ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* ^@ */
/* 01 */ 0x7e, 0x81, 0xa5, 0x81, 0xbd, 0x99, 0x81, 0x7e, /* ^A */
/* 02 */ 0x7e, 0xff, 0xbd, 0xff, 0xc3, 0xe7, 0xff, 0x7e, /* ^B */
@@ -260,14 +263,14 @@ static const unsigned char acorndata_8x8[] = {
/* FD */ 0x38, 0x04, 0x18, 0x20, 0x3c, 0x00, 0x00, 0x00,
/* FE */ 0x00, 0x00, 0x3c, 0x3c, 0x3c, 0x3c, 0x00, 0x00,
/* FF */ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
-};
+} };
const struct font_desc font_acorn_8x8 = {
.idx = ACORN8x8_IDX,
.name = "Acorn8x8",
.width = 8,
.height = 8,
- .data = acorndata_8x8,
+ .data = acorndata_8x8.data,
#ifdef CONFIG_ARCH_ACORN
.pref = 20,
#else
diff --git a/lib/fonts/font_mini_4x6.c b/lib/fonts/font_mini_4x6.c
index 838caa1cfef7..1449876c6a27 100644
--- a/lib/fonts/font_mini_4x6.c
+++ b/lib/fonts/font_mini_4x6.c
@@ -43,8 +43,8 @@ __END__;
#define FONTDATAMAX 1536
-static const unsigned char fontdata_mini_4x6[FONTDATAMAX] = {
-
+static struct font_data fontdata_mini_4x6 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/*{*/
/* Char 0: ' ' */
0xee, /*= [*** ] */
@@ -2145,14 +2145,14 @@ static const unsigned char fontdata_mini_4x6[FONTDATAMAX] = {
0xee, /*= [*** ] */
0x00, /*= [ ] */
/*}*/
-};
+} };
const struct font_desc font_mini_4x6 = {
.idx = MINI4x6_IDX,
.name = "MINI4x6",
.width = 4,
.height = 6,
- .data = fontdata_mini_4x6,
+ .data = fontdata_mini_4x6.data,
.pref = 3,
};
diff --git a/lib/fonts/font_pearl_8x8.c b/lib/fonts/font_pearl_8x8.c
index b15d3c342c5b..32d65551e7ed 100644
--- a/lib/fonts/font_pearl_8x8.c
+++ b/lib/fonts/font_pearl_8x8.c
@@ -14,8 +14,8 @@
#define FONTDATAMAX 2048
-static const unsigned char fontdata_pearl8x8[FONTDATAMAX] = {
-
+static struct font_data fontdata_pearl8x8 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, /* 00000000 */
0x00, /* 00000000 */
@@ -2575,14 +2575,13 @@ static const unsigned char fontdata_pearl8x8[FONTDATAMAX] = {
0x00, /* 00000000 */
0x00, /* 00000000 */
0x00, /* 00000000 */
-
-};
+} };
const struct font_desc font_pearl_8x8 = {
.idx = PEARL8x8_IDX,
.name = "PEARL8x8",
.width = 8,
.height = 8,
- .data = fontdata_pearl8x8,
+ .data = fontdata_pearl8x8.data,
.pref = 2,
};
diff --git a/lib/fonts/font_sun12x22.c b/lib/fonts/font_sun12x22.c
index 955d6eee3959..641a6b4dca42 100644
--- a/lib/fonts/font_sun12x22.c
+++ b/lib/fonts/font_sun12x22.c
@@ -3,8 +3,8 @@
#define FONTDATAMAX 11264
-static const unsigned char fontdata_sun12x22[FONTDATAMAX] = {
-
+static struct font_data fontdata_sun12x22 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
/* 0 0x00 '^@' */
0x00, 0x00, /* 000000000000 */
0x00, 0x00, /* 000000000000 */
@@ -6148,8 +6148,7 @@ static const unsigned char fontdata_sun12x22[FONTDATAMAX] = {
0x00, 0x00, /* 000000000000 */
0x00, 0x00, /* 000000000000 */
0x00, 0x00, /* 000000000000 */
-
-};
+} };
const struct font_desc font_sun_12x22 = {
@@ -6157,7 +6156,7 @@ const struct font_desc font_sun_12x22 = {
.name = "SUN12x22",
.width = 12,
.height = 22,
- .data = fontdata_sun12x22,
+ .data = fontdata_sun12x22.data,
#ifdef __sparc__
.pref = 5,
#else
diff --git a/lib/fonts/font_sun8x16.c b/lib/fonts/font_sun8x16.c
index 03d71e53954a..193fe6d988e0 100644
--- a/lib/fonts/font_sun8x16.c
+++ b/lib/fonts/font_sun8x16.c
@@ -3,7 +3,8 @@
#define FONTDATAMAX 4096
-static const unsigned char fontdata_sun8x16[FONTDATAMAX] = {
+static struct font_data fontdata_sun8x16 = {
+{ 0, 0, FONTDATAMAX, 0 }, {
/* */ 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
/* */ 0x00,0x00,0x7e,0x81,0xa5,0x81,0x81,0xbd,0x99,0x81,0x81,0x7e,0x00,0x00,0x00,0x00,
/* */ 0x00,0x00,0x7e,0xff,0xdb,0xff,0xff,0xc3,0xe7,0xff,0xff,0x7e,0x00,0x00,0x00,0x00,
@@ -260,14 +261,14 @@ static const unsigned char fontdata_sun8x16[FONTDATAMAX] = {
/* */ 0x00,0x70,0xd8,0x30,0x60,0xc8,0xf8,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
/* */ 0x00,0x00,0x00,0x00,0x7c,0x7c,0x7c,0x7c,0x7c,0x7c,0x7c,0x00,0x00,0x00,0x00,0x00,
/* */ 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
-};
+} };
const struct font_desc font_sun_8x16 = {
.idx = SUN8x16_IDX,
.name = "SUN8x16",
.width = 8,
.height = 16,
- .data = fontdata_sun8x16,
+ .data = fontdata_sun8x16.data,
#ifdef __sparc__
.pref = 10,
#else
diff --git a/lib/fonts/font_ter16x32.c b/lib/fonts/font_ter16x32.c
index 3f0cf1ccdf3a..91b9c283bd9c 100644
--- a/lib/fonts/font_ter16x32.c
+++ b/lib/fonts/font_ter16x32.c
@@ -4,8 +4,8 @@
#define FONTDATAMAX 16384
-static const unsigned char fontdata_ter16x32[FONTDATAMAX] = {
-
+static struct font_data fontdata_ter16x32 = {
+ { 0, 0, FONTDATAMAX, 0 }, {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x7f, 0xfc, 0x7f, 0xfc,
0x70, 0x1c, 0x70, 0x1c, 0x70, 0x1c, 0x70, 0x1c,
@@ -2054,8 +2054,7 @@ static const unsigned char fontdata_ter16x32[FONTDATAMAX] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* 255 */
-
-};
+} };
const struct font_desc font_ter_16x32 = {
@@ -2063,7 +2062,7 @@ const struct font_desc font_ter_16x32 = {
.name = "TER16x32",
.width = 16,
.height = 32,
- .data = fontdata_ter16x32,
+ .data = fontdata_ter16x32.data,
#ifdef __sparc__
.pref = 5,
#else
diff --git a/lib/iov_iter.c b/lib/iov_iter.c
index 5e40786c8f12..14cae2584db4 100644
--- a/lib/iov_iter.c
+++ b/lib/iov_iter.c
@@ -7,6 +7,7 @@
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/splice.h>
+#include <linux/compat.h>
#include <net/checksum.h>
#include <linux/scatterlist.h>
#include <linux/instrumented.h>
@@ -581,7 +582,7 @@ static size_t copy_pipe_to_iter(const void *addr, size_t bytes,
static __wsum csum_and_memcpy(void *to, const void *from, size_t len,
__wsum sum, size_t off)
{
- __wsum next = csum_partial_copy_nocheck(from, to, len, 0);
+ __wsum next = csum_partial_copy_nocheck(from, to, len);
return csum_block_add(sum, next, off);
}
@@ -637,30 +638,30 @@ size_t _copy_to_iter(const void *addr, size_t bytes, struct iov_iter *i)
}
EXPORT_SYMBOL(_copy_to_iter);
-#ifdef CONFIG_ARCH_HAS_UACCESS_MCSAFE
-static int copyout_mcsafe(void __user *to, const void *from, size_t n)
+#ifdef CONFIG_ARCH_HAS_COPY_MC
+static int copyout_mc(void __user *to, const void *from, size_t n)
{
if (access_ok(to, n)) {
instrument_copy_to_user(to, from, n);
- n = copy_to_user_mcsafe((__force void *) to, from, n);
+ n = copy_mc_to_user((__force void *) to, from, n);
}
return n;
}
-static unsigned long memcpy_mcsafe_to_page(struct page *page, size_t offset,
+static unsigned long copy_mc_to_page(struct page *page, size_t offset,
const char *from, size_t len)
{
unsigned long ret;
char *to;
to = kmap_atomic(page);
- ret = memcpy_mcsafe(to + offset, from, len);
+ ret = copy_mc_to_kernel(to + offset, from, len);
kunmap_atomic(to);
return ret;
}
-static size_t copy_pipe_to_iter_mcsafe(const void *addr, size_t bytes,
+static size_t copy_mc_pipe_to_iter(const void *addr, size_t bytes,
struct iov_iter *i)
{
struct pipe_inode_info *pipe = i->pipe;
@@ -678,7 +679,7 @@ static size_t copy_pipe_to_iter_mcsafe(const void *addr, size_t bytes,
size_t chunk = min_t(size_t, n, PAGE_SIZE - off);
unsigned long rem;
- rem = memcpy_mcsafe_to_page(pipe->bufs[i_head & p_mask].page,
+ rem = copy_mc_to_page(pipe->bufs[i_head & p_mask].page,
off, addr, chunk);
i->head = i_head;
i->iov_offset = off + chunk - rem;
@@ -695,18 +696,17 @@ static size_t copy_pipe_to_iter_mcsafe(const void *addr, size_t bytes,
}
/**
- * _copy_to_iter_mcsafe - copy to user with source-read error exception handling
+ * _copy_mc_to_iter - copy to iter with source memory error exception handling
* @addr: source kernel address
* @bytes: total transfer length
* @iter: destination iterator
*
- * The pmem driver arranges for filesystem-dax to use this facility via
- * dax_copy_to_iter() for protecting read/write to persistent memory.
- * Unless / until an architecture can guarantee identical performance
- * between _copy_to_iter_mcsafe() and _copy_to_iter() it would be a
- * performance regression to switch more users to the mcsafe version.
+ * The pmem driver deploys this for the dax operation
+ * (dax_copy_to_iter()) for dax reads (bypass page-cache and the
+ * block-layer). Upon #MC read(2) aborts and returns EIO or the bytes
+ * successfully copied.
*
- * Otherwise, the main differences between this and typical _copy_to_iter().
+ * The main differences between this and typical _copy_to_iter().
*
* * Typical tail/residue handling after a fault retries the copy
* byte-by-byte until the fault happens again. Re-triggering machine
@@ -717,23 +717,22 @@ static size_t copy_pipe_to_iter_mcsafe(const void *addr, size_t bytes,
* * ITER_KVEC, ITER_PIPE, and ITER_BVEC can return short copies.
* Compare to copy_to_iter() where only ITER_IOVEC attempts might return
* a short copy.
- *
- * See MCSAFE_TEST for self-test.
*/
-size_t _copy_to_iter_mcsafe(const void *addr, size_t bytes, struct iov_iter *i)
+size_t _copy_mc_to_iter(const void *addr, size_t bytes, struct iov_iter *i)
{
const char *from = addr;
unsigned long rem, curr_addr, s_addr = (unsigned long) addr;
if (unlikely(iov_iter_is_pipe(i)))
- return copy_pipe_to_iter_mcsafe(addr, bytes, i);
+ return copy_mc_pipe_to_iter(addr, bytes, i);
if (iter_is_iovec(i))
might_fault();
iterate_and_advance(i, bytes, v,
- copyout_mcsafe(v.iov_base, (from += v.iov_len) - v.iov_len, v.iov_len),
+ copyout_mc(v.iov_base, (from += v.iov_len) - v.iov_len,
+ v.iov_len),
({
- rem = memcpy_mcsafe_to_page(v.bv_page, v.bv_offset,
- (from += v.bv_len) - v.bv_len, v.bv_len);
+ rem = copy_mc_to_page(v.bv_page, v.bv_offset,
+ (from += v.bv_len) - v.bv_len, v.bv_len);
if (rem) {
curr_addr = (unsigned long) from;
bytes = curr_addr - s_addr - rem;
@@ -741,8 +740,8 @@ size_t _copy_to_iter_mcsafe(const void *addr, size_t bytes, struct iov_iter *i)
}
}),
({
- rem = memcpy_mcsafe(v.iov_base, (from += v.iov_len) - v.iov_len,
- v.iov_len);
+ rem = copy_mc_to_kernel(v.iov_base, (from += v.iov_len)
+ - v.iov_len, v.iov_len);
if (rem) {
curr_addr = (unsigned long) from;
bytes = curr_addr - s_addr - rem;
@@ -753,8 +752,8 @@ size_t _copy_to_iter_mcsafe(const void *addr, size_t bytes, struct iov_iter *i)
return bytes;
}
-EXPORT_SYMBOL_GPL(_copy_to_iter_mcsafe);
-#endif /* CONFIG_ARCH_HAS_UACCESS_MCSAFE */
+EXPORT_SYMBOL_GPL(_copy_mc_to_iter);
+#endif /* CONFIG_ARCH_HAS_COPY_MC */
size_t _copy_from_iter(void *addr, size_t bytes, struct iov_iter *i)
{
@@ -1449,15 +1448,14 @@ size_t csum_and_copy_from_iter(void *addr, size_t bytes, __wsum *csum,
return 0;
}
iterate_and_advance(i, bytes, v, ({
- int err = 0;
next = csum_and_copy_from_user(v.iov_base,
(to += v.iov_len) - v.iov_len,
- v.iov_len, 0, &err);
- if (!err) {
+ v.iov_len);
+ if (next) {
sum = csum_block_add(sum, next, off);
off += v.iov_len;
}
- err ? v.iov_len : 0;
+ next ? 0 : v.iov_len;
}), ({
char *p = kmap_atomic(v.bv_page);
sum = csum_and_memcpy((to += v.bv_len) - v.bv_len,
@@ -1491,11 +1489,10 @@ bool csum_and_copy_from_iter_full(void *addr, size_t bytes, __wsum *csum,
if (unlikely(i->count < bytes))
return false;
iterate_all_kinds(i, bytes, v, ({
- int err = 0;
next = csum_and_copy_from_user(v.iov_base,
(to += v.iov_len) - v.iov_len,
- v.iov_len, 0, &err);
- if (err)
+ v.iov_len);
+ if (!next)
return false;
sum = csum_block_add(sum, next, off);
off += v.iov_len;
@@ -1537,15 +1534,14 @@ size_t csum_and_copy_to_iter(const void *addr, size_t bytes, void *csump,
return 0;
}
iterate_and_advance(i, bytes, v, ({
- int err = 0;
next = csum_and_copy_to_user((from += v.iov_len) - v.iov_len,
v.iov_base,
- v.iov_len, 0, &err);
- if (!err) {
+ v.iov_len);
+ if (next) {
sum = csum_block_add(sum, next, off);
off += v.iov_len;
}
- err ? v.iov_len : 0;
+ next ? 0 : v.iov_len;
}), ({
char *p = kmap_atomic(v.bv_page);
sum = csum_and_memcpy(p + v.bv_offset,
@@ -1650,16 +1646,145 @@ const void *dup_iter(struct iov_iter *new, struct iov_iter *old, gfp_t flags)
}
EXPORT_SYMBOL(dup_iter);
+static int copy_compat_iovec_from_user(struct iovec *iov,
+ const struct iovec __user *uvec, unsigned long nr_segs)
+{
+ const struct compat_iovec __user *uiov =
+ (const struct compat_iovec __user *)uvec;
+ int ret = -EFAULT, i;
+
+ if (!user_access_begin(uvec, nr_segs * sizeof(*uvec)))
+ return -EFAULT;
+
+ for (i = 0; i < nr_segs; i++) {
+ compat_uptr_t buf;
+ compat_ssize_t len;
+
+ unsafe_get_user(len, &uiov[i].iov_len, uaccess_end);
+ unsafe_get_user(buf, &uiov[i].iov_base, uaccess_end);
+
+ /* check for compat_size_t not fitting in compat_ssize_t .. */
+ if (len < 0) {
+ ret = -EINVAL;
+ goto uaccess_end;
+ }
+ iov[i].iov_base = compat_ptr(buf);
+ iov[i].iov_len = len;
+ }
+
+ ret = 0;
+uaccess_end:
+ user_access_end();
+ return ret;
+}
+
+static int copy_iovec_from_user(struct iovec *iov,
+ const struct iovec __user *uvec, unsigned long nr_segs)
+{
+ unsigned long seg;
+
+ if (copy_from_user(iov, uvec, nr_segs * sizeof(*uvec)))
+ return -EFAULT;
+ for (seg = 0; seg < nr_segs; seg++) {
+ if ((ssize_t)iov[seg].iov_len < 0)
+ return -EINVAL;
+ }
+
+ return 0;
+}
+
+struct iovec *iovec_from_user(const struct iovec __user *uvec,
+ unsigned long nr_segs, unsigned long fast_segs,
+ struct iovec *fast_iov, bool compat)
+{
+ struct iovec *iov = fast_iov;
+ int ret;
+
+ /*
+ * SuS says "The readv() function *may* fail if the iovcnt argument was
+ * less than or equal to 0, or greater than {IOV_MAX}. Linux has
+ * traditionally returned zero for zero segments, so...
+ */
+ if (nr_segs == 0)
+ return iov;
+ if (nr_segs > UIO_MAXIOV)
+ return ERR_PTR(-EINVAL);
+ if (nr_segs > fast_segs) {
+ iov = kmalloc_array(nr_segs, sizeof(struct iovec), GFP_KERNEL);
+ if (!iov)
+ return ERR_PTR(-ENOMEM);
+ }
+
+ if (compat)
+ ret = copy_compat_iovec_from_user(iov, uvec, nr_segs);
+ else
+ ret = copy_iovec_from_user(iov, uvec, nr_segs);
+ if (ret) {
+ if (iov != fast_iov)
+ kfree(iov);
+ return ERR_PTR(ret);
+ }
+
+ return iov;
+}
+
+ssize_t __import_iovec(int type, const struct iovec __user *uvec,
+ unsigned nr_segs, unsigned fast_segs, struct iovec **iovp,
+ struct iov_iter *i, bool compat)
+{
+ ssize_t total_len = 0;
+ unsigned long seg;
+ struct iovec *iov;
+
+ iov = iovec_from_user(uvec, nr_segs, fast_segs, *iovp, compat);
+ if (IS_ERR(iov)) {
+ *iovp = NULL;
+ return PTR_ERR(iov);
+ }
+
+ /*
+ * According to the Single Unix Specification we should return EINVAL if
+ * an element length is < 0 when cast to ssize_t or if the total length
+ * would overflow the ssize_t return value of the system call.
+ *
+ * Linux caps all read/write calls to MAX_RW_COUNT, and avoids the
+ * overflow case.
+ */
+ for (seg = 0; seg < nr_segs; seg++) {
+ ssize_t len = (ssize_t)iov[seg].iov_len;
+
+ if (!access_ok(iov[seg].iov_base, len)) {
+ if (iov != *iovp)
+ kfree(iov);
+ *iovp = NULL;
+ return -EFAULT;
+ }
+
+ if (len > MAX_RW_COUNT - total_len) {
+ len = MAX_RW_COUNT - total_len;
+ iov[seg].iov_len = len;
+ }
+ total_len += len;
+ }
+
+ iov_iter_init(i, type, iov, nr_segs, total_len);
+ if (iov == *iovp)
+ *iovp = NULL;
+ else
+ *iovp = iov;
+ return total_len;
+}
+
/**
* import_iovec() - Copy an array of &struct iovec from userspace
* into the kernel, check that it is valid, and initialize a new
* &struct iov_iter iterator to access it.
*
* @type: One of %READ or %WRITE.
- * @uvector: Pointer to the userspace array.
+ * @uvec: Pointer to the userspace array.
* @nr_segs: Number of elements in userspace array.
* @fast_segs: Number of elements in @iov.
- * @iov: (input and output parameter) Pointer to pointer to (usually small
+ * @iovp: (input and output parameter) Pointer to pointer to (usually small
* on-stack) kernel array.
* @i: Pointer to iterator that will be initialized on success.
*
@@ -1672,51 +1797,15 @@ EXPORT_SYMBOL(dup_iter);
*
* Return: Negative error code on error, bytes imported on success
*/
-ssize_t import_iovec(int type, const struct iovec __user * uvector,
+ssize_t import_iovec(int type, const struct iovec __user *uvec,
unsigned nr_segs, unsigned fast_segs,
- struct iovec **iov, struct iov_iter *i)
+ struct iovec **iovp, struct iov_iter *i)
{
- ssize_t n;
- struct iovec *p;
- n = rw_copy_check_uvector(type, uvector, nr_segs, fast_segs,
- *iov, &p);
- if (n < 0) {
- if (p != *iov)
- kfree(p);
- *iov = NULL;
- return n;
- }
- iov_iter_init(i, type, p, nr_segs, n);
- *iov = p == *iov ? NULL : p;
- return n;
+ return __import_iovec(type, uvec, nr_segs, fast_segs, iovp, i,
+ in_compat_syscall());
}
EXPORT_SYMBOL(import_iovec);
-#ifdef CONFIG_COMPAT
-#include <linux/compat.h>
-
-ssize_t compat_import_iovec(int type,
- const struct compat_iovec __user * uvector,
- unsigned nr_segs, unsigned fast_segs,
- struct iovec **iov, struct iov_iter *i)
-{
- ssize_t n;
- struct iovec *p;
- n = compat_rw_copy_check_uvector(type, uvector, nr_segs, fast_segs,
- *iov, &p);
- if (n < 0) {
- if (p != *iov)
- kfree(p);
- *iov = NULL;
- return n;
- }
- iov_iter_init(i, type, p, nr_segs, n);
- *iov = p == *iov ? NULL : p;
- return n;
-}
-EXPORT_SYMBOL(compat_import_iovec);
-#endif
-
int import_single_range(int rw, void __user *buf, size_t len,
struct iovec *iov, struct iov_iter *i)
{
diff --git a/lib/kunit/test.c b/lib/kunit/test.c
index c36037200310..dcc35fd30d95 100644
--- a/lib/kunit/test.c
+++ b/lib/kunit/test.c
@@ -10,16 +10,12 @@
#include <linux/kernel.h>
#include <linux/kref.h>
#include <linux/sched/debug.h>
+#include <linux/sched.h>
#include "debugfs.h"
#include "string-stream.h"
#include "try-catch-impl.h"
-static void kunit_set_failure(struct kunit *test)
-{
- WRITE_ONCE(test->success, false);
-}
-
static void kunit_print_tap_version(void)
{
static bool kunit_has_printed_tap_version;
@@ -288,6 +284,10 @@ static void kunit_try_run_case(void *data)
struct kunit_suite *suite = ctx->suite;
struct kunit_case *test_case = ctx->test_case;
+#if (IS_ENABLED(CONFIG_KASAN) && IS_ENABLED(CONFIG_KUNIT))
+ current->kunit_test = test;
+#endif /* IS_ENABLED(CONFIG_KASAN) && IS_ENABLED(CONFIG_KUNIT) */
+
/*
* kunit_run_case_internal may encounter a fatal error; if it does,
* abort will be called, this thread will exit, and finally the parent
@@ -602,6 +602,9 @@ void kunit_cleanup(struct kunit *test)
spin_unlock(&test->lock);
kunit_remove_resource(test, res);
}
+#if (IS_ENABLED(CONFIG_KASAN) && IS_ENABLED(CONFIG_KUNIT))
+ current->kunit_test = NULL;
+#endif /* IS_ENABLED(CONFIG_KASAN) && IS_ENABLED(CONFIG_KUNIT)*/
}
EXPORT_SYMBOL_GPL(kunit_cleanup);
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 14f44f59e733..a899b3f0e2e5 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -28,6 +28,7 @@
* Change this to 1 if you want to see the failure printouts:
*/
static unsigned int debug_locks_verbose;
+unsigned int force_read_lock_recursive;
static DEFINE_WD_CLASS(ww_lockdep);
@@ -399,6 +400,49 @@ static void rwsem_ABBA1(void)
* read_lock(A)
* spin_lock(B)
* spin_lock(B)
+ * write_lock(A)
+ *
+ * This test case is aimed at poking whether the chain cache prevents us from
+ * detecting a read-lock/lock-write deadlock: if the chain cache doesn't differ
+ * read/write locks, the following case may happen
+ *
+ * { read_lock(A)->lock(B) dependency exists }
+ *
+ * P0:
+ * lock(B);
+ * read_lock(A);
+ *
+ * { Not a deadlock, B -> A is added in the chain cache }
+ *
+ * P1:
+ * lock(B);
+ * write_lock(A);
+ *
+ * { B->A found in chain cache, not reported as a deadlock }
+ *
+ */
+static void rlock_chaincache_ABBA1(void)
+{
+ RL(X1);
+ L(Y1);
+ U(Y1);
+ RU(X1);
+
+ L(Y1);
+ RL(X1);
+ RU(X1);
+ U(Y1);
+
+ L(Y1);
+ WL(X1);
+ WU(X1);
+ U(Y1); // should fail
+}
+
+/*
+ * read_lock(A)
+ * spin_lock(B)
+ * spin_lock(B)
* read_lock(A)
*/
static void rlock_ABBA2(void)
@@ -991,6 +1035,133 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_soft_wlock)
#undef E3
/*
+ * write-read / write-read / write-read deadlock even if read is recursive
+ */
+
+#define E1() \
+ \
+ WL(X1); \
+ RL(Y1); \
+ RU(Y1); \
+ WU(X1);
+
+#define E2() \
+ \
+ WL(Y1); \
+ RL(Z1); \
+ RU(Z1); \
+ WU(Y1);
+
+#define E3() \
+ \
+ WL(Z1); \
+ RL(X1); \
+ RU(X1); \
+ WU(Z1);
+
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(W1R2_W2R3_W3R1)
+
+#undef E1
+#undef E2
+#undef E3
+
+/*
+ * write-write / read-read / write-read deadlock even if read is recursive
+ */
+
+#define E1() \
+ \
+ WL(X1); \
+ WL(Y1); \
+ WU(Y1); \
+ WU(X1);
+
+#define E2() \
+ \
+ RL(Y1); \
+ RL(Z1); \
+ RU(Z1); \
+ RU(Y1);
+
+#define E3() \
+ \
+ WL(Z1); \
+ RL(X1); \
+ RU(X1); \
+ WU(Z1);
+
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(W1W2_R2R3_W3R1)
+
+#undef E1
+#undef E2
+#undef E3
+
+/*
+ * write-write / read-read / read-write is not deadlock when read is recursive
+ */
+
+#define E1() \
+ \
+ WL(X1); \
+ WL(Y1); \
+ WU(Y1); \
+ WU(X1);
+
+#define E2() \
+ \
+ RL(Y1); \
+ RL(Z1); \
+ RU(Z1); \
+ RU(Y1);
+
+#define E3() \
+ \
+ RL(Z1); \
+ WL(X1); \
+ WU(X1); \
+ RU(Z1);
+
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(W1R2_R2R3_W3W1)
+
+#undef E1
+#undef E2
+#undef E3
+
+/*
+ * write-read / read-read / write-write is not deadlock when read is recursive
+ */
+
+#define E1() \
+ \
+ WL(X1); \
+ RL(Y1); \
+ RU(Y1); \
+ WU(X1);
+
+#define E2() \
+ \
+ RL(Y1); \
+ RL(Z1); \
+ RU(Z1); \
+ RU(Y1);
+
+#define E3() \
+ \
+ WL(Z1); \
+ WL(X1); \
+ WU(X1); \
+ WU(Z1);
+
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(W1W2_R2R3_R3W1)
+
+#undef E1
+#undef E2
+#undef E3
+/*
* read-lock / write-lock recursion that is actually safe.
*/
@@ -1009,20 +1180,28 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_inversion_soft_wlock)
#define E3() \
\
IRQ_ENTER(); \
- RL(A); \
+ LOCK(A); \
L(B); \
U(B); \
- RU(A); \
+ UNLOCK(A); \
IRQ_EXIT();
/*
- * Generate 12 testcases:
+ * Generate 24 testcases:
*/
#include "locking-selftest-hardirq.h"
-GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_hard)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_hard_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_hard_wlock)
#include "locking-selftest-softirq.h"
-GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft_wlock)
#undef E1
#undef E2
@@ -1036,8 +1215,8 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft)
\
IRQ_DISABLE(); \
L(B); \
- WL(A); \
- WU(A); \
+ LOCK(A); \
+ UNLOCK(A); \
U(B); \
IRQ_ENABLE();
@@ -1054,13 +1233,75 @@ GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion_soft)
IRQ_EXIT();
/*
- * Generate 12 testcases:
+ * Generate 24 testcases:
*/
#include "locking-selftest-hardirq.h"
-// GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_hard)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_hard_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_hard_wlock)
#include "locking-selftest-softirq.h"
-// GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft)
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion2_soft_wlock)
+
+#undef E1
+#undef E2
+#undef E3
+/*
+ * read-lock / write-lock recursion that is unsafe.
+ *
+ * A is a ENABLED_*_READ lock
+ * B is a USED_IN_*_READ lock
+ *
+ * read_lock(A);
+ * write_lock(B);
+ * <interrupt>
+ * read_lock(B);
+ * write_lock(A); // if this one is read_lock(), no deadlock
+ */
+
+#define E1() \
+ \
+ IRQ_DISABLE(); \
+ WL(B); \
+ LOCK(A); \
+ UNLOCK(A); \
+ WU(B); \
+ IRQ_ENABLE();
+
+#define E2() \
+ \
+ RL(A); \
+ RU(A); \
+
+#define E3() \
+ \
+ IRQ_ENTER(); \
+ RL(B); \
+ RU(B); \
+ IRQ_EXIT();
+
+/*
+ * Generate 24 testcases:
+ */
+#include "locking-selftest-hardirq.h"
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_hard_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_hard_wlock)
+
+#include "locking-selftest-softirq.h"
+#include "locking-selftest-rlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_soft_rlock)
+
+#include "locking-selftest-wlock.h"
+GENERATE_PERMUTATIONS_3_EVENTS(irq_read_recursion3_soft_wlock)
#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define I_SPINLOCK(x) lockdep_reset_lock(&lock_##x.dep_map)
@@ -1199,6 +1440,19 @@ static inline void print_testname(const char *testname)
dotest(name##_##nr, FAILURE, LOCKTYPE_RWLOCK); \
pr_cont("\n");
+#define DO_TESTCASE_1RR(desc, name, nr) \
+ print_testname(desc"/"#nr); \
+ pr_cont(" |"); \
+ dotest(name##_##nr, SUCCESS, LOCKTYPE_RWLOCK); \
+ pr_cont("\n");
+
+#define DO_TESTCASE_1RRB(desc, name, nr) \
+ print_testname(desc"/"#nr); \
+ pr_cont(" |"); \
+ dotest(name##_##nr, FAILURE, LOCKTYPE_RWLOCK); \
+ pr_cont("\n");
+
+
#define DO_TESTCASE_3(desc, name, nr) \
print_testname(desc"/"#nr); \
dotest(name##_spin_##nr, FAILURE, LOCKTYPE_SPIN); \
@@ -1213,6 +1467,25 @@ static inline void print_testname(const char *testname)
dotest(name##_rlock_##nr, SUCCESS, LOCKTYPE_RWLOCK); \
pr_cont("\n");
+#define DO_TESTCASE_2RW(desc, name, nr) \
+ print_testname(desc"/"#nr); \
+ pr_cont(" |"); \
+ dotest(name##_wlock_##nr, FAILURE, LOCKTYPE_RWLOCK); \
+ dotest(name##_rlock_##nr, SUCCESS, LOCKTYPE_RWLOCK); \
+ pr_cont("\n");
+
+#define DO_TESTCASE_2x2RW(desc, name, nr) \
+ DO_TESTCASE_2RW("hard-"desc, name##_hard, nr) \
+ DO_TESTCASE_2RW("soft-"desc, name##_soft, nr) \
+
+#define DO_TESTCASE_6x2x2RW(desc, name) \
+ DO_TESTCASE_2x2RW(desc, name, 123); \
+ DO_TESTCASE_2x2RW(desc, name, 132); \
+ DO_TESTCASE_2x2RW(desc, name, 213); \
+ DO_TESTCASE_2x2RW(desc, name, 231); \
+ DO_TESTCASE_2x2RW(desc, name, 312); \
+ DO_TESTCASE_2x2RW(desc, name, 321);
+
#define DO_TESTCASE_6(desc, name) \
print_testname(desc); \
dotest(name##_spin, FAILURE, LOCKTYPE_SPIN); \
@@ -1289,6 +1562,22 @@ static inline void print_testname(const char *testname)
DO_TESTCASE_2IB(desc, name, 312); \
DO_TESTCASE_2IB(desc, name, 321);
+#define DO_TESTCASE_6x1RR(desc, name) \
+ DO_TESTCASE_1RR(desc, name, 123); \
+ DO_TESTCASE_1RR(desc, name, 132); \
+ DO_TESTCASE_1RR(desc, name, 213); \
+ DO_TESTCASE_1RR(desc, name, 231); \
+ DO_TESTCASE_1RR(desc, name, 312); \
+ DO_TESTCASE_1RR(desc, name, 321);
+
+#define DO_TESTCASE_6x1RRB(desc, name) \
+ DO_TESTCASE_1RRB(desc, name, 123); \
+ DO_TESTCASE_1RRB(desc, name, 132); \
+ DO_TESTCASE_1RRB(desc, name, 213); \
+ DO_TESTCASE_1RRB(desc, name, 231); \
+ DO_TESTCASE_1RRB(desc, name, 312); \
+ DO_TESTCASE_1RRB(desc, name, 321);
+
#define DO_TESTCASE_6x6(desc, name) \
DO_TESTCASE_6I(desc, name, 123); \
DO_TESTCASE_6I(desc, name, 132); \
@@ -1966,6 +2255,108 @@ static void ww_tests(void)
pr_cont("\n");
}
+
+/*
+ * <in hardirq handler>
+ * read_lock(&A);
+ * <hardirq disable>
+ * spin_lock(&B);
+ * spin_lock(&B);
+ * read_lock(&A);
+ *
+ * is a deadlock.
+ */
+static void queued_read_lock_hardirq_RE_Er(void)
+{
+ HARDIRQ_ENTER();
+ read_lock(&rwlock_A);
+ LOCK(B);
+ UNLOCK(B);
+ read_unlock(&rwlock_A);
+ HARDIRQ_EXIT();
+
+ HARDIRQ_DISABLE();
+ LOCK(B);
+ read_lock(&rwlock_A);
+ read_unlock(&rwlock_A);
+ UNLOCK(B);
+ HARDIRQ_ENABLE();
+}
+
+/*
+ * <in hardirq handler>
+ * spin_lock(&B);
+ * <hardirq disable>
+ * read_lock(&A);
+ * read_lock(&A);
+ * spin_lock(&B);
+ *
+ * is not a deadlock.
+ */
+static void queued_read_lock_hardirq_ER_rE(void)
+{
+ HARDIRQ_ENTER();
+ LOCK(B);
+ read_lock(&rwlock_A);
+ read_unlock(&rwlock_A);
+ UNLOCK(B);
+ HARDIRQ_EXIT();
+
+ HARDIRQ_DISABLE();
+ read_lock(&rwlock_A);
+ LOCK(B);
+ UNLOCK(B);
+ read_unlock(&rwlock_A);
+ HARDIRQ_ENABLE();
+}
+
+/*
+ * <hardirq disable>
+ * spin_lock(&B);
+ * read_lock(&A);
+ * <in hardirq handler>
+ * spin_lock(&B);
+ * read_lock(&A);
+ *
+ * is a deadlock. Because the two read_lock()s are both non-recursive readers.
+ */
+static void queued_read_lock_hardirq_inversion(void)
+{
+
+ HARDIRQ_ENTER();
+ LOCK(B);
+ UNLOCK(B);
+ HARDIRQ_EXIT();
+
+ HARDIRQ_DISABLE();
+ LOCK(B);
+ read_lock(&rwlock_A);
+ read_unlock(&rwlock_A);
+ UNLOCK(B);
+ HARDIRQ_ENABLE();
+
+ read_lock(&rwlock_A);
+ read_unlock(&rwlock_A);
+}
+
+static void queued_read_lock_tests(void)
+{
+ printk(" --------------------------------------------------------------------------\n");
+ printk(" | queued read lock tests |\n");
+ printk(" ---------------------------\n");
+ print_testname("hardirq read-lock/lock-read");
+ dotest(queued_read_lock_hardirq_RE_Er, FAILURE, LOCKTYPE_RWLOCK);
+ pr_cont("\n");
+
+ print_testname("hardirq lock-read/read-lock");
+ dotest(queued_read_lock_hardirq_ER_rE, SUCCESS, LOCKTYPE_RWLOCK);
+ pr_cont("\n");
+
+ print_testname("hardirq inversion");
+ dotest(queued_read_lock_hardirq_inversion, FAILURE, LOCKTYPE_RWLOCK);
+ pr_cont("\n");
+}
+
void locking_selftest(void)
{
/*
@@ -1979,6 +2370,11 @@ void locking_selftest(void)
}
/*
+ * treats read_lock() as recursive read locks for testing purpose
+ */
+ force_read_lock_recursive = 1;
+
+ /*
* Run the testsuite:
*/
printk("------------------------\n");
@@ -2033,14 +2429,6 @@ void locking_selftest(void)
print_testname("mixed read-lock/lock-write ABBA");
pr_cont(" |");
dotest(rlock_ABBA1, FAILURE, LOCKTYPE_RWLOCK);
-#ifdef CONFIG_PROVE_LOCKING
- /*
- * Lockdep does indeed fail here, but there's nothing we can do about
- * that now. Don't kill lockdep for it.
- */
- unexpected_testcase_failures--;
-#endif
-
pr_cont(" |");
dotest(rwsem_ABBA1, FAILURE, LOCKTYPE_RWSEM);
@@ -2056,6 +2444,15 @@ void locking_selftest(void)
pr_cont(" |");
dotest(rwsem_ABBA3, FAILURE, LOCKTYPE_RWSEM);
+ print_testname("chain cached mixed R-L/L-W ABBA");
+ pr_cont(" |");
+ dotest(rlock_chaincache_ABBA1, FAILURE, LOCKTYPE_RWLOCK);
+
+ DO_TESTCASE_6x1RRB("rlock W1R2/W2R3/W3R1", W1R2_W2R3_W3R1);
+ DO_TESTCASE_6x1RRB("rlock W1W2/R2R3/W3R1", W1W2_R2R3_W3R1);
+ DO_TESTCASE_6x1RR("rlock W1W2/R2R3/R3W1", W1W2_R2R3_R3W1);
+ DO_TESTCASE_6x1RR("rlock W1R2/R2R3/W3W1", W1R2_R2R3_W3W1);
+
printk(" --------------------------------------------------------------------------\n");
/*
@@ -2068,11 +2465,19 @@ void locking_selftest(void)
DO_TESTCASE_6x6("safe-A + unsafe-B #2", irqsafe4);
DO_TESTCASE_6x6RW("irq lock-inversion", irq_inversion);
- DO_TESTCASE_6x2("irq read-recursion", irq_read_recursion);
-// DO_TESTCASE_6x2B("irq read-recursion #2", irq_read_recursion2);
+ DO_TESTCASE_6x2x2RW("irq read-recursion", irq_read_recursion);
+ DO_TESTCASE_6x2x2RW("irq read-recursion #2", irq_read_recursion2);
+ DO_TESTCASE_6x2x2RW("irq read-recursion #3", irq_read_recursion3);
ww_tests();
+ force_read_lock_recursive = 0;
+ /*
+ * queued_read_lock() specific test cases can be put here
+ */
+ if (IS_ENABLED(CONFIG_QUEUED_RWLOCKS))
+ queued_read_lock_tests();
+
if (unexpected_testcase_failures) {
printk("-----------------------------------------------------------------\n");
debug_locks = 0;
diff --git a/lib/memregion.c b/lib/memregion.c
index 77c85b5251da..be5cfa5a3b57 100644
--- a/lib/memregion.c
+++ b/lib/memregion.c
@@ -2,6 +2,7 @@
/* identifiers for device / performance-differentiated memory regions */
#include <linux/idr.h>
#include <linux/types.h>
+#include <linux/memregion.h>
static DEFINE_IDA(memregion_ids);
diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile
index 43b8fce14079..6e6ef9a34fe1 100644
--- a/lib/mpi/Makefile
+++ b/lib/mpi/Makefile
@@ -13,10 +13,16 @@ 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 \
mpih-div.o \
mpih-mul.o \
diff --git a/lib/mpi/ec.c b/lib/mpi/ec.c
new file mode 100644
index 000000000000..c21470122dfc
--- /dev/null
+++ b/lib/mpi/ec.c
@@ -0,0 +1,1509 @@
+/* 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->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;
+ int scalar_copied = 0;
+
+ /* 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--) {
+ MPI_POINT t;
+
+ 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);
+ t = q1; q1 = prd; prd = t;
+ t = q2; q2 = sum; sum = t;
+ }
+
+ 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_);
+ if (scalar_copied)
+ mpi_free(scalar);
+ 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/mpi/mpi-add.c b/lib/mpi/mpi-add.c
new file mode 100644
index 000000000000..2cdae54c1bd0
--- /dev/null
+++ b/lib/mpi/mpi-add.c
@@ -0,0 +1,155 @@
+/* mpi-add.c - MPI functions
+ * Copyright (C) 1994, 1996, 1998, 2001, 2002,
+ * 2003 Free Software Foundation, Inc.
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ * Actually it's the same code with only minor changes in the
+ * way the data is stored; this is to support the abstraction
+ * of an optional secure memory allocation which may be used
+ * to avoid revealing of sensitive data due to paging etc.
+ */
+
+#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)
+{
+ mpi_ptr_t wp, up, vp;
+ mpi_size_t usize, vsize, wsize;
+ int usign, vsign, wsign;
+
+ if (u->nlimbs < v->nlimbs) { /* Swap U and V. */
+ usize = v->nlimbs;
+ usign = v->sign;
+ vsize = u->nlimbs;
+ vsign = u->sign;
+ wsize = usize + 1;
+ RESIZE_IF_NEEDED(w, wsize);
+ /* These must be after realloc (u or v may be the same as w). */
+ up = v->d;
+ vp = u->d;
+ } else {
+ usize = u->nlimbs;
+ usign = u->sign;
+ vsize = v->nlimbs;
+ vsign = v->sign;
+ wsize = usize + 1;
+ RESIZE_IF_NEEDED(w, wsize);
+ /* These must be after realloc (u or v may be the same as w). */
+ up = u->d;
+ vp = v->d;
+ }
+ wp = w->d;
+ wsign = 0;
+
+ if (!vsize) { /* simple */
+ MPN_COPY(wp, up, usize);
+ wsize = usize;
+ wsign = usign;
+ } else if (usign != vsign) { /* different sign */
+ /* This test is right since USIZE >= VSIZE */
+ if (usize != vsize) {
+ mpihelp_sub(wp, up, usize, vp, vsize);
+ wsize = usize;
+ MPN_NORMALIZE(wp, wsize);
+ wsign = usign;
+ } else if (mpihelp_cmp(up, vp, usize) < 0) {
+ mpihelp_sub_n(wp, vp, up, usize);
+ wsize = usize;
+ MPN_NORMALIZE(wp, wsize);
+ if (!usign)
+ wsign = 1;
+ } else {
+ mpihelp_sub_n(wp, up, vp, usize);
+ wsize = usize;
+ MPN_NORMALIZE(wp, wsize);
+ if (usign)
+ wsign = 1;
+ }
+ } else { /* U and V have same sign. Add them. */
+ mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
+ wp[usize] = cy;
+ wsize = usize + cy;
+ if (usign)
+ wsign = 1;
+ }
+
+ w->nlimbs = wsize;
+ w->sign = wsign;
+}
+EXPORT_SYMBOL_GPL(mpi_add);
+
+void mpi_sub(MPI w, MPI u, MPI v)
+{
+ MPI vv = mpi_copy(v);
+ vv->sign = !vv->sign;
+ mpi_add(w, u, vv);
+ mpi_free(vv);
+}
+
+
+void mpi_addm(MPI w, MPI u, MPI v, MPI m)
+{
+ 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)
+{
+ mpi_sub(w, u, v);
+ mpi_mod(w, w, m);
+}
+EXPORT_SYMBOL_GPL(mpi_subm);
diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c
index 503537e08436..a5119a2bcdd4 100644
--- a/lib/mpi/mpi-bit.c
+++ b/lib/mpi/mpi-bit.c
@@ -32,6 +32,7 @@ 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.
@@ -54,3 +55,253 @@ unsigned mpi_get_nbits(MPI a)
return n;
}
EXPORT_SYMBOL_GPL(mpi_get_nbits);
+
+/****************
+ * Test whether bit N is set.
+ */
+int mpi_test_bit(MPI a, unsigned int n)
+{
+ unsigned int limbno, bitno;
+ mpi_limb_t limb;
+
+ limbno = n / BITS_PER_MPI_LIMB;
+ bitno = n % BITS_PER_MPI_LIMB;
+
+ if (limbno >= a->nlimbs)
+ return 0; /* too far left: this is a 0 */
+ limb = a->d[limbno];
+ return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
+}
+EXPORT_SYMBOL_GPL(mpi_test_bit);
+
+/****************
+ * Set bit N of A.
+ */
+void mpi_set_bit(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);
+}
+
+/****************
+ * 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;
+}
+
+/*
+ * Shift A by N bits to the right.
+ */
+void 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);
+
+ if (x == a) {
+ /* In-place operation. */
+ if (nlimbs >= x->nlimbs) {
+ x->nlimbs = 0;
+ return;
+ }
+
+ if (nlimbs) {
+ for (i = 0; i < x->nlimbs - nlimbs; i++)
+ x->d[i] = x->d[i+nlimbs];
+ x->d[i] = 0;
+ x->nlimbs -= nlimbs;
+ }
+ if (x->nlimbs && nbits)
+ mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
+ } else if (nlimbs) {
+ /* Copy and shift by more or equal bits than in a limb. */
+ xsize = a->nlimbs;
+ x->sign = a->sign;
+ RESIZE_IF_NEEDED(x, xsize);
+ x->nlimbs = xsize;
+ for (i = 0; i < a->nlimbs; i++)
+ x->d[i] = a->d[i];
+ x->nlimbs = i;
+
+ if (nlimbs >= x->nlimbs) {
+ x->nlimbs = 0;
+ return;
+ }
+
+ if (nlimbs) {
+ for (i = 0; i < x->nlimbs - nlimbs; i++)
+ x->d[i] = x->d[i+nlimbs];
+ x->d[i] = 0;
+ x->nlimbs -= nlimbs;
+ }
+
+ if (x->nlimbs && nbits)
+ mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
+ } else {
+ /* Copy and shift by less than bits in a limb. */
+ xsize = a->nlimbs;
+ x->sign = a->sign;
+ RESIZE_IF_NEEDED(x, xsize);
+ x->nlimbs = xsize;
+
+ if (xsize) {
+ if (nbits)
+ mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
+ else {
+ /* The rshift helper function is not specified for
+ * NBITS==0, thus we do a plain copy here.
+ */
+ for (i = 0; i < x->nlimbs; i++)
+ x->d[i] = a->d[i];
+ }
+ }
+ }
+ MPN_NORMALIZE(x->d, x->nlimbs);
+}
+
+/****************
+ * 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);
+}
diff --git a/lib/mpi/mpi-cmp.c b/lib/mpi/mpi-cmp.c
index d25e9e96c310..c4cfa3ff0581 100644
--- a/lib/mpi/mpi-cmp.c
+++ b/lib/mpi/mpi-cmp.c
@@ -41,28 +41,54 @@ int mpi_cmp_ui(MPI u, unsigned long v)
}
EXPORT_SYMBOL_GPL(mpi_cmp_ui);
-int mpi_cmp(MPI u, MPI v)
+static int do_mpi_cmp(MPI u, MPI v, int absmode)
{
- mpi_size_t usize, vsize;
+ mpi_size_t usize;
+ mpi_size_t vsize;
+ int usign;
+ int vsign;
int cmp;
mpi_normalize(u);
mpi_normalize(v);
+
usize = u->nlimbs;
vsize = v->nlimbs;
- if (!u->sign && v->sign)
+ usign = absmode ? 0 : u->sign;
+ vsign = absmode ? 0 : v->sign;
+
+ /* Compare sign bits. */
+
+ if (!usign && vsign)
return 1;
- if (u->sign && !v->sign)
+ if (usign && !vsign)
return -1;
- if (usize != vsize && !u->sign && !v->sign)
+
+ /* U and V are either both positive or both negative. */
+
+ if (usize != vsize && !usign && !vsign)
return usize - vsize;
- if (usize != vsize && u->sign && v->sign)
- return vsize - usize;
+ if (usize != vsize && usign && vsign)
+ return vsize + usize;
if (!usize)
return 0;
cmp = mpihelp_cmp(u->d, v->d, usize);
- if (u->sign)
- return -cmp;
- return cmp;
+ 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);
}
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/mpi/mpi-div.c b/lib/mpi/mpi-div.c
new file mode 100644
index 000000000000..45beab8b9e9e
--- /dev/null
+++ b/lib/mpi/mpi-div.c
@@ -0,0 +1,234 @@
+/* mpi-div.c - MPI functions
+ * Copyright (C) 1994, 1996, 1998, 2001, 2002,
+ * 2003 Free Software Foundation, Inc.
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ * Actually it's the same code with only minor changes in the
+ * way the data is stored; this is to support the abstraction
+ * of an optional secure memory allocation which may be used
+ * to avoid revealing of sensitive data due to paging etc.
+ */
+
+#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);
+
+void mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor)
+{
+ int divisor_sign = divisor->sign;
+ MPI temp_divisor = NULL;
+
+ /* 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
+ * the same variable as REM.
+ */
+ if (rem == divisor) {
+ temp_divisor = mpi_copy(divisor);
+ divisor = temp_divisor;
+ }
+
+ mpi_tdiv_r(rem, dividend, divisor);
+
+ if (((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs)
+ mpi_add(rem, rem, divisor);
+
+ if (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);
+}
+
+/* If den == quot, den needs temporary storage.
+ * If den == rem, den needs temporary storage.
+ * If num == quot, num needs temporary storage.
+ * If den has temporary storage, it can be normalized while being copied,
+ * i.e no extra storage should be allocated.
+ */
+
+void mpi_tdiv_r(MPI rem, MPI num, MPI den)
+{
+ mpi_tdiv_qr(NULL, rem, num, den);
+}
+
+void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den)
+{
+ mpi_ptr_t np, dp;
+ mpi_ptr_t qp, rp;
+ mpi_size_t nsize = num->nlimbs;
+ mpi_size_t dsize = den->nlimbs;
+ mpi_size_t qsize, rsize;
+ mpi_size_t sign_remainder = num->sign;
+ mpi_size_t sign_quotient = num->sign ^ den->sign;
+ unsigned int normalization_steps;
+ mpi_limb_t q_limb;
+ mpi_ptr_t marker[5];
+ int markidx = 0;
+
+ /* 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);
+
+ qsize = rsize - dsize; /* qsize cannot be bigger than this. */
+ if (qsize <= 0) {
+ if (num != rem) {
+ rem->nlimbs = num->nlimbs;
+ rem->sign = num->sign;
+ MPN_COPY(rem->d, num->d, nsize);
+ }
+ if (quot) {
+ /* This needs to follow the assignment to rem, in case the
+ * numerator and quotient are the same.
+ */
+ quot->nlimbs = 0;
+ quot->sign = 0;
+ }
+ return;
+ }
+
+ if (quot)
+ mpi_resize(quot, qsize);
+
+ /* Read pointers here, when reallocation is finished. */
+ np = num->d;
+ dp = den->d;
+ rp = rem->d;
+
+ /* Optimize division by a single-limb divisor. */
+ if (dsize == 1) {
+ mpi_limb_t rlimb;
+ if (quot) {
+ qp = quot->d;
+ rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]);
+ qsize -= qp[qsize - 1] == 0;
+ quot->nlimbs = qsize;
+ quot->sign = sign_quotient;
+ } else
+ rlimb = mpihelp_mod_1(np, nsize, dp[0]);
+ rp[0] = rlimb;
+ rsize = rlimb != 0?1:0;
+ rem->nlimbs = rsize;
+ rem->sign = sign_remainder;
+ return;
+ }
+
+
+ if (quot) {
+ qp = quot->d;
+ /* Make sure QP and NP point to different objects. Otherwise the
+ * numerator would be gradually overwritten by the quotient limbs.
+ */
+ if (qp == np) { /* Copy NP object to temporary space. */
+ np = marker[markidx++] = mpi_alloc_limb_space(nsize);
+ MPN_COPY(np, qp, nsize);
+ }
+ } else /* Put quotient at top of remainder. */
+ qp = rp + dsize;
+
+ normalization_steps = count_leading_zeros(dp[dsize - 1]);
+
+ /* Normalize the denominator, i.e. make its most significant bit set by
+ * shifting it NORMALIZATION_STEPS bits to the left. Also shift the
+ * numerator the same number of steps (to keep the quotient the same!).
+ */
+ if (normalization_steps) {
+ mpi_ptr_t tp;
+ mpi_limb_t nlimb;
+
+ /* Shift up the denominator setting the most significant bit of
+ * the most significant word. Use temporary storage not to clobber
+ * the original contents of the denominator.
+ */
+ tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
+ mpihelp_lshift(tp, dp, dsize, normalization_steps);
+ dp = tp;
+
+ /* Shift up the numerator, possibly introducing a new most
+ * significant word. Move the shifted numerator in the remainder
+ * meanwhile.
+ */
+ nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps);
+ if (nlimb) {
+ rp[nsize] = nlimb;
+ rsize = nsize + 1;
+ } else
+ rsize = nsize;
+ } else {
+ /* The denominator is already normalized, as required. Copy it to
+ * temporary space if it overlaps with the quotient or remainder.
+ */
+ if (dp == rp || (quot && (dp == qp))) {
+ mpi_ptr_t tp;
+
+ tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
+ MPN_COPY(tp, dp, dsize);
+ dp = tp;
+ }
+
+ /* Move the numerator to the remainder. */
+ if (rp != np)
+ MPN_COPY(rp, np, nsize);
+
+ rsize = nsize;
+ }
+
+ q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize);
+
+ if (quot) {
+ qsize = rsize - dsize;
+ if (q_limb) {
+ qp[qsize] = q_limb;
+ qsize += 1;
+ }
+
+ quot->nlimbs = qsize;
+ quot->sign = sign_quotient;
+ }
+
+ rsize = dsize;
+ MPN_NORMALIZE(rp, rsize);
+
+ if (normalization_steps && rsize) {
+ mpihelp_rshift(rp, rp, rsize, normalization_steps);
+ rsize -= rp[rsize - 1] == 0?1:0;
+ }
+
+ rem->nlimbs = rsize;
+ rem->sign = sign_remainder;
+ while (markidx) {
+ markidx--;
+ mpi_free_limb_space(marker[markidx]);
+ }
+}
diff --git a/lib/mpi/mpi-internal.h b/lib/mpi/mpi-internal.h
index 91df5f0b70f2..554002182db1 100644
--- a/lib/mpi/mpi-internal.h
+++ b/lib/mpi/mpi-internal.h
@@ -52,6 +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)
+
/* Copy N limbs from S to D. */
#define MPN_COPY(d, s, n) \
do { \
@@ -60,6 +66,14 @@ 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; \
@@ -92,6 +106,38 @@ typedef int mpi_size_t; /* (must be a signed type) */
mul_n(prodp, up, vp, size, tspace); \
} while (0);
+/* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
+ * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
+ * If this would yield overflow, DI should be the largest possible number
+ * (i.e., only ones). For correct operation, the most significant bit of D
+ * has to be set. Put the quotient in Q and the remainder in R.
+ */
+#define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \
+ do { \
+ mpi_limb_t _ql __maybe_unused; \
+ mpi_limb_t _q, _r; \
+ mpi_limb_t _xh, _xl; \
+ umul_ppmm(_q, _ql, (nh), (di)); \
+ _q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \
+ umul_ppmm(_xh, _xl, _q, (d)); \
+ sub_ddmmss(_xh, _r, (nh), (nl), _xh, _xl); \
+ if (_xh) { \
+ sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \
+ _q++; \
+ if (_xh) { \
+ sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \
+ _q++; \
+ } \
+ } \
+ if (_r >= (d)) { \
+ _r -= (d); \
+ _q++; \
+ } \
+ (r) = _r; \
+ (q) = _q; \
+ } while (0)
+
+
/*-- mpiutil.c --*/
mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs);
void mpi_free_limb_space(mpi_ptr_t a);
@@ -135,6 +181,8 @@ 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,
@@ -146,9 +194,14 @@ mpi_limb_t mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
mpi_size_t s1_size, mpi_limb_t s2_limb);
/*-- mpih-div.c --*/
+mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
+ mpi_limb_t divisor_limb);
mpi_limb_t mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
mpi_ptr_t np, mpi_size_t nsize,
mpi_ptr_t dp, mpi_size_t dsize);
+mpi_limb_t mpihelp_divmod_1(mpi_ptr_t quot_ptr,
+ mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
+ mpi_limb_t divisor_limb);
/*-- generic_mpih-[lr]shift.c --*/
mpi_limb_t mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
diff --git a/lib/mpi/mpi-inv.c b/lib/mpi/mpi-inv.c
new file mode 100644
index 000000000000..61e37d18f793
--- /dev/null
+++ b/lib/mpi/mpi-inv.c
@@ -0,0 +1,143 @@
+/* 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/mpi/mpi-mod.c b/lib/mpi/mpi-mod.c
new file mode 100644
index 000000000000..47bc59edd4ff
--- /dev/null
+++ b/lib/mpi/mpi-mod.c
@@ -0,0 +1,155 @@
+/* mpi-mod.c - Modular reduction
+ * Copyright (C) 1998, 1999, 2001, 2002, 2003,
+ * 2007 Free Software Foundation, Inc.
+ *
+ * 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 (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)
+{
+ mpi_mul(w, u, v);
+ mpi_mod_barrett(w, w, ctx);
+}
diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c
new file mode 100644
index 000000000000..8f5fa200f297
--- /dev/null
+++ b/lib/mpi/mpi-mul.c
@@ -0,0 +1,91 @@
+/* mpi-mul.c - MPI functions
+ * Copyright (C) 1994, 1996, 1998, 2001, 2002,
+ * 2003 Free Software Foundation, Inc.
+ *
+ * This file is part of Libgcrypt.
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ * Actually it's the same code with only minor changes in the
+ * way the data is stored; this is to support the abstraction
+ * of an optional secure memory allocation which may be used
+ * to avoid revealing of sensitive data due to paging etc.
+ */
+
+#include "mpi-internal.h"
+
+void mpi_mul(MPI w, MPI u, MPI v)
+{
+ mpi_size_t usize, vsize, wsize;
+ mpi_ptr_t up, vp, wp;
+ mpi_limb_t cy;
+ int usign, vsign, sign_product;
+ int assign_wp = 0;
+ mpi_ptr_t tmp_limb = NULL;
+
+ if (u->nlimbs < v->nlimbs) {
+ /* Swap U and V. */
+ usize = v->nlimbs;
+ usign = v->sign;
+ up = v->d;
+ vsize = u->nlimbs;
+ vsign = u->sign;
+ vp = u->d;
+ } else {
+ usize = u->nlimbs;
+ usign = u->sign;
+ up = u->d;
+ vsize = v->nlimbs;
+ vsign = v->sign;
+ vp = v->d;
+ }
+ sign_product = usign ^ vsign;
+ wp = w->d;
+
+ /* Ensure W has space enough to store the result. */
+ wsize = usize + vsize;
+ if (w->alloced < wsize) {
+ if (wp == up || wp == vp) {
+ wp = mpi_alloc_limb_space(wsize);
+ assign_wp = 1;
+ } else {
+ mpi_resize(w, wsize);
+ 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);
+ /* Is V identical too? Keep it identical with U. */
+ if (wp == vp)
+ vp = up;
+ /* Copy to the temporary space. */
+ MPN_COPY(up, wp, usize);
+ } else if (wp == vp) {
+ /* W and V are identical. Allocate temporary space for V. */
+ vp = tmp_limb = mpi_alloc_limb_space(vsize);
+ /* Copy to the temporary space. */
+ MPN_COPY(vp, wp, vsize);
+ }
+ }
+
+ if (!vsize)
+ wsize = 0;
+ else {
+ mpihelp_mul(wp, up, usize, vp, vsize, &cy);
+ wsize -= cy ? 0:1;
+ }
+
+ if (assign_wp)
+ mpi_assign_limb_space(w, wp, wsize);
+ w->nlimbs = wsize;
+ w->sign = sign_product;
+ if (tmp_limb)
+ mpi_free_limb_space(tmp_limb);
+}
+
+void mpi_mulm(MPI w, MPI u, MPI v, MPI m)
+{
+ mpi_mul(w, u, v);
+ mpi_tdiv_r(w, w, m);
+}
+EXPORT_SYMBOL_GPL(mpi_mulm);
diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c
index eead4b339466..7ea225b2204f 100644
--- a/lib/mpi/mpicoder.c
+++ b/lib/mpi/mpicoder.c
@@ -25,6 +25,7 @@
#include <linux/string.h>
#include "mpi-internal.h"
+#define MAX_EXTERN_SCAN_BYTES (16*1024*1024)
#define MAX_EXTERN_MPI_BITS 16384
/**
@@ -109,6 +110,112 @@ 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;
@@ -413,3 +520,232 @@ 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/mpi/mpih-div.c b/lib/mpi/mpih-div.c
index 913a519eb005..be70ee2e42d3 100644
--- a/lib/mpi/mpih-div.c
+++ b/lib/mpi/mpih-div.c
@@ -24,6 +24,150 @@
#define UDIV_TIME UMUL_TIME
#endif
+
+mpi_limb_t
+mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
+ mpi_limb_t divisor_limb)
+{
+ mpi_size_t i;
+ mpi_limb_t n1, n0, r;
+ mpi_limb_t dummy __maybe_unused;
+
+ /* Botch: Should this be handled at all? Rely on callers? */
+ if (!dividend_size)
+ return 0;
+
+ /* If multiplication is much faster than division, and the
+ * dividend is large, pre-invert the divisor, and use
+ * only multiplications in the inner loop.
+ *
+ * This test should be read:
+ * Does it ever help to use udiv_qrnnd_preinv?
+ * && Does what we save compensate for the inversion overhead?
+ */
+ if (UDIV_TIME > (2 * UMUL_TIME + 6)
+ && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
+ int normalization_steps;
+
+ normalization_steps = count_leading_zeros(divisor_limb);
+ if (normalization_steps) {
+ mpi_limb_t divisor_limb_inverted;
+
+ divisor_limb <<= normalization_steps;
+
+ /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
+ * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+ * most significant bit (with weight 2**N) implicit.
+ *
+ * Special case for DIVISOR_LIMB == 100...000.
+ */
+ if (!(divisor_limb << 1))
+ divisor_limb_inverted = ~(mpi_limb_t)0;
+ else
+ udiv_qrnnd(divisor_limb_inverted, dummy,
+ -divisor_limb, 0, divisor_limb);
+
+ n1 = dividend_ptr[dividend_size - 1];
+ r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
+
+ /* Possible optimization:
+ * if (r == 0
+ * && divisor_limb > ((n1 << normalization_steps)
+ * | (dividend_ptr[dividend_size - 2] >> ...)))
+ * ...one division less...
+ */
+ for (i = dividend_size - 2; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ UDIV_QRNND_PREINV(dummy, r, r,
+ ((n1 << normalization_steps)
+ | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
+ divisor_limb, divisor_limb_inverted);
+ n1 = n0;
+ }
+ UDIV_QRNND_PREINV(dummy, r, r,
+ n1 << normalization_steps,
+ divisor_limb, divisor_limb_inverted);
+ return r >> normalization_steps;
+ } else {
+ mpi_limb_t divisor_limb_inverted;
+
+ /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
+ * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+ * most significant bit (with weight 2**N) implicit.
+ *
+ * Special case for DIVISOR_LIMB == 100...000.
+ */
+ if (!(divisor_limb << 1))
+ divisor_limb_inverted = ~(mpi_limb_t)0;
+ else
+ udiv_qrnnd(divisor_limb_inverted, dummy,
+ -divisor_limb, 0, divisor_limb);
+
+ i = dividend_size - 1;
+ r = dividend_ptr[i];
+
+ if (r >= divisor_limb)
+ r = 0;
+ else
+ i--;
+
+ for ( ; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ UDIV_QRNND_PREINV(dummy, r, r,
+ n0, divisor_limb, divisor_limb_inverted);
+ }
+ return r;
+ }
+ } else {
+ if (UDIV_NEEDS_NORMALIZATION) {
+ int normalization_steps;
+
+ normalization_steps = count_leading_zeros(divisor_limb);
+ if (normalization_steps) {
+ divisor_limb <<= normalization_steps;
+
+ n1 = dividend_ptr[dividend_size - 1];
+ r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
+
+ /* Possible optimization:
+ * if (r == 0
+ * && divisor_limb > ((n1 << normalization_steps)
+ * | (dividend_ptr[dividend_size - 2] >> ...)))
+ * ...one division less...
+ */
+ for (i = dividend_size - 2; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ udiv_qrnnd(dummy, r, r,
+ ((n1 << normalization_steps)
+ | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
+ divisor_limb);
+ n1 = n0;
+ }
+ udiv_qrnnd(dummy, r, r,
+ n1 << normalization_steps,
+ divisor_limb);
+ return r >> normalization_steps;
+ }
+ }
+ /* No normalization needed, either because udiv_qrnnd doesn't require
+ * it, or because DIVISOR_LIMB is already normalized.
+ */
+ i = dividend_size - 1;
+ r = dividend_ptr[i];
+
+ if (r >= divisor_limb)
+ r = 0;
+ else
+ i--;
+
+ for (; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ udiv_qrnnd(dummy, r, r, n0, divisor_limb);
+ }
+ return r;
+ }
+}
+
/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
* the NSIZE-DSIZE least significant quotient limbs at QP
* and the DSIZE long remainder at NP. If QEXTRA_LIMBS is
@@ -221,3 +365,153 @@ q_test:
return most_significant_q_limb;
}
+
+/****************
+ * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
+ * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
+ * Return the single-limb remainder.
+ * There are no constraints on the value of the divisor.
+ *
+ * QUOT_PTR and DIVIDEND_PTR might point to the same limb.
+ */
+
+mpi_limb_t
+mpihelp_divmod_1(mpi_ptr_t quot_ptr,
+ mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
+ mpi_limb_t divisor_limb)
+{
+ mpi_size_t i;
+ mpi_limb_t n1, n0, r;
+ mpi_limb_t dummy __maybe_unused;
+
+ if (!dividend_size)
+ return 0;
+
+ /* If multiplication is much faster than division, and the
+ * dividend is large, pre-invert the divisor, and use
+ * only multiplications in the inner loop.
+ *
+ * This test should be read:
+ * Does it ever help to use udiv_qrnnd_preinv?
+ * && Does what we save compensate for the inversion overhead?
+ */
+ if (UDIV_TIME > (2 * UMUL_TIME + 6)
+ && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
+ int normalization_steps;
+
+ normalization_steps = count_leading_zeros(divisor_limb);
+ if (normalization_steps) {
+ mpi_limb_t divisor_limb_inverted;
+
+ divisor_limb <<= normalization_steps;
+
+ /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
+ * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+ * most significant bit (with weight 2**N) implicit.
+ */
+ /* Special case for DIVISOR_LIMB == 100...000. */
+ if (!(divisor_limb << 1))
+ divisor_limb_inverted = ~(mpi_limb_t)0;
+ else
+ udiv_qrnnd(divisor_limb_inverted, dummy,
+ -divisor_limb, 0, divisor_limb);
+
+ n1 = dividend_ptr[dividend_size - 1];
+ r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
+
+ /* Possible optimization:
+ * if (r == 0
+ * && divisor_limb > ((n1 << normalization_steps)
+ * | (dividend_ptr[dividend_size - 2] >> ...)))
+ * ...one division less...
+ */
+ for (i = dividend_size - 2; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ UDIV_QRNND_PREINV(quot_ptr[i + 1], r, r,
+ ((n1 << normalization_steps)
+ | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
+ divisor_limb, divisor_limb_inverted);
+ n1 = n0;
+ }
+ UDIV_QRNND_PREINV(quot_ptr[0], r, r,
+ n1 << normalization_steps,
+ divisor_limb, divisor_limb_inverted);
+ return r >> normalization_steps;
+ } else {
+ mpi_limb_t divisor_limb_inverted;
+
+ /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
+ * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+ * most significant bit (with weight 2**N) implicit.
+ */
+ /* Special case for DIVISOR_LIMB == 100...000. */
+ if (!(divisor_limb << 1))
+ divisor_limb_inverted = ~(mpi_limb_t) 0;
+ else
+ udiv_qrnnd(divisor_limb_inverted, dummy,
+ -divisor_limb, 0, divisor_limb);
+
+ i = dividend_size - 1;
+ r = dividend_ptr[i];
+
+ if (r >= divisor_limb)
+ r = 0;
+ else
+ quot_ptr[i--] = 0;
+
+ for ( ; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ UDIV_QRNND_PREINV(quot_ptr[i], r, r,
+ n0, divisor_limb, divisor_limb_inverted);
+ }
+ return r;
+ }
+ } else {
+ if (UDIV_NEEDS_NORMALIZATION) {
+ int normalization_steps;
+
+ normalization_steps = count_leading_zeros(divisor_limb);
+ if (normalization_steps) {
+ divisor_limb <<= normalization_steps;
+
+ n1 = dividend_ptr[dividend_size - 1];
+ r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
+
+ /* Possible optimization:
+ * if (r == 0
+ * && divisor_limb > ((n1 << normalization_steps)
+ * | (dividend_ptr[dividend_size - 2] >> ...)))
+ * ...one division less...
+ */
+ for (i = dividend_size - 2; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ udiv_qrnnd(quot_ptr[i + 1], r, r,
+ ((n1 << normalization_steps)
+ | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
+ divisor_limb);
+ n1 = n0;
+ }
+ udiv_qrnnd(quot_ptr[0], r, r,
+ n1 << normalization_steps,
+ divisor_limb);
+ return r >> normalization_steps;
+ }
+ }
+ /* No normalization needed, either because udiv_qrnnd doesn't require
+ * it, or because DIVISOR_LIMB is already normalized.
+ */
+ i = dividend_size - 1;
+ r = dividend_ptr[i];
+
+ if (r >= divisor_limb)
+ r = 0;
+ else
+ quot_ptr[i--] = 0;
+
+ for (; i >= 0; i--) {
+ n0 = dividend_ptr[i];
+ udiv_qrnnd(quot_ptr[i], r, r, n0, divisor_limb);
+ }
+ return r;
+ }
+}
diff --git a/lib/mpi/mpih-mul.c b/lib/mpi/mpih-mul.c
index a93647564054..e5f1c84e3c48 100644
--- a/lib/mpi/mpih-mul.c
+++ b/lib/mpi/mpih-mul.c
@@ -317,6 +317,31 @@ 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/mpi/mpiutil.c b/lib/mpi/mpiutil.c
index 4cd2b335cb7f..3c63710c20c6 100644
--- a/lib/mpi/mpiutil.c
+++ b/lib/mpi/mpiutil.c
@@ -20,6 +20,63 @@
#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
@@ -106,6 +163,15 @@ 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)
@@ -122,5 +188,143 @@ void mpi_free(MPI a)
}
EXPORT_SYMBOL_GPL(mpi_free);
+/****************
+ * Note: This copy function should not interpret the MPI
+ * but copy it transparently.
+ */
+MPI mpi_copy(MPI a)
+{
+ int i;
+ MPI b;
+
+ if (a) {
+ b = mpi_alloc(a->nlimbs);
+ b->nlimbs = a->nlimbs;
+ b->sign = a->sign;
+ b->flags = a->flags;
+ b->flags &= ~(16|32); /* Reset the immutable and constant flags. */
+ for (i = 0; i < b->nlimbs; i++)
+ b->d[i] = a->d[i];
+ } else
+ b = NULL;
+ 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 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/percpu-refcount.c b/lib/percpu-refcount.c
index 0ba686b8fe57..e59eda07305e 100644
--- a/lib/percpu-refcount.c
+++ b/lib/percpu-refcount.c
@@ -4,6 +4,7 @@
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/wait.h>
+#include <linux/slab.h>
#include <linux/percpu-refcount.h>
/*
@@ -64,18 +65,25 @@ int percpu_ref_init(struct percpu_ref *ref, percpu_ref_func_t *release,
size_t align = max_t(size_t, 1 << __PERCPU_REF_FLAG_BITS,
__alignof__(unsigned long));
unsigned long start_count = 0;
+ struct percpu_ref_data *data;
ref->percpu_count_ptr = (unsigned long)
__alloc_percpu_gfp(sizeof(unsigned long), align, gfp);
if (!ref->percpu_count_ptr)
return -ENOMEM;
- ref->force_atomic = flags & PERCPU_REF_INIT_ATOMIC;
- ref->allow_reinit = flags & PERCPU_REF_ALLOW_REINIT;
+ data = kzalloc(sizeof(*ref->data), gfp);
+ if (!data) {
+ free_percpu((void __percpu *)ref->percpu_count_ptr);
+ return -ENOMEM;
+ }
+
+ data->force_atomic = flags & PERCPU_REF_INIT_ATOMIC;
+ data->allow_reinit = flags & PERCPU_REF_ALLOW_REINIT;
if (flags & (PERCPU_REF_INIT_ATOMIC | PERCPU_REF_INIT_DEAD)) {
ref->percpu_count_ptr |= __PERCPU_REF_ATOMIC;
- ref->allow_reinit = true;
+ data->allow_reinit = true;
} else {
start_count += PERCPU_COUNT_BIAS;
}
@@ -85,14 +93,28 @@ int percpu_ref_init(struct percpu_ref *ref, percpu_ref_func_t *release,
else
start_count++;
- atomic_long_set(&ref->count, start_count);
+ atomic_long_set(&data->count, start_count);
- ref->release = release;
- ref->confirm_switch = NULL;
+ data->release = release;
+ data->confirm_switch = NULL;
+ data->ref = ref;
+ ref->data = data;
return 0;
}
EXPORT_SYMBOL_GPL(percpu_ref_init);
+static void __percpu_ref_exit(struct percpu_ref *ref)
+{
+ unsigned long __percpu *percpu_count = percpu_count_ptr(ref);
+
+ if (percpu_count) {
+ /* non-NULL confirm_switch indicates switching in progress */
+ WARN_ON_ONCE(ref->data && ref->data->confirm_switch);
+ free_percpu(percpu_count);
+ ref->percpu_count_ptr = __PERCPU_REF_ATOMIC_DEAD;
+ }
+}
+
/**
* percpu_ref_exit - undo percpu_ref_init()
* @ref: percpu_ref to exit
@@ -105,27 +127,36 @@ EXPORT_SYMBOL_GPL(percpu_ref_init);
*/
void percpu_ref_exit(struct percpu_ref *ref)
{
- unsigned long __percpu *percpu_count = percpu_count_ptr(ref);
+ struct percpu_ref_data *data = ref->data;
+ unsigned long flags;
- if (percpu_count) {
- /* non-NULL confirm_switch indicates switching in progress */
- WARN_ON_ONCE(ref->confirm_switch);
- free_percpu(percpu_count);
- ref->percpu_count_ptr = __PERCPU_REF_ATOMIC_DEAD;
- }
+ __percpu_ref_exit(ref);
+
+ if (!data)
+ return;
+
+ spin_lock_irqsave(&percpu_ref_switch_lock, flags);
+ ref->percpu_count_ptr |= atomic_long_read(&ref->data->count) <<
+ __PERCPU_REF_FLAG_BITS;
+ ref->data = NULL;
+ spin_unlock_irqrestore(&percpu_ref_switch_lock, flags);
+
+ kfree(data);
}
EXPORT_SYMBOL_GPL(percpu_ref_exit);
static void percpu_ref_call_confirm_rcu(struct rcu_head *rcu)
{
- struct percpu_ref *ref = container_of(rcu, struct percpu_ref, rcu);
+ struct percpu_ref_data *data = container_of(rcu,
+ struct percpu_ref_data, rcu);
+ struct percpu_ref *ref = data->ref;
- ref->confirm_switch(ref);
- ref->confirm_switch = NULL;
+ data->confirm_switch(ref);
+ data->confirm_switch = NULL;
wake_up_all(&percpu_ref_switch_waitq);
- if (!ref->allow_reinit)
- percpu_ref_exit(ref);
+ if (!data->allow_reinit)
+ __percpu_ref_exit(ref);
/* drop ref from percpu_ref_switch_to_atomic() */
percpu_ref_put(ref);
@@ -133,7 +164,9 @@ static void percpu_ref_call_confirm_rcu(struct rcu_head *rcu)
static void percpu_ref_switch_to_atomic_rcu(struct rcu_head *rcu)
{
- struct percpu_ref *ref = container_of(rcu, struct percpu_ref, rcu);
+ struct percpu_ref_data *data = container_of(rcu,
+ struct percpu_ref_data, rcu);
+ struct percpu_ref *ref = data->ref;
unsigned long __percpu *percpu_count = percpu_count_ptr(ref);
unsigned long count = 0;
int cpu;
@@ -142,7 +175,7 @@ static void percpu_ref_switch_to_atomic_rcu(struct rcu_head *rcu)
count += *per_cpu_ptr(percpu_count, cpu);
pr_debug("global %lu percpu %lu\n",
- atomic_long_read(&ref->count), count);
+ atomic_long_read(&data->count), count);
/*
* It's crucial that we sum the percpu counters _before_ adding the sum
@@ -156,11 +189,11 @@ static void percpu_ref_switch_to_atomic_rcu(struct rcu_head *rcu)
* reaching 0 before we add the percpu counts. But doing it at the same
* time is equivalent and saves us atomic operations:
*/
- atomic_long_add((long)count - PERCPU_COUNT_BIAS, &ref->count);
+ atomic_long_add((long)count - PERCPU_COUNT_BIAS, &data->count);
- WARN_ONCE(atomic_long_read(&ref->count) <= 0,
+ WARN_ONCE(atomic_long_read(&data->count) <= 0,
"percpu ref (%ps) <= 0 (%ld) after switching to atomic",
- ref->release, atomic_long_read(&ref->count));
+ data->release, atomic_long_read(&data->count));
/* @ref is viewed as dead on all CPUs, send out switch confirmation */
percpu_ref_call_confirm_rcu(rcu);
@@ -186,10 +219,11 @@ static void __percpu_ref_switch_to_atomic(struct percpu_ref *ref,
* Non-NULL ->confirm_switch is used to indicate that switching is
* in progress. Use noop one if unspecified.
*/
- ref->confirm_switch = confirm_switch ?: percpu_ref_noop_confirm_switch;
+ ref->data->confirm_switch = confirm_switch ?:
+ percpu_ref_noop_confirm_switch;
percpu_ref_get(ref); /* put after confirmation */
- call_rcu(&ref->rcu, percpu_ref_switch_to_atomic_rcu);
+ call_rcu(&ref->data->rcu, percpu_ref_switch_to_atomic_rcu);
}
static void __percpu_ref_switch_to_percpu(struct percpu_ref *ref)
@@ -202,10 +236,10 @@ static void __percpu_ref_switch_to_percpu(struct percpu_ref *ref)
if (!(ref->percpu_count_ptr & __PERCPU_REF_ATOMIC))
return;
- if (WARN_ON_ONCE(!ref->allow_reinit))
+ if (WARN_ON_ONCE(!ref->data->allow_reinit))
return;
- atomic_long_add(PERCPU_COUNT_BIAS, &ref->count);
+ atomic_long_add(PERCPU_COUNT_BIAS, &ref->data->count);
/*
* Restore per-cpu operation. smp_store_release() is paired
@@ -223,6 +257,8 @@ static void __percpu_ref_switch_to_percpu(struct percpu_ref *ref)
static void __percpu_ref_switch_mode(struct percpu_ref *ref,
percpu_ref_func_t *confirm_switch)
{
+ struct percpu_ref_data *data = ref->data;
+
lockdep_assert_held(&percpu_ref_switch_lock);
/*
@@ -230,10 +266,10 @@ static void __percpu_ref_switch_mode(struct percpu_ref *ref,
* its completion. If the caller ensures that ATOMIC switching
* isn't in progress, this function can be called from any context.
*/
- wait_event_lock_irq(percpu_ref_switch_waitq, !ref->confirm_switch,
+ wait_event_lock_irq(percpu_ref_switch_waitq, !data->confirm_switch,
percpu_ref_switch_lock);
- if (ref->force_atomic || (ref->percpu_count_ptr & __PERCPU_REF_DEAD))
+ if (data->force_atomic || (ref->percpu_count_ptr & __PERCPU_REF_DEAD))
__percpu_ref_switch_to_atomic(ref, confirm_switch);
else
__percpu_ref_switch_to_percpu(ref);
@@ -266,7 +302,7 @@ void percpu_ref_switch_to_atomic(struct percpu_ref *ref,
spin_lock_irqsave(&percpu_ref_switch_lock, flags);
- ref->force_atomic = true;
+ ref->data->force_atomic = true;
__percpu_ref_switch_mode(ref, confirm_switch);
spin_unlock_irqrestore(&percpu_ref_switch_lock, flags);
@@ -284,7 +320,7 @@ EXPORT_SYMBOL_GPL(percpu_ref_switch_to_atomic);
void percpu_ref_switch_to_atomic_sync(struct percpu_ref *ref)
{
percpu_ref_switch_to_atomic(ref, NULL);
- wait_event(percpu_ref_switch_waitq, !ref->confirm_switch);
+ wait_event(percpu_ref_switch_waitq, !ref->data->confirm_switch);
}
EXPORT_SYMBOL_GPL(percpu_ref_switch_to_atomic_sync);
@@ -312,7 +348,7 @@ void percpu_ref_switch_to_percpu(struct percpu_ref *ref)
spin_lock_irqsave(&percpu_ref_switch_lock, flags);
- ref->force_atomic = false;
+ ref->data->force_atomic = false;
__percpu_ref_switch_mode(ref, NULL);
spin_unlock_irqrestore(&percpu_ref_switch_lock, flags);
@@ -344,7 +380,8 @@ void percpu_ref_kill_and_confirm(struct percpu_ref *ref,
spin_lock_irqsave(&percpu_ref_switch_lock, flags);
WARN_ONCE(ref->percpu_count_ptr & __PERCPU_REF_DEAD,
- "%s called more than once on %ps!", __func__, ref->release);
+ "%s called more than once on %ps!", __func__,
+ ref->data->release);
ref->percpu_count_ptr |= __PERCPU_REF_DEAD;
__percpu_ref_switch_mode(ref, confirm_kill);
@@ -355,6 +392,34 @@ void percpu_ref_kill_and_confirm(struct percpu_ref *ref,
EXPORT_SYMBOL_GPL(percpu_ref_kill_and_confirm);
/**
+ * percpu_ref_is_zero - test whether a percpu refcount reached zero
+ * @ref: percpu_ref to test
+ *
+ * Returns %true if @ref reached zero.
+ *
+ * This function is safe to call as long as @ref is between init and exit.
+ */
+bool percpu_ref_is_zero(struct percpu_ref *ref)
+{
+ unsigned long __percpu *percpu_count;
+ unsigned long count, flags;
+
+ if (__ref_is_percpu(ref, &percpu_count))
+ return false;
+
+ /* protect us from being destroyed */
+ spin_lock_irqsave(&percpu_ref_switch_lock, flags);
+ if (ref->data)
+ count = atomic_long_read(&ref->data->count);
+ else
+ count = ref->percpu_count_ptr >> __PERCPU_REF_FLAG_BITS;
+ spin_unlock_irqrestore(&percpu_ref_switch_lock, flags);
+
+ return count == 0;
+}
+EXPORT_SYMBOL_GPL(percpu_ref_is_zero);
+
+/**
* percpu_ref_reinit - re-initialize a percpu refcount
* @ref: perpcu_ref to re-initialize
*
diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c
index a2345de90e93..f61689a96e85 100644
--- a/lib/percpu_counter.c
+++ b/lib/percpu_counter.c
@@ -17,7 +17,7 @@ static DEFINE_SPINLOCK(percpu_counters_lock);
#ifdef CONFIG_DEBUG_OBJECTS_PERCPU_COUNTER
-static struct debug_obj_descr percpu_counter_debug_descr;
+static const struct debug_obj_descr percpu_counter_debug_descr;
static bool percpu_counter_fixup_free(void *addr, enum debug_obj_state state)
{
@@ -33,7 +33,7 @@ static bool percpu_counter_fixup_free(void *addr, enum debug_obj_state state)
}
}
-static struct debug_obj_descr percpu_counter_debug_descr = {
+static const struct debug_obj_descr percpu_counter_debug_descr = {
.name = "percpu_counter",
.fixup_free = percpu_counter_fixup_free,
};
diff --git a/lib/random32.c b/lib/random32.c
index 932345323af0..dfb9981ab798 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -49,7 +49,7 @@ static inline void prandom_state_selftest(void)
}
#endif
-DEFINE_PER_CPU(struct rnd_state, net_rand_state);
+DEFINE_PER_CPU(struct rnd_state, net_rand_state) __latent_entropy;
/**
* prandom_u32_state - seeded pseudo-random number generator.
diff --git a/lib/string.c b/lib/string.c
index 6012c385fb31..4288e0158d47 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -272,6 +272,30 @@ ssize_t strscpy_pad(char *dest, const char *src, size_t count)
}
EXPORT_SYMBOL(strscpy_pad);
+/**
+ * stpcpy - copy a string from src to dest returning a pointer to the new end
+ * of dest, including src's %NUL-terminator. May overrun dest.
+ * @dest: pointer to end of string being copied into. Must be large enough
+ * to receive copy.
+ * @src: pointer to the beginning of string being copied from. Must not overlap
+ * dest.
+ *
+ * stpcpy differs from strcpy in a key way: the return value is a pointer
+ * to the new %NUL-terminating character in @dest. (For strcpy, the return
+ * value is a pointer to the start of @dest). This interface is considered
+ * unsafe as it doesn't perform bounds checking of the inputs. As such it's
+ * not recommended for usage. Instead, its definition is provided in case
+ * the compiler lowers other libcalls to stpcpy.
+ */
+char *stpcpy(char *__restrict__ dest, const char *__restrict__ src);
+char *stpcpy(char *__restrict__ dest, const char *__restrict__ src)
+{
+ while ((*dest++ = *src++) != '\0')
+ /* nothing */;
+ return --dest;
+}
+EXPORT_SYMBOL(stpcpy);
+
#ifndef __HAVE_ARCH_STRCAT
/**
* strcat - Append one %NUL-terminated string to another
diff --git a/lib/string_helpers.c b/lib/string_helpers.c
index 963050c0283e..7f2d5fbaf243 100644
--- a/lib/string_helpers.c
+++ b/lib/string_helpers.c
@@ -649,3 +649,26 @@ char *kstrdup_quotable_file(struct file *file, gfp_t gfp)
return pathname;
}
EXPORT_SYMBOL_GPL(kstrdup_quotable_file);
+
+/**
+ * kfree_strarray - free a number of dynamically allocated strings contained
+ * in an array and the array itself
+ *
+ * @array: Dynamically allocated array of strings to free.
+ * @n: Number of strings (starting from the beginning of the array) to free.
+ *
+ * Passing a non-NULL @array and @n == 0 as well as NULL @array are valid
+ * use-cases. If @array is NULL, the function does nothing.
+ */
+void kfree_strarray(char **array, size_t n)
+{
+ unsigned int i;
+
+ if (!array)
+ return;
+
+ for (i = 0; i < n; i++)
+ kfree(array[i]);
+ kfree(array);
+}
+EXPORT_SYMBOL_GPL(kfree_strarray);
diff --git a/lib/test_free_pages.c b/lib/test_free_pages.c
new file mode 100644
index 000000000000..074e76bd76b2
--- /dev/null
+++ b/lib/test_free_pages.c
@@ -0,0 +1,42 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * test_free_pages.c: Check that free_pages() doesn't leak memory
+ * Copyright (c) 2020 Oracle
+ * Author: Matthew Wilcox <willy@infradead.org>
+ */
+
+#include <linux/gfp.h>
+#include <linux/mm.h>
+#include <linux/module.h>
+
+static void test_free_pages(gfp_t gfp)
+{
+ unsigned int i;
+
+ for (i = 0; i < 1000 * 1000; i++) {
+ unsigned long addr = __get_free_pages(gfp, 3);
+ struct page *page = virt_to_page(addr);
+
+ /* Simulate page cache getting a speculative reference */
+ get_page(page);
+ free_pages(addr, 3);
+ put_page(page);
+ }
+}
+
+static int m_in(void)
+{
+ test_free_pages(GFP_KERNEL);
+ test_free_pages(GFP_KERNEL | __GFP_COMP);
+
+ return 0;
+}
+
+static void m_ex(void)
+{
+}
+
+module_init(m_in);
+module_exit(m_ex);
+MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
+MODULE_LICENSE("GPL");
diff --git a/lib/test_hmm.c b/lib/test_hmm.c
index e7dc3de355b7..e151a7f10519 100644
--- a/lib/test_hmm.c
+++ b/lib/test_hmm.c
@@ -36,7 +36,6 @@
static const struct dev_pagemap_ops dmirror_devmem_ops;
static const struct mmu_interval_notifier_ops dmirror_min_ops;
static dev_t dmirror_dev;
-static struct page *dmirror_zero_page;
struct dmirror_device;
@@ -460,6 +459,22 @@ static bool dmirror_allocate_chunk(struct dmirror_device *mdevice,
unsigned long pfn_last;
void *ptr;
+ devmem = kzalloc(sizeof(*devmem), GFP_KERNEL);
+ if (!devmem)
+ return -ENOMEM;
+
+ res = request_free_mem_region(&iomem_resource, DEVMEM_CHUNK_SIZE,
+ "hmm_dmirror");
+ if (IS_ERR(res))
+ goto err_devmem;
+
+ devmem->pagemap.type = MEMORY_DEVICE_PRIVATE;
+ devmem->pagemap.range.start = res->start;
+ devmem->pagemap.range.end = res->end;
+ devmem->pagemap.nr_range = 1;
+ devmem->pagemap.ops = &dmirror_devmem_ops;
+ devmem->pagemap.owner = mdevice;
+
mutex_lock(&mdevice->devmem_lock);
if (mdevice->devmem_count == mdevice->devmem_capacity) {
@@ -472,33 +487,18 @@ static bool dmirror_allocate_chunk(struct dmirror_device *mdevice,
sizeof(new_chunks[0]) * new_capacity,
GFP_KERNEL);
if (!new_chunks)
- goto err;
+ goto err_release;
mdevice->devmem_capacity = new_capacity;
mdevice->devmem_chunks = new_chunks;
}
- res = request_free_mem_region(&iomem_resource, DEVMEM_CHUNK_SIZE,
- "hmm_dmirror");
- if (IS_ERR(res))
- goto err;
-
- devmem = kzalloc(sizeof(*devmem), GFP_KERNEL);
- if (!devmem)
- goto err_release;
-
- devmem->pagemap.type = MEMORY_DEVICE_PRIVATE;
- devmem->pagemap.res = *res;
- devmem->pagemap.ops = &dmirror_devmem_ops;
- devmem->pagemap.owner = mdevice;
-
ptr = memremap_pages(&devmem->pagemap, numa_node_id());
if (IS_ERR(ptr))
- goto err_free;
+ goto err_release;
devmem->mdevice = mdevice;
- pfn_first = devmem->pagemap.res.start >> PAGE_SHIFT;
- pfn_last = pfn_first +
- (resource_size(&devmem->pagemap.res) >> PAGE_SHIFT);
+ pfn_first = devmem->pagemap.range.start >> PAGE_SHIFT;
+ pfn_last = pfn_first + (range_len(&devmem->pagemap.range) >> PAGE_SHIFT);
mdevice->devmem_chunks[mdevice->devmem_count++] = devmem;
mutex_unlock(&mdevice->devmem_lock);
@@ -525,12 +525,12 @@ static bool dmirror_allocate_chunk(struct dmirror_device *mdevice,
return true;
-err_free:
- kfree(devmem);
err_release:
- release_mem_region(res->start, resource_size(res));
-err:
mutex_unlock(&mdevice->devmem_lock);
+ release_mem_region(devmem->pagemap.range.start, range_len(&devmem->pagemap.range));
+err_devmem:
+ kfree(devmem);
+
return false;
}
@@ -1100,8 +1100,8 @@ static void dmirror_device_remove(struct dmirror_device *mdevice)
mdevice->devmem_chunks[i];
memunmap_pages(&devmem->pagemap);
- release_mem_region(devmem->pagemap.res.start,
- resource_size(&devmem->pagemap.res));
+ release_mem_region(devmem->pagemap.range.start,
+ range_len(&devmem->pagemap.range));
kfree(devmem);
}
kfree(mdevice->devmem_chunks);
@@ -1126,17 +1126,6 @@ static int __init hmm_dmirror_init(void)
goto err_chrdev;
}
- /*
- * Allocate a zero page to simulate a reserved page of device private
- * memory which is always zero. The zero_pfn page isn't used just to
- * make the code here simpler (i.e., we need a struct page for it).
- */
- dmirror_zero_page = alloc_page(GFP_HIGHUSER | __GFP_ZERO);
- if (!dmirror_zero_page) {
- ret = -ENOMEM;
- goto err_chrdev;
- }
-
pr_info("HMM test module loaded. This is only for testing HMM.\n");
return 0;
@@ -1152,8 +1141,6 @@ static void __exit hmm_dmirror_exit(void)
{
int id;
- if (dmirror_zero_page)
- __free_page(dmirror_zero_page);
for (id = 0; id < DMIRROR_NDEVICES; id++)
dmirror_device_remove(dmirror_devices + id);
unregister_chrdev_region(dmirror_dev, DMIRROR_NDEVICES);
diff --git a/lib/test_kasan.c b/lib/test_kasan.c
index 53e953bb1d1d..63c26171a791 100644
--- a/lib/test_kasan.c
+++ b/lib/test_kasan.c
@@ -5,8 +5,6 @@
* Author: Andrey Ryabinin <a.ryabinin@samsung.com>
*/
-#define pr_fmt(fmt) "kasan test: %s " fmt, __func__
-
#include <linux/bitops.h>
#include <linux/delay.h>
#include <linux/kasan.h>
@@ -23,6 +21,8 @@
#include <asm/page.h>
+#include <kunit/test.h>
+
#include "../mm/kasan/kasan.h"
#define OOB_TAG_OFF (IS_ENABLED(CONFIG_KASAN_GENERIC) ? 0 : KASAN_SHADOW_SCALE_SIZE)
@@ -32,418 +32,370 @@
* are not eliminated as dead code.
*/
-int kasan_int_result;
void *kasan_ptr_result;
+int kasan_int_result;
-/*
- * Note: test functions are marked noinline so that their names appear in
- * reports.
- */
+static struct kunit_resource resource;
+static struct kunit_kasan_expectation fail_data;
+static bool multishot;
-static noinline void __init kmalloc_oob_right(void)
+static int kasan_test_init(struct kunit *test)
+{
+ /*
+ * Temporarily enable multi-shot mode and set panic_on_warn=0.
+ * Otherwise, we'd only get a report for the first case.
+ */
+ multishot = kasan_save_enable_multi_shot();
+
+ return 0;
+}
+
+static void kasan_test_exit(struct kunit *test)
+{
+ kasan_restore_multi_shot(multishot);
+}
+
+/**
+ * KUNIT_EXPECT_KASAN_FAIL() - Causes a test failure when the expression does
+ * not cause a KASAN error. This uses a KUnit resource named "kasan_data." Do
+ * Do not use this name for a KUnit resource outside here.
+ *
+ */
+#define KUNIT_EXPECT_KASAN_FAIL(test, condition) do { \
+ fail_data.report_expected = true; \
+ fail_data.report_found = false; \
+ kunit_add_named_resource(test, \
+ NULL, \
+ NULL, \
+ &resource, \
+ "kasan_data", &fail_data); \
+ condition; \
+ KUNIT_EXPECT_EQ(test, \
+ fail_data.report_expected, \
+ fail_data.report_found); \
+} while (0)
+
+static void kmalloc_oob_right(struct kunit *test)
{
char *ptr;
size_t size = 123;
- pr_info("out-of-bounds to right\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- ptr[size + OOB_TAG_OFF] = 'x';
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr[size + OOB_TAG_OFF] = 'x');
kfree(ptr);
}
-static noinline void __init kmalloc_oob_left(void)
+static void kmalloc_oob_left(struct kunit *test)
{
char *ptr;
size_t size = 15;
- pr_info("out-of-bounds to left\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
- *ptr = *(ptr - 1);
+ KUNIT_EXPECT_KASAN_FAIL(test, *ptr = *(ptr - 1));
kfree(ptr);
}
-static noinline void __init kmalloc_node_oob_right(void)
+static void kmalloc_node_oob_right(struct kunit *test)
{
char *ptr;
size_t size = 4096;
- pr_info("kmalloc_node(): out-of-bounds to right\n");
ptr = kmalloc_node(size, GFP_KERNEL, 0);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
- ptr[size] = 0;
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr[size] = 0);
kfree(ptr);
}
-#ifdef CONFIG_SLUB
-static noinline void __init kmalloc_pagealloc_oob_right(void)
+static void kmalloc_pagealloc_oob_right(struct kunit *test)
{
char *ptr;
size_t size = KMALLOC_MAX_CACHE_SIZE + 10;
+ if (!IS_ENABLED(CONFIG_SLUB)) {
+ kunit_info(test, "CONFIG_SLUB is not enabled.");
+ return;
+ }
+
/* Allocate a chunk that does not fit into a SLUB cache to trigger
* the page allocator fallback.
*/
- pr_info("kmalloc pagealloc allocation: out-of-bounds to right\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- ptr[size + OOB_TAG_OFF] = 0;
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr[size + OOB_TAG_OFF] = 0);
kfree(ptr);
}
-static noinline void __init kmalloc_pagealloc_uaf(void)
+static void kmalloc_pagealloc_uaf(struct kunit *test)
{
char *ptr;
size_t size = KMALLOC_MAX_CACHE_SIZE + 10;
- pr_info("kmalloc pagealloc allocation: use-after-free\n");
- ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
+ if (!IS_ENABLED(CONFIG_SLUB)) {
+ kunit_info(test, "CONFIG_SLUB is not enabled.");
return;
}
+ ptr = kmalloc(size, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+
kfree(ptr);
- ptr[0] = 0;
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr[0] = 0);
}
-static noinline void __init kmalloc_pagealloc_invalid_free(void)
+static void kmalloc_pagealloc_invalid_free(struct kunit *test)
{
char *ptr;
size_t size = KMALLOC_MAX_CACHE_SIZE + 10;
- pr_info("kmalloc pagealloc allocation: invalid-free\n");
- ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
+ if (!IS_ENABLED(CONFIG_SLUB)) {
+ kunit_info(test, "CONFIG_SLUB is not enabled.");
return;
}
- kfree(ptr + 1);
+ ptr = kmalloc(size, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+
+ KUNIT_EXPECT_KASAN_FAIL(test, kfree(ptr + 1));
}
-#endif
-static noinline void __init kmalloc_large_oob_right(void)
+static void kmalloc_large_oob_right(struct kunit *test)
{
char *ptr;
size_t size = KMALLOC_MAX_CACHE_SIZE - 256;
/* Allocate a chunk that is large enough, but still fits into a slab
* and does not trigger the page allocator fallback in SLUB.
*/
- pr_info("kmalloc large allocation: out-of-bounds to right\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
- ptr[size] = 0;
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr[size] = 0);
kfree(ptr);
}
-static noinline void __init kmalloc_oob_krealloc_more(void)
+static void kmalloc_oob_krealloc_more(struct kunit *test)
{
char *ptr1, *ptr2;
size_t size1 = 17;
size_t size2 = 19;
- pr_info("out-of-bounds after krealloc more\n");
ptr1 = kmalloc(size1, GFP_KERNEL);
- ptr2 = krealloc(ptr1, size2, GFP_KERNEL);
- if (!ptr1 || !ptr2) {
- pr_err("Allocation failed\n");
- kfree(ptr1);
- kfree(ptr2);
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr1);
- ptr2[size2 + OOB_TAG_OFF] = 'x';
+ ptr2 = krealloc(ptr1, size2, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr2);
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr2[size2 + OOB_TAG_OFF] = 'x');
kfree(ptr2);
}
-static noinline void __init kmalloc_oob_krealloc_less(void)
+static void kmalloc_oob_krealloc_less(struct kunit *test)
{
char *ptr1, *ptr2;
size_t size1 = 17;
size_t size2 = 15;
- pr_info("out-of-bounds after krealloc less\n");
ptr1 = kmalloc(size1, GFP_KERNEL);
- ptr2 = krealloc(ptr1, size2, GFP_KERNEL);
- if (!ptr1 || !ptr2) {
- pr_err("Allocation failed\n");
- kfree(ptr1);
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr1);
- ptr2[size2 + OOB_TAG_OFF] = 'x';
+ ptr2 = krealloc(ptr1, size2, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr2);
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr2[size2 + OOB_TAG_OFF] = 'x');
kfree(ptr2);
}
-static noinline void __init kmalloc_oob_16(void)
+static void kmalloc_oob_16(struct kunit *test)
{
struct {
u64 words[2];
} *ptr1, *ptr2;
- pr_info("kmalloc out-of-bounds for 16-bytes access\n");
ptr1 = kmalloc(sizeof(*ptr1) - 3, GFP_KERNEL);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr1);
+
ptr2 = kmalloc(sizeof(*ptr2), GFP_KERNEL);
- if (!ptr1 || !ptr2) {
- pr_err("Allocation failed\n");
- kfree(ptr1);
- kfree(ptr2);
- return;
- }
- *ptr1 = *ptr2;
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr2);
+
+ KUNIT_EXPECT_KASAN_FAIL(test, *ptr1 = *ptr2);
kfree(ptr1);
kfree(ptr2);
}
-static noinline void __init kmalloc_oob_memset_2(void)
+static void kmalloc_oob_memset_2(struct kunit *test)
{
char *ptr;
size_t size = 8;
- pr_info("out-of-bounds in memset2\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- memset(ptr + 7 + OOB_TAG_OFF, 0, 2);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, memset(ptr + 7 + OOB_TAG_OFF, 0, 2));
kfree(ptr);
}
-static noinline void __init kmalloc_oob_memset_4(void)
+static void kmalloc_oob_memset_4(struct kunit *test)
{
char *ptr;
size_t size = 8;
- pr_info("out-of-bounds in memset4\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- memset(ptr + 5 + OOB_TAG_OFF, 0, 4);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, memset(ptr + 5 + OOB_TAG_OFF, 0, 4));
kfree(ptr);
}
-static noinline void __init kmalloc_oob_memset_8(void)
+static void kmalloc_oob_memset_8(struct kunit *test)
{
char *ptr;
size_t size = 8;
- pr_info("out-of-bounds in memset8\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- memset(ptr + 1 + OOB_TAG_OFF, 0, 8);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, memset(ptr + 1 + OOB_TAG_OFF, 0, 8));
kfree(ptr);
}
-static noinline void __init kmalloc_oob_memset_16(void)
+static void kmalloc_oob_memset_16(struct kunit *test)
{
char *ptr;
size_t size = 16;
- pr_info("out-of-bounds in memset16\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- memset(ptr + 1 + OOB_TAG_OFF, 0, 16);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, memset(ptr + 1 + OOB_TAG_OFF, 0, 16));
kfree(ptr);
}
-static noinline void __init kmalloc_oob_in_memset(void)
+static void kmalloc_oob_in_memset(struct kunit *test)
{
char *ptr;
size_t size = 666;
- pr_info("out-of-bounds in memset\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- memset(ptr, 0, size + 5 + OOB_TAG_OFF);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, memset(ptr, 0, size + 5 + OOB_TAG_OFF));
kfree(ptr);
}
-static noinline void __init kmalloc_memmove_invalid_size(void)
+static void kmalloc_memmove_invalid_size(struct kunit *test)
{
char *ptr;
size_t size = 64;
volatile size_t invalid_size = -2;
- pr_info("invalid size in memmove\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
memset((char *)ptr, 0, 64);
- memmove((char *)ptr, (char *)ptr + 4, invalid_size);
+
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ memmove((char *)ptr, (char *)ptr + 4, invalid_size));
kfree(ptr);
}
-static noinline void __init kmalloc_uaf(void)
+static void kmalloc_uaf(struct kunit *test)
{
char *ptr;
size_t size = 10;
- pr_info("use-after-free\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
kfree(ptr);
- *(ptr + 8) = 'x';
+ KUNIT_EXPECT_KASAN_FAIL(test, *(ptr + 8) = 'x');
}
-static noinline void __init kmalloc_uaf_memset(void)
+static void kmalloc_uaf_memset(struct kunit *test)
{
char *ptr;
size_t size = 33;
- pr_info("use-after-free in memset\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
kfree(ptr);
- memset(ptr, 0, size);
+ KUNIT_EXPECT_KASAN_FAIL(test, memset(ptr, 0, size));
}
-static noinline void __init kmalloc_uaf2(void)
+static void kmalloc_uaf2(struct kunit *test)
{
char *ptr1, *ptr2;
size_t size = 43;
- pr_info("use-after-free after another kmalloc\n");
ptr1 = kmalloc(size, GFP_KERNEL);
- if (!ptr1) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr1);
kfree(ptr1);
+
ptr2 = kmalloc(size, GFP_KERNEL);
- if (!ptr2) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr2);
+
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr1[40] = 'x');
+ KUNIT_EXPECT_PTR_NE(test, ptr1, ptr2);
- ptr1[40] = 'x';
- if (ptr1 == ptr2)
- pr_err("Could not detect use-after-free: ptr1 == ptr2\n");
kfree(ptr2);
}
-static noinline void __init kfree_via_page(void)
+static void kfree_via_page(struct kunit *test)
{
char *ptr;
size_t size = 8;
struct page *page;
unsigned long offset;
- pr_info("invalid-free false positive (via page)\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
page = virt_to_page(ptr);
offset = offset_in_page(ptr);
kfree(page_address(page) + offset);
}
-static noinline void __init kfree_via_phys(void)
+static void kfree_via_phys(struct kunit *test)
{
char *ptr;
size_t size = 8;
phys_addr_t phys;
- pr_info("invalid-free false positive (via phys)\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
phys = virt_to_phys(ptr);
kfree(phys_to_virt(phys));
}
-static noinline void __init kmem_cache_oob(void)
+static void kmem_cache_oob(struct kunit *test)
{
char *p;
size_t size = 200;
struct kmem_cache *cache = kmem_cache_create("test_cache",
size, 0,
0, NULL);
- if (!cache) {
- pr_err("Cache allocation failed\n");
- return;
- }
- pr_info("out-of-bounds in kmem_cache_alloc\n");
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, cache);
p = kmem_cache_alloc(cache, GFP_KERNEL);
if (!p) {
- pr_err("Allocation failed\n");
+ kunit_err(test, "Allocation failed: %s\n", __func__);
kmem_cache_destroy(cache);
return;
}
- *p = p[size + OOB_TAG_OFF];
-
+ KUNIT_EXPECT_KASAN_FAIL(test, *p = p[size + OOB_TAG_OFF]);
kmem_cache_free(cache, p);
kmem_cache_destroy(cache);
}
-static noinline void __init memcg_accounted_kmem_cache(void)
+static void memcg_accounted_kmem_cache(struct kunit *test)
{
int i;
char *p;
@@ -451,12 +403,8 @@ static noinline void __init memcg_accounted_kmem_cache(void)
struct kmem_cache *cache;
cache = kmem_cache_create("test_cache", size, 0, SLAB_ACCOUNT, NULL);
- if (!cache) {
- pr_err("Cache allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, cache);
- pr_info("allocate memcg accounted object\n");
/*
* Several allocations with a delay to allow for lazy per memcg kmem
* cache creation.
@@ -476,134 +424,93 @@ free_cache:
static char global_array[10];
-static noinline void __init kasan_global_oob(void)
+static void kasan_global_oob(struct kunit *test)
{
volatile int i = 3;
char *p = &global_array[ARRAY_SIZE(global_array) + i];
- pr_info("out-of-bounds global variable\n");
- *(volatile char *)p;
+ KUNIT_EXPECT_KASAN_FAIL(test, *(volatile char *)p);
}
-static noinline void __init kasan_stack_oob(void)
-{
- char stack_array[10];
- volatile int i = OOB_TAG_OFF;
- char *p = &stack_array[ARRAY_SIZE(stack_array) + i];
-
- pr_info("out-of-bounds on stack\n");
- *(volatile char *)p;
-}
-
-static noinline void __init ksize_unpoisons_memory(void)
+static void ksize_unpoisons_memory(struct kunit *test)
{
char *ptr;
size_t size = 123, real_size;
- pr_info("ksize() unpoisons the whole allocated chunk\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
real_size = ksize(ptr);
/* This access doesn't trigger an error. */
ptr[size] = 'x';
/* This one does. */
- ptr[real_size] = 'y';
+ KUNIT_EXPECT_KASAN_FAIL(test, ptr[real_size] = 'y');
kfree(ptr);
}
-static noinline void __init copy_user_test(void)
+static void kasan_stack_oob(struct kunit *test)
{
- char *kmem;
- char __user *usermem;
- size_t size = 10;
- int unused;
-
- kmem = kmalloc(size, GFP_KERNEL);
- if (!kmem)
- return;
+ char stack_array[10];
+ volatile int i = OOB_TAG_OFF;
+ char *p = &stack_array[ARRAY_SIZE(stack_array) + i];
- usermem = (char __user *)vm_mmap(NULL, 0, PAGE_SIZE,
- PROT_READ | PROT_WRITE | PROT_EXEC,
- MAP_ANONYMOUS | MAP_PRIVATE, 0);
- if (IS_ERR(usermem)) {
- pr_err("Failed to allocate user memory\n");
- kfree(kmem);
+ if (!IS_ENABLED(CONFIG_KASAN_STACK)) {
+ kunit_info(test, "CONFIG_KASAN_STACK is not enabled");
return;
}
- pr_info("out-of-bounds in copy_from_user()\n");
- unused = copy_from_user(kmem, usermem, size + 1 + OOB_TAG_OFF);
-
- pr_info("out-of-bounds in copy_to_user()\n");
- unused = copy_to_user(usermem, kmem, size + 1 + OOB_TAG_OFF);
-
- pr_info("out-of-bounds in __copy_from_user()\n");
- unused = __copy_from_user(kmem, usermem, size + 1 + OOB_TAG_OFF);
-
- pr_info("out-of-bounds in __copy_to_user()\n");
- unused = __copy_to_user(usermem, kmem, size + 1 + OOB_TAG_OFF);
-
- pr_info("out-of-bounds in __copy_from_user_inatomic()\n");
- unused = __copy_from_user_inatomic(kmem, usermem, size + 1 + OOB_TAG_OFF);
-
- pr_info("out-of-bounds in __copy_to_user_inatomic()\n");
- unused = __copy_to_user_inatomic(usermem, kmem, size + 1 + OOB_TAG_OFF);
-
- pr_info("out-of-bounds in strncpy_from_user()\n");
- unused = strncpy_from_user(kmem, usermem, size + 1 + OOB_TAG_OFF);
-
- vm_munmap((unsigned long)usermem, PAGE_SIZE);
- kfree(kmem);
+ KUNIT_EXPECT_KASAN_FAIL(test, *(volatile char *)p);
}
-static noinline void __init kasan_alloca_oob_left(void)
+static void kasan_alloca_oob_left(struct kunit *test)
{
volatile int i = 10;
char alloca_array[i];
char *p = alloca_array - 1;
- pr_info("out-of-bounds to left on alloca\n");
- *(volatile char *)p;
+ if (!IS_ENABLED(CONFIG_KASAN_STACK)) {
+ kunit_info(test, "CONFIG_KASAN_STACK is not enabled");
+ return;
+ }
+
+ KUNIT_EXPECT_KASAN_FAIL(test, *(volatile char *)p);
}
-static noinline void __init kasan_alloca_oob_right(void)
+static void kasan_alloca_oob_right(struct kunit *test)
{
volatile int i = 10;
char alloca_array[i];
char *p = alloca_array + i;
- pr_info("out-of-bounds to right on alloca\n");
- *(volatile char *)p;
+ if (!IS_ENABLED(CONFIG_KASAN_STACK)) {
+ kunit_info(test, "CONFIG_KASAN_STACK is not enabled");
+ return;
+ }
+
+ KUNIT_EXPECT_KASAN_FAIL(test, *(volatile char *)p);
}
-static noinline void __init kmem_cache_double_free(void)
+static void kmem_cache_double_free(struct kunit *test)
{
char *p;
size_t size = 200;
struct kmem_cache *cache;
cache = kmem_cache_create("test_cache", size, 0, 0, NULL);
- if (!cache) {
- pr_err("Cache allocation failed\n");
- return;
- }
- pr_info("double-free on heap object\n");
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, cache);
+
p = kmem_cache_alloc(cache, GFP_KERNEL);
if (!p) {
- pr_err("Allocation failed\n");
+ kunit_err(test, "Allocation failed: %s\n", __func__);
kmem_cache_destroy(cache);
return;
}
kmem_cache_free(cache, p);
- kmem_cache_free(cache, p);
+ KUNIT_EXPECT_KASAN_FAIL(test, kmem_cache_free(cache, p));
kmem_cache_destroy(cache);
}
-static noinline void __init kmem_cache_invalid_free(void)
+static void kmem_cache_invalid_free(struct kunit *test)
{
char *p;
size_t size = 200;
@@ -611,20 +518,17 @@ static noinline void __init kmem_cache_invalid_free(void)
cache = kmem_cache_create("test_cache", size, 0, SLAB_TYPESAFE_BY_RCU,
NULL);
- if (!cache) {
- pr_err("Cache allocation failed\n");
- return;
- }
- pr_info("invalid-free of heap object\n");
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, cache);
+
p = kmem_cache_alloc(cache, GFP_KERNEL);
if (!p) {
- pr_err("Allocation failed\n");
+ kunit_err(test, "Allocation failed: %s\n", __func__);
kmem_cache_destroy(cache);
return;
}
/* Trigger invalid free, the object doesn't get freed */
- kmem_cache_free(cache, p + 1);
+ KUNIT_EXPECT_KASAN_FAIL(test, kmem_cache_free(cache, p + 1));
/*
* Properly free the object to prevent the "Objects remaining in
@@ -635,45 +539,63 @@ static noinline void __init kmem_cache_invalid_free(void)
kmem_cache_destroy(cache);
}
-static noinline void __init kasan_memchr(void)
+static void kasan_memchr(struct kunit *test)
{
char *ptr;
size_t size = 24;
- pr_info("out-of-bounds in memchr\n");
- ptr = kmalloc(size, GFP_KERNEL | __GFP_ZERO);
- if (!ptr)
+ /* See https://bugzilla.kernel.org/show_bug.cgi?id=206337 */
+ if (IS_ENABLED(CONFIG_AMD_MEM_ENCRYPT)) {
+ kunit_info(test,
+ "str* functions are not instrumented with CONFIG_AMD_MEM_ENCRYPT");
return;
+ }
+
+ ptr = kmalloc(size, GFP_KERNEL | __GFP_ZERO);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
+
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ kasan_ptr_result = memchr(ptr, '1', size + 1));
- kasan_ptr_result = memchr(ptr, '1', size + 1);
kfree(ptr);
}
-static noinline void __init kasan_memcmp(void)
+static void kasan_memcmp(struct kunit *test)
{
char *ptr;
size_t size = 24;
int arr[9];
- pr_info("out-of-bounds in memcmp\n");
- ptr = kmalloc(size, GFP_KERNEL | __GFP_ZERO);
- if (!ptr)
+ /* See https://bugzilla.kernel.org/show_bug.cgi?id=206337 */
+ if (IS_ENABLED(CONFIG_AMD_MEM_ENCRYPT)) {
+ kunit_info(test,
+ "str* functions are not instrumented with CONFIG_AMD_MEM_ENCRYPT");
return;
+ }
+ ptr = kmalloc(size, GFP_KERNEL | __GFP_ZERO);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
memset(arr, 0, sizeof(arr));
- kasan_int_result = memcmp(ptr, arr, size + 1);
+
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ kasan_int_result = memcmp(ptr, arr, size+1));
kfree(ptr);
}
-static noinline void __init kasan_strings(void)
+static void kasan_strings(struct kunit *test)
{
char *ptr;
size_t size = 24;
- pr_info("use-after-free in strchr\n");
- ptr = kmalloc(size, GFP_KERNEL | __GFP_ZERO);
- if (!ptr)
+ /* See https://bugzilla.kernel.org/show_bug.cgi?id=206337 */
+ if (IS_ENABLED(CONFIG_AMD_MEM_ENCRYPT)) {
+ kunit_info(test,
+ "str* functions are not instrumented with CONFIG_AMD_MEM_ENCRYPT");
return;
+ }
+
+ ptr = kmalloc(size, GFP_KERNEL | __GFP_ZERO);
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
kfree(ptr);
@@ -684,220 +606,164 @@ static noinline void __init kasan_strings(void)
* will likely point to zeroed byte.
*/
ptr += 16;
- kasan_ptr_result = strchr(ptr, '1');
+ KUNIT_EXPECT_KASAN_FAIL(test, kasan_ptr_result = strchr(ptr, '1'));
- pr_info("use-after-free in strrchr\n");
- kasan_ptr_result = strrchr(ptr, '1');
+ KUNIT_EXPECT_KASAN_FAIL(test, kasan_ptr_result = strrchr(ptr, '1'));
- pr_info("use-after-free in strcmp\n");
- kasan_int_result = strcmp(ptr, "2");
+ KUNIT_EXPECT_KASAN_FAIL(test, kasan_int_result = strcmp(ptr, "2"));
- pr_info("use-after-free in strncmp\n");
- kasan_int_result = strncmp(ptr, "2", 1);
+ KUNIT_EXPECT_KASAN_FAIL(test, kasan_int_result = strncmp(ptr, "2", 1));
- pr_info("use-after-free in strlen\n");
- kasan_int_result = strlen(ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, kasan_int_result = strlen(ptr));
- pr_info("use-after-free in strnlen\n");
- kasan_int_result = strnlen(ptr, 1);
+ KUNIT_EXPECT_KASAN_FAIL(test, kasan_int_result = strnlen(ptr, 1));
}
-static noinline void __init kasan_bitops(void)
+static void kasan_bitops(struct kunit *test)
{
/*
* Allocate 1 more byte, which causes kzalloc to round up to 16-bytes;
* this way we do not actually corrupt other memory.
*/
long *bits = kzalloc(sizeof(*bits) + 1, GFP_KERNEL);
- if (!bits)
- return;
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, bits);
/*
* Below calls try to access bit within allocated memory; however, the
* below accesses are still out-of-bounds, since bitops are defined to
* operate on the whole long the bit is in.
*/
- pr_info("out-of-bounds in set_bit\n");
- set_bit(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, set_bit(BITS_PER_LONG, bits));
- pr_info("out-of-bounds in __set_bit\n");
- __set_bit(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, __set_bit(BITS_PER_LONG, bits));
- pr_info("out-of-bounds in clear_bit\n");
- clear_bit(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, clear_bit(BITS_PER_LONG, bits));
- pr_info("out-of-bounds in __clear_bit\n");
- __clear_bit(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, __clear_bit(BITS_PER_LONG, bits));
- pr_info("out-of-bounds in clear_bit_unlock\n");
- clear_bit_unlock(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, clear_bit_unlock(BITS_PER_LONG, bits));
- pr_info("out-of-bounds in __clear_bit_unlock\n");
- __clear_bit_unlock(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, __clear_bit_unlock(BITS_PER_LONG, bits));
- pr_info("out-of-bounds in change_bit\n");
- change_bit(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, change_bit(BITS_PER_LONG, bits));
- pr_info("out-of-bounds in __change_bit\n");
- __change_bit(BITS_PER_LONG, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test, __change_bit(BITS_PER_LONG, bits));
/*
* Below calls try to access bit beyond allocated memory.
*/
- pr_info("out-of-bounds in test_and_set_bit\n");
- test_and_set_bit(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ test_and_set_bit(BITS_PER_LONG + BITS_PER_BYTE, bits));
- pr_info("out-of-bounds in __test_and_set_bit\n");
- __test_and_set_bit(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ __test_and_set_bit(BITS_PER_LONG + BITS_PER_BYTE, bits));
- pr_info("out-of-bounds in test_and_set_bit_lock\n");
- test_and_set_bit_lock(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ test_and_set_bit_lock(BITS_PER_LONG + BITS_PER_BYTE, bits));
- pr_info("out-of-bounds in test_and_clear_bit\n");
- test_and_clear_bit(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ test_and_clear_bit(BITS_PER_LONG + BITS_PER_BYTE, bits));
- pr_info("out-of-bounds in __test_and_clear_bit\n");
- __test_and_clear_bit(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ __test_and_clear_bit(BITS_PER_LONG + BITS_PER_BYTE, bits));
- pr_info("out-of-bounds in test_and_change_bit\n");
- test_and_change_bit(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ test_and_change_bit(BITS_PER_LONG + BITS_PER_BYTE, bits));
- pr_info("out-of-bounds in __test_and_change_bit\n");
- __test_and_change_bit(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ __test_and_change_bit(BITS_PER_LONG + BITS_PER_BYTE, bits));
- pr_info("out-of-bounds in test_bit\n");
- kasan_int_result = test_bit(BITS_PER_LONG + BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ kasan_int_result =
+ test_bit(BITS_PER_LONG + BITS_PER_BYTE, bits));
#if defined(clear_bit_unlock_is_negative_byte)
- pr_info("out-of-bounds in clear_bit_unlock_is_negative_byte\n");
- kasan_int_result = clear_bit_unlock_is_negative_byte(BITS_PER_LONG +
- BITS_PER_BYTE, bits);
+ KUNIT_EXPECT_KASAN_FAIL(test,
+ kasan_int_result = clear_bit_unlock_is_negative_byte(
+ BITS_PER_LONG + BITS_PER_BYTE, bits));
#endif
kfree(bits);
}
-static noinline void __init kmalloc_double_kzfree(void)
+static void kmalloc_double_kzfree(struct kunit *test)
{
char *ptr;
size_t size = 16;
- pr_info("double-free (kfree_sensitive)\n");
ptr = kmalloc(size, GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);
kfree_sensitive(ptr);
- kfree_sensitive(ptr);
+ KUNIT_EXPECT_KASAN_FAIL(test, kfree_sensitive(ptr));
}
-#ifdef CONFIG_KASAN_VMALLOC
-static noinline void __init vmalloc_oob(void)
+static void vmalloc_oob(struct kunit *test)
{
void *area;
- pr_info("vmalloc out-of-bounds\n");
+ if (!IS_ENABLED(CONFIG_KASAN_VMALLOC)) {
+ kunit_info(test, "CONFIG_KASAN_VMALLOC is not enabled.");
+ return;
+ }
/*
* We have to be careful not to hit the guard page.
* The MMU will catch that and crash us.
*/
area = vmalloc(3000);
- if (!area) {
- pr_err("Allocation failed\n");
- return;
- }
+ KUNIT_ASSERT_NOT_ERR_OR_NULL(test, area);
- ((volatile char *)area)[3100];
+ KUNIT_EXPECT_KASAN_FAIL(test, ((volatile char *)area)[3100]);
vfree(area);
}
-#else
-static void __init vmalloc_oob(void) {}
-#endif
-static struct kasan_rcu_info {
- int i;
- struct rcu_head rcu;
-} *global_rcu_ptr;
-
-static noinline void __init kasan_rcu_reclaim(struct rcu_head *rp)
-{
- struct kasan_rcu_info *fp = container_of(rp,
- struct kasan_rcu_info, rcu);
-
- kfree(fp);
- fp->i = 1;
-}
-
-static noinline void __init kasan_rcu_uaf(void)
-{
- struct kasan_rcu_info *ptr;
-
- pr_info("use-after-free in kasan_rcu_reclaim\n");
- ptr = kmalloc(sizeof(struct kasan_rcu_info), GFP_KERNEL);
- if (!ptr) {
- pr_err("Allocation failed\n");
- return;
- }
-
- global_rcu_ptr = rcu_dereference_protected(ptr, NULL);
- call_rcu(&global_rcu_ptr->rcu, kasan_rcu_reclaim);
-}
-
-static int __init kmalloc_tests_init(void)
-{
- /*
- * Temporarily enable multi-shot mode. Otherwise, we'd only get a
- * report for the first case.
- */
- bool multishot = kasan_save_enable_multi_shot();
-
- kmalloc_oob_right();
- kmalloc_oob_left();
- kmalloc_node_oob_right();
-#ifdef CONFIG_SLUB
- kmalloc_pagealloc_oob_right();
- kmalloc_pagealloc_uaf();
- kmalloc_pagealloc_invalid_free();
-#endif
- kmalloc_large_oob_right();
- kmalloc_oob_krealloc_more();
- kmalloc_oob_krealloc_less();
- kmalloc_oob_16();
- kmalloc_oob_in_memset();
- kmalloc_oob_memset_2();
- kmalloc_oob_memset_4();
- kmalloc_oob_memset_8();
- kmalloc_oob_memset_16();
- kmalloc_memmove_invalid_size();
- kmalloc_uaf();
- kmalloc_uaf_memset();
- kmalloc_uaf2();
- kfree_via_page();
- kfree_via_phys();
- kmem_cache_oob();
- memcg_accounted_kmem_cache();
- kasan_stack_oob();
- kasan_global_oob();
- kasan_alloca_oob_left();
- kasan_alloca_oob_right();
- ksize_unpoisons_memory();
- copy_user_test();
- kmem_cache_double_free();
- kmem_cache_invalid_free();
- kasan_memchr();
- kasan_memcmp();
- kasan_strings();
- kasan_bitops();
- kmalloc_double_kzfree();
- vmalloc_oob();
- kasan_rcu_uaf();
-
- kasan_restore_multi_shot(multishot);
-
- return -EAGAIN;
-}
+static struct kunit_case kasan_kunit_test_cases[] = {
+ KUNIT_CASE(kmalloc_oob_right),
+ KUNIT_CASE(kmalloc_oob_left),
+ KUNIT_CASE(kmalloc_node_oob_right),
+ KUNIT_CASE(kmalloc_pagealloc_oob_right),
+ KUNIT_CASE(kmalloc_pagealloc_uaf),
+ KUNIT_CASE(kmalloc_pagealloc_invalid_free),
+ KUNIT_CASE(kmalloc_large_oob_right),
+ KUNIT_CASE(kmalloc_oob_krealloc_more),
+ KUNIT_CASE(kmalloc_oob_krealloc_less),
+ KUNIT_CASE(kmalloc_oob_16),
+ KUNIT_CASE(kmalloc_oob_in_memset),
+ KUNIT_CASE(kmalloc_oob_memset_2),
+ KUNIT_CASE(kmalloc_oob_memset_4),
+ KUNIT_CASE(kmalloc_oob_memset_8),
+ KUNIT_CASE(kmalloc_oob_memset_16),
+ KUNIT_CASE(kmalloc_memmove_invalid_size),
+ KUNIT_CASE(kmalloc_uaf),
+ KUNIT_CASE(kmalloc_uaf_memset),
+ KUNIT_CASE(kmalloc_uaf2),
+ KUNIT_CASE(kfree_via_page),
+ KUNIT_CASE(kfree_via_phys),
+ KUNIT_CASE(kmem_cache_oob),
+ KUNIT_CASE(memcg_accounted_kmem_cache),
+ KUNIT_CASE(kasan_global_oob),
+ KUNIT_CASE(kasan_stack_oob),
+ KUNIT_CASE(kasan_alloca_oob_left),
+ KUNIT_CASE(kasan_alloca_oob_right),
+ KUNIT_CASE(ksize_unpoisons_memory),
+ KUNIT_CASE(kmem_cache_double_free),
+ KUNIT_CASE(kmem_cache_invalid_free),
+ KUNIT_CASE(kasan_memchr),
+ KUNIT_CASE(kasan_memcmp),
+ KUNIT_CASE(kasan_strings),
+ KUNIT_CASE(kasan_bitops),
+ KUNIT_CASE(kmalloc_double_kzfree),
+ KUNIT_CASE(vmalloc_oob),
+ {}
+};
+
+static struct kunit_suite kasan_kunit_test_suite = {
+ .name = "kasan",
+ .init = kasan_test_init,
+ .test_cases = kasan_kunit_test_cases,
+ .exit = kasan_test_exit,
+};
+
+kunit_test_suite(kasan_kunit_test_suite);
-module_init(kmalloc_tests_init);
MODULE_LICENSE("GPL");
diff --git a/lib/test_kasan_module.c b/lib/test_kasan_module.c
new file mode 100644
index 000000000000..2d68db6ae67b
--- /dev/null
+++ b/lib/test_kasan_module.c
@@ -0,0 +1,111 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ *
+ * Copyright (c) 2014 Samsung Electronics Co., Ltd.
+ * Author: Andrey Ryabinin <a.ryabinin@samsung.com>
+ */
+
+#define pr_fmt(fmt) "kasan test: %s " fmt, __func__
+
+#include <linux/mman.h>
+#include <linux/module.h>
+#include <linux/printk.h>
+#include <linux/slab.h>
+#include <linux/uaccess.h>
+
+#include "../mm/kasan/kasan.h"
+
+#define OOB_TAG_OFF (IS_ENABLED(CONFIG_KASAN_GENERIC) ? 0 : KASAN_SHADOW_SCALE_SIZE)
+
+static noinline void __init copy_user_test(void)
+{
+ char *kmem;
+ char __user *usermem;
+ size_t size = 10;
+ int unused;
+
+ kmem = kmalloc(size, GFP_KERNEL);
+ if (!kmem)
+ return;
+
+ usermem = (char __user *)vm_mmap(NULL, 0, PAGE_SIZE,
+ PROT_READ | PROT_WRITE | PROT_EXEC,
+ MAP_ANONYMOUS | MAP_PRIVATE, 0);
+ if (IS_ERR(usermem)) {
+ pr_err("Failed to allocate user memory\n");
+ kfree(kmem);
+ return;
+ }
+
+ pr_info("out-of-bounds in copy_from_user()\n");
+ unused = copy_from_user(kmem, usermem, size + 1 + OOB_TAG_OFF);
+
+ pr_info("out-of-bounds in copy_to_user()\n");
+ unused = copy_to_user(usermem, kmem, size + 1 + OOB_TAG_OFF);
+
+ pr_info("out-of-bounds in __copy_from_user()\n");
+ unused = __copy_from_user(kmem, usermem, size + 1 + OOB_TAG_OFF);
+
+ pr_info("out-of-bounds in __copy_to_user()\n");
+ unused = __copy_to_user(usermem, kmem, size + 1 + OOB_TAG_OFF);
+
+ pr_info("out-of-bounds in __copy_from_user_inatomic()\n");
+ unused = __copy_from_user_inatomic(kmem, usermem, size + 1 + OOB_TAG_OFF);
+
+ pr_info("out-of-bounds in __copy_to_user_inatomic()\n");
+ unused = __copy_to_user_inatomic(usermem, kmem, size + 1 + OOB_TAG_OFF);
+
+ pr_info("out-of-bounds in strncpy_from_user()\n");
+ unused = strncpy_from_user(kmem, usermem, size + 1 + OOB_TAG_OFF);
+
+ vm_munmap((unsigned long)usermem, PAGE_SIZE);
+ kfree(kmem);
+}
+
+static struct kasan_rcu_info {
+ int i;
+ struct rcu_head rcu;
+} *global_rcu_ptr;
+
+static noinline void __init kasan_rcu_reclaim(struct rcu_head *rp)
+{
+ struct kasan_rcu_info *fp = container_of(rp,
+ struct kasan_rcu_info, rcu);
+
+ kfree(fp);
+ fp->i = 1;
+}
+
+static noinline void __init kasan_rcu_uaf(void)
+{
+ struct kasan_rcu_info *ptr;
+
+ pr_info("use-after-free in kasan_rcu_reclaim\n");
+ ptr = kmalloc(sizeof(struct kasan_rcu_info), GFP_KERNEL);
+ if (!ptr) {
+ pr_err("Allocation failed\n");
+ return;
+ }
+
+ global_rcu_ptr = rcu_dereference_protected(ptr, NULL);
+ call_rcu(&global_rcu_ptr->rcu, kasan_rcu_reclaim);
+}
+
+
+static int __init test_kasan_module_init(void)
+{
+ /*
+ * Temporarily enable multi-shot mode. Otherwise, we'd only get a
+ * report for the first case.
+ */
+ bool multishot = kasan_save_enable_multi_shot();
+
+ copy_user_test();
+ kasan_rcu_uaf();
+
+ kasan_restore_multi_shot(multishot);
+ return -EAGAIN;
+}
+
+module_init(test_kasan_module_init);
+MODULE_LICENSE("GPL");
diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c
index c5a6fef7b45d..76c607ee6db5 100644
--- a/lib/test_rhashtable.c
+++ b/lib/test_rhashtable.c
@@ -434,7 +434,7 @@ static int __init test_rhltable(unsigned int entries)
} else {
if (WARN(err != -ENOENT, "removed non-existent element, error %d not %d",
err, -ENOENT))
- continue;
+ continue;
}
}
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index afb9521ddf91..14c9a6af1b23 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -940,13 +940,13 @@ char *bdev_name(char *buf, char *end, struct block_device *bdev,
hd = bdev->bd_disk;
buf = string(buf, end, hd->disk_name, spec);
- if (bdev->bd_part->partno) {
+ if (bdev->bd_partno) {
if (isdigit(hd->disk_name[strlen(hd->disk_name)-1])) {
if (buf < end)
*buf = 'p';
buf++;
}
- buf = number(buf, end, bdev->bd_part->partno, spec);
+ buf = number(buf, end, bdev->bd_partno, spec);
}
return buf;
}