{"thread":{"id":"46515","subject":"Partial clone design (with connectivity check for locally-created objects)","startedAt":"2017-08-04T21:51:26Z","lastAt":"2017-08-18T23:33:20Z","messageCount":18,"participants":["Jonathan Tan","Junio C Hamano","Ben Peart","Jonathan Nieder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"325630","messageId":"20170804145113.5ceafafa@twelve2.svl.corp.google.com","threadId":"46515","inReplyTo":null,"subject":"Partial clone design (with connectivity check for locally-created objects)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-08-04T21:51:13Z","receivedAt":"2017-08-04T21:51:26Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"After some discussion in [1] (in particular, about preserving the\nfunctionality of the connectivity check as much as possible) and some\nin-office discussion, here's an updated design.\n\nOverview\n========\n\nThis is an update of the design in [1].\n\nThe main difference between this and other related work [1] [2] [3] is\nthat we can still check connectivity between locally-created objects\nwithout having to consult a remote server for any information.\n\nIn addition, the object loader writes to an incomplete packfile. This\n(i) ensures that Git has immediate access to the object, (ii) ensures\nthat not too many files are written during a single Git invocation, and\n(iii) prevents some unnecessary copies (compared to, for example,\ntransmitting entire objects through the protocol).\n\nLocal repo layout\n=================\n\nObjects in the local repo are further divided into \"homegrown\" and\n\"imported\" objects.\n\n\"Imported\" objects must be in a packfile that has a \".remote\"\nfile with arbitrary text (similar to the \".keep\" file). They come from\nclones, fetches, and the object loader (see below).\n\n\"Homegrown\" objects are every other object.\n\nObject loader\n=============\n\nThe object loader is a process that can obtain objects from elsewhere,\ngiven their hashes, and write their packed representation to a\nclient-given file.\n\nThe first time a missing object is needed during an invocation of Git,\nGit creates a temporary packfile and writes the header with a\nplaceholder number of objects. Then, it starts the object loader,\npassing in the name of that temporary packfile.\n\nWhenever a missing object is needed, Git sends the hash of the missing\nobject and expects the loader to append (with O_APPEND) the object to\nthat packfile. Git keeps track of the object offsets as it goes, and Git\ncan use the contents of that incomplete packfile. This is similar to\nwhat \"git fast-import\" does.\n\nWhen Git exits, it writes the number of objects in the header, writes\nthe packfile checksum, moves the packfile to its final location, and\nwrites a .idx and a .remote file.\n\nConnectivity check\n==================\n\nAn object walk is performed as usual from the tips (see the\ndocumentation for fsck etc. for which tips they use).\n\nA \"homegrown\" object is valid if each object it references:\n 1. is a \"homegrown\" object,\n 2. is an \"imported\" object, or\n 3. is referenced by an \"imported\" object.\n\nThe references of an \"imported\" object are not checked.\n\nPerformance notes\n-----------------\n\nBecause of rule 3 above, iteration through every \"imported\" object (or,\nat least, every \"imported\" object of a certain type) is sometimes\nrequired.\n\nFor fsck, this should be fine because (i) this is not a regression since\ncurrently all objects must be iterated through anyway, and (ii) fsck\nprioritizes correctness over speed.\n\nFor fetch, the speed of the connectivity check is immaterial; the\nconnectivity check no longer needs to be performed because all objects\nobtained from the remote are, by definition, \"imported\" objects.\n\nThere might be connectivity checks run during other commands like\n\"receive-pack\". I don't expect partial clones to use these often. These\ncommands will still work, but performance of these is a secondary\nconcern in this design.\n\nImpact on other tools\n=====================\n\n\"git gc\" will need to not do anything to an \"imported\" object, even if\nit is unreachable, without ensuring that the connectivity check will\nsucceed in that object's absence. (Special attention to rule 3 under\n\"Connectivity check\".)\n\nIf this design stands, the initial patch set will probably have \"git gc\"\nnot touch \"imported\" packs at all, trivially satisfying the above. In\nthe future, \"git gc\" will either need to expel such objects into loose\nobjects (like what is currently done for normal packs), treating them\nlike a \"homegrown\" object (unreachable, so it won't interfere with\nfuture connectivity checks), or delete them outright - but there may be\nrace conditions to think of.\n\n\"git repack\" will need to differentiate between packs with \".remote\" and\npacks without.\n\n[1] https://public-inbox.org/git/cover.1501532294.git.jonathantanmy@google.com/\n[2] https://public-inbox.org/git/20170714132651.170708-1-benpeart@microsoft.com/\n[3] https://public-inbox.org/git/20170803091926.1755-1-chriscool@tuxfamily.org/\n\n"},{"id":"325634","messageId":"xmqqtw1nrlpf.fsf@gitster.mtv.corp.google.com","threadId":"46515","inReplyTo":"20170804145113.5ceafafa@twelve2.svl.corp.google.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-04T22:51:08Z","receivedAt":"2017-08-04T22:51:25Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> \"Imported\" objects must be in a packfile that has a \".remote\"\n> file with arbitrary text (similar to the \".keep\" file). They come from\n> clones, fetches, and the object loader (see below).\n> ...\n> A \"homegrown\" object is valid if each object it references:\n> 1. is a \"homegrown\" object,\n> 2. is an \"imported\" object, or\n> 3. is referenced by an \"imported\" object.\n\nOverall it captures what was discussed, and I think it is a good\nstart.\n\nI doubt you want to treat all fetches/clones the same way as the\n\"lazy object\" loading, though. You may be critically rely on the\ncorporate central server that will give the objects it \"promised\"\nwhen you cloned from it lazily (i.e. it may have given you a commit,\nbut not its parents or objects contained in its tree--you still know\nthat the parents and the tree and its contents will later be\navailable and rely on that fact). You trust that and build on top,\nso the packfile you obtained when you cloned from such a server\nshould count as \"imported\". But if you exchanged wip changes with\nyour colleages by fetching or pushing peer-to-peer, without the\ncorporate central server knowing, you would want to treat objects in\npacks (or loose objects) you obtained that way as \"not imported\".\n\nAlso I think \"imported\" vs \"homegrown\" may be a bit misnomer; the\nidea to split objects into two camps sounds like a good idea, and\n\"imported\" probably is an OK name to use for the category that is a\ngroup of objects to which you know/trust are backed by your lazy\nloader. But the other one does not have to be \"home\"-grown.\n\nWell, the names are not that important, but I think the line between\nthe two classes should not be \"everything that came from clone and\nfetch is imported\", which is a more important point I am trying to\nmake.\n\nThanks.\n"},{"id":"325636","messageId":"20170804172137.42f27653@twelve2.svl.corp.google.com","threadId":"46515","inReplyTo":"xmqqtw1nrlpf.fsf@gitster.mtv.corp.google.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-08-05T00:21:37Z","receivedAt":"2017-08-05T00:21:46Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Fri, 04 Aug 2017 15:51:08 -0700\nJunio C Hamano wrote:\n\n> Jonathan Tan writes:\n> \n> > \"Imported\" objects must be in a packfile that has a \".remote\"\n> > file with arbitrary text (similar to the \".keep\" file). They come from\n> > clones, fetches, and the object loader (see below).\n> > ...\n> > A \"homegrown\" object is valid if each object it references:\n> > 1. is a \"homegrown\" object,\n> > 2. is an \"imported\" object, or\n> > 3. is referenced by an \"imported\" object.\n> \n> Overall it captures what was discussed, and I think it is a good\n> start.\n> \n> I doubt you want to treat all fetches/clones the same way as the\n> \"lazy object\" loading, though. You may be critically rely on the\n> corporate central server that will give the objects it \"promised\"\n> when you cloned from it lazily (i.e. it may have given you a commit,\n> but not its parents or objects contained in its tree--you still know\n> that the parents and the tree and its contents will later be\n> available and rely on that fact). You trust that and build on top,\n> so the packfile you obtained when you cloned from such a server\n> should count as \"imported\". But if you exchanged wip changes with\n> your colleages by fetching or pushing peer-to-peer, without the\n> corporate central server knowing, you would want to treat objects in\n> packs (or loose objects) you obtained that way as \"not imported\".\n\nThat's true. I discussed this with a teammate and we might need to make\nextensions.lazyObject be the name of the \"corporate central server\"\nremote instead, and have a \"loader\" setting within that remote, so that\nwe can distinguish that objects from this server are \"imported\" but\nobjects from other servers are not.\n\nThe connectivity check shouldn't be slow in this case because fetches\nare usually onto tips that we have (so we don't hit case 3).\n\n> Also I think \"imported\" vs \"homegrown\" may be a bit misnomer; the\n> idea to split objects into two camps sounds like a good idea, and\n> \"imported\" probably is an OK name to use for the category that is a\n> group of objects to which you know/trust are backed by your lazy\n> loader. But the other one does not have to be \"home\"-grown.\n> \n> Well, the names are not that important, but I think the line between\n> the two classes should not be \"everything that came from clone and\n> fetch is imported\", which is a more important point I am trying to\n> make.\n> \n> Thanks.\n\nMaybe \"imported\" vs \"non-imported\" would be better. I agree that the\nobjects in the non-\"imported\" group could still be obtained from\nelsewhere.\n\nThanks for your comments.\n"},{"id":"325726","messageId":"0633771f-ce19-6211-fabe-3f7f676e53ab@gmail.com","threadId":"46515","inReplyTo":"20170804172137.42f27653@twelve2.svl.corp.google.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-07T19:12:11Z","receivedAt":"2017-08-07T19:12:24Z","isPatch":false,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/4/2017 8:21 PM, Jonathan Tan wrote:\n> On Fri, 04 Aug 2017 15:51:08 -0700\n> Junio C Hamano wrote:\n> \n>> Jonathan Tan writes:\n>>\n>>> \"Imported\" objects must be in a packfile that has a \".remote\"\n>>> file with arbitrary text (similar to the \".keep\" file). They come from\n>>> clones, fetches, and the object loader (see below).\n>>> ...\n>>> A \"homegrown\" object is valid if each object it references:\n>>> 1. is a \"homegrown\" object,\n>>> 2. is an \"imported\" object, or\n>>> 3. is referenced by an \"imported\" object.\n>>\n>> Overall it captures what was discussed, and I think it is a good\n>> start.\n\nI missed the offline discussion and so am trying to piece together what \nthis latest design is trying to do. Please let me know if I'm not \nunderstanding something correctly.\n\n From what I can tell, objects are going to be segmented into two \n\"types\" - those that were fetched from a remote source that allows \npartial clones/fetches (lazyobject/imported) and those that come from \n\"regular\" remote sources (homegrown) that requires all objects to exist \nlocally.\n\nFWIW, the names here are not making things clearer for me. If I'm \ncorrect perhaps \"partial\" and \"normal\" would be better to indicate the \ntype of the source? Anyway...\n\nOnce the objects are segmented into the 2 types, the fsck connectivity \ncheck code is updated to ignore missing objects from \"partial\" remotes \nbut still expect/validate them from \"normal\" remotes.\n\nThis compromise seems reasonable - don't generate errors for missing \nobjects for remotes that returned a partial clone but do generate errors \nfor missing objects from normal clones as a missing object is always an \nerror in this case.\n\nThis segmentation is what is driving the need for the object loader to \nbuild a new local pack file for every command that has to fetch a \nmissing object. For example, we can't just write a tree object from a \n\"partial\" clone into the loose object store as we have no way for fsck \nto treat them differently and ignore any missing objects referenced by \nthat tree object.\n\nMy concern with this proposal is the combination of 1) writing a new \npack file for every git command that ends up bringing down a missing \nobject and 2) gc not compressing those pack files into a single pack file.\n\nWe all know that git doesn't scale well with a lot of pack files as it \nhas to do a linear search through all the pack files when attempting to \nfind an object. I can see that very quickly, there would be a lot of \npack files generated and with gc ignoring \"partial\" pack files, this \nwould never get corrected.\n\nIn our usage scenarios, _all_ of the objects come from \"partial\" clones \nso all of our objects would end up in a series of \"partial\" pack files \nand would have pretty poor performance as a result.\n\nI wondered if it is possible to flag a specific remote as \"partial\" and \nhave fsck be able to track any given object back to the remote and then \nproperly handle the fact that it was missing based on that. I couldn't \nthink of a good way to do that without some additional data structure \nthat would have to be build/maintained (ie promises).\n\nThat thinking did lead me back to wondering again if we could live with \na repo specific flag. If any clone/fetch was \"partial\" the flag is set \nand fsck ignore missing objects whether they came from a \"partial\" \nremote or not.\n\nI'll admit it isn't as robust if someone is mixing and matching remotes \nfrom different servers some of which are partial and some of which are \nnot. I'm not sure how often that would actually happen but I _am_ \ncertain a single repo specific flag is a _much_ simpler model than \nanything else we've come up with so far.\n\n>>\n>> I doubt you want to treat all fetches/clones the same way as the\n>> \"lazy object\" loading, though. You may be critically rely on the\n>> corporate central server that will give the objects it \"promised\"\n>> when you cloned from it lazily (i.e. it may have given you a commit,\n>> but not its parents or objects contained in its tree--you still know\n>> that the parents and the tree and its contents will later be\n>> available and rely on that fact). You trust that and build on top,\n>> so the packfile you obtained when you cloned from such a server\n>> should count as \"imported\". But if you exchanged wip changes with\n>> your colleages by fetching or pushing peer-to-peer, without the\n>> corporate central server knowing, you would want to treat objects in\n>> packs (or loose objects) you obtained that way as \"not imported\".\n> \n> That's true. I discussed this with a teammate and we might need to make\n> extensions.lazyObject be the name of the \"corporate central server\"\n> remote instead, and have a \"loader\" setting within that remote, so that\n> we can distinguish that objects from this server are \"imported\" but\n> objects from other servers are not.\n> \n> The connectivity check shouldn't be slow in this case because fetches\n> are usually onto tips that we have (so we don't hit case 3).\n> \n>> Also I think \"imported\" vs \"homegrown\" may be a bit misnomer; the\n>> idea to split objects into two camps sounds like a good idea, and\n>> \"imported\" probably is an OK name to use for the category that is a\n>> group of objects to which you know/trust are backed by your lazy\n>> loader. But the other one does not have to be \"home\"-grown.\n>>\n>> Well, the names are not that important, but I think the line between\n>> the two classes should not be \"everything that came from clone and\n>> fetch is imported\", which is a more important point I am trying to\n>> make.\n>>\n>> Thanks.\n> \n> Maybe \"imported\" vs \"non-imported\" would be better. I agree that the\n> objects in the non-\"imported\" group could still be obtained from\n> elsewhere.\n> \n> Thanks for your comments.\n> \n"},{"id":"325727","messageId":"20170807192151.GX13924@aiede.mtv.corp.google.com","threadId":"46515","inReplyTo":"0633771f-ce19-6211-fabe-3f7f676e53ab@gmail.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-08-07T19:21:51Z","receivedAt":"2017-08-07T19:22:05Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nBen Peart wrote:\n>> On Fri, 04 Aug 2017 15:51:08 -0700\n>> Junio C Hamano wrote:\n>>> Jonathan Tan writes:\n\n>>>> \"Imported\" objects must be in a packfile that has a \".remote\"\n>>>> file with arbitrary text (similar to the \".keep\" file). They come from\n>>>> clones, fetches, and the object loader (see below).\n>>>> ...\n>>>>\n>>>> A \"homegrown\" object is valid if each object it references:\n>>>> 1. is a \"homegrown\" object,\n>>>> 2. is an \"imported\" object, or\n>>>> 3. is referenced by an \"imported\" object.\n>>>\n>>> Overall it captures what was discussed, and I think it is a good\n>>> start.\n>\n> I missed the offline discussion and so am trying to piece together\n> what this latest design is trying to do. Please let me know if I'm\n> not understanding something correctly.\n\nI believe\nhttps://public-inbox.org/git/cover.1501532294.git.jonathantanmy@google.com/\nand the surrounding thread (especially\nhttps://public-inbox.org/git/xmqqefsudjqk.fsf@gitster.mtv.corp.google.com/)\nis the discussion Junio is referring to.\n\n[...]\n> This segmentation is what is driving the need for the object loader\n> to build a new local pack file for every command that has to fetch a\n> missing object. For example, we can't just write a tree object from\n> a \"partial\" clone into the loose object store as we have no way for\n> fsck to treat them differently and ignore any missing objects\n> referenced by that tree object.\n\nThat's related and how it got lumped into this proposal, but it's not\nthe only motivation.\n\nOther aspects:\n\n 1. using pack files instead of loose objects means we can use deltas.\n This is the primary motivation.\n\n 2. pack files can use reachability bitmaps (I realize there are\n obstacles to getting benefit out of this because git's bitmap\n format currently requires a pack to be self-contained, but I\n thought it was worth mentioning for completeness).\n\n 3. existing git servers are oriented around pack files; they can\n more cheaply serve objects from pack files in pack format,\n including reusing deltas from them.\n\n 4. file systems cope better with a few large files than many small\n files\n\n[...]\n> We all know that git doesn't scale well with a lot of pack files as\n> it has to do a linear search through all the pack files when\n> attempting to find an object. I can see that very quickly, there\n> would be a lot of pack files generated and with gc ignoring\n> \"partial\" pack files, this would never get corrected.\n\nYes, that's an important point. Regardless of this proposal, we need\nto get more aggressive about concatenating pack files (e.g. by\nimplementing exponential rollup in \"git gc --auto\").\n\n> In our usage scenarios, _all_ of the objects come from \"partial\"\n> clones so all of our objects would end up in a series of \"partial\"\n> pack files and would have pretty poor performance as a result.\n\nCan you say more about this? Why would the pack files (or loose\nobjects, for that matter) never end up being consolidated into few\npack files?\n\n[...]\n> That thinking did lead me back to wondering again if we could live\n> with a repo specific flag. If any clone/fetch was \"partial\" the\n> flag is set and fsck ignore missing objects whether they came from a\n> \"partial\" remote or not.\n>\n> I'll admit it isn't as robust if someone is mixing and matching\n> remotes from different servers some of which are partial and some of\n> which are not. I'm not sure how often that would actually happen\n> but I _am_ certain a single repo specific flag is a _much_ simpler\n> model than anything else we've come up with so far.\n\nThe primary motivation in this thread is locally-created objects, not\nobjects obtained from other remotes. Objects obtained from other\nremotes are more of an edge case.\n\nThanks for your thoughtful comments.\n\nJonathan\n"},{"id":"325731","messageId":"xmqqwp6fp3mk.fsf@gitster.mtv.corp.google.com","threadId":"46515","inReplyTo":"0633771f-ce19-6211-fabe-3f7f676e53ab@gmail.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-07T19:41:23Z","receivedAt":"2017-08-07T19:41:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ben Peart writes:\n\n> My concern with this proposal is the combination of 1) writing a new\n> pack file for every git command that ends up bringing down a missing\n> object and 2) gc not compressing those pack files into a single pack\n> file.\n\nYour noticing these is a sign that you read the outline of the\ndesign correctly, I think. \n\nThe basic idea is that the local fsck should tolerate missing\nobjects when they are known to be obtainable from that external\nservice, but should still be able to diagnose missing objects that\nwe do not know if the external service has, especially the ones that\nhave been newly created locally and not yet made available to them\nby pushing them back.\n\nSo we need a way to tell if an object that we do not have (but we\nknow about) can later be obtained from the external service.\nMaintaining an explicit list of such objects obviously is one way,\nbut we can get the moral equivalent by using pack files. After\nreceiving a pack file that has a commit from such an external\nservice, if the commit refers to its parent commit that we do not\nhave locally, the design proposes us to consider that the parent\ncommit that is missing is available at the external service that\ngave the pack to us. Similarly for missing trees, blobs, and any\nobjects that are supposed to be \"reachable\" from objects in such a\npackfile. \n\nWe can extend the approach to cover loose objects if we wanted to;\njust define an alternate object store used internally for this\npurpose and drop loose objects obtained from such an external\nservice in that object store.\n\nBecause we do not want to leave too many loose objects and small\npackfiles lying around, we will need a new way of packing these.\nJust enumerate these objects known to have come from the external\nservice (by being in packfiles marked as such or being loose objects\nin the dedicated alternate object store), and create a single larger\npackfile, which is marked as \"holding the objects that are known to\nbe in the external service\". We do not have such a mode of gc, and\nthat is a new development that needs to happen, but we know that is\ndoable.\n\n> That thinking did lead me back to wondering again if we could live\n> with a repo specific flag. If any clone/fetch was \"partial\" the flag\n> is set and fsck ignore missing objects whether they came from a\n> \"partial\" remote or not.\n\nThe only reason people run \"git fsck\" is to make sure that their\nlocal repository is sound and they can rely on the objects you have\nas the base of building new stuff on top of. That is why we are\ntrying to find a way to make sure \"fsck\" can be used to detect\nbroken or missing objects that cannot be obtained from the\nlazy-object store, without incurring undue overhead for normal\ncodepath (i.e. outside fsck).\n\nIt is OK to go back to wondering again, but I think that essentially\ntosses \"git fsck\" out of the window and declares that it is OK to\nhope that local objects will never go bad. We can make such an\ndeclaration anytime, but I do not want to see us doing so without\nfirst trying to solve the issue without punting.\n"},{"id":"325775","messageId":"20170807161031.7c4eae50@twelve2.svl.corp.google.com","threadId":"46515","inReplyTo":"0633771f-ce19-6211-fabe-3f7f676e53ab@gmail.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-08-07T23:10:31Z","receivedAt":"2017-08-07T23:10:43Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Mon, 7 Aug 2017 15:12:11 -0400\nBen Peart wrote:\n\n> I missed the offline discussion and so am trying to piece together what \n> this latest design is trying to do. Please let me know if I'm not \n> understanding something correctly.\n> \n> From what I can tell, objects are going to be segmented into two \n> \"types\" - those that were fetched from a remote source that allows \n> partial clones/fetches (lazyobject/imported) and those that come from \n> \"regular\" remote sources (homegrown) that requires all objects to exist \n> locally.\n> \n> FWIW, the names here are not making things clearer for me. If I'm \n> correct perhaps \"partial\" and \"normal\" would be better to indicate the \n> type of the source? Anyway...\n\nThat's right. As for names, I'm leaning now towards \"imported\" and\n\"non-imported\". \"Partial\" is a bit strange because such an object is\nfully available; it's just that the objects that it references are\npromised by the server.\n\n> Once the objects are segmented into the 2 types, the fsck connectivity \n> check code is updated to ignore missing objects from \"partial\" remotes \n> but still expect/validate them from \"normal\" remotes.\n> \n> This compromise seems reasonable - don't generate errors for missing \n> objects for remotes that returned a partial clone but do generate errors \n> for missing objects from normal clones as a missing object is always an \n> error in this case.\n\nYes. In addition, the references of \"imported\" objects are also\npotentially used when connectivity-checking \"non-imported\" objects - if\na \"non-imported\" object refers to an object that an \"imported\" object\nrefers to, that is fine, even though we don't have that object.\n\n> This segmentation is what is driving the need for the object loader to \n> build a new local pack file for every command that has to fetch a \n> missing object. For example, we can't just write a tree object from a \n> \"partial\" clone into the loose object store as we have no way for fsck \n> to treat them differently and ignore any missing objects referenced by \n> that tree object.\n> \n> My concern with this proposal is the combination of 1) writing a new \n> pack file for every git command that ends up bringing down a missing \n> object and 2) gc not compressing those pack files into a single pack file.\n> \n> We all know that git doesn't scale well with a lot of pack files as it \n> has to do a linear search through all the pack files when attempting to \n> find an object. I can see that very quickly, there would be a lot of \n> pack files generated and with gc ignoring \"partial\" pack files, this \n> would never get corrected.\n> \n> In our usage scenarios, _all_ of the objects come from \"partial\" clones \n> so all of our objects would end up in a series of \"partial\" pack files \n> and would have pretty poor performance as a result.\n\nOne possible solution...would support for annotating loose objects with\n\".remote\" be sufficient? (That is, for each loose object file created,\ncreate another of the same name but with \".remote\" appended.) This means\nthat a loose-object-creating lazy loader would need to create 2 files\nper object instead of one.\n\nThe lazy loader protocol will thus be updated to something resembling a\nprior version with the loader writing objects directly to the object\ndatabase, but now the loader is also responsible for creating the\n\".remote\" files. (In the Android use case, we probably won't need the\nwriting-to-partial-packfile mechanism anymore since only comparatively\nfew and large blobs will go in there.)\n"},{"id":"325806","messageId":"12fbcba3-1b31-2240-a330-e7cc11820f4a@gmail.com","threadId":"46515","inReplyTo":"20170807192151.GX13924@aiede.mtv.corp.google.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-08T14:18:43Z","receivedAt":"2017-08-08T14:18:54Z","isPatch":false,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/7/2017 3:21 PM, Jonathan Nieder wrote:\n> Hi,\n> \n> Ben Peart wrote:\n>>> On Fri, 04 Aug 2017 15:51:08 -0700\n>>> Junio C Hamano wrote:\n>>>> Jonathan Tan writes:\n> \n>>>>> \"Imported\" objects must be in a packfile that has a \".remote\"\n>>>>> file with arbitrary text (similar to the \".keep\" file). They come from\n>>>>> clones, fetches, and the object loader (see below).\n>>>>> ...\n>>>>>\n>>>>> A \"homegrown\" object is valid if each object it references:\n>>>>> 1. is a \"homegrown\" object,\n>>>>> 2. is an \"imported\" object, or\n>>>>> 3. is referenced by an \"imported\" object.\n>>>>\n>>>> Overall it captures what was discussed, and I think it is a good\n>>>> start.\n>>\n>> I missed the offline discussion and so am trying to piece together\n>> what this latest design is trying to do. Please let me know if I'm\n>> not understanding something correctly.\n> \n> I believe\n> https://public-inbox.org/git/cover.1501532294.git.jonathantanmy@google.com/\n> and the surrounding thread (especially\n> https://public-inbox.org/git/xmqqefsudjqk.fsf@gitster.mtv.corp.google.com/)\n> is the discussion Junio is referring to.\n> \n> [...]\n>> This segmentation is what is driving the need for the object loader\n>> to build a new local pack file for every command that has to fetch a\n>> missing object. For example, we can't just write a tree object from\n>> a \"partial\" clone into the loose object store as we have no way for\n>> fsck to treat them differently and ignore any missing objects\n>> referenced by that tree object.\n> \n> That's related and how it got lumped into this proposal, but it's not\n> the only motivation.\n> \n> Other aspects:\n> \n> 1. using pack files instead of loose objects means we can use deltas.\n> This is the primary motivation.\n> \n> 2. pack files can use reachability bitmaps (I realize there are\n> obstacles to getting benefit out of this because git's bitmap\n> format currently requires a pack to be self-contained, but I\n> thought it was worth mentioning for completeness).\n> \n> 3. existing git servers are oriented around pack files; they can\n> more cheaply serve objects from pack files in pack format,\n> including reusing deltas from them.\n> \n> 4. file systems cope better with a few large files than many small\n> files\n> \n> [...]\n>> We all know that git doesn't scale well with a lot of pack files as\n>> it has to do a linear search through all the pack files when\n>> attempting to find an object. I can see that very quickly, there\n>> would be a lot of pack files generated and with gc ignoring\n>> \"partial\" pack files, this would never get corrected.\n> \n> Yes, that's an important point. Regardless of this proposal, we need\n> to get more aggressive about concatenating pack files (e.g. by\n> implementing exponential rollup in \"git gc --auto\").\n> \n>> In our usage scenarios, _all_ of the objects come from \"partial\"\n>> clones so all of our objects would end up in a series of \"partial\"\n>> pack files and would have pretty poor performance as a result.\n> \n> Can you say more about this? Why would the pack files (or loose\n> objects, for that matter) never end up being consolidated into few\n> pack files?\n> \n\nOur initial clone is very sparse - we only pull down the commit we are \nabout to checkout and none of the blobs. All missing objects are then \ndownloaded on demand (and in this proposal, would end up in a \"partial\" \npack file). For performance reasons, we also (by default) download a \nserver computed pack file of commits and trees to pre-populate the local \ncache.\n\nWithout modification, fsck, repack, prune, gc will trigger every object \nin the repo to be downloaded. We punted for now and just block those \ncommands but eventually they need to be aware of missing objects so that \nthey do not cause them to be downloaded. Jonathan is already working on \nthis for fsck in another patch series.\n\n> [...]\n>> That thinking did lead me back to wondering again if we could live\n>> with a repo specific flag. If any clone/fetch was \"partial\" the\n>> flag is set and fsck ignore missing objects whether they came from a\n>> \"partial\" remote or not.\n>>\n>> I'll admit it isn't as robust if someone is mixing and matching\n>> remotes from different servers some of which are partial and some of\n>> which are not. I'm not sure how often that would actually happen\n>> but I _am_ certain a single repo specific flag is a _much_ simpler\n>> model than anything else we've come up with so far.\n> \n> The primary motivation in this thread is locally-created objects, not\n> objects obtained from other remotes. Objects obtained from other\n> remotes are more of an edge case.\n> \n\nThank you - that helps me to better understand the requirements of the \nproblem we're trying to solve. In short, that means what we really need \nis a way to identify locally created objects so that fsck can do a \ncomplete connectivity check on them. I'll have to think about a good \nway to do that - we've talked about a few but each has a different set \nof trade-offs and none of them are great (yet :)).\n\n> Thanks for your thoughtful comments.\n> \n> Jonathan\n> \n"},{"id":"325811","messageId":"693596b8-7a84-bcc8-7eef-2d534293e14b@gmail.com","threadId":"46515","inReplyTo":"xmqqwp6fp3mk.fsf@gitster.mtv.corp.google.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-08T16:45:40Z","receivedAt":"2017-08-08T16:45:48Z","isPatch":false,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/7/2017 3:41 PM, Junio C Hamano wrote:\n> Ben Peart writes:\n> \n>> My concern with this proposal is the combination of 1) writing a new\n>> pack file for every git command that ends up bringing down a missing\n>> object and 2) gc not compressing those pack files into a single pack\n>> file.\n> \n> Your noticing these is a sign that you read the outline of the\n> design correctly, I think.\n> \n> The basic idea is that the local fsck should tolerate missing\n> objects when they are known to be obtainable from that external\n> service, but should still be able to diagnose missing objects that\n> we do not know if the external service has, especially the ones that\n> have been newly created locally and not yet made available to them\n> by pushing them back.\n> \n\nThis helps me a lot as now I think I understand the primary requirement \nwe're trying to solve for. Let me rephrase it and see if this makes sense:\n\nWe need to be able to identify whether an object was created locally \n(and should pass more strict fsck/connectivity tests) or whether it came \nfrom a remote (and so any missing objects could presumably be fetched \nfrom the server).\n\nI agree it would be nice to solve this (and not just punt fsck - even if \nit is an opt-in behavior).\n\nWe've discussed a couple of different possible solutions, each of which \nhave different tradeoffs. Let me try to summarize here and perhaps \nsuggest some other possibilities:\n\n\nPromised list\n-------------\nThis provides an external data structure that allowed us to flag objects \nthat came from a remote server (vs created locally).\n\nThe biggest drawback is that this data structure can get very large and \nbecome difficult/expensive to generate/transfer/maintain.\n\nIt also (at least in one proposal) required protocol and server side \nchanges to support it.\n\n\nAnnotated via filename\n----------------------\nThis idea is to annotate the file names of objects that came from a \nremote server (pack files and loose objects) with a unique file \nextension (.remote) that indicates whether they are locally created or not.\n\nTo make this work, git must understand about both types of loose objects \nand pack files and search in both locations when looking for objects.\n\nAnother drawback of this is that commands (repack, gc) that optimize \nloose objects and pack files must now be aware of the different \nextensions and handle both while not merging remote and non-remote objects.\n\nIn short, we're creating separate object stores - one for locally \ncreated objects and one for everything else.\n\n\nNow a couple of different ideas:\n\nAnnotated via flags\n===================\nThe fundamental idea here is that we add the ability to flag locally \ncreated objects on the object itself.\n\nGiven that at the core, \"Git is a simple key-value data store\" can we \ntake advantage of that fact and include a \"locally created\" bit as a \nproperty on every object?\n\nI could not think of a good way to accomplish this as it is ultimately \nchanging the object format which creates rapidly expanding ripples of \nchange.\n\nFor example, The object header currently includes the type a space, the \nlength and a null. Even if we could add a \"local\" property (either by \nadding a 5th item, taking over the space, creating new object types, \netc), the fact that the header is included in the sha1 means that push \nwould become problematic as flipping the bit would change the sha and \nthe trees and commits that reference it.\n\n\nLocal list\n----------\nGiven the number of locally created objects is usually very small in \ncomparison to the total number of objects (even just due to history), it \nmakes more sense to track locally created objects instead of \npromised/remote objects.\n\nThe biggest advantage of this over the \"promised list\" is that the \n\"local list\" being maintained is _significantly_ smaller (often orders \nof magnitude smaller).\n\nAnother advantage over the \"promised list\" solution is that it doesn't \nrequire any server side or protocol changes.\n\nOn the client when objects are created (write_loose_object?) the new \nobjects are added to the \"local list\" and in the connectivity check \n(fsck) if the object is not in the \"local list,\" the connectivity check \ncan be skipped as any missing object can presumably be retrieved from \nthe server.\n\nA simple file format could be used (header + list of SHA1 values) and \nwrite_loose_object could do a trivial append. In fsck, the file could be \nloaded into a hashmap to make for fast existence checks.\n\nEntries could be removed from the \"local list\" for objects later fetched \nfrom a server (though I had a hard time contriving a scenario where this \nwould happen so I consider this optional).\n\nOn the surface, this seems like the simplest solution that meets the \nstated requirements.\n\n\nObject DB\n---------\nThis is a different way of providing separate object stores than the \n\"Annotated via filename\" proposal. It should be a cleaner/more elegant \nsolution that enables several other capabilities but it is also more \nwork to implement (isn't that always the case?).\n\nWe create an object store abstraction layer that enables multiple object \nstore providers to exist. The order that they are called should be \nconfigurable based on the command (esp have/read vs create/write). This \nenables features like tiered storage: in memory, pack, loose, alternate, \nlarge, remote.\n\nThe connectivity check in fsck would then only traverse and validate \nobjects that existed via the local object store providers.\n\nWhile I like the flexibility of this design and hope we can obtain it in \nthe long term for it's other benefits, it's a bit overkill for this \nspecific problem. The big drawback of this model is the cost to design \nand implement it.\n\n"},{"id":"325815","messageId":"20170808170311.GA169894@aiede.mtv.corp.google.com","threadId":"46515","inReplyTo":"693596b8-7a84-bcc8-7eef-2d534293e14b@gmail.com","subject":"Re: Partial clone design (with connectivity check for locally-created objects)","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-08-08T17:03:11Z","receivedAt":"2017-08-08T17:03:46Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nBen Peart wrote:\n\n> We've discussed a couple of different possible solutions, each of\n> which have different tradeoffs. Let me try to summarize here and\n> perhaps suggest some other possibilities:\n\nThanks for this. Some comments below.\n\n> Promised list\n> -------------\n> This provides an external data structure that allowed us to flag\n> objects that came from a remote server (vs created locally).\n>\n> The biggest drawback is that this data structure can get very large\n> and become difficult/expensive to generate/transfer/maintain.\n\nAgreed. Using a single immutable file to maintain this data with\nlock-and-rename update means that I/O when updating it can be a\nbottleneck and that contention can be a problem.\n\n> It also (at least in one proposal) required protocol and server side\n> changes to support it.\n\nI don't think that's a very big problem. This is the Git project: we\ncontrol the protocol and the server. Partial clone requires changing\nthe protocol and server already.\n\n> Annotated via filename\n> ----------------------\n> This idea is to annotate the file names of objects that came from a\n> remote server (pack files and loose objects) with a unique file\n> extension (.remote) that indicates whether they are locally created\n> or not.\n>\n> To make this work, git must understand about both types of loose\n> objects and pack files and search in both locations when looking for\n> objects.\n\nI don't understand the drawback you're describing here. To avoid a\nnumber of serious problems, Git already needs to be aware of partial\nclone. I don't think anyone has been proposing adding partial clone\nto upstream Git without a repository format extension (see\nDocumentation/technical/repository-version.txt) to prevent older\nversions of Git from being confused about such repositories.\n\nIf you don't do this, some problems include\n- confusing messages due to missing objects\n- errors over the wire protocol from trying to serve fetches and\n getting confused\n- \"git gc\" running and not knowing which objects are safe to be\n deleted\n\nSo the relevant issue couldn't be that Git has to be changed at all:\nit would be that a change is excessively invasive.\n\nBut it's not clear to me that the change you are describing is very\ninvasive.\n\n> Another drawback of this is that commands (repack, gc) that optimize\n> loose objects and pack files must now be aware of the different\n> extensions and handle both while not merging remote and non-remote\n> objects.\n>\n> In short, we're creating separate object stores - one for locally\n> created objects and one for everything else.\n\nThese also seem like non-issues.\n\nSome examples of problems I could imagine:\n\n- is writing multiple files when writing a loose object a problem for\n your setup?\n- is one of the operations described (repack, prune, fsck) too slow?\n\nDo you forsee either of those being an issue?\n\n> Now a couple of different ideas:\n>\n> Annotated via flags\n> ===================\n> The fundamental idea here is that we add the ability to flag locally\n> created objects on the object itself.\n\nDo you mean changing the underlying object format that produces an\nobject's object id? Or do you mean changing the container format?\n\nChanging the container format is exactly what was described in the\nprevious example (\"Annotated via filename\"). There are other ways to\nchange the container format: e.g. if writing multiple files when\nwriting a loose object is a problem, we could add a field that does\nnot affect the object id to the loose object format.\n\n[...]\n> Local list\n> ----------\n> Given the number of locally created objects is usually very small in\n> comparison to the total number of objects (even just due to\n> history), it makes more sense to track locally created objects\n> instead of promised/remote objects.\n>\n> The biggest advantage of this over the \"promised list\" is that the\n> \"local list\" being maintained is _significantly_ smaller (often\n> orders of magnitude smaller).\n[...]\n> On the surface, this seems like the simplest solution that meets the\n> stated requirements.\n\nThis has the same problems as the list of promised objects: excessive\nI/O and contention when updating the list.\n\nMoreover, it doesn't bring one of the main benefits of the list of\npromised objects. Promised objects are not present in the local\nrepository, so the list of promises provided a way to maintain some\ninformation about them (e.g., object size). Locally created objects\nare present in the local repository so they don't need such metadata.\n\n> Object DB\n> ---------\n\nIf I understand correctly, this is pushing the issues described in the\nother cases into a hook and making them not upstream Git's problem.\n\nBut it is still someone's problem. It just means upstream Git doesn't\nbenefit from their solution to it.\n\nI don't see a need to give up in that way just yet.\n\nI'm also available on #git-devel on freenode.net for real-time\nconversation. Logs are at http://bit.ly/aLzrmv. You can prepend a\nmessage with \"[off]\" to prevent it from showing up in logs. I'm also\nhappy to try to summarize any conversation that happens there here.\n\nThanks,\nJonathan\n"},{"id":"326475","messageId":"20170816003200.19992-1-jonathantanmy@google.com","threadId":"46515","inReplyTo":"20170804145113.5ceafafa@twelve2.svl.corp.google.com","subject":"[RFC PATCH] Updated \"imported object\" design","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-08-16T00:32:00Z","receivedAt":"2017-08-16T00:32:11Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This patch is based on an updated version of my refactoring of\npack-related functions [1].\n\nThis corresponds to patch 1 of my previous series [2]. I'm sending this\npatch out (before I update the rest) for 2 reasons:\n * to provide a demonstration of how the feature could be implemented,\n in the hope of restarting the discussion\n * to obtain comments about this patch to see if I'm heading in the\n right direction\n\nIn an earlier e-mail [3], I suggested that loose objects can also be\nmarked as \".imported\" (formerly \".remote\" - after looking at the code, I\ndecided to use \"imported\" throughout, since \"remote\" can be easily\nconfused as the opposite of \"local\", used to represent objects in the\nlocal store as opposed to an alternate store).\n\nHowever, I have only implemented the imported packed objects part -\nimported loose objects can be added later.\n\nIt still remains to be discussed whether we should mark the imported\nobjects or the non-imported objects as the source of promises, but I\nstill think that we should mark the imported objects. In this way, the\nnew properties (the provision of promises and the mark) coincide on the\nsame object, and the same things (locally created objects, fetches from\nnon-lazy-object-serving remotes) behave in the same way regardless of\nwhether extensions.lazyObject is set (allowing, for example, a repo to\nbe converted into a promise-enabled one solely through modifying the\nconfiguration).\n\nAlso, let me know if there's a better way to send out these patches for\nreview. Some of the code here has been reviewed before, for example.\n\n[1] https://public-inbox.org/git/cover.1502241234.git.jonathantanmy@google.com/\n\n[2] https://public-inbox.org/git/ffb734d277132802bcc25baa13e8ede3490af62a.1501532294.git.jonathantanmy@google.com/\n\n[3] https://public-inbox.org/git/20170807161031.7c4eae50@twelve2.svl.corp.google.com/\n-- 8< --\nenvironment, fsck: introduce lazyobject extension\n\nCurrently, Git does not support repos with very large numbers of objects\nor repos that wish to minimize manipulation of certain blobs (for\nexample, because they are very large) very well, even if the user\noperates mostly on part of the repo, because Git is designed on the\nassumption that every referenced object is available somewhere in the\nrepo storage. In such an arrangement, the full set of objects is usually\navailable in remote storage, ready to be lazily downloaded.\n\nIntroduce the concept of promises, objects believed by the local repo to\nbe downloadable from remote storage. An object is a promise if it is\nreferred to by an object in a specially marked packfile. Any such\npromise can be validly referred to, even if the object itself is not in\nthe local repo.\n\nThis functionality is guarded behind a new repository extension option\n`extensions.lazyObject`. The value of `extensions.lazyObject` must be a\nstring. The meaning of this string will be defined in a subsequent\ncommit.\n\nTeach fsck about the new state of affairs. In this commit, teach fsck\nthat promises referenced from the reflog are not an error case; in\nfuture commits, fsck will be taught about other cases.\n\nSigned-off-by: Jonathan Tan \n---\n Documentation/technical/repository-version.txt | 8 +++\n builtin/fsck.c | 64 +++++++++++++++++++-\n cache.h | 5 +-\n environment.c | 1 +\n pack.h | 1 +\n packfile.c | 13 +++-\n setup.c | 7 ++-\n t/t0410-lazy-object.sh | 84 ++++++++++++++++++++++++++\n 8 files changed, 177 insertions(+), 6 deletions(-)\n create mode 100755 t/t0410-lazy-object.sh\n\ndiff --git a/Documentation/technical/repository-version.txt b/Documentation/technical/repository-version.txt\nindex 00ad37986..71cb3bfee 100644\n--- a/Documentation/technical/repository-version.txt\n+++ b/Documentation/technical/repository-version.txt\n@@ -86,3 +86,11 @@ for testing format-1 compatibility.\n When the config key `extensions.preciousObjects` is set to `true`,\n objects in the repository MUST NOT be deleted (e.g., by `git-prune` or\n `git repack -d`).\n+\n+`lazyObject`\n+~~~~~~~~~~~~~~~~~\n+\n+When the config key `extensions.lazyObject` is set, Git does not treat\n+missing objects as errors. The value of `extensions.lazyObject` must be\n+a string. NEEDSWORK: define what this string contains when the\n+appropriate functionality is implemented.\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex 99dea7adf..25265b1fe 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -15,6 +15,7 @@\n #include \"progress.h\"\n #include \"streaming.h\"\n #include \"decorate.h\"\n+#include \"oidset.h\"\n \n #define REACHABLE 0x0001\n #define SEEN 0x0002\n@@ -43,6 +44,67 @@ static int name_objects;\n #define ERROR_PACK 04\n #define ERROR_REFS 010\n \n+/*\n+ * Objects that are believed to be loadable by the lazy loader, because\n+ * they are referred to by an imported object. If an object that we have\n+ * refers to such an object even though we don't have that object, it is\n+ * not an error.\n+ */\n+static struct oidset promises;\n+static int promises_prepared;\n+\n+static int add_promise(const struct object_id *oid, struct packed_git *pack,\n+\t\t uint32_t pos, void *data)\n+{\n+\tstruct object *obj = parse_object(oid);\n+\tif (!obj)\n+\t\t/*\n+\t\t * Error messages are given when packs are verified, so\n+\t\t * do not print any here.\n+\t\t */\n+\t\treturn 0;\n+\t\n+\t/*\n+\t * If this is a tree, commit, or tag, the objects it refers\n+\t * to are promises. (Blobs refer to no objects.)\n+\t */\n+\tif (obj->type == OBJ_TREE) {\n+\t\tstruct tree *tree = (struct tree *) obj;\n+\t\tstruct tree_desc desc;\n+\t\tstruct name_entry entry;\n+\t\tif (init_tree_desc_gently(&desc, tree->buffer, tree->size))\n+\t\t\t/*\n+\t\t\t * Error messages are given when packs are\n+\t\t\t * verified, so do not print any here.\n+\t\t\t */\n+\t\t\treturn 0;\n+\t\twhile (tree_entry_gently(&desc, &entry))\n+\t\t\toidset_insert(&promises, entry.oid);\n+\t} else if (obj->type == OBJ_COMMIT) {\n+\t\tstruct commit *commit = (struct commit *) obj;\n+\t\tstruct commit_list *parents = commit->parents;\n+\n+\t\toidset_insert(&promises, &commit->tree->object.oid);\n+\t\tfor (; parents; parents = parents->next)\n+\t\t\toidset_insert(&promises, &parents->item->object.oid);\n+\t} else if (obj->type == OBJ_TAG) {\n+\t\tstruct tag *tag = (struct tag *) obj;\n+\t\toidset_insert(&promises, &tag->tagged->oid);\n+\t}\n+\treturn 0;\n+}\n+\n+static int is_promise(const struct object_id *oid)\n+{\n+\tif (!promises_prepared) {\n+\t\tif (repository_format_lazy_object)\n+\t\t\tfor_each_packed_object(add_promise, NULL,\n+\t\t\t\t\t FOR_EACH_OBJECT_IMPORTED_ONLY);\n+\t\tpromises_prepared = 1;\n+\t}\n+\treturn oidset_contains(&promises, oid);\n+}\n+\n static const char *describe_object(struct object *obj)\n {\n \tstatic struct strbuf buf = STRBUF_INIT;\n@@ -410,7 +472,7 @@ static void fsck_handle_reflog_oid(const char *refname, struct object_id *oid,\n \t\t\t\t\txstrfmt(\"%s@{%\"PRItime\"}\", refname, timestamp));\n \t\t\tobj->used = 1;\n \t\t\tmark_object_reachable(obj);\n-\t\t} else {\n+\t\t} else if (!is_promise(oid)) {\n \t\t\terror(\"%s: invalid reflog entry %s\", refname, oid_to_hex(oid));\n \t\t\terrors_found |= ERROR_REACHABLE;\n \t\t}\ndiff --git a/cache.h b/cache.h\nindex b15645672..f529096c8 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -853,10 +853,12 @@ extern int grafts_replace_parents;\n #define GIT_REPO_VERSION 0\n #define GIT_REPO_VERSION_READ 1\n extern int repository_format_precious_objects;\n+extern char *repository_format_lazy_object;\n \n struct repository_format {\n \tint version;\n \tint precious_objects;\n+\tchar *lazy_object;\n \tint is_bare;\n \tchar *work_tree;\n \tstruct string_list unknown_extensions;\n@@ -1584,7 +1586,8 @@ extern struct packed_git {\n \tunsigned pack_local:1,\n \t\t pack_keep:1,\n \t\t freshened:1,\n-\t\t do_not_close:1;\n+\t\t do_not_close:1,\n+\t\t pack_imported:1;\n \tunsigned char sha1[20];\n \tstruct revindex_entry *revindex;\n \t/* something like \".git/objects/pack/xxxxx.pack\" */\ndiff --git a/environment.c b/environment.c\nindex 3fd4b1084..cd8ef2897 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -27,6 +27,7 @@ int warn_ambiguous_refs = 1;\n int warn_on_object_refname_ambiguity = 1;\n int ref_paranoia = -1;\n int repository_format_precious_objects;\n+char *repository_format_lazy_object;\n const char *git_commit_encoding;\n const char *git_log_output_encoding;\n const char *apply_default_whitespace;\ndiff --git a/pack.h b/pack.h\nindex 6aae1a7c3..7c196c6cd 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -229,6 +229,7 @@ extern int has_pack_index(const unsigned char *sha1);\n * repository and any alternates repositories (unless the\n * FOR_EACH_OBJECT_LOCAL_ONLY flag, defined in cache.h, is set).\n */\n+#define FOR_EACH_OBJECT_IMPORTED_ONLY 2\n typedef int each_packed_object_fn(const struct object_id *oid,\n \t\t\t\t struct packed_git *pack,\n \t\t\t\t uint32_t pos,\ndiff --git a/packfile.c b/packfile.c\nindex 2f008ede7..90028f9af 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -637,10 +637,10 @@ struct packed_git *add_packed_git(const char *path, size_t path_len, int local)\n \t\treturn NULL;\n \n \t/*\n-\t * \".pack\" is long enough to hold any suffix we're adding (and\n+\t * \".imported\" is long enough to hold any suffix we're adding (and\n \t * the use xsnprintf double-checks that)\n \t */\n-\talloc = st_add3(path_len, strlen(\".pack\"), 1);\n+\talloc = st_add3(path_len, strlen(\".imported\"), 1);\n \tp = alloc_packed_git(alloc);\n \tmemcpy(p->pack_name, path, path_len);\n \n@@ -648,6 +648,10 @@ struct packed_git *add_packed_git(const char *path, size_t path_len, int local)\n \tif (!access(p->pack_name, F_OK))\n \t\tp->pack_keep = 1;\n \n+\txsnprintf(p->pack_name + path_len, alloc - path_len, \".imported\");\n+\tif (!access(p->pack_name, F_OK))\n+\t\tp->pack_imported = 1;\n+\n \txsnprintf(p->pack_name + path_len, alloc - path_len, \".pack\");\n \tif (stat(p->pack_name, &st) || !S_ISREG(st.st_mode)) {\n \t\tfree(p);\n@@ -775,7 +779,8 @@ static void prepare_packed_git_one(char *objdir, int local)\n \t\tif (ends_with(de->d_name, \".idx\") ||\n \t\t ends_with(de->d_name, \".pack\") ||\n \t\t ends_with(de->d_name, \".bitmap\") ||\n-\t\t ends_with(de->d_name, \".keep\"))\n+\t\t ends_with(de->d_name, \".keep\") ||\n+\t\t ends_with(de->d_name, \".imported\"))\n \t\t\tstring_list_append(&garbage, path.buf);\n \t\telse\n \t\t\treport_garbage(PACKDIR_FILE_GARBAGE, path.buf);\n@@ -1893,6 +1898,8 @@ int for_each_packed_object(each_packed_object_fn cb, void *data, unsigned flags)\n \tfor (p = packed_git; p; p = p->next) {\n \t\tif ((flags & FOR_EACH_OBJECT_LOCAL_ONLY) && !p->pack_local)\n \t\t\tcontinue;\n+\t\tif ((flags & FOR_EACH_OBJECT_IMPORTED_ONLY) && !p->pack_imported)\n+\t\t\tcontinue;\n \t\tif (open_pack_index(p)) {\n \t\t\tpack_errors = 1;\n \t\t\tcontinue;\ndiff --git a/setup.c b/setup.c\nindex 860507e1f..94cfde3cc 100644\n--- a/setup.c\n+++ b/setup.c\n@@ -425,7 +425,11 @@ static int check_repo_format(const char *var, const char *value, void *vdata)\n \t\t\t;\n \t\telse if (!strcmp(ext, \"preciousobjects\"))\n \t\t\tdata->precious_objects = git_config_bool(var, value);\n-\t\telse\n+\t\telse if (!strcmp(ext, \"lazyobject\")) {\n+\t\t\tif (!value)\n+\t\t\t\treturn config_error_nonbool(var);\n+\t\t\tdata->lazy_object = xstrdup(value);\n+\t\t} else\n \t\t\tstring_list_append(&data->unknown_extensions, ext);\n \t} else if (strcmp(var, \"core.bare\") == 0) {\n \t\tdata->is_bare = git_config_bool(var, value);\n@@ -468,6 +472,7 @@ static int check_repository_format_gently(const char *gitdir, int *nongit_ok)\n \t}\n \n \trepository_format_precious_objects = candidate.precious_objects;\n+\trepository_format_lazy_object = candidate.lazy_object;\n \tstring_list_clear(&candidate.unknown_extensions, 0);\n \tif (!has_common) {\n \t\tif (candidate.is_bare != -1) {\ndiff --git a/t/t0410-lazy-object.sh b/t/t0410-lazy-object.sh\nnew file mode 100755\nindex 000000000..2368150d4\n--- /dev/null\n+++ b/t/t0410-lazy-object.sh\n@@ -0,0 +1,84 @@\n+#!/bin/sh\n+\n+test_description='lazy object'\n+\n+. ./test-lib.sh\n+\n+delete_object () {\n+\trm $1/.git/objects/$(echo $2 | cut -c1-2)/$(echo $2 | cut -c3-40)\n+}\n+\n+pack_imported_object() {\n+\tprintf \"%s\" \"$1\" | git -C repo pack-objects .git/objects/pack/pack &&\n+\t(\n+\t\tcd repo/.git/objects/pack &&\n+\t\t>$(basename --suffix=.pack *.pack).imported\n+\t)\n+}\n+\n+test_expect_success 'missing reflog object referred to by imported commit passes fsck' '\n+\ttest_create_repo repo &&\n+\ttest_commit -C repo my_commit &&\n+\n+\tA=$(git -C repo commit-tree -m a HEAD^{tree}) &&\n+\tC=$(git -C repo commit-tree -m c -p $A HEAD^{tree}) &&\n+\n+\t# Reference $A only from reflog, and delete it\n+\tgit -C repo branch my_branch \"$A\" &&\n+\tgit -C repo branch -f my_branch my_commit &&\n+\tdelete_object repo \"$A\" &&\n+\n+\t# Designate $C, which refers to $A, as an imported object\n+\tpack_imported_object \"$C\\n\" &&\n+\n+\t# Normally, it fails\n+\ttest_must_fail git -C repo fsck &&\n+\n+\t# But with the extension, it succeeds\n+\tgit -C repo config core.repositoryformatversion 1 &&\n+\tgit -C repo config extensions.lazyobject \"arbitrary string\" &&\n+\tgit -C repo fsck\n+'\n+\n+test_expect_success 'missing reflog object referred to by imported tag passes fsck' '\n+\trm -rf repo &&\n+\ttest_create_repo repo &&\n+\ttest_commit -C repo my_commit &&\n+\n+\tA=$(git -C repo commit-tree -m a HEAD^{tree}) &&\n+\tgit -C repo tag -a -m d my_tag_name $A &&\n+\tT=$(git -C repo rev-parse my_tag_name) &&\n+\tgit -C repo tag -d my_tag_name &&\n+\n+\t# Reference $A only from reflog, and delete it\n+\tgit -C repo branch my_branch \"$A\" &&\n+\tgit -C repo branch -f my_branch my_commit &&\n+\tdelete_object repo \"$A\" &&\n+\n+\t# Designate $T, which refers to $A, as an imported object\n+\tpack_imported_object \"$T\\n\" &&\n+\n+\tgit -C repo config core.repositoryformatversion 1 &&\n+\tgit -C repo config extensions.lazyobject \"arbitrary string\" &&\n+\tgit -C repo fsck\n+'\n+\n+test_expect_success 'missing reflog object alone fails fsck, even with extension set' '\n+\trm -rf repo &&\n+\ttest_create_repo repo &&\n+\ttest_commit -C repo my_commit &&\n+\n+\tA=$(git -C repo commit-tree -m a HEAD^{tree}) &&\n+\tB=$(git -C repo commit-tree -m b HEAD^{tree}) &&\n+\n+\t# Reference $A only from reflog, and delete it\n+\tgit -C repo branch my_branch \"$A\" &&\n+\tgit -C repo branch -f my_branch my_commit &&\n+\tdelete_object repo \"$A\" &&\n+\n+\tgit -C repo config core.repositoryformatversion 1 &&\n+\tgit -C repo config extensions.lazyobject \"arbitrary string\" &&\n+\ttest_must_fail git -C repo fsck\n+'\n+\n+test_done\n-- \n2.14.1.480.gb18f417b89-goog\n\n"},{"id":"326557","messageId":"xmqqa82zjlt4.fsf@gitster.mtv.corp.google.com","threadId":"46515","inReplyTo":"20170816003200.19992-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] Updated \"imported object\" design","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-16T20:32:23Z","receivedAt":"2017-08-16T20:32:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> Also, let me know if there's a better way to send out these patches for\n> review. Some of the code here has been reviewed before, for example.\n>\n> [1] https://public-inbox.org/git/cover.1502241234.git.jonathantanmy@google.com/\n>\n> [2] https://public-inbox.org/git/ffb734d277132802bcc25baa13e8ede3490af62a.1501532294.git.jonathantanmy@google.com/\n>\n> [3] https://public-inbox.org/git/20170807161031.7c4eae50@twelve2.svl.corp.google.com/\n\n... and some of the code exists only in the list archive, so we\ndon't know which other topic if any we may want to eject tentatively\nif we wanted to give precedence to move this topic forward over\nothers. I'll worry about it later but help from others is also\nappreciated.\n\nAs to the contents of this patch, overall, everything makes sense,\nexcept for one thing that makes me wonder. It's not that I see\nsomething specifically incorrect--it is just I do not yet quiet\nfathom the implications of.\n\n> +/*\n> + * Objects that are believed to be loadable by the lazy loader, because\n> + * they are referred to by an imported object. If an object that we have\n> + * refers to such an object even though we don't have that object, it is\n> + * not an error.\n> + */\n> +static struct oidset promises;\n> +static int promises_prepared;\n> +\n> +static int add_promise(const struct object_id *oid, struct packed_git *pack,\n> +\t\t uint32_t pos, void *data)\n> +{\n> +\tstruct object *obj = parse_object(oid);\n> +\tif (!obj)\n> +\t\t/*\n> +\t\t * Error messages are given when packs are verified, so\n> +\t\t * do not print any here.\n> +\t\t */\n> +\t\treturn 0;\n> +\t\n> +\t/*\n> +\t * If this is a tree, commit, or tag, the objects it refers\n> +\t * to are promises. (Blobs refer to no objects.)\n> +\t */\n> +\tif (obj->type == OBJ_TREE) {\n> +\t\tstruct tree *tree = (struct tree *) obj;\n> +\t\tstruct tree_desc desc;\n> +\t\tstruct name_entry entry;\n> +\t\tif (init_tree_desc_gently(&desc, tree->buffer, tree->size))\n> +\t\t\t/*\n> +\t\t\t * Error messages are given when packs are\n> +\t\t\t * verified, so do not print any here.\n> +\t\t\t */\n> +\t\t\treturn 0;\n> +\t\twhile (tree_entry_gently(&desc, &entry))\n> +\t\t\toidset_insert(&promises, entry.oid);\n> +\t} else if (obj->type == OBJ_COMMIT) {\n> +\t\tstruct commit *commit = (struct commit *) obj;\n> +\t\tstruct commit_list *parents = commit->parents;\n> +\n> +\t\toidset_insert(&promises, &commit->tree->object.oid);\n> +\t\tfor (; parents; parents = parents->next)\n> +\t\t\toidset_insert(&promises, &parents->item->object.oid);\n> +\t} else if (obj->type == OBJ_TAG) {\n> +\t\tstruct tag *tag = (struct tag *) obj;\n> +\t\toidset_insert(&promises, &tag->tagged->oid);\n> +\t}\n> +\treturn 0;\n> +}\n\nThis collects names of the objects that are _directly_ referred to\nby imported objects. An imported pack may have a commit, whose\ntop-level tree may or may not appear in the same pack, or the tree\nmay exist locally but not in the same pack. Or the tree may not be\nlocally available at all. In any of these four cases, the top-level\ntree is listed in the \"promises\" set. Same for trees and tags.\n\nI wonder if all of the calls to oidset_insert() in this function\nwant to be guarded by \"mark it as promised only when the referrent\nis *not* locally available\" to keep the promises set minimally\npopulated. The only change needed to fsck in order to make it\nrefrain from treating a missing but promised object as an error\nwould be:\n\n - if (object is missing)\n + if (object is missing && object is not promised)\n error(\"that object must be there but missing\");\n\nso there is no point in throwing something that we know we locally\nhave in this oidset, right?\n\nOn the other hand, cost of such additional checks in this function\nmay outweigh the savings of both memory pressure and look-up cost,\nso I do not know how the tradeoff would turn out.\n\n> +static int is_promise(const struct object_id *oid)\n> +{\n> +\tif (!promises_prepared) {\n> +\t\tif (repository_format_lazy_object)\n> +\t\t\tfor_each_packed_object(add_promise, NULL,\n> +\t\t\t\t\t FOR_EACH_OBJECT_IMPORTED_ONLY);\n> +\t\tpromises_prepared = 1;\n> +\t}\n> +\treturn oidset_contains(&promises, oid);\n> +}\n\nSomehow I'm tempted to call this function \"is_promised()\" but that\nis a minor naming issue.\n\n> static const char *describe_object(struct object *obj)\n> {\n> \tstatic struct strbuf buf = STRBUF_INIT;\n> @@ -410,7 +472,7 @@ static void fsck_handle_reflog_oid(const char *refname, struct object_id *oid,\n> \t\t\t\t\txstrfmt(\"%s@{%\"PRItime\"}\", refname, timestamp));\n> \t\t\tobj->used = 1;\n> \t\t\tmark_object_reachable(obj);\n> -\t\t} else {\n> +\t\t} else if (!is_promise(oid)) {\n> \t\t\terror(\"%s: invalid reflog entry %s\", refname, oid_to_hex(oid));\n> \t\t\terrors_found |= ERROR_REACHABLE;\n> \t\t}\n\nThis is about certainly is one place we want to check if the missing\nobject is OK, but I'm a bit surprised if this were the only place.\n\nDon't we need \"while trying to follow all the outgoing links from\nthis tree object, and we found this object is not available locally;\nnormally we would mark it as an error but it turns out that the\nmissing one is in the promised set of objects, so it is OK\" for the\nnormal connectivity traversal codepaths, for example?\n\n"},{"id":"326561","messageId":"20170816143515.0a74f959@twelve2.svl.corp.google.com","threadId":"46515","inReplyTo":"xmqqa82zjlt4.fsf@gitster.mtv.corp.google.com","subject":"Re: [RFC PATCH] Updated \"imported object\" design","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-08-16T21:35:15Z","receivedAt":"2017-08-16T21:35:26Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Wed, 16 Aug 2017 13:32:23 -0700\nJunio C Hamano wrote:\n\n> Jonathan Tan writes:\n> \n> > Also, let me know if there's a better way to send out these patches for\n> > review. Some of the code here has been reviewed before, for example.\n> >\n> > [1] https://public-inbox.org/git/cover.1502241234.git.jonathantanmy@google.com/\n> >\n> > [2] https://public-inbox.org/git/ffb734d277132802bcc25baa13e8ede3490af62a.1501532294.git.jonathantanmy@google.com/\n> >\n> > [3] https://public-inbox.org/git/20170807161031.7c4eae50@twelve2.svl.corp.google.com/\n> \n> ... and some of the code exists only in the list archive, so we\n> don't know which other topic if any we may want to eject tentatively\n> if we wanted to give precedence to move this topic forward over\n> others. I'll worry about it later but help from others is also\n> appreciated.\n\nThanks - I can help take a look when it is time to move the code in.\n\nI think the issue here is whether we want to move this topic forward or\nnot, that is, if this (special \".imported\" objects) is the best way to\nsolve (at least partially) the connectivity check part of tolerating\nmissing objects. I hope that we can continue to talk about it.\n\n> This collects names of the objects that are _directly_ referred to\n> by imported objects. An imported pack may have a commit, whose\n> top-level tree may or may not appear in the same pack, or the tree\n> may exist locally but not in the same pack. Or the tree may not be\n> locally available at all. In any of these four cases, the top-level\n> tree is listed in the \"promises\" set. Same for trees and tags.\n> \n> I wonder if all of the calls to oidset_insert() in this function\n> want to be guarded by \"mark it as promised only when the referrent\n> is *not* locally available\" to keep the promises set minimally\n> populated. The only change needed to fsck in order to make it\n> refrain from treating a missing but promised object as an error\n> would be:\n> \n> - if (object is missing)\n> + if (object is missing && object is not promised)\n> error(\"that object must be there but missing\");\n> \n> so there is no point in throwing something that we know we locally\n> have in this oidset, right?\n> \n> On the other hand, cost of such additional checks in this function\n> may outweigh the savings of both memory pressure and look-up cost,\n> so I do not know how the tradeoff would turn out.\n\nI also don't know how the tradeoff would turn out, so I leaned towards\nthe slightly simpler solution of not doing the check. In the future,\nmaybe a t/perf test can be done to decide between the two.\n\n> > +static int is_promise(const struct object_id *oid)\n> > +{\n> > +\tif (!promises_prepared) {\n> > +\t\tif (repository_format_lazy_object)\n> > +\t\t\tfor_each_packed_object(add_promise, NULL,\n> > +\t\t\t\t\t FOR_EACH_OBJECT_IMPORTED_ONLY);\n> > +\t\tpromises_prepared = 1;\n> > +\t}\n> > +\treturn oidset_contains(&promises, oid);\n> > +}\n> \n> Somehow I'm tempted to call this function \"is_promised()\" but that\n> is a minor naming issue.\n\nI was trying to be consistent in using the name \"promise\" instead of\n\"promised object/tag/commit/tree/blob\" everywhere, but we can switch if\nneed be (for example, if we don't want to limit the generic name\n\"promise\" to merely objects).\n\n> > static const char *describe_object(struct object *obj)\n> > {\n> > \tstatic struct strbuf buf = STRBUF_INIT;\n> > @@ -410,7 +472,7 @@ static void fsck_handle_reflog_oid(const char *refname, struct object_id *oid,\n> > \t\t\t\t\txstrfmt(\"%s@{%\"PRItime\"}\", refname, timestamp));\n> > \t\t\tobj->used = 1;\n> > \t\t\tmark_object_reachable(obj);\n> > -\t\t} else {\n> > +\t\t} else if (!is_promise(oid)) {\n> > \t\t\terror(\"%s: invalid reflog entry %s\", refname, oid_to_hex(oid));\n> > \t\t\terrors_found |= ERROR_REACHABLE;\n> > \t\t}\n> \n> This is about certainly is one place we want to check if the missing\n> object is OK, but I'm a bit surprised if this were the only place.\n> \n> Don't we need \"while trying to follow all the outgoing links from\n> this tree object, and we found this object is not available locally;\n> normally we would mark it as an error but it turns out that the\n> missing one is in the promised set of objects, so it is OK\" for the\n> normal connectivity traversal codepaths, for example?\n\nThat's right. The places to make this change are the same as those in\nsome earlier patches I sent (patches 2-4 in [1]).\n\n[1] https://public-inbox.org/git/cover.1501532294.git.jonathantanmy@google.com/\n"},{"id":"326633","messageId":"850a7b88-8e3c-4c4b-4a0d-16e2aa2145fc@gmail.com","threadId":"46515","inReplyTo":"20170816003200.19992-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH] Updated \"imported object\" design","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-17T20:07:26Z","receivedAt":"2017-08-17T20:07:33Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/15/2017 8:32 PM, Jonathan Tan wrote:\n> This patch is based on an updated version of my refactoring of\n> pack-related functions [1].\n> \n> This corresponds to patch 1 of my previous series [2]. I'm sending this\n> patch out (before I update the rest) for 2 reasons:\n> * to provide a demonstration of how the feature could be implemented,\n> in the hope of restarting the discussion\n> * to obtain comments about this patch to see if I'm heading in the\n> right direction\n> \n> In an earlier e-mail [3], I suggested that loose objects can also be\n> marked as \".imported\" (formerly \".remote\" - after looking at the code, I\n> decided to use \"imported\" throughout, since \"remote\" can be easily\n> confused as the opposite of \"local\", used to represent objects in the\n> local store as opposed to an alternate store).\n> \n> However, I have only implemented the imported packed objects part -\n> imported loose objects can be added later.\n> \n> It still remains to be discussed whether we should mark the imported\n> objects or the non-imported objects as the source of promises, but I\n> still think that we should mark the imported objects. In this way, the\n> new properties (the provision of promises and the mark) coincide on the\n> same object, and the same things (locally created objects, fetches from\n> non-lazy-object-serving remotes) behave in the same way regardless of\n> whether extensions.lazyObject is set (allowing, for example, a repo to\n> be converted into a promise-enabled one solely through modifying the\n> configuration).\n> \n\nThis illustrates another place we need to resolve the naming/vocabulary. \n We should at least be consistent to make it easier to discuss/explain. \n We obviously went with \"virtual\" when building GVFS but I'm OK with \n\"lazy\" as long as we're consistent. Some examples of how the naming can \nclarify or confuse:\n\n'Promise-enable your repo by setting the \"extensions.lazyObject\" flag'\n\n'Enable your repo to lazily fetch objects by setting the \n\"extensions.lazyObject\"'\n\n'Virtualize your repo by setting the \"extensions.virtualize\" flag'\n\nWe may want to carry the same name into the filename we use to mark the \n(virtualized/lazy/promised/imported) objects.\n\n(This reminds me that there are only 2 hard problems in computer \nscience...) ;)\n\n\nIt is true that converting a normal repo to \nvirtualized/lazy/promise-enabled repo wouldn't have to munge with the \nobject marking but since this only happens once, I wouldn't make that \nprimary decision maker (and switching back would require munging the \nobjects anyway). I think we can make either work (ie tagging local vs \nnon-local/remote/imported/promised/lazy/virtual).\n\nI'm fine leaving \"how\" the objects are marked as an implementation \ndetail - the design requires them to be marked, the person writing the \ncode can figure out the fastest way to accomplish that.\n\nIn the current patch/design, the access time to check for the existence \nof an \"imported\" file is going to be dwarfed by the cost of opening and \nparsing every object (loose and pack) to get its oid so that isn't \nreally an issue.\n\n> +/*\n> + * Objects that are believed to be loadable by the lazy loader, because\n> + * they are referred to by an imported object. If an object that we have\n> + * refers to such an object even though we don't have that object, it is\n> + * not an error.\n> + */\n> +static struct oidset promises;\n> +static int promises_prepared;\n> +\n> +static int add_promise(const struct object_id *oid, struct packed_git *pack,\n> +\t\t uint32_t pos, void *data)\n> +{\n> +\tstruct object *obj = parse_object(oid);\n> +\tif (!obj)\n> +\t\t/*\n> +\t\t * Error messages are given when packs are verified, so\n> +\t\t * do not print any here.\n> +\t\t */\n> +\t\treturn 0;\n> +\t\n> +\t/*\n> +\t * If this is a tree, commit, or tag, the objects it refers\n> +\t * to are promises. (Blobs refer to no objects.)\n> +\t */\n> +\tif (obj->type == OBJ_TREE) {\n> +\t\tstruct tree *tree = (struct tree *) obj;\n> +\t\tstruct tree_desc desc;\n> +\t\tstruct name_entry entry;\n> +\t\tif (init_tree_desc_gently(&desc, tree->buffer, tree->size))\n> +\t\t\t/*\n> +\t\t\t * Error messages are given when packs are\n> +\t\t\t * verified, so do not print any here.\n> +\t\t\t */\n> +\t\t\treturn 0;\n> +\t\twhile (tree_entry_gently(&desc, &entry))\n> +\t\t\toidset_insert(&promises, entry.oid);\n> +\t} else if (obj->type == OBJ_COMMIT) {\n> +\t\tstruct commit *commit = (struct commit *) obj;\n> +\t\tstruct commit_list *parents = commit->parents;\n> +\n> +\t\toidset_insert(&promises, &commit->tree->object.oid);\n> +\t\tfor (; parents; parents = parents->next)\n> +\t\t\toidset_insert(&promises, &parents->item->object.oid);\n> +\t} else if (obj->type == OBJ_TAG) {\n> +\t\tstruct tag *tag = (struct tag *) obj;\n> +\t\toidset_insert(&promises, &tag->tagged->oid);\n> +\t}\n> +\treturn 0;\n> +}\n> +\n> +static int is_promise(const struct object_id *oid)\n> +{\n> +\tif (!promises_prepared) {\n> +\t\tif (repository_format_lazy_object)\n> +\t\t\tfor_each_packed_object(add_promise, NULL,\n> +\t\t\t\t\t FOR_EACH_OBJECT_IMPORTED_ONLY);\n> +\t\tpromises_prepared = 1;\n> +\t}\n> +\treturn oidset_contains(&promises, oid);\n> +}\n> +\n\nI think this all works and would meet the requirements we've been \ndiscussing. The big trade off here vs what we first discussed with \npromises is that we are generating the list of promises on the fly when \nthey are needed rather than downloading and maintaining a list locally.\n\nMy biggest concern with this model is the cost of opening and parsing \nevery imported object (loose and pack for local and alternates) to build \nthe oidset of promises.\n\nIn fsck this probably won't be an issue as it already focuses on \ncorrectness at the expense of speed. I'm more worried about when we add \nthe same/similar logic into check_connected. That impacts fetch, clone, \nand receive_pack.\n\nI guess the only way we can know for sure it to do a perf test and \nmeasure the impact.\n"},{"id":"326639","messageId":"c6787a0b-ba7c-106a-66bd-5c2d38752ccb@gmail.com","threadId":"46515","inReplyTo":"20170816143515.0a74f959@twelve2.svl.corp.google.com","subject":"Re: [RFC PATCH] Updated \"imported object\" design","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-17T20:50:35Z","receivedAt":"2017-08-17T20:50:42Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/16/2017 5:35 PM, Jonathan Tan wrote:\n> On Wed, 16 Aug 2017 13:32:23 -0700\n> Junio C Hamano wrote:\n> \n>> Jonathan Tan writes:\n>>\n>>> Also, let me know if there's a better way to send out these patches for\n>>> review. Some of the code here has been reviewed before, for example.\n>>>\n>>> [1] https://public-inbox.org/git/cover.1502241234.git.jonathantanmy@google.com/\n>>>\n>>> [2] https://public-inbox.org/git/ffb734d277132802bcc25baa13e8ede3490af62a.1501532294.git.jonathantanmy@google.com/\n>>>\n>>> [3] https://public-inbox.org/git/20170807161031.7c4eae50@twelve2.svl.corp.google.com/\n>>\n>> ... and some of the code exists only in the list archive, so we\n>> don't know which other topic if any we may want to eject tentatively\n>> if we wanted to give precedence to move this topic forward over\n>> others. I'll worry about it later but help from others is also\n>> appreciated.\n> \n> Thanks - I can help take a look when it is time to move the code in.\n> \n\nI agree that having this depend on patches elsewhere in the list archive \nmakes it more difficult to review. I know I like to see things in \ncontext to get a better picture.\n\n> I think the issue here is whether we want to move this topic forward or\n> not, that is, if this (special \".imported\" objects) is the best way to\n> solve (at least partially) the connectivity check part of tolerating\n> missing objects. I hope that we can continue to talk about it.\n> \n\nI think this topic should continue to move forward so that we can \nprovide reasonable connectivity tests for fsck and check_connected in \nthe face of partial clones. I'm not sure the prototype implementation \nof reading/parsing all imported objects to build the promised oidset is \nthe most performant model but we can continue to investigate the best \noptions.\n\n>> This collects names of the objects that are _directly_ referred to\n>> by imported objects. An imported pack may have a commit, whose\n>> top-level tree may or may not appear in the same pack, or the tree\n>> may exist locally but not in the same pack. Or the tree may not be\n>> locally available at all. In any of these four cases, the top-level\n>> tree is listed in the \"promises\" set. Same for trees and tags.\n>>\n>> I wonder if all of the calls to oidset_insert() in this function\n>> want to be guarded by \"mark it as promised only when the referrent\n>> is *not* locally available\" to keep the promises set minimally\n>> populated. The only change needed to fsck in order to make it\n>> refrain from treating a missing but promised object as an error\n>> would be:\n>>\n>> - if (object is missing)\n>> + if (object is missing && object is not promised)\n>> error(\"that object must be there but missing\");\n>>\n>> so there is no point in throwing something that we know we locally\n>> have in this oidset, right?\n>>\n>> On the other hand, cost of such additional checks in this function\n>> may outweigh the savings of both memory pressure and look-up cost,\n>> so I do not know how the tradeoff would turn out.\n> \n> I also don't know how the tradeoff would turn out, so I leaned towards\n> the slightly simpler solution of not doing the check. In the future,\n> maybe a t/perf test can be done to decide between the two.\n> \n>>> +static int is_promise(const struct object_id *oid)\n>>> +{\n>>> +\tif (!promises_prepared) {\n>>> +\t\tif (repository_format_lazy_object)\n>>> +\t\t\tfor_each_packed_object(add_promise, NULL,\n>>> +\t\t\t\t\t FOR_EACH_OBJECT_IMPORTED_ONLY);\n>>> +\t\tpromises_prepared = 1;\n>>> +\t}\n>>> +\treturn oidset_contains(&promises, oid);\n>>> +}\n>>\n>> Somehow I'm tempted to call this function \"is_promised()\" but that\n>> is a minor naming issue.\n> \n\nGiven all we need is an existance check for a given oid, I wonder if it \nwould be faster overall to do a binary search through the list of \nimported idx files + an existence test for an imported loose object.\n\nEspecially in the check_connected case which isn't verifying every \nobject, that should be a lot less IO than loading all the imported \ncommits, trees and blobs and pre-computing an oidset of all possible \nobjects. The lookup for each object would be slower than a simple call \nto oidset_contains but we avoid the up front cost.\n\nWith some caching of idx files and threading, I suspect this could be \nmade pretty fast.\n\n> I was trying to be consistent in using the name \"promise\" instead of\n> \"promised object/tag/commit/tree/blob\" everywhere, but we can switch if\n> need be (for example, if we don't want to limit the generic name\n> \"promise\" to merely objects).\n> \n>>> static const char *describe_object(struct object *obj)\n>>> {\n>>> \tstatic struct strbuf buf = STRBUF_INIT;\n>>> @@ -410,7 +472,7 @@ static void fsck_handle_reflog_oid(const char *refname, struct object_id *oid,\n>>> \t\t\t\t\txstrfmt(\"%s@{%\"PRItime\"}\", refname, timestamp));\n>>> \t\t\tobj->used = 1;\n>>> \t\t\tmark_object_reachable(obj);\n>>> -\t\t} else {\n>>> +\t\t} else if (!is_promise(oid)) {\n>>> \t\t\terror(\"%s: invalid reflog entry %s\", refname, oid_to_hex(oid));\n>>> \t\t\terrors_found |= ERROR_REACHABLE;\n>>> \t\t}\n>>\n>> This is about certainly is one place we want to check if the missing\n>> object is OK, but I'm a bit surprised if this were the only place.\n>>\n>> Don't we need \"while trying to follow all the outgoing links from\n>> this tree object, and we found this object is not available locally;\n>> normally we would mark it as an error but it turns out that the\n>> missing one is in the promised set of objects, so it is OK\" for the\n>> normal connectivity traversal codepaths, for example?\n> \n> That's right. The places to make this change are the same as those in\n> some earlier patches I sent (patches 2-4 in [1]).\n> \n> [1] https://public-inbox.org/git/cover.1501532294.git.jonathantanmy@google.com/\n> \n"},{"id":"326649","messageId":"20170817143905.2ef872e6@twelve2.svl.corp.google.com","threadId":"46515","inReplyTo":"c6787a0b-ba7c-106a-66bd-5c2d38752ccb@gmail.com","subject":"Re: [RFC PATCH] Updated \"imported object\" design","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-08-17T21:39:05Z","receivedAt":"2017-08-17T21:39:13Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Thanks for your comments. I'll reply to both your e-mails in this one\ne-mail.\n\n> This illustrates another place we need to resolve the\n> naming/vocabulary. We should at least be consistent to make it easier\n> to discuss/explain. We obviously went with \"virtual\" when building\n> GVFS but I'm OK with \"lazy\" as long as we're consistent. Some\n> examples of how the naming can clarify or confuse:\n> \n> 'Promise-enable your repo by setting the \"extensions.lazyObject\" flag'\n> \n> 'Enable your repo to lazily fetch objects by setting the\n> \"extensions.lazyObject\"'\n> \n> 'Virtualize your repo by setting the \"extensions.virtualize\" flag'\n> \n> We may want to carry the same name into the filename we use to mark\n> the (virtualized/lazy/promised/imported) objects.\n> \n> (This reminds me that there are only 2 hard problems in computer\n> science...) ;)\n\nGood point about the name. Maybe the 2nd one is the best? (Mainly\nbecause I would expect a \"virtualized\" repo to have virtual refs too.)\n\nBut if there was a good way to refer to the \"anti-projection\" in a\nvirtualized system (that is, the \"real\" thing or \"object\" behind the\n\"virtual\" thing or \"image\"), then maybe the \"virtualized\" language is\nthe best. (And I would gladly change - I'm having a hard time coming up\nwith a name for the \"anti-projection\" in the \"lazy\" language.)\n\nAlso, I should probably standardize on \"lazily fetch\" instead of \"lazily\nload\". I didn't want to overlap with the existing fetching, but after\nsome thought, it's probably better to do that. The explanation would\nthus be that you can either use the built-in Git fetcher (to be built,\nalthough I have an old version here [1]) or supply a custom fetcher.\n\n[1] https://github.com/jonathantanmy/git/commits/partialclone\n\n> I think this all works and would meet the requirements we've been\n> discussing. The big trade off here vs what we first discussed with\n> promises is that we are generating the list of promises on the fly\n> when they are needed rather than downloading and maintaining a list\n> locally.\n> \n> My biggest concern with this model is the cost of opening and parsing\n> every imported object (loose and pack for local and alternates) to\n> build the oidset of promises.\n> \n> In fsck this probably won't be an issue as it already focuses on\n> correctness at the expense of speed. I'm more worried about when we\n> add the same/similar logic into check_connected. That impacts fetch,\n> clone, and receive_pack.\n> \n> I guess the only way we can know for sure it to do a perf test and\n> measure the impact.\n\nAs for fetching from the main repo, the connectivity check does not need\nto be performed at all because all objects are \"imported\", so the\nperformance of the connectivity check does not matter. Same for cloning.\n\nThis is not true if you're fetching from another repo or if you're using\nreceive-pack, but (1) I think these are not used as much in such a\nsituation, and (2) if you do use them, the slowness only \"kicks in\" if\nyou do not have the objects referred to (whether non-\"imported\" or\n\"imported\") and thus have to check the references in all \"imported\"\nobjects.\n\n> I think this topic should continue to move forward so that we can \n> provide reasonable connectivity tests for fsck and check_connected in \n> the face of partial clones. I'm not sure the prototype implementation \n> of reading/parsing all imported objects to build the promised oidset is \n> the most performant model but we can continue to investigate the best \n> options.\n\nAgreed - I think the most important thing here is settling on the API\n(name of extension and the nature of the object mark).\n\n> Given all we need is an existance check for a given oid,\n\nThis is true...\n\n> I wonder if it \n> would be faster overall to do a binary search through the list of \n> imported idx files + an existence test for an imported loose object.\n\n...but what we're checking is the existence of a reference, not the\nexistence of an object. For a concrete example, consider what happens if\nwe both have an \"imported\" tree and a non-\"imported\" tree that\nreferences a blob that we do not have. When checking the non-\"imported\"\ntree for connectivity, we have to iterate through all \"imported\" trees\nto see if any can vouch for the existence of such a blob. We cannot\nmerely binary-search the .idx file.\n"},{"id":"326690","messageId":"78139f5c-a044-9c00-11ff-eb91a70b6ab9@gmail.com","threadId":"46515","inReplyTo":"20170817143905.2ef872e6@twelve2.svl.corp.google.com","subject":"Re: [RFC PATCH] Updated \"imported object\" design","fromName":"Ben Peart","fromEmail":"peartben@gmail.com","sentAt":"2017-08-18T14:18:37Z","receivedAt":"2017-08-18T14:18:47Z","isPatch":true,"sender":{"key":"benpeart@microsoft.com","avatar":"https://avatars.githubusercontent.com/u/15252029?v=4"},"body":"\n\nOn 8/17/2017 5:39 PM, Jonathan Tan wrote:\n> Thanks for your comments. I'll reply to both your e-mails in this one\n> e-mail.\n> \n>> This illustrates another place we need to resolve the\n>> naming/vocabulary. We should at least be consistent to make it easier\n>> to discuss/explain. We obviously went with \"virtual\" when building\n>> GVFS but I'm OK with \"lazy\" as long as we're consistent. Some\n>> examples of how the naming can clarify or confuse:\n>>\n>> 'Promise-enable your repo by setting the \"extensions.lazyObject\" flag'\n>>\n>> 'Enable your repo to lazily fetch objects by setting the\n>> \"extensions.lazyObject\"'\n>>\n>> 'Virtualize your repo by setting the \"extensions.virtualize\" flag'\n>>\n>> We may want to carry the same name into the filename we use to mark\n>> the (virtualized/lazy/promised/imported) objects.\n>>\n>> (This reminds me that there are only 2 hard problems in computer\n>> science...) ;)\n> \n> Good point about the name. Maybe the 2nd one is the best? (Mainly\n> because I would expect a \"virtualized\" repo to have virtual refs too.)\n> \n> But if there was a good way to refer to the \"anti-projection\" in a\n> virtualized system (that is, the \"real\" thing or \"object\" behind the\n> \"virtual\" thing or \"image\"), then maybe the \"virtualized\" language is\n> the best. (And I would gladly change - I'm having a hard time coming up\n> with a name for the \"anti-projection\" in the \"lazy\" language.)\n> \n\nThe most common \"anti-virtual\" language I'm familiar with is \"physical.\" \n Virtual machine <-> physical machine. Virtual world <-> physical \nworld. Virtual repo, commit, tree, blob - physical repo, commit, tree, \nblob. I'm not thrilled but I think it works...\n\n> Also, I should probably standardize on \"lazily fetch\" instead of \"lazily\n> load\". I didn't want to overlap with the existing fetching, but after\n> some thought, it's probably better to do that. The explanation would\n> thus be that you can either use the built-in Git fetcher (to be built,\n> although I have an old version here [1]) or supply a custom fetcher.\n> \n> [1] https://github.com/jonathantanmy/git/commits/partialclone\n> \n>> I think this all works and would meet the requirements we've been\n>> discussing. The big trade off here vs what we first discussed with\n>> promises is that we are generating the list of promises on the fly\n>> when they are needed rather than downloading and maintaining a list\n>> locally.\n>>\n>> My biggest concern with this model is the cost of opening and parsing\n>> every imported object (loose and pack for local and alternates) to\n>> build the oidset of promises.\n>>\n>> In fsck this probably won't be an issue as it already focuses on\n>> correctness at the expense of speed. I'm more worried about when we\n>> add the same/similar logic into check_connected. That impacts fetch,\n>> clone, and receive_pack.\n>>\n>> I guess the only way we can know for sure it to do a perf test and\n>> measure the impact.\n> \n> As for fetching from the main repo, the connectivity check does not need\n> to be performed at all because all objects are \"imported\", so the\n> performance of the connectivity check does not matter. Same for cloning.\n> \n\nVery good point! I got stuck on connectivity check in general forgetting \nthat we really only need to prevent sharing a corrupt repo.\n\n> This is not true if you're fetching from another repo \n\nThis isn't a case we've explicitly dealt with (multiple remotes into a \nvirtualized repo). Our behavior today would be that once you set the \n\"virtual repo\" flag on the repo (this happens at clone for us), all \nremotes are treated as virtual as well (ie we don't differentiate \nbehavior based on which remote was used). Our \"custom fetcher\" always \nuses \"origin\" and some custom settings for a cache-server saved in the \n.git/config file when asked to fetch missing objects.\n\nThis is probably a good model to stick with at least initially as trying \nto solve multiple possible \"virtual\" remotes as well as mingling \nvirtualized and non-virtualized remotes and all the mixed cases that can \ncome up makes my head hurt. We should probably address that in a \ndifferent thread. :)\n\n> or if you're using\n> receive-pack, but (1) I think these are not used as much in such a\n> situation, and (2) if you do use them, the slowness only \"kicks in\" if\n> you do not have the objects referred to (whether non-\"imported\" or\n> \"imported\") and thus have to check the references in all \"imported\"\n> objects.\n> \n\nIs there any case where receive-pack is used on the client side? I'm \nonly aware of it being used on the server side to receive packs pushed \nfrom the client. If it is not used in a virtualized client, then we \nwould not need to do anything different for receive-pack.\n\n>> I think this topic should continue to move forward so that we can\n>> provide reasonable connectivity tests for fsck and check_connected in\n>> the face of partial clones. I'm not sure the prototype implementation\n>> of reading/parsing all imported objects to build the promised oidset is\n>> the most performant model but we can continue to investigate the best\n>> options.\n> \n> Agreed - I think the most important thing here is settling on the API\n> (name of extension and the nature of the object mark).\n> \n>> Given all we need is an existance check for a given oid,\n> \n> This is true...\n> \n>> I wonder if it\n>> would be faster overall to do a binary search through the list of\n>> imported idx files + an existence test for an imported loose object.\n> \n> ...but what we're checking is the existence of a reference, not the\n> existence of an object. For a concrete example, consider what happens if\n> we both have an \"imported\" tree and a non-\"imported\" tree that\n> references a blob that we do not have. When checking the non-\"imported\"\n> tree for connectivity, we have to iterate through all \"imported\" trees\n> to see if any can vouch for the existence of such a blob. We cannot\n> merely binary-search the .idx file.\n> \n\nThat is another good point. Given the discussion above about not \nneeding to do the connectivity test for fetch/clone - the potential perf \nhit of loading/parsing all the various objects to build up the oidset is \nmuch less of an issue.\n\n"},{"id":"326752","messageId":"20170818163311.3bef1da7@twelve2.svl.corp.google.com","threadId":"46515","inReplyTo":"78139f5c-a044-9c00-11ff-eb91a70b6ab9@gmail.com","subject":"Re: [RFC PATCH] Updated \"imported object\" design","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-08-18T23:33:11Z","receivedAt":"2017-08-18T23:33:20Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Fri, 18 Aug 2017 10:18:37 -0400\nBen Peart wrote:\n\n> > But if there was a good way to refer to the \"anti-projection\" in a\n> > virtualized system (that is, the \"real\" thing or \"object\" behind the\n> > \"virtual\" thing or \"image\"), then maybe the \"virtualized\" language is\n> > the best. (And I would gladly change - I'm having a hard time coming up\n> > with a name for the \"anti-projection\" in the \"lazy\" language.)\n> > \n> \n> The most common \"anti-virtual\" language I'm familiar with is \"physical.\" \n> Virtual machine <-> physical machine. Virtual world <-> physical \n> world. Virtual repo, commit, tree, blob - physical repo, commit, tree, \n> blob. I'm not thrilled but I think it works...\n\nI was thinking more along the lines of the \"entity that projects the\nvirtualization\", not the opposite of a \"virtualization\" - \"physical\"\nmight work for the latter but probably not the former.\n\nAfter some in-office discussion, if we stick to the \"promise\" concept,\nmaybe we have something like this:\n\n In a partial clone, the origin acts as a promisor of objects. Every\n object obtained from the promisor also acts as a promise that any\n object directly or indirectly referenced from that object is fetchable\n from the promisor.\n\n> > This is not true if you're fetching from another repo \n> \n> This isn't a case we've explicitly dealt with (multiple remotes into a \n> virtualized repo). Our behavior today would be that once you set the \n> \"virtual repo\" flag on the repo (this happens at clone for us), all \n> remotes are treated as virtual as well (ie we don't differentiate \n> behavior based on which remote was used). Our \"custom fetcher\" always \n> uses \"origin\" and some custom settings for a cache-server saved in the \n> .git/config file when asked to fetch missing objects.\n> \n> This is probably a good model to stick with at least initially as trying \n> to solve multiple possible \"virtual\" remotes as well as mingling \n> virtualized and non-virtualized remotes and all the mixed cases that can \n> come up makes my head hurt. We should probably address that in a \n> different thread. :)\n\nOK, let's stick to the current model first then, whether our opinion on\nother remotes is (1) \"we won't have any other remotes so we don't care\",\n(2) \"we have other remotes but it's fine to make sure that they don't\nintroduce any new missing objects\", or (3) \"we need other remotes to\nintroduce missing objects, but we can build that after this foundation\nis laid\".\n\n> > or if you're using\n> > receive-pack, but (1) I think these are not used as much in such a\n> > situation, and (2) if you do use them, the slowness only \"kicks in\" if\n> > you do not have the objects referred to (whether non-\"imported\" or\n> > \"imported\") and thus have to check the references in all \"imported\"\n> > objects.\n> > \n> \n> Is there any case where receive-pack is used on the client side? I'm \n> only aware of it being used on the server side to receive packs pushed \n> from the client. If it is not used in a virtualized client, then we \n> would not need to do anything different for receive-pack.\n\nThis happens if another repo decides to push to the virtualized client,\nwhich (as I wrote) I don't expect to happen often. My intention is to\nensure that receive-pack will still work.\n\n> That is another good point. Given the discussion above about not \n> needing to do the connectivity test for fetch/clone - the potential perf \n> hit of loading/parsing all the various objects to build up the oidset is \n> much less of an issue.\n\nAgreed.\n"}]}