[2/4] avoid computing zero offsets from NULL pointer
diff mbox series

Message ID 20200125053834.GB744673@coredump.intra.peff.net
State New
Headers show
Series
  • more clang/sanitizer fixes
Related show

Commit Message

Jeff King Jan. 25, 2020, 5:38 a.m. UTC
The Undefined Behavior Sanitizer in clang-11 seems to have learned a new
trick: it complains about computing offsets from a NULL pointer, even if
that offset is 0. This causes numerous test failures. For example, from
t1090:

  unpack-trees.c:1355:41: runtime error: applying zero offset to null pointer
  ...
  not ok 6 - in partial clone, sparse checkout only fetches needed blobs

The code in question looks like this:

  struct cache_entry **cache_end = cache + nr;
  ...
  while (cache != cache_end)

and we sometimes pass in a NULL and 0 for "cache" and "nr". This is
conceptually fine, as "cache_end" would be equal to "cache" in this
case, and we wouldn't enter the loop at all. But computing even a zero
offset violates the C standard. And given the fact that UBSan is
noticing this behavior, this might be a potential problem spot if the
compiler starts making unexpected assumptions based on undefined
behavior.

So let's just avoid it, which is pretty easy. In some cases we can just
switch to iterating with a numeric index (as we do in sequencer.c here).
In other cases (like the cache_end one) the use of an end pointer is
more natural; we can keep that by just explicitly checking for NULL when
assigning the end pointer.

Signed-off-by: Jeff King <peff@peff.net>
---
 sequencer.c       | 6 +++---
 unpack-trees.c    | 2 +-
 xdiff-interface.c | 4 ++--
 3 files changed, 6 insertions(+), 6 deletions(-)

Comments

Junio C Hamano Jan. 27, 2020, 8:03 p.m. UTC | #1
Jeff King <peff@peff.net> writes:

