threads / patch / 44581

patchDefine XDL_FAST_HASH when building *for* (not *on*) x86_64

Subject: [PATCH] Define XDL_FAST_HASH when building *for* (not *on*) x86_64

## tl;dr

4 messages between Dec 1, 2016 and Dec 1, 2016. Diffs are folded; open one to read it.

replies: 3people: 2as markdown or json

Anders Kaseorg· Dec 1, 2016, 03:04 UTC · lore

Previously, XDL_FAST_HASH was defined when ‘uname -m’ returns x86_64, even if we are cross-compiling for a different architecture. Check the __x86_64__ compiler macro instead.

In addition to fixing the cross compilation bug, this is needed to pass the Debian build reproducibility test (https://tests.reproducible-builds.org/debian/index_variations.html).

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
---
 config.mak.uname | 5 -----
 xdiff/xutils.c   | 4 ++++
 2 files changed, 4 insertions(+), 5 deletions(-)
Show changes to 2 files +4 −5

config.mak.uname, xdiff/xutils.c

diff --git a/config.mak.uname b/config.mak.uname
index b232908f8..2831a68c3 100644
--- a/config.mak.uname
+++ b/config.mak.uname
@@ -1,10 +1,8 @@
 # Platform specific Makefile tweaks based on uname detection
 
 uname_S := $(shell sh -c 'uname -s 2>/dev/null || echo not')
-uname_M := $(shell sh -c 'uname -m 2>/dev/null || echo not')
 uname_O := $(shell sh -c 'uname -o 2>/dev/null || echo not')
 uname_R := $(shell sh -c 'uname -r 2>/dev/null || echo not')
-uname_P := $(shell sh -c 'uname -p 2>/dev/null || echo not')
 uname_V := $(shell sh -c 'uname -v 2>/dev/null || echo not')
 
 ifdef MSVC
@@ -17,9 +15,6 @@ endif
 # because maintaining the nesting to match is a pain.  If
 # we had "elif" things would have been much nicer...
 
-ifeq ($(uname_M),x86_64)
-	XDL_FAST_HASH = YesPlease
-endif
 ifeq ($(uname_S),OSF1)
 	# Need this for u_short definitions et al
 	BASIC_CFLAGS += -D_OSF_SOURCE
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 027192a1c..f46351fe4 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -264,6 +264,10 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,
 	return ha;
 }
 
+#ifdef __x86_64__
+#define XDL_FAST_HASH
+#endif
+
 #ifdef XDL_FAST_HASH
 
 #define REPEAT_BYTE(x)  ((~0ul / 0xff) * (x))

-- 
2.11.0
Jeff King· Dec 1, 2016, 03:56 UTC · re: Anders Kaseorg · lore

Re: [PATCH] Define XDL_FAST_HASH when building *for* (not *on*) x86_64

