{"thread":{"id":"44363","subject":"[RFH] limiting ref advertisements","startedAt":"2016-10-24T13:29:49Z","lastAt":"2016-11-16T13:42:49Z","messageCount":4,"participants":["Jeff King","Duy Nguyen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"304773","messageId":"20161024132932.i42rqn2vlpocqmkq@sigill.intra.peff.net","threadId":"44363","inReplyTo":null,"subject":"[RFH] limiting ref advertisements","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-10-24T13:29:33Z","receivedAt":"2016-10-24T13:29:49Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I'm looking into the oft-discussed idea of reducing the size of ref\nadvertisements by having the client say \"these are the refs I'm\ninterested in\". Let's set aside the protocol complexities for a\nmoment and imagine we magically have some way to communicate a set of\npatterns to the server.\n\nWhat should those patterns look like?\n\nI had hoped that we could keep most of the pattern logic on the\nclient-side. Otherwise we risk incompatibilities between how the client\nand server interpret a pattern. I had also hoped we could do some kind\nof prefix-matching, which would let the server look only at the\ninteresting bits of the ref tree (so if you don't care about\nrefs/changes, and the server has some ref storage that is hierarchical,\nthey can literally get away without opening that sub-tree).\n\nThe patch at the end of this email is what I came up with in that\ndirection. It obviously won't compile without the twenty other patches\nimplementing transport->advertise_prefixes, but it gives you a sense of\nwhat I'm talking about.\n\nUnfortunately it doesn't work in all cases, because refspec sources may\nbe unqualified. If I ask for:\n\n  git fetch $remote master:foo\n\nthen we have to actually dwim-resolve \"master\" from the complete list of\nrefs we get from the remote.  It could be \"refs/heads/master\",\n\"refs/tags/master\", etc. Worse, it could be \"refs/master\". In that case,\nat least, I think we are OK because we avoid advertising refs directly\nbelow \"refs/\" in the first place. But if you have a slash, like:\n\n  git fetch $remote jk/foo\n\nthen that _could_ be \"refs/jk/foo\". Likewise, we cannot even optimize\nthe common case of a fully-qualified ref, like \"refs/heads/foo\". If it\nexists, we obviously want to use that. But if it doesn't, then it\ncould be refs/something-else/refs/heads/foo. That's unlikely, but it\n_does_ work now, and optimizing the advertisement would break it.\n\nSo it seems like left-anchoring the refspecs can never be fully correct.\nWe can communicate \"master\" to the server, who can then look at every\nref it would advertise and ask \"could this be called master\"? But it\nwill be setting in stone the set of \"could this be\" patterns. Granted,\nthose haven't changed much over the history of git, but it seems awfully\nfragile.\n\nIn an ideal world the client and server would negotiate to come to some\nagreement on the patterns being used. But as we are bolting this onto\nthe existing protocol, I was really trying to do it without introducing\nan extra capabilities phase or extra round-trips. I.e., something like\nDavid Turner's \"stick the refspec in the HTTP query parameters\" trick,\nbut working everywhere[1].\n\nClever ideas?\n\n-Peff\n\n[1] I do have working patches to pass these \"early capabilities\"\n    everywhere, but they're still somewhat rough. I got it to the point\n    where I could flip the default to \"on\" to see what breaks. That's\n    not something we'd want to do for real, but is good for running the\n    test suite to uncover issues like this one.\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 7c10d70092..3a2585ffd7 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -302,6 +302,33 @@ static void find_non_local_tags(struct transport *transport,\n \tstring_list_clear(&remote_refs, 0);\n }\n \n+static void add_advertise_prefixes(struct transport *transport,\n+\t\t\t\t   const struct refspec *refs, int nr)\n+{\n+\tstruct argv_array *list = &transport->advertise_prefixes;\n+\tint i;\n+\n+\tfor (i = 0; i < nr; i++) {\n+\t\tconst struct refspec *rs = &refs[i];\n+\t\tsize_t len;\n+\n+\t\tif (!rs->pattern)\n+\t\t\targv_array_push(list, rs->src);\n+\t\telse if (strip_suffix(rs->src, \"/*\", &len))\n+\t\t\targv_array_pushf(list, \"%.*s\", (int)len, rs->src);\n+\t\telse {\n+\t\t\t/*\n+\t\t\t * This refspec is too complex for us to communicate;\n+\t\t\t * not only do we skip it, but we must avoid\n+\t\t\t * communicating any prefixes, since we need to see\n+\t\t\t * all refs.\n+\t\t\t */\n+\t\t\ttransport->ignore_advertise_prefixes = 1;\n+\t\t\treturn;\n+\t\t}\n+\t}\n+}\n+\n static struct ref *get_ref_map(struct transport *transport,\n \t\t\t       struct refspec *refspecs, int refspec_count,\n \t\t\t       int tags, int *autotags)\n@@ -314,12 +341,18 @@ static struct ref *get_ref_map(struct transport *transport,\n \t/* opportunistically-updated references: */\n \tstruct ref *orefs = NULL, **oref_tail = &orefs;\n \n-\tconst struct ref *remote_refs = transport_get_remote_refs(transport);\n+\tconst struct ref *remote_refs;\n+\n+\tif (tags == TAGS_SET || (tags == TAGS_DEFAULT && *autotags))\n+\t\tadd_advertise_prefixes(transport, tag_refspec, 1);\n \n \tif (refspec_count) {\n \t\tstruct refspec *fetch_refspec;\n \t\tint fetch_refspec_nr;\n \n+\t\tadd_advertise_prefixes(transport, refspecs, refspec_count);\n+\t\tremote_refs = transport_get_remote_refs(transport);\n+\n \t\tfor (i = 0; i < refspec_count; i++) {\n \t\t\tget_fetch_map(remote_refs, &refspecs[i], &tail, 0);\n \t\t\tif (refspecs[i].dst && refspecs[i].dst[0])\n@@ -373,6 +406,17 @@ static struct ref *get_ref_map(struct transport *transport,\n \t\t    (remote->fetch_refspec_nr ||\n \t\t     /* Note: has_merge implies non-NULL branch->remote_name */\n \t\t     (has_merge && !strcmp(branch->remote_name, remote->name)))) {\n+\n+\t\t\tadd_advertise_prefixes(transport, remote->fetch,\n+\t\t\t\t\t       remote->fetch_refspec_nr);\n+\t\t\tif (has_merge && !strcmp(branch->remote_name, remote->name)) {\n+\t\t\t\tint i;\n+\t\t\t\tfor (i = 0; i < branch->merge_nr; i++)\n+\t\t\t\t\tadd_advertise_prefixes(transport, branch->merge[i], 1);\n+\t\t\t}\n+\n+\t\t\tremote_refs = transport_get_remote_refs(transport);\n+\n \t\t\tfor (i = 0; i < remote->fetch_refspec_nr; i++) {\n \t\t\t\tget_fetch_map(remote_refs, &remote->fetch[i], &tail, 0);\n \t\t\t\tif (remote->fetch[i].dst &&\n@@ -393,6 +437,8 @@ static struct ref *get_ref_map(struct transport *transport,\n \t\t\t    !strcmp(branch->remote_name, remote->name))\n \t\t\t\tadd_merge_config(&ref_map, remote_refs, branch, &tail);\n \t\t} else {\n+\t\t\targv_array_push(&transport->advertise_prefixes, \"HEAD\");\n+\t\t\tremote_refs = transport_get_remote_refs(transport);\n \t\t\tref_map = get_remote_ref(remote_refs, \"HEAD\");\n \t\t\tif (!ref_map)\n \t\t\t\tdie(_(\"Couldn't find remote ref HEAD\"));\n"},{"id":"304837","messageId":"CACsJy8DwKxz14Dow9dEKeXnBriMzN_OptnGM7nPigPcS_pHX9w@mail.gmail.com","threadId":"44363","inReplyTo":"20161024132932.i42rqn2vlpocqmkq@sigill.intra.peff.net","subject":"Re: [RFH] limiting ref advertisements","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-10-25T11:46:21Z","receivedAt":"2016-10-25T11:46:57Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Oct 24, 2016 at 8:29 PM, Jeff King <peff@peff.net> wrote:\n> I'm looking into the oft-discussed idea of reducing the size of ref\n> advertisements by having the client say \"these are the refs I'm\n> interested in\". Let's set aside the protocol complexities for a\n> moment and imagine we magically have some way to communicate a set of\n> patterns to the server.\n>\n> What should those patterns look like?\n>\n> I had hoped that we could keep most of the pattern logic on the\n> client-side. Otherwise we risk incompatibilities between how the client\n> and server interpret a pattern. I had also hoped we could do some kind\n> of prefix-matching, which would let the server look only at the\n> interesting bits of the ref tree (so if you don't care about\n> refs/changes, and the server has some ref storage that is hierarchical,\n> they can literally get away without opening that sub-tree).\n>\n> The patch at the end of this email is what I came up with in that\n> direction. It obviously won't compile without the twenty other patches\n> implementing transport->advertise_prefixes\n\nYes! git-upload-pack-2 is making a come back, one form or another.\n\n> but it gives you a sense of what I'm talking about.\n>\n> Unfortunately it doesn't work in all cases, because refspec sources may\n> be unqualified. If I ask for:\n>\n>   git fetch $remote master:foo\n>\n> then we have to actually dwim-resolve \"master\" from the complete list of\n> refs we get from the remote.  It could be \"refs/heads/master\",\n> \"refs/tags/master\", etc. Worse, it could be \"refs/master\". In that case,\n> at least, I think we are OK because we avoid advertising refs directly\n> below \"refs/\" in the first place. But if you have a slash, like:\n>\n>   git fetch $remote jk/foo\n>\n> then that _could_ be \"refs/jk/foo\". Likewise, we cannot even optimize\n> the common case of a fully-qualified ref, like \"refs/heads/foo\". If it\n> exists, we obviously want to use that. But if it doesn't, then it\n> could be refs/something-else/refs/heads/foo. That's unlikely, but it\n> _does_ work now, and optimizing the advertisement would break it.\n>\n> So it seems like left-anchoring the refspecs can never be fully correct.\n> We can communicate \"master\" to the server, who can then look at every\n> ref it would advertise and ask \"could this be called master\"? But it\n> will be setting in stone the set of \"could this be\" patterns. Granted,\n> those haven't changed much over the history of git, but it seems awfully\n> fragile.\n\nThe first thought that comes to mind is, if left anchoring does not\nwork, let's support both left and right anchoring. I guess you\nconsidered and discarded this.\n\nIf prefix matching does not work, and assuming \"some-prefix\" sent by\nclient to be in fact \"**/some-prefix\" pattern at server side will set\nthe \"could this be\" in stone, how about use wildmatch? It's flexible\nenough and we have full control over the pattern matching engine so C\nGit <-> C Git should be good regardless of platforms. I understand\nthat wildmatch is still complicated enough that a re-implementation\ncan easily divert in behavior. But a pattern with only '*', '/**',\n'/**/' and '**/' wildcards (in other words, no [] or ?) could make the\nengine a lot simpler and still fit our needs (and give some room for\nclient-optimization).\n\n> In an ideal world the client and server would negotiate to come to some\n> agreement on the patterns being used. But as we are bolting this onto\n> the existing protocol, I was really trying to do it without introducing\n> an extra capabilities phase or extra round-trips. I.e., something like\n> David Turner's \"stick the refspec in the HTTP query parameters\" trick,\n> but working everywhere[1].\n-- \nDuy\n"},{"id":"305921","messageId":"20161114212122.rkgeoh4rj5cxdadf@sigill.intra.peff.net","threadId":"44363","inReplyTo":"CACsJy8DwKxz14Dow9dEKeXnBriMzN_OptnGM7nPigPcS_pHX9w@mail.gmail.com","subject":"Re: [RFH] limiting ref advertisements","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-11-14T21:21:23Z","receivedAt":"2016-11-14T21:21:32Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 25, 2016 at 06:46:21PM +0700, Duy Nguyen wrote:\n\n> > So it seems like left-anchoring the refspecs can never be fully correct.\n> > We can communicate \"master\" to the server, who can then look at every\n> > ref it would advertise and ask \"could this be called master\"? But it\n> > will be setting in stone the set of \"could this be\" patterns. Granted,\n> > those haven't changed much over the history of git, but it seems awfully\n> > fragile.\n> \n> The first thought that comes to mind is, if left anchoring does not\n> work, let's support both left and right anchoring. I guess you\n> considered and discarded this.\n> \n> If prefix matching does not work, and assuming \"some-prefix\" sent by\n> client to be in fact \"**/some-prefix\" pattern at server side will set\n> the \"could this be\" in stone, how about use wildmatch? It's flexible\n> enough and we have full control over the pattern matching engine so C\n> Git <-> C Git should be good regardless of platforms. I understand\n> that wildmatch is still complicated enough that a re-implementation\n> can easily divert in behavior. But a pattern with only '*', '/**',\n> '/**/' and '**/' wildcards (in other words, no [] or ?) could make the\n> engine a lot simpler and still fit our needs (and give some room for\n> client-optimization).\n\nThanks for responding to this. I've been meaning to get back to it with\nsome code experiments, but they keep getting bumped down in priority. So\nlet me at least outline some of my thoughts, without code. :)\n\nI was hoping to avoid right-anchoring because it's expensive to find all\nof the right-anchored cases (assuming that ref storage is generally\nhierarchical, which it is now and probably will be for future backends).\n\nI also don't think it covers all cases. As bizarre as it is, I believe\nyou can currently do:\n\n  git fetch $remote origin\n\nand find refs/remotes/origin/HEAD.\n\nSo I think the best we can ever do is have the server look at a specific\nset of patterns. Those patterns could be expressed by wildmatch. I was\njust a little nervous to turn to wildmatch, because it's complicated and\nwe may want to update it in the future in a slightly-incompatible way.\n\nWe also want to give some preference-order to the patterns. If I give\nyou \"refs/heads/master\", and that ref exists, you do not need to tell me\nwhether you also have \"refs/heads/refs/heads/master\". So you have to\nprovide multiple patterns for each possible ref. And you need to group\nthem as \"show the first one that matches from this group\".\n\nThe pattern the client is using really is the ref_rev_parse_rules. So I\nthink the solution is more like one of:\n\n  1. Specify the pattern set ahead of time, and then the server applies\n     it to each refname. We need some pattern language that can express\n     \"fill in the thing in the middle\". IOW, something like:\n\n       advertise-pattern=%s\n       advertise-pattern=refs/tags/%s\n       advertise-pattern=refs/heads/%s\n       advertise-lookup=master\n       advertise-lookup=v1.0\n\n     except that the thought of using snprintf() to handle formats\n     provided by the user is vaguely terrifying. We could make sure they\n     contain only a single \"%s\", but given the history there, it still\n     makes me nervous. I guess we could write our own pseudo-%s parser\n     that is much more careful and complains on bugs instead of\n     executing arbitrary code. ;)\n\n     I don't think wildmatch quite works for that, because it wants to\n     have the full pattern.\n\n  2. Declare the current set of ref_rev_parse_rules as \"version 1\", and\n     send:\n\n       advertise-lookup-v1=master\n       advertise-lookup-v1=v1.0\n\n     and the server would do the right thing. We could do a v2, but it\n     gets hairy. Let's imagine we add \"refs/notes/%s\" to the lookup\n     rules, and we'll call that v2.\n\n     But remember that these are \"early capabilities\", before the server\n     has spoken at all. So the client doesn't know if we can handle v2.\n     So we have to send _both_ (and v2-aware servers can ignore the v1).\n\n       advertise-lookup-v1=master\n       advertise-lookup-v2=master\n\n     But that's not quite enough. A v1 server won't look in refs/notes\n     at all. So we have to say that, too:\n\n       advertise-lookup-v1=refs/notes/master\n\n     And of course the v1 server has no idea that this isn't necessary\n     if we already found refs/heads/master.\n\n     So I think you really do need the client to be able to say \"also\n     look at this pattern\".\n\nOf course we do still want left-anchoring, too. Wildcards like\n\"refs/heads/*\" are always left-anchored. So I think we'd have two types,\nand a full request for\n\n  git fetch origin +refs/heads/*:refs/remotes/origin/* master:foo\n\nwould look like:\n\n  (1) advertise-pattern-v1\n  (2) advertise-pattern=refs/notes/%s\n  (3) advertise-prefix=refs/heads\n  (4) advertise-lookup=master\n\nwhere the lines mean:\n\n  1. Use the standard v1 patterns (we could spell them out, but this\n     just saves bandwidth. In fact, it could just be implicit that v1\n     patterns are included, and we could skip this line).\n\n  2. This is for our fictional future version where the client knows\n     added refs/notes/* to its DWIM but the server hasn't yet.\n\n  3. Give me all of refs/heads/*\n\n  4. Look up \"master\" using the advertise patterns and give me the first\n     one you find.\n\nSo given that we can omit (1), and that (2) is just an example for the\nfuture, it could look like:\n\n  advertise-prefix=refs/heads\n  advertise-lookup=master\n\nwhich is pretty reasonable. It's not _completely_ bulletproof in terms\nof backwards compatibility. The \"v1\" thing means the client can't insert\na new pattern in the middle (remember they're ordered by priority). So\nmaybe it is better to spell them all out (one thing that makes me\nhesitate is that these will probably end up as URL parameters for the\nHTTP version, which means our URL can start to get a little long).\n\nAnyway. That's the direction I'm thinking. I haven't written the code\nyet. The trickiest thing will probably be that the server would want to\navoid advertising the same ref twice via two mechanisms (or perhaps the\nclient just be tolerant of duplicates; that relieves the server of any\nduplicate-storage requirements).\n\n-Peff\n"},{"id":"306045","messageId":"CACsJy8APSV_ONDjYDU0PHogpHg3cPULuWUySESqiXA2Eic+0wg@mail.gmail.com","threadId":"44363","inReplyTo":"20161114212122.rkgeoh4rj5cxdadf@sigill.intra.peff.net","subject":"Re: [RFH] limiting ref advertisements","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-11-16T13:42:01Z","receivedAt":"2016-11-16T13:42:49Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Nov 15, 2016 at 4:21 AM, Jeff King <peff@peff.net> wrote:\n> Thanks for responding to this.\n\nGlad to help (or more precisely annoy you somewhat :D)\n\n> I've been meaning to get back to it with\n> some code experiments, but they keep getting bumped down in priority. So\n> let me at least outline some of my thoughts, without code. :)\n>\n> I was hoping to avoid right-anchoring because it's expensive to find all\n> of the right-anchored cases (assuming that ref storage is generally\n> hierarchical, which it is now and probably will be for future backends).\n\nUrgh.. I completely forgot about future refs backends. Yeah this would\nkick both wildmatch and right-anchoring out of the window.\n\nFor the record I almost suggested BPF as well (to keep the server side\nsimple, but at the super high cost of client side). That would also go\nout of the window the same way wildmatch and right-anchoring does.\n\n>      But remember that these are \"early capabilities\", before the server\n>      has spoken at all. So the client doesn't know if we can handle v2.\n>      So we have to send _both_ (and v2-aware servers can ignore the v1).\n>\n>        advertise-lookup-v1=master\n>        advertise-lookup-v2=master\n>\n>      But that's not quite enough. A v1 server won't look in refs/notes\n>      at all. So we have to say that, too:\n>\n>        advertise-lookup-v1=refs/notes/master\n>\n>      And of course the v1 server has no idea that this isn't necessary\n>      if we already found refs/heads/master.\n\nWe discussed a bit about upgrading upload-pack version 1 to 2 in more\nthan one session: the first fetch just does v1 as normal, the server\nreturns v1 response to but also advertises that v2 is supported. The\nclient keeps this info and skips v1 and tries v2 right away in the\nfollowing fetches, falling back to v1 (new fetch session) if v2 is\nunsupported. Can it work the same way here too?\n\nI'm in favor of this option 2 (without trying to be absolute backward\ncompatible with older lookup versions) since it allows us to optimize\nfor common case and experiment a bit. Once we know better we can make\nthe next version that hopefully suits everybody.\n\n>      So I think you really do need the client to be able to say \"also\n>      look at this pattern\".\n\nWhat about the order of patterns? Does it matter \"this pattern\" is in\nthe middle or the end of the pattern list? I suppose not, just\nchecking...\n\nBut does this call for the ability to remove a pattern from the\npattern list as well, as a way to narrow down the search scope and\navoid sending unwanted refs?\n\n> Of course we do still want left-anchoring, too. Wildcards like\n> \"refs/heads/*\" are always left-anchored. So I think we'd have two types,\n> and a full request for\n>\n>   git fetch origin +refs/heads/*:refs/remotes/origin/* master:foo\n>\n> would look like:\n>\n>   (1) advertise-pattern-v1\n>   (2) advertise-pattern=refs/notes/%s\n>   (3) advertise-prefix=refs/heads\n>   (4) advertise-lookup=master\n>\n> where the lines mean:\n>\n>   1. Use the standard v1 patterns (we could spell them out, but this\n>      just saves bandwidth. In fact, it could just be implicit that v1\n>      patterns are included, and we could skip this line).\n>\n>   2. This is for our fictional future version where the client knows\n>      added refs/notes/* to its DWIM but the server hasn't yet.\n>\n>   3. Give me all of refs/heads/*\n>\n>   4. Look up \"master\" using the advertise patterns and give me the first\n>      one you find.\n\nWell.. it sounds good to me. But I would not trust myself on refs matters :D\n\n> So given that we can omit (1), and that (2) is just an example for the\n> future, it could look like:\n>\n>   advertise-prefix=refs/heads\n>   advertise-lookup=master\n>\n> which is pretty reasonable. It's not _completely_ bulletproof in terms\n> of backwards compatibility. The \"v1\" thing means the client can't insert\n> a new pattern in the middle (remember they're ordered by priority).\n\nOK so pattern order probably matters...\n\n> So\n> maybe it is better to spell them all out (one thing that makes me\n> hesitate is that these will probably end up as URL parameters for the\n> HTTP version, which means our URL can start to get a little long).\n>\n> Anyway. That's the direction I'm thinking. I haven't written the code\n> yet. The trickiest thing will probably be that the server would want to\n> avoid advertising the same ref twice via two mechanisms (or perhaps the\n> client just be tolerant of duplicates; that relieves the server of any\n> duplicate-storage requirements).\n\nThanks for sharing.\n-- \nDuy\n"}]}