aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug118
-rw-r--r--lib/Kconfig.kasan32
-rw-r--r--lib/Kconfig.ubsan14
-rw-r--r--lib/Makefile11
-rw-r--r--lib/assoc_array.c9
-rw-r--r--lib/bsearch.c2
-rw-r--r--lib/cpumask.c6
-rw-r--r--lib/crc32.c4
-rw-r--r--lib/devres.c4
-rw-r--r--lib/div64.c4
-rw-r--r--lib/dynamic_debug.c22
-rw-r--r--lib/flex_array.c398
-rw-r--r--lib/generic-radix-tree.c217
-rw-r--r--lib/int_sqrt.c2
-rw-r--r--lib/iomap.c140
-rw-r--r--lib/iov_iter.c17
-rw-r--r--lib/irq_poll.c2
-rw-r--r--lib/kobject.c2
-rw-r--r--lib/kobject_uevent.c9
-rw-r--r--lib/livepatch/Makefile15
-rw-r--r--lib/livepatch/test_klp_atomic_replace.c57
-rw-r--r--lib/livepatch/test_klp_callbacks_busy.c43
-rw-r--r--lib/livepatch/test_klp_callbacks_demo.c121
-rw-r--r--lib/livepatch/test_klp_callbacks_demo2.c93
-rw-r--r--lib/livepatch/test_klp_callbacks_mod.c24
-rw-r--r--lib/livepatch/test_klp_livepatch.c51
-rw-r--r--lib/livepatch/test_klp_shadow_vars.c258
-rw-r--r--lib/locking-selftest.c2
-rw-r--r--lib/lzo/lzo1x_compress.c130
-rw-r--r--lib/lzo/lzo1x_decompress_safe.c75
-rw-r--r--lib/lzo/lzodefs.h21
-rw-r--r--lib/objagg.c583
-rw-r--r--lib/raid6/Makefile2
-rw-r--r--lib/raid6/neon.uc5
-rw-r--r--lib/raid6/recov_neon_inner.c19
-rw-r--r--lib/refcount.c18
-rw-r--r--lib/rhashtable.c2
-rw-r--r--lib/sbitmap.c13
-rw-r--r--lib/scatterlist.c26
-rw-r--r--lib/smp_processor_id.c7
-rw-r--r--lib/test_bpf.c2
-rw-r--r--lib/test_firmware.c9
-rw-r--r--lib/test_kasan.c24
-rw-r--r--lib/test_kmod.c2
-rw-r--r--lib/test_objagg.c199
-rw-r--r--lib/test_rhashtable.c36
-rw-r--r--lib/test_stackinit.c378
-rw-r--r--lib/test_ubsan.c11
-rw-r--r--lib/test_vmalloc.c551
-rw-r--r--lib/test_xarray.c333
-rw-r--r--lib/vsprintf.c6
-rw-r--r--lib/xarray.c205
52 files changed, 3521 insertions, 813 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index d4df5b24d75e..0d9e81779e37 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -17,6 +17,23 @@ config PRINTK_TIME
17 The behavior is also controlled by the kernel command line 17 The behavior is also controlled by the kernel command line
18 parameter printk.time=1. See Documentation/admin-guide/kernel-parameters.rst 18 parameter printk.time=1. See Documentation/admin-guide/kernel-parameters.rst
19 19
20config PRINTK_CALLER
21 bool "Show caller information on printks"
22 depends on PRINTK
23 help
24 Selecting this option causes printk() to add a caller "thread id" (if
25 in task context) or a caller "processor id" (if not in task context)
26 to every message.
27
28 This option is intended for environments where multiple threads
29 concurrently call printk() for many times, for it is difficult to
30 interpret without knowing where these lines (or sometimes individual
31 line which was divided into multiple lines due to race) came from.
32
33 Since toggling after boot makes the code racy, currently there is
34 no option to enable/disable at the kernel command line parameter or
35 sysfs interface.
36
20config CONSOLE_LOGLEVEL_DEFAULT 37config CONSOLE_LOGLEVEL_DEFAULT
21 int "Default console loglevel (1-15)" 38 int "Default console loglevel (1-15)"
22 range 1 15 39 range 1 15
@@ -179,6 +196,7 @@ config DEBUG_INFO_REDUCED
179config DEBUG_INFO_SPLIT 196config DEBUG_INFO_SPLIT
180 bool "Produce split debuginfo in .dwo files" 197 bool "Produce split debuginfo in .dwo files"
181 depends on DEBUG_INFO 198 depends on DEBUG_INFO
199 depends on $(cc-option,-gsplit-dwarf)
182 help 200 help
183 Generate debug info into separate .dwo files. This significantly 201 Generate debug info into separate .dwo files. This significantly
184 reduces the build directory size for builds with DEBUG_INFO, 202 reduces the build directory size for builds with DEBUG_INFO,
@@ -194,6 +212,7 @@ config DEBUG_INFO_SPLIT
194config DEBUG_INFO_DWARF4 212config DEBUG_INFO_DWARF4
195 bool "Generate dwarf4 debuginfo" 213 bool "Generate dwarf4 debuginfo"
196 depends on DEBUG_INFO 214 depends on DEBUG_INFO
215 depends on $(cc-option,-gdwarf-4)
197 help 216 help
198 Generate dwarf4 debug info. This requires recent versions 217 Generate dwarf4 debug info. This requires recent versions
199 of gcc and gdb. It makes the debug information larger. 218 of gcc and gdb. It makes the debug information larger.
@@ -222,7 +241,6 @@ config ENABLE_MUST_CHECK
222config FRAME_WARN 241config FRAME_WARN
223 int "Warn for stack frames larger than (needs gcc 4.4)" 242 int "Warn for stack frames larger than (needs gcc 4.4)"
224 range 0 8192 243 range 0 8192
225 default 3072 if KASAN_EXTRA
226 default 2048 if GCC_PLUGIN_LATENT_ENTROPY 244 default 2048 if GCC_PLUGIN_LATENT_ENTROPY
227 default 1280 if (!64BIT && PARISC) 245 default 1280 if (!64BIT && PARISC)
228 default 1024 if (!64BIT && !PARISC) 246 default 1024 if (!64BIT && !PARISC)
@@ -266,23 +284,6 @@ config UNUSED_SYMBOLS
266 you really need it, and what the merge plan to the mainline kernel for 284 you really need it, and what the merge plan to the mainline kernel for
267 your module is. 285 your module is.
268 286
269config PAGE_OWNER
270 bool "Track page owner"
271 depends on DEBUG_KERNEL && STACKTRACE_SUPPORT
272 select DEBUG_FS
273 select STACKTRACE
274 select STACKDEPOT
275 select PAGE_EXTENSION
276 help
277 This keeps track of what call chain is the owner of a page, may
278 help to find bare alloc_page(s) leaks. Even if you include this
279 feature on your build, it is disabled in default. You should pass
280 "page_owner=on" to boot parameter in order to enable it. Eats
281 a fair amount of memory if enabled. See tools/vm/page_owner_sort.c
282 for user-space helper.
283
284 If unsure, say N.
285
286config DEBUG_FS 287config DEBUG_FS
287 bool "Debug Filesystem" 288 bool "Debug Filesystem"
288 help 289 help
@@ -1655,42 +1656,6 @@ config PROVIDE_OHCI1394_DMA_INIT
1655 1656
1656 See Documentation/debugging-via-ohci1394.txt for more information. 1657 See Documentation/debugging-via-ohci1394.txt for more information.
1657 1658
1658config DMA_API_DEBUG
1659 bool "Enable debugging of DMA-API usage"
1660 select NEED_DMA_MAP_STATE
1661 help
1662 Enable this option to debug the use of the DMA API by device drivers.
1663 With this option you will be able to detect common bugs in device
1664 drivers like double-freeing of DMA mappings or freeing mappings that
1665 were never allocated.
1666
1667 This also attempts to catch cases where a page owned by DMA is
1668 accessed by the cpu in a way that could cause data corruption. For
1669 example, this enables cow_user_page() to check that the source page is
1670 not undergoing DMA.
1671
1672 This option causes a performance degradation. Use only if you want to
1673 debug device drivers and dma interactions.
1674
1675 If unsure, say N.
1676
1677config DMA_API_DEBUG_SG
1678 bool "Debug DMA scatter-gather usage"
1679 default y
1680 depends on DMA_API_DEBUG
1681 help
1682 Perform extra checking that callers of dma_map_sg() have respected the
1683 appropriate segment length/boundary limits for the given device when
1684 preparing DMA scatterlists.
1685
1686 This is particularly likely to have been overlooked in cases where the
1687 dma_map_sg() API is used for general bulk mapping of pages rather than
1688 preparing literal scatter-gather descriptors, where there is a risk of
1689 unexpected behaviour from DMA API implementations if the scatterlist
1690 is technically out-of-spec.
1691
1692 If unsure, say N.
1693
1694menuconfig RUNTIME_TESTING_MENU 1659menuconfig RUNTIME_TESTING_MENU
1695 bool "Runtime Testing" 1660 bool "Runtime Testing"
1696 def_bool y 1661 def_bool y
@@ -1700,7 +1665,6 @@ if RUNTIME_TESTING_MENU
1700config LKDTM 1665config LKDTM
1701 tristate "Linux Kernel Dump Test Tool Module" 1666 tristate "Linux Kernel Dump Test Tool Module"
1702 depends on DEBUG_FS 1667 depends on DEBUG_FS
1703 depends on BLOCK
1704 help 1668 help
1705 This module enables testing of the different dumping mechanisms by 1669 This module enables testing of the different dumping mechanisms by
1706 inducing system failures at predefined crash points. 1670 inducing system failures at predefined crash points.
@@ -1876,6 +1840,19 @@ config TEST_LKM
1876 1840
1877 If unsure, say N. 1841 If unsure, say N.
1878 1842
1843config TEST_VMALLOC
1844 tristate "Test module for stress/performance analysis of vmalloc allocator"
1845 default n
1846 depends on MMU
1847 depends on m
1848 help
1849 This builds the "test_vmalloc" module that should be used for
1850 stress and performance analysis. So, any new change for vmalloc
1851 subsystem can be evaluated from performance and stability point
1852 of view.
1853
1854 If unsure, say N.
1855
1879config TEST_USER_COPY 1856config TEST_USER_COPY
1880 tristate "Test user/kernel boundary protections" 1857 tristate "Test user/kernel boundary protections"
1881 depends on m 1858 depends on m
@@ -1991,6 +1968,28 @@ config TEST_MEMCAT_P
1991 1968
1992 If unsure, say N. 1969 If unsure, say N.
1993 1970
1971config TEST_LIVEPATCH
1972 tristate "Test livepatching"
1973 default n
1974 depends on DYNAMIC_DEBUG
1975 depends on LIVEPATCH
1976 depends on m
1977 help
1978 Test kernel livepatching features for correctness. The tests will
1979 load test modules that will be livepatched in various scenarios.
1980
1981 To run all the livepatching tests:
1982
1983 make -C tools/testing/selftests TARGETS=livepatch run_tests
1984
1985 Alternatively, individual tests may be invoked:
1986
1987 tools/testing/selftests/livepatch/test-callbacks.sh
1988 tools/testing/selftests/livepatch/test-livepatch.sh
1989 tools/testing/selftests/livepatch/test-shadow-vars.sh
1990
1991 If unsure, say N.
1992
1994config TEST_OBJAGG 1993config TEST_OBJAGG
1995 tristate "Perform selftest on object aggreration manager" 1994 tristate "Perform selftest on object aggreration manager"
1996 default n 1995 default n
@@ -1999,6 +1998,15 @@ config TEST_OBJAGG
1999 Enable this option to test object aggregation manager on boot 1998 Enable this option to test object aggregation manager on boot
2000 (or module load). 1999 (or module load).
2001 2000
2001
2002config TEST_STACKINIT
2003 tristate "Test level of stack variable initialization"
2004 help
2005 Test if the kernel is zero-initializing stack variables and
2006 padding. Coverage is controlled by compiler flags,
2007 CONFIG_GCC_PLUGIN_STRUCTLEAK, CONFIG_GCC_PLUGIN_STRUCTLEAK_BYREF,
2008 or CONFIG_GCC_PLUGIN_STRUCTLEAK_BYREF_ALL.
2009
2002 If unsure, say N. 2010 If unsure, say N.
2003 2011
2004endif # RUNTIME_TESTING_MENU 2012endif # RUNTIME_TESTING_MENU
diff --git a/lib/Kconfig.kasan b/lib/Kconfig.kasan
index d8c474b6691e..9950b660e62d 100644
--- a/lib/Kconfig.kasan
+++ b/lib/Kconfig.kasan
@@ -78,16 +78,6 @@ config KASAN_SW_TAGS
78 78
79endchoice 79endchoice
80 80
81config KASAN_EXTRA
82 bool "KASAN: extra checks"
83 depends on KASAN_GENERIC && DEBUG_KERNEL && !COMPILE_TEST
84 help
85 This enables further checks in generic KASAN, for now it only
86 includes the address-use-after-scope check that can lead to
87 excessive kernel stack usage, frame size warnings and longer
88 compile time.
89 See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81715
90
91choice 81choice
92 prompt "Instrumentation type" 82 prompt "Instrumentation type"
93 depends on KASAN 83 depends on KASAN
@@ -113,6 +103,28 @@ config KASAN_INLINE
113 103
114endchoice 104endchoice
115 105
106config KASAN_STACK_ENABLE
107 bool "Enable stack instrumentation (unsafe)" if CC_IS_CLANG && !COMPILE_TEST
108 default !(CLANG_VERSION < 90000)
109 depends on KASAN
110 help
111 The LLVM stack address sanitizer has a know problem that
112 causes excessive stack usage in a lot of functions, see
113 https://bugs.llvm.org/show_bug.cgi?id=38809
114 Disabling asan-stack makes it safe to run kernels build
115 with clang-8 with KASAN enabled, though it loses some of
116 the functionality.
117 This feature is always disabled when compile-testing with clang-8
118 or earlier to avoid cluttering the output in stack overflow
119 warnings, but clang-8 users can still enable it for builds without
120 CONFIG_COMPILE_TEST. On gcc and later clang versions it is
121 assumed to always be safe to use and enabled by default.
122
123config KASAN_STACK
124 int
125 default 1 if KASAN_STACK_ENABLE || CC_IS_GCC
126 default 0
127
116config KASAN_S390_4_LEVEL_PAGING 128config KASAN_S390_4_LEVEL_PAGING
117 bool "KASan: use 4-level paging" 129 bool "KASan: use 4-level paging"
118 depends on KASAN && S390 130 depends on KASAN && S390
diff --git a/lib/Kconfig.ubsan b/lib/Kconfig.ubsan
index 98fa559ebd80..a2ae4a8e4fa6 100644
--- a/lib/Kconfig.ubsan
+++ b/lib/Kconfig.ubsan
@@ -27,15 +27,19 @@ config UBSAN_SANITIZE_ALL
27 Enabling this option will get kernel image size increased 27 Enabling this option will get kernel image size increased
28 significantly. 28 significantly.
29 29
30config UBSAN_ALIGNMENT 30config UBSAN_NO_ALIGNMENT
31 bool "Enable checking of pointers alignment" 31 bool "Disable checking of pointers alignment"
32 depends on UBSAN 32 depends on UBSAN
33 default y if !HAVE_EFFICIENT_UNALIGNED_ACCESS 33 default y if HAVE_EFFICIENT_UNALIGNED_ACCESS
34 help 34 help
35 This option enables detection of unaligned memory accesses. 35 This option disables the check of unaligned memory accesses.
36 Enabling this option on architectures that support unaligned 36 This option should be used when building allmodconfig.
37 Disabling this option on architectures that support unaligned
37 accesses may produce a lot of false positives. 38 accesses may produce a lot of false positives.
38 39
40config UBSAN_ALIGNMENT
41 def_bool !UBSAN_NO_ALIGNMENT
42
39config TEST_UBSAN 43config TEST_UBSAN
40 tristate "Module for testing for undefined behavior detection" 44 tristate "Module for testing for undefined behavior detection"
41 depends on m && UBSAN 45 depends on m && UBSAN
diff --git a/lib/Makefile b/lib/Makefile
index e1b59da71418..3b08673e8881 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -35,10 +35,11 @@ obj-y += lockref.o
35 35
36obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \ 36obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \
37 bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \ 37 bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \
38 gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \ 38 gcd.o lcm.o list_sort.o uuid.o iov_iter.o clz_ctz.o \
39 bsearch.o find_bit.o llist.o memweight.o kfifo.o \ 39 bsearch.o find_bit.o llist.o memweight.o kfifo.o \
40 percpu-refcount.o rhashtable.o reciprocal_div.o \ 40 percpu-refcount.o rhashtable.o reciprocal_div.o \
41 once.o refcount.o usercopy.o errseq.o bucket_locks.o 41 once.o refcount.o usercopy.o errseq.o bucket_locks.o \
42 generic-radix-tree.o
42obj-$(CONFIG_STRING_SELFTEST) += test_string.o 43obj-$(CONFIG_STRING_SELFTEST) += test_string.o
43obj-y += string_helpers.o 44obj-y += string_helpers.o
44obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o 45obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
@@ -60,6 +61,7 @@ UBSAN_SANITIZE_test_ubsan.o := y
60obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o 61obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
61obj-$(CONFIG_TEST_LIST_SORT) += test_list_sort.o 62obj-$(CONFIG_TEST_LIST_SORT) += test_list_sort.o
62obj-$(CONFIG_TEST_LKM) += test_module.o 63obj-$(CONFIG_TEST_LKM) += test_module.o
64obj-$(CONFIG_TEST_VMALLOC) += test_vmalloc.o
63obj-$(CONFIG_TEST_OVERFLOW) += test_overflow.o 65obj-$(CONFIG_TEST_OVERFLOW) += test_overflow.o
64obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o 66obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o
65obj-$(CONFIG_TEST_SORT) += test_sort.o 67obj-$(CONFIG_TEST_SORT) += test_sort.o
@@ -76,6 +78,9 @@ obj-$(CONFIG_TEST_KMOD) += test_kmod.o
76obj-$(CONFIG_TEST_DEBUG_VIRTUAL) += test_debug_virtual.o 78obj-$(CONFIG_TEST_DEBUG_VIRTUAL) += test_debug_virtual.o
77obj-$(CONFIG_TEST_MEMCAT_P) += test_memcat_p.o 79obj-$(CONFIG_TEST_MEMCAT_P) += test_memcat_p.o
78obj-$(CONFIG_TEST_OBJAGG) += test_objagg.o 80obj-$(CONFIG_TEST_OBJAGG) += test_objagg.o
81obj-$(CONFIG_TEST_STACKINIT) += test_stackinit.o
82
83obj-$(CONFIG_TEST_LIVEPATCH) += livepatch/
79 84
80ifeq ($(CONFIG_DEBUG_KOBJECT),y) 85ifeq ($(CONFIG_DEBUG_KOBJECT),y)
81CFLAGS_kobject.o += -DDEBUG 86CFLAGS_kobject.o += -DDEBUG
@@ -208,7 +213,7 @@ KCOV_INSTRUMENT_stackdepot.o := n
208libfdt_files = fdt.o fdt_ro.o fdt_wip.o fdt_rw.o fdt_sw.o fdt_strerror.o \ 213libfdt_files = fdt.o fdt_ro.o fdt_wip.o fdt_rw.o fdt_sw.o fdt_strerror.o \
209 fdt_empty_tree.o 214 fdt_empty_tree.o
210$(foreach file, $(libfdt_files), \ 215$(foreach file, $(libfdt_files), \
211 $(eval CFLAGS_$(file) = -I$(src)/../scripts/dtc/libfdt)) 216 $(eval CFLAGS_$(file) = -I $(srctree)/scripts/dtc/libfdt))
212lib-$(CONFIG_LIBFDT) += $(libfdt_files) 217lib-$(CONFIG_LIBFDT) += $(libfdt_files)
213 218
214obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o 219obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o
diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index c6659cb37033..edc3c14af41d 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -768,9 +768,11 @@ all_leaves_cluster_together:
768 new_s0->index_key[i] = 768 new_s0->index_key[i] =
769 ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE); 769 ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
770 770
771 blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK); 771 if (level & ASSOC_ARRAY_KEY_CHUNK_MASK) {
772 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank); 772 blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
773 new_s0->index_key[keylen - 1] &= ~blank; 773 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);
774 new_s0->index_key[keylen - 1] &= ~blank;
775 }
774 776
775 /* This now reduces to a node splitting exercise for which we'll need 777 /* This now reduces to a node splitting exercise for which we'll need
776 * to regenerate the disparity table. 778 * to regenerate the disparity table.
@@ -1115,6 +1117,7 @@ struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
1115 index_key)) 1117 index_key))
1116 goto found_leaf; 1118 goto found_leaf;
1117 } 1119 }
1120 /* fall through */
1118 case assoc_array_walk_tree_empty: 1121 case assoc_array_walk_tree_empty:
1119 case assoc_array_walk_found_wrong_shortcut: 1122 case assoc_array_walk_found_wrong_shortcut:
1120 default: 1123 default:
diff --git a/lib/bsearch.c b/lib/bsearch.c
index 18b445b010c3..82512fe7b33c 100644
--- a/lib/bsearch.c
+++ b/lib/bsearch.c
@@ -11,6 +11,7 @@
11 11
12#include <linux/export.h> 12#include <linux/export.h>
13#include <linux/bsearch.h> 13#include <linux/bsearch.h>
14#include <linux/kprobes.h>
14 15
15/* 16/*
16 * bsearch - binary search an array of elements 17 * bsearch - binary search an array of elements
@@ -53,3 +54,4 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
53 return NULL; 54 return NULL;
54} 55}
55EXPORT_SYMBOL(bsearch); 56EXPORT_SYMBOL(bsearch);
57NOKPROBE_SYMBOL(bsearch);
diff --git a/lib/cpumask.c b/lib/cpumask.c
index 8d666ab84b5c..0cb672eb107c 100644
--- a/lib/cpumask.c
+++ b/lib/cpumask.c
@@ -5,6 +5,7 @@
5#include <linux/cpumask.h> 5#include <linux/cpumask.h>
6#include <linux/export.h> 6#include <linux/export.h>
7#include <linux/memblock.h> 7#include <linux/memblock.h>
8#include <linux/numa.h>
8 9
9/** 10/**
10 * cpumask_next - get the next cpu in a cpumask 11 * cpumask_next - get the next cpu in a cpumask
@@ -164,6 +165,9 @@ EXPORT_SYMBOL(zalloc_cpumask_var);
164void __init alloc_bootmem_cpumask_var(cpumask_var_t *mask) 165void __init alloc_bootmem_cpumask_var(cpumask_var_t *mask)
165{ 166{
166 *mask = memblock_alloc(cpumask_size(), SMP_CACHE_BYTES); 167 *mask = memblock_alloc(cpumask_size(), SMP_CACHE_BYTES);
168 if (!*mask)
169 panic("%s: Failed to allocate %u bytes\n", __func__,
170 cpumask_size());
167} 171}
168 172
169/** 173/**
@@ -206,7 +210,7 @@ unsigned int cpumask_local_spread(unsigned int i, int node)
206 /* Wrap: we always want a cpu. */ 210 /* Wrap: we always want a cpu. */
207 i %= num_online_cpus(); 211 i %= num_online_cpus();
208 212
209 if (node == -1) { 213 if (node == NUMA_NO_NODE) {
210 for_each_cpu(cpu, cpu_online_mask) 214 for_each_cpu(cpu, cpu_online_mask)
211 if (i-- == 0) 215 if (i-- == 0)
212 return cpu; 216 return cpu;
diff --git a/lib/crc32.c b/lib/crc32.c
index 45b1d67a1767..4a20455d1f61 100644
--- a/lib/crc32.c
+++ b/lib/crc32.c
@@ -206,8 +206,8 @@ u32 __pure __weak __crc32c_le(u32 crc, unsigned char const *p, size_t len)
206EXPORT_SYMBOL(crc32_le); 206EXPORT_SYMBOL(crc32_le);
207EXPORT_SYMBOL(__crc32c_le); 207EXPORT_SYMBOL(__crc32c_le);
208 208
209u32 crc32_le_base(u32, unsigned char const *, size_t) __alias(crc32_le); 209u32 __pure crc32_le_base(u32, unsigned char const *, size_t) __alias(crc32_le);
210u32 __crc32c_le_base(u32, unsigned char const *, size_t) __alias(__crc32c_le); 210u32 __pure __crc32c_le_base(u32, unsigned char const *, size_t) __alias(__crc32c_le);
211 211
212/* 212/*
213 * This multiplies the polynomials x and y modulo the given modulus. 213 * This multiplies the polynomials x and y modulo the given modulus.
diff --git a/lib/devres.c b/lib/devres.c
index faccf1a037d0..69bed2f38306 100644
--- a/lib/devres.c
+++ b/lib/devres.c
@@ -134,7 +134,6 @@ EXPORT_SYMBOL(devm_iounmap);
134void __iomem *devm_ioremap_resource(struct device *dev, struct resource *res) 134void __iomem *devm_ioremap_resource(struct device *dev, struct resource *res)
135{ 135{
136 resource_size_t size; 136 resource_size_t size;
137 const char *name;
138 void __iomem *dest_ptr; 137 void __iomem *dest_ptr;
139 138
140 BUG_ON(!dev); 139 BUG_ON(!dev);
@@ -145,9 +144,8 @@ void __iomem *devm_ioremap_resource(struct device *dev, struct resource *res)
145 } 144 }
146 145
147 size = resource_size(res); 146 size = resource_size(res);
148 name = res->name ?: dev_name(dev);
149 147
150 if (!devm_request_mem_region(dev, res->start, size, name)) { 148 if (!devm_request_mem_region(dev, res->start, size, dev_name(dev))) {
151 dev_err(dev, "can't request region for resource %pR\n", res); 149 dev_err(dev, "can't request region for resource %pR\n", res);
152 return IOMEM_ERR_PTR(-EBUSY); 150 return IOMEM_ERR_PTR(-EBUSY);
153 } 151 }
diff --git a/lib/div64.c b/lib/div64.c
index 01c8602bb6ff..ee146bb4c558 100644
--- a/lib/div64.c
+++ b/lib/div64.c
@@ -109,7 +109,7 @@ u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
109 quot = div_u64_rem(dividend, divisor, &rem32); 109 quot = div_u64_rem(dividend, divisor, &rem32);
110 *remainder = rem32; 110 *remainder = rem32;
111 } else { 111 } else {
112 int n = 1 + fls(high); 112 int n = fls(high);
113 quot = div_u64(dividend >> n, divisor >> n); 113 quot = div_u64(dividend >> n, divisor >> n);
114 114
115 if (quot != 0) 115 if (quot != 0)
@@ -147,7 +147,7 @@ u64 div64_u64(u64 dividend, u64 divisor)
147 if (high == 0) { 147 if (high == 0) {
148 quot = div_u64(dividend, divisor); 148 quot = div_u64(dividend, divisor);
149 } else { 149 } else {
150 int n = 1 + fls(high); 150 int n = fls(high);
151 quot = div_u64(dividend >> n, divisor >> n); 151 quot = div_u64(dividend >> n, divisor >> n);
152 152
153 if (quot != 0) 153 if (quot != 0)
diff --git a/lib/dynamic_debug.c b/lib/dynamic_debug.c
index dbf2b457e47e..7bdf98c37e91 100644
--- a/lib/dynamic_debug.c
+++ b/lib/dynamic_debug.c
@@ -847,17 +847,19 @@ int ddebug_add_module(struct _ddebug *tab, unsigned int n,
847 const char *name) 847 const char *name)
848{ 848{
849 struct ddebug_table *dt; 849 struct ddebug_table *dt;
850 const char *new_name;
851 850
852 dt = kzalloc(sizeof(*dt), GFP_KERNEL); 851 dt = kzalloc(sizeof(*dt), GFP_KERNEL);
853 if (dt == NULL) 852 if (dt == NULL) {
854 return -ENOMEM; 853 pr_err("error adding module: %s\n", name);
855 new_name = kstrdup_const(name, GFP_KERNEL);
856 if (new_name == NULL) {
857 kfree(dt);
858 return -ENOMEM; 854 return -ENOMEM;
859 } 855 }
860 dt->mod_name = new_name; 856 /*
857 * For built-in modules, name lives in .rodata and is
858 * immortal. For loaded modules, name points at the name[]
859 * member of struct module, which lives at least as long as
860 * this struct ddebug_table.
861 */
862 dt->mod_name = name;
861 dt->num_ddebugs = n; 863 dt->num_ddebugs = n;
862 dt->ddebugs = tab; 864 dt->ddebugs = tab;
863 865
@@ -868,7 +870,6 @@ int ddebug_add_module(struct _ddebug *tab, unsigned int n,
868 vpr_info("%u debug prints in module %s\n", n, dt->mod_name); 870 vpr_info("%u debug prints in module %s\n", n, dt->mod_name);
869 return 0; 871 return 0;
870} 872}
871EXPORT_SYMBOL_GPL(ddebug_add_module);
872 873
873/* helper for ddebug_dyndbg_(boot|module)_param_cb */ 874/* helper for ddebug_dyndbg_(boot|module)_param_cb */
874static int ddebug_dyndbg_param_cb(char *param, char *val, 875static int ddebug_dyndbg_param_cb(char *param, char *val,
@@ -913,7 +914,6 @@ int ddebug_dyndbg_module_param_cb(char *param, char *val, const char *module)
913static void ddebug_table_free(struct ddebug_table *dt) 914static void ddebug_table_free(struct ddebug_table *dt)
914{ 915{
915 list_del_init(&dt->link); 916 list_del_init(&dt->link);
916 kfree_const(dt->mod_name);
917 kfree(dt); 917 kfree(dt);
918} 918}
919 919
@@ -930,15 +930,15 @@ int ddebug_remove_module(const char *mod_name)
930 930
931 mutex_lock(&ddebug_lock); 931 mutex_lock(&ddebug_lock);
932 list_for_each_entry_safe(dt, nextdt, &ddebug_tables, link) { 932 list_for_each_entry_safe(dt, nextdt, &ddebug_tables, link) {
933 if (!strcmp(dt->mod_name, mod_name)) { 933 if (dt->mod_name == mod_name) {
934 ddebug_table_free(dt); 934 ddebug_table_free(dt);
935 ret = 0; 935 ret = 0;
936 break;
936 } 937 }
937 } 938 }
938 mutex_unlock(&ddebug_lock); 939 mutex_unlock(&ddebug_lock);
939 return ret; 940 return ret;
940} 941}
941EXPORT_SYMBOL_GPL(ddebug_remove_module);
942 942
943static void ddebug_remove_all_tables(void) 943static void ddebug_remove_all_tables(void)
944{ 944{
diff --git a/lib/flex_array.c b/lib/flex_array.c
deleted file mode 100644
index 2eed22fa507c..000000000000
--- a/lib/flex_array.c
+++ /dev/null
@@ -1,398 +0,0 @@
1/*
2 * Flexible array managed in PAGE_SIZE parts
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 *
18 * Copyright IBM Corporation, 2009
19 *
20 * Author: Dave Hansen <dave@linux.vnet.ibm.com>
21 */
22
23#include <linux/flex_array.h>
24#include <linux/slab.h>
25#include <linux/stddef.h>
26#include <linux/export.h>
27#include <linux/reciprocal_div.h>
28
29struct flex_array_part {
30 char elements[FLEX_ARRAY_PART_SIZE];
31};
32
33/*
34 * If a user requests an allocation which is small
35 * enough, we may simply use the space in the
36 * flex_array->parts[] array to store the user
37 * data.
38 */
39static inline int elements_fit_in_base(struct flex_array *fa)
40{
41 int data_size = fa->element_size * fa->total_nr_elements;
42 if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT)
43 return 1;
44 return 0;
45}
46
47/**
48 * flex_array_alloc - allocate a new flexible array
49 * @element_size: the size of individual elements in the array
50 * @total: total number of elements that this should hold
51 * @flags: page allocation flags to use for base array
52 *
53 * Note: all locking must be provided by the caller.
54 *
55 * @total is used to size internal structures. If the user ever
56 * accesses any array indexes >=@total, it will produce errors.
57 *
58 * The maximum number of elements is defined as: the number of
59 * elements that can be stored in a page times the number of
60 * page pointers that we can fit in the base structure or (using
61 * integer math):
62 *
63 * (PAGE_SIZE/element_size) * (PAGE_SIZE-8)/sizeof(void *)
64 *
65 * Here's a table showing example capacities. Note that the maximum
66 * index that the get/put() functions is just nr_objects-1. This
67 * basically means that you get 4MB of storage on 32-bit and 2MB on
68 * 64-bit.
69 *
70 *
71 * Element size | Objects | Objects |
72 * PAGE_SIZE=4k | 32-bit | 64-bit |
73 * ---------------------------------|
74 * 1 bytes | 4177920 | 2088960 |
75 * 2 bytes | 2088960 | 1044480 |
76 * 3 bytes | 1392300 | 696150 |
77 * 4 bytes | 1044480 | 522240 |
78 * 32 bytes | 130560 | 65408 |
79 * 33 bytes | 126480 | 63240 |
80 * 2048 bytes | 2040 | 1020 |
81 * 2049 bytes | 1020 | 510 |
82 * void * | 1044480 | 261120 |
83 *
84 * Since 64-bit pointers are twice the size, we lose half the
85 * capacity in the base structure. Also note that no effort is made
86 * to efficiently pack objects across page boundaries.
87 */
88struct flex_array *flex_array_alloc(int element_size, unsigned int total,
89 gfp_t flags)
90{
91 struct flex_array *ret;
92 int elems_per_part = 0;
93 int max_size = 0;
94 struct reciprocal_value reciprocal_elems = { 0 };
95
96 if (element_size) {
97 elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
98 reciprocal_elems = reciprocal_value(elems_per_part);
99 max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
100 }
101
102 /* max_size will end up 0 if element_size > PAGE_SIZE */
103 if (total > max_size)
104 return NULL;
105 ret = kzalloc(sizeof(struct flex_array), flags);
106 if (!ret)
107 return NULL;
108 ret->element_size = element_size;
109 ret->total_nr_elements = total;
110 ret->elems_per_part = elems_per_part;
111 ret->reciprocal_elems = reciprocal_elems;
112 if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
113 memset(&ret->parts[0], FLEX_ARRAY_FREE,
114 FLEX_ARRAY_BASE_BYTES_LEFT);
115 return ret;
116}
117EXPORT_SYMBOL(flex_array_alloc);
118
119static int fa_element_to_part_nr(struct flex_array *fa,
120 unsigned int element_nr)
121{
122 /*
123 * if element_size == 0 we don't get here, so we never touch
124 * the zeroed fa->reciprocal_elems, which would yield invalid
125 * results
126 */
127 return reciprocal_divide(element_nr, fa->reciprocal_elems);
128}
129
130/**
131 * flex_array_free_parts - just free the second-level pages
132 * @fa: the flex array from which to free parts
133 *
134 * This is to be used in cases where the base 'struct flex_array'
135 * has been statically allocated and should not be free.
136 */
137void flex_array_free_parts(struct flex_array *fa)
138{
139 int part_nr;
140
141 if (elements_fit_in_base(fa))
142 return;
143 for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++)
144 kfree(fa->parts[part_nr]);
145}
146EXPORT_SYMBOL(flex_array_free_parts);
147
148void flex_array_free(struct flex_array *fa)
149{
150 flex_array_free_parts(fa);
151 kfree(fa);
152}
153EXPORT_SYMBOL(flex_array_free);
154
155static unsigned int index_inside_part(struct flex_array *fa,
156 unsigned int element_nr,
157 unsigned int part_nr)
158{
159 unsigned int part_offset;
160
161 part_offset = element_nr - part_nr * fa->elems_per_part;
162 return part_offset * fa->element_size;
163}
164
165static struct flex_array_part *
166__fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags)
167{
168 struct flex_array_part *part = fa->parts[part_nr];
169 if (!part) {
170 part = kmalloc(sizeof(struct flex_array_part), flags);
171 if (!part)
172 return NULL;
173 if (!(flags & __GFP_ZERO))
174 memset(part, FLEX_ARRAY_FREE,
175 sizeof(struct flex_array_part));
176 fa->parts[part_nr] = part;
177 }
178 return part;
179}
180
181/**
182 * flex_array_put - copy data into the array at @element_nr
183 * @fa: the flex array to copy data into
184 * @element_nr: index of the position in which to insert
185 * the new element.
186 * @src: address of data to copy into the array
187 * @flags: page allocation flags to use for array expansion
188 *
189 *
190 * Note that this *copies* the contents of @src into
191 * the array. If you are trying to store an array of
192 * pointers, make sure to pass in &ptr instead of ptr.
193 * You may instead wish to use the flex_array_put_ptr()
194 * helper function.
195 *
196 * Locking must be provided by the caller.
197 */
198int flex_array_put(struct flex_array *fa, unsigned int element_nr, void *src,
199 gfp_t flags)
200{
201 int part_nr = 0;
202 struct flex_array_part *part;
203 void *dst;
204
205 if (element_nr >= fa->total_nr_elements)
206 return -ENOSPC;
207 if (!fa->element_size)
208 return 0;
209 if (elements_fit_in_base(fa))
210 part = (struct flex_array_part *)&fa->parts[0];
211 else {
212 part_nr = fa_element_to_part_nr(fa, element_nr);
213 part = __fa_get_part(fa, part_nr, flags);
214 if (!part)
215 return -ENOMEM;
216 }
217 dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
218 memcpy(dst, src, fa->element_size);
219 return 0;
220}
221EXPORT_SYMBOL(flex_array_put);
222
223/**
224 * flex_array_clear - clear element in array at @element_nr
225 * @fa: the flex array of the element.
226 * @element_nr: index of the position to clear.
227 *
228 * Locking must be provided by the caller.
229 */
230int flex_array_clear(struct flex_array *fa, unsigned int element_nr)
231{
232 int part_nr = 0;
233 struct flex_array_part *part;
234 void *dst;
235
236 if (element_nr >= fa->total_nr_elements)
237 return -ENOSPC;
238 if (!fa->element_size)
239 return 0;
240 if (elements_fit_in_base(fa))
241 part = (struct flex_array_part *)&fa->parts[0];
242 else {
243 part_nr = fa_element_to_part_nr(fa, element_nr);
244 part = fa->parts[part_nr];
245 if (!part)
246 return -EINVAL;
247 }
248 dst = &part->elements[index_inside_part(fa, element_nr, part_nr)];
249 memset(dst, FLEX_ARRAY_FREE, fa->element_size);
250 return 0;
251}
252EXPORT_SYMBOL(flex_array_clear);
253
254/**
255 * flex_array_prealloc - guarantee that array space exists
256 * @fa: the flex array for which to preallocate parts
257 * @start: index of first array element for which space is allocated
258 * @nr_elements: number of elements for which space is allocated
259 * @flags: page allocation flags
260 *
261 * This will guarantee that no future calls to flex_array_put()
262 * will allocate memory. It can be used if you are expecting to
263 * be holding a lock or in some atomic context while writing
264 * data into the array.
265 *
266 * Locking must be provided by the caller.
267 */
268int flex_array_prealloc(struct flex_array *fa, unsigned int start,
269 unsigned int nr_elements, gfp_t flags)
270{
271 int start_part;
272 int end_part;
273 int part_nr;
274 unsigned int end;
275 struct flex_array_part *part;
276
277 if (!start && !nr_elements)
278 return 0;
279 if (start >= fa->total_nr_elements)
280 return -ENOSPC;
281 if (!nr_elements)
282 return 0;
283
284 end = start + nr_elements - 1;
285
286 if (end >= fa->total_nr_elements)
287 return -ENOSPC;
288 if (!fa->element_size)
289 return 0;
290 if (elements_fit_in_base(fa))
291 return 0;
292 start_part = fa_element_to_part_nr(fa, start);
293 end_part = fa_element_to_part_nr(fa, end);
294 for (part_nr = start_part; part_nr <= end_part; part_nr++) {
295 part = __fa_get_part(fa, part_nr, flags);
296 if (!part)
297 return -ENOMEM;
298 }
299 return 0;
300}
301EXPORT_SYMBOL(flex_array_prealloc);
302
303/**
304 * flex_array_get - pull data back out of the array
305 * @fa: the flex array from which to extract data
306 * @element_nr: index of the element to fetch from the array
307 *
308 * Returns a pointer to the data at index @element_nr. Note
309 * that this is a copy of the data that was passed in. If you
310 * are using this to store pointers, you'll get back &ptr. You
311 * may instead wish to use the flex_array_get_ptr helper.
312 *
313 * Locking must be provided by the caller.
314 */
315void *flex_array_get(struct flex_array *fa, unsigned int element_nr)
316{
317 int part_nr = 0;
318 struct flex_array_part *part;
319
320 if (!fa->element_size)
321 return NULL;
322 if (element_nr >= fa->total_nr_elements)
323 return NULL;
324 if (elements_fit_in_base(fa))
325 part = (struct flex_array_part *)&fa->parts[0];
326 else {
327 part_nr = fa_element_to_part_nr(fa, element_nr);
328 part = fa->parts[part_nr];
329 if (!part)
330 return NULL;
331 }
332 return &part->elements[index_inside_part(fa, element_nr, part_nr)];
333}
334EXPORT_SYMBOL(flex_array_get);
335
336/**
337 * flex_array_get_ptr - pull a ptr back out of the array
338 * @fa: the flex array from which to extract data
339 * @element_nr: index of the element to fetch from the array
340 *
341 * Returns the pointer placed in the flex array at element_nr using
342 * flex_array_put_ptr(). This function should not be called if the
343 * element in question was not set using the _put_ptr() helper.
344 */
345void *flex_array_get_ptr(struct flex_array *fa, unsigned int element_nr)
346{
347 void **tmp;
348
349 tmp = flex_array_get(fa, element_nr);
350 if (!tmp)
351 return NULL;
352
353 return *tmp;
354}
355EXPORT_SYMBOL(flex_array_get_ptr);
356
357static int part_is_free(struct flex_array_part *part)
358{
359 int i;
360
361 for (i = 0; i < sizeof(struct flex_array_part); i++)
362 if (part->elements[i] != FLEX_ARRAY_FREE)
363 return 0;
364 return 1;
365}
366
367/**
368 * flex_array_shrink - free unused second-level pages
369 * @fa: the flex array to shrink
370 *
371 * Frees all second-level pages that consist solely of unused
372 * elements. Returns the number of pages freed.
373 *
374 * Locking must be provided by the caller.
375 */
376int flex_array_shrink(struct flex_array *fa)
377{
378 struct flex_array_part *part;
379 int part_nr;
380 int ret = 0;
381
382 if (!fa->total_nr_elements || !fa->element_size)
383 return 0;
384 if (elements_fit_in_base(fa))
385 return ret;
386 for (part_nr = 0; part_nr < FLEX_ARRAY_NR_BASE_PTRS; part_nr++) {
387 part = fa->parts[part_nr];
388 if (!part)
389 continue;
390 if (part_is_free(part)) {
391 fa->parts[part_nr] = NULL;
392 kfree(part);
393 ret++;
394 }
395 }
396 return ret;
397}
398EXPORT_SYMBOL(flex_array_shrink);
diff --git a/lib/generic-radix-tree.c b/lib/generic-radix-tree.c
new file mode 100644
index 000000000000..a7bafc413730
--- /dev/null
+++ b/lib/generic-radix-tree.c
@@ -0,0 +1,217 @@
1
2#include <linux/export.h>
3#include <linux/generic-radix-tree.h>
4#include <linux/gfp.h>
5
6#define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *))
7#define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY)
8
9struct genradix_node {
10 union {
11 /* Interior node: */
12 struct genradix_node *children[GENRADIX_ARY];
13
14 /* Leaf: */
15 u8 data[PAGE_SIZE];
16 };
17};
18
19static inline int genradix_depth_shift(unsigned depth)
20{
21 return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
22}
23
24/*
25 * Returns size (of data, in bytes) that a tree of a given depth holds:
26 */
27static inline size_t genradix_depth_size(unsigned depth)
28{
29 return 1UL << genradix_depth_shift(depth);
30}
31
32/* depth that's needed for a genradix that can address up to ULONG_MAX: */
33#define GENRADIX_MAX_DEPTH \
34 DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
35
36#define GENRADIX_DEPTH_MASK \
37 ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
38
39unsigned genradix_root_to_depth(struct genradix_root *r)
40{
41 return (unsigned long) r & GENRADIX_DEPTH_MASK;
42}
43
44struct genradix_node *genradix_root_to_node(struct genradix_root *r)
45{
46 return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
47}
48
49/*
50 * Returns pointer to the specified byte @offset within @radix, or NULL if not
51 * allocated
52 */
53void *__genradix_ptr(struct __genradix *radix, size_t offset)
54{
55 struct genradix_root *r = READ_ONCE(radix->root);
56 struct genradix_node *n = genradix_root_to_node(r);
57 unsigned level = genradix_root_to_depth(r);
58
59 if (ilog2(offset) >= genradix_depth_shift(level))
60 return NULL;
61
62 while (1) {
63 if (!n)
64 return NULL;
65 if (!level)
66 break;
67
68 level--;
69
70 n = n->children[offset >> genradix_depth_shift(level)];
71 offset &= genradix_depth_size(level) - 1;
72 }
73
74 return &n->data[offset];
75}
76EXPORT_SYMBOL(__genradix_ptr);
77
78/*
79 * Returns pointer to the specified byte @offset within @radix, allocating it if
80 * necessary - newly allocated slots are always zeroed out:
81 */
82void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
83 gfp_t gfp_mask)
84{
85 struct genradix_root *v = READ_ONCE(radix->root);
86 struct genradix_node *n, *new_node = NULL;
87 unsigned level;
88
89 /* Increase tree depth if necessary: */
90 while (1) {
91 struct genradix_root *r = v, *new_root;
92
93 n = genradix_root_to_node(r);
94 level = genradix_root_to_depth(r);
95
96 if (n && ilog2(offset) < genradix_depth_shift(level))
97 break;
98
99 if (!new_node) {
100 new_node = (void *)
101 __get_free_page(gfp_mask|__GFP_ZERO);
102 if (!new_node)
103 return NULL;
104 }
105
106 new_node->children[0] = n;
107 new_root = ((struct genradix_root *)
108 ((unsigned long) new_node | (n ? level + 1 : 0)));
109
110 if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
111 v = new_root;
112 new_node = NULL;
113 }
114 }
115
116 while (level--) {
117 struct genradix_node **p =
118 &n->children[offset >> genradix_depth_shift(level)];
119 offset &= genradix_depth_size(level) - 1;
120
121 n = READ_ONCE(*p);
122 if (!n) {
123 if (!new_node) {
124 new_node = (void *)
125 __get_free_page(gfp_mask|__GFP_ZERO);
126 if (!new_node)
127 return NULL;
128 }
129
130 if (!(n = cmpxchg_release(p, NULL, new_node)))
131 swap(n, new_node);
132 }
133 }
134
135 if (new_node)
136 free_page((unsigned long) new_node);
137
138 return &n->data[offset];
139}
140EXPORT_SYMBOL(__genradix_ptr_alloc);
141
142void *__genradix_iter_peek(struct genradix_iter *iter,
143 struct __genradix *radix,
144 size_t objs_per_page)
145{
146 struct genradix_root *r;
147 struct genradix_node *n;
148 unsigned level, i;
149restart:
150 r = READ_ONCE(radix->root);
151 if (!r)
152 return NULL;
153
154 n = genradix_root_to_node(r);
155 level = genradix_root_to_depth(r);
156
157 if (ilog2(iter->offset) >= genradix_depth_shift(level))
158 return NULL;
159
160 while (level) {
161 level--;
162
163 i = (iter->offset >> genradix_depth_shift(level)) &
164 (GENRADIX_ARY - 1);
165
166 while (!n->children[i]) {
167 i++;
168 iter->offset = round_down(iter->offset +
169 genradix_depth_size(level),
170 genradix_depth_size(level));
171 iter->pos = (iter->offset >> PAGE_SHIFT) *
172 objs_per_page;
173 if (i == GENRADIX_ARY)
174 goto restart;
175 }
176
177 n = n->children[i];
178 }
179
180 return &n->data[iter->offset & (PAGE_SIZE - 1)];
181}
182EXPORT_SYMBOL(__genradix_iter_peek);
183
184static void genradix_free_recurse(struct genradix_node *n, unsigned level)
185{
186 if (level) {
187 unsigned i;
188
189 for (i = 0; i < GENRADIX_ARY; i++)
190 if (n->children[i])
191 genradix_free_recurse(n->children[i], level - 1);
192 }
193
194 free_page((unsigned long) n);
195}
196
197int __genradix_prealloc(struct __genradix *radix, size_t size,
198 gfp_t gfp_mask)
199{
200 size_t offset;
201
202 for (offset = 0; offset < size; offset += PAGE_SIZE)
203 if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
204 return -ENOMEM;
205
206 return 0;
207}
208EXPORT_SYMBOL(__genradix_prealloc);
209
210void __genradix_free(struct __genradix *radix)
211{
212 struct genradix_root *r = xchg(&radix->root, NULL);
213
214 genradix_free_recurse(genradix_root_to_node(r),
215 genradix_root_to_depth(r));
216}
217EXPORT_SYMBOL(__genradix_free);
diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
index 14436f4ca6bd..30e0f9770f88 100644
--- a/lib/int_sqrt.c
+++ b/lib/int_sqrt.c
@@ -52,7 +52,7 @@ u32 int_sqrt64(u64 x)
52 if (x <= ULONG_MAX) 52 if (x <= ULONG_MAX)
53 return int_sqrt((unsigned long) x); 53 return int_sqrt((unsigned long) x);
54 54
55 m = 1ULL << (fls64(x) & ~1ULL); 55 m = 1ULL << ((fls64(x) - 1) & ~1ULL);
56 while (m != 0) { 56 while (m != 0) {
57 b = y + m; 57 b = y + m;
58 y >>= 1; 58 y >>= 1;
diff --git a/lib/iomap.c b/lib/iomap.c
index 541d926da95e..e909ab71e995 100644
--- a/lib/iomap.c
+++ b/lib/iomap.c
@@ -65,8 +65,9 @@ static void bad_io_access(unsigned long port, const char *access)
65#endif 65#endif
66 66
67#ifndef mmio_read16be 67#ifndef mmio_read16be
68#define mmio_read16be(addr) be16_to_cpu(__raw_readw(addr)) 68#define mmio_read16be(addr) swab16(readw(addr))
69#define mmio_read32be(addr) be32_to_cpu(__raw_readl(addr)) 69#define mmio_read32be(addr) swab32(readl(addr))
70#define mmio_read64be(addr) swab64(readq(addr))
70#endif 71#endif
71 72
72unsigned int ioread8(void __iomem *addr) 73unsigned int ioread8(void __iomem *addr)
@@ -100,14 +101,89 @@ EXPORT_SYMBOL(ioread16be);
100EXPORT_SYMBOL(ioread32); 101EXPORT_SYMBOL(ioread32);
101EXPORT_SYMBOL(ioread32be); 102EXPORT_SYMBOL(ioread32be);
102 103
104#ifdef readq
105static u64 pio_read64_lo_hi(unsigned long port)
106{
107 u64 lo, hi;
108
109 lo = inl(port);
110 hi = inl(port + sizeof(u32));
111
112 return lo | (hi << 32);
113}
114
115static u64 pio_read64_hi_lo(unsigned long port)
116{
117 u64 lo, hi;
118
119 hi = inl(port + sizeof(u32));
120 lo = inl(port);
121
122 return lo | (hi << 32);
123}
124
125static u64 pio_read64be_lo_hi(unsigned long port)
126{
127 u64 lo, hi;
128
129 lo = pio_read32be(port + sizeof(u32));
130 hi = pio_read32be(port);
131
132 return lo | (hi << 32);
133}
134
135static u64 pio_read64be_hi_lo(unsigned long port)
136{
137 u64 lo, hi;
138
139 hi = pio_read32be(port);
140 lo = pio_read32be(port + sizeof(u32));
141
142 return lo | (hi << 32);
143}
144
145u64 ioread64_lo_hi(void __iomem *addr)
146{
147 IO_COND(addr, return pio_read64_lo_hi(port), return readq(addr));
148 return 0xffffffffffffffffULL;
149}
150
151u64 ioread64_hi_lo(void __iomem *addr)
152{
153 IO_COND(addr, return pio_read64_hi_lo(port), return readq(addr));
154 return 0xffffffffffffffffULL;
155}
156
157u64 ioread64be_lo_hi(void __iomem *addr)
158{
159 IO_COND(addr, return pio_read64be_lo_hi(port),
160 return mmio_read64be(addr));
161 return 0xffffffffffffffffULL;
162}
163
164u64 ioread64be_hi_lo(void __iomem *addr)
165{
166 IO_COND(addr, return pio_read64be_hi_lo(port),
167 return mmio_read64be(addr));
168 return 0xffffffffffffffffULL;
169}
170
171EXPORT_SYMBOL(ioread64_lo_hi);
172EXPORT_SYMBOL(ioread64_hi_lo);
173EXPORT_SYMBOL(ioread64be_lo_hi);
174EXPORT_SYMBOL(ioread64be_hi_lo);
175
176#endif /* readq */
177
103#ifndef pio_write16be 178#ifndef pio_write16be
104#define pio_write16be(val,port) outw(swab16(val),port) 179#define pio_write16be(val,port) outw(swab16(val),port)
105#define pio_write32be(val,port) outl(swab32(val),port) 180#define pio_write32be(val,port) outl(swab32(val),port)
106#endif 181#endif
107 182
108#ifndef mmio_write16be 183#ifndef mmio_write16be
109#define mmio_write16be(val,port) __raw_writew(be16_to_cpu(val),port) 184#define mmio_write16be(val,port) writew(swab16(val),port)
110#define mmio_write32be(val,port) __raw_writel(be32_to_cpu(val),port) 185#define mmio_write32be(val,port) writel(swab32(val),port)
186#define mmio_write64be(val,port) writeq(swab64(val),port)
111#endif 187#endif
112 188
113void iowrite8(u8 val, void __iomem *addr) 189void iowrite8(u8 val, void __iomem *addr)
@@ -136,6 +212,62 @@ EXPORT_SYMBOL(iowrite16be);
136EXPORT_SYMBOL(iowrite32); 212EXPORT_SYMBOL(iowrite32);
137EXPORT_SYMBOL(iowrite32be); 213EXPORT_SYMBOL(iowrite32be);
138 214
215#ifdef writeq
216static void pio_write64_lo_hi(u64 val, unsigned long port)
217{
218 outl(val, port);
219 outl(val >> 32, port + sizeof(u32));
220}
221
222static void pio_write64_hi_lo(u64 val, unsigned long port)
223{
224 outl(val >> 32, port + sizeof(u32));
225 outl(val, port);
226}
227
228static void pio_write64be_lo_hi(u64 val, unsigned long port)
229{
230 pio_write32be(val, port + sizeof(u32));
231 pio_write32be(val >> 32, port);
232}
233
234static void pio_write64be_hi_lo(u64 val, unsigned long port)
235{
236 pio_write32be(val >> 32, port);
237 pio_write32be(val, port + sizeof(u32));
238}
239
240void iowrite64_lo_hi(u64 val, void __iomem *addr)
241{
242 IO_COND(addr, pio_write64_lo_hi(val, port),
243 writeq(val, addr));
244}
245
246void iowrite64_hi_lo(u64 val, void __iomem *addr)
247{
248 IO_COND(addr, pio_write64_hi_lo(val, port),
249 writeq(val, addr));
250}
251
252void iowrite64be_lo_hi(u64 val, void __iomem *addr)
253{
254 IO_COND(addr, pio_write64be_lo_hi(val, port),
255 mmio_write64be(val, addr));
256}
257
258void iowrite64be_hi_lo(u64 val, void __iomem *addr)
259{
260 IO_COND(addr, pio_write64be_hi_lo(val, port),
261 mmio_write64be(val, addr));
262}
263
264EXPORT_SYMBOL(iowrite64_lo_hi);
265EXPORT_SYMBOL(iowrite64_hi_lo);
266EXPORT_SYMBOL(iowrite64be_lo_hi);
267EXPORT_SYMBOL(iowrite64be_hi_lo);
268
269#endif /* readq */
270
139/* 271/*
140 * These are the "repeat MMIO read/write" functions. 272 * These are the "repeat MMIO read/write" functions.
141 * Note the "__raw" accesses, since we don't want to 273 * Note the "__raw" accesses, since we don't want to
diff --git a/lib/iov_iter.c b/lib/iov_iter.c
index be4bd627caf0..ea36dc355da1 100644
--- a/lib/iov_iter.c
+++ b/lib/iov_iter.c
@@ -861,8 +861,21 @@ EXPORT_SYMBOL(_copy_from_iter_full_nocache);
861 861
862static inline bool page_copy_sane(struct page *page, size_t offset, size_t n) 862static inline bool page_copy_sane(struct page *page, size_t offset, size_t n)
863{ 863{
864 struct page *head = compound_head(page); 864 struct page *head;
865 size_t v = n + offset + page_address(page) - page_address(head); 865 size_t v = n + offset;
866
867 /*
868 * The general case needs to access the page order in order
869 * to compute the page size.
870 * However, we mostly deal with order-0 pages and thus can
871 * avoid a possible cache line miss for requests that fit all
872 * page orders.
873 */
874 if (n <= v && v <= PAGE_SIZE)
875 return true;
876
877 head = compound_head(page);
878 v += (page - head) << PAGE_SHIFT;
866 879
867 if (likely(n <= v && v <= (PAGE_SIZE << compound_order(head)))) 880 if (likely(n <= v && v <= (PAGE_SIZE << compound_order(head))))
868 return true; 881 return true;
diff --git a/lib/irq_poll.c b/lib/irq_poll.c
index 86a709954f5a..2f17b488d58e 100644
--- a/lib/irq_poll.c
+++ b/lib/irq_poll.c
@@ -35,7 +35,7 @@ void irq_poll_sched(struct irq_poll *iop)
35 35
36 local_irq_save(flags); 36 local_irq_save(flags);
37 list_add_tail(&iop->list, this_cpu_ptr(&blk_cpu_iopoll)); 37 list_add_tail(&iop->list, this_cpu_ptr(&blk_cpu_iopoll));
38 __raise_softirq_irqoff(IRQ_POLL_SOFTIRQ); 38 raise_softirq_irqoff(IRQ_POLL_SOFTIRQ);
39 local_irq_restore(flags); 39 local_irq_restore(flags);
40} 40}
41EXPORT_SYMBOL(irq_poll_sched); 41EXPORT_SYMBOL(irq_poll_sched);
diff --git a/lib/kobject.c b/lib/kobject.c
index b72e00fd7d09..aa89edcd2b63 100644
--- a/lib/kobject.c
+++ b/lib/kobject.c
@@ -887,7 +887,7 @@ static void kset_release(struct kobject *kobj)
887 kfree(kset); 887 kfree(kset);
888} 888}
889 889
890void kset_get_ownership(struct kobject *kobj, kuid_t *uid, kgid_t *gid) 890static void kset_get_ownership(struct kobject *kobj, kuid_t *uid, kgid_t *gid)
891{ 891{
892 if (kobj->parent) 892 if (kobj->parent)
893 kobject_get_ownership(kobj->parent, uid, gid); 893 kobject_get_ownership(kobj->parent, uid, gid);
diff --git a/lib/kobject_uevent.c b/lib/kobject_uevent.c
index 27c6118afd1c..f05802687ba4 100644
--- a/lib/kobject_uevent.c
+++ b/lib/kobject_uevent.c
@@ -200,7 +200,7 @@ int kobject_synth_uevent(struct kobject *kobj, const char *buf, size_t count)
200 200
201 r = kobject_action_type(buf, count, &action, &action_args); 201 r = kobject_action_type(buf, count, &action, &action_args);
202 if (r) { 202 if (r) {
203 msg = "unknown uevent action string\n"; 203 msg = "unknown uevent action string";
204 goto out; 204 goto out;
205 } 205 }
206 206
@@ -212,7 +212,7 @@ int kobject_synth_uevent(struct kobject *kobj, const char *buf, size_t count)
212 r = kobject_action_args(action_args, 212 r = kobject_action_args(action_args,
213 count - (action_args - buf), &env); 213 count - (action_args - buf), &env);
214 if (r == -EINVAL) { 214 if (r == -EINVAL) {
215 msg = "incorrect uevent action arguments\n"; 215 msg = "incorrect uevent action arguments";
216 goto out; 216 goto out;
217 } 217 }
218 218
@@ -224,7 +224,7 @@ int kobject_synth_uevent(struct kobject *kobj, const char *buf, size_t count)
224out: 224out:
225 if (r) { 225 if (r) {
226 devpath = kobject_get_path(kobj, GFP_KERNEL); 226 devpath = kobject_get_path(kobj, GFP_KERNEL);
227 printk(KERN_WARNING "synth uevent: %s: %s", 227 pr_warn("synth uevent: %s: %s\n",
228 devpath ?: "unknown device", 228 devpath ?: "unknown device",
229 msg ?: "failed to send uevent"); 229 msg ?: "failed to send uevent");
230 kfree(devpath); 230 kfree(devpath);
@@ -765,8 +765,7 @@ static int uevent_net_init(struct net *net)
765 765
766 ue_sk->sk = netlink_kernel_create(net, NETLINK_KOBJECT_UEVENT, &cfg); 766 ue_sk->sk = netlink_kernel_create(net, NETLINK_KOBJECT_UEVENT, &cfg);
767 if (!ue_sk->sk) { 767 if (!ue_sk->sk) {
768 printk(KERN_ERR 768 pr_err("kobject_uevent: unable to create netlink socket!\n");
769 "kobject_uevent: unable to create netlink socket!\n");
770 kfree(ue_sk); 769 kfree(ue_sk);
771 return -ENODEV; 770 return -ENODEV;
772 } 771 }
diff --git a/lib/livepatch/Makefile b/lib/livepatch/Makefile
new file mode 100644
index 000000000000..26900ddaef82
--- /dev/null
+++ b/lib/livepatch/Makefile
@@ -0,0 +1,15 @@
1# SPDX-License-Identifier: GPL-2.0
2#
3# Makefile for livepatch test code.
4
5obj-$(CONFIG_TEST_LIVEPATCH) += test_klp_atomic_replace.o \
6 test_klp_callbacks_demo.o \
7 test_klp_callbacks_demo2.o \
8 test_klp_callbacks_busy.o \
9 test_klp_callbacks_mod.o \
10 test_klp_livepatch.o \
11 test_klp_shadow_vars.o
12
13# Target modules to be livepatched require CC_FLAGS_FTRACE
14CFLAGS_test_klp_callbacks_busy.o += $(CC_FLAGS_FTRACE)
15CFLAGS_test_klp_callbacks_mod.o += $(CC_FLAGS_FTRACE)
diff --git a/lib/livepatch/test_klp_atomic_replace.c b/lib/livepatch/test_klp_atomic_replace.c
new file mode 100644
index 000000000000..5af7093ca00c
--- /dev/null
+++ b/lib/livepatch/test_klp_atomic_replace.c
@@ -0,0 +1,57 @@
1// SPDX-License-Identifier: GPL-2.0
2// Copyright (C) 2018 Joe Lawrence <joe.lawrence@redhat.com>
3
4#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
5
6#include <linux/module.h>
7#include <linux/kernel.h>
8#include <linux/livepatch.h>
9
10static int replace;
11module_param(replace, int, 0644);
12MODULE_PARM_DESC(replace, "replace (default=0)");
13
14#include <linux/seq_file.h>
15static int livepatch_meminfo_proc_show(struct seq_file *m, void *v)
16{
17 seq_printf(m, "%s: %s\n", THIS_MODULE->name,
18 "this has been live patched");
19 return 0;
20}
21
22static struct klp_func funcs[] = {
23 {
24 .old_name = "meminfo_proc_show",
25 .new_func = livepatch_meminfo_proc_show,
26 }, {}
27};
28
29static struct klp_object objs[] = {
30 {
31 /* name being NULL means vmlinux */
32 .funcs = funcs,
33 }, {}
34};
35
36static struct klp_patch patch = {
37 .mod = THIS_MODULE,
38 .objs = objs,
39 /* set .replace in the init function below for demo purposes */
40};
41
42static int test_klp_atomic_replace_init(void)
43{
44 patch.replace = replace;
45 return klp_enable_patch(&patch);
46}
47
48static void test_klp_atomic_replace_exit(void)
49{
50}
51
52module_init(test_klp_atomic_replace_init);
53module_exit(test_klp_atomic_replace_exit);
54MODULE_LICENSE("GPL");
55MODULE_INFO(livepatch, "Y");
56MODULE_AUTHOR("Joe Lawrence <joe.lawrence@redhat.com>");
57MODULE_DESCRIPTION("Livepatch test: atomic replace");
diff --git a/lib/livepatch/test_klp_callbacks_busy.c b/lib/livepatch/test_klp_callbacks_busy.c
new file mode 100644
index 000000000000..40beddf8a0e2
--- /dev/null
+++ b/lib/livepatch/test_klp_callbacks_busy.c
@@ -0,0 +1,43 @@
1// SPDX-License-Identifier: GPL-2.0
2// Copyright (C) 2018 Joe Lawrence <joe.lawrence@redhat.com>
3
4#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
5
6#include <linux/module.h>
7#include <linux/kernel.h>
8#include <linux/workqueue.h>
9#include <linux/delay.h>
10
11static int sleep_secs;
12module_param(sleep_secs, int, 0644);
13MODULE_PARM_DESC(sleep_secs, "sleep_secs (default=0)");
14
15static void busymod_work_func(struct work_struct *work);
16static DECLARE_DELAYED_WORK(work, busymod_work_func);
17
18static void busymod_work_func(struct work_struct *work)
19{
20 pr_info("%s, sleeping %d seconds ...\n", __func__, sleep_secs);
21 msleep(sleep_secs * 1000);
22 pr_info("%s exit\n", __func__);
23}
24
25static int test_klp_callbacks_busy_init(void)
26{
27 pr_info("%s\n", __func__);
28 schedule_delayed_work(&work,
29 msecs_to_jiffies(1000 * 0));
30 return 0;
31}
32
33static void test_klp_callbacks_busy_exit(void)
34{
35 cancel_delayed_work_sync(&work);
36 pr_info("%s\n", __func__);
37}
38
39module_init(test_klp_callbacks_busy_init);
40module_exit(test_klp_callbacks_busy_exit);
41MODULE_LICENSE("GPL");
42MODULE_AUTHOR("Joe Lawrence <joe.lawrence@redhat.com>");
43MODULE_DESCRIPTION("Livepatch test: busy target module");
diff --git a/lib/livepatch/test_klp_callbacks_demo.c b/lib/livepatch/test_klp_callbacks_demo.c
new file mode 100644
index 000000000000..3fd8fe1cd1cc
--- /dev/null
+++ b/lib/livepatch/test_klp_callbacks_demo.c
@@ -0,0 +1,121 @@
1// SPDX-License-Identifier: GPL-2.0
2// Copyright (C) 2018 Joe Lawrence <joe.lawrence@redhat.com>
3
4#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
5
6#include <linux/module.h>
7#include <linux/kernel.h>
8#include <linux/livepatch.h>
9
10static int pre_patch_ret;
11module_param(pre_patch_ret, int, 0644);
12MODULE_PARM_DESC(pre_patch_ret, "pre_patch_ret (default=0)");
13
14static const char *const module_state[] = {
15 [MODULE_STATE_LIVE] = "[MODULE_STATE_LIVE] Normal state",
16 [MODULE_STATE_COMING] = "[MODULE_STATE_COMING] Full formed, running module_init",
17 [MODULE_STATE_GOING] = "[MODULE_STATE_GOING] Going away",
18 [MODULE_STATE_UNFORMED] = "[MODULE_STATE_UNFORMED] Still setting it up",
19};
20
21static void callback_info(const char *callback, struct klp_object *obj)
22{
23 if (obj->mod)
24 pr_info("%s: %s -> %s\n", callback, obj->mod->name,
25 module_state[obj->mod->state]);
26 else
27 pr_info("%s: vmlinux\n", callback);
28}
29
30/* Executed on object patching (ie, patch enablement) */
31static int pre_patch_callback(struct klp_object *obj)
32{
33 callback_info(__func__, obj);
34 return pre_patch_ret;
35}
36
37/* Executed on object unpatching (ie, patch disablement) */
38static void post_patch_callback(struct klp_object *obj)
39{
40 callback_info(__func__, obj);
41}
42
43/* Executed on object unpatching (ie, patch disablement) */
44static void pre_unpatch_callback(struct klp_object *obj)
45{
46 callback_info(__func__, obj);
47}
48
49/* Executed on object unpatching (ie, patch disablement) */
50static void post_unpatch_callback(struct klp_object *obj)
51{
52 callback_info(__func__, obj);
53}
54
55static void patched_work_func(struct work_struct *work)
56{
57 pr_info("%s\n", __func__);
58}
59
60static struct klp_func no_funcs[] = {
61 {}
62};
63
64static struct klp_func busymod_funcs[] = {
65 {
66 .old_name = "busymod_work_func",
67 .new_func = patched_work_func,
68 }, {}
69};
70
71static struct klp_object objs[] = {
72 {
73 .name = NULL, /* vmlinux */
74 .funcs = no_funcs,
75 .callbacks = {
76 .pre_patch = pre_patch_callback,
77 .post_patch = post_patch_callback,
78 .pre_unpatch = pre_unpatch_callback,
79 .post_unpatch = post_unpatch_callback,
80 },
81 }, {
82 .name = "test_klp_callbacks_mod",
83 .funcs = no_funcs,
84 .callbacks = {
85 .pre_patch = pre_patch_callback,
86 .post_patch = post_patch_callback,
87 .pre_unpatch = pre_unpatch_callback,
88 .post_unpatch = post_unpatch_callback,
89 },
90 }, {
91 .name = "test_klp_callbacks_busy",
92 .funcs = busymod_funcs,
93 .callbacks = {
94 .pre_patch = pre_patch_callback,
95 .post_patch = post_patch_callback,
96 .pre_unpatch = pre_unpatch_callback,
97 .post_unpatch = post_unpatch_callback,
98 },
99 }, { }
100};
101
102static struct klp_patch patch = {
103 .mod = THIS_MODULE,
104 .objs = objs,
105};
106
107static int test_klp_callbacks_demo_init(void)
108{
109 return klp_enable_patch(&patch);
110}
111
112static void test_klp_callbacks_demo_exit(void)
113{
114}
115
116module_init(test_klp_callbacks_demo_init);
117module_exit(test_klp_callbacks_demo_exit);
118MODULE_LICENSE("GPL");
119MODULE_INFO(livepatch, "Y");
120MODULE_AUTHOR("Joe Lawrence <joe.lawrence@redhat.com>");
121MODULE_DESCRIPTION("Livepatch test: livepatch demo");
diff --git a/lib/livepatch/test_klp_callbacks_demo2.c b/lib/livepatch/test_klp_callbacks_demo2.c
new file mode 100644
index 000000000000..5417573e80af
--- /dev/null
+++ b/lib/livepatch/test_klp_callbacks_demo2.c
@@ -0,0 +1,93 @@
1// SPDX-License-Identifier: GPL-2.0
2// Copyright (C) 2018 Joe Lawrence <joe.lawrence@redhat.com>
3
4#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
5
6#include <linux/module.h>
7#include <linux/kernel.h>
8#include <linux/livepatch.h>
9
10static int replace;
11module_param(replace, int, 0644);
12MODULE_PARM_DESC(replace, "replace (default=0)");
13
14static const char *const module_state[] = {
15 [MODULE_STATE_LIVE] = "[MODULE_STATE_LIVE] Normal state",
16 [MODULE_STATE_COMING] = "[MODULE_STATE_COMING] Full formed, running module_init",
17 [MODULE_STATE_GOING] = "[MODULE_STATE_GOING] Going away",
18 [MODULE_STATE_UNFORMED] = "[MODULE_STATE_UNFORMED] Still setting it up",
19};
20
21static void callback_info(const char *callback, struct klp_object *obj)
22{
23 if (obj->mod)
24 pr_info("%s: %s -> %s\n", callback, obj->mod->name,
25 module_state[obj->mod->state]);
26 else
27 pr_info("%s: vmlinux\n", callback);
28}
29
30/* Executed on object patching (ie, patch enablement) */
31static int pre_patch_callback(struct klp_object *obj)
32{
33 callback_info(__func__, obj);
34 return 0;
35}
36
37/* Executed on object unpatching (ie, patch disablement) */
38static void post_patch_callback(struct klp_object *obj)
39{
40 callback_info(__func__, obj);
41}
42
43/* Executed on object unpatching (ie, patch disablement) */
44static void pre_unpatch_callback(struct klp_object *obj)
45{
46 callback_info(__func__, obj);
47}
48
49/* Executed on object unpatching (ie, patch disablement) */
50static void post_unpatch_callback(struct klp_object *obj)
51{
52 callback_info(__func__, obj);
53}
54
55static struct klp_func no_funcs[] = {
56 { }
57};
58
59static struct klp_object objs[] = {
60 {
61 .name = NULL, /* vmlinux */
62 .funcs = no_funcs,
63 .callbacks = {
64 .pre_patch = pre_patch_callback,
65 .post_patch = post_patch_callback,
66 .pre_unpatch = pre_unpatch_callback,
67 .post_unpatch = post_unpatch_callback,
68 },
69 }, { }
70};
71
72static struct klp_patch patch = {
73 .mod = THIS_MODULE,
74 .objs = objs,
75 /* set .replace in the init function below for demo purposes */
76};
77
78static int test_klp_callbacks_demo2_init(void)
79{
80 patch.replace = replace;
81 return klp_enable_patch(&patch);
82}
83
84static void test_klp_callbacks_demo2_exit(void)
85{
86}
87
88module_init(test_klp_callbacks_demo2_init);
89module_exit(test_klp_callbacks_demo2_exit);
90MODULE_LICENSE("GPL");
91MODULE_INFO(livepatch, "Y");
92MODULE_AUTHOR("Joe Lawrence <joe.lawrence@redhat.com>");
93MODULE_DESCRIPTION("Livepatch test: livepatch demo2");
diff --git a/lib/livepatch/test_klp_callbacks_mod.c b/lib/livepatch/test_klp_callbacks_mod.c
new file mode 100644
index 000000000000..8fbe645b1c2c
--- /dev/null
+++ b/lib/livepatch/test_klp_callbacks_mod.c
@@ -0,0 +1,24 @@
1// SPDX-License-Identifier: GPL-2.0
2// Copyright (C) 2018 Joe Lawrence <joe.lawrence@redhat.com>
3
4#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
5
6#include <linux/module.h>
7#include <linux/kernel.h>
8
9static int test_klp_callbacks_mod_init(void)
10{
11 pr_info("%s\n", __func__);
12 return 0;
13}
14
15static void test_klp_callbacks_mod_exit(void)
16{
17 pr_info("%s\n", __func__);
18}
19
20module_init(test_klp_callbacks_mod_init);
21module_exit(test_klp_callbacks_mod_exit);
22MODULE_LICENSE("GPL");
23MODULE_AUTHOR("Joe Lawrence <joe.lawrence@redhat.com>");
24MODULE_DESCRIPTION("Livepatch test: target module");
diff --git a/lib/livepatch/test_klp_livepatch.c b/lib/livepatch/test_klp_livepatch.c
new file mode 100644
index 000000000000..aff08199de71
--- /dev/null
+++ b/lib/livepatch/test_klp_livepatch.c
@@ -0,0 +1,51 @@
1// SPDX-License-Identifier: GPL-2.0
2// Copyright (C) 2014 Seth Jennings <sjenning@redhat.com>
3
4#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
5
6#include <linux/module.h>
7#include <linux/kernel.h>
8#include <linux/livepatch.h>
9
10#include <linux/seq_file.h>
11static int livepatch_cmdline_proc_show(struct seq_file *m, void *v)
12{
13 seq_printf(m, "%s: %s\n", THIS_MODULE->name,
14 "this has been live patched");
15 return 0;
16}
17
18static struct klp_func funcs[] = {
19 {
20 .old_name = "cmdline_proc_show",
21 .new_func = livepatch_cmdline_proc_show,
22 }, { }
23};
24
25static struct klp_object objs[] = {
26 {
27 /* name being NULL means vmlinux */
28 .funcs = funcs,
29 }, { }
30};
31
32static struct klp_patch patch = {
33 .mod = THIS_MODULE,
34 .objs = objs,
35};
36
37static int test_klp_livepatch_init(void)
38{
39 return klp_enable_patch(&patch);
40}
41
42static void test_klp_livepatch_exit(void)
43{
44}
45
46module_init(test_klp_livepatch_init);
47module_exit(test_klp_livepatch_exit);
48MODULE_LICENSE("GPL");
49MODULE_INFO(livepatch, "Y");
50MODULE_AUTHOR("Seth Jennings <sjenning@redhat.com>");
51MODULE_DESCRIPTION("Livepatch test: livepatch module");
diff --git a/lib/livepatch/test_klp_shadow_vars.c b/lib/livepatch/test_klp_shadow_vars.c
new file mode 100644
index 000000000000..fe5c413efe96
--- /dev/null
+++ b/lib/livepatch/test_klp_shadow_vars.c
@@ -0,0 +1,258 @@
1// SPDX-License-Identifier: GPL-2.0
2// Copyright (C) 2018 Joe Lawrence <joe.lawrence@redhat.com>
3
4#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
5
6#include <linux/module.h>
7#include <linux/kernel.h>
8#include <linux/list.h>
9#include <linux/livepatch.h>
10#include <linux/slab.h>
11
12/*
13 * Keep a small list of pointers so that we can print address-agnostic
14 * pointer values. Use a rolling integer count to differentiate the values.
15 * Ironically we could have used the shadow variable API to do this, but
16 * let's not lean too heavily on the very code we're testing.
17 */
18static LIST_HEAD(ptr_list);
19struct shadow_ptr {
20 void *ptr;
21 int id;
22 struct list_head list;
23};
24
25static void free_ptr_list(void)
26{
27 struct shadow_ptr *sp, *tmp_sp;
28
29 list_for_each_entry_safe(sp, tmp_sp, &ptr_list, list) {
30 list_del(&sp->list);
31 kfree(sp);
32 }
33}
34
35static int ptr_id(void *ptr)
36{
37 struct shadow_ptr *sp;
38 static int count;
39
40 list_for_each_entry(sp, &ptr_list, list) {
41 if (sp->ptr == ptr)
42 return sp->id;
43 }
44
45 sp = kmalloc(sizeof(*sp), GFP_ATOMIC);
46 if (!sp)
47 return -ENOMEM;
48 sp->ptr = ptr;
49 sp->id = count++;
50
51 list_add(&sp->list, &ptr_list);
52
53 return sp->id;
54}
55
56/*
57 * Shadow variable wrapper functions that echo the function and arguments
58 * to the kernel log for testing verification. Don't display raw pointers,
59 * but use the ptr_id() value instead.
60 */
61static void *shadow_get(void *obj, unsigned long id)
62{
63 void *ret = klp_shadow_get(obj, id);
64
65 pr_info("klp_%s(obj=PTR%d, id=0x%lx) = PTR%d\n",
66 __func__, ptr_id(obj), id, ptr_id(ret));
67
68 return ret;
69}
70
71static void *shadow_alloc(void *obj, unsigned long id, size_t size,
72 gfp_t gfp_flags, klp_shadow_ctor_t ctor,
73 void *ctor_data)
74{
75 void *ret = klp_shadow_alloc(obj, id, size, gfp_flags, ctor,
76 ctor_data);
77 pr_info("klp_%s(obj=PTR%d, id=0x%lx, size=%zx, gfp_flags=%pGg), ctor=PTR%d, ctor_data=PTR%d = PTR%d\n",
78 __func__, ptr_id(obj), id, size, &gfp_flags, ptr_id(ctor),
79 ptr_id(ctor_data), ptr_id(ret));
80 return ret;
81}
82
83static void *shadow_get_or_alloc(void *obj, unsigned long id, size_t size,
84 gfp_t gfp_flags, klp_shadow_ctor_t ctor,
85 void *ctor_data)
86{
87 void *ret = klp_shadow_get_or_alloc(obj, id, size, gfp_flags, ctor,
88 ctor_data);
89 pr_info("klp_%s(obj=PTR%d, id=0x%lx, size=%zx, gfp_flags=%pGg), ctor=PTR%d, ctor_data=PTR%d = PTR%d\n",
90 __func__, ptr_id(obj), id, size, &gfp_flags, ptr_id(ctor),
91 ptr_id(ctor_data), ptr_id(ret));
92 return ret;
93}
94
95static void shadow_free(void *obj, unsigned long id, klp_shadow_dtor_t dtor)
96{
97 klp_shadow_free(obj, id, dtor);
98 pr_info("klp_%s(obj=PTR%d, id=0x%lx, dtor=PTR%d)\n",
99 __func__, ptr_id(obj), id, ptr_id(dtor));
100}
101
102static void shadow_free_all(unsigned long id, klp_shadow_dtor_t dtor)
103{
104 klp_shadow_free_all(id, dtor);
105 pr_info("klp_%s(id=0x%lx, dtor=PTR%d)\n",
106 __func__, id, ptr_id(dtor));
107}
108
109
110/* Shadow variable constructor - remember simple pointer data */
111static int shadow_ctor(void *obj, void *shadow_data, void *ctor_data)
112{
113 int **shadow_int = shadow_data;
114 *shadow_int = ctor_data;
115 pr_info("%s: PTR%d -> PTR%d\n",
116 __func__, ptr_id(shadow_int), ptr_id(ctor_data));
117
118 return 0;
119}
120
121static void shadow_dtor(void *obj, void *shadow_data)
122{
123 pr_info("%s(obj=PTR%d, shadow_data=PTR%d)\n",
124 __func__, ptr_id(obj), ptr_id(shadow_data));
125}
126
127static int test_klp_shadow_vars_init(void)
128{
129 void *obj = THIS_MODULE;
130 int id = 0x1234;
131 size_t size = sizeof(int *);
132 gfp_t gfp_flags = GFP_KERNEL;
133
134 int var1, var2, var3, var4;
135 int **sv1, **sv2, **sv3, **sv4;
136
137 void *ret;
138
139 ptr_id(NULL);
140 ptr_id(&var1);
141 ptr_id(&var2);
142 ptr_id(&var3);
143 ptr_id(&var4);
144
145 /*
146 * With an empty shadow variable hash table, expect not to find
147 * any matches.
148 */
149 ret = shadow_get(obj, id);
150 if (!ret)
151 pr_info(" got expected NULL result\n");
152
153 /*
154 * Allocate a few shadow variables with different <obj> and <id>.
155 */
156 sv1 = shadow_alloc(obj, id, size, gfp_flags, shadow_ctor, &var1);
157 if (!sv1)
158 return -ENOMEM;
159
160 sv2 = shadow_alloc(obj + 1, id, size, gfp_flags, shadow_ctor, &var2);
161 if (!sv2)
162 return -ENOMEM;
163
164 sv3 = shadow_alloc(obj, id + 1, size, gfp_flags, shadow_ctor, &var3);
165 if (!sv3)
166 return -ENOMEM;
167
168 /*
169 * Verify we can find our new shadow variables and that they point
170 * to expected data.
171 */
172 ret = shadow_get(obj, id);
173 if (!ret)
174 return -EINVAL;
175 if (ret == sv1 && *sv1 == &var1)
176 pr_info(" got expected PTR%d -> PTR%d result\n",
177 ptr_id(sv1), ptr_id(*sv1));
178
179 ret = shadow_get(obj + 1, id);
180 if (!ret)
181 return -EINVAL;
182 if (ret == sv2 && *sv2 == &var2)
183 pr_info(" got expected PTR%d -> PTR%d result\n",
184 ptr_id(sv2), ptr_id(*sv2));
185 ret = shadow_get(obj, id + 1);
186 if (!ret)
187 return -EINVAL;
188 if (ret == sv3 && *sv3 == &var3)
189 pr_info(" got expected PTR%d -> PTR%d result\n",
190 ptr_id(sv3), ptr_id(*sv3));
191
192 /*
193 * Allocate or get a few more, this time with the same <obj>, <id>.
194 * The second invocation should return the same shadow var.
195 */
196 sv4 = shadow_get_or_alloc(obj + 2, id, size, gfp_flags, shadow_ctor, &var4);
197 if (!sv4)
198 return -ENOMEM;
199
200 ret = shadow_get_or_alloc(obj + 2, id, size, gfp_flags, shadow_ctor, &var4);
201 if (!ret)
202 return -EINVAL;
203 if (ret == sv4 && *sv4 == &var4)
204 pr_info(" got expected PTR%d -> PTR%d result\n",
205 ptr_id(sv4), ptr_id(*sv4));
206
207 /*
208 * Free the <obj=*, id> shadow variables and check that we can no
209 * longer find them.
210 */
211 shadow_free(obj, id, shadow_dtor); /* sv1 */
212 ret = shadow_get(obj, id);
213 if (!ret)
214 pr_info(" got expected NULL result\n");
215
216 shadow_free(obj + 1, id, shadow_dtor); /* sv2 */
217 ret = shadow_get(obj + 1, id);
218 if (!ret)
219 pr_info(" got expected NULL result\n");
220
221 shadow_free(obj + 2, id, shadow_dtor); /* sv4 */
222 ret = shadow_get(obj + 2, id);
223 if (!ret)
224 pr_info(" got expected NULL result\n");
225
226 /*
227 * We should still find an <id+1> variable.
228 */
229 ret = shadow_get(obj, id + 1);
230 if (!ret)
231 return -EINVAL;
232 if (ret == sv3 && *sv3 == &var3)
233 pr_info(" got expected PTR%d -> PTR%d result\n",
234 ptr_id(sv3), ptr_id(*sv3));
235
236 /*
237 * Free all the <id+1> variables, too.
238 */
239 shadow_free_all(id + 1, shadow_dtor); /* sv3 */
240 ret = shadow_get(obj, id);
241 if (!ret)
242 pr_info(" shadow_get() got expected NULL result\n");
243
244
245 free_ptr_list();
246
247 return 0;
248}
249
250static void test_klp_shadow_vars_exit(void)
251{
252}
253
254module_init(test_klp_shadow_vars_init);
255module_exit(test_klp_shadow_vars_exit);
256MODULE_LICENSE("GPL");
257MODULE_AUTHOR("Joe Lawrence <joe.lawrence@redhat.com>");
258MODULE_DESCRIPTION("Livepatch test: shadow variables");
diff --git a/lib/locking-selftest.c b/lib/locking-selftest.c
index 1e1bbf171eca..a1705545e6ac 100644
--- a/lib/locking-selftest.c
+++ b/lib/locking-selftest.c
@@ -1989,6 +1989,7 @@ void locking_selftest(void)
1989 1989
1990 init_shared_classes(); 1990 init_shared_classes();
1991 debug_locks_silent = !debug_locks_verbose; 1991 debug_locks_silent = !debug_locks_verbose;
1992 lockdep_set_selftest_task(current);
1992 1993
1993 DO_TESTCASE_6R("A-A deadlock", AA); 1994 DO_TESTCASE_6R("A-A deadlock", AA);
1994 DO_TESTCASE_6R("A-B-B-A deadlock", ABBA); 1995 DO_TESTCASE_6R("A-B-B-A deadlock", ABBA);
@@ -2097,5 +2098,6 @@ void locking_selftest(void)
2097 printk("---------------------------------\n"); 2098 printk("---------------------------------\n");
2098 debug_locks = 1; 2099 debug_locks = 1;
2099 } 2100 }
2101 lockdep_set_selftest_task(NULL);
2100 debug_locks_silent = 0; 2102 debug_locks_silent = 0;
2101} 2103}
diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index 236eb21167b5..4525fb094844 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -20,7 +20,8 @@
20static noinline size_t 20static noinline size_t
21lzo1x_1_do_compress(const unsigned char *in, size_t in_len, 21lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
22 unsigned char *out, size_t *out_len, 22 unsigned char *out, size_t *out_len,
23 size_t ti, void *wrkmem) 23 size_t ti, void *wrkmem, signed char *state_offset,
24 const unsigned char bitstream_version)
24{ 25{
25 const unsigned char *ip; 26 const unsigned char *ip;
26 unsigned char *op; 27 unsigned char *op;
@@ -35,27 +36,85 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
35 ip += ti < 4 ? 4 - ti : 0; 36 ip += ti < 4 ? 4 - ti : 0;
36 37
37 for (;;) { 38 for (;;) {
38 const unsigned char *m_pos; 39 const unsigned char *m_pos = NULL;
39 size_t t, m_len, m_off; 40 size_t t, m_len, m_off;
40 u32 dv; 41 u32 dv;
42 u32 run_length = 0;
41literal: 43literal:
42 ip += 1 + ((ip - ii) >> 5); 44 ip += 1 + ((ip - ii) >> 5);
43next: 45next:
44 if (unlikely(ip >= ip_end)) 46 if (unlikely(ip >= ip_end))
45 break; 47 break;
46 dv = get_unaligned_le32(ip); 48 dv = get_unaligned_le32(ip);
47 t = ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK; 49
48 m_pos = in + dict[t]; 50 if (dv == 0 && bitstream_version) {
49 dict[t] = (lzo_dict_t) (ip - in); 51 const unsigned char *ir = ip + 4;
50 if (unlikely(dv != get_unaligned_le32(m_pos))) 52 const unsigned char *limit = ip_end
51 goto literal; 53 < (ip + MAX_ZERO_RUN_LENGTH + 1)
54 ? ip_end : ip + MAX_ZERO_RUN_LENGTH + 1;
55#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && \
56 defined(LZO_FAST_64BIT_MEMORY_ACCESS)
57 u64 dv64;
58
59 for (; (ir + 32) <= limit; ir += 32) {
60 dv64 = get_unaligned((u64 *)ir);
61 dv64 |= get_unaligned((u64 *)ir + 1);
62 dv64 |= get_unaligned((u64 *)ir + 2);
63 dv64 |= get_unaligned((u64 *)ir + 3);
64 if (dv64)
65 break;
66 }
67 for (; (ir + 8) <= limit; ir += 8) {
68 dv64 = get_unaligned((u64 *)ir);
69 if (dv64) {
70# if defined(__LITTLE_ENDIAN)
71 ir += __builtin_ctzll(dv64) >> 3;
72# elif defined(__BIG_ENDIAN)
73 ir += __builtin_clzll(dv64) >> 3;
74# else
75# error "missing endian definition"
76# endif
77 break;
78 }
79 }
80#else
81 while ((ir < (const unsigned char *)
82 ALIGN((uintptr_t)ir, 4)) &&
83 (ir < limit) && (*ir == 0))
84 ir++;
85 for (; (ir + 4) <= limit; ir += 4) {
86 dv = *((u32 *)ir);
87 if (dv) {
88# if defined(__LITTLE_ENDIAN)
89 ir += __builtin_ctz(dv) >> 3;
90# elif defined(__BIG_ENDIAN)
91 ir += __builtin_clz(dv) >> 3;
92# else
93# error "missing endian definition"
94# endif
95 break;
96 }
97 }
98#endif
99 while (likely(ir < limit) && unlikely(*ir == 0))
100 ir++;
101 run_length = ir - ip;
102 if (run_length > MAX_ZERO_RUN_LENGTH)
103 run_length = MAX_ZERO_RUN_LENGTH;
104 } else {
105 t = ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK;
106 m_pos = in + dict[t];
107 dict[t] = (lzo_dict_t) (ip - in);
108 if (unlikely(dv != get_unaligned_le32(m_pos)))
109 goto literal;
110 }
52 111
53 ii -= ti; 112 ii -= ti;
54 ti = 0; 113 ti = 0;
55 t = ip - ii; 114 t = ip - ii;
56 if (t != 0) { 115 if (t != 0) {
57 if (t <= 3) { 116 if (t <= 3) {
58 op[-2] |= t; 117 op[*state_offset] |= t;
59 COPY4(op, ii); 118 COPY4(op, ii);
60 op += t; 119 op += t;
61 } else if (t <= 16) { 120 } else if (t <= 16) {
@@ -88,6 +147,17 @@ next:
88 } 147 }
89 } 148 }
90 149
150 if (unlikely(run_length)) {
151 ip += run_length;
152 run_length -= MIN_ZERO_RUN_LENGTH;
153 put_unaligned_le32((run_length << 21) | 0xfffc18
154 | (run_length & 0x7), op);
155 op += 4;
156 run_length = 0;
157 *state_offset = -3;
158 goto finished_writing_instruction;
159 }
160
91 m_len = 4; 161 m_len = 4;
92 { 162 {
93#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ64) 163#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ64)
@@ -170,7 +240,6 @@ m_len_done:
170 240
171 m_off = ip - m_pos; 241 m_off = ip - m_pos;
172 ip += m_len; 242 ip += m_len;
173 ii = ip;
174 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) { 243 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
175 m_off -= 1; 244 m_off -= 1;
176 *op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2)); 245 *op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2));
@@ -207,29 +276,45 @@ m_len_done:
207 *op++ = (m_off << 2); 276 *op++ = (m_off << 2);
208 *op++ = (m_off >> 6); 277 *op++ = (m_off >> 6);
209 } 278 }
279 *state_offset = -2;
280finished_writing_instruction:
281 ii = ip;
210 goto next; 282 goto next;
211 } 283 }
212 *out_len = op - out; 284 *out_len = op - out;
213 return in_end - (ii - ti); 285 return in_end - (ii - ti);
214} 286}
215 287
216int lzo1x_1_compress(const unsigned char *in, size_t in_len, 288int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
217 unsigned char *out, size_t *out_len, 289 unsigned char *out, size_t *out_len,
218 void *wrkmem) 290 void *wrkmem, const unsigned char bitstream_version)
219{ 291{
220 const unsigned char *ip = in; 292 const unsigned char *ip = in;
221 unsigned char *op = out; 293 unsigned char *op = out;
222 size_t l = in_len; 294 size_t l = in_len;
223 size_t t = 0; 295 size_t t = 0;
296 signed char state_offset = -2;
297 unsigned int m4_max_offset;
298
299 // LZO v0 will never write 17 as first byte,
300 // so this is used to version the bitstream
301 if (bitstream_version > 0) {
302 *op++ = 17;
303 *op++ = bitstream_version;
304 m4_max_offset = M4_MAX_OFFSET_V1;
305 } else {
306 m4_max_offset = M4_MAX_OFFSET_V0;
307 }
224 308
225 while (l > 20) { 309 while (l > 20) {
226 size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1); 310 size_t ll = l <= (m4_max_offset + 1) ? l : (m4_max_offset + 1);
227 uintptr_t ll_end = (uintptr_t) ip + ll; 311 uintptr_t ll_end = (uintptr_t) ip + ll;
228 if ((ll_end + ((t + ll) >> 5)) <= ll_end) 312 if ((ll_end + ((t + ll) >> 5)) <= ll_end)
229 break; 313 break;
230 BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS); 314 BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
231 memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t)); 315 memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
232 t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem); 316 t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem,
317 &state_offset, bitstream_version);
233 ip += ll; 318 ip += ll;
234 op += *out_len; 319 op += *out_len;
235 l -= ll; 320 l -= ll;
@@ -242,7 +327,7 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
242 if (op == out && t <= 238) { 327 if (op == out && t <= 238) {
243 *op++ = (17 + t); 328 *op++ = (17 + t);
244 } else if (t <= 3) { 329 } else if (t <= 3) {
245 op[-2] |= t; 330 op[state_offset] |= t;
246 } else if (t <= 18) { 331 } else if (t <= 18) {
247 *op++ = (t - 3); 332 *op++ = (t - 3);
248 } else { 333 } else {
@@ -273,7 +358,24 @@ int lzo1x_1_compress(const unsigned char *in, size_t in_len,
273 *out_len = op - out; 358 *out_len = op - out;
274 return LZO_E_OK; 359 return LZO_E_OK;
275} 360}
361
362int lzo1x_1_compress(const unsigned char *in, size_t in_len,
363 unsigned char *out, size_t *out_len,
364 void *wrkmem)
365{
366 return lzogeneric1x_1_compress(in, in_len, out, out_len, wrkmem, 0);
367}
368
369int lzorle1x_1_compress(const unsigned char *in, size_t in_len,
370 unsigned char *out, size_t *out_len,
371 void *wrkmem)
372{
373 return lzogeneric1x_1_compress(in, in_len, out, out_len,
374 wrkmem, LZO_VERSION);
375}
376
276EXPORT_SYMBOL_GPL(lzo1x_1_compress); 377EXPORT_SYMBOL_GPL(lzo1x_1_compress);
378EXPORT_SYMBOL_GPL(lzorle1x_1_compress);
277 379
278MODULE_LICENSE("GPL"); 380MODULE_LICENSE("GPL");
279MODULE_DESCRIPTION("LZO1X-1 Compressor"); 381MODULE_DESCRIPTION("LZO1X-1 Compressor");
diff --git a/lib/lzo/lzo1x_decompress_safe.c b/lib/lzo/lzo1x_decompress_safe.c
index a1c387f6afba..6d2600ea3b55 100644
--- a/lib/lzo/lzo1x_decompress_safe.c
+++ b/lib/lzo/lzo1x_decompress_safe.c
@@ -46,11 +46,23 @@ int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
46 const unsigned char * const ip_end = in + in_len; 46 const unsigned char * const ip_end = in + in_len;
47 unsigned char * const op_end = out + *out_len; 47 unsigned char * const op_end = out + *out_len;
48 48
49 unsigned char bitstream_version;
50
49 op = out; 51 op = out;
50 ip = in; 52 ip = in;
51 53
52 if (unlikely(in_len < 3)) 54 if (unlikely(in_len < 3))
53 goto input_overrun; 55 goto input_overrun;
56
57 if (likely(*ip == 17)) {
58 bitstream_version = ip[1];
59 ip += 2;
60 if (unlikely(in_len < 5))
61 goto input_overrun;
62 } else {
63 bitstream_version = 0;
64 }
65
54 if (*ip > 17) { 66 if (*ip > 17) {
55 t = *ip++ - 17; 67 t = *ip++ - 17;
56 if (t < 4) { 68 if (t < 4) {
@@ -154,32 +166,49 @@ copy_literal_run:
154 m_pos -= next >> 2; 166 m_pos -= next >> 2;
155 next &= 3; 167 next &= 3;
156 } else { 168 } else {
157 m_pos = op; 169 NEED_IP(2);
158 m_pos -= (t & 8) << 11; 170 next = get_unaligned_le16(ip);
159 t = (t & 7) + (3 - 1); 171 if (((next & 0xfffc) == 0xfffc) &&
160 if (unlikely(t == 2)) { 172 ((t & 0xf8) == 0x18) &&
161 size_t offset; 173 likely(bitstream_version)) {
162 const unsigned char *ip_last = ip; 174 NEED_IP(3);
175 t &= 7;
176 t |= ip[2] << 3;
177 t += MIN_ZERO_RUN_LENGTH;
178 NEED_OP(t);
179 memset(op, 0, t);
180 op += t;
181 next &= 3;
182 ip += 3;
183 goto match_next;
184 } else {
185 m_pos = op;
186 m_pos -= (t & 8) << 11;
187 t = (t & 7) + (3 - 1);
188 if (unlikely(t == 2)) {
189 size_t offset;
190 const unsigned char *ip_last = ip;
163 191
164 while (unlikely(*ip == 0)) { 192 while (unlikely(*ip == 0)) {
165 ip++; 193 ip++;
166 NEED_IP(1); 194 NEED_IP(1);
167 } 195 }
168 offset = ip - ip_last; 196 offset = ip - ip_last;
169 if (unlikely(offset > MAX_255_COUNT)) 197 if (unlikely(offset > MAX_255_COUNT))
170 return LZO_E_ERROR; 198 return LZO_E_ERROR;
171 199
172 offset = (offset << 8) - offset; 200 offset = (offset << 8) - offset;
173 t += offset + 7 + *ip++; 201 t += offset + 7 + *ip++;
174 NEED_IP(2); 202 NEED_IP(2);
203 next = get_unaligned_le16(ip);
204 }
205 ip += 2;
206 m_pos -= next >> 2;
207 next &= 3;
208 if (m_pos == op)
209 goto eof_found;
210 m_pos -= 0x4000;
175 } 211 }
176 next = get_unaligned_le16(ip);
177 ip += 2;
178 m_pos -= next >> 2;
179 next &= 3;
180 if (m_pos == op)
181 goto eof_found;
182 m_pos -= 0x4000;
183 } 212 }
184 TEST_LB(m_pos); 213 TEST_LB(m_pos);
185#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 214#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
diff --git a/lib/lzo/lzodefs.h b/lib/lzo/lzodefs.h
index 4edefd2f540c..b60851fcf6ce 100644
--- a/lib/lzo/lzodefs.h
+++ b/lib/lzo/lzodefs.h
@@ -13,9 +13,15 @@
13 */ 13 */
14 14
15 15
16/* Version
17 * 0: original lzo version
18 * 1: lzo with support for RLE
19 */
20#define LZO_VERSION 1
21
16#define COPY4(dst, src) \ 22#define COPY4(dst, src) \
17 put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst)) 23 put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
18#if defined(__x86_64__) 24#if defined(CONFIG_X86_64) || defined(CONFIG_ARM64)
19#define COPY8(dst, src) \ 25#define COPY8(dst, src) \
20 put_unaligned(get_unaligned((const u64 *)(src)), (u64 *)(dst)) 26 put_unaligned(get_unaligned((const u64 *)(src)), (u64 *)(dst))
21#else 27#else
@@ -25,19 +31,21 @@
25 31
26#if defined(__BIG_ENDIAN) && defined(__LITTLE_ENDIAN) 32#if defined(__BIG_ENDIAN) && defined(__LITTLE_ENDIAN)
27#error "conflicting endian definitions" 33#error "conflicting endian definitions"
28#elif defined(__x86_64__) 34#elif defined(CONFIG_X86_64) || defined(CONFIG_ARM64)
29#define LZO_USE_CTZ64 1 35#define LZO_USE_CTZ64 1
30#define LZO_USE_CTZ32 1 36#define LZO_USE_CTZ32 1
31#elif defined(__i386__) || defined(__powerpc__) 37#define LZO_FAST_64BIT_MEMORY_ACCESS
38#elif defined(CONFIG_X86) || defined(CONFIG_PPC)
32#define LZO_USE_CTZ32 1 39#define LZO_USE_CTZ32 1
33#elif defined(__arm__) && (__LINUX_ARM_ARCH__ >= 5) 40#elif defined(CONFIG_ARM) && (__LINUX_ARM_ARCH__ >= 5)
34#define LZO_USE_CTZ32 1 41#define LZO_USE_CTZ32 1
35#endif 42#endif
36 43
37#define M1_MAX_OFFSET 0x0400 44#define M1_MAX_OFFSET 0x0400
38#define M2_MAX_OFFSET 0x0800 45#define M2_MAX_OFFSET 0x0800
39#define M3_MAX_OFFSET 0x4000 46#define M3_MAX_OFFSET 0x4000
40#define M4_MAX_OFFSET 0xbfff 47#define M4_MAX_OFFSET_V0 0xbfff
48#define M4_MAX_OFFSET_V1 0xbffe
41 49
42#define M1_MIN_LEN 2 50#define M1_MIN_LEN 2
43#define M1_MAX_LEN 2 51#define M1_MAX_LEN 2
@@ -53,6 +61,9 @@
53#define M3_MARKER 32 61#define M3_MARKER 32
54#define M4_MARKER 16 62#define M4_MARKER 16
55 63
64#define MIN_ZERO_RUN_LENGTH 4
65#define MAX_ZERO_RUN_LENGTH (2047 + MIN_ZERO_RUN_LENGTH)
66
56#define lzo_dict_t unsigned short 67#define lzo_dict_t unsigned short
57#define D_BITS 13 68#define D_BITS 13
58#define D_SIZE (1u << D_BITS) 69#define D_SIZE (1u << D_BITS)
diff --git a/lib/objagg.c b/lib/objagg.c
index c9b457a91153..576be22e86de 100644
--- a/lib/objagg.c
+++ b/lib/objagg.c
@@ -4,6 +4,7 @@
4#include <linux/module.h> 4#include <linux/module.h>
5#include <linux/slab.h> 5#include <linux/slab.h>
6#include <linux/rhashtable.h> 6#include <linux/rhashtable.h>
7#include <linux/idr.h>
7#include <linux/list.h> 8#include <linux/list.h>
8#include <linux/sort.h> 9#include <linux/sort.h>
9#include <linux/objagg.h> 10#include <linux/objagg.h>
@@ -11,6 +12,34 @@
11#define CREATE_TRACE_POINTS 12#define CREATE_TRACE_POINTS
12#include <trace/events/objagg.h> 13#include <trace/events/objagg.h>
13 14
15struct objagg_hints {
16 struct rhashtable node_ht;
17 struct rhashtable_params ht_params;
18 struct list_head node_list;
19 unsigned int node_count;
20 unsigned int root_count;
21 unsigned int refcount;
22 const struct objagg_ops *ops;
23};
24
25struct objagg_hints_node {
26 struct rhash_head ht_node; /* member of objagg_hints->node_ht */
27 struct list_head list; /* member of objagg_hints->node_list */
28 struct objagg_hints_node *parent;
29 unsigned int root_id;
30 struct objagg_obj_stats_info stats_info;
31 unsigned long obj[0];
32};
33
34static struct objagg_hints_node *
35objagg_hints_lookup(struct objagg_hints *objagg_hints, void *obj)
36{
37 if (!objagg_hints)
38 return NULL;
39 return rhashtable_lookup_fast(&objagg_hints->node_ht, obj,
40 objagg_hints->ht_params);
41}
42
14struct objagg { 43struct objagg {
15 const struct objagg_ops *ops; 44 const struct objagg_ops *ops;
16 void *priv; 45 void *priv;
@@ -18,6 +47,8 @@ struct objagg {
18 struct rhashtable_params ht_params; 47 struct rhashtable_params ht_params;
19 struct list_head obj_list; 48 struct list_head obj_list;
20 unsigned int obj_count; 49 unsigned int obj_count;
50 struct ida root_ida;
51 struct objagg_hints *hints;
21}; 52};
22 53
23struct objagg_obj { 54struct objagg_obj {
@@ -30,6 +61,7 @@ struct objagg_obj {
30 void *delta_priv; /* user delta private */ 61 void *delta_priv; /* user delta private */
31 void *root_priv; /* user root private */ 62 void *root_priv; /* user root private */
32 }; 63 };
64 unsigned int root_id;
33 unsigned int refcount; /* counts number of users of this object 65 unsigned int refcount; /* counts number of users of this object
34 * including nested objects 66 * including nested objects
35 */ 67 */
@@ -130,7 +162,8 @@ static struct objagg_obj *objagg_obj_lookup(struct objagg *objagg, void *obj)
130 162
131static int objagg_obj_parent_assign(struct objagg *objagg, 163static int objagg_obj_parent_assign(struct objagg *objagg,
132 struct objagg_obj *objagg_obj, 164 struct objagg_obj *objagg_obj,
133 struct objagg_obj *parent) 165 struct objagg_obj *parent,
166 bool take_parent_ref)
134{ 167{
135 void *delta_priv; 168 void *delta_priv;
136 169
@@ -144,7 +177,8 @@ static int objagg_obj_parent_assign(struct objagg *objagg,
144 */ 177 */
145 objagg_obj->parent = parent; 178 objagg_obj->parent = parent;
146 objagg_obj->delta_priv = delta_priv; 179 objagg_obj->delta_priv = delta_priv;
147 objagg_obj_ref_inc(objagg_obj->parent); 180 if (take_parent_ref)
181 objagg_obj_ref_inc(objagg_obj->parent);
148 trace_objagg_obj_parent_assign(objagg, objagg_obj, 182 trace_objagg_obj_parent_assign(objagg, objagg_obj,
149 parent, 183 parent,
150 parent->refcount); 184 parent->refcount);
@@ -164,7 +198,7 @@ static int objagg_obj_parent_lookup_assign(struct objagg *objagg,
164 if (!objagg_obj_is_root(objagg_obj_cur)) 198 if (!objagg_obj_is_root(objagg_obj_cur))
165 continue; 199 continue;
166 err = objagg_obj_parent_assign(objagg, objagg_obj, 200 err = objagg_obj_parent_assign(objagg, objagg_obj,
167 objagg_obj_cur); 201 objagg_obj_cur, true);
168 if (!err) 202 if (!err)
169 return 0; 203 return 0;
170 } 204 }
@@ -184,16 +218,68 @@ static void objagg_obj_parent_unassign(struct objagg *objagg,
184 __objagg_obj_put(objagg, objagg_obj->parent); 218 __objagg_obj_put(objagg, objagg_obj->parent);
185} 219}
186 220
221static int objagg_obj_root_id_alloc(struct objagg *objagg,
222 struct objagg_obj *objagg_obj,
223 struct objagg_hints_node *hnode)
224{
225 unsigned int min, max;
226 int root_id;
227
228 /* In case there are no hints available, the root id is invalid. */
229 if (!objagg->hints) {
230 objagg_obj->root_id = OBJAGG_OBJ_ROOT_ID_INVALID;
231 return 0;
232 }
233
234 if (hnode) {
235 min = hnode->root_id;
236 max = hnode->root_id;
237 } else {
238 /* For objects with no hint, start after the last
239 * hinted root_id.
240 */
241 min = objagg->hints->root_count;
242 max = ~0;
243 }
244
245 root_id = ida_alloc_range(&objagg->root_ida, min, max, GFP_KERNEL);
246
247 if (root_id < 0)
248 return root_id;
249 objagg_obj->root_id = root_id;
250 return 0;
251}
252
253static void objagg_obj_root_id_free(struct objagg *objagg,
254 struct objagg_obj *objagg_obj)
255{
256 if (!objagg->hints)
257 return;
258 ida_free(&objagg->root_ida, objagg_obj->root_id);
259}
260
187static int objagg_obj_root_create(struct objagg *objagg, 261static int objagg_obj_root_create(struct objagg *objagg,
188 struct objagg_obj *objagg_obj) 262 struct objagg_obj *objagg_obj,
263 struct objagg_hints_node *hnode)
189{ 264{
190 objagg_obj->root_priv = objagg->ops->root_create(objagg->priv, 265 int err;
191 objagg_obj->obj);
192 if (IS_ERR(objagg_obj->root_priv))
193 return PTR_ERR(objagg_obj->root_priv);
194 266
267 err = objagg_obj_root_id_alloc(objagg, objagg_obj, hnode);
268 if (err)
269 return err;
270 objagg_obj->root_priv = objagg->ops->root_create(objagg->priv,
271 objagg_obj->obj,
272 objagg_obj->root_id);
273 if (IS_ERR(objagg_obj->root_priv)) {
274 err = PTR_ERR(objagg_obj->root_priv);
275 goto err_root_create;
276 }
195 trace_objagg_obj_root_create(objagg, objagg_obj); 277 trace_objagg_obj_root_create(objagg, objagg_obj);
196 return 0; 278 return 0;
279
280err_root_create:
281 objagg_obj_root_id_free(objagg, objagg_obj);
282 return err;
197} 283}
198 284
199static void objagg_obj_root_destroy(struct objagg *objagg, 285static void objagg_obj_root_destroy(struct objagg *objagg,
@@ -201,19 +287,69 @@ static void objagg_obj_root_destroy(struct objagg *objagg,
201{ 287{
202 trace_objagg_obj_root_destroy(objagg, objagg_obj); 288 trace_objagg_obj_root_destroy(objagg, objagg_obj);
203 objagg->ops->root_destroy(objagg->priv, objagg_obj->root_priv); 289 objagg->ops->root_destroy(objagg->priv, objagg_obj->root_priv);
290 objagg_obj_root_id_free(objagg, objagg_obj);
291}
292
293static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj);
294
295static int objagg_obj_init_with_hints(struct objagg *objagg,
296 struct objagg_obj *objagg_obj,
297 bool *hint_found)
298{
299 struct objagg_hints_node *hnode;
300 struct objagg_obj *parent;
301 int err;
302
303 hnode = objagg_hints_lookup(objagg->hints, objagg_obj->obj);
304 if (!hnode) {
305 *hint_found = false;
306 return 0;
307 }
308 *hint_found = true;
309
310 if (!hnode->parent)
311 return objagg_obj_root_create(objagg, objagg_obj, hnode);
312
313 parent = __objagg_obj_get(objagg, hnode->parent->obj);
314 if (IS_ERR(parent))
315 return PTR_ERR(parent);
316
317 err = objagg_obj_parent_assign(objagg, objagg_obj, parent, false);
318 if (err) {
319 *hint_found = false;
320 err = 0;
321 goto err_parent_assign;
322 }
323
324 return 0;
325
326err_parent_assign:
327 objagg_obj_put(objagg, parent);
328 return err;
204} 329}
205 330
206static int objagg_obj_init(struct objagg *objagg, 331static int objagg_obj_init(struct objagg *objagg,
207 struct objagg_obj *objagg_obj) 332 struct objagg_obj *objagg_obj)
208{ 333{
334 bool hint_found;
209 int err; 335 int err;
210 336
337 /* First, try to use hints if they are available and
338 * if they provide result.
339 */
340 err = objagg_obj_init_with_hints(objagg, objagg_obj, &hint_found);
341 if (err)
342 return err;
343
344 if (hint_found)
345 return 0;
346
211 /* Try to find if the object can be aggregated under an existing one. */ 347 /* Try to find if the object can be aggregated under an existing one. */
212 err = objagg_obj_parent_lookup_assign(objagg, objagg_obj); 348 err = objagg_obj_parent_lookup_assign(objagg, objagg_obj);
213 if (!err) 349 if (!err)
214 return 0; 350 return 0;
215 /* If aggregation is not possible, make the object a root. */ 351 /* If aggregation is not possible, make the object a root. */
216 return objagg_obj_root_create(objagg, objagg_obj); 352 return objagg_obj_root_create(objagg, objagg_obj, NULL);
217} 353}
218 354
219static void objagg_obj_fini(struct objagg *objagg, 355static void objagg_obj_fini(struct objagg *objagg,
@@ -349,8 +485,9 @@ EXPORT_SYMBOL(objagg_obj_put);
349 485
350/** 486/**
351 * objagg_create - creates a new objagg instance 487 * objagg_create - creates a new objagg instance
352 * @ops: user-specific callbacks 488 * @ops: user-specific callbacks
353 * @priv: pointer to a private data passed to the ops 489 * @objagg_hints: hints, can be NULL
490 * @priv: pointer to a private data passed to the ops
354 * 491 *
355 * Note: all locking must be provided by the caller. 492 * Note: all locking must be provided by the caller.
356 * 493 *
@@ -374,18 +511,25 @@ EXPORT_SYMBOL(objagg_obj_put);
374 * Returns a pointer to newly created objagg instance in case of success, 511 * Returns a pointer to newly created objagg instance in case of success,
375 * otherwise it returns pointer error using ERR_PTR macro. 512 * otherwise it returns pointer error using ERR_PTR macro.
376 */ 513 */
377struct objagg *objagg_create(const struct objagg_ops *ops, void *priv) 514struct objagg *objagg_create(const struct objagg_ops *ops,
515 struct objagg_hints *objagg_hints, void *priv)
378{ 516{
379 struct objagg *objagg; 517 struct objagg *objagg;
380 int err; 518 int err;
381 519
382 if (WARN_ON(!ops || !ops->root_create || !ops->root_destroy || 520 if (WARN_ON(!ops || !ops->root_create || !ops->root_destroy ||
383 !ops->delta_create || !ops->delta_destroy)) 521 !ops->delta_check || !ops->delta_create ||
522 !ops->delta_destroy))
384 return ERR_PTR(-EINVAL); 523 return ERR_PTR(-EINVAL);
524
385 objagg = kzalloc(sizeof(*objagg), GFP_KERNEL); 525 objagg = kzalloc(sizeof(*objagg), GFP_KERNEL);
386 if (!objagg) 526 if (!objagg)
387 return ERR_PTR(-ENOMEM); 527 return ERR_PTR(-ENOMEM);
388 objagg->ops = ops; 528 objagg->ops = ops;
529 if (objagg_hints) {
530 objagg->hints = objagg_hints;
531 objagg_hints->refcount++;
532 }
389 objagg->priv = priv; 533 objagg->priv = priv;
390 INIT_LIST_HEAD(&objagg->obj_list); 534 INIT_LIST_HEAD(&objagg->obj_list);
391 535
@@ -397,6 +541,8 @@ struct objagg *objagg_create(const struct objagg_ops *ops, void *priv)
397 if (err) 541 if (err)
398 goto err_rhashtable_init; 542 goto err_rhashtable_init;
399 543
544 ida_init(&objagg->root_ida);
545
400 trace_objagg_create(objagg); 546 trace_objagg_create(objagg);
401 return objagg; 547 return objagg;
402 548
@@ -415,8 +561,11 @@ EXPORT_SYMBOL(objagg_create);
415void objagg_destroy(struct objagg *objagg) 561void objagg_destroy(struct objagg *objagg)
416{ 562{
417 trace_objagg_destroy(objagg); 563 trace_objagg_destroy(objagg);
564 ida_destroy(&objagg->root_ida);
418 WARN_ON(!list_empty(&objagg->obj_list)); 565 WARN_ON(!list_empty(&objagg->obj_list));
419 rhashtable_destroy(&objagg->obj_ht); 566 rhashtable_destroy(&objagg->obj_ht);
567 if (objagg->hints)
568 objagg_hints_put(objagg->hints);
420 kfree(objagg); 569 kfree(objagg);
421} 570}
422EXPORT_SYMBOL(objagg_destroy); 571EXPORT_SYMBOL(objagg_destroy);
@@ -472,6 +621,8 @@ const struct objagg_stats *objagg_stats_get(struct objagg *objagg)
472 objagg_stats->stats_info[i].objagg_obj = objagg_obj; 621 objagg_stats->stats_info[i].objagg_obj = objagg_obj;
473 objagg_stats->stats_info[i].is_root = 622 objagg_stats->stats_info[i].is_root =
474 objagg_obj_is_root(objagg_obj); 623 objagg_obj_is_root(objagg_obj);
624 if (objagg_stats->stats_info[i].is_root)
625 objagg_stats->root_count++;
475 i++; 626 i++;
476 } 627 }
477 objagg_stats->stats_info_count = i; 628 objagg_stats->stats_info_count = i;
@@ -485,7 +636,7 @@ const struct objagg_stats *objagg_stats_get(struct objagg *objagg)
485EXPORT_SYMBOL(objagg_stats_get); 636EXPORT_SYMBOL(objagg_stats_get);
486 637
487/** 638/**
488 * objagg_stats_puts - puts stats of the objagg instance 639 * objagg_stats_put - puts stats of the objagg instance
489 * @objagg_stats: objagg instance stats 640 * @objagg_stats: objagg instance stats
490 * 641 *
491 * Note: all locking must be provided by the caller. 642 * Note: all locking must be provided by the caller.
@@ -496,6 +647,410 @@ void objagg_stats_put(const struct objagg_stats *objagg_stats)
496} 647}
497EXPORT_SYMBOL(objagg_stats_put); 648EXPORT_SYMBOL(objagg_stats_put);
498 649
650static struct objagg_hints_node *
651objagg_hints_node_create(struct objagg_hints *objagg_hints,
652 struct objagg_obj *objagg_obj, size_t obj_size,
653 struct objagg_hints_node *parent_hnode)
654{
655 unsigned int user_count = objagg_obj->stats.user_count;
656 struct objagg_hints_node *hnode;
657 int err;
658
659 hnode = kzalloc(sizeof(*hnode) + obj_size, GFP_KERNEL);
660 if (!hnode)
661 return ERR_PTR(-ENOMEM);
662 memcpy(hnode->obj, &objagg_obj->obj, obj_size);
663 hnode->stats_info.stats.user_count = user_count;
664 hnode->stats_info.stats.delta_user_count = user_count;
665 if (parent_hnode) {
666 parent_hnode->stats_info.stats.delta_user_count += user_count;
667 } else {
668 hnode->root_id = objagg_hints->root_count++;
669 hnode->stats_info.is_root = true;
670 }
671 hnode->stats_info.objagg_obj = objagg_obj;
672
673 err = rhashtable_insert_fast(&objagg_hints->node_ht, &hnode->ht_node,
674 objagg_hints->ht_params);
675 if (err)
676 goto err_ht_insert;
677
678 list_add(&hnode->list, &objagg_hints->node_list);
679 hnode->parent = parent_hnode;
680 objagg_hints->node_count++;
681
682 return hnode;
683
684err_ht_insert:
685 kfree(hnode);
686 return ERR_PTR(err);
687}
688
689static void objagg_hints_flush(struct objagg_hints *objagg_hints)
690{
691 struct objagg_hints_node *hnode, *tmp;
692
693 list_for_each_entry_safe(hnode, tmp, &objagg_hints->node_list, list) {
694 list_del(&hnode->list);
695 rhashtable_remove_fast(&objagg_hints->node_ht, &hnode->ht_node,
696 objagg_hints->ht_params);
697 kfree(hnode);
698 }
699}
700
701struct objagg_tmp_node {
702 struct objagg_obj *objagg_obj;
703 bool crossed_out;
704};
705
706struct objagg_tmp_graph {
707 struct objagg_tmp_node *nodes;
708 unsigned long nodes_count;
709 unsigned long *edges;
710};
711
712static int objagg_tmp_graph_edge_index(struct objagg_tmp_graph *graph,
713 int parent_index, int index)
714{
715 return index * graph->nodes_count + parent_index;
716}
717
718static void objagg_tmp_graph_edge_set(struct objagg_tmp_graph *graph,
719 int parent_index, int index)
720{
721 int edge_index = objagg_tmp_graph_edge_index(graph, index,
722 parent_index);
723
724 __set_bit(edge_index, graph->edges);
725}
726
727static bool objagg_tmp_graph_is_edge(struct objagg_tmp_graph *graph,
728 int parent_index, int index)
729{
730 int edge_index = objagg_tmp_graph_edge_index(graph, index,
731 parent_index);
732
733 return test_bit(edge_index, graph->edges);
734}
735
736static unsigned int objagg_tmp_graph_node_weight(struct objagg_tmp_graph *graph,
737 unsigned int index)
738{
739 struct objagg_tmp_node *node = &graph->nodes[index];
740 unsigned int weight = node->objagg_obj->stats.user_count;
741 int j;
742
743 /* Node weight is sum of node users and all other nodes users
744 * that this node can represent with delta.
745 */
746
747 for (j = 0; j < graph->nodes_count; j++) {
748 if (!objagg_tmp_graph_is_edge(graph, index, j))
749 continue;
750 node = &graph->nodes[j];
751 if (node->crossed_out)
752 continue;
753 weight += node->objagg_obj->stats.user_count;
754 }
755 return weight;
756}
757
758static int objagg_tmp_graph_node_max_weight(struct objagg_tmp_graph *graph)
759{
760 struct objagg_tmp_node *node;
761 unsigned int max_weight = 0;
762 unsigned int weight;
763 int max_index = -1;
764 int i;
765
766 for (i = 0; i < graph->nodes_count; i++) {
767 node = &graph->nodes[i];
768 if (node->crossed_out)
769 continue;
770 weight = objagg_tmp_graph_node_weight(graph, i);
771 if (weight >= max_weight) {
772 max_weight = weight;
773 max_index = i;
774 }
775 }
776 return max_index;
777}
778
779static struct objagg_tmp_graph *objagg_tmp_graph_create(struct objagg *objagg)
780{
781 unsigned int nodes_count = objagg->obj_count;
782 struct objagg_tmp_graph *graph;
783 struct objagg_tmp_node *node;
784 struct objagg_tmp_node *pnode;
785 struct objagg_obj *objagg_obj;
786 size_t alloc_size;
787 int i, j;
788
789 graph = kzalloc(sizeof(*graph), GFP_KERNEL);
790 if (!graph)
791 return NULL;
792
793 graph->nodes = kcalloc(nodes_count, sizeof(*graph->nodes), GFP_KERNEL);
794 if (!graph->nodes)
795 goto err_nodes_alloc;
796 graph->nodes_count = nodes_count;
797
798 alloc_size = BITS_TO_LONGS(nodes_count * nodes_count) *
799 sizeof(unsigned long);
800 graph->edges = kzalloc(alloc_size, GFP_KERNEL);
801 if (!graph->edges)
802 goto err_edges_alloc;
803
804 i = 0;
805 list_for_each_entry(objagg_obj, &objagg->obj_list, list) {
806 node = &graph->nodes[i++];
807 node->objagg_obj = objagg_obj;
808 }
809
810 /* Assemble a temporary graph. Insert edge X->Y in case Y can be
811 * in delta of X.
812 */
813 for (i = 0; i < nodes_count; i++) {
814 for (j = 0; j < nodes_count; j++) {
815 if (i == j)
816 continue;
817 pnode = &graph->nodes[i];
818 node = &graph->nodes[j];
819 if (objagg->ops->delta_check(objagg->priv,
820 pnode->objagg_obj->obj,
821 node->objagg_obj->obj)) {
822 objagg_tmp_graph_edge_set(graph, i, j);
823
824 }
825 }
826 }
827 return graph;
828
829err_edges_alloc:
830 kfree(graph->nodes);
831err_nodes_alloc:
832 kfree(graph);
833 return NULL;
834}
835
836static void objagg_tmp_graph_destroy(struct objagg_tmp_graph *graph)
837{
838 kfree(graph->edges);
839 kfree(graph->nodes);
840 kfree(graph);
841}
842
843static int
844objagg_opt_simple_greedy_fillup_hints(struct objagg_hints *objagg_hints,
845 struct objagg *objagg)
846{
847 struct objagg_hints_node *hnode, *parent_hnode;
848 struct objagg_tmp_graph *graph;
849 struct objagg_tmp_node *node;
850 int index;
851 int j;
852 int err;
853
854 graph = objagg_tmp_graph_create(objagg);
855 if (!graph)
856 return -ENOMEM;
857
858 /* Find the nodes from the ones that can accommodate most users
859 * and cross them out of the graph. Save them to the hint list.
860 */
861 while ((index = objagg_tmp_graph_node_max_weight(graph)) != -1) {
862 node = &graph->nodes[index];
863 node->crossed_out = true;
864 hnode = objagg_hints_node_create(objagg_hints,
865 node->objagg_obj,
866 objagg->ops->obj_size,
867 NULL);
868 if (IS_ERR(hnode)) {
869 err = PTR_ERR(hnode);
870 goto out;
871 }
872 parent_hnode = hnode;
873 for (j = 0; j < graph->nodes_count; j++) {
874 if (!objagg_tmp_graph_is_edge(graph, index, j))
875 continue;
876 node = &graph->nodes[j];
877 if (node->crossed_out)
878 continue;
879 node->crossed_out = true;
880 hnode = objagg_hints_node_create(objagg_hints,
881 node->objagg_obj,
882 objagg->ops->obj_size,
883 parent_hnode);
884 if (IS_ERR(hnode)) {
885 err = PTR_ERR(hnode);
886 goto out;
887 }
888 }
889 }
890
891 err = 0;
892out:
893 objagg_tmp_graph_destroy(graph);
894 return err;
895}
896
897struct objagg_opt_algo {
898 int (*fillup_hints)(struct objagg_hints *objagg_hints,
899 struct objagg *objagg);
900};
901
902static const struct objagg_opt_algo objagg_opt_simple_greedy = {
903 .fillup_hints = objagg_opt_simple_greedy_fillup_hints,
904};
905
906
907static const struct objagg_opt_algo *objagg_opt_algos[] = {
908 [OBJAGG_OPT_ALGO_SIMPLE_GREEDY] = &objagg_opt_simple_greedy,
909};
910
911static int objagg_hints_obj_cmp(struct rhashtable_compare_arg *arg,
912 const void *obj)
913{
914 struct rhashtable *ht = arg->ht;
915 struct objagg_hints *objagg_hints =
916 container_of(ht, struct objagg_hints, node_ht);
917 const struct objagg_ops *ops = objagg_hints->ops;
918 const char *ptr = obj;
919
920 ptr += ht->p.key_offset;
921 return ops->hints_obj_cmp ? ops->hints_obj_cmp(ptr, arg->key) :
922 memcmp(ptr, arg->key, ht->p.key_len);
923}
924
925/**
926 * objagg_hints_get - obtains hints instance
927 * @objagg: objagg instance
928 * @opt_algo_type: type of hints finding algorithm
929 *
930 * Note: all locking must be provided by the caller.
931 *
932 * According to the algo type, the existing objects of objagg instance
933 * are going to be went-through to assemble an optimal tree. We call this
934 * tree hints. These hints can be later on used for creation of
935 * a new objagg instance. There, the future object creations are going
936 * to be consulted with these hints in order to find out, where exactly
937 * the new object should be put as a root or delta.
938 *
939 * Returns a pointer to hints instance in case of success,
940 * otherwise it returns pointer error using ERR_PTR macro.
941 */
942struct objagg_hints *objagg_hints_get(struct objagg *objagg,
943 enum objagg_opt_algo_type opt_algo_type)
944{
945 const struct objagg_opt_algo *algo = objagg_opt_algos[opt_algo_type];
946 struct objagg_hints *objagg_hints;
947 int err;
948
949 objagg_hints = kzalloc(sizeof(*objagg_hints), GFP_KERNEL);
950 if (!objagg_hints)
951 return ERR_PTR(-ENOMEM);
952
953 objagg_hints->ops = objagg->ops;
954 objagg_hints->refcount = 1;
955
956 INIT_LIST_HEAD(&objagg_hints->node_list);
957
958 objagg_hints->ht_params.key_len = objagg->ops->obj_size;
959 objagg_hints->ht_params.key_offset =
960 offsetof(struct objagg_hints_node, obj);
961 objagg_hints->ht_params.head_offset =
962 offsetof(struct objagg_hints_node, ht_node);
963 objagg_hints->ht_params.obj_cmpfn = objagg_hints_obj_cmp;
964
965 err = rhashtable_init(&objagg_hints->node_ht, &objagg_hints->ht_params);
966 if (err)
967 goto err_rhashtable_init;
968
969 err = algo->fillup_hints(objagg_hints, objagg);
970 if (err)
971 goto err_fillup_hints;
972
973 if (WARN_ON(objagg_hints->node_count != objagg->obj_count)) {
974 err = -EINVAL;
975 goto err_node_count_check;
976 }
977
978 return objagg_hints;
979
980err_node_count_check:
981err_fillup_hints:
982 objagg_hints_flush(objagg_hints);
983 rhashtable_destroy(&objagg_hints->node_ht);
984err_rhashtable_init:
985 kfree(objagg_hints);
986 return ERR_PTR(err);
987}
988EXPORT_SYMBOL(objagg_hints_get);
989
990/**
991 * objagg_hints_put - puts hints instance
992 * @objagg_hints: objagg hints instance
993 *
994 * Note: all locking must be provided by the caller.
995 */
996void objagg_hints_put(struct objagg_hints *objagg_hints)
997{
998 if (--objagg_hints->refcount)
999 return;
1000 objagg_hints_flush(objagg_hints);
1001 rhashtable_destroy(&objagg_hints->node_ht);
1002 kfree(objagg_hints);
1003}
1004EXPORT_SYMBOL(objagg_hints_put);
1005
1006/**
1007 * objagg_hints_stats_get - obtains stats of the hints instance
1008 * @objagg_hints: hints instance
1009 *
1010 * Note: all locking must be provided by the caller.
1011 *
1012 * The returned structure contains statistics of all objects
1013 * currently in use, ordered by following rules:
1014 * 1) Root objects are always on lower indexes than the rest.
1015 * 2) Objects with higher delta user count are always on lower
1016 * indexes.
1017 * 3) In case multiple objects have the same delta user count,
1018 * the objects are ordered by user count.
1019 *
1020 * Returns a pointer to stats instance in case of success,
1021 * otherwise it returns pointer error using ERR_PTR macro.
1022 */
1023const struct objagg_stats *
1024objagg_hints_stats_get(struct objagg_hints *objagg_hints)
1025{
1026 struct objagg_stats *objagg_stats;
1027 struct objagg_hints_node *hnode;
1028 int i;
1029
1030 objagg_stats = kzalloc(struct_size(objagg_stats, stats_info,
1031 objagg_hints->node_count),
1032 GFP_KERNEL);
1033 if (!objagg_stats)
1034 return ERR_PTR(-ENOMEM);
1035
1036 i = 0;
1037 list_for_each_entry(hnode, &objagg_hints->node_list, list) {
1038 memcpy(&objagg_stats->stats_info[i], &hnode->stats_info,
1039 sizeof(objagg_stats->stats_info[0]));
1040 if (objagg_stats->stats_info[i].is_root)
1041 objagg_stats->root_count++;
1042 i++;
1043 }
1044 objagg_stats->stats_info_count = i;
1045
1046 sort(objagg_stats->stats_info, objagg_stats->stats_info_count,
1047 sizeof(struct objagg_obj_stats_info),
1048 objagg_stats_info_sort_cmp_func, NULL);
1049
1050 return objagg_stats;
1051}
1052EXPORT_SYMBOL(objagg_hints_stats_get);
1053
499MODULE_LICENSE("Dual BSD/GPL"); 1054MODULE_LICENSE("Dual BSD/GPL");
500MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>"); 1055MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
501MODULE_DESCRIPTION("Object aggregation manager"); 1056MODULE_DESCRIPTION("Object aggregation manager");
diff --git a/lib/raid6/Makefile b/lib/raid6/Makefile
index 4e90d443d1b0..e723eacf7868 100644
--- a/lib/raid6/Makefile
+++ b/lib/raid6/Makefile
@@ -39,7 +39,7 @@ endif
39ifeq ($(CONFIG_KERNEL_MODE_NEON),y) 39ifeq ($(CONFIG_KERNEL_MODE_NEON),y)
40NEON_FLAGS := -ffreestanding 40NEON_FLAGS := -ffreestanding
41ifeq ($(ARCH),arm) 41ifeq ($(ARCH),arm)
42NEON_FLAGS += -mfloat-abi=softfp -mfpu=neon 42NEON_FLAGS += -march=armv7-a -mfloat-abi=softfp -mfpu=neon
43endif 43endif
44CFLAGS_recov_neon_inner.o += $(NEON_FLAGS) 44CFLAGS_recov_neon_inner.o += $(NEON_FLAGS)
45ifeq ($(ARCH),arm64) 45ifeq ($(ARCH),arm64)
diff --git a/lib/raid6/neon.uc b/lib/raid6/neon.uc
index d5242f544551..b7c68030da4f 100644
--- a/lib/raid6/neon.uc
+++ b/lib/raid6/neon.uc
@@ -28,7 +28,6 @@
28 28
29typedef uint8x16_t unative_t; 29typedef uint8x16_t unative_t;
30 30
31#define NBYTES(x) ((unative_t){x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x})
32#define NSIZE sizeof(unative_t) 31#define NSIZE sizeof(unative_t)
33 32
34/* 33/*
@@ -61,7 +60,7 @@ void raid6_neon$#_gen_syndrome_real(int disks, unsigned long bytes, void **ptrs)
61 int d, z, z0; 60 int d, z, z0;
62 61
63 register unative_t wd$$, wq$$, wp$$, w1$$, w2$$; 62 register unative_t wd$$, wq$$, wp$$, w1$$, w2$$;
64 const unative_t x1d = NBYTES(0x1d); 63 const unative_t x1d = vdupq_n_u8(0x1d);
65 64
66 z0 = disks - 3; /* Highest data disk */ 65 z0 = disks - 3; /* Highest data disk */
67 p = dptr[z0+1]; /* XOR parity */ 66 p = dptr[z0+1]; /* XOR parity */
@@ -92,7 +91,7 @@ void raid6_neon$#_xor_syndrome_real(int disks, int start, int stop,
92 int d, z, z0; 91 int d, z, z0;
93 92
94 register unative_t wd$$, wq$$, wp$$, w1$$, w2$$; 93 register unative_t wd$$, wq$$, wp$$, w1$$, w2$$;
95 const unative_t x1d = NBYTES(0x1d); 94 const unative_t x1d = vdupq_n_u8(0x1d);
96 95
97 z0 = stop; /* P/Q right side optimization */ 96 z0 = stop; /* P/Q right side optimization */
98 p = dptr[disks-2]; /* XOR parity */ 97 p = dptr[disks-2]; /* XOR parity */
diff --git a/lib/raid6/recov_neon_inner.c b/lib/raid6/recov_neon_inner.c
index 8cd20c9f834a..f13c07f82297 100644
--- a/lib/raid6/recov_neon_inner.c
+++ b/lib/raid6/recov_neon_inner.c
@@ -10,11 +10,6 @@
10 10
11#include <arm_neon.h> 11#include <arm_neon.h>
12 12
13static const uint8x16_t x0f = {
14 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f,
15 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f,
16};
17
18#ifdef CONFIG_ARM 13#ifdef CONFIG_ARM
19/* 14/*
20 * AArch32 does not provide this intrinsic natively because it does not 15 * AArch32 does not provide this intrinsic natively because it does not
@@ -41,6 +36,7 @@ void __raid6_2data_recov_neon(int bytes, uint8_t *p, uint8_t *q, uint8_t *dp,
41 uint8x16_t pm1 = vld1q_u8(pbmul + 16); 36 uint8x16_t pm1 = vld1q_u8(pbmul + 16);
42 uint8x16_t qm0 = vld1q_u8(qmul); 37 uint8x16_t qm0 = vld1q_u8(qmul);
43 uint8x16_t qm1 = vld1q_u8(qmul + 16); 38 uint8x16_t qm1 = vld1q_u8(qmul + 16);
39 uint8x16_t x0f = vdupq_n_u8(0x0f);
44 40
45 /* 41 /*
46 * while ( bytes-- ) { 42 * while ( bytes-- ) {
@@ -60,14 +56,14 @@ void __raid6_2data_recov_neon(int bytes, uint8_t *p, uint8_t *q, uint8_t *dp,
60 px = veorq_u8(vld1q_u8(p), vld1q_u8(dp)); 56 px = veorq_u8(vld1q_u8(p), vld1q_u8(dp));
61 vx = veorq_u8(vld1q_u8(q), vld1q_u8(dq)); 57 vx = veorq_u8(vld1q_u8(q), vld1q_u8(dq));
62 58
63 vy = (uint8x16_t)vshrq_n_s16((int16x8_t)vx, 4); 59 vy = vshrq_n_u8(vx, 4);
64 vx = vqtbl1q_u8(qm0, vandq_u8(vx, x0f)); 60 vx = vqtbl1q_u8(qm0, vandq_u8(vx, x0f));
65 vy = vqtbl1q_u8(qm1, vandq_u8(vy, x0f)); 61 vy = vqtbl1q_u8(qm1, vy);
66 qx = veorq_u8(vx, vy); 62 qx = veorq_u8(vx, vy);
67 63
68 vy = (uint8x16_t)vshrq_n_s16((int16x8_t)px, 4); 64 vy = vshrq_n_u8(px, 4);
69 vx = vqtbl1q_u8(pm0, vandq_u8(px, x0f)); 65 vx = vqtbl1q_u8(pm0, vandq_u8(px, x0f));
70 vy = vqtbl1q_u8(pm1, vandq_u8(vy, x0f)); 66 vy = vqtbl1q_u8(pm1, vy);
71 vx = veorq_u8(vx, vy); 67 vx = veorq_u8(vx, vy);
72 db = veorq_u8(vx, qx); 68 db = veorq_u8(vx, qx);
73 69
@@ -87,6 +83,7 @@ void __raid6_datap_recov_neon(int bytes, uint8_t *p, uint8_t *q, uint8_t *dq,
87{ 83{
88 uint8x16_t qm0 = vld1q_u8(qmul); 84 uint8x16_t qm0 = vld1q_u8(qmul);
89 uint8x16_t qm1 = vld1q_u8(qmul + 16); 85 uint8x16_t qm1 = vld1q_u8(qmul + 16);
86 uint8x16_t x0f = vdupq_n_u8(0x0f);
90 87
91 /* 88 /*
92 * while (bytes--) { 89 * while (bytes--) {
@@ -100,9 +97,9 @@ void __raid6_datap_recov_neon(int bytes, uint8_t *p, uint8_t *q, uint8_t *dq,
100 97
101 vx = veorq_u8(vld1q_u8(q), vld1q_u8(dq)); 98 vx = veorq_u8(vld1q_u8(q), vld1q_u8(dq));
102 99
103 vy = (uint8x16_t)vshrq_n_s16((int16x8_t)vx, 4); 100 vy = vshrq_n_u8(vx, 4);
104 vx = vqtbl1q_u8(qm0, vandq_u8(vx, x0f)); 101 vx = vqtbl1q_u8(qm0, vandq_u8(vx, x0f));
105 vy = vqtbl1q_u8(qm1, vandq_u8(vy, x0f)); 102 vy = vqtbl1q_u8(qm1, vy);
106 vx = veorq_u8(vx, vy); 103 vx = veorq_u8(vx, vy);
107 vy = veorq_u8(vx, vld1q_u8(p)); 104 vy = veorq_u8(vx, vld1q_u8(p));
108 105
diff --git a/lib/refcount.c b/lib/refcount.c
index ebcf8cd49e05..6e904af0fb3e 100644
--- a/lib/refcount.c
+++ b/lib/refcount.c
@@ -33,6 +33,9 @@
33 * Note that the allocator is responsible for ordering things between free() 33 * Note that the allocator is responsible for ordering things between free()
34 * and alloc(). 34 * and alloc().
35 * 35 *
36 * The decrements dec_and_test() and sub_and_test() also provide acquire
37 * ordering on success.
38 *
36 */ 39 */
37 40
38#include <linux/mutex.h> 41#include <linux/mutex.h>
@@ -164,8 +167,8 @@ EXPORT_SYMBOL(refcount_inc_checked);
164 * at UINT_MAX. 167 * at UINT_MAX.
165 * 168 *
166 * Provides release memory ordering, such that prior loads and stores are done 169 * Provides release memory ordering, such that prior loads and stores are done
167 * before, and provides a control dependency such that free() must come after. 170 * before, and provides an acquire ordering on success such that free()
168 * See the comment on top. 171 * must come after.
169 * 172 *
170 * Use of this function is not recommended for the normal reference counting 173 * Use of this function is not recommended for the normal reference counting
171 * use case in which references are taken and released one at a time. In these 174 * use case in which references are taken and released one at a time. In these
@@ -190,7 +193,12 @@ bool refcount_sub_and_test_checked(unsigned int i, refcount_t *r)
190 193
191 } while (!atomic_try_cmpxchg_release(&r->refs, &val, new)); 194 } while (!atomic_try_cmpxchg_release(&r->refs, &val, new));
192 195
193 return !new; 196 if (!new) {
197 smp_acquire__after_ctrl_dep();
198 return true;
199 }
200 return false;
201
194} 202}
195EXPORT_SYMBOL(refcount_sub_and_test_checked); 203EXPORT_SYMBOL(refcount_sub_and_test_checked);
196 204
@@ -202,8 +210,8 @@ EXPORT_SYMBOL(refcount_sub_and_test_checked);
202 * decrement when saturated at UINT_MAX. 210 * decrement when saturated at UINT_MAX.
203 * 211 *
204 * Provides release memory ordering, such that prior loads and stores are done 212 * Provides release memory ordering, such that prior loads and stores are done
205 * before, and provides a control dependency such that free() must come after. 213 * before, and provides an acquire ordering on success such that free()
206 * See the comment on top. 214 * must come after.
207 * 215 *
208 * Return: true if the resulting refcount is 0, false otherwise 216 * Return: true if the resulting refcount is 0, false otherwise
209 */ 217 */
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 852ffa5160f1..0a105d4af166 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -682,7 +682,7 @@ EXPORT_SYMBOL_GPL(rhashtable_walk_enter);
682 * rhashtable_walk_exit - Free an iterator 682 * rhashtable_walk_exit - Free an iterator
683 * @iter: Hash table Iterator 683 * @iter: Hash table Iterator
684 * 684 *
685 * This function frees resources allocated by rhashtable_walk_init. 685 * This function frees resources allocated by rhashtable_walk_enter.
686 */ 686 */
687void rhashtable_walk_exit(struct rhashtable_iter *iter) 687void rhashtable_walk_exit(struct rhashtable_iter *iter)
688{ 688{
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 65c2d06250a6..5b382c1244ed 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -26,14 +26,10 @@
26static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) 26static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index)
27{ 27{
28 unsigned long mask, val; 28 unsigned long mask, val;
29 unsigned long __maybe_unused flags;
30 bool ret = false; 29 bool ret = false;
30 unsigned long flags;
31 31
32 /* Silence bogus lockdep warning */ 32 spin_lock_irqsave(&sb->map[index].swap_lock, flags);
33#if defined(CONFIG_LOCKDEP)
34 local_irq_save(flags);
35#endif
36 spin_lock(&sb->map[index].swap_lock);
37 33
38 if (!sb->map[index].cleared) 34 if (!sb->map[index].cleared)
39 goto out_unlock; 35 goto out_unlock;
@@ -54,10 +50,7 @@ static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index)
54 50
55 ret = true; 51 ret = true;
56out_unlock: 52out_unlock:
57 spin_unlock(&sb->map[index].swap_lock); 53 spin_unlock_irqrestore(&sb->map[index].swap_lock, flags);
58#if defined(CONFIG_LOCKDEP)
59 local_irq_restore(flags);
60#endif
61 return ret; 54 return ret;
62} 55}
63 56
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index 9ba349e775ef..739dc9fe2c55 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -625,6 +625,32 @@ bool __sg_page_iter_next(struct sg_page_iter *piter)
625} 625}
626EXPORT_SYMBOL(__sg_page_iter_next); 626EXPORT_SYMBOL(__sg_page_iter_next);
627 627
628static int sg_dma_page_count(struct scatterlist *sg)
629{
630 return PAGE_ALIGN(sg->offset + sg_dma_len(sg)) >> PAGE_SHIFT;
631}
632
633bool __sg_page_iter_dma_next(struct sg_dma_page_iter *dma_iter)
634{
635 struct sg_page_iter *piter = &dma_iter->base;
636
637 if (!piter->__nents || !piter->sg)
638 return false;
639
640 piter->sg_pgoffset += piter->__pg_advance;
641 piter->__pg_advance = 1;
642
643 while (piter->sg_pgoffset >= sg_dma_page_count(piter->sg)) {
644 piter->sg_pgoffset -= sg_dma_page_count(piter->sg);
645 piter->sg = sg_next(piter->sg);
646 if (!--piter->__nents || !piter->sg)
647 return false;
648 }
649
650 return true;
651}
652EXPORT_SYMBOL(__sg_page_iter_dma_next);
653
628/** 654/**
629 * sg_miter_start - start mapping iteration over a sg list 655 * sg_miter_start - start mapping iteration over a sg list
630 * @miter: sg mapping iter to be started 656 * @miter: sg mapping iter to be started
diff --git a/lib/smp_processor_id.c b/lib/smp_processor_id.c
index 85925aaa4fff..157d9e31f6c2 100644
--- a/lib/smp_processor_id.c
+++ b/lib/smp_processor_id.c
@@ -5,10 +5,11 @@
5 * DEBUG_PREEMPT variant of smp_processor_id(). 5 * DEBUG_PREEMPT variant of smp_processor_id().
6 */ 6 */
7#include <linux/export.h> 7#include <linux/export.h>
8#include <linux/kprobes.h>
8#include <linux/sched.h> 9#include <linux/sched.h>
9 10
10notrace static unsigned int check_preemption_disabled(const char *what1, 11notrace static nokprobe_inline
11 const char *what2) 12unsigned int check_preemption_disabled(const char *what1, const char *what2)
12{ 13{
13 int this_cpu = raw_smp_processor_id(); 14 int this_cpu = raw_smp_processor_id();
14 15
@@ -56,9 +57,11 @@ notrace unsigned int debug_smp_processor_id(void)
56 return check_preemption_disabled("smp_processor_id", ""); 57 return check_preemption_disabled("smp_processor_id", "");
57} 58}
58EXPORT_SYMBOL(debug_smp_processor_id); 59EXPORT_SYMBOL(debug_smp_processor_id);
60NOKPROBE_SYMBOL(debug_smp_processor_id);
59 61
60notrace void __this_cpu_preempt_check(const char *op) 62notrace void __this_cpu_preempt_check(const char *op)
61{ 63{
62 check_preemption_disabled("__this_cpu_", op); 64 check_preemption_disabled("__this_cpu_", op);
63} 65}
64EXPORT_SYMBOL(__this_cpu_preempt_check); 66EXPORT_SYMBOL(__this_cpu_preempt_check);
67NOKPROBE_SYMBOL(__this_cpu_preempt_check);
diff --git a/lib/test_bpf.c b/lib/test_bpf.c
index f3e570722a7e..0845f635f404 100644
--- a/lib/test_bpf.c
+++ b/lib/test_bpf.c
@@ -6668,12 +6668,14 @@ static int __run_one(const struct bpf_prog *fp, const void *data,
6668 u64 start, finish; 6668 u64 start, finish;
6669 int ret = 0, i; 6669 int ret = 0, i;
6670 6670
6671 preempt_disable();
6671 start = ktime_get_ns(); 6672 start = ktime_get_ns();
6672 6673
6673 for (i = 0; i < runs; i++) 6674 for (i = 0; i < runs; i++)
6674 ret = BPF_PROG_RUN(fp, data); 6675 ret = BPF_PROG_RUN(fp, data);
6675 6676
6676 finish = ktime_get_ns(); 6677 finish = ktime_get_ns();
6678 preempt_enable();
6677 6679
6678 *duration = finish - start; 6680 *duration = finish - start;
6679 do_div(*duration, runs); 6681 do_div(*duration, runs);
diff --git a/lib/test_firmware.c b/lib/test_firmware.c
index 7cab9a9869ac..7222093ee00b 100644
--- a/lib/test_firmware.c
+++ b/lib/test_firmware.c
@@ -631,11 +631,6 @@ static ssize_t trigger_batched_requests_store(struct device *dev,
631 631
632 for (i = 0; i < test_fw_config->num_requests; i++) { 632 for (i = 0; i < test_fw_config->num_requests; i++) {
633 req = &test_fw_config->reqs[i]; 633 req = &test_fw_config->reqs[i];
634 if (!req) {
635 WARN_ON(1);
636 rc = -ENOMEM;
637 goto out_bail;
638 }
639 req->fw = NULL; 634 req->fw = NULL;
640 req->idx = i; 635 req->idx = i;
641 req->name = test_fw_config->name; 636 req->name = test_fw_config->name;
@@ -737,10 +732,6 @@ ssize_t trigger_batched_requests_async_store(struct device *dev,
737 732
738 for (i = 0; i < test_fw_config->num_requests; i++) { 733 for (i = 0; i < test_fw_config->num_requests; i++) {
739 req = &test_fw_config->reqs[i]; 734 req = &test_fw_config->reqs[i];
740 if (!req) {
741 WARN_ON(1);
742 goto out_bail;
743 }
744 req->name = test_fw_config->name; 735 req->name = test_fw_config->name;
745 req->fw = NULL; 736 req->fw = NULL;
746 req->idx = i; 737 req->idx = i;
diff --git a/lib/test_kasan.c b/lib/test_kasan.c
index 51b78405bf24..7de2702621dc 100644
--- a/lib/test_kasan.c
+++ b/lib/test_kasan.c
@@ -480,29 +480,6 @@ static noinline void __init copy_user_test(void)
480 kfree(kmem); 480 kfree(kmem);
481} 481}
482 482
483static noinline void __init use_after_scope_test(void)
484{
485 volatile char *volatile p;
486
487 pr_info("use-after-scope on int\n");
488 {
489 int local = 0;
490
491 p = (char *)&local;
492 }
493 p[0] = 1;
494 p[3] = 1;
495
496 pr_info("use-after-scope on array\n");
497 {
498 char local[1024] = {0};
499
500 p = local;
501 }
502 p[0] = 1;
503 p[1023] = 1;
504}
505
506static noinline void __init kasan_alloca_oob_left(void) 483static noinline void __init kasan_alloca_oob_left(void)
507{ 484{
508 volatile int i = 10; 485 volatile int i = 10;
@@ -682,7 +659,6 @@ static int __init kmalloc_tests_init(void)
682 kasan_alloca_oob_right(); 659 kasan_alloca_oob_right();
683 ksize_unpoisons_memory(); 660 ksize_unpoisons_memory();
684 copy_user_test(); 661 copy_user_test();
685 use_after_scope_test();
686 kmem_cache_double_free(); 662 kmem_cache_double_free();
687 kmem_cache_invalid_free(); 663 kmem_cache_invalid_free();
688 kasan_memchr(); 664 kasan_memchr();
diff --git a/lib/test_kmod.c b/lib/test_kmod.c
index d82d022111e0..9cf77628fc91 100644
--- a/lib/test_kmod.c
+++ b/lib/test_kmod.c
@@ -632,7 +632,7 @@ static void __kmod_config_free(struct test_config *config)
632 config->test_driver = NULL; 632 config->test_driver = NULL;
633 633
634 kfree_const(config->test_fs); 634 kfree_const(config->test_fs);
635 config->test_driver = NULL; 635 config->test_fs = NULL;
636} 636}
637 637
638static void kmod_config_free(struct kmod_test_device *test_dev) 638static void kmod_config_free(struct kmod_test_device *test_dev)
diff --git a/lib/test_objagg.c b/lib/test_objagg.c
index ab57144bb0cd..72c1abfa154d 100644
--- a/lib/test_objagg.c
+++ b/lib/test_objagg.c
@@ -87,6 +87,15 @@ static void world_obj_put(struct world *world, struct objagg *objagg,
87 87
88#define MAX_KEY_ID_DIFF 5 88#define MAX_KEY_ID_DIFF 5
89 89
90static bool delta_check(void *priv, const void *parent_obj, const void *obj)
91{
92 const struct tokey *parent_key = parent_obj;
93 const struct tokey *key = obj;
94 int diff = key->id - parent_key->id;
95
96 return diff >= 0 && diff <= MAX_KEY_ID_DIFF;
97}
98
90static void *delta_create(void *priv, void *parent_obj, void *obj) 99static void *delta_create(void *priv, void *parent_obj, void *obj)
91{ 100{
92 struct tokey *parent_key = parent_obj; 101 struct tokey *parent_key = parent_obj;
@@ -95,7 +104,7 @@ static void *delta_create(void *priv, void *parent_obj, void *obj)
95 int diff = key->id - parent_key->id; 104 int diff = key->id - parent_key->id;
96 struct delta *delta; 105 struct delta *delta;
97 106
98 if (diff < 0 || diff > MAX_KEY_ID_DIFF) 107 if (!delta_check(priv, parent_obj, obj))
99 return ERR_PTR(-EINVAL); 108 return ERR_PTR(-EINVAL);
100 109
101 delta = kzalloc(sizeof(*delta), GFP_KERNEL); 110 delta = kzalloc(sizeof(*delta), GFP_KERNEL);
@@ -115,7 +124,7 @@ static void delta_destroy(void *priv, void *delta_priv)
115 kfree(delta); 124 kfree(delta);
116} 125}
117 126
118static void *root_create(void *priv, void *obj) 127static void *root_create(void *priv, void *obj, unsigned int id)
119{ 128{
120 struct world *world = priv; 129 struct world *world = priv;
121 struct tokey *key = obj; 130 struct tokey *key = obj;
@@ -268,6 +277,12 @@ stats_put:
268 return err; 277 return err;
269} 278}
270 279
280static bool delta_check_dummy(void *priv, const void *parent_obj,
281 const void *obj)
282{
283 return false;
284}
285
271static void *delta_create_dummy(void *priv, void *parent_obj, void *obj) 286static void *delta_create_dummy(void *priv, void *parent_obj, void *obj)
272{ 287{
273 return ERR_PTR(-EOPNOTSUPP); 288 return ERR_PTR(-EOPNOTSUPP);
@@ -279,6 +294,7 @@ static void delta_destroy_dummy(void *priv, void *delta_priv)
279 294
280static const struct objagg_ops nodelta_ops = { 295static const struct objagg_ops nodelta_ops = {
281 .obj_size = sizeof(struct tokey), 296 .obj_size = sizeof(struct tokey),
297 .delta_check = delta_check_dummy,
282 .delta_create = delta_create_dummy, 298 .delta_create = delta_create_dummy,
283 .delta_destroy = delta_destroy_dummy, 299 .delta_destroy = delta_destroy_dummy,
284 .root_create = root_create, 300 .root_create = root_create,
@@ -292,7 +308,7 @@ static int test_nodelta(void)
292 int i; 308 int i;
293 int err; 309 int err;
294 310
295 objagg = objagg_create(&nodelta_ops, &world); 311 objagg = objagg_create(&nodelta_ops, NULL, &world);
296 if (IS_ERR(objagg)) 312 if (IS_ERR(objagg))
297 return PTR_ERR(objagg); 313 return PTR_ERR(objagg);
298 314
@@ -357,6 +373,7 @@ err_stats_second_zero:
357 373
358static const struct objagg_ops delta_ops = { 374static const struct objagg_ops delta_ops = {
359 .obj_size = sizeof(struct tokey), 375 .obj_size = sizeof(struct tokey),
376 .delta_check = delta_check,
360 .delta_create = delta_create, 377 .delta_create = delta_create,
361 .delta_destroy = delta_destroy, 378 .delta_destroy = delta_destroy,
362 .root_create = root_create, 379 .root_create = root_create,
@@ -728,8 +745,10 @@ static int check_expect_stats(struct objagg *objagg,
728 int err; 745 int err;
729 746
730 stats = objagg_stats_get(objagg); 747 stats = objagg_stats_get(objagg);
731 if (IS_ERR(stats)) 748 if (IS_ERR(stats)) {
749 *errmsg = "objagg_stats_get() failed.";
732 return PTR_ERR(stats); 750 return PTR_ERR(stats);
751 }
733 err = __check_expect_stats(stats, expect_stats, errmsg); 752 err = __check_expect_stats(stats, expect_stats, errmsg);
734 objagg_stats_put(stats); 753 objagg_stats_put(stats);
735 return err; 754 return err;
@@ -769,7 +788,6 @@ static int test_delta_action_item(struct world *world,
769 if (err) 788 if (err)
770 goto errout; 789 goto errout;
771 790
772 errmsg = NULL;
773 err = check_expect_stats(objagg, &action_item->expect_stats, &errmsg); 791 err = check_expect_stats(objagg, &action_item->expect_stats, &errmsg);
774 if (err) { 792 if (err) {
775 pr_err("Key %u: Stats: %s\n", action_item->key_id, errmsg); 793 pr_err("Key %u: Stats: %s\n", action_item->key_id, errmsg);
@@ -793,7 +811,7 @@ static int test_delta(void)
793 int i; 811 int i;
794 int err; 812 int err;
795 813
796 objagg = objagg_create(&delta_ops, &world); 814 objagg = objagg_create(&delta_ops, NULL, &world);
797 if (IS_ERR(objagg)) 815 if (IS_ERR(objagg))
798 return PTR_ERR(objagg); 816 return PTR_ERR(objagg);
799 817
@@ -815,6 +833,170 @@ err_do_action_item:
815 return err; 833 return err;
816} 834}
817 835
836struct hints_case {
837 const unsigned int *key_ids;
838 size_t key_ids_count;
839 struct expect_stats expect_stats;
840 struct expect_stats expect_stats_hints;
841};
842
843static const unsigned int hints_case_key_ids[] = {
844 1, 7, 3, 5, 3, 1, 30, 8, 8, 5, 6, 8,
845};
846
847static const struct hints_case hints_case = {
848 .key_ids = hints_case_key_ids,
849 .key_ids_count = ARRAY_SIZE(hints_case_key_ids),
850 .expect_stats =
851 EXPECT_STATS(7, ROOT(1, 2, 7), ROOT(7, 1, 4), ROOT(30, 1, 1),
852 DELTA(8, 3), DELTA(3, 2),
853 DELTA(5, 2), DELTA(6, 1)),
854 .expect_stats_hints =
855 EXPECT_STATS(7, ROOT(3, 2, 9), ROOT(1, 2, 2), ROOT(30, 1, 1),
856 DELTA(8, 3), DELTA(5, 2),
857 DELTA(6, 1), DELTA(7, 1)),
858};
859
860static void __pr_debug_stats(const struct objagg_stats *stats)
861{
862 int i;
863
864 for (i = 0; i < stats->stats_info_count; i++)
865 pr_debug("Stat index %d key %u: u %d, d %d, %s\n", i,
866 obj_to_key_id(stats->stats_info[i].objagg_obj),
867 stats->stats_info[i].stats.user_count,
868 stats->stats_info[i].stats.delta_user_count,
869 stats->stats_info[i].is_root ? "root" : "noroot");
870}
871
872static void pr_debug_stats(struct objagg *objagg)
873{
874 const struct objagg_stats *stats;
875
876 stats = objagg_stats_get(objagg);
877 if (IS_ERR(stats))
878 return;
879 __pr_debug_stats(stats);
880 objagg_stats_put(stats);
881}
882
883static void pr_debug_hints_stats(struct objagg_hints *objagg_hints)
884{
885 const struct objagg_stats *stats;
886
887 stats = objagg_hints_stats_get(objagg_hints);
888 if (IS_ERR(stats))
889 return;
890 __pr_debug_stats(stats);
891 objagg_stats_put(stats);
892}
893
894static int check_expect_hints_stats(struct objagg_hints *objagg_hints,
895 const struct expect_stats *expect_stats,
896 const char **errmsg)
897{
898 const struct objagg_stats *stats;
899 int err;
900
901 stats = objagg_hints_stats_get(objagg_hints);
902 if (IS_ERR(stats))
903 return PTR_ERR(stats);
904 err = __check_expect_stats(stats, expect_stats, errmsg);
905 objagg_stats_put(stats);
906 return err;
907}
908
909static int test_hints_case(const struct hints_case *hints_case)
910{
911 struct objagg_obj *objagg_obj;
912 struct objagg_hints *hints;
913 struct world world2 = {};
914 struct world world = {};
915 struct objagg *objagg2;
916 struct objagg *objagg;
917 const char *errmsg;
918 int i;
919 int err;
920
921 objagg = objagg_create(&delta_ops, NULL, &world);
922 if (IS_ERR(objagg))
923 return PTR_ERR(objagg);
924
925 for (i = 0; i < hints_case->key_ids_count; i++) {
926 objagg_obj = world_obj_get(&world, objagg,
927 hints_case->key_ids[i]);
928 if (IS_ERR(objagg_obj)) {
929 err = PTR_ERR(objagg_obj);
930 goto err_world_obj_get;
931 }
932 }
933
934 pr_debug_stats(objagg);
935 err = check_expect_stats(objagg, &hints_case->expect_stats, &errmsg);
936 if (err) {
937 pr_err("Stats: %s\n", errmsg);
938 goto err_check_expect_stats;
939 }
940
941 hints = objagg_hints_get(objagg, OBJAGG_OPT_ALGO_SIMPLE_GREEDY);
942 if (IS_ERR(hints)) {
943 err = PTR_ERR(hints);
944 goto err_hints_get;
945 }
946
947 pr_debug_hints_stats(hints);
948 err = check_expect_hints_stats(hints, &hints_case->expect_stats_hints,
949 &errmsg);
950 if (err) {
951 pr_err("Hints stats: %s\n", errmsg);
952 goto err_check_expect_hints_stats;
953 }
954
955 objagg2 = objagg_create(&delta_ops, hints, &world2);
956 if (IS_ERR(objagg2))
957 return PTR_ERR(objagg2);
958
959 for (i = 0; i < hints_case->key_ids_count; i++) {
960 objagg_obj = world_obj_get(&world2, objagg2,
961 hints_case->key_ids[i]);
962 if (IS_ERR(objagg_obj)) {
963 err = PTR_ERR(objagg_obj);
964 goto err_world2_obj_get;
965 }
966 }
967
968 pr_debug_stats(objagg2);
969 err = check_expect_stats(objagg2, &hints_case->expect_stats_hints,
970 &errmsg);
971 if (err) {
972 pr_err("Stats2: %s\n", errmsg);
973 goto err_check_expect_stats2;
974 }
975
976 err = 0;
977
978err_check_expect_stats2:
979err_world2_obj_get:
980 for (i--; i >= 0; i--)
981 world_obj_put(&world2, objagg, hints_case->key_ids[i]);
982 objagg_hints_put(hints);
983 objagg_destroy(objagg2);
984 i = hints_case->key_ids_count;
985err_check_expect_hints_stats:
986err_hints_get:
987err_check_expect_stats:
988err_world_obj_get:
989 for (i--; i >= 0; i--)
990 world_obj_put(&world, objagg, hints_case->key_ids[i]);
991
992 objagg_destroy(objagg);
993 return err;
994}
995static int test_hints(void)
996{
997 return test_hints_case(&hints_case);
998}
999
818static int __init test_objagg_init(void) 1000static int __init test_objagg_init(void)
819{ 1001{
820 int err; 1002 int err;
@@ -822,7 +1004,10 @@ static int __init test_objagg_init(void)
822 err = test_nodelta(); 1004 err = test_nodelta();
823 if (err) 1005 if (err)
824 return err; 1006 return err;
825 return test_delta(); 1007 err = test_delta();
1008 if (err)
1009 return err;
1010 return test_hints();
826} 1011}
827 1012
828static void __exit test_objagg_exit(void) 1013static void __exit test_objagg_exit(void)
diff --git a/lib/test_rhashtable.c b/lib/test_rhashtable.c
index 6a8ac7626797..3bd2e91bfc29 100644
--- a/lib/test_rhashtable.c
+++ b/lib/test_rhashtable.c
@@ -177,16 +177,11 @@ static int __init test_rht_lookup(struct rhashtable *ht, struct test_obj *array,
177 177
178static void test_bucket_stats(struct rhashtable *ht, unsigned int entries) 178static void test_bucket_stats(struct rhashtable *ht, unsigned int entries)
179{ 179{
180 unsigned int err, total = 0, chain_len = 0; 180 unsigned int total = 0, chain_len = 0;
181 struct rhashtable_iter hti; 181 struct rhashtable_iter hti;
182 struct rhash_head *pos; 182 struct rhash_head *pos;
183 183
184 err = rhashtable_walk_init(ht, &hti, GFP_KERNEL); 184 rhashtable_walk_enter(ht, &hti);
185 if (err) {
186 pr_warn("Test failed: allocation error");
187 return;
188 }
189
190 rhashtable_walk_start(&hti); 185 rhashtable_walk_start(&hti);
191 186
192 while ((pos = rhashtable_walk_next(&hti))) { 187 while ((pos = rhashtable_walk_next(&hti))) {
@@ -395,7 +390,7 @@ static int __init test_rhltable(unsigned int entries)
395 if (WARN(err, "cannot remove element at slot %d", i)) 390 if (WARN(err, "cannot remove element at slot %d", i))
396 continue; 391 continue;
397 } else { 392 } else {
398 if (WARN(err != -ENOENT, "removed non-existant element %d, error %d not %d", 393 if (WARN(err != -ENOENT, "removed non-existent element %d, error %d not %d",
399 i, err, -ENOENT)) 394 i, err, -ENOENT))
400 continue; 395 continue;
401 } 396 }
@@ -440,7 +435,7 @@ static int __init test_rhltable(unsigned int entries)
440 if (WARN(err, "cannot remove element at slot %d", i)) 435 if (WARN(err, "cannot remove element at slot %d", i))
441 continue; 436 continue;
442 } else { 437 } else {
443 if (WARN(err != -ENOENT, "removed non-existant element, error %d not %d", 438 if (WARN(err != -ENOENT, "removed non-existent element, error %d not %d",
444 err, -ENOENT)) 439 err, -ENOENT))
445 continue; 440 continue;
446 } 441 }
@@ -541,38 +536,45 @@ static unsigned int __init print_ht(struct rhltable *rhlt)
541static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects, 536static int __init test_insert_dup(struct test_obj_rhl *rhl_test_objects,
542 int cnt, bool slow) 537 int cnt, bool slow)
543{ 538{
544 struct rhltable rhlt; 539 struct rhltable *rhlt;
545 unsigned int i, ret; 540 unsigned int i, ret;
546 const char *key; 541 const char *key;
547 int err = 0; 542 int err = 0;
548 543
549 err = rhltable_init(&rhlt, &test_rht_params_dup); 544 rhlt = kmalloc(sizeof(*rhlt), GFP_KERNEL);
550 if (WARN_ON(err)) 545 if (WARN_ON(!rhlt))
546 return -EINVAL;
547
548 err = rhltable_init(rhlt, &test_rht_params_dup);
549 if (WARN_ON(err)) {
550 kfree(rhlt);
551 return err; 551 return err;
552 }
552 553
553 for (i = 0; i < cnt; i++) { 554 for (i = 0; i < cnt; i++) {
554 rhl_test_objects[i].value.tid = i; 555 rhl_test_objects[i].value.tid = i;
555 key = rht_obj(&rhlt.ht, &rhl_test_objects[i].list_node.rhead); 556 key = rht_obj(&rhlt->ht, &rhl_test_objects[i].list_node.rhead);
556 key += test_rht_params_dup.key_offset; 557 key += test_rht_params_dup.key_offset;
557 558
558 if (slow) { 559 if (slow) {
559 err = PTR_ERR(rhashtable_insert_slow(&rhlt.ht, key, 560 err = PTR_ERR(rhashtable_insert_slow(&rhlt->ht, key,
560 &rhl_test_objects[i].list_node.rhead)); 561 &rhl_test_objects[i].list_node.rhead));
561 if (err == -EAGAIN) 562 if (err == -EAGAIN)
562 err = 0; 563 err = 0;
563 } else 564 } else
564 err = rhltable_insert(&rhlt, 565 err = rhltable_insert(rhlt,
565 &rhl_test_objects[i].list_node, 566 &rhl_test_objects[i].list_node,
566 test_rht_params_dup); 567 test_rht_params_dup);
567 if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast")) 568 if (WARN(err, "error %d on element %d/%d (%s)\n", err, i, cnt, slow? "slow" : "fast"))
568 goto skip_print; 569 goto skip_print;
569 } 570 }
570 571
571 ret = print_ht(&rhlt); 572 ret = print_ht(rhlt);
572 WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast"); 573 WARN(ret != cnt, "missing rhltable elements (%d != %d, %s)\n", ret, cnt, slow? "slow" : "fast");
573 574
574skip_print: 575skip_print:
575 rhltable_destroy(&rhlt); 576 rhltable_destroy(rhlt);
577 kfree(rhlt);
576 578
577 return 0; 579 return 0;
578} 580}
diff --git a/lib/test_stackinit.c b/lib/test_stackinit.c
new file mode 100644
index 000000000000..13115b6f2b88
--- /dev/null
+++ b/lib/test_stackinit.c
@@ -0,0 +1,378 @@
1// SPDX-Licenses: GPLv2
2/*
3 * Test cases for compiler-based stack variable zeroing via future
4 * compiler flags or CONFIG_GCC_PLUGIN_STRUCTLEAK*.
5 */
6#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
7
8#include <linux/init.h>
9#include <linux/kernel.h>
10#include <linux/module.h>
11#include <linux/string.h>
12
13/* Exfiltration buffer. */
14#define MAX_VAR_SIZE 128
15static char check_buf[MAX_VAR_SIZE];
16
17/* Character array to trigger stack protector in all functions. */
18#define VAR_BUFFER 32
19
20/* Volatile mask to convince compiler to copy memory with 0xff. */
21static volatile u8 forced_mask = 0xff;
22
23/* Location and size tracking to validate fill and test are colocated. */
24static void *fill_start, *target_start;
25static size_t fill_size, target_size;
26
27static bool range_contains(char *haystack_start, size_t haystack_size,
28 char *needle_start, size_t needle_size)
29{
30 if (needle_start >= haystack_start &&
31 needle_start + needle_size <= haystack_start + haystack_size)
32 return true;
33 return false;
34}
35
36#define DO_NOTHING_TYPE_SCALAR(var_type) var_type
37#define DO_NOTHING_TYPE_STRING(var_type) void
38#define DO_NOTHING_TYPE_STRUCT(var_type) void
39
40#define DO_NOTHING_RETURN_SCALAR(ptr) *(ptr)
41#define DO_NOTHING_RETURN_STRING(ptr) /**/
42#define DO_NOTHING_RETURN_STRUCT(ptr) /**/
43
44#define DO_NOTHING_CALL_SCALAR(var, name) \
45 (var) = do_nothing_ ## name(&(var))
46#define DO_NOTHING_CALL_STRING(var, name) \
47 do_nothing_ ## name(var)
48#define DO_NOTHING_CALL_STRUCT(var, name) \
49 do_nothing_ ## name(&(var))
50
51#define FETCH_ARG_SCALAR(var) &var
52#define FETCH_ARG_STRING(var) var
53#define FETCH_ARG_STRUCT(var) &var
54
55#define FILL_SIZE_STRING 16
56
57#define INIT_CLONE_SCALAR /**/
58#define INIT_CLONE_STRING [FILL_SIZE_STRING]
59#define INIT_CLONE_STRUCT /**/
60
61#define INIT_SCALAR_none /**/
62#define INIT_SCALAR_zero = 0
63
64#define INIT_STRING_none [FILL_SIZE_STRING] /**/
65#define INIT_STRING_zero [FILL_SIZE_STRING] = { }
66
67#define INIT_STRUCT_none /**/
68#define INIT_STRUCT_zero = { }
69#define INIT_STRUCT_static_partial = { .two = 0, }
70#define INIT_STRUCT_static_all = { .one = arg->one, \
71 .two = arg->two, \
72 .three = arg->three, \
73 .four = arg->four, \
74 }
75#define INIT_STRUCT_dynamic_partial = { .two = arg->two, }
76#define INIT_STRUCT_dynamic_all = { .one = arg->one, \
77 .two = arg->two, \
78 .three = arg->three, \
79 .four = arg->four, \
80 }
81#define INIT_STRUCT_runtime_partial ; \
82 var.two = 0
83#define INIT_STRUCT_runtime_all ; \
84 var.one = 0; \
85 var.two = 0; \
86 var.three = 0; \
87 memset(&var.four, 0, \
88 sizeof(var.four))
89
90/*
91 * @name: unique string name for the test
92 * @var_type: type to be tested for zeroing initialization
93 * @which: is this a SCALAR, STRING, or STRUCT type?
94 * @init_level: what kind of initialization is performed
95 */
96#define DEFINE_TEST_DRIVER(name, var_type, which) \
97/* Returns 0 on success, 1 on failure. */ \
98static noinline __init int test_ ## name (void) \
99{ \
100 var_type zero INIT_CLONE_ ## which; \
101 int ignored; \
102 u8 sum = 0, i; \
103 \
104 /* Notice when a new test is larger than expected. */ \
105 BUILD_BUG_ON(sizeof(zero) > MAX_VAR_SIZE); \
106 \
107 /* Fill clone type with zero for per-field init. */ \
108 memset(&zero, 0x00, sizeof(zero)); \
109 /* Fill stack with 0xFF. */ \
110 ignored = leaf_ ##name((unsigned long)&ignored, 1, \
111 FETCH_ARG_ ## which(zero)); \
112 /* Clear entire check buffer for later bit tests. */ \
113 memset(check_buf, 0x00, sizeof(check_buf)); \
114 /* Extract stack-defined variable contents. */ \
115 ignored = leaf_ ##name((unsigned long)&ignored, 0, \
116 FETCH_ARG_ ## which(zero)); \
117 \
118 /* Validate that compiler lined up fill and target. */ \
119 if (!range_contains(fill_start, fill_size, \
120 target_start, target_size)) { \
121 pr_err(#name ": stack fill missed target!?\n"); \
122 pr_err(#name ": fill %zu wide\n", fill_size); \
123 pr_err(#name ": target offset by %d\n", \
124 (int)((ssize_t)(uintptr_t)fill_start - \
125 (ssize_t)(uintptr_t)target_start)); \
126 return 1; \
127 } \
128 \
129 /* Look for any set bits in the check region. */ \
130 for (i = 0; i < sizeof(check_buf); i++) \
131 sum += (check_buf[i] != 0); \
132 \
133 if (sum == 0) \
134 pr_info(#name " ok\n"); \
135 else \
136 pr_warn(#name " FAIL (uninit bytes: %d)\n", \
137 sum); \
138 \
139 return (sum != 0); \
140}
141#define DEFINE_TEST(name, var_type, which, init_level) \
142/* no-op to force compiler into ignoring "uninitialized" vars */\
143static noinline __init DO_NOTHING_TYPE_ ## which(var_type) \
144do_nothing_ ## name(var_type *ptr) \
145{ \
146 /* Will always be true, but compiler doesn't know. */ \
147 if ((unsigned long)ptr > 0x2) \
148 return DO_NOTHING_RETURN_ ## which(ptr); \
149 else \
150 return DO_NOTHING_RETURN_ ## which(ptr + 1); \
151} \
152static noinline __init int leaf_ ## name(unsigned long sp, \
153 bool fill, \
154 var_type *arg) \
155{ \
156 char buf[VAR_BUFFER]; \
157 var_type var INIT_ ## which ## _ ## init_level; \
158 \
159 target_start = &var; \
160 target_size = sizeof(var); \
161 /* \
162 * Keep this buffer around to make sure we've got a \
163 * stack frame of SOME kind... \
164 */ \
165 memset(buf, (char)(sp && 0xff), sizeof(buf)); \
166 /* Fill variable with 0xFF. */ \
167 if (fill) { \
168 fill_start = &var; \
169 fill_size = sizeof(var); \
170 memset(fill_start, \
171 (char)((sp && 0xff) | forced_mask), \
172 fill_size); \
173 } \
174 \
175 /* Silence "never initialized" warnings. */ \
176 DO_NOTHING_CALL_ ## which(var, name); \
177 \
178 /* Exfiltrate "var". */ \
179 memcpy(check_buf, target_start, target_size); \
180 \
181 return (int)buf[0] | (int)buf[sizeof(buf) - 1]; \
182} \
183DEFINE_TEST_DRIVER(name, var_type, which)
184
185/* Structure with no padding. */
186struct test_packed {
187 unsigned long one;
188 unsigned long two;
189 unsigned long three;
190 unsigned long four;
191};
192
193/* Simple structure with padding likely to be covered by compiler. */
194struct test_small_hole {
195 size_t one;
196 char two;
197 /* 3 byte padding hole here. */
198 int three;
199 unsigned long four;
200};
201
202/* Try to trigger unhandled padding in a structure. */
203struct test_aligned {
204 u32 internal1;
205 u64 internal2;
206} __aligned(64);
207
208struct test_big_hole {
209 u8 one;
210 u8 two;
211 u8 three;
212 /* 61 byte padding hole here. */
213 struct test_aligned four;
214} __aligned(64);
215
216struct test_trailing_hole {
217 char *one;
218 char *two;
219 char *three;
220 char four;
221 /* "sizeof(unsigned long) - 1" byte padding hole here. */
222};
223
224/* Test if STRUCTLEAK is clearing structs with __user fields. */
225struct test_user {
226 u8 one;
227 unsigned long two;
228 char __user *three;
229 unsigned long four;
230};
231
232#define DEFINE_SCALAR_TEST(name, init) \
233 DEFINE_TEST(name ## _ ## init, name, SCALAR, init)
234
235#define DEFINE_SCALAR_TESTS(init) \
236 DEFINE_SCALAR_TEST(u8, init); \
237 DEFINE_SCALAR_TEST(u16, init); \
238 DEFINE_SCALAR_TEST(u32, init); \
239 DEFINE_SCALAR_TEST(u64, init); \
240 DEFINE_TEST(char_array_ ## init, unsigned char, STRING, init)
241
242#define DEFINE_STRUCT_TEST(name, init) \
243 DEFINE_TEST(name ## _ ## init, \
244 struct test_ ## name, STRUCT, init)
245
246#define DEFINE_STRUCT_TESTS(init) \
247 DEFINE_STRUCT_TEST(small_hole, init); \
248 DEFINE_STRUCT_TEST(big_hole, init); \
249 DEFINE_STRUCT_TEST(trailing_hole, init); \
250 DEFINE_STRUCT_TEST(packed, init)
251
252/* These should be fully initialized all the time! */
253DEFINE_SCALAR_TESTS(zero);
254DEFINE_STRUCT_TESTS(zero);
255/* Static initialization: padding may be left uninitialized. */
256DEFINE_STRUCT_TESTS(static_partial);
257DEFINE_STRUCT_TESTS(static_all);
258/* Dynamic initialization: padding may be left uninitialized. */
259DEFINE_STRUCT_TESTS(dynamic_partial);
260DEFINE_STRUCT_TESTS(dynamic_all);
261/* Runtime initialization: padding may be left uninitialized. */
262DEFINE_STRUCT_TESTS(runtime_partial);
263DEFINE_STRUCT_TESTS(runtime_all);
264/* No initialization without compiler instrumentation. */
265DEFINE_SCALAR_TESTS(none);
266DEFINE_STRUCT_TESTS(none);
267DEFINE_TEST(user, struct test_user, STRUCT, none);
268
269/*
270 * Check two uses through a variable declaration outside either path,
271 * which was noticed as a special case in porting earlier stack init
272 * compiler logic.
273 */
274static int noinline __leaf_switch_none(int path, bool fill)
275{
276 switch (path) {
277 uint64_t var;
278
279 case 1:
280 target_start = &var;
281 target_size = sizeof(var);
282 if (fill) {
283 fill_start = &var;
284 fill_size = sizeof(var);
285
286 memset(fill_start, forced_mask | 0x55, fill_size);
287 }
288 memcpy(check_buf, target_start, target_size);
289 break;
290 case 2:
291 target_start = &var;
292 target_size = sizeof(var);
293 if (fill) {
294 fill_start = &var;
295 fill_size = sizeof(var);
296
297 memset(fill_start, forced_mask | 0xaa, fill_size);
298 }
299 memcpy(check_buf, target_start, target_size);
300 break;
301 default:
302 var = 5;
303 return var & forced_mask;
304 }
305 return 0;
306}
307
308static noinline __init int leaf_switch_1_none(unsigned long sp, bool fill,
309 uint64_t *arg)
310{
311 return __leaf_switch_none(1, fill);
312}
313
314static noinline __init int leaf_switch_2_none(unsigned long sp, bool fill,
315 uint64_t *arg)
316{
317 return __leaf_switch_none(2, fill);
318}
319
320DEFINE_TEST_DRIVER(switch_1_none, uint64_t, SCALAR);
321DEFINE_TEST_DRIVER(switch_2_none, uint64_t, SCALAR);
322
323static int __init test_stackinit_init(void)
324{
325 unsigned int failures = 0;
326
327#define test_scalars(init) do { \
328 failures += test_u8_ ## init (); \
329 failures += test_u16_ ## init (); \
330 failures += test_u32_ ## init (); \
331 failures += test_u64_ ## init (); \
332 failures += test_char_array_ ## init (); \
333 } while (0)
334
335#define test_structs(init) do { \
336 failures += test_small_hole_ ## init (); \
337 failures += test_big_hole_ ## init (); \
338 failures += test_trailing_hole_ ## init (); \
339 failures += test_packed_ ## init (); \
340 } while (0)
341
342 /* These are explicitly initialized and should always pass. */
343 test_scalars(zero);
344 test_structs(zero);
345 /* Padding here appears to be accidentally always initialized? */
346 test_structs(dynamic_partial);
347 /* Padding initialization depends on compiler behaviors. */
348 test_structs(static_partial);
349 test_structs(static_all);
350 test_structs(dynamic_all);
351 test_structs(runtime_partial);
352 test_structs(runtime_all);
353
354 /* STRUCTLEAK_BYREF_ALL should cover everything from here down. */
355 test_scalars(none);
356 failures += test_switch_1_none();
357 failures += test_switch_2_none();
358
359 /* STRUCTLEAK_BYREF should cover from here down. */
360 test_structs(none);
361
362 /* STRUCTLEAK will only cover this. */
363 failures += test_user();
364
365 if (failures == 0)
366 pr_info("all tests passed!\n");
367 else
368 pr_err("failures: %u\n", failures);
369
370 return failures ? -EINVAL : 0;
371}
372module_init(test_stackinit_init);
373
374static void __exit test_stackinit_exit(void)
375{ }
376module_exit(test_stackinit_exit);
377
378MODULE_LICENSE("GPL");
diff --git a/lib/test_ubsan.c b/lib/test_ubsan.c
index 280f4979d00e..9ea10adf7a66 100644
--- a/lib/test_ubsan.c
+++ b/lib/test_ubsan.c
@@ -42,14 +42,6 @@ static void test_ubsan_divrem_overflow(void)
42 val /= val2; 42 val /= val2;
43} 43}
44 44
45static void test_ubsan_vla_bound_not_positive(void)
46{
47 volatile int size = -1;
48 char buf[size];
49
50 (void)buf;
51}
52
53static void test_ubsan_shift_out_of_bounds(void) 45static void test_ubsan_shift_out_of_bounds(void)
54{ 46{
55 volatile int val = -1; 47 volatile int val = -1;
@@ -61,7 +53,7 @@ static void test_ubsan_shift_out_of_bounds(void)
61static void test_ubsan_out_of_bounds(void) 53static void test_ubsan_out_of_bounds(void)
62{ 54{
63 volatile int i = 4, j = 5; 55 volatile int i = 4, j = 5;
64 volatile int arr[i]; 56 volatile int arr[4];
65 57
66 arr[j] = i; 58 arr[j] = i;
67} 59}
@@ -113,7 +105,6 @@ static const test_ubsan_fp test_ubsan_array[] = {
113 test_ubsan_mul_overflow, 105 test_ubsan_mul_overflow,
114 test_ubsan_negate_overflow, 106 test_ubsan_negate_overflow,
115 test_ubsan_divrem_overflow, 107 test_ubsan_divrem_overflow,
116 test_ubsan_vla_bound_not_positive,
117 test_ubsan_shift_out_of_bounds, 108 test_ubsan_shift_out_of_bounds,
118 test_ubsan_out_of_bounds, 109 test_ubsan_out_of_bounds,
119 test_ubsan_load_invalid_value, 110 test_ubsan_load_invalid_value,
diff --git a/lib/test_vmalloc.c b/lib/test_vmalloc.c
new file mode 100644
index 000000000000..83cdcaa82bf6
--- /dev/null
+++ b/lib/test_vmalloc.c
@@ -0,0 +1,551 @@
1// SPDX-License-Identifier: GPL-2.0
2
3/*
4 * Test module for stress and analyze performance of vmalloc allocator.
5 * (C) 2018 Uladzislau Rezki (Sony) <urezki@gmail.com>
6 */
7#include <linux/init.h>
8#include <linux/kernel.h>
9#include <linux/module.h>
10#include <linux/vmalloc.h>
11#include <linux/random.h>
12#include <linux/kthread.h>
13#include <linux/moduleparam.h>
14#include <linux/completion.h>
15#include <linux/delay.h>
16#include <linux/rwsem.h>
17#include <linux/mm.h>
18
19#define __param(type, name, init, msg) \
20 static type name = init; \
21 module_param(name, type, 0444); \
22 MODULE_PARM_DESC(name, msg) \
23
24__param(bool, single_cpu_test, false,
25 "Use single first online CPU to run tests");
26
27__param(bool, sequential_test_order, false,
28 "Use sequential stress tests order");
29
30__param(int, test_repeat_count, 1,
31 "Set test repeat counter");
32
33__param(int, test_loop_count, 1000000,
34 "Set test loop counter");
35
36__param(int, run_test_mask, INT_MAX,
37 "Set tests specified in the mask.\n\n"
38 "\t\tid: 1, name: fix_size_alloc_test\n"
39 "\t\tid: 2, name: full_fit_alloc_test\n"
40 "\t\tid: 4, name: long_busy_list_alloc_test\n"
41 "\t\tid: 8, name: random_size_alloc_test\n"
42 "\t\tid: 16, name: fix_align_alloc_test\n"
43 "\t\tid: 32, name: random_size_align_alloc_test\n"
44 "\t\tid: 64, name: align_shift_alloc_test\n"
45 "\t\tid: 128, name: pcpu_alloc_test\n"
46 /* Add a new test case description here. */
47);
48
49/*
50 * Depends on single_cpu_test parameter. If it is true, then
51 * use first online CPU to trigger a test on, otherwise go with
52 * all online CPUs.
53 */
54static cpumask_t cpus_run_test_mask = CPU_MASK_NONE;
55
56/*
57 * Read write semaphore for synchronization of setup
58 * phase that is done in main thread and workers.
59 */
60static DECLARE_RWSEM(prepare_for_test_rwsem);
61
62/*
63 * Completion tracking for worker threads.
64 */
65static DECLARE_COMPLETION(test_all_done_comp);
66static atomic_t test_n_undone = ATOMIC_INIT(0);
67
68static inline void
69test_report_one_done(void)
70{
71 if (atomic_dec_and_test(&test_n_undone))
72 complete(&test_all_done_comp);
73}
74
75static int random_size_align_alloc_test(void)
76{
77 unsigned long size, align, rnd;
78 void *ptr;
79 int i;
80
81 for (i = 0; i < test_loop_count; i++) {
82 get_random_bytes(&rnd, sizeof(rnd));
83
84 /*
85 * Maximum 1024 pages, if PAGE_SIZE is 4096.
86 */
87 align = 1 << (rnd % 23);
88
89 /*
90 * Maximum 10 pages.
91 */
92 size = ((rnd % 10) + 1) * PAGE_SIZE;
93
94 ptr = __vmalloc_node_range(size, align,
95 VMALLOC_START, VMALLOC_END,
96 GFP_KERNEL | __GFP_ZERO,
97 PAGE_KERNEL,
98 0, 0, __builtin_return_address(0));
99
100 if (!ptr)
101 return -1;
102
103 vfree(ptr);
104 }
105
106 return 0;
107}
108
109/*
110 * This test case is supposed to be failed.
111 */
112static int align_shift_alloc_test(void)
113{
114 unsigned long align;
115 void *ptr;
116 int i;
117
118 for (i = 0; i < BITS_PER_LONG; i++) {
119 align = ((unsigned long) 1) << i;
120
121 ptr = __vmalloc_node_range(PAGE_SIZE, align,
122 VMALLOC_START, VMALLOC_END,
123 GFP_KERNEL | __GFP_ZERO,
124 PAGE_KERNEL,
125 0, 0, __builtin_return_address(0));
126
127 if (!ptr)
128 return -1;
129
130 vfree(ptr);
131 }
132
133 return 0;
134}
135
136static int fix_align_alloc_test(void)
137{
138 void *ptr;
139 int i;
140
141 for (i = 0; i < test_loop_count; i++) {
142 ptr = __vmalloc_node_range(5 * PAGE_SIZE,
143 THREAD_ALIGN << 1,
144 VMALLOC_START, VMALLOC_END,
145 GFP_KERNEL | __GFP_ZERO,
146 PAGE_KERNEL,
147 0, 0, __builtin_return_address(0));
148
149 if (!ptr)
150 return -1;
151
152 vfree(ptr);
153 }
154
155 return 0;
156}
157
158static int random_size_alloc_test(void)
159{
160 unsigned int n;
161 void *p;
162 int i;
163
164 for (i = 0; i < test_loop_count; i++) {
165 get_random_bytes(&n, sizeof(i));
166 n = (n % 100) + 1;
167
168 p = vmalloc(n * PAGE_SIZE);
169
170 if (!p)
171 return -1;
172
173 *((__u8 *)p) = 1;
174 vfree(p);
175 }
176
177 return 0;
178}
179
180static int long_busy_list_alloc_test(void)
181{
182 void *ptr_1, *ptr_2;
183 void **ptr;
184 int rv = -1;
185 int i;
186
187 ptr = vmalloc(sizeof(void *) * 15000);
188 if (!ptr)
189 return rv;
190
191 for (i = 0; i < 15000; i++)
192 ptr[i] = vmalloc(1 * PAGE_SIZE);
193
194 for (i = 0; i < test_loop_count; i++) {
195 ptr_1 = vmalloc(100 * PAGE_SIZE);
196 if (!ptr_1)
197 goto leave;
198
199 ptr_2 = vmalloc(1 * PAGE_SIZE);
200 if (!ptr_2) {
201 vfree(ptr_1);
202 goto leave;
203 }
204
205 *((__u8 *)ptr_1) = 0;
206 *((__u8 *)ptr_2) = 1;
207
208 vfree(ptr_1);
209 vfree(ptr_2);
210 }
211
212 /* Success */
213 rv = 0;
214
215leave:
216 for (i = 0; i < 15000; i++)
217 vfree(ptr[i]);
218
219 vfree(ptr);
220 return rv;
221}
222
223static int full_fit_alloc_test(void)
224{
225 void **ptr, **junk_ptr, *tmp;
226 int junk_length;
227 int rv = -1;
228 int i;
229
230 junk_length = fls(num_online_cpus());
231 junk_length *= (32 * 1024 * 1024 / PAGE_SIZE);
232
233 ptr = vmalloc(sizeof(void *) * junk_length);
234 if (!ptr)
235 return rv;
236
237 junk_ptr = vmalloc(sizeof(void *) * junk_length);
238 if (!junk_ptr) {
239 vfree(ptr);
240 return rv;
241 }
242
243 for (i = 0; i < junk_length; i++) {
244 ptr[i] = vmalloc(1 * PAGE_SIZE);
245 junk_ptr[i] = vmalloc(1 * PAGE_SIZE);
246 }
247
248 for (i = 0; i < junk_length; i++)
249 vfree(junk_ptr[i]);
250
251 for (i = 0; i < test_loop_count; i++) {
252 tmp = vmalloc(1 * PAGE_SIZE);
253
254 if (!tmp)
255 goto error;
256
257 *((__u8 *)tmp) = 1;
258 vfree(tmp);
259 }
260
261 /* Success */
262 rv = 0;
263
264error:
265 for (i = 0; i < junk_length; i++)
266 vfree(ptr[i]);
267
268 vfree(ptr);
269 vfree(junk_ptr);
270
271 return rv;
272}
273
274static int fix_size_alloc_test(void)
275{
276 void *ptr;
277 int i;
278
279 for (i = 0; i < test_loop_count; i++) {
280 ptr = vmalloc(3 * PAGE_SIZE);
281
282 if (!ptr)
283 return -1;
284
285 *((__u8 *)ptr) = 0;
286
287 vfree(ptr);
288 }
289
290 return 0;
291}
292
293static int
294pcpu_alloc_test(void)
295{
296 int rv = 0;
297#ifndef CONFIG_NEED_PER_CPU_KM
298 void __percpu **pcpu;
299 size_t size, align;
300 int i;
301
302 pcpu = vmalloc(sizeof(void __percpu *) * 35000);
303 if (!pcpu)
304 return -1;
305
306 for (i = 0; i < 35000; i++) {
307 unsigned int r;
308
309 get_random_bytes(&r, sizeof(i));
310 size = (r % (PAGE_SIZE / 4)) + 1;
311
312 /*
313 * Maximum PAGE_SIZE
314 */
315 get_random_bytes(&r, sizeof(i));
316 align = 1 << ((i % 11) + 1);
317
318 pcpu[i] = __alloc_percpu(size, align);
319 if (!pcpu[i])
320 rv = -1;
321 }
322
323 for (i = 0; i < 35000; i++)
324 free_percpu(pcpu[i]);
325
326 vfree(pcpu);
327#endif
328 return rv;
329}
330
331struct test_case_desc {
332 const char *test_name;
333 int (*test_func)(void);
334};
335
336static struct test_case_desc test_case_array[] = {
337 { "fix_size_alloc_test", fix_size_alloc_test },
338 { "full_fit_alloc_test", full_fit_alloc_test },
339 { "long_busy_list_alloc_test", long_busy_list_alloc_test },
340 { "random_size_alloc_test", random_size_alloc_test },
341 { "fix_align_alloc_test", fix_align_alloc_test },
342 { "random_size_align_alloc_test", random_size_align_alloc_test },
343 { "align_shift_alloc_test", align_shift_alloc_test },
344 { "pcpu_alloc_test", pcpu_alloc_test },
345 /* Add a new test case here. */
346};
347
348struct test_case_data {
349 int test_failed;
350 int test_passed;
351 u64 time;
352};
353
354/* Split it to get rid of: WARNING: line over 80 characters */
355static struct test_case_data
356 per_cpu_test_data[NR_CPUS][ARRAY_SIZE(test_case_array)];
357
358static struct test_driver {
359 struct task_struct *task;
360 unsigned long start;
361 unsigned long stop;
362 int cpu;
363} per_cpu_test_driver[NR_CPUS];
364
365static void shuffle_array(int *arr, int n)
366{
367 unsigned int rnd;
368 int i, j, x;
369
370 for (i = n - 1; i > 0; i--) {
371 get_random_bytes(&rnd, sizeof(rnd));
372
373 /* Cut the range. */
374 j = rnd % i;
375
376 /* Swap indexes. */
377 x = arr[i];
378 arr[i] = arr[j];
379 arr[j] = x;
380 }
381}
382
383static int test_func(void *private)
384{
385 struct test_driver *t = private;
386 cpumask_t newmask = CPU_MASK_NONE;
387 int random_array[ARRAY_SIZE(test_case_array)];
388 int index, i, j, ret;
389 ktime_t kt;
390 u64 delta;
391
392 cpumask_set_cpu(t->cpu, &newmask);
393 set_cpus_allowed_ptr(current, &newmask);
394
395 for (i = 0; i < ARRAY_SIZE(test_case_array); i++)
396 random_array[i] = i;
397
398 if (!sequential_test_order)
399 shuffle_array(random_array, ARRAY_SIZE(test_case_array));
400
401 /*
402 * Block until initialization is done.
403 */
404 down_read(&prepare_for_test_rwsem);
405
406 t->start = get_cycles();
407 for (i = 0; i < ARRAY_SIZE(test_case_array); i++) {
408 index = random_array[i];
409
410 /*
411 * Skip tests if run_test_mask has been specified.
412 */
413 if (!((run_test_mask & (1 << index)) >> index))
414 continue;
415
416 kt = ktime_get();
417 for (j = 0; j < test_repeat_count; j++) {
418 ret = test_case_array[index].test_func();
419 if (!ret)
420 per_cpu_test_data[t->cpu][index].test_passed++;
421 else
422 per_cpu_test_data[t->cpu][index].test_failed++;
423 }
424
425 /*
426 * Take an average time that test took.
427 */
428 delta = (u64) ktime_us_delta(ktime_get(), kt);
429 do_div(delta, (u32) test_repeat_count);
430
431 per_cpu_test_data[t->cpu][index].time = delta;
432 }
433 t->stop = get_cycles();
434
435 up_read(&prepare_for_test_rwsem);
436 test_report_one_done();
437
438 /*
439 * Wait for the kthread_stop() call.
440 */
441 while (!kthread_should_stop())
442 msleep(10);
443
444 return 0;
445}
446
447static void
448init_test_configurtion(void)
449{
450 /*
451 * Reset all data of all CPUs.
452 */
453 memset(per_cpu_test_data, 0, sizeof(per_cpu_test_data));
454
455 if (single_cpu_test)
456 cpumask_set_cpu(cpumask_first(cpu_online_mask),
457 &cpus_run_test_mask);
458 else
459 cpumask_and(&cpus_run_test_mask, cpu_online_mask,
460 cpu_online_mask);
461
462 if (test_repeat_count <= 0)
463 test_repeat_count = 1;
464
465 if (test_loop_count <= 0)
466 test_loop_count = 1;
467}
468
469static void do_concurrent_test(void)
470{
471 int cpu, ret;
472
473 /*
474 * Set some basic configurations plus sanity check.
475 */
476 init_test_configurtion();
477
478 /*
479 * Put on hold all workers.
480 */
481 down_write(&prepare_for_test_rwsem);
482
483 for_each_cpu(cpu, &cpus_run_test_mask) {
484 struct test_driver *t = &per_cpu_test_driver[cpu];
485
486 t->cpu = cpu;
487 t->task = kthread_run(test_func, t, "vmalloc_test/%d", cpu);
488
489 if (!IS_ERR(t->task))
490 /* Success. */
491 atomic_inc(&test_n_undone);
492 else
493 pr_err("Failed to start kthread for %d CPU\n", cpu);
494 }
495
496 /*
497 * Now let the workers do their job.
498 */
499 up_write(&prepare_for_test_rwsem);
500
501 /*
502 * Sleep quiet until all workers are done with 1 second
503 * interval. Since the test can take a lot of time we
504 * can run into a stack trace of the hung task. That is
505 * why we go with completion_timeout and HZ value.
506 */
507 do {
508 ret = wait_for_completion_timeout(&test_all_done_comp, HZ);
509 } while (!ret);
510
511 for_each_cpu(cpu, &cpus_run_test_mask) {
512 struct test_driver *t = &per_cpu_test_driver[cpu];
513 int i;
514
515 if (!IS_ERR(t->task))
516 kthread_stop(t->task);
517
518 for (i = 0; i < ARRAY_SIZE(test_case_array); i++) {
519 if (!((run_test_mask & (1 << i)) >> i))
520 continue;
521
522 pr_info(
523 "Summary: %s passed: %d failed: %d repeat: %d loops: %d avg: %llu usec\n",
524 test_case_array[i].test_name,
525 per_cpu_test_data[cpu][i].test_passed,
526 per_cpu_test_data[cpu][i].test_failed,
527 test_repeat_count, test_loop_count,
528 per_cpu_test_data[cpu][i].time);
529 }
530
531 pr_info("All test took CPU%d=%lu cycles\n",
532 cpu, t->stop - t->start);
533 }
534}
535
536static int vmalloc_test_init(void)
537{
538 do_concurrent_test();
539 return -EAGAIN; /* Fail will directly unload the module */
540}
541
542static void vmalloc_test_exit(void)
543{
544}
545
546module_init(vmalloc_test_init)
547module_exit(vmalloc_test_exit)
548
549MODULE_LICENSE("GPL");
550MODULE_AUTHOR("Uladzislau Rezki");
551MODULE_DESCRIPTION("vmalloc test module");
diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index 4676c0a1eeca..5d4bad8bd96a 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -40,9 +40,9 @@ static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)
40 40
41static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp) 41static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)
42{ 42{
43 u32 id = 0; 43 u32 id;
44 44
45 XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_index(index), 45 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(index), xa_limit_32b,
46 gfp) != 0); 46 gfp) != 0);
47 XA_BUG_ON(xa, id != index); 47 XA_BUG_ON(xa, id != index);
48} 48}
@@ -107,8 +107,11 @@ static noinline void check_xas_retry(struct xarray *xa)
107 XA_BUG_ON(xa, xas.xa_node != XAS_RESTART); 107 XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
108 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0)); 108 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
109 XA_BUG_ON(xa, xas.xa_node != NULL); 109 XA_BUG_ON(xa, xas.xa_node != NULL);
110 rcu_read_unlock();
110 111
111 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL); 112 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
113
114 rcu_read_lock();
112 XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas))); 115 XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
113 xas.xa_node = XAS_RESTART; 116 xas.xa_node = XAS_RESTART;
114 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0)); 117 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
@@ -199,7 +202,7 @@ static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
199 XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL)); 202 XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));
200 xa_set_mark(xa, index + 1, XA_MARK_0); 203 xa_set_mark(xa, index + 1, XA_MARK_0);
201 XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL)); 204 XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));
202 xa_set_mark(xa, index + 2, XA_MARK_1); 205 xa_set_mark(xa, index + 2, XA_MARK_2);
203 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL)); 206 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));
204 xa_store_order(xa, index, order, xa_mk_index(index), 207 xa_store_order(xa, index, order, xa_mk_index(index),
205 GFP_KERNEL); 208 GFP_KERNEL);
@@ -209,8 +212,8 @@ static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
209 void *entry; 212 void *entry;
210 213
211 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0)); 214 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
212 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_1)); 215 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1));
213 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_2)); 216 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2));
214 217
215 /* We should see two elements in the array */ 218 /* We should see two elements in the array */
216 rcu_read_lock(); 219 rcu_read_lock();
@@ -343,7 +346,7 @@ static noinline void check_cmpxchg(struct xarray *xa)
343 346
344 XA_BUG_ON(xa, !xa_empty(xa)); 347 XA_BUG_ON(xa, !xa_empty(xa));
345 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL); 348 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);
346 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EEXIST); 349 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EBUSY);
347 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS); 350 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);
348 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS); 351 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);
349 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE); 352 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);
@@ -357,45 +360,66 @@ static noinline void check_cmpxchg(struct xarray *xa)
357static noinline void check_reserve(struct xarray *xa) 360static noinline void check_reserve(struct xarray *xa)
358{ 361{
359 void *entry; 362 void *entry;
360 unsigned long index = 0; 363 unsigned long index;
364 int count;
361 365
362 /* An array with a reserved entry is not empty */ 366 /* An array with a reserved entry is not empty */
363 XA_BUG_ON(xa, !xa_empty(xa)); 367 XA_BUG_ON(xa, !xa_empty(xa));
364 xa_reserve(xa, 12345678, GFP_KERNEL); 368 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
365 XA_BUG_ON(xa, xa_empty(xa)); 369 XA_BUG_ON(xa, xa_empty(xa));
366 XA_BUG_ON(xa, xa_load(xa, 12345678)); 370 XA_BUG_ON(xa, xa_load(xa, 12345678));
367 xa_release(xa, 12345678); 371 xa_release(xa, 12345678);
368 XA_BUG_ON(xa, !xa_empty(xa)); 372 XA_BUG_ON(xa, !xa_empty(xa));
369 373
370 /* Releasing a used entry does nothing */ 374 /* Releasing a used entry does nothing */
371 xa_reserve(xa, 12345678, GFP_KERNEL); 375 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
372 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL); 376 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
373 xa_release(xa, 12345678); 377 xa_release(xa, 12345678);
374 xa_erase_index(xa, 12345678); 378 xa_erase_index(xa, 12345678);
375 XA_BUG_ON(xa, !xa_empty(xa)); 379 XA_BUG_ON(xa, !xa_empty(xa));
376 380
377 /* cmpxchg sees a reserved entry as NULL */ 381 /* cmpxchg sees a reserved entry as ZERO */
378 xa_reserve(xa, 12345678, GFP_KERNEL); 382 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
379 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, NULL, xa_mk_value(12345678), 383 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,
380 GFP_NOWAIT) != NULL); 384 xa_mk_value(12345678), GFP_NOWAIT) != NULL);
381 xa_release(xa, 12345678); 385 xa_release(xa, 12345678);
382 xa_erase_index(xa, 12345678); 386 xa_erase_index(xa, 12345678);
383 XA_BUG_ON(xa, !xa_empty(xa)); 387 XA_BUG_ON(xa, !xa_empty(xa));
384 388
385 /* And so does xa_insert */ 389 /* xa_insert treats it as busy */
386 xa_reserve(xa, 12345678, GFP_KERNEL); 390 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
387 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) != 0); 391 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=
388 xa_erase_index(xa, 12345678); 392 -EBUSY);
393 XA_BUG_ON(xa, xa_empty(xa));
394 XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);
389 XA_BUG_ON(xa, !xa_empty(xa)); 395 XA_BUG_ON(xa, !xa_empty(xa));
390 396
391 /* Can iterate through a reserved entry */ 397 /* Can iterate through a reserved entry */
392 xa_store_index(xa, 5, GFP_KERNEL); 398 xa_store_index(xa, 5, GFP_KERNEL);
393 xa_reserve(xa, 6, GFP_KERNEL); 399 XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);
394 xa_store_index(xa, 7, GFP_KERNEL); 400 xa_store_index(xa, 7, GFP_KERNEL);
395 401
396 xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 402 count = 0;
403 xa_for_each(xa, index, entry) {
397 XA_BUG_ON(xa, index != 5 && index != 7); 404 XA_BUG_ON(xa, index != 5 && index != 7);
405 count++;
398 } 406 }
407 XA_BUG_ON(xa, count != 2);
408
409 /* If we free a reserved entry, we should be able to allocate it */
410 if (xa->xa_flags & XA_FLAGS_ALLOC) {
411 u32 id;
412
413 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),
414 XA_LIMIT(5, 10), GFP_KERNEL) != 0);
415 XA_BUG_ON(xa, id != 8);
416
417 xa_release(xa, 6);
418 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),
419 XA_LIMIT(5, 10), GFP_KERNEL) != 0);
420 XA_BUG_ON(xa, id != 6);
421 }
422
399 xa_destroy(xa); 423 xa_destroy(xa);
400} 424}
401 425
@@ -584,64 +608,194 @@ static noinline void check_multi_store(struct xarray *xa)
584#endif 608#endif
585} 609}
586 610
587static DEFINE_XARRAY_ALLOC(xa0); 611static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base)
588
589static noinline void check_xa_alloc(void)
590{ 612{
591 int i; 613 int i;
592 u32 id; 614 u32 id;
593 615
594 /* An empty array should assign 0 to the first alloc */ 616 XA_BUG_ON(xa, !xa_empty(xa));
595 xa_alloc_index(&xa0, 0, GFP_KERNEL); 617 /* An empty array should assign %base to the first alloc */
618 xa_alloc_index(xa, base, GFP_KERNEL);
596 619
597 /* Erasing it should make the array empty again */ 620 /* Erasing it should make the array empty again */
598 xa_erase_index(&xa0, 0); 621 xa_erase_index(xa, base);
599 XA_BUG_ON(&xa0, !xa_empty(&xa0)); 622 XA_BUG_ON(xa, !xa_empty(xa));
600 623
601 /* And it should assign 0 again */ 624 /* And it should assign %base again */
602 xa_alloc_index(&xa0, 0, GFP_KERNEL); 625 xa_alloc_index(xa, base, GFP_KERNEL);
603 626
604 /* The next assigned ID should be 1 */ 627 /* Allocating and then erasing a lot should not lose base */
605 xa_alloc_index(&xa0, 1, GFP_KERNEL); 628 for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)
606 xa_erase_index(&xa0, 1); 629 xa_alloc_index(xa, i, GFP_KERNEL);
630 for (i = base; i < 2 * XA_CHUNK_SIZE; i++)
631 xa_erase_index(xa, i);
632 xa_alloc_index(xa, base, GFP_KERNEL);
633
634 /* Destroying the array should do the same as erasing */
635 xa_destroy(xa);
636
637 /* And it should assign %base again */
638 xa_alloc_index(xa, base, GFP_KERNEL);
639
640 /* The next assigned ID should be base+1 */
641 xa_alloc_index(xa, base + 1, GFP_KERNEL);
642 xa_erase_index(xa, base + 1);
607 643
608 /* Storing a value should mark it used */ 644 /* Storing a value should mark it used */
609 xa_store_index(&xa0, 1, GFP_KERNEL); 645 xa_store_index(xa, base + 1, GFP_KERNEL);
610 xa_alloc_index(&xa0, 2, GFP_KERNEL); 646 xa_alloc_index(xa, base + 2, GFP_KERNEL);
611 647
612 /* If we then erase 0, it should be free */ 648 /* If we then erase base, it should be free */
613 xa_erase_index(&xa0, 0); 649 xa_erase_index(xa, base);
614 xa_alloc_index(&xa0, 0, GFP_KERNEL); 650 xa_alloc_index(xa, base, GFP_KERNEL);
615 651
616 xa_erase_index(&xa0, 1); 652 xa_erase_index(xa, base + 1);
617 xa_erase_index(&xa0, 2); 653 xa_erase_index(xa, base + 2);
618 654
619 for (i = 1; i < 5000; i++) { 655 for (i = 1; i < 5000; i++) {
620 xa_alloc_index(&xa0, i, GFP_KERNEL); 656 xa_alloc_index(xa, base + i, GFP_KERNEL);
621 } 657 }
622 658
623 xa_destroy(&xa0); 659 xa_destroy(xa);
624 660
625 id = 0xfffffffeU; 661 /* Check that we fail properly at the limit of allocation */
626 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_index(id), 662 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),
663 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
627 GFP_KERNEL) != 0); 664 GFP_KERNEL) != 0);
628 XA_BUG_ON(&xa0, id != 0xfffffffeU); 665 XA_BUG_ON(xa, id != 0xfffffffeU);
629 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_index(id), 666 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),
667 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
630 GFP_KERNEL) != 0); 668 GFP_KERNEL) != 0);
631 XA_BUG_ON(&xa0, id != 0xffffffffU); 669 XA_BUG_ON(xa, id != 0xffffffffU);
632 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_index(id), 670 id = 3;
633 GFP_KERNEL) != -ENOSPC); 671 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),
634 XA_BUG_ON(&xa0, id != 0xffffffffU); 672 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
635 xa_destroy(&xa0); 673 GFP_KERNEL) != -EBUSY);
636 674 XA_BUG_ON(xa, id != 3);
637 id = 10; 675 xa_destroy(xa);
638 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, 5, xa_mk_index(id), 676
639 GFP_KERNEL) != -ENOSPC); 677 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
640 XA_BUG_ON(&xa0, xa_store_index(&xa0, 3, GFP_KERNEL) != 0); 678 GFP_KERNEL) != -EBUSY);
641 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, 5, xa_mk_index(id), 679 XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);
642 GFP_KERNEL) != -ENOSPC); 680 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
643 xa_erase_index(&xa0, 3); 681 GFP_KERNEL) != -EBUSY);
644 XA_BUG_ON(&xa0, !xa_empty(&xa0)); 682 xa_erase_index(xa, 3);
683 XA_BUG_ON(xa, !xa_empty(xa));
684}
685
686static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)
687{
688 unsigned int i, id;
689 unsigned long index;
690 void *entry;
691
692 /* Allocate and free a NULL and check xa_empty() behaves */
693 XA_BUG_ON(xa, !xa_empty(xa));
694 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
695 XA_BUG_ON(xa, id != base);
696 XA_BUG_ON(xa, xa_empty(xa));
697 XA_BUG_ON(xa, xa_erase(xa, id) != NULL);
698 XA_BUG_ON(xa, !xa_empty(xa));
699
700 /* Ditto, but check destroy instead of erase */
701 XA_BUG_ON(xa, !xa_empty(xa));
702 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
703 XA_BUG_ON(xa, id != base);
704 XA_BUG_ON(xa, xa_empty(xa));
705 xa_destroy(xa);
706 XA_BUG_ON(xa, !xa_empty(xa));
707
708 for (i = base; i < base + 10; i++) {
709 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,
710 GFP_KERNEL) != 0);
711 XA_BUG_ON(xa, id != i);
712 }
713
714 XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);
715 XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);
716 XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));
717 XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);
718 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
719 XA_BUG_ON(xa, id != 5);
720
721 xa_for_each(xa, index, entry) {
722 xa_erase_index(xa, index);
723 }
724
725 for (i = base; i < base + 9; i++) {
726 XA_BUG_ON(xa, xa_erase(xa, i) != NULL);
727 XA_BUG_ON(xa, xa_empty(xa));
728 }
729 XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);
730 XA_BUG_ON(xa, xa_empty(xa));
731 XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);
732 XA_BUG_ON(xa, !xa_empty(xa));
733
734 xa_destroy(xa);
735}
736
737static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)
738{
739 struct xa_limit limit = XA_LIMIT(1, 0x3fff);
740 u32 next = 0;
741 unsigned int i, id;
742 unsigned long index;
743 void *entry;
744
745 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,
746 &next, GFP_KERNEL) != 0);
747 XA_BUG_ON(xa, id != 1);
748
749 next = 0x3ffd;
750 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,
751 &next, GFP_KERNEL) != 0);
752 XA_BUG_ON(xa, id != 0x3ffd);
753 xa_erase_index(xa, 0x3ffd);
754 xa_erase_index(xa, 1);
755 XA_BUG_ON(xa, !xa_empty(xa));
756
757 for (i = 0x3ffe; i < 0x4003; i++) {
758 if (i < 0x4000)
759 entry = xa_mk_index(i);
760 else
761 entry = xa_mk_index(i - 0x3fff);
762 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,
763 &next, GFP_KERNEL) != (id == 1));
764 XA_BUG_ON(xa, xa_mk_index(id) != entry);
765 }
766
767 /* Check wrap-around is handled correctly */
768 if (base != 0)
769 xa_erase_index(xa, base);
770 xa_erase_index(xa, base + 1);
771 next = UINT_MAX;
772 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),
773 xa_limit_32b, &next, GFP_KERNEL) != 0);
774 XA_BUG_ON(xa, id != UINT_MAX);
775 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),
776 xa_limit_32b, &next, GFP_KERNEL) != 1);
777 XA_BUG_ON(xa, id != base);
778 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),
779 xa_limit_32b, &next, GFP_KERNEL) != 0);
780 XA_BUG_ON(xa, id != base + 1);
781
782 xa_for_each(xa, index, entry)
783 xa_erase_index(xa, index);
784
785 XA_BUG_ON(xa, !xa_empty(xa));
786}
787
788static DEFINE_XARRAY_ALLOC(xa0);
789static DEFINE_XARRAY_ALLOC1(xa1);
790
791static noinline void check_xa_alloc(void)
792{
793 check_xa_alloc_1(&xa0, 0);
794 check_xa_alloc_1(&xa1, 1);
795 check_xa_alloc_2(&xa0, 0);
796 check_xa_alloc_2(&xa1, 1);
797 check_xa_alloc_3(&xa0, 0);
798 check_xa_alloc_3(&xa1, 1);
645} 799}
646 800
647static noinline void __check_store_iter(struct xarray *xa, unsigned long start, 801static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
@@ -812,17 +966,16 @@ static noinline void check_find_1(struct xarray *xa)
812static noinline void check_find_2(struct xarray *xa) 966static noinline void check_find_2(struct xarray *xa)
813{ 967{
814 void *entry; 968 void *entry;
815 unsigned long i, j, index = 0; 969 unsigned long i, j, index;
816 970
817 xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 971 xa_for_each(xa, index, entry) {
818 XA_BUG_ON(xa, true); 972 XA_BUG_ON(xa, true);
819 } 973 }
820 974
821 for (i = 0; i < 1024; i++) { 975 for (i = 0; i < 1024; i++) {
822 xa_store_index(xa, index, GFP_KERNEL); 976 xa_store_index(xa, index, GFP_KERNEL);
823 j = 0; 977 j = 0;
824 index = 0; 978 xa_for_each(xa, index, entry) {
825 xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) {
826 XA_BUG_ON(xa, xa_mk_index(index) != entry); 979 XA_BUG_ON(xa, xa_mk_index(index) != entry);
827 XA_BUG_ON(xa, index != j++); 980 XA_BUG_ON(xa, index != j++);
828 } 981 }
@@ -839,6 +992,7 @@ static noinline void check_find_3(struct xarray *xa)
839 992
840 for (i = 0; i < 100; i++) { 993 for (i = 0; i < 100; i++) {
841 for (j = 0; j < 100; j++) { 994 for (j = 0; j < 100; j++) {
995 rcu_read_lock();
842 for (k = 0; k < 100; k++) { 996 for (k = 0; k < 100; k++) {
843 xas_set(&xas, j); 997 xas_set(&xas, j);
844 xas_for_each_marked(&xas, entry, k, XA_MARK_0) 998 xas_for_each_marked(&xas, entry, k, XA_MARK_0)
@@ -847,6 +1001,7 @@ static noinline void check_find_3(struct xarray *xa)
847 XA_BUG_ON(xa, 1001 XA_BUG_ON(xa,
848 xas.xa_node != XAS_RESTART); 1002 xas.xa_node != XAS_RESTART);
849 } 1003 }
1004 rcu_read_unlock();
850 } 1005 }
851 xa_store_index(xa, i, GFP_KERNEL); 1006 xa_store_index(xa, i, GFP_KERNEL);
852 xa_set_mark(xa, i, XA_MARK_0); 1007 xa_set_mark(xa, i, XA_MARK_0);
@@ -1183,6 +1338,58 @@ static noinline void check_store_range(struct xarray *xa)
1183 } 1338 }
1184} 1339}
1185 1340
1341static void check_align_1(struct xarray *xa, char *name)
1342{
1343 int i;
1344 unsigned int id;
1345 unsigned long index;
1346 void *entry;
1347
1348 for (i = 0; i < 8; i++) {
1349 XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,
1350 GFP_KERNEL) != 0);
1351 XA_BUG_ON(xa, id != i);
1352 }
1353 xa_for_each(xa, index, entry)
1354 XA_BUG_ON(xa, xa_is_err(entry));
1355 xa_destroy(xa);
1356}
1357
1358/*
1359 * We should always be able to store without allocating memory after
1360 * reserving a slot.
1361 */
1362static void check_align_2(struct xarray *xa, char *name)
1363{
1364 int i;
1365
1366 XA_BUG_ON(xa, !xa_empty(xa));
1367
1368 for (i = 0; i < 8; i++) {
1369 XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);
1370 xa_erase(xa, 0);
1371 }
1372
1373 for (i = 0; i < 8; i++) {
1374 XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);
1375 XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);
1376 xa_erase(xa, 0);
1377 }
1378
1379 XA_BUG_ON(xa, !xa_empty(xa));
1380}
1381
1382static noinline void check_align(struct xarray *xa)
1383{
1384 char name[] = "Motorola 68000";
1385
1386 check_align_1(xa, name);
1387 check_align_1(xa, name + 1);
1388 check_align_1(xa, name + 2);
1389 check_align_1(xa, name + 3);
1390 check_align_2(xa, name);
1391}
1392
1186static LIST_HEAD(shadow_nodes); 1393static LIST_HEAD(shadow_nodes);
1187 1394
1188static void test_update_node(struct xa_node *node) 1395static void test_update_node(struct xa_node *node)
@@ -1322,6 +1529,7 @@ static int xarray_checks(void)
1322 check_xas_erase(&array); 1529 check_xas_erase(&array);
1323 check_cmpxchg(&array); 1530 check_cmpxchg(&array);
1324 check_reserve(&array); 1531 check_reserve(&array);
1532 check_reserve(&xa0);
1325 check_multi_store(&array); 1533 check_multi_store(&array);
1326 check_xa_alloc(); 1534 check_xa_alloc();
1327 check_find(&array); 1535 check_find(&array);
@@ -1332,6 +1540,7 @@ static int xarray_checks(void)
1332 check_create_range(&array); 1540 check_create_range(&array);
1333 check_store_range(&array); 1541 check_store_range(&array);
1334 check_store_iter(&array); 1542 check_store_iter(&array);
1543 check_align(&xa0);
1335 1544
1336 check_workingset(&array, 0); 1545 check_workingset(&array, 0);
1337 check_workingset(&array, 64); 1546 check_workingset(&array, 64);
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 3add92329bae..791b6fa36905 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -17,6 +17,7 @@
17 */ 17 */
18 18
19#include <stdarg.h> 19#include <stdarg.h>
20#include <linux/build_bug.h>
20#include <linux/clk.h> 21#include <linux/clk.h>
21#include <linux/clk-provider.h> 22#include <linux/clk-provider.h>
22#include <linux/module.h> /* for KSYM_SYMBOL_LEN */ 23#include <linux/module.h> /* for KSYM_SYMBOL_LEN */
@@ -405,6 +406,8 @@ struct printf_spec {
405 unsigned int base:8; /* number base, 8, 10 or 16 only */ 406 unsigned int base:8; /* number base, 8, 10 or 16 only */
406 signed int precision:16; /* # of digits/chars */ 407 signed int precision:16; /* # of digits/chars */
407} __packed; 408} __packed;
409static_assert(sizeof(struct printf_spec) == 8);
410
408#define FIELD_WIDTH_MAX ((1 << 23) - 1) 411#define FIELD_WIDTH_MAX ((1 << 23) - 1)
409#define PRECISION_MAX ((1 << 15) - 1) 412#define PRECISION_MAX ((1 << 15) - 1)
410 413
@@ -422,8 +425,6 @@ char *number(char *buf, char *end, unsigned long long num,
422 int field_width = spec.field_width; 425 int field_width = spec.field_width;
423 int precision = spec.precision; 426 int precision = spec.precision;
424 427
425 BUILD_BUG_ON(sizeof(struct printf_spec) != 8);
426
427 /* locase = 0 or 0x20. ORing digits or letters with 'locase' 428 /* locase = 0 or 0x20. ORing digits or letters with 'locase'
428 * produces same digits or (maybe lowercased) letters */ 429 * produces same digits or (maybe lowercased) letters */
429 locase = (spec.flags & SMALL); 430 locase = (spec.flags & SMALL);
@@ -1930,7 +1931,6 @@ char *device_node_string(char *buf, char *end, struct device_node *dn,
1930 * (legacy clock framework) of the clock 1931 * (legacy clock framework) of the clock
1931 * - 'Cn' For a clock, it prints the name (Common Clock Framework) or address 1932 * - 'Cn' For a clock, it prints the name (Common Clock Framework) or address
1932 * (legacy clock framework) of the clock 1933 * (legacy clock framework) of the clock
1933 * - 'Cr' For a clock, it prints the current rate of the clock
1934 * - 'G' For flags to be printed as a collection of symbolic strings that would 1934 * - 'G' For flags to be printed as a collection of symbolic strings that would
1935 * construct the specific value. Supported flags given by option: 1935 * construct the specific value. Supported flags given by option:
1936 * p page flags (see struct page) given as pointer to unsigned long 1936 * p page flags (see struct page) given as pointer to unsigned long
diff --git a/lib/xarray.c b/lib/xarray.c
index 5f3f9311de89..6be3acbb861f 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -57,6 +57,11 @@ static inline bool xa_track_free(const struct xarray *xa)
57 return xa->xa_flags & XA_FLAGS_TRACK_FREE; 57 return xa->xa_flags & XA_FLAGS_TRACK_FREE;
58} 58}
59 59
60static inline bool xa_zero_busy(const struct xarray *xa)
61{
62 return xa->xa_flags & XA_FLAGS_ZERO_BUSY;
63}
64
60static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark) 65static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
61{ 66{
62 if (!(xa->xa_flags & XA_FLAGS_MARK(mark))) 67 if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
@@ -232,6 +237,8 @@ void *xas_load(struct xa_state *xas)
232 if (xas->xa_shift > node->shift) 237 if (xas->xa_shift > node->shift)
233 break; 238 break;
234 entry = xas_descend(xas, node); 239 entry = xas_descend(xas, node);
240 if (node->shift == 0)
241 break;
235 } 242 }
236 return entry; 243 return entry;
237} 244}
@@ -430,6 +437,8 @@ static void xas_shrink(struct xa_state *xas)
430 break; 437 break;
431 if (!xa_is_node(entry) && node->shift) 438 if (!xa_is_node(entry) && node->shift)
432 break; 439 break;
440 if (xa_is_zero(entry) && xa_zero_busy(xa))
441 entry = NULL;
433 xas->xa_node = XAS_BOUNDS; 442 xas->xa_node = XAS_BOUNDS;
434 443
435 RCU_INIT_POINTER(xa->xa_head, entry); 444 RCU_INIT_POINTER(xa->xa_head, entry);
@@ -506,7 +515,7 @@ static void xas_free_nodes(struct xa_state *xas, struct xa_node *top)
506 for (;;) { 515 for (;;) {
507 void *entry = xa_entry_locked(xas->xa, node, offset); 516 void *entry = xa_entry_locked(xas->xa, node, offset);
508 517
509 if (xa_is_node(entry)) { 518 if (node->shift && xa_is_node(entry)) {
510 node = xa_to_node(entry); 519 node = xa_to_node(entry);
511 offset = 0; 520 offset = 0;
512 continue; 521 continue;
@@ -604,6 +613,7 @@ static int xas_expand(struct xa_state *xas, void *head)
604/* 613/*
605 * xas_create() - Create a slot to store an entry in. 614 * xas_create() - Create a slot to store an entry in.
606 * @xas: XArray operation state. 615 * @xas: XArray operation state.
616 * @allow_root: %true if we can store the entry in the root directly
607 * 617 *
608 * Most users will not need to call this function directly, as it is called 618 * Most users will not need to call this function directly, as it is called
609 * by xas_store(). It is useful for doing conditional store operations 619 * by xas_store(). It is useful for doing conditional store operations
@@ -613,7 +623,7 @@ static int xas_expand(struct xa_state *xas, void *head)
613 * If the slot was newly created, returns %NULL. If it failed to create the 623 * If the slot was newly created, returns %NULL. If it failed to create the
614 * slot, returns %NULL and indicates the error in @xas. 624 * slot, returns %NULL and indicates the error in @xas.
615 */ 625 */
616static void *xas_create(struct xa_state *xas) 626static void *xas_create(struct xa_state *xas, bool allow_root)
617{ 627{
618 struct xarray *xa = xas->xa; 628 struct xarray *xa = xas->xa;
619 void *entry; 629 void *entry;
@@ -625,9 +635,13 @@ static void *xas_create(struct xa_state *xas)
625 if (xas_top(node)) { 635 if (xas_top(node)) {
626 entry = xa_head_locked(xa); 636 entry = xa_head_locked(xa);
627 xas->xa_node = NULL; 637 xas->xa_node = NULL;
638 if (!entry && xa_zero_busy(xa))
639 entry = XA_ZERO_ENTRY;
628 shift = xas_expand(xas, entry); 640 shift = xas_expand(xas, entry);
629 if (shift < 0) 641 if (shift < 0)
630 return NULL; 642 return NULL;
643 if (!shift && !allow_root)
644 shift = XA_CHUNK_SHIFT;
631 entry = xa_head_locked(xa); 645 entry = xa_head_locked(xa);
632 slot = &xa->xa_head; 646 slot = &xa->xa_head;
633 } else if (xas_error(xas)) { 647 } else if (xas_error(xas)) {
@@ -687,7 +701,7 @@ void xas_create_range(struct xa_state *xas)
687 xas->xa_sibs = 0; 701 xas->xa_sibs = 0;
688 702
689 for (;;) { 703 for (;;) {
690 xas_create(xas); 704 xas_create(xas, true);
691 if (xas_error(xas)) 705 if (xas_error(xas))
692 goto restore; 706 goto restore;
693 if (xas->xa_index <= (index | XA_CHUNK_MASK)) 707 if (xas->xa_index <= (index | XA_CHUNK_MASK))
@@ -753,10 +767,12 @@ void *xas_store(struct xa_state *xas, void *entry)
753 void *first, *next; 767 void *first, *next;
754 bool value = xa_is_value(entry); 768 bool value = xa_is_value(entry);
755 769
756 if (entry) 770 if (entry) {
757 first = xas_create(xas); 771 bool allow_root = !xa_is_node(entry) && !xa_is_zero(entry);
758 else 772 first = xas_create(xas, allow_root);
773 } else {
759 first = xas_load(xas); 774 first = xas_load(xas);
775 }
760 776
761 if (xas_invalid(xas)) 777 if (xas_invalid(xas))
762 return first; 778 return first;
@@ -786,7 +802,7 @@ void *xas_store(struct xa_state *xas, void *entry)
786 * entry is set to NULL. 802 * entry is set to NULL.
787 */ 803 */
788 rcu_assign_pointer(*slot, entry); 804 rcu_assign_pointer(*slot, entry);
789 if (xa_is_node(next)) 805 if (xa_is_node(next) && (!node || node->shift))
790 xas_free_nodes(xas, xa_to_node(next)); 806 xas_free_nodes(xas, xa_to_node(next));
791 if (!node) 807 if (!node)
792 break; 808 break;
@@ -1251,35 +1267,6 @@ void *xas_find_conflict(struct xa_state *xas)
1251EXPORT_SYMBOL_GPL(xas_find_conflict); 1267EXPORT_SYMBOL_GPL(xas_find_conflict);
1252 1268
1253/** 1269/**
1254 * xa_init_flags() - Initialise an empty XArray with flags.
1255 * @xa: XArray.
1256 * @flags: XA_FLAG values.
1257 *
1258 * If you need to initialise an XArray with special flags (eg you need
1259 * to take the lock from interrupt context), use this function instead
1260 * of xa_init().
1261 *
1262 * Context: Any context.
1263 */
1264void xa_init_flags(struct xarray *xa, gfp_t flags)
1265{
1266 unsigned int lock_type;
1267 static struct lock_class_key xa_lock_irq;
1268 static struct lock_class_key xa_lock_bh;
1269
1270 spin_lock_init(&xa->xa_lock);
1271 xa->xa_flags = flags;
1272 xa->xa_head = NULL;
1273
1274 lock_type = xa_lock_type(xa);
1275 if (lock_type == XA_LOCK_IRQ)
1276 lockdep_set_class(&xa->xa_lock, &xa_lock_irq);
1277 else if (lock_type == XA_LOCK_BH)
1278 lockdep_set_class(&xa->xa_lock, &xa_lock_bh);
1279}
1280EXPORT_SYMBOL(xa_init_flags);
1281
1282/**
1283 * xa_load() - Load an entry from an XArray. 1270 * xa_load() - Load an entry from an XArray.
1284 * @xa: XArray. 1271 * @xa: XArray.
1285 * @index: index into array. 1272 * @index: index into array.
@@ -1308,7 +1295,6 @@ static void *xas_result(struct xa_state *xas, void *curr)
1308{ 1295{
1309 if (xa_is_zero(curr)) 1296 if (xa_is_zero(curr))
1310 return NULL; 1297 return NULL;
1311 XA_NODE_BUG_ON(xas->xa_node, xa_is_internal(curr));
1312 if (xas_error(xas)) 1298 if (xas_error(xas))
1313 curr = xas->xa_node; 1299 curr = xas->xa_node;
1314 return curr; 1300 return curr;
@@ -1319,13 +1305,12 @@ static void *xas_result(struct xa_state *xas, void *curr)
1319 * @xa: XArray. 1305 * @xa: XArray.
1320 * @index: Index into array. 1306 * @index: Index into array.
1321 * 1307 *
1322 * If the entry at this index is a multi-index entry then all indices will 1308 * After this function returns, loading from @index will return %NULL.
1323 * be erased, and the entry will no longer be a multi-index entry. 1309 * If the index is part of a multi-index entry, all indices will be erased
1324 * This function expects the xa_lock to be held on entry. 1310 * and none of the entries will be part of a multi-index entry.
1325 * 1311 *
1326 * Context: Any context. Expects xa_lock to be held on entry. May 1312 * Context: Any context. Expects xa_lock to be held on entry.
1327 * release and reacquire xa_lock if @gfp flags permit. 1313 * Return: The entry which used to be at this index.
1328 * Return: The old entry at this index.
1329 */ 1314 */
1330void *__xa_erase(struct xarray *xa, unsigned long index) 1315void *__xa_erase(struct xarray *xa, unsigned long index)
1331{ 1316{
@@ -1339,9 +1324,9 @@ EXPORT_SYMBOL(__xa_erase);
1339 * @xa: XArray. 1324 * @xa: XArray.
1340 * @index: Index of entry. 1325 * @index: Index of entry.
1341 * 1326 *
1342 * This function is the equivalent of calling xa_store() with %NULL as 1327 * After this function returns, loading from @index will return %NULL.
1343 * the third argument. The XArray does not need to allocate memory, so 1328 * If the index is part of a multi-index entry, all indices will be erased
1344 * the user does not need to provide GFP flags. 1329 * and none of the entries will be part of a multi-index entry.
1345 * 1330 *
1346 * Context: Any context. Takes and releases the xa_lock. 1331 * Context: Any context. Takes and releases the xa_lock.
1347 * Return: The entry which used to be at this index. 1332 * Return: The entry which used to be at this index.
@@ -1378,7 +1363,7 @@ void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1378 XA_STATE(xas, xa, index); 1363 XA_STATE(xas, xa, index);
1379 void *curr; 1364 void *curr;
1380 1365
1381 if (WARN_ON_ONCE(xa_is_internal(entry))) 1366 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1382 return XA_ERROR(-EINVAL); 1367 return XA_ERROR(-EINVAL);
1383 if (xa_track_free(xa) && !entry) 1368 if (xa_track_free(xa) && !entry)
1384 entry = XA_ZERO_ENTRY; 1369 entry = XA_ZERO_ENTRY;
@@ -1444,18 +1429,14 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index,
1444 XA_STATE(xas, xa, index); 1429 XA_STATE(xas, xa, index);
1445 void *curr; 1430 void *curr;
1446 1431
1447 if (WARN_ON_ONCE(xa_is_internal(entry))) 1432 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1448 return XA_ERROR(-EINVAL); 1433 return XA_ERROR(-EINVAL);
1449 if (xa_track_free(xa) && !entry)
1450 entry = XA_ZERO_ENTRY;
1451 1434
1452 do { 1435 do {
1453 curr = xas_load(&xas); 1436 curr = xas_load(&xas);
1454 if (curr == XA_ZERO_ENTRY)
1455 curr = NULL;
1456 if (curr == old) { 1437 if (curr == old) {
1457 xas_store(&xas, entry); 1438 xas_store(&xas, entry);
1458 if (xa_track_free(xa)) 1439 if (xa_track_free(xa) && entry && !curr)
1459 xas_clear_mark(&xas, XA_FREE_MARK); 1440 xas_clear_mark(&xas, XA_FREE_MARK);
1460 } 1441 }
1461 } while (__xas_nomem(&xas, gfp)); 1442 } while (__xas_nomem(&xas, gfp));
@@ -1465,40 +1446,45 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index,
1465EXPORT_SYMBOL(__xa_cmpxchg); 1446EXPORT_SYMBOL(__xa_cmpxchg);
1466 1447
1467/** 1448/**
1468 * __xa_reserve() - Reserve this index in the XArray. 1449 * __xa_insert() - Store this entry in the XArray if no entry is present.
1469 * @xa: XArray. 1450 * @xa: XArray.
1470 * @index: Index into array. 1451 * @index: Index into array.
1452 * @entry: New entry.
1471 * @gfp: Memory allocation flags. 1453 * @gfp: Memory allocation flags.
1472 * 1454 *
1473 * Ensures there is somewhere to store an entry at @index in the array. 1455 * Inserting a NULL entry will store a reserved entry (like xa_reserve())
1474 * If there is already something stored at @index, this function does 1456 * if no entry is present. Inserting will fail if a reserved entry is
1475 * nothing. If there was nothing there, the entry is marked as reserved. 1457 * present, even though loading from this index will return NULL.
1476 * Loading from a reserved entry returns a %NULL pointer.
1477 *
1478 * If you do not use the entry that you have reserved, call xa_release()
1479 * or xa_erase() to free any unnecessary memory.
1480 * 1458 *
1481 * Context: Any context. Expects the xa_lock to be held on entry. May 1459 * Context: Any context. Expects xa_lock to be held on entry. May
1482 * release the lock, sleep and reacquire the lock if the @gfp flags permit. 1460 * release and reacquire xa_lock if @gfp flags permit.
1483 * Return: 0 if the reservation succeeded or -ENOMEM if it failed. 1461 * Return: 0 if the store succeeded. -EBUSY if another entry was present.
1462 * -ENOMEM if memory could not be allocated.
1484 */ 1463 */
1485int __xa_reserve(struct xarray *xa, unsigned long index, gfp_t gfp) 1464int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
1486{ 1465{
1487 XA_STATE(xas, xa, index); 1466 XA_STATE(xas, xa, index);
1488 void *curr; 1467 void *curr;
1489 1468
1469 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1470 return -EINVAL;
1471 if (!entry)
1472 entry = XA_ZERO_ENTRY;
1473
1490 do { 1474 do {
1491 curr = xas_load(&xas); 1475 curr = xas_load(&xas);
1492 if (!curr) { 1476 if (!curr) {
1493 xas_store(&xas, XA_ZERO_ENTRY); 1477 xas_store(&xas, entry);
1494 if (xa_track_free(xa)) 1478 if (xa_track_free(xa))
1495 xas_clear_mark(&xas, XA_FREE_MARK); 1479 xas_clear_mark(&xas, XA_FREE_MARK);
1480 } else {
1481 xas_set_err(&xas, -EBUSY);
1496 } 1482 }
1497 } while (__xas_nomem(&xas, gfp)); 1483 } while (__xas_nomem(&xas, gfp));
1498 1484
1499 return xas_error(&xas); 1485 return xas_error(&xas);
1500} 1486}
1501EXPORT_SYMBOL(__xa_reserve); 1487EXPORT_SYMBOL(__xa_insert);
1502 1488
1503#ifdef CONFIG_XARRAY_MULTI 1489#ifdef CONFIG_XARRAY_MULTI
1504static void xas_set_range(struct xa_state *xas, unsigned long first, 1490static void xas_set_range(struct xa_state *xas, unsigned long first,
@@ -1567,7 +1553,7 @@ void *xa_store_range(struct xarray *xa, unsigned long first,
1567 if (last + 1) 1553 if (last + 1)
1568 order = __ffs(last + 1); 1554 order = __ffs(last + 1);
1569 xas_set_order(&xas, last, order); 1555 xas_set_order(&xas, last, order);
1570 xas_create(&xas); 1556 xas_create(&xas, true);
1571 if (xas_error(&xas)) 1557 if (xas_error(&xas))
1572 goto unlock; 1558 goto unlock;
1573 } 1559 }
@@ -1591,25 +1577,25 @@ EXPORT_SYMBOL(xa_store_range);
1591 * __xa_alloc() - Find somewhere to store this entry in the XArray. 1577 * __xa_alloc() - Find somewhere to store this entry in the XArray.
1592 * @xa: XArray. 1578 * @xa: XArray.
1593 * @id: Pointer to ID. 1579 * @id: Pointer to ID.
1594 * @max: Maximum ID to allocate (inclusive). 1580 * @limit: Range for allocated ID.
1595 * @entry: New entry. 1581 * @entry: New entry.
1596 * @gfp: Memory allocation flags. 1582 * @gfp: Memory allocation flags.
1597 * 1583 *
1598 * Allocates an unused ID in the range specified by @id and @max. 1584 * Finds an empty entry in @xa between @limit.min and @limit.max,
1599 * Updates the @id pointer with the index, then stores the entry at that 1585 * stores the index into the @id pointer, then stores the entry at
1600 * index. A concurrent lookup will not see an uninitialised @id. 1586 * that index. A concurrent lookup will not see an uninitialised @id.
1601 * 1587 *
1602 * Context: Any context. Expects xa_lock to be held on entry. May 1588 * Context: Any context. Expects xa_lock to be held on entry. May
1603 * release and reacquire xa_lock if @gfp flags permit. 1589 * release and reacquire xa_lock if @gfp flags permit.
1604 * Return: 0 on success, -ENOMEM if memory allocation fails or -ENOSPC if 1590 * Return: 0 on success, -ENOMEM if memory could not be allocated or
1605 * there is no more space in the XArray. 1591 * -EBUSY if there are no free entries in @limit.
1606 */ 1592 */
1607int __xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry, gfp_t gfp) 1593int __xa_alloc(struct xarray *xa, u32 *id, void *entry,
1594 struct xa_limit limit, gfp_t gfp)
1608{ 1595{
1609 XA_STATE(xas, xa, 0); 1596 XA_STATE(xas, xa, 0);
1610 int err;
1611 1597
1612 if (WARN_ON_ONCE(xa_is_internal(entry))) 1598 if (WARN_ON_ONCE(xa_is_advanced(entry)))
1613 return -EINVAL; 1599 return -EINVAL;
1614 if (WARN_ON_ONCE(!xa_track_free(xa))) 1600 if (WARN_ON_ONCE(!xa_track_free(xa)))
1615 return -EINVAL; 1601 return -EINVAL;
@@ -1618,22 +1604,71 @@ int __xa_alloc(struct xarray *xa, u32 *id, u32 max, void *entry, gfp_t gfp)
1618 entry = XA_ZERO_ENTRY; 1604 entry = XA_ZERO_ENTRY;
1619 1605
1620 do { 1606 do {
1621 xas.xa_index = *id; 1607 xas.xa_index = limit.min;
1622 xas_find_marked(&xas, max, XA_FREE_MARK); 1608 xas_find_marked(&xas, limit.max, XA_FREE_MARK);
1623 if (xas.xa_node == XAS_RESTART) 1609 if (xas.xa_node == XAS_RESTART)
1624 xas_set_err(&xas, -ENOSPC); 1610 xas_set_err(&xas, -EBUSY);
1611 else
1612 *id = xas.xa_index;
1625 xas_store(&xas, entry); 1613 xas_store(&xas, entry);
1626 xas_clear_mark(&xas, XA_FREE_MARK); 1614 xas_clear_mark(&xas, XA_FREE_MARK);
1627 } while (__xas_nomem(&xas, gfp)); 1615 } while (__xas_nomem(&xas, gfp));
1628 1616
1629 err = xas_error(&xas); 1617 return xas_error(&xas);
1630 if (!err)
1631 *id = xas.xa_index;
1632 return err;
1633} 1618}
1634EXPORT_SYMBOL(__xa_alloc); 1619EXPORT_SYMBOL(__xa_alloc);
1635 1620
1636/** 1621/**
1622 * __xa_alloc_cyclic() - Find somewhere to store this entry in the XArray.
1623 * @xa: XArray.
1624 * @id: Pointer to ID.
1625 * @entry: New entry.
1626 * @limit: Range of allocated ID.
1627 * @next: Pointer to next ID to allocate.
1628 * @gfp: Memory allocation flags.
1629 *
1630 * Finds an empty entry in @xa between @limit.min and @limit.max,
1631 * stores the index into the @id pointer, then stores the entry at
1632 * that index. A concurrent lookup will not see an uninitialised @id.
1633 * The search for an empty entry will start at @next and will wrap
1634 * around if necessary.
1635 *
1636 * Context: Any context. Expects xa_lock to be held on entry. May
1637 * release and reacquire xa_lock if @gfp flags permit.
1638 * Return: 0 if the allocation succeeded without wrapping. 1 if the
1639 * allocation succeeded after wrapping, -ENOMEM if memory could not be
1640 * allocated or -EBUSY if there are no free entries in @limit.
1641 */
1642int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry,
1643 struct xa_limit limit, u32 *next, gfp_t gfp)
1644{
1645 u32 min = limit.min;
1646 int ret;
1647
1648 limit.min = max(min, *next);
1649 ret = __xa_alloc(xa, id, entry, limit, gfp);
1650 if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) {
1651 xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED;
1652 ret = 1;
1653 }
1654
1655 if (ret < 0 && limit.min > min) {
1656 limit.min = min;
1657 ret = __xa_alloc(xa, id, entry, limit, gfp);
1658 if (ret == 0)
1659 ret = 1;
1660 }
1661
1662 if (ret >= 0) {
1663 *next = *id + 1;
1664 if (*next == 0)
1665 xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED;
1666 }
1667 return ret;
1668}
1669EXPORT_SYMBOL(__xa_alloc_cyclic);
1670
1671/**
1637 * __xa_set_mark() - Set this mark on this entry while locked. 1672 * __xa_set_mark() - Set this mark on this entry while locked.
1638 * @xa: XArray. 1673 * @xa: XArray.
1639 * @index: Index of entry. 1674 * @index: Index of entry.
@@ -1927,6 +1962,8 @@ void xa_destroy(struct xarray *xa)
1927 entry = xa_head_locked(xa); 1962 entry = xa_head_locked(xa);
1928 RCU_INIT_POINTER(xa->xa_head, NULL); 1963 RCU_INIT_POINTER(xa->xa_head, NULL);
1929 xas_init_marks(&xas); 1964 xas_init_marks(&xas);
1965 if (xa_zero_busy(xa))
1966 xa_mark_clear(xa, XA_FREE_MARK);
1930 /* lockdep checks we're still holding the lock in xas_free_nodes() */ 1967 /* lockdep checks we're still holding the lock in xas_free_nodes() */
1931 if (xa_is_node(entry)) 1968 if (xa_is_node(entry))
1932 xas_free_nodes(&xas, xa_to_node(entry)); 1969 xas_free_nodes(&xas, xa_to_node(entry));
generated by cgit v1.2.2 (git 2.25.0) at 2025-08-26 09:56:52 -0400