patchsha1-file: remove OBJECT_INFO_SKIP_CACHED

In a partial clone, if a user provides the hash of the empty tree ("git mktree </dev/null" - for SHA-1, this is 4b825d...) to a command which requires that that object be parsed, for example:

  git diff-tree 4b825d <a non-empty tree>

then Git will lazily fetch the empty tree. This fetch would merely be inconvenient if the promisor remote could supply that tree, but at $DAYJOB we discovered that some repositories do not (e.g. [1]).

There are 2 functions: repo_has_object_file() which does not consult find_cached_object() (which, among other things, knows about the empty tree); and repo_read_object_file() which does. This issue occurs because, as an optimization to avoid reading blobs into memory, parse_object() calls repo_has_object_file() before repo_read_object_file(). In the case of a regular repository (that is, not a partial clone), repo_has_object_file() will return false for the empty tree (thus bypassing the optimization) and repo_read_object_file() will nevertheless succeed, thus things coincidentally work. But in a partial clone, repo_has_object_file() triggers a lazy fetch of the missing empty tree. This optimization was introduced by 090ea12671 ("parse_object: avoid putting whole blob in core", 2012-03-07), and the empty-tree special-case dichotomy between repo_has_object_file() (then, has_sha1_file()) and repo_read_object_file() (then, sha1_object_info()) has existed since then.

(The flag OBJECT_INFO_SKIP_CACHED, introduced later in dfdd4afcf9 ("sha1_file: teach sha1_object_info_extended more flags", 2017-06-26) and used in e83e71c5e1 ("sha1_file: refactor has_sha1_file_with_flags", 2017-06-26), was introduced to preserve the empty-tree special-case dichotomy.)

The best solution to the problem introduced at the start of this commit message seems to be to eliminate this dichotomy. Not only will this fix the problem, but it reduces a potential avenue of surprise for future developers of Git - it will no longer be the case that repo_has_object_file() doesn't know about empty trees, but repo_read_object_file() does. A cost is that repo_has_object_file() will now need to oideq upon each invocation, but that is trivial compared to the filesystem lookup or the pack index search required anyway. (And if find_cached_object() needs to do more because of previous invocations to pretend_object_file(), all the more reason to be consistent in whether we present cached objects.) Therefore, remove OBJECT_INFO_SKIP_CACHED.

[1] https://dart.googlesource.com/json_rpc_2

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
I put a lot of historical references which makes the commit message
rather long - let me know if you think that some can be omitted.
---
 object-store.h |  2 --
 sha1-file.c    | 38 ++++++++++++++++++--------------------
 2 files changed, 18 insertions(+), 22 deletions(-)

Jonathan Tan <jonathantanmy@google.com> writes:

That sounds like a bug. Shouldn't some objects like empty tree and empty blob whose names are hardcoded come internally without being fetched from anywhere?

OK, that bypassing already sounds wrong.  

Yup, that sounds like the right solution to the bug, with or without lazy cloning.

Hi,

Jonathan Tan wrote:

Ooh, I think there's something subtle hiding in this paragraph.

When I first read it, I thought you meant that the repositories are not self-contained --- that they contain references to the empty tree but do not fulfill "want"s for them. I don't believe that's what you mean, though.

My second reading is the repository genuinely doesn't contain the empty tree but different Git server implementations handle that differently. I tried to reproduce this with

	empty_tree=$(git mktree </dev/null)
	git init --bare x
	git clone --filter=blob:none file://$(pwd)/x y
	cd y
	echo hi >README
	git add README
	git commit -m 'nonempty tree'
	GIT_TRACE=1 git diff-tree "$empty_tree" HEAD

and indeed, it looks like Git serves the empty tree even from repositories that don't contain it. By comparison, JGit does not do the same trick. So we don't need to refer to a specific repository in the wild to reproduce this.

All that said, having to fetch this object in the first place is unexpected. The question of the promisor remote serving it is only relevant from the point of view of "why didn't we discover this sooner?"

Hm, where does this dichotomy come from? E.g. is the latter a lower-level function used by the former?

nit: on first reading I had trouble figuring out what "this issue" refers to here.

[...]

