Partial clone: promised blobs (formerly "missing blobs")

Currently, Git does not support repos with very large numbers of blobs or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every blob referenced by a tree object is available somewhere in the repo storage.

As a first step to reducing this problem, introduce the concept of promised blobs. Each Git repo can contain a list of promised blobs and their sizes at $GIT_DIR/objects/promisedblob. This patch contains functions to query them; functions for creating and modifying that file will be introduced in later patches.

A repository that is missing a blob but has that blob promised is not considered to be in error, so also teach fsck this.

+ * A mmap-ed byte array of size (missing_blob_nr * ENTRY_SIZE). Each
+ * ENTRY_SIZE-sized entry consists of the SHA-1 of the promised blob and its
+ * 64-bit size in network byte order. The entries are sorted in ascending SHA-1
+ * order.

promised-blob.c new file +15 -0

+int for_each_promised_blob(each_promised_blob_fn cb, void *data)
+{
+       struct object_id oid;
+       int i, r;
+
+       prepare_promised_blobs();
+       for (i = 0; i < promised_blob_nr; i++) {
+               memcpy(oid.hash, &promised_blobs[i * ENTRY_SIZE],
+                      GIT_SHA1_RAWSZ);
+               r = cb(&oid, data);
+               if (r)
+                       return r;
+       }
+       return 0;
+}

promised-blob.h new file +14 -0

new file mode 100644
index 000000000..a303ea1ff
@@ -0,0 +1,14 @@
+#ifndef PROMISED_BLOB_H
+#define PROMISED_BLOB_H
+
+/*
+ * Returns 1 if oid is the name of a promised blob. If size is not NULL, also
+ * returns its size.
+ */
+extern int is_promised_blob(const struct object_id *oid,
+                           unsigned long *size);
+
+typedef int each_promised_blob_fn(const struct object_id *oid, void *data);
+int for_each_promised_blob(each_promised_blob_fn, void *);
+
+#endif

t/t3907-promised-blob.sh new file +0 -0

new file mode 100755
index 000000000..827072004

Here I wondered what this file looks like, in a later patch you add documentation:

+objects/promisedblob::
+ This file records the sha1 object names and sizes of promised
+ blobs.
+

but that leaves more fundamental questions:
* Is that a list of sha1s, separated by LF? (CRLF? How would Windows users interact with it, are they supposed to ever modify this file?)
* Similar to .git/packed-refs, would we want to have a first line that has some sort of comment?
* In the first question I assumed a linear list, will that be a sorted list, or do we want to have some fancy data structure here?
(critbit tree, bloom filter)
* is the contents in ASCII or binary? (What are the separators?)
* In the future I presume we'd want to quickly answer "Is X in the promised blobs list?" so would it be possible (in the future) to improve the searching e.g. binary search?
* ... I'll read on to see my questions answered, but I'd guess others would prefer to see it in the docs. :)

Similar to other files, would we want to prefix the file with a 4 letter magic number and a version number?

