{"thread":{"id":"54858","subject":"Documentation errors for HTTP protocol v2 and packfile","startedAt":"2020-12-19T17:09:12Z","lastAt":"2020-12-29T22:44:57Z","messageCount":8,"participants":["Ross Light","Martin Ågren","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"412650","messageId":"CAEs=z9Pajgjnq56+umA+g9-NFv-Rzo9m5sa-7cow_byckLiJ0A@mail.gmail.com","threadId":"54858","inReplyTo":null,"subject":"Documentation errors for HTTP protocol v2 and packfile","fromName":"Ross Light","fromEmail":"ross@zombiezen.com","sentAt":"2020-12-19T17:07:35Z","receivedAt":"2020-12-19T17:09:12Z","isPatch":false,"sender":{"key":"ross@zombiezen.com","avatar":null},"body":"Hello Git mailing list,\n\nI'm working on a library to interoperate with the Git wire protocol.\nWhile doing so, I noticed two omissions in the documentation:\n\n1. In the protocol-v2 doc [1], the HTTP example implies that the first\nbytes in the response are \"000eversion 2\\n\" when in fact they will be\nPKT-LINE(\"# service=git-upload-pack\" LF) followed by a flush packet,\nthen the version 2 data.\n\n2. In the pack-format doc, the Deltified representation section [2]\ndescribes the instruction sequence well, but neglects to mention the\ntwo size varints [3] at the beginning of such an object.\n\nI think it would be good to correct these documents for others\nattempting to work with Git internals. Let me know how I can help.\n\n-Ross Light\n\n[1]: https://github.com/git/git/blob/ae46588be0cd730430dded4491246dfb4eac5557/Documentation/technical/protocol-v2.txt#L72-L79\n[2]: https://github.com/git/git/blob/ae46588be0cd730430dded4491246dfb4eac5557/Documentation/technical/pack-format.txt#L70-L76\n[3]: https://github.com/git/git/blob/ae46588be0cd730430dded4491246dfb4eac5557/patch-delta.c#L29-L36\n"},{"id":"412707","messageId":"42c6206b102cd97290fd9ad207bb39b20660064c.1608537234.git.martin.agren@gmail.com","threadId":"54858","inReplyTo":"cover.1608537234.git.martin.agren@gmail.com","subject":"[PATCH 1/2] pack-format.txt: define \"varint\" format","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2020-12-21T07:54:58Z","receivedAt":"2020-12-21T07:56:21Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"We define our varint format pretty much on the fly as we describe a pack\nfile entry. In preparation for referring to it in more places in this\ndocument, define \"varint\" and refer to it.\n\nSigned-off-by: Martin Ågren \n---\n Documentation/technical/pack-format.txt | 17 +++++++++++++----\n 1 file changed, 13 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex f96b2e605f..42198de74c 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -55,6 +55,15 @@ Valid object types are:\n \n Type 5 is reserved for future expansion. Type 0 is invalid.\n \n+=== Variable-length integer encoding\n+\n+This document uses \"varint\" encoding of non-negative integers: From\n+each byte, the seven least significant bits are used to form the\n+resulting integer. As long as the most significant bit is 1, this\n+process continues; the byte with MSB 0 provides the last seven bits.\n+The seven-bit chunks are concatenated. Later values are more\n+significant.\n+\n === Deltified representation\n \n Conceptually there are only four object types: commit, tree, tag and\n@@ -196,10 +205,10 @@ Pack file entry: <+\n \t1-byte size extension bit (MSB)\n \t type (next 3 bit)\n \t size0 (lower 4-bit)\n- n-byte sizeN (as long as MSB is set, each 7-bit)\n-\t\tsize0..sizeN form 4+7+7+..+7 bit integer, size0\n-\t\tis the least significant part, and sizeN is the\n-\t\tmost significant part.\n+ n-byte size1 (varint encoding; present if MSB is set)\n+ If the MSB is set, the size is size0 + 16*size1, otherwise\n+ it is size0. (Equivalently, the entire packed object header\n+ is a varint encoding of (size/16)*128 + type*16 + size%16.)\n packed object data:\n If it is not DELTA, then deflated bytes (the size above\n \t\tis the size before compression).\n-- \n2.30.0.rc1\n\n"},{"id":"412708","messageId":"cover.1608537234.git.martin.agren@gmail.com","threadId":"54858","inReplyTo":"CAEs=z9Pajgjnq56+umA+g9-NFv-Rzo9m5sa-7cow_byckLiJ0A@mail.gmail.com","subject":"[PATCH 0/2] pack-format.txt: document lengths at start of delta data","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2020-12-21T07:54:57Z","receivedAt":"2020-12-21T07:56:21Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"Hi Ross,\n\nWelcome to the list and thanks for reporting your findings. I haven't\nlooked at all at the first issue you brought up, about the protocol-v2\ndoc.\n\nOn Sat, 19 Dec 2020 at 18:10, Ross Light wrote:\n> 2. In the pack-format doc, the Deltified representation section [2]\n> describes the instruction sequence well, but neglects to mention the\n> two size varints [3] at the beginning of such an object.\n\nWould something like this be what you have in mind?\n\nMartin Ågren (2):\n pack-format.txt: define \"varint\" format\n pack-format.txt: document lengths at start of delta data\n\n Documentation/technical/pack-format.txt | 22 +++++++++++++++++-----\n 1 file changed, 17 insertions(+), 5 deletions(-)\n\n-- \n2.30.0.rc1\n\n"},{"id":"412709","messageId":"c515a44179576db202c8b6d2419459df0e67ec0a.1608537234.git.martin.agren@gmail.com","threadId":"54858","inReplyTo":"cover.1608537234.git.martin.agren@gmail.com","subject":"[PATCH 2/2] pack-format.txt: document lengths at start of delta data","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2020-12-21T07:54:59Z","receivedAt":"2020-12-21T07:56:21Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"We document the delta data as a set of instructions, but forget to\ndocument the two lengths that precede those instructions: the length of\nthe base object and the length of the object to be reconstructed. Fix\nthis omission.\n\nReported-by: Ross Light \nSigned-off-by: Martin Ågren \n---\n Documentation/technical/pack-format.txt | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex 42198de74c..05889a2e43 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -82,7 +82,10 @@ Ref-delta can also refer to an object outside the pack (i.e. the\n so-called \"thin pack\"). When stored on disk however, the pack should\n be self contained to avoid cyclic dependency.\n \n-The delta data is a sequence of instructions to reconstruct an object\n+The delta data starts with the length of the base object and the\n+length of the object to be reconstructed. These lengths are\n+encoded as varints. The remainder of\n+the delta data is a sequence of instructions to reconstruct the object\n from the base object. If the base object is deltified, it must be\n converted to canonical form first. Each instruction appends more and\n more data to the target object until it's complete. There are two\n-- \n2.30.0.rc1\n\n"},{"id":"412779","messageId":"xmqqft3yltxo.fsf@gitster.c.googlers.com","threadId":"54858","inReplyTo":"42c6206b102cd97290fd9ad207bb39b20660064c.1608537234.git.martin.agren@gmail.com","subject":"Re: [PATCH 1/2] pack-format.txt: define \"varint\" format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-12-21T21:40:03Z","receivedAt":"2020-12-21T21:40:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Ågren writes:\n\n> We define our varint format pretty much on the fly as we describe a pack\n> file entry. In preparation for referring to it in more places in this\n> document, define \"varint\" and refer to it.\n>\n> Signed-off-by: Martin Ågren \n> ---\n> Documentation/technical/pack-format.txt | 17 +++++++++++++----\n> 1 file changed, 13 insertions(+), 4 deletions(-)\n>\n> diff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\n> index f96b2e605f..42198de74c 100644\n> --- a/Documentation/technical/pack-format.txt\n> +++ b/Documentation/technical/pack-format.txt\n> @@ -55,6 +55,15 @@ Valid object types are:\n> \n> Type 5 is reserved for future expansion. Type 0 is invalid.\n> \n> +=== Variable-length integer encoding\n> +\n> +This document uses \"varint\" encoding of non-negative integers: From\n> +each byte, the seven least significant bits are used to form the\n> +resulting integer. As long as the most significant bit is 1, this\n> +process continues; the byte with MSB 0 provides the last seven bits.\n> +The seven-bit chunks are concatenated. Later values are more\n> +significant.\n> +\n\nUnfortunately we have two kinds of varint, and the above describes\nthe older and less efficient variant that is used to encode\n\n (1) the size of the base object and the object that would result\n by applying a delta (stored at the beginning of each datum that\n represents a deltified object, and read by get_delta_hdr_size())\n\n (2) the size of the object that is represented in the base\n representation and read by unpack_object_header())\n\n(and nothing else as far as I know).\n\nThere is another varint encoding that is slightly more efficient and\nit also is used in the packfile format to encode the OFS_DELTA\noffset, i.e. the number of bytes to go back in the same packfile\nstarting at the beginning of OFS_DELTA dats to find the object the\ndelta applies to. This newer variant is what is known as \"varint\"\nand used throughout the other parts of the system (see hits from\n\"git grep -e ncode_varint\").\n\nWe need to be careful when using a generic \"varint\" to mean the\nolder variant as it would confuse readers of OFS_DELTA section.\n\n\t... goes and looks ...\n\nThe phrase \"offset encoding\" is used in the document to talk about\nOFS_DELTA offset. It is actually what the rest of the code thinks\nis the canonical varint defined in varint.[ch]).\n\nA way to avoid confusion would be to refrain from using \"varint\" as\nthe primary way to describe this size field; instead explain it as\nthe \"size encoding\", to match \"offset encoding\" used for OFS_DELTA.\n\nIt may also help if we added to the description of \"offset encoding\"\nthat it is what other parts of the system consider the canonical\n\"varint\" encoding.\n\nThanks.\n\n> === Deltified representation\n> Conceptually there are only four object types: commit, tree, tag and\n> @@ -196,10 +205,10 @@ Pack file entry: <+\n> \t1-byte size extension bit (MSB)\n> \t type (next 3 bit)\n> \t size0 (lower 4-bit)\n> - n-byte sizeN (as long as MSB is set, each 7-bit)\n> -\t\tsize0..sizeN form 4+7+7+..+7 bit integer, size0\n> -\t\tis the least significant part, and sizeN is the\n> -\t\tmost significant part.\n> + n-byte size1 (varint encoding; present if MSB is set)\n> + If the MSB is set, the size is size0 + 16*size1, otherwise\n> + it is size0. (Equivalently, the entire packed object header\n> + is a varint encoding of (size/16)*128 + type*16 + size%16.)\n> packed object data:\n> If it is not DELTA, then deflated bytes (the size above\n> \t\tis the size before compression).\n"},{"id":"412906","messageId":"CAEs=z9Pjh=4mLoW1m9dnNuLL7HmpD3u-rdEmN41ONBOhr474ZQ@mail.gmail.com","threadId":"54858","inReplyTo":"cover.1608537234.git.martin.agren@gmail.com","subject":"Re: [PATCH 0/2] pack-format.txt: document lengths at start of delta data","fromName":"Ross Light","fromEmail":"ross@zombiezen.com","sentAt":"2020-12-23T04:40:49Z","receivedAt":"2020-12-23T04:41:44Z","isPatch":true,"sender":{"key":"ross@zombiezen.com","avatar":null},"body":"Looks good to me, FWIW. Thank you! :)\n\n-Ross\n\nOn Sun, Dec 20, 2020 at 11:55 PM Martin Ågren wrote:\n>\n> Hi Ross,\n>\n> Welcome to the list and thanks for reporting your findings. I haven't\n> looked at all at the first issue you brought up, about the protocol-v2\n> doc.\n>\n> On Sat, 19 Dec 2020 at 18:10, Ross Light wrote:\n> > 2. In the pack-format doc, the Deltified representation section [2]\n> > describes the instruction sequence well, but neglects to mention the\n> > two size varints [3] at the beginning of such an object.\n>\n> Would something like this be what you have in mind?\n>\n> Martin Ågren (2):\n> pack-format.txt: define \"varint\" format\n> pack-format.txt: document lengths at start of delta data\n>\n> Documentation/technical/pack-format.txt | 22 +++++++++++++++++-----\n> 1 file changed, 17 insertions(+), 5 deletions(-)\n>\n> --\n> 2.30.0.rc1\n>\n"},{"id":"413148","messageId":"CAN0heSrEPt3=-uccGk2fKu=ScbE1Bq-cpsvisBcsoXdUC2sz5Q@mail.gmail.com","threadId":"54858","inReplyTo":"xmqqft3yltxo.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/2] pack-format.txt: define \"varint\" format","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2020-12-29T22:41:58Z","receivedAt":"2020-12-29T22:43:02Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"On Mon, 21 Dec 2020 at 22:40, Junio C Hamano wrote:\n>\n> Martin Ågren writes:\n>\n> > We define our varint format pretty much on the fly as we describe a pack\n> > file entry. In preparation for referring to it in more places in this\n> > document, define \"varint\" and refer to it.\n\n> We need to be careful when using a generic \"varint\" to mean the\n> older variant as it would confuse readers of OFS_DELTA section.\n>\n> ... goes and looks ...\n>\n> The phrase \"offset encoding\" is used in the document to talk about\n> OFS_DELTA offset. It is actually what the rest of the code thinks\n> is the canonical varint defined in varint.[ch]).\n>\n> A way to avoid confusion would be to refrain from using \"varint\" as\n> the primary way to describe this size field; instead explain it as\n> the \"size encoding\", to match \"offset encoding\" used for OFS_DELTA.\n\nThank you very much for these comments. I will post a v2 soon, which\nwill do exactly this: avoid \"varint\" in favor of \"size encoding\".\n\n> It may also help if we added to the description of \"offset encoding\"\n> that it is what other parts of the system consider the canonical\n> \"varint\" encoding.\n\nI will leave this as #leftoverbits, though. I'll \"only\" fix the omission\nreported by Ross.\n\nMartin\n"},{"id":"413149","messageId":"20201229224335.8989-1-martin.agren@gmail.com","threadId":"54858","inReplyTo":"cover.1608537234.git.martin.agren@gmail.com","subject":"[PATCH v2] pack-format.txt: document sizes at start of delta data","fromName":"Martin Ågren","fromEmail":"martin.agren@gmail.com","sentAt":"2020-12-29T22:43:35Z","receivedAt":"2020-12-29T22:44:57Z","isPatch":true,"sender":{"key":"martin.agren@gmail.com","avatar":null},"body":"We document the delta data as a set of instructions, but forget to\ndocument the two sizes that precede those instructions: the size of the\nbase object and the size of the object to be reconstructed. Fix this\nomission.\n\nRather than cramming all the details about the encoding into the running\ntext, introduce a separate section detailing our \"size encoding\" and\nrefer to it.\n\nReported-by: Ross Light \nSigned-off-by: Martin Ågren \n---\n v1: https://lore.kernel.org/git/cover.1608537234.git.martin.agren@gmail.com/\n\n Documentation/technical/pack-format.txt | 17 ++++++++++++++++-\n 1 file changed, 16 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex f96b2e605f..96d2fc589f 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -55,6 +55,18 @@ Valid object types are:\n \n Type 5 is reserved for future expansion. Type 0 is invalid.\n \n+=== Size encoding\n+\n+This document uses the following \"size encoding\" of non-negative\n+integers: From each byte, the seven least significant bits are\n+used to form the resulting integer. As long as the most significant\n+bit is 1, this process continues; the byte with MSB 0 provides the\n+last seven bits. The seven-bit chunks are concatenated. Later\n+values are more significant.\n+\n+This size encoding should not be confused with the \"offset encoding\",\n+which is also used in this document.\n+\n === Deltified representation\n \n Conceptually there are only four object types: commit, tree, tag and\n@@ -73,7 +85,10 @@ Ref-delta can also refer to an object outside the pack (i.e. the\n so-called \"thin pack\"). When stored on disk however, the pack should\n be self contained to avoid cyclic dependency.\n \n-The delta data is a sequence of instructions to reconstruct an object\n+The delta data starts with the size of the base object and the\n+size of the object to be reconstructed. These sizes are\n+encoded using the size encoding from above. The remainder of\n+the delta data is a sequence of instructions to reconstruct the object\n from the base object. If the base object is deltified, it must be\n converted to canonical form first. Each instruction appends more and\n more data to the target object until it's complete. There are two\n-- \n2.30.0\n\n"}]}