[PATCH 0/2] compiling with -fsanitize=undefined

[PATCH 0/2] compiling with -fsanitize=undefined

[Jeff King]

I was playing around with the new-ish "-fsanitize=undefined" compiler
flag, and it detected a few problems:

  1. We sometimes bit-shift signed constants too far (fixed by the first
     patch).

  2. We have some unaligned memory accesses that presumably work OK on
     x86, but would blow up on ARM or other platforms (I didn't test).

The latter looks like it's in the untracked cache code (Duy and
Christian cc'd). Running t7063 gets me this:

dir.c:2631:45: runtime error: member access within misaligned address 0x7f19806ff185 for type 'const struct ondisk_untracked_cache', which requires 4 byte alignment
0x7f19806ff185: note: pointer points here
 31 33 29 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00
             ^

We also do unaligned loads in the get_be* functions, but only on x86 and
similar platforms.  I'm counting these as a false positive, since it is
presumably OK there. The second patch makes it easier to squelch these.

I also got false positives from feeding NULL to qsort(). This is
technically wrong, but OK in practice when we tell it we have zero
elements. Compiling with INTERNAL_QSORT silences these (and if somebody
is on a platform where their qsort() segfaults, it's what I'd tell them
to use).

So if you want to play along at home, my build is something like:

  make \
    CC=clang \
    INTERNAL_QSORT=YesPlease \
    CFLAGS='-O2 -g -fsanitize=undefined -fno-sanitize-recover=undefined -DNO_UNALIGNED_LOADS' \
    test

and it passes except for t7063.

The patches are:

  [1/2]: avoid shifting signed integers 31 bits
  [2/2]: bswap: add NO_UNALIGNED_LOADS define

-Peff

[PATCH 1/2] avoid shifting signed integers 31 bits

[Jeff King]

We sometimes use 32-bit unsigned integers as bit-fields.
It's fine to access the MSB, because it's unsigned. However,
doing so as "1 << 31" is wrong, because the constant "1" is
a signed int, and we shift into the sign bit, causing
undefined behavior.

We can fix this by using "1U" as the constant.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c | 2 +-
 diff.h                 | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index ca38131..2b3b746 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -1618,7 +1618,7 @@ static void prepare_shallow_update(struct command *commands,
 				continue;
 			si->need_reachability_test[i]++;
 			for (k = 0; k < 32; k++)
-				if (si->used_shallow[i][j] & (1 << k))
+				if (si->used_shallow[i][j] & (1U << k))
 					si->shallow_ref[j * 32 + k]++;
 		}
 
diff --git a/diff.h b/diff.h
index f7208ad..893f446 100644
--- a/diff.h
+++ b/diff.h
@@ -91,7 +91,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)
 #define DIFF_OPT_DIRSTAT_BY_LINE     (1 << 28)
 #define DIFF_OPT_FUNCCONTEXT         (1 << 29)
 #define DIFF_OPT_PICKAXE_IGNORE_CASE (1 << 30)
-#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1 << 31)
+#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1U << 31)
 
 #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
 #define DIFF_OPT_TOUCHED(opts, flag)    ((opts)->touched_flags & DIFF_OPT_##flag)
-- 
2.7.0.rc2.368.g1cbb535

[PATCH 2/2] bswap: add NO_UNALIGNED_LOADS define

[Jeff King]

The byte-swapping code automatically decides, based on the
platform, whether it is sensible to cast an do a potentially
unaligned ntohl(), or to pick individual bytes out of an
array.

It can be handy to override this decision, though, when
turning on compiler flags that will complain about unaligned
loads (such as -fsanitize=undefined). This patch adds a
macro check to make this possible.

There's no nice Makefile knob here; this is for prodding at
Git's internals, and anybody using it can set
"-DNO_UNALIGNED_LOADS" in the same place they are setting up
"-fsanitize".

Signed-off-by: Jeff King <peff@peff.net>
---
 compat/bswap.h | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/compat/bswap.h b/compat/bswap.h
index 7fed637..d47c003 100644
--- a/compat/bswap.h
+++ b/compat/bswap.h
@@ -149,11 +149,12 @@ static inline uint64_t git_bswap64(uint64_t x)
  * and is faster on architectures with memory alignment issues.
  */
 