This might be easier to understand if phrased in terms of the intention behind the code instead of the specific call stacks used. See f06ab027 for an example of this kind of thing. For example:

  Applications within and outside of Git benefit from being able to
  assume that every repository contains the empty tree as an object
  (see, for example, commit 9abd46a347 "Make sure the empty tree
  exists when needed in merge-recursive", 2006-12-07).  To this end,
  since 346245a1bb (hard-code the empty tree object, 2008-02-13), Git
  has made the empty tree available in all repositories via
  find_cached_object, which all object access paths can use.

  Object existence checks (has_object_file), however, do not use
  find_cached_object.  <describe reason here>

  This particularly affects partial clones: has_object_file does not
  only report false in this case but contacts the promisor remote in
  order to obtain that answer.  The cost of these repeated negative
  lookups can add up.

  For example, in an optimization introduced in 090ea12671
  ("parse_object: avoid putting whole blob in core", 2012-03-07),
  object parsing uses has_object_file before read_object_file to check
  for a fast-path, so this negative lookup is triggered whenever we
  try to parse the absent empty tree.

When I state it this way, it's not obvious why this particular caller of has_object_file is more relevant than others. Did I miss some subtlety?

[...]

  If the promisor remote is running standard Git then it *does* have a
  copy of the empty tree, via the cached object itself.  This
  guarantee is not a documented part of the protocol, however, and
  other Git servers do not implement it.

Indeed.  Can we justify the change even more simply in those terms?

  Object existence checks (has_object_file), however, do not use
  find_cached_object.  <describe reason here>

  This makes the API unnecessarily difficult to reason about.
  Instead, let's consistently view the empty tree as a genuine part of
  the repository, even in has_object_file.  As a side effect, this
  allows us to simplify the common 'has_object_file ||
  find_cached_object' pattern to a more simple existence check.

[...]

Thanks for discussing the possible costs, and I agree that they're trivial relative to the I/O that these functions already incur.

[...]

As hinted above, we should be able to simplify away has_sha1_file || find_cached_object checks in this change.

Thanks and hpoe that helps, Jonathan

Yes, that's true. I'll reword it to emphasize the spurious fetching (and mention some implementations like JGit not serving those, which exacerbates the problem).

I think we didn't discover this sooner because not many people directly enter the empty tree on the command line :-) (but this is a problem that we should solve, most certainly).

I don't know the reason for the dichotomy - perhaps it was an oversight. The relevant commits are:

d66b37bb19 ("Add pretend_sha1_file() interface.", 2007-02-05) Adds a way to pretend that some objects are present by including them in a cache - empty-tree-pervasiveness is built on top of this later. Only read_sha1_file() was updated to make use of this; has_sha1_file() and sha1_object_info() were already present at this time, but were not updated. (Maybe the latter 2 had no need for pretending?)

346245a1bb ("hard-code the empty tree object", 2008-02-13) Empty tree pervasiveness built on top of the cache.

c4d9986f5f ("sha1_object_info: examine cached_object store too", 2011-02-07) sha1_object_info() was updated to use the cache. has_sha1_file() is never mentioned.

This particular caller is what caused us to notice this problem.

OK, let me see if I can rewrite it to emphasize the reasoning-about-API part. I still want to include the user-facing part that caused us to observe this problem, but I can deemphasize it.

This might be a moot point, but what do you mean by the "'has_object_file || find_cached_object' pattern"?

Jonathan Tan wrote:

Ah, that makes sense.

[...]

Oh! Thanks, I should have been more precise. And calling it a pattern was probably overreaching --- I can only find one instance, in pretend_object_file:

	if (has_object_file(oid) || find_cached_object(oid))
		return 0;

Since there's only one, I was on the wrong track. (Except that with this change, that can indeed change to

	if (has_object_file(oid))
		return 0;

Thanks, Jonathan

In a partial clone, if a user provides the hash of the empty tree ("git mktree </dev/null" - for SHA-1, this is 4b825d...) to a command which requires that that object be parsed, for example:

  git diff-tree 4b825d <a non-empty tree>

then Git will lazily fetch the empty tree, unnecessarily, because parsing of that object invokes repo_has_object_file(), which does not special-case the empty tree.

Instead, teach repo_has_object_file() to consult find_cached_object() (which handles the empty tree), thus bringing it in line with the rest of the object-store-accessing functions. A cost is that repo_has_object_file() will now need to oideq upon each invocation, but that is trivial compared to the filesystem lookup or the pack index search required anyway. (And if find_cached_object() needs to do more because of previous invocations to pretend_object_file(), all the more reason to be consistent in whether we present cached objects.)

As a historical note, the function now known as repo_read_object_file() was taught the empty tree in 346245a1bb ("hard-code the empty tree object", 2008-02-13), and the function now known as oid_object_info() was taught the empty tree in c4d9986f5f ("sha1_object_info: examine cached_object store too", 2011-02-07). repo_has_object_file() was never updated, perhaps due to oversight. The flag OBJECT_INFO_SKIP_CACHED, introduced later in dfdd4afcf9 ("sha1_file: teach sha1_object_info_extended more flags", 2017-06-26) and used in e83e71c5e1 ("sha1_file: refactor has_sha1_file_with_flags", 2017-06-26), was introduced to preserve this difference in empty-tree handling, but now it can be removed.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
Difference from v1: updated commit message in response to Jonathan
Nieder's feedback. Hopefully I didn't remove too much.
---
 object-store.h |  2 --
 sha1-file.c    | 38 ++++++++++++++++++--------------------
 2 files changed, 18 insertions(+), 22 deletions(-)

In a partial clone, if a user provides the hash of the empty tree ("git mktree </dev/null" - for SHA-1, this is 4b825d...) to a command which requires that that object be parsed, for example:

  git diff-tree 4b825d <a non-empty tree>

then Git will lazily fetch the empty tree, unnecessarily, because parsing of that object invokes repo_has_object_file(), which does not special-case the empty tree.

Instead, teach repo_has_object_file() to consult find_cached_object() (which handles the empty tree), thus bringing it in line with the rest of the object-store-accessing functions. A cost is that repo_has_object_file() will now need to oideq upon each invocation, but that is trivial compared to the filesystem lookup or the pack index search required anyway. (And if find_cached_object() needs to do more because of previous invocations to pretend_object_file(), all the more reason to be consistent in whether we present cached objects.)

As a historical note, the function now known as repo_read_object_file() was taught the empty tree in 346245a1bb ("hard-code the empty tree object", 2008-02-13), and the function now known as oid_object_info() was taught the empty tree in c4d9986f5f ("sha1_object_info: examine cached_object store too", 2011-02-07). repo_has_object_file() was never updated, perhaps due to oversight. The flag OBJECT_INFO_SKIP_CACHED, introduced later in dfdd4afcf9 ("sha1_file: teach sha1_object_info_extended more flags", 2017-06-26) and used in e83e71c5e1 ("sha1_file: refactor has_sha1_file_with_flags", 2017-06-26), was introduced to preserve this difference in empty-tree handling, but now it can be removed.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
Forgot to add v2 to the other email, so resending it with the correct
email subject.

Difference from v1: updated commit message in response to Jonathan
Nieder's feedback. Hopefully I didn't remove too much.
---
 object-store.h |  2 --
 sha1-file.c    | 38 ++++++++++++++++++--------------------
 2 files changed, 18 insertions(+), 22 deletions(-)

Jonathan Tan <jonathantanmy@google.com> writes:

I am not 100% sure if the implication of this change is safe to allow us to say "now it can be".

The has_object_file() helper wanted to say "no" when given a non-existing object registered via the pretend_object_file(), presumably because we wanted to allow a use pattern like:

 - prepare an in-core representation of an object we tentatively
   expect, but not absolutely sure, to be necessary.

 - perform operations, using the object data obtained via
   read_object() API, which is capable of yielding data even for
   such "pretend" objects (perhaps we are creating a tentative merge
   parents during a recursive merge).

 - write out final set of objects by enumerating those that do not
   really exist yet (via has_object_file() API).

Teaching about the empty tree to has_object_file() is a good thing (especially because we do not necessarily write an empty tree object to our repositories), but as a collateral damage of doing so, we make such use pattern impossible.

It is not a large loss---the third bullet in the above list can just be made to unconditionally call write_object_file() without filtering with has_object_file() and write_object_file() will apply the right optimization anyway, so it probably is OK.

Will queue.

Thanks.

On Thu, Jan 02, 2020 at 01:41:27PM -0800, Junio C Hamano wrote:

I agree that whoever called pretend_object_file() can be careful and write out the final set of objects itself via write_object_file(). But I'd worry a bit about a caller who doesn't necessarily realize that they need to do that. E.g., imagine we call pretend_object_file() for some blob oid, expecting it to be read-only. And then in the same process, some other bit of the code writes out a tree that mentions that blob. Oops, that tree is now corrupt after we exit the process. And IMHO neither the pretend-caller nor the tree-writer are to blame; the problem is that they shared global state they were not expecting.

This is pretty far-fetched given that the only user of pretend_object_file() is in git-blame right now. But it does give me pause. Overall, though, I'm more inclined to say that we should be dropping SKIP_CACHED here and considering pretend_object_file() to be a bit dangerous (i.e., to keep it in mind if somebody proposes more calls).

Another point of reference (in favor of Jonathan's patch):

  https://lore.kernel.org/git/20190304174053.GA27497@sigill.intra.peff.net/

is a bug that would not have happened if this patch had been applied (there's also some discussion of the greater issue, but nothing that wasn't already brought up here, I think).

-Peff

Jonathan Tan wrote:

Lovely, thank you.

Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

To follow up on Junio's hint in his review: callers can inject additional cached objects by using pretend_object_file. Junio described how this would make sense as a mechanism for building the virtual ancestor object, but we don't do that. In fact, the only caller is fake_working_tree_commit in "git blame", a read-only code path. *phew*

-- >8 --
Subject: sha1-file: document how to use pretend_object_file

Like in-memory alternates, pretend_object_file contains a trap for the unwary: careless callers can use it to create references to an object that does not exist in the on-disk object store.

Add a comment documenting how to use the function without risking such problems.

The only current caller is blame, which uses pretend_object_file to create an in-memory commit representing the working tree state. Noticed during a discussion of how to safely use this function in operations like "git merge" which, unlike blame, are not read-only.

Inspired-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 object-store.h | 8 ++++++++
 1 file changed, 8 insertions(+)

On Fri, Jan 03, 2020 at 04:13:31PM -0800, Jonathan Nieder wrote:

I think this is an improvement over the status quo, but it's still a potential trap for code which happens to run in the same process (see my other email in the thread).

Should the message perhaps be even more scary?

-Peff

Hi,

Jeff King wrote:

A pet peeve of mine is warning volume escalation: if it becomes common for us to say

 * Warning: callers are reponsible for [...]

then new warnings trying to stand out might say

 * WARNING: callers are responsible for [...]

and then after we are desensitized to that, we may switch to

 * WARNING WARNING WARNING, not the usual blah-blah: callers are

and so on. The main way I have found to counteract that is to make the "dangerous curve" markers context-specific enough that people don't learn to ignore them. After all, sometimes a concurrency warning is important to me, at other times warnings about clarity may be what attract my interest, and so on.

I don't have a good suggestion here. Perhaps "Callers are responsible for" is too slow and something more terse would help?

 /*
  * Adds an object to the in-memory object store, without writing it
  * to disk.
  *
  * Use with caution!  Unless you call write_object_file to record the
  * in-memory object to persistent storage, any other new objects that
  * reference it will point to a missing (in memory only) object,
  * resulting in a corrupt repository.
  */

It would be even better if we have some automated way to catch this kind of issue. Should tests run "git fsck" after each test? Should write_object_file have a paranoid mode that checks integrity?

I don't know an efficient way to do that. Ultimately I am comfortable counting on reviewers to be aware of this kind of pitfall. While nonlocal invariants are always hard to maintain, this pitfall is inherent in the semantics of the function, so I am not too worried that reviewers will overlook it.

A less error-prone interface would tie the result of pretend_object_file to a short-lived overlay on the_repository without affecting global state. We could even enforce read-only access in that overlay. I don't think the "struct repository" interface and callers are ready for that yet, though.

Thanks, Jonathan

On Mon, Jan 06, 2020 at 03:47:53PM -0800, Jonathan Nieder wrote:

I meant less about the number of capital letters, and more that we should be saying "this interface is dangerous; don't use it". Because it's not just "callers are responsible". It's "this can cause subtle and hard-to-debug issues because it's writing to global state".

My preferred solution would actually be to rip it out entirely, but we'd need some solution for git-blame, the sole caller. Possibly it could insert the value straight into the diff_filespec. But according to the thread that I linked earlier, I poked at that last year but it didn't look trivial.

Yeah, that's more what I had in mind.

Yeah, given the scope of the problem (we have a single caller, and this mechanism is over a decade old) I'm fine with review as the enforcement mechanism, too.

I agree that would be better, though it's still kind-of global (in that the repository object is effectively a global for most processes).

-Peff