From 468a9428521e7d00fb21250af363eb94dc1d6861 Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Thu, 26 May 2016 22:11:51 -0400 Subject: : Add support for architecture-specific functions This is just the infrastructure; there are no users yet. This is modelled on CONFIG_ARCH_RANDOM; a CONFIG_ symbol declares the existence of . That file may define its own versions of various functions, and define HAVE_* symbols (no CONFIG_ prefix!) to suppress the generic ones. Included is a self-test (in lib/test_hash.c) that verifies the basics. It is NOT in general required that the arch-specific functions compute the same thing as the generic, but if a HAVE_* symbol is defined with the value 1, then equality is tested. Signed-off-by: George Spelvin Cc: Geert Uytterhoeven Cc: Greg Ungerer Cc: Andreas Schwab Cc: Philippe De Muyter Cc: linux-m68k@lists.linux-m68k.org Cc: Alistair Francis Cc: Michal Simek Cc: Yoshinori Sato Cc: uclinux-h8-devel@lists.sourceforge.jp --- arch/Kconfig | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'arch') diff --git a/arch/Kconfig b/arch/Kconfig index 81869a5e7e17..96406e4db995 100644 --- a/arch/Kconfig +++ b/arch/Kconfig @@ -589,6 +589,14 @@ config HAVE_STACK_VALIDATION Architecture supports the 'objtool check' host tool command, which performs compile-time stack metadata validation. +config HAVE_ARCH_HASH + bool + default n + help + If this is set, the architecture provides an + file which provides platform-specific implementations of some + functions in or fs/namei.c. + # # ABI hall of shame # -- cgit From 14c44b95b3dcb8ff1d627e6b78f57c4373d375cb Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Thu, 26 May 2016 11:36:19 -0400 Subject: m68k: Add This provides a multiply by constant GOLDEN_RATIO_32 = 0x61C88647 for the original mc68000, which lacks a 32x32-bit multiply instruction. Yes, the amount of optimization effort put in is excessive. :-) Shift-add chain found by Yevgen Voronenko's Hcub algorithm at http://spiral.ece.cmu.edu/mcm/gen.html Signed-off-by: George Spelvin Cc: Geert Uytterhoeven Cc: Greg Ungerer Cc: Andreas Schwab Cc: Philippe De Muyter Cc: linux-m68k@lists.linux-m68k.org --- arch/m68k/Kconfig.cpu | 1 + arch/m68k/include/asm/hash.h | 59 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 60 insertions(+) create mode 100644 arch/m68k/include/asm/hash.h (limited to 'arch') diff --git a/arch/m68k/Kconfig.cpu b/arch/m68k/Kconfig.cpu index 0dfcf1281e9c..bf3de464cf3c 100644 --- a/arch/m68k/Kconfig.cpu +++ b/arch/m68k/Kconfig.cpu @@ -40,6 +40,7 @@ config M68000 select CPU_HAS_NO_MULDIV64 select CPU_HAS_NO_UNALIGNED select GENERIC_CSUM + select HAVE_ARCH_HASH help The Freescale (was Motorola) 68000 CPU is the first generation of the well known M68K family of processors. The CPU core as well as diff --git a/arch/m68k/include/asm/hash.h b/arch/m68k/include/asm/hash.h new file mode 100644 index 000000000000..6407af84a994 --- /dev/null +++ b/arch/m68k/include/asm/hash.h @@ -0,0 +1,59 @@ +#ifndef _ASM_HASH_H +#define _ASM_HASH_H + +/* + * If CONFIG_M68000=y (original mc68000/010), this file is #included + * to work around the lack of a MULU.L instruction. + */ + +#define HAVE_ARCH__HASH_32 1 +/* + * While it would be legal to substitute a different hash operation + * entirely, let's keep it simple and just use an optimized multiply + * by GOLDEN_RATIO_32 = 0x61C88647. + * + * The best way to do that appears to be to multiply by 0x8647 with + * shifts and adds, and use mulu.w to multiply the high half by 0x61C8. + * + * Because the 68000 has multi-cycle shifts, this addition chain is + * chosen to minimise the shift distances. + * + * Despite every attempt to spoon-feed it simple operations, GCC + * 6.1.1 doggedly insists on doing annoying things like converting + * "lsl.l #2," (12 cycles) to two adds (8+8 cycles). + * + * It also likes to notice two shifts in a row, like "a = x << 2" and + * "a <<= 7", and convert that to "a = x << 9". But shifts longer + * than 8 bits are extra-slow on m68k, so that's a lose. + * + * Since the 68000 is a very simple in-order processor with no + * instruction scheduling effects on execution time, we can safely + * take it out of GCC's hands and write one big asm() block. + * + * Without calling overhead, this operation is 30 bytes (14 instructions + * plus one immediate constant) and 166 cycles. + * + * (Because %2 is fetched twice, it can't be postincrement, and thus it + * can't be a fully general "g" or "m". Register is preferred, but + * offsettable memory or immediate will work.) + */ +static inline u32 __attribute_const__ __hash_32(u32 x) +{ + u32 a, b; + + asm( "move.l %2,%0" /* a = x * 0x0001 */ + "\n lsl.l #2,%0" /* a = x * 0x0004 */ + "\n move.l %0,%1" + "\n lsl.l #7,%0" /* a = x * 0x0200 */ + "\n add.l %2,%0" /* a = x * 0x0201 */ + "\n add.l %0,%1" /* b = x * 0x0205 */ + "\n add.l %0,%0" /* a = x * 0x0402 */ + "\n add.l %0,%1" /* b = x * 0x0607 */ + "\n lsl.l #5,%0" /* a = x * 0x8040 */ + : "=&d,d" (a), "=&r,r" (b) + : "r,roi?" (x)); /* a+b = x*0x8647 */ + + return ((u16)(x*0x61c8) << 16) + a + b; +} + +#endif /* _ASM_HASH_H */ -- cgit From 7b13277b682972c2ff8f6419e86c333d81936023 Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Wed, 25 May 2016 11:06:09 -0400 Subject: microblaze: Add Microblaze is an FPGA soft core that can be configured various ways. If it is configured without a multiplier, the standard __hash_32() will require a call to __mulsi3, which is a slow software loop. Instead, use a shift-and-add sequence for the constant multiply. GCC knows how to do this, but it's not as clever as some. Signed-off-by: George Spelvin Cc: Alistair Francis Cc: Michal Simek --- arch/microblaze/Kconfig | 1 + arch/microblaze/include/asm/hash.h | 81 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 82 insertions(+) create mode 100644 arch/microblaze/include/asm/hash.h (limited to 'arch') diff --git a/arch/microblaze/Kconfig b/arch/microblaze/Kconfig index 3d793b55f60c..ce3e512517ce 100644 --- a/arch/microblaze/Kconfig +++ b/arch/microblaze/Kconfig @@ -16,6 +16,7 @@ config MICROBLAZE select GENERIC_IRQ_SHOW select GENERIC_PCI_IOMAP select GENERIC_SCHED_CLOCK + select HAVE_ARCH_HASH select HAVE_ARCH_KGDB select HAVE_DEBUG_KMEMLEAK select HAVE_DMA_API_DEBUG diff --git a/arch/microblaze/include/asm/hash.h b/arch/microblaze/include/asm/hash.h new file mode 100644 index 000000000000..753513ae8cb0 --- /dev/null +++ b/arch/microblaze/include/asm/hash.h @@ -0,0 +1,81 @@ +#ifndef _ASM_HASH_H +#define _ASM_HASH_H + +/* + * Fortunately, most people who want to run Linux on Microblaze enable + * both multiplier and barrel shifter, but omitting them is technically + * a supported configuration. + * + * With just a barrel shifter, we can implement an efficient constant + * multiply using shifts and adds. GCC can find a 9-step solution, but + * this 6-step solution was found by Yevgen Voronenko's implementation + * of the Hcub algorithm at http://spiral.ece.cmu.edu/mcm/gen.html. + * + * That software is really not designed for a single multiplier this large, + * but if you run it enough times with different seeds, it'll find several + * 6-shift, 6-add sequences for computing x * 0x61C88647. They are all + * c = (x << 19) + x; + * a = (x << 9) + c; + * b = (x << 23) + a; + * return (a<<11) + (b<<6) + (c<<3) - b; + * with variations on the order of the final add. + * + * Without even a shifter, it's hopless; any hash function will suck. + */ + +#if CONFIG_XILINX_MICROBLAZE0_USE_HW_MUL == 0 + +#define HAVE_ARCH__HASH_32 1 + +/* Multiply by GOLDEN_RATIO_32 = 0x61C88647 */ +static inline u32 __attribute_const__ __hash_32(u32 a) +{ +#if CONFIG_XILINX_MICROBLAZE0_USE_BARREL + unsigned int b, c; + + /* Phase 1: Compute three intermediate values */ + b = a << 23; + c = (a << 19) + a; + a = (a << 9) + c; + b += a; + + /* Phase 2: Compute (a << 11) + (b << 6) + (c << 3) - b */ + a <<= 5; + a += b; /* (a << 5) + b */ + a <<= 3; + a += c; /* (a << 8) + (b << 3) + c */ + a <<= 3; + return a - b; /* (a << 11) + (b << 6) + (c << 3) - b */ +#else + /* + * "This is really going to hurt." + * + * Without a barrel shifter, left shifts are implemented as + * repeated additions, and the best we can do is an optimal + * addition-subtraction chain. This one is not known to be + * optimal, but at 37 steps, it's decent for a 31-bit multiplier. + * + * Question: given its size (37*4 = 148 bytes per instance), + * and slowness, is this worth having inline? + */ + unsigned int b, c, d; + + b = a << 4; /* 4 */ + c = b << 1; /* 1 5 */ + b += a; /* 1 6 */ + c += b; /* 1 7 */ + c <<= 3; /* 3 10 */ + c -= a; /* 1 11 */ + d = c << 7; /* 7 18 */ + d += b; /* 1 19 */ + d <<= 8; /* 8 27 */ + d += a; /* 1 28 */ + d <<= 1; /* 1 29 */ + d += b; /* 1 30 */ + d <<= 6; /* 6 36 */ + return d + c; /* 1 37 total instructions*/ +#endif +} + +#endif /* !CONFIG_XILINX_MICROBLAZE0_USE_HW_MUL */ +#endif /* _ASM_HASH_H */ -- cgit From 4684fe95300c071983f77653e354c040fe80a265 Mon Sep 17 00:00:00 2001 From: George Spelvin Date: Wed, 25 May 2016 14:19:49 -0400 Subject: h8300: Add This will improve the performance of hash_32() and hash_64(), but due to complete lack of multi-bit shift instructions on H8, performance will still be bad in surrounding code. Designing H8-specific hash algorithms to work around that is a separate project. (But if the maintainers would like to get in touch...) Signed-off-by: George Spelvin Cc: Yoshinori Sato Cc: uclinux-h8-devel@lists.sourceforge.jp --- arch/h8300/Kconfig | 1 + arch/h8300/include/asm/hash.h | 53 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+) create mode 100644 arch/h8300/include/asm/hash.h (limited to 'arch') diff --git a/arch/h8300/Kconfig b/arch/h8300/Kconfig index 986ea84caaed..6c583dbbc119 100644 --- a/arch/h8300/Kconfig +++ b/arch/h8300/Kconfig @@ -20,6 +20,7 @@ config H8300 select HAVE_KERNEL_GZIP select HAVE_KERNEL_LZO select HAVE_ARCH_KGDB + select HAVE_ARCH_HASH config RWSEM_GENERIC_SPINLOCK def_bool y diff --git a/arch/h8300/include/asm/hash.h b/arch/h8300/include/asm/hash.h new file mode 100644 index 000000000000..04cfbd2bd850 --- /dev/null +++ b/arch/h8300/include/asm/hash.h @@ -0,0 +1,53 @@ +#ifndef _ASM_HASH_H +#define _ASM_HASH_H + +/* + * The later H8SX models have a 32x32-bit multiply, but the H8/300H + * and H8S have only 16x16->32. Since it's tolerably compact, this is + * basically an inlined version of the __mulsi3 code. Since the inputs + * are not expected to be small, it's also simplfied by skipping the + * early-out checks. + * + * (Since neither CPU has any multi-bit shift instructions, a + * shift-and-add version is a non-starter.) + * + * TODO: come up with an arch-specific version of the hashing in fs/namei.c, + * since that is heavily dependent on rotates. Which, as mentioned, suck + * horribly on H8. + */ + +#if defined(CONFIG_CPU_H300H) || defined(CONFIG_CPU_H8S) + +#define HAVE_ARCH__HASH_32 1 + +/* + * Multiply by k = 0x61C88647. Fitting this into three registers requires + * one extra instruction, but reducing register pressure will probably + * make that back and then some. + * + * GCC asm note: %e1 is the high half of operand %1, while %f1 is the + * low half. So if %1 is er4, then %e1 is e4 and %f1 is r4. + * + * This has been designed to modify x in place, since that's the most + * common usage, but preserve k, since hash_64() makes two calls in + * quick succession. + */ +static inline u32 __attribute_const__ __hash_32(u32 x) +{ + u32 temp; + + asm( "mov.w %e1,%f0" + "\n mulxu.w %f2,%0" /* klow * xhigh */ + "\n mov.w %f0,%e1" /* The extra instruction */ + "\n mov.w %f1,%f0" + "\n mulxu.w %e2,%0" /* khigh * xlow */ + "\n add.w %e1,%f0" + "\n mulxu.w %f2,%1" /* klow * xlow */ + "\n add.w %f0,%e1" + : "=&r" (temp), "=r" (x) + : "%r" (GOLDEN_RATIO_32), "1" (x)); + return x; +} + +#endif +#endif /* _ASM_HASH_H */ -- cgit