-#if defined(__i386__) || defined(__x86_64__) || \
+#if !defined(NO_UNALIGNED_LOADS) && ( \
+    defined(__i386__) || defined(__x86_64__) || \
     defined(_M_IX86) || defined(_M_X64) || \
     defined(__ppc__) || defined(__ppc64__) || \
     defined(__powerpc__) || defined(__powerpc64__) || \
-    defined(__s390__) || defined(__s390x__)
+    defined(__s390__) || defined(__s390x__))
 
 #define get_be16(p)	ntohs(*(unsigned short *)(p))
 #define get_be32(p)	ntohl(*(unsigned int *)(p))
-- 
2.7.0.rc2.368.g1cbb535

Re: [PATCH 2/2] bswap: add NO_UNALIGNED_LOADS define

[Eric Sunshine]

On Tue, Dec 29, 2015 at 1:36 AM, Jeff King <peff@peff.net> wrote:
> The byte-swapping code automatically decides, based on the
> platform, whether it is sensible to cast an do a potentially

s/an/and/ or something?

> unaligned ntohl(), or to pick individual bytes out of an
> array.
>
> It can be handy to override this decision, though, when
> turning on compiler flags that will complain about unaligned
> loads (such as -fsanitize=undefined). This patch adds a
> macro check to make this possible.
>
> There's no nice Makefile knob here; this is for prodding at
> Git's internals, and anybody using it can set
> "-DNO_UNALIGNED_LOADS" in the same place they are setting up
> "-fsanitize".
>
> Signed-off-by: Jeff King <peff@peff.net>

Re: [PATCH 0/2] compiling with -fsanitize=undefined

[Jeff King]

On Tue, Dec 29, 2015 at 01:34:49AM -0500, Jeff King wrote:

>   2. We have some unaligned memory accesses that presumably work OK on
>      x86, but would blow up on ARM or other platforms (I didn't test).
> 
> The latter looks like it's in the untracked cache code (Duy and
> Christian cc'd). Running t7063 gets me this:
> 
> dir.c:2631:45: runtime error: member access within misaligned address 0x7f19806ff185 for type 'const struct ondisk_untracked_cache', which requires 4 byte alignment
> 0x7f19806ff185: note: pointer points here
>  31 33 29 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00
>              ^

I took a brief look at fixing this, and it may actually be a false
positive, as well (in a manner of speaking; if the compiler thinks it is
undefined behavior, it may still be worth fixing so we don't fall prey
to some optimizations-gone-wild).

The line in question is:

  load_sha1_stat(&uc->ss_info_exclude, &ouc->info_exclude_stat,
		 ouc->info_exclude_sha1);

where "ouc" is the on-disk data cast to a struct. So we definitely
generate an unaligned pointer, but then we only access its contents via
get_be32(), which handles alignment. So it might actually be OK. I
dunno.

-Peff

Re: [PATCH 2/2] bswap: add NO_UNALIGNED_LOADS define

[Jeff King]

On Tue, Dec 29, 2015 at 01:42:45AM -0500, Eric Sunshine wrote:

> On Tue, Dec 29, 2015 at 1:36 AM, Jeff King <peff@peff.net> wrote:
> > The byte-swapping code automatically decides, based on the
> > platform, whether it is sensible to cast an do a potentially
> 
> s/an/and/ or something?

Yes, it should be "and". Thanks.

-Peff

Re: [PATCH 1/2] avoid shifting signed integers 31 bits

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> diff --git a/diff.h b/diff.h
> index f7208ad..893f446 100644
> --- a/diff.h
> +++ b/diff.h
> @@ -91,7 +91,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)
>  #define DIFF_OPT_DIRSTAT_BY_LINE     (1 << 28)
>  #define DIFF_OPT_FUNCCONTEXT         (1 << 29)
>  #define DIFF_OPT_PICKAXE_IGNORE_CASE (1 << 30)
> -#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1 << 31)
> +#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1U << 31)
>  
>  #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
>  #define DIFF_OPT_TOUCHED(opts, flag)    ((opts)->touched_flags & DIFF_OPT_##flag)

Thanks.

