[PATCH 00/10] String hash improvements

[PATCH 00/10] String hash improvements

[George Spelvin]

On Tue, 17 May 2016 at 09:32, Linus Torvalds <torvalds@linux-foundation.org> wrote:
> On Tue, May 17, 2016 at 6:41 AM, George Spelvin <linux@horizon.com> wrote:
>> I had assumed that since they weren't fully baked when the window opened,
>> they weren't eligible, but I'll try.

> Hey, if they aren't ready, they aren't.

Well, they're close, and I can and did *get* them ready.

> How about just the minimal set of patches that you'er happy with as-is?

The things are a bit interdependent.  I can't fix hash_64() on 32-bit systems until
I get rid of hash_string()'s need for it to return 64 bits, which requires work
on the dcache hashes to make them suitable replacements...

The real fun has come from TPTB deciding to sell the horizon.com domain,
and it turns out that updating rDNS takes the ISP a whole freaking week,
during which time outgoing mail trips everyone's spam filters.

That finally got fixed, just in time for me to put my dominant hand through
a piece of glass.  It's been a week. :-(


Anyway, the patches...

This series does several related things:
1) Gets rid of the string hashes in <linux/sunrpc/svcauth.h>,
   and uses the dcache hash (fs/namei.c) instead.
2) Avoid 64-bit multiplies in hash_64() on 32-bit platforms.
   Two 32-bit multiplies will do well enough.
3) Rids the world of the bad hash multipliers in hash_32.
   This finishes the job started in 689de1d6ca.
   The vast majority of Linux architectures have hardware support
   for 32x32-bit multiply and so derive no benefit from "simplified"
   multipliers.
   The few processors that do not (68000, h8/300 and some models of
   Microblaze) have arch-specific implementations added.  Those patches
   are last in the series so they can go through the relevant arch
   maintainers.
4) Overhauls the dcache hash mixing.
   The patch in 2bf0b16954 was an off-the-cuff suggestion.  Replaced with
   a much more careful design that's simultaneously faster and better.
   (My own invention, as there was noting suitable in the literature I
   could find.  Comments welcome!)

Things I thought about but can wait for now:
5) Modify the hash_name() loop to skip the initial HASH_MIX().
   That would let us salt the hash if we ever wanted to.
6) Modify bytemask_from_count to handle inputs of 1..sizeof(long)
   rather than 0..sizeof(long)-1.  This would simplify all its users
   including full_name_hash.
7) Sort out partial_name_hash().
   The hash function is declared as using a long state, even though
   it's truncated to 32 bits at the end and the extra internal state
   contributes nothing to the result.  And some callers do odd things:
   * fs/hfs/string.c only allocates 32 bits of state
   * fs/hfsplus/unicode.c uses it to hash 16-bit unicode symbols not bytes

I'm not particularly fond of the names of the header files I created,
but if anyone has a better idea please talk fast!

George Spelvin (10):
  Pull out string hash to <linux/stringhash.h>
  fs/namei.c: Add hash_string() function.
  <linux/sunrpc/svcauth.h>: Define hash_str() in terms of hash_string()
  Change hash_64() return value to 32 bits.
  Eliminate bad hash multipliers from hash_32() and hash_64().
  fs/namei.c: Improve dcache hash function
  <linux/hash.h>: Add support for architecture-specific functions
  m68k: Add <asm/archhash.h>
  microblaze: Add <asm/archhash.h>
  h8300: Add <asm/archhash.h>

 arch/Kconfig                           |   8 ++
 arch/h8300/Kconfig                     |   1 +
 arch/h8300/include/asm/archhash.h      |  52 ++++++++++++
 arch/m68k/Kconfig                      |   1 +
 arch/m68k/include/asm/archhash.h       |  67 +++++++++++++++
 arch/microblaze/Kconfig                |   1 +
 arch/microblaze/include/asm/archhash.h |  80 ++++++++++++++++++
 fs/namei.c                             | 149 +++++++++++++++++++++++++--------
 include/linux/dcache.h                 |  27 +-----
 include/linux/hash.h                   | 111 ++++++++++++------------
 include/linux/stringhash.h             |  76 +++++++++++++++++
 include/linux/sunrpc/svcauth.h         |  36 ++------
 12 files changed, 464 insertions(+), 145 deletions(-)
 create mode 100644 arch/h8300/include/asm/archhash.h
 create mode 100644 arch/m68k/include/asm/archhash.h
 create mode 100644 arch/microblaze/include/asm/archhash.h
 create mode 100644 include/linux/stringhash.h

-- 
2.8.1

Re: [PATCH 00/10] String hash improvements

[Geert Uytterhoeven]

Hi George,

On Wed, May 25, 2016 at 9:20 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
> I'm not particularly fond of the names of the header files I created,
> but if anyone has a better idea please talk fast!

Usually this is handled through include/asm-generic/.
Put the generic default implementation in include/asm-generic/hash.h.

Architectures that need to override provide their own version, e.g.
arch/m68k/include/asm/hash.h. They may #include <asm-generic/hash.h>
if they still want to reuse parts of the generic implementation.

Other architectures add "generic-y += hash.h" to their
arch/<ARCH>/include/asm/Kbuild.

<linux/hash.h> includes <asm/hash.h> t.

>  arch/h8300/include/asm/archhash.h      |  52 ++++++++++++
>  arch/m68k/include/asm/archhash.h       |  67 +++++++++++++++
>  arch/microblaze/include/asm/archhash.h |  80 ++++++++++++++++++
>  include/linux/hash.h                   | 111 ++++++++++++------------
>  include/linux/stringhash.h             |  76 +++++++++++++++++

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [PATCH 00/10] String hash improvements

[Linus Torvalds]

On Wed, May 25, 2016 at 12:20 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
>
> Well, they're close, and I can and did *get* them ready.

Ok, thanks. For some odd reason all your emails in this series got
marked as spam. Every single one, including the cover letter (but not
your replies to the replies to this).

Stupidly, I unmarked them before thinking to ask google *why* they got
marked as spam.

Did you do something different to send this series than you usually do?

Would you mind sending it again (maybe you have changes due to some o
the comments, but even if not, I'd like to see what the spam filter
says)? You could do it just to me to avoid filling up the mailing list
with duplicates.

                    Linus

[PATCH v2 00/10] String hash improvements

[George Spelvin]

This is just the arch-specific part, updated as per requests.

* Fix the stupidly overcomplex m68k conditionals (per Geert Uytterhoeven)
* Renamed the arch file to <asm/hash.h> (per Geert Uytterhoeven)
* Improved the comments on the progress of shift-and-add (Philippe De Muyter)
* Added a self-test (per Michal Simek)

Things I did *not* do, because I thought the concerns were withdrawn
after discussion:  (If I misintrepreted silence, please correct me!)

* Use unconditional inclusion with an <asm-generic/hash.h> fallback.
* Change the multi-line asm() formatting (Philippe De Muyter)
* Move reference about algorithm credit (Philippe De Muyter)

The big change is the addition of a self-test in lib/test_hash.c.
That had to be written and the various tests validated by introducing
deliberate bugs into <arch/hash.h>.

Handling the fact that architectures are allowed to change the computed
function (even though none of the ones written so far have used that
freedom) added some complexity.  I ended up using the value of the
HAVE_ARCH_* macro.  If it's 1, that means it's expected to be a clone
of the generic versions, and it's compared against them.  If it's 0,
it's its own magic thing.

