git 1.9.0 segfault

git 1.9.0 segfault

[Guillaume Gelin]

Hi,

http://pastebin.com/Np7L54ar

Cheers,

-- 
Guillaume Gelin

Re: git 1.9.0 segfault

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 2610 bytes --]

On Sat, Mar 08, 2014 at 04:23:43PM +0000, Guillaume Gelin wrote:
> Hi,
>
> http://pastebin.com/Np7L54ar

I can confirm this.  I get the following backtrace:

  Core was generated by `/home/bmc/checkouts/git/git mv packages/ lisp'.
  Program terminated with signal 11, Segmentation fault.
  #0  0x00007fe31a4371b2 in _IO_vfprintf_internal (s=s@entry=0x7fffa330d2e0, format=<optimized out>, format@entry=0x7fffa330e5b0 "renaming '%s' failed: Bad address", ap=ap@entry=0x7fffa330e498)
      at vfprintf.c:1649
  1649	vfprintf.c: No such file or directory.
  (gdb) bt
  #0  0x00007fe31a4371b2 in _IO_vfprintf_internal (s=s@entry=0x7fffa330d2e0, format=<optimized out>, format@entry=0x7fffa330e5b0 "renaming '%s' failed: Bad address", ap=ap@entry=0x7fffa330e498)
      at vfprintf.c:1649
  #1  0x00007fe31a4e2315 in ___vsnprintf_chk (s=s@entry=0x7fffa330d450 "renaming '0\243\377\177", maxlen=<optimized out>, maxlen@entry=4096, flags=flags@entry=1, slen=slen@entry=4096,
      format=0x7fffa330e5b0 "renaming '%s' failed: Bad address", format@entry=0x544fe5 "fatal: ", args=0x7fffa330e498) at vsnprintf_chk.c:63
  #2  0x00000000005041cb in vsnprintf (__ap=<optimized out>, __fmt=0x544fe5 "fatal: ", __n=4096, __s=0x7fffa330d450 "renaming '0\243\377\177") at /usr/include/x86_64-linux-gnu/bits/stdio2.h:77
  #3  vreportf (prefix=prefix@entry=0x544fe5 "fatal: ", err=<optimized out>, params=<optimized out>) at usage.c:12
  #4  0x0000000000504224 in die_builtin (err=<optimized out>, params=<optimized out>) at usage.c:36
  #5  0x0000000000504650 in die_errno (fmt=0x52be9a "renaming '%s' failed") at usage.c:137
  #6  0x000000000044cb4d in cmd_mv (argc=<optimized out>, argv=<optimized out>, prefix=<optimized out>) at builtin/mv.c:246
  #7  0x000000000040602d in run_builtin (argv=0x7fffa330ef90, argc=3, p=0x779d40 <commands+1536>) at git.c:314
  #8  handle_builtin (argc=3, argv=0x7fffa330ef90) at git.c:487
  #9  0x00000000004052e1 in run_argv (argv=0x7fffa330ee48, argcp=0x7fffa330ee2c) at git.c:533
  #10 main (argc=3, av=<optimized out>) at git.c:616

We're failing to rename because we got an EFAULT, and then we try to
print the failing filename, and we get a segfault right here:

			if (rename(src, dst) < 0 && !ignore_errors)
				die_errno (_("renaming '%s' failed"), src);

I don't know yet if dst is also bad, but clearly src is.  I'm looking
into it.

-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: git 1.9.0 segfault

[John Keeping]

On Sat, Mar 08, 2014 at 04:46:51PM +0000, brian m. carlson wrote:
> On Sat, Mar 08, 2014 at 04:23:43PM +0000, Guillaume Gelin wrote:
> > Hi,
> >
> > http://pastebin.com/Np7L54ar
> We're failing to rename because we got an EFAULT, and then we try to
> print the failing filename, and we get a segfault right here:
> 
> 			if (rename(src, dst) < 0 && !ignore_errors)
> 				die_errno (_("renaming '%s' failed"), src);
> 
> I don't know yet if dst is also bad, but clearly src is.  I'm looking
> into it.

The problem seems to be that we change argc when we append nested
directories to the list and then continue looping over 'source' which
has been realloc'd to be larger.  But we do not realloc
submodule_gitfile at the same time so we start writing beyond the end of
the submodule_gitfile array.

The particular behaviour of glibc's malloc happens to mean (at least on
my system) that this starts overwriting 'src'.

This fixes it for me:

-- >8 --
diff --git a/builtin/mv.c b/builtin/mv.c
index 7e26eb5..23f119a 100644
--- a/builtin/mv.c
+++ b/builtin/mv.c
@@ -180,6 +180,9 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 						modes = xrealloc(modes,
 								(argc + last - first)
 								* sizeof(enum update_mode));
+						submodule_gitfile = xrealloc(submodule_gitfile,
+								(argc + last - first)
+								* sizeof(char *));
 					}
 
 					dst = add_slash(dst);

[PATCH] builtin/mv: fix out of bounds write

[John Keeping]

When commit a88c915 (mv: move submodules using a gitfile, 2013-07-30)
added the submodule_gitfile array, it was not added to the block that
enlarges the arrays when we are moving a directory so that we do not
have to worry about it being a directory when we perform the actual
move.  After this, the loop continues over the enlarged set of sources.

Since we assume that submodule_gitfile has size argc, if any of the
items in the source directory are submodules we are guaranteed to write
beyond the end of submodule_gitfile.

Fix this by realloc'ing submodule_gitfile at the same time as the other
arrays.

Reported-by: Guillaume Gelin <contact@ramnes.eu>
Signed-off-by: John Keeping <john@keeping.me.uk>
---
On Sat, Mar 08, 2014 at 06:12:18PM +0000, John Keeping wrote:
> This fixes it for me:

Here it is as a proper patch.

 builtin/mv.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/builtin/mv.c b/builtin/mv.c
index 21c46d1..f99c91e 100644
--- a/builtin/mv.c
+++ b/builtin/mv.c
@@ -179,6 +179,9 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 						modes = xrealloc(modes,
 								(argc + last - first)
 								* sizeof(enum update_mode));
+						submodule_gitfile = xrealloc(submodule_gitfile,
+								(argc + last - first)
+								* sizeof(char *));
 					}
 
 					dst = add_slash(dst);
-- 
1.9.0.6.g037df60.dirty

Re: [PATCH] builtin/mv: fix out of bounds write

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 1887 bytes --]

On Sat, Mar 08, 2014 at 06:35:01PM +0000, John Keeping wrote:
> When commit a88c915 (mv: move submodules using a gitfile, 2013-07-30)
> added the submodule_gitfile array, it was not added to the block that
> enlarges the arrays when we are moving a directory so that we do not
> have to worry about it being a directory when we perform the actual
> move.  After this, the loop continues over the enlarged set of sources.
> 
> Since we assume that submodule_gitfile has size argc, if any of the
> items in the source directory are submodules we are guaranteed to write
> beyond the end of submodule_gitfile.
> 
> Fix this by realloc'ing submodule_gitfile at the same time as the other
> arrays.
> 
> Reported-by: Guillaume Gelin <contact@ramnes.eu>
> Signed-off-by: John Keeping <john@keeping.me.uk>
> ---
> On Sat, Mar 08, 2014 at 06:12:18PM +0000, John Keeping wrote:
> > This fixes it for me:
> 
> Here it is as a proper patch.
> 
>  builtin/mv.c | 3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/builtin/mv.c b/builtin/mv.c
> index 21c46d1..f99c91e 100644
> --- a/builtin/mv.c
> +++ b/builtin/mv.c
> @@ -179,6 +179,9 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
>  						modes = xrealloc(modes,
>  								(argc + last - first)
>  								* sizeof(enum update_mode));
> +						submodule_gitfile = xrealloc(submodule_gitfile,
> +								(argc + last - first)
> +								* sizeof(char *));
>  					}
>  
>  					dst = add_slash(dst);

Yup, that's the same conclusion I came to.  There are also two cases
where we don't shrink the array properly.  I'll rebase my patch on top
of this one and send it.

-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[PATCH] mv: prevent mismatched data when ignoring errors.

[brian m. carlson]

We shrink the source and destination arrays, but not the modes or
submodule_gitfile arrays, resulting in potentially mismatched data.  Shrink
all the arrays at the same time to prevent this.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 builtin/mv.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/builtin/mv.c b/builtin/mv.c
index f99c91e..b20cd95 100644
--- a/builtin/mv.c
+++ b/builtin/mv.c
@@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 					memmove(destination + i,
 						destination + i + 1,
 						(argc - i) * sizeof(char *));
+					memmove(modes + i, modes + i + 1,
+						(argc - i) * sizeof(char *));
+					memmove(submodule_gitfile + i,
+						submodule_gitfile + i + 1,
+						(argc - i) * sizeof(char *));
 					i--;
 				}
 			} else
-- 
1.9.0.1010.g6633b85.dirty

[PATCH v2] builtin/mv: fix out of bounds write

[John Keeping]

When commit a88c915 (mv: move submodules using a gitfile, 2013-07-30)
added the submodule_gitfile array, it was not added to the block that
enlarges the arrays when we are moving a directory so that we do not
have to worry about it being a directory when we perform the actual
move.  After this, the loop continues over the enlarged set of sources.

Since we assume that submodule_gitfile has size argc, if any of the
items in the source directory are submodules we are guaranteed to write
beyond the end of submodule_gitfile.

Fix this by realloc'ing submodule_gitfile at the same time as the other
arrays.

Reported-by: Guillaume Gelin <contact@ramnes.eu>
Signed-off-by: John Keeping <john@keeping.me.uk>
---
On Sat, Mar 08, 2014 at 07:15:42PM +0000, brian m. carlson wrote:
> Yup, that's the same conclusion I came to.  There are also two cases
> where we don't shrink the array properly.  I'll rebase my patch on top
> of this one and send it.

Nice catch.  While looking at that, I spotted that I forgot to
initialize the new values in submodule_gitfile when it grows.
Guillaume's test case doesn't catch that because all the subdirectories
are submodules.

 builtin/mv.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/builtin/mv.c b/builtin/mv.c
index 21c46d1..5258077 100644
--- a/builtin/mv.c
+++ b/builtin/mv.c
@@ -179,6 +179,9 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 						modes = xrealloc(modes,
 								(argc + last - first)
 								* sizeof(enum update_mode));
+						submodule_gitfile = xrealloc(submodule_gitfile,
+								(argc + last - first)
+								* sizeof(char *));
 					}
 
 					dst = add_slash(dst);
@@ -192,6 +195,7 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 							prefix_path(dst, dst_len,
 								path + length + 1);
 						modes[argc + j] = INDEX;
+						submodule_gitfile[argc + j] = NULL;
 					}
 					argc += last - first;
 				}
-- 
1.9.0.6.g037df60.dirty

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Jeff King]

On Sat, Mar 08, 2014 at 07:21:39PM +0000, brian m. carlson wrote:

> We shrink the source and destination arrays, but not the modes or
> submodule_gitfile arrays, resulting in potentially mismatched data.  Shrink
> all the arrays at the same time to prevent this.
> 
> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
> ---
>  builtin/mv.c | 5 +++++
>  1 file changed, 5 insertions(+)
> 
> diff --git a/builtin/mv.c b/builtin/mv.c
> index f99c91e..b20cd95 100644
> --- a/builtin/mv.c
> +++ b/builtin/mv.c
> @@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
>  					memmove(destination + i,
>  						destination + i + 1,
>  						(argc - i) * sizeof(char *));
> +					memmove(modes + i, modes + i + 1,
> +						(argc - i) * sizeof(char *));
> +					memmove(submodule_gitfile + i,
> +						submodule_gitfile + i + 1,
> +						(argc - i) * sizeof(char *));

I haven't looked that closely, but would it be crazy to suggest that
these arrays all be squashed into one array-of-struct? It would be less
error prone and perhaps more readable.

-Peff

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 1714 bytes --]

On Mon, Mar 10, 2014 at 09:56:03PM -0400, Jeff King wrote:
> On Sat, Mar 08, 2014 at 07:21:39PM +0000, brian m. carlson wrote:
> 
> > We shrink the source and destination arrays, but not the modes or
> > submodule_gitfile arrays, resulting in potentially mismatched data.  Shrink
> > all the arrays at the same time to prevent this.
> > 
> > Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
> > ---
> >  builtin/mv.c | 5 +++++
> >  1 file changed, 5 insertions(+)
> > 
> > diff --git a/builtin/mv.c b/builtin/mv.c
> > index f99c91e..b20cd95 100644
> > --- a/builtin/mv.c
> > +++ b/builtin/mv.c
> > @@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
> >  					memmove(destination + i,
> >  						destination + i + 1,
> >  						(argc - i) * sizeof(char *));
> > +					memmove(modes + i, modes + i + 1,
> > +						(argc - i) * sizeof(char *));
> > +					memmove(submodule_gitfile + i,
> > +						submodule_gitfile + i + 1,
> > +						(argc - i) * sizeof(char *));
> 
> I haven't looked that closely, but would it be crazy to suggest that
> these arrays all be squashed into one array-of-struct? It would be less
> error prone and perhaps more readable.

I was thinking of doing exactly that, but the way internal_copy_pathspec
is written, I'd need to use offsetof to have it write to the right
structure members.  That's a bit more gross than I wanted, but I'll
probably implement it at some point during the upcoming week.

-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Junio C Hamano]

"brian m. carlson" <sandals@crustytoothpaste.net> writes:

> We shrink the source and destination arrays, but not the modes or
> submodule_gitfile arrays, resulting in potentially mismatched data.  Shrink
> all the arrays at the same time to prevent this.
>
> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
> ---
>  builtin/mv.c | 5 +++++
>  1 file changed, 5 insertions(+)
>
> diff --git a/builtin/mv.c b/builtin/mv.c
> index f99c91e..b20cd95 100644
> --- a/builtin/mv.c
> +++ b/builtin/mv.c
> @@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
>  					memmove(destination + i,
>  						destination + i + 1,
>  						(argc - i) * sizeof(char *));
> +					memmove(modes + i, modes + i + 1,
> +						(argc - i) * sizeof(char *));
> +					memmove(submodule_gitfile + i,
> +						submodule_gitfile + i + 1,
> +						(argc - i) * sizeof(char *));
>  					i--;
>  				}
>  			} else

Thanks.  Neither this nor John's seems to describe the user-visible
way to trigger the symptom.  Can we have tests for them?

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 586 bytes --]

On Tue, Mar 11, 2014 at 02:45:59PM -0700, Junio C Hamano wrote:
> Thanks.  Neither this nor John's seems to describe the user-visible
> way to trigger the symptom.  Can we have tests for them?

I'll try to get to writing some test today or tomorrow.  I just noticed
the bugginess by looking at the code, so I'll need to actually spend
time reproducing the problem.

-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Thomas Rast]

"brian m. carlson" <sandals@crustytoothpaste.net> writes:

> We shrink the source and destination arrays, but not the modes or
> submodule_gitfile arrays, resulting in potentially mismatched data.  Shrink
> all the arrays at the same time to prevent this.
>
> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
> ---
>  builtin/mv.c | 5 +++++
>  1 file changed, 5 insertions(+)
>
> diff --git a/builtin/mv.c b/builtin/mv.c
> index f99c91e..b20cd95 100644
> --- a/builtin/mv.c
> +++ b/builtin/mv.c
> @@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
>  					memmove(destination + i,
>  						destination + i + 1,
>  						(argc - i) * sizeof(char *));
> +					memmove(modes + i, modes + i + 1,
> +						(argc - i) * sizeof(char *));

This isn't right -- you are computing the size of things to be moved
based on a type of char*, but 'modes' is an enum.

(Valgrind spotted this.)

-- 
Thomas Rast
tr@thomasrast.ch

[PATCH v2] mv: prevent mismatched data when ignoring errors.

[brian m. carlson]

We shrink the source and destination arrays, but not the modes or
submodule_gitfile arrays, resulting in potentially mismatched data.  Shrink
all the arrays at the same time to prevent this.  Add tests to ensure the
problem does not recur.

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---

I attempted to come up with a second patch that would refactor out the
four different arrays into one array of struct, as Jeff suggested, but
it became very ugly very quickly.  So this patch simply fixes the
problem and adds tests.

 builtin/mv.c  |  5 +++++
 t/t7001-mv.sh | 13 ++++++++++++-
 2 files changed, 17 insertions(+), 1 deletion(-)

diff --git a/builtin/mv.c b/builtin/mv.c
index f99c91e..09bbc63 100644
--- a/builtin/mv.c
+++ b/builtin/mv.c
@@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
 					memmove(destination + i,
 						destination + i + 1,
 						(argc - i) * sizeof(char *));
+					memmove(modes + i, modes + i + 1,
+						(argc - i) * sizeof(enum update_mode));
+					memmove(submodule_gitfile + i,
+						submodule_gitfile + i + 1,
+						(argc - i) * sizeof(char *));
 					i--;
 				}
 			} else
diff --git a/t/t7001-mv.sh b/t/t7001-mv.sh
index e3c8c2c..215d43d 100755
--- a/t/t7001-mv.sh
+++ b/t/t7001-mv.sh
@@ -294,7 +294,8 @@ test_expect_success 'setup submodule' '
 	git submodule add ./. sub &&
 	echo content >file &&
 	git add file &&
-	git commit -m "added sub and file"
+	git commit -m "added sub and file" &&
+	git branch submodule
 '
 
 test_expect_success 'git mv cannot move a submodule in a file' '
@@ -463,4 +464,14 @@ test_expect_success 'checking out a commit before submodule moved needs manual u
 	! test -s actual
 '
 
+test_expect_success 'mv -k does not accidentally destroy submodules' '
+	git checkout submodule &&
+	mkdir dummy dest &&
+	git mv -k dummy sub dest &&
+	git status --porcelain >actual &&
+	grep "^R  sub -> dest/sub" actual &&
+	git reset --hard &&
+	git checkout .
+'
+
 test_done
-- 
1.9.0.1010.g6633b85.dirty

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Jeff King]

On Sat, Mar 15, 2014 at 05:05:29PM +0100, Thomas Rast wrote:

> > diff --git a/builtin/mv.c b/builtin/mv.c
> > index f99c91e..b20cd95 100644
> > --- a/builtin/mv.c
> > +++ b/builtin/mv.c
> > @@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
> >  					memmove(destination + i,
> >  						destination + i + 1,
> >  						(argc - i) * sizeof(char *));
> > +					memmove(modes + i, modes + i + 1,
> > +						(argc - i) * sizeof(char *));
> 
> This isn't right -- you are computing the size of things to be moved
> based on a type of char*, but 'modes' is an enum.
> 
> (Valgrind spotted this.)

Maybe using sizeof(*destination) and sizeof(*modes) would make this less
error-prone?

-Peff

Re: [PATCH v2] mv: prevent mismatched data when ignoring errors.

[Jeff King]

On Sat, Mar 15, 2014 at 06:56:52PM +0000, brian m. carlson wrote:

> We shrink the source and destination arrays, but not the modes or
> submodule_gitfile arrays, resulting in potentially mismatched data.  Shrink
> all the arrays at the same time to prevent this.  Add tests to ensure the
> problem does not recur.
> 
> Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
> ---
> 
> I attempted to come up with a second patch that would refactor out the
> four different arrays into one array of struct, as Jeff suggested, but
> it became very ugly very quickly.  So this patch simply fixes the
> problem and adds tests.

>From my brief look, I feared that might be the case. Oh well, thanks for
trying.

-Peff

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Sat, Mar 15, 2014 at 05:05:29PM +0100, Thomas Rast wrote:
>
>> > diff --git a/builtin/mv.c b/builtin/mv.c
>> > index f99c91e..b20cd95 100644
>> > --- a/builtin/mv.c
>> > +++ b/builtin/mv.c
>> > @@ -230,6 +230,11 @@ int cmd_mv(int argc, const char **argv, const char *prefix)
>> >  					memmove(destination + i,
>> >  						destination + i + 1,
>> >  						(argc - i) * sizeof(char *));
>> > +					memmove(modes + i, modes + i + 1,
>> > +						(argc - i) * sizeof(char *));
>> 
>> This isn't right -- you are computing the size of things to be moved
>> based on a type of char*, but 'modes' is an enum.
>> 
>> (Valgrind spotted this.)
>
> Maybe using sizeof(*destination) and sizeof(*modes) would make this less
> error-prone?
>
> -Peff

Would it make sense to go one step further to introduce two macros
to make this kind of screw-up less likely?

 1. "array" is an array that holds "nr" elements.  Move "count"
    elements starting at index "at" down to remove them.

    #define MOVE_DOWN(array, nr, at, count)

    The implementation should take advantage of sizeof(*array) to
    come up with the number of bytes to move.


 2. "array" is an array that holds "nr" elements.  Move "count"
    elements starting at index "at" up to make room to copy new
    elements in.

    #define MOVE_UP(array, nr, at, count)

    The implementation should take advantage of sizeof(*array) to
    come up with the number of bytes to move.

Optionally, to make 2. even safer, these macros could take "alloc"
to say that "array" has memory allocated to hold "alloc" elements,
and the implementation may check "nr + count" does not overflow
"alloc".  This would make 1. and 2. asymmetric (move-down can do no
validation using "alloc", but move-up would be helped), so I am not
sure it is a good idea.

After letting my eyes coast over hits from "git grep memmove", there
do seem to be some places that these would help readability, but not
very many.

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Would it make sense to go one step further to introduce two macros
> to make this kind of screw-up less likely?
> ...
> After letting my eyes coast over hits from "git grep memmove", there
> do seem to be some places that these would help readability, but not
> very many.

I see quite a many hits that follow this pattern

	memmove(array + pos, array + pos + 1, sizeof(*array) * (nr - pos))

to make a single slot in a middle of array available, which would be
good candidates to use MOVE_DOWN().  Just to show a few:

builtin/mv.c:226:	memmove(source + i, source + i + 1,
builtin/mv.c-227-		(argc - i) * sizeof(char *));
builtin/mv.c:228:	memmove(destination + i,
builtin/mv.c-229-		destination + i + 1,
builtin/mv.c-230-		(argc - i) * sizeof(char *));
cache-tree.c:92:	memmove(it->down + pos + 1,
cache-tree.c-93-		it->down + pos,
cache-tree.c-94-		sizeof(down) * (it->subtree_nr - pos - 1));


Perhaps something like this patch to start off; I am not sure
MOVE_DOWN_BOUNDED is needed, though.

 cache.h | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/cache.h b/cache.h
index b66cb49..b2615ab 100644
--- a/cache.h
+++ b/cache.h
@@ -455,6 +455,39 @@ extern int daemonize(void);
 		} \
 	} while (0)
 
+/*
+ * With an array "array" that currently holds "nr" elements, move
+ * elements at "at" and later down by "count" elements to make room to
+ * add in new elements.  The caller is responsible for making sure
+ * that the array has enough room to hold "nr" + "count" slots.
+ */
+#define MOVE_DOWN(array, nr, at, count)			\
+	memmove((array) + (at) + (count),		\
+		(array) + (at),				\
+		sizeof((array)[0]) * ((nr) - (at)))
+
+/*
+ * With an array "array" that has enough memory to hold "alloc"
+ * elements allocated and currently holds "nr" elements, move elements
+ * at "at" and later down by "count" elements to make room to add in
+ * new elements.
+ */
+#define MOVE_DOWN_BOUNDED(array, nr, at, count, alloc)		     \
+	do {							     \
+		if ((alloc) <= (nr) + (count))			     \
+			BUG("MOVE_DOWN beyond the end of an array"); \
+		MOVE_DOWN((array), (nr), (at), (count));	     \
+	} while (0)
+
+/*
+ * With an array "array" that curently holds "nr" elements, move elements
+ * at "at" + "count" and later down by "count" elements, removing the
+ * elements between "at" and "at" + "count".
+ */
+#define MOVE_UP(array, nr, at, count)				\
+	memmove((array) + (at), (array) + (at) + (count),	\
+		sizeof((array)[0]) * ((nr) - ((at) + (count))))
+
 /* Initialize and use the cache information */
 extern int read_index(struct index_state *);
 extern int read_index_preload(struct index_state *, const struct pathspec *pathspec);

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Michael Haggerty]

On 03/17/2014 07:33 AM, Junio C Hamano wrote:
> Junio C Hamano <gitster@pobox.com> writes:
> 
>> Would it make sense to go one step further to introduce two macros
>> to make this kind of screw-up less likely?
>> ...
>> After letting my eyes coast over hits from "git grep memmove", there
>> do seem to be some places that these would help readability, but not
>> very many.
> 
> I see quite a many hits that follow this pattern
> 
> 	memmove(array + pos, array + pos + 1, sizeof(*array) * (nr - pos))
> 
> to make a single slot in a middle of array available, which would be
> good candidates to use MOVE_DOWN().  Just to show a few:
> 
> builtin/mv.c:226:	memmove(source + i, source + i + 1,
> builtin/mv.c-227-		(argc - i) * sizeof(char *));
> builtin/mv.c:228:	memmove(destination + i,
> builtin/mv.c-229-		destination + i + 1,
> builtin/mv.c-230-		(argc - i) * sizeof(char *));
> cache-tree.c:92:	memmove(it->down + pos + 1,
> cache-tree.c-93-		it->down + pos,
> cache-tree.c-94-		sizeof(down) * (it->subtree_nr - pos - 1));
> 
> 
> Perhaps something like this patch to start off; I am not sure
> MOVE_DOWN_BOUNDED is needed, though.
> 
>  cache.h | 33 +++++++++++++++++++++++++++++++++
>  1 file changed, 33 insertions(+)
> 
> diff --git a/cache.h b/cache.h
> index b66cb49..b2615ab 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -455,6 +455,39 @@ extern int daemonize(void);
>  		} \
>  	} while (0)
>  
> +/*
> + * With an array "array" that currently holds "nr" elements, move
> + * elements at "at" and later down by "count" elements to make room to
> + * add in new elements.  The caller is responsible for making sure
> + * that the array has enough room to hold "nr" + "count" slots.
> + */
> +#define MOVE_DOWN(array, nr, at, count)			\
> +	memmove((array) + (at) + (count),		\
> +		(array) + (at),				\
> +		sizeof((array)[0]) * ((nr) - (at)))
> +
> +/*
> + * With an array "array" that has enough memory to hold "alloc"
> + * elements allocated and currently holds "nr" elements, move elements
> + * at "at" and later down by "count" elements to make room to add in
> + * new elements.
> + */
> +#define MOVE_DOWN_BOUNDED(array, nr, at, count, alloc)		     \
> +	do {							     \
> +		if ((alloc) <= (nr) + (count))			     \
> +			BUG("MOVE_DOWN beyond the end of an array"); \
> +		MOVE_DOWN((array), (nr), (at), (count));	     \
> +	} while (0)
> +
> +/*
> + * With an array "array" that curently holds "nr" elements, move elements
> + * at "at" + "count" and later down by "count" elements, removing the
> + * elements between "at" and "at" + "count".
> + */
> +#define MOVE_UP(array, nr, at, count)				\
> +	memmove((array) + (at), (array) + (at) + (count),	\
> +		sizeof((array)[0]) * ((nr) - ((at) + (count))))
> +
>  /* Initialize and use the cache information */
>  extern int read_index(struct index_state *);
>  extern int read_index_preload(struct index_state *, const struct pathspec *pathspec);

I had recently been thinking along the same lines.  In many of the
potential callers that I noticed, ALLOC_GROW() was used immediately
before making space in the array for a new element.  So I suggest
something more like

+#define MOVE_DOWN(array, nr, at, count)	\
+	memmove((array) + (at) + (count),		\
+		(array) + (at),				\
+		sizeof((array)[0]) * ((nr) - (at)))
+#define ALLOC_INSERT_GAP(array, nr, at, count, alloc)		     \
+	do {							     \
+		ALLOC_GROW((array), (nr) + (count), (alloc));        \
+		MOVE_DOWN((array), (nr), (at), (count));	     \
+	} while (0)

Also, count==1 is so frequent that this special case might deserve its
own macro pair.

I'm not inspired by these macro names, though.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Eric Sunshine]

On Mon, Mar 17, 2014 at 11:07 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> On 03/17/2014 07:33 AM, Junio C Hamano wrote:
>> Junio C Hamano <gitster@pobox.com> writes:
>>
>>> Would it make sense to go one step further to introduce two macros
>>> to make this kind of screw-up less likely?
> potential callers that I noticed, ALLOC_GROW() was used immediately
> before making space in the array for a new element.  So I suggest
> something more like
>
> +#define MOVE_DOWN(array, nr, at, count)        \
> +       memmove((array) + (at) + (count),               \
> +               (array) + (at),                         \
> +               sizeof((array)[0]) * ((nr) - (at)))

Each time I read these, my brain (for whatever reason) interprets the
names UP and DOWN opposite of the intended meaning, which makes them
confusing. Perhaps INSERT_GAP and CLOSE_GAP would avoid such problems,
and be more consistent with Michael's proposed ALLOC_INSERT_GAP.

> +#define ALLOC_INSERT_GAP(array, nr, at, count, alloc)               \
> +       do {                                                         \
> +               ALLOC_GROW((array), (nr) + (count), (alloc));        \
> +               MOVE_DOWN((array), (nr), (at), (count));             \
> +       } while (0)
>
> Also, count==1 is so frequent that this special case might deserve its
> own macro pair.
>
> I'm not inspired by these macro names, though.
>
> Michael
>
> --
> Michael Haggerty
> mhagger@alum.mit.edu
> http://softwareswirl.blogspot.com/

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Jeff King]

On Mon, Mar 17, 2014 at 03:06:02PM -0400, Eric Sunshine wrote:

> On Mon, Mar 17, 2014 at 11:07 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> > On 03/17/2014 07:33 AM, Junio C Hamano wrote:
> >> Junio C Hamano <gitster@pobox.com> writes:
> >>
> >>> Would it make sense to go one step further to introduce two macros
> >>> to make this kind of screw-up less likely?
> > potential callers that I noticed, ALLOC_GROW() was used immediately
> > before making space in the array for a new element.  So I suggest
> > something more like
> >
> > +#define MOVE_DOWN(array, nr, at, count)        \
> > +       memmove((array) + (at) + (count),               \
> > +               (array) + (at),                         \
> > +               sizeof((array)[0]) * ((nr) - (at)))
> 
> Each time I read these, my brain (for whatever reason) interprets the
> names UP and DOWN opposite of the intended meaning, which makes them
> confusing. Perhaps INSERT_GAP and CLOSE_GAP would avoid such problems,
> and be more consistent with Michael's proposed ALLOC_INSERT_GAP.

Yeah, the UP/DOWN are very confusing to me. Something like SHRINK/EXPAND
(with the latter handling the ALLOC_GROW for us) makes more sense to me.
Those terms do not explicitly specify that we are doing it in the middle
(whereas GAP does), but I think it is fairly obvious from the parameters
what each is used for.

Side note: I had _almost_ added something to my original email
suggesting more use of macros to embody common idioms. For example, in
the vast majority of malloc cases, you could using something like:

  #define ALLOC_OBJS(x,n) do { x = xmalloc(sizeof(*x) * (n)); } while(0)
  #define ALLOC_OBJ(x) ALLOC_OBJS(x,1)

That eliminates a whole possible class of errors. But it's also
un-idiomatic as hell, and the resulting confusion can cause its own
problems. So I refrained from suggesting it.

I think as long as a macro is expressing a more high-level intent,
though, paying that cost can be worth it. By itself, wrapping memmove
to use sizeof(*array) does not seem all that exciting. But wrapping a
few specific cases like shrink/expand probably does make the code more
readable.

-Peff

Re: [PATCH] mv: prevent mismatched data when ignoring errors.

[Junio C Hamano]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> I had recently been thinking along the same lines.  In many of the
> potential callers that I noticed, ALLOC_GROW() was used immediately
> before making space in the array for a new element.  So I suggest
> something more like
>
> +#define MOVE_DOWN(array, nr, at, count)	\
> +	memmove((array) + (at) + (count),		\
> +		(array) + (at),				\
> +		sizeof((array)[0]) * ((nr) - (at)))
> +#define ALLOC_INSERT_GAP(array, nr, at, count, alloc)		     \
> +	do {							     \
> +		ALLOC_GROW((array), (nr) + (count), (alloc));        \
> +		MOVE_DOWN((array), (nr), (at), (count));	     \
> +	} while (0)
>
> Also, count==1 is so frequent that this special case might deserve its
> own macro pair.

Yeah, probably.

> I'm not inspired by these macro names, though.

Me neither, about ups and downs.

Peff's suggestion to name these around the concept of "gap" sounded
sensible.