Seeing (1 << 30) and (1U <<31) together made me feel that we are way
_too_ explicit being careful about 32-bit archs (iow, it would be
more consistent to turn all of these "1 <<" into "1U <<"), but at
the same time, (1 << 30) won't be broken unless we are on 31-bit
arch in the sense that if we are on 30-bit or smaller arch the
expression is already broken with or without "U", and if we are on
32-bit or more, then with or without "U" we are OK---which made me
feel somewhat funny.

In any case, these two are good changes.  Thanks.

Re: [PATCH 1/2] avoid shifting signed integers 31 bits

[Jeff King]

On Tue, Dec 29, 2015 at 04:09:21PM -0800, Junio C Hamano wrote:

> > diff --git a/diff.h b/diff.h
> > index f7208ad..893f446 100644
> > --- a/diff.h
> > +++ b/diff.h
> > @@ -91,7 +91,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)
> >  #define DIFF_OPT_DIRSTAT_BY_LINE     (1 << 28)
> >  #define DIFF_OPT_FUNCCONTEXT         (1 << 29)
> >  #define DIFF_OPT_PICKAXE_IGNORE_CASE (1 << 30)
> > -#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1 << 31)
> > +#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1U << 31)
> >  
> >  #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
> >  #define DIFF_OPT_TOUCHED(opts, flag)    ((opts)->touched_flags & DIFF_OPT_##flag)
> 
> Thanks.
> 
> Seeing (1 << 30) and (1U <<31) together made me feel that we are way
> _too_ explicit being careful about 32-bit archs (iow, it would be
> more consistent to turn all of these "1 <<" into "1U <<"), but at
> the same time, (1 << 30) won't be broken unless we are on 31-bit
> arch in the sense that if we are on 30-bit or smaller arch the
> expression is already broken with or without "U", and if we are on
> 32-bit or more, then with or without "U" we are OK---which made me
> feel somewhat funny.

Yeah, I was tempted to convert them all, but there's no benefit except
consistency. Interestingly, if we spelled these as:

  0x01
  0x02
  ...
  0x80000000

that _is_ OK by the C standard (the type of the constant is "the first
thing big enough to hold it" from a list of int, unsigned, etc[1]). I find
that style more error-prone, though, so I don't think it's a good idea
to move to it.

We pretty much assume an int of at least 32-bits anyway; the flags field
itself is a simple "unsigned". We could make that a uint32_t, but in
practice I hope that sub-32-bit platforms are all dead, at least for
general purpose application code like git.

-Peff

[1] The list of possible types is actually _different_ for decimal and
    hex constants. Which seems slightly insane, but hey, it's C.
    Notably, the decimal equivalent of 0x80000000 is guaranteed to be
    signed (but would be a "long int" on a 32-bit platform).

Re: [PATCH 1/2] avoid shifting signed integers 31 bits

[Duy Nguyen]

On Tue, Dec 29, 2015 at 1:35 PM, Jeff King <peff@peff.net> wrote:
> We sometimes use 32-bit unsigned integers as bit-fields.
> It's fine to access the MSB, because it's unsigned. However,
> doing so as "1 << 31" is wrong, because the constant "1" is
> a signed int, and we shift into the sign bit, causing
> undefined behavior.
>
> We can fix this by using "1U" as the constant.

We have this in cache.h, should it be fixed as well?

/* CE_EXTENDED2 is for future extension */
#define CE_EXTENDED2         (1 << 31)
-- 
Duy

Re: [PATCH 1/2] avoid shifting signed integers 31 bits

[Jeff King]

On Thu, Dec 31, 2015 at 12:10:33PM +0700, Duy Nguyen wrote:

> On Tue, Dec 29, 2015 at 1:35 PM, Jeff King <peff@peff.net> wrote:
> > We sometimes use 32-bit unsigned integers as bit-fields.
> > It's fine to access the MSB, because it's unsigned. However,
> > doing so as "1 << 31" is wrong, because the constant "1" is
> > a signed int, and we shift into the sign bit, causing
> > undefined behavior.
> >
> > We can fix this by using "1U" as the constant.
> 
> We have this in cache.h, should it be fixed as well?
> 
> /* CE_EXTENDED2 is for future extension */
> #define CE_EXTENDED2         (1 << 31)

Sort of. We don't actually use it, and since it's a macro, that means it
never even hits the compiler proper itself. So it's not a bug, but it's
a bug waiting to happen. :)

-Peff