The big question is, should these go through the arch trees, or may I
just include them in the series to Linus?  The latter is simpler for me,
but obviously not okay without permission.

[PATCH v3 07/10] <linux/hash.h>: Add support for architecture-specific functions

[George Spelvin]

This is just the infrastructure; there are no users yet.

This is modelled on CONFIG_ARCH_RANDOM; a CONFIG_ symbol declares
the existence of <asm/hash.h>.

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 <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: Andreas Schwab <schwab@linux-m68k.org>
Cc: Philippe De Muyter <phdm@macq.eu>
Cc: linux-m68k@lists.linux-m68k.org
Cc: Alistair Francis <alistai@xilinx.com>
Cc: Michal Simek <michal.simek@xilinx.com>
Cc: Yoshinori Sato <ysato@users.sourceforge.jp>
Cc: uclinux-h8-devel@lists.sourceforge.jp
---
 arch/Kconfig         |   8 ++
 fs/namei.c           |   6 +-
 include/linux/hash.h |  27 +++++-
 lib/Kconfig.debug    |  11 +++
 lib/Makefile         |   1 +
 lib/test_hash.c      | 250 +++++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 299 insertions(+), 4 deletions(-)
 create mode 100644 lib/test_hash.c

diff --git a/arch/Kconfig b/arch/Kconfig
index 81869a5e..96406e4d 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 <asm/hash.h>
+	  file which provides platform-specific implementations of some
+	  functions in <linux/hash.h> or fs/namei.c.
+
 #
 # ABI hall of shame
 #
diff --git a/fs/namei.c b/fs/namei.c
index a49cbd7e..968dae02 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -1788,7 +1788,11 @@ static int walk_component(struct nameidata *nd, int flags)
 
 #include <asm/word-at-a-time.h>
 
-#ifdef CONFIG_64BIT
+#ifdef HASH_MIX
+
+/* Architecture provides HASH_MIX and fold_hash() in <asm/hash.h> */
+
+#elif defined(CONFIG_64BIT)
 /*
  * Register pressure in the mixing function is an issue, particularly
  * on 32-bit x86, but almost any function requires one state value and
diff --git a/include/linux/hash.h b/include/linux/hash.h
index 613cfde3..ad6fa21d 100644
--- a/include/linux/hash.h
+++ b/include/linux/hash.h
@@ -41,19 +41,40 @@
 #define GOLDEN_RATIO_32 0x61C88647
 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
 
+#ifdef CONFIG_HAVE_ARCH_HASH
+/* This header may use the GOLDEN_RATIO_xx constants */
+#include <asm/hash.h>
+#endif
 
-static inline u32 __hash_32(u32 val)
+/*
+ * The _generic versions exist only so lib/test_hash.c can compare
+ * the arch-optimized versions with the generic.
+ *
+ * Note that if you change these, any <asm/hash.h> that aren't updated
+ * to match need to have their HAVE_ARCH_* define values updated so the
+ * self-test will not false-positive.
+ */
+#ifndef HAVE_ARCH__HASH_32
+#define __hash_32 __hash_32_generic
+#endif
+static inline u32 __hash_32_generic(u32 val)
 {
 	return val * GOLDEN_RATIO_32;
 }
 
-static inline u32 hash_32(u32 val, unsigned int bits)
+#ifndef HAVE_ARCH_HASH_32
+#define hash_32 hash_32_generic
+#endif
+static inline u32 hash_32_generic(u32 val, unsigned int bits)
 {
 	/* High bits are more random, so use them. */
 	return __hash_32(val) >> (32 - bits);
 }
 
