[PATCH] cache-tree: reject entries with null sha1

[PATCH] cache-tree: reject entries with null sha1

[Jeff King]

We generally disallow null sha1s from entering the index,
due to 4337b5856 (do not write null sha1s to on-disk index,
2012-07-28). However, we loosened that in 83bd7437c
(write_index: optionally allow broken null sha1s,
2013-08-27) so that tools like filter-branch could be used
to repair broken history.

However, we should make sure that these broken entries do
not get propagated into new trees. For most entries, we'd
catch them with the missing-object check (since presumably
the null sha1 does not exist in our object database). But
gitlink entries do not need reachability, so we may blindly
copy the entry into a bogus tree.

This patch rejects all null sha1s (with the same "invalid
entry" message that missing objects get) when building trees
from the index. It does so even for non-gitlinks, and even
when "write-tree" is given the --missing-ok flag. The null
sha1 is a special sentinel value that is already rejected in
trees by fsck; whether the object exists or not, it is an
error to put it in a tree.

Note that for this to work, we must also avoid reusing an
existing cache-tree that contains the null sha1. This patch
does so by just refusing to write out any cache tree when
the index contains a null sha1. This is blunter than we need
to be; we could just reject the subtree that contains the
offending entry. But it's not worth the complexity. The
behavior is unchanged unless you have a broken index entry,
and even then we'd refuse the whole index write unless the
emergency GIT_ALLOW_NULL_SHA1 is in use. And even then the
end result is only a performance drop (any write-tree will
have to generate the whole cache-tree from scratch).

The tests bear some explanation.

The existing test in t7009 doesn't catch this problem,
because our index-filter runs "git rm --cached", which will
try to rewrite the updated index and barf on the bogus
entry. So we never even make it to write-tree.  The new test
there adds a noop index-filter, which does show the problem.

The new tests in t1601 are slightly redundant with what
filter-branch is doing under the hood in t7009. But as
they're much more direct, they're easier to reason about.
And should filter-branch ever change or go away, we'd want
to make sure that these plumbing commands behave sanely.

Signed-off-by: Jeff King <peff@peff.net>
---
When merged to pu, this fixes the existing test breakage in t7009 when
GIT_TEST_SPLIT_INDEX is used (because the split index didn't rewrite the
whole index, "git rm --cached" didn't always barf). But I think it's
worth doing on its own merits, as demonstrated by the new tests.

The one thing I haven't figured out it is why the new test in t7009
fails with the split-index. And even more curiously, the new tests in
t1601 _don't_ fail with it, even if I instrument the fake index to have
more entries (making it more likely to split).

 cache-tree.c                       |  4 +++-
 read-cache.c                       |  5 ++++-
 t/t1601-index-bogus.sh             | 22 ++++++++++++++++++++++
 t/t7009-filter-branch-null-sha1.sh |  6 ++++++
 4 files changed, 35 insertions(+), 2 deletions(-)
 create mode 100755 t/t1601-index-bogus.sh

diff --git a/cache-tree.c b/cache-tree.c
index 345ea3596..34baa6d85 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -354,7 +354,9 @@ static int update_one(struct cache_tree *it,
 			entlen = pathlen - baselen;
 			i++;
 		}
-		if (mode != S_IFGITLINK && !missing_ok && !has_sha1_file(sha1)) {
+
+		if (is_null_sha1(sha1) ||
+		    (mode != S_IFGITLINK && !missing_ok && !has_sha1_file(sha1))) {
 			strbuf_release(&buffer);
 			if (expected_missing)
 				return -1;
diff --git a/read-cache.c b/read-cache.c
index e44775182..6851de892 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -2054,6 +2054,7 @@ static int do_write_index(struct index_state *istate, int newfd,
 	int entries = istate->cache_nr;
 	struct stat st;
 	struct strbuf previous_name_buf = STRBUF_INIT, *previous_name;
+	int drop_cache_tree = 0;
 
 	for (i = removed = extended = 0; i < entries; i++) {
 		if (cache[i]->ce_flags & CE_REMOVE)
@@ -2104,6 +2105,8 @@ static int do_write_index(struct index_state *istate, int newfd,
 				warning(msg, ce->name);
 			else
 				return error(msg, ce->name);
+
+			drop_cache_tree = 1;
 		}
 		if (ce_write_entry(&c, newfd, ce, previous_name) < 0)
 			return -1;
@@ -2122,7 +2125,7 @@ static int do_write_index(struct index_state *istate, int newfd,
 		if (err)
 			return -1;
 	}
-	if (!strip_extensions && istate->cache_tree) {
+	if (!strip_extensions && !drop_cache_tree && istate->cache_tree) {
 		struct strbuf sb = STRBUF_INIT;
 
 		cache_tree_write(&sb, istate->cache_tree);
diff --git a/t/t1601-index-bogus.sh b/t/t1601-index-bogus.sh
new file mode 100755
index 000000000..73cc9323c
--- /dev/null
+++ b/t/t1601-index-bogus.sh
@@ -0,0 +1,22 @@
+#!/bin/sh
+
+test_description='test handling of bogus index entries'
+. ./test-lib.sh
+
+test_expect_success 'create tree with null sha1' '
+	tree=$(printf "160000 commit $_z40\\tbroken\\n" | git mktree)
+'
+
+test_expect_success 'read-tree refuses to read null sha1' '
+	test_must_fail git read-tree $tree
+'
+
+test_expect_success 'GIT_ALLOW_NULL_SHA1 overrides refusal' '
+	GIT_ALLOW_NULL_SHA1=1 git read-tree $tree
+'
+
+test_expect_success 'git write-tree refuses to write null sha1' '
+	test_must_fail git write-tree
+'
+
+test_done
diff --git a/t/t7009-filter-branch-null-sha1.sh b/t/t7009-filter-branch-null-sha1.sh
index c27f90f28..a8d9ec498 100755
--- a/t/t7009-filter-branch-null-sha1.sh
+++ b/t/t7009-filter-branch-null-sha1.sh
@@ -31,6 +31,12 @@ test_expect_success 'setup: bring HEAD and index in sync' '
 	git commit -a -m "back to normal"
 '
 
+test_expect_success 'noop filter-branch complains' '
+	test_must_fail git filter-branch \
+		--force --prune-empty \
+		--index-filter "true"
+'
+
 test_expect_success 'filter commands are still checked' '
 	test_must_fail git filter-branch \
 		--force --prune-empty \
-- 
2.13.0.rc0.364.g36b4d8031

Re: [PATCH] cache-tree: reject entries with null sha1

[Duy Nguyen]

On Sat, Apr 22, 2017 at 1:46 AM, Jeff King <peff@peff.net> wrote:
> We generally disallow null sha1s from entering the index,
> due to 4337b5856 (do not write null sha1s to on-disk index,
> 2012-07-28). However, we loosened that in 83bd7437c
> (write_index: optionally allow broken null sha1s,
> 2013-08-27) so that tools like filter-branch could be used
> to repair broken history.

Uh oh.. cache-tree.

> However, we should make sure that these broken entries do
> not get propagated into new trees. For most entries, we'd
> catch them with the missing-object check (since presumably
> the null sha1 does not exist in our object database). But
> gitlink entries do not need reachability, so we may blindly
> copy the entry into a bogus tree.

Phew.. not another bug of mine :D

> When merged to pu, this fixes the existing test breakage in t7009 when
> GIT_TEST_SPLIT_INDEX is used (because the split index didn't rewrite the
> whole index, "git rm --cached" didn't always barf).

Latest 'pu' has your patch, but t7009 still fails on me (with "invalid
object" error), more on this later..

> But I think it's worth doing on its own merits, as demonstrated by the new tests.

Agreed. The patch looks correct.

Just checking, since cache-tree helps speed up many operations,
dropping cache-tree can have some performance implication. But this
must be an error case (null sha1) and we will not run into it often to
worry about unnecessary dropping, correct?

> The one thing I haven't figured out it is why the new test in t7009
> fails with the split-index. And even more curiously, the new tests in
> t1601 _don't_ fail with it, even if I instrument the fake index to have
> more entries (making it more likely to split).

back to t7009 failure. I'll see if I can look more into this this
weekend. If split-index somehow produces these null sha1, then I
probably have a problem.

Thanks for looking at it anyway. One bug down. Thousands to go...

BTW, I ran t7009 with valgrind and it reported this. Is it something
we should be worried about? I vaguely recall you're doing something
with prio-queue...

==4246== Source and destination overlap in memcpy(0x5952990, 0x5952990, 16)
==4246==    at 0x4C2EACD: memcpy@@GLIBC_2.14 (in
/usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==4246==    by 0x545D05: swap (prio-queue.c:15)
==4246==    by 0x545D72: prio_queue_reverse (prio-queue.c:25)
==4246==    by 0x4CBC0C: sort_in_topological_order (commit.c:723)
==4246==    by 0x574C97: prepare_revision_walk (revision.c:2858)
==4246==    by 0x48A2BA: cmd_rev_list (rev-list.c:385)
==4246==    by 0x405A6F: run_builtin (git.c:371)
==4246==    by 0x405CDC: handle_builtin (git.c:572)
==4246==    by 0x405E51: run_argv (git.c:624)
==4246==    by 0x405FF3: cmd_main (git.c:701)
==4246==    by 0x4A48CE: main (common-main.c:43)
-- 
Duy

Re: [PATCH] cache-tree: reject entries with null sha1

[Jeff King]

On Mon, Apr 24, 2017 at 05:39:33PM +0700, Duy Nguyen wrote:

> > When merged to pu, this fixes the existing test breakage in t7009 when
> > GIT_TEST_SPLIT_INDEX is used (because the split index didn't rewrite the
> > whole index, "git rm --cached" didn't always barf).
> 
> Latest 'pu' has your patch, but t7009 still fails on me (with "invalid
> object" error), more on this later..

Right, it fails for me, too. But only on the new test "noop
filter-branch complaisn". The old one "filter commands are still
checked" should pass after my patch.

> Just checking, since cache-tree helps speed up many operations,
> dropping cache-tree can have some performance implication. But this
> must be an error case (null sha1) and we will not run into it often to
> worry about unnecessary dropping, correct?

Correct. We usually die when we see a null sha1. So this only kicks in
when GIT_ALLOW_NULL_SHA1 is set, which basically means when
filter-branch is running. And of course there it only kicks in when you
actually have a null sha1, which is a rare error case (and you must be
removing it with your filter, or write-tree will barf anyway).

> > The one thing I haven't figured out it is why the new test in t7009
> > fails with the split-index. And even more curiously, the new tests in
> > t1601 _don't_ fail with it, even if I instrument the fake index to have
> > more entries (making it more likely to split).
> 
> back to t7009 failure. I'll see if I can look more into this this
> weekend. If split-index somehow produces these null sha1, then I
> probably have a problem.

I don't think it's producing them. It's just that the check in
write-tree isn't triggering for some reasons. If I run t7009 with
GIT_TRACE=1, the failing test shows:

  trace: built-in: git 'read-tree' '-i' '-m' 'e3ed0c3a94f05540151bd8cb9ac647b8777964a6'
  error: invalid object 160000 0000000000000000000000000000000000000000 for 'broken'
  warning: cache entry has null sha1: broken
  trace: built-in: git 'cat-file' 'commit' 'e3ed0c3a94f05540151bd8cb9ac647b8777964a6'
  trace: built-in: git 'write-tree'

That last write-tree _should_ barf, but it doesn't. I suspect the reason
is that in the read-tree step, we do not properly strip the cache-tree
when we see the null sha1, so it just gets reused later. But I couldn't
reproduce it when running t1601, which does roughly the same steps.

If I instrument it like this:

diff --git a/read-cache.c b/read-cache.c
index 15a4779f2..4d9482092 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -2268,9 +2268,10 @@ static int do_write_index(struct index_state *istate, int newfd,
 		if (err)
 			return -1;
 	}
+	warning("drop_cache_tree = %d", drop_cache_tree);
 	if (!strip_extensions && !drop_cache_tree && istate->cache_tree) {
 		struct strbuf sb = STRBUF_INIT;
-
+		warning("reusing cache tree");
 		cache_tree_write(&sb, istate->cache_tree);
 		err = write_index_ext_header(&c, newfd, CACHE_EXT_TREE, sb.len) < 0
 			|| ce_write(&c, newfd, sb.buf, sb.len) < 0;

then I see:

  trace: built-in: git 'read-tree' '-i' '-m' 'e3ed0c3a94f05540151bd8cb9ac647b8777964a6'
  error: invalid object 160000 0000000000000000000000000000000000000000 for 'broken'
  warning: cache entry has null sha1: broken
  warning: drop_cache_tree = 1
  warning: drop_cache_tree = 0
  warning: reusing cache tree
  trace: built-in: git 'cat-file' 'commit' 'e3ed0c3a94f05540151bd8cb9ac647b8777964a6'
  trace: built-in: git 'write-tree'

So we end up in do_write_index twice, and one time we copy the cache
tree. I don't know how cache-tree works with the split index. Is it
possible that we write the cache-tree covering the entry for "broken"
into a separate index than the "broken" entry itself? That would explain
what I'm seeing.

> BTW, I ran t7009 with valgrind and it reported this. Is it something
> we should be worried about? I vaguely recall you're doing something
> with prio-queue...
> 
> ==4246== Source and destination overlap in memcpy(0x5952990, 0x5952990, 16)
> ==4246==    at 0x4C2EACD: memcpy@@GLIBC_2.14 (in
> /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==4246==    by 0x545D05: swap (prio-queue.c:15)
> ==4246==    by 0x545D72: prio_queue_reverse (prio-queue.c:25)
> ==4246==    by 0x4CBC0C: sort_in_topological_order (commit.c:723)
> ==4246==    by 0x574C97: prepare_revision_walk (revision.c:2858)
> ==4246==    by 0x48A2BA: cmd_rev_list (rev-list.c:385)
> ==4246==    by 0x405A6F: run_builtin (git.c:371)
> ==4246==    by 0x405CDC: handle_builtin (git.c:572)
> ==4246==    by 0x405E51: run_argv (git.c:624)
> ==4246==    by 0x405FF3: cmd_main (git.c:701)
> ==4246==    by 0x4A48CE: main (common-main.c:43)

I couldn't reproduce here, but it looks like it comes from René's new
SWAP macro. It doesn't detect a noop swap, and we may call memcpy with
identical src and dst parameters. That's _probably_ fine in practice,
but we may want to exit the function early.

I'll ping separately in that thread.

-Peff

Re: [PATCH] cache-tree: reject entries with null sha1

[René Scharfe]

Am 24.04.2017 um 12:39 schrieb Duy Nguyen:
> BTW, I ran t7009 with valgrind and it reported this. Is it something
> we should be worried about? I vaguely recall you're doing something
> with prio-queue...
> 
> ==4246== Source and destination overlap in memcpy(0x5952990, 0x5952990, 16)
> ==4246==    at 0x4C2EACD: memcpy@@GLIBC_2.14 (in
> /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==4246==    by 0x545D05: swap (prio-queue.c:15)
> ==4246==    by 0x545D72: prio_queue_reverse (prio-queue.c:25)
> ==4246==    by 0x4CBC0C: sort_in_topological_order (commit.c:723)
> ==4246==    by 0x574C97: prepare_revision_walk (revision.c:2858)
> ==4246==    by 0x48A2BA: cmd_rev_list (rev-list.c:385)
> ==4246==    by 0x405A6F: run_builtin (git.c:371)
> ==4246==    by 0x405CDC: handle_builtin (git.c:572)
> ==4246==    by 0x405E51: run_argv (git.c:624)
> ==4246==    by 0x405FF3: cmd_main (git.c:701)
> ==4246==    by 0x4A48CE: main (common-main.c:43)

I can only get gcc and clang to call memcpy instead of inlining it by
specifying -fno-builtin.  Do you use that option?  If yes, why?  (Just
curious.)

But I can't get Valgrind to report overlapping (nicely explained in
http://valgrind.org/docs/manual/mc-manual.html#mc-manual.overlap, by
the way), not for t7009 and not for the short test program at the
bottom.  Do you set flags in GIT_VALGRIND_OPTIONS or use a special
version of Valgrind?  I use valgrind-3.12.0.SVN from Debian testing.

Thanks,
René


/* Compile with -fno-builtin. */
#include <string.h>
int main(void) {int i = 1; memcpy(&i, &i, sizeof(i)); return i;}

Re: [PATCH] cache-tree: reject entries with null sha1

[René Scharfe]

Am 01.05.2017 um 13:23 schrieb René Scharfe:
> But I can't get Valgrind to report overlapping (nicely explained in
> http://valgrind.org/docs/manual/mc-manual.html#mc-manual.overlap, by
> the way), not for t7009 and not for the short test program at the
> bottom.  Do you set flags in GIT_VALGRIND_OPTIONS or use a special
> version of Valgrind?  I use valgrind-3.12.0.SVN from Debian testing.
> 
> Thanks,
> René
> 
> 
> /* Compile with -fno-builtin. */
> #include <string.h>
> int main(void) {int i = 1; memcpy(&i, &i, sizeof(i)); return i;}

Actually I can, on Debian stable x86 (Valgrind-3.10.0).  Not sure
whether it's the older version of Valgrind or the 32-bitness, but
it gives me a way to reproduce, so nevermind.

René

Re: [PATCH] cache-tree: reject entries with null sha1

[Jeff King]

On Mon, May 01, 2017 at 01:23:28PM +0200, René Scharfe wrote:

> Am 24.04.2017 um 12:39 schrieb Duy Nguyen:
> > BTW, I ran t7009 with valgrind and it reported this. Is it something
> > we should be worried about? I vaguely recall you're doing something
> > with prio-queue...
> > 
> > ==4246== Source and destination overlap in memcpy(0x5952990, 0x5952990, 16)
> > ==4246==    at 0x4C2EACD: memcpy@@GLIBC_2.14 (in
> > /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
> > ==4246==    by 0x545D05: swap (prio-queue.c:15)
> > ==4246==    by 0x545D72: prio_queue_reverse (prio-queue.c:25)
> > ==4246==    by 0x4CBC0C: sort_in_topological_order (commit.c:723)
> > ==4246==    by 0x574C97: prepare_revision_walk (revision.c:2858)
> > ==4246==    by 0x48A2BA: cmd_rev_list (rev-list.c:385)
> > ==4246==    by 0x405A6F: run_builtin (git.c:371)
> > ==4246==    by 0x405CDC: handle_builtin (git.c:572)
> > ==4246==    by 0x405E51: run_argv (git.c:624)
> > ==4246==    by 0x405FF3: cmd_main (git.c:701)
> > ==4246==    by 0x4A48CE: main (common-main.c:43)
> 
> I can only get gcc and clang to call memcpy instead of inlining it by
> specifying -fno-builtin.  Do you use that option?  If yes, why?  (Just
> curious.)

I do my normal edit-compile cycles with -O0 because it's fast, and
because it makes debugging much easier.

> But I can't get Valgrind to report overlapping (nicely explained in
> http://valgrind.org/docs/manual/mc-manual.html#mc-manual.overlap, by
> the way), not for t7009 and not for the short test program at the
> bottom.  Do you set flags in GIT_VALGRIND_OPTIONS or use a special
> version of Valgrind?  I use valgrind-3.12.0.SVN from Debian testing.

I saw it with 3.12.0-1.1 on Debian unstable.

-Peff

Re: [PATCH] cache-tree: reject entries with null sha1

[René Scharfe]

Am 01.05.2017 um 21:22 schrieb Jeff King:
> On Mon, May 01, 2017 at 01:23:28PM +0200, René Scharfe wrote:
>> I can only get gcc and clang to call memcpy instead of inlining it by
>> specifying -fno-builtin.  Do you use that option?  If yes, why?  (Just
>> curious.)
> 
> I do my normal edit-compile cycles with -O0 because it's fast, and
> because it makes debugging much easier.

GCC and Clang still inline memcpy with -O0 alone (at least the versions
I tested).

René

Re: [PATCH] cache-tree: reject entries with null sha1

[Jeff King]

On Mon, May 01, 2017 at 11:00:58PM +0200, René Scharfe wrote:

> Am 01.05.2017 um 21:22 schrieb Jeff King:
> > On Mon, May 01, 2017 at 01:23:28PM +0200, René Scharfe wrote:
> > > I can only get gcc and clang to call memcpy instead of inlining it by
> > > specifying -fno-builtin.  Do you use that option?  If yes, why?  (Just
> > > curious.)
> > 
> > I do my normal edit-compile cycles with -O0 because it's fast, and
> > because it makes debugging much easier.
> 
> GCC and Clang still inline memcpy with -O0 alone (at least the versions
> I tested).

I just checked the assembler output and confirmed that is the case for
my builds, even with -O0. Which probably explains why I wasn't able to
replicate Duy's valgrind error in the first place.

-Peff

Re: [PATCH] cache-tree: reject entries with null sha1

[Duy Nguyen]

On Tue, May 2, 2017 at 2:22 AM, Jeff King <peff@peff.net> wrote:
> On Mon, May 01, 2017 at 01:23:28PM +0200, René Scharfe wrote:
>
>> Am 24.04.2017 um 12:39 schrieb Duy Nguyen:
>> > BTW, I ran t7009 with valgrind and it reported this. Is it something
>> > we should be worried about? I vaguely recall you're doing something
>> > with prio-queue...
>> >
>> > ==4246== Source and destination overlap in memcpy(0x5952990, 0x5952990, 16)
>> > ==4246==    at 0x4C2EACD: memcpy@@GLIBC_2.14 (in
>> > /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
>> > ==4246==    by 0x545D05: swap (prio-queue.c:15)
>> > ==4246==    by 0x545D72: prio_queue_reverse (prio-queue.c:25)
>> > ==4246==    by 0x4CBC0C: sort_in_topological_order (commit.c:723)
>> > ==4246==    by 0x574C97: prepare_revision_walk (revision.c:2858)
>> > ==4246==    by 0x48A2BA: cmd_rev_list (rev-list.c:385)
>> > ==4246==    by 0x405A6F: run_builtin (git.c:371)
>> > ==4246==    by 0x405CDC: handle_builtin (git.c:572)
>> > ==4246==    by 0x405E51: run_argv (git.c:624)
>> > ==4246==    by 0x405FF3: cmd_main (git.c:701)
>> > ==4246==    by 0x4A48CE: main (common-main.c:43)
>>
>> I can only get gcc and clang to call memcpy instead of inlining it by
>> specifying -fno-builtin.  Do you use that option?  If yes, why?  (Just
>> curious.)
>
> I do my normal edit-compile cycles with -O0 because it's fast, and
> because it makes debugging much easier.

Same here. My CFLAGS (without lots of -Wstuff)

CFLAGS =  -g -O0 -fstack-protector

Maybe it's -fstack-protector then? This is gcc 4.9.3. I think Gentoo
does not add any distro-specific patches on this particular version.
-- 
Duy

Re: [PATCH] cache-tree: reject entries with null sha1

[René Scharfe]

Am 03.05.2017 um 11:46 schrieb Duy Nguyen:
> On Tue, May 2, 2017 at 2:22 AM, Jeff King <peff@peff.net> wrote:
>> On Mon, May 01, 2017 at 01:23:28PM +0200, René Scharfe wrote:
>>>
>>> I can only get gcc and clang to call memcpy instead of inlining it by
>>> specifying -fno-builtin.  Do you use that option?  If yes, why?  (Just
>>> curious.)
>>
>> I do my normal edit-compile cycles with -O0 because it's fast, and
>> because it makes debugging much easier.
> 
> Same here. My CFLAGS (without lots of -Wstuff)
> 
> CFLAGS =  -g -O0 -fstack-protector
> 
> Maybe it's -fstack-protector then? This is gcc 4.9.3. I think Gentoo
> does not add any distro-specific patches on this particular version.

gcc 4.9.2 on Debian i386 still inlines memcpy for me with these options.

https://packages.debian.org/jessie/gcc-4.9 links to a 5MB diff, and it
adds these lines to NEWS.gcc (plus changing a whole lot of other files,
of course):

+ - Better inlining of memcpy and memset that is aware of value ranges
+   and produces shorter alignment prologues.

That might be it.

René