Re: [PATCH 1/2] avoid shifting signed integers 31 bits

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Thu, Dec 31, 2015 at 12:10:33PM +0700, Duy Nguyen wrote:
>
>> On Tue, Dec 29, 2015 at 1:35 PM, Jeff King <peff@peff.net> wrote:
>> > We sometimes use 32-bit unsigned integers as bit-fields.
>> > It's fine to access the MSB, because it's unsigned. However,
>> > doing so as "1 << 31" is wrong, because the constant "1" is
>> > a signed int, and we shift into the sign bit, causing
>> > undefined behavior.
>> >
>> > We can fix this by using "1U" as the constant.
>> 
>> We have this in cache.h, should it be fixed as well?
>> 
>> /* CE_EXTENDED2 is for future extension */
>> #define CE_EXTENDED2         (1 << 31)
>
> Sort of. We don't actually use it, and since it's a macro, that means it
> never even hits the compiler proper itself. So it's not a bug, but it's
> a bug waiting to happen. :)
>
> -Peff

Let's squash an obvious change for that in to 1/2, then, before I
merge the series to 'next'.

Thanks.

-- >8 --
From: Jeff King <peff@peff.net>
Date: Tue, 29 Dec 2015 01:35:46 -0500
Subject: [PATCH] avoid shifting signed integers 31 bits

We sometimes use 32-bit unsigned integers as bit-fields.
It's fine to access the MSB, because it's unsigned. However,
doing so as "1 << 31" is wrong, because the constant "1" is
a signed int, and we shift into the sign bit, causing
undefined behavior.

We can fix this by using "1U" as the constant.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/receive-pack.c | 2 +-
 cache.h                | 2 +-
 diff.h                 | 2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index e6b93d0..e35ed40 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -1597,7 +1597,7 @@ static void prepare_shallow_update(struct command *commands,
 				continue;
 			si->need_reachability_test[i]++;
 			for (k = 0; k < 32; k++)
-				if (si->used_shallow[i][j] & (1 << k))
+				if (si->used_shallow[i][j] & (1U << k))
 					si->shallow_ref[j * 32 + k]++;
 		}
 
diff --git a/cache.h b/cache.h
index 6f53962..9088843 100644
--- a/cache.h
+++ b/cache.h
@@ -214,7 +214,7 @@ struct cache_entry {
 #define CE_INTENT_TO_ADD     (1 << 29)
 #define CE_SKIP_WORKTREE     (1 << 30)
 /* CE_EXTENDED2 is for future extension */
-#define CE_EXTENDED2         (1 << 31)
+#define CE_EXTENDED2         (1U << 31)
 
 #define CE_EXTENDED_FLAGS (CE_INTENT_TO_ADD | CE_SKIP_WORKTREE)
 
diff --git a/diff.h b/diff.h
index f7208ad..893f446 100644
--- a/diff.h
+++ b/diff.h
@@ -91,7 +91,7 @@ typedef struct strbuf *(*diff_prefix_fn_t)(struct diff_options *opt, void *data)
 #define DIFF_OPT_DIRSTAT_BY_LINE     (1 << 28)
 #define DIFF_OPT_FUNCCONTEXT         (1 << 29)
 #define DIFF_OPT_PICKAXE_IGNORE_CASE (1 << 30)
-#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1 << 31)
+#define DIFF_OPT_DEFAULT_FOLLOW_RENAMES (1U << 31)
 
 #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
 #define DIFF_OPT_TOUCHED(opts, flag)    ((opts)->touched_flags & DIFF_OPT_##flag)
-- 
2.7.0-rc3-132-g73ad441

Re: [PATCH 1/2] avoid shifting signed integers 31 bits

[Jeff King]

On Mon, Jan 04, 2016 at 09:52:10AM -0800, Junio C Hamano wrote:

> >> We have this in cache.h, should it be fixed as well?
> >> 
> >> /* CE_EXTENDED2 is for future extension */
> >> #define CE_EXTENDED2         (1 << 31)
> >
> > Sort of. We don't actually use it, and since it's a macro, that means it
> > never even hits the compiler proper itself. So it's not a bug, but it's
> > a bug waiting to happen. :)
> >
> 
> Let's squash an obvious change for that in to 1/2, then, before I
> merge the series to 'next'.

Thanks, I agree it is worth fixing while we're visiting the topic.

-Peff