> switch to iterating with a numeric index (as we do in sequencer.c here).
> In other cases (like the cache_end one) the use of an end pointer is
> more natural; we can keep that by just explicitly checking for NULL when
> assigning the end pointer.
>
> diff --git a/xdiff-interface.c b/xdiff-interface.c
> index 8509f9ea22..2f1fe48512 100644
> --- a/xdiff-interface.c
> +++ b/xdiff-interface.c
> @@ -84,8 +84,8 @@ static void trim_common_tail(mmfile_t *a, mmfile_t *b)
>  {
>  	const int blk = 1024;
>  	long trimmed = 0, recovered = 0;
> -	char *ap = a->ptr + a->size;
> -	char *bp = b->ptr + b->size;
> +	char *ap = a->ptr ? a->ptr + a->size : a->ptr;
> +	char *bp = b->ptr ? b->ptr + b->size : b->ptr;
>  	long smaller = (a->size < b->size) ? a->size : b->size;
>  
>  	while (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {

Isn't it a bug for a->ptr or b->ptr to be NULL here?  Even if we
manage to assign ap = a->ptr = NULL without complaints, how would
that memcmp work?

Is it that the corresponding .size would always be 0 if .ptr is NULL
that protects us?

A bit puzzled.
Jeff King Jan. 27, 2020, 9:19 p.m. UTC | #2
On Mon, Jan 27, 2020 at 12:03:55PM -0800, Junio C Hamano wrote:

> > diff --git a/xdiff-interface.c b/xdiff-interface.c
> > index 8509f9ea22..2f1fe48512 100644
> > --- a/xdiff-interface.c
> > +++ b/xdiff-interface.c
> > @@ -84,8 +84,8 @@ static void trim_common_tail(mmfile_t *a, mmfile_t *b)
> >  {
> >  	const int blk = 1024;
> >  	long trimmed = 0, recovered = 0;
> > -	char *ap = a->ptr + a->size;
> > -	char *bp = b->ptr + b->size;
> > +	char *ap = a->ptr ? a->ptr + a->size : a->ptr;
> > +	char *bp = b->ptr ? b->ptr + b->size : b->ptr;
> >  	long smaller = (a->size < b->size) ? a->size : b->size;
> >  
> >  	while (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {
> 
> Isn't it a bug for a->ptr or b->ptr to be NULL here?  Even if we
> manage to assign ap = a->ptr = NULL without complaints, how would
> that memcmp work?
> 
> Is it that the corresponding .size would always be 0 if .ptr is NULL
> that protects us?
> 
> A bit puzzled.

Yes, that's what's happening; all of the cases in this first patch are
dealing with "NULL + 0". Which isn't to say somebody couldn't pass in an
mmfile_t with NULL and a non-zero size, but obviously that would be a
bug. Before my patch that would be a segfault, but afterwards we'd
quietly treat it as if the size were zero.

If we want to be more defensive, we could do something like this:

  /* dual inline/macro magic to avoid evaluating ptr twice but knowing
   * enough about the type of *ptr to get the size. */
  #define SAFE_END_PTR(ptr, len) safe_end_ptr(ptr, len, sizeof(*ptr))
  static inline void *safe_end_ptr(void *ptr, size_t nr, size_t elem_size)
  {
	if (!ptr) {
		if (nr)
			BUG("non-zero size coupled with NULL pointer");
		return NULL;
	}
	return (char *)ptr + nr * elem_size;
  }

  ...
  char *ap = SAFE_END_PTR(a->ptr, a->size);

I'm not sure if it's worth it, though.

Yet another alternative is to consider it a bug to use an mmfile_t with
a NULL pointer, figure out where that's being set up, and fix it.

As an aside, I also wondered whether we could run into problems with
"memcmp(NULL, ..., 0)", which is also undefined behavior. But we don't
here because the first half of the while() condition wouldn't trigger.

-Peff
Junio C Hamano Jan. 28, 2020, 6:03 p.m. UTC | #3
Jeff King <peff@peff.net> writes:

>> >  	const int blk = 1024;
>> >  	long trimmed = 0, recovered = 0;
>> > -	char *ap = a->ptr + a->size;
>> > -	char *bp = b->ptr + b->size;
>> > +	char *ap = a->ptr ? a->ptr + a->size : a->ptr;
>> > +	char *bp = b->ptr ? b->ptr + b->size : b->ptr;
>> >  	long smaller = (a->size < b->size) ? a->size : b->size;
>> >  
>> >  	while (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {
>> 
>> Isn't it a bug for a->ptr or b->ptr to be NULL here?  Even if we
>> manage to assign ap = a->ptr = NULL without complaints, how would
>> that memcmp work?
>> 
>> Is it that the corresponding .size would always be 0 if .ptr is NULL
>> that protects us?
>
> If we want to be more defensive, we could do something like this:
>
>   /* dual inline/macro magic to avoid evaluating ptr twice but knowing
>    * enough about the type of *ptr to get the size. */
>   #define SAFE_END_PTR(ptr, len) safe_end_ptr(ptr, len, sizeof(*ptr))
>   static inline void *safe_end_ptr(void *ptr, size_t nr, size_t elem_size)
>   {
> 	if (!ptr) {
> 		if (nr)
> 			BUG("non-zero size coupled with NULL pointer");
> 		return NULL;
> 	}
> 	return (char *)ptr + nr * elem_size;
>   }
>
>   ...
>   char *ap = SAFE_END_PTR(a->ptr, a->size);
>
> I'm not sure if it's worth it, though.

As long as we make it clear to those who add new callers that
any mmfile_t with .ptr==NULL must come with .size==0, it is fine.

> Yet another alternative is to consider it a bug to use an mmfile_t with
> a NULL pointer, figure out where that's being set up, and fix it.

But that would still require us to make it clear to those who add
new callers that mmfile_t with .ptr==NULL is a bug, and the current
callers must be using that as it is convenient for them, I presume,
so I think a simple comment should probably be sufficient.

> As an aside, I also wondered whether we could run into problems with
> "memcmp(NULL, ..., 0)", which is also undefined behavior. But we don't
> here because the first half of the while() condition wouldn't trigger.

Yes, although the details slightly differ ;-)

What is problematic actually is "memcmp(NULL - 1024, ..., 1024)",
which is guarded with "1024 + trimmed <= smaller &&" that will never
be true as long as "mmfile_t with .ptr==NULL must have .size==0"
holds true, right?

Thanks.
Jeff King Jan. 29, 2020, 2:31 a.m. UTC | #4
On Tue, Jan 28, 2020 at 10:03:49AM -0800, Junio C Hamano wrote:

> > I'm not sure if it's worth it, though.
> 
> As long as we make it clear to those who add new callers that
> any mmfile_t with .ptr==NULL must come with .size==0, it is fine.

TBH, I'm not sure it _is_ fine. The concept that it's safe for a ptr/len
pair to use NULL/0 is true in a lot of places, but the mmfile struct
gets used in a lot of places, much of which is xdiff code we didn't
write. I have no idea if that assumption holds everywhere.

We'd be fixing this one spot, and that's enough to make the tests happy
with UBSan. But I don't know if it's something we ought to be
recommending.

> > Yet another alternative is to consider it a bug to use an mmfile_t with
> > a NULL pointer, figure out where that's being set up, and fix it.
> 
> But that would still require us to make it clear to those who add
> new callers that mmfile_t with .ptr==NULL is a bug, and the current
> callers must be using that as it is convenient for them, I presume,
> so I think a simple comment should probably be sufficient.

Yep, but it's not much different than the hundreds of other function
interfaces we have where sometimes you can pass NULL and sometimes not.

So anyway. What do we want to do here? The fix I have? Something more
elaborate and reusable? Or perhaps just switch it to:

diff --git a/xdiff-interface.c b/xdiff-interface.c
index 3cd2ac2855..4d20069302 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c
@@ -84,8 +84,8 @@ static void trim_common_tail(mmfile_t *a, mmfile_t *b)
 {
 	const int blk = 1024;
 	long trimmed = 0, recovered = 0;
-	char *ap = a->ptr ? a->ptr + a->size : a->ptr;
-	char *bp = b->ptr ? b->ptr + b->size : b->ptr;
+	char *ap = a->size ? a->ptr + a->size : a->ptr;
+	char *bp = b->size ? b->ptr + b->size : b->ptr;
 	long smaller = (a->size < b->size) ? a->size : b->size;
 
 	while (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {

By checking "size" instead of "ptr", then we know that the addition is a
noop. And we'd continue to catch a NULL pointer mixed with a non-zero
length (as a segfault). And a non-NULL pointer with a zero length does
the right thing.

> > As an aside, I also wondered whether we could run into problems with
> > "memcmp(NULL, ..., 0)", which is also undefined behavior. But we don't
> > here because the first half of the while() condition wouldn't trigger.
> 
> Yes, although the details slightly differ ;-)
> 
> What is problematic actually is "memcmp(NULL - 1024, ..., 1024)",
> which is guarded with "1024 + trimmed <= smaller &&" that will never
> be true as long as "mmfile_t with .ptr==NULL must have .size==0"
> holds true, right?

Yes, because "smaller" would always be "0". And that part of the code
always uses a 1024-size blk, so it would never have passed "0" to memcmp
anyway.

-Peff
Junio C Hamano Jan. 29, 2020, 5:16 a.m. UTC | #5
Jeff King <peff@peff.net> writes:

> Yep, but it's not much different than the hundreds of other function
> interfaces we have where sometimes you can pass NULL and sometimes not.
>
> So anyway. What do we want to do here? The fix I have? Something more
> elaborate and reusable? Or perhaps just switch it to:

My preference was to take the patch as-is, as it was clear enough,
before seeing this one ...

> diff --git a/xdiff-interface.c b/xdiff-interface.c
> index 3cd2ac2855..4d20069302 100644
> --- a/xdiff-interface.c
> +++ b/xdiff-interface.c
> @@ -84,8 +84,8 @@ static void trim_common_tail(mmfile_t *a, mmfile_t *b)
>  {
>  	const int blk = 1024;
>  	long trimmed = 0, recovered = 0;
> -	char *ap = a->ptr ? a->ptr + a->size : a->ptr;
> -	char *bp = b->ptr ? b->ptr + b->size : b->ptr;
> +	char *ap = a->size ? a->ptr + a->size : a->ptr;
> +	char *bp = b->size ? b->ptr + b->size : b->ptr;
>  	long smaller = (a->size < b->size) ? a->size : b->size;
>  
>  	while (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {
>
> By checking "size" instead of "ptr", then we know that the addition is a
> noop. And we'd continue to catch a NULL pointer mixed with a non-zero
> length (as a segfault). And a non-NULL pointer with a zero length does
> the right thing.

which makes quite a lot of sense.
Jeff King Jan. 29, 2020, 5:46 a.m. UTC | #6
On Tue, Jan 28, 2020 at 09:16:39PM -0800, Junio C Hamano wrote:

> My preference was to take the patch as-is, as it was clear enough,
> before seeing this one ...
> [..]
> which makes quite a lot of sense.

Yeah, about an hour after I wrote it, I thought "gee, that's clearly
better than the other way; I should have done that from the start".

So here's a re-roll of the patch using that technique, with a note in
the commit message.

-- >8 --
Subject: [PATCH] avoid computing zero offsets from NULL pointer

The Undefined Behavior Sanitizer in clang-11 seems to have learned a new
trick: it complains about computing offsets from a NULL pointer, even if
that offset is 0. This causes numerous test failures. For example, from
t1090:

  unpack-trees.c:1355:41: runtime error: applying zero offset to null pointer
  ...
  not ok 6 - in partial clone, sparse checkout only fetches needed blobs

The code in question looks like this:

  struct cache_entry **cache_end = cache + nr;
  ...
  while (cache != cache_end)

and we sometimes pass in a NULL and 0 for "cache" and "nr". This is
conceptually fine, as "cache_end" would be equal to "cache" in this
case, and we wouldn't enter the loop at all. But computing even a zero
offset violates the C standard. And given the fact that UBSan is
noticing this behavior, this might be a potential problem spot if the
compiler starts making unexpected assumptions based on undefined
behavior.

So let's just avoid it, which is pretty easy. In some cases we can just
switch to iterating with a numeric index (as we do in sequencer.c here).
In other cases (like the cache_end one) the use of an end pointer is
more natural; we can keep that by just explicitly checking for the
NULL/0 case when assigning the end pointer.

Note that there are two ways you can write this latter case, checking
for the pointer:

  cache_end = cache ? cache + nr : cache;

or the size:

  cache_end = nr ? cache + nr : cache;

For the case of a NULL/0 ptr/len combo, they are equivalent. But writing
it the second way (as this patch does) has the property that if somebody
were to incorrectly pass a NULL pointer with a non-zero length, we'd
continue to notice and segfault, rather than silently pretending the
length was zero.

Signed-off-by: Jeff King <peff@peff.net>
---
 sequencer.c       | 6 +++---
 unpack-trees.c    | 2 +-
 xdiff-interface.c | 4 ++--
 3 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/sequencer.c b/sequencer.c
index b9dbf1adb0..4d31ec3296 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -588,7 +588,7 @@ static int do_recursive_merge(struct repository *r,
 	struct merge_options o;
 	struct tree *next_tree, *base_tree, *head_tree;
 	int clean;
-	char **xopt;
+	int i;
 	struct lock_file index_lock = LOCK_INIT;
 
 	if (repo_hold_locked_index(r, &index_lock, LOCK_REPORT_ON_ERROR) < 0)
@@ -608,8 +608,8 @@ static int do_recursive_merge(struct repository *r,
 	next_tree = next ? get_commit_tree(next) : empty_tree(r);
 	base_tree = base ? get_commit_tree(base) : empty_tree(r);
 
-	for (xopt = opts->xopts; xopt != opts->xopts + opts->xopts_nr; xopt++)
-		parse_merge_opt(&o, *xopt);
+	for (i = 0; i < opts->xopts_nr; i++)
+		parse_merge_opt(&o, opts->xopts[i]);
 
 	clean = merge_trees(&o,
 			    head_tree,
diff --git a/unpack-trees.c b/unpack-trees.c
index d5f4d997da..a027504b56 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -1352,7 +1352,7 @@ static int clear_ce_flags_1(struct index_state *istate,
 			    enum pattern_match_result default_match,
 			    int progress_nr)
 {
-	struct cache_entry **cache_end = cache + nr;
+	struct cache_entry **cache_end = nr ? cache + nr : cache;
 
 	/*
 	 * Process all entries that have the given prefix and meet
diff --git a/xdiff-interface.c b/xdiff-interface.c
index 8509f9ea22..99661d43c6 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c
@@ -84,8 +84,8 @@ static void trim_common_tail(mmfile_t *a, mmfile_t *b)
 {
 	const int blk = 1024;
 	long trimmed = 0, recovered = 0;
-	char *ap = a->ptr + a->size;
-	char *bp = b->ptr + b->size;
+	char *ap = a->size ? a->ptr + a->size : a->ptr;
+	char *bp = b->size ? b->ptr + b->size : b->ptr;
 	long smaller = (a->size < b->size) ? a->size : b->size;
 
 	while (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {

Patch
diff mbox series

diff --git a/sequencer.c b/sequencer.c
index b9dbf1adb0..4d31ec3296 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -588,7 +588,7 @@  static int do_recursive_merge(struct repository *r,
 	struct merge_options o;
 	struct tree *next_tree, *base_tree, *head_tree;
 	int clean;
-	char **xopt;
+	int i;
 	struct lock_file index_lock = LOCK_INIT;
 
 	if (repo_hold_locked_index(r, &index_lock, LOCK_REPORT_ON_ERROR) < 0)
@@ -608,8 +608,8 @@  static int do_recursive_merge(struct repository *r,
 	next_tree = next ? get_commit_tree(next) : empty_tree(r);
 	base_tree = base ? get_commit_tree(base) : empty_tree(r);
 
-	for (xopt = opts->xopts; xopt != opts->xopts + opts->xopts_nr; xopt++)
-		parse_merge_opt(&o, *xopt);
+	for (i = 0; i < opts->xopts_nr; i++)
+		parse_merge_opt(&o, opts->xopts[i]);
 
 	clean = merge_trees(&o,
 			    head_tree,
diff --git a/unpack-trees.c b/unpack-trees.c
index d5f4d997da..b4292d2be8 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -1352,7 +1352,7 @@  static int clear_ce_flags_1(struct index_state *istate,
 			    enum pattern_match_result default_match,
 			    int progress_nr)
 {
-	struct cache_entry **cache_end = cache + nr;
+	struct cache_entry **cache_end = cache ? cache + nr : cache;
 
 	/*
 	 * Process all entries that have the given prefix and meet
diff --git a/xdiff-interface.c b/xdiff-interface.c
index 8509f9ea22..2f1fe48512 100644
--- a/xdiff-interface.c
+++ b/xdiff-interface.c
@@ -84,8 +84,8 @@  static void trim_common_tail(mmfile_t *a, mmfile_t *b)
 {
 	const int blk = 1024;
 	long trimmed = 0, recovered = 0;
-	char *ap = a->ptr + a->size;
-	char *bp = b->ptr + b->size;
+	char *ap = a->ptr ? a->ptr + a->size : a->ptr;
+	char *bp = b->ptr ? b->ptr + b->size : b->ptr;
 	long smaller = (a->size < b->size) ? a->size : b->size;
 
 	while (blk + trimmed <= smaller && !memcmp(ap - blk, bp - blk, blk)) {