threads / patch / 39522

patchindex-pack: fix truncation of off_t in comparison

Subject: [PATCH] index-pack: fix truncation of off_t in comparison

## tl;dr

3 messages between Jun 4, 2015 and Jun 4, 2015. Diffs are folded; open one to read it.

replies: 2people: 3as markdown or json

Jeff King· Jun 4, 2015, 12:35 UTC · lore

Commit c6458e6 (index-pack: kill union delta_base to save memory, 2015-04-18) refactored the comparison functions used in sorting and binary searching our delta list. The resulting code does something like:

  int cmp_offsets(off_t a, off_t b)
  {
	  return a - b;
  }

This works most of the time, but produces nonsensical results when the difference between the two offsets is larger than what can be stored in an "int". This can lead to unresolved deltas if the packsize is larger than 2G (even on 64-bit systems, an int is still typically 32 bits):

  $ git clone git://github.com/mozilla/gecko-dev
  Cloning into 'gecko-dev'...
  remote: Counting objects: 4800161, done.
  remote: Compressing objects: 100% (178/178), done.
  remote: Total 4800161 (delta 88), reused 0 (delta 0), pack-reused 4799978
  Receiving objects: 100% (4800161/4800161), 2.21 GiB | 3.26 MiB/s, done.
  Resolving deltas:  99% (3808820/3811944), completed with 0 local objects.
  fatal: pack has 3124 unresolved deltas
  fatal: index-pack failed

We can fix it by doing direct comparisons between the offsets and returning constants; the callers only care about the sign of the comparison, not the magnitude.

Signed-off-by: Jeff King <peff@peff.net>
---
On top of nd/slim-index-pack-memory-usage, which introduced the bug (but
it is already in master).

 builtin/index-pack.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

Show changes to builtin/index-pack.c +6 −2

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 3ed53e3..06dd973 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -616,7 +616,9 @@ static int compare_ofs_delta_bases(off_t offset1, off_t offset2,
 	int cmp = type1 - type2;
 	if (cmp)
 		return cmp;
-	return offset1 - offset2;
+	return offset1 < offset2 ? -1 :
+	       offset1 > offset2 ?  1 :
+	       0;
 }
 
 static int find_ofs_delta(const off_t offset, enum object_type type)
@@ -1051,7 +1053,9 @@ static int compare_ofs_delta_entry(const void *a, const void *b)
 	const struct ofs_delta_entry *delta_a = a;
 	const struct ofs_delta_entry *delta_b = b;
 
-	return delta_a->offset - delta_b->offset;
+	return delta_a->offset < delta_b->offset ? -1 :
+	       delta_a->offset > delta_b->offset ?  1 :
+	       0;
 }
 
 static int compare_ref_delta_entry(const void *a, const void *b)

-- 
2.4.2.745.g0aa058d

Duy Nguyen· Jun 4, 2015, 13:10 UTC · re: Jeff King · lore

Re: [PATCH] index-pack: fix truncation of off_t in comparison

On Thu, Jun 4, 2015 at 7:35 PM, Jeff King <peff@peff.net> wrote:

Show 13 quoted lines

> Commit c6458e6 (index-pack: kill union delta_base to save
> memory, 2015-04-18) refactored the comparison functions used
> in sorting and binary searching our delta list. The
> resulting code does something like:
>
>   int cmp_offsets(off_t a, off_t b)
>   {
>           return a - b;
>   }
>
> This works most of the time, but produces nonsensical
> results when the difference between the two offsets is
> larger than what can be stored in an "int".

Ugh.. thanks for fixing this. Too bad neither gcc, clang or coverity spotted this.

-- 
Duy

Junio C Hamano· Jun 4, 2015, 17:28 UTC · re: Jeff King · lore

Re: [PATCH] index-pack: fix truncation of off_t in comparison

Jeff King <peff@peff.net> writes:

> On top of nd/slim-index-pack-memory-usage, which introduced the bug (but
> it is already in master).

Thanks.

In this round, I decided to deliberately merge more iffy and larger topics to 'master' in early part of the cycle, and it seems to be paying off nicely ;-).

Will queue.

Show 29 quoted lines

>  builtin/index-pack.c | 8 ++++++--
>  1 file changed, 6 insertions(+), 2 deletions(-)
>
> diff --git a/builtin/index-pack.c b/builtin/index-pack.c
> index 3ed53e3..06dd973 100644
> --- a/builtin/index-pack.c
> +++ b/builtin/index-pack.c
> @@ -616,7 +616,9 @@ static int compare_ofs_delta_bases(off_t offset1, off_t offset2,
>  	int cmp = type1 - type2;
>  	if (cmp)
>  		return cmp;
> -	return offset1 - offset2;
> +	return offset1 < offset2 ? -1 :
> +	       offset1 > offset2 ?  1 :
> +	       0;
>  }
>  
>  static int find_ofs_delta(const off_t offset, enum object_type type)
> @@ -1051,7 +1053,9 @@ static int compare_ofs_delta_entry(const void *a, const void *b)
>  	const struct ofs_delta_entry *delta_a = a;
>  	const struct ofs_delta_entry *delta_b = b;
>  
> -	return delta_a->offset - delta_b->offset;
> +	return delta_a->offset < delta_b->offset ? -1 :
> +	       delta_a->offset > delta_b->offset ?  1 :
> +	       0;
>  }
>  
>  static int compare_ref_delta_entry(const void *a, const void *b)