... and some of the code exists only in the list archive, so we
don't know which other topic if any we may want to eject tentatively
if we wanted to give precedence to move this topic forward over
others. I'll worry about it later but help from others is also
appreciated.
As to the contents of this patch, overall, everything makes sense,
except for one thing that makes me wonder. It's not that I see
something specifically incorrect--it is just I do not yet quiet
fathom the implications of.
+/*
+ * Objects that are believed to be loadable by the lazy loader, because
+ * they are referred to by an imported object. If an object that we have
+ * refers to such an object even though we don't have that object, it is
+ * not an error.
+ */
+static struct oidset promises;
+static int promises_prepared;
+
+static int add_promise(const struct object_id *oid, struct packed_git *pack,
+ uint32_t pos, void *data)
+{
+ struct object *obj = parse_object(oid);
+ if (!obj)
+ /*
+ * Error messages are given when packs are verified, so
+ * do not print any here.
+ */
+ return 0;
+
+ /*
+ * If this is a tree, commit, or tag, the objects it refers
+ * to are promises. (Blobs refer to no objects.)
+ */
+ if (obj->type == OBJ_TREE) {
+ struct tree *tree = (struct tree *) obj;
+ struct tree_desc desc;
+ struct name_entry entry;
+ if (init_tree_desc_gently(&desc, tree->buffer, tree->size))
+ /*
+ * Error messages are given when packs are
+ * verified, so do not print any here.
+ */
+ return 0;
+ while (tree_entry_gently(&desc, &entry))
+ oidset_insert(&promises, entry.oid);
+ } else if (obj->type == OBJ_COMMIT) {
+ struct commit *commit = (struct commit *) obj;
+ struct commit_list *parents = commit->parents;
+
+ oidset_insert(&promises, &commit->tree->object.oid);
+ for (; parents; parents = parents->next)
+ oidset_insert(&promises, &parents->item->object.oid);
+ } else if (obj->type == OBJ_TAG) {
+ struct tag *tag = (struct tag *) obj;
+ oidset_insert(&promises, &tag->tagged->oid);
+ }
+ return 0;
+}
This collects names of the objects that are _directly_ referred to
by imported objects. An imported pack may have a commit, whose
top-level tree may or may not appear in the same pack, or the tree
may exist locally but not in the same pack. Or the tree may not be
locally available at all. In any of these four cases, the top-level
tree is listed in the "promises" set. Same for trees and tags.
I wonder if all of the calls to oidset_insert() in this function
want to be guarded by "mark it as promised only when the referrent
is *not* locally available" to keep the promises set minimally
populated. The only change needed to fsck in order to make it
refrain from treating a missing but promised object as an error
would be:
- if (object is missing)
+ if (object is missing && object is not promised)
error("that object must be there but missing");
so there is no point in throwing something that we know we locally
have in this oidset, right?
On the other hand, cost of such additional checks in this function
may outweigh the savings of both memory pressure and look-up cost,
so I do not know how the tradeoff would turn out.
+static int is_promise(const struct object_id *oid)
+{
+ if (!promises_prepared) {
+ if (repository_format_lazy_object)
+ for_each_packed_object(add_promise, NULL,
+ FOR_EACH_OBJECT_IMPORTED_ONLY);
+ promises_prepared = 1;
+ }
+ return oidset_contains(&promises, oid);
+}
Somehow I'm tempted to call this function "is_promised()" but that
is a minor naming issue.
This is about certainly is one place we want to check if the missing
object is OK, but I'm a bit surprised if this were the only place.
Don't we need "while trying to follow all the outgoing links from
this tree object, and we found this object is not available locally;
normally we would mark it as an error but it turns out that the
missing one is in the promised set of objects, so it is OK" for the
normal connectivity traversal codepaths, for example?
... and some of the code exists only in the list archive, so we
don't know which other topic if any we may want to eject tentatively
if we wanted to give precedence to move this topic forward over
others. I'll worry about it later but help from others is also
appreciated.
Thanks - I can help take a look when it is time to move the code in.
I think the issue here is whether we want to move this topic forward or
not, that is, if this (special ".imported" objects) is the best way to
solve (at least partially) the connectivity check part of tolerating
missing objects. I hope that we can continue to talk about it.
This collects names of the objects that are _directly_ referred to
by imported objects. An imported pack may have a commit, whose
top-level tree may or may not appear in the same pack, or the tree
may exist locally but not in the same pack. Or the tree may not be
locally available at all. In any of these four cases, the top-level
tree is listed in the "promises" set. Same for trees and tags.
I wonder if all of the calls to oidset_insert() in this function
want to be guarded by "mark it as promised only when the referrent
is *not* locally available" to keep the promises set minimally
populated. The only change needed to fsck in order to make it
refrain from treating a missing but promised object as an error
would be:
- if (object is missing)
+ if (object is missing && object is not promised)
error("that object must be there but missing");
so there is no point in throwing something that we know we locally
have in this oidset, right?
On the other hand, cost of such additional checks in this function
may outweigh the savings of both memory pressure and look-up cost,
so I do not know how the tradeoff would turn out.
I also don't know how the tradeoff would turn out, so I leaned towards
the slightly simpler solution of not doing the check. In the future,
maybe a t/perf test can be done to decide between the two.
quoted
+static int is_promise(const struct object_id *oid)
+{
+ if (!promises_prepared) {
+ if (repository_format_lazy_object)
+ for_each_packed_object(add_promise, NULL,
+ FOR_EACH_OBJECT_IMPORTED_ONLY);
+ promises_prepared = 1;
+ }
+ return oidset_contains(&promises, oid);
+}
Somehow I'm tempted to call this function "is_promised()" but that
is a minor naming issue.
I was trying to be consistent in using the name "promise" instead of
"promised object/tag/commit/tree/blob" everywhere, but we can switch if
need be (for example, if we don't want to limit the generic name
"promise" to merely objects).
This is about certainly is one place we want to check if the missing
object is OK, but I'm a bit surprised if this were the only place.
Don't we need "while trying to follow all the outgoing links from
this tree object, and we found this object is not available locally;
normally we would mark it as an error but it turns out that the
missing one is in the promised set of objects, so it is OK" for the
normal connectivity traversal codepaths, for example?
... and some of the code exists only in the list archive, so we
don't know which other topic if any we may want to eject tentatively
if we wanted to give precedence to move this topic forward over
others. I'll worry about it later but help from others is also
appreciated.
Thanks - I can help take a look when it is time to move the code in.
I agree that having this depend on patches elsewhere in the list archive
makes it more difficult to review. I know I like to see things in
context to get a better picture.
I think the issue here is whether we want to move this topic forward or
not, that is, if this (special ".imported" objects) is the best way to
solve (at least partially) the connectivity check part of tolerating
missing objects. I hope that we can continue to talk about it.
I think this topic should continue to move forward so that we can
provide reasonable connectivity tests for fsck and check_connected in
the face of partial clones. I'm not sure the prototype implementation
of reading/parsing all imported objects to build the promised oidset is
the most performant model but we can continue to investigate the best
options.
quoted
This collects names of the objects that are _directly_ referred to
by imported objects. An imported pack may have a commit, whose
top-level tree may or may not appear in the same pack, or the tree
may exist locally but not in the same pack. Or the tree may not be
locally available at all. In any of these four cases, the top-level
tree is listed in the "promises" set. Same for trees and tags.
I wonder if all of the calls to oidset_insert() in this function
want to be guarded by "mark it as promised only when the referrent
is *not* locally available" to keep the promises set minimally
populated. The only change needed to fsck in order to make it
refrain from treating a missing but promised object as an error
would be:
- if (object is missing)
+ if (object is missing && object is not promised)
error("that object must be there but missing");
so there is no point in throwing something that we know we locally
have in this oidset, right?
On the other hand, cost of such additional checks in this function
may outweigh the savings of both memory pressure and look-up cost,
so I do not know how the tradeoff would turn out.
I also don't know how the tradeoff would turn out, so I leaned towards
the slightly simpler solution of not doing the check. In the future,
maybe a t/perf test can be done to decide between the two.
quoted
quoted
+static int is_promise(const struct object_id *oid)
+{
+ if (!promises_prepared) {
+ if (repository_format_lazy_object)
+ for_each_packed_object(add_promise, NULL,
+ FOR_EACH_OBJECT_IMPORTED_ONLY);
+ promises_prepared = 1;
+ }
+ return oidset_contains(&promises, oid);
+}
Somehow I'm tempted to call this function "is_promised()" but that
is a minor naming issue.
Given all we need is an existance check for a given oid, I wonder if it
would be faster overall to do a binary search through the list of
imported idx files + an existence test for an imported loose object.
Especially in the check_connected case which isn't verifying every
object, that should be a lot less IO than loading all the imported
commits, trees and blobs and pre-computing an oidset of all possible
objects. The lookup for each object would be slower than a simple call
to oidset_contains but we avoid the up front cost.
With some caching of idx files and threading, I suspect this could be
made pretty fast.
I was trying to be consistent in using the name "promise" instead of
"promised object/tag/commit/tree/blob" everywhere, but we can switch if
need be (for example, if we don't want to limit the generic name
"promise" to merely objects).
This is about certainly is one place we want to check if the missing
object is OK, but I'm a bit surprised if this were the only place.
Don't we need "while trying to follow all the outgoing links from
this tree object, and we found this object is not available locally;
normally we would mark it as an error but it turns out that the
missing one is in the promised set of objects, so it is OK" for the
normal connectivity traversal codepaths, for example?
From: Jonathan Tan <hidden> Date: 2017-08-17 21:39:13
Thanks for your comments. I'll reply to both your e-mails in this one
e-mail.
This illustrates another place we need to resolve the
naming/vocabulary. We should at least be consistent to make it easier
to discuss/explain. We obviously went with "virtual" when building
GVFS but I'm OK with "lazy" as long as we're consistent. Some
examples of how the naming can clarify or confuse:
'Promise-enable your repo by setting the "extensions.lazyObject" flag'
'Enable your repo to lazily fetch objects by setting the
"extensions.lazyObject"'
'Virtualize your repo by setting the "extensions.virtualize" flag'
We may want to carry the same name into the filename we use to mark
the (virtualized/lazy/promised/imported) objects.
(This reminds me that there are only 2 hard problems in computer
science...) ;)
Good point about the name. Maybe the 2nd one is the best? (Mainly
because I would expect a "virtualized" repo to have virtual refs too.)
But if there was a good way to refer to the "anti-projection" in a
virtualized system (that is, the "real" thing or "object" behind the
"virtual" thing or "image"), then maybe the "virtualized" language is
the best. (And I would gladly change - I'm having a hard time coming up
with a name for the "anti-projection" in the "lazy" language.)
Also, I should probably standardize on "lazily fetch" instead of "lazily
load". I didn't want to overlap with the existing fetching, but after
some thought, it's probably better to do that. The explanation would
thus be that you can either use the built-in Git fetcher (to be built,
although I have an old version here [1]) or supply a custom fetcher.
[1] https://github.com/jonathantanmy/git/commits/partialclone
I think this all works and would meet the requirements we've been
discussing. The big trade off here vs what we first discussed with
promises is that we are generating the list of promises on the fly
when they are needed rather than downloading and maintaining a list
locally.
My biggest concern with this model is the cost of opening and parsing
every imported object (loose and pack for local and alternates) to
build the oidset of promises.
In fsck this probably won't be an issue as it already focuses on
correctness at the expense of speed. I'm more worried about when we
add the same/similar logic into check_connected. That impacts fetch,
clone, and receive_pack.
I guess the only way we can know for sure it to do a perf test and
measure the impact.
As for fetching from the main repo, the connectivity check does not need
to be performed at all because all objects are "imported", so the
performance of the connectivity check does not matter. Same for cloning.
This is not true if you're fetching from another repo or if you're using
receive-pack, but (1) I think these are not used as much in such a
situation, and (2) if you do use them, the slowness only "kicks in" if
you do not have the objects referred to (whether non-"imported" or
"imported") and thus have to check the references in all "imported"
objects.
I think this topic should continue to move forward so that we can
provide reasonable connectivity tests for fsck and check_connected in
the face of partial clones. I'm not sure the prototype implementation
of reading/parsing all imported objects to build the promised oidset is
the most performant model but we can continue to investigate the best
options.
Agreed - I think the most important thing here is settling on the API
(name of extension and the nature of the object mark).
Given all we need is an existance check for a given oid,
This is true...
I wonder if it
would be faster overall to do a binary search through the list of
imported idx files + an existence test for an imported loose object.
...but what we're checking is the existence of a reference, not the
existence of an object. For a concrete example, consider what happens if
we both have an "imported" tree and a non-"imported" tree that
references a blob that we do not have. When checking the non-"imported"
tree for connectivity, we have to iterate through all "imported" trees
to see if any can vouch for the existence of such a blob. We cannot
merely binary-search the .idx file.
From: Ben Peart <hidden> Date: 2017-08-18 14:18:47
On 8/17/2017 5:39 PM, Jonathan Tan wrote:
Thanks for your comments. I'll reply to both your e-mails in this one
e-mail.
quoted
This illustrates another place we need to resolve the
naming/vocabulary. We should at least be consistent to make it easier
to discuss/explain. We obviously went with "virtual" when building
GVFS but I'm OK with "lazy" as long as we're consistent. Some
examples of how the naming can clarify or confuse:
'Promise-enable your repo by setting the "extensions.lazyObject" flag'
'Enable your repo to lazily fetch objects by setting the
"extensions.lazyObject"'
'Virtualize your repo by setting the "extensions.virtualize" flag'
We may want to carry the same name into the filename we use to mark
the (virtualized/lazy/promised/imported) objects.
(This reminds me that there are only 2 hard problems in computer
science...) ;)
Good point about the name. Maybe the 2nd one is the best? (Mainly
because I would expect a "virtualized" repo to have virtual refs too.)
But if there was a good way to refer to the "anti-projection" in a
virtualized system (that is, the "real" thing or "object" behind the
"virtual" thing or "image"), then maybe the "virtualized" language is
the best. (And I would gladly change - I'm having a hard time coming up
with a name for the "anti-projection" in the "lazy" language.)
The most common "anti-virtual" language I'm familiar with is "physical."
Virtual machine <-> physical machine. Virtual world <-> physical
world. Virtual repo, commit, tree, blob - physical repo, commit, tree,
blob. I'm not thrilled but I think it works...
Also, I should probably standardize on "lazily fetch" instead of "lazily
load". I didn't want to overlap with the existing fetching, but after
some thought, it's probably better to do that. The explanation would
thus be that you can either use the built-in Git fetcher (to be built,
although I have an old version here [1]) or supply a custom fetcher.
[1] https://github.com/jonathantanmy/git/commits/partialclone
quoted
I think this all works and would meet the requirements we've been
discussing. The big trade off here vs what we first discussed with
promises is that we are generating the list of promises on the fly
when they are needed rather than downloading and maintaining a list
locally.
My biggest concern with this model is the cost of opening and parsing
every imported object (loose and pack for local and alternates) to
build the oidset of promises.
In fsck this probably won't be an issue as it already focuses on
correctness at the expense of speed. I'm more worried about when we
add the same/similar logic into check_connected. That impacts fetch,
clone, and receive_pack.
I guess the only way we can know for sure it to do a perf test and
measure the impact.
As for fetching from the main repo, the connectivity check does not need
to be performed at all because all objects are "imported", so the
performance of the connectivity check does not matter. Same for cloning.
Very good point! I got stuck on connectivity check in general forgetting
that we really only need to prevent sharing a corrupt repo.
This is not true if you're fetching from another repo
This isn't a case we've explicitly dealt with (multiple remotes into a
virtualized repo). Our behavior today would be that once you set the
"virtual repo" flag on the repo (this happens at clone for us), all
remotes are treated as virtual as well (ie we don't differentiate
behavior based on which remote was used). Our "custom fetcher" always
uses "origin" and some custom settings for a cache-server saved in the
.git/config file when asked to fetch missing objects.
This is probably a good model to stick with at least initially as trying
to solve multiple possible "virtual" remotes as well as mingling
virtualized and non-virtualized remotes and all the mixed cases that can
come up makes my head hurt. We should probably address that in a
different thread. :)
or if you're using
receive-pack, but (1) I think these are not used as much in such a
situation, and (2) if you do use them, the slowness only "kicks in" if
you do not have the objects referred to (whether non-"imported" or
"imported") and thus have to check the references in all "imported"
objects.
Is there any case where receive-pack is used on the client side? I'm
only aware of it being used on the server side to receive packs pushed
from the client. If it is not used in a virtualized client, then we
would not need to do anything different for receive-pack.
quoted
I think this topic should continue to move forward so that we can
provide reasonable connectivity tests for fsck and check_connected in
the face of partial clones. I'm not sure the prototype implementation
of reading/parsing all imported objects to build the promised oidset is
the most performant model but we can continue to investigate the best
options.
Agreed - I think the most important thing here is settling on the API
(name of extension and the nature of the object mark).
quoted
Given all we need is an existance check for a given oid,
This is true...
quoted
I wonder if it
would be faster overall to do a binary search through the list of
imported idx files + an existence test for an imported loose object.
...but what we're checking is the existence of a reference, not the
existence of an object. For a concrete example, consider what happens if
we both have an "imported" tree and a non-"imported" tree that
references a blob that we do not have. When checking the non-"imported"
tree for connectivity, we have to iterate through all "imported" trees
to see if any can vouch for the existence of such a blob. We cannot
merely binary-search the .idx file.
That is another good point. Given the discussion above about not
needing to do the connectivity test for fetch/clone - the potential perf
hit of loading/parsing all the various objects to build up the oidset is
much less of an issue.
From: Jonathan Tan <hidden> Date: 2017-08-18 23:33:20
On Fri, 18 Aug 2017 10:18:37 -0400
Ben Peart [off-list ref] wrote:
quoted
But if there was a good way to refer to the "anti-projection" in a
virtualized system (that is, the "real" thing or "object" behind the
"virtual" thing or "image"), then maybe the "virtualized" language is
the best. (And I would gladly change - I'm having a hard time coming up
with a name for the "anti-projection" in the "lazy" language.)
The most common "anti-virtual" language I'm familiar with is "physical."
Virtual machine <-> physical machine. Virtual world <-> physical
world. Virtual repo, commit, tree, blob - physical repo, commit, tree,
blob. I'm not thrilled but I think it works...
I was thinking more along the lines of the "entity that projects the
virtualization", not the opposite of a "virtualization" - "physical"
might work for the latter but probably not the former.
After some in-office discussion, if we stick to the "promise" concept,
maybe we have something like this:
In a partial clone, the origin acts as a promisor of objects. Every
object obtained from the promisor also acts as a promise that any
object directly or indirectly referenced from that object is fetchable
from the promisor.
quoted
This is not true if you're fetching from another repo
This isn't a case we've explicitly dealt with (multiple remotes into a
virtualized repo). Our behavior today would be that once you set the
"virtual repo" flag on the repo (this happens at clone for us), all
remotes are treated as virtual as well (ie we don't differentiate
behavior based on which remote was used). Our "custom fetcher" always
uses "origin" and some custom settings for a cache-server saved in the
.git/config file when asked to fetch missing objects.
This is probably a good model to stick with at least initially as trying
to solve multiple possible "virtual" remotes as well as mingling
virtualized and non-virtualized remotes and all the mixed cases that can
come up makes my head hurt. We should probably address that in a
different thread. :)
OK, let's stick to the current model first then, whether our opinion on
other remotes is (1) "we won't have any other remotes so we don't care",
(2) "we have other remotes but it's fine to make sure that they don't
introduce any new missing objects", or (3) "we need other remotes to
introduce missing objects, but we can build that after this foundation
is laid".
quoted
or if you're using
receive-pack, but (1) I think these are not used as much in such a
situation, and (2) if you do use them, the slowness only "kicks in" if
you do not have the objects referred to (whether non-"imported" or
"imported") and thus have to check the references in all "imported"
objects.
Is there any case where receive-pack is used on the client side? I'm
only aware of it being used on the server side to receive packs pushed
from the client. If it is not used in a virtualized client, then we
would not need to do anything different for receive-pack.
This happens if another repo decides to push to the virtualized client,
which (as I wrote) I don't expect to happen often. My intention is to
ensure that receive-pack will still work.
That is another good point. Given the discussion above about not
needing to do the connectivity test for fetch/clone - the potential perf
hit of loading/parsing all the various objects to build up the oidset is
much less of an issue.