diff options
Diffstat (limited to 'lib')
46 files changed, 664 insertions, 2144 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index a9e15403434e..bb94c1ba616a 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -340,6 +340,9 @@ config NLATTR config GENERIC_ATOMIC64 bool +config ARCH_HAS_ATOMIC64_DEC_IF_POSITIVE + def_bool y if GENERIC_ATOMIC64 + config LRU_CACHE tristate @@ -378,14 +381,6 @@ config MPILIB It is used to implement RSA digital signature verification, which is used by IMA/EVM digital signature extension. -config MPILIB_EXTRA - bool - depends on MPILIB - help - Additional sources of multiprecision maths library from GnuPG. - This code is unnecessary for RSA digital signature verification, - but can be compiled if needed. - config SIGNATURE tristate depends on KEYS && CRYPTO @@ -395,4 +390,10 @@ config SIGNATURE Digital signature verification. Currently only RSA is supported. Implementation is done using GnuPG MPI library +# +# libfdt files, only selected if needed. +# +config LIBFDT + bool + endmenu diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index a42d3ae39648..2403a63b5da5 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -241,6 +241,26 @@ config BOOTPARAM_SOFTLOCKUP_PANIC_VALUE default 0 if !BOOTPARAM_SOFTLOCKUP_PANIC default 1 if BOOTPARAM_SOFTLOCKUP_PANIC +config PANIC_ON_OOPS + bool "Panic on Oops" if EXPERT + default n + help + Say Y here to enable the kernel to panic when it oopses. This + has the same effect as setting oops=panic on the kernel command + line. + + This feature is useful to ensure that the kernel does not do + anything erroneous after an oops which could result in data + corruption or other issues. + + Say N if unsure. + +config PANIC_ON_OOPS_VALUE + int + range 0 1 + default 0 if !PANIC_ON_OOPS + default 1 if PANIC_ON_OOPS + config DETECT_HUNG_TASK bool "Detect Hung Tasks" depends on DEBUG_KERNEL @@ -694,7 +714,7 @@ config STACKTRACE config DEBUG_STACK_USAGE bool "Stack utilization instrumentation" - depends on DEBUG_KERNEL + depends on DEBUG_KERNEL && !IA64 && !PARISC help Enables the display of the minimum amount of free stack which each task has ever had available in the sysrq-T and sysrq-P debug output. @@ -1064,18 +1084,105 @@ config LKDTM Documentation on how to use the module can be found in Documentation/fault-injection/provoke-crashes.txt +config NOTIFIER_ERROR_INJECTION + tristate "Notifier error injection" + depends on DEBUG_KERNEL + select DEBUG_FS + help + This option provides the ability to inject artifical errors to + specified notifier chain callbacks. It is useful to test the error + handling of notifier call chain failures. + + Say N if unsure. + config CPU_NOTIFIER_ERROR_INJECT tristate "CPU notifier error injection module" - depends on HOTPLUG_CPU && DEBUG_KERNEL + depends on HOTPLUG_CPU && NOTIFIER_ERROR_INJECTION help This option provides a kernel module that can be used to test - the error handling of the cpu notifiers + the error handling of the cpu notifiers by injecting artifical + errors to CPU notifier chain callbacks. It is controlled through + debugfs interface under /sys/kernel/debug/notifier-error-inject/cpu + + If the notifier call chain should be failed with some events + notified, write the error code to "actions/<notifier event>/error". + + Example: Inject CPU offline error (-1 == -EPERM) + + # cd /sys/kernel/debug/notifier-error-inject/cpu + # echo -1 > actions/CPU_DOWN_PREPARE/error + # echo 0 > /sys/devices/system/cpu/cpu1/online + bash: echo: write error: Operation not permitted To compile this code as a module, choose M here: the module will be called cpu-notifier-error-inject. If unsure, say N. +config PM_NOTIFIER_ERROR_INJECT + tristate "PM notifier error injection module" + depends on PM && NOTIFIER_ERROR_INJECTION + default m if PM_DEBUG + help + This option provides the ability to inject artifical errors to + PM notifier chain callbacks. It is controlled through debugfs + interface /sys/kernel/debug/notifier-error-inject/pm + + If the notifier call chain should be failed with some events + notified, write the error code to "actions/<notifier event>/error". + + Example: Inject PM suspend error (-12 = -ENOMEM) + + # cd /sys/kernel/debug/notifier-error-inject/pm/ + # echo -12 > actions/PM_SUSPEND_PREPARE/error + # echo mem > /sys/power/state + bash: echo: write error: Cannot allocate memory + + To compile this code as a module, choose M here: the module will + be called pm-notifier-error-inject. + + If unsure, say N. + +config MEMORY_NOTIFIER_ERROR_INJECT + tristate "Memory hotplug notifier error injection module" + depends on MEMORY_HOTPLUG_SPARSE && NOTIFIER_ERROR_INJECTION + help + This option provides the ability to inject artifical errors to + memory hotplug notifier chain callbacks. It is controlled through + debugfs interface under /sys/kernel/debug/notifier-error-inject/memory + + If the notifier call chain should be failed with some events + notified, write the error code to "actions/<notifier event>/error". + + Example: Inject memory hotplug offline error (-12 == -ENOMEM) + + # cd /sys/kernel/debug/notifier-error-inject/memory + # echo -12 > actions/MEM_GOING_OFFLINE/error + # echo offline > /sys/devices/system/memory/memoryXXX/state + bash: echo: write error: Cannot allocate memory + + To compile this code as a module, choose M here: the module will + be called pSeries-reconfig-notifier-error-inject. + + If unsure, say N. + +config PSERIES_RECONFIG_NOTIFIER_ERROR_INJECT + tristate "pSeries reconfig notifier error injection module" + depends on PPC_PSERIES && NOTIFIER_ERROR_INJECTION + help + This option provides the ability to inject artifical errors to + pSeries reconfig notifier chain callbacks. It is controlled + through debugfs interface under + /sys/kernel/debug/notifier-error-inject/pSeries-reconfig/ + + If the notifier call chain should be failed with some events + notified, write the error code to "actions/<notifier event>/error". + + To compile this code as a module, choose M here: the module will + be called memory-notifier-error-inject. + + If unsure, say N. + config FAULT_INJECTION bool "Fault-injection framework" depends on DEBUG_KERNEL diff --git a/lib/Makefile b/lib/Makefile index ee837378b107..42d283edc4d3 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -22,7 +22,7 @@ lib-y += kobject.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \ - bsearch.o find_last_bit.o find_next_bit.o llist.o + bsearch.o find_last_bit.o find_next_bit.o llist.o memweight.o obj-y += kstrtox.o obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o @@ -90,7 +90,12 @@ obj-$(CONFIG_AUDIT_GENERIC) += audit.o obj-$(CONFIG_SWIOTLB) += swiotlb.o obj-$(CONFIG_IOMMU_HELPER) += iommu-helper.o obj-$(CONFIG_FAULT_INJECTION) += fault-inject.o +obj-$(CONFIG_NOTIFIER_ERROR_INJECTION) += notifier-error-inject.o obj-$(CONFIG_CPU_NOTIFIER_ERROR_INJECT) += cpu-notifier-error-inject.o +obj-$(CONFIG_PM_NOTIFIER_ERROR_INJECT) += pm-notifier-error-inject.o +obj-$(CONFIG_MEMORY_NOTIFIER_ERROR_INJECT) += memory-notifier-error-inject.o +obj-$(CONFIG_PSERIES_RECONFIG_NOTIFIER_ERROR_INJECT) += \ + pSeries-reconfig-notifier-error-inject.o lib-$(CONFIG_GENERIC_BUG) += bug.o @@ -130,6 +135,11 @@ obj-$(CONFIG_GENERIC_STRNLEN_USER) += strnlen_user.o obj-$(CONFIG_STMP_DEVICE) += stmp_device.o +libfdt_files = fdt.o fdt_ro.o fdt_wip.o fdt_rw.o fdt_sw.o fdt_strerror.o +$(foreach file, $(libfdt_files), \ + $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) +lib-$(CONFIG_LIBFDT) += $(libfdt_files) + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/atomic64_test.c b/lib/atomic64_test.c index cb99b91c3a1d..00bca223d1e1 100644 --- a/lib/atomic64_test.c +++ b/lib/atomic64_test.c @@ -114,8 +114,7 @@ static __init int test_atomic64(void) r += one; BUG_ON(v.counter != r); -#if defined(CONFIG_X86) || defined(CONFIG_MIPS) || defined(CONFIG_PPC) || \ - defined(CONFIG_S390) || defined(_ASM_GENERIC_ATOMIC64_H) || defined(CONFIG_ARM) +#ifdef CONFIG_ARCH_HAS_ATOMIC64_DEC_IF_POSITIVE INIT(onestwos); BUG_ON(atomic64_dec_if_positive(&v) != (onestwos - 1)); r -= one; @@ -129,7 +128,7 @@ static __init int test_atomic64(void) BUG_ON(atomic64_dec_if_positive(&v) != (-one - one)); BUG_ON(v.counter != r); #else -#warning Please implement atomic64_dec_if_positive for your architecture, and add it to the IF above +#warning Please implement atomic64_dec_if_positive for your architecture and select the above Kconfig symbol #endif INIT(onestwos); diff --git a/lib/btree.c b/lib/btree.c index e5ec1e9c1aa5..f9a484676cb6 100644 --- a/lib/btree.c +++ b/lib/btree.c @@ -319,8 +319,8 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, if (head->height == 0) return NULL; -retry: longcpy(key, __key, geo->keylen); +retry: dec_key(geo, key); node = head->node; @@ -351,7 +351,7 @@ retry: } miss: if (retry_key) { - __key = retry_key; + longcpy(key, retry_key, geo->keylen); retry_key = NULL; goto retry; } @@ -509,6 +509,7 @@ retry: int btree_insert(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val, gfp_t gfp) { + BUG_ON(!val); return btree_insert_level(head, geo, key, val, 1, gfp); } EXPORT_SYMBOL_GPL(btree_insert); diff --git a/lib/cpu-notifier-error-inject.c b/lib/cpu-notifier-error-inject.c index 4dc20321b0d5..707ca24f7b18 100644 --- a/lib/cpu-notifier-error-inject.c +++ b/lib/cpu-notifier-error-inject.c @@ -1,58 +1,45 @@ #include <linux/kernel.h> -#include <linux/cpu.h> #include <linux/module.h> -#include <linux/notifier.h> +#include <linux/cpu.h> -static int priority; -static int cpu_up_prepare_error; -static int cpu_down_prepare_error; +#include "notifier-error-inject.h" +static int priority; module_param(priority, int, 0); MODULE_PARM_DESC(priority, "specify cpu notifier priority"); -module_param(cpu_up_prepare_error, int, 0644); -MODULE_PARM_DESC(cpu_up_prepare_error, - "specify error code to inject CPU_UP_PREPARE action"); - -module_param(cpu_down_prepare_error, int, 0644); -MODULE_PARM_DESC(cpu_down_prepare_error, - "specify error code to inject CPU_DOWN_PREPARE action"); - -static int err_inject_cpu_callback(struct notifier_block *nfb, - unsigned long action, void *hcpu) -{ - int err = 0; - - switch (action) { - case CPU_UP_PREPARE: - case CPU_UP_PREPARE_FROZEN: - err = cpu_up_prepare_error; - break; - case CPU_DOWN_PREPARE: - case CPU_DOWN_PREPARE_FROZEN: - err = cpu_down_prepare_error; - break; +static struct notifier_err_inject cpu_notifier_err_inject = { + .actions = { + { NOTIFIER_ERR_INJECT_ACTION(CPU_UP_PREPARE) }, + { NOTIFIER_ERR_INJECT_ACTION(CPU_UP_PREPARE_FROZEN) }, + { NOTIFIER_ERR_INJECT_ACTION(CPU_DOWN_PREPARE) }, + { NOTIFIER_ERR_INJECT_ACTION(CPU_DOWN_PREPARE_FROZEN) }, + {} } - if (err) - printk(KERN_INFO "Injecting error (%d) at cpu notifier\n", err); - - return notifier_from_errno(err); -} - -static struct notifier_block err_inject_cpu_notifier = { - .notifier_call = err_inject_cpu_callback, }; +static struct dentry *dir; + static int err_inject_init(void) { - err_inject_cpu_notifier.priority = priority; + int err; + + dir = notifier_err_inject_init("cpu", notifier_err_inject_dir, + &cpu_notifier_err_inject, priority); + if (IS_ERR(dir)) + return PTR_ERR(dir); + + err = register_hotcpu_notifier(&cpu_notifier_err_inject.nb); + if (err) + debugfs_remove_recursive(dir); - return register_hotcpu_notifier(&err_inject_cpu_notifier); + return err; } static void err_inject_exit(void) { - unregister_hotcpu_notifier(&err_inject_cpu_notifier); + unregister_hotcpu_notifier(&cpu_notifier_err_inject.nb); + debugfs_remove_recursive(dir); } module_init(err_inject_init); diff --git a/lib/crc32.c b/lib/crc32.c index b0d278fb1d91..61774b8db4de 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -74,7 +74,9 @@ crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) size_t i; # endif const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3]; +# if CRC_LE_BITS != 32 const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7]; +# endif u32 q; /* Align it */ diff --git a/lib/div64.c b/lib/div64.c index 3ea24907d52e..a163b6caef73 100644 --- a/lib/div64.c +++ b/lib/div64.c @@ -87,7 +87,7 @@ EXPORT_SYMBOL(div_s64_rem); * by the book 'Hacker's Delight'. The original source and full proof * can be found here and is available for use without restriction. * - * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c' + * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c.txt' */ #ifndef div64_u64 u64 div64_u64(u64 dividend, u64 divisor) diff --git a/lib/dma-debug.c b/lib/dma-debug.c index 518aea714d21..66ce41489133 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -78,7 +78,7 @@ static LIST_HEAD(free_entries); static DEFINE_SPINLOCK(free_entries_lock); /* Global disable flag - will be set in case of an error */ -static bool global_disable __read_mostly; +static u32 global_disable __read_mostly; /* Global error count */ static u32 error_count; @@ -657,7 +657,7 @@ static int dma_debug_fs_init(void) global_disable_dent = debugfs_create_bool("disabled", 0444, dma_debug_dent, - (u32 *)&global_disable); + &global_disable); if (!global_disable_dent) goto out_err; diff --git a/lib/fault-inject.c b/lib/fault-inject.c index 6805453c18e7..f7210ad6cffd 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -101,6 +101,10 @@ static inline bool fail_stacktrace(struct fault_attr *attr) bool should_fail(struct fault_attr *attr, ssize_t size) { + /* No need to check any other properties if the probability is 0 */ + if (attr->probability == 0) + return false; + if (attr->task_filter && !fail_task(attr, current)) return false; diff --git a/lib/fdt.c b/lib/fdt.c new file mode 100644 index 000000000000..97f20069fc37 --- /dev/null +++ b/lib/fdt.c @@ -0,0 +1,2 @@ +#include <linux/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt.c" diff --git a/lib/fdt_ro.c b/lib/fdt_ro.c new file mode 100644 index 000000000000..f73c04ea7be4 --- /dev/null +++ b/lib/fdt_ro.c @@ -0,0 +1,2 @@ +#include <linux/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_ro.c" diff --git a/lib/fdt_rw.c b/lib/fdt_rw.c new file mode 100644 index 000000000000..0c1f0f4a4b13 --- /dev/null +++ b/lib/fdt_rw.c @@ -0,0 +1,2 @@ +#include <linux/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_rw.c" diff --git a/lib/fdt_strerror.c b/lib/fdt_strerror.c new file mode 100644 index 000000000000..8713e3ff4707 --- /dev/null +++ b/lib/fdt_strerror.c @@ -0,0 +1,2 @@ +#include <linux/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_strerror.c" diff --git a/lib/fdt_sw.c b/lib/fdt_sw.c new file mode 100644 index 000000000000..9ac7e50c76ce --- /dev/null +++ b/lib/fdt_sw.c @@ -0,0 +1,2 @@ +#include <linux/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_sw.c" diff --git a/lib/fdt_wip.c b/lib/fdt_wip.c new file mode 100644 index 000000000000..45b3fc3d3ba1 --- /dev/null +++ b/lib/fdt_wip.c @@ -0,0 +1,2 @@ +#include <linux/libfdt_env.h> +#include "../scripts/dtc/libfdt/fdt_wip.c" diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c index 1a91efa6d121..0401d2916d9f 100644 --- a/lib/kobject_uevent.c +++ b/lib/kobject_uevent.c @@ -373,13 +373,16 @@ EXPORT_SYMBOL_GPL(add_uevent_var); static int uevent_net_init(struct net *net) { struct uevent_sock *ue_sk; + struct netlink_kernel_cfg cfg = { + .groups = 1, + }; ue_sk = kzalloc(sizeof(*ue_sk), GFP_KERNEL); if (!ue_sk) return -ENOMEM; ue_sk->sk = netlink_kernel_create(net, NETLINK_KOBJECT_UEVENT, - 1, NULL, NULL, THIS_MODULE); + THIS_MODULE, &cfg); if (!ue_sk->sk) { printk(KERN_ERR "kobject_uevent: unable to create netlink socket!\n"); diff --git a/lib/list_debug.c b/lib/list_debug.c index 23a5e031cd8b..c24c2f7e296f 100644 --- a/lib/list_debug.c +++ b/lib/list_debug.c @@ -87,12 +87,10 @@ void __list_add_rcu(struct list_head *new, struct list_head *prev, struct list_head *next) { WARN(next->prev != prev, - "list_add_rcu corruption. next->prev should be " - "prev (%p), but was %p. (next=%p).\n", + "list_add_rcu corruption. next->prev should be prev (%p), but was %p. (next=%p).\n", prev, next->prev, next); WARN(prev->next != next, - "list_add_rcu corruption. prev->next should be " - "next (%p), but was %p. (prev=%p).\n", + "list_add_rcu corruption. prev->next should be next (%p), but was %p. (prev=%p).\n", next, prev->next, prev); new->next = next; new->prev = prev; diff --git a/lib/memory-notifier-error-inject.c b/lib/memory-notifier-error-inject.c new file mode 100644 index 000000000000..e6239bf0b0df --- /dev/null +++ b/lib/memory-notifier-error-inject.c @@ -0,0 +1,48 @@ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/memory.h> + +#include "notifier-error-inject.h" + +static int priority; +module_param(priority, int, 0); +MODULE_PARM_DESC(priority, "specify memory notifier priority"); + +static struct notifier_err_inject memory_notifier_err_inject = { + .actions = { + { NOTIFIER_ERR_INJECT_ACTION(MEM_GOING_ONLINE) }, + { NOTIFIER_ERR_INJECT_ACTION(MEM_GOING_OFFLINE) }, + {} + } +}; + +static struct dentry *dir; + +static int err_inject_init(void) +{ + int err; + + dir = notifier_err_inject_init("memory", notifier_err_inject_dir, + &memory_notifier_err_inject, priority); + if (IS_ERR(dir)) + return PTR_ERR(dir); + + err = register_memory_notifier(&memory_notifier_err_inject.nb); + if (err) + debugfs_remove_recursive(dir); + + return err; +} + +static void err_inject_exit(void) +{ + unregister_memory_notifier(&memory_notifier_err_inject.nb); + debugfs_remove_recursive(dir); +} + +module_init(err_inject_init); +module_exit(err_inject_exit); + +MODULE_DESCRIPTION("memory notifier error injection module"); +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Akinobu Mita <akinobu.mita@gmail.com>"); diff --git a/lib/memweight.c b/lib/memweight.c new file mode 100644 index 000000000000..e35fc8771893 --- /dev/null +++ b/lib/memweight.c @@ -0,0 +1,38 @@ +#include <linux/export.h> +#include <linux/bug.h> +#include <linux/bitmap.h> + +/** + * memweight - count the total number of bits set in memory area + * @ptr: pointer to the start of the area + * @bytes: the size of the area + */ +size_t memweight(const void *ptr, size_t bytes) +{ + size_t ret = 0; + size_t longs; + const unsigned char *bitmap = ptr; + + for (; bytes > 0 && ((unsigned long)bitmap) % sizeof(long); + bytes--, bitmap++) + ret += hweight8(*bitmap); + + longs = bytes / sizeof(long); + if (longs) { + BUG_ON(longs >= INT_MAX / BITS_PER_LONG); + ret += bitmap_weight((unsigned long *)bitmap, + longs * BITS_PER_LONG); + bytes -= longs * sizeof(long); + bitmap += longs * sizeof(long); + } + /* + * The reason that this last loop is distinct from the preceding + * bitmap_weight() call is to compute 1-bits in the last region smaller + * than sizeof(long) properly on big-endian systems. + */ + for (; bytes > 0; bytes--, bitmap++) + ret += hweight8(*bitmap); + + return ret; +} +EXPORT_SYMBOL(memweight); diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile index 567d52e74d77..45ca90a8639c 100644 --- a/lib/mpi/Makefile +++ b/lib/mpi/Makefile @@ -19,14 +19,3 @@ mpi-y = \ mpih-mul.o \ mpi-pow.o \ mpiutil.o - -mpi-$(CONFIG_MPILIB_EXTRA) += \ - mpi-add.o \ - mpi-div.o \ - mpi-cmp.o \ - mpi-gcd.o \ - mpi-inline.o \ - mpi-inv.o \ - mpi-mpow.o \ - mpi-mul.o \ - mpi-scan.o diff --git a/lib/mpi/generic_mpi-asm-defs.h b/lib/mpi/generic_mpi-asm-defs.h deleted file mode 100644 index 047d1f5a7249..000000000000 --- a/lib/mpi/generic_mpi-asm-defs.h +++ /dev/null @@ -1,4 +0,0 @@ -/* This file defines some basic constants for the MPI machinery. We - * need to define the types on a per-CPU basis, so it is done with - * this file here. */ -#define BYTES_PER_MPI_LIMB (SIZEOF_UNSIGNED_LONG) diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c deleted file mode 100644 index f56b9ba295e6..000000000000 --- a/lib/mpi/mpi-add.c +++ /dev/null @@ -1,234 +0,0 @@ -/* mpi-add.c - MPI functions - * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. - * Copyright (C) 1994, 1996 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - * - * 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. - * The GNU MP Library itself is published under the LGPL; - * however I decided to publish this code under the plain GPL. - */ - -#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. - */ -int mpi_add_ui(MPI w, const 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) - if (mpi_resize(w, wsize) < 0) - return -ENOMEM; - - /* 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; - return 0; -} - -int mpi_add(MPI w, MPI u, MPI v) -{ - mpi_ptr_t wp, up, vp; - mpi_size_t usize, vsize, wsize; - int usign, vsign, wsign; - - if (u->nlimbs < v->nlimbs) { /* Swap U and V. */ - usize = v->nlimbs; - usign = v->sign; - vsize = u->nlimbs; - vsign = u->sign; - wsize = usize + 1; - if (RESIZE_IF_NEEDED(w, wsize) < 0) - return -ENOMEM; - /* 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; - if (RESIZE_IF_NEEDED(w, wsize) < 0) - return -ENOMEM; - /* 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; - return 0; -} - -/**************** - * Subtract the unsigned integer V from the mpi-integer U and store the - * result in W. - */ -int mpi_sub_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) - if (mpi_resize(w, wsize) < 0) - return -ENOMEM; - - /* 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; - wsign = 1; - } else if (usign) { /* mpi and v are 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; - wsign = 1; - } else { - mpihelp_sub_1(wp, up, usize, v); - /* Size can decrease with at most one limb. */ - wsize = usize - (wp[usize - 1] == 0); - } - } - - w->nlimbs = wsize; - w->sign = wsign; - return 0; -} - -int mpi_sub(MPI w, MPI u, MPI v) -{ - int rc; - - if (w == v) { - MPI vv; - if (mpi_copy(&vv, v) < 0) - return -ENOMEM; - vv->sign = !vv->sign; - rc = mpi_add(w, u, vv); - mpi_free(vv); - } else { - /* fixme: this is not thread-save (we temp. modify v) */ - v->sign = !v->sign; - rc = mpi_add(w, u, v); - v->sign = !v->sign; - } - return rc; -} - -int mpi_addm(MPI w, MPI u, MPI v, MPI m) -{ - if (mpi_add(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0) - return -ENOMEM; - return 0; -} - -int mpi_subm(MPI w, MPI u, MPI v, MPI m) -{ - if (mpi_sub(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0) - return -ENOMEM; - return 0; -} diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c index 0c505361da19..568724804f29 100644 --- a/lib/mpi/mpi-bit.c +++ b/lib/mpi/mpi-bit.c @@ -54,165 +54,3 @@ 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 n) -{ - unsigned 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; -} - -/**************** - * Set bit N of A. - */ -int mpi_set_bit(MPI a, unsigned n) -{ - unsigned limbno, bitno; - - limbno = n / BITS_PER_MPI_LIMB; - bitno = n % BITS_PER_MPI_LIMB; - - if (limbno >= a->nlimbs) { /* resize */ - if (a->alloced >= limbno) - if (mpi_resize(a, limbno + 1) < 0) - return -ENOMEM; - a->nlimbs = limbno + 1; - } - a->d[limbno] |= (A_LIMB_1 << bitno); - return 0; -} - -/**************** - * Set bit N of A. and clear all bits above - */ -int mpi_set_highbit(MPI a, unsigned n) -{ - unsigned limbno, bitno; - - limbno = n / BITS_PER_MPI_LIMB; - bitno = n % BITS_PER_MPI_LIMB; - - if (limbno >= a->nlimbs) { /* resize */ - if (a->alloced >= limbno) - if (mpi_resize(a, limbno + 1) < 0) - return -ENOMEM; - 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; - return 0; -} - -/**************** - * clear bit N of A and all bits above - */ -void mpi_clear_highbit(MPI a, unsigned n) -{ - unsigned limbno, bitno; - - limbno = n / BITS_PER_MPI_LIMB; - bitno = n % BITS_PER_MPI_LIMB; - - if (limbno >= a->nlimbs) - return; /* not allocated, so 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 n) -{ - unsigned 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 to far to left */ - a->d[limbno] &= ~(A_LIMB_1 << bitno); -} - -/**************** - * Shift A by N bits to the right - * FIXME: should use alloc_limb if X and A are same. - */ -int mpi_rshift(MPI x, MPI a, unsigned n) -{ - mpi_ptr_t xp; - mpi_size_t xsize; - - xsize = a->nlimbs; - x->sign = a->sign; - if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0) - return -ENOMEM; - xp = x->d; - - if (xsize) { - mpihelp_rshift(xp, a->d, xsize, n); - MPN_NORMALIZE(xp, xsize); - } - x->nlimbs = xsize; - return 0; -} - -/**************** - * Shift A by COUNT limbs to the left - * This is used only within the MPI library - */ -int mpi_lshift_limbs(MPI a, unsigned int count) -{ - const int n = a->nlimbs; - mpi_ptr_t ap; - int i; - - if (!count || !n) - return 0; - - if (RESIZE_IF_NEEDED(a, n + count) < 0) - return -ENOMEM; - - 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; - return 0; -} - -/**************** - * 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; -} diff --git a/lib/mpi/mpi-cmp.c b/lib/mpi/mpi-cmp.c deleted file mode 100644 index 914bc42a8a80..000000000000 --- a/lib/mpi/mpi-cmp.c +++ /dev/null @@ -1,68 +0,0 @@ -/* mpi-cmp.c - MPI functions - * Copyright (C) 1998, 1999 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - */ - -#include "mpi-internal.h" - -int mpi_cmp_ui(MPI u, unsigned long v) -{ - mpi_limb_t limb = v; - - mpi_normalize(u); - if (!u->nlimbs && !limb) - return 0; - if (u->sign) - return -1; - if (u->nlimbs > 1) - return 1; - - if (u->d[0] == limb) - return 0; - else if (u->d[0] > limb) - return 1; - else - return -1; -} - -int mpi_cmp(MPI u, MPI v) -{ - mpi_size_t usize, vsize; - int cmp; - - mpi_normalize(u); - mpi_normalize(v); - usize = u->nlimbs; - vsize = v->nlimbs; - if (!u->sign && v->sign) - return 1; - if (u->sign && !v->sign) - return -1; - if (usize != vsize && !u->sign && !v->sign) - return usize - vsize; - if (usize != vsize && u->sign && v->sign) - return vsize + usize; - if (!usize) - return 0; - cmp = mpihelp_cmp(u->d, v->d, usize); - if (!cmp) - return 0; - if ((cmp < 0 ? 1 : 0) == (u->sign ? 1 : 0)) - return 1; - return -1; -} diff --git a/lib/mpi/mpi-div.c b/lib/mpi/mpi-div.c deleted file mode 100644 index f68cbbb4d4a4..000000000000 --- a/lib/mpi/mpi-div.c +++ /dev/null @@ -1,338 +0,0 @@ -/* mpi-div.c - MPI functions - * Copyright (C) 1994, 1996 Free Software Foundation, Inc. - * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - * - * 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. - * The GNU MP Library itself is published under the LGPL; - * however I decided to publish this code under the plain GPL. - */ - -#include <linux/string.h> -#include "mpi-internal.h" -#include "longlong.h" - -int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) -{ - int rc = -ENOMEM; - 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) { - if (mpi_copy(&temp_divisor, divisor) < 0) - goto nomem; - divisor = temp_divisor; - } - - if (mpi_tdiv_qr(NULL, rem, dividend, divisor) < 0) - goto nomem; - if (((divisor_sign ? 1 : 0) ^ (dividend->sign ? 1 : 0)) && rem->nlimbs) - if (mpi_add(rem, rem, divisor) < 0) - goto nomem; - - rc = 0; - -nomem: - if (temp_divisor) - mpi_free(temp_divisor); - return rc; -} - -/**************** - * Division rounding the quotient towards -infinity. - * The remainder gets the same sign as the denominator. - * rem is optional - */ - -ulong mpi_fdiv_r_ui(MPI rem, MPI dividend, ulong divisor) -{ - mpi_limb_t rlimb; - - rlimb = mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor); - if (rlimb && dividend->sign) - rlimb = divisor - rlimb; - - if (rem) { - rem->d[0] = rlimb; - rem->nlimbs = rlimb ? 1 : 0; - } - return rlimb; -} - -int mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor) -{ - MPI tmp = mpi_alloc(mpi_get_nlimbs(quot)); - if (!tmp) - return -ENOMEM; - mpi_fdiv_qr(quot, tmp, dividend, divisor); - mpi_free(tmp); - return 0; -} - -int 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) { - if (mpi_copy(&temp_divisor, divisor) < 0) - return -ENOMEM; - divisor = temp_divisor; - } - - if (mpi_tdiv_qr(quot, rem, dividend, divisor) < 0) - goto nomem; - - if ((divisor_sign ^ dividend->sign) && rem->nlimbs) { - if (mpi_sub_ui(quot, quot, 1) < 0) - goto nomem; - if (mpi_add(rem, rem, divisor) < 0) - goto nomem; - } - - if (temp_divisor) - mpi_free(temp_divisor); - - return 0; - -nomem: - mpi_free(temp_divisor); - return -ENOMEM; -} - -/* 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. - */ - -int mpi_tdiv_r(MPI rem, MPI num, MPI den) -{ - return mpi_tdiv_qr(NULL, rem, num, den); -} - -int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) -{ - int rc = -ENOMEM; - 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 normalization_steps; - mpi_limb_t q_limb; - mpi_ptr_t marker[5]; - int markidx = 0; - - if (!dsize) - return -EINVAL; - - memset(marker, 0, sizeof(marker)); - - /* 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; - if (mpi_resize(rem, rsize) < 0) - goto nomem; - - 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 0; - } - - if (quot) - if (mpi_resize(quot, qsize) < 0) - goto nomem; - - /* 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 0; - } - - 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); - if (!np) - goto nomem; - MPN_COPY(np, qp, nsize); - } - } else /* Put quotient at top of remainder. */ - qp = rp + dsize; - - count_leading_zeros(normalization_steps, 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); - if (!tp) - goto nomem; - 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); - if (!tp) - goto nomem; - 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; - - rc = 0; -nomem: - while (markidx) - mpi_free_limb_space(marker[--markidx]); - return rc; -} - -int mpi_tdiv_q_2exp(MPI w, MPI u, unsigned count) -{ - mpi_size_t usize, wsize; - mpi_size_t limb_cnt; - - usize = u->nlimbs; - limb_cnt = count / BITS_PER_MPI_LIMB; - wsize = usize - limb_cnt; - if (limb_cnt >= usize) - w->nlimbs = 0; - else { - mpi_ptr_t wp; - mpi_ptr_t up; - - if (RESIZE_IF_NEEDED(w, wsize) < 0) - return -ENOMEM; - wp = w->d; - up = u->d; - - count %= BITS_PER_MPI_LIMB; - if (count) { - mpihelp_rshift(wp, up + limb_cnt, wsize, count); - wsize -= !wp[wsize - 1]; - } else { - MPN_COPY_INCR(wp, up + limb_cnt, wsize); - } - - w->nlimbs = wsize; - } - return 0; -} - -/**************** - * Check whether dividend is divisible by divisor - * (note: divisor must fit into a limb) - */ -int mpi_divisible_ui(MPI dividend, ulong divisor) -{ - return !mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor); -} diff --git a/lib/mpi/mpi-gcd.c b/lib/mpi/mpi-gcd.c deleted file mode 100644 index 13c48aef9c4e..000000000000 --- a/lib/mpi/mpi-gcd.c +++ /dev/null @@ -1,59 +0,0 @@ -/* mpi-gcd.c - MPI functions - * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - */ - -#include "mpi-internal.h" - -/**************** - * Find the greatest common divisor G of A and B. - * Return: true if this 1, false in all other cases - */ -int mpi_gcd(MPI g, const MPI xa, const MPI xb) -{ - MPI a = NULL, b = NULL; - - if (mpi_copy(&a, xa) < 0) - goto nomem; - - if (mpi_copy(&b, xb) < 0) - goto nomem; - - /* TAOCP Vol II, 4.5.2, Algorithm A */ - a->sign = 0; - b->sign = 0; - while (mpi_cmp_ui(b, 0)) { - if (mpi_fdiv_r(g, a, b) < 0) /* g used as temorary variable */ - goto nomem; - if (mpi_set(a, b) < 0) - goto nomem; - if (mpi_set(b, g) < 0) - goto nomem; - } - if (mpi_set(g, a) < 0) - goto nomem; - - mpi_free(a); - mpi_free(b); - return !mpi_cmp_ui(g, 1); - -nomem: - mpi_free(a); - mpi_free(b); - return -ENOMEM; -} diff --git a/lib/mpi/mpi-inline.c b/lib/mpi/mpi-inline.c deleted file mode 100644 index 654f68aeed8b..000000000000 --- a/lib/mpi/mpi-inline.c +++ /dev/null @@ -1,31 +0,0 @@ -/* mpi-inline.c - * Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - */ - -/* put the inline functions as real functions into the lib */ -#define G10_MPI_INLINE_DECL - -#include "mpi-internal.h" - -/* always include the header becuase it is only - * included by mpi-internal if __GCC__ is defined but we - * need it here in all cases and the above definition of - * of the macro allows us to do so - */ -#include "mpi-inline.h" diff --git a/lib/mpi/mpi-inv.c b/lib/mpi/mpi-inv.c deleted file mode 100644 index 0951f9847745..000000000000 --- a/lib/mpi/mpi-inv.c +++ /dev/null @@ -1,187 +0,0 @@ -/* mpi-inv.c - MPI functions - * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - */ - -#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, const MPI a, const MPI n) -{ - /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X) - * modified according to Michael Penk's solution for Exercice 35 - * with further enhancement */ - MPI u = NULL, v = NULL; - MPI u1 = NULL, u2 = NULL, u3 = NULL; - MPI v1 = NULL, v2 = NULL, v3 = NULL; - MPI t1 = NULL, t2 = NULL, t3 = NULL; - unsigned k; - int sign; - int odd = 0; - int rc = -ENOMEM; - - if (mpi_copy(&u, a) < 0) - goto cleanup; - if (mpi_copy(&v, n) < 0) - goto cleanup; - - for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) { - if (mpi_rshift(u, u, 1) < 0) - goto cleanup; - if (mpi_rshift(v, v, 1) < 0) - goto cleanup; - } - odd = mpi_test_bit(v, 0); - - u1 = mpi_alloc_set_ui(1); - if (!u1) - goto cleanup; - if (!odd) { - u2 = mpi_alloc_set_ui(0); - if (!u2) - goto cleanup; - } - if (mpi_copy(&u3, u) < 0) - goto cleanup; - if (mpi_copy(&v1, v) < 0) - goto cleanup; - if (!odd) { - v2 = mpi_alloc(mpi_get_nlimbs(u)); - if (!v2) - goto cleanup; - if (mpi_sub(v2, u1, u) < 0) - goto cleanup; /* U is used as const 1 */ - } - if (mpi_copy(&v3, v) < 0) - goto cleanup; - if (mpi_test_bit(u, 0)) { /* u is odd */ - t1 = mpi_alloc_set_ui(0); - if (!t1) - goto cleanup; - if (!odd) { - t2 = mpi_alloc_set_ui(1); - if (!t2) - goto cleanup; - t2->sign = 1; - } - if (mpi_copy(&t3, v) < 0) - goto cleanup; - t3->sign = !t3->sign; - goto Y4; - } else { - t1 = mpi_alloc_set_ui(1); - if (!t1) - goto cleanup; - if (!odd) { - t2 = mpi_alloc_set_ui(0); - if (!t2) - goto cleanup; - } - if (mpi_copy(&t3, u) < 0) - goto cleanup; - } - do { - do { - if (!odd) { - if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) { /* one is odd */ - if (mpi_add(t1, t1, v) < 0) - goto cleanup; - if (mpi_sub(t2, t2, u) < 0) - goto cleanup; - } - if (mpi_rshift(t1, t1, 1) < 0) - goto cleanup; - if (mpi_rshift(t2, t2, 1) < 0) - goto cleanup; - if (mpi_rshift(t3, t3, 1) < 0) - goto cleanup; - } else { - if (mpi_test_bit(t1, 0)) - if (mpi_add(t1, t1, v) < 0) - goto cleanup; - if (mpi_rshift(t1, t1, 1) < 0) - goto cleanup; - if (mpi_rshift(t3, t3, 1) < 0) - goto cleanup; - } -Y4: - ; - } while (!mpi_test_bit(t3, 0)); /* while t3 is even */ - - if (!t3->sign) { - if (mpi_set(u1, t1) < 0) - goto cleanup; - if (!odd) - if (mpi_set(u2, t2) < 0) - goto cleanup; - if (mpi_set(u3, t3) < 0) - goto cleanup; - } else { - if (mpi_sub(v1, v, t1) < 0) - goto cleanup; - sign = u->sign; - u->sign = !u->sign; - if (!odd) - if (mpi_sub(v2, u, t2) < 0) - goto cleanup; - u->sign = sign; - sign = t3->sign; - t3->sign = !t3->sign; - if (mpi_set(v3, t3) < 0) - goto cleanup; - t3->sign = sign; - } - if (mpi_sub(t1, u1, v1) < 0) - goto cleanup; - if (!odd) - if (mpi_sub(t2, u2, v2) < 0) - goto cleanup; - if (mpi_sub(t3, u3, v3) < 0) - goto cleanup; - if (t1->sign) { - if (mpi_add(t1, t1, v) < 0) - goto cleanup; - if (!odd) - if (mpi_sub(t2, t2, u) < 0) - goto cleanup; - } - } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */ - /* mpi_lshift( u3, k ); */ - rc = mpi_set(x, u1); - -cleanup: - 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 rc; -} diff --git a/lib/mpi/mpi-mpow.c b/lib/mpi/mpi-mpow.c deleted file mode 100644 index 7328d0d6c748..000000000000 --- a/lib/mpi/mpi-mpow.c +++ /dev/null @@ -1,134 +0,0 @@ -/* mpi-mpow.c - MPI functions - * Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - */ - -#include "mpi-internal.h" -#include "longlong.h" - -static int build_index(const MPI *exparray, int k, int i, int t) -{ - int j, bitno; - int index = 0; - - bitno = t - i; - for (j = k - 1; j >= 0; j--) { - index <<= 1; - if (mpi_test_bit(exparray[j], bitno)) - index |= 1; - } - return index; -} - -/**************** - * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M - */ -int mpi_mulpowm(MPI res, MPI *basearray, MPI *exparray, MPI m) -{ - int rc = -ENOMEM; - int k; /* number of elements */ - int t; /* bit size of largest exponent */ - int i, j, idx; - MPI *G = NULL; /* table with precomputed values of size 2^k */ - MPI tmp = NULL; - - for (k = 0; basearray[k]; k++) - ; - if (!k) { - pr_emerg("mpi_mulpowm: assert(k) failed\n"); - BUG(); - } - for (t = 0, i = 0; (tmp = exparray[i]); i++) { - j = mpi_get_nbits(tmp); - if (j > t) - t = j; - } - if (i != k) { - pr_emerg("mpi_mulpowm: assert(i==k) failed\n"); - BUG(); - } - if (!t) { - pr_emerg("mpi_mulpowm: assert(t) failed\n"); - BUG(); - } - if (k >= 10) { - pr_emerg("mpi_mulpowm: assert(k<10) failed\n"); - BUG(); - } - - G = kzalloc((1 << k) * sizeof *G, GFP_KERNEL); - if (!G) - goto err_out; - - /* and calculate */ - tmp = mpi_alloc(mpi_get_nlimbs(m) + 1); - if (!tmp) - goto nomem; - if (mpi_set_ui(res, 1) < 0) - goto nomem; - for (i = 1; i <= t; i++) { - if (mpi_mulm(tmp, res, res, m) < 0) - goto nomem; - idx = build_index(exparray, k, i, t); - if (!(idx >= 0 && idx < (1 << k))) { - pr_emerg("mpi_mulpowm: assert(idx >= 0 && idx < (1<<k)) failed\n"); - BUG(); - } - if (!G[idx]) { - if (!idx) { - G[0] = mpi_alloc_set_ui(1); - if (!G[0]) - goto nomem; - } else { - for (j = 0; j < k; j++) { - if ((idx & (1 << j))) { - if (!G[idx]) { - if (mpi_copy - (&G[idx], - basearray[j]) < 0) - goto nomem; - } else { - if (mpi_mulm - (G[idx], G[idx], - basearray[j], - m) < 0) - goto nomem; - } - } - } - if (!G[idx]) { - G[idx] = mpi_alloc(0); - if (!G[idx]) - goto nomem; - } - } - } - if (mpi_mulm(res, tmp, G[idx], m) < 0) - goto nomem; - } - - rc = 0; -nomem: - /* cleanup */ - mpi_free(tmp); - for (i = 0; i < (1 << k); i++) - mpi_free(G[i]); - kfree(G); -err_out: - return rc; -} diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c deleted file mode 100644 index 1f3219e27292..000000000000 --- a/lib/mpi/mpi-mul.c +++ /dev/null @@ -1,194 +0,0 @@ -/* mpi-mul.c - MPI functions - * Copyright (C) 1994, 1996 Free Software Foundation, Inc. - * Copyright (C) 1998, 2001 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - * - * 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. - * The GNU MP Library itself is published under the LGPL; - * however I decided to publish this code under the plain GPL. - */ - -#include "mpi-internal.h" - -int mpi_mul_ui(MPI prod, MPI mult, unsigned long small_mult) -{ - mpi_size_t size, prod_size; - mpi_ptr_t prod_ptr; - mpi_limb_t cy; - int sign; - - size = mult->nlimbs; - sign = mult->sign; - - if (!size || !small_mult) { - prod->nlimbs = 0; - prod->sign = 0; - return 0; - } - - prod_size = size + 1; - if (prod->alloced < prod_size) - if (mpi_resize(prod, prod_size) < 0) - return -ENOMEM; - prod_ptr = prod->d; - - cy = mpihelp_mul_1(prod_ptr, mult->d, size, (mpi_limb_t) small_mult); - if (cy) - prod_ptr[size++] = cy; - prod->nlimbs = size; - prod->sign = sign; - return 0; -} - -int mpi_mul_2exp(MPI w, MPI u, unsigned long cnt) -{ - mpi_size_t usize, wsize, limb_cnt; - mpi_ptr_t wp; - mpi_limb_t wlimb; - int usign, wsign; - - usize = u->nlimbs; - usign = u->sign; - - if (!usize) { - w->nlimbs = 0; - w->sign = 0; - return 0; - } - - limb_cnt = cnt / BITS_PER_MPI_LIMB; - wsize = usize + limb_cnt + 1; - if (w->alloced < wsize) - if (mpi_resize(w, wsize) < 0) - return -ENOMEM; - wp = w->d; - wsize = usize + limb_cnt; - wsign = usign; - - cnt %= BITS_PER_MPI_LIMB; - if (cnt) { - wlimb = mpihelp_lshift(wp + limb_cnt, u->d, usize, cnt); - if (wlimb) { - wp[wsize] = wlimb; - wsize++; - } - } else { - MPN_COPY_DECR(wp + limb_cnt, u->d, usize); - } - - /* Zero all whole limbs at low end. Do it here and not before calling - * mpn_lshift, not to lose for U == W. */ - MPN_ZERO(wp, limb_cnt); - - w->nlimbs = wsize; - w->sign = wsign; - return 0; -} - -int mpi_mul(MPI w, MPI u, MPI v) -{ - int rc = -ENOMEM; - 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 < (size_t) wsize) { - if (wp == up || wp == vp) { - wp = mpi_alloc_limb_space(wsize); - if (!wp) - goto nomem; - assign_wp = 1; - } else { - if (mpi_resize(w, wsize) < 0) - goto nomem; - wp = w->d; - } - } else { /* Make U and V not overlap with W. */ - if (wp == up) { - /* W and U are identical. Allocate temporary space for U. */ - up = tmp_limb = mpi_alloc_limb_space(usize); - if (!up) - goto nomem; - /* 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); - if (!vp) - goto nomem; - /* Copy to the temporary space. */ - MPN_COPY(vp, wp, vsize); - } - } - - if (!vsize) - wsize = 0; - else { - if (mpihelp_mul(wp, up, usize, vp, vsize, &cy) < 0) - goto nomem; - wsize -= cy ? 0 : 1; - } - - if (assign_wp) - mpi_assign_limb_space(w, wp, wsize); - - w->nlimbs = wsize; - w->sign = sign_product; - rc = 0; -nomem: - if (tmp_limb) - mpi_free_limb_space(tmp_limb); - return rc; -} - -int mpi_mulm(MPI w, MPI u, MPI v, MPI m) -{ - if (mpi_mul(w, u, v) < 0) - return -ENOMEM; - return mpi_fdiv_r(w, w, m); -} diff --git a/lib/mpi/mpi-scan.c b/lib/mpi/mpi-scan.c deleted file mode 100644 index b2da5ad96199..000000000000 --- a/lib/mpi/mpi-scan.c +++ /dev/null @@ -1,136 +0,0 @@ -/* mpi-scan.c - MPI functions - * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. - * - * This file is part of GnuPG. - * - * GnuPG is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * GnuPG 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA - */ - -#include "mpi-internal.h" -#include "longlong.h" - -/**************** - * Scan through an mpi and return byte for byte. a -1 is returned to indicate - * the end of the mpi. Scanning is done from the lsb to the msb, returned - * values are in the range of 0 .. 255. - * - * FIXME: This code is VERY ugly! - */ -int mpi_getbyte(const MPI a, unsigned idx) -{ - int i, j; - unsigned n; - mpi_ptr_t ap; - mpi_limb_t limb; - - ap = a->d; - for (n = 0, i = 0; i < a->nlimbs; i++) { - limb = ap[i]; - for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++) - if (n == idx) - return (limb >> j * 8) & 0xff; - } - return -1; -} - -/**************** - * Put a value at position IDX into A. idx counts from lsb to msb - */ -void mpi_putbyte(MPI a, unsigned idx, int xc) -{ - int i, j; - unsigned n; - mpi_ptr_t ap; - mpi_limb_t limb, c; - - c = xc & 0xff; - ap = a->d; - for (n = 0, i = 0; i < a->alloced; i++) { - limb = ap[i]; - for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++) - if (n == idx) { -#if BYTES_PER_MPI_LIMB == 4 - if (j == 0) - limb = (limb & 0xffffff00) | c; - else if (j == 1) - limb = (limb & 0xffff00ff) | (c << 8); - else if (j == 2) - limb = (limb & 0xff00ffff) | (c << 16); - else - limb = (limb & 0x00ffffff) | (c << 24); -#elif BYTES_PER_MPI_LIMB == 8 - if (j == 0) - limb = (limb & 0xffffffffffffff00) | c; - else if (j == 1) - limb = - (limb & 0xffffffffffff00ff) | (c << - 8); - else if (j == 2) - limb = - (limb & 0xffffffffff00ffff) | (c << - 16); - else if (j == 3) - limb = - (limb & 0xffffffff00ffffff) | (c << - 24); - else if (j == 4) - limb = - (limb & 0xffffff00ffffffff) | (c << - 32); - else if (j == 5) - limb = - (limb & 0xffff00ffffffffff) | (c << - 40); - else if (j == 6) - limb = - (limb & 0xff00ffffffffffff) | (c << - 48); - else - limb = - (limb & 0x00ffffffffffffff) | (c << - 56); -#else -#error please enhance this function, its ugly - i know. -#endif - if (a->nlimbs <= i) - a->nlimbs = i + 1; - ap[i] = limb; - return; - } - } - log_bug("index out of range\n"); -} - -/**************** - * Count the number of zerobits at the low end of A - */ -unsigned mpi_trailing_zeros(const MPI a) -{ - unsigned n, count = 0; - - for (n = 0; n < a->nlimbs; n++) { - if (a->d[n]) { - unsigned nn; - mpi_limb_t alimb = a->d[n]; - - count_trailing_zeros(nn, alimb); - count += nn; - break; - } - count += BITS_PER_MPI_LIMB; - } - return count; - -} diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c index f26b41fcb48c..f0fa65995800 100644 --- a/lib/mpi/mpicoder.c +++ b/lib/mpi/mpicoder.c @@ -74,81 +74,6 @@ leave: EXPORT_SYMBOL_GPL(mpi_read_from_buffer); /**************** - * Make an mpi from a character string. - */ -int mpi_fromstr(MPI val, const char *str) -{ - int hexmode = 0, sign = 0, prepend_zero = 0, i, j, c, c1, c2; - unsigned nbits, nbytes, nlimbs; - mpi_limb_t a; - - if (*str == '-') { - sign = 1; - str++; - } - if (*str == '0' && str[1] == 'x') - hexmode = 1; - else - return -EINVAL; /* other bases are not yet supported */ - str += 2; - - nbits = strlen(str) * 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) - if (!mpi_resize(val, nlimbs)) - return -ENOMEM; - 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++; - assert(c1); - c2 = *str++; - assert(c2); - 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 1; - } - 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 1; - } - a <<= 8; - a |= c; - } - i = 0; - - val->d[j - 1] = a; - } - - return 0; -} -EXPORT_SYMBOL_GPL(mpi_fromstr); - -/**************** * Return an allocated buffer with the MPI (msb first). * NBYTES receives the length of this buffer. Caller must free the * return string (This function does return a 0 byte buffer with NBYTES diff --git a/lib/mpi/mpih-div.c b/lib/mpi/mpih-div.c index cde1aaec18da..c57d1d46295e 100644 --- a/lib/mpi/mpih-div.c +++ b/lib/mpi/mpih-div.c @@ -37,159 +37,6 @@ #define UDIV_TIME UMUL_TIME #endif -/* FIXME: We should be using invert_limb (or invert_normalized_limb) - * here (not udiv_qrnnd). - */ - -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; - int dummy; - - /* 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; - - count_leading_zeros(normalization_steps, 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; - - count_leading_zeros(normalization_steps, 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 @@ -387,159 +234,3 @@ 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; - int dummy; - - 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; - - count_leading_zeros(normalization_steps, 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; - - count_leading_zeros(normalization_steps, 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 c69c5eef233b..7c841719fdfb 100644 --- a/lib/mpi/mpih-mul.c +++ b/lib/mpi/mpih-mul.c @@ -330,36 +330,6 @@ mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace) } } -/* This should be made into an inline function in gmp.h. */ -int 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); - if (!tspace) - return -ENOMEM; - 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); - if (!tspace) - return -ENOMEM; - mul_n(prodp, up, vp, size, tspace); - mpi_free_limb_space(tspace); - } - } - - return 0; -} - 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 26e4ed31e256..657979f71bef 100644 --- a/lib/mpi/mpiutil.c +++ b/lib/mpi/mpiutil.c @@ -106,13 +106,6 @@ int mpi_resize(MPI a, unsigned nlimbs) return 0; } -void mpi_clear(MPI a) -{ - a->nlimbs = 0; - a->nbits = 0; - a->flags = 0; -} - void mpi_free(MPI a) { if (!a) @@ -128,84 +121,3 @@ void mpi_free(MPI a) kfree(a); } EXPORT_SYMBOL_GPL(mpi_free); - -/**************** - * Note: This copy function should not interpret the MPI - * but copy it transparently. - */ -int mpi_copy(MPI *copied, const MPI a) -{ - size_t i; - MPI b; - - *copied = NULL; - - if (a) { - b = mpi_alloc(a->nlimbs); - if (!b) - return -ENOMEM; - - b->nlimbs = a->nlimbs; - b->sign = a->sign; - b->flags = a->flags; - b->nbits = a->nbits; - - for (i = 0; i < b->nlimbs; i++) - b->d[i] = a->d[i]; - - *copied = b; - } - - return 0; -} - -int mpi_set(MPI w, const MPI u) -{ - mpi_ptr_t wp, up; - mpi_size_t usize = u->nlimbs; - int usign = u->sign; - - if (RESIZE_IF_NEEDED(w, (size_t) usize) < 0) - return -ENOMEM; - - wp = w->d; - up = u->d; - MPN_COPY(wp, up, usize); - w->nlimbs = usize; - w->nbits = u->nbits; - w->flags = u->flags; - w->sign = usign; - return 0; -} - -int mpi_set_ui(MPI w, unsigned long u) -{ - if (RESIZE_IF_NEEDED(w, 1) < 0) - return -ENOMEM; - w->d[0] = u; - w->nlimbs = u ? 1 : 0; - w->sign = 0; - w->nbits = 0; - w->flags = 0; - return 0; -} - -MPI mpi_alloc_set_ui(unsigned long u) -{ - MPI w = mpi_alloc(1); - if (!w) - return w; - w->d[0] = u; - w->nlimbs = u ? 1 : 0; - w->sign = 0; - return w; -} - -void mpi_swap(MPI a, MPI b) -{ - struct gcry_mpi tmp; - - tmp = *a; - *a = *b; - *b = tmp; -} diff --git a/lib/notifier-error-inject.c b/lib/notifier-error-inject.c new file mode 100644 index 000000000000..44b92cb6224f --- /dev/null +++ b/lib/notifier-error-inject.c @@ -0,0 +1,112 @@ +#include <linux/module.h> + +#include "notifier-error-inject.h" + +static int debugfs_errno_set(void *data, u64 val) +{ + *(int *)data = clamp_t(int, val, -MAX_ERRNO, 0); + return 0; +} + +static int debugfs_errno_get(void *data, u64 *val) +{ + *val = *(int *)data; + return 0; +} + +DEFINE_SIMPLE_ATTRIBUTE(fops_errno, debugfs_errno_get, debugfs_errno_set, + "%lld\n"); + +static struct dentry *debugfs_create_errno(const char *name, mode_t mode, + struct dentry *parent, int *value) +{ + return debugfs_create_file(name, mode, parent, value, &fops_errno); +} + +static int notifier_err_inject_callback(struct notifier_block *nb, + unsigned long val, void *p) +{ + int err = 0; + struct notifier_err_inject *err_inject = + container_of(nb, struct notifier_err_inject, nb); + struct notifier_err_inject_action *action; + + for (action = err_inject->actions; action->name; action++) { + if (action->val == val) { + err = action->error; + break; + } + } + if (err) + pr_info("Injecting error (%d) to %s\n", err, action->name); + + return notifier_from_errno(err); +} + +struct dentry *notifier_err_inject_dir; +EXPORT_SYMBOL_GPL(notifier_err_inject_dir); + +struct dentry *notifier_err_inject_init(const char *name, struct dentry *parent, + struct notifier_err_inject *err_inject, int priority) +{ + struct notifier_err_inject_action *action; + mode_t mode = S_IFREG | S_IRUSR | S_IWUSR; + struct dentry *dir; + struct dentry *actions_dir; + + err_inject->nb.notifier_call = notifier_err_inject_callback; + err_inject->nb.priority = priority; + + dir = debugfs_create_dir(name, parent); + if (!dir) + return ERR_PTR(-ENOMEM); + + actions_dir = debugfs_create_dir("actions", dir); + if (!actions_dir) + goto fail; + + for (action = err_inject->actions; action->name; action++) { + struct dentry *action_dir; + + action_dir = debugfs_create_dir(action->name, actions_dir); + if (!action_dir) + goto fail; + + /* + * Create debugfs r/w file containing action->error. If + * notifier call chain is called with action->val, it will + * fail with the error code + */ + if (!debugfs_create_errno("error", mode, action_dir, + &action->error)) + goto fail; + } + return dir; +fail: + debugfs_remove_recursive(dir); + return ERR_PTR(-ENOMEM); +} +EXPORT_SYMBOL_GPL(notifier_err_inject_init); + +static int __init err_inject_init(void) +{ + notifier_err_inject_dir = + debugfs_create_dir("notifier-error-inject", NULL); + + if (!notifier_err_inject_dir) + return -ENOMEM; + + return 0; +} + +static void __exit err_inject_exit(void) +{ + debugfs_remove_recursive(notifier_err_inject_dir); +} + +module_init(err_inject_init); +module_exit(err_inject_exit); + +MODULE_DESCRIPTION("Notifier error injection module"); +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Akinobu Mita <akinobu.mita@gmail.com>"); diff --git a/lib/notifier-error-inject.h b/lib/notifier-error-inject.h new file mode 100644 index 000000000000..99b3b6fc470b --- /dev/null +++ b/lib/notifier-error-inject.h @@ -0,0 +1,24 @@ +#include <linux/atomic.h> +#include <linux/debugfs.h> +#include <linux/notifier.h> + +struct notifier_err_inject_action { + unsigned long val; + int error; + const char *name; +}; + +#define NOTIFIER_ERR_INJECT_ACTION(action) \ + .name = #action, .val = (action), + +struct notifier_err_inject { + struct notifier_block nb; + struct notifier_err_inject_action actions[]; + /* The last slot must be terminated with zero sentinel */ +}; + +extern struct dentry *notifier_err_inject_dir; + +extern struct dentry *notifier_err_inject_init(const char *name, + struct dentry *parent, struct notifier_err_inject *err_inject, + int priority); diff --git a/lib/pSeries-reconfig-notifier-error-inject.c b/lib/pSeries-reconfig-notifier-error-inject.c new file mode 100644 index 000000000000..7f7c98dcd5c4 --- /dev/null +++ b/lib/pSeries-reconfig-notifier-error-inject.c @@ -0,0 +1,51 @@ +#include <linux/kernel.h> +#include <linux/module.h> + +#include <asm/pSeries_reconfig.h> + +#include "notifier-error-inject.h" + +static int priority; +module_param(priority, int, 0); +MODULE_PARM_DESC(priority, "specify pSeries reconfig notifier priority"); + +static struct notifier_err_inject reconfig_err_inject = { + .actions = { + { NOTIFIER_ERR_INJECT_ACTION(PSERIES_RECONFIG_ADD) }, + { NOTIFIER_ERR_INJECT_ACTION(PSERIES_RECONFIG_REMOVE) }, + { NOTIFIER_ERR_INJECT_ACTION(PSERIES_DRCONF_MEM_ADD) }, + { NOTIFIER_ERR_INJECT_ACTION(PSERIES_DRCONF_MEM_REMOVE) }, + {} + } +}; + +static struct dentry *dir; + +static int err_inject_init(void) +{ + int err; + + dir = notifier_err_inject_init("pSeries-reconfig", + notifier_err_inject_dir, &reconfig_err_inject, priority); + if (IS_ERR(dir)) + return PTR_ERR(dir); + + err = pSeries_reconfig_notifier_register(&reconfig_err_inject.nb); + if (err) + debugfs_remove_recursive(dir); + + return err; +} + +static void err_inject_exit(void) +{ + pSeries_reconfig_notifier_unregister(&reconfig_err_inject.nb); + debugfs_remove_recursive(dir); +} + +module_init(err_inject_init); +module_exit(err_inject_exit); + +MODULE_DESCRIPTION("pSeries reconfig notifier error injection module"); +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Akinobu Mita <akinobu.mita@gmail.com>"); diff --git a/lib/pm-notifier-error-inject.c b/lib/pm-notifier-error-inject.c new file mode 100644 index 000000000000..c094b2dedc23 --- /dev/null +++ b/lib/pm-notifier-error-inject.c @@ -0,0 +1,49 @@ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/suspend.h> + +#include "notifier-error-inject.h" + +static int priority; +module_param(priority, int, 0); +MODULE_PARM_DESC(priority, "specify PM notifier priority"); + +static struct notifier_err_inject pm_notifier_err_inject = { + .actions = { + { NOTIFIER_ERR_INJECT_ACTION(PM_HIBERNATION_PREPARE) }, + { NOTIFIER_ERR_INJECT_ACTION(PM_SUSPEND_PREPARE) }, + { NOTIFIER_ERR_INJECT_ACTION(PM_RESTORE_PREPARE) }, + {} + } +}; + +static struct dentry *dir; + +static int err_inject_init(void) +{ + int err; + + dir = notifier_err_inject_init("pm", notifier_err_inject_dir, + &pm_notifier_err_inject, priority); + if (IS_ERR(dir)) + return PTR_ERR(dir); + + err = register_pm_notifier(&pm_notifier_err_inject.nb); + if (err) + debugfs_remove_recursive(dir); + + return err; +} + +static void err_inject_exit(void) +{ + unregister_pm_notifier(&pm_notifier_err_inject.nb); + debugfs_remove_recursive(dir); +} + +module_init(err_inject_init); +module_exit(err_inject_exit); + +MODULE_DESCRIPTION("PM notifier error injection module"); +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Akinobu Mita <akinobu.mita@gmail.com>"); diff --git a/lib/radix-tree.c b/lib/radix-tree.c index d7c878cc006c..e7964296fd50 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -686,6 +686,9 @@ void **radix_tree_next_chunk(struct radix_tree_root *root, * during iterating; it can be zero only at the beginning. * And we cannot overflow iter->next_index in a single step, * because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG. + * + * This condition also used by radix_tree_next_slot() to stop + * contiguous iterating, and forbid swithing to the next chunk. */ index = iter->next_index; if (!index && iter->index) diff --git a/lib/raid6/recov.c b/lib/raid6/recov.c index 1805a5cc5daa..a95bccb8497d 100644 --- a/lib/raid6/recov.c +++ b/lib/raid6/recov.c @@ -22,8 +22,8 @@ #include <linux/raid/pq.h> /* Recover two failed data blocks. */ -void raid6_2data_recov_intx1(int disks, size_t bytes, int faila, int failb, - void **ptrs) +static void raid6_2data_recov_intx1(int disks, size_t bytes, int faila, + int failb, void **ptrs) { u8 *p, *q, *dp, *dq; u8 px, qx, db; @@ -66,7 +66,8 @@ void raid6_2data_recov_intx1(int disks, size_t bytes, int faila, int failb, } /* Recover failure of one data block plus the P block */ -void raid6_datap_recov_intx1(int disks, size_t bytes, int faila, void **ptrs) +static void raid6_datap_recov_intx1(int disks, size_t bytes, int faila, + void **ptrs) { u8 *p, *q, *dq; const u8 *qmul; /* Q multiplier table */ diff --git a/lib/raid6/recov_ssse3.c b/lib/raid6/recov_ssse3.c index 37ae61930559..ecb710c0b4d9 100644 --- a/lib/raid6/recov_ssse3.c +++ b/lib/raid6/recov_ssse3.c @@ -19,8 +19,8 @@ static int raid6_has_ssse3(void) boot_cpu_has(X86_FEATURE_SSSE3); } -void raid6_2data_recov_ssse3(int disks, size_t bytes, int faila, int failb, - void **ptrs) +static void raid6_2data_recov_ssse3(int disks, size_t bytes, int faila, + int failb, void **ptrs) { u8 *p, *q, *dp, *dq; const u8 *pbmul; /* P multiplier table for B data */ @@ -194,7 +194,8 @@ void raid6_2data_recov_ssse3(int disks, size_t bytes, int faila, int failb, } -void raid6_datap_recov_ssse3(int disks, size_t bytes, int faila, void **ptrs) +static void raid6_datap_recov_ssse3(int disks, size_t bytes, int faila, + void **ptrs) { u8 *p, *q, *dq; const u8 *qmul; /* Q multiplier table */ diff --git a/lib/scatterlist.c b/lib/scatterlist.c index 6096e89bee55..fadae774a20c 100644 --- a/lib/scatterlist.c +++ b/lib/scatterlist.c @@ -279,14 +279,6 @@ int __sg_alloc_table(struct sg_table *table, unsigned int nents, if (!left) sg_mark_end(&sg[sg_size - 1]); - /* - * only really needed for mempool backed sg allocations (like - * SCSI), a possible improvement here would be to pass the - * table pointer into the allocator and let that clear these - * flags - */ - gfp_mask &= ~__GFP_WAIT; - gfp_mask |= __GFP_HIGH; prv = sg; } while (left); @@ -319,6 +311,70 @@ int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask) EXPORT_SYMBOL(sg_alloc_table); /** + * sg_alloc_table_from_pages - Allocate and initialize an sg table from + * an array of pages + * @sgt: The sg table header to use + * @pages: Pointer to an array of page pointers + * @n_pages: Number of pages in the pages array + * @offset: Offset from start of the first page to the start of a buffer + * @size: Number of valid bytes in the buffer (after offset) + * @gfp_mask: GFP allocation mask + * + * Description: + * Allocate and initialize an sg table from a list of pages. Contiguous + * ranges of the pages are squashed into a single scatterlist node. A user + * may provide an offset at a start and a size of valid data in a buffer + * specified by the page array. The returned sg table is released by + * sg_free_table. + * + * Returns: + * 0 on success, negative error on failure + */ +int sg_alloc_table_from_pages(struct sg_table *sgt, + struct page **pages, unsigned int n_pages, + unsigned long offset, unsigned long size, + gfp_t gfp_mask) +{ + unsigned int chunks; + unsigned int i; + unsigned int cur_page; + int ret; + struct scatterlist *s; + + /* compute number of contiguous chunks */ + chunks = 1; + for (i = 1; i < n_pages; ++i) + if (page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) + ++chunks; + + ret = sg_alloc_table(sgt, chunks, gfp_mask); + if (unlikely(ret)) + return ret; + + /* merging chunks and putting them into the scatterlist */ + cur_page = 0; + for_each_sg(sgt->sgl, s, sgt->orig_nents, i) { + unsigned long chunk_size; + unsigned int j; + + /* look for the end of the current chunk */ + for (j = cur_page + 1; j < n_pages; ++j) + if (page_to_pfn(pages[j]) != + page_to_pfn(pages[j - 1]) + 1) + break; + + chunk_size = ((j - cur_page) << PAGE_SHIFT) - offset; + sg_set_page(s, pages[cur_page], min(size, chunk_size), offset); + size -= chunk_size; + offset = 0; + cur_page = j; + } + + return 0; +} +EXPORT_SYMBOL(sg_alloc_table_from_pages); + +/** * sg_miter_start - start mapping iteration over a sg list * @miter: sg mapping iter to be started * @sgl: sg list to iterate over diff --git a/lib/spinlock_debug.c b/lib/spinlock_debug.c index d0ec4f3d1593..eb10578ae055 100644 --- a/lib/spinlock_debug.c +++ b/lib/spinlock_debug.c @@ -58,7 +58,7 @@ static void spin_dump(raw_spinlock_t *lock, const char *msg) printk(KERN_EMERG "BUG: spinlock %s on CPU#%d, %s/%d\n", msg, raw_smp_processor_id(), current->comm, task_pid_nr(current)); - printk(KERN_EMERG " lock: %ps, .magic: %08x, .owner: %s/%d, " + printk(KERN_EMERG " lock: %pS, .magic: %08x, .owner: %s/%d, " ".owner_cpu: %d\n", lock, lock->magic, owner ? owner->comm : "<none>", @@ -118,7 +118,7 @@ static void __spin_lock_debug(raw_spinlock_t *lock) /* lockup suspected: */ if (print_once) { print_once = 0; - spin_dump(lock, "lockup"); + spin_dump(lock, "lockup suspected"); #ifdef CONFIG_SMP trigger_all_cpu_backtrace(); #endif diff --git a/lib/vsprintf.c b/lib/vsprintf.c index c3f36d415bdf..0e337541f005 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -655,6 +655,50 @@ char *resource_string(char *buf, char *end, struct resource *res, } static noinline_for_stack +char *hex_string(char *buf, char *end, u8 *addr, struct printf_spec spec, + const char *fmt) +{ + int i, len = 1; /* if we pass '%ph[CDN]', field witdh remains + negative value, fallback to the default */ + char separator; + + if (spec.field_width == 0) + /* nothing to print */ + return buf; + + if (ZERO_OR_NULL_PTR(addr)) + /* NULL pointer */ + return string(buf, end, NULL, spec); + + switch (fmt[1]) { + case 'C': + separator = ':'; + break; + case 'D': + separator = '-'; + break; + case 'N': + separator = 0; + break; + default: + separator = ' '; + break; + } + + if (spec.field_width > 0) + len = min_t(int, spec.field_width, 64); + + for (i = 0; i < len && buf < end - 1; i++) { + buf = hex_byte_pack(buf, addr[i]); + + if (buf < end && separator && i != len - 1) + *buf++ = separator; + } + + return buf; +} + +static noinline_for_stack char *mac_address_string(char *buf, char *end, u8 *addr, struct printf_spec spec, const char *fmt) { @@ -662,15 +706,28 @@ char *mac_address_string(char *buf, char *end, u8 *addr, char *p = mac_addr; int i; char separator; + bool reversed = false; - if (fmt[1] == 'F') { /* FDDI canonical format */ + switch (fmt[1]) { + case 'F': separator = '-'; - } else { + break; + + case 'R': + reversed = true; + /* fall through */ + + default: separator = ':'; + break; } for (i = 0; i < 6; i++) { - p = hex_byte_pack(p, addr[i]); + if (reversed) + p = hex_byte_pack(p, addr[5 - i]); + else + p = hex_byte_pack(p, addr[i]); + if (fmt[0] == 'M' && i != 5) *p++ = separator; } @@ -933,6 +990,7 @@ int kptr_restrict __read_mostly; * - 'm' For a 6-byte MAC address, it prints the hex address without colons * - 'MF' For a 6-byte MAC FDDI address, it prints the address * with a dash-separated hex notation + * - '[mM]R For a 6-byte MAC address, Reverse order (Bluetooth) * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4) * IPv6 uses colon separated network-order 16 bit hex with leading 0's @@ -960,6 +1018,13 @@ int kptr_restrict __read_mostly; * correctness of the format string and va_list arguments. * - 'K' For a kernel pointer that should be hidden from unprivileged users * - 'NF' For a netdev_features_t + * - 'h[CDN]' For a variable-length buffer, it prints it as a hex string with + * a certain separator (' ' by default): + * C colon + * D dash + * N no separator + * The maximum supported length is 64 bytes of the input. Consider + * to use print_hex_dump() for the larger input. * * Note: The difference between 'S' and 'F' is that on ia64 and ppc64 * function pointers are really function descriptors, which contain a @@ -993,9 +1058,12 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr, case 'R': case 'r': return resource_string(buf, end, ptr, spec, fmt); + case 'h': + return hex_string(buf, end, ptr, spec, fmt); case 'M': /* Colon separated: 00:01:02:03:04:05 */ case 'm': /* Contiguous: 000102030405 */ - /* [mM]F (FDDI, bit reversed) */ + /* [mM]F (FDDI) */ + /* [mM]R (Reverse order; Bluetooth) */ return mac_address_string(buf, end, ptr, spec, fmt); case 'I': /* Formatted IP supported * 4: 1.2.3.4 @@ -1030,7 +1098,8 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr, * %pK cannot be used in IRQ context because its test * for CAP_SYSLOG would be meaningless. */ - if (in_irq() || in_serving_softirq() || in_nmi()) { + if (kptr_restrict && (in_irq() || in_serving_softirq() || + in_nmi())) { if (spec.field_width == -1) spec.field_width = default_width; return string(buf, end, "pK-error", spec); @@ -1280,8 +1349,12 @@ qualifier: * %pI6c print an IPv6 address as specified by RFC 5952 * %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper * case. + * %*ph[CDN] a variable-length hex string with a separator (supports up to 64 + * bytes of the input) * %n is ignored * + * ** Please update Documentation/printk-formats.txt when making changes ** + * * The return value is the number of characters which would * be generated for the given input, excluding the trailing * '\0', as per ISO C99. If you want to have the exact |