-static __always_inline u32 hash_64(u64 val, unsigned int bits)
+#ifndef HAVE_ARCH_HASH_64
+#define hash_64 hash_64_generic
+#endif
+static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
 {
 #if BITS_PER_LONG == 64
 	/* 64x64-bit multiply is efficient on all 64-bit processors */
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 1e9a6075..18ec69ba 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1815,6 +1815,17 @@ config TEST_RHASHTABLE
 
 	  If unsure, say N.
 
+config TEST_HASH
+	tristate "Perform selftest on hash functions"
+	default n
+	help
+	  Enable this option to test the kernel's integer (<linux/hash,h>)
+	  and string (<linux/stringhash.h>) hash functions on boot
+	  (or module load).
+
+	  This is intended to help people writing architecture-specific
+	  optimized versions.  If unsure, say N.
+
 endmenu # runtime tests
 
 config PROVIDE_OHCI1394_DMA_INIT
diff --git a/lib/Makefile b/lib/Makefile
index 7bd6fd43..f80b1a1b 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -48,6 +48,7 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
+obj-$(CONFIG_TEST_HASH) += test_hash.o
 obj-$(CONFIG_TEST_KASAN) += test_kasan.o
 obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
 obj-$(CONFIG_TEST_LKM) += test_module.o
diff --git a/lib/test_hash.c b/lib/test_hash.c
new file mode 100644
index 00000000..c9549c8b
--- /dev/null
+++ b/lib/test_hash.c
@@ -0,0 +1,250 @@
+/*
+ * Test cases for <linux/hash.h> and <linux/stringhash.h>
+ * This just verifies that various ways of computing a hash
+ * produce the same thing and, for cases where a k-bit hash
+ * value is requested, is of the requested size.
+ *
+ * We fill a buffer with a 255-byte null-terminated string,
+ * and use both full_name_hash() and hashlen_string() to hash the
+ * substrings from i to j, where 0 <= i < j < 256.
+ *
+ * The returned values are used to check that __hash_32() and
+ * __hash_32_generic() compute the same thing.  Likewise hash_32()
+ * and hash_64().
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt "\n"
+
+#include <linux/compiler.h>
+#include <linux/types.h>
+#include <linux/module.h>
+#include <linux/hash.h>
+#include <linux/stringhash.h>
+#include <linux/printk.h>
+
+/* 32-bit XORSHIFT generator.  Seed must not be zero. */
+static u32 __init __attribute_const__
+xorshift(u32 seed)
+{
+	seed ^= seed << 13;
+	seed ^= seed >> 17;
+	seed ^= seed << 5;
+	return seed;
+}
+
+/* Given a non-zero x, returns a non-zero byte. */
+static u8 __init __attribute_const__
+mod255(u32 x)
+{
+	x = (x & 0xffff) + (x >> 16);	/* 1 <= x <= 0x1fffe */
+	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0x2fd */
+	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0x100 */
+	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0xff */
+	return x;
+}
+
+/* Fill the buffer with non-zero bytes. */
+static void __init
+fill_buf(char *buf, size_t len, u32 seed)
+{
+	size_t i;
+
+	for (i = 0; i < len; i++) {
+		seed = xorshift(seed);
+		buf[i] = mod255(seed);
+	}
+}
+
+/*
+ * Test the various integer hash functions.  h64 (or its low-order bits)
+ * is the integer to hash.  hash_or accumulates the OR of the hash values,
+ * which are later checked to see that they cover all the requested bits.
+ *
+ * Because these functions (as opposed to the string hashes) are all
+ * inline, the code being tested is actually in the module, and you can
+ * recompile and re-test the module without rebooting.
+ */
+static bool __init
+test_int_hash(unsigned long long h64, u32 hash_or[2][33])
+{
+	int k;
+	u32 h0 = (u32)h64, h1, h2;
+
+	/* Test __hash32 */
+	hash_or[0][0] |= h1 = __hash_32(h0);
+#ifdef HAVE_ARCH__HASH_32
+	hash_or[1][0] |= h2 = __hash_32_generic(h0);
+#if HAVE_ARCH__HASH_32 == 1
+	if (h1 != h2) {
+		pr_err("__hash_32(%#x) = %#x != __hash_32_generic() = %#x",
+			h0, h1, h2);
+		return false;
+	}
+#endif
+#endif
+
+	/* Test k = 1..32 bits */
+	for (k = 1; k <= 32; k++) {
+		u32 const m = ((u32)2 << (k-1)) - 1;	/* Low k bits set */
+
+		/* Test hash_32 */
+		hash_or[0][k] |= h1 = hash_32(h0, k);
+		if (h1 > m) {
+			pr_err("hash_32(%#x, %d) = %#x > %#x", h0, k, h1, m);
+			return false;
+		}
+#ifdef HAVE_ARCH_HASH_32
+		h2 = hash_32_generic(h0, k);
+#if HAVE_ARCH_HASH_32 == 1
+		if (h1 != h2) {
+			pr_err("hash_32(%#x, %d) = %#x != hash_32_generic() "
+				" = %#x", h0, k, h1, h2);
+			return false;
+		}
+#else
+		if (h2 > m) {
+			pr_err("hash_32_generic(%#x, %d) = %#x > %#x",
+				h0, k, h1, m);
+			return false;
+		}
+#endif
+#endif
+		/* Test hash_64 */
+		hash_or[1][k] |= h1 = hash_64(h64, k);
+		if (h1 > m) {
+			pr_err("hash_64(%#llx, %d) = %#x > %#x", h64, k, h1, m);
+			return false;
+		}
+#ifdef HAVE_ARCH_HASH_64
+		h2 = hash_64_generic(h64, k);
+#if HAVE_ARCH_HASH_64 == 1
+		if (h1 != h2) {
+			pr_err("hash_64(%#llx, %d) = %#x != hash_64_generic() "
+				"= %#x", h64, k, h1, h2);
+			return false;
+		}
+#else
+		if (h2 > m) {
+			pr_err("hash_64_generic(%#llx, %d) = %#x > %#x",
+				h64, k, h1, m);
+			return false;
+		}
+#endif
+#endif
+	}
+
+	(void)h2;	/* Suppress unused variable warning */
+	return true;
+}
+
+#define SIZE 256	/* Run time is cubic in SIZE */
+
+static int __init
+test_hash_init(void)
+{
+	char buf[SIZE+1];
+	u32 string_or = 0, hash_or[2][33] = { 0 };
+	unsigned tests = 0;
+	unsigned long long h64 = 0;
+	int i, j;
+
+	fill_buf(buf, SIZE, 1);
+
+	/* Test every possible non-empty substring in the buffer. */
+	for (j = SIZE; j > 0; --j) {
+		buf[j] = '\0';
+
+		for (i = 0; i <= j; i++) {
+			u64 hashlen = hashlen_string(buf+i);
+			u32 h0 = full_name_hash(buf+i, j-i);
+
+			/* Check that hashlen_string gets the length right */
+			if (hashlen_len(hashlen) != j-i) {
+				pr_err("hashlen_string(%d..%d) returned length"
+					" %u, expected %d",
+					i, j, hashlen_len(hashlen), j-i);
+				return -EINVAL;
+			}
+			/* Check that the hashes match */
+			if (hashlen_hash(hashlen) != h0) {
+				pr_err("hashlen_string(%d..%d) = %08x != "
+					"full_name_hash() = %08x",
+					i, j, hashlen_hash(hashlen), h0);
+				return -EINVAL;
+			}
+
+			string_or |= h0;
+			h64 = h64 << 32 | h0;	/* For use with hash_64 */
+			if (!test_int_hash(h64, hash_or))
+				return -EINVAL;
+			tests++;
+		} /* i */
+	} /* j */
+
+	/* The OR of all the hash values should cover all the bits */
+	if (~string_or) {
+		pr_err("OR of all string hash results = %#x != %#x",
+			string_or, -1u);
+		return -EINVAL;
+	}
+	if (~hash_or[0][0]) {
+		pr_err("OR of all __hash_32 results = %#x != %#x",
+			hash_or[0][0], -1u);
+		return -EINVAL;
+	}
+#ifdef HAVE_ARCH__HASH_32
+#if HAVE_ARCH__HASH_32 != 1	/* Test is pointless if results match */
+	if (~hash_or[1][0]) {
+		pr_err("OR of all __hash_32_generic results = %#x != %#x",
+			hash_or[1][0], -1u);
+		return -EINVAL;
+	}
+#endif
+#endif
+
+	/* Likewise for all the i-bit hash values */
+	for (i = 1; i <= 32; i++) {
+		u32 const m = ((u32)2 << (i-1)) - 1;	/* Low i bits set */
+
+		if (hash_or[0][i] != m) {
+			pr_err("OR of all hash_32(%d) results = %#x "
+				"(%#x expected)", i, hash_or[0][i], m);
+			return -EINVAL;
+		}
+		if (hash_or[1][i] != m) {
+			pr_err("OR of all hash_64(%d) results = %#x "
+				"(%#x expected)", i, hash_or[1][i], m);
+			return -EINVAL;
+		}
+	}
+
+	/* Issue notices about skipped tests. */
+#ifndef HAVE_ARCH__HASH_32
+	pr_info("__hash_32() has no arch implementation to test.");
+#elif HAVE_ARCH__HASH_32 != 1
+	pr_info("__hash_32() is arch-specific; not compared to generic.");
+#endif
+#ifndef HAVE_ARCH_HASH_32
+	pr_info("hash_32() has no arch implementation to test.");
+#elif HAVE_ARCH_HASH_32 != 1
+	pr_info("hash_32() is arch-specific; not compared to generic.");
+#endif
+#ifndef HAVE_ARCH_HASH_64
+	pr_info("hash_64() has no arch implementation to test.");
+#elif HAVE_ARCH_HASH_64 != 1
+	pr_info("hash_64() is arch-specific; not compared to generic.");
+#endif
+
+	pr_notice("%u tests passed.", tests);
+
+	return 0;
+}
+
+static void __exit test_hash_exit(void)
+{
+}
+
+module_init(test_hash_init);	/* Does everything */
+module_exit(test_hash_exit);	/* Does nothing */
+
+MODULE_LICENSE("GPL");
-- 
2.8.1

[PATCH v3 08/10] m68k: Add <asm/hash.h>

[George Spelvin]

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 <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: Andreas Schwab <schwab@linux-m68k.org>
Cc: Philippe De Muyter <phdm@macq.eu>
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

diff --git a/arch/m68k/Kconfig.cpu b/arch/m68k/Kconfig.cpu
index 0dfcf128..bf3de464 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 00000000..6407af84
--- /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,<reg>" (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 */
-- 
2.8.1

Re: [PATCH v3 07/10] <linux/hash.h>: Add support for architecture-specific functions

[Geert Uytterhoeven]

Hi George,

I see this has been applied in the mean time, but improvements
never hurt...

On Sat, May 28, 2016 at 9:57 PM, George Spelvin
<linux@sciencehorizons.net> wrote:
> --- /dev/null
> +++ b/lib/test_hash.c
> @@ -0,0 +1,250 @@

> +/*
> + * Test the various integer hash functions.  h64 (or its low-order bits)
> + * is the integer to hash.  hash_or accumulates the OR of the hash values,
> + * which are later checked to see that they cover all the requested bits.
> + *
> + * Because these functions (as opposed to the string hashes) are all
> + * inline, the code being tested is actually in the module, and you can
> + * recompile and re-test the module without rebooting.
> + */
> +static bool __init
> +test_int_hash(unsigned long long h64, u32 hash_or[2][33])
> +{
> +       int k;
> +       u32 h0 = (u32)h64, h1, h2;
> +
> +       /* Test __hash32 */
> +       hash_or[0][0] |= h1 = __hash_32(h0);
> +#ifdef HAVE_ARCH__HASH_32
> +       hash_or[1][0] |= h2 = __hash_32_generic(h0);

__hash_32_generic() always exist, right?
So you can reduce #ifdefery and increase compile coverage by dropping the
#ifdef ...

> +#if HAVE_ARCH__HASH_32 == 1
> +       if (h1 != h2) {

... and replacing this test by

        if (identical_hashes && (h1 != h2))

with identical_hashes a static const bool initialized depending on
HAVE_ARCH__HASH_32.

> +               pr_err("__hash_32(%#x) = %#x != __hash_32_generic() = %#x",
> +                       h0, h1, h2);
> +               return false;
> +       }
> +#endif
> +#endif

The same comment applies to the other hunks.

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [PATCH 00/10] String hash improvements

[Fubo Chen]

On Wed, May 25, 2016 at 9:08 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> Ok, thanks. For some odd reason all your emails in this series got
> marked as spam. Every single one, including the cover letter (but not
> your replies to the replies to this).

I have added the following filter to my gmail account: "never send
e-mails with [PATCH in the subject to the spam folder". That helps a
lot.

Fubo.

[PATCH 07/10] <linux/hash.h>: Add support for architecture-specific functions

[George Spelvin]

This is just the infrastructure; there are no users yet.

This is modelled on CONFIG_ARCH_RANDOM; a CONFIG_ symbol declares
the existence of <asm/archhash.h>.

That file may define its own versions of various functions, and define
HAVE_* symbols (no CONFIG_ prefix!) to suppress the generic ones.

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: linux-m68k@lists.linux-m68k.org
Cc: Alistair Francis <alistai@xilinx.com>
Cc: Michal Simek <michal.simek@xilinx.com>
Cc: Yoshinori Sato <ysato@users.sourceforge.jp>
Cc: uclinux-h8-devel@lists.sourceforge.jp
---
 arch/Kconfig         |  8 ++++++++
 fs/namei.c           |  6 +++++-
 include/linux/hash.h | 11 +++++++++++
 3 files changed, 24 insertions(+), 1 deletion(-)

diff --git a/arch/Kconfig b/arch/Kconfig
index 81869a5e..33e8d7b1 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 <asm/archhash.h>
+	  file which provides platform-specific implementations of some
+	  functions in <linux/hash.h> or fs/namei.c.
+
 #
 # ABI hall of shame
 #
diff --git a/fs/namei.c b/fs/namei.c
index 2b8d0650..380e8057 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -1788,7 +1788,11 @@ static int walk_component(struct nameidata *nd, int flags)
 
 #include <asm/word-at-a-time.h>
 
-#ifdef CONFIG_64BIT
+#ifdef HASH_MIX
+
+/* Architecture provides HASH_MIX and fold_hash() in <linux/hash.h> */
+
+#elif defined(CONFIG_64BIT)
 /*
  * Register pressure in the mixing function is an issue, particularly
  * on 32-bit x86, but almost any function requires one state value and
diff --git a/include/linux/hash.h b/include/linux/hash.h
index 8926f369..838bc84b 100644
--- a/include/linux/hash.h
+++ b/include/linux/hash.h
@@ -41,17 +41,27 @@
 #define GOLDEN_RATIO_32 0x61C88647
 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
 
+#ifdef CONFIG_HAVE_ARCH_HASH
+/* This header may use the GOLDEN_RATIO_xx constants */
+#include <asm/archhash.h>
+#endif
+
+#ifndef HAVE_ARCH__HASH_32
 static inline u32 __hash_32(u32 val)
 {
 	return val * GOLDEN_RATIO_32;
 }
+#endif
 
+#ifndef HAVE_ARCH_HASH_32
 static inline u32 hash_32(u32 val, unsigned int bits)
 {
 	/* High bits are more random, so use them. */
 	return __hash_32(val) >> (32 - bits);
 }
+#endif
 
+#ifndef HAVE_ARCH_HASH_64
 static __always_inline u32 hash_64(u64 val, unsigned int bits)
 {
 	if (__builtin_constant_p(bits > 32 || bits == 0)) {
@@ -74,6 +84,7 @@ static __always_inline u32 hash_64(u64 val, unsigned int bits)
 	return hash_32((u32)val - __hash_32(val >> 32), bits);
 #endif
 }
+#endif
 
 static inline u32 hash_ptr(const void *ptr, unsigned int bits)
 {
-- 
2.8.1

[PATCH v2 07/10] <linux/hash.h>: Add support for architecture-specific functions

[George Spelvin]

This is just the infrastructure; there are no users yet.

This is modelled on CONFIG_ARCH_RANDOM; a CONFIG_ symbol declares
the existence of <asm/hash.h>.

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 <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: Andreas Schwab <schwab@linux-m68k.org>
Cc: Philippe De Muyter <phdm@macq.eu>
Cc: linux-m68k@lists.linux-m68k.org
Cc: Alistair Francis <alistai@xilinx.com>
Cc: Michal Simek <michal.simek@xilinx.com>
Cc: Yoshinori Sato <ysato@users.sourceforge.jp>
Cc: uclinux-h8-devel@lists.sourceforge.jp
---
 arch/Kconfig         |   8 ++
 fs/namei.c           |   6 +-
 include/linux/hash.h |  24 ++++-
 lib/Kconfig.debug    |  11 +++
 lib/Makefile         |   1 +
 lib/test_hash.c      | 250 +++++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 296 insertions(+), 4 deletions(-)
 create mode 100644 lib/test_hash.c

diff --git a/arch/Kconfig b/arch/Kconfig
index 81869a5e..96406e4d 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 <asm/hash.h>
+	  file which provides platform-specific implementations of some
+	  functions in <linux/hash.h> or fs/namei.c.
+
 #
 # ABI hall of shame
 #
diff --git a/fs/namei.c b/fs/namei.c
index 2b8d0650..cb438b84 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -1788,7 +1788,11 @@ static int walk_component(struct nameidata *nd, int flags)
 
 #include <asm/word-at-a-time.h>
 
-#ifdef CONFIG_64BIT
+#ifdef HASH_MIX
+
+/* Architecture provides HASH_MIX and fold_hash() in <asm/hash.h> */
+
+#elif defined(CONFIG_64BIT)
 /*
  * Register pressure in the mixing function is an issue, particularly
  * on 32-bit x86, but almost any function requires one state value and
diff --git a/include/linux/hash.h b/include/linux/hash.h
index 8926f369..ab62a9a4 100644
--- a/include/linux/hash.h
+++ b/include/linux/hash.h
@@ -41,18 +41,36 @@
 #define GOLDEN_RATIO_32 0x61C88647
 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
 
-static inline u32 __hash_32(u32 val)
+#ifdef CONFIG_HAVE_ARCH_HASH
+/* This header may use the GOLDEN_RATIO_xx constants */
+#include <asm/hash.h>
+#endif
+
+/*
+ * The _generic versions exist only so lib/test_hash.c can
+ * compare the arch-optimized versions with the generic.
+ */
+#ifndef HAVE_ARCH__HASH_32
+#define __hash_32 __hash_32_generic
+#endif
+static inline u32 __hash_32_generic(u32 val)
 {
 	return val * GOLDEN_RATIO_32;
 }
 
-static inline u32 hash_32(u32 val, unsigned int bits)
+#ifndef HAVE_ARCH_HASH_32
+#define hash_32 hash_32_generic
+#endif
+static inline u32 hash_32_generic(u32 val, unsigned int bits)
 {
 	/* High bits are more random, so use them. */
 	return __hash_32(val) >> (32 - bits);
 }
 
-static __always_inline u32 hash_64(u64 val, unsigned int bits)
+#ifndef HAVE_ARCH_HASH_64
+#define hash_64 hash_64_generic
+#endif
+static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
 {
 	if (__builtin_constant_p(bits > 32 || bits == 0)) {
 		BUILD_BUG_ON(bits > 32 || bits == 0);
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 1e9a6075..18ec69ba 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1815,6 +1815,17 @@ config TEST_RHASHTABLE
 
 	  If unsure, say N.
 
+config TEST_HASH
+	tristate "Perform selftest on hash functions"
+	default n
+	help
+	  Enable this option to test the kernel's integer (<linux/hash,h>)
+	  and string (<linux/stringhash.h>) hash functions on boot
+	  (or module load).
+
+	  This is intended to help people writing architecture-specific
+	  optimized versions.  If unsure, say N.
+
 endmenu # runtime tests
 
 config PROVIDE_OHCI1394_DMA_INIT
diff --git a/lib/Makefile b/lib/Makefile
index 9d9804e5..16c3bda5 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -48,6 +48,7 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
+obj-$(CONFIG_TEST_HASH) += test_hash.o
 obj-$(CONFIG_TEST_KASAN) += test_kasan.o
 obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
 obj-$(CONFIG_TEST_LKM) += test_module.o
diff --git a/lib/test_hash.c b/lib/test_hash.c
new file mode 100644
index 00000000..bb43dac1
--- /dev/null
+++ b/lib/test_hash.c
@@ -0,0 +1,250 @@
+/*
+ * Test cases for <linux/hash.h> and <linux/stringhash.h>
+ * This just verifies that various ways of computing a hash
+ * produce the same thing and, for cases where a k-bit hash
+ * value is requested, is of the requested size.
+ *
+ * We fill a buffer with a 255-byte null-terminated string,
+ * and use both full_name_hash() and hash_string() to hash the
+ * substrings from i to j, where 0 <= i < j < 256.
+ *
+ * The returned values are used to check that __hash_32() and
+ * __hash_32_generic() compute the same thing.  Likewise hash_32()
+ * and hash_64().
+ * */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt "\n"
+
+#include <linux/compiler.h>
+#include <linux/types.h>
+#include <linux/module.h>
+#include <linux/hash.h>
+#include <linux/stringhash.h>
+#include <linux/printk.h>
+
+/* 32-bit XORSHIFT generator.  Seed must not be zero. */
+static u32 __init __attribute_const__
+xorshift(u32 seed)
+{
+	seed ^= seed << 13;
+	seed ^= seed >> 17;
+	seed ^= seed << 5;
+	return seed;
+}
+
+/* Given a non-zero x, returns a non-zero byte. */
+static u8 __init __attribute_const__
+mod255(u32 x)
+{
+	x = (x & 0xffff) + (x >> 16);	/* 1 <= x <= 0x1fffe */
+	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0x2fd */
+	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0x100 */
+	x = (x & 0xff) + (x >> 8);	/* 1 <= x <= 0xff */
+	return x;
+}
+
+/* Fill the buffer with non-zero bytes. */
+static void __init
+fill_buf(char *buf, size_t len, u32 seed)
+{
+	size_t i;
+
+	for (i = 0; i < len; i++) {
+		seed = xorshift(seed);
+		buf[i] = mod255(seed);
+	}
+}
+
+/*
+ * Test the various integer hash functions.  h64 (or its low-order bits)
+ * is the integer to hash.  hash_or accumulates the OR of the hash values,
+ * which are later checked to see that they cover all the requested bits.
+ *
+ * Because these functions (as opposed to the string hashes) are all
+ * inline, the code being tested is actually in the module, and you can
+ * recompile and re-test the module without rebooting.
+ */
+static bool __init
+test_int_hash(unsigned long long h64, u32 hash_or[2][33])
+{
+	int k;
+	u32 h0 = (u32)h64, h1, h2;
+
+	/* Test __hash32 */
+	hash_or[0][0] |= h1 = __hash_32(h0);
+#ifdef HAVE_ARCH__HASH_32
+	hash_or[1][0] |= h2 = __hash_32_generic(h0);
+#if HAVE_ARCH__HASH_32 == 1
+	if (h1 != h2) {
+		pr_err("__hash_32(%#x) = %#x != __hash_32_generic() = %#x",
+			h0, h1, h2);
+		return false;
+	}
+#endif
+#endif
+
+	/* Test k = 1..32 bits */
+	for (k = 1; k <= 32; k++) {
+		u32 const m = ((u32)2 << (k-1)) - 1;	/* Low k bits set */
+
+		/* Test hash_32 */
+		hash_or[0][k] |= h1 = hash_32(h0, k);
+		if (h1 > m) {
+			pr_err("hash_32(%#x, %d) = %#x > %#x", h0, k, h1, m);
+			return false;
+		}
+#ifdef HAVE_ARCH_HASH_32
+		h2 = hash_32_generic(h0, k);
+#if HAVE_ARCH_HASH_32 == 1
+		if (h1 != h2) {
+			pr_err("hash_32(%#x, %d) = %#x != hash_32_generic() "
+				" = %#x", h0, k, h1, h2);
+			return false;
+		}
+#else
+		if (h2 > m) {
+			pr_err("hash_32_generic(%#x, %d) = %#x > %#x",
+				h0, k, h1, m);
+			return false;
+		}
+#endif
+#endif
+		/* Test hash_64 */
+		hash_or[1][k] |= h1 = hash_64(h64, k);
+		if (h1 > m) {
+			pr_err("hash_64(%#llx, %d) = %#x > %#x", h64, k, h1, m);
+			return false;
+		}
+#ifdef HAVE_ARCH_HASH_64
+		h2 = hash_64_generic(h64, k);
+#if HAVE_ARCH_HASH_64 == 1
+		if (h1 != h2) {
+			pr_err("hash_64(%#llx, %d) = %#x != hash_64_generic() "
+				"= %#x", h64, k, h1, h2);
+			return false;
+		}
+#else
+		if (h2 > m) {
+			pr_err("hash_64_generic(%#llx, %d) = %#x > %#x",
+				h64, k, h1, m);
+			return false;
+		}
+#endif
+#endif
+	}
+
+	(void)h2;	/* Suppress unused variable warning */
+	return true;
+}
+
+#define SIZE 256	/* Run time is cubic in SIZE */
+
+static int __init
+test_hash_init(void)
+{
+	char buf[SIZE];
+	u32 string_or = 0, hash_or[2][33] = { 0 };
+	unsigned tests = 0;
+	unsigned long long h64 = 0;
+	int i, j;
+
+	fill_buf(buf, SIZE-1, 1);
+
+	/* Test every possible non-empty substring in the buffer. */
+	for (j = SIZE; j > 0; --j) {
+		buf[j-1] = '\0';
+
+		for (i = 0; i < j; i++) {
+			u32 h0 = full_name_hash(buf+i, j-i);
+			u64 hashlen = hash_string(buf+i);
+
+			/* Check that hash_string gets the length right */
+			if (hashlen_len(hashlen) != j-i-1) {
+				pr_err("hash_string(%d..%d) returned length "
+					"%u, expected %d",
+					i, j, hashlen_len(hashlen), j-i-1);
+				return -EINVAL;
+			}
+			/* Check that the hashes match */
+			if (hashlen_hash(hashlen) != h0) {
+				pr_err("hash_string(%d..%d) = %08x != "
+					"full_name_hash() = %08x",
+					i, j, hashlen_hash(hashlen), h0);
+				return -EINVAL;
+			}
+
+			string_or |= h0;
+			h64 = h64 << 32 | h0;	/* For use with hash_64 */
+			if (!test_int_hash(h64, hash_or))
+				return -EINVAL;
+			tests++;
+		} /* i */
+	} /* j */
+
+	/* The OR of all the hash values should cover all the bits */
+	if (~string_or) {
+		pr_err("OR of all string hash results = %#x != %#x",
+			string_or, -1u);
+		return -EINVAL;
+	}
+	if (~hash_or[0][0]) {
+		pr_err("OR of all __hash_32 results = %#x != %#x",
+			hash_or[0][0], -1u);
+		return -EINVAL;
+	}
+#ifdef HAVE_ARCH__HASH_32
+#if HAVE_ARCH__HASH_32 != 1	/* Test is pointless if results match */
+	if (~hash_or[1][0]) {
+		pr_err("OR of all __hash_32_generic results = %#x != %#x",
+			hash_or[1][0], -1u);
+		return -EINVAL;
+	}
+#endif
+#endif
+
+	/* Likewise for all the i-bit hash values */
+	for (i = 1; i <= 32; i++) {
+		u32 const m = ((u32)2 << (i-1)) - 1;	/* Low i bits set */
+
+		if (hash_or[0][i] != m) {
+			pr_err("OR of all hash_32(%d) results = %#x "
+				"(%#x expected)", i, hash_or[0][i], m);
+			return -EINVAL;
+		}
+		if (hash_or[1][i] != m) {
+			pr_err("OR of all hash_64(%d) results = %#x "
+				"(%#x expected)", i, hash_or[1][i], m);
+			return -EINVAL;
+		}
+	}
+
+	/* Issue notices about skipped tests. */
+#ifndef HAVE_ARCH__HASH_32
+	pr_info("__hash_32() has no arch implementation to test.");
+#elif HAVE_ARCH__HASH_32 != 1
+	pr_info("__hash_32() is arch-specific; not compared to generic.");
+#endif
+#ifndef HAVE_ARCH_HASH_32
+	pr_info("hash_32() has no arch implementation to test.");
+#elif HAVE_ARCH_HASH_32 != 1
+	pr_info("hash_32() is arch-specific; not compared to generic.");
+#endif
+#ifndef HAVE_ARCH_HASH_64
+	pr_info("hash_64() has no arch implementation to test.");
+#elif HAVE_ARCH_HASH_64 != 1
+	pr_info("hash_64() is arch-specific; not compared to generic.");
+#endif
+
+	pr_notice("%u tests passed.", tests);
+
+	return 0;
+}
+
+static void __exit test_hash_exit(void)
+{
+}
+
+module_init(test_hash_init);	/* Does everything */
+module_exit(test_hash_exit);	/* Does nothing */
+
+MODULE_LICENSE("GPL");
-- 
2.8.1

[PATCH 08/10] m68k: Add <asm/archhash.h>

[George Spelvin]

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. :-)

Addition chains found by Yevgen Voronenko's Hcub algorithm at
http://spiral.ece.cmu.edu/mcm/gen.html

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: linux-m68k@lists.linux-m68k.org
---
 arch/m68k/Kconfig                |  1 +
 arch/m68k/include/asm/archhash.h | 67 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 68 insertions(+)
 create mode 100644 arch/m68k/include/asm/archhash.h

diff --git a/arch/m68k/Kconfig b/arch/m68k/Kconfig
index 498b567f..95197d5e 100644
--- a/arch/m68k/Kconfig
+++ b/arch/m68k/Kconfig
@@ -23,6 +23,7 @@ config M68K
 	select MODULES_USE_ELF_RELA
 	select OLD_SIGSUSPEND3
 	select OLD_SIGACTION
+	select HAVE_ARCH_HASH
 
 config RWSEM_GENERIC_SPINLOCK
 	bool
diff --git a/arch/m68k/include/asm/archhash.h b/arch/m68k/include/asm/archhash.h
new file mode 100644
index 00000000..c2bb2fc5
--- /dev/null
+++ b/arch/m68k/include/asm/archhash.h
@@ -0,0 +1,67 @@
+#ifndef _ASM_ARCHHASH_H
+#define _ASM_ARCHHASH_H
+
+/*
+ * The only 68k processors that lack MULU.L and so need this workaround
+ * are the original 68000 and 68010.
+ *
+ * Annoyingly, GCC defines __mc68000 for all processors in the family;
+ * the only way to identify an mc68000 is by the *absence* of other
+ * symbols; __mcpu32, __mcoldfire__, __mc68020, etc.
+ */
+#if ! (defined(__mc68020) || \
+	defined(__mc68030) || \
+	defined(__mc68040) || \
+	defined(__mc68060) || \
+	defined(__mcpu32)  || \
+	defined(__mcoldfire))
+
+#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 GCC simple operations, GCC 6.1.1
+ * doggedly insists on doing annoying things like converting "lsl.l #2,<reg>"
+ * (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.
+ */
+static inline u32 __attribute_const__ __hash_32(u32 x)
+{
+	u32 a, b;
+
+	asm(   "move.l %2,%0"	/* 0x0001 */
+	"\n	lsl.l #2,%0"	/* 0x0004 */
+	"\n	move.l %0,%1"
+	"\n	lsl.l #7,%0"	/* 0x0200 */
+	"\n	add.l %2,%0"	/* 0x0201 */
+	"\n	add.l %0,%1"	/* 0x0205 */
+	"\n	add.l %0,%0"	/* 0x0402 */
+	"\n	add.l %0,%1"	/* 0x0607 */
+	"\n	lsl.l #5,%0"	/* 0x8040 */
+				/* 0x8647 */
+	: "=&d" (a), "=&r" (b)
+	: "g" (x));
+
+	return ((u16)(x*0x61c8) << 16) + a + b;
+}
+#endif	/* HAVE_ARCH__HASH_32 */
+
+#endif	/* _ASM_ARCHHASH_H */
-- 
2.8.1

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[Geert Uytterhoeven]

Hi George,

On Wed, May 25, 2016 at 9:34 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
> 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. :-)
>
> Addition chains found by Yevgen Voronenko's Hcub algorithm at
> http://spiral.ece.cmu.edu/mcm/gen.html
>
> Signed-off-by: George Spelvin <linux@sciencehorizons.net>
> Cc: Geert Uytterhoeven <geert@linux-m68k.org>
> Cc: Greg Ungerer <gerg@linux-m68k.org>
> Cc: linux-m68k@lists.linux-m68k.org
> ---
>  arch/m68k/Kconfig                |  1 +
>  arch/m68k/include/asm/archhash.h | 67 ++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 68 insertions(+)
>  create mode 100644 arch/m68k/include/asm/archhash.h
>
> diff --git a/arch/m68k/Kconfig b/arch/m68k/Kconfig
> index 498b567f..95197d5e 100644
> --- a/arch/m68k/Kconfig
> +++ b/arch/m68k/Kconfig
> @@ -23,6 +23,7 @@ config M68K
>         select MODULES_USE_ELF_RELA
>         select OLD_SIGSUSPEND3
>         select OLD_SIGACTION
> +       select HAVE_ARCH_HASH

"select HAVE_ARCH_HASH if M68000"?

Or better, move the select to the M68000 section in arch/m68k/Kconfig.cpu.

> --- /dev/null
> +++ b/arch/m68k/include/asm/archhash.h
> @@ -0,0 +1,67 @@
> +#ifndef _ASM_ARCHHASH_H
> +#define _ASM_ARCHHASH_H
> +
> +/*
> + * The only 68k processors that lack MULU.L and so need this workaround
> + * are the original 68000 and 68010.
> + *
> + * Annoyingly, GCC defines __mc68000 for all processors in the family;
> + * the only way to identify an mc68000 is by the *absence* of other
> + * symbols; __mcpu32, __mcoldfire__, __mc68020, etc.
> + */
> +#if ! (defined(__mc68020) || \
> +       defined(__mc68030) || \
> +       defined(__mc68040) || \
> +       defined(__mc68060) || \
> +       defined(__mcpu32)  || \
> +       defined(__mcoldfire))

With my comment above, you wouldn't need this, but I'm gonna comment anyway.

We don't use special GCCs to target specific CPU variants. Hence inside the
kernel, you should check the config symbols, to see if support for 68000 or
68010 (which isn't supported by the kernel yet) is enabled.

Hence the check should be:

    #if defined(CONFIG_M68000) || defined(CONFIG_M68010)

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[George Spelvin]

> With my comment above, you wouldn't need this, but I'm gonna comment anyway.
> 
> We don't use special GCCs to target specific CPU variants. Hence inside the
> kernel, you should check the config symbols, to see if support for 68000 or
> 68010 (which isn't supported by the kernel yet) is enabled.

Do you remember some earlier discussion about the m68k Makefile and old
GCC versions?  In particular, lines like:

cpuflags-$(CONFIG_M525x)        := $(call cc-option,-mcpu=5253,-m5200)
cpuflags-$(CONFIG_M5249)        := $(call cc-option,-mcpu=5249,-m5200)
cpuflags-$(CONFIG_M520x)        := $(call cc-option,-mcpu=5208,-m5200)
cpuflags-$(CONFIG_M5206e)       := $(call cc-option,-mcpu=5206e,-m5200)
cpuflags-$(CONFIG_M5206)        := $(call cc-option,-mcpu=5206,-m5200)

The problem is that whether MULU.L exists depends on the targeted
architecture, and *that* depends on this Makefile trickery, not
just CONFIG symbols...

Oh, f*** me.


I misremembered.  That problem exists, but only for DIVU.L.  As I said in
the comments (which I wrote *after* deciding I needed this approach), all
ColdFire have MULU.L.  It's DIVU.L that's missing from some early ones.

You're absolutely right.  MULU.L support can be done perfectly from
CONFIG_ options.


Improved patch coming in a few minutes.  My sincere apologies.

Re: [PATCH 08v2/10] m68k: Add <asm/archhash.h>

[George Spelvin]

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. :-)

Addition chains found by Yevgen Voronenko's Hcub algorithm at
http://spiral.ece.cmu.edu/mcm/gen.html

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: linux-m68k@lists.linux-m68k.org
---
 arch/m68k/Kconfig.cpu            |  1 +
 arch/m68k/include/asm/archhash.h | 58 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 59 insertions(+)
 create mode 100644 arch/m68k/include/asm/archhash.h

diff --git a/arch/m68k/Kconfig.cpu b/arch/m68k/Kconfig.cpu
index 0dfcf128..bf3de464 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/archhash.h b/arch/m68k/include/asm/archhash.h
new file mode 100644
index 00000000..2532cf92
--- /dev/null
+++ b/arch/m68k/include/asm/archhash.h
@@ -0,0 +1,58 @@
+#ifndef _ASM_ARCHHASH_H
+#define _ASM_ARCHHASH_H
+
+/*
+ * The only 68k processors that lack MULU.L and so need this workaround
+ * are the original 68000 and 68010.
+ */
+#if defined(CONFIG_M68000) || defined(CONFIG_M68010)
+
+#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 GCC simple operations, GCC 6.1.1
+ * doggedly insists on doing annoying things like converting "lsl.l #2,<reg>"
+ * (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.
+ */
+static inline u32 __attribute_const__ __hash_32(u32 x)
+{
+	u32 a, b;
+
+	asm(   "move.l %2,%0"	/* 0x0001 */
+	"\n	lsl.l #2,%0"	/* 0x0004 */
+	"\n	move.l %0,%1"
+	"\n	lsl.l #7,%0"	/* 0x0200 */
+	"\n	add.l %2,%0"	/* 0x0201 */
+	"\n	add.l %0,%1"	/* 0x0205 */
+	"\n	add.l %0,%0"	/* 0x0402 */
+	"\n	add.l %0,%1"	/* 0x0607 */
+	"\n	lsl.l #5,%0"	/* 0x8040 */
+				/* 0x8647 */
+	: "=&d" (a), "=&r" (b)
+	: "g" (x));
+
+	return ((u16)(x*0x61c8) << 16) + a + b;
+}
+#endif	/* HAVE_ARCH__HASH_32 */
+
+#endif	/* _ASM_ARCHHASH_H */
-- 
2.8.1

Re: [PATCH 08v2/10] m68k: Add <asm/archhash.h>

[Geert Uytterhoeven]

On Wed, May 25, 2016 at 10:24 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
> --- 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/archhash.h b/arch/m68k/include/asm/archhash.h
> new file mode 100644
> index 00000000..2532cf92
> --- /dev/null
> +++ b/arch/m68k/include/asm/archhash.h
> @@ -0,0 +1,58 @@
> +#ifndef _ASM_ARCHHASH_H
> +#define _ASM_ARCHHASH_H
> +
> +/*
> + * The only 68k processors that lack MULU.L and so need this workaround
> + * are the original 68000 and 68010.
> + */
> +#if defined(CONFIG_M68000) || defined(CONFIG_M68010)

As I said before, I don't think you need this check, given HAVE_ARCH_HASH is
selected by M68000, and M68010 doesn't exist.

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[Philippe De Muyter]

On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
> +static inline u32 __attribute_const__ __hash_32(u32 x)
> +{
> +	u32 a, b;
> +
> +	asm(   "move.l %2,%0"	/* 0x0001 */
> +	"\n	lsl.l #2,%0"	/* 0x0004 */
> +	"\n	move.l %0,%1"
> +	"\n	lsl.l #7,%0"	/* 0x0200 */
> +	"\n	add.l %2,%0"	/* 0x0201 */
> +	"\n	add.l %0,%1"	/* 0x0205 */
> +	"\n	add.l %0,%0"	/* 0x0402 */
> +	"\n	add.l %0,%1"	/* 0x0607 */
> +	"\n	lsl.l #5,%0"	/* 0x8040 */
> +				/* 0x8647 */

There is no standard way to write asm in the kernel, but I prefer
a simple semicolon after each insn

	asm("move.l	%2,%0;"	/* 0x0001 */
	    "lsl.l	#2,%0;"	/* 0x0004 */
	    "move.l	%0,%1;"
	    "lsl.l	#7,%0;"	/* 0x0200 */
	    "add.l	%2,%0;"	/* 0x0201 */
	    "add.l	%0,%1;"	/* 0x0205 */
	    "add.l	%0,%0;"	/* 0x0402 */
	    "add.l	%0,%1;"	/* 0x0607 */
	    "lsl.l	#5,%0"	/* 0x8040 */
				/* 0x8647 */

Also, it took me some time to understand the hexadecimal constants
in the comments (and the last one predicts a future event :)).

> +	: "=&d" (a), "=&r" (b)
> +	: "g" (x));
> +
> +	return ((u16)(x*0x61c8) << 16) + a + b;
> +}

Just my two cents

Philippe

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[George Spelvin]

> On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
>> +static inline u32 __attribute_const__ __hash_32(u32 x)
>> +{
>> +	u32 a, b;
>> +
>> +	asm(   "move.l %2,%0"	/* 0x0001 */
>> +	"\n	lsl.l #2,%0"	/* 0x0004 */
>> +	"\n	move.l %0,%1"
>> +	"\n	lsl.l #7,%0"	/* 0x0200 */
>> +	"\n	add.l %2,%0"	/* 0x0201 */
>> +	"\n	add.l %0,%1"	/* 0x0205 */
>> +	"\n	add.l %0,%0"	/* 0x0402 */
>> +	"\n	add.l %0,%1"	/* 0x0607 */
>> +	"\n	lsl.l #5,%0"	/* 0x8040 */
>> +				/* 0x8647 */

> There is no standard way to write asm in the kernel, but I prefer
> a simple semicolon after each insn

I did it the way I did above because it makes the gcc -S output very
legible.  Just like I put a space before the perands on m68k but a tab
on h8300: that's what GCC does on those platforms.

I started with the "\n\t" suffixes on each line like so much other
kernel code, but then figured out the format above which is legible
both in C source and compiler output.

>>	asm("move.l	%2,%0;"	/* 0x0001 */
>>	    "lsl.l	#2,%0;"	/* 0x0004 */
>>	    "move.l	%0,%1;"
>>	    "lsl.l	#7,%0;"	/* 0x0200 */
>>	    "add.l	%2,%0;"	/* 0x0201 */
>>	    "add.l	%0,%1;"	/* 0x0205 */
>>	    "add.l	%0,%0;"	/* 0x0402 */
>>	    "add.l	%0,%1;"	/* 0x0607 */
>>	    "lsl.l	#5,%0"	/* 0x8040 */
>>				/* 0x8647 */

> Also, it took me some time to understand the hexadecimal constants
> in the comments (and the last one predicts a future event :)).


Can you recmmend a better way to comment this?  My nose is so deep
in the code it's hard for me to judge.

> Just my two cents

And thank you very much for them!

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[Andreas Schwab]

"George Spelvin" <linux@sciencehorizons.net> writes:

> Can you recmmend a better way to comment this?  My nose is so deep
> in the code it's hard for me to judge.

It's probably best to express the effect of the insns in plain C.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[Philippe De Muyter]

On Wed, May 25, 2016 at 05:14:35AM -0400, George Spelvin wrote:
> 
> I did it the way I did above because it makes the gcc -S output very
> legible.  Just like I put a space before the perands on m68k but a tab
> on h8300: that's what GCC does on those platforms.
> 
> I started with the "\n\t" suffixes on each line like so much other
> kernel code, but then figured out the format above which is legible
> both in C source and compiler output.

OK thanks.

> 
> >>	asm("move.l	%2,%0;"	/* 0x0001 */
> >>	    "lsl.l	#2,%0;"	/* 0x0004 */
> >>	    "move.l	%0,%1;"
> >>	    "lsl.l	#7,%0;"	/* 0x0200 */
> >>	    "add.l	%2,%0;"	/* 0x0201 */
> >>	    "add.l	%0,%1;"	/* 0x0205 */
> >>	    "add.l	%0,%0;"	/* 0x0402 */
> >>	    "add.l	%0,%1;"	/* 0x0607 */
> >>	    "lsl.l	#5,%0"	/* 0x8040 */
> >>				/* 0x8647 */
> 
> > Also, it took me some time to understand the hexadecimal constants
> > in the comments (and the last one predicts a future event :)).
> 
> 
> Can you recmmend a better way to comment this?  My nose is so deep
> in the code it's hard for me to judge.

I second Andreas' suggestion.

Philippe
-- 
Philippe De Muyter +32 2 6101532 Macq SA rue de l'Aeronef 2 B-1140 Bruxelles

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[Philippe De Muyter]

On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
> This provides a multiply by constant GOLDEN_RATIO_32 = 0x61C88647
> for the original mc68000, which lacks a 32x32-bit multiply instruction.
> 
> Addition chains found by Yevgen Voronenko's Hcub algorithm at
> http://spiral.ece.cmu.edu/mcm/gen.html

Shouldn't you put that reference in the comments of your archhash.h file ?

Philippe

Re: [PATCH 08/10] m68k: Add <asm/archhash.h>

[George Spelvin]

Philippe De Muyter wrote:
> On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
>> Addition chains found by Yevgen Voronenko's Hcub algorithm at
>> http://spiral.ece.cmu.edu/mcm/gen.html

> Shouldn't you put that reference in the comments of your archhash.h file ?

I don't really care either way, but generally comments show what the
code does and commit messages talk about how it was created and by whom.
That references seemed to fall into the latter category.

Rationales (*why* it does what it does) can go in both places, with the
commit message providing more room.


I have a revised set of arch/ patches including all of the suggestions
made so far, currently awaiting the requested self-test.

(I found a clean way to do it using the *value* of the HAVE_FOO define
to indicate whether the function is meant to be equivalent to the
generic one.  If it's 1, the self-test will compare the arch-specific
and generic implementations.)

[PATCH v2 08/10] m68k: Add <asm/hash.h>

[George Spelvin]

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 <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: Andreas Schwab <schwab@linux-m68k.org>
Cc: Philippe De Muyter <phdm@macq.eu>
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

diff --git a/arch/m68k/Kconfig.cpu b/arch/m68k/Kconfig.cpu
index 0dfcf128..bf3de464 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 00000000..6407af84
--- /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,<reg>" (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 */
-- 
2.8.1