aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig17
-rw-r--r--lib/Kconfig.debug93
-rw-r--r--lib/Makefile14
-rw-r--r--lib/atomic64_test.c5
-rw-r--r--lib/cpu-notifier-error-inject.c63
-rw-r--r--lib/crc32.c2
-rw-r--r--lib/div64.c2
-rw-r--r--lib/fdt.c2
-rw-r--r--lib/fdt_ro.c2
-rw-r--r--lib/fdt_rw.c2
-rw-r--r--lib/fdt_strerror.c2
-rw-r--r--lib/fdt_sw.c2
-rw-r--r--lib/fdt_wip.c2
-rw-r--r--lib/flex_proportions.c272
-rw-r--r--lib/kobject_uevent.c5
-rw-r--r--lib/list_debug.c6
-rw-r--r--lib/memory-notifier-error-inject.c48
-rw-r--r--lib/memweight.c38
-rw-r--r--lib/mpi/Makefile11
-rw-r--r--lib/mpi/generic_mpi-asm-defs.h4
-rw-r--r--lib/mpi/mpi-add.c234
-rw-r--r--lib/mpi/mpi-bit.c162
-rw-r--r--lib/mpi/mpi-cmp.c68
-rw-r--r--lib/mpi/mpi-div.c338
-rw-r--r--lib/mpi/mpi-gcd.c59
-rw-r--r--lib/mpi/mpi-inline.c31
-rw-r--r--lib/mpi/mpi-inv.c187
-rw-r--r--lib/mpi/mpi-mpow.c134
-rw-r--r--lib/mpi/mpi-mul.c194
-rw-r--r--lib/mpi/mpi-scan.c136
-rw-r--r--lib/mpi/mpicoder.c75
-rw-r--r--lib/mpi/mpih-div.c309
-rw-r--r--lib/mpi/mpih-mul.c30
-rw-r--r--lib/mpi/mpiutil.c88
-rw-r--r--lib/notifier-error-inject.c112
-rw-r--r--lib/notifier-error-inject.h24
-rw-r--r--lib/pSeries-reconfig-notifier-error-inject.c51
-rw-r--r--lib/percpu_counter.c14
-rw-r--r--lib/pm-notifier-error-inject.c49
-rw-r--r--lib/scatterlist.c72
-rw-r--r--lib/spinlock_debug.c2
-rw-r--r--lib/vsprintf.c83
42 files changed, 903 insertions, 2141 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
340config GENERIC_ATOMIC64 340config GENERIC_ATOMIC64
341 bool 341 bool
342 342
343config ARCH_HAS_ATOMIC64_DEC_IF_POSITIVE
344 def_bool y if GENERIC_ATOMIC64
345
343config LRU_CACHE 346config LRU_CACHE
344 tristate 347 tristate
345 348
@@ -378,14 +381,6 @@ config MPILIB
378 It is used to implement RSA digital signature verification, 381 It is used to implement RSA digital signature verification,
379 which is used by IMA/EVM digital signature extension. 382 which is used by IMA/EVM digital signature extension.
380 383
381config MPILIB_EXTRA
382 bool
383 depends on MPILIB
384 help
385 Additional sources of multiprecision maths library from GnuPG.
386 This code is unnecessary for RSA digital signature verification,
387 but can be compiled if needed.
388
389config SIGNATURE 384config SIGNATURE
390 tristate 385 tristate
391 depends on KEYS && CRYPTO 386 depends on KEYS && CRYPTO
@@ -395,4 +390,10 @@ config SIGNATURE
395 Digital signature verification. Currently only RSA is supported. 390 Digital signature verification. Currently only RSA is supported.
396 Implementation is done using GnuPG MPI library 391 Implementation is done using GnuPG MPI library
397 392
393#
394# libfdt files, only selected if needed.
395#
396config LIBFDT
397 bool
398
398endmenu 399endmenu
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
714 714
715config DEBUG_STACK_USAGE 715config DEBUG_STACK_USAGE
716 bool "Stack utilization instrumentation" 716 bool "Stack utilization instrumentation"
717 depends on DEBUG_KERNEL 717 depends on DEBUG_KERNEL && !IA64 && !PARISC
718 help 718 help
719 Enables the display of the minimum amount of free stack which each 719 Enables the display of the minimum amount of free stack which each
720 task has ever had available in the sysrq-T and sysrq-P debug output. 720 task has ever had available in the sysrq-T and sysrq-P debug output.
@@ -1084,18 +1084,105 @@ config LKDTM
1084 Documentation on how to use the module can be found in 1084 Documentation on how to use the module can be found in
1085 Documentation/fault-injection/provoke-crashes.txt 1085 Documentation/fault-injection/provoke-crashes.txt
1086 1086
1087config NOTIFIER_ERROR_INJECTION
1088 tristate "Notifier error injection"
1089 depends on DEBUG_KERNEL
1090 select DEBUG_FS
1091 help
1092 This option provides the ability to inject artifical errors to
1093 specified notifier chain callbacks. It is useful to test the error
1094 handling of notifier call chain failures.
1095
1096 Say N if unsure.
1097
1087config CPU_NOTIFIER_ERROR_INJECT 1098config CPU_NOTIFIER_ERROR_INJECT
1088 tristate "CPU notifier error injection module" 1099 tristate "CPU notifier error injection module"
1089 depends on HOTPLUG_CPU && DEBUG_KERNEL 1100 depends on HOTPLUG_CPU && NOTIFIER_ERROR_INJECTION
1090 help 1101 help
1091 This option provides a kernel module that can be used to test 1102 This option provides a kernel module that can be used to test
1092 the error handling of the cpu notifiers 1103 the error handling of the cpu notifiers by injecting artifical
1104 errors to CPU notifier chain callbacks. It is controlled through
1105 debugfs interface under /sys/kernel/debug/notifier-error-inject/cpu
1106
1107 If the notifier call chain should be failed with some events
1108 notified, write the error code to "actions/<notifier event>/error".
1109
1110 Example: Inject CPU offline error (-1 == -EPERM)
1111
1112 # cd /sys/kernel/debug/notifier-error-inject/cpu
1113 # echo -1 > actions/CPU_DOWN_PREPARE/error
1114 # echo 0 > /sys/devices/system/cpu/cpu1/online
1115 bash: echo: write error: Operation not permitted
1093 1116
1094 To compile this code as a module, choose M here: the module will 1117 To compile this code as a module, choose M here: the module will
1095 be called cpu-notifier-error-inject. 1118 be called cpu-notifier-error-inject.
1096 1119
1097 If unsure, say N. 1120 If unsure, say N.
1098 1121
1122config PM_NOTIFIER_ERROR_INJECT
1123 tristate "PM notifier error injection module"
1124 depends on PM && NOTIFIER_ERROR_INJECTION
1125 default m if PM_DEBUG
1126 help
1127 This option provides the ability to inject artifical errors to
1128 PM notifier chain callbacks. It is controlled through debugfs
1129 interface /sys/kernel/debug/notifier-error-inject/pm
1130
1131 If the notifier call chain should be failed with some events
1132 notified, write the error code to "actions/<notifier event>/error".
1133
1134 Example: Inject PM suspend error (-12 = -ENOMEM)
1135
1136 # cd /sys/kernel/debug/notifier-error-inject/pm/
1137 # echo -12 > actions/PM_SUSPEND_PREPARE/error
1138 # echo mem > /sys/power/state
1139 bash: echo: write error: Cannot allocate memory
1140
1141 To compile this code as a module, choose M here: the module will
1142 be called pm-notifier-error-inject.
1143
1144 If unsure, say N.
1145
1146config MEMORY_NOTIFIER_ERROR_INJECT
1147 tristate "Memory hotplug notifier error injection module"
1148 depends on MEMORY_HOTPLUG_SPARSE && NOTIFIER_ERROR_INJECTION
1149 help
1150 This option provides the ability to inject artifical errors to
1151 memory hotplug notifier chain callbacks. It is controlled through
1152 debugfs interface under /sys/kernel/debug/notifier-error-inject/memory
1153
1154 If the notifier call chain should be failed with some events
1155 notified, write the error code to "actions/<notifier event>/error".
1156
1157 Example: Inject memory hotplug offline error (-12 == -ENOMEM)
1158
1159 # cd /sys/kernel/debug/notifier-error-inject/memory
1160 # echo -12 > actions/MEM_GOING_OFFLINE/error
1161 # echo offline > /sys/devices/system/memory/memoryXXX/state
1162 bash: echo: write error: Cannot allocate memory
1163
1164 To compile this code as a module, choose M here: the module will
1165 be called pSeries-reconfig-notifier-error-inject.
1166
1167 If unsure, say N.
1168
1169config PSERIES_RECONFIG_NOTIFIER_ERROR_INJECT
1170 tristate "pSeries reconfig notifier error injection module"
1171 depends on PPC_PSERIES && NOTIFIER_ERROR_INJECTION
1172 help
1173 This option provides the ability to inject artifical errors to
1174 pSeries reconfig notifier chain callbacks. It is controlled
1175 through debugfs interface under
1176 /sys/kernel/debug/notifier-error-inject/pSeries-reconfig/
1177
1178 If the notifier call chain should be failed with some events
1179 notified, write the error code to "actions/<notifier event>/error".
1180
1181 To compile this code as a module, choose M here: the module will
1182 be called memory-notifier-error-inject.
1183
1184 If unsure, say N.
1185
1099config FAULT_INJECTION 1186config FAULT_INJECTION
1100 bool "Fault-injection framework" 1187 bool "Fault-injection framework"
1101 depends on DEBUG_KERNEL 1188 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 \
11 rbtree.o radix-tree.o dump_stack.o timerqueue.o\ 11 rbtree.o radix-tree.o dump_stack.o timerqueue.o\
12 idr.o int_sqrt.o extable.o prio_tree.o \ 12 idr.o int_sqrt.o extable.o prio_tree.o \
13 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ 13 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
14 proportions.o prio_heap.o ratelimit.o show_mem.o \ 14 proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \
15 is_single_threaded.o plist.o decompress.o 15 is_single_threaded.o plist.o decompress.o
16 16
17lib-$(CONFIG_MMU) += ioremap.o 17lib-$(CONFIG_MMU) += ioremap.o
@@ -22,7 +22,7 @@ lib-y += kobject.o klist.o
22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ 22obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ 23 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
24 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \ 24 string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o \
25 bsearch.o find_last_bit.o find_next_bit.o llist.o 25 bsearch.o find_last_bit.o find_next_bit.o llist.o memweight.o
26obj-y += kstrtox.o 26obj-y += kstrtox.o
27obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o 27obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
28 28
@@ -90,7 +90,12 @@ obj-$(CONFIG_AUDIT_GENERIC) += audit.o
90obj-$(CONFIG_SWIOTLB) += swiotlb.o 90obj-$(CONFIG_SWIOTLB) += swiotlb.o
91obj-$(CONFIG_IOMMU_HELPER) += iommu-helper.o 91obj-$(CONFIG_IOMMU_HELPER) += iommu-helper.o
92obj-$(CONFIG_FAULT_INJECTION) += fault-inject.o 92obj-$(CONFIG_FAULT_INJECTION) += fault-inject.o
93obj-$(CONFIG_NOTIFIER_ERROR_INJECTION) += notifier-error-inject.o
93obj-$(CONFIG_CPU_NOTIFIER_ERROR_INJECT) += cpu-notifier-error-inject.o 94obj-$(CONFIG_CPU_NOTIFIER_ERROR_INJECT) += cpu-notifier-error-inject.o
95obj-$(CONFIG_PM_NOTIFIER_ERROR_INJECT) += pm-notifier-error-inject.o
96obj-$(CONFIG_MEMORY_NOTIFIER_ERROR_INJECT) += memory-notifier-error-inject.o
97obj-$(CONFIG_PSERIES_RECONFIG_NOTIFIER_ERROR_INJECT) += \
98 pSeries-reconfig-notifier-error-inject.o
94 99
95lib-$(CONFIG_GENERIC_BUG) += bug.o 100lib-$(CONFIG_GENERIC_BUG) += bug.o
96 101
@@ -130,6 +135,11 @@ obj-$(CONFIG_GENERIC_STRNLEN_USER) += strnlen_user.o
130 135
131obj-$(CONFIG_STMP_DEVICE) += stmp_device.o 136obj-$(CONFIG_STMP_DEVICE) += stmp_device.o
132 137
138libfdt_files = fdt.o fdt_ro.o fdt_wip.o fdt_rw.o fdt_sw.o fdt_strerror.o
139$(foreach file, $(libfdt_files), \
140 $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt))
141lib-$(CONFIG_LIBFDT) += $(libfdt_files)
142
133hostprogs-y := gen_crc32table 143hostprogs-y := gen_crc32table
134clean-files := crc32table.h 144clean-files := crc32table.h
135 145
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)
114 r += one; 114 r += one;
115 BUG_ON(v.counter != r); 115 BUG_ON(v.counter != r);
116 116
117#if defined(CONFIG_X86) || defined(CONFIG_MIPS) || defined(CONFIG_PPC) || \ 117#ifdef CONFIG_ARCH_HAS_ATOMIC64_DEC_IF_POSITIVE
118 defined(CONFIG_S390) || defined(_ASM_GENERIC_ATOMIC64_H) || defined(CONFIG_ARM)
119 INIT(onestwos); 118 INIT(onestwos);
120 BUG_ON(atomic64_dec_if_positive(&v) != (onestwos - 1)); 119 BUG_ON(atomic64_dec_if_positive(&v) != (onestwos - 1));
121 r -= one; 120 r -= one;
@@ -129,7 +128,7 @@ static __init int test_atomic64(void)
129 BUG_ON(atomic64_dec_if_positive(&v) != (-one - one)); 128 BUG_ON(atomic64_dec_if_positive(&v) != (-one - one));
130 BUG_ON(v.counter != r); 129 BUG_ON(v.counter != r);
131#else 130#else
132#warning Please implement atomic64_dec_if_positive for your architecture, and add it to the IF above 131#warning Please implement atomic64_dec_if_positive for your architecture and select the above Kconfig symbol
133#endif 132#endif
134 133
135 INIT(onestwos); 134 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 @@
1#include <linux/kernel.h> 1#include <linux/kernel.h>
2#include <linux/cpu.h>
3#include <linux/module.h> 2#include <linux/module.h>
4#include <linux/notifier.h> 3#include <linux/cpu.h>
5 4
6static int priority; 5#include "notifier-error-inject.h"
7static int cpu_up_prepare_error;
8static int cpu_down_prepare_error;
9 6
7static int priority;
10module_param(priority, int, 0); 8module_param(priority, int, 0);
11MODULE_PARM_DESC(priority, "specify cpu notifier priority"); 9MODULE_PARM_DESC(priority, "specify cpu notifier priority");
12 10
13module_param(cpu_up_prepare_error, int, 0644); 11static struct notifier_err_inject cpu_notifier_err_inject = {
14MODULE_PARM_DESC(cpu_up_prepare_error, 12 .actions = {
15 "specify error code to inject CPU_UP_PREPARE action"); 13 { NOTIFIER_ERR_INJECT_ACTION(CPU_UP_PREPARE) },
16 14 { NOTIFIER_ERR_INJECT_ACTION(CPU_UP_PREPARE_FROZEN) },
17module_param(cpu_down_prepare_error, int, 0644); 15 { NOTIFIER_ERR_INJECT_ACTION(CPU_DOWN_PREPARE) },
18MODULE_PARM_DESC(cpu_down_prepare_error, 16 { NOTIFIER_ERR_INJECT_ACTION(CPU_DOWN_PREPARE_FROZEN) },
19 "specify error code to inject CPU_DOWN_PREPARE action"); 17 {}
20
21static int err_inject_cpu_callback(struct notifier_block *nfb,
22 unsigned long action, void *hcpu)
23{
24 int err = 0;
25
26 switch (action) {
27 case CPU_UP_PREPARE:
28 case CPU_UP_PREPARE_FROZEN:
29 err = cpu_up_prepare_error;
30 break;
31 case CPU_DOWN_PREPARE:
32 case CPU_DOWN_PREPARE_FROZEN:
33 err = cpu_down_prepare_error;
34 break;
35 } 18 }
36 if (err)
37 printk(KERN_INFO "Injecting error (%d) at cpu notifier\n", err);
38
39 return notifier_from_errno(err);
40}
41
42static struct notifier_block err_inject_cpu_notifier = {
43 .notifier_call = err_inject_cpu_callback,
44}; 19};
45 20
21static struct dentry *dir;
22
46static int err_inject_init(void) 23static int err_inject_init(void)
47{ 24{
48 err_inject_cpu_notifier.priority = priority; 25 int err;
26
27 dir = notifier_err_inject_init("cpu", notifier_err_inject_dir,
28 &cpu_notifier_err_inject, priority);
29 if (IS_ERR(dir))
30 return PTR_ERR(dir);
31
32 err = register_hotcpu_notifier(&cpu_notifier_err_inject.nb);
33 if (err)
34 debugfs_remove_recursive(dir);
49 35
50 return register_hotcpu_notifier(&err_inject_cpu_notifier); 36 return err;
51} 37}
52 38
53static void err_inject_exit(void) 39static void err_inject_exit(void)
54{ 40{
55 unregister_hotcpu_notifier(&err_inject_cpu_notifier); 41 unregister_hotcpu_notifier(&cpu_notifier_err_inject.nb);
42 debugfs_remove_recursive(dir);
56} 43}
57 44
58module_init(err_inject_init); 45module_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])
74 size_t i; 74 size_t i;
75# endif 75# endif
76 const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3]; 76 const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
77# if CRC_LE_BITS != 32
77 const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7]; 78 const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7];
79# endif
78 u32 q; 80 u32 q;
79 81
80 /* Align it */ 82 /* 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);
87 * by the book 'Hacker's Delight'. The original source and full proof 87 * by the book 'Hacker's Delight'. The original source and full proof
88 * can be found here and is available for use without restriction. 88 * can be found here and is available for use without restriction.
89 * 89 *
90 * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c' 90 * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c.txt'
91 */ 91 */
92#ifndef div64_u64 92#ifndef div64_u64
93u64 div64_u64(u64 dividend, u64 divisor) 93u64 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 @@
1#include <linux/libfdt_env.h>
2#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 @@
1#include <linux/libfdt_env.h>
2#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 @@
1#include <linux/libfdt_env.h>
2#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 @@
1#include <linux/libfdt_env.h>
2#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 @@
1#include <linux/libfdt_env.h>
2#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 @@
1#include <linux/libfdt_env.h>
2#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 @@
1/*
2 * Floating proportions with flexible aging period
3 *
4 * Copyright (C) 2011, SUSE, Jan Kara <jack@suse.cz>
5 *
6 * The goal of this code is: Given different types of event, measure proportion
7 * of each type of event over time. The proportions are measured with
8 * exponentially decaying history to give smooth transitions. A formula
9 * expressing proportion of event of type 'j' is:
10 *
11 * p_{j} = (\Sum_{i>=0} x_{i,j}/2^{i+1})/(\Sum_{i>=0} x_i/2^{i+1})
12 *
13 * Where x_{i,j} is j's number of events in i-th last time period and x_i is
14 * total number of events in i-th last time period.
15 *
16 * Note that p_{j}'s are normalised, i.e.
17 *
18 * \Sum_{j} p_{j} = 1,
19 *
20 * This formula can be straightforwardly computed by maintaing denominator
21 * (let's call it 'd') and for each event type its numerator (let's call it
22 * 'n_j'). When an event of type 'j' happens, we simply need to do:
23 * n_j++; d++;
24 *
25 * When a new period is declared, we could do:
26 * d /= 2
27 * for each j
28 * n_j /= 2
29 *
30 * To avoid iteration over all event types, we instead shift numerator of event
31 * j lazily when someone asks for a proportion of event j or when event j
32 * occurs. This can bit trivially implemented by remembering last period in
33 * which something happened with proportion of type j.
34 */
35#include <linux/flex_proportions.h>
36
37int fprop_global_init(struct fprop_global *p)
38{
39 int err;
40
41 p->period = 0;
42 /* Use 1 to avoid dealing with periods with 0 events... */
43 err = percpu_counter_init(&p->events, 1);
44 if (err)
45 return err;
46 seqcount_init(&p->sequence);
47 return 0;
48}
49
50void fprop_global_destroy(struct fprop_global *p)
51{
52 percpu_counter_destroy(&p->events);
53}
54
55/*
56 * Declare @periods new periods. It is upto the caller to make sure period
57 * transitions cannot happen in parallel.
58 *
59 * The function returns true if the proportions are still defined and false
60 * if aging zeroed out all events. This can be used to detect whether declaring
61 * further periods has any effect.
62 */
63bool fprop_new_period(struct fprop_global *p, int periods)
64{
65 u64 events;
66 unsigned long flags;
67
68 local_irq_save(flags);
69 events = percpu_counter_sum(&p->events);
70 /*
71 * Don't do anything if there are no events.
72 */
73 if (events <= 1) {
74 local_irq_restore(flags);
75 return false;
76 }
77 write_seqcount_begin(&p->sequence);
78 if (periods < 64)
79 events -= events >> periods;
80 /* Use addition to avoid losing events happening between sum and set */
81 percpu_counter_add(&p->events, -events);
82 p->period += periods;
83 write_seqcount_end(&p->sequence);
84 local_irq_restore(flags);
85
86 return true;
87}
88
89/*
90 * ---- SINGLE ----
91 */
92
93int fprop_local_init_single(struct fprop_local_single *pl)
94{
95 pl->events = 0;
96 pl->period = 0;
97 raw_spin_lock_init(&pl->lock);
98 return 0;
99}
100
101void fprop_local_destroy_single(struct fprop_local_single *pl)
102{
103}
104
105static void fprop_reflect_period_single(struct fprop_global *p,
106 struct fprop_local_single *pl)
107{
108 unsigned int period = p->period;
109 unsigned long flags;
110
111 /* Fast path - period didn't change */
112 if (pl->period == period)
113 return;
114 raw_spin_lock_irqsave(&pl->lock, flags);
115 /* Someone updated pl->period while we were spinning? */
116 if (pl->period >= period) {
117 raw_spin_unlock_irqrestore(&pl->lock, flags);
118 return;
119 }
120 /* Aging zeroed our fraction? */
121 if (period - pl->period < BITS_PER_LONG)
122 pl->events >>= period - pl->period;
123 else
124 pl->events = 0;
125 pl->period = period;
126 raw_spin_unlock_irqrestore(&pl->lock, flags);
127}
128
129/* Event of type pl happened */
130void __fprop_inc_single(struct fprop_global *p, struct fprop_local_single *pl)
131{
132 fprop_reflect_period_single(p, pl);
133 pl->events++;
134 percpu_counter_add(&p->events, 1);
135}
136
137/* Return fraction of events of type pl */
138void fprop_fraction_single(struct fprop_global *p,
139 struct fprop_local_single *pl,
140 unsigned long *numerator, unsigned long *denominator)
141{
142 unsigned int seq;
143 s64 num, den;
144
145 do {
146 seq = read_seqcount_begin(&p->sequence);
147 fprop_reflect_period_single(p, pl);
148 num = pl->events;
149 den = percpu_counter_read_positive(&p->events);
150 } while (read_seqcount_retry(&p->sequence, seq));
151
152 /*
153 * Make fraction <= 1 and denominator > 0 even in presence of percpu
154 * counter errors
155 */
156 if (den <= num) {
157 if (num)
158 den = num;
159 else
160 den = 1;
161 }
162 *denominator = den;
163 *numerator = num;
164}
165
166/*
167 * ---- PERCPU ----
168 */
169#define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
170
171int fprop_local_init_percpu(struct fprop_local_percpu *pl)
172{
173 int err;
174
175 err = percpu_counter_init(&pl->events, 0);
176 if (err)
177 return err;
178 pl->period = 0;
179 raw_spin_lock_init(&pl->lock);
180 return 0;
181}
182
183void fprop_local_destroy_percpu(struct fprop_local_percpu *pl)
184{
185 percpu_counter_destroy(&pl->events);
186}
187
188static void fprop_reflect_period_percpu(struct fprop_global *p,
189 struct fprop_local_percpu *pl)
190{
191 unsigned int period = p->period;
192 unsigned long flags;
193
194 /* Fast path - period didn't change */
195 if (pl->period == period)
196 return;
197 raw_spin_lock_irqsave(&pl->lock, flags);
198 /* Someone updated pl->period while we were spinning? */
199 if (pl->period >= period) {
200 raw_spin_unlock_irqrestore(&pl->lock, flags);
201 return;
202 }
203 /* Aging zeroed our fraction? */
204 if (period - pl->period < BITS_PER_LONG) {
205 s64 val = percpu_counter_read(&pl->events);
206
207 if (val < (nr_cpu_ids * PROP_BATCH))
208 val = percpu_counter_sum(&pl->events);
209
210 __percpu_counter_add(&pl->events,
211 -val + (val >> (period-pl->period)), PROP_BATCH);
212 } else
213 percpu_counter_set(&pl->events, 0);
214 pl->period = period;
215 raw_spin_unlock_irqrestore(&pl->lock, flags);
216}
217
218/* Event of type pl happened */
219void __fprop_inc_percpu(struct fprop_global *p, struct fprop_local_percpu *pl)
220{
221 fprop_reflect_period_percpu(p, pl);
222 __percpu_counter_add(&pl->events, 1, PROP_BATCH);
223 percpu_counter_add(&p->events, 1);
224}
225
226void fprop_fraction_percpu(struct fprop_global *p,
227 struct fprop_local_percpu *pl,
228 unsigned long *numerator, unsigned long *denominator)
229{
230 unsigned int seq;
231 s64 num, den;
232
233 do {
234 seq = read_seqcount_begin(&p->sequence);
235 fprop_reflect_period_percpu(p, pl);
236 num = percpu_counter_read_positive(&pl->events);
237 den = percpu_counter_read_positive(&p->events);
238 } while (read_seqcount_retry(&p->sequence, seq));
239
240 /*
241 * Make fraction <= 1 and denominator > 0 even in presence of percpu
242 * counter errors
243 */
244 if (den <= num) {
245 if (num)
246 den = num;
247 else
248 den = 1;
249 }
250 *denominator = den;
251 *numerator = num;
252}
253
254/*
255 * Like __fprop_inc_percpu() except that event is counted only if the given
256 * type has fraction smaller than @max_frac/FPROP_FRAC_BASE
257 */
258void __fprop_inc_percpu_max(struct fprop_global *p,
259 struct fprop_local_percpu *pl, int max_frac)
260{
261 if (unlikely(max_frac < FPROP_FRAC_BASE)) {
262 unsigned long numerator, denominator;
263
264 fprop_fraction_percpu(p, pl, &numerator, &denominator);
265 if (numerator >
266 (((u64)denominator) * max_frac) >> FPROP_FRAC_SHIFT)
267 return;
268 } else
269 fprop_reflect_period_percpu(p, pl);
270 __percpu_counter_add(&pl->events, 1, PROP_BATCH);
271 percpu_counter_add(&p->events, 1);
272}
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);
373static int uevent_net_init(struct net *net) 373static int uevent_net_init(struct net *net)
374{ 374{
375 struct uevent_sock *ue_sk; 375 struct uevent_sock *ue_sk;
376 struct netlink_kernel_cfg cfg = {
377 .groups = 1,
378 };
376 379
377 ue_sk = kzalloc(sizeof(*ue_sk), GFP_KERNEL); 380 ue_sk = kzalloc(sizeof(*ue_sk), GFP_KERNEL);
378 if (!ue_sk) 381 if (!ue_sk)
379 return -ENOMEM; 382 return -ENOMEM;
380 383
381 ue_sk->sk = netlink_kernel_create(net, NETLINK_KOBJECT_UEVENT, 384 ue_sk->sk = netlink_kernel_create(net, NETLINK_KOBJECT_UEVENT,
382 1, NULL, NULL, THIS_MODULE); 385 THIS_MODULE, &cfg);
383 if (!ue_sk->sk) { 386 if (!ue_sk->sk) {
384 printk(KERN_ERR 387 printk(KERN_ERR
385 "kobject_uevent: unable to create netlink socket!\n"); 388 "kobject_uevent: unable to create netlink socket!\n");
diff --git a/lib/list_debug.c b/lib/list_debug.c
index 23a5e031cd8b..c24c2f7e296f 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -87,12 +87,10 @@ void __list_add_rcu(struct list_head *new,
87 struct list_head *prev, struct list_head *next) 87 struct list_head *prev, struct list_head *next)
88{ 88{
89 WARN(next->prev != prev, 89 WARN(next->prev != prev,
90 "list_add_rcu corruption. next->prev should be " 90 "list_add_rcu corruption. next->prev should be prev (%p), but was %p. (next=%p).\n",
91 "prev (%p), but was %p. (next=%p).\n",
92 prev, next->prev, next); 91 prev, next->prev, next);
93 WARN(prev->next != next, 92 WARN(prev->next != next,
94 "list_add_rcu corruption. prev->next should be " 93 "list_add_rcu corruption. prev->next should be next (%p), but was %p. (prev=%p).\n",
95 "next (%p), but was %p. (prev=%p).\n",
96 next, prev->next, prev); 94 next, prev->next, prev);
97 new->next = next; 95 new->next = next;
98 new->prev = prev; 96 new->prev = prev;
diff --git a/lib/memory-notifier-error-inject.c b/lib/memory-notifier-error-inject.c
new file mode 100644
index 000000000000..e6239bf0b0df
--- /dev/null
+++ b/lib/memory-notifier-error-inject.c
@@ -0,0 +1,48 @@
1#include <linux/kernel.h>
2#include <linux/module.h>
3#include <linux/memory.h>
4
5#include "notifier-error-inject.h"
6
7static int priority;
8module_param(priority, int, 0);
9MODULE_PARM_DESC(priority, "specify memory notifier priority");
10
11static struct notifier_err_inject memory_notifier_err_inject = {
12 .actions = {
13 { NOTIFIER_ERR_INJECT_ACTION(MEM_GOING_ONLINE) },
14 { NOTIFIER_ERR_INJECT_ACTION(MEM_GOING_OFFLINE) },
15 {}
16 }
17};
18
19static struct dentry *dir;
20
21static int err_inject_init(void)
22{
23 int err;
24
25 dir = notifier_err_inject_init("memory", notifier_err_inject_dir,
26 &memory_notifier_err_inject, priority);
27 if (IS_ERR(dir))
28 return PTR_ERR(dir);
29
30 err = register_memory_notifier(&memory_notifier_err_inject.nb);
31 if (err)
32 debugfs_remove_recursive(dir);
33
34 return err;
35}
36
37static void err_inject_exit(void)
38{
39 unregister_memory_notifier(&memory_notifier_err_inject.nb);
40 debugfs_remove_recursive(dir);
41}
42
43module_init(err_inject_init);
44module_exit(err_inject_exit);
45
46MODULE_DESCRIPTION("memory notifier error injection module");
47MODULE_LICENSE("GPL");
48MODULE_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 @@
1#include <linux/export.h>
2#include <linux/bug.h>
3#include <linux/bitmap.h>
4
5/**
6 * memweight - count the total number of bits set in memory area
7 * @ptr: pointer to the start of the area
8 * @bytes: the size of the area
9 */
10size_t memweight(const void *ptr, size_t bytes)
11{
12 size_t ret = 0;
13 size_t longs;
14 const unsigned char *bitmap = ptr;
15
16 for (; bytes > 0 && ((unsigned long)bitmap) % sizeof(long);
17 bytes--, bitmap++)
18 ret += hweight8(*bitmap);
19
20 longs = bytes / sizeof(long);
21 if (longs) {
22 BUG_ON(longs >= INT_MAX / BITS_PER_LONG);
23 ret += bitmap_weight((unsigned long *)bitmap,
24 longs * BITS_PER_LONG);
25 bytes -= longs * sizeof(long);
26 bitmap += longs * sizeof(long);
27 }
28 /*
29 * The reason that this last loop is distinct from the preceding
30 * bitmap_weight() call is to compute 1-bits in the last region smaller
31 * than sizeof(long) properly on big-endian systems.
32 */
33 for (; bytes > 0; bytes--, bitmap++)
34 ret += hweight8(*bitmap);
35
36 return ret;
37}
38EXPORT_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 = \
19 mpih-mul.o \ 19 mpih-mul.o \
20 mpi-pow.o \ 20 mpi-pow.o \
21 mpiutil.o 21 mpiutil.o
22
23mpi-$(CONFIG_MPILIB_EXTRA) += \
24 mpi-add.o \
25 mpi-div.o \
26 mpi-cmp.o \
27 mpi-gcd.o \
28 mpi-inline.o \
29 mpi-inv.o \
30 mpi-mpow.o \
31 mpi-mul.o \
32 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 @@
1/* This file defines some basic constants for the MPI machinery. We
2 * need to define the types on a per-CPU basis, so it is done with
3 * this file here. */
4#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 @@
1/* mpi-add.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
4 *
5 * This file is part of GnuPG.
6 *
7 * GnuPG is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * GnuPG is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
20 *
21 * Note: This code is heavily based on the GNU MP Library.
22 * Actually it's the same code with only minor changes in the
23 * way the data is stored; this is to support the abstraction
24 * of an optional secure memory allocation which may be used
25 * to avoid revealing of sensitive data due to paging etc.
26 * The GNU MP Library itself is published under the LGPL;
27 * however I decided to publish this code under the plain GPL.
28 */
29
30#include "mpi-internal.h"
31
32/****************
33 * Add the unsigned integer V to the mpi-integer U and store the
34 * result in W. U and V may be the same.
35 */
36int mpi_add_ui(MPI w, const MPI u, unsigned long v)
37{
38 mpi_ptr_t wp, up;
39 mpi_size_t usize, wsize;
40 int usign, wsign;
41
42 usize = u->nlimbs;
43 usign = u->sign;
44 wsign = 0;
45
46 /* If not space for W (and possible carry), increase space. */
47 wsize = usize + 1;
48 if (w->alloced < wsize)
49 if (mpi_resize(w, wsize) < 0)
50 return -ENOMEM;
51
52 /* These must be after realloc (U may be the same as W). */
53 up = u->d;
54 wp = w->d;
55
56 if (!usize) { /* simple */
57 wp[0] = v;
58 wsize = v ? 1 : 0;
59 } else if (!usign) { /* mpi is not negative */
60 mpi_limb_t cy;
61 cy = mpihelp_add_1(wp, up, usize, v);
62 wp[usize] = cy;
63 wsize = usize + cy;
64 } else { /* The signs are different. Need exact comparison to determine
65 * which operand to subtract from which. */
66 if (usize == 1 && up[0] < v) {
67 wp[0] = v - up[0];
68 wsize = 1;
69 } else {
70 mpihelp_sub_1(wp, up, usize, v);
71 /* Size can decrease with at most one limb. */
72 wsize = usize - (wp[usize - 1] == 0);
73 wsign = 1;
74 }
75 }
76
77 w->nlimbs = wsize;
78 w->sign = wsign;
79 return 0;
80}
81
82int mpi_add(MPI w, MPI u, MPI v)
83{
84 mpi_ptr_t wp, up, vp;
85 mpi_size_t usize, vsize, wsize;
86 int usign, vsign, wsign;
87
88 if (u->nlimbs < v->nlimbs) { /* Swap U and V. */
89 usize = v->nlimbs;
90 usign = v->sign;
91 vsize = u->nlimbs;
92 vsign = u->sign;
93 wsize = usize + 1;
94 if (RESIZE_IF_NEEDED(w, wsize) < 0)
95 return -ENOMEM;
96 /* These must be after realloc (u or v may be the same as w). */
97 up = v->d;
98 vp = u->d;
99 } else {
100 usize = u->nlimbs;
101 usign = u->sign;
102 vsize = v->nlimbs;
103 vsign = v->sign;
104 wsize = usize + 1;
105 if (RESIZE_IF_NEEDED(w, wsize) < 0)
106 return -ENOMEM;
107 /* These must be after realloc (u or v may be the same as w). */
108 up = u->d;
109 vp = v->d;
110 }
111 wp = w->d;
112 wsign = 0;
113
114 if (!vsize) { /* simple */
115 MPN_COPY(wp, up, usize);
116 wsize = usize;
117 wsign = usign;
118 } else if (usign != vsign) { /* different sign */
119 /* This test is right since USIZE >= VSIZE */
120 if (usize != vsize) {
121 mpihelp_sub(wp, up, usize, vp, vsize);
122 wsize = usize;
123 MPN_NORMALIZE(wp, wsize);
124 wsign = usign;
125 } else if (mpihelp_cmp(up, vp, usize) < 0) {
126 mpihelp_sub_n(wp, vp, up, usize);
127 wsize = usize;
128 MPN_NORMALIZE(wp, wsize);
129 if (!usign)
130 wsign = 1;
131 } else {
132 mpihelp_sub_n(wp, up, vp, usize);
133 wsize = usize;
134 MPN_NORMALIZE(wp, wsize);
135 if (usign)
136 wsign = 1;
137 }
138 } else { /* U and V have same sign. Add them. */
139 mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
140 wp[usize] = cy;
141 wsize = usize + cy;
142 if (usign)
143 wsign = 1;
144 }
145
146 w->nlimbs = wsize;
147 w->sign = wsign;
148 return 0;
149}
150
151/****************
152 * Subtract the unsigned integer V from the mpi-integer U and store the
153 * result in W.
154 */
155int mpi_sub_ui(MPI w, MPI u, unsigned long v)
156{
157 mpi_ptr_t wp, up;
158 mpi_size_t usize, wsize;
159 int usign, wsign;
160
161 usize = u->nlimbs;
162 usign = u->sign;
163 wsign = 0;
164
165 /* If not space for W (and possible carry), increase space. */
166 wsize = usize + 1;
167 if (w->alloced < wsize)
168 if (mpi_resize(w, wsize) < 0)
169 return -ENOMEM;
170
171 /* These must be after realloc (U may be the same as W). */
172 up = u->d;
173 wp = w->d;
174
175 if (!usize) { /* simple */
176 wp[0] = v;
177 wsize = v ? 1 : 0;
178 wsign = 1;
179 } else if (usign) { /* mpi and v are negative */
180 mpi_limb_t cy;
181 cy = mpihelp_add_1(wp, up, usize, v);
182 wp[usize] = cy;
183 wsize = usize + cy;
184 } else { /* The signs are different. Need exact comparison to determine
185 * which operand to subtract from which. */
186 if (usize == 1 && up[0] < v) {
187 wp[0] = v - up[0];
188 wsize = 1;
189 wsign = 1;
190 } else {
191 mpihelp_sub_1(wp, up, usize, v);
192 /* Size can decrease with at most one limb. */
193 wsize = usize - (wp[usize - 1] == 0);
194 }
195 }
196
197 w->nlimbs = wsize;
198 w->sign = wsign;
199 return 0;
200}
201
202int mpi_sub(MPI w, MPI u, MPI v)
203{
204 int rc;
205
206 if (w == v) {
207 MPI vv;
208 if (mpi_copy(&vv, v) < 0)
209 return -ENOMEM;
210 vv->sign = !vv->sign;
211 rc = mpi_add(w, u, vv);
212 mpi_free(vv);
213 } else {
214 /* fixme: this is not thread-save (we temp. modify v) */
215 v->sign = !v->sign;
216 rc = mpi_add(w, u, v);
217 v->sign = !v->sign;
218 }
219 return rc;
220}
221
222int mpi_addm(MPI w, MPI u, MPI v, MPI m)
223{
224 if (mpi_add(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
225 return -ENOMEM;
226 return 0;
227}
228
229int mpi_subm(MPI w, MPI u, MPI v, MPI m)
230{
231 if (mpi_sub(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
232 return -ENOMEM;
233 return 0;
234}
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)
54 return n; 54 return n;
55} 55}
56EXPORT_SYMBOL_GPL(mpi_get_nbits); 56EXPORT_SYMBOL_GPL(mpi_get_nbits);
57
58/****************
59 * Test whether bit N is set.
60 */
61int mpi_test_bit(MPI a, unsigned n)
62{
63 unsigned limbno, bitno;
64 mpi_limb_t limb;
65
66 limbno = n / BITS_PER_MPI_LIMB;
67 bitno = n % BITS_PER_MPI_LIMB;
68
69 if (limbno >= a->nlimbs)
70 return 0; /* too far left: this is a 0 */
71 limb = a->d[limbno];
72 return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
73}
74
75/****************
76 * Set bit N of A.
77 */
78int mpi_set_bit(MPI a, unsigned n)
79{
80 unsigned limbno, bitno;
81
82 limbno = n / BITS_PER_MPI_LIMB;
83 bitno = n % BITS_PER_MPI_LIMB;
84
85 if (limbno >= a->nlimbs) { /* resize */
86 if (a->alloced >= limbno)
87 if (mpi_resize(a, limbno + 1) < 0)
88 return -ENOMEM;
89 a->nlimbs = limbno + 1;
90 }
91 a->d[limbno] |= (A_LIMB_1 << bitno);
92 return 0;
93}
94
95/****************
96 * Set bit N of A. and clear all bits above
97 */
98int mpi_set_highbit(MPI a, unsigned n)
99{
100 unsigned limbno, bitno;
101
102 limbno = n / BITS_PER_MPI_LIMB;
103 bitno = n % BITS_PER_MPI_LIMB;
104
105 if (limbno >= a->nlimbs) { /* resize */
106 if (a->alloced >= limbno)
107 if (mpi_resize(a, limbno + 1) < 0)
108 return -ENOMEM;
109 a->nlimbs = limbno + 1;
110 }
111 a->d[limbno] |= (A_LIMB_1 << bitno);
112 for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
113 a->d[limbno] &= ~(A_LIMB_1 << bitno);
114 a->nlimbs = limbno + 1;
115 return 0;
116}
117
118/****************
119 * clear bit N of A and all bits above
120 */
121void mpi_clear_highbit(MPI a, unsigned n)
122{
123 unsigned limbno, bitno;
124
125 limbno = n / BITS_PER_MPI_LIMB;
126 bitno = n % BITS_PER_MPI_LIMB;
127
128 if (limbno >= a->nlimbs)
129 return; /* not allocated, so need to clear bits :-) */
130
131 for (; bitno < BITS_PER_MPI_LIMB; bitno++)
132 a->d[limbno] &= ~(A_LIMB_1 << bitno);
133 a->nlimbs = limbno + 1;
134}
135
136/****************
137 * Clear bit N of A.
138 */
139void mpi_clear_bit(MPI a, unsigned n)
140{
141 unsigned limbno, bitno;
142
143 limbno = n / BITS_PER_MPI_LIMB;
144 bitno = n % BITS_PER_MPI_LIMB;
145
146 if (limbno >= a->nlimbs)
147 return; /* don't need to clear this bit, it's to far to left */
148 a->d[limbno] &= ~(A_LIMB_1 << bitno);
149}
150
151/****************
152 * Shift A by N bits to the right
153 * FIXME: should use alloc_limb if X and A are same.
154 */
155int mpi_rshift(MPI x, MPI a, unsigned n)
156{
157 mpi_ptr_t xp;
158 mpi_size_t xsize;
159
160 xsize = a->nlimbs;
161 x->sign = a->sign;
162 if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0)
163 return -ENOMEM;
164 xp = x->d;
165
166 if (xsize) {
167 mpihelp_rshift(xp, a->d, xsize, n);
168 MPN_NORMALIZE(xp, xsize);
169 }
170 x->nlimbs = xsize;
171 return 0;
172}
173
174/****************
175 * Shift A by COUNT limbs to the left
176 * This is used only within the MPI library
177 */
178int mpi_lshift_limbs(MPI a, unsigned int count)
179{
180 const int n = a->nlimbs;
181 mpi_ptr_t ap;
182 int i;
183
184 if (!count || !n)
185 return 0;
186
187 if (RESIZE_IF_NEEDED(a, n + count) < 0)
188 return -ENOMEM;
189
190 ap = a->d;
191 for (i = n - 1; i >= 0; i--)
192 ap[i + count] = ap[i];
193 for (i = 0; i < count; i++)
194 ap[i] = 0;
195 a->nlimbs += count;
196 return 0;
197}
198
199/****************
200 * Shift A by COUNT limbs to the right
201 * This is used only within the MPI library
202 */
203void mpi_rshift_limbs(MPI a, unsigned int count)
204{
205 mpi_ptr_t ap = a->d;
206 mpi_size_t n = a->nlimbs;
207 unsigned int i;
208
209 if (count >= n) {
210 a->nlimbs = 0;
211 return;
212 }
213
214 for (i = 0; i < n - count; i++)
215 ap[i] = ap[i + count];
216 ap[i] = 0;
217 a->nlimbs -= count;
218}
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 @@
1/* mpi-cmp.c - MPI functions
2 * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * GnuPG is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19 */
20
21#include "mpi-internal.h"
22
23int mpi_cmp_ui(MPI u, unsigned long v)
24{
25 mpi_limb_t limb = v;
26
27 mpi_normalize(u);
28 if (!u->nlimbs && !limb)
29 return 0;
30 if (u->sign)
31 return -1;
32 if (u->nlimbs > 1)
33 return 1;
34
35 if (u->d[0] == limb)
36 return 0;
37 else if (u->d[0] > limb)
38 return 1;
39 else
40 return -1;
41}
42
43int mpi_cmp(MPI u, MPI v)
44{
45 mpi_size_t usize, vsize;
46 int cmp;
47
48 mpi_normalize(u);
49 mpi_normalize(v);
50 usize = u->nlimbs;
51 vsize = v->nlimbs;
52 if (!u->sign && v->sign)
53 return 1;
54 if (u->sign && !v->sign)
55 return -1;
56 if (usize != vsize && !u->sign && !v->sign)
57 return usize - vsize;
58 if (usize != vsize && u->sign && v->sign)
59 return vsize + usize;
60 if (!usize)
61 return 0;
62 cmp = mpihelp_cmp(u->d, v->d, usize);
63 if (!cmp)
64 return 0;
65 if ((cmp < 0 ? 1 : 0) == (u->sign ? 1 : 0))
66 return 1;
67 return -1;
68}
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 @@
1/* mpi-div.c - MPI functions
2 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
3 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
4 *
5 * This file is part of GnuPG.
6 *
7 * GnuPG is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * GnuPG is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
20 *
21 * Note: This code is heavily based on the GNU MP Library.
22 * Actually it's the same code with only minor changes in the
23 * way the data is stored; this is to support the abstraction
24 * of an optional secure memory allocation which may be used
25 * to avoid revealing of sensitive data due to paging etc.
26 * The GNU MP Library itself is published under the LGPL;
27 * however I decided to publish this code under the plain GPL.
28 */
29
30#include <linux/string.h>
31#include "mpi-internal.h"
32#include "longlong.h"
33
34int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor)
35{
36 int rc = -ENOMEM;
37 int divisor_sign = divisor->sign;
38 MPI temp_divisor = NULL;
39
40 /* We need the original value of the divisor after the remainder has been
41 * preliminary calculated. We have to copy it to temporary space if it's
42 * the same variable as REM. */
43 if (rem == divisor) {
44 if (mpi_copy(&temp_divisor, divisor) < 0)
45 goto nomem;
46 divisor = temp_divisor;
47 }
48
49 if (mpi_tdiv_qr(NULL, rem, dividend, divisor) < 0)
50 goto nomem;
51 if (((divisor_sign ? 1 : 0) ^ (dividend->sign ? 1 : 0)) && rem->nlimbs)
52 if (mpi_add(rem, rem, divisor) < 0)
53 goto nomem;
54
55 rc = 0;
56
57nomem:
58 if (temp_divisor)
59 mpi_free(temp_divisor);
60 return rc;
61}
62
63/****************
64 * Division rounding the quotient towards -infinity.
65 * The remainder gets the same sign as the denominator.
66 * rem is optional
67 */
68
69ulong mpi_fdiv_r_ui(MPI rem, MPI dividend, ulong divisor)
70{
71 mpi_limb_t rlimb;
72
73 rlimb = mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor);
74 if (rlimb && dividend->sign)
75 rlimb = divisor - rlimb;
76
77 if (rem) {
78 rem->d[0] = rlimb;
79 rem->nlimbs = rlimb ? 1 : 0;
80 }
81 return rlimb;
82}
83
84int mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor)
85{
86 MPI tmp = mpi_alloc(mpi_get_nlimbs(quot));
87 if (!tmp)
88 return -ENOMEM;
89 mpi_fdiv_qr(quot, tmp, dividend, divisor);
90 mpi_free(tmp);
91 return 0;
92}
93
94int mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor)
95{
96 int divisor_sign = divisor->sign;
97 MPI temp_divisor = NULL;
98
99 if (quot == divisor || rem == divisor) {
100 if (mpi_copy(&temp_divisor, divisor) < 0)
101 return -ENOMEM;
102 divisor = temp_divisor;
103 }
104
105 if (mpi_tdiv_qr(quot, rem, dividend, divisor) < 0)
106 goto nomem;
107
108 if ((divisor_sign ^ dividend->sign) && rem->nlimbs) {
109 if (mpi_sub_ui(quot, quot, 1) < 0)
110 goto nomem;
111 if (mpi_add(rem, rem, divisor) < 0)
112 goto nomem;
113 }
114
115 if (temp_divisor)
116 mpi_free(temp_divisor);
117
118 return 0;
119
120nomem:
121 mpi_free(temp_divisor);
122 return -ENOMEM;
123}
124
125/* If den == quot, den needs temporary storage.
126 * If den == rem, den needs temporary storage.
127 * If num == quot, num needs temporary storage.
128 * If den has temporary storage, it can be normalized while being copied,
129 * i.e no extra storage should be allocated.
130 */
131
132int mpi_tdiv_r(MPI rem, MPI num, MPI den)
133{
134 return mpi_tdiv_qr(NULL, rem, num, den);
135}
136
137int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den)
138{
139 int rc = -ENOMEM;
140 mpi_ptr_t np, dp;
141 mpi_ptr_t qp, rp;
142 mpi_size_t nsize = num->nlimbs;
143 mpi_size_t dsize = den->nlimbs;
144 mpi_size_t qsize, rsize;
145 mpi_size_t sign_remainder = num->sign;
146 mpi_size_t sign_quotient = num->sign ^ den->sign;
147 unsigned normalization_steps;
148 mpi_limb_t q_limb;
149 mpi_ptr_t marker[5];
150 int markidx = 0;
151
152 if (!dsize)
153 return -EINVAL;
154
155 memset(marker, 0, sizeof(marker));
156
157 /* Ensure space is enough for quotient and remainder.
158 * We need space for an extra limb in the remainder, because it's
159 * up-shifted (normalized) below. */
160 rsize = nsize + 1;
161 if (mpi_resize(rem, rsize) < 0)
162 goto nomem;
163
164 qsize = rsize - dsize; /* qsize cannot be bigger than this. */
165 if (qsize <= 0) {
166 if (num != rem) {
167 rem->nlimbs = num->nlimbs;
168 rem->sign = num->sign;
169 MPN_COPY(rem->d, num->d, nsize);
170 }
171 if (quot) {
172 /* This needs to follow the assignment to rem, in case the
173 * numerator and quotient are the same. */
174 quot->nlimbs = 0;
175 quot->sign = 0;
176 }
177 return 0;
178 }
179
180 if (quot)
181 if (mpi_resize(quot, qsize) < 0)
182 goto nomem;
183
184 /* Read pointers here, when reallocation is finished. */
185 np = num->d;
186 dp = den->d;
187 rp = rem->d;
188
189 /* Optimize division by a single-limb divisor. */
190 if (dsize == 1) {
191 mpi_limb_t rlimb;
192 if (quot) {
193 qp = quot->d;
194 rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]);
195 qsize -= qp[qsize - 1] == 0;
196 quot->nlimbs = qsize;
197 quot->sign = sign_quotient;
198 } else
199 rlimb = mpihelp_mod_1(np, nsize, dp[0]);
200 rp[0] = rlimb;
201 rsize = rlimb != 0 ? 1 : 0;
202 rem->nlimbs = rsize;
203 rem->sign = sign_remainder;
204 return 0;
205 }
206
207 if (quot) {
208 qp = quot->d;
209 /* Make sure QP and NP point to different objects. Otherwise the
210 * numerator would be gradually overwritten by the quotient limbs. */
211 if (qp == np) { /* Copy NP object to temporary space. */
212 np = marker[markidx++] = mpi_alloc_limb_space(nsize);
213 if (!np)
214 goto nomem;
215 MPN_COPY(np, qp, nsize);
216 }
217 } else /* Put quotient at top of remainder. */
218 qp = rp + dsize;
219
220 count_leading_zeros(normalization_steps, dp[dsize - 1]);
221
222 /* Normalize the denominator, i.e. make its most significant bit set by
223 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the
224 * numerator the same number of steps (to keep the quotient the same!).
225 */
226 if (normalization_steps) {
227 mpi_ptr_t tp;
228 mpi_limb_t nlimb;
229
230 /* Shift up the denominator setting the most significant bit of
231 * the most significant word. Use temporary storage not to clobber
232 * the original contents of the denominator. */
233 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
234 if (!tp)
235 goto nomem;
236 mpihelp_lshift(tp, dp, dsize, normalization_steps);
237 dp = tp;
238
239 /* Shift up the numerator, possibly introducing a new most
240 * significant word. Move the shifted numerator in the remainder
241 * meanwhile. */
242 nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps);
243 if (nlimb) {
244 rp[nsize] = nlimb;
245 rsize = nsize + 1;
246 } else
247 rsize = nsize;
248 } else {
249 /* The denominator is already normalized, as required. Copy it to
250 * temporary space if it overlaps with the quotient or remainder. */
251 if (dp == rp || (quot && (dp == qp))) {
252 mpi_ptr_t tp;
253
254 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
255 if (!tp)
256 goto nomem;
257 MPN_COPY(tp, dp, dsize);
258 dp = tp;
259 }
260
261 /* Move the numerator to the remainder. */
262 if (rp != np)
263 MPN_COPY(rp, np, nsize);
264
265 rsize = nsize;
266 }
267
268 q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize);
269
270 if (quot) {
271 qsize = rsize - dsize;
272 if (q_limb) {
273 qp[qsize] = q_limb;
274 qsize += 1;
275 }
276
277 quot->nlimbs = qsize;
278 quot->sign = sign_quotient;
279 }
280
281 rsize = dsize;
282 MPN_NORMALIZE(rp, rsize);
283
284 if (normalization_steps && rsize) {
285 mpihelp_rshift(rp, rp, rsize, normalization_steps);
286 rsize -= rp[rsize - 1] == 0 ? 1 : 0;
287 }
288
289 rem->nlimbs = rsize;
290 rem->sign = sign_remainder;
291
292 rc = 0;
293nomem:
294 while (markidx)
295 mpi_free_limb_space(marker[--markidx]);
296 return rc;
297}
298
299int mpi_tdiv_q_2exp(MPI w, MPI u, unsigned count)
300{
301 mpi_size_t usize, wsize;
302 mpi_size_t limb_cnt;
303
304 usize = u->nlimbs;
305 limb_cnt = count / BITS_PER_MPI_LIMB;
306 wsize = usize - limb_cnt;
307 if (limb_cnt >= usize)
308 w->nlimbs = 0;
309 else {
310 mpi_ptr_t wp;
311 mpi_ptr_t up;
312
313 if (RESIZE_IF_NEEDED(w, wsize) < 0)
314 return -ENOMEM;
315 wp = w->d;
316 up = u->d;
317
318 count %= BITS_PER_MPI_LIMB;
319 if (count) {
320 mpihelp_rshift(wp, up + limb_cnt, wsize, count);
321 wsize -= !wp[wsize - 1];
322 } else {
323 MPN_COPY_INCR(wp, up + limb_cnt, wsize);
324 }
325
326 w->nlimbs = wsize;
327 }
328 return 0;
329}
330
331/****************
332 * Check whether dividend is divisible by divisor
333 * (note: divisor must fit into a limb)
334 */
335int mpi_divisible_ui(MPI dividend, ulong divisor)
336{
337 return !mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor);
338}
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 @@
1/* mpi-gcd.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * GnuPG is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19 */
20
21#include "mpi-internal.h"
22
23/****************
24 * Find the greatest common divisor G of A and B.
25 * Return: true if this 1, false in all other cases
26 */
27int mpi_gcd(MPI g, const MPI xa, const MPI xb)
28{
29 MPI a = NULL, b = NULL;
30
31 if (mpi_copy(&a, xa) < 0)
32 goto nomem;
33
34 if (mpi_copy(&b, xb) < 0)
35 goto nomem;
36
37 /* TAOCP Vol II, 4.5.2, Algorithm A */
38 a->sign = 0;
39 b->sign = 0;
40 while (mpi_cmp_ui(b, 0)) {
41 if (mpi_fdiv_r(g, a, b) < 0) /* g used as temorary variable */
42 goto nomem;
43 if (mpi_set(a, b) < 0)
44 goto nomem;
45 if (mpi_set(b, g) < 0)
46 goto nomem;
47 }
48 if (mpi_set(g, a) < 0)
49 goto nomem;
50
51 mpi_free(a);
52 mpi_free(b);
53 return !mpi_cmp_ui(g, 1);
54
55nomem:
56 mpi_free(a);
57 mpi_free(b);
58 return -ENOMEM;
59}
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 @@
1/* mpi-inline.c
2 * Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * GnuPG is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19 */
20
21/* put the inline functions as real functions into the lib */
22#define G10_MPI_INLINE_DECL
23
24#include "mpi-internal.h"
25
26/* always include the header becuase it is only
27 * included by mpi-internal if __GCC__ is defined but we
28 * need it here in all cases and the above definition of
29 * of the macro allows us to do so
30 */
31#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 @@
1/* mpi-inv.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * GnuPG is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19 */
20
21#include "mpi-internal.h"
22
23/****************
24 * Calculate the multiplicative inverse X of A mod N
25 * That is: Find the solution x for
26 * 1 = (a*x) mod n
27 */
28int mpi_invm(MPI x, const MPI a, const MPI n)
29{
30 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
31 * modified according to Michael Penk's solution for Exercice 35
32 * with further enhancement */
33 MPI u = NULL, v = NULL;
34 MPI u1 = NULL, u2 = NULL, u3 = NULL;
35 MPI v1 = NULL, v2 = NULL, v3 = NULL;
36 MPI t1 = NULL, t2 = NULL, t3 = NULL;
37 unsigned k;
38 int sign;
39 int odd = 0;
40 int rc = -ENOMEM;
41
42 if (mpi_copy(&u, a) < 0)
43 goto cleanup;
44 if (mpi_copy(&v, n) < 0)
45 goto cleanup;
46
47 for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) {
48 if (mpi_rshift(u, u, 1) < 0)
49 goto cleanup;
50 if (mpi_rshift(v, v, 1) < 0)
51 goto cleanup;
52 }
53 odd = mpi_test_bit(v, 0);
54
55 u1 = mpi_alloc_set_ui(1);
56 if (!u1)
57 goto cleanup;
58 if (!odd) {
59 u2 = mpi_alloc_set_ui(0);
60 if (!u2)
61 goto cleanup;
62 }
63 if (mpi_copy(&u3, u) < 0)
64 goto cleanup;
65 if (mpi_copy(&v1, v) < 0)
66 goto cleanup;
67 if (!odd) {
68 v2 = mpi_alloc(mpi_get_nlimbs(u));
69 if (!v2)
70 goto cleanup;
71 if (mpi_sub(v2, u1, u) < 0)
72 goto cleanup; /* U is used as const 1 */
73 }
74 if (mpi_copy(&v3, v) < 0)
75 goto cleanup;
76 if (mpi_test_bit(u, 0)) { /* u is odd */
77 t1 = mpi_alloc_set_ui(0);
78 if (!t1)
79 goto cleanup;
80 if (!odd) {
81 t2 = mpi_alloc_set_ui(1);
82 if (!t2)
83 goto cleanup;
84 t2->sign = 1;
85 }
86 if (mpi_copy(&t3, v) < 0)
87 goto cleanup;
88 t3->sign = !t3->sign;
89 goto Y4;
90 } else {
91 t1 = mpi_alloc_set_ui(1);
92 if (!t1)
93 goto cleanup;
94 if (!odd) {
95 t2 = mpi_alloc_set_ui(0);
96 if (!t2)
97 goto cleanup;
98 }
99 if (mpi_copy(&t3, u) < 0)
100 goto cleanup;
101 }
102 do {
103 do {
104 if (!odd) {
105 if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) { /* one is odd */
106 if (mpi_add(t1, t1, v) < 0)
107 goto cleanup;
108 if (mpi_sub(t2, t2, u) < 0)
109 goto cleanup;
110 }
111 if (mpi_rshift(t1, t1, 1) < 0)
112 goto cleanup;
113 if (mpi_rshift(t2, t2, 1) < 0)
114 goto cleanup;
115 if (mpi_rshift(t3, t3, 1) < 0)
116 goto cleanup;
117 } else {
118 if (mpi_test_bit(t1, 0))
119 if (mpi_add(t1, t1, v) < 0)
120 goto cleanup;
121 if (mpi_rshift(t1, t1, 1) < 0)
122 goto cleanup;
123 if (mpi_rshift(t3, t3, 1) < 0)
124 goto cleanup;
125 }
126Y4:
127 ;
128 } while (!mpi_test_bit(t3, 0)); /* while t3 is even */
129
130 if (!t3->sign) {
131 if (mpi_set(u1, t1) < 0)
132 goto cleanup;
133 if (!odd)
134 if (mpi_set(u2, t2) < 0)
135 goto cleanup;
136 if (mpi_set(u3, t3) < 0)
137 goto cleanup;
138 } else {
139 if (mpi_sub(v1, v, t1) < 0)
140 goto cleanup;
141 sign = u->sign;
142 u->sign = !u->sign;
143 if (!odd)
144 if (mpi_sub(v2, u, t2) < 0)
145 goto cleanup;
146 u->sign = sign;
147 sign = t3->sign;
148 t3->sign = !t3->sign;
149 if (mpi_set(v3, t3) < 0)
150 goto cleanup;
151 t3->sign = sign;
152 }
153 if (mpi_sub(t1, u1, v1) < 0)
154 goto cleanup;
155 if (!odd)
156 if (mpi_sub(t2, u2, v2) < 0)
157 goto cleanup;
158 if (mpi_sub(t3, u3, v3) < 0)
159 goto cleanup;
160 if (t1->sign) {
161 if (mpi_add(t1, t1, v) < 0)
162 goto cleanup;
163 if (!odd)
164 if (mpi_sub(t2, t2, u) < 0)
165 goto cleanup;
166 }
167 } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */
168 /* mpi_lshift( u3, k ); */
169 rc = mpi_set(x, u1);
170
171cleanup:
172 mpi_free(u1);
173 mpi_free(v1);
174 mpi_free(t1);
175 if (!odd) {
176 mpi_free(u2);
177 mpi_free(v2);
178 mpi_free(t2);
179 }
180 mpi_free(u3);
181 mpi_free(v3);
182 mpi_free(t3);
183
184 mpi_free(u);
185 mpi_free(v);
186 return rc;
187}
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 @@
1/* mpi-mpow.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * GnuPG is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19 */
20
21#include "mpi-internal.h"
22#include "longlong.h"
23
24static int build_index(const MPI *exparray, int k, int i, int t)
25{
26 int j, bitno;
27 int index = 0;
28
29 bitno = t - i;
30 for (j = k - 1; j >= 0; j--) {
31 index <<= 1;
32 if (mpi_test_bit(exparray[j], bitno))
33 index |= 1;
34 }
35 return index;
36}
37
38/****************
39 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
40 */
41int mpi_mulpowm(MPI res, MPI *basearray, MPI *exparray, MPI m)
42{
43 int rc = -ENOMEM;
44 int k; /* number of elements */
45 int t; /* bit size of largest exponent */
46 int i, j, idx;
47 MPI *G = NULL; /* table with precomputed values of size 2^k */
48 MPI tmp = NULL;
49
50 for (k = 0; basearray[k]; k++)
51 ;
52 if (!k) {
53 pr_emerg("mpi_mulpowm: assert(k) failed\n");
54 BUG();
55 }
56 for (t = 0, i = 0; (tmp = exparray[i]); i++) {
57 j = mpi_get_nbits(tmp);
58 if (j > t)
59 t = j;
60 }
61 if (i != k) {
62 pr_emerg("mpi_mulpowm: assert(i==k) failed\n");
63 BUG();
64 }
65 if (!t) {
66 pr_emerg("mpi_mulpowm: assert(t) failed\n");
67 BUG();
68 }
69 if (k >= 10) {
70 pr_emerg("mpi_mulpowm: assert(k<10) failed\n");
71 BUG();
72 }
73
74 G = kzalloc((1 << k) * sizeof *G, GFP_KERNEL);
75 if (!G)
76 goto err_out;
77
78 /* and calculate */
79 tmp = mpi_alloc(mpi_get_nlimbs(m) + 1);
80 if (!tmp)
81 goto nomem;
82 if (mpi_set_ui(res, 1) < 0)
83 goto nomem;
84 for (i = 1; i <= t; i++) {
85 if (mpi_mulm(tmp, res, res, m) < 0)
86 goto nomem;
87 idx = build_index(exparray, k, i, t);
88 if (!(idx >= 0 && idx < (1 << k))) {
89 pr_emerg("mpi_mulpowm: assert(idx >= 0 && idx < (1<<k)) failed\n");
90 BUG();
91 }
92 if (!G[idx]) {
93 if (!idx) {
94 G[0] = mpi_alloc_set_ui(1);
95 if (!G[0])
96 goto nomem;
97 } else {
98 for (j = 0; j < k; j++) {
99 if ((idx & (1 << j))) {
100 if (!G[idx]) {
101 if (mpi_copy
102 (&G[idx],
103 basearray[j]) < 0)
104 goto nomem;
105 } else {
106 if (mpi_mulm
107 (G[idx], G[idx],
108 basearray[j],
109 m) < 0)
110 goto nomem;
111 }
112 }
113 }
114 if (!G[idx]) {
115 G[idx] = mpi_alloc(0);
116 if (!G[idx])
117 goto nomem;
118 }
119 }
120 }
121 if (mpi_mulm(res, tmp, G[idx], m) < 0)
122 goto nomem;
123 }
124
125 rc = 0;
126nomem:
127 /* cleanup */
128 mpi_free(tmp);
129 for (i = 0; i < (1 << k); i++)
130 mpi_free(G[i]);
131 kfree(G);
132err_out:
133 return rc;
134}
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 @@
1/* mpi-mul.c - MPI functions
2 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
3 * Copyright (C) 1998, 2001 Free Software Foundation, Inc.
4 *
5 * This file is part of GnuPG.
6 *
7 * GnuPG is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * GnuPG is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
20 *
21 * Note: This code is heavily based on the GNU MP Library.
22 * Actually it's the same code with only minor changes in the
23 * way the data is stored; this is to support the abstraction
24 * of an optional secure memory allocation which may be used
25 * to avoid revealing of sensitive data due to paging etc.
26 * The GNU MP Library itself is published under the LGPL;
27 * however I decided to publish this code under the plain GPL.
28 */
29
30#include "mpi-internal.h"
31
32int mpi_mul_ui(MPI prod, MPI mult, unsigned long small_mult)
33{
34 mpi_size_t size, prod_size;
35 mpi_ptr_t prod_ptr;
36 mpi_limb_t cy;
37 int sign;
38
39 size = mult->nlimbs;
40 sign = mult->sign;
41
42 if (!size || !small_mult) {
43 prod->nlimbs = 0;
44 prod->sign = 0;
45 return 0;
46 }
47
48 prod_size = size + 1;
49 if (prod->alloced < prod_size)
50 if (mpi_resize(prod, prod_size) < 0)
51 return -ENOMEM;
52 prod_ptr = prod->d;
53
54 cy = mpihelp_mul_1(prod_ptr, mult->d, size, (mpi_limb_t) small_mult);
55 if (cy)
56 prod_ptr[size++] = cy;
57 prod->nlimbs = size;
58 prod->sign = sign;
59 return 0;
60}
61
62int mpi_mul_2exp(MPI w, MPI u, unsigned long cnt)
63{
64 mpi_size_t usize, wsize, limb_cnt;
65 mpi_ptr_t wp;
66 mpi_limb_t wlimb;
67 int usign, wsign;
68
69 usize = u->nlimbs;
70 usign = u->sign;
71
72 if (!usize) {
73 w->nlimbs = 0;
74 w->sign = 0;
75 return 0;
76 }
77
78 limb_cnt = cnt / BITS_PER_MPI_LIMB;
79 wsize = usize + limb_cnt + 1;
80 if (w->alloced < wsize)
81 if (mpi_resize(w, wsize) < 0)
82 return -ENOMEM;
83 wp = w->d;
84 wsize = usize + limb_cnt;
85 wsign = usign;
86
87 cnt %= BITS_PER_MPI_LIMB;
88 if (cnt) {
89 wlimb = mpihelp_lshift(wp + limb_cnt, u->d, usize, cnt);
90 if (wlimb) {
91 wp[wsize] = wlimb;
92 wsize++;
93 }
94 } else {
95 MPN_COPY_DECR(wp + limb_cnt, u->d, usize);
96 }
97
98 /* Zero all whole limbs at low end. Do it here and not before calling
99 * mpn_lshift, not to lose for U == W. */
100 MPN_ZERO(wp, limb_cnt);
101
102 w->nlimbs = wsize;
103 w->sign = wsign;
104 return 0;
105}
106
107int mpi_mul(MPI w, MPI u, MPI v)
108{
109 int rc = -ENOMEM;
110 mpi_size_t usize, vsize, wsize;
111 mpi_ptr_t up, vp, wp;
112 mpi_limb_t cy;
113 int usign, vsign, sign_product;
114 int assign_wp = 0;
115 mpi_ptr_t tmp_limb = NULL;
116
117 if (u->nlimbs < v->nlimbs) { /* Swap U and V. */
118 usize = v->nlimbs;
119 usign = v->sign;
120 up = v->d;
121 vsize = u->nlimbs;
122 vsign = u->sign;
123 vp = u->d;
124 } else {
125 usize = u->nlimbs;
126 usign = u->sign;
127 up = u->d;
128 vsize = v->nlimbs;
129 vsign = v->sign;
130 vp = v->d;
131 }
132 sign_product = usign ^ vsign;
133 wp = w->d;
134
135 /* Ensure W has space enough to store the result. */
136 wsize = usize + vsize;
137 if (w->alloced < (size_t) wsize) {
138 if (wp == up || wp == vp) {
139 wp = mpi_alloc_limb_space(wsize);
140 if (!wp)
141 goto nomem;
142 assign_wp = 1;
143 } else {
144 if (mpi_resize(w, wsize) < 0)
145 goto nomem;
146 wp = w->d;
147 }
148 } else { /* Make U and V not overlap with W. */
149 if (wp == up) {
150 /* W and U are identical. Allocate temporary space for U. */
151 up = tmp_limb = mpi_alloc_limb_space(usize);
152 if (!up)
153 goto nomem;
154 /* Is V identical too? Keep it identical with U. */
155 if (wp == vp)
156 vp = up;
157 /* Copy to the temporary space. */
158 MPN_COPY(up, wp, usize);
159 } else if (wp == vp) {
160 /* W and V are identical. Allocate temporary space for V. */
161 vp = tmp_limb = mpi_alloc_limb_space(vsize);
162 if (!vp)
163 goto nomem;
164 /* Copy to the temporary space. */
165 MPN_COPY(vp, wp, vsize);
166 }
167 }
168
169 if (!vsize)
170 wsize = 0;
171 else {
172 if (mpihelp_mul(wp, up, usize, vp, vsize, &cy) < 0)
173 goto nomem;
174 wsize -= cy ? 0 : 1;
175 }
176
177 if (assign_wp)
178 mpi_assign_limb_space(w, wp, wsize);
179
180 w->nlimbs = wsize;
181 w->sign = sign_product;
182 rc = 0;
183nomem:
184 if (tmp_limb)
185 mpi_free_limb_space(tmp_limb);
186 return rc;
187}
188
189int mpi_mulm(MPI w, MPI u, MPI v, MPI m)
190{
191 if (mpi_mul(w, u, v) < 0)
192 return -ENOMEM;
193 return mpi_fdiv_r(w, w, m);
194}
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 @@
1/* mpi-scan.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * GnuPG is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19 */
20
21#include "mpi-internal.h"
22#include "longlong.h"
23
24/****************
25 * Scan through an mpi and return byte for byte. a -1 is returned to indicate
26 * the end of the mpi. Scanning is done from the lsb to the msb, returned
27 * values are in the range of 0 .. 255.
28 *
29 * FIXME: This code is VERY ugly!
30 */
31int mpi_getbyte(const MPI a, unsigned idx)
32{
33 int i, j;
34 unsigned n;
35 mpi_ptr_t ap;
36 mpi_limb_t limb;
37
38 ap = a->d;
39 for (n = 0, i = 0; i < a->nlimbs; i++) {
40 limb = ap[i];
41 for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++)
42 if (n == idx)
43 return (limb >> j * 8) & 0xff;
44 }
45 return -1;
46}
47
48/****************
49 * Put a value at position IDX into A. idx counts from lsb to msb
50 */
51void mpi_putbyte(MPI a, unsigned idx, int xc)
52{
53 int i, j;
54 unsigned n;
55 mpi_ptr_t ap;
56 mpi_limb_t limb, c;
57
58 c = xc & 0xff;
59 ap = a->d;
60 for (n = 0, i = 0; i < a->alloced; i++) {
61 limb = ap[i];
62 for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++)
63 if (n == idx) {
64#if BYTES_PER_MPI_LIMB == 4
65 if (j == 0)
66 limb = (limb & 0xffffff00) | c;
67 else if (j == 1)
68 limb = (limb & 0xffff00ff) | (c << 8);
69 else if (j == 2)
70 limb = (limb & 0xff00ffff) | (c << 16);
71 else
72 limb = (limb & 0x00ffffff) | (c << 24);
73#elif BYTES_PER_MPI_LIMB == 8
74 if (j == 0)
75 limb = (limb & 0xffffffffffffff00) | c;
76 else if (j == 1)
77 limb =
78 (limb & 0xffffffffffff00ff) | (c <<
79 8);
80 else if (j == 2)
81 limb =
82 (limb & 0xffffffffff00ffff) | (c <<
83 16);
84 else if (j == 3)
85 limb =
86 (limb & 0xffffffff00ffffff) | (c <<
87 24);
88 else if (j == 4)
89 limb =
90 (limb & 0xffffff00ffffffff) | (c <<
91 32);
92 else if (j == 5)
93 limb =
94 (limb & 0xffff00ffffffffff) | (c <<
95 40);
96 else if (j == 6)
97 limb =
98 (limb & 0xff00ffffffffffff) | (c <<
99 48);
100 else
101 limb =
102 (limb & 0x00ffffffffffffff) | (c <<
103 56);
104#else
105#error please enhance this function, its ugly - i know.
106#endif
107 if (a->nlimbs <= i)
108 a->nlimbs = i + 1;
109 ap[i] = limb;
110 return;
111 }
112 }
113 log_bug("index out of range\n");
114}
115
116/****************
117 * Count the number of zerobits at the low end of A
118 */
119unsigned mpi_trailing_zeros(const MPI a)
120{
121 unsigned n, count = 0;
122
123 for (n = 0; n < a->nlimbs; n++) {
124 if (a->d[n]) {
125 unsigned nn;
126 mpi_limb_t alimb = a->d[n];
127
128 count_trailing_zeros(nn, alimb);
129 count += nn;
130 break;
131 }
132 count += BITS_PER_MPI_LIMB;
133 }
134 return count;
135
136}
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:
74EXPORT_SYMBOL_GPL(mpi_read_from_buffer); 74EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
75 75
76/**************** 76/****************
77 * Make an mpi from a character string.
78 */
79int mpi_fromstr(MPI val, const char *str)
80{
81 int hexmode = 0, sign = 0, prepend_zero = 0, i, j, c, c1, c2;
82 unsigned nbits, nbytes, nlimbs;
83 mpi_limb_t a;
84
85 if (*str == '-') {
86 sign = 1;
87 str++;
88 }
89 if (*str == '0' && str[1] == 'x')
90 hexmode = 1;
91 else
92 return -EINVAL; /* other bases are not yet supported */
93 str += 2;
94
95 nbits = strlen(str) * 4;
96 if (nbits % 8)
97 prepend_zero = 1;
98 nbytes = (nbits + 7) / 8;
99 nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
100 if (val->alloced < nlimbs)
101 if (!mpi_resize(val, nlimbs))
102 return -ENOMEM;
103 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
104 i %= BYTES_PER_MPI_LIMB;
105 j = val->nlimbs = nlimbs;
106 val->sign = sign;
107 for (; j > 0; j--) {
108 a = 0;
109 for (; i < BYTES_PER_MPI_LIMB; i++) {
110 if (prepend_zero) {
111 c1 = '0';
112 prepend_zero = 0;
113 } else
114 c1 = *str++;
115 assert(c1);
116 c2 = *str++;
117 assert(c2);
118 if (c1 >= '0' && c1 <= '9')
119 c = c1 - '0';
120 else if (c1 >= 'a' && c1 <= 'f')
121 c = c1 - 'a' + 10;
122 else if (c1 >= 'A' && c1 <= 'F')
123 c = c1 - 'A' + 10;
124 else {
125 mpi_clear(val);
126 return 1;
127 }
128 c <<= 4;
129 if (c2 >= '0' && c2 <= '9')
130 c |= c2 - '0';
131 else if (c2 >= 'a' && c2 <= 'f')
132 c |= c2 - 'a' + 10;
133 else if (c2 >= 'A' && c2 <= 'F')
134 c |= c2 - 'A' + 10;
135 else {
136 mpi_clear(val);
137 return 1;
138 }
139 a <<= 8;
140 a |= c;
141 }
142 i = 0;
143
144 val->d[j - 1] = a;
145 }
146
147 return 0;
148}
149EXPORT_SYMBOL_GPL(mpi_fromstr);
150
151/****************
152 * Return an allocated buffer with the MPI (msb first). 77 * Return an allocated buffer with the MPI (msb first).
153 * NBYTES receives the length of this buffer. Caller must free the 78 * NBYTES receives the length of this buffer. Caller must free the
154 * return string (This function does return a 0 byte buffer with NBYTES 79 * 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 @@
37#define UDIV_TIME UMUL_TIME 37#define UDIV_TIME UMUL_TIME
38#endif 38#endif
39 39
40/* FIXME: We should be using invert_limb (or invert_normalized_limb)
41 * here (not udiv_qrnnd).
42 */
43
44mpi_limb_t
45mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
46 mpi_limb_t divisor_limb)
47{
48 mpi_size_t i;
49 mpi_limb_t n1, n0, r;
50 int dummy;
51
52 /* Botch: Should this be handled at all? Rely on callers? */
53 if (!dividend_size)
54 return 0;
55
56 /* If multiplication is much faster than division, and the
57 * dividend is large, pre-invert the divisor, and use
58 * only multiplications in the inner loop.
59 *
60 * This test should be read:
61 * Does it ever help to use udiv_qrnnd_preinv?
62 * && Does what we save compensate for the inversion overhead?
63 */
64 if (UDIV_TIME > (2 * UMUL_TIME + 6)
65 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
66 int normalization_steps;
67
68 count_leading_zeros(normalization_steps, divisor_limb);
69 if (normalization_steps) {
70 mpi_limb_t divisor_limb_inverted;
71
72 divisor_limb <<= normalization_steps;
73
74 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
75 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
76 * most significant bit (with weight 2**N) implicit.
77 *
78 * Special case for DIVISOR_LIMB == 100...000.
79 */
80 if (!(divisor_limb << 1))
81 divisor_limb_inverted = ~(mpi_limb_t) 0;
82 else
83 udiv_qrnnd(divisor_limb_inverted, dummy,
84 -divisor_limb, 0, divisor_limb);
85
86 n1 = dividend_ptr[dividend_size - 1];
87 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
88
89 /* Possible optimization:
90 * if (r == 0
91 * && divisor_limb > ((n1 << normalization_steps)
92 * | (dividend_ptr[dividend_size - 2] >> ...)))
93 * ...one division less...
94 */
95 for (i = dividend_size - 2; i >= 0; i--) {
96 n0 = dividend_ptr[i];
97 UDIV_QRNND_PREINV(dummy, r, r,
98 ((n1 << normalization_steps)
99 | (n0 >>
100 (BITS_PER_MPI_LIMB -
101 normalization_steps))),
102 divisor_limb,
103 divisor_limb_inverted);
104 n1 = n0;
105 }
106 UDIV_QRNND_PREINV(dummy, r, r,
107 n1 << normalization_steps,
108 divisor_limb, divisor_limb_inverted);
109 return r >> normalization_steps;
110 } else {
111 mpi_limb_t divisor_limb_inverted;
112
113 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
114 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
115 * most significant bit (with weight 2**N) implicit.
116 *
117 * Special case for DIVISOR_LIMB == 100...000.
118 */
119 if (!(divisor_limb << 1))
120 divisor_limb_inverted = ~(mpi_limb_t) 0;
121 else
122 udiv_qrnnd(divisor_limb_inverted, dummy,
123 -divisor_limb, 0, divisor_limb);
124
125 i = dividend_size - 1;
126 r = dividend_ptr[i];
127
128 if (r >= divisor_limb)
129 r = 0;
130 else
131 i--;
132
133 for (; i >= 0; i--) {
134 n0 = dividend_ptr[i];
135 UDIV_QRNND_PREINV(dummy, r, r,
136 n0, divisor_limb,
137 divisor_limb_inverted);
138 }
139 return r;
140 }
141 } else {
142 if (UDIV_NEEDS_NORMALIZATION) {
143 int normalization_steps;
144
145 count_leading_zeros(normalization_steps, divisor_limb);
146 if (normalization_steps) {
147 divisor_limb <<= normalization_steps;
148
149 n1 = dividend_ptr[dividend_size - 1];
150 r = n1 >> (BITS_PER_MPI_LIMB -
151 normalization_steps);
152
153 /* Possible optimization:
154 * if (r == 0
155 * && divisor_limb > ((n1 << normalization_steps)
156 * | (dividend_ptr[dividend_size - 2] >> ...)))
157 * ...one division less...
158 */
159 for (i = dividend_size - 2; i >= 0; i--) {
160 n0 = dividend_ptr[i];
161 udiv_qrnnd(dummy, r, r,
162 ((n1 << normalization_steps)
163 | (n0 >>
164 (BITS_PER_MPI_LIMB -
165 normalization_steps))),
166 divisor_limb);
167 n1 = n0;
168 }
169 udiv_qrnnd(dummy, r, r,
170 n1 << normalization_steps,
171 divisor_limb);
172 return r >> normalization_steps;
173 }
174 }
175 /* No normalization needed, either because udiv_qrnnd doesn't require
176 * it, or because DIVISOR_LIMB is already normalized. */
177 i = dividend_size - 1;
178 r = dividend_ptr[i];
179
180 if (r >= divisor_limb)
181 r = 0;
182 else
183 i--;
184
185 for (; i >= 0; i--) {
186 n0 = dividend_ptr[i];
187 udiv_qrnnd(dummy, r, r, n0, divisor_limb);
188 }
189 return r;
190 }
191}
192
193/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write 40/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
194 * the NSIZE-DSIZE least significant quotient limbs at QP 41 * the NSIZE-DSIZE least significant quotient limbs at QP
195 * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is 42 * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is
@@ -387,159 +234,3 @@ q_test:
387 234
388 return most_significant_q_limb; 235 return most_significant_q_limb;
389} 236}
390
391/****************
392 * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
393 * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
394 * Return the single-limb remainder.
395 * There are no constraints on the value of the divisor.
396 *
397 * QUOT_PTR and DIVIDEND_PTR might point to the same limb.
398 */
399
400mpi_limb_t
401mpihelp_divmod_1(mpi_ptr_t quot_ptr,
402 mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
403 mpi_limb_t divisor_limb)
404{
405 mpi_size_t i;
406 mpi_limb_t n1, n0, r;
407 int dummy;
408
409 if (!dividend_size)
410 return 0;
411
412 /* If multiplication is much faster than division, and the
413 * dividend is large, pre-invert the divisor, and use
414 * only multiplications in the inner loop.
415 *
416 * This test should be read:
417 * Does it ever help to use udiv_qrnnd_preinv?
418 * && Does what we save compensate for the inversion overhead?
419 */
420 if (UDIV_TIME > (2 * UMUL_TIME + 6)
421 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
422 int normalization_steps;
423
424 count_leading_zeros(normalization_steps, divisor_limb);
425 if (normalization_steps) {
426 mpi_limb_t divisor_limb_inverted;
427
428 divisor_limb <<= normalization_steps;
429
430 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
431 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
432 * most significant bit (with weight 2**N) implicit.
433 */
434 /* Special case for DIVISOR_LIMB == 100...000. */
435 if (!(divisor_limb << 1))
436 divisor_limb_inverted = ~(mpi_limb_t) 0;
437 else
438 udiv_qrnnd(divisor_limb_inverted, dummy,
439 -divisor_limb, 0, divisor_limb);
440
441 n1 = dividend_ptr[dividend_size - 1];
442 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
443
444 /* Possible optimization:
445 * if (r == 0
446 * && divisor_limb > ((n1 << normalization_steps)
447 * | (dividend_ptr[dividend_size - 2] >> ...)))
448 * ...one division less...
449 */
450 for (i = dividend_size - 2; i >= 0; i--) {
451 n0 = dividend_ptr[i];
452 UDIV_QRNND_PREINV(quot_ptr[i + 1], r, r,
453 ((n1 << normalization_steps)
454 | (n0 >>
455 (BITS_PER_MPI_LIMB -
456 normalization_steps))),
457 divisor_limb,
458 divisor_limb_inverted);
459 n1 = n0;
460 }
461 UDIV_QRNND_PREINV(quot_ptr[0], r, r,
462 n1 << normalization_steps,
463 divisor_limb, divisor_limb_inverted);
464 return r >> normalization_steps;
465 } else {
466 mpi_limb_t divisor_limb_inverted;
467
468 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
469 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
470 * most significant bit (with weight 2**N) implicit.
471 */
472 /* Special case for DIVISOR_LIMB == 100...000. */
473 if (!(divisor_limb << 1))
474 divisor_limb_inverted = ~(mpi_limb_t) 0;
475 else
476 udiv_qrnnd(divisor_limb_inverted, dummy,
477 -divisor_limb, 0, divisor_limb);
478
479 i = dividend_size - 1;
480 r = dividend_ptr[i];
481
482 if (r >= divisor_limb)
483 r = 0;
484 else
485 quot_ptr[i--] = 0;
486
487 for (; i >= 0; i--) {
488 n0 = dividend_ptr[i];
489 UDIV_QRNND_PREINV(quot_ptr[i], r, r,
490 n0, divisor_limb,
491 divisor_limb_inverted);
492 }
493 return r;
494 }
495 } else {
496 if (UDIV_NEEDS_NORMALIZATION) {
497 int normalization_steps;
498
499 count_leading_zeros(normalization_steps, divisor_limb);
500 if (normalization_steps) {
501 divisor_limb <<= normalization_steps;
502
503 n1 = dividend_ptr[dividend_size - 1];
504 r = n1 >> (BITS_PER_MPI_LIMB -
505 normalization_steps);
506
507 /* Possible optimization:
508 * if (r == 0
509 * && divisor_limb > ((n1 << normalization_steps)
510 * | (dividend_ptr[dividend_size - 2] >> ...)))
511 * ...one division less...
512 */
513 for (i = dividend_size - 2; i >= 0; i--) {
514 n0 = dividend_ptr[i];
515 udiv_qrnnd(quot_ptr[i + 1], r, r,
516 ((n1 << normalization_steps)
517 | (n0 >>
518 (BITS_PER_MPI_LIMB -
519 normalization_steps))),
520 divisor_limb);
521 n1 = n0;
522 }
523 udiv_qrnnd(quot_ptr[0], r, r,
524 n1 << normalization_steps,
525 divisor_limb);
526 return r >> normalization_steps;
527 }
528 }
529 /* No normalization needed, either because udiv_qrnnd doesn't require
530 * it, or because DIVISOR_LIMB is already normalized. */
531 i = dividend_size - 1;
532 r = dividend_ptr[i];
533
534 if (r >= divisor_limb)
535 r = 0;
536 else
537 quot_ptr[i--] = 0;
538
539 for (; i >= 0; i--) {
540 n0 = dividend_ptr[i];
541 udiv_qrnnd(quot_ptr[i], r, r, n0, divisor_limb);
542 }
543 return r;
544 }
545}
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)
330 } 330 }
331} 331}
332 332
333/* This should be made into an inline function in gmp.h. */
334int mpihelp_mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
335{
336 if (up == vp) {
337 if (size < KARATSUBA_THRESHOLD)
338 mpih_sqr_n_basecase(prodp, up, size);
339 else {
340 mpi_ptr_t tspace;
341 tspace = mpi_alloc_limb_space(2 * size);
342 if (!tspace)
343 return -ENOMEM;
344 mpih_sqr_n(prodp, up, size, tspace);
345 mpi_free_limb_space(tspace);
346 }
347 } else {
348 if (size < KARATSUBA_THRESHOLD)
349 mul_n_basecase(prodp, up, vp, size);
350 else {
351 mpi_ptr_t tspace;
352 tspace = mpi_alloc_limb_space(2 * size);
353 if (!tspace)
354 return -ENOMEM;
355 mul_n(prodp, up, vp, size, tspace);
356 mpi_free_limb_space(tspace);
357 }
358 }
359
360 return 0;
361}
362
363int 333int
364mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, 334mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
365 mpi_ptr_t up, mpi_size_t usize, 335 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)
106 return 0; 106 return 0;
107} 107}
108 108
109void mpi_clear(MPI a)
110{
111 a->nlimbs = 0;
112 a->nbits = 0;
113 a->flags = 0;
114}
115
116void mpi_free(MPI a) 109void mpi_free(MPI a)
117{ 110{
118 if (!a) 111 if (!a)
@@ -128,84 +121,3 @@ void mpi_free(MPI a)
128 kfree(a); 121 kfree(a);
129} 122}
130EXPORT_SYMBOL_GPL(mpi_free); 123EXPORT_SYMBOL_GPL(mpi_free);
131
132/****************
133 * Note: This copy function should not interpret the MPI
134 * but copy it transparently.
135 */
136int mpi_copy(MPI *copied, const MPI a)
137{
138 size_t i;
139 MPI b;
140
141 *copied = NULL;
142
143 if (a) {
144 b = mpi_alloc(a->nlimbs);
145 if (!b)
146 return -ENOMEM;
147
148 b->nlimbs = a->nlimbs;
149 b->sign = a->sign;
150 b->flags = a->flags;
151 b->nbits = a->nbits;
152
153 for (i = 0; i < b->nlimbs; i++)
154 b->d[i] = a->d[i];
155
156 *copied = b;
157 }
158
159 return 0;
160}
161
162int mpi_set(MPI w, const MPI u)
163{
164 mpi_ptr_t wp, up;
165 mpi_size_t usize = u->nlimbs;
166 int usign = u->sign;
167
168 if (RESIZE_IF_NEEDED(w, (size_t) usize) < 0)
169 return -ENOMEM;
170
171 wp = w->d;
172 up = u->d;
173 MPN_COPY(wp, up, usize);
174 w->nlimbs = usize;
175 w->nbits = u->nbits;
176 w->flags = u->flags;
177 w->sign = usign;
178 return 0;
179}
180
181int mpi_set_ui(MPI w, unsigned long u)
182{
183 if (RESIZE_IF_NEEDED(w, 1) < 0)
184 return -ENOMEM;
185 w->d[0] = u;
186 w->nlimbs = u ? 1 : 0;
187 w->sign = 0;
188 w->nbits = 0;
189 w->flags = 0;
190 return 0;
191}
192
193MPI mpi_alloc_set_ui(unsigned long u)
194{
195 MPI w = mpi_alloc(1);
196 if (!w)
197 return w;
198 w->d[0] = u;
199 w->nlimbs = u ? 1 : 0;
200 w->sign = 0;
201 return w;
202}
203
204void mpi_swap(MPI a, MPI b)
205{
206 struct gcry_mpi tmp;
207
208 tmp = *a;
209 *a = *b;
210 *b = tmp;
211}
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 @@
1#include <linux/module.h>
2
3#include "notifier-error-inject.h"
4
5static int debugfs_errno_set(void *data, u64 val)
6{
7 *(int *)data = clamp_t(int, val, -MAX_ERRNO, 0);
8 return 0;
9}
10
11static int debugfs_errno_get(void *data, u64 *val)
12{
13 *val = *(int *)data;
14 return 0;
15}
16
17DEFINE_SIMPLE_ATTRIBUTE(fops_errno, debugfs_errno_get, debugfs_errno_set,
18 "%lld\n");
19
20static struct dentry *debugfs_create_errno(const char *name, mode_t mode,
21 struct dentry *parent, int *value)
22{
23 return debugfs_create_file(name, mode, parent, value, &fops_errno);
24}
25
26static int notifier_err_inject_callback(struct notifier_block *nb,
27 unsigned long val, void *p)
28{
29 int err = 0;
30 struct notifier_err_inject *err_inject =
31 container_of(nb, struct notifier_err_inject, nb);
32 struct notifier_err_inject_action *action;
33
34 for (action = err_inject->actions; action->name; action++) {
35 if (action->val == val) {
36 err = action->error;
37 break;
38 }
39 }
40 if (err)
41 pr_info("Injecting error (%d) to %s\n", err, action->name);
42
43 return notifier_from_errno(err);
44}
45
46struct dentry *notifier_err_inject_dir;
47EXPORT_SYMBOL_GPL(notifier_err_inject_dir);
48
49struct dentry *notifier_err_inject_init(const char *name, struct dentry *parent,
50 struct notifier_err_inject *err_inject, int priority)
51{
52 struct notifier_err_inject_action *action;
53 mode_t mode = S_IFREG | S_IRUSR | S_IWUSR;
54 struct dentry *dir;
55 struct dentry *actions_dir;
56
57 err_inject->nb.notifier_call = notifier_err_inject_callback;
58 err_inject->nb.priority = priority;
59
60 dir = debugfs_create_dir(name, parent);
61 if (!dir)
62 return ERR_PTR(-ENOMEM);
63
64 actions_dir = debugfs_create_dir("actions", dir);
65 if (!actions_dir)
66 goto fail;
67
68 for (action = err_inject->actions; action->name; action++) {
69 struct dentry *action_dir;
70
71 action_dir = debugfs_create_dir(action->name, actions_dir);
72 if (!action_dir)
73 goto fail;
74
75 /*
76 * Create debugfs r/w file containing action->error. If
77 * notifier call chain is called with action->val, it will
78 * fail with the error code
79 */
80 if (!debugfs_create_errno("error", mode, action_dir,
81 &action->error))
82 goto fail;
83 }
84 return dir;
85fail:
86 debugfs_remove_recursive(dir);
87 return ERR_PTR(-ENOMEM);
88}
89EXPORT_SYMBOL_GPL(notifier_err_inject_init);
90
91static int __init err_inject_init(void)
92{
93 notifier_err_inject_dir =
94 debugfs_create_dir("notifier-error-inject", NULL);
95
96 if (!notifier_err_inject_dir)
97 return -ENOMEM;
98
99 return 0;
100}
101
102static void __exit err_inject_exit(void)
103{
104 debugfs_remove_recursive(notifier_err_inject_dir);
105}
106
107module_init(err_inject_init);
108module_exit(err_inject_exit);
109
110MODULE_DESCRIPTION("Notifier error injection module");
111MODULE_LICENSE("GPL");
112MODULE_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 @@
1#include <linux/atomic.h>
2#include <linux/debugfs.h>
3#include <linux/notifier.h>
4
5struct notifier_err_inject_action {
6 unsigned long val;
7 int error;
8 const char *name;
9};
10
11#define NOTIFIER_ERR_INJECT_ACTION(action) \
12 .name = #action, .val = (action),
13
14struct notifier_err_inject {
15 struct notifier_block nb;
16 struct notifier_err_inject_action actions[];
17 /* The last slot must be terminated with zero sentinel */
18};
19
20extern struct dentry *notifier_err_inject_dir;
21
22extern struct dentry *notifier_err_inject_init(const char *name,
23 struct dentry *parent, struct notifier_err_inject *err_inject,
24 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 @@
1#include <linux/kernel.h>
2#include <linux/module.h>
3
4#include <asm/pSeries_reconfig.h>
5
6#include "notifier-error-inject.h"
7
8static int priority;
9module_param(priority, int, 0);
10MODULE_PARM_DESC(priority, "specify pSeries reconfig notifier priority");
11
12static struct notifier_err_inject reconfig_err_inject = {
13 .actions = {
14 { NOTIFIER_ERR_INJECT_ACTION(PSERIES_RECONFIG_ADD) },
15 { NOTIFIER_ERR_INJECT_ACTION(PSERIES_RECONFIG_REMOVE) },
16 { NOTIFIER_ERR_INJECT_ACTION(PSERIES_DRCONF_MEM_ADD) },
17 { NOTIFIER_ERR_INJECT_ACTION(PSERIES_DRCONF_MEM_REMOVE) },
18 {}
19 }
20};
21
22static struct dentry *dir;
23
24static int err_inject_init(void)
25{
26 int err;
27
28 dir = notifier_err_inject_init("pSeries-reconfig",
29 notifier_err_inject_dir, &reconfig_err_inject, priority);
30 if (IS_ERR(dir))
31 return PTR_ERR(dir);
32
33 err = pSeries_reconfig_notifier_register(&reconfig_err_inject.nb);
34 if (err)
35 debugfs_remove_recursive(dir);
36
37 return err;
38}
39
40static void err_inject_exit(void)
41{
42 pSeries_reconfig_notifier_unregister(&reconfig_err_inject.nb);
43 debugfs_remove_recursive(dir);
44}
45
46module_init(err_inject_init);
47module_exit(err_inject_exit);
48
49MODULE_DESCRIPTION("pSeries reconfig notifier error injection module");
50MODULE_LICENSE("GPL");
51MODULE_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 @@
12 12
13#ifdef CONFIG_HOTPLUG_CPU 13#ifdef CONFIG_HOTPLUG_CPU
14static LIST_HEAD(percpu_counters); 14static LIST_HEAD(percpu_counters);
15static DEFINE_MUTEX(percpu_counters_lock); 15static DEFINE_SPINLOCK(percpu_counters_lock);
16#endif 16#endif
17 17
18#ifdef CONFIG_DEBUG_OBJECTS_PERCPU_COUNTER 18#ifdef CONFIG_DEBUG_OBJECTS_PERCPU_COUNTER
@@ -123,9 +123,9 @@ int __percpu_counter_init(struct percpu_counter *fbc, s64 amount,
123 123
124#ifdef CONFIG_HOTPLUG_CPU 124#ifdef CONFIG_HOTPLUG_CPU
125 INIT_LIST_HEAD(&fbc->list); 125 INIT_LIST_HEAD(&fbc->list);
126 mutex_lock(&percpu_counters_lock); 126 spin_lock(&percpu_counters_lock);
127 list_add(&fbc->list, &percpu_counters); 127 list_add(&fbc->list, &percpu_counters);
128 mutex_unlock(&percpu_counters_lock); 128 spin_unlock(&percpu_counters_lock);
129#endif 129#endif
130 return 0; 130 return 0;
131} 131}
@@ -139,9 +139,9 @@ void percpu_counter_destroy(struct percpu_counter *fbc)
139 debug_percpu_counter_deactivate(fbc); 139 debug_percpu_counter_deactivate(fbc);
140 140
141#ifdef CONFIG_HOTPLUG_CPU 141#ifdef CONFIG_HOTPLUG_CPU
142 mutex_lock(&percpu_counters_lock); 142 spin_lock(&percpu_counters_lock);
143 list_del(&fbc->list); 143 list_del(&fbc->list);
144 mutex_unlock(&percpu_counters_lock); 144 spin_unlock(&percpu_counters_lock);
145#endif 145#endif
146 free_percpu(fbc->counters); 146 free_percpu(fbc->counters);
147 fbc->counters = NULL; 147 fbc->counters = NULL;
@@ -170,7 +170,7 @@ static int __cpuinit percpu_counter_hotcpu_callback(struct notifier_block *nb,
170 return NOTIFY_OK; 170 return NOTIFY_OK;
171 171
172 cpu = (unsigned long)hcpu; 172 cpu = (unsigned long)hcpu;
173 mutex_lock(&percpu_counters_lock); 173 spin_lock(&percpu_counters_lock);
174 list_for_each_entry(fbc, &percpu_counters, list) { 174 list_for_each_entry(fbc, &percpu_counters, list) {
175 s32 *pcount; 175 s32 *pcount;
176 unsigned long flags; 176 unsigned long flags;
@@ -181,7 +181,7 @@ static int __cpuinit percpu_counter_hotcpu_callback(struct notifier_block *nb,
181 *pcount = 0; 181 *pcount = 0;
182 raw_spin_unlock_irqrestore(&fbc->lock, flags); 182 raw_spin_unlock_irqrestore(&fbc->lock, flags);
183 } 183 }
184 mutex_unlock(&percpu_counters_lock); 184 spin_unlock(&percpu_counters_lock);
185#endif 185#endif
186 return NOTIFY_OK; 186 return NOTIFY_OK;
187} 187}
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 @@
1#include <linux/kernel.h>
2#include <linux/module.h>
3#include <linux/suspend.h>
4
5#include "notifier-error-inject.h"
6
7static int priority;
8module_param(priority, int, 0);
9MODULE_PARM_DESC(priority, "specify PM notifier priority");
10
11static struct notifier_err_inject pm_notifier_err_inject = {
12 .actions = {
13 { NOTIFIER_ERR_INJECT_ACTION(PM_HIBERNATION_PREPARE) },
14 { NOTIFIER_ERR_INJECT_ACTION(PM_SUSPEND_PREPARE) },
15 { NOTIFIER_ERR_INJECT_ACTION(PM_RESTORE_PREPARE) },
16 {}
17 }
18};
19
20static struct dentry *dir;
21
22static int err_inject_init(void)
23{
24 int err;
25
26 dir = notifier_err_inject_init("pm", notifier_err_inject_dir,
27 &pm_notifier_err_inject, priority);
28 if (IS_ERR(dir))
29 return PTR_ERR(dir);
30
31 err = register_pm_notifier(&pm_notifier_err_inject.nb);
32 if (err)
33 debugfs_remove_recursive(dir);
34
35 return err;
36}
37
38static void err_inject_exit(void)
39{
40 unregister_pm_notifier(&pm_notifier_err_inject.nb);
41 debugfs_remove_recursive(dir);
42}
43
44module_init(err_inject_init);
45module_exit(err_inject_exit);
46
47MODULE_DESCRIPTION("PM notifier error injection module");
48MODULE_LICENSE("GPL");
49MODULE_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,
279 if (!left) 279 if (!left)
280 sg_mark_end(&sg[sg_size - 1]); 280 sg_mark_end(&sg[sg_size - 1]);
281 281
282 /*
283 * only really needed for mempool backed sg allocations (like
284 * SCSI), a possible improvement here would be to pass the
285 * table pointer into the allocator and let that clear these
286 * flags
287 */
288 gfp_mask &= ~__GFP_WAIT;
289 gfp_mask |= __GFP_HIGH;
290 prv = sg; 282 prv = sg;
291 } while (left); 283 } while (left);
292 284
@@ -319,6 +311,70 @@ int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask)
319EXPORT_SYMBOL(sg_alloc_table); 311EXPORT_SYMBOL(sg_alloc_table);
320 312
321/** 313/**
314 * sg_alloc_table_from_pages - Allocate and initialize an sg table from
315 * an array of pages
316 * @sgt: The sg table header to use
317 * @pages: Pointer to an array of page pointers
318 * @n_pages: Number of pages in the pages array
319 * @offset: Offset from start of the first page to the start of a buffer
320 * @size: Number of valid bytes in the buffer (after offset)
321 * @gfp_mask: GFP allocation mask
322 *
323 * Description:
324 * Allocate and initialize an sg table from a list of pages. Contiguous
325 * ranges of the pages are squashed into a single scatterlist node. A user
326 * may provide an offset at a start and a size of valid data in a buffer
327 * specified by the page array. The returned sg table is released by
328 * sg_free_table.
329 *
330 * Returns:
331 * 0 on success, negative error on failure
332 */
333int sg_alloc_table_from_pages(struct sg_table *sgt,
334 struct page **pages, unsigned int n_pages,
335 unsigned long offset, unsigned long size,
336 gfp_t gfp_mask)
337{
338 unsigned int chunks;
339 unsigned int i;
340 unsigned int cur_page;
341 int ret;
342 struct scatterlist *s;
343
344 /* compute number of contiguous chunks */
345 chunks = 1;
346 for (i = 1; i < n_pages; ++i)
347 if (page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1)
348 ++chunks;
349
350 ret = sg_alloc_table(sgt, chunks, gfp_mask);
351 if (unlikely(ret))
352 return ret;
353
354 /* merging chunks and putting them into the scatterlist */
355 cur_page = 0;
356 for_each_sg(sgt->sgl, s, sgt->orig_nents, i) {
357 unsigned long chunk_size;
358 unsigned int j;
359
360 /* look for the end of the current chunk */
361 for (j = cur_page + 1; j < n_pages; ++j)
362 if (page_to_pfn(pages[j]) !=
363 page_to_pfn(pages[j - 1]) + 1)
364 break;
365
366 chunk_size = ((j - cur_page) << PAGE_SHIFT) - offset;
367 sg_set_page(s, pages[cur_page], min(size, chunk_size), offset);
368 size -= chunk_size;
369 offset = 0;
370 cur_page = j;
371 }
372
373 return 0;
374}
375EXPORT_SYMBOL(sg_alloc_table_from_pages);
376
377/**
322 * sg_miter_start - start mapping iteration over a sg list 378 * sg_miter_start - start mapping iteration over a sg list
323 * @miter: sg mapping iter to be started 379 * @miter: sg mapping iter to be started
324 * @sgl: sg list to iterate over 380 * @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)
58 printk(KERN_EMERG "BUG: spinlock %s on CPU#%d, %s/%d\n", 58 printk(KERN_EMERG "BUG: spinlock %s on CPU#%d, %s/%d\n",
59 msg, raw_smp_processor_id(), 59 msg, raw_smp_processor_id(),
60 current->comm, task_pid_nr(current)); 60 current->comm, task_pid_nr(current));
61 printk(KERN_EMERG " lock: %ps, .magic: %08x, .owner: %s/%d, " 61 printk(KERN_EMERG " lock: %pS, .magic: %08x, .owner: %s/%d, "
62 ".owner_cpu: %d\n", 62 ".owner_cpu: %d\n",
63 lock, lock->magic, 63 lock, lock->magic,
64 owner ? owner->comm : "<none>", 64 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,
655} 655}
656 656
657static noinline_for_stack 657static noinline_for_stack
658char *hex_string(char *buf, char *end, u8 *addr, struct printf_spec spec,
659 const char *fmt)
660{
661 int i, len = 1; /* if we pass '%ph[CDN]', field witdh remains
662 negative value, fallback to the default */
663 char separator;
664
665 if (spec.field_width == 0)
666 /* nothing to print */
667 return buf;
668
669 if (ZERO_OR_NULL_PTR(addr))
670 /* NULL pointer */
671 return string(buf, end, NULL, spec);
672
673 switch (fmt[1]) {
674 case 'C':
675 separator = ':';
676 break;
677 case 'D':
678 separator = '-';
679 break;
680 case 'N':
681 separator = 0;
682 break;
683 default:
684 separator = ' ';
685 break;
686 }
687
688 if (spec.field_width > 0)
689 len = min_t(int, spec.field_width, 64);
690
691 for (i = 0; i < len && buf < end - 1; i++) {
692 buf = hex_byte_pack(buf, addr[i]);
693
694 if (buf < end && separator && i != len - 1)
695 *buf++ = separator;
696 }
697
698 return buf;
699}
700
701static noinline_for_stack
658char *mac_address_string(char *buf, char *end, u8 *addr, 702char *mac_address_string(char *buf, char *end, u8 *addr,
659 struct printf_spec spec, const char *fmt) 703 struct printf_spec spec, const char *fmt)
660{ 704{
@@ -662,15 +706,28 @@ char *mac_address_string(char *buf, char *end, u8 *addr,
662 char *p = mac_addr; 706 char *p = mac_addr;
663 int i; 707 int i;
664 char separator; 708 char separator;
709 bool reversed = false;
665 710
666 if (fmt[1] == 'F') { /* FDDI canonical format */ 711 switch (fmt[1]) {
712 case 'F':
667 separator = '-'; 713 separator = '-';
668 } else { 714 break;
715
716 case 'R':
717 reversed = true;
718 /* fall through */
719
720 default:
669 separator = ':'; 721 separator = ':';
722 break;
670 } 723 }
671 724
672 for (i = 0; i < 6; i++) { 725 for (i = 0; i < 6; i++) {
673 p = hex_byte_pack(p, addr[i]); 726 if (reversed)
727 p = hex_byte_pack(p, addr[5 - i]);
728 else
729 p = hex_byte_pack(p, addr[i]);
730
674 if (fmt[0] == 'M' && i != 5) 731 if (fmt[0] == 'M' && i != 5)
675 *p++ = separator; 732 *p++ = separator;
676 } 733 }
@@ -933,6 +990,7 @@ int kptr_restrict __read_mostly;
933 * - 'm' For a 6-byte MAC address, it prints the hex address without colons 990 * - 'm' For a 6-byte MAC address, it prints the hex address without colons
934 * - 'MF' For a 6-byte MAC FDDI address, it prints the address 991 * - 'MF' For a 6-byte MAC FDDI address, it prints the address
935 * with a dash-separated hex notation 992 * with a dash-separated hex notation
993 * - '[mM]R For a 6-byte MAC address, Reverse order (Bluetooth)
936 * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way 994 * - 'I' [46] for IPv4/IPv6 addresses printed in the usual way
937 * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4) 995 * IPv4 uses dot-separated decimal without leading 0's (1.2.3.4)
938 * IPv6 uses colon separated network-order 16 bit hex with leading 0's 996 * IPv6 uses colon separated network-order 16 bit hex with leading 0's
@@ -960,6 +1018,13 @@ int kptr_restrict __read_mostly;
960 * correctness of the format string and va_list arguments. 1018 * correctness of the format string and va_list arguments.
961 * - 'K' For a kernel pointer that should be hidden from unprivileged users 1019 * - 'K' For a kernel pointer that should be hidden from unprivileged users
962 * - 'NF' For a netdev_features_t 1020 * - 'NF' For a netdev_features_t
1021 * - 'h[CDN]' For a variable-length buffer, it prints it as a hex string with
1022 * a certain separator (' ' by default):
1023 * C colon
1024 * D dash
1025 * N no separator
1026 * The maximum supported length is 64 bytes of the input. Consider
1027 * to use print_hex_dump() for the larger input.
963 * 1028 *
964 * Note: The difference between 'S' and 'F' is that on ia64 and ppc64 1029 * Note: The difference between 'S' and 'F' is that on ia64 and ppc64
965 * function pointers are really function descriptors, which contain a 1030 * function pointers are really function descriptors, which contain a
@@ -993,9 +1058,12 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr,
993 case 'R': 1058 case 'R':
994 case 'r': 1059 case 'r':
995 return resource_string(buf, end, ptr, spec, fmt); 1060 return resource_string(buf, end, ptr, spec, fmt);
1061 case 'h':
1062 return hex_string(buf, end, ptr, spec, fmt);
996 case 'M': /* Colon separated: 00:01:02:03:04:05 */ 1063 case 'M': /* Colon separated: 00:01:02:03:04:05 */
997 case 'm': /* Contiguous: 000102030405 */ 1064 case 'm': /* Contiguous: 000102030405 */
998 /* [mM]F (FDDI, bit reversed) */ 1065 /* [mM]F (FDDI) */
1066 /* [mM]R (Reverse order; Bluetooth) */
999 return mac_address_string(buf, end, ptr, spec, fmt); 1067 return mac_address_string(buf, end, ptr, spec, fmt);
1000 case 'I': /* Formatted IP supported 1068 case 'I': /* Formatted IP supported
1001 * 4: 1.2.3.4 1069 * 4: 1.2.3.4
@@ -1030,7 +1098,8 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr,
1030 * %pK cannot be used in IRQ context because its test 1098 * %pK cannot be used in IRQ context because its test
1031 * for CAP_SYSLOG would be meaningless. 1099 * for CAP_SYSLOG would be meaningless.
1032 */ 1100 */
1033 if (in_irq() || in_serving_softirq() || in_nmi()) { 1101 if (kptr_restrict && (in_irq() || in_serving_softirq() ||
1102 in_nmi())) {
1034 if (spec.field_width == -1) 1103 if (spec.field_width == -1)
1035 spec.field_width = default_width; 1104 spec.field_width = default_width;
1036 return string(buf, end, "pK-error", spec); 1105 return string(buf, end, "pK-error", spec);
@@ -1280,8 +1349,12 @@ qualifier:
1280 * %pI6c print an IPv6 address as specified by RFC 5952 1349 * %pI6c print an IPv6 address as specified by RFC 5952
1281 * %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper 1350 * %pU[bBlL] print a UUID/GUID in big or little endian using lower or upper
1282 * case. 1351 * case.
1352 * %*ph[CDN] a variable-length hex string with a separator (supports up to 64
1353 * bytes of the input)
1283 * %n is ignored 1354 * %n is ignored
1284 * 1355 *
1356 * ** Please update Documentation/printk-formats.txt when making changes **
1357 *
1285 * The return value is the number of characters which would 1358 * The return value is the number of characters which would
1286 * be generated for the given input, excluding the trailing 1359 * be generated for the given input, excluding the trailing
1287 * '\0', as per ISO C99. If you want to have the exact 1360 * '\0', as per ISO C99. If you want to have the exact
generated by cgit v1.2.2 (git 2.25.0) at 2025-02-11 15:49:26 -0500