diff options
| author | Ingo Molnar <mingo@kernel.org> | 2012-08-21 11:27:00 +0200 |
|---|---|---|
| committer | Ingo Molnar <mingo@kernel.org> | 2012-08-21 11:27:00 +0200 |
| commit | bcada3d4b8c96b8792c2306f363992ca5ab9da42 (patch) | |
| tree | e420679a5db6ea4e1694eef57f9abb6acac8d4d3 /lib | |
| parent | Merge branch 'tip/perf/core' of git://git.kernel.org/pub/scm/linux/kernel/git... (diff) | |
| parent | perf hists: Rename and move some functions (diff) | |
| download | linux-bcada3d4b8c96b8792c2306f363992ca5ab9da42.tar.gz linux-bcada3d4b8c96b8792c2306f363992ca5ab9da42.zip | |
Merge tag 'perf-core-for-mingo' of git://git.kernel.org/pub/scm/linux/kernel/git/acme/linux into perf/core
Pull perf/core improvements and fixes from Arnaldo Carvalho de Melo:
* Fix include order for bison/flex-generated C files, from Ben Hutchings
* Build fixes and documentation corrections from David Ahern
* Group parsing support, from Jiri Olsa
* UI/gtk refactorings and improvements from Namhyung Kim
* NULL deref fix for perf script, from Namhyung Kim
* Assorted cleanups from Robert Richter
* Let O= makes handle relative paths, from Steven Rostedt
* perf script python fixes, from Feng Tang.
* Improve 'perf lock' error message when the needed tracepoints
are not present, from David Ahern.
* Initial bash completion support, from Frederic Weisbecker
* Allow building without libelf, from Namhyung Kim.
* Support DWARF CFI based unwind to have callchains when %bp
based unwinding is not possible, from Jiri Olsa.
* Symbol resolution fixes, while fixing support PPC64 files with an .opt ELF
section was the end goal, several fixes for code that handles all
architectures and cleanups are included, from Cody Schafer.
* Add a description for the JIT interface, from Andi Kleen.
* Assorted fixes for Documentation and build in 32 bit, from Robert Richter
* Add support for non-tracepoint events in perf script python, from Feng Tang
* Cache the libtraceevent event_format associated to each evsel early, so that we
avoid relookups, i.e. calling pevent_find_event repeatedly when processing
tracepoint events.
[ This is to reduce the surface contact with libtraceevents and make clear what
is that the perf tools needs from that lib: so far parsing the common and per
event fields. ]
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Diffstat (limited to 'lib')
41 files changed, 901 insertions, 2137 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 ff5bdee4716d..2403a63b5da5 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -714,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. @@ -1084,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 8c31a0cb75e9..42d283edc4d3 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -11,7 +11,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ rbtree.o radix-tree.o dump_stack.o timerqueue.o\ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ - proportions.o prio_heap.o ratelimit.o show_mem.o \ + proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o lib-$(CONFIG_MMU) += ioremap.o @@ -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/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/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/flex_proportions.c b/lib/flex_proportions.c new file mode 100644 index 000000000000..c785554f9523 --- /dev/null +++ b/lib/flex_proportions.c @@ -0,0 +1,272 @@ +/* + * Floating proportions with flexible aging period + * + * Copyright (C) 2011, SUSE, Jan Kara <jack@suse.cz> + * + * The goal of this code is: Given different types of event, measure proportion + * of each type of event over time. The proportions are measured with + * exponentially decaying history to give smooth transitions. A formula + * expressing proportion of event of type 'j' is: + * + * p_{j} = (\Sum_{i>=0} x_{i,j}/2^{i+1})/(\Sum_{i>=0} x_i/2^{i+1}) + * + * Where x_{i,j} is j's number of events in i-th last time period and x_i is + * total number of events in i-th last time period. + * + * Note that p_{j}'s are normalised, i.e. + * + * \Sum_{j} p_{j} = 1, + * + * This formula can be straightforwardly computed by maintaing denominator + * (let's call it 'd') and for each event type its numerator (let's call it + * 'n_j'). When an event of type 'j' happens, we simply need to do: + * n_j++; d++; + * + * When a new period is declared, we could do: + * d /= 2 + * for each j + * n_j /= 2 + * + * To avoid iteration over all event types, we instead shift numerator of event + * j lazily when someone asks for a proportion of event j or when event j + * occurs. This can bit trivially implemented by remembering last period in + * which something happened with proportion of type j. + */ +#include <linux/flex_proportions.h> + +int fprop_global_init(struct fprop_global *p) +{ + int err; + + p->period = 0; + /* Use 1 to avoid dealing with periods with 0 events... */ + err = percpu_counter_init(&p->events, 1); + if (err) + return err; + seqcount_init(&p->sequence); + return 0; +} + +void fprop_global_destroy(struct fprop_global *p) +{ + percpu_counter_destroy(&p->events); +} + +/* + * Declare @periods new periods. It is upto the caller to make sure period + * transitions cannot happen in parallel. + * + * The function returns true if the proportions are still defined and false + * if aging zeroed out all events. This can be used to detect whether declaring + * further periods has any effect. + */ +bool fprop_new_period(struct fprop_global *p, int periods) +{ + u64 events; + unsigned long flags; + + local_irq_save(flags); + events = percpu_counter_sum(&p->events); + /* + * Don't do anything if there are no events. + */ + if (events <= 1) { + local_irq_restore(flags); + return false; + } + write_seqcount_begin(&p->sequence); + if (periods < 64) + events -= events >> periods; + /* Use addition to avoid losing events happening between sum and set */ + percpu_counter_add(&p->events, -events); + p->period += periods; + write_seqcount_end(&p->sequence); + local_irq_restore(flags); + + return true; +} + +/* + * ---- SINGLE ---- + */ + +int fprop_local_init_single(struct fprop_local_single *pl) +{ + pl->events = 0; + pl->period = 0; + raw_spin_lock_init(&pl->lock); + return 0; +} + +void fprop_local_destroy_single(struct fprop_local_single *pl) +{ +} + +static void fprop_reflect_period_single(struct fprop_global *p, + struct fprop_local_single *pl) +{ + unsigned int period = p->period; + unsigned long flags; + + /* Fast path - period didn't change */ + if (pl->period == period) + return; + raw_spin_lock_irqsave(&pl->lock, flags); + /* Someone updated pl->period while we were spinning? */ + if (pl->period >= period) { + raw_spin_unlock_irqrestore(&pl->lock, flags); + return; + } + /* Aging zeroed our fraction? */ + if (period - pl->period < BITS_PER_LONG) + pl->events >>= period - pl->period; + else + pl->events = 0; + pl->period = period; + raw_spin_unlock_irqrestore(&pl->lock, flags); +} + +/* Event of type pl happened */ +void __fprop_inc_single(struct fprop_global *p, struct fprop_local_single *pl) +{ + fprop_reflect_period_single(p, pl); + pl->events++; + percpu_counter_add(&p->events, 1); +} + +/* Return fraction of events of type pl */ +void fprop_fraction_single(struct fprop_global *p, + struct fprop_local_single *pl, + unsigned long *numerator, unsigned long *denominator) +{ + unsigned int seq; + s64 num, den; + + do { + seq = read_seqcount_begin(&p->sequence); + fprop_reflect_period_single(p, pl); + num = pl->events; + den = percpu_counter_read_positive(&p->events); + } while (read_seqcount_retry(&p->sequence, seq)); + + /* + * Make fraction <= 1 and denominator > 0 even in presence of percpu + * counter errors + */ + if (den <= num) { + if (num) + den = num; + else + den = 1; + } + *denominator = den; + *numerator = num; +} + +/* + * ---- PERCPU ---- + */ +#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids))) + +int fprop_local_init_percpu(struct fprop_local_percpu *pl) +{ + int err; + + err = percpu_counter_init(&pl->events, 0); + if (err) + return err; + pl->period = 0; + raw_spin_lock_init(&pl->lock); + return 0; +} + +void fprop_local_destroy_percpu(struct fprop_local_percpu *pl) +{ + percpu_counter_destroy(&pl->events); +} + +static void fprop_reflect_period_percpu(struct fprop_global *p, + struct fprop_local_percpu *pl) +{ + unsigned int period = p->period; + unsigned long flags; + + /* Fast path - period didn't change */ + if (pl->period == period) + return; + raw_spin_lock_irqsave(&pl->lock, flags); + /* Someone updated pl->period while we were spinning? */ + if (pl->period >= period) { + raw_spin_unlock_irqrestore(&pl->lock, flags); + return; + } + /* Aging zeroed our fraction? */ + if (period - pl->period < BITS_PER_LONG) { + s64 val = percpu_counter_read(&pl->events); + + if (val < (nr_cpu_ids * PROP_BATCH)) + val = percpu_counter_sum(&pl->events); + + __percpu_counter_add(&pl->events, + -val + (val >> (period-pl->period)), PROP_BATCH); + } else + percpu_counter_set(&pl->events, 0); + pl->period = period; + raw_spin_unlock_irqrestore(&pl->lock, flags); +} + +/* Event of type pl happened */ +void __fprop_inc_percpu(struct fprop_global *p, struct fprop_local_percpu *pl) +{ + fprop_reflect_period_percpu(p, pl); + __percpu_counter_add(&pl->events, 1, PROP_BATCH); + percpu_counter_add(&p->events, 1); +} + +void fprop_fraction_percpu(struct fprop_global *p, + struct fprop_local_percpu *pl, + unsigned long *numerator, unsigned long *denominator) +{ + unsigned int seq; + s64 num, den; + + do { + seq = read_seqcount_begin(&p->sequence); + fprop_reflect_period_percpu(p, pl); + num = percpu_counter_read_positive(&pl->events); + den = percpu_counter_read_positive(&p->events); + } while (read_seqcount_retry(&p->sequence, seq)); + + /* + * Make fraction <= 1 and denominator > 0 even in presence of percpu + * counter errors + */ + if (den <= num) { + if (num) + den = num; + else + den = 1; + } + *denominator = den; + *numerator = num; +} + +/* + * Like __fprop_inc_percpu() except that event is counted only if the given + * type has fraction smaller than @max_frac/FPROP_FRAC_BASE + */ +void __fprop_inc_percpu_max(struct fprop_global *p, + struct fprop_local_percpu *pl, int max_frac) +{ + if (unlikely(max_frac < FPROP_FRAC_BASE)) { + unsigned long numerator, denominator; + + fprop_fraction_percpu(p, pl, &numerator, &denominator); + if (numerator > + (((u64)denominator) * max_frac) >> FPROP_FRAC_SHIFT) + return; + } else + fprop_reflect_period_percpu(p, pl); + __percpu_counter_add(&pl->events, 1, PROP_BATCH); + percpu_counter_add(&p->events, 1); +} 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/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/percpu_counter.c b/lib/percpu_counter.c index f8a3f1a829b8..ba6085d9c741 100644 --- a/lib/percpu_counter.c +++ b/lib/percpu_counter.c @@ -12,7 +12,7 @@ #ifdef CONFIG_HOTPLUG_CPU static LIST_HEAD(percpu_counters); -static DEFINE_MUTEX(percpu_counters_lock); +static DEFINE_SPINLOCK(percpu_counters_lock); #endif #ifdef CONFIG_DEBUG_OBJECTS_PERCPU_COUNTER @@ -123,9 +123,9 @@ int __percpu_counter_init(struct percpu_counter *fbc, s64 amount, #ifdef CONFIG_HOTPLUG_CPU INIT_LIST_HEAD(&fbc->list); - mutex_lock(&percpu_counters_lock); + spin_lock(&percpu_counters_lock); list_add(&fbc->list, &percpu_counters); - mutex_unlock(&percpu_counters_lock); + spin_unlock(&percpu_counters_lock); #endif return 0; } @@ -139,9 +139,9 @@ void percpu_counter_destroy(struct percpu_counter *fbc) debug_percpu_counter_deactivate(fbc); #ifdef CONFIG_HOTPLUG_CPU - mutex_lock(&percpu_counters_lock); + spin_lock(&percpu_counters_lock); list_del(&fbc->list); - mutex_unlock(&percpu_counters_lock); + spin_unlock(&percpu_counters_lock); #endif free_percpu(fbc->counters); fbc->counters = NULL; @@ -170,7 +170,7 @@ static int __cpuinit percpu_counter_hotcpu_callback(struct notifier_block *nb, return NOTIFY_OK; cpu = (unsigned long)hcpu; - mutex_lock(&percpu_counters_lock); + spin_lock(&percpu_counters_lock); list_for_each_entry(fbc, &percpu_counters, list) { s32 *pcount; unsigned long flags; @@ -181,7 +181,7 @@ static int __cpuinit percpu_counter_hotcpu_callback(struct notifier_block *nb, *pcount = 0; raw_spin_unlock_irqrestore(&fbc->lock, flags); } - mutex_unlock(&percpu_counters_lock); + spin_unlock(&percpu_counters_lock); #endif return NOTIFY_OK; } 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/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 e91fbc23fff1..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>", 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 |