Later down the road, do we want to have a (plumbing) command to move an object from standard blob to promised blob (as of now I'd think it would perform this rm call as well as an insert into the promised blobs file) ?
(Well, we'd also have to think about how to get objects out of a pack)

With such a command you can easily write your own custom filter to free up blobs again.

Quoted 1 line

+ test_must_fail git -C repo fsck

test_i18n_grep missing out ?

maybe, too? (Maybe that is already tested elsewhere, so no need for it)

Currently, Git does not support repos with very large numbers of blobs or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every blob referenced by a tree object is available somewhere in the repo storage.

As a first step to reducing this problem, introduce the concept of promised blobs. Each Git repo can contain a list of promised blobs and their sizes at $GIT_DIR/objects/promisedblob. This patch contains functions to query them; functions for creating and modifying that file will be introduced in later patches.

My primary concern is scale and managing the list of objects over time.

For
example, on the Windows repo we have (conservatively) 100M+ blobs (and growing). Assuming 28 bytes per, gives a 2.8GB list to be manipulated.

If I understand your proposal, newly-omitted blobs would need to be merged into the promised-blob list after each fetch. The fetch itself may not have that many new entries, but inserting them into the existing list will be slow.

In such a "sparse clone", it would be nice to omit unneeded tree objects
in addition to just blobs. I say that because we are finding with GVFS
on the Windows repo, that even with commits-and-trees-only filtering, the number of tree objects is overwhelming. So I'm also concerned about limiting the list to just blobs. If we need to have this list, it should be able to contain any object. (Suggesting having an object type in the entry.)

I assume that we'll also need a promised-blob.lock file to control access during list manipulation. This is already a sore spot with the index; I'd hate to create another one.

I also have to wonder about the need to have a complete list of omitted blobs up front. It may be better to just relax the consistency checks and assume a missing blob is "intentionally missing" rather than indicating a corruption somewhere.

And then let the client do a later
round-trip to either demand-load the object -or- demand-load the existence/size info if/when it really matters.

Maybe we should add a verb to your new fetch-blob endpoint to just get the size of one or more objects to help with this.

Hi,

Quoted 1 line · Jeff Hostetler

My primary concern is scale and managing the list of objects over time.

[...]

Quoted 8 lines

For
example, on the Windows repo we have (conservatively) 100M+ blobs (and growing). Assuming 28 bytes per, gives a 2.8GB list to be manipulated.

If I understand your proposal, newly-omitted blobs would need to be merged into the promised-blob list after each fetch. The fetch itself may not have that many new entries, but inserting them into the existing list will be slow.

This is a good point. An alternative would be to avoid storing the list and instead use a repository extension that treats all missing blobs in the repository similarly to promised blobs (with a weaker promise, where the server is allowed to return 404). The downsides:

- blob sizes are not available without an additional request, e.g. for directory listings

- the semantics of has_object_file become more complicated. If it is allowed to return false for omitted blobs, then callers have to be audited to tolerate that and try to look up the blob anyway. If it has to contact the server to find out whether an omitted blob is available, then callers have to be audited to skip this expensive operation when possible.

- similarly, the semantics of sha1_object_info{,_extended} become more complicated. If they are allowed to return -1 for omitted blobs, then callers have to be audited to handle that. If they have to contact the server to find the object type and size, it becomes expensive in a way that affects callers.

- causes futile repeated requests to the server for objects that don't exist. Caching negative lookups is fussy because a later push could cause those objects to exist --- though it should be possible for fetches to invalidate entries in such a cache using the list of promised blobs sent by the server.

[...]

Quoted 7 lines

In such a "sparse clone", it would be nice to omit unneeded tree objects
in addition to just blobs. I say that because we are finding with GVFS
on the Windows repo, that even with commits-and-trees-only filtering, the number of tree objects is overwhelming. So I'm also concerned about limiting the list to just blobs. If we need to have this list, it should be able to contain any object. (Suggesting having an object type in the entry.)

Would it work to have a separate lists of blobs and trees (either in separate files or in the same file)?

One option would be to add a version number / magic string to the start of the file. That would allow making format changes later without a proliferation of distinct repository extensions.

[...]

Quoted 3 lines

I assume that we'll also need a promised-blob.lock file to control access during list manipulation. This is already a sore spot with the index; I'd hate to create another one.

Can you say more about this concern? My experience with concurrent fetches has already not been great (since one fetch process is not aware of what the other has fetched) --- is your concern that the promised-blob facility would affect pushes as well some day?

Quoted 4 lines

I also have to wonder about the need to have a complete list of omitted blobs up front. It may be better to just relax the consistency checks and assume a missing blob is "intentionally missing" rather than indicating a corruption somewhere.

We've discussed this previously on list and gone back and forth. :)

Quoted 3 lines

And then let the client do a later
round-trip to either demand-load the object -or- demand-load the existence/size info if/when it really matters.

The cost of demand-loading this existence/size information is what ultimately convinced me of this approach.

But I can see how the tradeoffs differ between the omit-large-blobs case and the omit-all-blobs case. We might end up having to support both modes. :(

Quoted 2 lines

Maybe we should add a verb to your new fetch-blob endpoint to just get the size of one or more objects to help with this.

No objections from me, though we don't need it yet.

Thanks,
Jonathan

Quoted 36 lines · Jonathan Nieder

Hi,

Quoted 1 line · Jeff Hostetler

My primary concern is scale and managing the list of objects over time.

[...]

Quoted 8 lines

For
example, on the Windows repo we have (conservatively) 100M+ blobs (and growing). Assuming 28 bytes per, gives a 2.8GB list to be manipulated.

If I understand your proposal, newly-omitted blobs would need to be merged into the promised-blob list after each fetch. The fetch itself may not have that many new entries, but inserting them into the existing list will be slow.

This is a good point. An alternative would be to avoid storing the list and instead use a repository extension that treats all missing blobs in the repository similarly to promised blobs (with a weaker promise, where the server is allowed to return 404). The downsides:

- blob sizes are not available without an additional request, e.g. for directory listings

- the semantics of has_object_file become more complicated. If it is allowed to return false for omitted blobs, then callers have to be audited to tolerate that and try to look up the blob anyway. If it has to contact the server to find out whether an omitted blob is available, then callers have to be audited to skip this expensive operation when possible.

- similarly, the semantics of sha1_object_info{,_extended} become more complicated. If they are allowed to return -1 for omitted blobs, then callers have to be audited to handle that. If they have to contact the server to find the object type and size, it becomes expensive in a way that affects callers.

Quoted 5 lines

- causes futile repeated requests to the server for objects that don't exist. Caching negative lookups is fussy because a later push could cause those objects to exist --- though it should be possible for fetches to invalidate entries in such a cache using the list of promised blobs sent by the server.

Also good points. :-)

Would it be better to:
[] let fetch-pack/index-pack on the client compute the set of missing
objects based upon the commit range in the response.
[] build a "pack-<id>.promised" as a peer of the "pack-<id>.[pack,idx]"
files.
[] Use Jonathan's binary format with (-1LL) for the sizes, but also add
a flags/object-type word. Since the local commit/object traversal usually knows the type of object (either by context or the mode field in the parent entry), index-pack can set it immediately.
[] Repack would "do the right thing" when building new packfiles from
existing packfiles (and merge/prune/etc. a new promise file).

Conceptually, these "pack-<id>.promised" files would be read-only once created, like the corresponding .pack/.idx files. But since we have a fixed record size, we could let the dynamic object size requests update
the sizes in-place. (And if an update failed for some reason, the
client could just go on and use the result (as we do when trying to update mtime info in the index).)

This gives us the full set of omitted objects without the network overhead and without the overhead of merging them into a single list. And we defer the cost of getting an object's size until we actually need the info.

Quoted 9 lines

[...]

Quoted 7 lines

In such a "sparse clone", it would be nice to omit unneeded tree objects
in addition to just blobs. I say that because we are finding with GVFS
on the Windows repo, that even with commits-and-trees-only filtering, the number of tree objects is overwhelming. So I'm also concerned about limiting the list to just blobs. If we need to have this list, it should be able to contain any object. (Suggesting having an object type in the entry.)

Quoted 6 lines

Would it work to have a separate lists of blobs and trees (either in separate files or in the same file)?

One option would be to add a version number / magic string to the start of the file. That would allow making format changes later without a proliferation of distinct repository extensions.

As I suggested above, we could just put them in the same file with a flags/object-type field.

Without getting too nerdy here, we could even say that the size doesn't need to be a int:64 -- definitely bigger than int:32, but we don't need the full int:64. We could make the size a int:40 or int:48 and use the rest of the QWORD for flags/object-type.

Quoted 9 lines

[...]

Quoted 3 lines

I assume that we'll also need a promised-blob.lock file to control access during list manipulation. This is already a sore spot with the index; I'd hate to create another one.

Can you say more about this concern? My experience with concurrent fetches has already not been great (since one fetch process is not aware of what the other has fetched) --- is your concern that the promised-blob facility would affect pushes as well some day?

[I wrote this before I wrote the multi-peer-file suggestion above.]

I'm assuming that anyone adding a new promised-blob to the single file will use the standard "read foo, write foo.lock, rename" trick. If we have a large number of omitted blobs, this file will be large and the insert will take a non-trivial amount of time.

Concurrent fetches does sound a bit silly, so we only have to worry about the time to copy the bits on disk.

If other operations (such as demand loading missing blobs in a log or diff) need to remove promised-blobs from the list as they create loose blobs, then they will get stuck on the lock. I suppose we could just say that the promised-blob list may have false-positives in it (because lookups in it won't happen until the packed and loose objects have been searched and failed) and just wait for GC to clean it.

And there's always that stale lock problem where something dies holding the lock and doesn't delete it.

Some of these could be addressed with a DB or something that allows incremental and atomic updates rather than a regular index-like flat file, but I don't want to dive into that here.

Quoted 11 lines

Quoted 4 lines

I also have to wonder about the need to have a complete list of omitted blobs up front. It may be better to just relax the consistency checks and assume a missing blob is "intentionally missing" rather than indicating a corruption somewhere.

We've discussed this previously on list and gone back and forth. :)

Quoted 3 lines

And then let the client do a later
round-trip to either demand-load the object -or- demand-load the existence/size info if/when it really matters.

Quoted 6 lines

The cost of demand-loading this existence/size information is what ultimately convinced me of this approach.

But I can see how the tradeoffs differ between the omit-large-blobs case and the omit-all-blobs case. We might end up having to support both modes. :(

I think I've been in both camps myself.

I'm not sure it would be that hard to support both (other than being unfortunate), assuming pack-objects could build the same binary data as I suggested be computed by fetch-pack/index-pack above. It could then just be a run-time decision.

I could even see it being useful -- do the initial clone with client-side computation (because you're getting mostly ancient data that you don't care about) and then let fetches use server-side computation (because you're more likely to care about the sizes of objects near your branch heads).

Quoted 4 lines

Quoted 2 lines

Maybe we should add a verb to your new fetch-blob endpoint to just get the size of one or more objects to help with this.

No objections from me, though we don't need it yet.

My primary concern is scale and managing the list of objects over time.

My fear is that this list will be quite large. If we only want to omit the very large blobs, then maybe not. But if we want to expand that scope to also omit other objects (such as a clone synchronized with a sparse checkout), then that list will get large on large repos. For example, on the Windows repo we have (conservatively) 100M+ blobs (and growing). Assuming 28 bytes per, gives a 2.8GB list to be manipulated.

If I understand your proposal, newly-omitted blobs would need to be merged into the promised-blob list after each fetch. The fetch itself may not have that many new entries, but inserting them into the existing list will be slow. Also, mmap'ing and bsearch'ing will likely have issues. And there's likely to be a very expensive step to remove entries from the list as new blobs are received (or locally created).

In such a "sparse clone", it would be nice to omit unneeded tree objects
in addition to just blobs. I say that because we are finding with GVFS
on the Windows repo, that even with commits-and-trees-only filtering, the number of tree objects is overwhelming.

So I'm also concerned about
limiting the list to just blobs. If we need to have this list, it should be able to contain any object. (Suggesting having an object type in the entry.)

I also have to wonder about the need to have a complete list of omitted blobs up front. It may be better to just relax the consistency checks and assume a missing blob is "intentionally missing" rather than indicating a corruption somewhere. And then let the client do a later round-trip to either demand-load the object -or- demand-load the existence/size info if/when it really matters.

Maybe we should add a verb to your new fetch-blob endpoint to just get the size of one or more objects to help with this.

Quoted 16 lines · On Wed, 12 Jul 2017 13:29:11 -0400 Jeff Hostetler <[email protected]> wrote:

My primary concern is scale and managing the list of objects over time.

My fear is that this list will be quite large. If we only want to omit the very large blobs, then maybe not. But if we want to expand that scope to also omit other objects (such as a clone synchronized with a sparse checkout), then that list will get large on large repos. For example, on the Windows repo we have (conservatively) 100M+ blobs (and growing). Assuming 28 bytes per, gives a 2.8GB list to be manipulated.

If I understand your proposal, newly-omitted blobs would need to be merged into the promised-blob list after each fetch. The fetch itself may not have that many new entries, but inserting them into the existing list will be slow. Also, mmap'ing and bsearch'ing will likely have issues. And there's likely to be a very expensive step to remove entries from the list as new blobs are received (or locally created).

Quoted 4 lines

In such a "sparse clone", it would be nice to omit unneeded tree objects
in addition to just blobs. I say that because we are finding with GVFS
on the Windows repo, that even with commits-and-trees-only filtering, the number of tree objects is overwhelming.

I know that discussion has shifted to the possibility of not having this list at all, and not sending size information together with the fetch, but going back to this...maybe omitting trees *is* the solution to both the large local list and the large amount of size information needing to be transferred.

So the large-blob (e.g. Android) and many-blob (e.g. Windows) cases would look like this:

* Large-blob repositories have no trees omitted and a few blobs omitted, and we have sizes for all of them.
* Many-blob repositories have many trees omitted and either all blobs omitted (and we have size information for them, useful for FUSE or FUSE-like things, for example) or possibly no blobs omitted (for example, if shallow clones are going to be the norm, there won't be many blobs to begin with if trees are omitted).

This seems better than an intermediate solution for the many-blob repository case in which we still keep all the trees but also try to avoid sending and storing as much information about the blobs as possible, because that doesn't seem to provide us with much savings (because the trees as a whole are just as large, if not larger, than the blob information).

Quoted 4 lines

So I'm also concerned about
limiting the list to just blobs. If we need to have this list, it should be able to contain any object. (Suggesting having an object type in the entry.)

This makes sense - I'll add it in.

Quoted 7 lines

I also have to wonder about the need to have a complete list of omitted blobs up front. It may be better to just relax the consistency checks and assume a missing blob is "intentionally missing" rather than indicating a corruption somewhere. And then let the client do a later round-trip to either demand-load the object -or- demand-load the existence/size info if/when it really matters.

Quoted 2 lines

Maybe we should add a verb to your new fetch-blob endpoint to just get the size of one or more objects to help with this.

If we allow the omission of trees, I don't think the added complexity of demand-loading sizes is worth it.

What do you think of doing this:
* add a "type" field to the list of promised objects (formerly the list of promised blobs)
* retain mandatory size for blobs
* retain single file containing list of promised objects (I don't feel too strongly about this, but it has a slight simplicity and in-between-GC performance advantage)

Quoted 9 lines · Jonathan Tan

I know that discussion has shifted to the possibility of not having this list at all, and not sending size information together with the fetch, but going back to this...maybe omitting trees *is* the solution to both the large local list and the large amount of size information needing to be transferred.

So the large-blob (e.g. Android) and many-blob (e.g. Windows) cases would look like this:

Quoted 7 lines

* Large-blob repositories have no trees omitted and a few blobs omitted, and we have sizes for all of them.
* Many-blob repositories have many trees omitted and either all blobs omitted (and we have size information for them, useful for FUSE or FUSE-like things, for example) or possibly no blobs omitted (for example, if shallow clones are going to be the norm, there won't be many blobs to begin with if trees are omitted).

I'm not sure I understand what you're saying here. Does omitting a tree object change the set of blob sizes we receive? Are you saying that if we omit a tree, then we implicitly omit all the blobs it references and don't send size info those blobs? So that the local list only has reachable objects? So faulting-in a tree would also have to send size info for the newly referenced blobs?

Would this make it more similar to a shallow clone (in that none of the have_object tests work for items beyond the cut point) ?

For the former case, if you just have a few omitted objects, then a second round-trip to mget their sizes isn't that much work.

I think for the latter, forcing a full promise-list on clone is just too much data to send -- data that we likely won't ever need.

Quoted 7 lines

What do you think of doing this:
* add a "type" field to the list of promised objects (formerly the list of promised blobs)
* retain mandatory size for blobs
* retain single file containing list of promised objects (I don't feel too strongly about this, but it has a slight simplicity and in-between-GC performance advantage)

The single promise-set is problematic. I think it will grow too large (in our case) and will need all the usual lock juggling and merging.

I still prefer my suggestion for a per-packfile promise-set for all of the reasons I stated the other day. This can be computed quickly during index-pack, is (nearly) read-only, and doesn't require the whole file rewrite lock file. It also has the benefit of being portable -- in that I can also copy the .promise file if I copy the .pack and .idx file to another repo.

In a subsequent patch, sha1_file will need to append object names in the form of "unsigned char *" to oid arrays. Teach sha1-array support for that.

Signed-off-by Jonathan Tan <[email protected]>

Quoted 5 lines · Jonathan Tan

In a subsequent patch, sha1_file will need to append object names in the form of "unsigned char *" to oid arrays. Teach sha1-array support for that.

Signed-off-by Jonathan Tan <[email protected]>

This breaks the oid/sha1 barrier?

I would have expected the caller to do a

  oid_array_append_oid(&array, sha1_to_oid(sha1));

with sha1_to_oid working off some static memory, such that the call to oid_array_append_oid (which we have as oid_array_append) is just as cheap?

Could you say more in the commit message on why we collude sha1 and oids here?

Quoted 5 lines · On Tue, 11 Jul 2017 15:06:11 -0700 Stefan Beller <[email protected]> wrote:

Quoted 4 lines · Jonathan Tan

In a subsequent patch, sha1_file will need to append object names in the form of "unsigned char *" to oid arrays. Teach sha1-array support for that.

Quoted 3 lines

Quoted 1 line

Signed-off-by Jonathan Tan <[email protected]>

This breaks the oid/sha1 barrier?

Not sure what you mean by this. This patch is meant to be a change to make "unsigned char *"-using code able to create/modify oid arrays, while we migrate away from "unsigned char *" - I don't know of any barrier.

Teach sha1_file to invoke a hook whenever a blob is requested and unavailable but is promised. The hook is a shell command that can be configured through "git config"; this hook takes in a list of hashes and writes (if successful) the corresponding objects to the repo's local storage.

This is meant as a temporary measure to ensure that all Git commands work in such a situation. Future patches will update some commands to either tolerate promised blobs (without invoking the hook) or be more efficient in invoking the promised blob hook.

In order to determine the code changes in sha1_file.c necessary, I investigated the following:
(1) functions in sha1_file that take in a hash, without the user regarding how the object is stored (loose or packed)
(2) functions in sha1_file that operate on packed objects (because I need to check callers that know about the loose/packed distinction and operate on both differently, and ensure that they can handle the concept of objects that are neither loose nor packed)

(1) is handled by the modification to sha1_object_info_extended().

For (2), I looked at for_each_packed_object and at the packed-related functions that take in a hash. For for_each_packed_object, the callers either already work or are fixed in this patch:
- reachable - only to find recent objects
- builtin/fsck - already knows about promised blobs
- builtin/cat-file - fixed in this commit

Callers of the other functions do not need to be changed:
- parse_pack_index
- http - indirectly from http_get_info_packs
- find_pack_entry_one
- this searches a single pack that is provided as an argument; the caller already knows (through other means) that the sought object is in a specific pack
- find_sha1_pack
- fast-import - appears to be an optimization to not store a file if it is already in a pack
- http-walker - to search through a struct alt_base
- http-push - to search through remote packs
- has_sha1_pack
- builtin/fsck - already knows about promised blobs
- builtin/count-objects - informational purposes only (check if loose object is also packed)
- builtin/prune-packed - check if object to be pruned is packed (if not, don't prune it)
- revision - used to exclude packed objects if requested by user
- diff - just for optimization

An alternative design that I considered but rejected:

- Adding a hook whenever a packed blob is requested, not on any blob. That is, whenever we attempt to search the packfiles for a blob, if it is missing (from the packfiles and from the loose object storage), to invoke the hook (which must then store it as a packfile), open the packfile the hook generated, and report that the blob is found in that new packfile. This reduces the amount of analysis needed (in that we only need to look at how packed blobs are handled), but requires that the hook generate packfiles (or for sha1_file to pack whatever loose objects are generated), creating one packfile for each missing blob and potentially very many packfiles that must be linearly searched. This may be tolerable now for repos that only have a few missing blobs (for example, repos that only want to exclude large blobs), and might be tolerable in the future if we have batching support for the most commonly used commands, but is not tolerable now for repos that exclude a large amount of blobs.

Signed-off-by Jonathan Tan <[email protected]>

+/*
+ * If any of the given blobs are promised blobs, invokes
+ * core.promisedblobcommand with those blobs and returns the number of blobs
+ * requested. No check is made as to whether the invocation actually populated
+ * the repository with the promised blobs.
+ *
+ * If none of the given blobs are promised blobs, this function does not invoke
+ * anything and returns 0.

+ */

promised-blob.h +2 -0

+int request_promised_blobs(const struct oid_array *blobs);
+
 #endif

sha1_file.c +17 -13

index 5862386cd..5778a6dbd 100644
@@ -28,6 +28,11 @@
 #include "list.h"
 #include "mergesort.h"
 #include "quote.h"
+#include "iterator.h"
+#include "dir-iterator.h"
+#include "sha1-lookup.h"
+#include "promised-blob.h"
+#include "sha1-array.h"
 
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }

@@ -2983,6 +2988,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
        const unsigned char *real = (flags & OBJECT_INFO_LOOKUP_REPLACE) ?
                                    lookup_replace_object(sha1) :
                                    sha1;
+       int already_retried = 0;
 
        if (!oi)
                oi = &blank_oi;

@@ -3007,30 +3013,40 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
                }
        }
 
-       if (!find_pack_entry(real, &e)) {
-               /* Most likely it's a loose object. */
-               if (!sha1_loose_object_info(real, oi, flags)) {
-                       oi->whence = OI_LOOSE;
-                       return 0;
-               }
+retry:
+       if (find_pack_entry(real, &e))
+               goto found_packed;
 
-               /* Not a loose object; someone else may have just packed it. */
-               if (flags & OBJECT_INFO_QUICK) {
-                       return -1;
-               } else {
-                       reprepare_packed_git();
-                       if (!find_pack_entry(real, &e))
-                               return -1;
+       /* Most likely it's a loose object. */
+       if (!sha1_loose_object_info(real, oi, flags)) {
+               oi->whence = OI_LOOSE;
+               return 0;
+       }
+
+       /* Not a loose object; someone else may have just packed it. */
+       reprepare_packed_git();

Teach sha1_file to invoke a hook whenever a blob is requested and unavailable but is promised. The hook is a shell command that can be configured through "git config"; this hook takes in a list of hashes and writes (if successful) the corresponding objects to the repo's local storage.

This is meant as a temporary measure to ensure that all Git commands work in such a situation. Future patches will update some commands to either tolerate promised blobs (without invoking the hook) or be more efficient in invoking the promised blob hook.

In order to determine the code changes in sha1_file.c necessary, I investigated the following:
(1) functions in sha1_file that take in a hash, without the user regarding how the object is stored (loose or packed)
(2) functions in sha1_file that operate on packed objects (because I need to check callers that know about the loose/packed distinction and operate on both differently, and ensure that they can handle the concept of objects that are neither loose nor packed)

(1) is handled by the modification to sha1_object_info_extended().

For (2), I looked at for_each_packed_object and at the packed-related functions that take in a hash. For for_each_packed_object, the callers either already work or are fixed in this patch:
- reachable - only to find recent objects
- builtin/fsck - already knows about promised blobs
- builtin/cat-file - fixed in this commit

Callers of the other functions do not need to be changed:
- parse_pack_index
- http - indirectly from http_get_info_packs
- find_pack_entry_one
- this searches a single pack that is provided as an argument; the caller already knows (through other means) that the sought object is in a specific pack
- find_sha1_pack
- fast-import - appears to be an optimization to not store a file if it is already in a pack
- http-walker - to search through a struct alt_base
- http-push - to search through remote packs
- has_sha1_pack
- builtin/fsck - already knows about promised blobs
- builtin/count-objects - informational purposes only (check if loose object is also packed)
- builtin/prune-packed - check if object to be pruned is packed (if not, don't prune it)
- revision - used to exclude packed objects if requested by user
- diff - just for optimization

An alternative design that I considered but rejected:

- Adding a hook whenever a packed blob is requested, not on any blob. That is, whenever we attempt to search the packfiles for a blob, if it is missing (from the packfiles and from the loose object storage), to invoke the hook (which must then store it as a packfile), open the packfile the hook generated, and report that the blob is found in that new packfile. This reduces the amount of analysis needed (in that we only need to look at how packed blobs are handled), but requires that the hook generate packfiles (or for sha1_file to pack whatever loose objects are generated), creating one packfile for each missing blob and potentially very many packfiles that must be linearly searched. This may be tolerable now for repos that only have a few missing blobs (for example, repos that only want to exclude large blobs), and might be tolerable in the future if we have batching support for the most commonly used commands, but is not tolerable now for repos that exclude a large amount of blobs.

Signed-off-by Jonathan Tan <[email protected]>

---
  Documentation/config.txt               |  8 ++++
  Documentation/gitrepository-layout.txt |  8 ++++
  builtin/cat-file.c                     |  9 ++++
  promised-blob.c                        | 75 ++++++++++++++++++++++++++++++++++
  promised-blob.h                        | 13 ++++++
  sha1_file.c                            | 44 +++++++++++++-------
  t/t3907-promised-blob.sh               | 36 ++++++++++++++++
  7 files changed, 179 insertions(+), 14 deletions(-)

Documentation/config.txt +8 -0

index d5c9c4cab..c293ac921 100644
@@ -393,6 +393,14 @@ The default is false, except linkgit:git-clone[1] or linkgit:git-init[1]
  will probe and set core.ignoreCase true if appropriate when the repository
  is created.
 
+core.promisedBlobCommand::
+	If set, whenever a blob in the local repo is attempted to be read, but
+	is both missing and a promised blob, invoke this shell command to
+	generate or obtain that blob before reporting an error. This shell
+	command should take one or more hashes, each terminated by a newline,
+	as standard input, and (if successful) should write the corresponding
+	objects to the local repo (packed or loose).
+
  core.precomposeUnicode::
  	This option is only used by Mac OS implementation of Git.
  	When core.precomposeUnicode=true, Git reverts the unicode decomposition

Documentation/gitrepository-layout.txt +8 -0

index f51ed4e37..0ef9312fa 100644
@@ -47,6 +47,10 @@ use with dumb transports but otherwise is OK as long as
  `objects/info/alternates` points at the object stores it
  borrows from.
  +
+. You could have blobs that are merely promised by another source. When
+Git requires those blobs, it will invoke the command in the
+`core.promisedBlobCommand` configuration variable.
++
  This directory is ignored if $GIT_COMMON_DIR is set and
  "$GIT_COMMON_DIR/objects" will be used instead.
 

@@ -91,6 +95,10 @@ objects/info/http-alternates::
  	this object store borrows objects from, to be used when
  	the repository is fetched over HTTP.
 
+objects/promisedblob::
+	This file records the sha1 object names and sizes of promised
+	blobs.
+
  refs::
  	References are stored in subdirectories of this
  	directory.  The 'git prune' command knows to preserve

builtin/cat-file.c +9 -0

index 96b786e48..3df00bf91 100644
@@ -12,6 +12,7 @@
  #include "streaming.h"
  #include "tree-walk.h"
  #include "sha1-array.h"
+#include "promised-blob.h"
 
  struct batch_options {
  	int enabled;

@@ -432,6 +433,13 @@ static int batch_packed_object(const struct object_id *oid,
  	return 0;
  }
 
+static int batch_promised_blob(const struct object_id *oid,
+			       void *data)
+{
+	oid_array_append(data, oid);
+	return 0;
+}
+
  static int batch_objects(struct batch_options *opt)
  {
  	struct strbuf buf = STRBUF_INIT;

@@ -473,6 +481,7 @@ static int batch_objects(struct batch_options *opt)
 
  		for_each_loose_object(batch_loose_object, &sa, 0);
  		for_each_packed_object(batch_packed_object, &sa, 0);
+		for_each_promised_blob(batch_promised_blob, &sa);
 
  		cb.opt = opt;
  		cb.expand = &data;

promised-blob.c +75 -0

index 493808ed2..0fe04daf2 100644
@@ -2,6 +2,9 @@
  #include "promised-blob.h"
  #include "sha1-lookup.h"
  #include "strbuf.h"
+#include "run-command.h"
+#include "sha1-array.h"
+#include "config.h"
 
  #define ENTRY_SIZE (GIT_SHA1_RAWSZ + 8)
  /*

@@ -93,3 +96,75 @@ int for_each_promised_blob(each_promised_blob_fn cb, void *data)
  	}
  	return 0;
  }
+
+static char *promised_blob_command;
+
+static int promised_blob_config(const char *conf_key, const char *value,
+				void *cb)
+{
+	if (!strcmp(conf_key, "core.promisedblobcommand")) {
+		promised_blob_command = xstrdup(value);
+	}
+	return 0;
+}
+
+static void ensure_promised_blob_configured(void)
+{
+	static int configured;
+	if (configured)
+		return;
+	git_config(promised_blob_config, NULL);
+	configured = 1;
+}
+
+int request_promised_blobs(const struct oid_array *blobs)
+{
+	struct child_process cp = CHILD_PROCESS_INIT;
+	const char *argv[] = {NULL, NULL};
+	const char *env[] = {"GIT_IGNORE_PROMISED_BLOBS=1", NULL};
+	int blobs_requested = 0;
+	int i;
+
+	for (i = 0; i < blobs->nr; i++) {
+		if (is_promised_blob(&blobs->oid[i], NULL))
+			break;
+	}
+
+	if (i == blobs->nr)
+		/* Nothing to fetch */
+		return 0;
+
+	ensure_promised_blob_configured();
+	if (!promised_blob_command)
+		die("some promised blobs need to be fetched, but\n"
+		    "no core.promisedblobcommand configured");
+
+	argv[0] = promised_blob_command;
+	cp.argv = argv;
+	cp.env = env;
+	cp.use_shell = 1;
+	cp.in = -1;
+
+	if (start_command(&cp))
+		die("failed to start <%s>", promised_blob_command);
+
+	for (; i < blobs->nr; i++) {
+		if (is_promised_blob(&blobs->oid[i], NULL)) {
+			write_in_full(cp.in, oid_to_hex(&blobs->oid[i]),
+				      GIT_SHA1_HEXSZ);
+			write_in_full(cp.in, "\n", 1);
+			blobs_requested++;
+		}
+	}
+	close(cp.in);
+
+	if (finish_command(&cp))
+		die("failed to finish <%s>", promised_blob_command);
+
+	/*
+	 * The command above may have updated packfiles, so update our record
+	 * of them.
+	 */
+	reprepare_packed_git();
+	return blobs_requested;
+}

promised-blob.h +13 -0

index a303ea1ff..34b1d3f9e 100644
@@ -1,6 +1,8 @@
  #ifndef PROMISED_BLOB_H
  #define PROMISED_BLOB_H
 
+#include "sha1-array.h"
+
  /*
   * Returns 1 if oid is the name of a promised blob. If size is not NULL, also
   * returns its size.

@@ -11,4 +13,15 @@ extern int is_promised_blob(const struct object_id *oid,
  typedef int each_promised_blob_fn(const struct object_id *oid, void *data);
  int for_each_promised_blob(each_promised_blob_fn, void *);
 
+/*
+ * If any of the given blobs are promised blobs, invokes
+ * core.promisedblobcommand with those blobs and returns the number of blobs
+ * requested. No check is made as to whether the invocation actually populated
+ * the repository with the promised blobs.
+ *
+ * If none of the given blobs are promised blobs, this function does not invoke
+ * anything and returns 0.
+ */
+int request_promised_blobs(const struct oid_array *blobs);
+
  #endif

sha1_file.c +30 -14

index 5862386cd..5778a6dbd 100644
@@ -28,6 +28,11 @@
  #include "list.h"
  #include "mergesort.h"
  #include "quote.h"
+#include "iterator.h"
+#include "dir-iterator.h"
+#include "sha1-lookup.h"
+#include "promised-blob.h"
+#include "sha1-array.h"
 
  #define SZ_FMT PRIuMAX
  static inline uintmax_t sz_fmt(size_t s) { return s; }

@@ -2983,6 +2988,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
  	const unsigned char *real = (flags & OBJECT_INFO_LOOKUP_REPLACE) ?
  				    lookup_replace_object(sha1) :
  				    sha1;
+	int already_retried = 0;
 
  	if (!oi)
  		oi = &blank_oi;

@@ -3007,30 +3013,40 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
  		}
  	}
 
-	if (!find_pack_entry(real, &e)) {
-		/* Most likely it's a loose object. */
-		if (!sha1_loose_object_info(real, oi, flags)) {
-			oi->whence = OI_LOOSE;
-			return 0;
-		}
+retry:
+	if (find_pack_entry(real, &e))
+		goto found_packed;
 
-		/* Not a loose object; someone else may have just packed it. */
-		if (flags & OBJECT_INFO_QUICK) {
-			return -1;
-		} else {
-			reprepare_packed_git();
-			if (!find_pack_entry(real, &e))
-				return -1;
+	/* Most likely it's a loose object. */
+	if (!sha1_loose_object_info(real, oi, flags)) {
+		oi->whence = OI_LOOSE;
+		return 0;
+	}
+
+	/* Not a loose object; someone else may have just packed it. */
+	reprepare_packed_git();
+	if (find_pack_entry(real, &e))
+		goto found_packed;
+
+	/* Check if it is a promised blob */
+	if (!already_retried) {
+		struct oid_array promised = OID_ARRAY_INIT;
+		oid_array_append_sha1(&promised, real);
+		if (request_promised_blobs(&promised)) {
+			already_retried = 1;
+			goto retry;
  		}
  	}
 
+	return -1;
+
+found_packed:
  	if (oi == &blank_oi)
  		/*
  		 * We know that the caller doesn't actually need the
  		 * information below, so return early.
  		 */
  		return 0;
-
  	rtype = packed_object_info(e.p, e.offset, oi);
  	if (rtype < 0) {
  		mark_bad_packed_object(e.p, real);

t/t3907-promised-blob.sh +36 -0

index 827072004..778afd1f6 100755
@@ -26,4 +26,40 @@ test_expect_success '...but fails again with GIT_IGNORE_PROMISED_BLOBS' '
  	unset GIT_IGNORE_PROMISED_BLOBS
  '
 
+test_expect_success 'sha1_object_info_extended (through git cat-file)' '
+	rm -rf server client &&
+
+	git init server &&
+	test_commit -C server 1 1.t abcdefgh &&
+	HASH=$(git hash-object server/1.t) &&
+
+	git init client &&
+	git -C client config core.promisedblobcommand \
+		"git -C \"$(pwd)/server\" pack-objects --stdout |
+		 git unpack-objects" &&
+	
+	test_must_fail git -C client cat-file -p "$HASH"
+'
+
+test_expect_success '...succeeds if it is a promised blob' '
+	printf "%s%016x" "$HASH" "$(wc -c <server/1.t)" |
+		hex_pack >client/.git/objects/promisedblob &&
+	git -C client cat-file -p "$HASH"
+'
+
+test_expect_success 'cat-file --batch-all-objects with promised blobs' '
+	rm -rf client &&
+
+	git init client &&
+	git -C client config core.promisedblobcommand \
+		"git -C \"$(pwd)/server\" pack-objects --stdout |
+		 git unpack-objects" &&
+	printf "%s%016x" "$HASH" "$(wc -c <server/1.t)" |
+		hex_pack >client/.git/objects/promisedblob &&
+
+	# Verify that the promised blob is printed
+	git -C client cat-file --batch --batch-all-objects | tee out |
+		grep abcdefgh
+'
+
  test_done

Quoted 5 lines · Jonathan Tan

Teach sha1_file to invoke a hook whenever a blob is requested and unavailable but is promised. The hook is a shell command that can be configured through "git config"; this hook takes in a list of hashes and writes (if successful) the corresponding objects to the repo's local storage.

This would seem to work well for promised blobs but does it currently support other object types? In our large mono repos, we have to support missing commits and trees as well.

There are a couple of related patch series in flight that are playing in this area. We should definitely coordinate these various efforts.

These patches are part of a set of patches implementing partial clone, as you can see here:

https://github.com/jonathantanmy/git/tree/partialclone

In that branch, clone with batch checkout works, as you can see in the README. The code and tests are generally done, but some patches are still missing documentation and commit messages.

These 3 patches implement the foundational concept - formerly known as "missing blobs" in the "missing blob manifest", I decided to call them "promised blobs". The repo knows their object names and sizes. It also does not have the blobs themselves, but can be configured to know how to fetch them.

An older version of these patches was sent as a single demonstration patch in versions 1 to 3 of [1]. In there, Junio suggested that I have only one file containing missing blob information. I have made that suggested change in this version.

One thing remaining is to add a repository extension [2] so that older versions of Git fail immediately instead of trying to read missing blobs, but I thought I'd send these first in order to get some initial feedback.

[1] https://public-inbox.org/git/[email protected]/
[2] Documentation/technical/repository-version.txt

Jonathan Tan (3):
promised-blob, fsck: introduce promised blobs
sha1-array: support appending unsigned char hash
sha1_file: add promised blob hook support

Documentation/config.txt               |   8 ++
Documentation/gitrepository-layout.txt |   8 ++
Makefile                               |   1 +
builtin/cat-file.c                     |   9 ++
builtin/fsck.c                         |  13 +++
promised-blob.c                        | 170 
+++++++++++++++++++++++++++++++++
promised-blob.h                        |  27 ++++++
sha1-array.c                           |   7 ++
sha1-array.h                           |   1 +
sha1_file.c                            |  44 ++++++---
t/t3907-promised-blob.sh               |  65 +++++++++++++
t/test-lib-functions.sh                |   6 ++
12 files changed, 345 insertions(+), 14 deletions(-)

create mode 100644 promised-blob.c
create mode 100644 promised-blob.h
create mode 100755 t/t3907-promised-blob.sh

Signature · 1 line

2.13.2.932.g7449e964c-goog

From: "Jonathan Tan" <[email protected]>
Sent: Tuesday, July 11, 2017 8:48 PM

Quoted 9 lines

These patches are part of a set of patches implementing partial clone, as you can see here:

https://github.com/jonathantanmy/git/tree/partialclone

In that branch, clone with batch checkout works, as you can see in the README. The code and tests are generally done, but some patches are still missing documentation and commit messages.

Quoted 6 lines

These 3 patches implement the foundational concept - formerly known as "missing blobs" in the "missing blob manifest", I decided to call them "promised blobs". The repo knows their object names and sizes. It also does not have the blobs themselves, but can be configured to know how to fetch them.

If I understand correctly, this method doesn't give any direct user visibility of missing blobs in the file system. Is that correct?

I was hoping that eventually the various 'on demand' approaches would still allow users to continue to work as they go off-line such that they can see directly (in the FS) where the missing blobs (and trees) are located, so that they can continue to commit new work on existing files.

I had felt that some sort of 'gitlink' should be present (huma readable) as a place holder for the missing blob/tree. e.g. 'gitblob: 1234abcd' (showing the missing oid, jsut like sub-modules can do - it's no different really.

I'm concerned that the various GVFS extensions haven't fully achieved a separation of concerns surrounding the DVCS capability for on-line/off-line conversion as comms drop in and out. The GVFS looks great for a fully networked, always on, environment, but it would be good to also have the sepration for those who (will) have shallow/narrow clones that may also need to work with a local upstream that is also shallow/narrow.

Signature · 2 lines

Philip
I wanted to at least get my thoughts into the discussion before it all passes by.

Quoted 40 lines

An older version of these patches was sent as a single demonstration patch in versions 1 to 3 of [1]. In there, Junio suggested that I have only one file containing missing blob information. I have made that suggested change in this version.

One thing remaining is to add a repository extension [2] so that older versions of Git fail immediately instead of trying to read missing blobs, but I thought I'd send these first in order to get some initial feedback.

[1] https://public-inbox.org/git/[email protected]/

[2] Documentation/technical/repository-version.txt

Jonathan Tan (3):
promised-blob, fsck: introduce promised blobs
sha1-array: support appending unsigned char hash
sha1_file: add promised blob hook support

Documentation/config.txt               |   8 ++
Documentation/gitrepository-layout.txt |   8 ++
Makefile                               |   1 +
builtin/cat-file.c                     |   9 ++
builtin/fsck.c                         |  13 +++
promised-blob.c                        | 170 
+++++++++++++++++++++++++++++++++
promised-blob.h                        |  27 ++++++
sha1-array.c                           |   7 ++
sha1-array.h                           |   1 +
sha1_file.c                            |  44 ++++++---
t/t3907-promised-blob.sh               |  65 +++++++++++++
t/test-lib-functions.sh                |   6 ++
12 files changed, 345 insertions(+), 14 deletions(-)

create mode 100644 promised-blob.c
create mode 100644 promised-blob.h
create mode 100755 t/t3907-promised-blob.sh

Signature · 1 line

2.13.2.932.g7449e964c-goog

Quoted 11 lines

From: "Jonathan Tan" <[email protected]>
Sent: Tuesday, July 11, 2017 8:48 PM

Quoted 9 lines

These patches are part of a set of patches implementing partial clone, as you can see here:

https://github.com/jonathantanmy/git/tree/partialclone

In that branch, clone with batch checkout works, as you can see in the README. The code and tests are generally done, but some patches are still missing documentation and commit messages.

Quoted 7 lines

Quoted 6 lines

These 3 patches implement the foundational concept - formerly known as "missing blobs" in the "missing blob manifest", I decided to call them "promised blobs". The repo knows their object names and sizes. It also does not have the blobs themselves, but can be configured to know how to fetch them.

If I understand correctly, this method doesn't give any direct user visibility of missing blobs in the file system. Is that correct?

That is correct

Quoted 3 lines

I was hoping that eventually the various 'on demand' approaches would still allow users to continue to work as they go off-line such that they can see directly (in the FS) where the missing blobs (and trees) are located, so that they can continue to commit new work on existing files.

This is a challenge as git assumes all objects are always available (that is a key design principal of a DVCS) so any missing object is considered a corruption that typically results in a call to "die."

The GVFS solution gets around this by ensuring any missing object is retrieved on behalf of git so that it never sees it as missing. The obvious tradeoff is that this requires a network connection so the object can be retrieved.

Quoted 3 lines

I had felt that some sort of 'gitlink' should be present (huma readable) as a place holder for the missing blob/tree. e.g. 'gitblob: 1234abcd' (showing the missing oid, jsut like sub-modules can do - it's no different really.

We explored that option briefly but when you have a large number of files, even writing out some sort of place holder can take a very long time. In fact, since the typical source file is relatively small (a few kilobytes), writing out a placeholder doesn't save much time vs just writing out the actual file contents.

Another challenge is that even if there is a placeholder written to disk, you still need a network connection to retrieve the actual contents if/when it is needed.

Quoted 3 lines

I'm concerned that the various GVFS extensions haven't fully achieved a separation of concerns surrounding the DVCS capability for on-line/off-line conversion as comms drop in and out. The GVFS looks great for a fully networked, always on, environment, but it would be good to also have the sepration for those who (will) have shallow/narrow clones that may also need to work with a local upstream that is also shallow/narrow.

You are correct that this hasn't been tackled yet. It is a challenging problem. I can envision something along the lines of what was done for the shallow clone feature where there are distinct ways to change the set of objects that are available but that would hopefully come in some future patch series.

Quoted 45 lines

Signature · 3 lines

-- 
Philip
I wanted to at least get my thoughts into the discussion before it all passes by.

Quoted 39 lines

An older version of these patches was sent as a single demonstration patch in versions 1 to 3 of [1]. In there, Junio suggested that I have only one file containing missing blob information. I have made that suggested change in this version.

One thing remaining is to add a repository extension [2] so that older versions of Git fail immediately instead of trying to read missing blobs, but I thought I'd send these first in order to get some initial feedback.

[1] https://public-inbox.org/git/[email protected]/
[2] Documentation/technical/repository-version.txt

Jonathan Tan (3):
promised-blob, fsck: introduce promised blobs
sha1-array: support appending unsigned char hash
sha1_file: add promised blob hook support

Documentation/config.txt               |   8 ++
Documentation/gitrepository-layout.txt |   8 ++
Makefile                               |   1 +
builtin/cat-file.c                     |   9 ++
builtin/fsck.c                         |  13 +++
promised-blob.c                        | 170 
+++++++++++++++++++++++++++++++++
promised-blob.h                        |  27 ++++++
sha1-array.c                           |   7 ++
sha1-array.h                           |   1 +
sha1_file.c                            |  44 ++++++---
t/t3907-promised-blob.sh               |  65 +++++++++++++
t/test-lib-functions.sh                |   6 ++
12 files changed, 345 insertions(+), 14 deletions(-)

create mode 100644 promised-blob.c
create mode 100644 promised-blob.h
create mode 100755 t/t3907-promised-blob.sh

Signature · 1 line

2.13.2.932.g7449e964c-goog

From: "Jonathan Tan" <[email protected]>

Quoted 4 lines

These patches are part of a set of patches implementing partial clone, as you can see here:

https://github.com/jonathantanmy/git/tree/partialclone

If I understand correctly, this method doesn't give any direct user visibility of missing blobs in the file system. Is that correct?

I was hoping that eventually the various 'on demand' approaches would still allow users to continue to work as they go off-line such that they can see directly (in the FS) where the missing blobs (and trees) are located, so that they can continue to commit new work on existing files.

I had felt that some sort of 'gitlink' should be present (huma readable) as a place holder for the missing blob/tree. e.g. 'gitblob: 1234abcd' (showing the missing oid, jsut like sub-modules can do - it's no different really.

Hi Philip,

Quoted 6 lines · Philip Oakley

From: "Jonathan Tan" <[email protected]>

Quoted 4 lines

These patches are part of a set of patches implementing partial clone, as you can see here:

https://github.com/jonathantanmy/git/tree/partialclone

[...]

Quoted 9 lines

If I understand correctly, this method doesn't give any direct user visibility of missing blobs in the file system. Is that correct?

I was hoping that eventually the various 'on demand' approaches would still allow users to continue to work as they go off-line such that they can see directly (in the FS) where the missing blobs (and trees) are located, so that they can continue to commit new work on existing files.

Quoted 4 lines

I had felt that some sort of 'gitlink' should be present (huma readable) as a place holder for the missing blob/tree. e.g. 'gitblob: 1234abcd' (showing the missing oid, jsut like sub-modules can do - it's no different really.

That's a reasonable thing to want, but it's a little different from the use cases that partial clone work so far has aimed to support. They are:

A. Avoiding downloading all blobs (and likely trees as well) that are
not needed in the current operation (e.g. checkout). This blends well with the sparse checkout feature, which allows the current checkout to be fairly small in a large repository.

GVFS uses a trick that makes it a little easier to widen a sparse checkout upon access of a directory. But the same building blocks should work fine with a sparse checkout that has been set up explicitly.

B. Avoiding downloading large blobs, except for those needed in the
current operation (e.g. checkout).

When not using sparse checkout, the main benefit out of the box is avoiding downloading *historical versions* of large blobs.

It sounds like you are looking for a sort of placeholder outside the sparse checkout area.

In a way, that's orthogonal to these patches:
even if you have all relevant blobs, you may want to avoid inflating them to check them out and reading them to compare to the index (i.e. the usual benefits of sparse checkout).

In a sparse checkout, you
still might like to be able to get a listing of files outside the sparse area (which you can get with "git ls-tree") and you may even want to be able to get such a listing with plain "ls" (as with your proposal).

Thanks and hope that helps,
Jonathan

The "used" field in struct object is only used by builtin/fsck. Remove that field and modify builtin/fsck to use a flag instead.

Quoted 2 lines · Jonathan Tan

The "used" field in struct object is only used by builtin/fsck. Remove that field and modify builtin/fsck to use a flag instead.

The patch looks good to me (I would even claim this could go in as an independent cleanup, not tied to the RFCish nature of the later patches), though I have a question:
How did you select 0x0008 for USED, i.e. does it collide with other flags (theoretically?), and if so how do we make sure to avoid the collusion in
the future?

Quoted 11 lines · On Wed, 19 Jul 2017 17:36:39 -0700 Stefan Beller <[email protected]> wrote:

Quoted 2 lines · Jonathan Tan

The "used" field in struct object is only used by builtin/fsck. Remove that field and modify builtin/fsck to use a flag instead.

The patch looks good to me (I would even claim this could go in as an independent cleanup, not tied to the RFCish nature of the later patches), though I have a question:
How did you select 0x0008 for USED, i.e. does it collide with other flags (theoretically?), and if so how do we make sure to avoid the collusion in
the future?

Thanks. 0x0008 was the next one in the series (as you can see in the context). As for whether it collides with other flags, that is what the chart in object.h is for (which I have added to in this patch), I presume. As far as I can tell, each component must make sure not to overlap with any other component running concurrently.

The "used" field in struct object is only used by builtin/fsck. Remove that field and modify builtin/fsck to use a flag instead.

Signed-off-by Jonathan Tan <[email protected]>

---
 builtin/fsck.c | 24 ++++++++++++++----------
 object.c       |  1 -
 object.h       |  2 +-
 3 files changed, 15 insertions(+), 12 deletions(-)

Currently, Git does not support repos with very large numbers of objects or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every referenced object is available somewhere in the repo storage.

As a first step to reducing this problem, introduce the concept of promised objects. Each Git repo can contain a list of promised objects and their sizes (if blobs) at $GIT_DIR/objects/promised. This patch contains functions to query them; functions for creating and modifying that file will be introduced in later patches.

A repository that is missing an object but has that object promised is not considered to be in error, so also teach fsck this. As part of doing this, object.{h,c} has been modified to generate "struct object" based on only the information available to promised objects, without requiring the object itself.

Signed-off-by Jonathan Tan <[email protected]>

---
 Documentation/technical/repository-version.txt |   6 ++
 Makefile                                       |   1 +
 builtin/fsck.c                                 |  18 +++-
 cache.h                                        |   2 +
 environment.c                                  |   1 +
 fsck.c                                         |   6 +-
 object.c                                       |  19 ++++
 object.h                                       |  19 ++++
 promised-object.c                              | 130 +++++++++++++++++++++++++
 promised-object.h                              |  22 +++++
 setup.c                                        |   7 +-
 t/t3907-promised-object.sh                     |  41 ++++++++
 t/test-lib-functions.sh                        |   6 ++
 13 files changed, 273 insertions(+), 5 deletions(-)
 create mode 100644 promised-object.c
 create mode 100644 promised-object.h
 create mode 100755 t/t3907-promised-object.sh

Documentation/technical/repository-version.txt +6 -0

index 00ad37986..f8b82c1c7 100644
@@ -86,3 +86,9 @@ for testing format-1 compatibility.
 When the config key `extensions.preciousObjects` is set to `true`,
 objects in the repository MUST NOT be deleted (e.g., by `git-prune` or
 `git repack -d`).
+
+`promisedObjects`
+~~~~~~~~~~~~~~~~~
+
+(Explain this - basically a string containing a command to be run
+whenever a missing object needs to be fetched.)

Makefile +1 -0

index 9c9c42f8f..c1446d5ef 100644
@@ -828,6 +828,7 @@ LIB_OBJS += preload-index.o
 LIB_OBJS += pretty.o
 LIB_OBJS += prio-queue.o
 LIB_OBJS += progress.o
+LIB_OBJS += promised-object.o
 LIB_OBJS += prompt.o
 LIB_OBJS += quote.o
 LIB_OBJS += reachable.o

builtin/fsck.c +10 -2

index 462b8643b..49e21f361 100644
@@ -15,6 +15,7 @@
 #include "progress.h"
 #include "streaming.h"
 #include "decorate.h"
+#include "promised-object.h"
 
 #define REACHABLE 0x0001
 #define SEEN      0x0002

@@ -44,6 +45,7 @@ static int name_objects;
 #define ERROR_REACHABLE 02
 #define ERROR_PACK 04
 #define ERROR_REFS 010
+#define ERROR_PROMISED_OBJECT 011
 
 static const char *describe_object(struct object *obj)
 {

@@ -436,7 +438,7 @@ static int fsck_handle_ref(const char *refname, const struct object_id *oid,
 {
        struct object *obj;
 
-       obj = parse_object(oid);
+       obj = parse_or_promise_object(oid);
        if (!obj) {
                error("%s: invalid sha1 pointer %s", refname, oid_to_hex(oid));
                errors_found |= ERROR_REACHABLE;

@@ -592,7 +594,7 @@ static int fsck_cache_tree(struct cache_tree *it)
                fprintf(stderr, "Checking cache tree\n");
 
        if (0 <= it->entry_count) {
-               struct object *obj = parse_object(&it->oid);
+               struct object *obj = parse_or_promise_object(&it->oid);
                if (!obj) {
                        error("%s: invalid sha1 pointer in cache-tree",
                              oid_to_hex(&it->oid));

@@ -635,6 +637,12 @@ static int mark_packed_for_connectivity(const struct object_id *oid,
        return 0;
 }
 
+static int mark_have_promised_object(const struct object_id *oid, void *data)
+{
+       mark_object_for_connectivity(oid);
+       return 0;
+}
+
 static char const * const fsck_usage[] = {
        N_("git fsck [<options>] [<object>...]"),
        NULL

builtin/fsck.c +7 -0

+test_expect_success 'fsck fails on missing objects' '
+       test_create_repo repo &&
+
+       test_commit -C repo 1 &&
+       test_commit -C repo 2 &&
+       test_commit -C repo 3 &&
+       git -C repo tag -a annotated_tag -m "annotated tag" &&

builtin/fsck.c int cmd_fsck(int argc, const char **argv, const char *prefix) · line 704

Quoted 4 lines

builtin/fsck.c +4 -0

+       if (fsck_promised_objects()) {
+               error("Errors found in promised object list");
+               errors_found |= ERROR_PROMISED_OBJECT;
+       }

This got me thinking: It is an error if we do not have an object and also do not promise it, but what about the other case:
having and object and promising it, too?
That is not harmful to the operation, except that the promise machinery may be slower due to its size. (Should that be a soft warning then? Do we have warnings in fsck?)

Quoted 2 lines

* The object type is stored in 3 bits.
*/

We may want to remove this comment while we're here as it sounds stale despite being technically correct. 1974632c66 (Remove TYPE_* constant macros and use object_type enums consistently., 2006-07-11)

object.h struct object_array { · line 59

Quoted 12 lines

struct object {

object.h +10 -0

+       /*
+        * Set if this object is parsed. If set, "type" is populated and this
+        * object can be casted to "struct commit" or an equivalent.
+        */
        unsigned parsed : 1;
+       /*
+        * Set if this object is not in the repo but is promised. If set,
+        * "type" is populated, but this object cannot be casted to "struct
+        * commit" or an equivalent.
+        */
+       unsigned promised : 1;

Would it make sense to have a bit field instead:

#define STATE_BITS 2
#define STATE_PARSED (1<<0)
#define STATE_PROMISED (1<<1)

unsigned state : STATE_BITS

This would be similar to the types and flags?

Quoted 12 lines

t/t3907-promised-object.sh new file +12 -0

+test_expect_success 'fsck fails on missing objects' '
+       test_create_repo repo &&
+
+       test_commit -C repo 1 &&
+       test_commit -C repo 2 &&
+       test_commit -C repo 3 &&
+       git -C repo tag -a annotated_tag -m "annotated tag" &&
+       C=$(git -C repo rev-parse 1) &&
+       T=$(git -C repo rev-parse 2^{tree}) &&
+       B=$(git hash-object repo/3.t) &&
+       AT=$(git -C repo rev-parse annotated_tag) &&
+

t/t3907-promised-object.sh line 23

Quoted 5 lines

t/t3907-promised-object.sh new file +5 -0

+       # missing commit, tree, blob, and tag
+       rm repo/.git/objects/$(echo $C | cut -c1-2)/$(echo $C | cut -c3-40) &&
+       rm repo/.git/objects/$(echo $T | cut -c1-2)/$(echo $T | cut -c3-40) &&
+       rm repo/.git/objects/$(echo $B | cut -c1-2)/$(echo $B | cut -c3-40) &&
+       rm repo/.git/objects/$(echo $AT | cut -c1-2)/$(echo $AT | cut -c3-40) &&

This is a pretty cool test as it promises all sorts of objects from different parts of the graph.

Currently, Git does not support repos with very large numbers of objects or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every referenced object is available somewhere in the repo storage.

As a first step to reducing this problem, introduce the concept of promised objects. Each Git repo can contain a list of promised objects and their sizes (if blobs) at $GIT_DIR/objects/promised. This patch contains functions to query them; functions for creating and modifying that file will be introduced in later patches.

A repository that is missing an object but has that object promised is not considered to be in error, so also teach fsck this. As part of doing this, object.{h,c} has been modified to generate "struct object" based on only the information available to promised objects, without requiring the object itself.

Signed-off-by Jonathan Tan <[email protected]>

---
  Documentation/technical/repository-version.txt |   6 ++
  Makefile                                       |   1 +
  builtin/fsck.c                                 |  18 +++-
  cache.h                                        |   2 +
  environment.c                                  |   1 +
  fsck.c                                         |   6 +-
  object.c                                       |  19 ++++
  object.h                                       |  19 ++++
  promised-object.c                              | 130 +++++++++++++++++++++++++
  promised-object.h                              |  22 +++++
  setup.c                                        |   7 +-
  t/t3907-promised-object.sh                     |  41 ++++++++
  t/test-lib-functions.sh                        |   6 ++
  13 files changed, 273 insertions(+), 5 deletions(-)

create mode 100644 promised-object.c
create mode 100644 promised-object.h
create mode 100755 t/t3907-promised-object.sh

Documentation/technical/repository-version.txt +6 -0

index 00ad37986..f8b82c1c7 100644
@@ -86,3 +86,9 @@ for testing format-1 compatibility.
  When the config key `extensions.preciousObjects` is set to `true`,
  objects in the repository MUST NOT be deleted (e.g., by `git-prune` or
  `git repack -d`).
+
+`promisedObjects`
+~~~~~~~~~~~~~~~~~
+
+(Explain this - basically a string containing a command to be run
+whenever a missing object needs to be fetched.)

Makefile +1 -0

index 9c9c42f8f..c1446d5ef 100644
@@ -828,6 +828,7 @@ LIB_OBJS += preload-index.o
  LIB_OBJS += pretty.o
  LIB_OBJS += prio-queue.o
  LIB_OBJS += progress.o
+LIB_OBJS += promised-object.o
  LIB_OBJS += prompt.o
  LIB_OBJS += quote.o
  LIB_OBJS += reachable.o

builtin/fsck.c +16 -2

index 462b8643b..49e21f361 100644
@@ -15,6 +15,7 @@
  #include "progress.h"
  #include "streaming.h"
  #include "decorate.h"
+#include "promised-object.h"
 
  #define REACHABLE 0x0001
  #define SEEN      0x0002

@@ -44,6 +45,7 @@ static int name_objects;
  #define ERROR_REACHABLE 02
  #define ERROR_PACK 04
  #define ERROR_REFS 010
+#define ERROR_PROMISED_OBJECT 011
 
  static const char *describe_object(struct object *obj)
  {

@@ -436,7 +438,7 @@ static int fsck_handle_ref(const char *refname, const struct object_id *oid,
  {
  	struct object *obj;
 
-	obj = parse_object(oid);
+	obj = parse_or_promise_object(oid);
  	if (!obj) {
  		error("%s: invalid sha1 pointer %s", refname, oid_to_hex(oid));
  		errors_found |= ERROR_REACHABLE;

@@ -592,7 +594,7 @@ static int fsck_cache_tree(struct cache_tree *it)
  		fprintf(stderr, "Checking cache tree\n");
 
  	if (0 <= it->entry_count) {
-		struct object *obj = parse_object(&it->oid);
+		struct object *obj = parse_or_promise_object(&it->oid);
  		if (!obj) {
  			error("%s: invalid sha1 pointer in cache-tree",
  			      oid_to_hex(&it->oid));

@@ -635,6 +637,12 @@ static int mark_packed_for_connectivity(const struct object_id *oid,
  	return 0;
  }
 
+static int mark_have_promised_object(const struct object_id *oid, void *data)
+{
+	mark_object_for_connectivity(oid);
+	return 0;
+}
+
  static char const * const fsck_usage[] = {
  	N_("git fsck [<options>] [<object>...]"),
  	NULL

@@ -690,6 +698,11 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
 
  	git_config(fsck_config, NULL);
 
+	if (fsck_promised_objects()) {
+		error("Errors found in promised object list");
+		errors_found |= ERROR_PROMISED_OBJECT;
+	}
+
  	fsck_head_link();
  	if (connectivity_only) {
  		for_each_loose_object(mark_loose_for_connectivity, NULL, 0);

@@ -727,6 +740,7 @@ int cmd_fsck(int argc, const char **argv, const char *prefix)
  			stop_progress(&progress);
  		}
  	}
+	for_each_promised_object(mark_have_promised_object, NULL);
 
  	heads = 0;
  	for (i = 0; i < argc; i++) {

cache.h +2 -0

index 71fe09264..dd94b5ffc 100644
@@ -853,10 +853,12 @@ extern int grafts_replace_parents;
  #define GIT_REPO_VERSION 0
  #define GIT_REPO_VERSION_READ 1
  extern int repository_format_precious_objects;
+extern char *repository_format_promised_objects;
 
  struct repository_format {
  	int version;
  	int precious_objects;
+	char *promised_objects;
  	int is_bare;
  	char *work_tree;
  	struct string_list unknown_extensions;

environment.c +1 -0

index 3fd4b1084..82658470d 100644
@@ -27,6 +27,7 @@ int warn_ambiguous_refs = 1;
  int warn_on_object_refname_ambiguity = 1;
  int ref_paranoia = -1;
  int repository_format_precious_objects;
+char *repository_format_promised_objects;
  const char *git_commit_encoding;
  const char *git_log_output_encoding;
  const char *apply_default_whitespace;

fsck.c +4 -2

index b4204d772..f08ff0675 100644
@@ -460,8 +460,10 @@ int fsck_walk(struct object *obj, void *data, struct fsck_options *options)
  	if (!obj)
  		return -1;
 
-	if (obj->type == OBJ_NONE)
-		parse_object(&obj->oid);
+	if (!obj->parsed && !obj->promised)
+		parse_or_promise_object(&obj->oid);
+	if (obj->promised)
+		return 0;
 
  	switch (obj->type) {
  	case OBJ_BLOB:

object.c +19 -0

index 321d7e920..0aeb95084 100644
@@ -4,6 +4,7 @@
  #include "tree.h"
  #include "commit.h"
  #include "tag.h"
+#include "promised-object.h"
 
  static struct object **obj_hash;
  static int nr_objs, obj_hash_size;

@@ -141,6 +142,7 @@ void *create_object(const unsigned char *sha1, void *o)
  	struct object *obj = o;
 
  	obj->parsed = 0;
+	obj->promised = 0;
  	obj->flags = 0;
  	hashcpy(obj->oid.hash, sha1);
 

@@ -279,6 +281,23 @@ struct object *parse_object(const struct object_id *oid)
  	return NULL;
  }
 
+struct object *parse_or_promise_object(const struct object_id *oid)
+{
+	enum object_type type;
+
+	if (has_object_file(oid))
+		return parse_object(oid);
+
+	if (is_promised_object(oid, &type, NULL)) {
+		struct object *obj = lookup_unknown_object(oid->hash);
+		obj->promised = 1;
+		obj->type = type;
+		return obj;
+	}
+
+	return NULL;
+}
+
  struct object_list *object_list_insert(struct object *item,
  				       struct object_list **list_p)
  {

object.h +19 -0

index 0a419ba8d..640c8bff1 100644
@@ -46,7 +46,17 @@ struct object_array {
   * The object type is stored in 3 bits.
   */
  struct object {
+	/*
+	 * Set if this object is parsed. If set, "type" is populated and this
+	 * object can be casted to "struct commit" or an equivalent.
+	 */
  	unsigned parsed : 1;
+	/*
+	 * Set if this object is not in the repo but is promised. If set,
+	 * "type" is populated, but this object cannot be casted to "struct
+	 * commit" or an equivalent.
+	 */
+	unsigned promised : 1;
  	unsigned type : TYPE_BITS;
  	unsigned flags : FLAG_BITS;
  	struct object_id oid;

@@ -104,6 +114,15 @@ struct object *parse_object_or_die(const struct object_id *oid, const char *name
   */
  struct object *parse_object_buffer(const struct object_id *oid, enum object_type type, unsigned long size, void *buffer, int *eaten_p);
 
+/*
+ * Returns the object, having parsed it if possible. In the returned object,
+ * either "parsed" or "promised" will be set.
+ *
+ * Returns NULL if the object is missing and not promised, or if the object is
+ * corrupt.
+ */
+struct object *parse_or_promise_object(const struct object_id *oid);
+
  /** Returns the object, with potentially excess memory allocated. **/
  struct object *lookup_unknown_object(const unsigned  char *sha1);
 

promised-object.c new file +130 -0

new file mode 100644
index 000000000..487ade437
@@ -0,0 +1,130 @@
+#include "cache.h"
+#include "promised-object.h"
+#include "sha1-lookup.h"
+#include "strbuf.h"
+
+#define ENTRY_SIZE (GIT_SHA1_RAWSZ + 1 + 8)
+/*
+ * A mmap-ed byte array of size (promised_object_nr * ENTRY_SIZE). Each
+ * ENTRY_SIZE-sized entry consists of the SHA-1 of the promised object, its
+ * 8-bit object type, and its 64-bit size in network byte order. The entries
+ * are sorted in ascending SHA-1 order.
+ */
+static char *promised_objects;
+static int64_t promised_object_nr = -1;
+
+static void prepare_promised_objects(void)
+{
+	char *filename;
+	int fd;
+	struct stat st;
+
+	if (promised_object_nr >= 0)
+		return;
+
+	if (!repository_format_promised_objects ||
+	    getenv("GIT_IGNORE_PROMISED_OBJECTS")) {
+		promised_object_nr = 0;
+		return;
+	}
+
+	filename = xstrfmt("%s/promised", get_object_directory());
+	fd = git_open(filename);
+	if (fd < 0) {
+		if (errno == ENOENT) {
+			promised_object_nr = 0;
+			goto cleanup;
+		}
+		perror("prepare_promised_objects");
+		die("Could not open %s", filename);
+	}
+	if (fstat(fd, &st)) {
+		perror("prepare_promised_objects");
+		die("Could not stat %s", filename);
+	}
+	if (st.st_size == 0) {
+		promised_object_nr = 0;
+		goto cleanup;
+	}
+	if (st.st_size % ENTRY_SIZE) {
+		die("Size of %s is not a multiple of %d", filename, ENTRY_SIZE);
+	}
+
+	promised_objects = xmmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	promised_object_nr = st.st_size / ENTRY_SIZE;
+
+cleanup:
+	free(filename);
+	if (fd >= 0)
+		close(fd);
+}
+
+int is_promised_object(const struct object_id *oid, enum object_type *type,
+		       unsigned long *size)
+{
+	int result;
+
+	prepare_promised_objects();
+	result = sha1_entry_pos(promised_objects, ENTRY_SIZE, 0, 0,
+				promised_object_nr, promised_object_nr,
+				oid->hash);
+	if (result >= 0) {
+		if (type) {
+			char *ptr = promised_objects +
+				    result * ENTRY_SIZE + GIT_SHA1_RAWSZ;
+			*type = *ptr;
+		}
+		if (size) {
+			uint64_t size_nbo;
+			char *ptr = promised_objects +
+				    result * ENTRY_SIZE + GIT_SHA1_RAWSZ + 1;
+			memcpy(&size_nbo, ptr, sizeof(size_nbo));
+			*size = ntohll(size_nbo);
+		}
+		return 1;
+	}
+	return 0;
+}
+
+int for_each_promised_object(each_promised_object_fn cb, void *data)
+{
+	struct object_id oid;
+	int i, r;
+
+	prepare_promised_objects();
+	for (i = 0; i < promised_object_nr; i++) {
+		memcpy(oid.hash, &promised_objects[i * ENTRY_SIZE],
+		       GIT_SHA1_RAWSZ);
+		r = cb(&oid, data);
+		if (r)
+			return r;
+	}
+	return 0;
+}
+
+int fsck_promised_objects(void)
+{
+	int i;
+	prepare_promised_objects();
+	for (i = 0; i < promised_object_nr; i++) {
+		enum object_type type;
+		if (i != 0 && memcmp(&promised_objects[(i - 1) * ENTRY_SIZE],
+				     &promised_objects[i * ENTRY_SIZE],
+				     GIT_SHA1_RAWSZ) >= 0)
+			return error("Error in list of promised objects: not "
+				     "in ascending order of object name");
+		type = promised_objects[i * ENTRY_SIZE + GIT_SHA1_RAWSZ];
+		switch (type) {
+			case OBJ_BLOB:
+			case OBJ_TREE:
+			case OBJ_COMMIT:
+			case OBJ_TAG:
+				break;
+			default:
+				return error("Error in list of promised "
+					     "objects: found object of type %d",
+					     type);
+		}
+	}
+	return 0;
+}

promised-object.h new file +22 -0

new file mode 100644
index 000000000..7eaedff17
@@ -0,0 +1,22 @@
+#ifndef PROMISED_OBJECT_H
+#define PROMISED_OBJECT_H
+
+#include "cache.h"
+
+/*
+ * Returns 1 if oid is the name of a promised object. For non-blobs, 0 is
+ * reported as their size.
+ */
+int is_promised_object(const struct object_id *oid, enum object_type *type,
+		       unsigned long *size);
+
+typedef int each_promised_object_fn(const struct object_id *oid, void *data);
+int for_each_promised_object(each_promised_object_fn, void *);
+
+/*
+ * Returns 0 if there is no list of promised objects or if the list of promised
+ * objects is valid.
+ */
+int fsck_promised_objects(void);
+
+#endif

setup.c +6 -1

index 860507e1f..36022452f 100644
@@ -425,7 +425,11 @@ static int check_repo_format(const char *var, const char *value, void *vdata)
  			;
  		else if (!strcmp(ext, "preciousobjects"))
  			data->precious_objects = git_config_bool(var, value);
-		else
+		else if (!strcmp(ext, "promisedobjects")) {
+			if (!value)
+				return config_error_nonbool(var);
+			data->promised_objects = xstrdup(value);
+		} else
  			string_list_append(&data->unknown_extensions, ext);
  	} else if (strcmp(var, "core.bare") == 0) {
  		data->is_bare = git_config_bool(var, value);

@@ -468,6 +472,7 @@ static int check_repository_format_gently(const char *gitdir, int *nongit_ok)
  	}
 
  	repository_format_precious_objects = candidate.precious_objects;
+	repository_format_promised_objects = candidate.promised_objects;
  	string_list_clear(&candidate.unknown_extensions, 0);
  	if (!has_common) {
  		if (candidate.is_bare != -1) {

t/t3907-promised-object.sh new file +41 -0

new file mode 100755
index 000000000..3e0caf4f9
@@ -0,0 +1,41 @@
+#!/bin/sh
+
+test_description='promised objects'
+
+. ./test-lib.sh
+
+test_expect_success 'fsck fails on missing objects' '
+	test_create_repo repo &&
+
+	test_commit -C repo 1 &&
+	test_commit -C repo 2 &&
+	test_commit -C repo 3 &&
+	git -C repo tag -a annotated_tag -m "annotated tag" &&
+	C=$(git -C repo rev-parse 1) &&
+	T=$(git -C repo rev-parse 2^{tree}) &&
+	B=$(git hash-object repo/3.t) &&
+	AT=$(git -C repo rev-parse annotated_tag) &&
+
+	# missing commit, tree, blob, and tag
+	rm repo/.git/objects/$(echo $C | cut -c1-2)/$(echo $C | cut -c3-40) &&
+	rm repo/.git/objects/$(echo $T | cut -c1-2)/$(echo $T | cut -c3-40) &&
+	rm repo/.git/objects/$(echo $B | cut -c1-2)/$(echo $B | cut -c3-40) &&
+	rm repo/.git/objects/$(echo $AT | cut -c1-2)/$(echo $AT | cut -c3-40) &&
+	test_must_fail git -C repo fsck
+'
+
+test_expect_success '...but succeeds if they are promised objects' '
+	printf "%s01%016x\n%s02%016x\n%s03%016x\n%s04%016x" \
+		"$C" 0 "$T" 0 "$B" "$(wc -c <repo/3.t)" "$AT" 0 |
+		sort | tr -d "\n" | hex_pack >repo/.git/objects/promised &&
+	git -C repo config core.repositoryformatversion 1 &&
+	git -C repo config extensions.promisedobjects "arbitrary string" &&
+	git -C repo fsck
+'
+
+test_expect_success '...but fails again with GIT_IGNORE_PROMISED_OBJECTS' '
+	GIT_IGNORE_PROMISED_OBJECTS=1 test_must_fail git -C repo fsck &&
+	unset GIT_IGNORE_PROMISED_OBJECTS
+'
+
+test_done

t/test-lib-functions.sh +6 -0

index db622c355..1ebdd2d04 100644
@@ -1018,3 +1018,9 @@ nongit () {
  		"$@"
  	)
  }
+
+# Converts big-endian pairs of hexadecimal digits into bytes. For example,
+# "printf 61620d0a | hex_pack" results in "ab\r\n".
+hex_pack () {
+	perl -e '$/ = undef; $input = <>; print pack("H*", $input)'
+}

Quoted 7 lines · Jonathan Tan

Currently, Git does not support repos with very large numbers of objects or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every referenced object is available somewhere in the repo storage.

Great to see this idea making progress. Making git able to gracefully handle partial clones (beyond the existing shallow clone support) is a key piece of dealing with very large objects and repos.

Quoted 5 lines

As a first step to reducing this problem, introduce the concept of promised objects. Each Git repo can contain a list of promised objects and their sizes (if blobs) at $GIT_DIR/objects/promised. This patch contains functions to query them; functions for creating and modifying that file will be introduced in later patches.

If I'm reading this patch correctly, for a repo to successfully pass "git fsck" either the object or a promise must exist for everything fsck checks. From the documentation for fsck it says "git fsck defaults to using the index file, all SHA-1 references in refs namespace, and all reflogs (unless --no-reflogs is given) as heads." Doesn't this then imply objects or promises must exist for all objects referenced by any of these locations?

We're currently in the hundreds of millions of objects on some of our repos so even downloading the promises for all the objects in the index is unreasonable as it is gigabytes of data and growing.

I think we should have a flag (off by default) that enables someone to say that promised objects are optional. If the flag is set, "is_promised_object" will return success and pass the OBJ_ANY type and a size of -1.

Nothing today is using the size and in the two places where the object type is being checked for consistency (fsck_cache_tree and fsck_handle_ref) the test can add a test for OBJ_ANY as well.

This will enable very large numbers of objects to be omitted from the clone without triggering a download of the corresponding number of promised objects.

Quoted 5 lines

A repository that is missing an object but has that object promised is not considered to be in error, so also teach fsck this. As part of doing this, object.{h,c} has been modified to generate "struct object" based on only the information available to promised objects, without requiring the object itself.

In your work on this, did you investigate if there are other commands (ie repack/gc) that will need to learn about promised objects? Have you had a chance (or have plans) to hack up the test suite so that it runs all tests with promised objects and see what (if anything) breaks?

Quoted 9 lines · On Thu, 20 Jul 2017 15:58:51 -0400 Ben Peart <[email protected]> wrote:

Quoted 7 lines · Jonathan Tan

Currently, Git does not support repos with very large numbers of objects or repos that wish to minimize manipulation of certain blobs (for example, because they are very large) very well, even if the user operates mostly on part of the repo, because Git is designed on the assumption that every referenced object is available somewhere in the repo storage.

Quoted 3 lines

Great to see this idea making progress. Making git able to gracefully handle partial clones (beyond the existing shallow clone support) is a key piece of dealing with very large objects and repos.

Thanks.

Quoted 14 lines

Quoted 5 lines

As a first step to reducing this problem, introduce the concept of promised objects. Each Git repo can contain a list of promised objects and their sizes (if blobs) at $GIT_DIR/objects/promised. This patch contains functions to query them; functions for creating and modifying that file will be introduced in later patches.

If I'm reading this patch correctly, for a repo to successfully pass "git fsck" either the object or a promise must exist for everything fsck checks. From the documentation for fsck it says "git fsck defaults to using the index file, all SHA-1 references in refs namespace, and all reflogs (unless --no-reflogs is given) as heads." Doesn't this then imply objects or promises must exist for all objects referenced by any of these locations?

Quoted 3 lines

We're currently in the hundreds of millions of objects on some of our repos so even downloading the promises for all the objects in the index is unreasonable as it is gigabytes of data and growing.

For the index to contain all the files, the repo must already have downloaded all the trees for HEAD (at least). The trees collectively contain entries for all the relevant blobs. We need one promise for each blob, and the size of a promise is comparable to the size of a tree entry, so the size (of download and storage) needed would be just double of what we would need if we didn't need promises. This is still only linear growth, unless you have found that the absolute numbers are too large?

Also, if the index is ever changed to not have one entry for every file, we also wouldn't need one promise for every file.

Quoted 5 lines

I think we should have a flag (off by default) that enables someone to say that promised objects are optional. If the flag is set, "is_promised_object" will return success and pass the OBJ_ANY type and a size of -1.

Quoted 7 lines

Nothing today is using the size and in the two places where the object type is being checked for consistency (fsck_cache_tree and fsck_handle_ref) the test can add a test for OBJ_ANY as well.

This will enable very large numbers of objects to be omitted from the clone without triggering a download of the corresponding number of promised objects.

Eventually I plan to use the size when implementing parameters for history-searching commands (e.g. "git log -S"), but it's true that that's in the future.

Allowing promised objects to be optional would indeed solve the issue of downloading too many promises. It would make the code more complicated, but I'm not sure by how much.

For example, in this fsck patch, the easiest way I could think of to have promised objects was to introduce a 3rd state, called "promised", of "struct object" - one in which the type is known, but we don't have access to the full "struct commit" or equivalent. And thus fsck could assume that if the "struct object" is "parsed" or "promised", the type is known. Having optional promised objects would require that we let this "promised" state have a type of OBJ_UNKNOWN (or something like that) - maybe that would be fine, but I haven't looked into this in detail.

Quoted 10 lines

Quoted 5 lines

A repository that is missing an object but has that object promised is not considered to be in error, so also teach fsck this. As part of doing this, object.{h,c} has been modified to generate "struct object" based on only the information available to promised objects, without requiring the object itself.

In your work on this, did you investigate if there are other commands (ie repack/gc) that will need to learn about promised objects? Have you had a chance (or have plans) to hack up the test suite so that it runs all tests with promised objects and see what (if anything) breaks?

In one of the subsequent patches, I tried to ensure that all object-reading functions in sha1_file.c somewhat works (albeit slowly) in the presence of promised objects - that would cover the functionality of the other commands. As for hacking up the test suite to run with promised objects, that would be ideal, but I haven't figured out how to do that yet.

Today we have 3.5 million objects * 30 bytes per entry = 105 MB of promises. Given the average developer only hydrates 56K files (2 MB promises) that is 103 MB to download that no one will ever need. We would like to avoid that if possible as this would be a significant regression in clone times from where we are today.

I'm also concerned about the performance of merging in promises given we have 100M objects today and growing so the number of promises over time could get pretty large.

Quoted 21 lines

Quoted 5 lines

I think we should have a flag (off by default) that enables someone to say that promised objects are optional. If the flag is set, "is_promised_object" will return success and pass the OBJ_ANY type and a size of -1.

Quoted 7 lines

Nothing today is using the size and in the two places where the object type is being checked for consistency (fsck_cache_tree and fsck_handle_ref) the test can add a test for OBJ_ANY as well.

This will enable very large numbers of objects to be omitted from the clone without triggering a download of the corresponding number of promised objects.

Eventually I plan to use the size when implementing parameters for history-searching commands (e.g. "git log -S"), but it's true that that's in the future.

Allowing promised objects to be optional would indeed solve the issue of downloading too many promises. It would make the code more complicated, but I'm not sure by how much.

Quoted 10 lines

For example, in this fsck patch, the easiest way I could think of to have promised objects was to introduce a 3rd state, called "promised", of "struct object" - one in which the type is known, but we don't have access to the full "struct commit" or equivalent. And thus fsck could assume that if the "struct object" is "parsed" or "promised", the type is known. Having optional promised objects would require that we let this "promised" state have a type of OBJ_UNKNOWN (or something like that) - maybe that would be fine, but I haven't looked into this in detail.

Caveats apply as I only did a quick look but I only found the two locations that were checking the object type for consistency.

Quoted 9 lines · On Fri, 21 Jul 2017 12:24:52 -0400 Ben Peart <[email protected]> wrote:

Today we have 3.5 million objects * 30 bytes per entry = 105 MB of promises. Given the average developer only hydrates 56K files (2 MB promises) that is 103 MB to download that no one will ever need. We would like to avoid that if possible as this would be a significant regression in clone times from where we are today.

I'm also concerned about the performance of merging in promises given we have 100M objects today and growing so the number of promises over time could get pretty large.

After some thought, maybe a hybrid solution is best, in which it is permissible but optional for some missing objects to have promises. In that case, it is more of a "size cache" (which stores the type as well) rather than a true promise. When fetching, the client can optionally request for the sizes and types of missing objects.

This is good for the large-blob case, in which we can always have size information of missing blobs, and we can subsequently add blob-size filtering (as a parameter) to "git log -S" and friends to avoid needing to resolve a missing object. And this is, as far as I can tell, also good for the many-blob case - just have an empty size cache all the time. (And in the future, use cases could come up that desire non-empty but non-comprehensive caches - for example, a directory lister working on a partial clone that only needs to cache the sizes of frequently accessed directories.)

Another option is to have a repo-wide option that toggles between mandatory entries in the "size cache" and prohibited entries. Switching to mandatory provides stricter fsck and negative lookups, but I think it's not worth it for both the developers and users of Git to have to know about these two modes.

Quoted 32 lines

Quoted 21 lines

Quoted 5 lines

I think we should have a flag (off by default) that enables someone to say that promised objects are optional. If the flag is set, "is_promised_object" will return success and pass the OBJ_ANY type and a size of -1.

Quoted 7 lines

Nothing today is using the size and in the two places where the object type is being checked for consistency (fsck_cache_tree and fsck_handle_ref) the test can add a test for OBJ_ANY as well.

This will enable very large numbers of objects to be omitted from the clone without triggering a download of the corresponding number of promised objects.

Eventually I plan to use the size when implementing parameters for history-searching commands (e.g. "git log -S"), but it's true that that's in the future.

Allowing promised objects to be optional would indeed solve the issue of downloading too many promises. It would make the code more complicated, but I'm not sure by how much.

Quoted 10 lines

For example, in this fsck patch, the easiest way I could think of to have promised objects was to introduce a 3rd state, called "promised", of "struct object" - one in which the type is known, but we don't have access to the full "struct commit" or equivalent. And thus fsck could assume that if the "struct object" is "parsed" or "promised", the type is known. Having optional promised objects would require that we let this "promised" state have a type of OBJ_UNKNOWN (or something like that) - maybe that would be fine, but I haven't looked into this in detail.

Quoted 2 lines

Caveats apply as I only did a quick look but I only found the two locations that were checking the object type for consistency.

I haven't looked into detail, but you are probably right.

Quoted 9 lines

Quoted 6 lines · On Fri, 21 Jul 2017 12:24:52 -0400 Ben Peart <[email protected]> wrote:

Today we have 3.5 million objects * 30 bytes per entry = 105 MB of promises. Given the average developer only hydrates 56K files (2 MB promises) that is 103 MB to download that no one will ever need. We would like to avoid that if possible as this would be a significant regression in clone times from where we are today.

Quoted 10 lines

Quoted 3 lines

I'm also concerned about the performance of merging in promises given we have 100M objects today and growing so the number of promises over time could get pretty large.

After some thought, maybe a hybrid solution is best, in which it is permissible but optional for some missing objects to have promises. In that case, it is more of a "size cache" (which stores the type as well) rather than a true promise. When fetching, the client can optionally request for the sizes and types of missing objects.

In our GVFS solution today we do not download any size or object type information at clone as the number of objects and the resulting file would be too large. Instead, we have a new sizes endpoint (https://github.com/Microsoft/GVFS/blob/master/Protocol.md) that enables us to retrieve object sizes "on demand" much like we are enabling for the actual object content.

This protocol could easily be extended to return both size and type so that it could be used to retrieve "promise" data for objects as they are needed. Having a way to "cache" that data locally so that both git and other code could share it would be great.

At a minimum, we should ensure the data stream passed back is the same whether at clone time or when hitting a "promises" end point. I think it would also be helpful to enable promises to be downloaded on demand much like we are doing for the object data itself.

Quoted 53 lines

This is good for the large-blob case, in which we can always have size information of missing blobs, and we can subsequently add blob-size filtering (as a parameter) to "git log -S" and friends to avoid needing to resolve a missing object. And this is, as far as I can tell, also good for the many-blob case - just have an empty size cache all the time. (And in the future, use cases could come up that desire non-empty but non-comprehensive caches - for example, a directory lister working on a partial clone that only needs to cache the sizes of frequently accessed directories.)

Another option is to have a repo-wide option that toggles between mandatory entries in the "size cache" and prohibited entries. Switching to mandatory provides stricter fsck and negative lookups, but I think it's not worth it for both the developers and users of Git to have to know about these two modes.

Quoted 32 lines

Quoted 21 lines

Quoted 5 lines

I think we should have a flag (off by default) that enables someone to say that promised objects are optional. If the flag is set, "is_promised_object" will return success and pass the OBJ_ANY type and a size of -1.

Quoted 7 lines

Nothing today is using the size and in the two places where the object type is being checked for consistency (fsck_cache_tree and fsck_handle_ref) the test can add a test for OBJ_ANY as well.

This will enable very large numbers of objects to be omitted from the clone without triggering a download of the corresponding number of promised objects.

Eventually I plan to use the size when implementing parameters for history-searching commands (e.g. "git log -S"), but it's true that that's in the future.

Allowing promised objects to be optional would indeed solve the issue of downloading too many promises. It would make the code more complicated, but I'm not sure by how much.

Quoted 10 lines

For example, in this fsck patch, the easiest way I could think of to have promised objects was to introduce a 3rd state, called "promised", of "struct object" - one in which the type is known, but we don't have access to the full "struct commit" or equivalent. And thus fsck could assume that if the "struct object" is "parsed" or "promised", the type is known. Having optional promised objects would require that we let this "promised" state have a type of OBJ_UNKNOWN (or something like that) - maybe that would be fine, but I haven't looked into this in detail.

Quoted 2 lines

Caveats apply as I only did a quick look but I only found the two locations that were checking the object type for consistency.

I haven't looked into detail, but you are probably right.

Teach sha1_file to invoke a hook whenever an object is requested and unavailable but is promised. The hook is a shell command that can be configured through "git config"; this hook takes in a list of hashes and writes (if successful) the corresponding objects to the repo's local storage.

The usage of the hook can be suppressed through a flag when invoking has_object_file_with_flags() and other similar functions. parse_or_promise_object() in object.c requires this functionality, and has been modified to use it.

This is meant as a temporary measure to ensure that all Git commands work in such a situation. Future patches will update some commands to either tolerate promised objects (without invoking the hook) or be more efficient in invoking the promised objects hook.

In order to determine the code changes in sha1_file.c necessary, I investigated the following:
(1) functions in sha1_file that take in a hash, without the user regarding how the object is stored (loose or packed)
(2) functions in sha1_file that operate on packed objects (because I need to check callers that know about the loose/packed distinction and operate on both differently, and ensure that they can handle the concept of objects that are neither loose nor packed)

(1) is handled by the modification to sha1_object_info_extended().

For (2), I looked at for_each_packed_object and at the packed-related functions that take in a hash. For for_each_packed_object, the callers either already work or are fixed in this patch:
- reachable - only to find recent objects
- builtin/fsck - already knows about promised objects
- builtin/cat-file - fixed in this commit

Callers of the other functions do not need to be changed:
- parse_pack_index
- http - indirectly from http_get_info_packs
- find_pack_entry_one
- this searches a single pack that is provided as an argument; the caller already knows (through other means) that the sought object is in a specific pack
- find_sha1_pack
- fast-import - appears to be an optimization to not store a file if it is already in a pack
- http-walker - to search through a struct alt_base
- http-push - to search through remote packs
- has_sha1_pack
- builtin/fsck - already knows about promised objects
- builtin/count-objects - informational purposes only (check if loose object is also packed)
- builtin/prune-packed - check if object to be pruned is packed (if not, don't prune it)
- revision - used to exclude packed objects if requested by user
- diff - just for optimization

An alternative design that I considered but rejected:

- Adding a hook whenever a packed object is requested, not on any object. That is, whenever we attempt to search the packfiles for an object, if it is missing (from the packfiles and from the loose object storage), to invoke the hook (which must then store it as a packfile), open the packfile the hook generated, and report that the object is found in that new packfile. This reduces the amount of analysis needed (in that we only need to look at how packed objects are handled), but requires that the hook generate packfiles (or for sha1_file to pack whatever loose objects are generated), creating one packfile for each missing object and potentially very many packfiles that must be linearly searched. This may be tolerable now for repos that only have a few missing objects (for example, repos that only want to exclude large blobs), and might be tolerable in the future if we have batching support for the most commonly used commands, but is not tolerable now for repos that exclude a large amount of objects.

Helped-by Ben Peart <[email protected]>

Signed-off-by Jonathan Tan <[email protected]>

---
 Documentation/config.txt                         |   8 +
 Documentation/gitrepository-layout.txt           |   8 +
 Documentation/technical/read-object-protocol.txt | 102 ++++++++++++
 builtin/cat-file.c                               |   9 ++
 cache.h                                          |   2 +
 object.c                                         |   3 +-
 promised-object.c                                | 194 +++++++++++++++++++++++
 promised-object.h                                |  12 ++
 sha1_file.c                                      |  44 +++--
 t/t3907-promised-object.sh                       |  32 ++++
 t/t3907/read-object                              | 114 +++++++++++++
 11 files changed, 513 insertions(+), 15 deletions(-)
 create mode 100644 Documentation/technical/read-object-protocol.txt
 create mode 100755 t/t3907/read-object

Documentation/config.txt +8 -0

index d5c9c4cab..c293ac921 100644
@@ -393,6 +393,14 @@ The default is false, except linkgit:git-clone[1] or linkgit:git-init[1]
 will probe and set core.ignoreCase true if appropriate when the repository
 is created.
 
+core.promisedBlobCommand::
+       If set, whenever a blob in the local repo is attempted to be read, but
+       is both missing and a promised blob, invoke this shell command to
+       generate or obtain that blob before reporting an error. This shell
+       command should take one or more hashes, each terminated by a newline,
+       as standard input, and (if successful) should write the corresponding
+       objects to the local repo (packed or loose).
+
 core.precomposeUnicode::
        This option is only used by Mac OS implementation of Git.
        When core.precomposeUnicode=true, Git reverts the unicode decomposition

Documentation/gitrepository-layout.txt +8 -0

index f51ed4e37..7dea7fe6b 100644
@@ -47,6 +47,10 @@ use with dumb transports but otherwise is OK as long as
 `objects/info/alternates` points at the object stores it
 borrows from.
 +
+. You could have objects that are merely promised by another source.
+When Git requires those objects, it will invoke the command in the
+`extensions.promisedObjects` configuration variable.
++
 This directory is ignored if $GIT_COMMON_DIR is set and
 "$GIT_COMMON_DIR/objects" will be used instead.
 

@@ -91,6 +95,10 @@ objects/info/http-alternates::
        this object store borrows objects from, to be used when
        the repository is fetched over HTTP.
 
+objects/promised::
+       This file records the sha1 object names, types, and sizes of
+       promised objects.
+
 refs::
        References are stored in subdirectories of this
        directory.  The 'git prune' command knows to preserve

Documentation/technical/read-object-protocol.txt new file +0 -0

new file mode 100644
index 000000000..a893b46e7

Documentation/technical/read-object-protocol.txt new file +100 -0

+
+The read-object process enables Git to read all missing blobs with a
+single process invocation for the entire life of a single Git command.
+This is achieved by using a packet format (pkt-line, see technical/
+protocol-common.txt) based protocol over standard input and standard
+output as follows. All packets, except for the "*CONTENT" packets and
+the "0000" flush packet, are considered text and therefore are
+terminated by a LF.
+
+Git starts the process when it encounters the first missing object that
+needs to be retrieved. After the process is started, Git sends a welcome
+message ("git-read-object-client"), a list of supported protocol version
+numbers, and a flush packet. Git expects to read a welcome response
+message ("git-read-object-server"), exactly one protocol version number
+from the previously sent list, and a flush packet. All further
+communication will be based on the selected version.
+
+The remaining protocol description below documents "version=1". Please
+note that "version=42" in the example below does not exist and is only
+there to illustrate how the protocol would look with more than one
+version.
+
+After the version negotiation Git sends a list of all capabilities that
+it supports and a flush packet. Git expects to read a list of desired
+capabilities, which must be a subset of the supported capabilities list,
+and a flush packet as response:
+------------------------
+packet: git> git-read-object-client
+packet: git> version=1
+packet: git> version=42
+packet: git> 0000
+packet: git< git-read-object-server
+packet: git< version=1
+packet: git< 0000
+packet: git> capability=get
+packet: git> capability=have
+packet: git> capability=put
+packet: git> capability=not-yet-invented
+packet: git> 0000
+packet: git< capability=get
+packet: git< 0000
+------------------------
+The only supported capability in version 1 is "get".
+
+Afterwards Git sends a list of "key=value" pairs terminated with a flush
+packet. The list will contain at least the command (based on the
+supported capabilities) and the sha1 of the object to retrieve. Please
+note, that the process must not send any response before it received the
+final flush packet.
+
+When the process receives the "get" command, it should make the requested
+object available in the git object store and then return success. Git will
+then check the object store again and this time find it and proceed.
+------------------------
+packet: git> command=get
+packet: git> sha1=0a214a649e1b3d5011e14a3dc227753f2bd2be05
+packet: git> 0000
+------------------------
+
+The process is expected to respond with a list of "key=value" pairs
+terminated with a flush packet. If the process does not experience
+problems then the list must contain a "success" status.
+------------------------
+packet: git< status=success
+packet: git< 0000
+------------------------
+
+In case the process cannot or does not want to process the content, it
+is expected to respond with an "error" status.
+------------------------
+packet: git< status=error
+packet: git< 0000
+------------------------
+
+In case the process cannot or does not want to process the content as
+well as any future content for the lifetime of the Git process, then it
+is expected to respond with an "abort" status at any point in the
+protocol.
+------------------------
+packet: git< status=abort
+packet: git< 0000
+------------------------
+
+Git neither stops nor restarts the process in case the "error"/"abort"
+status is set.
+
+If the process dies during the communication or does not adhere to the
+protocol then Git will stop the process and restart it with the next
+object that needs to be processed.
+
+After the read-object process has processed an object it is expected to
+wait for the next "key=value" list containing a command. Git will close
+the command pipe on exit. The process is expected to detect EOF and exit
+gracefully on its own. Git will wait until the process has stopped.
+
+A long running read-object process demo implementation can be found in
+`contrib/long-running-read-object/example.pl` located in the Git core
+repository. If you develop your own long running process then the
+`GIT_TRACE_PACKET` environment variables can be very helpful for
+debugging (see linkgit:git[1]).

builtin/cat-file.c +9 -0

index 96b786e48..33f636926 100644
@@ -12,6 +12,7 @@
 #include "streaming.h"
 #include "tree-walk.h"
 #include "sha1-array.h"
+#include "promised-object.h"
 
 struct batch_options {
        int enabled;

@@ -432,6 +433,13 @@ static int batch_packed_object(const struct object_id *oid,
        return 0;
 }
 
+static int batch_promised_object(const struct object_id *oid,
+                                void *data)
+{
+       oid_array_append(data, oid);
+       return 0;
+}
+
 static int batch_objects(struct batch_options *opt)
 {
        struct strbuf buf = STRBUF_INIT;

@@ -473,6 +481,7 @@ static int batch_objects(struct batch_options *opt)
 
                for_each_loose_object(batch_loose_object, &sa, 0);
                for_each_packed_object(batch_packed_object, &sa, 0);
+               for_each_promised_object(batch_promised_object, &sa);
 
                cb.opt = opt;
                cb.expand = &data;

cache.h +2 -0

index dd94b5ffc..75b71f38b 100644
@@ -1835,6 +1835,8 @@ struct object_info {
 #define OBJECT_INFO_SKIP_CACHED 4
 /* Do not retry packed storage after checking packed and loose storage */
 #define OBJECT_INFO_QUICK 8
+/* Ignore list of promised objects */
+#define OBJECT_INFO_IGNORE_PROMISES 16
 extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);
 extern int packed_object_info(struct packed_git *pack, off_t offset, struct object_info *);
 

object.c +2 -1

index 0aeb95084..23f2a6cbc 100644
@@ -285,7 +285,8 @@ struct object *parse_or_promise_object(const struct object_id *oid)
 {
        enum object_type type;
 
-       if (has_object_file(oid))
+       if (has_object_file_with_flags(oid, OBJECT_INFO_SKIP_CACHED |
+                                           OBJECT_INFO_IGNORE_PROMISES))
                return parse_object(oid);
 
        if (is_promised_object(oid, &type, NULL)) {

promised-object.c +194 -0

index 487ade437..d8d95ebb2 100644
@@ -2,6 +2,12 @@
 #include "promised-object.h"
 #include "sha1-lookup.h"
 #include "strbuf.h"
+#include "run-command.h"
+#include "sha1-array.h"
+#include "config.h"
+#include "sigchain.h"
+#include "sub-process.h"
+#include "pkt-line.h"
 
 #define ENTRY_SIZE (GIT_SHA1_RAWSZ + 1 + 8)
 /*

@@ -128,3 +134,191 @@ int fsck_promised_objects(void)
        }
        return 0;
 }
+
+#define CAP_GET    (1u<<0)
+
+static int subprocess_map_initialized;
+static struct hashmap subprocess_map;
+
+struct read_object_process {
+       struct subprocess_entry subprocess;
+       unsigned int supported_capabilities;
+};
+
+int start_read_object_fn(struct subprocess_entry *subprocess)
+{
+       int err;
+       struct read_object_process *entry = (struct read_object_process *)subprocess;
+       struct child_process *process;
+       struct string_list cap_list = STRING_LIST_INIT_NODUP;
+       char *cap_buf;
+       const char *cap_name;
+
+       process = subprocess_get_child_process(&entry->subprocess);
+
+       sigchain_push(SIGPIPE, SIG_IGN);
+
+       err = packet_writel(process->in, "git-read-object-client", "version=1", NULL);
+       if (err)
+               goto done;
+
+       err = strcmp(packet_read_line(process->out, NULL), "git-read-object-server");
+       if (err) {
+               error("external process '%s' does not support read-object protocol version 1", subprocess->cmd);
+               goto done;
+       }
+       err = strcmp(packet_read_line(process->out, NULL), "version=1");
+       if (err)
+               goto done;
+       err = packet_read_line(process->out, NULL) != NULL;
+       if (err)
+               goto done;
+
+       err = packet_writel(process->in, "capability=get", NULL);
+       if (err)
+               goto done;
+
+       for (;;) {
+               cap_buf = packet_read_line(process->out, NULL);
+               if (!cap_buf)
+                       break;
+               string_list_split_in_place(&cap_list, cap_buf, '=', 1);
+
+               if (cap_list.nr != 2 || strcmp(cap_list.items[0].string, "capability"))
+                       continue;
+
+               cap_name = cap_list.items[1].string;
+               if (!strcmp(cap_name, "get")) {
+                       entry->supported_capabilities |= CAP_GET;
+               }
+               else {
+                       warning(
+                               "external process '%s' requested unsupported read-object capability '%s'",
+                               subprocess->cmd, cap_name
+                       );
+               }
+
+               string_list_clear(&cap_list, 0);
+       }
+
+done:
+       sigchain_pop(SIGPIPE);
+
+       if (err || errno == EPIPE)
+               return err ? err : errno;
+
+       return 0;
+}
+
+static int read_object_process(const unsigned char *sha1)
+{
+       int err;
+       struct read_object_process *entry;
+       struct child_process *process;
+       struct strbuf status = STRBUF_INIT;
+       uint64_t start;
+
+       start = getnanotime();
+
+       if (!repository_format_promised_objects)
+               die("BUG: if extensions.promisedObjects is not set, there "
+                   "should not be any promised objects");
+
+       if (!subprocess_map_initialized) {
+               subprocess_map_initialized = 1;
+               hashmap_init(&subprocess_map, (hashmap_cmp_fn)cmd2process_cmp, 0);
+               entry = NULL;
+       } else {
+               entry = (struct read_object_process *)subprocess_find_entry(&subprocess_map, repository_format_promised_objects);
+       }
+       if (!entry) {
+               entry = xmalloc(sizeof(*entry));
+               entry->supported_capabilities = 0;
+
+               if (subprocess_start(&subprocess_map, &entry->subprocess, repository_format_promised_objects, start_read_object_fn)) {
+                       free(entry);
+                       return -1;
+               }
+       }
+       process = subprocess_get_child_process(&entry->subprocess);
+
+       if (!(CAP_GET & entry->supported_capabilities))
+               return -1;
+
+       sigchain_push(SIGPIPE, SIG_IGN);
+
+       err = packet_write_fmt_gently(process->in, "command=get\n");
+       if (err)
+               goto done;
+
+       err = packet_write_fmt_gently(process->in, "sha1=%s\n", sha1_to_hex(sha1));
+       if (err)
+               goto done;
+
+       err = packet_flush_gently(process->in);
+       if (err)
+               goto done;
+
+       err = subprocess_read_status(process->out, &status);
+       err = err ? err : strcmp(status.buf, "success");
+
+done:
+       sigchain_pop(SIGPIPE);
+
+       if (err || errno == EPIPE) {
+               err = err ? err : errno;
+               if (!strcmp(status.buf, "error")) {
+                       /* The process signaled a problem with the file. */
+               }
+               else if (!strcmp(status.buf, "abort")) {
+                       /*
+                        * The process signaled a permanent problem. Don't try to read
+                        * objects with the same command for the lifetime of the current
+                        * Git process.
+                        */
+                       entry->supported_capabilities &= ~CAP_GET;
+               }
+               else {
+                       /*
+                        * Something went wrong with the read-object process.
+                        * Force shutdown and restart if needed.
+                        */
+                       error("external process '%s' failed", repository_format_promised_objects);
+                       subprocess_stop(&subprocess_map, (struct subprocess_entry *)entry);
+                       free(entry);
+               }
+       }
+
+       trace_performance_since(start, "read_object_process");
+
+       return err;
+}
+
+int request_promised_objects(const struct oid_array *oids)
+{
+       int oids_requested = 0;
+       int i;
+
+       for (i = 0; i < oids->nr; i++) {
+               if (is_promised_object(&oids->oid[i], NULL, NULL))
+                       break;
+       }
+
+       if (i == oids->nr)
+               /* Nothing to fetch */
+               return 0;
+
+       for (; i < oids->nr; i++) {
+               if (is_promised_object(&oids->oid[i], NULL, NULL)) {
+                       read_object_process(oids->oid[i].hash);
+                       oids_requested++;
+               }
+       }
+
+       /*
+        * The command above may have updated packfiles, so update our record
+        * of them.
+        */
+       reprepare_packed_git();
+       return oids_requested;
+}

promised-object.h +12 -0

index 7eaedff17..8ad47aa4c 100644
@@ -2,6 +2,7 @@
 #define PROMISED_OBJECT_H
 
 #include "cache.h"
+#include "sha1-array.h"
 
 /*
  * Returns 1 if oid is the name of a promised object. For non-blobs, 0 is

@@ -19,4 +20,15 @@ int for_each_promised_object(each_promised_object_fn, void *);
  */
 int fsck_promised_objects(void);
 
+/*
+ * If any of the given objects are promised objects, invokes
+ * core.promisedobjectcommand with those objects and returns the number of
+ * objects requested. No check is made as to whether the invocation actually
+ * populated the repository with the promised objects.
+ *
+ * If none of the given objects are promised objects, this function does not
+ * invoke anything and returns 0.
+ */
+int request_promised_objects(const struct oid_array *oids);
+
 #endif

sha1_file.c +30 -14

index 5862386cd..ded0ef46b 100644
@@ -28,6 +28,11 @@
 #include "list.h"
 #include "mergesort.h"
 #include "quote.h"
+#include "iterator.h"
+#include "dir-iterator.h"
+#include "sha1-lookup.h"
+#include "promised-object.h"
+#include "sha1-array.h"
 
 #define SZ_FMT PRIuMAX
 static inline uintmax_t sz_fmt(size_t s) { return s; }

@@ -2983,6 +2988,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
        const unsigned char *real = (flags & OBJECT_INFO_LOOKUP_REPLACE) ?
                                    lookup_replace_object(sha1) :
                                    sha1;
+       int already_retried = 0;
 
        if (!oi)
                oi = &blank_oi;

@@ -3007,30 +3013,40 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
                }
        }
 
-       if (!find_pack_entry(real, &e)) {
-               /* Most likely it's a loose object. */
-               if (!sha1_loose_object_info(real, oi, flags)) {
-                       oi->whence = OI_LOOSE;
-                       return 0;
-               }
+retry:
+       if (find_pack_entry(real, &e))
+               goto found_packed;
 
-               /* Not a loose object; someone else may have just packed it. */
-               if (flags & OBJECT_INFO_QUICK) {
-                       return -1;
-               } else {
-                       reprepare_packed_git();
-                       if (!find_pack_entry(real, &e))
-                               return -1;
+       /* Most likely it's a loose object. */
+       if (!sha1_loose_object_info(real, oi, flags)) {
+               oi->whence = OI_LOOSE;
+               return 0;
+       }
+
+       /* Not a loose object; someone else may have just packed it. */
+       reprepare_packed_git();
+       if (find_pack_entry(real, &e))
+               goto found_packed;
+
+       /* Check if it is a promised blob */
+       if (!already_retried && !(flags & OBJECT_INFO_IGNORE_PROMISES)) {
+               struct oid_array promised = OID_ARRAY_INIT;
+               oid_array_append_sha1(&promised, real);
+               if (request_promised_objects(&promised)) {
+                       already_retried = 1;
+                       goto retry;
                }
        }
 
+       return -1;
+
+found_packed:
        if (oi == &blank_oi)
                /*
                 * We know that the caller doesn't actually need the
                 * information below, so return early.
                 */
                return 0;
-
        rtype = packed_object_info(e.p, e.offset, oi);
        if (rtype < 0) {
                mark_bad_packed_object(e.p, real);

t/t3907-promised-object.sh +32 -0

index 3e0caf4f9..d9e6a6486 100755
@@ -38,4 +38,36 @@ test_expect_success '...but fails again with GIT_IGNORE_PROMISED_OBJECTS' '
        unset GIT_IGNORE_PROMISED_OBJECTS
 '
 
+test_expect_success 'sha1_object_info_extended (through git cat-file)' '
+       test_create_repo server &&
+       test_commit -C server 1 1.t abcdefgh &&
+       HASH=$(git hash-object server/1.t) &&
+
+       test_create_repo client &&
+       test_must_fail git -C client cat-file -p "$HASH"
+'
+
+test_expect_success '...succeeds if it is a promised object' '
+       printf "%s03%016x" "$HASH" "$(wc -c <server/1.t)" |
+               hex_pack >client/.git/objects/promised &&
+       git -C client config core.repositoryformatversion 1 &&
+       git -C client config extensions.promisedobjects \
+               "\"$TEST_DIRECTORY/t3907/read-object\" \"$(pwd)/server/.git\"" &&
+       git -C client cat-file -p "$HASH"
+'
+
+test_expect_success 'cat-file --batch-all-objects with promised objects' '
+       rm -rf client &&
+       test_create_repo client &&
+       git -C client config core.repositoryformatversion 1 &&
+       git -C client config extensions.promisedobjects \
+               "\"$TEST_DIRECTORY/t3907/read-object\" \"$(pwd)/server/.git\"" &&
+       printf "%s03%016x" "$HASH" "$(wc -c <server/1.t)" |
+               hex_pack >client/.git/objects/promised &&
+
+       # Verify that the promised object is printed
+       git -C client cat-file --batch --batch-all-objects | tee out |
+               grep abcdefgh
+'
+
 test_done

t/t3907/read-object new file +114 -1

new file mode 100755
index 000000000..9666ad597
@@ -0,0 +1,114 @@
+#!/usr/bin/perl
+#
+# Example implementation for the Git read-object protocol version 1
+# See Documentation/technical/read-object-protocol.txt
+#
+# Allows you to test the ability for blobs to be pulled from a host git repo
+# "on demand."  Called when git needs a blob it couldn't find locally due to
+# a lazy clone that only cloned the commits and trees.
+#
+# A lazy clone can be simulated via the following commands from the host repo
+# you wish to create a lazy clone of:
+#
+# cd /host_repo
+# git rev-parse HEAD
+# git init /guest_repo
+# git cat-file --batch-check --batch-all-objects | grep -v 'blob' |
+#      cut -d' ' -f1 | git pack-objects /guest_repo/.git/objects/pack/noblobs
+# cd /guest_repo
+# git config core.virtualizeobjects true
+# git reset --hard <sha from rev-parse call above>
+#
+# Please note, this sample is a minimal skeleton. No proper error handling
+# was implemented.
+#
+
+use strict;
+use warnings;
+
+#
+# Point $DIR to the folder where your host git repo is located so we can pull
+# missing objects from it
+#
+my $DIR = $ARGV[0];
+
+sub packet_bin_read {
+       my $buffer;
+       my $bytes_read = read STDIN, $buffer, 4;
+       if ( $bytes_read == 0 ) {
+
+               # EOF - Git stopped talking to us!
+               exit();
+       }
+       elsif ( $bytes_read != 4 ) {
+               die "invalid packet: '$buffer'";
+       }
+       my $pkt_size = hex($buffer);
+       if ( $pkt_size == 0 ) {
+               return ( 1, "" );
+       }
+       elsif ( $pkt_size > 4 ) {
+               my $content_size = $pkt_size - 4;
+               $bytes_read = read STDIN, $buffer, $content_size;
+               if ( $bytes_read != $content_size ) {
+                       die "invalid packet ($content_size bytes expected; $bytes_read bytes read)";
+               }
+               return ( 0, $buffer );
+       }
+       else {
+               die "invalid packet size: $pkt_size";
+       }
+}
+
+sub packet_txt_read {
+       my ( $res, $buf ) = packet_bin_read();
+       unless ( $buf =~ s/\n$// ) {
+               die "A non-binary line MUST be terminated by an LF.";
+       }
+       return ( $res, $buf );
+}
+
+sub packet_bin_write {
+       my $buf = shift;
+       print STDOUT sprintf( "%04x", length($buf) + 4 );
+       print STDOUT $buf;
+       STDOUT->flush();
+}
+
+sub packet_txt_write {
+       packet_bin_write( $_[0] . "\n" );
+}
+
+sub packet_flush {
+       print STDOUT sprintf( "%04x", 0 );
+       STDOUT->flush();
+}
+
+( packet_txt_read() eq ( 0, "git-read-object-client" ) ) || die "bad initialize";
+( packet_txt_read() eq ( 0, "version=1" ) )                             || die "bad version";
+( packet_bin_read() eq ( 1, "" ) )                       || die "bad version end";
+
+packet_txt_write("git-read-object-server");
+packet_txt_write("version=1");
+packet_flush();
+
+( packet_txt_read() eq ( 0, "capability=get" ) )    || die "bad capability";
+( packet_bin_read() eq ( 1, "" ) )                  || die "bad capability end";
+
+packet_txt_write("capability=get");
+packet_flush();
+
+while (1) {
+       my ($command) = packet_txt_read() =~ /^command=([^=]+)$/;
+
+       if ( $command eq "get" ) {
+               my ($sha1) = packet_txt_read() =~ /^sha1=([0-9a-f]{40})$/;
+               packet_bin_read();
+
+               system ('git --git-dir="' . $DIR . '" cat-file blob ' . $sha1 . ' | git -c core.virtualizeobjects=false hash-object -w --stdin >/dev/null 2>&1');
+               packet_txt_write(($?) ? "status=error" : "status=success");
+               packet_flush();
+       } else {
+               die "bad command '$command'";
+       }
+}
--

2.14.0.rc0.284.gd933b75aa4-goog