diff options
Diffstat (limited to 'lib')
59 files changed, 1719 insertions, 2415 deletions
diff --git a/lib/842/842_compress.c b/lib/842/842_compress.c index c02baa4168e1..055356508d97 100644 --- a/lib/842/842_compress.c +++ b/lib/842/842_compress.c @@ -532,6 +532,8 @@ int sw842_compress(const u8 *in, unsigned int ilen, } if (repeat_count) { ret = add_repeat_template(p, repeat_count); + if (ret) + return ret; repeat_count = 0; if (next == last) /* reached max repeat bits */ goto repeat; diff --git a/lib/Kconfig b/lib/Kconfig index 5a318f753b2f..dccb61b7d698 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -156,13 +156,18 @@ config CRC16 config CRC_T10DIF tristate "CRC calculation for the T10 Data Integrity Field" - select CRYPTO - select CRYPTO_CRCT10DIF help This option is only needed if a module that's not in the kernel tree needs to calculate CRC checks for use with the SCSI data integrity subsystem. +config ARCH_HAS_CRC_T10DIF + bool + +config CRC_T10DIF_ARCH + tristate + default CRC_T10DIF if ARCH_HAS_CRC_T10DIF && CRC_OPTIMIZATIONS + config CRC64_ROCKSOFT tristate "CRC calculation for the Rocksoft model CRC64" select CRC64 @@ -190,61 +195,12 @@ config CRC32 the kernel tree does. Such modules that use library CRC32/CRC32c functions require M here. -config CRC32_SELFTEST - tristate "CRC32 perform self test on init" - depends on CRC32 - help - This option enables the CRC32 library functions to perform a - self test on initialization. The self test computes crc32_le - and crc32_be over byte strings with random alignment and length - and computes the total elapsed time and number of bytes processed. - -choice - prompt "CRC32 implementation" - depends on CRC32 - default CRC32_SLICEBY8 - help - This option allows a kernel builder to override the default choice - of CRC32 algorithm. Choose the default ("slice by 8") unless you - know that you need one of the others. - -config CRC32_SLICEBY8 - bool "Slice by 8 bytes" - help - Calculate checksum 8 bytes at a time with a clever slicing algorithm. - This is the fastest algorithm, but comes with a 8KiB lookup table. - Most modern processors have enough cache to hold this table without - thrashing the cache. - - This is the default implementation choice. Choose this one unless - you have a good reason not to. - -config CRC32_SLICEBY4 - bool "Slice by 4 bytes" - help - Calculate checksum 4 bytes at a time with a clever slicing algorithm. - This is a bit slower than slice by 8, but has a smaller 4KiB lookup - table. - - Only choose this option if you know what you are doing. - -config CRC32_SARWATE - bool "Sarwate's Algorithm (one byte at a time)" - help - Calculate checksum a byte at a time using Sarwate's algorithm. This - is not particularly fast, but has a small 256 byte lookup table. - - Only choose this option if you know what you are doing. - -config CRC32_BIT - bool "Classic Algorithm (one bit at a time)" - help - Calculate checksum one bit at a time. This is VERY slow, but has - no lookup table. This is provided as a debugging option. - - Only choose this option if you are debugging crc32. +config ARCH_HAS_CRC32 + bool -endchoice +config CRC32_ARCH + tristate + default CRC32 if ARCH_HAS_CRC32 && CRC_OPTIMIZATIONS config CRC64 tristate "CRC64 functions" @@ -272,14 +228,10 @@ config CRC7 config LIBCRC32C tristate "CRC32c (Castagnoli, et al) Cyclic Redundancy-Check" - select CRYPTO - select CRYPTO_CRC32C + select CRC32 help - This option is provided for the case where no in-kernel-tree - modules require CRC32c functions, but a module built outside the - kernel tree does. Such modules that use library CRC32c functions - require M here. See Castagnoli93. - Module will be libcrc32c. + This option just selects CRC32 and is provided for compatibility + purposes until the users are updated to select CRC32 directly. config CRC8 tristate "CRC8 function" @@ -288,6 +240,17 @@ config CRC8 when they need to do cyclic redundancy check according CRC8 algorithm. Module will be called crc8. +config CRC_OPTIMIZATIONS + bool "Enable optimized CRC implementations" if EXPERT + default y + help + Disabling this option reduces code size slightly by disabling the + architecture-optimized implementations of any CRC variants that are + enabled. CRC checksumming performance may get much slower. + + Keep this enabled unless you're really trying to minimize the size of + the kernel. + config XXHASH tristate diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index bc725add84f4..35796c290ca3 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -433,7 +433,7 @@ config GDB_SCRIPTS build directory. If you load vmlinux into gdb, the helper scripts will be automatically imported by gdb as well, and additional functions are available to analyze a Linux kernel - instance. See Documentation/dev-tools/gdb-kernel-debugging.rst + instance. See Documentation/process/debugging/gdb-kernel-debugging.rst for further details. endif # DEBUG_INFO @@ -1397,9 +1397,9 @@ config PROVE_LOCKING For more details, see Documentation/locking/lockdep-design.rst. config PROVE_RAW_LOCK_NESTING - bool + bool "Enable raw_spinlock - spinlock nesting checks" if !ARCH_SUPPORTS_RT depends on PROVE_LOCKING - default y + default y if ARCH_SUPPORTS_RT help Enable the raw_spinlock vs. spinlock nesting checks which ensure that the lock nesting rules for PREEMPT_RT enabled kernels are @@ -1502,7 +1502,7 @@ config LOCKDEP_SMALL bool config LOCKDEP_BITS - int "Bitsize for MAX_LOCKDEP_ENTRIES" + int "Size for MAX_LOCKDEP_ENTRIES (as Nth power of 2)" depends on LOCKDEP && !LOCKDEP_SMALL range 10 24 default 15 @@ -1510,7 +1510,7 @@ config LOCKDEP_BITS Try increasing this value if you hit "BUG: MAX_LOCKDEP_ENTRIES too low!" message. config LOCKDEP_CHAINS_BITS - int "Bitsize for MAX_LOCKDEP_CHAINS" + int "Size for MAX_LOCKDEP_CHAINS (as Nth power of 2)" depends on LOCKDEP && !LOCKDEP_SMALL range 10 21 default 16 @@ -1518,7 +1518,7 @@ config LOCKDEP_CHAINS_BITS Try increasing this value if you hit "BUG: MAX_LOCKDEP_CHAINS too low!" message. config LOCKDEP_STACK_TRACE_BITS - int "Bitsize for MAX_STACK_TRACE_ENTRIES" + int "Size for MAX_STACK_TRACE_ENTRIES (as Nth power of 2)" depends on LOCKDEP && !LOCKDEP_SMALL range 10 26 default 19 @@ -1526,7 +1526,7 @@ config LOCKDEP_STACK_TRACE_BITS Try increasing this value if you hit "BUG: MAX_STACK_TRACE_ENTRIES too low!" message. config LOCKDEP_STACK_TRACE_HASH_BITS - int "Bitsize for STACK_TRACE_HASH_SIZE" + int "Size for STACK_TRACE_HASH_SIZE (as Nth power of 2)" depends on LOCKDEP && !LOCKDEP_SMALL range 10 26 default 14 @@ -1534,7 +1534,7 @@ config LOCKDEP_STACK_TRACE_HASH_BITS Try increasing this value if you need large STACK_TRACE_HASH_SIZE. config LOCKDEP_CIRCULAR_QUEUE_BITS - int "Bitsize for elements in circular_queue struct" + int "Size for elements in circular_queue struct (as Nth power of 2)" depends on LOCKDEP range 10 26 default 12 @@ -2103,7 +2103,7 @@ config FAIL_SKB_REALLOC reallocated, catching possible invalid pointers to the skb. For more information, check - Documentation/dev-tools/fault-injection/fault-injection.rst + Documentation/fault-injection/fault-injection.rst config FAULT_INJECTION_CONFIGFS bool "Configfs interface for fault-injection capabilities" @@ -2269,7 +2269,6 @@ config TEST_LIST_SORT config TEST_MIN_HEAP tristate "Min heap test" depends on DEBUG_KERNEL || m - select MIN_HEAP help Enable this to turn on min heap function tests. This test is executed only once during system boot (so affects only boot time), @@ -2479,6 +2478,17 @@ config TEST_RHASHTABLE config TEST_IDA tristate "Perform selftest on IDA functions" +config TEST_MISC_MINOR + tristate "Basic misc minor Kunit test" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + Kunit test for the misc minor. + It tests misc minor functions for dynamic and misc dynamic minor. + This include misc_xxx functions + + If unsure, say N. + config TEST_PARMAN tristate "Perform selftest on priority array manager" depends on PARMAN @@ -2838,6 +2848,26 @@ config HW_BREAKPOINT_KUNIT_TEST If unsure, say N. +config CRC_KUNIT_TEST + tristate "KUnit tests for CRC functions" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + select CRC16 + select CRC_T10DIF + select CRC32 + select CRC64 + help + Unit tests for the CRC library functions. + + This is intended to help people writing architecture-specific + optimized versions. If unsure, say N. + +config CRC_BENCHMARK + bool "Benchmark for the CRC functions" + depends on CRC_KUNIT_TEST + help + Include benchmarks in the KUnit test suite for the CRC functions. + config SIPHASH_KUNIT_TEST tristate "Perform selftest on siphash functions" if !KUNIT_ALL_TESTS depends on KUNIT @@ -2858,15 +2888,6 @@ config USERCOPY_KUNIT_TEST on the copy_to/from_user infrastructure, making sure basic user/kernel boundary testing is working. -config CRC16_KUNIT_TEST - tristate "KUnit tests for CRC16" - depends on KUNIT - default KUNIT_ALL_TESTS - select CRC16 - help - Enable this option to run unit tests for the kernel's CRC16 - implementation (<linux/crc16.h>). - config TEST_UDELAY tristate "udelay test driver" help @@ -3161,6 +3182,21 @@ config INT_POW_TEST If unsure, say N +config INT_SQRT_KUNIT_TEST + tristate "Integer square root test" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + This option enables the KUnit test suite for the int_sqrt() function, + which performs square root calculation. The test suite checks + various scenarios, including edge cases, to ensure correctness. + + Enabling this option will include tests that check various scenarios + and edge cases to ensure the accuracy and reliability of the square root + function. + + If unsure, say N + endif # RUNTIME_TESTING_MENU config ARCH_USE_MEMTEST diff --git a/lib/Kconfig.kgdb b/lib/Kconfig.kgdb index 537e1b3f5734..8336b1a489a3 100644 --- a/lib/Kconfig.kgdb +++ b/lib/Kconfig.kgdb @@ -19,7 +19,7 @@ menuconfig KGDB CONFIG_FRAME_POINTER to aid in producing more reliable stack backtraces in the external debugger. Documentation of kernel debugger is available at http://kgdb.sourceforge.net - as well as in Documentation/dev-tools/kgdb.rst. If + as well as in Documentation/process/debugging/kgdb.rst. If unsure, say N. if KGDB diff --git a/lib/Makefile b/lib/Makefile index a8155c972f02..4f3d00a2fd65 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -5,6 +5,11 @@ ccflags-remove-$(CONFIG_FUNCTION_TRACER) += $(CC_FLAGS_FTRACE) +# Branch profiling isn't noinstr-safe +ifdef CONFIG_TRACE_BRANCH_PROFILING +CFLAGS_smp_processor_id.o += -DDISABLE_BRANCH_PROFILING +endif + # These files are disabled because they produce lots of non-interesting and/or # flaky coverage that is not a function of syscall inputs. For example, # rbtree can be global and individual rotations don't correlate with inputs. @@ -164,10 +169,8 @@ obj-$(CONFIG_CRC_T10DIF)+= crc-t10dif.o obj-$(CONFIG_CRC_ITU_T) += crc-itu-t.o obj-$(CONFIG_CRC32) += crc32.o obj-$(CONFIG_CRC64) += crc64.o -obj-$(CONFIG_CRC32_SELFTEST) += crc32test.o obj-$(CONFIG_CRC4) += crc4.o obj-$(CONFIG_CRC7) += crc7.o -obj-$(CONFIG_LIBCRC32C) += libcrc32c.o obj-$(CONFIG_CRC8) += crc8.o obj-$(CONFIG_CRC64_ROCKSOFT) += crc64-rocksoft.o obj-$(CONFIG_XXHASH) += xxhash.o @@ -392,9 +395,9 @@ CFLAGS_fortify_kunit.o += $(call cc-disable-warning, stringop-overread) CFLAGS_fortify_kunit.o += $(call cc-disable-warning, stringop-truncation) CFLAGS_fortify_kunit.o += $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_FORTIFY_KUNIT_TEST) += fortify_kunit.o +obj-$(CONFIG_CRC_KUNIT_TEST) += crc_kunit.o obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o -obj-$(CONFIG_CRC16_KUNIT_TEST) += crc16_kunit.o obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o diff --git a/lib/alloc_tag.c b/lib/alloc_tag.c index 4e5d7af3eaa2..513176e33242 100644 --- a/lib/alloc_tag.c +++ b/lib/alloc_tag.c @@ -422,11 +422,20 @@ static int vm_module_tags_populate(void) unsigned long old_shadow_end = ALIGN(phys_end, MODULE_ALIGN); unsigned long new_shadow_end = ALIGN(new_end, MODULE_ALIGN); unsigned long more_pages; - unsigned long nr; + unsigned long nr = 0; more_pages = ALIGN(new_end - phys_end, PAGE_SIZE) >> PAGE_SHIFT; - nr = alloc_pages_bulk_array_node(GFP_KERNEL | __GFP_NOWARN, - NUMA_NO_NODE, more_pages, next_page); + while (nr < more_pages) { + unsigned long allocated; + + allocated = alloc_pages_bulk_node(GFP_KERNEL | __GFP_NOWARN, + NUMA_NO_NODE, more_pages - nr, next_page + nr); + + if (!allocated) + break; + nr += allocated; + } + if (nr < more_pages || vmap_pages_range(phys_end, phys_end + (nr << PAGE_SHIFT), PAGE_KERNEL, next_page, PAGE_SHIFT) < 0) { diff --git a/lib/cpumask.c b/lib/cpumask.c index e77ee9d46f71..57274ba8b6d9 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -83,10 +83,7 @@ EXPORT_SYMBOL(alloc_cpumask_var_node); */ void __init alloc_bootmem_cpumask_var(cpumask_var_t *mask) { - *mask = memblock_alloc(cpumask_size(), SMP_CACHE_BYTES); - if (!*mask) - panic("%s: Failed to allocate %u bytes\n", __func__, - cpumask_size()); + *mask = memblock_alloc_or_panic(cpumask_size(), SMP_CACHE_BYTES); } /** diff --git a/lib/crc-t10dif.c b/lib/crc-t10dif.c index 1ed2ed487097..311c2ab829f1 100644 --- a/lib/crc-t10dif.c +++ b/lib/crc-t10dif.c @@ -9,123 +9,57 @@ #include <linux/types.h> #include <linux/module.h> #include <linux/crc-t10dif.h> -#include <linux/err.h> -#include <linux/init.h> -#include <crypto/hash.h> -#include <crypto/algapi.h> -#include <linux/static_key.h> -#include <linux/notifier.h> -static struct crypto_shash __rcu *crct10dif_tfm; -static DEFINE_STATIC_KEY_TRUE(crct10dif_fallback); -static DEFINE_MUTEX(crc_t10dif_mutex); -static struct work_struct crct10dif_rehash_work; - -static int crc_t10dif_notify(struct notifier_block *self, unsigned long val, void *data) -{ - struct crypto_alg *alg = data; - - if (val != CRYPTO_MSG_ALG_LOADED || - strcmp(alg->cra_name, CRC_T10DIF_STRING)) - return NOTIFY_DONE; - - schedule_work(&crct10dif_rehash_work); - return NOTIFY_OK; -} - -static void crc_t10dif_rehash(struct work_struct *work) -{ - struct crypto_shash *new, *old; - - mutex_lock(&crc_t10dif_mutex); - old = rcu_dereference_protected(crct10dif_tfm, - lockdep_is_held(&crc_t10dif_mutex)); - new = crypto_alloc_shash(CRC_T10DIF_STRING, 0, 0); - if (IS_ERR(new)) { - mutex_unlock(&crc_t10dif_mutex); - return; - } - rcu_assign_pointer(crct10dif_tfm, new); - mutex_unlock(&crc_t10dif_mutex); - - if (old) { - synchronize_rcu(); - crypto_free_shash(old); - } else { - static_branch_disable(&crct10dif_fallback); - } -} - -static struct notifier_block crc_t10dif_nb = { - .notifier_call = crc_t10dif_notify, +/* + * Table generated using the following polynomial: + * x^16 + x^15 + x^11 + x^9 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 + * gt: 0x8bb7 + */ +static const u16 t10_dif_crc_table[256] = { + 0x0000, 0x8BB7, 0x9CD9, 0x176E, 0xB205, 0x39B2, 0x2EDC, 0xA56B, + 0xEFBD, 0x640A, 0x7364, 0xF8D3, 0x5DB8, 0xD60F, 0xC161, 0x4AD6, + 0x54CD, 0xDF7A, 0xC814, 0x43A3, 0xE6C8, 0x6D7F, 0x7A11, 0xF1A6, + 0xBB70, 0x30C7, 0x27A9, 0xAC1E, 0x0975, 0x82C2, 0x95AC, 0x1E1B, + 0xA99A, 0x222D, 0x3543, 0xBEF4, 0x1B9F, 0x9028, 0x8746, 0x0CF1, + 0x4627, 0xCD90, 0xDAFE, 0x5149, 0xF422, 0x7F95, 0x68FB, 0xE34C, + 0xFD57, 0x76E0, 0x618E, 0xEA39, 0x4F52, 0xC4E5, 0xD38B, 0x583C, + 0x12EA, 0x995D, 0x8E33, 0x0584, 0xA0EF, 0x2B58, 0x3C36, 0xB781, + 0xD883, 0x5334, 0x445A, 0xCFED, 0x6A86, 0xE131, 0xF65F, 0x7DE8, + 0x373E, 0xBC89, 0xABE7, 0x2050, 0x853B, 0x0E8C, 0x19E2, 0x9255, + 0x8C4E, 0x07F9, 0x1097, 0x9B20, 0x3E4B, 0xB5FC, 0xA292, 0x2925, + 0x63F3, 0xE844, 0xFF2A, 0x749D, 0xD1F6, 0x5A41, 0x4D2F, 0xC698, + 0x7119, 0xFAAE, 0xEDC0, 0x6677, 0xC31C, 0x48AB, 0x5FC5, 0xD472, + 0x9EA4, 0x1513, 0x027D, 0x89CA, 0x2CA1, 0xA716, 0xB078, 0x3BCF, + 0x25D4, 0xAE63, 0xB90D, 0x32BA, 0x97D1, 0x1C66, 0x0B08, 0x80BF, + 0xCA69, 0x41DE, 0x56B0, 0xDD07, 0x786C, 0xF3DB, 0xE4B5, 0x6F02, + 0x3AB1, 0xB106, 0xA668, 0x2DDF, 0x88B4, 0x0303, 0x146D, 0x9FDA, + 0xD50C, 0x5EBB, 0x49D5, 0xC262, 0x6709, 0xECBE, 0xFBD0, 0x7067, + 0x6E7C, 0xE5CB, 0xF2A5, 0x7912, 0xDC79, 0x57CE, 0x40A0, 0xCB17, + 0x81C1, 0x0A76, 0x1D18, 0x96AF, 0x33C4, 0xB873, 0xAF1D, 0x24AA, + 0x932B, 0x189C, 0x0FF2, 0x8445, 0x212E, 0xAA99, 0xBDF7, 0x3640, + 0x7C96, 0xF721, 0xE04F, 0x6BF8, 0xCE93, 0x4524, 0x524A, 0xD9FD, + 0xC7E6, 0x4C51, 0x5B3F, 0xD088, 0x75E3, 0xFE54, 0xE93A, 0x628D, + 0x285B, 0xA3EC, 0xB482, 0x3F35, 0x9A5E, 0x11E9, 0x0687, 0x8D30, + 0xE232, 0x6985, 0x7EEB, 0xF55C, 0x5037, 0xDB80, 0xCCEE, 0x4759, + 0x0D8F, 0x8638, 0x9156, 0x1AE1, 0xBF8A, 0x343D, 0x2353, 0xA8E4, + 0xB6FF, 0x3D48, 0x2A26, 0xA191, 0x04FA, 0x8F4D, 0x9823, 0x1394, + 0x5942, 0xD2F5, 0xC59B, 0x4E2C, 0xEB47, 0x60F0, 0x779E, 0xFC29, + 0x4BA8, 0xC01F, 0xD771, 0x5CC6, 0xF9AD, 0x721A, 0x6574, 0xEEC3, + 0xA415, 0x2FA2, 0x38CC, 0xB37B, 0x1610, 0x9DA7, 0x8AC9, 0x017E, + 0x1F65, 0x94D2, 0x83BC, 0x080B, 0xAD60, 0x26D7, 0x31B9, 0xBA0E, + 0xF0D8, 0x7B6F, 0x6C01, 0xE7B6, 0x42DD, 0xC96A, 0xDE04, 0x55B3 }; -__u16 crc_t10dif_update(__u16 crc, const unsigned char *buffer, size_t len) -{ - struct { - struct shash_desc shash; - __u16 crc; - } desc; - int err; - - if (static_branch_unlikely(&crct10dif_fallback)) - return crc_t10dif_generic(crc, buffer, len); - - rcu_read_lock(); - desc.shash.tfm = rcu_dereference(crct10dif_tfm); - desc.crc = crc; - err = crypto_shash_update(&desc.shash, buffer, len); - rcu_read_unlock(); - - BUG_ON(err); - - return desc.crc; -} -EXPORT_SYMBOL(crc_t10dif_update); - -__u16 crc_t10dif(const unsigned char *buffer, size_t len) -{ - return crc_t10dif_update(0, buffer, len); -} -EXPORT_SYMBOL(crc_t10dif); - -static int __init crc_t10dif_mod_init(void) -{ - INIT_WORK(&crct10dif_rehash_work, crc_t10dif_rehash); - crypto_register_notifier(&crc_t10dif_nb); - crc_t10dif_rehash(&crct10dif_rehash_work); - return 0; -} - -static void __exit crc_t10dif_mod_fini(void) -{ - crypto_unregister_notifier(&crc_t10dif_nb); - cancel_work_sync(&crct10dif_rehash_work); - crypto_free_shash(rcu_dereference_protected(crct10dif_tfm, 1)); -} - -module_init(crc_t10dif_mod_init); -module_exit(crc_t10dif_mod_fini); - -static int crc_t10dif_transform_show(char *buffer, const struct kernel_param *kp) +u16 crc_t10dif_generic(u16 crc, const u8 *p, size_t len) { - struct crypto_shash *tfm; - int len; + size_t i; - if (static_branch_unlikely(&crct10dif_fallback)) - return sprintf(buffer, "fallback\n"); + for (i = 0; i < len; i++) + crc = (crc << 8) ^ t10_dif_crc_table[(crc >> 8) ^ p[i]]; - rcu_read_lock(); - tfm = rcu_dereference(crct10dif_tfm); - len = snprintf(buffer, PAGE_SIZE, "%s\n", - crypto_shash_driver_name(tfm)); - rcu_read_unlock(); - - return len; + return crc; } +EXPORT_SYMBOL(crc_t10dif_generic); -module_param_call(transform, NULL, crc_t10dif_transform_show, NULL, 0444); - -MODULE_DESCRIPTION("T10 DIF CRC calculation (library API)"); +MODULE_DESCRIPTION("T10 DIF CRC calculation"); MODULE_LICENSE("GPL"); -MODULE_SOFTDEP("pre: crct10dif"); diff --git a/lib/crc16_kunit.c b/lib/crc16_kunit.c deleted file mode 100644 index 0918c98a96d2..000000000000 --- a/lib/crc16_kunit.c +++ /dev/null @@ -1,155 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 -/* - * KUnits tests for CRC16. - * - * Copyright (C) 2024, LKCAMP - * Author: Vinicius Peixoto <vpeixoto@lkcamp.dev> - * Author: Fabricio Gasperin <fgasperin@lkcamp.dev> - * Author: Enzo Bertoloti <ebertoloti@lkcamp.dev> - */ -#include <kunit/test.h> -#include <linux/crc16.h> -#include <linux/prandom.h> - -#define CRC16_KUNIT_DATA_SIZE 4096 -#define CRC16_KUNIT_TEST_SIZE 100 -#define CRC16_KUNIT_SEED 0x12345678 - -/** - * struct crc16_test - CRC16 test data - * @crc: initial input value to CRC16 - * @start: Start index within the data buffer - * @length: Length of the data - */ -static struct crc16_test { - u16 crc; - u16 start; - u16 length; -} tests[CRC16_KUNIT_TEST_SIZE]; - -u8 data[CRC16_KUNIT_DATA_SIZE]; - - -/* Naive implementation of CRC16 for validation purposes */ -static inline u16 _crc16_naive_byte(u16 crc, u8 data) -{ - u8 i = 0; - - crc ^= (u16) data; - for (i = 0; i < 8; i++) { - if (crc & 0x01) - crc = (crc >> 1) ^ 0xa001; - else - crc = crc >> 1; - } - - return crc; -} - - -static inline u16 _crc16_naive(u16 crc, u8 *buffer, size_t len) -{ - while (len--) - crc = _crc16_naive_byte(crc, *buffer++); - return crc; -} - - -/* Small helper for generating pseudorandom 16-bit data */ -static inline u16 _rand16(void) -{ - static u32 rand = CRC16_KUNIT_SEED; - - rand = next_pseudo_random32(rand); - return rand & 0xFFFF; -} - - -static int crc16_init_test_data(struct kunit_suite *suite) -{ - size_t i; - - /* Fill the data buffer with random bytes */ - for (i = 0; i < CRC16_KUNIT_DATA_SIZE; i++) - data[i] = _rand16() & 0xFF; - - /* Generate random test data while ensuring the random - * start + length values won't overflow the 4096-byte - * buffer (0x7FF * 2 = 0xFFE < 0x1000) - */ - for (size_t i = 0; i < CRC16_KUNIT_TEST_SIZE; i++) { - tests[i].crc = _rand16(); - tests[i].start = _rand16() & 0x7FF; - tests[i].length = _rand16() & 0x7FF; - } - - return 0; -} - -static void crc16_test_empty(struct kunit *test) -{ - u16 crc; - - /* The result for empty data should be the same as the - * initial crc - */ - crc = crc16(0x00, data, 0); - KUNIT_EXPECT_EQ(test, crc, 0); - crc = crc16(0xFF, data, 0); - KUNIT_EXPECT_EQ(test, crc, 0xFF); -} - -static void crc16_test_correctness(struct kunit *test) -{ - size_t i; - u16 crc, crc_naive; - - for (i = 0; i < CRC16_KUNIT_TEST_SIZE; i++) { - /* Compare results with the naive crc16 implementation */ - crc = crc16(tests[i].crc, data + tests[i].start, - tests[i].length); - crc_naive = _crc16_naive(tests[i].crc, data + tests[i].start, - tests[i].length); - KUNIT_EXPECT_EQ(test, crc, crc_naive); - } -} - - -static void crc16_test_combine(struct kunit *test) -{ - size_t i, j; - u16 crc, crc_naive; - - /* Make sure that combining two consecutive crc16 calculations - * yields the same result as calculating the crc16 for the whole thing - */ - for (i = 0; i < CRC16_KUNIT_TEST_SIZE; i++) { - crc_naive = crc16(tests[i].crc, data + tests[i].start, tests[i].length); - for (j = 0; j < tests[i].length; j++) { - crc = crc16(tests[i].crc, data + tests[i].start, j); - crc = crc16(crc, data + tests[i].start + j, tests[i].length - j); - KUNIT_EXPECT_EQ(test, crc, crc_naive); - } - } -} - - -static struct kunit_case crc16_test_cases[] = { - KUNIT_CASE(crc16_test_empty), - KUNIT_CASE(crc16_test_combine), - KUNIT_CASE(crc16_test_correctness), - {}, -}; - -static struct kunit_suite crc16_test_suite = { - .name = "crc16", - .test_cases = crc16_test_cases, - .suite_init = crc16_init_test_data, -}; -kunit_test_suite(crc16_test_suite); - -MODULE_AUTHOR("Fabricio Gasperin <fgasperin@lkcamp.dev>"); -MODULE_AUTHOR("Vinicius Peixoto <vpeixoto@lkcamp.dev>"); -MODULE_AUTHOR("Enzo Bertoloti <ebertoloti@lkcamp.dev>"); -MODULE_DESCRIPTION("Unit tests for crc16"); -MODULE_LICENSE("GPL"); diff --git a/lib/crc32.c b/lib/crc32.c index ff587fee3893..ede6131f66fc 100644 --- a/lib/crc32.c +++ b/lib/crc32.c @@ -30,20 +30,6 @@ #include <linux/crc32poly.h> #include <linux/module.h> #include <linux/types.h> -#include <linux/sched.h> -#include "crc32defs.h" - -#if CRC_LE_BITS > 8 -# define tole(x) ((__force u32) cpu_to_le32(x)) -#else -# define tole(x) (x) -#endif - -#if CRC_BE_BITS > 8 -# define tobe(x) ((__force u32) cpu_to_be32(x)) -#else -# define tobe(x) (x) -#endif #include "crc32table.h" @@ -51,166 +37,21 @@ MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); MODULE_DESCRIPTION("Various CRC32 calculations"); MODULE_LICENSE("GPL"); -#if CRC_LE_BITS > 8 || CRC_BE_BITS > 8 - -/* implements slicing-by-4 or slicing-by-8 algorithm */ -static inline u32 __pure -crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256]) +u32 __pure crc32_le_base(u32 crc, const u8 *p, size_t len) { -# ifdef __LITTLE_ENDIAN -# define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8) -# define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \ - t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255]) -# define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \ - t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255]) -# else -# define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8) -# define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \ - t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255]) -# define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \ - t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255]) -# endif - const u32 *b; - size_t rem_len; -# ifdef CONFIG_X86 - size_t i; -# endif - const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3]; -# if CRC_LE_BITS != 32 - const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7]; -# endif - u32 q; - - /* Align it */ - if (unlikely((long)buf & 3 && len)) { - do { - DO_CRC(*buf++); - } while ((--len) && ((long)buf)&3); - } - -# if CRC_LE_BITS == 32 - rem_len = len & 3; - len = len >> 2; -# else - rem_len = len & 7; - len = len >> 3; -# endif - - b = (const u32 *)buf; -# ifdef CONFIG_X86 - --b; - for (i = 0; i < len; i++) { -# else - for (--b; len; --len) { -# endif - q = crc ^ *++b; /* use pre increment for speed */ -# if CRC_LE_BITS == 32 - crc = DO_CRC4; -# else - crc = DO_CRC8; - q = *++b; - crc ^= DO_CRC4; -# endif - } - len = rem_len; - /* And the last few bytes */ - if (len) { - u8 *p = (u8 *)(b + 1) - 1; -# ifdef CONFIG_X86 - for (i = 0; i < len; i++) - DO_CRC(*++p); /* use pre increment for speed */ -# else - do { - DO_CRC(*++p); /* use pre increment for speed */ - } while (--len); -# endif - } + while (len--) + crc = (crc >> 8) ^ crc32table_le[(crc & 255) ^ *p++]; return crc; -#undef DO_CRC -#undef DO_CRC4 -#undef DO_CRC8 } -#endif - +EXPORT_SYMBOL(crc32_le_base); -/** - * crc32_le_generic() - Calculate bitwise little-endian Ethernet AUTODIN II - * CRC32/CRC32C - * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for other - * uses, or the previous crc32/crc32c value if computing incrementally. - * @p: pointer to buffer over which CRC32/CRC32C is run - * @len: length of buffer @p - * @tab: little-endian Ethernet table - * @polynomial: CRC32/CRC32c LE polynomial - */ -static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, - size_t len, const u32 (*tab)[256], - u32 polynomial) +u32 __pure crc32c_le_base(u32 crc, const u8 *p, size_t len) { -#if CRC_LE_BITS == 1 - int i; - while (len--) { - crc ^= *p++; - for (i = 0; i < 8; i++) - crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); - } -# elif CRC_LE_BITS == 2 - while (len--) { - crc ^= *p++; - crc = (crc >> 2) ^ tab[0][crc & 3]; - crc = (crc >> 2) ^ tab[0][crc & 3]; - crc = (crc >> 2) ^ tab[0][crc & 3]; - crc = (crc >> 2) ^ tab[0][crc & 3]; - } -# elif CRC_LE_BITS == 4 - while (len--) { - crc ^= *p++; - crc = (crc >> 4) ^ tab[0][crc & 15]; - crc = (crc >> 4) ^ tab[0][crc & 15]; - } -# elif CRC_LE_BITS == 8 - /* aka Sarwate algorithm */ - while (len--) { - crc ^= *p++; - crc = (crc >> 8) ^ tab[0][crc & 255]; - } -# else - crc = (__force u32) __cpu_to_le32(crc); - crc = crc32_body(crc, p, len, tab); - crc = __le32_to_cpu((__force __le32)crc); -#endif + while (len--) + crc = (crc >> 8) ^ crc32ctable_le[(crc & 255) ^ *p++]; return crc; } - -#if CRC_LE_BITS == 1 -u32 __pure __weak crc32_le(u32 crc, unsigned char const *p, size_t len) -{ - return crc32_le_generic(crc, p, len, NULL, CRC32_POLY_LE); -} -u32 __pure __weak __crc32c_le(u32 crc, unsigned char const *p, size_t len) -{ - return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE); -} -#else -u32 __pure __weak crc32_le(u32 crc, unsigned char const *p, size_t len) -{ - return crc32_le_generic(crc, p, len, crc32table_le, CRC32_POLY_LE); -} -u32 __pure __weak __crc32c_le(u32 crc, unsigned char const *p, size_t len) -{ - return crc32_le_generic(crc, p, len, crc32ctable_le, CRC32C_POLY_LE); -} -#endif -EXPORT_SYMBOL(crc32_le); -EXPORT_SYMBOL(__crc32c_le); - -u32 __pure crc32_le_base(u32, unsigned char const *, size_t) __alias(crc32_le); -EXPORT_SYMBOL(crc32_le_base); - -u32 __pure __crc32c_le_base(u32, unsigned char const *, size_t) __alias(__crc32c_le); -EXPORT_SYMBOL(__crc32c_le_base); - -u32 __pure crc32_be_base(u32, unsigned char const *, size_t) __alias(crc32_be); +EXPORT_SYMBOL(crc32c_le_base); /* * This multiplies the polynomials x and y modulo the given modulus. @@ -285,64 +126,10 @@ u32 __attribute_const__ __crc32c_le_shift(u32 crc, size_t len) EXPORT_SYMBOL(crc32_le_shift); EXPORT_SYMBOL(__crc32c_le_shift); -/** - * crc32_be_generic() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32 - * @crc: seed value for computation. ~0 for Ethernet, sometimes 0 for - * other uses, or the previous crc32 value if computing incrementally. - * @p: pointer to buffer over which CRC32 is run - * @len: length of buffer @p - * @tab: big-endian Ethernet table - * @polynomial: CRC32 BE polynomial - */ -static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p, - size_t len, const u32 (*tab)[256], - u32 polynomial) +u32 __pure crc32_be_base(u32 crc, const u8 *p, size_t len) { -#if CRC_BE_BITS == 1 - int i; - while (len--) { - crc ^= *p++ << 24; - for (i = 0; i < 8; i++) - crc = - (crc << 1) ^ ((crc & 0x80000000) ? polynomial : - 0); - } -# elif CRC_BE_BITS == 2 - while (len--) { - crc ^= *p++ << 24; - crc = (crc << 2) ^ tab[0][crc >> 30]; - crc = (crc << 2) ^ tab[0][crc >> 30]; - crc = (crc << 2) ^ tab[0][crc >> 30]; - crc = (crc << 2) ^ tab[0][crc >> 30]; - } -# elif CRC_BE_BITS == 4 - while (len--) { - crc ^= *p++ << 24; - crc = (crc << 4) ^ tab[0][crc >> 28]; - crc = (crc << 4) ^ tab[0][crc >> 28]; - } -# elif CRC_BE_BITS == 8 - while (len--) { - crc ^= *p++ << 24; - crc = (crc << 8) ^ tab[0][crc >> 24]; - } -# else - crc = (__force u32) __cpu_to_be32(crc); - crc = crc32_body(crc, p, len, tab); - crc = __be32_to_cpu((__force __be32)crc); -# endif + while (len--) + crc = (crc << 8) ^ crc32table_be[(crc >> 24) ^ *p++]; return crc; } - -#if CRC_BE_BITS == 1 -u32 __pure __weak crc32_be(u32 crc, unsigned char const *p, size_t len) -{ - return crc32_be_generic(crc, p, len, NULL, CRC32_POLY_BE); -} -#else -u32 __pure __weak crc32_be(u32 crc, unsigned char const *p, size_t len) -{ - return crc32_be_generic(crc, p, len, crc32table_be, CRC32_POLY_BE); -} -#endif -EXPORT_SYMBOL(crc32_be); +EXPORT_SYMBOL(crc32_be_base); diff --git a/lib/crc32defs.h b/lib/crc32defs.h deleted file mode 100644 index 0c8fb5923e7e..000000000000 --- a/lib/crc32defs.h +++ /dev/null @@ -1,59 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0 */ - -/* Try to choose an implementation variant via Kconfig */ -#ifdef CONFIG_CRC32_SLICEBY8 -# define CRC_LE_BITS 64 -# define CRC_BE_BITS 64 -#endif -#ifdef CONFIG_CRC32_SLICEBY4 -# define CRC_LE_BITS 32 -# define CRC_BE_BITS 32 -#endif -#ifdef CONFIG_CRC32_SARWATE -# define CRC_LE_BITS 8 -# define CRC_BE_BITS 8 -#endif -#ifdef CONFIG_CRC32_BIT -# define CRC_LE_BITS 1 -# define CRC_BE_BITS 1 -#endif - -/* - * How many bits at a time to use. Valid values are 1, 2, 4, 8, 32 and 64. - * For less performance-sensitive, use 4 or 8 to save table size. - * For larger systems choose same as CPU architecture as default. - * This works well on X86_64, SPARC64 systems. This may require some - * elaboration after experiments with other architectures. - */ -#ifndef CRC_LE_BITS -# ifdef CONFIG_64BIT -# define CRC_LE_BITS 64 -# else -# define CRC_LE_BITS 32 -# endif -#endif -#ifndef CRC_BE_BITS -# ifdef CONFIG_64BIT -# define CRC_BE_BITS 64 -# else -# define CRC_BE_BITS 32 -# endif -#endif - -/* - * Little-endian CRC computation. Used with serial bit streams sent - * lsbit-first. Be sure to use cpu_to_le32() to append the computed CRC. - */ -#if CRC_LE_BITS > 64 || CRC_LE_BITS < 1 || CRC_LE_BITS == 16 || \ - CRC_LE_BITS & CRC_LE_BITS-1 -# error "CRC_LE_BITS must be one of {1, 2, 4, 8, 32, 64}" -#endif - -/* - * Big-endian CRC computation. Used with serial bit streams sent - * msbit-first. Be sure to use cpu_to_be32() to append the computed CRC. - */ -#if CRC_BE_BITS > 64 || CRC_BE_BITS < 1 || CRC_BE_BITS == 16 || \ - CRC_BE_BITS & CRC_BE_BITS-1 -# error "CRC_BE_BITS must be one of {1, 2, 4, 8, 32, 64}" -#endif diff --git a/lib/crc32test.c b/lib/crc32test.c deleted file mode 100644 index 9b4af79412c4..000000000000 --- a/lib/crc32test.c +++ /dev/null @@ -1,852 +0,0 @@ -/* - * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin - * cleaned up code to current version of sparse and added the slicing-by-8 - * algorithm to the closely similar existing slicing-by-4 algorithm. - * - * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com> - * Nicer crc32 functions/docs submitted by linux@horizon.com. Thanks! - * Code was from the public domain, copyright abandoned. Code was - * subsequently included in the kernel, thus was re-licensed under the - * GNU GPL v2. - * - * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com> - * Same crc32 function was used in 5 other places in the kernel. - * I made one version, and deleted the others. - * There are various incantations of crc32(). Some use a seed of 0 or ~0. - * Some xor at the end with ~0. The generic crc32() function takes - * seed as an argument, and doesn't xor at the end. Then individual - * users can do whatever they need. - * drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0. - * fs/jffs2 uses seed 0, doesn't xor with ~0. - * fs/partitions/efi.c uses seed ~0, xor's with ~0. - * - * This source code is licensed under the GNU General Public License, - * Version 2. See the file COPYING for more details. - */ - -#include <linux/crc32.h> -#include <linux/module.h> -#include <linux/sched.h> - -#include "crc32defs.h" - -/* 4096 random bytes */ -static u8 const __aligned(8) test_buf[] __initconst = -{ - 0x5b, 0x85, 0x21, 0xcb, 0x09, 0x68, 0x7d, 0x30, - 0xc7, 0x69, 0xd7, 0x30, 0x92, 0xde, 0x59, 0xe4, - 0xc9, 0x6e, 0x8b, 0xdb, 0x98, 0x6b, 0xaa, 0x60, - 0xa8, 0xb5, 0xbc, 0x6c, 0xa9, 0xb1, 0x5b, 0x2c, - 0xea, 0xb4, 0x92, 0x6a, 0x3f, 0x79, 0x91, 0xe4, - 0xe9, 0x70, 0x51, 0x8c, 0x7f, 0x95, 0x6f, 0x1a, - 0x56, 0xa1, 0x5c, 0x27, 0x03, 0x67, 0x9f, 0x3a, - 0xe2, 0x31, 0x11, 0x29, 0x6b, 0x98, 0xfc, 0xc4, - 0x53, 0x24, 0xc5, 0x8b, 0xce, 0x47, 0xb2, 0xb9, - 0x32, 0xcb, 0xc1, 0xd0, 0x03, 0x57, 0x4e, 0xd4, - 0xe9, 0x3c, 0xa1, 0x63, 0xcf, 0x12, 0x0e, 0xca, - 0xe1, 0x13, 0xd1, 0x93, 0xa6, 0x88, 0x5c, 0x61, - 0x5b, 0xbb, 0xf0, 0x19, 0x46, 0xb4, 0xcf, 0x9e, - 0xb6, 0x6b, 0x4c, 0x3a, 0xcf, 0x60, 0xf9, 0x7a, - 0x8d, 0x07, 0x63, 0xdb, 0x40, 0xe9, 0x0b, 0x6f, - 0xad, 0x97, 0xf1, 0xed, 0xd0, 0x1e, 0x26, 0xfd, - 0xbf, 0xb7, 0xc8, 0x04, 0x94, 0xf8, 0x8b, 0x8c, - 0xf1, 0xab, 0x7a, 0xd4, 0xdd, 0xf3, 0xe8, 0x88, - 0xc3, 0xed, 0x17, 0x8a, 0x9b, 0x40, 0x0d, 0x53, - 0x62, 0x12, 0x03, 0x5f, 0x1b, 0x35, 0x32, 0x1f, - 0xb4, 0x7b, 0x93, 0x78, 0x0d, 0xdb, 0xce, 0xa4, - 0xc0, 0x47, 0xd5, 0xbf, 0x68, 0xe8, 0x5d, 0x74, - 0x8f, 0x8e, 0x75, 0x1c, 0xb2, 0x4f, 0x9a, 0x60, - 0xd1, 0xbe, 0x10, 0xf4, 0x5c, 0xa1, 0x53, 0x09, - 0xa5, 0xe0, 0x09, 0x54, 0x85, 0x5c, 0xdc, 0x07, - 0xe7, 0x21, 0x69, 0x7b, 0x8a, 0xfd, 0x90, 0xf1, - 0x22, 0xd0, 0xb4, 0x36, 0x28, 0xe6, 0xb8, 0x0f, - 0x39, 0xde, 0xc8, 0xf3, 0x86, 0x60, 0x34, 0xd2, - 0x5e, 0xdf, 0xfd, 0xcf, 0x0f, 0xa9, 0x65, 0xf0, - 0xd5, 0x4d, 0x96, 0x40, 0xe3, 0xdf, 0x3f, 0x95, - 0x5a, 0x39, 0x19, 0x93, 0xf4, 0x75, 0xce, 0x22, - 0x00, 0x1c, 0x93, 0xe2, 0x03, 0x66, 0xf4, 0x93, - 0x73, 0x86, 0x81, 0x8e, 0x29, 0x44, 0x48, 0x86, - 0x61, 0x7c, 0x48, 0xa3, 0x43, 0xd2, 0x9c, 0x8d, - 0xd4, 0x95, 0xdd, 0xe1, 0x22, 0x89, 0x3a, 0x40, - 0x4c, 0x1b, 0x8a, 0x04, 0xa8, 0x09, 0x69, 0x8b, - 0xea, 0xc6, 0x55, 0x8e, 0x57, 0xe6, 0x64, 0x35, - 0xf0, 0xc7, 0x16, 0x9f, 0x5d, 0x5e, 0x86, 0x40, - 0x46, 0xbb, 0xe5, 0x45, 0x88, 0xfe, 0xc9, 0x63, - 0x15, 0xfb, 0xf5, 0xbd, 0x71, 0x61, 0xeb, 0x7b, - 0x78, 0x70, 0x07, 0x31, 0x03, 0x9f, 0xb2, 0xc8, - 0xa7, 0xab, 0x47, 0xfd, 0xdf, 0xa0, 0x78, 0x72, - 0xa4, 0x2a, 0xe4, 0xb6, 0xba, 0xc0, 0x1e, 0x86, - 0x71, 0xe6, 0x3d, 0x18, 0x37, 0x70, 0xe6, 0xff, - 0xe0, 0xbc, 0x0b, 0x22, 0xa0, 0x1f, 0xd3, 0xed, - 0xa2, 0x55, 0x39, 0xab, 0xa8, 0x13, 0x73, 0x7c, - 0x3f, 0xb2, 0xd6, 0x19, 0xac, 0xff, 0x99, 0xed, - 0xe8, 0xe6, 0xa6, 0x22, 0xe3, 0x9c, 0xf1, 0x30, - 0xdc, 0x01, 0x0a, 0x56, 0xfa, 0xe4, 0xc9, 0x99, - 0xdd, 0xa8, 0xd8, 0xda, 0x35, 0x51, 0x73, 0xb4, - 0x40, 0x86, 0x85, 0xdb, 0x5c, 0xd5, 0x85, 0x80, - 0x14, 0x9c, 0xfd, 0x98, 0xa9, 0x82, 0xc5, 0x37, - 0xff, 0x32, 0x5d, 0xd0, 0x0b, 0xfa, 0xdc, 0x04, - 0x5e, 0x09, 0xd2, 0xca, 0x17, 0x4b, 0x1a, 0x8e, - 0x15, 0xe1, 0xcc, 0x4e, 0x52, 0x88, 0x35, 0xbd, - 0x48, 0xfe, 0x15, 0xa0, 0x91, 0xfd, 0x7e, 0x6c, - 0x0e, 0x5d, 0x79, 0x1b, 0x81, 0x79, 0xd2, 0x09, - 0x34, 0x70, 0x3d, 0x81, 0xec, 0xf6, 0x24, 0xbb, - 0xfb, 0xf1, 0x7b, 0xdf, 0x54, 0xea, 0x80, 0x9b, - 0xc7, 0x99, 0x9e, 0xbd, 0x16, 0x78, 0x12, 0x53, - 0x5e, 0x01, 0xa7, 0x4e, 0xbd, 0x67, 0xe1, 0x9b, - 0x4c, 0x0e, 0x61, 0x45, 0x97, 0xd2, 0xf0, 0x0f, - 0xfe, 0x15, 0x08, 0xb7, 0x11, 0x4c, 0xe7, 0xff, - 0x81, 0x53, 0xff, 0x91, 0x25, 0x38, 0x7e, 0x40, - 0x94, 0xe5, 0xe0, 0xad, 0xe6, 0xd9, 0x79, 0xb6, - 0x92, 0xc9, 0xfc, 0xde, 0xc3, 0x1a, 0x23, 0xbb, - 0xdd, 0xc8, 0x51, 0x0c, 0x3a, 0x72, 0xfa, 0x73, - 0x6f, 0xb7, 0xee, 0x61, 0x39, 0x03, 0x01, 0x3f, - 0x7f, 0x94, 0x2e, 0x2e, 0xba, 0x3a, 0xbb, 0xb4, - 0xfa, 0x6a, 0x17, 0xfe, 0xea, 0xef, 0x5e, 0x66, - 0x97, 0x3f, 0x32, 0x3d, 0xd7, 0x3e, 0xb1, 0xf1, - 0x6c, 0x14, 0x4c, 0xfd, 0x37, 0xd3, 0x38, 0x80, - 0xfb, 0xde, 0xa6, 0x24, 0x1e, 0xc8, 0xca, 0x7f, - 0x3a, 0x93, 0xd8, 0x8b, 0x18, 0x13, 0xb2, 0xe5, - 0xe4, 0x93, 0x05, 0x53, 0x4f, 0x84, 0x66, 0xa7, - 0x58, 0x5c, 0x7b, 0x86, 0x52, 0x6d, 0x0d, 0xce, - 0xa4, 0x30, 0x7d, 0xb6, 0x18, 0x9f, 0xeb, 0xff, - 0x22, 0xbb, 0x72, 0x29, 0xb9, 0x44, 0x0b, 0x48, - 0x1e, 0x84, 0x71, 0x81, 0xe3, 0x6d, 0x73, 0x26, - 0x92, 0xb4, 0x4d, 0x2a, 0x29, 0xb8, 0x1f, 0x72, - 0xed, 0xd0, 0xe1, 0x64, 0x77, 0xea, 0x8e, 0x88, - 0x0f, 0xef, 0x3f, 0xb1, 0x3b, 0xad, 0xf9, 0xc9, - 0x8b, 0xd0, 0xac, 0xc6, 0xcc, 0xa9, 0x40, 0xcc, - 0x76, 0xf6, 0x3b, 0x53, 0xb5, 0x88, 0xcb, 0xc8, - 0x37, 0xf1, 0xa2, 0xba, 0x23, 0x15, 0x99, 0x09, - 0xcc, 0xe7, 0x7a, 0x3b, 0x37, 0xf7, 0x58, 0xc8, - 0x46, 0x8c, 0x2b, 0x2f, 0x4e, 0x0e, 0xa6, 0x5c, - 0xea, 0x85, 0x55, 0xba, 0x02, 0x0e, 0x0e, 0x48, - 0xbc, 0xe1, 0xb1, 0x01, 0x35, 0x79, 0x13, 0x3d, - 0x1b, 0xc0, 0x53, 0x68, 0x11, 0xe7, 0x95, 0x0f, - 0x9d, 0x3f, 0x4c, 0x47, 0x7b, 0x4d, 0x1c, 0xae, - 0x50, 0x9b, 0xcb, 0xdd, 0x05, 0x8d, 0x9a, 0x97, - 0xfd, 0x8c, 0xef, 0x0c, 0x1d, 0x67, 0x73, 0xa8, - 0x28, 0x36, 0xd5, 0xb6, 0x92, 0x33, 0x40, 0x75, - 0x0b, 0x51, 0xc3, 0x64, 0xba, 0x1d, 0xc2, 0xcc, - 0xee, 0x7d, 0x54, 0x0f, 0x27, 0x69, 0xa7, 0x27, - 0x63, 0x30, 0x29, 0xd9, 0xc8, 0x84, 0xd8, 0xdf, - 0x9f, 0x68, 0x8d, 0x04, 0xca, 0xa6, 0xc5, 0xc7, - 0x7a, 0x5c, 0xc8, 0xd1, 0xcb, 0x4a, 0xec, 0xd0, - 0xd8, 0x20, 0x69, 0xc5, 0x17, 0xcd, 0x78, 0xc8, - 0x75, 0x23, 0x30, 0x69, 0xc9, 0xd4, 0xea, 0x5c, - 0x4f, 0x6b, 0x86, 0x3f, 0x8b, 0xfe, 0xee, 0x44, - 0xc9, 0x7c, 0xb7, 0xdd, 0x3e, 0xe5, 0xec, 0x54, - 0x03, 0x3e, 0xaa, 0x82, 0xc6, 0xdf, 0xb2, 0x38, - 0x0e, 0x5d, 0xb3, 0x88, 0xd9, 0xd3, 0x69, 0x5f, - 0x8f, 0x70, 0x8a, 0x7e, 0x11, 0xd9, 0x1e, 0x7b, - 0x38, 0xf1, 0x42, 0x1a, 0xc0, 0x35, 0xf5, 0xc7, - 0x36, 0x85, 0xf5, 0xf7, 0xb8, 0x7e, 0xc7, 0xef, - 0x18, 0xf1, 0x63, 0xd6, 0x7a, 0xc6, 0xc9, 0x0e, - 0x4d, 0x69, 0x4f, 0x84, 0xef, 0x26, 0x41, 0x0c, - 0xec, 0xc7, 0xe0, 0x7e, 0x3c, 0x67, 0x01, 0x4c, - 0x62, 0x1a, 0x20, 0x6f, 0xee, 0x47, 0x4d, 0xc0, - 0x99, 0x13, 0x8d, 0x91, 0x4a, 0x26, 0xd4, 0x37, - 0x28, 0x90, 0x58, 0x75, 0x66, 0x2b, 0x0a, 0xdf, - 0xda, 0xee, 0x92, 0x25, 0x90, 0x62, 0x39, 0x9e, - 0x44, 0x98, 0xad, 0xc1, 0x88, 0xed, 0xe4, 0xb4, - 0xaf, 0xf5, 0x8c, 0x9b, 0x48, 0x4d, 0x56, 0x60, - 0x97, 0x0f, 0x61, 0x59, 0x9e, 0xa6, 0x27, 0xfe, - 0xc1, 0x91, 0x15, 0x38, 0xb8, 0x0f, 0xae, 0x61, - 0x7d, 0x26, 0x13, 0x5a, 0x73, 0xff, 0x1c, 0xa3, - 0x61, 0x04, 0x58, 0x48, 0x55, 0x44, 0x11, 0xfe, - 0x15, 0xca, 0xc3, 0xbd, 0xca, 0xc5, 0xb4, 0x40, - 0x5d, 0x1b, 0x7f, 0x39, 0xb5, 0x9c, 0x35, 0xec, - 0x61, 0x15, 0x32, 0x32, 0xb8, 0x4e, 0x40, 0x9f, - 0x17, 0x1f, 0x0a, 0x4d, 0xa9, 0x91, 0xef, 0xb7, - 0xb0, 0xeb, 0xc2, 0x83, 0x9a, 0x6c, 0xd2, 0x79, - 0x43, 0x78, 0x5e, 0x2f, 0xe5, 0xdd, 0x1a, 0x3c, - 0x45, 0xab, 0x29, 0x40, 0x3a, 0x37, 0x5b, 0x6f, - 0xd7, 0xfc, 0x48, 0x64, 0x3c, 0x49, 0xfb, 0x21, - 0xbe, 0xc3, 0xff, 0x07, 0xfb, 0x17, 0xe9, 0xc9, - 0x0c, 0x4c, 0x5c, 0x15, 0x9e, 0x8e, 0x22, 0x30, - 0x0a, 0xde, 0x48, 0x7f, 0xdb, 0x0d, 0xd1, 0x2b, - 0x87, 0x38, 0x9e, 0xcc, 0x5a, 0x01, 0x16, 0xee, - 0x75, 0x49, 0x0d, 0x30, 0x01, 0x34, 0x6a, 0xb6, - 0x9a, 0x5a, 0x2a, 0xec, 0xbb, 0x48, 0xac, 0xd3, - 0x77, 0x83, 0xd8, 0x08, 0x86, 0x4f, 0x48, 0x09, - 0x29, 0x41, 0x79, 0xa1, 0x03, 0x12, 0xc4, 0xcd, - 0x90, 0x55, 0x47, 0x66, 0x74, 0x9a, 0xcc, 0x4f, - 0x35, 0x8c, 0xd6, 0x98, 0xef, 0xeb, 0x45, 0xb9, - 0x9a, 0x26, 0x2f, 0x39, 0xa5, 0x70, 0x6d, 0xfc, - 0xb4, 0x51, 0xee, 0xf4, 0x9c, 0xe7, 0x38, 0x59, - 0xad, 0xf4, 0xbc, 0x46, 0xff, 0x46, 0x8e, 0x60, - 0x9c, 0xa3, 0x60, 0x1d, 0xf8, 0x26, 0x72, 0xf5, - 0x72, 0x9d, 0x68, 0x80, 0x04, 0xf6, 0x0b, 0xa1, - 0x0a, 0xd5, 0xa7, 0x82, 0x3a, 0x3e, 0x47, 0xa8, - 0x5a, 0xde, 0x59, 0x4f, 0x7b, 0x07, 0xb3, 0xe9, - 0x24, 0x19, 0x3d, 0x34, 0x05, 0xec, 0xf1, 0xab, - 0x6e, 0x64, 0x8f, 0xd3, 0xe6, 0x41, 0x86, 0x80, - 0x70, 0xe3, 0x8d, 0x60, 0x9c, 0x34, 0x25, 0x01, - 0x07, 0x4d, 0x19, 0x41, 0x4e, 0x3d, 0x5c, 0x7e, - 0xa8, 0xf5, 0xcc, 0xd5, 0x7b, 0xe2, 0x7d, 0x3d, - 0x49, 0x86, 0x7d, 0x07, 0xb7, 0x10, 0xe3, 0x35, - 0xb8, 0x84, 0x6d, 0x76, 0xab, 0x17, 0xc6, 0x38, - 0xb4, 0xd3, 0x28, 0x57, 0xad, 0xd3, 0x88, 0x5a, - 0xda, 0xea, 0xc8, 0x94, 0xcc, 0x37, 0x19, 0xac, - 0x9c, 0x9f, 0x4b, 0x00, 0x15, 0xc0, 0xc8, 0xca, - 0x1f, 0x15, 0xaa, 0xe0, 0xdb, 0xf9, 0x2f, 0x57, - 0x1b, 0x24, 0xc7, 0x6f, 0x76, 0x29, 0xfb, 0xed, - 0x25, 0x0d, 0xc0, 0xfe, 0xbd, 0x5a, 0xbf, 0x20, - 0x08, 0x51, 0x05, 0xec, 0x71, 0xa3, 0xbf, 0xef, - 0x5e, 0x99, 0x75, 0xdb, 0x3c, 0x5f, 0x9a, 0x8c, - 0xbb, 0x19, 0x5c, 0x0e, 0x93, 0x19, 0xf8, 0x6a, - 0xbc, 0xf2, 0x12, 0x54, 0x2f, 0xcb, 0x28, 0x64, - 0x88, 0xb3, 0x92, 0x0d, 0x96, 0xd1, 0xa6, 0xe4, - 0x1f, 0xf1, 0x4d, 0xa4, 0xab, 0x1c, 0xee, 0x54, - 0xf2, 0xad, 0x29, 0x6d, 0x32, 0x37, 0xb2, 0x16, - 0x77, 0x5c, 0xdc, 0x2e, 0x54, 0xec, 0x75, 0x26, - 0xc6, 0x36, 0xd9, 0x17, 0x2c, 0xf1, 0x7a, 0xdc, - 0x4b, 0xf1, 0xe2, 0xd9, 0x95, 0xba, 0xac, 0x87, - 0xc1, 0xf3, 0x8e, 0x58, 0x08, 0xd8, 0x87, 0x60, - 0xc9, 0xee, 0x6a, 0xde, 0xa4, 0xd2, 0xfc, 0x0d, - 0xe5, 0x36, 0xc4, 0x5c, 0x52, 0xb3, 0x07, 0x54, - 0x65, 0x24, 0xc1, 0xb1, 0xd1, 0xb1, 0x53, 0x13, - 0x31, 0x79, 0x7f, 0x05, 0x76, 0xeb, 0x37, 0x59, - 0x15, 0x2b, 0xd1, 0x3f, 0xac, 0x08, 0x97, 0xeb, - 0x91, 0x98, 0xdf, 0x6c, 0x09, 0x0d, 0x04, 0x9f, - 0xdc, 0x3b, 0x0e, 0x60, 0x68, 0x47, 0x23, 0x15, - 0x16, 0xc6, 0x0b, 0x35, 0xf8, 0x77, 0xa2, 0x78, - 0x50, 0xd4, 0x64, 0x22, 0x33, 0xff, 0xfb, 0x93, - 0x71, 0x46, 0x50, 0x39, 0x1b, 0x9c, 0xea, 0x4e, - 0x8d, 0x0c, 0x37, 0xe5, 0x5c, 0x51, 0x3a, 0x31, - 0xb2, 0x85, 0x84, 0x3f, 0x41, 0xee, 0xa2, 0xc1, - 0xc6, 0x13, 0x3b, 0x54, 0x28, 0xd2, 0x18, 0x37, - 0xcc, 0x46, 0x9f, 0x6a, 0x91, 0x3d, 0x5a, 0x15, - 0x3c, 0x89, 0xa3, 0x61, 0x06, 0x7d, 0x2e, 0x78, - 0xbe, 0x7d, 0x40, 0xba, 0x2f, 0x95, 0xb1, 0x2f, - 0x87, 0x3b, 0x8a, 0xbe, 0x6a, 0xf4, 0xc2, 0x31, - 0x74, 0xee, 0x91, 0xe0, 0x23, 0xaa, 0x5d, 0x7f, - 0xdd, 0xf0, 0x44, 0x8c, 0x0b, 0x59, 0x2b, 0xfc, - 0x48, 0x3a, 0xdf, 0x07, 0x05, 0x38, 0x6c, 0xc9, - 0xeb, 0x18, 0x24, 0x68, 0x8d, 0x58, 0x98, 0xd3, - 0x31, 0xa3, 0xe4, 0x70, 0x59, 0xb1, 0x21, 0xbe, - 0x7e, 0x65, 0x7d, 0xb8, 0x04, 0xab, 0xf6, 0xe4, - 0xd7, 0xda, 0xec, 0x09, 0x8f, 0xda, 0x6d, 0x24, - 0x07, 0xcc, 0x29, 0x17, 0x05, 0x78, 0x1a, 0xc1, - 0xb1, 0xce, 0xfc, 0xaa, 0x2d, 0xe7, 0xcc, 0x85, - 0x84, 0x84, 0x03, 0x2a, 0x0c, 0x3f, 0xa9, 0xf8, - 0xfd, 0x84, 0x53, 0x59, 0x5c, 0xf0, 0xd4, 0x09, - 0xf0, 0xd2, 0x6c, 0x32, 0x03, 0xb0, 0xa0, 0x8c, - 0x52, 0xeb, 0x23, 0x91, 0x88, 0x43, 0x13, 0x46, - 0xf6, 0x1e, 0xb4, 0x1b, 0xf5, 0x8e, 0x3a, 0xb5, - 0x3d, 0x00, 0xf6, 0xe5, 0x08, 0x3d, 0x5f, 0x39, - 0xd3, 0x21, 0x69, 0xbc, 0x03, 0x22, 0x3a, 0xd2, - 0x5c, 0x84, 0xf8, 0x15, 0xc4, 0x80, 0x0b, 0xbc, - 0x29, 0x3c, 0xf3, 0x95, 0x98, 0xcd, 0x8f, 0x35, - 0xbc, 0xa5, 0x3e, 0xfc, 0xd4, 0x13, 0x9e, 0xde, - 0x4f, 0xce, 0x71, 0x9d, 0x09, 0xad, 0xf2, 0x80, - 0x6b, 0x65, 0x7f, 0x03, 0x00, 0x14, 0x7c, 0x15, - 0x85, 0x40, 0x6d, 0x70, 0xea, 0xdc, 0xb3, 0x63, - 0x35, 0x4f, 0x4d, 0xe0, 0xd9, 0xd5, 0x3c, 0x58, - 0x56, 0x23, 0x80, 0xe2, 0x36, 0xdd, 0x75, 0x1d, - 0x94, 0x11, 0x41, 0x8e, 0xe0, 0x81, 0x8e, 0xcf, - 0xe0, 0xe5, 0xf6, 0xde, 0xd1, 0xe7, 0x04, 0x12, - 0x79, 0x92, 0x2b, 0x71, 0x2a, 0x79, 0x8b, 0x7c, - 0x44, 0x79, 0x16, 0x30, 0x4e, 0xf4, 0xf6, 0x9b, - 0xb7, 0x40, 0xa3, 0x5a, 0xa7, 0x69, 0x3e, 0xc1, - 0x3a, 0x04, 0xd0, 0x88, 0xa0, 0x3b, 0xdd, 0xc6, - 0x9e, 0x7e, 0x1e, 0x1e, 0x8f, 0x44, 0xf7, 0x73, - 0x67, 0x1e, 0x1a, 0x78, 0xfa, 0x62, 0xf4, 0xa9, - 0xa8, 0xc6, 0x5b, 0xb8, 0xfa, 0x06, 0x7d, 0x5e, - 0x38, 0x1c, 0x9a, 0x39, 0xe9, 0x39, 0x98, 0x22, - 0x0b, 0xa7, 0xac, 0x0b, 0xf3, 0xbc, 0xf1, 0xeb, - 0x8c, 0x81, 0xe3, 0x48, 0x8a, 0xed, 0x42, 0xc2, - 0x38, 0xcf, 0x3e, 0xda, 0xd2, 0x89, 0x8d, 0x9c, - 0x53, 0xb5, 0x2f, 0x41, 0x01, 0x26, 0x84, 0x9c, - 0xa3, 0x56, 0xf6, 0x49, 0xc7, 0xd4, 0x9f, 0x93, - 0x1b, 0x96, 0x49, 0x5e, 0xad, 0xb3, 0x84, 0x1f, - 0x3c, 0xa4, 0xe0, 0x9b, 0xd1, 0x90, 0xbc, 0x38, - 0x6c, 0xdd, 0x95, 0x4d, 0x9d, 0xb1, 0x71, 0x57, - 0x2d, 0x34, 0xe8, 0xb8, 0x42, 0xc7, 0x99, 0x03, - 0xc7, 0x07, 0x30, 0x65, 0x91, 0x55, 0xd5, 0x90, - 0x70, 0x97, 0x37, 0x68, 0xd4, 0x11, 0xf9, 0xe8, - 0xce, 0xec, 0xdc, 0x34, 0xd5, 0xd3, 0xb7, 0xc4, - 0xb8, 0x97, 0x05, 0x92, 0xad, 0xf8, 0xe2, 0x36, - 0x64, 0x41, 0xc9, 0xc5, 0x41, 0x77, 0x52, 0xd7, - 0x2c, 0xa5, 0x24, 0x2f, 0xd9, 0x34, 0x0b, 0x47, - 0x35, 0xa7, 0x28, 0x8b, 0xc5, 0xcd, 0xe9, 0x46, - 0xac, 0x39, 0x94, 0x3c, 0x10, 0xc6, 0x29, 0x73, - 0x0e, 0x0e, 0x5d, 0xe0, 0x71, 0x03, 0x8a, 0x72, - 0x0e, 0x26, 0xb0, 0x7d, 0x84, 0xed, 0x95, 0x23, - 0x49, 0x5a, 0x45, 0x83, 0x45, 0x60, 0x11, 0x4a, - 0x46, 0x31, 0xd4, 0xd8, 0x16, 0x54, 0x98, 0x58, - 0xed, 0x6d, 0xcc, 0x5d, 0xd6, 0x50, 0x61, 0x9f, - 0x9d, 0xc5, 0x3e, 0x9d, 0x32, 0x47, 0xde, 0x96, - 0xe1, 0x5d, 0xd8, 0xf8, 0xb4, 0x69, 0x6f, 0xb9, - 0x15, 0x90, 0x57, 0x7a, 0xf6, 0xad, 0xb0, 0x5b, - 0xf5, 0xa6, 0x36, 0x94, 0xfd, 0x84, 0xce, 0x1c, - 0x0f, 0x4b, 0xd0, 0xc2, 0x5b, 0x6b, 0x56, 0xef, - 0x73, 0x93, 0x0b, 0xc3, 0xee, 0xd9, 0xcf, 0xd3, - 0xa4, 0x22, 0x58, 0xcd, 0x50, 0x6e, 0x65, 0xf4, - 0xe9, 0xb7, 0x71, 0xaf, 0x4b, 0xb3, 0xb6, 0x2f, - 0x0f, 0x0e, 0x3b, 0xc9, 0x85, 0x14, 0xf5, 0x17, - 0xe8, 0x7a, 0x3a, 0xbf, 0x5f, 0x5e, 0xf8, 0x18, - 0x48, 0xa6, 0x72, 0xab, 0x06, 0x95, 0xe9, 0xc8, - 0xa7, 0xf4, 0x32, 0x44, 0x04, 0x0c, 0x84, 0x98, - 0x73, 0xe3, 0x89, 0x8d, 0x5f, 0x7e, 0x4a, 0x42, - 0x8f, 0xc5, 0x28, 0xb1, 0x82, 0xef, 0x1c, 0x97, - 0x31, 0x3b, 0x4d, 0xe0, 0x0e, 0x10, 0x10, 0x97, - 0x93, 0x49, 0x78, 0x2f, 0x0d, 0x86, 0x8b, 0xa1, - 0x53, 0xa9, 0x81, 0x20, 0x79, 0xe7, 0x07, 0x77, - 0xb6, 0xac, 0x5e, 0xd2, 0x05, 0xcd, 0xe9, 0xdb, - 0x8a, 0x94, 0x82, 0x8a, 0x23, 0xb9, 0x3d, 0x1c, - 0xa9, 0x7d, 0x72, 0x4a, 0xed, 0x33, 0xa3, 0xdb, - 0x21, 0xa7, 0x86, 0x33, 0x45, 0xa5, 0xaa, 0x56, - 0x45, 0xb5, 0x83, 0x29, 0x40, 0x47, 0x79, 0x04, - 0x6e, 0xb9, 0x95, 0xd0, 0x81, 0x77, 0x2d, 0x48, - 0x1e, 0xfe, 0xc3, 0xc2, 0x1e, 0xe5, 0xf2, 0xbe, - 0xfd, 0x3b, 0x94, 0x9f, 0xc4, 0xc4, 0x26, 0x9d, - 0xe4, 0x66, 0x1e, 0x19, 0xee, 0x6c, 0x79, 0x97, - 0x11, 0x31, 0x4b, 0x0d, 0x01, 0xcb, 0xde, 0xa8, - 0xf6, 0x6d, 0x7c, 0x39, 0x46, 0x4e, 0x7e, 0x3f, - 0x94, 0x17, 0xdf, 0xa1, 0x7d, 0xd9, 0x1c, 0x8e, - 0xbc, 0x7d, 0x33, 0x7d, 0xe3, 0x12, 0x40, 0xca, - 0xab, 0x37, 0x11, 0x46, 0xd4, 0xae, 0xef, 0x44, - 0xa2, 0xb3, 0x6a, 0x66, 0x0e, 0x0c, 0x90, 0x7f, - 0xdf, 0x5c, 0x66, 0x5f, 0xf2, 0x94, 0x9f, 0xa6, - 0x73, 0x4f, 0xeb, 0x0d, 0xad, 0xbf, 0xc0, 0x63, - 0x5c, 0xdc, 0x46, 0x51, 0xe8, 0x8e, 0x90, 0x19, - 0xa8, 0xa4, 0x3c, 0x91, 0x79, 0xfa, 0x7e, 0x58, - 0x85, 0x13, 0x55, 0xc5, 0x19, 0x82, 0x37, 0x1b, - 0x0a, 0x02, 0x1f, 0x99, 0x6b, 0x18, 0xf1, 0x28, - 0x08, 0xa2, 0x73, 0xb8, 0x0f, 0x2e, 0xcd, 0xbf, - 0xf3, 0x86, 0x7f, 0xea, 0xef, 0xd0, 0xbb, 0xa6, - 0x21, 0xdf, 0x49, 0x73, 0x51, 0xcc, 0x36, 0xd3, - 0x3e, 0xa0, 0xf8, 0x44, 0xdf, 0xd3, 0xa6, 0xbe, - 0x8a, 0xd4, 0x57, 0xdd, 0x72, 0x94, 0x61, 0x0f, - 0x82, 0xd1, 0x07, 0xb8, 0x7c, 0x18, 0x83, 0xdf, - 0x3a, 0xe5, 0x50, 0x6a, 0x82, 0x20, 0xac, 0xa9, - 0xa8, 0xff, 0xd9, 0xf3, 0x77, 0x33, 0x5a, 0x9e, - 0x7f, 0x6d, 0xfe, 0x5d, 0x33, 0x41, 0x42, 0xe7, - 0x6c, 0x19, 0xe0, 0x44, 0x8a, 0x15, 0xf6, 0x70, - 0x98, 0xb7, 0x68, 0x4d, 0xfa, 0x97, 0x39, 0xb0, - 0x8e, 0xe8, 0x84, 0x8b, 0x75, 0x30, 0xb7, 0x7d, - 0x92, 0x69, 0x20, 0x9c, 0x81, 0xfb, 0x4b, 0xf4, - 0x01, 0x50, 0xeb, 0xce, 0x0c, 0x1c, 0x6c, 0xb5, - 0x4a, 0xd7, 0x27, 0x0c, 0xce, 0xbb, 0xe5, 0x85, - 0xf0, 0xb6, 0xee, 0xd5, 0x70, 0xdd, 0x3b, 0xfc, - 0xd4, 0x99, 0xf1, 0x33, 0xdd, 0x8b, 0xc4, 0x2f, - 0xae, 0xab, 0x74, 0x96, 0x32, 0xc7, 0x4c, 0x56, - 0x3c, 0x89, 0x0f, 0x96, 0x0b, 0x42, 0xc0, 0xcb, - 0xee, 0x0f, 0x0b, 0x8c, 0xfb, 0x7e, 0x47, 0x7b, - 0x64, 0x48, 0xfd, 0xb2, 0x00, 0x80, 0x89, 0xa5, - 0x13, 0x55, 0x62, 0xfc, 0x8f, 0xe2, 0x42, 0x03, - 0xb7, 0x4e, 0x2a, 0x79, 0xb4, 0x82, 0xea, 0x23, - 0x49, 0xda, 0xaf, 0x52, 0x63, 0x1e, 0x60, 0x03, - 0x89, 0x06, 0x44, 0x46, 0x08, 0xc3, 0xc4, 0x87, - 0x70, 0x2e, 0xda, 0x94, 0xad, 0x6b, 0xe0, 0xe4, - 0xd1, 0x8a, 0x06, 0xc2, 0xa8, 0xc0, 0xa7, 0x43, - 0x3c, 0x47, 0x52, 0x0e, 0xc3, 0x77, 0x81, 0x11, - 0x67, 0x0e, 0xa0, 0x70, 0x04, 0x47, 0x29, 0x40, - 0x86, 0x0d, 0x34, 0x56, 0xa7, 0xc9, 0x35, 0x59, - 0x68, 0xdc, 0x93, 0x81, 0x70, 0xee, 0x86, 0xd9, - 0x80, 0x06, 0x40, 0x4f, 0x1a, 0x0d, 0x40, 0x30, - 0x0b, 0xcb, 0x96, 0x47, 0xc1, 0xb7, 0x52, 0xfd, - 0x56, 0xe0, 0x72, 0x4b, 0xfb, 0xbd, 0x92, 0x45, - 0x61, 0x71, 0xc2, 0x33, 0x11, 0xbf, 0x52, 0x83, - 0x79, 0x26, 0xe0, 0x49, 0x6b, 0xb7, 0x05, 0x8b, - 0xe8, 0x0e, 0x87, 0x31, 0xd7, 0x9d, 0x8a, 0xf5, - 0xc0, 0x5f, 0x2e, 0x58, 0x4a, 0xdb, 0x11, 0xb3, - 0x6c, 0x30, 0x2a, 0x46, 0x19, 0xe3, 0x27, 0x84, - 0x1f, 0x63, 0x6e, 0xf6, 0x57, 0xc7, 0xc9, 0xd8, - 0x5e, 0xba, 0xb3, 0x87, 0xd5, 0x83, 0x26, 0x34, - 0x21, 0x9e, 0x65, 0xde, 0x42, 0xd3, 0xbe, 0x7b, - 0xbc, 0x91, 0x71, 0x44, 0x4d, 0x99, 0x3b, 0x31, - 0xe5, 0x3f, 0x11, 0x4e, 0x7f, 0x13, 0x51, 0x3b, - 0xae, 0x79, 0xc9, 0xd3, 0x81, 0x8e, 0x25, 0x40, - 0x10, 0xfc, 0x07, 0x1e, 0xf9, 0x7b, 0x9a, 0x4b, - 0x6c, 0xe3, 0xb3, 0xad, 0x1a, 0x0a, 0xdd, 0x9e, - 0x59, 0x0c, 0xa2, 0xcd, 0xae, 0x48, 0x4a, 0x38, - 0x5b, 0x47, 0x41, 0x94, 0x65, 0x6b, 0xbb, 0xeb, - 0x5b, 0xe3, 0xaf, 0x07, 0x5b, 0xd4, 0x4a, 0xa2, - 0xc9, 0x5d, 0x2f, 0x64, 0x03, 0xd7, 0x3a, 0x2c, - 0x6e, 0xce, 0x76, 0x95, 0xb4, 0xb3, 0xc0, 0xf1, - 0xe2, 0x45, 0x73, 0x7a, 0x5c, 0xab, 0xc1, 0xfc, - 0x02, 0x8d, 0x81, 0x29, 0xb3, 0xac, 0x07, 0xec, - 0x40, 0x7d, 0x45, 0xd9, 0x7a, 0x59, 0xee, 0x34, - 0xf0, 0xe9, 0xd5, 0x7b, 0x96, 0xb1, 0x3d, 0x95, - 0xcc, 0x86, 0xb5, 0xb6, 0x04, 0x2d, 0xb5, 0x92, - 0x7e, 0x76, 0xf4, 0x06, 0xa9, 0xa3, 0x12, 0x0f, - 0xb1, 0xaf, 0x26, 0xba, 0x7c, 0xfc, 0x7e, 0x1c, - 0xbc, 0x2c, 0x49, 0x97, 0x53, 0x60, 0x13, 0x0b, - 0xa6, 0x61, 0x83, 0x89, 0x42, 0xd4, 0x17, 0x0c, - 0x6c, 0x26, 0x52, 0xc3, 0xb3, 0xd4, 0x67, 0xf5, - 0xe3, 0x04, 0xb7, 0xf4, 0xcb, 0x80, 0xb8, 0xcb, - 0x77, 0x56, 0x3e, 0xaa, 0x57, 0x54, 0xee, 0xb4, - 0x2c, 0x67, 0xcf, 0xf2, 0xdc, 0xbe, 0x55, 0xf9, - 0x43, 0x1f, 0x6e, 0x22, 0x97, 0x67, 0x7f, 0xc4, - 0xef, 0xb1, 0x26, 0x31, 0x1e, 0x27, 0xdf, 0x41, - 0x80, 0x47, 0x6c, 0xe2, 0xfa, 0xa9, 0x8c, 0x2a, - 0xf6, 0xf2, 0xab, 0xf0, 0x15, 0xda, 0x6c, 0xc8, - 0xfe, 0xb5, 0x23, 0xde, 0xa9, 0x05, 0x3f, 0x06, - 0x54, 0x4c, 0xcd, 0xe1, 0xab, 0xfc, 0x0e, 0x62, - 0x33, 0x31, 0x73, 0x2c, 0x76, 0xcb, 0xb4, 0x47, - 0x1e, 0x20, 0xad, 0xd8, 0xf2, 0x31, 0xdd, 0xc4, - 0x8b, 0x0c, 0x77, 0xbe, 0xe1, 0x8b, 0x26, 0x00, - 0x02, 0x58, 0xd6, 0x8d, 0xef, 0xad, 0x74, 0x67, - 0xab, 0x3f, 0xef, 0xcb, 0x6f, 0xb0, 0xcc, 0x81, - 0x44, 0x4c, 0xaf, 0xe9, 0x49, 0x4f, 0xdb, 0xa0, - 0x25, 0xa4, 0xf0, 0x89, 0xf1, 0xbe, 0xd8, 0x10, - 0xff, 0xb1, 0x3b, 0x4b, 0xfa, 0x98, 0xf5, 0x79, - 0x6d, 0x1e, 0x69, 0x4d, 0x57, 0xb1, 0xc8, 0x19, - 0x1b, 0xbd, 0x1e, 0x8c, 0x84, 0xb7, 0x7b, 0xe8, - 0xd2, 0x2d, 0x09, 0x41, 0x41, 0x37, 0x3d, 0xb1, - 0x6f, 0x26, 0x5d, 0x71, 0x16, 0x3d, 0xb7, 0x83, - 0x27, 0x2c, 0xa7, 0xb6, 0x50, 0xbd, 0x91, 0x86, - 0xab, 0x24, 0xa1, 0x38, 0xfd, 0xea, 0x71, 0x55, - 0x7e, 0x9a, 0x07, 0x77, 0x4b, 0xfa, 0x61, 0x66, - 0x20, 0x1e, 0x28, 0x95, 0x18, 0x1b, 0xa4, 0xa0, - 0xfd, 0xc0, 0x89, 0x72, 0x43, 0xd9, 0x3b, 0x49, - 0x5a, 0x3f, 0x9d, 0xbf, 0xdb, 0xb4, 0x46, 0xea, - 0x42, 0x01, 0x77, 0x23, 0x68, 0x95, 0xb6, 0x24, - 0xb3, 0xa8, 0x6c, 0x28, 0x3b, 0x11, 0x40, 0x7e, - 0x18, 0x65, 0x6d, 0xd8, 0x24, 0x42, 0x7d, 0x88, - 0xc0, 0x52, 0xd9, 0x05, 0xe4, 0x95, 0x90, 0x87, - 0x8c, 0xf4, 0xd0, 0x6b, 0xb9, 0x83, 0x99, 0x34, - 0x6d, 0xfe, 0x54, 0x40, 0x94, 0x52, 0x21, 0x4f, - 0x14, 0x25, 0xc5, 0xd6, 0x5e, 0x95, 0xdc, 0x0a, - 0x2b, 0x89, 0x20, 0x11, 0x84, 0x48, 0xd6, 0x3a, - 0xcd, 0x5c, 0x24, 0xad, 0x62, 0xe3, 0xb1, 0x93, - 0x25, 0x8d, 0xcd, 0x7e, 0xfc, 0x27, 0xa3, 0x37, - 0xfd, 0x84, 0xfc, 0x1b, 0xb2, 0xf1, 0x27, 0x38, - 0x5a, 0xb7, 0xfc, 0xf2, 0xfa, 0x95, 0x66, 0xd4, - 0xfb, 0xba, 0xa7, 0xd7, 0xa3, 0x72, 0x69, 0x48, - 0x48, 0x8c, 0xeb, 0x28, 0x89, 0xfe, 0x33, 0x65, - 0x5a, 0x36, 0x01, 0x7e, 0x06, 0x79, 0x0a, 0x09, - 0x3b, 0x74, 0x11, 0x9a, 0x6e, 0xbf, 0xd4, 0x9e, - 0x58, 0x90, 0x49, 0x4f, 0x4d, 0x08, 0xd4, 0xe5, - 0x4a, 0x09, 0x21, 0xef, 0x8b, 0xb8, 0x74, 0x3b, - 0x91, 0xdd, 0x36, 0x85, 0x60, 0x2d, 0xfa, 0xd4, - 0x45, 0x7b, 0x45, 0x53, 0xf5, 0x47, 0x87, 0x7e, - 0xa6, 0x37, 0xc8, 0x78, 0x7a, 0x68, 0x9d, 0x8d, - 0x65, 0x2c, 0x0e, 0x91, 0x5c, 0xa2, 0x60, 0xf0, - 0x8e, 0x3f, 0xe9, 0x1a, 0xcd, 0xaa, 0xe7, 0xd5, - 0x77, 0x18, 0xaf, 0xc9, 0xbc, 0x18, 0xea, 0x48, - 0x1b, 0xfb, 0x22, 0x48, 0x70, 0x16, 0x29, 0x9e, - 0x5b, 0xc1, 0x2c, 0x66, 0x23, 0xbc, 0xf0, 0x1f, - 0xef, 0xaf, 0xe4, 0xd6, 0x04, 0x19, 0x82, 0x7a, - 0x0b, 0xba, 0x4b, 0x46, 0xb1, 0x6a, 0x85, 0x5d, - 0xb4, 0x73, 0xd6, 0x21, 0xa1, 0x71, 0x60, 0x14, - 0xee, 0x0a, 0x77, 0xc4, 0x66, 0x2e, 0xf9, 0x69, - 0x30, 0xaf, 0x41, 0x0b, 0xc8, 0x83, 0x3c, 0x53, - 0x99, 0x19, 0x27, 0x46, 0xf7, 0x41, 0x6e, 0x56, - 0xdc, 0x94, 0x28, 0x67, 0x4e, 0xb7, 0x25, 0x48, - 0x8a, 0xc2, 0xe0, 0x60, 0x96, 0xcc, 0x18, 0xf4, - 0x84, 0xdd, 0xa7, 0x5e, 0x3e, 0x05, 0x0b, 0x26, - 0x26, 0xb2, 0x5c, 0x1f, 0x57, 0x1a, 0x04, 0x7e, - 0x6a, 0xe3, 0x2f, 0xb4, 0x35, 0xb6, 0x38, 0x40, - 0x40, 0xcd, 0x6f, 0x87, 0x2e, 0xef, 0xa3, 0xd7, - 0xa9, 0xc2, 0xe8, 0x0d, 0x27, 0xdf, 0x44, 0x62, - 0x99, 0xa0, 0xfc, 0xcf, 0x81, 0x78, 0xcb, 0xfe, - 0xe5, 0xa0, 0x03, 0x4e, 0x6c, 0xd7, 0xf4, 0xaf, - 0x7a, 0xbb, 0x61, 0x82, 0xfe, 0x71, 0x89, 0xb2, - 0x22, 0x7c, 0x8e, 0x83, 0x04, 0xce, 0xf6, 0x5d, - 0x84, 0x8f, 0x95, 0x6a, 0x7f, 0xad, 0xfd, 0x32, - 0x9c, 0x5e, 0xe4, 0x9c, 0x89, 0x60, 0x54, 0xaa, - 0x96, 0x72, 0xd2, 0xd7, 0x36, 0x85, 0xa9, 0x45, - 0xd2, 0x2a, 0xa1, 0x81, 0x49, 0x6f, 0x7e, 0x04, - 0xfa, 0xe2, 0xfe, 0x90, 0x26, 0x77, 0x5a, 0x33, - 0xb8, 0x04, 0x9a, 0x7a, 0xe6, 0x4c, 0x4f, 0xad, - 0x72, 0x96, 0x08, 0x28, 0x58, 0x13, 0xf8, 0xc4, - 0x1c, 0xf0, 0xc3, 0x45, 0x95, 0x49, 0x20, 0x8c, - 0x9f, 0x39, 0x70, 0xe1, 0x77, 0xfe, 0xd5, 0x4b, - 0xaf, 0x86, 0xda, 0xef, 0x22, 0x06, 0x83, 0x36, - 0x29, 0x12, 0x11, 0x40, 0xbc, 0x3b, 0x86, 0xaa, - 0xaa, 0x65, 0x60, 0xc3, 0x80, 0xca, 0xed, 0xa9, - 0xf3, 0xb0, 0x79, 0x96, 0xa2, 0x55, 0x27, 0x28, - 0x55, 0x73, 0x26, 0xa5, 0x50, 0xea, 0x92, 0x4b, - 0x3c, 0x5c, 0x82, 0x33, 0xf0, 0x01, 0x3f, 0x03, - 0xc1, 0x08, 0x05, 0xbf, 0x98, 0xf4, 0x9b, 0x6d, - 0xa5, 0xa8, 0xb4, 0x82, 0x0c, 0x06, 0xfa, 0xff, - 0x2d, 0x08, 0xf3, 0x05, 0x4f, 0x57, 0x2a, 0x39, - 0xd4, 0x83, 0x0d, 0x75, 0x51, 0xd8, 0x5b, 0x1b, - 0xd3, 0x51, 0x5a, 0x32, 0x2a, 0x9b, 0x32, 0xb2, - 0xf2, 0xa4, 0x96, 0x12, 0xf2, 0xae, 0x40, 0x34, - 0x67, 0xa8, 0xf5, 0x44, 0xd5, 0x35, 0x53, 0xfe, - 0xa3, 0x60, 0x96, 0x63, 0x0f, 0x1f, 0x6e, 0xb0, - 0x5a, 0x42, 0xa6, 0xfc, 0x51, 0x0b, 0x60, 0x27, - 0xbc, 0x06, 0x71, 0xed, 0x65, 0x5b, 0x23, 0x86, - 0x4a, 0x07, 0x3b, 0x22, 0x07, 0x46, 0xe6, 0x90, - 0x3e, 0xf3, 0x25, 0x50, 0x1b, 0x4c, 0x7f, 0x03, - 0x08, 0xa8, 0x36, 0x6b, 0x87, 0xe5, 0xe3, 0xdb, - 0x9a, 0x38, 0x83, 0xff, 0x9f, 0x1a, 0x9f, 0x57, - 0xa4, 0x2a, 0xf6, 0x37, 0xbc, 0x1a, 0xff, 0xc9, - 0x1e, 0x35, 0x0c, 0xc3, 0x7c, 0xa3, 0xb2, 0xe5, - 0xd2, 0xc6, 0xb4, 0x57, 0x47, 0xe4, 0x32, 0x16, - 0x6d, 0xa9, 0xae, 0x64, 0xe6, 0x2d, 0x8d, 0xc5, - 0x8d, 0x50, 0x8e, 0xe8, 0x1a, 0x22, 0x34, 0x2a, - 0xd9, 0xeb, 0x51, 0x90, 0x4a, 0xb1, 0x41, 0x7d, - 0x64, 0xf9, 0xb9, 0x0d, 0xf6, 0x23, 0x33, 0xb0, - 0x33, 0xf4, 0xf7, 0x3f, 0x27, 0x84, 0xc6, 0x0f, - 0x54, 0xa5, 0xc0, 0x2e, 0xec, 0x0b, 0x3a, 0x48, - 0x6e, 0x80, 0x35, 0x81, 0x43, 0x9b, 0x90, 0xb1, - 0xd0, 0x2b, 0xea, 0x21, 0xdc, 0xda, 0x5b, 0x09, - 0xf4, 0xcc, 0x10, 0xb4, 0xc7, 0xfe, 0x79, 0x51, - 0xc3, 0xc5, 0xac, 0x88, 0x74, 0x84, 0x0b, 0x4b, - 0xca, 0x79, 0x16, 0x29, 0xfb, 0x69, 0x54, 0xdf, - 0x41, 0x7e, 0xe9, 0xc7, 0x8e, 0xea, 0xa5, 0xfe, - 0xfc, 0x76, 0x0e, 0x90, 0xc4, 0x92, 0x38, 0xad, - 0x7b, 0x48, 0xe6, 0x6e, 0xf7, 0x21, 0xfd, 0x4e, - 0x93, 0x0a, 0x7b, 0x41, 0x83, 0x68, 0xfb, 0x57, - 0x51, 0x76, 0x34, 0xa9, 0x6c, 0x00, 0xaa, 0x4f, - 0x66, 0x65, 0x98, 0x4a, 0x4f, 0xa3, 0xa0, 0xef, - 0x69, 0x3f, 0xe3, 0x1c, 0x92, 0x8c, 0xfd, 0xd8, - 0xe8, 0xde, 0x7c, 0x7f, 0x3e, 0x84, 0x8e, 0x69, - 0x3c, 0xf1, 0xf2, 0x05, 0x46, 0xdc, 0x2f, 0x9d, - 0x5e, 0x6e, 0x4c, 0xfb, 0xb5, 0x99, 0x2a, 0x59, - 0x63, 0xc1, 0x34, 0xbc, 0x57, 0xc0, 0x0d, 0xb9, - 0x61, 0x25, 0xf3, 0x33, 0x23, 0x51, 0xb6, 0x0d, - 0x07, 0xa6, 0xab, 0x94, 0x4a, 0xb7, 0x2a, 0xea, - 0xee, 0xac, 0xa3, 0xc3, 0x04, 0x8b, 0x0e, 0x56, - 0xfe, 0x44, 0xa7, 0x39, 0xe2, 0xed, 0xed, 0xb4, - 0x22, 0x2b, 0xac, 0x12, 0x32, 0x28, 0x91, 0xd8, - 0xa5, 0xab, 0xff, 0x5f, 0xe0, 0x4b, 0xda, 0x78, - 0x17, 0xda, 0xf1, 0x01, 0x5b, 0xcd, 0xe2, 0x5f, - 0x50, 0x45, 0x73, 0x2b, 0xe4, 0x76, 0x77, 0xf4, - 0x64, 0x1d, 0x43, 0xfb, 0x84, 0x7a, 0xea, 0x91, - 0xae, 0xf9, 0x9e, 0xb7, 0xb4, 0xb0, 0x91, 0x5f, - 0x16, 0x35, 0x9a, 0x11, 0xb8, 0xc7, 0xc1, 0x8c, - 0xc6, 0x10, 0x8d, 0x2f, 0x63, 0x4a, 0xa7, 0x57, - 0x3a, 0x51, 0xd6, 0x32, 0x2d, 0x64, 0x72, 0xd4, - 0x66, 0xdc, 0x10, 0xa6, 0x67, 0xd6, 0x04, 0x23, - 0x9d, 0x0a, 0x11, 0x77, 0xdd, 0x37, 0x94, 0x17, - 0x3c, 0xbf, 0x8b, 0x65, 0xb0, 0x2e, 0x5e, 0x66, - 0x47, 0x64, 0xac, 0xdd, 0xf0, 0x84, 0xfd, 0x39, - 0xfa, 0x15, 0x5d, 0xef, 0xae, 0xca, 0xc1, 0x36, - 0xa7, 0x5c, 0xbf, 0xc7, 0x08, 0xc2, 0x66, 0x00, - 0x74, 0x74, 0x4e, 0x27, 0x3f, 0x55, 0x8a, 0xb7, - 0x38, 0x66, 0x83, 0x6d, 0xcf, 0x99, 0x9e, 0x60, - 0x8f, 0xdd, 0x2e, 0x62, 0x22, 0x0e, 0xef, 0x0c, - 0x98, 0xa7, 0x85, 0x74, 0x3b, 0x9d, 0xec, 0x9e, - 0xa9, 0x19, 0x72, 0xa5, 0x7f, 0x2c, 0x39, 0xb7, - 0x7d, 0xb7, 0xf1, 0x12, 0x65, 0x27, 0x4b, 0x5a, - 0xde, 0x17, 0xfe, 0xad, 0x44, 0xf3, 0x20, 0x4d, - 0xfd, 0xe4, 0x1f, 0xb5, 0x81, 0xb0, 0x36, 0x37, - 0x08, 0x6f, 0xc3, 0x0c, 0xe9, 0x85, 0x98, 0x82, - 0xa9, 0x62, 0x0c, 0xc4, 0x97, 0xc0, 0x50, 0xc8, - 0xa7, 0x3c, 0x50, 0x9f, 0x43, 0xb9, 0xcd, 0x5e, - 0x4d, 0xfa, 0x1c, 0x4b, 0x0b, 0xa9, 0x98, 0x85, - 0x38, 0x92, 0xac, 0x8d, 0xe4, 0xad, 0x9b, 0x98, - 0xab, 0xd9, 0x38, 0xac, 0x62, 0x52, 0xa3, 0x22, - 0x63, 0x0f, 0xbf, 0x95, 0x48, 0xdf, 0x69, 0xe7, - 0x8b, 0x33, 0xd5, 0xb2, 0xbd, 0x05, 0x49, 0x49, - 0x9d, 0x57, 0x73, 0x19, 0x33, 0xae, 0xfa, 0x33, - 0xf1, 0x19, 0xa8, 0x80, 0xce, 0x04, 0x9f, 0xbc, - 0x1d, 0x65, 0x82, 0x1b, 0xe5, 0x3a, 0x51, 0xc8, - 0x1c, 0x21, 0xe3, 0x5d, 0xf3, 0x7d, 0x9b, 0x2f, - 0x2c, 0x1d, 0x4a, 0x7f, 0x9b, 0x68, 0x35, 0xa3, - 0xb2, 0x50, 0xf7, 0x62, 0x79, 0xcd, 0xf4, 0x98, - 0x4f, 0xe5, 0x63, 0x7c, 0x3e, 0x45, 0x31, 0x8c, - 0x16, 0xa0, 0x12, 0xc8, 0x58, 0xce, 0x39, 0xa6, - 0xbc, 0x54, 0xdb, 0xc5, 0xe0, 0xd5, 0xba, 0xbc, - 0xb9, 0x04, 0xf4, 0x8d, 0xe8, 0x2f, 0x15, 0x9d, -}; - -/* 100 test cases */ -static struct crc_test { - u32 crc; /* random starting crc */ - u32 start; /* random 6 bit offset in buf */ - u32 length; /* random 11 bit length of test */ - u32 crc_le; /* expected crc32_le result */ - u32 crc_be; /* expected crc32_be result */ - u32 crc32c_le; /* expected crc32c_le result */ -} const test[] __initconst = -{ - {0x674bf11d, 0x00000038, 0x00000542, 0x0af6d466, 0xd8b6e4c1, 0xf6e93d6c}, - {0x35c672c6, 0x0000003a, 0x000001aa, 0xc6d3dfba, 0x28aaf3ad, 0x0fe92aca}, - {0x496da28e, 0x00000039, 0x000005af, 0xd933660f, 0x5d57e81f, 0x52e1ebb8}, - {0x09a9b90e, 0x00000027, 0x000001f8, 0xb45fe007, 0xf45fca9a, 0x0798af9a}, - {0xdc97e5a9, 0x00000025, 0x000003b6, 0xf81a3562, 0xe0126ba2, 0x18eb3152}, - {0x47c58900, 0x0000000a, 0x000000b9, 0x8e58eccf, 0xf3afc793, 0xd00d08c7}, - {0x292561e8, 0x0000000c, 0x00000403, 0xa2ba8aaf, 0x0b797aed, 0x8ba966bc}, - {0x415037f6, 0x00000003, 0x00000676, 0xa17d52e8, 0x7f0fdf35, 0x11d694a2}, - {0x3466e707, 0x00000026, 0x00000042, 0x258319be, 0x75c484a2, 0x6ab3208d}, - {0xafd1281b, 0x00000023, 0x000002ee, 0x4428eaf8, 0x06c7ad10, 0xba4603c5}, - {0xd3857b18, 0x00000028, 0x000004a2, 0x5c430821, 0xb062b7cb, 0xe6071c6f}, - {0x1d825a8f, 0x0000002b, 0x0000050b, 0xd2c45f0c, 0xd68634e0, 0x179ec30a}, - {0x5033e3bc, 0x0000000b, 0x00000078, 0xa3ea4113, 0xac6d31fb, 0x0903beb8}, - {0x94f1fb5e, 0x0000000f, 0x000003a2, 0xfbfc50b1, 0x3cfe50ed, 0x6a7cb4fa}, - {0xc9a0fe14, 0x00000009, 0x00000473, 0x5fb61894, 0x87070591, 0xdb535801}, - {0x88a034b1, 0x0000001c, 0x000005ad, 0xc1b16053, 0x46f95c67, 0x92bed597}, - {0xf0f72239, 0x00000020, 0x0000026d, 0xa6fa58f3, 0xf8c2c1dd, 0x192a3f1b}, - {0xcc20a5e3, 0x0000003b, 0x0000067a, 0x7740185a, 0x308b979a, 0xccbaec1a}, - {0xce589c95, 0x0000002b, 0x00000641, 0xd055e987, 0x40aae25b, 0x7eabae4d}, - {0x78edc885, 0x00000035, 0x000005be, 0xa39cb14b, 0x035b0d1f, 0x28c72982}, - {0x9d40a377, 0x0000003b, 0x00000038, 0x1f47ccd2, 0x197fbc9d, 0xc3cd4d18}, - {0x703d0e01, 0x0000003c, 0x000006f1, 0x88735e7c, 0xfed57c5a, 0xbca8f0e7}, - {0x776bf505, 0x0000000f, 0x000005b2, 0x5cc4fc01, 0xf32efb97, 0x713f60b3}, - {0x4a3e7854, 0x00000027, 0x000004b8, 0x8d923c82, 0x0cbfb4a2, 0xebd08fd5}, - {0x209172dd, 0x0000003b, 0x00000356, 0xb89e9c2b, 0xd7868138, 0x64406c59}, - {0x3ba4cc5b, 0x0000002f, 0x00000203, 0xe51601a9, 0x5b2a1032, 0x7421890e}, - {0xfc62f297, 0x00000000, 0x00000079, 0x71a8e1a2, 0x5d88685f, 0xe9347603}, - {0x64280b8b, 0x00000016, 0x000007ab, 0x0fa7a30c, 0xda3a455f, 0x1bef9060}, - {0x97dd724b, 0x00000033, 0x000007ad, 0x5788b2f4, 0xd7326d32, 0x34720072}, - {0x61394b52, 0x00000035, 0x00000571, 0xc66525f1, 0xcabe7fef, 0x48310f59}, - {0x29b4faff, 0x00000024, 0x0000006e, 0xca13751e, 0x993648e0, 0x783a4213}, - {0x29bfb1dc, 0x0000000b, 0x00000244, 0x436c43f7, 0x429f7a59, 0x9e8efd41}, - {0x86ae934b, 0x00000035, 0x00000104, 0x0760ec93, 0x9cf7d0f4, 0xfc3d34a5}, - {0xc4c1024e, 0x0000002e, 0x000006b1, 0x6516a3ec, 0x19321f9c, 0x17a52ae2}, - {0x3287a80a, 0x00000026, 0x00000496, 0x0b257eb1, 0x754ebd51, 0x886d935a}, - {0xa4db423e, 0x00000023, 0x0000045d, 0x9b3a66dc, 0x873e9f11, 0xeaaeaeb2}, - {0x7a1078df, 0x00000015, 0x0000014a, 0x8c2484c5, 0x6a628659, 0x8e900a4b}, - {0x6048bd5b, 0x00000006, 0x0000006a, 0x897e3559, 0xac9961af, 0xd74662b1}, - {0xd8f9ea20, 0x0000003d, 0x00000277, 0x60eb905b, 0xed2aaf99, 0xd26752ba}, - {0xea5ec3b4, 0x0000002a, 0x000004fe, 0x869965dc, 0x6c1f833b, 0x8b1fcd62}, - {0x2dfb005d, 0x00000016, 0x00000345, 0x6a3b117e, 0xf05e8521, 0xf54342fe}, - {0x5a214ade, 0x00000020, 0x000005b6, 0x467f70be, 0xcb22ccd3, 0x5b95b988}, - {0xf0ab9cca, 0x00000032, 0x00000515, 0xed223df3, 0x7f3ef01d, 0x2e1176be}, - {0x91b444f9, 0x0000002e, 0x000007f8, 0x84e9a983, 0x5676756f, 0x66120546}, - {0x1b5d2ddb, 0x0000002e, 0x0000012c, 0xba638c4c, 0x3f42047b, 0xf256a5cc}, - {0xd824d1bb, 0x0000003a, 0x000007b5, 0x6288653b, 0x3a3ebea0, 0x4af1dd69}, - {0x0470180c, 0x00000034, 0x000001f0, 0x9d5b80d6, 0x3de08195, 0x56f0a04a}, - {0xffaa3a3f, 0x00000036, 0x00000299, 0xf3a82ab8, 0x53e0c13d, 0x74f6b6b2}, - {0x6406cfeb, 0x00000023, 0x00000600, 0xa920b8e8, 0xe4e2acf4, 0x085951fd}, - {0xb24aaa38, 0x0000003e, 0x000004a1, 0x657cc328, 0x5077b2c3, 0xc65387eb}, - {0x58b2ab7c, 0x00000039, 0x000002b4, 0x3a17ee7e, 0x9dcb3643, 0x1ca9257b}, - {0x3db85970, 0x00000006, 0x000002b6, 0x95268b59, 0xb9812c10, 0xfd196d76}, - {0x857830c5, 0x00000003, 0x00000590, 0x4ef439d5, 0xf042161d, 0x5ef88339}, - {0xe1fcd978, 0x0000003e, 0x000007d8, 0xae8d8699, 0xce0a1ef5, 0x2c3714d9}, - {0xb982a768, 0x00000016, 0x000006e0, 0x62fad3df, 0x5f8a067b, 0x58576548}, - {0x1d581ce8, 0x0000001e, 0x0000058b, 0xf0f5da53, 0x26e39eee, 0xfd7c57de}, - {0x2456719b, 0x00000025, 0x00000503, 0x4296ac64, 0xd50e4c14, 0xd5fedd59}, - {0xfae6d8f2, 0x00000000, 0x0000055d, 0x057fdf2e, 0x2a31391a, 0x1cc3b17b}, - {0xcba828e3, 0x00000039, 0x000002ce, 0xe3f22351, 0x8f00877b, 0x270eed73}, - {0x13d25952, 0x0000000a, 0x0000072d, 0x76d4b4cc, 0x5eb67ec3, 0x91ecbb11}, - {0x0342be3f, 0x00000015, 0x00000599, 0xec75d9f1, 0x9d4d2826, 0x05ed8d0c}, - {0xeaa344e0, 0x00000014, 0x000004d8, 0x72a4c981, 0x2064ea06, 0x0b09ad5b}, - {0xbbb52021, 0x0000003b, 0x00000272, 0x04af99fc, 0xaf042d35, 0xf8d511fb}, - {0xb66384dc, 0x0000001d, 0x000007fc, 0xd7629116, 0x782bd801, 0x5ad832cc}, - {0x616c01b6, 0x00000022, 0x000002c8, 0x5b1dab30, 0x783ce7d2, 0x1214d196}, - {0xce2bdaad, 0x00000016, 0x0000062a, 0x932535c8, 0x3f02926d, 0x5747218a}, - {0x00fe84d7, 0x00000005, 0x00000205, 0x850e50aa, 0x753d649c, 0xde8f14de}, - {0xbebdcb4c, 0x00000006, 0x0000055d, 0xbeaa37a2, 0x2d8c9eba, 0x3563b7b9}, - {0xd8b1a02a, 0x00000010, 0x00000387, 0x5017d2fc, 0x503541a5, 0x071475d0}, - {0x3b96cad2, 0x00000036, 0x00000347, 0x1d2372ae, 0x926cd90b, 0x54c79d60}, - {0xc94c1ed7, 0x00000005, 0x0000038b, 0x9e9fdb22, 0x144a9178, 0x4c53eee6}, - {0x1aad454e, 0x00000025, 0x000002b2, 0xc3f6315c, 0x5c7a35b3, 0x10137a3c}, - {0xa4fec9a6, 0x00000000, 0x000006d6, 0x90be5080, 0xa4107605, 0xaa9d6c73}, - {0x1bbe71e2, 0x0000001f, 0x000002fd, 0x4e504c3b, 0x284ccaf1, 0xb63d23e7}, - {0x4201c7e4, 0x00000002, 0x000002b7, 0x7822e3f9, 0x0cc912a9, 0x7f53e9cf}, - {0x23fddc96, 0x00000003, 0x00000627, 0x8a385125, 0x07767e78, 0x13c1cd83}, - {0xd82ba25c, 0x00000016, 0x0000063e, 0x98e4148a, 0x283330c9, 0x49ff5867}, - {0x786f2032, 0x0000002d, 0x0000060f, 0xf201600a, 0xf561bfcd, 0x8467f211}, - {0xfebe4e1f, 0x0000002a, 0x000004f2, 0x95e51961, 0xfd80dcab, 0x3f9683b2}, - {0x1a6e0a39, 0x00000008, 0x00000672, 0x8af6c2a5, 0x78dd84cb, 0x76a3f874}, - {0x56000ab8, 0x0000000e, 0x000000e5, 0x36bacb8f, 0x22ee1f77, 0x863b702f}, - {0x4717fe0c, 0x00000000, 0x000006ec, 0x8439f342, 0x5c8e03da, 0xdc6c58ff}, - {0xd5d5d68e, 0x0000003c, 0x000003a3, 0x46fff083, 0x177d1b39, 0x0622cc95}, - {0xc25dd6c6, 0x00000024, 0x000006c0, 0x5ceb8eb4, 0x892b0d16, 0xe85605cd}, - {0xe9b11300, 0x00000023, 0x00000683, 0x07a5d59a, 0x6c6a3208, 0x31da5f06}, - {0x95cd285e, 0x00000001, 0x00000047, 0x7b3a4368, 0x0202c07e, 0xa1f2e784}, - {0xd9245a25, 0x0000001e, 0x000003a6, 0xd33c1841, 0x1936c0d5, 0xb07cc616}, - {0x103279db, 0x00000006, 0x0000039b, 0xca09b8a0, 0x77d62892, 0xbf943b6c}, - {0x1cba3172, 0x00000027, 0x000001c8, 0xcb377194, 0xebe682db, 0x2c01af1c}, - {0x8f613739, 0x0000000c, 0x000001df, 0xb4b0bc87, 0x7710bd43, 0x0fe5f56d}, - {0x1c6aa90d, 0x0000001b, 0x0000053c, 0x70559245, 0xda7894ac, 0xf8943b2d}, - {0xaabe5b93, 0x0000003d, 0x00000715, 0xcdbf42fa, 0x0c3b99e7, 0xe4d89272}, - {0xf15dd038, 0x00000006, 0x000006db, 0x6e104aea, 0x8d5967f2, 0x7c2f6bbb}, - {0x584dd49c, 0x00000020, 0x000007bc, 0x36b6cfd6, 0xad4e23b2, 0xabbf388b}, - {0x5d8c9506, 0x00000020, 0x00000470, 0x4c62378e, 0x31d92640, 0x1dca1f4e}, - {0xb80d17b0, 0x00000032, 0x00000346, 0x22a5bb88, 0x9a7ec89f, 0x5c170e23}, - {0xdaf0592e, 0x00000023, 0x000007b0, 0x3cab3f99, 0x9b1fdd99, 0xc0e9d672}, - {0x4793cc85, 0x0000000d, 0x00000706, 0xe82e04f6, 0xed3db6b7, 0xc18bdc86}, - {0x82ebf64e, 0x00000009, 0x000007c3, 0x69d590a9, 0x9efa8499, 0xa874fcdd}, - {0xb18a0319, 0x00000026, 0x000007db, 0x1cf98dcc, 0x8fa9ad6a, 0x9dc0bb48}, -}; - -#include <linux/time.h> - -static int __init crc32c_test(void) -{ - int i; - int errors = 0; - int bytes = 0; - u64 nsec; - unsigned long flags; - - /* keep static to prevent cache warming code from - * getting eliminated by the compiler */ - static u32 crc; - - /* pre-warm the cache */ - for (i = 0; i < 100; i++) { - bytes += test[i].length; - - crc ^= __crc32c_le(test[i].crc, test_buf + - test[i].start, test[i].length); - } - - /* reduce OS noise */ - local_irq_save(flags); - - nsec = ktime_get_ns(); - for (i = 0; i < 100; i++) { - if (test[i].crc32c_le != __crc32c_le(test[i].crc, test_buf + - test[i].start, test[i].length)) - errors++; - } - nsec = ktime_get_ns() - nsec; - - local_irq_restore(flags); - - pr_info("crc32c: CRC_LE_BITS = %d\n", CRC_LE_BITS); - - if (errors) - pr_warn("crc32c: %d self tests failed\n", errors); - else { - pr_info("crc32c: self tests passed, processed %d bytes in %lld nsec\n", - bytes, nsec); - } - - return 0; -} - -static int __init crc32c_combine_test(void) -{ - int i, j; - int errors = 0, runs = 0; - - for (i = 0; i < 10; i++) { - u32 crc_full; - - crc_full = __crc32c_le(test[i].crc, test_buf + test[i].start, - test[i].length); - for (j = 0; j <= test[i].length; ++j) { - u32 crc1, crc2; - u32 len1 = j, len2 = test[i].length - j; - - crc1 = __crc32c_le(test[i].crc, test_buf + - test[i].start, len1); - crc2 = __crc32c_le(0, test_buf + test[i].start + - len1, len2); - - if (!(crc_full == __crc32c_le_combine(crc1, crc2, len2) && - crc_full == test[i].crc32c_le)) - errors++; - runs++; - cond_resched(); - } - } - - if (errors) - pr_warn("crc32c_combine: %d/%d self tests failed\n", errors, runs); - else - pr_info("crc32c_combine: %d self tests passed\n", runs); - - return 0; -} - -static int __init crc32_test(void) -{ - int i; - int errors = 0; - int bytes = 0; - u64 nsec; - unsigned long flags; - - /* keep static to prevent cache warming code from - * getting eliminated by the compiler */ - static u32 crc; - - /* pre-warm the cache */ - for (i = 0; i < 100; i++) { - bytes += 2*test[i].length; - - crc ^= crc32_le(test[i].crc, test_buf + - test[i].start, test[i].length); - - crc ^= crc32_be(test[i].crc, test_buf + - test[i].start, test[i].length); - } - - /* reduce OS noise */ - local_irq_save(flags); - - nsec = ktime_get_ns(); - for (i = 0; i < 100; i++) { - if (test[i].crc_le != crc32_le(test[i].crc, test_buf + - test[i].start, test[i].length)) - errors++; - - if (test[i].crc_be != crc32_be(test[i].crc, test_buf + - test[i].start, test[i].length)) - errors++; - } - nsec = ktime_get_ns() - nsec; - - local_irq_restore(flags); - - pr_info("crc32: CRC_LE_BITS = %d, CRC_BE BITS = %d\n", - CRC_LE_BITS, CRC_BE_BITS); - - if (errors) - pr_warn("crc32: %d self tests failed\n", errors); - else { - pr_info("crc32: self tests passed, processed %d bytes in %lld nsec\n", - bytes, nsec); - } - - return 0; -} - -static int __init crc32_combine_test(void) -{ - int i, j; - int errors = 0, runs = 0; - - for (i = 0; i < 10; i++) { - u32 crc_full; - - crc_full = crc32_le(test[i].crc, test_buf + test[i].start, - test[i].length); - for (j = 0; j <= test[i].length; ++j) { - u32 crc1, crc2; - u32 len1 = j, len2 = test[i].length - j; - - crc1 = crc32_le(test[i].crc, test_buf + - test[i].start, len1); - crc2 = crc32_le(0, test_buf + test[i].start + - len1, len2); - - if (!(crc_full == crc32_le_combine(crc1, crc2, len2) && - crc_full == test[i].crc_le)) - errors++; - runs++; - cond_resched(); - } - } - - if (errors) - pr_warn("crc32_combine: %d/%d self tests failed\n", errors, runs); - else - pr_info("crc32_combine: %d self tests passed\n", runs); - - return 0; -} - -static int __init crc32test_init(void) -{ - crc32_test(); - crc32c_test(); - - crc32_combine_test(); - crc32c_combine_test(); - - return 0; -} - -static void __exit crc32_exit(void) -{ -} - -module_init(crc32test_init); -module_exit(crc32_exit); - -MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>"); -MODULE_DESCRIPTION("CRC32 selftest"); -MODULE_LICENSE("GPL"); diff --git a/lib/crc_kunit.c b/lib/crc_kunit.c new file mode 100644 index 000000000000..6a61d4b5fd45 --- /dev/null +++ b/lib/crc_kunit.c @@ -0,0 +1,435 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Unit tests and benchmarks for the CRC library functions + * + * Copyright 2024 Google LLC + * + * Author: Eric Biggers <ebiggers@google.com> + */ +#include <kunit/test.h> +#include <linux/crc16.h> +#include <linux/crc-t10dif.h> +#include <linux/crc32.h> +#include <linux/crc32c.h> +#include <linux/crc64.h> +#include <linux/prandom.h> +#include <linux/vmalloc.h> + +#define CRC_KUNIT_SEED 42 +#define CRC_KUNIT_MAX_LEN 16384 +#define CRC_KUNIT_NUM_TEST_ITERS 1000 + +static struct rnd_state rng; +static u8 *test_buffer; +static size_t test_buflen; + +/** + * struct crc_variant - describes a CRC variant + * @bits: Number of bits in the CRC, 1 <= @bits <= 64. + * @le: true if it's a "little endian" CRC (reversed mapping between bits and + * polynomial coefficients in each byte), false if it's a "big endian" CRC + * (natural mapping between bits and polynomial coefficients in each byte) + * @poly: The generator polynomial with the highest-order term omitted. + * Bit-reversed if @le is true. + * @func: The function to compute a CRC. The type signature uses u64 so that it + * can fit any CRC up to CRC-64. + * @combine_func: Optional function to combine two CRCs. + */ +struct crc_variant { + int bits; + bool le; + u64 poly; + u64 (*func)(u64 crc, const u8 *p, size_t len); + u64 (*combine_func)(u64 crc1, u64 crc2, size_t len2); +}; + +static u32 rand32(void) +{ + return prandom_u32_state(&rng); +} + +static u64 rand64(void) +{ + u32 n = rand32(); + + return ((u64)n << 32) | rand32(); +} + +static u64 crc_mask(const struct crc_variant *v) +{ + return (u64)-1 >> (64 - v->bits); +} + +/* Reference implementation of any CRC variant */ +static u64 crc_ref(const struct crc_variant *v, + u64 crc, const u8 *p, size_t len) +{ + size_t i, j; + + for (i = 0; i < len; i++) { + for (j = 0; j < 8; j++) { + if (v->le) { + crc ^= (p[i] >> j) & 1; + crc = (crc >> 1) ^ ((crc & 1) ? v->poly : 0); + } else { + crc ^= (u64)((p[i] >> (7 - j)) & 1) << + (v->bits - 1); + if (crc & (1ULL << (v->bits - 1))) + crc = ((crc << 1) ^ v->poly) & + crc_mask(v); + else + crc <<= 1; + } + } + } + return crc; +} + +static int crc_suite_init(struct kunit_suite *suite) +{ + /* + * Allocate the test buffer using vmalloc() with a page-aligned length + * so that it is immediately followed by a guard page. This allows + * buffer overreads to be detected, even in assembly code. + */ + test_buflen = round_up(CRC_KUNIT_MAX_LEN, PAGE_SIZE); + test_buffer = vmalloc(test_buflen); + if (!test_buffer) + return -ENOMEM; + + prandom_seed_state(&rng, CRC_KUNIT_SEED); + prandom_bytes_state(&rng, test_buffer, test_buflen); + return 0; +} + +static void crc_suite_exit(struct kunit_suite *suite) +{ + vfree(test_buffer); + test_buffer = NULL; +} + +/* Generate a random initial CRC. */ +static u64 generate_random_initial_crc(const struct crc_variant *v) +{ + switch (rand32() % 4) { + case 0: + return 0; + case 1: + return crc_mask(v); /* All 1 bits */ + default: + return rand64() & crc_mask(v); + } +} + +/* Generate a random length, preferring small lengths. */ +static size_t generate_random_length(size_t max_length) +{ + size_t len; + + switch (rand32() % 3) { + case 0: + len = rand32() % 128; + break; + case 1: + len = rand32() % 3072; + break; + default: + len = rand32(); + break; + } + return len % (max_length + 1); +} + +/* Test that v->func gives the same CRCs as a reference implementation. */ +static void crc_main_test(struct kunit *test, const struct crc_variant *v) +{ + size_t i; + + for (i = 0; i < CRC_KUNIT_NUM_TEST_ITERS; i++) { + u64 init_crc, expected_crc, actual_crc; + size_t len, offset; + bool nosimd; + + init_crc = generate_random_initial_crc(v); + len = generate_random_length(CRC_KUNIT_MAX_LEN); + + /* Generate a random offset. */ + if (rand32() % 2 == 0) { + /* Use a random alignment mod 64 */ + offset = rand32() % 64; + offset = min(offset, CRC_KUNIT_MAX_LEN - len); + } else { + /* Go up to the guard page, to catch buffer overreads */ + offset = test_buflen - len; + } + + if (rand32() % 8 == 0) + /* Refresh the data occasionally. */ + prandom_bytes_state(&rng, &test_buffer[offset], len); + + nosimd = rand32() % 8 == 0; + + /* + * Compute the CRC, and verify that it equals the CRC computed + * by a simple bit-at-a-time reference implementation. + */ + expected_crc = crc_ref(v, init_crc, &test_buffer[offset], len); + if (nosimd) + local_irq_disable(); + actual_crc = v->func(init_crc, &test_buffer[offset], len); + if (nosimd) + local_irq_enable(); + KUNIT_EXPECT_EQ_MSG(test, expected_crc, actual_crc, + "Wrong result with len=%zu offset=%zu nosimd=%d", + len, offset, nosimd); + } +} + +/* Test that CRC(concat(A, B)) == combine_CRCs(CRC(A), CRC(B), len(B)). */ +static void crc_combine_test(struct kunit *test, const struct crc_variant *v) +{ + int i; + + for (i = 0; i < 100; i++) { + u64 init_crc = generate_random_initial_crc(v); + size_t len1 = generate_random_length(CRC_KUNIT_MAX_LEN); + size_t len2 = generate_random_length(CRC_KUNIT_MAX_LEN - len1); + u64 crc1, crc2, expected_crc, actual_crc; + + prandom_bytes_state(&rng, test_buffer, len1 + len2); + crc1 = v->func(init_crc, test_buffer, len1); + crc2 = v->func(0, &test_buffer[len1], len2); + expected_crc = v->func(init_crc, test_buffer, len1 + len2); + actual_crc = v->combine_func(crc1, crc2, len2); + KUNIT_EXPECT_EQ_MSG(test, expected_crc, actual_crc, + "CRC combination gave wrong result with len1=%zu len2=%zu\n", + len1, len2); + } +} + +static void crc_test(struct kunit *test, const struct crc_variant *v) +{ + crc_main_test(test, v); + if (v->combine_func) + crc_combine_test(test, v); +} + +static __always_inline void +crc_benchmark(struct kunit *test, + u64 (*crc_func)(u64 crc, const u8 *p, size_t len)) +{ + static const size_t lens_to_test[] = { + 1, 16, 64, 127, 128, 200, 256, 511, 512, 1024, 3173, 4096, 16384, + }; + size_t len, i, j, num_iters; + /* + * Some of the CRC library functions are marked as __pure, so use + * volatile to ensure that all calls are really made as intended. + */ + volatile u64 crc = 0; + u64 t; + + if (!IS_ENABLED(CONFIG_CRC_BENCHMARK)) + kunit_skip(test, "not enabled"); + + /* warm-up */ + for (i = 0; i < 10000000; i += CRC_KUNIT_MAX_LEN) + crc = crc_func(crc, test_buffer, CRC_KUNIT_MAX_LEN); + + for (i = 0; i < ARRAY_SIZE(lens_to_test); i++) { + len = lens_to_test[i]; + KUNIT_ASSERT_LE(test, len, CRC_KUNIT_MAX_LEN); + num_iters = 10000000 / (len + 128); + preempt_disable(); + t = ktime_get_ns(); + for (j = 0; j < num_iters; j++) + crc = crc_func(crc, test_buffer, len); + t = ktime_get_ns() - t; + preempt_enable(); + kunit_info(test, "len=%zu: %llu MB/s\n", + len, div64_u64((u64)len * num_iters * 1000, t)); + } +} + +/* crc16 */ + +static u64 crc16_wrapper(u64 crc, const u8 *p, size_t len) +{ + return crc16(crc, p, len); +} + +static const struct crc_variant crc_variant_crc16 = { + .bits = 16, + .le = true, + .poly = 0xa001, + .func = crc16_wrapper, +}; + +static void crc16_test(struct kunit *test) +{ + crc_test(test, &crc_variant_crc16); +} + +static void crc16_benchmark(struct kunit *test) +{ + crc_benchmark(test, crc16_wrapper); +} + +/* crc_t10dif */ + +static u64 crc_t10dif_wrapper(u64 crc, const u8 *p, size_t len) +{ + return crc_t10dif_update(crc, p, len); +} + +static const struct crc_variant crc_variant_crc_t10dif = { + .bits = 16, + .le = false, + .poly = 0x8bb7, + .func = crc_t10dif_wrapper, +}; + +static void crc_t10dif_test(struct kunit *test) +{ + crc_test(test, &crc_variant_crc_t10dif); +} + +static void crc_t10dif_benchmark(struct kunit *test) +{ + crc_benchmark(test, crc_t10dif_wrapper); +} + +/* crc32_le */ + +static u64 crc32_le_wrapper(u64 crc, const u8 *p, size_t len) +{ + return crc32_le(crc, p, len); +} + +static u64 crc32_le_combine_wrapper(u64 crc1, u64 crc2, size_t len2) +{ + return crc32_le_combine(crc1, crc2, len2); +} + +static const struct crc_variant crc_variant_crc32_le = { + .bits = 32, + .le = true, + .poly = 0xedb88320, + .func = crc32_le_wrapper, + .combine_func = crc32_le_combine_wrapper, +}; + +static void crc32_le_test(struct kunit *test) +{ + crc_test(test, &crc_variant_crc32_le); +} + +static void crc32_le_benchmark(struct kunit *test) +{ + crc_benchmark(test, crc32_le_wrapper); +} + +/* crc32_be */ + +static u64 crc32_be_wrapper(u64 crc, const u8 *p, size_t len) +{ + return crc32_be(crc, p, len); +} + +static const struct crc_variant crc_variant_crc32_be = { + .bits = 32, + .le = false, + .poly = 0x04c11db7, + .func = crc32_be_wrapper, +}; + +static void crc32_be_test(struct kunit *test) +{ + crc_test(test, &crc_variant_crc32_be); +} + +static void crc32_be_benchmark(struct kunit *test) +{ + crc_benchmark(test, crc32_be_wrapper); +} + +/* crc32c */ + +static u64 crc32c_wrapper(u64 crc, const u8 *p, size_t len) +{ + return crc32c(crc, p, len); +} + +static u64 crc32c_combine_wrapper(u64 crc1, u64 crc2, size_t len2) +{ + return __crc32c_le_combine(crc1, crc2, len2); +} + +static const struct crc_variant crc_variant_crc32c = { + .bits = 32, + .le = true, + .poly = 0x82f63b78, + .func = crc32c_wrapper, + .combine_func = crc32c_combine_wrapper, +}; + +static void crc32c_test(struct kunit *test) +{ + crc_test(test, &crc_variant_crc32c); +} + +static void crc32c_benchmark(struct kunit *test) +{ + crc_benchmark(test, crc32c_wrapper); +} + +/* crc64_be */ + +static u64 crc64_be_wrapper(u64 crc, const u8 *p, size_t len) +{ + return crc64_be(crc, p, len); +} + +static const struct crc_variant crc_variant_crc64_be = { + .bits = 64, + .le = false, + .poly = 0x42f0e1eba9ea3693, + .func = crc64_be_wrapper, +}; + +static void crc64_be_test(struct kunit *test) +{ + crc_test(test, &crc_variant_crc64_be); +} + +static void crc64_be_benchmark(struct kunit *test) +{ + crc_benchmark(test, crc64_be_wrapper); +} + +static struct kunit_case crc_test_cases[] = { + KUNIT_CASE(crc16_test), + KUNIT_CASE(crc16_benchmark), + KUNIT_CASE(crc_t10dif_test), + KUNIT_CASE(crc_t10dif_benchmark), + KUNIT_CASE(crc32_le_test), + KUNIT_CASE(crc32_le_benchmark), + KUNIT_CASE(crc32_be_test), + KUNIT_CASE(crc32_be_benchmark), + KUNIT_CASE(crc32c_test), + KUNIT_CASE(crc32c_benchmark), + KUNIT_CASE(crc64_be_test), + KUNIT_CASE(crc64_be_benchmark), + {}, +}; + +static struct kunit_suite crc_test_suite = { + .name = "crc", + .test_cases = crc_test_cases, + .suite_init = crc_suite_init, + .suite_exit = crc_suite_exit, +}; +kunit_test_suite(crc_test_suite); + +MODULE_DESCRIPTION("Unit tests and benchmarks for the CRC library functions"); +MODULE_LICENSE("GPL"); diff --git a/lib/crypto/aesgcm.c b/lib/crypto/aesgcm.c index 6bba6473fdf3..902e49410aaf 100644 --- a/lib/crypto/aesgcm.c +++ b/lib/crypto/aesgcm.c @@ -697,7 +697,7 @@ static int __init libaesgcm_init(void) u8 tagbuf[AES_BLOCK_SIZE]; int plen = aesgcm_tv[i].plen; struct aesgcm_ctx ctx; - u8 buf[sizeof(ptext12)]; + static u8 buf[sizeof(ptext12)]; if (aesgcm_expandkey(&ctx, aesgcm_tv[i].key, aesgcm_tv[i].klen, aesgcm_tv[i].clen - plen)) { diff --git a/lib/crypto/gf128mul.c b/lib/crypto/gf128mul.c index 8f8c45e0cdcf..fbe72cb3453a 100644 --- a/lib/crypto/gf128mul.c +++ b/lib/crypto/gf128mul.c @@ -225,44 +225,6 @@ void gf128mul_lle(be128 *r, const be128 *b) } EXPORT_SYMBOL(gf128mul_lle); -void gf128mul_bbe(be128 *r, const be128 *b) -{ - be128 p[8]; - int i; - - p[0] = *r; - for (i = 0; i < 7; ++i) - gf128mul_x_bbe(&p[i + 1], &p[i]); - - memset(r, 0, sizeof(*r)); - for (i = 0;;) { - u8 ch = ((u8 *)b)[i]; - - if (ch & 0x80) - be128_xor(r, r, &p[7]); - if (ch & 0x40) - be128_xor(r, r, &p[6]); - if (ch & 0x20) - be128_xor(r, r, &p[5]); - if (ch & 0x10) - be128_xor(r, r, &p[4]); - if (ch & 0x08) - be128_xor(r, r, &p[3]); - if (ch & 0x04) - be128_xor(r, r, &p[2]); - if (ch & 0x02) - be128_xor(r, r, &p[1]); - if (ch & 0x01) - be128_xor(r, r, &p[0]); - - if (++i >= 16) - break; - - gf128mul_x8_bbe(r); - } -} -EXPORT_SYMBOL(gf128mul_bbe); - /* This version uses 64k bytes of table space. A 16 byte buffer has to be multiplied by a 16 byte key value in GF(2^128). If we consider a GF(2^128) value in @@ -380,28 +342,6 @@ out: } EXPORT_SYMBOL(gf128mul_init_4k_lle); -struct gf128mul_4k *gf128mul_init_4k_bbe(const be128 *g) -{ - struct gf128mul_4k *t; - int j, k; - - t = kzalloc(sizeof(*t), GFP_KERNEL); - if (!t) - goto out; - - t->t[1] = *g; - for (j = 1; j <= 64; j <<= 1) - gf128mul_x_bbe(&t->t[j + j], &t->t[j]); - - for (j = 2; j < 256; j += j) - for (k = 1; k < j; ++k) - be128_xor(&t->t[j + k], &t->t[j], &t->t[k]); - -out: - return t; -} -EXPORT_SYMBOL(gf128mul_init_4k_bbe); - void gf128mul_4k_lle(be128 *a, const struct gf128mul_4k *t) { u8 *ap = (u8 *)a; @@ -417,20 +357,5 @@ void gf128mul_4k_lle(be128 *a, const struct gf128mul_4k *t) } EXPORT_SYMBOL(gf128mul_4k_lle); -void gf128mul_4k_bbe(be128 *a, const struct gf128mul_4k *t) -{ - u8 *ap = (u8 *)a; - be128 r[1]; - int i = 0; - - *r = t->t[ap[0]]; - while (++i < 16) { - gf128mul_x8_bbe(r); - be128_xor(r, r, &t->t[ap[i]]); - } - *a = *r; -} -EXPORT_SYMBOL(gf128mul_4k_bbe); - MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)"); diff --git a/lib/fault-inject.c b/lib/fault-inject.c index 52eb6ba29698..999053fa133e 100644 --- a/lib/fault-inject.c +++ b/lib/fault-inject.c @@ -1,7 +1,7 @@ // SPDX-License-Identifier: GPL-2.0-only #include <linux/kernel.h> #include <linux/init.h> -#include <linux/random.h> +#include <linux/prandom.h> #include <linux/debugfs.h> #include <linux/sched.h> #include <linux/stat.h> @@ -13,6 +13,24 @@ #include <linux/fault-inject.h> /* + * The should_fail() functions use prandom instead of the normal Linux RNG + * since they don't need cryptographically secure random numbers. + */ +static DEFINE_PER_CPU(struct rnd_state, fault_rnd_state); + +static u32 fault_prandom_u32_below_100(void) +{ + struct rnd_state *state; + u32 res; + + state = &get_cpu_var(fault_rnd_state); + res = prandom_u32_state(state); + put_cpu_var(fault_rnd_state); + + return res % 100; +} + +/* * setup_fault_attr() is a helper function for various __setup handlers, so it * returns 0 on error, because that is what __setup handlers do. */ @@ -31,6 +49,8 @@ int setup_fault_attr(struct fault_attr *attr, char *str) return 0; } + prandom_init_once(&fault_rnd_state); + attr->probability = probability; attr->interval = interval; atomic_set(&attr->times, times); @@ -146,7 +166,7 @@ bool should_fail_ex(struct fault_attr *attr, ssize_t size, int flags) return false; } - if (attr->probability <= get_random_u32_below(100)) + if (attr->probability <= fault_prandom_u32_below_100()) return false; fail: @@ -219,6 +239,8 @@ struct dentry *fault_create_debugfs_attr(const char *name, if (IS_ERR(dir)) return dir; + prandom_init_once(&fault_rnd_state); + debugfs_create_ul("probability", mode, dir, &attr->probability); debugfs_create_ul("interval", mode, dir, &attr->interval); debugfs_create_atomic_t("times", mode, dir, &attr->times); @@ -431,6 +453,8 @@ static const struct config_item_type fault_config_type = { void fault_config_init(struct fault_config *config, const char *name) { + prandom_init_once(&fault_rnd_state); + config_group_init_type_name(&config->group, name, &fault_config_type); } EXPORT_SYMBOL_GPL(fault_config_init); diff --git a/lib/fonts/Kconfig b/lib/fonts/Kconfig index 3ac26bdbc3ff..ae59b5b4e225 100644 --- a/lib/fonts/Kconfig +++ b/lib/fonts/Kconfig @@ -10,7 +10,7 @@ if FONT_SUPPORT config FONTS bool "Select compiled-in fonts" - depends on FRAMEBUFFER_CONSOLE || STI_CONSOLE || DRM_PANIC + depends on FRAMEBUFFER_CONSOLE || STI_CONSOLE || DRM_PANIC || DRM_CLIENT_LOG help Say Y here if you would like to use fonts other than the default your frame buffer console usually use. diff --git a/lib/gen_crc32table.c b/lib/gen_crc32table.c index f755b997b967..6d03425b849e 100644 --- a/lib/gen_crc32table.c +++ b/lib/gen_crc32table.c @@ -2,30 +2,11 @@ #include <stdio.h> #include "../include/linux/crc32poly.h" #include "../include/generated/autoconf.h" -#include "crc32defs.h" #include <inttypes.h> -#define ENTRIES_PER_LINE 4 - -#if CRC_LE_BITS > 8 -# define LE_TABLE_ROWS (CRC_LE_BITS/8) -# define LE_TABLE_SIZE 256 -#else -# define LE_TABLE_ROWS 1 -# define LE_TABLE_SIZE (1 << CRC_LE_BITS) -#endif - -#if CRC_BE_BITS > 8 -# define BE_TABLE_ROWS (CRC_BE_BITS/8) -# define BE_TABLE_SIZE 256 -#else -# define BE_TABLE_ROWS 1 -# define BE_TABLE_SIZE (1 << CRC_BE_BITS) -#endif - -static uint32_t crc32table_le[LE_TABLE_ROWS][256]; -static uint32_t crc32table_be[BE_TABLE_ROWS][256]; -static uint32_t crc32ctable_le[LE_TABLE_ROWS][256]; +static uint32_t crc32table_le[256]; +static uint32_t crc32table_be[256]; +static uint32_t crc32ctable_le[256]; /** * crc32init_le() - allocate and initialize LE table data @@ -34,25 +15,17 @@ static uint32_t crc32ctable_le[LE_TABLE_ROWS][256]; * fact that crctable[i^j] = crctable[i] ^ crctable[j]. * */ -static void crc32init_le_generic(const uint32_t polynomial, - uint32_t (*tab)[256]) +static void crc32init_le_generic(const uint32_t polynomial, uint32_t tab[256]) { unsigned i, j; uint32_t crc = 1; - tab[0][0] = 0; + tab[0] = 0; - for (i = LE_TABLE_SIZE >> 1; i; i >>= 1) { + for (i = 128; i; i >>= 1) { crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0); - for (j = 0; j < LE_TABLE_SIZE; j += 2 * i) - tab[0][i + j] = crc ^ tab[0][j]; - } - for (i = 0; i < LE_TABLE_SIZE; i++) { - crc = tab[0][i]; - for (j = 1; j < LE_TABLE_ROWS; j++) { - crc = tab[0][crc & 0xff] ^ (crc >> 8); - tab[j][i] = crc; - } + for (j = 0; j < 256; j += 2 * i) + tab[i + j] = crc ^ tab[j]; } } @@ -74,34 +47,22 @@ static void crc32init_be(void) unsigned i, j; uint32_t crc = 0x80000000; - crc32table_be[0][0] = 0; + crc32table_be[0] = 0; - for (i = 1; i < BE_TABLE_SIZE; i <<= 1) { + for (i = 1; i < 256; i <<= 1) { crc = (crc << 1) ^ ((crc & 0x80000000) ? CRC32_POLY_BE : 0); for (j = 0; j < i; j++) - crc32table_be[0][i + j] = crc ^ crc32table_be[0][j]; - } - for (i = 0; i < BE_TABLE_SIZE; i++) { - crc = crc32table_be[0][i]; - for (j = 1; j < BE_TABLE_ROWS; j++) { - crc = crc32table_be[0][(crc >> 24) & 0xff] ^ (crc << 8); - crc32table_be[j][i] = crc; - } + crc32table_be[i + j] = crc ^ crc32table_be[j]; } } -static void output_table(uint32_t (*table)[256], int rows, int len, char *trans) +static void output_table(const uint32_t table[256]) { - int i, j; - - for (j = 0 ; j < rows; j++) { - printf("{"); - for (i = 0; i < len - 1; i++) { - if (i % ENTRIES_PER_LINE == 0) - printf("\n"); - printf("%s(0x%8.8xL), ", trans, table[j][i]); - } - printf("%s(0x%8.8xL)},\n", trans, table[j][len - 1]); + int i; + + for (i = 0; i < 256; i += 4) { + printf("\t0x%08x, 0x%08x, 0x%08x, 0x%08x,\n", + table[i], table[i + 1], table[i + 2], table[i + 3]); } } @@ -109,34 +70,20 @@ int main(int argc, char** argv) { printf("/* this file is generated - do not edit */\n\n"); - if (CRC_LE_BITS > 1) { - crc32init_le(); - printf("static const u32 ____cacheline_aligned " - "crc32table_le[%d][%d] = {", - LE_TABLE_ROWS, LE_TABLE_SIZE); - output_table(crc32table_le, LE_TABLE_ROWS, - LE_TABLE_SIZE, "tole"); - printf("};\n"); - } + crc32init_le(); + printf("static const u32 ____cacheline_aligned crc32table_le[256] = {\n"); + output_table(crc32table_le); + printf("};\n"); - if (CRC_BE_BITS > 1) { - crc32init_be(); - printf("static const u32 ____cacheline_aligned " - "crc32table_be[%d][%d] = {", - BE_TABLE_ROWS, BE_TABLE_SIZE); - output_table(crc32table_be, LE_TABLE_ROWS, - BE_TABLE_SIZE, "tobe"); - printf("};\n"); - } - if (CRC_LE_BITS > 1) { - crc32cinit_le(); - printf("static const u32 ____cacheline_aligned " - "crc32ctable_le[%d][%d] = {", - LE_TABLE_ROWS, LE_TABLE_SIZE); - output_table(crc32ctable_le, LE_TABLE_ROWS, - LE_TABLE_SIZE, "tole"); - printf("};\n"); - } + crc32init_be(); + printf("static const u32 ____cacheline_aligned crc32table_be[256] = {\n"); + output_table(crc32table_be); + printf("};\n"); + + crc32cinit_le(); + printf("static const u32 ____cacheline_aligned crc32ctable_le[256] = {\n"); + output_table(crc32ctable_le); + printf("};\n"); return 0; } diff --git a/lib/inflate.c b/lib/inflate.c index fbaf03c1748d..eab886baa1b4 100644 --- a/lib/inflate.c +++ b/lib/inflate.c @@ -1257,8 +1257,6 @@ static int INIT gunzip(void) /* Decompress */ if ((res = inflate())) { switch (res) { - case 0: - break; case 1: error("invalid compressed format (err=1)"); break; diff --git a/lib/iov_iter.c b/lib/iov_iter.c index 65f550cb5081..bc9391e55d57 100644 --- a/lib/iov_iter.c +++ b/lib/iov_iter.c @@ -1190,8 +1190,12 @@ static ssize_t __iov_iter_get_pages_alloc(struct iov_iter *i, if (!n) return -ENOMEM; p = *pages; - for (int k = 0; k < n; k++) - get_page(p[k] = page + k); + for (int k = 0; k < n; k++) { + struct folio *folio = page_folio(page + k); + p[k] = page + k; + if (!folio_test_slab(folio)) + folio_get(folio); + } maxsize = min_t(size_t, maxsize, n * PAGE_SIZE - *start); i->count -= maxsize; i->iov_offset += maxsize; diff --git a/lib/kobject.c b/lib/kobject.c index 72fa20f405f1..abe5f5b856ce 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -1096,30 +1096,6 @@ void *kobj_ns_grab_current(enum kobj_ns_type type) } EXPORT_SYMBOL_GPL(kobj_ns_grab_current); -const void *kobj_ns_netlink(enum kobj_ns_type type, struct sock *sk) -{ - const void *ns = NULL; - - spin_lock(&kobj_ns_type_lock); - if (kobj_ns_type_is_valid(type) && kobj_ns_ops_tbl[type]) - ns = kobj_ns_ops_tbl[type]->netlink_ns(sk); - spin_unlock(&kobj_ns_type_lock); - - return ns; -} - -const void *kobj_ns_initial(enum kobj_ns_type type) -{ - const void *ns = NULL; - - spin_lock(&kobj_ns_type_lock); - if (kobj_ns_type_is_valid(type) && kobj_ns_ops_tbl[type]) - ns = kobj_ns_ops_tbl[type]->initial_ns(); - spin_unlock(&kobj_ns_type_lock); - - return ns; -} - void kobj_ns_drop(enum kobj_ns_type type, void *ns) { spin_lock(&kobj_ns_type_lock); diff --git a/lib/kunit/Kconfig b/lib/kunit/Kconfig index 34d7242d526d..a97897edd964 100644 --- a/lib/kunit/Kconfig +++ b/lib/kunit/Kconfig @@ -81,4 +81,16 @@ config KUNIT_DEFAULT_ENABLED In most cases this should be left as Y. Only if additional opt-in behavior is needed should this be set to N. +config KUNIT_AUTORUN_ENABLED + bool "Default value of kunit.autorun" + default y + help + Sets the default value of kunit.autorun. If set to N then KUnit + tests will not run after initialization unless kunit.autorun=1 is + passed to the kernel command line. The test can still be run manually + via debugfs interface. + + In most cases this should be left as Y. Only if additional opt-in + behavior is needed should this be set to N. + endif # KUNIT diff --git a/lib/kunit/debugfs.c b/lib/kunit/debugfs.c index af71911f4a07..9c326f1837bd 100644 --- a/lib/kunit/debugfs.c +++ b/lib/kunit/debugfs.c @@ -145,7 +145,7 @@ static ssize_t debugfs_run(struct file *file, struct inode *f_inode = file->f_inode; struct kunit_suite *suite = (struct kunit_suite *) f_inode->i_private; - __kunit_test_suites_init(&suite, 1); + __kunit_test_suites_init(&suite, 1, true); return count; } diff --git a/lib/kunit/executor.c b/lib/kunit/executor.c index 34b7b6833df3..3f39955cb0f1 100644 --- a/lib/kunit/executor.c +++ b/lib/kunit/executor.c @@ -29,6 +29,22 @@ const char *kunit_action(void) return action_param; } +/* + * Run KUnit tests after initialization + */ +#ifdef CONFIG_KUNIT_AUTORUN_ENABLED +static bool autorun_param = true; +#else +static bool autorun_param; +#endif +module_param_named(autorun, autorun_param, bool, 0); +MODULE_PARM_DESC(autorun, "Run KUnit tests after initialization"); + +bool kunit_autorun(void) +{ + return autorun_param; +} + static char *filter_glob_param; static char *filter_param; static char *filter_action_param; @@ -260,13 +276,14 @@ free_copy: void kunit_exec_run_tests(struct kunit_suite_set *suite_set, bool builtin) { size_t num_suites = suite_set->end - suite_set->start; + bool autorun = kunit_autorun(); - if (builtin || num_suites) { + if (autorun && (builtin || num_suites)) { pr_info("KTAP version 1\n"); pr_info("1..%zu\n", num_suites); } - __kunit_test_suites_init(suite_set->start, num_suites); + __kunit_test_suites_init(suite_set->start, num_suites, autorun); } void kunit_exec_list_tests(struct kunit_suite_set *suite_set, bool include_attr) diff --git a/lib/kunit/test.c b/lib/kunit/test.c index 089c832e3cdb..146d1b48a096 100644 --- a/lib/kunit/test.c +++ b/lib/kunit/test.c @@ -708,7 +708,8 @@ bool kunit_enabled(void) return enable_param; } -int __kunit_test_suites_init(struct kunit_suite * const * const suites, int num_suites) +int __kunit_test_suites_init(struct kunit_suite * const * const suites, int num_suites, + bool run_tests) { unsigned int i; @@ -731,7 +732,8 @@ int __kunit_test_suites_init(struct kunit_suite * const * const suites, int num_ for (i = 0; i < num_suites; i++) { kunit_init_suite(suites[i]); - kunit_run_tests(suites[i]); + if (run_tests) + kunit_run_tests(suites[i]); } static_branch_dec(&kunit_running); diff --git a/lib/kunit_iov_iter.c b/lib/kunit_iov_iter.c index 13e15687675a..48342736d016 100644 --- a/lib/kunit_iov_iter.c +++ b/lib/kunit_iov_iter.c @@ -57,15 +57,12 @@ static void *__init iov_kunit_create_buffer(struct kunit *test, KUNIT_ASSERT_NOT_ERR_OR_NULL(test, pages); *ppages = pages; - got = alloc_pages_bulk_array(GFP_KERNEL, npages, pages); + got = alloc_pages_bulk(GFP_KERNEL, npages, pages); if (got != npages) { release_pages(pages, got); KUNIT_ASSERT_EQ(test, got, npages); } - for (int i = 0; i < npages; i++) - pages[i]->index = i; - buffer = vmap(pages, npages, VM_MAP | VM_MAP_PUT_PAGES, PAGE_KERNEL); KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buffer); @@ -392,7 +389,7 @@ static void __init iov_kunit_load_folioq(struct kunit *test, if (folioq_full(p)) { p->next = kzalloc(sizeof(struct folio_queue), GFP_KERNEL); KUNIT_ASSERT_NOT_ERR_OR_NULL(test, p->next); - folioq_init(p->next); + folioq_init(p->next, 0); p->next->prev = p; p = p->next; } @@ -409,7 +406,7 @@ static struct folio_queue *iov_kunit_create_folioq(struct kunit *test) folioq = kzalloc(sizeof(struct folio_queue), GFP_KERNEL); KUNIT_ASSERT_NOT_ERR_OR_NULL(test, folioq); kunit_add_action_or_reset(test, iov_kunit_destroy_folioq, folioq); - folioq_init(folioq); + folioq_init(folioq, 0); return folioq; } diff --git a/lib/libcrc32c.c b/lib/libcrc32c.c deleted file mode 100644 index 649e687413a0..000000000000 --- a/lib/libcrc32c.c +++ /dev/null @@ -1,74 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0-or-later -/* - * CRC32C - *@Article{castagnoli-crc, - * author = { Guy Castagnoli and Stefan Braeuer and Martin Herrman}, - * title = {{Optimization of Cyclic Redundancy-Check Codes with 24 - * and 32 Parity Bits}}, - * journal = IEEE Transactions on Communication, - * year = {1993}, - * volume = {41}, - * number = {6}, - * pages = {}, - * month = {June}, - *} - * Used by the iSCSI driver, possibly others, and derived from - * the iscsi-crc.c module of the linux-iscsi driver at - * http://linux-iscsi.sourceforge.net. - * - * Following the example of lib/crc32, this function is intended to be - * flexible and useful for all users. Modules that currently have their - * own crc32c, but hopefully may be able to use this one are: - * net/sctp (please add all your doco to here if you change to - * use this one!) - * <endoflist> - * - * Copyright (c) 2004 Cisco Systems, Inc. - */ - -#include <crypto/hash.h> -#include <linux/err.h> -#include <linux/init.h> -#include <linux/kernel.h> -#include <linux/module.h> -#include <linux/crc32c.h> - -static struct crypto_shash *tfm; - -u32 crc32c(u32 crc, const void *address, unsigned int length) -{ - SHASH_DESC_ON_STACK(shash, tfm); - u32 ret, *ctx = (u32 *)shash_desc_ctx(shash); - int err; - - shash->tfm = tfm; - *ctx = crc; - - err = crypto_shash_update(shash, address, length); - BUG_ON(err); - - ret = *ctx; - barrier_data(ctx); - return ret; -} - -EXPORT_SYMBOL(crc32c); - -static int __init libcrc32c_mod_init(void) -{ - tfm = crypto_alloc_shash("crc32c", 0, 0); - return PTR_ERR_OR_ZERO(tfm); -} - -static void __exit libcrc32c_mod_fini(void) -{ - crypto_free_shash(tfm); -} - -module_init(libcrc32c_mod_init); -module_exit(libcrc32c_mod_fini); - -MODULE_AUTHOR("Clay Haapala <chaapala@cisco.com>"); -MODULE_DESCRIPTION("CRC32c (Castagnoli) calculations"); -MODULE_LICENSE("GPL"); -MODULE_SOFTDEP("pre: crc32c"); diff --git a/lib/list_debug.c b/lib/list_debug.c index db602417febf..ee7eeeb8f92c 100644 --- a/lib/list_debug.c +++ b/lib/list_debug.c @@ -22,17 +22,17 @@ __list_valid_slowpath bool __list_add_valid_or_report(struct list_head *new, struct list_head *prev, struct list_head *next) { - if (CHECK_DATA_CORRUPTION(prev == NULL, + if (CHECK_DATA_CORRUPTION(prev == NULL, NULL, "list_add corruption. prev is NULL.\n") || - CHECK_DATA_CORRUPTION(next == NULL, + CHECK_DATA_CORRUPTION(next == NULL, NULL, "list_add corruption. next is NULL.\n") || - CHECK_DATA_CORRUPTION(next->prev != prev, + CHECK_DATA_CORRUPTION(next->prev != prev, next, "list_add corruption. next->prev should be prev (%px), but was %px. (next=%px).\n", prev, next->prev, next) || - CHECK_DATA_CORRUPTION(prev->next != next, + CHECK_DATA_CORRUPTION(prev->next != next, prev, "list_add corruption. prev->next should be next (%px), but was %px. (prev=%px).\n", next, prev->next, prev) || - CHECK_DATA_CORRUPTION(new == prev || new == next, + CHECK_DATA_CORRUPTION(new == prev || new == next, NULL, "list_add double add: new=%px, prev=%px, next=%px.\n", new, prev, next)) return false; @@ -49,20 +49,20 @@ bool __list_del_entry_valid_or_report(struct list_head *entry) prev = entry->prev; next = entry->next; - if (CHECK_DATA_CORRUPTION(next == NULL, + if (CHECK_DATA_CORRUPTION(next == NULL, NULL, "list_del corruption, %px->next is NULL\n", entry) || - CHECK_DATA_CORRUPTION(prev == NULL, + CHECK_DATA_CORRUPTION(prev == NULL, NULL, "list_del corruption, %px->prev is NULL\n", entry) || - CHECK_DATA_CORRUPTION(next == LIST_POISON1, + CHECK_DATA_CORRUPTION(next == LIST_POISON1, next, "list_del corruption, %px->next is LIST_POISON1 (%px)\n", entry, LIST_POISON1) || - CHECK_DATA_CORRUPTION(prev == LIST_POISON2, + CHECK_DATA_CORRUPTION(prev == LIST_POISON2, prev, "list_del corruption, %px->prev is LIST_POISON2 (%px)\n", entry, LIST_POISON2) || - CHECK_DATA_CORRUPTION(prev->next != entry, + CHECK_DATA_CORRUPTION(prev->next != entry, prev, "list_del corruption. prev->next should be %px, but was %px. (prev=%px)\n", entry, prev->next, prev) || - CHECK_DATA_CORRUPTION(next->prev != entry, + CHECK_DATA_CORRUPTION(next->prev != entry, next, "list_del corruption. next->prev should be %px, but was %px. (next=%px)\n", entry, next->prev, next)) return false; diff --git a/lib/list_sort.c b/lib/list_sort.c index 8d3f623536fe..a310ecb7ccc0 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -108,6 +108,13 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, * and list_sort is a stable sort, so it is not necessary to distinguish * the @a < @b and @a == @b cases. * + * The comparison function must adhere to specific mathematical properties + * to ensure correct and stable sorting: + * - Antisymmetry: cmp(@a, @b) must return the opposite sign of + * cmp(@b, @a). + * - Transitivity: if cmp(@a, @b) <= 0 and cmp(@b, @c) <= 0, then + * cmp(@a, @c) <= 0. + * * This is compatible with two styles of @cmp function: * - The traditional style which returns <0 / =0 / >0, or * - Returning a boolean 0/1. diff --git a/lib/lockref.c b/lib/lockref.c index 2afe4c5d8919..5d8e3ef3860e 100644 --- a/lib/lockref.c +++ b/lib/lockref.c @@ -58,23 +58,22 @@ EXPORT_SYMBOL(lockref_get); * @lockref: pointer to lockref structure * Return: 1 if count updated successfully or 0 if count was zero */ -int lockref_get_not_zero(struct lockref *lockref) +bool lockref_get_not_zero(struct lockref *lockref) { - int retval; + bool retval = false; CMPXCHG_LOOP( new.count++; if (old.count <= 0) - return 0; + return false; , - return 1; + return true; ); spin_lock(&lockref->lock); - retval = 0; if (lockref->count > 0) { lockref->count++; - retval = 1; + retval = true; } spin_unlock(&lockref->lock); return retval; @@ -82,39 +81,11 @@ int lockref_get_not_zero(struct lockref *lockref) EXPORT_SYMBOL(lockref_get_not_zero); /** - * lockref_put_not_zero - Decrements count unless count <= 1 before decrement - * @lockref: pointer to lockref structure - * Return: 1 if count updated successfully or 0 if count would become zero - */ -int lockref_put_not_zero(struct lockref *lockref) -{ - int retval; - - CMPXCHG_LOOP( - new.count--; - if (old.count <= 1) - return 0; - , - return 1; - ); - - spin_lock(&lockref->lock); - retval = 0; - if (lockref->count > 1) { - lockref->count--; - retval = 1; - } - spin_unlock(&lockref->lock); - return retval; -} -EXPORT_SYMBOL(lockref_put_not_zero); - -/** * lockref_put_return - Decrement reference count if possible * @lockref: pointer to lockref structure * * Decrement the reference count and return the new value. - * If the lockref was dead or locked, return an error. + * If the lockref was dead or locked, return -1. */ int lockref_put_return(struct lockref *lockref) { @@ -134,22 +105,22 @@ EXPORT_SYMBOL(lockref_put_return); * @lockref: pointer to lockref structure * Return: 1 if count updated successfully or 0 if count <= 1 and lock taken */ -int lockref_put_or_lock(struct lockref *lockref) +bool lockref_put_or_lock(struct lockref *lockref) { CMPXCHG_LOOP( new.count--; if (old.count <= 1) break; , - return 1; + return true; ); spin_lock(&lockref->lock); if (lockref->count <= 1) - return 0; + return false; lockref->count--; spin_unlock(&lockref->lock); - return 1; + return true; } EXPORT_SYMBOL(lockref_put_or_lock); @@ -169,23 +140,22 @@ EXPORT_SYMBOL(lockref_mark_dead); * @lockref: pointer to lockref structure * Return: 1 if count updated successfully or 0 if lockref was dead */ -int lockref_get_not_dead(struct lockref *lockref) +bool lockref_get_not_dead(struct lockref *lockref) { - int retval; + bool retval = false; CMPXCHG_LOOP( new.count++; if (old.count < 0) - return 0; + return false; , - return 1; + return true; ); spin_lock(&lockref->lock); - retval = 0; if (lockref->count >= 0) { lockref->count++; - retval = 1; + retval = true; } spin_unlock(&lockref->lock); return retval; diff --git a/lib/lz4/lz4_compress.c b/lib/lz4/lz4_compress.c index b0bbeeb74b9e..2a397bb2c661 100644 --- a/lib/lz4/lz4_compress.c +++ b/lib/lz4/lz4_compress.c @@ -33,7 +33,6 @@ /*-************************************ * Dependencies **************************************/ -#include <linux/lz4.h> #include "lz4defs.h" #include <linux/module.h> #include <linux/kernel.h> diff --git a/lib/lz4/lz4_decompress.c b/lib/lz4/lz4_decompress.c index 0e31e6da5ce7..3a2cd9acada4 100644 --- a/lib/lz4/lz4_decompress.c +++ b/lib/lz4/lz4_decompress.c @@ -33,7 +33,6 @@ /*-************************************ * Dependencies **************************************/ -#include <linux/lz4.h> #include "lz4defs.h" #include <linux/init.h> #include <linux/module.h> diff --git a/lib/lz4/lz4defs.h b/lib/lz4/lz4defs.h index cb358d6bde5a..17277ec16919 100644 --- a/lib/lz4/lz4defs.h +++ b/lib/lz4/lz4defs.h @@ -39,6 +39,7 @@ #include <linux/bitops.h> #include <linux/string.h> /* memset, memcpy */ +#include <linux/lz4.h> #define FORCE_INLINE __always_inline @@ -92,8 +93,7 @@ typedef uintptr_t uptrval; #define MB (1 << 20) #define GB (1U << 30) -#define MAXD_LOG 16 -#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) +#define MAX_DISTANCE LZ4_DISTANCE_MAX #define STEPSIZE sizeof(size_t) #define ML_BITS 4 diff --git a/lib/lz4/lz4hc_compress.c b/lib/lz4/lz4hc_compress.c index bc45594ad2a8..91936dc3d14b 100644 --- a/lib/lz4/lz4hc_compress.c +++ b/lib/lz4/lz4hc_compress.c @@ -34,7 +34,6 @@ /*-************************************ * Dependencies **************************************/ -#include <linux/lz4.h> #include "lz4defs.h" #include <linux/module.h> #include <linux/kernel.h> diff --git a/lib/maple_tree.c b/lib/maple_tree.c index db9bf663661c..f7153ade1be5 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4735,29 +4735,6 @@ again: } /* - * mas_next_entry() - Internal function to get the next entry. - * @mas: The maple state - * @limit: The maximum range start. - * - * Set the @mas->node to the next entry and the range_start to - * the beginning value for the entry. Does not check beyond @limit. - * Sets @mas->index and @mas->last to the range, Does not update @mas->index and - * @mas->last on overflow. - * Restarts on dead nodes. - * - * Return: the next entry or %NULL. - */ -static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) -{ - if (mas->last >= limit) { - mas->status = ma_overflow; - return NULL; - } - - return mas_next_slot(mas, limit, false); -} - -/* * mas_rev_awalk() - Internal function. Reverse allocation walk. Find the * highest gap address of a given size in a given node and descend. * @mas: The maple state @@ -4892,15 +4869,14 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) if (gap >= size) { if (ma_is_leaf(type)) { found = true; - goto done; - } - if (mas->index <= pivot) { - mas->node = mas_slot(mas, slots, offset); - mas->min = min; - mas->max = pivot; - offset = 0; break; } + + mas->node = mas_slot(mas, slots, offset); + mas->min = min; + mas->max = pivot; + offset = 0; + break; } next_slot: min = pivot + 1; @@ -4910,9 +4886,6 @@ next_slot: } } - if (mte_is_root(mas->node)) - found = true; -done: mas->offset = offset; return found; } @@ -5016,8 +4989,8 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size) * There are 4 options: * go to child (descend) * go back to parent (ascend) - * no gap found. (return, slot == MAPLE_NODE_SLOTS) - * found the gap. (return, slot != MAPLE_NODE_SLOTS) + * no gap found. (return, error == -EBUSY) + * found the gap. (return) */ while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) { if (last == mas->node) @@ -5102,9 +5075,6 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, return xa_err(mas->node); offset = mas->offset; - if (unlikely(offset == MAPLE_NODE_SLOTS)) - return -EBUSY; - node = mas_mn(mas); mt = mte_node_type(mas->node); pivots = ma_pivots(node, mt); @@ -6927,7 +6897,7 @@ retry: goto unlock; while (mas_is_active(&mas) && (mas.last < max)) { - entry = mas_next_entry(&mas, max); + entry = mas_next_slot(&mas, max, false); if (likely(entry && !xa_is_zero(entry))) break; } @@ -7586,7 +7556,7 @@ void mt_validate(struct maple_tree *mt) MAS_WARN_ON(&mas, mte_dead_node(mas.node)); end = mas_data_end(&mas); if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && - (mas.max != ULONG_MAX))) { + (!mte_is_root(mas.node)))) { pr_err("Invalid size %u of " PTR_FMT "\n", end, mas_mn(&mas)); } diff --git a/lib/math/Makefile b/lib/math/Makefile index 3ef11305f8d2..853f023ae537 100644 --- a/lib/math/Makefile +++ b/lib/math/Makefile @@ -9,3 +9,4 @@ obj-$(CONFIG_INT_POW_TEST) += tests/int_pow_kunit.o obj-$(CONFIG_TEST_DIV64) += test_div64.o obj-$(CONFIG_TEST_MULDIV64) += test_mul_u64_u64_div_u64.o obj-$(CONFIG_RATIONAL_KUNIT_TEST) += rational-test.o +obj-$(CONFIG_INT_SQRT_KUNIT_TEST) += tests/int_sqrt_kunit.o
\ No newline at end of file diff --git a/lib/math/tests/Makefile b/lib/math/tests/Makefile index 6a169123320a..e1a79f093b2d 100644 --- a/lib/math/tests/Makefile +++ b/lib/math/tests/Makefile @@ -1,3 +1,4 @@ # SPDX-License-Identifier: GPL-2.0-only obj-$(CONFIG_INT_POW_TEST) += int_pow_kunit.o +obj-$(CONFIG_INT_SQRT_KUNIT_TEST) += int_sqrt_kunit.o diff --git a/lib/math/tests/int_sqrt_kunit.c b/lib/math/tests/int_sqrt_kunit.c new file mode 100644 index 000000000000..1798e1312eb7 --- /dev/null +++ b/lib/math/tests/int_sqrt_kunit.c @@ -0,0 +1,66 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <kunit/test.h> +#include <linux/limits.h> +#include <linux/math.h> +#include <linux/module.h> +#include <linux/string.h> + +struct test_case_params { + unsigned long x; + unsigned long expected_result; + const char *name; +}; + +static const struct test_case_params params[] = { + { 0, 0, "edge case: square root of 0" }, + { 1, 1, "perfect square: square root of 1" }, + { 2, 1, "non-perfect square: square root of 2" }, + { 3, 1, "non-perfect square: square root of 3" }, + { 4, 2, "perfect square: square root of 4" }, + { 5, 2, "non-perfect square: square root of 5" }, + { 6, 2, "non-perfect square: square root of 6" }, + { 7, 2, "non-perfect square: square root of 7" }, + { 8, 2, "non-perfect square: square root of 8" }, + { 9, 3, "perfect square: square root of 9" }, + { 15, 3, "non-perfect square: square root of 15 (N-1 from 16)" }, + { 16, 4, "perfect square: square root of 16" }, + { 17, 4, "non-perfect square: square root of 17 (N+1 from 16)" }, + { 80, 8, "non-perfect square: square root of 80 (N-1 from 81)" }, + { 81, 9, "perfect square: square root of 81" }, + { 82, 9, "non-perfect square: square root of 82 (N+1 from 81)" }, + { 255, 15, "non-perfect square: square root of 255 (N-1 from 256)" }, + { 256, 16, "perfect square: square root of 256" }, + { 257, 16, "non-perfect square: square root of 257 (N+1 from 256)" }, + { 2147483648, 46340, "large input: square root of 2147483648" }, + { 4294967295, 65535, "edge case: ULONG_MAX for 32-bit" }, +}; + +static void get_desc(const struct test_case_params *tc, char *desc) +{ + strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE); +} + +KUNIT_ARRAY_PARAM(int_sqrt, params, get_desc); + +static void int_sqrt_test(struct kunit *test) +{ + const struct test_case_params *tc = (const struct test_case_params *)test->param_value; + + KUNIT_EXPECT_EQ(test, tc->expected_result, int_sqrt(tc->x)); +} + +static struct kunit_case math_int_sqrt_test_cases[] = { + KUNIT_CASE_PARAM(int_sqrt_test, int_sqrt_gen_params), + {} +}; + +static struct kunit_suite int_sqrt_test_suite = { + .name = "math-int_sqrt", + .test_cases = math_int_sqrt_test_cases, +}; + +kunit_test_suites(&int_sqrt_test_suite); + +MODULE_DESCRIPTION("math.int_sqrt KUnit test suite"); +MODULE_LICENSE("GPL"); diff --git a/lib/packing.c b/lib/packing.c index 793942745e34..bb1643d9e64d 100644 --- a/lib/packing.c +++ b/lib/packing.c @@ -5,10 +5,37 @@ #include <linux/packing.h> #include <linux/module.h> #include <linux/bitops.h> +#include <linux/bits.h> #include <linux/errno.h> #include <linux/types.h> #include <linux/bitrev.h> +#define __pack_fields(pbuf, pbuflen, ustruct, fields, num_fields, quirks) \ + ({ \ + for (size_t i = 0; i < (num_fields); i++) { \ + typeof(&(fields)[0]) field = &(fields)[i]; \ + u64 uval; \ + \ + uval = ustruct_field_to_u64(ustruct, field->offset, field->size); \ + \ + __pack(pbuf, uval, field->startbit, field->endbit, \ + pbuflen, quirks); \ + } \ + }) + +#define __unpack_fields(pbuf, pbuflen, ustruct, fields, num_fields, quirks) \ + ({ \ + for (size_t i = 0; i < (num_fields); i++) { \ + typeof(&(fields)[0]) field = &fields[i]; \ + u64 uval; \ + \ + __unpack(pbuf, &uval, field->startbit, field->endbit, \ + pbuflen, quirks); \ + \ + u64_to_ustruct_field(ustruct, field->offset, field->size, uval); \ + } \ + }) + /** * calculate_box_addr - Determine physical location of byte in buffer * @box: Index of byte within buffer seen as a logical big-endian big number @@ -51,64 +78,29 @@ static size_t calculate_box_addr(size_t box, size_t len, u8 quirks) return offset_of_group + offset_in_group; } -/** - * pack - Pack u64 number into bitfield of buffer. - * - * @pbuf: Pointer to a buffer holding the packed value. - * @uval: CPU-readable unpacked value to pack. - * @startbit: The index (in logical notation, compensated for quirks) where - * the packed value starts within pbuf. Must be larger than, or - * equal to, endbit. - * @endbit: The index (in logical notation, compensated for quirks) where - * the packed value ends within pbuf. Must be smaller than, or equal - * to, startbit. - * @pbuflen: The length in bytes of the packed buffer pointed to by @pbuf. - * @quirks: A bit mask of QUIRK_LITTLE_ENDIAN, QUIRK_LSW32_IS_FIRST and - * QUIRK_MSB_ON_THE_RIGHT. - * - * Return: 0 on success, EINVAL or ERANGE if called incorrectly. Assuming - * correct usage, return code may be discarded. The @pbuf memory will - * be modified on success. - */ -int pack(void *pbuf, u64 uval, size_t startbit, size_t endbit, size_t pbuflen, - u8 quirks) +static void __pack(void *pbuf, u64 uval, size_t startbit, size_t endbit, + size_t pbuflen, u8 quirks) { /* Logical byte indices corresponding to the * start and end of the field. */ - int plogical_first_u8, plogical_last_u8, box; - /* width of the field to access in the pbuf */ - u64 value_width; - - /* startbit is expected to be larger than endbit, and both are - * expected to be within the logically addressable range of the buffer. - */ - if (unlikely(startbit < endbit || startbit >= BITS_PER_BYTE * pbuflen)) - /* Invalid function call */ - return -EINVAL; - - value_width = startbit - endbit + 1; - if (unlikely(value_width > 64)) - return -ERANGE; + int plogical_first_u8 = startbit / BITS_PER_BYTE; + int plogical_last_u8 = endbit / BITS_PER_BYTE; + int value_width = startbit - endbit + 1; + int box; /* Check if "uval" fits in "value_width" bits. - * If value_width is 64, the check will fail, but any - * 64-bit uval will surely fit. + * The test only works for value_width < 64, but in the latter case, + * any 64-bit uval will surely fit. */ - if (unlikely(value_width < 64 && uval >= (1ull << value_width))) - /* Cannot store "uval" inside "value_width" bits. - * Truncating "uval" is most certainly not desirable, - * so simply erroring out is appropriate. - */ - return -ERANGE; + WARN(value_width < 64 && uval >= (1ull << value_width), + "Cannot store 0x%llx inside bits %zu-%zu - will truncate\n", + uval, startbit, endbit); /* Iterate through an idealistic view of the pbuf as an u64 with * no quirks, u8 by u8 (aligned at u8 boundaries), from high to low * logical bit significance. "box" denotes the current logical u8. */ - plogical_first_u8 = startbit / BITS_PER_BYTE; - plogical_last_u8 = endbit / BITS_PER_BYTE; - for (box = plogical_first_u8; box >= plogical_last_u8; box--) { /* Bit indices into the currently accessed 8-bit box */ size_t box_start_bit, box_end_bit, box_addr; @@ -163,15 +155,13 @@ int pack(void *pbuf, u64 uval, size_t startbit, size_t endbit, size_t pbuflen, ((u8 *)pbuf)[box_addr] &= ~box_mask; ((u8 *)pbuf)[box_addr] |= pval; } - return 0; } -EXPORT_SYMBOL(pack); /** - * unpack - Unpack u64 number from packed buffer. + * pack - Pack u64 number into bitfield of buffer. * * @pbuf: Pointer to a buffer holding the packed value. - * @uval: Pointer to an u64 holding the unpacked value. + * @uval: CPU-readable unpacked value to pack. * @startbit: The index (in logical notation, compensated for quirks) where * the packed value starts within pbuf. Must be larger than, or * equal to, endbit. @@ -183,19 +173,12 @@ EXPORT_SYMBOL(pack); * QUIRK_MSB_ON_THE_RIGHT. * * Return: 0 on success, EINVAL or ERANGE if called incorrectly. Assuming - * correct usage, return code may be discarded. The @uval will be - * modified on success. + * correct usage, return code may be discarded. The @pbuf memory will + * be modified on success. */ -int unpack(const void *pbuf, u64 *uval, size_t startbit, size_t endbit, - size_t pbuflen, u8 quirks) +int pack(void *pbuf, u64 uval, size_t startbit, size_t endbit, size_t pbuflen, + u8 quirks) { - /* Logical byte indices corresponding to the - * start and end of the field. - */ - int plogical_first_u8, plogical_last_u8, box; - /* width of the field to access in the pbuf */ - u64 value_width; - /* startbit is expected to be larger than endbit, and both are * expected to be within the logically addressable range of the buffer. */ @@ -203,10 +186,25 @@ int unpack(const void *pbuf, u64 *uval, size_t startbit, size_t endbit, /* Invalid function call */ return -EINVAL; - value_width = startbit - endbit + 1; - if (unlikely(value_width > 64)) + if (unlikely(startbit - endbit >= 64)) return -ERANGE; + __pack(pbuf, uval, startbit, endbit, pbuflen, quirks); + + return 0; +} +EXPORT_SYMBOL(pack); + +static void __unpack(const void *pbuf, u64 *uval, size_t startbit, size_t endbit, + size_t pbuflen, u8 quirks) +{ + /* Logical byte indices corresponding to the + * start and end of the field. + */ + int plogical_first_u8 = startbit / BITS_PER_BYTE; + int plogical_last_u8 = endbit / BITS_PER_BYTE; + int box; + /* Initialize parameter */ *uval = 0; @@ -214,9 +212,6 @@ int unpack(const void *pbuf, u64 *uval, size_t startbit, size_t endbit, * no quirks, u8 by u8 (aligned at u8 boundaries), from high to low * logical bit significance. "box" denotes the current logical u8. */ - plogical_first_u8 = startbit / BITS_PER_BYTE; - plogical_last_u8 = endbit / BITS_PER_BYTE; - for (box = plogical_first_u8; box >= plogical_last_u8; box--) { /* Bit indices into the currently accessed 8-bit box */ size_t box_start_bit, box_end_bit, box_addr; @@ -271,6 +266,46 @@ int unpack(const void *pbuf, u64 *uval, size_t startbit, size_t endbit, *uval &= ~proj_mask; *uval |= pval; } +} + +/** + * unpack - Unpack u64 number from packed buffer. + * + * @pbuf: Pointer to a buffer holding the packed value. + * @uval: Pointer to an u64 holding the unpacked value. + * @startbit: The index (in logical notation, compensated for quirks) where + * the packed value starts within pbuf. Must be larger than, or + * equal to, endbit. + * @endbit: The index (in logical notation, compensated for quirks) where + * the packed value ends within pbuf. Must be smaller than, or equal + * to, startbit. + * @pbuflen: The length in bytes of the packed buffer pointed to by @pbuf. + * @quirks: A bit mask of QUIRK_LITTLE_ENDIAN, QUIRK_LSW32_IS_FIRST and + * QUIRK_MSB_ON_THE_RIGHT. + * + * Return: 0 on success, EINVAL or ERANGE if called incorrectly. Assuming + * correct usage, return code may be discarded. The @uval will be + * modified on success. + */ +int unpack(const void *pbuf, u64 *uval, size_t startbit, size_t endbit, + size_t pbuflen, u8 quirks) +{ + /* width of the field to access in the pbuf */ + u64 value_width; + + /* startbit is expected to be larger than endbit, and both are + * expected to be within the logically addressable range of the buffer. + */ + if (startbit < endbit || startbit >= BITS_PER_BYTE * pbuflen) + /* Invalid function call */ + return -EINVAL; + + value_width = startbit - endbit + 1; + if (value_width > 64) + return -ERANGE; + + __unpack(pbuf, uval, startbit, endbit, pbuflen, quirks); + return 0; } EXPORT_SYMBOL(unpack); @@ -314,4 +349,130 @@ int packing(void *pbuf, u64 *uval, int startbit, int endbit, size_t pbuflen, } EXPORT_SYMBOL(packing); +static u64 ustruct_field_to_u64(const void *ustruct, size_t field_offset, + size_t field_size) +{ + switch (field_size) { + case 1: + return *((u8 *)(ustruct + field_offset)); + case 2: + return *((u16 *)(ustruct + field_offset)); + case 4: + return *((u32 *)(ustruct + field_offset)); + default: + return *((u64 *)(ustruct + field_offset)); + } +} + +static void u64_to_ustruct_field(void *ustruct, size_t field_offset, + size_t field_size, u64 uval) +{ + switch (field_size) { + case 1: + *((u8 *)(ustruct + field_offset)) = uval; + break; + case 2: + *((u16 *)(ustruct + field_offset)) = uval; + break; + case 4: + *((u32 *)(ustruct + field_offset)) = uval; + break; + default: + *((u64 *)(ustruct + field_offset)) = uval; + break; + } +} + +/** + * pack_fields_u8 - Pack array of fields + * + * @pbuf: Pointer to a buffer holding the packed value. + * @pbuflen: The length in bytes of the packed buffer pointed to by @pbuf. + * @ustruct: Pointer to CPU-readable structure holding the unpacked value. + * It is expected (but not checked) that this has the same data type + * as all struct packed_field_u8 definitions. + * @fields: Array of packed_field_u8 field definition. They must not overlap. + * @num_fields: Length of @fields array. + * @quirks: A bit mask of QUIRK_LITTLE_ENDIAN, QUIRK_LSW32_IS_FIRST and + * QUIRK_MSB_ON_THE_RIGHT. + * + * Use the pack_fields() macro instead of calling this directly. + */ +void pack_fields_u8(void *pbuf, size_t pbuflen, const void *ustruct, + const struct packed_field_u8 *fields, size_t num_fields, + u8 quirks) +{ + __pack_fields(pbuf, pbuflen, ustruct, fields, num_fields, quirks); +} +EXPORT_SYMBOL(pack_fields_u8); + +/** + * pack_fields_u16 - Pack array of fields + * + * @pbuf: Pointer to a buffer holding the packed value. + * @pbuflen: The length in bytes of the packed buffer pointed to by @pbuf. + * @ustruct: Pointer to CPU-readable structure holding the unpacked value. + * It is expected (but not checked) that this has the same data type + * as all struct packed_field_u16 definitions. + * @fields: Array of packed_field_u16 field definitions. They must not overlap. + * @num_fields: Length of @fields array. + * @quirks: A bit mask of QUIRK_LITTLE_ENDIAN, QUIRK_LSW32_IS_FIRST and + * QUIRK_MSB_ON_THE_RIGHT. + * + * Use the pack_fields() macro instead of calling this directly. + */ +void pack_fields_u16(void *pbuf, size_t pbuflen, const void *ustruct, + const struct packed_field_u16 *fields, size_t num_fields, + u8 quirks) +{ + __pack_fields(pbuf, pbuflen, ustruct, fields, num_fields, quirks); +} +EXPORT_SYMBOL(pack_fields_u16); + +/** + * unpack_fields_u8 - Unpack array of fields + * + * @pbuf: Pointer to a buffer holding the packed value. + * @pbuflen: The length in bytes of the packed buffer pointed to by @pbuf. + * @ustruct: Pointer to CPU-readable structure holding the unpacked value. + * It is expected (but not checked) that this has the same data type + * as all struct packed_field_u8 definitions. + * @fields: Array of packed_field_u8 field definitions. They must not overlap. + * @num_fields: Length of @fields array. + * @quirks: A bit mask of QUIRK_LITTLE_ENDIAN, QUIRK_LSW32_IS_FIRST and + * QUIRK_MSB_ON_THE_RIGHT. + * + * Use the unpack_fields() macro instead of calling this directly. + */ +void unpack_fields_u8(const void *pbuf, size_t pbuflen, void *ustruct, + const struct packed_field_u8 *fields, size_t num_fields, + u8 quirks) +{ + __unpack_fields(pbuf, pbuflen, ustruct, fields, num_fields, quirks); +} +EXPORT_SYMBOL(unpack_fields_u8); + +/** + * unpack_fields_u16 - Unpack array of fields + * + * @pbuf: Pointer to a buffer holding the packed value. + * @pbuflen: The length in bytes of the packed buffer pointed to by @pbuf. + * @ustruct: Pointer to CPU-readable structure holding the unpacked value. + * It is expected (but not checked) that this has the same data type + * as all struct packed_field_u16 definitions. + * @fields: Array of packed_field_u16 field definitions. They must not overlap. + * @num_fields: Length of @fields array. + * @quirks: A bit mask of QUIRK_LITTLE_ENDIAN, QUIRK_LSW32_IS_FIRST and + * QUIRK_MSB_ON_THE_RIGHT. + * + * Use the unpack_fields() macro instead of calling this directly. + */ +void unpack_fields_u16(const void *pbuf, size_t pbuflen, void *ustruct, + const struct packed_field_u16 *fields, size_t num_fields, + u8 quirks) +{ + __unpack_fields(pbuf, pbuflen, ustruct, fields, num_fields, quirks); +} +EXPORT_SYMBOL(unpack_fields_u16); + MODULE_DESCRIPTION("Generic bitfield packing and unpacking"); diff --git a/lib/packing_test.c b/lib/packing_test.c index b38ea43c03fd..ce3b83d33b04 100644 --- a/lib/packing_test.c +++ b/lib/packing_test.c @@ -396,9 +396,70 @@ static void packing_test_unpack(struct kunit *test) KUNIT_EXPECT_EQ(test, uval, params->uval); } +#define PACKED_BUF_SIZE 8 + +typedef struct __packed { u8 buf[PACKED_BUF_SIZE]; } packed_buf_t; + +struct test_data { + u32 field3; + u16 field2; + u16 field4; + u16 field6; + u8 field1; + u8 field5; +}; + +static const struct packed_field_u8 test_fields[] = { + PACKED_FIELD(63, 61, struct test_data, field1), + PACKED_FIELD(60, 52, struct test_data, field2), + PACKED_FIELD(51, 28, struct test_data, field3), + PACKED_FIELD(27, 14, struct test_data, field4), + PACKED_FIELD(13, 9, struct test_data, field5), + PACKED_FIELD(8, 0, struct test_data, field6), +}; + +static void packing_test_pack_fields(struct kunit *test) +{ + const struct test_data data = { + .field1 = 0x2, + .field2 = 0x100, + .field3 = 0xF00050, + .field4 = 0x7D3, + .field5 = 0x9, + .field6 = 0x10B, + }; + packed_buf_t expect = { + .buf = { 0x50, 0x0F, 0x00, 0x05, 0x01, 0xF4, 0xD3, 0x0B }, + }; + packed_buf_t buf = {}; + + pack_fields(&buf, sizeof(buf), &data, test_fields, 0); + + KUNIT_EXPECT_MEMEQ(test, &expect, &buf, sizeof(buf)); +} + +static void packing_test_unpack_fields(struct kunit *test) +{ + const packed_buf_t buf = { + .buf = { 0x17, 0x28, 0x10, 0x19, 0x3D, 0xA9, 0x07, 0x9C }, + }; + struct test_data data = {}; + + unpack_fields(&buf, sizeof(buf), &data, test_fields, 0); + + KUNIT_EXPECT_EQ(test, 0, data.field1); + KUNIT_EXPECT_EQ(test, 0x172, data.field2); + KUNIT_EXPECT_EQ(test, 0x810193, data.field3); + KUNIT_EXPECT_EQ(test, 0x36A4, data.field4); + KUNIT_EXPECT_EQ(test, 0x3, data.field5); + KUNIT_EXPECT_EQ(test, 0x19C, data.field6); +} + static struct kunit_case packing_test_cases[] = { KUNIT_CASE_PARAM(packing_test_pack, packing_gen_params), KUNIT_CASE_PARAM(packing_test_unpack, packing_gen_params), + KUNIT_CASE(packing_test_pack_fields), + KUNIT_CASE(packing_test_unpack_fields), {}, }; diff --git a/lib/parser.c b/lib/parser.c index f4eafb9d74e6..73e8f8e5be73 100644 --- a/lib/parser.c +++ b/lib/parser.c @@ -275,8 +275,9 @@ EXPORT_SYMBOL(match_hex); * * Description: Parse the string @str to check if matches wildcard * pattern @pattern. The pattern may contain two types of wildcards: - * '*' - matches zero or more characters - * '?' - matches one character + * + * * '*' - matches zero or more characters + * * '?' - matches one character * * Return: If the @str matches the @pattern, return true, else return false. */ diff --git a/lib/pldmfw/pldmfw.c b/lib/pldmfw/pldmfw.c index 6e1581b9a616..6264e2013f25 100644 --- a/lib/pldmfw/pldmfw.c +++ b/lib/pldmfw/pldmfw.c @@ -481,9 +481,17 @@ static int pldm_parse_components(struct pldmfw_priv *data) component->component_data = data->fw->data + offset; component->component_size = size; + if (data->context->mode == PLDMFW_UPDATE_MODE_SINGLE_COMPONENT && + data->context->component_identifier != component->identifier) + continue; + list_add_tail(&component->entry, &data->components); } + if (data->context->mode == PLDMFW_UPDATE_MODE_SINGLE_COMPONENT && + list_empty(&data->components)) + return -ENOENT; + header_crc_ptr = data->fw->data + data->offset; err = pldm_move_fw_offset(data, sizeof(data->header_crc)); diff --git a/lib/rhashtable.c b/lib/rhashtable.c index 0e9a1d4cf89b..3e555d012ed6 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -669,7 +669,7 @@ EXPORT_SYMBOL_GPL(rhashtable_insert_slow); * structure outside the hash table. * * This function may be called from any process context, including - * non-preemptable context, but cannot be called from softirq or + * non-preemptible context, but cannot be called from softirq or * hardirq context. * * You must call rhashtable_walk_exit after this function returns. diff --git a/lib/sg_split.c b/lib/sg_split.c index 60a0babebf2e..0f89aab5c671 100644 --- a/lib/sg_split.c +++ b/lib/sg_split.c @@ -88,8 +88,6 @@ static void sg_split_phys(struct sg_splitter *splitters, const int nb_splits) if (!j) { out_sg->offset += split->skip_sg0; out_sg->length -= split->skip_sg0; - } else { - out_sg->offset = 0; } sg_dma_address(out_sg) = 0; sg_dma_len(out_sg) = 0; diff --git a/lib/sort.c b/lib/sort.c index 048b7a6ef967..8e73dc55476b 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -200,6 +200,13 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size) * copy (e.g. fix up pointers or auxiliary data), but the built-in swap * avoids a slow retpoline and so is significantly faster. * + * The comparison function must adhere to specific mathematical + * properties to ensure correct and stable sorting: + * - Antisymmetry: cmp_func(a, b) must return the opposite sign of + * cmp_func(b, a). + * - Transitivity: if cmp_func(a, b) <= 0 and cmp_func(b, c) <= 0, then + * cmp_func(a, c) <= 0. + * * Sorting time is O(n log n) both on average and worst-case. While * quicksort is slightly faster on average, it suffers from exploitable * O(n*n) worst-case behavior and extra memory requirements that make diff --git a/lib/stackinit_kunit.c b/lib/stackinit_kunit.c index c40818ec9c18..63aa78e6f5c1 100644 --- a/lib/stackinit_kunit.c +++ b/lib/stackinit_kunit.c @@ -47,10 +47,12 @@ static bool stackinit_range_contains(char *haystack_start, size_t haystack_size, #define DO_NOTHING_TYPE_SCALAR(var_type) var_type #define DO_NOTHING_TYPE_STRING(var_type) void #define DO_NOTHING_TYPE_STRUCT(var_type) void +#define DO_NOTHING_TYPE_UNION(var_type) void #define DO_NOTHING_RETURN_SCALAR(ptr) *(ptr) #define DO_NOTHING_RETURN_STRING(ptr) /**/ #define DO_NOTHING_RETURN_STRUCT(ptr) /**/ +#define DO_NOTHING_RETURN_UNION(ptr) /**/ #define DO_NOTHING_CALL_SCALAR(var, name) \ (var) = do_nothing_ ## name(&(var)) @@ -58,10 +60,13 @@ static bool stackinit_range_contains(char *haystack_start, size_t haystack_size, do_nothing_ ## name(var) #define DO_NOTHING_CALL_STRUCT(var, name) \ do_nothing_ ## name(&(var)) +#define DO_NOTHING_CALL_UNION(var, name) \ + do_nothing_ ## name(&(var)) #define FETCH_ARG_SCALAR(var) &var #define FETCH_ARG_STRING(var) var #define FETCH_ARG_STRUCT(var) &var +#define FETCH_ARG_UNION(var) &var /* * On m68k, if the leaf function test variable is longer than 8 bytes, @@ -70,13 +75,16 @@ static bool stackinit_range_contains(char *haystack_start, size_t haystack_size, */ #ifdef CONFIG_M68K #define FILL_SIZE_STRING 8 +#define FILL_SIZE_ARRAY 2 #else #define FILL_SIZE_STRING 16 +#define FILL_SIZE_ARRAY 8 #endif #define INIT_CLONE_SCALAR /**/ #define INIT_CLONE_STRING [FILL_SIZE_STRING] #define INIT_CLONE_STRUCT /**/ +#define INIT_CLONE_UNION /**/ #define ZERO_CLONE_SCALAR(zero) memset(&(zero), 0x00, sizeof(zero)) #define ZERO_CLONE_STRING(zero) memset(&(zero), 0x00, sizeof(zero)) @@ -92,6 +100,7 @@ static bool stackinit_range_contains(char *haystack_start, size_t haystack_size, zero.three = 0; \ zero.four = 0; \ } while (0) +#define ZERO_CLONE_UNION(zero) ZERO_CLONE_STRUCT(zero) #define INIT_SCALAR_none(var_type) /**/ #define INIT_SCALAR_zero(var_type) = 0 @@ -101,6 +110,7 @@ static bool stackinit_range_contains(char *haystack_start, size_t haystack_size, #define INIT_STRUCT_none(var_type) /**/ #define INIT_STRUCT_zero(var_type) = { } +#define INIT_STRUCT_old_zero(var_type) = { 0 } #define __static_partial { .two = 0, } @@ -146,6 +156,43 @@ static bool stackinit_range_contains(char *haystack_start, size_t haystack_size, #define INIT_STRUCT_assigned_copy(var_type) \ ; var = *(arg) +/* Union initialization is the same as structs. */ +#define INIT_UNION_none(var_type) INIT_STRUCT_none(var_type) +#define INIT_UNION_zero(var_type) INIT_STRUCT_zero(var_type) +#define INIT_UNION_old_zero(var_type) INIT_STRUCT_old_zero(var_type) + +#define INIT_UNION_static_partial(var_type) \ + INIT_STRUCT_static_partial(var_type) +#define INIT_UNION_static_all(var_type) \ + INIT_STRUCT_static_all(var_type) +#define INIT_UNION_dynamic_partial(var_type) \ + INIT_STRUCT_dynamic_partial(var_type) +#define INIT_UNION_dynamic_all(var_type) \ + INIT_STRUCT_dynamic_all(var_type) +#define INIT_UNION_runtime_partial(var_type) \ + INIT_STRUCT_runtime_partial(var_type) +#define INIT_UNION_runtime_all(var_type) \ + INIT_STRUCT_runtime_all(var_type) +#define INIT_UNION_assigned_static_partial(var_type) \ + INIT_STRUCT_assigned_static_partial(var_type) +#define INIT_UNION_assigned_static_all(var_type) \ + INIT_STRUCT_assigned_static_all(var_type) +#define INIT_UNION_assigned_dynamic_partial(var_type) \ + INIT_STRUCT_assigned_dynamic_partial(var_type) +#define INIT_UNION_assigned_dynamic_all(var_type) \ + INIT_STRUCT_assigned_dynamic_all(var_type) +#define INIT_UNION_assigned_copy(var_type) \ + INIT_STRUCT_assigned_copy(var_type) + +/* + * The "did we actually fill the stack?" check value needs + * to be neither 0 nor any of the "pattern" bytes. The + * pattern bytes are compiler, architecture, and type based, + * so we have to pick a value that never appears for those + * combinations. Use 0x99 which is not 0xFF, 0xFE, nor 0xAA. + */ +#define FILL_BYTE 0x99 + /* * @name: unique string name for the test * @var_type: type to be tested for zeroing initialization @@ -168,12 +215,12 @@ static noinline void test_ ## name (struct kunit *test) \ ZERO_CLONE_ ## which(zero); \ /* Clear entire check buffer for 0xFF overlap test. */ \ memset(check_buf, 0x00, sizeof(check_buf)); \ - /* Fill stack with 0xFF. */ \ + /* Fill stack with FILL_BYTE. */ \ ignored = leaf_ ##name((unsigned long)&ignored, 1, \ FETCH_ARG_ ## which(zero)); \ - /* Verify all bytes overwritten with 0xFF. */ \ + /* Verify all bytes overwritten with FILL_BYTE. */ \ for (sum = 0, i = 0; i < target_size; i++) \ - sum += (check_buf[i] != 0xFF); \ + sum += (check_buf[i] != FILL_BYTE); \ /* Clear entire check buffer for later bit tests. */ \ memset(check_buf, 0x00, sizeof(check_buf)); \ /* Extract stack-defined variable contents. */ \ @@ -184,7 +231,8 @@ static noinline void test_ ## name (struct kunit *test) \ * possible between the two leaf function calls. \ */ \ KUNIT_ASSERT_EQ_MSG(test, sum, 0, \ - "leaf fill was not 0xFF!?\n"); \ + "leaf fill was not 0x%02X!?\n", \ + FILL_BYTE); \ \ /* Validate that compiler lined up fill and target. */ \ KUNIT_ASSERT_TRUE_MSG(test, \ @@ -196,9 +244,9 @@ static noinline void test_ ## name (struct kunit *test) \ (int)((ssize_t)(uintptr_t)fill_start - \ (ssize_t)(uintptr_t)target_start)); \ \ - /* Look for any bytes still 0xFF in check region. */ \ + /* Validate check region has no FILL_BYTE bytes. */ \ for (sum = 0, i = 0; i < target_size; i++) \ - sum += (check_buf[i] == 0xFF); \ + sum += (check_buf[i] == FILL_BYTE); \ \ if (sum != 0 && xfail) \ kunit_skip(test, \ @@ -233,12 +281,12 @@ static noinline int leaf_ ## name(unsigned long sp, bool fill, \ * stack frame of SOME kind... \ */ \ memset(buf, (char)(sp & 0xff), sizeof(buf)); \ - /* Fill variable with 0xFF. */ \ + /* Fill variable with FILL_BYTE. */ \ if (fill) { \ fill_start = &var; \ fill_size = sizeof(var); \ memset(fill_start, \ - (char)((sp & 0xff) | forced_mask), \ + FILL_BYTE & forced_mask, \ fill_size); \ } \ \ @@ -294,6 +342,33 @@ struct test_user { unsigned long four; }; +/* No padding: all members are the same size. */ +union test_same_sizes { + unsigned long one; + unsigned long two; + unsigned long three; + unsigned long four; +}; + +/* Mismatched sizes, with one and two being small */ +union test_small_start { + char one:1; + char two; + short three; + unsigned long four; + struct big_struct { + unsigned long array[FILL_SIZE_ARRAY]; + } big; +}; + +/* Mismatched sizes, with three and four being small */ +union test_small_end { + short one; + unsigned long two; + char three:1; + char four; +}; + #define ALWAYS_PASS WANT_SUCCESS #define ALWAYS_FAIL XFAIL @@ -332,6 +407,11 @@ struct test_user { struct test_ ## name, STRUCT, init, \ xfail) +#define DEFINE_UNION_TEST(name, init, xfail) \ + DEFINE_TEST(name ## _ ## init, \ + union test_ ## name, STRUCT, init, \ + xfail) + #define DEFINE_STRUCT_TESTS(init, xfail) \ DEFINE_STRUCT_TEST(small_hole, init, xfail); \ DEFINE_STRUCT_TEST(big_hole, init, xfail); \ @@ -343,9 +423,22 @@ struct test_user { xfail); \ DEFINE_STRUCT_TESTS(base ## _ ## all, xfail) +#define DEFINE_UNION_INITIALIZER_TESTS(base, xfail) \ + DEFINE_UNION_TESTS(base ## _ ## partial, \ + xfail); \ + DEFINE_UNION_TESTS(base ## _ ## all, xfail) + +#define DEFINE_UNION_TESTS(init, xfail) \ + DEFINE_UNION_TEST(same_sizes, init, xfail); \ + DEFINE_UNION_TEST(small_start, init, xfail); \ + DEFINE_UNION_TEST(small_end, init, xfail); + /* These should be fully initialized all the time! */ DEFINE_SCALAR_TESTS(zero, ALWAYS_PASS); DEFINE_STRUCT_TESTS(zero, ALWAYS_PASS); +DEFINE_STRUCT_TESTS(old_zero, ALWAYS_PASS); +DEFINE_UNION_TESTS(zero, ALWAYS_PASS); +DEFINE_UNION_TESTS(old_zero, ALWAYS_PASS); /* Struct initializers: padding may be left uninitialized. */ DEFINE_STRUCT_INITIALIZER_TESTS(static, STRONG_PASS); DEFINE_STRUCT_INITIALIZER_TESTS(dynamic, STRONG_PASS); @@ -353,6 +446,12 @@ DEFINE_STRUCT_INITIALIZER_TESTS(runtime, STRONG_PASS); DEFINE_STRUCT_INITIALIZER_TESTS(assigned_static, STRONG_PASS); DEFINE_STRUCT_INITIALIZER_TESTS(assigned_dynamic, STRONG_PASS); DEFINE_STRUCT_TESTS(assigned_copy, ALWAYS_FAIL); +DEFINE_UNION_INITIALIZER_TESTS(static, STRONG_PASS); +DEFINE_UNION_INITIALIZER_TESTS(dynamic, STRONG_PASS); +DEFINE_UNION_INITIALIZER_TESTS(runtime, STRONG_PASS); +DEFINE_UNION_INITIALIZER_TESTS(assigned_static, STRONG_PASS); +DEFINE_UNION_INITIALIZER_TESTS(assigned_dynamic, STRONG_PASS); +DEFINE_UNION_TESTS(assigned_copy, ALWAYS_FAIL); /* No initialization without compiler instrumentation. */ DEFINE_SCALAR_TESTS(none, STRONG_PASS); DEFINE_STRUCT_TESTS(none, BYREF_PASS); @@ -380,7 +479,7 @@ static int noinline __leaf_switch_none(int path, bool fill) fill_start = &var; fill_size = sizeof(var); - memset(fill_start, forced_mask | 0x55, fill_size); + memset(fill_start, (forced_mask | 0x55) & FILL_BYTE, fill_size); } memcpy(check_buf, target_start, target_size); break; @@ -391,7 +490,7 @@ static int noinline __leaf_switch_none(int path, bool fill) fill_start = &var; fill_size = sizeof(var); - memset(fill_start, forced_mask | 0xaa, fill_size); + memset(fill_start, (forced_mask | 0xaa) & FILL_BYTE, fill_size); } memcpy(check_buf, target_start, target_size); break; @@ -436,13 +535,23 @@ DEFINE_TEST_DRIVER(switch_2_none, uint64_t, SCALAR, ALWAYS_FAIL); KUNIT_CASE(test_trailing_hole_ ## init),\ KUNIT_CASE(test_packed_ ## init) \ +#define KUNIT_test_unions(init) \ + KUNIT_CASE(test_same_sizes_ ## init), \ + KUNIT_CASE(test_small_start_ ## init), \ + KUNIT_CASE(test_small_end_ ## init) \ + static struct kunit_case stackinit_test_cases[] = { /* These are explicitly initialized and should always pass. */ KUNIT_test_scalars(zero), KUNIT_test_structs(zero), + KUNIT_test_structs(old_zero), + KUNIT_test_unions(zero), + KUNIT_test_unions(old_zero), /* Padding here appears to be accidentally always initialized? */ KUNIT_test_structs(dynamic_partial), KUNIT_test_structs(assigned_dynamic_partial), + KUNIT_test_unions(dynamic_partial), + KUNIT_test_unions(assigned_dynamic_partial), /* Padding initialization depends on compiler behaviors. */ KUNIT_test_structs(static_partial), KUNIT_test_structs(static_all), @@ -452,8 +561,17 @@ static struct kunit_case stackinit_test_cases[] = { KUNIT_test_structs(assigned_static_partial), KUNIT_test_structs(assigned_static_all), KUNIT_test_structs(assigned_dynamic_all), + KUNIT_test_unions(static_partial), + KUNIT_test_unions(static_all), + KUNIT_test_unions(dynamic_all), + KUNIT_test_unions(runtime_partial), + KUNIT_test_unions(runtime_all), + KUNIT_test_unions(assigned_static_partial), + KUNIT_test_unions(assigned_static_all), + KUNIT_test_unions(assigned_dynamic_all), /* Everything fails this since it effectively performs a memcpy(). */ KUNIT_test_structs(assigned_copy), + KUNIT_test_unions(assigned_copy), /* STRUCTLEAK_BYREF_ALL should cover everything from here down. */ KUNIT_test_scalars(none), KUNIT_CASE(test_switch_1_none), diff --git a/lib/string.c b/lib/string.c index eb4486ed40d2..b632c71df1a5 100644 --- a/lib/string.c +++ b/lib/string.c @@ -119,6 +119,7 @@ ssize_t sized_strscpy(char *dest, const char *src, size_t count) if (count == 0 || WARN_ON_ONCE(count > INT_MAX)) return -E2BIG; +#ifndef CONFIG_DCACHE_WORD_ACCESS #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS /* * If src is unaligned, don't cross a page boundary, @@ -134,11 +135,13 @@ ssize_t sized_strscpy(char *dest, const char *src, size_t count) if (((long) dest | (long) src) & (sizeof(long) - 1)) max = 0; #endif +#endif /* - * read_word_at_a_time() below may read uninitialized bytes after the - * trailing zero and use them in comparisons. Disable this optimization - * under KMSAN to prevent false positive reports. + * load_unaligned_zeropad() or read_word_at_a_time() below may read + * uninitialized bytes after the trailing zero and use them in + * comparisons. Disable this optimization under KMSAN to prevent + * false positive reports. */ if (IS_ENABLED(CONFIG_KMSAN)) max = 0; @@ -146,7 +149,11 @@ ssize_t sized_strscpy(char *dest, const char *src, size_t count) while (max >= sizeof(unsigned long)) { unsigned long c, data; +#ifdef CONFIG_DCACHE_WORD_ACCESS + c = load_unaligned_zeropad(src+res); +#else c = read_word_at_a_time(src+res); +#endif if (has_zero(c, &data, &constants)) { data = prep_zero_mask(c, data, &constants); data = create_zero_mask(data); diff --git a/lib/test_bpf.c b/lib/test_bpf.c index 2eed1ad958e9..af0041df2b72 100644 --- a/lib/test_bpf.c +++ b/lib/test_bpf.c @@ -478,7 +478,7 @@ static int __bpf_ld_imm64(struct bpf_insn insns[2], u8 reg, s64 imm64) * to overflow the field size of the native instruction, triggering * a branch conversion mechanism in some JITs. */ -static int __bpf_fill_max_jmp(struct bpf_test *self, int jmp, int imm) +static int __bpf_fill_max_jmp(struct bpf_test *self, int jmp, int imm, bool alu32) { struct bpf_insn *insns; int len = S16_MAX + 5; @@ -501,7 +501,7 @@ static int __bpf_fill_max_jmp(struct bpf_test *self, int jmp, int imm) }; int op = ops[(i >> 1) % ARRAY_SIZE(ops)]; - if (i & 1) + if ((i & 1) || alu32) insns[i++] = BPF_ALU32_REG(op, R0, R1); else insns[i++] = BPF_ALU64_REG(op, R0, R1); @@ -516,27 +516,47 @@ static int __bpf_fill_max_jmp(struct bpf_test *self, int jmp, int imm) } /* Branch taken by runtime decision */ +static int bpf_fill_max_jmp_taken_32(struct bpf_test *self) +{ + return __bpf_fill_max_jmp(self, BPF_JEQ, 1, true); +} + static int bpf_fill_max_jmp_taken(struct bpf_test *self) { - return __bpf_fill_max_jmp(self, BPF_JEQ, 1); + return __bpf_fill_max_jmp(self, BPF_JEQ, 1, false); } /* Branch not taken by runtime decision */ +static int bpf_fill_max_jmp_not_taken_32(struct bpf_test *self) +{ + return __bpf_fill_max_jmp(self, BPF_JEQ, 0, true); +} + static int bpf_fill_max_jmp_not_taken(struct bpf_test *self) { - return __bpf_fill_max_jmp(self, BPF_JEQ, 0); + return __bpf_fill_max_jmp(self, BPF_JEQ, 0, false); } /* Branch always taken, known at JIT time */ +static int bpf_fill_max_jmp_always_taken_32(struct bpf_test *self) +{ + return __bpf_fill_max_jmp(self, BPF_JGE, 0, true); +} + static int bpf_fill_max_jmp_always_taken(struct bpf_test *self) { - return __bpf_fill_max_jmp(self, BPF_JGE, 0); + return __bpf_fill_max_jmp(self, BPF_JGE, 0, false); } /* Branch never taken, known at JIT time */ +static int bpf_fill_max_jmp_never_taken_32(struct bpf_test *self) +{ + return __bpf_fill_max_jmp(self, BPF_JLT, 0, true); +} + static int bpf_fill_max_jmp_never_taken(struct bpf_test *self) { - return __bpf_fill_max_jmp(self, BPF_JLT, 0); + return __bpf_fill_max_jmp(self, BPF_JLT, 0, false); } /* ALU result computation used in tests */ @@ -14234,6 +14254,38 @@ static struct bpf_test tests[] = { }, /* Conditional branch conversions */ { + "Long conditional jump: taken at runtime (32 bits)", + { }, + INTERNAL | FLAG_NO_DATA, + { }, + { { 0, 1 } }, + .fill_helper = bpf_fill_max_jmp_taken_32, + }, + { + "Long conditional jump: not taken at runtime (32 bits)", + { }, + INTERNAL | FLAG_NO_DATA, + { }, + { { 0, 2 } }, + .fill_helper = bpf_fill_max_jmp_not_taken_32, + }, + { + "Long conditional jump: always taken, known at JIT time (32 bits)", + { }, + INTERNAL | FLAG_NO_DATA, + { }, + { { 0, 1 } }, + .fill_helper = bpf_fill_max_jmp_always_taken_32, + }, + { + "Long conditional jump: never taken, known at JIT time (32 bits)", + { }, + INTERNAL | FLAG_NO_DATA, + { }, + { { 0, 2 } }, + .fill_helper = bpf_fill_max_jmp_never_taken_32, + }, + { "Long conditional jump: taken at runtime", { }, INTERNAL | FLAG_NO_DATA, diff --git a/lib/test_fprobe.c b/lib/test_fprobe.c index 24de0e5ff859..cf92111b5c79 100644 --- a/lib/test_fprobe.c +++ b/lib/test_fprobe.c @@ -17,10 +17,8 @@ static u32 rand1, entry_val, exit_val; /* Use indirect calls to avoid inlining the target functions */ static u32 (*target)(u32 value); static u32 (*target2)(u32 value); -static u32 (*target_nest)(u32 value, u32 (*nest)(u32)); static unsigned long target_ip; static unsigned long target2_ip; -static unsigned long target_nest_ip; static int entry_return_value; static noinline u32 fprobe_selftest_target(u32 value) @@ -33,14 +31,9 @@ static noinline u32 fprobe_selftest_target2(u32 value) return (value / div_factor) + 1; } -static noinline u32 fprobe_selftest_nest_target(u32 value, u32 (*nest)(u32)) -{ - return nest(value + 2); -} - static notrace int fp_entry_handler(struct fprobe *fp, unsigned long ip, unsigned long ret_ip, - struct pt_regs *regs, void *data) + struct ftrace_regs *fregs, void *data) { KUNIT_EXPECT_FALSE(current_test, preemptible()); /* This can be called on the fprobe_selftest_target and the fprobe_selftest_target2 */ @@ -59,9 +52,9 @@ static notrace int fp_entry_handler(struct fprobe *fp, unsigned long ip, static notrace void fp_exit_handler(struct fprobe *fp, unsigned long ip, unsigned long ret_ip, - struct pt_regs *regs, void *data) + struct ftrace_regs *fregs, void *data) { - unsigned long ret = regs_return_value(regs); + unsigned long ret = ftrace_regs_get_return_value(fregs); KUNIT_EXPECT_FALSE(current_test, preemptible()); if (ip != target_ip) { @@ -79,22 +72,6 @@ static notrace void fp_exit_handler(struct fprobe *fp, unsigned long ip, KUNIT_EXPECT_NULL(current_test, data); } -static notrace int nest_entry_handler(struct fprobe *fp, unsigned long ip, - unsigned long ret_ip, - struct pt_regs *regs, void *data) -{ - KUNIT_EXPECT_FALSE(current_test, preemptible()); - return 0; -} - -static notrace void nest_exit_handler(struct fprobe *fp, unsigned long ip, - unsigned long ret_ip, - struct pt_regs *regs, void *data) -{ - KUNIT_EXPECT_FALSE(current_test, preemptible()); - KUNIT_EXPECT_EQ(current_test, ip, target_nest_ip); -} - /* Test entry only (no rethook) */ static void test_fprobe_entry(struct kunit *test) { @@ -191,25 +168,6 @@ static void test_fprobe_data(struct kunit *test) KUNIT_EXPECT_EQ(test, 0, unregister_fprobe(&fp)); } -/* Test nr_maxactive */ -static void test_fprobe_nest(struct kunit *test) -{ - static const char *syms[] = {"fprobe_selftest_target", "fprobe_selftest_nest_target"}; - struct fprobe fp = { - .entry_handler = nest_entry_handler, - .exit_handler = nest_exit_handler, - .nr_maxactive = 1, - }; - - current_test = test; - KUNIT_EXPECT_EQ(test, 0, register_fprobe_syms(&fp, syms, 2)); - - target_nest(rand1, target); - KUNIT_EXPECT_EQ(test, 1, fp.nmissed); - - KUNIT_EXPECT_EQ(test, 0, unregister_fprobe(&fp)); -} - static void test_fprobe_skip(struct kunit *test) { struct fprobe fp = { @@ -247,10 +205,8 @@ static int fprobe_test_init(struct kunit *test) rand1 = get_random_u32_above(div_factor); target = fprobe_selftest_target; target2 = fprobe_selftest_target2; - target_nest = fprobe_selftest_nest_target; target_ip = get_ftrace_location(target); target2_ip = get_ftrace_location(target2); - target_nest_ip = get_ftrace_location(target_nest); return 0; } @@ -260,7 +216,6 @@ static struct kunit_case fprobe_testcases[] = { KUNIT_CASE(test_fprobe), KUNIT_CASE(test_fprobe_syms), KUNIT_CASE(test_fprobe_data), - KUNIT_CASE(test_fprobe_nest), KUNIT_CASE(test_fprobe_skip), {} }; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 704cb1093ae8..13e2a10d7554 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1563,6 +1563,30 @@ static noinline void __init check_root_expand(struct maple_tree *mt) mas_unlock(&mas); } +static noinline void __init check_deficient_node(struct maple_tree *mt) +{ + MA_STATE(mas, mt, 0, 0); + int count; + + mas_lock(&mas); + for (count = 0; count < 10; count++) { + mas_set(&mas, count); + mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); + } + + for (count = 20; count < 39; count++) { + mas_set(&mas, count); + mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); + } + + for (count = 10; count < 12; count++) { + mas_set(&mas, count); + mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL); + } + mas_unlock(&mas); + mt_validate(mt); +} + static noinline void __init check_gap_combining(struct maple_tree *mt) { struct maple_enode *mn1, *mn2; @@ -3714,6 +3738,34 @@ static noinline void __init alloc_cyclic_testing(struct maple_tree *mt) } mtree_destroy(mt); + + /* + * Issue with reverse search was discovered + * https://lore.kernel.org/all/20241216060600.287B4C4CED0@smtp.kernel.org/ + * Exhausting the allocation area and forcing the search to wrap needs a + * mas_reset() in mas_alloc_cyclic(). + */ + next = 0; + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (int i = 0; i < 1023; i++) { + mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL); + MT_BUG_ON(mt, i != location - 2); + MT_BUG_ON(mt, i != next - 3); + MT_BUG_ON(mt, mtree_load(mt, location) != mt); + } + mtree_erase(mt, 123); + MT_BUG_ON(mt, mtree_load(mt, 123) != NULL); + mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL); + MT_BUG_ON(mt, 123 != location); + MT_BUG_ON(mt, 124 != next); + MT_BUG_ON(mt, mtree_load(mt, location) != mt); + mtree_erase(mt, 100); + mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL); + MT_BUG_ON(mt, 100 != location); + MT_BUG_ON(mt, 101 != next); + MT_BUG_ON(mt, mtree_load(mt, location) != mt); + mtree_destroy(mt); + /* Overflow test */ next = ULONG_MAX - 1; ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); @@ -3797,6 +3849,10 @@ static int __init maple_tree_seed(void) #endif mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_deficient_node(&tree); + mtree_destroy(&tree); + + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_store_null(&tree); mtree_destroy(&tree); diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index e6fbb798558b..a9c4a74d3898 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -32,7 +32,7 @@ static __init int pop_verify_heap(bool min_heap, int last; last = values[0]; - min_heap_pop(heap, funcs, NULL); + min_heap_pop_inline(heap, funcs, NULL); while (heap->nr > 0) { if (min_heap) { if (last > values[0]) { @@ -48,7 +48,7 @@ static __init int pop_verify_heap(bool min_heap, } } last = values[0]; - min_heap_pop(heap, funcs, NULL); + min_heap_pop_inline(heap, funcs, NULL); } return err; } @@ -69,7 +69,7 @@ static __init int test_heapify_all(bool min_heap) int i, err; /* Test with known set of values. */ - min_heapify_all(&heap, &funcs, NULL); + min_heapify_all_inline(&heap, &funcs, NULL); err = pop_verify_heap(min_heap, &heap, &funcs); @@ -78,7 +78,7 @@ static __init int test_heapify_all(bool min_heap) for (i = 0; i < heap.nr; i++) values[i] = get_random_u32(); - min_heapify_all(&heap, &funcs, NULL); + min_heapify_all_inline(&heap, &funcs, NULL); err += pop_verify_heap(min_heap, &heap, &funcs); return err; @@ -102,14 +102,14 @@ static __init int test_heap_push(bool min_heap) /* Test with known set of values copied from data. */ for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &data[i], &funcs, NULL); + min_heap_push_inline(&heap, &data[i], &funcs, NULL); err = pop_verify_heap(min_heap, &heap, &funcs); /* Test with randomly generated values. */ while (heap.nr < heap.size) { temp = get_random_u32(); - min_heap_push(&heap, &temp, &funcs, NULL); + min_heap_push_inline(&heap, &temp, &funcs, NULL); } err += pop_verify_heap(min_heap, &heap, &funcs); @@ -135,22 +135,22 @@ static __init int test_heap_pop_push(bool min_heap) /* Fill values with data to pop and replace. */ temp = min_heap ? 0x80000000 : 0x7FFFFFFF; for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs, NULL); + min_heap_push_inline(&heap, &temp, &funcs, NULL); /* Test with known set of values copied from data. */ for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_pop_push(&heap, &data[i], &funcs, NULL); + min_heap_pop_push_inline(&heap, &data[i], &funcs, NULL); err = pop_verify_heap(min_heap, &heap, &funcs); heap.nr = 0; for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs, NULL); + min_heap_push_inline(&heap, &temp, &funcs, NULL); /* Test with randomly generated values. */ for (i = 0; i < ARRAY_SIZE(data); i++) { temp = get_random_u32(); - min_heap_pop_push(&heap, &temp, &funcs, NULL); + min_heap_pop_push_inline(&heap, &temp, &funcs, NULL); } err += pop_verify_heap(min_heap, &heap, &funcs); @@ -163,7 +163,7 @@ static __init int test_heap_del(bool min_heap) -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; struct min_heap_test heap; - min_heap_init(&heap, values, ARRAY_SIZE(values)); + min_heap_init_inline(&heap, values, ARRAY_SIZE(values)); heap.nr = ARRAY_SIZE(values); struct min_heap_callbacks funcs = { .less = min_heap ? less_than : greater_than, @@ -172,9 +172,9 @@ static __init int test_heap_del(bool min_heap) int i, err; /* Test with known set of values. */ - min_heapify_all(&heap, &funcs, NULL); + min_heapify_all_inline(&heap, &funcs, NULL); for (i = 0; i < ARRAY_SIZE(values) / 2; i++) - min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + min_heap_del_inline(&heap, get_random_u32() % heap.nr, &funcs, NULL); err = pop_verify_heap(min_heap, &heap, &funcs); @@ -182,10 +182,10 @@ static __init int test_heap_del(bool min_heap) heap.nr = ARRAY_SIZE(values); for (i = 0; i < heap.nr; i++) values[i] = get_random_u32(); - min_heapify_all(&heap, &funcs, NULL); + min_heapify_all_inline(&heap, &funcs, NULL); for (i = 0; i < ARRAY_SIZE(values) / 2; i++) - min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + min_heap_del_inline(&heap, get_random_u32() % heap.nr, &funcs, NULL); err += pop_verify_heap(min_heap, &heap, &funcs); return err; diff --git a/lib/test_objpool.c b/lib/test_objpool.c index 5a3f6961a70f..896c0131c9a8 100644 --- a/lib/test_objpool.c +++ b/lib/test_objpool.c @@ -371,14 +371,10 @@ static int ot_start_sync(struct ot_test *test) if (!cpu_online(cpu)) continue; - work = kthread_create_on_node(ot_thread_worker, item, - cpu_to_node(cpu), "ot_worker_%d", cpu); - if (IS_ERR(work)) { + work = kthread_run_on_cpu(ot_thread_worker, item, + cpu, "ot_worker_%d"); + if (IS_ERR(work)) pr_err("failed to create thread for cpu %d\n", cpu); - } else { - kthread_bind(work, cpu); - wake_up_process(work); - } } /* wait a while to make sure all threads waiting at start line */ @@ -562,14 +558,9 @@ static int ot_start_async(struct ot_test *test) if (!cpu_online(cpu)) continue; - work = kthread_create_on_node(ot_thread_worker, item, - cpu_to_node(cpu), "ot_worker_%d", cpu); - if (IS_ERR(work)) { + work = kthread_run_on_cpu(ot_thread_worker, item, cpu, "ot_worker_%d"); + if (IS_ERR(work)) pr_err("failed to create thread for cpu %d\n", cpu); - } else { - kthread_bind(work, cpu); - wake_up_process(work); - } } /* wait a while to make sure all threads waiting at start line */ diff --git a/lib/test_sysctl.c b/lib/test_sysctl.c index b6696fa1d426..4249e0cc8aaf 100644 --- a/lib/test_sysctl.c +++ b/lib/test_sysctl.c @@ -71,7 +71,7 @@ static struct test_sysctl_data test_data = { }; /* These are all under /proc/sys/debug/test_sysctl/ */ -static struct ctl_table test_table[] = { +static const struct ctl_table test_table[] = { { .procname = "int_0001", .data = &test_data.int_0001, @@ -177,7 +177,7 @@ static int test_sysctl_setup_node_tests(void) } /* Used to test that unregister actually removes the directory */ -static struct ctl_table test_table_unregister[] = { +static const struct ctl_table test_table_unregister[] = { { .procname = "unregister_error", .data = &test_data.int_0001, @@ -220,7 +220,7 @@ static int test_sysctl_run_register_mount_point(void) return 0; } -static struct ctl_table test_table_empty[] = { }; +static const struct ctl_table test_table_empty[] = { }; static int test_sysctl_run_register_empty(void) { diff --git a/lib/test_vmalloc.c b/lib/test_vmalloc.c index 4ddf769861ff..f585949ff696 100644 --- a/lib/test_vmalloc.c +++ b/lib/test_vmalloc.c @@ -373,7 +373,7 @@ vm_map_ram_test(void) if (!pages) return -1; - nr_allocated = alloc_pages_bulk_array(GFP_KERNEL, map_nr_pages, pages); + nr_allocated = alloc_pages_bulk(GFP_KERNEL, map_nr_pages, pages); if (nr_allocated != map_nr_pages) goto cleanup; diff --git a/lib/test_xarray.c b/lib/test_xarray.c index d5c5cbba33ed..0e865bab4a10 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1418,7 +1418,7 @@ static noinline void check_pause(struct xarray *xa) { XA_STATE(xas, xa, 0); void *entry; - unsigned int order; + int order; unsigned long index = 1; unsigned int count = 0; @@ -1448,6 +1448,42 @@ static noinline void check_pause(struct xarray *xa) XA_BUG_ON(xa, count != order_limit); xa_destroy(xa); + + index = 0; + for (order = order_limit - 1; order >= 0; order--) { + XA_BUG_ON(xa, xa_store_order(xa, index, order, + xa_mk_index(index), GFP_KERNEL)); + index += 1UL << order; + } + + index = 0; + count = 0; + xas_set(&xas, 0); + rcu_read_lock(); + xas_for_each(&xas, entry, ULONG_MAX) { + XA_BUG_ON(xa, entry != xa_mk_index(index)); + index += 1UL << (order_limit - count - 1); + count++; + } + rcu_read_unlock(); + XA_BUG_ON(xa, count != order_limit); + + index = 0; + count = 0; + /* test unaligned index */ + xas_set(&xas, 1 % (1UL << (order_limit - 1))); + rcu_read_lock(); + xas_for_each(&xas, entry, ULONG_MAX) { + XA_BUG_ON(xa, entry != xa_mk_index(index)); + index += 1UL << (order_limit - count - 1); + count++; + xas_pause(&xas); + } + rcu_read_unlock(); + XA_BUG_ON(xa, count != order_limit); + + xa_destroy(xa); + } static noinline void check_move_tiny(struct xarray *xa) diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 9d3dac38a3f4..a8ac4c4fffcf 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -160,8 +160,7 @@ long long simple_strtoll(const char *cp, char **endp, unsigned int base) } EXPORT_SYMBOL(simple_strtoll); -static noinline_for_stack -int skip_atoi(const char **s) +static inline int skip_atoi(const char **s) { int i = 0; @@ -407,7 +406,7 @@ int num_to_str(char *buf, int size, unsigned long long num, unsigned int width) return len + width; } -#define SIGN 1 /* unsigned/signed, must be 1 */ +#define SIGN 1 /* unsigned/signed */ #define LEFT 2 /* left justified */ #define PLUS 4 /* show plus */ #define SPACE 8 /* space if plus */ @@ -415,38 +414,26 @@ int num_to_str(char *buf, int size, unsigned long long num, unsigned int width) #define SMALL 32 /* use lowercase in hex (must be 32 == 0x20) */ #define SPECIAL 64 /* prefix hex with "0x", octal with "0" */ -static_assert(SIGN == 1); static_assert(ZEROPAD == ('0' - ' ')); static_assert(SMALL == ('a' ^ 'A')); -enum format_type { - FORMAT_TYPE_NONE, /* Just a string part */ - FORMAT_TYPE_WIDTH, - FORMAT_TYPE_PRECISION, - FORMAT_TYPE_CHAR, - FORMAT_TYPE_STR, - FORMAT_TYPE_PTR, - FORMAT_TYPE_PERCENT_CHAR, - FORMAT_TYPE_INVALID, - FORMAT_TYPE_LONG_LONG, - FORMAT_TYPE_ULONG, - FORMAT_TYPE_LONG, - FORMAT_TYPE_UBYTE, - FORMAT_TYPE_BYTE, - FORMAT_TYPE_USHORT, - FORMAT_TYPE_SHORT, - FORMAT_TYPE_UINT, - FORMAT_TYPE_INT, - FORMAT_TYPE_SIZE_T, - FORMAT_TYPE_PTRDIFF +enum format_state { + FORMAT_STATE_NONE, /* Just a string part */ + FORMAT_STATE_NUM, + FORMAT_STATE_WIDTH, + FORMAT_STATE_PRECISION, + FORMAT_STATE_CHAR, + FORMAT_STATE_STR, + FORMAT_STATE_PTR, + FORMAT_STATE_PERCENT_CHAR, + FORMAT_STATE_INVALID, }; struct printf_spec { - unsigned int type:8; /* format_type enum */ - signed int field_width:24; /* width of output field */ - unsigned int flags:8; /* flags to number() */ - unsigned int base:8; /* number base, 8, 10 or 16 only */ - signed int precision:16; /* # of digits/chars */ + unsigned char flags; /* flags to number() */ + unsigned char base; /* number base, 8, 10 or 16 only */ + short precision; /* # of digits/chars */ + int field_width; /* width of output field */ } __packed; static_assert(sizeof(struct printf_spec) == 8); @@ -579,7 +566,6 @@ char *special_hex_number(char *buf, char *end, unsigned long long num, int size) { struct printf_spec spec; - spec.type = FORMAT_TYPE_PTR; spec.field_width = 2 + 2 * size; /* 0x + hex */ spec.flags = SPECIAL | SMALL | ZEROPAD; spec.base = 16; @@ -2299,7 +2285,7 @@ int __init no_hash_pointers_enable(char *str) early_param("no_hash_pointers", no_hash_pointers_enable); /* Used for Rust formatting ('%pA'). */ -char *rust_fmt_argument(char *buf, char *end, void *ptr); +char *rust_fmt_argument(char *buf, char *end, const void *ptr); /* * Show a '%p' thing. A kernel extension is that the '%p' is followed @@ -2530,6 +2516,26 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr, } } +struct fmt { + const char *str; + unsigned char state; // enum format_state + unsigned char size; // size of numbers +}; + +#define SPEC_CHAR(x, flag) [(x)-32] = flag +static unsigned char spec_flag(unsigned char c) +{ + static const unsigned char spec_flag_array[] = { + SPEC_CHAR(' ', SPACE), + SPEC_CHAR('#', SPECIAL), + SPEC_CHAR('+', PLUS), + SPEC_CHAR('-', LEFT), + SPEC_CHAR('0', ZEROPAD), + }; + c -= 32; + return (c < sizeof(spec_flag_array)) ? spec_flag_array[c] : 0; +} + /* * Helper function to decode printf style format. * Each call decode a token from the format and return the @@ -2552,181 +2558,141 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr, * @qualifier: qualifier of a number (long, size_t, ...) */ static noinline_for_stack -int format_decode(const char *fmt, struct printf_spec *spec) +struct fmt format_decode(struct fmt fmt, struct printf_spec *spec) { - const char *start = fmt; - char qualifier; + const char *start = fmt.str; + char flag; /* we finished early by reading the field width */ - if (spec->type == FORMAT_TYPE_WIDTH) { + if (unlikely(fmt.state == FORMAT_STATE_WIDTH)) { if (spec->field_width < 0) { spec->field_width = -spec->field_width; spec->flags |= LEFT; } - spec->type = FORMAT_TYPE_NONE; + fmt.state = FORMAT_STATE_NONE; goto precision; } /* we finished early by reading the precision */ - if (spec->type == FORMAT_TYPE_PRECISION) { + if (unlikely(fmt.state == FORMAT_STATE_PRECISION)) { if (spec->precision < 0) spec->precision = 0; - spec->type = FORMAT_TYPE_NONE; + fmt.state = FORMAT_STATE_NONE; goto qualifier; } /* By default */ - spec->type = FORMAT_TYPE_NONE; + fmt.state = FORMAT_STATE_NONE; - for (; *fmt ; ++fmt) { - if (*fmt == '%') + for (; *fmt.str ; fmt.str++) { + if (*fmt.str == '%') break; } /* Return the current non-format string */ - if (fmt != start || !*fmt) - return fmt - start; + if (fmt.str != start || !*fmt.str) + return fmt; - /* Process flags */ + /* Process flags. This also skips the first '%' */ spec->flags = 0; - - while (1) { /* this also skips first '%' */ - bool found = true; - - ++fmt; - - switch (*fmt) { - case '-': spec->flags |= LEFT; break; - case '+': spec->flags |= PLUS; break; - case ' ': spec->flags |= SPACE; break; - case '#': spec->flags |= SPECIAL; break; - case '0': spec->flags |= ZEROPAD; break; - default: found = false; - } - - if (!found) - break; - } + do { + /* this also skips first '%' */ + flag = spec_flag(*++fmt.str); + spec->flags |= flag; + } while (flag); /* get field width */ spec->field_width = -1; - if (isdigit(*fmt)) - spec->field_width = skip_atoi(&fmt); - else if (*fmt == '*') { + if (isdigit(*fmt.str)) + spec->field_width = skip_atoi(&fmt.str); + else if (unlikely(*fmt.str == '*')) { /* it's the next argument */ - spec->type = FORMAT_TYPE_WIDTH; - return ++fmt - start; + fmt.state = FORMAT_STATE_WIDTH; + fmt.str++; + return fmt; } precision: /* get the precision */ spec->precision = -1; - if (*fmt == '.') { - ++fmt; - if (isdigit(*fmt)) { - spec->precision = skip_atoi(&fmt); + if (unlikely(*fmt.str == '.')) { + fmt.str++; + if (isdigit(*fmt.str)) { + spec->precision = skip_atoi(&fmt.str); if (spec->precision < 0) spec->precision = 0; - } else if (*fmt == '*') { + } else if (*fmt.str == '*') { /* it's the next argument */ - spec->type = FORMAT_TYPE_PRECISION; - return ++fmt - start; + fmt.state = FORMAT_STATE_PRECISION; + fmt.str++; + return fmt; } } qualifier: - /* get the conversion qualifier */ - qualifier = 0; - if (*fmt == 'h' || _tolower(*fmt) == 'l' || - *fmt == 'z' || *fmt == 't') { - qualifier = *fmt++; - if (unlikely(qualifier == *fmt)) { - if (qualifier == 'l') { - qualifier = 'L'; - ++fmt; - } else if (qualifier == 'h') { - qualifier = 'H'; - ++fmt; - } - } - } - - /* default base */ + /* Set up default numeric format */ spec->base = 10; - switch (*fmt) { - case 'c': - spec->type = FORMAT_TYPE_CHAR; - return ++fmt - start; - - case 's': - spec->type = FORMAT_TYPE_STR; - return ++fmt - start; - - case 'p': - spec->type = FORMAT_TYPE_PTR; - return ++fmt - start; - - case '%': - spec->type = FORMAT_TYPE_PERCENT_CHAR; - return ++fmt - start; - - /* integer number formats - set up the flags and "break" */ - case 'o': - spec->base = 8; - break; - - case 'x': - spec->flags |= SMALL; - fallthrough; - - case 'X': - spec->base = 16; - break; + fmt.state = FORMAT_STATE_NUM; + fmt.size = sizeof(int); + static const struct format_state { + unsigned char state; + unsigned char size; + unsigned char flags_or_double_size; + unsigned char base; + } lookup_state[256] = { + // Length + ['l'] = { 0, sizeof(long), sizeof(long long) }, + ['L'] = { 0, sizeof(long long) }, + ['h'] = { 0, sizeof(short), sizeof(char) }, + ['H'] = { 0, sizeof(char) }, // Questionable historical + ['z'] = { 0, sizeof(size_t) }, + ['t'] = { 0, sizeof(ptrdiff_t) }, + + // Non-numeric formats + ['c'] = { FORMAT_STATE_CHAR }, + ['s'] = { FORMAT_STATE_STR }, + ['p'] = { FORMAT_STATE_PTR }, + ['%'] = { FORMAT_STATE_PERCENT_CHAR }, + + // Numerics + ['o'] = { FORMAT_STATE_NUM, 0, 0, 8 }, + ['x'] = { FORMAT_STATE_NUM, 0, SMALL, 16 }, + ['X'] = { FORMAT_STATE_NUM, 0, 0, 16 }, + ['d'] = { FORMAT_STATE_NUM, 0, SIGN, 10 }, + ['i'] = { FORMAT_STATE_NUM, 0, SIGN, 10 }, + ['u'] = { FORMAT_STATE_NUM, 0, 0, 10, }, - case 'd': - case 'i': - spec->flags |= SIGN; - break; - case 'u': - break; - - case 'n': /* * Since %n poses a greater security risk than * utility, treat it as any other invalid or * unsupported format specifier. */ - fallthrough; + }; - default: - WARN_ONCE(1, "Please remove unsupported %%%c in format string\n", *fmt); - spec->type = FORMAT_TYPE_INVALID; - return fmt - start; - } - - if (qualifier == 'L') - spec->type = FORMAT_TYPE_LONG_LONG; - else if (qualifier == 'l') { - BUILD_BUG_ON(FORMAT_TYPE_ULONG + SIGN != FORMAT_TYPE_LONG); - spec->type = FORMAT_TYPE_ULONG + (spec->flags & SIGN); - } else if (qualifier == 'z') { - spec->type = FORMAT_TYPE_SIZE_T; - } else if (qualifier == 't') { - spec->type = FORMAT_TYPE_PTRDIFF; - } else if (qualifier == 'H') { - BUILD_BUG_ON(FORMAT_TYPE_UBYTE + SIGN != FORMAT_TYPE_BYTE); - spec->type = FORMAT_TYPE_UBYTE + (spec->flags & SIGN); - } else if (qualifier == 'h') { - BUILD_BUG_ON(FORMAT_TYPE_USHORT + SIGN != FORMAT_TYPE_SHORT); - spec->type = FORMAT_TYPE_USHORT + (spec->flags & SIGN); - } else { - BUILD_BUG_ON(FORMAT_TYPE_UINT + SIGN != FORMAT_TYPE_INT); - spec->type = FORMAT_TYPE_UINT + (spec->flags & SIGN); + const struct format_state *p = lookup_state + (u8)*fmt.str; + if (p->size) { + fmt.size = p->size; + if (p->flags_or_double_size && fmt.str[0] == fmt.str[1]) { + fmt.size = p->flags_or_double_size; + fmt.str++; + } + fmt.str++; + p = lookup_state + *fmt.str; + } + if (p->state) { + if (p->base) + spec->base = p->base; + spec->flags |= p->flags_or_double_size; + fmt.state = p->state; + fmt.str++; + return fmt; } - return ++fmt - start; + WARN_ONCE(1, "Please remove unsupported %%%c in format string\n", *fmt.str); + fmt.state = FORMAT_STATE_INVALID; + return fmt; } static void @@ -2747,11 +2713,27 @@ set_precision(struct printf_spec *spec, int prec) } } +/* + * Turn a 1/2/4-byte value into a 64-bit one for printing: truncate + * as necessary and deal with signedness. + * + * 'size' is the size of the value in bytes. + */ +static unsigned long long convert_num_spec(unsigned int val, int size, struct printf_spec spec) +{ + unsigned int shift = 32 - size*8; + + val <<= shift; + if (!(spec.flags & SIGN)) + return val >> shift; + return (int)val >> shift; +} + /** * vsnprintf - Format a string and place it in a buffer * @buf: The buffer to place the result into * @size: The size of the buffer, including the trailing null space - * @fmt: The format string to use + * @fmt_str: The format string to use * @args: Arguments for the format string * * This function generally follows C99 vsnprintf, but has some @@ -2775,11 +2757,14 @@ set_precision(struct printf_spec *spec, int prec) * * If you're not already dealing with a va_list consider using snprintf(). */ -int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) +int vsnprintf(char *buf, size_t size, const char *fmt_str, va_list args) { - unsigned long long num; char *str, *end; struct printf_spec spec = {0}; + struct fmt fmt = { + .str = fmt_str, + .state = FORMAT_STATE_NONE, + }; /* Reject out-of-range values early. Large positive sizes are used for unknown buffer sizes. */ @@ -2795,33 +2780,43 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) size = end - buf; } - while (*fmt) { - const char *old_fmt = fmt; - int read = format_decode(fmt, &spec); + while (*fmt.str) { + const char *old_fmt = fmt.str; - fmt += read; + fmt = format_decode(fmt, &spec); - switch (spec.type) { - case FORMAT_TYPE_NONE: { - int copy = read; + switch (fmt.state) { + case FORMAT_STATE_NONE: { + int read = fmt.str - old_fmt; if (str < end) { + int copy = read; if (copy > end - str) copy = end - str; memcpy(str, old_fmt, copy); } str += read; - break; + continue; } - case FORMAT_TYPE_WIDTH: + case FORMAT_STATE_NUM: { + unsigned long long num; + if (fmt.size <= sizeof(int)) + num = convert_num_spec(va_arg(args, int), fmt.size, spec); + else + num = va_arg(args, long long); + str = number(str, end, num, spec); + continue; + } + + case FORMAT_STATE_WIDTH: set_field_width(&spec, va_arg(args, int)); - break; + continue; - case FORMAT_TYPE_PRECISION: + case FORMAT_STATE_PRECISION: set_precision(&spec, va_arg(args, int)); - break; + continue; - case FORMAT_TYPE_CHAR: { + case FORMAT_STATE_CHAR: { char c; if (!(spec.flags & LEFT)) { @@ -2841,27 +2836,27 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) *str = ' '; ++str; } - break; + continue; } - case FORMAT_TYPE_STR: + case FORMAT_STATE_STR: str = string(str, end, va_arg(args, char *), spec); - break; + continue; - case FORMAT_TYPE_PTR: - str = pointer(fmt, str, end, va_arg(args, void *), + case FORMAT_STATE_PTR: + str = pointer(fmt.str, str, end, va_arg(args, void *), spec); - while (isalnum(*fmt)) - fmt++; - break; + while (isalnum(*fmt.str)) + fmt.str++; + continue; - case FORMAT_TYPE_PERCENT_CHAR: + case FORMAT_STATE_PERCENT_CHAR: if (str < end) *str = '%'; ++str; - break; + continue; - case FORMAT_TYPE_INVALID: + default: /* * Presumably the arguments passed gcc's type * checking, but there is no safe or sane way @@ -2871,47 +2866,6 @@ int vsnprintf(char *buf, size_t size, const char *fmt, va_list args) * sync. */ goto out; - - default: - switch (spec.type) { - case FORMAT_TYPE_LONG_LONG: - num = va_arg(args, long long); - break; - case FORMAT_TYPE_ULONG: - num = va_arg(args, unsigned long); - break; - case FORMAT_TYPE_LONG: - num = va_arg(args, long); - break; - case FORMAT_TYPE_SIZE_T: - if (spec.flags & SIGN) - num = va_arg(args, ssize_t); - else - num = va_arg(args, size_t); - break; - case FORMAT_TYPE_PTRDIFF: - num = va_arg(args, ptrdiff_t); - break; - case FORMAT_TYPE_UBYTE: - num = (unsigned char) va_arg(args, int); - break; - case FORMAT_TYPE_BYTE: - num = (signed char) va_arg(args, int); - break; - case FORMAT_TYPE_USHORT: - num = (unsigned short) va_arg(args, int); - break; - case FORMAT_TYPE_SHORT: - num = (short) va_arg(args, int); - break; - case FORMAT_TYPE_INT: - num = (int) va_arg(args, int); - break; - default: - num = va_arg(args, unsigned int); - } - - str = number(str, end, num, spec); } } @@ -3067,7 +3021,7 @@ EXPORT_SYMBOL(sprintf); * vbin_printf - Parse a format string and place args' binary value in a buffer * @bin_buf: The buffer to place args' binary value * @size: The size of the buffer(by words(32bits), not characters) - * @fmt: The format string to use + * @fmt_str: The format string to use * @args: Arguments for the format string * * The format follows C99 vsnprintf, except %n is ignored, and its argument @@ -3080,8 +3034,12 @@ EXPORT_SYMBOL(sprintf); * If the return value is greater than @size, the resulting bin_buf is NOT * valid for bstr_printf(). */ -int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args) +int vbin_printf(u32 *bin_buf, size_t size, const char *fmt_str, va_list args) { + struct fmt fmt = { + .str = fmt_str, + .state = FORMAT_STATE_NONE, + }; struct printf_spec spec = {0}; char *str, *end; int width; @@ -3113,31 +3071,29 @@ int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args) value; \ }) - while (*fmt) { - int read = format_decode(fmt, &spec); + while (*fmt.str) { + fmt = format_decode(fmt, &spec); - fmt += read; - - switch (spec.type) { - case FORMAT_TYPE_NONE: - case FORMAT_TYPE_PERCENT_CHAR: + switch (fmt.state) { + case FORMAT_STATE_NONE: + case FORMAT_STATE_PERCENT_CHAR: break; - case FORMAT_TYPE_INVALID: + case FORMAT_STATE_INVALID: goto out; - case FORMAT_TYPE_WIDTH: - case FORMAT_TYPE_PRECISION: + case FORMAT_STATE_WIDTH: + case FORMAT_STATE_PRECISION: width = (int)save_arg(int); /* Pointers may require the width */ - if (*fmt == 'p') + if (*fmt.str == 'p') set_field_width(&spec, width); break; - case FORMAT_TYPE_CHAR: + case FORMAT_STATE_CHAR: save_arg(char); break; - case FORMAT_TYPE_STR: { + case FORMAT_STATE_STR: { const char *save_str = va_arg(args, char *); const char *err_msg; size_t len; @@ -3153,9 +3109,9 @@ int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args) break; } - case FORMAT_TYPE_PTR: + case FORMAT_STATE_PTR: /* Dereferenced pointers must be done now */ - switch (*fmt) { + switch (*fmt.str) { /* Dereference of functions is still OK */ case 'S': case 's': @@ -3165,11 +3121,11 @@ int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args) save_arg(void *); break; default: - if (!isalnum(*fmt)) { + if (!isalnum(*fmt.str)) { save_arg(void *); break; } - str = pointer(fmt, str, end, va_arg(args, void *), + str = pointer(fmt.str, str, end, va_arg(args, void *), spec); if (str + 1 < end) *str++ = '\0'; @@ -3177,35 +3133,14 @@ int vbin_printf(u32 *bin_buf, size_t size, const char *fmt, va_list args) end[-1] = '\0'; /* Must be nul terminated */ } /* skip all alphanumeric pointer suffixes */ - while (isalnum(*fmt)) - fmt++; + while (isalnum(*fmt.str)) + fmt.str++; break; - default: - switch (spec.type) { - - case FORMAT_TYPE_LONG_LONG: + case FORMAT_STATE_NUM: + if (fmt.size > sizeof(int)) { save_arg(long long); - break; - case FORMAT_TYPE_ULONG: - case FORMAT_TYPE_LONG: - save_arg(unsigned long); - break; - case FORMAT_TYPE_SIZE_T: - save_arg(size_t); - break; - case FORMAT_TYPE_PTRDIFF: - save_arg(ptrdiff_t); - break; - case FORMAT_TYPE_UBYTE: - case FORMAT_TYPE_BYTE: - save_arg(char); - break; - case FORMAT_TYPE_USHORT: - case FORMAT_TYPE_SHORT: - save_arg(short); - break; - default: + } else { save_arg(int); } } @@ -3221,7 +3156,7 @@ EXPORT_SYMBOL_GPL(vbin_printf); * bstr_printf - Format a string from binary arguments and place it in a buffer * @buf: The buffer to place the result into * @size: The size of the buffer, including the trailing null space - * @fmt: The format string to use + * @fmt_str: The format string to use * @bin_buf: Binary arguments for the format string * * This function like C99 vsnprintf, but the difference is that vsnprintf gets @@ -3239,8 +3174,12 @@ EXPORT_SYMBOL_GPL(vbin_printf); * return is greater than or equal to @size, the resulting * string is truncated. */ -int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf) +int bstr_printf(char *buf, size_t size, const char *fmt_str, const u32 *bin_buf) { + struct fmt fmt = { + .str = fmt_str, + .state = FORMAT_STATE_NONE, + }; struct printf_spec spec = {0}; char *str, *end; const char *args = (const char *)bin_buf; @@ -3272,33 +3211,33 @@ int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf) size = end - buf; } - while (*fmt) { - const char *old_fmt = fmt; - int read = format_decode(fmt, &spec); - - fmt += read; + while (*fmt.str) { + const char *old_fmt = fmt.str; + unsigned long long num; - switch (spec.type) { - case FORMAT_TYPE_NONE: { - int copy = read; + fmt = format_decode(fmt, &spec); + switch (fmt.state) { + case FORMAT_STATE_NONE: { + int read = fmt.str - old_fmt; if (str < end) { + int copy = read; if (copy > end - str) copy = end - str; memcpy(str, old_fmt, copy); } str += read; - break; + continue; } - case FORMAT_TYPE_WIDTH: + case FORMAT_STATE_WIDTH: set_field_width(&spec, get_arg(int)); - break; + continue; - case FORMAT_TYPE_PRECISION: + case FORMAT_STATE_PRECISION: set_precision(&spec, get_arg(int)); - break; + continue; - case FORMAT_TYPE_CHAR: { + case FORMAT_STATE_CHAR: { char c; if (!(spec.flags & LEFT)) { @@ -3317,21 +3256,21 @@ int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf) *str = ' '; ++str; } - break; + continue; } - case FORMAT_TYPE_STR: { + case FORMAT_STATE_STR: { const char *str_arg = args; args += strlen(str_arg) + 1; str = string(str, end, (char *)str_arg, spec); - break; + continue; } - case FORMAT_TYPE_PTR: { + case FORMAT_STATE_PTR: { bool process = false; int copy, len; /* Non function dereferences were already done */ - switch (*fmt) { + switch (*fmt.str) { case 'S': case 's': case 'x': @@ -3340,7 +3279,7 @@ int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf) process = true; break; default: - if (!isalnum(*fmt)) { + if (!isalnum(*fmt.str)) { process = true; break; } @@ -3355,63 +3294,32 @@ int bstr_printf(char *buf, size_t size, const char *fmt, const u32 *bin_buf) } } if (process) - str = pointer(fmt, str, end, get_arg(void *), spec); + str = pointer(fmt.str, str, end, get_arg(void *), spec); - while (isalnum(*fmt)) - fmt++; - break; + while (isalnum(*fmt.str)) + fmt.str++; + continue; } - case FORMAT_TYPE_PERCENT_CHAR: + case FORMAT_STATE_PERCENT_CHAR: if (str < end) *str = '%'; ++str; - break; + continue; - case FORMAT_TYPE_INVALID: + case FORMAT_STATE_INVALID: goto out; - default: { - unsigned long long num; - - switch (spec.type) { - - case FORMAT_TYPE_LONG_LONG: + case FORMAT_STATE_NUM: + if (fmt.size > sizeof(int)) { num = get_arg(long long); - break; - case FORMAT_TYPE_ULONG: - case FORMAT_TYPE_LONG: - num = get_arg(unsigned long); - break; - case FORMAT_TYPE_SIZE_T: - num = get_arg(size_t); - break; - case FORMAT_TYPE_PTRDIFF: - num = get_arg(ptrdiff_t); - break; - case FORMAT_TYPE_UBYTE: - num = get_arg(unsigned char); - break; - case FORMAT_TYPE_BYTE: - num = get_arg(signed char); - break; - case FORMAT_TYPE_USHORT: - num = get_arg(unsigned short); - break; - case FORMAT_TYPE_SHORT: - num = get_arg(short); - break; - case FORMAT_TYPE_UINT: - num = get_arg(unsigned int); - break; - default: - num = get_arg(int); + } else { + num = convert_num_spec(get_arg(int), fmt.size, spec); } - str = number(str, end, num, spec); - } /* default: */ - } /* switch(spec.type) */ - } /* while(*fmt) */ + continue; + } + } /* while(*fmt.str) */ out: if (size > 0) { diff --git a/lib/win_minmax.c b/lib/win_minmax.c index ec10506834b6..1682e614309c 100644 --- a/lib/win_minmax.c +++ b/lib/win_minmax.c @@ -97,3 +97,4 @@ u32 minmax_running_min(struct minmax *m, u32 win, u32 t, u32 meas) return minmax_subwin_update(m, win, &val); } +EXPORT_SYMBOL(minmax_running_min); diff --git a/lib/xarray.c b/lib/xarray.c index 32d4bac8c94c..116e9286c64e 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -125,19 +125,20 @@ static inline void node_mark_all(struct xa_node *node, xa_mark_t mark) */ static void xas_squash_marks(const struct xa_state *xas) { - unsigned int mark = 0; + xa_mark_t mark = 0; unsigned int limit = xas->xa_offset + xas->xa_sibs + 1; - if (!xas->xa_sibs) - return; + for (;;) { + unsigned long *marks = node_marks(xas->xa_node, mark); - do { - unsigned long *marks = xas->xa_node->marks[mark]; - if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit) - continue; - __set_bit(xas->xa_offset, marks); - bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs); - } while (mark++ != (__force unsigned)XA_MARK_MAX); + if (find_next_bit(marks, limit, xas->xa_offset + 1) != limit) { + __set_bit(xas->xa_offset, marks); + bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs); + } + if (mark == XA_MARK_MAX) + break; + mark_inc(mark); + } } /* extracts the offset within this node from the index */ @@ -435,6 +436,11 @@ static unsigned long max_index(void *entry) return (XA_CHUNK_SIZE << xa_to_node(entry)->shift) - 1; } +static inline void *xa_zero_to_null(void *entry) +{ + return xa_is_zero(entry) ? NULL : entry; +} + static void xas_shrink(struct xa_state *xas) { struct xarray *xa = xas->xa; @@ -451,8 +457,8 @@ static void xas_shrink(struct xa_state *xas) break; if (!xa_is_node(entry) && node->shift) break; - if (xa_is_zero(entry) && xa_zero_busy(xa)) - entry = NULL; + if (xa_zero_busy(xa)) + entry = xa_zero_to_null(entry); xas->xa_node = XAS_BOUNDS; RCU_INIT_POINTER(xa->xa_head, entry); @@ -1022,7 +1028,7 @@ void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order, unsigned int mask = xas->xa_sibs; /* XXX: no support for splitting really large entries yet */ - if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT < order)) + if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT <= order)) goto nomem; if (xas->xa_shift + XA_CHUNK_SHIFT > order) return; @@ -1147,6 +1153,7 @@ void xas_pause(struct xa_state *xas) if (!xa_is_sibling(xa_entry(xas->xa, node, offset))) break; } + xas->xa_index &= ~0UL << node->shift; xas->xa_index += (offset - xas->xa_offset) << node->shift; if (xas->xa_index == 0) xas->xa_node = XAS_BOUNDS; @@ -1382,6 +1389,8 @@ void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark) entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK)) continue; + if (xa_is_sibling(entry)) + continue; if (!xa_is_node(entry)) return entry; xas->xa_node = xa_to_node(entry); @@ -1474,9 +1483,7 @@ void *xa_load(struct xarray *xa, unsigned long index) rcu_read_lock(); do { - entry = xas_load(&xas); - if (xa_is_zero(entry)) - entry = NULL; + entry = xa_zero_to_null(xas_load(&xas)); } while (xas_retry(&xas, entry)); rcu_read_unlock(); @@ -1486,8 +1493,6 @@ EXPORT_SYMBOL(xa_load); static void *xas_result(struct xa_state *xas, void *curr) { - if (xa_is_zero(curr)) - return NULL; if (xas_error(xas)) curr = xas->xa_node; return curr; @@ -1508,7 +1513,7 @@ static void *xas_result(struct xa_state *xas, void *curr) void *__xa_erase(struct xarray *xa, unsigned long index) { XA_STATE(xas, xa, index); - return xas_result(&xas, xas_store(&xas, NULL)); + return xas_result(&xas, xa_zero_to_null(xas_store(&xas, NULL))); } EXPORT_SYMBOL(__xa_erase); @@ -1567,7 +1572,7 @@ void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) xas_clear_mark(&xas, XA_FREE_MARK); } while (__xas_nomem(&xas, gfp)); - return xas_result(&xas, curr); + return xas_result(&xas, xa_zero_to_null(curr)); } EXPORT_SYMBOL(__xa_store); @@ -1600,6 +1605,9 @@ void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) } EXPORT_SYMBOL(xa_store); +static inline void *__xa_cmpxchg_raw(struct xarray *xa, unsigned long index, + void *old, void *entry, gfp_t gfp); + /** * __xa_cmpxchg() - Store this entry in the XArray. * @xa: XArray. @@ -1619,6 +1627,13 @@ EXPORT_SYMBOL(xa_store); void *__xa_cmpxchg(struct xarray *xa, unsigned long index, void *old, void *entry, gfp_t gfp) { + return xa_zero_to_null(__xa_cmpxchg_raw(xa, index, old, entry, gfp)); +} +EXPORT_SYMBOL(__xa_cmpxchg); + +static inline void *__xa_cmpxchg_raw(struct xarray *xa, unsigned long index, + void *old, void *entry, gfp_t gfp) +{ XA_STATE(xas, xa, index); void *curr; @@ -1636,7 +1651,6 @@ void *__xa_cmpxchg(struct xarray *xa, unsigned long index, return xas_result(&xas, curr); } -EXPORT_SYMBOL(__xa_cmpxchg); /** * __xa_insert() - Store this entry in the XArray if no entry is present. @@ -1656,26 +1670,16 @@ EXPORT_SYMBOL(__xa_cmpxchg); */ int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) { - XA_STATE(xas, xa, index); void *curr; + int errno; - if (WARN_ON_ONCE(xa_is_advanced(entry))) - return -EINVAL; if (!entry) entry = XA_ZERO_ENTRY; - - do { - curr = xas_load(&xas); - if (!curr) { - xas_store(&xas, entry); - if (xa_track_free(xa)) - xas_clear_mark(&xas, XA_FREE_MARK); - } else { - xas_set_err(&xas, -EBUSY); - } - } while (__xas_nomem(&xas, gfp)); - - return xas_error(&xas); + curr = __xa_cmpxchg_raw(xa, index, NULL, entry, gfp); + errno = xa_err(curr); + if (errno) + return errno; + return (curr != NULL) ? -EBUSY : 0; } EXPORT_SYMBOL(__xa_insert); diff --git a/lib/zstd/common/portability_macros.h b/lib/zstd/common/portability_macros.h index 0e3b2c0a527d..0dde8bf56595 100644 --- a/lib/zstd/common/portability_macros.h +++ b/lib/zstd/common/portability_macros.h @@ -55,7 +55,7 @@ #ifndef DYNAMIC_BMI2 #if ((defined(__clang__) && __has_attribute(__target__)) \ || (defined(__GNUC__) \ - && (__GNUC__ >= 5 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)))) \ + && (__GNUC__ >= 11))) \ && (defined(__x86_64__) || defined(_M_X64)) \ && !defined(__BMI2__) # define DYNAMIC_BMI2 1 |