On Wed, Nov 30, 2016 at 10:04:07PM -0500, Anders Kaseorg wrote:
Show 7 quoted lines
> Previously, XDL_FAST_HASH was defined when ‘uname -m’ returns x86_64,
> even if we are cross-compiling for a different architecture.  Check
> the __x86_64__ compiler macro instead.
> 
> In addition to fixing the cross compilation bug, this is needed to
> pass the Debian build reproducibility test
> (https://tests.reproducible-builds.org/debian/index_variations.html).

I don't think this is a good approach to fix it. Right now XDL_FAST_HASH is a Makefile knob that can be turned by the user, and can be used either to explicitly enable or explicitly disable the feature.

With your patch, building with "make XDL_FAST_HASH=Yes" will still explicitly enable it, but "make XDL_FAST_HASH=" would no longer disable it (because even if unset, the compiler would turn it on when it sees __x86_64__).

And being able to turn it off is important; more on that in a second.

So I think if we wanted to auto-detect based on __x86_64__, we'd probably need to be able to set it to "auto" or something, and then

  #if defined(XDL_FAST_HASH_AUTO) && __x86_64__
  #define XDL_FAST_HASH
  #endif
or something.

However, I think this might be the tip of the iceberg. There are lots of Makefile knobs whose defaults are tweaked based on uname output. This one caught you because you are cross-compiling across architectures, but in theory you could cross-compile for FreeBSD from Linux, or whatever.

So I suspect a better strategy in general is to just override the uname_* variables when cross-compiling.

All that being said, I actually think an easier fix for this particular case might be to drop XDL_FAST_HASH entirely. It computes the hashes slightly faster, but its collision characteristics are much worse. About 2 years ago I ran across a pathological diff that ran over 100x slower with XDL_FAST_HASH:

  http://public-inbox.org/git/20141222041944.GA441@peff.net/

The discussion veered into whether we should have a randomized hash secured against DoS attacks. I played around with some alternatives, but never found anything quite as fast for the "normal" case. And having disabled XDL_FAST_HASH on GitHub's servers, it wasn't a big priority for me.

I'd be happy if somebody wanted to investigate other hash functions further. But barring that, I think we should drop XDL_FAST_HASH (or at the very least stop turning it on by default) in the meantime. It's just not a good tradeoff.

-Peff
Jeff King· Dec 1, 2016, 03:59 UTC · re: Anders Kaseorg · lore

Re: [PATCH] Define XDL_FAST_HASH when building *for* (not *on*) x86_64

[resend; the original had an outdated address for Thomas, and I would
 definitely like his blessing before removing XDL_FAST_HASH].
On Wed, Nov 30, 2016 at 10:04:07PM -0500, Anders Kaseorg wrote:
Show 7 quoted lines
> Previously, XDL_FAST_HASH was defined when ‘uname -m’ returns x86_64,
> even if we are cross-compiling for a different architecture.  Check
> the __x86_64__ compiler macro instead.
> 
> In addition to fixing the cross compilation bug, this is needed to
> pass the Debian build reproducibility test
> (https://tests.reproducible-builds.org/debian/index_variations.html).

I don't think this is a good approach to fix it. Right now XDL_FAST_HASH is a Makefile knob that can be turned by the user, and can be used either to explicitly enable or explicitly disable the feature.

With your patch, building with "make XDL_FAST_HASH=Yes" will still explicitly enable it, but "make XDL_FAST_HASH=" would no longer disable it (because even if unset, the compiler would turn it on when it sees __x86_64__).

And being able to turn it off is important; more on that in a second.

So I think if we wanted to auto-detect based on __x86_64__, we'd probably need to be able to set it to "auto" or something, and then

  #if defined(XDL_FAST_HASH_AUTO) && __x86_64__
  #define XDL_FAST_HASH
  #endif
or something.

However, I think this might be the tip of the iceberg. There are lots of Makefile knobs whose defaults are tweaked based on uname output. This one caught you because you are cross-compiling across architectures, but in theory you could cross-compile for FreeBSD from Linux, or whatever.

So I suspect a better strategy in general is to just override the uname_* variables when cross-compiling.

All that being said, I actually think an easier fix for this particular case might be to drop XDL_FAST_HASH entirely. It computes the hashes slightly faster, but its collision characteristics are much worse. About 2 years ago I ran across a pathological diff that ran over 100x slower with XDL_FAST_HASH:

  http://public-inbox.org/git/20141222041944.GA441@peff.net/

The discussion veered into whether we should have a randomized hash secured against DoS attacks. I played around with some alternatives, but never found anything quite as fast for the "normal" case. And having disabled XDL_FAST_HASH on GitHub's servers, it wasn't a big priority for me.

I'd be happy if somebody wanted to investigate other hash functions further. But barring that, I think we should drop XDL_FAST_HASH (or at the very least stop turning it on by default) in the meantime. It's just not a good tradeoff.

-Peff
Anders Kaseorg· Dec 1, 2016, 04:30 UTC · re: Jeff King · lore

[PATCH] xdiff: Do not enable XDL_FAST_HASH by default

Although XDL_FAST_HASH computes hashes slightly faster on some architectures, its collision characteristics are much worse, resulting in some pathological diffs running over 100x slower (http://public-inbox.org/git/20141222041944.GA441@peff.net/).

Furthermore, it was being enabled when ‘uname -m’ returns x86_64, even if we are cross-compiling for a different architecture. This mistake was also causing the Debian build reproducibility test to fail (https://tests.reproducible-builds.org/debian/index_variations.html). Future architecture-specific definitions should be based on compiler macros such as __x86_64__ rather than uname.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
---

[Oops, also resending for Thomas’s new email address. Sorry for the spam.]

On Wed, 30 Nov 2016, Jeff King wrote:
Show 7 quoted lines
> However, I think this might be the tip of the iceberg. There are lots of
> Makefile knobs whose defaults are tweaked based on uname output. This
> one caught you because you are cross-compiling across architectures, but
> in theory you could cross-compile for FreeBSD from Linux, or whatever.
> 
> So I suspect a better strategy in general is to just override the
> uname_* variables when cross-compiling.

The specific case of an i386 userspace on an x86_64 kernel is important independently of the general cross compilation problem (in fact, the words “cross compilation” may not even really apply here). And I don’t think one should have to manually tweak the build for this setup, especially since the compiler already has the needed information.

> All that being said, I actually think an easier fix for this particular
> case might be to drop XDL_FAST_HASH entirely.
Works for me.
Anders
 Makefile         | 1 -
 config.mak.uname | 5 -----
 2 files changed, 6 deletions(-)
Show changes to 2 files +0 −6

Makefile, config.mak.uname

diff --git a/Makefile b/Makefile
index f53fcc90d..c237d4f91 100644
--- a/Makefile
+++ b/Makefile
@@ -341,7 +341,6 @@ all::
 # Define XDL_FAST_HASH to use an alternative line-hashing method in
 # the diff algorithm.  It gives a nice speedup if your processor has
 # fast unaligned word loads.  Does NOT work on big-endian systems!
-# Enabled by default on x86_64.
 #
 # Define GIT_USER_AGENT if you want to change how git identifies itself during
 # network interactions.  The default is "git/$(GIT_VERSION)".
diff --git a/config.mak.uname b/config.mak.uname
index b232908f8..2831a68c3 100644
--- a/config.mak.uname
+++ b/config.mak.uname
@@ -1,10 +1,8 @@
 # Platform specific Makefile tweaks based on uname detection
 
 uname_S := $(shell sh -c 'uname -s 2>/dev/null || echo not')
-uname_M := $(shell sh -c 'uname -m 2>/dev/null || echo not')
 uname_O := $(shell sh -c 'uname -o 2>/dev/null || echo not')
 uname_R := $(shell sh -c 'uname -r 2>/dev/null || echo not')
-uname_P := $(shell sh -c 'uname -p 2>/dev/null || echo not')
 uname_V := $(shell sh -c 'uname -v 2>/dev/null || echo not')
 
 ifdef MSVC
@@ -17,9 +15,6 @@ endif
 # because maintaining the nesting to match is a pain.  If
 # we had "elif" things would have been much nicer...
 
-ifeq ($(uname_M),x86_64)
-	XDL_FAST_HASH = YesPlease
-endif
 ifeq ($(uname_S),OSF1)
 	# Need this for u_short definitions et al
 	BASIC_CFLAGS += -D_OSF_SOURCE

-- 
2.11.0

← back to recent threads